X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=44b9531b2fb8080b1a7e5bf02320669374f5bc6e;hp=cdc78d54c420f0b9f4128aadd429c2dd5266a261;hb=3eca1b8cce5630bcbd865a8d30855c996bc021c3;hpb=a42cc6594389e8f88cc49e36a7779afdb6529135 diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index cdc78d5..44b9531 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -30,13 +30,12 @@ #include #include #include -#include #include -#include -#include #include -#include "../arch.h" +#ifdef __linux__ +#include +#endif #define HASH_SIZE 32 #define RAND_POOL 1000 @@ -67,7 +66,9 @@ static inline pid_t gettid(void) #else #define debug_yield_read() #endif -#include "../urcu.h" +#include +#include +#include static unsigned int __thread rand_lookup; static unsigned long __thread nr_add; @@ -96,7 +97,7 @@ static unsigned long rduration; static inline void loop_sleep(unsigned long l) { while(l-- != 0) - cpu_relax(); + caa_cpu_relax(); } static int verbose_mode; @@ -180,12 +181,154 @@ void rcu_copy_mutex_unlock(void) } } -#define ARRAY_POISON 0xDEADBEEF +/* + * 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 long key = (unsigned long) _key; + unsigned long v; + + 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 + +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) { unsigned long long *count = _count; - struct test_data *local_ptr; + struct rcu_ht_node *node; printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", "reader", pthread_self(), (unsigned long)gettid()); @@ -197,13 +340,14 @@ void *thr_reader(void *_count) while (!test_go) { } - smp_mb(); + cmm_smp_mb(); for (;;) { rcu_read_lock(); - local_ptr = ht_lookup(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); - if (local_ptr == NULL) + node = ht_lookup(test_ht, + (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *)); + if (node == NULL) lookup_fail++; else lookup_ok++; @@ -227,10 +371,18 @@ void *thr_reader(void *_count) } +static +void free_node_cb(struct rcu_head *head) +{ + struct rcu_ht_node *node = + caa_container_of(head, struct rcu_ht_node, head); + free(node); +} + void *thr_writer(void *_count) { + struct rcu_ht_node *node; unsigned long long *count = _count; - struct test_data *data; int ret; printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -239,46 +391,55 @@ void *thr_writer(void *_count) set_affinity(); rcu_register_thread(); - rcu_defer_register_thread(); while (!test_go) { } - smp_mb(); + cmm_smp_mb(); for (;;) { if (rand_r(&rand_lookup) & 1) { - data = malloc(sizeof(struct test_data)); - //rcu_copy_mutex_lock(); - ret = ht_add(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), - data); - if (ret == -EEXIST) { - free(data); + node = malloc(sizeof(struct rcu_ht_node)); + rcu_read_lock(); + ht_node_init(node, + (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *), + (void *) 0x42); + ret = ht_add_unique(test_ht, node); + rcu_read_unlock(); + if (ret) nr_addexist++; - } else { + else nr_add++; - } - //rcu_copy_mutex_unlock(); } else { /* May delete */ - //rcu_copy_mutex_lock(); - ret = ht_delete(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); - if (ret == -ENOENT) - nr_delnoent++; + rcu_read_lock(); + node = ht_lookup(test_ht, + (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *)); + if (node) + ret = ht_remove(test_ht, node); else + ret = -ENOENT; + rcu_read_unlock(); + if (ret == 0) { + call_rcu(&node->head, free_node_cb); nr_del++; - //rcu_copy_mutex_unlock(); + } else + nr_delnoent++; } +#if 0 //if (nr_writes % 100000 == 0) { if (nr_writes % 1000 == 0) { + rcu_read_lock(); if (rand_r(&rand_lookup) & 1) { ht_resize(test_ht, 1); } else { ht_resize(test_ht, -1); } + rcu_read_unlock(); } +#endif //0 nr_writes++; if (unlikely(!test_duration_write())) break; @@ -286,7 +447,6 @@ void *thr_writer(void *_count) loop_sleep(wdelay); } - rcu_defer_unregister_thread(); rcu_unregister_thread(); printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", @@ -396,8 +556,8 @@ 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(ht_jhash, free, HASH_SIZE, sizeof(unsigned long), - 43223455); + test_ht = ht_new(test_hash, test_compare, 0x42UL, + HASH_SIZE, call_rcu); next_aff = 0; for (i = 0; i < nr_readers; i++) { @@ -413,7 +573,7 @@ int main(int argc, char **argv) exit(1); } - smp_mb(); + cmm_smp_mb(); test_go = 1; @@ -433,12 +593,10 @@ int main(int argc, char **argv) exit(1); tot_writes += count_writer[i]; } - rcu_register_thread(); - rcu_defer_register_thread(); ret = ht_destroy(test_ht); - rcu_defer_unregister_thread(); - rcu_unregister_thread(); - + if (ret) + printf("WARNING: nodes left in the hash table upon destroy\n"); + printf_verbose("final delete: %d items\n", ret); printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads, tot_writes);