[ltt-dev] [PATCH 0/9] change lfht test

[ltt-dev] [PATCH 0/9] change lfht test

[Lai Jiangshan]

remove pools
add bucket conflict test
add same-hash-value-chain test
use different duplicated node test

Use random value for hash value directly, so a proper random
number generator is used.

Lai Jiangshan (9):
  Fix arguments order
  keep the last position for failed lookup
  add cds_lfht_add_at()
  new random generator
  use random value for hash value directly
  test hash value Confilict with buckets
  add identical-hash-value-chain test
  add duplicated node test
  change strategy for AR_RANDOM

 rculfhash.c            |   50 +++++--
 tests/test_urcu_hash.c |  433 +++++++++++++++++++++++-------------------------
 urcu/rculfhash.h       |   51 ++++--
 3 files changed, 279 insertions(+), 255 deletions(-)

-- 
1.7.4.4

[ltt-dev] [PATCH 1/9] Fix arguments order

[Lai Jiangshan]

use: hash, match, key

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

diff --git a/rculfhash.c b/rculfhash.c
index 41b774a..bda3bd6 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1381,8 +1381,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	return ht;
 }
 
-void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
-		unsigned long hash, void *key, struct cds_lfht_iter *iter)
+void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+		cds_lfht_match_fct match, void *key,
+		struct cds_lfht_iter *iter)
 {
 	struct cds_lfht_node *node, *next, *bucket;
 	unsigned long reverse_hash, size;
@@ -1498,9 +1499,9 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 }
 
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
+				unsigned long hash,
 				cds_lfht_match_fct match,
 				void *key,
-				unsigned long hash,
 				struct cds_lfht_node *node)
 {
 	unsigned long size;
@@ -1515,9 +1516,9 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 }
 
 struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
+				unsigned long hash,
 				cds_lfht_match_fct match,
 				void *key,
-				unsigned long hash,
 				struct cds_lfht_node *node)
 {
 	unsigned long size;
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 554f1e9..509767c 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -440,9 +440,8 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 {
 	assert(key_len == sizeof(unsigned long));
 
-	cds_lfht_lookup(ht, test_match,
-			test_hash(key, key_len, TEST_HASH_SEED),
-			key, iter);
+	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
+			test_match, key, iter);
 }
 
 void *thr_count(void *arg)
@@ -577,14 +576,14 @@ void *thr_writer(void *_count)
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
+				ret_node = cds_lfht_add_unique(test_ht,
 					test_hash(node->key, node->key_len, TEST_HASH_SEED),
-					&node->node);
+					test_match, node->key, &node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
+					ret_node = cds_lfht_add_replace(test_ht,
 							test_hash(node->key, node->key_len, TEST_HASH_SEED),
-							&node->node);
+							test_match, node->key, &node->node);
 				else
 					cds_lfht_add(test_ht,
 						test_hash(node->key, node->key_len, TEST_HASH_SEED),
@@ -674,14 +673,14 @@ static int populate_hash(void)
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
+			ret_node = cds_lfht_add_unique(test_ht,
 				test_hash(node->key, node->key_len, TEST_HASH_SEED),
-				&node->node);
+				test_match, node->key, &node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
+				ret_node = cds_lfht_add_replace(test_ht,
 						test_hash(node->key, node->key_len, TEST_HASH_SEED),
-						&node->node);
+						test_match, node->key, &node->node);
 			else
 				cds_lfht_add(test_ht,
 					test_hash(node->key, node->key_len, TEST_HASH_SEED),
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 06e3eb9..c13d3df 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -71,8 +71,6 @@ 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_match_fct)(struct cds_lfht_node *node, void *key);
 
 /*
@@ -179,15 +177,17 @@ 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.
+ * @match: the key match function.
+ * @key: the current node key.
  * @iter: Node, if found (output). *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, cds_lfht_match_fct match,
-		unsigned long hash, void *key, struct cds_lfht_iter *iter);
+void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+		cds_lfht_match_fct match, void *key,
+		struct cds_lfht_iter *iter);
 
 /*
  * cds_lfht_next_duplicate - get the next item with same key (after a lookup).
@@ -248,9 +248,9 @@ 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.
+ * @hash: the node's hash.
  * @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.
@@ -266,17 +266,17 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
  * add_unique and add_replace (see below).
  */
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
+		unsigned long hash,
 		cds_lfht_match_fct match,
 		void *key,
-		unsigned long hash,
 		struct cds_lfht_node *node);
 
 /*
  * cds_lfht_add_replace - replace or add a node within hash table.
  * @ht: the hash table.
+ * @hash: the node's hash.
  * @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
@@ -298,9 +298,9 @@ 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,
+		unsigned long hash,
 		cds_lfht_match_fct match,
 		void *key,
-		unsigned long hash,
 		struct cds_lfht_node *node);
 
 /*
@@ -373,8 +373,8 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 		cds_lfht_next(ht, iter),				\
 			node = cds_lfht_iter_get_node(iter))
 
-#define cds_lfht_for_each_duplicate(ht, match, hash, key, iter, node)	\
-	for (cds_lfht_lookup(ht, match, hash, key, iter),		\
+#define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
+	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
 			node = cds_lfht_iter_get_node(iter);		\
 		node != NULL;						\
 		cds_lfht_next_duplicate(ht, match, key, iter),		\
@@ -389,9 +389,9 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 					typeof(*(pos)), member))
 
-#define cds_lfht_for_each_entry_duplicate(ht, match, hash, key,		\
+#define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,		\
 				iter, pos, member)			\
-	for (cds_lfht_lookup(ht, match, hash, key, iter),		\
+	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
 			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
 					typeof(*(pos)), member);	\
 		&(pos)->member != NULL;					\
-- 
1.7.4.4

[ltt-dev] [PATCH 1/9] Fix arguments order

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> use: hash, match, key

Yep, makes more sense like this. Merged, thanks !

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |    9 +++++----
>  tests/test_urcu_hash.c |   21 ++++++++++-----------
>  urcu/rculfhash.h       |   26 +++++++++++++-------------
>  3 files changed, 28 insertions(+), 28 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 41b774a..bda3bd6 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1381,8 +1381,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	return ht;
>  }
>  
> -void cds_lfht_lookup(struct cds_lfht *ht, cds_lfht_match_fct match,
> -		unsigned long hash, void *key, struct cds_lfht_iter *iter)
> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> +		cds_lfht_match_fct match, void *key,
> +		struct cds_lfht_iter *iter)
>  {
>  	struct cds_lfht_node *node, *next, *bucket;
>  	unsigned long reverse_hash, size;
> @@ -1498,9 +1499,9 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
>  }
>  
>  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> +				unsigned long hash,
>  				cds_lfht_match_fct match,
>  				void *key,
> -				unsigned long hash,
>  				struct cds_lfht_node *node)
>  {
>  	unsigned long size;
> @@ -1515,9 +1516,9 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
>  }
>  
>  struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
> +				unsigned long hash,
>  				cds_lfht_match_fct match,
>  				void *key,
> -				unsigned long hash,
>  				struct cds_lfht_node *node)
>  {
>  	unsigned long size;
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 554f1e9..509767c 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -440,9 +440,8 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
>  {
>  	assert(key_len == sizeof(unsigned long));
>  
> -	cds_lfht_lookup(ht, test_match,
> -			test_hash(key, key_len, TEST_HASH_SEED),
> -			key, iter);
> +	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
> +			test_match, key, iter);
>  }
>  
>  void *thr_count(void *arg)
> @@ -577,14 +576,14 @@ void *thr_writer(void *_count)
>  				sizeof(void *));
>  			rcu_read_lock();
>  			if (add_unique) {
> -				ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
> +				ret_node = cds_lfht_add_unique(test_ht,
>  					test_hash(node->key, node->key_len, TEST_HASH_SEED),
> -					&node->node);
> +					test_match, node->key, &node->node);
>  			} else {
>  				if (add_replace)
> -					ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
> +					ret_node = cds_lfht_add_replace(test_ht,
>  							test_hash(node->key, node->key_len, TEST_HASH_SEED),
> -							&node->node);
> +							test_match, node->key, &node->node);
>  				else
>  					cds_lfht_add(test_ht,
>  						test_hash(node->key, node->key_len, TEST_HASH_SEED),
> @@ -674,14 +673,14 @@ static int populate_hash(void)
>  			sizeof(void *));
>  		rcu_read_lock();
>  		if (add_unique) {
> -			ret_node = cds_lfht_add_unique(test_ht, test_match, node->key,
> +			ret_node = cds_lfht_add_unique(test_ht,
>  				test_hash(node->key, node->key_len, TEST_HASH_SEED),
> -				&node->node);
> +				test_match, node->key, &node->node);
>  		} else {
>  			if (add_replace)
> -				ret_node = cds_lfht_add_replace(test_ht, test_match, node->key,
> +				ret_node = cds_lfht_add_replace(test_ht,
>  						test_hash(node->key, node->key_len, TEST_HASH_SEED),
> -						&node->node);
> +						test_match, node->key, &node->node);
>  			else
>  				cds_lfht_add(test_ht,
>  					test_hash(node->key, node->key_len, TEST_HASH_SEED),
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index 06e3eb9..c13d3df 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -71,8 +71,6 @@ 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_match_fct)(struct cds_lfht_node *node, void *key);
>  
>  /*
> @@ -179,15 +177,17 @@ 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.
> + * @match: the key match function.
> + * @key: the current node key.
>   * @iter: Node, if found (output). *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, cds_lfht_match_fct match,
> -		unsigned long hash, void *key, struct cds_lfht_iter *iter);
> +void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> +		cds_lfht_match_fct match, void *key,
> +		struct cds_lfht_iter *iter);
>  
>  /*
>   * cds_lfht_next_duplicate - get the next item with same key (after a lookup).
> @@ -248,9 +248,9 @@ 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.
> + * @hash: the node's hash.
>   * @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.
> @@ -266,17 +266,17 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
>   * add_unique and add_replace (see below).
>   */
>  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> +		unsigned long hash,
>  		cds_lfht_match_fct match,
>  		void *key,
> -		unsigned long hash,
>  		struct cds_lfht_node *node);
>  
>  /*
>   * cds_lfht_add_replace - replace or add a node within hash table.
>   * @ht: the hash table.
> + * @hash: the node's hash.
>   * @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
> @@ -298,9 +298,9 @@ 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,
> +		unsigned long hash,
>  		cds_lfht_match_fct match,
>  		void *key,
> -		unsigned long hash,
>  		struct cds_lfht_node *node);
>  
>  /*
> @@ -373,8 +373,8 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
>  		cds_lfht_next(ht, iter),				\
>  			node = cds_lfht_iter_get_node(iter))
>  
> -#define cds_lfht_for_each_duplicate(ht, match, hash, key, iter, node)	\
> -	for (cds_lfht_lookup(ht, match, hash, key, iter),		\
> +#define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
> +	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
>  			node = cds_lfht_iter_get_node(iter);		\
>  		node != NULL;						\
>  		cds_lfht_next_duplicate(ht, match, key, iter),		\
> @@ -389,9 +389,9 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
>  			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
>  					typeof(*(pos)), member))
>  
> -#define cds_lfht_for_each_entry_duplicate(ht, match, hash, key,		\
> +#define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,		\
>  				iter, pos, member)			\
> -	for (cds_lfht_lookup(ht, match, hash, key, iter),		\
> +	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
>  			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
>  					typeof(*(pos)), member);	\
>  		&(pos)->member != NULL;					\
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 2/9] keep the last position for failed lookup

[Lai Jiangshan]

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

diff --git a/rculfhash.c b/rculfhash.c
index bda3bd6..cbfc79e 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1381,27 +1381,28 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	return ht;
 }
 
-void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		cds_lfht_match_fct match, void *key,
 		struct cds_lfht_iter *iter)
 {
-	struct cds_lfht_node *node, *next, *bucket;
+	struct cds_lfht_node *prev, *node, *next;
 	unsigned long reverse_hash, size;
 
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
-	bucket = lookup_bucket(ht, size, hash);
+	node = lookup_bucket(ht, size, hash);
+	next = rcu_dereference(node->next);
+	prev = node;
 	/* We can always skip the bucket node initially */
