source: src/libcfa/concurrency/kernel.c @ cc344be

//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// kernel.c --
//
// Author           : Thierry Delisle
// Created On       : Tue Jan 17 12:27:26 2017
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Dec  8 16:23:33 2017
// Update Count     : 3
//

//C Includes
#include <stddef.h>
#define ftype `ftype`
extern "C" {
#include <stdio.h>
#include <fenv.h>
#include <sys/resource.h>
#include <signal.h>
#include <unistd.h>
}
#undef ftype

//CFA Includes
#include "kernel_private.h"
#include "preemption.h"
#include "startup.h"

//Private includes
#define __CFA_INVOKE_PRIVATE__
#include "invoke.h"

//Start and stop routine for the kernel, declared first to make sure they run first
void kernel_startup(void)  __attribute__(( constructor( STARTUP_PRIORITY_KERNEL ) ));
void kernel_shutdown(void) __attribute__(( destructor ( STARTUP_PRIORITY_KERNEL ) ));

//-----------------------------------------------------------------------------
// Kernel storage
KERNEL_STORAGE(cluster,           mainCluster);
KERNEL_STORAGE(processor,         mainProcessor);
KERNEL_STORAGE(processorCtx_t,    mainProcessorCtx);
KERNEL_STORAGE(thread_desc,       mainThread);
KERNEL_STORAGE(machine_context_t, mainThreadCtx);

cluster *     mainCluster;
processor *   mainProcessor;
thread_desc * mainThread;

//-----------------------------------------------------------------------------
// Global state

thread_local coroutine_desc * volatile this_coroutine;
thread_local thread_desc *    volatile this_thread;
thread_local processor *      volatile this_processor;

volatile thread_local bool preemption_in_progress = 0;
volatile thread_local unsigned short disable_preempt_count = 1;

//-----------------------------------------------------------------------------
// Main thread construction
struct current_stack_info_t {
        machine_context_t ctx;
        unsigned int size;              // size of stack
        void *base;                             // base of stack
        void *storage;                  // pointer to stack
        void *limit;                    // stack grows towards stack limit
        void *context;                  // address of cfa_context_t
        void *top;                              // address of top of storage
};

void ?{}( current_stack_info_t & this ) {
        CtxGet( this.ctx );
        this.base = this.ctx.FP;
        this.storage = this.ctx.SP;

        rlimit r;
        getrlimit( RLIMIT_STACK, &r);
        this.size = r.rlim_cur;

        this.limit = (void *)(((intptr_t)this.base) - this.size);
        this.context = &storage_mainThreadCtx;
        this.top = this.base;
}

void ?{}( coStack_t & this, current_stack_info_t * info) with( this ) {
        size      = info->size;
        storage   = info->storage;
        limit     = info->limit;
        base      = info->base;
        context   = info->context;
        top       = info->top;
        userStack = true;
}

void ?{}( coroutine_desc & this, current_stack_info_t * info) with( this ) {
        stack{ info };
        name = "Main Thread";
        errno_ = 0;
        state = Start;
        starter = NULL;
}

void ?{}( thread_desc & this, current_stack_info_t * info) with( this ) {
        self_cor{ info };
}

//-----------------------------------------------------------------------------
// Processor coroutine

// Construct the processor context of the main processor
void ?{}(processorCtx_t & this, processor * proc) {
        (this.__cor){ "Processor" };
        this.__cor.starter = NULL;
        this.proc = proc;
        proc->runner = &this;
}

// Construct the processor context of non-main processors
void ?{}(processorCtx_t & this, processor * proc, current_stack_info_t * info) {
        (this.__cor){ info };
        this.proc = proc;
        proc->runner = &this;
}

void ?{}(processor & this) {
        this{ mainCluster };
}

void ?{}(processor & this, cluster * cltr) {
        this.cltr = cltr;
        this.terminated{ 0 };
        this.do_terminate = false;
        this.preemption_alarm = NULL;
        this.pending_preemption = false;

        start( &this );
}

void ?{}(processor & this, cluster * cltr, processorCtx_t & runner) {
        this.cltr = cltr;
        this.terminated{ 0 };
        this.do_terminate = false;
        this.preemption_alarm = NULL;
        this.pending_preemption = false;
        this.kernel_thread = pthread_self();

        this.runner = &runner;
        __cfaabi_dbg_print_safe("Kernel : constructing main processor context %p\n", &runner);
        runner{ &this };
}

void ^?{}(processor & this) with( this ){
        if( ! do_terminate ) {
                __cfaabi_dbg_print_safe("Kernel : core %p signaling termination\n", &this);
                do_terminate = true;
                P( terminated );
                pthread_join( kernel_thread, NULL );
        }
}

