133 lines
6.2 KiB
Markdown
133 lines
6.2 KiB
Markdown
|
|
# Kernel Threads
|
|
|
|
In this project, you'll be adding real kernel threads to xv6. Sound like fun?
|
|
Well, it should. Because you are on your way to becoming a real kernel
|
|
hacker. And what could be more fun than that?
|
|
|
|
Specifically, you'll do three things. First, you'll define a new system call
|
|
to create a kernel thread, called `clone()`, as well as one to wait for a
|
|
thread called `join()`. Then, you'll use `clone()` to build a little thread
|
|
library, with a `thread_create()` call and `lock_acquire()` and
|
|
`lock_release()` functions. That's it! And now, for some details.
|
|
|
|
## Overview
|
|
|
|
Your new clone system call should look like this: `int clone(void(*fcn)(void
|
|
*, void *), void *arg1, void *arg2, void *stack)`. This call creates a new
|
|
kernel thread which shares the calling process's address space. File
|
|
descriptors are copied as in `fork()`. The new process uses `stack` as its
|
|
user stack, which is passed two arguments (`arg1` and `arg2`) and uses a fake
|
|
return PC (`0xffffffff`); a proper thread will simply call `exit()` when it is
|
|
done (and not `return`). The stack should be one page in size and
|
|
page-aligned. The new thread starts executing at the address specified by
|
|
`fcn`. As with `fork()`, the PID of the new thread is returned to the parent
|
|
(for simplicity, threads each have their own process ID).
|
|
|
|
The other new system call is `int join(void **stack)`. This call waits for a
|
|
child thread that shares the address space with the calling process to
|
|
exit. It returns the PID of waited-for child or -1 if none. The location of
|
|
the child's user stack is copied into the argument `stack` (which can then be
|
|
freed).
|
|
|
|
You also need to think about the semantics of a couple of existing system
|
|
calls. For example, `int wait()` should wait for a child process that does not
|
|
share the address space with this process. It should also free the address
|
|
space if this is last reference to it. Also, `exit()` should work as before
|
|
but for both processes and threads; little change is required here.
|
|
|
|
Your thread library will be built on top of this, and just have a simple `int
|
|
thread_create(void (*start_routine)(void *, void *), void *arg1, void *arg2)`
|
|
routine. This routine should call `malloc()` to create a new user stack, use
|
|
`clone()` to create the child thread and get it running. It returns the newly
|
|
created PID to the parent and 0 to the child (if successful), -1 otherwise.
|
|
An `int thread_join()` call should also be created, which calls the underlying
|
|
`join()` system call, frees the user stack, and then returns. It returns the
|
|
waited-for PID (when successful), -1 otherwise.
|
|
|
|
Your thread library should also have a simple *ticket lock* (read [this book
|
|
chapter](http://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf) for more
|
|
information on this). There should be a type `lock_t` that one uses to declare
|
|
a lock, and two routines `void lock_acquire(lock_t *)` and `void
|
|
lock_release(lock_t *)`, which acquire and release the lock. The spin lock
|
|
should use x86 atomic add to build the lock -- see [this wikipedia
|
|
page](https://en.wikipedia.org/wiki/Fetch-and-add) for a way to create an
|
|
atomic fetch-and-add routine using the x86 `xaddl` instruction. One last
|
|
routine, `void lock_init(lock_t *)`, is used to initialize the lock as need be
|
|
(it should only be called by one thread).
|
|
|
|
The thread library should be available as part of every program that runs in
|
|
xv6. Thus, you should add prototypes to `user/user.h` and the actual code to
|
|
implement the library routines in `user/ulib.c`.
|
|
|
|
One thing you need to be careful with is when an address space is grown by a
|
|
thread in a multi-threaded process (for example, when `malloc()` is called, it
|
|
may call `sbrk` to grow the address space of the process). Trace this code
|
|
path carefully and see where a new lock is needed and what else needs to be
|
|
updated to grow an address space in a multi-threaded process correctly.
|
|
|
|
## Building `clone()` from `fork()`
|
|
|
|
To implement `clone()`, you should study (and mostly copy) the `fork()` system
|
|
call. The `fork()` system call will serve as a template for `clone()`, with
|
|
some modifications. For example, in `kernel/proc.c`, we see the beginning of
|
|
the `fork()` implementation:
|
|
|
|
```c
|
|
int
|
|
fork(void)
|
|
{
|
|
int i, pid;
|
|
struct proc *np;
|
|
|
|
// Allocate process.
|
|
if((np = allocproc()) == 0)
|
|
return -1;
|
|
|
|
// Copy process state from p.
|
|
if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){
|
|
kfree(np->kstack);
|
|
np->kstack = 0;
|
|
np->state = UNUSED;
|
|
return -1;
|
|
}
|
|
np->sz = proc->sz;
|
|
np->parent = proc;
|
|
*np->tf = *proc->tf;
|
|
```
|
|
|
|
This code does some work you need to have done for `clone()`, for example,
|
|
calling `allocproc()` to allocate a slot in the process table, creating a
|
|
kernel stack for the new thread, etc.
|
|
|
|
However, as you can see, the next thing `fork()` does is copy the address
|
|
space and point the page directory (`np->pgdir`) to a new page table for that
|
|
address space. When creating a thread (as `clone()` does), you'll want the
|
|
new child thread to be in the *same* address space as the parent; thus, there
|
|
is no need to create a copy of the address space, and the new thread's
|
|
`np->pgdir` should be the same as the parent's -- they now share the address
|
|
space, and thus have the same page table.
|
|
|
|
Once that part is complete, there is a little more effort you'll have to apply
|
|
inside `clone()` to make it work. Specifically, you'll have to set up the
|
|
kernel stack so that when `clone()` returns in the child (i.e., in the newly
|
|
created thread), it runs on the user stack passed into clone (`stack`), that
|
|
the function `fcn` is the starting point of the child thread, and that the
|
|
arguments `arg1` and `arg2` are available to that function. This will be a
|
|
little work on your part to figure out; have fun!
|
|
|
|
## x86 Calling Convention
|
|
|
|
One other thing you'll have to understand to make this all work is the x86
|
|
calling convention, and exactly how the stack works when calling a function.
|
|
This is you can read about in [Programming From The Ground
|
|
Up](https://download-mirror.savannah.gnu.org/releases/pgubook/ProgrammingGroundUp-1-0-booksize.pdf),
|
|
a free online book. Specifically, you should understand Chapter 4 (and maybe
|
|
Chapter 3) and the details of call/return. All of this will be useful in
|
|
getting `clone()` above to set things up properly on the user stack of the
|
|
child thread.
|
|
|
|
|
|
|
|
|