From bab731cf43b743adfd95447f5f72200cd22611dd Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Fri, 13 Feb 2015 00:52:46 -0800 Subject: [PATCH] changes to treiber --- treiber-stack/Makefile | 14 ++----- treiber-stack/stack.h | 64 ++++++++++++++++++-------------- treiber-stack/stack_wildcard.h | 49 +++++++++++++++++++++++++ treiber-stack/testcase1.cc | 67 ++++++++++++++++++++++++++++++++++ 4 files changed, 157 insertions(+), 37 deletions(-) create mode 100644 treiber-stack/stack_wildcard.h create mode 100644 treiber-stack/testcase1.cc diff --git a/treiber-stack/Makefile b/treiber-stack/Makefile index b97c158..40b3cb5 100644 --- a/treiber-stack/Makefile +++ b/treiber-stack/Makefile @@ -10,17 +10,11 @@ TESTS := $(NORMAL_TESTS) $(WILDCARD_TESTS) all: $(TESTS) -$(BENCH).o : $(BENCH).c $(BENCH).h - $(CC) -o $@ $< $(CFLAGS) -c $(LDFLAGS) +$(WILDCARD_TESTS): %_wildcard : %.cc $(BENCH)_wildcard.h + $(CXX) -o $@ $^ $(CXXFLAGS) $(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) - -$(NORMAL_TESTS): % : %.c $(BENCH).o - $(CC) -o $@ $^ $(CFLAGS) $(LDFLAGS) +$(NORMAL_TESTS): % : %.cc $(BENCH).h + $(CXX) -o $@ $^ $(CXXFLAGS) $(LDFLAGS) clean: rm -f *.o *.d $(TESTS) diff --git a/treiber-stack/stack.h b/treiber-stack/stack.h index 8d4d789..de551cb 100644 --- a/treiber-stack/stack.h +++ b/treiber-stack/stack.h @@ -1,35 +1,45 @@ #include +#include #define release memory_order_release #define acquire memory_order_acquire +#define acq_rel memory_order_acq_rel #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 { +struct node { unsigned int value; - pointer_t next; - -} node_t; - -typedef struct { - pointer_t top; - node_t nodes[MAX_NODES + 1]; -} stack_t; + node *next; + + node(unsigned int v) { + value = v; + next = NULL; + } +}; + +struct stack { + atomic top; + + stack() { + atomic_init(&top, NULL); + } + + void push(unsigned int val) { + node *n = new node(val); + node *old = top.load(acquire); + do { + n->next = old; + } while (!top.compare_exchange_strong(old, n, acq_rel, relaxed)); + } + + unsigned int pop() { + node *old = top.load(acquire); + node *n; + do { + if (!old) + return 0; + n = old->next; + } while (!top.compare_exchange_strong(old, n, acq_rel, acquire)); + return old->value; + } +}; -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.h b/treiber-stack/stack_wildcard.h new file mode 100644 index 0000000..75c375a --- /dev/null +++ b/treiber-stack/stack_wildcard.h @@ -0,0 +1,49 @@ +#include +#include + +#include "wildcard.h" + +#define release memory_order_release +#define acquire memory_order_acquire +#define acq_rel memory_order_acq_rel +#define relaxed memory_order_relaxed + +struct node { + unsigned int value; + node *next; + + node(unsigned int v) { + value = v; + next = NULL; + } +}; + +struct stack { + atomic top; + + stack() { + atomic_init(&top, NULL); + } + + void push(unsigned int val) { + node *n = new node(val); + node *old = top.load(wildcard(1)); // acquire + do { + n->next = old; + } while (!top.compare_exchange_strong(old, n, wildcard(2), wildcard(3))); + // acq_rel & relaxed + } + + unsigned int pop() { + node *old = top.load(wildcard(4)); // acquire + node *n; + do { + if (!old) + return 0; + n = old->next; + } while (!top.compare_exchange_strong(old, n, wildcard(5), wildcard(6))); + // acq_rel & acquire + return old->value; + } +}; + diff --git a/treiber-stack/testcase1.cc b/treiber-stack/testcase1.cc new file mode 100644 index 0000000..7ca474d --- /dev/null +++ b/treiber-stack/testcase1.cc @@ -0,0 +1,67 @@ +#include +#include +#include +#include "model-assert.h" + +#include "stack.h" + +static int procs = 4; +static stack *s; + +unsigned int idx1, idx2; +unsigned int a, b; + + +atomic_int x[3]; + +static void main_task(void *param) +{ + unsigned int val; + int pid = *((int *)param); + + if (pid % 4 == 0) { + atomic_store_explicit(&x[1], 17, relaxed); + } else if (pid % 4 == 1) { + atomic_store_explicit(&x[2], 37, relaxed); + s->push(2); + } else if (pid % 4 == 2) { + idx1 = s->pop(); + if (idx1 != 0) { + a = atomic_load_explicit(&x[idx1], relaxed); + } + } else { + idx2 = s->pop(); + if (idx2 != 0) { + b = atomic_load_explicit(&x[idx2], relaxed); + } + } +} + +int user_main(int argc, char **argv) +{ + int i; + int *param; + + atomic_init(&x[1], 0); + atomic_init(&x[2], 0); + + s = new stack; + + int num_threads = 4; + + param = new int[num_threads]; + thrd_t *threads = new thrd_t[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]); + + delete param; + delete threads; + delete s; + + return 0; +} -- 2.34.1