X-Git-Url: https://git.liburcu.org/?a=blobdiff_plain;f=rculfhash.c;h=6f470fd1cac2fea4ed24400543fb951242b63e88;hb=5c4ca589b1ecba14e6a34f900a88fe5fd5f29257;hp=958982bf40a420f4c8d15103591d3e8ce8c79524;hpb=709bacf9834b5007ec04aad9195ec060b9e27b67;p=urcu.git

diff --git a/rculfhash.c b/rculfhash.c
index 958982b..6f470fd 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
@@ -150,12 +150,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>
@@ -820,6 +822,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 +836,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 +1070,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();
 }
@@ -1473,7 +1476,7 @@ void cds_lfht_add(struct cds_lfht *ht, 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);
 }
 
@@ -1488,7 +1491,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 
 	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;
@@ -1506,7 +1509,7 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 	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;
@@ -1552,6 +1555,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)
 {
@@ -1774,6 +1782,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);