Changeset eb5962a for libcfa/src

Timestamp:

Jun 21, 2022, 1:39:24 PM (3 years ago)

Author:

JiadaL <j82liang@…>

Branches:

ADT, ast-experimental, master, pthread-emulation, qualifiedEnum

Children:

b62d1d6

Parents:

1df492a (diff), 1dbbef6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

libcfa/src

Files:

• bits/locks.hfa (modified) (3 diffs)
• concurrency/invoke.h (modified) (3 diffs)
• concurrency/io.cfa (modified) (1 diff)
• concurrency/io/setup.cfa (modified) (1 diff)
• concurrency/iofwd.hfa (modified) (1 diff)
• concurrency/kernel.cfa (modified) (1 diff)
• concurrency/kernel/fwd.hfa (modified) (5 diffs)
• concurrency/locks.cfa (modified) (2 diffs)
• concurrency/locks.hfa (modified) (9 diffs)
• concurrency/thread.cfa (modified) (2 diffs)
• containers/queueLockFree.hfa (modified) (1 diff)
• startup.cfa (modified) (1 diff)

libcfa/src/bits/locks.hfa

@@ -26 +26 @@
         // Wrap in struct to prevent false sharing with debug info
         volatile bool lock;
-        #ifdef __CFA_DEBUG__
-                // previous function to acquire the lock
-                const char * prev_name;
-                // previous thread to acquire the lock
-                void* prev_thrd;
-                // keep track of number of times we had to spin, just in case the number is unexpectedly huge
-                size_t spin_count;
-        #endif
 };
 
@@ -40 +32 @@
                 extern void disable_interrupts() OPTIONAL_THREAD;
                 extern void enable_interrupts( bool poll = true ) OPTIONAL_THREAD;
-
-                #ifdef __CFA_DEBUG__
-                        void __cfaabi_dbg_record_lock(__spinlock_t & this, const char prev_name[]);
-                #else
-                        #define __cfaabi_dbg_record_lock(x, y)
-                #endif
+                #define __cfaabi_dbg_record_lock(x, y)
         }
 
         static inline void ?{}( __spinlock_t & this ) {
                 this.lock = 0;
-                #ifdef __CFA_DEBUG__
-                        this.spin_count = 0;
-                #endif
         }
 
@@ -77 +61 @@
                 for ( unsigned int i = 1;; i += 1 ) {
                         if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break;
-                        #ifdef __CFA_DEBUG__
-                                this.spin_count++;
-                        #endif
                         #ifndef NOEXPBACK
                                 // exponential spin

libcfa/src/concurrency/invoke.h

@@ -195 +195 @@
                 struct __monitor_group_t monitors;
 
-                // used to put threads on user data structures
-                struct {
-                        struct thread$ * next;
-                        struct thread$ * back;
-                } seqable;
-
                 // used to put threads on dlist data structure
                 __cfa_dlink(thread$);
@@ -208 +202 @@
                         struct thread$ * prev;
                 } node;
+
+                // used to store state between clh lock/unlock
+                volatile bool * clh_prev;
+
+                // used to point to this thd's current clh node
+                volatile bool * clh_node;
 
                 struct processor * last_proc;
@@ -240 +240 @@
                 }
 
