Homework 2: Make QEMU, boot xv6, understand address translation

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.

Exercise 1: Running GDB

This first part of the assignment teaches you to debug the xv6 kernel with GDB. First, lets start GDB and set a breakpoint on the main function.

openlab$ make qemu-nox-gdb
...

openlab$ cd ~/cs238p/xv6-public
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

What you see on the screen is the assembly code of the BIOS that QEMU executes as part of the platform initialization. The BIOS starts at address 0xfff0 (you can read more about it in the How Does an Intel Processor Boot? blog post. You can single step through the BIOS machine code with the si (single instruction) GDB command if you like, but it's hard to make sense of what is going on so lets skip it for now and get to the point when QEMU starts executing the xv6 kernel.

Note, if you need to exit GDB you can press Ctrl-C and then Ctrl-D. To exit xv6 running under QEMU you can terminate it with Ctrl-A X.

Now from inside the GDB session set a breakpoint on main, e.g.

 (gdb) br main 
Breakpoint 1 at 0x80102e00: file main.c, line 19. 

Now since you set two breakpoints you can continue execution of the system until one of them gets hit. In gdb enter the "c" (continue) command to run xv6 until it hits the first breakpoint (main).

(gdb) c

(gdb) help all

Now you've reached the C code, and since we compiled it with the "-g" flag that includes the symbol information into the ELF file we can see the C source code that we're executing. Enter the l (list) command.

(gdb) l
14	// Bootstrap processor starts running C code here.
15	// Allocate a real stack and switch to it, first
16	// doing some setup required for memory allocator to work.
17	int
18	main(void)
19	{
20	  kinit1(end, P2V(4*1024*1024)); // phys page allocator
21	  kvmalloc();      // kernel page table
22	  mpinit();        // detect other processors
23	  lapicinit();     // interrupt controller

Remember that when you hit the main breakpoint the GDB showed you that you're at line 19 in the main.c file (main.c:19). This is where you are. You can either step into the functions with the s (step) command (note, in contrast to the si step instruction command, this one will execute one C line at a time), or step over the functions with the n (next) command which will not enter the function, but instead will execute it till completion.

Try stepping into the kinit1 function.

(gdb) s

Note, that on my machine when I enter s for the first time the GDB believes that I'm executing the startothers() function. It's a glitch---the compiler generated an incorrect debug symbol information and GDB is confused. If I hit s a couple of times I eventually get to kinit1().

The whole listing of the source code seems a bit inconvenient (entering l every time you want to see the source line is a bit annoying). GDB provides a more conventional way of following the program execution with the TUI mechanism. Enable it with the following GDB command

(gdb) tui enable

(gdb) layout asm

Now you see the source code window and the machine instructions at the bottom. You can use the same commands to walk through your program. You can scroll the source with arrow keys, PgUp, and PgDown.

TUI can show you the state of the registers and how they are changing as you execute your code

(gdb) tui reg general

TUI is a very cute part of GDB and hence it makes sense to read more about various capabilities http://sourceware.org/gdb/onlinedocs/gdb/TUI-Commands.html. For example, you can specify the assembly layout to single step through machine instructions similar to source code:

(gdb) layout asm

(gdb) layout src

Troubleshooting GDB

andromeda-1:1001-/16:40>gdb
GNU gdb (GDB) Red Hat Enterprise Linux 7.6.1-110.el7
Copyright (C) 2013 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-redhat-linux-gnu".
For bug reporting instructions, please see:
.
warning: File "/home/aburtsev/projects/cs143a/xv6-public/.gdbinit" auto-loading has been 
declined by your `auto-load safe-path' set to "$debugdir:$datadir/auto-load:/usr/bin/mono-gdb.py".
To enable execution of this file add
	add-auto-load-safe-path /home/aburtsev/projects/cs143a/xv6-public/.gdbinit
line to your configuration file "/home/aburtsev/.gdbinit".
To completely disable this security protection add
	set auto-load safe-path /
line to your configuration file "/home/aburtsev/.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual.  E.g., run from the shell:
	info "(gdb)Auto-loading safe path"
(gdb) quit

add-auto-load-safe-path /home/aburtsev/projects/cs143a/xv6-public/.gdbinit

/home/aburtsev/.gdbinit

Exercise 2: Breaking inside the bootloader

Remember that the BIOS loads the kernel bootloader at the address 0x7c00. The kernel bootloader is implemented in the file bootasm.S

# Start the first CPU: switch to 32-bit protected mode, jump into C.
# The BIOS loads this code from the first sector of the hard disk into
# memory at physical address 0x7c00 and starts executing in real mode
# with %cs=0 %ip=7c00.

.code16                       # Assemble for 16-bit mode
.globl start
start:
  cli                         # BIOS enabled interrupts; disable

  # Zero data segment registers DS, ES, and SS.
  xorw    %ax,%ax             # Set %ax to zero
  movw    %ax,%ds             # -> Data Segment
  movw    %ax,%es             # -> Extra Segment
  movw    %ax,%ss             # -> Stack Segment

Lets try to set the breakpoint at this address. First, exit both GDB and QEMU sessions and start them over. Inside GDB set the breakpoint at a specific address 0x7c00

 
(gdb) br * 0x7c00
Breakpoint 1 at 0x7c00

(gdb) c
Continuing
[   0:7c00] => 0x7c00:	cli

Now use the si (step instruction) command to single step your execution (execute it one machine instruction at a time). Remember that the 0x7c00 address is defined in the assembly file, bootasm.S (the entry point of the boot loader). Enter si

(gdb) si

Every time you enter si it executes one machine instruction and shows you the next machine instruction so you know what is coming next

(gdb) si
(gdb) si
[   0:7c01] => 0x7c01:	xor    %ax,%ax

You can switch between ATT and Intel disassembly syntax with these commands:

(gdb) set disassembly-flavor intel
(gdb) set disassembly-flavor att

Note the first call instruction. Right before it, the first stack was set up (this will be useful in the question about the stack below).

Exercise 2: Breaking on the kernel entry and inspecting ELF files

# Entering xv6 on boot processor, with paging off.
.globl entry
entry:
  # Turn on page size extension for 4Mbyte pages
  movl    %cr4, %eax

# By convention, the _start symbol specifies the ELF entry point.
# Since we haven't set up virtual memory yet, our entry point is
# the physical address of 'entry'.
.globl _start
_start = V2P_WO(entry)

Question 1: Explain why the _start label is assigned V2P_WO(entry)?

 man readelf

This provides explanation for all possible command line options readelf can take. Alternatively, for a short help you can run it like

readelf

openlab$ readelf -s kernel | grep _start
   302: 0010000c     0 NOTYPE  GLOBAL DEFAULT    1 _start
   382: 8010a48c     0 NOTYPE  GLOBAL DEFAULT    5 _binary_entryother_start
   445: 8010a460     0 NOTYPE  GLOBAL DEFAULT    5 _binary_initcode_start
openlab$

Now lets do the same for the entry symbol.

readelf -s kernel | grep entry
    84: 8010000c     0 NOTYPE  GLOBAL DEFAULT    1 entry
   301: 80109000  4096 OBJECT  GLOBAL DEFAULT    5 entrypgdir
   344: 0000008a     0 NOTYPE  GLOBAL DEFAULT  ABS _binary_entryother_size
   382: 8010a48c     0 NOTYPE  GLOBAL DEFAULT    5 _binary_entryother_start
   457: 8010a516     0 NOTYPE  GLOBAL DEFAULT    5 _binary_entryother_end

Now lets set a breakpoint at the _start label. Restart the xv6 and GDB sessions and set the breakpoint:

 
(gdb) br _start
Breakpoint 1 at 0x10000c

(gdb) c
Continuing.
The target architecture is assumed to be i386
=> 0x10000c:	mov    %cr4,%eax

Breakpoint 1, 0x0010000c in ?? ()

(gdb) si
=> 0x10000f:	or     $0x10,%eax
0x0010000f in ?? ()
(gdb) si
=> 0x100012:	mov    %eax,%cr4
0x00100012 in ?? ()
(gdb)

To make sure that you understand what is going on, open the entry.S file and look over it. Remember, that the _start and entry labels are defined in this file. And the instructions that you were executing in GDB come from exactly this file. Make sure that you understand what is happening there (we covered in the lecture), i.e., the kernel works on enabling the 4MB page tables, and create a stack for executing the C code inside main().

Question 2: Why breaking on entry doesn't work?

Now lets set a breakpoint at the enry label. Restart the xv6 and GDB sessions and set the breakpoint:

(gdb) b  entry
Breakpoint 1 at 0x8010000c: file entry.S, line 47.

(gdb) c

Question 3: What is on the stack?

Restart your xv6 and gdb session. Set a breakpoint at the freerange label.

(gdb) br freerange

(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.)

To double check that you actually hit freerange called right inside from main use the backtrace command provided by GDB:

(gdb) bt
#0  kinit1 (vstart=, vend=, vend@entry=0x80400000) at kalloc.c:36
#1  0x80102e23 in main () at main.c:20

You might find it convenient to go over the lecture that explains how the kernel boots and at what point it initializes its stack and at the lecture that talks about calling conventions (take a look at the bootasm.S, bootmain.c, and entry.S files). A short x86 Assembly Guide and additional resources from the MIT reference page provide pointers to x86 assembly documentation, if you are wondering about the semantics of a particular instruction. Here are some questions to help you along:

Tip

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='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 address translation

Question 1: Explain how logical to physical address translation works

You can choose any physical addresses for the page table directory (Level 2) and the page table (Level 1) involved in the translation. Draw a diagram (hand drawn figures are sufficient, but need to be clear) representing the state of the GDT, page table, and hardware CPU registers pointing to the GDT and page table directory 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.