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