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