MIT Operating System xv6 on Mac OS

When I play around xv6 on my Mac OS, I find the following link (http://moss.cs.iit.edu/cs450/assign-xv6.html) is very useful and many thanks Michael @ http://moss.cs.iit.edu/.

The following is directed from http://moss.cs.iit.edu/cs450/assign-xv6.html. (Please refer to the original web and acknowledge the author)

Assignment: xv6

Objectives

In this assignment you will be modifying and adding code to the xv6 kernel, in order to better understand how various process and file system related mechanisms are implemented in an actual operating system.

Cloning xv6

The version of xv6 you’ll be working on for this lab is hosted on BitBucket at https://bitbucket.org/michaelee/xv6.

Be sure to clone this version instead of the original one hosted at MIT — we’ve made some additions/changes for the exercises that follow. Your submission (described later) will also need to be generated from this specific repository.

Assuming you have Git installed on your machine, simply run the following command to clone the repository into a directory named xv6.

git clone https://michaelee@bitbucket.org/michaelee/xv6.git


Running xv6

If you are running a Unix-based operating system (e.g., Mac OS X or Linux), it should be quite easy to compile and run xv6 on the Qemux86 emulator. Instructions for Mac OS X and Linux are below.

If you are running Windows, it is technically possible to use Cygwin to build xv6 and to use a Windows-based Qemu package to test the kernel. This process is potentially a bit finnicky, however. Instead, I recommend installing Linux on your machine using the free VirtualBoxvirtualization package, then following the instructions below to get xv6 compiled and running within Linux (this way you’ll be running two layers of virtualization, which is pretty cool, too).

Here’s a super-short screencast that shows how to build/run xv6 on Ubuntu Linux.

OS X

To install the compiler toolchain and emulator for building and testing xv6, you should first install the MacPorts package. Follow the instructions on the website to do this.

After this is done, run the following commands in a terminal window to install the required tools (you’ll need to authenticate as an admin):

sudo port install i386-elf-gcc
sudo port install qemu


Next, do “make” to build xv6 (within the cloned directory), and “make qemu-nox” to start up the emulator and boot up the kernel.

Linux

First, use your distribution’s package manager to install the qemu-kvm package — on Debian/Ubuntu, the following command will do (assuming you have relatively up-to-date package sources):

sudo apt-get install qemu-kvm


To build xv6, edit Makefile (in the cloned repository) and uncomment the blank TOOLPREFIX variable assignment. Comment out or delete the other TOOLPREFIX line. I.e., make the following change:

# Cross-compiling (e.g., on Mac OS X)
#TOOLPREFIX = i386-elf-

# Using native tools (e.g., on X86 Linux)
TOOLPREFIX =


Next, do “make” to build xv6 and “make qemu-nox” to start up the emulator and boot up the kernel.

Windows

Follow the instructions here to install the latest version of Ubuntu in VirtualBox on Windows. When done, fire up a terminal and follow the Linux instructions, above.

Exercises

For this exercise you’ll add a new system call called getcount to xv6, which, when passed a valid system call number (listed in the file “syscall.h“) as an argument, will return the number of times the referenced system call was invoked by the calling process.

E.g., the following test program:

#include "types.h"
#include "user.h"
#include "syscall.h"

int
main(int argc, char *argv[])
{
printf(1, "initial fork count %d\n", getcount(SYS_fork));
if (fork() == 0) {
printf(1, "child fork count %d\n", getcount(SYS_fork));
printf(1, "child write count %d\n", getcount(SYS_write));
} else {
wait();
printf(1, "parent fork count %d\n", getcount(SYS_fork));
printf(1, "parent write count %d\n", getcount(SYS_write));
}
printf(1, "wait count %d\n", getcount(SYS_wait));
exit();
}


Will produce the following output (note that each character is output with a separate call to write in xv6):

initial fork count 0
child fork count 0
child write count 19
wait count 0
parent fork count 1
parent write count 41
wait count 1


HINTS

You will need to modify a number of different files for this exercise, though the total number of lines of code you’ll be adding is quite small. At a minimum, you’ll need to alter syscall.h, syscall.c, user.h, and usys.S to implement your new system call (try tracing how some other system call is implemented, e.g., uptime, for clues). You will likely also need to update struct proc, located inproc.h, to add a syscall-count tracking data structure for each process. To re-initialize your data structure when a process terminates, you may want to look into the functions found in proc.c.

Chapter 3 of the xv6 book contains details on traps and system calls (though most of the low level details won’t be necessary for you to complete this exercise).

TESTING

To test your implementation, you’ll run the getcount executable (when booted into xv6), which is based on the program above. Because the program depends on your implementation, however, it isn’t compiled into xv6 by default. When you’re ready to test, you should uncomment the line in the Makefile following the UPROGS declaration that builds getcount (delete the ‘#’ character in front of the string “_getcount“).

Note that while getcount only prints out counts for three different system calls, your implementation should support all the system calls listed in syscall.h. Feel free to add tests to the test program, located in getcount.c, for other system calls.

2. Increasing the maximum file size

xv6 uses an inode based filesystem where each inode contains 12 direct data block pointers and 1 single indirect block pointer, where a block “pointer” is just a 4-byte disk block number (indexed from the first sector on the drive). Because a block is 512 bytes large, the indirect block can hold an additional 128 block numbers, resulting in a maximum file size of 140 blocks, which equals a puny 70KB.

For this lab you’ll modify xv6 to change the inode structure so that it contains:

• 10 direct block numbers
• 2 single indirect block numbers
• 1 double indirect block number

Recall that a double indirect reference takes us to a block full of single indirect block numbers. Using this scheme, we can address a total of 10+2×128+1×128×128=16650 blocks, or just over 8MB.

HINTS

You will need to modify, at minimum, the file.h, fs.h, and fs.c files. Most of your work will take place in the bmap function (found in fs.c), which takes a pointer to an in-memory inode and a logical block number (i.e., an offset from the start of the file), and returns the corresponding disk block number. Note that bmap is called when reading and writing a file, so if it is given a logical block number beyond the current end of file (but within the maximum file size), bmap will allocate the necessary disk block(s) and update the inode structure(s).

struct dinode, in fs.h, defines the on-disk inode structure, and struct inode, in file.h, represents an in-memory inode. Theaddrs component of these structures is particularly important; its first NDIRECT entries are disk block numbers for data blocks (when allocated), and the last three entries will hold the disk block numbers for our indirect blocks. You’ll need to change / add to the constantsNDIRECT, NINDIRECT, and MAXFILE (in fs.h), which are specified in numbers of blocks.

bmap makes use of balloc to allocate new (zeroed) disk blocks, bread to read the contents of a disk block, and brelse to release a lock on a block. We don’t have time to cover all the details of how and why these locks are used, but you do need to ensure that all blocks you read (using bread) are released. bread reads disk blocks into struct buf structures (defined in buf.h), and raw data can be accessed via the structure’s data component. Finally, log_write must also be called with a pointer to each struct buf that contains modified data.

Read chapter 6 of the xv6 book, focusing on the “Block allocator” and “Inodes” sections, for useful information. You should also read through the original bmap first, to make sure you understand how it works.

TESTING

To test your program, you’ll run the program bigtest (when booted into xv6), which will try to write to, then read from as big of a file as it can. Without any changes, it should report that it can write 140 sectors. After your changes, it should report that it can write 16650 sectors.

Submission

You will be submitting all your work as a set of patch files that we can apply to the original source repository. A patch file contains a listing of all the changes you’ve made to the files in the repository (compared to some past version), and is much more efficient to transmit than the entire repository itself.

To generate your patch file, you will need to first commit all your work in git. You can choose to either commit multiple times (e.g., once for each exercise) or just once for the entire assignment — it makes no difference to us, as we’ll just apply all the patches at once.

To commit your work, run the following command inside the directory you cloned (customizing the commit message, if you wish):

git commit -am "Completed assignment 5"


After this, you can generate the patch files with the following command:

git format-patch 6e0d8f2


The 6e0d8f2 sequence identifies the “tip” of the original repository you cloned. The command will generate one (numbered) patch file per commit. For instance, if you committed once for each exercise, the command might produce the following output (the filenames contain the first line of your commit message):

\$ git format-patch 6e0d8f2