Spring 2012 -- Junfeng Yang

Homework 1 is due Wed 2/1 at 12:01 AM ET.

Submit your solutions electronically via Courseworks. Refer to the homework submission page on the class web site for additional submission instructions.

Written Assignment (40 pts)

Exercise numbers X.Y refer to the exercise problem Y in Chapter X in the course textbook, Modern Operating Systems. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.

  1. 1.3
  2. 1.7
  3. 1.13
  4. 1.18
  5. 1.25
  6. The issue of resource utilization shows up in different forms in different types of operating systems. List what resources must be managed carefully in the following settings: a. Mainframe or minicomputer systems. b. Workstations connected to servers. c. Handheld computers
  7. Write a C function that prints the return addresses of all functions currently on the stack.

Programming Assignment: Booting a PC (60 pts)

This programming assignment is split into three parts. Part A concentrates on getting familiarized with x86 assembly language, the QEMU x86 emulator, and the PC's power-on bootstrap procedure. Part B examines the boot loader (bootasm.S and bootmain.c) for the xv6 kernel. Finally, Part C delves into the xv6 kernel itself.

One purpose of this assignment is to test whether you meet the prerequisites of this course and to warm you up for future kernel programming assignments.

You do not need to turn in any answers except code for the exercises in this assignment, but you must go through them for your own understanding and preparation for the exams.

Software Setup


Follow these instructions to install QEMU.

To get the xv6 source code for this assignment, run the following command

$ git clone http://debug.cs.columbia.edu/xv6.git xv6 -b hw1

This command clones the course Git repository onto your local machine (the "clone" command), and switch to the "hw1" branch (the "checkout" command). Then you can modify the source files, and Git automatically tracks your changes. If you add a new file, you should tell Git to track this file by running

$ git add <new file>

To generate an intermediate checkpoint of the source files, you can commit your changes to your local repository by running

$ git commit -am 'whatever comments you have for this commit'
[hw2 9bad18e] whatever comments you have for this commit

You can also run git diff HEAD to see what you have changed since your last commit. To see what you've changed since you cloned the repository, run git diff origin/hw1.

Part A: PC Bootstrap

Getting Started with x86 assembly



Exercise 1. Familiarize yourself with the assembly language materials available on the course resources page. You don't have to read them now, but you'll almost certainly want to refer to some of this material when reading and writing x86 assembly. We do recommend reading the section "The Syntax" in this book. It gives a good (and quite brief) description of the AT&T assembly syntax we'll be using with the GNU assembler in xv6.

Certainly the definitive reference for x86 assembly language programming is Intel's instruction set architecture reference, which you can find on in two flavors: an HTML edition of 80386 Programmer's Reference Manual from MIT folks; and the full, latest and greatest IA-32 Intel Architecture Software Developer's Manuals from Intel, covering all the features of the most recent processors that we won't need in class but you may be interested in learning about.


Simulating the x86

Instead of developing the operating system on a real, physical personal computer (PC), we use QEMU Emulator which faithfully emulates a complete PC: the code you write for QEMU will boot on a real PC too. Using an emulator instead of a real PC simplifies debugging; you can, for example, set break points inside of the emulated x86, which is difficult to do with the silicon version of an x86.

While QEMU's built-in monitor provides only limited debugging support, QEMU can act as a remote debugging target for the GNU debugger (GDB), which we'll use in this assignment to step through the early boot process.

To get started, clone our xv6 repository as described above in "Setup", then type make in the xv6 directory to build the boot loader and kernel you will start with.

$ cd xv6
$ make
dd if=kernel of=xv6.img seek=1 conv=notrunc
281+1 records in
281+1 records out
144356 bytes transferred in 0.061452 secs (2349080 bytes/sec)
rm wc.o grep.o mkdir.o rm.o ln.o stressfs.o kill.o echo.o init.o usertests.o
zombie.o cat.o sh.o ls.o

Now you're ready to run QEMU, supplying the file xv6.img and fs.img created above. xv6.img serves as the emulated PC's "virtual hard disk", which contains both our boot loader (bootmain) and our kernel (kernel). The second virtual disk fs.img contains a file system you will later examine after the system boots up.

To run xv6 under QEMU, type make qemu:

$ make qemu
qemu -serial mon:stdio -hdb fs.img xv6.img -smp 2

cpu0: starting xv6

lapicinit: 1 0xfee00000
cpu1: starting
init: starting sh
cpu0: starting
Spurious IDE interrupt.

A separate window should appear containing the display of the virtual machine. After a few seconds, QEMU's virtual BIOS will load xv6's boot loader from a virtual hard drive image contained in the file xv6.img, and the boot loader will in turn load and run the xv6 kernel.

After everything is loaded, you should get a '$' prompt in the xv6 display window and be able to enter commands into the rudimentary but functional xv6 shell. For example, try:

$ ls
.              1 1 512
..             1 1 512
README         2 2 1926
cat            2 3 12491
$ echo Hello
$ cat README

