MIT 6.828 Lab1(从引导扇区开始)

同步于语雀,感觉语雀的界面更简洁,推荐√

把环境配置好后, 结合官方文档一起看应该是没什么问题的官方文档

一些前置知识

这里收录了各端口对应的作用, 各个bit的作用等

实模式工作机制

对8086/8088来说计算实际地址是用绝对地址对1M取模. 8086拥有20根地址线, 可以物理寻址字节, 也就是1M空间. 但由于当时的寄存器只有16位, 为了访问这1M内存, Intel采用分段取址的模式,也就是16位段基址:16位段偏移. 取址方式为把16位的段机制左移4位再加上16位的段偏移, 这种技术是处理器内部实现的.

通过这种分段技术, 能表示的最大内存为0xFFFF:0xFFFF=0xFFFF0+0xFFFF=0x10FFEF
也就是1M+64KB-16Bytes.

但8086/8088只有20位地址线, 只能访问1M地址范围的数据.如果访问超过1M的内存, 需要有第21根地址线参与寻址. 不过8086/8088是没有的, 所以计算实际地址时按照1M取模方式进行.
对于80286或以上的CPU通过A20 GATE控制A20(也就是第21根)地址线. 技术发展到80286, 虽然地址总线已经从20根扩展到了24根. 可以访问16M的空间. 但Intel设计时一直贯彻向下兼容的理念, 也就是在实模式下系统表现的行为应该和8086/8088的完全一样. 然而对80286来说, 如果程序员访问0x100000~0x10FFEF的内存, 处理器会实际访问这块内存而不是绕回地址0.

为了解决这种兼容性问题, IBM使用键盘控制器上剩余的一些输出线管理第21根地址线的有效性,称为A20 Gate。若A20 Gate打开, 程序员给出0x100000~0x10FFEF的地址, 系统将访问这块内存区域. 如果被禁止, 那么系统仍使用8086/8088的方式对1M取模.
上述内存访问模式都是实模式. 即使A20 Gate被打开, 实模式下能访问的最大内存也仅仅为0xFFFF:0xFFFF. 要访问之外的内存, 必须进入保护模式

保护模式工作机制

保护模式本身是80286及以后兼容处理器序列后产生的一种操作模式, 它的许多特性设计为提高系统的多道任务和系统的稳定性. 例如内存的保护, 分页机制和硬件虚拟存储支持.

80286及以后的处理器的另一种工作模式是实模式, 本着向下兼容的原则屏蔽保护模式特性, 从而容许老的软件能运行在新的芯片上. 作为一个设计规范, 在系统启动时处于实模式, 被启动程序(操作系统最初的运行代码)重新设置为保护模式. 在此之前任何保护模式的特性都是无效的.

实模式和保护模式区别

实模式中内存被划分为段, 每个段大小为64KB, 段地址用16位来标识, 内存段的处理是通过和段寄存器相关联的内部机制来处理的, 这些段寄存器( CS,DS,SS和ES )的内容构成物理地址的一部分.物理地址=左移4位的段地址+段内偏移

而保护模式下, 段是通过一系列称为"描述符表"的表定义的. 段寄存器存储的是指向这些表的指针(索引). 定义内存段的表有两种: 全局描述符表(GDT)和局部描述符表(LDT). GDT是一个段描述符数组, 其中包括所有应用程序都能使用的基本描述符. 在实模式中, 段长固定为64KB. 而保护模式中, 段长是可变的, 最大可达到4GB. LDT也是段描述符的一个数组. 与GDT不同, LDT是一个段, 其中存放的是局部的,不需要全局共享的段描述符. 每个操作系统都要定义一个GDT, 而每个运行中的任务都有一个对应的LDT。一个描述符的长度为8字节. 当段寄存器被加载时, 段基址会根据段寄存器中的选择子去对应表的对应描述符取出. 如果多次使用一个段, 不需要每次都去GDT或LDT中查询, 因为每个段寄存器还配备了一个64位的描述符高度缓存器, 用于缓存段属性,段机制,段界限.

Booting a PC(Part 1: PC Bootstrap)

boot.S

程序入口处, 由于暂时处于实模式, 所以标记以下以16位模式编译

.globl start
start:
  .code16                     # Assemble for 16-bit mode
  cli                         # 关中断
  cld                         # 串操作方向取反(内存地址向高地址增长)
1
2
3
4
5

然后是用0初始化ds,es,ss这几个段寄存器

# Set up the important data segment registers (DS, ES, SS).
  xorw    %ax,%ax             # Segment number zero
  movw    %ax,%ds             # -> Data Segment
  movw    %ax,%es             # -> Extra Segment
  movw    %ax,%ss             # -> Stack Segment
1
2
3
4
5

接下来就是去打开我们的A20开关, 开启第21根地址线.
由于之前的历史原因, 许多程序以20根地址线的地址回绕特性工作. 当多于20根地址线时, 进位到A20时的数字不会被舍弃, 会造成许多错误. 于是后来, 设计了一个与门控制第21根地址线A20, 并把这个与门控制阀门放在键盘控制器内, 端口为0x60. 向该端口写数据时, 如果第1位是1那么键盘控制器向与门的输出就为1. 与门的输出就决定处理器A20是0还是1.
0x64端口是控制器读取状态寄存器, 向0x60写数据前需要先保证键盘控制器不忙.
先判断0x64端口是否正忙. 通过从0x64中读取的bit1判断, 如果忙, 通过jnz循环跳转.
如果不忙, 就把0xd1写入端口0x64. 这个值最后会被写入0x60, 意味着打开A20 gate.

seta20.1:
  inb     $0x64,%al               # Wait for not busy
  testb   $0x2,%al
  jnz     seta20.1

  movb    $0xd1,%al               # 0xd1 -> port 0x64
  outb    %al,$0x64
1
2
3
4
5
6
7

接下来也是类似, 打开A20地址线

seta20.2:
  inb     $0x64,%al               # Wait for not busy
  testb   $0x2,%al
  jnz     seta20.2

  movb    $0xdf,%al               # 0xdf -> port 0x60
  outb    %al,$0x60
1
2
3
4
5
6
7

