source: trunk/kernel/kern/scheduler.c @ 564

Last change on this file since 564 was 564, checked in by alain, 3 years ago

Complete restructuration of kernel locks.

File size: 22.6 KB
Line 
1/*
2 * scheduler.c - Core scheduler implementation.
3 *
4 * Author    Alain Greiner (2016,2017,2018)
5 *
6 * Copyright (c)  UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH. is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH. is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH.; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <kernel_config.h>
25#include <hal_kernel_types.h>
26#include <hal_switch.h>
27#include <hal_irqmask.h>
28#include <hal_context.h>
29#include <printk.h>
30#include <list.h>
31#include <core.h>
32#include <thread.h>
33#include <chdev.h>
34#include <scheduler.h>
35
36
37///////////////////////////////////////////////////////////////////////////////////////////
38//         global variables
39///////////////////////////////////////////////////////////////////////////////////////////
40
41extern chdev_directory_t    chdev_dir;          // allocated in kernel_init.c
42
43///////////////////////////////////////////////////////////////////////////////////////////
44//         private functions
45///////////////////////////////////////////////////////////////////////////////////////////
46
47
48////////////////////////////////////////////////////////////////////////////////////////////
49// This static function does NOT modify the scheduler state.
50// It just select a thread in the list of attached threads, implementing the following
51// three steps policy:
52// 1) It scan the list of kernel threads, from the next thread after the last executed one,
53//    and returns the first runnable found : not IDLE, not blocked, client queue not empty.
54//    It can be the current thread.
55// 2) If no kernel thread found, it scan the list of user thread, from the next thread after
56//    the last executed one, and returns the first runable found : not blocked.
57//    It can be the current thread.
58// 3) If no runable thread found, it returns the idle thread.
59////////////////////////////////////////////////////////////////////////////////////////////
60// @ sched   : local pointer on scheduler.
61// @ returns pointer on selected thread descriptor
62////////////////////////////////////////////////////////////////////////////////////////////
63thread_t * sched_select( scheduler_t * sched )
64{
65    thread_t     * thread;
66    list_entry_t * current;
67    list_entry_t * last;
68    list_entry_t * root;
69    bool_t         done;
70    uint32_t       count;
71
72    // first : scan the kernel threads list if not empty
73    if( list_is_empty( &sched->k_root ) == false )
74    {
75        root    = &sched->k_root;
76        last    = sched->k_last;
77        done    = false;
78        count   = 0;
79        current = last;
80
81        while( done == false )
82        {
83
84// check kernel threads list
85assert( (count < sched->k_threads_nr),
86"bad kernel threads list" );
87
88            // get next entry in kernel list
89            current = current->next;
90
91            // check exit condition
92            if( current == last ) done = true;
93
94            // skip the root that does not contain a thread
95            if( current == root ) continue;
96            else                  count++;
97
98            // get thread pointer for this entry
99            thread = LIST_ELEMENT( current , thread_t , sched_list );
100
101            // select kernel thread if non blocked and non THREAD_IDLE
102            if( (thread->blocked == 0)  && (thread->type != THREAD_IDLE) ) return thread;
103
104        } // end loop on kernel threads
105    } // end kernel threads
106
107    // second : scan the user threads list if not empty
108    if( list_is_empty( &sched->u_root ) == false )
109    {
110        root    = &sched->u_root;
111        last    = sched->u_last;
112        done    = false;
113        count   = 0;
114        current = last;
115
116        while( done == false )
117        {
118
119// check user threads list
120assert( (count < sched->u_threads_nr),
121"bad user threads list" );
122
123            // get next entry in user list
124            current = current->next;
125
126            // check exit condition
127            if( current == last ) done = true;
128
129            // skip the root that does not contain a thread
130            if( current == root ) continue;
131            else                  count++;
132
133            // get thread pointer for this entry
134            thread = LIST_ELEMENT( current , thread_t , sched_list );
135
136            // select thread if non blocked
137            if( thread->blocked == 0 )  return thread;
138
139        } // end loop on user threads
140    } // end user threads
141
142    // third : return idle thread if no other runnable thread
143    return sched->idle;
144
145}  // end sched_select()
146
147////////////////////////////////////////////////////////////////////////////////////////////
148// This static function is the only function that can remove a thread from the scheduler.
149// It is private, because it is called by the sched_yield() public function.
150// It scan all threads attached to a given scheduler, and executes the relevant
151// actions for pending requests:
152// - REQ_ACK : it checks that target thread is blocked, decrements the response counter
153//   to acknowledge the client thread, and reset the pending request.
154// - REQ_DELETE : it detach the target thread from parent if attached, detach it from
155//   the process, remove it from scheduler, release memory allocated to thread descriptor,
156//   and destroy the process descriptor it the target thread was the last thread.
157////////////////////////////////////////////////////////////////////////////////////////////
158// @ core    : local pointer on the core descriptor.
159////////////////////////////////////////////////////////////////////////////////////////////
160static void sched_handle_signals( core_t * core )
161{
162
163    list_entry_t * iter;
164    list_entry_t * root;
165    thread_t     * thread;
166    process_t    * process;
167    scheduler_t  * sched;
168    bool_t         last;
169
170    // get pointer on scheduler
171    sched = &core->scheduler;
172
173    // get pointer on user threads root
174    root = &sched->u_root;
175
176    // We use a while to scan the user threads, to control the iterator increment,
177    // because some threads will be destroyed, and we want not use a LIST_FOREACH()
178
179    // initialise list iterator
180    iter = root->next;
181
182    // scan all user threads
183    while( iter != root )
184    {
185        // get pointer on thread
186        thread = LIST_ELEMENT( iter , thread_t , sched_list );
187
188        // increment iterator
189        iter = iter->next;
190
191        // handle REQ_ACK
192        if( thread->flags & THREAD_FLAG_REQ_ACK )
193        {
194
195// check thread blocked
196assert( (thread->blocked & THREAD_BLOCKED_GLOBAL) , 
197"thread not blocked" );
198 
199            // decrement response counter
200            hal_atomic_add( thread->ack_rsp_count , -1 );
201
202            // reset REQ_ACK in thread descriptor
203            thread_reset_req_ack( thread );
204        }
205
206        // handle REQ_DELETE only if target thread != calling thread
207        if( (thread->flags & THREAD_FLAG_REQ_DELETE) && (thread != CURRENT_THREAD) )
208        {
209            // get thread process descriptor
210            process = thread->process;
211
212                // release FPU if required
213                if( thread->core->fpu_owner == thread )  thread->core->fpu_owner = NULL;
214
215            // take lock protecting sheduler state
216            busylock_acquire( &sched->lock );
217
218            // update scheduler state
219            uint32_t threads_nr = sched->u_threads_nr;
220            sched->u_threads_nr = threads_nr - 1;
221            list_unlink( &thread->sched_list );
222            if( sched->u_last == &thread->sched_list )
223            {
224                if( threads_nr == 1 ) 
225                {
226                    sched->u_last = NULL;
227                }
228                else if( sched->u_root.next == &thread->sched_list )
229                {
230                    sched->u_last = sched->u_root.pred;
231                }
232                else
233                {
234                    sched->u_last = sched->u_root.next;
235                }
236            }
237
238            // release lock protecting scheduler state
239            busylock_release( &sched->lock );
240
241            // delete thread descriptor
242            last = thread_destroy( thread );
243
244#if DEBUG_SCHED_HANDLE_SIGNALS
245uint32_t cycle = (uint32_t)hal_get_cycles();
246if( DEBUG_SCHED_HANDLE_SIGNALS < cycle )
247printk("\n[DBG] %s : thread %x in process %x on core[%x,%d] deleted / cycle %d\n",
248__FUNCTION__ , thread->trdid , process->pid , local_cxy , thread->core->lid , cycle );
249#endif
250            // destroy process descriptor if no more threads
251            if( last ) 
252            {
253                // delete process   
254                process_destroy( process );
255
256#if DEBUG_SCHED_HANDLE_SIGNALS
257cycle = (uint32_t)hal_get_cycles();
258if( DEBUG_SCHED_HANDLE_SIGNALS < cycle )
259printk("\n[DBG] %s : process %x in cluster %x deleted / cycle %d\n",
260__FUNCTION__ , process->pid , local_cxy , cycle );
261#endif
262            }
263        }
264    }
265} // end sched_handle_signals()
266
267////////////////////////////////////////////////////////////////////////////////////////////
268// This static function is called by the sched_yield function when the RFC_FIFO
269// associated to the core is not empty.
270// It checks if it exists an idle (blocked) RPC thread for this core, and unblock
271// it if found. It creates a new RPC thread if no idle RPC thread is found.
272////////////////////////////////////////////////////////////////////////////////////////////
273// @ sched   : local pointer on scheduler.
274////////////////////////////////////////////////////////////////////////////////////////////
275void sched_rpc_activate( scheduler_t * sched )
276{
277    error_t         error;
278    thread_t      * thread; 
279    list_entry_t  * iter;
280    lid_t           lid = CURRENT_THREAD->core->lid;
281    bool_t          found = false;
282
283    // search one IDLE RPC thread associated to the selected core   
284    LIST_FOREACH( &sched->k_root , iter )
285    {
286        thread = LIST_ELEMENT( iter , thread_t , sched_list );
287        if( (thread->type == THREAD_RPC) && (thread->blocked == THREAD_BLOCKED_IDLE ) ) 
288        {
289            // exit loop
290            found = true;
291            break;
292        }
293    }
294
295    if( found == false )     // create new RPC thread     
296    {
297        error = thread_kernel_create( &thread,
298                                      THREAD_RPC, 
299                                              &rpc_thread_func, 
300                                      NULL,
301                                          lid );
302        // check memory
303        if ( error )
304        {
305            printk("\n[WARNING] in %s : no memory to create a RPC thread in cluster %x\n",
306            __FUNCTION__, local_cxy );
307        }
308        else
309        {
310            // unblock created RPC thread
311            thread->blocked = 0;
312
313            // update RPC threads counter 
314            hal_atomic_add( &LOCAL_CLUSTER->rpc_threads[lid] , 1 );
315
316#if DEBUG_SCHED_RPC_ACTIVATE
317uint32_t cycle = (uint32_t)hal_get_cycles();
318if( DEBUG_SCHED_RPC_ACTIVATE < cycle ) 
319printk("\n[DBG] %s : new RPC thread %x created for core[%x,%d] / cycle %d\n",
320__FUNCTION__, thread->trdid, local_cxy, lid, cycle );
321#endif
322        }
323    }
324    else                 // RPC thread found => unblock it
325    {
326        // unblock found RPC thread
327        thread_unblock( XPTR( local_cxy , thread ) , THREAD_BLOCKED_IDLE );
328
329#if DEBUG_SCHED_RPC_ACTIVATE
330uint32_t cycle = (uint32_t)hal_get_cycles();
331if( DEBUG_SCHED_RPC_ACTIVATE < cycle ) 
332printk("\n[DBG] %s : idle RPC thread %x unblocked for core[%x,%d] / cycle %d\n",
333__FUNCTION__, thread->trdid, local_cxy, lid, cycle );
334#endif
335
336    }
337
338} // end sched_rpc_activate()
339
340
341
342///////////////////////////////////////////////////////////////////////////////////////////
343//         public functions
344///////////////////////////////////////////////////////////////////////////////////////////
345
346////////////////////////////////
347void sched_init( core_t * core )
348{
349    scheduler_t * sched = &core->scheduler;
350
351    sched->u_threads_nr   = 0;
352    sched->k_threads_nr   = 0;
353
354    sched->current        = CURRENT_THREAD;
355    sched->idle           = NULL;               // initialized in kernel_init()
356    sched->u_last         = NULL;               // initialized in sched_register_thread()
357    sched->k_last         = NULL;               // initialized in sched_register_thread()
358
359    // initialise threads lists
360    list_root_init( &sched->u_root );
361    list_root_init( &sched->k_root );
362
363    // init lock
364    busylock_init( &sched->lock , LOCK_SCHED_STATE );
365
366    sched->req_ack_pending = false;             // no pending request
367    sched->trace           = false;             // context switches trace desactivated
368
369}  // end sched_init()
370
371////////////////////////////////////////////
372void sched_register_thread( core_t   * core,
373                            thread_t * thread )
374{
375    scheduler_t * sched = &core->scheduler;
376    thread_type_t type  = thread->type;
377
378    // take lock protecting sheduler state
379    busylock_acquire( &sched->lock );
380
381    if( type == THREAD_USER )
382    {
383        list_add_last( &sched->u_root , &thread->sched_list );
384        sched->u_threads_nr++;
385        if( sched->u_last == NULL ) sched->u_last = &thread->sched_list;
386    }
387    else // kernel thread
388    {
389        list_add_last( &sched->k_root , &thread->sched_list );
390        sched->k_threads_nr++;
391        if( sched->k_last == NULL ) sched->k_last = &thread->sched_list; 
392    }
393
394    // release lock
395    busylock_release( &sched->lock );
396
397}  // end sched_register_thread()
398
399//////////////////////////////////////
400void sched_yield( const char * cause )
401{
402    thread_t      * next;
403    thread_t      * current = CURRENT_THREAD;
404    core_t        * core    = current->core;
405    lid_t           lid     = core->lid;
406    scheduler_t   * sched   = &core->scheduler;
407    remote_fifo_t * fifo    = &LOCAL_CLUSTER->rpc_fifo[lid]; 
408 
409#if (DEBUG_SCHED_YIELD & 0x1)
410if( sched->trace ) sched_display( lid );
411#endif
412
413// check current thread busylocks counter
414assert( (current->busylocks == 0),
415"thread cannot yield : busylocks = %d\n", current->busylocks ); 
416
417    // activate or create an RPC thread if RPC_FIFO non empty
418    if( remote_fifo_is_empty( fifo ) == false )  sched_rpc_activate( sched );
419
420    // disable IRQs / save SR in current thread descriptor
421    hal_disable_irq( &current->save_sr );
422
423    // take lock protecting sheduler state
424    busylock_acquire( &sched->lock );
425   
426    // select next thread
427    next = sched_select( sched );
428
429// check next thread kernel_stack overflow
430assert( (next->signature == THREAD_SIGNATURE),
431"kernel stack overflow for thread %x on core[%x,%d] \n", next, local_cxy, lid );
432
433// check next thread attached to same core as the calling thread
434assert( (next->core == current->core),
435"next core %x != current core %x\n", next->core, current->core );
436
437// check next thread not blocked when type != IDLE
438assert( ((next->blocked == 0) || (next->type == THREAD_IDLE)) ,
439"next thread %x (%s) is blocked on core[%x,%d]\n", 
440next->trdid , thread_type_str(next->type) , local_cxy , lid );
441
442    // switch contexts and update scheduler state if next != current
443        if( next != current )
444    {
445        // update scheduler
446        sched->current = next;
447        if( next->type == THREAD_USER ) sched->u_last = &next->sched_list;
448        else                            sched->k_last = &next->sched_list;
449
450        // handle FPU ownership
451            if( next->type == THREAD_USER )
452        {
453                if( next == current->core->fpu_owner )  hal_fpu_enable();
454                else                                    hal_fpu_disable();
455        }
456
457        // release lock protecting scheduler state
458        busylock_release( &sched->lock );
459
460#if DEBUG_SCHED_YIELD
461if( sched->trace )
462printk("\n[DBG] %s : core[%x,%d] / cause = %s\n"
463"      thread %x (%s) (%x,%x) => thread %x (%s) (%x,%x) / cycle %d\n",
464__FUNCTION__, local_cxy, lid, cause, 
465current, thread_type_str(current->type), current->process->pid, current->trdid,next ,
466thread_type_str(next->type) , next->process->pid , next->trdid , (uint32_t)hal_get_cycles() );
467#endif
468
469        // switch CPU from current thread context to new thread context
470        hal_do_cpu_switch( current->cpu_context, next->cpu_context );
471    }
472    else
473    {
474        // release lock protecting scheduler state
475        busylock_release( &sched->lock );
476
477#if DEBUG_SCHED_YIELD
478if( sched->trace )
479printk("\n[DBG] %s : core[%x,%d] / cause = %s\n"
480"      thread %x (%s) (%x,%x) continue / cycle %d\n",
481__FUNCTION__, local_cxy, lid, cause, current, thread_type_str(current->type),
482current->process->pid, current->trdid, (uint32_t)hal_get_cycles() );
483#endif
484
485    }
486
487    // handle pending requests for all threads executing on this core.
488    sched_handle_signals( core );
489
490    // exit critical section / restore SR from current thread descriptor
491    hal_restore_irq( CURRENT_THREAD->save_sr );
492
493}  // end sched_yield()
494
495
496///////////////////////////////
497void sched_display( lid_t lid )
498{
499    list_entry_t * iter;
500    thread_t     * thread;
501
502// check lid
503assert( (lid < LOCAL_CLUSTER->cores_nr), 
504"illegal core index %d\n", lid);
505
506    core_t       * core    = &LOCAL_CLUSTER->core_tbl[lid];
507    scheduler_t  * sched   = &core->scheduler;
508   
509    // get pointers on TXT0 chdev
510    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
511    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
512    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
513
514    // get extended pointer on remote TXT0 lock
515    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
516
517    // get TXT0 lock
518    remote_busylock_acquire( lock_xp );
519
520    nolock_printk("\n***** threads on core[%x,%d] / current %x / cycle %d\n",
521    local_cxy , core->lid, sched->current, (uint32_t)hal_get_cycles() );
522
523    // display kernel threads
524    LIST_FOREACH( &sched->k_root , iter )
525    {
526        thread = LIST_ELEMENT( iter , thread_t , sched_list );
527        if (thread->type == THREAD_DEV) 
528        {
529            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n",
530            thread_type_str( thread->type ), thread->process->pid, thread->trdid,
531            thread, thread->blocked, thread->flags, thread->chdev->name );
532        }
533        else
534        {
535            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
536            thread_type_str( thread->type ), thread->process->pid, thread->trdid,
537            thread, thread->blocked, thread->flags );
538        }
539    }
540
541    // display user threads
542    LIST_FOREACH( &sched->u_root , iter )
543    {
544        thread = LIST_ELEMENT( iter , thread_t , sched_list );
545        nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
546        thread_type_str( thread->type ), thread->process->pid, thread->trdid,
547        thread, thread->blocked, thread->flags );
548    }
549
550    // release TXT0 lock
551    remote_busylock_release( lock_xp );
552
553}  // end sched_display()
554
555/////////////////////////////////////
556void sched_remote_display( cxy_t cxy,
557                           lid_t lid )
558{
559    thread_t     * thread;
560
561// check cxy
562assert( (cluster_is_undefined( cxy ) == false),
563"illegal cluster %x\n", cxy );
564
565// check lid
566assert( (lid < hal_remote_l32( XPTR( cxy , &LOCAL_CLUSTER->cores_nr ) ) ),
567"illegal core index %d\n", lid );
568
569    // get local pointer on target scheduler
570    core_t      * core  = &LOCAL_CLUSTER->core_tbl[lid];
571    scheduler_t * sched = &core->scheduler;
572
573    // get local pointer on current thread in target scheduler
574    thread_t * current = hal_remote_lpt( XPTR( cxy, &sched->current ) );
575
576    // get local pointer on the first kernel and user threads list_entry
577    list_entry_t * k_entry = hal_remote_lpt( XPTR( cxy , &sched->k_root.next ) );
578    list_entry_t * u_entry = hal_remote_lpt( XPTR( cxy , &sched->u_root.next ) );
579   
580    // get pointers on TXT0 chdev
581    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
582    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
583    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
584
585    // get extended pointer on remote TXT0 chdev lock
586    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
587
588    // get TXT0 lock
589    remote_busylock_acquire( lock_xp );
590
591    // display header
592    nolock_printk("\n***** threads on core[%x,%d] / current %x / cycle %d\n",
593    cxy , lid, current, (uint32_t)hal_get_cycles() );
594
595    // display kernel threads
596    while( k_entry != &sched->k_root )
597    {
598        // get local pointer on kernel_thread
599        thread = LIST_ELEMENT( k_entry , thread_t , sched_list );
600
601        // get relevant thead info
602        thread_type_t type    = hal_remote_l32 ( XPTR( cxy , &thread->type ) );
603        trdid_t       trdid   = hal_remote_l32 ( XPTR( cxy , &thread->trdid ) );
604        uint32_t      blocked = hal_remote_l32 ( XPTR( cxy , &thread->blocked ) );
605        uint32_t      flags   = hal_remote_l32 ( XPTR( cxy , &thread->flags ) );
606        process_t *   process = hal_remote_lpt( XPTR( cxy , &thread->process ) );
607        pid_t         pid     = hal_remote_l32 ( XPTR( cxy , &process->pid ) );
608
609        // display thread info
610        if (type == THREAD_DEV) 
611        {
612            char      name[16];
613            chdev_t * chdev = hal_remote_lpt( XPTR( cxy , &thread->chdev ) );
614            hal_remote_strcpy( XPTR( local_cxy , name ), XPTR( cxy , &chdev->name ) );
615
616            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n",
617            thread_type_str( type ), pid, trdid, thread, blocked, flags, name );
618        }
619        else
620        {
621            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
622            thread_type_str( type ), pid, trdid, thread, blocked, flags );
623        }
624
625        // get next remote kernel thread list_entry
626        k_entry = hal_remote_lpt( XPTR( cxy , &k_entry->next ) );
627    }
628
629    // display user threads
630    while( u_entry != &sched->u_root )
631    {
632        // get local pointer on user_thread
633        thread = LIST_ELEMENT( u_entry , thread_t , sched_list );
634
635        // get relevant thead info
636        thread_type_t type    = hal_remote_l32 ( XPTR( cxy , &thread->type ) );
637        trdid_t       trdid   = hal_remote_l32 ( XPTR( cxy , &thread->trdid ) );
638        uint32_t      blocked = hal_remote_l32 ( XPTR( cxy , &thread->blocked ) );
639        uint32_t      flags   = hal_remote_l32 ( XPTR( cxy , &thread->flags ) );
640        process_t *   process = hal_remote_lpt( XPTR( cxy , &thread->process ) );
641        pid_t         pid     = hal_remote_l32 ( XPTR( cxy , &process->pid ) );
642
643        nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
644        thread_type_str( type ), pid, trdid, thread, blocked, flags );
645
646        // get next user thread list_entry
647        u_entry = hal_remote_lpt( XPTR( cxy , &u_entry->next ) );
648    }
649
650    // release TXT0 lock
651    remote_busylock_release( lock_xp );
652
653}  // end sched_remote_display()
654
655
Note: See TracBrowser for help on using the repository browser.