source: src/libcfa/concurrency/kernel.c @ 8fc45b7

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

Internal helper functions now use arrays and references instead of pointers

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