Changeset 5a46e09

Timestamp:

Jun 29, 2021, 5:33:38 PM (3 years ago)

Author:

caparsons <caparson@…>

Branches:

ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

660665f

Parents:

bae0d35

Message:

Added Martins SpinCondLock? as linear_backoff_then_block lock

Files:

• libcfa/src/concurrency/locks.hfa (modified) (2 diffs)
• tests/unified_locking/.expect/locks.txt (modified) (1 diff)
• tests/unified_locking/locks.cfa (modified) (3 diffs)

libcfa/src/concurrency/locks.hfa

@@ -18 +18 @@
 
 #include <stdbool.h>
+#include <stdio.h>
 
 #include "bits/weakso_locks.hfa"
@@ -237 +238 @@
 }
 
+struct linear_backoff_then_block_lock {
+        // Spin lock used for mutual exclusion
+        __spinlock_t spinlock;
+
+        // Current thread owning the lock
+        struct $thread * owner;
+
+        // List of blocked threads
+        dlist( $thread ) blocked_threads;
+
+        // Used for comparing and exchanging
+        volatile size_t lock_value;
+
+        // used for linear backoff spinning
+        int spin_start;
+        int spin_end;
+        int spin_count;
+
+        // after unsuccessful linear backoff yield this many times
+        int yield_count;
+};
+
+static inline void  ?{}( linear_backoff_then_block_lock & this, int spin_start, int spin_end, int spin_count, int yield_count ) {
+        this.spinlock{};
+        this.blocked_threads{};
+        this.lock_value = 0;
+        this.spin_start = spin_start;
+        this.spin_end = spin_end;
+        this.spin_count = spin_count;
+        this.yield_count = yield_count;
+}
+static inline void  ?{}( linear_backoff_then_block_lock & this ) { this{4, 1024, 16, 0}; }
+static inline void ^?{}( linear_backoff_then_block_lock & this ) {}
+
+static inline bool internal_try_lock(linear_backoff_then_block_lock & this, size_t & compare_val) with(this) {
+        if (__atomic_compare_exchange_n(&lock_value, &compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
+                owner = active_thread();
+                return true;
+        }
+        return false;
+}
+
+static inline bool try_lock(linear_backoff_then_block_lock & this) { size_t compare_val = 0; return internal_try_lock(this, compare_val); }
+
+static inline bool try_lock_contention(linear_backoff_then_block_lock & this) with(this) {
+        if (__atomic_exchange_n(&lock_value, 2, __ATOMIC_ACQUIRE) == 0) {
+                owner = active_thread();
+                return true;
+        }
+        return false;
+}
+
+static inline bool block(linear_backoff_then_block_lock & this) with(this) {
+        lock( spinlock __cfaabi_dbg_ctx2 );
+        if (lock_value != 2) {
+                unlock( spinlock );
+                return true;
+        }
+        insert_last( blocked_threads, *active_thread() );
+        unlock( spinlock );
+        park( );
+        return true;
+}
+
+static inline bool lock(linear_backoff_then_block_lock & this) with(this) {
+        // if owner just return
+        if (active_thread() == owner) return true;
+        size_t compare_val = 0;
+        int spin = spin_start;
+        // linear backoff
+        for( ;; ) {
+                compare_val = 0;
+                if (internal_try_lock(this, compare_val)) return true;
+                if (2 == compare_val) break;
+                for (int i = 0; i < spin; i++) Pause();
+                if (spin >= spin_end) break;
+                spin += spin;
+        }
+
+        // linear backoff bounded by spin_count
+        spin = spin_start;
+        int spin_counter = 0;
+        int yield_counter = 0;
+        for ( ;; ) {
+                if(try_lock_contention(this)) return true;
+                if(spin_counter < spin_count) {
+                        for (int i = 0; i < spin; i++) Pause();
+                        if (spin < spin_end) spin += spin;
+                        else spin_counter++;
+                } else if (yield_counter < yield_count) {
+                        // after linear backoff yield yield_count times
+                        yield_counter++;
+                        yield();
+                } else { break; }
+        }
+
+        // block until signalled
+        while (block(this)) if(try_lock_contention(this)) return true;
+        
+        // this should never be reached as block(this) always returns true
+        return false;
+}
+
+static inline void unlock(linear_backoff_then_block_lock & this) with(this) {
+        verify(lock_value > 0);
+    owner = 0p;
+    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 );
+}
+
+
+void on_notify(linear_backoff_then_block_lock & this, struct $thread * t ) { unpark(t); }
+size_t on_wait(linear_backoff_then_block_lock & this) { unlock(this); return 0; }
+void on_wakeup(linear_backoff_then_block_lock & this, size_t recursion ) { lock(this); }
+
 //-----------------------------------------------------------------------------
 // is_blocking_lock

