X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=043a33a9353105eac57e2363693bdfb41c49f12c;hp=9ae1fa0791cec5bbbf89e4513bd33a030977911d;hb=747d725c1dd45d5072e0e411642c4d5c6403b4be;hpb=5afadd129c36f4778bcc12c8def6f4e3f9604c7b diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index 9ae1fa0..043a33a 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -38,8 +38,11 @@ #endif #define DEFAULT_HASH_SIZE 32 +#define DEFAULT_MIN_ALLOC_SIZE 1 #define DEFAULT_RAND_POOL 1000000 +#define TEST_HASH_SEED 0x42UL + /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */ #define CACHE_LINE_SIZE 4096 @@ -104,6 +107,35 @@ struct test_data { int b; }; +struct lfht_test_node { + struct cds_lfht_node node; + void *key; + unsigned int key_len; + /* cache-cold for iteration */ + struct rcu_head head; +}; + +static inline struct lfht_test_node * +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) +{ + return to_test_node(cds_lfht_iter_get_node(iter)); +} + static volatile int test_go, test_stop; static unsigned long wdelay; @@ -114,6 +146,7 @@ static unsigned long duration; static unsigned long rduration; static unsigned long init_hash_size = DEFAULT_HASH_SIZE; +static unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE; static unsigned long init_populate; static int opt_auto_resize; static int add_only, add_unique, add_replace; @@ -351,7 +384,7 @@ void hashword2( #if (CAA_BITS_PER_LONG == 32) static -unsigned long test_hash(void *_key, size_t length, unsigned long seed) +unsigned long test_hash(const void *_key, size_t length, unsigned long seed) { unsigned int key = (unsigned int) _key; @@ -360,7 +393,7 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed) } #else static -unsigned long test_hash(void *_key, size_t length, unsigned long seed) +unsigned long test_hash(const void *_key, size_t length, unsigned long seed) { union { uint64_t v64; @@ -380,10 +413,10 @@ unsigned long test_hash(void *_key, size_t length, unsigned long seed) #endif static -unsigned long test_compare(void *key1, size_t key1_len, - void *key2, size_t key2_len) +unsigned long test_compare(const void *key1, size_t key1_len, + const void *key2, size_t key2_len) { - if (unlikely(key1_len != key2_len)) + if (caa_unlikely(key1_len != key2_len)) return -1; assert(key1_len == sizeof(unsigned long)); if (key1 == key2) @@ -392,6 +425,25 @@ unsigned long test_compare(void *key1, size_t key1_len, return 1; } +static +int test_match(struct cds_lfht_node *node, const 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)); + + cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED), + test_match, key, iter); +} + void *thr_count(void *arg) { printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -408,7 +460,7 @@ void *thr_count(void *arg) rcu_thread_offline(); len = read(count_pipe[0], buf, 1); rcu_thread_online(); - if (unlikely(!test_duration_read())) + if (caa_unlikely(!test_duration_read())) break; if (len != 1) continue; @@ -435,7 +487,7 @@ void *thr_count(void *arg) void *thr_reader(void *_count) { unsigned long long *count = _count; - struct cds_lfht_node *node; + struct lfht_test_node *node; struct cds_lfht_iter iter; printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -452,10 +504,10 @@ void *thr_reader(void *_count) for (;;) { rcu_read_lock(); - cds_lfht_lookup(test_ht, + cds_lfht_test_lookup(test_ht, (void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset), sizeof(void *), &iter); - node = cds_lfht_iter_get_node(&iter); + node = cds_lfht_iter_get_test_node(&iter); if (node == NULL) { if (validate_lookup) { printf("[ERROR] Lookup cannot find initial node.\n"); @@ -466,13 +518,13 @@ void *thr_reader(void *_count) lookup_ok++; } debug_yield_read(); - if (unlikely(rduration)) + if (caa_unlikely(rduration)) loop_sleep(rduration); rcu_read_unlock(); nr_reads++; - if (unlikely(!test_duration_read())) + if (caa_unlikely(!test_duration_read())) break; - if (unlikely((nr_reads & ((1 << 10) - 1)) == 0)) + if (caa_unlikely((nr_reads & ((1 << 10) - 1)) == 0)) rcu_quiescent_state(); } @@ -490,14 +542,15 @@ void *thr_reader(void *_count) static void free_node_cb(struct rcu_head *head) { - struct cds_lfht_node *node = - caa_container_of(head, struct cds_lfht_node, head); + struct lfht_test_node *node = + caa_container_of(head, struct lfht_test_node, head); free(node); } void *thr_writer(void *_count) { - struct cds_lfht_node *node, *ret_node; + struct lfht_test_node *node; + struct cds_lfht_node *ret_node; struct cds_lfht_iter iter; struct wr_count *count = _count; int ret; @@ -517,26 +570,33 @@ void *thr_writer(void *_count) for (;;) { if ((addremove == AR_ADD || add_only) || (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) { - node = malloc(sizeof(struct cds_lfht_node)); - cds_lfht_node_init(node, + node = malloc(sizeof(struct lfht_test_node)); + lfht_test_node_init(node, (void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset), sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, node); + ret_node = cds_lfht_add_unique(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); } else { if (add_replace) - ret_node = cds_lfht_add_replace(test_ht, node); + ret_node = cds_lfht_add_replace(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); else - cds_lfht_add(test_ht, node); + cds_lfht_add(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + &node->node); } rcu_read_unlock(); - if (add_unique && ret_node != node) { + if (add_unique && ret_node != &node->node) { free(node); nr_addexist++; } else { if (add_replace && ret_node) { - call_rcu(&ret_node->head, free_node_cb); + call_rcu(&to_test_node(ret_node)->head, + free_node_cb); nr_addexist++; } else { nr_add++; @@ -545,13 +605,13 @@ void *thr_writer(void *_count) } else { /* May delete */ rcu_read_lock(); - cds_lfht_lookup(test_ht, + cds_lfht_test_lookup(test_ht, (void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset), sizeof(void *), &iter); ret = cds_lfht_del(test_ht, &iter); rcu_read_unlock(); if (ret == 0) { - node = cds_lfht_iter_get_node(&iter); + node = cds_lfht_iter_get_test_node(&iter); call_rcu(&node->head, free_node_cb); nr_del++; } else @@ -570,11 +630,11 @@ void *thr_writer(void *_count) } #endif //0 nr_writes++; - if (unlikely(!test_duration_write())) + if (caa_unlikely(!test_duration_write())) break; - if (unlikely(wdelay)) + if (caa_unlikely(wdelay)) loop_sleep(wdelay); - if (unlikely((nr_writes & ((1 << 10) - 1)) == 0)) + if (caa_unlikely((nr_writes & ((1 << 10) - 1)) == 0)) rcu_quiescent_state(); } @@ -594,7 +654,8 @@ void *thr_writer(void *_count) static int populate_hash(void) { - struct cds_lfht_node *node, *ret_node; + struct lfht_test_node *node; + struct cds_lfht_node *ret_node; if (!init_populate) return 0; @@ -606,26 +667,32 @@ static int populate_hash(void) } while (nr_add < init_populate) { - node = malloc(sizeof(struct cds_lfht_node)); - cds_lfht_node_init(node, + node = malloc(sizeof(struct lfht_test_node)); + lfht_test_node_init(node, (void *)(((unsigned long) rand_r(&rand_lookup) % init_pool_size) + init_pool_offset), sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, node); + ret_node = cds_lfht_add_unique(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); } else { if (add_replace) - ret_node = cds_lfht_add_replace(test_ht, node); + ret_node = cds_lfht_add_replace(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); else - cds_lfht_add(test_ht, node); + cds_lfht_add(test_ht, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + &node->node); } rcu_read_unlock(); - if (add_unique && ret_node != node) { + if (add_unique && ret_node != &node->node) { free(node); nr_addexist++; } else { if (add_replace && ret_node) { - call_rcu(&ret_node->head, free_node_cb); + call_rcu(&to_test_node(ret_node)->head, free_node_cb); nr_addexist++; } else { nr_add++; @@ -640,17 +707,15 @@ static void test_delete_all_nodes(struct cds_lfht *ht) { struct cds_lfht_iter iter; - struct cds_lfht_node *node; + struct lfht_test_node *node; unsigned long count = 0; - cds_lfht_first(ht, &iter); - while ((node = cds_lfht_iter_get_node(&iter)) != NULL) { + cds_lfht_for_each_entry(ht, &iter, node, node) { int ret; ret = cds_lfht_del(test_ht, &iter); assert(!ret); call_rcu(&node->head, free_node_cb); - cds_lfht_next(ht, &iter); count++; } printf("deleted %lu nodes.\n", count); @@ -667,6 +732,7 @@ void show_usage(int argc, char **argv) printf(" [-v] (verbose output)\n"); printf(" [-a cpu#] [-a cpu#]... (affinity)\n"); printf(" [-h size] (initial hash table size)\n"); + printf(" [-m size] (minimum hash alloc size)\n"); printf(" [not -u nor -s] Add entries (supports redundant keys).\n"); printf(" [-u] Uniquify add (no redundant keys).\n"); printf(" [-s] Replace (swap) entries.\n"); @@ -768,6 +834,13 @@ int main(int argc, char **argv) } init_hash_size = atol(argv[++i]); break; + case 'm': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + min_hash_alloc_size = atol(argv[++i]); + break; case 'u': if (add_replace) { printf("Please specify at most one of -s or -u.\n"); @@ -823,6 +896,12 @@ int main(int argc, char **argv) return -1; } + if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) { + printf("Error: Min hash alloc size %lu is not a power of 2.\n", + min_hash_alloc_size); + return -1; + } + memset(&act, 0, sizeof(act)); ret = sigemptyset(&act.sa_mask); if (ret == -1) { @@ -865,6 +944,7 @@ int main(int argc, char **argv) add_only ? " add only" : " add/remove", 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", @@ -887,8 +967,7 @@ int main(int argc, char **argv) * thread from the point of view of resize. */ rcu_register_thread(); - test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL, - init_hash_size, 1, + test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18), (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) | CDS_LFHT_ACCOUNTING, NULL); ret = populate_hash();