From 8d33d370dc330e62ba3086d7a98c362e231a4307 Mon Sep 17 00:00:00 2001 From: Brian Demsky Date: Tue, 7 May 2013 18:28:31 -0700 Subject: [PATCH] bugfix for chase lev --- chase-lev-deque-bugfix/Makefile | 17 +++++++ chase-lev-deque-bugfix/deque.c | 85 +++++++++++++++++++++++++++++++++ chase-lev-deque-bugfix/deque.h | 22 +++++++++ chase-lev-deque-bugfix/main.c | 46 ++++++++++++++++++ 4 files changed, 170 insertions(+) create mode 100644 chase-lev-deque-bugfix/Makefile create mode 100644 chase-lev-deque-bugfix/deque.c create mode 100644 chase-lev-deque-bugfix/deque.h create mode 100644 chase-lev-deque-bugfix/main.c diff --git a/chase-lev-deque-bugfix/Makefile b/chase-lev-deque-bugfix/Makefile new file mode 100644 index 0000000..91ff999 --- /dev/null +++ b/chase-lev-deque-bugfix/Makefile @@ -0,0 +1,17 @@ +include ../benchmarks.mk + +TESTNAME = main + +HEADERS = deque.h +OBJECTS = main.o deque.o + +all: $(TESTNAME) + +$(TESTNAME): $(HEADERS) $(OBJECTS) + $(CC) -o $@ $(OBJECTS) $(CPPFLAGS) $(LDFLAGS) + +%.o: %.c + $(CC) -c -o $@ $< $(CPPFLAGS) + +clean: + rm -f $(TESTNAME) *.o diff --git a/chase-lev-deque-bugfix/deque.c b/chase-lev-deque-bugfix/deque.c new file mode 100644 index 0000000..6328446 --- /dev/null +++ b/chase-lev-deque-bugfix/deque.c @@ -0,0 +1,85 @@ +#include +#include +#include "deque.h" +#include +#include + +Deque * create() { + Deque * q = (Deque *) calloc(1, sizeof(Deque)); + Array * a = (Array *) calloc(1, sizeof(Array)+2*sizeof(atomic_int)); + atomic_store_explicit(&q->array, a, memory_order_relaxed); + atomic_store_explicit(&q->top, 0, memory_order_relaxed); + atomic_store_explicit(&q->bottom, 0, memory_order_relaxed); + atomic_store_explicit(&a->size, 2, memory_order_relaxed); + return q; +} + +int take(Deque *q) { + size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed) - 1; + Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed); + atomic_store_explicit(&q->bottom, b, memory_order_relaxed); + atomic_thread_fence(memory_order_seq_cst); + size_t t = atomic_load_explicit(&q->top, memory_order_relaxed); + int x; + if (t <= b) { + /* Non-empty queue. */ + x = atomic_load_explicit(&a->buffer[b % atomic_load_explicit(&a->size,memory_order_relaxed)], memory_order_relaxed); + if (t == b) { + /* Single last element in queue. */ + if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed)) + /* Failed race. */ + x = EMPTY; + atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); + } + } else { /* Empty queue. */ + x = EMPTY; + atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); + } + return x; +} + +void resize(Deque *q) { + Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed); + size_t size=atomic_load_explicit(&a->size, memory_order_relaxed); + size_t new_size=size << 1; + Array *new_a = (Array *) calloc(1, new_size * sizeof(atomic_int) + sizeof(Array)); + size_t top=atomic_load_explicit(&q->top, memory_order_relaxed); + size_t bottom=atomic_load_explicit(&q->bottom, memory_order_relaxed); + atomic_store_explicit(&new_a->size, new_size, memory_order_relaxed); + size_t i; + for(i=top; i < bottom; i++) { + atomic_store_explicit(&new_a->buffer[i % new_size], atomic_load_explicit(&a->buffer[i % size], memory_order_relaxed), memory_order_relaxed); + } + atomic_store_explicit(&q->array, new_a, memory_order_release); + printf("resize\n"); +} + +void push(Deque *q, int x) { + size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed); + size_t t = atomic_load_explicit(&q->top, memory_order_acquire); + Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed); + if (b - t > atomic_load_explicit(&a->size, memory_order_relaxed) - 1) /* Full queue. */ { + resize(q); + //Bug in paper...should have next line... + a = (Array *) atomic_load_explicit(&q->array, memory_order_relaxed); + } + atomic_store_explicit(&a->buffer[b % atomic_load_explicit(&a->size, memory_order_relaxed)], x, memory_order_relaxed); + atomic_thread_fence(memory_order_release); + atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); +} + +int steal(Deque *q) { + size_t t = atomic_load_explicit(&q->top, memory_order_acquire); + atomic_thread_fence(memory_order_seq_cst); + size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire); + int x = EMPTY; + if (t < b) { + /* Non-empty queue. */ + Array *a = (Array *) atomic_load_explicit(&q->array, memory_order_acquire); + x = atomic_load_explicit(&a->buffer[t % atomic_load_explicit(&a->size, memory_order_relaxed)], memory_order_relaxed); + if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed)) + /* Failed race. */ + return ABORT; + } + return x; +} diff --git a/chase-lev-deque-bugfix/deque.h b/chase-lev-deque-bugfix/deque.h new file mode 100644 index 0000000..bc670e7 --- /dev/null +++ b/chase-lev-deque-bugfix/deque.h @@ -0,0 +1,22 @@ +#ifndef DEQUE_H +#define DEQUE_H + +typedef struct { + atomic_size_t size; + atomic_int buffer[]; +} Array; + +typedef struct { + atomic_size_t top, bottom; + atomic_uintptr_t array; /* Atomic(Array *) */ +} Deque; + +Deque * create(); +int take(Deque *q); +void resize(Deque *q); +void push(Deque *q, int x); + +#define EMPTY 0xffffffff +#define ABORT 0xfffffffe + +#endif diff --git a/chase-lev-deque-bugfix/main.c b/chase-lev-deque-bugfix/main.c new file mode 100644 index 0000000..f2e8dca --- /dev/null +++ b/chase-lev-deque-bugfix/main.c @@ -0,0 +1,46 @@ +#include +#include +#include +#include +#include + +#include "model-assert.h" + +#include "deque.h" + +Deque *q; +int a; +int b; +int c; + +static void task(void * param) { + a=steal(q); +} + +int user_main(int argc, char **argv) +{ + thrd_t t; + q=create(); + thrd_create(&t, task, 0); + push(q, 1); + push(q, 2); + push(q, 4); + b=take(q); + c=take(q); + thrd_join(t); + + bool correct=true; + if (a!=1 && a!=2 && a!=4 && a!= EMPTY) + correct=false; + if (b!=1 && b!=2 && b!=4 && b!= EMPTY) + correct=false; + if (c!=1 && c!=2 && c!=4 && a!= EMPTY) + correct=false; + if (a!=EMPTY && b!=EMPTY && c!=EMPTY && (a+b+c)!=7) + correct=false; + if (!correct) + printf("a=%d b=%d c=%d\n",a,b,c); + MODEL_ASSERT(correct); + + return 0; +} -- 2.34.1