source: libcfa/src/concurrency/locks.hfa @ f4ec5e45

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since f4ec5e45 was f4ec5e45, checked in by Thierry Delisle <tdelisle@…>, 9 months ago

Added several locks and other MES objects.

  • Property mode set to 100644
File size: 10.3 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
21#include "bits/weakso_locks.hfa"
22#include "containers/queueLockFree.hfa"
23
24#include "thread.hfa"
25
26#include "time_t.hfa"
27#include "time.hfa"
28
29//-----------------------------------------------------------------------------
30// Semaphores
31
32// '0-nary' semaphore
33// Similar to a counting semaphore except the value of one is never reached
34// as a consequence, a V() that would bring the value to 1 *spins* until
35// a P consumes it
36struct Semaphore0nary {
37        __spinlock_t lock; // needed to protect
38        mpsc_queue($thread) queue;
39};
40
41static inline bool P(Semaphore0nary & this, $thread * thrd) __attribute__((artificial));
42static inline bool P(Semaphore0nary & this, $thread * thrd) {
43        /* paranoid */ verify(!(thrd->seqable.next));
44        /* paranoid */ verify(!(thrd`next));
45
46        push(this.queue, thrd);
47        return true;
48}
49
50static inline bool P(Semaphore0nary & this) __attribute__((artificial));
51static inline bool P(Semaphore0nary & this) {
52    $thread * thrd = active_thread();
53    P(this, thrd);
54    park();
55    return true;
56}
57
58static inline $thread * V(Semaphore0nary & this, const bool doUnpark = true) __attribute__((artificial));
59static inline $thread * V(Semaphore0nary & this, const bool doUnpark = true) {
60        $thread * next;
61        lock(this.lock __cfaabi_dbg_ctx2);
62                for (;;) {
63                        next = pop(this.queue);
64                        if (next) break;
65                        Pause();
66                }
67        unlock(this.lock);
68
69        if (doUnpark) unpark(next);
70        return next;
71}
72
73// Wrapper used on top of any sempahore to avoid potential locking
74struct BinaryBenaphore {
75        volatile ssize_t counter;
76};
77
78static inline {
79        void ?{}(BinaryBenaphore & this) { this.counter = 0; }
80        void ?{}(BinaryBenaphore & this, zero_t) { this.counter = 0; }
81        void ?{}(BinaryBenaphore & this, one_t ) { this.counter = 1; }
82
83        // returns true if no blocking needed
84        bool P(BinaryBenaphore & this) { return __atomic_fetch_sub(&this.counter, 1, __ATOMIC_SEQ_CST) > 0; }
85        bool tryP(BinaryBenaphore & this) {
86                ssize_t c = this.counter;
87                return (c >= 1) && __atomic_compare_exchange_n(&this.counter, &c, c-1, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
88        }
89
90        // returns true if notify needed
91        bool V(BinaryBenaphore & this) {
92                ssize_t c = 0;
93                for () {
94                        if (__atomic_compare_exchange_n(&this.counter, &c, c+1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
95                                if (c == 0) return true;
96                                /* paranoid */ verify(c < 0);
97                                return false;
98                        } else {
99                                if (c == 1) return true;
100                                /* paranoid */ verify(c < 1);
101                                Pause();
102                        }
103                }
104        }
105}
106
107// Binary Semaphore based on the BinaryBenaphore on top of the 0-nary Semaphore
108struct ThreadBenaphore {
109        BinaryBenaphore ben;
110        Semaphore0nary  sem;
111};
112
113static inline void ?{}(ThreadBenaphore & this) {}
114static inline void ?{}(ThreadBenaphore & this, zero_t) { (this.ben){ 0 }; }
115static inline void ?{}(ThreadBenaphore & this, one_t ) { (this.ben){ 1 }; }
116
117static inline bool P(ThreadBenaphore & this)              { return /* P(this.ben) ? false : */ P(this.sem); }
118static inline bool P(ThreadBenaphore & this, $thread * t) { return /* P(this.ben) ? false : */ P(this.sem, t ); }
119static inline bool tryP(ThreadBenaphore & this)           { return tryP(this.ben); }
120static inline bool P(ThreadBenaphore & this, bool wait)   { return wait ? P(this) : tryP(this); }
121
122static inline $thread * V(ThreadBenaphore & this, const bool doUnpark = true) {
123        // if (V(this.ben)) return 0p;
124        return V(this.sem, doUnpark);
125}
126
127//-----------------------------------------------------------------------------
128// Semaphore
129struct semaphore {
130        __spinlock_t lock;
131        int count;
132        __queue_t($thread) waiting;
133};
134
135void  ?{}(semaphore & this, int count = 1);
136void ^?{}(semaphore & this);
137bool   P (semaphore & this);
138bool   V (semaphore & this);
139bool   V (semaphore & this, unsigned count);
140
141//----------
142struct single_acquisition_lock {
143        inline blocking_lock;
144};
145
146static inline void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
147static inline void ^?{}( single_acquisition_lock & this ) {}
148static inline void   lock      ( single_acquisition_lock & this ) { lock    ( (blocking_lock &)this ); }
149static inline bool   try_lock  ( single_acquisition_lock & this ) { return try_lock( (blocking_lock &)this ); }
150static inline void   unlock    ( single_acquisition_lock & this ) { unlock  ( (blocking_lock &)this ); }
151static inline void   on_wait   ( single_acquisition_lock & this ) { on_wait ( (blocking_lock &)this ); }
152static inline void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
153static inline void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
154static inline size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
155
156//----------
157struct owner_lock {
158        inline blocking_lock;
159};
160
161static inline void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
162static inline void ^?{}( owner_lock & this ) {}
163static inline void   lock     ( owner_lock & this ) { lock    ( (blocking_lock &)this ); }
164static inline bool   try_lock ( owner_lock & this ) { return try_lock( (blocking_lock &)this ); }
165static inline void   unlock   ( owner_lock & this ) { unlock  ( (blocking_lock &)this ); }
166static inline void   on_wait  ( owner_lock & this ) { on_wait ( (blocking_lock &)this ); }
167static inline void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
168static inline void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
169static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
170
171struct fast_lock {
172        $thread * volatile owner;
173        ThreadBenaphore sem;
174};
175
176static inline bool $try_lock(fast_lock & this, $thread * thrd) {
177    $thread * exp = 0p;
178    return __atomic_compare_exchange_n(&this.owner, &exp, thrd, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
179}
180
181static inline void $lock(fast_lock & this, $thread * thrd) {
182        /* paranoid */verify(thrd != this.owner);
183
184        for (;;) {
185                if ($try_lock(this, thrd)) return;
186                P(this.sem, thrd);
187        }
188}
189
190static inline void lock( fast_lock & this ) {
191        $thread * thrd = active_thread();
192        /* paranoid */verify(thrd != this.owner);
193
194        for (;;) {
195                if ($try_lock(this, thrd)) return;
196                P(this.sem);
197        }
198}
199
200static inline void try_lock ( fast_lock & this ) {
201        $thread * thrd = active_thread();
202        /* paranoid */ verify(thrd != this.owner);
203        return $try_lock(this, thrd);
204}
205
206static inline void unlock( fast_lock & this ) {
207        $thread * thrd = active_thread();
208        /* paranoid */ verify(thrd == this.owner);
209        $thread * next = V(this.sem, false); // implicit fence
210        // open 'owner' only after fence
211        this.owner = 0p;
212
213        // Unpark the next person (can be 0p, unpark handles it)
214        unpark(next);
215}
216
217static inline void on_wait( fast_lock & this ) {
218        unlock(this);
219        #warning this is broken
220}
221
222static inline void on_notify( fast_lock & this, struct $thread * t ) {
223        $lock(this, t);
224        #warning this is broken
225}
226
227static inline void   set_recursion_count( fast_lock & this, size_t recursion ) {}
228static inline size_t get_recursion_count( fast_lock & this ) { return 0; }
229
230struct mcs_node {
231        mcs_node * volatile next;
232        single_sem sem;
233};
234
235void ?{}(mcs_node & this) { this.next = 0p; }
236
237static inline mcs_node * volatile & ?`next ( mcs_node * node ) {
238        return node->next;
239}
240
241struct mcs_lock {
242        mcs_queue(mcs_node) queue;
243};
244
245static inline void lock(mcs_lock & l, mcs_node & n) {
246        if(push(l.queue, &n))
247                wait(n.sem);
248}
249
250static inline void unlock(mcs_lock & l, mcs_node & n) {
251        mcs_node * next = advance(l.queue, &n);
252        if(next) post(next->sem);
253}
254
255//-----------------------------------------------------------------------------
256// is_blocking_lock
257trait is_blocking_lock(L & | sized(L)) {
258        // For synchronization locks to use when acquiring
259        void on_notify( L &, struct $thread * );
260
261        // For synchronization locks to use when releasing
262        void on_wait( L & );
263
264        // to get recursion count for cond lock to reset after waking
265        size_t get_recursion_count( L & );
266
267        // to set recursion count after getting signalled;
268        void set_recursion_count( L &, size_t recursion );
269};
270
271//-----------------------------------------------------------------------------
272// info_thread
273// the info thread is a wrapper around a thread used
274// to store extra data for use in the condition variable
275forall(L & | is_blocking_lock(L)) {
276        struct info_thread;
277
278        // for use by sequence
279        info_thread(L) *& Back( info_thread(L) * this );
280        info_thread(L) *& Next( info_thread(L) * this );
281}
282
283//-----------------------------------------------------------------------------
284// Synchronization Locks
285forall(L & | is_blocking_lock(L)) {
286        struct condition_variable {
287                // Spin lock used for mutual exclusion
288                __spinlock_t lock;
289
290                // List of blocked threads
291                Sequence( info_thread(L) ) blocked_threads;
292
293                // Count of current blocked threads
294                int count;
295        };
296
297        void  ?{}( condition_variable(L) & this );
298        void ^?{}( condition_variable(L) & this );
299
300        bool notify_one( condition_variable(L) & this );
301        bool notify_all( condition_variable(L) & this );
302
303        uintptr_t front( condition_variable(L) & this );
304
305        bool empty  ( condition_variable(L) & this );
306        int  counter( condition_variable(L) & this );
307
308        void wait( condition_variable(L) & this );
309        void wait( condition_variable(L) & this, uintptr_t info );
310        bool wait( condition_variable(L) & this, Duration duration );
311        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
312        bool wait( condition_variable(L) & this, Time time );
313        bool wait( condition_variable(L) & this, uintptr_t info, Time time );
314
315        void wait( condition_variable(L) & this, L & l );
316        void wait( condition_variable(L) & this, L & l, uintptr_t info );
317        bool wait( condition_variable(L) & this, L & l, Duration duration );
318        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
319        bool wait( condition_variable(L) & this, L & l, Time time );
320        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time );
321}
Note: See TracBrowser for help on using the repository browser.