Kernel/threads.c

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