KernelLand/Kernel/threads.c

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