From 1438eb7c0715e53611a717e593bfa3fe1bd30588 Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 11 Feb 2015 21:23:08 -0800 Subject: [PATCH] changes --- ms-queue/Makefile | 27 +++-- ms-queue/{my_queue.c => queue.c} | 2 +- ms-queue/{my_queue.h => queue.h} | 0 ms-queue/queue_wildcard.c | 169 +++++++++++++++++++++++++++++++ ms-queue/{main.c => testcase1.c} | 2 +- 5 files changed, 189 insertions(+), 11 deletions(-) rename ms-queue/{my_queue.c => queue.c} (99%) rename ms-queue/{my_queue.h => queue.h} (100%) create mode 100644 ms-queue/queue_wildcard.c rename ms-queue/{main.c => testcase1.c} (98%) diff --git a/ms-queue/Makefile b/ms-queue/Makefile index da3a0e4..34881f4 100644 --- a/ms-queue/Makefile +++ b/ms-queue/Makefile @@ -1,17 +1,26 @@ include ../benchmarks.mk -TESTNAME = main +BENCH := queue -HEADERS = my_queue.h -OBJECTS = main.o my_queue.o +NORMAL_TESTS := testcase1 -all: $(TESTNAME) +WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS)) -$(TESTNAME): $(HEADERS) $(OBJECTS) - $(CC) -o $@ $(OBJECTS) $(CFLAGS) $(LDFLAGS) +TESTS := $(NORMAL_TESTS) $(WILDCARD_TESTS) -%.o: %.c - $(CC) -c -o $@ $< $(CFLAGS) +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) + +$(NORMAL_TESTS): % : %.c $(BENCH).o + $(CC) -o $@ $^ $(CFLAGS) $(LDFLAGS) clean: - rm -f $(TESTNAME) *.o + rm -f *.o *.d $(TESTS) diff --git a/ms-queue/my_queue.c b/ms-queue/queue.c similarity index 99% rename from ms-queue/my_queue.c rename to ms-queue/queue.c index 6c0ccd4..0a5f3bd 100644 --- a/ms-queue/my_queue.c +++ b/ms-queue/queue.c @@ -3,7 +3,7 @@ #include "librace.h" #include "model-assert.h" -#include "my_queue.h" +#include "queue.h" #define relaxed memory_order_relaxed #define release memory_order_release diff --git a/ms-queue/my_queue.h b/ms-queue/queue.h similarity index 100% rename from ms-queue/my_queue.h rename to ms-queue/queue.h diff --git a/ms-queue/queue_wildcard.c b/ms-queue/queue_wildcard.c new file mode 100644 index 0000000..df1702a --- /dev/null +++ b/ms-queue/queue_wildcard.c @@ -0,0 +1,169 @@ +#include +#include +#include "librace.h" +#include "model-assert.h" + +#include "queue.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 */ + +#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_queue(queue_t *q, 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] = 2 + i * MAX_FREELIST + j; + atomic_init(&q->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0)); + } + } + + /* initialize queue */ + atomic_init(&q->head, MAKE_POINTER(1, 0)); + atomic_init(&q->tail, MAKE_POINTER(1, 0)); + atomic_init(&q->nodes[1].next, MAKE_POINTER(0, 0)); +} + +void enqueue(queue_t *q, unsigned int val) +{ + int success = 0; + unsigned int node; + pointer tail; + pointer next; + pointer tmp; + + node = new_node(); + //store_32(&q->nodes[node].value, val); + q->nodes[node].value = val; + tmp = atomic_load_explicit(&q->nodes[node].next, wildcard(1)); // relaxed + set_ptr(&tmp, 0); // NULL + atomic_store_explicit(&q->nodes[node].next, tmp, wildcard(2)); // relaxed + + while (!success) { + tail = atomic_load_explicit(&q->tail, wildcard(3)); // acquire + // FIXME: SCFence makes this relaxed + next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, wildcard(4)); //acquire + if (tail == atomic_load_explicit(&q->tail, wildcard(5))) { // relaxed + + /* Check for uninitialized 'next' */ + //MODEL_ASSERT(get_ptr(next) != POISON_IDX); + + if (get_ptr(next) == 0) { // == NULL + pointer value = MAKE_POINTER(node, get_count(next) + 1); + success = atomic_compare_exchange_strong_explicit(&q->nodes[get_ptr(tail)].next, + &next, value, wildcard(6), wildcard(7)); // release & relaxed + } + if (!success) { + unsigned int ptr = + get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, wildcard(8))); // acquire + pointer value = MAKE_POINTER(ptr, + get_count(tail) + 1); + atomic_compare_exchange_strong_explicit(&q->tail, + &tail, value, + wildcard(9), wildcard(10)); // release & relaxed + thrd_yield(); + } + } + } + atomic_compare_exchange_strong_explicit(&q->tail, + &tail, + MAKE_POINTER(node, get_count(tail) + 1), + wildcard(11), wildcard(12)); // release & relaxed +} + +bool dequeue(queue_t *q, unsigned int *retVal) +{ + unsigned int value; + int success = 0; + pointer head; + pointer tail; + pointer next; + + while (!success) { + head = atomic_load_explicit(&q->head, wildcard(13)); // acquire + // FIXME: SCFence makes this acquire + tail = atomic_load_explicit(&q->tail, wildcard(14)); // relaxed + next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, wildcard(15)); // acquire + if (atomic_load_explicit(&q->head, wildcard(16)) == head) { // relaxed + if (get_ptr(head) == get_ptr(tail)) { + + /* Check for uninitialized 'next' */ + //MODEL_ASSERT(get_ptr(next) != POISON_IDX); + + if (get_ptr(next) == 0) { // NULL + return false; // NULL + } + atomic_compare_exchange_strong_explicit(&q->tail, + &tail, + MAKE_POINTER(get_ptr(next), get_count(tail) + 1), + wildcard(17), wildcard(18)); // release & relaxed + thrd_yield(); + } else { + //value = load_32(&q->nodes[get_ptr(next)].value); + value = q->nodes[get_ptr(next)].value; + // FIXME: SCFence makes this relaxed + success = atomic_compare_exchange_strong_explicit(&q->head, + &head, MAKE_POINTER(get_ptr(next), get_count(head) + 1), + wildcard(19), wildcard(20)); // release & relaxed + if (!success) + thrd_yield(); + } + } + } + reclaim(get_ptr(head)); + *retVal = value; + return true; +} diff --git a/ms-queue/main.c b/ms-queue/testcase1.c similarity index 98% rename from ms-queue/main.c rename to ms-queue/testcase1.c index e464138..9bf12fb 100644 --- a/ms-queue/main.c +++ b/ms-queue/testcase1.c @@ -2,7 +2,7 @@ #include #include -#include "my_queue.h" +#include "queue.h" #include "model-assert.h" static int procs = 2; -- 2.34.1