Merge branch 'master' into urcu/ht

[urcu.git] / rculfhash.c

diff --git a/rculfhash.c b/rculfhash.c
index 64875f6a57ba96025d076319f35772f6b0ca96a2..98547851b210a64e25788eef3cca2bc87f7ce8e0 100644 (file)
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -77,6 +77,11 @@
  *   that is does not contain the "removed" node anymore, even if
  *   concurrent delete/add operations are changing the structure of the
  *   list concurrently.
+ * - The add operation performs gargage collection of buckets if it
+ *   encounters nodes with removed flag set in the bucket where it wants
+ *   to add its new node. This ensures lock-freedom of add operation by
+ *   helping the remover unlink nodes from the list rather than to wait
+ *   for it do to so.
  * - A RCU "order table" indexed by log2(hash index) is copied and
  *   expanded by the resize operation. This order table allows finding
  *   the "dummy node" tables.
@@ -420,10 +425,10 @@ void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
                for (;;) {
                        if (unlikely(!clear_flag(iter)))
                                return;
-                       if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)
+                       if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
                                return;
                        next = rcu_dereference(clear_flag(iter)->p.next);
-                       if (is_removed(next))
+                       if (likely(is_removed(next)))
                                break;
                        iter_prev = clear_flag(iter);
                        iter = next;
@@ -469,10 +474,10 @@ struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
                for (;;) {
                        if (unlikely(!clear_flag(iter)))
                                goto insert;
-                       if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)
+                       if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
                                goto insert;
                        next = rcu_dereference(clear_flag(iter)->p.next);
-                       if (is_removed(next))
+                       if (unlikely(is_removed(next)))
                                goto gc_node;
                        if (unique
                            && !is_dummy(next)
@@ -535,7 +540,7 @@ int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
        old = rcu_dereference(node->p.next);
        do {
                next = old;
-               if (is_removed(next))
+               if (unlikely(is_removed(next)))
                        goto end;
                assert(!is_dummy(next));
                old = uatomic_cmpxchg(&node->p.next, next,