rculfhash: break in-progress resize when target size change (between levels)
[urcu.git] / rculfhash.c
index f95ef5dc083aa4e22618512708beb37cee22e1e3..1391b6bb630102c18138ffe953e745e806808d62 100644 (file)
@@ -752,10 +752,8 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
                iter = rcu_dereference(iter_prev->p.next);
                assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
                for (;;) {
-                       /* TODO: check if removed */
                        if (unlikely(!clear_flag(iter)))
                                goto insert;
-                       /* TODO: check if removed */
                        if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
                                goto insert;
                        next = rcu_dereference(clear_flag(iter)->p.next);
@@ -883,6 +881,11 @@ void init_table_hash(struct cds_lfht *ht, unsigned long i,
        }
 }
 
+/*
+ * Holding RCU read lock to protect _cds_lfht_add against memory
+ * reclaim that could be performed by other call_rcu worker threads (ABA
+ * problem).
+ */
 static
 void init_table_link(struct cds_lfht *ht, unsigned long i, unsigned long len)
 {
@@ -905,11 +908,6 @@ void init_table_link(struct cds_lfht *ht, unsigned long i, unsigned long len)
        ht->cds_lfht_rcu_thread_offline();
 }
 
-/*
- * Holding RCU read lock to protect _cds_lfht_add against memory
- * reclaim that could be performed by other call_rcu worker threads (ABA
- * problem).
- */
 static
 void init_table(struct cds_lfht *ht,
                unsigned long first_order, unsigned long len_order)
@@ -924,6 +922,11 @@ void init_table(struct cds_lfht *ht,
 
                len = !i ? 1 : 1UL << (i - 1);
                dbg_printf("init order %lu len: %lu\n", i, len);
+
+               /* Stop expand if the resize target changes under us */
+               if (CMM_LOAD_SHARED(ht->t.resize_target) < (!i ? 1 : (1UL << i)))
+                       break;
+
                ht->t.tbl[i] = calloc(1, sizeof(struct rcu_level)
                                + (len * sizeof(struct _cds_lfht_node)));
 
@@ -948,6 +951,26 @@ void init_table(struct cds_lfht *ht,
        }
 }
 
+/*
+ * Holding RCU read lock to protect _cds_lfht_remove against memory
+ * reclaim that could be performed by other call_rcu worker threads (ABA
+ * problem).
+ * For a single level, we logically remove and garbage collect each node.
+ *
+ * As a design choice, we perform logical removal and garbage collection on a
+ * node-per-node basis to simplify this algorithm. We also assume keeping good
+ * cache locality of the operation would overweight possible performance gain
+ * that could be achieved by batching garbage collection for multiple levels.
+ * However, this would have to be justified by benchmarks.
+ *
+ * Concurrent removal and add operations are helping us perform garbage
+ * collection of logically removed nodes. We guarantee that all logically
+ * removed nodes have been garbage-collected (unlinked) before call_rcu is
+ * invoked to free a hole level of dummy nodes (after a grace period).
+ *
+ * Logical removal and garbage collection can therefore be done in batch or on a
+ * node-per-node basis, as long as the guarantee above holds.
+ */
 static
 void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
 {
@@ -972,11 +995,6 @@ void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
        ht->cds_lfht_rcu_thread_offline();
 }
 
-/*
- * Holding RCU read lock to protect _cds_lfht_remove against memory
- * reclaim that could be performed by other call_rcu worker threads (ABA
- * problem).
- */
 static
 void fini_table(struct cds_lfht *ht,
                unsigned long first_order, unsigned long len_order)
@@ -987,13 +1005,27 @@ void fini_table(struct cds_lfht *ht,
                   first_order, first_order + len_order);
        end_order = first_order + len_order;
        assert(first_order > 0);
-       assert(ht->t.size == (1UL << (first_order - 1)));
        for (i = end_order - 1; i >= first_order; i--) {
                unsigned long len;
 
                len = !i ? 1 : 1UL << (i - 1);
                dbg_printf("fini order %lu len: %lu\n", i, len);
 
+               /* Stop shrink if the resize target changes under us */
+               if (CMM_LOAD_SHARED(ht->t.resize_target) > (1UL << (i - 1)))
+                       break;
+
+               cmm_smp_wmb();  /* populate data before RCU size */
+               CMM_STORE_SHARED(ht->t.size, 1UL << (i - 1));
+
+               /*
+                * We need to wait for all add operations to reach Q.S. (and
+                * thus use the new table for lookups) before we can start
+                * releasing the old dummy nodes. Otherwise their lookup will
+                * return a logically removed node as insert position.
+                */
+               ht->cds_lfht_synchronize_rcu();
+
                /*
                 * Set "removed" flag in dummy nodes about to be removed.
                 * Unlink all now-logically-removed dummy node pointers.
@@ -1046,6 +1078,7 @@ struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
        ht->flags = flags;
        ht->cds_lfht_rcu_thread_offline();
        pthread_mutex_lock(&ht->resize_mutex);
+       ht->t.resize_target = 1UL << (order - 1);
        init_table(ht, 0, order);
        pthread_mutex_unlock(&ht->resize_mutex);
        ht->cds_lfht_rcu_thread_online();
@@ -1274,17 +1307,6 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
               old_size, old_order, new_size, new_order);
        assert(new_size < old_size);
 
-       cmm_smp_wmb();  /* populate data before RCU size */
-       CMM_STORE_SHARED(ht->t.size, new_size);
-
-       /*
-        * We need to wait for all add operations to reach Q.S. (and
-        * thus use the new table for lookups) before we can start
-        * releasing the old dummy nodes. Otherwise their lookup will
-        * return a logically removed node as insert position.
-        */
-       ht->cds_lfht_synchronize_rcu();
-
        /* Remove and unlink all dummy nodes to remove. */
        fini_table(ht, new_order, old_order - new_order);
 }
@@ -1310,7 +1332,7 @@ void _do_cds_lfht_resize(struct cds_lfht *ht)
                ht->t.resize_initiated = 0;
                /* write resize_initiated before read resize_target */
                cmm_smp_mb();
-       } while (new_size != CMM_LOAD_SHARED(ht->t.resize_target));
+       } while (ht->t.size != CMM_LOAD_SHARED(ht->t.resize_target));
 }
 
 static
This page took 0.024647 seconds and 4 git commands to generate.