OSDev.org

OSwhatever wrote:The traditional way of doing things is that you allocate the kernel stack during thread creation and let that thread have that stack through its entire life. However, since the trip in the kernel is always supposed to be short vacation from the ordinary user life without any memory of the last trips, the kernel stack can be assigned when the thread enters the kernel and also be reused.

OSwhatever wrote:The thread doesn't care which kernel stack it uses. This might reduce some memory usage but another things comes to mind is user mode scheduling. The problem with user mode threads that the kernel has no idea about the threads and there are no kernel stacks associated with them. With dynamic kernel stack allocation the kernel doesn't care how many threads visits the kernel and just gives them a kernel stack upon entry, this would also solve user mode thread kernel call parallelism. Why isn't this method more widely used? Are there any drawbacks I'm not aware of?

I've been thinking about this for a while. You'd need one kernel stack per CPU (and could pre-allocate them rather than dynamically allocate them). On kernel entry you'd save the user state and on kernel exit you'd restore the user state. When something happens that causes a task switch, the kernel only changes a "return task ID" value, so that it restores a different task's state when it returns to user space.

gerryg400 wrote:

I've been thinking about this for a while. You'd need one kernel stack per CPU (and could pre-allocate them rather than dynamically allocate them). On kernel entry you'd save the user state and on kernel exit you'd restore the user state. When something happens that causes a task switch, the kernel only changes a "return task ID" value, so that it restores a different task's state when it returns to user space.

This works well and is very easy to implement if your kernel design doesn't allow threads to sleep (i.e. no IO waiting in the kernel) and doesn't allow threads in kernel mode to be pre-empted. Many microkernels don't need IO wait because that sort of thing happens in userspace.

    if(currentTask != returnTask) {
        while(returnTask == UNKNOWN) {
            returnTask = scheduler_findTask();
            if(returnTask = UNKNOWN) {
                put_CPU_into_sleep_state();
            }
        }
        if(currentTask != UNKNOWN) {
           /* For "on demand" FPU/MMX/SSE state loading using the "device not available" exception */
            save_FPU_MMX_SSE_state(currentTask);
            set_FPU_MMX_SSE_state_owner(UNKNOWN);
        }
        currentTask = returnTask;
    }
    loadState(currentTask);
    return to user space

gerryg400 wrote:But almost all kernels have at least some long system calls and will need some sort of kernel pre-emption.

gerryg400 wrote:BTW, I think I misunderstood OSwhatever's original point. I thought that by "Dynamic kernel stack allocation" he meant allocating kernel stacks as required using kmalloc.

Brendan wrote:Worst case for a micro-kernel is creating a new process - creating some sort of "process info" structure, creating a new virtual address space and creating an initial thread for the process. I think I can do it fast enough, given that I don't do "fork()" (and don't need to clone an existing address space or setup "copy on write") and that the "process loader" (e.g. code to parse command line arguments, build environment strings, parse executable headers, load the executable, etc) would be running in user space.

gerryg400 wrote:

Brendan wrote:Worst case for a micro-kernel is creating a new process - creating some sort of "process info" structure, creating a new virtual address space and creating an initial thread for the process. I think I can do it fast enough, given that I don't do "fork()" (and don't need to clone an existing address space or setup "copy on write") and that the "process loader" (e.g. code to parse command line arguments, build environment strings, parse executable headers, load the executable, etc) would be running in user space.

True, most of that stuff is quick or can be done by the new process itself.

But aren't the longest kernel calls process_destroy(), mailbox_destroy etc. where you need to tear down and dispose of all the accumulated stuff that is linked to the process or mailbox ?

gerryg400 wrote:I've been trying to find nice ways to pre-empt this sort of stuff. I'm currently playing around with an idea where, when a process is deleted it's just marked as deleted (which hides all it's resources) and tearing it down as time permits. I really only want one kstack per core. You're correct with 10's of thousands of threads it just burns too much memory. Oh and currently my kernel stacks are fully-commited (with phys-mem allocated) kernel memory and that's not an unlimited resource. If your kernel stacks are virtual memory or are swappable then perhaps that's not so bad.

