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

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 b826e6b was 969b3fe, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

More clean-up of the kernel code

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