Lab Thread: Kernel Threads

In this project, you will implement a simplified version of kernel-level threads to have a taste of how threading is supported by an operating system kernel. To simplify things, the xv6 kernel-level threads will behave slightly differently compared to typical kernel-level threads (e.g., on Linux), and we will describe the differences in Overview section. However, even implementing a simplified version will already give you have a deep understanding of threads and a chance to practice your system engineering/programming skills.

To start the lab, update your repository and create a new branch for your solution by running:

$ git fetch origin
$ git checkout -b thread origin/main
$ make clean

Overview

Kernel-level threads enable a process to have several different execution contexts simultaneously, as each thread is responsible for its own context (e.g., register state, stack). However, threads are not concerned with resource management or protection, which are instead concerns for the process. Therefore, all threads belonging to the same process share the virtual memory address space (page table), file descriptor table, and more.

To implement kernel-level threads and let user programs benefit from them, you essentially need to do the following:

• Define and implement a new system call clone to create a new kernel-level thread.
• Define and implement a new system call join to wait for a kernel-level thread to terminate.
• Define and implement two user-space library functions (i.e., wrappers around the underlying syscalls) thread_create and thread_join for applications to invoke.
• Modify corresponding functions in kernel/proc.c to make your kernel-level threads work properly. This will include (but is not limited to) modifying clone, join, wait, exit, allocproc, freeproc, growproc.

This xv6 kernel-level threads behave differently from typical kernel-level threads in several ways:

• Traditionally, all threads usually share the same file descriptor table. However, for simplicity, each xv6 kernel-level thread has its own file descriptor table (copied as part of clone) and our tests will not invoke any file operations. Therefore, you don’t need to take file descriptors into consideration for this lab.
• Traditionally, if any thread calls exit, this will terminate the entire process (including all other threads belonging to that process). However, the exit in this lab has different semantics. If the main thread of the process (i.e., the one created via fork) calls exit, then the entire process should be terminated (including all of the created threads via clone). However, if any other thread of the process (i.e., ones created via clone) call exit, then only that thread itself should terminate (with all other threads unaffected).
• In the lecture, we denote the thread control block (TCB) and process control block (PCB) as two different data structures in the operating system kernel to track threads/processes metadata. In this lab, you can (and should) reuse struct proc as the TCB for simplicity, as creating a separate struct thread would involve significant refactoring. Note that you will need to modify struct proc to store thread information as necessary.

Our tests will focus on the following aspects:

• Each thread has its own execution context, with clone() and join() are implemented correctly.
• Threads of the same process share the same address space correctly. For example, if one thread’s address space grows (e.g., sbrk), all other threads should see the same thing (i.e., growproc() is implemented correctly).
• A thread exiting will only terminate itself and won’t affect other threads (i.e., exit() and freeproc() are implemented correctly).
• A process can reap its terminated threads and won’t mess up existing syscall handling (i.e., join() and wait() are implemented correctly).

Again, our tests won’t cover file descriptors (to reduce your workload). If you already got a score of 100, feel free to make them work in the traditional way and test it yourself!

API Details

We describe the API here, including its input parameters, what it does, and its return value.

clone (system call)

int clone(void(*fcn)(void*, void*), void *arg1, void *arg2, void *stack);

This call creates a new kernel-level thread which shares the calling process’s address space.

Input parameters:

• fcn - the new thread will starts to execute fcn, which is similar to the signal handler in alarm lab.
• arg1 and arg2 - additionally, we allow the calling process to pass two arguments (arg1 and arg2) to the thread. So that the thread can use these two arguments in its routine (i.e., fcn).
• stack - each thread should have its own userspace stack, we require the calling process to provide a page of memory (stack) when creating this thread. This stack should point to a valid userspace memory with at least 1 page as its size, and it should also be page aligned.

Return value:

• Returns the thread’s id on success. -1 on failure. For brevity, we let each thread has its own process ID (pid); for example, process (pid=4) may create a new thread (pid=5).

join (system call)

int join(void **stack);

This call waits for a child thread of this calling process to terminate. If there is no child thread, it returns immediately. Otherwise, it keeps waiting until there is one child thread terminates. It reaps the terminated thread, freeing the underlying thread resources resources, and returns the child thread’s PID. (Note: It is possible that there is already a terminated thread when join is called.)

Input parameters:

• stack is the address of a void * variable (e.g., void *ptr). When a thread exits, the address of this thread’s user stack will be copied into the ptr, which can subsequently be freed.

Return value:

• Returns the PID of the terminated thread or -1 on failure (i.e., there is no thread to wait on).

thread_create (user library function)

int thread_create(void (*start_routine)(void *, void *), void *arg1, void *arg2);

