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

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 a33c113 was 7a2972b9, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

ready queue can now toggle between

  • lock-based queue
  • mpsc_queue a.k.a. nemesis queue

slightly messy implementation, some clean up needed.
  • Property mode set to 100644
File size: 7.1 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5#include "containers/queueLockFree.hfa"
6
7// Intrusives lanes which are used by the relaxed ready queue
8struct __attribute__((aligned(128))) __intrusive_lane_t {
9
10 #if defined(USE_MPSC)
11 mpsc_queue($thread) queue;
12 __attribute__((aligned(128)))
13 #else
14 // anchor for the head and the tail of the queue
15 __attribute__((aligned(128))) struct __sentinel_t {
16 // Link lists fields
17 // instrusive link field for threads
18 // must be exactly as in $thread
19 __thread_desc_link link;
20 } before, after;
21 #endif
22
23 // spin lock protecting the queue
24 volatile bool lock;
25
26 // Optional statistic counters
27 #if !defined(__CFA_NO_SCHED_STATS__)
28 struct __attribute__((aligned(64))) {
29 // difference between number of push and pops
30 ssize_t diff;
31
32 // total number of pushes and pops
33 size_t push;
34 size_t pop ;
35 } stat;
36 #endif
37};
38
39void ?{}(__intrusive_lane_t & this);
40void ^?{}(__intrusive_lane_t & this);
41
42// Get the head pointer (one before the first element) from the anchor
43static inline $thread * head(const __intrusive_lane_t & this) {
44 #if defined(USE_MPSC)
45 return this.queue.head;
46 #else
47 $thread * rhead = ($thread *)(
48 (uintptr_t)( &this.before ) - offsetof( $thread, link )
49 );
50 /* paranoid */ verify(rhead);
51 return rhead;
52 #endif
53}
54
55// Get the tail pointer (one after the last element) from the anchor
56static inline $thread * tail(const __intrusive_lane_t & this) {
57 #if defined(USE_MPSC)
58 return this.queue.tail;
59 #else
60 $thread * rtail = ($thread *)(
61 (uintptr_t)( &this.after ) - offsetof( $thread, link )
62 );
63 /* paranoid */ verify(rtail);
64 return rtail;
65 #endif
66}
67
68// Ctor
69void ?{}( __intrusive_lane_t & this ) {
70 this.lock = false;
71
72 #if !defined(USE_MPSC)
73 this.before.link.prev = 0p;
74 this.before.link.next = tail(this);
75 this.before.link.ts = 0;
76
77 this.after .link.prev = head(this);
78 this.after .link.next = 0p;
79 this.after .link.ts = 0;
80
81 #if !defined(__CFA_NO_SCHED_STATS__)
82 this.stat.diff = 0;
83 this.stat.push = 0;
84 this.stat.pop = 0;
85 #endif
86
87 // We add a boat-load of assertions here because the anchor code is very fragile
88 /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
89 /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
90 /* paranoid */ verify(head(this)->link.prev == 0p );
91 /* paranoid */ verify(head(this)->link.next == tail(this) );
92 /* paranoid */ verify(tail(this)->link.next == 0p );
93 /* paranoid */ verify(tail(this)->link.prev == head(this) );
94 /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
95 /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
96 /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
97 /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
98 /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
99 /* paranoid */ verify(__alignof__(this) == 128);
100 /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
101 #endif
102}
103
104// Dtor is trivial
105void ^?{}( __intrusive_lane_t & this ) {
106 #if !defined(USE_MPSC)
107 // Make sure the list is empty
108 /* paranoid */ verify(head(this)->link.prev == 0p );
109 /* paranoid */ verify(head(this)->link.next == tail(this) );
110 /* paranoid */ verify(tail(this)->link.next == 0p );
111 /* paranoid */ verify(tail(this)->link.prev == head(this) );
112 #endif
113}
114
115// Push a thread onto this lane
116// returns true of lane was empty before push, false otherwise
117bool push(__intrusive_lane_t & this, $thread * node) {
118 #if defined(USE_MPSC)
119 inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) {
120 return this->link.next;
121 }
122 push(this.queue, node);
123 #else
124 #if defined(__CFA_WITH_VERIFY__)
125 /* paranoid */ verify(this.lock);
126 /* paranoid */ verify(node->link.ts != 0);
127 /* paranoid */ verify(node->link.next == 0p);
128 /* paranoid */ verify(node->link.prev == 0p);
129 /* paranoid */ verify(tail(this)->link.next == 0p);
130 /* paranoid */ verify(head(this)->link.prev == 0p);
131
132 if(this.before.link.ts == 0l) {
133 /* paranoid */ verify(tail(this)->link.prev == head(this));
134 /* paranoid */ verify(head(this)->link.next == tail(this));
135 } else {
136 /* paranoid */ verify(tail(this)->link.prev != head(this));
137 /* paranoid */ verify(head(this)->link.next != tail(this));
138 }
139 #endif
140
141 // Get the relevant nodes locally
142 $thread * tail = tail(this);
143 $thread * prev = tail->link.prev;
144
145 // Do the push
146 node->link.next = tail;
147 node->link.prev = prev;
148 prev->link.next = node;
149 tail->link.prev = node;
150
151 // Update stats
152 #if !defined(__CFA_NO_SCHED_STATS__)
153 this.stat.diff++;
154 this.stat.push++;
155 #endif
156
157 verify(node->link.next == tail(this));
158
159 // Check if the queue used to be empty
160 if(this.before.link.ts == 0l) {
161 this.before.link.ts = node->link.ts;
162 /* paranoid */ verify(node->link.prev == head(this));
163 return true;
164 }
165 return false;
166 #endif
167}
168
169// Pop a thread from this lane (must be non-empty)
170// returns popped
171// returns true of lane was empty before push, false otherwise
172$thread * pop(__intrusive_lane_t & this) {
173 /* paranoid */ verify(this.lock);
174 #if defined(USE_MPSC)
175 inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) {
176 return this->link.next;
177 }
178 return pop(this.queue);
179 #else
180 /* paranoid */ verify(this.before.link.ts != 0ul);
181
182 // Get anchors locally
183 $thread * head = head(this);
184 $thread * tail = tail(this);
185
186 // Get the relevant nodes locally
187 $thread * node = head->link.next;
188 $thread * next = node->link.next;
189
190 /* paranoid */ verify(node != tail);
191 /* paranoid */ verify(node);
192
193 // Do the pop
194 head->link.next = next;
195 next->link.prev = head;
196 node->link.next = 0p;
197 node->link.prev = 0p;
198
199 // Update head time stamp
200 this.before.link.ts = next->link.ts;
201
202 // Update stats
203 #ifndef __CFA_NO_SCHED_STATS__
204 this.stat.diff--;
205 this.stat.pop ++;
206 #endif
207
208 // Check if we emptied list and return accordingly
209 /* paranoid */ verify(tail(this)->link.next == 0p);
210 /* paranoid */ verify(head(this)->link.prev == 0p);
211 if(next == tail) {
212 /* paranoid */ verify(this.before.link.ts == 0);
213 /* paranoid */ verify(tail(this)->link.prev == head(this));
214 /* paranoid */ verify(head(this)->link.next == tail(this));
215 return node;
216 }
217 else {
218 /* paranoid */ verify(next->link.ts != 0);
219 /* paranoid */ verify(tail(this)->link.prev != head(this));
220 /* paranoid */ verify(head(this)->link.next != tail(this));
221 /* paranoid */ verify(this.before.link.ts != 0);
222 return node;
223 }
224 #endif
225}
226
227// Check whether or not list is empty
228static inline bool is_empty(__intrusive_lane_t & this) {
229 #if defined(USE_MPSC)
230 return this.queue.head == 0p;
231 #else
232 // Cannot verify here since it may not be locked
233 return this.before.link.ts == 0;
234 #endif
235}
236
237// Return the timestamp
238static inline unsigned long long ts(__intrusive_lane_t & this) {
239 #if defined(USE_MPSC)
240 $thread * tl = this.queue.head;
241 if(!tl) return -1ull;
242 return tl->link.ts;
243 #else
244 // Cannot verify here since it may not be locked
245 return this.before.link.ts;
246 #endif
247}
Note: See TracBrowser for help on using the repository browser.