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