Context Navigation

fwd.hfa @ eef2a9b

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since eef2a9b was c993b15, checked in by Thierry Delisle <tdelisle@…>, 4 years ago
Changed RW lock to avoid hitting the global array on schedule.
Property mode set to `100644`
File size: 12.4 KB

Line
1	//
2	// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
3	//
4	// The contents of this file are covered under the licence agreement in the
5	// file "LICENCE" distributed with Cforall.
6	//
7	// kernel/fwd.hfa -- PUBLIC
8	// Fundamental code needed to implement threading M.E.S. algorithms.
9	//
10	// Author : Thierry Delisle
11	// Created On : Thu Jul 30 16:46:41 2020
12	// Last Modified By :
13	// Last Modified On :
14	// Update Count :
15	//
16
17	#pragma once
18
19	#include "bits/defs.hfa"
20	#include "bits/debug.hfa"
21
22	#ifdef __cforall
23	#include "bits/random.hfa"
24	#endif
25
26	struct $thread;
27	struct processor;
28	struct cluster;
29
30	enum __Preemption_Reason { __NO_PREEMPTION, __ALARM_PREEMPTION, __POLL_PREEMPTION, __MANUAL_PREEMPTION };
31
32	#define KERNEL_STORAGE(T,X) __attribute((aligned(__alignof__(T)))) static char storage_##X[sizeof(T)]
33
34	#ifdef __cforall
35	extern "C" {
36	extern "Cforall" {
37	extern __attribute__((aligned(128))) thread_local struct KernelThreadData {
38	struct $thread * volatile this_thread;
39	struct processor * volatile this_processor;
40	volatile bool sched_lock;
41
42	struct {
43	volatile unsigned short disable_count;
44	volatile bool enabled;
45	volatile bool in_progress;
46	} preemption_state;
47
48	#if defined(__SIZEOF_INT128__)
49	__uint128_t rand_seed;
50	#else
51	uint64_t rand_seed;
52	#endif
53	struct {
54	uint64_t fwd_seed;
55	uint64_t bck_seed;
56	} ready_rng;
57
58	struct __stats_t * volatile this_stats;
59
60
61	#ifdef __CFA_WITH_VERIFY__
62	// Debug, check if the rwlock is owned for reading
63	bool in_sched_lock;
64	unsigned sched_id;
65	#endif
66	} __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
67
68	extern bool __preemption_enabled();
69
70	static inline KernelThreadData & kernelTLS( void ) {
71	/* paranoid */ verify( ! __preemption_enabled() );
72	return __cfaabi_tls;
73	}
74
75	extern uintptr_t __cfatls_get( unsigned long int member );
76	#define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
77
78	static inline uint64_t __tls_rand() {
79	#if defined(__SIZEOF_INT128__)
80	return __lehmer64( kernelTLS().rand_seed );
81	#else
82	return __xorshift64( kernelTLS().rand_seed );
83	#endif
84	}
85
86	#define M (1_l64u << 48_l64u)
87	#define A (25214903917_l64u)
88	#define AI (18446708753438544741_l64u)
89	#define C (11_l64u)
90	#define D (16_l64u)
91
92	static inline unsigned __tls_rand_fwd() {
93
94	kernelTLS().ready_rng.fwd_seed = (A * kernelTLS().ready_rng.fwd_seed + C) & (M - 1);
95	return kernelTLS().ready_rng.fwd_seed >> D;
96	}
97
98	static inline unsigned __tls_rand_bck() {
99	unsigned int r = kernelTLS().ready_rng.bck_seed >> D;
100	kernelTLS().ready_rng.bck_seed = AI * (kernelTLS().ready_rng.bck_seed - C) & (M - 1);
101	return r;
102	}
103
104	#undef M
105	#undef A
106	#undef AI
107	#undef C
108	#undef D
109
110	static inline void __tls_rand_advance_bck(void) {
111	kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
112	}
113	}
114
115
116
117	extern void disable_interrupts();
118	extern void enable_interrupts( bool poll = false );
119
120	extern "Cforall" {
121	extern void park( void );
122	extern void unpark( struct $thread * this );
123	static inline struct $thread * active_thread () {
124	struct $thread * t = publicTLS_get( this_thread );
125	/* paranoid */ verify( t );
126	return t;
127	}
128
129	extern bool force_yield( enum __Preemption_Reason );
130
131	static inline void yield() {
132	force_yield(__MANUAL_PREEMPTION);
133	}
134
135	// Yield: yield N times
136	static inline void yield( unsigned times ) {
137	for( times ) {
138	yield();
139	}
140	}
141
142	extern uint64_t thread_rand();
143
144	// Semaphore which only supports a single thread
145	struct single_sem {
146	struct $thread * volatile ptr;
147	};
148
149	static inline {
150	void ?{}(single_sem & this) {
151	this.ptr = 0p;
152	}
153
154	void ^?{}(single_sem &) {}
155
156	bool wait(single_sem & this) {
157	for() {
158	struct $thread * expected = this.ptr;
159	if(expected == 1p) {
160	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
161	return false;
162	}
163	}
164	else {
165	/* paranoid */ verify( expected == 0p );
166	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
167	park();
168	return true;
169	}
170	}
171
172	}
173	}
174
175	bool post(single_sem & this) {
176	for() {
177	struct $thread * expected = this.ptr;
178	if(expected == 1p) return false;
179	if(expected == 0p) {
180	if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
181	return false;
182	}
183	}
184	else {
185	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
186	unpark( expected );
187	return true;
188	}
189	}
190	}
191	}
192	}
193
194	// Synchronozation primitive which only supports a single thread and one post
195	// Similar to a binary semaphore with a 'one shot' semantic
196	// is expected to be discarded after each party call their side
197	struct oneshot {
198	// Internal state :
199	// 0p : is initial state (wait will block)
200	// 1p : fulfilled (wait won't block)
201	// any thread : a thread is currently waiting
202	struct $thread * volatile ptr;
203	};
204
205	static inline {
206	void ?{}(oneshot & this) {
207	this.ptr = 0p;
208	}
209
210	void ^?{}(oneshot &) {}
211
212	// Wait for the post, return immidiately if it already happened.
213	// return true if the thread was parked
214	bool wait(oneshot & this) {
215	for() {
216	struct $thread * expected = this.ptr;
217	if(expected == 1p) return false;
218	/* paranoid */ verify( expected == 0p );
219	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
220	park();
221	/* paranoid */ verify( this.ptr == 1p );
222	return true;
223	}
224	}
225	}
226
227	// Mark as fulfilled, wake thread if needed
228	// return true if a thread was unparked
229	$thread * post(oneshot & this, bool do_unpark = true) {
230	struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
231	if( got == 0p ) return 0p;
232	if(do_unpark) unpark( got );
233	return got;
234	}
235	}
236
237	// base types for future to build upon
238	// It is based on the 'oneshot' type to allow multiple futures
239	// to block on the same instance, permitting users to block a single
240	// thread on "any of" [a given set of] futures.
241	// does not support multiple threads waiting on the same future
242	struct future_t {
243	// Internal state :
244	// 0p : is initial state (wait will block)
245	// 1p : fulfilled (wait won't block)
246	// 2p : in progress ()
247	// 3p : abandoned, server should delete
248	// any oneshot : a context has been setup to wait, a thread could wait on it
249	struct oneshot * volatile ptr;
250	};
251
252	static inline {
253	void ?{}(future_t & this) {
254	this.ptr = 0p;
255	}
256
257	void ^?{}(future_t &) {}
258
259	void reset(future_t & this) {
260	// needs to be in 0p or 1p
261	__atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
262	}
263
264	// check if the future is available
265	bool available( future_t & this ) {
266	return this.ptr == 1p;
267	}
268
269	// Prepare the future to be waited on
270	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
271	bool setup( future_t & this, oneshot & wait_ctx ) {
272	/* paranoid */ verify( wait_ctx.ptr == 0p );
273	// The future needs to set the wait context
274	for() {
275	struct oneshot * expected = this.ptr;
276	// Is the future already fulfilled?
277	if(expected == 1p) return false; // Yes, just return false (didn't block)
278
279	// The future is not fulfilled, try to setup the wait context
280	/* paranoid */ verify( expected == 0p );
281	if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
282	return true;
283	}
284	}
285	}
286
287	// Stop waiting on a future
288	// When multiple futures are waited for together in "any of" pattern
289	// futures that weren't fulfilled before the thread woke up
290	// should retract the wait ctx
291	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
292	void retract( future_t & this, oneshot & wait_ctx ) {
293	// Remove the wait context
294	struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
295
296	// got == 0p: future was never actually setup, just return
297	if( got == 0p ) return;
298
299	// got == wait_ctx: since fulfil does an atomic_swap,
300	// if we got back the original then no one else saw context
301	// It is safe to delete (which could happen after the return)
302	if( got == &wait_ctx ) return;
303
304	// got == 1p: the future is ready and the context was fully consumed
305	// the server won't use the pointer again
306	// It is safe to delete (which could happen after the return)
307	if( got == 1p ) return;
308
309	// got == 2p: the future is ready but the context hasn't fully been consumed
310	// spin until it is safe to move on
311	if( got == 2p ) {
312	while( this.ptr != 1p ) Pause();
313	return;
314	}
315
316	// got == any thing else, something wen't wrong here, abort
317	abort("Future in unexpected state");
318	}
319
320	// Mark the future as abandoned, meaning it will be deleted by the server
321	bool abandon( future_t & this ) {
322	/* paranoid */ verify( this.ptr != 3p );
323
324	// Mark the future as abandonned
325	struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
326
327	// If the future isn't already fulfilled, let the server delete it
328	if( got == 0p ) return false;
329
330	// got == 2p: the future is ready but the context hasn't fully been consumed
331	// spin until it is safe to move on
332	if( got == 2p ) {
333	while( this.ptr != 1p ) Pause();
334	got = 1p;
335	}
336
337	// The future is completed delete it now
338	/* paranoid */ verify( this.ptr != 1p );
339	free( &this );
340	return true;
341	}
342
343	// from the server side, mark the future as fulfilled
344	// delete it if needed
345	$thread * fulfil( future_t & this, bool do_unpark = true ) {
346	for() {
347	struct oneshot * expected = this.ptr;
348	// was this abandoned?
349	#if defined(__GNUC__) && __GNUC__ >= 7
350	#pragma GCC diagnostic push
351	#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
352	#endif
353	if( expected == 3p ) { free( &this ); return 0p; }
354	#if defined(__GNUC__) && __GNUC__ >= 7
355	#pragma GCC diagnostic pop
356	#endif
357
358	/* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
359	/* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
360
361	// If there is a wait context, we need to consume it and mark it as consumed after
362	// If there is no context then we can skip the in progress phase
363	struct oneshot * want = expected == 0p ? 1p : 2p;
364	if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
365	if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return 0p; }
366	$thread * ret = post( *expected, do_unpark );
367	__atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
368	return ret;
369	}
370	}
371
372	}
373
374	// Wait for the future to be fulfilled
375	bool wait( future_t & this ) {
376	oneshot temp;
377	if( !setup(this, temp) ) return false;
378
379	// Wait context is setup, just wait on it
380	bool ret = wait( temp );
381
382	// Wait for the future to tru
383	while( this.ptr == 2p ) Pause();
384	// Make sure the state makes sense
385	// Should be fulfilled, could be in progress but it's out of date if so
386	// since if that is the case, the oneshot was fulfilled (unparking this thread)
387	// and the oneshot should not be needed any more
388	__attribute__((unused)) struct oneshot * was = this.ptr;
389	/* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
390
391	// Mark the future as fulfilled, to be consistent
392	// with potential calls to avail
393	// this.ptr = 1p;
394	return ret;
395	}
396	}
397
398	//-----------------------------------------------------------------------
399	// Statics call at the end of each thread to register statistics
400	#if !defined(__CFA_NO_STATISTICS__)
401	static inline struct __stats_t * __tls_stats() {
402	/* paranoid */ verify( ! __preemption_enabled() );
403	/* paranoid */ verify( kernelTLS().this_stats );
404	return kernelTLS().this_stats;
405	}
406
407	#define __STATS__(in_kernel, ...) { \
408	if( !(in_kernel) ) disable_interrupts(); \
409	with( *__tls_stats() ) { \
410	__VA_ARGS__ \
411	} \
412	if( !(in_kernel) ) enable_interrupts(); \
413	}
414	#else
415	#define __STATS__(in_kernel, ...)
416	#endif
417	}
418	}
419	#endif

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

Download in other formats:

Original Format