X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=d22b44d25135b9a69a8faa7377ed8fb6fb72df16;hp=94366050bfb00957988730edcae25923e3f39379;hb=0f5543cb1780acef35878646e6cdc966f1406c18;hpb=aee1715b914e5f4ba5003079d5d954ef2209f04e

diff --git a/rculfhash.c b/rculfhash.c
index 9436605..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 <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>
@@ -1780,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);