source: libcfa/src/concurrency/ready_subqueue.hfa@ f04a3df6

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since f04a3df6 was 2b96031, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Added new subqueue implementation.
Seems faster will test on another machine before full replacement.
  • Property mode set to 100644
File size: 11.1 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5#include "containers/queueLockFree.hfa"
6
7// #define USE_NEW_SUBQUEUE
8#if defined(USE_NEW_SUBQUEUE)
9 // Intrusives lanes which are used by the relaxed ready queue
10 struct __attribute__((aligned(128))) __intrusive_lane_t {
11 struct $thread * prev;
12
13 // spin lock protecting the queue
14 volatile bool lock;
15
16 __thread_desc_link anchor;
17 };
18
19 // Get the head pointer (one before the first element) from the anchor
20 static inline $thread * mock_head(const __intrusive_lane_t & this) {
21 $thread * rhead = ($thread *)(
22 (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
23 );
24 return rhead;
25 }
26
27 // Ctor
28 void ?{}( __intrusive_lane_t & this ) {
29 this.lock = false;
30 this.prev = mock_head(this);
31 this.anchor.next = 0p;
32 this.anchor.ts = 0;
33
34 // We add a boat-load of assertions here because the anchor code is very fragile
35 /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
36 /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
37 /* paranoid */ verify( &mock_head(this)->link.ts == &this.anchor.ts );
38 /* paranoid */ verify( mock_head(this)->link.next == 0p );
39 /* paranoid */ verify( mock_head(this)->link.ts == 0 );
40 /* paranoid */ verify( mock_head(this) == this.prev );
41 /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
42 /* paranoid */ verify( __alignof__(this) == 128 );
43 /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
44 }
45
46 // Dtor is trivial
47 void ^?{}( __intrusive_lane_t & this ) {
48 // Make sure the list is empty
49 /* paranoid */ verify( this.anchor.next == 0p );
50 /* paranoid */ verify( this.anchor.ts == 0 );
51 /* paranoid */ verify( mock_head(this) == this.prev );
52 }
53
54 // Push a thread onto this lane
55 // returns true of lane was empty before push, false otherwise
56 void push( __intrusive_lane_t & this, $thread * node ) {
57 /* paranoid */ verify( node->link.next == 0p );
58 /* paranoid */ verify( node->link.ts == 0 );
59 /* paranoid */ verify( this.prev->link.next == 0p );
60 /* paranoid */ verify( this.prev->link.ts == 0 );
61 if( this.anchor.next == 0p ) {
62 /* paranoid */ verify( this.anchor.next == 0p );
63 /* paranoid */ verify( this.anchor.ts == 0 );
64 /* paranoid */ verify( this.prev == mock_head( this ) );
65 } else {
66 /* paranoid */ verify( this.anchor.next != 0p );
67 /* paranoid */ verify( this.anchor.ts != 0 );
68 /* paranoid */ verify( this.prev != mock_head( this ) );
69 }
70
71 // Get the relevant nodes locally
72 this.prev->link.next = node;
73 this.prev->link.ts = rdtscl();
74 this.prev = node;
75 }
76
77 // Pop a thread from this lane (must be non-empty)
78 // returns popped
79 // returns true of lane was empty before push, false otherwise
80 $thread * pop( __intrusive_lane_t & this ) {
81 /* paranoid */ verify( this.anchor.next != 0p );
82 /* paranoid */ verify( this.anchor.ts != 0 );
83
84 // Get the relevant nodes locally
85 $thread * node = this.anchor.next;
86 this.anchor.next = node->link.next;
87 this.anchor.ts = node->link.ts;
88 bool is_empty = this.anchor.ts == 0;
89 node->link.next = 0p;
90 node->link.ts = 0;
91
92 // Update head time stamp
93 if(is_empty) this.prev = mock_head( this );
94
95 /* paranoid */ verify( node->link.next == 0p );
96 /* paranoid */ verify( node->link.ts == 0 );
97 return node;
98 }
99
100 // Check whether or not list is empty
101 static inline bool is_empty(__intrusive_lane_t & this) {
102 return this.anchor.ts == 0;
103 }
104
105 // Return the timestamp
106 static inline unsigned long long ts(__intrusive_lane_t & this) {
107 // Cannot verify here since it may not be locked
108 return this.anchor.ts;
109 }
110#else
111 // Intrusives lanes which are used by the relaxed ready queue
112 struct __attribute__((aligned(128))) __intrusive_lane_t {
113
114 #if defined(USE_MPSC)
115 mpsc_queue($thread) queue;
116 __attribute__((aligned(128)))
117 #else
118 // anchor for the head and the tail of the queue
119 __attribute__((aligned(128))) struct __sentinel_t {
120 // Link lists fields
121 // instrusive link field for threads
122 // must be exactly as in $thread
123 __thread_desc_link link;
124 } before, after;
125
126 // spin lock protecting the queue
127 volatile bool lock;
128 #endif
129
130 // Optional statistic counters
131 #if !defined(__CFA_NO_SCHED_STATS__)
132 struct __attribute__((aligned(64))) {
133 // difference between number of push and pops
134 ssize_t diff;
135
136 // total number of pushes and pops
137 size_t push;
138 size_t pop ;
139 } stat;
140 #endif
141 };
142
143 void ?{}(__intrusive_lane_t & this);
144 void ^?{}(__intrusive_lane_t & this);
145
146 // Get the head pointer (one before the first element) from the anchor
147 static inline $thread * head(const __intrusive_lane_t & this) {
148 #if defined(USE_MPSC)
149 return this.queue.head;
150 #else
151 $thread * rhead = ($thread *)(
152 (uintptr_t)( &this.before ) - offsetof( $thread, link )
153 );
154 /* paranoid */ verify(rhead);
155 return rhead;
156 #endif
157 }
158
159 // Get the tail pointer (one after the last element) from the anchor
160 static inline $thread * tail(const __intrusive_lane_t & this) {
161 #if defined(USE_MPSC)
162 return this.queue.tail;
163 #else
164 $thread * rtail = ($thread *)(
165 (uintptr_t)( &this.after ) - offsetof( $thread, link )
166 );
167 /* paranoid */ verify(rtail);
168 return rtail;
169 #endif
170 }
171
172 // Ctor
173 void ?{}( __intrusive_lane_t & this ) {
174 this.lock = false;
175
176 #if !defined(USE_MPSC)
177 this.before.link.prev = 0p;
178 this.before.link.next = tail(this);
179 this.before.link.ts = 0;
180
181 this.after .link.prev = head(this);
182 this.after .link.next = 0p;
183 this.after .link.ts = 0;
184
185 #if !defined(__CFA_NO_SCHED_STATS__)
186 this.stat.diff = 0;
187 this.stat.push = 0;
188 this.stat.pop = 0;
189 #endif
190
191 // We add a boat-load of assertions here because the anchor code is very fragile
192 /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
193 /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
194 /* paranoid */ verify(head(this)->link.prev == 0p );
195 /* paranoid */ verify(head(this)->link.next == tail(this) );
196 /* paranoid */ verify(tail(this)->link.next == 0p );
197 /* paranoid */ verify(tail(this)->link.prev == head(this) );
198 /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
199 /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
200 /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
201 /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
202 /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
203 /* paranoid */ verify(__alignof__(this) == 128);
204 /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
205 #endif
206 }
207
208 // Dtor is trivial
209 void ^?{}( __intrusive_lane_t & this ) {
210 #if !defined(USE_MPSC)
211 // Make sure the list is empty
212 /* paranoid */ verify(head(this)->link.prev == 0p );
213 /* paranoid */ verify(head(this)->link.next == tail(this) );
214 /* paranoid */ verify(tail(this)->link.next == 0p );
215 /* paranoid */ verify(tail(this)->link.prev == head(this) );
216 #endif
217 }
218
219 // Push a thread onto this lane
220 // returns true of lane was empty before push, false otherwise
221 bool push(__intrusive_lane_t & this, $thread * node) {
222 #if defined(USE_MPSC)
223 inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) {
224 return this->link.next;
225 }
226 push(this.queue, node);
227 #else
228 #if defined(__CFA_WITH_VERIFY__)
229 /* paranoid */ verify(this.lock);
230 /* paranoid */ verify(node->link.ts != 0);
231 /* paranoid */ verify(node->link.next == 0p);
232 /* paranoid */ verify(node->link.prev == 0p);
233 /* paranoid */ verify(tail(this)->link.next == 0p);
234 /* paranoid */ verify(head(this)->link.prev == 0p);
235
236 if(this.before.link.ts == 0l) {
237 /* paranoid */ verify(tail(this)->link.prev == head(this));
238 /* paranoid */ verify(head(this)->link.next == tail(this));
239 } else {
240 /* paranoid */ verify(tail(this)->link.prev != head(this));
241 /* paranoid */ verify(head(this)->link.next != tail(this));
242 }
243 #endif
244
245 // Get the relevant nodes locally
246 $thread * tail = tail(this);
247 $thread * prev = tail->link.prev;
248
249 // Do the push
250 node->link.next = tail;
251 node->link.prev = prev;
252 prev->link.next = node;
253 tail->link.prev = node;
254
255 // Update stats
256 #if !defined(__CFA_NO_SCHED_STATS__)
257 this.stat.diff++;
258 this.stat.push++;
259 #endif
260
261 verify(node->link.next == tail(this));
262
263 // Check if the queue used to be empty
264 if(this.before.link.ts == 0l) {
265 this.before.link.ts = node->link.ts;
266 /* paranoid */ verify(node->link.prev == head(this));
267 return true;
268 }
269 return false;
270 #endif
271 }
272
273 // Pop a thread from this lane (must be non-empty)
274 // returns popped
275 // returns true of lane was empty before push, false otherwise
276 $thread * pop(__intrusive_lane_t & this) {
277 /* paranoid */ verify(this.lock);
278 #if defined(USE_MPSC)
279 inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) {
280 return this->link.next;
281 }
282 return pop(this.queue);
283 #else
284 /* paranoid */ verify(this.before.link.ts != 0ul);
285
286 // Get anchors locally
287 $thread * head = head(this);
288 $thread * tail = tail(this);
289
290 // Get the relevant nodes locally
291 $thread * node = head->link.next;
292 $thread * next = node->link.next;
293
294 /* paranoid */ verify(node != tail);
295 /* paranoid */ verify(node);
296
297 // Do the pop
298 head->link.next = next;
299 next->link.prev = head;
300 node->link.next = 0p;
301 node->link.prev = 0p;
302
303 // Update head time stamp
304 this.before.link.ts = next->link.ts;
305
306 // Update stats
307 #ifndef __CFA_NO_SCHED_STATS__
308 this.stat.diff--;
309 this.stat.pop ++;
310 #endif
311
312 // Check if we emptied list and return accordingly
313 /* paranoid */ verify(tail(this)->link.next == 0p);
314 /* paranoid */ verify(head(this)->link.prev == 0p);
315 if(next == tail) {
316 /* paranoid */ verify(this.before.link.ts == 0);
317 /* paranoid */ verify(tail(this)->link.prev == head(this));
318 /* paranoid */ verify(head(this)->link.next == tail(this));
319 return node;
320 }
321 else {
322 /* paranoid */ verify(next->link.ts != 0);
323 /* paranoid */ verify(tail(this)->link.prev != head(this));
324 /* paranoid */ verify(head(this)->link.next != tail(this));
325 /* paranoid */ verify(this.before.link.ts != 0);
326 return node;
327 }
328 #endif
329 }
330
331 // Check whether or not list is empty
332 static inline bool is_empty(__intrusive_lane_t & this) {
333 #if defined(USE_MPSC)
334 return this.queue.head == 0p;
335 #else
336 // Cannot verify here since it may not be locked
337 return this.before.link.ts == 0;
338 #endif
339 }
340
341 // Return the timestamp
342 static inline unsigned long long ts(__intrusive_lane_t & this) {
343 #if defined(USE_MPSC)
344 $thread * tl = this.queue.head;
345 if(!tl) return -1ull;
346 return tl->link.ts;
347 #else
348 // Cannot verify here since it may not be locked
349 return this.before.link.ts;
350 #endif
351 }
352#endif
353
354// Aligned timestamps which are used by the relaxed ready queue
355struct __attribute__((aligned(128))) __timestamp_t {
356 volatile unsigned long long tv;
357};
358
359void ?{}(__timestamp_t & this) { this.tv = 0; }
360void ^?{}(__timestamp_t & this) {}
Note: See TracBrowser for help on using the repository browser.