Context Navigation

fwd.hfa @ d489da8

ADTast-experimentalpthread-emulation

Last change on this file since d489da8 was 1bcbf02, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Changed declarations using _Thread_local to use thread.
I'm fairly sure they do exactly the same, but thread is:

more consistent with uC++.
Shorter.
Better documented.

Property mode set to 100644

File size: 13.1 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" {
[1bcbf02]	37	extern __attribute__((aligned(64))) __thread 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() {
[c52f033]	79	return
[3e2b9c9]	80	#if defined(__SIZEOF_INT128__)
[5d1ebb9]	81	lehmer64( kernelTLS().rand_seed );
[3e2b9c9]	82	#else
[5d1ebb9]	83	xorshift_13_7_17( kernelTLS().rand_seed );
[3e2b9c9]	84	#endif
	85	}
[f2384c9a]	86
	87	static inline unsigned __tls_rand_fwd() {
[5d1ebb9]	88	return LCGBI_fwd( kernelTLS().ready_rng.fwd_seed );
[f2384c9a]	89	}
	90
	91	static inline unsigned __tls_rand_bck() {
[5d1ebb9]	92	return LCGBI_bck( kernelTLS().ready_rng.bck_seed );
[f2384c9a]	93	}
	94
	95	static inline void __tls_rand_advance_bck(void) {
[8fc652e0]	96	kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
[f2384c9a]	97	}
[e660761]	98	}
	99
[3e2b9c9]	100	extern void disable_interrupts();
[a3821fa]	101	extern void enable_interrupts( bool poll = false );
[e660761]	102
[3e2b9c9]	103	extern "Cforall" {
[24e321c]	104	enum unpark_hint { UNPARK_LOCAL, UNPARK_REMOTE };
	105
[e235429]	106	extern void park( void );
[24e321c]	107	extern void unpark( struct thread$ *, unpark_hint );
	108	static inline void unpark( struct thread$ * thrd ) { unpark(thrd, UNPARK_LOCAL); }
[e84ab3d]	109	static inline struct thread$ * active_thread () {
	110	struct thread$ * t = publicTLS_get( this_thread );
[8fc652e0]	111	/* paranoid */ verify( t );
	112	return t;
	113	}
[3e2b9c9]	114
	115	extern bool force_yield( enum __Preemption_Reason );
[e660761]	116
[3e2b9c9]	117	static inline void yield() {
	118	force_yield(__MANUAL_PREEMPTION);
	119	}
[e660761]	120
[3e2b9c9]	121	// Yield: yield N times
	122	static inline void yield( unsigned times ) {
	123	for( times ) {
	124	yield();
	125	}
	126	}
	127
[454f478]	128	// Semaphore which only supports a single thread
	129	struct single_sem {
[e84ab3d]	130	struct thread$ * volatile ptr;
[454f478]	131	};
	132
	133	static inline {
	134	void ?{}(single_sem & this) {
	135	this.ptr = 0p;
	136	}
	137
	138	void ^?{}(single_sem &) {}
	139
	140	bool wait(single_sem & this) {
	141	for() {
[e84ab3d]	142	struct thread$ * expected = this.ptr;
[454f478]	143	if(expected == 1p) {
	144	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	145	return false;
	146	}
	147	}
	148	else {
	149	/* paranoid */ verify( expected == 0p );
	150	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	151	park();
	152	return true;
	153	}
	154	}
	155
	156	}
	157	}
	158
	159	bool post(single_sem & this) {
	160	for() {
[e84ab3d]	161	struct thread$ * expected = this.ptr;
[454f478]	162	if(expected == 1p) return false;
	163	if(expected == 0p) {
	164	if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	165	return false;
	166	}
	167	}
	168	else {
	169	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	170	unpark( expected );
	171	return true;
	172	}
	173	}
	174	}
	175	}
	176	}
	177
	178	// Synchronozation primitive which only supports a single thread and one post
	179	// Similar to a binary semaphore with a 'one shot' semantic
	180	// is expected to be discarded after each party call their side
	181	struct oneshot {
	182	// Internal state :
	183	// 0p : is initial state (wait will block)
	184	// 1p : fulfilled (wait won't block)
	185	// any thread : a thread is currently waiting
[e84ab3d]	186	struct thread$ * volatile ptr;
[454f478]	187	};
	188
	189	static inline {
	190	void ?{}(oneshot & this) {
	191	this.ptr = 0p;
	192	}
	193
	194	void ^?{}(oneshot &) {}
	195
	196	// Wait for the post, return immidiately if it already happened.
	197	// return true if the thread was parked
	198	bool wait(oneshot & this) {
	199	for() {
[e84ab3d]	200	struct thread$ * expected = this.ptr;
[454f478]	201	if(expected == 1p) return false;
	202	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	203	park();
	204	/* paranoid */ verify( this.ptr == 1p );
	205	return true;
	206	}
	207	}
	208	}
	209
	210	// Mark as fulfilled, wake thread if needed
	211	// return true if a thread was unparked
