[ltt-dev] [PATCH 0/7] rculfhash: More proper APIs and struct cds_lfht_node

[ltt-dev] [PATCH 0/7] rculfhash: More proper APIs and struct cds_lfht_node

[Lai Jiangshan]

This series patches change the lfht APIs and simplify struct cds_lfht_node.
struct cds_lfht_node only contains the field of the original fields
of struct _cds_lfht_node now.

It makes struct cds_lfht_node only contains basic fields.
All other things(key, key-value, hash-calculation,
allocation, deallocation) are become user's responsibility.

It make cds_lfht act as a sanity hash table,
not an incomplete hash_set nor hash_map.

The structure which embeds struct cds_lfht_node must takes the responsibility
to manage the key (or key-value pair) of the object and calculate
the hash value for cds_lfht APIs.

These patches are important preparation for merge it to kernel.
They are preparation for me to develop rculfhash testing which I just decided to
rework earlier)

Lai Jiangshan (7):
  wrap struct cds_lfht_node
  Move "struct rcu_head head" out of "struct cds_lfht_node"
  make cds_lfht_lookup() generic
  Compare API use node pointer instead of key
  Pass hash value to add APIs
  Move key out of struct lfht_test_node
  cleanup struct _cds_lfht_node

 rculfhash.c            |  178 +++++++++++++++++++++---------------------------
 tests/test_urcu_hash.c |  143 +++++++++++++++++++++++++++++++--------
 urcu/rculfhash.h       |   76 ++++++--------------
 3 files changed, 215 insertions(+), 182 deletions(-)

-- 
1.7.4.4

[ltt-dev] [PATCH 1/7] rculfhash, test: wrap struct cds_lfht_node

[Lai Jiangshan]

Use struct lfht_test_node for test instead of struct cds_lfht_node.
We can add test related things in struct lfht_test_node in future.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 tests/test_urcu_hash.c |   76 ++++++++++++++++++++++++++++++++----------------
 1 files changed, 51 insertions(+), 25 deletions(-)

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 25f872f..dbacf73 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -105,6 +105,29 @@ struct test_data {
 	int b;
 };
 
+struct lfht_test_node {
+	struct cds_lfht_node node;
+};
+
+static inline struct lfht_test_node *
+to_test_node(struct cds_lfht_node *node)
+{
+	return caa_container_of(node, struct lfht_test_node, node);
+}
+
+static inline
+void lfht_test_node_init(struct lfht_test_node *node, void *key,
+			size_t key_len)
+{
+	cds_lfht_node_init(&node->node, key, key_len);
+}
+
+static inline struct lfht_test_node *
+cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
+{
+	return to_test_node(cds_lfht_iter_get_node(iter));
+}
+
 static volatile int test_go, test_stop;
 
 static unsigned long wdelay;
