source: libcfa/src/concurrency/locks.hfa@ 89c2a77b

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 89c2a77b was 198e335, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Fixed default parameter
  • Property mode set to 100644
File size: 9.5 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) {
42 /* paranoid */ verify(!(thrd->seqable.next));
43 /* paranoid */ verify(!(thrd`next));
44
45 push(this.queue, thrd);
46 return true;
47}
48
49static inline bool P(Semaphore0nary & this) {
50 $thread * thrd = active_thread();
51 P(this, thrd);
52 park();
53 return true;
54}
55
56static inline $thread * V(Semaphore0nary & this, bool doUnpark = true) {
57 $thread * next;
58 lock(this.lock __cfaabi_dbg_ctx2);
59 for (;;) {
60 next = pop(this.queue);
61 if (next) break;
62 Pause();
63 }
64 unlock(this.lock);
65
66 if (doUnpark) unpark(next);
67 return next;
68}
69
70// Wrapper used on top of any sempahore to avoid potential locking
71struct BinaryBenaphore {
72 volatile ssize_t counter;
73};
74
75static inline {
76 void ?{}(BinaryBenaphore & this) { this.counter = 0; }
77 void ?{}(BinaryBenaphore & this, zero_t) { this.counter = 0; }
78 void ?{}(BinaryBenaphore & this, one_t ) { this.counter = 1; }
79
80 // returns true if no blocking needed
81 bool P(BinaryBenaphore & this) {
82 return __atomic_fetch_sub(&this.counter, 1, __ATOMIC_SEQ_CST) > 0;
83 }
84
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 tryP(ThreadBenaphore & this) { return tryP(this.ben); }
119static inline bool P(ThreadBenaphore & this, bool wait) { return wait ? P(this) : tryP(this); }
120
121static inline $thread * V(ThreadBenaphore & this, bool doUnpark = true) {
122 if (V(this.ben)) return 0p;
123 return V(this.sem, doUnpark);
124}
125
126//-----------------------------------------------------------------------------
127// Semaphore
128struct semaphore {
129 __spinlock_t lock;
130 int count;
131 __queue_t($thread) waiting;
132};
133
134void ?{}(semaphore & this, int count = 1);
135void ^?{}(semaphore & this);
136bool P (semaphore & this);
137bool V (semaphore & this);
138bool V (semaphore & this, unsigned count);
139$thread * V (semaphore & this, bool );
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 size_t on_wait ( single_acquisition_lock & this ) { return on_wait ( (blocking_lock &)this ); }
152static inline void on_wakeup( single_acquisition_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
153static inline void on_notify( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
154
155//----------
156struct owner_lock {
157 inline blocking_lock;
158};
159
160static inline void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
161static inline void ^?{}( owner_lock & this ) {}
162static inline void lock ( owner_lock & this ) { lock ( (blocking_lock &)this ); }
163static inline bool try_lock ( owner_lock & this ) { return try_lock( (blocking_lock &)this ); }
164static inline void unlock ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
165static inline size_t on_wait ( owner_lock & this ) { return on_wait ( (blocking_lock &)this ); }
166static inline void on_wakeup( owner_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
167static inline void on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
168
169struct fast_lock {
170 $thread * volatile owner;
171 ThreadBenaphore sem;
172};
173
174static inline bool $try_lock(fast_lock & this, $thread * thrd) {
175 $thread * exp = 0p;
176 return __atomic_compare_exchange_n(&this.owner, &exp, thrd, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
177}
178
179static inline void lock( fast_lock & this ) __attribute__((artificial));
180static inline void lock( fast_lock & this ) {
181 $thread * thrd = active_thread();
182 /* paranoid */verify(thrd != this.owner);
183
184 for (;;) {
185 if ($try_lock(this, thrd)) return;
186 P(this.sem);
187 }
188}
189
190static inline bool try_lock( fast_lock & this ) __attribute__((artificial));
191static inline bool try_lock ( fast_lock & this ) {
192 $thread * thrd = active_thread();
193 /* paranoid */ verify(thrd != this.owner);
194 return $try_lock(this, thrd);
195}
196
197static inline $thread * unlock( fast_lock & this ) __attribute__((artificial));
198static inline $thread * unlock( fast_lock & this ) {
199 $thread * thrd = active_thread();
200 /* paranoid */ verify(thrd == 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 Sequence( info_thread(L) ) blocked_threads;
273
274 // Count of current blocked threads
275 int count;
276 };
277
278 void ?{}( condition_variable(L) & this );
279 void ^?{}( condition_variable(L) & this );
280
281 bool notify_one( condition_variable(L) & this );
282 bool notify_all( condition_variable(L) & this );
283
284 uintptr_t front( condition_variable(L) & this );
285
286 bool empty ( condition_variable(L) & this );
287 int counter( condition_variable(L) & this );
288
289 void wait( condition_variable(L) & this );
290 void wait( condition_variable(L) & this, uintptr_t info );
291 bool wait( condition_variable(L) & this, Duration duration );
292 bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
293 bool wait( condition_variable(L) & this, Time time );
294 bool wait( condition_variable(L) & this, uintptr_t info, Time time );
295
296 void wait( condition_variable(L) & this, L & l );
297 void wait( condition_variable(L) & this, L & l, uintptr_t info );
298 bool wait( condition_variable(L) & this, L & l, Duration duration );
299 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
300 bool wait( condition_variable(L) & this, L & l, Time time );
301 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time );
302}
Note: See TracBrowser for help on using the repository browser.