Kernel/threads - Debug cleanups and (hopefully) race avoidance
[tpg/acess2.git] / KernelLand / Kernel / threads.c
1 /*
2  * Acess2 Kernel
3  * - By John Hodge (thePowersGang)
4  * threads.c
5  * - Common Thread Control
6  */
7 #define DEBUG   0
8 #include <acess.h>
9 #include <threads.h>
10 #include <threads_int.h>
11 #include <errno.h>
12 #include <hal_proc.h>
13 #include <semaphore.h>
14 #include <rwlock.h>
15 #include <vfs_threads.h>        // VFS Handle maintainence
16 #include <events.h>
17 #include <debug_hooks.h>
18
19 // Configuration
20 #define DEBUG_TRACE_ACTIVEQUEUE 0       // Trace adds/removals from the active queue
21 #define DEBUG_TRACE_TICKETS     0       // Trace ticket counts
22 #define DEBUG_TRACE_STATE       0       // Trace state changes (sleep/wake)
23 #define DEBUG_TRACE_SCHEDULE    0       // Trace scheduling
24
25 // --- Schedulers ---
26 #define SCHED_UNDEF     0
27 #define SCHED_LOTTERY   1       // Lottery scheduler
28 #define SCHED_RR_SIM    2       // Single Queue Round Robin
29 #define SCHED_RR_PRI    3       // Multi Queue Round Robin
30 // Set scheduler type
31 #define SCHEDULER_TYPE  SCHED_RR_PRI
32
33 // === CONSTANTS ===
34 #define DEFAULT_QUANTUM 5
35 #define DEFAULT_PRIORITY        5
36 #define MIN_PRIORITY            10
37
38 #define PRIthread_fmt   "%p(%i %s)"
39 #define PRIthread_args(t)       (t), ((t)?(t)->TID:-1), ((t)?(t)->ThreadName:"-")
40
41 // === IMPORTS ===
42 extern void     User_Signal_Kill(int SigNum);
43
44 // === TYPE ===
45 typedef struct
46 {
47         tThread *Head;
48         tThread *Tail;
49 } tThreadList;
50
51 // === PROTOTYPES ===
52 void    Threads_Init(void);
53 #if 0
54 void    Threads_Delete(tThread *Thread);
55  int    Threads_SetName(const char *NewName);
56 #endif
57 char    *Threads_GetName(tTID ID);
58 #if 0
59 void    Threads_SetPriority(tThread *Thread, int Pri);
60 tThread *Threads_CloneTCB(Uint Flags);
61  int    Threads_WaitTID(int TID, int *status);
62 tThread *Threads_GetThread(Uint TID);
63 #endif
64 tThread *Threads_int_DelFromQueue(tThreadList *List, tThread *Thread);
65 void    Threads_int_AddToList(tThreadList *List, tThread *Thread);
66 #if 0
67 void    Threads_Exit(int TID, int Status);
68 void    Threads_Kill(tThread *Thread, int Status);
69 void    Threads_Yield(void);
70  int    Threads_int_Sleep(enum eThreadStatus Status, void *Ptr, int Num, tThread **ListHead, tThread **ListTail, tShortSpinlock *Lock);
71 void    Threads_Sleep(void);
72  int    Threads_Wake(tThread *Thread);
73 void    Threads_AddActive(tThread *Thread);
74 tThread *Threads_RemActive(void);
75 void    Threads_ToggleTrace(int TID);
76 #endif
77 void    Threads_Fault(int Num);
78 void    Threads_SegFault(tVAddr Addr);
79 void    Threads_PostSignalTo(tThread *Thread, int SignalNum);
80 #if 0
81 void    Threads_PostSignal(int SignalNum);
82 void    Threads_SignalGroup(tPGID PGID, int SignalNum);
83 #endif
84  int    Threads_GetPendingSignal(void);
85 void    Threads_SetSignalHandler(int SignalNum, void *Handler);
86 void    *Threads_GetSignalHandler(int SignalNum);
87 #if 0
88  int    Threads_GetPID(void);
89  int    Threads_GetTID(void);
90 tUID    Threads_GetUID(void);
91 tGID    Threads_GetGID(void);
92  int    Threads_SetUID(Uint *Errno, tUID ID);
93  int    Threads_SetGID(Uint *Errno, tUID ID);
94 #endif
95 void    Threads_int_DumpThread(tThread *thread);
96 #if 0
97 void    Threads_Dump(void);
98 #endif
99 void    Threads_DumpActive(void);
100 tThread *Threads_int_GetRunnable(void);
101
102 // === GLOBALS ===
103 // -- Core Thread --
104 tProcess        gProcessZero = {
105         };
106 // Only used for the core kernel
107 tThread gThreadZero = {
108         .Status         = THREAD_STAT_ACTIVE,   // Status
109         .ThreadName     = (char*)"ThreadZero",  // Name
110         .Quantum        = DEFAULT_QUANTUM,      // Default Quantum
111         .Remaining      = DEFAULT_QUANTUM,      // Current Quantum
112         .Priority       = DEFAULT_PRIORITY      // Number of tickets
113         };
114 // -- Processes --
115 tProcess        *gAllProcesses = &gProcessZero;
116 // --- Locks ---
117 tShortSpinlock  glThreadListLock;       ///\note NEVER use a heap function while locked
118 // --- Current State ---
119 volatile int    giNumActiveThreads = 0; // Number of threads on the active queue
120 volatile Uint   giNextTID = 1;  // Next TID to allocate
121 // --- Thread Lists ---
122 tThread *gAllThreads = NULL;            // All allocated threads
123 tThreadList     gSleepingThreads;       // Sleeping Threads
124  int    giNumCPUs = 1;  // Number of CPUs
125 BOOL     gaThreads_NoTaskSwitch[MAX_CPUS];      // Disables task switches for each core (Pseudo-IF)
126 // --- Scheduler Types ---
127 #if SCHEDULER_TYPE == SCHED_LOTTERY
128 const int       caiTICKET_COUNTS[MIN_PRIORITY+1] = {100,81,64,49,36,25,16,9,4,1,0};
129 volatile int    giFreeTickets = 0;      // Number of tickets held by non-scheduled threads
130 tThreadList     gActiveThreads;         // Currently Running Threads
131 #elif SCHEDULER_TYPE == SCHED_RR_SIM
132 tThreadList     gActiveThreads;         // Currently Running Threads
133 #elif SCHEDULER_TYPE == SCHED_RR_PRI
134 tThreadList     gaActiveThreads[MIN_PRIORITY+1];        // Active threads for each priority level
135 #else
136 # error "Unkown scheduler type"
137 #endif
138
139 // === CODE ===
140 /**
141  * \fn void Threads_Init(void)
142  * \brief Initialse the thread list
143  */
144 void Threads_Init(void)
145 {
146         ArchThreads_Init();
147         
148         Log_Debug("Threads", "Offsets of tThread");
149         Log_Debug("Threads", ".Priority = %i", offsetof(tThread, Priority));
150         Log_Debug("Threads", ".KernelStack = %i", offsetof(tThread, KernelStack));
151         
152         // Create Initial Task
153         gAllThreads = &gThreadZero;
154         giNumActiveThreads = 1;
155         gThreadZero.Process = &gProcessZero;
156                 
157         Proc_Start();
158 }
159
160 void Threads_Delete(tThread *Thread)
161 {
162         // Set to dead
163         Thread->Status = THREAD_STAT_BURIED;
164
165         // Clear out process state
166         Proc_ClearThread(Thread);                       
167
168         Thread->Process->nThreads --;
169
170         if( Thread->Process->FirstThread == Thread )
171         {
172                 Thread->Process->FirstThread = Thread->ProcessNext;
173         }
174         else
175         {
176                 tThread *prev = Thread->Process->FirstThread;
177                 while(prev && prev->ProcessNext != Thread)
178                         prev = prev->ProcessNext;
179                 if( !prev )
180                         Log_Error("Threads", "Thread %p(%i %s) is not on the process's list",
181                                 Thread, Thread->TID, Thread->ThreadName
182                                 );
183                 else
184                         prev->ProcessNext = Thread->ProcessNext;
185         }
186
187         // If the final thread is being terminated, clean up the process
188         if( Thread->Process->nThreads == 0 )
189         {
190                 tProcess        *proc = Thread->Process;
191
192                 // Remove from global process list
193                 // TODO: RWLock
194                 if(proc->Prev)
195                         proc->Prev->Next = proc->Next;
196                 else
197                         gAllProcesses = proc->Next;
198                 if(proc->Next)
199                         proc->Next->Prev = proc->Prev;
200
201                 // VFS Cleanup
202                 VFS_CloseAllUserHandles( proc );
203                 // Architecture cleanup
204                 Proc_ClearProcess( proc );
205                 // VFS Configuration strings
206                 if( proc->CurrentWorkingDir)
207                         free( proc->CurrentWorkingDir );
208                 if( proc->RootDir )
209                         free( proc->RootDir );
210                 // Process descriptor
211                 free( proc );
212         }
213         
214         // Free name
215         if( IsHeap(Thread->ThreadName) )
216                 free(Thread->ThreadName);
217         
218         // Remove from global list
219         // TODO: Lock this too
220         if( Thread == gAllThreads )
221                 gAllThreads = Thread->GlobalNext;
222         else
223                 Thread->GlobalPrev->GlobalNext = Thread->GlobalNext;
224         
225         free(Thread);
226 }
227
228 /**
229  * \fn void Threads_SetName(const char *NewName)
230  * \brief Sets the current thread's name
231  * \param NewName       New name for the thread
232  * \return Boolean Failure
233  */
234 int Threads_SetName(const char *NewName)
235 {
236         tThread *cur = Proc_GetCurThread();
237         char    *oldname = cur->ThreadName;
238         
239         // NOTE: There is a possibility of non-thread safety here
240         // A thread could read the current name pointer before it is zeroed
241         
242         cur->ThreadName = NULL;
243         
244         if( IsHeap(oldname) )   free( oldname );        
245         cur->ThreadName = strdup(NewName);
246
247         Log_Debug("Threads", "Thread renamed to '%s'", NewName);        
248
249         return 0;
250 }
251
252 /**
253  * \fn char *Threads_GetName(int ID)
254  * \brief Gets a thread's name
255  * \param ID    Thread ID (-1 indicates current thread)
256  * \return Pointer to name
257  * \retval NULL Failure
258  */
259 char *Threads_GetName(tTID ID)
260 {
261         if(ID == -1) {
262                 return Proc_GetCurThread()->ThreadName;
263         }
264         return Threads_GetThread(ID)->ThreadName;
265 }
266
267 /**
268  * \fn void Threads_SetPriority(tThread *Thread, int Pri)
269  * \brief Sets the priority of a task
270  * \param Thread        Thread to update ticket count (NULL means current thread)
271  * \param Pri   New priority
272  */
273 void Threads_SetPriority(tThread *Thread, int Pri)
274 {
275         // Get current thread
276         if(Thread == NULL)      Thread = Proc_GetCurThread();
277         // Bounds checking
278         // - If < 0, set to lowest priority
279         // - Minumum priority is actualy a high number, 0 is highest
280         if(Pri < 0)     Pri = MIN_PRIORITY;
281         if(Pri > MIN_PRIORITY)  Pri = MIN_PRIORITY;
282         
283         // Do we actually have to do anything?
284         if( Pri == Thread->Priority )   return;
285         
286         #if SCHEDULER_TYPE == SCHED_RR_PRI
287         if( Thread != Proc_GetCurThread() )
288         {
289                 SHORTLOCK( &glThreadListLock );
290                 // Remove from old priority
291                 Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread );
292                 // And add to new
293                 Threads_int_AddToList( &gaActiveThreads[Pri], Thread );
294                 Thread->Priority = Pri;
295                 SHORTREL( &glThreadListLock );
296         }
297         else
298                 Thread->Priority = Pri;
299         #else
300         // If this isn't the current thread, we need to lock
301         if( Thread != Proc_GetCurThread() )
302         {
303                 SHORTLOCK( &glThreadListLock );
304                 
305                 #if SCHEDULER_TYPE == SCHED_LOTTERY
306                 giFreeTickets -= caiTICKET_COUNTS[Thread->Priority] - caiTICKET_COUNTS[Pri];
307                 # if DEBUG_TRACE_TICKETS
308                 Log("Threads_SetTickets: new giFreeTickets = %i [-%i+%i]",
309                         giFreeTickets,
310                         caiTICKET_COUNTS[Thread->Priority], caiTICKET_COUNTS[Pri]);
311                 # endif
312                 #endif
313                 Thread->Priority = Pri;
314                 SHORTREL( &glThreadListLock );
315         }
316         else
317                 Thread->Priority = Pri;
318         #endif
319         
320         #if DEBUG_TRACE_STATE
321         Log("Threads_SetPriority: %p(%i %s) pri set %i",
322                 Thread, Thread->TID, Thread->ThreadName,
323                 Pri);
324         #endif
325 }
326
327 /**
328  * \brief Clone the TCB of the current thread
329  * \param Flags Flags for something... (What is this for?)
330  */
331 tThread *Threads_CloneTCB(Uint Flags)
332 {
333         tThread *cur = Proc_GetCurThread();
334         
335         // Allocate and duplicate
336         tThread *new = malloc(sizeof(tThread));
337         if(new == NULL) { errno = -ENOMEM; return NULL; }
338         memcpy(new, cur, sizeof(tThread));
339         
340         new->CurCPU = -1;
341         new->Next = NULL;
342         memset( &new->IsLocked, 0, sizeof(new->IsLocked));
343         new->Status = THREAD_STAT_PREINIT;
344         new->RetStatus = 0;
345         
346         // Get Thread ID
347         new->TID = giNextTID++;
348         new->Parent = cur;
349         new->bInstrTrace = 0;
350         
351         // Clone Name
352         new->ThreadName = strdup(cur->ThreadName);
353         
354         // Set Thread Group ID (PID)
355         if(Flags & CLONE_VM) {
356                 tProcess        *newproc, *oldproc;
357                 oldproc = cur->Process;
358                 new->Process = calloc( sizeof(struct sProcess), 1 );
359                 newproc = new->Process;
360                 newproc->PID = new->TID;
361                 if( Flags & CLONE_PGID )
362                         newproc->PGID = oldproc->PGID;
363                 else
364                         newproc->PGID = newproc->PID;
365                 newproc->UID = oldproc->UID;
366                 newproc->GID = oldproc->GID;
367                 newproc->MaxFD = oldproc->MaxFD;
368                 newproc->CurrentWorkingDir = oldproc->CurrentWorkingDir ? strdup( oldproc->CurrentWorkingDir ) : NULL;
369                 newproc->RootDir = oldproc->RootDir ? strdup( oldproc->RootDir ) : NULL;
370                 newproc->nThreads = 1;
371                 // Reference all handles in the VFS
372                 VFS_ReferenceUserHandles();
373                 
374                 // Add to global list
375                 newproc->Prev = NULL;
376                 // TODO: RWLock
377                 newproc->Next = gAllProcesses;
378                 gAllProcesses = newproc;
379
380                 newproc->FirstThread = new;
381                 new->ProcessNext = NULL;
382         }
383         else {
384                 new->Process->nThreads ++;
385                 new->Process = cur->Process;
386                 // TODO: Locking
387                 new->ProcessNext = new->Process->FirstThread;
388                 new->Process->FirstThread = new;
389         }
390         
391         // Messages are not inherited
392         new->Messages = NULL;
393         new->LastMessage = NULL;
394         
395         // Set State
396         new->Remaining = new->Quantum = cur->Quantum;
397         new->Priority = cur->Priority;
398         new->_errno = 0;
399         
400         // Set Signal Handlers
401         new->CurFaultNum = 0;
402         new->FaultHandler = cur->FaultHandler;
403         
404         // Maintain a global list of threads
405         SHORTLOCK( &glThreadListLock );
406         new->GlobalPrev = NULL; // Protect against bugs
407         new->GlobalNext = gAllThreads;
408         gAllThreads->GlobalPrev = new;
409         gAllThreads = new;
410         SHORTREL( &glThreadListLock );
411         
412         return new;
413 }
414
415 /**
416  * \brief Clone the TCB of the kernel thread
417  */
418 tThread *Threads_CloneThreadZero(void)
419 {
420         tThread *new;
421         
422         // Allocate and duplicate
423         new = malloc(sizeof(tThread));
424         if(new == NULL) {
425                 return NULL;
426         }
427         memcpy(new, &gThreadZero, sizeof(tThread));
428
429         new->Process->nThreads ++;
430         
431         new->CurCPU = -1;
432         new->Next = NULL;
433         memset( &new->IsLocked, 0, sizeof(new->IsLocked));
434         new->Status = THREAD_STAT_PREINIT;
435         new->RetStatus = 0;
436         
437         // Get Thread ID
438         new->TID = giNextTID++;
439         new->Parent = 0;
440         
441         // Clone Name
442         new->ThreadName = NULL;
443         
444         // Messages are not inherited
445         new->Messages = NULL;
446         new->LastMessage = NULL;
447         
448         // Set State
449         new->Remaining = new->Quantum = DEFAULT_QUANTUM;
450         new->Priority = DEFAULT_PRIORITY;
451         new->bInstrTrace = 0;
452         
453         // Set Signal Handlers
454         new->CurFaultNum = 0;
455         new->FaultHandler = 0;
456         
457         // Maintain a global list of threads
458         SHORTLOCK( &glThreadListLock );
459         new->GlobalPrev = NULL; // Protect against bugs
460         new->GlobalNext = gAllThreads;
461         gAllThreads->GlobalPrev = new;
462         gAllThreads = new;
463         SHORTREL( &glThreadListLock );
464         
465         return new;
466 }
467
468 /**
469  * \brief Wait for a task to change state
470  * \param TID   Thread ID to wait on (-1: Any child thread, 0: Any Child/Sibling, <-1: -PID)
471  * \param Status        Thread return status
472  * \return TID of child that changed state
473  */
474 tTID Threads_WaitTID(int TID, int *Status)
475 {       
476         // Any Child
477         if(TID == -1)
478         {
479                 Uint32 ev = Threads_WaitEvents(THREAD_EVENT_DEADCHILD);
480                 tTID    ret = -1;
481                 if( ev & THREAD_EVENT_DEADCHILD )
482                 {
483                         tThread * const us = Proc_GetCurThread();
484                         // A child died, get the TID
485                         ASSERT(us->LastDeadChild);
486                         tThread *dead_thread = us->LastDeadChild;
487                         us->LastDeadChild = dead_thread->Next;
488                         if( us->LastDeadChild )
489                                 Threads_PostEvent( us, THREAD_EVENT_DEADCHILD );
490                         else
491                                 Threads_ClearEvent( THREAD_EVENT_DEADCHILD );
492                         Mutex_Release(&us->DeadChildLock);
493                         
494                         ret = dead_thread->TID;
495                         // - Mark as dead (as opposed to undead)
496                         if( dead_thread->Status != THREAD_STAT_ZOMBIE ) {
497                                 Log_Error("Thread", "Thread %p(%i %s) is not ZOMBIE, instead %s",
498                                         dead_thread, dead_thread->TID, dead_thread->ThreadName,
499                                         (dead_thread->Status < ciTHREAD_STAT_COUNT ? casTHREAD_STAT[dead_thread->Status] : "?")
500                                         );
501                                 ASSERTC(dead_thread->Status, ==, THREAD_STAT_ZOMBIE);
502                         }
503                         dead_thread->Status = THREAD_STAT_DEAD;
504                         // - Set return status
505                         if(Status)
506                                 *Status = dead_thread->RetStatus;
507                         
508                         Threads_Delete( dead_thread );
509                 }
510                 else
511                 {
512                         Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Woken with no child");
513                 }
514                 return ret;
515         }
516         
517         // Any peer/child thread
518         if(TID == 0) {
519                 Log_Error("Threads", "TODO: Threads_WaitTID(TID=0) - Any Child/Sibling");
520                 return -1;
521         }
522         
523         // TGID = abs(TID)
524         if(TID < -1) {
525                 Log_Error("Threads", "TODO: Threads_WaitTID(TID<0) - TGID");
526                 return -1;
527         }
528         
529         // Specific Thread
530         if(TID > 0)
531         {
532                 // TODO: Register on thread to be poked when it dies
533                 tTID    ret;
534                 // NOTE: Race condition - Other child dies, desired child dies, first death is 'lost'
535                 while( (ret = Threads_WaitTID(-1, Status)) != TID )
536                 {
537                         if( ret == -1 )
538                                 break;
539                 }
540                 return ret;
541         }
542         
543         return -1;
544 }
545
546 /**
547  * \brief Gets a thread given its TID
548  * \param TID   Thread ID
549  * \return Thread pointer
550  */
551 tThread *Threads_GetThread(Uint TID)
552 {
553         tThread *thread;
554         
555         // Search global list
556         for( thread = gAllThreads; thread; thread = thread->GlobalNext )
557         {
558                 if(thread->TID == TID)
559                         return thread;
560         }
561
562         Log_Notice("Threads", "Unable to find TID %i on main list\n", TID);
563         
564         return NULL;
565 }
566
567 /**
568  * \brief Deletes an entry from a list
569  * \param List  Pointer to the list head
570  * \param Thread        Thread to find
571  * \return \a Thread
572  */
573 tThread *Threads_int_DelFromQueue(tThreadList *List, tThread *Thread)
574 {
575         tThread *ret, *prev = NULL;
576         
577         for(ret = List->Head;
578                 ret && ret != Thread;
579                 prev = ret, ret = ret->Next
580                 );
581         
582         // Is the thread on the list
583         if(!ret) {
584                 //LogF("%p(%s) is not on list %p\n", Thread, Thread->ThreadName, List);
585                 return NULL;
586         }
587         
588         if( !prev ) {
589                 List->Head = Thread->Next;
590                 //LogF("%p(%s) removed from head of %p\n", Thread, Thread->ThreadName, List);
591         }
592         else {
593                 prev->Next = Thread->Next;
594                 //LogF("%p(%s) removed from %p (prev=%p)\n", Thread, Thread->ThreadName, List, prev);
595         }
596         if( Thread->Next == NULL )
597                 List->Tail = prev;
598         
599         return Thread;
600 }
601
602 void Threads_int_AddToList(tThreadList *List, tThread *Thread)
603 {
604         if( List->Head )
605                 List->Tail->Next = Thread;
606         else
607                 List->Head = Thread;
608         List->Tail = Thread;
609         Thread->Next = NULL;
610 }
611
612 /**
613  * \brief Exit the current process (or another?)
614  * \param TID   Thread ID to kill
615  * \param Status        Exit status
616  */
617 void Threads_Exit(int TID, int Status)
618 {
619         if( TID == 0 )
620                 Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF );
621         else
622                 Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF );
623         
624         // Halt forever, just in case
625         for(;;) HALT();
626 }
627
628 /**
629  * \fn void Threads_Kill(tThread *Thread, int Status)
630  * \brief Kill a thread
631  * \param Thread        Thread to kill
632  * \param Status        Status code to return to the parent
633  */
634 void Threads_Kill(tThread *Thread, int Status)
635 {
636          int    isCurThread = Thread == Proc_GetCurThread();
637         
638         // TODO: Disown all children?
639         #if 1
640         {
641                 // TODO: I should keep a .Children list
642                 for(tThread* child = gAllThreads; child; child = child->GlobalNext)
643                 {
644                         if(child->Parent == Thread)
645                                 child->Parent = &gThreadZero;
646                 }
647         }
648         #endif
649         
650         ///\note Double lock is needed due to overlap of lock areas
651         
652         // Lock thread (stop us recieving messages)
653         SHORTLOCK( &Thread->IsLocked );
654         
655         // Clear Message Queue
656         while( Thread->Messages )
657         {
658                 tMsg    *msg = Thread->Messages->Next;
659                 free( Thread->Messages );
660                 Thread->Messages = msg;
661         }
662         
663         // Lock thread list
664         SHORTLOCK( &glThreadListLock );
665         
666         switch(Thread->Status)
667         {
668         case THREAD_STAT_PREINIT:       // Only on main list
669                 break;
670         
671         // Currently active thread
672         case THREAD_STAT_ACTIVE:
673                 if( Thread != Proc_GetCurThread() )
674                 {
675                         #if SCHEDULER_TYPE == SCHED_RR_PRI
676                         tThreadList     *list = &gaActiveThreads[Thread->Priority];
677                         #else
678                         tThreadList     *list = &gActiveThreads;
679                         #endif
680                         if( Threads_int_DelFromQueue( list, Thread ) )
681                         {
682                         }
683                         else
684                         {
685                                 Log_Warning("Threads",
686                                         "Threads_Kill - Thread %p(%i,%s) marked as active, but not on list",
687                                         Thread, Thread->TID, Thread->ThreadName
688                                         );
689                         }
690                         #if SCHEDULER_TYPE == SCHED_LOTTERY
691                         giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ];
692                         #endif
693                 }
694                 // Ensure that we are not rescheduled
695                 Thread->Remaining = 0;  // Clear Remaining Quantum
696                 Thread->Quantum = 0;    // Clear Quantum to indicate dead thread
697                         
698                 // Update bookkeeping
699                 giNumActiveThreads --;
700                 break;
701         // Kill it while it sleeps!
702         case THREAD_STAT_SLEEPING:
703                 if( !Threads_int_DelFromQueue( &gSleepingThreads, Thread ) )
704                 {
705                         Log_Warning("Threads",
706                                 "Threads_Kill - Thread "PRIthread_fmt" marked as sleeping, but not on list",
707                                 PRIthread_args(Thread)
708                                 );
709                 }
710                 break;
711         
712         // Brains!... You cannot kill something that is already dead
713         case THREAD_STAT_ZOMBIE:
714                 Log_Warning("Threads", "Threads_Kill - Thread %p(%i,%s) is undead, you cannot kill it",
715                         Thread, Thread->TID, Thread->ThreadName);
716                 SHORTREL( &glThreadListLock );
717                 SHORTREL( &Thread->IsLocked );
718                 return ;
719         
720         default:
721                 Log_Warning("Threads", "Threads_Kill - BUG Un-checked status (%i)",
722                         Thread->Status);
723                 break;
724         }
725         
726         // Save exit status
727         Thread->RetStatus = Status;
728
729         Thread->Status = THREAD_STAT_ZOMBIE;
730         SHORTREL( &glThreadListLock );
731         // TODO: It's possible that we could be timer-preempted here, should disable that... somehow
732         Mutex_Acquire( &Thread->Parent->DeadChildLock );        // released by parent
733         Thread->Next = Thread->Parent->LastDeadChild;
734         Thread->Parent->LastDeadChild = Thread;
735         Threads_PostEvent( Thread->Parent, THREAD_EVENT_DEADCHILD );
736         
737         // Process cleanup happens on reaping
738         Log("Thread "PRIthread_fmt" went *hurk* (%i) (isCurThread=%B)", PRIthread_args(Thread), Status, isCurThread);
739         //Log("Thread status = %i %s", Thread->Status, casTHREAD_STAT[Thread->Status]);
740         
741         SHORTREL( &Thread->IsLocked );
742         
743         // And, reschedule
744         if(isCurThread)
745         {
746                 for( ;; )
747                         Proc_Reschedule();
748         }
749 }
750
751 /**
752  * \brief Yield remainder of the current thread's timeslice
753  */
754 void Threads_Yield(void)
755 {
756 //      Log("Threads_Yield: by %p", __builtin_return_address(0));
757         Proc_Reschedule();
758 }
759
760 /**
761  * \breif Wait for the thread status to not be a specified value
762  */
763 void Threads_int_WaitForStatusEnd(enum eThreadStatus Status)
764 {
765         tThread *us = Proc_GetCurThread();
766         LOG("us = %p(%i %s), status=%i", us, us->TID, us->ThreadName, Status);
767         ASSERT(Status != THREAD_STAT_ACTIVE);
768         ASSERT(Status != THREAD_STAT_DEAD);
769         while( us->Status == Status )
770         {
771                 Proc_Reschedule();
772                 if( us->Status == Status )
773                         Debug("Thread %p(%i %s) rescheduled while in %s state for %p",
774                                 us, us->TID, us->ThreadName,
775                                 casTHREAD_STAT[Status],
776                                 __builtin_return_address(0));
777         }
778 }
779
780 int Threads_int_Sleep(enum eThreadStatus Status, void *Ptr, int Num, tThread **ListHead, tThread **ListTail, tShortSpinlock *Lock)
781 {
782         SHORTLOCK( &glThreadListLock );
783         tThread *us = Threads_RemActive();
784         us->Next = NULL;
785         // - Mark as sleeping
786         us->Status = Status;
787         us->WaitPointer = Ptr;
788         us->RetStatus = Num;    // Use RetStatus as a temp variable
789                 
790         // - Add to waiting
791         if( ListTail ) {
792                 if(*ListTail) {
793                         (*ListTail)->Next = us;
794                 }
795                 else {
796                         *ListHead = us;
797                 }
798                 *ListTail = us;
799         }
800         else if( ListHead ) {
801                 us->Next = *ListHead;
802                 *ListHead = us;
803         }
804         else {
805                 // Nothing
806         }
807         
808         //if( Proc_ThreadSync(us) )
809         //      return ;
810         SHORTREL( &glThreadListLock );
811         if( Lock )
812                 SHORTREL( Lock );
813         Threads_int_WaitForStatusEnd(Status);
814         us->WaitPointer = NULL;
815         return us->RetStatus;
816 }
817
818 /**
819  * \fn void Threads_Sleep(void)
820  * \brief Take the current process off the run queue
821  */
822 void Threads_Sleep(void)
823 {
824         tThread *cur = Proc_GetCurThread();
825         
826         // Acquire Spinlock
827         SHORTLOCK( &glThreadListLock );
828         
829         // Don't sleep if there is a message waiting
830         if( cur->Messages ) {
831                 SHORTREL( &glThreadListLock );
832                 return;
833         }
834         
835         // Remove us from running queue
836         Threads_RemActive();
837         // Mark thread as sleeping
838         cur->Status = THREAD_STAT_SLEEPING;
839         
840         // Add to Sleeping List (at the top)
841         Threads_int_AddToList( &gSleepingThreads, cur );
842         
843         #if DEBUG_TRACE_STATE
844         Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName);
845         #endif
846         
847         // Release Spinlock
848         SHORTREL( &glThreadListLock );
849         Threads_int_WaitForStatusEnd(THREAD_STAT_SLEEPING);
850 }
851
852
853 /**
854  * \brief Wakes a sleeping/waiting thread up
855  * \param Thread        Thread to wake
856  * \return Boolean Failure (Returns ERRNO)
857  * \warning This should ONLY be called with task switches disabled
858  */
859 int Threads_Wake(tThread *Thread)
860 {
861         if(!Thread)
862                 return -EINVAL;
863         
864         switch(Thread->Status)
865         {
866         case THREAD_STAT_ACTIVE:
867                 Log("Threads_Wake - Waking awake thread (%i)", Thread->TID);
868                 return -EALREADY;
869         
870         case THREAD_STAT_SLEEPING:
871                 // Remove from sleeping queue
872                 SHORTLOCK( &glThreadListLock );
873                 Threads_int_DelFromQueue(&gSleepingThreads, Thread);
874                 SHORTREL( &glThreadListLock );
875                 
876                 Threads_AddActive( Thread );
877                 
878                 #if DEBUG_TRACE_STATE
879                 Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName);
880                 #endif
881                 return -EOK;
882         
883         case THREAD_STAT_SEMAPHORESLEEP: {
884                 tSemaphore      *sem;
885                 tThread *th, *prev=NULL;
886                 
887                 sem = Thread->WaitPointer;
888                 
889                 SHORTLOCK( &sem->Protector );
890                 
891                 // Remove from sleeping queue
892                 for( th = sem->Waiting; th; prev = th, th = th->Next )
893                         if( th == Thread )      break;
894                 if( th )
895                 {
896                         if(prev)
897                                 prev->Next = Thread->Next;
898                         else
899                                 sem->Waiting = Thread->Next;
900                         if(sem->LastWaiting == Thread)
901                                 sem->LastWaiting = prev;
902                 }
903                 else
904                 {
905                         prev = NULL;
906                         for( th = sem->Signaling; th; prev = th, th = th->Next )
907                                 if( th == Thread )      break;
908                         if( !th ) {
909                                 Log_Warning("Threads", "Thread %p(%i %s) is not on semaphore %p(%s:%s)",
910                                         Thread, Thread->TID, Thread->ThreadName,
911                                         sem, sem->ModName, sem->Name);
912                                 return -EINTERNAL;
913                         }
914                         
915                         if(prev)
916                                 prev->Next = Thread->Next;
917                         else
918                                 sem->Signaling = Thread->Next;
919                         if(sem->LastSignaling == Thread)
920                                 sem->LastSignaling = prev;
921                 }
922                 
923                 Thread->RetStatus = 0;  // It didn't get anything
924                 Threads_AddActive( Thread );
925                 
926                 #if DEBUG_TRACE_STATE
927                 Log("Threads_Sleep: %p(%i %s) woken from semaphore", Thread, Thread->TID, Thread->ThreadName);
928                 #endif
929                 SHORTREL( &sem->Protector );
930                 } return -EOK;
931         
932         case THREAD_STAT_WAITING:
933                 Warning("Threads_Wake - Waiting threads are not currently supported");
934                 return -ENOTIMPL;
935         
936         case THREAD_STAT_DEAD:
937                 Warning("Threads_Wake - Attempt to wake dead thread (%i)", Thread->TID);
938                 return -ENOTIMPL;
939         
940         default:
941                 Log_Warning("Threads", "Threads_Wake - Unknown process status (%i)", Thread->Status);
942                 return -EINTERNAL;
943         }
944 }
945
946 /**
947  * \brief Wake a thread given the TID
948  * \param TID   Thread ID to wake
949  * \return Boolean Faulure (errno)
950  */
951 int Threads_WakeTID(tTID TID)
952 {
953         tThread *thread = Threads_GetThread(TID);
954          int    ret;
955         if(!thread)
956                 return -ENOENT;
957         ret = Threads_Wake( thread );
958         //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread);
959         return ret;
960 }
961
962 void Threads_ToggleTrace(int TID)
963 {
964         tThread *thread = Threads_GetThread(TID);
965         if(!thread)     return ;
966         thread->bInstrTrace = !thread->bInstrTrace;
967 }
968
969 /**
970  * \brief Adds a thread to the active queue
971  */
972 void Threads_AddActive(tThread *Thread)
973 {
974         #if DEBUG_TRACE_ACTIVEQUEUE
975         Debug("Threads_AddActive("PRIthread_fmt")", PRIthread_args(Thread));
976         #endif
977         SHORTLOCK( &glThreadListLock );
978         
979         if( Thread->Status == THREAD_STAT_ACTIVE )
980         {
981                 tThread *cur = Proc_GetCurThread();
982                 Log_KernelPanic("Threads",
983                         "ret=%p CPU%i "PRIthread_fmt" is adding "PRIthread_fmt" when it is active",
984                         __builtin_return_address(0),
985                         GetCPUNum(), PRIthread_args(cur), PRIthread_args(Thread));
986                 SHORTREL( &glThreadListLock );
987                 return ;
988         }
989         
990         // Set state
991         Thread->Status = THREAD_STAT_ACTIVE;
992         // Add to active list
993         // - Thread can be the current thread if we're interrupted just before
994         //   Proc_Reschedule in a sleep state.
995         if( Thread != Proc_GetCurThread() )
996         {
997                 #if SCHEDULER_TYPE == SCHED_RR_PRI
998                 tThreadList     *list = &gaActiveThreads[Thread->Priority];
999                 #else
1000                 tThreadList     *list = &gActiveThreads;
1001                 #endif
1002                 #if DEBUG_TRACE_ACTIVEQUEUE
1003                 Debug(" - Head="PRIthread_fmt",Tail="PRIthread_fmt"",
1004                         PRIthread_args(list->Head),
1005                         PRIthread_args(list->Tail)
1006                         );
1007                 #endif
1008                 Threads_int_AddToList( list, Thread );
1009         }
1010         
1011         // Update bookkeeping
1012         giNumActiveThreads ++;
1013         
1014         #if SCHEDULER_TYPE == SCHED_LOTTERY
1015         {
1016                  int    delta;
1017                 // Only change the ticket count if the thread is un-scheduled
1018                 if(Thread->CurCPU != -1)
1019                         delta = 0;
1020                 else
1021                         delta = caiTICKET_COUNTS[ Thread->Priority ];
1022                 
1023                 giFreeTickets += delta;
1024                 # if DEBUG_TRACE_TICKETS
1025                 Log("CPU%i %p (%i %s) added, new giFreeTickets = %i [+%i]",
1026                         GetCPUNum(), Thread, Thread->TID, Thread->ThreadName,
1027                         giFreeTickets, delta
1028                         );
1029                 # endif
1030         }
1031         #endif
1032         
1033         SHORTREL( &glThreadListLock );
1034 }
1035
1036 /**
1037  * \brief Removes the current thread from the active queue
1038  * \warning This should ONLY be called with the lock held
1039  * \return Current thread pointer
1040  */
1041 tThread *Threads_RemActive(void)
1042 {
1043         tThread *us = Proc_GetCurThread();
1044         #if DEBUG_TRACE_ACTIVEQUEUE
1045         Debug("Threads_RemActive(%p(%i %s))", us, us->TID, us->ThreadName);
1046         #endif
1047         giNumActiveThreads --;
1048         return us;
1049 }
1050
1051 /**
1052  * \fn void Threads_SetFaultHandler(Uint Handler)
1053  * \brief Sets the signal handler for a signal
1054  */
1055 void Threads_SetFaultHandler(Uint Handler)
1056 {       
1057         //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
1058         Proc_GetCurThread()->FaultHandler = Handler;
1059 }
1060
1061 /**
1062  * \fn void Threads_Fault(int Num)
1063  * \brief Calls a fault handler
1064  */
1065 void Threads_Fault(int Num)
1066 {
1067         tThread *thread = Proc_GetCurThread();
1068         
1069         if(!thread)     return ;
1070         
1071         Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
1072         
1073         switch(thread->FaultHandler)
1074         {
1075         case 0: // Panic?
1076                 Threads_Kill(thread, -1);
1077                 HALT();
1078                 return ;
1079         case 1: // Dump Core?
1080                 Threads_Kill(thread, -1);
1081                 HALT();
1082                 return ;
1083         }
1084         
1085         // Double Fault? Oh, F**k
1086         if(thread->CurFaultNum != 0) {
1087                 Log_Warning("Threads", "Threads_Fault: Double fault on %i", thread->TID);
1088                 Threads_Kill(thread, -1);       // For now, just kill
1089                 HALT();
1090         }
1091         
1092         thread->CurFaultNum = Num;
1093         
1094         Proc_CallFaultHandler(thread);
1095 }
1096
1097 /**
1098  * \fn void Threads_SegFault(tVAddr Addr)
1099  * \brief Called when a Segment Fault occurs
1100  */
1101 void Threads_SegFault(tVAddr Addr)
1102 {
1103         tThread *cur = Proc_GetCurThread();
1104         cur->bInstrTrace = 0;
1105         Log_Warning("Threads", "Thread #%i committed a segfault at address %p", cur->TID, Addr);
1106         MM_DumpTables(0, USER_MAX);
1107         Threads_Fault( 1 );
1108         //Threads_Exit( 0, -1 );
1109 }
1110
1111
1112 void Threads_PostSignalTo(tThread *Thread, int SignalNum)
1113 {
1114         ASSERT(Thread);
1115         Log_Debug("Threads", "Signalling %i(%s) with %i", Thread->TID, Thread->ThreadName, SignalNum);
1116         Thread->PendingSignal = SignalNum;
1117         Threads_PostEvent(Thread, THREAD_EVENT_SIGNAL);
1118 }
1119 void Threads_PostSignal(int SignalNum)
1120 {
1121         Threads_PostSignalTo( Proc_GetCurThread(), SignalNum );
1122 }
1123
1124 void Threads_SignalGroup(tPGID PGID, int Signal)
1125 {
1126         for( tProcess *proc = gAllProcesses; proc; proc = proc->Next )
1127         {
1128                 if(proc->PGID == PGID)
1129                 {
1130                         Threads_PostSignalTo(proc->FirstThread, Signal);
1131                 }
1132         }
1133 }
1134
1135 /**
1136  */
1137 int Threads_GetPendingSignal(void)
1138 {
1139         tThread *cur = Proc_GetCurThread();
1140         
1141         // Atomic AND with 0 fetches and clears in one operation
1142         int ret = __sync_fetch_and_and( &cur->PendingSignal, 0 );
1143         if( ret )
1144         {
1145                 Log_Debug("Threads", "Thread %i(%s) has signal %i pending",
1146                         cur->TID, cur->ThreadName, ret);
1147         }
1148         return ret;
1149 }
1150
1151 /*
1152  * \brief Update the current thread's signal handler
1153  */
1154 void Threads_SetSignalHandler(int SignalNum, void *Handler)
1155 {
1156         if( SignalNum <= 0 || SignalNum >= NSIGNALS )
1157                 return ;
1158         if( !MM_IsUser(Handler) )
1159                 return ;
1160         Proc_GetCurThread()->Process->SignalHandlers[SignalNum] = Handler;
1161 }
1162
1163 /**
1164  * \brief Gets the registered (or default, if none set) handler for a signal.
1165  * \return Handler function pointer, OR NULL if no signal to be ignored
1166  */
1167 void *Threads_GetSignalHandler(int SignalNum)
1168 {
1169         // TODO: Core dump
1170         void *User_Signal_Core = User_Signal_Kill;
1171         
1172         if( SignalNum <= 0 || SignalNum >= NSIGNALS )
1173                 return NULL;
1174         void *ret = Proc_GetCurThread()->Process->SignalHandlers[SignalNum];
1175         if( !ret || (SignalNum == SIGKILL || SignalNum == SIGSTOP) )
1176         {
1177                 // Defaults
1178                 switch(SignalNum)
1179                 {
1180                 case SIGHUP:
1181                 case SIGINT:
1182                         ret = User_Signal_Kill;
1183                         break;
1184                 case SIGQUIT:
1185                 case SIGILL:
1186                 case SIGABRT:
1187                 case SIGFPE:
1188                         ret = User_Signal_Core;
1189                         break;
1190                 case SIGKILL:
1191                         ret = User_Signal_Kill;
1192                         break;
1193                 case SIGSEGV:
1194                         ret = User_Signal_Core;
1195                         break;
1196                 case SIGPIPE:
1197                 case SIGALRM:
1198                 case SIGTERM:
1199                         ret = User_Signal_Kill;
1200                         break;
1201                 default:
1202                         ret = NULL;
1203                         break;
1204                 }
1205         }
1206         Log_Debug("Threads", "Handler %p for signal %i", ret, SignalNum);
1207         return ret;
1208 }
1209
1210 // --- Process Structure Access Functions ---
1211 tPGID Threads_GetPGID(void)
1212 {
1213         return Proc_GetCurThread()->Process->PGID;
1214 }
1215 tPID Threads_GetPID(void)
1216 {
1217         return Proc_GetCurThread()->Process->PID;
1218 }
1219 tTID Threads_GetTID(void)
1220 {
1221         return Proc_GetCurThread()->TID;
1222 }
1223 tUID Threads_GetUID(void)
1224 {
1225         return Proc_GetCurThread()->Process->UID;
1226 }
1227 tGID Threads_GetGID(void)
1228 {
1229         return Proc_GetCurThread()->Process->GID;
1230 }
1231
1232 int Threads_SetUID(tUID ID)
1233 {
1234         tThread *t = Proc_GetCurThread();
1235         if( t->Process->UID != 0 ) {
1236                 errno = -EACCES;
1237                 return -1;
1238         }
1239         Log_Debug("Threads", "PID %i's UID set to %i", t->Process->PID, ID);
1240         t->Process->UID = ID;
1241         return 0;
1242 }
1243
1244 int Threads_SetGID(tGID ID)
1245 {
1246         tThread *t = Proc_GetCurThread();
1247         if( t->Process->UID != 0 ) {
1248                 errno = -EACCES;
1249                 return -1;
1250         }
1251         Log_Debug("Threads", "PID %i's GID set to %i", t->Process->PID, ID);
1252         t->Process->GID = ID;
1253         return 0;
1254 }
1255
1256 // --- Per-thread storage ---
1257 int *Threads_GetErrno(void)
1258 {
1259         return &Proc_GetCurThread()->_errno;
1260 }
1261
1262 // --- Configuration ---
1263 int *Threads_GetMaxFD(tProcess *Process)
1264 {
1265         if(!Process)    Process = Proc_GetCurThread()->Process;
1266         return &Process->MaxFD;
1267 }
1268 char **Threads_GetChroot(tProcess *Process)
1269 {
1270         if(!Process)    Process = Proc_GetCurThread()->Process;
1271         return &Process->RootDir;
1272 }
1273 char **Threads_GetCWD(tProcess *Process)
1274 {
1275         if(!Process)    Process = Proc_GetCurThread()->Process;
1276         return &Process->CurrentWorkingDir;
1277 }
1278 // ---
1279
1280 void Threads_int_DumpThread(tThread *thread)
1281 {
1282         if( !thread ) {
1283                 Log(" %p NULL", thread);
1284                 return ;
1285         }
1286         if( !CheckMem(thread, sizeof(tThread)) ) {
1287                 Log(" %p INVAL", thread);
1288                 return ;
1289         }
1290         tPID    pid = (thread->Process ? thread->Process->PID : -1);
1291         const char      *statstr = (thread->Status < sizeof(casTHREAD_STAT)/sizeof(casTHREAD_STAT[0])
1292                 ? casTHREAD_STAT[thread->Status] : "");
1293         Log(" %p %i (%i) - %s (CPU %i) - %i (%s)",
1294                 thread, thread->TID, pid, thread->ThreadName, thread->CurCPU,
1295                 thread->Status, statstr
1296                 );
1297         switch(thread->Status)
1298         {
1299         case THREAD_STAT_MUTEXSLEEP:
1300                 Log("  Mutex Pointer: %p", thread->WaitPointer);
1301                 break;
1302         case THREAD_STAT_RWLOCKSLEEP:
1303                 Log("  Lock Pointer: %p", thread->WaitPointer);
1304                 Log("  Lock Name: %s",
1305                         ((tRWLock*)thread->WaitPointer)->Name);
1306                 break;
1307         case THREAD_STAT_SEMAPHORESLEEP:
1308                 Log("  Semaphore Pointer: %p", thread->WaitPointer);
1309                 Log("  Semaphore Name: %s:%s", 
1310                         ((tSemaphore*)thread->WaitPointer)->ModName,
1311                         ((tSemaphore*)thread->WaitPointer)->Name
1312                         );
1313                 break;
1314         case THREAD_STAT_EVENTSLEEP:
1315                 Log("  Event Mask: %x", thread->RetStatus);
1316                 break;
1317         case THREAD_STAT_ZOMBIE:
1318                 Log("  Return Status: %i", thread->RetStatus);
1319                 break;
1320         default:        break;
1321         }
1322         Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
1323         Log("  KStack %p", thread->KernelStack);
1324         if( thread->bInstrTrace )
1325                 Log("  Tracing Enabled");
1326         Proc_DumpThreadCPUState(thread);
1327 }
1328
1329 /**
1330  * \fn void Threads_Dump(void)
1331  */
1332 void Threads_DumpActive(void)
1333 {
1334         Log("Active Threads: (%i reported)", giNumActiveThreads);
1335         
1336         #if SCHEDULER_TYPE == SCHED_RR_PRI
1337         for( int i = 0; i < MIN_PRIORITY+1; i++ )
1338         {
1339                 tThreadList *list = &gaActiveThreads[i];
1340         #else
1341                 tThreadList *list = &gActiveThreads;
1342         #endif
1343                 for(tThread *thread = list->Head; thread; thread = thread->Next)
1344                 {
1345                         Threads_int_DumpThread(thread);
1346                         if(thread->Status != THREAD_STAT_ACTIVE)
1347                                 Log("  ERROR State (%i) != THREAD_STAT_ACTIVE (%i)",
1348                                         thread->Status, THREAD_STAT_ACTIVE);
1349                 }
1350         
1351         #if SCHEDULER_TYPE == SCHED_RR_PRI
1352         }
1353         #endif
1354 }
1355
1356 /**
1357  * \fn void Threads_Dump(void)
1358  * \brief Dumps a list of currently running threads
1359  */
1360 void Threads_Dump(void)
1361 {
1362         Log("--- Thread Dump ---");
1363         Threads_DumpActive();
1364         
1365         Log("All Threads:");
1366         for(tThread *thread = gAllThreads; thread; thread = thread->GlobalNext)
1367         {
1368                 Threads_int_DumpThread(thread);
1369         }
1370 }
1371
1372 tThread *Threads_int_GetRunnable(void)
1373 {
1374         #if SCHEDULER_TYPE == SCHED_LOTTERY
1375         // -----------------------------------
1376         // Lottery Scheduler
1377         // -----------------------------------
1378         #if DEBUG_VALIDATE_TICKET_COUNTS
1379         {
1380                 int total_tickets = 0;
1381                 for(const tThread *thread = gActiveThreads.Head; thread; thread = thread->Next)
1382                 {
1383                         if(thread->Status != THREAD_STAT_ACTIVE)
1384                                 Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i",
1385                                         thread, thread->TID, thread->ThreadName, thread->Status);
1386                         if(thread->Next == thread) {
1387                                 Panic("Bookkeeping fail - %p %i(%s) loops back on itself",
1388                                         thread, thread->TID, thread->ThreadName, thread->Status);
1389                         }
1390                         total_tickets += caiTICKET_COUNTS[ thread->Priority ];
1391                 }
1392                 if(total_tickets != giFreeTickets)
1393                 {
1394                         Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
1395                                 giFreeTickets, total_tickets, CPU);
1396                 }
1397         }
1398         # endif
1399         
1400         // No free tickets (all tasks delegated to cores)
1401         if( giFreeTickets == 0 )
1402         {
1403                 return NULL;
1404         }
1405         
1406         // Get the ticket number
1407         int ticket = rand() % giFreeTickets;
1408         int number = ticket;
1409         
1410         // Find the next thread
1411         tThread **pnp = &gActiveThreads.Head;
1412         tThread *thread;
1413         for(thread = gActiveThreads.Head; thread; pnp = &thread->Next, thread = thread->Next )
1414         {
1415                 if( caiTICKET_COUNTS[ thread->Priority ] > number)
1416                         break;
1417                 number -= caiTICKET_COUNTS[ thread->Priority ];
1418         }
1419         
1420         // If we didn't find a thread, something went wrong
1421         if(thread == NULL)
1422         {
1423                 int total_tickets = 0;
1424                 for(thread=gActiveThreads;thread;thread=thread->Next) {
1425                         if(thread->CurCPU >= 0) continue;
1426                         total_tickets += caiTICKET_COUNTS[ thread->Priority ];
1427                 }
1428                 Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
1429                         giFreeTickets, total_tickets);
1430         }
1431
1432         // Remove
1433         *pnp = thread->Next;
1434         if( !thread->Next )
1435                 gActiveThreads.Tail = prev;             
1436
1437         giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ];
1438         # if DEBUG_TRACE_TICKETS
1439         LogF("Log: CPU%i allocated %p (%i %s), (%i [-%i] tickets in pool), \n",
1440                 CPU, thread, thread->TID, thread->ThreadName,
1441                 giFreeTickets, caiTICKET_COUNTS[ thread->Priority ]);
1442         # endif
1443         return thread;
1444         
1445         #elif SCHEDULER_TYPE == SCHED_RR_PRI
1446         
1447         // -----------------------------------
1448         // Priority based round robin scheduler
1449         // -----------------------------------
1450         for( int i = 0; i < MIN_PRIORITY + 1; i ++ )
1451         {
1452                 if( gaActiveThreads[i].Head == NULL )
1453                         continue ;
1454         
1455                 tThread *thread = gaActiveThreads[i].Head;
1456
1457                 if( thread->Status != THREAD_STAT_ACTIVE ) {
1458                         for( const tThread *t = gaActiveThreads[i].Head; t; t = t->Next )
1459                                 LogF("- %p(%i %s)\n", t, t->TID, t->ThreadName);
1460                         Panic("Thread %p(%i %s) from pqueue %i is active!",
1461                                 thread, thread->TID, thread->ThreadName, i);
1462                 }
1463
1464                 // Remove from head
1465                 gaActiveThreads[i].Head = thread->Next;
1466                 if(!thread->Next)
1467                         gaActiveThreads[i].Tail = NULL;
1468                 thread->Next = NULL;
1469                 return thread;
1470         }
1471         return NULL;
1472         
1473         #elif SCHEDULER_TYPE == SCHED_RR_SIM
1474         
1475         // -----------------------------------
1476         // Single-list round-robin
1477         // -----------------------------------
1478         tThread *thread = gActiveThreads.Head;
1479         LOG("thread = %p", thread);
1480         if( thread )
1481         {
1482                 gActiveThreads.Head = thread->Next;
1483                 if(!thread->Next)
1484                         gaActiveThreads.Tail = NULL;
1485                 thread->Next = NULL;
1486         }
1487         return thread;
1488         #else
1489         # error "Unimplemented scheduling algorithm"
1490         return NULL;
1491         #endif
1492 }
1493
1494 /**
1495  * \brief Gets the next thread to run
1496  * \param CPU   Current CPU
1497  * \param Last  The thread the CPU was running
1498  */
1499 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
1500 {
1501         ASSERT( CPU_HAS_LOCK(&glThreadListLock) );
1502         
1503         // Don't change threads if the current CPU has switches disabled
1504         if( gaThreads_NoTaskSwitch[CPU] ) {
1505                 LOG("- Denied");
1506                 return Last;
1507         }
1508         
1509         // Make sure the current (well, old) thread is marked as de-scheduled   
1510         if(Last)        Last->CurCPU = -1;
1511
1512         // No active threads, just take a nap
1513         if(giNumActiveThreads == 0) {
1514                 LOG("- No active");
1515                 #if DEBUG_TRACE_TICKETS
1516                 Log("No active threads");
1517                 #endif
1518                 return NULL;
1519         }
1520
1521         // Allow the old thread to be scheduled again
1522         if( Last )
1523         {
1524                 if( Last->Status == THREAD_STAT_ACTIVE ) {
1525                         tThreadList     *list;
1526                         #if SCHEDULER_TYPE == SCHED_LOTTERY
1527                         giFreeTickets += caiTICKET_COUNTS[ Last->Priority ];
1528                         # if DEBUG_TRACE_TICKETS
1529                         LogF("Log: CPU%i released %p (%i %s) into the pool (%i [+%i] tickets in pool)\n",
1530                                 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets,
1531                                 caiTICKET_COUNTS[ Last->Priority ]);
1532                         # endif
1533                         #endif
1534                         
1535                         #if SCHEDULER_TYPE == SCHED_RR_PRI
1536                         list = &gaActiveThreads[ Last->Priority ];
1537                         #else
1538                         list = &gActiveThreads;
1539                         #endif
1540                         // Add to end of list
1541                         Threads_int_AddToList( list, Last );
1542                         #if DEBUG_TRACE_ACTIVEQUEUE > 1
1543                         Debug("Threads_GetNextToRun: Append thread %p(%i %s)",
1544                                 Last, Last->TID, Last->ThreadName);
1545                         #endif
1546                 }
1547                 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
1548                 else
1549                         LogF("Log: CPU%i released %p (%i %s)->Status = %i (Released,not in pool)\n",
1550                                 CPU, Last, Last->TID, Last->ThreadName, Last->Status);
1551                 #endif
1552                 Last->CurCPU = -1;
1553         }
1554
1555         // Call actual scheduler        
1556         tThread *thread = Threads_int_GetRunnable();
1557         
1558         // Anything to do?
1559         if( thread )
1560         {
1561                 if( thread->Status != THREAD_STAT_ACTIVE )
1562                 {
1563                         LogF("Thread %p(%i %s) scheduled while not active\n",
1564                                 thread, thread->TID, thread->ThreadName);
1565                 }
1566
1567                 // Make the new thread non-schedulable
1568                 thread->CurCPU = CPU;
1569                 thread->Remaining = thread->Quantum;
1570                 
1571                 #if DEBUG_TRACE_SCHEDULE
1572                 Debug("Scheduled "PRIthread_fmt", next = %p",
1573                         PRIthread_args(thread),
1574                         thread->Next);
1575                 #endif
1576         }
1577         else
1578         {
1579                 // No thread possible, warning condition (idle thread should be runnable)
1580                 Warning("No runnable thread for CPU%i", CPU);
1581         }
1582         
1583         return thread;
1584 }
1585
1586 // === EXPORTS ===
1587 EXPORT(Threads_GetUID);
1588 EXPORT(Threads_GetGID);

UCC git Repository :: git.ucc.asn.au