source: src/libcfa/concurrency/kernel.c @ 320eb73a

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 320eb73a was 2e9aed4, checked in by Thierry Delisle <tdelisle@…>, 6 years ago

Fixed non-preemptive locks

  • Property mode set to 100644
File size: 18.8 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 Dec  8 16:23:33 2017
13// Update Count     : 3
14//
15
16//C Includes
17#include <stddef.h>
18#define ftype `ftype`
19extern "C" {
20#include <stdio.h>
21#include <fenv.h>
22#include <sys/resource.h>
23#include <signal.h>
24#include <unistd.h>
25}
26#undef ftype
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        this.starter = NULL;
105}
106
107void ?{}( thread_desc & this, current_stack_info_t * info) {
108        (this.self_cor){ info };
109}
110
111//-----------------------------------------------------------------------------
112// Processor coroutine
113
114// Construct the processor context of the main processor
115void ?{}(processorCtx_t & this, processor * proc) {
116        (this.__cor){ "Processor" };
117        this.__cor.starter = NULL;
118        this.proc = proc;
119        proc->runner = &this;
120}
121
122// Construct the processor context of non-main processors
123void ?{}(processorCtx_t & this, processor * proc, current_stack_info_t * info) {
124        (this.__cor){ info };
125        this.proc = proc;
126        proc->runner = &this;
127}
128
129void ?{}(processor & this) {
130        this{ mainCluster };
131}
132
133void ?{}(processor & this, cluster * cltr) {
134        this.cltr = cltr;
135        (this.terminated){ 0 };
136        this.do_terminate = false;
137        this.preemption_alarm = NULL;
138        this.pending_preemption = false;
139
140        start( &this );
141}
142
143void ?{}(processor & this, cluster * cltr, processorCtx_t & runner) {
144        this.cltr = cltr;
145        (this.terminated){ 0 };
146        this.do_terminate = false;
147        this.preemption_alarm = NULL;
148        this.pending_preemption = false;
149        this.kernel_thread = pthread_self();
150
151        this.runner = &runner;
152        __cfaabi_dbg_print_safe("Kernel : constructing main processor context %p\n", &runner);
153        runner{ &this };
154}
155
156void ^?{}(processor & this) {
157        if( ! this.do_terminate ) {
158                __cfaabi_dbg_print_safe("Kernel : core %p signaling termination\n", &this);
159                this.do_terminate = true;
160                P( this.terminated );
161                pthread_join( this.kernel_thread, NULL );
162        }
163}
164
165void ?{}(cluster & this) {
166        (this.ready_queue){};
167        ( this.ready_queue_lock ){};
168
169        this.preemption = default_preemption();
170}
171
172void ^?{}(cluster & this) {
173
174}
175
176//=============================================================================================
177// Kernel Scheduling logic
178//=============================================================================================
179//Main of the processor contexts
180void main(processorCtx_t & runner) {
181        processor * this = runner.proc;
182
183        __cfaabi_dbg_print_safe("Kernel : core %p starting\n", this);
184
185        {
186                // Setup preemption data
187                preemption_scope scope = { this };
188
189                __cfaabi_dbg_print_safe("Kernel : core %p started\n", this);
190
191                thread_desc * readyThread = NULL;
192                for( unsigned int spin_count = 0; ! this->do_terminate; spin_count++ )
193                {
194                        readyThread = nextThread( this->cltr );
195
196                        if(readyThread)
197                        {
198                                verify( disable_preempt_count > 0 );
199
200                                runThread(this, readyThread);
201
202                                verify( disable_preempt_count > 0 );
203
204                                //Some actions need to be taken from the kernel
205                                finishRunning(this);
206
207                                spin_count = 0;
208                        }
209                        else
210                        {
211                                spin(this, &spin_count);
212                        }
213                }
214
215                __cfaabi_dbg_print_safe("Kernel : core %p stopping\n", this);
216        }
217
218        V( this->terminated );
219
220        __cfaabi_dbg_print_safe("Kernel : core %p terminated\n", this);
221}
222
223// runThread runs a thread by context switching
224// from the processor coroutine to the target thread
225void runThread(processor * this, thread_desc * dst) {
226        coroutine_desc * proc_cor = get_coroutine(*this->runner);
227        coroutine_desc * thrd_cor = get_coroutine(dst);
228
229        //Reset the terminating actions here
230        this->finish.action_code = No_Action;
231
232        //Update global state
233        this_thread = dst;
234
235        // Context Switch to the thread
236        ThreadCtxSwitch(proc_cor, thrd_cor);
237        // when ThreadCtxSwitch returns we are back in the processor coroutine
238}
239
240// Once a thread has finished running, some of
241// its final actions must be executed from the kernel
242void finishRunning(processor * this) {
243        if( this->finish.action_code == Release ) {
244                verify( disable_preempt_count > 1 );
245                unlock( *this->finish.lock );
246        }
247        else if( this->finish.action_code == Schedule ) {
248                ScheduleThread( this->finish.thrd );
249        }
250        else if( this->finish.action_code == Release_Schedule ) {
251                verify( disable_preempt_count > 1 );
252                unlock( *this->finish.lock );
253                ScheduleThread( this->finish.thrd );
254        }
255        else if( this->finish.action_code == Release_Multi ) {
256                verify( disable_preempt_count > this->finish.lock_count );
257                for(int i = 0; i < this->finish.lock_count; i++) {
258                        unlock( *this->finish.locks[i] );
259                }
260        }
261        else if( this->finish.action_code == Release_Multi_Schedule ) {
262                verify( disable_preempt_count > this->finish.lock_count );
263                for(int i = 0; i < this->finish.lock_count; i++) {
264                        unlock( *this->finish.locks[i] );
265                }
266                for(int i = 0; i < this->finish.thrd_count; i++) {
267                        ScheduleThread( this->finish.thrds[i] );
268                }
269        }
270        else {
271                assert(this->finish.action_code == No_Action);
272        }
273}
274
275// Handles spinning logic
276// TODO : find some strategy to put cores to sleep after some time
277void spin(processor * this, unsigned int * spin_count) {
278        (*spin_count)++;
279}
280
281// Context invoker for processors
282// This is the entry point for processors (kernel threads)
283// It effectively constructs a coroutine by stealing the pthread stack
284void * CtxInvokeProcessor(void * arg) {
285        processor * proc = (processor *) arg;
286        this_processor = proc;
287        this_coroutine = NULL;
288        this_thread = NULL;
289        disable_preempt_count = 1;
290        // SKULLDUGGERY: We want to create a context for the processor coroutine
291        // which is needed for the 2-step context switch. However, there is no reason
292        // to waste the perfectly valid stack create by pthread.
293        current_stack_info_t info;
294        machine_context_t ctx;
295        info.context = &ctx;
296        processorCtx_t proc_cor_storage = { proc, &info };
297
298        __cfaabi_dbg_print_safe("Coroutine : created stack %p\n", proc_cor_storage.__cor.stack.base);
299
300        //Set global state
301        this_coroutine = &proc->runner->__cor;
302        this_thread = NULL;
303
304        //We now have a proper context from which to schedule threads
305        __cfaabi_dbg_print_safe("Kernel : core %p created (%p, %p)\n", proc, proc->runner, &ctx);
306
307        // SKULLDUGGERY: Since the coroutine doesn't have its own stack, we can't
308        // resume it to start it like it normally would, it will just context switch
309        // back to here. Instead directly call the main since we already are on the
310        // appropriate stack.
311        proc_cor_storage.__cor.state = Active;
312        main( proc_cor_storage );
313        proc_cor_storage.__cor.state = Halted;
314
315        // Main routine of the core returned, the core is now fully terminated
316        __cfaabi_dbg_print_safe("Kernel : core %p main ended (%p)\n", proc, proc->runner);
317
318        return NULL;
319}
320
321void start(processor * this) {
322        __cfaabi_dbg_print_safe("Kernel : Starting core %p\n", this);
323
324        pthread_create( &this->kernel_thread, NULL, CtxInvokeProcessor, (void*)this );
325
326        __cfaabi_dbg_print_safe("Kernel : core %p started\n", this);
327}
328
329//-----------------------------------------------------------------------------
330// Scheduler routines
331void ScheduleThread( thread_desc * thrd ) {
332        // if( !thrd ) return;
333        verify( thrd );
334        verify( thrd->self_cor.state != Halted );
335
336        verify( disable_preempt_count > 0 );
337
338        verifyf( thrd->next == NULL, "Expected null got %p", thrd->next );
339
340        lock(   this_processor->cltr->ready_queue_lock __cfaabi_dbg_ctx2 );
341        append( this_processor->cltr->ready_queue, thrd );
342        unlock( this_processor->cltr->ready_queue_lock );
343
344        verify( disable_preempt_count > 0 );
345}
346
347thread_desc * nextThread(cluster * this) {
348        verify( disable_preempt_count > 0 );
349        lock( this->ready_queue_lock __cfaabi_dbg_ctx2 );
350        thread_desc * head = pop_head( this->ready_queue );
351        unlock( this->ready_queue_lock );
352        verify( disable_preempt_count > 0 );
353        return head;
354}
355
356void BlockInternal() {
357        disable_interrupts();
358        verify( disable_preempt_count > 0 );
359        suspend();
360        verify( disable_preempt_count > 0 );
361        enable_interrupts( __cfaabi_dbg_ctx );
362}
363
364void BlockInternal( __spinlock_t * lock ) {
365        disable_interrupts();
366        this_processor->finish.action_code = Release;
367        this_processor->finish.lock = lock;
368
369        verify( disable_preempt_count > 1 );
370        suspend();
371        verify( disable_preempt_count > 0 );
372
373        enable_interrupts( __cfaabi_dbg_ctx );
374}
375
376void BlockInternal( thread_desc * thrd ) {
377        assert(thrd);
378        disable_interrupts();
379        assert( thrd->self_cor.state != Halted );
380        this_processor->finish.action_code = Schedule;
381        this_processor->finish.thrd = thrd;
382
383        verify( disable_preempt_count > 0 );
384        suspend();
385        verify( disable_preempt_count > 0 );
386
387        enable_interrupts( __cfaabi_dbg_ctx );
388}
389
390void BlockInternal( __spinlock_t * lock, thread_desc * thrd ) {
391        assert(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 > 1 );
398        suspend();
399        verify( disable_preempt_count > 0 );
400
401        enable_interrupts( __cfaabi_dbg_ctx );
402}
403
404void BlockInternal(__spinlock_t * 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( __cfaabi_dbg_ctx );
415}
416
417void BlockInternal(__spinlock_t * 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( __cfaabi_dbg_ctx );
430}
431
432void LeaveThread(__spinlock_t * lock, thread_desc * thrd) {
433        verify( disable_preempt_count > 0 );
434        this_processor->finish.action_code = thrd ? Release_Schedule : Release;
435        this_processor->finish.lock = lock;
436        this_processor->finish.thrd = thrd;
437
438        suspend();
439}
440
441//=============================================================================================
442// Kernel Setup logic
443//=============================================================================================
444//-----------------------------------------------------------------------------
445// Kernel boot procedures
446void kernel_startup(void) {
447        __cfaabi_dbg_print_safe("Kernel : Starting\n");
448
449        // Start by initializing the main thread
450        // SKULLDUGGERY: the mainThread steals the process main thread
451        // which will then be scheduled by the mainProcessor normally
452        mainThread = (thread_desc *)&storage_mainThread;
453        current_stack_info_t info;
454        (*mainThread){ &info };
455
456        __cfaabi_dbg_print_safe("Kernel : Main thread ready\n");
457
458        // Initialize the main cluster
459        mainCluster = (cluster *)&storage_mainCluster;
460        (*mainCluster){};
461
462        __cfaabi_dbg_print_safe("Kernel : main cluster ready\n");
463
464        // Initialize the main processor and the main processor ctx
465        // (the coroutine that contains the processing control flow)
466        mainProcessor = (processor *)&storage_mainProcessor;
467        (*mainProcessor){ mainCluster, *(processorCtx_t *)&storage_mainProcessorCtx };
468
469        //initialize the global state variables
470        this_processor = mainProcessor;
471        this_thread = mainThread;
472        this_coroutine = &mainThread->self_cor;
473
474        // Enable preemption
475        kernel_start_preemption();
476
477        // Add the main thread to the ready queue
478        // once resume is called on mainProcessor->runner the mainThread needs to be scheduled like any normal thread
479        ScheduleThread(mainThread);
480
481        // SKULLDUGGERY: Force a context switch to the main processor to set the main thread's context to the current UNIX
482        // context. Hence, the main thread does not begin through CtxInvokeThread, like all other threads. The trick here is that
483        // mainThread is on the ready queue when this call is made.
484        resume( *mainProcessor->runner );
485
486
487
488        // THE SYSTEM IS NOW COMPLETELY RUNNING
489        __cfaabi_dbg_print_safe("Kernel : Started\n--------------------------------------------------\n\n");
490
491        enable_interrupts( __cfaabi_dbg_ctx );
492}
493
494void kernel_shutdown(void) {
495        __cfaabi_dbg_print_safe("\n--------------------------------------------------\nKernel : Shutting down\n");
496
497        disable_interrupts();
498
499        // SKULLDUGGERY: Notify the mainProcessor it needs to terminates.
500        // When its coroutine terminates, it return control to the mainThread
501        // which is currently here
502        mainProcessor->do_terminate = true;
503        suspend();
504
505        // THE SYSTEM IS NOW COMPLETELY STOPPED
506
507        // Disable preemption
508        kernel_stop_preemption();
509
510        // Destroy the main processor and its context in reverse order of construction
511        // These were manually constructed so we need manually destroy them
512        ^(*mainProcessor->runner){};
513        ^(mainProcessor){};
514
515        // Final step, destroy the main thread since it is no longer needed
516        // Since we provided a stack to this taxk it will not destroy anything
517        ^(mainThread){};
518
519        __cfaabi_dbg_print_safe("Kernel : Shutdown complete\n");
520}
521
522//=============================================================================================
523// Unexpected Terminating logic
524//=============================================================================================
525
526
527static __spinlock_t kernel_abort_lock;
528static __spinlock_t kernel_debug_lock;
529static bool kernel_abort_called = false;
530
531void * kernel_abort    (void) __attribute__ ((__nothrow__)) {
532        // abort cannot be recursively entered by the same or different processors because all signal handlers return when
533        // the globalAbort flag is true.
534        lock( kernel_abort_lock __cfaabi_dbg_ctx2 );
535
536        // first task to abort ?
537        if ( !kernel_abort_called ) {                   // not first task to abort ?
538                kernel_abort_called = true;
539                unlock( kernel_abort_lock );
540        }
541        else {
542                unlock( kernel_abort_lock );
543
544                sigset_t mask;
545                sigemptyset( &mask );
546                sigaddset( &mask, SIGALRM );                    // block SIGALRM signals
547                sigaddset( &mask, SIGUSR1 );                    // block SIGUSR1 signals
548                sigsuspend( &mask );                            // block the processor to prevent further damage during abort
549                _exit( EXIT_FAILURE );                          // if processor unblocks before it is killed, terminate it
550        }
551
552        return this_thread;
553}
554
555void kernel_abort_msg( void * kernel_data, char * abort_text, int abort_text_size ) {
556        thread_desc * thrd = kernel_data;
557
558        int len = snprintf( abort_text, abort_text_size, "Error occurred while executing task %.256s (%p)", thrd->self_cor.name, thrd );
559        __cfaabi_dbg_bits_write( abort_text, len );
560
561        if ( thrd != this_coroutine ) {
562                len = snprintf( abort_text, abort_text_size, " in coroutine %.256s (%p).\n", this_coroutine->name, this_coroutine );
563                __cfaabi_dbg_bits_write( abort_text, len );
564        }
565        else {
566                __cfaabi_dbg_bits_write( ".\n", 2 );
567        }
568}
569
570extern "C" {
571        void __cfaabi_dbg_bits_acquire() {
572                lock( kernel_debug_lock __cfaabi_dbg_ctx2 );
573        }
574
575        void __cfaabi_dbg_bits_release() {
576                unlock( kernel_debug_lock );
577        }
578}
579
580//=============================================================================================
581// Kernel Utilities
582//=============================================================================================
583//-----------------------------------------------------------------------------
584// Locks
585void  ?{}( semaphore & this, int count = 1 ) {
586        (this.lock){};
587        this.count = count;
588        (this.waiting){};
589}
590void ^?{}(semaphore & this) {}
591
592void P(semaphore & this) {
593        lock( this.lock __cfaabi_dbg_ctx2 );
594        this.count -= 1;
595        if ( this.count < 0 ) {
596                // queue current task
597                append( this.waiting, (thread_desc *)this_thread );
598
599                // atomically release spin lock and block
600                BlockInternal( &this.lock );
601        }
602        else {
603            unlock( this.lock );
604        }
605}
606
607void V(semaphore & this) {
608        thread_desc * thrd = NULL;
609        lock( this.lock __cfaabi_dbg_ctx2 );
610        this.count += 1;
611        if ( this.count <= 0 ) {
612                // remove task at head of waiting list
613                thrd = pop_head( this.waiting );
614        }
615
616        unlock( this.lock );
617
618        // make new owner
619        WakeThread( thrd );
620}
621
622//-----------------------------------------------------------------------------
623// Debug
624__cfaabi_dbg_debug_do(
625        struct {
626                thread_desc * tail;
627        } __cfaabi_dbg_thread_list = { NULL };
628
629        void __cfaabi_dbg_thread_register( thread_desc * thrd ) {
630                if( !__cfaabi_dbg_thread_list.tail ) {
631                        __cfaabi_dbg_thread_list.tail = thrd;
632                        return;
633                }
634                __cfaabi_dbg_thread_list.tail->dbg_next = thrd;
635                thrd->dbg_prev = __cfaabi_dbg_thread_list.tail;
636                __cfaabi_dbg_thread_list.tail = thrd;
637        }
638
639        void __cfaabi_dbg_thread_unregister( thread_desc * thrd ) {
640                thread_desc * prev = thrd->dbg_prev;
641                thread_desc * next = thrd->dbg_next;
642
643                if( next ) { next->dbg_prev = prev; }
644                else       {
645                        assert( __cfaabi_dbg_thread_list.tail == thrd );
646                        __cfaabi_dbg_thread_list.tail = prev;
647                }
648
649                if( prev ) { prev->dbg_next = next; }
650
651                thrd->dbg_prev = NULL;
652                thrd->dbg_next = NULL;
653        }
654)
655// Local Variables: //
656// mode: c //
657// tab-width: 4 //
658// End: //
Note: See TracBrowser for help on using the repository browser.