Operating Systems #9 — Building LWPs and a Process Manager in xv6

The second project came in two halves: building LWPs (threads) in xv6, and building a process manager called pmanager on top of them.

Before I get into it — a git branch misconfiguration wiped my master branch once. I recreated master and worked there, keeping main as a temporary backup. The wiki is written against master.

Design

pmanager

pmanager supports five commands.

• list — prints information about the currently running processes, one line per process rather than per thread. "Running" means the RUNNABLE, RUNNING, and SLEEPING states. It scans the ptable in a for loop and prints only the process-level information.
• kill — takes a <pid> and kills that process through the kill system call. kill returns 0 on success and -1 on failure, so that's what the success message keys off.
• execute — takes <path> <stacksize> and runs the program at path with stacksize pages of stack. The existing exec doesn't take a stacksize and gives one stack page plus one guard page, so a new system call, exec2, is needed. And since pmanager must not block after launching, it follows the shell's background execution (&) pattern.
• memlim — takes <pid> <limit> and enforces it through a new setmemorylimit system call. The limit accounts for memory including threads.
• exit — terminates pmanager.

pmanager reads input and acts on it just like the shell, so it's built off sh.c.

LWPs

An LWP shares resources and address space with other LWPs, making multitasking possible at user level. xv6 has no threads, so we add them.

Since a thread is also a process, and a single process is also a thread, the implementation just adds a few fields to struct proc. Looking at pthreads, in the kernel every thread has a distinct pid and threads in the same process share a tgid; when the user calls getpid, it appears to return that tgid.

Three functions to build:

• thread_create(thread_t *thread, void *(*start_routine)(void *), void *arg) — creates a thread starting at start_routine. The first argument receives the new thread's number, and the third is passed through to start_routine. Returns 0 on success and -1 on error such as running out of space. Sharing the calling process's pgdir is what shares the resources and address space.
• thread_exit(void *retval) — terminates the thread and passes back a return value, which thread_join will collect.
• thread_join(thread_t thread, void **retval) — if that thread exists, sleeps until it exits. If it's already a zombie, cleans up its resources. Stores the value passed to thread_exit into retval. Returns -1 if no such thread, 0 on normal completion. For resource recovery I planned to borrow the approach free uses for memory: don't deallocate, put unused regions on a freelist and take them back out when needed.

Then the existing system calls have to be redefined for a threaded world. fork copies only the calling thread; exec cleans up every thread except the caller; sbrk must not hand out overlapping space when several threads call it at once; exit and kill must terminate every thread in the process.

Implementation

struct proc

The fields I added:

• int pid — every process and thread has its own pid.
• int tgid — threads in one process share the main thread's pid as the thread group id.
• void *retval — where a thread stores its return value. thread_exit stores the address it's given here, and thread_join delivers it to the location it was given.
• struct proc *mainThread — the thread that was the original basis of the process.
• struct proc *createThread — the thread that created this thread. Calling thread_create from a non-main thread produces cases where mainThread != createThread.
• struct freelist fl[20] — holds the stacks freed by thread_join, borrowing the idea from free() in umalloc.c. valid == 1 means there's a free stack whose top address is addr; 0 means the entry isn't valid. fl[0].valid == 0 means no free stack, so a new one has to be allocated.
• uint stack — the top address of the stack this thread was given. Used when putting the stack into a freelist addr.

proc.h — the fields added for threads.

The freelist struct. valid == 1 means a free stack whose top is addr.

These get initialized in allocproc, userinit, fork, exec (exec2), and thread_create.

• allocproc — initializes tgid to equal pid on first allocation. Even a non-thread process belongs to its own thread group by default.
• userinit — for a non-thread process, it is its own mainThread and createThread. Everything in fl is zeroed, building a freelist with no spare stacks.
• fork — called from a thread, it copies only that thread. If curproc's createThread is itself (i.e. it isn't a thread), the flow is as before and createThread is itself; if it is a thread, it takes curproc's createThread. fl is copied straight from curproc.
• exec — has to handle being called from a thread, so tgid is set to the caller's own pid. createThread, mainThread, and fl are set the same way as in userinit.

allocproc — tgid initialized to equal pid.

thread_create

Built from the fork and exec code. It takes a process out of the ptable, then checks whether the current process's (thread's) mainThread has a usable stack in its fl. If so it reuses it; if not it allocates a new one — the reuse path jumps past the allocation via a label.

Then it sets the new thread's mainThread and createThread, and pushes arg and a fake return address onto the stack the way exec does.

• For a newly allocated stack, sz has grown, so sz is bumped on every thread sharing the tgid.
• For a recycled stack, the new thread's sz is just the existing sz, and the used addr is removed from fl.

thread_create — taking a ptable slot and looking for a reusable stack.

Setting the new thread's mainThread and createThread.

thread_exit and thread_join

thread_exit closes the file references (the fds) and cwd (dropping refcounts) and stores its argument into the thread's retval. Then it wakes the thread that created it so the resources can be handled. Since it's natural for the creator to clean up what it created, only createThread is allowed to call join.

thread_exit — waking the thread that created it.