I've been thinking about this for a while. You'd need one kernel stack per CPU (and could pre-allocate them rather than dynamically allocate them).... etc.

Brendan wrote:For disadvantages; it will make simple kernel API services (where very little state actually needed to be saved/restored) slower; partly because user state would have to be stored in some sort of "thread info structure" and not on the kernel stack, and you'd need to shift some things that the CPU puts on the stack (e.g. return SS:ESP and return SS:EIP would need to be shifted to/from the "thread info structure"). The other disadvantage is that you couldn't have "kernel threads" with this method; and I like having kernel threads (mostly for cleaning up various pieces of kernel data in idle time).

n theory user space threads have less overhead because the cost of switching to/from CPL=0 is avoided sometimes. In practice this overhead is negligible (around 30 cycles, depending on a wide variety of things). The problem with user space threads is that it's impossible to have "global thread priorities". Each process doesn't know if there's higher priority threads in other processes that should be running instead of its own threads; and the kernel doesn't know the priority of any user space threads (and isn't doing most of the scheduling anyway); so you end up executing less important threads when you should be executing more important threads. This can make the OS feel slow/sluggish - e.g. one application wasting time calculating the first million prime numbers while the user is sitting there waiting for another application to respond to a keypress. If you have a look at some of the performance numbers for various OSs, you'll see that OSs with very slow "kernel task switching" (e.g. Windows) tend to benefit from things like fibres, while for better OSs (with fast "kernel task switching", like Linux) it's not worth bothering with. Basically, user space threads are only good when the kernel is crappy, and I'd suggest writing a kernel that isn't crappy instead of bothering with user space threads.

FlashBurn wrote:I also like the idea of having just one kernelstack per core, but I don´t like the idea that my kernel is not preemptive.

Just imagine you have lots of cores and all threads on these cores go into the kernel the same time and all want the the lock. So you either use a mutex/semaphore and need to save the cpu state (because you can´t just push all regs to the stack) or you use a spinlock and this can then take some time for all cpus to get it.

FlashBurn wrote:I also like the idea of having just one kernelstack per core, but I don´t like the idea that my kernel is not preemptive.

Just imagine you have lots of cores and all threads on these cores go into the kernel the same time and all want the the lock. So you either use a mutex/semaphore and need to save the cpu state (because you can´t just push all regs to the stack) or you use a spinlock and this can then take some time for all cpus to get it.

gerryg400 wrote:

I've been thinking about this for a while. You'd need one kernel stack per CPU (and could pre-allocate them rather than dynamically allocate them).... etc.

Brendan, have you actually decided to go this way or are you still thinking about it ? I've decided. It's one kstack per core for me.

OSwhatever wrote:I was thinking that you simply use a lock less stack storing stack candidates, if the stack is empty you allocate a new stack from the kernel heap. Upon kernel entry you pluck a kernel stack from the lock stack and push it back it when leaving. This will be more code for a system call but still feasible performance wise I think. If the the thread is preempted in the kernel it simply keeps the kernel stack during the time it is blocked.

FlashBurn wrote:I also like the idea of having just one kernelstack per core, but I don´t like the idea that my kernel is not preemptive.

OSwhatever wrote:The "global kernel lock" was something that was ridiculed in the earlier days of Linux. I'm not sure if you can seriously sell a non re-entrant kernel today. With the current multicore trend it really motivates it even more.

• functions that are so simple that they can be completed without acquiring any lock (including things like "get_process_ID()" and things that can be done with lock-free or wait-free code). These are typically so fast that nobody cares anyway.
• functions that acquire one or more locks at the same time (where in practice "fully pre-emptable" is very similar to "no pre-emption" anyway)
• functions that are lengthy/expensive (e.g. creating and destroying processes). In previous kernels I've been especially careful and split these up into pieces to ensure that there's "gaps" where no locks are held (and pre-emption can occur). I've even deliberately released a lock and then acquired the exact same lock immediately after releasing it in a few places. For "no pre-emption" you'd do the same thing - split lengthy/expensive operations into pieces (you just split things in a different way - e.g. explicit "pre-emption points" or some sort of "kernel helper" in user space).