source: src/libcfa/concurrency/kernel.c @ 0c78741

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 0c78741 was 0c78741, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

Implementation of internal scheduling in CFA

  • Property mode set to 100644
File size: 16.0 KB
RevLine 
[8118303]1//                              -*- Mode: CFA -*-
2//
3// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
4//
5// The contents of this file are covered under the licence agreement in the
6// file "LICENCE" distributed with Cforall.
7//
8// kernel.c --
9//
10// Author           : Thierry Delisle
[75f3522]11// Created On       : Tue Jan 17 12:27:26 2017
[8118303]12// Last Modified By : Thierry Delisle
13// Last Modified On : --
14// Update Count     : 0
15//
16
[9d944b2]17#include "startup.h"
18
[0c92c9f]19//Start and stop routine for the kernel, declared first to make sure they run first
[9d944b2]20void kernel_startup(void)  __attribute__(( constructor( STARTUP_PRIORITY_KERNEL ) ));
21void kernel_shutdown(void) __attribute__(( destructor ( STARTUP_PRIORITY_KERNEL ) ));
[0c92c9f]22
[8118303]23//Header
[75f3522]24#include "kernel_private.h"
[8118303]25
26//C Includes
[c84e80a]27#include <stddef.h>
[eb2e723]28extern "C" {
[9d944b2]29#include <stdio.h>
[8fcbb4c]30#include <fenv.h>
[eb2e723]31#include <sys/resource.h>
[9d944b2]32#include <signal.h>
33#include <unistd.h>
[eb2e723]34}
[8118303]35
36//CFA Includes
37#include "libhdr.h"
38
39//Private includes
40#define __CFA_INVOKE_PRIVATE__
41#include "invoke.h"
42
[8def349]43//-----------------------------------------------------------------------------
44// Kernel storage
45#define KERNEL_STORAGE(T,X) static char X##_storage[sizeof(T)]
46
47KERNEL_STORAGE(processorCtx_t, systemProcessorCtx);
48KERNEL_STORAGE(cluster, systemCluster);
49KERNEL_STORAGE(processor, systemProcessor);
[348006f]50KERNEL_STORAGE(thread_desc, mainThread);
[8def349]51KERNEL_STORAGE(machine_context_t, mainThread_context);
52
[bd98b58]53cluster * systemCluster;
[eb2e723]54processor * systemProcessor;
[348006f]55thread_desc * mainThread;
[eb2e723]56
[bd98b58]57//-----------------------------------------------------------------------------
58// Global state
59
[8def349]60thread_local processor * this_processor;
61
[c3acb841]62coroutine_desc * this_coroutine(void) {
[bd98b58]63        return this_processor->current_coroutine;
64}
65
[348006f]66thread_desc * this_thread(void) {
[bd98b58]67        return this_processor->current_thread;
[c84e80a]68}
69
70//-----------------------------------------------------------------------------
[8def349]71// Main thread construction
72struct current_stack_info_t {
73        machine_context_t ctx; 
74        unsigned int size;              // size of stack
75        void *base;                             // base of stack
76        void *storage;                  // pointer to stack
77        void *limit;                    // stack grows towards stack limit
78        void *context;                  // address of cfa_context_t
79        void *top;                              // address of top of storage
[c84e80a]80};
81
[8def349]82void ?{}( current_stack_info_t * this ) {
83        CtxGet( &this->ctx );
84        this->base = this->ctx.FP;
85        this->storage = this->ctx.SP;
86
87        rlimit r;
[132fad4]88        getrlimit( RLIMIT_STACK, &r);
[8def349]89        this->size = r.rlim_cur;
90
91        this->limit = (void *)(((intptr_t)this->base) - this->size);
92        this->context = &mainThread_context_storage;
93        this->top = this->base;
94}
95
96void ?{}( coStack_t * this, current_stack_info_t * info) {
97        this->size = info->size;
98        this->storage = info->storage;
99        this->limit = info->limit;
100        this->base = info->base;
101        this->context = info->context;
102        this->top = info->top;
103        this->userStack = true;
104}
105
[c3acb841]106void ?{}( coroutine_desc * this, current_stack_info_t * info) {
[8def349]107        (&this->stack){ info }; 
108        this->name = "Main Thread";
109        this->errno_ = 0;
[ee897e4b]110        this->state = Start;
[8def349]111}
112
[348006f]113void ?{}( thread_desc * this, current_stack_info_t * info) {
[17af7d1]114        (&this->cor){ info };
[8def349]115}
[c84e80a]116
[8def349]117//-----------------------------------------------------------------------------
118// Processor coroutine
[eb2e723]119void ?{}(processorCtx_t * this, processor * proc) {
[17af7d1]120        (&this->__cor){};
[c84e80a]121        this->proc = proc;
[8fcbb4c]122        proc->runner = this;
[8def349]123}
124
125void ?{}(processorCtx_t * this, processor * proc, current_stack_info_t * info) {
[17af7d1]126        (&this->__cor){ info };
[8def349]127        this->proc = proc;
[8fcbb4c]128        proc->runner = this;
[8def349]129}
130
131void ?{}(processor * this) {
132        this{ systemCluster };
133}
134
135void ?{}(processor * this, cluster * cltr) {
136        this->cltr = cltr;
137        this->current_coroutine = NULL;
138        this->current_thread = NULL;
[db6f06a]139        (&this->terminated){};
140        this->is_terminated = false;
[8def349]141
142        start( this );
[c84e80a]143}
144
[8fcbb4c]145void ?{}(processor * this, cluster * cltr, processorCtx_t * runner) {
[8def349]146        this->cltr = cltr;
147        this->current_coroutine = NULL;
148        this->current_thread = NULL;
[db6f06a]149        (&this->terminated){};
150        this->is_terminated = false;
[8def349]151
[8fcbb4c]152        this->runner = runner;
[9d944b2]153        LIB_DEBUG_PRINT_SAFE("Kernel : constructing processor context %p\n", runner);
[8fcbb4c]154        runner{ this };
[8def349]155}
156
157void ^?{}(processor * this) {
[db6f06a]158        if( ! this->is_terminated ) {
[9d944b2]159                LIB_DEBUG_PRINT_SAFE("Kernel : core %p signaling termination\n", this);
[db6f06a]160                this->is_terminated = true;
161                wait( &this->terminated );
[8def349]162        }
163}
164
165void ?{}(cluster * this) {
166        ( &this->ready_queue ){};
[eafb094]167        ( &this->lock ){};
[8def349]168}
169
170void ^?{}(cluster * this) {
[8fcbb4c]171       
[c84e80a]172}
173
[75f3522]174//=============================================================================================
175// Kernel Scheduling logic
176//=============================================================================================
[8fcbb4c]177//Main of the processor contexts
178void main(processorCtx_t * runner) {
179        processor * this = runner->proc;
[9d944b2]180        LIB_DEBUG_PRINT_SAFE("Kernel : core %p starting\n", this);
[8118303]181
[348006f]182        thread_desc * readyThread = NULL;
[db6f06a]183        for( unsigned int spin_count = 0; ! this->is_terminated; spin_count++ ) 
[75f3522]184        {
[bd98b58]185                readyThread = nextThread( this->cltr );
[8118303]186
[75f3522]187                if(readyThread) 
188                {
189                        runThread(this, readyThread);
190
191                        //Some actions need to be taken from the kernel
[db6f06a]192                        finishRunning(this);
[75f3522]193
[c84e80a]194                        spin_count = 0;
[75f3522]195                } 
196                else 
197                {
[c84e80a]198                        spin(this, &spin_count);
199                }               
200        }
[8118303]201
[9d944b2]202        LIB_DEBUG_PRINT_SAFE("Kernel : core %p unlocking thread\n", this);
[db6f06a]203        signal( &this->terminated );
[9d944b2]204        LIB_DEBUG_PRINT_SAFE("Kernel : core %p terminated\n", this);
[c84e80a]205}
206
[75f3522]207// runThread runs a thread by context switching
[0c92c9f]208// from the processor coroutine to the target thread
[348006f]209void runThread(processor * this, thread_desc * dst) {
[c3acb841]210        coroutine_desc * proc_cor = get_coroutine(this->runner);
211        coroutine_desc * thrd_cor = get_coroutine(dst);
[75f3522]212       
213        //Reset the terminating actions here
[db6f06a]214        this->finish.action_code = No_Action;
[8fcbb4c]215
[75f3522]216        //Update global state
217        this->current_thread = dst;
218
219        // Context Switch to the thread
220        ThreadCtxSwitch(proc_cor, thrd_cor);
221        // when ThreadCtxSwitch returns we are back in the processor coroutine
222}
223
224// Once a thread has finished running, some of
225// its final actions must be executed from the kernel
[db6f06a]226void finishRunning(processor * this) {
227        if( this->finish.action_code == Release ) {
228                unlock( this->finish.lock );
229        }
230        else if( this->finish.action_code == Schedule ) {
231                ScheduleThread( this->finish.thrd );
232        }
233        else if( this->finish.action_code == Release_Schedule ) {
234                unlock( this->finish.lock );           
235                ScheduleThread( this->finish.thrd );
236        }
[0c78741]237        else if( this->finish.action_code == Release_Multi ) {
238                for(int i = 0; i < this->finish.lock_count; i++) {
239                        unlock( this->finish.locks[i] );
240                }
241        }
242        else if( this->finish.action_code == Release_Multi_Schedule ) {
243                for(int i = 0; i < this->finish.lock_count; i++) {
244                        unlock( this->finish.locks[i] );
245                }
246                for(int i = 0; i < this->finish.thrd_count; i++) {
247                        ScheduleThread( this->finish.thrds[i] );
248                }
249        }
[db6f06a]250        else {
251                assert(this->finish.action_code == No_Action);
[8fcbb4c]252        }
[c84e80a]253}
254
[0c92c9f]255// Handles spinning logic
256// TODO : find some strategy to put cores to sleep after some time
[c84e80a]257void spin(processor * this, unsigned int * spin_count) {
258        (*spin_count)++;
259}
260
[0c92c9f]261// Context invoker for processors
262// This is the entry point for processors (kernel threads)
263// It effectively constructs a coroutine by stealing the pthread stack
[8def349]264void * CtxInvokeProcessor(void * arg) {
265        processor * proc = (processor *) arg;
266        this_processor = proc;
267        // SKULLDUGGERY: We want to create a context for the processor coroutine
268        // which is needed for the 2-step context switch. However, there is no reason
269        // to waste the perfectly valid stack create by pthread.
270        current_stack_info_t info;
271        machine_context_t ctx;
272        info.context = &ctx;
273        processorCtx_t proc_cor_storage = { proc, &info };
274
[9d944b2]275        LIB_DEBUG_PRINT_SAFE("Coroutine : created stack %p\n", proc_cor_storage.__cor.stack.base);
[8fcbb4c]276
[0c92c9f]277        //Set global state
[17af7d1]278        proc->current_coroutine = &proc->runner->__cor;
[8def349]279        proc->current_thread = NULL;
280
281        //We now have a proper context from which to schedule threads
[9d944b2]282        LIB_DEBUG_PRINT_SAFE("Kernel : core %p created (%p, %p)\n", proc, proc->runner, &ctx);
[8def349]283
284        // SKULLDUGGERY: Since the coroutine doesn't have its own stack, we can't
285        // resume it to start it like it normally would, it will just context switch
286        // back to here. Instead directly call the main since we already are on the
287        // appropriate stack.
[17af7d1]288        proc_cor_storage.__cor.state = Active;
[8def349]289      main( &proc_cor_storage );
[17af7d1]290      proc_cor_storage.__cor.state = Halted;
[8def349]291
[0c92c9f]292        // Main routine of the core returned, the core is now fully terminated
[9d944b2]293        LIB_DEBUG_PRINT_SAFE("Kernel : core %p main ended (%p)\n", proc, proc->runner); 
[8def349]294
295        return NULL;
[c84e80a]296}
297
[8def349]298void start(processor * this) {
[9d944b2]299        LIB_DEBUG_PRINT_SAFE("Kernel : Starting core %p\n", this);
[8def349]300       
[8fcbb4c]301        // pthread_attr_t attributes;
302        // pthread_attr_init( &attributes );
[eb2e723]303
[8fcbb4c]304        pthread_create( &this->kernel_thread, NULL, CtxInvokeProcessor, (void*)this );
[eb2e723]305
[8fcbb4c]306        // pthread_attr_destroy( &attributes );
[eb2e723]307
[9d944b2]308        LIB_DEBUG_PRINT_SAFE("Kernel : core %p started\n", this);       
[eb2e723]309}
310
[8def349]311//-----------------------------------------------------------------------------
312// Scheduler routines
[348006f]313void ScheduleThread( thread_desc * thrd ) {
[690f13c]314        if( !thrd ) return;
315
[8def349]316        assertf( thrd->next == NULL, "Expected null got %p", thrd->next );
317       
[db6f06a]318        lock( &systemProcessor->cltr->lock );
[8def349]319        append( &systemProcessor->cltr->ready_queue, thrd );
[db6f06a]320        unlock( &systemProcessor->cltr->lock );
321}
322
[348006f]323thread_desc * nextThread(cluster * this) {
[db6f06a]324        lock( &this->lock );
[348006f]325        thread_desc * head = pop_head( &this->ready_queue );
[db6f06a]326        unlock( &this->lock );
327        return head;
[eb2e723]328}
329
[75f3522]330void ScheduleInternal() {
331        suspend();
332}
333
[db6f06a]334void ScheduleInternal( spinlock * lock ) {
[89a3df5]335        this_processor->finish.action_code = Release;
336        this_processor->finish.lock = lock;
[db6f06a]337        suspend();
338}
339
[348006f]340void ScheduleInternal( thread_desc * thrd ) {
[89a3df5]341        this_processor->finish.action_code = Schedule;
342        this_processor->finish.thrd = thrd;
[db6f06a]343        suspend();
344}
345
[348006f]346void ScheduleInternal( spinlock * lock, thread_desc * thrd ) {
[89a3df5]347        this_processor->finish.action_code = Release_Schedule;
348        this_processor->finish.lock = lock;
349        this_processor->finish.thrd = thrd;
[db6f06a]350        suspend();
[eb2e723]351}
352
[0c78741]353void ScheduleInternal(spinlock ** locks, unsigned short count) {
354        this_processor->finish.action_code = Release_Multi;
355        this_processor->finish.locks = locks;
356        this_processor->finish.lock_count = count;
357        suspend();
358}
359
360void ScheduleInternal(spinlock ** locks, unsigned short lock_count, thread_desc ** thrds, unsigned short thrd_count) {
361        this_processor->finish.action_code = Release_Multi_Schedule;
362        this_processor->finish.locks = locks;
363        this_processor->finish.lock_count = lock_count;
364        this_processor->finish.thrds = thrds;
365        this_processor->finish.thrd_count = thrd_count;
366        suspend();
367}
368
[eb2e723]369//-----------------------------------------------------------------------------
370// Kernel boot procedures
371void kernel_startup(void) {
[9d944b2]372        LIB_DEBUG_PRINT_SAFE("Kernel : Starting\n");   
[eb2e723]373
374        // Start by initializing the main thread
[8fcbb4c]375        // SKULLDUGGERY: the mainThread steals the process main thread
376        // which will then be scheduled by the systemProcessor normally
[348006f]377        mainThread = (thread_desc *)&mainThread_storage;
[8fcbb4c]378        current_stack_info_t info;
[8def349]379        mainThread{ &info };
[eb2e723]380
[bd98b58]381        // Initialize the system cluster
382        systemCluster = (cluster *)&systemCluster_storage;
383        systemCluster{};
384
[8def349]385        // Initialize the system processor and the system processor ctx
[eb2e723]386        // (the coroutine that contains the processing control flow)
[8def349]387        systemProcessor = (processor *)&systemProcessor_storage;
388        systemProcessor{ systemCluster, (processorCtx_t *)&systemProcessorCtx_storage };
[eb2e723]389
[dcb42b8]390        // Add the main thread to the ready queue
391        // once resume is called on systemProcessor->ctx the mainThread needs to be scheduled like any normal thread
[75f3522]392        ScheduleThread(mainThread);
[eb2e723]393
[dcb42b8]394        //initialize the global state variables
[bd98b58]395        this_processor = systemProcessor;
396        this_processor->current_thread = mainThread;
[17af7d1]397        this_processor->current_coroutine = &mainThread->cor;
[eb2e723]398
[dcb42b8]399        // SKULLDUGGERY: Force a context switch to the system processor to set the main thread's context to the current UNIX
400        // context. Hence, the main thread does not begin through CtxInvokeThread, like all other threads. The trick here is that
401        // mainThread is on the ready queue when this call is made.
[8fcbb4c]402        resume(systemProcessor->runner);
[eb2e723]403
[dcb42b8]404
405
406        // THE SYSTEM IS NOW COMPLETELY RUNNING
[9d944b2]407        LIB_DEBUG_PRINT_SAFE("Kernel : Started\n--------------------------------------------------\n\n");
[eb2e723]408}
409
[dcb42b8]410void kernel_shutdown(void) {
[9d944b2]411        LIB_DEBUG_PRINT_SAFE("\n--------------------------------------------------\nKernel : Shutting down\n");
[eb2e723]412
[dcb42b8]413        // SKULLDUGGERY: Notify the systemProcessor it needs to terminates.
414        // When its coroutine terminates, it return control to the mainThread
415        // which is currently here
[db6f06a]416        systemProcessor->is_terminated = true;
[eb2e723]417        suspend();
418
[dcb42b8]419        // THE SYSTEM IS NOW COMPLETELY STOPPED
[eb2e723]420
[dcb42b8]421        // Destroy the system processor and its context in reverse order of construction
422        // These were manually constructed so we need manually destroy them
[8fcbb4c]423        ^(systemProcessor->runner){};
[eb2e723]424        ^(systemProcessor){};
425
[dcb42b8]426        // Final step, destroy the main thread since it is no longer needed
427        // Since we provided a stack to this taxk it will not destroy anything
[eb2e723]428        ^(mainThread){};
429
[9d944b2]430        LIB_DEBUG_PRINT_SAFE("Kernel : Shutdown complete\n");   
431}
432
433static spinlock kernel_abort_lock;
434static spinlock kernel_debug_lock;
435static bool kernel_abort_called = false;
436
437void * kernel_abort    (void) __attribute__ ((__nothrow__)) {
438        // abort cannot be recursively entered by the same or different processors because all signal handlers return when
439        // the globalAbort flag is true.
440        lock( &kernel_abort_lock );
441
442        // first task to abort ?
443        if ( !kernel_abort_called ) {                   // not first task to abort ?
444                kernel_abort_called = true;
445                unlock( &kernel_abort_lock );
446        } 
447        else {
448                unlock( &kernel_abort_lock );
449               
450                sigset_t mask;
451                sigemptyset( &mask );
452                sigaddset( &mask, SIGALRM );                    // block SIGALRM signals
453                sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
454                sigsuspend( &mask );                            // block the processor to prevent further damage during abort
455                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it             
456        }
457
458        return this_thread();
459}
460
461void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
462        thread_desc * thrd = kernel_data;
463
464        int len = snprintf( abort_text, abort_text_size, "Error occurred while executing task %.256s (%p)", thrd->cor.name, thrd );
465        __lib_debug_write( STDERR_FILENO, abort_text, len );
466
467        if ( thrd != this_coroutine() ) {
468                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine()->name, this_coroutine() );
469                __lib_debug_write( STDERR_FILENO, abort_text, len );
470        } 
471        else {
472                __lib_debug_write( STDERR_FILENO, ".\n", 2 );
473        }
474}
475
476extern "C" {
477        void __lib_debug_acquire() {
478                lock(&kernel_debug_lock);
479        }
480
481        void __lib_debug_release() {
482                unlock(&kernel_debug_lock);
483        }
[8118303]484}
485
[bd98b58]486//-----------------------------------------------------------------------------
487// Locks
[db6f06a]488void ?{}( spinlock * this ) {
489        this->lock = 0;
[bd98b58]490}
[db6f06a]491void ^?{}( spinlock * this ) {
[bd98b58]492
[db6f06a]493}
494
495void lock( spinlock * this ) {
496        for ( unsigned int i = 1;; i += 1 ) {
497                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) break;
498        }
499}
[bd98b58]500
[db6f06a]501void unlock( spinlock * this ) {
502        __sync_lock_release_4( &this->lock );
[bd98b58]503}
504
[db6f06a]505void ?{}( signal_once * this ) {
[5ea06d6]506        this->cond = false;
[db6f06a]507}
508void ^?{}( signal_once * this ) {
509
510}
511
512void wait( signal_once * this ) {
513        lock( &this->lock );
[5ea06d6]514        if( !this->cond ) {
[8def349]515                append( &this->blocked, this_thread() );
[db6f06a]516                ScheduleInternal( &this->lock );
517                lock( &this->lock );
[8def349]518        }
[db6f06a]519        unlock( &this->lock );
[bd98b58]520}
521
[db6f06a]522void signal( signal_once * this ) {
523        lock( &this->lock );
524        {
[5ea06d6]525                this->cond = true;
[db6f06a]526
[348006f]527                thread_desc * it;
[db6f06a]528                while( it = pop_head( &this->blocked) ) {
529                        ScheduleThread( it );
530                }
[bd98b58]531        }
[db6f06a]532        unlock( &this->lock );
[bd98b58]533}
534
535//-----------------------------------------------------------------------------
536// Queues
[5ea06d6]537void ?{}( __thread_queue_t * this ) {
[bd98b58]538        this->head = NULL;
539        this->tail = &this->head;
540}
541
[5ea06d6]542void append( __thread_queue_t * this, thread_desc * t ) {
[f07e037]543        assert(this->tail != NULL);
[bd98b58]544        *this->tail = t;
545        this->tail = &t->next;
546}
547
[5ea06d6]548thread_desc * pop_head( __thread_queue_t * this ) {
[348006f]549        thread_desc * head = this->head;
[bd98b58]550        if( head ) {
551                this->head = head->next;
552                if( !head->next ) {
553                        this->tail = &this->head;
554                }
555                head->next = NULL;
556        }       
557        return head;
558}
[690f13c]559
[0c78741]560void ?{}( __condition_stack_t * this ) {
[690f13c]561        this->top = NULL;
562}
563
[0c78741]564void push( __condition_stack_t * this, __condition_criterion_t * t ) {
565        assert( !t->next );
[690f13c]566        t->next = this->top;
567        this->top = t;
568}
569
[0c78741]570__condition_criterion_t * pop( __condition_stack_t * this ) {
571        __condition_criterion_t * top = this->top;
[690f13c]572        if( top ) {
573                this->top = top->next;
574                top->next = NULL;
575        }       
576        return top;
577}
[8118303]578// Local Variables: //
579// mode: c //
580// tab-width: 4 //
581// End: //
Note: See TracBrowser for help on using the repository browser.