thread_join skips threads with a different tgid and looks for the thread in the same process whose pid matches the argument. If it exists and is a zombie, it frees the kstack, clears the user stack region, and adds it to mainThread's fl. It then fills in retval and cleans up the remaining resources the way wait does. If no such thread is found it returns -1; if the thread exists but isn't a zombie, it sleeps — which is why thread_exit has to wake it.

removeFree() drops the front entry of mainThread's fl and shifts the rest forward; addFree(uint stack) puts its argument into addr, sets valid to 1, and inserts it at the front of fl.

thread_join — reclaiming a zombie thread's stack into the freelist.

System calls adapted for threads

• fork — copies only the thread, so the mechanism is unchanged. Nothing altered beyond initializing the new fields.
• exec / exec2 — has to clean up every thread but the caller, so I wrote clearThread(), which removes the resources of threads sharing its tgid. pgdir is handled by exec itself, so no freevm is needed here.
• sbrk — takes the ptable lock, since simultaneous allocation requests from several threads must not overlap.
• kill — sets killed to 1 on every thread with the same tgid.
• sleep — unchanged; only the caller sleeps, because each thread was given a distinct pid.
• pipe — thread creation copies the fds, so creating threads after a pipe and using those fds prints fine.
• exit — uses clearThread, since every thread has to die.

clearThread() — clearing every thread with the same tgid but itself.

sbrk — the ptable lock that keeps concurrent allocations from overlapping.

kill — setting killed on every thread sharing the tgid.

exec2 and setmemorylimit

exec2 changes the part of exec that allocated 2 pages to allocate stacksize + 1. Making the bottom page a guard page uses clearpteu.

setmemorylimit(int pid, int limit) checks that the limit is positive and larger than the size already occupied, and sets it if valid. 0 means unlimited. The stored value is then consulted in growproc and on thread creation.

exec2 — the two-page allocation changed to stacksize + 1.

setmemorylimit — checking the limit against the size already occupied.

pmanager

I built getcmd2 from sh.c's input function and used it as the while condition in main, so it loops forever short of an error.

• list — calls proList, a system call I wrote. It prints pid, name, number of stack pages, memory size, and memory limit. Size and limit account for all threads; the stack page count is per-thread, since the main thread can't use another thread's stack.
• kill — if the pid exists, kills the entire process with that pid. (pid here means tgid.)
• execute — reads path and stacksize separately, with atoi for the stacksize. Following the shell's background execution, it calls fork() twice: the innermost child calls exec and the first child calls exit(). The top-level parent handles only the exited child's resources, leaving the exec'd child's resources to initproc.
• memlim — 0 for unlimited, positive to cap at that size. Trying to set a limit below what's already allocated prints a failure.
• Anything else prints <command not found>.

Results

pmanager. Executing thread_test and then typing list shows the information.

Launching thread_test with execute, then listing.

memlim fails when asked for a limit below the current one and takes effect when it succeeds.

A limit below the occupied size fails; a valid one is applied.

thread_test. To check stack reuse I printed addresses at create and join time. In test 1 (basic) the created thread's stack came back cleanly.

Test 1 — create and join addresses line up, so the stack is reclaimed.

In test 2 (fork), 32768 and 24576 from test 1 were reused first, then the freelist emptied and 40960, 49152, and 57344 were freshly allocated — and all of them returned to the freelist afterwards. In test 3 (sbrk) the same stacks were reused again and sbrk didn't overlap.

Test 2 — the stacks left on the freelist are handed out first.

• thread_exec / thread_exit / thread_kill — exec printed its success message correctly; exit terminated every thread without printing the message it shouldn't have. The kill test forked separate processes with five threads each and had thread_2 kill thread_1; the message printed exactly five times.

Trouble shooting

pmanager

list wasn't being recognized. I'd written buf[4] = ' '; changing it to buf[4] = '\n' fixed it.

Repeated kills stopped working. Checking the input showed it contained the previous entry. The pid was initialized to 0 when pmanager started but never again inside the loop. Initializing it to 0 inside the kill branch fixed it.

Threads

Where removeFree is called. I put removeFree before t->stack = ~, so the stack address actually allocated and the one memset cleared at join time diverged. That produced a trap 14 in user space. Moving removeFree down fixed it.

Double acquire. Using allocproc() panicked on a duplicate acquire, because allocproc already acquires the lock inside. I moved the lock acquisition to after allocproc.

ustack arguments. In thread_create I pushed an argument count and a 0 the way exec does, and the thread read back garbage. Simply pushing arg worked.

switchuvm. Passing the newly created thread to switchuvm at the end of thread_create panicked. Passing curproc instead worked. I assumed sharing the same pgdir made it irrelevant, and it didn't. I still don't know why, and want to keep digging.

growproc. sbrk tests were fine single-threaded but produced a remap panic with several threads, because growproc was only changing curproc's size.

Deallocation and copyuvm. Joining a thread wedged in the middle and trying to deallocate its stack produced copyuvm: page not present. copyuvm copies page by page from 0 to sz, and deallocating sets PTE_P to 0, which is what triggered the error. So a middle thread's stack can't be deallocated. I handled it with *pte = 0 instead. And since fork after deallocation breaks, I allocuvm the empty region before forking. I kept addr around rather than clearing it, to consult on the later fork.

copyuvm: page not present — what forking after deallocating a middle thread's stack produces.