Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/locks.cfa

    r4aeaee5 rac5816d  
    11#include "locks.hfa"
    22#include "kernel_private.hfa"
    3 #include <stdlib.h>
    4 #include <stdio.h>
    53
    64#include <kernel.hfa>
    75#include <stdlib.hfa>
    8 #include <thread.hfa>
    9 
    10 ///////////////////////////////////////////////////////////////////
    11 //// info_thread
    12 ///////////////////////////////////////////////////////////////////
    13 
     6
     7//-----------------------------------------------------------------------------
     8// info_thread
    149forall(dtype L | is_blocking_lock(L)) {
    15         void ?{}( info_thread(L) & this, $thread * t ) {
    16                 ((Seqable &) this){};
    17                 this.t = t;
    18                 this.lock = 0p;
    19                 this.listed = false;
    20         }
    21 
    22         void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ) {
     10        struct info_thread {
     11                // used to put info_thread on a dl queue (aka sequence)
     12                inline Seqable;
     13
     14                // waiting thread
     15                struct $thread * t;
     16
     17                // shadow field
     18                uintptr_t info;
     19
     20                // lock that is passed to wait() (if one is passed)
     21                L * lock;
     22
     23                // true when signalled and false when timeout wakes thread
     24                bool signalled;
     25        };
     26
     27        void ?{}( info_thread(L) & this, $thread * t, uintptr_t info, L * l ) {
    2328                ((Seqable &) this){};
    2429                this.t = t;
    2530                this.info = info;
    26                 this.lock = 0p;
    27                 this.listed = false;
    28         }
    29 
    30         void ^?{}( info_thread(L) & this ){ }
    31 }
    32 
    33 ///////////////////////////////////////////////////////////////////
    34 //// Blocking Locks
    35 ///////////////////////////////////////////////////////////////////
    36 
     31                this.lock = l;
     32        }
     33
     34        void ^?{}( info_thread(L) & this ) {}
     35
     36        info_thread(L) *& Back( info_thread(L) * this ) {
     37                return (info_thread(L) *)Back( (Seqable *)this );
     38        }
     39
     40        info_thread(L) *& Next( info_thread(L) * this ) {
     41                return (info_thread(L) *)Next( (Colable *)this );
     42        }
     43}
     44
     45//-----------------------------------------------------------------------------
     46// Blocking Locks
    3747void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ) {
    3848        this.lock{};
    … …  
    4656
    4757void ^?{}( blocking_lock & this ) {}
    48 void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
     58void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
    4959void ^?{}( single_acquisition_lock & this ) {}
    50 void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
     60void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
    5161void ^?{}( owner_lock & this ) {}
    52 void ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };}
     62void  ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };}
    5363void ^?{}( multiple_acquisition_lock & this ) {}
    5464
    5565void lock( blocking_lock & this ) with( this ) {
    5666        lock( lock __cfaabi_dbg_ctx2 );
    57         if ( owner == active_thread() && !multi_acquisition) {
    58                 abort("A single acquisition lock holder attempted to reacquire the lock resulting in a deadlock.");
    59         } else if ( owner != 0p && owner != active_thread() ) {
    60                 append( blocked_threads, active_thread() );
     67        $thread * thrd = active_thread();
     68
     69        // single acquisition lock is held by current thread
     70        /* paranoid */ verifyf( owner != thrd || multi_acquisition, "Single acquisition lock holder (%p) attempted to reacquire the lock %p resulting in a deadlock.", owner, &this );
     71
     72        // lock is held by some other thread
     73        if ( owner != 0p && owner != thrd ) {
     74                addTail( blocked_threads, *thrd );
    6175                wait_count++;
    6276                unlock( lock );
    6377                park( );
    64         } else if ( owner == active_thread() && multi_acquisition ) {
     78        }
     79        // multi acquisition lock is held by current thread
     80        else if ( owner == thrd && multi_acquisition ) {
    6581                recursion_count++;
    6682                unlock( lock );
    67         } else {
    68                 owner = active_thread();
     83        }
     84        // lock isn't held
     85        else {
     86                owner = thrd;
    6987                recursion_count = 1;
    7088                unlock( lock );
    … …  
    7593        bool ret = false;
    7694        lock( lock __cfaabi_dbg_ctx2 );
     95
     96        // lock isn't held
    7797        if ( owner == 0p ) {
    7898                owner = active_thread();
    7999                recursion_count = 1;
    80100                ret = true;
    81         } else if ( owner == active_thread() && multi_acquisition ) {
     101        }
     102        // multi acquisition lock is held by current thread
     103        else if ( owner == active_thread() && multi_acquisition ) {
    82104                recursion_count++;
    83105                ret = true;
    84106        }
     107
    85108        unlock( lock );
    86109        return ret;
    87110}
    88111
    89 void unlock_error_check( blocking_lock & this ) with( this ) {
    90         if ( owner == 0p ){ // no owner implies lock isn't held
    91                 abort( "There was an attempt to release a lock that isn't held" );
    92         } else if ( strict_owner && owner != active_thread() ) {
    93                 abort( "A thread other than the owner attempted to release an owner lock" );
    94         }
    95 }
    96 
    97112void pop_and_set_new_owner( blocking_lock & this ) with( this ) {
    98         $thread * t = pop_head( blocked_threads );
     113        $thread * t = &dropHead( blocked_threads );
    99114        owner = t;
    100115        recursion_count = ( t ? 1 : 0 );
    … …  
    105120void unlock( blocking_lock & this ) with( this ) {
    106121        lock( lock __cfaabi_dbg_ctx2 );
    107         unlock_error_check( this );
     122        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
     123        /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
     124
     125        // if recursion count is zero release lock and set new owner if one is waiting
    108126        recursion_count--;
    109127        if ( recursion_count == 0 ) {
    … …  
    125143}
    126144
    127 void add_( blocking_lock & this, $thread * t ) with( this ) {
    128     lock( lock __cfaabi_dbg_ctx2 );
     145void on_notify( blocking_lock & this, $thread * t ) with( this ) {
     146        lock( lock __cfaabi_dbg_ctx2 );
     147        // lock held
    129148        if ( owner != 0p ) {
    130                 append( blocked_threads, t );
     149                addTail( blocked_threads, *t );
    131150                wait_count++;
    132151                unlock( lock );
    133         } else {
     152        }
     153        // lock not held
     154        else {
    134155                owner = t;
    135156                recursion_count = 1;
    … …  
    139160}
    140161
    141 void remove_( blocking_lock & this ) with( this ) {
    142     lock( lock __cfaabi_dbg_ctx2 );
    143         unlock_error_check( this );
     162void on_wait( blocking_lock & this ) with( this ) {
     163        lock( lock __cfaabi_dbg_ctx2 );
     164        /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this );
     165        /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this );
     166
    144167        pop_and_set_new_owner( this );
    145168        unlock( lock );
    146169}
    147170
    148 ///////////////////////////////////////////////////////////////////
    149 //// Overloaded routines for traits
    150 ///////////////////////////////////////////////////////////////////
    151 
    152 // This is temporary until an inheritance bug is fixed
    153 
    154 void lock( single_acquisition_lock & this ){ lock( (blocking_lock &)this ); }
    155 void unlock( single_acquisition_lock & this ){ unlock( (blocking_lock &)this ); }
    156 void add_( single_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
    157 void remove_( single_acquisition_lock & this ){ remove_( (blocking_lock &)this ); }
    158 void set_recursion_count( single_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
    159 size_t get_recursion_count( single_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
    160 
    161 void lock( owner_lock & this ){ lock( (blocking_lock &)this ); }
    162 void unlock( owner_lock & this ){ unlock( (blocking_lock &)this ); }
    163 void add_( owner_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
    164 void remove_( owner_lock & this ){ remove_( (blocking_lock &)this ); }
    165 void set_recursion_count( owner_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
    166 size_t get_recursion_count( owner_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
    167 
    168 void lock( multiple_acquisition_lock & this ){ lock( (blocking_lock &)this ); }
    169 void unlock( multiple_acquisition_lock & this ){ unlock( (blocking_lock &)this ); }
    170 void add_( multiple_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); }
    171 void remove_( multiple_acquisition_lock & this ){ remove_( (blocking_lock &)this ); }
    172 void set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
     171//-----------------------------------------------------------------------------
     172// Overloaded routines for traits
     173// These routines are temporary until an inheritance bug is fixed
     174void   lock      ( single_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
     175void   unlock    ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
     176void   on_wait   ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
     177void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     178void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     179size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
     180
     181void   lock     ( owner_lock & this ) { lock   ( (blocking_lock &)this ); }
     182void   unlock   ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
     183void   on_wait  ( owner_lock & this ) { on_wait( (blocking_lock &)this ); }
     184void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     185void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     186size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
     187
     188void   lock     ( multiple_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
     189void   unlock   ( multiple_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
     190void   on_wait  ( multiple_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
     191void   on_notify( multiple_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); }
     192void   set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
    173193size_t get_recursion_count( multiple_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
    174194
    175 ///////////////////////////////////////////////////////////////////
    176 //// condition variable
    177 ///////////////////////////////////////////////////////////////////
    178 
     195//-----------------------------------------------------------------------------
     196// alarm node wrapper
    179197forall(dtype L | is_blocking_lock(L)) {
     198        struct alarm_node_wrap {
     199                alarm_node_t alarm_node;
     200                condition_variable(L) * cond;
     201                info_thread(L) * i;
     202        };
     203
     204        void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) {
     205                this.alarm_node{ callback, alarm, period };
     206                this.cond = c;
     207                this.i = i;
     208        }
     209
     210        void ^?{}( alarm_node_wrap(L) & this ) { }
    180211
    181212        void timeout_handler ( alarm_node_wrap(L) & this ) with( this ) {
    182         // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin.
    183             lock( cond->lock __cfaabi_dbg_ctx2 );
    184            
    185             if ( i->listed ) {                  // is thread on queue
    186                 cond->last_thread = i;          // REMOVE THIS AFTER DEBUG
    187                         remove( cond->blocked_threads, *i );             //remove this thread O(1)
     213                // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin.
     214                lock( cond->lock __cfaabi_dbg_ctx2 );
     215
     216                // this check is necessary to avoid a race condition since this timeout handler
     217                //      may still be called after a thread has been removed from the queue but
     218                //      before the alarm is unregistered
     219                if ( listed(i) ) {      // is thread on queue
     220                        i->signalled = false;
     221                        // remove this thread O(1)
     222                        remove( cond->blocked_threads, *i );
    188223                        cond->count--;
    189                         if( !i->lock ) {
     224                        if( i->lock ) {
     225                                // call lock's on_notify if a lock was passed
     226                                on_notify(*i->lock, i->t);
     227                        } else {
     228                                // otherwise wake thread
    190229                                unpark( i->t );
    191                 } else {
    192                         add_(*i->lock, i->t);                   // call lock's add_
    193                 }
    194             }
    195             unlock( cond->lock );
    196         }
    197 
     230                        }
     231                }
     232                unlock( cond->lock );
     233        }
     234
     235        // this casts the alarm node to our wrapped type since we used type erasure
    198236        void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); }
     237}
     238
     239//-----------------------------------------------------------------------------
     240// condition variable
     241forall(dtype L | is_blocking_lock(L)) {
    199242
    200243        void ?{}( condition_variable(L) & this ){
    … …  
    202245                this.blocked_threads{};
    203246                this.count = 0;
    204                 this.last_thread = 0p; // REMOVE AFTER DEBUG
    205247        }
    206248
    207249        void ^?{}( condition_variable(L) & this ){ }
    208 
    209         void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback ) {
    210                 this.alarm_node{ callback, alarm, period };
    211         }
    212 
    213         void ^?{}( alarm_node_wrap(L) & this ) { }
    214250
    215251        void process_popped( condition_variable(L) & this, info_thread(L) & popped ) with( this ) {
    216252                if(&popped != 0p) {
    217                         popped.listed = false;
     253                        popped.signalled = true;
    218254                        count--;
    219255                        if (popped.lock) {
    220                                 add_(*popped.lock, popped.t);
     256                                // if lock passed call on_notify
     257                                on_notify(*popped.lock, popped.t);
    221258                        } else {
     259                                // otherwise wake thread
    222260                                unpark(popped.t);
    223261                        }
    … …  
    252290
    253291        size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) {
     292                // add info_thread to waiting queue
    254293                addTail( blocked_threads, *i );
    255294                count++;
    256                 i->listed = true;
    257295                size_t recursion_count = 0;
    258296                if (i->lock) {
    259                         i->t->link.next = 1p;
     297                        // if lock was passed get recursion count to reset to after waking thread
    260298                        recursion_count = get_recursion_count(*i->lock);
    261                         remove_( *i->lock );
     299                        on_wait( *i->lock );
    262300                }
    263301                return recursion_count;
    … …  
    269307                size_t recursion_count = queue_and_get_recursion(this, &i);
    270308                unlock( lock );
    271                 park( ); // blocks here
    272                 if (i.lock) set_recursion_count(*i.lock, recursion_count); // resets recursion count here after waking
    273         }
     309
     310                // blocks here
     311                park( );
     312
     313                // resets recursion count here after waking
     314                if (i.lock) set_recursion_count(*i.lock, recursion_count);
     315        }
     316
     317        #define WAIT( u, l ) \
     318                info_thread( L ) i = { active_thread(), u, l }; \
     319                queue_info_thread( this, i );
    274320
    275321        // helper for wait()'s' with a timeout
    … …  
    277323                lock( lock __cfaabi_dbg_ctx2 );
    278324                size_t recursion_count = queue_and_get_recursion(this, &info);
    279                 alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast };
    280                 node_wrap.cond = &this;
    281                 node_wrap.i = &info;
     325                alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast, &this, &info };
    282326                register_self( &node_wrap.alarm_node );
    283327                unlock( lock );
     328
     329                // blocks here
    284330                park();
     331
     332                // unregisters alarm so it doesn't go off if this happens first
    285333                unregister_self( &node_wrap.alarm_node );
     334
     335                // resets recursion count here after waking
    286336                if (info.lock) set_recursion_count(*info.lock, recursion_count);
    287337        }
    288338
    289         void wait( condition_variable(L) & this ) with(this) {
    290                 info_thread( L ) i = { active_thread() };
    291                 queue_info_thread( this, i );
    292         }
    293 
    294         void wait( condition_variable(L) & this, uintptr_t info ) with(this) {
    295                 info_thread( L ) i = { active_thread(), info };
    296                 queue_info_thread( this, i );
    297         }
    298        
    299         void wait( condition_variable(L) & this, Duration duration ) with(this) {
    300                 info_thread( L ) i = { active_thread() };
    301                 queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
    302         }
    303 
    304         void wait( condition_variable(L) & this, uintptr_t info, Duration duration ) with(this) {
    305                 info_thread( L ) i = { active_thread(), info };
    306                 queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
    307         }
    308 
    309         void wait( condition_variable(L) & this, Time time ) with(this) {
    310                 info_thread( L ) i = { active_thread() };
    311                 queue_info_thread_timeout(this, i, time);
    312         }
    313 
    314         void wait( condition_variable(L) & this, uintptr_t info, Time time ) with(this) {
    315                 info_thread( L ) i = { active_thread(), info };
    316                 queue_info_thread_timeout(this, i, time);
    317         }
    318 
    319         void wait( condition_variable(L) & this, L & l ) with(this) {
    320                 info_thread(L) i = { active_thread() };
    321                 i.lock = &l;
    322                 queue_info_thread( this, i );
    323         }
    324 
    325         void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) {
    326                 info_thread(L) i = { active_thread(), info };
    327                 i.lock = &l;
    328                 queue_info_thread( this, i );
    329         }
    330        
    331         void wait( condition_variable(L) & this, L & l, Duration duration ) with(this) {
    332                 info_thread(L) i = { active_thread() };
    333                 i.lock = &l;
    334                 queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
    335         }
    336        
    337         void wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) {
    338                 info_thread(L) i = { active_thread(), info };
    339                 i.lock = &l;
    340                 queue_info_thread_timeout(this, i, __kernel_get_time() + duration );
    341         }
    342        
    343         void wait( condition_variable(L) & this, L & l, Time time ) with(this) {
    344                 info_thread(L) i = { active_thread() };
    345                 i.lock = &l;
    346                 queue_info_thread_timeout(this, i, time );
    347         }
    348        
    349         void wait( condition_variable(L) & this, L & l, uintptr_t info, Time time ) with(this) {
    350                 info_thread(L) i = { active_thread(), info };
    351                 i.lock = &l;
    352                 queue_info_thread_timeout(this, i, time );
    353         }
    354 }
     339        #define WAIT_TIME( u, l, t ) \
     340                info_thread( L ) i = { active_thread(), u, l }; \
     341                queue_info_thread_timeout(this, i, t ); \
     342                return i.signalled;
     343
     344        void wait( condition_variable(L) & this                        ) with(this) { WAIT( 0, 0p    ) }
     345        void wait( condition_variable(L) & this, uintptr_t info        ) with(this) { WAIT( info, 0p ) }
     346        void wait( condition_variable(L) & this, L & l                 ) with(this) { WAIT( 0, &l    ) }
     347        void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { WAIT( info, &l ) }
     348
     349        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , __kernel_get_time() + duration ) }
     350        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , __kernel_get_time() + duration ) }
     351        bool wait( condition_variable(L) & this, Time time                                ) with(this) { WAIT_TIME( 0   , 0p , time ) }
     352        bool wait( condition_variable(L) & this, uintptr_t info, Time time                ) with(this) { WAIT_TIME( info, 0p , time ) }
     353        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , __kernel_get_time() + duration ) }
     354        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , __kernel_get_time() + duration ) }
     355        bool wait( condition_variable(L) & this, L & l, Time time                         ) with(this) { WAIT_TIME( 0   , &l , time ) }
     356        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time         ) with(this) { WAIT_TIME( info, &l , time ) }
     357}
Note: See TracChangeset for help on using the changeset viewer.