Changeset 22f94a4 for libcfa/src/concurrency/kernel.cfa

Timestamp:

Aug 11, 2020, 4:40:15 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

0d070ca

Parents:

07d867b (diff), 129674b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' into new-ast

File:

• libcfa/src/concurrency/kernel.cfa (modified) (27 diffs)

libcfa/src/concurrency/kernel.cfa

@@ -10 +10 @@
 // Created On       : Tue Jan 17 12:27:26 2017
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Tue Feb  4 13:03:15 2020
-// Update Count     : 58
+// Last Modified On : Thu Jul  9 06:22:54 2020
+// Update Count     : 66
 //
 
@@ -18 +18 @@
 
 //C Includes
-#include <stddef.h>
 #include <errno.h>
-#include <string.h>
-extern "C" {
 #include <stdio.h>
-#include <fenv.h>
-#include <sys/resource.h>
 #include <signal.h>
 #include <unistd.h>
-#include <limits.h>                                                                             // PTHREAD_STACK_MIN
-#include <sys/mman.h>                                                                   // mprotect
-}
 
 //CFA Includes
-#include "time.hfa"
 #include "kernel_private.hfa"
 #include "preemption.hfa"
-#include "startup.hfa"
 
 //Private includes
@@ -45 +35 @@
 // Some assembly required
 #if defined( __i386 )
-        #define CtxGet( ctx )        \
-                __asm__ volatile (     \
-                        "movl %%esp,%0\n"\
-                        "movl %%ebp,%1\n"\
-                        : "=rm" (ctx.SP),\
-                                "=rm" (ctx.FP) \
-                )
-
         // mxcr : SSE Status and Control bits (control bits are preserved across function calls)
         // fcw  : X87 FPU control word (preserved across function calls)
@@ -74 +56 @@
 
 #elif defined( __x86_64 )
-        #define CtxGet( ctx )        \
-                __asm__ volatile (     \
-                        "movq %%rsp,%0\n"\
-                        "movq %%rbp,%1\n"\
-                        : "=rm" (ctx.SP),\
-                                "=rm" (ctx.FP) \
-                )
-
         #define __x87_store         \
                 uint32_t __mxcr;      \
@@ -102 +76 @@
 
 #elif defined( __ARM_ARCH )
-#define CtxGet( ctx ) __asm__ ( \
-                "mov %0,%%sp\n"   \
-                "mov %1,%%r11\n"   \
-        : "=rm" (ctx.SP), "=rm" (ctx.FP) )
 #else
         #error unknown hardware architecture
 #endif
 
-//-----------------------------------------------------------------------------
-//Start and stop routine for the kernel, declared first to make sure they run first
-static void __kernel_startup (void) __attribute__(( constructor( STARTUP_PRIORITY_KERNEL ) ));
-static void __kernel_shutdown(void) __attribute__(( destructor ( STARTUP_PRIORITY_KERNEL ) ));
+extern $thread * mainThread;
+extern processor * mainProcessor;
 
 //-----------------------------------------------------------------------------
 // Kernel Scheduling logic
 static $thread * __next_thread(cluster * this);
+static $thread * __next_thread_slow(cluster * this);
 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_proc(processor *);
