From: jdybnis Date: Sun, 30 Nov 2008 04:30:08 +0000 (+0000) Subject: use generic map interface in tests X-Git-Url: https://pd.if.org/git/?p=nbds;a=commitdiff_plain;h=df360b20f11476e53534a53c9ce11493d7c7a764 use generic map interface in tests fix a few skiplist bugs caught by new tests --- diff --git a/makefile b/makefile index 13364a8..6baa518 100644 --- a/makefile +++ b/makefile @@ -7,17 +7,16 @@ OPT := -fwhole-program -combine -03 #-DNDEBUG CFLAGS := -g -Wall -Werror -std=c99 -m64 $(OPT) #-DENABLE_TRACE INCS := $(addprefix -I, include) -TESTS := output/ll_test output/sl_test output/ht_test output/rcu_test +TESTS := output/map_test1 output/map_test2 output/rcu_test EXES := $(TESTS) -RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c -MAP_SRCS := map/map.c map/nstring.c -TEST_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) -rcu_test_SRCS := $(TEST_SRCS) test/rcu_test.c -txn_test_SRCS := $(TEST_SRCS) txn/txn.c map/hashtable.c -ll_test_SRCS := $(TEST_SRCS) test/ll_test.c map/list.c -sl_test_SRCS := $(TEST_SRCS) test/sl_test.c map/skiplist.c -ht_test_SRCS := $(TEST_SRCS) test/ht_test.c map/hashtable.c test/CuTest.c +RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c +MAP_SRCS := map/map.c map/nstring.c map/list.c map/skiplist.c map/hashtable.c + +rcu_test_SRCS := $(RUNTIME_SRCS) test/rcu_test.c +txn_test_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) txn/txn.c +map_test1_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) test/map_test1.c +map_test2_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) test/map_test2.c test/CuTest.c tests: $(TESTS) diff --git a/map/skiplist.c b/map/skiplist.c index d18ee3d..ec8a6ff 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -340,7 +340,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ // There in no need to continue linking in the item if another thread removed it. node_t *old_next = ((volatile node_t *)new_item)->next[level]; if (IS_TAGGED(old_next)) - return new_val; + return DOES_NOT_EXIST; // success // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item. if (old_next == next || SYNC_CAS(&new_item->next[level], old_next, next) == old_next) @@ -348,7 +348,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ } while (1); } while (1); } - return new_val; + return DOES_NOT_EXIST; // success } uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) { @@ -379,8 +379,9 @@ uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) { TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0); if (level == 0) return DOES_NOT_EXIST; + break; } - } while (!IS_TAGGED(old_next) || next != old_next); + } while (next != old_next); } // This has to be an atomic swap in case another thread is updating the item while we are removing it. diff --git a/test/ll_test.c b/test/map_test1.c similarity index 69% rename from test/ll_test.c rename to test/map_test1.c index 490bf7d..30d7ce0 100644 --- a/test/ll_test.c +++ b/test/map_test1.c @@ -75,26 +75,30 @@ int main (int argc, char **argv) { } } - map_ = map_alloc(MAP_TYPE_LIST); + map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; + for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { + map_ = map_alloc(map_types[i]); - struct timeval tv1, tv2; - gettimeofday(&tv1, NULL); + struct timeval tv1, tv2; + gettimeofday(&tv1, NULL); - wait_ = num_threads_; + 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) { + 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); - } + 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; - map_print(map_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); + gettimeofday(&tv2, NULL); + int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; + map_print(map_); + printf("Th:%ld Time:%dms\n", num_threads_, ms); + fflush(stdout); + } return 0; } diff --git a/test/ht_test.c b/test/map_test2.c similarity index 86% rename from test/ht_test.c rename to test/map_test2.c index e6ec9ff..7d31c87 100644 --- a/test/ht_test.c +++ b/test/map_test2.c @@ -20,10 +20,12 @@ typedef struct worker_data { int *wait; } worker_data_t; +static map_type_t map_type_; + // Test some basic stuff; add a few keys, remove a few keys void basic_test (CuTest* tc) { - map_t *ht = map_alloc(MAP_TYPE_HASHTABLE); + map_t *ht = map_alloc(map_type_); ASSERT_EQUAL( 0, map_count(ht) ); ASSERT_EQUAL( DOES_NOT_EXIST, map_add(ht,"a",2,10) ); @@ -83,7 +85,7 @@ void *simple_worker (void *arg) { map_t *ht = wd->ht; CuTest* tc = wd->tc; uint64_t d = wd->id; - int iters = 1000000; + int iters = map_type_ == MAP_TYPE_LIST ? 100 : 1000000; SYNC_ADD(wd->wait, -1); do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready @@ -94,14 +96,15 @@ void *simple_worker (void *arg) { sprintf(key, "k%u", i); TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i); CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(ht, key, strlen(key)+1, d+1) ); + rcu_update(); } for (int i = d; i < iters; i+=2) { char key[10]; sprintf(key, "k%u", i); TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i); CuAssertIntEquals_Msg(tc, key, d+1, map_remove(ht, key, strlen(key)+1) ); + rcu_update(); } - rcu_update(); } return NULL; } @@ -112,7 +115,7 @@ void simple_add_remove (CuTest* tc) { pthread_t thread[2]; worker_data_t wd[2]; int wait = 2; - map_t *ht = map_alloc(MAP_TYPE_HASHTABLE); + map_t *ht = map_alloc(map_type_); // In 2 threads, add & remove even & odd elements concurrently int i; @@ -152,17 +155,22 @@ int main (void) { nbd_init(); //lwt_set_trace_level("h0"); - // Create and run test suite - CuString *output = CuStringNew(); - CuSuite* suite = CuSuiteNew(); + map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; + for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { + map_type_ = map_types[i]; + + // Create and run test suite + CuString *output = CuStringNew(); + CuSuite* suite = CuSuiteNew(); - SUITE_ADD_TEST(suite, basic_test); - SUITE_ADD_TEST(suite, simple_add_remove); + SUITE_ADD_TEST(suite, basic_test); + SUITE_ADD_TEST(suite, simple_add_remove); - CuSuiteRun(suite); - CuSuiteSummary(suite, output); - CuSuiteDetails(suite, output); - printf("%s\n", output->buffer); + CuSuiteRun(suite); + CuSuiteSummary(suite, output); + CuSuiteDetails(suite, output); + printf("%s\n", output->buffer); + } return 0; } diff --git a/test/sl_test.c b/test/sl_test.c deleted file mode 100644 index 00f9ac0..0000000 --- a/test/sl_test.c +++ /dev/null @@ -1,100 +0,0 @@ -#include -#include -#include -#include - -#include "common.h" -#include "runtime.h" -#include "map.h" - -#define NUM_ITERATIONS 10000000 - -static volatile int wait_; -static long num_threads_; -static map_t *map_; - -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(); - uint64_t key = r & 0xF; -#if 1 - char key_str[10]; - sprintf(key_str, "%llX", key); - if (r & (1 << 8)) { - map_set(map_, key_str, strlen(key_str) + 1, (r & 0xFF)+1); - } else { - map_remove(map_, key_str, strlen(key_str) + 1); - } -#else - if (r & (1 << 8)) { - map_set(map_, (void *)key, -1, (r & 0xFF)+1); - } else { - map_remove(map_, (void *)key, -1); - } -#endif - - 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; - } - } - - map_ = map_alloc(MAP_TYPE_SKIPLIST); - - 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; - map_print(map_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); - - return 0; -}