KernelLand/Kernel/threads.c

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