Software task switching and priviledge levels

[tom1000000]

Hello,

I am wondering how stack based task switching works when some of the threads run at CPL 0 (kernel process) and some of the threads obviously are at CPL 3.

Basically for a user-mode thread the stack looks like this:

| | User mode stack
| |
| | <- ESP before switch

ESP0 stack (based on TSS):

| SS3 | (saved values of user mode stack)
| ESP3 |
| EFLG |
| CS3 |
| EIP3 | (user mode CS and EIP)
(esp now points to TSS stack, not user mode stack)

However, a kernel thread has a different layout because there is no priviledge level change. It is simply:

| EFLG |
| CS0 |
| EIP0 | (kernel mode CS and EIP)
(esp remains on kernel mode stack)


If a kernel thread calls INT y (which is the yield system call) how do I make the IRET return to a user mode (CPL3) thread?.

And if a user mode thread calls INT y, how do I make it IRET to a CPL0 thread?

Do I have to write a whole lot of complicated code to determine the calling CPL, the return CPL, and mangle the stack appropriately? Is there a more elegant way?

[Pype.Clicker]

Hello,

Do I have to write a whole lot of complicated code to determine the calling CPL, the return CPL, and mangle the stack appropriately? Is there a more elegant way?

No: there is no need for such complicated actions. When you will perform the stack switch (i.e. loading SS and ESP with values stored in the thread structure), the processor will now be in the proper mode to return to the procedure that called the switch in that thread.

For instance, if you have a user-mode program that is interrupted by IRQ0, it will create a level-switch stack frame on its own kernel-mode stack.
If you now switch to a kernel thread that had been suspended voluntarily (i.e. calling "threadSleep()"), you enter a stack that has a intra-level switch, and when returning/unpopping on that stack, you will just restore the kernel thread at the point following threadSleep().

[Pype.Clicker]

MegaT0ky0$ su
'super-user mode passw0rd: *******
MegaT0ky0# merge threads
' merging . . . . [done]

Hi, could someone explain the best method of software task switching.

I think my method is not the best, and it causes all sorts of problems when some threads are CPL0 and some are CPL3.

My intended method was something like this:

- IRQ occurs - privilege level switch
- pushad to save current thread on stack


then stack looks like this:

| | User mode stack
| |
| | <- ESP before switch

ESP0 stack (based on TSS):

| SS3 | (saved values of user mode stack)
| ESP3 |
| EFLAGS |
| CS3 |
| EIP3 | (user mode CS and EIP)
| PUSHAD | - all the registers

(esp now points to TSS stack, not user mode stack)

then:

- copy thread info into current thread structure
- choose new thread
- copy info from new thread's structure onto stack
- IRET


Is there a better way of doing software task switching?

yes, there is! almost all of your thread's status can be kept on the thread's stack :p just pick up the ESP and SS values and copy them into the thread structure, instead of copying everything.

if you have one single segment for every thread kernel tasks (which i do not recommend, personnally), it becomes

Code: Select all

{
  thread next=scheduler.next();
  if (next!=curr) {
     disable_interrupts();
     push_all_status();
     curr.esp=%esp;
     curr.cr3 =%cr3;
     if (curr.cr3!=next.cr3) %cr3=next.cr3;
     %esp=next.esp;
     pop_all_status();
     enable_interrupts();
  }
}

[tom1000000]

Hi,

Thanks for your help and sorry for my stupidity but could you explain in a bit more detail?

Eg you say that I should copy only SS and ESP into the thread's structure. Well which SS/ESP, SS3/ESP3 (which is placed on the stack) or SS0/ESP0, which originates from the TSS.

If I was to copy SS0/ESP0 into the thread structure, I don't see how it would work as there is only 1 TSS (on uniprocessor system) so all threads share the same SS0/ESP0 stack.

Also, how do you keep the thread registers on the threads stack, as when an interrupt occurs you are automatically transferred to the TSS ESP0 stack?

Also you said "one single segment for every thread kernel task". What exactly did you mean by "segment". Where you referring to the SS segment register? The stack? Something else?

I guess there is a PUSHAD somewhere, but when an IRQ occurs you don't have direct access to the thread's stack.

I have gotten myself rather confused on this. Hopefully when I finally get this sorted and move onto the FPU FXSAVE / FXRSTOR should be a piece of cake.

[Pype.Clicker]

Hi,

Thanks for your help and sorry for my stupidity but could you explain in a bit more detail?

Eg you say that I should copy only SS and ESP into the thread's structure. Well which SS/ESP, SS3/ESP3 (which is placed on the stack) or SS0/ESP0, which originates from the TSS.

