MIT6.828 Lab 1: C, Assembly, Tools, and Bootstrapping
環境
實現機器為VMWare的虛擬機，作業系統為 Debian-11(無桌面版本)，內核版本為 5.10.0，指令集為 AMD64(i7 9700K)，編譯器為 GCC-10.
程式碼
Lab 的程式碼克隆自 //pdos.csail.mit.edu/6.828/2018/jos.git
QEMU 虛擬化支援
理論上只需要 qemu 提供軟體虛擬化即可，所以硬體虛擬化非必要，libvirt 等相關組件也可以不需要；這裡只安裝 QEMU：apt install qemu-kvm
Lab 相關變動
安裝 Lab1 的流程，執行 make && make qemu 之後會有報錯，由於裝的作業系統無桌面，gtk 也就沒有安裝。
# qemu-system-i386 -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb tcp::25000 -D qemu.log
Unable to init server: Could not connect: Connection refused
gtk initialization failed
非圖形版本修改如下：
-QEMUOPTS = -drive file=$(OBJDIR)/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb tcp::$(GDBPORT)
+QEMUOPTS = -drive file=$(OBJDIR)/kern/kernel.img,index=0,media=disk,format=raw -nographic -gdb tcp::$(GDBPORT)
解釋一下 qemu 的這條命令 qemu-system-i386 -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -nographic -gdb tcp::25000 -D qemu.log
- drive 指定驅動類型
- format=raw 文件格式，其他的如有 qcow2
- nographic 無圖形頁面
- gdb 接受 gdb 的遠程連接，後續 make gdb 調試會使用到這個點
make qemu-gdb 和 make qemu 多了一個參數 -S，作用為 freeze CPU at startup。
Lab 1: C, Assembly, Tools, and Bootstrapping
啟動
記憶體布局
+------------------+ <- 0xFFFFFFFF (4GB)
| 32-bit |
| memory mapped |
| devices |
| |
/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\
| |
| Unused |
| |
+------------------+ <- depends on amount of RAM
| |
| |
| Extended Memory |
| |
| |
+------------------+ <- 0x00100000 (1MB)
| BIOS ROM |
+------------------+ <- 0x000F0000 (960KB)
| 16-bit devices, |
| expansion ROMs |
+------------------+ <- 0x000C0000 (768KB)
| VGA Display |
+------------------+ <- 0x000A0000 (640KB)
| |
| Low Memory |
| |
+------------------+ <- 0x00000000
簡而言之，最初的處理器最大定址只有 0xFFFFF，然後預留 64KB 給 BIOS 作為保留使用，完全給用戶使用的記憶體空間只有起始的 640KB(0x00000000 ~ 0x000A0000).
BIOS
通過 gdb 跟蹤到第一條執行的指令為 ljmp，地址為 physical address = 16 * segment + offset，[CS:IP] 為 [f000:fff0] 的情況下地址為 0xffff0 = 16 * 0xf000 + 0xfff0.
[f000:fff0] 0xffff0: ljmp $0x3630,$0xf000e05b
為了使 BIOS 加電就被執行，約定好將 BIOS 放在 0xFFFF0 這個位置，機器加電後就將控制權交給 BIOS.
引導程式
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.
像課程說的那樣，和驅動的相關的東西，了解就略過。此處 描述了從硬碟控制器中讀取數據的說明，對應 out*() 簇函數。
引導進程位於 boot/boot.S 和 boot/main.c 中，閱讀程式碼後回答以下幾個問題:
-
At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?
使用ljmp切換為保護模式，ljmp 隨後的movw指令為在 32-bit 執行的第一條指令。 -
What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?
call *0x10018為 bootloader 最後一條執行的指令（也就是((void (*)(void)) (ELFHDR->e_entry))();這行程式碼）;repnz insl為讀取內核的第一條指令，從磁碟文件中讀取出內核的數據。 -
Where is the first instruction of the kernel?
地址為 0x10018 這條指令movw為內核第一條執行的指令。 -
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?
先從第1(下標為 0)個扇區讀取8個扇區的數據，然後通過 ELF 的格式進行解析，通過 ELF 文件頭中的e_phoff欄位拿到程式段表的文件偏移，再通過這個偏移取到每一個段的大小和偏移。
內核
內核在硬碟中的分布緊跟著 bootloader，在 bootloader 中將內核鏡像讀取至物理記憶體 0x100000 處，由於內核鏡像的是 ELF 格式，直接通過 ELF 找到 e_entry(.txt) 段，然後進項跳轉，進入內核的程式碼段中；
內核的程式碼段起始位置通過 kern/entry.S 中的 .global _start 指定了入口。由於我們一般把內核放在高記憶體區域，盡量和用戶使用的記憶體部分錯開。可以在鏈接的情況下指定虛擬地址（通過 kern/kernel.ld），觀察 obj/kern/kernel.asm 中每一條指令的地址，起始地址為 0xF0100000 指令為 add 0x1bad(%eax),%dh，該地址在 kern/kernel.ld 中被指定，其中 0xF0100000 為虛擬地址，0x100000 為物理地址（bootloader 讀取）
readelf -h obj/kern/kernel 可以看到程式段頭 Number of program headers 的值為 3. 內核的入口地址為 Entry point address 值為 9x10000c.
readelf -l obj/kern/kernel 可以看到詳細的資訊 PhysAddr 為物理地址，VirtAddr 為虛擬地址，MemSiz 為段的大小。以此部分內容返回查看 boot/main.c 的邏輯更清晰。
在 kern/entry.S 中做了一個簡單的映射，通過 _start = RELOC(entry) 將 entry 的虛擬地址設置為了 0xF0100000
// readelf -h obj/kern/kernel
ELF Header:
Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Intel 80386
Version: 0x1
Entry point address: 0x10000c
Start of program headers: 52 (bytes into file)
Start of section headers: 91220 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 3
Size of section headers: 40 (bytes)
Number of section headers: 14
Section header string table index: 13
// readelf -S obj/kern/kernel
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS f0100000 001000 0024ed 00 AX 0 0 16
[ 2] .rodata PROGBITS f01024f0 0034f0 000533 00 A 0 0 4
[ 3] .stab PROGBITS f0102a24 003a24 004519 0c A 4 0 4
[ 4] .stabstr STRTAB f0106f3d 007f3d 0017aa 00 A 0 0 1
[ 5] .data PROGBITS f0109000 00a000 009500 00 WA 0 0 4096
[ 6] .got.plt PROGBITS f0112500 013500 00000c 04 WA 0 0 4
[ 7] .data.rel.local PROGBITS f0113000 014000 001044 00 WA 0 0 4096
[ 8] .data.rel.ro[...] PROGBITS f0114044 015044 00001c 00 WA 0 0 4
[ 9] .bss PROGBITS f0114060 015060 000661 00 WA 0 0 32
[10] .comment PROGBITS 00000000 0156c1 000027 01 MS 0 0 1
[11] .symtab SYMTAB 00000000 0156e8 000890 10 12 78 4
[12] .strtab STRTAB 00000000 015f78 000463 00 0 0 1
[13] .shstrtab STRTAB 00000000 0163db 000078 00 0 0 1
// readelf -l obj/kern/kernel
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x001000 0xf0100000 0x00100000 0x086e7 0x086e7 R E 0x1000
LOAD 0x00a000 0xf0109000 0x00109000 0x0b6c1 0x0b6c1 RW 0x1000
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x10
由於涉及到了虛擬記憶體，故需要使用 CPU 特性，開啟記憶體分頁。參考Intel文檔Volume 3: 4.1 PAGING MODES AND CONTROL BITS。
Software enables paging by using the MOV to CR0 instruction to set CR0.PG. Before doing so, software should ensure that control register CR3 contains the physical address of the first paging structure that the processor will use for linear-address translation.
棧
增加編譯選項 -no-pie -fno-pic 來避免產生的位置無關的指令，如 __x86.get_pc_thunk.bx，對閱讀彙編程式碼更友好一些。
調整優化等級 O1 至 O0，直接讓 C 和彙編對應。比如在 i386_init() 中，開啟優化後棧空間佔用了 0x0c 的大小，但是我們只用了兩個變數，應該為 0x08.
調試可以使用 gdb 的 i r edp 來查看 edp 暫存器的值，p/x addr 對 addr 進行十六進位的輸出。
晚上上面的修改動作後，通過閱讀 obj/kern/kernel.asm，定位到棧大小為 32768(8*PGSIZE)，最前設置的棧底為 0x00，棧頂為 bootstacktop，進入到 i86_init() 中後，棧棧底為 bootstacktop+4
之前有一篇讀CS:APP的文章，描述的是x86-64下的函數調用過程。對於函數的調用鏈關鍵點在於這幾個元素
- 返回地址
- 在執行 call 指令時，會將call指令的下一條指令地址壓棧
- 在執行 ret 指令時，從棧彈出並且跳轉（大概的邏輯）
- 棧基暫存器，為當前函數的棧底地址，在進入一個函數中壓棧，返回前退棧
backtrace 要求輸出每一個函數的的 ebp eip args，在一行中顯示。
- ebp 直接從 edp 暫存器中讀取
- eip 為函數的返回地址，在棧底的底下(ebp+4)
- args 參數，和 x64 不同的是 x86 全部使用棧傳遞參數，對暫存器的利用不高。這樣來看backtrace變得更輕鬆一些。
本質上為 上一個棧底地址作為元素被壓入當前棧中，所以獲取到當前的 ebp 暫存器的再進行反覆的回溯就可以解決獲取到 edp rip args.
回溯的終點為 entry.S 裡面設置的 movl $0x0,%ebp
int mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
// Your code here.
cprintf("Stack backtrace:\n");
uint32_t ebp = *(uint32_t *)read_ebp();
while (ebp != 0x00) {
cprintf(" ebp %08x", ebp);
uint32_t eip = *(uint32_t *)(ebp + 4);
cprintf(" eip %08x", eip);
cprintf(" args");
struct Eipdebuginfo info;
debuginfo_eip(eip, &info);
// for (int i = 0; i < info.eip_fn_narg; i++) {
for (int i = 0; i < 5; i++) {
cprintf(" %08x", *(uint32_t *)(ebp + 8 + i * 4));
}
cprintf("\n %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;
}
在實現的時候，理論上 read_ebp() 返回的值應該指針，但是需要解地址才能夠得到和 gdb 中 info reg ebp 相同的值
後續調試的時候結果是在 mon_backtrace 處的斷點還未運行 mov %esp %ebp
Stack backtrace:
ebp f010ff18 eip f01000a1 args 00000000 00000000 00000000 f010004a f0111308
ebp f010ff38 eip f0100076 args 00000000 00000001 f010ff78 f010004a f0111308
ebp f010ff58 eip f0100076 args 00000001 00000002 f010ff98 f010004a f0111308
ebp f010ff78 eip f0100076 args 00000002 00000003 f010ffb8 f010004a f0111308
ebp f010ff98 eip f0100076 args 00000003 00000004 00000000 f010004a f0111308
ebp f010ffb8 eip f0100076 args 00000004 00000005 00000000 f010004a f0111308
ebp f010ffd8 eip f0100102 args 00000005 00001aac 00000660 00000000 00000000
ebp f010fff8 eip f010003e args 00000003 00001003 00002003 00003003 00004003
目前只有一堆和地址相關的東西，沒有可讀性，所以更進一步，補充函數名稱，文件及返回地址所在行號。
JOS預先提供了一個幫助函數 debuginfo_eip，和一個結構體 struct Eipdebuginfo。函數名稱，文件名，及返回地址所在行號都定義在結構體內，只需要補充實現完這個 debugifo_eip 就可以獲取到相關的資訊。目前的輸出資訊如下：
eip_file=kern/init.c eip_fn_name=i386_init:F(0,1) eip_fn_addr=f010009a eip_line=0, eip_fn_narg=0
需要對 eip_fn_name 進行修改，eip_line 補充獲取。
根據實驗提供的方向，我們可以通過讀取 .stab 的內容讀取相關資訊，使用命令 objdump -G obj/kern/kernel 可以得到
// 這裡截取截取部分輸出
obj/kern/kernel: file format elf32-i386
Contents of .stab section:
Symnum n_type n_othr n_desc n_value n_strx String
...
obj/kern/kernel: file format elf32-i386
Contents of .stab section:
Symnum n_type n_othr n_desc n_value n_strx String
-1 HdrSym 0 1477 000017fa 1
0 SO 0 0 f0100000 1 {standard input}
1 SOL 0 0 f010000c 18 kern/entry.S
...
13 SLINE 0 83 f010003e 0
14 SO 0 2 f0100040 31 kern/entrypgdir.c
15 OPT 0 0 00000000 49 gcc2_compiled.
16 GSYM 0 0 00000000 64 entry_pgtable:G(0,1)=ar(0,2)=r(0,2);0;4294967295;;0;1023;(0,3)=(0,4)=(0,5)=r(0,5);0;4294967295;
17 LSYM 0 0 00000000 160 pte_t:t(0,3)
18 LSYM 0 0 00000000 173 uint32_t:t(0,4)
19 LSYM 0 0 00000000 189 unsigned int:t(0,5)
20 GSYM 0 0 00000000 209 entry_pgdir:G(0,6)=ar(0,2);0;1023;(0,7)=(0,4)
21 LSYM 0 0 00000000 255 pde_t:t(0,7)
22 SO 0 0 f0100040 0
23 SO 0 2 f0100040 268 kern/init.c
24 OPT 0 0 00000000 49 gcc2_compiled.
25 FUN 0 0 f0100040 280 test_backtrace:F(0,1)=(0,1)
26 LSYM 0 0 00000000 308 void:t(0,1)
27 PSYM 0 0 00000008 320 x:p(0,2)=r(0,2);-2147483648;2147483647;
28 LSYM 0 0 00000000 360 int:t(0,2)
29 SLINE 0 13 00000000 0
30 SLINE 0 14 00000006 0
31 SLINE 0 15 00000019 0
...
對照符號表的結構體 struct Stab
// Entries in the STABS table are formatted as follows.
struct Stab {
uint32_t n_strx; // index into string table of name
uint8_t n_type; // type of symbol
uint8_t n_other; // misc info (usually empty)
uint16_t n_desc; // description field
uintptr_t n_value; // value of symbol
};
在 inc/stab.h 中使用到的 n_type 為
- SO 主源文件，可以通過這個欄位來找到對應的源文件
- FUN 函數名，對應的函數名稱
- SLINE 程式碼段行號
。stab 符號表的內容依次按照源文件/函數名稱/程式碼段行號排布。比如 test_backtrace 的實現在 kern/init.c 內，行號為 13.
10 // Test the stack backtrace function (lab 1 only)
11 void
12 test_backtrace(int x)
13 {
14 cprintf("entering test_backtrace %d\n", x);
15 if (x > 0)
16 test_backtrace(x-1);
17 else
18 mon_backtrace(0, 0, 0);
19 cprintf("leaving test_backtrace %d\n", x);
20 }
對應 test_backtrace 的查找演算法，在本實驗中使用二分查抄，關鍵點為 eip 地址
- 全局範圍內，比較 eip 的地址找到類型為 SO 對應的源文件的行範圍，這裡為 kern/init.c
- 縮小範圍為該源文件內的符號表，找到類型 FUN 找到對應的函數行範圍，這裡為 test_backtrace
- 縮小範圍為函數範圍的符號表，找到類型為 SLINE 的行，取欄位 n_desc 這裡為 13
- 對應的返回地址在函數的偏移計算，直接 eip 地址減去 eip_fn_addr 即可
函數參數個數準確輸出
這個還是解析 .stab 內容得到結果。實現非常簡單，只需要從 fun 開始找到 PSYM 類型行的個數就可以
for (lline = lfun + 1; lline < rline && stabs[lline].n_type != N_SLINE; lline++)
if (stabs[lline].n_type == N_PSYM)
info->eip_fn_narg++;
info->eip_line = stabs[lline].n_desc;
最終輸出結果如下，由於這個結果不能通過 case 的校驗，所以只能作為擴展
K> backtrace
Stack backtrace:
ebp f0110f38 eip f0100f2b args 00000001 f0110f58
kern/monitor.c:96: runcmd+323
ebp f0110fa8 eip f0100fbb args f01142c9
kern/monitor.c:135: monitor+95
ebp f0110fd8 eip f010012d args
kern/init.c:24: i386_init+128
ebp f0110ff8 eip f010003e args
kern/entry.S:44: <unknown>+0
TODO
虛擬記憶體的映射邏輯，在下一個 Lab 中展開。
控制台顏色輸出，非作業系統核心內容，暫時跳過。
LAB1 總結
一個關於內核啟動的記憶體布局圖
+------------------+ <- 0xFFFFFFFF (4GB)
| 32-bit |
| memory mapped |
| devices |
| |
+------------------+ <- (2GB+Kernel Program Size)
| (JOS) Kernel |
+--------> +------------------+ <- 0xF0100000 (2GB+1MB)
| | |
| +------------------+ <- 0xF0000000 (2GB)
| /\/\/\/\/\/\/\/\/\/\
|
| /\/\/\/\/\/\/\/\/\/\
| | |
3 | Unused |
| | |
| ------------------+ <- depends on amount of RAM
| | |
| | |
| | Extended Memory |
| | |
| +------------------+ <- 0x00100000 (1MB+4KB)
+--------- | (JOS) 1st Page |
+-----> +------------------+ <- 0x00100000 (1MB)
| +-- | BIOS ROM |
| | +------------------+ <- 0x000F0000 (960KB)
| | | 16-bit devices, |
2 | | expansion ROMs |
| 1 +------------------+ <- 0x000C0000 (768KB)
| | | VGA Display |
| | +------------------+ <- 0x000A0000 (640KB)
+-- v - | (JOS) 1st Sec |
+-> +------------------+ <- 0x00007C00 (31KB)
| |
| Low Memory |
| |
+------------------+ <- 0x00000000
- BIOS 載入硬碟鏡像的第一個扇區至 0x7C00，並且跳轉
- 1扇區將後面的作業系統載入進記憶體 0x100000 及將作業系統的程式段載入至高記憶體區域 0xF00100000，然後跳轉至內核的入口地址 e_entry
- 設置內核記憶體空間運行環境，跳轉
