From b21e1c182a2e469240d2b1cbbda37f2dfeb880d9 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Tue, 25 Nov 2008 09:30:10 +0000 Subject: [PATCH] separate tests out into their own files --- include/struct.h | 22 ++++++++-- makefile | 36 +++++++-------- runtime/rcu.c | 109 ---------------------------------------------- struct/list.c | 96 ++-------------------------------------- struct/skiplist.c | 94 +-------------------------------------- test/ll_test.c | 90 ++++++++++++++++++++++++++++++++++++++ test/rcu_test.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++ test/sl_test.c | 90 ++++++++++++++++++++++++++++++++++++++ txn/txn.c | 8 ---- 9 files changed, 331 insertions(+), 323 deletions(-) create mode 100644 test/ll_test.c create mode 100644 test/rcu_test.c create mode 100644 test/sl_test.c diff --git a/include/struct.h b/include/struct.h index 5894c0b..3dec0fa 100644 --- a/include/struct.h +++ b/include/struct.h @@ -8,12 +8,28 @@ #define EXPECT_WHATEVER (-2) typedef struct hti *hashtable_t; - hashtable_t *ht_alloc (void); void ht_free (hashtable_t *ht); -uint64_t ht_get (hashtable_t *ht, const char *key, uint32_t len); + uint64_t ht_compare_and_set (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val); +uint64_t ht_get (hashtable_t *ht, const char *key, uint32_t len); uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len); -uint64_t ht_count (hashtable_t *ht); +uint64_t ht_count (hashtable_t *ht); + +typedef struct ll list_t; +list_t * ll_alloc (void); + +uint64_t ll_lookup (list_t *ll, uint64_t key); +uint64_t ll_add (list_t *ll, uint64_t key, uint64_t value); +uint64_t ll_remove (list_t *ll, uint64_t key); +void ll_print (list_t *ll); + +typedef struct sl skiplist_t; +skiplist_t * sl_alloc (void); + +uint64_t sl_lookup (skiplist_t *sl, uint64_t key); +uint64_t sl_add (skiplist_t *sl, uint64_t key, uint64_t value); +uint64_t sl_remove (skiplist_t *sl, uint64_t key); +void sl_print (skiplist_t *sl); #endif//STRUCT_H diff --git a/makefile b/makefile index a4700ef..1e4072f 100644 --- a/makefile +++ b/makefile @@ -3,23 +3,23 @@ # http://creativecommons.org/licenses/publicdomain # ################################################################################################### -# Makefile for building programs with whole-program interfile optimization +# Makefile for building programs with whole-program interfile optimization ################################################################################################### -OPT := -fwhole-program -combine -03 #-DNDEBUG -CFLAGS := -g -Wall -Werror -std=c99 -m64 -fnested-functions $(OPT) #-DENABLE_TRACE +OPT := -fwhole-program -combine -03# -DNDEBUG +CFLAGS := -g -Wall -Werror -std=c99 -m64 -fnested-functions $(OPT)# -DENABLE_TRACE INCS := $(addprefix -I, include) -TESTS := output/rcu_test output/list_test output/skiplist_test output/ht_test output/txn_test +TESTS := output/ll_test output/sl_test output/ht_test output/rcu_test EXES := $(TESTS) -RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c -TEST_SRCS := $(RUNTIME_SRCS) -rcu_test_SRCS := $(TEST_SRCS) -list_test_SRCS := $(TEST_SRCS) struct/list.c -skiplist_test_SRCS := $(TEST_SRCS) struct/skiplist.c -ht_test_SRCS := $(TEST_SRCS) struct/hashtable.c test/ht_test.c test/CuTest.c -txn_test_SRCS := $(TEST_SRCS) struct/hashtable.c txn/txn.c +RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c +TEST_SRCS := $(RUNTIME_SRCS) +rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c +txn_test_SRCS := $(TEST_SRCS) struct/hashtable.c txn/txn.c +ll_test_SRCS := $(TEST_SRCS) struct/list.c test/ll_test.c +sl_test_SRCS := $(TEST_SRCS) struct/skiplist.c test/sl_test.c +ht_test_SRCS := $(TEST_SRCS) struct/hashtable.c test/ht_test.c test/CuTest.c -tests: $(TESTS) +tests: $(TESTS) ################################################################################################### # Run the tests @@ -27,18 +27,18 @@ tests: $(TESTS) test: $(addsuffix .log, $(TESTS)) @echo > /dev/null -$(addsuffix .log, $(TESTS)) : %.log : % +$(addsuffix .log, $(TESTS)) : %.log : % @echo "Running $*" && $* | tee $*.log ################################################################################################### -# Rebuild an executable if any of it's source files need to be recompiled +# Rebuild an executable if any of it's source files need to be recompiled # -# Note: Calculating dependancies as a side-effect of compilation is disabled. There is a bug in +# Note: Calculating dependancies as a side-effect of compilation is disabled. There is a bug in # gcc. Compilation fails when -MM -MF is used and there is more than one source file. # -MM -MT $@.d -MF $@.d ################################################################################################### $(EXES): output/% : output/%.d makefile - gcc $(CFLAGS) $(INCS) -DMAKE_$* -o $@ $($*_SRCS) + gcc $(CFLAGS) $(INCS) -o $@ $($*_SRCS) ################################################################################################### # Build tags file for vi @@ -47,7 +47,7 @@ tags: ctags -R . ################################################################################################### -# +# ################################################################################################### clean: rm -rfv output/* @@ -61,6 +61,6 @@ clean: # -MM is used with -combine. ################################################################################################### $(addsuffix .d, $(EXES)) : output/%.d : - gcc $(CFLAGS:-combine:) $(INCS) -DMAKE_$* -MM -MT $@ $($*_SRCS) > $@ + gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > $@ -include $(addsuffix .d, $(EXES)) diff --git a/runtime/rcu.c b/runtime/rcu.c index f5e3c3c..b163348 100644 --- a/runtime/rcu.c +++ b/runtime/rcu.c @@ -100,112 +100,3 @@ void nbd_defer_free (void *x) { TRACE("r0", "nbd_defer_free: put %p on queue at position %llu", x, pending_[tid_]->head); rcu_post(pending_[tid_]->head); } - -#ifdef MAKE_rcu_test -#include -#include -#include "runtime.h" - -#define NUM_ITERATIONS 10000000 - -typedef struct node { - struct node *next; -} node_t; - -typedef struct lifo { - node_t *head; -} lifo_t; - -static volatile int wait_; -static lifo_t *stk_; - -static lifo_t *lifo_alloc (void) { - lifo_t *stk = (lifo_t *)nbd_malloc(sizeof(lifo_t)); - memset(stk, 0, sizeof(lifo_t)); - return stk; -} - -static void lifo_aba_push (lifo_t *stk, node_t *x) { - node_t *head; - do { - head = ((volatile lifo_t *)stk)->head; - ((volatile node_t *)x)->next = head; - } while (__sync_val_compare_and_swap(&stk->head, head, x) != head); -} - -node_t *lifo_aba_pop (lifo_t *stk) { - node_t *head; - do { - head = ((volatile lifo_t *)stk)->head; - if (head == NULL) - return NULL; - } while (__sync_val_compare_and_swap(&stk->head, head, head->next) != head); - head->next = NULL; - return head; -} - -node_t *node_alloc (void) { - node_t *node = (node_t *)nbd_malloc(sizeof(node_t)); - memset(node, 0, sizeof(node_t)); - return node; -} - -void *worker (void *arg) { - int id = (int)(size_t)arg; - unsigned int rand_seed = (unsigned int)id + 1; - - // Wait for all the worker threads to be ready. - __sync_fetch_and_add(&wait_, -1); - do {} while (wait_); - - int i; - for (i = 0; i < NUM_ITERATIONS; ++ i) { - int n = rand_r(&rand_seed); - if (n & 0x1) { - lifo_aba_push(stk_, node_alloc()); - } else { - node_t *x = lifo_aba_pop(stk_); - if (x) { - nbd_defer_free(x); - } - } - rcu_update(); - } - - return NULL; -} - -int main (int argc, char **argv) { - nbd_init(); - //lwt_set_trace_level("m0r0"); - - int num_threads = 2; - if (argc == 2) - { - errno = 0; - num_threads = strtol(argv[1], NULL, 10); - if (errno) { - fprintf(stderr, "%s: Invalid argument for number of threads\n", argv[0]); - return -1; - } - if (num_threads <= 0) { - fprintf(stderr, "%s: Number of threads must be at least 1\n", argv[0]); - return -1; - } - } - - stk_ = lifo_alloc(); - wait_ = num_threads; - - pthread_t thread[num_threads]; - for (int i = 0; i < num_threads; ++i) { - int rc = nbd_thread_create(thread + i, i, worker, (void *)(size_t)i); - if (rc != 0) { perror("pthread_create"); return rc; } - } - for (int i = 0; i < num_threads; ++i) { - pthread_join(thread[i], NULL); - } - - return 0; -} -#endif//rcu_test diff --git a/struct/list.c b/struct/list.c index c6c1780..29784a9 100644 --- a/struct/list.c +++ b/struct/list.c @@ -18,11 +18,11 @@ typedef struct node { struct node *next; } node_t; -typedef struct ll { +struct ll { node_t *head; -} list_t; +}; -node_t *node_alloc (uint64_t key, uint64_t value) { +static node_t *node_alloc (uint64_t key, uint64_t value) { node_t *item = (node_t *)nbd_malloc(sizeof(node_t)); memset(item, 0, sizeof(node_t)); item->key = key; @@ -191,93 +191,3 @@ void ll_print (list_t *ll) { } printf("\n"); } - -#ifdef MAKE_list_test -#include -#include -#include - -#include "runtime.h" - -#define NUM_ITERATIONS 10000000 - -static volatile int wait_; -static long num_threads_; -static list_t *ll_; - -void *worker (void *arg) { - - // Wait for all the worker threads to be ready. - SYNC_ADD(&wait_, -1); - do {} while (wait_); - - for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { - unsigned r = nbd_rand(); - int key = r & 0xF; - if (r & (1 << 8)) { - ll_add(ll_, key, 1); - } else { - ll_remove(ll_, key); - } - - rcu_update(); - } - - return NULL; -} - -int main (int argc, char **argv) { - nbd_init(); - //lwt_set_trace_level("m0l0"); - - char* program_name = argv[0]; - pthread_t thread[MAX_NUM_THREADS]; - - if (argc > 2) { - fprintf(stderr, "Usage: %s num_threads\n", program_name); - return -1; - } - - num_threads_ = 2; - if (argc == 2) - { - errno = 0; - num_threads_ = strtol(argv[1], NULL, 10); - if (errno) { - fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); - return -1; - } - if (num_threads_ <= 0) { - fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); - return -1; - } - if (num_threads_ > MAX_NUM_THREADS) { - fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); - return -1; - } - } - - ll_ = ll_alloc(); - - struct timeval tv1, tv2; - gettimeofday(&tv1, NULL); - - wait_ = num_threads_; - - for (int i = 0; i < num_threads_; ++i) { - int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i); - if (rc != 0) { perror("pthread_create"); return rc; } - } - - for (int i = 0; i < num_threads_; ++i) { - pthread_join(thread[i], NULL); - } - - gettimeofday(&tv2, NULL); - int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; - ll_print(ll_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); - - return 0; -} -#endif//list_test diff --git a/struct/skiplist.c b/struct/skiplist.c index 1d65efa..df8e98a 100644 --- a/struct/skiplist.c +++ b/struct/skiplist.c @@ -33,9 +33,9 @@ typedef struct node { struct node *next[]; } node_t; -typedef struct sl { +struct sl { node_t *head; -} skiplist_t; +}; static int random_level (void) { unsigned r = nbd_rand(); @@ -332,93 +332,3 @@ void sl_print (skiplist_t *sl) { item = (node_t *)STRIP_TAG(item->next[0]); } } - -#ifdef MAKE_skiplist_test -#include -#include -#include - -#include "runtime.h" - -#define NUM_ITERATIONS 10000000 - -static volatile int wait_; -static long num_threads_; -static skiplist_t *sl_; - -void *worker (void *arg) { - - // Wait for all the worker threads to be ready. - SYNC_ADD(&wait_, -1); - do {} while (wait_); - - for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { - unsigned r = nbd_rand(); - int key = r & 0xF; - if (r & (1 << 8)) { - sl_add(sl_, key, 1); - } else { - sl_remove(sl_, key); - } - - rcu_update(); - } - - return NULL; -} - -int main (int argc, char **argv) { - nbd_init(); - lwt_set_trace_level("s3"); - - char* program_name = argv[0]; - pthread_t thread[MAX_NUM_THREADS]; - - if (argc > 2) { - fprintf(stderr, "Usage: %s num_threads\n", program_name); - return -1; - } - - num_threads_ = 2; - if (argc == 2) - { - errno = 0; - num_threads_ = strtol(argv[1], NULL, 10); - if (errno) { - fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); - return -1; - } - if (num_threads_ <= 0) { - fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); - return -1; - } - if (num_threads_ > MAX_NUM_THREADS) { - fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); - return -1; - } - } - - sl_ = sl_alloc(); - - struct timeval tv1, tv2; - gettimeofday(&tv1, NULL); - - wait_ = num_threads_; - - for (int i = 0; i < num_threads_; ++i) { - int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i); - if (rc != 0) { perror("pthread_create"); return rc; } - } - - for (int i = 0; i < num_threads_; ++i) { - pthread_join(thread[i], NULL); - } - - gettimeofday(&tv2, NULL); - int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; - sl_print(sl_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); - - return 0; -} -#endif//skiplist_test diff --git a/test/ll_test.c b/test/ll_test.c new file mode 100644 index 0000000..e7c9337 --- /dev/null +++ b/test/ll_test.c @@ -0,0 +1,90 @@ +#include +#include +#include +#include + +#include "common.h" +#include "runtime.h" +#include "struct.h" + +#define NUM_ITERATIONS 10000000 + +static volatile int wait_; +static long num_threads_; +static list_t *ll_; + +void *worker (void *arg) { + + // Wait for all the worker threads to be ready. + SYNC_ADD(&wait_, -1); + do {} while (wait_); + + for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { + unsigned r = nbd_rand(); + int key = r & 0xF; + if (r & (1 << 8)) { + ll_add(ll_, key, 1); + } else { + ll_remove(ll_, key); + } + + rcu_update(); + } + + return NULL; +} + +int main (int argc, char **argv) { + nbd_init(); + //lwt_set_trace_level("m0l0"); + + char* program_name = argv[0]; + pthread_t thread[MAX_NUM_THREADS]; + + if (argc > 2) { + fprintf(stderr, "Usage: %s num_threads\n", program_name); + return -1; + } + + num_threads_ = 2; + if (argc == 2) + { + errno = 0; + num_threads_ = strtol(argv[1], NULL, 10); + if (errno) { + fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); + return -1; + } + if (num_threads_ <= 0) { + fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); + return -1; + } + if (num_threads_ > MAX_NUM_THREADS) { + fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); + return -1; + } + } + + ll_ = ll_alloc(); + + struct timeval tv1, tv2; + gettimeofday(&tv1, NULL); + + wait_ = num_threads_; + + for (int i = 0; i < num_threads_; ++i) { + int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i); + if (rc != 0) { perror("pthread_create"); return rc; } + } + + for (int i = 0; i < num_threads_; ++i) { + pthread_join(thread[i], NULL); + } + + gettimeofday(&tv2, NULL); + int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; + ll_print(ll_); + printf("Th:%ld Time:%dms\n", num_threads_, ms); + + return 0; +} diff --git a/test/rcu_test.c b/test/rcu_test.c new file mode 100644 index 0000000..96d196b --- /dev/null +++ b/test/rcu_test.c @@ -0,0 +1,109 @@ +#include +#include +#include +#include "common.h" +#include "runtime.h" +#include "mem.h" + +#define NUM_ITERATIONS 10000000 + +typedef struct node { + struct node *next; +} node_t; + +typedef struct lifo { + node_t *head; +} lifo_t; + +static volatile int wait_; +static lifo_t *stk_; + +static lifo_t *lifo_alloc (void) { + lifo_t *stk = (lifo_t *)nbd_malloc(sizeof(lifo_t)); + memset(stk, 0, sizeof(lifo_t)); + return stk; +} + +static void lifo_aba_push (lifo_t *stk, node_t *x) { + node_t *head; + do { + head = ((volatile lifo_t *)stk)->head; + ((volatile node_t *)x)->next = head; + } while (__sync_val_compare_and_swap(&stk->head, head, x) != head); +} + +node_t *lifo_aba_pop (lifo_t *stk) { + node_t *head; + do { + head = ((volatile lifo_t *)stk)->head; + if (head == NULL) + return NULL; + } while (__sync_val_compare_and_swap(&stk->head, head, head->next) != head); + head->next = NULL; + return head; +} + +node_t *node_alloc (void) { + node_t *node = (node_t *)nbd_malloc(sizeof(node_t)); + memset(node, 0, sizeof(node_t)); + return node; +} + +void *worker (void *arg) { + int id = (int)(size_t)arg; + unsigned int rand_seed = (unsigned int)id + 1; + + // Wait for all the worker threads to be ready. + __sync_fetch_and_add(&wait_, -1); + do {} while (wait_); + + int i; + for (i = 0; i < NUM_ITERATIONS; ++ i) { + int n = rand_r(&rand_seed); + if (n & 0x1) { + lifo_aba_push(stk_, node_alloc()); + } else { + node_t *x = lifo_aba_pop(stk_); + if (x) { + nbd_defer_free(x); + } + } + rcu_update(); + } + + return NULL; +} + +int main (int argc, char **argv) { + nbd_init(); + //lwt_set_trace_level("m0r0"); + + int num_threads = 2; + if (argc == 2) + { + errno = 0; + num_threads = strtol(argv[1], NULL, 10); + if (errno) { + fprintf(stderr, "%s: Invalid argument for number of threads\n", argv[0]); + return -1; + } + if (num_threads <= 0) { + fprintf(stderr, "%s: Number of threads must be at least 1\n", argv[0]); + return -1; + } + } + + stk_ = lifo_alloc(); + wait_ = num_threads; + + pthread_t thread[num_threads]; + for (int i = 0; i < num_threads; ++i) { + int rc = nbd_thread_create(thread + i, i, worker, (void *)(size_t)i); + if (rc != 0) { perror("pthread_create"); return rc; } + } + for (int i = 0; i < num_threads; ++i) { + pthread_join(thread[i], NULL); + } + + return 0; +} diff --git a/test/sl_test.c b/test/sl_test.c new file mode 100644 index 0000000..9fc6466 --- /dev/null +++ b/test/sl_test.c @@ -0,0 +1,90 @@ +#include +#include +#include +#include + +#include "common.h" +#include "runtime.h" +#include "struct.h" + +#define NUM_ITERATIONS 10000000 + +static volatile int wait_; +static long num_threads_; +static skiplist_t *sl_; + +void *worker (void *arg) { + + // Wait for all the worker threads to be ready. + SYNC_ADD(&wait_, -1); + do {} while (wait_); + + for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { + unsigned r = nbd_rand(); + int key = r & 0xF; + if (r & (1 << 8)) { + sl_add(sl_, key, 1); + } else { + sl_remove(sl_, key); + } + + rcu_update(); + } + + return NULL; +} + +int main (int argc, char **argv) { + nbd_init(); + //lwt_set_trace_level("s3"); + + char* program_name = argv[0]; + pthread_t thread[MAX_NUM_THREADS]; + + if (argc > 2) { + fprintf(stderr, "Usage: %s num_threads\n", program_name); + return -1; + } + + num_threads_ = 2; + if (argc == 2) + { + errno = 0; + num_threads_ = strtol(argv[1], NULL, 10); + if (errno) { + fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); + return -1; + } + if (num_threads_ <= 0) { + fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); + return -1; + } + if (num_threads_ > MAX_NUM_THREADS) { + fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); + return -1; + } + } + + sl_ = sl_alloc(); + + struct timeval tv1, tv2; + gettimeofday(&tv1, NULL); + + wait_ = num_threads_; + + for (int i = 0; i < num_threads_; ++i) { + int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i); + if (rc != 0) { perror("pthread_create"); return rc; } + } + + for (int i = 0; i < num_threads_; ++i) { + pthread_join(thread[i], NULL); + } + + gettimeofday(&tv2, NULL); + int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; + sl_print(sl_); + printf("Th:%ld Time:%dms\n", num_threads_, ms); + + return 0; +} diff --git a/txn/txn.c b/txn/txn.c index 8f54370..b0b6174 100644 --- a/txn/txn.c +++ b/txn/txn.c @@ -240,11 +240,3 @@ void txn_ht_put (txn_t *txn, const char *key, uint32_t key_len, int64_t value) { txn->writes[i].key = key; txn->writes[i].rec = update; } - -#ifdef MAKE_txn_test -#include "runtime.h" -int main (void) { - nbd_init(); - return 0; -} -#endif//txn_test -- 2.40.0