source: libcfa/src/concurrency/locks.hfa@ 15a0f6f

//
// 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 : Sat Jul  4 06:52:06 2026
// Update Count     : 70
//

#pragma once

#include <stdbool.h>
#include <stdio.h>

#include "bits/weakso_locks.hfa"
#include "bits/atomic.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 <linux/futex.h>                                                                // Definition of FUTEX_* constants
#include <sys/syscall.h>                                                                // Definition of SYS_* constants
#include <unistd.h>                                                                             // 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, counting

struct semaphore {
        ssize_t count$;                                                                          // - => # waiting threads, 0 => block, + => acquire
        __spinlock_t lock$;                                                                      // protect blocking-lock critical sections
        __queue_t( thread$ ) waiting$;                                           // waiting threads
};

void ?{}( semaphore & sem, ssize_t count = 1 );
// Return values are used for composition. Calling threads know if a thread is unblocked, which can be useful for
// debugging, performance instrumentation and other metadata tracking purposes.
bool P( semaphore & sem );
static inline bool P( semaphore & sem, uintptr_t shadow ) { active_thread()->shadow$ = shadow; return P( sem ); }
bool P( semaphore & sem, semaphore & lock );                    // atomic block and release
bool try_P( semaphore & sem );
static inline bool P( semaphore & sem, semaphore & lock, uintptr_t shadow ) { active_thread()->shadow$ = shadow; return P( sem, lock ); }
bool V( semaphore & sem );
size_t V( semaphore & sem, size_t count );
static inline uintptr_t front( semaphore & sem ) with( sem ) { // return shadow information for first waiting thread
        #ifdef __CFA_DEBUG__
        if ( waiting$ ) {                                                                       // condition queue must not be empty
                abort( "Attempt to access user data on an empty semaphore lock.\n"
                           "Possible cause is not checking if the condition lock is empty before reading stored data." );
        } // if
        #endif // __CFA_DEBUG__
        return waiting$.head->shadow$;                                          // return condition information stored with blocked task
}
static inline ssize_t counter( semaphore & sem ) with( sem ) { return count$; } // - => # waiting threads, 0 => block, + => acquire
//static inline int ?!=?( semaphore & sem, zero_t ) with( sem ) { return count$ != 0; } // empty waiting queue
static inline bool empty( semaphore & sem ) with( sem ) { return count$ == 0; } // empty waiting queue


//----------
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 * nxt = advance( l.queue, &n );
        if ( nxt ) post( nxt->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_val = __atomic_exchange_n( &l.queue.tail, &n, __ATOMIC_SEQ_CST );
        if ( prev_val == 0p ) return;
        prev_val->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 = &remove_first( 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 = &remove_first( 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 = &remove_first( 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 ( listed( node ) ) {
                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 ) ) {

        //-----------------------------------------------------------------------------
        // cond_lock

        // 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 cond_lock {
                // 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 ?{}( cond_lock( L ) & this );
        void ^?{}( cond_lock( L ) & this );

        bool notify_one( cond_lock( L ) & this );
        bool notify_all( cond_lock( L ) & this );

        uintptr_t front( cond_lock( L ) & this );

        bool empty  ( cond_lock( L ) & this );
        int  counter( cond_lock( L ) & this );

        void wait( cond_lock( L ) & this );
        void wait( cond_lock( L ) & this, uintptr_t info );
        bool wait( cond_lock( L ) & this, Duration duration );
        bool wait( cond_lock( L ) & this, uintptr_t info, Duration duration );

        void wait( cond_lock( L ) & this, L & l );
        void wait( cond_lock( L ) & this, L & l, uintptr_t info );
        bool wait( cond_lock( L ) & this, L & l, Duration duration );
        bool wait( cond_lock( 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 );
}