[SOLVED] How do I switch between kernel threads?

[peachsmith]

As part of implementing multitasking, I'm trying to alternate between two constantly running kernel threads called task_a and task_b.
I'm attempting to do software task switching preemptively initiated by the PIT through my IRQ0 handler.

I can call each thread's function, but then I get a page fault when I attempt to swap the register values.
How can I repopulate the registers such that execution resumes in a different thread where it last left off?
Am I leaving out some registers when swapping? Should I be swapping the segment registers?
Every example I can find seems to have a different idea of which registers to switch.




Here is an outline of my thread-switching plan:

I've given each of these tasks a single 4KiB page from the same virtual address space to use as a stack.
I've assigned their esp and ebp values to the "bottom" (highest address) of their respective stacks.

The flow of my task switching logic is as follows:
1. IRQ0 occurs, enter assembly procedure irq_0, push GPRs, push eflags, then call the C function irq_0_handler
2. In irq_0_handler, call the C function k_switch_task to perform task switching logic
3. In k_switch_task, save the current register values and choose the next task
4. If the next task is not yet started, set esp and ebp, enable interrupts, and call its start function. This should not return.
5. If the next task is already running, load its register values into the registers and jump back to the irq0 assembly procedure to do an iret.


Here's a sort of flow chart:

Code: Select all

irq0 --> irq_0_handler --> k_switch_task --> start_kthread
                                        |
                                        |--> swap_kthread_regs --> ir0 --> iret (page fault somewhere in here)

Here is my IRQ0 handling assembly procedure:

Code: Select all

.global resume_irq0 # allow register swapper proc to jump back to irq0

irq_0:
	pushal
	pushfl
	call irq_0_handler
	popfl
	popal
resume_irq0:
	iret

Here is my irq_0_handler C function:

Code: Select all

void irq_0_handler(
	uint32_t eflags,
	uint32_t edi,
	uint32_t esi,
	uint32_t ebp,
	uint32_t esp,
	uint32_t ebx,
	uint32_t edx,
	uint32_t ecx,
	uint32_t eax
)
{
	if (ticks > 0)
		ticks--;

	main_ticks++;

	// Send the EOI before doing task switch logic
	// since we don't normally return from a task switch.
	k_outb(0x20, 0x20);

	// Here is where we initiate a task switch
	if (main_ticks % 2000 == 0)
	{
		k_switch_task(eflags,
			edi,
			esi,
			ebp,
			esp,
			ebx,
			edx,
			ecx,
			eax);
	}
}

This is my task switching logic:

Code: Select all

void k_switch_task(uint32_t eflags,
	uint32_t edi,
	uint32_t esi,
	uint32_t ebp,
	uint32_t esp,
	uint32_t ebx,
	uint32_t edx,
	uint32_t ecx,
	uint32_t eax)
{
    // If there is no current task,
    // then tasking has not yet been initialized.
    if (current_task == NULL)
        return;
        
    // Update the stored CPU state of the current task.
    current_task->eflags = eflags;
    current_task->edi = edi;
    current_task->esi = esi;
    current_task->ebp = ebp;
    current_task->esp = esp;
    current_task->ebx = ebx;
    current_task->edx = edx;
    current_task->ecx = ecx;
    current_task->eax = eax;

    // Alternate between task a and task b.
    switch (current_task->id)
    {
        case 2:
            current_task = &task_b;
            break;

        case 1:
        case 3:
            current_task = &task_a;
            break;

        default:
            break;
    }

    // If the current task is new, start it.
    if (current_task->status == TASK_NEW)
    {
        current_task->status = TASK_RUNNING;

        start_kthread(
            current_task->esp,
            current_task->ebp,
            current_task->start
        );

        return;
    }

    // Swap the registers. (jumps to irq0)
    swap_kthread_regs(
        current_task->eflags,
        current_task->edi,
        current_task->esi,
        current_task->ebp,
        current_task->esp,
        current_task->ebx,
        current_task->edx,
        current_task->ecx,
        current_task->eax
    );
}

Here is how I'm starting my threads:

Code: Select all

