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                 // TODO: Register on thread to be poked when it dies
 509                 tTID    ret;
 510                 // NOTE: Race condition - Other child dies, desired child dies, first death is 'lost'
 511                 while( (ret = Threads_WaitTID(-1, Status)) != TID )
 512                 {
 513                         if( ret == -1 )
 514                                 break;
 515                 }
 516                 return ret;
 517         }
 518
 519         return -1;
 520 }
 521
 522 /**
 523  * \brief Gets a thread given its TID
 524  * \param TID   Thread ID
 525  * \return Thread pointer
 526  */
 527 tThread *Threads_GetThread(Uint TID)
 528 {
 529         tThread *thread;
 530
 531         // Search global list
 532         for( thread = gAllThreads; thread; thread = thread->GlobalNext )
 533         {
 534                 if(thread->TID == TID)
 535                         return thread;
 536         }
 537
 538         Log_Notice("Threads", "Unable to find TID %i on main list\n", TID);
 539
 540         return NULL;
 541 }
 542
 543 /**
 544  * \brief Deletes an entry from a list
 545  * \param List  Pointer to the list head
 546  * \param Thread        Thread to find
 547  * \return \a Thread
 548  */
 549 tThread *Threads_int_DelFromQueue(tThreadList *List, tThread *Thread)
 550 {
 551         tThread *ret, *prev = NULL;
 552
 553         for(ret = List->Head;
 554                 ret && ret != Thread;
 555                 prev = ret, ret = ret->Next
 556                 );
 557
 558         // Is the thread on the list
 559         if(!ret) {
 560                 //LogF("%p(%s) is not on list %p\n", Thread, Thread->ThreadName, List);
 561                 return NULL;
 562         }
 563
 564         if( !prev ) {
 565                 List->Head = Thread->Next;
 566                 //LogF("%p(%s) removed from head of %p\n", Thread, Thread->ThreadName, List);
 567         }
 568         else {
 569                 prev->Next = Thread->Next;
 570                 //LogF("%p(%s) removed from %p (prev=%p)\n", Thread, Thread->ThreadName, List, prev);
 571         }
 572         if( Thread->Next == NULL )
 573                 List->Tail = prev;
 574
 575         return Thread;
 576 }
 577
 578 void Threads_int_AddToList(tThreadList *List, tThread *Thread)
 579 {
 580         if( List->Head )
 581                 List->Tail->Next = Thread;
 582         else
 583                 List->Head = Thread;
 584         List->Tail = Thread;
 585         Thread->Next = NULL;
 586 }
 587
 588 /**
 589  * \brief Exit the current process (or another?)
 590  * \param TID   Thread ID to kill
 591  * \param Status        Exit status
 592  */
 593 void Threads_Exit(int TID, int Status)
 594 {
 595         if( TID == 0 )
 596                 Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF );
 597         else
 598                 Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF );
 599
 600         // Halt forever, just in case
 601         for(;;) HALT();
 602 }
 603
 604 /**
 605  * \fn void Threads_Kill(tThread *Thread, int Status)
 606  * \brief Kill a thread
 607  * \param Thread        Thread to kill
 608  * \param Status        Status code to return to the parent
 609  */
 610 void Threads_Kill(tThread *Thread, int Status)
 611 {
 612         tMsg    *msg;
 613          int    isCurThread = Thread == Proc_GetCurThread();
 614
 615         // TODO: Disown all children?
 616         #if 1
 617         {
 618                 tThread *child;
 619                 // TODO: I should keep a .Children list
 620                 for(child = gAllThreads;
 621                         child;
 622                         child = child->GlobalNext)
 623                 {
 624                         if(child->Parent == Thread)
 625                                 child->Parent = &gThreadZero;
 626                 }
 627         }
 628         #endif
 629
 630         ///\note Double lock is needed due to overlap of lock areas
 631
 632         // Lock thread (stop us recieving messages)
 633         SHORTLOCK( &Thread->IsLocked );
 634
 635         // Clear Message Queue
 636         while( Thread->Messages )
 637         {
 638                 msg = Thread->Messages->Next;
 639                 free( Thread->Messages );
 640                 Thread->Messages = msg;
 641         }
 642
 643         // Lock thread list
 644         SHORTLOCK( &glThreadListLock );
 645
 646         switch(Thread->Status)
 647         {
 648         case THREAD_STAT_PREINIT:       // Only on main list
 649                 break;
 650
 651         // Currently active thread
 652         case THREAD_STAT_ACTIVE:
 653                 if( Thread != Proc_GetCurThread() )
 654                 {
 655                         #if SCHEDULER_TYPE == SCHED_RR_PRI
 656                         tThreadList     *list = &gaActiveThreads[Thread->Priority];
 657                         #else
 658                         tThreadList     *list = &gActiveThreads;
 659                         #endif
 660                         if( Threads_int_DelFromQueue( list, Thread ) )
 661                         {
 662                         }
 663                         else
 664                         {
 665                                 Log_Warning("Threads",
 666                                         "Threads_Kill - Thread %p(%i,%s) marked as active, but not on list",
 667                                         Thread, Thread->TID, Thread->ThreadName
 668                                         );
 669                         }
 670                         #if SCHEDULER_TYPE == SCHED_LOTTERY
 671                         giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ];
 672                         #endif
 673                 }
 674                 // Ensure that we are not rescheduled
 675                 Thread->Remaining = 0;  // Clear Remaining Quantum
 676                 Thread->Quantum = 0;    // Clear Quantum to indicate dead thread
 677
 678                 // Update bookkeeping
 679                 giNumActiveThreads --;
 680                 break;
 681         // Kill it while it sleeps!
 682         case THREAD_STAT_SLEEPING:
 683                 if( !Threads_int_DelFromQueue( &gSleepingThreads, Thread ) )
 684                 {
 685                         Log_Warning("Threads",
 686                                 "Threads_Kill - Thread %p(%i,%s) marked as sleeping, but not on list",
 687                                 Thread, Thread->TID, Thread->ThreadName
 688                                 );
 689                 }
 690                 break;
 691
 692         // Brains!... You cannot kill something that is already dead
 693         case THREAD_STAT_ZOMBIE:
 694                 Log_Warning("Threads", "Threads_Kill - Thread %p(%i,%s) is undead, you cannot kill it",
 695                         Thread, Thread->TID, Thread->ThreadName);
 696                 SHORTREL( &glThreadListLock );
 697                 SHORTREL( &Thread->IsLocked );
 698                 return ;
 699
 700         default:
 701                 Log_Warning("Threads", "Threads_Kill - BUG Un-checked status (%i)",
 702                         Thread->Status);
 703                 break;
 704         }
 705
 706         // Save exit status
 707         Thread->RetStatus = Status;
 708
 709         SHORTREL( &Thread->IsLocked );
 710
 711         Thread->Status = THREAD_STAT_ZOMBIE;
 712         SHORTREL( &glThreadListLock );
 713         // TODO: It's possible that we could be timer-preempted here, should disable that... somehow
 714         Mutex_Acquire( &Thread->Parent->DeadChildLock );        // released by parent
 715         Thread->Parent->LastDeadChild = Thread;
 716         Threads_PostEvent( Thread->Parent, THREAD_EVENT_DEADCHILD );
 717
 718         Log("Thread %i went *hurk* (%i)", Thread->TID, Status);
 719
 720         // And, reschedule
 721         if(isCurThread)
 722         {
 723                 for( ;; )
 724                         Proc_Reschedule();
 725         }
 726 }
 727
 728 /**
 729  * \brief Yield remainder of the current thread's timeslice
 730  */
 731 void Threads_Yield(void)
 732 {
 733 //      Log("Threads_Yield: by %p", __builtin_return_address(0));
 734         Proc_Reschedule();
 735 }
 736
 737 /**
 738  * \breif Wait for the thread status to not be a specified value
 739  */
 740 void Threads_int_WaitForStatusEnd(enum eThreadStatus Status)
 741 {
 742         tThread *us = Proc_GetCurThread();
 743         ASSERT(Status != THREAD_STAT_ACTIVE);
 744         ASSERT(Status != THREAD_STAT_DEAD);
 745         while( us->Status == Status )
 746         {
 747                 Proc_Reschedule();
 748                 if( us->Status == Status )
 749                         Debug("Thread %p(%i %s) rescheduled while in %s state for %p",
 750                                 us, us->TID, us->ThreadName,
 751                                 casTHREAD_STAT[Status],
 752                                 __builtin_return_address(0));
 753         }
 754 }
 755
 756 int Threads_int_Sleep(enum eThreadStatus Status, void *Ptr, int Num, tThread **ListHead, tThread **ListTail, tShortSpinlock *Lock)
 757 {
 758         SHORTLOCK( &glThreadListLock );
 759         tThread *us = Threads_RemActive();
 760         us->Next = NULL;
 761         // - Mark as sleeping
 762         us->Status = Status;
 763         us->WaitPointer = Ptr;
 764         us->RetStatus = Num;    // Use RetStatus as a temp variable
 765
 766         // - Add to waiting
 767         if( ListTail ) {
 768                 if(*ListTail) {
 769                         (*ListTail)->Next = us;
 770                 }
 771                 else {
 772                         *ListHead = us;
 773                 }
 774                 *ListTail = us;
 775         }
 776         else {
 777                 *ListHead = us;
 778         }
 779
 780         //if( Proc_ThreadSync(us) )
 781         //      return ;
 782         SHORTREL( &glThreadListLock );
 783         if( Lock )
 784                 SHORTREL( Lock );
 785         Threads_int_WaitForStatusEnd(Status);
 786         us->WaitPointer = NULL;
 787         return us->RetStatus;
 788 }
 789
 790 /**
 791  * \fn void Threads_Sleep(void)
 792  * \brief Take the current process off the run queue
 793  */
 794 void Threads_Sleep(void)
 795 {
 796         tThread *cur = Proc_GetCurThread();
 797
 798         // Acquire Spinlock
 799         SHORTLOCK( &glThreadListLock );
 800
 801         // Don't sleep if there is a message waiting
 802         if( cur->Messages ) {
 803                 SHORTREL( &glThreadListLock );
 804                 return;
 805         }
 806
 807         // Remove us from running queue
 808         Threads_RemActive();
 809         // Mark thread as sleeping
 810         cur->Status = THREAD_STAT_SLEEPING;
 811
 812         // Add to Sleeping List (at the top)
 813         Threads_int_AddToList( &gSleepingThreads, cur );
 814
 815         #if DEBUG_TRACE_STATE
 816         Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName);
 817         #endif
 818
 819         // Release Spinlock
 820         SHORTREL( &glThreadListLock );
 821         Threads_int_WaitForStatusEnd(THREAD_STAT_SLEEPING);
 822 }
 823
 824
 825 /**
 826  * \brief Wakes a sleeping/waiting thread up
 827  * \param Thread        Thread to wake
 828  * \return Boolean Failure (Returns ERRNO)
 829  * \warning This should ONLY be called with task switches disabled
 830  */
 831 int Threads_Wake(tThread *Thread)
 832 {
 833         if(!Thread)
 834                 return -EINVAL;
 835
 836         switch(Thread->Status)
 837         {
 838         case THREAD_STAT_ACTIVE:
 839                 Log("Threads_Wake - Waking awake thread (%i)", Thread->TID);
 840                 return -EALREADY;
 841
 842         case THREAD_STAT_SLEEPING:
 843                 // Remove from sleeping queue
 844                 SHORTLOCK( &glThreadListLock );
 845                 Threads_int_DelFromQueue(&gSleepingThreads, Thread);
 846                 SHORTREL( &glThreadListLock );
 847
 848                 Threads_AddActive( Thread );
 849
 850                 #if DEBUG_TRACE_STATE
 851                 Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName);
 852                 #endif
 853                 return -EOK;
 854
 855         case THREAD_STAT_SEMAPHORESLEEP: {
 856                 tSemaphore      *sem;
 857                 tThread *th, *prev=NULL;
 858
 859                 sem = Thread->WaitPointer;
 860
 861                 SHORTLOCK( &sem->Protector );
 862
 863                 // Remove from sleeping queue
 864                 for( th = sem->Waiting; th; prev = th, th = th->Next )
 865                         if( th == Thread )      break;
 866                 if( th )
 867                 {
 868                         if(prev)
 869                                 prev->Next = Thread->Next;
 870                         else
 871                                 sem->Waiting = Thread->Next;
 872                         if(sem->LastWaiting == Thread)
 873                                 sem->LastWaiting = prev;
 874                 }
 875                 else
 876                 {
 877                         prev = NULL;
 878                         for( th = sem->Signaling; th; prev = th, th = th->Next )
 879                                 if( th == Thread )      break;
 880                         if( !th ) {
 881                                 Log_Warning("Threads", "Thread %p(%i %s) is not on semaphore %p(%s:%s)",
 882                                         Thread, Thread->TID, Thread->ThreadName,
 883                                         sem, sem->ModName, sem->Name);
 884                                 return -EINTERNAL;
 885                         }
 886
 887                         if(prev)
 888                                 prev->Next = Thread->Next;
 889                         else
 890                                 sem->Signaling = Thread->Next;
 891                         if(sem->LastSignaling == Thread)
 892                                 sem->LastSignaling = prev;
 893                 }
 894
 895                 Thread->RetStatus = 0;  // It didn't get anything
 896                 Threads_AddActive( Thread );
 897
 898                 #if DEBUG_TRACE_STATE
 899                 Log("Threads_Sleep: %p(%i %s) woken from semaphore", Thread, Thread->TID, Thread->ThreadName);
 900                 #endif
 901                 SHORTREL( &sem->Protector );
 902                 } return -EOK;
 903
 904         case THREAD_STAT_WAITING:
 905                 Warning("Threads_Wake - Waiting threads are not currently supported");
 906                 return -ENOTIMPL;
 907
 908         case THREAD_STAT_DEAD:
 909                 Warning("Threads_Wake - Attempt to wake dead thread (%i)", Thread->TID);
 910                 return -ENOTIMPL;
 911
 912         default:
 913                 Log_Warning("Threads", "Threads_Wake - Unknown process status (%i)", Thread->Status);
 914                 return -EINTERNAL;
 915         }
 916 }
 917
 918 /**
 919  * \brief Wake a thread given the TID
 920  * \param TID   Thread ID to wake
 921  * \return Boolean Faulure (errno)
 922  */
 923 int Threads_WakeTID(tTID TID)
 924 {
 925         tThread *thread = Threads_GetThread(TID);
 926          int    ret;
 927         if(!thread)
 928                 return -ENOENT;
 929         ret = Threads_Wake( thread );
 930         //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread);
 931         return ret;
 932 }
 933
 934 void Threads_ToggleTrace(int TID)
 935 {
 936         tThread *thread = Threads_GetThread(TID);
 937         if(!thread)     return ;
 938         thread->bInstrTrace = !thread->bInstrTrace;
 939 }
 940
 941 /**
 942  * \brief Adds a thread to the active queue
 943  */
 944 void Threads_AddActive(tThread *Thread)
 945 {
 946         SHORTLOCK( &glThreadListLock );
 947
 948         if( Thread->Status == THREAD_STAT_ACTIVE ) {
 949                 tThread *cur = Proc_GetCurThread();
 950                 Log_Warning("Threads", "WTF, %p CPU%i %p (%i %s) is adding %p (%i %s) when it is active",
 951                         __builtin_return_address(0),
 952                         GetCPUNum(), cur, cur->TID, cur->ThreadName, Thread, Thread->TID, Thread->ThreadName);
 953                 SHORTREL( &glThreadListLock );
 954                 return ;
 955         }
 956
 957         // Set state
 958         Thread->Status = THREAD_STAT_ACTIVE;
 959 //      Thread->CurCPU = -1;
 960         // Add to active list
 961         {
 962                 #if SCHEDULER_TYPE == SCHED_RR_PRI
 963                 tThreadList     *list = &gaActiveThreads[Thread->Priority];
 964                 #else
 965                 tThreadList     *list = &gActiveThreads;
 966                 #endif
 967                 Threads_int_AddToList( list, Thread );
 968         }
 969
 970         // Update bookkeeping
 971         giNumActiveThreads ++;
 972
 973         #if SCHEDULER_TYPE == SCHED_LOTTERY
 974         {
 975                  int    delta;
 976                 // Only change the ticket count if the thread is un-scheduled
 977                 if(Thread->CurCPU != -1)
 978                         delta = 0;
 979                 else
 980                         delta = caiTICKET_COUNTS[ Thread->Priority ];
 981
 982                 giFreeTickets += delta;
 983                 # if DEBUG_TRACE_TICKETS
 984                 Log("CPU%i %p (%i %s) added, new giFreeTickets = %i [+%i]",
 985                         GetCPUNum(), Thread, Thread->TID, Thread->ThreadName,
 986                         giFreeTickets, delta
 987                         );
 988                 # endif
 989         }
 990         #endif
 991
 992         SHORTREL( &glThreadListLock );
 993 }
 994
 995 /**
 996  * \brief Removes the current thread from the active queue
 997  * \warning This should ONLY be called with the lock held
 998  * \return Current thread pointer
 999  */
