Lab Thread: Kernel Threads

In this project, you will implement a simplified version of kernel thread to have a taste of how thread works. This xv6 kernel thread behaves differently from a typical kernel thread. We will describe the difference in overview section. However, to implement a simplified version of kernel thread will already let you have a deep understanding of threads and practice your system-level engineering skills. That is super interesting and please have fun with it!

Before you start

We update the xv6 base repo to provide some helper functions for your kernel thread lab, please re-pull the course repo from main branch (git pull origin main) and then create your own branch as you did for alarm and util labs.

Overview

The essential of kernel thread is to let a process have several execution flows simultaneously. This requires each thread keeps its own contexts. For example, threads of the same process can have their own program counters and stacks, and kernel needs to keep track of these for threads. However, all threads of the same process will share the same virtual memory address space, and hence, the same page table.

To implement kernel threads and let application developers to use them, you basically need to do the following things

• Define and implement a new system call clone to create a kernel thread.
• Define and implement a new system call join for a process to “wait for” its kernel thread to terminate.
• Define and implement two userspace library functions (i.e., a wrapper of the system call) thread_create and thread_join for applications to create their threads and waits for their threads to terminate.
• Modify corresponding functions in kernel/proc.c to make your kernel threads work properly. For references, you will need to (but not limited to) add or modify the following functions, clone, join, wait, exit, allocproc, freeproc, growproc.

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

• Traditionally, all threads usually share the same file descriptor table. However, for simplicity, each xv6 kernel thread has its own file descriptor table (copied from the process who calls clone) and we assure there is no file operations/syscall invoked in our tests. Therefore, you don’t need to take file descriptor into consideration in this lab.
• Traditionally, any thread calls exit will terminate the process (including all threads of the same process). However, the exit in this lab has different semantics. A process, who is created with fork, calls the exit and the process with its created threads will all terminate. A thread, who is created with clone in this lab, calls the exit and only the thread itself will terminate, other threads of the same process will not be affected.
• In the lecture, we reference thread control block (TCB) and process control block (PCB) as different data structures in the operating system kernel to track threads/processes metadata. In this lab, you can reuse struct proc as the TCB for simplicity, but you need to make corresponding modifications to store thread info.

Specifically, to make sure you implement the simplified xv6 kernel thread correctly, we test -

• Each thread has its own execution context - 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 - growproc() is implemented correctly
• Thread’s exit will only terminate itself and won’t affect other threads - exit() and freeproc() is implemented correctly
• A process can reap its terminated threads (even the thread created by its thread) and won’t mess up existing system calls - join() and wait() are implemented correctly.

Notice - our tests won’t cover file descriptors (to reduce your workload) and you don’t need to worry about file descriptor tables in this lab. If you already get 100, feel free to make them work in a proper 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 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 points to a valid userspace memory with at least 1 page as its size, and it should also be page aligned.

Return value:

• return the thread’s id on success. -1 on failure. For brevity, in this lab we let each thread has its own process ID (pid). For example, process (pid=4) may create a new thread whose pid is 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, return immediately. Otherwise, keeps waiting until there is one child thread terminated. It reap the terminated thread and free the terminated thread’s resources, and return the child thread’s PID. Notice, 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. Therefore the ptr can be freed because this piece of memory will not be used.

Return value:

• return the PID of the terminated thread or -1 on failure (there is no thread to wait)

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 the clone() to create a new thread for 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 values:

• Return 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 memory leak.

Input parameters: N/A

Return value:

• Return the PID of the terminated thread on success and -1 on error. Blocked if there is active threads but no one terminates.

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 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.
3. You new xv6 implementation with kernel thread support should pass usertests.

Test and Submit

For test, python3 grade_lab_kthread.py

For submission, make gradescope and submit the submission.zip file. Please delete submission.zip file before you create a new one. Besides, refer to the Ed pinned post if you have zip: command not found error.