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

Lai Jiangshan laijs at cn.fujitsu.com
Sun Nov 13 23:50:55 EST 2011


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





More information about the lttng-dev mailing list