Kernel/threads.c

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