source: libcfa/src/concurrency/locks.hfa@ 10a9479d

Last change on this file since 10a9479d was 2ad5e1d5, checked in by caparson <caparson@…>, 2 years ago

added missing semicolons
  • Property mode set to 100644
File size: 28.1 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 "collections/lockfree.hfa"
24#include "collections/list.hfa"
25
26#include "limits.hfa"
27#include "thread.hfa"
28
29#include "time_t.hfa"
30#include "time.hfa"
31
32#include "select.hfa"
33
34// futex headers
35#include <linux/futex.h> /* Definition of FUTEX_* constants */
36#include <sys/syscall.h> /* Definition of SYS_* constants */
37#include <unistd.h> /* Definition of syscall routine */
38
39typedef void (*__cfa_pre_park)( void * );
40
41static inline void pre_park_noop( void * ) {}
42
43//-----------------------------------------------------------------------------
44// is_blocking_lock
45forall( L & | sized(L) )
46trait is_blocking_lock {
47 // For synchronization locks to use when acquiring
48 void on_notify( L &, struct thread$ * );
49
50 // For synchronization locks to use when releasing
51 size_t on_wait( L &, __cfa_pre_park pp_fn, void * pp_datum );
52
53 // to set recursion count after getting signalled;
54 void on_wakeup( L &, size_t recursion );
55};
56
57static inline void pre_park_then_park( __cfa_pre_park pp_fn, void * pp_datum ) {
58 pp_fn( pp_datum );
59 park();
60}
61
62// macros for default routine impls for is_blocking_lock trait that do not wait-morph
63
64#define DEFAULT_ON_NOTIFY( lock_type ) \
65 static inline void on_notify( lock_type & this, thread$ * t ){ unpark(t); }
66
67#define DEFAULT_ON_WAIT( lock_type ) \
68 static inline size_t on_wait( lock_type & this, __cfa_pre_park pp_fn, void * pp_datum ) { \
69 unlock( this ); \
70 pre_park_then_park( pp_fn, pp_datum ); \
71 return 0; \
72 }
73
74// on_wakeup impl if lock should be reacquired after waking up
75#define DEFAULT_ON_WAKEUP_REACQ( lock_type ) \
76 static inline void on_wakeup( lock_type & this, size_t recursion ) { lock( this ); }
77
78// on_wakeup impl if lock will not be reacquired after waking up
79#define DEFAULT_ON_WAKEUP_NO_REACQ( lock_type ) \
80 static inline void on_wakeup( lock_type & this, size_t recursion ) {}
81
82
83
84//-----------------------------------------------------------------------------
85// Semaphore
86struct semaphore {
87 __spinlock_t lock;
88 int count;
89 __queue_t(thread$) waiting;
90};
91
92void ?{}(semaphore & this, int count = 1);
93void ^?{}(semaphore & this);
94bool P (semaphore & this);
95bool V (semaphore & this);
96bool V (semaphore & this, unsigned count);
97thread$ * V (semaphore & this, bool );
98
99//----------
100struct single_acquisition_lock {
101 inline blocking_lock;
102};
103
104static inline void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
105static inline void ^?{}( single_acquisition_lock & this ) {}
106static inline void lock ( single_acquisition_lock & this ) { lock ( (blocking_lock &)this ); }
107static inline bool try_lock ( single_acquisition_lock & this ) { return try_lock( (blocking_lock &)this ); }
108static inline void unlock ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
109static inline size_t on_wait ( single_acquisition_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) { return on_wait ( (blocking_lock &)this, pp_fn, pp_datum ); }
110static inline void on_wakeup( single_acquisition_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
111static inline void on_notify( single_acquisition_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); }
112static inline bool register_select( single_acquisition_lock & this, select_node & node ) { return register_select( (blocking_lock &)this, node ); }
113static inline bool unregister_select( single_acquisition_lock & this, select_node & node ) { return unregister_select( (blocking_lock &)this, node ); }
114static inline bool on_selected( single_acquisition_lock & this, select_node & node ) { return on_selected( (blocking_lock &)this, node ); }
115__CFA_SELECT_GET_TYPE( single_acquisition_lock );
116
117//----------
118struct owner_lock {
119 inline blocking_lock;
120};
121
122static inline void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
123static inline void ^?{}( owner_lock & this ) {}
124static inline void lock ( owner_lock & this ) { lock ( (blocking_lock &)this ); }
125static inline bool try_lock ( owner_lock & this ) { return try_lock( (blocking_lock &)this ); }
126static inline void unlock ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
127static inline size_t on_wait ( owner_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) { return on_wait ( (blocking_lock &)this, pp_fn, pp_datum ); }
128static inline void on_wakeup( owner_lock & this, size_t v ) { on_wakeup ( (blocking_lock &)this, v ); }
129static inline void on_notify( owner_lock & this, struct thread$ * t ) { on_notify( (blocking_lock &)this, t ); }
130static inline bool register_select( owner_lock & this, select_node & node ) { return register_select( (blocking_lock &)this, node ); }
131static inline bool unregister_select( owner_lock & this, select_node & node ) { return unregister_select( (blocking_lock &)this, node ); }
132static inline bool on_selected( owner_lock & this, select_node & node ) { return on_selected( (blocking_lock &)this, node ); }
133__CFA_SELECT_GET_TYPE( owner_lock );
134
135//-----------------------------------------------------------------------------
136// MCS Lock
137struct mcs_node {
138 mcs_node * volatile next;
139 single_sem sem;
140};
141
142static inline void ?{}( mcs_node & this ) { this.next = 0p; }
143
144static inline mcs_node * volatile & ?`next ( mcs_node * node ) {
145 return node->next;
146}
147
148struct mcs_lock {
149 mcs_queue(mcs_node) queue;
150};
151
152static inline void lock( mcs_lock & l, mcs_node & n ) {
153 if(push(l.queue, &n))
154 wait(n.sem);
155}
156
157static inline void unlock(mcs_lock & l, mcs_node & n) {
158 mcs_node * next = advance(l.queue, &n);
159 if(next) post(next->sem);
160}
161
162//-----------------------------------------------------------------------------
163// MCS Spin Lock
164// - No recursive acquisition
165// - Needs to be released by owner
166
167struct mcs_spin_node {
168 mcs_spin_node * volatile next;
169 volatile bool locked;
170};
171
172struct mcs_spin_queue {
173 mcs_spin_node * volatile tail;
174};
175
176static inline void ?{}( mcs_spin_node & this ) { this.next = 0p; this.locked = true; }
177
178struct mcs_spin_lock {
179 mcs_spin_queue queue;
180};
181
182static inline void lock( mcs_spin_lock & l, mcs_spin_node & n ) {
183 n.locked = true;
184
185 #if defined(__ARM_ARCH)
186 __asm__ __volatile__ ( "DMB ISH" ::: );
187 #endif
188
189 mcs_spin_node * prev = __atomic_exchange_n(&l.queue.tail, &n, __ATOMIC_SEQ_CST);
190 if( prev == 0p ) return;
191 prev->next = &n;
192
193 #if defined(__ARM_ARCH)
194 __asm__ __volatile__ ( "DMB ISH" ::: );
195 #endif
196
197 while( __atomic_load_n(&n.locked, __ATOMIC_RELAXED) ) Pause();
198
199 #if defined(__ARM_ARCH)
200 __asm__ __volatile__ ( "DMB ISH" ::: );
201 #endif
202}
203
204static inline void unlock(mcs_spin_lock & l, mcs_spin_node & n) {
205 #if defined(__ARM_ARCH)
206 __asm__ __volatile__ ( "DMB ISH" ::: );
207 #endif
208
209 mcs_spin_node * n_ptr = &n;
210 if (__atomic_compare_exchange_n(&l.queue.tail, &n_ptr, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return;
211 while (__atomic_load_n(&n.next, __ATOMIC_RELAXED) == 0p) Pause();
212
213 #if defined(__ARM_ARCH)
214 __asm__ __volatile__ ( "DMB ISH" ::: );
215 #endif
216
217 n.next->locked = false;
218}
219
220//-----------------------------------------------------------------------------
221// futex_mutex
222
223// - Kernel thd blocking alternative to the spinlock
224// - No ownership (will deadlock on reacq)
225// - no reacq on wakeup
226struct futex_mutex {
227 // lock state any state other than UNLOCKED is locked
228 // enum LockState { UNLOCKED = 0, UNCONTENDED = 1, CONTENDED = 2 };
229
230 // stores a lock state
231 int val;
232};
233
234// to use for FUTEX_WAKE and FUTEX_WAIT (other futex calls will need more params)
235static inline int futex(int *uaddr, int futex_op, int val) {
236 return syscall(SYS_futex, uaddr, futex_op, val, NULL, NULL, 0);
237}
238
239static inline void ?{}( futex_mutex & this ) with(this) { val = 0; }
240
241static inline bool internal_try_lock( futex_mutex & this, int & compare_val) with(this) {
242 return __atomic_compare_exchange_n((int*)&val, (int*)&compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE);
243}
244
245static inline int internal_exchange( futex_mutex & this ) with(this) {
246 return __atomic_exchange_n((int*)&val, 2, __ATOMIC_ACQUIRE);
247}
248
249// if this is called recursively IT WILL DEADLOCK!!!!!
250static inline void lock( futex_mutex & this ) with(this) {
251 int state;
252
253 for( int spin = 4; spin < 1024; spin += spin) {
254 state = 0;
255 // if unlocked, lock and return
256 if (internal_try_lock(this, state)) return;
257 if (2 == state) break;
258 for (int i = 0; i < spin; i++) Pause();
259 }
260
261 // if not in contended state, set to be in contended state
262 if (state != 2) state = internal_exchange(this);
263
264 // block and spin until we win the lock
265 while (state != 0) {
266 futex((int*)&val, FUTEX_WAIT, 2); // if val is not 2 this returns with EWOULDBLOCK
267 state = internal_exchange(this);
268 }
269}
270
271static inline void unlock(futex_mutex & this) with(this) {
272 // if uncontended do atomic unlock and then return
273 if (__atomic_exchange_n(&val, 0, __ATOMIC_RELEASE) == 1) return;
274
275 // otherwise threads are blocked so we must wake one
276 futex((int *)&val, FUTEX_WAKE, 1);
277}
278
279DEFAULT_ON_NOTIFY( futex_mutex )
280DEFAULT_ON_WAIT( futex_mutex )
281DEFAULT_ON_WAKEUP_NO_REACQ( futex_mutex )
282
283//-----------------------------------------------------------------------------
284// go_mutex
285
286// - Kernel thd blocking alternative to the spinlock
287// - No ownership (will deadlock on reacq)
288// - Golang's flavour of mutex
289// - Impl taken from Golang: src/runtime/lock_futex.go
290struct go_mutex {
291 // lock state any state other than UNLOCKED is locked
292 // enum LockState { UNLOCKED = 0, LOCKED = 1, SLEEPING = 2 };
293
294 // stores a lock state
295 int val;
296};
297static inline void ?{}( go_mutex & this ) with(this) { val = 0; }
298static inline void ?{}( go_mutex & this, go_mutex this2 ) = void;
299static inline void ?=?( go_mutex & this, go_mutex this2 ) = void;
300
301static inline bool internal_try_lock(go_mutex & this, int & compare_val, int new_val ) with(this) {
302 return __atomic_compare_exchange_n((int*)&val, (int*)&compare_val, new_val, false, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE);
303}
304
305static inline int internal_exchange(go_mutex & this, int swap ) with(this) {
306 return __atomic_exchange_n((int*)&val, swap, __ATOMIC_ACQUIRE);
307}
308
309// if this is called recursively IT WILL DEADLOCK!!!!!
310static inline void lock( go_mutex & this ) with( this ) {
311 int state, init_state;
312
313 // speculative grab
314 state = internal_exchange(this, 1);
315 if ( !state ) return; // state == 0
316 init_state = state;
317 for (;;) {
318 for( int i = 0; i < 4; i++ ) {
319 while( !val ) { // lock unlocked
320 state = 0;
321 if ( internal_try_lock( this, state, init_state ) ) return;
322 }
323 for (int i = 0; i < 30; i++) Pause();
324 }
325
326 while( !val ) { // lock unlocked
327 state = 0;
328 if ( internal_try_lock( this, state, init_state ) ) return;
329 }
330 sched_yield();
331
332 // if not in contended state, set to be in contended state
333 state = internal_exchange( this, 2 );
334 if ( !state ) return; // state == 0
335 init_state = 2;
336 futex( (int*)&val, FUTEX_WAIT, 2 ); // if val is not 2 this returns with EWOULDBLOCK
337 }
338}
339
340static inline void unlock( go_mutex & this ) with(this) {
341 // if uncontended do atomic unlock and then return
342 if ( __atomic_exchange_n(&val, 0, __ATOMIC_RELEASE) == 1 ) return;
343
344 // otherwise threads are blocked so we must wake one
345 futex( (int *)&val, FUTEX_WAKE, 1 );
346}
347
348DEFAULT_ON_NOTIFY( go_mutex )
349DEFAULT_ON_WAIT( go_mutex )
350DEFAULT_ON_WAKEUP_NO_REACQ( go_mutex )
351
352//-----------------------------------------------------------------------------
353// Exponential backoff then block lock
354struct exp_backoff_then_block_lock {
355 // Spin lock used for mutual exclusion
356 __spinlock_t spinlock;
357
358 // List of blocked threads
359 dlist( thread$ ) blocked_threads;
360
361 // Used for comparing and exchanging
362 volatile size_t lock_value;
363};
364
365static inline void ?{}( exp_backoff_then_block_lock & this ) {
366 this.spinlock{};
367 this.blocked_threads{};
368 this.lock_value = 0;
369}
370static inline void ?{}( exp_backoff_then_block_lock & this, exp_backoff_then_block_lock this2 ) = void;
371static inline void ?=?( exp_backoff_then_block_lock & this, exp_backoff_then_block_lock this2 ) = void;
372
373static inline void ^?{}( exp_backoff_then_block_lock & this ){}
374
375static inline bool internal_try_lock( exp_backoff_then_block_lock & this, size_t & compare_val ) with(this) {
376 return __atomic_compare_exchange_n(&lock_value, &compare_val, 1, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
377}
378
379static inline bool try_lock( exp_backoff_then_block_lock & this ) { size_t compare_val = 0; return internal_try_lock( this, compare_val ); }
380
381static inline bool try_lock_contention( exp_backoff_then_block_lock & this ) with(this) {
382 return !__atomic_exchange_n( &lock_value, 2, __ATOMIC_ACQUIRE );
383}
384
385static inline bool block( exp_backoff_then_block_lock & this ) with(this) {
386 lock( spinlock __cfaabi_dbg_ctx2 );
387 if (__atomic_load_n( &lock_value, __ATOMIC_SEQ_CST) != 2) {
388 unlock( spinlock );
389 return true;
390 }
391 insert_last( blocked_threads, *active_thread() );
392 unlock( spinlock );
393 park( );
394 return true;
395}
396
397static inline void lock( exp_backoff_then_block_lock & this ) with(this) {
398 size_t compare_val = 0;
399 int spin = 4;
400
401 // linear backoff
402 for( ;; ) {
403 compare_val = 0;
404 if (internal_try_lock(this, compare_val)) return;
405 if (2 == compare_val) break;
406 for (int i = 0; i < spin; i++) Pause();
407 if (spin >= 1024) break;
408 spin += spin;
409 }
410
411 if(2 != compare_val && try_lock_contention(this)) return;
412 // block until signalled
413 while (block(this)) if(try_lock_contention(this)) return;
414}
415
416static inline void unlock( exp_backoff_then_block_lock & this ) with(this) {
417 if (__atomic_exchange_n(&lock_value, 0, __ATOMIC_RELEASE) == 1) return;
418 lock( spinlock __cfaabi_dbg_ctx2 );
419 thread$ * t = &try_pop_front( blocked_threads );
420 unlock( spinlock );
421 unpark( t );
422}
423
424DEFAULT_ON_NOTIFY( exp_backoff_then_block_lock )
425DEFAULT_ON_WAIT( exp_backoff_then_block_lock )
426DEFAULT_ON_WAKEUP_REACQ( exp_backoff_then_block_lock )
427
428//-----------------------------------------------------------------------------
429// Fast Block Lock
430
431// minimal blocking lock
432// - No reacquire for cond var
433// - No recursive acquisition
434// - No ownership
435struct fast_block_lock {
436 // List of blocked threads
437 dlist( thread$ ) blocked_threads;
438
439 // Spin lock used for mutual exclusion
440 __spinlock_t lock;
441
442 // flag showing if lock is held
443 bool held:1;
444};
445
446static inline void ?{}( fast_block_lock & this ) with(this) {
447 lock{};
448 blocked_threads{};
449 held = false;
450}
451static inline void ^?{}( fast_block_lock & this ) {}
452static inline void ?{}( fast_block_lock & this, fast_block_lock this2 ) = void;
453static inline void ?=?( fast_block_lock & this, fast_block_lock this2 ) = void;
454
455// if this is called recursively IT WILL DEADLOCK!!!!!
456static inline void lock( fast_block_lock & this ) with(this) {
457 lock( lock __cfaabi_dbg_ctx2 );
458 if ( held ) {
459 insert_last( blocked_threads, *active_thread() );
460 unlock( lock );
461 park( );
462 return;
463 }
464 held = true;
465 unlock( lock );
466}
467
468static inline void unlock( fast_block_lock & this ) with(this) {
469 lock( lock __cfaabi_dbg_ctx2 );
470 /* paranoid */ verifyf( held != false, "Attempt to release lock %p that isn't held", &this );
471 thread$ * t = &try_pop_front( blocked_threads );
472 held = ( t ? true : false );
473 unpark( t );
474 unlock( lock );
475}
476
477static inline void on_notify( fast_block_lock & this, struct thread$ * t ) with(this) {
478 lock( lock __cfaabi_dbg_ctx2 );
479 insert_last( blocked_threads, *t );
480 unlock( lock );
481}
482DEFAULT_ON_WAIT( fast_block_lock )
483DEFAULT_ON_WAKEUP_NO_REACQ( fast_block_lock )
484
485//-----------------------------------------------------------------------------
486// simple_owner_lock
487
488// pthread owner lock
489// - reacquire for cond var
490// - recursive acquisition
491// - ownership
492struct simple_owner_lock {
493 // List of blocked threads
494 dlist( select_node ) blocked_threads;
495
496 // Spin lock used for mutual exclusion
497 __spinlock_t lock;
498
499 // owner showing if lock is held
500 struct thread$ * owner;
501
502 size_t recursion_count;
503};
504
505static inline void ?{}( simple_owner_lock & this ) with(this) {
506 lock{};
507 blocked_threads{};
508 owner = 0p;
509 recursion_count = 0;
510}
511static inline void ^?{}( simple_owner_lock & this ) {}
512static inline void ?{}( simple_owner_lock & this, simple_owner_lock this2 ) = void;
513static inline void ?=?( simple_owner_lock & this, simple_owner_lock this2 ) = void;
514
515static inline void lock( simple_owner_lock & this ) with(this) {
516 if ( owner == active_thread() ) {
517 recursion_count++;
518 return;
519 }
520 lock( lock __cfaabi_dbg_ctx2 );
521
522 if ( owner != 0p ) {
523 select_node node;
524 insert_last( blocked_threads, node );
525 unlock( lock );
526 park( );
527 return;
528 }
529 owner = active_thread();
530 recursion_count = 1;
531 unlock( lock );
532}
533
534static inline void pop_node( simple_owner_lock & this ) with(this) {
535 __handle_waituntil_OR( blocked_threads );
536 select_node * node = &try_pop_front( blocked_threads );
537 if ( node ) {
538 owner = node->blocked_thread;
539 recursion_count = 1;
540 // if ( !node->clause_status || __make_select_node_available( *node ) ) unpark( node->blocked_thread );
541 wake_one( blocked_threads, *node );
542 } else {
543 owner = 0p;
544 recursion_count = 0;
545 }
546}
547
548static inline void unlock( simple_owner_lock & this ) with(this) {
549 lock( lock __cfaabi_dbg_ctx2 );
550 /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
551 /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
552 // if recursion count is zero release lock and set new owner if one is waiting
553 recursion_count--;
554 if ( recursion_count == 0 ) {
555 pop_node( this );
556 }
557 unlock( lock );
558}
559
560static inline void on_notify( simple_owner_lock & this, thread$ * t ) with(this) {
561 lock( lock __cfaabi_dbg_ctx2 );
562 // lock held
563 if ( owner != 0p ) {
564 insert_last( blocked_threads, *(select_node *)t->link_node );
565 }
566 // lock not held
567 else {
568 owner = t;
569 recursion_count = 1;
570 unpark( t );
571 }
572 unlock( lock );
573}
574
575static inline size_t on_wait( simple_owner_lock & this, __cfa_pre_park pp_fn, void * pp_datum ) with(this) {
576 lock( lock __cfaabi_dbg_ctx2 );
577 /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
578 /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
579
580 size_t ret = recursion_count;
581
582 pop_node( this );
583
584 select_node node;
585 active_thread()->link_node = (void *)&node;
586 unlock( lock );
587
588 pre_park_then_park( pp_fn, pp_datum );
589
590 return ret;
591}
592
593static inline void on_wakeup( simple_owner_lock & this, size_t recursion ) with(this) { recursion_count = recursion; }
594
595// waituntil() support
596static inline bool register_select( simple_owner_lock & this, select_node & node ) with(this) {
597 lock( lock __cfaabi_dbg_ctx2 );
598
599 // check if we can complete operation. If so race to establish winner in special OR case
600 if ( !node.park_counter && ( owner == active_thread() || owner == 0p ) ) {
601 if ( !__make_select_node_available( node ) ) { // we didn't win the race so give up on registering
602 unlock( lock );
603 return false;
604 }
605 }
606
607 if ( owner == active_thread() ) {
608 recursion_count++;
609 if ( node.park_counter ) __make_select_node_available( node );
610 unlock( lock );
611 return true;
612 }
613
614 if ( owner != 0p ) {
615 insert_last( blocked_threads, node );
616 unlock( lock );
617 return false;
618 }
619
620 owner = active_thread();
621 recursion_count = 1;
622
623 if ( node.park_counter ) __make_select_node_available( node );
624 unlock( lock );
625 return true;
626}
627
628static inline bool unregister_select( simple_owner_lock & this, select_node & node ) with(this) {
629 lock( lock __cfaabi_dbg_ctx2 );
630 if ( node`isListed ) {
631 remove( node );
632 unlock( lock );
633 return false;
634 }
635
636 if ( owner == active_thread() ) {
637 recursion_count--;
638 if ( recursion_count == 0 ) {
639 pop_node( this );
640 }
641 }
642 unlock( lock );
643 return false;
644}
645
646static inline bool on_selected( simple_owner_lock & this, select_node & node ) { return true; }
647__CFA_SELECT_GET_TYPE( simple_owner_lock );
648
649//-----------------------------------------------------------------------------
650// Spin Queue Lock
651
652// - No reacquire for cond var
653// - No recursive acquisition
654// - No ownership
655// - spin lock with no locking/atomics in unlock
656struct spin_queue_lock {
657 // Spin lock used for mutual exclusion
658 mcs_spin_lock lock;
659
660 // flag showing if lock is held
661 volatile bool held;
662};
663
664static inline void ?{}( spin_queue_lock & this ) with(this) {
665 lock{};
666 held = false;
667}
668static inline void ^?{}( spin_queue_lock & this ) {}
669static inline void ?{}( spin_queue_lock & this, spin_queue_lock this2 ) = void;
670static inline void ?=?( spin_queue_lock & this, spin_queue_lock this2 ) = void;
671
672// if this is called recursively IT WILL DEADLOCK!
673static inline void lock( spin_queue_lock & this ) with(this) {
674 mcs_spin_node node;
675 lock( lock, node );
676 while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
677 __atomic_store_n(&held, true, __ATOMIC_SEQ_CST);
678 unlock( lock, node );
679}
680
681static inline void unlock( spin_queue_lock & this ) with(this) {
682 __atomic_store_n(&held, false, __ATOMIC_RELEASE);
683}
684
685DEFAULT_ON_NOTIFY( spin_queue_lock )
686DEFAULT_ON_WAIT( spin_queue_lock )
687DEFAULT_ON_WAKEUP_REACQ( spin_queue_lock )
688
689//-----------------------------------------------------------------------------
690// MCS Block Spin Lock
691
692// - No reacquire for cond var
693// - No recursive acquisition
694// - No ownership
695// - Blocks but first node spins (like spin queue but blocking for not first thd)
696struct mcs_block_spin_lock {
697 // Spin lock used for mutual exclusion
698 mcs_lock lock;
699
700 // flag showing if lock is held
701 volatile bool held;
702};
703
704static inline void ?{}( mcs_block_spin_lock & this ) with(this) {
705 lock{};
706 held = false;
707}
708static inline void ^?{}( mcs_block_spin_lock & this ) {}
709static inline void ?{}( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void;
710static inline void ?=?( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void;
711
712// if this is called recursively IT WILL DEADLOCK!!!!!
713static inline void lock( mcs_block_spin_lock & this ) with(this) {
714 mcs_node node;
715 lock( lock, node );
716 while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
717 __atomic_store_n(&held, true, __ATOMIC_SEQ_CST);
718 unlock( lock, node );
719}
720
721static inline void unlock(mcs_block_spin_lock & this) with(this) {
722 __atomic_store_n(&held, false, __ATOMIC_SEQ_CST);
723}
724
725DEFAULT_ON_NOTIFY( mcs_block_spin_lock )
726DEFAULT_ON_WAIT( mcs_block_spin_lock )
727DEFAULT_ON_WAKEUP_REACQ( mcs_block_spin_lock )
728
729//-----------------------------------------------------------------------------
730// Block Spin Lock
731
732// - No reacquire for cond var
733// - No recursive acquisition
734// - No ownership
735// - Blocks but first node spins (like spin queue but blocking for not first thd)
736struct block_spin_lock {
737 // Spin lock used for mutual exclusion
738 fast_block_lock lock;
739
740 // flag showing if lock is held
741 volatile bool held;
742};
743
744static inline void ?{}( block_spin_lock & this ) with(this) {
745 lock{};
746 held = false;
747}
748static inline void ^?{}( block_spin_lock & this ) {}
749static inline void ?{}( block_spin_lock & this, block_spin_lock this2 ) = void;
750static inline void ?=?( block_spin_lock & this, block_spin_lock this2 ) = void;
751
752// if this is called recursively IT WILL DEADLOCK!!!!!
753static inline void lock( block_spin_lock & this ) with(this) {
754 lock( lock );
755 while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
756 __atomic_store_n(&held, true, __ATOMIC_RELEASE);
757 unlock( lock );
758}
759
760static inline void unlock( block_spin_lock & this ) with(this) {
761 __atomic_store_n(&held, false, __ATOMIC_RELEASE);
762}
763
764static inline void on_notify( block_spin_lock & this, struct thread$ * t ) with(this.lock) {
765 // first we acquire internal fast_block_lock
766 lock( lock __cfaabi_dbg_ctx2 );
767 if ( held ) { // if internal fast_block_lock is held
768 insert_last( blocked_threads, *t );
769 unlock( lock );
770 return;
771 }
772 // if internal fast_block_lock is not held
773 held = true;
774 unlock( lock );
775
776 unpark(t);
777}
778DEFAULT_ON_WAIT( block_spin_lock )
779static inline void on_wakeup( block_spin_lock & this, size_t recursion ) with(this) {
780 // now we acquire the entire block_spin_lock upon waking up
781 while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
782 __atomic_store_n(&held, true, __ATOMIC_RELEASE);
783 unlock( lock ); // Now we release the internal fast_spin_lock
784}
785
786//-----------------------------------------------------------------------------
787// // info_thread
788// // the info thread is a wrapper around a thread used
789// // to store extra data for use in the condition variable
790forall(L & | is_blocking_lock(L)) {
791 struct info_thread;
792}
793
794//-----------------------------------------------------------------------------
795// Synchronization Locks
796forall(L & | is_blocking_lock(L)) {
797
798 //-----------------------------------------------------------------------------
799 // condition_variable
800
801 // The multi-tool condition variable
802 // - can pass timeouts to wait for either a signal or timeout
803 // - can wait without passing a lock
804 // - can have waiters reacquire different locks while waiting on the same cond var
805 // - has shadow queue
806 // - can be signalled outside of critical sections with no locks held
807 struct condition_variable {
808 // Spin lock used for mutual exclusion
809 __spinlock_t lock;
810
811 // List of blocked threads
812 dlist( info_thread(L) ) blocked_threads;
813
814 // Count of current blocked threads
815 int count;
816 };
817
818
819 void ?{}( condition_variable(L) & this );
820 void ^?{}( condition_variable(L) & this );
821
822 bool notify_one( condition_variable(L) & this );
823 bool notify_all( condition_variable(L) & this );
824
825 uintptr_t front( condition_variable(L) & this );
826
827 bool empty ( condition_variable(L) & this );
828 int counter( condition_variable(L) & this );
829
830 void wait( condition_variable(L) & this );
831 void wait( condition_variable(L) & this, uintptr_t info );
832 bool wait( condition_variable(L) & this, Duration duration );
833 bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
834
835 void wait( condition_variable(L) & this, L & l );
836 void wait( condition_variable(L) & this, L & l, uintptr_t info );
837 bool wait( condition_variable(L) & this, L & l, Duration duration );
838 bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
839
840 //-----------------------------------------------------------------------------
841 // fast_cond_var
842
843 // The trimmed and slim condition variable
844 // - no internal lock so you must hold a lock while using this cond var
845 // - signalling without holding branded lock is UNSAFE!
846 // - only allows usage of one lock, cond var is branded after usage
847
848 struct fast_cond_var {
849 // List of blocked threads
850 dlist( info_thread(L) ) blocked_threads;
851 #ifdef __CFA_DEBUG__
852 L * lock_used;
853 #endif
854 };
855
856 void ?{}( fast_cond_var(L) & this );
857 void ^?{}( fast_cond_var(L) & this );
858
859 bool notify_one( fast_cond_var(L) & this );
860 bool notify_all( fast_cond_var(L) & this );
861
862 uintptr_t front( fast_cond_var(L) & this );
863 bool empty ( fast_cond_var(L) & this );
864
865 void wait( fast_cond_var(L) & this, L & l );
866 void wait( fast_cond_var(L) & this, L & l, uintptr_t info );
867
868
869 //-----------------------------------------------------------------------------
870 // pthread_cond_var
871 //
872 // - cond var with minimal footprint
873 // - supports operations needed for phthread cond
874
875 struct pthread_cond_var {
876 dlist( info_thread(L) ) blocked_threads;
877 __spinlock_t lock;
878 };
879
880 void ?{}( pthread_cond_var(L) & this );
881 void ^?{}( pthread_cond_var(L) & this );
882
883 bool notify_one( pthread_cond_var(L) & this );
884 bool notify_all( pthread_cond_var(L) & this );
885
886 uintptr_t front( pthread_cond_var(L) & this );
887 bool empty ( pthread_cond_var(L) & this );
888
889 void wait( pthread_cond_var(L) & this, L & l );
890 void wait( pthread_cond_var(L) & this, L & l, uintptr_t info );
891 bool wait( pthread_cond_var(L) & this, L & l, timespec t );
892 bool wait( pthread_cond_var(L) & this, L & l, uintptr_t info, timespec t );
893}
Note: See TracBrowser for help on using the repository browser.