Task switching & kernel stack questions

[techdude17]

Hi all!

I'm working on adding multitasking to my OS and so far my scheduler is coming along okay, but I'm having problems with understanding a specific concept related to context switching.

So, my scheduler crashes (i386) when the thread list looks like this:

Code: Select all

[Sun Feb 16 15:43:12 2025] [CPU0] [DBG ] [TASK:SCHED] Reschedule thread 0x54e810 to back of queue (owned by 'init')
[Sun Feb 16 15:43:12 2025] [CPU0] [DBG ] [TASK:SCHED] New thread list:
[Sun Feb 16 15:43:12 2025] [CPU0] [DBG ] [TASK:SCHED] Thread 0x54e1c0 - owned by process 'kthread2' (pid 2 prio 2)
[Sun Feb 16 15:43:12 2025] [CPU0] [DBG ] [TASK:SCHED] Thread 0x54df40 - owned by process 'kthread' (pid 1 prio 2)
[Sun Feb 16 15:43:12 2025] [CPU0] [DBG ] [TASK:SCHED] Thread 0x54e810 - owned by process 'init' (pid 0 prio 3)

kthread2 is created and added after kthread. My thread creation code clones the kernel directory (which is what the BSP's current directory is anyways) for each thread and gives it a kstack allocated in that directory. This is an approach I've seen used before and works

However, when I switch to kthread from kthread2, the entire system triple faults - I quickly tracked this down to be because of ESP being no longer valid when switching to kthread's page directory. But this makes total sense - kthread2 had a stack allocated in its page directory AFTER kthread was created.

The weird part is this approach works on x86_64 (targeting both architectures) - it just doesn't care. I'm really confused because I can't find any information for this (or I'm just bad at looking ). Thanks for your help!

[nullplan]

My glass ball is currently in the wash, so I would ask you to provide your source code (possibly as a github link or similar) so we can look at it more thoroughly. However, it seems to me that your stack switching code runs in the wrong context.

Normally, you have the kernel mapped the exact same way in all tasks (with possibly lazy propagation for different cores). The task switcher runs in kernel mode, and it switches CR3 and the return ESP simultaneously. This way, what you're describing becomes impossible. What you are describing sounds like the task switcher is running in the task context.

Or else you are doing what the James Molloy tutorial does with the task stacks, where it uses the same virtual address for all task stacks but different physical addresses. I would try to get as far away as possible from that insanity, but some of what you're describing could be that exact thing.

However, due to my glass ball being in the wash, I can't really say much more.

[techdude17]

Here's the current source code, don't mind the mess while I clean it up - https://github.com/sasdallas/Hexahedron. Tasking code is located in hexahedron/task/whatever.c

I'm definitely not following the James Molloy way of thinking - that's mental insanity. The task switcher doesn't run in task context - it runs in kernel mode. However, each thread has its own kernel stack that is allocated to the thread's page directory - sometimes those kernel stacks just aren't allocated when it comes time to switch to the next thread's page directory.

I thought of a way I could get around this - by loading CR3 in a function where it shouldn't matter (if you're reading the source that's arch_load_context), but while that would've worked I still wanted to understand why it worked on x86_64 and not i386. As well as that, the scheduler code is a massive mess and has some weird bugs in it (if you can spot any stupidity from a glance let me know lol).

[rdos]

The kernel stack should be global and not part of any process context IOW, it must be allocated in global kernel memory.

[techdude17]

Each thread has its own allocated kernel stack in kernel memory. The problem is that the threads created before it have page directories containing clones of the kernel's page directory before that stack was allocated.

[nullplan]

A picture is forming in my brain, but bear in mind that I am currently slightly inebriated.

When you spawn the three kernel threads, you duplicate the page directory for each of them. But you allocate the kernel stacks only one after the other. So the page directory for kthread2 has the mapping for its own stack and the stack of kthread1, but kthread1 doesn't have the mapping for kthread2's stack. Same for kthread3.

So when you switch from kthread2 to kthread1, when you load the page directory of kthread1, the stack of kthread2 becomes unmapped. Principal issue is that your kernel threads are on different page directories at all. They should all be using the same one, since kernel space is all shared and kernel threads have no userspace. Only user tasks need a different page directory (CR3 value).

And as I suspected, you are running the task switcher in task context. Your kernel tasks call process_yield(), which doesn't switch to a kernel context before doing its work. But if you get rid of the different pagedirs for the kernel threads, that problem is no longer a problem.

As for why it "works" on x86_64, I have no idea. Should fail the same way.

[iansjack]

As for why it "works" on x86_64, I have no idea. Should fail the same way.

Just because code appears to work doesn't mean it works. At worst it is failing in ways that haven't yet become apparent.

For example, suppose you have code allocating memory that doesn't allow for the situation when sufficient free memory is not available. That code might appear to work, most of the time, but it doesn't work when it reaches that border case. And it probably fails in a manner that makes it difficult to trace the cause.