# Starts a kernel thread.
# Updates esp and ebp, then calls the start function.
#
# Params:
#   8(%ebp)  - the new esp value
#   12(%ebp) - the new ebp value
#   16(%ebp) - the address of the starting function
#
start_kthread:
    
    pushl %ebp
    movl %esp, %ebp
    subl $8, %esp

    movl 8(%ebp), %eax
    movl %eax, -4(%ebp)  # temporarily store esp

    movl 12(%ebp), %eax
    movl %eax, -8(%ebp)  # temporarily store ebp

    movl 16(%ebp), %ecx  # put the address of the start function in ecx

    movl -4(%ebp), %esp  # update esp
    movl -8(%ebp), %ebp  # update ebp

    sti                  # enable interrupts
    call *%ecx           # call the start function
    
    leave
    ret

Here is how I'm loading the registers:

Code: Select all

# Populates the registers with the values from the next task.
# This procedure is only called while handling IRQ0, so after
# loading the register values, it jumps to IRQ0.
#
# Params:
#   8(%ebp)  - eflags
#   12(%ebp) - edi
#   16(%ebp) - esi
#   20(%ebp) - ebp
#   24(%ebp) - esp
#   28(%ebp) - ebx
#   32(%ebp) - edx
#   36(%ebp) - ecx
#   40(%ebp) - eax
#
swap_kthread_regs:

	 movl %esp, %ebp
    subl $12, %esp

    movl 8(%ebp), %eax
    movl %eax, -4(%ebp)  # temporarily store eflags

    movl 20(%ebp), %eax
    movl %eax, -8(%ebp)  # temporarily store ebp

    movl 24(%ebp), %eax
    movl %eax, -12(%ebp) # temporarily store esp

    movl 12(%ebp), %edi  # update edi
    movl 16(%ebp), %esi  # update esi

    movl 28(%ebp), %ebx  # update ebx
    movl 32(%ebp), %edx  # update edx
    movl 36(%ebp), %ecx  # update ecx
    movl 40(%ebp), %eax  # update eax

    pushl -4(%ebp)
    popfl                # update eflags

    movl -12(%ebp), %esp # update esp
    movl -8(%ebp), %ebp  # update ebp

    jmp resume_irq0      # resume IRQ0

And here are the two thread functions that I'm trying to switch between:
task_a:

Code: Select all

void task_a_action()
{
    for(;;)
    {
        printf("This is task a.\n");
    }
}

task_b:

Code: Select all

void task_b_action()
{
    for(;;)
    {
        printf("This is task b.\n");
    }
}

[pvc]

Thread switching is very delicate (can easily break) thing to do. You, most likely, won't get anywhere without carefully debugging it instruction by instruction. The easiest way to do task switching would be just changing the stack pointer (ESP on x86). You can do that by using return value of your irq_0_handler as stack pointer to be loaded before returning from interrupt (add something like MOV ESP, EAX [intel syntax] after call irq_0_handler). You don't have to worry about any other general purpose registers since they are saved when entering interrupt service routine (your irq_0) by PUSHAL instruction and restored by POPAL, but from different threads stack (if you in fact changed ESP). Also that PUSHFL/POPFL pair is not necessary. CPU saves EFLAGS on ISR entry automatically and restores it when executing IRET instruction. The only complication of stack swapping is that you need to create fake interrupt stack frame for every new thread. And that stack frame MUST exactly match what's in your ISR.

[max]

In my kernel, I just fire int 0x81 when I want to yield. My standard interrupt routine is then called (see also the comments) which means that some registers are just not pushed during that switch. The rest works like for a ring 3 task switch.

[peachsmith]

Thanks.
I temporarily changed my irq_0_handler to return a pointer to the next task.
I also reconstructed the ISR stack before iret and it seems to be updating eip and ebp correctly, but I can't seem to update esp.
Since popa ignored the value of esp on the stack, I tried to manually update it, but it gives me a general protection fault.
Am I just not setting esp in the right place?

Here's my updated ISR entry for IRQ0:

Code: Select all

irq_0:

	pushal
	call irq_0_handler

	cmp $0, %eax      # check if there has been a task switch
	jz end_irq_0      # if there was no task switch, jump to the end

	addl $44, %esp    # discard the old registers

	# push the new registers onto the stack

	pushl 36(%eax)    # save esp for updating later

	pushl 8(%eax)     # eflags
	pushl 12(%eax)    # cs
	pushl 16(%eax)    # eip
	pushl 20(%eax)    # eax
	pushl 24(%eax)    # ecx
	pushl 28(%eax)    # edx
	pushl 32(%eax)    # ebx
	pushl 36(%eax)    # esp
	pushl 40(%eax)    # ebp
	pushl 44(%eax)    # esi
	pushl 48(%eax)    # edi

	popal
	popl %esp         # update esp using the value we stored earlier (I get a general protection fault if I do this)
	jmp end_task_switch

