2 * AcessOS Microkernel Version
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
23 extern Uint GetEIP(); // start.asm
24 extern Uint32 gaInitPageDir[1024]; // start.asm
25 extern void Kernel_Stack_Top;
29 void Proc_ChangeStack();
30 int Proc_Clone(Uint *Err, Uint Flags);
34 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread);
35 void Proc_Scheduler();
41 tThread gThreadZero = {
42 NULL, 0, // Next, Lock
43 THREAD_STAT_ACTIVE, // Status
47 0, 0, 0, // ESP, EBP, EIP (Set on switch)
49 {0,0,0}, // PML4 Entries
51 (Uint)&gaInitPageDir-KERNEL_BASE, // CR3
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
57 {0} // Default config to zero
61 volatile int giThreadListLock = 0; ///\note NEVER use a heap function while locked
62 // --- Current State ---
64 tThread **gCurrentThread = NULL;
65 # define CUR_THREAD gCurrentThread[0]
67 tThread *gCurrentThread = NULL;
68 # define CUR_THREAD gCurrentThread
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 ---
80 tMPInfo *gMPTable = NULL;
83 Uint32 *gPML4s[4] = NULL;
92 * \fn void Proc_Start()
93 * \brief Starts the process scheduler
100 // -- Initialise Multiprocessing
101 // Find MP Floating Table
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;
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;
125 // If the MP Table Exists, parse it
128 Panic("Uh oh... MP Table Parsing is unimplemented\n");
137 for(pos=0;pos<giNumCPUs;pos++)
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;
153 for(pos=0;pos<giNumCPUs;pos++) {
155 __asm__ __volatile__ ("ltr %%ax"::"a"(0x28+pos*8));
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
165 // Create Initial Task
166 gActiveThreads = &gThreadZero;
167 gCurrentThread = &gThreadZero;
168 giTotalTickets = gThreadZero.NumTickets;
169 giNumActiveThreads = 1;
171 // Create Per-Process Data Block
172 MM_Allocate(MM_PPD_CFG);
179 if(Proc_Clone(0, 0) == 0)
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
188 // Start Interrupts (and hence scheduler)
189 __asm__ __volatile__("sti");
193 * \fn void Proc_ChangeStack()
194 * \brief Swaps the current stack for a new one (in the proper stack reigon)
196 void Proc_ChangeStack()
200 Uint curBase, newBase;
202 __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
203 __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
208 newBase = MM_NewKStack();
211 Panic("What the?? Unable to allocate space for initial kernel stack");
215 curBase = gCurrentThread->KernelStack;
217 LOG("curBase = 0x%x, newBase = 0x%x", curBase, newBase);
219 // Get ESP as a used size
221 LOG("memcpy( %p, %p, 0x%x )", (void*)(newBase - esp), (void*)(curBase - esp), esp );
223 memcpy( (void*)(newBase - esp), (void*)(curBase - esp), esp );
224 // Get ESP as an offset in the new stack
227 ebp = newBase - (curBase - ebp);
229 // Repair EBPs & Stack Addresses
230 // Catches arguments also, but may trash stack-address-like values
231 for(tmpEbp = esp; tmpEbp < newBase; tmpEbp += 4)
233 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < curBase)
234 *(Uint*)tmpEbp += newBase - curBase;
237 gCurrentThread->KernelStack = newBase;
239 __asm__ __volatile__ ("mov %0, %%esp"::"r"(esp));
240 __asm__ __volatile__ ("mov %0, %%ebp"::"r"(ebp));
244 * \fn int Proc_Clone(Uint *Err, Uint Flags)
245 * \brief Clone the current process
247 int Proc_Clone(Uint *Err, Uint Flags)
252 __asm__ __volatile__ ("mov %%esp, %0": "=r"(esp));
253 __asm__ __volatile__ ("mov %%ebp, %0": "=r"(ebp));
255 // Create new thread structure
256 newThread = malloc( sizeof(tThread) );
258 Warning("Proc_Clone - Out of memory when creating thread\n");
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();
269 Uint tmpEbp, oldEsp = esp;
272 newThread->KernelStack = MM_NewKStack();
274 if(newThread->KernelStack == 0) {
279 // Get ESP as a used size
280 esp = gCurrentThread->KernelStack - esp;
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;
286 ebp = newThread->KernelStack - (gCurrentThread->KernelStack - ebp);
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)
292 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < gCurrentThread->KernelStack)
293 *(Uint*)tmpEbp += newThread->KernelStack - gCurrentThread->KernelStack;
297 // Set Pointer, Spinlock and TID
298 newThread->Next = NULL;
299 newThread->IsLocked = 0;
300 newThread->TID = giNextTID++;
302 // Clear message list (messages are not inherited)
303 newThread->Messages = NULL;
304 newThread->LastMessage = NULL;
306 // Set remaining (sheduler expects remaining to be correct)
307 newThread->Remaining = newThread->Quantum;
309 // Save core machine state
310 newThread->ESP = esp;
311 newThread->EBP = ebp;
313 if(eip == SWITCH_MAGIC) {
314 outb(0x20, 0x20); // ACK Timer and return as child
319 newThread->EIP = eip;
321 //Log(" Proc_Clone: giTimestamp = %i.%07i", (Uint)giTimestamp, (Uint)giPartMiliseconds/214);
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 );
331 return newThread->TID;
335 * \fn void Proc_SetThreadName()
336 * \brief Sets the thread's name
338 void Proc_SetThreadName(char *NewName)
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);
347 * \fn Uint Proc_MakeUserStack()
349 Uint Proc_MakeUserStack()
352 Uint base = USER_STACK_TOP - USER_STACK_SZ;
354 // Check Prospective Space
355 for( i = USER_STACK_SZ >> 12; i--; )
356 if( MM_GetPhysAddr( base + (i<<12) ) != 0 )
359 if(i != -1) return 0;
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) );
365 return base + USER_STACK_SZ;
370 * \fn void Proc_StartUser(Uint Entrypoint, Uint Base, int ArgC, char **ArgV, char **EnvP, int DataSize)
371 * \brief Starts a user task
373 void Proc_StartUser(Uint Entrypoint, Uint *Bases, int ArgC, char **ArgV, char **EnvP, int DataSize)
375 Uint *stack = (void*)Proc_MakeUserStack();
380 LOG("stack = 0x%x", stack);
383 stack = (void*)( (Uint)stack - DataSize );
384 memcpy( stack, ArgV, DataSize );
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;
392 for( i = 0; EnvP[i]; i++ ) EnvP[i] += delta;
394 // User Mode Segments
395 ss = 0x23; cs = 0x1B;
398 *--stack = (Uint)EnvP;
399 *--stack = (Uint)ArgV;
400 *--stack = (Uint)ArgC;
403 *--stack = 0; // Return Address
404 delta = (Uint)stack; // Reuse delta to save SP
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
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
426 __asm__ __volatile__ (
427 "mov %%eax,%%esp;\n\t" // Set stack pointer
433 "iret;\n\t" : : "a" (stack));
438 * \fn void Proc_Exit()
439 * \brief Kill the current process
446 ///\note Double lock is needed due to overlap of locks
448 // Lock thread (stop us recieving messages)
449 LOCK( &gCurrentThread->IsLocked );
452 LOCK( &giThreadListLock );
454 // Get previous thread on list
455 thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
457 Warning("Proc_Exit - Current thread is not on the active queue");
461 // Clear Message Queue
462 while( gCurrentThread->Messages )
464 msg = gCurrentThread->Messages->Next;
465 free( gCurrentThread->Messages );
466 gCurrentThread->Messages = msg;
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
473 // Add to delete queue
475 gCurrentThread->Next = gDeleteThreads;
476 gDeleteThreads = gCurrentThread;
478 gCurrentThread->Next = NULL;
479 gDeleteThreads = gCurrentThread;
482 giNumActiveThreads --;
483 giTotalTickets -= gCurrentThread->NumTickets;
485 // Mark thread as sleeping
486 gCurrentThread->Status = THREAD_STAT_DEAD;
489 RELEASE( &gCurrentThread->IsLocked ); // Released first so that it IS released
490 RELEASE( &giThreadListLock );
491 __asm__ __volatile__ ("hlt");
495 * \fn void Proc_Yield()
496 * \brief Yield remainder of timeslice
500 gCurrentThread->Quantum = 0;
501 __asm__ __volatile__ ("hlt");
505 * \fn void Proc_Sleep()
506 * \brief Take the current process off the run queue
512 //Log("Proc_Sleep: %i going to sleep", gCurrentThread->TID);
515 LOCK( &giThreadListLock );
517 // Get thread before current thread
518 thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
520 Warning("Proc_Sleep - Current thread is not on the active queue");
524 // Don't sleep if there is a message waiting
525 if( gCurrentThread->Messages ) {
526 RELEASE( &giThreadListLock );
530 // Unset remaining timeslices (force a task switch on timer fire)
531 gCurrentThread->Remaining = 0;
533 // Remove from active list
534 thread->Next = gCurrentThread->Next;
536 // Add to Sleeping List (at the top)
537 gCurrentThread->Next = gSleepingThreads;
538 gSleepingThreads = gCurrentThread;
540 // Reduce the active count & ticket count
541 giNumActiveThreads --;
542 giTotalTickets -= gCurrentThread->NumTickets;
544 // Mark thread as sleeping
545 gCurrentThread->Status = THREAD_STAT_SLEEPING;
548 RELEASE( &giThreadListLock );
550 __asm__ __volatile__ ("hlt");
554 * \fn void Thread_Wake( tThread *Thread )
555 * \brief Wakes a sleeping/waiting thread up
557 void Thread_Wake(tThread *Thread)
560 switch(Thread->Status)
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 );
572 case THREAD_STAT_WAITING:
573 Warning("Thread_Wake - Waiting threads are not currently supported");
575 case THREAD_STAT_DEAD:
576 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
579 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
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
589 int Proc_Demote(Uint *Err, int Dest, tRegs *Regs)
591 int cpl = Regs->cs & 3;
593 if(Dest > 3 || Dest < 0) {
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;
617 * \fn void Proc_SetTickets(int Num)
618 * \brief Sets the 'priority' of a task
620 void Proc_SetTickets(int Num)
623 if(Num > MAX_TICKETS) Num = MAX_TICKETS;
625 LOCK( &giThreadListLock );
626 giTotalTickets -= gCurrentThread->NumTickets;
627 gCurrentThread->NumTickets = Num;
628 giTotalTickets += Num;
629 //LOG("giTotalTickets = %i", giTotalTickets);
630 RELEASE( &giThreadListLock );
634 * \fn tThread *Proc_GetThread(Uint TID)
635 * \brief Gets a thread given its TID
637 tThread *Proc_GetThread(Uint TID)
641 // Search Active List
642 for(thread = gActiveThreads;
644 thread = thread->Next)
646 if(thread->TID == TID)
650 // Search Sleeping List
651 for(thread = gSleepingThreads;
653 thread = thread->Next)
655 if(thread->TID == TID)
663 * \fn static tThread *Proc_int_GetPrevThread(tThread *List, tThread *Thread)
664 * \brief Gets the previous entry in a thead linked list
666 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread)
670 if(*List == Thread) {
671 return (tThread*)List;
674 ret->Next && ret->Next != Thread;
677 // Error if the thread is not on the list
678 if(!ret->Next || ret->Next != Thread) {
686 * \fn void Proc_DumpThreads()
688 void Proc_DumpThreads()
692 Log("Active Threads:");
693 for(thread=gActiveThreads;thread;thread=thread->Next)
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);
699 Log("Sleeping Threads:");
700 for(thread=gSleepingThreads;thread;thread=thread->Next)
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);
709 * \fn void Proc_Scheduler(int CPU)
710 * \brief Swap current task
712 void Proc_Scheduler(int CPU)
718 // If the spinlock is set, let it complete
719 if(giThreadListLock) return;
721 // Clear Delete Queue
722 while(gDeleteThreads)
724 thread = gDeleteThreads->Next;
725 if(gDeleteThreads->IsLocked) { // Only free if structure is unused
726 gDeleteThreads->Status = THREAD_STAT_NULL;
727 free( gDeleteThreads );
729 gDeleteThreads = thread;
732 // Check if there is any tasks running
733 if(giNumActiveThreads == 0) {
734 Log("No Active threads, sleeping\n");
735 __asm__ __volatile__ ("hlt");
739 // Reduce remaining quantum
740 if(gCurrentThread->Remaining--) return;
741 // Reset quantum for next call
742 gCurrentThread->Remaining = gCurrentThread->Quantum;
745 __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
746 __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
748 if(eip == SWITCH_MAGIC) return; // Check if a switch happened
750 // Save machine state
751 gCurrentThread->ESP = esp;
752 gCurrentThread->EBP = ebp;
753 gCurrentThread->EIP = eip;
755 // Special case: 1 thread
756 if(giNumActiveThreads == 1)
758 // Check if a switch is needed (NumActive can be 1 after a sleep)
759 if(gActiveThreads == gCurrentThread) return;
761 gCurrentThread = gActiveThreads;
765 // Get the ticket number
766 ticket = number = rand() % giTotalTickets;
768 // Find the next thread
769 for(thread=gActiveThreads;thread;thread=thread->Next)
771 if(thread->NumTickets > number) break;
772 number -= thread->NumTickets;
779 for(thread=gActiveThreads;thread;thread=thread->Next)
780 number += thread->NumTickets;
781 Panic("Bookeeping Failed - giTotalTicketCount (%i) != true count (%i)",
782 giTotalTickets, number);
785 // Set current thread
786 gCurrentThread = thread;
788 // Update Kernel Stack pointer
789 gTSSs[CPU].ESP0 = thread->KernelStack;
793 //MM_SetCR3( gCurrentThread->CR3 );
794 __asm__ __volatile__ ("mov %0, %%cr3"::"a"(gCurrentThread->CR3));
796 __asm__ __volatile__ (
800 "a"(SWITCH_MAGIC), "b"(gCurrentThread->ESP),
801 "d"(gCurrentThread->EBP), "c"(gCurrentThread->EIP));
802 for(;;); // Shouldn't reach here
805 // --- Process Structure Access Functions ---
808 return gCurrentThread->TGID;
812 return gCurrentThread->TID;
816 return gCurrentThread->UID;
820 return gCurrentThread->GID;
825 * \brief Pseudo random number generator
826 * \note Unknown effectiveness (made up on the spot)
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;