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