This is a wrapper library function for clone(). Inside this function, you need to allocate a suitable block of memory for the newly created thread to use (remember the stack parameter for clone()) and then call clone() to create a new thread for the process.

Input parameters:

• start_routine - the function that the newly created thread will execute
• arg1 and arg2 - the parameters the calling process want to pass to the thread’s routine

Return value:

• Returns the PID of the new thread on success and -1 on error.

thread_join (user library function)

int thread_join();

This is a wrapper for the join() system call. Inside this function, you need to call join() to wait for a thread to terminate. You need to free the allocated memory (for thread’s stack) inside to avoid a memory leak.

Input parameters: N/A

Return value:

• Return the PID of the terminated thread on success and -1 on error.

Step by Step Hints

1. You can first implement the glue. Implement the necessary parts for system calls - simply implement a clone and join that always return 0. Get them compiled without errors.
2. Edit user/ulib.c and user/user.h to implement the thread_create and thread_join. Make sure that they can call clone and join in a correct way. Additionally, make sure they can be called by threadtest.c in a correct way. Now, edit your Makefile to include threadtest. Your code now should be able to compiled correctly and … fail as expected.
3. Now focus on implementing clone first.
   1. fork() already provides a template about how to create a new process control block (struct proc) and assign them with correct values. Read fork() source code carefully.
   2. You also need to allocate a new thread control block for your clone. Fortunately, you can just use struct proc as a TCB here. Therefore, you need to allocate a new struct proc for your thread. Take a look at how fork() does this, and you will find the answer.
   3. Different from fork(), threads of the same process share the same address space, which means they use the same page table.
   4. The newly created thread will return to usertrapret and return to the userspace after it gets scheduled. It will then restore its context from its trapframe. Recall what we’ve done in the alarm lab, you need to modify some values of its trapframe to make it correct, including the program counter, two arguments, and the stack pointer.
   5. Please refer to the RISC-V calling convention, and you will find a0 and a1 stores the arguments. For the stack pointer, you need to make it points to the top of the stack, and you also want to make it aligned. (Hint: a & (~(8-1)) is a way to align a with 8)
   6. Important: each thread has its own proc, and hence its own trapframe. However, since all threads share the same process’s address space, their trapframes may be mapped to the same address and will interfere each other. You therefore need to map each thread’s trapframe to a unique address. We provide you several APIs in kernel/vm.c to do so -
      1. uint64 kwalkaddr(pagetable_t, uint64); to find a free page in the page table
      2. int mappages(pagetable_t, uint64, uint64, uint64, int); to map into the page You can refer to how TRAPFRAME is mapped to properly use the above APIs in kernel/proc.c.
4. With a correct clone, you should be able to run the test and see TEST1 passed followed by some kernel errors. Please use gdb as instructed on course website and xv6 command line to back trace the panic. If you see some weird page fault errors, you may want to take a look at exit : the reason why the page fault are caused by exit is that when thread calls exit(0), they will free their resources, including freeing their page tables and physical memory. However, all threads share the same memory address space. If one thread exits and free everything, the other threads of the same process will suffer from invalid page table and have no physical memory. To address this issue, you need to go into exit and differentiate thread and process. Make sure thread exits without destroying the entire process. Notice: thread’s unique resource (the page table entry for the trapframe) should be freed properly here, because other threads of the same process have no visibility of that.
5. After fixing the exit issue, you can try to comment out all other tests and you should be able to pass test1 correctly now.
6. Now focus on implementing join
   1. wait() already provides a template about how to wait for a process to terminate. Read wait() source code carefully.
   2. Similar as wait(), all you need to do for join() is to reap a proc that is for a thread and is already ZOMBIE.
   3. Additionally, you may need to copy the stack address back (to free it) in a similar way as the copyout for xstate
   4. You need to make corresponding changes to wait() to make sure it only captures child processes not threads.

Now you should be able to run clone() and join() correctly.

1. However, the above is not enough for the kernel-level thread to be fully correct. One note is that all threads of the same process share the same address space. When the address space grows (e.g., growproc()), it currently only updates its own sz while the pagetable is visible to all threads. You need to ensure that all threads of the same process have the same visibility of the sz, so that they won’t update pagetable wrongly (e.g., remap).
2. Besides, when a process (not a thread) calls exit, all threads of this process should be exit. You need to do something similar to reparent. The difference is that reparent changes the parent of all children to be the init process while for a process’s exit you need to make all threads (not child process) of the same process exit correctly. You may refer to freeproc or kill to see how we can terminate a thread/proc.

Test and Submit

For test, python3 grade_lab_kthread.py

For submission, run make gradescope and submit the resulting submission.zip file. If you have any errors, you can use make gradescope-all instead.