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