Index: libcfa/src/bits/containers.hfa =================================================================== --- libcfa/src/bits/containers.hfa (revision a5a67ab897a37cb777e0553f71e8a72fff0efe62) +++ libcfa/src/bits/containers.hfa (revision 7b2a786f512308877bfeafe66231edaf0c9db719) @@ -17,5 +17,5 @@ #include "bits/align.hfa" #include "bits/defs.hfa" - +#include //----------------------------------------------------------------------------- // Array @@ -146,23 +146,23 @@ static inline forall( dtype T | is_node(T) ) { void ?{}( __queue(T) & this ) with( this ) { - head{ 1p }; - tail{ &head }; - verify(*tail == 1p); + (this.head){ 1p }; + (this.tail){ &this.head }; + verify(*this.tail == 1p); } void append( __queue(T) & this, T * val ) with( this ) { - verify(tail != 0p); - verify(*tail == 1p); - *tail = val; - tail = &get_next( *val ); - *tail = 1p; + verify(this.tail != 0p); + verify(*this.tail == 1p); + *this.tail = val; + this.tail = &get_next( *val ); + *this.tail = 1p; } T * peek( __queue(T) & this ) { verify(*this.tail == 1p); - T * head = this.head; - if( head != 1p ) { + T * front = this.head; + if( front != 1p ) { verify(*this.tail == 1p); - return head; + return front; } verify(*this.tail == 1p); @@ -172,14 +172,14 @@ T * pop_head( __queue(T) & this ) { verify(*this.tail == 1p); - T * head = this.head; - if( head != 1p ) { - this.head = get_next( *head ); - if( get_next( *head ) == 1p ) { + T * _head = this.head; + if( _head != 1p ) { + this.head = get_next( *_head ); + if( get_next( *_head ) == 1p ) { this.tail = &this.head; } - get_next( *head ) = 0p; + get_next( *_head ) = 0p; verify(*this.tail == 1p); - verify( get_next(*head) == 0p ); - return head; + verify( get_next(*_head) == 0p ); + return _head; } verify(*this.tail == 1p); @@ -193,12 +193,12 @@ (*it) = get_next( *val ); - if( tail == &get_next( *val ) ) { - tail = it; + if( this.tail == &get_next( *val ) ) { + this.tail = it; } get_next( *val ) = 0p; - verify( (head == 1p) == (&head == tail) ); - verify( *tail == 1p ); + verify( (this.head == 1p) == (&this.head == this.tail) ); + verify( *this.tail == 1p ); return val; } @@ -239,5 +239,5 @@ forall(dtype T ) static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { - this.head{ 0p }; + (this.head){ 0p }; this.__get = __get; } @@ -248,11 +248,11 @@ void push_front( __dllist(T) & this, T & node ) with( this ) { verify(__get); - if ( head ) { - __get( node ).next = head; - __get( node ).prev = __get( *head ).prev; + if ( this.head ) { + __get( node ).next = this.head; + __get( node ).prev = __get( *this.head ).prev; // inserted node must be consistent before it is seen // prevent code movement across barrier asm( "" : : : "memory" ); - __get( *head ).prev = &node; + __get( *this.head ).prev = &node; T & _prev = *__get( node ).prev; __get( _prev ).next = &node; @@ -264,14 +264,14 @@ // prevent code movement across barrier asm( "" : : : "memory" ); - head = &node; + this.head = &node; } void remove( __dllist(T) & this, T & node ) with( this ) { verify(__get); - if ( &node == head ) { - if ( __get( *head ).next == head ) { - head = 0p; + if ( &node == this.head ) { + if ( __get( *this.head ).next == this.head ) { + this.head = 0p; } else { - head = __get( *head ).next; + this.head = __get( *this.head ).next; } } Index: libcfa/src/concurrency/alarm.cfa =================================================================== --- libcfa/src/concurrency/alarm.cfa (revision a5a67ab897a37cb777e0553f71e8a72fff0efe62) +++ libcfa/src/concurrency/alarm.cfa (revision 7b2a786f512308877bfeafe66231edaf0c9db719) @@ -60,6 +60,5 @@ type = Kernel; } -void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period, Alarm_Callback callback ) with( this ) { - this.thrd = thrd; +void ?{}( alarm_node_t & this, Alarm_Callback callback, Time alarm, Duration period ) with( this ) { this.alarm = alarm; this.period = period; Index: libcfa/src/concurrency/alarm.hfa =================================================================== --- libcfa/src/concurrency/alarm.hfa (revision a5a67ab897a37cb777e0553f71e8a72fff0efe62) +++ libcfa/src/concurrency/alarm.hfa (revision 7b2a786f512308877bfeafe66231edaf0c9db719) @@ -52,9 +52,8 @@ union { - $thread * thrd; // thrd who created event - processor * proc; // proc who created event + $thread * thrd; // thrd who created event + processor * proc; // proc who created event + Alarm_Callback callback; // callback to handle event }; - - Alarm_Callback callback; bool set :1; // whether or not the alarm has be registered @@ -65,5 +64,5 @@ void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period ); void ?{}( alarm_node_t & this, processor * proc, Time alarm, Duration period ); -void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period, Alarm_Callback callback ); +void ?{}( alarm_node_t & this, Alarm_Callback callback, Time alarm, Duration period ); void ^?{}( alarm_node_t & this ); Index: libcfa/src/concurrency/locks.cfa =================================================================== --- libcfa/src/concurrency/locks.cfa (revision a5a67ab897a37cb777e0553f71e8a72fff0efe62) +++ libcfa/src/concurrency/locks.cfa (revision 7b2a786f512308877bfeafe66231edaf0c9db719) @@ -11,6 +11,8 @@ //// info_thread /////////////////////////////////////////////////////////////////// + forall(dtype L | is_blocking_lock(L)) { void ?{}( info_thread(L) & this, $thread * t ) { + ((Seqable &) this){}; this.t = t; this.lock = 0p; @@ -19,4 +21,5 @@ void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ) { + ((Seqable &) this){}; this.t = t; this.info = info; @@ -25,12 +28,7 @@ } - void ^?{}( info_thread(L) & this ){ - // default - } - - info_thread(L) *& get_next( info_thread(L) & this ) { - return this.next; - } -} + void ^?{}( info_thread(L) & this ){ } +} + /////////////////////////////////////////////////////////////////// //// Blocking Locks @@ -47,37 +45,16 @@ } -void ^?{}( blocking_lock & this ) { - // default -} - -void ?{}( single_acquisition_lock & this ) { - ((blocking_lock &)this){ false, false }; -} - -void ^?{}( single_acquisition_lock & this ) { - // default -} - -void ?{}( owner_lock & this ) { - ((blocking_lock &)this){ true, true }; -} - -void ^?{}( owner_lock & this ) { - // default -} - -void ?{}( multiple_acquisition_lock & this ) { - ((blocking_lock &)this){ true, false }; -} - -void ^?{}( multiple_acquisition_lock & this ) { - // default -} +void ^?{}( blocking_lock & this ) {} +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 ) {} +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) { - fprintf(stderr, "A single acquisition lock holder attempted to reacquire the lock resulting in a deadlock."); // Possibly throw instead - exit(EXIT_FAILURE); + abort("A single acquisition lock holder attempted to reacquire the lock resulting in a deadlock."); } else if ( owner != 0p && owner != active_thread() ) { append( blocked_threads, active_thread() ); @@ -110,20 +87,26 @@ } +void unlock_error_check( blocking_lock & this ) with( this ) { + if ( owner == 0p ){ // no owner implies 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" ); + } +} + +void pop_and_set_new_owner( blocking_lock & this ) with( this ) { + $thread * t = pop_head( blocked_threads ); + owner = t; + recursion_count = ( t ? 1 : 0 ); + wait_count--; + unpark( t ); +} + void unlock( blocking_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); - if ( owner == 0p ){ // no owner implies lock isn't held - fprintf( stderr, "There was an attempt to release a lock that isn't held" ); - return; - } else if ( strict_owner && owner != active_thread() ) { - fprintf( stderr, "A thread other than the owner attempted to release an owner lock" ); - return; - } + unlock_error_check( this ); recursion_count--; if ( recursion_count == 0 ) { - $thread * thrd = pop_head( blocked_threads ); - owner = thrd; - recursion_count = ( thrd ? 1 : 0 ); - wait_count--; - unpark( thrd ); + pop_and_set_new_owner( this ); } unlock( lock ); @@ -133,5 +116,4 @@ return wait_count; } - void set_recursion_count( blocking_lock & this, size_t recursion ) with( this ) { @@ -152,7 +134,4 @@ owner = t; recursion_count = 1; - #if !defined( __CFA_NO_STATISTICS__ ) - //kernelTLS.this_stats = t->curr_cluster->stats; - #endif unpark( t ); unlock( lock ); @@ -162,15 +141,6 @@ void remove_( blocking_lock & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); - if ( owner == 0p ){ // no owner implies lock isn't held - fprintf( stderr, "A lock that is not held was passed to a synchronization lock" ); - } else if ( strict_owner && owner != active_thread() ) { - fprintf( stderr, "A thread other than the owner of a lock passed it to a synchronization lock" ); - } else { - $thread * thrd = pop_head( blocked_threads ); - owner = thrd; - recursion_count = ( thrd ? 1 : 0 ); - wait_count--; - unpark( thrd ); - } + unlock_error_check( this ); + pop_and_set_new_owner( this ); unlock( lock ); } @@ -182,75 +152,24 @@ // This is 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 add_( single_acquisition_lock & this, struct $thread * t ){ - add_( (blocking_lock &)this, t ); -} - -void remove_( single_acquisition_lock & this ){ - remove_( (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 add_( owner_lock & this, struct $thread * t ){ - add_( (blocking_lock &)this, t ); -} - -void remove_( owner_lock & this ){ - remove_( (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 add_( multiple_acquisition_lock & this, struct $thread * t ){ - add_( (blocking_lock &)this, t ); -} - -void remove_( multiple_acquisition_lock & this ){ - remove_( (blocking_lock &)this ); -} - -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 ); -} +void lock( single_acquisition_lock & this ){ lock( (blocking_lock &)this ); } +void unlock( single_acquisition_lock & this ){ unlock( (blocking_lock &)this ); } +void add_( single_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); } +void remove_( single_acquisition_lock & this ){ remove_( (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 add_( owner_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); } +void remove_( owner_lock & this ){ remove_( (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 add_( multiple_acquisition_lock & this, struct $thread * t ){ add_( (blocking_lock &)this, t ); } +void remove_( multiple_acquisition_lock & this ){ remove_( (blocking_lock &)this ); } +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 ); } /////////////////////////////////////////////////////////////////// @@ -263,15 +182,13 @@ // This condition_variable member is called from the kernel, and therefore, cannot block, but it can spin. lock( cond->lock __cfaabi_dbg_ctx2 ); - if ( (*i)->listed ) { // is thread on queue - info_thread(L) * copy = *i; - remove( cond->blocked_threads, i ); //remove this thread O(1) + + if ( i->listed ) { // is thread on queue + cond->last_thread = i; // REMOVE THIS AFTER DEBUG + remove( cond->blocked_threads, *i ); //remove this thread O(1) cond->count--; - if( !copy->lock ) { - #if !defined( __CFA_NO_STATISTICS__ ) - //kernelTLS.this_stats = copy->t->curr_cluster->stats; - #endif - unpark( copy->t ); + if( !i->lock ) { + unpark( i->t ); } else { - add_(*copy->lock, copy->t); // call lock's add_ + add_(*i->lock, i->t); // call lock's add_ } } @@ -279,7 +196,5 @@ } - void alarm_node_wrap_cast( alarm_node_t & a ) { - timeout_handler( (alarm_node_wrap(L) &)a ); - } + void alarm_node_wrap_cast( alarm_node_t & a ) { timeout_handler( (alarm_node_wrap(L) &)a ); } void ?{}( condition_variable(L) & this ){ @@ -287,31 +202,31 @@ this.blocked_threads{}; this.count = 0; - } - - void ^?{}( condition_variable(L) & this ){ - // default - } - - void ?{}( alarm_node_wrap(L) & this, $thread * thrd, Time alarm, Duration period, Alarm_Callback callback ) { - this.alarm_node{ thrd, alarm, period, callback }; - } - - void ^?{}( alarm_node_wrap(L) & this ) { - // default + this.last_thread = 0p; // REMOVE AFTER DEBUG + } + + 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 ) { + if(&popped != 0p) { + popped.listed = false; + count--; + if (popped.lock) { + add_(*popped.lock, popped.t); + } else { + unpark(popped.t); + } + } } bool notify_one( condition_variable(L) & this ) with( this ) { lock( lock __cfaabi_dbg_ctx2 ); - bool ret = !!blocked_threads; - info_thread(L) * popped = pop_head( blocked_threads ); - if(popped != 0p) { - popped->listed = false; - count--; - if (popped->lock) { - add_(*popped->lock, popped->t); - } else { - unpark(popped->t); - } - } + bool ret = !empty(blocked_threads); + process_popped(this, dropHead( blocked_threads )); unlock( lock ); return ret; @@ -320,16 +235,7 @@ bool notify_all( condition_variable(L) & this ) with(this) { lock( lock __cfaabi_dbg_ctx2 ); - bool ret = blocked_threads ? true : false; - while( blocked_threads ) { - info_thread(L) * popped = pop_head( blocked_threads ); - if(popped != 0p){ - popped->listed = false; - count--; - if (popped->lock) { - add_(*popped->lock, popped->t); - } else { - unpark(popped->t); - } - } + bool ret = !empty(blocked_threads); + while( !empty(blocked_threads) ) { + process_popped(this, dropHead( blocked_threads )); } unlock( lock ); @@ -338,31 +244,30 @@ uintptr_t front( condition_variable(L) & this ) with(this) { - if(!blocked_threads) return NULL; - return peek(blocked_threads)->info; - } - - bool empty( condition_variable(L) & this ) with(this) { - return blocked_threads ? false : true; - } - - int counter( condition_variable(L) & this ) with(this) { - return count; - } - - // helper for wait()'s' without a timeout + return empty(blocked_threads) ? NULL : head(blocked_threads).info; + } + + bool empty( condition_variable(L) & this ) with(this) { return empty(blocked_threads); } + + int counter( condition_variable(L) & this ) with(this) { return count; } + + size_t queue_and_get_recursion( condition_variable(L) & this, info_thread(L) * i ) with(this) { + addTail( blocked_threads, *i ); + count++; + i->listed = true; + size_t recursion_count = 0; + if (i->lock) { + i->t->link.next = 1p; + recursion_count = get_recursion_count(*i->lock); + remove_( *i->lock ); + } + return recursion_count; + } + + // helper for wait()'s' with no timeout void queue_info_thread( condition_variable(L) & this, info_thread(L) & i ) with(this) { lock( lock __cfaabi_dbg_ctx2 ); - append( this.blocked_threads, &i ); - count++; - i.listed = true; - size_t recursion_count; - if (i.lock) { - recursion_count = get_recursion_count(*i.lock); - remove_( *i.lock ); - } - + 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 } @@ -371,26 +276,12 @@ void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Time t ) with(this) { lock( lock __cfaabi_dbg_ctx2 ); - - info_thread(L) * queue_ptr = &info; - - alarm_node_wrap(L) node_wrap = { info.t, t, 0`s, alarm_node_wrap_cast }; + 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 = &queue_ptr; - + node_wrap.i = &info; register_self( &node_wrap.alarm_node ); - - append( blocked_threads, queue_ptr ); - info.listed = true; - count++; - - size_t recursion_count; - if (info.lock) { - recursion_count = get_recursion_count(*info.lock); - remove_( *info.lock ); - } - unlock( lock ); park(); - + unregister_self( &node_wrap.alarm_node ); if (info.lock) set_recursion_count(*info.lock, recursion_count); } @@ -462,54 +353,2 @@ } } - -// thread T1 {}; -// thread T2 {}; - -// multiple_acquisition_lock m; -// condition_variable( multiple_acquisition_lock ) c; - -// void main( T1 & this ) { -// printf("T1 start\n"); -// lock(m); -// printf("%d\n", counter(c)); -// if(empty(c)) { -// printf("T1 wait\n"); -// wait(c,m,12); -// }else{ -// printf("%d\n", front(c)); -// notify_one(c); -// } -// unlock(m); -// printf("curr thd in main %p \n", active_thread()); -// printf("T1 waits for 2s\n"); -// lock(m); -// wait( c, m, 2`s ); -// unlock(m); -// printf("T1 wakes\n"); -// printf("T1 done\n"); -// } - -// void main( T2 & this ) { -// printf("T2 start\n"); -// lock(m); -// printf("%d\n", counter(c)); -// if(empty(c)) { -// printf("T2 wait\n"); -// wait(c,m,12); -// }else{ -// printf("%d\n", front(c)); -// notify_one(c); -// } -// unlock(m); -// printf("T2 done\n"); -// } - -// int main() { -// printf("start\n"); -// processor p[2]; -// { -// T1 t1; -// T2 t2; -// } -// printf("done\n"); -// } Index: libcfa/src/concurrency/locks.hfa =================================================================== --- libcfa/src/concurrency/locks.hfa (revision a5a67ab897a37cb777e0553f71e8a72fff0efe62) +++ libcfa/src/concurrency/locks.hfa (revision 7b2a786f512308877bfeafe66231edaf0c9db719) @@ -5,4 +5,5 @@ #include "bits/algorithm.hfa" #include "bits/locks.hfa" +#include "bits/sequence.hfa" #include "bits/containers.hfa" @@ -31,7 +32,7 @@ forall(dtype L | is_blocking_lock(L)) { struct info_thread { + inline Seqable; struct $thread * t; uintptr_t info; - info_thread(L) * next; L * lock; bool listed; // true if info_thread is on queue, false otherwise; @@ -42,6 +43,4 @@ void ?{}( info_thread(L) & this, $thread * t, uintptr_t info ); void ^?{}( info_thread(L) & this ); - - info_thread(L) *& get_next( info_thread(L) & this ); } @@ -50,4 +49,14 @@ /////////////////////////////////////////////////////////////////// +// struct lock_thread { +// struct $thread * t; +// lock_thread * next; +// }; + +// void ?{}( lock_thread & this, struct $thread * thd ); +// void ^?{}( lock_thread & this ); + +// lock_thread *& get_next( lock_thread & ); + struct blocking_lock { // Spin lock used for mutual exclusion @@ -55,5 +64,5 @@ // List of blocked threads - __queue_t( struct $thread ) blocked_threads; + __queue_t( $thread ) blocked_threads; // Count of current blocked threads @@ -135,6 +144,8 @@ __spinlock_t lock; + info_thread(L) * last_thread; + // List of blocked threads - __queue_t( info_thread(L) ) blocked_threads; + Sequence( info_thread(L) ) blocked_threads; // Count of current blocked threads @@ -150,8 +161,8 @@ condition_variable(L) * cond; - info_thread(L) ** i; + info_thread(L) * i; }; - void ?{}( alarm_node_wrap(L) & this, $thread * thrd, Time alarm, Duration period, Alarm_Callback callback ); + void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback ); void ^?{}( alarm_node_wrap(L) & this );