1000 tThread *Threads_RemActive(void)
1001 {
1002         giNumActiveThreads --;
1003         return Proc_GetCurThread();
1004 }
1005
1006 /**
1007  * \fn void Threads_SetFaultHandler(Uint Handler)
1008  * \brief Sets the signal handler for a signal
1009  */
1010 void Threads_SetFaultHandler(Uint Handler)
1011 {
1012         //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
1013         Proc_GetCurThread()->FaultHandler = Handler;
1014 }
1015
1016 /**
1017  * \fn void Threads_Fault(int Num)
1018  * \brief Calls a fault handler
1019  */
1020 void Threads_Fault(int Num)
1021 {
1022         tThread *thread = Proc_GetCurThread();
1023
1024         if(!thread)     return ;
1025
1026         Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
1027
1028         switch(thread->FaultHandler)
1029         {
1030         case 0: // Panic?
1031                 Threads_Kill(thread, -1);
1032                 HALT();
1033                 return ;
1034         case 1: // Dump Core?
1035                 Threads_Kill(thread, -1);
1036                 HALT();
1037                 return ;
1038         }
1039
1040         // Double Fault? Oh, F**k
1041         if(thread->CurFaultNum != 0) {
1042                 Log_Warning("Threads", "Threads_Fault: Double fault on %i", thread->TID);
1043                 Threads_Kill(thread, -1);       // For now, just kill
1044                 HALT();
1045         }
1046
1047         thread->CurFaultNum = Num;
1048
1049         Proc_CallFaultHandler(thread);
1050 }
1051
1052 /**
1053  * \fn void Threads_SegFault(tVAddr Addr)
1054  * \brief Called when a Segment Fault occurs
1055  */
1056 void Threads_SegFault(tVAddr Addr)
1057 {
1058         tThread *cur = Proc_GetCurThread();
1059         cur->bInstrTrace = 0;
1060         Log_Warning("Threads", "Thread #%i committed a segfault at address %p", cur->TID, Addr);
1061         MM_DumpTables(0, USER_MAX);
1062         Threads_Fault( 1 );
1063         //Threads_Exit( 0, -1 );
1064 }
1065
1066
1067 void Threads_PostSignalTo(tThread *Thread, int SignalNum)
1068 {
1069         ASSERT(Thread);
1070         Log_Debug("Threads", "Signalling %i(%s) with %i", Thread->TID, Thread->ThreadName, SignalNum);
1071         Thread->PendingSignal = SignalNum;
1072         Threads_PostEvent(Thread, THREAD_EVENT_SIGNAL);
1073 }
1074 void Threads_PostSignal(int SignalNum)
1075 {
1076         Threads_PostSignalTo( Proc_GetCurThread(), SignalNum );
1077 }
1078
1079 void Threads_SignalGroup(tPGID PGID, int Signal)
1080 {
1081         for( tProcess *proc = gAllProcesses; proc; proc = proc->Next )
1082         {
1083                 if(proc->PGID == PGID)
1084                 {
1085                         Threads_PostSignalTo(proc->FirstThread, Signal);
1086                 }
1087         }
1088 }
1089
1090 /**
1091  */
1092 int Threads_GetPendingSignal(void)
1093 {
1094         tThread *cur = Proc_GetCurThread();
1095
1096         // Atomic AND with 0 fetches and clears in one operation
1097         int ret = __sync_fetch_and_and( &cur->PendingSignal, 0 );
1098         if( ret )
1099         {
1100                 Log_Debug("Threads", "Thread %i(%s) has signal %i pending",
1101                         cur->TID, cur->ThreadName, ret);
1102         }
1103         return ret;
1104 }
1105
1106 /*
1107  * \brief Update the current thread's signal handler
1108  */
1109 void Threads_SetSignalHandler(int SignalNum, void *Handler)
1110 {
1111         if( SignalNum <= 0 || SignalNum >= NSIGNALS )
1112                 return ;
1113         if( !MM_IsUser(Handler) )
1114                 return ;
1115         Proc_GetCurThread()->Process->SignalHandlers[SignalNum] = Handler;
1116 }
1117
1118 /**
1119  * \brief Gets the registered (or default, if none set) handler for a signal.
1120  * \return Handler function pointer, OR NULL if no signal to be ignored
1121  */
1122 void *Threads_GetSignalHandler(int SignalNum)
1123 {
1124         // TODO: Core dump
1125         void *User_Signal_Core = User_Signal_Kill;
1126
1127         if( SignalNum <= 0 || SignalNum >= NSIGNALS )
1128                 return NULL;
1129         void *ret = Proc_GetCurThread()->Process->SignalHandlers[SignalNum];
1130         if( !ret || (SignalNum == SIGKILL || SignalNum == SIGSTOP) )
1131         {
1132                 // Defaults
1133                 switch(SignalNum)
1134                 {
1135                 case SIGHUP:
1136                 case SIGINT:
1137                         ret = User_Signal_Kill;
1138                         break;
1139                 case SIGQUIT:
1140                 case SIGILL:
1141                 case SIGABRT:
1142                 case SIGFPE:
1143                         ret = User_Signal_Core;
1144                         break;
1145                 case SIGKILL:
1146                         ret = User_Signal_Kill;
1147                         break;
1148                 case SIGSEGV:
1149                         ret = User_Signal_Core;
1150                         break;
1151                 case SIGPIPE:
1152                 case SIGALRM:
1153                 case SIGTERM:
1154                         ret = User_Signal_Kill;
1155                         break;
1156                 default:
1157                         ret = NULL;
1158                         break;
1159                 }
1160         }
1161         Log_Debug("Threads", "Handler %p for signal %i", ret, SignalNum);
1162         return ret;
1163 }
1164
1165 // --- Process Structure Access Functions ---
1166 tPGID Threads_GetPGID(void)
1167 {
1168         return Proc_GetCurThread()->Process->PGID;
1169 }
1170 tPID Threads_GetPID(void)
1171 {
1172         return Proc_GetCurThread()->Process->PID;
1173 }
1174 tTID Threads_GetTID(void)
1175 {
1176         return Proc_GetCurThread()->TID;
1177 }
1178 tUID Threads_GetUID(void)
1179 {
1180         return Proc_GetCurThread()->Process->UID;
1181 }
1182 tGID Threads_GetGID(void)
1183 {
1184         return Proc_GetCurThread()->Process->GID;
1185 }
1186
1187 int Threads_SetUID(tUID ID)
1188 {
1189         tThread *t = Proc_GetCurThread();
1190         if( t->Process->UID != 0 ) {
1191                 errno = -EACCES;
1192                 return -1;
1193         }
1194         Log_Debug("Threads", "PID %i's UID set to %i", t->Process->PID, ID);
1195         t->Process->UID = ID;
1196         return 0;
1197 }
1198
1199 int Threads_SetGID(tGID ID)
1200 {
1201         tThread *t = Proc_GetCurThread();
1202         if( t->Process->UID != 0 ) {
1203                 errno = -EACCES;
1204                 return -1;
1205         }
1206         Log_Debug("Threads", "PID %i's GID set to %i", t->Process->PID, ID);
1207         t->Process->GID = ID;
1208         return 0;
1209 }
1210
1211 // --- Per-thread storage ---
1212 int *Threads_GetErrno(void)
1213 {
1214         return &Proc_GetCurThread()->_errno;
1215 }
1216
1217 // --- Configuration ---
1218 int *Threads_GetMaxFD(void)
1219 {
1220         return &Proc_GetCurThread()->Process->MaxFD;
1221 }
1222 char **Threads_GetChroot(void)
1223 {
1224         return &Proc_GetCurThread()->Process->RootDir;
1225 }
1226 char **Threads_GetCWD(void)
1227 {
1228         return &Proc_GetCurThread()->Process->CurrentWorkingDir;
1229 }
1230 // ---
1231
1232 void Threads_int_DumpThread(tThread *thread)
1233 {
1234         if( !thread ) {
1235                 Log(" %p NULL", thread);
1236                 return ;
1237         }
1238         if( !CheckMem(thread, sizeof(tThread)) ) {
1239                 Log(" %p INVAL", thread);
1240                 return ;
1241         }
1242         tPID    pid = (thread->Process ? thread->Process->PID : -1);
1243         const char      *statstr = (thread->Status < sizeof(casTHREAD_STAT)/sizeof(casTHREAD_STAT[0])
1244                 ? casTHREAD_STAT[thread->Status] : "");
1245         Log(" %p %i (%i) - %s (CPU %i) - %i (%s)",
1246                 thread, thread->TID, pid, thread->ThreadName, thread->CurCPU,
1247                 thread->Status, statstr
1248                 );
1249         switch(thread->Status)
1250         {
1251         case THREAD_STAT_MUTEXSLEEP:
1252                 Log("  Mutex Pointer: %p", thread->WaitPointer);
1253                 break;
1254         case THREAD_STAT_SEMAPHORESLEEP:
1255                 Log("  Semaphore Pointer: %p", thread->WaitPointer);
1256                 Log("  Semaphore Name: %s:%s",
1257                         ((tSemaphore*)thread->WaitPointer)->ModName,
1258                         ((tSemaphore*)thread->WaitPointer)->Name
1259                         );
1260                 break;
1261         case THREAD_STAT_EVENTSLEEP:
1262                 Log("  Event Mask: %x", thread->RetStatus);
1263                 break;
1264         case THREAD_STAT_ZOMBIE:
1265                 Log("  Return Status: %i", thread->RetStatus);
1266                 break;
1267         default:        break;
1268         }
1269         Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
1270         Log("  KStack %p", thread->KernelStack);
1271         if( thread->bInstrTrace )
1272                 Log("  Tracing Enabled");
1273         Proc_DumpThreadCPUState(thread);
1274 }
1275
1276 /**
1277  * \fn void Threads_Dump(void)
1278  */
1279 void Threads_DumpActive(void)
1280 {
1281         tThread *thread;
1282         tThreadList     *list;
1283         #if SCHEDULER_TYPE == SCHED_RR_PRI
1284          int    i;
1285         #endif
1286
1287         Log("Active Threads: (%i reported)", giNumActiveThreads);
1288
1289         #if SCHEDULER_TYPE == SCHED_RR_PRI
1290         for( i = 0; i < MIN_PRIORITY+1; i++ )
1291         {
1292                 list = &gaActiveThreads[i];
1293         #else
1294                 list = &gActiveThreads;
1295         #endif
1296                 for(thread=list->Head;thread;thread=thread->Next)
1297                 {
1298                         Threads_int_DumpThread(thread);
1299                         if(thread->Status != THREAD_STAT_ACTIVE)
1300                                 Log("  ERROR State (%i) != THREAD_STAT_ACTIVE (%i)",
1301                                         thread->Status, THREAD_STAT_ACTIVE);
1302                 }
1303
1304         #if SCHEDULER_TYPE == SCHED_RR_PRI
1305         }
1306         #endif
1307 }
1308
1309 /**
1310  * \fn void Threads_Dump(void)
1311  * \brief Dumps a list of currently running threads
1312  */
1313 void Threads_Dump(void)
1314 {
1315         Log("--- Thread Dump ---");
1316         Threads_DumpActive();
1317
1318         Log("All Threads:");
1319         for(tThread *thread = gAllThreads; thread; thread = thread->GlobalNext)
1320         {
1321                 Threads_int_DumpThread(thread);
1322         }
1323 }
1324
1325 /**
1326  * \brief Gets the next thread to run
1327  * \param CPU   Current CPU
1328  * \param Last  The thread the CPU was running
1329  */
1330 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
1331 {
1332         tThread *thread;
1333
1334         // If this CPU has the lock, we must let it complete
1335         if( CPU_HAS_LOCK( &glThreadListLock ) )
1336                 return Last;
1337
1338         // Don't change threads if the current CPU has switches disabled
1339         if( gaThreads_NoTaskSwitch[CPU] )
1340                 return Last;
1341
1342         // Lock thread list
1343         SHORTLOCK( &glThreadListLock );
1344
1345         // Make sure the current (well, old) thread is marked as de-scheduled
1346         if(Last)        Last->CurCPU = -1;
1347
1348         // No active threads, just take a nap
1349         if(giNumActiveThreads == 0) {
1350                 SHORTREL( &glThreadListLock );
1351                 #if DEBUG_TRACE_TICKETS
1352                 Log("No active threads");
1353                 #endif
1354                 return NULL;
1355         }
1356
1357         #if 0
1358         #if SCHEDULER_TYPE != SCHED_RR_PRI
1359         // Special case: 1 thread
1360         if(giNumActiveThreads == 1) {
1361                 if( gActiveThreads.Head->CurCPU == -1 )
1362                         gActiveThreads.Head->CurCPU = CPU;
1363
1364                 SHORTREL( &glThreadListLock );
1365
1366                 if( gActiveThreads.Head->CurCPU == CPU )
1367                         return gActiveThreads.Head;
1368
1369                 return NULL;    // CPU has nothing to do
1370         }
1371         #endif
1372         #endif
1373
1374         // Allow the old thread to be scheduled again
1375         if( Last ) {
1376                 if( Last->Status == THREAD_STAT_ACTIVE ) {
1377                         tThreadList     *list;
1378                         #if SCHEDULER_TYPE == SCHED_LOTTERY
1379                         giFreeTickets += caiTICKET_COUNTS[ Last->Priority ];
1380                         # if DEBUG_TRACE_TICKETS
1381                         LogF("Log: CPU%i released %p (%i %s) into the pool (%i [+%i] tickets in pool)\n",
1382                                 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets,
1383                                 caiTICKET_COUNTS[ Last->Priority ]);
1384                         # endif
1385                         #endif
1386
1387                         #if SCHEDULER_TYPE == SCHED_RR_PRI
1388                         list = &gaActiveThreads[ Last->Priority ];
1389                         #else
1390                         list = &gActiveThreads;
1391                         #endif
1392                         // Add to end of list
1393                         Threads_int_AddToList( list, Last );
1394                 }
1395                 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
1396                 else
1397                         LogF("Log: CPU%i released %p (%i %s)->Status = %i (Released,not in pool)\n",
1398                                 CPU, Last, Last->TID, Last->ThreadName, Last->Status);
1399                 #endif
1400                 Last->CurCPU = -1;
1401         }
1402
1403         // ---
1404         // Lottery Scheduler
1405         // ---
1406         #if SCHEDULER_TYPE == SCHED_LOTTERY
1407         {
1408                  int    ticket, number;
1409                 # if 1
1410                 number = 0;
1411                 for(thread = gActiveThreads.Head; thread; thread = thread->Next)
1412                 {
1413                         if(thread->Status != THREAD_STAT_ACTIVE)
1414                                 Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i",
1415                                         thread, thread->TID, thread->ThreadName, thread->Status);
1416                         if(thread->Next == thread) {
1417                                 Panic("Bookkeeping fail - %p %i(%s) loops back on itself",
1418                                         thread, thread->TID, thread->ThreadName, thread->Status);
1419                         }
1420                         number += caiTICKET_COUNTS[ thread->Priority ];
1421                 }
1422                 if(number != giFreeTickets) {
1423                         Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
1424                                 giFreeTickets, number, CPU);
1425                 }
1426                 # endif
1427
1428                 // No free tickets (all tasks delegated to cores)
1429                 if( giFreeTickets == 0 ) {
1430                         SHORTREL(&glThreadListLock);
1431                         return NULL;
1432                 }
1433
1434                 // Get the ticket number
1435                 ticket = number = rand() % giFreeTickets;
1436
1437                 // Find the next thread
1438                 for(thread = gActiveThreads.Head; thread; prev = thread, thread = thread->Next )
1439                 {
1440                         if( caiTICKET_COUNTS[ thread->Priority ] > number)      break;
1441                         number -= caiTICKET_COUNTS[ thread->Priority ];
1442                 }
1443
1444                 // If we didn't find a thread, something went wrong
1445                 if(thread == NULL)
1446                 {
1447                         number = 0;
1448                         for(thread=gActiveThreads;thread;thread=thread->Next) {
1449                                 if(thread->CurCPU >= 0) continue;
1450                                 number += caiTICKET_COUNTS[ thread->Priority ];
1451                         }
1452                         Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
1453                                 giFreeTickets, number);
1454                 }
1455
1456                 // Remove
1457                 if(prev)
1458                         prev->Next = thread->Next;
1459                 else
1460                         gActiveThreads.Head = thread->Next;
1461                 if(!thread->Next)
1462                         gActiveThreads.Tail = prev;
1463
1464                 giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ];
1465                 # if DEBUG_TRACE_TICKETS
1466                 LogF("Log: CPU%i allocated %p (%i %s), (%i [-%i] tickets in pool), \n",
1467                         CPU, thread, thread->TID, thread->ThreadName,
1468                         giFreeTickets, caiTICKET_COUNTS[ thread->Priority ]);
1469                 # endif
1470         }
1471
1472         // ---
1473         // Priority based round robin scheduler
1474         // ---
1475         #elif SCHEDULER_TYPE == SCHED_RR_PRI
1476         {
1477                  int    i;
1478                 thread = NULL;
1479                 for( i = 0; i < MIN_PRIORITY + 1; i ++ )
1480                 {
1481                         if( !gaActiveThreads[i].Head )
1482                                 continue ;
1483
1484                         thread = gaActiveThreads[i].Head;
1485
1486                         // Remove from head
1487                         gaActiveThreads[i].Head = thread->Next;
1488                         if(!thread->Next)
1489                                 gaActiveThreads[i].Tail = NULL;
1490                         thread->Next = NULL;
1491                         break;
1492                 }
1493
1494                 // Anything to do?
1495                 if( !thread ) {
1496                         SHORTREL(&glThreadListLock);
1497                         return NULL;
1498                 }
1499                 if( thread->Status != THREAD_STAT_ACTIVE ) {
1500                         LogF("Oops, Thread %i (%s) is not active\n", thread->TID, thread->ThreadName);
1501                 }
1502         }
1503         #elif SCHEDULER_TYPE == SCHED_RR_SIM
1504         {
1505                 // Get the next thread off the list
1506                 thread = gActiveThreads.Head;
1507                 gActiveThreads.Head = thread->Next;
1508                 if(!thread->Next)
1509                         gaActiveThreads.Tail = NULL;
1510                 thread->Next = NULL;
1511
1512                 // Anything to do?
1513                 if( !thread ) {
1514                         SHORTREL(&glThreadListLock);
1515                         return NULL;
1516                 }
1517         }
1518         #else
1519         # error "Unimplemented scheduling algorithm"
1520         #endif
1521
1522         // Make the new thread non-schedulable
1523         thread->CurCPU = CPU;
1524         thread->Remaining = thread->Quantum;
1525
1526         SHORTREL( &glThreadListLock );
1527
1528         return thread;
1529 }
1530
1531 // === EXPORTS ===
1532 EXPORT(Threads_GetUID);
1533 EXPORT(Threads_GetGID);