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

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since eaace25 was eaace25, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

  • Property mode set to 100644
File size: 19.1 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){ 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
434//=============================================================================================
435// Kernel Setup logic
436//=============================================================================================
437//-----------------------------------------------------------------------------
438// Kernel boot procedures
439void kernel_startup(void) {
440        LIB_DEBUG_PRINT_SAFE("Kernel : Starting\n");
441
442        // Start by initializing the main thread
443        // SKULLDUGGERY: the mainThread steals the process main thread
444        // which will then be scheduled by the systemProcessor normally
445        mainThread = (thread_desc *)&mainThread_storage;
446        current_stack_info_t info;
447        mainThread{ &info };
448
449        LIB_DEBUG_PRINT_SAFE("Kernel : Main thread ready\n");
450
451        // Initialize the system cluster
452        systemCluster = (cluster *)&systemCluster_storage;
453        systemCluster{};
454
455        LIB_DEBUG_PRINT_SAFE("Kernel : System cluster ready\n");
456
457        // Initialize the system processor and the system processor ctx
458        // (the coroutine that contains the processing control flow)
459        systemProcessor = (system_proc_t *)&systemProcessor_storage;
460        systemProcessor{ systemCluster, (processorCtx_t *)&systemProcessorCtx_storage };
461
462        // Add the main thread to the ready queue
463        // once resume is called on systemProcessor->runner the mainThread needs to be scheduled like any normal thread
464        ScheduleThread(mainThread);
465
466        //initialize the global state variables
467        this_processor = &systemProcessor->proc;
468        this_thread = mainThread;
469        this_coroutine = &mainThread->cor;
470        disable_preempt_count = 1;
471
472        // Enable preemption
473        kernel_start_preemption();
474
475        // SKULLDUGGERY: Force a context switch to the system processor to set the main thread's context to the current UNIX
476        // context. Hence, the main thread does not begin through CtxInvokeThread, like all other threads. The trick here is that
477        // mainThread is on the ready queue when this call is made.
478        resume( systemProcessor->proc.runner );
479
480
481
482        // THE SYSTEM IS NOW COMPLETELY RUNNING
483        LIB_DEBUG_PRINT_SAFE("Kernel : Started\n--------------------------------------------------\n\n");
484
485        enable_interrupts( DEBUG_CTX );
486}
487
488void kernel_shutdown(void) {
489        LIB_DEBUG_PRINT_SAFE("\n--------------------------------------------------\nKernel : Shutting down\n");
490
491        disable_interrupts();
492
493        // SKULLDUGGERY: Notify the systemProcessor it needs to terminates.
494        // When its coroutine terminates, it return control to the mainThread
495        // which is currently here
496        systemProcessor->proc.is_terminated = true;
497        suspend();
498
499        // THE SYSTEM IS NOW COMPLETELY STOPPED
500
501        // Disable preemption
502        kernel_stop_preemption();
503
504        // Destroy the system processor and its context in reverse order of construction
505        // These were manually constructed so we need manually destroy them
506        ^(systemProcessor->proc.runner){};
507        ^(systemProcessor){};
508
509        // Final step, destroy the main thread since it is no longer needed
510        // Since we provided a stack to this taxk it will not destroy anything
511        ^(mainThread){};
512
513        LIB_DEBUG_PRINT_SAFE("Kernel : Shutdown complete\n");
514}
515
516static spinlock kernel_abort_lock;
517static spinlock kernel_debug_lock;
518static bool kernel_abort_called = false;
519
520void * kernel_abort    (void) __attribute__ ((__nothrow__)) {
521        // abort cannot be recursively entered by the same or different processors because all signal handlers return when
522        // the globalAbort flag is true.
523        lock( &kernel_abort_lock DEBUG_CTX2 );
524
525        // first task to abort ?
526        if ( !kernel_abort_called ) {                   // not first task to abort ?
527                kernel_abort_called = true;
528                unlock( &kernel_abort_lock );
529        }
530        else {
531                unlock( &kernel_abort_lock );
532
533                sigset_t mask;
534                sigemptyset( &mask );
535                sigaddset( &mask, SIGALRM );                    // block SIGALRM signals
536                sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
537                sigsuspend( &mask );                            // block the processor to prevent further damage during abort
538                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it
539        }
540
541        return this_thread;
542}
543
544void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
545        thread_desc * thrd = kernel_data;
546
547        int len = snprintf( abort_text, abort_text_size, "Error occurred while executing task %.256s (%p)", thrd->cor.name, thrd );
548        __lib_debug_write( STDERR_FILENO, abort_text, len );
549
550        if ( thrd != this_coroutine ) {
551                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine->name, this_coroutine );
552                __lib_debug_write( STDERR_FILENO, abort_text, len );
553        }
554        else {
555                __lib_debug_write( STDERR_FILENO, ".\n", 2 );
556        }
557}
558
559extern "C" {
560        void __lib_debug_acquire() {
561                lock( &kernel_debug_lock DEBUG_CTX2 );
562        }
563
564        void __lib_debug_release() {
565                unlock( &kernel_debug_lock );
566        }
567}
568
569//=============================================================================================
570// Kernel Utilities
571//=============================================================================================
572//-----------------------------------------------------------------------------
573// Locks
574void ?{}( spinlock * this ) {
575        this->lock = 0;
576}
577void ^?{}( spinlock * this ) {
578
579}
580
581bool try_lock( spinlock * this DEBUG_CTX_PARAM2 ) {
582        return this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0;
583}
584
585void lock( spinlock * this DEBUG_CTX_PARAM2 ) {
586        for ( unsigned int i = 1;; i += 1 ) {
587                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
588        }
589        LIB_DEBUG_DO(
590                this->prev_name = caller;
591                this->prev_thrd = this_thread;
592        )
593}
594
595void lock_yield( spinlock * this DEBUG_CTX_PARAM2 ) {
596        for ( unsigned int i = 1;; i += 1 ) {
597                if ( this->lock == 0 && __sync_lock_test_and_set_4( &this->lock, 1 ) == 0 ) { break; }
598                yield();
599        }
600        LIB_DEBUG_DO(
601                this->prev_name = caller;
602                this->prev_thrd = this_thread;
603        )
604}
605
606
607void unlock( spinlock * this ) {
608        __sync_lock_release_4( &this->lock );
609}
610
611void  ?{}( semaphore * this, int count = 1 ) {
612        (&this->lock){};
613        this->count = count;
614        (&this->waiting){};
615}
616void ^?{}(semaphore * this) {}
617
618void P(semaphore * this) {
619        lock( &this->lock DEBUG_CTX2 );
620        this->count -= 1;
621        if ( this->count < 0 ) {
622                // queue current task
623                append( &this->waiting, (thread_desc *)this_thread );
624
625                // atomically release spin lock and block
626                BlockInternal( &this->lock );
627        }
628        else {
629            unlock( &this->lock );
630        }
631}
632
633void V(semaphore * this) {
634        thread_desc * thrd = NULL;
635        lock( &this->lock DEBUG_CTX2 );
636        this->count += 1;
637        if ( this->count <= 0 ) {
638                // remove task at head of waiting list
639                thrd = pop_head( &this->waiting );
640        }
641
642        unlock( &this->lock );
643
644        // make new owner
645        WakeThread( thrd );
646}
647
648//-----------------------------------------------------------------------------
649// Queues
650void ?{}( __thread_queue_t * this ) {
651        this->head = NULL;
652        this->tail = &this->head;
653}
654
655void append( __thread_queue_t * this, thread_desc * t ) {
656        verify(this->tail != NULL);
657        *this->tail = t;
658        this->tail = &t->next;
659}
660
661thread_desc * pop_head( __thread_queue_t * this ) {
662        thread_desc * head = this->head;
663        if( head ) {
664                this->head = head->next;
665                if( !head->next ) {
666                        this->tail = &this->head;
667                }
668                head->next = NULL;
669        }
670        return head;
671}
672
673void ?{}( __condition_stack_t * this ) {
674        this->top = NULL;
675}
676
677void push( __condition_stack_t * this, __condition_criterion_t * t ) {
678        verify( !t->next );
679        t->next = this->top;
680        this->top = t;
681}
682
683__condition_criterion_t * pop( __condition_stack_t * this ) {
684        __condition_criterion_t * top = this->top;
685        if( top ) {
686                this->top = top->next;
687                top->next = NULL;
688        }
689        return top;
690}
691// Local Variables: //
692// mode: c //
693// tab-width: 4 //
694// End: //
Note: See TracBrowser for help on using the repository browser.