X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=0af6eebf6b781caa4edf0bc35116afa0991b92c6;hp=d7fe4c877c3d5a78cb8d81c15f69b515a7738af3;hb=6d5c0ca90ae4e999cdf4366ff615a6c619e7257e;hpb=f000907d757239af9a08625b850b93b4ef6db508 diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index d7fe4c8..0af6eeb 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -37,8 +37,8 @@ #include #endif -#define HASH_SIZE 32 -#define RAND_POOL 1000 +#define DEFAULT_HASH_SIZE 32 +#define DEFAULT_RAND_POOL 1000000 /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */ #define CACHE_LINE_SIZE 4096 @@ -70,6 +70,12 @@ static inline pid_t gettid(void) #include #include +struct wr_count { + unsigned long update_ops; + unsigned long add; + unsigned long remove; +}; + static unsigned int __thread rand_lookup; static unsigned long __thread nr_add; static unsigned long __thread nr_addexist; @@ -94,6 +100,10 @@ static unsigned long duration; /* read-side C.S. duration, in loops */ static unsigned long rduration; +static unsigned long init_hash_size = DEFAULT_HASH_SIZE; +static unsigned long rand_pool = DEFAULT_RAND_POOL; +static int add_only, add_unique; + static inline void loop_sleep(unsigned long l) { while(l-- != 0) @@ -181,22 +191,148 @@ void rcu_copy_mutex_unlock(void) } } +/* + * 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 -unsigned long test_hash(void *_hashseed, void *_key) +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 long seed = (unsigned long) _hashseed; unsigned long key = (unsigned long) _key; unsigned long v; - v = key ^ seed; - v ^= v << 8; - v ^= v << 16; - v ^= v << 27; - v ^= v >> 8; - v ^= v >> 16; - v ^= v >> 27; + assert(length == sizeof(unsigned long)); + return hash_u32(&v, 1, seed); +} +#else +static +unsigned long test_hash(void *_key, size_t length, unsigned long seed) +{ + 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; +} +#endif - return v; +static +unsigned long test_compare(void *key1, size_t key1_len, + void *key2, size_t key2_len) +{ + if (unlikely(key1_len != key2_len)) + return -1; + assert(key1_len == sizeof(unsigned long)); + if (key1 == key2) + return 0; + else + return 1; } void *thr_reader(void *_count) @@ -219,7 +355,8 @@ void *thr_reader(void *_count) for (;;) { rcu_read_lock(); node = ht_lookup(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); + (void *)(unsigned long)(rand_r(&rand_lookup) % rand_pool), + sizeof(void *)); if (node == NULL) lookup_fail++; else @@ -254,8 +391,8 @@ void free_node_cb(struct rcu_head *head) void *thr_writer(void *_count) { - struct rcu_ht_node *node; - unsigned long long *count = _count; + struct rcu_ht_node *node, *ret_node; + struct wr_count *count = _count; int ret; printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -271,20 +408,28 @@ void *thr_writer(void *_count) cmm_smp_mb(); for (;;) { - if (rand_r(&rand_lookup) & 1) { + if (add_only || rand_r(&rand_lookup) & 1) { node = malloc(sizeof(struct rcu_ht_node)); rcu_read_lock(); ht_node_init(node, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), - (void *) 0x42); - ht_add(test_ht, node); + (void *)(unsigned long)(rand_r(&rand_lookup) % rand_pool), + sizeof(void *)); + if (add_unique) + ret_node = ht_add_unique(test_ht, node); + else + ht_add(test_ht, node); rcu_read_unlock(); - nr_add++; + if (add_unique && ret_node != node) { + free(node); + nr_addexist++; + } else + nr_add++; } else { /* May delete */ rcu_read_lock(); node = ht_lookup(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); + (void *)(unsigned long)(rand_r(&rand_lookup) % rand_pool), + sizeof(void *)); if (node) ret = ht_remove(test_ht, node); else @@ -322,7 +467,9 @@ void *thr_writer(void *_count) printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, " "nr_delnoent %lu\n", pthread_self(), nr_add, nr_addexist, nr_del, nr_delnoent); - *count = nr_writes; + count->update_ops = nr_writes; + count->add = nr_add; + count->remove = nr_del; return ((void*)2); } @@ -336,6 +483,10 @@ void show_usage(int argc, char **argv) printf(" [-c duration] (reader C.S. duration (in loops))"); printf(" [-v] (verbose output)"); printf(" [-a cpu#] [-a cpu#]... (affinity)"); + printf(" [-p size] (random key value pool size)"); + printf(" [-h size] (initial hash table size)"); + printf(" [-u] Uniquify add."); + printf(" [-i] Add only (no removal)."); printf("\n"); } @@ -344,8 +495,11 @@ int main(int argc, char **argv) int err; pthread_t *tid_reader, *tid_writer; void *tret; - unsigned long long *count_reader, *count_writer; - unsigned long long tot_reads = 0, tot_writes = 0; + unsigned long long *count_reader; + struct wr_count *count_writer; + unsigned long long tot_reads = 0, tot_writes = 0, + tot_add = 0, tot_remove = 0; + unsigned long count, removed; int i, a, ret; if (argc < 4) { @@ -410,13 +564,45 @@ int main(int argc, char **argv) case 'v': verbose_mode = 1; break; + case 'p': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + rand_pool = atol(argv[++i]); + break; + case 'h': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + init_hash_size = atol(argv[++i]); + break; + case 'u': + add_unique = 1; + break; + case 'i': + add_only = 1; + break; } } + /* Check if hash size is power of 2 */ + if (init_hash_size && init_hash_size & (init_hash_size - 1)) { + printf("Error: Hash table size %lu is not a power of 2.\n", + init_hash_size); + return -1; + } + printf_verbose("running test for %lu seconds, %u readers, %u writers.\n", duration, nr_readers, nr_writers); printf_verbose("Writer delay : %lu loops.\n", wdelay); printf_verbose("Reader duration : %lu loops.\n", rduration); + printf_verbose("Random pool size : %lu.\n", rand_pool); + printf_verbose("Mode:%s%s.\n", + add_only ? " add only" : " add/remove", + add_unique ? " uniquify" : ""); + printf_verbose("Initial hash table size: %lu buckets.\n", init_hash_size); printf_verbose("thread %-6s, thread id : %lx, tid %lu\n", "main", pthread_self(), (unsigned long)gettid()); @@ -424,8 +610,12 @@ int main(int argc, char **argv) tid_writer = malloc(sizeof(*tid_writer) * nr_writers); count_reader = malloc(sizeof(*count_reader) * nr_readers); count_writer = malloc(sizeof(*count_writer) * nr_writers); - test_ht = ht_new(test_hash, (void *) 0x42, - HASH_SIZE, call_rcu); + test_ht = ht_new(test_hash, test_compare, 0x42UL, + init_hash_size, call_rcu); + + err = create_all_cpu_call_rcu_data(0); + assert(!err); + next_aff = 0; for (i = 0; i < nr_readers; i++) { @@ -459,21 +649,27 @@ int main(int argc, char **argv) err = pthread_join(tid_writer[i], &tret); if (err != 0) exit(1); - tot_writes += count_writer[i]; + tot_writes += count_writer[i].update_ops; + tot_add += count_writer[i].add; + tot_remove += count_writer[i].remove; } - ret = ht_destroy(test_ht); - if (ret) - printf("WARNING: nodes left in the hash table upon destroy\n"); + ht_count_nodes(test_ht, &count, &removed); + if (count || removed) + printf("WARNING: nodes left in the hash table upon destroy: " + "%lu nodes + %lu logically removed.\n", count, removed); + (void) ht_destroy(test_ht); printf_verbose("final delete: %d items\n", ret); printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads, tot_writes); printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu " "nr_writers %3u " - "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu\n", + "wdelay %6lu rand_pool %12llu nr_reads %12llu nr_writes %12llu nr_ops %12llu " + "nr_add %12llu nr_remove %12llu nr_leaked %12llu\n", argv[0], duration, nr_readers, rduration, - nr_writers, wdelay, tot_reads, tot_writes, - tot_reads + tot_writes); + nr_writers, wdelay, rand_pool, tot_reads, tot_writes, + tot_reads + tot_writes, tot_add, tot_remove, + tot_add - tot_remove - count); free(tid_reader); free(tid_writer); free(count_reader);