-
-//-----------------------------------------------------------------------------
-// Kernel storage
-KERNEL_STORAGE(cluster,         mainCluster);
-KERNEL_STORAGE(processor,       mainProcessor);
-KERNEL_STORAGE($thread, mainThread);
-KERNEL_STORAGE(__stack_t,       mainThreadCtx);
-
-cluster     * mainCluster;
-processor   * mainProcessor;
-$thread * mainThread;
-
-extern "C" {
-        struct { __dllist_t(cluster) list; __spinlock_t lock; } __cfa_dbg_global_clusters;
-}
-
-size_t __page_size = 0;
-
-//-----------------------------------------------------------------------------
-// Global state
-thread_local struct KernelThreadData kernelTLS __attribute__ ((tls_model ( "initial-exec" ))) = {
-        NULL,                                                                                           // cannot use 0p
-        NULL,
-        { 1, false, false },
-        6u //this should be seeded better but due to a bug calling rdtsc doesn't work
-};
-
-//-----------------------------------------------------------------------------
-// Struct to steal stack
-struct current_stack_info_t {
-        __stack_t * storage;                                                            // pointer to stack object
-        void * base;                                                                            // base of stack
-        void * limit;                                                                           // stack grows towards stack limit
-        void * context;                                                                         // address of cfa_context_t
-};
-
-void ?{}( current_stack_info_t & this ) {
-        __stack_context_t ctx;
-        CtxGet( ctx );
-        this.base = ctx.FP;
-
-        rlimit r;
-        getrlimit( RLIMIT_STACK, &r);
-        size_t size = r.rlim_cur;
-
-        this.limit = (void *)(((intptr_t)this.base) - size);
-        this.context = &storage_mainThreadCtx;
-}
-
-//-----------------------------------------------------------------------------
-// Main thread construction
-
-void ?{}( $coroutine & this, current_stack_info_t * info) with( this ) {
-        stack.storage = info->storage;
-        with(*stack.storage) {
-                limit     = info->limit;
-                base      = info->base;
-        }
-        __attribute__((may_alias)) intptr_t * istorage = (intptr_t*) &stack.storage;
-        *istorage |= 0x1;
-        name = "Main Thread";
-        state = Start;
-        starter = 0p;
-        last = 0p;
-        cancellation = 0p;
-}
-
-void ?{}( $thread & this, current_stack_info_t * info) with( this ) {
-        state = Start;
-        self_cor{ info };
-        curr_cor = &self_cor;
-        curr_cluster = mainCluster;
-        self_mon.owner = &this;
-        self_mon.recursion = 1;
-        self_mon_p = &self_mon;
-        next = 0p;
-
-        node.next = 0p;
-        node.prev = 0p;
-        doregister(curr_cluster, this);
-
-        monitors{ &self_mon_p, 1, (fptr_t)0 };
-}
-
-//-----------------------------------------------------------------------------
-// Processor coroutine
-void ?{}(processorCtx_t & this) {
-
-}
-
-// Construct the processor context of non-main processors
-static void ?{}(processorCtx_t & this, processor * proc, current_stack_info_t * info) {
-        (this.__cor){ info };
-        this.proc = proc;
-}
-
-static void * __invoke_processor(void * arg);
-
-void ?{}(processor & this, const char name[], cluster & cltr) with( this ) {
-        this.name = name;
-        this.cltr = &cltr;
-        terminated{ 0 };
-        destroyer = 0p;
-        do_terminate = false;
-        preemption_alarm = 0p;
-        pending_preemption = false;
-        runner.proc = &this;
-
-        idle{};
-
-        __cfadbg_print_safe(runtime_core, "Kernel : Starting core %p\n", &this);
-
-        this.stack = __create_pthread( &this.kernel_thread, __invoke_processor, (void *)&this );
-
-        __cfadbg_print_safe(runtime_core, "Kernel : core %p created\n", &this);
-}
-
-void ^?{}(processor & this) with( this ){
-        if( ! __atomic_load_n(&do_terminate, __ATOMIC_ACQUIRE) ) {
-                __cfadbg_print_safe(runtime_core, "Kernel : core %p signaling termination\n", &this);
-
-                __atomic_store_n(&do_terminate, true, __ATOMIC_RELAXED);
-                __wake_proc( &this );
-
-                P( terminated );
-                verify( kernelTLS.this_processor != &this);
-        }
-
-        int err = pthread_join( kernel_thread, 0p );
-        if( err != 0 ) abort("KERNEL ERROR: joining processor %p caused error %s\n", &this, strerror(err));
-
-        free( this.stack );
-}
-
-void ?{}(cluster & this, const char name[], Duration preemption_rate, int io_flags) with( this ) {
-        this.name = name;
-        this.preemption_rate = preemption_rate;
-        ready_queue{};
-        ready_queue_lock{};
-
-        #if !defined(__CFA_NO_STATISTICS__)
-                print_stats = false;
-        #endif
-
-        procs{ __get };
-        idles{ __get };
-        threads{ __get };
-
-        __kernel_io_startup( this, io_flags, &this == mainCluster );
-
-        doregister(this);
-}
-
-void ^?{}(cluster & this) {
-        __kernel_io_shutdown( this, &this == mainCluster );
-
-        unregister(this);
-}
+static void __wake_one(struct __processor_id_t * id, cluster * cltr);
+
+static void push  (__cluster_idles & idles, processor & proc);
+static void remove(__cluster_idles & idles, processor & proc);
+static [unsigned idle, unsigned total, * processor] query( & __cluster_idles idles );
+
 
 //=============================================================================================
@@ -294 +108 @@
 
         __cfadbg_print_safe(runtime_core, "Kernel : core %p starting\n", this);
