Index: libcfa/src/concurrency/locks.cfa =================================================================== --- libcfa/src/concurrency/locks.cfa (revision 62a7cc0ac31873baa3923dd92c537b60b4a3eac1) +++ libcfa/src/concurrency/locks.cfa (revision 1e6f632fe210f10e8a5aeaa25a8be00593f7e333) @@ -5,23 +5,32 @@ #include -/////////////////////////////////////////////////////////////////// -//// info_thread -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// info_thread forall(dtype L | is_blocking_lock(L)) { - void ?{}( info_thread(L) & this, $thread * t ) { - ((Seqable &) this){}; - this.t = t; - this.lock = 0p; - } - - void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ) { + struct info_thread { + // used to put info_thread on a dl queue (aka sequence) + inline Seqable; + + // waiting thread + struct $thread * t; + + // shadow field + uintptr_t info; + + // lock that is passed to wait() (if one is passed) + L * lock; + + // true when signalled and false when timeout wakes thread + bool signalled; + }; + + void ?{}( info_thread(L) & this, $thread * t, uintptr_t info, L * l ) { ((Seqable &) this){}; this.t = t; this.info = info; - this.lock = 0p; - } - - void ^?{}( info_thread(L) & this ){ } + this.lock = l; + } + + void ^?{}( info_thread(L) & this ) {} info_thread(L) *& Back( info_thread(L) * this ) { @@ -34,8 +43,6 @@ } -/////////////////////////////////////////////////////////////////// -//// Blocking Locks -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// Blocking Locks void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ) { this.lock{}; @@ -49,25 +56,33 @@ void ^?{}( blocking_lock & this ) {} -void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };} +void ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };} void ^?{}( single_acquisition_lock & this ) {} -void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };} +void ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };} void ^?{}( owner_lock & this ) {} -void ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };} +void ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };} void ^?{}( multiple_acquisition_lock & this ) {} void lock( blocking_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); - if ( owner == active_thread() && !multi_acquisition) { // single acquisition lock is held by current thread - abort("A single acquisition lock holder attempted to reacquire the lock resulting in a deadlock."); - } else if ( owner != 0p && owner != active_thread() ) { // lock is held by some other thread - addTail( blocked_threads, *active_thread() ); + $thread * thrd = active_thread(); + + // single acquisition lock is held by current thread + /* paranoid */ verifyf( owner != thrd || multi_acquisition, "Single acquisition lock holder (%p) attempted to reacquire the lock %p resulting in a deadlock.", owner, &this ); + + // lock is held by some other thread + if ( owner != 0p && owner != thrd ) { + addTail( blocked_threads, *thrd ); wait_count++; unlock( lock ); park( ); - } else if ( owner == active_thread() && multi_acquisition ) { // multi acquisition lock is held by current thread + } + // multi acquisition lock is held by current thread + else if ( owner == thrd && multi_acquisition ) { recursion_count++; unlock( lock ); - } else { // lock isn't held - owner = active_thread(); + } + // lock isn't held + else { + owner = thrd; recursion_count = 1; unlock( lock ); @@ -78,22 +93,19 @@ bool ret = false; lock( lock __cfaabi_dbg_ctx2 ); - if ( owner == 0p ) { // lock isn't held + + // lock isn't held + if ( owner == 0p ) { owner = active_thread(); recursion_count = 1; ret = true; - } else if ( owner == active_thread() && multi_acquisition ) { // multi acquisition lock is held by current thread + } + // multi acquisition lock is held by current thread + else if ( owner == active_thread() && multi_acquisition ) { recursion_count++; ret = true; } + unlock( lock ); return ret; -} - -void unlock_error_check( blocking_lock & this ) with( this ) { - if ( owner == 0p ){ // lock isn't held - abort( "There was an attempt to release a lock that isn't held" ); - } else if ( strict_owner && owner != active_thread() ) { - abort( "A thread other than the owner attempted to release an owner lock" ); - } } @@ -108,7 +120,10 @@ void unlock( blocking_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); - unlock_error_check( this ); + /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this ); + /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this ); + + // if recursion count is zero release lock and set new owner if one is waiting recursion_count--; - if ( recursion_count == 0 ) { // if recursion count is zero release lock and set new owner if one is waiting + if ( recursion_count == 0 ) { pop_and_set_new_owner( this ); } @@ -129,10 +144,13 @@ void on_notify( blocking_lock & this, $thread * t ) with( this ) { - lock( lock __cfaabi_dbg_ctx2 ); - if ( owner != 0p ) { // lock held + lock( lock __cfaabi_dbg_ctx2 ); + // lock held + if ( owner != 0p ) { addTail( blocked_threads, *t ); wait_count++; unlock( lock ); - } else { // lock not held + } + // lock not held + else { owner = t; recursion_count = 1; @@ -143,65 +161,83 @@ void on_wait( blocking_lock & this ) with( this ) { - lock( lock __cfaabi_dbg_ctx2 ); - unlock_error_check( this ); + lock( lock __cfaabi_dbg_ctx2 ); + /* paranoid */ verifyf( owner != 0p, "Attempt to release lock %p that isn't held", &this ); + /* paranoid */ verifyf( owner == active_thread() || !strict_owner, "Thread %p other than the owner %p attempted to release owner lock %p", owner, active_thread(), &this ); + pop_and_set_new_owner( this ); unlock( lock ); } -/////////////////////////////////////////////////////////////////// -//// Overloaded routines for traits -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// Overloaded routines for traits // These routines are temporary until an inheritance bug is fixed - -void lock( single_acquisition_lock & this ){ lock( (blocking_lock &)this ); } -void unlock( single_acquisition_lock & this ){ unlock( (blocking_lock &)this ); } -void on_notify( single_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); } -void on_wait( single_acquisition_lock & this ){ on_wait( (blocking_lock &)this ); } -void set_recursion_count( single_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); } -size_t get_recursion_count( single_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); } - -void lock( owner_lock & this ){ lock( (blocking_lock &)this ); } -void unlock( owner_lock & this ){ unlock( (blocking_lock &)this ); } -void on_notify( owner_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); } -void on_wait( owner_lock & this ){ on_wait( (blocking_lock &)this ); } -void set_recursion_count( owner_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); } -size_t get_recursion_count( owner_lock & this ){ return get_recursion_count( (blocking_lock &)this ); } - -void lock( multiple_acquisition_lock & this ){ lock( (blocking_lock &)this ); } -void unlock( multiple_acquisition_lock & this ){ unlock( (blocking_lock &)this ); } -void on_notify( multiple_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); } -void on_wait( multiple_acquisition_lock & this ){ on_wait( (blocking_lock &)this ); } -void set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); } +void lock ( single_acquisition_lock & this ) { lock ( (blocking_lock &)this ); } +void unlock ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); } +void on_wait ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); } +void on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); } +void set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); } +size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); } + +void lock ( owner_lock & this ) { lock ( (blocking_lock &)this ); } +void unlock ( owner_lock & this ) { unlock ( (blocking_lock &)this ); } +void on_wait ( owner_lock & this ) { on_wait( (blocking_lock &)this ); } +void on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); } +void set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); } +size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); } + +void lock ( multiple_acquisition_lock & this ) { lock ( (blocking_lock &)this ); } +void unlock ( multiple_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); } +void on_wait ( multiple_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); } +void on_notify( multiple_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); } +void set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); } size_t get_recursion_count( multiple_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); } -/////////////////////////////////////////////////////////////////// -//// condition variable -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// alarm node wrapper forall(dtype L | is_blocking_lock(L)) { + struct alarm_node_wrap { + alarm_node_t alarm_node; + condition_variable(L) * cond; + info_thread(L) * i; + }; + + void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) { + this.alarm_node{ callback, alarm, period }; + this.cond = c; + this.i = i; + } + + void ^?{}( alarm_node_wrap(L) & this ) { } void timeout_handler ( alarm_node_wrap(L) & this ) with( this ) { - // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin. - lock( cond->lock __cfaabi_dbg_ctx2 ); - - // this check is necessary to avoid a race condition since this timeout handler - // may still be called after a thread has been removed from the queue but - // before the alarm is unregistered - if ( listed(i) ) { // is thread on queue - i->signalled = false; - remove( cond->blocked_threads, *i ); // remove this thread O(1) + // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin. + lock( cond->lock __cfaabi_dbg_ctx2 ); + + // this check is necessary to avoid a race condition since this timeout handler + // may still be called after a thread has been removed from the queue but + // before the alarm is unregistered + if ( listed(i) ) { // is thread on queue + i->signalled = false; + // remove this thread O(1) + remove( cond->blocked_threads, *i ); cond->count--; if( i->lock ) { - on_notify(*i->lock, i->t); // call lock's on_notify if a lock was passed - } else { - unpark( i->t ); // otherwise wake thread - } - } - unlock( cond->lock ); + // call lock's on_notify if a lock was passed + on_notify(*i->lock, i->t); + } else { + // otherwise wake thread + unpark( i->t ); + } + } + unlock( cond->lock ); } // this casts the alarm node to our wrapped type since we used type erasure void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); } +} + +//----------------------------------------------------------------------------- +// condition variable +forall(dtype L | is_blocking_lock(L)) { void ?{}( condition_variable(L) & this ){ @@ -212,10 +248,4 @@ void ^?{}( condition_variable(L) & this ){ } - - void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback ) { - this.alarm_node{ callback, alarm, period }; - } - - void ^?{}( alarm_node_wrap(L) & this ) { } void process_popped( condition_variable(L) & this, info_thread(L) & popped ) with( this ) { @@ -224,7 +254,9 @@ count--; if (popped.lock) { - on_notify(*popped.lock, popped.t); // if lock passed call on_notify + // if lock passed call on_notify + on_notify(*popped.lock, popped.t); } else { - unpark(popped.t); // otherwise wake thread + // otherwise wake thread + unpark(popped.t); } } @@ -258,8 +290,10 @@ size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) { - addTail( blocked_threads, *i ); // add info_thread to waiting queue + // add info_thread to waiting queue + addTail( blocked_threads, *i ); count++; size_t recursion_count = 0; - if (i->lock) { // if lock was passed get recursion count to reset to after waking thread + if (i->lock) { + // if lock was passed get recursion count to reset to after waking thread recursion_count = get_recursion_count(*i->lock); on_wait( *i->lock ); @@ -273,7 +307,15 @@ size_t recursion_count = queue_and_get_recursion(this, &i); unlock( lock ); - park( ); // blocks here - if (i.lock) set_recursion_count(*i.lock, recursion_count); // resets recursion count here after waking - } + + // blocks here + park( ); + + // resets recursion count here after waking + if (i.lock) set_recursion_count(*i.lock, recursion_count); + } + + #define WAIT( u, l ) \ + info_thread( L ) i = { active_thread(), u, l }; \ + queue_info_thread( this, i ); // helper for wait()'s' with a timeout @@ -281,86 +323,35 @@ lock( lock __cfaabi_dbg_ctx2 ); size_t recursion_count = queue_and_get_recursion(this, &info); - alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast }; - node_wrap.cond = &this; - node_wrap.i = &info; + alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast, &this, &info }; register_self( &node_wrap.alarm_node ); unlock( lock ); + + // blocks here park(); - unregister_self( &node_wrap.alarm_node ); // unregisters alarm so it doesn't go off if this happens first - if (info.lock) set_recursion_count(*info.lock, recursion_count); // resets recursion count here after waking - } - - void wait( condition_variable(L) & this ) with(this) { - info_thread( L ) i = { active_thread() }; - queue_info_thread( this, i ); - } - - void wait( condition_variable(L) & this, uintptr_t info ) with(this) { - info_thread( L ) i = { active_thread(), info }; - queue_info_thread( this, i ); - } - - bool wait( condition_variable(L) & this, Duration duration ) with(this) { - info_thread( L ) i = { active_thread() }; - queue_info_thread_timeout(this, i, __kernel_get_time() + duration ); + + // unregisters alarm so it doesn't go off if this happens first + unregister_self( &node_wrap.alarm_node ); + + // resets recursion count here after waking + if (info.lock) set_recursion_count(*info.lock, recursion_count); + } + + #define WAIT_TIME( u, l, t ) \ + info_thread( L ) i = { active_thread(), u, l }; \ + queue_info_thread_timeout(this, i, t ); \ return i.signalled; - } - - bool wait( condition_variable(L) & this, uintptr_t info, Duration duration ) with(this) { - info_thread( L ) i = { active_thread(), info }; - queue_info_thread_timeout(this, i, __kernel_get_time() + duration ); - return i.signalled; - } - - bool wait( condition_variable(L) & this, Time time ) with(this) { - info_thread( L ) i = { active_thread() }; - queue_info_thread_timeout(this, i, time); - return i.signalled; - } - - bool wait( condition_variable(L) & this, uintptr_t info, Time time ) with(this) { - info_thread( L ) i = { active_thread(), info }; - queue_info_thread_timeout(this, i, time); - return i.signalled; - } - - void wait( condition_variable(L) & this, L & l ) with(this) { - info_thread(L) i = { active_thread() }; - i.lock = &l; - queue_info_thread( this, i ); - } - - void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { - info_thread(L) i = { active_thread(), info }; - i.lock = &l; - queue_info_thread( this, i ); - } - - bool wait( condition_variable(L) & this, L & l, Duration duration ) with(this) { - info_thread(L) i = { active_thread() }; - i.lock = &l; - queue_info_thread_timeout(this, i, __kernel_get_time() + duration ); - return i.signalled; - } - - bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { - info_thread(L) i = { active_thread(), info }; - i.lock = &l; - queue_info_thread_timeout(this, i, __kernel_get_time() + duration ); - return i.signalled; - } - - bool wait( condition_variable(L) & this, L & l, Time time ) with(this) { - info_thread(L) i = { active_thread() }; - i.lock = &l; - queue_info_thread_timeout(this, i, time ); - return i.signalled; - } - - bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time ) with(this) { - info_thread(L) i = { active_thread(), info }; - i.lock = &l; - queue_info_thread_timeout(this, i, time ); - return i.signalled; - } -} + + void wait( condition_variable(L) & this ) with(this) { WAIT( 0, 0p ) } + void wait( condition_variable(L) & this, uintptr_t info ) with(this) { WAIT( info, 0p ) } + void wait( condition_variable(L) & this, L & l ) with(this) { WAIT( 0, &l ) } + void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { WAIT( info, &l ) } + + bool wait( condition_variable(L) & this, Duration duration ) with(this) { WAIT_TIME( 0 , 0p , __kernel_get_time() + duration ) } + bool wait( condition_variable(L) & this, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, 0p , __kernel_get_time() + duration ) } + bool wait( condition_variable(L) & this, Time time ) with(this) { WAIT_TIME( 0 , 0p , time ) } + bool wait( condition_variable(L) & this, uintptr_t info, Time time ) with(this) { WAIT_TIME( info, 0p , time ) } + bool wait( condition_variable(L) & this, L & l, Duration duration ) with(this) { WAIT_TIME( 0 , &l , __kernel_get_time() + duration ) } + bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , __kernel_get_time() + duration ) } + bool wait( condition_variable(L) & this, L & l, Time time ) with(this) { WAIT_TIME( 0 , &l , time ) } + bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time ) with(this) { WAIT_TIME( info, &l , time ) } +} Index: libcfa/src/concurrency/locks.hfa =================================================================== --- libcfa/src/concurrency/locks.hfa (revision 62a7cc0ac31873baa3923dd92c537b60b4a3eac1) +++ libcfa/src/concurrency/locks.hfa (revision 1e6f632fe210f10e8a5aeaa25a8be00593f7e333) @@ -3,5 +3,4 @@ #include -#include "bits/algorithm.hfa" #include "bits/locks.hfa" #include "bits/sequence.hfa" @@ -11,37 +10,27 @@ #include "time_t.hfa" #include "time.hfa" -#include -#include "alarm.hfa" -/////////////////////////////////////////////////////////////////// -//// is_blocking_lock -/////////////////////////////////////////////////////////////////// +//----------------------------------------------------------------------------- +// is_blocking_lock +trait is_blocking_lock(dtype L | sized(L)) { + // For synchronization locks to use when acquiring + void on_notify( L &, struct $thread * ); -trait is_blocking_lock(dtype L | sized(L)) { - void on_notify( L &, struct $thread * ); // For synchronization locks to use when acquiring - void on_wait( L & ); // For synchronization locks to use when releasing - size_t get_recursion_count( L & ); // to get recursion count for cond lock to reset after waking - void set_recursion_count( L &, size_t recursion ); // to set recursion count after getting signalled; + // For synchronization locks to use when releasing + void on_wait( L & ); + + // to get recursion count for cond lock to reset after waking + size_t get_recursion_count( L & ); + + // to set recursion count after getting signalled; + void set_recursion_count( L &, size_t recursion ); }; -/////////////////////////////////////////////////////////////////// -//// info_thread -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// info_thread // the info thread is a wrapper around a thread used // to store extra data for use in the condition variable forall(dtype L | is_blocking_lock(L)) { - struct info_thread { - inline Seqable; // used to put info_thread on a dl queue (aka sequence) - struct $thread * t; // waiting thread - uintptr_t info; // shadow field - L * lock; // lock that is passed to wait() (if one is passed) - bool signalled; // true when signalled and false when timeout wakes thread - }; - - - void ?{}( info_thread(L) & this, $thread * t ); - void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ); - void ^?{}( info_thread(L) & this ); + struct info_thread; // for use by sequence @@ -50,8 +39,6 @@ } -/////////////////////////////////////////////////////////////////// -//// Blocking Locks -/////////////////////////////////////////////////////////////////// - +//----------------------------------------------------------------------------- +// Blocking Locks struct blocking_lock { // Spin lock used for mutual exclusion @@ -89,14 +76,14 @@ }; -void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ); +void ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner ); void ^?{}( blocking_lock & this ); -void ?{}( single_acquisition_lock & this ); +void ?{}( single_acquisition_lock & this ); void ^?{}( single_acquisition_lock & this ); -void ?{}( owner_lock & this ); +void ?{}( owner_lock & this ); void ^?{}( owner_lock & this ); -void ?{}( multiple_acquisition_lock & this ); +void ?{}( multiple_acquisition_lock & this ); void ^?{}( multiple_acquisition_lock & this ); @@ -131,7 +118,6 @@ size_t get_recursion_count( multiple_acquisition_lock & this ); -/////////////////////////////////////////////////////////////////// -//// Synchronization Locks -/////////////////////////////////////////////////////////////////// +//----------------------------------------------------------------------------- +// Synchronization Locks forall(dtype L | is_blocking_lock(L)) { struct condition_variable { @@ -146,21 +132,6 @@ }; - void ?{}( condition_variable(L) & this ); + void ?{}( condition_variable(L) & this ); void ^?{}( condition_variable(L) & this ); - - struct alarm_node_wrap { - alarm_node_t alarm_node; - - condition_variable(L) * cond; - - info_thread(L) * i; - }; - - void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback ); - void ^?{}( alarm_node_wrap(L) & this ); - - void alarm_node_callback( alarm_node_wrap(L) & this ); - - void alarm_node_wrap_cast( alarm_node_t & a ); bool notify_one( condition_variable(L) & this ); @@ -169,6 +140,6 @@ uintptr_t front( condition_variable(L) & this ); - bool empty( condition_variable(L) & this ); - int counter( condition_variable(L) & this ); + bool empty ( condition_variable(L) & this ); + int counter( condition_variable(L) & this ); void wait( condition_variable(L) & this ); Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision 62a7cc0ac31873baa3923dd92c537b60b4a3eac1) +++ libcfa/src/concurrency/thread.cfa (revision 1e6f632fe210f10e8a5aeaa25a8be00593f7e333) @@ -133,5 +133,5 @@ this_thrd->context.[SP, FP] = this_thrd->self_cor.context.[SP, FP]; - verify( this_thrd->context.SP ); + /* paranoid */ verify( this_thrd->context.SP ); __schedule_thread( this_thrd );