-                static inline thread$ * volatile & ?`next ( thread$ * this )  __attribute__((const)) {
-                        return this->seqable.next;
-                }
-
-                static inline thread$ *& Back( thread$ * this ) __attribute__((const)) {
-                        return this->seqable.back;
-                }
-
-                static inline thread$ *& Next( thread$ * this ) __attribute__((const)) {
-                                return this->seqable.next;
-                }
-
-                static inline bool listed( thread$ * this ) {
-                        return this->seqable.next != 0p;
-                }
-
                 static inline void ?{}(__monitor_group_t & this) {
                         (this.data){0p};

libcfa/src/concurrency/io.cfa

@@ -159 +159 @@
 
                 const __u32 mask = *ctx->cq.mask;
+                const __u32 num  = *ctx->cq.num;
                 unsigned long long ts_prev = ctx->cq.ts;
-
-                // re-read the head and tail in case it already changed.
-                const __u32 head = *ctx->cq.head;
-                const __u32 tail = *ctx->cq.tail;
-                const __u32 count = tail - head;
-                __STATS__( false, io.calls.drain++; io.calls.completed += count; )
-
-                for(i; count) {
-                        unsigned idx = (head + i) & mask;
-                        volatile struct io_uring_cqe & cqe = ctx->cq.cqes[idx];
-
-                        /* paranoid */ verify(&cqe);
-
-                        struct io_future_t * future = (struct io_future_t *)(uintptr_t)cqe.user_data;
-                        // __cfadbg_print_safe( io, "Kernel I/O : Syscall completed : cqe %p, result %d for %p\n", &cqe, cqe.res, future );
-
-                        __kernel_unpark( fulfil( *future, cqe.res, false ), UNPARK_LOCAL );
-                }
-
-                unsigned long long ts_next = ctx->cq.ts = rdtscl();
-
-                // Mark to the kernel that the cqe has been seen
-                // Ensure that the kernel only sees the new value of the head index after the CQEs have been read.
-                __atomic_store_n( ctx->cq.head, head + count, __ATOMIC_SEQ_CST );
-                ctx->proc->idle_wctx.drain_time = ts_next;
+                unsigned long long ts_next;
+
+                // We might need to do this multiple times if more events completed than can fit in the queue.
+                for() {
+                        // re-read the head and tail in case it already changed.
+                        const __u32 head = *ctx->cq.head;
+                        const __u32 tail = *ctx->cq.tail;
+                        const __u32 count = tail - head;
+                        __STATS__( false, io.calls.drain++; io.calls.completed += count; )
+
+                        for(i; count) {
+                                unsigned idx = (head + i) & mask;
+                                volatile struct io_uring_cqe & cqe = ctx->cq.cqes[idx];
+
+                                /* paranoid */ verify(&cqe);
+
+                                struct io_future_t * future = (struct io_future_t *)(uintptr_t)cqe.user_data;
+                                // __cfadbg_print_safe( io, "Kernel I/O : Syscall completed : cqe %p, result %d for %p\n", &cqe, cqe.res, future );
+
+                                __kernel_unpark( fulfil( *future, cqe.res, false ), UNPARK_LOCAL );
+                        }
+
+                        ts_next = ctx->cq.ts = rdtscl();
+
+                        // Mark to the kernel that the cqe has been seen
+                        // Ensure that the kernel only sees the new value of the head index after the CQEs have been read.
+                        __atomic_store_n( ctx->cq.head, head + count, __ATOMIC_SEQ_CST );
+                        ctx->proc->idle_wctx.drain_time = ts_next;
+
+                        if(likely(count < num)) break;
+
+                        ioring_syscsll( *ctx, 0, IORING_ENTER_GETEVENTS);
+                }
 
                 __cfadbg_print_safe(io, "Kernel I/O : %u completed age %llu\n", count, ts_next);

libcfa/src/concurrency/io/setup.cfa

@@ -138 +138 @@
                 __u32 nentries = params_in.num_entries != 0 ? params_in.num_entries : 256;
                 if( !is_pow2(nentries) ) {
-                        abort("ERROR: I/O setup 'num_entries' must be a power of 2\n");
+                        abort("ERROR: I/O setup 'num_entries' must be a power of 2, was %u\n", nentries);
                 }
 

libcfa/src/concurrency/iofwd.hfa

@@ -76 +76 @@
         void reset    ( io_future_t & this ) { return reset    (this.self); }
         bool available( io_future_t & this ) { return available(this.self); }
+        bool setup    ( io_future_t & this, oneshot & ctx ) { return setup  (this.self, ctx); }
+        bool retract  ( io_future_t & this, oneshot & ctx ) { return retract(this.self, ctx); }
 }
 

libcfa/src/concurrency/kernel.cfa

@@ -834 +834 @@
 #endif
 
-
-
-//-----------------------------------------------------------------------------
-// Debug
-__cfaabi_dbg_debug_do(
-        extern "C" {
-                void __cfaabi_dbg_record_lock(__spinlock_t & this, const char prev_name[]) {
-                        this.prev_name = prev_name;
-                        this.prev_thrd = kernelTLS().this_thread;
-                }
-        }
-)
-
 //-----------------------------------------------------------------------------
 // Debug

libcfa/src/concurrency/kernel/fwd.hfa

@@ -200 +200 @@
                                         struct thread$ * expected = this.ptr;
                                         if(expected == 1p) return false;
-                                        /* paranoid */ verify( expected == 0p );
                                         if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
                                                 park();
@@ -213 +212 @@
                         thread$ * post(oneshot & this, bool do_unpark = true) {
                                 struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
-                                if( got == 0p ) return 0p;
+                                if( got == 0p || got == 1p ) return 0p;
                                 if(do_unpark) unpark( got );
                                 return got;
@@ -263 +262 @@
 
                                         // The future is not fulfilled, try to setup the wait context
-                                        /* paranoid */ verify( expected == 0p );
                                         if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
                                                 return true;
@@ -275 +273 @@
                         // should retract the wait ctx
                         // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
-                        void retract( future_t & this, oneshot & wait_ctx ) {
-                                // Remove the wait context
-                                struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
-
-                                // got == 0p: future was never actually setup, just return
-                                if( got == 0p ) return;
-
-                                // got == wait_ctx: since fulfil does an atomic_swap,
-                                // if we got back the original then no one else saw context
-                                // It is safe to delete (which could happen after the return)
-                                if( got == &wait_ctx ) return;
-
-                                // got == 1p: the future is ready and the context was fully consumed
-                                // the server won't use the pointer again
-                                // It is safe to delete (which could happen after the return)
-                                if( got == 1p ) return;
-
-                                // got == 2p: the future is ready but the context hasn't fully been consumed
-                                // spin until it is safe to move on
-                                if( got == 2p ) {
-                                        while( this.ptr != 1p ) Pause();
-                                        return;
-                                }
-
-                                // got == any thing else, something wen't wrong here, abort
-                                abort("Future in unexpected state");
+                        bool retract( future_t & this, oneshot & wait_ctx ) {
+                                for() {
+                                        struct oneshot * expected = this.ptr;
+
+                                        // expected == 0p: future was never actually setup, just return
+                                        if( expected == 0p ) return false;
+
+                                        // expected == 1p: the future is ready and the context was fully consumed
+                                        // the server won't use the pointer again
+                                        // It is safe to delete (which could happen after the return)
+                                        if( expected == 1p ) return true;
+
+                                        // expected == 2p: the future is ready but the context hasn't fully been consumed
+                                        // spin until it is safe to move on
+                                        if( expected == 2p ) {
+                                                while( this.ptr != 1p ) Pause();
+                                                /* paranoid */ verify( this.ptr == 1p );
+                                                return true;
+                                        }
+
+                                        // expected != wait_ctx: the future was setup with a different context ?!?!
+                                        // something went wrong here, abort
+                                        if( expected != &wait_ctx ) abort("Future in unexpected state");
+
+                                        // we still have the original context, then no one else saw it
+                                        // attempt to remove the context so it doesn't get consumed.
+                                        if(__atomic_compare_exchange_n( &this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
+                                                return false;
+                                        }
+                                }
                         }
 
@@ -379 +381 @@
                                 return ret;
                         }
+
+                        // Wait for any future to be fulfilled
+                        forall(T& | sized(T) | { bool setup( T&, oneshot & ); bool retract( T&, oneshot & ); })
+                        T & wait_any( T * futures, size_t num_futures ) {
+                                oneshot temp;
+
+                                // setup all futures
+                                // if any are already satisfied return
+                                for ( i; num_futures ) {
+                                        if( !setup(futures[i], temp) ) return futures[i];
+                                }
+
+                                // Wait context is setup, just wait on it
+                                wait( temp );
+
+                                size_t ret;
+                                // attempt to retract all futures
+                                for ( i; num_futures ) {
+                                        if ( retract( futures[i], temp ) ) ret = i;
+                                }
+
+                                return futures[ret];
+                        }
                 }
 

libcfa/src/concurrency/locks.cfa

@@ -219 +219 @@
         // this casts the alarm node to our wrapped type since we used type erasure
         static void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); }
+
+        struct pthread_alarm_node_wrap {
+                alarm_node_t alarm_node;
+                pthread_cond_var(L) * cond;
+                info_thread(L) * info_thd;
+        };
+
+        void ?{}( pthread_alarm_node_wrap(L) & this, Duration alarm, Duration period, Alarm_Callback callback, pthread_cond_var(L) * c, info_thread(L) * i ) {
+                this.alarm_node{ callback, alarm, period };
+                this.cond = c;
+                this.info_thd = i;
+        }
+
+        void ^?{}( pthread_alarm_node_wrap(L) & this ) { }
+
+        static void timeout_handler ( pthread_alarm_node_wrap(L) & this ) with( this ) {
+                // This pthread_cond_var member is called from the kernel, and therefore, cannot block, but it can spin.
+                lock( cond->lock __cfaabi_dbg_ctx2 );
+
+                // this check is necessary to avoid a race condition since this timeout handler
+                //      may still be called after a thread has been removed from the queue but
+                //      before the alarm is unregistered
+                if ( (*info_thd)`isListed ) {   // is thread on queue
+                        info_thd->signalled = false;
+                        // remove this thread O(1)
+                        remove( *info_thd );
+                        on_notify(*info_thd->lock, info_thd->t);
+                }
+                unlock( cond->lock );
+        }
+
+        // this casts the alarm node to our wrapped type since we used type erasure
+        static void pthread_alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (pthread_alarm_node_wrap(L) &)a ); }
 }
 
