Changeset 7f958c4

Timestamp:

May 4, 2022, 3:28:00 PM (3 years ago)

Author:

caparsons <caparson@…>

Branches:

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

Children:

ec57856

Parents:

f6737ae1

Message:

added fast lock/cond var

Location:

libcfa/src/concurrency

Files:

• locks.cfa (modified) (2 diffs)
• locks.hfa (modified) (5 diffs)

libcfa/src/concurrency/locks.cfa

@@ -220 +220 @@
 
 //-----------------------------------------------------------------------------
-// condition variable
+// Synchronization Locks
 forall(L & | is_blocking_lock(L)) {
 
+        //-----------------------------------------------------------------------------
+        // condition variable
         void ?{}( condition_variable(L) & this ){
                 this.lock{};
@@ -337 +339 @@
         bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , duration ) }
         bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , duration ) }
+
+        //-----------------------------------------------------------------------------
+        // fast_cond_var
+        void  ?{}( fast_cond_var(L) & this ){
+                this.blocked_threads{}; 
+                #ifdef __CFA_DEBUG__
+                this.lock_used = 0p;
+                #endif
+        }
+        void ^?{}( fast_cond_var(L) & this ){ }
+
+        bool notify_one( fast_cond_var(L) & this ) with(this) {
+                bool ret = ! blocked_threads`isEmpty;
+                if ( ret ) {
+                        info_thread(L) & popped = try_pop_front( blocked_threads );
+                        on_notify(*popped.lock, popped.t);
+                }
+                return ret;
+        }
+        bool notify_all( fast_cond_var(L) & this ) with(this) {
+                bool ret = ! blocked_threads`isEmpty;
+                while( ! blocked_threads`isEmpty ) {
+                        info_thread(L) & popped = try_pop_front( blocked_threads );
+                        on_notify(*popped.lock, popped.t);
+                }
+                return ret;
+        }
+
+        uintptr_t front( fast_cond_var(L) & this ) with(this) { return blocked_threads`isEmpty ? NULL : blocked_threads`first.info; }
+        bool empty ( fast_cond_var(L) & this ) with(this) { return blocked_threads`isEmpty; }
+
+        void wait( fast_cond_var(L) & this, L & l ) {
+                wait( this, l, 0 );
+        }
+
+        void wait( fast_cond_var(L) & this, L & l, uintptr_t info ) with(this) {
+                // brand cond lock with lock
+                #ifdef __CFA_DEBUG__
+                        if ( lock_used == 0p ) lock_used = &l;
+                        else { assert(lock_used == &l); }
+                #endif
+                info_thread( L ) i = { active_thread(), info, &l };
+                insert_last( blocked_threads, i );
+                size_t recursion_count = on_wait( *i.lock );
+                park( );
+                on_wakeup(*i.lock, recursion_count);
+        }
 }
 

libcfa/src/concurrency/locks.hfa

@@ -73 +73 @@
 static inline void   on_notify( owner_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); }
 
+//-----------------------------------------------------------------------------
+// MCS Lock
 struct mcs_node {
         mcs_node * volatile next;
@@ -98 +100 @@
 }
 
+//-----------------------------------------------------------------------------
+// Linear backoff Spinlock
 struct linear_backoff_then_block_lock {
         // Spin lock used for mutual exclusion
@@ -199 +203 @@
 
 //-----------------------------------------------------------------------------
+// Fast Block Lock
+
+// High efficiency minimal blocking lock
+// - No reacquire for cond var
+// - No recursive acquisition
+// - No ownership
+struct fast_block_lock {
+        // Spin lock used for mutual exclusion
+        __spinlock_t lock;
+
+        // List of blocked threads
+        dlist( thread$ ) blocked_threads;
+
+        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 ) { unpark(t); }
+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 ) { }
+
+//-----------------------------------------------------------------------------
 // is_blocking_lock
 trait is_blocking_lock(L & | sized(L)) {
@@ -226 +282 @@
 // 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
@@ -258 +324 @@
         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 );
+}