Kernel/arch/x86/proc.c

   1 /*
   2  * AcessOS Microkernel Version
   3  * proc.c
   4  */
   5 #include <common.h>
   6 #include <proc.h>
   7 #include <mm_virt.h>
   8 #include <errno.h>
   9 #if USE_MP
  10 # include <mp.h>
  11 #endif
  12
  13 // === CONSTANTS ===
  14 #define RANDOM_SEED     0xACE55052
  15 #define SWITCH_MAGIC    0xFFFACE55      // There is no code in this area
  16 #define DEFAULT_QUANTUM 10
  17 #define DEFAULT_TICKETS 5
  18 #define MAX_TICKETS             10
  19 #define TIMER_DIVISOR   11931   //~100Hz
  20
  21 // === IMPORTS ===
  22 extern tGDT     gGDT[];
  23 extern Uint     GetEIP();       // start.asm
  24 extern Uint32   gaInitPageDir[1024];    // start.asm
  25 extern void     Kernel_Stack_Top;
  26
  27 // === PROTOTYPES ===
  28 void    Proc_Start();
  29 void    Proc_ChangeStack();
  30  int    Proc_Clone(Uint *Err, Uint Flags);
  31 void    Proc_Exit();
  32 void    Proc_Yield();
  33 void    Proc_Sleep();
  34 static tThread  *Proc_int_GetPrevThread(tThread **List, tThread *Thread);
  35 void    Proc_Scheduler();
  36 Sint64  now();
  37 Uint    rand();
  38
  39 // === GLOBALS ===
  40 // -- Core Thread --
  41 tThread gThreadZero = {
  42         NULL, 0,        // Next, Lock
  43         THREAD_STAT_ACTIVE,     // Status
  44         0, 0,   // TID, TGID
  45         0, 0,   // UID, GID
  46         "ThreadZero",   // Name
  47         0, 0, 0,        // ESP, EBP, EIP (Set on switch)
  48         #if USE_PAE
  49         {0,0,0},        // PML4 Entries
  50         #else
  51         (Uint)&gaInitPageDir-KERNEL_BASE,       // CR3
  52         #endif
  53         (Uint)&Kernel_Stack_Top,        // Kernel Stack (Unused as it is PL0)
  54         NULL, NULL,     // Messages, Last Message
  55         DEFAULT_QUANTUM, DEFAULT_QUANTUM,       // Quantum, Remaining
  56         DEFAULT_TICKETS,
  57         {0}     // Default config to zero
  58         };
  59 // -- Processes --
  60 // --- Locks ---
  61 volatile int    giThreadListLock = 0;   ///\note NEVER use a heap function while locked
  62 // --- Current State ---
  63 #if USE_MP
  64 tThread **gCurrentThread = NULL;
  65 # define CUR_THREAD     gCurrentThread[0]
  66 #else
  67 tThread *gCurrentThread = NULL;
  68 # define CUR_THREAD     gCurrentThread
  69 #endif
  70 volatile int    giNumActiveThreads = 0;
  71 volatile int    giTotalTickets = 0;
  72 volatile Uint   giNextTID = 1;
  73 // --- Thread Lists ---
  74 tThread *gActiveThreads = NULL;         // Currently Running Threads
  75 tThread *gSleepingThreads = NULL;       // Sleeping Threads
  76 tThread *gDeleteThreads = NULL;         // Threads to delete
  77 // --- Multiprocessing ---
  78  int    giNumCPUs = 1;
  79 #if USE_MP
  80 tMPInfo *gMPTable = NULL;
  81 #endif
  82 #if USE_PAE
  83 Uint32  *gPML4s[4] = NULL;
  84 #endif
  85 tTSS    *gTSSs = NULL;
  86 #if !USE_MP
  87 tTSS    gTSS0 = {0};
  88 #endif
  89
  90 // === CODE ===
  91 /**
  92  * \fn void Proc_Start()
  93  * \brief Starts the process scheduler
  94  */
  95 void Proc_Start()
  96 {
  97         Uint    pos = 0;
  98
  99         #if USE_MP
 100         // -- Initialise Multiprocessing
 101         // Find MP Floating Table
 102         // - EBDA
 103         for(pos = KERNEL_BASE|0x9FC00; pos < (KERNEL_BASE|0xA0000); pos += 16) {
 104                 if( *(Uint*)(pos) == MPTABLE_IDENT ) {
 105                         if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
 106                         gMPTable = (void*)pos;
 107                         break;
 108                 }
 109         }
 110         // - Last KiB
 111         if(!gMPTable) {
 112
 113         }
 114         // - BIOS ROM
 115         if(!gMPTable) {
 116                 for(pos = KERNEL_BASE|0xF0000; pos < (KERNEL_BASE|0x100000); pos += 16) {
 117                         if( *(Uint*)(pos) == MPTABLE_IDENT ) {
 118                                 if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
 119                                 gMPTable = (void*)pos;
 120                                 break;
 121                         }
 122                 }
 123         }
 124
 125         // If the MP Table Exists, parse it
 126         if(gMPTable)
 127         {
 128                 Panic("Uh oh... MP Table Parsing is unimplemented\n");
 129         } else {
 130         #endif
 131                 giNumCPUs = 1;
 132                 gTSSs = &gTSS0;
 133         #if USE_MP
 134         }
 135
 136         // Initialise TSS
 137         for(pos=0;pos<giNumCPUs;pos++)
 138         {
 139         #else
 140         pos = 0;
 141         #endif
 142                 gTSSs[pos].SS0 = 0x10;
 143                 gTSSs[pos].ESP0 = 0;    // Set properly by scheduler
 144                 gGDT[5+pos].LimitLow = sizeof(tTSS);
 145                 gGDT[5+pos].LimitHi = 0;
 146                 gGDT[5+pos].Access = 0x89;      // Type
 147                 gGDT[5+pos].Flags = 0x4;
 148                 gGDT[5+pos].BaseLow = (Uint)&gTSSs[pos] & 0xFFFF;
 149                 gGDT[5+pos].BaseMid = (Uint)&gTSSs[pos] >> 16;
 150                 gGDT[5+pos].BaseHi = (Uint)&gTSSs[pos] >> 24;
 151         #if USE_MP
 152         }
 153         for(pos=0;pos<giNumCPUs;pos++) {
 154         #endif
 155                 __asm__ __volatile__ ("ltr %%ax"::"a"(0x28+pos*8));
 156         #if USE_MP
 157         }
 158         #endif
 159
 160         // Set timer frequency
 161         outb(0x43, 0x34);       // Set Channel 0, Low/High, Rate Generator
 162         outb(0x40, TIMER_DIVISOR&0xFF); // Low Byte of Divisor
 163         outb(0x40, (TIMER_DIVISOR>>8)&0xFF);    // High Byte
 164
 165         // Create Initial Task
 166         gActiveThreads = &gThreadZero;
 167         gCurrentThread = &gThreadZero;
 168         giTotalTickets = gThreadZero.NumTickets;
 169         giNumActiveThreads = 1;
 170
 171         // Create Per-Process Data Block
 172         MM_Allocate(MM_PPD_CFG);
 173
 174         // Change Stacks
 175         Proc_ChangeStack();
 176
 177         #if 1
 178         // Create Idle Task
 179         if(Proc_Clone(0, 0) == 0)
 180         {
 181                 gCurrentThread->ThreadName = "Idle Thread";
 182                 Proc_SetTickets(0);     // Never called randomly
 183                 gCurrentThread->Quantum = 1;    // 1 slice quantum
 184                 for(;;) __asm__ __volatile__ ("hlt");   // Just yeilds
 185         }
 186         #endif
 187
 188         // Start Interrupts (and hence scheduler)
 189         __asm__ __volatile__("sti");
 190 }
 191
 192 /**
 193  * \fn void Proc_ChangeStack()
 194  * \brief Swaps the current stack for a new one (in the proper stack reigon)
 195  */
 196 void Proc_ChangeStack()
 197 {
 198         Uint    esp, ebp;
 199         Uint    tmpEbp, oldEsp;
 200         Uint    curBase, newBase;
 201
 202         __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
 203         __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
 204
 205         oldEsp = esp;
 206
 207         // Create new KStack
 208         newBase = MM_NewKStack();
 209         // Check for errors
 210         if(newBase == 0) {
 211                 Panic("What the?? Unable to allocate space for initial kernel stack");
 212                 return;
 213         }
 214
 215         curBase = gCurrentThread->KernelStack;
 216
 217         LOG("curBase = 0x%x, newBase = 0x%x", curBase, newBase);
 218
 219         // Get ESP as a used size
 220         esp = curBase - esp;
 221         LOG("memcpy( %p, %p, 0x%x )", (void*)(newBase - esp), (void*)(curBase - esp), esp );
 222         // Copy used stack
 223         memcpy( (void*)(newBase - esp), (void*)(curBase - esp), esp );
 224         // Get ESP as an offset in the new stack
 225         esp = newBase - esp;
 226         // Adjust EBP
 227         ebp = newBase - (curBase - ebp);
 228
 229         // Repair EBPs & Stack Addresses
 230         // Catches arguments also, but may trash stack-address-like values
 231         for(tmpEbp = esp; tmpEbp < newBase; tmpEbp += 4)
 232         {
 233                 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < curBase)
 234                         *(Uint*)tmpEbp += newBase - curBase;
 235         }
 236
 237         gCurrentThread->KernelStack = newBase;
 238
 239         __asm__ __volatile__ ("mov %0, %%esp"::"r"(esp));
 240         __asm__ __volatile__ ("mov %0, %%ebp"::"r"(ebp));
 241 }
 242
 243 /**
 244  * \fn int Proc_Clone(Uint *Err, Uint Flags)
 245  * \brief Clone the current process
 246  */
 247 int Proc_Clone(Uint *Err, Uint Flags)
 248 {
 249         tThread *newThread;
 250         Uint    eip, esp, ebp;
 251
 252         __asm__ __volatile__ ("mov %%esp, %0": "=r"(esp));
 253         __asm__ __volatile__ ("mov %%ebp, %0": "=r"(ebp));
 254
 255         // Create new thread structure
 256         newThread = malloc( sizeof(tThread) );
 257         if(!newThread) {
 258                 Warning("Proc_Clone - Out of memory when creating thread\n");
 259                 *Err = -ENOMEM;
 260                 return -1;
 261         }
 262         // Base new thread on old
 263         memcpy(newThread, gCurrentThread, sizeof(tThread));
 264         // Initialise Memory Space (New Addr space or kernel stack)
 265         if(Flags & CLONE_VM) {
 266                 newThread->TGID = newThread->TID;
 267                 newThread->CR3 = MM_Clone();
 268         } else {
 269                 Uint    tmpEbp, oldEsp = esp;
 270
 271                 // Create new KStack
 272                 newThread->KernelStack = MM_NewKStack();
 273                 // Check for errors
 274                 if(newThread->KernelStack == 0) {
 275                         free(newThread);
 276                         return -1;
 277                 }
 278
 279                 // Get ESP as a used size
 280                 esp = gCurrentThread->KernelStack - esp;
 281                 // Copy used stack
 282                 memcpy( (void*)(newThread->KernelStack - esp), (void*)(gCurrentThread->KernelStack - esp), esp );
 283                 // Get ESP as an offset in the new stack
 284                 esp = newThread->KernelStack - esp;
 285                 // Adjust EBP
 286                 ebp = newThread->KernelStack - (gCurrentThread->KernelStack - ebp);
 287
 288                 // Repair EBPs & Stack Addresses
 289                 // Catches arguments also, but may trash stack-address-like values
 290                 for(tmpEbp = esp; tmpEbp < newThread->KernelStack; tmpEbp += 4)
 291                 {
 292                         if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < gCurrentThread->KernelStack)
 293                                 *(Uint*)tmpEbp += newThread->KernelStack - gCurrentThread->KernelStack;
 294                 }
 295         }
 296
 297         // Set Pointer, Spinlock and TID
 298         newThread->Next = NULL;
 299         newThread->IsLocked = 0;
 300         newThread->TID = giNextTID++;
 301
 302         // Clear message list (messages are not inherited)
 303         newThread->Messages = NULL;
 304         newThread->LastMessage = NULL;
 305
 306         // Set remaining (sheduler expects remaining to be correct)
 307         newThread->Remaining = newThread->Quantum;
 308
 309         // Save core machine state
 310         newThread->ESP = esp;
 311         newThread->EBP = ebp;
 312         eip = GetEIP();
 313         if(eip == SWITCH_MAGIC) {
 314                 outb(0x20, 0x20);       // ACK Timer and return as child
 315                 return 0;
 316         }
 317
 318         // Set EIP as parent
 319         newThread->EIP = eip;
 320
 321         //Log(" Proc_Clone: giTimestamp = %i.%07i", (Uint)giTimestamp, (Uint)giPartMiliseconds/214);
 322
 323         // Lock list and add to active
 324         LOCK( &giThreadListLock );
 325         newThread->Next = gActiveThreads;
 326         gActiveThreads = newThread;
 327         giNumActiveThreads ++;
 328         giTotalTickets += newThread->NumTickets;
 329         RELEASE( &giThreadListLock );
 330
 331         return newThread->TID;
 332 }
 333
 334 /**
 335  * \fn void Proc_SetThreadName()
 336  * \brief Sets the thread's name
 337  */
 338 void Proc_SetThreadName(char *NewName)
 339 {
 340         if( (Uint)CUR_THREAD->ThreadName > 0xC0400000 )
 341                 free( CUR_THREAD->ThreadName );
 342         CUR_THREAD->ThreadName = malloc(strlen(NewName)+1);
 343         strcpy(CUR_THREAD->ThreadName, NewName);
 344 }
 345
 346 /**
 347  * \fn Uint Proc_MakeUserStack()
 348  */
 349 Uint Proc_MakeUserStack()
 350 {
 351          int    i;
 352         Uint    base = USER_STACK_TOP - USER_STACK_SZ;
 353
 354         // Check Prospective Space
 355         for( i = USER_STACK_SZ >> 12; i--; )
 356                 if( MM_GetPhysAddr( base + (i<<12) ) != 0 )
 357                         break;
 358
 359         if(i != -1)     return 0;
 360
 361         // Allocate Stack - Allocate incrementally to clean up MM_Dump output
 362         for( i = 0; i < USER_STACK_SZ/4069; i++ )
 363                 MM_Allocate( base + (i<<12) );
 364
 365         return base + USER_STACK_SZ;
 366 }
 367
 368
 369 /**
 370  * \fn void Proc_StartUser(Uint Entrypoint, Uint Base, int ArgC, char **ArgV, char **EnvP, int DataSize)
 371  * \brief Starts a user task
 372  */
 373 void Proc_StartUser(Uint Entrypoint, Uint *Bases, int ArgC, char **ArgV, char **EnvP, int DataSize)
 374 {
 375         Uint    *stack = (void*)Proc_MakeUserStack();
 376          int    i;
 377         Uint    delta;
 378         Uint16  ss, cs;
 379
 380         LOG("stack = 0x%x", stack);
 381
 382         // Copy Arguments
 383         stack = (void*)( (Uint)stack - DataSize );
 384         memcpy( stack, ArgV, DataSize );
 385
 386         // Adjust Arguments and environment
 387         delta = (Uint)stack - (Uint)ArgV;
 388         ArgV = (char**)stack;
 389         for( i = 0; ArgV[i]; i++ )      ArgV[i] += delta;
 390         i ++;
 391         EnvP = &ArgV[i];
 392         for( i = 0; EnvP[i]; i++ )      EnvP[i] += delta;
 393
 394         // User Mode Segments
 395         ss = 0x23;      cs = 0x1B;
 396
 397         // Arguments
 398         *--stack = (Uint)EnvP;
 399         *--stack = (Uint)ArgV;
 400         *--stack = (Uint)ArgC;
 401         while(*Bases)
 402                 *--stack = *Bases++;
 403         *--stack = 0;   // Return Address
 404         delta = (Uint)stack;    // Reuse delta to save SP
 405
 406         *--stack = ss;          //Stack Segment
 407         *--stack = delta;       //Stack Pointer
 408         *--stack = 0x0202;      //EFLAGS (Resvd (0x2) and IF (0x20))
 409         *--stack = cs;          //Code Segment
 410         *--stack = Entrypoint;  //EIP
 411         //PUSHAD
 412         *--stack = 0xAAAAAAAA;  // eax
 413         *--stack = 0xCCCCCCCC;  // ecx
 414         *--stack = 0xDDDDDDDD;  // edx
 415         *--stack = 0xBBBBBBBB;  // ebx
 416         *--stack = 0xD1D1D1D1;  // edi
 417         *--stack = 0x54545454;  // esp - NOT POPED
 418         *--stack = 0x51515151;  // esi
 419         *--stack = 0xB4B4B4B4;  // ebp
 420         //Individual PUSHs
 421         *--stack = ss;  // ds
 422         *--stack = ss;  // es
 423         *--stack = ss;  // fs
 424         *--stack = ss;  // gs
 425
 426         __asm__ __volatile__ (
 427         "mov %%eax,%%esp;\n\t"  // Set stack pointer
 428         "pop %%gs;\n\t"
 429         "pop %%fs;\n\t"
 430         "pop %%es;\n\t"
 431         "pop %%ds;\n\t"
 432         "popa;\n\t"
 433         "iret;\n\t" : : "a" (stack));
 434         for(;;);
 435 }
 436
 437 /**
 438  * \fn void Proc_Exit()
 439  * \brief Kill the current process
 440  */
 441 void Proc_Exit()
 442 {
 443         tThread *thread;
 444         tMsg    *msg;
 445
 446         ///\note Double lock is needed due to overlap of locks
 447
 448         // Lock thread (stop us recieving messages)
 449         LOCK( &gCurrentThread->IsLocked );
 450
 451         // Lock thread list
 452         LOCK( &giThreadListLock );
 453
 454         // Get previous thread on list
 455         thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
 456         if(!thread) {
 457                 Warning("Proc_Exit - Current thread is not on the active queue");
 458                 return;
 459         }
 460
 461         // Clear Message Queue
 462         while( gCurrentThread->Messages )
 463         {
 464                 msg = gCurrentThread->Messages->Next;
 465                 free( gCurrentThread->Messages );
 466                 gCurrentThread->Messages = msg;
 467         }
 468
 469         gCurrentThread->Remaining = 0;  // Clear Remaining Quantum
 470         gCurrentThread->Quantum = 0;    // Clear Quantum to indicate dead thread
 471         thread->Next = gCurrentThread->Next;    // Remove from active
 472
 473         // Add to delete queue
 474         if(gDeleteThreads) {
 475                 gCurrentThread->Next = gDeleteThreads;
 476                 gDeleteThreads = gCurrentThread;
 477         } else {
 478                 gCurrentThread->Next = NULL;
 479                 gDeleteThreads = gCurrentThread;
 480         }
 481
 482         giNumActiveThreads --;
 483         giTotalTickets -= gCurrentThread->NumTickets;
 484
 485         // Mark thread as sleeping
 486         gCurrentThread->Status = THREAD_STAT_DEAD;
 487
 488         // Release spinlocks
 489         RELEASE( &gCurrentThread->IsLocked );   // Released first so that it IS released
 490         RELEASE( &giThreadListLock );
 491         __asm__ __volatile__ ("hlt");
 492 }
 493
 494 /**
 495  * \fn void Proc_Yield()
 496  * \brief Yield remainder of timeslice
 497  */
 498 void Proc_Yield()
 499 {
 500         gCurrentThread->Quantum = 0;
 501         __asm__ __volatile__ ("hlt");
 502 }
 503
 504 /**
 505  * \fn void Proc_Sleep()
 506  * \brief Take the current process off the run queue
 507  */
 508 void Proc_Sleep()
 509 {
 510         tThread *thread;
 511
 512         //Log("Proc_Sleep: %i going to sleep", gCurrentThread->TID);
 513
 514         // Acquire Spinlock
 515         LOCK( &giThreadListLock );
 516
 517         // Get thread before current thread
 518         thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
 519         if(!thread) {
 520                 Warning("Proc_Sleep - Current thread is not on the active queue");
 521                 return;
 522         }
 523
 524         // Don't sleep if there is a message waiting
 525         if( gCurrentThread->Messages ) {
 526                 RELEASE( &giThreadListLock );
 527                 return;
 528         }
 529
 530         // Unset remaining timeslices (force a task switch on timer fire)
 531         gCurrentThread->Remaining = 0;
 532
 533         // Remove from active list
 534         thread->Next = gCurrentThread->Next;
 535
 536         // Add to Sleeping List (at the top)
 537         gCurrentThread->Next = gSleepingThreads;
 538         gSleepingThreads = gCurrentThread;
 539
 540         // Reduce the active count & ticket count
 541         giNumActiveThreads --;
 542         giTotalTickets -= gCurrentThread->NumTickets;
 543
 544         // Mark thread as sleeping
 545         gCurrentThread->Status = THREAD_STAT_SLEEPING;
 546
 547         // Release Spinlock
 548         RELEASE( &giThreadListLock );
 549
 550         __asm__ __volatile__ ("hlt");
 551 }
 552
 553 /**
 554  * \fn void Thread_Wake( tThread *Thread )
 555  * \brief Wakes a sleeping/waiting thread up
 556  */
 557 void Thread_Wake(tThread *Thread)
 558 {
 559         tThread *prev;
 560         switch(Thread->Status)
 561         {
 562         case THREAD_STAT_ACTIVE:        break;
 563         case THREAD_STAT_SLEEPING:
 564                 LOCK( &giThreadListLock );
 565                 prev = Proc_int_GetPrevThread(&gSleepingThreads, Thread);
 566                 prev->Next = Thread->Next;      // Remove from sleeping queue
 567                 Thread->Next = gActiveThreads;  // Add to active queue
 568                 gActiveThreads = Thread;
 569                 Thread->Status = THREAD_STAT_ACTIVE;
 570                 RELEASE( &giThreadListLock );
 571                 break;
 572         case THREAD_STAT_WAITING:
 573                 Warning("Thread_Wake - Waiting threads are not currently supported");
 574                 break;
 575         case THREAD_STAT_DEAD:
 576                 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
 577                 break;
 578         default:
 579                 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
 580                 break;
 581         }
 582 }
 583
 584 /**
 585  * \fn int Proc_Demote(Uint *Err, int Dest, tRegs *Regs)
 586  * \brief Demotes a process to a lower permission level
 587  * \param Err   Pointer to user's errno
 588  */
 589 int Proc_Demote(Uint *Err, int Dest, tRegs *Regs)
 590 {
 591          int    cpl = Regs->cs & 3;
 592         // Sanity Check
 593         if(Dest > 3 || Dest < 0) {
 594                 *Err = -EINVAL;
 595                 return -1;
 596         }
 597
 598         // Permission Check
 599         if(cpl > Dest) {
 600                 *Err = -EACCES;
 601                 return -1;
 602         }
 603
 604         // Change the Segment Registers
 605         Regs->cs = (((Dest+1)<<4) | Dest) - 8;
 606         Regs->ss = ((Dest+1)<<4) | Dest;
 607         // Check if the GP Segs are GDT, then change them
 608         if(!(Regs->ds & 4))     Regs->ds = ((Dest+1)<<4) | Dest;
 609         if(!(Regs->es & 4))     Regs->es = ((Dest+1)<<4) | Dest;
 610         if(!(Regs->fs & 4))     Regs->fs = ((Dest+1)<<4) | Dest;
 611         if(!(Regs->gs & 4))     Regs->gs = ((Dest+1)<<4) | Dest;
 612
 613         return 0;
 614 }
 615
 616 /**
 617  * \fn void Proc_SetTickets(int Num)
 618  * \brief Sets the 'priority' of a task
 619  */
 620 void Proc_SetTickets(int Num)
 621 {
 622         if(Num < 0)     return;
 623         if(Num > MAX_TICKETS)   Num = MAX_TICKETS;
 624
 625         LOCK( &giThreadListLock );
 626         giTotalTickets -= gCurrentThread->NumTickets;
 627         gCurrentThread->NumTickets = Num;
 628         giTotalTickets += Num;
 629         //LOG("giTotalTickets = %i", giTotalTickets);
 630         RELEASE( &giThreadListLock );
 631 }
 632
 633 /**
 634  * \fn tThread *Proc_GetThread(Uint TID)
 635  * \brief Gets a thread given its TID
 636  */
 637 tThread *Proc_GetThread(Uint TID)
 638 {
 639         tThread *thread;
 640
 641         // Search Active List
 642         for(thread = gActiveThreads;
 643                 thread;
 644                 thread = thread->Next)
 645         {
 646                 if(thread->TID == TID)
 647                         return thread;
 648         }
 649
 650         // Search Sleeping List
 651         for(thread = gSleepingThreads;
 652                 thread;
 653                 thread = thread->Next)
 654         {
 655                 if(thread->TID == TID)
 656                         return thread;
 657         }
 658
 659         return NULL;
 660 }
 661
 662 /**
 663  * \fn static tThread *Proc_int_GetPrevThread(tThread *List, tThread *Thread)
 664  * \brief Gets the previous entry in a thead linked list
 665  */
 666 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread)
 667 {
 668         tThread *ret;
 669         // First Entry
 670         if(*List == Thread) {
 671                 return (tThread*)List;
 672         } else {
 673                 for(ret = *List;
 674                         ret->Next && ret->Next != Thread;
 675                         ret = ret->Next
 676                         );
 677                 // Error if the thread is not on the list
 678                 if(!ret->Next || ret->Next != Thread) {
 679                         return NULL;
 680                 }
 681         }
 682         return ret;
 683 }
 684
 685 /**
 686  * \fn void Proc_DumpThreads()
 687  */
 688 void Proc_DumpThreads()
 689 {
 690         tThread *thread;
 691
 692         Log("Active Threads:");
 693         for(thread=gActiveThreads;thread;thread=thread->Next)
 694         {
 695                 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
 696                 Log("  %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
 697                 Log("  CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
 698         }
 699         Log("Sleeping Threads:");
 700         for(thread=gSleepingThreads;thread;thread=thread->Next)
 701         {
 702                 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
 703                 Log("  %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
 704                 Log("  CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
 705         }
 706 }
 707
 708 /**
 709  * \fn void Proc_Scheduler(int CPU)
 710  * \brief Swap current task
 711  */
 712 void Proc_Scheduler(int CPU)
 713 {
 714         Uint    esp, ebp, eip;
 715         Uint    number, ticket;
 716         tThread *thread;
 717
 718         // If the spinlock is set, let it complete
 719         if(giThreadListLock)    return;
 720
 721         // Clear Delete Queue
 722         while(gDeleteThreads)
 723         {
 724                 thread = gDeleteThreads->Next;
 725                 if(gDeleteThreads->IsLocked) {  // Only free if structure is unused
 726                         gDeleteThreads->Status = THREAD_STAT_NULL;
 727                         free( gDeleteThreads );
 728                 }
 729                 gDeleteThreads = thread;
 730         }
 731
 732         // Check if there is any tasks running
 733         if(giNumActiveThreads == 0) {
 734                 Log("No Active threads, sleeping\n");
 735                 __asm__ __volatile__ ("hlt");
 736                 return;
 737         }
 738
 739         // Reduce remaining quantum
 740         if(gCurrentThread->Remaining--) return;
 741         // Reset quantum for next call
 742         gCurrentThread->Remaining = gCurrentThread->Quantum;
 743
 744         // Get machine state
 745         __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
 746         __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
 747         eip = GetEIP();
 748         if(eip == SWITCH_MAGIC) return; // Check if a switch happened
 749
 750         // Save machine state
 751         gCurrentThread->ESP = esp;
 752         gCurrentThread->EBP = ebp;
 753         gCurrentThread->EIP = eip;
 754
 755         // Special case: 1 thread
 756         if(giNumActiveThreads == 1)
 757         {
 758                 // Check if a switch is needed (NumActive can be 1 after a sleep)
 759                 if(gActiveThreads == gCurrentThread)    return;
 760                 // Switch processes
 761                 gCurrentThread = gActiveThreads;
 762                 goto performSwitch;
 763         }
 764
 765         // Get the ticket number
 766         ticket = number = rand() % giTotalTickets;
 767
 768         // Find the next thread
 769         for(thread=gActiveThreads;thread;thread=thread->Next)
 770         {
 771                 if(thread->NumTickets > number) break;
 772                 number -= thread->NumTickets;
 773         }
 774
 775         // Error Check
 776         if(thread == NULL)
 777         {
 778                 number = 0;
 779                 for(thread=gActiveThreads;thread;thread=thread->Next)
 780                         number += thread->NumTickets;
 781                 Panic("Bookeeping Failed - giTotalTicketCount (%i) != true count (%i)",
 782                         giTotalTickets, number);
 783         }
 784
 785         // Set current thread
 786         gCurrentThread = thread;
 787
 788         // Update Kernel Stack pointer
 789         gTSSs[CPU].ESP0 = thread->KernelStack;
 790
 791 performSwitch:
 792         // Set address space
 793         //MM_SetCR3( gCurrentThread->CR3 );
 794         __asm__ __volatile__ ("mov %0, %%cr3"::"a"(gCurrentThread->CR3));
 795         // Switch threads
 796         __asm__ __volatile__ (
 797                 "mov %1, %%esp\n\t"
 798                 "mov %2, %%ebp\n\t"
 799                 "jmp *%3" : :
 800                 "a"(SWITCH_MAGIC), "b"(gCurrentThread->ESP),
 801                 "d"(gCurrentThread->EBP), "c"(gCurrentThread->EIP));
 802         for(;;);        // Shouldn't reach here
 803 }
 804
 805 // --- Process Structure Access Functions ---
 806 int Proc_GetPID()
 807 {
 808         return gCurrentThread->TGID;
 809 }
 810 int Proc_GetTID()
 811 {
 812         return gCurrentThread->TID;
 813 }
 814 int Proc_GetUID()
 815 {
 816         return gCurrentThread->UID;
 817 }
 818 int Proc_GetGID()
 819 {
 820         return gCurrentThread->GID;
 821 }
 822
 823 /**
 824  * \fn Uint rand()
 825  * \brief Pseudo random number generator
 826  * \note Unknown effectiveness (made up on the spot)
 827  */
 828 Uint rand()
 829 {
 830         static Uint     randomState = RANDOM_SEED;
 831         Uint    ret = randomState;
 832          int    roll = randomState & 31;
 833         randomState = (randomState << roll) | (randomState >> (32-roll));
 834         randomState ^= 0x9A3C5E78;
 835         return ret;
 836 }