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

Last change on this file since 462 was 462, checked in by viala@…, 6 years ago

FIX: Add a spinlock_init on sheduler->lock.

File size: 18.1 KB
Line 
1/*
2 * scheduler.c - Core scheduler implementation.
3 *
4 * Author    Alain Greiner (2016)
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// Extern global variables
39///////////////////////////////////////////////////////////////////////////////////////////
40
41uint32_t   idle_thread_count;
42uint32_t   idle_thread_count_active;
43
44extern chdev_directory_t    chdev_dir;          // allocated in kernel_init.c file
45extern uint32_t             switch_save_sr[];   // allocated in kernel_init.c file
46
47////////////////////////////////
48void sched_init( core_t * core )
49{
50    scheduler_t * sched = &core->scheduler;
51
52    sched->u_threads_nr   = 0;
53    sched->k_threads_nr   = 0;
54
55    sched->current        = CURRENT_THREAD;
56    sched->idle           = NULL;               // initialized in kernel_init()
57    sched->u_last         = NULL;               // initialized in sched_register_thread()
58    sched->k_last         = NULL;               // initialized in sched_register_thread()
59    spinlock_init(&sched->lock);
60
61    // initialise threads lists
62    list_root_init( &sched->u_root );
63    list_root_init( &sched->k_root );
64
65    sched->req_ack_pending = false;             // no pending request
66    sched->trace           = false;             // context switches trace desactivated
67
68}  // end sched_init()
69
70////////////////////////////////////////////
71void sched_register_thread( core_t   * core,
72                            thread_t * thread )
73{
74    scheduler_t * sched = &core->scheduler;
75    thread_type_t type  = thread->type;
76
77    // take lock protecting sheduler lists
78    spinlock_lock( &sched->lock );
79
80    if( type == THREAD_USER )
81    {
82        list_add_last( &sched->u_root , &thread->sched_list );
83        sched->u_threads_nr++;
84        if( sched->u_last == NULL ) sched->u_last = &thread->sched_list;
85    }
86    else // kernel thread
87    {
88        list_add_last( &sched->k_root , &thread->sched_list );
89        sched->k_threads_nr++;
90        if( sched->k_last == NULL ) sched->k_last = &thread->sched_list; 
91    }
92
93    // release lock
94    hal_fence();
95    spinlock_unlock( &sched->lock );
96
97}  // end sched_register_thread()
98
99//////////////////////////////////////////////
100thread_t * sched_select( scheduler_t * sched )
101{
102    thread_t     * thread;
103    list_entry_t * current;
104    list_entry_t * last;
105    list_entry_t * root;
106    bool_t         done;
107    uint32_t       count;
108
109    // take lock protecting sheduler lists
110    spinlock_lock( &sched->lock );
111
112    // first : scan the kernel threads list if not empty
113    if( list_is_empty( &sched->k_root ) == false )
114    {
115        root    = &sched->k_root;
116        last    = sched->k_last;
117        done    = false;
118        count   = 0;
119        current = last;
120
121        while( done == false )
122        {
123            assert( (count < sched->k_threads_nr), __FUNCTION__, "bad kernel threads list" );
124
125            // get next entry in kernel list
126            current = current->next;
127
128            // check exit condition
129            if( current == last ) done = true;
130
131            // skip the root that does not contain a thread
132            if( current == root ) continue;
133            else                  count++;
134
135            // get thread pointer for this entry
136            thread = LIST_ELEMENT( current , thread_t , sched_list );
137
138            // select kernel thread if non blocked and non THREAD_IDLE
139            if( (thread->blocked == 0)  && (thread->type != THREAD_IDLE) )
140            {
141                spinlock_unlock( &sched->lock );
142                return thread;
143            }
144        } // end loop on kernel threads
145    } // end kernel threads
146
147    // second : scan the user threads list if not empty
148    if( list_is_empty( &sched->u_root ) == false )
149    {
150        root    = &sched->u_root;
151        last    = sched->u_last;
152        done    = false;
153        count   = 0;
154        current = last;
155
156        while( done == false )
157        {
158            assert( (count < sched->u_threads_nr), __FUNCTION__, "bad user threads list" );
159
160            // get next entry in user list
161            current = current->next;
162
163            // check exit condition
164            if( current == last ) done = true;
165
166            // skip the root that does not contain a thread
167            if( current == root ) continue;
168            else                  count++;
169
170            // get thread pointer for this entry
171            thread = LIST_ELEMENT( current , thread_t , sched_list );
172
173            // select thread if non blocked
174            if( thread->blocked == 0 )
175            {
176                spinlock_unlock( &sched->lock );
177                return thread;
178            }
179        } // end loop on user threads
180    } // end user threads
181
182    // third : return idle thread if no other runnable thread
183    spinlock_unlock( &sched->lock );
184    return sched->idle;
185
186}  // end sched_select()
187
188///////////////////////////////////////////
189void sched_handle_signals( core_t * core )
190{
191
192    list_entry_t * iter;
193    list_entry_t * root;
194    thread_t     * thread;
195    process_t    * process;
196    bool_t         last_thread;
197
198    // get pointer on scheduler
199    scheduler_t  * sched = &core->scheduler;
200
201    // get pointer on user threads root
202    root = &sched->u_root;
203
204    // take lock protecting threads lists
205    spinlock_lock( &sched->lock );
206
207    // We use a while to scan the user threads, to control the iterator increment,
208    // because some threads will be destroyed, and we cannot use a LIST_FOREACH()
209
210    // initialise list iterator
211    iter = root->next;
212
213    // scan all user threads
214    while( iter != root )
215    {
216        // get pointer on thread
217        thread = LIST_ELEMENT( iter , thread_t , sched_list );
218
219        // increment iterator
220        iter = iter->next;
221
222        // handle REQ_ACK
223        if( thread->flags & THREAD_FLAG_REQ_ACK )
224        {
225            // check thread blocked
226            assert( (thread->blocked & THREAD_BLOCKED_GLOBAL) , 
227            __FUNCTION__ , "thread not blocked" );
228 
229            // decrement response counter
230            hal_atomic_add( thread->ack_rsp_count , -1 );
231
232            // reset REQ_ACK in thread descriptor
233            thread_reset_req_ack( thread );
234        }
235
236        // handle REQ_DELETE
237        if( thread->flags & THREAD_FLAG_REQ_DELETE )
238        {
239            // get thread process descriptor
240            process = thread->process;
241
242                // release FPU if required
243                if( thread->core->fpu_owner == thread )  thread->core->fpu_owner = NULL;
244
245            // remove thread from scheduler (scheduler lock already taken)
246            uint32_t threads_nr = sched->u_threads_nr;
247
248            assert( (threads_nr != 0) , __FUNCTION__ , "u_threads_nr cannot be 0\n" );
249
250            sched->u_threads_nr = threads_nr - 1;
251            list_unlink( &thread->sched_list );
252            if( sched->u_last == &thread->sched_list )
253            {
254                if( threads_nr == 1 ) 
255                {
256                    sched->u_last = NULL;
257                }
258                else if( sched->u_root.next == &thread->sched_list )
259                {
260                    sched->u_last = sched->u_root.pred;
261                }
262                else
263                {
264                    sched->u_last = sched->u_root.next;
265                }
266            }
267
268            // delete thread descriptor
269            last_thread = thread_destroy( thread );
270
271#if DEBUG_SCHED_HANDLE_SIGNALS
272uint32_t cycle = (uint32_t)hal_get_cycles();
273if( DEBUG_SCHED_HANDLE_SIGNALS < cycle )
274printk("\n[DBG] %s : thread %x in process %x on core[%x,%d] deleted / cycle %d\n",
275__FUNCTION__ , thread->trdid , process->pid , local_cxy , thread->core->lid , cycle );
276#endif
277            // destroy process descriptor if no more threads
278            if( last_thread ) 
279            {
280                // delete process   
281                process_destroy( process );
282
283#if DEBUG_SCHED_HANDLE_SIGNALS
284cycle = (uint32_t)hal_get_cycles();
285if( DEBUG_SCHED_HANDLE_SIGNALS < cycle )
286printk("\n[DBG] %s : process %x in cluster %x deleted / cycle %d\n",
287__FUNCTION__ , process->pid , local_cxy , cycle );
288#endif
289            }
290        }
291    }
292
293    // release lock
294    hal_fence();
295    spinlock_unlock( &sched->lock );
296
297} // end sched_handle_signals()
298
299////////////////////////////////
300void sched_yield( char * cause )
301{
302    thread_t    * next;
303    thread_t    * current = CURRENT_THREAD;
304    core_t      * core    = current->core;
305    scheduler_t * sched   = &core->scheduler;
306 
307#if (DEBUG_SCHED_YIELD & 0x1)
308if( sched->trace )
309sched_display( core->lid );
310#endif
311
312    // delay the yield if current thread has locks
313    if( (current->local_locks != 0) || (current->remote_locks != 0) )
314    {
315        current->flags |= THREAD_FLAG_SCHED;
316        return;
317    }
318
319    // enter critical section / save SR in current thread descriptor
320    hal_disable_irq( &CURRENT_THREAD->save_sr );
321
322    // loop on threads to select next thread
323    next = sched_select( sched );
324
325    // check next thread kernel_stack overflow
326    assert( (next->signature == THREAD_SIGNATURE), __FUNCTION__ , 
327    "kernel stack overflow for thread %x on core[%x,%d] \n", next, local_cxy, core->lid );
328
329    // check next thread attached to same core as the calling thread
330    assert( (next->core == current->core), __FUNCTION__ , 
331    "next core %x != current core %x\n", next->core, current->core );
332
333    // check next thread not blocked when type != IDLE
334    assert( ((next->blocked == 0) || (next->type == THREAD_IDLE)) , __FUNCTION__ ,
335    "next thread %x (%s) is blocked on core[%x,%d]\n", 
336    next->trdid , thread_type_str(next->type) , local_cxy , core->lid );
337
338    // switch contexts and update scheduler state if next != current
339        if( next != current )
340    {
341
342#if DEBUG_SCHED_YIELD
343if( sched->trace )
344printk("\n[DBG] %s : core[%x,%d] / cause = %s\n"
345"      thread %x (%s) (%x,%x) => thread %x (%s) (%x,%x) / cycle %d\n",
346__FUNCTION__, local_cxy, core->lid, cause, 
347current, thread_type_str(current->type), current->process->pid, current->trdid,next ,
348thread_type_str(next->type) , next->process->pid , next->trdid , (uint32_t)hal_get_cycles() );
349#endif
350
351        // update scheduler
352        sched->current = next;
353        if( next->type == THREAD_USER ) sched->u_last = &next->sched_list;
354        else                            sched->k_last = &next->sched_list;
355
356        // handle FPU ownership
357            if( next->type == THREAD_USER )
358        {
359                if( next == current->core->fpu_owner )  hal_fpu_enable();
360                else                                    hal_fpu_disable();
361        }
362
363        // switch CPU from current thread context to new thread context
364        hal_do_cpu_switch( current->cpu_context, next->cpu_context );
365    }
366    else
367    {
368
369#if DEBUG_SCHED_YIELD
370if( sched->trace )
371printk("\n[DBG] %s : core[%x,%d] / cause = %s\n"
372"      thread %x (%s) (%x,%x) continue / cycle %d\n",
373__FUNCTION__, local_cxy, core->lid, cause, current, thread_type_str(current->type),
374current->process->pid, current->trdid, (uint32_t)hal_get_cycles() );
375#endif
376
377    }
378
379    // handle pending requests for all threads executing on this core.
380    sched_handle_signals( core );
381
382    // exit critical section / restore SR from current thread descriptor
383    hal_restore_irq( CURRENT_THREAD->save_sr );
384
385}  // end sched_yield()
386
387
388///////////////////////////////
389void sched_display( lid_t lid )
390{
391    list_entry_t * iter;
392    thread_t     * thread;
393    uint32_t       save_sr;
394
395    assert( (lid < LOCAL_CLUSTER->cores_nr), __FUNCTION__, "illegal core index %d\n", lid);
396
397    core_t       * core    = &LOCAL_CLUSTER->core_tbl[lid];
398    scheduler_t  * sched   = &core->scheduler;
399   
400    // get pointers on TXT0 chdev
401    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
402    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
403    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
404
405    // get extended pointer on remote TXT0 chdev lock
406    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
407
408    // get TXT0 lock in busy waiting mode
409    remote_spinlock_lock_busy( lock_xp , &save_sr );
410
411    nolock_printk("\n***** threads on core[%x,%d] / current %x / cycle %d\n",
412    local_cxy , core->lid, sched->current, (uint32_t)hal_get_cycles() );
413
414    // display kernel threads
415    LIST_FOREACH( &sched->k_root , iter )
416    {
417        thread = LIST_ELEMENT( iter , thread_t , sched_list );
418        if (thread->type == THREAD_DEV) 
419        {
420            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n",
421            thread_type_str( thread->type ), thread->process->pid, thread->trdid,
422            thread, thread->blocked, thread->flags, thread->chdev->name );
423        }
424        else
425        {
426            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
427            thread_type_str( thread->type ), thread->process->pid, thread->trdid,
428            thread, thread->blocked, thread->flags );
429        }
430    }
431
432    // display user threads
433    LIST_FOREACH( &sched->u_root , iter )
434    {
435        thread = LIST_ELEMENT( iter , thread_t , sched_list );
436        nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
437        thread_type_str( thread->type ), thread->process->pid, thread->trdid,
438        thread, thread->blocked, thread->flags );
439    }
440
441    // release TXT0 lock
442    remote_spinlock_unlock_busy( lock_xp , save_sr );
443
444}  // end sched_display()
445
446/////////////////////////////////////
447void sched_remote_display( cxy_t cxy,
448                           lid_t lid )
449{
450    thread_t     * thread;
451    uint32_t       save_sr;
452
453    // check cxy
454    bool_t undefined = cluster_is_undefined( cxy );
455    assert( (undefined == false), __FUNCTION__, "illegal cluster %x\n", cxy );
456
457    // check lid
458    uint32_t cores = hal_remote_lw( XPTR( cxy , &LOCAL_CLUSTER->cores_nr ) );
459    assert( (lid < cores), __FUNCTION__, "illegal core index %d\n", lid);
460
461    // get local pointer on target scheduler
462    core_t      * core  = &LOCAL_CLUSTER->core_tbl[lid];
463    scheduler_t * sched = &core->scheduler;
464
465    // get local pointer on current thread in target scheduler
466    thread_t * current = hal_remote_lpt( XPTR( cxy, &sched->current ) );
467
468    // get local pointer on the first kernel and user threads list_entry
469    list_entry_t * k_entry = hal_remote_lpt( XPTR( cxy , &sched->k_root.next ) );
470    list_entry_t * u_entry = hal_remote_lpt( XPTR( cxy , &sched->u_root.next ) );
471   
472    // get pointers on TXT0 chdev
473    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
474    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
475    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
476
477    // get extended pointer on remote TXT0 chdev lock
478    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
479
480    // get TXT0 lock in busy waiting mode
481    remote_spinlock_lock_busy( lock_xp , &save_sr );
482
483    // display header
484    nolock_printk("\n***** threads on core[%x,%d] / current %x / cycle %d\n",
485    cxy , lid, current, (uint32_t)hal_get_cycles() );
486
487    // display kernel threads
488    while( k_entry != &sched->k_root )
489    {
490        // get local pointer on kernel_thread
491        thread = LIST_ELEMENT( k_entry , thread_t , sched_list );
492
493        // get relevant thead info
494        thread_type_t type    = hal_remote_lw ( XPTR( cxy , &thread->type ) );
495        trdid_t       trdid   = hal_remote_lw ( XPTR( cxy , &thread->trdid ) );
496        uint32_t      blocked = hal_remote_lw ( XPTR( cxy , &thread->blocked ) );
497        uint32_t      flags   = hal_remote_lw ( XPTR( cxy , &thread->flags ) );
498        process_t *   process = hal_remote_lpt( XPTR( cxy , &thread->process ) );
499        pid_t         pid     = hal_remote_lw ( XPTR( cxy , &process->pid ) );
500
501        // display thread info
502        if (type == THREAD_DEV) 
503        {
504            char      name[16];
505            chdev_t * chdev = hal_remote_lpt( XPTR( cxy , &thread->chdev ) );
506            hal_remote_strcpy( XPTR( local_cxy , name ), XPTR( cxy , &chdev->name ) );
507
508            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n",
509            thread_type_str( type ), pid, trdid, thread, blocked, flags, name );
510        }
511        else
512        {
513            nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
514            thread_type_str( type ), pid, trdid, thread, blocked, flags );
515        }
516
517        // get next remote kernel thread list_entry
518        k_entry = hal_remote_lpt( XPTR( cxy , &k_entry->next ) );
519    }
520
521    // display user threads
522    while( u_entry != &sched->u_root )
523    {
524        // get local pointer on user_thread
525        thread = LIST_ELEMENT( u_entry , thread_t , sched_list );
526
527        // get relevant thead info
528        thread_type_t type    = hal_remote_lw ( XPTR( cxy , &thread->type ) );
529        trdid_t       trdid   = hal_remote_lw ( XPTR( cxy , &thread->trdid ) );
530        uint32_t      blocked = hal_remote_lw ( XPTR( cxy , &thread->blocked ) );
531        uint32_t      flags   = hal_remote_lw ( XPTR( cxy , &thread->flags ) );
532        process_t *   process = hal_remote_lpt( XPTR( cxy , &thread->process ) );
533        pid_t         pid     = hal_remote_lw ( XPTR( cxy , &process->pid ) );
534
535        nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n",
536        thread_type_str( type ), pid, trdid, thread, blocked, flags );
537
538        // get next user thread list_entry
539        u_entry = hal_remote_lpt( XPTR( cxy , &u_entry->next ) );
540    }
541
542    // release TXT0 lock
543    remote_spinlock_unlock_busy( lock_xp , save_sr );
544
545}  // end sched_remote_display()
546
Note: See TracBrowser for help on using the repository browser.