#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
# 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
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
ctags -R .
###################################################################################################
-#
+#
###################################################################################################
clean:
rm -rfv output/*
# -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))
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 <errno.h>
-#include <stdio.h>
-#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
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;
}
printf("\n");
}
-
-#ifdef MAKE_list_test
-#include <errno.h>
-#include <pthread.h>
-#include <sys/time.h>
-
-#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
struct node *next[];
} node_t;
-typedef struct sl {
+struct sl {
node_t *head;
-} skiplist_t;
+};
static int random_level (void) {
unsigned r = nbd_rand();
item = (node_t *)STRIP_TAG(item->next[0]);
}
}
-
-#ifdef MAKE_skiplist_test
-#include <errno.h>
-#include <pthread.h>
-#include <sys/time.h>
-
-#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
--- /dev/null
+#include <stdio.h>
+#include <errno.h>
+#include <pthread.h>
+#include <sys/time.h>
+
+#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;
+}
--- /dev/null
+#include <stdio.h>
+#include <errno.h>
+#include <pthread.h>
+#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;
+}
--- /dev/null
+#include <stdio.h>
+#include <errno.h>
+#include <pthread.h>
+#include <sys/time.h>
+
+#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;
+}
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
projects / nbds / commitdiff