-	node = rcu_dereference(bucket->next);
-	node = clear_flag(node);
+	node = clear_flag(next);
 	for (;;) {
 		if (caa_unlikely(is_end(node))) {
-			node = next = NULL;
+			node = prev;
 			break;
 		}
 		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
-			node = next = NULL;
+			node = prev;
 			break;
 		}
 		next = rcu_dereference(node->next);
@@ -1412,11 +1413,13 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		    && caa_likely(match(node, key))) {
 				break;
 		}
+		prev = node;
 		node = clear_flag(next);
 	}
-	assert(!node || !is_bucket(rcu_dereference(node->next)));
+	assert(node == prev || !is_bucket(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
+	return node != prev;
 }
 
 void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 509767c..bae6ed2 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -440,8 +440,9 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 {
 	assert(key_len == sizeof(unsigned long));
 
-	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
-			test_match, key, iter);
+	if (!cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
+			test_match, key, iter))
+		iter->node = iter->next = NULL;
 }
 
 void *thr_count(void *arg)
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index c13d3df..7d919d0 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -26,6 +26,7 @@
  */
 
 #include <stdint.h>
+#include <stdbool.h>
 #include <urcu/compiler.h>
 #include <urcu-call-rcu.h>
 
@@ -180,12 +181,15 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
  * @hash: the key hash.
  * @match: the key match function.
  * @key: the current node key.
- * @iter: Node, if found (output). *iter->node set to NULL if not found.
+ * @iter: Node, if found (output).
+ *        The last lookup node(maybe a bucket/removed node), if not found.
  *
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
+ *
+ * Return true if a match node is found
  */
-void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		cds_lfht_match_fct match, void *key,
 		struct cds_lfht_iter *iter);
 
@@ -374,8 +378,8 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 			node = cds_lfht_iter_get_node(iter))
 
 #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
-	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
-			node = cds_lfht_iter_get_node(iter);		\
+	for (node = cds_lfht_lookup(ht, hash, match, key, iter) ?	\
+			cds_lfht_iter_get_node(iter) : NULL;		\
 		node != NULL;						\
 		cds_lfht_next_duplicate(ht, match, key, iter),		\
 			node = cds_lfht_iter_get_node(iter))
@@ -391,8 +395,9 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 
 #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,		\
 				iter, pos, member)			\
-	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
-			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
+	for (pos = caa_container_of(					\
+			cds_lfht_lookup(ht, hash, match, key, iter) ?	\
+			cds_lfht_iter_get_node(iter) : NULL,		\
 					typeof(*(pos)), member);	\
 		&(pos)->member != NULL;					\
 		cds_lfht_next_duplicate(ht, match, key, iter),		\
-- 
1.7.4.4

[ltt-dev] [PATCH 2/9] keep the last position for failed lookup

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c            |   19 +++++++++++--------
>  tests/test_urcu_hash.c |    5 +++--
>  urcu/rculfhash.h       |   17 +++++++++++------
>  3 files changed, 25 insertions(+), 16 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index bda3bd6..cbfc79e 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1381,27 +1381,28 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>  	return ht;
>  }
>  
> -void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> +bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>  		cds_lfht_match_fct match, void *key,
>  		struct cds_lfht_iter *iter)
>  {

[...]

>  #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
> -	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
> -			node = cds_lfht_iter_get_node(iter);		\
> +	for (node = cds_lfht_lookup(ht, hash, match, key, iter) ?	\
> +			cds_lfht_iter_get_node(iter) : NULL;		\

Hrm, is it me or this just complexifies use of this API ? Now, instead
of a 

  cds_lfht_lookup -> cds_lfht_iter_get_node -> check for null

chain, we need to do:

  cds_lfht_lookup -> check for nonzero return ? cds_lfht_iter_get_node :
                                                    NULL -> check for NULL

actually adding one test into the caller code.

What use-case is it allowing to justify this added API complexity ?

Thanks,

Mathieu

>  		node != NULL;						\
>  		cds_lfht_next_duplicate(ht, match, key, iter),		\
>  			node = cds_lfht_iter_get_node(iter))
> @@ -391,8 +395,9 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
>  
>  #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,		\
>  				iter, pos, member)			\
> -	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
> -			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
> +	for (pos = caa_container_of(					\
> +			cds_lfht_lookup(ht, hash, match, key, iter) ?	\
> +			cds_lfht_iter_get_node(iter) : NULL,		\
>  					typeof(*(pos)), member);	\
>  		&(pos)->member != NULL;					\
>  		cds_lfht_next_duplicate(ht, match, key, iter),		\
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 2/9] keep the last position for failed lookup

[Lai Jiangshan]

On 11/15/2011 07:10 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  rculfhash.c            |   19 +++++++++++--------
>>  tests/test_urcu_hash.c |    5 +++--
>>  urcu/rculfhash.h       |   17 +++++++++++------
>>  3 files changed, 25 insertions(+), 16 deletions(-)
>>
>> diff --git a/rculfhash.c b/rculfhash.c
>> index bda3bd6..cbfc79e 100644
>> --- a/rculfhash.c
>> +++ b/rculfhash.c
>> @@ -1381,27 +1381,28 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>>  	return ht;
>>  }
>>  
>> -void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>> +bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>>  		cds_lfht_match_fct match, void *key,
>>  		struct cds_lfht_iter *iter)
>>  {
> 
> [...]
> 
>>  #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
>> -	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
>> -			node = cds_lfht_iter_get_node(iter);		\
>> +	for (node = cds_lfht_lookup(ht, hash, match, key, iter) ?	\
>> +			cds_lfht_iter_get_node(iter) : NULL;		\
> 
> Hrm, is it me or this just complexifies use of this API ? Now, instead
> of a 
> 
>   cds_lfht_lookup -> cds_lfht_iter_get_node -> check for null
> 
> chain, we need to do:
> 
>   cds_lfht_lookup -> check for nonzero return ? cds_lfht_iter_get_node :
>                                                     NULL -> check for NULL
> 
> actually adding one test into the caller code.
> 
> What use-case is it allowing to justify this added API complexity ?

I found that it is a pattern:
lookup() --> found --> done
	 --> failed --> create --> insert at the last search place

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Lai Jiangshan]

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

diff --git a/rculfhash.c b/rculfhash.c
index cbfc79e..70f5863 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1495,12 +1495,34 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 {
 	unsigned long size;
 
-	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
+	node->reverse_hash = bit_reverse_ulong(hash);
 	size = rcu_dereference(ht->t.size);
 	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
 	ht_count_add(ht, size, hash);
 }
 
+bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
+		unsigned long hash, struct cds_lfht_node *node)
+{
+	struct cds_lfht_node *new_node;
+
+	if (caa_unlikely(is_removed(iter->next)))
+		return false;
+
+	node->reverse_hash = bit_reverse_ulong(hash);
+	node->next = clear_flag(iter->next);
+	if (is_bucket(iter->next))
+		new_node = flag_bucket(node);
+	else
+		new_node = node;
+	if (uatomic_cmpxchg(&iter->node->next, iter->next,
+			new_node) != iter->next)
+		return false;
+
+	ht_count_add(ht, rcu_dereference(ht->t.size), hash);
+	return true;
+}
+
 struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
 				unsigned long hash,
 				cds_lfht_match_fct match,
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 7d919d0..0f9bf44 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -250,6 +250,20 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
 		struct cds_lfht_node *node);
 
 /*
+ * cds_lfht_add_at - add a node to the hash table at the specified place.
+ * @ht: the hash table.
+ * @iter: the specified place to insert
+ * @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.
+ */
+bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
+		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.
  * @hash: the node's hash.
-- 
1.7.4.4

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Lai Jiangshan]

It seems that the testing patches have a strange problem, please wait before merge it.

Thanks,
Lai

