Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/locks.hfa

    r2ed32fa7 r7f958c4  
    9898        mcs_node * next = advance(l.queue, &n);
    9999        if(next) post(next->sem);
    100 }
    101 
    102 //-----------------------------------------------------------------------------
    103 // MCS Spin Lock
    104 // - No recursive acquisition
    105 // - Needs to be released by owner
    106 
    107 struct mcs_spin_node {
    108         mcs_spin_node * volatile next;
    109         volatile bool locked;
    110 };
    111 
    112 struct mcs_spin_queue {
    113         mcs_spin_node * volatile tail;
    114 };
    115 
    116 static inline void ?{}(mcs_spin_node & this) { this.next = 0p; this.locked = true; }
    117 
    118 static inline mcs_spin_node * volatile & ?`next ( mcs_spin_node * node ) {
    119         return node->next;
    120 }
    121 
    122 struct mcs_spin_lock {
    123         mcs_spin_queue queue;
    124 };
    125 
    126 static inline void lock(mcs_spin_lock & l, mcs_spin_node & n) {
    127         mcs_spin_node * prev = __atomic_exchange_n(&l.queue.tail, &n, __ATOMIC_SEQ_CST);
    128         n.locked = true;
    129         if(prev == 0p) return;
    130         prev->next = &n;
    131         while(__atomic_load_n(&n.locked, __ATOMIC_RELAXED)) Pause();
    132 }
    133 
    134 static inline void unlock(mcs_spin_lock & l, mcs_spin_node & n) {
    135         mcs_spin_node * n_ptr = &n;
    136         if (__atomic_compare_exchange_n(&l.queue.tail, &n_ptr, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return;
    137         while (__atomic_load_n(&n.next, __ATOMIC_RELAXED) == 0p) {}
    138         n.next->locked = false;
    139 }
    140 
    141 //-----------------------------------------------------------------------------
    142 // CLH Spinlock
    143 // - No recursive acquisition
    144 // - Needs to be released by owner
    145 
    146 struct clh_lock {
    147         volatile bool * volatile tail;
    148 };
    149 
    150 static inline void  ?{}( clh_lock & this ) { this.tail = malloc(); *this.tail = true; }
    151 static inline void ^?{}( clh_lock & this ) { free(this.tail); }
    152 
    153 static inline void lock(clh_lock & l) {
    154         thread$ * curr_thd = active_thread();
    155         *(curr_thd->clh_node) = false;
    156         volatile bool * prev = __atomic_exchange_n((bool **)(&l.tail), (bool *)(curr_thd->clh_node), __ATOMIC_SEQ_CST);
    157         while(!__atomic_load_n(prev, __ATOMIC_ACQUIRE)) Pause();
    158         curr_thd->clh_prev = prev;
    159 }
    160 
    161 static inline void unlock(clh_lock & l) {
    162         thread$ * curr_thd = active_thread();
    163         __atomic_store_n(curr_thd->clh_node, true, __ATOMIC_RELEASE);
    164         curr_thd->clh_node = curr_thd->clh_prev;
    165100}
    166101
    … …  
    270205// Fast Block Lock
    271206
    272 // minimal blocking lock
     207// High efficiency minimal blocking lock
    273208// - No reacquire for cond var
    274209// - No recursive acquisition
    275210// - No ownership
    276211struct fast_block_lock {
     212        // Spin lock used for mutual exclusion
     213        __spinlock_t lock;
     214
    277215        // List of blocked threads
    278216        dlist( thread$ ) blocked_threads;
    279217
    280         // Spin lock used for mutual exclusion
    281         __spinlock_t lock;
    282 
    283         // flag showing if lock is held
    284218        bool held:1;
    285 
    286         #ifdef __CFA_DEBUG__
    287         // for deadlock detection
    288         struct thread$ * owner;
    289         #endif
    290219};
    291220
    … …  
    302231static inline void lock(fast_block_lock & this) with(this) {
    303232        lock( lock __cfaabi_dbg_ctx2 );
    304 
    305         #ifdef __CFA_DEBUG__
    306         assert(!(held && owner == active_thread()));
    307         #endif
    308233        if (held) {
    309234                insert_last( blocked_threads, *active_thread() );
    … …  
    313238        }
    314239        held = true;
    315         #ifdef __CFA_DEBUG__
    316         owner = active_thread();
    317         #endif
    318240        unlock( lock );
    319241}
    … …  
    324246        thread$ * t = &try_pop_front( blocked_threads );
    325247        held = ( t ? true : false );
    326         #ifdef __CFA_DEBUG__
    327         owner = ( t ? t : 0p );
    328         #endif
    329248        unpark( t );
    330249        unlock( lock );
    … …  
    334253static inline size_t on_wait(fast_block_lock & this) { unlock(this); return 0; }
    335254static inline void on_wakeup(fast_block_lock & this, size_t recursion ) { }
    336 
    337 //-----------------------------------------------------------------------------
    338 // simple_owner_lock
    339 
    340 // pthread owner lock
    341 // - reacquire for cond var
    342 // - recursive acquisition
    343 // - ownership
    344 struct simple_owner_lock {
    345         // List of blocked threads
    346         dlist( thread$ ) blocked_threads;
    347 
    348         // Spin lock used for mutual exclusion
    349         __spinlock_t lock;
    350 
    351         // owner showing if lock is held
    352         struct thread$ * owner;
    353 
    354         size_t recursion_count;
    355 };
    356 
    357 static inline void  ?{}( simple_owner_lock & this ) with(this) {
    358         lock{};
    359         blocked_threads{};
    360         owner = 0p;
    361         recursion_count = 0;
    362 }
    363 static inline void ^?{}( simple_owner_lock & this ) {}
    364 static inline void ?{}( simple_owner_lock & this, simple_owner_lock this2 ) = void;
    365 static inline void ?=?( simple_owner_lock & this, simple_owner_lock this2 ) = void;
    366 
    367 static inline void lock(simple_owner_lock & this) with(this) {
    368         if (owner == active_thread()) {
    369                 recursion_count++;
    370                 return;
    371         }
    372         lock( lock __cfaabi_dbg_ctx2 );
    373 
    374         if (owner != 0p) {
    375                 insert_last( blocked_threads, *active_thread() );
    376                 unlock( lock );
    377                 park( );
    378                 return;
    379         }
    380         owner = active_thread();
    381         recursion_count = 1;
    382         unlock( lock );
    383 }
    384 
    385 // TODO: fix duplicate def issue and bring this back
    386 // void pop_and_set_new_owner( simple_owner_lock & this ) with( this ) {
    387         // thread$ * t = &try_pop_front( blocked_threads );
    388         // owner = t;
    389         // recursion_count = ( t ? 1 : 0 );
    390         // unpark( t );
    391 // }
    392 
    393 static inline void unlock(simple_owner_lock & this) with(this) {
    394         lock( lock __cfaabi_dbg_ctx2 );
    395         /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
    396         /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
    397         // if recursion count is zero release lock and set new owner if one is waiting
    398         recursion_count--;
    399         if ( recursion_count == 0 ) {
    400                 // pop_and_set_new_owner( this );
    401                 thread$ * t = &try_pop_front( blocked_threads );
    402                 owner = t;
    403                 recursion_count = ( t ? 1 : 0 );
    404                 unpark( t );
    405         }
    406         unlock( lock );
    407 }
    408 
    409 static inline void on_notify(simple_owner_lock & this, struct thread$ * t ) with(this) {
    410         lock( lock __cfaabi_dbg_ctx2 );
    411         // lock held
    412         if ( owner != 0p ) {
    413                 insert_last( blocked_threads, *t );
    414                 unlock( lock );
    415         }
    416         // lock not held
    417         else {
    418                 owner = t;
    419                 recursion_count = 1;
    420                 unpark( t );
    421                 unlock( lock );
    422         }
    423 }
    424 
    425 static inline size_t on_wait(simple_owner_lock & this) with(this) {
    426         lock( lock __cfaabi_dbg_ctx2 );
    427         /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
    428         /* paranoid */ verifyf( owner == active_thread(), "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
    429 
    430         size_t ret = recursion_count;
    431 
    432         // pop_and_set_new_owner( this );
    433 
    434         thread$ * t = &try_pop_front( blocked_threads );
    435         owner = t;
    436         recursion_count = ( t ? 1 : 0 );
    437         unpark( t );
    438 
    439         unlock( lock );
    440         return ret;
    441 }
    442 
    443 static inline void on_wakeup(simple_owner_lock & this, size_t recursion ) with(this) { recursion_count = recursion; }
    444 
    445 //-----------------------------------------------------------------------------
    446 // Spin Queue Lock
    447 
    448 // - No reacquire for cond var
    449 // - No recursive acquisition
    450 // - No ownership
    451 // - spin lock with no locking/atomics in unlock
    452 struct spin_queue_lock {
    453         // Spin lock used for mutual exclusion
    454         mcs_spin_lock lock;
    455 
    456         // flag showing if lock is held
    457         volatile bool held;
    458 
    459         #ifdef __CFA_DEBUG__
    460         // for deadlock detection
    461         struct thread$ * owner;
    462         #endif
    463 };
    464 
    465 static inline void  ?{}( spin_queue_lock & this ) with(this) {
    466         lock{};
    467         held = false;
    468 }
    469 static inline void ^?{}( spin_queue_lock & this ) {}
    470 static inline void ?{}( spin_queue_lock & this, spin_queue_lock this2 ) = void;
    471 static inline void ?=?( spin_queue_lock & this, spin_queue_lock this2 ) = void;
    472 
    473 // if this is called recursively IT WILL DEADLOCK!!!!!
    474 static inline void lock(spin_queue_lock & this) with(this) {
    475         mcs_spin_node node;
    476         #ifdef __CFA_DEBUG__
    477         assert(!(held && owner == active_thread()));
    478         #endif
    479         lock( lock, node );
    480         while(__atomic_load_n(&held, __ATOMIC_SEQ_CST)) Pause();
    481         __atomic_store_n(&held, true, __ATOMIC_SEQ_CST);
    482         unlock( lock, node );
    483         #ifdef __CFA_DEBUG__
    484         owner = active_thread();
    485         #endif
    486 }
    487 
    488 static inline void unlock(spin_queue_lock & this) with(this) {
    489         #ifdef __CFA_DEBUG__
    490         owner = 0p;
    491         #endif
    492         __atomic_store_n(&held, false, __ATOMIC_RELEASE);
    493 }
    494 
    495 static inline void on_notify(spin_queue_lock & this, struct thread$ * t ) { unpark(t); }
    496 static inline size_t on_wait(spin_queue_lock & this) { unlock(this); return 0; }
    497 static inline void on_wakeup(spin_queue_lock & this, size_t recursion ) { }
    498 
    499 
    500 //-----------------------------------------------------------------------------
    501 // MCS Block Spin Lock
    502 
    503 // - No reacquire for cond var
    504 // - No recursive acquisition
    505 // - No ownership
    506 // - Blocks but first node spins (like spin queue but blocking for not first thd)
    507 struct mcs_block_spin_lock {
    508         // Spin lock used for mutual exclusion
    509         mcs_lock lock;
    510 
    511         // flag showing if lock is held
    512         volatile bool held;
    513 
    514         #ifdef __CFA_DEBUG__
    515         // for deadlock detection
    516         struct thread$ * owner;
    517         #endif
    518 };
    519 
    520 static inline void  ?{}( mcs_block_spin_lock & this ) with(this) {
    521         lock{};
    522         held = false;
    523 }
    524 static inline void ^?{}( mcs_block_spin_lock & this ) {}
    525 static inline void ?{}( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void;
    526 static inline void ?=?( mcs_block_spin_lock & this, mcs_block_spin_lock this2 ) = void;
    527 
    528 // if this is called recursively IT WILL DEADLOCK!!!!!
    529 static inline void lock(mcs_block_spin_lock & this) with(this) {
    530         mcs_node node;
    531         #ifdef __CFA_DEBUG__
    532         assert(!(held && owner == active_thread()));
    533         #endif
    534         lock( lock, node );
    535         while(held) Pause();
    536         held = true;
    537         unlock( lock, node );
    538         #ifdef __CFA_DEBUG__
    539         owner = active_thread();
    540         #endif
    541 }
    542 
    543 static inline void unlock(mcs_block_spin_lock & this) with(this) {
    544         #ifdef __CFA_DEBUG__
    545         owner = 0p;
    546         #endif
    547         held = false;
    548 }
    549 
    550 static inline void on_notify(mcs_block_spin_lock & this, struct thread$ * t ) { unpark(t); }
    551 static inline size_t on_wait(mcs_block_spin_lock & this) { unlock(this); return 0; }
    552 static inline void on_wakeup(mcs_block_spin_lock & this, size_t recursion ) { }
    553 
    554 //-----------------------------------------------------------------------------
    555 // Block Spin Lock
    556 
    557 // - No reacquire for cond var
    558 // - No recursive acquisition
    559 // - No ownership
    560 // - Blocks but first node spins (like spin queue but blocking for not first thd)
    561 struct block_spin_lock {
    562         // Spin lock used for mutual exclusion
    563         fast_block_lock lock;
    564 
    565         // flag showing if lock is held
    566         volatile bool held;
    567 
    568         #ifdef __CFA_DEBUG__
    569         // for deadlock detection
    570         struct thread$ * owner;
    571         #endif
    572 };
    573 
    574 static inline void  ?{}( block_spin_lock & this ) with(this) {
    575         lock{};
    576         held = false;
    577 }
    578 static inline void ^?{}( block_spin_lock & this ) {}
    579 static inline void ?{}( block_spin_lock & this, block_spin_lock this2 ) = void;
    580 static inline void ?=?( block_spin_lock & this, block_spin_lock this2 ) = void;
    581 
    582 // if this is called recursively IT WILL DEADLOCK!!!!!
    583 static inline void lock(block_spin_lock & this) with(this) {
    584         #ifdef __CFA_DEBUG__
    585         assert(!(held && owner == active_thread()));
    586         #endif
    587         lock( lock );
    588         while(held) Pause();
    589         held = true;
    590         unlock( lock );
    591         #ifdef __CFA_DEBUG__
    592         owner = active_thread();
    593         #endif
    594 }
    595 
    596 static inline void unlock(block_spin_lock & this) with(this) {
    597         #ifdef __CFA_DEBUG__
    598         owner = 0p;
    599         #endif
    600         held = false;
    601 }
    602 
    603 static inline void on_notify(block_spin_lock & this, struct thread$ * t ) { unpark(t); }
    604 static inline size_t on_wait(block_spin_lock & this) { unlock(this); return 0; }
    605 static inline void on_wakeup(block_spin_lock & this, size_t recursion ) { }
    606255
    607256//-----------------------------------------------------------------------------
    … …  
    683332        // - signalling without holding branded lock is UNSAFE!
    684333        // - only allows usage of one lock, cond var is branded after usage
    685 
    686334        struct fast_cond_var {
    687335                // List of blocked threads
    688336                dlist( info_thread(L) ) blocked_threads;
     337
    689338                #ifdef __CFA_DEBUG__
    690339                L * lock_used;
    … …  
    692341        };
    693342
     343
    694344        void  ?{}( fast_cond_var(L) & this );
    695345        void ^?{}( fast_cond_var(L) & this );
    … …  
    699349
    700350        uintptr_t front( fast_cond_var(L) & this );
     351
    701352        bool empty  ( fast_cond_var(L) & this );
    702353
    703354        void wait( fast_cond_var(L) & this, L & l );
    704355        void wait( fast_cond_var(L) & this, L & l, uintptr_t info );
    705 
    706 
    707         //-----------------------------------------------------------------------------
    708         // pthread_cond_var
    709         //
    710         // - cond var with minimal footprint
    711         // - supports operations needed for phthread cond
    712 
    713         struct pthread_cond_var {
    714                 dlist( info_thread(L) ) blocked_threads;
    715                 __spinlock_t lock;
    716         };
    717 
    718         void  ?{}( pthread_cond_var(L) & this );
    719         void ^?{}( pthread_cond_var(L) & this );
    720 
    721         bool notify_one( pthread_cond_var(L) & this );
    722         bool notify_all( pthread_cond_var(L) & this );
    723 
    724         uintptr_t front( pthread_cond_var(L) & this );
    725         bool empty ( pthread_cond_var(L) & this );
    726 
    727         void wait( pthread_cond_var(L) & this, L & l );
    728         void wait( pthread_cond_var(L) & this, L & l, uintptr_t info );
    729         bool wait( pthread_cond_var(L) & this, L & l, timespec t );
    730         bool wait( pthread_cond_var(L) & this, L & l, uintptr_t info, timespec t );
    731 }
     356}
Note: See TracChangeset for help on using the changeset viewer.