X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=Kernel%2Fthreads.c;h=3ebc4dc6aa3428820b4f1d6e488520608e8d46f8;hb=930fe819133ddb444bc6c22df09baf788183f6ad;hp=b9d59f3f00c14644f2678b4bcede04a43c614837;hpb=da67fd4fd32d16dcd6b4cb0b63497a9925a2ef35;p=tpg%2Facess2.git diff --git a/Kernel/threads.c b/Kernel/threads.c index b9d59f3f..3ebc4dc6 100644 --- a/Kernel/threads.c +++ b/Kernel/threads.c @@ -5,15 +5,27 @@ */ #include #include +#include #include +#include +// Configuration #define DEBUG_TRACE_TICKETS 0 // Trace ticket counts #define DEBUG_TRACE_STATE 0 // Trace state changes (sleep/wake) +#define SEMAPHORE_DEBUG 0 + +// --- Schedulers --- +#define SCHED_UNDEF 0 +#define SCHED_LOTTERY 1 // Lottery scheduler +#define SCHED_RR_SIM 2 // Single Queue Round Robin +#define SCHED_RR_PRI 3 // Multi Queue Round Robin +// Set scheduler type +#define SCHEDULER_TYPE SCHED_LOTTERY // === CONSTANTS === #define DEFAULT_QUANTUM 10 -#define DEFAULT_TICKETS 5 -#define MAX_TICKETS 10 +#define DEFAULT_PRIORITY 5 +#define MIN_PRIORITY 10 const enum eConfigTypes cCONFIG_TYPES[] = { CFGT_HEAPSTR, // e.g. CFG_VFS_CWD CFGT_INT, // e.g. CFG_VFS_MAXFILES @@ -22,21 +34,25 @@ const enum eConfigTypes cCONFIG_TYPES[] = { // === IMPORTS === extern void ArchThreads_Init(void); -extern void Proc_Start(void); -extern tThread *Proc_GetCurThread(void); -extern int Proc_Clone(Uint *Err, Uint Flags); extern void Proc_CallFaultHandler(tThread *Thread); +extern void Proc_DumpThreadCPUState(tThread *Thread); +extern int GetCPUNum(void); // === PROTOTYPES === void Threads_Init(void); - int Threads_SetName(char *NewName); +#if 0 + int Threads_SetName(const char *NewName); +#endif char *Threads_GetName(int ID); -void Threads_SetTickets(tThread *Thread, int Num); +#if 0 +void Threads_SetPriority(tThread *Thread, int Pri); tThread *Threads_CloneTCB(Uint *Err, Uint Flags); int Threads_WaitTID(int TID, int *status); tThread *Threads_GetThread(Uint TID); +#endif void Threads_AddToDelete(tThread *Thread); tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread); +#if 0 void Threads_Exit(int TID, int Status); void Threads_Kill(tThread *Thread, int Status); void Threads_Yield(void); @@ -44,42 +60,60 @@ void Threads_Sleep(void); int Threads_Wake(tThread *Thread); void Threads_AddActive(tThread *Thread); tThread *Threads_RemActive(void); +#endif +void Threads_ToggleTrace(int TID); +void Threads_Fault(int Num); +void Threads_SegFault(tVAddr Addr); +#if 0 int Threads_GetPID(void); int Threads_GetTID(void); tUID Threads_GetUID(void); - int Threads_SetUID(Uint *Errno, tUID ID); tGID Threads_GetGID(void); + int Threads_SetUID(Uint *Errno, tUID ID); int Threads_SetGID(Uint *Errno, tUID ID); +#endif void Threads_Dump(void); void Threads_DumpActive(void); -void Mutex_Acquire(tMutex *Mutex); +#if 0 + int Mutex_Acquire(tMutex *Mutex); void Mutex_Release(tMutex *Mutex); int Mutex_IsLocked(tMutex *Mutex); +#endif // === GLOBALS === // -- Core Thread -- // Only used for the core kernel tThread gThreadZero = { - Status: THREAD_STAT_ACTIVE, // Status - ThreadName: "ThreadZero", // Name - Quantum: DEFAULT_QUANTUM, // Default Quantum - Remaining: DEFAULT_QUANTUM, // Current Quantum - NumTickets: DEFAULT_TICKETS // Number of tickets + .Status = THREAD_STAT_ACTIVE, // Status + .ThreadName = (char*)"ThreadZero", // Name + .Quantum = DEFAULT_QUANTUM, // Default Quantum + .Remaining = DEFAULT_QUANTUM, // Current Quantum + .Priority = DEFAULT_PRIORITY // Number of tickets }; // -- Processes -- // --- Locks --- tShortSpinlock glThreadListLock; ///\note NEVER use a heap function while locked // --- Current State --- volatile int giNumActiveThreads = 0; // Number of threads on the active queue -volatile int giFreeTickets = 0; // Number of tickets held by non-scheduled threads volatile Uint giNextTID = 1; // Next TID to allocate // --- Thread Lists --- tThread *gAllThreads = NULL; // All allocated threads -tThread *gActiveThreads = NULL; // Currently Running Threads tThread *gSleepingThreads = NULL; // Sleeping Threads tThread *gDeleteThreads = NULL; // Threads to delete int giNumCPUs = 1; // Number of CPUs BOOL gaThreads_NoTaskSwitch[MAX_CPUS]; // Disables task switches for each core (Pseudo-IF) +// --- Scheduler Types --- +#if SCHEDULER_TYPE == SCHED_LOTTERY +const int caiTICKET_COUNTS[MIN_PRIORITY+1] = {100,81,64,49,36,25,16,9,4,1,0}; +volatile int giFreeTickets = 0; // Number of tickets held by non-scheduled threads +tThread *gActiveThreads = NULL; // Currently Running Threads +#elif SCHEDULER_TYPE == SCHED_RR_SIM +tThread *gActiveThreads = NULL; // Currently Running Threads +#elif SCHEDULER_TYPE == SCHED_RR_PRI +tThread *gaActiveThreads[MIN_PRIORITY+1]; // Active threads for each priority level +#else +# error "Unkown scheduler type" +#endif // === CODE === /** @@ -90,22 +124,29 @@ void Threads_Init(void) { ArchThreads_Init(); + Log_Debug("Threads", "Offsets of tThread"); + Log_Debug("Threads", ".Priority = %i", offsetof(tThread, Priority)); + // Create Initial Task + #if SCHEDULER_TYPE == SCHED_RR_PRI + gaActiveThreads[gThreadZero.Priority] = &gThreadZero; + #else gActiveThreads = &gThreadZero; + #endif + gAllThreads = &gThreadZero; - //giFreeTickets = gThreadZero.NumTickets; // Not needed, as ThreadZero is scheduled giNumActiveThreads = 1; Proc_Start(); } /** - * \fn void Threads_SetName(char *NewName) + * \fn void Threads_SetName(const char *NewName) * \brief Sets the current thread's name * \param NewName New name for the thread * \return Boolean Failure */ -int Threads_SetName(char *NewName) +int Threads_SetName(const char *NewName) { tThread *cur = Proc_GetCurThread(); char *oldname = cur->ThreadName; @@ -137,31 +178,59 @@ char *Threads_GetName(tTID ID) } /** - * \fn void Threads_SetTickets(tThread *Thread, int Num) - * \brief Sets the 'priority' of a task + * \fn void Threads_SetPriority(tThread *Thread, int Pri) + * \brief Sets the priority of a task * \param Thread Thread to update ticket count (NULL means current thread) - * \param Num New ticket count (must be >= 0, clipped to \a MAX_TICKETS) + * \param Pri New priority */ -void Threads_SetTickets(tThread *Thread, int Num) +void Threads_SetPriority(tThread *Thread, int Pri) { // Get current thread if(Thread == NULL) Thread = Proc_GetCurThread(); // Bounds checking - if(Num < 0) return; - if(Num > MAX_TICKETS) Num = MAX_TICKETS; + // - If < 0, set to lowest priority + // - Minumum priority is actualy a high number, 0 is highest + if(Pri < 0) Pri = MIN_PRIORITY; + if(Pri > MIN_PRIORITY) Pri = MIN_PRIORITY; + + // Do we actually have to do anything? + if( Pri == Thread->Priority ) return; + #if SCHEDULER_TYPE == SCHED_RR_PRI + SHORTLOCK( &glThreadListLock ); + // Remove from old priority + Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ); + // And add to new + Thread->Next = gaActiveThreads[Pri]; + gaActiveThreads[Pri] = Thread; + Thread->Priority = Pri; + SHORTREL( &glThreadListLock ); + #else // If this isn't the current thread, we need to lock - if( Thread != Proc_GetCurThread() ) { + if( Thread != Proc_GetCurThread() ) + { SHORTLOCK( &glThreadListLock ); - giFreeTickets -= Thread->NumTickets - Num; - Thread->NumTickets = Num; - #if DEBUG_TRACE_TICKETS - Log("Threads_SetTickets: new giFreeTickets = %i", giFreeTickets); + + #if SCHEDULER_TYPE == SCHED_LOTTERY + giFreeTickets -= caiTICKET_COUNTS[Thread->Priority] - caiTICKET_COUNTS[Pri]; + # if DEBUG_TRACE_TICKETS + Log("Threads_SetTickets: new giFreeTickets = %i [-%i+%i]", + giFreeTickets, + caiTICKET_COUNTS[Thread->Priority], caiTICKET_COUNTS[Pri]); + # endif #endif + Thread->Priority = Pri; SHORTREL( &glThreadListLock ); } else - Thread->NumTickets = Num; + Thread->Priority = Pri; + #endif + + #if DEBUG_TRACE_STATE + Log("Threads_SetPriority: %p(%i %s) pri set %i", + Thread, Thread->TID, Thread->ThreadName, + Pri); + #endif } /** @@ -178,10 +247,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) // Allocate and duplicate new = malloc(sizeof(tThread)); - if(new == NULL) { - *Err = -ENOMEM; - return NULL; - } + if(new == NULL) { *Err = -ENOMEM; return NULL; } memcpy(new, cur, sizeof(tThread)); new->CurCPU = -1; @@ -193,6 +259,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) // Get Thread ID new->TID = giNextTID++; new->Parent = cur; + new->bInstrTrace = 0; // Clone Name new->ThreadName = strdup(cur->ThreadName); @@ -209,7 +276,7 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) // Set State new->Remaining = new->Quantum = cur->Quantum; - new->NumTickets = cur->NumTickets; + new->Priority = cur->Priority; // Set Signal Handlers new->CurFaultNum = 0; @@ -235,6 +302,77 @@ tThread *Threads_CloneTCB(Uint *Err, Uint Flags) SHORTLOCK( &glThreadListLock ); new->GlobalPrev = NULL; // Protect against bugs new->GlobalNext = gAllThreads; + gAllThreads->GlobalPrev = new; + gAllThreads = new; + SHORTREL( &glThreadListLock ); + + return new; +} + +/** + * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags) + * \brief Clone the TCB of the current thread + */ +tThread *Threads_CloneThreadZero(void) +{ + tThread *cur, *new; + int i; + cur = Proc_GetCurThread(); + + // Allocate and duplicate + new = malloc(sizeof(tThread)); + if(new == NULL) { + return NULL; + } + memcpy(new, &gThreadZero, sizeof(tThread)); + + new->CurCPU = -1; + new->Next = NULL; + memset( &new->IsLocked, 0, sizeof(new->IsLocked)); + new->Status = THREAD_STAT_PREINIT; + new->RetStatus = 0; + + // Get Thread ID + new->TID = giNextTID++; + new->Parent = 0; + + // Clone Name + new->ThreadName = NULL; + + // Messages are not inherited + new->Messages = NULL; + new->LastMessage = NULL; + + // Set State + new->Remaining = new->Quantum = cur->Quantum; + new->Priority = cur->Priority; + new->bInstrTrace = 0; + + // Set Signal Handlers + new->CurFaultNum = 0; + new->FaultHandler = cur->FaultHandler; + + for( i = 0; i < NUM_CFG_ENTRIES; i ++ ) + { + switch(cCONFIG_TYPES[i]) + { + default: + new->Config[i] = cur->Config[i]; + break; + case CFGT_HEAPSTR: + if(cur->Config[i]) + new->Config[i] = (Uint) strdup( (void*)cur->Config[i] ); + else + new->Config[i] = 0; + break; + } + } + + // Maintain a global list of threads + SHORTLOCK( &glThreadListLock ); + new->GlobalPrev = NULL; // Protect against bugs + new->GlobalNext = gAllThreads; + gAllThreads->GlobalPrev = new; gAllThreads = new; SHORTREL( &glThreadListLock ); @@ -420,17 +558,18 @@ void Threads_Exit(int TID, int Status) void Threads_Kill(tThread *Thread, int Status) { tMsg *msg; + int isCurThread = Thread == Proc_GetCurThread(); // TODO: Kill all children - #if 0 + #if 1 { tThread *child; // TODO: I should keep a .Parent pointer, and a .Children list - for(child = gActiveThreads; + for(child = gAllThreads; child; - child = child->Next) + child = child->GlobalNext) { - if(child->PTID == Thread->TID) + if(child->Parent == Thread) Threads_Kill(child, -1); } } @@ -452,23 +591,62 @@ void Threads_Kill(tThread *Thread, int Status) // Lock thread list SHORTLOCK( &glThreadListLock ); - // Delete from active list - if( !Threads_int_DelFromQueue( &gActiveThreads, Thread ) ) + switch(Thread->Status) { - Warning("Proc_Exit - Current thread is not on the active queue"); + case THREAD_STAT_PREINIT: // Only on main list + break; + + // Currently active thread + case THREAD_STAT_ACTIVE: + #if SCHEDULER_TYPE == SCHED_RR_PRI + if( Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ) ) + #else + if( Threads_int_DelFromQueue( &gActiveThreads, Thread ) ) + #endif + { + // Ensure that we are not rescheduled + Thread->Remaining = 0; // Clear Remaining Quantum + Thread->Quantum = 0; // Clear Quantum to indicate dead thread + + // Update bookkeeping + giNumActiveThreads --; + #if SCHEDULER_TYPE == SCHED_LOTTERY + if( Thread != Proc_GetCurThread() ) + giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ]; + #endif + } + else + { + Log_Warning("Threads", + "Threads_Kill - Thread %p(%i,%s) marked as active, but not on list", + Thread, Thread->TID, Thread->ThreadName + ); + } + break; + // Kill it while it sleeps! + case THREAD_STAT_SLEEPING: + if( !Threads_int_DelFromQueue( &gSleepingThreads, Thread ) ) + { + Log_Warning("Threads", + "Threads_Kill - Thread %p(%i,%s) marked as sleeping, but not on list", + Thread, Thread->TID, Thread->ThreadName + ); + } + break; + + // Brains!... You cannot kill + case THREAD_STAT_ZOMBIE: + Log_Warning("Threads", "Threads_Kill - Thread %p(%i,%s) is undead, you cannot kill it", + Thread, Thread->TID, Thread->ThreadName); SHORTREL( &glThreadListLock ); SHORTREL( &Thread->IsLocked ); - return; - } - - // Ensure that we are not rescheduled - Thread->Remaining = 0; // Clear Remaining Quantum - Thread->Quantum = 0; // Clear Quantum to indicate dead thread + return ; - // Update bookkeeping - giNumActiveThreads --; - if( Thread != Proc_GetCurThread() ) - giFreeTickets -= Thread->NumTickets; + default: + Log_Warning("Threads", "Threads_Kill - BUG Un-checked status (%i)", + Thread->Status); + break; + } // Save exit status Thread->RetStatus = Status; @@ -484,14 +662,14 @@ void Threads_Kill(tThread *Thread, int Status) Threads_Wake( Thread->Parent ); } - Log("Thread %i went *hurk* (%i)", Thread->TID, Thread->Status); + Log("Thread %i went *hurk* (%i)", Thread->TID, Status); // Release spinlocks SHORTREL( &glThreadListLock ); SHORTREL( &Thread->IsLocked ); // TODO: We may not actually be released... // And, reschedule - if(Status != -1) { + if(isCurThread) { for( ;; ) HALT(); } @@ -561,7 +739,7 @@ int Threads_Wake(tThread *Thread) switch(Thread->Status) { case THREAD_STAT_ACTIVE: - Log("Thread_Wake: Waking awake thread (%i)", Thread->TID); + Log("Threads_Wake - Waking awake thread (%i)", Thread->TID); return -EALREADY; case THREAD_STAT_SLEEPING: @@ -577,16 +755,66 @@ int Threads_Wake(tThread *Thread) SHORTREL( &glThreadListLock ); return -EOK; + case THREAD_STAT_SEMAPHORESLEEP: { + tSemaphore *sem; + tThread *th, *prev=NULL; + + sem = Thread->WaitPointer; + + SHORTLOCK( &sem->Protector ); + + // Remove from sleeping queue + for( th = sem->Waiting; th; prev = th, th = th->Next ) + if( th == Thread ) break; + if( th ) + { + if(prev) + prev->Next = Thread->Next; + else + sem->Waiting = Thread->Next; + if(sem->LastWaiting == Thread) + sem->LastWaiting = prev; + } + else + { + prev = NULL; + for( th = sem->Signaling; th; prev = th, th = th->Next ) + if( th == Thread ) break; + if( !th ) { + Log_Warning("Threads", "Thread %p(%i %s) is not on semaphore %p(%s:%s)", + Thread, Thread->TID, Thread->ThreadName, + sem, sem->ModName, sem->Name); + return -EINTERNAL; + } + + if(prev) + prev->Next = Thread->Next; + else + sem->Signaling = Thread->Next; + if(sem->LastSignaling == Thread) + sem->LastSignaling = prev; + } + + SHORTLOCK( &glThreadListLock ); + Threads_AddActive( Thread ); + SHORTREL( &glThreadListLock ); + + #if DEBUG_TRACE_STATE + Log("Threads_Sleep: %p(%i %s) woken from semaphore", Thread, Thread->TID, Thread->ThreadName); + #endif + SHORTREL( &sem->Protector ); + } return -EOK; + case THREAD_STAT_WAITING: - Warning("Thread_Wake - Waiting threads are not currently supported"); + Warning("Threads_Wake - Waiting threads are not currently supported"); return -ENOTIMPL; case THREAD_STAT_DEAD: - Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID); + Warning("Threads_Wake - Attempt to wake dead thread (%i)", Thread->TID); return -ENOTIMPL; default: - Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status); + Warning("Threads_Wake - Unknown process status (%i)\n", Thread->Status); return -EINTERNAL; } } @@ -607,6 +835,13 @@ int Threads_WakeTID(tTID TID) return ret; } +void Threads_ToggleTrace(int TID) +{ + tThread *thread = Threads_GetThread(TID); + if(!thread) return ; + thread->bInstrTrace = !thread->bInstrTrace; +} + /** * \brief Adds a thread to the active queue */ @@ -614,39 +849,48 @@ void Threads_AddActive(tThread *Thread) { SHORTLOCK( &glThreadListLock ); - #if 1 - { - tThread *t; - for( t = gActiveThreads; t; t = t->Next ) - { - if( t == Thread ) { - Panic("Threads_AddActive: Attempting a double add of TID %i (0x%x)", - Thread->TID, __builtin_return_address(0)); - } - - if(t->Status != THREAD_STAT_ACTIVE) { - Panic("Threads_AddActive: TID %i status != THREAD_STAT_ACTIVE", - Thread->TID); - } - } + if( Thread->Status == THREAD_STAT_ACTIVE ) { + tThread *cur = Proc_GetCurThread(); + Warning("WTF, CPU%i %p (%i %s) is adding %p (%i %s) when it is active", + GetCPUNum(), cur, cur->TID, cur->ThreadName, Thread, Thread->TID, Thread->ThreadName); + SHORTREL( &glThreadListLock ); + return ; } - #endif // Set state Thread->Status = THREAD_STAT_ACTIVE; - Thread->CurCPU = -1; +// Thread->CurCPU = -1; // Add to active list + #if SCHEDULER_TYPE == SCHED_RR_PRI + Thread->Next = gaActiveThreads[Thread->Priority]; + gaActiveThreads[Thread->Priority] = Thread; + #else Thread->Next = gActiveThreads; gActiveThreads = Thread; + #endif // Update bookkeeping giNumActiveThreads ++; - giFreeTickets += Thread->NumTickets; - #if DEBUG_TRACE_TICKETS - Log("Threads_AddActive: %p %i (%s) added, new giFreeTickets = %i", - Thread, Thread->TID, Thread->ThreadName, giFreeTickets); + #if SCHEDULER_TYPE == SCHED_LOTTERY + { + int delta; + // Only change the ticket count if the thread is un-scheduled + if(Thread->CurCPU != -1) + delta = 0; + else + delta = caiTICKET_COUNTS[ Thread->Priority ]; + + giFreeTickets += delta; + # if DEBUG_TRACE_TICKETS + Log("CPU%i %p (%i %s) added, new giFreeTickets = %i [+%i]", + GetCPUNum(), Thread, Thread->TID, Thread->ThreadName, + giFreeTickets, delta + ); + # endif + } #endif + SHORTREL( &glThreadListLock ); } @@ -662,20 +906,28 @@ tThread *Threads_RemActive(void) SHORTLOCK( &glThreadListLock ); // Delete from active queue - if( !Threads_int_DelFromQueue(&gActiveThreads, ret) ) { + #if SCHEDULER_TYPE == SCHED_RR_PRI + if( !Threads_int_DelFromQueue(&gaActiveThreads[ret->Priority], ret) ) + #else + if( !Threads_int_DelFromQueue(&gActiveThreads, ret) ) + #endif + { SHORTREL( &glThreadListLock ); + Log_Warning("Threads", "Current thread %p(%i %s) is not on active queue", + ret, ret->TID, ret->ThreadName + ); return NULL; } + ret->Next = NULL; ret->Remaining = 0; - ret->CurCPU = -1; giNumActiveThreads --; // no need to decrement tickets, scheduler did it for us - #if DEBUG_TRACE_TICKETS - Log("Threads_RemActive: %p %i (%s) removed, giFreeTickets = %i", - ret, ret->TID, ret->ThreadName, giFreeTickets); + #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS + Log("CPU%i %p (%i %s) removed, giFreeTickets = %i [nc]", + GetCPUNum(), ret, ret->TID, ret->ThreadName, giFreeTickets); #endif SHORTREL( &glThreadListLock ); @@ -701,8 +953,6 @@ void Threads_Fault(int Num) { tThread *thread = Proc_GetCurThread(); - Log_Log("Threads", "Threads_Fault: thread = %p", thread); - if(!thread) return ; Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler); @@ -730,6 +980,17 @@ void Threads_Fault(int Num) Proc_CallFaultHandler(thread); } +/** + * \fn void Threads_SegFault(tVAddr Addr) + * \brief Called when a Segment Fault occurs + */ +void Threads_SegFault(tVAddr Addr) +{ + Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr); + Threads_Fault( 1 ); + //Threads_Exit( 0, -1 ); +} + // --- Process Structure Access Functions --- tPID Threads_GetPID(void) { @@ -774,50 +1035,79 @@ int Threads_SetGID(Uint *Errno, tGID ID) /** * \fn void Threads_Dump(void) - * \brief Dumps a list of currently running threads */ -void Threads_Dump(void) +void Threads_DumpActive(void) { tThread *thread; + #if SCHEDULER_TYPE == SCHED_RR_PRI + int i; + #endif - Log("--- Thread Dump ---"); Log("Active Threads: (%i reported)", giNumActiveThreads); - for(thread=gActiveThreads;thread;thread=thread->Next) - { - Log(" %i (%i) - %s (CPU %i)", - thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); - if(thread->Status != THREAD_STAT_ACTIVE) - Log(" ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE); - Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum); - Log(" KStack 0x%x", thread->KernelStack); - } - Log("All Threads:"); - for(thread=gAllThreads;thread;thread=thread->GlobalNext) + #if SCHEDULER_TYPE == SCHED_RR_PRI + for( i = 0; i < MIN_PRIORITY+1; i++ ) { - Log(" %i (%i) - %s (CPU %i)", - thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); - Log(" State %i", thread->Status); - Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum); - Log(" KStack 0x%x", thread->KernelStack); + for(thread=gaActiveThreads[i];thread;thread=thread->Next) + #else + for(thread=gActiveThreads;thread;thread=thread->Next) + #endif + { + Log(" %p %i (%i) - %s (CPU %i)", + thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); + if(thread->Status != THREAD_STAT_ACTIVE) + Log(" ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE); + Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum); + Log(" KStack 0x%x", thread->KernelStack); + if( thread->bInstrTrace ) + Log(" Tracing Enabled"); + Proc_DumpThreadCPUState(thread); + } + + #if SCHEDULER_TYPE == SCHED_RR_PRI } + #endif } + /** * \fn void Threads_Dump(void) + * \brief Dumps a list of currently running threads */ -void Threads_DumpActive(void) +void Threads_Dump(void) { tThread *thread; - Log("Active Threads:"); - for(thread=gActiveThreads;thread;thread=thread->Next) + Log("--- Thread Dump ---"); + Threads_DumpActive(); + + Log("All Threads:"); + for(thread=gAllThreads;thread;thread=thread->GlobalNext) { - Log(" %i (%i) - %s (CPU %i)", - thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); - if(thread->Status != THREAD_STAT_ACTIVE) - Log(" ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE); - Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum); + Log(" %p %i (%i) - %s (CPU %i)", + thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU); + Log(" State %i (%s)", thread->Status, casTHREAD_STAT[thread->Status]); + switch(thread->Status) + { + case THREAD_STAT_MUTEXSLEEP: + Log(" Mutex Pointer: %p", thread->WaitPointer); + break; + case THREAD_STAT_SEMAPHORESLEEP: + Log(" Semaphore Pointer: %p", thread->WaitPointer); + Log(" Semaphore Name: %s:%s", + ((tSemaphore*)thread->WaitPointer)->ModName, + ((tSemaphore*)thread->WaitPointer)->Name + ); + 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); + if( thread->bInstrTrace ) + Log(" Tracing Enabled"); + Proc_DumpThreadCPUState(thread); } } @@ -829,8 +1119,6 @@ void Threads_DumpActive(void) tThread *Threads_GetNextToRun(int CPU, tThread *Last) { tThread *thread; - int ticket; - int number; // If this CPU has the lock, we must let it complete if( CPU_HAS_LOCK( &glThreadListLock ) ) @@ -846,12 +1134,16 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) // Clear Delete Queue // - I should probably put this in a worker thread to avoid calling free() in the scheduler + // DEFINITELY - free() can deadlock in this case + // I'll do it when it becomes an issue while(gDeleteThreads) { thread = gDeleteThreads->Next; - if( IS_LOCKED(&gDeleteThreads->IsLocked) ) { // Only free if structure is unused + // Only free if structure is unused + if( !IS_LOCKED(&gDeleteThreads->IsLocked) ) + { // Set to dead - gDeleteThreads->Status = THREAD_STAT_DEAD; + gDeleteThreads->Status = THREAD_STAT_BURIED; // Free name if( IsHeap(gDeleteThreads->ThreadName) ) free(gDeleteThreads->ThreadName); @@ -864,7 +1156,10 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) } gDeleteThreads = thread; } - + + // 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 ); @@ -874,6 +1169,7 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) return NULL; } + #if SCHEDULER_TYPE != SCHED_RR_PRI // Special case: 1 thread if(giNumActiveThreads == 1) { if( gActiveThreads->CurCPU == -1 ) @@ -886,115 +1182,162 @@ tThread *Threads_GetNextToRun(int CPU, tThread *Last) return NULL; // CPU has nothing to do } + #endif // Allow the old thread to be scheduled again if( Last ) { if( Last->Status == THREAD_STAT_ACTIVE ) { - giFreeTickets += Last->NumTickets; - #if DEBUG_TRACE_TICKETS - LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n", - CPU, Last, Last->TID, Last->ThreadName, giFreeTickets); + #if SCHEDULER_TYPE == SCHED_LOTTERY + giFreeTickets += caiTICKET_COUNTS[ Last->Priority ]; + # if DEBUG_TRACE_TICKETS + LogF("Log: CPU%i released %p (%i %s) into the pool (%i [+%i] tickets in pool)\n", + CPU, Last, Last->TID, Last->ThreadName, giFreeTickets, + caiTICKET_COUNTS[ Last->Priority ]); + # endif #endif } - #if DEBUG_TRACE_TICKETS + #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS else - LogF(" CPU %i released %p (%i %s)->Status = %i (Released)\n", + LogF("Log: CPU%i released %p (%i %s)->Status = %i (Released,not in pool)\n", CPU, Last, Last->TID, Last->ThreadName, Last->Status); #endif Last->CurCPU = -1; } - #if DEBUG_TRACE_TICKETS - //Threads_DumpActive(); - #endif - - #if 1 - number = 0; - for(thread = gActiveThreads; thread; thread = thread->Next) { - if(thread->CurCPU >= 0) continue; - 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); + // --- + // Lottery Scheduler + // --- + #if SCHEDULER_TYPE == SCHED_LOTTERY + { + int ticket, number; + # if 1 + number = 0; + for(thread = gActiveThreads; thread; thread = thread->Next) { + if(thread->CurCPU >= 0) continue; + 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 ]; } - number += thread->NumTickets; - } - 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; + 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;thread;thread=thread->Next) + { + if(thread->CurCPU >= 0) continue; + 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); + } + + 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 } - // Get the ticket number - ticket = number = rand() % giFreeTickets; - - // Find the next thread - for(thread=gActiveThreads;thread;thread=thread->Next) + // --- + // Priority based round robin scheduler + // --- + #elif SCHEDULER_TYPE == SCHED_RR_PRI { - if(thread->CurCPU >= 0) continue; - if(thread->NumTickets > number) break; - number -= thread->NumTickets; + int i; + for( i = 0; i < MIN_PRIORITY + 1; i ++ ) + { + for(thread = gaActiveThreads[i]; thread; thread = thread->Next) + { + if( thread->CurCPU == -1 ) break; + } + // If we fall onto the same queue again, special handling is + // needed + if( i == Last->Priority ) { + tThread *savedThread = thread; + + // Find the next unscheduled thread in the list + for( thread = Last->Next; thread; thread = thread->Next ) + { + if( thread->CurCPU == -1 ) break; + } + // If we don't find anything after, just use the one + // found above. + if( !thread ) thread = savedThread; + } + // Found a thread? Schedule it! + if( thread ) break; + } + + // Anything to do? + if( !thread ) { + SHORTREL(&glThreadListLock); + return NULL; + } } - // Error Check - if(thread == NULL) - { - number = 0; - for(thread=gActiveThreads;thread;thread=thread->Next) { - if(thread->CurCPU >= 0) continue; - number += thread->NumTickets; + #elif SCHEDULER_TYPE == SCHED_RR_SIM + { + // Find the next unscheduled thread in the list + for( thread = Last->Next; thread; thread = thread->Next ) + { + if( thread->CurCPU == -1 ) break; + } + // If we don't find anything after, search from the beginning + if( !thread ) + { + for(thread = gActiveThreads; thread; thread = thread->Next) + { + if( thread->CurCPU == -1 ) break; + } + } + + // Anything to do? + if( !thread ) { + SHORTREL(&glThreadListLock); + return NULL; } - Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)", - giFreeTickets, number); } - #if DEBUG_TRACE_TICKETS - LogF(" CPU%i giFreeTickets = %i\n", CPU, giFreeTickets); + #else + # error "Unimplemented scheduling algorithm" #endif // Make the new thread non-schedulable - giFreeTickets -= thread->NumTickets; thread->CurCPU = CPU; - //Threads_Dump(); - #if DEBUG_TRACE_TICKETS - LogF(" CPU%i giFreeTickets = %i, giving %p (%i %s CPU=%i)\n", - CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU); - #endif - SHORTREL( &glThreadListLock ); return thread; } -/** - * \fn void Threads_SegFault(tVAddr Addr) - * \brief Called when a Segment Fault occurs - */ -void Threads_SegFault(tVAddr Addr) -{ - Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr); - Threads_Fault( 1 ); - //Threads_Exit( 0, -1 ); -} - -/** - * \brief Acquire a heavy mutex - * \param Mutex Mutex to acquire - * - * This type of mutex checks if the mutex is avaliable, and acquires it - * if it is. Otherwise, the current thread is added to the mutex's wait - * queue and the thread suspends. When the holder of the mutex completes, - * the oldest thread (top thread) on the queue is given the lock and - * restarted. - */ -void Mutex_Acquire(tMutex *Mutex) +// Acquire mutex (see mutex.h for documentation) +int Mutex_Acquire(tMutex *Mutex) { tThread *us = Proc_GetCurThread(); @@ -1008,8 +1351,10 @@ void Mutex_Acquire(tMutex *Mutex) SHORTLOCK( &glThreadListLock ); // - Remove from active list us = Threads_RemActive(); + us->Next = NULL; // - Mark as sleeping - us->Status = THREAD_STAT_OFFSLEEP; + us->Status = THREAD_STAT_MUTEXSLEEP; + us->WaitPointer = Mutex; // - Add to waiting if(Mutex->LastWaiting) { @@ -1020,22 +1365,44 @@ void Mutex_Acquire(tMutex *Mutex) Mutex->Waiting = us; Mutex->LastWaiting = us; } + + #if DEBUG_TRACE_STATE + Log("%p (%i %s) waiting on mutex %p", + us, us->TID, us->ThreadName, Mutex); + #endif + + #if 0 + { + int i = 0; + tThread *t; + for( t = Mutex->Waiting; t; t = t->Next, i++ ) + Log("[%i] (tMutex)%p->Waiting[%i] = %p (%i %s)", us->TID, Mutex, i, + t, t->TID, t->ThreadName); + } + #endif + SHORTREL( &glThreadListLock ); SHORTREL( &Mutex->Protector ); - while(us->Status == THREAD_STAT_OFFSLEEP) Threads_Yield(); + while(us->Status == THREAD_STAT_MUTEXSLEEP) Threads_Yield(); // We're only woken when we get the lock + us->WaitPointer = NULL; } // Ooh, let's take it! else { Mutex->Owner = us; SHORTREL( &Mutex->Protector ); } + + #if 0 + extern tMutex glPhysAlloc; + if( Mutex != &glPhysAlloc ) + LogF("Mutex %p taken by %i %p\n", Mutex, us->TID, __builtin_return_address(0)); + #endif + + return 0; } -/** - * \brief Release a held mutex - * \param Mutex Mutex to release - */ +// Release a mutex void Mutex_Release(tMutex *Mutex) { SHORTLOCK( &Mutex->Protector ); @@ -1060,20 +1427,262 @@ void Mutex_Release(tMutex *Mutex) Mutex->Owner = NULL; } SHORTREL( &Mutex->Protector ); + + #if 0 + extern tMutex glPhysAlloc; + if( Mutex != &glPhysAlloc ) + LogF("Mutex %p released by %i %p\n", Mutex, Threads_GetTID(), __builtin_return_address(0)); + #endif } -/** - * \brief Is this mutex locked? - * \param Mutex Mutex pointer - */ +// Check if a mutex is locked int Mutex_IsLocked(tMutex *Mutex) { return Mutex->Owner != NULL; } +// +// Initialise a semaphore +// +void Semaphore_Init(tSemaphore *Sem, int Value, int MaxValue, const char *Module, const char *Name) +{ + memset(Sem, 0, sizeof(tSemaphore)); + Sem->Value = Value; + Sem->ModName = Module; + Sem->Name = Name; + Sem->MaxValue = MaxValue; +} +// +// Wait for items to be avaliable +// +int Semaphore_Wait(tSemaphore *Sem, int MaxToTake) +{ + tThread *us; + int taken; + if( MaxToTake < 0 ) { + Log_Warning("Threads", "Semaphore_Wait: User bug - MaxToTake(%i) < 0, Sem=%p(%s)", + MaxToTake, Sem, Sem->Name); + } + + SHORTLOCK( &Sem->Protector ); + + // Check if there's already items avaliable + if( Sem->Value > 0 ) { + // Take what we need + if( MaxToTake && Sem->Value > MaxToTake ) + taken = MaxToTake; + else + taken = Sem->Value; + Sem->Value -= taken; + SHORTREL( &Sem->Protector ); + } + else + { + SHORTLOCK( &glThreadListLock ); + + // - Remove from active list + us = Threads_RemActive(); + us->Next = NULL; + // - Mark as sleeping + us->Status = THREAD_STAT_SEMAPHORESLEEP; + us->WaitPointer = Sem; + us->RetStatus = MaxToTake; // Use RetStatus as a temp variable + + // - Add to waiting + if(Sem->LastWaiting) { + Sem->LastWaiting->Next = us; + Sem->LastWaiting = us; + } + else { + Sem->Waiting = us; + Sem->LastWaiting = us; + } + + #if DEBUG_TRACE_STATE || SEMAPHORE_DEBUG + Log("%p (%i %s) waiting on semaphore %p %s:%s", + us, us->TID, us->ThreadName, + Sem, Sem->ModName, Sem->Name); + #endif + + SHORTREL( &Sem->Protector ); // Release first to make sure it is released + SHORTREL( &glThreadListLock ); + while(us->Status == THREAD_STAT_SEMAPHORESLEEP) Threads_Yield(); + // We're only woken when there's something avaliable (or a signal arrives) + us->WaitPointer = NULL; + + taken = us->RetStatus; + + // Get the lock again + SHORTLOCK( &Sem->Protector ); + } + + // While there is space, and there are thread waiting + // wake the first thread and give it what it wants (or what's left) + while( (Sem->MaxValue == 0 || Sem->Value < Sem->MaxValue) && Sem->Signaling ) + { + int given; + tThread *toWake = Sem->Signaling; + + Sem->Signaling = Sem->Signaling->Next; + // Reset ->LastWaiting to NULL if we have just removed the last waiting thread + if( Sem->Signaling == NULL ) + Sem->LastSignaling = NULL; + + // Figure out how much to give + if( toWake->RetStatus && Sem->Value + toWake->RetStatus < Sem->MaxValue ) + given = toWake->RetStatus; + else + given = Sem->MaxValue - Sem->Value; + Sem->Value -= given; + + + #if DEBUG_TRACE_STATE || SEMAPHORE_DEBUG + Log("%p (%i %s) woken by wait on %p %s:%s", + toWake, toWake->TID, toWake->ThreadName, + Sem, Sem->ModName, Sem->Name); + #endif + + // Save the number we gave to the thread's status + toWake->RetStatus = given; + + // Wake the sleeper + SHORTLOCK( &glThreadListLock ); + if( toWake->Status != THREAD_STAT_ACTIVE ) + Threads_AddActive(toWake); + SHORTREL( &glThreadListLock ); + } + SHORTREL( &Sem->Protector ); + + return taken; +} + +// +// Add items to a semaphore +// +int Semaphore_Signal(tSemaphore *Sem, int AmmountToAdd) +{ + int given; + int added; + + if( AmmountToAdd < 0 ) { + Log_Warning("Threads", "Semaphore_Signal: User bug - AmmountToAdd(%i) < 0, Sem=%p(%s)", + AmmountToAdd, Sem, Sem->Name); + } + SHORTLOCK( &Sem->Protector ); + + // Check if we have to block + if( Sem->MaxValue && Sem->Value == Sem->MaxValue ) + { + tThread *us; + #if 0 + Log_Debug("Threads", "Semaphore_Signal: IDLE Sem = %s:%s", Sem->ModName, Sem->Name); + Log_Debug("Threads", "Semaphore_Signal: Sem->Value(%i) == Sem->MaxValue(%i)", Sem->Value, Sem->MaxValue); + #endif + + SHORTLOCK( &glThreadListLock ); + // - Remove from active list + us = Threads_RemActive(); + us->Next = NULL; + // - Mark as sleeping + us->Status = THREAD_STAT_SEMAPHORESLEEP; + us->WaitPointer = Sem; + us->RetStatus = AmmountToAdd; // Use RetStatus as a temp variable + + // - Add to waiting + if(Sem->LastSignaling) { + Sem->LastSignaling->Next = us; + Sem->LastSignaling = us; + } + else { + Sem->Signaling = us; + Sem->LastSignaling = us; + } + + #if DEBUG_TRACE_STATE || SEMAPHORE_DEBUG + Log("%p (%i %s) signaling semaphore %p %s:%s", + us, us->TID, us->ThreadName, + Sem, Sem->ModName, Sem->Name); + #endif + + SHORTREL( &glThreadListLock ); + SHORTREL( &Sem->Protector ); + while(us->Status == THREAD_STAT_SEMAPHORESLEEP) Threads_Yield(); + // We're only woken when there's something avaliable + us->WaitPointer = NULL; + + added = us->RetStatus; + + // Get the lock again + SHORTLOCK( &Sem->Protector ); + } + // Non blocking + else + { + // Figure out how much we need to take off + if( Sem->MaxValue && Sem->Value + AmmountToAdd > Sem->MaxValue) + added = Sem->MaxValue - Sem->Value; + else + added = AmmountToAdd; + Sem->Value += added; + } + + // While there are items avaliable, and there are thread waiting + // wake the first thread and give it what it wants (or what's left) + while( Sem->Value && Sem->Waiting ) + { + tThread *toWake = Sem->Waiting; + + // Remove thread from list (double ended, so clear LastWaiting if needed) + Sem->Waiting = Sem->Waiting->Next; + if( Sem->Waiting == NULL ) + Sem->LastWaiting = NULL; + + // Figure out how much to give to woken thread + // - Requested count is stored in ->RetStatus + if( toWake->RetStatus && Sem->Value > toWake->RetStatus ) + given = toWake->RetStatus; + else + given = Sem->Value; + Sem->Value -= given; + + // Save the number we gave to the thread's status + toWake->RetStatus = given; + + if(toWake->bInstrTrace) + Log("%s(%i) given %i from %p", toWake->ThreadName, toWake->TID, given, Sem); + #if DEBUG_TRACE_STATE || SEMAPHORE_DEBUG + Log("%p (%i %s) woken by signal on %p %s:%s", + toWake, toWake->TID, toWake->ThreadName, + Sem, Sem->ModName, Sem->Name); + #endif + + // Wake the sleeper + SHORTLOCK( &glThreadListLock ); + if( toWake->Status != THREAD_STAT_ACTIVE ) + Threads_AddActive(toWake); + else + Warning("Thread %p (%i %s) is already awake", toWake, toWake->TID, toWake->ThreadName); + SHORTREL( &glThreadListLock ); + } + SHORTREL( &Sem->Protector ); + + return added; +} + +// +// Get the current value of a semaphore +// +int Semaphore_GetValue(tSemaphore *Sem) +{ + return Sem->Value; +} + // === EXPORTS === EXPORT(Threads_GetUID); EXPORT(Threads_GetGID); EXPORT(Mutex_Acquire); EXPORT(Mutex_Release); EXPORT(Mutex_IsLocked); +EXPORT(Semaphore_Init); +EXPORT(Semaphore_Wait); +EXPORT(Semaphore_Signal);