Assignment 3

Paul Krzyzanowski

February 11, 2015

Due Friday, February 27, 2015 6:00 pm via sakai
Due Saturday, February 28, 2015 11:59 pm via sakai

Assignment 3 FAQ

Introduction

Your assignment is to download and build the xv6 operating system and boot it on an x86 emulator. You will add a new system call called trace, which turns console-based system call tracing for the calling process on and off. The system call also reports the total number of system calls called by the process since it started.

Group size

This assignment entails writing only a miniscule amount of code. Given the large class size, however, you may work on this assignment in a group comprising up to five members. Be sure to indicate the group members clearly in your report.

Groups of four or more

If you have over three members in your group, you must implement the optional part of the assignment: the csinfo system call, which returns the number of context switches that the process has experienced so far.

What is xv6?

xv6 is a slimmed-down, simplified operating system that is a loosly-based reimplementation of the UNIX sixth edition (v6) kernel, written in standard C and for the Intel x86 architecture. The original source for UNIX v6 was written in a pre-standardized version of C that uses constructs that will not be accepted by today’s compilers. Moreover, it was written with the PDP–11 architecture in mind.

It was designed at MIT as a small, easy-to-understand operating system that is suitable for teaching. For information about xv6, take a look at its home page at MIT. A detailed description of the structure of xv6, including its system calls, file system, and memory management can be found in the xv6 book:

xv6 installation instructions

There are several ways to get xv6 up and running. It can run natively or through one of several x86 simualtors. Here, I provide instructions for running it under the QEMU emulator under Linux as well as installing Linux on a virtual machine if you are running a system other than Linux or don’t want to install extra stuff on your Linux installation.

QEMU is an open source machine emulator and virtualizer. It allows you to run software for one machine on a different machine architecture. It also makes it easy to run and debug opearating systems since the complete operating system just runs as another process on your system.

You’re welcome to search for other instructions, use other virtual machines, or other simulators. I tested the process on my Mac but expect it to work on other operating systems. You’ll have to search out other instructions if you want to compile and run xv6 on an emulator directly on Windows or OS X. You can check this out for instructions on running xv6 directly on Windows. I have not tried it.

Running xv6 on the iLab machines

Bill Katsak has modified the Makefile to point to the QEMU installation in his directory on the iLab machines. The entire xv6 package can be obtained from his posting to github. To install it into a directory called xv6, run:

git clone http://github.com/wkatsak/xv6

Then go to step 11 to compile and run it.

This version of xv6 contains:

a. A patch that configures QEMU for iLabs