-
-        doregister(this->cltr, this);
+        #if !defined(__CFA_NO_STATISTICS__)
+                if( this->print_halts ) {
+                        __cfaabi_bits_print_safe( STDOUT_FILENO, "Processor : %d - %s (%p)\n", this->id, this->name, (void*)this);
+                }
+        #endif
 
         {
@@ -304 +121 @@
 
                 $thread * readyThread = 0p;
-                for( unsigned int spin_count = 0; ! __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST); spin_count++ ) {
+                MAIN_LOOP:
+                for() {
                         // Try to get the next thread
                         readyThread = __next_thread( this->cltr );
 
-                        // If no ready thread
-                        if( readyThread == 0p ) {
-                                // Block until a thread is ready
-                                readyThread = __halt(this);
+                        if( !readyThread ) {
+                                readyThread = __next_thread_slow( this->cltr );
                         }
 
-                        // Check if we actually found a thread
-                        if( readyThread ) {
-                                /* 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 );
-
-                                // We found a thread run it
-                                __run_thread(this, readyThread);
-
-                                /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+                        HALT:
+                        if( !readyThread ) {
+                                // Don't block if we are done
+                                if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
+
+                                #if !defined(__CFA_NO_STATISTICS__)
+                                        __tls_stats()->ready.sleep.halts++;
+                                #endif
+
+                                // Push self to idle stack
+                                push(this->cltr->idles, * this);
+
+                                // Confirm the ready-queue is empty
+                                readyThread = __next_thread_slow( this->cltr );
+                                if( readyThread ) {
+                                        // A thread was found, cancel the halt
+                                        remove(this->cltr->idles, * this);
+
+                                        #if !defined(__CFA_NO_STATISTICS__)
+                                                __tls_stats()->ready.sleep.cancels++;
+                                        #endif
+
+                                        // continue the mai loop
+                                        break HALT;
+                                }
+
+                                #if !defined(__CFA_NO_STATISTICS__)
+                                        if(this->print_halts) {
+                                                __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->id, rdtscl());
+                                        }
+                                #endif
+
+                                wait( this->idle );
+
+                                #if !defined(__CFA_NO_STATISTICS__)
+                                        if(this->print_halts) {
+                                                __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->id, rdtscl());
+                                        }
+                                #endif
+
+                                // We were woken up, remove self from idle
+                                remove(this->cltr->idles, * this);
+
+                                // DON'T just proceed, start looking again
+                                continue MAIN_LOOP;
                         }
+
+                        /* paranoid */ verify( readyThread );
+
+                        // We found a thread run it
+                        __run_thread(this, readyThread);
+
+                        // Are we done?
+                        if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
                 }
 
@@ -330 +189 @@
         }
 
-        unregister(this->cltr, this);
-
         V( this->terminated );
 
+        if(this == mainProcessor) {
+                // HACK : the coroutine context switch expects this_thread to be set
+                // and it make sense for it to be set in all other cases except here
+                // fake it
+                kernelTLS.this_thread = mainThread;
+        }
+
         __cfadbg_print_safe(runtime_core, "Kernel : core %p terminated\n", this);
-
-        // HACK : the coroutine context switch expects this_thread to be set
-        // and it make sense for it to be set in all other cases except here
-        // fake it
-        if( this == mainProcessor ) kernelTLS.this_thread = mainThread;
 }
 
@@ -349 +208 @@
 // from the processor coroutine to the target thread
 static void __run_thread(processor * this, $thread * thrd_dst) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        /* paranoid */ verifyf( thrd_dst->state == Ready || thrd_dst->preempted != __NO_PREEMPTION, "state : %d, preempted %d\n", thrd_dst->state, thrd_dst->preempted);
+        /* paranoid */ verifyf( thrd_dst->link.next == 0p, "Expected null got %p", thrd_dst->link.next );
+        __builtin_prefetch( thrd_dst->context.SP );
+
         $coroutine * proc_cor = get_coroutine(this->runner);
 
@@ -360 +224 @@
         // Actually run the thread
         RUNNING:  while(true) {
-                if(unlikely(thrd_dst->preempted)) {
-                        thrd_dst->preempted = __NO_PREEMPTION;
-                        verify(thrd_dst->state == Active  || thrd_dst->state == Rerun);
-                } else {
-                        verify(thrd_dst->state == Blocked || thrd_dst->state == Ready); // Ready means scheduled normally, blocked means rerun
-                        thrd_dst->state = Active;
-                }
+                thrd_dst->preempted = __NO_PREEMPTION;
+                thrd_dst->state = Active;
 
                 __cfaabi_dbg_debug_do(
@@ -374 +233 @@
 
                 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+                /* paranoid */ verify( kernelTLS.this_thread == thrd_dst );
                 /* paranoid */ verifyf( ((uintptr_t)thrd_dst->context.SP) < ((uintptr_t)__get_stack(thrd_dst->curr_cor)->base ) || thrd_dst->curr_cor == proc_cor, "ERROR : Destination $thread %p has been corrupted.\n StackPointer too small.\n", thrd_dst ); // add escape condition if we are setting up the processor
                 /* paranoid */ verifyf( ((uintptr_t)thrd_dst->context.SP) > ((uintptr_t)__get_stack(thrd_dst->curr_cor)->limit) || thrd_dst->curr_cor == proc_cor, "ERROR : Destination $thread %p has been corrupted.\n StackPointer too large.\n", thrd_dst ); // add escape condition if we are setting up the processor
@@ -384 +244 @@
                 /* paranoid */ verifyf( ((uintptr_t)thrd_dst->context.SP) > ((uintptr_t)__get_stack(thrd_dst->curr_cor)->limit), "ERROR : Destination $thread %p has been corrupted.\n StackPointer too large.\n", thrd_dst );
                 /* paranoid */ verifyf( ((uintptr_t)thrd_dst->context.SP) < ((uintptr_t)__get_stack(thrd_dst->curr_cor)->base ), "ERROR : Destination $thread %p has been corrupted.\n StackPointer too small.\n", thrd_dst );
+                /* paranoid */ verify( kernelTLS.this_thread == thrd_dst );
                 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
 
@@ -396 +257 @@
                 if(unlikely(thrd_dst->preempted != __NO_PREEMPTION)) {
                         // The thread was preempted, reschedule it and reset the flag
-                        __schedule_thread( thrd_dst );
+                        __schedule_thread( (__processor_id_t*)this, thrd_dst );
                         break RUNNING;
                 }
 
+                if(unlikely(thrd_dst->state == Halted)) {
+                        // The thread has halted, it should never be scheduled/run again
+                        // We may need to wake someone up here since
+                        unpark( this->destroyer __cfaabi_dbg_ctx2 );
+                        this->destroyer = 0p;
+                        break RUNNING;
+                }
+
+                /* paranoid */ verify( thrd_dst->state == Active );
+                thrd_dst->state = Blocked;
+
                 // set state of processor coroutine to active and the thread to inactive
-                static_assert(sizeof(thrd_dst->state) == sizeof(int));
-                enum coroutine_state old_state = __atomic_exchange_n(&thrd_dst->state, Blocked, __ATOMIC_SEQ_CST);
-                __cfaabi_dbg_debug_do( thrd_dst->park_result = old_state; )
-                switch(old_state) {
-                        case Halted:
-                                // The thread has halted, it should never be scheduled/run again, leave it back to Halted and move on
-                                thrd_dst->state = Halted;
-
-                                // We may need to wake someone up here since
-                                unpark( this->destroyer __cfaabi_dbg_ctx2 );
-                                this->destroyer = 0p;
-                                break RUNNING;
-                        case Active:
+                int old_ticket = __atomic_fetch_sub(&thrd_dst->ticket, 1, __ATOMIC_SEQ_CST);
+                __cfaabi_dbg_debug_do( thrd_dst->park_result = old_ticket; )
+                switch(old_ticket) {
+                        case 1:
                                 // This is case 1, the regular case, nothing more is needed
                                 break RUNNING;
-                        case Rerun:
+                        case 2:
                                 // This is case 2, the racy case, someone tried to run this thread before it finished blocking
                                 // In this case, just run it again.
@@ -422 +285 @@
                         default:
                                 // This makes no sense, something is wrong abort
-                                abort("Finished running a thread that was Blocked/Start/Primed %d\n", old_state);
+                                abort();
                 }
         }
@@ -429 +292 @@
         proc_cor->state = Active;
         kernelTLS.this_thread = 0p;
+
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
 }
 
@@ -436 +301 @@
         $coroutine * proc_cor = get_coroutine(kernelTLS.this_processor->runner);
         $thread * thrd_src = kernelTLS.this_thread;
+
+        #if !defined(__CFA_NO_STATISTICS__)
+                struct processor * last_proc = kernelTLS.this_processor;
+        #endif
 
         // Run the thread on this processor
@@ -451 +320 @@
         }
 
+        #if !defined(__CFA_NO_STATISTICS__)
+                if(last_proc != kernelTLS.this_processor) {
+                        __tls_stats()->ready.threads.migration++;
+                }
+        #endif
+
         /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
         /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) < ((uintptr_t)__get_stack(thrd_src->curr_cor)->base ), "ERROR : Returning $thread %p has been corrupted.\n StackPointer too small.\n", thrd_src );
         /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) > ((uintptr_t)__get_stack(thrd_src->curr_cor)->limit), "ERROR : Returning $thread %p has been corrupted.\n StackPointer too large.\n", thrd_src );
