From f5596c94199db7677d2d96fab386c260c2e3e518 Mon Sep 17 00:00:00 2001
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Date: Sat, 9 Jul 2011 15:28:38 -0400
Subject: [PATCH] rculfhash: merge dummy flag into next pointer

step 1: set flag

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 rculfhash.c | 57 +++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 44 insertions(+), 13 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index da04b9d..86b93b2 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -54,7 +54,8 @@
 #endif
 
 #define REMOVED_FLAG		(1UL << 0)
-#define FLAGS_MASK		((1UL << 1) - 1)
+#define DUMMY_FLAG		(1UL << 1)
+#define FLAGS_MASK		((1UL << 2) - 1)
 
 struct rcu_table {
 	unsigned long size;	/* always a power of 2 */
@@ -194,6 +195,18 @@ struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
 	return (struct rcu_ht_node *) (((unsigned long) node) | REMOVED_FLAG);
 }
 
+static
+int is_dummy(struct rcu_ht_node *node)
+{
+	return ((unsigned long) node) & DUMMY_FLAG;
+}
+
+static
+struct rcu_ht_node *flag_dummy(struct rcu_ht_node *node)
+{
+	return (struct rcu_ht_node *) (((unsigned long) node) | DUMMY_FLAG);
+}
+ 
 static
 unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
 {
@@ -214,7 +227,7 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
 static
 void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
 {
-	struct rcu_ht_node *iter_prev, *iter, *next;
+	struct rcu_ht_node *iter_prev, *iter, *next, *new_next;
 
 	for (;;) {
 		iter_prev = dummy;
@@ -233,19 +246,26 @@ void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
 			iter = next;
 		}
 		assert(!is_removed(iter));
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, clear_flag(next));
+		if (is_dummy(iter))
+			new_next = flag_dummy(clear_flag(next));
+		else
+			new_next = clear_flag(next);
+		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
 	}
 }
 
 static
 struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
-			    struct rcu_ht_node *node, int unique)
+			    struct rcu_ht_node *node, int unique, int dummy)
 {
-	struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
+	struct rcu_ht_node *iter_prev, *iter, *next, *new_node, *new_next,
+			*dummy_node;
 	unsigned long hash;
 
 	if (!t->size) {
 		assert(node->p.dummy);
+		assert(dummy);
+		node->p.next = flag_dummy(NULL);
 		return node;	/* Initial first add (head) */
 	}
 	hash = bit_reverse_ulong(node->p.reverse_hash);
@@ -284,21 +304,32 @@ struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
 		assert(node != clear_flag(iter));
 		assert(!is_removed(iter_prev));
 		assert(iter_prev != node);
-		node->p.next = iter;
+		if (!dummy)
+			node->p.next = iter;
+		else
+			node->p.next = flag_dummy(iter);
+		if (is_dummy(iter))
+			new_node = flag_dummy(node);
+		else
+			new_node = node;
 		if (uatomic_cmpxchg(&iter_prev->p.next, iter,
-				    node) != iter)
+				    new_node) != iter)
 			continue;	/* retry */
 		else
 			goto gc_end;
 	gc_node:
 		assert(!is_removed(iter));
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, clear_flag(next));
+		if (is_dummy(iter))
+			new_next = flag_dummy(clear_flag(next));
+		else
+			new_next = clear_flag(next);
+		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
 		/* retry */
 	}
 gc_end:
 	/* Garbage collect logically removed nodes in the bucket */
-	dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
-	_ht_gc_bucket(dummy, node);
+	dummy_node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
+	_ht_gc_bucket(dummy_node, node);
 	return node;
 }
 
@@ -357,7 +388,7 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t,
 		t->tbl[i] = calloc(1, sizeof(struct _rcu_ht_node));
 		t->tbl[i]->p.dummy = 1;
 		t->tbl[i]->p.reverse_hash = bit_reverse_ulong(i);
-		(void) _ht_add(ht, t, t->tbl[i], 0);
+		(void) _ht_add(ht, t, t->tbl[i], 0, 1);
 	}
 	t->resize_target = t->size = end;
 	t->resize_initiated = 0;
@@ -427,7 +458,7 @@ void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	t = rcu_dereference(ht->t);
-	(void) _ht_add(ht, t, node, 0);
+	(void) _ht_add(ht, t, node, 0, 0);
 }
 
 struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
@@ -439,7 +470,7 @@ struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	t = rcu_dereference(ht->t);
-	return _ht_add(ht, t, node, 1);
+	return _ht_add(ht, t, node, 1, 0);
 }
 
 int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
-- 
2.34.1