From 789a02caa782b613d3c381710127f9e71fe811c4 Mon Sep 17 00:00:00 2001
From: Peizhao Ou <peizhaoo@uci.edu>
Date: Sat, 22 Mar 2014 23:48:54 -0700
Subject: [PATCH] fix ms-queue spec

---
 benchmark/mcs-lock/mcs-lock.h |  6 +++---
 benchmark/ms-queue/main.c     |  1 +
 benchmark/ms-queue/my_queue.c | 17 +++++++++++++----
 benchmark/ms-queue/my_queue.h | 11 +++++++++--
 4 files changed, 26 insertions(+), 9 deletions(-)

diff --git a/benchmark/mcs-lock/mcs-lock.h b/benchmark/mcs-lock/mcs-lock.h
index a27b37e..4714567 100644
--- a/benchmark/mcs-lock/mcs-lock.h
+++ b/benchmark/mcs-lock/mcs-lock.h
@@ -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;
diff --git a/benchmark/ms-queue/main.c b/benchmark/ms-queue/main.c
index 200ae45..c8d160b 100644
--- a/benchmark/ms-queue/main.c
+++ b/benchmark/ms-queue/main.c
@@ -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;
diff --git a/benchmark/ms-queue/my_queue.c b/benchmark/ms-queue/my_queue.c
index 186745e..2b90fe5 100644
--- 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
 
@@ -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 {
diff --git a/benchmark/ms-queue/my_queue.h b/benchmark/ms-queue/my_queue.h
index 0d83392..bc4c345 100644
--- a/benchmark/ms-queue/my_queue.h
+++ b/benchmark/ms-queue/my_queue.h
@@ -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
-- 
2.34.1