KernelLand/Kernel/threads.c

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