From f6c52abed3f6cc928e88c59f220a8b0f0d51c9fe Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 11 Feb 2015 17:53:57 -0800 Subject: [PATCH] changes to treiber-stack makefile --- treiber-stack/Makefile | 24 +++++-- treiber-stack/stack.c | 123 +++++++++++++++++++++++++++++++++ treiber-stack/stack.h | 35 ++++++++++ treiber-stack/stack_wildcard.c | 123 +++++++++++++++++++++++++++++++++ treiber-stack/testcase1.c | 90 ++++++++++++++++++++++++ 5 files changed, 391 insertions(+), 4 deletions(-) create mode 100644 treiber-stack/stack.c create mode 100644 treiber-stack/stack.h create mode 100644 treiber-stack/stack_wildcard.c create mode 100644 treiber-stack/testcase1.c diff --git a/treiber-stack/Makefile b/treiber-stack/Makefile index 99cac3f..b97c158 100644 --- a/treiber-stack/Makefile +++ b/treiber-stack/Makefile @@ -1,10 +1,26 @@ include ../benchmarks.mk -main: my_stack.o main.c +BENCH := stack + +NORMAL_TESTS := testcase1 + +WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS)) + +TESTS := $(NORMAL_TESTS) $(WILDCARD_TESTS) + +all: $(TESTS) + +$(BENCH).o : $(BENCH).c $(BENCH).h + $(CC) -o $@ $< $(CFLAGS) -c $(LDFLAGS) + +$(BENCH)_wildcard.o : $(BENCH)_wildcard.c $(BENCH).h + $(CC) -o $@ $< $(CFLAGS) -c $(LDFLAGS) + +$(WILDCARD_TESTS): %_wildcard : %.c $(BENCH)_wildcard.o $(CC) -o $@ $^ $(CFLAGS) $(LDFLAGS) -%.o: %.c - $(CC) -c -o $@ $^ $(CFLAGS) +$(NORMAL_TESTS): % : %.c $(BENCH).o + $(CC) -o $@ $^ $(CFLAGS) $(LDFLAGS) clean: - rm -f *.o + rm -f *.o *.d $(TESTS) diff --git a/treiber-stack/stack.c b/treiber-stack/stack.c new file mode 100644 index 0000000..9fc501d --- /dev/null +++ b/treiber-stack/stack.c @@ -0,0 +1,123 @@ +#include +#include +#include "librace.h" +#include "model-assert.h" + +#include "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/stack.h b/treiber-stack/stack.h new file mode 100644 index 0000000..8d4d789 --- /dev/null +++ b/treiber-stack/stack.h @@ -0,0 +1,35 @@ +#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 new file mode 100644 index 0000000..9fc501d --- /dev/null +++ b/treiber-stack/stack_wildcard.c @@ -0,0 +1,123 @@ +#include +#include +#include "librace.h" +#include "model-assert.h" + +#include "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/testcase1.c b/treiber-stack/testcase1.c new file mode 100644 index 0000000..b97af0f --- /dev/null +++ b/treiber-stack/testcase1.c @@ -0,0 +1,90 @@ +#include +#include +#include + +#include "model-assert.h" + +#include "stack.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; +} -- 2.34.1