Problem set 3: Files

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 Wednesday 3/6 at 12 noon.
Final checkin: You should complete all parts by 11:59pm on Wednesday 3/20.

Preparation

Update your code from our handout repository:

$ git pull handout main
$ git push

A. Initial read and write system calls

Take a look at p-cat.cc, and then run make run-cat. Type some stuff and press the return key. 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. (You may want to use the vmiter::range_perm functions.) Also check for overflow: the memory range implied by the buf and sz arguments must not wrap around the address space.

    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 11:59pm on Monday 3/7 and check it in to your repository. You can use Markdown (psets/pset3vfs.md), plaintext, or a 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 be less complicated than FreeBSD! 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 <cstdio>

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.

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 an array of 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 pointer into the new %rsi register, because that pointer’s value was only meaningful in the old process—the memory it pointed to has been obliterated as part of exec! The kernel must copy the arguments to new user-accessible memory, map that memory into the new page table, and initialize %rsi with a new value pointing into the copied arguments. Where should the arguments go? For a hint, compile and run this program on a Linux or Mac OS host:

#include <cstdio>
#include <cstdint>

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!

Optional: Unix-domain sockets and file descriptor passing

Create a simplified version of Unix domain sockets (see here and here for more information about Unix domain sockets). At a high level, Unix domain sockets are similar to pipes. Both abstractions allow two processes to exchange messages with each other. However, a Unix domain socket is identified by a string name. A server process opens a socket with the given name; a client can send a message to the server by connecting to the socket and sending data to that socket. Unix domain sockets are interesting because they allow a process to send a file descriptor to another process!

The specifics of passing file descriptors over real Unix domain sockets are a bit convoluted. For the optional work, modify Chickadee to support a simplified version of file descriptor passing. Allow a client process to:

Modify Chickadee to allow a server process to:

Write a p-uds.cc program to test your work! Be sure to test for error cases like a client passing a non-valid fd to a Unix domain socket.