Kernel/threads.c

   1 /*
   2  * Acess2
   3  * threads.c
   4  * - Common Thread Control
   5  */
   6 #include <acess.h>
   7 #include <threads.h>
   8 #include <errno.h>
   9
  10 // Configuration
  11 #define DEBUG_TRACE_TICKETS     0       // Trace ticket counts
  12 #define DEBUG_TRACE_STATE       0       // Trace state changes (sleep/wake)
  13
  14 // --- Schedulers ---
  15 #define SCHED_UNDEF     0
  16 #define SCHED_LOTTERY   1       // Lottery scheduler
  17 #define SCHED_RR_SIM    2       // Single Queue Round Robin
  18 #define SCHED_RR_PRI    3       // Multi Queue Round Robin
  19 // Set scheduler type
  20 #define SCHEDULER_TYPE  SCHED_LOTTERY
  21
  22 // === CONSTANTS ===
  23 #define DEFAULT_QUANTUM 10
  24 #define DEFAULT_PRIORITY        5
  25 #define MIN_PRIORITY            10
  26 const enum eConfigTypes cCONFIG_TYPES[] = {
  27         CFGT_HEAPSTR,   // e.g. CFG_VFS_CWD
  28         CFGT_INT,       // e.g. CFG_VFS_MAXFILES
  29         CFGT_NULL
  30 };
  31
  32 // === IMPORTS ===
  33 extern void     ArchThreads_Init(void);
  34 extern void     Proc_Start(void);
  35 extern tThread  *Proc_GetCurThread(void);
  36 extern int      Proc_Clone(Uint *Err, Uint Flags);
  37 extern void     Proc_CallFaultHandler(tThread *Thread);
  38 extern int      GetCPUNum(void);
  39
  40 // === PROTOTYPES ===
  41 void    Threads_Init(void);
  42  int    Threads_SetName(const char *NewName);
  43 char    *Threads_GetName(int ID);
  44 void    Threads_SetPriority(tThread *Thread, int Pri);
  45 tThread *Threads_CloneTCB(Uint *Err, Uint Flags);
  46  int    Threads_WaitTID(int TID, int *status);
  47 tThread *Threads_GetThread(Uint TID);
  48 void    Threads_AddToDelete(tThread *Thread);
  49 tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread);
  50 void    Threads_Exit(int TID, int Status);
  51 void    Threads_Kill(tThread *Thread, int Status);
  52 void    Threads_Yield(void);
  53 void    Threads_Sleep(void);
  54  int    Threads_Wake(tThread *Thread);
  55 void    Threads_AddActive(tThread *Thread);
  56 tThread *Threads_RemActive(void);
  57  int    Threads_GetPID(void);
  58  int    Threads_GetTID(void);
  59 tUID    Threads_GetUID(void);
  60  int    Threads_SetUID(Uint *Errno, tUID ID);
  61 tGID    Threads_GetGID(void);
  62  int    Threads_SetGID(Uint *Errno, tUID ID);
  63 void    Threads_Dump(void);
  64 void    Threads_DumpActive(void);
  65 void    Mutex_Acquire(tMutex *Mutex);
  66 void    Mutex_Release(tMutex *Mutex);
  67  int    Mutex_IsLocked(tMutex *Mutex);
  68
  69 // === GLOBALS ===
  70 // -- Core Thread --
  71 // Only used for the core kernel
  72 tThread gThreadZero = {
  73         Status: THREAD_STAT_ACTIVE,     // Status
  74         ThreadName:     "ThreadZero",   // Name
  75         Quantum: DEFAULT_QUANTUM,       // Default Quantum
  76         Remaining:      DEFAULT_QUANTUM,        // Current Quantum
  77         Priority:       DEFAULT_PRIORITY        // Number of tickets
  78         };
  79 // -- Processes --
  80 // --- Locks ---
  81 tShortSpinlock  glThreadListLock;       ///\note NEVER use a heap function while locked
  82 // --- Current State ---
  83 volatile int    giNumActiveThreads = 0; // Number of threads on the active queue
  84 volatile Uint   giNextTID = 1;  // Next TID to allocate
  85 // --- Thread Lists ---
  86 tThread *gAllThreads = NULL;            // All allocated threads
  87 tThread *gSleepingThreads = NULL;       // Sleeping Threads
  88 tThread *gDeleteThreads = NULL;         // Threads to delete
  89  int    giNumCPUs = 1;  // Number of CPUs
  90 BOOL     gaThreads_NoTaskSwitch[MAX_CPUS];      // Disables task switches for each core (Pseudo-IF)
  91 // --- Scheduler Types ---
  92 #if SCHEDULER_TYPE == SCHED_LOTTERY
  93 const int       caiTICKET_COUNTS[MIN_PRIORITY+1] = {100,81,64,49,36,25,16,9,4,1,0};
  94 volatile int    giFreeTickets = 0;      // Number of tickets held by non-scheduled threads
  95 tThread *gActiveThreads = NULL;         // Currently Running Threads
  96 #elif SCHEDULER_TYPE == SCHED_RR_SIM
  97 tThread *gActiveThreads = NULL;         // Currently Running Threads
  98 #elif SCHEDULER_TYPE == SCHED_RR_PRI
  99 tThread *gaActiveThreads[MIN_PRIORITY+1];       // Active threads for each priority level
 100 #else
 101 # error "Unkown scheduler type"
 102 #endif
 103
 104 // === CODE ===
 105 /**
 106  * \fn void Threads_Init(void)
 107  * \brief Initialse the thread list
 108  */
 109 void Threads_Init(void)
 110 {
 111         ArchThreads_Init();
 112
 113         // Create Initial Task
 114         #if SCHEDULER_TYPE == SCHED_RR_PRI
 115         gaActiveThreads[gThreadZero.Priority] = &gThreadZero;
 116         #else
 117         gActiveThreads = &gThreadZero;
 118         #endif
 119
 120         gAllThreads = &gThreadZero;
 121         giNumActiveThreads = 1;
 122
 123         Proc_Start();
 124 }
 125
 126 /**
 127  * \fn void Threads_SetName(const char *NewName)
 128  * \brief Sets the current thread's name
 129  * \param NewName       New name for the thread
 130  * \return Boolean Failure
 131  */
 132 int Threads_SetName(const char *NewName)
 133 {
 134         tThread *cur = Proc_GetCurThread();
 135         char    *oldname = cur->ThreadName;
 136
 137         // NOTE: There is a possibility of non-thread safety here
 138         // A thread could read the current name pointer before it is zeroed
 139
 140         cur->ThreadName = NULL;
 141
 142         if( IsHeap(oldname) )   free( oldname );
 143
 144         cur->ThreadName = strdup(NewName);
 145         return 0;
 146 }
 147
 148 /**
 149  * \fn char *Threads_GetName(int ID)
 150  * \brief Gets a thread's name
 151  * \param ID    Thread ID (-1 indicates current thread)
 152  * \return Pointer to name
 153  * \retval NULL Failure
 154  */
 155 char *Threads_GetName(tTID ID)
 156 {
 157         if(ID == -1) {
 158                 return Proc_GetCurThread()->ThreadName;
 159         }
 160         return Threads_GetThread(ID)->ThreadName;
 161 }
 162
 163 /**
 164  * \fn void Threads_SetPriority(tThread *Thread, int Pri)
 165  * \brief Sets the priority of a task
 166  * \param Thread        Thread to update ticket count (NULL means current thread)
 167  * \param Pri   New priority
 168  */
 169 void Threads_SetPriority(tThread *Thread, int Pri)
 170 {
 171         // Get current thread
 172         if(Thread == NULL)      Thread = Proc_GetCurThread();
 173         // Bounds checking
 174         // - If < 0, set to lowest priority
 175         if(Pri < 0)     Pri = MIN_PRIORITY;
 176         if(Pri > MIN_PRIORITY)  Pri = MIN_PRIORITY;
 177
 178         // Do we actually have to do anything?
 179         if( Pri == Thread->Priority )   return;
 180
 181         #if SCHEDULER_TYPE == SCHED_RR_PRI
 182         SHORTLOCK( &glThreadListLock );
 183         // Remove from old priority
 184         Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread );
 185         // And add to new
 186         Thread->Next = gaActiveThreads[Pri];
 187         gaActiveThreads[Pri] = Thread;
 188         Thread->Priority = Pri;
 189         SHORTREL( &glThreadListLock );
 190         #else
 191         // If this isn't the current thread, we need to lock
 192         if( Thread != Proc_GetCurThread() )
 193         {
 194                 SHORTLOCK( &glThreadListLock );
 195
 196                 #if SCHEDULER_TYPE == SCHED_LOTTERY
 197                 giFreeTickets -= caiTICKET_COUNTS[Thread->Priority] - caiTICKET_COUNTS[Pri];
 198                 # if DEBUG_TRACE_TICKETS
 199                 Log("Threads_SetTickets: new giFreeTickets = %i", giFreeTickets);
 200                 # endif
 201                 #endif
 202                 Thread->Priority = Pri;
 203                 SHORTREL( &glThreadListLock );
 204         }
 205         else
 206                 Thread->Priority = Pri;
 207         #endif
 208 }
 209
 210 /**
 211  * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
 212  * \brief Clone the TCB of the current thread
 213  * \param Err   Error pointer
 214  * \param Flags Flags for something... (What is this for?)
 215  */
 216 tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
 217 {
 218         tThread *cur, *new;
 219          int    i;
 220         cur = Proc_GetCurThread();
 221
 222         // Allocate and duplicate
 223         new = malloc(sizeof(tThread));
 224         if(new == NULL) {
 225                 *Err = -ENOMEM;
 226                 return NULL;
 227         }
 228         memcpy(new, cur, sizeof(tThread));
 229
 230         new->CurCPU = -1;
 231         new->Next = NULL;
 232         memset( &new->IsLocked, 0, sizeof(new->IsLocked));
 233         new->Status = THREAD_STAT_PREINIT;
 234         new->RetStatus = 0;
 235
 236         // Get Thread ID
 237         new->TID = giNextTID++;
 238         new->Parent = cur;
 239
 240         // Clone Name
 241         new->ThreadName = strdup(cur->ThreadName);
 242
 243         // Set Thread Group ID (PID)
 244         if(Flags & CLONE_VM)
 245                 new->TGID = new->TID;
 246         else
 247                 new->TGID = cur->TGID;
 248
 249         // Messages are not inherited
 250         new->Messages = NULL;
 251         new->LastMessage = NULL;
 252
 253         // Set State
 254         new->Remaining = new->Quantum = cur->Quantum;
 255         new->Priority = cur->Priority;
 256
 257         // Set Signal Handlers
 258         new->CurFaultNum = 0;
 259         new->FaultHandler = cur->FaultHandler;
 260
 261         for( i = 0; i < NUM_CFG_ENTRIES; i ++ )
 262         {
 263                 switch(cCONFIG_TYPES[i])
 264                 {
 265                 default:
 266                         new->Config[i] = cur->Config[i];
 267                         break;
 268                 case CFGT_HEAPSTR:
 269                         if(cur->Config[i])
 270                                 new->Config[i] = (Uint) strdup( (void*)cur->Config[i] );
 271                         else
 272                                 new->Config[i] = 0;
 273                         break;
 274                 }
 275         }
 276
 277         // Maintain a global list of threads
 278         SHORTLOCK( &glThreadListLock );
 279         new->GlobalPrev = NULL; // Protect against bugs
 280         new->GlobalNext = gAllThreads;
 281         gAllThreads = new;
 282         SHORTREL( &glThreadListLock );
 283
 284         return new;
 285 }
 286
 287 /**
 288  * \brief Get a configuration pointer from the Per-Thread data area
 289  * \param ID    Config slot ID
 290  * \return Pointer at ID
 291  */
 292 Uint *Threads_GetCfgPtr(int ID)
 293 {
 294         if(ID < 0 || ID >= NUM_CFG_ENTRIES) {
 295                 Warning("Threads_GetCfgPtr: Index %i is out of bounds", ID);
 296                 return NULL;
 297         }
 298
 299         return &Proc_GetCurThread()->Config[ID];
 300 }
 301
 302 /**
 303  * \brief Wait for a task to change state
 304  * \param TID   Thread ID to wait on (-1: Any child thread, 0: Any Child/Sibling, <-1: -PID)
 305  * \param Status        Thread return status
 306  * \return TID of child that changed state
 307  */
 308 tTID Threads_WaitTID(int TID, int *Status)
 309 {
 310         // Any Child
 311         if(TID == -1) {
 312                 Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Any Child");
 313                 return -1;
 314         }
 315
 316         // Any peer/child thread
 317         if(TID == 0) {
 318                 Log_Error("Threads", "TODO: Threads_WaitTID(TID=0) - Any Child/Sibling");
 319                 return -1;
 320         }
 321
 322         // TGID = abs(TID)
 323         if(TID < -1) {
 324                 Log_Error("Threads", "TODO: Threads_WaitTID(TID<0) - TGID");
 325                 return -1;
 326         }
 327
 328         // Specific Thread
 329         if(TID > 0) {
 330                 tThread *t = Threads_GetThread(TID);
 331                  int    initStatus = t->Status;
 332                 tTID    ret;
 333
 334                 // Wait for the thread to die!
 335                 if(initStatus != THREAD_STAT_ZOMBIE) {
 336                         // TODO: Handle child also being suspended if wanted
 337                         while(t->Status != THREAD_STAT_ZOMBIE) {
 338                                 Threads_Sleep();
 339                                 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
 340                                         Threads_GetTID(), t->TID, t->Status);
 341                         }
 342                 }
 343
 344                 // Set return status
 345                 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
 346                         Threads_GetTID(), t->TID, t->Status);
 347                 ret = t->TID;
 348                 switch(t->Status)
 349                 {
 350                 case THREAD_STAT_ZOMBIE:
 351                         // Kill the thread
 352                         t->Status = THREAD_STAT_DEAD;
 353                         // TODO: Child return value?
 354                         if(Status)      *Status = t->RetStatus;
 355                         // add to delete queue
 356                         Threads_AddToDelete( t );
 357                         break;
 358                 default:
 359                         if(Status)      *Status = -1;
 360                         break;
 361                 }
 362                 return ret;
 363         }
 364
 365         return -1;
 366 }
 367
 368 /**
 369  * \brief Gets a thread given its TID
 370  * \param TID   Thread ID
 371  * \return Thread pointer
 372  */
 373 tThread *Threads_GetThread(Uint TID)
 374 {
 375         tThread *thread;
 376
 377         // Search global list
 378         for(thread = gAllThreads;
 379                 thread;
 380                 thread = thread->GlobalNext)
 381         {
 382                 if(thread->TID == TID)
 383                         return thread;
 384         }
 385
 386         Log("Unable to find TID %i on main list\n", TID);
 387
 388         return NULL;
 389 }
 390
 391 /**
 392  * \brief Adds a thread to the delete queue
 393  * \param Thread        Thread to delete
 394  */
 395 void Threads_AddToDelete(tThread *Thread)
 396 {
 397         // Add to delete queue
 398         // TODO: Is locking needed?
 399         if(gDeleteThreads) {
 400                 Thread->Next = gDeleteThreads;
 401                 gDeleteThreads = Thread;
 402         } else {
 403                 Thread->Next = NULL;
 404                 gDeleteThreads = Thread;
 405         }
 406 }
 407
 408 /**
 409  * \brief Deletes an entry from a list
 410  * \param List  Pointer to the list head
 411  * \param Thread        Thread to find
 412  * \return \a Thread
 413  */
 414 tThread *Threads_int_DelFromQueue(tThread **List, tThread *Thread)
 415 {
 416         tThread *ret, *prev = NULL;
 417
 418         for(ret = *List;
 419                 ret && ret != Thread;
 420                 prev = ret, ret = ret->Next
 421                 );
 422
 423         // Is the thread on the list
 424         if(!ret) {
 425                 //LogF("%p(%s) is not on list %p\n", Thread, Thread->ThreadName, List);
 426                 return NULL;
 427         }
 428
 429         if( !prev ) {
 430                 *List = Thread->Next;
 431                 //LogF("%p(%s) removed from head of %p\n", Thread, Thread->ThreadName, List);
 432         }
 433         else {
 434                 prev->Next = Thread->Next;
 435                 //LogF("%p(%s) removed from %p (prev=%p)\n", Thread, Thread->ThreadName, List, prev);
 436         }
 437
 438         return Thread;
 439 }
 440
 441 /**
 442  * \brief Exit the current process (or another?)
 443  * \param TID   Thread ID to kill
 444  * \param Status        Exit status
 445  */
 446 void Threads_Exit(int TID, int Status)
 447 {
 448         if( TID == 0 )
 449                 Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF );
 450         else
 451                 Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF );
 452
 453         // Halt forever, just in case
 454         for(;;) HALT();
 455 }
 456
 457 /**
 458  * \fn void Threads_Kill(tThread *Thread, int Status)
 459  * \brief Kill a thread
 460  * \param Thread        Thread to kill
 461  * \param Status        Status code to return to the parent
 462  */
 463 void Threads_Kill(tThread *Thread, int Status)
 464 {
 465         tMsg    *msg;
 466
 467         // TODO: Kill all children
 468         #if 0
 469         {
 470                 tThread *child;
 471                 // TODO: I should keep a .Parent pointer, and a .Children list
 472                 for(child = gActiveThreads;
 473                         child;
 474                         child = child->Next)
 475                 {
 476                         if(child->PTID == Thread->TID)
 477                                 Threads_Kill(child, -1);
 478                 }
 479         }
 480         #endif
 481
 482         ///\note Double lock is needed due to overlap of lock areas
 483
 484         // Lock thread (stop us recieving messages)
 485         SHORTLOCK( &Thread->IsLocked );
 486
 487         // Clear Message Queue
 488         while( Thread->Messages )
 489         {
 490                 msg = Thread->Messages->Next;
 491                 free( Thread->Messages );
 492                 Thread->Messages = msg;
 493         }
 494
 495         // Lock thread list
 496         SHORTLOCK( &glThreadListLock );
 497
 498         // Delete from active list
 499         #if SCHEDULER_TYPE == SCHED_RR_PRI
 500         if( !Threads_int_DelFromQueue( &gaActiveThreads[Thread->Priority], Thread ) )
 501         #else
 502         if( !Threads_int_DelFromQueue( &gActiveThreads, Thread ) )
 503         #endif
 504         {
 505                 Warning("Proc_Exit - Current thread is not on the active queue");
 506                 SHORTREL( &glThreadListLock );
 507                 SHORTREL( &Thread->IsLocked );
 508                 return;
 509         }
 510
 511         // Ensure that we are not rescheduled
 512         Thread->Remaining = 0;  // Clear Remaining Quantum
 513         Thread->Quantum = 0;    // Clear Quantum to indicate dead thread
 514
 515         // Update bookkeeping
 516         giNumActiveThreads --;
 517         #if SCHEDULER_TYPE == SCHED_LOTTERY
 518         if( Thread != Proc_GetCurThread() )
 519                 giFreeTickets -= caiTICKET_COUNTS[ Thread->Priority ];
 520         #endif
 521
 522         // Save exit status
 523         Thread->RetStatus = Status;
 524
 525         // Don't Zombie if we are being killed because our parent is
 526         if(Status == -1)
 527         {
 528                 Thread->Status = THREAD_STAT_DEAD;
 529                 Threads_AddToDelete( Thread );
 530         } else {
 531                 Thread->Status = THREAD_STAT_ZOMBIE;
 532                 // Wake parent
 533                 Threads_Wake( Thread->Parent );
 534         }
 535
 536         Log("Thread %i went *hurk* (%i)", Thread->TID, Thread->Status);
 537
 538         // Release spinlocks
 539         SHORTREL( &glThreadListLock );
 540         SHORTREL( &Thread->IsLocked );  // TODO: We may not actually be released...
 541
 542         // And, reschedule
 543         if(Status != -1) {
 544                 for( ;; )
 545                         HALT();
 546         }
 547 }
 548
 549 /**
 550  * \brief Yield remainder of the current thread's timeslice
 551  */
 552 void Threads_Yield(void)
 553 {
 554         tThread *thread = Proc_GetCurThread();
 555         thread->Remaining = 0;
 556         //while(thread->Remaining == 0)
 557                 HALT();
 558 }
 559
 560 /**
 561  * \fn void Threads_Sleep(void)
 562  * \brief Take the current process off the run queue
 563  */
 564 void Threads_Sleep(void)
 565 {
 566         tThread *cur = Proc_GetCurThread();
 567
 568         // Acquire Spinlock
 569         SHORTLOCK( &glThreadListLock );
 570
 571         // Don't sleep if there is a message waiting
 572         if( cur->Messages ) {
 573                 SHORTREL( &glThreadListLock );
 574                 return;
 575         }
 576
 577         // Remove us from running queue
 578         Threads_RemActive();
 579         // Mark thread as sleeping
 580         cur->Status = THREAD_STAT_SLEEPING;
 581
 582         // Add to Sleeping List (at the top)
 583         cur->Next = gSleepingThreads;
 584         gSleepingThreads = cur;
 585
 586
 587         #if DEBUG_TRACE_STATE
 588         Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName);
 589         #endif
 590
 591         // Release Spinlock
 592         SHORTREL( &glThreadListLock );
 593
 594         while(cur->Status != THREAD_STAT_ACTIVE)        HALT();
 595 }
 596
 597
 598 /**
 599  * \fn int Threads_Wake( tThread *Thread )
 600  * \brief Wakes a sleeping/waiting thread up
 601  * \param Thread        Thread to wake
 602  * \return Boolean Failure (Returns ERRNO)
 603  * \warning This should ONLY be called with task switches disabled
 604  */
 605 int Threads_Wake(tThread *Thread)
 606 {
 607         if(!Thread)
 608                 return -EINVAL;
 609
 610         switch(Thread->Status)
 611         {
 612         case THREAD_STAT_ACTIVE:
 613                 Log("Thread_Wake: Waking awake thread (%i)", Thread->TID);
 614                 return -EALREADY;
 615
 616         case THREAD_STAT_SLEEPING:
 617                 SHORTLOCK( &glThreadListLock );
 618                 // Remove from sleeping queue
 619                 Threads_int_DelFromQueue(&gSleepingThreads, Thread);
 620
 621                 Threads_AddActive( Thread );
 622
 623                 #if DEBUG_TRACE_STATE
 624                 Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName);
 625                 #endif
 626                 SHORTREL( &glThreadListLock );
 627                 return -EOK;
 628
 629         case THREAD_STAT_WAITING:
 630                 Warning("Thread_Wake - Waiting threads are not currently supported");
 631                 return -ENOTIMPL;
 632
 633         case THREAD_STAT_DEAD:
 634                 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
 635                 return -ENOTIMPL;
 636
 637         default:
 638                 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
 639                 return -EINTERNAL;
 640         }
 641 }
 642
 643 /**
 644  * \brief Wake a thread given the TID
 645  * \param TID   Thread ID to wake
 646  * \return Boolean Faulure (errno)
 647  */
 648 int Threads_WakeTID(tTID TID)
 649 {
 650         tThread *thread = Threads_GetThread(TID);
 651          int    ret;
 652         if(!thread)
 653                 return -ENOENT;
 654         ret = Threads_Wake( thread );
 655         //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread);
 656         return ret;
 657 }
 658
 659 /**
 660  * \brief Adds a thread to the active queue
 661  */
 662 void Threads_AddActive(tThread *Thread)
 663 {
 664         SHORTLOCK( &glThreadListLock );
 665
 666         if( Thread->Status == THREAD_STAT_ACTIVE ) {
 667                 tThread *cur = Proc_GetCurThread();
 668                 Warning("WTF, CPU%i %p (%i %s) is adding %p (%i %s) when it is active",
 669                         GetCPUNum(), cur, cur->TID, cur->ThreadName, Thread, Thread->TID, Thread->ThreadName);
 670         }
 671
 672         // Set state
 673         Thread->Status = THREAD_STAT_ACTIVE;
 674         Thread->CurCPU = -1;
 675         // Add to active list
 676         #if SCHEDULER_TYPE == SCHED_RR_PRI
 677         Thread->Next = gaActiveThreads[Thread->Priority];
 678         gaActiveThreads[Thread->Priority] = Thread;
 679         #else
 680         Thread->Next = gActiveThreads;
 681         gActiveThreads = Thread;
 682         #endif
 683
 684         // Update bookkeeping
 685         giNumActiveThreads ++;
 686
 687         #if SCHEDULER_TYPE == SCHED_LOTTERY
 688         giFreeTickets += caiTICKET_COUNTS[ Thread->Priority ];
 689         # if DEBUG_TRACE_TICKETS
 690         Log("Threads_AddActive: CPU%i %p %i (%s) added, new giFreeTickets = %i",
 691                 GetCPUNum(), Thread, Thread->TID, Thread->ThreadName, giFreeTickets);
 692         # endif
 693         #endif
 694
 695         SHORTREL( &glThreadListLock );
 696 }
 697
 698 /**
 699  * \brief Removes the current thread from the active queue
 700  * \warning This should ONLY be called with task switches disabled
 701  * \return Current thread pointer
 702  */
 703 tThread *Threads_RemActive(void)
 704 {
 705         tThread *ret = Proc_GetCurThread();
 706
 707         SHORTLOCK( &glThreadListLock );
 708
 709         // Delete from active queue
 710         #if SCHEDULER_TYPE == SCHED_RR_PRI
 711         if( !Threads_int_DelFromQueue(&gaActiveThreads[ret->Priority], ret) )
 712         #else
 713         if( !Threads_int_DelFromQueue(&gActiveThreads, ret) )
 714         #endif
 715         {
 716                 SHORTREL( &glThreadListLock );
 717                 return NULL;
 718         }
 719
 720         ret->Next = NULL;
 721         ret->Remaining = 0;
 722         ret->CurCPU = -1;
 723
 724         giNumActiveThreads --;
 725         // no need to decrement tickets, scheduler did it for us
 726
 727         #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
 728         Log("Threads_RemActive: CPU%i %p %i (%s) removed, giFreeTickets = %i",
 729                 GetCPUNum(), ret, ret->TID, ret->ThreadName, giFreeTickets);
 730         #endif
 731
 732         SHORTREL( &glThreadListLock );
 733
 734         return ret;
 735 }
 736
 737 /**
 738  * \fn void Threads_SetFaultHandler(Uint Handler)
 739  * \brief Sets the signal handler for a signal
 740  */
 741 void Threads_SetFaultHandler(Uint Handler)
 742 {
 743         //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
 744         Proc_GetCurThread()->FaultHandler = Handler;
 745 }
 746
 747 /**
 748  * \fn void Threads_Fault(int Num)
 749  * \brief Calls a fault handler
 750  */
 751 void Threads_Fault(int Num)
 752 {
 753         tThread *thread = Proc_GetCurThread();
 754
 755         Log_Log("Threads", "Threads_Fault: thread = %p", thread);
 756
 757         if(!thread)     return ;
 758
 759         Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
 760
 761         switch(thread->FaultHandler)
 762         {
 763         case 0: // Panic?
 764                 Threads_Kill(thread, -1);
 765                 HALT();
 766                 return ;
 767         case 1: // Dump Core?
 768                 Threads_Kill(thread, -1);
 769                 HALT();
 770                 return ;
 771         }
 772
 773         // Double Fault? Oh, F**k
 774         if(thread->CurFaultNum != 0) {
 775                 Threads_Kill(thread, -1);       // For now, just kill
 776                 HALT();
 777         }
 778
 779         thread->CurFaultNum = Num;
 780
 781         Proc_CallFaultHandler(thread);
 782 }
 783
 784 // --- Process Structure Access Functions ---
 785 tPID Threads_GetPID(void)
 786 {
 787         return Proc_GetCurThread()->TGID;
 788 }
 789 tTID Threads_GetTID(void)
 790 {
 791         return Proc_GetCurThread()->TID;
 792 }
 793 tUID Threads_GetUID(void)
 794 {
 795         return Proc_GetCurThread()->UID;
 796 }
 797 tGID Threads_GetGID(void)
 798 {
 799         return Proc_GetCurThread()->GID;
 800 }
 801
 802 int Threads_SetUID(Uint *Errno, tUID ID)
 803 {
 804         tThread *t = Proc_GetCurThread();
 805         if( t->UID != 0 ) {
 806                 *Errno = -EACCES;
 807                 return -1;
 808         }
 809         Log_Debug("Threads", "TID %i's UID set to %i", t->TID, ID);
 810         t->UID = ID;
 811         return 0;
 812 }
 813
 814 int Threads_SetGID(Uint *Errno, tGID ID)
 815 {
 816         tThread *t = Proc_GetCurThread();
 817         if( t->UID != 0 ) {
 818                 *Errno = -EACCES;
 819                 return -1;
 820         }
 821         Log_Debug("Threads", "TID %i's GID set to %i", t->TID, ID);
 822         t->GID = ID;
 823         return 0;
 824 }
 825
 826 /**
 827  * \fn void Threads_Dump(void)
 828  */
 829 void Threads_DumpActive(void)
 830 {
 831         tThread *thread;
 832         #if SCHEDULER_TYPE == SCHED_RR_PRI
 833          int    i;
 834         #endif
 835
 836         Log("Active Threads: (%i reported)", giNumActiveThreads);
 837
 838         #if SCHEDULER_TYPE == SCHED_RR_PRI
 839         for( i = 0; i < MIN_PRIORITY+1; i++ )
 840         {
 841                 for(thread=gaActiveThreads[i];thread;thread=thread->Next)
 842         #else
 843                 for(thread=gActiveThreads;thread;thread=thread->Next)
 844         #endif
 845                 {
 846                         Log(" %p %i (%i) - %s (CPU %i)",
 847                                 thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 848                         if(thread->Status != THREAD_STAT_ACTIVE)
 849                                 Log("  ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE);
 850                         Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
 851                         Log("  KStack 0x%x", thread->KernelStack);
 852                 }
 853
 854         #if SCHEDULER_TYPE == SCHED_RR_PRI
 855         }
 856         #endif
 857 }
 858
 859 /**
 860  * \fn void Threads_Dump(void)
 861  * \brief Dumps a list of currently running threads
 862  */
 863 void Threads_Dump(void)
 864 {
 865         tThread *thread;
 866
 867         Log("--- Thread Dump ---");
 868         Threads_DumpActive();
 869
 870         Log("All Threads:");
 871         for(thread=gAllThreads;thread;thread=thread->GlobalNext)
 872         {
 873                 Log(" %p %i (%i) - %s (CPU %i)",
 874                         thread, thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 875                 Log("  State %i (%s)", thread->Status, casTHREAD_STAT[thread->Status]);
 876                 switch(thread->Status)
 877                 {
 878                 case THREAD_STAT_MUTEXSLEEP:
 879                         Log("  Mutex Pointer: %p", thread->WaitPointer);
 880                         break;
 881                 case THREAD_STAT_ZOMBIE:
 882                         Log("  Return Status: %i", thread->RetStatus);
 883                         break;
 884                 default:        break;
 885                 }
 886                 Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
 887                 Log("  KStack 0x%x", thread->KernelStack);
 888         }
 889 }
 890
 891 /**
 892  * \brief Gets the next thread to run
 893  * \param CPU   Current CPU
 894  * \param Last  The thread the CPU was running
 895  */
 896 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
 897 {
 898         tThread *thread;
 899
 900         // If this CPU has the lock, we must let it complete
 901         if( CPU_HAS_LOCK( &glThreadListLock ) )
 902                 return Last;
 903
 904         // Don't change threads if the current CPU has switches disabled
 905         if( gaThreads_NoTaskSwitch[CPU] )
 906                 return Last;
 907
 908
 909         // Lock thread list
 910         SHORTLOCK( &glThreadListLock );
 911
 912         // Clear Delete Queue
 913         // - I should probably put this in a worker thread to avoid calling free() in the scheduler
 914         while(gDeleteThreads)
 915         {
 916                 thread = gDeleteThreads->Next;
 917                 if( IS_LOCKED(&gDeleteThreads->IsLocked) ) {    // Only free if structure is unused
 918                         // Set to dead
 919                         gDeleteThreads->Status = THREAD_STAT_BURIED;
 920                         // Free name
 921                         if( IsHeap(gDeleteThreads->ThreadName) )
 922                                 free(gDeleteThreads->ThreadName);
 923                         // Remove from global list
 924                         if( gDeleteThreads == gAllThreads )
 925                                 gAllThreads = gDeleteThreads->GlobalNext;
 926                         else
 927                                 gDeleteThreads->GlobalPrev->GlobalNext = gDeleteThreads->GlobalNext;
 928                         free( gDeleteThreads );
 929                 }
 930                 gDeleteThreads = thread;
 931         }
 932
 933         // No active threads, just take a nap
 934         if(giNumActiveThreads == 0) {
 935                 SHORTREL( &glThreadListLock );
 936                 #if DEBUG_TRACE_TICKETS
 937                 Log("No active threads");
 938                 #endif
 939                 return NULL;
 940         }
 941
 942         #if SCHEDULER_TYPE != SCHED_RR_PRI
 943         // Special case: 1 thread
 944         if(giNumActiveThreads == 1) {
 945                 if( gActiveThreads->CurCPU == -1 )
 946                         gActiveThreads->CurCPU = CPU;
 947
 948                 SHORTREL( &glThreadListLock );
 949
 950                 if( gActiveThreads->CurCPU == CPU )
 951                         return gActiveThreads;
 952
 953                 return NULL;    // CPU has nothing to do
 954         }
 955         #endif
 956
 957         // Allow the old thread to be scheduled again
 958         if( Last ) {
 959                 if( Last->Status == THREAD_STAT_ACTIVE ) {
 960                         #if SCHEDULER_TYPE == SCHED_LOTTERY
 961                         giFreeTickets += caiTICKET_COUNTS[ Last->Priority ];
 962                         # if DEBUG_TRACE_TICKETS
 963                         LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n",
 964                                 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets);
 965                         # endif
 966                         #endif
 967                 }
 968                 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
 969                 else
 970                         LogF(" CPU %i released %p (%i %s)->Status = %i (Released)\n",
 971                                 CPU, Last, Last->TID, Last->ThreadName, Last->Status);
 972                 #endif
 973                 Last->CurCPU = -1;
 974         }
 975
 976         // ---
 977         // Lottery Scheduler
 978         // ---
 979         #if SCHEDULER_TYPE == SCHED_LOTTERY
 980         {
 981                  int    ticket, number;
 982                 # if 1
 983                 number = 0;
 984                 for(thread = gActiveThreads; thread; thread = thread->Next) {
 985                         if(thread->CurCPU >= 0) continue;
 986                         if(thread->Status != THREAD_STAT_ACTIVE)
 987                                 Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i",
 988                                         thread, thread->TID, thread->ThreadName, thread->Status);
 989                         if(thread->Next == thread) {
 990                                 Panic("Bookkeeping fail - %p %i(%s) loops back on itself",
 991                                         thread, thread->TID, thread->ThreadName, thread->Status);
 992                         }
 993                         number += caiTICKET_COUNTS[ thread->Priority ];
 994                 }
 995                 if(number != giFreeTickets) {
 996                         Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
 997                                 giFreeTickets, number, CPU);
 998                 }
 999                 # endif
1000
1001                 // No free tickets (all tasks delegated to cores)
1002                 if( giFreeTickets == 0 ) {
1003                         SHORTREL(&glThreadListLock);
1004                         return NULL;
1005                 }
1006
1007                 // Get the ticket number
1008                 ticket = number = rand() % giFreeTickets;
1009
1010                 // Find the next thread
1011                 for(thread=gActiveThreads;thread;thread=thread->Next)
1012                 {
1013                         if(thread->CurCPU >= 0) continue;
1014                         if( caiTICKET_COUNTS[ thread->Priority ] > number)      break;
1015                         number -= caiTICKET_COUNTS[ thread->Priority ];
1016                 }
1017
1018                 // If we didn't find a thread, something went wrong
1019                 if(thread == NULL)
1020                 {
1021                         number = 0;
1022                         for(thread=gActiveThreads;thread;thread=thread->Next) {
1023                                 if(thread->CurCPU >= 0) continue;
1024                                 number += caiTICKET_COUNTS[ thread->Priority ];
1025                         }
1026                         Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
1027                                 giFreeTickets, number);
1028                 }
1029                 # if DEBUG_TRACE_TICKETS
1030                 LogF(" CPU%i giFreeTickets = %i, running %p (%i %s CPU=%i)\n",
1031                         CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU);
1032                 # endif
1033
1034                 giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ];
1035         }
1036
1037         // ---
1038         // Priority based round robin scheduler
1039         // ---
1040         #elif SCHEDULER_TYPE == SCHED_RR_PRI
1041         {
1042                  int    i;
1043                 for( i = 0; i < MIN_PRIORITY + 1; i ++ )
1044                 {
1045                         for(thread = gaActiveThreads[i]; thread; thread = thread->Next)
1046                         {
1047                                 if( thread->CurCPU == -1 )      break;
1048                         }
1049                         // If we fall onto the same queue again, special handling is
1050                         // needed
1051                         if( i == Last->Priority ) {
1052                                 tThread *savedThread = thread;
1053
1054                                 // Find the next unscheduled thread in the list
1055                                 for( thread = Last->Next; thread; thread = thread->Next )
1056                                 {
1057                                         if( thread->CurCPU == -1 )      break;
1058                                 }
1059                                 // If we don't find anything after, just use the one
1060                                 // found above.
1061                                 if( !thread )   thread = savedThread;
1062                         }
1063                         // Found a thread? Schedule it!
1064                         if( thread )    break;
1065                 }
1066
1067                 // Anything to do?
1068                 if( !thread ) {
1069                         SHORTREL(&glThreadListLock);
1070                         return NULL;
1071                 }
1072         }
1073         #elif SCHEDULER_TYPE == SCHED_RR_SIM
1074         {
1075                 // Find the next unscheduled thread in the list
1076                 for( thread = Last->Next; thread; thread = thread->Next )
1077                 {
1078                         if( thread->CurCPU == -1 )      break;
1079                 }
1080                 // If we don't find anything after, search from the beginning
1081                 if( !thread )
1082                 {
1083                         for(thread = gActiveThreads; thread; thread = thread->Next)
1084                         {
1085                                 if( thread->CurCPU == -1 )      break;
1086                         }
1087                 }
1088
1089                 // Anything to do?
1090                 if( !thread ) {
1091                         SHORTREL(&glThreadListLock);
1092                         return NULL;
1093                 }
1094         }
1095         #else
1096         # error "Unimplemented scheduling algorithm"
1097         #endif
1098
1099         // Make the new thread non-schedulable
1100         thread->CurCPU = CPU;
1101
1102         SHORTREL( &glThreadListLock );
1103
1104         return thread;
1105 }
1106
1107 /**
1108  * \fn void Threads_SegFault(tVAddr Addr)
1109  * \brief Called when a Segment Fault occurs
1110  */
1111 void Threads_SegFault(tVAddr Addr)
1112 {
1113         Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr);
1114         Threads_Fault( 1 );
1115         //Threads_Exit( 0, -1 );
1116 }
1117
1118 /**
1119  * \brief Acquire a heavy mutex
1120  * \param Mutex Mutex to acquire
1121  *
1122  * This type of mutex checks if the mutex is avaliable, and acquires it
1123  * if it is. Otherwise, the current thread is added to the mutex's wait
1124  * queue and the thread suspends. When the holder of the mutex completes,
1125  * the oldest thread (top thread) on the queue is given the lock and
1126  * restarted.
1127  */
1128 void Mutex_Acquire(tMutex *Mutex)
1129 {
1130         tThread *us = Proc_GetCurThread();
1131
1132         // Get protector
1133         SHORTLOCK( &Mutex->Protector );
1134
1135         //Log("Mutex_Acquire: (%p)", Mutex);
1136
1137         // Check if the lock is already held
1138         if( Mutex->Owner ) {
1139                 SHORTLOCK( &glThreadListLock );
1140                 // - Remove from active list
1141                 us = Threads_RemActive();
1142                 us->Next = NULL;
1143                 // - Mark as sleeping
1144                 us->Status = THREAD_STAT_MUTEXSLEEP;
1145                 us->WaitPointer = Mutex;
1146
1147                 // - Add to waiting
1148                 if(Mutex->LastWaiting) {
1149                         Mutex->LastWaiting->Next = us;
1150                         Mutex->LastWaiting = us;
1151                 }
1152                 else {
1153                         Mutex->Waiting = us;
1154                         Mutex->LastWaiting = us;
1155                 }
1156                 #if 0
1157                 {
1158                          int    i = 0;
1159                         tThread *t;
1160                         for( t = Mutex->Waiting; t; t = t->Next, i++ )
1161                                 Log("[%i] (tMutex)%p->Waiting[%i] = %p (%i %s)", us->TID, Mutex, i,
1162                                         t, t->TID, t->ThreadName);
1163                 }
1164                 #endif
1165
1166                 SHORTREL( &glThreadListLock );
1167                 SHORTREL( &Mutex->Protector );
1168                 while(us->Status == THREAD_STAT_MUTEXSLEEP)     Threads_Yield();
1169                 // We're only woken when we get the lock
1170                 us->WaitPointer = NULL;
1171         }
1172         // Ooh, let's take it!
1173         else {
1174                 Mutex->Owner = us;
1175                 SHORTREL( &Mutex->Protector );
1176         }
1177
1178         #if 0
1179         extern tMutex   glPhysAlloc;
1180         if( Mutex != &glPhysAlloc )
1181                 LogF("Mutex %p taken by %i %p\n", Mutex, us->TID, __builtin_return_address(0));
1182         #endif
1183 }
1184
1185 /**
1186  * \brief Release a held mutex
1187  * \param Mutex Mutex to release
1188  */
1189 void Mutex_Release(tMutex *Mutex)
1190 {
1191         SHORTLOCK( &Mutex->Protector );
1192         //Log("Mutex_Release: (%p)", Mutex);
1193         if( Mutex->Waiting ) {
1194                 Mutex->Owner = Mutex->Waiting;  // Set owner
1195                 Mutex->Waiting = Mutex->Waiting->Next;  // Next!
1196                 // Reset ->LastWaiting to NULL if we have just removed the last waiting thread
1197                 // 2010-10-02 21:50 - Comemerating the death of the longest single
1198                 //                    blocker in the Acess2 history. REMEMBER TO
1199                 //                    FUCKING MAINTAIN YOUR FUCKING LISTS DIPWIT
1200                 if( Mutex->LastWaiting == Mutex->Owner )
1201                         Mutex->LastWaiting = NULL;
1202
1203                 // Wake new owner
1204                 SHORTLOCK( &glThreadListLock );
1205                 if( Mutex->Owner->Status != THREAD_STAT_ACTIVE )
1206                         Threads_AddActive(Mutex->Owner);
1207                 SHORTREL( &glThreadListLock );
1208         }
1209         else {
1210                 Mutex->Owner = NULL;
1211         }
1212         SHORTREL( &Mutex->Protector );
1213
1214         #if 0
1215         extern tMutex   glPhysAlloc;
1216         if( Mutex != &glPhysAlloc )
1217                 LogF("Mutex %p released by %i %p\n", Mutex, Threads_GetTID(), __builtin_return_address(0));
1218         #endif
1219 }
1220
1221 /**
1222  * \brief Is this mutex locked?
1223  * \param Mutex Mutex pointer
1224  */
1225 int Mutex_IsLocked(tMutex *Mutex)
1226 {
1227         return Mutex->Owner != NULL;
1228 }
1229
1230 // === EXPORTS ===
1231 EXPORT(Threads_GetUID);
1232 EXPORT(Threads_GetGID);
1233 EXPORT(Mutex_Acquire);
1234 EXPORT(Mutex_Release);
1235 EXPORT(Mutex_IsLocked);