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