This page last updated: December 2018.
The exercises described on this page build on the ideas that you have developed in the earlier labs on context switching and paging, but also incorporate new ideas that were introduced in the Week 7 lecture about capabilities. You should make sure that you have completed the earlier labs, and reviewed the slides from the lecture before proceeding. Although the implementation of capabilities presented here is not as sophisticated or complete, it is important to note that the overall approach is very much informed and inspired by the capability system in the seL4 microkernel; many more details about that system can be found at https://sel4.systems.
Step 1: Getting set up
To begin, you will need to download, unpack, and build the source code for the simple kernel and user-level demo with capability-based system calls that was the main focus of the capabilities lecture. This code is packaged as caps.tar.gz and should be installed in the same way as previous files: place a copy in your llp directory; unpack using tar xvzf caps.tar.gz; and then run make in the new caps folder.
In fact, as you've likely guessed based on past exercises, you can use make run from within the caps folder to build and run the demo program in a single step. If you've installed everything correctly, you should see a window that looks something like this:
Note that there is a "spinner" in the top right hand corner that is updated by the timer interrupt handler. This is a simplified version of the clock exercise that was suggested as a stretch goal in the context switching lab. Its primary purpose here is to provide an indication that the kernel is still running, even when no output appears on screen. But those who did not get a working clock for the switching demo may find some useful hints about how to accomplish that by studying the implementation of this simple spinner.
Step 2: A guided tour of the caps folder
This lab draws on the techniques and ideas that have been introduced in the previous switching and paging labs. But with all the extensions and modifications that we've made in the course of those exercises, you're probably finding that the code base is getting a little tangled and hard to navigate. So we're going to take advantage of this new lab to do a little clean up work, reorganizing the code and breaking it in to smaller pieces with a more clearly defined purpose or focus. In this section, we'll provide a brief tour of the important files.
For starters, I recommend that you run make clean in the caps directory before you proceed; this will clear away compiler-generated files so that we can focus on the source code. Of course, you can always regenerate the other files later by repeating the make or make run commands.
Now we'll begin our tour for real in the kernel folder; I encourage you to follow along by reviewing each of the listed files in an editor (or using a tool like less, or similar), as you see fit:
Phew, quite a lot to take in there! Fortunately, the changes to our user folder are a little easier to follow (it helps that we didn't have much code there to begin with):
Finally, you might have noticed that the kernel and user folders inside the caps directory are now joined by a third folder called capio. This contains source code for a simple, user-level library for performing I/O via window capabilities. It is similar in purpose to the userio library that you have used previously, except that it allows for providing a specific window capability reference as part of each call. (A brief description of this library is included in the capabilities lectures.)
That's a lot of information to digest. But remember that you can always come back to check these details again later as you need them.
Step 3: Fixing those TODOs
As mentioned previously, there are a few TODO items in kernel/syscalls.c. Now is the time to start filling them in! Essentially, what you are being asked to do here is to complete the implementations of some system calls. The supplied code already includes the code for system calls whose implementation was shown in the lecture, so you can use those as starting points/inspiration for the missing system calls. Each of the TODO items includes comments to describe what that particular system call is expected to do, so we will not waste space repeating that information here. All of the code that is needed to support these system calls in kernel/init.S, user/syscalls.h, and user/userlib.s has already been provided so that you can focus your attention on kernel/syscalls.c. But of course you're welcome to look at the other files if you want to check any details there or to make sure you understand all of the steps that are needed to get from user-level code to the implementation of a system call.
We'll start with the following TODO items. I recommend that you work through them in the order they are listed, testing at each stage:
There are some other TODO items not included in the list above; we'll come back to finish these off later on in Step 5.
Step 4: Adding a new type of capability
Add a new capability type, TimerCap, and an associated system call, getTicks(tcap), that a user-level process can invoke to access the current timer value via a reference, tcap, to a TimerCap. In the distributed code, the timer is stored in the ticks variable inside the code for the timer interrupt handler; you'll need to make this a global variable so that your system call implementation can access it.
Some operating systems block access to accurate timer information from user-level processes to prevent timing attacks. One way to address this is to limit the resolution of the timing information. Extend your implementation of TimerCap to include a number of bits that will be zero in every timer reading that is returned through that capability. For example, if the number of bits is set to 3, then actual timer values of 0, 1, 2, 3, 4, 5, 6, and 7 will all be reported back to the holder as 0. The holder will still be able to see that the timer is advancing, but will not have access to the highest available resolution.
Note: Remember that this is just an exercise in using capabilities: I'm not really proposing it as a serious practical solution to avoid timing attacks, nor am I claiming that timing attacks are a concern for us in this lab, especially because the tick count in this implementation does not provide a particularly high resolution to begin with!
Step 5: Fixing some more TODOS
Now it is time to finish off the TODO items in kernel/syscalls.c. The remaining items on the list all have to do with the data structures for memory management that we first encountered in the paging lab:
The supplied user code already includes some simple uses of these system calls that you can use for testing (based on the example that was presented in the lecture), but of course you are free to make up your own examples for more extensive testing and to demonstrate your understanding of the relevant course objectives.
Step 6: Adding a new system call to an existing capability type
Add a new system call, invoked as remaining(ucap) from user-level code, that can be used to determine how much unallocated memory is left in the untyped capability specified by ucap. That description makes it sound very simple, but it might take a little bit more work to get this up and running!
Step 7: Improving an existing operation
Using the WindowCap capability type, we can print a string of characters on an output window using a sequence of system calls, one for each character. While this is enough to get the job done, it is not very efficient or practical to use so many system calls for such a simple task! Wouldn't it be better if we could use a single system call to pass and display a whole string of characters at once?
To implement this we need a region of memory that both the user-level program and the kernel can use to communicate with one another. From the kernel's perspective, we can handle this by adding a new field, unsigned* buffer, to each struct Proc object that is initialized to null. For the user-level side, we can provide a system call allocBuffer(ucap, addr) that can be invoked to allocate a page of memory (from the untyped memory specified by ucap) that is mapped into the address space of the user-level process at the specified address, addr. Of course, this operation will fail if there is a problem with the capability (wrong type, not enough space, etc.) or the address (in KERNEL_SPACE, already mapped, etc.), or if a buffer has already been allocated for this process. But if it succeeds, then a pointer to the newly allocated page will be saved in the buffer for the process.
The next step is to add a new system call, printBuffer(wcap) that will print the string in the process buffer in the window specified by the given WindowCap, wcap. A user-level process will typically invoke this system call after it has filled the buffer, via the address that it specified in the allocBuffer() call. On the kernel side, we have to check not only that wcap is valid (and, presumably that it includes the permission to printing a single character), but also that the invoking process has previously allocated a buffer. We'll assume that the user-level process marks the end of the string that it wants to be displayed by adding a null byte after all the characters, thereby following the time-honored (and highly error-prone) tradition of C. This creates another obligation for the kernel, because if the user-level program "forgets" to add that null byte, whether by mistake or design, then an over-eager implementation of printBuffer() might be tricked into reading past the end of the buffer page, and trigger a kernel page fault. That would be pretty embarrassing, so make sure your implementation stops before it goes past the end of the page! If you like, you could even add another field to the WindowCap capability to set a "maximum message length" value as an extra badge. Of course, the kernel should also be ready to ignore that value if it is more than the length of the buffer page ...
[The technique described here still has some potential performance problems because it forces the user-level process to copy data into the buffer area before making the call to printBuffer(). You could imagine an alternative approach that provides user-level processes with a system call printString(wcap, addr) where addr can be an arbitrary address that points to a string in the caller's address space. The kernel, of course, will be able to read the characters stored at that address. But again, our poor kernel will have to careful and protect itself against misbehaving user-level programs that supply an invalid addr that would cause the kernel to page fault if it tried to access that memory. Happily, the kernel also has access to the page directory and page table for the process, so it can check that the address is valid before attempting the operation. But this will take a fair bit of extra work ...]
Note that the buffer technique described above is inspired, in large part, by the approach that is used in seL4 to allocate an `IPC buffer' to threads that need to send or receive messages that are more than a few words in length, and hence cannot be stored completely in CPU registers.
Step 8: Let's retype that ... (a stretch goal)
You may have noticed that the various functions for allocating objects from an untyped memory area (e.g., allocCspace, allocUntyped(), allocPage(), etc.) all have a pretty similar structure. In addition, there are often situations where we need to make multiple allocator calls in a row to allocate a sequence of objects. One way to tackle these problems is to collapse all of the allocators into a single system call of the form:
retype(ucap, type, bits, slot, num)
Your task now, of course, is to implement this all-powerful allocator system call. It will take a fair bit of work, but then you will also be able to throw away all those close-to-duplicated allocXXX() functions, and it will also be much easier after this to add support for allocating new types of object. In addition, you won't need to rewrite all your existing user level code to use the new retype() call: instead, you can just write simple wrappers in user/syscalls.h that implement each of the original, more specialized allocators as special cases of retype().
Once again, we should also acknowledge that the retype() system call is inspired by a system call of the same name in the seL4 microkernel.
Step 9: What's next?
Really? That was quite a lot of work, and you still want more? Of course, I'm glad to hear that, but I'd still suggest this might be a good time to take a break. In your idle moments, however, you might still want to be considering questions like the following:
If you have enjoyed the material in this lab, you are strongly encouraged to check out https://sel4.systems to see how a substantially more complete capability abstraction fits in to a real-world microkernel implementation (that has also been the subject of a successful formal verification effort)!