On 11/14/2011 12:50 PM, Lai Jiangshan wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  rculfhash.c      |   24 +++++++++++++++++++++++-
>  urcu/rculfhash.h |   14 ++++++++++++++
>  2 files changed, 37 insertions(+), 1 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index cbfc79e..70f5863 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -1495,12 +1495,34 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
>  {
>  	unsigned long size;
>  
> -	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> +	node->reverse_hash = bit_reverse_ulong(hash);
>  	size = rcu_dereference(ht->t.size);
>  	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
>  	ht_count_add(ht, size, hash);
>  }
>  
> +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> +		unsigned long hash, struct cds_lfht_node *node)
> +{
> +	struct cds_lfht_node *new_node;
> +
> +	if (caa_unlikely(is_removed(iter->next)))
> +		return false;
> +
> +	node->reverse_hash = bit_reverse_ulong(hash);
> +	node->next = clear_flag(iter->next);
> +	if (is_bucket(iter->next))
> +		new_node = flag_bucket(node);
> +	else
> +		new_node = node;
> +	if (uatomic_cmpxchg(&iter->node->next, iter->next,
> +			new_node) != iter->next)
> +		return false;
> +
> +	ht_count_add(ht, rcu_dereference(ht->t.size), hash);
> +	return true;
> +}
> +
>  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
>  				unsigned long hash,
>  				cds_lfht_match_fct match,
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index 7d919d0..0f9bf44 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -250,6 +250,20 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
>  		struct cds_lfht_node *node);
>  
>  /*
> + * cds_lfht_add_at - add a node to the hash table at the specified place.
> + * @ht: the hash table.
> + * @iter: the specified place to insert
> + * @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.
> + */
> +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> +		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.
>   * @hash: the node's hash.

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> It seems that the testing patches have a strange problem, please wait
> before merge it.

OK, will wait. I'm a bit puzzled as to what this "add_to_at" actually
helps us doing ? What is the use-case for this new API ?

Thanks,

Mathieu

> 
> Thanks,
> Lai
> 
> On 11/14/2011 12:50 PM, Lai Jiangshan wrote:
> > Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> > ---
> >  rculfhash.c      |   24 +++++++++++++++++++++++-
> >  urcu/rculfhash.h |   14 ++++++++++++++
> >  2 files changed, 37 insertions(+), 1 deletions(-)
> > 
> > diff --git a/rculfhash.c b/rculfhash.c
> > index cbfc79e..70f5863 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -1495,12 +1495,34 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  {
> >  	unsigned long size;
> >  
> > -	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> >  	size = rcu_dereference(ht->t.size);
> >  	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
> >  	ht_count_add(ht, size, hash);
> >  }
> >  
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		unsigned long hash, struct cds_lfht_node *node)
> > +{
> > +	struct cds_lfht_node *new_node;
> > +
> > +	if (caa_unlikely(is_removed(iter->next)))
> > +		return false;
> > +
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> > +	node->next = clear_flag(iter->next);
> > +	if (is_bucket(iter->next))
> > +		new_node = flag_bucket(node);
> > +	else
> > +		new_node = node;
> > +	if (uatomic_cmpxchg(&iter->node->next, iter->next,
> > +			new_node) != iter->next)
> > +		return false;
> > +
> > +	ht_count_add(ht, rcu_dereference(ht->t.size), hash);
> > +	return true;
> > +}
> > +
> >  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> >  				unsigned long hash,
> >  				cds_lfht_match_fct match,
> > diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> > index 7d919d0..0f9bf44 100644
> > --- a/urcu/rculfhash.h
> > +++ b/urcu/rculfhash.h
> > @@ -250,6 +250,20 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  		struct cds_lfht_node *node);
> >  
> >  /*
> > + * cds_lfht_add_at - add a node to the hash table at the specified place.
> > + * @ht: the hash table.
> > + * @iter: the specified place to insert
> > + * @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.
> > + */
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		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.
> >   * @hash: the node's hash.
> 

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

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> It seems that the testing patches have a strange problem, please wait
> before merge it.

Hi Lai,

I'm still waiting to hear from you before pulling the testing patches.
One thought that occurs to me is that we should probably create a second
hash table test program alongside with the existing one.

The test program currently in the tree can also be used as an example of
how to use the hash table. The modifications you bring are interesting
for testing subtle corner-cases, but these transform the test program in
a synthetic workload that cannot be used as a usage example.

So, what are your thoughts about creating a second hash table test
program ? It can very well be derived from a copy of test_urcu_hash, no
problem there. We could event rename the current test_urcu_hash into
example_urcu_hash.c ?

Thanks,

Mathieu

> 
> Thanks,
> Lai
> 
> On 11/14/2011 12:50 PM, Lai Jiangshan wrote:
> > Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> > ---
> >  rculfhash.c      |   24 +++++++++++++++++++++++-
> >  urcu/rculfhash.h |   14 ++++++++++++++
> >  2 files changed, 37 insertions(+), 1 deletions(-)
> > 
> > diff --git a/rculfhash.c b/rculfhash.c
> > index cbfc79e..70f5863 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -1495,12 +1495,34 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  {
> >  	unsigned long size;
> >  
> > -	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> >  	size = rcu_dereference(ht->t.size);
> >  	_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
> >  	ht_count_add(ht, size, hash);
> >  }
> >  
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		unsigned long hash, struct cds_lfht_node *node)
> > +{
> > +	struct cds_lfht_node *new_node;
> > +
> > +	if (caa_unlikely(is_removed(iter->next)))
> > +		return false;
> > +
> > +	node->reverse_hash = bit_reverse_ulong(hash);
> > +	node->next = clear_flag(iter->next);
> > +	if (is_bucket(iter->next))
> > +		new_node = flag_bucket(node);
> > +	else
> > +		new_node = node;
> > +	if (uatomic_cmpxchg(&iter->node->next, iter->next,
> > +			new_node) != iter->next)
> > +		return false;
> > +
> > +	ht_count_add(ht, rcu_dereference(ht->t.size), hash);
> > +	return true;
> > +}
> > +
> >  struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> >  				unsigned long hash,
> >  				cds_lfht_match_fct match,
> > diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> > index 7d919d0..0f9bf44 100644
> > --- a/urcu/rculfhash.h
> > +++ b/urcu/rculfhash.h
> > @@ -250,6 +250,20 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> >  		struct cds_lfht_node *node);
> >  
> >  /*
> > + * cds_lfht_add_at - add a node to the hash table at the specified place.
> > + * @ht: the hash table.
> > + * @iter: the specified place to insert
> > + * @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.
> > + */
> > +bool cds_lfht_add_at(struct cds_lfht *ht, struct cds_lfht_iter *iter,
> > +		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.
> >   * @hash: the node's hash.
> 

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

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Lai Jiangshan]

On 11/18/2011 10:29 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> It seems that the testing patches have a strange problem, please wait
>> before merge it.
> 
> Hi Lai,
> 
> I'm still waiting to hear from you before pulling the testing patches.
> One thought that occurs to me is that we should probably create a second
> hash table test program alongside with the existing one.
> 
> The test program currently in the tree can also be used as an example of
> how to use the hash table. The modifications you bring are interesting
> for testing subtle corner-cases, but these transform the test program in
> a synthetic workload that cannot be used as a usage example.
> 
> So, what are your thoughts about creating a second hash table test
> program ? It can very well be derived from a copy of test_urcu_hash, no
> problem there. We could event rename the current test_urcu_hash into
> example_urcu_hash.c ?

Hi, Mathieu,

Did you miss the memory-management patches, you can merge them first.

Testing patches are not urgent/important, you can use original test-suit.
Testing patches need to be carefully reworked. The strange problem is
not a bug: The testing results sometimes(5%) are unstable. But I can't find
the reason.

Thanks,
Lai.

[ltt-dev] [PATCH 3/9] add cds_lfht_add_at()

[Mathieu Desnoyers]

Hi Lai,

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
 [...]
> Hi, Mathieu,
> 
> Did you miss the memory-management patches, you can merge them first.

I got them, just been busy on other things.

> Testing patches are not urgent/important, you can use original test-suit.
> Testing patches need to be carefully reworked. The strange problem is
> not a bug: The testing results sometimes(5%) are unstable. But I can't find
> the reason.

OK, it will be nice to pinpoint though :)

I'll have a look at the mm patches given they do not depend on the
testing patches.

Thanks!

Mathieu

> 
> Thanks,
> Lai.

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

[ltt-dev] [PATCH 4/9] new random generator

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index bae6ed2..a1aa660 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -32,6 +32,8 @@
 #include <assert.h>
 #include <sched.h>
 #include <errno.h>
+#include <sys/stat.h>
+#include <fcntl.h>
 
 #ifdef __linux__
 #include <syscall.h>
