source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp@ b2a37b0

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr pthread-emulation qualifiedEnum stuck-waitfor-destruct
Last change on this file since b2a37b0 was b2a37b0, checked in by Thierry Delisle <tdelisle@…>, 6 years ago

Initial drafts in C++ of the CFA scheduler
  • Property mode set to 100644
File size: 6.7 KB
Line 
1#pragma once
2
3#include <iostream>
4#include <memory>
5#include <mutex>
6#include <type_traits>
7
8#include "assert.hpp"
9#include "utils.hpp"
10
11using namespace std;
12
13extern bool enable_stats;
14
15
16struct pick_stat {
17 size_t attempt = 0;
18 size_t success = 0;
19};
20
21extern __attribute__((aligned(64))) thread_local pick_stat local_pick;
22
23template<typename node_t>
24struct _LinksFields_t {
25 node_t * prev = nullptr;
26 node_t * next = nullptr;
27 unsigned long long ts = 0;
28};
29
30struct spinlock_t {
31 std::atomic_bool ll = { false };
32
33 inline void lock() {
34 while( __builtin_expect(ll.exchange(true),false) ) {
35 while(ll.load(std::memory_order_relaxed))
36 asm volatile("pause");
37 }
38 }
39
40 inline void unlock() {
41 ll.store(false, std::memory_order_release);
42 }
43};
44
45template<typename node_t>
46class relaxed_list {
47 static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
48
49
50public:
51 relaxed_list(unsigned numLists)
52 : numLists(numLists)
53 , lists(new intrusive_queue_t[numLists])
54 , numNonEmpty(0)
55 {}
56
57 void push(node_t * node) {
58 int i = rng_g.next() % numLists;
59 lists[i].push(node, numNonEmpty);
60 }
61
62 node_t * pop() {
63 int i = pickRandomly(-1);
64 int j = pickRandomly(i);
65
66 if(i == -1) {
67 return nullptr;
68 }
69
70 auto guard = lock(i, j);
71 auto & list = best(i, j);
72 return list.pop(numNonEmpty);
73 }
74
75 node_t * pop2() {
76 int i = pickRandomly(-1);
77 int j = pickRandomly(i);
78
79 if(i == -1) {
80 return nullptr;
81 }
82
83 auto & list = best2(i, j);
84 return list.pop2(numNonEmpty);
85 }
86
87private:
88
89 class intrusive_queue_t {
90 public:
91 typedef spinlock_t lock_t;
92
93 friend class relaxed_list<node_t>;
94
95 private:
96 struct sentinel_t {
97 _LinksFields_t<node_t> _links;
98 };
99
100 struct stat {
101 size_t push = 0;
102 size_t pop = 0;
103 };
104
105 __attribute__((aligned(64))) lock_t lock;
106 __attribute__((aligned(64))) bool empty;
107 stat s;
108 sentinel_t before;
109 sentinel_t after;
110
111 static constexpr auto fields_offset = offsetof( node_t, _links );
112 public:
113 intrusive_queue_t()
114 : empty(true)
115 , before{{ nullptr, tail() }}
116 , after {{ head(), nullptr }}
117 {
118 assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
119 assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
120 assert(head()->_links.prev == nullptr);
121 assert(head()->_links.next == tail() );
122 assert(tail()->_links.next == nullptr);
123 assert(tail()->_links.prev == head() );
124 }
125
126 ~intrusive_queue_t() {
127 std::cout << " Push: " << s.push << "\tPop: " << s.pop << "\t(this: " << this << ")" << std::endl;
128 }
129
130 node_t * head() const {
131 return reinterpret_cast<node_t *>(
132 reinterpret_cast<uintptr_t>( &before ) - fields_offset
133 );
134 }
135
136 node_t * tail() const {
137 return reinterpret_cast<node_t *>(
138 reinterpret_cast<uintptr_t>( &after ) - fields_offset
139 );
140 }
141
142 void push(node_t * node, volatile int & nonEmpty) {
143 node_t * tail = this->tail();
144 std::lock_guard<lock_t> guard(lock);
145 node->_links.ts = rdtscl();
146
147 node_t * prev = tail->_links.prev;
148 // assertf(node->_links.ts >= prev->_links.ts,
149 // "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
150 node->_links.next = tail;
151 node->_links.prev = prev;
152 prev->_links.next = node;
153 tail->_links.prev = node;
154 if(empty) {
155 __atomic_fetch_add(&nonEmpty, 1, __ATOMIC_SEQ_CST);
156 empty = false;
157 }
158 if(enable_stats) s.push++;
159 }
160
161 node_t * pop(volatile int & nonEmpty) {
162 node_t * head = this->head();
163 node_t * tail = this->tail();
164
165 node_t * node = head->_links.next;
166 node_t * next = node->_links.next;
167 if(node == tail) return nullptr;
168
169 head->_links.next = next;
170 next->_links.prev = head;
171
172 if(next == tail) {
173 empty = true;
174 __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
175 }
176 if(enable_stats) s.pop++;
177 return node;
178 }
179
180 node_t * pop2(volatile int & nonEmpty) {
181 node_t * head = this->head();
182 node_t * tail = this->tail();
183
184 std::lock_guard<lock_t> guard(lock);
185 node_t * node = head->_links.next;
186 node_t * next = node->_links.next;
187 if(node == tail) return nullptr;
188
189 head->_links.next = next;
190 next->_links.prev = head;
191
192 if(next == tail) {
193 empty = true;
194 __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
195 }
196 if(enable_stats) s.pop++;
197 return node;
198 }
199
200 static intrusive_queue_t & best(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
201 bool lhs_empty = lhs.empty;
202 bool rhs_empty = rhs.empty;
203
204 if(lhs_empty && rhs_empty) return lhs;
205 if(!lhs_empty && rhs_empty) return lhs;
206 if(lhs_empty && !rhs_empty) return rhs;
207 node_t * lhs_head = lhs.head()->_links.next;
208 node_t * rhs_head = rhs.head()->_links.next;
209
210 assert(lhs_head != lhs.tail());
211 assert(rhs_head != rhs.tail());
212
213 if(lhs_head->_links.ts < lhs_head->_links.ts) {
214 return lhs;
215 } else {
216 return rhs;
217 }
218 }
219
220 static intrusive_queue_t & best2(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
221 node_t * lhs_head = lhs.head()->_links.next;
222 node_t * rhs_head = rhs.head()->_links.next;
223
224 bool lhs_empty = lhs_head != lhs.tail();
225 bool rhs_empty = rhs_head != rhs.tail();
226 if(lhs_empty && rhs_empty) return lhs;
227 if(!lhs_empty && rhs_empty) return lhs;
228 if(lhs_empty && !rhs_empty) return rhs;
229
230 if(lhs_head->_links.ts < lhs_head->_links.ts) {
231 return lhs;
232 } else {
233 return rhs;
234 }
235 }
236 };
237
238
239private:
240
241 static thread_local Random rng_g;
242 __attribute__((aligned(64))) const unsigned numLists;
243 std::unique_ptr<intrusive_queue_t []> lists;
244 __attribute__((aligned(64))) volatile int numNonEmpty; // number of non-empty lists
245
246
247private:
248
249
250
251private:
252 int pickRandomly(const int avoid) {
253 int j;
254 do {
255 local_pick.attempt++;
256 j = rng_g.next() % numLists;
257 if (numNonEmpty < 1 + (avoid != -1)) return -1;
258 } while (j == avoid || lists[j].empty);
259 local_pick.success++;
260 return j;
261 }
262
263private:
264
265 struct queue_guard {
266 intrusive_queue_t * lists;
267 int i, j;
268
269 queue_guard(intrusive_queue_t * lists, int i, int j)
270 : lists(lists), i(i), j(j)
271 {
272 if(i >= 0) lists[i].lock.lock();
273 if(j >= 0) lists[j].lock.lock();
274 }
275
276 queue_guard(const queue_guard &) = delete;
277 queue_guard(queue_guard &&) = default;
278
279 ~queue_guard() {
280 if(i >= 0) lists[i].lock.unlock();
281 if(j >= 0) lists[j].lock.unlock();
282 }
283 };
284
285 auto lock(int i, int j) {
286 assert(i >= 0);
287 assert(i != j);
288 if(j < i) return queue_guard(lists.get(), j, i);
289 return queue_guard(lists.get(), i, j);
290 }
291
292 intrusive_queue_t & best(int i, int j) {
293 assert(i != -1);
294 if(j == -1) return lists[i];
295 return intrusive_queue_t::best(lists[i], lists[j]);
296 }
297
298 intrusive_queue_t & best2(int i, int j) {
299 assert(i != -1);
300 if(j == -1) return lists[i];
301 return intrusive_queue_t::best2(lists[i], lists[j]);
302 }
303};
Note: See TracBrowser for help on using the repository browser.