-}
-
-// KERNEL_ONLY
-// Context invoker for processors
-// This is the entry point for processors (kernel threads)
-// It effectively constructs a coroutine by stealing the pthread stack
-static void * __invoke_processor(void * arg) {
-        processor * proc = (processor *) arg;
-        kernelTLS.this_processor = proc;
-        kernelTLS.this_thread    = 0p;
-        kernelTLS.preemption_state.[enabled, disable_count] = [false, 1];
-        // SKULLDUGGERY: We want to create a context for the processor coroutine
-        // which is needed for the 2-step context switch. However, there is no reason
-        // to waste the perfectly valid stack create by pthread.
-        current_stack_info_t info;
-        __stack_t ctx;
-        info.storage = &ctx;
-        (proc->runner){ proc, &info };
-
-        __cfaabi_dbg_print_safe("Coroutine : created stack %p\n", get_coroutine(proc->runner)->stack.storage);
-
-        //Set global state
-        kernelTLS.this_thread = 0p;
-
-        //We now have a proper context from which to schedule threads
-        __cfadbg_print_safe(runtime_core, "Kernel : core %p created (%p, %p)\n", proc, &proc->runner, &ctx);
-
-        // SKULLDUGGERY: Since the coroutine doesn't have its own stack, we can't
-        // resume it to start it like it normally would, it will just context switch
-        // back to here. Instead directly call the main since we already are on the
-        // appropriate stack.
-        get_coroutine(proc->runner)->state = Active;
-        main( proc->runner );
-        get_coroutine(proc->runner)->state = Halted;
-
-        // Main routine of the core returned, the core is now fully terminated
-        __cfadbg_print_safe(runtime_core, "Kernel : core %p main ended (%p)\n", proc, &proc->runner);
-
-        return 0p;
-}
-
-static void Abort( int ret, const char func[] ) {
-        if ( ret ) {                                                                            // pthread routines return errno values
-                abort( "%s : internal error, error(%d) %s.", func, ret, strerror( ret ) );
-        } // if
-} // Abort
-
-void * __create_pthread( pthread_t * pthread, void * (*start)(void *), void * arg ) {
-        pthread_attr_t attr;
-
-        Abort( pthread_attr_init( &attr ), "pthread_attr_init" ); // initialize attribute
-
-        size_t stacksize;
-        // default stack size, normally defined by shell limit
-        Abort( pthread_attr_getstacksize( &attr, &stacksize ), "pthread_attr_getstacksize" );
-        assert( stacksize >= PTHREAD_STACK_MIN );
-
-        void * stack;
-        __cfaabi_dbg_debug_do(
-                stack = memalign( __page_size, stacksize + __page_size );
-                // pthread has no mechanism to create the guard page in user supplied stack.
-                if ( mprotect( stack, __page_size, PROT_NONE ) == -1 ) {
-                        abort( "mprotect : internal error, mprotect failure, error(%d) %s.", errno, strerror( errno ) );
-                } // if
-        );
-        __cfaabi_dbg_no_debug_do(
-                stack = malloc( stacksize );
-        );
-
-        Abort( pthread_attr_setstack( &attr, stack, stacksize ), "pthread_attr_setstack" );
-
-        Abort( pthread_create( pthread, &attr, start, arg ), "pthread_create" );
-        return stack;
-}
-
-// KERNEL_ONLY
-static void __kernel_first_resume( processor * this ) {
-        $thread * src = mainThread;
-        $coroutine * dst = get_coroutine(this->runner);
-
-        verify( ! kernelTLS.preemption_state.enabled );
-
-        kernelTLS.this_thread->curr_cor = dst;
-        __stack_prepare( &dst->stack, 65000 );
-        __cfactx_start(main, dst, this->runner, __cfactx_invoke_coroutine);
-
-        verify( ! kernelTLS.preemption_state.enabled );
-
-        dst->last = &src->self_cor;
-        dst->starter = dst->starter ? dst->starter : &src->self_cor;
-
-        // make sure the current state is still correct
-        /* paranoid */ verify(src->state == Ready);
-
-        // context switch to specified coroutine
-        verify( dst->context.SP );
-        __cfactx_switch( &src->context, &dst->context );
-        // when __cfactx_switch returns we are back in the src coroutine
-
-        mainThread->curr_cor = &mainThread->self_cor;
-
-        // make sure the current state has been update
-        /* paranoid */ verify(src->state == Active);
-
-        verify( ! kernelTLS.preemption_state.enabled );
-}
-
-// KERNEL_ONLY
-static void __kernel_last_resume( processor * this ) {
-        $coroutine * src = &mainThread->self_cor;
-        $coroutine * dst = get_coroutine(this->runner);
-
-        verify( ! kernelTLS.preemption_state.enabled );
-        verify( dst->starter == src );
-        verify( dst->context.SP );
-
-        // SKULLDUGGERY in debug the processors check that the
-        // stack is still within the limit of the stack limits after running a thread.
-        // that check doesn't make sense if we context switch to the processor using the
-        // coroutine semantics. Since this is a special case, use the current context
-        // info to populate these fields.
-        __cfaabi_dbg_debug_do(
-                __stack_context_t ctx;
-                CtxGet( ctx );
-                mainThread->context.SP = ctx.SP;
-                mainThread->context.FP = ctx.FP;
-        )
-
-        // context switch to the processor
-        __cfactx_switch( &src->context, &dst->context );
 }
 
