Homework 2: Make QEMU, boot xv6, understand page tables

To start working on this homework follow the xv6 setup instructions. After you're done with them, you'll be ready to start working on the assignment.

Boot xv6

From inside your Vagrant VM (remember you did vagrant ssh to get inside your Vagrant VM) fetch the xv6 source:
vagrant@openlab$ cd /vagrant
vagrant@openlab$ mkdir cs238p
vagrant@openlab$ cd cs238p
vagrant@openlab$ git clone git://github.com/mit-pdos/xv6-public.git
Cloning into xv6...
...
Build xv6:
vagrant@openlab$ cd xv6-public
vagrant@openlab$ make 
...
gcc -O -nostdinc -I. -c bootmain.c
gcc -nostdinc -I. -c bootasm.S
ld -m    elf_i386 -N -e start -Ttext 0x7C00 -o bootblock.o bootasm.o bootmain.o
objdump -S bootblock.o > bootblock.asm
objcopy -S -O binary -j .text bootblock.o bootblock
...
vagrant@openlab$ 

You're now ready to run xv6.

vagrant@openlab$ make qemu-nox
...

Exercise 1: Finding and breaking at an address

Find the address of _start, the entry point of the kernel:
vagrant@openlab$ nm kernel | grep _start
8010b50c D _binary_entryother_start
8010b4e0 D _binary_initcode_start
0010000c T _start
vagrant@openlab$
In this case, the address is 0010000c.

Run the kernel inside QEMU GDB, setting a breakpoint at _start (i.e., the address you just found).