接下来是安装GDT(全局段描述符表)`
lgdt gdtdesc
其中gdtdesc是一个标号, 定义在文件末, 前2字节是界限值, 数值为描述符表的大小减1, 后4字节是GDT被安装的物理地址. 通过lgdt指令安装, 处理器会把描述符表的地址和界限值都存入内部的GDT寄存器.

# Bootstrap GDT
.p2align 2                                # force 4 byte alignment
gdt:
  SEG_NULL              # null seg(这是默认的空描述符)
  SEG(STA_X|STA_R, 0x0, 0xffffffff) # code seg
  SEG(STA_W, 0x0, 0xffffffff)           # data seg

gdtdesc:
  .word   0x17                            # sizeof(gdt) - 1
  .long   gdt                             # address gdt
1
2
3
4
5
6
7
8
9
10

最后控制实模式和保护模式的开关是在一个叫CR0的寄存器中. 第一位(位0)是保护模式允许位, 我们需要把该位置置为1.

movl    %cr0, %eax
  orl     $CR0_PE_ON, %eax
  movl    %eax, %cr0
1
2
3

现在已经是保护模式状态, 那么意味着地址访问模式不再是 [16位段地址:16位段偏移]了.
段寄存器应该存段选择子(也就是段描述表中的索引), 不然连下一条指令都无法执行CS:IP.
于是通过一条跳转指令去修改CS,IP寄存器的信息
ljmp $PROT_MODE_CSEG, $protcseg
接下来就进入保护模式了. 除了CS寄存器, 其他段寄存器也应该改一改

.code32                     # Assemble for 32-bit mode
protcseg:
  # Set up the protected-mode data segment registers
  movw    $PROT_MODE_DSEG, %ax    # Our data segment selector
  movw    %ax, %ds                # -> DS: Data Segment
  movw    %ax, %es                # -> ES: Extra Segment
  movw    %ax, %fs                # -> FS
  movw    %ax, %gs                # -> GS
  movw    %ax, %ss                # -> SS: Stack Segment
1
2
3
4
5
6
7
8
9

最后, 通过call调用跳转到c语言程序处. 在此之前, 我们先设置一下栈寄存器的值.
让esp的值变为0x7c00, 也就是恰好往boot.S的反方向增长

movl    $start, %esp
  call bootmain
1
2

最后, 执行完过程返回, 执行一个无限循环

spin:
  jmp spin
1
2

main.c

前面在boot.S中跳转到bootmain过程, 这个过程把操作系统载入到内存中,
readseg((uint32_t) ELFHDR, SECTSIZE8, 0);
readseg把距离内核0位置的SECTSIZE8大小个比特读到物理地址ELFHDR处.
也就是把内核的第一个页(4096)读到内存0x10000处.
内核是ELF格式的, 先判断一下标志位

if (ELFHDR->e_magic != ELF_MAGIC)
        goto bad;
1
2

然后根据ELF头记录的信息找到程序段表的起始位置和终止位置

ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);
    eph = ph + ELFHDR->e_phnum;
1
2

接下来通过一个for循环加载所有段

for (; ph < eph; ph++)
        readseg(ph->p_pa, ph->p_memsz, ph->p_offset);
1
2

最后把头文件的地址ELFHDR->e_entry(内核的入口点)转为一个函数指针, 执行它
((void (*)(void)) (ELFHDR->e_entry))();

Exercise 4

这里官方让你读一下The C Programming Language这本书. 然后读一下pointer.c, 理解一下指针的用法.

#include 
#include 

void
f(void)
{
    int a[4];
    int *b = malloc(16);
    int *c;
    int i;

    printf("1: a = %p, b = %p, c = %p\n", a, b, c);

    c = a;
    for (i = 0; i < 4; i++)
    a[i] = 100 + i;
    c[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;
    *(c + 2) = 301;
    3[c] = 302;
    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;
    *c = 400;
    printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

    c = (int *) ((char *) c + 1);
    *c = 500;
    printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

    b = (int *) a + 1;
    c = (int *) ((char *) a + 1);
    printf("6: a = %p, b = %p, c = %p\n", a, b, c);
}

int
main(int ac, char **av)
{
    f();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

这里的核心就是, 理解指针的实质就是一个起始内存地址, 指针的类型就代表该指针能操作的数据范围. 且如果指针类型大小为siz, 那么对指针加1就是把内存地址加siz.

Loading the Kernel

为了理解boot/main.c, 你需要知道什么是ELF二进制格式.
当你编译并链接一个c程序时(比如JOS内核), 编译器会把c源文件(.c) 转化为一个对象文件(.o), 其中包含硬件期望的二进制格式编码的汇编语言指令, 然后链接器将所有已编译的目标文件组合成一个二进制映像, 比如obj/kern/kernel. 在这里, 它是ELF格式的二进制文件(可执行和可链接格式).
ELF格式非常复杂, 但复杂的部分基本都是支持共享库的动态加载, 在本课程中你不需要了解这么多(用不到). 在6.828中, 你可以把ELF可执行文件看作一个自带加载信息的头文件, 后面跟着若干个连续的代码段或是数据段. boot loader不会修改这些段, 只是把他们加载到指定的内存地址并执行.
一个ELF二进制文件以一个固定大小的ELF Header开始, 再后面是一个可变大小的 program header, 描述着每个程序段的加载方式. c语言中也有ELF Header的定义, 它在头文件inc/elf.h中. 我们对程序段感兴趣的部分有:
1
2
3
4

• .text: 程序的可执行指令
• .rodata: 只读数据, 比如C编译器生成的ASCII字符串常量
• .data: 保存在程序的初始化数据, 如初始化的全局变量如 int x = 5;
• .bss: 存放未初始化变量. 但只需在ELF中记录.bss的起始地址和长度, 内核需要将.bss清零

当链接器计算程序的内存布局时, 它会在内存中.data后面的.bss部分为未初始化的全局变量保留空间. C要求未初始化的全局变量以0值开始. 因此, 不需要在ELF二进制文件中存储.bss的内容, 链接器只需要记录.bss部分的地址和大小, 加载器/内核去初始化.bss节的变量为0值.
输入以下命令检查内核可执行/文件中所有节的名称, 大小, 链接地址

[root@cl lab]# objdump -h obj/kern/kernel

obj/kern/kernel:     file format elf32-i386

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .text         00001917  f0100000  00100000  00001000  2**4
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .rodata       00000714  f0101920  00101920  00002920  2**5
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  2 .stab         00003889  f0102034  00102034  00003034  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  3 .stabstr      000018af  f01058bd  001058bd  000068bd  2**0
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  4 .data         0000a300  f0108000  00108000  00009000  2**12
                  CONTENTS, ALLOC, LOAD, DATA
  5 .bss          00000648  f0112300  00112300  00013300  2**5
                  CONTENTS, ALLOC, LOAD, DATA
  6 .comment      0000002d  00000000  00000000  00013948  2**0
                  CONTENTS, READONLY
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

你可以看到比上面列出的更多部分段/节, 但是其他部分并不重要, 大部分是用于保存调试信息, 这些信息通常包含在程序的可执行文件中, 但不会被程序加载器加载到内存中.
特别注意VMA(链接地址)和LMA(加载地址).
段的加载地址指段应该被加载到内存的哪个位置, 段的链接地址是该段期望从中执行的内存地址.
链接器以各种方式对二进制文件中的链接地址进行编码, 例如当代码需要全局变量的地址时, 如果二进制文件从不是链接地址的地址执行, 那么通常无法工作. (可以生成不包含任何绝对地址的代码, 它被现代的共享库广泛使用, 但我们在6.828不会使用)
通常, VMA和LMA是相等的. 如果不相等, 程序实际执行时应把LMA开始的程序拷贝到VMA处
boot loader使用ELF program headers决定如何加载段. program header指明了ELF对象的哪些部分加载到内存中, 以及每个部分应该占用的目标地址. 你可以输入以下命令查看program headers

[root@cl lab]# objdump -x obj/kern/kernel

obj/kern/kernel:     file format elf32-i386
obj/kern/kernel
architecture: i386, flags 0x00000112:
EXEC_P, HAS_SYMS, D_PAGED
start address 0x0010000c

Program Header:
    LOAD off    0x00001000 vaddr 0xf0100000 paddr 0x00100000 align 2**12
         filesz 0x0000716c memsz 0x0000716c flags r-x
    LOAD off    0x00009000 vaddr 0xf0108000 paddr 0x00108000 align 2**12
         filesz 0x0000a948 memsz 0x0000a948 flags rw-
   STACK off    0x00000000 vaddr 0x00000000 paddr 0x00000000 align 2**4
         filesz 0x00000000 memsz 0x00000000 flags rwx
.....................此处省略......................
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如图所示, ELF对象中需要加载到内存中的区域是那些标记为“LOAD”的区域. 给出了每一项的其他信息, 如虚拟地址vaddr, 物理地址paddr和加载区域大小memsz和filesz
回到boot/main.c, ph->p_pa表示program header中的段目标物理地址
BIOS将引导扇区加载到内存0x7c00处. 这是引导扇区的加载地址, 也是引导扇区执行的位置. 因此, 这也是它的链接地址. 我们通过在boot/Makefrag中将Ttext 0x7c00传递给链接器来设置链接地址, 因此链接器将在生成的代码中生成正确的内存地址.

Exercise 5

追踪引导加载程序的前几个指令, 确定如果引导加载程序的链接地址错误, 那么第一个执行错误的指令是哪个. 然后将boot/Makefrag中的链接地址更改为错误的地址, 运行make clean, make. 再次跟踪到引导加载程序, 看看发生了什么.
这里我直接把0x7c00改为0x6c00.
这里就直接看boot.S了, 看看什么地方用到了链接地址(VMA). 因为BIOS默认把引导程序加载到0x7c00, 如果VMA变化不和0x7c00, 那么程序中所有引用相对地址的指令都可能发生问题
第一条用到的指令就是

lgdt gdtdesc
1

而我们知道其实gdtdesc是在0x7c64才对. 这里势必会对之后保护模式的寻址产生影响.
而之后则更离谱, 我们本意是想通过一条ljmp指令切换CS:IP的值, 可是地址也不是我们期望的
于是程序就错误了.毕竟还是处于保护模式下, 内存可不能随意访问. 处理器加载了错误的GDT, 去GDT找对应的段自然会出错.
让我们回到内核的加载和链接地址. 于引导程序不同, 这两个地址并不相同. 内核告诉引导加载程序以0x100000.( 注意不是0x10000, 这是main.c把第一个页装载进来的物理内存, 只是为了读取如何加载整个内核. for循环根据ELF Header的信息加载的信息才是真正的加载位置). 内核期望从一个高地址执行, 我们将在下一节深入讨论如何实现这一点.
这里补充一下, 你可以用以下命令比对以下内核 和 引导程序的VMA,LMA的值.

objdump -h obj/kern/kernel
objdump -h obj/boot/boot.out
1
2

好了, 除了节信息外, ELF header还有一个很重要的属性叫e_entry. 这个字段包含了程序入口点的链接地址, 程序应该从此处执行。使用以下命令看到内核入口点
objdump -f obj/kern/kernel
现在你应该理解这个迷你ELF加载器了--------boot/main.c. 它把内核的各个节从磁盘读到内存, 然后跳转到内核的入口点.

Exercise 6

在BIOS载入引导程序后, 检查0x100000处的8个字的内存. 然后在引导加载程序跳转到内核时再次检查. 它们有什么不同? 为什么?
这个问题有点简单… 显然是因为引导加载程序main.c把内核加载进来了, 当然不一样了.
内核.text段的加载地址就是0x100000. 如果你想用gdb调试看一下, 可以使用x/Nx ADDR命令观察内存值. 比如, x/8x 0x100000.

The Kernel

现在我们要开始学习这个小型内核----JOS的更多细节. 就像这个boot Loader, 内核以一串汇编代码开始, 最终跳转到c程序运行.

使用虚拟地址(VM)解决地址依赖

当你检查boot loader的VMA和LMA时, 他们是完美的吻合. 但是当检查内核时却有差异. 链接内核比链接boot loader更复杂, 所以我们把链接和加载地址放在kern/kernel.ld的顶部.)
操作系统内核看上去被链接在一个很高的链接地址并运行, 比如0xf0100000, 以便把低地址空间留给用户程序使用. 在下一个Lab我们可以更清楚这样的安排.
许多机器甚至在0xf0100000处没有物理内存, 因此我们不能期望可以把内核直接放在那里.
我们使用处理器的内存管理硬件将虚拟地址0xf0100000(内核的VMA,期望运行的链接地址)映射到物理地址0x00100000(引导加载程序将内核加载的物理内存). 通过这种方式, 尽管内核的虚拟地址足够高,可以预留充分空间给用户程序, 它被加载到物理内存的1MB上的空间, 就在BIOS RAM的上方,这种方式要求PC至少有几MB的物理内存来运行0x00100000, 不过好在自1990年后的PC几乎都满足这个条件.
事实上, 在下个lab, 我们将映射底部的256MB物理内存. 从物理地址的0x00000000~0x0FFFFFFF映射到虚拟地址的0xF0000000 ~ 0xFFFFFFFF. 你现在应该理解为什么JOS只使用物理内存的256MB了.
现在, 我们只映射第一个4MB的物理内存, 这足以使我们启动和运行. 我们使用kern/entrypgdir.c中手写的、静态初始化的页目录和页表来实现这点. 现在, 你不需要了解它是如何工作的, 只需要了解它的效果即可. 一直到kern/entry.S设置CR0_PG标记时, 内存引用被视为物理地址. 一旦设置了CR0_PG，内存引用就是虚拟地址, 由虚拟内存硬件转换为物理地址. Entry_pgdir将范围为0xF0000000~0xF0400000的虚拟地址转换为物理地址的0x00000000 ~0x00400000, 并将虚拟地址0x00000000~0x00400000转换为物理地址0x00000000 ~0x00400000. 任何不在这两个范围的虚拟地址都会导致硬件异常, 由于我们还没设置中断处理, 这会导致qemu退出.

Exercise 7

使用qemu和GDB追踪JOS内核并在movl %eax,%cr0处停下. 查看0x00100000和0xf0100000的内存. 现在，使用stepiGDB指令跳过这条语句, 再次检查0x00100000和0xf0100000, 确保你理解刚才发生了什么.
在新映射建立之后, 如果映射没有在它应在的位置, 第一条无法正常工作的指令是什么? 注释掉kern/entry中的movl %eax,cr0, 对它进行追踪, 看你是否正确.

=> 0x10001d:    mov    %cr0,%eax
0x0010001d in ?? ()
(gdb) x/8x 0x00100000
0x100000:   0x1badb002  0x00000000  0xe4524ffe  0x7205c766
0x100010:   0x34000004  0x0000b812  0x220f0011  0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start-268435468>:  0x00000000  0x00000000  0x00000000  0x00000000
0xf0100010 :   0x00000000  0x00000000  0x00000000  0x00000000
(gdb) si
=> 0x100020:    or     $0x80010001,%eax
0x00100020 in ?? ()
(gdb) si
=> 0x100025:    mov    %eax,%cr0
0x00100025 in ?? ()
(gdb) si
=> 0x100028:    mov    $0xf010002f,%eax
0x00100028 in ?? ()
(gdb) x/8x 0x00100000
0x100000:   0x1badb002  0x00000000  0xe4524ffe  0x7205c766
0x100010:   0x34000004  0x0000b812  0x220f0011  0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start-268435468>:  0x1badb002  0x00000000  0xe4524ffe  0x7205c766
0xf0100010 :   0x34000004  0x0000b812  0x220f0011  0xc0200fd8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

可以发现, 当把eax的值送入cr0后, 0xf0100000的内容就从全零变成了0x00100000的内容.容易想到是发生了地址的映射.
现在把movl %eax, %cr0注释掉, 那么地址映射就失效了, 第一条发生错误的指令是什么呢?
略微分析以下, 前面提到通过映射地址, 把0xF0000000~0xF0400000的虚拟地址映射到了0x00000000 ~0x00400000处. 现在如果没开启虚拟地址转换, 0xF0000000~0xF0400000的地址不会被转换, 任何访问这个地址的内容都会出错.

mov $relocated, %eax
    jmp *%eax
relocated:
1
2
3

这里通过relocated标号跳转, 而relocated最后会是汇编地址+链接地址, 我们知道链接地址是0xF0100000, 那么这个地址必然处于0xF0000000~0xF0400000中, 这样IP寄存器会是一个很大的值, 肯定远超GDT的段界限, 就会出错. 经过调试, 果然如此.
todo: 但是, 这里关于切换虚拟地址转换的步骤, 以及cr0,cr3对应的操作还没弄清楚, 后续补上.

Formatted Printing to the Console

许多人把printf()函数当作理所当然的, 但是在操作系统中, 我们必须自己实现所有的I/O。
阅读kern/printf.c, lib/printfmt.c和kern/console.c, 确保你理解他们间的关系. 在之后的lab中你可以更清楚的了解为什么prinfmt.c位于单独的lib目录中.
先大概浏览一下三个文件, printf.c中的cprintf可以理解为c语言中的printf函数. 在此基础之上, 发现它调用了vcprintf, 接着调用了printfmt.c中的vprintfmt函数.
然后回答下面的问题:

1. 解释printf.c和console.c的关系. 具体来说, console.c暴露了什么函数? 他们是如何被printf.c使用的?

printf.c依赖于console.c, console.c暴露了cputchar(int c)出去. 可以发现cputchar被printf.c的putch函数略微封装了一下, 就先看一下cputchar函数是干嘛的.

// `High'-level console I/O.  Used by readline and cprintf.

