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

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

Merge branch 'master' into references

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