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

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

Preemption now uses an oracle kernel thread

  • Property mode set to 100644
File size: 18.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        pthread_create( &this->kernel_thread, NULL, CtxInvokeProcessor, (void*)this );
327
328        LIB_DEBUG_PRINT_SAFE("Kernel : core %p started\n", this);
329}
330
331//-----------------------------------------------------------------------------
332// Scheduler routines
333void ScheduleThread( thread_desc * thrd ) {
334        // if( !thrd ) return;
335        assert( thrd );
336        assert( thrd->cor.state != Halted );
337
338        verify( disable_preempt_count > 0 );
339
340        verifyf( thrd->next == NULL, "Expected null got %p", thrd->next );
341
342        lock( &systemProcessor->proc.cltr->lock DEBUG_CTX2 );
343        append( &systemProcessor->proc.cltr->ready_queue, thrd );
344        unlock( &systemProcessor->proc.cltr->lock );
345
346        verify( disable_preempt_count > 0 );
347}
348
349thread_desc * nextThread(cluster * this) {
350        verify( disable_preempt_count > 0 );
351        lock( &this->lock DEBUG_CTX2 );
352        thread_desc * head = pop_head( &this->ready_queue );
353        unlock( &this->lock );
354        verify( disable_preempt_count > 0 );
355        return head;
356}
357
358void BlockInternal() {
359        disable_interrupts();
360        verify( disable_preempt_count > 0 );
361        suspend();
362        verify( disable_preempt_count > 0 );
363        enable_interrupts( DEBUG_CTX );
364}
365
366void BlockInternal( spinlock * lock ) {
367        disable_interrupts();
368        this_processor->finish.action_code = Release;
369        this_processor->finish.lock = lock;
370
371        verify( disable_preempt_count > 0 );
372        suspend();
373        verify( disable_preempt_count > 0 );
374
375        enable_interrupts( DEBUG_CTX );
376}
377
378void BlockInternal( thread_desc * thrd ) {
379        disable_interrupts();
380        assert( thrd->cor.state != Halted );
381        this_processor->finish.action_code = Schedule;
382        this_processor->finish.thrd = thrd;
383
384        verify( disable_preempt_count > 0 );
385        suspend();
386        verify( disable_preempt_count > 0 );
387
388        enable_interrupts( DEBUG_CTX );
389}
390
391void BlockInternal( spinlock * lock, thread_desc * thrd ) {
392        disable_interrupts();
393        this_processor->finish.action_code = Release_Schedule;
394        this_processor->finish.lock = lock;
395        this_processor->finish.thrd = thrd;
396
397        verify( disable_preempt_count > 0 );
398        suspend();
399        verify( disable_preempt_count > 0 );
400
401        enable_interrupts( DEBUG_CTX );
402}
403
404void BlockInternal(spinlock ** locks, unsigned short count) {
405        disable_interrupts();
406        this_processor->finish.action_code = Release_Multi;
407        this_processor->finish.locks = locks;
408        this_processor->finish.lock_count = count;
409
410        verify( disable_preempt_count > 0 );
411        suspend();
412        verify( disable_preempt_count > 0 );
413
414        enable_interrupts( DEBUG_CTX );
415}
416
417void BlockInternal(spinlock ** locks, unsigned short lock_count, thread_desc ** thrds, unsigned short thrd_count) {
418        disable_interrupts();
419        this_processor->finish.action_code = Release_Multi_Schedule;
420        this_processor->finish.locks = locks;
421        this_processor->finish.lock_count = lock_count;
422        this_processor->finish.thrds = thrds;
423        this_processor->finish.thrd_count = thrd_count;
424
425        verify( disable_preempt_count > 0 );
426        suspend();
427        verify( disable_preempt_count > 0 );
428
429        enable_interrupts( DEBUG_CTX );
430}
431
432//=============================================================================================
433// Kernel Setup logic
434//=============================================================================================
435//-----------------------------------------------------------------------------
436// Kernel boot procedures
437void kernel_startup(void) {
438        LIB_DEBUG_PRINT_SAFE("Kernel : Starting\n");
439
440        // Start by initializing the main thread
441        // SKULLDUGGERY: the mainThread steals the process main thread
442        // which will then be scheduled by the systemProcessor normally
443        mainThread = (thread_desc *)&mainThread_storage;
444        current_stack_info_t info;
445        mainThread{ &info };
446
447        LIB_DEBUG_PRINT_SAFE("Kernel : Main thread ready\n");
448
449        // Initialize the system cluster
450        systemCluster = (cluster *)&systemCluster_storage;
451        systemCluster{};
452
453        LIB_DEBUG_PRINT_SAFE("Kernel : System cluster ready\n");
454
455        // Initialize the system processor and the system processor ctx
456        // (the coroutine that contains the processing control flow)
457        systemProcessor = (system_proc_t *)&systemProcessor_storage;
458        systemProcessor{ systemCluster, (processorCtx_t *)&systemProcessorCtx_storage };
459
460        // Add the main thread to the ready queue
461        // once resume is called on systemProcessor->runner the mainThread needs to be scheduled like any normal thread
462        ScheduleThread(mainThread);
463
464        //initialize the global state variables
465        this_processor = &systemProcessor->proc;
466        this_thread = mainThread;
467        this_coroutine = &mainThread->cor;
468        disable_preempt_count = 1;
469
470        // Enable preemption
471        kernel_start_preemption();
472
473        // SKULLDUGGERY: Force a context switch to the system processor to set the main thread's context to the current UNIX
474        // context. Hence, the main thread does not begin through CtxInvokeThread, like all other threads. The trick here is that
475        // mainThread is on the ready queue when this call is made.
476        resume( systemProcessor->proc.runner );
477
478
479
480        // THE SYSTEM IS NOW COMPLETELY RUNNING
481        LIB_DEBUG_PRINT_SAFE("Kernel : Started\n--------------------------------------------------\n\n");
482
483        enable_interrupts( DEBUG_CTX );
484}
485
486void kernel_shutdown(void) {
487        LIB_DEBUG_PRINT_SAFE("\n--------------------------------------------------\nKernel : Shutting down\n");
488
489        disable_interrupts();
490
491        // SKULLDUGGERY: Notify the systemProcessor it needs to terminates.
492        // When its coroutine terminates, it return control to the mainThread
493        // which is currently here
494        systemProcessor->proc.is_terminated = true;
495        suspend();
496
497        // THE SYSTEM IS NOW COMPLETELY STOPPED
498
499        // Disable preemption
500        kernel_stop_preemption();
501
502        // Destroy the system processor and its context in reverse order of construction
503        // These were manually constructed so we need manually destroy them
504        ^(systemProcessor->proc.runner){};
505        ^(systemProcessor){};
506
507        // Final step, destroy the main thread since it is no longer needed
508        // Since we provided a stack to this taxk it will not destroy anything
509        ^(mainThread){};
510
511        LIB_DEBUG_PRINT_SAFE("Kernel : Shutdown complete\n");
512}
513
514static spinlock kernel_abort_lock;
515static spinlock kernel_debug_lock;
516static bool kernel_abort_called = false;
517
518void * kernel_abort    (void) __attribute__ ((__nothrow__)) {
519        // abort cannot be recursively entered by the same or different processors because all signal handlers return when
520        // the globalAbort flag is true.
521        lock( &kernel_abort_lock DEBUG_CTX2 );
522
523        // first task to abort ?
524        if ( !kernel_abort_called ) {                   // not first task to abort ?
525                kernel_abort_called = true;
526                unlock( &kernel_abort_lock );
527        }
528        else {
529                unlock( &kernel_abort_lock );
530
531                sigset_t mask;
532                sigemptyset( &mask );
533                sigaddset( &mask, SIGALRM );                    // block SIGALRM signals
534                sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
535                sigsuspend( &mask );                            // block the processor to prevent further damage during abort
536                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it
537        }
538
539        return this_thread;
540}
541
542void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
543        thread_desc * thrd = kernel_data;
544
545        int len = snprintf( abort_text, abort_text_size, "Error occurred while executing task %.256s (%p)", thrd->cor.name, thrd );
546        __lib_debug_write( STDERR_FILENO, abort_text, len );
547
548        if ( thrd != this_coroutine ) {
549                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine->name, this_coroutine );
550                __lib_debug_write( STDERR_FILENO, abort_text, len );
551        }
552        else {
553                __lib_debug_write( STDERR_FILENO, ".\n", 2 );
554        }
555}
556
557extern "C" {
558        void __lib_debug_acquire() {
559                lock( &kernel_debug_lock DEBUG_CTX2 );
560        }
561
562        void __lib_debug_release() {
563                unlock( &kernel_debug_lock );
564        }
565}
566
567//=============================================================================================
568// Kernel Utilities
569//=============================================================================================
570//-----------------------------------------------------------------------------
571// Locks
572void ?{}( spinlock * this ) {
573        this->lock = 0;
574}
575void ^?{}( spinlock * this ) {
576
577}
578
579bool try_lock( spinlock * this DEBUG_CTX_PARAM2 ) {
580        return this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0;
581}
582
583void lock( spinlock * this DEBUG_CTX_PARAM2 ) {
584        for ( unsigned int i = 1;; i += 1 ) {
585                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
586        }
587        LIB_DEBUG_DO(
588                this->prev_name = caller;
589                this->prev_thrd = this_thread;
590        )
591}
592
593void lock_yield( spinlock * this DEBUG_CTX_PARAM2 ) {
594        for ( unsigned int i = 1;; i += 1 ) {
595                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
596                yield();
597        }
598        LIB_DEBUG_DO(
599                this->prev_name = caller;
600                this->prev_thrd = this_thread;
601        )
602}
603
604
605void unlock( spinlock * this ) {
606        __sync_lock_release_4( &this->lock );
607}
608
609void ?{}( signal_once * this ) {
610        this->cond = false;
611}
612void ^?{}( signal_once * this ) {
613
614}
615
616void wait( signal_once * this ) {
617        lock( &this->lock DEBUG_CTX2 );
618        if( !this->cond ) {
619                append( &this->blocked, (thread_desc*)this_thread );
620                BlockInternal( &this->lock );
621        }
622        else {
623                unlock( &this->lock );
624        }
625}
626
627void signal( signal_once * this ) {
628        lock( &this->lock DEBUG_CTX2 );
629        {
630                this->cond = true;
631
632                disable_interrupts();
633                thread_desc * it;
634                while( it = pop_head( &this->blocked) ) {
635                        ScheduleThread( it );
636                }
637                enable_interrupts( DEBUG_CTX );
638        }
639        unlock( &this->lock );
640}
641
642//-----------------------------------------------------------------------------
643// Queues
644void ?{}( __thread_queue_t * this ) {
645        this->head = NULL;
646        this->tail = &this->head;
647}
648
649void append( __thread_queue_t * this, thread_desc * t ) {
650        verify(this->tail != NULL);
651        *this->tail = t;
652        this->tail = &t->next;
653}
654
655thread_desc * pop_head( __thread_queue_t * this ) {
656        thread_desc * head = this->head;
657        if( head ) {
658                this->head = head->next;
659                if( !head->next ) {
660                        this->tail = &this->head;
661                }
662                head->next = NULL;
663        }
664        return head;
665}
666
667void ?{}( __condition_stack_t * this ) {
668        this->top = NULL;
669}
670
671void push( __condition_stack_t * this, __condition_criterion_t * t ) {
672        verify( !t->next );
673        t->next = this->top;
674        this->top = t;
675}
676
677__condition_criterion_t * pop( __condition_stack_t * this ) {
678        __condition_criterion_t * top = this->top;
679        if( top ) {
680                this->top = top->next;
681                top->next = NULL;
682        }
683        return top;
684}
685// Local Variables: //
686// mode: c //
687// tab-width: 4 //
688// End: //
Note: See TracBrowser for help on using the repository browser.