source: src/libcfa/concurrency/kernel.c @ 242a902

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 242a902 was 242a902, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

Convert more library files to use references

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