Context Navigation

fwd.hfa @ 12782a9

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

Last change on this file since 12782a9 was e84ab3d, checked in by Thierry Delisle <tdelisle@…>, 3 years ago
Step 1 of changing $thread to thread$
Property mode set to `100644`
File size: 12.4 KB

Rev	Line
[e660761]	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	//
[454f478]	7	// kernel/fwd.hfa -- PUBLIC
	8	// Fundamental code needed to implement threading M.E.S. algorithms.
[e660761]	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
[3e2b9c9]	17	#pragma once
	18
[e660761]	19	#include "bits/defs.hfa"
	20	#include "bits/debug.hfa"
	21
[3e2b9c9]	22	#ifdef __cforall
	23	#include "bits/random.hfa"
[e660761]	24	#endif
	25
[e84ab3d]	26	struct thread$;
[e660761]	27	struct processor;
	28	struct cluster;
	29
[3e2b9c9]	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
[e660761]	34	#ifdef __cforall
	35	extern "C" {
[3e2b9c9]	36	extern "Cforall" {
[e660761]	37	extern __attribute__((aligned(128))) thread_local struct KernelThreadData {
[e84ab3d]	38	struct thread$ * volatile this_thread;
[e873838]	39	struct processor * volatile this_processor;
[c993b15]	40	volatile bool sched_lock;
[e660761]	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
[f2384c9a]	53	struct {
	54	uint64_t fwd_seed;
	55	uint64_t bck_seed;
	56	} ready_rng;
[c993b15]	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
[8fc652e0]	66	} __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
[3e2b9c9]	67
[8fc652e0]	68	extern bool __preemption_enabled();
[f2384c9a]	69
[8fc652e0]	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 );
[82a2fed]	76	#define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
[f2384c9a]	77
[3e2b9c9]	78	static inline uint64_t __tls_rand() {
	79	#if defined(__SIZEOF_INT128__)
[8fc652e0]	80	return __lehmer64( kernelTLS().rand_seed );
[3e2b9c9]	81	#else
[8fc652e0]	82	return __xorshift64( kernelTLS().rand_seed );
[3e2b9c9]	83	#endif
	84	}
[f2384c9a]	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
[8fc652e0]	94	kernelTLS().ready_rng.fwd_seed = (A * kernelTLS().ready_rng.fwd_seed + C) & (M - 1);
	95	return kernelTLS().ready_rng.fwd_seed >> D;
[f2384c9a]	96	}
	97
	98	static inline unsigned __tls_rand_bck() {
[8fc652e0]	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);
[f2384c9a]	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) {
[8fc652e0]	111	kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
[f2384c9a]	112	}
[e660761]	113	}
	114
[8fc652e0]	115
[3e2b9c9]	116
	117	extern void disable_interrupts();
[a3821fa]	118	extern void enable_interrupts( bool poll = false );
[e660761]	119
[3e2b9c9]	120	extern "Cforall" {
[e235429]	121	extern void park( void );
[e84ab3d]	122	extern void unpark( struct thread$ * this );
	123	static inline struct thread$ * active_thread () {
	124	struct thread$ * t = publicTLS_get( this_thread );
[8fc652e0]	125	/* paranoid */ verify( t );
	126	return t;
	127	}
[3e2b9c9]	128
	129	extern bool force_yield( enum __Preemption_Reason );
[e660761]	130
[3e2b9c9]	131	static inline void yield() {
	132	force_yield(__MANUAL_PREEMPTION);
	133	}
[e660761]	134
[3e2b9c9]	135	// Yield: yield N times
	136	static inline void yield( unsigned times ) {
	137	for( times ) {
	138	yield();
	139	}
	140	}
	141
[fe9468e2]	142	extern uint64_t thread_rand();
	143
[454f478]	144	// Semaphore which only supports a single thread
	145	struct single_sem {
[e84ab3d]	146	struct thread$ * volatile ptr;
[454f478]	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() {
[e84ab3d]	158	struct thread$ * expected = this.ptr;
[454f478]	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() {
[e84ab3d]	177	struct thread$ * expected = this.ptr;
[454f478]	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
[e84ab3d]	202	struct thread$ * volatile ptr;
[454f478]	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() {
[e84ab3d]	216	struct thread$ * expected = this.ptr;
[454f478]	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
[e84ab3d]	229	thread$ * post(oneshot & this, bool do_unpark = true) {
	230	struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
[a76efc8]	231	if( got == 0p ) return 0p;
	232	if(do_unpark) unpark( got );
	233	return got;
[454f478]	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
[e84ab3d]	345	thread$ * fulfil( future_t & this, bool do_unpark = true ) {
[454f478]	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
[a76efc8]	353	if( expected == 3p ) { free( &this ); return 0p; }
[454f478]	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)) {
[a76efc8]	365	if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return 0p; }
[e84ab3d]	366	thread$ * ret = post( *expected, do_unpark );
[454f478]	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
[3e2b9c9]	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() {
[8fc652e0]	402	/* paranoid */ verify( ! __preemption_enabled() );
	403	/* paranoid */ verify( kernelTLS().this_stats );
	404	return kernelTLS().this_stats;
[3e2b9c9]	405	}
	406
	407	#define __STATS__(in_kernel, ...) { \
	408	if( !(in_kernel) ) disable_interrupts(); \
	409	with( *__tls_stats() ) { \
	410	__VA_ARGS__ \
	411	} \
[a3821fa]	412	if( !(in_kernel) ) enable_interrupts(); \
[3e2b9c9]	413	}
	414	#else
	415	#define __STATS__(in_kernel, ...)
	416	#endif
	417	}
[e660761]	418	}
[442b624]	419	#endif

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

Download in other formats:

Original Format