@@ -283,6 +285,120 @@ void rcu_copy_mutex_unlock(void)
 }
 
 /*
+ * Test random generator
+ *
+ * (copied from linux kernel)
+ *
+ * This is a maximally equidistributed combined Tausworthe generator
+ * based on code from GNU Scientific Library 1.5 (30 Jun 2004)
+ *
+ * x_n = (s1_n ^ s2_n ^ s3_n)
+ *
+ * s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
+ * s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
+ * s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
+ *
+ * The period of this generator is about 2^88.
+ *
+ * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
+ * Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
+ *
+ * This is available on the net from L'Ecuyer's home page,
+ *
+ * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
+ * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
+ *
+ * There is an erratum in the paper "Tables of Maximally
+ * Equidistributed Combined LFSR Generators", Mathematics of
+ * Computation, 68, 225 (1999), 261--269:
+ * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
+ *
+ *      ... the k_j most significant bits of z_j must be non-
+ *      zero, for each j. (Note: this restriction also applies to the
+ *      computer code given in [4], but was mistakenly not mentioned in
+ *      that paper.)
+ *
+ * This affects the seeding procedure by imposing the requirement
+ * s1 > 1, s2 > 7, s3 > 15.
+ *
+ */
+
+struct rand_state {
+	uint32_t s1, s2, s3;
+};
+
+static __thread struct rand_state rand_state;
+
+static uint32_t test_rand_get32(void)
+{
+	struct rand_state *state = &rand_state;
+#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
+
+	state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
+	state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
+	state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
+
+	return (state->s1 ^ state->s2 ^ state->s3);
+}
+
+static void test_rand_init(void)
+{
+	int urandom_fd;
+	struct rand_state *state = &rand_state;
+
+	urandom_fd = open("/dev/urandom", O_RDONLY);
+	assert(urandom_fd > 2);
+
+	do {
+		ssize_t size = sizeof(*state), ret;
+
+		while (size > 0) {
+			ret = read(urandom_fd, state, size);
+			assert(ret >= 0);
+			size -= ret;
+		}
+		state->s1 ^= (uint32_t)(unsigned long)state;
+	} while (state->s1 <= 1 || state->s2 <= 7 || state->s3 <= 15);
+
+	test_rand_get32();
+	close(urandom_fd);
+}
+
+#if (CAA_BITS_PER_LONG == 32)
+static inline unsigned long test_rand_get(void)
+{
+	return test_rand_get32();
+}
+#else
+static inline unsigned long test_rand_get(void)
+{
+	return ((unsigned long)test_rand_get32() << 32) | test_rand_get32();
+}
+#endif
+
+static __thread uint32_t random_bits;
+static __thread int nr_random_bits;
+
+static unsigned long test_rand_get_bits(int n)
+{
+	uint32_t result = random_bits;
+	int m = n;
+
+	assert(n > 0 && n < 32);
+
+	if (m > nr_random_bits) {
+		random_bits = test_rand_get32();
+		result |= random_bits << nr_random_bits;
+		m -= nr_random_bits;
+		nr_random_bits = 32;
+	}
+
+	random_bits >>= m;
+	nr_random_bits -= m;
+	return result & ((1UL << n) - 1);
+}
+
+/*
  * Hash function
  * Source: http://burtleburtle.net/bob/c/lookup3.c
  * Originally Public Domain
@@ -495,6 +611,7 @@ void *thr_reader(void *_count)
 			"reader", pthread_self(), (unsigned long)gettid());
 
 	set_affinity();
+	test_rand_init();
 
 	rcu_register_thread();
 
@@ -506,7 +623,7 @@ void *thr_reader(void *_count)
 	for (;;) {
 		rcu_read_lock();
 		cds_lfht_test_lookup(test_ht,
-			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
+			(void *)((test_rand_get() % lookup_pool_size) + lookup_pool_offset),
 			sizeof(void *), &iter);
 		node = cds_lfht_iter_get_test_node(&iter);
 		if (node == NULL) {
@@ -560,6 +677,7 @@ void *thr_writer(void *_count)
 			"writer", pthread_self(), (unsigned long)gettid());
 
 	set_affinity();
+	test_rand_init();
 
 	rcu_register_thread();
 
@@ -570,10 +688,10 @@ void *thr_writer(void *_count)
 
 	for (;;) {
 		if ((addremove == AR_ADD || add_only)
-				|| (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
+				|| (addremove == AR_RANDOM && test_rand_get_bits(1))) {
 			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),
+				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
 				sizeof(void *));
 			rcu_read_lock();
 			if (add_unique) {
@@ -607,7 +725,7 @@ void *thr_writer(void *_count)
 			/* May delete */
 			rcu_read_lock();
 			cds_lfht_test_lookup(test_ht,
-				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
+				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
 				sizeof(void *), &iter);
 			ret = cds_lfht_del(test_ht, &iter);
 			rcu_read_unlock();