void ?{}(cluster & this) with( this ) {
        ready_queue{};
        ready_queue_lock{};

        preemption = default_preemption();
}

void ^?{}(cluster & this) {

}

//=============================================================================================
// Kernel Scheduling logic
//=============================================================================================
//Main of the processor contexts
void main(processorCtx_t & runner) {
        processor * this = runner.proc;

        __cfaabi_dbg_print_safe("Kernel : core %p starting\n", this);

        {
                // Setup preemption data
                preemption_scope scope = { this };

                __cfaabi_dbg_print_safe("Kernel : core %p started\n", this);

                thread_desc * readyThread = NULL;
                for( unsigned int spin_count = 0; ! this->do_terminate; spin_count++ )
                {
                        readyThread = nextThread( this->cltr );

                        if(readyThread)
                        {
                                verify( disable_preempt_count > 0 );

                                runThread(this, readyThread);

                                verify( disable_preempt_count > 0 );

                                //Some actions need to be taken from the kernel
                                finishRunning(this);

                                spin_count = 0;
                        }
                        else
                        {
                                spin(this, &spin_count);
                        }
                }

                __cfaabi_dbg_print_safe("Kernel : core %p stopping\n", this);
        }

        V( this->terminated );

        __cfaabi_dbg_print_safe("Kernel : core %p terminated\n", this);
}

// runThread runs a thread by context switching
// from the processor coroutine to the target thread
void runThread(processor * this, thread_desc * dst) {
        coroutine_desc * proc_cor = get_coroutine(*this->runner);
        coroutine_desc * thrd_cor = get_coroutine(dst);

        //Reset the terminating actions here
        this->finish.action_code = No_Action;

        //Update global state
        this_thread = dst;

        // Context Switch to the thread
        ThreadCtxSwitch(proc_cor, thrd_cor);
        // when ThreadCtxSwitch returns we are back in the processor coroutine
}

// Once a thread has finished running, some of
// its final actions must be executed from the kernel
void finishRunning(processor * this) with( this->finish ) {
        if( action_code == Release ) {
                verify( disable_preempt_count > 1 );
                unlock( *lock );
        }
        else if( action_code == Schedule ) {
                ScheduleThread( thrd );
        }
        else if( action_code == Release_Schedule ) {
                verify( disable_preempt_count > 1 );
                unlock( *lock );
                ScheduleThread( thrd );
        }
        else if( action_code == Release_Multi ) {
                verify( disable_preempt_count > lock_count );
                for(int i = 0; i < lock_count; i++) {
                        unlock( *locks[i] );
                }
        }
        else if( action_code == Release_Multi_Schedule ) {
                for(int i = 0; i < lock_count; i++) {
                        unlock( *locks[i] );
                }
                for(int i = 0; i < thrd_count; i++) {
                        ScheduleThread( thrds[i] );
                }
        }
        else {
                assert(action_code == No_Action);
        }
}

// Handles spinning logic
// TODO : find some strategy to put cores to sleep after some time
void spin(processor * this, unsigned int * spin_count) {
        (*spin_count)++;
}

