source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/links2.hpp @ a1b9bc3

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since a1b9bc3 was a1b9bc3, checked in by Thierry Delisle <tdelisle@…>, 7 months ago

Many small changes to prototype code

  • Property mode set to 100644
File size: 3.3 KB
Line 
1#pragma once
2
3#include <assert.h>
4
5//------------------------------------------------------------
6// Queue based on the MCS lock
7// It is a Multi-Producer/Single-Consumer queue threads pushing
8// elements must hold on to the elements they push
9// Not appropriate for an async message queue for example,
10template<typename node_t>
11class mcs_queue {
12        node_t * volatile tail;
13
14public:
15        mcs_queue(): tail(nullptr) {}
16
17        inline bool empty() const { return !tail; }
18
19        node_t * push( node_t * elem ) {
20                /* paranoid */ assert(!elem->_links.next);
21                // Race to add to the tail
22                node_t * prev = __atomic_exchange_n(&tail, elem, __ATOMIC_SEQ_CST);
23                // If we aren't the first, we need to tell the person before us
24                // No need to
25                if (prev) prev->_links.next = elem;
26                return prev;
27        }
28
29        // Advances the head of the list, dropping the element given.
30        // Passing an element that is not the head is undefined behavior
31        // NOT Multi-Thread Safe, concurrent pushes are safe
32        node_t * advance(node_t * elem) {
33                node_t * expected = elem;
34                // Check if this is already the last item
35                if (__atomic_compare_exchange_n(&tail, &expected, nullptr, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return nullptr;
36
37                // If not wait for next item to show-up, filled by push
38                while (!elem->_links.next) asm volatile("pause");
39
40                // we need to return if the next link was empty
41                node_t * ret = elem->_links.next;
42
43                // invalidate link to reset to initial state
44                elem->_links.next = nullptr;
45                return ret;
46        }
47};
48
49//------------------------------------------------------------
50// Queue based on the MCS lock
51// Extension of the above lock which supports 'blind' pops.
52// i.e., popping a value from the head without knowing what the head is
53// has no extra guarantees beyond the mcs_queue
54template<typename node_t>
55class mpsc_queue : private mcs_queue<node_t> {
56        node_t * volatile head;
57public:
58        mpsc_queue(): mcs_queue<node_t>(), head(nullptr) {}
59
60        inline bool empty() const { return mcs_queue<node_t>::empty(); }
61
62        // Added a new element to the queue
63        // Multi-Thread Safe, Lock-Free
64        inline node_t * push(node_t * elem) {
65                node_t * prev = mcs_queue<node_t>::push(elem);
66                if (!prev) head = elem;
67                return prev;
68        }
69
70        // Pop an element from the queue
71        // return the element that was removed
72        // next is set to the new head of the queue
73        // NOT Multi-Thread Safe
74        inline node_t * pop(node_t *& next) {
75                node_t * elem = head;
76                // If head is empty just return
77                if (!elem) return nullptr;
78
79                // If there is already someone in the list, then it's easy
80                if (elem->_links.next) {
81                        head = next = elem->_links.next;
82                        // force memory sync
83                        __atomic_thread_fence(__ATOMIC_SEQ_CST);
84
85                        // invalidate link to reset to initial state
86                        elem->_links.next = nullptr;
87                }
88                // Otherwise, there might be a race where it only looks but someone is enqueuing
89                else {
90                        // null out head here, because we linearize with push
91                        // at the CAS in advance and therefore can write to head
92                        // after that point, it could overwrite the write in push
93                        head = nullptr;
94                        next = mcs_queue<node_t>::advance(elem);
95
96                        // Only write to the head if there is a next element
97                        // it is the only way we can guarantee we are not overwriting
98                        // a write made in push
99                        if (next) head = next;
100                }
101
102                // return removed element
103                return elem;
104        }
105
106        // Same as previous function
107        inline node_t * pop() {
108                node_t * _ = nullptr;
109                return pop(_);
110        }
111};
Note: See TracBrowser for help on using the repository browser.