Context Navigation

ready_subqueue.hfa @ 2b96031

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 2b96031 was 2b96031, checked in by Thierry Delisle <tdelisle@…>, 3 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
355	struct __attribute__((aligned(128))) __timestamp_t {
356	volatile unsigned long long tv;
357	};
358
359	void ?{}(__timestamp_t & this) { this.tv = 0; }
360	void ^?{}(__timestamp_t & this) {}

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format