From 04caaa74db8971f48e11cb71aa88bb3b56c0223c Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 27 Aug 2014 16:17:47 -0700 Subject: [PATCH] changes to ms-queue --- benchmark/ms-queue/main.c | 22 +++++++++++++----- benchmark/ms-queue/my_queue.c | 43 ++++++++++++++++++----------------- 2 files changed, 38 insertions(+), 27 deletions(-) diff --git a/benchmark/ms-queue/main.c b/benchmark/ms-queue/main.c index 4840014..d3bc9c2 100644 --- a/benchmark/ms-queue/main.c +++ b/benchmark/ms-queue/main.c @@ -23,23 +23,33 @@ int get_thread_num() return -1; } +bool succ1, succ2; + static void main_task(void *param) { + unsigned int val; int pid = *((int *)param); +/* + if (!pid) { + input[0] = 17; + succ1 = dequeue(queue, &input[0]); + } else { + input[1] = 37; + enqueue(queue, input[1]); + } +*/ if (!pid) { input[0] = 17; - //enqueue(queue, input[0]); enqueue(queue, input[0]); - //output[0] = dequeue(queue); + succ1 = dequeue(queue, &input[0]); } else { input[1] = 37; - //enqueue(queue, input[1]); - //output[1] = dequeue(queue); - //output[0] = dequeue(queue); - bool succ = dequeue(queue, &output[0]); + enqueue(queue, input[1]); + succ2 = dequeue(queue, &output[1]); } + } int user_main(int argc, char **argv) diff --git a/benchmark/ms-queue/my_queue.c b/benchmark/ms-queue/my_queue.c index 5078785..c70adac 100644 --- a/benchmark/ms-queue/my_queue.c +++ b/benchmark/ms-queue/my_queue.c @@ -22,10 +22,12 @@ 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 = load_32(&free_lists[t][i]); + unsigned int node = free_lists[t][i]; //unsigned int node = free_lists[t][i]; if (node) { - store_32(&free_lists[t][i], 0); + //store_32(&free_lists[t][i], 0); + free_lists[t][i] = 0; //free_lists[t][i] = 0; return node; } @@ -46,12 +48,14 @@ static void reclaim(unsigned int 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 = load_32(&free_lists[t][i]); + unsigned int idx = 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); + //store_32(&free_lists[t][i], node); + free_lists[t][i] = node; //free_lists[t][i] = node; return; } @@ -94,18 +98,18 @@ void enqueue(queue_t *q, unsigned int val) pointer tmp; node = new_node(); - store_32(&q->nodes[node].value, val); + //store_32(&q->nodes[node].value, val); + q->nodes[node].value = val; //q->nodes[node].value = val; tmp = atomic_load_explicit(&q->nodes[node].next, relaxed); set_ptr(&tmp, 0); // NULL atomic_store_explicit(&q->nodes[node].next, tmp, relaxed); while (!success) { - /**** detected UL ****/ + /**** detected UL (2 threads, 1 enqueue & 1 dequeue) ****/ tail = atomic_load_explicit(&q->tail, acquire); /****FIXME: miss ****/ next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, acquire); - //printf("miss1_enqueue\n"); if (tail == atomic_load_explicit(&q->tail, relaxed)) { /* Check for uninitialized 'next' */ @@ -113,8 +117,7 @@ void enqueue(queue_t *q, unsigned int val) if (get_ptr(next) == 0) { // == NULL pointer value = MAKE_POINTER(node, get_count(next) + 1); - /**** detected UL ****/ - // Second release can be just relaxed + /**** correctness error (1 dequeue & 1 enqueue) ****/ success = atomic_compare_exchange_strong_explicit(&q->nodes[get_ptr(tail)].next, &next, value, release, relaxed); /** @@ -126,12 +129,11 @@ void enqueue(queue_t *q, unsigned int val) } if (!success) { // This routine helps the other enqueue to update the tail - /**** detected UL ****/ + /**** detected UL (2 threads, 1 enqueue & 1 dequeue) ****/ unsigned int ptr = get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, acquire)); pointer value = MAKE_POINTER(ptr, get_count(tail) + 1); /****FIXME: miss ****/ - // Second release can be just relaxed bool succ = false; succ = atomic_compare_exchange_strong_explicit(&q->tail, &tail, value, release, relaxed); @@ -143,8 +145,7 @@ void enqueue(queue_t *q, unsigned int val) } } } - /**** dectected UL ****/ - // Second release can be just relaxed + /**** correctness error (1 dequeue & 1 enqueue) ****/ atomic_compare_exchange_strong_explicit(&q->tail, &tail, MAKE_POINTER(node, get_count(tail) + 1), @@ -165,12 +166,13 @@ bool dequeue(queue_t *q, unsigned int *retVal) pointer next; while (!success) { - /**** detected correctness error ****/ + /**** FIXME: miss ****/ head = atomic_load_explicit(&q->head, acquire); - // FIXME: This must be acquire otherwise we have a bug with 1 enqueue & + // This must be acquire otherwise we have a bug with 1 enqueue & // 1 dequeue - tail = atomic_load_explicit(&q->tail, relaxed); - /****FIXME: miss ****/ + /**** correctness error (1 dequeue & 1 enqueue) ****/ + tail = atomic_load_explicit(&q->tail, acquire); + /**** correctness error (1 dequeue & 1 enqueue) ****/ next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, acquire); //printf("miss3_dequeue\n"); if (atomic_load_explicit(&q->head, relaxed) == head) { @@ -189,7 +191,6 @@ bool dequeue(queue_t *q, unsigned int *retVal) return false; // NULL } /****FIXME: miss (not reached) ****/ - // Second release can be just relaxed bool succ = false; succ = atomic_compare_exchange_strong_explicit(&q->tail, &tail, @@ -201,10 +202,10 @@ bool dequeue(queue_t *q, unsigned int *retVal) //printf("miss4_dequeue\n"); thrd_yield(); } else { - *retVal = load_32(&q->nodes[get_ptr(next)].value); + //*retVal = load_32(&q->nodes[get_ptr(next)].value); + *retVal = q->nodes[get_ptr(next)].value; //value = q->nodes[get_ptr(next)].value; - /****FIXME: correctness error ****/ - // Seconde release can be just relaxed + /**** FIXME: miss (not reached) ****/ success = atomic_compare_exchange_strong_explicit(&q->head, &head, MAKE_POINTER(get_ptr(next), get_count(head) + 1), -- 2.34.1