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