rculfhash: flip order of removal

[urcu.git] / rculfhash.c

diff --git a/rculfhash.c b/rculfhash.c
index f09f6132aa458103a216be214e011acc5586a410..24783bbdb619d4f4bf39d671780ff756e190f8c8 100644 (file)
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -46,8 +46,8 @@
 #define dbg_printf(args...)
 #endif
 
-#define CHAIN_LEN_TARGET               4
-#define CHAIN_LEN_RESIZE_THRESHOLD     16
+#define CHAIN_LEN_TARGET               1
+#define CHAIN_LEN_RESIZE_THRESHOLD     2
 
 #ifndef max
 #define max(a, b)      ((a) > (b) ? (a) : (b))
@@ -169,7 +169,7 @@ void check_resize(struct rcu_ht *ht, struct rcu_table *t,
 {
        if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
                ht_resize_lazy(ht, t,
-                       log2_u32(chain_len - CHAIN_LEN_TARGET));
+                       log2_u32(chain_len - CHAIN_LEN_TARGET - 1));
 }
 
 static
@@ -205,12 +205,13 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
 }
 
 static
-void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
+int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
+            int unique)
 {
        struct rcu_ht_node *iter_prev, *iter, *iter_prev_next, *next;
 
        if (!t->size)
-               return;
+               return 0;
        for (;;) {
                uint32_t chain_len = 0;
 
@@ -232,6 +233,12 @@ void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
                        next = rcu_dereference(clear_flag(iter)->next);
                        if (unlikely(is_removed(next)))
                                continue;
+                       if (unique
+                           && !clear_flag(iter)->dummy
+                           && !ht->compare_fct(node->key, node->key_len,
+                                       clear_flag(iter)->key,
+                                       clear_flag(iter)->key_len))
+                               return -EEXIST;
                        if (clear_flag(iter)->reverse_hash > node->reverse_hash)
                                break;
                        /* Only account for identical reverse hash once */
@@ -240,7 +247,7 @@ void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
                        iter_prev = clear_flag(iter);
                        iter_prev_next = next;
                }
-               assert(node != iter);
+               assert(node != clear_flag(iter));
                assert(!is_removed(iter_prev));
                assert(iter_prev != node);
                node->next = iter;
@@ -250,23 +257,39 @@ void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
                else
                        break;
        }
+       return 0;
 }
 
 static
 int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 {
        struct rcu_ht_node *iter_prev, *iter, *iter_prev_next, *next, *old;
-       unsigned long chain_len;
        int found;
        int flagged = 0;
 
+       /* logically delete the node */
+       old = rcu_dereference(node->next);
+       do {
+               next = old;
+               if (is_removed(next))
+                       goto end;
+               old = uatomic_cmpxchg(&node->next, next,
+                                     flag_removed(next));
+       } while (old != next);
+
+       /* We performed the (logical) deletion. */
+       flagged = 1;
+
+       /*
+        * Ensure that the node is not visible to readers anymore: lookup for
+        * the node, and remove it if found.
+        */
 retry:
-       chain_len = 0;
        found = 0;
        /*
         * iter_prev points to the non-removed node prior to the remove
         * location.
-        * node is the node to remove.
+        * next points to the non-removed node following the remove location.
         */
        iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
        /* We can always skip the dummy node initially */
@@ -278,8 +301,9 @@ retry:
                if (unlikely(!clear_flag(iter)))
                        break;
                next = rcu_dereference(clear_flag(iter)->next);
-               if (iter == node) {
+               if (clear_flag(iter) == node) {
                        found = 1;
+                       assert(is_removed(rcu_dereference(node->next)));
                        break;
                }
                if (unlikely(is_removed(next)))
@@ -291,31 +315,6 @@ retry:
        } 
        if (!found)
                goto end;
-       if (!flagged) {
-               if (is_removed(next))
-                       goto end;
-               /* set deletion flag */
-               if ((old = uatomic_cmpxchg(&iter->next, next,
-                                          flag_removed(next))) != next) {
-                       if (old == flag_removed(next))
-                               goto end;
-                       else
-                               goto retry;
-               }
-               flagged = 1;
-       }
-       /*
-        * Remove the element from the list.
-        * - Retry if there has been a concurrent add before us.
-        * - Retry if the prev node has been deleted (its next removed
-        *   flag would be set).
-        * - There cannot be a concurrent delete for our position, because
-        *   we won the deletion flag cmpxchg.
-        * - If there is a concurrent add or remove after us while our
-        *   removed flag is set, it will skip us and link directly after
-        *   the prior non-removed node before us. In this case, the
-        *   retry will not find the node in the list anymore.
-        */
        if (uatomic_cmpxchg(&iter_prev->next, iter_prev_next,
                            clear_flag(next)) != iter_prev_next)
                goto retry;
@@ -324,9 +323,10 @@ end:
         * Only the flagging action indicated that we (and no other)
         * removed the node from the hash.
         */
-       if (flagged)
+       if (flagged) {
+               assert(is_removed(rcu_dereference(node->next)));
                return 0;
-       else
+       } else
                return -ENOENT;
 }
 
@@ -345,7 +345,7 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t,
                t->tbl[i]->dummy = 1;
                t->tbl[i]->hash = i;
                t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
-               _ht_add(ht, t, t->tbl[i]);
+               (void) _ht_add(ht, t, t->tbl[i], 0);
        }
        t->resize_target = t->size = end;
        t->resize_initiated = 0;
@@ -412,7 +412,18 @@ void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
        node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
 
        t = rcu_dereference(ht->t);
-       _ht_add(ht, t, node);
+       (void) _ht_add(ht, t, node, 0);
+}
+
+int ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
+{
+       struct rcu_table *t;
+
+       node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
+       node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
+
+       t = rcu_dereference(ht->t);
+       return _ht_add(ht, t, node, 1);
 }
 
 int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)