This is not the current version of the class.

Problem set 3: File descriptors and VFS

You should first merge your code with our pset updates. The easiest way:

git pull https://github.com/cs161/chickadee master

You will then have to fix up any conflicts. Follow Git’s instructions and commit the final result.

A. Initial read and write system calls

Our handout code includes:

Merge with our handout code, look at p-cat.cc, and run make run-cat. Type some stuff and press Return. p-cat should echo what you typed, one line at a time! The characters you type are echoed to the console by the keyboard driver in a green-blue; the characters printed by sys_write appear in bright white.

Now read and understand the implementations of SYSCALL_READ and SYSCALL_WRITE. You may be interested in the implementation of the keyboardstate object, which supports line buffering; it is in k-devices.hh and k-devices.cc.

Your task has two parts:

  1. The SYSCALL_READ system call waits until a line is available, but the current implementation does this using kernel polling (yielding) rather than blocking. Change it to block instead of yield. You will use a waiter and block_until, and you’ll want to add a wait_queue to keyboardstate (see k-devices.hh and keyboardstate::handle_interrupt in k-devices.cc).

  2. The SYSCALL_READ and SYSCALL_WRITE implementations do not check their arguments for validity, making them seriously dangerous. Change them to verify that the relevant memory ranges are present, user-accessible, and (for SYSCALL_READ) writable. Also check for integer overflow. You may want to augment vmiter with another function to check a range of address permissions.

    Use make run-testrwaddr to check your work.

B. File descriptors and VFS

The goal of this part is to implement a VFS skeleton and per-process file descriptor table. This includes significant design effort. By the end of this part, your Chickadee should support:

When you’re done, the p-testrwaddr.cc and p-cat.cc programs should work as they did before, but using your VFS abstraction. The p-testvfs.cc program should work too.

Design document

Write up a design document for your VFS layer abstraction. Answer the following kinds of questions:

Please write up the design document by Monday afternoon 3/11 and check it in to your repository. You can use Markdown (psets/pset3vfs.md), plaintext, or Google doc (post a link to the doc in your repository). We threw together an example for your reference.

Here are some references to other operating systems’ VFS layers. Your design should not be as complicated as that of FreeBSD or Linux! It should probably be more complex than that of xv6.

Note on keyboard/console

We referenced a “keyboard/console file system” above. Though that might sound surprising, it follows Unix’s typical behavior. Try running this Unix program to see what we mean.

#include <unistd.h>
#include <stdio.h>

int main() {
    write(1, "Hello\n", 6);
    close(1);
    write(0, "Hello again\n", 12);
    dup2(0, 1);
    write(1, "Hi\n", 3);
}

(To compile and run a one-file program like this, run c++ FILENAME.cc; ./a.out. Or tell the compiler a better name for the executable: c++ -o EXECUTABLE FILENAME.cc; ./EXECUTABLE.)

Implementation

Implement your design. Keep track of any changes required to the initial design; describe those changes briefly in your pset3answers.md file. Again, use make run-testvfs to check your work.

C. Pipes

Implement the SYSCALL_PIPE system call. Test your work with make run-testpipe.

Some notes:

You will want to check that any dynamically-allocated memory for pipes is freed at the appropriate times.

Use make run-testpipe to check your work.

Keep track of any changes pipes require to your initial VFS design. Describe those changes briefly in your pset3answers.md file.

D. Memfs

Parts D and E are independent.

The Chickadee kernel image contains a set of binaries—things like obj/p-allocator, the allocator process, or obj/p-testpipe. These binaries comprise an in-memory file system where each file consists of contiguous kernel memory. Each file on the file system is defined by a struct memfile (see k-devices.hh). In this part, you will let user processes access that in-memory file system via the SYSCALL_OPEN system call.

SYSCALL_OPEN takes two arguments, const char* pathname and int flags. Here’s how it should work for now.

The current memfile::initfs is unsynchronized (because the current kernel never modifies it), so you will need to add synchronization. Write up your synchronization plan.

Use make run-testmemfs to check your work.

Keep track of any changes required to your initial VFS design. Describe those changes briefly in your pset3answers.md file.

E. Execv

Parts D and E are independent.

Implement the SYSCALL_EXECV system call, which should replace the current process image with a fresh process image running a binary found on the memfs.

The user-level sys_execv wrapper passes three arguments to the kernel: %rdi contains const char* pathname, the name of the binary; %rsi contains const char* const* argv, an argument array; and %rdx contains int argc, the number of valid arguments in the argument array. The initial kernel system call implementation should:

Use make run-execallocexit to test execv without arguments. This isn’t a stress test; you might want to develop your own test to check for absence of memory leaks.

Then it’s time for argument passing. Your goal is to set up the new process so that its %rdi register contains argc and its %rsi register contains a pointer to strings equivalent to argv. For instance, make run-exececho should print

About to greet you...
hello, world

But passing arguments to a process isn’t trivial. You can’t just copy the input argv into the new %rsi register, because the memory pointed to by argv has been obliterated as part of the exec procedure! The kernel must copy the arguments to new user-accessible memory, and then map that memory into the new page table. But where? For a hint, compile and run this program:

#include <stdio.h>
#include <stdint.h>

int main(int argc, char** argv) {
    uintptr_t rsp;
    asm volatile("movq %%rsp, %0" : "=r" (rsp));
    printf("%%rsp 0x%lx\n", rsp);
    printf("argc %d\n", argc);
    printf("argv %p (%%rsp+0x%lx)\n",
           argv, reinterpret_cast<uintptr_t>(argv) - rsp);
    for (int i = 0; i < argc; ++i) {
        printf("argv[%d] @%p: %p (%%rsp+0x%lx) \"%s\"\n", i, &argv[i],
               argv[i], reinterpret_cast<uintptr_t>(argv[i]) - rsp,
               argv[i]);
    }
}

Setting up arguments is the most fiddly part of this problem set; it rivals the buddy allocator for potential for errors and confusion. Draw your argument layout carefully with pencil and paper, and think in advance about how you will test your code. (For instance, could you organize argument passing into a function that could be unit tested separately from exec?)

F. Shell

Run make run-sh. You now have a shell. If your work on Parts C and E is correct, you’ll be able to run command lines like echo foo | wc. If your work on Parts D and E is correct, you’ll be able to run cat emerson.txt or echo Hello > hi.txt; cat hi.txt. There’s no work to do for this part. Play around!

Turnin

Fill out psets/pset3answers.md and psets/pset3collab.md and push to GitHub. Then submit on the grading server.

Initial checkin: Your VFS design document is due by Monday 3/11.
Final checkin: You should be able to complete all parts by 11:59pm Monday 3/18, during spring break. (Happy break!) We won’t take off points for pset 3 until 3/25, but we will release pset 4 during break, and you will want to get started on it then.