[e84ab3d]	212	thread$ * post(oneshot & this, bool do_unpark = true) {
	213	struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
[c06551b]	214	if( got == 0p \|\| got == 1p ) return 0p;
[a76efc8]	215	if(do_unpark) unpark( got );
	216	return got;
[454f478]	217	}
	218	}
	219
	220	// base types for future to build upon
	221	// It is based on the 'oneshot' type to allow multiple futures
	222	// to block on the same instance, permitting users to block a single
	223	// thread on "any of" [a given set of] futures.
	224	// does not support multiple threads waiting on the same future
	225	struct future_t {
	226	// Internal state :
	227	// 0p : is initial state (wait will block)
	228	// 1p : fulfilled (wait won't block)
	229	// 2p : in progress ()
	230	// 3p : abandoned, server should delete
	231	// any oneshot : a context has been setup to wait, a thread could wait on it
	232	struct oneshot * volatile ptr;
	233	};
	234
	235	static inline {
	236	void ?{}(future_t & this) {
	237	this.ptr = 0p;
	238	}
	239
	240	void ^?{}(future_t &) {}
	241
	242	void reset(future_t & this) {
	243	// needs to be in 0p or 1p
	244	__atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
	245	}
	246
	247	// check if the future is available
	248	bool available( future_t & this ) {
[64bdacc]	249	while( this.ptr == 2p ) Pause();
[454f478]	250	return this.ptr == 1p;
	251	}
	252
	253	// Prepare the future to be waited on
	254	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
	255	bool setup( future_t & this, oneshot & wait_ctx ) {
[fc2c57a9]	256	/* paranoid */ verify( wait_ctx.ptr == 0p \|\| wait_ctx.ptr == 1p );
[454f478]	257	// The future needs to set the wait context
	258	for() {
	259	struct oneshot * expected = this.ptr;
	260	// Is the future already fulfilled?
	261	if(expected == 1p) return false; // Yes, just return false (didn't block)
	262
	263	// The future is not fulfilled, try to setup the wait context
	264	if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	265	return true;
	266	}
	267	}
	268	}
	269
	270	// Stop waiting on a future
	271	// When multiple futures are waited for together in "any of" pattern
	272	// futures that weren't fulfilled before the thread woke up
	273	// should retract the wait ctx
	274	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
