Changes in libcfa/src/concurrency/locks.hfa [7f958c4:490d17e0]

File:

• libcfa/src/concurrency/locks.hfa (modified) (6 diffs)

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;
+        bool locked:1;
+};
+
+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);
+        if(prev != 0p) {
+                prev->next = &n;
+                while(n.locked) 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) ) {
+                while (n.next == 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 +271 @@
 // 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 +303 @@
 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 +314 @@
         }
         held = true;
+        #ifdef __CFA_DEBUG__
+        owner = active_thread();
+        #endif
         unlock( lock );
 }
@@ -246 +325 @@
         thread$ * t = &try_pop_front( blocked_threads );
         held = ( t ? true : false );
+        #ifdef __CFA_DEBUG__
+        owner = ( t ? t : 0p );
+        #endif
         unpark( t );
         unlock( lock );
@@ -253 +335 @@
 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;
+
+//-----------------------------------------------------------------------------
+// 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
+        bool held:1;
+
+        #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(held) Pause();
+        held = true;
+        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
+        held = false;
+}
+
+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
+        bool held:1;
+
+        #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
+        bool held:1;
+
+        #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 ) { }
 
 //-----------------------------------------------------------------------------