void
cputchar(int c)
{
    cons_putc(c);
}

// output a character to the console
static void
cons_putc(int c)
{
    serial_putc(c);
    lpt_putc(c);
    cga_putc(c);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

根据注释, 发现这是一个输出字符到控制台/显示屏的函数, 这就有意思了.
这里我们只主要看一下cga_putc函数. 要显示某个字符, 除了字符本身的ascii之外, 还需要显示这个字符的属性(字颜色/背景色), 所以显示字符需要四字节. 高两字节属性, 低两字节ascii.
上来先设一个默认属性(我记得好像是白底黑字?)

// if no attribute given, then use black on white
    if (!(c & ~0xFF))
        c |= 0x0700;
1
2
3

然后是通过一个switch 去判断该字符, 是一个特殊字符(\b,\n,\r,\t…), 或是一个普通字符.
这里由于屏幕显示模式默认是25*80的, 所以把当前屏幕的所有字符暂存在crt_buf数组中
若字符是普通字符, 简单的加在末尾即可

default:
        crt_buf[crt_pos++] = c;     /* write the character */
        break;
1
2
3

若当前字符是’\t’, 需要替换为四个空格

case '\t':
        cons_putc(' ');
        cons_putc(' ');
        cons_putc(' ');
        cons_putc(' ');
        cons_putc(' ');
        break;
1
2
3
4
5
6
7

若当前字符是’\n’, 直接换行, 也就是直接把crt_pos加一行的索引

case '\n':
        crt_pos += CRT_COLS;
1
2

其他字符也是以此类推.
这样crt_buf数组更新完毕, 判断一下当前字符是否超过了一个屏幕容纳的最多字符. 如果超过, 需要把所有字符往上移一行(舍弃第一行)

// What is the purpose of this?
    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;
    }
