X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=ms-queue%2Fmy_queue.c;h=6c0ccd4bea4c0f49b2a1fdd4f9b24d992dc0f749;hb=430eca5dcc20bfc89edac5c134d1c8af7a9614bc;hp=18ce29f7d346f9be68747749e236e23edf69c796;hpb=d9df2d0a3a5bbd40771568c659d60c19e197af25;p=model-checker-benchmarks.git

diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c
index 18ce29f..6c0ccd4 100644
--- a/ms-queue/my_queue.c
+++ b/ms-queue/my_queue.c
@@ -12,6 +12,8 @@
 #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 */
@@ -58,12 +60,13 @@ void init_queue(queue_t *q, int num_threads)
 {
 	int i, j;
 
-	/* Initialize each thread's free list with INITIAL_FREE NULL "pointers" */
+	/* 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(0, 0));
+			atomic_init(&q->nodes[free_lists[i][j]].next, MAKE_POINTER(POISON_IDX, 0));
 		}
 	}
 
@@ -91,6 +94,10 @@ void enqueue(queue_t *q, unsigned int val)
 		tail = atomic_load_explicit(&q->tail, acquire);
 		next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, acquire);
 		if (tail == atomic_load_explicit(&q->tail, 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,
@@ -113,9 +120,8 @@ void enqueue(queue_t *q, unsigned int val)
 			release, release);
 }
 
-unsigned int dequeue(queue_t *q)
+bool dequeue(queue_t *q, unsigned int *retVal)
 {
-	unsigned int value;
 	int success = 0;
 	pointer head;
 	pointer tail;
@@ -127,8 +133,12 @@ unsigned int dequeue(queue_t *q)
 		next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, acquire);
 		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);
+
 				if (get_ptr(next) == 0) { // NULL
-					return 0; // NULL
+					return false; // NULL
 				}
 				atomic_compare_exchange_strong_explicit(&q->tail,
 						&tail,
@@ -136,7 +146,7 @@ unsigned int dequeue(queue_t *q)
 						release, release);
 				thrd_yield();
 			} else {
-				value = load_32(&q->nodes[get_ptr(next)].value);
+				*retVal = load_32(&q->nodes[get_ptr(next)].value);
 				success = atomic_compare_exchange_strong_explicit(&q->head,
 						&head,
 						MAKE_POINTER(get_ptr(next), get_count(head) + 1),
@@ -147,5 +157,5 @@ unsigned int dequeue(queue_t *q)
 		}
 	}
 	reclaim(get_ptr(head));
-	return value;
+	return true;
 }