end_irq_0:
	popal
	
end_task_switch:
	iret

[max]

That code seems a little fishy to me. So you are pushing general purpose registers with pushal. Call your irq handler, then why do you start with discarding registers from that new stack?

The usual way for ring0<->ring0 would be this:

• When an interrupt happens, the CPU pushes eflags, cs, eip automatically on the current stack
• Then you push all remaining registers onto the current stack
• Switch the stack to the next tasks stack (which must already contain all the registers)
• Pop all registers from that other stack
• Call iret, which causes the CPU to pop eip, cs and eflags again

You very probably get that general protection fault during the iret. No need to do any fancy eax calculations there, just mov esp, eax to the place you get from your interrupt handler. Your tasking code is then responsible for setting up the stack correctly so the first switch into a new task works.

[peachsmith]

So I removed that goofy eax comparison logic, and just moved the return value of my irq_0_handler C function into esp and eventually got it to work.

However, since pusha pushes the value of esp before its execution onto the stack, I needed to store an esp value that included the pushed register values in my TCB.
So after pushing the GPRs, I pushed esp and stored that value in my TCB like so:

Code: Select all

irq_0:

	pushal             # Store GPRs on the stack. This pushes the value of esp before pusha was executed.
	pushl %esp         # Store value of esp after pushing GPRs.
	call irq_0_handler
	movl %eax, %esp    # Update esp to point to the stack of the next task.
	popal              # Retrieve the GPR values of the next task.
	iret

Alternatively, when I call my irq_0_handler C function, I can just set esp to the value pushed by pusha - 32, where 32 is an offset to account for 8, 4-byte registers being pushed onto the stack.
However, with this offset approach, I would need to change the offset if I wanted to save more information on the stack.

[Octocontrabass]

I don't think anyone else mentioned it, but the System V ABI allows functions to overwrite parameters passed by value. This means all the GPRs you pass to your irq_0_handler function can be overwritten by the compiler, leading to some very frustrating debugging.

The fix is to instead pass a pointer to the values on the stack (for example, by doing "pushl %esp") and changing the function signature to accept only that one pointer as a parameter. The compiler may clobber the pointer, but not the data it points to.

[peachsmith]

This means all the GPRs you pass to your irq_0_handler function can be overwritten by the compiler

I've heard elsewhere that it's better to pass a pointer to a struct with register data, but maybe I'm misunderstanding this.
So you're telling me that if I have the following C function, and I pass it the value 4 on the stack, I can't reliably expect the actual value 4 to be stored?

Code: Select all

// C function
void store_value(uint32_t val)
{
    data_storage->x = val;
}

# Assembly procedure (prologue and epilogue omitted)
abi_test:
    movl $4, %eax
    pushl %eax
    call store_value

[Octocontrabass]

So you're telling me that if I have the following C function, and I pass it the value 4 on the stack, I can't reliably expect the actual value 4 to be stored?

No, I'm saying you can't reliably expect to pop the value 4 off the stack after calling the function.

[peachsmith]

Ok, what I'm trying to do at this point is ensure that the stack contains the GPR values of the next task on top of the ISR stack value of the next task.
So would it be better to return a pointer to my TCB and then push its values onto the stack?

It tried this, and it seemed to work. Though I have to currently assume a task switch with no CPL change. (but I don't have userland yet, so that's not a problem yet)

Code: Select all

irq_0:

	pushal
	call irq_0_handler

	# Update the esp
	movl 36(%eax), %esp

	# Rebuild the ISR stack (assumes no CPL change)
	addl $12, %esp
	pushl 8(%eax)  # eflags
	pushl 12(%eax) # cs
	pushl 16(%eax) # eip

	# push the GPRs from the next task onto the stack
	pushl 20(%eax) # eax
	pushl 24(%eax) # ecx
	pushl 28(%eax) # edx
	pushl 32(%eax) # ebx
	pushl 36(%eax) # esp
	pushl 40(%eax) # ebp
	pushl 44(%eax) # esi
	pushl 48(%eax) # edi

	popal
	iret

[Octocontrabass]

So would it be better to return a pointer to my TCB and then push its values onto the stack?

