From 18ca7a5b5573e511a66f118ec863df82a6d247e4 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 24 Apr 2012 10:30:15 -0400 Subject: [PATCH] rculfhash tests: modularize tests Signed-off-by: Mathieu Desnoyers --- tests/Makefile.am | 3 +- tests/test_urcu_hash.c | 630 +++----------------------------------- tests/test_urcu_hash.h | 384 +++++++++++++++++++++++ tests/test_urcu_hash_rw.c | 271 ++++++++++++++++ 4 files changed, 703 insertions(+), 585 deletions(-) create mode 100644 tests/test_urcu_hash.h create mode 100644 tests/test_urcu_hash_rw.c diff --git a/tests/Makefile.am b/tests/Makefile.am index bbd72f8..e9d2046 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -175,7 +175,8 @@ test_urcu_wfs_dynlink_SOURCES = test_urcu_wfs.c test_urcu_wfs_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) test_urcu_wfs_dynlink_LDADD = $(URCU_COMMON_LIB) -test_urcu_hash_SOURCES = test_urcu_hash.c $(COMPAT) +test_urcu_hash_SOURCES = test_urcu_hash.c test_urcu_hash.h \ + test_urcu_hash_rw.c $(COMPAT) test_urcu_hash_CFLAGS = -DRCU_QSBR $(AM_CFLAGS) test_urcu_hash_LDADD = $(URCU_QSBR_LIB) $(URCU_CDS_LIB) diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index aac1db8..3578cc9 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -3,7 +3,7 @@ * * Userspace RCU library - test program * - * Copyright February 2009 - Mathieu Desnoyers + * Copyright 2009-2012 - Mathieu Desnoyers * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -21,181 +21,60 @@ */ #define _GNU_SOURCE -#include "../config.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include +#include "test_urcu_hash.h" -#ifdef __linux__ -#include -#endif - -#define DEFAULT_HASH_SIZE 32 -#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 - -/* hardcoded number of CPUs */ -#define NR_CPUS 16384 - -#ifdef POISON_FREE -#define poison_free(ptr) \ - do { \ - memset(ptr, 0x42, sizeof(*(ptr))); \ - free(ptr); \ - } while (0) -#else -#define poison_free(ptr) free(ptr) -#endif - - - -#if defined(_syscall0) -_syscall0(pid_t, gettid) -#elif defined(__NR_gettid) -static inline pid_t gettid(void) -{ - return syscall(__NR_gettid); -} -#else -#warning "use pid as tid" -static inline pid_t gettid(void) -{ - return getpid(); -} -#endif - -#ifndef DYNAMIC_LINK_TEST -#define _LGPL_SOURCE -#else -#define debug_yield_read() -#endif -#include -#include -#include - -struct wr_count { - unsigned long update_ops; - unsigned long add; - unsigned long add_exist; - unsigned long remove; -}; +unsigned int __thread rand_lookup; +unsigned long __thread nr_add; +unsigned long __thread nr_addexist; +unsigned long __thread nr_del; +unsigned long __thread nr_delnoent; +unsigned long __thread lookup_fail; +unsigned long __thread lookup_ok; -static unsigned int __thread rand_lookup; -static unsigned long __thread nr_add; -static unsigned long __thread nr_addexist; -static unsigned long __thread nr_del; -static unsigned long __thread nr_delnoent; -static unsigned long __thread lookup_fail; -static unsigned long __thread lookup_ok; +struct cds_lfht *test_ht; -static struct cds_lfht *test_ht; +volatile int test_go, test_stop; -struct test_data { - int a; - int b; -}; +unsigned long wdelay; -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; - -static unsigned long duration; +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 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, +unsigned long rduration; + +unsigned long init_hash_size = DEFAULT_HASH_SIZE; +unsigned long min_hash_alloc_size = DEFAULT_MIN_ALLOC_SIZE; +unsigned long max_hash_buckets_size = (1UL << 20); +unsigned long init_populate; +int opt_auto_resize; +int add_only, add_unique, add_replace; +const struct cds_lfht_mm_type *memory_backend; + +unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset; +unsigned long init_pool_size = DEFAULT_RAND_POOL, lookup_pool_size = DEFAULT_RAND_POOL, write_pool_size = DEFAULT_RAND_POOL; -static int validate_lookup; +int validate_lookup; -static int count_pipe[2]; +int count_pipe[2]; -static inline void loop_sleep(unsigned long l) -{ - while(l-- != 0) - caa_cpu_relax(); -} +int verbose_mode; -static int verbose_mode; +unsigned int cpu_affinities[NR_CPUS]; +unsigned int next_aff = 0; +int use_affinity = 0; -#define printf_verbose(fmt, args...) \ - do { \ - if (verbose_mode) \ - printf(fmt, ## args); \ - } while (0) +pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER; -static unsigned int cpu_affinities[NR_CPUS]; -static unsigned int next_aff = 0; -static int use_affinity = 0; +unsigned long long __thread nr_writes; +unsigned long long __thread nr_reads; -pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER; +unsigned int nr_readers; +unsigned int nr_writers; -#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 pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER; -static void set_affinity(void) +void set_affinity(void) { cpu_set_t mask; int cpu; @@ -226,63 +105,6 @@ static void set_affinity(void) #endif /* HAVE_SCHED_SETAFFINITY */ } -static enum { - AR_RANDOM = 0, - AR_ADD = 1, - AR_REMOVE = -1, -} addremove; /* 1: add, -1 remove, 0: random */ - -static -void sigusr1_handler(int signo) -{ - switch (addremove) { - case AR_ADD: - printf("Add/Remove: random.\n"); - addremove = AR_RANDOM; - break; - case AR_RANDOM: - printf("Add/Remove: remove only.\n"); - addremove = AR_REMOVE; - break; - case AR_REMOVE: - printf("Add/Remove: add only.\n"); - addremove = AR_ADD; - break; - } -} - -static -void sigusr2_handler(int signo) -{ - char msg[1] = { 0x42 }; - ssize_t ret; - - do { - ret = write(count_pipe[1], msg, 1); /* wakeup thread */ - } while (ret == -1L && errno == EINTR); -} - -/* - * returns 0 if test should end. - */ -static int test_duration_write(void) -{ - return !test_stop; -} - -static int test_duration_read(void) -{ - return !test_stop; -} - -static unsigned long long __thread nr_writes; -static unsigned long long __thread nr_reads; - -static unsigned int nr_readers; -static unsigned int nr_writers; - -pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER; - void rcu_copy_mutex_lock(void) { int ret; @@ -304,137 +126,6 @@ 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 -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(const 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(const 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(const void *key1, size_t key1_len, const void *key2, size_t key2_len) { @@ -447,25 +138,6 @@ unsigned long test_compare(const 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", @@ -506,62 +178,6 @@ void *thr_count(void *arg) return NULL; } -void *thr_reader(void *_count) -{ - unsigned long long *count = _count; - struct lfht_test_node *node; - struct cds_lfht_iter iter; - - printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", - "reader", pthread_self(), (unsigned long)gettid()); - - set_affinity(); - - rcu_register_thread(); - - while (!test_go) - { - } - cmm_smp_mb(); - - for (;;) { - rcu_read_lock(); - 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); - if (node == NULL) { - if (validate_lookup) { - printf("[ERROR] Lookup cannot find initial node.\n"); - exit(-1); - } - lookup_fail++; - } else { - lookup_ok++; - } - debug_yield_read(); - if (caa_unlikely(rduration)) - loop_sleep(rduration); - rcu_read_unlock(); - nr_reads++; - if (caa_unlikely(!test_duration_read())) - break; - if (caa_unlikely((nr_reads & ((1 << 10) - 1)) == 0)) - rcu_quiescent_state(); - } - - rcu_unregister_thread(); - - *count = nr_reads; - printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", - "reader", pthread_self(), (unsigned long)gettid()); - printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n", - pthread_self(), lookup_fail, lookup_ok); - return ((void*)1); - -} - -static void free_node_cb(struct rcu_head *head) { struct lfht_test_node *node = @@ -569,162 +185,6 @@ void free_node_cb(struct rcu_head *head) free(node); } -void *thr_writer(void *_count) -{ - struct lfht_test_node *node; - struct cds_lfht_node *ret_node; - struct cds_lfht_iter iter; - struct wr_count *count = _count; - int ret; - - printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", - "writer", pthread_self(), (unsigned long)gettid()); - - set_affinity(); - - rcu_register_thread(); - - while (!test_go) - { - } - cmm_smp_mb(); - - for (;;) { - if ((addremove == AR_ADD || add_only) - || (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) { - 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, - 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, - test_hash(node->key, node->key_len, TEST_HASH_SEED), - test_match, node->key, &node->node); - else - 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) { - free(node); - nr_addexist++; - } else { - if (add_replace && ret_node) { - call_rcu(&to_test_node(ret_node)->head, - free_node_cb); - nr_addexist++; - } else { - nr_add++; - } - } - } else { - /* May delete */ - rcu_read_lock(); - 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, cds_lfht_iter_get_node(&iter)); - rcu_read_unlock(); - if (ret == 0) { - node = cds_lfht_iter_get_test_node(&iter); - call_rcu(&node->head, free_node_cb); - nr_del++; - } 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 (caa_unlikely(!test_duration_write())) - break; - if (caa_unlikely(wdelay)) - loop_sleep(wdelay); - if (caa_unlikely((nr_writes & ((1 << 10) - 1)) == 0)) - rcu_quiescent_state(); - } - - rcu_unregister_thread(); - - printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", - "writer", pthread_self(), (unsigned long)gettid()); - 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->update_ops = nr_writes; - count->add = nr_add; - count->add_exist = nr_addexist; - count->remove = nr_del; - return ((void*)2); -} - -static int populate_hash(void) -{ - struct lfht_test_node *node; - struct cds_lfht_node *ret_node; - - if (!init_populate) - return 0; - - 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 *)(((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, - 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, - test_hash(node->key, node->key_len, TEST_HASH_SEED), - test_match, node->key, &node->node); - else - 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) { - free(node); - nr_addexist++; - } else { - if (add_replace && ret_node) { - call_rcu(&to_test_node(ret_node)->head, free_node_cb); - nr_addexist++; - } else { - nr_add++; - } - } - nr_writes++; - } - return 0; -} - static void test_delete_all_nodes(struct cds_lfht *ht) { @@ -756,7 +216,7 @@ void show_usage(int argc, char **argv) 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(" [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"); @@ -962,7 +422,7 @@ int main(int argc, char **argv) perror("sigemptyset"); return -1; } - act.sa_handler = sigusr1_handler; + act.sa_handler = test_hash_rw_sigusr1_handler; act.sa_flags = SA_RESTART; ret = sigaction(SIGUSR1, &act, NULL); if (ret == -1) { @@ -982,7 +442,7 @@ int main(int argc, char **argv) if (err != 0) exit(1); - act.sa_handler = sigusr2_handler; + act.sa_handler = test_hash_rw_sigusr2_handler; act.sa_flags = SA_RESTART; ret = sigaction(SIGUSR2, &act, NULL); if (ret == -1) { @@ -1037,7 +497,7 @@ int main(int argc, char **argv) * thread from the point of view of resize. */ rcu_register_thread(); - ret = populate_hash(); + ret = test_hash_rw_populate_hash(); assert(!ret); rcu_thread_offline(); @@ -1045,13 +505,15 @@ int main(int argc, char **argv) next_aff = 0; for (i = 0; i < nr_readers; i++) { - err = pthread_create(&tid_reader[i], NULL, thr_reader, + err = pthread_create(&tid_reader[i], + NULL, test_hash_rw_thr_reader, &count_reader[i]); if (err != 0) exit(1); } for (i = 0; i < nr_writers; i++) { - err = pthread_create(&tid_writer[i], NULL, thr_writer, + err = pthread_create(&tid_writer[i], + NULL, test_hash_rw_thr_writer, &count_writer[i]); if (err != 0) exit(1); diff --git a/tests/test_urcu_hash.h b/tests/test_urcu_hash.h new file mode 100644 index 0000000..994c659 --- /dev/null +++ b/tests/test_urcu_hash.h @@ -0,0 +1,384 @@ +#ifndef _TEST_URCU_HASH_H +#define _TEST_URCU_HASH_H + +/* + * test_urcu_hash.h + * + * Userspace RCU library - test program + * + * Copyright 2009-2012 - Mathieu Desnoyers + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "../config.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#ifdef __linux__ +#include +#endif + +#define DEFAULT_HASH_SIZE 32 +#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 + +/* hardcoded number of CPUs */ +#define NR_CPUS 16384 + +#ifdef POISON_FREE +#define poison_free(ptr) \ + do { \ + memset(ptr, 0x42, sizeof(*(ptr))); \ + free(ptr); \ + } while (0) +#else +#define poison_free(ptr) free(ptr) +#endif + + + +#if defined(_syscall0) +_syscall0(pid_t, gettid) +#elif defined(__NR_gettid) +static inline pid_t gettid(void) +{ + return syscall(__NR_gettid); +} +#else +#warning "use pid as tid" +static inline pid_t gettid(void) +{ + return getpid(); +} +#endif + +#ifndef DYNAMIC_LINK_TEST +#define _LGPL_SOURCE +#else +#define debug_yield_read() +#endif +#include +#include +#include + +struct wr_count { + unsigned long update_ops; + unsigned long add; + unsigned long add_exist; + unsigned long remove; +}; + +extern unsigned int __thread rand_lookup; +extern unsigned long __thread nr_add; +extern unsigned long __thread nr_addexist; +extern unsigned long __thread nr_del; +extern unsigned long __thread nr_delnoent; +extern unsigned long __thread lookup_fail; +extern unsigned long __thread lookup_ok; + +extern struct cds_lfht *test_ht; + +struct test_data { + int a; + 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)); +} + +extern volatile int test_go, test_stop; + +extern unsigned long wdelay; + +extern unsigned long duration; + +/* read-side C.S. duration, in loops */ +extern unsigned long rduration; + +extern unsigned long init_hash_size; +extern unsigned long min_hash_alloc_size; +extern unsigned long max_hash_buckets_size; +extern unsigned long init_populate; +extern int opt_auto_resize; +extern int add_only, add_unique, add_replace; +extern const struct cds_lfht_mm_type *memory_backend; + +extern unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset; +extern unsigned long init_pool_size, + lookup_pool_size, + write_pool_size; +extern int validate_lookup; + +extern int count_pipe[2]; + +static inline void loop_sleep(unsigned long l) +{ + while(l-- != 0) + caa_cpu_relax(); +} + +extern int verbose_mode; + +#define printf_verbose(fmt, args...) \ + do { \ + if (verbose_mode) \ + printf(fmt, ## args); \ + } while (0) + +extern unsigned int cpu_affinities[NR_CPUS]; +extern unsigned int next_aff; +extern int use_affinity; + +extern pthread_mutex_t affinity_mutex; + +#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 + +void set_affinity(void); + +/* rw test */ +void test_hash_rw_sigusr1_handler(int signo); +void test_hash_rw_sigusr2_handler(int signo); +void *test_hash_rw_thr_reader(void *_count); +void *test_hash_rw_thr_writer(void *_count); + +/* + * returns 0 if test should end. + */ +static inline int test_duration_write(void) +{ + return !test_stop; +} + +static inline int test_duration_read(void) +{ + return !test_stop; +} + +extern unsigned long long __thread nr_writes; +extern unsigned long long __thread nr_reads; + +extern unsigned int nr_readers; +extern unsigned int nr_writers; + +void rcu_copy_mutex_lock(void); +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 inline __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 inline +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 inline +unsigned long test_hash(const 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 inline +unsigned long test_hash(const 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 + +unsigned long test_compare(const void *key1, size_t key1_len, + const void *key2, size_t key2_len); + +static inline +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 free_node_cb(struct rcu_head *head); + +#endif /* _TEST_URCU_HASH_H */ diff --git a/tests/test_urcu_hash_rw.c b/tests/test_urcu_hash_rw.c new file mode 100644 index 0000000..7145ca4 --- /dev/null +++ b/tests/test_urcu_hash_rw.c @@ -0,0 +1,271 @@ +/* + * test_urcu_hash_rw.c + * + * Userspace RCU library - test program + * + * Copyright 2009-2012 - Mathieu Desnoyers + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#define _GNU_SOURCE +#include "test_urcu_hash.h" + +enum urcu_hash_addremove { + AR_RANDOM = 0, + AR_ADD = 1, + AR_REMOVE = -1, +}; /* 1: add, -1 remove, 0: random */ + +static enum urcu_hash_addremove addremove; /* 1: add, -1 remove, 0: random */ + +void test_hash_rw_sigusr1_handler(int signo) +{ + switch (addremove) { + case AR_ADD: + printf("Add/Remove: random.\n"); + addremove = AR_RANDOM; + break; + case AR_RANDOM: + printf("Add/Remove: remove only.\n"); + addremove = AR_REMOVE; + break; + case AR_REMOVE: + printf("Add/Remove: add only.\n"); + addremove = AR_ADD; + break; + } +} + +void test_hash_rw_sigusr2_handler(int signo) +{ + char msg[1] = { 0x42 }; + ssize_t ret; + + do { + ret = write(count_pipe[1], msg, 1); /* wakeup thread */ + } while (ret == -1L && errno == EINTR); +} + +void *test_hash_rw_thr_reader(void *_count) +{ + unsigned long long *count = _count; + struct lfht_test_node *node; + struct cds_lfht_iter iter; + + printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", + "reader", pthread_self(), (unsigned long)gettid()); + + set_affinity(); + + rcu_register_thread(); + + while (!test_go) + { + } + cmm_smp_mb(); + + for (;;) { + rcu_read_lock(); + 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); + if (node == NULL) { + if (validate_lookup) { + printf("[ERROR] Lookup cannot find initial node.\n"); + exit(-1); + } + lookup_fail++; + } else { + lookup_ok++; + } + debug_yield_read(); + if (caa_unlikely(rduration)) + loop_sleep(rduration); + rcu_read_unlock(); + nr_reads++; + if (caa_unlikely(!test_duration_read())) + break; + if (caa_unlikely((nr_reads & ((1 << 10) - 1)) == 0)) + rcu_quiescent_state(); + } + + rcu_unregister_thread(); + + *count = nr_reads; + printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", + "reader", pthread_self(), (unsigned long)gettid()); + printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n", + pthread_self(), lookup_fail, lookup_ok); + return ((void*)1); + +} + +void *test_hash_rw_thr_writer(void *_count) +{ + struct lfht_test_node *node; + struct cds_lfht_node *ret_node; + struct cds_lfht_iter iter; + struct wr_count *count = _count; + int ret; + + printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", + "writer", pthread_self(), (unsigned long)gettid()); + + set_affinity(); + + rcu_register_thread(); + + while (!test_go) + { + } + cmm_smp_mb(); + + for (;;) { + if ((addremove == AR_ADD || add_only) + || (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) { + 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, + 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, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); + else + 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) { + free(node); + nr_addexist++; + } else { + if (add_replace && ret_node) { + call_rcu(&to_test_node(ret_node)->head, + free_node_cb); + nr_addexist++; + } else { + nr_add++; + } + } + } else { + /* May delete */ + rcu_read_lock(); + 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, cds_lfht_iter_get_node(&iter)); + rcu_read_unlock(); + if (ret == 0) { + node = cds_lfht_iter_get_test_node(&iter); + call_rcu(&node->head, free_node_cb); + nr_del++; + } 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 (caa_unlikely(!test_duration_write())) + break; + if (caa_unlikely(wdelay)) + loop_sleep(wdelay); + if (caa_unlikely((nr_writes & ((1 << 10) - 1)) == 0)) + rcu_quiescent_state(); + } + + rcu_unregister_thread(); + + printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", + "writer", pthread_self(), (unsigned long)gettid()); + 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->update_ops = nr_writes; + count->add = nr_add; + count->add_exist = nr_addexist; + count->remove = nr_del; + return ((void*)2); +} + +int test_hash_rw_populate_hash(void) +{ + struct lfht_test_node *node; + struct cds_lfht_node *ret_node; + + if (!init_populate) + return 0; + + 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 *)(((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, + 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, + test_hash(node->key, node->key_len, TEST_HASH_SEED), + test_match, node->key, &node->node); + else + 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) { + free(node); + nr_addexist++; + } else { + if (add_replace && ret_node) { + call_rcu(&to_test_node(ret_node)->head, free_node_cb); + nr_addexist++; + } else { + nr_add++; + } + } + nr_writes++; + } + return 0; +} -- 2.34.1