@@ -622,7 +740,7 @@ void *thr_writer(void *_count)
 		//if (nr_writes % 100000 == 0) {
 		if (nr_writes % 1000 == 0) {
 			rcu_read_lock();
-			if (rand_r(&rand_lookup) & 1) {
+			if (test_rand_get_bits(1)) {
 				ht_resize(test_ht, 1);
 			} else {
 				ht_resize(test_ht, -1);
@@ -660,6 +778,7 @@ static int populate_hash(void)
 
 	if (!init_populate)
 		return 0;
+	test_rand_init();
 
 	if ((add_unique || add_replace) && init_populate * 10 > init_pool_size) {
 		printf("WARNING: required to populate %lu nodes (-k), but random "
@@ -670,7 +789,7 @@ static int populate_hash(void)
 	while (nr_add < init_populate) {
 		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),
+			(void *)((test_rand_get() % init_pool_size) + init_pool_offset),
 			sizeof(void *));
 		rcu_read_lock();
 		if (add_unique) {
-- 
1.7.4.4

[ltt-dev] [PATCH 4/9] new random generator

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |  131 +++++++++++++++++++++++++++++++++++++++++++++--
>  1 files changed, 125 insertions(+), 6 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index bae6ed2..a1aa660 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -32,6 +32,8 @@
>  #include <assert.h>
>  #include <sched.h>
>  #include <errno.h>
> +#include <sys/stat.h>
> +#include <fcntl.h>
>  
>  #ifdef __linux__
>  #include <syscall.h>
> @@ -283,6 +285,120 @@ void rcu_copy_mutex_unlock(void)
>  }
>  
>  /*
> + * Test random generator
> + *
> + * (copied from linux kernel)
> + *
> + * This is a maximally equidistributed combined Tausworthe generator
> + * based on code from GNU Scientific Library 1.5 (30 Jun 2004)
> + *
> + * x_n = (s1_n ^ s2_n ^ s3_n)
> + *
> + * s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
> + * s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
> + * s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
> + *
> + * The period of this generator is about 2^88.
> + *
> + * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
> + * Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
> + *
> + * This is available on the net from L'Ecuyer's home page,
> + *
> + * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
> + * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
> + *
> + * There is an erratum in the paper "Tables of Maximally
> + * Equidistributed Combined LFSR Generators", Mathematics of
> + * Computation, 68, 225 (1999), 261--269:
> + * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
> + *
> + *      ... the k_j most significant bits of z_j must be non-
> + *      zero, for each j. (Note: this restriction also applies to the
> + *      computer code given in [4], but was mistakenly not mentioned in
> + *      that paper.)
> + *
> + * This affects the seeding procedure by imposing the requirement
> + * s1 > 1, s2 > 7, s3 > 15.
> + *
> + */
> +
> +struct rand_state {
> +	uint32_t s1, s2, s3;
> +};
> +
> +static __thread struct rand_state rand_state;
> +
> +static uint32_t test_rand_get32(void)
> +{
> +	struct rand_state *state = &rand_state;
> +#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)

please add parenthesis around use of s, a, b, c, and d.

> +
> +	state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
> +	state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
> +	state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
> +

#undef TAUSWORTHE

(if only meant to be used within this function scope)

> +	return (state->s1 ^ state->s2 ^ state->s3);
> +}
> +
> +static void test_rand_init(void)
> +{
> +	int urandom_fd;
> +	struct rand_state *state = &rand_state;
> +
> +	urandom_fd = open("/dev/urandom", O_RDONLY);
> +	assert(urandom_fd > 2);

Instead of an assert, can we print a warning and fall-back on time(NULL)
instead ?

> +
> +	do {
> +		ssize_t size = sizeof(*state), ret;
> +
> +		while (size > 0) {
> +			ret = read(urandom_fd, state, size);
> +			assert(ret >= 0);
> +			size -= ret;
> +		}
> +		state->s1 ^= (uint32_t)(unsigned long)state;
> +	} while (state->s1 <= 1 || state->s2 <= 7 || state->s3 <= 15);
> +
> +	test_rand_get32();
> +	close(urandom_fd);
> +}
> +
> +#if (CAA_BITS_PER_LONG == 32)
> +static inline unsigned long test_rand_get(void)
> +{
> +	return test_rand_get32();
> +}
> +#else
> +static inline unsigned long test_rand_get(void)
> +{
> +	return ((unsigned long)test_rand_get32() << 32) | test_rand_get32();
> +}
> +#endif
> +
> +static __thread uint32_t random_bits;
> +static __thread int nr_random_bits;
> +
> +static unsigned long test_rand_get_bits(int n)

I think this function should use test_rand_get(), and allow n to go up
to CAA_BITS_PER_LONG.

Thanks,

Mathieu

> +{
> +	uint32_t result = random_bits;
> +	int m = n;
> +
> +	assert(n > 0 && n < 32);
> +
> +	if (m > nr_random_bits) {
> +		random_bits = test_rand_get32();
> +		result |= random_bits << nr_random_bits;
> +		m -= nr_random_bits;
> +		nr_random_bits = 32;
> +	}
> +
> +	random_bits >>= m;
> +	nr_random_bits -= m;
> +	return result & ((1UL << n) - 1);
> +}
> +
> +/*
>   * Hash function
>   * Source: http://burtleburtle.net/bob/c/lookup3.c
>   * Originally Public Domain
> @@ -495,6 +611,7 @@ void *thr_reader(void *_count)
>  			"reader", pthread_self(), (unsigned long)gettid());
>  
>  	set_affinity();
> +	test_rand_init();
>  
>  	rcu_register_thread();
>  
> @@ -506,7 +623,7 @@ void *thr_reader(void *_count)
>  	for (;;) {
>  		rcu_read_lock();
>  		cds_lfht_test_lookup(test_ht,
> -			(void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
> +			(void *)((test_rand_get() % lookup_pool_size) + lookup_pool_offset),
>  			sizeof(void *), &iter);
>  		node = cds_lfht_iter_get_test_node(&iter);
>  		if (node == NULL) {
> @@ -560,6 +677,7 @@ void *thr_writer(void *_count)
>  			"writer", pthread_self(), (unsigned long)gettid());
>  
>  	set_affinity();
> +	test_rand_init();
>  
>  	rcu_register_thread();
>  
> @@ -570,10 +688,10 @@ void *thr_writer(void *_count)
>  
>  	for (;;) {
>  		if ((addremove == AR_ADD || add_only)
> -				|| (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
> +				|| (addremove == AR_RANDOM && test_rand_get_bits(1))) {
>  			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),
> +				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
>  				sizeof(void *));
>  			rcu_read_lock();
>  			if (add_unique) {
> @@ -607,7 +725,7 @@ void *thr_writer(void *_count)
>  			/* May delete */
>  			rcu_read_lock();
>  			cds_lfht_test_lookup(test_ht,
> -				(void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
> +				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
>  				sizeof(void *), &iter);
>  			ret = cds_lfht_del(test_ht, &iter);
>  			rcu_read_unlock();
> @@ -622,7 +740,7 @@ void *thr_writer(void *_count)
>  		//if (nr_writes % 100000 == 0) {
>  		if (nr_writes % 1000 == 0) {
>  			rcu_read_lock();
> -			if (rand_r(&rand_lookup) & 1) {
> +			if (test_rand_get_bits(1)) {
>  				ht_resize(test_ht, 1);
>  			} else {
>  				ht_resize(test_ht, -1);
> @@ -660,6 +778,7 @@ static int populate_hash(void)
>  
>  	if (!init_populate)
>  		return 0;
> +	test_rand_init();
>  
>  	if ((add_unique || add_replace) && init_populate * 10 > init_pool_size) {
>  		printf("WARNING: required to populate %lu nodes (-k), but random "
> @@ -670,7 +789,7 @@ static int populate_hash(void)
>  	while (nr_add < init_populate) {
>  		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),
> +			(void *)((test_rand_get() % init_pool_size) + init_pool_offset),
>  			sizeof(void *));
>  		rcu_read_lock();
>  		if (add_unique) {
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 5/9] use random value for hash value directly

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index a1aa660..02d2c63 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -94,7 +94,6 @@ struct wr_count {
 	unsigned long remove;
 };
 
-static unsigned int __thread rand_lookup;
 static unsigned long __thread nr_add;
 static unsigned long __thread nr_addexist;
 static unsigned long __thread nr_del;
@@ -111,8 +110,7 @@ struct test_data {
 
 struct lfht_test_node {
 	struct cds_lfht_node node;
-	void *key;
-	unsigned int key_len;
+	unsigned long hash;
 	/* cache-cold for iteration */
 	struct rcu_head head;
 };
@@ -123,15 +121,6 @@ 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);
-	node->key = key;
-	node->key_len = key_len;
-}
-
 static inline struct lfht_test_node *
 cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
 {
@@ -153,12 +142,6 @@ static unsigned long init_populate;
 static int opt_auto_resize;
 static int add_only, add_unique, add_replace;
 
-static unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
-static unsigned long init_pool_size = DEFAULT_RAND_POOL,
-	lookup_pool_size = DEFAULT_RAND_POOL,
-	write_pool_size = DEFAULT_RAND_POOL;
-static int validate_lookup;
-
 static int count_pipe[2];
 
 static inline void loop_sleep(unsigned long l)
@@ -398,167 +381,23 @@ static unsigned long test_rand_get_bits(int n)
 	return result & ((1UL << n) - 1);
 }
 
-/*
- * Hash function
- * Source: http://burtleburtle.net/bob/c/lookup3.c
- * Originally Public Domain
- */
-
-#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
-
-#define mix(a, b, c) \
-do { \
-	a -= c; a ^= rot(c,  4); c += b; \
-	b -= a; b ^= rot(a,  6); a += c; \
-	c -= b; c ^= rot(b,  8); b += a; \
-	a -= c; a ^= rot(c, 16); c += b; \
-	b -= a; b ^= rot(a, 19); a += c; \
-	c -= b; c ^= rot(b,  4); b += a; \
-} while (0)
-
-#define final(a, b, c) \
-{ \
-	c ^= b; c -= rot(b, 14); \
-	a ^= c; a -= rot(c, 11); \
-	b ^= a; b -= rot(a, 25); \
-	c ^= b; c -= rot(b, 16); \
-	a ^= c; a -= rot(c,  4);\
-	b ^= a; b -= rot(a, 14); \
-	c ^= b; c -= rot(b, 24); \
-}
-
-static __attribute__((unused))
-uint32_t hash_u32(
-	const uint32_t *k,	/* the key, an array of uint32_t values */
-	size_t length,		/* the length of the key, in uint32_ts */
-	uint32_t initval)	/* the previous hash, or an arbitrary value */
-{
-	uint32_t a, b, c;
-
-	/* Set up the internal state */
-	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
-
-	/*----------------------------------------- handle most of the key */
-	while (length > 3) {
-		a += k[0];
-		b += k[1];
-		c += k[2];
-		mix(a, b, c);
-		length -= 3;
-		k += 3;
-	}
-
-	/*----------------------------------- handle the last 3 uint32_t's */
-	switch (length) {	/* all the case statements fall through */
-	case 3: c += k[2];
-	case 2: b += k[1];
-	case 1: a += k[0];
-		final(a, b, c);
-	case 0:			/* case 0: nothing left to add */
-		break;
-	}
-	/*---------------------------------------------- report the result */
-	return c;
-}
-
-static
-void hashword2(
-	const uint32_t *k,	/* the key, an array of uint32_t values */
-	size_t length,		/* the length of the key, in uint32_ts */
-	uint32_t *pc,		/* IN: seed OUT: primary hash value */
-	uint32_t *pb)		/* IN: more seed OUT: secondary hash value */
-{
-	uint32_t a, b, c;
-
-	/* Set up the internal state */
-	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
-	c += *pb;
-
-	/*----------------------------------------- handle most of the key */
-	while (length > 3) {
-		a += k[0];
-		b += k[1];
-		c += k[2];
-		mix(a, b, c);
-		length -= 3;
-		k += 3;
-	}
-
-	/*----------------------------------- handle the last 3 uint32_t's */
-	switch (length) {	/* all the case statements fall through */
-	case 3: c += k[2];
-	case 2: b += k[1];
-	case 1: a += k[0];
-		final(a, b, c);
-	case 0:			/* case 0: nothing left to add */
-		break;
-	}
-	/*---------------------------------------------- report the result */
-	*pc = c;
-	*pb = b;
-}
-
-#if (CAA_BITS_PER_LONG == 32)
-static
-unsigned long test_hash(void *_key, size_t length, unsigned long seed)
-{
-	unsigned int key = (unsigned int) _key;
-
-	assert(length == sizeof(unsigned int));
-	return hash_u32(&key, 1, seed);
-}
-#else
 static
-unsigned long test_hash(void *_key, size_t length, unsigned long seed)
+int lookup_first(struct cds_lfht_node *node, void *key)
 {
-	union {
-		uint64_t v64;
-		uint32_t v32[2];
-	} v;
-	union {
-		uint64_t v64;
-		uint32_t v32[2];
-	} key;
-
-	assert(length == sizeof(unsigned long));
-	v.v64 = (uint64_t) seed;
-	key.v64 = (uint64_t) _key;
-	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
-	return v.v64;
+	return 1;
 }
-#endif
 
-static
-unsigned long test_compare(void *key1, size_t key1_len,
-                           void *key2, size_t key2_len)
+static inline
+void lfht_test_node_init(struct lfht_test_node *node)
 {
-	if (caa_unlikely(key1_len != key2_len))
-		return -1;
-	assert(key1_len == sizeof(unsigned long));
-	if (key1 == key2)
-		return 0;
-	else
-		return 1;
+	cds_lfht_node_init(&node->node);
+	node->hash = test_rand_get();
 }
 
 static
 int test_match(struct cds_lfht_node *node, void *key)
 {
-	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
-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));
-
-	if (!cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
-			test_match, key, iter))
-		iter->node = iter->next = NULL;
+	return 0;
 }
 
 void *thr_count(void *arg)
@@ -604,7 +443,7 @@ void *thr_count(void *arg)
 void *thr_reader(void *_count)
 {
 	unsigned long long *count = _count;
-	struct lfht_test_node *node;
+	struct lfht_test_node node;
 	struct cds_lfht_iter iter;
 
 	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
@@ -621,16 +460,10 @@ void *thr_reader(void *_count)
 	cmm_smp_mb();
 
 	for (;;) {
+		lfht_test_node_init(&node);
+
 		rcu_read_lock();
-		cds_lfht_test_lookup(test_ht,
-			(void *)((test_rand_get() % lookup_pool_size) + lookup_pool_offset),
-			sizeof(void *), &iter);
-		node = cds_lfht_iter_get_test_node(&iter);
-		if (node == NULL) {
-			if (validate_lookup) {
-				printf("[ERROR] Lookup cannot find initial node.\n");
-				exit(-1);
-			}
+		if (!cds_lfht_lookup(test_ht, node.hash, test_match, &node, &iter)) {
 			lookup_fail++;
 		} else {
 			lookup_ok++;
@@ -690,23 +523,17 @@ void *thr_writer(void *_count)
 		if ((addremove == AR_ADD || add_only)
 				|| (addremove == AR_RANDOM && test_rand_get_bits(1))) {
 			node = malloc(sizeof(struct lfht_test_node));
-			lfht_test_node_init(node,
-				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
-				sizeof(void *));
+			lfht_test_node_init(node);
 			rcu_read_lock();
 			if (add_unique) {
-				ret_node = cds_lfht_add_unique(test_ht,
-					test_hash(node->key, node->key_len, TEST_HASH_SEED),
-					test_match, node->key, &node->node);
+				ret_node = cds_lfht_add_unique(test_ht, node->hash,
+					test_match, &node, &node->node);
 			} else {
 				if (add_replace)
-					ret_node = cds_lfht_add_replace(test_ht,
-							test_hash(node->key, node->key_len, TEST_HASH_SEED),
-							test_match, node->key, &node->node);
+					ret_node = cds_lfht_add_replace(test_ht, node->hash,
+							test_match, &node, &node->node);
 				else
-					cds_lfht_add(test_ht,
-						test_hash(node->key, node->key_len, TEST_HASH_SEED),
-						&node->node);
+					cds_lfht_add(test_ht, node->hash, &node->node);
 			}
 			rcu_read_unlock();
 			if (add_unique && ret_node != &node->node) {
@@ -724,9 +551,9 @@ void *thr_writer(void *_count)
 		} else {
 			/* May delete */
 			rcu_read_lock();
-			cds_lfht_test_lookup(test_ht,
-				(void *)((test_rand_get() % write_pool_size) + write_pool_offset),
-				sizeof(void *), &iter);
+			if (!cds_lfht_lookup(test_ht, test_rand_get(),
+					lookup_first, NULL, &iter))
+				cds_lfht_next(test_ht, &iter);
 			ret = cds_lfht_del(test_ht, &iter);
 			rcu_read_unlock();
 			if (ret == 0) {
@@ -780,31 +607,19 @@ static int populate_hash(void)
 		return 0;
 	test_rand_init();
 
-	if ((add_unique || add_replace) && init_populate * 10 > init_pool_size) {
-		printf("WARNING: required to populate %lu nodes (-k), but random "
-"pool is quite small (%lu values) and we are in add_unique (-u) or add_replace (-s) mode. Try with a "
-"larger random pool (-p option). This may take a while...\n", init_populate, init_pool_size);
-	}
-
 	while (nr_add < init_populate) {
 		node = malloc(sizeof(struct lfht_test_node));
-		lfht_test_node_init(node,
-			(void *)((test_rand_get() % init_pool_size) + init_pool_offset),
-			sizeof(void *));
+		lfht_test_node_init(node);
 		rcu_read_lock();
 		if (add_unique) {
-			ret_node = cds_lfht_add_unique(test_ht,
-				test_hash(node->key, node->key_len, TEST_HASH_SEED),
-				test_match, node->key, &node->node);
+			ret_node = cds_lfht_add_unique(test_ht, node->hash,
+				test_match, &node, &node->node);
 		} else {
 			if (add_replace)
-				ret_node = cds_lfht_add_replace(test_ht,
-						test_hash(node->key, node->key_len, TEST_HASH_SEED),
-						test_match, node->key, &node->node);
+				ret_node = cds_lfht_add_replace(test_ht, node->hash,
+						test_match, &node, &node->node);
 			else
-				cds_lfht_add(test_ht,
-					test_hash(node->key, node->key_len, TEST_HASH_SEED),
-					&node->node);
+				cds_lfht_add(test_ht, node->hash, &node->node);
 		}
 		rcu_read_unlock();
 		if (add_unique && ret_node != &node->node) {
@@ -859,13 +674,6 @@ void show_usage(int argc, char **argv)
 	printf("        [-i] Add only (no removal).\n");
 	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
 	printf("        [-A] Automatically resize hash table.\n");
-	printf("        [-R offset] Lookup pool offset.\n");
-	printf("        [-S offset] Write pool offset.\n");
-	printf("        [-T offset] Init pool offset.\n");
-	printf("        [-M size] Lookup pool size.\n");
-	printf("        [-N size] Write pool size.\n");
-	printf("        [-O size] Init pool size.\n");
-	printf("        [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
 	printf("\n\n");
 }
 
@@ -984,26 +792,6 @@ int main(int argc, char **argv)
 		case 'A':
 			opt_auto_resize = 1;
 			break;
-		case 'R':
-			lookup_pool_offset = atol(argv[++i]);
-			break;
-		case 'S':
-			write_pool_offset = atol(argv[++i]);
-			break;
-		case 'T':
-			init_pool_offset = atol(argv[++i]);
-			break;
-		case 'M':
-			lookup_pool_size = atol(argv[++i]);
-			break;
-		case 'N':
-			write_pool_size = atol(argv[++i]);
-			break;
-		case 'O':
-			init_pool_size = atol(argv[++i]);
-			break;
-		case 'V':
-			validate_lookup = 1;
 			break;
 
 		}
@@ -1065,12 +853,6 @@ int main(int argc, char **argv)
 		add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
 	printf_verbose("Initial hash table size: %lu buckets.\n", init_hash_size);
 	printf_verbose("Minimum hash alloc size: %lu buckets.\n", min_hash_alloc_size);
-	printf_verbose("Init pool size offset %lu size %lu.\n",
-		init_pool_offset, init_pool_size);
-	printf_verbose("Lookup pool size offset %lu size %lu.\n",
-		lookup_pool_offset, lookup_pool_size);
-	printf_verbose("Update pool size offset %lu size %lu.\n",
-		write_pool_offset, write_pool_size);
 	printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
 			"main", pthread_self(), (unsigned long)gettid());
 
-- 
1.7.4.4

[ltt-dev] [PATCH 5/9] use random value for hash value directly

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
[...]
>  struct lfht_test_node {
>  	struct cds_lfht_node node;
> -	void *key;
> -	unsigned int key_len;
> +	unsigned long hash;
>  	/* cache-cold for iteration */
>  	struct rcu_head head;

I'm really unsure about this. One of the test-case should be to walk
through identical-hash-value-chain and find the right node by matching
its key. If we make the hash equal to the key, we don't test the "match"
code anymore.

Thanks,

Mathieu

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

[ltt-dev] [PATCH 5/9] use random value for hash value directly

[Lai Jiangshan]

On 11/15/2011 07:20 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> [...]
>>  struct lfht_test_node {
>>  	struct cds_lfht_node node;
>> -	void *key;
>> -	unsigned int key_len;
>> +	unsigned long hash;
>>  	/* cache-cold for iteration */
>>  	struct rcu_head head;
> 
> I'm really unsure about this. 


The key is just a black box for a hash table.
hash table focus on hash value mainly, so we can use random value for
hash value when testing if the random values are good(very random).


> One of the test-case should be to walk
> through identical-hash-value-chain and find the right node by matching
> its key. If we make the hash equal to the key, we don't test the "match"
> code anymore.
> 

there is no duplicated key/node for this patch.

[ltt-dev] [PATCH 6/9] test hash value Confilict with buckets

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 02d2c63..eb42522 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -141,6 +141,7 @@ static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE;
 static unsigned long init_populate;
 static int opt_auto_resize;
 static int add_only, add_unique, add_replace;
+static int opt_test_bucket_conflict;
 
 static int count_pipe[2];
 
@@ -390,8 +391,22 @@ int lookup_first(struct cds_lfht_node *node, void *key)
 static inline
 void lfht_test_node_init(struct lfht_test_node *node)
 {
+	unsigned long hash = test_rand_get();
+
 	cds_lfht_node_init(&node->node);
-	node->hash = test_rand_get();
+
+	if (opt_test_bucket_conflict) {
+#if (CAA_BITS_PER_LONG == 32)
+		int hash_bits= test_rand_get_bits(5);
+#else
+		int hash_bits= test_rand_get_bits(6);
+#endif
+
+		if (hash_bits > 4)
+			hash &= (1UL << hash_bits) - 1;
+	}
+
+	node->hash = hash;
 }
 
 static
@@ -674,6 +689,7 @@ void show_usage(int argc, char **argv)
 	printf("        [-i] Add only (no removal).\n");
 	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
 	printf("        [-A] Automatically resize hash table.\n");
+	printf("	[-C] Use some hash value Confilict with buckets.\n");
 	printf("\n\n");
 }
 
@@ -792,6 +808,8 @@ int main(int argc, char **argv)
 		case 'A':
 			opt_auto_resize = 1;
 			break;
+		case 'C':
+			opt_test_bucket_conflict = 1;
 			break;
 
 		}
-- 
1.7.4.4

[ltt-dev] [PATCH 6/9] test hash value Confilict with buckets

[Mathieu Desnoyers]

"Confilict" -> "conflict"

This increases conflicts by restricting the pool of random numbers to a
limited number of bits. Actually, this approach replaces the "pool size"
parameters I already have there, with slightly less flexibility though.
Please look into the "random number pool size" to try to achieve the
same effect.

Thanks,

Mathieu

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   20 +++++++++++++++++++-
>  1 files changed, 19 insertions(+), 1 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 02d2c63..eb42522 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -141,6 +141,7 @@ static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE;
>  static unsigned long init_populate;
>  static int opt_auto_resize;
>  static int add_only, add_unique, add_replace;
> +static int opt_test_bucket_conflict;
>  
>  static int count_pipe[2];
>  
> @@ -390,8 +391,22 @@ int lookup_first(struct cds_lfht_node *node, void *key)
>  static inline
>  void lfht_test_node_init(struct lfht_test_node *node)
>  {
> +	unsigned long hash = test_rand_get();
> +
>  	cds_lfht_node_init(&node->node);
> -	node->hash = test_rand_get();
> +
> +	if (opt_test_bucket_conflict) {
> +#if (CAA_BITS_PER_LONG == 32)
> +		int hash_bits= test_rand_get_bits(5);
> +#else
> +		int hash_bits= test_rand_get_bits(6);
> +#endif
> +
> +		if (hash_bits > 4)
> +			hash &= (1UL << hash_bits) - 1;
> +	}
> +
> +	node->hash = hash;
>  }
>  
>  static
> @@ -674,6 +689,7 @@ void show_usage(int argc, char **argv)
>  	printf("        [-i] Add only (no removal).\n");
>  	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
>  	printf("        [-A] Automatically resize hash table.\n");
> +	printf("	[-C] Use some hash value Confilict with buckets.\n");
>  	printf("\n\n");
>  }
>  
> @@ -792,6 +808,8 @@ int main(int argc, char **argv)
>  		case 'A':
>  			opt_auto_resize = 1;
>  			break;
> +		case 'C':
> +			opt_test_bucket_conflict = 1;
>  			break;
>  
>  		}
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 6/9] test hash value Confilict with buckets

[Lai Jiangshan]

On 11/15/2011 07:22 PM, Mathieu Desnoyers wrote:
> "Confilict" -> "conflict"
> 
> This increases conflicts by restricting the pool of random numbers to a
> limited number of bits. Actually, this approach replaces the "pool size"
> parameters I already have there, with slightly less flexibility though.
> Please look into the "random number pool size" to try to achieve the
> same effect.

I missed something? pool size in the original code is constant when the test
is started.

And when the hash table is larger/equal than the pool, many bucket is unused
and cause long chain in a bucket.

> 
> Thanks,
> 
> Mathieu
> 
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  tests/test_urcu_hash.c |   20 +++++++++++++++++++-
>>  1 files changed, 19 insertions(+), 1 deletions(-)
>>
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index 02d2c63..eb42522 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -141,6 +141,7 @@ static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE;
>>  static unsigned long init_populate;
>>  static int opt_auto_resize;
>>  static int add_only, add_unique, add_replace;
>> +static int opt_test_bucket_conflict;
>>  
>>  static int count_pipe[2];
>>  
>> @@ -390,8 +391,22 @@ int lookup_first(struct cds_lfht_node *node, void *key)
>>  static inline
>>  void lfht_test_node_init(struct lfht_test_node *node)
>>  {
>> +	unsigned long hash = test_rand_get();
>> +
>>  	cds_lfht_node_init(&node->node);
>> -	node->hash = test_rand_get();
>> +
>> +	if (opt_test_bucket_conflict) {
>> +#if (CAA_BITS_PER_LONG == 32)
>> +		int hash_bits= test_rand_get_bits(5);
>> +#else
>> +		int hash_bits= test_rand_get_bits(6);
>> +#endif
>> +
>> +		if (hash_bits > 4)
>> +			hash &= (1UL << hash_bits) - 1;
>> +	}
>> +
>> +	node->hash = hash;
>>  }
>>  
>>  static
>> @@ -674,6 +689,7 @@ void show_usage(int argc, char **argv)
>>  	printf("        [-i] Add only (no removal).\n");
>>  	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
>>  	printf("        [-A] Automatically resize hash table.\n");
>> +	printf("	[-C] Use some hash value Confilict with buckets.\n");
>>  	printf("\n\n");
>>  }
>>  
>> @@ -792,6 +808,8 @@ int main(int argc, char **argv)
>>  		case 'A':
>>  			opt_auto_resize = 1;
>>  			break;
>> +		case 'C':
>> +			opt_test_bucket_conflict = 1;
>>  			break;
>>  
>>  		}
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 7/9] add identical-hash-value-chain test

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index eb42522..3730c2b 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -111,6 +111,7 @@ struct test_data {
 struct lfht_test_node {
 	struct cds_lfht_node node;
 	unsigned long hash;
+	unsigned long orig_hash;
 	/* cache-cold for iteration */
 	struct rcu_head head;
 };
@@ -142,6 +143,7 @@ static unsigned long init_populate;
 static int opt_auto_resize;
 static int add_only, add_unique, add_replace;
 static int opt_test_bucket_conflict;
+static int opt_duplicated;
 
 static int count_pipe[2];
 
@@ -395,6 +397,19 @@ void lfht_test_node_init(struct lfht_test_node *node)
 
 	cds_lfht_node_init(&node->node);
 
+	/* 25% duplicated hash value */
+	if (opt_duplicated && test_rand_get_bits(2) == 0) {
+		struct cds_lfht_iter iter;
+
+		if (!cds_lfht_lookup(test_ht, test_rand_get(),
+				lookup_first, NULL, &iter))
+			cds_lfht_next(test_ht, &iter);
+		if (iter.node)
+			hash = to_test_node(iter.node)->orig_hash;
+	}
+
+	node->orig_hash = hash;
+
 	if (opt_test_bucket_conflict) {
 #if (CAA_BITS_PER_LONG == 32)
 		int hash_bits= test_rand_get_bits(5);
@@ -690,6 +705,7 @@ void show_usage(int argc, char **argv)
 	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
 	printf("        [-A] Automatically resize hash table.\n");
 	printf("	[-C] Use some hash value Confilict with buckets.\n");
+	printf("	[-D] Test Duplicated hash values and nodes.\n");
 	printf("\n\n");
 }
 
@@ -810,6 +826,8 @@ int main(int argc, char **argv)
 			break;
 		case 'C':
 			opt_test_bucket_conflict = 1;
+		case 'D':
+			opt_duplicated = 1;
 			break;
 
 		}
-- 
1.7.4.4

[ltt-dev] [PATCH 7/9] add identical-hash-value-chain test

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   18 ++++++++++++++++++
>  1 files changed, 18 insertions(+), 0 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index eb42522..3730c2b 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -111,6 +111,7 @@ struct test_data {
>  struct lfht_test_node {
>  	struct cds_lfht_node node;
>  	unsigned long hash;
> +	unsigned long orig_hash;

Is it just me or orig_hash is never populated ?

Thanks,

Mathieu

>  	/* cache-cold for iteration */
>  	struct rcu_head head;
>  };
> @@ -142,6 +143,7 @@ static unsigned long init_populate;
>  static int opt_auto_resize;
>  static int add_only, add_unique, add_replace;
>  static int opt_test_bucket_conflict;
> +static int opt_duplicated;
>  
>  static int count_pipe[2];
>  
> @@ -395,6 +397,19 @@ void lfht_test_node_init(struct lfht_test_node *node)
>  
>  	cds_lfht_node_init(&node->node);
>  
> +	/* 25% duplicated hash value */
> +	if (opt_duplicated && test_rand_get_bits(2) == 0) {
> +		struct cds_lfht_iter iter;
> +
> +		if (!cds_lfht_lookup(test_ht, test_rand_get(),
> +				lookup_first, NULL, &iter))
> +			cds_lfht_next(test_ht, &iter);
> +		if (iter.node)
> +			hash = to_test_node(iter.node)->orig_hash;
> +	}
> +
> +	node->orig_hash = hash;
> +
>  	if (opt_test_bucket_conflict) {
>  #if (CAA_BITS_PER_LONG == 32)
>  		int hash_bits= test_rand_get_bits(5);
> @@ -690,6 +705,7 @@ void show_usage(int argc, char **argv)
>  	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
>  	printf("        [-A] Automatically resize hash table.\n");
>  	printf("	[-C] Use some hash value Confilict with buckets.\n");
> +	printf("	[-D] Test Duplicated hash values and nodes.\n");
>  	printf("\n\n");
>  }
>  
> @@ -810,6 +826,8 @@ int main(int argc, char **argv)
>  			break;
>  		case 'C':
>  			opt_test_bucket_conflict = 1;
> +		case 'D':
> +			opt_duplicated = 1;
>  			break;
>  
>  		}
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 7/9] add identical-hash-value-chain test

[Lai Jiangshan]

On 11/15/2011 07:24 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  tests/test_urcu_hash.c |   18 ++++++++++++++++++
>>  1 files changed, 18 insertions(+), 0 deletions(-)
>>
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index eb42522..3730c2b 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -111,6 +111,7 @@ struct test_data {
>>  struct lfht_test_node {
>>  	struct cds_lfht_node node;
>>  	unsigned long hash;
>> +	unsigned long orig_hash;
> 
> Is it just me or orig_hash is never populated ?
> 
> Thanks,
> 
> Mathieu
> 
>>  	/* cache-cold for iteration */
>>  	struct rcu_head head;
>>  };
>> @@ -142,6 +143,7 @@ static unsigned long init_populate;
>>  static int opt_auto_resize;
>>  static int add_only, add_unique, add_replace;
>>  static int opt_test_bucket_conflict;
>> +static int opt_duplicated;
>>  
>>  static int count_pipe[2];
>>  
>> @@ -395,6 +397,19 @@ void lfht_test_node_init(struct lfht_test_node *node)
>>  
>>  	cds_lfht_node_init(&node->node);
>>  
>> +	/* 25% duplicated hash value */
>> +	if (opt_duplicated && test_rand_get_bits(2) == 0) {
>> +		struct cds_lfht_iter iter;
>> +
>> +		if (!cds_lfht_lookup(test_ht, test_rand_get(),
>> +				lookup_first, NULL, &iter))
>> +			cds_lfht_next(test_ht, &iter);
>> +		if (iter.node)
>> +			hash = to_test_node(iter.node)->orig_hash;

use here
for a identical-hash candidate node

>> +	}
>> +
>> +	node->orig_hash = hash;

init here

>> +
>>  	if (opt_test_bucket_conflict) {
>>  #if (CAA_BITS_PER_LONG == 32)
>>  		int hash_bits= test_rand_get_bits(5);
>> @@ -690,6 +705,7 @@ void show_usage(int argc, char **argv)
>>  	printf("        [-k nr_nodes] Number of nodes to insert initially.\n");
>>  	printf("        [-A] Automatically resize hash table.\n");
>>  	printf("	[-C] Use some hash value Confilict with buckets.\n");
>> +	printf("	[-D] Test Duplicated hash values and nodes.\n");
>>  	printf("\n\n");
>>  }
>>  
>> @@ -810,6 +826,8 @@ int main(int argc, char **argv)
>>  			break;
>>  		case 'C':
>>  			opt_test_bucket_conflict = 1;
>> +		case 'D':
>> +			opt_duplicated = 1;
>>  			break;
>>  
>>  		}
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 8/9] add duplicated node test

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 3730c2b..964a4e1 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -111,6 +111,7 @@ struct test_data {
 struct lfht_test_node {
 	struct cds_lfht_node node;
 	unsigned long hash;
+	unsigned long dup;
 	unsigned long orig_hash;
 	/* cache-cold for iteration */
 	struct rcu_head head;
@@ -406,6 +407,8 @@ void lfht_test_node_init(struct lfht_test_node *node)
 			cds_lfht_next(test_ht, &iter);
 		if (iter.node)
 			hash = to_test_node(iter.node)->orig_hash;
+
+		node->dup = test_rand_get_bits(2);
 	}
 
 	node->orig_hash = hash;
@@ -427,6 +430,15 @@ void lfht_test_node_init(struct lfht_test_node *node)
 static
 int test_match(struct cds_lfht_node *node, void *key)
 {
+	struct lfht_test_node *u = to_test_node(node), *v = key;
+
+	if (caa_likely(u->hash != v->hash))
+		return 0;
+
+	/* 56.25% (100% * 9 / 16) duplicated when hash value are the same */
+	if (u->dup && u->dup == v->dup)
+		return 1;
+
 	return 0;
 }
 
-- 
1.7.4.4

[ltt-dev] [PATCH 8/9] add duplicated node test

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   12 ++++++++++++
>  1 files changed, 12 insertions(+), 0 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 3730c2b..964a4e1 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -111,6 +111,7 @@ struct test_data {
>  struct lfht_test_node {
>  	struct cds_lfht_node node;
>  	unsigned long hash;
> +	unsigned long dup;
>  	unsigned long orig_hash;
>  	/* cache-cold for iteration */
>  	struct rcu_head head;
> @@ -406,6 +407,8 @@ void lfht_test_node_init(struct lfht_test_node *node)
>  			cds_lfht_next(test_ht, &iter);
>  		if (iter.node)
>  			hash = to_test_node(iter.node)->orig_hash;
> +
> +		node->dup = test_rand_get_bits(2);
>  	}
>  
>  	node->orig_hash = hash;
> @@ -427,6 +430,15 @@ void lfht_test_node_init(struct lfht_test_node *node)
>  static
>  int test_match(struct cds_lfht_node *node, void *key)
>  {
> +	struct lfht_test_node *u = to_test_node(node), *v = key;
> +
> +	if (caa_likely(u->hash != v->hash))
> +		return 0;
> +
> +	/* 56.25% (100% * 9 / 16) duplicated when hash value are the same */
> +	if (u->dup && u->dup == v->dup)
> +		return 1;

Oh, I see, so you use a flag in the node to specify if it is duplicated.
This is twisted ;)

Hrm, but cds_lfht_next_duplicate needs to follow next pointers to get
the duplicates, so I don't see how this approach works with the
rculfhash code.

It might be simpler to just create a physical duplicate and add it to
the table rather than this flag scheme. This would end up testing the
normal use of the table rather than a use-case nobody will use in
practice.

Thanks,

Mathieu

> +
>  	return 0;
>  }
>  
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 8/9] add duplicated node test

[Lai Jiangshan]

On 11/15/2011 07:31 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  tests/test_urcu_hash.c |   12 ++++++++++++
>>  1 files changed, 12 insertions(+), 0 deletions(-)
>>
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index 3730c2b..964a4e1 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -111,6 +111,7 @@ struct test_data {
>>  struct lfht_test_node {
>>  	struct cds_lfht_node node;
>>  	unsigned long hash;
>> +	unsigned long dup;
>>  	unsigned long orig_hash;
>>  	/* cache-cold for iteration */
>>  	struct rcu_head head;
>> @@ -406,6 +407,8 @@ void lfht_test_node_init(struct lfht_test_node *node)
>>  			cds_lfht_next(test_ht, &iter);
>>  		if (iter.node)
>>  			hash = to_test_node(iter.node)->orig_hash;
>> +
>> +		node->dup = test_rand_get_bits(2);
>>  	}
>>  
>>  	node->orig_hash = hash;
>> @@ -427,6 +430,15 @@ void lfht_test_node_init(struct lfht_test_node *node)
>>  static
>>  int test_match(struct cds_lfht_node *node, void *key)
>>  {
>> +	struct lfht_test_node *u = to_test_node(node), *v = key;
>> +
>> +	if (caa_likely(u->hash != v->hash))
>> +		return 0;
>> +
>> +	/* 56.25% (100% * 9 / 16) duplicated when hash value are the same */
>> +	if (u->dup && u->dup == v->dup)
>> +		return 1;
> 
> Oh, I see, so you use a flag in the node to specify if it is duplicated.
> This is twisted ;)
> 
> Hrm, but cds_lfht_next_duplicate needs to follow next pointers to get
> the duplicates, so I don't see how this approach works with the
> rculfhash code.


this new test_match() has:
any a:		test_match(a, a)				(*)
any a, b:	test_match(a, b) -> test_match(b, a)
any a, b, c:	test_match(a, b) && test_match(b, c) -> test_match(a, c)

So it is a correct code.
((*) The last line of test_match() should be "return u == v",
but in the code we don't use test_match(a, a), so we don't handle it)

> 
> It might be simpler to just create a physical duplicate and add it to
> the table rather than this flag scheme. 

User define the definition of the "node duplicate".
raw fingerprints of a finger are not physical duplicate, but they can "match"
with each other.

> This would end up testing the
> normal use of the table rather than a use-case nobody will use in
> practice.

I try to hide the key for test, it is already a use-case nobody will use in practice.

But I think:
We can just focus on the hash value, not the key:
	Easy add types of the nodes.
	make test flexible.
	avoid test only any selected hash function.

Thanks,
Lai


> 
> Thanks,
> 
> Mathieu
> 
>> +
>>  	return 0;
>>  }
>>  
>> -- 
>> 1.7.4.4
>>
> 

[ltt-dev] [PATCH 9/9] change strategy for AR_RANDOM

[Lai Jiangshan]

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

diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 964a4e1..f07f0d4 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -540,6 +540,37 @@ void free_node_cb(struct rcu_head *head)
 	free(node);
 }
 
+static inline
+int thr_writer_add(void)
+{
+	static __thread int addremove_thread;
+	unsigned addremove_random;
+
+	if (add_only)
+		return 1;
+
+	if (addremove == AR_ADD)
+		return 1;
+
+	if (addremove == AR_REMOVE)
+		return 0;
+
+	addremove_random = test_rand_get_bits(2);
+	if (addremove_random < 2)
+		return addremove_random;
+
+	while (caa_unlikely(!addremove_thread))
+		addremove_thread = test_rand_get_bits(16) - (1UL << 15);
+
+	if (addremove_thread > 0) {
+		addremove_thread--;
+		return 1;
+	} else {
+		addremove_thread++;
+		return 0;
+	}
+}
+
 void *thr_writer(void *_count)
 {
 	struct lfht_test_node *node;
@@ -562,8 +593,7 @@ void *thr_writer(void *_count)
 	cmm_smp_mb();
 
 	for (;;) {
-		if ((addremove == AR_ADD || add_only)
-				|| (addremove == AR_RANDOM && test_rand_get_bits(1))) {
+		if (thr_writer_add()) {
 			node = malloc(sizeof(struct lfht_test_node));
 			lfht_test_node_init(node);
 			rcu_read_lock();
-- 
1.7.4.4

[ltt-dev] [PATCH 9/9] change strategy for AR_RANDOM

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  tests/test_urcu_hash.c |   34 ++++++++++++++++++++++++++++++++--
>  1 files changed, 32 insertions(+), 2 deletions(-)
> 
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 964a4e1..f07f0d4 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -540,6 +540,37 @@ void free_node_cb(struct rcu_head *head)
>  	free(node);
>  }
>  
> +static inline
> +int thr_writer_add(void)
> +{
> +	static __thread int addremove_thread;
> +	unsigned addremove_random;
> +
> +	if (add_only)
> +		return 1;
> +
> +	if (addremove == AR_ADD)
> +		return 1;
> +
> +	if (addremove == AR_REMOVE)
> +		return 0;
> +
> +	addremove_random = test_rand_get_bits(2);
> +	if (addremove_random < 2)
> +		return addremove_random;
> +
> +	while (caa_unlikely(!addremove_thread))
> +		addremove_thread = test_rand_get_bits(16) - (1UL << 15);
> +
> +	if (addremove_thread > 0) {
> +		addremove_thread--;
> +		return 1;
> +	} else {
> +		addremove_thread++;
> +		return 0;
> +	}

Can you explain what this part of the change does ? I am slightly
uncomfortable about a while () loop in there too that depends on random
results.

Thanks,

Mathieu

> +}
> +
>  void *thr_writer(void *_count)
>  {
>  	struct lfht_test_node *node;
> @@ -562,8 +593,7 @@ void *thr_writer(void *_count)
>  	cmm_smp_mb();
>  
>  	for (;;) {
> -		if ((addremove == AR_ADD || add_only)
> -				|| (addremove == AR_RANDOM && test_rand_get_bits(1))) {
> +		if (thr_writer_add()) {
>  			node = malloc(sizeof(struct lfht_test_node));
>  			lfht_test_node_init(node);
>  			rcu_read_lock();
> -- 
> 1.7.4.4
> 

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

[ltt-dev] [PATCH 9/9] change strategy for AR_RANDOM

[Lai Jiangshan]

On 11/15/2011 07:35 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>> ---
>>  tests/test_urcu_hash.c |   34 ++++++++++++++++++++++++++++++++--
>>  1 files changed, 32 insertions(+), 2 deletions(-)
>>
>> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
>> index 964a4e1..f07f0d4 100644
>> --- a/tests/test_urcu_hash.c
>> +++ b/tests/test_urcu_hash.c
>> @@ -540,6 +540,37 @@ void free_node_cb(struct rcu_head *head)
>>  	free(node);
>>  }
>>  
>> +static inline
>> +int thr_writer_add(void)
>> +{
>> +	static __thread int addremove_thread;
>> +	unsigned addremove_random;
>> +
>> +	if (add_only)
>> +		return 1;
>> +
>> +	if (addremove == AR_ADD)
>> +		return 1;
>> +
>> +	if (addremove == AR_REMOVE)
>> +		return 0;
>> +
>> +	addremove_random = test_rand_get_bits(2);
>> +	if (addremove_random < 2)
>> +		return addremove_random;
>> +
>> +	while (caa_unlikely(!addremove_thread))
>> +		addremove_thread = test_rand_get_bits(16) - (1UL << 15);
>> +
>> +	if (addremove_thread > 0) {
>> +		addremove_thread--;
>> +		return 1;
>> +	} else {
>> +		addremove_thread++;
>> +		return 0;
>> +	}
> 
> Can you explain what this part of the change does ? 

It only change the behavior when AR_RANDOM.

I want to test this case:
add     a lot of nodes to the hash table but delete seldom in period in a thread.
delete                                       add


> I am slightly
> uncomfortable about a while () loop in there too that depends on random
> results.
> 


I can change to

if (caa_unlikely(!addremove_thread)) {
	addremove_thread = test_rand_get_bits(16) - (1UL << 15);
	if (caa_unlikely(!addremove_thread))
		return test_rand_get_bits(1);
}

Thanks,
Lai