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 #define DEBUG_TRACE_TICKETS     0       // Trace ticket counts
  11 #define DEBUG_TRACE_STATE       0       // Trace state changes (sleep/wake)
  12
  13 // === CONSTANTS ===
  14 #define DEFAULT_QUANTUM 10
  15 #define DEFAULT_TICKETS 5
  16 #define MAX_TICKETS             10
  17 const enum eConfigTypes cCONFIG_TYPES[] = {
  18         CFGT_HEAPSTR,   // e.g. CFG_VFS_CWD
  19         CFGT_INT,       // e.g. CFG_VFS_MAXFILES
  20         CFGT_NULL
  21 };
  22
  23 // === IMPORTS ===
  24 extern void     ArchThreads_Init(void);
  25 extern void     Proc_Start(void);
  26 extern tThread  *Proc_GetCurThread(void);
  27 extern int      Proc_Clone(Uint *Err, Uint Flags);
  28 extern void     Proc_CallFaultHandler(tThread *Thread);
  29
  30 // === PROTOTYPES ===
  31 void    Threads_Init(void);
  32  int    Threads_SetName(char *NewName);
  33 char    *Threads_GetName(int ID);
  34 void    Threads_SetTickets(tThread *Thread, int Num);
  35 tThread *Threads_CloneTCB(Uint *Err, Uint Flags);
  36  int    Threads_WaitTID(int TID, int *status);
  37 tThread *Threads_GetThread(Uint TID);
  38 void    Threads_AddToDelete(tThread *Thread);
  39 tThread *Threads_int_GetPrev(tThread **List, tThread *Thread);
  40 void    Threads_Exit(int TID, int Status);
  41 void    Threads_Kill(tThread *Thread, int Status);
  42 void    Threads_Yield(void);
  43 void    Threads_Sleep(void);
  44  int    Threads_Wake(tThread *Thread);
  45 void    Threads_AddActive(tThread *Thread);
  46 tThread *Threads_RemActive(void);
  47  int    Threads_GetPID(void);
  48  int    Threads_GetTID(void);
  49 tUID    Threads_GetUID(void);
  50  int    Threads_SetUID(Uint *Errno, tUID ID);
  51 tGID    Threads_GetGID(void);
  52  int    Threads_SetGID(Uint *Errno, tUID ID);
  53 void    Threads_Dump(void);
  54 void    Mutex_Acquire(tMutex *Mutex);
  55 void    Mutex_Release(tMutex *Mutex);
  56  int    Mutex_IsLocked(tMutex *Mutex);
  57
  58 // === GLOBALS ===
  59 // -- Core Thread --
  60 // Only used for the core kernel
  61 tThread gThreadZero = {
  62         Status: THREAD_STAT_ACTIVE,     // Status
  63         ThreadName:     "ThreadZero",   // Name
  64         Quantum: DEFAULT_QUANTUM,       // Default Quantum
  65         Remaining:      DEFAULT_QUANTUM,        // Current Quantum
  66         NumTickets:     DEFAULT_TICKETS // Number of tickets
  67         };
  68 // -- Processes --
  69 // --- Locks ---
  70 tShortSpinlock  glThreadListLock;       ///\note NEVER use a heap function while locked
  71 // --- Current State ---
  72 volatile int    giNumActiveThreads = 0;
  73 volatile int    giFreeTickets = 0;
  74 volatile Uint   giNextTID = 1;
  75 // --- Thread Lists ---
  76 tThread *gAllThreads = NULL;            // All allocated threads
  77 tThread *gActiveThreads = NULL;         // Currently Running Threads
  78 tThread *gSleepingThreads = NULL;       // Sleeping Threads
  79 tThread *gDeleteThreads = NULL;         // Threads to delete
  80  int    giNumCPUs = 1;
  81
  82 // === CODE ===
  83 /**
  84  * \fn void Threads_Init(void)
  85  * \brief Initialse the thread list
  86  */
  87 void Threads_Init(void)
  88 {
  89         ArchThreads_Init();
  90
  91         // Create Initial Task
  92         gActiveThreads = &gThreadZero;
  93         gAllThreads = &gThreadZero;
  94         //giFreeTickets = gThreadZero.NumTickets;       // Not needed, as ThreadZero is running
  95         giNumActiveThreads = 1;
  96
  97         Proc_Start();
  98 }
  99
 100 /**
 101  * \fn void Threads_SetName(char *NewName)
 102  * \brief Sets the current thread's name
 103  */
 104 int Threads_SetName(char *NewName)
 105 {
 106         tThread *cur = Proc_GetCurThread();
 107         char    *oldname = cur->ThreadName;
 108
 109         cur->ThreadName = NULL;
 110
 111         if( IsHeap(oldname) )   free( oldname );
 112
 113         cur->ThreadName = strdup(NewName);
 114         return 0;
 115 }
 116
 117 /**
 118  * \fn char *Threads_GetName(int ID)
 119  * \brief Gets a thread's name
 120  */
 121 char *Threads_GetName(int ID)
 122 {
 123         if(ID == -1) {
 124                 return Proc_GetCurThread()->ThreadName;
 125         }
 126         // TODO: Find a thread and get its name
 127         return NULL;
 128 }
 129
 130 /**
 131  * \fn void Threads_SetTickets(tThread *Thread, int Num)
 132  * \brief Sets the 'priority' of a task
 133  */
 134 void Threads_SetTickets(tThread *Thread, int Num)
 135 {
 136         if(Thread == NULL)
 137                 Thread = Proc_GetCurThread();
 138         if(Num < 0)     return;
 139         if(Num > MAX_TICKETS)   Num = MAX_TICKETS;
 140
 141         if( Thread != Proc_GetCurThread() ) {
 142                 SHORTLOCK( &glThreadListLock );
 143                 giFreeTickets -= Thread->NumTickets - Num;
 144                 Thread->NumTickets = Num;
 145                 SHORTREL( &glThreadListLock );
 146         }
 147         else
 148                 Thread->NumTickets = Num;
 149 }
 150
 151 /**
 152  * \fn tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
 153  */
 154 tThread *Threads_CloneTCB(Uint *Err, Uint Flags)
 155 {
 156         tThread *cur, *new;
 157          int    i;
 158         cur = Proc_GetCurThread();
 159
 160         new = malloc(sizeof(tThread));
 161         if(new == NULL) {
 162                 *Err = -ENOMEM;
 163                 return NULL;
 164         }
 165         memcpy(new, cur, sizeof(tThread));
 166
 167         new->CurCPU = -1;
 168         new->Next = NULL;
 169         memset( &new->IsLocked, 0, sizeof(new->IsLocked));
 170         new->Status = THREAD_STAT_ACTIVE;
 171         new->RetStatus = 0;
 172
 173         // Get Thread ID
 174         new->TID = giNextTID++;
 175         new->Parent = cur;
 176
 177         // Clone Name
 178         new->ThreadName = strdup(cur->ThreadName);
 179
 180         // Set Thread Group ID (PID)
 181         if(Flags & CLONE_VM)
 182                 new->TGID = new->TID;
 183         else
 184                 new->TGID = cur->TGID;
 185
 186         // Messages are not inherited
 187         new->Messages = NULL;
 188         new->LastMessage = NULL;
 189
 190         // Set State
 191         new->Remaining = new->Quantum = cur->Quantum;
 192         new->NumTickets = cur->NumTickets;
 193
 194         // Set Signal Handlers
 195         new->CurFaultNum = 0;
 196         new->FaultHandler = cur->FaultHandler;
 197
 198         for( i = 0; i < NUM_CFG_ENTRIES; i ++ )
 199         {
 200                 switch(cCONFIG_TYPES[i])
 201                 {
 202                 default:
 203                         new->Config[i] = cur->Config[i];
 204                         break;
 205                 case CFGT_HEAPSTR:
 206                         if(cur->Config[i])
 207                                 new->Config[i] = (Uint) strdup( (void*)cur->Config[i] );
 208                         else
 209                                 new->Config[i] = 0;
 210                         break;
 211                 }
 212         }
 213
 214         // Maintain a global list of threads
 215         SHORTLOCK( &glThreadListLock );
 216         new->GlobalPrev = NULL; // Protect against bugs
 217         new->GlobalNext = gAllThreads;
 218         gAllThreads = new;
 219         SHORTREL( &glThreadListLock );
 220
 221         return new;
 222 }
 223
 224 /**
 225  * \fn Uint *Threads_GetCfgPtr(int Id)
 226  */
 227 Uint *Threads_GetCfgPtr(int Id)
 228 {
 229         if(Id < 0 || Id >= NUM_CFG_ENTRIES) {
 230                 Warning("Threads_GetCfgPtr: Index %i is out of bounds", Id);
 231                 return NULL;
 232         }
 233
 234         return &Proc_GetCurThread()->Config[Id];
 235 }
 236
 237 /**
 238  * \fn tTID Threads_WaitTID(int TID, int *status)
 239  * \brief Wait for a task to change state
 240  * \return TID of child that changed state
 241  */
 242 int Threads_WaitTID(int TID, int *status)
 243 {
 244         // Any Child
 245         if(TID == -1) {
 246                 Log_Error("Threads", "TODO: Threads_WaitTID(TID=-1) - Any Child");
 247                 return -1;
 248         }
 249
 250         // Any peer/child thread
 251         if(TID == 0) {
 252                 Log_Error("Threads", "TODO: Threads_WaitTID(TID=0) - Any Child/Sibling");
 253                 return -1;
 254         }
 255
 256         // TGID = abs(TID)
 257         if(TID < -1) {
 258                 Log_Error("Threads", "TODO: Threads_WaitTID(TID<0) - TGID");
 259                 return -1;
 260         }
 261
 262         // Specific Thread
 263         if(TID > 0) {
 264                 tThread *t = Threads_GetThread(TID);
 265                  int    initStatus = t->Status;
 266                  int    ret;
 267
 268                 if(initStatus != THREAD_STAT_ZOMBIE) {
 269                         // TODO: Handle child also being suspended if wanted
 270                         while(t->Status != THREAD_STAT_ZOMBIE) {
 271                                 Threads_Sleep();
 272                                 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
 273                                         Threads_GetTID(), t->TID, t->Status);
 274                         }
 275                 }
 276
 277                 Log_Debug("Threads", "%i waiting for %i, t->Status = %i",
 278                         Threads_GetTID(), t->TID, t->Status);
 279                 ret = t->RetStatus;
 280                 switch(t->Status)
 281                 {
 282                 case THREAD_STAT_ZOMBIE:
 283                         // Kill the thread
 284                         t->Status = THREAD_STAT_DEAD;
 285                         // TODO: Child return value?
 286                         if(status)      *status = 0;
 287                         // add to delete queue
 288                         Threads_AddToDelete( t );
 289                         break;
 290                 default:
 291                         if(status)      *status = -1;
 292                         break;
 293                 }
 294                 return ret;
 295         }
 296
 297         return -1;
 298 }
 299
 300 /**
 301  * \fn tThread *Threads_GetThread(Uint TID)
 302  * \brief Gets a thread given its TID
 303  * \param TID   Thread ID
 304  */
 305 tThread *Threads_GetThread(Uint TID)
 306 {
 307         tThread *thread;
 308
 309         // Search global list
 310         for(thread = gAllThreads;
 311                 thread;
 312                 thread = thread->GlobalNext)
 313         {
 314                 if(thread->TID == TID)
 315                         return thread;
 316         }
 317
 318         Log("Unable to find TID %i on main list\n", TID);
 319
 320         return NULL;
 321 }
 322
 323 /**
 324  * \fn void Threads_AddToDelete(tThread *Thread)
 325  * \brief Adds a thread to the delete queue
 326  */
 327 void Threads_AddToDelete(tThread *Thread)
 328 {
 329         // Add to delete queue
 330         if(gDeleteThreads) {
 331                 Thread->Next = gDeleteThreads;
 332                 gDeleteThreads = Thread;
 333         } else {
 334                 Thread->Next = NULL;
 335                 gDeleteThreads = Thread;
 336         }
 337 }
 338
 339 /**
 340  * \fn tThread *Threads_int_GetPrev(tThread **List, tThread *Thread)
 341  * \brief Gets the previous entry in a thead linked list
 342  */
 343 tThread *Threads_int_GetPrev(tThread **List, tThread *Thread)
 344 {
 345         tThread *ret;
 346         // First Entry
 347         if(*List == Thread) {
 348                 return (tThread*)List;
 349         } else {
 350                 for(ret = *List;
 351                         ret->Next && ret->Next != Thread;
 352                         ret = ret->Next
 353                         );
 354                 // Error if the thread is not on the list
 355                 if(!ret->Next || ret->Next != Thread) {
 356                         return NULL;
 357                 }
 358         }
 359         return ret;
 360 }
 361
 362 /**
 363  * \fn void Threads_Exit(int TID, int Status)
 364  * \brief Exit the current process
 365  */
 366 void Threads_Exit(int TID, int Status)
 367 {
 368         if( TID == 0 )
 369                 Threads_Kill( Proc_GetCurThread(), (Uint)Status & 0xFF );
 370         else
 371                 Threads_Kill( Threads_GetThread(TID), (Uint)Status & 0xFF );
 372         // Halt forever, just in case
 373         for(;;)
 374                 HALT();
 375 }
 376
 377 /**
 378  * \fn void Threads_Kill(tThread *Thread, int Status)
 379  * \brief Kill a thread
 380  * \param Thread        Thread to kill
 381  * \param Status        Status code to return to the parent
 382  */
 383 void Threads_Kill(tThread *Thread, int Status)
 384 {
 385         tThread *prev;
 386         tMsg    *msg;
 387
 388         // TODO: Kill all children
 389         #if 0
 390         {
 391                 tThread *child;
 392                 for(child = gActiveThreads;
 393                         child;
 394                         child = child->Next)
 395                 {
 396                         if(child->PTID == Thread->TID)
 397                                 Threads_Kill(child, -1);
 398                 }
 399         }
 400         #endif
 401
 402         ///\note Double lock is needed due to overlap of lock areas
 403
 404         // Lock thread (stop us recieving messages)
 405         SHORTLOCK( &Thread->IsLocked );
 406
 407         // Lock thread list
 408         SHORTLOCK( &glThreadListLock );
 409
 410         // Get previous thread on list
 411         prev = Threads_int_GetPrev( &gActiveThreads, Thread );
 412         if(!prev) {
 413                 Warning("Proc_Exit - Current thread is not on the active queue");
 414                 SHORTREL( &glThreadListLock );
 415                 SHORTREL( &Thread->IsLocked );
 416                 return;
 417         }
 418
 419         // Clear Message Queue
 420         while( Thread->Messages )
 421         {
 422                 msg = Thread->Messages->Next;
 423                 free( Thread->Messages );
 424                 Thread->Messages = msg;
 425         }
 426
 427         Thread->Remaining = 0;  // Clear Remaining Quantum
 428         Thread->Quantum = 0;    // Clear Quantum to indicate dead thread
 429         prev->Next = Thread->Next;      // Remove from active
 430
 431         giNumActiveThreads --;
 432         if( Thread != Proc_GetCurThread() )
 433                 giFreeTickets -= Thread->NumTickets;
 434
 435         // Save exit status
 436         Thread->RetStatus = Status;
 437
 438         // Don't Zombie if we are being killed as part of a tree
 439         if(Status == -1)
 440         {
 441                 Thread->Status = THREAD_STAT_DEAD;
 442                 Threads_AddToDelete( Thread );
 443         } else {
 444                 Thread->Status = THREAD_STAT_ZOMBIE;
 445                 // Wake parent
 446                 Threads_Wake( Thread->Parent );
 447         }
 448
 449         Log("Thread %i went *hurk* (%i)", Thread->TID, Thread->Status);
 450
 451         // Release spinlocks
 452         SHORTREL( &Thread->IsLocked );
 453         SHORTREL( &glThreadListLock );
 454
 455         if(Status != -1)        HALT();
 456 }
 457
 458 /**
 459  * \fn void Threads_Yield(void)
 460  * \brief Yield remainder of timeslice
 461  */
 462 void Threads_Yield(void)
 463 {
 464         Proc_GetCurThread()->Remaining = 0;
 465         HALT();
 466 }
 467
 468 /**
 469  * \fn void Threads_Sleep(void)
 470  * \brief Take the current process off the run queue
 471  */
 472 void Threads_Sleep(void)
 473 {
 474         tThread *cur = Proc_GetCurThread();
 475
 476         //Log_Log("Threads", "%i going to sleep", cur->TID);
 477
 478         // Acquire Spinlock
 479         SHORTLOCK( &glThreadListLock );
 480
 481         // Don't sleep if there is a message waiting
 482         if( cur->Messages ) {
 483                 SHORTREL( &glThreadListLock );
 484                 return;
 485         }
 486
 487         // Remove us from running queue
 488         Threads_RemActive();
 489
 490         // Add to Sleeping List (at the top)
 491         cur->Next = gSleepingThreads;
 492         gSleepingThreads = cur;
 493
 494         // Mark thread as sleeping
 495         cur->Status = THREAD_STAT_SLEEPING;
 496
 497         #if DEBUG_TRACE_STATE
 498         Log("Threads_Sleep: %p (%i %s) sleeping", cur, cur->TID, cur->ThreadName);
 499         #endif
 500
 501         // Release Spinlock
 502         SHORTREL( &glThreadListLock );
 503
 504         while(cur->Status != THREAD_STAT_ACTIVE)        HALT();
 505 }
 506
 507
 508 /**
 509  * \fn int Threads_Wake( tThread *Thread )
 510  * \brief Wakes a sleeping/waiting thread up
 511  * \param Thread        Thread to wake
 512  * \return Boolean Failure (Returns ERRNO)
 513  * \warning This should ONLY be called with task switches disabled
 514  */
 515 int Threads_Wake(tThread *Thread)
 516 {
 517         tThread *prev;
 518
 519         if(!Thread)
 520                 return -EINVAL;
 521
 522         switch(Thread->Status)
 523         {
 524         case THREAD_STAT_ACTIVE:
 525                 Log("Thread_Wake: Waking awake thread (%i)", Thread->TID);
 526                 return -EALREADY;
 527
 528         case THREAD_STAT_SLEEPING:
 529                 // Remove from sleeping queue
 530                 prev = Threads_int_GetPrev(&gSleepingThreads, Thread);
 531                 prev->Next = Thread->Next;
 532
 533                 // Add to active queue
 534                 Thread->Next = gActiveThreads;
 535                 gActiveThreads = Thread;
 536
 537                 // Update bookkeeping
 538                 giNumActiveThreads ++;
 539                 giFreeTickets += Thread->NumTickets;
 540                 #if DEBUG_TRACE_TICKETS
 541                 Log("Threads_Wake: new giFreeTickets = %i", giFreeTickets);
 542                 #endif
 543
 544                 Thread->CurCPU = -1;
 545                 Thread->Status = THREAD_STAT_ACTIVE;
 546                 #if DEBUG_TRACE_STATE
 547                 Log("Threads_Sleep: %p (%i %s) woken", Thread, Thread->TID, Thread->ThreadName);
 548                 #endif
 549                 return -EOK;
 550
 551         case THREAD_STAT_WAITING:
 552                 Warning("Thread_Wake - Waiting threads are not currently supported");
 553                 return -ENOTIMPL;
 554
 555         case THREAD_STAT_DEAD:
 556                 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
 557                 return -ENOTIMPL;
 558
 559         default:
 560                 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
 561                 return -EINTERNAL;
 562         }
 563 }
 564
 565 /**
 566  * \brief Wake a thread given the TID
 567  * \param TID   Thread ID to wake
 568  * \return Boolean Faulure (errno)
 569  */
 570 int Threads_WakeTID(tTID TID)
 571 {
 572         tThread *thread = Threads_GetThread(TID);
 573          int    ret;
 574         if(!thread)
 575                 return -ENOENT;
 576         SHORTLOCK( &glThreadListLock );
 577         ret = Threads_Wake( thread );
 578         SHORTREL( &glThreadListLock );
 579         //Log_Debug("Threads", "TID %i woke %i (%p)", Threads_GetTID(), TID, thread);
 580         return ret;
 581 }
 582
 583 /**
 584  * \fn void Threads_AddActive(tThread *Thread)
 585  * \brief Adds a thread to the active queue
 586  */
 587 void Threads_AddActive(tThread *Thread)
 588 {
 589         SHORTLOCK( &glThreadListLock );
 590         // Add to active list
 591         Thread->Next = gActiveThreads;
 592         gActiveThreads = Thread;
 593         // Update bookkeeping
 594         giNumActiveThreads ++;
 595         giFreeTickets += Thread->NumTickets;
 596         #if DEBUG_TRACE_TICKETS
 597         Log("Threads_AddActive: new giFreeTickets = %i", giFreeTickets);
 598         #endif
 599         SHORTREL( &glThreadListLock );
 600 }
 601
 602 /**
 603  * \brief Removes the current thread from the active queue
 604  * \warning This should ONLY be called with task switches disabled
 605  * \return Current thread pointer
 606  */
 607 tThread *Threads_RemActive(void)
 608 {
 609         tThread *ret = Proc_GetCurThread();
 610         tThread *prev = Threads_int_GetPrev(&gActiveThreads, ret);
 611         if(!prev)       return NULL;
 612         ret->Remaining = 0;
 613         ret->CurCPU = -1;
 614         prev->Next = ret->Next;
 615         giNumActiveThreads --;
 616         return ret;
 617 }
 618
 619 /**
 620  * \fn void Threads_SetFaultHandler(Uint Handler)
 621  * \brief Sets the signal handler for a signal
 622  */
 623 void Threads_SetFaultHandler(Uint Handler)
 624 {
 625         //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
 626         Proc_GetCurThread()->FaultHandler = Handler;
 627 }
 628
 629 /**
 630  * \fn void Threads_Fault(int Num)
 631  * \brief Calls a fault handler
 632  */
 633 void Threads_Fault(int Num)
 634 {
 635         tThread *thread = Proc_GetCurThread();
 636
 637         Log_Log("Threads", "Threads_Fault: thread = %p", thread);
 638
 639         if(!thread)     return ;
 640
 641         Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
 642
 643         switch(thread->FaultHandler)
 644         {
 645         case 0: // Panic?
 646                 Threads_Kill(thread, -1);
 647                 HALT();
 648                 return ;
 649         case 1: // Dump Core?
 650                 Threads_Kill(thread, -1);
 651                 HALT();
 652                 return ;
 653         }
 654
 655         // Double Fault? Oh, F**k
 656         if(thread->CurFaultNum != 0) {
 657                 Threads_Kill(thread, -1);       // For now, just kill
 658                 HALT();
 659         }
 660
 661         thread->CurFaultNum = Num;
 662
 663         Proc_CallFaultHandler(thread);
 664 }
 665
 666 // --- Process Structure Access Functions ---
 667 tPID Threads_GetPID(void)
 668 {
 669         return Proc_GetCurThread()->TGID;
 670 }
 671 tTID Threads_GetTID(void)
 672 {
 673         return Proc_GetCurThread()->TID;
 674 }
 675 tUID Threads_GetUID(void)
 676 {
 677         return Proc_GetCurThread()->UID;
 678 }
 679 tGID Threads_GetGID(void)
 680 {
 681         return Proc_GetCurThread()->GID;
 682 }
 683
 684 int Threads_SetUID(Uint *Errno, tUID ID)
 685 {
 686         tThread *t = Proc_GetCurThread();
 687         if( t->UID != 0 ) {
 688                 *Errno = -EACCES;
 689                 return -1;
 690         }
 691         Log_Debug("Threads", "TID %i's UID set to %i", t->TID, ID);
 692         t->UID = ID;
 693         return 0;
 694 }
 695
 696 int Threads_SetGID(Uint *Errno, tGID ID)
 697 {
 698         tThread *t = Proc_GetCurThread();
 699         if( t->UID != 0 ) {
 700                 *Errno = -EACCES;
 701                 return -1;
 702         }
 703         Log_Debug("Threads", "TID %i's GID set to %i", t->TID, ID);
 704         t->GID = ID;
 705         return 0;
 706 }
 707
 708 /**
 709  * \fn void Threads_Dump(void)
 710  * \brief Dums a list of currently running threads
 711  */
 712 void Threads_Dump(void)
 713 {
 714         tThread *thread;
 715
 716         Log("Active Threads:");
 717         for(thread=gActiveThreads;thread;thread=thread->Next)
 718         {
 719                 Log(" %i (%i) - %s (CPU %i)",
 720                         thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 721                 if(thread->Status != THREAD_STAT_ACTIVE)
 722                         Log("  ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE);
 723                 Log("  %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
 724                 Log("  KStack 0x%x", thread->KernelStack);
 725         }
 726
 727         Log("All Threads:");
 728         for(thread=gAllThreads;thread;thread=thread->GlobalNext)
 729         {
 730                 Log(" %i (%i) - %s (CPU %i)",
 731                         thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 732                 Log("  State %i", thread->Status);
 733                 Log("  %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
 734                 Log("  KStack 0x%x", thread->KernelStack);
 735         }
 736 }
 737
 738 /**
 739  * \fn tThread *Threads_GetNextToRun(int CPU, tThread *Last)
 740  * \brief Gets the next thread to run
 741  * \param CPU   Current CPU
 742  * \param Last  The thread the CPU was running
 743  */
 744 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
 745 {
 746         tThread *thread;
 747          int    ticket;
 748          int    number;
 749
 750         // Lock thread list
 751         SHORTLOCK( &glThreadListLock );
 752
 753         // Clear Delete Queue
 754         // - I should probably put this in a worker thread to avoid calling free() in the scheduler
 755         while(gDeleteThreads)
 756         {
 757                 thread = gDeleteThreads->Next;
 758                 if( IS_LOCKED(&gDeleteThreads->IsLocked) ) {    // Only free if structure is unused
 759                         // Set to dead
 760                         gDeleteThreads->Status = THREAD_STAT_DEAD;
 761                         // Free name
 762                         if( IsHeap(gDeleteThreads->ThreadName) )
 763                                 free(gDeleteThreads->ThreadName);
 764                         // Remove from global list
 765                         if( gDeleteThreads == gAllThreads )
 766                                 gAllThreads = gDeleteThreads->GlobalNext;
 767                         else
 768                                 gDeleteThreads->GlobalPrev->GlobalNext = gDeleteThreads->GlobalNext;
 769                         free( gDeleteThreads );
 770                 }
 771                 gDeleteThreads = thread;
 772         }
 773
 774         // No active threads, just take a nap
 775         if(giNumActiveThreads == 0) {
 776                 SHORTREL( &glThreadListLock );
 777                 #if DEBUG_TRACE_TICKETS
 778                 Log("No active threads");
 779                 #endif
 780                 return NULL;
 781         }
 782
 783         // Special case: 1 thread
 784         if(giNumActiveThreads == 1) {
 785                 if( gActiveThreads->CurCPU == -1 )
 786                         gActiveThreads->CurCPU = CPU;
 787                 SHORTREL( &glThreadListLock );
 788                 if( gActiveThreads->CurCPU == CPU )
 789                         return gActiveThreads;
 790                 return NULL;    // CPU has nothing to do
 791         }
 792
 793         // Allow the old thread to be scheduled again
 794         if( Last ) {
 795                 if( Last->Status == THREAD_STAT_ACTIVE ) {
 796                         giFreeTickets += Last->NumTickets;
 797                         #if DEBUG_TRACE_TICKETS
 798                         LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n",
 799                                 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets);
 800                         #endif
 801                 }
 802                 #if DEBUG_TRACE_TICKETS
 803                 else
 804                         LogF(" %p (%s)->Status = %i (Released)\n", Last, Last->ThreadName, Last->Status);
 805                 #endif
 806                 Last->CurCPU = -1;
 807         }
 808
 809         #if 1
 810         number = 0;
 811         for(thread = gActiveThreads; thread; thread = thread->Next) {
 812                 if(thread->CurCPU >= 0) continue;
 813                 number += thread->NumTickets;
 814         }
 815         if(number != giFreeTickets) {
 816                 Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
 817                         giFreeTickets, number, CPU);
 818         }
 819         #endif
 820
 821         // No free tickets (all tasks delegated to cores)
 822         if( giFreeTickets == 0 ) {
 823                 SHORTREL(&glThreadListLock);
 824                 return NULL;
 825         }
 826
 827         // Get the ticket number
 828         ticket = number = rand() % giFreeTickets;
 829
 830         // Find the next thread
 831         for(thread=gActiveThreads;thread;thread=thread->Next)
 832         {
 833                 if(thread->CurCPU >= 0) continue;
 834                 if(thread->NumTickets > number) break;
 835                 number -= thread->NumTickets;
 836         }
 837         // Error Check
 838         if(thread == NULL)
 839         {
 840                 number = 0;
 841                 for(thread=gActiveThreads;thread;thread=thread->Next) {
 842                         if(thread->CurCPU >= 0) continue;
 843                         number += thread->NumTickets;
 844                 }
 845                 Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
 846                         giFreeTickets, number);
 847         }
 848         #if DEBUG_TRACE_TICKETS
 849         LogF(" CPU%i giFreeTickets = %i\n", CPU, giFreeTickets);
 850         #endif
 851
 852         // Make the new thread non-schedulable
 853         giFreeTickets -= thread->NumTickets;
 854         thread->CurCPU = CPU;
 855
 856         //Threads_Dump();
 857         #if DEBUG_TRACE_TICKETS
 858         LogF(" CPU%i giFreeTickets = %i, giving %p (%i %s CPU=%i)\n",
 859                 CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU);
 860         #endif
 861
 862         SHORTREL( &glThreadListLock );
 863
 864         return thread;
 865 }
 866
 867 /**
 868  * \fn void Threads_SegFault(tVAddr Addr)
 869  * \brief Called when a Segment Fault occurs
 870  */
 871 void Threads_SegFault(tVAddr Addr)
 872 {
 873         Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr);
 874         Threads_Fault( 1 );
 875         //Threads_Exit( 0, -1 );
 876 }
 877
 878 /**
 879  * \brief Acquire a heavy mutex
 880  * \param Mutex Mutex to acquire
 881  *
 882  * This type of mutex checks if the mutex is avaliable, and acquires it
 883  * if it is. Otherwise, the current thread is added to the mutex's wait
 884  * queue and the thread suspends. When the holder of the mutex completes,
 885  * the oldest thread (top thread) on the queue is given the lock and
 886  * restarted.
 887  */
 888 void Mutex_Acquire(tMutex *Mutex)
 889 {
 890         tThread *us = Proc_GetCurThread();
 891
 892         // Get protector
 893         SHORTLOCK( &Mutex->Protector );
 894
 895         //Log("Mutex_Acquire: (%p)", Mutex);
 896
 897         // Check if the lock is already held
 898         if( Mutex->Owner ) {
 899                 SHORTLOCK( &glThreadListLock );
 900                 // - Remove from active list
 901                 Threads_RemActive();
 902                 // - Mark as sleeping
 903                 us->Status = THREAD_STAT_OFFSLEEP;
 904
 905                 // - Add to waiting
 906                 if(Mutex->LastWaiting) {
 907                         Mutex->LastWaiting->Next = us;
 908                         Mutex->LastWaiting = us;
 909                 }
 910                 else {
 911                         Mutex->Waiting = us;
 912                         Mutex->LastWaiting = us;
 913                 }
 914                 SHORTREL( &glThreadListLock );
 915                 SHORTREL( &Mutex->Protector );
 916                 while(us->Status == THREAD_STAT_OFFSLEEP)       Threads_Yield();
 917                 // We're only woken when we get the lock
 918         }
 919         // Ooh, let's take it!
 920         else {
 921                 Mutex->Owner = us;
 922                 SHORTREL( &Mutex->Protector );
 923         }
 924 }
 925
 926 /**
 927  * \brief Release a held mutex
 928  * \param Mutex Mutex to release
 929  */
 930 void Mutex_Release(tMutex *Mutex)
 931 {
 932         SHORTLOCK( &Mutex->Protector );
 933         //Log("Mutex_Release: (%p)", Mutex);
 934         if( Mutex->Waiting ) {
 935                 Mutex->Owner = Mutex->Waiting;  // Set owner
 936                 Mutex->Waiting = Mutex->Waiting->Next;  // Next!
 937                 // Wake new owner
 938                 Mutex->Owner->Status = THREAD_STAT_ACTIVE;
 939                 Threads_AddActive(Mutex->Owner);
 940                 //Log("Mutex %p Woke %p", Mutex, Mutex->Owner);
 941         }
 942         else {
 943                 Mutex->Owner = NULL;
 944         }
 945         SHORTREL( &Mutex->Protector );
 946 }
 947
 948 /**
 949  * \brief Is this mutex locked?
 950  * \param Mutex Mutex pointer
 951  */
 952 int Mutex_IsLocked(tMutex *Mutex)
 953 {
 954         return Mutex->Owner != NULL;
 955 }
 956
 957 // === EXPORTS ===
 958 EXPORT(Threads_GetUID);
 959 EXPORT(Mutex_Acquire);
 960 EXPORT(Mutex_Release);
 961 EXPORT(Mutex_IsLocked);