changes

[cdsspec-compiler.git] / benchmark / ms-queue / my_queue.c

diff --git a/benchmark/ms-queue/my_queue.c b/benchmark/ms-queue/my_queue.c
index 186745eaec079251e7e49ce57b9cfe68def3db1a..50787854561c46a787dfcd0a516b4596693d5591 100644 (file)
--- a/benchmark/ms-queue/my_queue.c
+++ b/benchmark/ms-queue/my_queue.c
@@ -10,7 +10,7 @@
 #define acquire memory_order_acquire
 
 #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 INITIAL_FREE 3 /* Each thread starts with INITIAL_FREE free nodes */
 
 #define POISON_IDX 0x666
 
@@ -31,7 +31,7 @@ static unsigned int new_node()
                }
        }
        /* free_list is empty? */
-       MODEL_ASSERT(0);
+       //MODEL_ASSERT(0);
        return 0;
 }
 
@@ -42,7 +42,7 @@ static void reclaim(unsigned int node)
        int t = get_thread_num();
 
        /* Don't reclaim NULL node */
-       MODEL_ASSERT(node);
+       //MODEL_ASSERT(node);
 
        for (i = 0; i < MAX_FREELIST; i++) {
                /* Should never race with our own thread here */
@@ -57,7 +57,7 @@ static void reclaim(unsigned int node)
                }
        }
        /* free list is full? */
-       MODEL_ASSERT(0);
+       //MODEL_ASSERT(0);
 }
 
 void init_queue(queue_t *q, int num_threads)
@@ -101,11 +101,11 @@ void enqueue(queue_t *q, unsigned int val)
        atomic_store_explicit(&q->nodes[node].next, tmp, relaxed);
 
        while (!success) {
-               /****FIXME: detected UL ****/
+               /**** detected UL ****/
                tail = atomic_load_explicit(&q->tail, acquire);
                /****FIXME: miss ****/
                next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, acquire);
-               printf("miss1_enqueue\n");
+               //printf("miss1_enqueue\n");
                if (tail == atomic_load_explicit(&q->tail, relaxed)) {
 
                        /* Check for uninitialized 'next' */
@@ -113,7 +113,7 @@ void enqueue(queue_t *q, unsigned int val)
 
                        if (get_ptr(next) == 0) { // == NULL
                                pointer value = MAKE_POINTER(node, get_count(next) + 1);
-                               /****FIXME: first release UL ****/
+                               /**** detected UL ****/
                                // Second release can be just relaxed
                                success = atomic_compare_exchange_strong_explicit(&q->nodes[get_ptr(tail)].next,
                                                &next, value, release, relaxed);
@@ -125,21 +125,26 @@ void enqueue(queue_t *q, unsigned int val)
                                */
                        }
                        if (!success) {
-                               /****FIXME: detected UL ****/
+                               // This routine helps the other enqueue to update the tail
+                               /**** detected UL ****/
                                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 ****/
-                               // Seconde release can be just relaxed
-                               atomic_compare_exchange_strong_explicit(&q->tail,
+                               // Second release can be just relaxed
+                               bool succ = false;
+                               succ = atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail, value, release, relaxed);
-                               printf("miss2_enqueue\n");
+                               if (succ) {
+                                       //printf("miss2_enqueue CAS succ\n");
+                               }
+                               //printf("miss2_enqueue\n");
                                thrd_yield();
                        }
                }
        }
-       /****FIXME: first UL ****/
-       // Seconde release can be just relaxed
+       /**** dectected UL ****/
+       // Second release can be just relaxed
        atomic_compare_exchange_strong_explicit(&q->tail,
                        &tail,
                        MAKE_POINTER(node, get_count(tail) + 1),
@@ -151,7 +156,7 @@ void enqueue(queue_t *q, unsigned int val)
        @Interface_define: Dequeue
        @End
 */
-unsigned int dequeue(queue_t *q)
+bool dequeue(queue_t *q, unsigned int *retVal)
 {
        unsigned int value;
        int success = 0;
@@ -160,17 +165,19 @@ unsigned int dequeue(queue_t *q)
        pointer next;
 
        while (!success) {
-               /****FIXME: detected correctness error ****/
+               /**** detected correctness error ****/
                head = atomic_load_explicit(&q->head, acquire);
+               // FIXME: This must be acquire otherwise we have a bug with 1 enqueue &
+               // 1 dequeue
                tail = atomic_load_explicit(&q->tail, relaxed);
                /****FIXME: miss ****/
                next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, acquire);
-               printf("miss3_dequeue\n");
+               //printf("miss3_dequeue\n");
                if (atomic_load_explicit(&q->head, relaxed) == head) {
                        if (get_ptr(head) == get_ptr(tail)) {
 
                                /* Check for uninitialized 'next' */
-                               MODEL_ASSERT(get_ptr(next) != POISON_IDX);
+                               //MODEL_ASSERT(get_ptr(next) != POISON_IDX);
 
                                if (get_ptr(next) == 0) { // NULL
                                        /**
@@ -179,18 +186,22 @@ unsigned int dequeue(queue_t *q)
                                                @Label: Dequeue_Empty_Point
                                                @End
                                        */
-                                       return 0; // NULL
+                                       return false; // NULL
                                }
                                /****FIXME: miss (not reached) ****/
-                               // Seconde release can be just relaxed
-                               atomic_compare_exchange_strong_explicit(&q->tail,
+                               // Second release can be just relaxed
+                               bool succ = false;
+                               succ = atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail,
                                                MAKE_POINTER(get_ptr(next), get_count(tail) + 1),
                                                release, relaxed);
-                               printf("miss4_dequeue\n");
+                               if (succ) {
+                                       //printf("miss4_dequeue CAS succ\n");
+                               }
+                               //printf("miss4_dequeue\n");
                                thrd_yield();
                        } else {
-                               value = load_32(&q->nodes[get_ptr(next)].value);
+                               *retVal = load_32(&q->nodes[get_ptr(next)].value);
                                //value = q->nodes[get_ptr(next)].value;
                                /****FIXME: correctness error ****/
                                // Seconde release can be just relaxed
@@ -210,5 +221,5 @@ unsigned int dequeue(queue_t *q)
                }
        }
        reclaim(get_ptr(head));
-       return value;
+       return true;
 }