// Context invoker for processors
// This is the entry point for processors (kernel threads)
// It effectively constructs a coroutine by stealing the pthread stack
void * CtxInvokeProcessor(void * arg) {
        processor * proc = (processor *) arg;
        this_processor = proc;
        this_coroutine = NULL;
        this_thread = NULL;
        disable_preempt_count = 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;
        machine_context_t ctx;
        info.context = &ctx;
        processorCtx_t proc_cor_storage = { proc, &info };

        __cfaabi_dbg_print_safe("Coroutine : created stack %p\n", proc_cor_storage.__cor.stack.base);

        //Set global state
        this_coroutine = &proc->runner->__cor;
        this_thread = NULL;

        //We now have a proper context from which to schedule threads
        __cfaabi_dbg_print_safe("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.
        proc_cor_storage.__cor.state = Active;
        main( proc_cor_storage );
        proc_cor_storage.__cor.state = Halted;

        // Main routine of the core returned, the core is now fully terminated
        __cfaabi_dbg_print_safe("Kernel : core %p main ended (%p)\n", proc, proc->runner);

        return NULL;
}

void start(processor * this) {
        __cfaabi_dbg_print_safe("Kernel : Starting core %p\n", this);

        pthread_create( &this->kernel_thread, NULL, CtxInvokeProcessor, (void*)this );

        __cfaabi_dbg_print_safe("Kernel : core %p started\n", this);
}

//-----------------------------------------------------------------------------
// Scheduler routines
void ScheduleThread( thread_desc * thrd ) {
        // if( !thrd ) return;
        verify( thrd );
        verify( thrd->self_cor.state != Halted );

        verify( disable_preempt_count > 0 );

        verifyf( thrd->next == NULL, "Expected null got %p", thrd->next );

        with( *this_processor->cltr ) {
                lock  ( ready_queue_lock __cfaabi_dbg_ctx2 );
                append( ready_queue, thrd );
                unlock( ready_queue_lock );
        }

        verify( disable_preempt_count > 0 );
}

thread_desc * nextThread(cluster * this) with( *this ) {
        verify( disable_preempt_count > 0 );
        lock( ready_queue_lock __cfaabi_dbg_ctx2 );
        thread_desc * head = pop_head( ready_queue );
        unlock( ready_queue_lock );
        verify( disable_preempt_count > 0 );
        return head;
}

void BlockInternal() {
        disable_interrupts();
        verify( disable_preempt_count > 0 );
        suspend();
        verify( disable_preempt_count > 0 );
        enable_interrupts( __cfaabi_dbg_ctx );
}

void BlockInternal( __spinlock_t * lock ) {
        disable_interrupts();
        this_processor->finish.action_code = Release;
        this_processor->finish.lock        = lock;

        verify( disable_preempt_count > 1 );
        suspend();
        verify( disable_preempt_count > 0 );

        enable_interrupts( __cfaabi_dbg_ctx );
}

void BlockInternal( thread_desc * thrd ) {
        disable_interrupts();
        this_processor->finish.action_code = Schedule;
        this_processor->finish.thrd        = thrd;

        verify( disable_preempt_count > 0 );
        suspend();
        verify( disable_preempt_count > 0 );

        enable_interrupts( __cfaabi_dbg_ctx );
}

void BlockInternal( __spinlock_t * lock, thread_desc * thrd ) {
        assert(thrd);
        disable_interrupts();
        this_processor->finish.action_code = Release_Schedule;
        this_processor->finish.lock        = lock;
        this_processor->finish.thrd        = thrd;

        verify( disable_preempt_count > 1 );
        suspend();
        verify( disable_preempt_count > 0 );

        enable_interrupts( __cfaabi_dbg_ctx );
}

void BlockInternal(__spinlock_t * locks [], unsigned short count) {
        disable_interrupts();
        this_processor->finish.action_code = Release_Multi;
        this_processor->finish.locks       = locks;
        this_processor->finish.lock_count  = count;

        verify( disable_preempt_count > 0 );
        suspend();
        verify( disable_preempt_count > 0 );

        enable_interrupts( __cfaabi_dbg_ctx );
}

void BlockInternal(__spinlock_t * locks [], unsigned short lock_count, thread_desc * thrds [], unsigned short thrd_count) {
        disable_interrupts();
        this_processor->finish.action_code = Release_Multi_Schedule;
        this_processor->finish.locks       = locks;
        this_processor->finish.lock_count  = lock_count;
        this_processor->finish.thrds       = thrds;
        this_processor->finish.thrd_count  = thrd_count;

        verify( disable_preempt_count > 0 );
        suspend();
        verify( disable_preempt_count > 0 );

        enable_interrupts( __cfaabi_dbg_ctx );
}

void LeaveThread(__spinlock_t * lock, thread_desc * thrd) {
        verify( disable_preempt_count > 0 );
        this_processor->finish.action_code = thrd ? Release_Schedule : Release;
        this_processor->finish.lock        = lock;
        this_processor->finish.thrd        = thrd;

        suspend();
}

//=============================================================================================
// Kernel Setup logic
//=============================================================================================
//-----------------------------------------------------------------------------
// Kernel boot procedures
void kernel_startup(void) {
        __cfaabi_dbg_print_safe("Kernel : Starting\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_desc *)&storage_mainThread;
        current_stack_info_t info;
        (*mainThread){ &info };

        __cfaabi_dbg_print_safe("Kernel : Main thread ready\n");

        // Initialize the main cluster
        mainCluster = (cluster *)&storage_mainCluster;
        (*mainCluster){};

        __cfaabi_dbg_print_safe("Kernel : main cluster ready\n");

        // Initialize the main processor and the main processor ctx
        // (the coroutine that contains the processing control flow)
        mainProcessor = (processor *)&storage_mainProcessor;
        (*mainProcessor){ mainCluster, *(processorCtx_t *)&storage_mainProcessorCtx };

        //initialize the global state variables
        this_processor = mainProcessor;
        this_thread = mainThread;
        this_coroutine = &mainThread->self_cor;

        // 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
        ScheduleThread(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 CtxInvokeThread, like all other threads. The trick here is that
        // mainThread is on the ready queue when this call is made.
        resume( *mainProcessor->runner );



        // THE SYSTEM IS NOW COMPLETELY RUNNING
        __cfaabi_dbg_print_safe("Kernel : Started\n--------------------------------------------------\n\n");

        enable_interrupts( __cfaabi_dbg_ctx );
}

void kernel_shutdown(void) {
        __cfaabi_dbg_print_safe("\n--------------------------------------------------\nKernel : Shutting down\n");

        disable_interrupts();

        // SKULLDUGGERY: Notify the mainProcessor it needs to terminates.
        // When its coroutine terminates, it return control to the mainThread
        // which is currently here
        mainProcessor->do_terminate = true;
        suspend();

        // 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
        ^(*mainProcessor->runner){};
        ^(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
        ^(mainThread){};

        __cfaabi_dbg_print_safe("Kernel : Shutdown complete\n");
}

//=============================================================================================
// Unexpected Terminating logic
//=============================================================================================


static __spinlock_t kernel_abort_lock;
static __spinlock_t kernel_debug_lock;
static bool kernel_abort_called = false;

void * kernel_abort    (void) __attribute__ ((__nothrow__)) {
        // abort cannot be recursively entered by the same or different processors because all signal handlers return when
        // the globalAbort flag is true.
        lock( kernel_abort_lock __cfaabi_dbg_ctx2 );

        // first task to abort ?
        if ( !kernel_abort_called ) {                   // not first task to abort ?
                kernel_abort_called = true;
                unlock( kernel_abort_lock );
        }
        else {
                unlock( kernel_abort_lock );

                sigset_t mask;
                sigemptyset( &mask );
                sigaddset( &mask, SIGALRM );                    // block SIGALRM signals
                sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
                sigsuspend( &mask );                            // block the processor to prevent further damage during abort
                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it
        }

        return this_thread;
}

void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
        thread_desc * thrd = kernel_data;

        int len = snprintf( abort_text, abort_text_size, "Error occurred while executing task %.256s (%p)", thrd->self_cor.name, thrd );
        __cfaabi_dbg_bits_write( abort_text, len );

        if ( thrd != this_coroutine ) {
                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine->name, this_coroutine );
                __cfaabi_dbg_bits_write( abort_text, len );
        }
        else {
                __cfaabi_dbg_bits_write( ".\n", 2 );
        }
}

extern "C" {
        void __cfaabi_dbg_bits_acquire() {
                lock( kernel_debug_lock __cfaabi_dbg_ctx2 );
        }

        void __cfaabi_dbg_bits_release() {
                unlock( kernel_debug_lock );
        }
}

//=============================================================================================
// Kernel Utilities
//=============================================================================================
//-----------------------------------------------------------------------------
// Locks
void  ?{}( semaphore & this, int count = 1 ) {
        (this.lock){};
        this.count = count;
        (this.waiting){};
}
void ^?{}(semaphore & this) {}

void P(semaphore & this) with( this ){
        lock( lock __cfaabi_dbg_ctx2 );
        count -= 1;
        if ( count < 0 ) {
                // queue current task
                append( waiting, (thread_desc *)this_thread );

                // atomically release spin lock and block
                BlockInternal( &lock );
        }
        else {
            unlock( lock );
        }
}

void V(semaphore & this) with( this ) {
        thread_desc * thrd = NULL;
        lock( lock __cfaabi_dbg_ctx2 );
        count += 1;
        if ( count <= 0 ) {
                // remove task at head of waiting list
                thrd = pop_head( waiting );
        }

        unlock( lock );

        // make new owner
        WakeThread( thrd );
}

//-----------------------------------------------------------------------------
// Debug
__cfaabi_dbg_debug_do(
        struct {
                thread_desc * tail;
        } __cfaabi_dbg_thread_list = { NULL };

        void __cfaabi_dbg_thread_register( thread_desc * thrd ) {
                if( !__cfaabi_dbg_thread_list.tail ) {
                        __cfaabi_dbg_thread_list.tail = thrd;
                        return;
                }
                __cfaabi_dbg_thread_list.tail->dbg_next = thrd;
                thrd->dbg_prev = __cfaabi_dbg_thread_list.tail;
                __cfaabi_dbg_thread_list.tail = thrd;
        }

        void __cfaabi_dbg_thread_unregister( thread_desc * thrd ) {
                thread_desc * prev = thrd->dbg_prev;
                thread_desc * next = thrd->dbg_next;

                if( next ) { next->dbg_prev = prev; }
                else       {
                        assert( __cfaabi_dbg_thread_list.tail == thrd );
                        __cfaabi_dbg_thread_list.tail = prev;
                }

                if( prev ) { prev->dbg_next = next; }

                thrd->dbg_prev = NULL;
                thrd->dbg_next = NULL;
        }
)
// Local Variables: //
// mode: c //
// tab-width: 4 //
// End: //