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