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