tests/unified_locking/.expect/locks.txt

@@ -15 +15 @@
 Start Test 8: fast lock and condition variable 3 wait/notify all
 Done Test 8
-Start Test 9: multi acquisiton lock and condition variable multiple acquire and wait/notify
+Start Test 9: linear backoff lock and condition variable single wait/notify
 Done Test 9
-Start Test 10: owner lock and condition variable multiple acquire and wait/notify
+Start Test 10: linear backoff lock and condition variable 3 wait/notify all
 Done Test 10
-Start Test 11: no lock condition variable wait/notify
+Start Test 11: multi acquisiton lock and condition variable multiple acquire and wait/notify
 Done Test 11
-Start Test 12: locked condition variable wait/notify with front()
+Start Test 12: owner lock and condition variable multiple acquire and wait/notify
 Done Test 12
+Start Test 13: no lock condition variable wait/notify
+Done Test 13
+Start Test 14: locked condition variable wait/notify with front()
+Done Test 14

tests/unified_locking/locks.cfa

@@ -18 +18 @@
 condition_variable( fast_lock ) c_f;
 
+linear_backoff_then_block_lock l;
+condition_variable( linear_backoff_then_block_lock ) c_l;
+
 thread T_C_M_WS1 {};
 
@@ -99 +102 @@
                 }
                 unlock(f);
+        }
+}
+
+thread T_C_L_WS1 {};
+
+void main( T_C_L_WS1 & this ) {
+        for (unsigned int i = 0; i < num_times; i++) {
+                lock(l);
+                if(empty(c_l) && i != num_times - 1) {
+                        wait(c_l,l);
+                }else{
+                        notify_one(c_l);
+                }
+                unlock(l);
+        }
+}
+
+thread T_C_L_WB1 {};
+
+void main( T_C_L_WB1 & this ) {
+        for (unsigned int i = 0; i < num_times; i++) {
+                lock(l);
+                if(counter(c_l) == 3 || i == num_times - 1) {
+                        notify_all(c_l);
+                }else{
+                        wait(c_l,l);
+                }
+                unlock(l);
         }
 }
@@ -298 +329 @@
         printf("Done Test 8\n");
 
-        printf("Start Test 9: multi acquisiton lock and condition variable multiple acquire and wait/notify\n");
+        printf("Start Test 9: linear backoff lock and condition variable single wait/notify\n");
+        {
+                T_C_L_WS1 t1[2];
+        }
+        printf("Done Test 9\n");
+
+        printf("Start Test 10: linear backoff lock and condition variable 3 wait/notify all\n");
+        {
+                T_C_L_WB1 t1[4];
+        }
+        printf("Done Test 10\n");
+
+        printf("Start Test 11: multi acquisiton lock and condition variable multiple acquire and wait/notify\n");
         {
                 T_C_M_WS2 t1[2];
         }
-        printf("Done Test 9\n");
-
-        printf("Start Test 10: owner lock and condition variable multiple acquire and wait/notify\n");
+        printf("Done Test 11\n");
+
+        printf("Start Test 12: owner lock and condition variable multiple acquire and wait/notify\n");
         {
                 T_C_O_WS2 t1[2];
         }
-        printf("Done Test 10\n");
-
-        printf("Start Test 11: no lock condition variable wait/notify\n");
+        printf("Done Test 12\n");
+
+        printf("Start Test 13: no lock condition variable wait/notify\n");
         {
                 T_C_NLW t1;
                 T_C_NLS t2;
         }
-        printf("Done Test 11\n");
-
-        printf("Start Test 12: locked condition variable wait/notify with front()\n");
+        printf("Done Test 13\n");
+
+        printf("Start Test 14: locked condition variable wait/notify with front()\n");
         {
                 T_C_S_WNF t1[2];
         }
-        printf("Done Test 12\n");
-
-        // removed to limit test duration. Full test is in long run tests
-        // printf("Start Test 11: unlocked condition variable delay wait\n");
-        // {
-        //      T_C_NLWD t1;
-        //      T_C_WDS t2;
-        // }
-        // printf("Done Test 11\n");
-
-        // printf("Start Test 12: locked condition variable delay wait with unlocked signal\n");
-        // {
-        //      T_C_LWD t1;
-        //      T_C_WDS t2;
-        // }
-        // printf("Done Test 12\n");
-
-        // printf("Start Test 13: locked condition variable delay wait with locked signal\n");
-        // {
-        //      T_C_LWD t1;
-        //      T_C_LWDS t2;
-        // }
-        // printf("Done Test 13\n");
-}
+        printf("Done Test 14\n");
+}