Kernel/threads.c

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