vagrant@openlab$ make qemu-nox-gdb
...
Now open another terminal (you do that on your openlab host machine, i.e., andromeda-XX, odin, or tristram, whichever you're using). Change to the folder where Vagrant is configured, and connect to the same Vagrant VM, i.e.:
andromeda-XX$ cd ~/ics143a/xv6-vagrant-master/
andromeda-XX$ vagrant ssh
In this new terminal (but now inside your vagrant VM) change to the folder where you've built xv6, and start GDB:
vagrant@openlab$ cd /vagrant/ics143a/xv6-public
vagrant@openlab$ gdb
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
+ target remote localhost:26000
The target architecture is assumed to be i8086
[f000:fff0]    0xffff0:	ljmp   $0xf000,$0xe05b
0x0000fff0 in ?? ()
+ symbol-file kernel
Set a breakpoint at the address of _start, e.g.
(gdb) br * 0x0010000c
Breakpoint 1 at 0x10000c
(gdb) c
Continuing.
The target architecture is assumed to be i386
=> 0x10000c:	mov    %cr4,%eax

Breakpoint 1, 0x0010000c in ?? ()
(gdb)
The details of what you see are likely to differ from the above output.

Question 1: What is on the stack?

Look at the registers and the stack contents:
(gdb) info reg
...
(gdb) x/24x $esp
...
(gdb)

Write a short (3-5 word) comment next to each zero and non-zero value of the printout explaining what it is. Which part of the printout is actually the stack? (Hint: not all of it.)

You might find it convenient to consult the files bootasm.S, bootmain.c, and bootblock.asm (which contains the output of the compiler/assembler). The reference page has pointers to x86 assembly documentation, if you are wondering about the semantics of a particular instruction. Here are some questions to help you along:

  • Start by setting a break-point at 0x7c00, the start of the boot block (bootasm.S). Single step through the instructions (type si to the gdb prompt). Where in bootasm.S is the stack pointer initialized?
  • Single step through the call to bootmain; what is on the stack now?
  • What do the first assembly instructions of bootmain do to the stack? Look for bootmain in bootblock.asm.
  • Look in bootmain in bootblock.asm for the call that changes eip to 0x10000c. What does that call do to the stack?

Tip

Since we're running QEMU in headless mode (`make clean qemu-nox`) you don't have a GUI window to close whenever you want. There are two ways to exit QEMU.
  1. First, you can exit the xv6 QEMU session by killing the QEMU process from another terminal. A useful shortcut is to define an `alias` in your local machine as follows:
    alias kill-qemu='vagrant ssh -c "killall qemu-system-i386"'
    
    Add this to your `~/.bash_profile` or `~/.zshrc` file to make it persistant This will send the `killall qemu-system-i386` command over ssh to your vagrant machine. Notice this command will only work if you're running it from somewhere in the directory path of the Vagrantfile running this machine
  2. Alternatively you can send a Ctrl-a x command to the QEMU emulator forcing it to exit (here is a list of QEMU shortcuts and commands).

You can find more information about QEMU monitor and GDB debugger here, feel free to explore them.

Exercise 2: Understanding page tables

Question 1: Explain how virtual to physical address translation works

This question asks you to illustrate organization of the x86, 4K, 32bit page table through a simple example. Assume that the hardware translates the virtual address '0xc02005' into the physical address '0x8005'. The physical addresses of the page table directory (Level 1) and the page table (Level 2) involved in the translation of this virtual address are respectively 0x3000 and 0x1000. Draw a diagram (hand drawn figures are sufficient, but need to be clear) representing the state of the page table in physical memory and the process of translation (similar to Figure 2-1 in the xv6 book but using concrete physical and virtual addresses and page table entries). Provide a short explanation. Use Chapter 2 of the xv6 book to review how page tables work.

Exercise 3: What is the state of page tables after xv6 is done initializing the first 4K page table?

During boot, xv6 calls the kvmalloc() function to set up the kernel page table (kvmalloc() is called from main() (lines 1316-1340)). What is the state of this first 4K page table after kvmalloc() returns, and what are the details of page table initialization? To understand the state of the page table, we first take a look at the implementation of the kvmalloc function and then inspect the actual page tables with the QEMU monitor. Based on your analysis of the source code, and based on the inspection of the page tables with the QEMU monitor, explain the state of the page tables after kvmalloc() is done. Draw a figure of a page table, and briefly explain each page table entry.

To aid your analysis, inspect the actual page table with QEMU. QEMU includes a built-in monitor that can inspect and modify the machine state in useful ways. To enter the monitor, press Ctrl-a c in the terminal running QEMU. Press Ctrl-a c again to switch back to the serial console.

To inspect the page table, run xv6 to the point after it is done with kvmalloc(). Similar to Exercise 1, open two terminal windows. In one window start xv6 under control of the GDB debugger
vagrant@openlab$make qemu-nox-gdb
In another window start GDB
vagrant@openlab$ cd /vagrant/ics143a/xv6-public
vagrant@openlab$ gdb 
In the GDB window set breakpoint on main function, run continue (c), and run (n) executing functions inside main until you exit kvmalloc() (use "n" three times):
(gdb) b main
(gdb) c
Continuing.
The target architecture is assumed to be i386
=> 0x80102eb0 
: push %ebp Breakpoint 1, main () at main.c:19 19 { (gdb) n => 0x80102eba : movl $0x80400000,0x4(%esp) 20 kinit1(end, P2V(4*1024*1024)); // phys page allocator (gdb) n => 0x80102ece : call 0x80106790 21 kvmalloc(); // kernel page table (gdb) n => 0x80102ed3 : call 0x80103070 22 mpinit(); // detect other processors

At this point switch back to the terminal running the QEMU monitor and type info pg to display the state of the active page table. You will see page directory entries and page table entries along with the permissions for each separately. Repeated PTE's and entire page tables are folded up into a single line. For example,

VPN range     Entry         Flags        Physical page
[00000-003ff]  PDE[000]     -------UWP
  [00200-00233]  PTE[200-233] -------U-P 00380 0037e 0037d 0037c 0037b 0037a ..
[00800-00bff]  PDE[002]     ----A--UWP
  [00800-00801]  PTE[000-001] ----A--U-P 0034b 00349
  [00802-00802]  PTE[002]     -------U-P 00348
This shows two page directory entries, spanning virtual addresses 0x00000000 to 0x003fffff and 0x00800000 to 0x00bfffff, respectively. Both PDE's are present, writable, and user and the second PDE is also accessed. The second of these page tables maps three pages, spanning virtual addresses 0x00800000 through 0x00802fff, of which the first two are present, user, and accessed and the third is only present and user. The first of these PTE's maps physical page 0x34b.

You can find more information about QEMU monitor and GDB debugger here, feel free to explore them.

Shut down your VM

After you're done please halt your VM so it does not run on the cluster forever. All the xv6 files will be there in the cs238p/xv6-vagrant-master folder when you start vagrant the next time.

To shut down your VM, when you close your ssh connection type

 
UCInetID@andromeda-XX$ vagrant halt

You will be able to start your Vagrant VM from the same folder (cs238p/xv6-vagrant-master) by typing

 
UCInetID@andromeda-XX$ vagrant up
UCInetID@andromeda-XX$ vagrant ssh

Submit

Submit your answers on Canvas HW2 Boot xv6 (as a PDF file).

Updated: February, 2017