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

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since d6ff3ff was d6ff3ff, checked in by Thierry Delisle <tdelisle@…>, 8 years ago

Kernel shoud now drop preemptions during other preemptions

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