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