[c06551b]	275	bool retract( future_t & this, oneshot & wait_ctx ) {
[fc2c57a9]	276	struct oneshot * expected = this.ptr;
[454f478]	277
[fc2c57a9]	278	// attempt to remove the context so it doesn't get consumed.
	279	if(__atomic_compare_exchange_n( &this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	280	// we still have the original context, then no one else saw it
	281	return false;
	282	}
[1c56bf7]	283
[fc2c57a9]	284	// expected == 0p: future was never actually setup, just return
	285	if( expected == 0p ) return false;
[1c56bf7]	286
[fc2c57a9]	287	// expected == 1p: the future is ready and the context was fully consumed
	288	// the server won't use the pointer again
	289	// It is safe to delete (which could happen after the return)
	290	if( expected == 1p ) return true;
[1c56bf7]	291
[fc2c57a9]	292	// expected == 2p: the future is ready but the context hasn't fully been consumed
	293	// spin until it is safe to move on
	294	if( expected == 2p ) {
	295	while( this.ptr != 1p ) Pause();
	296	/* paranoid */ verify( this.ptr == 1p );
	297	return true;
[1c56bf7]	298	}
[fc2c57a9]	299
	300	// anything else: the future was setup with a different context ?!?!
	301	// something went wrong here, abort
	302	abort("Future in unexpected state");
[454f478]	303	}
	304
	305	// Mark the future as abandoned, meaning it will be deleted by the server
	306	bool abandon( future_t & this ) {
	307	/* paranoid */ verify( this.ptr != 3p );
	308
	309	// Mark the future as abandonned
	310	struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
	311
	312	// If the future isn't already fulfilled, let the server delete it
	313	if( got == 0p ) return false;
	314
	315	// got == 2p: the future is ready but the context hasn't fully been consumed
	316	// spin until it is safe to move on
	317	if( got == 2p ) {
	318	while( this.ptr != 1p ) Pause();
	319	got = 1p;
	320	}
	321
	322	// The future is completed delete it now
	323	/* paranoid */ verify( this.ptr != 1p );
	324	free( &this );
	325	return true;
	326	}
	327
	328	// from the server side, mark the future as fulfilled
	329	// delete it if needed
[e84ab3d]	330	thread$ * fulfil( future_t & this, bool do_unpark = true ) {
[454f478]	331	for() {
	332	struct oneshot * expected = this.ptr;
	333	// was this abandoned?
	334	#if defined(__GNUC__) && __GNUC__ >= 7
	335	#pragma GCC diagnostic push
	336	#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
	337	#endif
[a76efc8]	338	if( expected == 3p ) { free( &this ); return 0p; }
[454f478]	339	#if defined(__GNUC__) && __GNUC__ >= 7
	340	#pragma GCC diagnostic pop
	341	#endif
	342
	343	/* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
	344	/* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
	345
	346	// If there is a wait context, we need to consume it and mark it as consumed after
	347	// If there is no context then we can skip the in progress phase
	348	struct oneshot * want = expected == 0p ? 1p : 2p;
	349	if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
[13fdf86]	350	if( expected == 0p ) { return 0p; }
[e84ab3d]	351	thread$ * ret = post( *expected, do_unpark );
[454f478]	352	__atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
	353	return ret;
	354	}
	355	}
	356
	357	}
	358
	359	// Wait for the future to be fulfilled
	360	bool wait( future_t & this ) {
	361	oneshot temp;
	362	if( !setup(this, temp) ) return false;
	363
	364	// Wait context is setup, just wait on it
	365	bool ret = wait( temp );
	366
	367	// Wait for the future to tru
	368	while( this.ptr == 2p ) Pause();
	369	// Make sure the state makes sense
	370	// Should be fulfilled, could be in progress but it's out of date if so
	371	// since if that is the case, the oneshot was fulfilled (unparking this thread)
	372	// and the oneshot should not be needed any more
	373	__attribute__((unused)) struct oneshot * was = this.ptr;
	374	/* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
	375
	376	// Mark the future as fulfilled, to be consistent
	377	// with potential calls to avail
	378	// this.ptr = 1p;
	379	return ret;
	380	}
[c06551b]	381
	382	// Wait for any future to be fulfilled
[f3da205]	383	forall(T& \| sized(T) \| { bool setup( T&, oneshot & ); bool retract( T&, oneshot & ); })
	384	T & wait_any( T * futures, size_t num_futures ) {
[c06551b]	385	oneshot temp;
	386
	387	// setup all futures
	388	// if any are already satisfied return
	389	for ( i; num_futures ) {
	390	if( !setup(futures[i], temp) ) return futures[i];
	391	}
[f3da205]	392
[c06551b]	393	// Wait context is setup, just wait on it
	394	wait( temp );
[f3da205]	395
[c06551b]	396	size_t ret;
	397	// attempt to retract all futures
	398	for ( i; num_futures ) {
	399	if ( retract( futures[i], temp ) ) ret = i;
	400	}
[f3da205]	401
[c06551b]	402	return futures[ret];
	403	}
[454f478]	404	}
	405
[3e2b9c9]	406	//-----------------------------------------------------------------------
	407	// Statics call at the end of each thread to register statistics
	408	#if !defined(__CFA_NO_STATISTICS__)
	409	static inline struct __stats_t * __tls_stats() {
[8fc652e0]	410	/* paranoid */ verify( ! __preemption_enabled() );
	411	/* paranoid */ verify( kernelTLS().this_stats );
	412	return kernelTLS().this_stats;
[3e2b9c9]	413	}
	414
	415	#define __STATS__(in_kernel, ...) { \
	416	if( !(in_kernel) ) disable_interrupts(); \
	417	with( *__tls_stats() ) { \
	418	__VA_ARGS__ \
	419	} \
[a3821fa]	420	if( !(in_kernel) ) enable_interrupts(); \
[3e2b9c9]	421	}
[c9c1c1c]	422	#if defined(CFA_HAVE_LINUX_IO_URING_H)
	423	#define __IO_STATS__(in_kernel, ...) { \
	424	if( !(in_kernel) ) disable_interrupts(); \
	425	with( *__tls_stats() ) { \
	426	__VA_ARGS__ \
	427	} \
	428	if( !(in_kernel) ) enable_interrupts(); \
	429	}
	430	#else
	431	#define __IO_STATS__(in_kernel, ...)
	432	#endif
[3e2b9c9]	433	#else
	434	#define __STATS__(in_kernel, ...)
[c9c1c1c]	435	#define __IO_STATS__(in_kernel, ...)
[3e2b9c9]	436	#endif
	437	}
[e660761]	438	}
[442b624]	439	#endif

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

Download in other formats:

Original Format