From mboxrd@z Thu Jan 1 00:00:00 1970 From: laijs@cn.fujitsu.com (Lai Jiangshan) Date: Mon, 14 Nov 2011 12:50:55 +0800 Subject: [ltt-dev] [PATCH 5/9] use random value for hash value directly In-Reply-To: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> References: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> Message-ID: <1321246259-21223-6-git-send-email-laijs@cn.fujitsu.com> Signed-off-by: Lai Jiangshan --- 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