source: libcfa/src/concurrency/locks.hfa @ 82f4063

jacob/cs343-translationnew-ast-unique-expr
Last change on this file since 82f4063 was 82f4063, checked in by caparsons <caparson@…>, 8 months ago

switched unified locking to use dlist

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