Now close this QEMU session, destroying the state of the xv6 virtual machine. You can do so either by closing the QEMU window or by pressing CTRL-C in the terminal where you typed make qemu.

The PC's Physical Address Space


|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |

|                  |
|      Unused      |
|                  |
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |
|     BIOS ROM     |
|  16-bit devices, |
|  expansion ROMs  |
|   VGA Display    |
|                  |
|    Low Memory    |
|                  |








$ gdb
+ target remote localhost:25501
The target architecture is assumed to be i8086
0x0000fff0 in ?? ()
+ symbol-file kernel

The following line:





   16 * 0xf000 + 0xfff0   # in hex multiplication by 16 is
   = 0xffff0 



Exercise 2. Use GDB's si (Step Instruction) command to trace into the ROM BIOS for a few more instructions, and try to guess what it might be doing. You might want to look at Phil Storrs I/O Ports Description. No need to figure out all the details - just the general idea of what the BIOS is doing first.


Part B: The Boot Loader



Xv6 uses the conventional hard drive boot mechanism, which means that its boot loader must fit into a measly 512 bytes. The boot loader consists of one assembly language source file bootasm.S, and one C source file, bootmain.c. Look through these source files carefully and make sure you understand what's going on. The boot loader must perform two main functions:

  1. The boot loader switches the processor from real mode to 32-bit protected mode, because it is only in this mode that software can access all the memory above 1MB in the processor's physical address space. Protected mode is described briefly in the Bootstrap section in the xv6 book, and in great detail in the Intel architecture manuals. At this point you only have to understand that translation of segmented addresses (segment:offset pairs) into physical addresses happens differently in protected mode, and that after the transition offsets are 32 bits instead of 16.
  2. The boot loader reads the kernel from the hard disk by directly accessing the IDE disk device registers via the x86's special I/O instructions. You will not need to learn much about programming specific devices in this class: writing device drivers is in practice a very important part of OS development, but from a conceptual or architectural viewpoint it is also one of the least interesting.

After you understand the boot loader source code, look at the file bootblock.asm. This file is a disassembly of the boot loader that the Makefile creates after compiling the boot loader. This disassembly file makes it easy to see exactly where in physical memory all of the boot loader's code resides, and makes it easier to track what's happening while stepping through the boot loader in GDB. Likewise, kernel.asm contains a disassembly of the xv6 kernel, which can often be useful for debugging.

You can set address breakpoints in GDB with the b command. For example, b *0x7c00 sets a breakpoint at address 0x7C00; b _start sets a breakpoint at function _start, the entry of the xv6 kernel. Once at a breakpoint, you can continue execution using the c and si commands: c causes QEMU to continue execution until the next breakpoint (or until you press Ctrl-C in GDB), and si N steps through the instructions N at a time.



Set a breakpoint at address 0x7c00, which is where the boot sector will be loaded. Continue execution until that breakpoint. Trace through the code in bootasm.S, using the source code and the disassembly file bootblock.asm to keep track of where you are. Also use the x/i command in GDB to disassemble sequences of instructions in the boot loader, and compare the original boot loader source code with both the disassembly in bootblock.asm and GDB.


Be able to answer the following questions:

Loading the Kernel

We will now look in further detail at the C language portion of the boot loader, in bootmain.c. But before doing so, this is a good time to stop and review some of the basics of C programming.





To make sense out of bootmain.c you'll need to know what an ELF binary is. When you compile and link a C program such as the xv6 kernel, the compiler transforms each C source ('.c') file into an object ('.o') file containing assembly language instructions encoded in the binary format expected by the hardware. The linker then combines all of the compiled object files into a single binary image such as kernel, which in this case is a binary in the ELF format, which stands for "Executable and Linkable Format".

Full information about this format is available in the ELF specification, but you will not need to delve very deeply into the details of this format in this class. Although as a whole the format is quite powerful and complex, most of the complex parts are for supporting dynamic loading of shared libraries, which we will not do in this class.


An ELF binary starts with a fixed-length ELF header, followed by a variable-length program header listing each of the program sections to be loaded. The C definitions for these ELF headers are in elf.h. The program sections we're interested in are:



$ objdump -h kernel



The link address of a binary is the memory address for which the binary is linked. Linking a binary for a given link address prepares it to be loaded at that address. The linker encodes the link address in the binary in various ways, for example when the code needs the address of a global variable, with the result that a binary usually won't work if it is executing from an address that it is not linked for. (It is possible to generate position-independent code that does not contain any such absolute addresses. This is used extensively by modern shared libraries, but it has performance and complexity costs, so we won't be using it in this course.)

In one sentence: the link address is the location where a binary assumes it is going to be loaded, while the load address is the location where a binary is loaded. It's up to us to make sure that they turn out to be the same.


$ objdump -h bootblock.o

The BIOS loads the boot sector into memory starting at address 0x7c00, so this is the boot sector's load address. This is also where the boot sector executes from, so this is also its link address. We set the link address by passing -Ttext 0x7C00 to the linker in Makefile, so the linker will produce the correct memory addresses in the generated code.


