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)
// 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)
} 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) {
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.
}
}
- 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;
}
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) );
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
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;
}
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;
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;
}
+++ /dev/null
-#include <stdio.h>
-#include <errno.h>
-#include <pthread.h>
-#include <sys/time.h>
-
-#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;
-}
projects / nbds / commitdiff