source: libcfa/src/concurrency/locks.hfa @ 6b06abe

ADTast-experimentalenumpthread-emulationqualifiedEnum
Last change on this file since 6b06abe was 0d4f954, checked in by caparsons <caparson@…>, 3 years ago

changed concurrency library to work with new mutexstmt changes

  • Property mode set to 100644
File size: 8.4 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// locks.hfa -- PUBLIC
8// Runtime locks that used with the runtime thread system.
9//
10// Author           : Colby Alexander Parsons
11// Created On       : Thu Jan 21 19:46:50 2021
12// Last Modified By :
13// Last Modified On :
14// Update Count     :
15//
16
17#pragma once
18
19#include <stdbool.h>
20#include <stdio.h>
21
22#include "bits/weakso_locks.hfa"
23#include "containers/queueLockFree.hfa"
24#include "containers/list.hfa"
25
26#include "limits.hfa"
27#include "thread.hfa"
28
29#include "time_t.hfa"
30#include "time.hfa"
31
32//-----------------------------------------------------------------------------
33// Semaphore
34struct semaphore {
35        __spinlock_t lock;
36        int count;
37        __queue_t(thread$) waiting;
38};
39
40void  ?{}(semaphore & this, int count = 1);
41void ^?{}(semaphore & this);
42bool   P (semaphore & this);
43bool   V (semaphore & this);
44bool   V (semaphore & this, unsigned count);
45thread$ * V (semaphore & this, bool );
46
47//----------
48struct single_acquisition_lock {
49        inline blocking_lock;
50};
51
52static inline void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
53static inline void ^?{}( single_acquisition_lock & this ) {}
54static inline void   lock     ( single_acquisition_lock & this ) { lock    ( (blocking_lock &)this ); }
55static inline bool   try_lock ( single_acquisition_lock & this ) { return try_lock( (blocking_lock &)this ); }
56static inline void   unlock   ( single_acquisition_lock & this ) { unlock  ( (blocking_lock &)this ); }
57static inline size_t on_wait  ( single_acquisition_lock & this ) { return on_wait ( (blocking_lock &)this ); }
58static inline void   on_wakeup( single_acquisition_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
59static inline void   on_notify( single_acquisition_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); }
60
61//----------
62struct owner_lock {
63        inline blocking_lock;
64};
65
66static inline void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
67static inline void ^?{}( owner_lock & this ) {}
68static inline void   lock     ( owner_lock & this ) { lock    ( (blocking_lock &)this ); }
69static inline bool   try_lock ( owner_lock & this ) { return try_lock( (blocking_lock &)this ); }
70static inline void   unlock   ( owner_lock & this ) { unlock  ( (blocking_lock &)this ); }
71static inline size_t on_wait  ( owner_lock & this ) { return on_wait ( (blocking_lock &)this ); }
72static inline void   on_wakeup( owner_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
73static inline void   on_notify( owner_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); }
74
75struct mcs_node {
76        mcs_node * volatile next;
77        single_sem sem;
78};
79
80static inline void ?{}(mcs_node & this) { this.next = 0p; }
81
82static inline mcs_node * volatile & ?`next ( mcs_node * node ) {
83        return node->next;
84}
85
86struct mcs_lock {
87        mcs_queue(mcs_node) queue;
88};
89
90static inline void lock(mcs_lock & l, mcs_node & n) {
91        if(push(l.queue, &n))
92                wait(n.sem);
93}
94
95static inline void unlock(mcs_lock & l, mcs_node & n) {
96        mcs_node * next = advance(l.queue, &n);
97        if(next) post(next->sem);
98}
99
100struct linear_backoff_then_block_lock {
101        // Spin lock used for mutual exclusion
102        __spinlock_t spinlock;
103
104        // Current thread owning the lock
105        struct thread$ * owner;
106
107        // List of blocked threads
108        dlist( thread$ ) blocked_threads;
109
110        // Used for comparing and exchanging
111        volatile size_t lock_value;
112
113        // used for linear backoff spinning
114        int spin_start;
115        int spin_end;
116        int spin_count;
117
118        // after unsuccessful linear backoff yield this many times
119        int yield_count;
120};
121
122static inline void  ?{}( linear_backoff_then_block_lock & this, int spin_start, int spin_end, int spin_count, int yield_count ) {
123        this.spinlock{};
124        this.blocked_threads{};
125        this.lock_value = 0;
126        this.spin_start = spin_start;
127        this.spin_end = spin_end;
128        this.spin_count = spin_count;
129        this.yield_count = yield_count;
130}
131static inline void  ?{}( linear_backoff_then_block_lock & this ) { this{4, 1024, 16, 0}; }
132static inline void ^?{}( linear_backoff_then_block_lock & this ) {}
133static inline void ?{}( linear_backoff_then_block_lock & this, linear_backoff_then_block_lock this2 ) = void;
134static inline void ?=?( linear_backoff_then_block_lock & this, linear_backoff_then_block_lock this2 ) = void;
135
136static inline bool internal_try_lock(linear_backoff_then_block_lock & this, size_t & compare_val) with(this) {
137        if (__atomic_compare_exchange_n(&lock_value, &compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
138                owner = active_thread();
139                return true;
140        }
141        return false;
142}
143
144static inline bool try_lock(linear_backoff_then_block_lock & this) { size_t compare_val = 0; return internal_try_lock(this, compare_val); }
145
146static inline bool try_lock_contention(linear_backoff_then_block_lock & this) with(this) {
147        if (__atomic_exchange_n(&lock_value, 2, __ATOMIC_ACQUIRE) == 0) {
148                owner = active_thread();
149                return true;
150        }
151        return false;
152}
153
154static inline bool block(linear_backoff_then_block_lock & this) with(this) {
155        lock( spinlock __cfaabi_dbg_ctx2 );
156        if (lock_value != 2) {
157                unlock( spinlock );
158                return true;
159        }
160        insert_last( blocked_threads, *active_thread() );
161        unlock( spinlock );
162        park( );
163        return true;
164}
165
166static inline void lock(linear_backoff_then_block_lock & this) with(this) {
167        // if owner just return
168        if (active_thread() == owner) return;
169        size_t compare_val = 0;
170        int spin = spin_start;
171        // linear backoff
172        for( ;; ) {
173                compare_val = 0;
174                if (internal_try_lock(this, compare_val)) return;
175                if (2 == compare_val) break;
176                for (int i = 0; i < spin; i++) Pause();
177                if (spin >= spin_end) break;
178                spin += spin;
179        }
180
181        if(2 != compare_val && try_lock_contention(this)) return;
182        // block until signalled
183        while (block(this)) if(try_lock_contention(this)) return;
184}
185
186static inline void unlock(linear_backoff_then_block_lock & this) with(this) {
187        verify(lock_value > 0);
188    owner = 0p;
189    if (__atomic_exchange_n(&lock_value, 0, __ATOMIC_RELEASE) == 1) return;
190        lock( spinlock __cfaabi_dbg_ctx2 );
191        thread$ * t = &try_pop_front( blocked_threads );
192        unlock( spinlock );
193        unpark( t );
194}
195
196static inline void on_notify(linear_backoff_then_block_lock & this, struct thread$ * t ) { unpark(t); }
197static inline size_t on_wait(linear_backoff_then_block_lock & this) { unlock(this); return 0; }
198static inline void on_wakeup(linear_backoff_then_block_lock & this, size_t recursion ) { lock(this); }
199
200//-----------------------------------------------------------------------------
201// is_blocking_lock
202trait is_blocking_lock(L & | sized(L)) {
203        // For synchronization locks to use when acquiring
204        void on_notify( L &, struct thread$ * );
205
206        // For synchronization locks to use when releasing
207        size_t on_wait( L & );
208
209        // to set recursion count after getting signalled;
210        void on_wakeup( L &, size_t recursion );
211};
212
213//-----------------------------------------------------------------------------
214// // info_thread
215// // the info thread is a wrapper around a thread used
216// // to store extra data for use in the condition variable
217forall(L & | is_blocking_lock(L)) {
218        struct info_thread;
219
220        // // for use by sequence
221        // info_thread(L) *& Back( info_thread(L) * this );
222        // info_thread(L) *& Next( info_thread(L) * this );
223}
224
225//-----------------------------------------------------------------------------
226// Synchronization Locks
227forall(L & | is_blocking_lock(L)) {
228        struct condition_variable {
229                // Spin lock used for mutual exclusion
230                __spinlock_t lock;
231
232                // List of blocked threads
233                dlist( info_thread(L) ) blocked_threads;
234
235                // Count of current blocked threads
236                int count;
237        };
238
239
240        void  ?{}( condition_variable(L) & this );
241        void ^?{}( condition_variable(L) & this );
242
243        bool notify_one( condition_variable(L) & this );
244        bool notify_all( condition_variable(L) & this );
245
246        uintptr_t front( condition_variable(L) & this );
247
248        bool empty  ( condition_variable(L) & this );
249        int  counter( condition_variable(L) & this );
250
251        void wait( condition_variable(L) & this );
252        void wait( condition_variable(L) & this, uintptr_t info );
253        bool wait( condition_variable(L) & this, Duration duration );
254        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
255
256        void wait( condition_variable(L) & this, L & l );
257        void wait( condition_variable(L) & this, L & l, uintptr_t info );
258        bool wait( condition_variable(L) & this, L & l, Duration duration );
259        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
260}
Note: See TracBrowser for help on using the repository browser.