ms-queue: revert Brian D. changes

On second (or third or fourth) thought, these changes were ill-advised.
We will make a different set of tweaks shortly.

This reverts commits 647601d3f341bb2a2a79534b3d044c039695839d and
fad3891f3158a4285984bb60415c1e4ebc2b767b.

diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c
index dfdf819574e49bf4914f0b5b819390bf3236c1eb..d65840797b34e88402d78fe1b4b944533a2873dc 100644 (file)
--- a/ms-queue/my_queue.c
+++ b/ms-queue/my_queue.c
@@ -61,7 +61,6 @@ void enqueue(queue_t *q, unsigned int val)
        pointer next;
        pointer tmp;
 
-       /* Get a fresh node, set its value field, then set it's next reference to null */
        node = new_node();
        store_32(&q->nodes[node].value, val);
        tmp = atomic_load_explicit(&q->nodes[node].next, relaxed);
@@ -69,30 +68,29 @@ void enqueue(queue_t *q, unsigned int val)
        atomic_store_explicit(&q->nodes[node].next, tmp, relaxed);
 
        while (!success) {
-               //tail isn't actually synchronization point
-               tail = atomic_load_explicit(&q->tail, relaxed);
-               //acquire reference...
-               next = atomic_load_explicit(&q->nodes[get_ptr(tail)].next, memory_order_seq_cst);
-               if (tail == atomic_load_explicit(&q->tail, memory_order_seq_cst)) {
+               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)) {
                        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,
-                                               &next, value, memory_order_seq_cst, memory_order_seq_cst);
+                                               &next, value, memory_order_acq_rel, memory_order_acq_rel);
                        }
                        if (!success) {
-                               unsigned int ptr = get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, memory_order_relaxed));
+                               unsigned int ptr = get_ptr(atomic_load_explicit(&q->nodes[get_ptr(tail)].next, memory_order_seq_cst));
                                pointer value = MAKE_POINTER(ptr,
                                                get_count(tail) + 1);
                                atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail, value,
-                                               memory_order_seq_cst, memory_order_seq_cst);
+                                               memory_order_acq_rel, memory_order_acq_rel);
+                               thrd_yield();
                        }
                }
        }
        atomic_compare_exchange_strong_explicit(&q->tail,
                        &tail,
                        MAKE_POINTER(node, get_count(tail) + 1),
-                       memory_order_seq_cst, memory_order_seq_cst);
+                       memory_order_acq_rel, memory_order_acq_rel);
 }
 
 unsigned int dequeue(queue_t *q)
@@ -104,10 +102,10 @@ unsigned int dequeue(queue_t *q)
        pointer next;
 
        while (!success) {
-               head = atomic_load_explicit(&q->head, memory_order_seq_cst);
-               tail = atomic_load_explicit(&q->tail, memory_order_seq_cst);
-               next = atomic_load_explicit(&q->nodes[get_ptr(head)].next, memory_order_seq_cst);
-               if (atomic_load_explicit(&q->head, memory_order_seq_cst) == head) {
+               head = atomic_load_explicit(&q->head, acquire);
+               tail = atomic_load_explicit(&q->tail, acquire);
+               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)) {
                                if (get_ptr(next) == 0) { // NULL
                                        return 0; // NULL
@@ -115,13 +113,16 @@ unsigned int dequeue(queue_t *q)
                                atomic_compare_exchange_strong_explicit(&q->tail,
                                                &tail,
                                                MAKE_POINTER(get_ptr(next), get_count(tail) + 1),
-                                               memory_order_seq_cst, memory_order_seq_cst);
+                                               memory_order_acq_rel, memory_order_acq_rel);
+                               thrd_yield();
                        } else {
                                value = 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),
-                                               memory_order_seq_cst, memory_order_seq_cst);
+                                               memory_order_acq_rel, memory_order_acq_rel);
+                               if (!success)
+                                       thrd_yield();
                        }
                }
        }