@@ -437,7 +460,7 @@ void *thr_count(void *arg)
 void *thr_reader(void *_count)
 {
 	unsigned long long *count = _count;
-	struct cds_lfht_node *node;
+	struct lfht_test_node *node;
 	struct cds_lfht_iter iter;
 
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -457,7 +480,7 @@ void *thr_reader(void *_count)
 		cds_lfht_lookup(test_ht,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
 			sizeof(void *), &iter);
-		node = cds_lfht_iter_get_node(&iter);
+		node = cds_lfht_iter_get_test_node(&iter);
 		if (node == NULL) {
 			if (validate_lookup) {
 				printf("[ERROR] Lookup cannot find initial node.\n");
@@ -492,14 +515,15 @@ void *thr_reader(void *_count)
 static
 void free_node_cb(struct rcu_head *head)
 {
-	struct cds_lfht_node *node =
-		caa_container_of(head, struct cds_lfht_node, head);
+	struct lfht_test_node *node =
+		caa_container_of(head, struct lfht_test_node, node.head);
 	free(node);
 }
 
 void *thr_writer(void *_count)
 {
-	struct cds_lfht_node *node, *ret_node;
+	struct lfht_test_node *node;
+	struct cds_lfht_node *ret_node;
 	struct cds_lfht_iter iter;
 	struct wr_count *count = _count;
 	int ret;
@@ -519,26 +543,27 @@ void *thr_writer(void *_count)
 	for (;;) {
 		if ((addremove == AR_ADD || add_only)
 				|| (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
-			node = malloc(sizeof(struct cds_lfht_node));
-			cds_lfht_node_init(node,
+			node = malloc(sizeof(struct lfht_test_node));
+			lfht_test_node_init(node,
 				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, node);
+				ret_node = cds_lfht_add_unique(test_ht, &node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, node);
+					ret_node = cds_lfht_add_replace(test_ht, &node->node);
 				else
-					cds_lfht_add(test_ht, node);
+					cds_lfht_add(test_ht, &node->node);
 			}
 			rcu_read_unlock();
-			if (add_unique && ret_node != node) {
+			if (add_unique && ret_node != &node->node) {
 				free(node);
 				nr_addexist++;
 			} else {
 				if (add_replace && ret_node) {
-					call_rcu(&ret_node->head, free_node_cb);
+					call_rcu(&to_test_node(ret_node)->node.head,
+							free_node_cb);
 					nr_addexist++;
 				} else {
 					nr_add++;
@@ -553,8 +578,8 @@ void *thr_writer(void *_count)
 			ret = cds_lfht_del(test_ht, &iter);
 			rcu_read_unlock();
 			if (ret == 0) {
-				node = cds_lfht_iter_get_node(&iter);
-				call_rcu(&node->head, free_node_cb);
+				node = cds_lfht_iter_get_test_node(&iter);
+				call_rcu(&node->node.head, free_node_cb);
 				nr_del++;
 			} else
 				nr_delnoent++;
@@ -596,7 +621,8 @@ void *thr_writer(void *_count)
 
 static int populate_hash(void)
 {
-	struct cds_lfht_node *node, *ret_node;
+	struct lfht_test_node *node;
+	struct cds_lfht_node *ret_node;
 
 	if (!init_populate)
 		return 0;
@@ -608,26 +634,26 @@ static int populate_hash(void)
 	}
 
 	while (nr_add < init_populate) {
-		node = malloc(sizeof(struct cds_lfht_node));
-		cds_lfht_node_init(node,
+		node = malloc(sizeof(struct lfht_test_node));
+		lfht_test_node_init(node,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % init_pool_size) + init_pool_offset),
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, node);
+			ret_node = cds_lfht_add_unique(test_ht, &node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, node);
+				ret_node = cds_lfht_add_replace(test_ht, &node->node);
 			else
-				cds_lfht_add(test_ht, node);
+				cds_lfht_add(test_ht, &node->node);
 		}
 		rcu_read_unlock();
-		if (add_unique && ret_node != node) {
+		if (add_unique && ret_node != &node->node) {
 			free(node);
 			nr_addexist++;
 		} else {
 			if (add_replace && ret_node) {
-				call_rcu(&ret_node->head, free_node_cb);
+				call_rcu(&to_test_node(ret_node)->node.head, free_node_cb);
 				nr_addexist++;
 			} else {
 				nr_add++;
@@ -642,16 +668,16 @@ static
 void test_delete_all_nodes(struct cds_lfht *ht)
 {
 	struct cds_lfht_iter iter;
-	struct cds_lfht_node *node;
+	struct lfht_test_node *node;
 	unsigned long count = 0;
 
 	cds_lfht_first(ht, &iter);
-	while ((node = cds_lfht_iter_get_node(&iter)) != NULL) {
+	while ((node = cds_lfht_iter_get_test_node(&iter)) != NULL) {
 		int ret;
 
 		ret = cds_lfht_del(test_ht, &iter);
 		assert(!ret);
-		call_rcu(&node->head, free_node_cb);
+		call_rcu(&node->node.head, free_node_cb);
 		cds_lfht_next(ht, &iter);
 		count++;
 	}
-- 
1.7.4.4

[ltt-dev] [PATCH 1/7] rculfhash, test: wrap struct cds_lfht_node

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Use struct lfht_test_node for test instead of struct cds_lfht_node.
> We can add test related things in struct lfht_test_node in future.

merged, thanks !

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   76 ++++++++++++++++++++++++++++++++----------------
>  1 files changed, 51 insertions(+), 25 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 25f872f..dbacf73 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -105,6 +105,29 @@ struct test_data {
>  	int b;
>  };
>  
> +struct lfht_test_node {
> +	struct cds_lfht_node node;
> +};
> +
> +static inline struct lfht_test_node *
> +to_test_node(struct cds_lfht_node *node)
> +{
> +	return caa_container_of(node, struct lfht_test_node, node);
> +}
> +
> +static inline
> +void lfht_test_node_init(struct lfht_test_node *node, void *key,
> +			size_t key_len)
> +{
> +	cds_lfht_node_init(&node->node, key, key_len);
> +}
> +
> +static inline struct lfht_test_node *
> +cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
> +{
> +	return to_test_node(cds_lfht_iter_get_node(iter));
> +}
> +
>  static volatile int test_go, test_stop;
>  
>  static unsigned long wdelay;
> @@ -437,7 +460,7 @@ void *thr_count(void *arg)
>  void *thr_reader(void *_count)
>  {
>  	unsigned long long *count = _count;
> -	struct cds_lfht_node *node;
> +	struct lfht_test_node *node;
>  	struct cds_lfht_iter iter;
>  
>  	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
> @@ -457,7 +480,7 @@ void *thr_reader(void *_count)
>  		cds_lfht_lookup(test_ht,
>  			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
>  			sizeof(void *), &iter);
> -		node = cds_lfht_iter_get_node(&iter);
> +		node = cds_lfht_iter_get_test_node(&iter);
>  		if (node == NULL) {
>  			if (validate_lookup) {
>  				printf("[ERROR] Lookup cannot find initial node.\n");
> @@ -492,14 +515,15 @@ void *thr_reader(void *_count)
>  static
>  void free_node_cb(struct rcu_head *head)
>  {
> -	struct cds_lfht_node *node =
> -		caa_container_of(head, struct cds_lfht_node, head);
> +	struct lfht_test_node *node =
> +		caa_container_of(head, struct lfht_test_node, node.head);
>  	free(node);
>  }
>  
>  void *thr_writer(void *_count)
>  {
> -	struct cds_lfht_node *node, *ret_node;
> +	struct lfht_test_node *node;
> +	struct cds_lfht_node *ret_node;
>  	struct cds_lfht_iter iter;
>  	struct wr_count *count = _count;
>  	int ret;
> @@ -519,26 +543,27 @@ void *thr_writer(void *_count)
>  	for (;;) {
>  		if ((addremove == AR_ADD || add_only)
>  				|| (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
> -			node = malloc(sizeof(struct cds_lfht_node));
> -			cds_lfht_node_init(node,
> +			node = malloc(sizeof(struct lfht_test_node));
> +			lfht_test_node_init(node,
>  				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
>  				sizeof(void *));
>  			rcu_read_lock();
>  			if (add_unique) {
> -				ret_node = cds_lfht_add_unique(test_ht, node);
> +				ret_node = cds_lfht_add_unique(test_ht, &node->node);
>  			} else {
>  				if (add_replace)
> -					ret_node = cds_lfht_add_replace(test_ht, node);
> +					ret_node = cds_lfht_add_replace(test_ht, &node->node);
>  				else
> -					cds_lfht_add(test_ht, node);
> +					cds_lfht_add(test_ht, &node->node);
>  			}
>  			rcu_read_unlock();
> -			if (add_unique && ret_node != node) {
> +			if (add_unique && ret_node != &node->node) {
>  				free(node);
>  				nr_addexist++;
>  			} else {
>  				if (add_replace && ret_node) {
> -					call_rcu(&ret_node->head, free_node_cb);
> +					call_rcu(&to_test_node(ret_node)->node.head,
> +							free_node_cb);
>  					nr_addexist++;
>  				} else {
>  					nr_add++;
> @@ -553,8 +578,8 @@ void *thr_writer(void *_count)
>  			ret = cds_lfht_del(test_ht, &iter);
>  			rcu_read_unlock();
>  			if (ret == 0) {
> -				node = cds_lfht_iter_get_node(&iter);
> -				call_rcu(&node->head, free_node_cb);
> +				node = cds_lfht_iter_get_test_node(&iter);
> +				call_rcu(&node->node.head, free_node_cb);
>  				nr_del++;
>  			} else
>  				nr_delnoent++;
> @@ -596,7 +621,8 @@ void *thr_writer(void *_count)
>  
>  static int populate_hash(void)
>  {
> -	struct cds_lfht_node *node, *ret_node;
> +	struct lfht_test_node *node;
> +	struct cds_lfht_node *ret_node;
>  
>  	if (!init_populate)
>  		return 0;
> @@ -608,26 +634,26 @@ static int populate_hash(void)
>  	}
>  
>  	while (nr_add < init_populate) {
> -		node = malloc(sizeof(struct cds_lfht_node));
> -		cds_lfht_node_init(node,
> +		node = malloc(sizeof(struct lfht_test_node));
> +		lfht_test_node_init(node,
>  			(void *)(((unsigned long) rand_r(&rand_lookup) % init_pool_size) + init_pool_offset),
>  			sizeof(void *));
>  		rcu_read_lock();
>  		if (add_unique) {
> -			ret_node = cds_lfht_add_unique(test_ht, node);
> +			ret_node = cds_lfht_add_unique(test_ht, &node->node);
>  		} else {
>  			if (add_replace)
> -				ret_node = cds_lfht_add_replace(test_ht, node);
> +				ret_node = cds_lfht_add_replace(test_ht, &node->node);
>  			else
> -				cds_lfht_add(test_ht, node);
> +				cds_lfht_add(test_ht, &node->node);
>  		}
>  		rcu_read_unlock();
> -		if (add_unique && ret_node != node) {
> +		if (add_unique && ret_node != &node->node) {
>  			free(node);
>  			nr_addexist++;
>  		} else {
>  			if (add_replace && ret_node) {
> -				call_rcu(&ret_node->head, free_node_cb);
> +				call_rcu(&to_test_node(ret_node)->node.head, free_node_cb);
>  				nr_addexist++;
>  			} else {
>  				nr_add++;
> @@ -642,16 +668,16 @@ static
>  void test_delete_all_nodes(struct cds_lfht *ht)
>  {
>  	struct cds_lfht_iter iter;
> -	struct cds_lfht_node *node;
> +	struct lfht_test_node *node;
>  	unsigned long count = 0;
>  
>  	cds_lfht_first(ht, &iter);
> -	while ((node = cds_lfht_iter_get_node(&iter)) != NULL) {
> +	while ((node = cds_lfht_iter_get_test_node(&iter)) != NULL) {
>  		int ret;
>  
>  		ret = cds_lfht_del(test_ht, &iter);
>  		assert(!ret);
> -		call_rcu(&node->head, free_node_cb);
> +		call_rcu(&node->node.head, free_node_cb);
>  		cds_lfht_next(ht, &iter);
>  		count++;
>  	}
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 2/7] rculfhash: Move "struct rcu_head head" out of "struct cds_lfht_node"

[Lai Jiangshan]

It is user's responsibility to free it by call_rcu(),
synchronize_rcu() or defer_rcu().

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 tests/test_urcu_hash.c |   12 +++++++-----
 urcu/rculfhash.h       |    2 --
 2 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index dbacf73..e28c14a 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -107,6 +107,8 @@ struct test_data {
 
 struct lfht_test_node {
 	struct cds_lfht_node node;
+	/* cache-cold for iteration */
+	struct rcu_head head;
 };
 
 static inline struct lfht_test_node *
@@ -516,7 +518,7 @@ static
 void free_node_cb(struct rcu_head *head)
 {
 	struct lfht_test_node *node =
-		caa_container_of(head, struct lfht_test_node, node.head);
+		caa_container_of(head, struct lfht_test_node, head);
 	free(node);
 }
 
@@ -562,7 +564,7 @@ void *thr_writer(void *_count)
 				nr_addexist++;
 			} else {
 				if (add_replace && ret_node) {
-					call_rcu(&to_test_node(ret_node)->node.head,
+					call_rcu(&to_test_node(ret_node)->head,
 							free_node_cb);
 					nr_addexist++;
 				} else {
@@ -579,7 +581,7 @@ void *thr_writer(void *_count)
 			rcu_read_unlock();
 			if (ret == 0) {
 				node = cds_lfht_iter_get_test_node(&iter);
-				call_rcu(&node->node.head, free_node_cb);
+				call_rcu(&node->head, free_node_cb);
 				nr_del++;
 			} else
 				nr_delnoent++;
@@ -653,7 +655,7 @@ static int populate_hash(void)
 			nr_addexist++;
 		} else {
 			if (add_replace && ret_node) {
-				call_rcu(&to_test_node(ret_node)->node.head, free_node_cb);
+				call_rcu(&to_test_node(ret_node)->head, free_node_cb);
 				nr_addexist++;
 			} else {
 				nr_add++;
@@ -677,7 +679,7 @@ void test_delete_all_nodes(struct cds_lfht *ht)
 
 		ret = cds_lfht_del(test_ht, &iter);
 		assert(!ret);
-		call_rcu(&node->node.head, free_node_cb);
+		call_rcu(&node->head, free_node_cb);
 		cds_lfht_next(ht, &iter);
 		count++;
 	}
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 008b1d4..f4f3373 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -62,8 +62,6 @@ struct cds_lfht_node {
 	struct _cds_lfht_node p;          /* needs to be first field */
 	void *key;
 	unsigned int key_len;
-	/* cache-cold for iteration */
-	struct rcu_head head;
 };
 
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
-- 
1.7.4.4

[ltt-dev] [PATCH 2/7] rculfhash: Move "struct rcu_head head" out of "struct cds_lfht_node"

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> It is user's responsibility to free it by call_rcu(),
> synchronize_rcu() or defer_rcu().

merged, thanks!

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   12 +++++++-----
>  urcu/rculfhash.h       |    2 --
>  2 files changed, 7 insertions(+), 7 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index dbacf73..e28c14a 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -107,6 +107,8 @@ struct test_data {
>  
>  struct lfht_test_node {
>  	struct cds_lfht_node node;
> +	/* cache-cold for iteration */
> +	struct rcu_head head;
>  };
>  
>  static inline struct lfht_test_node *
> @@ -516,7 +518,7 @@ static
>  void free_node_cb(struct rcu_head *head)
>  {
>  	struct lfht_test_node *node =
> -		caa_container_of(head, struct lfht_test_node, node.head);
> +		caa_container_of(head, struct lfht_test_node, head);
>  	free(node);
>  }
>  
> @@ -562,7 +564,7 @@ void *thr_writer(void *_count)
>  				nr_addexist++;
>  			} else {
>  				if (add_replace && ret_node) {
> -					call_rcu(&to_test_node(ret_node)->node.head,
> +					call_rcu(&to_test_node(ret_node)->head,
>  							free_node_cb);
>  					nr_addexist++;
>  				} else {
> @@ -579,7 +581,7 @@ void *thr_writer(void *_count)
>  			rcu_read_unlock();
>  			if (ret == 0) {
>  				node = cds_lfht_iter_get_test_node(&iter);
> -				call_rcu(&node->node.head, free_node_cb);
> +				call_rcu(&node->head, free_node_cb);
>  				nr_del++;
>  			} else
>  				nr_delnoent++;
> @@ -653,7 +655,7 @@ static int populate_hash(void)
>  			nr_addexist++;
>  		} else {
>  			if (add_replace && ret_node) {
> -				call_rcu(&to_test_node(ret_node)->node.head, free_node_cb);
> +				call_rcu(&to_test_node(ret_node)->head, free_node_cb);
>  				nr_addexist++;
>  			} else {
>  				nr_add++;
> @@ -677,7 +679,7 @@ void test_delete_all_nodes(struct cds_lfht *ht)
>  
>  		ret = cds_lfht_del(test_ht, &iter);
>  		assert(!ret);
> -		call_rcu(&node->node.head, free_node_cb);
> +		call_rcu(&node->head, free_node_cb);
>  		cds_lfht_next(ht, &iter);
>  		count++;
>  	}
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index 008b1d4..f4f3373 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -62,8 +62,6 @@ struct cds_lfht_node {
>  	struct _cds_lfht_node p;          /* needs to be first field */
>  	void *key;
>  	unsigned int key_len;
> -	/* cache-cold for iteration */
> -	struct rcu_head head;
>  };
>  
>  /* cds_lfht_iter: Used to track state while traversing a hash chain. */
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Lai Jiangshan]

We use hash value to determine the range of the object
and use cds_lfht_lookup_fct to lookup them.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |    8 ++++----
 tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
 urcu/rculfhash.h       |    4 +++-
 3 files changed, 29 insertions(+), 8 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index d1a1766..29054cd 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 	return ht;
 }
 
-void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
+void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+		cds_lfht_lookup_fct match, void *arg,
 		struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next, *dummy_node;
 	struct _cds_lfht_node *lookup;
-	unsigned long hash, reverse_hash, size;
+	unsigned long reverse_hash, size;
 
-	hash = ht->hash_fct(key, key_len, ht->hash_seed);
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
@@ -1421,7 +1421,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
 		    && node->p.reverse_hash == reverse_hash
-		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
+		    && caa_likely(match(node, arg))) {
 				break;
 		}
 		node = clear_flag(next);
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index e28c14a..4c45573 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -41,6 +41,8 @@
 #define DEFAULT_MIN_ALLOC_SIZE	1
 #define DEFAULT_RAND_POOL	1000000
 
+#define TEST_HASH_SEED	0x42UL
+
 /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
 #define CACHE_LINE_SIZE 4096
 
@@ -419,6 +421,23 @@ unsigned long test_compare(void *key1, size_t key1_len,
 		return 1;
 }
 
+static
+int test_match(struct cds_lfht_node *node, void *arg)
+{
+	return !test_compare(node->key, node->key_len,
+			arg, sizeof(unsigned long));
+}
+
+static
+void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
+		struct cds_lfht_iter *iter)
+{
+	assert(key_len == sizeof(unsigned long));
+
+	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
+			test_match, key, iter);
+}
+
 void *thr_count(void *arg)
 {
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -479,7 +498,7 @@ void *thr_reader(void *_count)
 
 	for (;;) {
 		rcu_read_lock();
-		cds_lfht_lookup(test_ht,
+		cds_lfht_test_lookup(test_ht,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
 			sizeof(void *), &iter);
 		node = cds_lfht_iter_get_test_node(&iter);
@@ -574,7 +593,7 @@ void *thr_writer(void *_count)
 		} else {
 			/* May delete */
 			rcu_read_lock();
-			cds_lfht_lookup(test_ht,
+			cds_lfht_test_lookup(test_ht,
 				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
 				sizeof(void *), &iter);
 			ret = cds_lfht_del(test_ht, &iter);
@@ -932,7 +951,7 @@ int main(int argc, char **argv)
 	 * thread from the point of view of resize.
 	 */
 	rcu_register_thread();
-	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
+	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
 			init_hash_size, min_hash_alloc_size,
 			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
 			CDS_LFHT_ACCOUNTING, NULL);
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index f4f3373..b56fe56 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -86,6 +86,7 @@ typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
 					unsigned long seed);
 typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
 					void *key2, size_t key2_len);
+typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
 
 /*
  * cds_lfht_node_init - initialize a hash table node
@@ -203,7 +204,8 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
-void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
+void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+		cds_lfht_lookup_fct match, void *arg,
 		struct cds_lfht_iter *iter);
 
 /*
-- 
1.7.4.4

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> We use hash value to determine the range of the object
> and use cds_lfht_lookup_fct to lookup them.
> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |    8 ++++----
>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
>  urcu/rculfhash.h       |    4 +++-
>  3 files changed, 29 insertions(+), 8 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index d1a1766..29054cd 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>  	return ht;
>  }
>  
> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> +		cds_lfht_lookup_fct match, void *arg,

arg -> key ?

for "match", our approach is to provide this function as parameter to
cds_lfht_new rather than pass it as parameter each time a lookup is
performed. What is the reason why we should pass it here as a parameter?

Thanks,

Mathieu

>  		struct cds_lfht_iter *iter)
>  {
>  	struct cds_lfht_node *node, *next, *dummy_node;
>  	struct _cds_lfht_node *lookup;
> -	unsigned long hash, reverse_hash, size;
> +	unsigned long reverse_hash, size;
>  
> -	hash = ht->hash_fct(key, key_len, ht->hash_seed);
>  	reverse_hash = bit_reverse_ulong(hash);
>  
>  	size = rcu_dereference(ht->t.size);
> @@ -1421,7 +1421,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>  		if (caa_likely(!is_removed(next))
>  		    && !is_dummy(next)
>  		    && node->p.reverse_hash == reverse_hash
> -		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
> +		    && caa_likely(match(node, arg))) {
>  				break;
>  		}
>  		node = clear_flag(next);
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index e28c14a..4c45573 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -41,6 +41,8 @@
>  #define DEFAULT_MIN_ALLOC_SIZE	1
>  #define DEFAULT_RAND_POOL	1000000
>  
> +#define TEST_HASH_SEED	0x42UL
> +
>  /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
>  #define CACHE_LINE_SIZE 4096
>  
> @@ -419,6 +421,23 @@ unsigned long test_compare(void *key1, size_t key1_len,
>  		return 1;
>  }
>  
> +static
> +int test_match(struct cds_lfht_node *node, void *arg)
> +{
> +	return !test_compare(node->key, node->key_len,
> +			arg, sizeof(unsigned long));
> +}
> +
> +static
> +void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> +		struct cds_lfht_iter *iter)
> +{
> +	assert(key_len == sizeof(unsigned long));
> +
> +	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
> +			test_match, key, iter);
> +}
> +
>  void *thr_count(void *arg)
>  {
>  	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
> @@ -479,7 +498,7 @@ void *thr_reader(void *_count)
>  
>  	for (;;) {
>  		rcu_read_lock();
> -		cds_lfht_lookup(test_ht,
> +		cds_lfht_test_lookup(test_ht,
>  			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
>  			sizeof(void *), &iter);
>  		node = cds_lfht_iter_get_test_node(&iter);
> @@ -574,7 +593,7 @@ void *thr_writer(void *_count)
>  		} else {
>  			/* May delete */
>  			rcu_read_lock();
> -			cds_lfht_lookup(test_ht,
> +			cds_lfht_test_lookup(test_ht,
>  				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
>  				sizeof(void *), &iter);
>  			ret = cds_lfht_del(test_ht, &iter);
> @@ -932,7 +951,7 @@ int main(int argc, char **argv)
>  	 * thread from the point of view of resize.
>  	 */
>  	rcu_register_thread();
> -	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
> +	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
>  			init_hash_size, min_hash_alloc_size,
>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>  			CDS_LFHT_ACCOUNTING, NULL);
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index f4f3373..b56fe56 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -86,6 +86,7 @@ typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
>  					unsigned long seed);
>  typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
>  					void *key2, size_t key2_len);
> +typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
>  
>  /*
>   * cds_lfht_node_init - initialize a hash table node
> @@ -203,7 +204,8 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
>   * Call with rcu_read_lock held.
>   * Threads calling this API need to be registered RCU read-side threads.
>   */
> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> +		cds_lfht_lookup_fct match, void *arg,
>  		struct cds_lfht_iter *iter);
>  
>  /*
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Lai Jiangshan]

On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> We use hash value to determine the range of the object
>> and use cds_lfht_lookup_fct to lookup them.
>>
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c            |    8 ++++----
>>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
>>  urcu/rculfhash.h       |    4 +++-
>>  3 files changed, 29 insertions(+), 8 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index d1a1766..29054cd 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>>  	return ht;
>>  }
>>  
>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>> +		cds_lfht_lookup_fct match, void *arg,
> 
> arg -> key ?
> 
> for "match", our approach is to provide this function as parameter to
> cds_lfht_new rather than pass it as parameter each time a lookup is
> performed. What is the reason why we should pass it here as a parameter?
> 

Allow the user define it.
In the test, I pass match = a function always returns true when need,
thus cds_lfht_lookup() returns the first node of same-hash-value-chain.

thanks,
lai


> 
>>  		struct cds_lfht_iter *iter)
>>  {
>>  	struct cds_lfht_node *node, *next, *dummy_node;
>>  	struct _cds_lfht_node *lookup;
>> -	unsigned long hash, reverse_hash, size;
>> +	unsigned long reverse_hash, size;
>>  
>> -	hash = ht->hash_fct(key, key_len, ht->hash_seed);
>>  	reverse_hash = bit_reverse_ulong(hash);
>>  
>>  	size = rcu_dereference(ht->t.size);
>> @@ -1421,7 +1421,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>>  		if (caa_likely(!is_removed(next))
>>  		    && !is_dummy(next)
>>  		    && node->p.reverse_hash == reverse_hash
>> -		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
>> +		    && caa_likely(match(node, arg))) {
>>  				break;
>>  		}
>>  		node = clear_flag(next);
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index e28c14a..4c45573 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -41,6 +41,8 @@
>>  #define DEFAULT_MIN_ALLOC_SIZE	1
>>  #define DEFAULT_RAND_POOL	1000000
>>  
>> +#define TEST_HASH_SEED	0x42UL
>> +
>>  /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
>>  #define CACHE_LINE_SIZE 4096
>>  
>> @@ -419,6 +421,23 @@ unsigned long test_compare(void *key1, size_t key1_len,
>>  		return 1;
>>  }
>>  
>> +static
>> +int test_match(struct cds_lfht_node *node, void *arg)
>> +{
>> +	return !test_compare(node->key, node->key_len,
>> +			arg, sizeof(unsigned long));
>> +}
>> +
>> +static
>> +void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>> +		struct cds_lfht_iter *iter)
>> +{
>> +	assert(key_len == sizeof(unsigned long));
>> +
>> +	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
>> +			test_match, key, iter);
>> +}
>> +
>>  void *thr_count(void *arg)
>>  {
>>  	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
>> @@ -479,7 +498,7 @@ void *thr_reader(void *_count)
>>  
>>  	for (;;) {
>>  		rcu_read_lock();
>> -		cds_lfht_lookup(test_ht,
>> +		cds_lfht_test_lookup(test_ht,
>>  			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
>>  			sizeof(void *), &iter);
>>  		node = cds_lfht_iter_get_test_node(&iter);
>> @@ -574,7 +593,7 @@ void *thr_writer(void *_count)
>>  		} else {
>>  			/* May delete */
>>  			rcu_read_lock();
>> -			cds_lfht_lookup(test_ht,
>> +			cds_lfht_test_lookup(test_ht,
>>  				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
>>  				sizeof(void *), &iter);
>>  			ret = cds_lfht_del(test_ht, &iter);
>> @@ -932,7 +951,7 @@ int main(int argc, char **argv)
>>  	 * thread from the point of view of resize.
>>  	 */
>>  	rcu_register_thread();
>> -	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
>> +	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
>>  			init_hash_size, min_hash_alloc_size,
>>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>>  			CDS_LFHT_ACCOUNTING, NULL);
>> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
>> index f4f3373..b56fe56 100644
>> --- a/urcu/rculfhash.h
>> +++ b/urcu/rculfhash.h
>> @@ -86,6 +86,7 @@ typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
>>  					unsigned long seed);
>>  typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
>>  					void *key2, size_t key2_len);
>> +typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
>>  
>>  /*
>>   * cds_lfht_node_init - initialize a hash table node
>> @@ -203,7 +204,8 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
>>   * Call with rcu_read_lock held.
>>   * Threads calling this API need to be registered RCU read-side threads.
>>   */
>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>> +		cds_lfht_lookup_fct match, void *arg,
>>  		struct cds_lfht_iter *iter);
>>  
>>  /*
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> We use hash value to determine the range of the object
> >> and use cds_lfht_lookup_fct to lookup them.
> >>
> >> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> ---
> >>  rculfhash.c            |    8 ++++----
> >>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
> >>  urcu/rculfhash.h       |    4 +++-
> >>  3 files changed, 29 insertions(+), 8 deletions(-)
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index d1a1766..29054cd 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
> >>  	return ht;
> >>  }
> >>  
> >> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >> +		cds_lfht_lookup_fct match, void *arg,
> > 
> > arg -> key ?
> > 
> > for "match", our approach is to provide this function as parameter to
> > cds_lfht_new rather than pass it as parameter each time a lookup is
> > performed. What is the reason why we should pass it here as a parameter?
> > 
> 
> Allow the user define it.
> In the test, I pass match = a function always returns true when need,
> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.

This looks like an interesting debug and testing feature, but I don't
really see why we should complicate the API to include this. Is there a
real-life use-case you have in mind besides testing ?

If we only need this for testing, we can use a static variable in the
test program to influence the behavior of cds_lfht_test_lookup.

The other patches look fine, I'm just concerned about this one because
it adds complexity to the API which does not seem useful to end-users.

Thanks!

Mathieu

> 
> thanks,
> lai
> 
> 
> > 
> >>  		struct cds_lfht_iter *iter)
> >>  {
> >>  	struct cds_lfht_node *node, *next, *dummy_node;
> >>  	struct _cds_lfht_node *lookup;
> >> -	unsigned long hash, reverse_hash, size;
> >> +	unsigned long reverse_hash, size;
> >>  
> >> -	hash = ht->hash_fct(key, key_len, ht->hash_seed);
> >>  	reverse_hash = bit_reverse_ulong(hash);
> >>  
> >>  	size = rcu_dereference(ht->t.size);
> >> @@ -1421,7 +1421,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >>  		if (caa_likely(!is_removed(next))
> >>  		    && !is_dummy(next)
> >>  		    && node->p.reverse_hash == reverse_hash
> >> -		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
> >> +		    && caa_likely(match(node, arg))) {
> >>  				break;
> >>  		}
> >>  		node = clear_flag(next);
> >> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> >> index e28c14a..4c45573 100644
> >> --- a/tests/test_urcu_hash.c
> >> +++ b/tests/test_urcu_hash.c
> >> @@ -41,6 +41,8 @@
> >>  #define DEFAULT_MIN_ALLOC_SIZE	1
> >>  #define DEFAULT_RAND_POOL	1000000
> >>  
> >> +#define TEST_HASH_SEED	0x42UL
> >> +
> >>  /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
> >>  #define CACHE_LINE_SIZE 4096
> >>  
> >> @@ -419,6 +421,23 @@ unsigned long test_compare(void *key1, size_t key1_len,
> >>  		return 1;
> >>  }
> >>  
> >> +static
> >> +int test_match(struct cds_lfht_node *node, void *arg)
> >> +{
> >> +	return !test_compare(node->key, node->key_len,
> >> +			arg, sizeof(unsigned long));
> >> +}
> >> +
> >> +static
> >> +void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >> +		struct cds_lfht_iter *iter)
> >> +{
> >> +	assert(key_len == sizeof(unsigned long));
> >> +
> >> +	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
> >> +			test_match, key, iter);
> >> +}
> >> +
> >>  void *thr_count(void *arg)
> >>  {
> >>  	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
> >> @@ -479,7 +498,7 @@ void *thr_reader(void *_count)
> >>  
> >>  	for (;;) {
> >>  		rcu_read_lock();
> >> -		cds_lfht_lookup(test_ht,
> >> +		cds_lfht_test_lookup(test_ht,
> >>  			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
> >>  			sizeof(void *), &iter);
> >>  		node = cds_lfht_iter_get_test_node(&iter);
> >> @@ -574,7 +593,7 @@ void *thr_writer(void *_count)
> >>  		} else {
> >>  			/* May delete */
> >>  			rcu_read_lock();
> >> -			cds_lfht_lookup(test_ht,
> >> +			cds_lfht_test_lookup(test_ht,
> >>  				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
> >>  				sizeof(void *), &iter);
> >>  			ret = cds_lfht_del(test_ht, &iter);
> >> @@ -932,7 +951,7 @@ int main(int argc, char **argv)
> >>  	 * thread from the point of view of resize.
> >>  	 */
> >>  	rcu_register_thread();
> >> -	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
> >> +	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
> >>  			init_hash_size, min_hash_alloc_size,
> >>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
> >>  			CDS_LFHT_ACCOUNTING, NULL);
> >> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> >> index f4f3373..b56fe56 100644
> >> --- a/urcu/rculfhash.h
> >> +++ b/urcu/rculfhash.h
> >> @@ -86,6 +86,7 @@ typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
> >>  					unsigned long seed);
> >>  typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
> >>  					void *key2, size_t key2_len);
> >> +typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
> >>  
> >>  /*
> >>   * cds_lfht_node_init - initialize a hash table node
> >> @@ -203,7 +204,8 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
> >>   * Call with rcu_read_lock held.
> >>   * Threads calling this API need to be registered RCU read-side threads.
> >>   */
> >> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >> +		cds_lfht_lookup_fct match, void *arg,
> >>  		struct cds_lfht_iter *iter);
> >>  
> >>  /*
> >> -- 
> >> 1.7.4.4
> >>
> > 
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Lai Jiangshan]

On 11/04/2011 06:08 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
>>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>>>> We use hash value to determine the range of the object
>>>> and use cds_lfht_lookup_fct to lookup them.
>>>>
>>>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>>>> ---
>>>>  rculfhash.c            |    8 ++++----
>>>>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
>>>>  urcu/rculfhash.h       |    4 +++-
>>>>  3 files changed, 29 insertions(+), 8 deletions(-)
>>>>
>>>> diff --git a/rculfhash.c b/rculfhash.c
>>>> index d1a1766..29054cd 100644
>>>> --- a/rculfhash.c
>>>> +++ b/rculfhash.c
>>>> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>>>>  	return ht;
>>>>  }
>>>>  
>>>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>>>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>>>> +		cds_lfht_lookup_fct match, void *arg,
>>>
>>> arg -> key ?
>>>
>>> for "match", our approach is to provide this function as parameter to
>>> cds_lfht_new rather than pass it as parameter each time a lookup is
>>> performed. What is the reason why we should pass it here as a parameter?
>>>
>>
>> Allow the user define it.
>> In the test, I pass match = a function always returns true when need,
>> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.
> 
> This looks like an interesting debug and testing feature, but I don't
> really see why we should complicate the API to include this. Is there a
> real-life use-case you have in mind besides testing ?
> 
> If we only need this for testing, we can use a static variable in the
> test program to influence the behavior of cds_lfht_test_lookup.
> 
> The other patches look fine, I'm just concerned about this one because
> it adds complexity to the API which does not seem useful to end-users.
> 

I think a generic API is OK.

Sometimes the caller don't have the key or the keys which are big
are saved separated. Example: file server
Or key comparation is too slow.
Or caller just need approximate lookup.
Or caller want to compare keys with different strategies for performance.

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/04/2011 06:08 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
> >>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >>>> We use hash value to determine the range of the object
> >>>> and use cds_lfht_lookup_fct to lookup them.
> >>>>
> >>>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >>>> ---
> >>>>  rculfhash.c            |    8 ++++----
> >>>>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
> >>>>  urcu/rculfhash.h       |    4 +++-
> >>>>  3 files changed, 29 insertions(+), 8 deletions(-)
> >>>>
> >>>> diff --git a/rculfhash.c b/rculfhash.c
> >>>> index d1a1766..29054cd 100644
> >>>> --- a/rculfhash.c
> >>>> +++ b/rculfhash.c
> >>>> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
> >>>>  	return ht;
> >>>>  }
> >>>>  
> >>>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >>>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >>>> +		cds_lfht_lookup_fct match, void *arg,
> >>>
> >>> arg -> key ?
> >>>
> >>> for "match", our approach is to provide this function as parameter to
> >>> cds_lfht_new rather than pass it as parameter each time a lookup is
> >>> performed. What is the reason why we should pass it here as a parameter?
> >>>
> >>
> >> Allow the user define it.
> >> In the test, I pass match = a function always returns true when need,
> >> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.
> > 
> > This looks like an interesting debug and testing feature, but I don't
> > really see why we should complicate the API to include this. Is there a
> > real-life use-case you have in mind besides testing ?
> > 
> > If we only need this for testing, we can use a static variable in the
> > test program to influence the behavior of cds_lfht_test_lookup.
> > 
> > The other patches look fine, I'm just concerned about this one because
> > it adds complexity to the API which does not seem useful to end-users.
> > 
> 
> I think a generic API is OK.
> 
> Sometimes the caller don't have the key or the keys which are big
> are saved separated. Example: file server
> Or key comparation is too slow.
> Or caller just need approximate lookup.
> Or caller want to compare keys with different strategies for performance.

These arguments are appealing. However, this modification seems
incomplete: we would need to also modify cds_lfht_next_duplicate, and
*cds_lfht_add*, so they also can specify their own compare_fct strategy,
and remove the compare_fct from the lfht_new arguments, right ?

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Lai Jiangshan]

On 11/04/2011 09:53 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> On 11/04/2011 06:08 PM, Mathieu Desnoyers wrote:
>>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>>>> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
>>>>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>>>>>> We use hash value to determine the range of the object
>>>>>> and use cds_lfht_lookup_fct to lookup them.
>>>>>>
>>>>>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>>>>>> ---
>>>>>>  rculfhash.c            |    8 ++++----
>>>>>>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
>>>>>>  urcu/rculfhash.h       |    4 +++-
>>>>>>  3 files changed, 29 insertions(+), 8 deletions(-)
>>>>>>
>>>>>> diff --git a/rculfhash.c b/rculfhash.c
>>>>>> index d1a1766..29054cd 100644
>>>>>> --- a/rculfhash.c
>>>>>> +++ b/rculfhash.c
>>>>>> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>>>>>>  	return ht;
>>>>>>  }
>>>>>>  
>>>>>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>>>>>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>>>>>> +		cds_lfht_lookup_fct match, void *arg,
>>>>>
>>>>> arg -> key ?
>>>>>
>>>>> for "match", our approach is to provide this function as parameter to
>>>>> cds_lfht_new rather than pass it as parameter each time a lookup is
>>>>> performed. What is the reason why we should pass it here as a parameter?
>>>>>
>>>>
>>>> Allow the user define it.
>>>> In the test, I pass match = a function always returns true when need,
>>>> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.
>>>
>>> This looks like an interesting debug and testing feature, but I don't
>>> really see why we should complicate the API to include this. Is there a
>>> real-life use-case you have in mind besides testing ?
>>>
>>> If we only need this for testing, we can use a static variable in the
>>> test program to influence the behavior of cds_lfht_test_lookup.
>>>
>>> The other patches look fine, I'm just concerned about this one because
>>> it adds complexity to the API which does not seem useful to end-users.
>>>
>>
>> I think a generic API is OK.
>>
>> Sometimes the caller don't have the key or the keys which are big
>> are saved separated. Example: file server
>> Or key comparation is too slow.
>> Or caller just need approximate lookup.
>> Or caller want to compare keys with different strategies for performance.
> 
> These arguments are appealing. However, this modification seems
> incomplete: we would need to also modify cds_lfht_next_duplicate, and
> *cds_lfht_add*, so they also can specify their own compare_fct strategy,
> and remove the compare_fct from the lfht_new arguments, right ?
> 

Yes. I planned. But they don't be required for struct cds_lfht_node changes,
so they can be done later.

[ltt-dev] [PATCH 3/7] rculfhash: make cds_lfht_lookup() more generic

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/04/2011 09:53 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> On 11/04/2011 06:08 PM, Mathieu Desnoyers wrote:
> >>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >>>> On 11/03/2011 01:23 AM, Mathieu Desnoyers wrote:
> >>>>> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >>>>>> We use hash value to determine the range of the object
> >>>>>> and use cds_lfht_lookup_fct to lookup them.
> >>>>>>
> >>>>>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >>>>>> ---
> >>>>>>  rculfhash.c            |    8 ++++----
> >>>>>>  tests/test_urcu_hash.c |   25 ++++++++++++++++++++++---
> >>>>>>  urcu/rculfhash.h       |    4 +++-
> >>>>>>  3 files changed, 29 insertions(+), 8 deletions(-)
> >>>>>>
> >>>>>> diff --git a/rculfhash.c b/rculfhash.c
> >>>>>> index d1a1766..29054cd 100644
> >>>>>> --- a/rculfhash.c
> >>>>>> +++ b/rculfhash.c
> >>>>>> @@ -1391,14 +1391,14 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
> >>>>>>  	return ht;
> >>>>>>  }
> >>>>>>  
> >>>>>> -void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >>>>>> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >>>>>> +		cds_lfht_lookup_fct match, void *arg,
> >>>>>
> >>>>> arg -> key ?
> >>>>>
> >>>>> for "match", our approach is to provide this function as parameter to
> >>>>> cds_lfht_new rather than pass it as parameter each time a lookup is
> >>>>> performed. What is the reason why we should pass it here as a parameter?
> >>>>>
> >>>>
> >>>> Allow the user define it.
> >>>> In the test, I pass match = a function always returns true when need,
> >>>> thus cds_lfht_lookup() returns the first node of same-hash-value-chain.
> >>>
> >>> This looks like an interesting debug and testing feature, but I don't
> >>> really see why we should complicate the API to include this. Is there a
> >>> real-life use-case you have in mind besides testing ?
> >>>
> >>> If we only need this for testing, we can use a static variable in the
> >>> test program to influence the behavior of cds_lfht_test_lookup.
> >>>
> >>> The other patches look fine, I'm just concerned about this one because
> >>> it adds complexity to the API which does not seem useful to end-users.
> >>>
> >>
> >> I think a generic API is OK.
> >>
> >> Sometimes the caller don't have the key or the keys which are big
> >> are saved separated. Example: file server
> >> Or key comparation is too slow.
> >> Or caller just need approximate lookup.
> >> Or caller want to compare keys with different strategies for performance.
> > 
> > These arguments are appealing. However, this modification seems
> > incomplete: we would need to also modify cds_lfht_next_duplicate, and
> > *cds_lfht_add*, so they also can specify their own compare_fct strategy,
> > and remove the compare_fct from the lfht_new arguments, right ?
> > 
> 
> Yes. I planned. But they don't be required for struct cds_lfht_node changes,
> so they can be done later.

Given this is an API change with various directly related parts, I
prefer to do it in one go. I did the following patch that does the
entire change (now merged). Thanks for proposing this! I'll go through
the rest of your patchset and try to apply it after this patch.

Thanks,

Mathieu

commit 0422d92c2d658f6093b8209f75808efd2109a110
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Sat Nov 5 09:01:09 2011 -0400

    rculfhash: extract compare_fct and hash_fct from the hash table
    
    Leave the compare_fct and hash_fct to the caller, which can therefore
    become the only one which needs to know the layout of struct
    cds_lfht_node (except for the _cds_lfht_node part).
    
    This will enable us to remove the cds_lfht_node structure from the hash
    table (moving it entirely to the caller), replacing it by
    _cds_lfht_node, which is really the only part the hash table needs to
    know about.
    
    Use-cases that can benefit from this extra flexibility:
    
    >> Sometimes the caller don't have the key or the keys which are big
    >> are saved separated. Example: file server
    >> Or key comparation is too slow.
    >> Or caller just need approximate lookup.
    >> Or caller want to compare keys with different strategies for
    >> performance.
    
    Suggested-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index 600feec..53ecaac 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -267,8 +267,6 @@ struct rcu_table {
  */
 struct cds_lfht {
 	struct rcu_table t;
-	cds_lfht_hash_fct hash_fct;
-	cds_lfht_compare_fct compare_fct;
 	unsigned long min_alloc_order;
 	unsigned long min_alloc_size;
 	unsigned long hash_seed;
@@ -320,6 +318,7 @@ struct partition_resize_work {
 
 static
 void _cds_lfht_add(struct cds_lfht *ht,
+		cds_lfht_match_fct match,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
@@ -892,6 +891,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
  */
 static
 void _cds_lfht_add(struct cds_lfht *ht,
+		cds_lfht_match_fct match,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
@@ -944,7 +944,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 				 * (including observe one node by one node
 				 * by forward iterations)
 				 */
-				cds_lfht_next_duplicate(ht, &d_iter);
+				cds_lfht_next_duplicate(ht, match, &d_iter);
 				if (!d_iter.node)
 					goto insert;
 
@@ -1120,7 +1120,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
 			   i, j, (1UL << (i - 1)) + j);
 		new_node->p.reverse_hash =
 				bit_reverse_ulong((1UL << (i - 1)) + j);
-		_cds_lfht_add(ht, 1UL << (i - 1),
+		_cds_lfht_add(ht, NULL, 1UL << (i - 1),
 				new_node, NULL, 1);
 	}
 	ht->cds_lfht_rcu_read_unlock();
@@ -1337,10 +1337,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 	}
 }
 
-struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
-			unsigned long init_size,
+struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
 			void (*cds_lfht_call_rcu)(struct rcu_head *head,
@@ -1368,9 +1365,6 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 	ht = calloc(1, sizeof(struct cds_lfht));
 	assert(ht);
 	ht->flags = flags;
-	ht->hash_fct = hash_fct;
-	ht->compare_fct = compare_fct;
-	ht->hash_seed = hash_seed;
 	ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
 	ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
 	ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
@@ -1392,14 +1386,13 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 	return ht;
 }
 
-void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
-		struct cds_lfht_iter *iter)
+void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
+		unsigned long hash, void *key, struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next, *dummy_node;
 	struct _cds_lfht_node *lookup;
-	unsigned long hash, reverse_hash, size;
+	unsigned long reverse_hash, size;
 
-	hash = ht->hash_fct(key, key_len, ht->hash_seed);
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
@@ -1422,7 +1415,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
 		    && node->p.reverse_hash == reverse_hash
-		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
+		    && caa_likely(match(node, key))) {
 				break;
 		}
 		node = clear_flag(next);
@@ -1432,17 +1425,16 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 	iter->next = next;
 }
 
-void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
+void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
+		struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next;
 	unsigned long reverse_hash;
 	void *key;
-	size_t key_len;
 
 	node = iter->node;
 	reverse_hash = node->p.reverse_hash;
 	key = node->key;
-	key_len = node->key_len;
 	next = iter->next;
 	node = clear_flag(next);
 
@@ -1458,7 +1450,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 		next = rcu_dereference(node->p.next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
-		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
+		    && caa_likely(match(node->key, key))) {
 				break;
 		}
 		node = clear_flag(next);
@@ -1503,46 +1495,45 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	cds_lfht_next(ht, iter);
 }
 
-void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
+void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
+		struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
-
 	size = rcu_dereference(ht->t.size);
-	_cds_lfht_add(ht, size, node, NULL, 0);
+	_cds_lfht_add(ht, NULL, size, node, NULL, 0);
 	ht_count_add(ht, size, hash);
 }
 
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
+				cds_lfht_match_fct match,
+				unsigned long hash,
 				struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
-
 	size = rcu_dereference(ht->t.size);
-	_cds_lfht_add(ht, size, node, &iter, 0);
+	_cds_lfht_add(ht, match, size, node, &iter, 0);
 	if (iter.node == node)
 		ht_count_add(ht, size, hash);
 	return iter.node;
 }
 
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
+				cds_lfht_match_fct match,
+				unsigned long hash,
 				struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
-
 	size = rcu_dereference(ht->t.size);
 	for (;;) {
-		_cds_lfht_add(ht, size, node, &iter, 0);
+		_cds_lfht_add(ht, match, size, node, &iter, 0);
 		if (iter.node == node) {
 			ht_count_add(ht, size, hash);
 			return NULL;
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index e28c14a..3111353 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -41,6 +41,8 @@
 #define DEFAULT_MIN_ALLOC_SIZE	1
 #define DEFAULT_RAND_POOL	1000000
 
+#define TEST_HASH_SEED	0x42UL
+
 /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
 #define CACHE_LINE_SIZE 4096
 
@@ -419,6 +421,24 @@ unsigned long test_compare(void *key1, size_t key1_len,
 		return 1;
 }
 
+static
+int test_match(struct cds_lfht_node *node, void *arg)
+{
+	return !test_compare(node->key, node->key_len,
+			arg, sizeof(unsigned long));
+}
+
+static
+void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
+		struct cds_lfht_iter *iter)
+{
+	assert(key_len == sizeof(unsigned long));
+
+	cds_lfht_lookup(ht, test_match,
+			test_hash(key, key_len, TEST_HASH_SEED),
+			key, iter);
+}
+
 void *thr_count(void *arg)
 {
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -479,7 +499,7 @@ void *thr_reader(void *_count)
 
 	for (;;) {
 		rcu_read_lock();
-		cds_lfht_lookup(test_ht,
+		cds_lfht_test_lookup(test_ht,
 			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
 			sizeof(void *), &iter);
 		node = cds_lfht_iter_get_test_node(&iter);
@@ -551,12 +571,18 @@ void *thr_writer(void *_count)
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, &node->node);
+				ret_node = cds_lfht_add_unique(test_ht, test_match,
+					test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+					&node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, &node->node);
+					ret_node = cds_lfht_add_replace(test_ht, test_match,
+							test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+							&node->node);
 				else
-					cds_lfht_add(test_ht, &node->node);
+					cds_lfht_add(test_ht,
+						test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+						&node->node);
 			}
 			rcu_read_unlock();
 			if (add_unique && ret_node != &node->node) {
@@ -574,7 +600,7 @@ void *thr_writer(void *_count)
 		} else {
 			/* May delete */
 			rcu_read_lock();
-			cds_lfht_lookup(test_ht,
+			cds_lfht_test_lookup(test_ht,
 				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
 				sizeof(void *), &iter);
 			ret = cds_lfht_del(test_ht, &iter);
@@ -642,12 +668,18 @@ static int populate_hash(void)
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, &node->node);
+			ret_node = cds_lfht_add_unique(test_ht, test_match,
+				test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+				&node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, &node->node);
+				ret_node = cds_lfht_add_replace(test_ht, test_match,
+						test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+						&node->node);
 			else
-				cds_lfht_add(test_ht, &node->node);
+				cds_lfht_add(test_ht,
+					test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+					&node->node);
 		}
 		rcu_read_unlock();
 		if (add_unique && ret_node != &node->node) {
@@ -932,8 +964,7 @@ int main(int argc, char **argv)
 	 * thread from the point of view of resize.
 	 */
 	rcu_register_thread();
-	test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL,
-			init_hash_size, min_hash_alloc_size,
+	test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
 			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
 			CDS_LFHT_ACCOUNTING, NULL);
       	ret = populate_hash();
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index f4f3373..9dcaf02 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -84,11 +84,13 @@ struct cds_lfht;
 
 typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
 					unsigned long seed);
-typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
-					void *key2, size_t key2_len);
+typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, void *key);
 
 /*
  * cds_lfht_node_init - initialize a hash table node
+ * @node: the node to initialize.
+ * @key: pointer to the key to use.
+ * @key_len: the length of the key, in bytes.
  */
 static inline
 void cds_lfht_node_init(struct cds_lfht_node *node, void *key,
@@ -109,10 +111,7 @@ enum {
 /*
  * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
  */
-struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
-			unsigned long init_size,
+struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
 			void (*cds_lfht_call_rcu)(struct rcu_head *head,
@@ -128,9 +127,6 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 
 /*
  * cds_lfht_new - allocate a hash table.
- * @hash_fct: the hashing function.
- * @compare_fct: the key comparison function.
- * @hash_seed: the seed for hash function.
  * @init_size: number of nodes to allocate initially. Must be power of two.
  * @min_alloc_size: the smallest allocation size to use. Must be power of two.
  * @flags: hash table creation flags (can be combined with bitwise or: '|').
@@ -151,16 +147,12 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
  * Threads calling this API need to be registered RCU read-side threads.
  */
 static inline
-struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
-			unsigned long init_size,
+struct cds_lfht *cds_lfht_new(unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
 			pthread_attr_t *attr)
 {
-	return _cds_lfht_new(hash_fct, compare_fct, hash_seed,
-			init_size, min_alloc_size, flags,
+	return _cds_lfht_new(init_size, min_alloc_size, flags,
 			call_rcu, synchronize_rcu, rcu_read_lock,
 			rcu_read_unlock, rcu_thread_offline,
 			rcu_thread_online, rcu_register_thread,
@@ -187,6 +179,7 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr);
  * @count: Traverse the hash table, count the number of nodes observed.
  * @removed: Number of logically removed nodes observed during traversal.
  * @split_count_after: Sample the node count split-counter after traversal.
+ *
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
@@ -198,16 +191,22 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 
 /*
  * cds_lfht_lookup - lookup a node by key.
+ * @ht: the hash table.
+ * @match: the key match function.
+ * @hash: the key hash.
+ * @iter: Node, if found (output). *iter->node set to NULL if not found.
  *
- * Output in "*iter". *iter->node set to NULL if not found.
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
-void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
-		struct cds_lfht_iter *iter);
+void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
+		unsigned long hash, void *key, struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_next_duplicate - get the next item with same key (after a lookup).
+ * @ht: the hash table.
+ * @match: the key match function.
+ * @iter: Node, if found (output). *iter->node set to NULL if not found.
  *
  * Uses an iterator initialized by a lookup.
  * Sets *iter-node to the following node with same key.
@@ -218,10 +217,13 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
-void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter);
+void cds_lfht_next_duplicate(struct cds_lfht *ht,
+		cds_lfht_match_fct match, struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_first - get the first node in the table.
+ * @ht: the hash table.
+ * @iter: First node, if exists (output). *iter->node set to NULL if not found.
  *
  * Output in "*iter". *iter->node set to NULL if table is empty.
  * Call with rcu_read_lock held.
@@ -231,6 +233,8 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_next - get the next node in the table.
+ * @ht: the hash table.
+ * @iter: Next node, if exists (output). *iter->node set to NULL if not found.
  *
  * Input/Output in "*iter". *iter->node set to NULL if *iter was
  * pointing to the last table node.
@@ -241,15 +245,22 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_add - add a node to the hash table.
+ * @ht: the hash table.
+ * @hash: the key hash.
+ * @node: the node to add.
  *
  * This function supports adding redundant keys into the table.
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
-void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
+void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
+		struct cds_lfht_node *node);
 
 /*
  * cds_lfht_add_unique - add a node to hash table, if key is not present.
+ * @ht: the hash table.
+ * @match: the key match function.
+ * @node: the node to try adding.
  *
  * Return the node added upon success.
  * Return the unique node already present upon failure. If
@@ -264,10 +275,15 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
  * add_unique and add_replace (see below).
  */
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
+		cds_lfht_match_fct match,
+		unsigned long hash,
 		struct cds_lfht_node *node);
 
 /*
  * cds_lfht_add_replace - replace or add a node within hash table.
+ * @ht: the hash table.
+ * @match: the key match function.
+ * @node: the node to add.
  *
  * Return the node replaced upon success. If no node matching the key
  * was present, return NULL, which also means the operation succeeded.
@@ -288,10 +304,15 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
  * will never generate duplicated keys.
  */
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
+		cds_lfht_match_fct match,
+		unsigned long hash,
 		struct cds_lfht_node *node);
 
 /*
  * cds_lfht_replace - replace a node pointer to by iter within hash table.
+ * @ht: the hash table.
+ * @old_iter: the iterator position of the node to replace.
+ * @now_node: the new node to try using for replacement.
  *
  * Return 0 if replacement is successful, negative value otherwise.
  * Replacing a NULL old node or an already removed node will fail with a
@@ -319,6 +340,8 @@ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
 
 /*
  * cds_lfht_del - remove node pointed to by iterator from hash table.
+ * @ht: the hash table.
+ * @iter: the iterator position of the node to delete.
  *
  * Return 0 if the node is successfully removed, negative value
  * otherwise.
@@ -337,6 +360,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_resize - Force a hash table resize
+ * @ht: the hash table.
  * @new_size: update to this hash table size.
  *
  * Threads calling this API need to be registered RCU read-side threads.



-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 4/7] rculfhash: Comparision API use node pointer instead of key

[Lai Jiangshan]

Prepare for future work for moving key out of struct cds_lfht_node.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |    2 +-
 tests/test_urcu_hash.c |   12 +++++++++---
 urcu/rculfhash.h       |    4 ++--
 3 files changed, 12 insertions(+), 6 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 29054cd..9745129 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1457,7 +1457,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 		next = rcu_dereference(node->p.next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
-		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
+		    && caa_likely(!ht->compare_fct(node, iter->node))) {
 				break;
 		}
 		node = clear_flag(next);
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 4c45573..9689878 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -409,8 +409,8 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed)
 #endif
 
 static
-unsigned long test_compare(void *key1, size_t key1_len,
-                           void *key2, size_t key2_len)
+int __test_compare(void *key1, size_t key1_len,
+		   void *key2, size_t key2_len)
 {
 	if (caa_unlikely(key1_len != key2_len))
 		return -1;
@@ -422,9 +422,15 @@ unsigned long test_compare(void *key1, size_t key1_len,
 }
 
 static
+int test_compare(struct cds_lfht_node *a, struct cds_lfht_node *b)
+{
+	return __test_compare(a->key, a->key_len, b->key, b->key_len);
+}
+
+static
 int test_match(struct cds_lfht_node *node, void *arg)
 {
-	return !test_compare(node->key, node->key_len,
+	return !__test_compare(node->key, node->key_len,
 			arg, sizeof(unsigned long));
 }
 
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index b56fe56..c6946dc 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -84,8 +84,8 @@ struct cds_lfht;
 
 typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
 					unsigned long seed);
-typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
-					void *key2, size_t key2_len);
+typedef int (*cds_lfht_compare_fct)(struct cds_lfht_node *a,
+		struct cds_lfht_node *b);
 typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
 
 /*
-- 
1.7.4.4

[ltt-dev] [PATCH 4/7] rculfhash: Comparision API use node pointer instead of key

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Prepare for future work for moving key out of struct cds_lfht_node.

Following commit 0422d92c2d658f6093b8209f75808efd2109a110, I don't think
this is needed anymore.

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |    2 +-
>  tests/test_urcu_hash.c |   12 +++++++++---
>  urcu/rculfhash.h       |    4 ++--
>  3 files changed, 12 insertions(+), 6 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 29054cd..9745129 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1457,7 +1457,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  		next = rcu_dereference(node->p.next);
>  		if (caa_likely(!is_removed(next))
>  		    && !is_dummy(next)
> -		    && caa_likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
> +		    && caa_likely(!ht->compare_fct(node, iter->node))) {
>  				break;
>  		}
>  		node = clear_flag(next);
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 4c45573..9689878 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -409,8 +409,8 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed)
>  #endif
>  
>  static
> -unsigned long test_compare(void *key1, size_t key1_len,
> -                           void *key2, size_t key2_len)
> +int __test_compare(void *key1, size_t key1_len,
> +		   void *key2, size_t key2_len)
>  {
>  	if (caa_unlikely(key1_len != key2_len))
>  		return -1;
> @@ -422,9 +422,15 @@ unsigned long test_compare(void *key1, size_t key1_len,
>  }
>  
>  static
> +int test_compare(struct cds_lfht_node *a, struct cds_lfht_node *b)
> +{
> +	return __test_compare(a->key, a->key_len, b->key, b->key_len);
> +}
> +
> +static
>  int test_match(struct cds_lfht_node *node, void *arg)
>  {
> -	return !test_compare(node->key, node->key_len,
> +	return !__test_compare(node->key, node->key_len,
>  			arg, sizeof(unsigned long));
>  }
>  
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index b56fe56..c6946dc 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -84,8 +84,8 @@ struct cds_lfht;
>  
>  typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
>  					unsigned long seed);
> -typedef unsigned long (*cds_lfht_compare_fct)(void *key1, size_t key1_len,
> -					void *key2, size_t key2_len);
> +typedef int (*cds_lfht_compare_fct)(struct cds_lfht_node *a,
> +		struct cds_lfht_node *b);
>  typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
>  
>  /*
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 5/7] rculfhash: Pass hash value to cds_lfht_add* APIs

[Lai Jiangshan]

Pass hash value to cds_lfht_add* APIs instead of calculation it in rculfhash.c.
Prepare for future work for moving key out of struct cds_lfht_node.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |   16 +++++++---------
 tests/test_urcu_hash.c |   38 ++++++++++++++++++++++++++++++++------
 urcu/rculfhash.h       |    7 ++++---
 3 files changed, 43 insertions(+), 18 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 9745129..6a8c720 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1502,11 +1502,11 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	cds_lfht_next(ht, iter);
 }
 
-void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
+void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
+		struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
@@ -1515,12 +1515,11 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
 }
 
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
-				struct cds_lfht_node *node)
+		unsigned long hash, struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
@@ -1531,12 +1530,11 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 }
 
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
-				struct cds_lfht_node *node)
+		unsigned long hash, struct cds_lfht_node *node)
 {
-	unsigned long hash, size;
+	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 9689878..1cae6d6 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -444,6 +444,32 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 			test_match, key, iter);
 }
 
+static
+void cds_lfht_test_add(struct cds_lfht *ht, struct lfht_test_node *node)
+{
+	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+
+	cds_lfht_add(ht, hash, &node->node);
+}
+
+static
+struct cds_lfht_node *cds_lfht_test_add_unique(struct cds_lfht *ht,
+		struct lfht_test_node *node)
+{
+	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+
+	return cds_lfht_add_unique(ht, hash, &node->node);
+}
+
+static
+struct cds_lfht_node *cds_lfht_test_add_replace(struct cds_lfht *ht,
+		struct lfht_test_node *node)
+{
+	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+
+	return cds_lfht_add_replace(ht, hash, &node->node);
+}
+
 void *thr_count(void *arg)
 {
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -576,12 +602,12 @@ void *thr_writer(void *_count)
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, &node->node);
+				ret_node = cds_lfht_test_add_unique(test_ht, node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, &node->node);
+					ret_node = cds_lfht_test_add_replace(test_ht, node);
 				else
-					cds_lfht_add(test_ht, &node->node);
+					cds_lfht_test_add(test_ht, node);
 			}
 			rcu_read_unlock();
 			if (add_unique && ret_node != &node->node) {
@@ -667,12 +693,12 @@ static int populate_hash(void)
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, &node->node);
+			ret_node = cds_lfht_test_add_unique(test_ht, node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, &node->node);
+				ret_node = cds_lfht_test_add_replace(test_ht, node);
 			else
-				cds_lfht_add(test_ht, &node->node);
+				cds_lfht_test_add(test_ht, node);
 		}
 		rcu_read_unlock();
 		if (add_unique && ret_node != &node->node) {
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index c6946dc..d4c9209 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -248,7 +248,8 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter);
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
  */
-void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
+void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
+		struct cds_lfht_node *node);
 
 /*
  * cds_lfht_add_unique - add a node to hash table, if key is not present.
@@ -266,7 +267,7 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
  * add_unique and add_replace (see below).
  */
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
-		struct cds_lfht_node *node);
+		unsigned long hash, struct cds_lfht_node *node);
 
 /*
  * cds_lfht_add_replace - replace or add a node within hash table.
@@ -290,7 +291,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
  * will never generate duplicated keys.
  */
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
-		struct cds_lfht_node *node);
+		unsigned long hash, struct cds_lfht_node *node);
 
 /*
  * cds_lfht_replace - replace a node pointer to by iter within hash table.
-- 
1.7.4.4

[ltt-dev] [PATCH 5/7] rculfhash: Pass hash value to cds_lfht_add* APIs

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Pass hash value to cds_lfht_add* APIs instead of calculation it in rculfhash.c.
> Prepare for future work for moving key out of struct cds_lfht_node.

This has also been done within commit
0422d92c2d658f6093b8209f75808efd2109a110.

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |   16 +++++++---------
>  tests/test_urcu_hash.c |   38 ++++++++++++++++++++++++++++++++------
>  urcu/rculfhash.h       |    7 ++++---
>  3 files changed, 43 insertions(+), 18 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 9745129..6a8c720 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1502,11 +1502,11 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  	cds_lfht_next(ht, iter);
>  }
>  
> -void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
> +void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> +		struct cds_lfht_node *node)
>  {
> -	unsigned long hash, size;
> +	unsigned long size;
>  
> -	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
>  	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
>  
>  	size = rcu_dereference(ht->t.size);
> @@ -1515,12 +1515,11 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
>  }
>  
>  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> -				struct cds_lfht_node *node)
> +		unsigned long hash, struct cds_lfht_node *node)
>  {
> -	unsigned long hash, size;
> +	unsigned long size;
>  	struct cds_lfht_iter iter;
>  
> -	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
>  	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
>  
>  	size = rcu_dereference(ht->t.size);
> @@ -1531,12 +1530,11 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
>  }
>  
>  struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
> -				struct cds_lfht_node *node)
> +		unsigned long hash, struct cds_lfht_node *node)
>  {
> -	unsigned long hash, size;
> +	unsigned long size;
>  	struct cds_lfht_iter iter;
>  
> -	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
>  	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
>  
>  	size = rcu_dereference(ht->t.size);
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 9689878..1cae6d6 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -444,6 +444,32 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>  			test_match, key, iter);
>  }
>  
> +static
> +void cds_lfht_test_add(struct cds_lfht *ht, struct lfht_test_node *node)
> +{
> +	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +
> +	cds_lfht_add(ht, hash, &node->node);
> +}
> +
> +static
> +struct cds_lfht_node *cds_lfht_test_add_unique(struct cds_lfht *ht,
> +		struct lfht_test_node *node)
> +{
> +	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +
> +	return cds_lfht_add_unique(ht, hash, &node->node);
> +}
> +
> +static
> +struct cds_lfht_node *cds_lfht_test_add_replace(struct cds_lfht *ht,
> +		struct lfht_test_node *node)
> +{
> +	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +
> +	return cds_lfht_add_replace(ht, hash, &node->node);
> +}
> +
>  void *thr_count(void *arg)
>  {
>  	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
> @@ -576,12 +602,12 @@ void *thr_writer(void *_count)
>  				sizeof(void *));
>  			rcu_read_lock();
>  			if (add_unique) {
> -				ret_node = cds_lfht_add_unique(test_ht, &node->node);
> +				ret_node = cds_lfht_test_add_unique(test_ht, node);
>  			} else {
>  				if (add_replace)
> -					ret_node = cds_lfht_add_replace(test_ht, &node->node);
> +					ret_node = cds_lfht_test_add_replace(test_ht, node);
>  				else
> -					cds_lfht_add(test_ht, &node->node);
> +					cds_lfht_test_add(test_ht, node);
>  			}
>  			rcu_read_unlock();
>  			if (add_unique && ret_node != &node->node) {
> @@ -667,12 +693,12 @@ static int populate_hash(void)
>  			sizeof(void *));
>  		rcu_read_lock();
>  		if (add_unique) {
> -			ret_node = cds_lfht_add_unique(test_ht, &node->node);
> +			ret_node = cds_lfht_test_add_unique(test_ht, node);
>  		} else {
>  			if (add_replace)
> -				ret_node = cds_lfht_add_replace(test_ht, &node->node);
> +				ret_node = cds_lfht_test_add_replace(test_ht, node);
>  			else
> -				cds_lfht_add(test_ht, &node->node);
> +				cds_lfht_test_add(test_ht, node);
>  		}
>  		rcu_read_unlock();
>  		if (add_unique && ret_node != &node->node) {
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index c6946dc..d4c9209 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -248,7 +248,8 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter);
>   * Call with rcu_read_lock held.
>   * Threads calling this API need to be registered RCU read-side threads.
>   */
> -void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
> +void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> +		struct cds_lfht_node *node);
>  
>  /*
>   * cds_lfht_add_unique - add a node to hash table, if key is not present.
> @@ -266,7 +267,7 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node);
>   * add_unique and add_replace (see below).
>   */
>  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> -		struct cds_lfht_node *node);
> +		unsigned long hash, struct cds_lfht_node *node);
>  
>  /*
>   * cds_lfht_add_replace - replace or add a node within hash table.
> @@ -290,7 +291,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
>   * will never generate duplicated keys.
>   */
>  struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
> -		struct cds_lfht_node *node);
> +		unsigned long hash, struct cds_lfht_node *node);
>  
>  /*
>   * cds_lfht_replace - replace a node pointer to by iter within hash table.
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 6/7] rculfhash: Move key out of struct lfht_test_node

[Lai Jiangshan]

Make struct lfht_test_node only contains basic field.
Let user take the responsibility to handle the <key>(hash_set)
or <key,value>(hash_map) management and calculation.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |   12 +-----------
 tests/test_urcu_hash.c |   22 +++++++++++++++-------
 urcu/rculfhash.h       |   33 +++------------------------------
 3 files changed, 19 insertions(+), 48 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 6a8c720..a569172 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -267,11 +267,9 @@ struct rcu_table {
  */
 struct cds_lfht {
 	struct rcu_table t;
-	cds_lfht_hash_fct hash_fct;
 	cds_lfht_compare_fct compare_fct;
 	unsigned long min_alloc_order;
 	unsigned long min_alloc_size;
-	unsigned long hash_seed;
 	int flags;
 	/*
 	 * We need to put the work threads offline (QSBR) when taking this
@@ -1336,9 +1334,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 	}
 }
 
-struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
+struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
 			unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
@@ -1367,9 +1363,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 	ht = calloc(1, sizeof(struct cds_lfht));
 	assert(ht);
 	ht->flags = flags;
-	ht->hash_fct = hash_fct;
 	ht->compare_fct = compare_fct;
-	ht->hash_seed = hash_seed;
 	ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
 	ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
 	ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
@@ -1435,13 +1429,9 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next;
 	unsigned long reverse_hash;
-	void *key;
-	size_t key_len;
 
 	node = iter->node;
 	reverse_hash = node->p.reverse_hash;
-	key = node->key;
-	key_len = node->key_len;
 	next = iter->next;
 	node = clear_flag(next);
 
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 1cae6d6..2d2ef22 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -109,6 +109,8 @@ struct test_data {
 
 struct lfht_test_node {
 	struct cds_lfht_node node;
+	void *key;
+	unsigned int key_len;
 	/* cache-cold for iteration */
 	struct rcu_head head;
 };
@@ -123,7 +125,8 @@ static inline
 void lfht_test_node_init(struct lfht_test_node *node, void *key,
 			size_t key_len)
 {
-	cds_lfht_node_init(&node->node, key, key_len);
+	node->key = key;
+	node->key_len = key_len;
 }
 
 static inline struct lfht_test_node *
@@ -424,13 +427,18 @@ int __test_compare(void *key1, size_t key1_len,
 static
 int test_compare(struct cds_lfht_node *a, struct cds_lfht_node *b)
 {
-	return __test_compare(a->key, a->key_len, b->key, b->key_len);
+	struct lfht_test_node *u = to_test_node(a);
+	struct lfht_test_node *v = to_test_node(a);
+
+	return __test_compare(u->key, u->key_len, v->key, v->key_len);
 }
 
 static
 int test_match(struct cds_lfht_node *node, void *arg)
 {
-	return !__test_compare(node->key, node->key_len,
+	struct lfht_test_node *test_node = to_test_node(node);
+
+	return !__test_compare(test_node->key, test_node->key_len,
 			arg, sizeof(unsigned long));
 }
 
@@ -447,7 +455,7 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 static
 void cds_lfht_test_add(struct cds_lfht *ht, struct lfht_test_node *node)
 {
-	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
 
 	cds_lfht_add(ht, hash, &node->node);
 }
@@ -456,7 +464,7 @@ static
 struct cds_lfht_node *cds_lfht_test_add_unique(struct cds_lfht *ht,
 		struct lfht_test_node *node)
 {
-	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
 
 	return cds_lfht_add_unique(ht, hash, &node->node);
 }
@@ -465,7 +473,7 @@ static
 struct cds_lfht_node *cds_lfht_test_add_replace(struct cds_lfht *ht,
 		struct lfht_test_node *node)
 {
-	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
+	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
 
 	return cds_lfht_add_replace(ht, hash, &node->node);
 }
@@ -983,7 +991,7 @@ int main(int argc, char **argv)
 	 * thread from the point of view of resize.
 	 */
 	rcu_register_thread();
-	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
+	test_ht = cds_lfht_new(test_compare,
 			init_hash_size, min_hash_alloc_size,
 			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
 			CDS_LFHT_ACCOUNTING, NULL);
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index d4c9209..cd5760e 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -47,12 +47,6 @@ struct _cds_lfht_node {
 } __attribute__((aligned(4)));
 
 /*
- * cds_lfht_node: Contains the full key and length required to check for
- * an actual match, and also contains an rcu_head structure that is used
- * by RCU to track a node through a given RCU grace period.  There is an
- * instance of _cds_lfht_node enclosed as a field within each
- * _cds_lfht_node structure.
- *
  * struct cds_lfht_node can be embedded into a structure (as a field).
  * caa_container_of() can be used to get the structure from the struct
  * cds_lfht_node after a lookup.
@@ -60,8 +54,6 @@ struct _cds_lfht_node {
 struct cds_lfht_node {
 	/* cache-hot for iteration */
 	struct _cds_lfht_node p;          /* needs to be first field */
-	void *key;
-	unsigned int key_len;
 };
 
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
@@ -82,24 +74,11 @@ struct cds_lfht;
  * Ensure reader and writer threads are registered as urcu readers.
  */
 
-typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
-					unsigned long seed);
 typedef int (*cds_lfht_compare_fct)(struct cds_lfht_node *a,
 		struct cds_lfht_node *b);
 typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
 
 /*
- * cds_lfht_node_init - initialize a hash table node
- */
-static inline
-void cds_lfht_node_init(struct cds_lfht_node *node, void *key,
-			size_t key_len)
-{
-	node->key = key;
-	node->key_len = key_len;
-}
-
-/*
  * Hash table creation flags.
  */
 enum {
@@ -110,9 +89,7 @@ enum {
 /*
  * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
  */
-struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
+struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
 			unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
@@ -129,9 +106,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
 
 /*
  * cds_lfht_new - allocate a hash table.
- * @hash_fct: the hashing function.
  * @compare_fct: the key comparison function.
- * @hash_seed: the seed for hash function.
  * @init_size: number of nodes to allocate initially. Must be power of two.
  * @min_alloc_size: the smallest allocation size to use. Must be power of two.
  * @flags: hash table creation flags (can be combined with bitwise or: '|').
@@ -152,15 +127,13 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
  * Threads calling this API need to be registered RCU read-side threads.
  */
 static inline
-struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
-			cds_lfht_compare_fct compare_fct,
-			unsigned long hash_seed,
+struct cds_lfht *cds_lfht_new(cds_lfht_compare_fct compare_fct,
 			unsigned long init_size,
 			unsigned long min_alloc_size,
 			int flags,
 			pthread_attr_t *attr)
 {
-	return _cds_lfht_new(hash_fct, compare_fct, hash_seed,
+	return _cds_lfht_new(compare_fct,
 			init_size, min_alloc_size, flags,
 			call_rcu, synchronize_rcu, rcu_read_lock,
 			rcu_read_unlock, rcu_thread_offline,
-- 
1.7.4.4

[ltt-dev] [PATCH 6/7] rculfhash: Move key out of struct lfht_test_node

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Make struct lfht_test_node only contains basic field.
> Let user take the responsibility to handle the <key>(hash_set)
> or <key,value>(hash_map) management and calculation.

Taken care of by commits 0422d92c2d658f6093b8209f75808efd2109a110 and
b84f92d592010f01851c3fdcd5ac7d3666028146.

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |   12 +-----------
>  tests/test_urcu_hash.c |   22 +++++++++++++++-------
>  urcu/rculfhash.h       |   33 +++------------------------------
>  3 files changed, 19 insertions(+), 48 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 6a8c720..a569172 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -267,11 +267,9 @@ struct rcu_table {
>   */
>  struct cds_lfht {
>  	struct rcu_table t;
> -	cds_lfht_hash_fct hash_fct;
>  	cds_lfht_compare_fct compare_fct;
>  	unsigned long min_alloc_order;
>  	unsigned long min_alloc_size;
> -	unsigned long hash_seed;
>  	int flags;
>  	/*
>  	 * We need to put the work threads offline (QSBR) when taking this
> @@ -1336,9 +1334,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
>  	}
>  }
>  
> -struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
> -			cds_lfht_compare_fct compare_fct,
> -			unsigned long hash_seed,
> +struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
>  			unsigned long init_size,
>  			unsigned long min_alloc_size,
>  			int flags,
> @@ -1367,9 +1363,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>  	ht = calloc(1, sizeof(struct cds_lfht));
>  	assert(ht);
>  	ht->flags = flags;
> -	ht->hash_fct = hash_fct;
>  	ht->compare_fct = compare_fct;
> -	ht->hash_seed = hash_seed;
>  	ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
>  	ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
>  	ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
> @@ -1435,13 +1429,9 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  {
>  	struct cds_lfht_node *node, *next;
>  	unsigned long reverse_hash;
> -	void *key;
> -	size_t key_len;
>  
>  	node = iter->node;
>  	reverse_hash = node->p.reverse_hash;
> -	key = node->key;
> -	key_len = node->key_len;
>  	next = iter->next;
>  	node = clear_flag(next);
>  
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 1cae6d6..2d2ef22 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -109,6 +109,8 @@ struct test_data {
>  
>  struct lfht_test_node {
>  	struct cds_lfht_node node;
> +	void *key;
> +	unsigned int key_len;
>  	/* cache-cold for iteration */
>  	struct rcu_head head;
>  };
> @@ -123,7 +125,8 @@ static inline
>  void lfht_test_node_init(struct lfht_test_node *node, void *key,
>  			size_t key_len)
>  {
> -	cds_lfht_node_init(&node->node, key, key_len);
> +	node->key = key;
> +	node->key_len = key_len;
>  }
>  
>  static inline struct lfht_test_node *
> @@ -424,13 +427,18 @@ int __test_compare(void *key1, size_t key1_len,
>  static
>  int test_compare(struct cds_lfht_node *a, struct cds_lfht_node *b)
>  {
> -	return __test_compare(a->key, a->key_len, b->key, b->key_len);
> +	struct lfht_test_node *u = to_test_node(a);
> +	struct lfht_test_node *v = to_test_node(a);
> +
> +	return __test_compare(u->key, u->key_len, v->key, v->key_len);
>  }
>  
>  static
>  int test_match(struct cds_lfht_node *node, void *arg)
>  {
> -	return !__test_compare(node->key, node->key_len,
> +	struct lfht_test_node *test_node = to_test_node(node);
> +
> +	return !__test_compare(test_node->key, test_node->key_len,
>  			arg, sizeof(unsigned long));
>  }
>  
> @@ -447,7 +455,7 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>  static
>  void cds_lfht_test_add(struct cds_lfht *ht, struct lfht_test_node *node)
>  {
> -	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
>  
>  	cds_lfht_add(ht, hash, &node->node);
>  }
> @@ -456,7 +464,7 @@ static
>  struct cds_lfht_node *cds_lfht_test_add_unique(struct cds_lfht *ht,
>  		struct lfht_test_node *node)
>  {
> -	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
>  
>  	return cds_lfht_add_unique(ht, hash, &node->node);
>  }
> @@ -465,7 +473,7 @@ static
>  struct cds_lfht_node *cds_lfht_test_add_replace(struct cds_lfht *ht,
>  		struct lfht_test_node *node)
>  {
> -	unsigned long hash = test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED);
> +	unsigned long hash = test_hash(node->key, node->key_len, TEST_HASH_SEED);
>  
>  	return cds_lfht_add_replace(ht, hash, &node->node);
>  }
> @@ -983,7 +991,7 @@ int main(int argc, char **argv)
>  	 * thread from the point of view of resize.
>  	 */
>  	rcu_register_thread();
> -	test_ht = cds_lfht_new(test_hash, test_compare, TEST_HASH_SEED,
> +	test_ht = cds_lfht_new(test_compare,
>  			init_hash_size, min_hash_alloc_size,
>  			(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
>  			CDS_LFHT_ACCOUNTING, NULL);
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index d4c9209..cd5760e 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -47,12 +47,6 @@ struct _cds_lfht_node {
>  } __attribute__((aligned(4)));
>  
>  /*
> - * cds_lfht_node: Contains the full key and length required to check for
> - * an actual match, and also contains an rcu_head structure that is used
> - * by RCU to track a node through a given RCU grace period.  There is an
> - * instance of _cds_lfht_node enclosed as a field within each
> - * _cds_lfht_node structure.
> - *
>   * struct cds_lfht_node can be embedded into a structure (as a field).
>   * caa_container_of() can be used to get the structure from the struct
>   * cds_lfht_node after a lookup.
> @@ -60,8 +54,6 @@ struct _cds_lfht_node {
>  struct cds_lfht_node {
>  	/* cache-hot for iteration */
>  	struct _cds_lfht_node p;          /* needs to be first field */
> -	void *key;
> -	unsigned int key_len;
>  };
>  
>  /* cds_lfht_iter: Used to track state while traversing a hash chain. */
> @@ -82,24 +74,11 @@ struct cds_lfht;
>   * Ensure reader and writer threads are registered as urcu readers.
>   */
>  
> -typedef unsigned long (*cds_lfht_hash_fct)(void *key, size_t length,
> -					unsigned long seed);
>  typedef int (*cds_lfht_compare_fct)(struct cds_lfht_node *a,
>  		struct cds_lfht_node *b);
>  typedef int (*cds_lfht_lookup_fct)(struct cds_lfht_node *node, void *arg);
>  
>  /*
> - * cds_lfht_node_init - initialize a hash table node
> - */
> -static inline
> -void cds_lfht_node_init(struct cds_lfht_node *node, void *key,
> -			size_t key_len)
> -{
> -	node->key = key;
> -	node->key_len = key_len;
> -}
> -
> -/*
>   * Hash table creation flags.
>   */
>  enum {
> @@ -110,9 +89,7 @@ enum {
>  /*
>   * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
>   */
> -struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
> -			cds_lfht_compare_fct compare_fct,
> -			unsigned long hash_seed,
> +struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
>  			unsigned long init_size,
>  			unsigned long min_alloc_size,
>  			int flags,
> @@ -129,9 +106,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>  
>  /*
>   * cds_lfht_new - allocate a hash table.
> - * @hash_fct: the hashing function.
>   * @compare_fct: the key comparison function.
> - * @hash_seed: the seed for hash function.
>   * @init_size: number of nodes to allocate initially. Must be power of two.
>   * @min_alloc_size: the smallest allocation size to use. Must be power of two.
>   * @flags: hash table creation flags (can be combined with bitwise or: '|').
> @@ -152,15 +127,13 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct,
>   * Threads calling this API need to be registered RCU read-side threads.
>   */
>  static inline
> -struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
> -			cds_lfht_compare_fct compare_fct,
> -			unsigned long hash_seed,
> +struct cds_lfht *cds_lfht_new(cds_lfht_compare_fct compare_fct,
>  			unsigned long init_size,
>  			unsigned long min_alloc_size,
>  			int flags,
>  			pthread_attr_t *attr)
>  {
> -	return _cds_lfht_new(hash_fct, compare_fct, hash_seed,
> +	return _cds_lfht_new(compare_fct,
>  			init_size, min_alloc_size, flags,
>  			call_rcu, synchronize_rcu, rcu_read_lock,
>  			rcu_read_unlock, rcu_thread_offline,
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 6/7] rculfhash: Move key out of struct lfht_test_node

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Make struct lfht_test_node only contains basic field.
> Let user take the responsibility to handle the <key>(hash_set)
> or <key,value>(hash_map) management and calculation.
> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
[...]
> @@ -424,13 +427,18 @@ int __test_compare(void *key1, size_t key1_len,
>  static
>  int test_compare(struct cds_lfht_node *a, struct cds_lfht_node *b)
>  {
> -	return __test_compare(a->key, a->key_len, b->key, b->key_len);
> +	struct lfht_test_node *u = to_test_node(a);
> +	struct lfht_test_node *v = to_test_node(a);
> +
> +	return __test_compare(u->key, u->key_len, v->key, v->key_len);
>  }
>  

FYI, I think you had a tiny bug here (a -> b for the second). I've
replaced this patch with my own implementation, so it's not a problem.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 6/7] rculfhash: Move key out of struct lfht_test_node

[Mathieu Desnoyers]

I folded patches 6-7 and rebased them, for the following commit:

commit 04db56f85e2cd2abb05e4ef14990e99a1058d0df
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Sat Nov 5 09:48:18 2011 -0400

    rculfhash: Move key out of struct lfht_test_node, move key_len to caller
    
    Make struct lfht_test_node only contains basic field.
    Let user take the responsibility to handle the <key>(hash_set)
    or <key,value>(hash_map) management and calculation.
    
    [ Edit by Mathieu Desnoyers: rebased on top of commit
      0422d92c2d658f6093b8209f75808efd2109a110 ]
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index e5c91b9..7e81650 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -245,7 +245,7 @@ struct ht_items_count {
  */
 struct rcu_level {
 	/* Note: manually update allocation length when adding a field */
-	struct _cds_lfht_node nodes[0];
+	struct cds_lfht_node nodes[0];
 };
 
 /*
@@ -318,6 +318,7 @@ struct partition_resize_work {
 static
 void _cds_lfht_add(struct cds_lfht *ht,
 		cds_lfht_match_fct match,
+		void *key,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
@@ -755,7 +756,7 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
 }
 
 static
-struct _cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
+struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
 		unsigned long hash)
 {
 	unsigned long index, order;
@@ -794,9 +795,9 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 	for (;;) {
 		iter_prev = dummy;
 		/* We can always skip the dummy node initially */
-		iter = rcu_dereference(iter_prev->p.next);
+		iter = rcu_dereference(iter_prev->next);
 		assert(!is_removed(iter));
-		assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
+		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		/*
 		 * We should never be called with dummy (start of chain)
 		 * and logically removed node (end of path compression
@@ -807,9 +808,9 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 		for (;;) {
 			if (caa_unlikely(is_end(iter)))
 				return;
-			if (caa_likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
+			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
 				return;
-			next = rcu_dereference(clear_flag(iter)->p.next);
+			next = rcu_dereference(clear_flag(iter)->next);
 			if (caa_likely(is_removed(next)))
 				break;
 			iter_prev = clear_flag(iter);
@@ -820,7 +821,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 			new_next = flag_dummy(clear_flag(next));
 		else
 			new_next = clear_flag(next);
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
+		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 	}
 	return;
 }
@@ -831,8 +832,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		struct cds_lfht_node *old_next,
 		struct cds_lfht_node *new_node)
 {
-	struct cds_lfht_node *dummy, *ret_next;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket, *ret_next;
 
 	if (!old_node)	/* Return -ENOENT if asked to replace NULL node */
 		return -ENOENT;
@@ -853,7 +853,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		}
 		assert(!is_dummy(old_next));
 		assert(new_node != clear_flag(old_next));
-		new_node->p.next = clear_flag(old_next);
+		new_node->next = clear_flag(old_next);
 		/*
 		 * Here is the whole trick for lock-free replace: we add
 		 * the replacement node _after_ the node we want to
@@ -864,7 +864,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		 * to the removal flag and see the new node, or use
 		 * the old node, but will not see the new one.
 		 */
-		ret_next = uatomic_cmpxchg(&old_node->p.next,
+		ret_next = uatomic_cmpxchg(&old_node->next,
 			      old_next, flag_removed(new_node));
 		if (ret_next == old_next)
 			break;		/* We performed the replacement. */
@@ -876,11 +876,10 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 	 * lookup for the node, and remove it (along with any other
 	 * logically removed node) if found.
 	 */
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(old_node->p.reverse_hash));
-	dummy = (struct cds_lfht_node *) lookup;
-	_cds_lfht_gc_bucket(dummy, new_node);
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(old_node->reverse_hash));
+	_cds_lfht_gc_bucket(bucket, new_node);
 
-	assert(is_removed(rcu_dereference(old_node->p.next)));
+	assert(is_removed(rcu_dereference(old_node->next)));
 	return 0;
 }
 
@@ -891,6 +890,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 static
 void _cds_lfht_add(struct cds_lfht *ht,
 		cds_lfht_match_fct match,
+		void *key,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
@@ -898,11 +898,11 @@ void _cds_lfht_add(struct cds_lfht *ht,
 {
 	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
 			*return_node;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket;
 
 	assert(!is_dummy(node));
 	assert(!is_removed(node));
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
 	for (;;) {
 		uint32_t chain_len = 0;
 
@@ -910,28 +910,28 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		 * iter_prev points to the non-removed node prior to the
 		 * insert location.
 		 */
-		iter_prev = (struct cds_lfht_node *) lookup;
+		iter_prev = bucket;
 		/* We can always skip the dummy node initially */
-		iter = rcu_dereference(iter_prev->p.next);
-		assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
+		iter = rcu_dereference(iter_prev->next);
+		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		for (;;) {
 			if (caa_unlikely(is_end(iter)))
 				goto insert;
-			if (caa_likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
+			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
 				goto insert;
 
 			/* dummy node is the first node of the identical-hash-value chain */
-			if (dummy && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash)
+			if (dummy && clear_flag(iter)->reverse_hash == node->reverse_hash)
 				goto insert;
 
-			next = rcu_dereference(clear_flag(iter)->p.next);
+			next = rcu_dereference(clear_flag(iter)->next);
 			if (caa_unlikely(is_removed(next)))
 				goto gc_node;
 
 			/* uniquely add */
 			if (unique_ret
 			    && !is_dummy(next)
-			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) {
+			    && clear_flag(iter)->reverse_hash == node->reverse_hash) {
 				struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
 
 				/*
@@ -943,7 +943,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 				 * (including observe one node by one node
 				 * by forward iterations)
 				 */
-				cds_lfht_next_duplicate(ht, match, &d_iter);
+				cds_lfht_next_duplicate(ht, match, key, &d_iter);
 				if (!d_iter.node)
 					goto insert;
 
@@ -952,7 +952,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 			}
 
 			/* Only account for identical reverse hash once */
-			if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
+			if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash
 			    && !is_dummy(next))
 				check_resize(ht, size, ++chain_len);
 			iter_prev = clear_flag(iter);
@@ -965,14 +965,14 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		assert(!is_removed(iter));
 		assert(iter_prev != node);
 		if (!dummy)
-			node->p.next = clear_flag(iter);
+			node->next = clear_flag(iter);
 		else
-			node->p.next = flag_dummy(clear_flag(iter));
+			node->next = flag_dummy(clear_flag(iter));
 		if (is_dummy(iter))
 			new_node = flag_dummy(node);
 		else
 			new_node = node;
-		if (uatomic_cmpxchg(&iter_prev->p.next, iter,
+		if (uatomic_cmpxchg(&iter_prev->next, iter,
 				    new_node) != iter) {
 			continue;	/* retry */
 		} else {
@@ -986,7 +986,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 			new_next = flag_dummy(clear_flag(next));
 		else
 			new_next = clear_flag(next);
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
+		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 		/* retry */
 	}
 end:
@@ -1001,8 +1001,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		struct cds_lfht_node *node,
 		int dummy_removal)
 {
-	struct cds_lfht_node *dummy, *next, *old;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket, *next, *old;
 
 	if (!node)	/* Return -ENOENT if asked to delete NULL node */
 		return -ENOENT;
@@ -1010,7 +1009,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	/* logically delete the node */
 	assert(!is_dummy(node));
 	assert(!is_removed(node));
-	old = rcu_dereference(node->p.next);
+	old = rcu_dereference(node->next);
 	do {
 		struct cds_lfht_node *new_next;
 
@@ -1022,7 +1021,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		else
 			assert(!is_dummy(next));
 		new_next = flag_removed(next);
-		old = uatomic_cmpxchg(&node->p.next, next, new_next);
+		old = uatomic_cmpxchg(&node->next, next, new_next);
 	} while (old != next);
 	/* We performed the (logical) deletion. */
 
@@ -1031,11 +1030,10 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	 * the node, and remove it (along with any other logically removed node)
 	 * if found.
 	 */
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
-	dummy = (struct cds_lfht_node *) lookup;
-	_cds_lfht_gc_bucket(dummy, node);
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
+	_cds_lfht_gc_bucket(bucket, node);
 
-	assert(is_removed(rcu_dereference(node->p.next)));
+	assert(is_removed(rcu_dereference(node->next)));
 	return 0;
 }
 
@@ -1112,14 +1110,13 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
 	assert(i > ht->min_alloc_order);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = start; j < start + len; j++) {
-		struct cds_lfht_node *new_node =
-			(struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+		struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
 
 		dbg_printf("init populate: i %lu j %lu hash %lu\n",
 			   i, j, (1UL << (i - 1)) + j);
-		new_node->p.reverse_hash =
+		new_node->reverse_hash =
 				bit_reverse_ulong((1UL << (i - 1)) + j);
-		_cds_lfht_add(ht, NULL, 1UL << (i - 1),
+		_cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1),
 				new_node, NULL, 1);
 	}
 	ht->cds_lfht_rcu_read_unlock();
@@ -1158,7 +1155,7 @@ void init_table(struct cds_lfht *ht,
 		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
 			break;
 
-		ht->t.tbl[i] = calloc(1, len * sizeof(struct _cds_lfht_node));
+		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
 		assert(ht->t.tbl[i]);
 
 		/*
@@ -1213,12 +1210,11 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
 	assert(i > ht->min_alloc_order);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = start; j < start + len; j++) {
-		struct cds_lfht_node *fini_node =
-			(struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+		struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
 
 		dbg_printf("remove entry: i %lu j %lu hash %lu\n",
 			   i, j, (1UL << (i - 1)) + j);
-		fini_node->p.reverse_hash =
+		fini_node->reverse_hash =
 			bit_reverse_ulong((1UL << (i - 1)) + j);
 		(void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
 	}
@@ -1296,10 +1292,10 @@ void fini_table(struct cds_lfht *ht,
 static
 void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 {
-	struct _cds_lfht_node *prev, *node;
+	struct cds_lfht_node *prev, *node;
 	unsigned long order, len, i, j;
 
-	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct _cds_lfht_node));
+	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
 	assert(ht->t.tbl[0]);
 
 	dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0);
@@ -1311,7 +1307,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 		if (order <= ht->min_alloc_order) {
 			ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
 		} else {
-			ht->t.tbl[order] = calloc(1, len * sizeof(struct _cds_lfht_node));
+			ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
 			assert(ht->t.tbl[order]);
 		}
 
@@ -1331,7 +1327,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 			node->next = prev->next;
 			assert(is_dummy(node->next));
 			node->reverse_hash = bit_reverse_ulong(j + len);
-			prev->next = flag_dummy((struct cds_lfht_node *)node);
+			prev->next = flag_dummy(node);
 		}
 	}
 }
@@ -1388,52 +1384,48 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
 		unsigned long hash, void *key, struct cds_lfht_iter *iter)
 {
-	struct cds_lfht_node *node, *next, *dummy_node;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *node, *next, *bucket;
 	unsigned long reverse_hash, size;
 
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
-	lookup = lookup_bucket(ht, size, hash);
-	dummy_node = (struct cds_lfht_node *) lookup;
+	bucket = lookup_bucket(ht, size, hash);
 	/* We can always skip the dummy node initially */
-	node = rcu_dereference(dummy_node->p.next);
+	node = rcu_dereference(bucket->next);
 	node = clear_flag(node);
 	for (;;) {
 		if (caa_unlikely(is_end(node))) {
 			node = next = NULL;
 			break;
 		}
-		if (caa_unlikely(node->p.reverse_hash > reverse_hash)) {
+		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		assert(node == clear_flag(node));
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
-		    && node->p.reverse_hash == reverse_hash
+		    && node->reverse_hash == reverse_hash
 		    && caa_likely(match(node, key))) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
 
 void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
-		struct cds_lfht_iter *iter)
+		void *key, struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next;
 	unsigned long reverse_hash;
-	void *key;
 
 	node = iter->node;
-	reverse_hash = node->p.reverse_hash;
-	key = node->key;
+	reverse_hash = node->reverse_hash;
 	next = iter->next;
 	node = clear_flag(next);
 
@@ -1442,19 +1434,19 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
 			node = next = NULL;
 			break;
 		}
-		if (caa_unlikely(node->p.reverse_hash > reverse_hash)) {
+		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
-		    && caa_likely(match(node->key, key))) {
+		    && caa_likely(match(node, key))) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1469,21 +1461,21 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
 
 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *lookup;
 
 	/*
 	 * Get next after first dummy node. The first dummy node is the
@@ -1499,23 +1491,24 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 {
 	unsigned long size;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 	size = rcu_dereference(ht->t.size);
-	_cds_lfht_add(ht, NULL, size, node, NULL, 0);
+	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
 	ht_count_add(ht, size, hash);
 }
 
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 				cds_lfht_match_fct match,
+				void *key,
 				unsigned long hash,
 				struct cds_lfht_node *node)
 {
 	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 	size = rcu_dereference(ht->t.size);
-	_cds_lfht_add(ht, match, size, node, &iter, 0);
+	_cds_lfht_add(ht, match, key, size, node, &iter, 0);
 	if (iter.node == node)
 		ht_count_add(ht, size, hash);
 	return iter.node;
@@ -1523,16 +1516,17 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 				cds_lfht_match_fct match,
+				void *key,
 				unsigned long hash,
 				struct cds_lfht_node *node)
 {
 	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 	size = rcu_dereference(ht->t.size);
 	for (;;) {
-		_cds_lfht_add(ht, match, size, node, &iter, 0);
+		_cds_lfht_add(ht, match, key, size, node, &iter, 0);
 		if (iter.node == node) {
 			ht_count_add(ht, size, hash);
 			return NULL;
@@ -1561,7 +1555,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	size = rcu_dereference(ht->t.size);
 	ret = _cds_lfht_del(ht, size, iter->node, 0);
 	if (!ret) {
-		hash = bit_reverse_ulong(iter->node->p.reverse_hash);
+		hash = bit_reverse_ulong(iter->node->reverse_hash);
 		ht_count_del(ht, size, hash);
 	}
 	return ret;
@@ -1571,14 +1565,12 @@ static
 int cds_lfht_delete_dummy(struct cds_lfht *ht)
 {
 	struct cds_lfht_node *node;
-	struct _cds_lfht_node *lookup;
 	unsigned long order, i, size;
 
 	/* Check that the table is empty */
-	lookup = &ht->t.tbl[0]->nodes[0];
-	node = (struct cds_lfht_node *) lookup;
+	node = &ht->t.tbl[0]->nodes[0];
 	do {
-		node = clear_flag(node)->p.next;
+		node = clear_flag(node)->next;
 		if (!is_dummy(node))
 			return -EPERM;
 		assert(!is_removed(node));
@@ -1639,7 +1631,6 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 		long *approx_after)
 {
 	struct cds_lfht_node *node, *next;
-	struct _cds_lfht_node *lookup;
 	unsigned long nr_dummy = 0;
 
 	*approx_before = 0;
@@ -1656,10 +1647,9 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 	*removed = 0;
 
 	/* Count non-dummy nodes in the table */
-	lookup = &ht->t.tbl[0]->nodes[0];
-	node = (struct cds_lfht_node *) lookup;
+	node = &ht->t.tbl[0]->nodes[0];
 	do {
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (is_removed(next)) {
 			if (!is_dummy(next))
 				(*removed)++;
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 3111353..87c4ad1 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -109,6 +109,8 @@ struct test_data {
 
 struct lfht_test_node {
 	struct cds_lfht_node node;
+	void *key;
+	unsigned int key_len;
 	/* cache-cold for iteration */
 	struct rcu_head head;
 };
@@ -123,7 +125,9 @@ static inline
 void lfht_test_node_init(struct lfht_test_node *node, void *key,
 			size_t key_len)
 {
-	cds_lfht_node_init(&node->node, key, key_len);
+	cds_lfht_node_init(&node->node);
+	node->key = key;
+	node->key_len = key_len;
 }
 
 static inline struct lfht_test_node *
@@ -422,10 +426,12 @@ unsigned long test_compare(void *key1, size_t key1_len,
 }
 
 static
-int test_match(struct cds_lfht_node *node, void *arg)
+int test_match(struct cds_lfht_node *node, void *key)
 {
-	return !test_compare(node->key, node->key_len,
-			arg, sizeof(unsigned long));
+	struct lfht_test_node *test_node = to_test_node(node);
+
+	return !test_compare(test_node->key, test_node->key_len,
+			key, sizeof(unsigned long));
 }
 
 static
@@ -571,17 +577,17 @@ void *thr_writer(void *_count)
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, test_match,
-					test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+				ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
+					test_hash(node->key, node->key_len, TEST_HASH_SEED),
 					&node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, test_match,
-							test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+					ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
+							test_hash(node->key, node->key_len, TEST_HASH_SEED),
 							&node->node);
 				else
 					cds_lfht_add(test_ht,
-						test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+						test_hash(node->key, node->key_len, TEST_HASH_SEED),
 						&node->node);
 			}
 			rcu_read_unlock();
@@ -668,17 +674,17 @@ static int populate_hash(void)
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, test_match,
-				test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+			ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
+				test_hash(node->key, node->key_len, TEST_HASH_SEED),
 				&node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, test_match,
-						test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+				ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
+						test_hash(node->key, node->key_len, TEST_HASH_SEED),
 						&node->node);
 			else
 				cds_lfht_add(test_ht,
-					test_hash(node->node.key, node->node.key_len, TEST_HASH_SEED),
+					test_hash(node->key, node->key_len, TEST_HASH_SEED),
 					&node->node);
 		}
 		rcu_read_unlock();
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 9dcaf02..a1ae0f5 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -32,37 +32,26 @@
 extern "C" {
 #endif
 
-/*
- * struct cds_lfht_node and struct _cds_lfht_node should be aligned on
- * 4-bytes boundaries because the two lower bits are used as flags.
- */
 
 /*
- * _cds_lfht_node: Contains the internal pointers and reverse-hash
+ * cds_lfht_node: Contains the next pointers and reverse-hash
  * value required for lookup and traversal of the hash table.
- */
-struct _cds_lfht_node {
-	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
-	unsigned long reverse_hash;
-} __attribute__((aligned(4)));
-
-/*
- * cds_lfht_node: Contains the full key and length required to check for
- * an actual match, and also contains an rcu_head structure that is used
- * by RCU to track a node through a given RCU grace period.  There is an
- * instance of _cds_lfht_node enclosed as a field within each
- * _cds_lfht_node structure.
+ *
+ * struct cds_lfht_node should be aligned on 4-bytes boundaries because
+ * the two lower bits are used as flags.
  *
  * struct cds_lfht_node can be embedded into a structure (as a field).
  * caa_container_of() can be used to get the structure from the struct
  * cds_lfht_node after a lookup.
+ *
+ * The structure which embeds it typically holds the key (or key-value
+ * pair) of the object. The caller code is responsible for calculation
+ * of the hash value for cds_lfht APIs.
  */
 struct cds_lfht_node {
-	/* cache-hot for iteration */
-	struct _cds_lfht_node p;          /* needs to be first field */
-	void *key;
-	unsigned int key_len;
-};
+	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
+	unsigned long reverse_hash;
+} __attribute__((aligned(4)));
 
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
 struct cds_lfht_iter {
@@ -89,15 +78,13 @@ typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, void *key);
 /*
  * cds_lfht_node_init - initialize a hash table node
  * @node: the node to initialize.
- * @key: pointer to the key to use.
- * @key_len: the length of the key, in bytes.
+ *
+ * This function is kept to be eventually used for debugging purposes
+ * (detection of memory corruption).
  */
 static inline
-void cds_lfht_node_init(struct cds_lfht_node *node, void *key,
-			size_t key_len)
+void cds_lfht_node_init(struct cds_lfht_node *node)
 {
-	node->key = key;
-	node->key_len = key_len;
 }
 
 /*
@@ -206,6 +193,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
  * cds_lfht_next_duplicate - get the next item with same key (after a lookup).
  * @ht: the hash table.
  * @match: the key match function.
+ * @key: the current node key.
  * @iter: Node, if found (output). *iter->node set to NULL if not found.
  *
  * Uses an iterator initialized by a lookup.
@@ -218,7 +206,8 @@ void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
  * Threads calling this API need to be registered RCU read-side threads.
  */
 void cds_lfht_next_duplicate(struct cds_lfht *ht,
-		cds_lfht_match_fct match, struct cds_lfht_iter *iter);
+		cds_lfht_match_fct match, void *key,
+		struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_first - get the first node in the table.
@@ -260,6 +249,8 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
  * cds_lfht_add_unique - add a node to hash table, if key is not present.
  * @ht: the hash table.
  * @match: the key match function.
+ * @key: the node's key.
+ * @hash: the node's hash.
  * @node: the node to try adding.
  *
  * Return the node added upon success.
@@ -276,6 +267,7 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
  */
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 		cds_lfht_match_fct match,
+		void *key,
 		unsigned long hash,
 		struct cds_lfht_node *node);
 
@@ -283,6 +275,8 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
  * cds_lfht_add_replace - replace or add a node within hash table.
  * @ht: the hash table.
  * @match: the key match function.
+ * @key: the node's key.
+ * @hash: the node's hash.
  * @node: the node to add.
  *
  * Return the node replaced upon success. If no node matching the key
@@ -305,6 +299,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
  */
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 		cds_lfht_match_fct match,
+		void *key,
 		unsigned long hash,
 		struct cds_lfht_node *node);
 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 7/7] rculfhash: cleanup struct _cds_lfht_node

[Lai Jiangshan]

Remove struct _cds_lfht_node and move its fields to struct cds_lfht_node.

It is the last patch of this series. It makes struct cds_lfht_node
only contains basic field. All other things(key, key-value, hash-calculation,
allocation, deallocation) are become user's responsibility.

It make cds_lfht act as a sanity hash table,
not an incomplete hash_set nor hash_map.

The structure which embeds struct cds_lfht_node must takes the responsibility
to manage the key (or key-value pair) of the object and calculate
the hash value for cds_lfht APIs.

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c      |  140 +++++++++++++++++++++++++-----------------------------
 urcu/rculfhash.h |   28 +++++------
 2 files changed, 76 insertions(+), 92 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index a569172..86b234f 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -245,7 +245,7 @@ struct ht_items_count {
  */
 struct rcu_level {
 	/* Note: manually update allocation length when adding a field */
-	struct _cds_lfht_node nodes[0];
+	struct cds_lfht_node nodes[0];
 };
 
 /*
@@ -754,7 +754,7 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
 }
 
 static
-struct _cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
+struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
 		unsigned long hash)
 {
 	unsigned long index, order;
@@ -793,9 +793,9 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 	for (;;) {
 		iter_prev = dummy;
 		/* We can always skip the dummy node initially */
-		iter = rcu_dereference(iter_prev->p.next);
+		iter = rcu_dereference(iter_prev->next);
 		assert(!is_removed(iter));
-		assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
+		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		/*
 		 * We should never be called with dummy (start of chain)
 		 * and logically removed node (end of path compression
@@ -806,9 +806,9 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 		for (;;) {
 			if (caa_unlikely(is_end(iter)))
 				return;
-			if (caa_likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
+			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
 				return;
-			next = rcu_dereference(clear_flag(iter)->p.next);
+			next = rcu_dereference(clear_flag(iter)->next);
 			if (caa_likely(is_removed(next)))
 				break;
 			iter_prev = clear_flag(iter);
@@ -819,7 +819,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 			new_next = flag_dummy(clear_flag(next));
 		else
 			new_next = clear_flag(next);
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
+		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 	}
 	return;
 }
@@ -830,8 +830,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		struct cds_lfht_node *old_next,
 		struct cds_lfht_node *new_node)
 {
-	struct cds_lfht_node *dummy, *ret_next;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket, *ret_next;
 
 	if (!old_node)	/* Return -ENOENT if asked to replace NULL node */
 		return -ENOENT;
@@ -852,7 +851,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		}
 		assert(!is_dummy(old_next));
 		assert(new_node != clear_flag(old_next));
-		new_node->p.next = clear_flag(old_next);
+		new_node->next = clear_flag(old_next);
 		/*
 		 * Here is the whole trick for lock-free replace: we add
 		 * the replacement node _after_ the node we want to
@@ -863,7 +862,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		 * to the removal flag and see the new node, or use
 		 * the old node, but will not see the new one.
 		 */
-		ret_next = uatomic_cmpxchg(&old_node->p.next,
+		ret_next = uatomic_cmpxchg(&old_node->next,
 			      old_next, flag_removed(new_node));
 		if (ret_next == old_next)
 			break;		/* We performed the replacement. */
@@ -875,11 +874,10 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 	 * lookup for the node, and remove it (along with any other
 	 * logically removed node) if found.
 	 */
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(old_node->p.reverse_hash));
-	dummy = (struct cds_lfht_node *) lookup;
-	_cds_lfht_gc_bucket(dummy, new_node);
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(old_node->reverse_hash));
+	_cds_lfht_gc_bucket(bucket, new_node);
 
-	assert(is_removed(rcu_dereference(old_node->p.next)));
+	assert(is_removed(rcu_dereference(old_node->next)));
 	return 0;
 }
 
@@ -896,11 +894,11 @@ void _cds_lfht_add(struct cds_lfht *ht,
 {
 	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
 			*return_node;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket;
 
 	assert(!is_dummy(node));
 	assert(!is_removed(node));
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
 	for (;;) {
 		uint32_t chain_len = 0;
 
@@ -908,28 +906,28 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		 * iter_prev points to the non-removed node prior to the
 		 * insert location.
 		 */
-		iter_prev = (struct cds_lfht_node *) lookup;
+		iter_prev = bucket;
 		/* We can always skip the dummy node initially */
-		iter = rcu_dereference(iter_prev->p.next);
-		assert(iter_prev->p.reverse_hash <= node->p.reverse_hash);
+		iter = rcu_dereference(iter_prev->next);
+		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		for (;;) {
 			if (caa_unlikely(is_end(iter)))
 				goto insert;
-			if (caa_likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
+			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
 				goto insert;
 
 			/* dummy node is the first node of the identical-hash-value chain */
-			if (dummy && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash)
+			if (dummy && clear_flag(iter)->reverse_hash == node->reverse_hash)
 				goto insert;
 
-			next = rcu_dereference(clear_flag(iter)->p.next);
+			next = rcu_dereference(clear_flag(iter)->next);
 			if (caa_unlikely(is_removed(next)))
 				goto gc_node;
 
 			/* uniquely add */
 			if (unique_ret
 			    && !is_dummy(next)
-			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) {
+			    && clear_flag(iter)->reverse_hash == node->reverse_hash) {
 				struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
 
 				/*
@@ -950,7 +948,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 			}
 
 			/* Only account for identical reverse hash once */
-			if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
+			if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash
 			    && !is_dummy(next))
 				check_resize(ht, size, ++chain_len);
 			iter_prev = clear_flag(iter);
@@ -963,14 +961,14 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		assert(!is_removed(iter));
 		assert(iter_prev != node);
 		if (!dummy)
-			node->p.next = clear_flag(iter);
+			node->next = clear_flag(iter);
 		else
-			node->p.next = flag_dummy(clear_flag(iter));
+			node->next = flag_dummy(clear_flag(iter));
 		if (is_dummy(iter))
 			new_node = flag_dummy(node);
 		else
 			new_node = node;
-		if (uatomic_cmpxchg(&iter_prev->p.next, iter,
+		if (uatomic_cmpxchg(&iter_prev->next, iter,
 				    new_node) != iter) {
 			continue;	/* retry */
 		} else {
@@ -984,7 +982,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 			new_next = flag_dummy(clear_flag(next));
 		else
 			new_next = clear_flag(next);
-		(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
+		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 		/* retry */
 	}
 end:
@@ -999,8 +997,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		struct cds_lfht_node *node,
 		int dummy_removal)
 {
-	struct cds_lfht_node *dummy, *next, *old;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *bucket, *next, *old;
 
 	if (!node)	/* Return -ENOENT if asked to delete NULL node */
 		return -ENOENT;
@@ -1008,7 +1005,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	/* logically delete the node */
 	assert(!is_dummy(node));
 	assert(!is_removed(node));
-	old = rcu_dereference(node->p.next);
+	old = rcu_dereference(node->next);
 	do {
 		struct cds_lfht_node *new_next;
 
@@ -1020,7 +1017,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		else
 			assert(!is_dummy(next));
 		new_next = flag_removed(next);
-		old = uatomic_cmpxchg(&node->p.next, next, new_next);
+		old = uatomic_cmpxchg(&node->next, next, new_next);
 	} while (old != next);
 	/* We performed the (logical) deletion. */
 
@@ -1029,11 +1026,10 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 	 * the node, and remove it (along with any other logically removed node)
 	 * if found.
 	 */
-	lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
-	dummy = (struct cds_lfht_node *) lookup;
-	_cds_lfht_gc_bucket(dummy, node);
+	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
+	_cds_lfht_gc_bucket(bucket, node);
 
-	assert(is_removed(rcu_dereference(node->p.next)));
+	assert(is_removed(rcu_dereference(node->next)));
 	return 0;
 }
 
@@ -1110,12 +1106,11 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
 	assert(i > ht->min_alloc_order);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = start; j < start + len; j++) {
-		struct cds_lfht_node *new_node =
-			(struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+		struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
 
 		dbg_printf("init populate: i %lu j %lu hash %lu\n",
 			   i, j, (1UL << (i - 1)) + j);
-		new_node->p.reverse_hash =
+		new_node->reverse_hash =
 				bit_reverse_ulong((1UL << (i - 1)) + j);
 		_cds_lfht_add(ht, 1UL << (i - 1),
 				new_node, NULL, 1);
@@ -1156,7 +1151,7 @@ void init_table(struct cds_lfht *ht,
 		if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
 			break;
 
-		ht->t.tbl[i] = calloc(1, len * sizeof(struct _cds_lfht_node));
+		ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
 		assert(ht->t.tbl[i]);
 
 		/*
@@ -1211,12 +1206,11 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
 	assert(i > ht->min_alloc_order);
 	ht->cds_lfht_rcu_read_lock();
 	for (j = start; j < start + len; j++) {
-		struct cds_lfht_node *fini_node =
-			(struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
+		struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
 
 		dbg_printf("remove entry: i %lu j %lu hash %lu\n",
 			   i, j, (1UL << (i - 1)) + j);
-		fini_node->p.reverse_hash =
+		fini_node->reverse_hash =
 			bit_reverse_ulong((1UL << (i - 1)) + j);
 		(void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
 	}
@@ -1294,10 +1288,10 @@ void fini_table(struct cds_lfht *ht,
 static
 void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 {
-	struct _cds_lfht_node *prev, *node;
+	struct cds_lfht_node *prev, *node;
 	unsigned long order, len, i, j;
 
-	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct _cds_lfht_node));
+	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
 	assert(ht->t.tbl[0]);
 
 	dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0);
@@ -1309,7 +1303,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 		if (order <= ht->min_alloc_order) {
 			ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
 		} else {
-			ht->t.tbl[order] = calloc(1, len * sizeof(struct _cds_lfht_node));
+			ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
 			assert(ht->t.tbl[order]);
 		}
 
@@ -1329,7 +1323,7 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 			node->next = prev->next;
 			assert(is_dummy(node->next));
 			node->reverse_hash = bit_reverse_ulong(j + len);
-			prev->next = flag_dummy((struct cds_lfht_node *)node);
+			prev->next = flag_dummy(node);
 		}
 	}
 }
@@ -1389,38 +1383,36 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		cds_lfht_lookup_fct match, void *arg,
 		struct cds_lfht_iter *iter)
 {
-	struct cds_lfht_node *node, *next, *dummy_node;
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *node, *next, *bucket;
 	unsigned long reverse_hash, size;
 
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
-	lookup = lookup_bucket(ht, size, hash);
-	dummy_node = (struct cds_lfht_node *) lookup;
+	bucket = lookup_bucket(ht, size, hash);
 	/* We can always skip the dummy node initially */
-	node = rcu_dereference(dummy_node->p.next);
+	node = rcu_dereference(bucket->next);
 	node = clear_flag(node);
 	for (;;) {
 		if (caa_unlikely(is_end(node))) {
 			node = next = NULL;
 			break;
 		}
-		if (caa_unlikely(node->p.reverse_hash > reverse_hash)) {
+		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		assert(node == clear_flag(node));
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
-		    && node->p.reverse_hash == reverse_hash
+		    && node->reverse_hash == reverse_hash
 		    && caa_likely(match(node, arg))) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1431,7 +1423,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	unsigned long reverse_hash;
 
 	node = iter->node;
-	reverse_hash = node->p.reverse_hash;
+	reverse_hash = node->reverse_hash;
 	next = iter->next;
 	node = clear_flag(next);
 
@@ -1440,11 +1432,11 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 			node = next = NULL;
 			break;
 		}
-		if (caa_unlikely(node->p.reverse_hash > reverse_hash)) {
+		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)
 		    && caa_likely(!ht->compare_fct(node, iter->node))) {
@@ -1452,7 +1444,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1467,21 +1459,21 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 			node = next = NULL;
 			break;
 		}
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
 		    && !is_dummy(next)) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->p.next)));
+	assert(!node || !is_dummy(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
 
 void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 {
-	struct _cds_lfht_node *lookup;
+	struct cds_lfht_node *lookup;
 
 	/*
 	 * Get next after first dummy node. The first dummy node is the
@@ -1497,7 +1489,7 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 {
 	unsigned long size;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
 	_cds_lfht_add(ht, size, node, NULL, 0);
@@ -1510,7 +1502,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
 	_cds_lfht_add(ht, size, node, &iter, 0);
@@ -1525,7 +1517,7 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
 	unsigned long size;
 	struct cds_lfht_iter iter;
 
-	node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	size = rcu_dereference(ht->t.size);
 	for (;;) {
@@ -1558,7 +1550,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	size = rcu_dereference(ht->t.size);
 	ret = _cds_lfht_del(ht, size, iter->node, 0);
 	if (!ret) {
-		hash = bit_reverse_ulong(iter->node->p.reverse_hash);
+		hash = bit_reverse_ulong(iter->node->reverse_hash);
 		ht_count_del(ht, size, hash);
 	}
 	return ret;
@@ -1568,14 +1560,12 @@ static
 int cds_lfht_delete_dummy(struct cds_lfht *ht)
 {
 	struct cds_lfht_node *node;
-	struct _cds_lfht_node *lookup;
 	unsigned long order, i, size;
 
 	/* Check that the table is empty */
-	lookup = &ht->t.tbl[0]->nodes[0];
-	node = (struct cds_lfht_node *) lookup;
+	node = &ht->t.tbl[0]->nodes[0];
 	do {
-		node = clear_flag(node)->p.next;
+		node = clear_flag(node)->next;
 		if (!is_dummy(node))
 			return -EPERM;
 		assert(!is_removed(node));
@@ -1636,7 +1626,6 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 		long *approx_after)
 {
 	struct cds_lfht_node *node, *next;
-	struct _cds_lfht_node *lookup;
 	unsigned long nr_dummy = 0;
 
 	*approx_before = 0;
@@ -1653,10 +1642,9 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 	*removed = 0;
 
 	/* Count non-dummy nodes in the table */
-	lookup = &ht->t.tbl[0]->nodes[0];
-	node = (struct cds_lfht_node *) lookup;
+	node = &ht->t.tbl[0]->nodes[0];
 	do {
-		next = rcu_dereference(node->p.next);
+		next = rcu_dereference(node->next);
 		if (is_removed(next)) {
 			if (!is_dummy(next))
 				(*removed)++;
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index cd5760e..3e915a0 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -33,28 +33,24 @@ extern "C" {
 #endif
 
 /*
- * struct cds_lfht_node and struct _cds_lfht_node should be aligned on
- * 4-bytes boundaries because the two lower bits are used as flags.
- */
-
-/*
- * _cds_lfht_node: Contains the internal pointers and reverse-hash
+ * struct cds_lfht_node: Contains the next pointers and reverse-hash
  * value required for lookup and traversal of the hash table.
- */
-struct _cds_lfht_node {
-	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
-	unsigned long reverse_hash;
-} __attribute__((aligned(4)));
-
-/*
+ *
+ * struct cds_lfht_node should be aligned on 4-bytes boundaries
+ * because the two lower bits are used as flags.
+ *
  * struct cds_lfht_node can be embedded into a structure (as a field).
  * caa_container_of() can be used to get the structure from the struct
  * cds_lfht_node after a lookup.
+ *
+ * The structure which embeds it must takes the responsibility
+ * to manage the key (or key-value pair) of the object and calculate
+ * the hash value for cds_lfht APIs.
  */
 struct cds_lfht_node {
-	/* cache-hot for iteration */
-	struct _cds_lfht_node p;          /* needs to be first field */
-};
+	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
+	unsigned long reverse_hash;
+} __attribute__((aligned(4)));
 
 /* cds_lfht_iter: Used to track state while traversing a hash chain. */
 struct cds_lfht_iter {
-- 
1.7.4.4

[ltt-dev] [PATCH 1/2] rculfhash: rename dummy to bucket

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c      |  180 +++++++++++++++++++++++++++---------------------------
 urcu/rculfhash.h |    2 +-
 2 files changed, 91 insertions(+), 91 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 86b234f..88079f9 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -45,7 +45,7 @@
  * - The resize operation executes concurrently with add/remove/lookup.
  * - Hash table nodes are contained within a split-ordered list. This
  *   list is ordered by incrementing reversed-bits-hash value.
- * - An index of dummy nodes is kept. These dummy nodes are the hash
+ * - An index of bucket nodes is kept. These bucket nodes are the hash
  *   table "buckets", and they are also chained together in the
  *   split-ordered list, which allows recursive expansion.
  * - The resize operation for small tables only allows expanding the hash table.
@@ -74,7 +74,7 @@
  *   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 dummy node) up to the
+ *   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
@@ -88,19 +88,19 @@
  *   for it do to so.
  * - A RCU "order table" indexed by log2(hash index) is copied and
  *   expanded by the resize operation. This order table allows finding
- *   the "dummy node" tables.
- * - There is one dummy node table per hash index order. The size of
- *   each dummy node table is half the number of hashes contained in
+ *   the "bucket node" tables.
+ * - There is one bucket node table per hash index order. The size of
+ *   each bucket node table is half the number of hashes contained in
  *   this order (except for order 0).
- * - synchronzie_rcu is used to garbage-collect the old dummy node table.
- * - The per-order dummy node tables contain a compact version of the
+ * - synchronzie_rcu is used to garbage-collect the old bucket node table.
+ * - The per-order bucket node tables contain a compact version of the
  *   hash table nodes. These tables are invariant after they are
  *   populated into the hash table.
  *
- * Dummy node tables:
+ * Bucket node tables:
  *
- * hash table	hash table	the last	all dummy node tables
- * order	size		dummy node	0   1   2   3   4   5   6(index)
+ * hash table	hash table	the last	all bucket node tables
+ * order	size		bucket node	0   1   2   3   4   5   6(index)
  * 				table size
  * 0		1		1		1
  * 1		2		1		1   1
@@ -110,12 +110,12 @@
  * 5		32		16		1   1   2   4   8  16
  * 6		64		32		1   1   2   4   8  16  32
  *
- * When growing/shrinking, we only focus on the last dummy node table
+ * When growing/shrinking, we only focus on the last bucket node table
  * which size is (!order ? 1 : (1 << (order -1))).
  *
  * Example for growing/shrinking:
- * grow hash table from order 5 to 6: init the index=6 dummy node table
- * shrink hash table from order 6 to 5: fini the index=6 dummy node table
+ * grow hash table from order 5 to 6: init the index=6 bucket node table
+ * shrink hash table from order 6 to 5: fini the index=6 bucket node table
  *
  * A bit of ascii art explanation:
  * 
@@ -195,7 +195,7 @@
 #endif
 
 /*
- * Minimum number of dummy nodes to touch per thread to parallelize grow/shrink.
+ * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
  */
 #define MIN_PARTITION_PER_THREAD_ORDER	12
 #define MIN_PARTITION_PER_THREAD	(1UL << MIN_PARTITION_PER_THREAD_ORDER)
@@ -212,11 +212,11 @@
  * The removed flag needs to be updated atomically with the pointer.
  * It indicates that no node must attach to the node scheduled for
  * removal, and that node garbage collection must be performed.
- * The dummy flag does not require to be updated atomically with the
+ * The bucket flag does not require to be updated atomically with the
  * pointer, but it is added as a pointer low bit flag to save space.
  */
 #define REMOVED_FLAG		(1UL << 0)
-#define DUMMY_FLAG		(1UL << 1)
+#define BUCKET_FLAG		(1UL << 1)
 #define FLAGS_MASK		((1UL << 2) - 1)
 
 /* Value of the end pointer. Should not interact with flags. */
@@ -237,10 +237,10 @@ struct ht_items_count {
 } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
 
 /*
- * rcu_level: Contains the per order-index-level dummy node table. The
- * size of each dummy node table is half the number of hashes contained
+ * rcu_level: Contains the per order-index-level bucket node table. The
+ * size of each bucket node table is half the number of hashes contained
  * in this order (except for order 0). The minimum allocation size
- * parameter allows combining the dummy node arrays of the lowermost
+ * parameter allows combining the bucket node arrays of the lowermost
  * levels to improve cache locality for small index orders.
  */
 struct rcu_level {
@@ -321,7 +321,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
-		int dummy);
+		int bucket);
 
 /*
  * Algorithm to reverse bits in a word by lookup table, extended to
@@ -716,15 +716,15 @@ struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
 }
 
 static
-int is_dummy(struct cds_lfht_node *node)
+int is_bucket(struct cds_lfht_node *node)
 {
-	return ((unsigned long) node) & DUMMY_FLAG;
+	return ((unsigned long) node) & BUCKET_FLAG;
 }
 
 static
-struct cds_lfht_node *flag_dummy(struct cds_lfht_node *node)
+struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
 {
-	return (struct cds_lfht_node *) (((unsigned long) node) | DUMMY_FLAG);
+	return (struct cds_lfht_node *) (((unsigned long) node) | BUCKET_FLAG);
 }
 
 static
@@ -782,27 +782,27 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
  * Remove all logically deleted nodes from a bucket up to a certain node key.
  */
 static
-void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node)
+void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *node)
 {
 	struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
 
-	assert(!is_dummy(dummy));
-	assert(!is_removed(dummy));
-	assert(!is_dummy(node));
+	assert(!is_bucket(bucket));
+	assert(!is_removed(bucket));
+	assert(!is_bucket(node));
 	assert(!is_removed(node));
 	for (;;) {
-		iter_prev = dummy;
-		/* We can always skip the dummy node initially */
+		iter_prev = bucket;
+		/* We can always skip the bucket node initially */
 		iter = rcu_dereference(iter_prev->next);
 		assert(!is_removed(iter));
 		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		/*
-		 * We should never be called with dummy (start of chain)
+		 * We should never be called with bucket (start of chain)
 		 * and logically removed node (end of path compression
 		 * marker) being the actual same node. This would be a
 		 * bug in the algorithm implementation.
 		 */
-		assert(dummy != node);
+		assert(bucket != node);
 		for (;;) {
 			if (caa_unlikely(is_end(iter)))
 				return;
@@ -815,8 +815,8 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
 			iter = next;
 		}
 		assert(!is_removed(iter));
-		if (is_dummy(iter))
-			new_next = flag_dummy(clear_flag(next));
+		if (is_bucket(iter))
+			new_next = flag_bucket(clear_flag(next));
 		else
 			new_next = clear_flag(next);
 		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
@@ -836,9 +836,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 		return -ENOENT;
 
 	assert(!is_removed(old_node));
-	assert(!is_dummy(old_node));
+	assert(!is_bucket(old_node));
 	assert(!is_removed(new_node));
-	assert(!is_dummy(new_node));
+	assert(!is_bucket(new_node));
 	assert(new_node != old_node);
 	for (;;) {
 		/* Insert after node to be replaced */
@@ -849,7 +849,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 			 */
 			return -ENOENT;
 		}
-		assert(!is_dummy(old_next));
+		assert(!is_bucket(old_next));
 		assert(new_node != clear_flag(old_next));
 		new_node->next = clear_flag(old_next);
 		/*
@@ -890,13 +890,13 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
-		int dummy)
+		int bucket_flag)
 {
 	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
 			*return_node;
 	struct cds_lfht_node *bucket;
 
-	assert(!is_dummy(node));
+	assert(!is_bucket(node));
 	assert(!is_removed(node));
 	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
 	for (;;) {
@@ -907,7 +907,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		 * insert location.
 		 */
 		iter_prev = bucket;
-		/* We can always skip the dummy node initially */
+		/* We can always skip the bucket node initially */
 		iter = rcu_dereference(iter_prev->next);
 		assert(iter_prev->reverse_hash <= node->reverse_hash);
 		for (;;) {
@@ -916,8 +916,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
 			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
 				goto insert;
 
-			/* dummy node is the first node of the identical-hash-value chain */
-			if (dummy && clear_flag(iter)->reverse_hash == node->reverse_hash)
+			/* bucket node is the first node of the identical-hash-value chain */
+			if (bucket_flag && clear_flag(iter)->reverse_hash == node->reverse_hash)
 				goto insert;
 
 			next = rcu_dereference(clear_flag(iter)->next);
@@ -926,7 +926,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
 			/* uniquely add */
 			if (unique_ret
-			    && !is_dummy(next)
+			    && !is_bucket(next)
 			    && clear_flag(iter)->reverse_hash == node->reverse_hash) {
 				struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
 
@@ -949,7 +949,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
 			/* Only account for identical reverse hash once */
 			if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash
-			    && !is_dummy(next))
+			    && !is_bucket(next))
 				check_resize(ht, size, ++chain_len);
 			iter_prev = clear_flag(iter);
 			iter = next;
@@ -960,12 +960,12 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		assert(!is_removed(iter_prev));
 		assert(!is_removed(iter));
 		assert(iter_prev != node);
-		if (!dummy)
+		if (!bucket_flag)
 			node->next = clear_flag(iter);
 		else
-			node->next = flag_dummy(clear_flag(iter));
-		if (is_dummy(iter))
-			new_node = flag_dummy(node);
+			node->next = flag_bucket(clear_flag(iter));
+		if (is_bucket(iter))
+			new_node = flag_bucket(node);
 		else
 			new_node = node;
 		if (uatomic_cmpxchg(&iter_prev->next, iter,
@@ -978,8 +978,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
 	gc_node:
 		assert(!is_removed(iter));
-		if (is_dummy(iter))
-			new_next = flag_dummy(clear_flag(next));
+		if (is_bucket(iter))
+			new_next = flag_bucket(clear_flag(next));
 		else
 			new_next = clear_flag(next);
 		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
@@ -995,7 +995,7 @@ end:
 static
 int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		struct cds_lfht_node *node,
-		int dummy_removal)
+		int bucket_removal)
 {
 	struct cds_lfht_node *bucket, *next, *old;
 
@@ -1003,7 +1003,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		return -ENOENT;
 
 	/* logically delete the node */
-	assert(!is_dummy(node));
+	assert(!is_bucket(node));
 	assert(!is_removed(node));
 	old = rcu_dereference(node->next);
 	do {
@@ -1012,10 +1012,10 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
 		next = old;
 		if (caa_unlikely(is_removed(next)))
 			return -ENOENT;
-		if (dummy_removal)
-			assert(is_dummy(next));
+		if (bucket_removal)
+			assert(is_bucket(next));
 		else
-			assert(!is_dummy(next));
+			assert(!is_bucket(next));
 		new_next = flag_removed(next);
 		old = uatomic_cmpxchg(&node->next, next, new_next);
 	} while (old != next);
@@ -1095,7 +1095,7 @@ void partition_resize_helper(struct cds_lfht *ht, unsigned long i,
  * many worker threads, based on the number of CPUs available in the system.
  * This should therefore take care of not having the expand lagging behind too
  * many concurrent insertion threads by using the scheduler's ability to
- * schedule dummy node population fairly with insertions.
+ * schedule bucket node population fairly with insertions.
  */
 static
 void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
@@ -1155,8 +1155,8 @@ void init_table(struct cds_lfht *ht,
 		assert(ht->t.tbl[i]);
 
 		/*
-		 * Set all dummy nodes reverse hash values for a level and
-		 * link all dummy nodes into the table.
+		 * Set all bucket nodes reverse hash values for a level and
+		 * link all bucket nodes into the table.
 		 */
 		init_table_populate(ht, i, len);
 
@@ -1187,7 +1187,7 @@ void init_table(struct cds_lfht *ht,
  * Concurrent removal and add operations are helping us perform garbage
  * collection of logically removed nodes. We guarantee that all logically
  * removed nodes have been garbage-collected (unlinked) before call_rcu is
- * invoked to free a hole level of dummy nodes (after a grace period).
+ * invoked to free a hole level of bucket nodes (after a grace period).
  *
  * Logical removal and garbage collection can therefore be done in batch or on a
  * node-per-node basis, as long as the guarantee above holds.
@@ -1257,7 +1257,7 @@ void fini_table(struct cds_lfht *ht,
 		/*
 		 * We need to wait for all add operations to reach Q.S. (and
 		 * thus use the new table for lookups) before we can start
-		 * releasing the old dummy nodes. Otherwise their lookup will
+		 * releasing the old bucket nodes. Otherwise their lookup will
 		 * return a logically removed node as insert position.
 		 */
 		ht->cds_lfht_synchronize_rcu();
@@ -1265,8 +1265,8 @@ void fini_table(struct cds_lfht *ht,
 			free(free_by_rcu);
 
 		/*
-		 * Set "removed" flag in dummy nodes about to be removed.
-		 * Unlink all now-logically-removed dummy node pointers.
+		 * Set "removed" flag in bucket nodes about to be removed.
+		 * Unlink all now-logically-removed bucket node pointers.
 		 * Concurrent add/remove operation are helping us doing
 		 * the gc.
 		 */
@@ -1286,7 +1286,7 @@ void fini_table(struct cds_lfht *ht,
 }
 
 static
-void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
+void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
 {
 	struct cds_lfht_node *prev, *node;
 	unsigned long order, len, i, j;
@@ -1294,8 +1294,8 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
 	assert(ht->t.tbl[0]);
 
-	dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0);
-	ht->t.tbl[0]->nodes[0].next = flag_dummy(get_end());
+	dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0);
+	ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end());
 	ht->t.tbl[0]->nodes[0].reverse_hash = 0;
 
 	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
@@ -1318,12 +1318,12 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
 			}
 
 			node = &ht->t.tbl[order]->nodes[j];
-			dbg_printf("create dummy: order %lu index %lu hash %lu\n",
+			dbg_printf("create bucket: order %lu index %lu hash %lu\n",
 				   order, j, j + len);
 			node->next = prev->next;
-			assert(is_dummy(node->next));
+			assert(is_bucket(node->next));
 			node->reverse_hash = bit_reverse_ulong(j + len);
-			prev->next = flag_dummy(node);
+			prev->next = flag_bucket(node);
 		}
 	}
 }
@@ -1374,7 +1374,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
 	ht->t.resize_target = 1UL << order;
 	ht->min_alloc_size = min_alloc_size;
 	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
-	cds_lfht_create_dummy(ht, 1UL << order);
+	cds_lfht_create_bucket(ht, 1UL << order);
 	ht->t.size = 1UL << order;
 	return ht;
 }
@@ -1390,7 +1390,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 
 	size = rcu_dereference(ht->t.size);
 	bucket = lookup_bucket(ht, size, hash);
-	/* We can always skip the dummy node initially */
+	/* We can always skip the bucket node initially */
 	node = rcu_dereference(bucket->next);
 	node = clear_flag(node);
 	for (;;) {
@@ -1405,14 +1405,14 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		next = rcu_dereference(node->next);
 		assert(node == clear_flag(node));
 		if (caa_likely(!is_removed(next))
-		    && !is_dummy(next)
+		    && !is_bucket(next)
 		    && node->reverse_hash == reverse_hash
 		    && caa_likely(match(node, arg))) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->next)));
+	assert(!node || !is_bucket(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1438,13 +1438,13 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 		}
 		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
-		    && !is_dummy(next)
+		    && !is_bucket(next)
 		    && caa_likely(!ht->compare_fct(node, iter->node))) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->next)));
+	assert(!node || !is_bucket(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1461,12 +1461,12 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 		}
 		next = rcu_dereference(node->next);
 		if (caa_likely(!is_removed(next))
-		    && !is_dummy(next)) {
+		    && !is_bucket(next)) {
 				break;
 		}
 		node = clear_flag(next);
 	}
-	assert(!node || !is_dummy(rcu_dereference(node->next)));
+	assert(!node || !is_bucket(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
 }
@@ -1476,7 +1476,7 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 	struct cds_lfht_node *lookup;
 
 	/*
-	 * Get next after first dummy node. The first dummy node is the
+	 * Get next after first bucket node. The first bucket node is the
 	 * first node of the linked list.
 	 */
 	lookup = &ht->t.tbl[0]->nodes[0];
@@ -1557,7 +1557,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
 }
 
 static
-int cds_lfht_delete_dummy(struct cds_lfht *ht)
+int cds_lfht_delete_bucket(struct cds_lfht *ht)
 {
 	struct cds_lfht_node *node;
 	unsigned long order, i, size;
@@ -1566,7 +1566,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
 	node = &ht->t.tbl[0]->nodes[0];
 	do {
 		node = clear_flag(node)->next;
-		if (!is_dummy(node))
+		if (!is_bucket(node))
 			return -EPERM;
 		assert(!is_removed(node));
 	} while (!is_end(node));
@@ -1575,7 +1575,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
 	 * being destroyed.
 	 */
 	size = ht->t.size;
-	/* Internal sanity check: all nodes left should be dummy */
+	/* Internal sanity check: all nodes left should be bucket */
 	for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
 		unsigned long len;
 
@@ -1584,7 +1584,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
 			dbg_printf("delete order %lu i %lu hash %lu\n",
 				order, i,
 				bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
-			assert(is_dummy(ht->t.tbl[order]->nodes[i].next));
+			assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
 		}
 
 		if (order == ht->min_alloc_order)
@@ -1609,7 +1609,7 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
 	cmm_smp_mb();	/* Store destroy before load resize */
 	while (uatomic_read(&ht->in_progress_resize))
 		poll(NULL, 0, 100);	/* wait for 100ms */
-	ret = cds_lfht_delete_dummy(ht);
+	ret = cds_lfht_delete_bucket(ht);
 	if (ret)
 		return ret;
 	free_split_items_count(ht);
@@ -1626,7 +1626,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 		long *approx_after)
 {
 	struct cds_lfht_node *node, *next;
-	unsigned long nr_dummy = 0;
+	unsigned long nr_bucket = 0;
 
 	*approx_before = 0;
 	if (ht->split_count) {
@@ -1641,22 +1641,22 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 	*count = 0;
 	*removed = 0;
 
-	/* Count non-dummy nodes in the table */
+	/* Count non-bucket nodes in the table */
 	node = &ht->t.tbl[0]->nodes[0];
 	do {
 		next = rcu_dereference(node->next);
 		if (is_removed(next)) {
-			if (!is_dummy(next))
+			if (!is_bucket(next))
 				(*removed)++;
 			else
-				(nr_dummy)++;
-		} else if (!is_dummy(next))
+				(nr_bucket)++;
+		} else if (!is_bucket(next))
 			(*count)++;
 		else
-			(nr_dummy)++;
+			(nr_bucket)++;
 		node = clear_flag(next);
 	} while (!is_end(node));
-	dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
+	dbg_printf("number of bucket nodes: %lu\n", nr_bucket);
 	*approx_after = 0;
 	if (ht->split_count) {
 		int i;
@@ -1697,7 +1697,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
 		   old_size, old_order, new_size, new_order);
 	assert(new_size < old_size);
 
-	/* Remove and unlink all dummy nodes to remove. */
+	/* Remove and unlink all bucket nodes to remove. */
 	fini_table(ht, new_order + 1, old_order);
 }
 
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 3e915a0..72598e4 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -48,7 +48,7 @@ extern "C" {
  * the hash value for cds_lfht APIs.
  */
 struct cds_lfht_node {
-	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
+	struct cds_lfht_node *next;	/* ptr | BUCKET_FLAG | REMOVED_FLAG */
 	unsigned long reverse_hash;
 } __attribute__((aligned(4)));
 
-- 
1.7.4.4

[ltt-dev] [PATCH 2/2] rculfhash: simplify BUCKET_FLAG tracking

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |   41 ++++++++++++++++-------------------------
 1 files changed, 16 insertions(+), 25 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 88079f9..0163a1b 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -316,13 +316,6 @@ struct partition_resize_work {
 		    unsigned long start, unsigned long len);
 };
 
-static
-void _cds_lfht_add(struct cds_lfht *ht,
-		unsigned long size,
-		struct cds_lfht_node *node,
-		struct cds_lfht_iter *unique_ret,
-		int bucket);
-
 /*
  * Algorithm to reverse bits in a word by lookup table, extended to
  * 64-bit words.
@@ -728,6 +721,14 @@ struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
 }
 
 static
+struct cds_lfht_node *flag_keep_bucket(struct cds_lfht_node *node,
+		unsigned long bucket)
+{
+	return (struct cds_lfht_node *) (((unsigned long) node) |
+			(bucket & BUCKET_FLAG));
+}
+
+static
 struct cds_lfht_node *get_end(void)
 {
 	return (struct cds_lfht_node *) END_VALUE;
@@ -815,10 +816,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *nod
 			iter = next;
 		}
 		assert(!is_removed(iter));
-		if (is_bucket(iter))
-			new_next = flag_bucket(clear_flag(next));
-		else
-			new_next = clear_flag(next);
+		new_next = flag_keep_bucket(clear_flag(next), (unsigned long)iter);
 		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 	}
 	return;
@@ -884,13 +882,15 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 /*
  * A non-NULL unique_ret pointer uses the "add unique" (or uniquify) add
  * mode. A NULL unique_ret allows creation of duplicate keys.
+ *
+ * @bucket_flag should be 0 or BUCKET_FLAG
  */
 static
 void _cds_lfht_add(struct cds_lfht *ht,
 		unsigned long size,
 		struct cds_lfht_node *node,
 		struct cds_lfht_iter *unique_ret,
-		int bucket_flag)
+		unsigned long bucket_flag)
 {
 	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
 			*return_node;
@@ -960,14 +960,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
 		assert(!is_removed(iter_prev));
 		assert(!is_removed(iter));
 		assert(iter_prev != node);
-		if (!bucket_flag)
-			node->next = clear_flag(iter);
-		else
-			node->next = flag_bucket(clear_flag(iter));
-		if (is_bucket(iter))
-			new_node = flag_bucket(node);
-		else
-			new_node = node;
+		node->next = flag_keep_bucket(clear_flag(iter), bucket_flag);
+		new_node = flag_keep_bucket(node, (unsigned long)iter);
 		if (uatomic_cmpxchg(&iter_prev->next, iter,
 				    new_node) != iter) {
 			continue;	/* retry */
@@ -978,10 +972,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
 
 	gc_node:
 		assert(!is_removed(iter));
-		if (is_bucket(iter))
-			new_next = flag_bucket(clear_flag(next));
-		else
-			new_next = clear_flag(next);
+		new_next = flag_keep_bucket(clear_flag(next), (unsigned long)iter);
 		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
 		/* retry */
 	}
@@ -1113,7 +1104,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
 		new_node->reverse_hash =
 				bit_reverse_ulong((1UL << (i - 1)) + j);
 		_cds_lfht_add(ht, 1UL << (i - 1),
-				new_node, NULL, 1);
+				new_node, NULL, BUCKET_FLAG);
 	}
 	ht->cds_lfht_rcu_read_unlock();
 }
-- 
1.7.4.4

[ltt-dev] [PATCH 2/2] rculfhash: simplify BUCKET_FLAG tracking

[Mathieu Desnoyers]

Hi Lai,

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c |   41 ++++++++++++++++-------------------------
>  1 files changed, 16 insertions(+), 25 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 88079f9..0163a1b 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -316,13 +316,6 @@ struct partition_resize_work {
>  		    unsigned long start, unsigned long len);
>  };
>  
> -static
> -void _cds_lfht_add(struct cds_lfht *ht,
> -		unsigned long size,
> -		struct cds_lfht_node *node,
> -		struct cds_lfht_iter *unique_ret,
> -		int bucket);
> -
>  /*
>   * Algorithm to reverse bits in a word by lookup table, extended to
>   * 64-bit words.
> @@ -728,6 +721,14 @@ struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
>  }
>  
>  static
> +struct cds_lfht_node *flag_keep_bucket(struct cds_lfht_node *node,
> +		unsigned long bucket)
> +{
> +	return (struct cds_lfht_node *) (((unsigned long) node) |
> +			(bucket & BUCKET_FLAG));
> +}

Hrm. The name is "flag_keep_bucket", but we don't do a clear_flag on
"node" within this helper. So we end up having a behavior that differs
from the helper semantic. I understand that the code below that uses
flag_keep_bucket performs the clear_flag when needed, but I think it
would be good to rename flag_keep_bucket so anyone reviewing the code
would not be mislead by the name: I initially thought that
flag_keep_bucket kept only the "BUCKET" flag and cleared all other flags
from node, which is not the case.

In fact, what it does is to keep the node flag as-is, and OR the BUCKET
flag to node if it is set in the "bucket" argument.

So maybe "bucket_flag_or" would be more appropriate ?

> +
> +static
>  struct cds_lfht_node *get_end(void)
>  {
>  	return (struct cds_lfht_node *) END_VALUE;
> @@ -815,10 +816,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *nod
>  			iter = next;
>  		}
>  		assert(!is_removed(iter));
> -		if (is_bucket(iter))
> -			new_next = flag_bucket(clear_flag(next));
> -		else
> -			new_next = clear_flag(next);
> +		new_next = flag_keep_bucket(clear_flag(next), (unsigned long)iter);


Also please use "(unsigned long) iter" (with a space) to keep the coding
style of the file.

Thanks,

Mathieu


>  		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
>  	}
>  	return;
> @@ -884,13 +882,15 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
>  /*
>   * A non-NULL unique_ret pointer uses the "add unique" (or uniquify) add
>   * mode. A NULL unique_ret allows creation of duplicate keys.
> + *
> + * @bucket_flag should be 0 or BUCKET_FLAG
>   */
>  static
>  void _cds_lfht_add(struct cds_lfht *ht,
>  		unsigned long size,
>  		struct cds_lfht_node *node,
>  		struct cds_lfht_iter *unique_ret,
> -		int bucket_flag)
> +		unsigned long bucket_flag)
>  {
>  	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
>  			*return_node;
> @@ -960,14 +960,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  		assert(!is_removed(iter_prev));
>  		assert(!is_removed(iter));
>  		assert(iter_prev != node);
> -		if (!bucket_flag)
> -			node->next = clear_flag(iter);
> -		else
> -			node->next = flag_bucket(clear_flag(iter));
> -		if (is_bucket(iter))
> -			new_node = flag_bucket(node);
> -		else
> -			new_node = node;
> +		node->next = flag_keep_bucket(clear_flag(iter), bucket_flag);
> +		new_node = flag_keep_bucket(node, (unsigned long)iter);
>  		if (uatomic_cmpxchg(&iter_prev->next, iter,
>  				    new_node) != iter) {
>  			continue;	/* retry */
> @@ -978,10 +972,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  
>  	gc_node:
>  		assert(!is_removed(iter));
> -		if (is_bucket(iter))
> -			new_next = flag_bucket(clear_flag(next));
> -		else
> -			new_next = clear_flag(next);
> +		new_next = flag_keep_bucket(clear_flag(next), (unsigned long)iter);
>  		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
>  		/* retry */
>  	}
> @@ -1113,7 +1104,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
>  		new_node->reverse_hash =
>  				bit_reverse_ulong((1UL << (i - 1)) + j);
>  		_cds_lfht_add(ht, 1UL << (i - 1),
> -				new_node, NULL, 1);
> +				new_node, NULL, BUCKET_FLAG);
>  	}
>  	ht->cds_lfht_rcu_read_unlock();
>  }
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[ltt-dev] [PATCH 1/2] rculfhash: rename dummy to bucket

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

Merged, thanks!

Mathieu

> ---
>  rculfhash.c      |  180 +++++++++++++++++++++++++++---------------------------
>  urcu/rculfhash.h |    2 +-
>  2 files changed, 91 insertions(+), 91 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 86b234f..88079f9 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -45,7 +45,7 @@
>   * - The resize operation executes concurrently with add/remove/lookup.
>   * - Hash table nodes are contained within a split-ordered list. This
>   *   list is ordered by incrementing reversed-bits-hash value.
> - * - An index of dummy nodes is kept. These dummy nodes are the hash
> + * - An index of bucket nodes is kept. These bucket nodes are the hash
>   *   table "buckets", and they are also chained together in the
>   *   split-ordered list, which allows recursive expansion.
>   * - The resize operation for small tables only allows expanding the hash table.
> @@ -74,7 +74,7 @@
>   *   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 dummy node) up to the
> + *   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
> @@ -88,19 +88,19 @@
>   *   for it do to so.
>   * - A RCU "order table" indexed by log2(hash index) is copied and
>   *   expanded by the resize operation. This order table allows finding
> - *   the "dummy node" tables.
> - * - There is one dummy node table per hash index order. The size of
> - *   each dummy node table is half the number of hashes contained in
> + *   the "bucket node" tables.
> + * - There is one bucket node table per hash index order. The size of
> + *   each bucket node table is half the number of hashes contained in
>   *   this order (except for order 0).
> - * - synchronzie_rcu is used to garbage-collect the old dummy node table.
> - * - The per-order dummy node tables contain a compact version of the
> + * - synchronzie_rcu is used to garbage-collect the old bucket node table.
> + * - The per-order bucket node tables contain a compact version of the
>   *   hash table nodes. These tables are invariant after they are
>   *   populated into the hash table.
>   *
> - * Dummy node tables:
> + * Bucket node tables:
>   *
> - * hash table	hash table	the last	all dummy node tables
> - * order	size		dummy node	0   1   2   3   4   5   6(index)
> + * hash table	hash table	the last	all bucket node tables
> + * order	size		bucket node	0   1   2   3   4   5   6(index)
>   * 				table size
>   * 0		1		1		1
>   * 1		2		1		1   1
> @@ -110,12 +110,12 @@
>   * 5		32		16		1   1   2   4   8  16
>   * 6		64		32		1   1   2   4   8  16  32
>   *
> - * When growing/shrinking, we only focus on the last dummy node table
> + * When growing/shrinking, we only focus on the last bucket node table
>   * which size is (!order ? 1 : (1 << (order -1))).
>   *
>   * Example for growing/shrinking:
> - * grow hash table from order 5 to 6: init the index=6 dummy node table
> - * shrink hash table from order 6 to 5: fini the index=6 dummy node table
> + * grow hash table from order 5 to 6: init the index=6 bucket node table
> + * shrink hash table from order 6 to 5: fini the index=6 bucket node table
>   *
>   * A bit of ascii art explanation:
>   * 
> @@ -195,7 +195,7 @@
>  #endif
>  
>  /*
> - * Minimum number of dummy nodes to touch per thread to parallelize grow/shrink.
> + * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
>   */
>  #define MIN_PARTITION_PER_THREAD_ORDER	12
>  #define MIN_PARTITION_PER_THREAD	(1UL << MIN_PARTITION_PER_THREAD_ORDER)
> @@ -212,11 +212,11 @@
>   * The removed flag needs to be updated atomically with the pointer.
>   * It indicates that no node must attach to the node scheduled for
>   * removal, and that node garbage collection must be performed.
> - * The dummy flag does not require to be updated atomically with the
> + * The bucket flag does not require to be updated atomically with the
>   * pointer, but it is added as a pointer low bit flag to save space.
>   */
>  #define REMOVED_FLAG		(1UL << 0)
> -#define DUMMY_FLAG		(1UL << 1)
> +#define BUCKET_FLAG		(1UL << 1)
>  #define FLAGS_MASK		((1UL << 2) - 1)
>  
>  /* Value of the end pointer. Should not interact with flags. */
> @@ -237,10 +237,10 @@ struct ht_items_count {
>  } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>  
>  /*
> - * rcu_level: Contains the per order-index-level dummy node table. The
> - * size of each dummy node table is half the number of hashes contained
> + * rcu_level: Contains the per order-index-level bucket node table. The
> + * size of each bucket node table is half the number of hashes contained
>   * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the dummy node arrays of the lowermost
> + * parameter allows combining the bucket node arrays of the lowermost
>   * levels to improve cache locality for small index orders.
>   */
>  struct rcu_level {
> @@ -321,7 +321,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  		unsigned long size,
>  		struct cds_lfht_node *node,
>  		struct cds_lfht_iter *unique_ret,
> -		int dummy);
> +		int bucket);
>  
>  /*
>   * Algorithm to reverse bits in a word by lookup table, extended to
> @@ -716,15 +716,15 @@ struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
>  }
>  
>  static
> -int is_dummy(struct cds_lfht_node *node)
> +int is_bucket(struct cds_lfht_node *node)
>  {
> -	return ((unsigned long) node) & DUMMY_FLAG;
> +	return ((unsigned long) node) & BUCKET_FLAG;
>  }
>  
>  static
> -struct cds_lfht_node *flag_dummy(struct cds_lfht_node *node)
> +struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node)
>  {
> -	return (struct cds_lfht_node *) (((unsigned long) node) | DUMMY_FLAG);
> +	return (struct cds_lfht_node *) (((unsigned long) node) | BUCKET_FLAG);
>  }
>  
>  static
> @@ -782,27 +782,27 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
>   * Remove all logically deleted nodes from a bucket up to a certain node key.
>   */
>  static
> -void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node)
> +void _cds_lfht_gc_bucket(struct cds_lfht_node *bucket, struct cds_lfht_node *node)
>  {
>  	struct cds_lfht_node *iter_prev, *iter, *next, *new_next;
>  
> -	assert(!is_dummy(dummy));
> -	assert(!is_removed(dummy));
> -	assert(!is_dummy(node));
> +	assert(!is_bucket(bucket));
> +	assert(!is_removed(bucket));
> +	assert(!is_bucket(node));
>  	assert(!is_removed(node));
>  	for (;;) {
> -		iter_prev = dummy;
> -		/* We can always skip the dummy node initially */
> +		iter_prev = bucket;
> +		/* We can always skip the bucket node initially */
>  		iter = rcu_dereference(iter_prev->next);
>  		assert(!is_removed(iter));
>  		assert(iter_prev->reverse_hash <= node->reverse_hash);
>  		/*
> -		 * We should never be called with dummy (start of chain)
> +		 * We should never be called with bucket (start of chain)
>  		 * and logically removed node (end of path compression
>  		 * marker) being the actual same node. This would be a
>  		 * bug in the algorithm implementation.
>  		 */
> -		assert(dummy != node);
> +		assert(bucket != node);
>  		for (;;) {
>  			if (caa_unlikely(is_end(iter)))
>  				return;
> @@ -815,8 +815,8 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node
>  			iter = next;
>  		}
>  		assert(!is_removed(iter));
> -		if (is_dummy(iter))
> -			new_next = flag_dummy(clear_flag(next));
> +		if (is_bucket(iter))
> +			new_next = flag_bucket(clear_flag(next));
>  		else
>  			new_next = clear_flag(next);
>  		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
> @@ -836,9 +836,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
>  		return -ENOENT;
>  
>  	assert(!is_removed(old_node));
> -	assert(!is_dummy(old_node));
> +	assert(!is_bucket(old_node));
>  	assert(!is_removed(new_node));
> -	assert(!is_dummy(new_node));
> +	assert(!is_bucket(new_node));
>  	assert(new_node != old_node);
>  	for (;;) {
>  		/* Insert after node to be replaced */
> @@ -849,7 +849,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
>  			 */
>  			return -ENOENT;
>  		}
> -		assert(!is_dummy(old_next));
> +		assert(!is_bucket(old_next));
>  		assert(new_node != clear_flag(old_next));
>  		new_node->next = clear_flag(old_next);
>  		/*
> @@ -890,13 +890,13 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  		unsigned long size,
>  		struct cds_lfht_node *node,
>  		struct cds_lfht_iter *unique_ret,
> -		int dummy)
> +		int bucket_flag)
>  {
>  	struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
>  			*return_node;
>  	struct cds_lfht_node *bucket;
>  
> -	assert(!is_dummy(node));
> +	assert(!is_bucket(node));
>  	assert(!is_removed(node));
>  	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
>  	for (;;) {
> @@ -907,7 +907,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  		 * insert location.
>  		 */
>  		iter_prev = bucket;
> -		/* We can always skip the dummy node initially */
> +		/* We can always skip the bucket node initially */
>  		iter = rcu_dereference(iter_prev->next);
>  		assert(iter_prev->reverse_hash <= node->reverse_hash);
>  		for (;;) {
> @@ -916,8 +916,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  			if (caa_likely(clear_flag(iter)->reverse_hash > node->reverse_hash))
>  				goto insert;
>  
> -			/* dummy node is the first node of the identical-hash-value chain */
> -			if (dummy && clear_flag(iter)->reverse_hash == node->reverse_hash)
> +			/* bucket node is the first node of the identical-hash-value chain */
> +			if (bucket_flag && clear_flag(iter)->reverse_hash == node->reverse_hash)
>  				goto insert;
>  
>  			next = rcu_dereference(clear_flag(iter)->next);
> @@ -926,7 +926,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  
>  			/* uniquely add */
>  			if (unique_ret
> -			    && !is_dummy(next)
> +			    && !is_bucket(next)
>  			    && clear_flag(iter)->reverse_hash == node->reverse_hash) {
>  				struct cds_lfht_iter d_iter = { .node = node, .next = iter, };
>  
> @@ -949,7 +949,7 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  
>  			/* Only account for identical reverse hash once */
>  			if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash
> -			    && !is_dummy(next))
> +			    && !is_bucket(next))
>  				check_resize(ht, size, ++chain_len);
>  			iter_prev = clear_flag(iter);
>  			iter = next;
> @@ -960,12 +960,12 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  		assert(!is_removed(iter_prev));
>  		assert(!is_removed(iter));
>  		assert(iter_prev != node);
> -		if (!dummy)
> +		if (!bucket_flag)
>  			node->next = clear_flag(iter);
>  		else
> -			node->next = flag_dummy(clear_flag(iter));
> -		if (is_dummy(iter))
> -			new_node = flag_dummy(node);
> +			node->next = flag_bucket(clear_flag(iter));
> +		if (is_bucket(iter))
> +			new_node = flag_bucket(node);
>  		else
>  			new_node = node;
>  		if (uatomic_cmpxchg(&iter_prev->next, iter,
> @@ -978,8 +978,8 @@ void _cds_lfht_add(struct cds_lfht *ht,
>  
>  	gc_node:
>  		assert(!is_removed(iter));
> -		if (is_dummy(iter))
> -			new_next = flag_dummy(clear_flag(next));
> +		if (is_bucket(iter))
> +			new_next = flag_bucket(clear_flag(next));
>  		else
>  			new_next = clear_flag(next);
>  		(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
> @@ -995,7 +995,7 @@ end:
>  static
>  int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
>  		struct cds_lfht_node *node,
> -		int dummy_removal)
> +		int bucket_removal)
>  {
>  	struct cds_lfht_node *bucket, *next, *old;
>  
> @@ -1003,7 +1003,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
>  		return -ENOENT;
>  
>  	/* logically delete the node */
> -	assert(!is_dummy(node));
> +	assert(!is_bucket(node));
>  	assert(!is_removed(node));
>  	old = rcu_dereference(node->next);
>  	do {
> @@ -1012,10 +1012,10 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
>  		next = old;
>  		if (caa_unlikely(is_removed(next)))
>  			return -ENOENT;
> -		if (dummy_removal)
> -			assert(is_dummy(next));
> +		if (bucket_removal)
> +			assert(is_bucket(next));
>  		else
> -			assert(!is_dummy(next));
> +			assert(!is_bucket(next));
>  		new_next = flag_removed(next);
>  		old = uatomic_cmpxchg(&node->next, next, new_next);
>  	} while (old != next);
> @@ -1095,7 +1095,7 @@ void partition_resize_helper(struct cds_lfht *ht, unsigned long i,
>   * many worker threads, based on the number of CPUs available in the system.
>   * This should therefore take care of not having the expand lagging behind too
>   * many concurrent insertion threads by using the scheduler's ability to
> - * schedule dummy node population fairly with insertions.
> + * schedule bucket node population fairly with insertions.
>   */
>  static
>  void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> @@ -1155,8 +1155,8 @@ void init_table(struct cds_lfht *ht,
>  		assert(ht->t.tbl[i]);
>  
>  		/*
> -		 * Set all dummy nodes reverse hash values for a level and
> -		 * link all dummy nodes into the table.
> +		 * Set all bucket nodes reverse hash values for a level and
> +		 * link all bucket nodes into the table.
>  		 */
>  		init_table_populate(ht, i, len);
>  
> @@ -1187,7 +1187,7 @@ void init_table(struct cds_lfht *ht,
>   * Concurrent removal and add operations are helping us perform garbage
>   * collection of logically removed nodes. We guarantee that all logically
>   * removed nodes have been garbage-collected (unlinked) before call_rcu is
> - * invoked to free a hole level of dummy nodes (after a grace period).
> + * invoked to free a hole level of bucket nodes (after a grace period).
>   *
>   * Logical removal and garbage collection can therefore be done in batch or on a
>   * node-per-node basis, as long as the guarantee above holds.
> @@ -1257,7 +1257,7 @@ void fini_table(struct cds_lfht *ht,
>  		/*
>  		 * We need to wait for all add operations to reach Q.S. (and
>  		 * thus use the new table for lookups) before we can start
> -		 * releasing the old dummy nodes. Otherwise their lookup will
> +		 * releasing the old bucket nodes. Otherwise their lookup will
>  		 * return a logically removed node as insert position.
>  		 */
>  		ht->cds_lfht_synchronize_rcu();
> @@ -1265,8 +1265,8 @@ void fini_table(struct cds_lfht *ht,
>  			free(free_by_rcu);
>  
>  		/*
> -		 * Set "removed" flag in dummy nodes about to be removed.
> -		 * Unlink all now-logically-removed dummy node pointers.
> +		 * Set "removed" flag in bucket nodes about to be removed.
> +		 * Unlink all now-logically-removed bucket node pointers.
>  		 * Concurrent add/remove operation are helping us doing
>  		 * the gc.
>  		 */
> @@ -1286,7 +1286,7 @@ void fini_table(struct cds_lfht *ht,
>  }
>  
>  static
> -void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
> +void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>  {
>  	struct cds_lfht_node *prev, *node;
>  	unsigned long order, len, i, j;
> @@ -1294,8 +1294,8 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
>  	ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
>  	assert(ht->t.tbl[0]);
>  
> -	dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0);
> -	ht->t.tbl[0]->nodes[0].next = flag_dummy(get_end());
> +	dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0);
> +	ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end());
>  	ht->t.tbl[0]->nodes[0].reverse_hash = 0;
>  
>  	for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
> @@ -1318,12 +1318,12 @@ void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size)
>  			}
>  
>  			node = &ht->t.tbl[order]->nodes[j];
> -			dbg_printf("create dummy: order %lu index %lu hash %lu\n",
> +			dbg_printf("create bucket: order %lu index %lu hash %lu\n",
>  				   order, j, j + len);
>  			node->next = prev->next;
> -			assert(is_dummy(node->next));
> +			assert(is_bucket(node->next));
>  			node->reverse_hash = bit_reverse_ulong(j + len);
> -			prev->next = flag_dummy(node);
> +			prev->next = flag_bucket(node);
>  		}
>  	}
>  }
> @@ -1374,7 +1374,7 @@ struct cds_lfht *_cds_lfht_new(cds_lfht_compare_fct compare_fct,
>  	ht->t.resize_target = 1UL << order;
>  	ht->min_alloc_size = min_alloc_size;
>  	ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> -	cds_lfht_create_dummy(ht, 1UL << order);
> +	cds_lfht_create_bucket(ht, 1UL << order);
>  	ht->t.size = 1UL << order;
>  	return ht;
>  }
> @@ -1390,7 +1390,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>  
>  	size = rcu_dereference(ht->t.size);
>  	bucket = lookup_bucket(ht, size, hash);
> -	/* We can always skip the dummy node initially */
> +	/* We can always skip the bucket node initially */
>  	node = rcu_dereference(bucket->next);
>  	node = clear_flag(node);
>  	for (;;) {
> @@ -1405,14 +1405,14 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>  		next = rcu_dereference(node->next);
>  		assert(node == clear_flag(node));
>  		if (caa_likely(!is_removed(next))
> -		    && !is_dummy(next)
> +		    && !is_bucket(next)
>  		    && node->reverse_hash == reverse_hash
>  		    && caa_likely(match(node, arg))) {
>  				break;
>  		}
>  		node = clear_flag(next);
>  	}
> -	assert(!node || !is_dummy(rcu_dereference(node->next)));
> +	assert(!node || !is_bucket(rcu_dereference(node->next)));
>  	iter->node = node;
>  	iter->next = next;
>  }
> @@ -1438,13 +1438,13 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  		}
>  		next = rcu_dereference(node->next);
>  		if (caa_likely(!is_removed(next))
> -		    && !is_dummy(next)
> +		    && !is_bucket(next)
>  		    && caa_likely(!ht->compare_fct(node, iter->node))) {
>  				break;
>  		}
>  		node = clear_flag(next);
>  	}
> -	assert(!node || !is_dummy(rcu_dereference(node->next)));
> +	assert(!node || !is_bucket(rcu_dereference(node->next)));
>  	iter->node = node;
>  	iter->next = next;
>  }
> @@ -1461,12 +1461,12 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  		}
>  		next = rcu_dereference(node->next);
>  		if (caa_likely(!is_removed(next))
> -		    && !is_dummy(next)) {
> +		    && !is_bucket(next)) {
>  				break;
>  		}
>  		node = clear_flag(next);
>  	}
> -	assert(!node || !is_dummy(rcu_dereference(node->next)));
> +	assert(!node || !is_bucket(rcu_dereference(node->next)));
>  	iter->node = node;
>  	iter->next = next;
>  }
> @@ -1476,7 +1476,7 @@ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  	struct cds_lfht_node *lookup;
>  
>  	/*
> -	 * Get next after first dummy node. The first dummy node is the
> +	 * Get next after first bucket node. The first bucket node is the
>  	 * first node of the linked list.
>  	 */
>  	lookup = &ht->t.tbl[0]->nodes[0];
> @@ -1557,7 +1557,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>  }
>  
>  static
> -int cds_lfht_delete_dummy(struct cds_lfht *ht)
> +int cds_lfht_delete_bucket(struct cds_lfht *ht)
>  {
>  	struct cds_lfht_node *node;
>  	unsigned long order, i, size;
> @@ -1566,7 +1566,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
>  	node = &ht->t.tbl[0]->nodes[0];
>  	do {
>  		node = clear_flag(node)->next;
> -		if (!is_dummy(node))
> +		if (!is_bucket(node))
>  			return -EPERM;
>  		assert(!is_removed(node));
>  	} while (!is_end(node));
> @@ -1575,7 +1575,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
>  	 * being destroyed.
>  	 */
>  	size = ht->t.size;
> -	/* Internal sanity check: all nodes left should be dummy */
> +	/* Internal sanity check: all nodes left should be bucket */
>  	for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
>  		unsigned long len;
>  
> @@ -1584,7 +1584,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht)
>  			dbg_printf("delete order %lu i %lu hash %lu\n",
>  				order, i,
>  				bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
> -			assert(is_dummy(ht->t.tbl[order]->nodes[i].next));
> +			assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
>  		}
>  
>  		if (order == ht->min_alloc_order)
> @@ -1609,7 +1609,7 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
>  	cmm_smp_mb();	/* Store destroy before load resize */
>  	while (uatomic_read(&ht->in_progress_resize))
>  		poll(NULL, 0, 100);	/* wait for 100ms */
> -	ret = cds_lfht_delete_dummy(ht);
> +	ret = cds_lfht_delete_bucket(ht);
>  	if (ret)
>  		return ret;
>  	free_split_items_count(ht);
> @@ -1626,7 +1626,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
>  		long *approx_after)
>  {
>  	struct cds_lfht_node *node, *next;
> -	unsigned long nr_dummy = 0;
> +	unsigned long nr_bucket = 0;
>  
>  	*approx_before = 0;
>  	if (ht->split_count) {
> @@ -1641,22 +1641,22 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
>  	*count = 0;
>  	*removed = 0;
>  
> -	/* Count non-dummy nodes in the table */
> +	/* Count non-bucket nodes in the table */
>  	node = &ht->t.tbl[0]->nodes[0];
>  	do {
>  		next = rcu_dereference(node->next);
>  		if (is_removed(next)) {
> -			if (!is_dummy(next))
> +			if (!is_bucket(next))
>  				(*removed)++;
>  			else
> -				(nr_dummy)++;
> -		} else if (!is_dummy(next))
> +				(nr_bucket)++;
> +		} else if (!is_bucket(next))
>  			(*count)++;
>  		else
> -			(nr_dummy)++;
> +			(nr_bucket)++;
>  		node = clear_flag(next);
>  	} while (!is_end(node));
> -	dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
> +	dbg_printf("number of bucket nodes: %lu\n", nr_bucket);
>  	*approx_after = 0;
>  	if (ht->split_count) {
>  		int i;
> @@ -1697,7 +1697,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
>  		   old_size, old_order, new_size, new_order);
>  	assert(new_size < old_size);
>  
> -	/* Remove and unlink all dummy nodes to remove. */
> +	/* Remove and unlink all bucket nodes to remove. */
>  	fini_table(ht, new_order + 1, old_order);
>  }
>  
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index 3e915a0..72598e4 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -48,7 +48,7 @@ extern "C" {
>   * the hash value for cds_lfht APIs.
>   */
>  struct cds_lfht_node {
> -	struct cds_lfht_node *next;	/* ptr | DUMMY_FLAG | REMOVED_FLAG */
> +	struct cds_lfht_node *next;	/* ptr | BUCKET_FLAG | REMOVED_FLAG */
>  	unsigned long reverse_hash;
>  } __attribute__((aligned(4)));
>  
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com