source: libcfa/src/concurrency/locks.hfa @ 62a38e7

Last change on this file since 62a38e7 was 2ad5e1d5, checked in by caparson <caparson@…>, 13 months 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.