/* * scheduler.c - Core scheduler implementation. * * Author Alain Greiner (2016,2017,2018) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-MKH. is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH. is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH.; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #include #include #include #include #include #include #include #include #include #include #include #include /////////////////////////////////////////////////////////////////////////////////////////// // global variables /////////////////////////////////////////////////////////////////////////////////////////// extern chdev_directory_t chdev_dir; // allocated in kernel_init.c extern process_t process_zero; // allocated in kernel_init.c /////////////////////////////////////////////////////////////////////////////////////////// // private functions /////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////// // This static function does NOT modify the scheduler state. // It just select a thread in the list of attached threads, implementing the following // three steps policy: // 1) It scan the list of kernel threads, from the next thread after the last executed one, // and returns the first runnable found : not IDLE, not blocked, client queue not empty. // It can be the current thread. // 2) If no kernel thread found, it scan the list of user thread, from the next thread after // the last executed one, and returns the first runable found : not blocked. // It can be the current thread. // 3) If no runable thread found, it returns the idle thread. //////////////////////////////////////////////////////////////////////////////////////////// // @ sched : local pointer on scheduler. // @ returns pointer on selected thread descriptor //////////////////////////////////////////////////////////////////////////////////////////// thread_t * sched_select( scheduler_t * sched ) { thread_t * thread; list_entry_t * current; list_entry_t * last; list_entry_t * root; bool_t done; uint32_t count; // first : scan the kernel threads list if not empty if( list_is_empty( &sched->k_root ) == false ) { root = &sched->k_root; last = sched->k_last; done = false; count = 0; current = last; while( done == false ) { // check kernel threads list assert( (count < sched->k_threads_nr), "bad kernel threads list" ); // get next entry in kernel list current = current->next; // check exit condition if( current == last ) done = true; // skip the root that does not contain a thread if( current == root ) continue; else count++; // get thread pointer for this entry thread = LIST_ELEMENT( current , thread_t , sched_list ); // select kernel thread if non blocked and non THREAD_IDLE if( (thread->blocked == 0) && (thread->type != THREAD_IDLE) ) return thread; } // end loop on kernel threads } // end kernel threads // second : scan the user threads list if not empty if( list_is_empty( &sched->u_root ) == false ) { root = &sched->u_root; last = sched->u_last; done = false; count = 0; current = last; while( done == false ) { // check user threads list assert( (count < sched->u_threads_nr), "bad user threads list" ); // get next entry in user list current = current->next; // check exit condition if( current == last ) done = true; // skip the root that does not contain a thread if( current == root ) continue; else count++; // get thread pointer for this entry thread = LIST_ELEMENT( current , thread_t , sched_list ); // select thread if non blocked if( thread->blocked == 0 ) return thread; } // end loop on user threads } // end user threads // third : return idle thread if no other runnable thread return sched->idle; } // end sched_select() //////////////////////////////////////////////////////////////////////////////////////////// // This static function is the only function that can actually delete a thread, // (and the associated process descriptor if required). // It is private, because it is only called by the sched_yield() public function. // It scan all threads attached to a given scheduler, and executes the relevant // actions for two types of pending requests: // // - REQ_ACK : it checks that target thread is blocked, decrements the response counter // to acknowledge the client thread, and reset the pending request. // - REQ_DELETE : it removes the target thread from the process th_tbl[], remove it // from the scheduler list, and release the memory allocated to thread descriptor. // For an user thread, it destroys the process descriptor it the target thread is // the last thread in the local process descriptor. // // Implementation note: // We use a while to scan the threads in scheduler lists, because some threads can // be destroyed, and we want not use a LIST_FOREACH() //////////////////////////////////////////////////////////////////////////////////////////// // @ core : local pointer on the core descriptor. //////////////////////////////////////////////////////////////////////////////////////////// static void sched_handle_signals( core_t * core ) { list_entry_t * iter; list_entry_t * root; thread_t * thread; process_t * process; scheduler_t * sched; uint32_t threads_nr; // number of threads in scheduler list ltid_t ltid; // thread local index uint32_t count; // number of threads in local process // get pointer on scheduler sched = &core->scheduler; /////////////// scan user threads to handle both ACK and DELETE requests root = &sched->u_root; iter = root->next; while( iter != root ) { // get pointer on thread thread = LIST_ELEMENT( iter , thread_t , sched_list ); // increment iterator iter = iter->next; // handle REQ_ACK if( thread->flags & THREAD_FLAG_REQ_ACK ) { // check thread blocked assert( (thread->blocked & THREAD_BLOCKED_GLOBAL) , "thread not blocked" ); // decrement response counter hal_atomic_add( thread->ack_rsp_count , -1 ); // reset REQ_ACK in thread descriptor thread_reset_req_ack( thread ); } // handle REQ_DELETE only if target thread != calling thread if( (thread->flags & THREAD_FLAG_REQ_DELETE) && (thread != CURRENT_THREAD) ) { // get thread process descriptor process = thread->process; // get thread ltid ltid = LTID_FROM_TRDID( thread->trdid); // take the lock protecting sheduler state busylock_acquire( &sched->lock ); // update scheduler state threads_nr = sched->u_threads_nr; sched->u_threads_nr = threads_nr - 1; list_unlink( &thread->sched_list ); if( sched->u_last == &thread->sched_list ) { if( threads_nr == 1 ) { sched->u_last = NULL; } else if( sched->u_root.next == &thread->sched_list ) { sched->u_last = sched->u_root.pred; } else { sched->u_last = sched->u_root.next; } } // release the lock protecting sheduler state busylock_release( &sched->lock ); // check th_nr value assert( (process->th_nr > 0) , "process th_nr cannot be 0\n" ); // remove thread from process th_tbl[] process->th_tbl[ltid] = NULL; count = hal_atomic_add( &process->th_nr , - 1 ); // release memory allocated for thread descriptor thread_destroy( thread ); hal_fence(); #if DEBUG_SCHED_HANDLE_SIGNALS uint32_t cycle = (uint32_t)hal_get_cycles(); if( DEBUG_SCHED_HANDLE_SIGNALS < cycle ) printk("\n[%s] thread[%x,%x] on core[%x,%d] deleted / cycle %d\n", __FUNCTION__ , process->pid , thread->trdid , local_cxy , thread->core->lid , cycle ); #endif // destroy process descriptor if last thread if( count == 1 ) { // delete process process_destroy( process ); #if DEBUG_SCHED_HANDLE_SIGNALS cycle = (uint32_t)hal_get_cycles(); if( DEBUG_SCHED_HANDLE_SIGNALS < cycle ) printk("\n[%s] process %x in cluster %x deleted / cycle %d\n", __FUNCTION__ , process->pid , local_cxy , cycle ); #endif } } } // end user threads ////// scan kernel threads for DELETE only root = &sched->k_root; iter = root->next; while( iter != root ) { // get pointer on thread thread = LIST_ELEMENT( iter , thread_t , sched_list ); // increment iterator iter = iter->next; // handle REQ_DELETE only if target thread != calling thread if( (thread->flags & THREAD_FLAG_REQ_DELETE) && (thread != CURRENT_THREAD) ) { // check process descriptor is local kernel process assert( ( thread->process == &process_zero ) , "illegal process descriptor\n"); // get thread ltid ltid = LTID_FROM_TRDID( thread->trdid); // take the lock protecting sheduler state busylock_acquire( &sched->lock ); // update scheduler state threads_nr = sched->k_threads_nr; sched->k_threads_nr = threads_nr - 1; list_unlink( &thread->sched_list ); if( sched->k_last == &thread->sched_list ) { if( threads_nr == 1 ) { sched->k_last = NULL; } else if( sched->k_root.next == &thread->sched_list ) { sched->k_last = sched->k_root.pred; } else { sched->k_last = sched->k_root.next; } } // release the lock protecting sheduler state busylock_release( &sched->lock ); // get number of threads in local kernel process count = process_zero.th_nr; // check th_nr value assert( (process_zero.th_nr > 0) , "kernel process th_nr cannot be 0\n" ); // remove thread from process th_tbl[] process_zero.th_tbl[ltid] = NULL; hal_atomic_add( &process_zero.th_nr , - 1 ); // delete thread descriptor thread_destroy( thread ); #if DEBUG_SCHED_HANDLE_SIGNALS uint32_t cycle = (uint32_t)hal_get_cycles(); if( DEBUG_SCHED_HANDLE_SIGNALS < cycle ) printk("\n[%s] thread[%x,%x] on core[%x,%d] deleted / cycle %d\n", __FUNCTION__ , process_zero.pid , thread->trdid , local_cxy , thread->core->lid , cycle ); #endif } } } // end sched_handle_signals() //////////////////////////////////////////////////////////////////////////////////////////// // This static function is called by the sched_yield function when the RFC_FIFO // associated to the core is not empty. // It search an idle RPC thread for this core, and unblock it if found. // It creates a new RPC thread if no idle RPC thread is found. //////////////////////////////////////////////////////////////////////////////////////////// // @ sched : local pointer on scheduler. //////////////////////////////////////////////////////////////////////////////////////////// static void sched_rpc_activate( scheduler_t * sched ) { error_t error; thread_t * thread; list_entry_t * iter; lid_t lid = CURRENT_THREAD->core->lid; bool_t found = false; // search one IDLE RPC thread associated to the selected core LIST_FOREACH( &sched->k_root , iter ) { thread = LIST_ELEMENT( iter , thread_t , sched_list ); if( (thread->type == THREAD_RPC) && (thread->blocked == THREAD_BLOCKED_IDLE ) ) { found = true; break; } } if( found == false ) // create new RPC thread { error = thread_kernel_create( &thread, THREAD_RPC, &rpc_server_func, NULL, lid ); // check memory if ( error ) { printk("\n[ERROR] in %s : no memory to create a RPC thread in cluster %x\n", __FUNCTION__, local_cxy ); } else { // unblock created RPC thread thread->blocked = 0; // update RPC threads counter hal_atomic_add( &LOCAL_CLUSTER->rpc_threads[lid] , 1 ); #if DEBUG_SCHED_RPC_ACTIVATE uint32_t cycle = (uint32_t)hal_get_cycles(); if( DEBUG_SCHED_RPC_ACTIVATE < cycle ) printk("\n[%s] new RPC thread %x created for core[%x,%d] / total %d / cycle %d\n", __FUNCTION__, thread->trdid, local_cxy, lid, LOCAL_CLUSTER->rpc_threads[lid], cycle ); #endif } } else // RPC thread found => unblock it { // unblock found RPC thread thread_unblock( XPTR( local_cxy , thread ) , THREAD_BLOCKED_IDLE ); #if DEBUG_SCHED_RPC_ACTIVATE uint32_t cycle = (uint32_t)hal_get_cycles(); if( DEBUG_SCHED_RPC_ACTIVATE < cycle ) printk("\n[%s] idle RPC thread %x unblocked for core[%x,%d] / cycle %d\n", __FUNCTION__, thread->trdid, local_cxy, lid, cycle ); #endif } } // end sched_rpc_activate() /////////////////////////////////////////////////////////////////////////////////////////// // public functions /////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////// void sched_init( core_t * core ) { scheduler_t * sched = &core->scheduler; sched->u_threads_nr = 0; sched->k_threads_nr = 0; sched->current = CURRENT_THREAD; sched->idle = NULL; // initialized in kernel_init() sched->u_last = NULL; // initialized in sched_register_thread() sched->k_last = NULL; // initialized in sched_register_thread() // initialise threads lists list_root_init( &sched->u_root ); list_root_init( &sched->k_root ); // init lock busylock_init( &sched->lock , LOCK_SCHED_STATE ); sched->req_ack_pending = false; // no pending request sched->trace = false; // context switches trace desactivated } // end sched_init() //////////////////////////////////////////// void sched_register_thread( core_t * core, thread_t * thread ) { scheduler_t * sched = &core->scheduler; thread_type_t type = thread->type; // take lock protecting sheduler state busylock_acquire( &sched->lock ); if( type == THREAD_USER ) { list_add_last( &sched->u_root , &thread->sched_list ); sched->u_threads_nr++; if( sched->u_last == NULL ) sched->u_last = &thread->sched_list; } else // kernel thread { list_add_last( &sched->k_root , &thread->sched_list ); sched->k_threads_nr++; if( sched->k_last == NULL ) sched->k_last = &thread->sched_list; } // release lock busylock_release( &sched->lock ); } // end sched_register_thread() ////////////////////////////////////// void sched_yield( const char * cause ) { thread_t * next; thread_t * current = CURRENT_THREAD; core_t * core = current->core; lid_t lid = core->lid; scheduler_t * sched = &core->scheduler; remote_fifo_t * fifo = &LOCAL_CLUSTER->rpc_fifo[lid]; #if (DEBUG_SCHED_YIELD & 0x1) // if( sched->trace ) if( (uint32_t)hal_get_cycles() > DEBUG_SCHED_YIELD ) sched_display( lid ); #endif // This assert should never be false, as this check has been // done before, by any function that can possibly deschedule... assert( (current->busylocks == 0), "unexpected descheduling of thread holding %d busylocks = %d\n", current->busylocks ); // activate or create an RPC thread if RPC_FIFO non empty if( remote_fifo_is_empty( fifo ) == false ) sched_rpc_activate( sched ); // disable IRQs / save SR in current thread descriptor hal_disable_irq( ¤t->save_sr ); // take lock protecting sheduler state busylock_acquire( &sched->lock ); // select next thread next = sched_select( sched ); // check next thread kernel_stack overflow assert( (next->signature == THREAD_SIGNATURE), "kernel stack overflow for thread %x on core[%x,%d] \n", next, local_cxy, lid ); // check next thread attached to same core as the calling thread assert( (next->core == current->core), "next core %x != current core %x\n", next->core, current->core ); // check next thread not blocked when type != IDLE assert( ((next->blocked == 0) || (next->type == THREAD_IDLE)) , "next thread %x (%s) is blocked on core[%x,%d]\n", next->trdid , thread_type_str(next->type) , local_cxy , lid ); // switch contexts and update scheduler state if next != current if( next != current ) { // update scheduler sched->current = next; if( next->type == THREAD_USER ) sched->u_last = &next->sched_list; else sched->k_last = &next->sched_list; // handle FPU ownership if( next->type == THREAD_USER ) { if( next == current->core->fpu_owner ) hal_fpu_enable(); else hal_fpu_disable(); } // release lock protecting scheduler state busylock_release( &sched->lock ); #if DEBUG_SCHED_YIELD // if( sched->trace ) if( (uint32_t)hal_get_cycles() > DEBUG_SCHED_YIELD ) printk("\n[%s] core[%x,%d] / cause = %s\n" " thread %x (%s) (%x,%x) => thread %x (%s) (%x,%x) / cycle %d\n", __FUNCTION__, local_cxy, lid, cause, current, thread_type_str(current->type), current->process->pid, current->trdid,next , thread_type_str(next->type) , next->process->pid , next->trdid , (uint32_t)hal_get_cycles() ); #endif // switch CPU from current thread context to new thread context hal_do_cpu_switch( current->cpu_context, next->cpu_context ); } else { // release lock protecting scheduler state busylock_release( &sched->lock ); #if (DEBUG_SCHED_YIELD & 1) // if( sched->trace ) if(uint32_t)hal_get_cycles() > DEBUG_SCHED_YIELD ) printk("\n[%s] core[%x,%d] / cause = %s\n" " thread %x (%s) (%x,%x) continue / cycle %d\n", __FUNCTION__, local_cxy, lid, cause, current, thread_type_str(current->type), current->process->pid, current->trdid, (uint32_t)hal_get_cycles() ); #endif } // handle pending requests for all threads executing on this core. sched_handle_signals( core ); // exit critical section / restore SR from current thread descriptor hal_restore_irq( CURRENT_THREAD->save_sr ); } // end sched_yield() /////////////////////////////// void sched_display( lid_t lid ) { list_entry_t * iter; thread_t * thread; // check lid assert( (lid < LOCAL_CLUSTER->cores_nr), "illegal core index %d\n", lid); core_t * core = &LOCAL_CLUSTER->core_tbl[lid]; scheduler_t * sched = &core->scheduler; // get pointers on TXT0 chdev xptr_t txt0_xp = chdev_dir.txt_tx[0]; cxy_t txt0_cxy = GET_CXY( txt0_xp ); chdev_t * txt0_ptr = GET_PTR( txt0_xp ); // get extended pointer on remote TXT0 lock xptr_t lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock ); // get TXT0 lock remote_busylock_acquire( lock_xp ); nolock_printk("\n***** threads on core[%x,%d] / current %x / rpc_threads %d / cycle %d\n", local_cxy , lid, sched->current, LOCAL_CLUSTER->rpc_threads[lid], (uint32_t)hal_get_cycles() ); // display kernel threads LIST_FOREACH( &sched->k_root , iter ) { thread = LIST_ELEMENT( iter , thread_t , sched_list ); if (thread->type == THREAD_DEV) { nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n", thread_type_str( thread->type ), thread->process->pid, thread->trdid, thread, thread->blocked, thread->flags, thread->chdev->name ); } else { nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n", thread_type_str( thread->type ), thread->process->pid, thread->trdid, thread, thread->blocked, thread->flags ); } } // display user threads LIST_FOREACH( &sched->u_root , iter ) { thread = LIST_ELEMENT( iter , thread_t , sched_list ); nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n", thread_type_str( thread->type ), thread->process->pid, thread->trdid, thread, thread->blocked, thread->flags ); } // release TXT0 lock remote_busylock_release( lock_xp ); } // end sched_display() ///////////////////////////////////// void sched_remote_display( cxy_t cxy, lid_t lid ) { thread_t * thread; // check cxy assert( (cluster_is_undefined( cxy ) == false), "illegal cluster %x\n", cxy ); assert( (lid < hal_remote_l32( XPTR( cxy , &LOCAL_CLUSTER->cores_nr ) ) ), "illegal core index %d\n", lid ); // get local pointer on target scheduler core_t * core = &LOCAL_CLUSTER->core_tbl[lid]; scheduler_t * sched = &core->scheduler; // get local pointer on current thread in target scheduler thread_t * current = hal_remote_lpt( XPTR( cxy, &sched->current ) ); // get local pointer on the first kernel and user threads list_entry list_entry_t * k_entry = hal_remote_lpt( XPTR( cxy , &sched->k_root.next ) ); list_entry_t * u_entry = hal_remote_lpt( XPTR( cxy , &sched->u_root.next ) ); // get pointers on TXT0 chdev xptr_t txt0_xp = chdev_dir.txt_tx[0]; cxy_t txt0_cxy = GET_CXY( txt0_xp ); chdev_t * txt0_ptr = GET_PTR( txt0_xp ); // get extended pointer on remote TXT0 chdev lock xptr_t lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock ); // get TXT0 lock remote_busylock_acquire( lock_xp ); // get rpc_threads uint32_t rpcs = hal_remote_l32( XPTR( cxy , &LOCAL_CLUSTER->rpc_threads[lid] ) ); // display header nolock_printk("\n***** threads on core[%x,%d] / current %x / rpc_threads %d / cycle %d\n", cxy , lid, current, rpcs, (uint32_t)hal_get_cycles() ); // display kernel threads while( k_entry != &sched->k_root ) { // get local pointer on kernel_thread thread = LIST_ELEMENT( k_entry , thread_t , sched_list ); // get relevant thead info thread_type_t type = hal_remote_l32 ( XPTR( cxy , &thread->type ) ); trdid_t trdid = hal_remote_l32 ( XPTR( cxy , &thread->trdid ) ); uint32_t blocked = hal_remote_l32 ( XPTR( cxy , &thread->blocked ) ); uint32_t flags = hal_remote_l32 ( XPTR( cxy , &thread->flags ) ); process_t * process = hal_remote_lpt ( XPTR( cxy , &thread->process ) ); pid_t pid = hal_remote_l32 ( XPTR( cxy , &process->pid ) ); // display thread info if (type == THREAD_DEV) { char name[16]; chdev_t * chdev = hal_remote_lpt( XPTR( cxy , &thread->chdev ) ); hal_remote_strcpy( XPTR( local_cxy , name ), XPTR( cxy , chdev->name ) ); nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X / %s\n", thread_type_str( type ), pid, trdid, thread, blocked, flags, name ); } else { nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n", thread_type_str( type ), pid, trdid, thread, blocked, flags ); } // get next remote kernel thread list_entry k_entry = hal_remote_lpt( XPTR( cxy , &k_entry->next ) ); } // display user threads while( u_entry != &sched->u_root ) { // get local pointer on user_thread thread = LIST_ELEMENT( u_entry , thread_t , sched_list ); // get relevant thead info thread_type_t type = hal_remote_l32 ( XPTR( cxy , &thread->type ) ); trdid_t trdid = hal_remote_l32 ( XPTR( cxy , &thread->trdid ) ); uint32_t blocked = hal_remote_l32 ( XPTR( cxy , &thread->blocked ) ); uint32_t flags = hal_remote_l32 ( XPTR( cxy , &thread->flags ) ); process_t * process = hal_remote_lpt ( XPTR( cxy , &thread->process ) ); pid_t pid = hal_remote_l32 ( XPTR( cxy , &process->pid ) ); nolock_printk(" - %s / pid %X / trdid %X / desc %X / block %X / flags %X\n", thread_type_str( type ), pid, trdid, thread, blocked, flags ); // get next user thread list_entry u_entry = hal_remote_lpt( XPTR( cxy , &u_entry->next ) ); } // release TXT0 lock remote_busylock_release( lock_xp ); } // end sched_remote_display()