X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=5264a8ec7fc9747afeccbc544dad3d2b3a80a54a;hp=2e338f132e66bb5c6a1271f9cdf2bc8730055aea;hb=0adc36a89d4089a653c11a68ea6fb92a2ec7c5aa;hpb=0d14ceb26e0ff3e1d6f86cf3ec9674ee3b16e96f diff --git a/rculfhash.c b/rculfhash.c index 2e338f1..5264a8e 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -119,12 +119,9 @@ * * order bits reverse * 0 0 000 000 - * | - * 1 | 1 001 100 <- <- - * | | | | - * 2 | | 2 010 010 | | + * 1 | 1 001 100 <- + * 2 | | 2 010 010 <- | * | | | 3 011 110 | <- | - * | | | | | | | * 3 -> | | | 4 100 001 | | * -> | | 5 101 101 | * -> | 6 110 011 @@ -262,17 +259,12 @@ struct partition_resize_work { unsigned long start, unsigned long len); }; -enum add_mode { - ADD_DEFAULT = 0, - ADD_UNIQUE = 1, - ADD_REPLACE = 2, -}; - static -struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, - unsigned long size, - struct cds_lfht_node *node, - enum add_mode mode, int dummy); +void _cds_lfht_add(struct cds_lfht *ht, + unsigned long size, + struct cds_lfht_node *node, + struct cds_lfht_iter *unique_ret, + int dummy); /* * Algorithm to reverse bits in a word by lookup table, extended to @@ -716,6 +708,27 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v) return v; } +static +struct _cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size, + unsigned long hash) +{ + unsigned long index, order; + + assert(size > 0); + index = hash & (size - 1); + /* + * equivalent to get_count_order_ulong(index + 1), but optimizes + * away the non-existing 0 special-case for + * get_count_order_ulong. + */ + order = fls_ulong(index); + + dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", + hash, index, order, index & (!order ? 0 : ((1UL << (order - 1)) - 1))); + + return &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; +} + /* * Remove all logically deleted nodes from a bucket up to a certain node key. */ @@ -732,6 +745,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node iter_prev = dummy; /* We can always skip the dummy node initially */ iter = rcu_dereference(iter_prev->p.next); + assert(!is_removed(iter)); assert(iter_prev->p.reverse_hash <= node->p.reverse_hash); /* * We should never be called with dummy (start of chain) @@ -756,8 +770,6 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node new_next = flag_dummy(clear_flag(next)); else new_next = clear_flag(next); - if (is_removed(iter)) - new_next = flag_removed(new_next); (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); } return; @@ -766,31 +778,28 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node static int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, struct cds_lfht_node *old_node, - struct cds_lfht_node *ret_next, + struct cds_lfht_node *old_next, struct cds_lfht_node *new_node) { - struct cds_lfht_node *dummy, *old_next; + struct cds_lfht_node *dummy, *ret_next; struct _cds_lfht_node *lookup; - int flagged = 0; - unsigned long hash, index, order; if (!old_node) /* Return -ENOENT if asked to replace NULL node */ - goto end; + return -ENOENT; assert(!is_removed(old_node)); assert(!is_dummy(old_node)); assert(!is_removed(new_node)); assert(!is_dummy(new_node)); assert(new_node != old_node); - do { + for (;;) { /* Insert after node to be replaced */ - old_next = ret_next; if (is_removed(old_next)) { /* * Too late, the old node has been removed under us * between lookup and replace. Fail. */ - goto end; + return -ENOENT; } assert(!is_dummy(old_next)); assert(new_node != clear_flag(old_next)); @@ -807,55 +816,48 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, */ ret_next = uatomic_cmpxchg(&old_node->p.next, old_next, flag_removed(new_node)); - } while (ret_next != old_next); - - /* We performed the replacement. */ - flagged = 1; + if (ret_next == old_next) + break; /* We performed the replacement. */ + old_next = ret_next; + } /* * Ensure that the old node is not visible to readers anymore: * lookup for the node, and remove it (along with any other * logically removed node) if found. */ - hash = bit_reverse_ulong(old_node->p.reverse_hash); - assert(size > 0); - index = hash & (size - 1); - order = get_count_order_ulong(index + 1); - lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; + lookup = lookup_bucket(ht, size, bit_reverse_ulong(old_node->p.reverse_hash)); dummy = (struct cds_lfht_node *) lookup; _cds_lfht_gc_bucket(dummy, new_node); -end: - /* - * Only the flagging action indicated that we (and no other) - * replaced the node from the hash table. - */ - if (flagged) { - assert(is_removed(rcu_dereference(old_node->p.next))); - return 0; - } else { - return -ENOENT; - } + + assert(is_removed(rcu_dereference(old_node->p.next))); + return 0; } +/* + * A non-NULL unique_ret pointer uses the "add unique" (or uniquify) add + * mode. A NULL unique_ret allows creation of duplicate keys. + */ static -struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, - unsigned long size, - struct cds_lfht_node *node, - enum add_mode mode, int dummy) +void _cds_lfht_add(struct cds_lfht *ht, + unsigned long size, + struct cds_lfht_node *node, + struct cds_lfht_iter *unique_ret, + int dummy) { struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next, - *dummy_node, *return_node; + *return_node; struct _cds_lfht_node *lookup; - unsigned long hash, index, order; assert(!is_dummy(node)); assert(!is_removed(node)); if (!size) { assert(dummy); + assert(!unique_ret); node->p.next = flag_dummy(get_end()); - return node; /* Initial first add (head) */ + return; /* Initial first add (head) */ } - hash = bit_reverse_ulong(node->p.reverse_hash); + lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash)); for (;;) { uint32_t chain_len = 0; @@ -863,9 +865,6 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, * iter_prev points to the non-removed node prior to the * insert location. */ - index = hash & (size - 1); - order = get_count_order_ulong(index + 1); - lookup = &ht->t.tbl[order]->nodes[index & ((!order ? 0 : (1UL << (order - 1))) - 1)]; iter_prev = (struct cds_lfht_node *) lookup; /* We can always skip the dummy node initially */ iter = rcu_dereference(iter_prev->p.next); @@ -875,18 +874,21 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, goto insert; if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)) goto insert; + /* dummy node is the first node of the identical-hash-value chain */ + if (dummy && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) + goto insert; next = rcu_dereference(clear_flag(iter)->p.next); if (unlikely(is_removed(next))) goto gc_node; - if ((mode == ADD_UNIQUE || mode == ADD_REPLACE) + if (unique_ret && !is_dummy(next) + && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash && !ht->compare_fct(node->key, node->key_len, clear_flag(iter)->key, clear_flag(iter)->key_len)) { - if (mode == ADD_UNIQUE) - return clear_flag(iter); - else /* mode == ADD_REPLACE */ - goto replace; + unique_ret->node = clear_flag(iter); + unique_ret->next = next; + return; } /* Only account for identical reverse hash once */ if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash @@ -913,21 +915,8 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, new_node) != iter) { continue; /* retry */ } else { - if (mode == ADD_REPLACE) - return_node = NULL; - else /* ADD_DEFAULT and ADD_UNIQUE */ - return_node = node; - goto gc_end; - } - - replace: - - if (!_cds_lfht_replace(ht, size, clear_flag(iter), next, - node)) { - return_node = clear_flag(iter); - goto end; /* gc already done */ - } else { - continue; /* retry */ + return_node = node; + goto end; } gc_node: @@ -939,15 +928,11 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); /* retry */ } -gc_end: - /* Garbage collect logically removed nodes in the bucket */ - index = hash & (size - 1); - order = get_count_order_ulong(index + 1); - lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; - dummy_node = (struct cds_lfht_node *) lookup; - _cds_lfht_gc_bucket(dummy_node, node); end: - return return_node; + if (unique_ret) { + unique_ret->node = return_node; + /* unique_ret->next left unset, never used. */ + } } static @@ -957,11 +942,9 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, { struct cds_lfht_node *dummy, *next, *old; struct _cds_lfht_node *lookup; - int flagged = 0; - unsigned long hash, index, order; if (!node) /* Return -ENOENT if asked to delete NULL node */ - goto end; + return -ENOENT; /* logically delete the node */ assert(!is_dummy(node)); @@ -972,7 +955,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, next = old; if (unlikely(is_removed(next))) - goto end; + return -ENOENT; if (dummy_removal) assert(is_dummy(next)); else @@ -980,33 +963,19 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, new_next = flag_removed(next); old = uatomic_cmpxchg(&node->p.next, next, new_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 (along with any other logically removed node) * if found. */ - hash = bit_reverse_ulong(node->p.reverse_hash); - assert(size > 0); - index = hash & (size - 1); - order = get_count_order_ulong(index + 1); - lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; + lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash)); dummy = (struct cds_lfht_node *) lookup; _cds_lfht_gc_bucket(dummy, node); -end: - /* - * Only the flagging action indicated that we (and no other) - * removed the node from the hash. - */ - if (flagged) { - assert(is_removed(rcu_dereference(node->p.next))); - return 0; - } else { - return -ENOENT; - } + + assert(is_removed(rcu_dereference(node->p.next))); + return 0; } static @@ -1088,8 +1057,8 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, i, j, !i ? 0 : (1UL << (i - 1)) + j); new_node->p.reverse_hash = bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j); - (void) _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)), - new_node, ADD_DEFAULT, 1); + _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)), + new_node, NULL, 1); } ht->cds_lfht_rcu_read_unlock(); } @@ -1318,17 +1287,13 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, { struct cds_lfht_node *node, *next, *dummy_node; struct _cds_lfht_node *lookup; - unsigned long hash, reverse_hash, index, order, size; + unsigned long hash, reverse_hash, size; hash = ht->hash_fct(key, key_len, ht->hash_seed); reverse_hash = bit_reverse_ulong(hash); size = rcu_dereference(ht->t.size); - index = hash & (size - 1); - order = get_count_order_ulong(index + 1); - lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1))) - 1)]; - dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", - hash, index, order, index & (!order ? 0 : ((1UL << (order - 1)) - 1))); + lookup = lookup_bucket(ht, size, hash); dummy_node = (struct cds_lfht_node *) lookup; /* We can always skip the dummy node initially */ node = rcu_dereference(dummy_node->p.next); @@ -1345,6 +1310,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, next = rcu_dereference(node->p.next); if (likely(!is_removed(next)) && !is_dummy(next) + && clear_flag(node)->p.reverse_hash == reverse_hash && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) { break; } @@ -1434,7 +1400,7 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node) node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); size = rcu_dereference(ht->t.size); - (void) _cds_lfht_add(ht, size, node, ADD_DEFAULT, 0); + _cds_lfht_add(ht, size, node, NULL, 0); ht_count_add(ht, size); } @@ -1442,32 +1408,38 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, struct cds_lfht_node *node) { unsigned long hash, size; - struct cds_lfht_node *ret; + struct cds_lfht_iter iter; hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); size = rcu_dereference(ht->t.size); - ret = _cds_lfht_add(ht, size, node, ADD_UNIQUE, 0); - if (ret == node) + _cds_lfht_add(ht, size, node, &iter, 0); + if (iter.node == node) ht_count_add(ht, size); - return ret; + return iter.node; } struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, struct cds_lfht_node *node) { unsigned long hash, size; - struct cds_lfht_node *ret; + struct cds_lfht_iter iter; hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); size = rcu_dereference(ht->t.size); - ret = _cds_lfht_add(ht, size, node, ADD_REPLACE, 0); - if (ret == NULL) - ht_count_add(ht, size); - return ret; + for (;;) { + _cds_lfht_add(ht, size, node, &iter, 0); + if (iter.node == node) { + ht_count_add(ht, size); + return NULL; + } + + if (!_cds_lfht_replace(ht, size, iter.node, iter.next, node)) + return iter.node; + } } int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,