If I was to copy SS0/ESP0 into the thread structure, I don't see how it would work as there is only 1 TSS (on uniprocessor system) so all threads share the same SS0/ESP0 stack.

I was talking about SS/ESP. The SS0/ESP0 should also be preseverd, but it can be stored on the stack and restored once the new stack has been set up, with the others registers content (eax, edx ...)

-- a small thing that i forgot to mention - shame on me --
another thing is that your thread structure will always have a link to a kernel mode stack, because only kernel mode can perform a stack switch.

Also, how do you keep the thread registers on the threads stack, as when an interrupt occurs you are automatically transferred to the TSS ESP0 stack?

but the trick is every thread has its own kernel stack space, so if thread A receives an interrupt (which implies the thread A is running and thus that it doesn't have to store registers anywhere but in the processor), the previous kernel stack content will indeed be erased, but this doesn't affect thread B's stack (which is used to hold thread B's state as long as B sleeps)

Also you said "one single segment for every thread kernel task". What exactly did you mean by "segment". Where you referring to the SS segment register? The stack? Something else?

I was indeed referring to the "kernel stack" .... just a typo from me. It is not really a wise idea to do so (imho) as it implies that you have no strong protection against kernel-mode stack overflows, and that can make your kernel hard to debug ...

[tom1000000]

Hi, thanks for your help.

So my design was all wrong. Each thread should have its own CPL0 stack.

Does this mean each context switch I have to modify the TSS's ESP0 value?

What size should each thread's stack be? Should each thread's CPL0 stack be 1 page (4K)? What about the CPL3 stack?

Thanks again.

[Pype.Clicker]

giving every thread its own DPL0 stack really helps, indeed. But i never checked it was completely mandatory.

the kernel stack should be 'as big as the longest system call chain can be' ... in other words, try to keep its size determinable (don't allocate variable-size structures on it, etc.)

The user stack may be expanded automatically by the kernel when a overflow is detected, kernel stack can't (as you need the kernel stack to handle the fault)...

BTW, i recommend the use of a separate segment for each kernel stack, so that a kernel stack overflow can be caught by the #StackFault exception (which should be a task gate, as stated in Intel Manuals) and can be recovered gracefully rather than letting kernel threads overwriting each others or damaging kernel data structures ...

[tom1000000]

Hi,

One last question!

If threads from the same process share the same address space (same page tables), then do they all have stacks at different addresses?

If they had stacks at the same address, would you have to mangle the page tables (change physical mapping), even if only changing between threads of the same process????

Thanks

[Pype.Clicker]

threads from the same process have different stacks located at different addresses (for instance, thread A would have a stack at 0x80000000 .. 0x8FFFFFFF, thread B at 0x90000000 .. 0x9FFFFFFF, et c.)
the maximal size of those stack must be defined at thread creation (in most programming models), and they should not overlap.

You cannot just say that you're going to make thread A's stack disappear and being replaced through paging tricks by thread B's stack, because two threads of the same process expect they can share *all* their memory space, including variables that are located on their own stack ...

Well, in fact, you can, but it wouldn't be multi-threading anymore, it would be ... something else, looking like lightweight multi-processing, and it would also mean that you couldn't have several tomthreads running from the same process simultaneously even if the system has several processors ...

[distantvoices]

What are tomthreads? *rofl*

aren't threads light weight processes sharing the adress space/code/data of one process - except their stacks and some book keeping structures?

[Pype.Clicker]

true, threads have separate stacks, but all can see every other thread's stack, which means (even if it might not be good practice) that thread A could have data on its "private" stack and publish (in a well-known global pointers) the address of these data for another thread to read or write into it.

With tomthreads (i.e. threads as Tom propose them), you cannot do this because thread A cannot see any other thread's stack ...

Maybe it's more a solution than a problem, though. A more problematic issue is that you'll have to flush all the Translation Lookaside Buffer entries for the stack pages - so your thread switch becomes roughly as expensive as a process switch ...

[tom1000000]

Hi,

Another question for you!


If multiple threads have different stacks, how exactly do ELF (and other binary formats) work?

I was under the impression that ELF programs had region x allocated for the text (code), region y for the heap and region z for the stack.

So what happens when there are multiple stacks?

I suppose you could just carve up the virtual address range allocated to the stack. But then you don't know exactly how many threads are going to be created so that option does not seem practical.

Tom

[Pype.Clicker]

roughly, additionnal threads allocate their stack on the heap ... until you reprogram the '&' operator of C so that references to the stack are handled in a special fashion, you can't do anything better ...