From 98f969fc5e7fcd7dcc260dde0ef788e8df50775a Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 6 Jul 2011 01:07:33 -0400 Subject: [PATCH] Comment list behavior wrt lock-freedom Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/rculfhash.c b/rculfhash.c index f1e6674..4abf27a 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -225,7 +225,10 @@ void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node) iter_prev = iter; check_resize(ht, t, ++chain_len); } - /* add in iter_prev->next */ + /* + * add in iter_prev->next: TODO: check for helping + * delete, for lock-freedom... + */ if (is_removed(iter)) continue; assert(node != iter); @@ -286,9 +289,13 @@ retry: flagged = 1; } /* - * Remove the element from the list. Retry if there has been a - * concurrent add (there cannot be a concurrent delete, because - * we won the deletion flag cmpxchg). + * Remove the element from the list. + * Retry if there has been a concurrent add before us. + * Retry if the prev node has been deleted. + * There cannot be a concurrent delete for our position, because + * we won the deletion flag cmpxchg. + * If there is a concurrent add after us, our deletion flag + * makes it busy-loop (FIXME: not lock-free). */ if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter) goto retry; -- 2.34.1