From e0ba718a906a70053d699a25c1d59b5bbdbf8715 Mon Sep 17 00:00:00 2001
From: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Date: Wed, 30 Sep 2009 10:05:36 -0400
Subject: [PATCH] Add stolen flag

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
---
 urcu-ht.c | 30 ++++++++++++++++++++++--------
 1 file changed, 22 insertions(+), 8 deletions(-)

diff --git a/urcu-ht.c b/urcu-ht.c
index e3fd313..500b8d3 100644
--- a/urcu-ht.c
+++ b/urcu-ht.c
@@ -5,16 +5,17 @@
 
 #define _LGPL_SOURCE
 #include <stdlib.h>
+#include <errno.h>
+#include <assert.h>
+#include <stdio.h>
+
 #include <urcu.h>
+#include <urcu-defer.h>
 #include <arch.h>
 #include <arch_atomic.h>
-#include <assert.h>
 #include <compiler.h>
-#include <urcu-defer.h>
-#include <errno.h>
-#include <urcu-ht.h>
 #include <urcu/jhash.h>
-#include <stdio.h>
+#include <urcu-ht.h>
 
 struct rcu_ht_node;
 
@@ -22,6 +23,7 @@ struct rcu_ht_node {
 	struct rcu_ht_node *next;
 	void *key;
 	void *data;
+	int stolen;
 };
 
 struct rcu_ht {
@@ -93,6 +95,7 @@ int ht_add(struct rcu_ht *ht, void *key, void *data)
 	new_head = calloc(1, sizeof(struct rcu_ht_node));
 	new_head->key = key;
 	new_head->data = data;
+	new_head->stolen = 0;
 	/* here comes the fun and tricky part.
 	 * Add at the beginning with a cmpxchg.
 	 * Hold a read lock between the moment the first element is read
@@ -134,8 +137,14 @@ restart:
 /*
  * Restart until we successfully remove the entry, or no entry is left
  * ((void *)(unsigned long)-ENOENT).
- * Deal with concurrent stealers by verifying that there are no element
- * in the list still pointing to the element stolen. (del_node)
+ * Deal with concurrent stealers by doing an extra verification pass to check
+ * that no element in the list are still pointing to the element stolen.
+ * This could happen if two concurrent steal for consecutive objects are
+ * executed. A pointer to an object being stolen could be saved by the
+ * concurrent stealer for the previous object.
+ * Also, given that in this precise scenario, another stealer can also want to
+ * delete the doubly-referenced object; use a "stolen" flag to let only one
+ * stealer delete the object.
  */
 void *ht_steal(struct rcu_ht *ht, void *key)
 {
@@ -155,7 +164,6 @@ retry:
 			if (del_node) {
 				goto end;
 			} else {
-				data = (void *)(unsigned long)-ENOENT;
 				goto error;
 			}
 		}
@@ -165,6 +173,11 @@ retry:
 		prev = &node->next;
 		node = rcu_dereference(*prev);
 	}
+
+	/* Another concurrent thread stole it ? If so, let it deal with this. */
+	if (cmpxchg(&node->stolen, 0, 1) != 0)
+		goto error;
+
 	/* Found it ! pointer to object is in "prev" */
 	if (rcu_cmpxchg_pointer(prev, node, node->next) == node)
 		del_node = node;
@@ -182,6 +195,7 @@ end:
 	return data;
 
 error:
+	data = (void *)(unsigned long)-ENOENT;
 	rcu_read_unlock();
 	return data;
 
-- 
2.34.1