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

diff --git a/rculfhash.c b/rculfhash.c
index e5db86c..9436605 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -201,7 +201,8 @@
  */
 #define REMOVED_FLAG		(1UL << 0)
 #define BUCKET_FLAG		(1UL << 1)
-#define FLAGS_MASK		((1UL << 2) - 1)
+#define REMOVAL_OWNER_FLAG	(1UL << 2)
+#define FLAGS_MASK		((1UL << 3) - 1)
 
 /* Value of the end pointer. Should not interact with flags. */
 #define END_VALUE		NULL
@@ -638,6 +639,18 @@ struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
 	return (struct cds_lfht_node *) (((unsigned long) node) | BUCKET_FLAG);
 }
 
+static
+int is_removal_owner(struct cds_lfht_node *node)
+{
+	return ((unsigned long) node) & REMOVAL_OWNER_FLAG;
+}
+
+static
+struct cds_lfht_node *flag_removal_owner(struct cds_lfht_node *node)
+{
+	return (struct cds_lfht_node *) (((unsigned long) node) | REMOVAL_OWNER_FLAG);
+}
+
 static
 struct cds_lfht_node *get_end(void)
 {
@@ -766,9 +779,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
@@ -778,6 +791,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		 * next pointer, they will either skip the old node due
 		 * to the removal flag and see the new node, or use
 		 * the old node, but will not see the new one.
+		 * This is a replacement of a node with another node
+		 * that has the same value: we are therefore not
+		 * removing a value from the hash table.
 		 */
 		ret_next = uatomic_cmpxchg(&old_node->next,
 			      old_next, flag_removed(new_node));
@@ -804,6 +820,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,
@@ -817,7 +834,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;
 
@@ -913,10 +930,9 @@ end:
 
 static
 int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
-		struct cds_lfht_node *node,
-		int bucket_removal)
+		struct cds_lfht_node *node)
 {
-	struct cds_lfht_node *bucket, *next, *old;
+	struct cds_lfht_node *bucket, *next;
 
 	if (!node)	/* Return -ENOENT if asked to delete NULL node */
 		return -ENOENT;
@@ -924,20 +940,25 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	/* logically delete the node */
 	assert(!is_bucket(node));
 	assert(!is_removed(node));
-	old = rcu_dereference(node->next);
-	do {
-		struct cds_lfht_node *new_next;
+	assert(!is_removal_owner(node));
 
-		next = old;
-		if (caa_unlikely(is_removed(next)))
-			return -ENOENT;
-		if (bucket_removal)
-			assert(is_bucket(next));
-		else
-			assert(!is_bucket(next));
-		new_next = flag_removed(next);
-		old = uatomic_cmpxchg(&node->next, next, new_next);
-	} while (old != next);
+	/*
+	 * We are first checking if the node had previously been
+	 * logically removed (this check is not atomic with setting the
+	 * logical removal flag). Return -ENOENT if the node had
+	 * previously been removed.
+	 */
+	next = rcu_dereference(node->next);
+	if (caa_unlikely(is_removed(next)))
+		return -ENOENT;
+	assert(!is_bucket(next));
+	/*
+	 * We set the REMOVED_FLAG unconditionally. Note that there may
+	 * be more than one concurrent thread setting this flag.
+	 * Knowing which wins the race will be known after the garbage
+	 * collection phase, stay tuned!
+	 */
+	uatomic_or(&node->next, REMOVED_FLAG);
 	/* We performed the (logical) deletion. */
 
 	/*
@@ -949,7 +970,23 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	_cds_lfht_gc_bucket(bucket, node);
 
 	assert(is_removed(rcu_dereference(node->next)));
-	return 0;
+	/*
+	 * Last phase: atomically exchange node->next with a version
+	 * having "REMOVAL_OWNER_FLAG" set. If the returned node->next
+	 * pointer did _not_ have "REMOVAL_OWNER_FLAG" set, we now own
+	 * the node and win the removal race.
+	 * It is interesting to note that all "add" paths are forbidden
+	 * to change the next pointer starting from the point where the
+	 * REMOVED_FLAG is set, so here using a read, followed by a
+	 * xchg() suffice to guarantee that the xchg() will ever only
+	 * set the "REMOVAL_OWNER_FLAG" (or change nothing if the flag
+	 * was already set).
+	 */
+	if (!is_removal_owner(uatomic_xchg(&node->next,
+			flag_removal_owner(node->next))))
+		return 0;
+	else
+		return -ENOENT;
 }
 
 static
@@ -1031,7 +1068,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();
 }
@@ -1435,9 +1472,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);
 }
 
@@ -1450,9 +1487,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;
@@ -1467,10 +1504,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;
@@ -1481,30 +1518,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, 0);
+	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)
 {
@@ -1564,11 +1617,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) {
@@ -1581,7 +1633,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);
@@ -1589,7 +1640,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))
@@ -1598,6 +1649,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) {