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

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 e20eaf4 was e20eaf4, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Fixed incorrect comment in locks code.
  • 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) {
85 return __atomic_fetch_sub(&this.counter, 1, __ATOMIC_SEQ_CST) > 0;
86 }
87
88 bool tryP(BinaryBenaphore & this) {
89 ssize_t c = this.counter;
90 return (c >= 1) && __atomic_compare_exchange_n(&this.counter, &c, c-1, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
91 }
92
93 // returns true if notify needed
94 bool V(BinaryBenaphore & this) {
95 ssize_t c = 0;
96 for () {
97 if (__atomic_compare_exchange_n(&this.counter, &c, c+1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
98 if (c == 0) return true;
99 /* paranoid */ verify(c < 0);
100 return false;
101 } else {
102 if (c == 1) return true;
103 /* paranoid */ verify(c < 1);
104 Pause();
105 }
106 }
107 }
108}
109
110// Binary Semaphore based on the BinaryBenaphore on top of the 0-nary Semaphore
111struct ThreadBenaphore {
112 BinaryBenaphore ben;
113 Semaphore0nary sem;
114};
115
116static inline void ?{}(ThreadBenaphore & this) {}
117static inline void ?{}(ThreadBenaphore & this, zero_t) { (this.ben){ 0 }; }
118static inline void ?{}(ThreadBenaphore & this, one_t ) { (this.ben){ 1 }; }
119
120static inline bool P(ThreadBenaphore & this) { return P(this.ben) ? false : P(this.sem); }
121static inline bool P(ThreadBenaphore & this, $thread * t) { return P(this.ben) ? false : P(this.sem, t ); }
122static inline bool tryP(ThreadBenaphore & this) { return tryP(this.ben); }
123static inline bool P(ThreadBenaphore & this, bool wait) { return wait ? P(this) : tryP(this); }
124
125static inline $thread * V(ThreadBenaphore & this, const bool doUnpark = true) {
126 if (V(this.ben)) return 0p;
127 return V(this.sem, doUnpark);
128}
129
130//-----------------------------------------------------------------------------
131// Semaphore
132struct semaphore {
133 __spinlock_t lock;
134 int count;
135 __queue_t($thread) waiting;
136};
137
138void ?{}(semaphore & this, int count = 1);
139void ^?{}(semaphore & this);
140bool P (semaphore & this);
141bool V (semaphore & this);
142bool V (semaphore & this, unsigned count);
143
144//----------
145struct single_acquisition_lock {
146 inline blocking_lock;
147};
148
149static inline void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
150static inline void ^?{}( single_acquisition_lock & this ) {}
151static inline void lock ( single_acquisition_lock & this ) { lock ( (blocking_lock &)this ); }
152static inline bool try_lock ( single_acquisition_lock & this ) { return try_lock( (blocking_lock &)this ); }
153static inline void unlock ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
154static inline void on_wait ( single_acquisition_lock & this ) { on_wait ( (blocking_lock &)this ); }
155static inline void on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
156static inline void set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
157static inline size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
158
159//----------
160struct owner_lock {
161 inline blocking_lock;
162};
163
164static inline void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
165static inline void ^?{}( owner_lock & this ) {}
166static inline void lock ( owner_lock & this ) { lock ( (blocking_lock &)this ); }
167static inline bool try_lock ( owner_lock & this ) { return try_lock( (blocking_lock &)this ); }
168static inline void unlock ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
169static inline void on_wait ( owner_lock & this ) { on_wait ( (blocking_lock &)this ); }
170static inline void on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
171static inline void set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
172static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
173
174struct fast_lock {
175 $thread * volatile owner;
176 ThreadBenaphore sem;
177};
178
179static inline bool $try_lock(fast_lock & this, $thread * thrd) {
180 $thread * exp = 0p;
181 return __atomic_compare_exchange_n(&this.owner, &exp, thrd, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
182}
183
184static inline void $lock(fast_lock & this, $thread * thrd) {
185 /* paranoid */verify(thrd != this.owner);
186
187 for (;;) {
188 if ($try_lock(this, thrd)) return;
189 P(this.sem, thrd);
190 }
191}
192
193static inline void lock( fast_lock & this ) {
194 $thread * thrd = active_thread();
195 /* paranoid */verify(thrd != this.owner);
196
197 for (;;) {
198 if ($try_lock(this, thrd)) return;
199 P(this.sem);
200 }
201}
202
203static inline void try_lock ( fast_lock & this ) {
204 $thread * thrd = active_thread();
205 /* paranoid */ verify(thrd != this.owner);
206 return $try_lock(this, thrd);
207}
208
209static inline void unlock( fast_lock & this ) {
210 $thread * thrd = active_thread();
211 /* paranoid */ verify(thrd == this.owner);
212 $thread * next = V(this.sem, false); // implicit fence
213 // open 'owner' only after fence
214 this.owner = 0p;
215
216 // Unpark the next person (can be 0p, unpark handles it)
217 unpark(next);
218}
219
220static inline void on_wait( fast_lock & this ) {
221 unlock(this);
222 #warning this is broken
223}
224
225static inline void on_notify( fast_lock & this, struct $thread * t ) {
226 $lock(this, t);
227 #warning this is broken
228}
229
230static inline void set_recursion_count( fast_lock & this, size_t recursion ) {}
231static inline size_t get_recursion_count( fast_lock & this ) { return 0; }
232
233struct mcs_node {
234 mcs_node * volatile next;
235 single_sem sem;
236};
237
238static inline void ?{}(mcs_node & this) { this.next = 0p; }
239
240static inline mcs_node * volatile & ?`next ( mcs_node * node ) {
241 return node->next;
242}
243
244struct mcs_lock {
245 mcs_queue(mcs_node) queue;
246};
247
248static inline void lock(mcs_lock & l, mcs_node & n) {
249 if(push(l.queue, &n))
250 wait(n.sem);
251}
252
253static inline void unlock(mcs_lock & l, mcs_node & n) {
254 mcs_node * next = advance(l.queue, &n);
255 if(next) post(next->sem);
256}
257
258//-----------------------------------------------------------------------------
259// is_blocking_lock
260trait is_blocking_lock(L & | sized(L)) {
261 // For synchronization locks to use when acquiring
262 void on_notify( L &, struct $thread * );
263
264 // For synchronization locks to use when releasing
265 void on_wait( L & );
266
267 // to get recursion count for cond lock to reset after waking
268 size_t get_recursion_count( L & );
269
270 // to set recursion count after getting signalled;
271 void set_recursion_count( L &, size_t recursion );
272};
273
274//-----------------------------------------------------------------------------
275// info_thread
276// the info thread is a wrapper around a thread used
277// to store extra data for use in the condition variable
278forall(L & | is_blocking_lock(L)) {
279 struct info_thread;
280
281 // for use by sequence
282 info_thread(L) *& Back( info_thread(L) * this );
283 info_thread(L) *& Next( info_thread(L) * this );
284}
285
286//-----------------------------------------------------------------------------
287// Synchronization Locks
288forall(L & | is_blocking_lock(L)) {
289 struct condition_variable {
290 // Spin lock used for mutual exclusion
291 __spinlock_t lock;
292
293 // List of blocked threads
294 Sequence( info_thread(L) ) blocked_threads;
295
296 // Count of current blocked threads
297 int count;
298 };
299
300 void ?{}( condition_variable(L) & this );
301 void ^?{}( condition_variable(L) & this );
302
303 bool notify_one( condition_variable(L) & this );
304 bool notify_all( condition_variable(L) & this );
305
306 uintptr_t front( condition_variable(L) & this );
307
308 bool empty ( condition_variable(L) & this );
309 int counter( condition_variable(L) & this );
310
311 void wait( condition_variable(L) & this );
312 void wait( condition_variable(L) & this, uintptr_t info );
313 bool wait( condition_variable(L) & this, Duration duration );
314 bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
315 bool wait( condition_variable(L) & this, Time time );
316 bool wait( condition_variable(L) & this, uintptr_t info, Time time );
317
318 void wait( condition_variable(L) & this, L & l );
319 void wait( condition_variable(L) & this, L & l, uintptr_t info );
320 bool wait( condition_variable(L) & this, L & l, Duration duration );
321 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
322 bool wait( condition_variable(L) & this, L & l, Time time );
323 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time );
324}
Note: See TracBrowser for help on using the repository browser.