rculfhash: document linearizability guarantees

[urcu.git] / rculfhash.c

diff --git a/rculfhash.c b/rculfhash.c
index b114e0c1e3f5e9afe56e985da2f6122551cc1f4f..d22b44d25135b9a69a8faa7377ed8fb6fb72df16 100644 (file)
--- 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 <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>
@@ -1553,6 +1582,11 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)
        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)
 {
@@ -1775,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);