MIT 6.828 labs walkthroughs: Lab 1 Booting a PC

## Exercise 2

I tracked a few instructions, the BIOS just did something to enter protected mode.

```objdump
[f000:fff0]    0xffff0: ljmp   $0xf000,$0xe05b    # jump to 0xfe05b
[f000:e05b]    0xfe05b: cmpl   $0x0,%cs:0x6ac8    # compare 0xf6ac8 with 0
[f000:e062]    0xfe062: jne    0xfd2e1            # if != 0, jump to 0xfd2e1
[f000:e066]    0xfe066: xor    %dx,%dx            # set %dx = 0
[f000:e068]    0xfe068: mov    %dx,%ss            # set stack segment = 0
[f000:e06a]    0xfe06a: mov    $0x7000,%esp       # set stack pointer = 0x7000
[f000:e070]    0xfe070: mov    $0xf34c2,%edx      # set %edx = 0xf34c2
[f000:e076]    0xfe076: jmp    0xfd15c
[f000:d15c]    0xfd15c: mov    %eax,%ecx
[f000:d15f]    0xfd15f: cli                       # clear interrupt flag
[f000:d160]    0xfd160: cld                       # clear direction flag
[f000:d161]    0xfd161: mov    $0x8f,%eax         # disable NMI
[f000:d167]    0xfd167: out    %al,$0x70
[f000:d169]    0xfd169: in     $0x71,%al          # read CMOS 0xf
[f000:d16b]    0xfd16b: in     $0x92,%al          # enable A20 address line
[f000:d16d]    0xfd16d: or     $0x2,%al           
[f000:d16f]    0xfd16f: out    %al,$0x92
[f000:d171]    0xfd171: lidtw  %cs:0x6ab8         # load interrupt descriptor table from 0xf6ab8
[f000:d177]    0xfd177: lgdtw  %cs:0x6a74         # load global descriptor table from 0xf6a74
[f000:d17d]    0xfd17d: mov    %cr0,%eax          # set PE flag to 1, enable protected mode
[f000:d180]    0xfd180: or     $0x1,%eax
[f000:d184]    0xfd184: mov    %eax,%cr0 
[f000:d187]    0xfd187: ljmpl  $0x8,$0xfd18f      # enter protected mode
```

According to the lab page, what the BIOS really does is:

> When the BIOS runs, it sets up an interrupt descriptor table and initializes various devices such as the VGA display. This is where the "Starting SeaBIOS" message you see in the QEMU window comes from.
> After initializing the PCI bus and all the important devices the BIOS knows about, it searches for a bootable device such as a floppy, hard drive, or CD-ROM. Eventually, when it finds a bootable disk, the BIOS reads the boot loader from the disk and transfers control to it.

Here comes a question, how does the BIOS switch back to real mode and give control to the bootloader?


## Exercise 3

**At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?**

In `boot/boot.S` or `obj/boot/boot.asm`, we can find the following code

```asm
# Jump to next instruction, but in 32-bit code segment.
# Switches processor into 32-bit mode.
ljmp    $PROT_MODE_CSEG, $protcseg
  7c2d:	ea                   	.byte 0xea
  7c2e:	32 7c 08 00          	xor    0x0(%eax,%ecx,1),%bh
```

But the disassembly of the code is quite confusing. Why the `ljmp` instruction is converted to `.byte` and `xor` instructions? To figure out what it actually is and whether this is what switches the processor to 32-bit, I made a breakpoint on 0x7c2d. The gdb's output is like that:

```
(gdb) b *0x7c2d
Breakpoint 1 at 0x7c2d
(gdb) c
Continuing.
[   0:7c2d] => 0x7c2d:  ljmp   $0x8,$0x7c32
(gdb) si
The target architecture is assumed to be i386
=> 0x7c32:      mov    $0x10,%ax
```

