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

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

Several prototype fixes for arm

  • Property mode set to 100644
File size: 3.3 KB
Line 
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,
12template<typename node_t>
13class mcs_queue {
14        node_t * volatile tail;
15
16public:
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
56template<typename node_t>
57class mpsc_queue : private mcs_queue<node_t> {
58        node_t * volatile head;
59public:
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};
Note: See TracBrowser for help on using the repository browser.