2 * AcessOS Microkernel Version
14 #define SWITCH_MAGIC 0xFFFACE55 // There is no code in this area
15 #define DEFAULT_QUANTUM 10
16 #define DEFAULT_TICKETS 5
17 #define MAX_TICKETS 10
18 #define TIMER_DIVISOR 11931 //~100Hz
22 extern Uint GetEIP(); // start.asm
23 extern Uint32 gaInitPageDir[1024]; // start.asm
24 extern void Kernel_Stack_Top;
28 void Proc_ChangeStack();
29 int Proc_Clone(Uint *Err, Uint Flags);
33 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread);
34 void Proc_Scheduler();
40 tThread gThreadZero = {
41 NULL, 0, // Next, Lock
42 THREAD_STAT_ACTIVE, // Status
46 0, 0, 0, // ESP, EBP, EIP (Set on switch)
48 {0,0,0}, // PML4 Entries
50 (Uint)&gaInitPageDir-KERNEL_BASE, // CR3
52 (Uint)&Kernel_Stack_Top, // Kernel Stack (Unused as it is PL0)
53 NULL, NULL, // Messages, Last Message
54 DEFAULT_QUANTUM, DEFAULT_QUANTUM, // Quantum, Remaining
56 {0} // Default config to zero
60 volatile int giThreadListLock = 0; ///\note NEVER use a heap function while locked
61 // --- Current State ---
63 tThread **gCurrentThread = NULL;
64 # define CUR_THREAD gCurrentThread[0]
66 tThread *gCurrentThread = NULL;
67 # define CUR_THREAD gCurrentThread
69 volatile int giNumActiveThreads = 0;
70 volatile int giTotalTickets = 0;
71 volatile Uint giNextTID = 1;
72 // --- Thread Lists ---
73 tThread *gActiveThreads = NULL; // Currently Running Threads
74 tThread *gSleepingThreads = NULL; // Sleeping Threads
75 tThread *gDeleteThreads = NULL; // Threads to delete
76 // --- Multiprocessing ---
79 tMPInfo *gMPTable = NULL;
82 Uint32 *gPML4s[4] = NULL;
91 * \fn void Proc_Start()
92 * \brief Starts the process scheduler
99 // -- Initialise Multiprocessing
100 // Find MP Floating Table
102 for(pos = KERNEL_BASE|0x9FC00; pos < (KERNEL_BASE|0xA0000); pos += 16) {
103 if( *(Uint*)(pos) == MPTABLE_IDENT ) {
104 if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
105 gMPTable = (void*)pos;
115 for(pos = KERNEL_BASE|0xF0000; pos < (KERNEL_BASE|0x100000); pos += 16) {
116 if( *(Uint*)(pos) == MPTABLE_IDENT ) {
117 if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
118 gMPTable = (void*)pos;
124 // If the MP Table Exists, parse it
127 Panic("Uh oh... MP Table Parsing is unimplemented\n");
136 for(pos=0;pos<giNumCPUs;pos++)
141 gTSSs[pos].SS0 = 0x10;
142 gTSSs[pos].ESP0 = 0; // Set properly by scheduler
143 gGDT[5+pos].LimitLow = sizeof(tTSS);
144 gGDT[5+pos].LimitHi = 0;
145 gGDT[5+pos].Access = 0x89; // Type
146 gGDT[5+pos].Flags = 0x4;
147 gGDT[5+pos].BaseLow = (Uint)&gTSSs[pos] & 0xFFFF;
148 gGDT[5+pos].BaseMid = (Uint)&gTSSs[pos] >> 16;
149 gGDT[5+pos].BaseHi = (Uint)&gTSSs[pos] >> 24;
152 for(pos=0;pos<giNumCPUs;pos++) {
154 __asm__ __volatile__ ("ltr %%ax"::"a"(0x28+pos*8));
159 // Set timer frequency
160 outb(0x43, 0x34); // Set Channel 0, Low/High, Rate Generator
161 outb(0x40, TIMER_DIVISOR&0xFF); // Low Byte of Divisor
162 outb(0x40, (TIMER_DIVISOR>>8)&0xFF); // High Byte
164 // Create Initial Task
165 gActiveThreads = &gThreadZero;
166 gCurrentThread = &gThreadZero;
167 giTotalTickets = gThreadZero.NumTickets;
168 giNumActiveThreads = 1;
170 // Create Per-Process Data Block
171 MM_Allocate(MM_PPD_CFG);
178 if(Proc_Clone(0, 0) == 0)
180 gCurrentThread->ThreadName = "Idle Thread";
181 Proc_SetTickets(0); // Never called randomly
182 gCurrentThread->Quantum = 1; // 1 slice quantum
183 for(;;) __asm__ __volatile__ ("hlt"); // Just yeilds
187 // Start Interrupts (and hence scheduler)
188 __asm__ __volatile__("sti");
192 * \fn void Proc_ChangeStack()
193 * \brief Swaps the current stack for a new one (in the proper stack reigon)
195 void Proc_ChangeStack()
199 Uint curBase, newBase;
201 __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
202 __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
207 newBase = MM_NewKStack();
210 Panic("What the?? Unable to allocate space for initial kernel stack");
214 curBase = gCurrentThread->KernelStack;
216 LOG("curBase = 0x%x, newBase = 0x%x", curBase, newBase);
218 // Get ESP as a used size
220 LOG("memcpy( %p, %p, 0x%x )", (void*)(newBase - esp), (void*)(curBase - esp), esp );
222 memcpy( (void*)(newBase - esp), (void*)(curBase - esp), esp );
223 // Get ESP as an offset in the new stack
226 ebp = newBase - (curBase - ebp);
228 // Repair EBPs & Stack Addresses
229 // Catches arguments also, but may trash stack-address-like values
230 for(tmpEbp = esp; tmpEbp < newBase; tmpEbp += 4)
232 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < curBase)
233 *(Uint*)tmpEbp += newBase - curBase;
236 gCurrentThread->KernelStack = newBase;
238 __asm__ __volatile__ ("mov %0, %%esp"::"r"(esp));
239 __asm__ __volatile__ ("mov %0, %%ebp"::"r"(ebp));
243 * \fn int Proc_Clone(Uint *Err, Uint Flags)
244 * \brief Clone the current process
246 int Proc_Clone(Uint *Err, Uint Flags)
251 __asm__ __volatile__ ("mov %%esp, %0": "=r"(esp));
252 __asm__ __volatile__ ("mov %%ebp, %0": "=r"(ebp));
254 // Create new thread structure
255 newThread = malloc( sizeof(tThread) );
257 Warning("Proc_Clone - Out of memory when creating thread\n");
261 // Base new thread on old
262 memcpy(newThread, gCurrentThread, sizeof(tThread));
263 // Initialise Memory Space (New Addr space or kernel stack)
264 if(Flags & CLONE_VM) {
265 newThread->TGID = newThread->TID;
266 newThread->CR3 = MM_Clone();
268 Uint tmpEbp, oldEsp = esp;
271 newThread->KernelStack = MM_NewKStack();
273 if(newThread->KernelStack == 0) {
278 // Get ESP as a used size
279 esp = gCurrentThread->KernelStack - esp;
281 memcpy( (void*)(newThread->KernelStack - esp), (void*)(gCurrentThread->KernelStack - esp), esp );
282 // Get ESP as an offset in the new stack
283 esp = newThread->KernelStack - esp;
285 ebp = newThread->KernelStack - (gCurrentThread->KernelStack - ebp);
287 // Repair EBPs & Stack Addresses
288 // Catches arguments also, but may trash stack-address-like values
289 for(tmpEbp = esp; tmpEbp < newThread->KernelStack; tmpEbp += 4)
291 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < gCurrentThread->KernelStack)
292 *(Uint*)tmpEbp += newThread->KernelStack - gCurrentThread->KernelStack;
296 // Set Pointer, Spinlock and TID
297 newThread->Next = NULL;
298 newThread->IsLocked = 0;
299 newThread->TID = giNextTID++;
301 // Clear message list (messages are not inherited)
302 newThread->Messages = NULL;
303 newThread->LastMessage = NULL;
305 // Set remaining (sheduler expects remaining to be correct)
306 newThread->Remaining = newThread->Quantum;
308 // Save core machine state
309 newThread->ESP = esp;
310 newThread->EBP = ebp;
312 if(eip == SWITCH_MAGIC) {
313 outb(0x20, 0x20); // ACK Timer and return as child
318 newThread->EIP = eip;
320 //Log(" Proc_Clone: giTimestamp = %i.%07i", (Uint)giTimestamp, (Uint)giPartMiliseconds/214);
322 // Lock list and add to active
323 LOCK( &giThreadListLock );
324 newThread->Next = gActiveThreads;
325 gActiveThreads = newThread;
326 giNumActiveThreads ++;
327 giTotalTickets += newThread->NumTickets;
328 RELEASE( &giThreadListLock );
330 return newThread->TID;
334 * \fn void Proc_SetThreadName()
335 * \brief Sets the thread's name
337 void Proc_SetThreadName(char *NewName)
339 if( (Uint)CUR_THREAD->ThreadName > 0xC0400000 )
340 free( CUR_THREAD->ThreadName );
341 CUR_THREAD->ThreadName = malloc(strlen(NewName)+1);
342 strcpy(CUR_THREAD->ThreadName, NewName);
346 * \fn Uint Proc_MakeUserStack()
347 * \brief Creates a new user stack
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()
687 * \brief Dums a list of currently running threads
689 void Proc_DumpThreads()
693 Log("Active Threads:");
694 for(thread=gActiveThreads;thread;thread=thread->Next)
696 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
697 Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
698 Log(" CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
700 Log("Sleeping Threads:");
701 for(thread=gSleepingThreads;thread;thread=thread->Next)
703 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
704 Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
705 Log(" CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
710 * \fn void Proc_Scheduler(int CPU)
711 * \brief Swap current thread and clears dead threads
713 void Proc_Scheduler(int CPU)
719 // If the spinlock is set, let it complete
720 if(giThreadListLock) return;
722 // Clear Delete Queue
723 while(gDeleteThreads)
725 thread = gDeleteThreads->Next;
726 if(gDeleteThreads->IsLocked) { // Only free if structure is unused
727 gDeleteThreads->Status = THREAD_STAT_NULL;
728 free( gDeleteThreads );
730 gDeleteThreads = thread;
733 // Check if there is any tasks running
734 if(giNumActiveThreads == 0) {
735 Log("No Active threads, sleeping\n");
736 __asm__ __volatile__ ("hlt");
740 // Reduce remaining quantum
741 if(gCurrentThread->Remaining--) return;
742 // Reset quantum for next call
743 gCurrentThread->Remaining = gCurrentThread->Quantum;
746 __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
747 __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
749 if(eip == SWITCH_MAGIC) return; // Check if a switch happened
751 // Save machine state
752 gCurrentThread->ESP = esp;
753 gCurrentThread->EBP = ebp;
754 gCurrentThread->EIP = eip;
756 // Special case: 1 thread
757 if(giNumActiveThreads == 1)
759 // Check if a switch is needed (NumActive can be 1 after a sleep)
760 if(gActiveThreads == gCurrentThread) return;
762 gCurrentThread = gActiveThreads;
766 // Get the ticket number
767 ticket = number = rand() % giTotalTickets;
769 // Find the next thread
770 for(thread=gActiveThreads;thread;thread=thread->Next)
772 if(thread->NumTickets > number) break;
773 number -= thread->NumTickets;
780 for(thread=gActiveThreads;thread;thread=thread->Next)
781 number += thread->NumTickets;
782 Panic("Bookeeping Failed - giTotalTicketCount (%i) != true count (%i)",
783 giTotalTickets, number);
786 // Set current thread
787 gCurrentThread = thread;
789 // Update Kernel Stack pointer
790 gTSSs[CPU].ESP0 = thread->KernelStack;
794 //MM_SetCR3( gCurrentThread->CR3 );
795 __asm__ __volatile__ ("mov %0, %%cr3"::"a"(gCurrentThread->CR3));
797 __asm__ __volatile__ (
801 "a"(SWITCH_MAGIC), "b"(gCurrentThread->ESP),
802 "d"(gCurrentThread->EBP), "c"(gCurrentThread->EIP));
803 for(;;); // Shouldn't reach here
806 // --- Process Structure Access Functions ---
809 return gCurrentThread->TGID;
813 return gCurrentThread->TID;
817 return gCurrentThread->UID;
821 return gCurrentThread->GID;