* (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
* 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
*/
#define _LGPL_SOURCE
+#define _GNU_SOURCE
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
+#include <sched.h>
#include "config.h"
#include <urcu.h>
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)
{
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);