To answer the second question, I googled "how to enter protect mode" and found that there are 4 prerequisites on [Protected Mode - OSDev Wiki](https://wiki.osdev.org/Protected_Mode), they are:

* Disable interrupts (line 15 of `boot/boot.S`)
* Enable the A20 Line (section `seta20.1` and `seta20.2` of `boot/boot.S`)
* Load the Global Descriptor Table (line 48 of `boot/boot.S`)
* Set PE bit in CR0 (line 49 to 51 of `boot/boot.S`)

After doing these prepare work, the `ljmp   $0x8,$0x7c32` at `0x7c2d` makes the processor start executing 32-bit code.


**What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?**

In `boot/main.c`, we can find that the final operation is to call the entry point from the ELF header.

```c
// call the entry point from the ELF header
// note: does not return!
((void (*)(void)) (ELFHDR->e_entry))();
```

And in `obj\boot\boot.asm`, the disassembly of this line is `7d6b: call *0x10018`. That's the last instruction of the boot loader executed. With a breakpoint and si command, it's easy to find out that `0x10000c: movw $0x1234,0x472` is the first instruction of the kernel.


**Where is the first instruction of the kernel?**

GDB shows that it is at `0x10000c`, but in `obj/kern/kernel.asm`, the instruction is at `0xf010000c`. To figure out why, I looked through the `kern/entry.S` and found this.

>  We haven't set up virtual memory yet, so we're running from the physical address the boot loader loaded the kernel at: 1MB (plus a few bytes).  However, the C code is linked to run at KERNBASE+1MB.  Hence, we set up a trivial page directory that translates virtual addresses [KERNBASE, KERNBASE+4MB) to physical addresses [0, 4MB).

`KERNBASE` is defined in `inc/memlayout.h` which value is `0xF0000000`. That what caused the difference.

Back to the question, the first instruction of the kernel is at `0x10000c`.


**How does the boot loader decide how many sectors it must read in order to fetch the entire kernel from disk? Where does it find this information?**

In `boot/main.c`, the bootloader first loads all the program headers (The number of entries is recorded at field `e_phnum` in ELF header). In each program header, the field tells `p_pa` the physical address for the segment and `p_memsz` tells the size of the program segment.

```c
// load each program segment (ignores ph flags)
ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);
eph = ph + ELFHDR->e_phnum;
for (; ph < eph; ph++)
	// p_pa is the load address of this segment (as well
	// as the physical address)
	readseg(ph->p_pa, ph->p_memsz, ph->p_offset);
```

Using the above two fields, the bootloader can decide how many sectors to load since a sector is 512B and the kernel starts at sector 1.


## Exercise 4

`pointers.c` prints following content on my machine:

```
1: a = 0x7ffea1330f70, b = 0x55a8a005e260, c = 0x7f5c8d96db55
2: a[0] = 200, a[1] = 101, a[2] = 102, a[3] = 103
3: a[0] = 200, a[1] = 300, a[2] = 301, a[3] = 302
4: a[0] = 200, a[1] = 400, a[2] = 301, a[3] = 302
5: a[0] = 200, a[1] = 128144, a[2] = 256, a[3] = 302
6: a = 0x7ffea1330f70, b = 0x7ffea1330f74, c = 0x7ffea1330f71
```

What you should know before doing this exercise is the following three points:

* Array's name represents the address of the first element
* `a[i]` is syntactic sugar for `*(a + i)`
* `(int)p + 1` and `(int)(p + 1)` have different behavior

```c
int a[4];
int *b = malloc(16);
int *c;
int i;
printf("1: a = %p, b = %p, c = %p\n", a, b, c);
```

For line 1, `a` is the starting address of array `a` or address of `a[0]`, `b` is the address of memories allocated by malloc on the heap and `c` has an indeterminate value since `c` is an uninitialized local variable.

```c
c = a;                   // c points to array a
for (i = 0; i < 4; i++)
    a[i] = 100 + i;      // a[4] = { 100, 101, 102, 103 }
c[0] = 200;              // c points to a[0], it equals a[0] = 200
printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

c[1] = 300;              // here c still points to a, so it equals a[1] = 300
*(c + 2) = 301;          // a[2] = 301
3[c] = 302;              // 3[c] == *(c + 3) == c[3], so a[3] = 302
// P.S. This is a trick to distinguish array subscript with operator[] in C++
printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

c = c + 1;               // move int pointer c to next element, now it points to a[1]
*c = 400;                // a[1] = 400
printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

```

For line 2, 3 and 4, please reference the comments above.

```c
c = (int *) ((char *) c + 1);  // casts c from int* c to char*, move to next element, then cast to int*
*c = 500;                      // set the dereference of c's value to 500
printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);
```

For line 5, please reference the comments above and the analysis below.

```
On a little-endian platform like x86_64 or i386, the process is like that

At the beginning
10                  c                   8                   4                   0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|       a[1]        |       a[2]        |       a[1]        |       a[0]        |
| 00 | 00 | 01 | 2e | 00 | 00 | 01 | 2d | 00 | 00 | 01 | 90 | 00 | 00 | 00 | c8 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                                         ^^^^ ^^^^ ^^^^ ^^^^ c
Cast to char pointer
10                  c                   8                   4                   0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 00 | 00 | 01 | 2e | 00 | 00 | 01 | 2d | 00 | 00 | 01 | 90 | 00 | 00 | 00 | c8 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                                                        ^^^^ c
Move pointer c to the next
10                  c                   8                   4                   0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 00 | 00 | 01 | 2e | 00 | 00 | 01 | 2d | 00 | 00 | 01 | 90 | 00 | 00 | 00 | c8 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                                                   ^^^^ c
Cast to int pointer
10                  c                   8                   4                   0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 00 | 00 | 01 | 2e | 00 | 00 | 01 | 2d | 00 | 00 | 01 | 90 | 00 | 00 | 00 | c8 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                                    ^^^^ ^^^^ ^^^^ ^^^^ c
Assign value *c = 0x000001f4
10                  c                   8                   4                   0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|       a[1]        |       a[2]        |       a[1]        |       a[0]        |
| 00 | 00 | 01 | 2e | 00 | 00 | 01 | 00 | 00 | 01 | f4 | 90 | 00 | 00 | 00 | c8 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
                                    ^^^^ ^^^^ ^^^^ ^^^^ c
The final result is:
a[0] == 0xc8 == 200
a[1] == 0x1f490 == 128144
a[2] == 0x100 == 256
a[4] == 0x12e == 302

```

```c
b = (int *) a + 1;             // b points to next int to a, it adds 4 to pointer a
c = (int *) ((char *) a + 1);  // ((char *) a + 1) points to next char to a, it adds 1 to pointer a, then cast to int*
printf("6: a = %p, b = %p, c = %p\n", a, b, c);
```

For line 6, `a` is still the starting address of array `a` or address of `a[0]`, `b` is the address of `a[1]`, or `a`'s address + 4, `c` is `a`'s address + 1.


## Exercise 5

The first instruction that would "break" will be `ljmp $PROT_MODE_CSEG, $protcseg`, `$protcseg` is a part of `.text` segment and the segment is assumed to be loaded at `0x7c00`.

To confirm this, I changed the link address in `boot/Makefrag` to `0x7000`, And it does cause a fault, the gdb outputs like follow:

```
Program received signal SIGTRAP, Trace/breakpoint trap.
[   0:7c2d] => 0x7c2d:  ljmp   $0x8,$0x7032
```

## Exercise 6

This exercise can be done without QEMU. According to the answer to the last question of Exercise 3, the bootloader will load the kernel at `0x100000` (1MB). So before the kernel is loaded, the 8 words of memory at `0x100000` can be anything. After the kernel is loaded, it was the first 8 words of the kernel.

To confirm that, let's set two breakpoints at `0x7c00`(starting address of bootloader) and `0x10000c`(the first instruction of the kernel).

At the first breakpoint, the output is that. QEMU may set all memories to 0.

```
Breakpoint 1, 0x00007c00 in ?? ()
(gdb) x/8x 0x100000
0x100000:       0x00000000      0x00000000      0x00000000      0x00000000
0x100010:       0x00000000      0x00000000      0x00000000      0x00000000
```

At the second breakpoint, the kernel is loaded as follows. We can use `x/Ni ADDR` to print N instructions of memory at ADDR. The disassembly is the same as what in `obj/kern/kernel.asm`.

```
Breakpoint 3, 0x0010000c in ?? ()
(gdb) x/8x 0x100000
0x100000:       0x1badb002      0x00000000      0xe4524ffe      0x7205c766
0x100010:       0x34000004      0x2000b812      0x220f0011      0xc0200fd8
(gdb) x/8i 0x100000
   0x100000:    add    0x1bad(%eax),%dh
   0x100006:    add    %al,(%eax)
   0x100008:    decb   0x52(%edi)
   0x10000b:    in     $0x66,%al
   0x10000d:    movl   $0xb81234,0x472
   0x100017:    and    %dl,(%ecx)
   0x100019:    add    %cl,(%edi)
   0x10001b:    and    %al,%bl
```


## Exercise 7

We can find the `movl %eax, %cr0` is located at `0x100025` from `obj/kern/kernel.asm`, this instruction is part of the procedure to turn on paging. It sets the PE (Protected Mode Enable), PG (Paging) and WP (Write Protect) flags in the CR0 register.

```
# Turn on paging.
movl	%cr0, %eax
orl	$(CR0_PE|CR0_PG|CR0_WP), %eax
movl	%eax, %cr0
```

Before this instruction executed, memory at `0x00100000` points to the kernel while memory at `0xf0100000` exceeds physical memory's size and the memory there is filled with 0. 

```
(gdb) x/8x 0x00100000
0x100000:       0x1badb002      0x00000000      0xe4524ffe      0x7205c766
0x100010:       0x34000004      0x2000b812      0x220f0011      0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start+4026531828>: 0x00000000      0x00000000      0x00000000      0x00000000
0xf0100010 <entry+4>:   0x00000000      0x00000000      0x00000000      0x00000000
```

After it is executed, the MMU starts working. Now memory at `0x00100000` and at `0xf0100000` points to the same physical memory where the kernel is located. So their content is the same.

```
(gdb) x/8x 0x00100000
0x100000:       0x1badb002      0x00000000      0xe4524ffe      0x7205c766
0x100010:       0x34000004      0x2000b812      0x220f0011      0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start+4026531828>: 0x1badb002      0x00000000      0xe4524ffe      0x7205c766
0xf0100010 <entry+4>:   0x34000004      0x2000b812      0x220f0011      0xc0200fd8
```

Following up are `0x100028: mov $0xf010002f,%eax` and `0x10002d: jmp *%eax` which jumps to the relocated kernel code at `0xf010002d`. If paging is not enabled, this will cause an out of range error.

To confirm that, I commented out the `movl %eax, %cr0` and got a `qemu: fatal: Trying to execute code outside RAM or ROM at 0xf010002c` error on executing `0x10002d: jmp *%eax`. That's it.


## Exercise 8

Finishing this exercise itself is quite simple. We can just copy the code of formating unsigned decimal in `lib/printfmt.c` and change the base to 8.

```diff
--- a/lib/printfmt.c
+++ b/lib/printfmt.c
@@ -205,11 +205,9 @@ vprintfmt(void (*putch)(int, void*), void *putdat, const char *fmt, va_list ap)
 
                // (unsigned) octal
                case 'o':
-                       // Replace this with your code.
-                       putch('X', putdat);
-                       putch('X', putdat);
-                       putch('X', putdat);
-                       break;
+                       num = getuint(&ap, lflag);
+                       base = 8;
+                       goto number;
 
                // pointer
                case 'p':
```

Now we can see `6828 decimal is 15254 octal!` instead of `6828 decimal is XXX octal!` in qemu window. It works.

However, answering the questions requires us to step further.

**Explain the interface between `printf.c` and `console.c`. Specifically, what function does `console.c` export? How is this function used by `printf.c`?**

The `putch()` function of `printf.c` calls the `cputchar()` function of `console.c` to output a single character to console.

**Explain the following from `console.c`:**

```c
if (crt_pos >= CRT_SIZE) {
	int i;
	memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
	for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
		crt_buf[i] = 0x0700 | ' ';
	crt_pos -= CRT_COLS;
}
```

These codes are located at line 195 of `console.c`

`crt_pos` is the current cursor position on the screen. `CRT_SIZE` is the screen size and `CRT_COLS` is the width of the screen. So the code can be explained like that:

```
if (cursor exceeds the screen size) {
     move one screen row up
     fill the new row with blank and black background
     move the cursor backward for one row
}
```

In short, the code above creates a new line when the screen is full.

**Trace the execution of the following code step-by-step:**

```c
int x = 1, y = 3, z = 4;
cprintf("x %d, y %x, z %d\n", x, y, z);
```

To trace the code, we can put it into the `i386_init()` of `kern/init.c`.

* In the call to `cprintf()`, to what does `fmt` point? To what does `ap` point?

Using gdb, we can find that `fmt` points to the format string `x %d, y %x, z %d\n` and `ap` points to a variable argument list which contains the data to be printed.

```
(gdb) p fmt
$1 = 0xf0101a77 "x %d, y %x, z %d\n"
(gdb) p ap
$2 = (va_list) 0xf010ffd4 "\001"
(gdb) x/3x ap
0xf010ffd4:     0x00000001      0x00000003      0x00000004
(gdb) x/3d ap
0xf010ffd4:     1       3       4
```

* List (in order of execution) each call to `cons_putc`, `va_arg`, and `vcprintf`. For `cons_putc`, list its argument as well. For `va_arg`, list what `ap` points to before and after the call. For `vcprintf` list the values of its two arguments.

Here, since `va_arg` is a macro function, we cannot make a breakpoint by directly inputting `b va_arg` to gdb. Tracing into `lib/printfmt.c`, we can find that all 3 arguments are formatted as `%d` or `%x`, and they call `getint()` or `getuint()` function. However, these two functions are static and we cannot break at them either. Since we know that all 3 arguments are of int type, as a workaround, we can break at `printfmt.c:62` and `printfmt.c:75` as before calling `va_arg`.

The order of calls is like that:

```
vcprintf (fmt=0xf0101a77 "x %d, y %x, z %d\n", ap=0xf010ffd4)
cons_putc (c=120 'x')
cons_putc (c=32 ' ')
ap=0xf010ffd4 -> 1
va_arg ()
ap=0xf010ffd8 -> 3
cons_putc (c=49 '1')
cons_putc (c=44 ',')
cons_putc (c=32 ' ')
cons_putc (c=121 'y')
cons_putc (c=32 ' ')
ap=0xf010ffd8 -> 3
va_arg ()
ap=0xf010ffdc -> 4
cons_putc (c=51 '3')
cons_putc (c=44 ',')
cons_putc (c=32 ' ')
cons_putc (c=122 'z')
cons_putc (c=32 ' ')
ap=0xf010ffdc -> 4
va_arg ()
ap=0xf010ffe0 -> 0xf0113060
cons_putc (c=52 '4')
cons_putc (c=10 '\n')
```

**Run the following code.**

```c
unsigned int i = 0x00646c72;
cprintf("H%x Wo%s", 57616, &i);
```

We can put the code in the same place as the previous exercise.

* What is the output? Explain how this output is arrived at in the step-by-step manner of the previous exercise. 

The output is `He110 World`. The decimal `57616` is formatted to hexadecimal `e110` and printed. As we discussed in Exercise 4, on a little-endian machine, `0x00646c72` is stored in memory in this order:

```
4                   0
+----+----+----+----+
| 00 | 64 | 6c | 72 |
+----+----+----+----+
```

Since the format option for `&i` is `%s`, the address of `i` is passed as a `char *`, and `i` represents a C-style null-terminated string, by looking up to the ASCII table using `man ascii`, its value is `rld\0`. The `printfmt()` formats it and prints `rld` to the screen.

* The output depends on the fact that the x86 is little-endian. If the x86 were instead big-endian what would you set `i` to in order to yield the same output? Would you need to change `57616` to a different value?

To the first question, in order to make `i` represent `rld\0`, it should be stored like that in a big-endian platform:

```
4                   0
+----+----+----+----+
| 72 | 6c | 64 | 00 |
+----+----+----+----+
```

So `i` should be changed to `0x726c6400`.

For the second question. Although `0xell0` is stored in a different order on big-endian machines, they are all fetched as unsigned int `0x0000e110`. That's why `57616` doesn't need to be changed.


**In the following code, what is going to be printed after 'y='?**

```c
cprintf("x=%d y=%d", 3);
```

The output on my machine is `x=3 y=1600`.

As we analyzed before, if 3 is located at `0x00`, the program will fetch the data for the second `%d` at `0x04`, since what at there is undefined, it can be anything.

**Let's say that GCC changed its calling convention so that it pushed arguments on the stack in declaration order, so that the last argument is pushed last. How would you have to change `cprintf` or its interface so that it would still be possible to pass it a variable number of arguments?**

To my surprise, the answer to this question is nothing has to change.

For normal arguments, GCC will generate the address for them automatically and these addresses are independent of the order.

For the variable argument list, functions like `va_start()` are defined in `inc/stdarg.h`, and they are implemented with GCC's built-in functions like `__builtin_va_start()`. That is to say, if the calling convention of GCC has changed, these built-in functions will also be changed, thus our code can still run properly.


## Exercise 9

The kernel initializes the stack at line 76 `kern/entry.S` with `movl $(bootstacktop),%esp` instruction setting up the stack pointer. In `obj/kern/kernel.asm`, we can find that the stack pointer is initialized at `0xf0110000`, which was after the kernel code in the 1MB kernel space previously reserved.


## Exercise 10

These disassembly of `test_backtrace()` are related to stack, that's what we are going to analyze:

```
f0100040 <test_backtrace>:
f0100040:	55                   	push   %ebp
f0100041:	89 e5                	mov    %esp,%ebp
f0100043:	56                   	push   %esi
f0100044:	53                   	push   %ebx
...
f0100050:	8b 75 08             	mov    0x8(%ebp),%esi
...
	if (x > 0)
f0100063:	83 c4 10             	add    $0x10,%esp
f0100066:	85 f6                	test   %esi,%esi
f0100068:	7f 2b                	jg     f0100095 <test_backtrace+0x55>
...
		test_backtrace(x-1);
f0100095:	83 ec 0c             	sub    $0xc,%esp
f0100098:	8d 46 ff             	lea    -0x1(%esi),%eax
f010009b:	50                   	push   %eax
f010009c:	e8 9f ff ff ff       	call   f0100040 <test_backtrace>
f01000a1:	83 c4 10             	add    $0x10,%esp
f01000a4:	eb d5                	jmp    f010007b <test_backtrace+0x3b>
```

We can see it first pushes the `%ebp` register to the stack, then `%esi` and `%ebx`, then move stack pointer to 12 bytes lower, then `%eax` which value equals `%esi-1` and finally it calls itself, here it pushes `%eip` implicitly. So it pushes 4+4+4+12+4+4=32Bytes, which as known as 8 words. This can also be proved by the `add $0x10,%esp` instruction executed after calling `test_backtrace()`. By the way, here we can figure out `x` is in the `%esi` register.


## Exercise 11

According to the previous analysis, the stack structure is like this:

```
              4               0
              +---------------+ HIGH
              | saved %ebp    | <---+
              | saved %esi    |     |
stack frame 0 | arg 4 (%ebx)  |     |
              | arg 3         |     |
              | arg 2         |     |
              | arg 1 (%esi)? |     |
              | arg 0 (%eax)  |     |
              | saved %eip    |     |
              +---------------+     |
    %ebp ---> | saved %ebp    | <---+
              | saved %esi    |     |
stack frame x | arg 4 (%ebx)  |     |
              | arg 3         |     |
              | arg 2         |     |
              | arg 1 (%esi)? |     |
              | arg 0 (%eax)  |     |
              | saved %eip    |     |
              +---------------+     |
    %ebp ---> | saved %ebp    | ----+
              | something     |
    %esp ---> +---------------+ LOW
```

`read_ebp()` returns the current value of `%ebp` register. Using the image above, we can easily figure out where all the stack data we need to print out are. Here is my code:

```c
int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
	uint32_t *ebp = (uint32_t *)read_ebp();
	cprintf("Stack backtrace:\n");
	while (ebp != 0){
		cprintf("  ebp %08x  eip %08x  args %08x %08x %08x %08x %08x\n", ebp, ebp[1], ebp[2], ebp[3], ebp[4], ebp[5], ebp[6]);
		ebp = (uint32_t *)(*ebp);
	}
	return 0;
}
```


## Exercise 12

In `kern/kern.ld`, we can find that `__STAB_*` points to the `.stab` section of the elf file which contains the debugging information, as known as the symbol table. It was linked to the kernel and loaded to the kernel memory. The output of `objdump -h obj/kern/kernel` command shows that the kernel does contain a `.stab` and a `.stabstr` section
and `objdump -G obj/kern/kernel` command will print the symbol table out. So `debuginfo_eip()` can read debugging information like function names from the `.stab` section and that's why `__STAB_*` is used.

In `kern/kdebug.c`, we notice that `debuginfo_eip()` uses a `struct Eipdebuginfo` structure to pass the information we want, and the struct was defined in `kern/kdebug.c` like that.

```c
// Debug information about a particular instruction pointer
struct Eipdebuginfo {
	const char *eip_file;		// Source code filename for EIP
	int eip_line;			// Source code linenumber for EIP

	const char *eip_fn_name;	// Name of function containing EIP
					//  - Note: not null terminated!
	int eip_fn_namelen;		// Length of function name
	uintptr_t eip_fn_addr;		// Address of start of function
	int eip_fn_narg;		// Number of function arguments
};
```

Noticed that `eip_fn_name` is not a null-terminated string, the lab page hinted that we can use `printf("%.*s", length, string)` to print non-null-terminated strings.

Now we can enhance the `mon_backtrace()` function with the ability to print debugging information. Here is my code:

```c
int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
	uint32_t *ebp = (uint32_t *)read_ebp();
	cprintf("Stack backtrace:\n");
	while (ebp != 0){
		uint32_t eip = ebp[1];
		cprintf("  ebp %08x  eip %08x  args %08x %08x %08x %08x %08x\n", ebp, eip, ebp[2], ebp[3], ebp[4], ebp[5], ebp[6]);
		struct Eipdebuginfo info;
		if (debuginfo_eip(eip, &info) == 0) {
			cprintf("         %s:%d: %.*s+%d\n", info.eip_file, info.eip_line, info.eip_fn_namelen, info.eip_fn_name, eip - info.eip_fn_addr);
		}
		ebp = (uint32_t *)(*ebp);
	}
	return 0;
}
```

The lab page also indicates the `debuginfo_eip()` is not fully implemented. We must add a call to `stab_binsearch()` to find the line number for an address. Looking up in the `inc/stab.h`, here we should use `N_SLINE` type, and for this type, `n_desc` field holds the line number according to the [STABS - Expanded reference by stab type](http://www.math.utah.edu/docs/info/stabs_12.html)

And Here is my code for `debuginfo_eip()`:

```c
// Search within [lline, rline] for the line number stab.
// If found, set info->eip_line to the right line number.
// If not found, return -1.
stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
if (lline <= rline)
	info->eip_line = stabs[lline].n_desc;
else
	return -1;
```

Don't forget to add a backtrace command to the kernel monitor. It should be added to the `struct Command commands[]` in `kern/monitor.c`

```diff
--- a/kern/monitor.c
+++ b/kern/monitor.c
@@ -24,4 +24,5 @@ struct Command {
 static struct Command commands[] = {
        { "help", "Display this list of commands", mon_help },
        { "kerninfo", "Display information about the kernel", mon_kerninfo },
+       { "backtrace", "Display stack backtrace", mon_backtrace },
 };
```

Now run `make grade` it shall pass all the tests.

```
running JOS: (1.0s)
  printf: OK 
  backtrace count: OK 
  backtrace arguments: OK 
  backtrace symbols: OK 
  backtrace lines: OK 
Score: 50/50
```