@@ -589 +334 @@
 // Scheduler routines
 // KERNEL ONLY
-void __schedule_thread( $thread * thrd ) with( *thrd->curr_cluster ) {
+void __schedule_thread( struct __processor_id_t * id, $thread * thrd ) {
+        /* paranoid */ verify( thrd );
+        /* paranoid */ verify( thrd->state != Halted );
         /* 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,
+                                        "Error preempted thread marked as not currently running, state %d, preemption %d\n", thrd->state, thrd->preempted );
         /* paranoid */ #endif
-        /* paranoid */ verifyf( thrd->next == 0p, "Expected null got %p", thrd->next );
+        /* paranoid */ verifyf( thrd->link.next == 0p, "Expected null got %p", thrd->link.next );
 
         if (thrd->preempted == __NO_PREEMPTION) thrd->state = Ready;
 
-        lock  ( ready_queue_lock __cfaabi_dbg_ctx2 );
-        bool was_empty = !(ready_queue != 0);
-        append( ready_queue, thrd );
-        unlock( ready_queue_lock );
-
-        __wake_one(thrd->curr_cluster, was_empty);
+        ready_schedule_lock  ( id );
+                push( thrd->curr_cluster, thrd );
+                __wake_one(id, thrd->curr_cluster);
+        ready_schedule_unlock( id );
 
         /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
@@ -612 +357 @@
 
 // KERNEL ONLY
-static $thread * __next_thread(cluster * this) with( *this ) {
-        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
-
-        lock( ready_queue_lock __cfaabi_dbg_ctx2 );
-        $thread * head = pop_head( ready_queue );
-        unlock( ready_queue_lock );
-
-        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
-        return head;
+static inline $thread * __next_thread(cluster * this) with( *this ) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+
+        ready_schedule_lock  ( (__processor_id_t*)kernelTLS.this_processor );
+                $thread * thrd = pop( this );
+        ready_schedule_unlock( (__processor_id_t*)kernelTLS.this_processor );
+
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        return thrd;
+}
+
+// KERNEL ONLY
+static inline $thread * __next_thread_slow(cluster * this) with( *this ) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+
+        ready_schedule_lock  ( (__processor_id_t*)kernelTLS.this_processor );
+                $thread * thrd = pop_slow( this );
+        ready_schedule_unlock( (__processor_id_t*)kernelTLS.this_processor );
+
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        return thrd;
 }
 
 // KERNEL ONLY unpark with out disabling interrupts
-void __unpark( $thread * thrd __cfaabi_dbg_ctx_param2 ) {
-        static_assert(sizeof(thrd->state) == sizeof(int));
-
+void __unpark(  struct __processor_id_t * id, $thread * thrd __cfaabi_dbg_ctx_param2 ) {
         // record activity
         __cfaabi_dbg_record_thrd( *thrd, false, caller );
 
-        enum coroutine_state old_state = __atomic_exchange_n(&thrd->state, Rerun, __ATOMIC_SEQ_CST);
-        __cfaabi_dbg_debug_do( thrd->unpark_result = old_state; )
-        switch(old_state) {
-                case Active:
+        int old_ticket = __atomic_fetch_add(&thrd->ticket, 1, __ATOMIC_SEQ_CST);
+        __cfaabi_dbg_debug_do( thrd->unpark_result = old_ticket; thrd->unpark_state = thrd->state; )
+        switch(old_ticket) {
+                case 1:
                         // Wake won the race, the thread will reschedule/rerun itself
                         break;
-                case Blocked:
+                case 0:
                         /* paranoid */ verify( ! thrd->preempted != __NO_PREEMPTION );
+                        /* paranoid */ verify( thrd->state == Blocked );
 
                         // Wake lost the race,
-                        thrd->state = Blocked;
-                        __schedule_thread( thrd );
+                        __schedule_thread( id, thrd );
                         break;
-                case Rerun:
-                        abort("More than one thread attempted to schedule thread %p\n", thrd);
-                        break;
-                case Halted:
-                case Start:
-                case Primed:
                 default:
                         // This makes no sense, something is wrong abort
@@ -659 +408 @@
 
         disable_interrupts();
-        __unpark( thrd __cfaabi_dbg_ctx_fwd2 );
+        __unpark( (__processor_id_t*)kernelTLS.this_processor, thrd __cfaabi_dbg_ctx_fwd2 );
         enable_interrupts( __cfaabi_dbg_ctx );
 }
@@ -694 +443 @@
 
         $thread * thrd = kernelTLS.this_thread;
-        /* paranoid */ verify(thrd->state == Active || thrd->state == Rerun);
+        /* paranoid */ verify(thrd->state == Active);
 
         // SKULLDUGGERY: It is possible that we are preempting this thread just before
@@ -701 +450 @@
         // 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;
@@ -715 +464 @@
 
 //=============================================================================================
-// Kernel Setup logic
-//=============================================================================================
-//-----------------------------------------------------------------------------
-// Kernel boot procedures
-static void __kernel_startup(void) {
-        verify( ! kernelTLS.preemption_state.enabled );
-        __cfadbg_print_safe(runtime_core, "Kernel : Starting\n");
-
-        __page_size = sysconf( _SC_PAGESIZE );
-
-        __cfa_dbg_global_clusters.list{ __get };
-        __cfa_dbg_global_clusters.lock{};
-
-        // Initialize the main cluster
-        mainCluster = (cluster *)&storage_mainCluster;
-        (*mainCluster){"Main Cluster"};
-
-        __cfadbg_print_safe(runtime_core, "Kernel : Main cluster ready\n");
-
-        // Start by initializing the main thread
-        // SKULLDUGGERY: the mainThread steals the process main thread
-        // which will then be scheduled by the mainProcessor normally
-        mainThread = ($thread *)&storage_mainThread;
-        current_stack_info_t info;
-        info.storage = (__stack_t*)&storage_mainThreadCtx;
-        (*mainThread){ &info };
-
-        __cfadbg_print_safe(runtime_core, "Kernel : Main thread ready\n");
-
-
-
-        // Construct the processor context of the main processor
-        void ?{}(processorCtx_t & this, processor * proc) {
-                (this.__cor){ "Processor" };
-                this.__cor.starter = 0p;
-                this.proc = proc;
-        }
-
-        void ?{}(processor & this) with( this ) {
-                name = "Main Processor";
-                cltr = mainCluster;
-                terminated{ 0 };
-                do_terminate = false;
-                preemption_alarm = 0p;
-                pending_preemption = false;
-                kernel_thread = pthread_self();
-
-                runner{ &this };
-                __cfadbg_print_safe(runtime_core, "Kernel : constructed main processor context %p\n", &runner);
-        }
-
-        // Initialize the main processor and the main processor ctx
-        // (the coroutine that contains the processing control flow)
-        mainProcessor = (processor *)&storage_mainProcessor;
-        (*mainProcessor){};
-
-        //initialize the global state variables
-        kernelTLS.this_processor = mainProcessor;
-        kernelTLS.this_thread    = mainThread;
-
-        // Enable preemption
-        kernel_start_preemption();
-
-        // Add the main thread to the ready queue
-        // once resume is called on mainProcessor->runner the mainThread needs to be scheduled like any normal thread
-        __schedule_thread(mainThread);
-
-        // SKULLDUGGERY: Force a context switch to the main processor to set the main thread's context to the current UNIX
-        // context. Hence, the main thread does not begin through __cfactx_invoke_thread, like all other threads. The trick here is that
-        // mainThread is on the ready queue when this call is made.
-        __kernel_first_resume( kernelTLS.this_processor );
-
-
-        // THE SYSTEM IS NOW COMPLETELY RUNNING
-
-
-        // Now that the system is up, finish creating systems that need threading
-        __kernel_io_finish_start( *mainCluster );
-
-
-        __cfadbg_print_safe(runtime_core, "Kernel : Started\n--------------------------------------------------\n\n");
-
-        verify( ! kernelTLS.preemption_state.enabled );
-        enable_interrupts( __cfaabi_dbg_ctx );
-        verify( TL_GET( preemption_state.enabled ) );
-}
-
-static void __kernel_shutdown(void) {
-        //Before we start shutting things down, wait for systems that need threading to shutdown
-        __kernel_io_prepare_stop( *mainCluster );
-
-        /* paranoid */ verify( TL_GET( preemption_state.enabled ) );
-        disable_interrupts();
-        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
-
-        __cfadbg_print_safe(runtime_core, "\n--------------------------------------------------\nKernel : Shutting down\n");
-
-        // SKULLDUGGERY: Notify the mainProcessor it needs to terminates.
-        // When its coroutine terminates, it return control to the mainThread
-        // which is currently here
-        __atomic_store_n(&mainProcessor->do_terminate, true, __ATOMIC_RELEASE);
-        __kernel_last_resume( kernelTLS.this_processor );
-        mainThread->self_cor.state = Halted;
-
-        // THE SYSTEM IS NOW COMPLETELY STOPPED
-
-        // Disable preemption
-        kernel_stop_preemption();
-
-        // Destroy the main processor and its context in reverse order of construction
-        // These were manually constructed so we need manually destroy them
-        void ^?{}(processor & this) with( this ){
-                /* paranoid */ verify( this.do_terminate == true );
-        }
-
-        ^(*mainProcessor){};
-
-        // Final step, destroy the main thread since it is no longer needed
-        // Since we provided a stack to this taxk it will not destroy anything
-        /* paranoid */ verify(mainThread->self_cor.stack.storage == (__stack_t*)(((uintptr_t)&storage_mainThreadCtx)| 0x1));
-        ^(*mainThread){};
-
-        ^(*mainCluster){};
-
-        ^(__cfa_dbg_global_clusters.list){};
-        ^(__cfa_dbg_global_clusters.lock){};
-
-        __cfadbg_print_safe(runtime_core, "Kernel : Shutdown complete\n");
-}
-
-//=============================================================================================
 // Kernel Idle Sleep
 //=============================================================================================
-static $thread * __halt(processor * this) with( *this ) {
-        if( do_terminate ) return 0p;
-
-        // First, lock the cluster idle
-        lock( cltr->idle_lock __cfaabi_dbg_ctx2 );
-
-        // Check if we can find a thread
-        if( $thread * found = __next_thread( cltr ) ) {
-                unlock( cltr->idle_lock );
-                return found;
-        }
-
-        // Move this processor from the active list to the idle list
-        move_to_front(cltr->procs, cltr->idles, *this);
-
-        // Unlock the idle lock so we don't go to sleep with a lock
-        unlock    (cltr->idle_lock);
-
-        // We are ready to sleep
-        __cfadbg_print_safe(runtime_core, "Kernel : Processor %p ready to sleep\n", this);
-        wait( idle );
-
-        // We have woken up
-        __cfadbg_print_safe(runtime_core, "Kernel : Processor %p woke up and ready to run\n", this);
-
-        // Get ourself off the idle list
-        with( *cltr ) {
-                lock  (idle_lock __cfaabi_dbg_ctx2);
-                move_to_front(idles, procs, *this);
-                unlock(idle_lock);
-        }
-
-        // Don't check the ready queue again, we may not be in a position to run a thread
-        return 0p;
-}
-
 // 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;
-
-        // First, lock the cluster idle
-        lock( this->idle_lock __cfaabi_dbg_ctx2 );
-
-        // Check if there is someone to wake up
-        if( !this->idles.head ) {
-                // Nope unlock and return false
-                unlock( this->idle_lock );
-                return false;
-        }
-
-        // Wake them up
-        __cfadbg_print_safe(runtime_core, "Kernel : waking Processor %p\n", this->idles.head);
-        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
-        post( this->idles.head->idle );
-
-        // Unlock and return true
-        unlock( this->idle_lock );
-        return true;
+static void __wake_one(struct __processor_id_t * id, cluster * this) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        /* paranoid */ verify( ready_schedule_islocked( id ) );
+
+        // Check if there is a sleeping processor
+        processor * p;
+        unsigned idle;
+        unsigned total;
+        [idle, total, p] = query(this->idles);
+
+        // If no one is sleeping, we are done
+        if( idle == 0 ) return;
+
+        // We found a processor, wake it up
+        post( p->idle );
+
+        #if !defined(__CFA_NO_STATISTICS__)
+                __tls_stats()->ready.sleep.wakes++;
+        #endif
+
+        /* paranoid */ verify( ready_schedule_islocked( id ) );
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+
+        return;
 }
 
 // Unconditionnaly wake a thread
-static bool __wake_proc(processor * this) {
+void __wake_proc(processor * this) {
         __cfadbg_print_safe(runtime_core, "Kernel : waking Processor %p\n", this);
 
@@ -917 +501 @@
                 bool ret = post( this->idle );
         enable_interrupts( __cfaabi_dbg_ctx );
-
-        return ret;
+}
+
+static void push  (__cluster_idles & this, processor & proc) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        lock( this );
+                this.idle++;
+                /* paranoid */ verify( this.idle <= this.total );
+
+                insert_first(this.list, proc);
+        unlock( this );
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+}
+
+static void remove(__cluster_idles & this, processor & proc) {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        lock( this );
+                this.idle--;
+                /* paranoid */ verify( this.idle >= 0 );
+
+                remove(proc);
+        unlock( this );
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+}
+
+static [unsigned idle, unsigned total, * processor] query( & __cluster_idles this ) {
+        for() {
+                uint64_t l = __atomic_load_n(&this.lock, __ATOMIC_SEQ_CST);
+                if( 1 == (l % 2) ) { Pause(); continue; }
+                unsigned idle    = this.idle;
+                unsigned total   = this.total;
+                processor * proc = &this.list`first;
+                if(l != __atomic_load_n(&this.lock, __ATOMIC_SEQ_CST)) { Pause(); continue; }
+                return [idle, total, proc];
+        }
 }
 
@@ -952 +568 @@
 
 void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
-        $thread * thrd = kernel_data;
+        $thread * thrd = ( $thread * ) kernel_data;
 
         if(thrd) {
@@ -1050 +666 @@
 
 //-----------------------------------------------------------------------------
-// Global Queues
-void doregister( cluster     & cltr ) {
-        lock      ( __cfa_dbg_global_clusters.lock __cfaabi_dbg_ctx2);
-        push_front( __cfa_dbg_global_clusters.list, cltr );
-        unlock    ( __cfa_dbg_global_clusters.lock );
-}
-
-void unregister( cluster     & cltr ) {
-        lock  ( __cfa_dbg_global_clusters.lock __cfaabi_dbg_ctx2);
-        remove( __cfa_dbg_global_clusters.list, cltr );
-        unlock( __cfa_dbg_global_clusters.lock );
-}
-
-void doregister( cluster * cltr, $thread & thrd ) {
-        lock      (cltr->thread_list_lock __cfaabi_dbg_ctx2);
-        cltr->nthreads += 1;
-        push_front(cltr->threads, thrd);
-        unlock    (cltr->thread_list_lock);
-}
-
-void unregister( cluster * cltr, $thread & thrd ) {
-        lock  (cltr->thread_list_lock __cfaabi_dbg_ctx2);
-        remove(cltr->threads, thrd );
-        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);
-}
-
-//-----------------------------------------------------------------------------
 // Debug
 __cfaabi_dbg_debug_do(
@@ -1118 +692 @@
         return true;
 }
+
+//-----------------------------------------------------------------------------
+// Statistics
+#if !defined(__CFA_NO_STATISTICS__)
+        void print_halts( processor & this ) {
+                this.print_halts = true;
+        }
+#endif
 // Local Variables: //
 // mode: c //