A. Protect read and write system calls
Our handout code includes:
- Several new system call constants and system call wrappers.
- Implementations of
SYSCALL_READ
(reading only from the keyboard) andSYSCALL_WRITE
(writing only to the console). - A new suite of wait queue helper functions,
waiter::block_until
, which block until until a predicate becomes true. Look over the implementations of these functions. - A
cat
program.
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
.
The SYSCALL_READ
implementation blocks until a line is available to read. It
uses a waiter::block_until
function and a C++
lambda to
detect this condition. Look at the assembly to see how this is compiled.
Your task: The SYSCALL_READ
and SYSCALL_WRITE
implementations do not
check their arguments for validity, and are thus seriously dangerous. Change
these implementations 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 work. By the end of this part, your Chickadee should support:
- The
dup2
andclose
system call implementations. - A per-process file descriptor table, initialized for the first process as in
Unix (i.e., fds 0–2 refer to the keyboard/console) and copied across
fork
. - File structures.
- A vnode abstraction that can support different kinds of file.
- A class derived from vnode for the keyboard/console file system.
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:
- What types of objects make up your VFS layer?
- What are the names and types of their methods?
- What are the relationships among the objects?
- How is memory for each kind of object allocated and freed?
- What synchronization invariants must VFS callers obey? For instance, which objects have locks? Is there a lock order necessary to prevent deadlock?
- What future OS changes might require updates to the VFS layer? Consider especially support for multithreaded processes.
- Which functions rely for safety on checks made elsewhere in the system?
- Which VFS functions, if any, can block?
Please write up the design document by Monday afternoon 3/5 and post a
private question to Piazza with the document. You can use Markdown
(psets/pset3vfs.md
), plaintext, or Google doc. 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.
OS/161:
kern/include/fs.h
,kern/include/vnode.h
xv6:
file.h
xv6 implements the object-oriented aspect of the VFS layer in a particularly simple way: each “device class” supports just two operations, read and write.
FreeBSD:
sys/sys/file.h
,sys/sys/vnode.h
,sys/sys/filedesc.h
The object-oriented aspect is defined in
file.h
, starting around here.Linux:
include/linux/fs.h
,include/linux/fdtable.h
Some places to concentrate:
struct files_struct
(a file descriptor table) is defined infdtable.h
.struct file
(an open file) is defined around here infs.h
.struct inode
(a “vnode” structure) is defined around here infs.h
. The object-oriented aspects of the VFS layer, namely the abstract operations for which each file system provides its own implementations, are broken into two parts,struct file_operations
andstruct inode_operations
; they are defined around here.
Note on keyboard/console
We referenced a “keyboard/console file system” above. That might sound surprising, but in fact it follows Unix’s typical behavior. Try compiling 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.
C. Pipes
Implement the SYSCALL_PIPE
system call. Test your work with make
run-testpipe
.
Some notes:
The
sys_pipe
wrapper function (provided for you) expects the kernel to return either a negative error code on error, or the (positive) 64-bit valuerfd | (wfd << 32)
, whererfd
andwfd
are file descriptor numbers. The wrapper function translates this calling convention into the more usualpipe(int pfd[2])
convention.Aside from normal behavior, the
p-testpipe
program tests that reading from a write end, or writing to a read end, returnsE_BADF
; that reading from a pipe with closed write end returns 0 (EOF); that writing to a pipe with closed read end returnsE_PIPE
; and various properties of file descriptor inheritance to children.Typically pipes are implemented using a bounded buffer abstraction. We built a correctly-synchronized bounded buffer in CS 61; you may want to refer to that.
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
The Chickadee kernel image contains a set of binaries—things like
obj/p-allocator
, the allocator process, or obj/p-testpipe
. These binaries
essentially make up 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
pathname
is a null-terminated string. The kernel must validate that the pathname is in valid memory; if not, returnE_FAULT
. You’ll need to implement a new validation helper function, because unlike withread
andwrite
, the size of the string isn’t passed explicitly!The kernel searches for a
memfile
with the givenpathname
in thememfile::initfs
array, usingmemfile::initfs_lookup
. If thepathname
isn’t found:- If the
OF_CREATE
flag is present, the kernel should create a new empty file with that name, returningE_NOSPC
if out of room. - Otherwise, the kernel should return
E_NOENT
.
- If the
If the
OF_TRUNC
flag is present, the kernel should set the file’s length to zero.Finally, the kernel should add a new file descriptor to the process’s file descriptor table. This new file descriptor should refer to the given
memfile
.- The file descriptor is open for reading and/or writing depending on
whether
OF_READ
and/orOF_WRITE
are present in the open flags. An attempt to read from a file descriptor open only for writing, or to write to a file descriptor open only for reading, should returnE_BADF
. - Writing beyond the end of file should extend the file’s length.
- The file descriptor is open for reading and/or writing depending on
whether
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:
Validate its arguments: the
pathname
argument should be a valid user-readable null-terminated string. (Forargv
andargc
, see below.)Look up the
memfile
named bypathname
. ReturnE_NOENT
if not found, andE_NOEXEC
if the file doesn’t look like a valid binary.Create a new register set and page table, in the same way that
process_setup
does. If this fails at any point (because of out-of-memory, for example) free any allocated memory and return the appropriate error.Install the new page table and register set in the
proc
, and useset_pagetable
to install the page table into the CPU. Note that the file descriptor table and any child processes do not change.Free/dereference the old page table and all memory referenced therein.
Resume the process (probably using
proc::yield_noreturn
).
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
process! 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]);
}
}
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
. 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.
Final checkin: Turn in all parts by 11:59pm Monday 3/12.