Look back at the load and link addresses for the kernel. Unlike the boot loader, these two addresses aren't the same: the kernel is telling the boot loader to load it into memory at a low address (0x100000, which is 1 megabyte), but it expects to execute from a high address. We'll dig in to how we make this work in the next section.


$ objdump -f kernel

You should now be able to understand the minimal ELF loader in bootmain.c. It reads each section of the kernel from disk into memory at the section's load address and then jumps to the kernel's entry point.




Part C: The Kernel


Operating system kernels often like to be linked and run at very high virtual address, such as 0x80100000, in order to leave the lower part of the processor's virtual address space for user programs to use. The reason for this arrangement will become clearer when we talk about processes and address spaces.


For now, we'll just map the first 4MB of physical memory, which will be enough to get us up and running. We do this using the hand-written, statically-initialized page directory and page table entrypgdir in main.c. For now, you don't have to understand the details of how this works, just the effect that it accomplishes. Up until entry.S sets the CR0_PG flag, memory references are treated as physical addresses (strictly speaking, they're linear addresses, but bootasm.S set up an identity mapping from linear addresses to physical addresses and we're never going to change that). Once CR0_PG is set, memory references are virtual addresses that get translated by the virtual memory hardware to physical addresses. entry_pgdir translates virtual addresses in the range 0x80000000 through 0x80400000 to physical addresses 0x00000000 through 0x00400000, as well as virtual addresses 0x00000000 through 0x00400000 to physical addresses 0x00000000 through 0x00400000. Any virtual address that is not in one of these two ranges will cause a hardware exception which, since we haven't set up interrupt handling yet, will cause QEMU to dump the machine state and exit (or endlessly reboot if you aren't using the patched version of QEMU).

Exercise 7. Use QEMU and GDB to trace into the xv6 kernel and stop at the movl %eax, %cr0 in entry.S. Examine memory at 0x00100000 and at 0x80100000. Now, single step over that instruction using the stepi GDB command. Again, examine memory at 0x00100000 and at 0x80100000. Make sure you understand what just happened.

What is the first instruction after the new mapping is established that would fail to work properly if the mapping weren't in place? Comment out the movl %eax, %cr0 in entry.S, trace into it, and see if you were right.
Formatted Printing to the Console


Exercise 8. Read through console.c. The xv6 cprintf implementation does not handle printing of octal numbers using patterns of the form "%o". Implement this feature.

Be able to answer the following questions:

  1. Explain the code of function cgaputc() in console.c.
  2. For the following questions you might wish to consult the notes for Lecture 3. These notes cover GCC's calling convention on the x86.


    • In the call to cprintf(), to what does fmt point? To what does argp point?
    • List (in order of execution) each call to cons_putc and its argument.
  3. Run the following code.
        unsigned int i = 0x00646c72;



The Stack

In the final exercise of this lab, we will explore in more detail the way the C language uses the stack on the x86, and in the process write a useful that prints a backtrace of the stack: a list of the saved Instruction Pointer (IP) values from the nested call instructions that led to the current point of execution.




Exercise 10. To become familiar with the C calling conventions on the x86, find the address of the test_backtrace function in kernel.asm, set a breakpoint there, and examine what happens each time it gets called after the kernel starts. How many 32-bit words does each recursive nesting level of test_backtrace push on the stack, and what are those words?

The above exercise should give you the information you need to implement a stack backtrace function, which you should call backtrace(). A prototype for this function is already waiting for you in backtrace.c. You can do it entirely in C, but you may find the read_ebp() function in x86.h useful.


Stack backtrace:
  ebp 8010c598 eip 801002b8 args 8010c5b8 80104db7 8010c5c8 460 7bf8
  ebp 8010c5f8 eip 801002c3 args 0 1 8010c624 80102c36 e000000

The first line printed reflects the currently executing function, namely backtrace() itself, the second line reflects the function that called backtrace(), the third line reflects the function that called that one, and so on. You should print all the outstanding stack frames. By studying entry.S you'll find that there is an easy way to tell when to stop.





At this point, your backtrace function should give you the addresses of the function callers on the stack that lead to backtrace() being executed. However, in practice you often want to know the function names corresponding to those addresses. For instance, you may want to know which functions could contain a bug that's causing your kernel to crash. You can use the addr2line utility to translate an address into a file name and line number.

If you enable the -O2 flag in your Makefile, you may find that the some functions are missing from the backtrace. This is because the compiler inlines some function calls. Other optimizations may cause you to see unexpected line numbers. If you get rid of the -O2 flag, the backtraces may make more sense (but your kernel will run more slowly).

Submission instructions

When you are ready to hand in your solution, put your UNI in conf.mk, commit all your changes, and run make handin in the xv6 directory. This will generate hw1-<your uni>-code.tar.gz for you, which includes a snapshot of all xv6 source code and a patch generated using git diff origin/hw1 hw1. This will be the programming part of your Courseworks submission. Be sure to commit all your changes (including the new files you add) before running make handin!
