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