fix ms-queue spec
authorPeizhao Ou <peizhaoo@uci.edu>
Sun, 23 Mar 2014 06:48:54 +0000 (23:48 -0700)
committerPeizhao Ou <peizhaoo@uci.edu>
Sun, 23 Mar 2014 06:48:54 +0000 (23:48 -0700)
benchmark/mcs-lock/mcs-lock.h
benchmark/ms-queue/main.c
benchmark/ms-queue/my_queue.c
benchmark/ms-queue/my_queue.h

index a27b37e..4714567 100644 (file)
@@ -94,7 +94,7 @@ public:
                        // unlock of pred can see me in the tail before I fill next
 
                        // publish me to previous lock-holder :
-                       // FIXME: detection miss  
+                       // FIXME: detection miss, don't think it's necessary  
                        pred->next.store(me, std::mo_release );
 
                        // (*2) pred not touched any more       
@@ -132,7 +132,7 @@ public:
        void unlock(guard * I) {
                mcs_node * me = &(I->m_node);
 
-               // FIXME: detection miss  
+               // FIXME: detection miss, don't think it's necessary
                mcs_node * next = me->next.load(std::mo_acquire);
                if ( next == NULL )
                {
@@ -155,7 +155,7 @@ public:
                        // (*1) catch the race :
                        rl::linear_backoff bo;
                        for(;;) {
-                               // FIXME: detection miss  
+                               // FIXME: detection miss, don't think it's necessary
                                next = me->next.load(std::mo_acquire);
                                if ( next != NULL )
                                        break;
index 200ae45..c8d160b 100644 (file)
@@ -31,6 +31,7 @@ static void main_task(void *param)
        if (!pid) {
                input[0] = 17;
                enqueue(queue, input[0]);
+               enqueue(queue, input[0]);
                output[0] = dequeue(queue);
        } else {
                input[1] = 37;
index 186745e..2b90fe5 100644 (file)
@@ -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
 
@@ -125,21 +125,26 @@ void enqueue(queue_t *q, unsigned int val)
                                */
                        }
                        if (!success) {
+                               // This routine helps the other enqueue to update the tail
                                /****FIXME: 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,
+                               bool succ = false;
+                               succ = atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail, value, release, relaxed);
+                               if (succ) {
+                                       printf("miss2_enqueue CAS succ\n");
+                               }
                                printf("miss2_enqueue\n");
                                thrd_yield();
                        }
                }
        }
        /****FIXME: first UL ****/
-       // Seconde release can be just relaxed
+       // Second release can be just relaxed
        atomic_compare_exchange_strong_explicit(&q->tail,
                        &tail,
                        MAKE_POINTER(node, get_count(tail) + 1),
@@ -183,10 +188,14 @@ unsigned int dequeue(queue_t *q)
                                }
                                /****FIXME: miss (not reached) ****/
                                // Seconde release can be just relaxed
-                               atomic_compare_exchange_strong_explicit(&q->tail,
+                               bool succ = false;
+                               succ = atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail,
                                                MAKE_POINTER(get_ptr(next), get_count(tail) + 1),
                                                release, relaxed);
+                               if (succ) {
+                                       printf("miss4_dequeue CAS succ\n");
+                               }
                                printf("miss4_dequeue\n");
                                thrd_yield();
                        } else {
index 0d83392..bc4c345 100644 (file)
@@ -67,6 +67,8 @@ void init_queue(queue_t *q, int num_threads);
                        }
                @DefineFunc:
                        call_id_t get_id(void *wrapper) {
+                               if (wrapper == NULL)
+                                       return 0;
                                return ((tag_elem_t*) wrapper)->id;
                        }
                @DefineFunc:
@@ -103,8 +105,13 @@ void enqueue(queue_t *q, unsigned int val);
        @Commit_point_set: Dequeue_Success_Point | Dequeue_Empty_Point
        @ID: get_id(front(__queue))
        @Action:
-               unsigned int _Old_Val = get_data(front(__queue));
-               pop_front(__queue);
+               unsigned int _Old_Val = 0;
+               if (size(__queue) > 0) {
+                       _Old_Val = get_data(front(__queue));
+                       pop_front(__queue);
+               } else {
+                       _Old_Val = 0;
+               }
        @Post_check:
                _Old_Val == __RET__
        @End