b. A patch that adds a halt() system call and a shutdown command (this is very useful when running “make qemu-nox” in an ssh window, because otherwise there is no way to kill it other than opening up another terminal, finding the pid, and issuing a kill. With this patch, you execute “shutdown” and QEMU dies.

c. A patch to the makefile and an extra helper script to pack up the modifications on a particular branch as patches and tar them up for submission.

Installing Linux on a virtual machine (VM)

Skip these steps if you are already running Linux and just want to install git and QEMU directly on Linux. Skip these steps also if you plan to use a cross-compiler and run git and QEMU directly on Windows or OS X. Go directly to step 8.

Step 1. Install VirtualBox

Download VirtualBox. You will be presented with a list of packages. Download the version suitable for your system (e.g., VirtualBox 4.3.20 for OS X host).

Run the installer to install VirtualBox.

Step 2. Create a virtual machine

Run VirtualBox and click on New (top left icon) to create a new virtual machine. Select the following options:

  • Name: Linux (or whatever you want)

  • Type: Linux

  • Version: Ubuntu 64-bit

[press Continue]

  • Memory Size: 1024 MB

[press Continue]

  • Virtual Hard Drive: 8 GB

[press Continue]

  • Hard drive file type: VDI

[press Continue]

  • Select Dynamically allocated

[press Continue]

  • File location & size: Pick a location & name for the drive

You’re done. The virtual machine is set up, powered off, and no operating system is yet installed.

Step 3. Download Ubuntu Server

Download Ubuntu. I downloaded Ubuntu 14.04.1 LTS 64-bit - recommended. xv6 on QEMU will work equally well with other configurations of Ubuntu or other Linux distributions. You really won’t need 95% of the stuff that gets installed.

The next page asks you for money. Select the Not now, take me to the download link if you don’t want to donate.

You now downloaded a disk image of the server: ubuntu–14.04.1-desktop-amd64.iso

Step 4. Prepare to install Linux (Ubuntu distribution)

Go back to VirtualBox.

  • Select your virtual machine (you’ll probably have just one: Linux - Powered off).
  • Go to Settings (top left, to the right of New).
  • Select Storage in the pop-up window (fourth icon from left).
  • Select the CD/DVD rom on the left (Empty) and click the CD/DVD icon on the right.
  • You’re prompted for a disk file.
  • Select the Ubuntu distribution iso file that you just downloaded.

Power on the virtual machine by clicking the Start button in the list of top left icons.

A window will appear that shows the console of your virtual machine.

Step 5. Install Ubuntu

  • Click Install Ubuntu
  • Select Erase disk and install Ubuntu when prompted.
  • Go through the prompts on the next few pages and then be patient.
  • After several minutes, you’ll be told Installation is complete.
  • Restart the system by clicking Restart now.

When you restart, you’ll see a message about mouse pointer integration. You can close it and then press Host-I to turn off mouse pointer integration since you don’t need it. The help message will tell you what the Host key is (it’s the command key on a Mac).

Step 6. Start the terminal in Linux

You can get a terminal from the Ubuntu desktop by pressing ctrl-alt-T. For basic info on using the terminal and command line, see here

Step 7. Optional - if you want to remove the desktop

Edit /etc/default/grub with your favorite text editor (e.g., vim). GRUB is the bootloader and you’re telling it to pass a startup environment setting to Linux when it boots up.

Change the line from: GRUB_CMDLINE_LINUX_DEFAULT=“quiet splash”

to GRUB_CMDLINE_LINUX_DEFAULT=“text”

Now update the bootloader and reboot:

sudo update-grub
sudo reboot

Start here if you just want to install git and QEMU on your existing Linux distribution

Step 8. If you don’t have git installed, install git

Start the terminal and run the command:

sudo apt-get install git

Step 9. Install the x86 emulator, QEMU

Start the terminal and run the command:

sudo apt-get install qemu-system-x86

Step 10. Install xv6 source code

Start the terminal. Create a directory where you want the xv6 source tree to live and download the xv6 source.

mkdir src
cd src
git clone git://pdos.csail.mit.edu/xv6/xv6.git

This will install the source tree in a directory callled xv6.

See http://pdos.csail.mit.edu/6.828/2014/tools.html.

Step 11. Compile and run xv6

Start the terminal, go to the place where you installed the xv6 source and run make to compile it, start the emulator, and run it. This compiles the kernel as well as the various commands and runs the kernel in the emulator. THe first process, init, starts the shell (sh).

cd src/xv6 (or wherever you installed xv6)
make qemu-nox

If all went well, you will see output similar to this:

qemu-system-i386 -nographic -hdb fs.img xv6.img -smp 2 -m 512 
xv6...
cpu1: starting
cpu0: starting
init: starting sh
$

The line with the $ sign is the shell prompt for a command from the shell program (sh) running as a process under xv6, which is running on an emulated x86 processor.

There are several options for compiling and running xv6

make qemu
builds everything. Starts QEMU with the VGA console in a new window and the serial console in your terminal. You can exit this by either closing the VGA window or entering ctrl-a x in your terminal.
make qemu-nox
builds everying. Runs only the serial console. I use this option since I ssh into my Linux systems. Exit QEMU by pressing ctrl-a x in the console.
make qemu-gdb and make qemu-nox-gdb
Same as the two above but here QEMU waits for a gdb (GNU debugger) connection.

For this assignment, you are unlikely to write code that will cause the kernel to die and you probably will not need to do register-level debugging or setting breakpoints. As such, you can probably do without gdb or QEMU’s breakpointing and register inspection capabillities.

To switch between the QEMU console (running xv6) and the QEMU emulator command interface, type ctrl-a c. This takes to you the QEMU command mode where you can type QEMU commands, such as:

info registers
to show CPU registers
x/10i $eip
show the next 10 instructions at the current instruction pointer
system-reset
reset & reboot the system
quit
exit the emulator (quit xv6)

The last of these commmands is probably the only one that you will use. Type ctrl-a c again to get back to the console (unless you ran quit)

Step 12. Test it out

Note: commands are really minimal and reside at the root of the file system. They include: cat, echo, forktest, grep, init, kill, ln, ls, mkdir, rm, sh, stressfs, usertests, wc, and zombie.

All commands are in the root directory and your shell’s current working directory is the root as well. Run the ls command to see all the files:

ls

Try running: cat README | grep xv6

which will search for all lines containing xv6 in the file README. You will note that all the commands are dramatically feature-poor compared with conteporary Linux/BSD/UNIX equivalents. The ls command, for example, accepts no flags.

Exit to the emulator via control-A C. Exit the emulator with the quit command.

To create a file for submission

Prior to making any changes, create your own branch of the code:

cd xv6
git checkout -b mods

This will create a branch called mods.

Now edit your files. When you are done, commit changes via:

git commit -a

If you’re running this on iLab machines, Bill Katsak’s modified makefile makes it easy to create a tar file containing modified files. To get a help message, run

make submit-help

To create a submission file, run

make submit netids=NETID1-NETID2 name=SECTION_NAME base=BASE_BRANCH

For example, if you have three students with netIDs abc, def, and ghi, use:

make submit netids=abc-def-ghi 3 base=master

This will create a gzipped tar file (tgz suffix)

If you get an error that states:

Error:  is an invalid branch!

There’s a good chance that Bill didn’t fix the Makefile on github yet. You can fix it yourself by editing the Makefile with a text editor. Go to line 292 where you’ll see the line:

@./package_patches.sh $(netid) $(name) $(base)

Change “netid” to “netids”:

@./package_patches.sh $(netids) $(name) $(base)

and again run 

make submit netids=abc-def-ghi name=3 base=master

This will greate a patch file with a name like:

3-abc-def-ghi.tar.gz

This is the file that you need to submit along with your write-up.

If you are not using the iLab machines, you can download the package_patches.sh shell script and run it as:

bash ./package_patches.sh netids name base

for example:

bash ./package_patches.sh abc-def-ghi 3 master

package_patches.sh

Your assignment

Your assignment is to add a new system call called trace. Its syntax is

int trace(int)

When called with a non-zero parameter, e.g., trace(1), system call tracing is turned on for that process. Each system call from that process will be printed to the console in a user-friendly format showing:

  • the process ID
  • the process name
  • the system call number
  • the system call name

Any other processes will not have their system calls printed unless they also call trace(1).

Calling trace(0) turns tracing off for that process. System calls will no longer be printed to the console

In all cases, the trace system call also returns the total number of system calls that the process has made since it started. Hence, you can write code such as:

printf("total system calls so far = %d\n", trace(0));

How to add a system call

You need to touch several files to add a system call in xv6. Look at the implementation of existing system calls for guidance on how to add a new one. The files that you need to edit to add a new system call include:

user.h
This contains the user-side function prototypes of system calls as well as utility library functions (stat, strcpy, printf, etc.).
syscall.h
This file contains symbolic definitions of system call numbers. You need to define a unique number for your system call. Be sure that the numbers are consecutive. That is, there are no missing number in the sequence. These numbers are indices into a table of pointers defined in syscall.c (see next item).
syscall.c
This file contains entry code for system call processing. The syscall(void) function is the entry function for all system calls. Each system call is identified by a unique integer, which is placed in the processor’s eax register. The syscall function checks the integer to ensure that it is in the appropriate range and then calls the corresponding function that implements that call by making an indirect funciton call to a function in the syscalls[] table. You need to ensure that the kernel function that implements your system call is in the proper sequence in the syscalls array.
usys.S
This file contains macros for the assembler code for each system call. This is user code (it will be part of a user-level program) that is used to make a system call. The macro simply places the system call number into the eax register and then invokes the system call. You need to add a macro entry for your system call here.
sysproc.c
This is a collection of process-related system calls. The functions in this file are called from syscall. You can add your new function to this file.

Per-process state is stored in a proc structure: struct proc in proc.h. You’ll need to extend that structure to keep track of the metrics required by this assignment. You’ll also need to find where the proc structure is allocated so that you can ensure that the elements are initialized appropriately.

When you implement your trace call, you’ll need to retrieve the incoming parameter. The file sysproc.c defines a few helper functions to do this. The functions argint, argptr, and argstr retrieve the nth system call argument, as either an integer, pointer, or a string. argint uses the esp register to locate the argument: esp points at the return address for the system call stub.

Implementation Hints

Step 1

Write a test program. Add it to the Makefile so that it will be compiled and built whenever you run make.

In the Makefile, add your program (e.g., try.c) to the list of user commands in the EXTRA= section. That should be all you need to do to that file.

Beware that programs don’t have access to the typical stdio library that you expect to find on most systems. You’ll have many of the functions you expect but some of the behavior might be different. For example, printf accepts an initial parameter that is the output stream: 1 represents the standard output and 2 represents the standard error stream. There is no FILE* type and no fopen, fclose, fgets, etc. calls. Look through usertests.c for examples on how all of the system calls provided with xv6 are used.

Step 2

Add system call tracing to the kernel. Print a message identifying every system call that is requested by any process as well as the process ID and process name. You do not need to print the arguments to the system calls. When you run any program, including the shell, you will see output similar to this:

...
pid: 2 [sh] syscall(5=read)
pid: 2 [sh] syscall(5=read)
pid: 2 [sh] syscall(1=fork)
pid: 2 [sh] syscall(3=wait)
pid: 3 [sh] syscall(12=sbrk)
pid: 3 [sh] syscall(7=exec)
pid: 3 [try] syscall(20=mkdir)
pid: 3 [try] syscall(15=open)
pid: 3 [try] syscall(16=write)
pid: 3 [try] syscall(21=close)
pid: 3 [try] syscall(2=exit)
pid: 2 [sh] syscall(16=write)
pid: 2 [sh] syscall(16=write)
...

Printing messages to the console is easy: use the cprintf function, which works just like the normal Linux printf function. For example:

cprintf("hello, I'm number %d\n", num);

Step 3

Seeing a trace of all system calls for all processes is a bit overwhelming and not particularly useful. In step 2, you will restrict this output to a single process.

Create a new system call called trace(int). This turns console-based system call logging on and off for only the calling process.

Extend the proc structure (the process control block) in proc.h to keep track of whether tracing for the process is on or off. Be sure that the elements are cleared (initialized) whenever a new process is created.

In implementing your system call, you’ll need to access the single parameter passed by trace. Use the helper functions defined in syscall.c (argint, argptr, and argstr). Take a look at how other system calls are implemented in xv6. For example, getpid is a simple system call that takes no arguments and returns the current process’ process ID; kill and sleep are examples of system calls that takes a single integer parameter.

Step 4

Add system call counting. Be sure to count calls on a per-process basis. You will need to keep track of this in the process control block, the proc structure.

Optional (mandatory for groups of 4 & 5 members)

You will now add another system call to xv6. This one is called csinfo:

int csinfo(void);

It returns the number of context switches that took place in the process from the time it started.

Implementing this will require keeping an additional counter in the proc structure for the file.

To test it out, try code along the lines of

int cs1, cs2, cs3, cs4;
cs1 = csinfo();
cs2 = csinfo();
sleep(1);
cs3 = csinfo();
sleep(1);
cs4 = csinfo();
printf(1, context switch counts = %d, %d, %d, %d\n", cs1, cs2, cs3, cs4");

The values of cs1 and cs2 will usually be the same since there will usually not be a context switch between them (the data is available immediately so the operating system has no need to block the process). Since a context switch may take place at an arbitrary time, it is possible that cs2 might be one greater than cs1 but it will, of course, never be more than that. The sleep() call will definitely put the processor to sleep (for one second), so cs3 will be one greater than cs2 and cs4 will be one greater than cs3.

Submission

Be sure to indicate all members of your team in the opening comments in your code. If it takes us effort to figure out whose program this is, you will lose points. Only one team member should submit the assignment.

Do not submit the entire set of sources for xv6! Submit only:

  • the files that you modified. If you’d like, you can submit the package patch file as discussed earlier.

  • any new files that you added

  • your test program(s)

  • your modified Makefile

Also, prepare and submit a report (plain text, pdf, or HTML in sakai only!). The report should

  • Identify the group members

  • Indentify if you did the optional component

  • Explain your implementation

  • Explain how you tested your work

Check your submission!

Before submitting, make sure that all the components are there. If I can’t compile any part, you will get no credit. Download the original source into a new directory, copy your list of modified files, and run make to ensure that everything works. The few minutes you spend doing this will be well worth the time versus the agony of getting a zero on an assignment because you forgot a file!

If you created a patch file, untar the package:

tar xvzf 3-abc-def-ghi.tar.gz

Find the .patch file that is extracted and apply it:

git apply --stat your-patch-file.patch

to make sure that your patches to the source are indeed present.

Don’t miss the deadline

Submit your assignment to sakai. Don’t wait until the final hour! Late submissions will not be accepted.