Index: libcfa/src/bits/debug.hfa =================================================================== --- libcfa/src/bits/debug.hfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/bits/debug.hfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -52,5 +52,6 @@ || defined(__CFA_DEBUG_PRINT_IO__) || defined(__CFA_DEBUG_PRINT_IO_CORE__) \ || defined(__CFA_DEBUG_PRINT_MONITOR__) || defined(__CFA_DEBUG_PRINT_PREEMPTION__) \ - || defined(__CFA_DEBUG_PRINT_RUNTIME_CORE__) || defined(__CFA_DEBUG_PRINT_EXCEPTION__) + || defined(__CFA_DEBUG_PRINT_RUNTIME_CORE__) || defined(__CFA_DEBUG_PRINT_EXCEPTION__) \ + || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) #include #include Index: libcfa/src/concurrency/kernel.cfa =================================================================== --- libcfa/src/concurrency/kernel.cfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/concurrency/kernel.cfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -120,5 +120,5 @@ static void __run_thread(processor * this, $thread * dst); static $thread * __halt(processor * this); -static bool __wake_one(cluster * cltr, bool was_empty); +static bool __wake_one(cluster * cltr); static bool __wake_proc(processor *); @@ -299,8 +299,9 @@ // register the processor unless it's the main thread which is handled in the boot sequence if(this != mainProcessor) { - this->id = doregister(this->cltr, this); + this->id = doregister2(this->cltr, this); ready_queue_grow( this->cltr ); } + doregister(this->cltr, this); { @@ -325,5 +326,5 @@ /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); /* paranoid */ verifyf( readyThread->state == Ready || readyThread->preempted != __NO_PREEMPTION, "state : %d, preempted %d\n", readyThread->state, readyThread->preempted); - /* paranoid */ verifyf( readyThread->next == 0p, "Expected null got %p", readyThread->next ); + /* paranoid */ verifyf( readyThread->link.next == 0p, "Expected null got %p", readyThread->link.next ); // We found a thread run it @@ -337,4 +338,6 @@ } + unregister(this->cltr, this); + V( this->terminated ); @@ -342,5 +345,5 @@ if(this != mainProcessor) { ready_queue_shrink( this->cltr ); - unregister(this->cltr, this); + unregister2(this->cltr, this); } else { @@ -610,8 +613,8 @@ /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); /* paranoid */ #if defined( __CFA_WITH_VERIFY__ ) - /* paranoid */ if( thrd->state == Blocked || thrd->state == Start ) assertf( thrd->preempted == __NO_PREEMPTION, - "Error inactive thread marked as preempted, state %d, preemption %d\n", thrd->state, thrd->preempted ); - /* paranoid */ if( thrd->preempted != __NO_PREEMPTION ) assertf(thrd->state == Active || thrd->state == Rerun, - "Error preempted thread marked as not currently running, state %d, preemption %d\n", thrd->state, thrd->preempted ); + /* paranoid */ if( thrd->state == Blocked || thrd->state == Start ) assertf( thrd->preempted == __NO_PREEMPTION, + "Error inactive thread marked as preempted, state %d, preemption %d\n", thrd->state, thrd->preempted ); + /* paranoid */ if( thrd->preempted != __NO_PREEMPTION ) assertf(thrd->state == Active || thrd->state == Rerun, + "Error preempted thread marked as not currently running, state %d, preemption %d\n", thrd->state, thrd->preempted ); /* paranoid */ #endif /* paranoid */ verifyf( thrd->link.next == 0p, "Expected null got %p", thrd->link.next ); @@ -620,8 +623,8 @@ ready_schedule_lock(thrd->curr_cluster, kernelTLS.this_processor); - bool was_empty = push( thrd->curr_cluster, thrd ); + push( thrd->curr_cluster, thrd ); + + __wake_one(thrd->curr_cluster); ready_schedule_unlock(thrd->curr_cluster, kernelTLS.this_processor); - - __wake_one(thrd->curr_cluster, was_empty); /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); @@ -718,5 +721,5 @@ // If that is the case, abandon the preemption. bool preempted = false; - if(thrd->next == 0p) { + if(thrd->link.next == 0p) { preempted = true; thrd->preempted = reason; @@ -789,5 +792,5 @@ (*mainProcessor){}; - mainProcessor->id = doregister(mainCluster, mainProcessor); + mainProcessor->id = doregister2(mainCluster, mainProcessor); //initialize the global state variables @@ -844,5 +847,5 @@ kernel_stop_preemption(); - unregister(mainCluster, mainProcessor); + unregister2(mainCluster, mainProcessor); // Destroy the main processor and its context in reverse order of construction @@ -909,8 +912,5 @@ // Wake a thread from the front if there are any -static bool __wake_one(cluster * this, __attribute__((unused)) bool force) { - // if we don't want to force check if we know it's false - // if( !this->idles.head && !force ) return false; - +static bool __wake_one(cluster * this) { // First, lock the cluster idle lock( this->idle_lock __cfaabi_dbg_ctx2 ); @@ -1099,4 +1099,18 @@ cltr->nthreads -= 1; unlock(cltr->thread_list_lock); +} + +void doregister( cluster * cltr, processor * proc ) { + lock (cltr->idle_lock __cfaabi_dbg_ctx2); + cltr->nprocessors += 1; + push_front(cltr->procs, *proc); + unlock (cltr->idle_lock); +} + +void unregister( cluster * cltr, processor * proc ) { + lock (cltr->idle_lock __cfaabi_dbg_ctx2); + remove(cltr->procs, *proc ); + cltr->nprocessors -= 1; + unlock(cltr->idle_lock); } Index: libcfa/src/concurrency/kernel.hfa =================================================================== --- libcfa/src/concurrency/kernel.hfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/concurrency/kernel.hfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -93,7 +93,7 @@ // Link lists fields - struct __dbg_node_proc { - struct processor * next; - struct processor * prev; + struct __dbg_node_cltr { + processor * next; + processor * prev; } node; @@ -162,5 +162,5 @@ // Link lists fields // instrusive link field for threads - // must be exactly as in thread_desc + // must be exactly as in $thread __thread_desc_link link; } before, after; @@ -286,6 +286,8 @@ // List of processors - __spinlock_t proc_list_lock; + __spinlock_t idle_lock; + __dllist_t(struct processor) procs; __dllist_t(struct processor) idles; + unsigned int nprocessors; // List of threads Index: libcfa/src/concurrency/kernel_private.hfa =================================================================== --- libcfa/src/concurrency/kernel_private.hfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/concurrency/kernel_private.hfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -100,4 +100,7 @@ void unregister( struct cluster * cltr, struct $thread & thrd ); +void doregister( struct cluster * cltr, struct processor * proc ); +void unregister( struct cluster * cltr, struct processor * proc ); + //======================================================================= // Cluster lock API @@ -110,8 +113,8 @@ // Lock-Free registering/unregistering of threads // Register a processor to a given cluster and get its unique id in return -unsigned doregister( struct cluster * cltr, struct processor * proc ); +unsigned doregister2( struct cluster * cltr, struct processor * proc ); // Unregister a processor from a given cluster using its id, getting back the original pointer -void unregister( struct cluster * cltr, struct processor * proc ); +void unregister2( struct cluster * cltr, struct processor * proc ); //======================================================================= @@ -184,10 +187,10 @@ // push thread onto a ready queue for a cluster // returns true if the list was previously empty, false otherwise -__attribute__((hot)) bool push(struct cluster * cltr, struct thread_desc * thrd); +__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd); //----------------------------------------------------------------------- // pop thread from the ready queue of a cluster // returns 0p if empty -__attribute__((hot)) thread_desc * pop(struct cluster * cltr); +__attribute__((hot)) struct $thread * pop(struct cluster * cltr); //----------------------------------------------------------------------- Index: libcfa/src/concurrency/monitor.cfa =================================================================== --- libcfa/src/concurrency/monitor.cfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/concurrency/monitor.cfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -114,7 +114,7 @@ // Some one else has the monitor, wait in line for it - /* paranoid */ verify( thrd->next == 0p ); + /* paranoid */ verify( thrd->link.next == 0p ); append( this->entry_queue, thrd ); - /* paranoid */ verify( thrd->next == 1p ); + /* paranoid */ verify( thrd->link.next == 1p ); unlock( this->lock ); @@ -199,7 +199,7 @@ // Some one else has the monitor, wait in line for it - /* paranoid */ verify( thrd->next == 0p ); + /* paranoid */ verify( thrd->link.next == 0p ); append( this->entry_queue, thrd ); - /* paranoid */ verify( thrd->next == 1p ); + /* paranoid */ verify( thrd->link.next == 1p ); unlock( this->lock ); @@ -761,5 +761,5 @@ $thread * new_owner = pop_head( this->entry_queue ); /* paranoid */ verifyf( !this->owner || kernelTLS.this_thread == this->owner, "Expected owner to be %p, got %p (r: %i, m: %p)", kernelTLS.this_thread, this->owner, this->recursion, this ); - /* paranoid */ verify( !new_owner || new_owner->next == 0p ); + /* paranoid */ verify( !new_owner || new_owner->link.next == 0p ); __set_owner( this, new_owner ); @@ -883,5 +883,5 @@ } - __cfaabi_dbg_print_safe( "Kernel : Runing %i (%p)\n", ready2run, ready2run ? (thread_desc*)node->waiting_thread : (thread_desc*)0p ); + __cfaabi_dbg_print_safe( "Kernel : Runing %i (%p)\n", ready2run, ready2run ? (thread*)node->waiting_thread : (thread*)0p ); return ready2run ? node->waiting_thread : 0p; } Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 6a490b2bb8f7820c78fa1575bef760986527a2d8) +++ libcfa/src/concurrency/ready_queue.cfa (revision 504a7dc09cca75a5ecf56f1d1986b6bda45c1afc) @@ -15,4 +15,5 @@ #define __cforall_thread__ +#define __CFA_DEBUG_PRINT_READY_QUEUE__ #include "bits/defs.hfa" @@ -34,5 +35,5 @@ const char * max_cores_s = getenv("CFA_MAX_PROCESSORS"); if(!max_cores_s) { - __cfaabi_dbg_print_nolock("No CFA_MAX_PROCESSORS in ENV"); + __cfadbg_print_nolock(ready_queue, "No CFA_MAX_PROCESSORS in ENV\n"); return __CFA_MAX_PROCESSORS__; } @@ -41,9 +42,9 @@ long int max_cores_l = strtol(max_cores_s, &endptr, 10); if(max_cores_l < 1 || max_cores_l > 65535) { - __cfaabi_dbg_print_nolock("CFA_MAX_PROCESSORS out of range : %ld", max_cores_l); + __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS out of range : %ld\n", max_cores_l); return __CFA_MAX_PROCESSORS__; } if('\0' != *endptr) { - __cfaabi_dbg_print_nolock("CFA_MAX_PROCESSORS not a decimal number : %s", max_cores_s); + __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS not a decimal number : %s\n", max_cores_s); return __CFA_MAX_PROCESSORS__; } @@ -152,5 +153,7 @@ //======================================================================= // Lock-Free registering/unregistering of threads -unsigned doregister( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { +unsigned doregister2( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { + __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p with cluster %p\n", proc, cltr); + // Step - 1 : check if there is already space in the data uint_fast32_t s = ready; @@ -185,4 +188,6 @@ } + __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %u\n", proc, n); + // Return new spot. /*paranoid*/ verify(n < ready); @@ -192,9 +197,11 @@ } -void unregister( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { +void unregister2( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { unsigned id = proc->id; /*paranoid*/ verify(id < ready); /*paranoid*/ verify(proc == __atomic_load_n(&data[id].handle, __ATOMIC_RELAXED)); __atomic_store_n(&data[id].handle, 0p, __ATOMIC_RELEASE); + + __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc); } @@ -241,7 +248,7 @@ //======================================================================= // Get the head pointer (one before the first element) from the anchor -static inline thread_desc * head(const __intrusive_lane_t & this) { - thread_desc * rhead = (thread_desc *)( - (uintptr_t)( &this.before ) - offsetof( thread_desc, link ) +static inline $thread * head(const __intrusive_lane_t & this) { + $thread * rhead = ($thread *)( + (uintptr_t)( &this.before ) - offsetof( $thread, link ) ); /* paranoid */ verify(rhead); @@ -250,7 +257,7 @@ // Get the tail pointer (one after the last element) from the anchor -static inline thread_desc * tail(const __intrusive_lane_t & this) { - thread_desc * rtail = (thread_desc *)( - (uintptr_t)( &this.after ) - offsetof( thread_desc, link ) +static inline $thread * tail(const __intrusive_lane_t & this) { + $thread * rtail = ($thread *)( + (uintptr_t)( &this.after ) - offsetof( $thread, link ) ); /* paranoid */ verify(rtail); @@ -261,6 +268,8 @@ void ?{}( __intrusive_lane_t & this ) { this.lock = false; - this.last_id = -1u; - this.count = 0u; + #if defined(__CFA_WITH_VERIFY__) + this.last_id = -1u; + this.count = 0u; + #endif this.before.link.prev = 0p; @@ -279,6 +288,6 @@ // We add a boat-load of assertions here because the anchor code is very fragile - /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( thread_desc, link )) == (uintptr_t)(&this.before)); - /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( thread_desc, link )) == (uintptr_t)(&this.after )); + /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before)); + /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after )); /* paranoid */ verify(head(this)->link.prev == 0p ); /* paranoid */ verify(head(this)->link.next == tail(this) ); @@ -311,5 +320,5 @@ // Push a thread onto this lane // returns true of lane was empty before push, false otherwise -bool push(__intrusive_lane_t & this, thread_desc * node) { +bool push(__intrusive_lane_t & this, $thread * node) { #if defined(__CFA_WITH_VERIFY__) /* paranoid */ verify(this.lock); @@ -317,18 +326,21 @@ /* paranoid */ verify(node->link.next == 0p); /* paranoid */ verify(node->link.prev == 0p); + /* paranoid */ verify(tail(this)->link.next == 0p); + /* paranoid */ verify(head(this)->link.prev == 0p); this.count++; if(this.before.link.ts == 0l) { - /* paranoid */ verify(tail(this)->link.next == 0p); /* paranoid */ verify(tail(this)->link.prev == head(this)); /* paranoid */ verify(head(this)->link.next == tail(this)); - /* paranoid */ verify(head(this)->link.prev == 0p); + } else { + /* paranoid */ verify(tail(this)->link.prev != head(this)); + /* paranoid */ verify(head(this)->link.next != tail(this)); } #endif // Get the relevant nodes locally - thread_desc * tail = tail(this); - thread_desc * prev = tail->link.prev; + $thread * tail = tail(this); + $thread * prev = tail->link.prev; // Do the push @@ -358,15 +370,15 @@ // returns popped // returns true of lane was empty before push, false otherwise -[thread_desc *, bool] pop(__intrusive_lane_t & this) { +[$thread *, bool] pop(__intrusive_lane_t & this) { /* paranoid */ verify(this.lock); /* paranoid */ verify(this.before.link.ts != 0ul); // Get anchors locally - thread_desc * head = head(this); - thread_desc * tail = tail(this); + $thread * head = head(this); + $thread * tail = tail(this); // Get the relevant nodes locally - thread_desc * node = head->link.next; - thread_desc * next = node->link.next; + $thread * node = head->link.next; + $thread * next = node->link.next; #if defined(__CFA_WITH_VERIFY__) @@ -391,14 +403,16 @@ // Check if we emptied list and return accordingly + /* paranoid */ verify(tail(this)->link.next == 0p); + /* paranoid */ verify(head(this)->link.prev == 0p); if(next == tail) { /* paranoid */ verify(this.before.link.ts == 0); - /* paranoid */ verify(tail(this)->link.next == 0p); /* paranoid */ verify(tail(this)->link.prev == head(this)); /* paranoid */ verify(head(this)->link.next == tail(this)); - /* paranoid */ verify(head(this)->link.prev == 0p); return [node, true]; } else { /* paranoid */ verify(next->link.ts != 0); + /* paranoid */ verify(tail(this)->link.prev != head(this)); + /* paranoid */ verify(head(this)->link.next != tail(this)); /* paranoid */ verify(this.before.link.ts != 0); return [node, false]; @@ -508,5 +522,5 @@ // Conditional check verifyf( - strict == STRICT && // Conditional check if it was expected to be cleared + strict != STRICT || // Conditional check if it was expected to be cleared ((mask[word] & (1ull << bit)) == 0), "Before set %llu:%llu (%u), %llx & %llx", word, bit, index, mask[word], (1ull << bit) @@ -518,5 +532,5 @@ // Conditional check verifyf( - strict == STRICT && // Conditional check if it was expected to be cleared + strict != STRICT || // Conditional check if it was expected to be cleared !ret, "Bit was not set but bts returned true" @@ -561,5 +575,5 @@ //----------------------------------------------------------------------- -__attribute__((hot)) bool push(struct cluster * cltr, struct thread_desc * thrd) with (cltr->ready_queue) { +__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) { // write timestamp thrd->link.ts = rdtscl(); @@ -569,5 +583,5 @@ do { // Pick the index of a lane - unsigned i = tls_rand() % lanes.count; + i = __tls_rand() % lanes.count; #if !defined(__CFA_NO_STATISTICS__) @@ -594,5 +608,5 @@ size_t ret = __atomic_fetch_add( &used.count, 1z, __ATOMIC_SEQ_CST); - // Check if the entire quue used to be empty + // Check if the entire queue used to be empty first = (ret == 0); @@ -624,5 +638,5 @@ //----------------------------------------------------------------------- // Given 2 indexes, pick the list with the oldest push an try to pop from it -static struct thread_desc * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) { +static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) { #if !defined(__CFA_NO_STATISTICS__) tls.pick.pop.attempt++; @@ -662,5 +676,5 @@ // Actually pop the list - struct thread_desc * thrd; + struct $thread * thrd; bool emptied; [thrd, emptied] = pop(lane); @@ -704,5 +718,5 @@ // Pop from the ready queue from a given cluster -__attribute__((hot)) thread_desc * pop(struct cluster * cltr) with (cltr->ready_queue) { +__attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) { /* paranoid */ verify( lanes.count > 0 ); @@ -716,6 +730,6 @@ // Pick two lists at random - unsigned ri = tls_rand(); - unsigned rj = tls_rand(); + unsigned ri = __tls_rand(); + unsigned rj = __tls_rand(); // Find which __cfa_readyQ_mask_t the two lists belong @@ -748,13 +762,13 @@ // try popping from the 2 picked lists - struct thread_desc * thrd = try_pop(cltr, i, j); + struct $thread * thrd = try_pop(cltr, i, j); if(thrd) return thrd; #else // Pick two lists at random - int i = tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); - int j = tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); + int i = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); + int j = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); // try popping from the 2 picked lists - struct thread_desc * thrd = try_pop(cltr, i, j); + struct $thread * thrd = try_pop(cltr, i, j); if(thrd) return thrd; #endif @@ -825,5 +839,5 @@ uint_fast32_t last_size = ready_mutate_lock( *cltr ); - __cfaabi_dbg_print_safe("Kernel : Growing ready queue\n"); + __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n"); // Make sure that everything is consistent @@ -862,5 +876,5 @@ /* paranoid */ check( cltr->ready_queue ); - __cfaabi_dbg_print_safe("Kernel : Growing ready queue done\n"); + __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n"); // Unlock the RWlock @@ -873,5 +887,5 @@ uint_fast32_t last_size = ready_mutate_lock( *cltr ); - __cfaabi_dbg_print_safe("Kernel : Shrinking ready queue\n"); + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n"); // Make sure that everything is consistent @@ -896,5 +910,5 @@ // for printing count the number of displaced threads - #if defined(__CFA_DEBUG_PRINT__) + #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) __attribute__((unused)) size_t displaced = 0; #endif @@ -908,5 +922,5 @@ // As long as we can pop from this lane to push the threads somewhere else in the queue while(!is_empty(lanes.data[idx])) { - struct thread_desc * thrd; + struct $thread * thrd; __attribute__((unused)) bool _; [thrd, _] = pop(lanes.data[idx]); @@ -915,5 +929,5 @@ // for printing count the number of displaced threads - #if defined(__CFA_DEBUG_PRINT__) + #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) displaced++; #endif @@ -930,5 +944,5 @@ } - __cfaabi_dbg_print_safe("Kernel : Shrinking ready queue displaced %zu threads\n", displaced); + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced); // recompute the used.count instead of maintaining it @@ -958,5 +972,5 @@ /* paranoid */ check( cltr->ready_queue ); - __cfaabi_dbg_print_safe("Kernel : Shrinking ready queue done\n"); + __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n"); // Unlock the RWlock