Context Navigation

locks.hfa @ cdacb73

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

Last change on this file since cdacb73 was e235429, checked in by Thierry Delisle <tdelisle@…>, 4 years ago
Removed last parker/unparker information is it was not particularly useful
Property mode set to `100644`
File size: 11.9 KB

Rev	Line
[ea7d2b0]	1	//
	2	// Cforall Version 1.0.0 Copyright (C) 2016 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	//
[73abe95]	7	// bits/locks.hfa -- Fast internal locks.
[ea7d2b0]	8	//
	9	// Author : Thierry Delisle
	10	// Created On : Tue Oct 31 15:14:38 2017
[b158d8f]	11	// Last Modified By : Peter A. Buhr
[fd9b524]	12	// Last Modified On : Wed Aug 12 14:18:07 2020
	13	// Update Count : 13
[ea7d2b0]	14	//
	15
	16	#pragma once
	17
[73abe95]	18	#include "bits/debug.hfa"
	19	#include "bits/defs.hfa"
[ea8b2f7]	20	#include <assert.h>
	21
	22	#ifdef __cforall
	23	extern "C" {
	24	#include <pthread.h>
	25	}
	26	#endif
[ea7d2b0]	27
	28	// pause to prevent excess processor bus usage
[fd9b524]	29	#if defined( __i386 ) \|\| defined( __x86_64 )
[ea7d2b0]	30	#define Pause() __asm__ __volatile__ ( "pause" : : : )
[b158d8f]	31	#elif defined( __ARM_ARCH )
[fd9b524]	32	#define Pause() __asm__ __volatile__ ( "YIELD" : : : )
[ea7d2b0]	33	#else
	34	#error unsupported architecture
	35	#endif
	36
	37	struct __spinlock_t {
[13073be]	38	// Wrap in struct to prevent false sharing with debug info
[3aeee3c]	39	volatile bool lock;
[ea7d2b0]	40	#ifdef __CFA_DEBUG__
[13073be]	41	// previous function to acquire the lock
[ea7d2b0]	42	const char * prev_name;
[13073be]	43	// previous thread to acquire the lock
[ea7d2b0]	44	void* prev_thrd;
	45	#endif
[3aeee3c]	46	};
[ea7d2b0]	47
[0cf5b79]	48	#ifdef __cforall
[dbe9b08]	49	extern "C" {
[2026bb6]	50	extern void disable_interrupts() OPTIONAL_THREAD;
	51	extern void enable_interrupts_noPoll() OPTIONAL_THREAD;
[1997b4e]	52
	53	#ifdef __CFA_DEBUG__
[ae66348]	54	void __cfaabi_dbg_record_lock(__spinlock_t & this, const char prev_name[]);
[1997b4e]	55	#else
[ae66348]	56	#define __cfaabi_dbg_record_lock(x, y)
[1997b4e]	57	#endif
[dbe9b08]	58	}
	59
[ea7d2b0]	60	static inline void ?{}( __spinlock_t & this ) {
	61	this.lock = 0;
	62	}
	63
	64	// Lock the spinlock, return false if already acquired
[93c2e0a]	65	static inline bool try_lock ( __spinlock_t & this __cfaabi_dbg_ctx_param2 ) {
[3381ed7]	66	disable_interrupts();
[93c2e0a]	67	bool result = (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0);
[dbe9b08]	68	if( result ) {
[ae66348]	69	__cfaabi_dbg_record_lock( this, caller );
[3381ed7]	70	} else {
	71	enable_interrupts_noPoll();
[dbe9b08]	72	}
[ea7d2b0]	73	return result;
	74	}
	75
	76	// Lock the spinlock, spin if already acquired
[36982fc]	77	static inline void lock( __spinlock_t & this __cfaabi_dbg_ctx_param2 ) {
[ea7d2b0]	78	#ifndef NOEXPBACK
	79	enum { SPIN_START = 4, SPIN_END = 64 * 1024, };
	80	unsigned int spin = SPIN_START;
	81	#endif
	82
[3381ed7]	83	disable_interrupts();
[ea7d2b0]	84	for ( unsigned int i = 1;; i += 1 ) {
[13073be]	85	if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break;
[ea7d2b0]	86	#ifndef NOEXPBACK
	87	// exponential spin
	88	for ( volatile unsigned int s = 0; s < spin; s += 1 ) Pause();
	89
	90	// slowly increase by powers of 2
	91	if ( i % 64 == 0 ) spin += spin;
	92
	93	// prevent overflow
	94	if ( spin > SPIN_END ) spin = SPIN_START;
	95	#else
	96	Pause();
	97	#endif
	98	}
[ae66348]	99	__cfaabi_dbg_record_lock( this, caller );
[ea7d2b0]	100	}
	101
	102	static inline void unlock( __spinlock_t & this ) {
[13073be]	103	__atomic_clear( &this.lock, __ATOMIC_RELEASE );
[3381ed7]	104	enable_interrupts_noPoll();
[ea7d2b0]	105	}
[ea8b2f7]	106
	107
	108	#ifdef __CFA_WITH_VERIFY__
	109	extern bool __cfaabi_dbg_in_kernel();
	110	#endif
	111