1
2
3
4
5
6
7
8
9

最后四句显然就是把缓冲区内容送到屏幕了(了解大概意思即可?)

/* move that little blinky thing */
    outb(addr_6845, 14);
    outb(addr_6845 + 1, crt_pos >> 8);
    outb(addr_6845, 15);
    outb(addr_6845 + 1, crt_pos);
1
2
3
4
5

2. 解释console.c中的下面代码片段

1      if (crt_pos >= CRT_SIZE) {
2              int i;
3              memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
4              for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
5                      crt_buf[i] = 0x0700 | ' ';
6              crt_pos -= CRT_COLS;
7      }
1
2
3
4
5
6
7

第一问已经提到了. 这就是判断缓冲区字符超过屏幕字符了, 舍弃第一行, 把后面所有字符往前提.

3. 追踪以下代码的执行

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

• 对cprintf的调用中, fmt指向什么? ap指的是什么?

int
cprintf(const char *fmt, ...)
{
    va_list ap;
    int cnt;

    va_start(ap, fmt);
    cnt = vcprintf(fmt, ap);
    va_end(ap);

    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12

显然fmt是我们输入的格式串, ap是可变参数集合, 类型为va_list, 里面都是需要格式化的值.
调用顺序为cprintf=>vcprintf=>vprintfmt, vprintfmt中才是实质的内容. 看一下这个函数的参数

void vprintfmt(void (*putch)(int, void*), void *putdat, const char *fmt, va_list ap)
// putch: 写入一个字符的函数指针. 参数第一个int表示字符, 第二个void*表示写入的地址值
// putdat: 写入的初始地址值. 含义于putch的第二个参数类似
// fmt: 格式串
// ap: 格式串需要格式化的所有值
1
2
3
4
5

于是想必vprintfmt就是把格式串转换为最终的输出串, 然后调putch一个字符一个字符输出. 由于这里我们是把字符输出到屏幕, 所以地址值都用不到, putdat参数其实没啥用.

• 按执行顺序列出对cons_putc, va_arg, vcprintf的每次调用. 对于cons_putc，列出它所有的输入参数。对于va_arg列出ap在执行完这个函数后的和执行之前的变化。对于vcprintf列出它的两个输入参数的值。

vcprintf最先调用, 把可变参数集合(需要格式化的值)和原始串等参数传给vprintfmt. vprintfmt是把格式串转化为字符串的函数, 所以开了一个while循环, 每次循环先把百分号%之前的字符全部输出

while ((ch = *(unsigned char *) fmt++) != '%') {
            if (ch == '\0')
                return;
            putch(ch, putdat);
        }
1
2
3
4
5

遇到%后, 就开始使用一个switch的状态机获取这是那种类型的格式. 比如如果是输出数字

case 'd':
            num = getint(&ap, lflag);
            if ((long long) num < 0) {
                putch('-', putdat);
                num = -(long long) num;
            }
            base = 10;
            goto number;
1
2
3
4
5
6
7
8

其中getint就会对可变参数集合ap调用一次va_arg函数获取当前数字.
所以这样调用顺序就明朗了, 一开始调用vcprintf, 然后交给vprintfmt指向. vprintfmt每次把百分号前的字符用cons_putc输出, 然后判断该%是何种格式, 最后用va_arg获取需要的参数。

4. 运行以下代码

unsigned int i = 0x00646c72;
    cprintf("H%x Wo%s\n", 57616, &i);
1
2

输出是什么? 解释下这个输出是如何得到的. 输出取决于x86是小端的这一事实, 如果x86是大端, 你会将i设置为什么以产生相同的输出? 你是否需要把57616改为不同的值?
%x是十六进制输出, 那么57616的十六进制是e110. 看一下之前vprintfmt的对应输出

static void
printnum(void (*putch)(int, void*), void *putdat,
     unsigned long long num, unsigned base, int width, int padc)
{
    // first recursively print all preceding (more significant) digits
    if (num >= base) {
        printnum(putch, putdat, num / base, base, width - 1, padc);
    } else {
        // print any needed pad characters before first digit
        while (--width > 0)
            putch(padc, putdat);
    }

    // then print this (the least significant) digit
    putch("0123456789abcdef"[num % base], putdat);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到[num % base]是在函数末输出的, 第一次输出的应该是数字的最低位. 不过由于这是个递归, 所以最低位反而是最后输出, 那么输出结果就应该是e110而不是011e.
再看第二个格式符%s, 这是输出字符串的表示, 看一下在vprintfmt中的对应实现.
这里实现的比较复杂(考虑了各种左右对齐/输出长度/占位符等), 但是我们看到是直接输出该char*指针后的每个字节即可, 直到遇到’\0’字节.

// string
        case 's':
            if ((p = va_arg(ap, char *)) == NULL)
                p = "(null)";
            if (width > 0 && padc != '-')
                for (width -= strnlen(p, precision); width > 0; width--)
                    putch(padc, putdat);
            for (; (ch = *p++) != '\0' && (precision < 0 || --precision >= 0); width--)
                if (altflag && (ch < ' ' || ch > '~'))
                    putch('?', putdat);
                else
                    putch(ch, putdat);
            for (; width > 0; width--)
                putch(' ', putdat);
            break;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

所以这里就是把i地址指向的值, 一个字节一个字节从低位作为ASCII输出. 由于小端序的原因, 0x00646c72的低字节存储在低地址处, 所以第一个输出的是72, 6c, 64, 00. 然后到此为止.它们对应的十进制分别是114, 108, 100, 0. 通过查阅我们知道小写字符的ASCII从97开始. 于是对应的字符值就是r, l, d. 这样输出就解释的通了.
如果是x86大端, 那么内存中就是高字节放在低地址了, 显然i应该改为0x00726c64.
但是57616不需要变, 我们在c语言中分解数位就是按照高字节先输出的原则. 不存在数字的排列问题.

5. 下面的代码会输出什么?

cprintf(“x=%d y=%d”, 3);
首先一开始输出"x=3"是确认无疑的, 但是后面缺失参数了, 继续调用va_arg会输出不确定的值, 因为那里的内存没有被指定.

6. 假设GCC改变了它的调用约定, 使它按声明顺序把参数推入堆栈, 以便最后一个参数被推到最后. 你应该如何修改cprintf, 以便它能正确运行?

这题好像没看到其他佬的解答, 个人拙见如下, 不正指出.
试想一下GCC为什么设置为参数右到左入栈, 是因为取参数时从栈顶取, 此时栈顶的数据就是第一个参数, 所以直接调用va_arg()可以获取当前参数。如果现在GCC是从左到右入栈, 只需要修改cprintf的参数顺序就可以? 不过这样做获取的可变参数顺序就反了, 后续函数要做处理?

int
cprintf(..., const char *fmt)
1
2

Exercise 8

我们省略了一小段代码------使用"%o"形式打印八进制数所必须的代码. 查找并填充此代码片段.
解决了上面那些问题, 这个就简单许多了. 操作格式串的代码在函数vprintfmt中.
仿照十六进制的模式抄一遍就好了.

case 'o':
            putch('0',putdat);
            num = getuint(&ap, lflag);
            base = 8;
        number:
            printnum(putch, putdat, num, base, width, padc);
            break;
1
2
3
4
5
6
7

Exercise 9

判断以下内核是从哪条指令开始初始化它的堆栈空间的, 以及这个堆栈在内存的哪个位置?内核又是如何给它的堆栈保留一块内存空间的? 堆栈指针又是指向这块被保留的区域哪一端呢?
在此之前, 先让我们了解两个寄存器.
ESP: 栈指针寄存器. 指向栈的已使用的最低地址. 由于栈地址往低处增长, 随着push指令esp越来越小. 当前栈地址用SS:SP的方式寻址, 类似CS:IP。
EBP: 基址指针寄存器. 这里卖个关子, 下面再解释.
在一个函数/过程开始时, 总是伴随着这两条指令(注意这里是INTEL语法)

push ebp
mov ebp,esp
1
2

在函数/过程结束时, 总是伴随着这两条指令

mov esp,ebp
pop ebp
1
2

稍微理解一下, 就能了解到意图. 由于esp是类似于栈偏移指针的东西, 随着栈的使用, esp逐渐减小(栈总是向低地址增长). 当调用者调用某个子过程后, 子过程会使用一些栈空间, esp变得更小. 当子过程返回时, 需要恢复现场, 但是调用者的原esp是什么呢? 没关系, 在进入子过程时已经把原esp放入ebp了, 只需要把ebp赋值给esp就可以恢复.
但是进入过程是为什么要把ebp压栈, 过程返回时从栈中恢复ebp呢?
如果过程只有一级嵌套自然没事. 说的数字化一点, 设l1过程调用l2过程, l2过程调用l3过程
l3返回到l2时, 由于ebp存的是l2的esp的值, l2的esp自然可以恢复, 但是ebp存的仍是l2的esp, 应该恢复成l1的esp才对. 这样就明了了, 需要有个东西来保存各级ebp的值, 那就放在栈中吧!!
如此一来, esp, ebp的含义我们完全可以根据上面的推测来编写
ebp: 存上一级过程的esp值. 进入新过程前先把ebp入栈, 然后更新ebp的值.
说了这么多, 再回到问题本身吧.

内核是从哪条指令开始初始化它的堆栈空间的?

从74行开始的两条指令

movl    $0x0,%ebp           # nuke frame pointer
    movl    $(bootstacktop),%esp  # Set the stack pointer
1
2

这里ebp被清零(这个好理解, 不会返回的过程赋值什么都无所谓)
esp被赋值为bootstacktop, 这个bootstacktop是一个标号, 在文件末尾

这个堆栈在内存的什么位置?内核是如何给它的堆栈保留一块内存空间的?

.data
###################################################################
# boot stack
###################################################################
    .p2align    PGSHIFT     # force page alignment
    .globl      bootstack
bootstack:
    .space      KSTKSIZE
    .globl      bootstacktop   
bootstacktop:
1
2
3
4
5
6
7
8
9
10

看懂这段代码还真不容易, 如果是intel语法就好了. 通过查阅得知以.开头的都是汇编伪指令
这里有一些ARM伪指令的解释
.data: 将定义符开始的数据编译到数据段
.space: 分配一段内存单元，用value将内存单元初始化. 如.space 10,6 分配十个字节单元，并用6填充
于是内核是在entry.S定义的数据段中声明了一块大小为KSTKSIZE的空间作为堆栈, 位置则是在bootstacktop处. bootstacktop通过gdb跟踪可以发现是虚拟地址0xf0110000, 也就是物理地址的0x00110000处. (至于链接器是如何把该汇编文件组织空间的, 暂时还不清楚)

堆栈指针指向该堆栈的哪一侧?

指向bootstacktop, 也就是该堆栈的最高地址, 因为堆栈是向下增长的.

Exercise 10

为了更熟悉C在x86下的调用约定, 可以在obj/kern/kernel.asm中找到test_backtrace函数的地址, 在这里设置断点, 检查每次内核启动时调用它会发生什么. test_backtrace的每个递归嵌套在堆栈上推了多少个32位的字? 这些字是什么?
可以找到test_backtrace()函数就在init.c中, 是个普通的递归函数

void
test_backtrace(int x)
{
    cprintf("entering test_backtrace %d\n", x);
    if (x > 0)
        test_backtrace(x-1);
    else
        mon_backtrace(0, 0, 0);
    cprintf("leaving test_backtrace %d\n", x);
}
1
2
3
4
5
6
7
8
9
10

其实这题的关键就是搞清楚函数调用时各个相关寄存器是如何变化的, 函数是如何返回,恢复的.
那索性我们从头看起, 当我们进入内核entry.S时, 切换完页表后, 通过call 调用到过程i386_init
这部分通过gdb跟踪进入i386_init前的esp, eip, ebp值(注意, 下面使用i r显示寄存器的值时, 当前指令还没执行完, 所以是上一条指令执行完后的状态)

(gdb) b *0xf0100039
Breakpoint 1 at 0xf0100039: file kern/entry.S, line 80.
(gdb) c
Continuing.
The target architecture is assumed to be i386
=> 0xf0100039 :   call   0xf010009d 

Breakpoint 1, relocated () at kern/entry.S:80
80      call    i386_init
(gdb) i r esp
esp            0xf0110000          0xf0110000 
(gdb) i r ebp
ebp            0x0                 0x0
(gdb) i r eip
eip            0xf0100039          0xf0100039 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

可以看到我们直接跳转到0xf0100039执行这条call指令. 在指令执行之前, 可以看到
esp: 栈偏移指针值为0xf0110000. 前面提到页表映射, 那么这里的实际物理地址是0x00110000. 堆栈大小为32KB. 当前处于最高地址, 一点空间都没使用
ebp: 栈帧寄存器, 这里没有意义.
eip: 0xf0100039. 这个值刚好是当前需要执行的指令的地址, 这个也符合认知. 处理器就是根据CS:IP取出指令执行的啊.
在call调用i386_init过程后, 再看看这三个寄存器的值

(gdb) si
=> 0xf010009d :  push   %ebp
i386_init () at kern/init.c:24
24  {
(gdb) i r esp
esp            0xf010fffc          0xf010fffc
(gdb) i r ebp
ebp            0x0                 0x0
(gdb) i r eip
eip            0xf010009d          0xf010009d 
1
2
3
4
5
6
7
8
9
10

ebp没变化. 根据前面的exercise, ebp是进入过程后才变化的.
eip变为i386_init首条指令的地址. 这也很好理解.
但是esp地址变小了4字节, 只能理解为call命令内部会往栈push一些内容, 不妨让我们看看.

(gdb) x/2x $esp    
0xf010fffc: 0xf010003e  0x00111021
1
2

这里发现push的值为0xf010003e.( 这里x/2x是查看内存的两个字, 我这里字长4字节, 看前半部分即可)
这个值就有意思了, 恰好是call i386_init的下一条指令的地址.
那就容易理解了, 假设过程结束后能顺利恢复esp的内容, 那就可以从esp中取得这个地址, 想必处理器会把这个地址恢复到eip寄存器, 这样就能顺利执行之前的指令了.
那esp的值是如何恢复的? 这个问题虽然前面的exercise聊过, 但这里还是再回顾一遍. 我们继续往下跟踪指令, 进入过程i386_init.

=> 0xf010009e :    mov    %esp,%ebp
0xf010009e  24  {
(gdb) i r esp
esp            0xf010fff8          0xf010fff8
(gdb) i r ebp
ebp            0x0                 0x0
1
2
3
4
5
6

首先, 看这里的esp变小了4字节, 因为上条指令把ebp的内容push进去了.
然后这条指令把esp的值赋给ebp, 之后两者肯定相等了, 如下图所示

=> 0xf01000a0 :    sub    $0x18,%esp
0xf01000a0 in i386_init () at kern/init.c:24
24  {
(gdb) i r esp
esp            0xf010fff8          0xf010fff8
(gdb) i r ebp
ebp            0xf010fff8          0xf010fff8
(gdb) x/2x $esp
0xf010fff8: 0x00000000  0xf010003e
1
2
3
4
5
6
7
8
9

果然如此. 不过这里又把esp减了0x18, 这是为了给该函数的一些临时变量使用的. 说实话我很好奇分配多少空间, 由谁分配的, 不过纠结在这里可就没完没了了.
让我们跳过一些指令, 如果到i386_init会怎样呢? 根据上面的分析, 应该首先恢复esp, 然后恢复ebp, 最后恢复eip, 这样就回到上一级过程了. 为了方便直接在反汇编文件kernel.asm中找到过程i386_init结束时候的两条语句.( 注意,官方下载的i386_init末尾是一个while死循环, 这样编译出来是不会有返回语句的, 试着先把它注释掉重新编译进行实验)

leave
ret
1
2

是不是有点晕, 这和之前那些寄存器有什么联系吗? 其实是一样的,这里只是略作包装.
leave指令相当于恢复esp, 也就是把栈帧ebp恢复到esp. esp恢复了, 就可以按顺序恢复之前放入栈中的ebp和eip

mov %ebp,%esp
pop %ebp
1
2

ret指令相当于恢复eip, 这样才能真正回去执行指令(个人猜测)
pop %eip
这样略施小计, 就理解了进入函数和退出函数时各个寄存器的变化, 以及它们如何恢复的.
现在还有一个问题, 就是函数参数是如何传递的? 由于这里i386_init()没有参数, 我们可以追踪一下内部调用的test_backtrace(int). (终于进入正题了? 嘛, 其实和上面差不多吧 )
找到call f0100040 指令

// Test the stack backtrace function (lab 1 only)
    test_backtrace(5);
f01000de:   c7 04 24 05 00 00 00    movl   $0x5,(%esp)
f01000e5:   e8 56 ff ff ff          call   f0100040 
1
2
3
4

可以看到这里首先把0x5这个数送入了当前的栈中. 可以猜到这是函数的参数. 这里开始使用gdb追踪

=> 0xf01000de :   movl   $0x5,(%esp)

Breakpoint 2, i386_init () at kern/init.c:40
40      test_backtrace(5);
(gdb) i r eip
eip            0xf01000de          0xf01000de 
(gdb) i r esp
esp            0xf010ffe0          0xf010ffe0
(gdb) i r ebp
ebp            0xf010fff8          0xf010fff8
1
2
3
4
5
6
7
8
9
10

还记得ebp的值为什么是0xf010fff8? 因为刚开始进入i386_init时esp是0xf0110000, 算上push了四字节的返回地址(用于恢复eip), push四字节的ebp值(用于恢复上一个过程的栈帧), 最后把esp赋值给ebp作为新过程的栈帧, 而esp由于被新过程使用而变成了0xf010ffe0.
接下来第一次进入过程test_backtrace(5)

=> 0xf01000e5 :   call   0xf0100040 
0xf01000e5  40      test_backtrace(5);
(gdb) i r esp
esp            0xf010ffe0          0xf010ffe0
(gdb) si
=> 0xf0100040 : push   %ebp
test_backtrace (x=5) at kern/init.c:13
13  {
(gdb) si
=> 0xf0100041 :   mov    %esp,%ebp
0xf0100041  13  {
(gdb) si
=> 0xf0100043 :   push   %ebx
0xf0100043  13  {
(gdb) i r esp
esp            0xf010ffd8          0xf010ffd8
(gdb) i r ebp
ebp            0xf010ffd8          0xf010ffd8
=> 0xf0100044 :   sub    $0x14,%esp
0xf0100044  13  {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

当前test_backtrace的栈帧0xf010ffd8(栈最高地址).
esp值为0xf010ffc0( 0xf010ffe0-4字节返回地址-4字节ebp-14字节预分配空间)
所以0xf010ffc0到0xf010ffd8就是test_backtrace(5)的栈范围, 输入参数5在 0xf010ffe0处.
接下来跳过一些不改变寄存器的指令, 来到调用test_backtrace(4)的位置

=> 0xf0100064 :  call   0xf0100040 
0xf0100064  16          test_backtrace(x-1);
(gdb) i r eip
eip            0xf0100064          0xf0100064 
(gdb) i r esp
esp            0xf010ffc0          0xf010ffc0
(gdb) i r ebp
ebp            0xf010ffd8          0xf010ffd8
1
2
3
4
5
6
7
8

以此类推… 每一层都是同样的逻辑.
对于任意一层调用, 设它在调用下一层test_trace前, esp, ebp值的含义分别为
esp为当前栈偏移, 且esp指向的内存单元为下一层传入的参数
ebp为上一层的栈偏移, 它指向的内存单元也是上一层ebp寄存器的值.

---

Exercise 11

上面的练习应该为您提供实现堆栈回溯函数所需的信息, 你应该调用mon_backtrace(). 这个函数原型已经在kern/monitor.c了, 你需要完善它.
backtrace()函数应该按以下格式显示函数调用帧的列表:

Stack backtrace:
ebp f0109e58  eip f0100a62  args 00000001 f0109e80 f0109e98 f0100ed2 00000031
ebp f0109ed8  eip f01000d6  args 00000000 00000000 f0100058 f0109f28 00000061
....
1
2
3
4

每一行包括ebp,eip和args.
ebp表示进入该函数使用的堆栈基指针
eip表示函数的返回指令指针, 当函数返回时eip应该恢复到的地址.
args列出的5个十六进制值是相关函数的前5个参数. 如果函数的参数小于5个那它们不都是有用的.
这里提出一个问题, 为什么不能检测到实际上有多少参数? 如何解决这个限制?
注意, 打印的第一行反应当前正执行的函数即mon_backtrace, 第二行反应上一层的函数, 第三行反应再上一层, 以此类推, 打印所有未完成的堆栈帧. 你很容易可以判断什么时候停下来.
先让我们写个流程步骤, 不然会比较乱

1. 把所有参数放入栈中
2, 调用call, 这意味着把call的下一条指令地址push进栈(为了从子过程中恢复eip)
3. push %ebp, 保存ebp值
4. mov %esp,%ebp, 子过程的ebp值就是父过程的esp
5.  ........使用栈, esp逐渐减小
6. mov %ebp,%esp, 从子过程中恢复父过程的esp
7. pop %ebp, 从栈中恢复父过程的ebp
8. pop %eip, 这条指令是我猜的, 因为需要恢复父过程的eip值
1
2
3
4
5
6
7
8

考虑到ebp是上一层函数的esp值, 而每次进入下一层函数时都会执行两个指令

push %ebp
mov %esp,%ebp
1
2

最后push的值就是上一层的ebp值, 那么当前层ebp指向的内存单元就是上一层的ebp值, 这样每层都能获得自己的ebp值.
再考虑eip值. 这个值是call指令会自动push进去的, 所以就是当前层ebp指向的上一个内存单元
再考虑参数值, 这个值是当前层ebp指向的上两个内存单元往后的内存单元
现在考虑如果终止循环. 因为我们这样一直从过程中恢复, 一定会恢复到最外层的过程, 也就是恢复到entry.S中, 这条call语句之前
这样就清楚了, 当ebp恢复到0x00时就可以停下来.
这里附上一张网上流传的一张图, 如果感觉脑子晕晕的, 它一定对你有帮助,
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0FmTv41D-1669131354845)(https://cdn.nlark.com/yuque/0/2022/jpeg/26132078/1669130133753-284327bf-3b3a-4db9-97f7-2252138f348b.jpeg#averageHue=%23eeeeee&clientId=u88bf434f-1cb2-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u25166741&margin=%5Bobject%20Object%5D&originHeight=449&originWidth=407&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u9067182b-8848-49dd-a587-b26b0063904&title=)]
代码如下

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
    // Your code here.
    cprintf("Stack backtrace:\n");
    uint32_t bp = read_ebp();
    uint32_t eip, prebp, va;
    while( bp != 0 ){
        uint32_t* p = (uint32_t*)bp;
        prebp = *p;
        eip = *(++p);
        cprintf("  ebp %08x  eip %08x  args",bp, eip);
        int i;
        for( i=0;i<5;i++){
            cprintf(" %08x",*(++p) );
        }
        cprintf("\n");
        bp = prebp;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Exercise 12

激动人心的时候到了, 这是lab1的最后一个测试.
backtrace()函数应该提供堆栈上导致mon_backtrace()执行的函数调用者的地址. 不过在实践中, 通常还需要知道与这些地址对应的函数名.例如, 你可能想知道那些函数可能包含导致内核崩溃的错误.
为了帮助你实现这个功能, 我们提供了函数debuginfo_eip(), 它在符号表中查找eip并返回该地址的调试信息, 这个函数在kern/kdebug.c中.
修改你的stack backtrace函数, 对每个eip显示对应的函数名, 源文件名和行号.
在debuginfo_eip中, STAB*来自哪里? 为了帮你找到答案, 以下可能是你需要做的事:

• 看文件kern/kernel.ld.
• 运行objdump -h obj/kern/kernel
• 运行objdump -G obj/kern/kernel
• 运行gcc -pipe -nostdinc -O2 -fno-builtin -I. -MD -Wall -Wno-format -DJOS_KERNEL -gstabs -c -S kern/init.c, 然后查看init.s
• 查看引导加载程序是否将符号表当作加载内核二进制文件的一部分加载到内存

通过插入对stab_binsearch的调用来查找地址的行号, 完成debuginfo_eip的实现.
想内核监控器添加一个backtrace命令, 并扩展mon_backtrace的实现以调用debuginfo_eip为每个堆栈帧打印一行

K> backtrace
Stack backtrace:
 ebp f010ff78  eip f01008ae  args 00000001 f010ff8c 00000000 f0110580 00000000
        kern/monitor.c:143: monitor+106
 ebp f010ffd8  eip f0100193  args 00000000 00001aac 00000660 00000000 00000000
        kern/init.c:49: i386_init+59
 ebp f010fff8  eip f010003d  args 00000000 00000000 0000ffff 10cf9a00 0000ffff
        kern/entry.S:70: +0
K>
1
2
3
4
5
6
7
8
9

*在debuginfo_eip中, STAB来自哪里?
这里的_STAB_*应该就是指.stab段的开头位置, 它在kdebug,c是通过extern从外部导入的

extern const struct Stab __STAB_BEGIN__[];  // Beginning of stabs table
extern const struct Stab __STAB_END__[];    // End of stabs table
extern const char __STABSTR_BEGIN__[];      // Beginning of string table
extern const char __STABSTR_END__[];        // End of string table
1
2
3
4

这些变量在kern/kernel.ld被定义. 这是一个链接文件, 指示着如何把多个目标文件链接为一个目标文件, 以及段的内存布局等问题.

/* Include debugging information in kernel memory */
.stab : {
    PROVIDE(__STAB_BEGIN__ = .);
    *(.stab);
    PROVIDE(__STAB_END__ = .);
    BYTE(0)     /* Force the linker to allocate space
                   for this section */
}
1
2
3
4
5
6
7
8

运行两个命令, 观察.stab段的构成
我们知道.stab是与debug有关的段, 这里通过两个命令具体了解一下它的构成和内容.

objdump -h obj/kern/kernel
objdump -G obj/kern/kernel
1
2

-h是老指令了, 我们知道可以通过这个查看各个段的头信息: VMA,LMA之类的. 通过该指令得到.stab会加载到虚拟地址0xf0102130处

2 .stab         00003985  f0102130  00102130  00003130  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
1
2

-G命令通过直接在shell输入objdump回车, 可以看到参数的解释

-g, --debugging Display debug information in object file // 展示该文件的debug信息
这里截取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

-1     HdrSym 0      1226   000018c4 1     
0      SO     0      0      f0100000 1      {standard input}
1      SOL    0      0      f010000c 18     kern/entry.S
2      SLINE  0      44     f010000c 0      
3      SLINE  0      57     f0100015 0      
4      SLINE  0      58     f010001a 0      
5      SLINE  0      60     f010001d 0      
6      SLINE  0      61     f0100020 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以看到其实这是输出.stab段的内容. 我们不妨验证一下, 由于.stab也是一个段, 那么也会被boot/main.c加载到内存VMA位置.
进入gdb, 在引导程序结束后打个断点(先让boot loader把段加载进来), 查看.stab的VMA内存处

(gdb) x/30x 0xf0102130
0xf0102130: 0x00000001  0x04ca0000  0x000018c4  0x00000001
0xf0102140: 0x00000064  0xf0100000  0x00000012  0x00000084
0xf0102150: 0xf010000c  0x00000000  0x002c0044  0xf010000c
0xf0102160: 0x00000000  0x00390044  0xf0100015  0x00000000
0xf0102170: 0x003a0044  0xf010001a  0x00000000  0x003c0044
0xf0102180: 0xf010001d  0x00000000  0x003d0044  0xf0100020
0xf0102190: 0x00000000  0x003e0044  0xf0100025  0x00000000
0xf01021a0: 0x00430044  0xf0100028
1
2
3
4
5
6
7
8
9

这样还不是很明显, 整理一下容易得到每行由12字节构成. 那么容易得到每行的构成按顺序
分别是32位的n_strx
接着是16位的n_desc. 然后是8位的n_othr, 然后是8位的n_type
上面那句当然是错的, 考虑内存读出的是一个十六进制数, 而PC为小端存储, 所以应该先是8位的n_type,再是8位的n_othr,再是16位的n_desc
最后是一个32位的n_value
至于再后面还有一列字符串string({standard input},kern/entry.S). 个人猜测可能是存在一张字符串表(可能就是.stabstr段), 根据n_strx String索引去表中对应的字符串.

0x00000001  0x04ca0000  0x000018c4
0x00000001  0x00000064  0xf0100000
0x00000012  0x00000084  0xf010000c
0x00000000  0x002c0044  0xf010000c
0x00000000  0x00390044  0xf0100015
0x00000000  0x003a0044  0xf010001a
0x00000000  0x003c0044  0xf010001d
0x00000000  0x003d0044  0xf0100020
1
2
3
4
5
6
7
8

事实上也验证了我的推测, 因为在inc/types.h中写好了一个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  符号在文件中的行号
};
1
2
3
4
5
6
7
8

n_type: FUN表示函数名, SLINE表示text段的每一行,SO表示文件名, SOL表示include的源文件.
n_desc: 在文件中的行号
n_value: 如果FUN表示函数入口地址, SLINE表示在函数中的偏移地址.
那么对一个文件来说, 大概的行分布大概是以一个SO类型开始.
接下来是第一个FUN行, 下面一系列的SLINE对应这个函数的每一行.
然后是第二个FUNC, 一系列对应的SLINE, 以此类推…
通过插入对stab_binsearch的调用来查找地址的行号, 完成debuginfo_eip的实现.
那只能先照猫画虎了… 先看一下debuginfo_eip的实现

// Find the relevant set of stabs
    if (addr >= ULIM) {
        stabs = __STAB_BEGIN__;
        stab_end = __STAB_END__;
        stabstr = __STABSTR_BEGIN__;
        stabstr_end = __STABSTR_END__;
    }
1
2
3
4
5
6
7

考虑知道当前行eip的值, 知道.stab .stabstr段的地址范围, 如何得到debug信息.
首先需要确定当前在哪个文件, 这个符号类型为SO, 所以先找到地址小于等于eip的最大的SO行
然后找到地址小于等于eip的最大的FUNC行(可以得到函数名)
最后找到地址小于等于eip的最大的SLINE行(可以得到在文件中的行号)
这样就集齐了所有debug信息.
上面的三个查询过程逻辑类似, 满足单调性, 可以使用二分查找.
先理解一下stab_binsearch函数是如何实现上面的二分过程的, 下面有我加的一些注释

// stabs是.stab段的起始位置, region_left,region_right是条目号
// 该函数在[region_left,region_right]条目中找到类型为type, 且地址小于等于addr的最大条目行. 答案放在region_left中
static void
stab_binsearch(const struct Stab *stabs, int *region_left, int *region_right,
           int type, uintptr_t addr)
{
    int l = *region_left, r = *region_right, any_matches = 0;

    while (l <= r) {
        int true_m = (l + r) / 2, m = true_m; // m为二分的中介点

        // search for earliest stab with right type
        while (m >= l && stabs[m].n_type != type)  // 地址只对同一类型有单调性, 找到最近的type类型
            m--;
        if (m < l) {    // no match in [l, m]
            l = true_m + 1;
            continue;
        }

        // actual binary search
        any_matches = 1;    // 已经匹配了(找到了地址值小于等于eip的,类型为type的条目行)
        if (stabs[m].n_value < addr) {
            *region_left = m;
            l = true_m + 1;
        } else if (stabs[m].n_value > addr) {  // 说明第m+1个条目已经不在当前type的管辖范围了(地址更大), 那么大于等于m+1的条目就更不可能
            *region_right = m - 1;
            r = m - 1;
        } else {
            // exact match for 'addr', but continue loop to find
            // *region_right
            // 恰好找到了eip对应的type类型. 但是这里没有直接break, 为了继续缩小region_right.
            // 作者的意思似乎是想二分到下一个type类型, 这样就可以把region_right固定在下一个type类型之前. (当然可以,虽然没意义,缩小边界使二分更快罢了)
            *region_left = m;
            l = m;
            addr++;
        }
    }

    if (!any_matches) // 没找到这样的条目行
        *region_right = *region_left - 1;
    else {
        // find rightmost region containing 'addr'
        for (l = *region_right;
             l > *region_left && stabs[l].n_type != type;
             l--)
            /* do nothing */;
        *region_left = l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

debuginfo_eip一次查找了当前eip对应的SO行(文件名), 然后查找当前eip对应的FUN(函数名)
我们只需要在最后补齐查找SLINE(行号)即可, 类似的写就好

if (lfun <= rfun) {
        // stabs[lfun] points to the function name
        // in the string table, but check bounds just in case.
        if (stabs[lfun].n_strx < stabstr_end - stabstr)
            info->eip_fn_name = stabstr + stabs[lfun].n_strx; // 函数名
        info->eip_fn_addr = stabs[lfun].n_value; // 函数入口地址
        addr -= info->eip_fn_addr;  // 由于下面查找行号, 行号的n_value的函数内偏移地址, 所以减去.
        // Search within the function definition for the line number.
        lline = lfun;
        rline = rfun;
        stab_binsearch(stabs,&lline,&rline,N_SLINE,addr);
        info->eip_line = stabs[lline].n_desc;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

完成了debuginfo_eip后, 去完善下mon_backtrace函数
这里输出info.eip_fn_name的时候, 末尾会带出一点额外字符.比如test_backtrace(0,+18),实际我们只需要test_backtrace
这里用了printf的一点技巧做到舍弃末尾(抄就完事了, 不重要这个)
printf(“%.*s”, length, string)

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
    // Your code here.
    cprintf("Stack backtrace:\n");
    uint32_t bp = read_ebp();
    uint32_t eip, prebp, va;
    while( bp != 0 ){
        uint32_t* p = (uint32_t*)bp;
        prebp = *p;
        eip = *(++p);
        cprintf("  ebp %08x  eip %08x  args",bp, eip);
        int i;
        for( i=0;i<5;i++){
            cprintf(" %08x",*(++p) );
        }
        cprintf("\n");
        struct Eipdebuginfo info;

        debuginfo_eip(eip,&info);
        cprintf("        %s:%d: %.*s+%u\n",info.eip_file,  info.eip_line,  info.eip_fn_namelen, info.eip_fn_name, eip-info.eip_fn_addr);
        bp = prebp;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

使用make grade测试一下是否正确, 果然满分!!!