[techdude17]

A picture is forming in my brain, but bear in mind that I am currently slightly inebriated.

When you spawn the three kernel threads, you duplicate the page directory for each of them. But you allocate the kernel stacks only one after the other. So the page directory for kthread2 has the mapping for its own stack and the stack of kthread1, but kthread1 doesn't have the mapping for kthread2's stack. Same for kthread3.

So when you switch from kthread2 to kthread1, when you load the page directory of kthread1, the stack of kthread2 becomes unmapped. Principal issue is that your kernel threads are on different page directories at all. They should all be using the same one, since kernel space is all shared and kernel threads have no userspace. Only user tasks need a different page directory (CR3 value).

And as I suspected, you are running the task switcher in task context. Your kernel tasks call process_yield(), which doesn't switch to a kernel context before doing its work. But if you get rid of the different pagedirs for the kernel threads, that problem is no longer a problem.

As for why it "works" on x86_64, I have no idea. Should fail the same way.

Exactly the problem I'm having, but I don't see how getting rid of page directories for kernel threads will resolve the issue (although you are correct and I will use kernel directories in kthreads from now on). The same will happen for normal usermode threads, unless I'm missing something.

EDIT: Ah nevermind, I think I see it - correct me if I'm wrong, but for usermode tasks I should load the kernel's page directory and have their kstacks be mapped there.

[nullplan]

Exactly the problem I'm having, but I don't see how getting rid of page directories for kernel threads will resolve the issue. The same will happen for normal usermode threads, unless I'm missing something.

The very basic issue is that all kernel allocations need to be global. They need to be eventually replicated in all page directories. This is typically accomplished by publishing them in the kernel page dir, which acts as a master copy, and then the page fault handler copies the assignments as necessary. Of course, this means that unmapping kernel pages becomes a pain (need to delete the assignment in all tasks somehow, and need to shoot down the TLB in all cores), which is why doing that is best avoided.

This doesn't help you with kernel thread stacks, though, because with them, an invalid reference will cause the page fault handler to be unable to run.

User mode tasks don't have that problem since they run in user mode, and switch to kernel mode before switching tasks. As long as their kernel stack is mapped in all tasks, no problem happens.

[thewrongchristian]

EDIT: Ah nevermind, I think I see it - correct me if I'm wrong, but for usermode tasks I should load the kernel's page directory and have their kstacks be mapped there.

I wouldn't even worry about user mode tasks for the time being.

Just get your kernel tasks switching reliably. As said by others, while each kernel thread can have it's own kernel directory, the page tables for kernel memory should be shared by all threads, so that when you switch page directories, all your existing mappings can be satisfied from the new page directory, because the actual page tables the directories point to will be the same.

Once you have your kernel task switching and page directory synchronisation code working reliably, then you can think about adding user mode mappings (which will tend not to be shared except by threads within a single process.)

Actually, on that note, threads can actually share page a page directory. So if your thread model is UNIX/Windows like, where the address space is a function of the process rather than the thread, several process threads can use the same page directory (same cr3 value) to work within the same address space as each other. That will also reduce cr3 switching when switching between threads of the same process. In addition, your kernel only threads can be in a kernel process, with it's own page directory, so for your kernel only threads you'll have no address spaces to switch.

The final thing to remember is that unless you used hardware task switching (not advised) you can't actually switch the kernel stack and page directory atomically. So I would recommend something like the following sequence when switching threads:

• Switch register state (GPR, FP regs if required.)
• Check if the threads you're switching from and to are in the same address space.
  • If so, then you're done, you can continue with the existing page directory.
  • If not, then you need to synchronize the page directory of the thread you're switching to (to pull in any new page table additions since this page directory was last mapped) then load the new page directory.

[rdos]

The very basic issue is that all kernel allocations need to be global. They need to be eventually replicated in all page directories. This is typically accomplished by publishing them in the kernel page dir, which acts as a master copy, and then the page fault handler copies the assignments as necessary. Of course, this means that unmapping kernel pages becomes a pain (need to delete the assignment in all tasks somehow, and need to shoot down the TLB in all cores), which is why doing that is best avoided.

Exactly. However, to simplify "unmapping", I don't do this and instead keep them mapped. The sharing of kernel pages operates at the page directory entry level, and so the issue is with sharing page directory entries, and not sharing individual pages which are updated automatically since they share page directory entries. The issue instead is that newly allocated page directory entries need to be remembered in a master copy, and be copied to new processes where they are not mapped rather than allocating a new entry. It's the page directory entries in kernel space that never are freed because it's too complicated, and they are likely needed again if they are freed.

[techdude17]

I see. I actually came to that conclusion myself, for copying PDEs with their frames - I do like nullplan's idea of using the page fault handler too, maybe there's some middle ground.

Thank you for your help! I'll be sure to implement this.