[c66f6cb]	112	extern "C" {
	113	char * strerror(int);
	114	}
[6ec07e5]	115	#define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }
[c66f6cb]	116
[ea8b2f7]	117	struct __bin_sem_t {
[85b1deb]	118	pthread_mutex_t lock;
	119	pthread_cond_t cond;
[4069faad]	120	int val;
[ea8b2f7]	121	};
	122
	123	static inline void ?{}(__bin_sem_t & this) with( this ) {
[c66f6cb]	124	// Create the mutex with error checking
	125	pthread_mutexattr_t mattr;
	126	pthread_mutexattr_init( &mattr );
	127	pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP);
	128	pthread_mutex_init(&lock, &mattr);
	129
[b81fd95]	130	pthread_cond_init (&cond, (const pthread_condattr_t *)0p); // workaround trac#208: cast should not be required
[4069faad]	131	val = 0;
[ea8b2f7]	132	}
	133
	134	static inline void ^?{}(__bin_sem_t & this) with( this ) {
[c66f6cb]	135	CHECKED( pthread_mutex_destroy(&lock) );
	136	CHECKED( pthread_cond_destroy (&cond) );
[ea8b2f7]	137	}
	138
	139	static inline void wait(__bin_sem_t & this) with( this ) {
	140	verify(__cfaabi_dbg_in_kernel());
[c66f6cb]	141	CHECKED( pthread_mutex_lock(&lock) );
[4069faad]	142	while(val < 1) {
[85b1deb]	143	pthread_cond_wait(&cond, &lock);
	144	}
[4069faad]	145	val -= 1;
[c66f6cb]	146	CHECKED( pthread_mutex_unlock(&lock) );
[ea8b2f7]	147	}
	148
[92e7631]	149	static inline bool post(__bin_sem_t & this) with( this ) {
[4069faad]	150	bool needs_signal = false;
	151
[c66f6cb]	152	CHECKED( pthread_mutex_lock(&lock) );
[4069faad]	153	if(val < 1) {
	154	val += 1;
	155	pthread_cond_signal(&cond);
	156	needs_signal = true;
	157	}
[c66f6cb]	158	CHECKED( pthread_mutex_unlock(&lock) );
[85b1deb]	159
[92e7631]	160	return needs_signal;
[85b1deb]	161	}
[c66f6cb]	162
	163	#undef CHECKED
[e0f93e0]	164
	165	struct $thread;
[e235429]	166	extern void park( void );
	167	extern void unpark( struct $thread * this );
[e0f93e0]	168	static inline struct $thread * active_thread ();
	169
	170	// Semaphore which only supports a single thread
	171	struct single_sem {
	172	struct $thread * volatile ptr;
	173	};
	174
	175	static inline {
	176	void ?{}(single_sem & this) {
	177	this.ptr = 0p;
	178	}
	179
	180	void ^?{}(single_sem & this) {}
	181
	182	bool wait(single_sem & this) {
	183	for() {
	184	struct $thread * expected = this.ptr;
	185	if(expected == 1p) {
	186	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	187	return false;
	188	}
	189	}
	190	else {
	191	/* paranoid */ verify( expected == 0p );
	192	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
[e235429]	193	park();
[e0f93e0]	194	return true;
	195	}
	196	}
	197
	198	}
	199	}
	200
	201	bool post(single_sem & this) {
	202	for() {
	203	struct $thread * expected = this.ptr;
	204	if(expected == 1p) return false;
	205	if(expected == 0p) {
	206	if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	207	return false;
	208	}
	209	}
	210	else {
	211	if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
[e235429]	212	unpark( expected );
[e0f93e0]	213	return true;
	214	}
	215	}
	216	}
	217	}
	218	}
[b353a49]	219
[a77496cb]	220	// Synchronozation primitive which only supports a single thread and one post
	221	// Similar to a binary semaphore with a 'one shot' semantic
	222	// is expected to be discarded after each party call their side
[b353a49]	223	struct oneshot {
[a77496cb]	224	// Internal state :
	225	// 0p : is initial state (wait will block)
	226	// 1p : fulfilled (wait won't block)
	227	// any thread : a thread is currently waiting
[b353a49]	228	struct $thread * volatile ptr;
	229	};
	230
	231	static inline {
	232	void ?{}(oneshot & this) {
	233	this.ptr = 0p;
	234	}
	235
	236	void ^?{}(oneshot & this) {}
	237
[a77496cb]	238	// Wait for the post, return immidiately if it already happened.
	239	// return true if the thread was parked
[b353a49]	240	bool wait(oneshot & this) {
	241	for() {
	242	struct $thread * expected = this.ptr;
	243	if(expected == 1p) return false;
	244	/* paranoid */ verify( expected == 0p );
	245	if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
[e235429]	246	park();
[b353a49]	247	/* paranoid */ verify( this.ptr == 1p );
	248	return true;
	249	}
	250	}
	251	}
	252
[a77496cb]	253	// Mark as fulfilled, wake thread if needed
	254	// return true if a thread was unparked
