This is not the current version of the class.

# Problem set 5: Journaling, threads, and/or project

For problem set 5, you must complete at least two of three parts: file system journaling, threads, and an open-ended project.

## A. Journaling

Add journal support to your file system. This not only shows you how to manage a complex on-disk structure, it also gives you practice in orchestrating different parts of a complex parallel system to achieve a goal.

Your VFS should ensure that groups of disk writes that should be atomic are committed with a single journal transaction. For example, a free-block-bitmap write that allocates a block should commit in the same transaction as an inode write that references the block.

You may implement any journaling mode. Writeback mode, which does not write data blocks to the journal, is a fine first choice, though it has worse recovery properties than the other modes.

You may assume that the journal is empty at boot, and journal replay support is not required. (Our tests will use obj/chickdeefsck -s IMAGE, which implements offline replay.) But you may implement journal replay if you like. We recommend using the chickadeefs::journalreplayer base class, which implements the (complicated!) replay analysis procedure.

It can be fun to design your own journal subsystem. The critical questions are:

• Transaction allocation: How should code mark the start and/or end of a journal transaction?
• Write matching: How can the buffer cache tell whether a write is part of a journal transaction, and if so, which one?
• Ordering constraints: How can the buffer cache ensure it delays writeback for journaled blocks until the relevant transactions commit?

Give some thought to these issues. What is the simplest solution you can think of that supports allocation, matching, and ordering? But after some thought, most people should look at the in-depth suggestions.

Implement multithreaded processes: processes that can have multiple independent threads of control, but that share the same virtual memory space and file descriptor table. Use kernel threads, the design where every user-visible “thread” corresponds to a struct proc.

• The new sys_clone system call starts a new thread in the current process. See below for more on sys_clone.
• The new sys_gettid system call returns the current thread’s thread ID. Different threads in a process have different sys_gettids, but the same sys_getpid. Note that the process ID returned by sys_getpid need not equal any of the sys_gettids for that process’s threads!
• The new sys_texit system call exits the current thread. When the last thread in a process exits, sys_texit behaves like sys_exit; otherwise, the process just continues with one fewer thread.

And change some existing ones:

• sys_exit exits all threads in the current process.
• sys_waitpid waits for processes, not threads (in other words, sys_waitpid(p) waits for all the threads of p to exit).
• sys_fork should clone only the calling thread.
• You may assume that sys_execv is called only by single-threaded processes.

Run make run-testthread to check your work.

### Process IDs and thread IDs

Kernel threading introduces a distinction between process and thread IDs: every user task has one of each, and they may not be equal. fork must allocate one of each.

You may find it easier to store the thread ID in proc::pid_. This may feel backwards but it’s just easier to keep ptable indexed by pid_. Add a new member, such as proc::true_pid_, to store the true process ID; and add a table, such as proc* true_ptable[NPROC], to store processes by true PID. (For what it’s worth, Linux does the same thing. The task_struct::pid member is a thread ID, while the true process ID is called a “thread group ID” and stored in task_struct::tgid; Linux’s getpid system call returns tgid and its gettid returns pid. ¯\_(ツ)_/¯)

### sys_clone interface

Your goal is for sys_clone(function, arg, stack_top) to set up a new thread running function(arg) on the given stack, where when that function returns, the thread exits via sys_texit. This means the initial thread stack frame should contain a return address pointing to sys_texit. Multithreading packages typically divide responsibility for this between the kernel’s system call and user-level code in the system call wrapper; most typically the stack setup is left to wrapper code.

Some examples from real operating systems:

• In Linux, the clone system call takes several arguments, but none of those arguments correspond to function or arg, and the stack_top argument doesn’t actually change the active stack pointer (it is recorded in the kernel for later use). Linux clone’s return value resembles that of fork: it is 0 in the new thread and the new thread’s ID in the original thread. User-level wrapper code examines the return value and modifies the stack as appropriate. In a Linux-like Chickadee design, the sys_clone system call would take no arguments.

References: clone manual page; uClibc’s clone implementation (documented); musl libc’s clone implementation (undocumented, but more compact).

• In FreeBSD, the thr_new system call does take arguments resembling function, arg, and stack_top. However, when used in a threading library, the wrapper code still adds a layer of indirection so that the sys_texit equivalent is called when the thread function returns.

### Synchronization

Explain your synchronization plan for parts of process state that can now be shared by multiple tasks, especially pagetable_ and your file descriptor table.

### Exiting

Process exit is a special issue for multithreaded processes. The sys_exit system call should exit all of the process’s threads, not just the calling thread. But the process’s other threads might be blocked in the kernel or running on other CPUs! The threads’ memory and struct procs cannot be deleted until they have all stopped running. You’ll want to mark the threads as “exiting,” wait for them to stop running, and only then tear down the process as a whole. This will use some of the same techniques you used in problem set 2, part G (system call interruption). The later parts of p-testthread.cc check interactions between sys_exit and sys_texit.

## C. Project

Design and implement an open-ended project: a new feature for your operating system.

Project ideas might include:

• Networking support. Implement device support for networking, then link that device to a networking stack, such as lwIP.

You may be interested in a networking project from MIT’s 6.828 class; though that class uses 32-bit x86 rather than 64-bit x86-64, network device handling support should be similar.

• Graphics support. Implement a fancier graphics mode. Maybe port a game!

• Debugging support. Can you make DWARF debugging information, or some other kind of debugging information, available in the kernel? This might let you print line numbers in backtraces!

• More visualizations. Can you create console visualizations for other aspects of the problem sets than virtual memory? For example, can you create a visualization for the disk, or the VFS?

• Performance optimization and stress tests. Create a thorough and comprehensive test suite, a stress test plan, and/or a performance benchmark, then improve your operating system until it is amazing.