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

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

Commented some debug messages.
Monitors now yield when spinning.
Debug mode saves more information about previous locks and interrupts

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