@@ -388 +421 @@
                 on_wakeup(*i.lock, recursion_count);
         }
-}
-
+
+        //-----------------------------------------------------------------------------
+        // pthread_cond_var
+
+        void  ?{}( pthread_cond_var(L) & this ) with(this) {
+                blocked_threads{};
+                lock{};
+        }
+
+        void ^?{}( pthread_cond_var(L) & this ) { }
+
+        bool notify_one( pthread_cond_var(L) & this ) with(this) { 
+                lock( lock __cfaabi_dbg_ctx2 );
+                bool ret = ! blocked_threads`isEmpty;
+                if ( ret ) {
+                        info_thread(L) & popped = try_pop_front( blocked_threads );
+                        on_notify(*popped.lock, popped.t);
+                }
+                unlock( lock );
+                return ret;
+        }
+
+        bool notify_all( pthread_cond_var(L) & this ) with(this) { 
+                lock( lock __cfaabi_dbg_ctx2 );
+                bool ret = ! blocked_threads`isEmpty;
+                while( ! blocked_threads`isEmpty ) {
+                        info_thread(L) & popped = try_pop_front( blocked_threads );
+                        on_notify(*popped.lock, popped.t);
+                }
+                unlock( lock );
+                return ret;
+        }
+
+        uintptr_t front( pthread_cond_var(L) & this ) with(this) { return blocked_threads`isEmpty ? NULL : blocked_threads`first.info; }
+        bool empty ( pthread_cond_var(L) & this ) with(this) { return blocked_threads`isEmpty; }
+
+        static size_t queue_and_get_recursion( pthread_cond_var(L) & this, info_thread(L) * i ) with(this) {
+                // add info_thread to waiting queue
+                insert_last( blocked_threads, *i );
+                size_t recursion_count = 0;
+                recursion_count = on_wait( *i->lock );
+                return recursion_count;
+        }
+        
+        static void queue_info_thread_timeout( pthread_cond_var(L) & this, info_thread(L) & info, Duration t, Alarm_Callback callback ) with(this) {
+                lock( lock __cfaabi_dbg_ctx2 );
+                size_t recursion_count = queue_and_get_recursion(this, &info);
+                pthread_alarm_node_wrap(L) node_wrap = { t, 0`s, callback, &this, &info };
+                register_self( &node_wrap.alarm_node );
+                unlock( lock );
+
+                // blocks here
+                park();
+
+                // unregisters alarm so it doesn't go off if this happens first
+                unregister_self( &node_wrap.alarm_node );
+
+                // resets recursion count here after waking
+                if (info.lock) on_wakeup(*info.lock, recursion_count);
+        }
+
+        void wait( pthread_cond_var(L) & this, L & l ) with(this) {
+                wait( this, l, 0 );
+        }
+
+        void wait( pthread_cond_var(L) & this, L & l, uintptr_t info ) with(this) {
+                lock( lock __cfaabi_dbg_ctx2 );
+                info_thread( L ) i = { active_thread(), info, &l };
+                size_t recursion_count = queue_and_get_recursion(this, &i);
+                unlock( lock );
+                park( );
+                on_wakeup(*i.lock, recursion_count);
+        }
+
+        #define PTHREAD_WAIT_TIME( u, l, t ) \
+                info_thread( L ) i = { active_thread(), u, l }; \
+                queue_info_thread_timeout(this, i, t, pthread_alarm_node_wrap_cast ); \
+                return i.signalled;
+
+        bool wait( pthread_cond_var(L) & this, L & l, timespec t ) {
+                Duration d = { t };
+                WAIT_TIME( 0, &l , d )
+        }
+        
+        bool wait( pthread_cond_var(L) & this, L & l, uintptr_t info, timespec t  ) {
+                Duration d = { t };
+                WAIT_TIME( info, &l , d )
+        }
+}
 //-----------------------------------------------------------------------------
 // Semaphore

libcfa/src/concurrency/locks.hfa

@@ -101 +101 @@
 
 //-----------------------------------------------------------------------------
+// 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; }
+
+static inline mcs_spin_node * volatile & ?`next ( mcs_spin_node * node ) {
+        return node->next;
+}
+
+struct mcs_spin_lock {
+        mcs_spin_queue queue;
+};
+
+static inline void lock(mcs_spin_lock & l, mcs_spin_node & n) {
+        mcs_spin_node * prev = __atomic_exchange_n(&l.queue.tail, &n, __ATOMIC_SEQ_CST);
+        n.locked = true;
+        if(prev == 0p) return;
+        prev->next = &n;
+        while(__atomic_load_n(&n.locked, __ATOMIC_RELAXED)) Pause();
+}
+
+static inline void unlock(mcs_spin_lock & l, mcs_spin_node & n) {
+        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) {}
+        n.next->locked = false;
+}
+
+//-----------------------------------------------------------------------------
+// CLH Spinlock
+// - No recursive acquisition
+// - Needs to be released by owner
+
+struct clh_lock {
+        volatile bool * volatile tail;
+};
+
+static inline void  ?{}( clh_lock & this ) { this.tail = malloc(); *this.tail = true; }
+static inline void ^?{}( clh_lock & this ) { free(this.tail); }
+
+static inline void lock(clh_lock & l) {
+        thread$ * curr_thd = active_thread();
+        *(curr_thd->clh_node) = false;
+        volatile bool * prev = __atomic_exchange_n((bool **)(&l.tail), (bool *)(curr_thd->clh_node), __ATOMIC_SEQ_CST);
+        while(!__atomic_load_n(prev, __ATOMIC_ACQUIRE)) Pause();
+        curr_thd->clh_prev = prev;
+}
+
+static inline void unlock(clh_lock & l) {
+        thread$ * curr_thd = active_thread();
+        __atomic_store_n(curr_thd->clh_node, true, __ATOMIC_RELEASE);
+        curr_thd->clh_node = curr_thd->clh_prev;
+}
+
+//-----------------------------------------------------------------------------
 // Linear backoff Spinlock
 struct linear_backoff_then_block_lock {
@@ -205 +270 @@
 // Fast Block Lock
 
-// High efficiency minimal blocking 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;
 
-        // List of blocked threads
-        dlist( thread$ ) blocked_threads;
-
+        // flag showing if lock is held
         bool held:1;
+
+        #ifdef __CFA_DEBUG__
+        // for deadlock detection
+        struct thread$ * owner;
+        #endif
 };
 
@@ -231 +302 @@
 static inline void lock(fast_block_lock & this) with(this) {
         lock( lock __cfaabi_dbg_ctx2 );
+
+        #ifdef __CFA_DEBUG__
+        assert(!(held && owner == active_thread()));
+        #endif
         if (held) {
                 insert_last( blocked_threads, *active_thread() );
@@ -238 +313 @@
         }
         held = true;
+        #ifdef __CFA_DEBUG__
+        owner = active_thread();
+        #endif
         unlock( lock );
 }
@@ -246 +324 @@
         thread$ * t = &try_pop_front( blocked_threads );
         held = ( t ? true : false );
+        #ifdef __CFA_DEBUG__
+        owner = ( t ? t : 0p );
+        #endif
         unpark( t );
         unlock( lock );
@@ -253 +334 @@
 static inline size_t on_wait(fast_block_lock & this) { unlock(this); return 0; }
 static inline void on_wakeup(fast_block_lock & this, size_t recursion ) { }
+
+//-----------------------------------------------------------------------------
+// simple_owner_lock
+
+// pthread owner lock
+// - reacquire for cond var
+// - recursive acquisition
+// - ownership
+struct simple_owner_lock {
+        // List of blocked threads
+        dlist( thread$ ) 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) {
+                insert_last( blocked_threads, *active_thread() );
+                unlock( lock );
+                park( );
+                return;
+        }
+        owner = active_thread();
+        recursion_count = 1;
+        unlock( lock );
+}
+
+// TODO: fix duplicate def issue and bring this back
+// void pop_and_set_new_owner( simple_owner_lock & this ) with( this ) {
+        // thread$ * t = &try_pop_front( blocked_threads );
+        // owner = t;
+        // recursion_count = ( t ? 1 : 0 );
+        // unpark( t );
+// }
+
+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_and_set_new_owner( this );
+                thread$ * t = &try_pop_front( blocked_threads );
+                owner = t;
+                recursion_count = ( t ? 1 : 0 );
+                unpark( t );
+        }
+        unlock( lock );
+}
+
+static inline void on_notify(simple_owner_lock & this, struct thread$ * t ) with(this) {
+        lock( lock __cfaabi_dbg_ctx2 );
+        // lock held
+        if ( owner != 0p ) {
+                insert_last( blocked_threads, *t );
+                unlock( lock );
+        }
+        // lock not held
+        else {
+                owner = t;
+                recursion_count = 1;
+                unpark( t );
+                unlock( lock );
+        }
+}
+
+static inline size_t on_wait(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 );
+
+        size_t ret = recursion_count;
+
+        // pop_and_set_new_owner( this );
+
+        thread$ * t = &try_pop_front( blocked_threads );
+        owner = t;
+        recursion_count = ( t ? 1 : 0 );
+        unpark( t );
+
+        unlock( lock );
+        return ret;
+}
+
+static inline void on_wakeup(simple_owner_lock & this, size_t recursion ) with(this) { recursion_count = recursion; }
+
+//-----------------------------------------------------------------------------
+// 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;
+
+        #ifdef __CFA_DEBUG__
+        // for deadlock detection
+        struct thread$ * owner;
+        #endif
+};
+
+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;
+        #ifdef __CFA_DEBUG__
+        assert(!(held && owner == active_thread()));
+        #endif
+        lock( lock, node );
+        while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
+        __atomic_store_n(&held, true, __ATOMIC_SEQ_CST);
+        unlock( lock, node );
+        #ifdef __CFA_DEBUG__
+        owner = active_thread();
+        #endif
+}
+
+static inline void unlock(spin_queue_lock & this) with(this) {
+        #ifdef __CFA_DEBUG__
+        owner = 0p;
+        #endif
+        __atomic_store_n(&held, false, __ATOMIC_RELEASE);
+}
+
+static inline void on_notify(spin_queue_lock & this, struct thread$ * t ) { unpark(t); }
+static inline size_t on_wait(spin_queue_lock & this) { unlock(this); return 0; }
+static inline void on_wakeup(spin_queue_lock & this, size_t recursion ) { }
+
+
+//-----------------------------------------------------------------------------
+// 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;
+
+        #ifdef __CFA_DEBUG__
+        // for deadlock detection
+        struct thread$ * owner;
+        #endif
+};
+
+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;
+        #ifdef __CFA_DEBUG__
+        assert(!(held && owner == active_thread()));
+        #endif
+        lock( lock, node );
+        while(held) Pause();
+        held = true;
+        unlock( lock, node );
+        #ifdef __CFA_DEBUG__
+        owner = active_thread();
+        #endif
+}
+
+static inline void unlock(mcs_block_spin_lock & this) with(this) {
+        #ifdef __CFA_DEBUG__
+        owner = 0p;
+        #endif
+        held = false;
+}
+
+static inline void on_notify(mcs_block_spin_lock & this, struct thread$ * t ) { unpark(t); }
+static inline size_t on_wait(mcs_block_spin_lock & this) { unlock(this); return 0; }
+static inline void on_wakeup(mcs_block_spin_lock & this, size_t recursion ) { }
+
+//-----------------------------------------------------------------------------
+// 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;
+
+        #ifdef __CFA_DEBUG__
+        // for deadlock detection
+        struct thread$ * owner;
+        #endif
+};
+
+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) {
+        #ifdef __CFA_DEBUG__
+        assert(!(held && owner == active_thread()));
+        #endif
+        lock( lock );
+        while(held) Pause();
+        held = true;
+        unlock( lock );
+        #ifdef __CFA_DEBUG__
+        owner = active_thread();
+        #endif
+}
+
+static inline void unlock(block_spin_lock & this) with(this) {
+        #ifdef __CFA_DEBUG__
+        owner = 0p;
+        #endif
+        held = false;
+}
+
+static inline void on_notify(block_spin_lock & this, struct thread$ * t ) { unpark(t); }
+static inline size_t on_wait(block_spin_lock & this) { unlock(this); return 0; }
+static inline void on_wakeup(block_spin_lock & this, size_t recursion ) { }
 
 //-----------------------------------------------------------------------------
