Context Navigation

fwd.hfa @ 9b71679

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

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

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

Download in other formats:

Original Format