source: tests/zombies/linked-list-perf/thierry-subqueue-old-rip.hfa@ f5dbc8d

Last change on this file since f5dbc8d was 3c2c2f0, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

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