[b353a49]	255	bool post(oneshot & this) {
	256	struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
	257	if( got == 0p ) return false;
[e235429]	258	unpark( got );
[b353a49]	259	return true;
	260	}
	261	}
[a77496cb]	262
	263	// base types for future to build upon
	264	// It is based on the 'oneshot' type to allow multiple futures
	265	// to block on the same instance, permitting users to block a single
	266	// thread on "any of" [a given set of] futures.
	267	// does not support multiple threads waiting on the same future
	268	struct future_t {
	269	// Internal state :
	270	// 0p : is initial state (wait will block)
	271	// 1p : fulfilled (wait won't block)
	272	// 2p : in progress ()
	273	// 3p : abandoned, server should delete
	274	// any oneshot : a context has been setup to wait, a thread could wait on it
	275	struct oneshot * volatile ptr;
	276	};
	277
	278	static inline {
	279	void ?{}(future_t & this) {
	280	this.ptr = 0p;
	281	}
	282
	283	void ^?{}(future_t & this) {}
	284
	285	// check if the future is available
	286	bool available( future_t & this ) {
	287	return this.ptr == 1p;
	288	}
	289
	290	// Prepare the future to be waited on
	291	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
	292	bool setup( future_t & this, oneshot & wait_ctx ) {
	293	/* paranoid */ verify( wait_ctx.ptr == 0p );
	294	// The future needs to set the wait context
	295	for() {
	296	struct oneshot * expected = this.ptr;
	297	// Is the future already fulfilled?
	298	if(expected == 1p) return false; // Yes, just return false (didn't block)
	299
	300	// The future is not fulfilled, try to setup the wait context
	301	/* paranoid */ verify( expected == 0p );
	302	if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	303	return true;
	304	}
	305	}
	306	}
	307
	308	// Stop waiting on a future
	309	// When multiple futures are waited for together in "any of" pattern
	310	// futures that weren't fulfilled before the thread woke up
	311	// should retract the wait ctx
	312	// intented to be use by wait, wait_any, waitfor, etc. rather than used directly
	313	void retract( future_t & this, oneshot & wait_ctx ) {
	314	// Remove the wait context
	315	struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
	316
	317	// got == 0p: future was never actually setup, just return
	318	if( got == 0p ) return;
	319
	320	// got == wait_ctx: since fulfil does an atomic_swap,
	321	// if we got back the original then no one else saw context
	322	// It is safe to delete (which could happen after the return)
	323	if( got == &wait_ctx ) return;
	324
	325	// got == 1p: the future is ready and the context was fully consumed
	326	// the server won't use the pointer again
	327	// It is safe to delete (which could happen after the return)
	328	if( got == 1p ) return;
	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	return;
	335	}
	336
	337	// got == any thing else, something wen't wrong here, abort
	338	abort("Future in unexpected state");
	339	}
	340
	341	// Mark the future as abandoned, meaning it will be deleted by the server
	342	void abandon( future_t & this ) {
	343	struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
	344
	345	// got == 2p: the future is ready but the context hasn't fully been consumed
	346	// spin until it is safe to move on
	347	if( got == 2p ) {
	348	while( this.ptr != 1p ) Pause();
	349	}
	350	return;
	351	}
	352
	353	// from the server side, mark the future as fulfilled
	354	// delete it if needed
	355	bool fulfil( future_t & this ) {
	356	for() {
	357	struct oneshot * expected = this.ptr;
	358	// was this abandoned?
[ace2e92]	359	#if defined(__GNUC__) && __GNUC__ >= 7
	360	#pragma GCC diagnostic push
	361	#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
	362	#endif
	363	if( expected == 3p ) { free( &this ); return false; }
	364	#if defined(__GNUC__) && __GNUC__ >= 7
	365	#pragma GCC diagnostic pop
	366	#endif
[a77496cb]	367
	368	/* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
	369	/* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
	370
	371	// If there is a wait context, we need to consume it and mark it as consumed after
	372	// If there is no context then we can skip the in progress phase
	373	struct oneshot * want = expected == 0p ? 1p : 2p;
	374	if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
	375	if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return false; }
	376	bool ret = post( *expected );
	377	__atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
	378	return ret;
	379	}
	380	}
	381
	382	}
	383
	384	// Wait for the future to be fulfilled
	385	bool wait( future_t & this ) {
	386	oneshot temp;
	387	if( !setup(this, temp) ) return false;
	388
	389	// Wait context is setup, just wait on it
	390	bool ret = wait( temp );
	391
	392	// Wait for the future to tru
	393	while( this.ptr == 2p ) Pause();
	394	// Make sure the state makes sense
	395	// Should be fulfilled, could be in progress but it's out of date if so
	396	// since if that is the case, the oneshot was fulfilled (unparking this thread)
	397	// and the oneshot should not be needed any more
	398	__attribute__((unused)) struct oneshot * was = this.ptr;
	399	/* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
	400
	401	// Mark the future as fulfilled, to be consistent
	402	// with potential calls to avail
	403	// this.ptr = 1p;
	404	return ret;
	405	}
	406	}
[b158d8f]	407	#endif

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

Download in other formats:

Original Format