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

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

Preemption is now stable enough to push, some clean-up needed

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