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->Remaining = 0;
 714         ret->CurCPU = -1;
 715
 716         giNumActiveThreads --;
 717         // no need to decrement tickets, scheduler did it for us
 718
 719         #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
 720         Log("Threads_RemActive: %p %i (%s) removed, giFreeTickets = %i",
 721                 ret, ret->TID, ret->ThreadName, giFreeTickets);
 722         #endif
 723
 724         SHORTREL( &glThreadListLock );
 725
 726         return ret;
 727 }
 728
 729 /**
 730  * \fn void Threads_SetFaultHandler(Uint Handler)
 731  * \brief Sets the signal handler for a signal
 732  */
 733 void Threads_SetFaultHandler(Uint Handler)
 734 {
 735         //Log_Debug("Threads", "Threads_SetFaultHandler: Handler = %p", Handler);
 736         Proc_GetCurThread()->FaultHandler = Handler;
 737 }
 738
 739 /**
 740  * \fn void Threads_Fault(int Num)
 741  * \brief Calls a fault handler
 742  */
 743 void Threads_Fault(int Num)
 744 {
 745         tThread *thread = Proc_GetCurThread();
 746
 747         Log_Log("Threads", "Threads_Fault: thread = %p", thread);
 748
 749         if(!thread)     return ;
 750
 751         Log_Log("Threads", "Threads_Fault: thread->FaultHandler = %p", thread->FaultHandler);
 752
 753         switch(thread->FaultHandler)
 754         {
 755         case 0: // Panic?
 756                 Threads_Kill(thread, -1);
 757                 HALT();
 758                 return ;
 759         case 1: // Dump Core?
 760                 Threads_Kill(thread, -1);
 761                 HALT();
 762                 return ;
 763         }
 764
 765         // Double Fault? Oh, F**k
 766         if(thread->CurFaultNum != 0) {
 767                 Threads_Kill(thread, -1);       // For now, just kill
 768                 HALT();
 769         }
 770
 771         thread->CurFaultNum = Num;
 772
 773         Proc_CallFaultHandler(thread);
 774 }
 775
 776 // --- Process Structure Access Functions ---
 777 tPID Threads_GetPID(void)
 778 {
 779         return Proc_GetCurThread()->TGID;
 780 }
 781 tTID Threads_GetTID(void)
 782 {
 783         return Proc_GetCurThread()->TID;
 784 }
 785 tUID Threads_GetUID(void)
 786 {
 787         return Proc_GetCurThread()->UID;
 788 }
 789 tGID Threads_GetGID(void)
 790 {
 791         return Proc_GetCurThread()->GID;
 792 }
 793
 794 int Threads_SetUID(Uint *Errno, tUID ID)
 795 {
 796         tThread *t = Proc_GetCurThread();
 797         if( t->UID != 0 ) {
 798                 *Errno = -EACCES;
 799                 return -1;
 800         }
 801         Log_Debug("Threads", "TID %i's UID set to %i", t->TID, ID);
 802         t->UID = ID;
 803         return 0;
 804 }
 805
 806 int Threads_SetGID(Uint *Errno, tGID ID)
 807 {
 808         tThread *t = Proc_GetCurThread();
 809         if( t->UID != 0 ) {
 810                 *Errno = -EACCES;
 811                 return -1;
 812         }
 813         Log_Debug("Threads", "TID %i's GID set to %i", t->TID, ID);
 814         t->GID = ID;
 815         return 0;
 816 }
 817
 818 /**
 819  * \fn void Threads_Dump(void)
 820  */
 821 void Threads_DumpActive(void)
 822 {
 823         tThread *thread;
 824         #if SCHEDULER_TYPE == SCHED_RR_PRI
 825          int    i;
 826         #endif
 827
 828         Log("Active Threads: (%i reported)", giNumActiveThreads);
 829
 830         #if SCHEDULER_TYPE == SCHED_RR_PRI
 831         for( i = 0; i < MIN_PRIORITY+1; i++ )
 832         {
 833                 for(thread=gaActiveThreads[i];thread;thread=thread->Next)
 834         #else
 835                 for(thread=gActiveThreads;thread;thread=thread->Next)
 836         #endif
 837                 {
 838                         Log(" %i (%i) - %s (CPU %i)",
 839                                 thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 840                         if(thread->Status != THREAD_STAT_ACTIVE)
 841                                 Log("  ERROR State (%i) != THREAD_STAT_ACTIVE (%i)", thread->Status, THREAD_STAT_ACTIVE);
 842                         Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
 843                         Log("  KStack 0x%x", thread->KernelStack);
 844                 }
 845
 846         #if SCHEDULER_TYPE == SCHED_RR_PRI
 847         }
 848         #endif
 849 }
 850
 851 /**
 852  * \fn void Threads_Dump(void)
 853  * \brief Dumps a list of currently running threads
 854  */
 855 void Threads_Dump(void)
 856 {
 857         tThread *thread;
 858
 859         Log("--- Thread Dump ---");
 860         Threads_DumpActive();
 861
 862         Log("All Threads:");
 863         for(thread=gAllThreads;thread;thread=thread->GlobalNext)
 864         {
 865                 Log(" %i (%i) - %s (CPU %i)",
 866                         thread->TID, thread->TGID, thread->ThreadName, thread->CurCPU);
 867                 Log("  State %i", thread->Status);
 868                 Log("  Priority %i, Quantum %i", thread->Priority, thread->Quantum);
 869                 Log("  KStack 0x%x", thread->KernelStack);
 870         }
 871 }
 872
 873 /**
 874  * \brief Gets the next thread to run
 875  * \param CPU   Current CPU
 876  * \param Last  The thread the CPU was running
 877  */
 878 tThread *Threads_GetNextToRun(int CPU, tThread *Last)
 879 {
 880         tThread *thread;
 881
 882         // If this CPU has the lock, we must let it complete
 883         if( CPU_HAS_LOCK( &glThreadListLock ) )
 884                 return Last;
 885
 886         // Don't change threads if the current CPU has switches disabled
 887         if( gaThreads_NoTaskSwitch[CPU] )
 888                 return Last;
 889
 890
 891         // Lock thread list
 892         SHORTLOCK( &glThreadListLock );
 893
 894         // Clear Delete Queue
 895         // - I should probably put this in a worker thread to avoid calling free() in the scheduler
 896         while(gDeleteThreads)
 897         {
 898                 thread = gDeleteThreads->Next;
 899                 if( IS_LOCKED(&gDeleteThreads->IsLocked) ) {    // Only free if structure is unused
 900                         // Set to dead
 901                         gDeleteThreads->Status = THREAD_STAT_DEAD;
 902                         // Free name
 903                         if( IsHeap(gDeleteThreads->ThreadName) )
 904                                 free(gDeleteThreads->ThreadName);
 905                         // Remove from global list
 906                         if( gDeleteThreads == gAllThreads )
 907                                 gAllThreads = gDeleteThreads->GlobalNext;
 908                         else
 909                                 gDeleteThreads->GlobalPrev->GlobalNext = gDeleteThreads->GlobalNext;
 910                         free( gDeleteThreads );
 911                 }
 912                 gDeleteThreads = thread;
 913         }
 914
 915         // No active threads, just take a nap
 916         if(giNumActiveThreads == 0) {
 917                 SHORTREL( &glThreadListLock );
 918                 #if DEBUG_TRACE_TICKETS
 919                 Log("No active threads");
 920                 #endif
 921                 return NULL;
 922         }
 923
 924         #if SCHEDULER_TYPE != SCHED_RR_PRI
 925         // Special case: 1 thread
 926         if(giNumActiveThreads == 1) {
 927                 if( gActiveThreads->CurCPU == -1 )
 928                         gActiveThreads->CurCPU = CPU;
 929
 930                 SHORTREL( &glThreadListLock );
 931
 932                 if( gActiveThreads->CurCPU == CPU )
 933                         return gActiveThreads;
 934
 935                 return NULL;    // CPU has nothing to do
 936         }
 937         #endif
 938
 939         // Allow the old thread to be scheduled again
 940         if( Last ) {
 941                 if( Last->Status == THREAD_STAT_ACTIVE ) {
 942                         #if SCHEDULER_TYPE == SCHED_LOTTERY
 943                         giFreeTickets += caiTICKET_COUNTS[ Last->Priority ];
 944                         # if DEBUG_TRACE_TICKETS
 945                         LogF(" CPU %i released %p (%i %s) into the pool (%i tickets in pool)\n",
 946                                 CPU, Last, Last->TID, Last->ThreadName, giFreeTickets);
 947                         # endif
 948                         #endif
 949                 }
 950                 #if SCHEDULER_TYPE == SCHED_LOTTERY && DEBUG_TRACE_TICKETS
 951                 else
 952                         LogF(" CPU %i released %p (%i %s)->Status = %i (Released)\n",
 953                                 CPU, Last, Last->TID, Last->ThreadName, Last->Status);
 954                 #endif
 955                 Last->CurCPU = -1;
 956         }
 957
 958         // ---
 959         // Lottery Scheduler
 960         // ---
 961         #if SCHEDULER_TYPE == SCHED_LOTTERY
 962         {
 963                  int    ticket, number;
 964                 # if 1
 965                 number = 0;
 966                 for(thread = gActiveThreads; thread; thread = thread->Next) {
 967                         if(thread->CurCPU >= 0) continue;
 968                         if(thread->Status != THREAD_STAT_ACTIVE)
 969                                 Panic("Bookkeeping fail - %p %i(%s) is on the active queue with a status of %i",
 970                                         thread, thread->TID, thread->ThreadName, thread->Status);
 971                         if(thread->Next == thread) {
 972                                 Panic("Bookkeeping fail - %p %i(%s) loops back on itself",
 973                                         thread, thread->TID, thread->ThreadName, thread->Status);
 974                         }
 975                         number += caiTICKET_COUNTS[ thread->Priority ];
 976                 }
 977                 if(number != giFreeTickets) {
 978                         Panic("Bookkeeping fail (giFreeTickets(%i) != number(%i)) - CPU%i",
 979                                 giFreeTickets, number, CPU);
 980                 }
 981                 # endif
 982
 983                 // No free tickets (all tasks delegated to cores)
 984                 if( giFreeTickets == 0 ) {
 985                         SHORTREL(&glThreadListLock);
 986                         return NULL;
 987                 }
 988
 989                 // Get the ticket number
 990                 ticket = number = rand() % giFreeTickets;
 991
 992                 // Find the next thread
 993                 for(thread=gActiveThreads;thread;thread=thread->Next)
 994                 {
 995                         if(thread->CurCPU >= 0) continue;
 996                         if( caiTICKET_COUNTS[ thread->Priority ] > number)      break;
 997                         number -= caiTICKET_COUNTS[ thread->Priority ];
 998                 }
 999
1000                 // If we didn't find a thread, something went wrong
1001                 if(thread == NULL)
1002                 {
1003                         number = 0;
1004                         for(thread=gActiveThreads;thread;thread=thread->Next) {
1005                                 if(thread->CurCPU >= 0) continue;
1006                                 number += caiTICKET_COUNTS[ thread->Priority ];
1007                         }
1008                         Panic("Bookeeping Failed - giFreeTickets(%i) > true count (%i)",
1009                                 giFreeTickets, number);
1010                 }
1011                 # if DEBUG_TRACE_TICKETS
1012                 LogF(" CPU%i giFreeTickets = %i, running %p (%i %s CPU=%i)\n",
1013                         CPU, giFreeTickets, thread, thread->TID, thread->ThreadName, thread->CurCPU);
1014                 # endif
1015
1016                 giFreeTickets -= caiTICKET_COUNTS[ thread->Priority ];
1017         }
1018
1019         // ---
1020         // Priority based round robin scheduler
1021         // ---
1022         #elif SCHEDULER_TYPE == SCHED_RR_PRI
1023         {
1024                  int    i;
1025                 for( i = 0; i < MIN_PRIORITY + 1; i ++ )
1026                 {
1027                         for(thread = gaActiveThreads[i]; thread; thread = thread->Next)
1028                         {
1029                                 if( thread->CurCPU == -1 )      break;
1030                         }
1031                         // If we fall onto the same queue again, special handling is
1032                         // needed
1033                         if( i == Last->Priority ) {
1034                                 tThread *savedThread = thread;
1035
1036                                 // Find the next unscheduled thread in the list
1037                                 for( thread = Last->Next; thread; thread = thread->Next )
1038                                 {
1039                                         if( thread->CurCPU == -1 )      break;
1040                                 }
1041                                 // If we don't find anything after, just use the one
1042                                 // found above.
1043                                 if( !thread )   thread = savedThread;
1044                         }
1045                         // Found a thread? Schedule it!
1046                         if( thread )    break;
1047                 }
1048
1049                 // Anything to do?
1050                 if( !thread ) {
1051                         SHORTREL(&glThreadListLock);
1052                         return NULL;
1053                 }
1054         }
1055         #elif SCHEDULER_TYPE == SCHED_RR_SIM
1056         {
1057                 // Find the next unscheduled thread in the list
1058                 for( thread = Last->Next; thread; thread = thread->Next )
1059                 {
1060                         if( thread->CurCPU == -1 )      break;
1061                 }
1062                 // If we don't find anything after, search from the beginning
1063                 if( !thread )
1064                 {
1065                         for(thread = gActiveThreads; thread; thread = thread->Next)
1066                         {
1067                                 if( thread->CurCPU == -1 )      break;
1068                         }
1069                 }
1070
1071                 // Anything to do?
1072                 if( !thread ) {
1073                         SHORTREL(&glThreadListLock);
1074                         return NULL;
1075                 }
1076         }
1077         #else
1078         # error "Unimplemented scheduling algorithm"
1079         #endif
1080
1081         // Make the new thread non-schedulable
1082         thread->CurCPU = CPU;
1083
1084         SHORTREL( &glThreadListLock );
1085
1086         return thread;
1087 }
1088
1089 /**
1090  * \fn void Threads_SegFault(tVAddr Addr)
1091  * \brief Called when a Segment Fault occurs
1092  */
1093 void Threads_SegFault(tVAddr Addr)
1094 {
1095         Warning("Thread #%i committed a segfault at address %p", Proc_GetCurThread()->TID, Addr);
1096         Threads_Fault( 1 );
1097         //Threads_Exit( 0, -1 );
1098 }
1099
1100 /**
1101  * \brief Acquire a heavy mutex
1102  * \param Mutex Mutex to acquire
1103  *
1104  * This type of mutex checks if the mutex is avaliable, and acquires it
1105  * if it is. Otherwise, the current thread is added to the mutex's wait
1106  * queue and the thread suspends. When the holder of the mutex completes,
1107  * the oldest thread (top thread) on the queue is given the lock and
1108  * restarted.
1109  */
1110 void Mutex_Acquire(tMutex *Mutex)
1111 {
1112         tThread *us = Proc_GetCurThread();
1113
1114         // Get protector
1115         SHORTLOCK( &Mutex->Protector );
1116
1117         //Log("Mutex_Acquire: (%p)", Mutex);
1118
1119         // Check if the lock is already held
1120         if( Mutex->Owner ) {
1121                 SHORTLOCK( &glThreadListLock );
1122                 // - Remove from active list
1123                 us = Threads_RemActive();
1124                 // - Mark as sleeping
1125                 us->Status = THREAD_STAT_OFFSLEEP;
1126
1127                 // - Add to waiting
1128                 if(Mutex->LastWaiting) {
1129                         Mutex->LastWaiting->Next = us;
1130                         Mutex->LastWaiting = us;
1131                 }
1132                 else {
1133                         Mutex->Waiting = us;
1134                         Mutex->LastWaiting = us;
1135                 }
1136                 SHORTREL( &glThreadListLock );
1137                 SHORTREL( &Mutex->Protector );
1138                 while(us->Status == THREAD_STAT_OFFSLEEP)       Threads_Yield();
1139                 // We're only woken when we get the lock
1140         }
1141         // Ooh, let's take it!
1142         else {
1143                 Mutex->Owner = us;
1144                 SHORTREL( &Mutex->Protector );
1145         }
1146 }
1147
1148 /**
1149  * \brief Release a held mutex
1150  * \param Mutex Mutex to release
1151  */
1152 void Mutex_Release(tMutex *Mutex)
1153 {
1154         SHORTLOCK( &Mutex->Protector );
1155         //Log("Mutex_Release: (%p)", Mutex);
1156         if( Mutex->Waiting ) {
1157                 Mutex->Owner = Mutex->Waiting;  // Set owner
1158                 Mutex->Waiting = Mutex->Waiting->Next;  // Next!
1159                 // Reset ->LastWaiting to NULL if we have just removed the last waiting thread
1160                 // 2010-10-02 21:50 - Comemerating the death of the longest single
1161                 //                    blocker in the Acess2 history. REMEMBER TO
1162                 //                    FUCKING MAINTAIN YOUR FUCKING LISTS DIPWIT
1163                 if( Mutex->LastWaiting == Mutex->Owner )
1164                         Mutex->LastWaiting = NULL;
1165
1166                 // Wake new owner
1167                 SHORTLOCK( &glThreadListLock );
1168                 if( Mutex->Owner->Status != THREAD_STAT_ACTIVE )
1169                         Threads_AddActive(Mutex->Owner);
1170                 SHORTREL( &glThreadListLock );
1171         }
1172         else {
1173                 Mutex->Owner = NULL;
1174         }
1175         SHORTREL( &Mutex->Protector );
1176 }
1177
1178 /**
1179  * \brief Is this mutex locked?
1180  * \param Mutex Mutex pointer
1181  */
1182 int Mutex_IsLocked(tMutex *Mutex)
1183 {
1184         return Mutex->Owner != NULL;
1185 }
1186
1187 // === EXPORTS ===
1188 EXPORT(Threads_GetUID);
1189 EXPORT(Threads_GetGID);
1190 EXPORT(Mutex_Acquire);
1191 EXPORT(Mutex_Release);
1192 EXPORT(Mutex_IsLocked);