X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=ms-queue%2Fqueue_wildcard.c;h=802e6f622bf889313d9252aecc137b9fc0df6e87;hb=b684f62b7411fea476b2e1f6a8bbf920ac4c7216;hp=df1702aa375cd38581ea499e74cb3c2583f8531a;hpb=1438eb7c0715e53611a717e593bfa3fe1bd30588;p=model-checker-benchmarks.git

diff --git a/ms-queue/queue_wildcard.c b/ms-queue/queue_wildcard.c
index df1702a..802e6f6 100644
--- a/ms-queue/queue_wildcard.c
+++ b/ms-queue/queue_wildcard.c
@@ -32,6 +32,12 @@ static unsigned int new_node()
 	return 0;
 }
 
+/* Simulate the fact that when a node got recycled, it will get assigned to the
+ * same queue or for other usage */
+void simulateRecycledNodeUpdate(queue_t *q, unsigned int node) {
+	atomic_store_explicit(&q->nodes[node].next, -1, memory_order_release);
+}
+
 /* Place this node index back on this thread's free list */
 static void reclaim(unsigned int node)
 {
@@ -77,7 +83,7 @@ void init_queue(queue_t *q, int num_threads)
 	atomic_init(&q->nodes[1].next, MAKE_POINTER(0, 0));
 }
 
-void enqueue(queue_t *q, unsigned int val)
+void enqueue(queue_t *q, unsigned int val, bool yield)
 {
 	int success = 0;
 	unsigned int node;
@@ -94,7 +100,9 @@ void enqueue(queue_t *q, unsigned int val)
 
 	while (!success) {
 		tail = atomic_load_explicit(&q->tail, wildcard(3)); // acquire
-		// FIXME: SCFence makes this relaxed 
+		// FIXME: SCFence makes this relaxed
+		if (yield)
+			thrd_yield();
 		next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, wildcard(4)); //acquire
 		if (tail == atomic_load_explicit(&q->tail, wildcard(5))) { // relaxed
 
@@ -108,7 +116,7 @@ void enqueue(queue_t *q, unsigned int val)
 			}
 			if (!success) {
 				unsigned int ptr =
-				get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, wildcard(8))); // acquire
+					get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, wildcard(8))); // acquire
 				pointer value = MAKE_POINTER(ptr,
 						get_count(tail) + 1);
 				atomic_compare_exchange_strong_explicit(&q->tail,
@@ -124,7 +132,7 @@ void enqueue(queue_t *q, unsigned int val)
 			wildcard(11), wildcard(12)); // release & relaxed
 }
 
-bool dequeue(queue_t *q, unsigned int *retVal)
+bool dequeue(queue_t *q, unsigned int *retVal, unsigned int *reclaimNode)
 {
 	unsigned int value;
 	int success = 0;
@@ -134,7 +142,7 @@ bool dequeue(queue_t *q, unsigned int *retVal)
 
 	while (!success) {
 		head = atomic_load_explicit(&q->head, wildcard(13)); // acquire
-		// FIXME: SCFence makes this acquire
+		// SCFence makes this acquire, and we actually need an acquire here!!!
 		tail = atomic_load_explicit(&q->tail, wildcard(14)); // relaxed 
 		next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, wildcard(15)); // acquire
 		if (atomic_load_explicit(&q->head, wildcard(16)) == head) { // relaxed
@@ -154,7 +162,6 @@ bool dequeue(queue_t *q, unsigned int *retVal)
 			} else {
 				//value = load_32(&q->nodes[get_ptr(next)].value);
 				value = q->nodes[get_ptr(next)].value;
-				// FIXME: SCFence makes this relaxed 
 				success = atomic_compare_exchange_strong_explicit(&q->head,
 						&head, MAKE_POINTER(get_ptr(next), get_count(head) + 1),
 						wildcard(19), wildcard(20)); // release & relaxed
@@ -163,6 +170,8 @@ bool dequeue(queue_t *q, unsigned int *retVal)
 			}
 		}
 	}
+
+	reclaimNode = get_ptr(head);
 	reclaim(get_ptr(head));
 	*retVal = value;
 	return true;