Extremely simple multitask

[korangar]

Hi everybody

I've been working on an extremely simple multitasking kernel, mainly to understand, explain and play with basic concepts and I have a very specific question on how to improve multitasking upon blocking syscalls.

Extremely simple means:

• 2 binaries: kernel and user. The only mechanism to interact is syscalls (int 0x80)
• No memory protection, flat memory model
• Everything runs on ring 0
• Just 1 core
• No special registers (-mgeneral-regs-only)
• Handles the timer, the keyboard and syscalls
• No file system
• Process creations takes just a pointer to a function in the user binary. They are more like threads since they share the address space :p
• No kernel stacks
• Scheduler preemptive RR, no priorities
• The same memory manager is used for kernel and user (for example, one that alloc fixed size chunks)

Other characteristics are:

• The linker output format is binary
• Arch: x86_64 (I know... it's like using a Ferrari to go grocery shopping)
• Bootloader: Pure64

To ask the question let me show you some code. This is the handler of the timer (18 Hz and switches processes every time it interrupts)

Code: Select all

_timerHandler:
  pushState ; pushes r8-r15 rsi rdi rbp rdx rcx rbx rax

  mov rdi, rsp
  call sched ; Just returns rsp of the next ready process
  mov rsp, rax

  ; Send EOI - omitted for this post
  
  popState
  iretq

The handler of the syscalls is similar. It saves all registers (I know it's not necessary to save all of them), except rax.

Code: Select all

_syscallHandler:
  pushStateNoRax ; Same as before, except rax

  call syscallDispatcher
  
  popStateNoRax
  iretq

Now, let's consider the simplest syscall that implies preemption: yield. This syscall essentially enable interrupts (sti) and waits (hlt) for the next timer interrupt. After this interrupt, the stack of this process looks like this:

Code: Select all

|         ...        |
| CS:IP RFLAGS SS:SP | <- int 0x80
|   pushStateNoRax   | <- _syscallHandler
|   ret addr / vars  | <- return addresses and local vars from syscallDispatcher, yield, etc
| CS:IP RFLAGS SS:SP | <- timer interrupt
|      pushState     | <- _timerHandler

Soon, this process will be chosen by the scheduler in _timerHandler. popState and iretq will restore process A to the point immediately after hlt:

Code: Select all

|         ...        |
| CS:IP RFLAGS SS:SP | <- int 0x80
|   pushStateNoRax   | <- _syscallHandler
|   ret addr / vars  | <- return addresses and local vars from syscallDispatcher, yield, etc

Then returns from the syscall yield

Code: Select all

|         ...        |
| CS:IP RFLAGS SS:SP | <- int 0x80
|   pushStateNoRax   | <- _syscallHandler

And _syscallHandler does the trick

Code: Select all

|         ...        |

Nothing happened.

This works but I don't want to wait for an interrupt to continue with the next process, besides an interrupt is costly. Forcing the same interrupt by software (int 0x20) is not completely correct since it would send the EOI for a non HW generated interrupt. Instead, I'd like to switch tasks with a function, however the stack of this process, when it's running inside yield, does not look like the stack of a process preempted by the timer. We have return addresses and local variables.

I don't understand how a kernel stack for each process would help with this scenario. (If it really does)

Is there any alternative? Opinions?

Thanks!

[Octocontrabass]

I don't understand how a kernel stack for each process would help with this scenario. (If it really does)

You already have a kernel stack for each process. Everything runs in ring 0, so every stack is a kernel stack.

Is there any alternative? Opinions?

Instead of having a sched() function that returns the stack pointer of the new task, have a function that switches to the new task's stack directly. That way, it won't return to the caller until the caller is scheduled to run again. Since it only returns when the caller is ready to run, it doesn't matter if different callers have different stack layouts. There's a pretty good example of this on the wiki.

In an interrupt handler, you'll have to make sure you send the EOI before you call the stack switching function, otherwise the EOI won't get sent until the next time the caller is scheduled to run.

[rdos]

I think the best approach is to have two scheduler functions: SaveState and LoadState. When a thread calls yield, or is preeempted in an IRQ, it will call SaveState. After this the scheduler picks a new thread and calls LoadState to execute the next thread. A thread should never try to directly switch to a different thread as this is the job of the scheduler.

Blocking a thread is done by putting it in some blocked list and then calling SaveState to switch to the scheduler. When another thread wants to unblock a thread, it removes it from the blocked list and puts it in the ready list, and if it has higher priority, it will call SaveState to let the scheduler execute it.

Thread state will typically be saved and loaded from a thread control block. What needs to be saved can differ, but I save all processor registers in the thread control block since my design is segmented and has a lot of assembly code that cannot be interrupted and resumed without saving all registers. The advantage of saving registers in a thread control block rather than on the stack is that it is easier to access from debuggers. I unwind exceptions too so the faulting instruction is in the thread state, not an exception frame. This can be used for single-stepping code in a kernel debugger too. Having thread state on different stack layouts makes it hard to decide what a blocked thread is doing.