X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=aac1db88cbc2a09425d87f3ef12adf6e54423161;hb=7f94921512c992dde5c3abf5990436531b6230af;hp=e28c14afc750c7ffe09ec879b44f05488f76dc44;hpb=5f74363e048fb82d7ad97a780eadbeb063840787;p=urcu.git diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index e28c14a..aac1db8 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -21,6 +21,7 @@ */ #define _GNU_SOURCE +#include "../config.h" #include #include #include @@ -32,6 +33,7 @@ #include #include #include +#include #ifdef __linux__ #include @@ -41,6 +43,14 @@ #define DEFAULT_MIN_ALLOC_SIZE 1 #define DEFAULT_RAND_POOL 1000000 +/* + * Note: the hash seed should be a random value for hash tables + * targeting production environments to provide protection against + * denial of service attacks. We keep it a static value within this test + * program to compare identical benchmark runs. + */ +#define TEST_HASH_SEED 0x42UL + /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */ #define CACHE_LINE_SIZE 4096 @@ -107,6 +117,8 @@ struct test_data { struct lfht_test_node { struct cds_lfht_node node; + void *key; + unsigned int key_len; /* cache-cold for iteration */ struct rcu_head head; }; @@ -121,7 +133,9 @@ static inline void lfht_test_node_init(struct lfht_test_node *node, void *key, size_t key_len) { - cds_lfht_node_init(&node->node, key, key_len); + cds_lfht_node_init(&node->node); + node->key = key; + node->key_len = key_len; } static inline struct lfht_test_node * @@ -141,9 +155,11 @@ 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 max_hash_buckets_size = (1UL << 20); static unsigned long init_populate; static int opt_auto_resize; static int add_only, add_unique, add_replace; +static const struct cds_lfht_mm_type *memory_backend; static unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset; static unsigned long init_pool_size = DEFAULT_RAND_POOL, @@ -173,6 +189,12 @@ static int use_affinity = 0; pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER; +#ifndef HAVE_CPU_SET_T +typedef unsigned long cpu_set_t; +# define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0) +# define CPU_SET(cpu, cpuset) do { *(cpuset) |= (1UL << (cpu)); } while(0) +#endif + static void set_affinity(void) { cpu_set_t mask; @@ -182,6 +204,7 @@ static void set_affinity(void) if (!use_affinity) return; +#if HAVE_SCHED_SETAFFINITY ret = pthread_mutex_lock(&affinity_mutex); if (ret) { perror("Error in pthread mutex lock"); @@ -195,7 +218,12 @@ static void set_affinity(void) } CPU_ZERO(&mask); CPU_SET(cpu, &mask); - sched_setaffinity(0, sizeof(mask), &mask); +#if SCHED_SETAFFINITY_ARGS == 2 + sched_setaffinity(0, &mask); +#else + sched_setaffinity(0, sizeof(mask), &mask); +#endif +#endif /* HAVE_SCHED_SETAFFINITY */ } static enum { @@ -378,7 +406,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; @@ -387,7 +415,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; @@ -407,8 +435,8 @@ 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 (caa_unlikely(key1_len != key2_len)) return -1; @@ -419,6 +447,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 inline +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", @@ -427,7 +474,7 @@ void *thr_count(void *arg) rcu_register_thread(); for (;;) { - unsigned long count, removed; + unsigned long count; long approx_before, approx_after; ssize_t len; char buf[1]; @@ -443,15 +490,15 @@ void *thr_count(void *arg) printf("Counting nodes... "); fflush(stdout); rcu_read_lock(); - cds_lfht_count_nodes(test_ht, &approx_before, &count, &removed, + cds_lfht_count_nodes(test_ht, &approx_before, &count, &approx_after); rcu_read_unlock(); printf("done.\n"); printf("Approximation before node accounting: %ld nodes.\n", approx_before); printf("Accounting of nodes in the hash table: " - "%lu nodes + %lu logically removed.\n", - count, removed); + "%lu nodes.\n", + count); printf("Approximation after node accounting: %ld nodes.\n", approx_after); } @@ -479,7 +526,7 @@ 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_test_node(&iter); @@ -551,12 +598,18 @@ void *thr_writer(void *_count) sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, &node->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->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->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->node) { @@ -574,10 +627,10 @@ 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); + ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter)); rcu_read_unlock(); if (ret == 0) { node = cds_lfht_iter_get_test_node(&iter); @@ -642,12 +695,18 @@ static int populate_hash(void) sizeof(void *)); rcu_read_lock(); if (add_unique) { - ret_node = cds_lfht_add_unique(test_ht, &node->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->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->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->node) { @@ -673,14 +732,12 @@ void test_delete_all_nodes(struct cds_lfht *ht) struct lfht_test_node *node; unsigned long count = 0; - cds_lfht_first(ht, &iter); - while ((node = cds_lfht_iter_get_test_node(&iter)) != NULL) { + cds_lfht_for_each_entry(ht, &iter, node, node) { int ret; - ret = cds_lfht_del(test_ht, &iter); + ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter)); assert(!ret); call_rcu(&node->head, free_node_cb); - cds_lfht_next(ht, &iter); count++; } printf("deleted %lu nodes.\n", count); @@ -696,14 +753,16 @@ void show_usage(int argc, char **argv) printf(" [-c duration] (reader C.S. duration (in loops))\n"); 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(" [-h size] (initial number of buckets)\n"); + printf(" [-m size] (minimum number of allocated buckets)\n"); + printf(" [-n size] (maximum number of buckets)\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"); 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(" [-B order|chunk|mmap] Specify the memory backend.\n"); printf(" [-R offset] Lookup pool offset.\n"); printf(" [-S offset] Write pool offset.\n"); printf(" [-T offset] Init pool offset.\n"); @@ -724,7 +783,7 @@ int main(int argc, char **argv) struct wr_count *count_writer; unsigned long long tot_reads = 0, tot_writes = 0, tot_add = 0, tot_add_exist = 0, tot_remove = 0; - unsigned long count, removed; + unsigned long count; long approx_before, approx_after; int i, a, ret; struct sigaction act; @@ -806,6 +865,13 @@ int main(int argc, char **argv) } min_hash_alloc_size = atol(argv[++i]); break; + case 'n': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + max_hash_buckets_size = atol(argv[++i]); + break; case 'u': if (add_replace) { printf("Please specify at most one of -s or -u.\n"); @@ -829,6 +895,23 @@ int main(int argc, char **argv) case 'A': opt_auto_resize = 1; break; + case 'B': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + i++; + if (!strcmp("order", argv[i])) + memory_backend = &cds_lfht_mm_order; + else if (!strcmp("chunk", argv[i])) + memory_backend = &cds_lfht_mm_chunk; + else if (!strcmp("mmap", argv[i])) + memory_backend = &cds_lfht_mm_mmap; + else { + printf("Please specify memory backend with order|chunk|mmap.\n"); + exit(-1); + } + break; case 'R': lookup_pool_offset = atol(argv[++i]); break; @@ -856,17 +939,23 @@ int main(int argc, char **argv) /* 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", + printf("Error: Initial number of buckets (%lu) is not a power of 2.\n", init_hash_size); 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", + if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) { + printf("Error: Minimum number of allocated buckets (%lu) is not a power of 2.\n", min_hash_alloc_size); return -1; } + if (max_hash_buckets_size && max_hash_buckets_size & (max_hash_buckets_size - 1)) { + printf("Error: Maximum number of buckets (%lu) is not a power of 2.\n", + max_hash_buckets_size); + return -1; + } + memset(&act, 0, sizeof(act)); ret = sigemptyset(&act.sa_mask); if (ret == -1) { @@ -908,8 +997,9 @@ int main(int argc, char **argv) printf_verbose("Mode:%s%s.\n", 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("Initial number of buckets: %lu buckets.\n", init_hash_size); + printf_verbose("Minimum number of allocated buckets: %lu buckets.\n", min_hash_alloc_size); + printf_verbose("Maximum number of buckets: %lu buckets.\n", max_hash_buckets_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", @@ -925,17 +1015,28 @@ int main(int argc, char **argv) count_writer = malloc(sizeof(*count_writer) * nr_writers); err = create_all_cpu_call_rcu_data(0); - assert(!err); + if (err) { + printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n"); + } + + if (memory_backend) { + test_ht = _cds_lfht_new(init_hash_size, min_hash_alloc_size, + max_hash_buckets_size, + (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) | + CDS_LFHT_ACCOUNTING, memory_backend, + &rcu_flavor, NULL); + } else { + test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, + max_hash_buckets_size, + (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) | + CDS_LFHT_ACCOUNTING, NULL); + } /* - * Hash creation and population needs to be seen as a RCU reader + * Hash Population needs to be seen as a RCU reader * thread from the point of view of resize. */ rcu_register_thread(); - test_ht = cds_lfht_new(test_hash, test_compare, 0x42UL, - init_hash_size, min_hash_alloc_size, - (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) | - CDS_LFHT_ACCOUNTING, NULL); ret = populate_hash(); assert(!ret); @@ -1007,18 +1108,17 @@ int main(int argc, char **argv) rcu_thread_online(); rcu_read_lock(); printf("Counting nodes... "); - cds_lfht_count_nodes(test_ht, &approx_before, &count, &removed, - &approx_after); + cds_lfht_count_nodes(test_ht, &approx_before, &count, &approx_after); printf("done.\n"); test_delete_all_nodes(test_ht); rcu_read_unlock(); rcu_thread_offline(); - if (count || removed) { + if (count) { printf("Approximation before node accounting: %ld nodes.\n", approx_before); printf("Nodes deleted from hash table before destroy: " - "%lu nodes + %lu logically removed.\n", - count, removed); + "%lu nodes.\n", + count); printf("Approximation after node accounting: %ld nodes.\n", approx_after); }