@@ -332 +683 @@
         // - 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;
@@ -341 +692 @@
         };
 
-
         void  ?{}( fast_cond_var(L) & this );
         void ^?{}( fast_cond_var(L) & this );
@@ -349 +699 @@
 
         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 );
+}

libcfa/src/concurrency/thread.cfa

@@ -53 +53 @@
         #endif
 
-        seqable.next = 0p;
-        seqable.back = 0p;
-
         node.next = 0p;
         node.prev = 0p;
+
+        clh_node = malloc( );
+        *clh_node = false;
+
         doregister(curr_cluster, this);
-
         monitors{ &self_mon_p, 1, (fptr_t)0 };
 }
@@ -67 +67 @@
                 canary = 0xDEADDEADDEADDEADp;
         #endif
+        free(clh_node);
         unregister(curr_cluster, this);
         ^self_cor{};

libcfa/src/containers/queueLockFree.hfa

@@ -2 +2 @@
 
 #include <assert.h>
+
+#include <bits/defs.hfa>
 
 forall( T &) {

libcfa/src/startup.cfa

@@ -63 +63 @@
 
 struct __spinlock_t;
-extern "C" {
-        void __cfaabi_dbg_record_lock(struct __spinlock_t & this, const char prev_name[]) __attribute__(( weak )) libcfa_public {}
-}
 
 // Local Variables: //