Do you need to? If you have one stack per thread, then you only need to switch stacks (by updating ESP) somewhere between PUSHA and POPA and the new stack will already have the correct values on it.

Starting a new task is then accomplished by allocating a new stack and pre-filling it with the appropriate values to "return" to the start of the new task.

(If you don't have one stack per thread, it's still possible to do task switches, but I'm not really clear on how that's supposed to work or what benefits there may be from doing things that way.)

[max]

So you're telling me that if I have the following C function, and I pass it the value 4 on the stack, I can't reliably expect the actual value 4 to be stored?

No, I'm saying you can't reliably expect to pop the value 4 off the stack after calling the function.

He doesn't try to, he sets the return value in eax as the new stack pointer and then pops off the new stack so that's fine.

[Octocontrabass]

My concern is mostly with this function:

Code: Select all

void irq_0_handler(
	uint32_t eflags,
	uint32_t edi,
	uint32_t esi,
	uint32_t ebp,
	uint32_t esp,
	uint32_t ebx,
	uint32_t edx,
	uint32_t ecx,
	uint32_t eax
)

The caller can't assume any of those parameters will retain their previous values after the function returns.

[peachsmith]

Ok, so after looking at max's Ghost OS code, it looks like I'm doing something similar, but I'm passing each of my register values as separate parameters, while he is passing esp and casting it to a pointer to a register struct.

Both of our approaches rely on storing the register values and esp in a structure and returning the esp of the next task.
We both rely on the following flow:

Code: Select all

pusha          # push some registers onto the stack (max pushes individual registers and does some segment switching, I just pusha for now)
push esp       # push the latest esp value onto the stack
switch task    # returns new esp
mov %eax, %esp # update esp
popa           # pop the registers of the next task off the stack
iret           # pop the ISR stack

As long as we both keep track of the esp of a given thread, can't we expect the ISR stack and registers that we pushed to still be there when we get back?

Ghost OS approach:

Code: Select all

// address types
typedef uint32_t g_address;
typedef g_address g_physical_address;
typedef g_address g_virtual_address;
typedef uint32_t g_far_pointer;

/**
 * Image of the stack on interrupt
 */
struct g_processor_state
{
	// Pushed by the interrupt request/routine handler
	uint32_t gs;
	uint32_t fs;
	uint32_t es;
	uint32_t ds;

	uint32_t eax;
	uint32_t ecx;
	uint32_t edx;
	uint32_t ebx;
	uint32_t ebp;
	uint32_t esi;
	uint32_t edi;

	// Pushed by ISR handler if available
	uint32_t intr;
	uint32_t error;

	// Pushed by the processor
	uint32_t eip;
	uint32_t cs;
	uint32_t eflags;

	// Only pushed/popped on Ring 3 <-> Ring 0 switches
	uint32_t esp;
	uint32_t ss;
}__attribute__((packed));



interruptRoutine (assembly procedure, Intel syntax):

    push registers
	push esp
	
	_interruptHandler (C function that returns esp):
	{
	
		taskingStore (C function):
		{
			cast esp as pointer to register struct (g_processor_state*)
			update register struct of current task
		}
			
		requestsHandle (C function):
		{
			select next task
		}
			
		taskingRestore (C function):
		{
			cast g_processor_state pointer of next task as uint32_t (g_virtual_address)
			this uint32_t value is now considered the esp of the next task
		}
	
		return esp of next task
	}
	
	# eax now contains the esp value of the next task
	mov esp, eax
	
	pop registers
	
	# skip over the intr and error fields of the g_processor_state struct
	# esp now should point to the ISR stack of the next task (eflags, cs, eip, ...)
	add esp, 8
	
	# pop the ISR stack
	iret

My approach:

Code: Select all

// register struct
typedef struct k_task{
    uint32_t id;
    uint32_t status;
    uint32_t eflags;
    uint32_t cs;
    uint32_t eip;
    uint32_t eax;
    uint32_t ecx;
    uint32_t edx;
    uint32_t ebx;
    uint32_t esp;
    uint32_t ebp;
    uint32_t esi;
    uint32_t edi;
    
    struct k_task* next;
    void (*start)();
    
}__attribute__((packed))k_task;

Code: Select all

# ISR entry point for IRQ0
irq_0:
	pushal             # push all GPRs
	pushl %esp         # push the current esp
	call irq_0_handler # handle timer and store ISR stack, GPRs, and esp of current task 
	movl %eax, %esp    # update esp
	popal              # pop all GPRs of the next task
	iret               # pop the ISR stack of the next task

