4 * - Common Thread Control
12 #define DEBUG_TRACE_TICKETS 0 // Trace ticket counts
13 #define DEBUG_TRACE_STATE 0 // Trace state changes (sleep/wake)
17 #define SCHED_LOTTERY 1 // Lottery scheduler
18 #define SCHED_RR_SIM 2 // Single Queue Round Robin
19 #define SCHED_RR_PRI 3 // Multi Queue Round Robin
21 #define SCHEDULER_TYPE SCHED_LOTTERY
24 #define DEFAULT_QUANTUM 10
25 #define DEFAULT_PRIORITY 5
26 #define MIN_PRIORITY 10
27 const enum eConfigTypes cCONFIG_TYPES[] = {
28 CFGT_HEAPSTR, // e.g. CFG_VFS_CWD
29 CFGT_INT, // e.g. CFG_VFS_MAXFILES
34 extern void ArchThreads_Init(void);
35 extern void Proc_Start(void);
36 extern tThread *Proc_GetCurThread(void);
37 extern int Proc_Clone(Uint *Err, Uint Flags);
38 extern void Proc_CallFaultHandler(tThread *Thread);
39 extern int GetCPUNum(void);
42 void Threads_Init(void);
43 int Threads_SetName(const char *NewName);
44 char *Threads_GetName(int ID);
45 void Threads_SetPriority(tThread *Thread, int Pri);
46 tThread *Threads_CloneTCB(Uint *Err, Uint Flags);
47 int Threads_WaitTID(int TID, int *status);
48 tThread *Threads_GetThread(Uint TID);
49 void Threads_AddToDelete(tThread *Thread);
50 tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread);
51 void Threads_Exit(int TID, int Status);
52 void Threads_Kill(tThread *Thread, int Status);
53 void Threads_Yield(void);
54 void Threads_Sleep(void);
55 int Threads_Wake(tThread *Thread);
56 void Threads_AddActive(tThread *Thread);
57 tThread *Threads_RemActive(void);
58 int Threads_GetPID(void);
59 int Threads_GetTID(void);
60 tUID Threads_GetUID(void);
61 int Threads_SetUID(Uint *Errno, tUID ID);
62 tGID Threads_GetGID(void);
63 int Threads_SetGID(Uint *Errno, tUID ID);
64 void Threads_Dump(void);
65 void Threads_DumpActive(void);
67 int Mutex_Acquire(tMutex *Mutex);
68 void Mutex_Release(tMutex *Mutex);
69 int Mutex_IsLocked(tMutex *Mutex);
73 // Only used for the core kernel
74 tThread gThreadZero = {
75 Status: THREAD_STAT_ACTIVE, // Status
76 ThreadName: "ThreadZero", // Name
77 Quantum: DEFAULT_QUANTUM, // Default Quantum
78 Remaining: DEFAULT_QUANTUM, // Current Quantum
79 Priority: DEFAULT_PRIORITY // Number of tickets
83 tShortSpinlock glThreadListLock; ///\note NEVER use a heap function while locked
84 // --- Current State ---
85 volatile int giNumActiveThreads = 0; // Number of threads on the active queue
86 volatile Uint giNextTID = 1; // Next TID to allocate
87 // --- Thread Lists ---
88 tThread *gAllThreads = NULL; // All allocated threads
89 tThread *gSleepingThreads = NULL; // Sleeping Threads
90 tThread *gDeleteThreads = NULL; // Threads to delete
91 int giNumCPUs = 1; // Number of CPUs
92 BOOL gaThreads_NoTaskSwitch[MAX_CPUS]; // Disables task switches for each core (Pseudo-IF)
93 // --- Scheduler Types ---
94 #if SCHEDULER_TYPE == SCHED_LOTTERY
95 const int caiTICKET_COUNTS[MIN_PRIORITY+1] = {100,81,64,49,36,25,16,9,4,1,0};
96 volatile int giFreeTickets = 0; // Number of tickets held by non-scheduled threads
97 tThread *gActiveThreads = NULL; // Currently Running Threads
98 #elif SCHEDULER_TYPE == SCHED_RR_SIM
99 tThread *gActiveThreads = NULL; // Currently Running Threads
100 #elif SCHEDULER_TYPE == SCHED_RR_PRI
101 tThread *gaActiveThreads[MIN_PRIORITY+1]; // Active threads for each priority level
103 # error "Unkown scheduler type"
108 * \fn void Threads_Init(void)
109 * \brief Initialse the thread list
111 void Threads_Init(void)
115 // Create Initial Task
116 #if SCHEDULER_TYPE == SCHED_RR_PRI
117 gaActiveThreads[gThreadZero.Priority] = &gThreadZero;
119 gActiveThreads = &gThreadZero;
122 gAllThreads = &gThreadZero;
123 giNumActiveThreads = 1;
129 * \fn void Threads_SetName(const char *NewName)
130 * \brief Sets the current thread's name
131 * \param NewName New name for the thread
132 * \return Boolean Failure
134 int Threads_SetName(const char *NewName)
136 tThread *cur = Proc_GetCurThread();
137 char *oldname = cur->ThreadName;
139 // NOTE: There is a possibility of non-thread safety here
140 // A thread could read the current name pointer before it is zeroed
142 cur->ThreadName = NULL;
144 if( IsHeap(oldname) ) free( oldname );
146 cur->ThreadName = strdup(NewName);
151 * \fn char *Threads_GetName(int ID)
152 * \brief Gets a thread's name
153 * \param ID Thread ID (-1 indicates current thread)
154 * \return Pointer to name
155 * \retval NULL Failure
157 char *Threads_GetName(tTID ID)
160 return Proc_GetCurThread()->ThreadName;
162 return Threads_GetThread(ID)->ThreadName;
166 * \fn void Threads_SetPriority(tThread *Thread, int Pri)
167 * \brief Sets the priority of a task
168 * \param Thread Thread to update ticket count (NULL means current thread)
169 * \param Pri New priority
171 void Threads_SetPriority(tThread *Thread, int Pri)
173 // Get current thread
174 if(Thread == NULL) Thread = Proc_GetCurThread();
176 // - If < 0, set to lowest priority
177 if(Pri < 0) Pri = MIN_PRIORITY;
178 if(Pri > MIN_PRIORITY) Pri = MIN_PRIORITY;
180 // Do we actually have to do anything?
181 if( Pri == Thread->Priority ) return;
183 #if SCHEDULER_TYPE == SCHED_RR_PRI
184 SHORTLOCK( &glThreadListLock );
185 // Remove from old priority
186 Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread );
188 Thread->Next = gaActiveThreads[Pri];
189 gaActiveThreads[Pri] = Thread;
190 Thread->Priority = Pri;
191 SHORTREL( &glThreadListLock );
193 // If this isn't the current thread, we need to lock
194 if( Thread != Proc_GetCurThread() )
196 SHORTLOCK( &glThreadListLock );
198 #if SCHEDULER_TYPE == SCHED_LOTTERY
199 giFreeTickets -= caiTICKET_COUNTS[Thread->Priority] - caiTICKET_COUNTS[Pri];
200 # if DEBUG_TRACE_TICKETS
201 Log("Threads_SetTickets: new giFreeTickets = %i", giFreeTickets);
204 Thread->Priority = Pri;
205 SHORTREL( &glThreadListLock );
208 Thread->Priority = Pri;
213 * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
214 * \brief Clone the TCB of the current thread
215 * \param Err Error pointer
216 * \param Flags Flags for something... (What is this for?)
218 tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
222 cur = Proc_GetCurThread();
224 // Allocate and duplicate
225 new = malloc(sizeof(tThread));
230 memcpy(new, cur, sizeof(tThread));
234 memset( &new->IsLocked, 0, sizeof(new->IsLocked));
235 new->Status = THREAD_STAT_PREINIT;
239 new->TID = giNextTID++;
243 new->ThreadName = strdup(cur->ThreadName);
245 // Set Thread Group ID (PID)
247 new->TGID = new->TID;
249 new->TGID = cur->TGID;
251 // Messages are not inherited
252 new->Messages = NULL;
253 new->LastMessage = NULL;
256 new->Remaining = new->Quantum = cur->Quantum;
257 new->Priority = cur->Priority;
259 // Set Signal Handlers
260 new->CurFaultNum = 0;
261 new->FaultHandler = cur->FaultHandler;
263 for( i = 0; i < NUM_CFG_ENTRIES; i ++ )
265 switch(cCONFIG_TYPES[i])
268 new->Config[i] = cur->Config[i];
272 new->Config[i] = (Uint) strdup( (void*)cur->Config[i] );
279 // Maintain a global list of threads
280 SHORTLOCK( &glThreadListLock );
281 new->GlobalPrev = NULL; // Protect against bugs
282 new->GlobalNext = gAllThreads;
283 gAllThreads->GlobalPrev = new;
285 SHORTREL( &glThreadListLock );
291 * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
292 * \brief Clone the TCB of the current thread
294 tThread *Threads_CloneThreadZero(void)
298 cur = Proc_GetCurThread();
300 // Allocate and duplicate
301 new = malloc(sizeof(tThread));
305 memcpy(new, &gThreadZero, sizeof(tThread));
309 memset( &new->IsLocked, 0, sizeof(new->IsLocked));
310 new->Status = THREAD_STAT_PREINIT;
314 new->TID = giNextTID++;
318 new->ThreadName = NULL;
320 // Messages are not inherited
321 new->Messages = NULL;
322 new->LastMessage = NULL;
325 new->Remaining = new->Quantum = cur->Quantum;
326 new->Priority = cur->Priority;
328 // Set Signal Handlers
329 new->CurFaultNum = 0;
330 new->FaultHandler = cur->FaultHandler;
332 for( i = 0; i < NUM_CFG_ENTRIES; i ++ )
334 switch(cCONFIG_TYPES[i])
337 new->Config[i] = cur->Config[i];
341 new->Config[i] = (Uint) strdup( (void*)cur->Config[i] );
348 // Maintain a global list of threads
349 SHORTLOCK( &glThreadListLock );
350 new->GlobalPrev = NULL; // Protect against bugs
351 new->GlobalNext = gAllThreads;
352 gAllThreads->GlobalPrev = new;
354 SHORTREL( &glThreadListLock );
360 * \brief Get a configuration pointer from the Per-Thread data area
361 * \param ID Config slot ID
362 * \return Pointer at ID
364 Uint *Threads_GetCfgPtr(int ID)
366 if(ID < 0 || ID >= NUM_CFG_ENTRIES) {
367 Warning("Threads_GetCfgPtr: Index %i is out of bounds", ID);
371 return &Proc_GetCurThread()->Config[ID];
375 * \brief Wait for a task to change state
376 * \param TID Thread ID to wait on (-1: Any child thread, 0: Any Child/Sibling, <-1: -PID)
377 * \param Status Thread return status
378 * \return TID of child that changed state
380 tTID Threads_WaitTID(int TID, int *Status)
384 Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Any Child");
388 // Any peer/child thread
390 Log_Error("Threads", "TODO: Threads_WaitTID(TID=0) - Any Child/Sibling");
396 Log_Error("Threads", "TODO: Threads_WaitTID(TID<0) - TGID");
402 tThread *t = Threads_GetThread(TID);
403 int initStatus = t->Status;
406 // Wait for the thread to die!
407 if(initStatus != THREAD_STAT_ZOMBIE) {
408 // TODO: Handle child also being suspended if wanted
409 while(t->Status != THREAD_STAT_ZOMBIE) {
411 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
412 Threads_GetTID(), t->TID, t->Status);
417 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
418 Threads_GetTID(), t->TID, t->Status);
422 case THREAD_STAT_ZOMBIE:
424 t->Status = THREAD_STAT_DEAD;
425 // TODO: Child return value?
426 if(Status) *Status = t->RetStatus;
427 // add to delete queue
428 Threads_AddToDelete( t );
431 if(Status) *Status = -1;
441 * \brief Gets a thread given its TID
442 * \param TID Thread ID
443 * \return Thread pointer
445 tThread *Threads_GetThread(Uint TID)
449 // Search global list
450 for(thread = gAllThreads;
452 thread = thread->GlobalNext)
454 if(thread->TID == TID)
458 Log("Unable to find TID %i on main list\n", TID);
464 * \brief Adds a thread to the delete queue
465 * \param Thread Thread to delete
467 void Threads_AddToDelete(tThread *Thread)
469 // Add to delete queue
470 // TODO: Is locking needed?
472 Thread->Next = gDeleteThreads;
473 gDeleteThreads = Thread;
476 gDeleteThreads = Thread;
481 * \brief Deletes an entry from a list
482 * \param List Pointer to the list head
483 * \param Thread Thread to find
486 tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread)
488 tThread *ret, *prev = NULL;
491 ret && ret != Thread;
492 prev = ret, ret = ret->Next
495 // Is the thread on the list
497 //LogF("%p(%s) is not on list %p\n", Thread, Thread->ThreadName, List);
502 *List = Thread->Next;
503 //LogF("%p(%s) removed from head of %p\n", Thread, Thread->ThreadName, List);
506 prev->Next = Thread->Next;
507 //LogF("%p(%s) removed from %p (prev=%p)\n", Thread, Thread->ThreadName, List, prev);
514 * \brief Exit the current process (or another?)
515 * \param TID Thread ID to kill
516 * \param Status Exit status
518 void Threads_Exit(int TID, int Status)
521 Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF );
523 Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF );
525 // Halt forever, just in case
530 * \fn void Threads_Kill(tThread *Thread, int Status)
531 * \brief Kill a thread
532 * \param Thread Thread to kill
533 * \param Status Status code to return to the parent
535 void Threads_Kill(tThread *Thread, int Status)
538 int isCurThread = Thread == Proc_GetCurThread();
540 // TODO: Kill all children
544 // TODO: I should keep a .Parent pointer, and a .Children list
545 for(child = gAllThreads;
547 child = child->GlobalNext)
549 if(child->Parent == Thread)
550 Threads_Kill(child, -1);
555 ///\note Double lock is needed due to overlap of lock areas
557 // Lock thread (stop us recieving messages)
558 SHORTLOCK( &Thread->IsLocked );
560 // Clear Message Queue
561 while( Thread->Messages )
563 msg = Thread->Messages->Next;
564 free( Thread->Messages );
565 Thread->Messages = msg;
569 SHORTLOCK( &glThreadListLock );
571 switch(Thread->Status)
573 case THREAD_STAT_PREINIT: // Only on main list
576 // Currently active thread
577 case THREAD_STAT_ACTIVE:
578 #if SCHEDULER_TYPE == SCHED_RR_PRI
579 if( Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ) )
581 if( Threads_int_DelFromQueue( &gActiveThreads, Thread ) )
584 // Ensure that we are not rescheduled
585 Thread->Remaining = 0; // Clear Remaining Quantum
586 Thread->Quantum = 0; // Clear Quantum to indicate dead thread
588 // Update bookkeeping
589 giNumActiveThreads --;
590 #if SCHEDULER_TYPE == SCHED_LOTTERY
591 if( Thread != Proc_GetCurThread() )
592 giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ];
597 Log_Warning("Threads",
598 "Threads_Kill - Thread %p(%i,%s) marked as active, but not on list",
599 Thread, Thread->TID, Thread->ThreadName
603 // Kill it while it sleeps!
604 case THREAD_STAT_SLEEPING:
605 if( !Threads_int_DelFromQueue( &gSleepingThreads, Thread ) )
607 Log_Warning("Threads",
608 "Threads_Kill - Thread %p(%i,%s) marked as sleeping, but not on list",
609 Thread, Thread->TID, Thread->ThreadName
614 // Brains!... You cannot kill
615 case THREAD_STAT_ZOMBIE:
616 Log_Warning("Threads", "Threads_Kill - Thread %p(%i,%s) is undead, you cannot kill it",
617 Thread, Thread->TID, Thread->ThreadName);
618 SHORTREL( &glThreadListLock );
619 SHORTREL( &Thread->IsLocked );
623 Log_Warning("Threads", "Threads_Kill - BUG Un-checked status (%i)",
629 Thread->RetStatus = Status;
631 // Don't Zombie if we are being killed because our parent is
634 Thread->Status = THREAD_STAT_DEAD;
635 Threads_AddToDelete( Thread );
637 Thread->Status = THREAD_STAT_ZOMBIE;
639 Threads_Wake( Thread->Parent );
642 Log("Thread %i went *hurk* (%i)", Thread->TID, Status);
645 SHORTREL( &glThreadListLock );
646 SHORTREL( &Thread->IsLocked ); // TODO: We may not actually be released...
656 * \brief Yield remainder of the current thread's timeslice
658 void Threads_Yield(void)
660 tThread *thread = Proc_GetCurThread();
661 thread->Remaining = 0;
662 //while(thread->Remaining == 0)
667 * \fn void Threads_Sleep(void)
668 * \brief Take the current process off the run queue
670 void Threads_Sleep(void)
672 tThread *cur = Proc_GetCurThread();
675 SHORTLOCK( &glThreadListLock );
677 // Don't sleep if there is a message waiting
678 if( cur->Messages ) {
679 SHORTREL( &glThreadListLock );
683 // Remove us from running queue
685 // Mark thread as sleeping
686 cur->Status = THREAD_STAT_SLEEPING;
688 // Add to Sleeping List (at the top)
689 cur->Next = gSleepingThreads;
690 gSleepingThreads = cur;
693 #if DEBUG_TRACE_STATE
694 Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName);
698 SHORTREL( &glThreadListLock );
700 while(cur->Status != THREAD_STAT_ACTIVE) HALT();
705 * \fn int Threads_Wake( tThread *Thread )
706 * \brief Wakes a sleeping/waiting thread up
707 * \param Thread Thread to wake
708 * \return Boolean Failure (Returns ERRNO)
709 * \warning This should ONLY be called with task switches disabled
711 int Threads_Wake(tThread *Thread)
716 switch(Thread->Status)
718 case THREAD_STAT_ACTIVE:
719 Log("Thread_Wake: Waking awake thread (%i)", Thread->TID);
722 case THREAD_STAT_SLEEPING:
723 SHORTLOCK( &glThreadListLock );
724 // Remove from sleeping queue
725 Threads_int_DelFromQueue(&gSleepingThreads, Thread);
727 Threads_AddActive( Thread );
729 #if DEBUG_TRACE_STATE
730 Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName);
732 SHORTREL( &glThreadListLock );
735 case THREAD_STAT_WAITING:
736 Warning("Thread_Wake - Waiting threads are not currently supported");
739 case THREAD_STAT_DEAD:
740 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
744 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
750 * \brief Wake a thread given the TID
751 * \param TID Thread ID to wake
752 * \return Boolean Faulure (errno)
754 int Threads_WakeTID(tTID TID)
756 tThread *thread = Threads_GetThread(TID);
760 ret = Threads_Wake( thread );
761 //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread);
766 * \brief Adds a thread to the active queue
768 void Threads_AddActive(tThread *Thread)
770 SHORTLOCK( &glThreadListLock );
772 if( Thread->Status == THREAD_STAT_ACTIVE ) {
773 tThread *cur = Proc_GetCurThread();
774 Warning("WTF, CPU%i %p (%i %s) is adding %p (%i %s) when it is active",
775 GetCPUNum(), cur, cur->TID, cur->ThreadName, Thread, Thread->TID, Thread->ThreadName);
779 Thread->Status = THREAD_STAT_ACTIVE;
781 // Add to active list
782 #if SCHEDULER_TYPE == SCHED_RR_PRI
783 Thread->Next = gaActiveThreads[Thread->Priority];
784 gaActiveThreads[Thread->Priority] = Thread;
786 Thread->Next = gActiveThreads;
787 gActiveThreads = Thread;
790 // Update bookkeeping
791 giNumActiveThreads ++;
793 #if SCHEDULER_TYPE == SCHED_LOTTERY
794 giFreeTickets += caiTICKET_COUNTS[ Thread->Priority ];
795 # if DEBUG_TRACE_TICKETS
796 Log("Threads_AddActive: CPU%i %p %i (%s) added, new giFreeTickets = %i",
797 GetCPUNum(), Thread, Thread->TID, Thread->ThreadName, giFreeTickets);
801 SHORTREL( &glThreadListLock );
805 * \brief Removes the current thread from the active queue
806 * \warning This should ONLY be called with task switches disabled
807 * \return Current thread pointer
809 tThread *Threads_RemActive(void)
811 tThread *ret = Proc_GetCurThread();
813 SHORTLOCK( &glThreadListLock );
815 // Delete from active queue
816 #if SCHEDULER_TYPE == SCHED_RR_PRI
817 if( !Threads_int_DelFromQueue(&gaActiveThreads[ret->Priority], ret) )
819 if( !Threads_int_DelFromQueue(&gActiveThreads, ret) )
822 SHORTREL( &glThreadListLock );
830 giNumActiveThreads --;
831 // no need to decrement tickets, scheduler did it for us
833 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
834 Log("Threads_RemActive: CPU%i %p %i (%s) removed, giFreeTickets = %i",
835 GetCPUNum(), ret, ret->TID, ret->ThreadName, giFreeTickets);
838 SHORTREL( &glThreadListLock );
844 * \fn void Threads_SetFaultHandler(Uint Handler)
845 * \brief Sets the signal handler for a signal
847 void Threads_SetFaultHandler(Uint Handler)
849 //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
850 Proc_GetCurThread()->FaultHandler = Handler;
854 * \fn void Threads_Fault(int Num)
855 * \brief Calls a fault handler
857 void Threads_Fault(int Num)
859 tThread *thread = Proc_GetCurThread();
861 Log_Log("Threads", "Threads_Fault: thread = %p", thread);
865 Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
867 switch(thread->FaultHandler)
870 Threads_Kill(thread, -1);
873 case 1: // Dump Core?
874 Threads_Kill(thread, -1);
879 // Double Fault? Oh, F**k
880 if(thread->CurFaultNum != 0) {
881 Threads_Kill(thread, -1); // For now, just kill
885 thread->CurFaultNum = Num;
887 Proc_CallFaultHandler(thread);
890 // --- Process Structure Access Functions ---
891 tPID Threads_GetPID(void)
893 return Proc_GetCurThread()->TGID;
895 tTID Threads_GetTID(void)
897 return Proc_GetCurThread()->TID;
899 tUID Threads_GetUID(void)
901 return Proc_GetCurThread()->UID;
903 tGID Threads_GetGID(void)
905 return Proc_GetCurThread()->GID;
908 int Threads_SetUID(Uint *Errno, tUID ID)
910 tThread *t = Proc_GetCurThread();
915 Log_Debug("Threads", "TID %i's UID set to %i", t->TID, ID);
920 int Threads_SetGID(Uint *Errno, tGID ID)
922 tThread *t = Proc_GetCurThread();
927 Log_Debug("Threads", "TID %i's GID set to %i", t->TID, ID);
933 * \fn void Threads_Dump(void)
935 void Threads_DumpActive(void)
938 #if SCHEDULER_TYPE == SCHED_RR_PRI
942 Log("Active Threads: (%i reported)", giNumActiveThreads);
944 #if SCHEDULER_TYPE == SCHED_RR_PRI
945 for( i = 0; i < MIN_PRIORITY+1; i++ )
947 for(thread=gaActiveThreads[i];thread;thread=thread->Next)
949 for(thread=gActiveThreads;thread;thread=thread->Next)
952 Log(" %p %i (%i) - %s (CPU %i)",
953 thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
954 if(thread->Status != THREAD_STAT_ACTIVE)
955 Log(" ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE);
956 Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum);
957 Log(" KStack 0x%x", thread->KernelStack);
960 #if SCHEDULER_TYPE == SCHED_RR_PRI
966 * \fn void Threads_Dump(void)
967 * \brief Dumps a list of currently running threads
969 void Threads_Dump(void)
973 Log("--- Thread Dump ---");
974 Threads_DumpActive();
977 for(thread=gAllThreads;thread;thread=thread->GlobalNext)
979 Log(" %p %i (%i) - %s (CPU %i)",
980 thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
981 Log(" State %i (%s)", thread->Status, casTHREAD_STAT[thread->Status]);
982 switch(thread->Status)
984 case THREAD_STAT_MUTEXSLEEP:
985 Log(" Mutex Pointer: %p", thread->WaitPointer);
987 case THREAD_STAT_SEMAPHORESLEEP:
988 Log(" Semaphore Pointer: %p", thread->WaitPointer);
989 Log(" Semaphore Name: %s:%s",
990 ((tSemaphore*)thread->WaitPointer)->ModName,
991 ((tSemaphore*)thread->WaitPointer)->Name
994 case THREAD_STAT_ZOMBIE:
995 Log(" Return Status: %i", thread->RetStatus);
999 Log(" Priority %i, Quantum %i", thread->Priority, thread->Quantum);
1000 Log(" KStack 0x%x", thread->KernelStack);
1005 * \brief Gets the next thread to run
1006 * \param CPU Current CPU
1007 * \param Last The thread the CPU was running
1009 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
1013 // If this CPU has the lock, we must let it complete
1014 if( CPU_HAS_LOCK( &glThreadListLock ) )
1017 // Don't change threads if the current CPU has switches disabled
1018 if( gaThreads_NoTaskSwitch[CPU] )
1023 SHORTLOCK( &glThreadListLock );
1025 // Clear Delete Queue
1026 // - I should probably put this in a worker thread to avoid calling free() in the scheduler
1027 // DEFINITELY - free() can deadlock in this case
1028 while(gDeleteThreads)
1030 thread = gDeleteThreads->Next;
1031 // Only free if structure is unused
1032 if( !IS_LOCKED(&gDeleteThreads->IsLocked) )
1035 gDeleteThreads->Status = THREAD_STAT_BURIED;
1037 if( IsHeap(gDeleteThreads->ThreadName) )
1038 free(gDeleteThreads->ThreadName);
1039 // Remove from global list
1040 if( gDeleteThreads == gAllThreads )
1041 gAllThreads = gDeleteThreads->GlobalNext;
1043 gDeleteThreads->GlobalPrev->GlobalNext = gDeleteThreads->GlobalNext;
1044 free( gDeleteThreads );
1046 gDeleteThreads = thread;
1049 // No active threads, just take a nap
1050 if(giNumActiveThreads == 0) {
1051 SHORTREL( &glThreadListLock );
1052 #if DEBUG_TRACE_TICKETS
1053 Log("No active threads");
1058 #if SCHEDULER_TYPE != SCHED_RR_PRI
1059 // Special case: 1 thread
1060 if(giNumActiveThreads == 1) {
1061 if( gActiveThreads->CurCPU == -1 )
1062 gActiveThreads->CurCPU = CPU;
1064 SHORTREL( &glThreadListLock );
1066 if( gActiveThreads->CurCPU == CPU )
1067 return gActiveThreads;
1069 return NULL; // CPU has nothing to do
1073 // Allow the old thread to be scheduled again
1075 if( Last->Status == THREAD_STAT_ACTIVE ) {
1076 #if SCHEDULER_TYPE == SCHED_LOTTERY
1077 giFreeTickets += caiTICKET_COUNTS[ Last->Priority ];
1078 # if DEBUG_TRACE_TICKETS
1079 LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n",
1080 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets);
1084 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
1086 LogF(" CPU %i released %p (%i %s)->Status = %i (Released)\n",
1087 CPU, Last, Last->TID, Last->ThreadName, Last->Status);
1093 // Lottery Scheduler
1095 #if SCHEDULER_TYPE == SCHED_LOTTERY
1100 for(thread = gActiveThreads; thread; thread = thread->Next) {
1101 if(thread->CurCPU >= 0) continue;
1102 if(thread->Status != THREAD_STAT_ACTIVE)
1103 Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i",
1104 thread, thread->TID, thread->ThreadName, thread->Status);
1105 if(thread->Next == thread) {
1106 Panic("Bookkeeping fail - %p %i(%s) loops back on itself",
1107 thread, thread->TID, thread->ThreadName, thread->Status);
1109 number += caiTICKET_COUNTS[ thread->Priority ];
1111 if(number != giFreeTickets) {
1112 Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
1113 giFreeTickets, number, CPU);
1117 // No free tickets (all tasks delegated to cores)
1118 if( giFreeTickets == 0 ) {
1119 SHORTREL(&glThreadListLock);
1123 // Get the ticket number
1124 ticket = number = rand() % giFreeTickets;
1126 // Find the next thread
1127 for(thread=gActiveThreads;thread;thread=thread->Next)
1129 if(thread->CurCPU >= 0) continue;
1130 if( caiTICKET_COUNTS[ thread->Priority ] > number) break;
1131 number -= caiTICKET_COUNTS[ thread->Priority ];
1134 // If we didn't find a thread, something went wrong
1138 for(thread=gActiveThreads;thread;thread=thread->Next) {
1139 if(thread->CurCPU >= 0) continue;
1140 number += caiTICKET_COUNTS[ thread->Priority ];
1142 Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
1143 giFreeTickets, number);
1145 # if DEBUG_TRACE_TICKETS
1146 LogF(" CPU%i giFreeTickets = %i, running %p (%i %s CPU=%i)\n",
1147 CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU);
1150 giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ];
1154 // Priority based round robin scheduler
1156 #elif SCHEDULER_TYPE == SCHED_RR_PRI
1159 for( i = 0; i < MIN_PRIORITY + 1; i ++ )
1161 for(thread = gaActiveThreads[i]; thread; thread = thread->Next)
1163 if( thread->CurCPU == -1 ) break;
1165 // If we fall onto the same queue again, special handling is
1167 if( i == Last->Priority ) {
1168 tThread *savedThread = thread;
1170 // Find the next unscheduled thread in the list
1171 for( thread = Last->Next; thread; thread = thread->Next )
1173 if( thread->CurCPU == -1 ) break;
1175 // If we don't find anything after, just use the one
1177 if( !thread ) thread = savedThread;
1179 // Found a thread? Schedule it!
1185 SHORTREL(&glThreadListLock);
1189 #elif SCHEDULER_TYPE == SCHED_RR_SIM
1191 // Find the next unscheduled thread in the list
1192 for( thread = Last->Next; thread; thread = thread->Next )
1194 if( thread->CurCPU == -1 ) break;
1196 // If we don't find anything after, search from the beginning
1199 for(thread = gActiveThreads; thread; thread = thread->Next)
1201 if( thread->CurCPU == -1 ) break;
1207 SHORTREL(&glThreadListLock);
1212 # error "Unimplemented scheduling algorithm"
1215 // Make the new thread non-schedulable
1216 thread->CurCPU = CPU;
1218 SHORTREL( &glThreadListLock );
1224 * \fn void Threads_SegFault(tVAddr Addr)
1225 * \brief Called when a Segment Fault occurs
1227 void Threads_SegFault(tVAddr Addr)
1229 Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr);
1231 //Threads_Exit( 0, -1 );
1235 * \brief Acquire a heavy mutex
1236 * \param Mutex Mutex to acquire
1238 * This type of mutex checks if the mutex is avaliable, and acquires it
1239 * if it is. Otherwise, the current thread is added to the mutex's wait
1240 * queue and the thread suspends. When the holder of the mutex completes,
1241 * the oldest thread (top thread) on the queue is given the lock and
1244 int Mutex_Acquire(tMutex *Mutex)
1246 tThread *us = Proc_GetCurThread();
1249 SHORTLOCK( &Mutex->Protector );
1251 //Log("Mutex_Acquire: (%p)", Mutex);
1253 // Check if the lock is already held
1254 if( Mutex->Owner ) {
1255 SHORTLOCK( &glThreadListLock );
1256 // - Remove from active list
1257 us = Threads_RemActive();
1259 // - Mark as sleeping
1260 us->Status = THREAD_STAT_MUTEXSLEEP;
1261 us->WaitPointer = Mutex;
1264 if(Mutex->LastWaiting) {
1265 Mutex->LastWaiting->Next = us;
1266 Mutex->LastWaiting = us;
1269 Mutex->Waiting = us;
1270 Mutex->LastWaiting = us;
1276 for( t = Mutex->Waiting; t; t = t->Next, i++ )
1277 Log("[%i] (tMutex)%p->Waiting[%i] = %p (%i %s)", us->TID, Mutex, i,
1278 t, t->TID, t->ThreadName);
1282 SHORTREL( &glThreadListLock );
1283 SHORTREL( &Mutex->Protector );
1284 while(us->Status == THREAD_STAT_MUTEXSLEEP) Threads_Yield();
1285 // We're only woken when we get the lock
1286 us->WaitPointer = NULL;
1288 // Ooh, let's take it!
1291 SHORTREL( &Mutex->Protector );
1295 extern tMutex glPhysAlloc;
1296 if( Mutex != &glPhysAlloc )
1297 LogF("Mutex %p taken by %i %p\n", Mutex, us->TID, __builtin_return_address(0));
1304 * \brief Release a held mutex
1305 * \param Mutex Mutex to release
1307 void Mutex_Release(tMutex *Mutex)
1309 SHORTLOCK( &Mutex->Protector );
1310 //Log("Mutex_Release: (%p)", Mutex);
1311 if( Mutex->Waiting ) {
1312 Mutex->Owner = Mutex->Waiting; // Set owner
1313 Mutex->Waiting = Mutex->Waiting->Next; // Next!
1314 // Reset ->LastWaiting to NULL if we have just removed the last waiting thread
1315 // 2010-10-02 21:50 - Comemerating the death of the longest single
1316 // blocker in the Acess2 history. REMEMBER TO
1317 // FUCKING MAINTAIN YOUR FUCKING LISTS DIPWIT
1318 if( Mutex->LastWaiting == Mutex->Owner )
1319 Mutex->LastWaiting = NULL;
1322 SHORTLOCK( &glThreadListLock );
1323 if( Mutex->Owner->Status != THREAD_STAT_ACTIVE )
1324 Threads_AddActive(Mutex->Owner);
1325 SHORTREL( &glThreadListLock );
1328 Mutex->Owner = NULL;
1330 SHORTREL( &Mutex->Protector );
1333 extern tMutex glPhysAlloc;
1334 if( Mutex != &glPhysAlloc )
1335 LogF("Mutex %p released by %i %p\n", Mutex, Threads_GetTID(), __builtin_return_address(0));
1340 * \brief Is this mutex locked?
1341 * \param Mutex Mutex pointer
1343 int Mutex_IsLocked(tMutex *Mutex)
1345 return Mutex->Owner != NULL;
1349 // Initialise a semaphore
1351 void Semaphore_Init(tSemaphore *Sem, int Value, int MaxValue, const char *Module, const char *Name)
1354 Sem->ModName = Module;
1358 // Wait for items to be avaliable
1360 int Semaphore_Wait(tSemaphore *Sem, int MaxToTake)
1364 if( MaxToTake < 0 ) {
1365 Log_Warning("Threads", "Semaphore_Wait: User bug - MaxToTake(%i) < 0, Sem=%p(%s)",
1366 MaxToTake, Sem, Sem->Name);
1369 SHORTLOCK( &Sem->Protector );
1371 // Check if there's already items avaliable
1372 if( Sem->Value > 0 ) {
1373 // Take what we need
1374 if( MaxToTake && Sem->Value > MaxToTake )
1378 Sem->Value -= taken;
1379 SHORTREL( &Sem->Protector );
1383 SHORTLOCK( &glThreadListLock );
1385 // - Remove from active list
1386 us = Threads_RemActive();
1388 // - Mark as sleeping
1389 us->Status = THREAD_STAT_SEMAPHORESLEEP;
1390 us->WaitPointer = Sem;
1391 us->RetStatus = MaxToTake; // Use RetStatus as a temp variable
1394 if(Sem->LastWaiting) {
1395 Sem->LastWaiting->Next = us;
1396 Sem->LastWaiting = us;
1400 Sem->LastWaiting = us;
1403 SHORTREL( &glThreadListLock );
1404 SHORTREL( &Sem->Protector );
1405 while(us->Status == THREAD_STAT_SEMAPHORESLEEP) Threads_Yield();
1406 // We're only woken when there's something avaliable
1407 us->WaitPointer = NULL;
1409 taken = us->RetStatus;
1411 // Get the lock again
1412 SHORTLOCK( &Sem->Protector );
1415 // While there is space, and there are thread waiting
1416 // wake the first thread and give it what it wants (or what's left)
1417 while( (Sem->MaxValue == 0 || Sem->Value < Sem->MaxValue) && Sem->Signaling )
1420 tThread *toWake = Sem->Signaling;
1422 Sem->Signaling = Sem->Signaling->Next;
1423 // Reset ->LastWaiting to NULL if we have just removed the last waiting thread
1424 if( Sem->Signaling == NULL )
1425 Sem->LastSignaling = NULL;
1427 // Figure out how much to give
1428 if( toWake->RetStatus && Sem->Value + toWake->RetStatus < Sem->MaxValue )
1429 given = toWake->RetStatus;
1431 given = Sem->MaxValue - Sem->Value;
1432 Sem->Value -= given;
1434 // Save the number we gave to the thread's status
1435 toWake->RetStatus = given;
1438 SHORTLOCK( &glThreadListLock );
1439 if( toWake->Status != THREAD_STAT_ACTIVE )
1440 Threads_AddActive(toWake);
1441 SHORTREL( &glThreadListLock );
1443 SHORTREL( &Sem->Protector );
1449 // Add items to a semaphore
1451 int Semaphore_Signal(tSemaphore *Sem, int AmmountToAdd)
1456 if( AmmountToAdd < 0 ) {
1457 Log_Warning("Threads", "Semaphore_Signal: User bug - AmmountToAdd(%i) < 0, Sem=%p(%s)",
1458 AmmountToAdd, Sem, Sem->Name);
1460 SHORTLOCK( &Sem->Protector );
1462 // Check if we have to block
1463 if( Sem->MaxValue && Sem->Value == Sem->MaxValue )
1466 SHORTLOCK( &glThreadListLock );
1468 // - Remove from active list
1469 us = Threads_RemActive();
1471 // - Mark as sleeping
1472 us->Status = THREAD_STAT_SEMAPHORESLEEP;
1473 us->WaitPointer = Sem;
1474 us->RetStatus = AmmountToAdd; // Use RetStatus as a temp variable
1477 if(Sem->LastSignaling) {
1478 Sem->LastSignaling->Next = us;
1479 Sem->LastSignaling = us;
1482 Sem->Signaling = us;
1483 Sem->LastSignaling = us;
1486 SHORTREL( &glThreadListLock );
1487 SHORTREL( &Sem->Protector );
1488 while(us->Status == THREAD_STAT_SEMAPHORESLEEP) Threads_Yield();
1489 // We're only woken when there's something avaliable
1490 us->WaitPointer = NULL;
1492 added = us->RetStatus;
1494 // Get the lock again
1495 SHORTLOCK( &Sem->Protector );
1500 // Figure out how much we need to take off
1501 if( Sem->MaxValue && Sem->Value + AmmountToAdd > Sem->MaxValue)
1502 added = Sem->MaxValue - Sem->Value;
1504 added = AmmountToAdd;
1505 Sem->Value += added;
1508 // While there are items avaliable, and there are thread waiting
1509 // wake the first thread and give it what it wants (or what's left)
1510 while( Sem->Value && Sem->Waiting )
1512 tThread *toWake = Sem->Waiting;
1514 Sem->Waiting = Sem->Waiting->Next;
1515 // Reset ->LastWaiting to NULL if we have just removed the last waiting thread
1516 if( Sem->Waiting == NULL )
1517 Sem->LastWaiting = NULL;
1519 // Figure out how much to give
1520 if( toWake->RetStatus && Sem->Value > toWake->RetStatus )
1521 given = toWake->RetStatus;
1524 Sem->Value -= given;
1526 // Save the number we gave to the thread's status
1527 toWake->RetStatus = given;
1530 SHORTLOCK( &glThreadListLock );
1531 if( toWake->Status != THREAD_STAT_ACTIVE )
1532 Threads_AddActive(toWake);
1533 SHORTREL( &glThreadListLock );
1535 SHORTREL( &Sem->Protector );
1541 // Get the current value of a semaphore
1543 int Semaphore_GetValue(tSemaphore *Sem)
1549 EXPORT(Threads_GetUID);
1550 EXPORT(Threads_GetGID);
1551 EXPORT(Mutex_Acquire);
1552 EXPORT(Mutex_Release);
1553 EXPORT(Mutex_IsLocked);
1554 EXPORT(Semaphore_Init);
1555 EXPORT(Semaphore_Wait);
1556 EXPORT(Semaphore_Signal);