Version 0.7.11

[userspace-rcu.git] / rculfhash.c

diff --git a/rculfhash.c b/rculfhash.c
index e9cf0622f53576ef8ad8c08eda082c37f1151b86..a997117f44548835442c78719bc95499fba3e0b9 100644 (file)
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -561,6 +561,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 
 static long nr_cpus_mask = -1;
 static long split_count_mask = -1;
+static int split_count_order = -1;
 
 #if defined(HAVE_SYSCONF)
 static void ht_init_nr_cpus_mask(void)
@@ -597,6 +598,8 @@ void alloc_split_items_count(struct cds_lfht *ht)
                        split_count_mask = DEFAULT_SPLIT_COUNT_MASK;
                else
                        split_count_mask = nr_cpus_mask;
+               split_count_order =
+                       cds_lfht_get_count_order_ulong(split_count_mask + 1);
        }
 
        assert(split_count_mask >= 0);
@@ -712,14 +715,39 @@ void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
         * Use bucket-local length for small table expand and for
         * environments lacking per-cpu data support.
         */
-       if (count >= (1UL << COUNT_COMMIT_ORDER))
+       if (count >= (1UL << (COUNT_COMMIT_ORDER + split_count_order)))
                return;
        if (chain_len > 100)
                dbg_printf("WARNING: large chain length: %u.\n",
                           chain_len);
-       if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
-               cds_lfht_resize_lazy_grow(ht, size,
-                       cds_lfht_get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
+       if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) {
+               int growth;
+
+               /*
+                * Ideal growth calculated based on chain length.
+                */
+               growth = cds_lfht_get_count_order_u32(chain_len
+                               - (CHAIN_LEN_TARGET - 1));
+               if ((ht->flags & CDS_LFHT_ACCOUNTING)
+                               && (size << growth)
+                                       >= (1UL << (COUNT_COMMIT_ORDER
+                                               + split_count_order))) {
+                       /*
+                        * If ideal growth expands the hash table size
+                        * beyond the "small hash table" sizes, use the
+                        * maximum small hash table size to attempt
+                        * expanding the hash table. This only applies
+                        * when node accounting is available, otherwise
+                        * the chain length is used to expand the hash
+                        * table in every case.
+                        */
+                       growth = COUNT_COMMIT_ORDER + split_count_order
+                               - cds_lfht_get_count_order_ulong(size);
+                       if (growth <= 0)
+                               return;
+               }
+               cds_lfht_resize_lazy_grow(ht, size, growth);
+       }
 }
 
 static
@@ -832,13 +860,16 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *nod
 
        assert(!is_bucket(bucket));
        assert(!is_removed(bucket));
+       assert(!is_removal_owner(bucket));
        assert(!is_bucket(node));
        assert(!is_removed(node));
+       assert(!is_removal_owner(node));
        for (;;) {
                iter_prev = bucket;
                /* We can always skip the bucket node initially */
                iter = rcu_dereference(iter_prev->next);
                assert(!is_removed(iter));
+               assert(!is_removal_owner(iter));
                assert(iter_prev->reverse_hash <= node->reverse_hash);
                /*
                 * We should never be called with bucket (start of chain)
@@ -859,6 +890,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *nod
                        iter = next;
                }
                assert(!is_removed(iter));
+               assert(!is_removal_owner(iter));
                if (is_bucket(iter))
                        new_next = flag_bucket(clear_flag(next));
                else
@@ -879,8 +911,10 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
                return -ENOENT;
 
        assert(!is_removed(old_node));
+       assert(!is_removal_owner(old_node));
        assert(!is_bucket(old_node));
        assert(!is_removed(new_node));
+       assert(!is_removal_owner(new_node));
        assert(!is_bucket(new_node));
        assert(new_node != old_node);
        for (;;) {
@@ -955,6 +989,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
        assert(!is_bucket(node));
        assert(!is_removed(node));
+       assert(!is_removal_owner(node));
        bucket = lookup_bucket(ht, size, hash);
        for (;;) {
                uint32_t chain_len = 0;
@@ -1015,7 +1050,9 @@ void _cds_lfht_add(struct cds_lfht *ht,
        insert:
                assert(node != clear_flag(iter));
                assert(!is_removed(iter_prev));
+               assert(!is_removal_owner(iter_prev));
                assert(!is_removed(iter));
+               assert(!is_removal_owner(iter));
                assert(iter_prev != node);
                if (!bucket_flag)
                        node->next = clear_flag(iter);
@@ -1035,6 +1072,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
        gc_node:
                assert(!is_removed(iter));
+               assert(!is_removal_owner(iter));
                if (is_bucket(iter))
                        new_next = flag_bucket(clear_flag(next));
                else
@@ -1073,6 +1111,11 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
        if (caa_unlikely(is_removed(next)))
                return -ENOENT;
        assert(!is_bucket(next));
+       /*
+        * The del operation semantic guarantees a full memory barrier
+        * before the uatomic_or atomic commit of the deletion flag.
+        */
+       cmm_smp_mb__before_uatomic_or();
        /*
         * We set the REMOVED_FLAG unconditionally. Note that there may
         * be more than one concurrent thread setting this flag.
@@ -1692,6 +1735,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
                if (!is_bucket(node))
                        return -EPERM;
                assert(!is_removed(node));
+               assert(!is_removal_owner(node));
        } while (!is_end(node));
        /*
         * size accessed without rcu_dereference because hash table is
@@ -1723,8 +1767,10 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
        /* Wait for in-flight resize operations to complete */
        _CMM_STORE_SHARED(ht->in_progress_destroy, 1);
        cmm_smp_mb();   /* Store destroy before load resize */
+       ht->flavor->thread_offline();
        while (uatomic_read(&ht->in_progress_resize))
                poll(NULL, 0, 100);     /* wait for 100ms */
+       ht->flavor->thread_online();
        ret = cds_lfht_delete_bucket(ht);
        if (ret)
                return ret;