X-Git-Url: https://git.ucc.asn.au/?p=tpg%2Facess2.git;a=blobdiff_plain;f=KernelLand%2FKernel%2Fthreads.c;h=469c5ec18dd3beae6afe01d71d9f4c14a1a67009;hp=17cccca1e24ed752f65e992f62255016cae0ccbf;hb=14d0ba44433f0f828aff710184fd3c597ab73999;hpb=8dcc3e209d0d728565a18c8dca2b0ba220b74a6f diff --git a/KernelLand/Kernel/threads.c b/KernelLand/Kernel/threads.c index 17cccca1..469c5ec1 100644 --- a/KernelLand/Kernel/threads.c +++ b/KernelLand/Kernel/threads.c @@ -4,17 +4,23 @@ * threads.c * - Common Thread Control */ +#define DEBUG 0 #include #include #include #include #include #include +#include #include // VFS Handle maintainence +#include +#include // Configuration +#define DEBUG_TRACE_ACTIVEQUEUE 0 // Trace adds/removals from the active queue #define DEBUG_TRACE_TICKETS 0 // Trace ticket counts #define DEBUG_TRACE_STATE 0 // Trace state changes (sleep/wake) +#define DEBUG_TRACE_SCHEDULE 0 // Trace scheduling // --- Schedulers --- #define SCHED_UNDEF 0 @@ -29,7 +35,11 @@ #define DEFAULT_PRIORITY 5 #define MIN_PRIORITY 10 +#define PRIthread_fmt "%p(%i %s)" +#define PRIthread_args(t) (t), ((t)?(t)->TID:-1), ((t)?(t)->ThreadName:"-") + // === IMPORTS === +extern void User_Signal_Kill(int SigNum); // === TYPE === typedef struct @@ -47,7 +57,7 @@ void Threads_Delete(tThread *Thread); char *Threads_GetName(tTID ID); #if 0 void Threads_SetPriority(tThread *Thread, int Pri); -tThread *Threads_CloneTCB(Uint *Err, Uint Flags); +tThread *Threads_CloneTCB(Uint Flags); int Threads_WaitTID(int TID, int *status); tThread *Threads_GetThread(Uint TID); #endif @@ -57,14 +67,23 @@ void Threads_int_AddToList(tThreadList *List, tThread *Thread); void Threads_Exit(int TID, int Status); void Threads_Kill(tThread *Thread, int Status); void Threads_Yield(void); + int Threads_int_Sleep(enum eThreadStatus Status, void *Ptr, int Num, tThread **ListHead, tThread **ListTail, tShortSpinlock *Lock); void Threads_Sleep(void); int Threads_Wake(tThread *Thread); void Threads_AddActive(tThread *Thread); tThread *Threads_RemActive(void); -#endif void Threads_ToggleTrace(int TID); +#endif void Threads_Fault(int Num); void Threads_SegFault(tVAddr Addr); +void Threads_PostSignalTo(tThread *Thread, int SignalNum); +#if 0 +void Threads_PostSignal(int SignalNum); +void Threads_SignalGroup(tPGID PGID, int SignalNum); +#endif + int Threads_GetPendingSignal(void); +void Threads_SetSignalHandler(int SignalNum, void *Handler); +void *Threads_GetSignalHandler(int SignalNum); #if 0 int Threads_GetPID(void); int Threads_GetTID(void); @@ -74,12 +93,15 @@ tGID Threads_GetGID(void); int Threads_SetGID(Uint *Errno, tUID ID); #endif void Threads_int_DumpThread(tThread *thread); +#if 0 void Threads_Dump(void); +#endif void Threads_DumpActive(void); +tThread *Threads_int_GetRunnable(void); // === GLOBALS === // -- Core Thread -- -struct sProcess gProcessZero = { +tProcess gProcessZero = { }; // Only used for the core kernel tThread gThreadZero = { @@ -90,6 +112,7 @@ tThread gThreadZero = { .Priority = DEFAULT_PRIORITY // Number of tickets }; // -- Processes -- +tProcess *gAllProcesses = &gProcessZero; // --- Locks --- tShortSpinlock glThreadListLock; ///\note NEVER use a heap function while locked // --- Current State --- @@ -165,8 +188,18 @@ void Threads_Delete(tThread *Thread) if( Thread->Process->nThreads == 0 ) { tProcess *proc = Thread->Process; + + // Remove from global process list + // TODO: RWLock + if(proc->Prev) + proc->Prev->Next = proc->Next; + else + gAllProcesses = proc->Next; + if(proc->Next) + proc->Next->Prev = proc->Prev; + // VFS Cleanup - VFS_CloseAllUserHandles(); + VFS_CloseAllUserHandles( proc ); // Architecture cleanup Proc_ClearProcess( proc ); // VFS Configuration strings @@ -211,7 +244,7 @@ int Threads_SetName(const char *NewName) if( IsHeap(oldname) ) free( oldname ); cur->ThreadName = strdup(NewName); -// Log_Debug("Threads", "Thread renamed to '%s'", NewName); + Log_Debug("Threads", "Thread renamed to '%s'", NewName); return 0; } @@ -297,11 +330,10 @@ void Threads_SetPriority(tThread *Thread, int Pri) */ tThread *Threads_CloneTCB(Uint Flags) { - tThread *cur, *new; - cur = Proc_GetCurThread(); + tThread *cur = Proc_GetCurThread(); // Allocate and duplicate - new = malloc(sizeof(tThread)); + tThread *new = malloc(sizeof(tThread)); if(new == NULL) { errno = -ENOMEM; return NULL; } memcpy(new, cur, sizeof(tThread)); @@ -323,7 +355,7 @@ tThread *Threads_CloneTCB(Uint Flags) if(Flags & CLONE_VM) { tProcess *newproc, *oldproc; oldproc = cur->Process; - new->Process = malloc( sizeof(struct sProcess) ); + new->Process = calloc( sizeof(struct sProcess), 1 ); newproc = new->Process; newproc->PID = new->TID; if( Flags & CLONE_PGID ) @@ -333,17 +365,17 @@ tThread *Threads_CloneTCB(Uint Flags) newproc->UID = oldproc->UID; newproc->GID = oldproc->GID; newproc->MaxFD = oldproc->MaxFD; - if( oldproc->CurrentWorkingDir ) - newproc->CurrentWorkingDir = strdup( oldproc->CurrentWorkingDir ); - else - newproc->CurrentWorkingDir = NULL; - if( oldproc->RootDir ) - newproc->RootDir = strdup( oldproc->RootDir ); - else - newproc->RootDir = NULL; + newproc->CurrentWorkingDir = oldproc->CurrentWorkingDir ? strdup( oldproc->CurrentWorkingDir ) : NULL; + newproc->RootDir = oldproc->RootDir ? strdup( oldproc->RootDir ) : NULL; newproc->nThreads = 1; // Reference all handles in the VFS VFS_ReferenceUserHandles(); + + // Add to global list + newproc->Prev = NULL; + // TODO: RWLock + newproc->Next = gAllProcesses; + gAllProcesses = newproc; newproc->FirstThread = new; new->ProcessNext = NULL; @@ -442,9 +474,38 @@ tThread *Threads_CloneThreadZero(void) tTID Threads_WaitTID(int TID, int *Status) { // Any Child - if(TID == -1) { - Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Any Child"); - return -1; + if(TID == -1) + { + Uint32 ev = Threads_WaitEvents(THREAD_EVENT_DEADCHILD); + tTID ret = -1; + if( ev & THREAD_EVENT_DEADCHILD ) + { + tThread * const us = Proc_GetCurThread(); + // A child died, get the TID + ASSERT(us->LastDeadChild); + tThread *dead_thread = us->LastDeadChild; + us->LastDeadChild = dead_thread->Next; + if( us->LastDeadChild ) + Threads_PostEvent( us, THREAD_EVENT_DEADCHILD ); + else + Threads_ClearEvent( THREAD_EVENT_DEADCHILD ); + Mutex_Release(&us->DeadChildLock); + + ret = dead_thread->TID; + // - Mark as dead (as opposed to undead) + ASSERTC(dead_thread->Status, ==, THREAD_STAT_ZOMBIE); + dead_thread->Status = THREAD_STAT_DEAD; + // - Set return status + if(Status) + *Status = dead_thread->RetStatus; + + Threads_Delete( dead_thread ); + } + else + { + Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Any Child"); + } + return ret; } // Any peer/child thread @@ -460,33 +521,15 @@ tTID Threads_WaitTID(int TID, int *Status) } // Specific Thread - if(TID > 0) { - tThread *t = Threads_GetThread(TID); + if(TID > 0) + { + // TODO: Register on thread to be poked when it dies tTID ret; - - // Wait for the thread to die! - // TODO: Handle child also being suspended if wanted - while(t->Status != THREAD_STAT_ZOMBIE) { - Threads_Sleep(); - Log_Debug("Threads", "%i waiting for %i, t->Status = %i", - Threads_GetTID(), t->TID, t->Status); - } - - // Set return status - ret = t->TID; - switch(t->Status) + // NOTE: Race condition - Other child dies, desired child dies, first death is 'lost' + while( (ret = Threads_WaitTID(-1, Status)) != TID ) { - case THREAD_STAT_ZOMBIE: - // Kill the thread - t->Status = THREAD_STAT_DEAD; - // TODO: Child return value? - if(Status) *Status = t->RetStatus; - // add to delete queue - Threads_Delete( t ); - break; - default: - if(Status) *Status = -1; - break; + if( ret == -1 ) + break; } return ret; } @@ -685,9 +728,13 @@ void Threads_Kill(tThread *Thread, int Status) Thread->Status = THREAD_STAT_ZOMBIE; SHORTREL( &glThreadListLock ); - // TODO: Send something like SIGCHLD - Threads_Wake( Thread->Parent ); + // TODO: It's possible that we could be timer-preempted here, should disable that... somehow + Mutex_Acquire( &Thread->Parent->DeadChildLock ); // released by parent + Thread->Next = Thread->Parent->LastDeadChild; + Thread->Parent->LastDeadChild = Thread; + Threads_PostEvent( Thread->Parent, THREAD_EVENT_DEADCHILD ); + // Process cleanup happens on reaping Log("Thread %i went *hurk* (%i)", Thread->TID, Status); // And, reschedule @@ -707,6 +754,64 @@ void Threads_Yield(void) Proc_Reschedule(); } +/** + * \breif Wait for the thread status to not be a specified value + */ +void Threads_int_WaitForStatusEnd(enum eThreadStatus Status) +{ + tThread *us = Proc_GetCurThread(); + LOG("us = %p(%i %s), status=%i", us, us->TID, us->ThreadName, Status); + ASSERT(Status != THREAD_STAT_ACTIVE); + ASSERT(Status != THREAD_STAT_DEAD); + while( us->Status == Status ) + { + Proc_Reschedule(); + if( us->Status == Status ) + Debug("Thread %p(%i %s) rescheduled while in %s state for %p", + us, us->TID, us->ThreadName, + casTHREAD_STAT[Status], + __builtin_return_address(0)); + } +} + +int Threads_int_Sleep(enum eThreadStatus Status, void *Ptr, int Num, tThread **ListHead, tThread **ListTail, tShortSpinlock *Lock) +{ + SHORTLOCK( &glThreadListLock ); + tThread *us = Threads_RemActive(); + us->Next = NULL; + // - Mark as sleeping + us->Status = Status; + us->WaitPointer = Ptr; + us->RetStatus = Num; // Use RetStatus as a temp variable + + // - Add to waiting + if( ListTail ) { + if(*ListTail) { + (*ListTail)->Next = us; + } + else { + *ListHead = us; + } + *ListTail = us; + } + else if( ListHead ) { + us->Next = *ListHead; + *ListHead = us; + } + else { + // Nothing + } + + //if( Proc_ThreadSync(us) ) + // return ; + SHORTREL( &glThreadListLock ); + if( Lock ) + SHORTREL( Lock ); + Threads_int_WaitForStatusEnd(Status); + us->WaitPointer = NULL; + return us->RetStatus; +} + /** * \fn void Threads_Sleep(void) * \brief Take the current process off the run queue @@ -738,12 +843,7 @@ void Threads_Sleep(void) // Release Spinlock SHORTREL( &glThreadListLock ); - - while(cur->Status != THREAD_STAT_ACTIVE) { - Proc_Reschedule(); - if( cur->Status != THREAD_STAT_ACTIVE ) - Log("%i - Huh? why am I up? zzzz...", cur->TID); - } + Threads_int_WaitForStatusEnd(THREAD_STAT_SLEEPING); } @@ -765,11 +865,11 @@ int Threads_Wake(tThread *Thread) return -EALREADY; case THREAD_STAT_SLEEPING: - SHORTLOCK( &glThreadListLock ); // Remove from sleeping queue + SHORTLOCK( &glThreadListLock ); Threads_int_DelFromQueue(&gSleepingThreads, Thread); - SHORTREL( &glThreadListLock ); + Threads_AddActive( Thread ); #if DEBUG_TRACE_STATE @@ -835,7 +935,7 @@ int Threads_Wake(tThread *Thread) return -ENOTIMPL; default: - Warning("Threads_Wake - Unknown process status (%i)\n", Thread->Status); + Log_Warning("Threads", "Threads_Wake - Unknown process status (%i)", Thread->Status); return -EINTERNAL; } } @@ -868,27 +968,40 @@ void Threads_ToggleTrace(int TID) */ void Threads_AddActive(tThread *Thread) { + #if DEBUG_TRACE_ACTIVEQUEUE + Debug("Threads_AddActive("PRIthread_fmt")", PRIthread_args(Thread)); + #endif SHORTLOCK( &glThreadListLock ); - if( Thread->Status == THREAD_STAT_ACTIVE ) { + if( Thread->Status == THREAD_STAT_ACTIVE ) + { tThread *cur = Proc_GetCurThread(); - Log_Warning("Threads", "WTF, %p CPU%i %p (%i %s) is adding %p (%i %s) when it is active", + Log_KernelPanic("Threads", + "ret=%p CPU%i "PRIthread_fmt" is adding "PRIthread_fmt" when it is active", __builtin_return_address(0), - GetCPUNum(), cur, cur->TID, cur->ThreadName, Thread, Thread->TID, Thread->ThreadName); + GetCPUNum(), PRIthread_args(cur), PRIthread_args(Thread)); SHORTREL( &glThreadListLock ); return ; } // Set state Thread->Status = THREAD_STAT_ACTIVE; -// Thread->CurCPU = -1; // Add to active list + // - Thread can be the current thread if we're interrupted just before + // Proc_Reschedule in a sleep state. + if( Thread != Proc_GetCurThread() ) { #if SCHEDULER_TYPE == SCHED_RR_PRI tThreadList *list = &gaActiveThreads[Thread->Priority]; #else tThreadList *list = &gActiveThreads; #endif + #if DEBUG_TRACE_ACTIVEQUEUE + Debug(" - Head="PRIthread_fmt",Tail="PRIthread_fmt"", + PRIthread_args(list->Head), + PRIthread_args(list->Tail) + ); + #endif Threads_int_AddToList( list, Thread ); } @@ -924,8 +1037,12 @@ void Threads_AddActive(tThread *Thread) */ tThread *Threads_RemActive(void) { + tThread *us = Proc_GetCurThread(); + #if DEBUG_TRACE_ACTIVEQUEUE + Debug("Threads_RemActive(%p(%i %s))", us, us->TID, us->ThreadName); + #endif giNumActiveThreads --; - return Proc_GetCurThread(); + return us; } /** @@ -988,6 +1105,105 @@ void Threads_SegFault(tVAddr Addr) //Threads_Exit( 0, -1 ); } + +void Threads_PostSignalTo(tThread *Thread, int SignalNum) +{ + ASSERT(Thread); + Log_Debug("Threads", "Signalling %i(%s) with %i", Thread->TID, Thread->ThreadName, SignalNum); + Thread->PendingSignal = SignalNum; + Threads_PostEvent(Thread, THREAD_EVENT_SIGNAL); +} +void Threads_PostSignal(int SignalNum) +{ + Threads_PostSignalTo( Proc_GetCurThread(), SignalNum ); +} + +void Threads_SignalGroup(tPGID PGID, int Signal) +{ + for( tProcess *proc = gAllProcesses; proc; proc = proc->Next ) + { + if(proc->PGID == PGID) + { + Threads_PostSignalTo(proc->FirstThread, Signal); + } + } +} + +/** + */ +int Threads_GetPendingSignal(void) +{ + tThread *cur = Proc_GetCurThread(); + + // Atomic AND with 0 fetches and clears in one operation + int ret = __sync_fetch_and_and( &cur->PendingSignal, 0 ); + if( ret ) + { + Log_Debug("Threads", "Thread %i(%s) has signal %i pending", + cur->TID, cur->ThreadName, ret); + } + return ret; +} + +/* + * \brief Update the current thread's signal handler + */ +void Threads_SetSignalHandler(int SignalNum, void *Handler) +{ + if( SignalNum <= 0 || SignalNum >= NSIGNALS ) + return ; + if( !MM_IsUser(Handler) ) + return ; + Proc_GetCurThread()->Process->SignalHandlers[SignalNum] = Handler; +} + +/** + * \brief Gets the registered (or default, if none set) handler for a signal. + * \return Handler function pointer, OR NULL if no signal to be ignored + */ +void *Threads_GetSignalHandler(int SignalNum) +{ + // TODO: Core dump + void *User_Signal_Core = User_Signal_Kill; + + if( SignalNum <= 0 || SignalNum >= NSIGNALS ) + return NULL; + void *ret = Proc_GetCurThread()->Process->SignalHandlers[SignalNum]; + if( !ret || (SignalNum == SIGKILL || SignalNum == SIGSTOP) ) + { + // Defaults + switch(SignalNum) + { + case SIGHUP: + case SIGINT: + ret = User_Signal_Kill; + break; + case SIGQUIT: + case SIGILL: + case SIGABRT: + case SIGFPE: + ret = User_Signal_Core; + break; + case SIGKILL: + ret = User_Signal_Kill; + break; + case SIGSEGV: + ret = User_Signal_Core; + break; + case SIGPIPE: + case SIGALRM: + case SIGTERM: + ret = User_Signal_Kill; + break; + default: + ret = NULL; + break; + } + } + Log_Debug("Threads", "Handler %p for signal %i", ret, SignalNum); + return ret; +} + // --- Process Structure Access Functions --- tPGID Threads_GetPGID(void) { @@ -1041,31 +1257,50 @@ int *Threads_GetErrno(void) } // --- Configuration --- -int *Threads_GetMaxFD(void) +int *Threads_GetMaxFD(tProcess *Process) { - return &Proc_GetCurThread()->Process->MaxFD; + if(!Process) Process = Proc_GetCurThread()->Process; + return &Process->MaxFD; } -char **Threads_GetChroot(void) +char **Threads_GetChroot(tProcess *Process) { - return &Proc_GetCurThread()->Process->RootDir; + if(!Process) Process = Proc_GetCurThread()->Process; + return &Process->RootDir; } -char **Threads_GetCWD(void) +char **Threads_GetCWD(tProcess *Process) { - return &Proc_GetCurThread()->Process->CurrentWorkingDir; + if(!Process) Process = Proc_GetCurThread()->Process; + return &Process->CurrentWorkingDir; } // --- void Threads_int_DumpThread(tThread *thread) { + if( !thread ) { + Log(" %p NULL", thread); + return ; + } + if( !CheckMem(thread, sizeof(tThread)) ) { + Log(" %p INVAL", thread); + return ; + } + tPID pid = (thread->Process ? thread->Process->PID : -1); + const char *statstr = (thread->Status < sizeof(casTHREAD_STAT)/sizeof(casTHREAD_STAT[0]) + ? casTHREAD_STAT[thread->Status] : ""); Log(" %p %i (%i) - %s (CPU %i) - %i (%s)", - thread, thread->TID, thread->Process->PID, thread->ThreadName, thread->CurCPU, - thread->Status, casTHREAD_STAT[thread->Status] + thread, thread->TID, pid, thread->ThreadName, thread->CurCPU, + thread->Status, statstr ); switch(thread->Status) { case THREAD_STAT_MUTEXSLEEP: Log(" Mutex Pointer: %p", thread->WaitPointer); break; + case THREAD_STAT_RWLOCKSLEEP: + Log(" Lock Pointer: %p", thread->WaitPointer); + Log(" Lock Name: %s", + ((tRWLock*)thread->WaitPointer)->Name); + break; case THREAD_STAT_SEMAPHORESLEEP: Log(" Semaphore Pointer: %p", thread->WaitPointer); Log(" Semaphore Name: %s:%s", @@ -1073,13 +1308,16 @@ void Threads_int_DumpThread(tThread *thread) ((tSemaphore*)thread->WaitPointer)->Name ); break; + case THREAD_STAT_EVENTSLEEP: + Log(" Event Mask: %x", thread->RetStatus); + break; case THREAD_STAT_ZOMBIE: Log(" Return Status: %i", thread->RetStatus); break; default: break; } Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum); - Log(" KStack 0x%x", thread->KernelStack); + Log(" KStack %p", thread->KernelStack); if( thread->bInstrTrace ) Log(" Tracing Enabled"); Proc_DumpThreadCPUState(thread); @@ -1090,22 +1328,16 @@ void Threads_int_DumpThread(tThread *thread) */ void Threads_DumpActive(void) { - tThread *thread; - tThreadList *list; - #if SCHEDULER_TYPE == SCHED_RR_PRI - int i; - #endif - Log("Active Threads: (%i reported)", giNumActiveThreads); #if SCHEDULER_TYPE == SCHED_RR_PRI - for( i = 0; i < MIN_PRIORITY+1; i++ ) + for( int i = 0; i < MIN_PRIORITY+1; i++ ) { - list = &gaActiveThreads[i]; + tThreadList *list = &gaActiveThreads[i]; #else - list = &gActiveThreads; + tThreadList *list = &gActiveThreads; #endif - for(thread=list->Head;thread;thread=thread->Next) + for(tThread *thread = list->Head; thread; thread = thread->Next) { Threads_int_DumpThread(thread); if(thread->Status != THREAD_STAT_ACTIVE) @@ -1124,18 +1356,138 @@ void Threads_DumpActive(void) */ void Threads_Dump(void) { - tThread *thread; - Log("--- Thread Dump ---"); Threads_DumpActive(); Log("All Threads:"); - for(thread=gAllThreads;thread;thread=thread->GlobalNext) + for(tThread *thread = gAllThreads; thread; thread = thread->GlobalNext) { Threads_int_DumpThread(thread); } } +tThread *Threads_int_GetRunnable(void) +{ + #if SCHEDULER_TYPE == SCHED_LOTTERY + // ----------------------------------- + // Lottery Scheduler + // ----------------------------------- + #if DEBUG_VALIDATE_TICKET_COUNTS + { + int total_tickets = 0; + for(const tThread *thread = gActiveThreads.Head; thread; thread = thread->Next) + { + if(thread->Status != THREAD_STAT_ACTIVE) + Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i", + thread, thread->TID, thread->ThreadName, thread->Status); + if(thread->Next == thread) { + Panic("Bookkeeping fail - %p %i(%s) loops back on itself", + thread, thread->TID, thread->ThreadName, thread->Status); + } + total_tickets += caiTICKET_COUNTS[ thread->Priority ]; + } + if(total_tickets != giFreeTickets) + { + Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i", + giFreeTickets, total_tickets, CPU); + } + } + # endif + + // No free tickets (all tasks delegated to cores) + if( giFreeTickets == 0 ) + { + return NULL; + } + + // Get the ticket number + int ticket = rand() % giFreeTickets; + int number = ticket; + + // Find the next thread + tThread **pnp = &gActiveThreads.Head; + tThread *thread; + for(thread = gActiveThreads.Head; thread; pnp = &thread->Next, thread = thread->Next ) + { + if( caiTICKET_COUNTS[ thread->Priority ] > number) + break; + number -= caiTICKET_COUNTS[ thread->Priority ]; + } + + // If we didn't find a thread, something went wrong + if(thread == NULL) + { + int total_tickets = 0; + for(thread=gActiveThreads;thread;thread=thread->Next) { + if(thread->CurCPU >= 0) continue; + total_tickets += caiTICKET_COUNTS[ thread->Priority ]; + } + Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)", + giFreeTickets, total_tickets); + } + + // Remove + *pnp = thread->Next; + if( !thread->Next ) + gActiveThreads.Tail = prev; + + giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ]; + # if DEBUG_TRACE_TICKETS + LogF("Log: CPU%i allocated %p (%i %s), (%i [-%i] tickets in pool), \n", + CPU, thread, thread->TID, thread->ThreadName, + giFreeTickets, caiTICKET_COUNTS[ thread->Priority ]); + # endif + return thread; + + #elif SCHEDULER_TYPE == SCHED_RR_PRI + + // ----------------------------------- + // Priority based round robin scheduler + // ----------------------------------- + for( int i = 0; i < MIN_PRIORITY + 1; i ++ ) + { + if( gaActiveThreads[i].Head == NULL ) + continue ; + + tThread *thread = gaActiveThreads[i].Head; + + if( thread->Status != THREAD_STAT_ACTIVE ) { + for( const tThread *t = gaActiveThreads[i].Head; t; t = t->Next ) + LogF("- %p(%i %s)\n", t, t->TID, t->ThreadName); + Panic("Thread %p(%i %s) from pqueue %i is active!", + thread, thread->TID, thread->ThreadName, i); + } + + // Remove from head + gaActiveThreads[i].Head = thread->Next; + if(!thread->Next) + gaActiveThreads[i].Tail = NULL; + thread->Next = NULL; + return thread; + } + return NULL; + + #elif SCHEDULER_TYPE == SCHED_RR_SIM + + // ----------------------------------- + // Single-list round-robin + // ----------------------------------- + tThread *thread = gActiveThreads.Head; + LOG("thread = %p", thread); + if( thread ) + { + gActiveThreads.Head = thread->Next; + if(!thread->Next) + gaActiveThreads.Tail = NULL; + thread->Next = NULL; + } + return thread; + #else + # error "Unimplemented scheduling algorithm" + return NULL; + #endif +} + /** * \brief Gets the next thread to run * \param CPU Current CPU @@ -1143,50 +1495,29 @@ void Threads_Dump(void) */ tThread *Threads_GetNextToRun(int CPU, tThread *Last) { - tThread *thread; - - // If this CPU has the lock, we must let it complete - if( CPU_HAS_LOCK( &glThreadListLock ) ) - return Last; + ASSERT( CPU_HAS_LOCK(&glThreadListLock) ); // Don't change threads if the current CPU has switches disabled - if( gaThreads_NoTaskSwitch[CPU] ) + if( gaThreads_NoTaskSwitch[CPU] ) { + LOG("- Denied"); return Last; - - // Lock thread list - SHORTLOCK( &glThreadListLock ); + } // Make sure the current (well, old) thread is marked as de-scheduled if(Last) Last->CurCPU = -1; // No active threads, just take a nap if(giNumActiveThreads == 0) { - SHORTREL( &glThreadListLock ); + LOG("- No active"); #if DEBUG_TRACE_TICKETS Log("No active threads"); #endif return NULL; } - #if 0 - #if SCHEDULER_TYPE != SCHED_RR_PRI - // Special case: 1 thread - if(giNumActiveThreads == 1) { - if( gActiveThreads.Head->CurCPU == -1 ) - gActiveThreads.Head->CurCPU = CPU; - - SHORTREL( &glThreadListLock ); - - if( gActiveThreads.Head->CurCPU == CPU ) - return gActiveThreads.Head; - - return NULL; // CPU has nothing to do - } - #endif - #endif - // Allow the old thread to be scheduled again - if( Last ) { + if( Last ) + { if( Last->Status == THREAD_STAT_ACTIVE ) { tThreadList *list; #if SCHEDULER_TYPE == SCHED_LOTTERY @@ -1205,6 +1536,10 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) #endif // Add to end of list Threads_int_AddToList( list, Last ); + #if DEBUG_TRACE_ACTIVEQUEUE > 1 + Debug("Threads_GetNextToRun: Append thread %p(%i %s)", + Last, Last->TID, Last->ThreadName); + #endif } #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS else @@ -1213,131 +1548,34 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) #endif Last->CurCPU = -1; } - - // --- - // Lottery Scheduler - // --- - #if SCHEDULER_TYPE == SCHED_LOTTERY - { - int ticket, number; - # if 1 - number = 0; - for(thread = gActiveThreads.Head; thread; thread = thread->Next) - { - if(thread->Status != THREAD_STAT_ACTIVE) - Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i", - thread, thread->TID, thread->ThreadName, thread->Status); - if(thread->Next == thread) { - Panic("Bookkeeping fail - %p %i(%s) loops back on itself", - thread, thread->TID, thread->ThreadName, thread->Status); - } - number += caiTICKET_COUNTS[ thread->Priority ]; - } - if(number != giFreeTickets) { - Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i", - giFreeTickets, number, CPU); - } - # endif - - // No free tickets (all tasks delegated to cores) - if( giFreeTickets == 0 ) { - SHORTREL(&glThreadListLock); - return NULL; - } - - // Get the ticket number - ticket = number = rand() % giFreeTickets; - - // Find the next thread - for(thread = gActiveThreads.Head; thread; prev = thread, thread = thread->Next ) - { - if( caiTICKET_COUNTS[ thread->Priority ] > number) break; - number -= caiTICKET_COUNTS[ thread->Priority ]; - } - - // If we didn't find a thread, something went wrong - if(thread == NULL) - { - number = 0; - for(thread=gActiveThreads;thread;thread=thread->Next) { - if(thread->CurCPU >= 0) continue; - number += caiTICKET_COUNTS[ thread->Priority ]; - } - Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)", - giFreeTickets, number); - } - // Remove - if(prev) - prev->Next = thread->Next; - else - gActiveThreads.Head = thread->Next; - if(!thread->Next) - gActiveThreads.Tail = prev; - - giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ]; - # if DEBUG_TRACE_TICKETS - LogF("Log: CPU%i allocated %p (%i %s), (%i [-%i] tickets in pool), \n", - CPU, thread, thread->TID, thread->ThreadName, - giFreeTickets, caiTICKET_COUNTS[ thread->Priority ]); - # endif - } + // Call actual scheduler + tThread *thread = Threads_int_GetRunnable(); - // --- - // Priority based round robin scheduler - // --- - #elif SCHEDULER_TYPE == SCHED_RR_PRI + // Anything to do? + if( thread ) { - int i; - thread = NULL; - for( i = 0; i < MIN_PRIORITY + 1; i ++ ) + if( thread->Status != THREAD_STAT_ACTIVE ) { - if( !gaActiveThreads[i].Head ) - continue ; - - thread = gaActiveThreads[i].Head; - - // Remove from head - gaActiveThreads[i].Head = thread->Next; - if(!thread->Next) - gaActiveThreads[i].Tail = NULL; - thread->Next = NULL; - break; + LogF("Thread %p(%i %s) scheduled while not active\n", + thread, thread->TID, thread->ThreadName); } + + // Make the new thread non-schedulable + thread->CurCPU = CPU; + thread->Remaining = thread->Quantum; - // Anything to do? - if( !thread ) { - SHORTREL(&glThreadListLock); - return NULL; - } - if( thread->Status != THREAD_STAT_ACTIVE ) { - LogF("Oops, Thread %i (%s) is not active\n", thread->TID, thread->ThreadName); - } + #if DEBUG_TRACE_SCHEDULE + Debug("Scheduled "PRIthread_fmt", next = %p", + PRIthread_args(thread), + thread->Next); + #endif } - #elif SCHEDULER_TYPE == SCHED_RR_SIM + else { - // Get the next thread off the list - thread = gActiveThreads.Head; - gActiveThreads.Head = thread->Next; - if(!thread->Next) - gaActiveThreads.Tail = NULL; - thread->Next = NULL; - - // Anything to do? - if( !thread ) { - SHORTREL(&glThreadListLock); - return NULL; - } + // No thread possible, warning condition (idle thread should be runnable) + Warning("No runnable thread for CPU%i", CPU); } - #else - # error "Unimplemented scheduling algorithm" - #endif - - // Make the new thread non-schedulable - thread->CurCPU = CPU; - thread->Remaining = thread->Quantum; - - SHORTREL( &glThreadListLock ); return thread; }