X-Git-Url: https://git.lttng.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=d22b44d25135b9a69a8faa7377ed8fb6fb72df16;hp=8f2d8e4480fda449fbe6dd9de2bb69a2659d8643;hb=0f5543cb1780acef35878646e6cdc966f1406c18;hpb=b65ec430efc1882ba63452a7fae7bbeea9446526 diff --git a/rculfhash.c b/rculfhash.c index 8f2d8e4..d22b44d 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -71,18 +71,18 @@ * (not visible to lookups anymore) before the RCU read-side critical * section held across removal ends. Furthermore, this ensures that * the node with "removed" flag set is removed from the linked-list - * before its memory is reclaimed. Only the thread which removal - * successfully set the "removed" flag (with a cmpxchg) into a node's - * next pointer is considered to have succeeded its removal (and thus - * owns the node to reclaim). Because we garbage-collect starting from - * an invariant node (the start-of-bucket bucket node) up to the - * "removed" node (or find a reverse-hash that is higher), we are sure - * that a successful traversal of the chain leads to a chain that is - * present in the linked-list (the start node is never removed) and - * 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 + * before its memory is reclaimed. After setting the "removal" flag, + * only the thread which removal is the first to set the "removal + * owner" flag (with an xchg) into a node's next pointer is considered + * to have succeeded its removal (and thus owns the node to reclaim). + * Because we garbage-collect starting from an invariant node (the + * start-of-bucket bucket node) up to the "removed" node (or find a + * reverse-hash that is higher), we are sure that a successful + * traversal of the chain leads to a chain that is present in the + * linked-list (the start node is never removed) and 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 garbage 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 @@ -98,6 +98,33 @@ * hash table nodes. These tables are invariant after they are * populated into the hash table. * + * Linearizability Guarantees: + * + * To discuss these guarantees, we first define "read" operations as any + * of the following operations surrounded by an RCU read-side lock/unlock + * pair: + * - cds_lfht_lookup + * - cds_lfht_lookup followed by iteration with cds_lfht_next_duplicate + * - cds_lfht_first followed iteration with cds_lfht_next + * + * We define "write" operations as any of cds_lfht_add, + * cds_lfht_add_unique, cds_lfht_add_replace, cds_lfht_del. + * + * The following guarantees are offered by this hash table: + * + * A) "read" after "write" will always return the result of the latest + * write. + * B) "write" after "read" will never be returned by the read. + * C) It is guaranteed that after a grace period following a "del" and + * "replace" operation, no reference to the removed items exists in + * the hash table. + * D) Uniqueness guarantee: when using add_unique and/or add_replace to + * insert nodes into the table, if there was previously one node or + * less with the same key being inserted by one or more concurrent + * add_unique and/or add_replace, all concurrent "read" performed on + * the hash table are guaranteed to find one, and only one node with + * that key. + * * Bucket node tables: * * hash table hash table the last all bucket node tables @@ -150,12 +177,14 @@ */ #define _LGPL_SOURCE +#define _GNU_SOURCE #include #include #include #include #include #include +#include #include "config.h" #include @@ -779,9 +808,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, */ return -ENOENT; } - assert(!is_bucket(old_next)); - assert(new_node != clear_flag(old_next)); - new_node->next = clear_flag(old_next); + assert(old_next == clear_flag(old_next)); + assert(new_node != old_next); + new_node->next = old_next; /* * Here is the whole trick for lock-free replace: we add * the replacement node _after_ the node we want to @@ -820,6 +849,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, */ static void _cds_lfht_add(struct cds_lfht *ht, + unsigned long hash, cds_lfht_match_fct match, const void *key, unsigned long size, @@ -833,7 +863,7 @@ void _cds_lfht_add(struct cds_lfht *ht, assert(!is_bucket(node)); assert(!is_removed(node)); - bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash)); + bucket = lookup_bucket(ht, size, hash); for (;;) { uint32_t chain_len = 0; @@ -1067,7 +1097,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, dbg_printf("init populate: order %lu index %lu hash %lu\n", i, j, j); new_node->reverse_hash = bit_reverse_ulong(j); - _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1); + _cds_lfht_add(ht, j, NULL, NULL, size, new_node, NULL, 1); } ht->flavor->read_unlock(); } @@ -1471,9 +1501,9 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, { unsigned long size; - node->reverse_hash = bit_reverse_ulong((unsigned long) hash); + node->reverse_hash = bit_reverse_ulong(hash); size = rcu_dereference(ht->size); - _cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0); + _cds_lfht_add(ht, hash, NULL, NULL, size, node, NULL, 0); ht_count_add(ht, size, hash); } @@ -1486,9 +1516,9 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, unsigned long size; struct cds_lfht_iter iter; - node->reverse_hash = bit_reverse_ulong((unsigned long) hash); + node->reverse_hash = bit_reverse_ulong(hash); size = rcu_dereference(ht->size); - _cds_lfht_add(ht, match, key, size, node, &iter, 0); + _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0); if (iter.node == node) ht_count_add(ht, size, hash); return iter.node; @@ -1503,10 +1533,10 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, unsigned long size; struct cds_lfht_iter iter; - node->reverse_hash = bit_reverse_ulong((unsigned long) hash); + node->reverse_hash = bit_reverse_ulong(hash); size = rcu_dereference(ht->size); for (;;) { - _cds_lfht_add(ht, match, key, size, node, &iter, 0); + _cds_lfht_add(ht, hash, match, key, size, node, &iter, 0); if (iter.node == node) { ht_count_add(ht, size, hash); return NULL; @@ -1517,30 +1547,46 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, } } -int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, +int cds_lfht_replace(struct cds_lfht *ht, + struct cds_lfht_iter *old_iter, + unsigned long hash, + cds_lfht_match_fct match, + const void *key, struct cds_lfht_node *new_node) { unsigned long size; + new_node->reverse_hash = bit_reverse_ulong(hash); + if (!old_iter->node) + return -ENOENT; + if (caa_unlikely(old_iter->node->reverse_hash != new_node->reverse_hash)) + return -EINVAL; + if (caa_unlikely(!match(old_iter->node, key))) + return -EINVAL; size = rcu_dereference(ht->size); return _cds_lfht_replace(ht, size, old_iter->node, old_iter->next, new_node); } -int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter) +int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node) { unsigned long size, hash; int ret; size = rcu_dereference(ht->size); - ret = _cds_lfht_del(ht, size, iter->node); + ret = _cds_lfht_del(ht, size, node); if (!ret) { - hash = bit_reverse_ulong(iter->node->reverse_hash); + hash = bit_reverse_ulong(node->reverse_hash); ht_count_del(ht, size, hash); } return ret; } +int cds_lfht_is_node_deleted(struct cds_lfht_node *node) +{ + return is_removed(rcu_dereference(node->next)); +} + static int cds_lfht_delete_bucket(struct cds_lfht *ht) { @@ -1600,11 +1646,10 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr) void cds_lfht_count_nodes(struct cds_lfht *ht, long *approx_before, unsigned long *count, - unsigned long *removed, long *approx_after) { struct cds_lfht_node *node, *next; - unsigned long nr_bucket = 0; + unsigned long nr_bucket = 0, nr_removed = 0; *approx_before = 0; if (ht->split_count) { @@ -1617,7 +1662,6 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, } *count = 0; - *removed = 0; /* Count non-bucket nodes in the table */ node = bucket_at(ht, 0); @@ -1625,7 +1669,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, next = rcu_dereference(node->next); if (is_removed(next)) { if (!is_bucket(next)) - (*removed)++; + (nr_removed)++; else (nr_bucket)++; } else if (!is_bucket(next)) @@ -1634,6 +1678,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, (nr_bucket)++; node = clear_flag(next); } while (!is_end(node)); + dbg_printf("number of logically removed nodes: %lu\n", nr_removed); dbg_printf("number of bucket nodes: %lu\n", nr_bucket); *approx_after = 0; if (ht->split_count) { @@ -1764,6 +1809,11 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht) return; } work = malloc(sizeof(*work)); + if (work == NULL) { + dbg_printf("error allocating resize work, bailing out\n"); + uatomic_dec(&ht->in_progress_resize); + return; + } work->ht = ht; ht->flavor->update_call_rcu(&work->head, do_resize_cb); CMM_STORE_SHARED(ht->resize_initiated, 1);