[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