Kernel Threading?

[purevoid]

Hi,

I've been trying to find some good info on basic kernel threading. I can find tuts on multi-tasking, but that's far too heavy-weight for my needs.

My kernel is just one uber-process I guess, and I -only- need basic threading support. I'm just not sure where to begin. (And don't tell me to change my kernel!! ;-)

As long as I can switch threads in C, and implement mutexes (maybe condition variables if I'm lucky), I'll be very happy.

Jonathan

[JoeKayzA]

Hi!

In my kernel I represent kernel threads as structures, that hold a few thread attributes (thread id, if neccessary, status [blocked/running]) and a stack pointer, that points to the actual stack top. On a timer interrupt, you push the cpu status (gp-registers, segment registers) on the stack and then save the new stack pointer in the thread struct. Then you call the scheduler function that determines the next thread to run, does some accounting (cpu time...) and returns this thread's stack pointer. After that, back in your ASM isr, you put this stack pointer in esp and pop off the status again, and iret. DONE

Bonafide has some very interesting tutorial on multitasking, if you need further information.

cheers Joe

[purevoid]

How about a very simple tutorial (of co-op threading!! no isr stuff)?

Like two threads, each puts a char to 0xb8000 then yield? Basically to demonstrate how to do proper switching. This is where I'm first a bit unsure on.

And a basic description of how to make mutexes work after this initial basics are setup...

Jonathan

[AR]

Cooperative is basically the same, all this together is also basically the same as user space software as well (the only difference being that you don't need a TSS).

For cooperative multithreading have a look at setjmp and longjmp.

[purevoid]

Hmm, then maybe co-op isn't what I'm looking for (at least in the C layer).

So no one has some example code on lightweight kernel threads?

[AR]

All forms of thread/task switching involve saving and restoring states, you cannot avoid that:

Code: Select all

struct jmp_buf
{
    unsigned int ESI, EDI, EBX, EBP, ESP, EIP;
};

int setjmp(jmp_buf *context);
void longjmp(jmp_buf *context, int val);

Code: Select all

.global setjmp
setjmp:
    mov %ss:4(%esp), %eax  # Get pointer off stack

    # Must be preserved by GCC ABI
    mov %esi, 20(%eax)
    mov %edi, 16(%eax)
    mov %ebx, 12(%eax)
    mov %ebp, 8(%eax)

    # Set EIP to the return address
    mov %ss:(%esp), %ecx
    mov %ecx, (%eax)

    # Stack state
    mov %esp, 4(%eax)

    # Return 0
    xor %eax, %eax
    ret

.global longjmp
longjmp:
    mov %ss:4(%esp), %ecx  # Get pointer to state to restore
    
    # Get the return value
    mov %ss:8(%esp), %eax

    # Restore the general registers
    mov 20(%ecx), %esi
    mov 16(%ecx), %edi
    mov 12(%ecx), %ebx
    mov 8(%ecx), %ebp

    # Set Stack State
    mov 4(%ecx), %esp
    add $4, %esp

    # Switch to previous path of execution
    mov (%ecx), %edx
    jmp *%edx

This is a basic implementation of setjmp/longjmp for 32bit flat linear address spaces. It should work but there may be some errors.

If you've never used them before, they operate like this:

Code: Select all

jmp_buf MyThreadState; /* global/static/whatever */

...

/* Since the state was saved here, longjmp will cause execution to "resume" here, the val parameter in longjmp is what the if() will think setjmp() returned */
if(setjmp(&MyThreadState) == 1)
    kprint("Thread was switched successfully!\n");

...

/* Switch to the thread context */
longjmp(&MyThreadState, 1);

[JoeKayzA]

Hmm, then maybe co-op isn't what I'm looking for (at least in the C layer).

So no one has some example code on lightweight kernel threads?

Ok, if you need complete code examples,

http://www.the-legend.de.vu/

has a very good tutorial, which was the basis for my multithreading engine. Thx, Legend, btw.

cheers Joe

[purevoid]

That's multi-tasking. Too heavy-weight for me.

And I'm driving myself insane trying to figure out the basics of this =( No-one can give me a simple step-by-step guide to the first few parts of lightweight kernel threads? My head is sore from the wall =(

[AR]

What do you want to know explicitly, can you provide a list of what you don't understand?

[purevoid]

Well, I need a c-layer of threads to implement OCaml threads on top of it.

I've tried setjmp/longjmp, but couldn't figure that out. And I'm not sure that's going to be the best long-term anyway.

I can't figure out this whole stack-switching business.

I assume I just need a circular list of threads in runnable state, and then switch to next in scheduler.

And for mutexes, take blocked threads off runnable list, and tack onto blocked threads for the given mutex?

Not sure how condition variables work, but I'll need these too.

But right now, all I want is: launch two threads, and have a yield() function that each can call, and some way of exiting a thread. After I get that going, the rest I can figure out ;-)

And can all this be done without using TSS/interrupts?

I'm using a single kernel address space for entire OS & Apps...

[purevoid]

A little of my background:

I'm not a C coder, and even less of an ASM coder (only familiar with AT&T syntax). I've managed to write a fairly functional OS without almost any C/ASM code (even has an IRC client, to give an idea of how functional it is), and now I'm screwed cause I have to tackle threading at the C level =(

[AR]

Stack switching is exactly what it's name implies, you save the ESP to the thread struct, pick another thread and put its ESP in the ESP register. Before the stack is switched, the state has to be saved on it (PUSHA) - this is usually done by the Timer ISR. After the stack is switched, the state from that thread is restored (POPA) and IRET back to the CS:EIP it was executing at.

For setjmp/longjmp, basically "setjmp" declares the return point on return, "longjmp" is basically equivalent to "yielding" to the thread given by the struct pointer. For example, if one program was drawing rectangles and the other was doing lines then you would have something like:

Code: Select all

jmp_buf thread1;
jmp_buf thread2;

void DrawRectsThread()
{
     /* while(1) DrawRndRectangle(); */
     if(setjmp(&thread1) != 0)
        DrawRndRectangle();

     longjmp(&thread2, 999);
}

void DrawLinesThread()
{
    /* while(1) DrawRndLine(); */
    if(setjmp(&thread2) != 0)
       DrawRndLine();

    longjmp(&thread1, 1);
}

void KernelInitIsDone_StartThreads()
{
    if(setjmp(&thread2) != 0)
        DrawLinesThread();

    DrawRectsThread();
}

What happens here in order is:

• 1) "KernelInitIsDone_StartThreads" saves "thread2"s state (as being at that IF)
• 2) It calls "DrawRectsThread"
• 3) "DrawRectsThread" saves "thread1"s state (ie. itself), then it "longjmp"s to "thread2"
• 4) The "longjmp" has dropped us back at the IF in "KernelInitIsDone_StartThreads", however this time the "setjmp" has returned something other than zero [999] so we call "DrawLinesThread" now
• 5) "DrawLinesThread" saves its own state ("thread2") then "longjmp"s to "thread1"
• 6) Control returns to "DrawRectsThread" at "setjmp" which has magically returned something other than 0 this time [1] so we perform the draw operation then "longjmp" to "thread2"
• 7) Control returns to "DrawLinesThread" at "setjmp" which has also magically returned something other than 0 this time as well [999], it performs the draw operation then "longjmp"s back to "thread1"
• 8) Goto 6, repeat for eternity, or until system failure

