MIT6.828 Lab 1: C, Assembly, Tools, and Bootstrapping
前置准备
实现机器为VMWare的虚拟机，操作系统为 Debian-11(无桌面版本)，内核版本为 5.10.0，指令集为 AMD64(i7 9700K)，编译器为 GCC-10
QEMU 虚拟化支持
理论上只需要 qemu 提供软件虚拟化即可，所以硬件虚拟化非必要，libvirt 等相关组件也可以不需要；这里只安装 QEMU
apt install qemu-kvm
其它
使用 clangd 工具链，代码风格对齐 Linux。
Lab 1: C, Assembly, Tools, and Bootstrapping
Lab1 主要汇编、工具链及引导部分。汇编使用 GNU 风格，可以 CS:APP 书籍进行学习。
安装 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。
启动
内存布局
+------------------+ <- 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: +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
- 设置内核内存空间运行环境，跳转