From f59f59385d850ff79016d33891fc09522ff509f3 Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 11 Feb 2015 18:14:47 -0800 Subject: [PATCH] changes --- concurrent-hashmap/Makefile | 15 +++- concurrent-hashmap/main_wildcard.cc | 58 ------------- treiber-stack/main.c | 89 -------------------- treiber-stack/my_stack.c | 123 ---------------------------- treiber-stack/my_stack.h | 35 -------- treiber-stack/stack_wildcard.c | 13 +-- 6 files changed, 18 insertions(+), 315 deletions(-) delete mode 100644 concurrent-hashmap/main_wildcard.cc delete mode 100644 treiber-stack/main.c delete mode 100644 treiber-stack/my_stack.c delete mode 100644 treiber-stack/my_stack.h diff --git a/concurrent-hashmap/Makefile b/concurrent-hashmap/Makefile index e386b4d..fece808 100644 --- a/concurrent-hashmap/Makefile +++ b/concurrent-hashmap/Makefile @@ -1,5 +1,6 @@ include ../benchmarks.mk +BENCH := hashmap NORMAL_TESTS := testcase1 testcase2 WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS)) @@ -10,11 +11,17 @@ all: $(TESTS) $(WILDCARD_TESTS): CXXFLAGS += -DWILDCARD -$(WILDCARD_TESTS): %_wildcard : %.cc hashmap_wildcard.h - $(CXX) -o $@ $< $(SPEC_OBJ) $(CXXFLAGS) $(LDFLAGS) +$(BENCH).o : $(BENCH).h + $(CXX) -o $@ $< $(CXXFLAGS) -c $(LDFLAGS) -$(NORMAL_TESTS): % : %.cc hashmap.h - $(CXX) -o $@ $< $(SPEC_OBJ) $(CXXFLAGS) $(LDFLAGS) +$(BENCH)_wildcard.o : $(BENCH)_wildcard.h + $(CXX) -o $@ $< $(CXXFLAGS) -c $(LDFLAGS) + +$(WILDCARD_TESTS): %_wildcard : %.cc $(BENCH)_wildcard.o + $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS) + +$(NORMAL_TESTS): % : %.cc $(BENCH).o + $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS) clean: rm -f *.o *.d $(TESTS) diff --git a/concurrent-hashmap/main_wildcard.cc b/concurrent-hashmap/main_wildcard.cc deleted file mode 100644 index 4a6f904..0000000 --- a/concurrent-hashmap/main_wildcard.cc +++ /dev/null @@ -1,58 +0,0 @@ -#include -#include -#include "hashmap_wildcard.h" - -HashMap *table; - -Key *k1, *k2; -Value *r1, *r2, *r3, *r4, *v1, *v2; - -void printKey(Key *key) { - if (key) - printf("pos = (%d, %d, %d)\n", key->x, key->y, key->z); - else - printf("pos = NULL\n"); -} - -void printValue(Value *value) { - if (value) - printf("velocity = (%d, %d, %d)\n", value->vX, value->vY, value->vZ); - else - printf("velocity = NULL\n"); -} - -void threadA(void *arg) { - k1 = new Key(1, 1, 1); - k2 = new Key(3, 4, 5); - v1 = new Value(10, 10, 10); - r1 = table->put(k1, v1); - //printValue(r1); - r2 = table->get(k2); - printf("Thrd A:\n"); - printValue(r2); -} - -void threadB(void *arg) { - k1 = new Key(1, 1, 1); - k2 = new Key(3, 4, 5); - v2 = new Value(30, 40, 50); - r3 = table->put(k2, v2); - //printValue(r3); - r4 = table->get(k1); - printf("Thrd B:\n"); - printValue(r4); -} - -int user_main(int argc, char *argv[]) { - thrd_t t1, t2; - table = new HashMap; - - thrd_create(&t1, threadA, NULL); - thrd_create(&t2, threadB, NULL); - thrd_join(t1); - thrd_join(t2); - - return 0; -} - - diff --git a/treiber-stack/main.c b/treiber-stack/main.c deleted file mode 100644 index d27242e..0000000 --- a/treiber-stack/main.c +++ /dev/null @@ -1,89 +0,0 @@ -#include -#include -#include - -#include "my_stack.h" -#include "model-assert.h" - -static int procs = 4; -static stack_t *stack; -static thrd_t *threads; -static int num_threads; - -unsigned int idx1, idx2; -unsigned int a, b; - - -atomic_int x[3]; - -int get_thread_num() -{ - thrd_t curr = thrd_current(); - int i; - for (i = 0; i < num_threads; i++) - if (curr.priv == threads[i].priv) - return i; - MODEL_ASSERT(0); - return -1; -} - -static void main_task(void *param) -{ - unsigned int val; - int pid = *((int *)param); - - if (pid % 4 == 0) { - atomic_store_explicit(&x[1], 17, relaxed); - push(stack, 1); - } else if (pid % 4 == 1) { - atomic_store_explicit(&x[2], 37, relaxed); - push(stack, 2); - } else if (pid % 4 == 2) {/* - idx1 = pop(stack); - if (idx1 != 0) { - a = atomic_load_explicit(&x[idx1], relaxed); - printf("a: %d\n", a); - }*/ - } else { - idx2 = pop(stack); - if (idx2 != 0) { - b = atomic_load_explicit(&x[idx2], relaxed); - printf("b: %d\n", b); - } - } -} - -int user_main(int argc, char **argv) -{ - int i; - int *param; - unsigned int in_sum = 0, out_sum = 0; - - atomic_init(&x[1], 0); - atomic_init(&x[2], 0); - - stack = calloc(1, sizeof(*stack)); - - num_threads = procs; - threads = malloc(num_threads * sizeof(thrd_t)); - param = malloc(num_threads * sizeof(*param)); - - init_stack(stack, num_threads); - - for (i = 0; i < num_threads; i++) { - param[i] = i; - thrd_create(&threads[i], main_task, ¶m[i]); - } - for (i = 0; i < num_threads; i++) - thrd_join(threads[i]); - - bool correct = false; - //correct |= (a == 17 || a == 37 || a == 0); - //MODEL_ASSERT(correct); - - free(param); - free(threads); - free(stack); - - return 0; -} diff --git a/treiber-stack/my_stack.c b/treiber-stack/my_stack.c deleted file mode 100644 index 5f3cc89..0000000 --- a/treiber-stack/my_stack.c +++ /dev/null @@ -1,123 +0,0 @@ -#include -#include -#include "librace.h" -#include "model-assert.h" - -#include "my_stack.h" - -#define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */ -#define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */ - -#define POISON_IDX 0x666 - -static unsigned int (*free_lists)[MAX_FREELIST]; - -/* Search this thread's free list for a "new" node */ -static unsigned int new_node() -{ - int i; - int t = get_thread_num(); - for (i = 0; i < MAX_FREELIST; i++) { - //unsigned int node = load_32(&free_lists[t][i]); - unsigned int node = free_lists[t][i]; - if (node) { - //store_32(&free_lists[t][i], 0); - free_lists[t][i] = 0; - return node; - } - } - /* free_list is empty? */ - MODEL_ASSERT(0); - return 0; -} - -/* Place this node index back on this thread's free list */ -static void reclaim(unsigned int node) -{ - int i; - int t = get_thread_num(); - - /* Don't reclaim NULL node */ - //MODEL_ASSERT(node); - - for (i = 0; i < MAX_FREELIST; i++) { - /* Should never race with our own thread here */ - //unsigned int idx = load_32(&free_lists[t][i]); - unsigned int idx = free_lists[t][i]; - - /* Found empty spot in free list */ - if (idx == 0) { - //store_32(&free_lists[t][i], node); - free_lists[t][i] = node; - return; - } - } - /* free list is full? */ - MODEL_ASSERT(0); -} - -void init_stack(stack_t *s, int num_threads) -{ - int i, j; - - /* Initialize each thread's free list with INITIAL_FREE pointers */ - /* The actual nodes are initialized with poison indexes */ - free_lists = malloc(num_threads * sizeof(*free_lists)); - for (i = 0; i < num_threads; i++) { - for (j = 0; j < INITIAL_FREE; j++) { - free_lists[i][j] = 1 + i * MAX_FREELIST + j; - atomic_init(&s->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0)); - } - } - - /* initialize stack */ - atomic_init(&s->top, MAKE_POINTER(0, 0)); -} - -void push(stack_t *s, unsigned int val) { - unsigned int nodeIdx = new_node(); - node_t *node = &s->nodes[nodeIdx]; - node->value = val; - pointer oldTop, newTop; - bool success; - while (true) { - // acquire - oldTop = atomic_load_explicit(&s->top, acquire); - newTop = MAKE_POINTER(nodeIdx, get_count(oldTop) + 1); - // relaxed - atomic_store_explicit(&node->next, oldTop, relaxed); - - // release & relaxed - success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop, - newTop, release, relaxed); - if (success) - break; - } -} - -unsigned int pop(stack_t *s) -{ - pointer oldTop, newTop, next; - node_t *node; - bool success; - int val; - while (true) { - // acquire - oldTop = atomic_load_explicit(&s->top, acquire); - if (get_ptr(oldTop) == 0) - return 0; - node = &s->nodes[get_ptr(oldTop)]; - // relaxed - next = atomic_load_explicit(&node->next, relaxed); - newTop = MAKE_POINTER(get_ptr(next), get_count(oldTop) + 1); - // release & relaxed - success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop, - newTop, release, relaxed); - if (success) - break; - } - val = node->value; - /* Reclaim the used slot */ - reclaim(get_ptr(oldTop)); - return val; -} diff --git a/treiber-stack/my_stack.h b/treiber-stack/my_stack.h deleted file mode 100644 index 8d4d789..0000000 --- a/treiber-stack/my_stack.h +++ /dev/null @@ -1,35 +0,0 @@ -#include - -#define release memory_order_release -#define acquire memory_order_acquire -#define relaxed memory_order_relaxed - -#define MAX_NODES 0xf - -typedef unsigned long long pointer; -typedef atomic_ullong pointer_t; - -#define MAKE_POINTER(ptr, count) ((((pointer)count) << 32) | ptr) -#define PTR_MASK 0xffffffffLL -#define COUNT_MASK (0xffffffffLL << 32) - -static inline void set_count(pointer *p, unsigned int val) { *p = (*p & ~COUNT_MASK) | ((pointer)val << 32); } -static inline void set_ptr(pointer *p, unsigned int val) { *p = (*p & ~PTR_MASK) | val; } -static inline unsigned int get_count(pointer p) { return (p & COUNT_MASK) >> 32; } -static inline unsigned int get_ptr(pointer p) { return p & PTR_MASK; } - -typedef struct node { - unsigned int value; - pointer_t next; - -} node_t; - -typedef struct { - pointer_t top; - node_t nodes[MAX_NODES + 1]; -} stack_t; - -void init_stack(stack_t *s, int num_threads); -void push(stack_t *s, unsigned int val); -unsigned int pop(stack_t *s); -int get_thread_num(); diff --git a/treiber-stack/stack_wildcard.c b/treiber-stack/stack_wildcard.c index 9fc501d..d7c11ac 100644 --- a/treiber-stack/stack_wildcard.c +++ b/treiber-stack/stack_wildcard.c @@ -4,6 +4,7 @@ #include "model-assert.h" #include "stack.h" +#include "wildcard.h" #define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */ #define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */ @@ -82,14 +83,14 @@ void push(stack_t *s, unsigned int val) { bool success; while (true) { // acquire - oldTop = atomic_load_explicit(&s->top, acquire); + oldTop = atomic_load_explicit(&s->top, wildcard(1)); newTop = MAKE_POINTER(nodeIdx, get_count(oldTop) + 1); // relaxed - atomic_store_explicit(&node->next, oldTop, relaxed); + atomic_store_explicit(&node->next, oldTop, wildcard(2)); // release & relaxed success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop, - newTop, release, relaxed); + newTop, wildcard(3), wildcard(4)); if (success) break; } @@ -103,16 +104,16 @@ unsigned int pop(stack_t *s) int val; while (true) { // acquire - oldTop = atomic_load_explicit(&s->top, acquire); + oldTop = atomic_load_explicit(&s->top, wildcard(5)); if (get_ptr(oldTop) == 0) return 0; node = &s->nodes[get_ptr(oldTop)]; // relaxed - next = atomic_load_explicit(&node->next, relaxed); + next = atomic_load_explicit(&node->next, wildcard(6)); newTop = MAKE_POINTER(get_ptr(next), get_count(oldTop) + 1); // release & relaxed success = atomic_compare_exchange_strong_explicit(&s->top, &oldTop, - newTop, release, relaxed); + newTop, wildcard(7), wildcard(8)); if (success) break; } -- 2.34.1