source: src/libcfa/concurrency/kernel.c @ 6b224a5

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 6b224a5 was 6b224a5, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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