// // Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo // // The contents of this file are covered under the licence agreement in the // file "LICENCE" distributed with Cforall. // // locks.hfa -- PUBLIC // Runtime locks that used with the runtime thread system. // // Author : Colby Alexander Parsons // Created On : Thu Jan 21 19:46:50 2021 // Last Modified By : Peter A. Buhr // Last Modified On : Tue Dec 24 09:36:52 2024 // Update Count : 16 // #pragma once #include #include #include "bits/weakso_locks.hfa" #include "collections/lockfree.hfa" #include "collections/list.hfa" #include "limits.hfa" #include "thread.hfa" #include "time_t.hfa" #include "time.hfa" #include "select.hfa" // futex headers #include // Definition of FUTEX_* constants #include // Definition of SYS_* constants #include // Definition of syscall routine typedef void (*__cfa_pre_park)( void * ); static inline void pre_park_noop( void * ) {} //----------------------------------------------------------------------------- // is_blocking_lock forall( L & /*| sized( L )*/ ) trait is_blocking_lock { // For synchronization locks to use when acquiring void on_notify( L &, struct thread$ * ); // For synchronization locks to use when releasing size_t on_wait( L &, __cfa_pre_park pp_fn, void * pp_datum ); // to set recursion count after getting signalled; void on_wakeup( L &, size_t recursion ); }; static inline void pre_park_then_park( __cfa_pre_park pp_fn, void * pp_datum ) { pp_fn( pp_datum ); park(); } // macros for default routine impls for is_blocking_lock trait that do not wait-morph #define DEFAULT_ON_NOTIFY( lock_type ) \ static inline void on_notify( lock_type & /*this*/, thread$ * t ){ unpark( t ); } #define DEFAULT_ON_WAIT( lock_type ) \ static inline size_t on_wait( lock_type & this, __cfa_pre_park pp_fn, void * pp_datum ) { \ unlock( this ); \ pre_park_then_park( pp_fn, pp_datum ); \ return 0; \ } // on_wakeup impl if lock should be reacquired after waking up #define DEFAULT_ON_WAKEUP_REACQ( lock_type ) \ static inline void on_wakeup( lock_type & this, size_t /*recursion*/ ) { lock( this ); } // on_wakeup impl if lock will not be reacquired after waking up #define DEFAULT_ON_WAKEUP_NO_REACQ( lock_type ) \ static inline void on_wakeup( lock_type & /*this*/, size_t /*recursion*/ ) {} //----------------------------------------------------------------------------- // Semaphore struct semaphore { __spinlock_t lock; int count; __queue_t( thread$) waiting; }; void ?{}( semaphore & this, int count = 1 ); void ^?{}( semaphore & this ); bool P( semaphore & this ); bool V( semaphore & this ); bool V( semaphore & this, unsigned count ); thread$ * V( semaphore & this, bool ); //---------- struct single_acquisition_lock { inline blocking_lock; }; static inline void ?{}( single_acquisition_lock & this ) { ((blocking_lock &)this){ false, false }; } static inline void ^?{}( single_acquisition_lock & this ) {} static inline void lock( single_acquisition_lock & this ) { lock( (blocking_lock &)this ); } static inline bool try_lock( single_acquisition_lock & this ) { return try_lock( (blocking_lock &)this ); } static inline void unlock( single_acquisition_lock & this ) { unlock( (blocking_lock &)this ); } static inline size_t on_wait( single_acquisition_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) { return on_wait ( (blocking_lock &)this, pp_fn, pp_datum ); } static inline void on_wakeup( single_acquisition_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); } static inline void on_notify( single_acquisition_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); } static inline bool register_select( single_acquisition_lock & this, select_node & node ) { return register_select( (blocking_lock &)this, node ); } static inline bool unregister_select( single_acquisition_lock & this, select_node & node ) { return unregister_select( (blocking_lock &)this, node ); } static inline bool on_selected( single_acquisition_lock & this, select_node & node ) { return on_selected( (blocking_lock &)this, node ); } __CFA_SELECT_GET_TYPE( single_acquisition_lock ); //---------- struct owner_lock { inline blocking_lock; }; static inline void ?{}( owner_lock & this ) { ((blocking_lock &)this){ true, true }; } static inline void ^?{}( owner_lock & this ) {} static inline void lock( owner_lock & this ) { lock( (blocking_lock &)this ); } static inline bool try_lock( owner_lock & this ) { return try_lock( (blocking_lock &)this ); } static inline void unlock( owner_lock & this ) { unlock( (blocking_lock &)this ); } static inline size_t on_wait( owner_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) { return on_wait ( (blocking_lock &)this, pp_fn, pp_datum ); } static inline void on_wakeup( owner_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); } static inline void on_notify( owner_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); } static inline bool register_select( owner_lock & this, select_node & node ) { return register_select( (blocking_lock &)this, node ); } static inline bool unregister_select( owner_lock & this, select_node & node ) { return unregister_select( (blocking_lock &)this, node ); } static inline bool on_selected( owner_lock & this, select_node & node ) { return on_selected( (blocking_lock &)this, node ); } __CFA_SELECT_GET_TYPE( owner_lock ); //----------------------------------------------------------------------------- // MCS Lock struct mcs_node { mcs_node * volatile next; single_sem sem; }; static inline void ?{}( mcs_node & this ) { this.next = 0p; } static inline mcs_node * volatile & ?`next ( mcs_node * node ) { return node->next; } struct mcs_lock { mcs_queue( mcs_node ) queue; }; static inline void lock( mcs_lock & l, mcs_node & n ) { if ( push( l.queue, &n ) ) wait( n.sem ); } static inline void unlock( mcs_lock & l, mcs_node & n ) { mcs_node * next = advance( l.queue, &n ); if ( next ) post( next->sem ); } //----------------------------------------------------------------------------- // MCS Spin Lock // - No recursive acquisition // - Needs to be released by owner struct mcs_spin_node { mcs_spin_node * volatile next; volatile bool locked; }; struct mcs_spin_queue { mcs_spin_node * volatile tail; }; static inline void ?{}( mcs_spin_node & this ) { this.next = 0p; this.locked = true; } struct mcs_spin_lock { mcs_spin_queue queue; }; static inline void lock( mcs_spin_lock & l, mcs_spin_node & n ) { n.locked = true; #if defined( __ARM_ARCH ) __asm__ __volatile__ ( "DMB ISH" ::: ); #endif mcs_spin_node * prev = __atomic_exchange_n( &l.queue.tail, &n, __ATOMIC_SEQ_CST ); if ( prev == 0p ) return; prev->next = &n; #if defined( __ARM_ARCH ) __asm__ __volatile__ ( "DMB ISH" ::: ); #endif while ( __atomic_load_n( &n.locked, __ATOMIC_RELAXED ) ) Pause(); #if defined( __ARM_ARCH ) __asm__ __volatile__ ( "DMB ISH" ::: ); #endif } static inline void unlock( mcs_spin_lock & l, mcs_spin_node & n ) { #if defined( __ARM_ARCH ) __asm__ __volatile__ ( "DMB ISH" ::: ); #endif mcs_spin_node * n_ptr = &n; if ( __atomic_compare_exchange_n( &l.queue.tail, &n_ptr, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return; while ( __atomic_load_n( &n.next, __ATOMIC_RELAXED ) == 0p ) Pause(); #if defined( __ARM_ARCH ) __asm__ __volatile__ ( "DMB ISH" ::: ); #endif n.next->locked = false; } //----------------------------------------------------------------------------- // futex_mutex // - Kernel thd blocking alternative to the spinlock // - No ownership (will deadlock on reacq) // - no reacq on wakeup struct futex_mutex { // lock state any state other than UNLOCKED is locked // enum LockState { UNLOCKED = 0, UNCONTENDED = 1, CONTENDED = 2 }; // stores a lock state int val; }; // to use for FUTEX_WAKE and FUTEX_WAIT (other futex calls will need more params) static inline int futex( int *uaddr, int futex_op, int val ) { return syscall( SYS_futex, uaddr, futex_op, val, NULL, NULL, 0 ); } static inline void ?{}( futex_mutex & this ) with( this ) { val = 0; } static inline bool internal_try_lock( futex_mutex & this, int & compare_val ) with( this ) { return __atomic_compare_exchange_n( (int*)&val, (int*)&compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE ); } static inline int internal_exchange( futex_mutex & this ) with( this ) { return __atomic_exchange_n(( int*)&val, 2, __ATOMIC_ACQUIRE ); } // if this is called recursively IT WILL DEADLOCK!!!!! static inline void lock( futex_mutex & this ) with( this ) { int state; for ( spin; 4 ~ 1024 ~ spin ) { state = 0; // if unlocked, lock and return if ( internal_try_lock( this, state ) ) return; if ( state == 2 ) break; for ( spin ) Pause(); } // if not in contended state, set to be in contended state if ( state != 2 ) state = internal_exchange( this ); // block and spin until we win the lock while ( state != 0 ) { futex( (int*)&val, FUTEX_WAIT, 2 ); // if val is not 2 this returns with EWOULDBLOCK state = internal_exchange( this ); } } static inline void unlock( futex_mutex & this ) with( this ) { // if uncontended do atomic unlock and then return if ( __atomic_exchange_n( &val, 0, __ATOMIC_RELEASE ) == 1 ) return; // otherwise threads are blocked so we must wake one futex(( int *)&val, FUTEX_WAKE, 1 ); } DEFAULT_ON_NOTIFY( futex_mutex ) DEFAULT_ON_WAIT( futex_mutex ) DEFAULT_ON_WAKEUP_NO_REACQ( futex_mutex ) //----------------------------------------------------------------------------- // go_mutex // - Kernel thd blocking alternative to the spinlock // - No ownership (will deadlock on reacq) // - Golang's flavour of mutex // - Impl taken from Golang: src/runtime/lock_futex.go struct go_mutex { // lock state any state other than UNLOCKED is locked // enum LockState { UNLOCKED = 0, LOCKED = 1, SLEEPING = 2 }; // stores a lock state int val; }; static inline void ?{}( go_mutex & this ) with( this ) { val = 0; } static inline void ?{}( go_mutex & this, go_mutex this2 ) = void; static inline void ?=?( go_mutex & this, go_mutex this2 ) = void; static inline bool internal_try_lock( go_mutex & this, int & compare_val, int new_val ) with( this ) { return __atomic_compare_exchange_n( (int*)&val, (int*)&compare_val, new_val, false, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE ); } static inline int internal_exchange( go_mutex & this, int swap ) with( this ) { return __atomic_exchange_n( (int*)&val, swap, __ATOMIC_ACQUIRE ); } // if this is called recursively IT WILL DEADLOCK!!!!! static inline void lock( go_mutex & this ) with( this ) { int state, init_state; // speculative grab state = internal_exchange( this, 1 ); if ( ! state ) return; // state == 0 init_state = state; for () { for ( 4 ) { while ( ! val ) { // lock unlocked state = 0; if ( internal_try_lock( this, state, init_state ) ) return; } for ( 30 ) Pause(); } while ( ! val ) { // lock unlocked state = 0; if ( internal_try_lock( this, state, init_state ) ) return; } sched_yield(); // if not in contended state, set to be in contended state state = internal_exchange( this, 2 ); if ( ! state ) return; // state == 0 init_state = 2; futex( (int*)&val, FUTEX_WAIT, 2 ); // if val is not 2 this returns with EWOULDBLOCK } } static inline void unlock( go_mutex & this ) with( this ) { // if uncontended do atomic unlock and then return if ( __atomic_exchange_n( &val, 0, __ATOMIC_RELEASE ) == 1 ) return; // otherwise threads are blocked so we must wake one futex( (int *)&val, FUTEX_WAKE, 1 ); } DEFAULT_ON_NOTIFY( go_mutex ) DEFAULT_ON_WAIT( go_mutex ) DEFAULT_ON_WAKEUP_NO_REACQ( go_mutex ) //----------------------------------------------------------------------------- // Exponential backoff then block lock struct exp_backoff_then_block_lock { // Spin lock used for mutual exclusion __spinlock_t spinlock; // List of blocked threads dlist( thread$ ) blocked_threads; // Used for comparing and exchanging volatile size_t lock_value; }; static inline void ?{}( exp_backoff_then_block_lock & this ) { this.spinlock{}; this.blocked_threads{}; this.lock_value = 0; } static inline void ?{}( exp_backoff_then_block_lock & this, exp_backoff_then_block_lock this2 ) = void; static inline void ?=?( exp_backoff_then_block_lock & this, exp_backoff_then_block_lock this2 ) = void; static inline void ^?{}( exp_backoff_then_block_lock & this ){} static inline bool internal_try_lock( exp_backoff_then_block_lock & this, size_t & compare_val ) with( this ) { return __atomic_compare_exchange_n( &lock_value, &compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED ); } static inline bool try_lock( exp_backoff_then_block_lock & this ) { size_t compare_val = 0; return internal_try_lock( this, compare_val ); } static inline bool try_lock_contention( exp_backoff_then_block_lock & this ) with( this ) { return ! __atomic_exchange_n( &lock_value, 2, __ATOMIC_ACQUIRE ); } static inline bool block( exp_backoff_then_block_lock & this ) with( this ) { lock( spinlock __cfaabi_dbg_ctx2 ); if ( __atomic_load_n( &lock_value, __ATOMIC_SEQ_CST ) != 2 ) { unlock( spinlock ); return true; } insert_last( blocked_threads, *active_thread() ); unlock( spinlock ); park( ); return true; } static inline void lock( exp_backoff_then_block_lock & this ) with( this ) { size_t compare_val = 0; int spin = 4; // linear backoff for () { compare_val = 0; if ( internal_try_lock( this, compare_val ) ) return; if ( compare_val == 2 ) break; for ( spin ) Pause(); if ( spin >= 1024 ) break; spin += spin; } if ( 2 != compare_val && try_lock_contention( this ) ) return; // block until signalled while ( block( this ) ) if ( try_lock_contention( this ) ) return; } static inline void unlock( exp_backoff_then_block_lock & this ) with( this ) { if ( __atomic_exchange_n( &lock_value, 0, __ATOMIC_RELEASE ) == 1 ) return; lock( spinlock __cfaabi_dbg_ctx2 ); thread$ * t = &try_pop_front( blocked_threads ); unlock( spinlock ); unpark( t ); } DEFAULT_ON_NOTIFY( exp_backoff_then_block_lock ) DEFAULT_ON_WAIT( exp_backoff_then_block_lock ) DEFAULT_ON_WAKEUP_REACQ( exp_backoff_then_block_lock ) //----------------------------------------------------------------------------- // Fast Block Lock // minimal blocking lock // - No reacquire for cond var // - No recursive acquisition // - No ownership struct fast_block_lock { // List of blocked threads dlist( thread$ ) blocked_threads; // Spin lock used for mutual exclusion __spinlock_t lock; // flag showing if lock is held bool held:1; }; static inline void ?{}( fast_block_lock & this ) with( this ) { lock{}; blocked_threads{}; held = false; } static inline void ^?{}( fast_block_lock & this ) {} static inline void ?{}( fast_block_lock & this, fast_block_lock this2 ) = void; static inline void ?=?( fast_block_lock & this, fast_block_lock this2 ) = void; // if this is called recursively IT WILL DEADLOCK!!!!! static inline void lock( fast_block_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); if ( held ) { insert_last( blocked_threads, *active_thread() ); unlock( lock ); park( ); return; } held = true; unlock( lock ); } static inline void unlock( fast_block_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); /* paranoid */ verifyf( held != false, "Attempt to release lock %p that isn't held", &this ); thread$ * t = &try_pop_front( blocked_threads ); held = ( t ? true : false ); unpark( t ); unlock( lock ); } static inline void on_notify( fast_block_lock & this, struct thread$ * t ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); insert_last( blocked_threads, *t ); unlock( lock ); } DEFAULT_ON_WAIT( fast_block_lock ) DEFAULT_ON_WAKEUP_NO_REACQ( fast_block_lock ) //----------------------------------------------------------------------------- // simple_owner_lock // pthread owner lock // - reacquire for cond var // - recursive acquisition // - ownership struct simple_owner_lock { // List of blocked threads dlist( select_node ) blocked_threads; // Spin lock used for mutual exclusion __spinlock_t lock; // owner showing if lock is held struct thread$ * owner; size_t recursion_count; }; static inline void ?{}( simple_owner_lock & this ) with( this ) { lock{}; blocked_threads{}; owner = 0p; recursion_count = 0; } static inline void ^?{}( simple_owner_lock & this ) {} static inline void ?{}( simple_owner_lock & this, simple_owner_lock this2 ) = void; static inline void ?=?( simple_owner_lock & this, simple_owner_lock this2 ) = void; static inline void lock( simple_owner_lock & this ) with( this ) { if ( owner == active_thread() ) { recursion_count++; return; } lock( lock __cfaabi_dbg_ctx2 ); if ( owner != 0p ) { select_node node; insert_last( blocked_threads, node ); unlock( lock ); park( ); return; } owner = active_thread(); recursion_count = 1; unlock( lock ); } static inline void pop_node( simple_owner_lock & this ) with( this ) { __handle_waituntil_OR( blocked_threads ); select_node * node = &try_pop_front( blocked_threads ); if ( node ) { owner = node->blocked_thread; recursion_count = 1; // if ( ! node->clause_status || __make_select_node_available( *node ) ) unpark( node->blocked_thread ); wake_one( blocked_threads, *node ); } else { owner = 0p; recursion_count = 0; } } static inline void unlock( simple_owner_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this ); /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this ); // if recursion count is zero release lock and set new owner if one is waiting recursion_count--; if ( recursion_count == 0 ) { pop_node( this ); } unlock( lock ); } static inline void on_notify( simple_owner_lock & this, thread$ * t ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); // lock held if ( owner != 0p ) { insert_last( blocked_threads, *(select_node *)t->link_node ); } // lock not held else { owner = t; recursion_count = 1; unpark( t ); } unlock( lock ); } static inline size_t on_wait( simple_owner_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this ); /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this ); size_t ret = recursion_count; pop_node( this ); select_node node; active_thread()->link_node = (void *)&node; unlock( lock ); pre_park_then_park( pp_fn, pp_datum ); return ret; } static inline void on_wakeup( simple_owner_lock & this, size_t recursion ) with( this ) { recursion_count = recursion; } // waituntil() support static inline bool register_select( simple_owner_lock & this, select_node & node ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); // check if we can complete operation. If so race to establish winner in special OR case if ( ! node.park_counter && ( owner == active_thread() || owner == 0p ) ) { if ( ! __make_select_node_available( node ) ) { // we didn't win the race so give up on registering unlock( lock ); return false; } } if ( owner == active_thread() ) { recursion_count++; if ( node.park_counter ) __make_select_node_available( node ); unlock( lock ); return true; } if ( owner != 0p ) { insert_last( blocked_threads, node ); unlock( lock ); return false; } owner = active_thread(); recursion_count = 1; if ( node.park_counter ) __make_select_node_available( node ); unlock( lock ); return true; } static inline bool unregister_select( simple_owner_lock & this, select_node & node ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); if ( node`isListed ) { remove( node ); unlock( lock ); return false; } if ( owner == active_thread() ) { recursion_count--; if ( recursion_count == 0 ) { pop_node( this ); } } unlock( lock ); return false; } static inline bool on_selected( simple_owner_lock & /*this*/, select_node & /*node*/ ) { return true; } __CFA_SELECT_GET_TYPE( simple_owner_lock ); //----------------------------------------------------------------------------- // Spin Queue Lock // - No reacquire for cond var // - No recursive acquisition // - No ownership // - spin lock with no locking/atomics in unlock struct spin_queue_lock { // Spin lock used for mutual exclusion mcs_spin_lock lock; // flag showing if lock is held volatile bool held; }; static inline void ?{}( spin_queue_lock & this ) with( this ) { lock{}; held = false; } static inline void ^?{}( spin_queue_lock & this ) {} static inline void ?{}( spin_queue_lock & this, spin_queue_lock this2 ) = void; static inline void ?=?( spin_queue_lock & this, spin_queue_lock this2 ) = void; // if this is called recursively IT WILL DEADLOCK! static inline void lock( spin_queue_lock & this ) with( this ) { mcs_spin_node node; lock( lock, node ); while ( __atomic_load_n( &held, __ATOMIC_SEQ_CST ) ) Pause(); __atomic_store_n( &held, true, __ATOMIC_SEQ_CST ); unlock( lock, node ); } static inline void unlock( spin_queue_lock & this ) with( this ) { __atomic_store_n( &held, false, __ATOMIC_RELEASE ); } DEFAULT_ON_NOTIFY( spin_queue_lock ) DEFAULT_ON_WAIT( spin_queue_lock ) DEFAULT_ON_WAKEUP_REACQ( spin_queue_lock ) //----------------------------------------------------------------------------- // MCS Block Spin Lock // - No reacquire for cond var // - No recursive acquisition // - No ownership // - Blocks but first node spins (like spin queue but blocking for not first thd) struct mcs_block_spin_lock { // Spin lock used for mutual exclusion mcs_lock lock; // flag showing if lock is held volatile bool held; }; static inline void ?{}( mcs_block_spin_lock & this ) with( this ) { lock{}; held = false; } static inline void ^?{}( mcs_block_spin_lock & this ) {} static inline void ?{}( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void; static inline void ?=?( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void; // if this is called recursively IT WILL DEADLOCK!!!!! static inline void lock( mcs_block_spin_lock & this ) with( this ) { mcs_node node; lock( lock, node ); while ( __atomic_load_n( &held, __ATOMIC_SEQ_CST ) ) Pause(); __atomic_store_n( &held, true, __ATOMIC_SEQ_CST ); unlock( lock, node ); } static inline void unlock( mcs_block_spin_lock & this ) with( this ) { __atomic_store_n( &held, false, __ATOMIC_SEQ_CST ); } DEFAULT_ON_NOTIFY( mcs_block_spin_lock ) DEFAULT_ON_WAIT( mcs_block_spin_lock ) DEFAULT_ON_WAKEUP_REACQ( mcs_block_spin_lock ) //----------------------------------------------------------------------------- // Block Spin Lock // - No reacquire for cond var // - No recursive acquisition // - No ownership // - Blocks but first node spins (like spin queue but blocking for not first thd) struct block_spin_lock { // Spin lock used for mutual exclusion fast_block_lock lock; // flag showing if lock is held volatile bool held; }; static inline void ?{}( block_spin_lock & this ) with( this ) { lock{}; held = false; } static inline void ^?{}( block_spin_lock & this ) {} static inline void ?{}( block_spin_lock & this, block_spin_lock this2 ) = void; static inline void ?=?( block_spin_lock & this, block_spin_lock this2 ) = void; // if this is called recursively IT WILL DEADLOCK!!!!! static inline void lock( block_spin_lock & this ) with( this ) { lock( lock ); while ( __atomic_load_n( &held, __ATOMIC_SEQ_CST ) ) Pause(); __atomic_store_n( &held, true, __ATOMIC_RELEASE ); unlock( lock ); } static inline void unlock( block_spin_lock & this ) with( this ) { __atomic_store_n( &held, false, __ATOMIC_RELEASE ); } static inline void on_notify( block_spin_lock & this, struct thread$ * t ) with( this.lock ) { // first we acquire internal fast_block_lock lock( lock __cfaabi_dbg_ctx2 ); if ( held ) { // if internal fast_block_lock is held insert_last( blocked_threads, *t ); unlock( lock ); return; } // if internal fast_block_lock is not held held = true; unlock( lock ); unpark( t ); } DEFAULT_ON_WAIT( block_spin_lock ) static inline void on_wakeup( block_spin_lock & this, size_t /*recursion*/ ) with( this ) { // now we acquire the entire block_spin_lock upon waking up while ( __atomic_load_n( &held, __ATOMIC_SEQ_CST ) ) Pause(); __atomic_store_n( &held, true, __ATOMIC_RELEASE ); unlock( lock ); // Now we release the internal fast_spin_lock } //----------------------------------------------------------------------------- // // info_thread // // the info thread is a wrapper around a thread used // // to store extra data for use in the condition variable forall( L & | is_blocking_lock( L ) ) { struct info_thread; } //----------------------------------------------------------------------------- // Synchronization Locks forall( L & | is_blocking_lock( L ) ) { //----------------------------------------------------------------------------- // condition_variable // The multi-tool condition variable // - can pass timeouts to wait for either a signal or timeout // - can wait without passing a lock // - can have waiters reacquire different locks while waiting on the same cond var // - has shadow queue // - can be signalled outside of critical sections with no locks held struct condition_variable { // Spin lock used for mutual exclusion __spinlock_t lock; // List of blocked threads dlist( info_thread( L ) ) blocked_threads; // Count of current blocked threads int count; }; void ?{}( condition_variable( L ) & this ); void ^?{}( condition_variable( L ) & this ); bool notify_one( condition_variable( L ) & this ); bool notify_all( condition_variable( L ) & this ); uintptr_t front( condition_variable( L ) & this ); bool empty ( condition_variable( L ) & this ); int counter( condition_variable( L ) & this ); void wait( condition_variable( L ) & this ); void wait( condition_variable( L ) & this, uintptr_t info ); bool wait( condition_variable( L ) & this, Duration duration ); bool wait( condition_variable( L ) & this, uintptr_t info, Duration duration ); void wait( condition_variable( L ) & this, L & l ); void wait( condition_variable( L ) & this, L & l, uintptr_t info ); bool wait( condition_variable( L ) & this, L & l, Duration duration ); bool wait( condition_variable( L ) & this, L & l, uintptr_t info, Duration duration ); //----------------------------------------------------------------------------- // fast_cond_var // The trimmed and slim condition variable // - no internal lock so you must hold a lock while using this cond var // - signalling without holding branded lock is UNSAFE! // - only allows usage of one lock, cond var is branded after usage struct fast_cond_var { // List of blocked threads dlist( info_thread( L ) ) blocked_threads; #ifdef __CFA_DEBUG__ L * lock_used; #endif }; void ?{}( fast_cond_var( L ) & this ); void ^?{}( fast_cond_var( L ) & this ); bool notify_one( fast_cond_var( L ) & this ); bool notify_all( fast_cond_var( L ) & this ); uintptr_t front( fast_cond_var( L ) & this ); bool empty ( fast_cond_var( L ) & this ); void wait( fast_cond_var( L ) & this, L & l ); void wait( fast_cond_var( L ) & this, L & l, uintptr_t info ); //----------------------------------------------------------------------------- // pthread_cond_var // // - cond var with minimal footprint // - supports operations needed for phthread cond struct pthread_cond_var { dlist( info_thread( L ) ) blocked_threads; __spinlock_t lock; }; void ?{}( pthread_cond_var( L ) & this ); void ^?{}( pthread_cond_var( L ) & this ); bool notify_one( pthread_cond_var( L ) & this ); bool notify_all( pthread_cond_var( L ) & this ); uintptr_t front( pthread_cond_var( L ) & this ); bool empty ( pthread_cond_var( L ) & this ); void wait( pthread_cond_var( L ) & this, L & l ); void wait( pthread_cond_var( L ) & this, L & l, uintptr_t info ); bool wait( pthread_cond_var( L ) & this, L & l, timespec t ); bool wait( pthread_cond_var( L ) & this, L & l, uintptr_t info, timespec t ); }