2 * AcessOS Microkernel Version
12 #define RANDOM_SEED 0xACE55051
13 #define SWITCH_MAGIC 0xFFFACE55 // There is no code in this area
14 #define DEFAULT_QUANTUM 10
15 #define DEFAULT_TICKETS 5
16 #define MAX_TICKETS 10
17 #define TIMER_DIVISOR 11931 //~100Hz
20 #define TIMER_BASE 1193182 //Hz
21 #define MS_PER_TICK_WHOLE (1000*(TIMER_DIVISOR)/(TIMER_BASE))
22 #define MS_PER_TICK_FRACT ((Uint64)(1000*TIMER_DIVISOR-((Uint64)MS_PER_TICK_WHOLE)*TIMER_BASE)*(0x80000000/TIMER_BASE))
25 extern Uint GetEIP(); // start.asm
26 extern Uint32 gaInitPageDir[1024]; // start.asm
27 extern void Kernel_Stack_Top;
31 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread);
32 void Proc_Scheduler();
37 tThread gThreadZero = {
38 NULL, 0, // Next, Lock
39 THREAD_STAT_ACTIVE, // Status
43 0, 0, 0, // ESP, EBP, EIP (Set on switch)
44 (Uint)&gaInitPageDir-KERNEL_BASE, // CR3
45 (Uint)&Kernel_Stack_Top, // Kernel Stack (Unused as it it PL0)
46 NULL, NULL, // Messages, Last Message
47 DEFAULT_QUANTUM, DEFAULT_QUANTUM, // Quantum, Remaining
52 int giThreadListLock = 0; ///\note NEVER use a heap function while locked
53 // --- Current State ---
54 tThread *gCurrentThread = NULL;
55 int giNumActiveThreads = 0;
56 int giTotalTickets = 0;
58 // --- Thread Lists ---
59 tThread *gActiveThreads = NULL; // Currently Running Threads
60 tThread *gSleepingThreads = NULL; // Sleeping Threads
61 tThread *gDeleteThreads = NULL; // Threads to delete
62 // --- Timekeeping ---
64 Uint64 giTimestamp = 0;
65 Uint64 giPartMiliseconds = 0;
66 // --- Multiprocessing ---
68 tMPInfo *gMPTable = NULL;
74 * \fn void Proc_Start()
75 * \brief Starts the process scheduler
80 // -- Initialise Multiprocessing
81 // Find MP Floating Table
83 for(pos = KERNEL_BASE|0x9FC00; pos < (KERNEL_BASE|0xA0000); pos += 16) {
84 if( *(Uint*)(pos) == MPTABLE_IDENT ) {
85 if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
86 gMPTable = (void*)pos;
96 for(pos = KERNEL_BASE|0xF0000; pos < (KERNEL_BASE|0x100000); pos += 16) {
97 if( *(Uint*)(pos) == MPTABLE_IDENT ) {
98 if(ByteSum( (void*)pos, sizeof(tMPInfo) ) != 0) continue;
99 gMPTable = (void*)pos;
105 // If the MP Table Exists, parse it
108 Panic("Uh oh... MP Table Parsing is unimplemented\n");
115 for(pos=0;pos<giNumCPUs;pos++)
117 gTSSs[pos].SS0 = 0x10;
118 gTSSs[pos].ESP0 = 0; // Set properly by scheduler
119 gGDT[9+pos].LimitLow = sizeof(tTSS);
120 gGDT[9+pos].LimitHi = 0;
121 gGDT[9+pos].Access = 0x89; // Type
122 gGDT[9+pos].Flags = 0x4;
123 gGDT[9+pos].BaseLow = (Uint)&gTSSs[pos] & 0xFFFF;
124 gGDT[9+pos].BaseMid = (Uint)&gTSSs[pos] >> 16;
125 gGDT[9+pos].BaseHi = (Uint)&gTSSs[pos] >> 24;
127 for(pos=0;pos<giNumCPUs;pos++) {
128 __asm__ __volatile__ ("ltr %%ax"::"a"(0x48+pos*8));
131 // Set timer frequency
132 outb(0x43, 0x34); // Set Channel 0, Low/High, Rate Generator
133 outb(0x40, TIMER_DIVISOR&0xFF); // Low Byte of Divisor
134 outb(0x40, (TIMER_DIVISOR>>8)&0xFF); // High Byte
138 giPartMiliseconds = 0;
141 // Create Initial Task
142 gActiveThreads = &gThreadZero;
143 gCurrentThread = &gThreadZero;
144 giTotalTickets = gThreadZero.NumTickets;
145 giNumActiveThreads = 1;
148 if(Proc_Clone(0, 0) == 0)
150 gCurrentThread->ThreadName = "Idle Thread";
151 Proc_SetTickets(0); // Never called randomly
152 gCurrentThread->Quantum = 1; // 1 slice quantum
153 for(;;) __asm__ __volatile__ ("hlt"); // Just yeilds
156 // Start Interrupts (and hence scheduler)
157 __asm__ __volatile__("sti");
161 * \fn int Proc_Clone(Uint *Err, Uint Flags)
162 * \brief Clone the current process
164 int Proc_Clone(Uint *Err, Uint Flags)
169 __asm__ __volatile__ ("mov %%esp, %0": "=r"(esp));
170 __asm__ __volatile__ ("mov %%ebp, %0": "=r"(ebp));
172 // Create new thread structure
173 newThread = malloc( sizeof(tThread) );
175 Warning("Proc_Clone - Out of memory when creating thread\n");
179 // Base new thread on old
180 memcpy(newThread, gCurrentThread, sizeof(tThread));
181 // Initialise Memory Space (New Addr space or kernel stack)
182 if(Flags & CLONE_VM) {
183 newThread->TGID = newThread->TID;
184 newThread->CR3 = MM_Clone();
186 Uint tmpEbp, oldEsp = esp;
189 newThread->KernelStack = MM_NewKStack();
191 if(newThread->KernelStack == 0) {
196 // Get ESP as a used size
197 esp = gCurrentThread->KernelStack - esp;
199 memcpy( (void*)(newThread->KernelStack - esp), (void*)(gCurrentThread->KernelStack - esp), esp );
200 // Get ESP as an offset in the new stack
201 esp = newThread->KernelStack - esp;
203 ebp = newThread->KernelStack - (gCurrentThread->KernelStack - ebp);
205 // Repair EBPs & Stack Addresses
208 while(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < gCurrentThread->KernelStack)
210 *(Uint*)tmpEbp += newThread->KernelStack - gCurrentThread->KernelStack;
211 tmpEbp = *(Uint*)tmpEbp;
213 #else // Catches arguments also, but may trash stack-address-like values
214 for(tmpEbp = esp; tmpEbp < newThread->KernelStack; tmpEbp += 4)
216 if(oldEsp < *(Uint*)tmpEbp && *(Uint*)tmpEbp < gCurrentThread->KernelStack)
217 *(Uint*)tmpEbp += newThread->KernelStack - gCurrentThread->KernelStack;
222 // Set Pointer, Spinlock and TID
223 newThread->Next = NULL;
224 newThread->IsLocked = 0;
225 newThread->TID = giNextTID++;
227 // Clear message list (messages are not inherited)
228 newThread->Messages = NULL;
229 newThread->LastMessage = NULL;
231 // Set remaining (sheduler expects remaining to be correct)
232 newThread->Remaining = newThread->Quantum;
234 // Save core machine state
235 newThread->ESP = esp;
236 newThread->EBP = ebp;
238 if(eip == SWITCH_MAGIC) {
239 outb(0x20, 0x20); // ACK Timer and return as child
244 newThread->EIP = eip;
246 //Log(" Proc_Clone: giTimestamp = %i.%07i", (Uint)giTimestamp, (Uint)giPartMiliseconds/214);
248 // Lock list and add to active
249 LOCK( &giThreadListLock );
250 newThread->Next = gActiveThreads;
251 gActiveThreads = newThread;
252 giNumActiveThreads ++;
253 giTotalTickets += newThread->NumTickets;
254 RELEASE( &giThreadListLock );
256 return newThread->TID;
260 * \fn void Proc_Exit()
261 * \brief Kill the current process
268 ///\note Double lock is needed due to overlap of locks
270 // Lock thread (stop us recieving messages)
271 LOCK( &gCurrentThread->IsLocked );
274 LOCK( &giThreadListLock );
276 // Get previous thread on list
277 thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
279 Warning("Proc_Exit - Current thread is not on the active queue");
283 // Clear Message Queue
284 while( gCurrentThread->Messages )
286 msg = gCurrentThread->Messages->Next;
287 free( gCurrentThread->Messages );
288 gCurrentThread->Messages = msg;
291 gCurrentThread->Remaining = 0; // Clear Remaining Quantum
292 gCurrentThread->Quantum = 0; // Clear Quantum to indicate dead thread
293 thread->Next = gCurrentThread->Next; // Remove from active
295 // Add to delete queue
297 gCurrentThread->Next = gDeleteThreads;
298 gDeleteThreads = gCurrentThread;
300 gCurrentThread->Next = NULL;
301 gDeleteThreads = gCurrentThread;
304 giNumActiveThreads --;
305 giTotalTickets -= gCurrentThread->NumTickets;
307 // Mark thread as sleeping
308 gCurrentThread->Status = THREAD_STAT_DEAD;
311 RELEASE( &gCurrentThread->IsLocked ); // Released first so that it IS released
312 RELEASE( &giThreadListLock );
313 __asm__ __volatile__ ("hlt");
317 * \fn void Proc_Yield()
318 * \brief Yield remainder of timeslice
322 gCurrentThread->Quantum = 0;
323 __asm__ __volatile__ ("hlt");
327 * \fn void Proc_Sleep()
328 * \brief Take the current process off the run queue
334 //Log("Proc_Sleep: %i going to sleep", gCurrentThread->TID);
337 LOCK( &giThreadListLock );
339 // Get thread before current thread
340 thread = Proc_int_GetPrevThread( &gActiveThreads, gCurrentThread );
342 Warning("Proc_Sleep - Current thread is not on the active queue");
346 // Don't sleep if there is a message waiting
347 if( gCurrentThread->Messages ) {
348 RELEASE( &giThreadListLock );
352 // Unset remaining timeslices (force a task switch on timer fire)
353 gCurrentThread->Remaining = 0;
355 // Remove from active list
356 thread->Next = gCurrentThread->Next;
358 // Add to Sleeping List (at the top)
359 gCurrentThread->Next = gSleepingThreads;
360 gSleepingThreads = gCurrentThread;
362 // Reduce the active count & ticket count
363 giNumActiveThreads --;
364 giTotalTickets -= gCurrentThread->NumTickets;
366 // Mark thread as sleeping
367 gCurrentThread->Status = THREAD_STAT_SLEEPING;
370 RELEASE( &giThreadListLock );
372 __asm__ __volatile__ ("hlt");
376 * \fn void Thread_Wake( tThread *Thread )
377 * \brief Wakes a sleeping/waiting thread up
379 void Thread_Wake(tThread *Thread)
382 switch(Thread->Status)
384 case THREAD_STAT_ACTIVE: break;
385 case THREAD_STAT_SLEEPING:
386 LOCK( &giThreadListLock );
387 prev = Proc_int_GetPrevThread(&gSleepingThreads, Thread);
388 prev->Next = Thread->Next; // Remove from sleeping queue
389 Thread->Next = gActiveThreads; // Add to active queue
390 gActiveThreads = Thread;
391 Thread->Status = THREAD_STAT_ACTIVE;
392 RELEASE( &giThreadListLock );
394 case THREAD_STAT_WAITING:
395 Warning("Thread_Wake - Waiting threads are not currently supported");
397 case THREAD_STAT_DEAD:
398 Warning("Thread_Wake - Attempt to wake dead thread (%i)", Thread->TID);
401 Warning("Thread_Wake - Unknown process status (%i)\n", Thread->Status);
407 * \fn int Proc_Demote(Uint *Err, int Dest, tRegs *Regs)
408 * \brief Demotes a process to a lower permission level
409 * \param Err Pointer to user's errno
411 int Proc_Demote(Uint *Err, int Dest, tRegs *Regs)
413 int cpl = Regs->cs & 3;
415 if(Dest > 3 || Dest < 0) {
426 // Change the Segment Registers
427 Regs->cs = (((Dest+1)<<4) | Dest) - 8;
428 Regs->ss = ((Dest+1)<<4) | Dest;
429 // Check if the GP Segs are GDT, then change them
430 if(!(Regs->ds & 4)) Regs->ds = ((Dest+1)<<4) | Dest;
431 if(!(Regs->es & 4)) Regs->es = ((Dest+1)<<4) | Dest;
432 if(!(Regs->fs & 4)) Regs->fs = ((Dest+1)<<4) | Dest;
433 if(!(Regs->gs & 4)) Regs->gs = ((Dest+1)<<4) | Dest;
439 * \fn void Proc_SetTickets(int Num)
440 * \brief Sets the 'priority' of a task
442 void Proc_SetTickets(int Num)
445 if(Num > MAX_TICKETS) Num = MAX_TICKETS;
447 Log("Proc_SetTickets: (Num=%i)", Num);
448 Log(" Proc_SetTickets: giTotalTickets = %i", giTotalTickets);
449 LOCK( &giThreadListLock );
450 giTotalTickets -= gCurrentThread->NumTickets;
451 gCurrentThread->NumTickets = Num;
452 giTotalTickets += Num;
453 RELEASE( &giThreadListLock );
454 Log(" Proc_SetTickets: giTotalTickets = %i", giTotalTickets);
455 Log("Proc_SetTickets: RETURN", giTotalTickets);
459 * \fn tThread *Proc_GetThread(Uint TID)
460 * \brief Gets a thread given its TID
462 tThread *Proc_GetThread(Uint TID)
466 // Search Active List
467 for(thread = gActiveThreads;
469 thread = thread->Next)
471 if(thread->TID == TID)
475 // Search Sleeping List
476 for(thread = gSleepingThreads;
478 thread = thread->Next)
480 if(thread->TID == TID)
488 * \fn static tThread *Proc_int_GetPrevThread(tThread *List, tThread *Thread)
489 * \brief Gets the previous entry in a thead linked list
491 static tThread *Proc_int_GetPrevThread(tThread **List, tThread *Thread)
495 if(*List == Thread) {
496 return (tThread*)List;
499 ret->Next && ret->Next != Thread;
502 // Error if the thread is not on the list
503 if(!ret->Next || ret->Next != Thread) {
511 * \fn void Proc_DumpThreads()
513 void Proc_DumpThreads()
517 Log("Active Threads:");
518 for(thread=gActiveThreads;thread;thread=thread->Next)
520 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
521 Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
522 Log(" CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
524 Log("Sleeping Threads:");
525 for(thread=gSleepingThreads;thread;thread=thread->Next)
527 Log(" %i (%i) - %s", thread->TID, thread->TGID, thread->ThreadName);
528 Log(" %i Tickets, Quantum %i", thread->NumTickets, thread->Quantum);
529 Log(" CR3 0x%x, KStack 0x%x", thread->CR3, thread->KernelStack);
534 * \fn void Proc_Scheduler(int CPU)
535 * \brief Swap current task
537 void Proc_Scheduler(int CPU)
543 // Increment Timestamps
545 giTimestamp += MS_PER_TICK_WHOLE;
546 giPartMiliseconds += MS_PER_TICK_FRACT;
547 if(giPartMiliseconds > 0x80000000) {
549 giPartMiliseconds -= 0x80000000;
552 // If the spinlock is set, let it complete
553 if(giThreadListLock) return;
555 // Clear Delete Queue
556 while(gDeleteThreads)
558 thread = gDeleteThreads->Next;
559 if(gDeleteThreads->IsLocked) { // Only free if structure is unused
560 gDeleteThreads->Status = THREAD_STAT_NULL;
561 free( gDeleteThreads );
563 gDeleteThreads = thread;
566 // Check if there is any tasks running
567 if(giNumActiveThreads == 0) {
568 Log("No Active threads, sleeping\n");
569 __asm__ __volatile__ ("hlt");
573 // Reduce remaining quantum
574 if(gCurrentThread->Remaining--) return;
575 // Reset quantum for next call
576 gCurrentThread->Remaining = gCurrentThread->Quantum;
579 __asm__ __volatile__ ("mov %%esp, %0":"=r"(esp));
580 __asm__ __volatile__ ("mov %%ebp, %0":"=r"(ebp));
582 if(eip == SWITCH_MAGIC) return; // Check if a switch happened
584 // Save machine state
585 gCurrentThread->ESP = esp;
586 gCurrentThread->EBP = ebp;
587 gCurrentThread->EIP = eip;
589 // Special case: 1 thread
590 if(giNumActiveThreads == 1)
592 // Check if a switch is needed (NumActive can be 1 after a sleep)
593 if(gActiveThreads == gCurrentThread) return;
595 gCurrentThread = gActiveThreads;
599 // Get the ticket number
600 ticket = number = rand() % giTotalTickets;
602 //Log(" Proc_Scheduler: number = 0x%x\n", number);
604 // Find the next thread
605 for(thread=gActiveThreads;thread;thread=thread->Next)
607 if(thread->NumTickets > number) break;
608 number -= thread->NumTickets;
615 for(thread=gActiveThreads;thread;thread=thread->Next)
616 number += thread->NumTickets;
617 Panic("Bookeeping Failed - giTotalTicketCount (%i) != true count (%i)",
618 giTotalTickets, number);
621 // Set current thread
622 gCurrentThread = thread;
624 // Update Kernel Stack pointer
625 gTSSs[CPU].ESP0 = thread->KernelStack;
629 MM_SetCR3( gCurrentThread->CR3 );
631 __asm__ __volatile__ (
635 "a"(SWITCH_MAGIC), "b"(gCurrentThread->ESP),
636 "d"(gCurrentThread->EBP), "c"(gCurrentThread->EIP));
637 for(;;); // Shouldn't reach here
642 * \brief Pseudo random number generator
643 * \note Unknown effectiveness (made up on the spot)
647 static Uint randomState = RANDOM_SEED;
648 Uint ret = randomState;
649 int roll = randomState & 31;
650 randomState = (randomState << roll) | (randomState >> (32-roll));
651 randomState ^= 0x9A3C5E78;