X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=a791d5b29687b3daf90927ff263a0a6c3f7405f0;hb=b1588aebcd1494f5c36ad13bdaddb426f018ddbe;hp=80487a78de23ae7727d2a7f7b27b918a052e9647;hpb=170e11866c8a4bb6c3b2bf0a1e86e8b60a44059b;p=userspace-rcu.git

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index 80487a7..a791d5b 100644
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -26,13 +26,12 @@
 #include <errno.h>
 #include <limits.h>
 #include <string.h>
+#include <assert.h>
 #include <urcu/rcuja.h>
 #include <urcu/compiler.h>
 #include <urcu/arch.h>
-#include <assert.h>
 #include <urcu-pointer.h>
 #include <urcu/uatomic.h>
-#include <stdint.h>
 
 #include "rcuja-internal.h"
 
@@ -1821,11 +1820,11 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key,
 
 	switch (mode) {
 	case JA_LOOKUP_BE:
-		if (caa_unlikely(key > ja->key_max || key == 0))
+		if (caa_unlikely(key > ja->key_max))
 			return NULL;
 		break;
 	case JA_LOOKUP_AE:
-		if (caa_unlikely(key >= ja->key_max))
+		if (caa_unlikely(key > ja->key_max))
 			return NULL;
 		break;
 	default:
@@ -2147,25 +2146,41 @@ int ja_chain_node(struct cds_ja *ja,
 		struct cds_ja_inode_flag *parent_node_flag,
 		struct cds_ja_inode_flag **node_flag_ptr,
 		struct cds_ja_inode_flag *node_flag,
+		struct cds_ja_node *last_node,
 		struct cds_ja_node *node)
 {
 	struct cds_ja_shadow_node *shadow_node;
-	int ret = 0;
+	struct cds_ja_node *iter_node;
+	int ret = 0, found = 0;
 
 	shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag);
 	if (!shadow_node) {
 		return -EAGAIN;
 	}
-	if (ja_node_ptr(*node_flag_ptr) != ja_node_ptr(node_flag)) {
+	/*
+	 * Ensure that previous node is still there at end of list.
+	 */
+	iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag);
+	if ((struct cds_ja_node *) ja_node_ptr(*node_flag_ptr) != iter_node) {
+		ret = -EAGAIN;
+		goto end;
+	}
+	cds_ja_for_each_duplicate(iter_node) {
+		if (iter_node == last_node)
+			found = 1;
+	}
+	if (!found) {
 		ret = -EAGAIN;
 		goto end;
 	}
 	/*
-	 * Add node to head of list. Safe against concurrent RCU read
-	 * traversals.
+	 * Add node to tail of list to ensure that RCU traversals will
+	 * always see either the prior node or the newly added if
+	 * executed concurrently with a sequence of add followed by del
+	 * on the same key. Safe against concurrent RCU read traversals.
 	 */
-	node->next = (struct cds_ja_node *) node_flag;
-	rcu_assign_pointer(*node_flag_ptr, (struct cds_ja_inode_flag *) node);
+	node->next = NULL;
+	rcu_assign_pointer(last_node->next, node);
 end:
 	rcuja_shadow_unlock(shadow_node);
 	return ret;
@@ -2239,11 +2254,18 @@ retry:
 				node_flag,
 				key, i, node);
 	} else {
+		struct cds_ja_node *iter_node, *last_node = NULL;
+
 		if (unique_node_ret) {
 			*unique_node_ret = (struct cds_ja_node *) ja_node_ptr(node_flag);
 			return -EEXIST;
 		}
 
+		/* Find last duplicate */
+		iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag);
+		cds_ja_for_each_duplicate_rcu(iter_node)
+			last_node = iter_node;
+
 		dbg_printf("cds_ja_add duplicate parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n",
 				parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag);
 
@@ -2255,6 +2277,7 @@ retry:
 			parent_attach_node_flag,
 			attach_node_flag_ptr,
 			attach_node_flag,
+			last_node,
 			node);
 	}
 	if (ret == -EAGAIN || ret == -EEXIST)