Code: Select all

// handle IRQ0
uint32_t irq_0_handler(
	uint32_t real_esp, // This points to the stack that contains the GPRs on top of the ISR stack
	uint32_t edi,
	uint32_t esi,
	uint32_t ebp,
	uint32_t esp, // This value is ignored, since it contains the value of esp before pusha was executed
	uint32_t ebx,
	uint32_t edx,
	uint32_t ecx,
	uint32_t eax,
	uint32_t eip,
	uint32_t cs,
	uint32_t eflags
)
{
	// Increment the tick count.
	// We don't have synchronization primitives yet,
	// so for now this is used to determine whether we should switch tasks.
	main_ticks++;

	// Send the EOI.
	k_outb(0x20, 0x20);

	// Update the ISR stack, GPRs, and esp of the current task.
	// Select the next task.
	k_task* task = k_switch_task(
		main_ticks,
		real_esp,
		edi,
		esi,
		ebp,
		esp,
		ebx,
		edx,
		ecx,
		eax,
		eip,
		cs,
		eflags
	);
	
	// Return the esp of the next task.
	return task->esp;
}

Code: Select all

// select the next task
k_task* k_switch_task(
	uint32_t main_ticks,
	uint32_t real_esp,
	uint32_t edi,
	uint32_t esi,
	uint32_t ebp,
	uint32_t esp,
	uint32_t ebx,
	uint32_t edx,
	uint32_t ecx,
	uint32_t eax,
	uint32_t eip,
	uint32_t cs,
	uint32_t eflags
)
{
    // Use the esp parameter since ignoring it causes a warning.
	 // Yes, this is silly. I'll improve the CPU state transition later.
    if (esp){}

    // If there is no current task,
    // then tasking has not yet been initialized.
    if (current_task == NULL || initialized == 0)
    {
        fprintf(stddbg, "tasking has not yet been initialized\n");
        return NULL;
    }

    // Update the stored CPU state of the current task.
    current_task->edi = edi;
    current_task->esi = esi;
    current_task->ebp = ebp;
    current_task->esp = real_esp;
    current_task->ebx = ebx;
    current_task->edx = edx;
    current_task->ecx = ecx;
    current_task->eax = eax;
    current_task->eip = eip;
    current_task->cs = cs;
    current_task->eflags = eflags;

    // If it's not time to switch tasks,
    // return the current task.
    if (main_ticks % 2000 != 0)
        return current_task;

    // Alternate between the three kernel threads.
    switch (current_task->id)
    {
        case 2:
            current_task = &task_b;
            break;

        case 1:
            current_task = &task_a;
            break;

        case 3:
            current_task = &main_task;
            break;

        default:
            break;
    }

    // If the current task is new, start it.
    if (current_task->status == TASK_NEW)
    {
        current_task->status = TASK_RUNNING;

		 // TODO: figure out a better way to start a task.
        start_kthread(
            current_task->esp,
            current_task->ebp,
            current_task->start
        );

		// For now, all the threads contain infinite loops,
		// so they should never terminate of their own accord.
		// TODO: implement proper thread termination.
        return NULL;
    }

    return current_task;
}

Code: Select all

# start a new task
start_kthread:
    
    pushl %ebp
    movl %esp, %ebp
    subl $8, %esp

    movl 8(%ebp), %eax
    movl %eax, -4(%ebp) # store esp

    movl 12(%ebp), %eax
    movl %eax, -8(%ebp) # store ebp

    movl 16(%ebp), %ecx # put the address of the start function in ecx

    movl -4(%ebp), %esp # update esp
    movl -8(%ebp), %ebp # update ebp

    sti                 # enable interrupts
    call *%ecx          # call the start function
    
    leave
    ret

[Octocontrabass]

As long as we both keep track of the esp of a given thread, can't we expect the ISR stack and registers that we pushed to still be there when we get back?

No. The System V ABI specifies that the portion of the stack used for storing parameters belongs to the called function, so your irq_0_handler code may clobber the register values you passed as parameters before it returns. If you pass a pointer instead, as Ghost does, only the portion of the stack used to store that pointer can be clobbered by the called function.

Also, I think I've mentioned this before, you can start new tasks by allocating a new stack and filling it with the values necessary to "return" to the start of the new task.