[AR]

A mutex is a device controlling mutual exclusion, its purpose is to prevent non-threadsafe operations from being performed by 2 or more threads simultaneously, generally in a multi-CPU environment. For example, if 2 CPUs were to try and add a process to the process list simultaneously, one CPU would create the struct and write its data, the second will then override half of what the first CPU wrote, and a third could be trying to read it at the same time.

A mutex is basically just an atomic variable get/set operation which disables interrupts, eg.

Code: Select all

typedef struct
{
     unsigned int mutex;
     unsigned int flags;
} mutex_t;
int AccquireMutex(mutex_t *m);
int ReleaseMutex(mutex_t *m);

Code: Select all

.global AccquireMutex
AccquireMutex:
     mov %ss:4(%esp), %eax   # Get the struct pointer off the stack

     mov $1, %ecx     # Set the mutex to 1
     xchgl %ecx, (%eax) # Atomic operation, value swap
     or %ecx, %ecx     # See if it is currently 0
     jz 1f              # If it was then success
     xor %eax, %eax    # Error code is return 0
     jmp 2f

1:  mov $1, %eax     # Success, return 1
     pushf                # Save flag state before disabling interrupts
     mov %ss:(%esp), %ecx   # (to preserve state if they are already off)
     mov %ecx, 4(%eax)
     pop %ecx
     cli                 # Disable interrupts
2:  ret

.global ReleaseMutex
ReleaseMutex:
     mov %ss:4(%esp), %eax  # Get struct pointer off the stack

     mov 4(%eax), %ecx  # Restore the flags
     push %ecx
     popf

     movl $0, (%eax)   # Zero the mutex
     ret

The above code is a generic single/multi CPU environment mutex. You would actually use a spinlock/yield in a multi-CPU environment, and you could just have a raw CLI/STI in a single CPU environment [provided you don't nest the mutexs].

[purevoid]

So, from your code, you don't need separate stacks per thread. Is that right? And if so, is that because it's co-operative?

[AR]

The stack gets messed around a bit but because they always yield at the point where the stack is no longer needed until the next iteration there is no problem.