Part3 The Kernel
利用虚拟内存解决位置依赖问题
当您检查上述引导加载器的链接地址和加载地址时，它们完全匹配，但内核的链接地址（由 objdump 打印）和加载地址之间存在（相当大的）差异。回去检查一下这两个地址，确保你能看到我们在说什么。(链接内核比引导加载器更复杂，所以链接地址和加载地址都在 kern/kernel.ld 的顶部）。
操作系统内核通常喜欢在很高的虚拟地址（如 0xf0100000）上链接和运行，以便将处理器虚拟地址空间的较低部分留给用户程序使用。这种安排的原因在下一个实验中将会更加清楚。
许多机器在地址 0xf0100000 处没有任何物理内存，因此我们不能指望在这里存储内核。相反，我们将使用处理器的内存管理硬件将虚拟地址 0xf0100000（内核代码希望运行的链接地址）映射到物理地址 0x00100000（引导加载程序将内核加载到物理内存的位置）。这样，虽然内核的虚拟地址足够高，为用户进程留出了足够的地址空间，但它将被加载到 PC RAM 中 1MB 处的物理内存中，就在 BIOS ROM 的上方。这种方法要求个人电脑至少有几兆字节的物理内存（这样物理地址 0x00100000 才能起作用），但 1990 年后生产的任何个人电脑都可能采用这种方法。
事实上，在下一个实验中，我们将把整个 256MB 的物理地址空间（从物理地址 0x00000000 到 0x0fffffffff）分别映射到虚拟地址 0xf0000000 到 0xffffffffff。现在你应该明白为什么 JOS 只能使用前 256MB 的物理内存了吧。
现在，我们只需映射前 4MB 的物理内存，这足以让我们开始运行。我们使用 kern/entrypgdir.c 中手工编写、静态初始化的页目录和页表来完成这项工作。现在，你不必了解这项工作的细节，只需了解它所达到的效果。在 kern/entry.S 设置 CR0_PG 标志之前，内存引用被视为物理地址（严格来说，它们是线性地址，但 boot/boot.S 设置了从线性地址到物理地址的身份映射，我们永远不会改变它）。一旦设置了 CR0_PG，内存引用就是虚拟地址，会被虚拟内存硬件转换为物理地址。 entry_pgdir 会将 0xf0000000 至 0xf0400000 范围内的虚拟地址转换为 0x00000000 至 0x00400000 的物理地址，也会将 0x00000000 至 0x00400000 的虚拟地址转换为 0x00000000 至 0x00400000 的物理地址。任何不在这两个范围内的虚拟地址都会导致硬件异常，由于我们还没有设置中断处理，QEMU 会转储机器状态并退出（如果不是使用 6.828 补丁版本的 QEMU，则会无休止地重启）。
练习 7.使用 QEMU 和 GDB 跟踪 JOS 内核，在 movl %eax, %cr0 处停止。检查 0x00100000 和 0xf0100000 处的内存。现在，使用 stepi GDB 命令对该指令进行单步跟踪。再次检查 0x00100000 和 0xf0100000 处的内存。确保了解刚才发生了什么。
新映射建立后，如果映射没有到位，第一条无法正常运行的指令是什么？注释掉 kern/entry.S 中的 movl %eax, %cr0，跟踪它，看看是否正确。
si之后，
movl %eax，%cr0指令执行完成之后，表示开启了分页模式，分页模式将虚拟地址[0,4MB)和[0xF0000000, 0xF0000000+4MB)映射到物理地址[0, 4MB）。
控制台格式化打印
大多数人都认为像 printf() 这样的函数是理所当然的，有时甚至认为它们是 C 语言的 "原语"。但在操作系统内核中，我们必须自己实现所有的 I/O。
请通读 kern/printf.c、lib/printfmt.c 和 kern/console.c，确保理解它们之间的关系。在后面的实验中，我们会明白为什么 printfmt.c 位于单独的 lib 目录中。
三个文件中函数的关系，如下图所示：
练习 8.我们遗漏了一小段代码，即使用"%o "形式的模式打印八进制数所需的代码。查找并填写这个代码片段。
这段代码，仿照"%u"写，即可，
case 'o':
// Replace this with your code.
num = getuint(&ap, lflag);
base = 8;
goto number;
1、解释 printf.c 和 console.c 之间的接口。具体来说，console.c 输出了什么函数？printf.c 如何使用该函数？
函数之间的调用关系如上图所示
2、解释一下console.c中这段代码：
if (crt_pos >= CRT_SIZE) //如果光标的位置大于了页面的大小
{
int i;
memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));//将crt_buf+CRT_COLS处的字符串转移到crt_buf处，将页面所有的行向上移动一行
for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
crt_buf[i] = 0x0700 | ' ';//0x0700设置前景色为白，背景色为黑，与空格或运算相当于输出一个黑底白色的空格
crt_pos -= CRT_COLS;将光标的位置减去一行
}
//console.h
#define CRT_ROWS 25
#define CRT_COLS 80
#define CRT_SIZE (CRT_ROWS * CRT_COLS)
一个页面最多能放得下CRT_SIZE个字符，因此上述代码是在当一个页面的字符装满后，需要刷新出新的一行。
3、逐步跟踪以下代码的执行过程
int x = 1, y = 3, z = 4;
cprintf("x %d, y %x, z %d\n", x, y, z);
- 在调用 cprintf() 时，fmt 指向什么？ap 指向什么？
- 按执行顺序列出对 cons_putc、va_arg 和 vcprintf 的每次调用。对于 cons_putc，也列出其参数。对于 va_arg，列出 ap 在调用前后指向的内容。对于 vcprintf，列出其两个参数的值。
通过x/s 0xf0101937指令，查得fmt指向cprint中的格式字符串：
通过x/16b指令，查得ap指向栈顶
4、运行以下代码
unsigned int i = 0x00646c72;
cprintf("H%x Wo%s", 57616, &i);
输出结果是什么？按照前面的练习逐步解释输出是如何得出的。
输出结果是：
使用gdb逐步跟踪，关注关键的步骤，首先查看fmt和ap的值：
ap的值中57616为e110，&i对应f010ffec
之后在vprintfmt函数中会调用putch函数，putch函数中的ch的值是72，在ASCII表中可以查得72对应的字符为"H"：
之后的字符输出流程均与上述类似，当打印57616对应的%x的时候，会直接输出57616的十六进制的值，其值就为e110，当轮到&i对应的%s时，在vprintfmt中的switch中会进入's'的分支，其会逐步从反方向将i的十六进制值转换成ASCII对应的值，i的值为0x00646c72，其相对应的ASCII的值为dlr，反方向为rld，因此全部的输出就是He110 World。
输出结果取决于 x86 是小端。如果 x86 是大端的，要得到相同的输出结果，需要将 i 设为多少？是否需要将 57616 改为其他值？
换成大端模式之后，i需要改成0x726c6400，57616无需更改。
这里涉及到大端模式和小端模式
小端模式就是将数据的低位放在低地址空间，数据的高位放在高地址空间
大端模式就是将数据的高位放在低地址，数据的低位放在高地址空间
5、在下面的代码中，"y="后面将打印什么？(注意：答案不是一个具体的值）为什么会出现这种情况？
cprintf("x=%d y=%d", 3);
打印出x=3 y=-267321544
只有3被压入栈，y对应的整数为3对应地址空间+1之后的内存
6、假设 GCC 改变了它的调用习惯，按声明顺序将参数推入堆栈，最后一个参数被推到最后。你将如何修改 cprintf 或其接口，使其仍能传递可变数量的参数？
正常函数将参数压入栈的过程：
例如x=1 y=3 z=4，gcc压入过程
压栈的时候，地址从高位向低位增长，也就是sp减少。
若改变过程，可以初始化一个变量，计数压栈的次数。
堆栈
在本实验的最后一个练习中，我们将更详细地探讨 C 语言在 x86 上使用堆栈的方式，并在此过程中编写一个有用的新内核监控函数，该函数可打印堆栈的回溯：导致当前执行点的嵌套调用指令所保存的指令指针 (IP) 值列表。
练习 9.确定内核初始化堆栈的位置，以及堆栈在内存中的具体位置。内核如何为堆栈预留空间？堆栈指针初始化后指向预留区域的哪个 "端点"？
内核在进入entry的时候，初始化了堆栈。
将堆栈指针指向bootstacktop，bootstacktop的值为0xf0110000，空间大小为4096字节
x86的堆栈指针（esp寄存器）指向堆栈上目前正在使用的最低位置。在为堆栈保留的区域中，低于该位置的所有内容都是空闲的。将一个值推入堆栈包括减少堆栈指针，然后将该值写入堆栈指针指向的位置。从堆栈中弹出一个值包括读取堆栈指针指向的值，然后增加堆栈指针。在32位模式下，堆栈只能容纳32位的值，而esp总是能被4整除。各种x86指令，如调用，都是 "硬接线 "来使用堆栈指针寄存器。
相比之下，ebp（基础指针）寄存器主要通过软件惯例与堆栈相关联。在进入一个C函数时，该函数的序言代码通常通过将其推入堆栈来保存前一个函数的基指针，然后将当前的esp值复制到ebp中，用于函数的执行。如果一个程序中的所有函数都遵守这个惯例，那么在程序执行过程中的任何给定点，都有可能通过跟踪保存的ebp指针链来回溯堆栈，并确定究竟是哪个嵌套的函数调用序列导致了程序中的这个特定点。这种能力特别有用，例如，当一个特定的函数导致断言失败或恐慌，因为它被传递了错误的参数，但你x/x/不确定谁传递了错误的参数。堆栈回溯可以让你找到错误的函数。
练习 10.为了熟悉 x86 上的 C 调用约定，请在 obj/kern/kernel.asm 中找到 test_backtrace 函数的地址，在此处设置断点，并检查内核启动后每次调用该函数时发生的情况。test_backtrace 的每个递归嵌套级在堆栈上推送了多少个 32 位字，这些字是什么？
请注意，为使本练习正常运行，您应使用工具页面或 Athena 上提供的 QEMU 补丁版本。否则，您必须手动将所有断点和内存地址转换为线性地址。
首先在kernel.asm中找到运行test_backtrace函数的地址，并在此设置断点，逐步跟踪，运行的第一个test_backtrace函数输入的参数为5，程序先将0x5压入栈中，再调用call，call指令会将下一条指令入栈保存，进入test_backtrace后，会先将ebp寄存器的值压入栈，可以在gdb中使用info register ebp来查看寄存器的值，到此刻为止栈内的值为：
之后将esp的值赋值给ebp，接下来再设置一个断点在test_backtrace函数中的test_backtrace(x-1)的位置，继续按照上述步骤进行跟踪，在进入test_backtrace(4)前，同样先把0x4压入栈，再将ebp压入栈，再次查看栈内的值：
还是依照上述顺序，逐步查看每次递归的堆栈的值，
test_backtrace(3)：
test_backtrace(2)：
test_backtrace(1)：
test_backtrace(0)：
此时函数的递归堆栈与调用链可以用下图表示(地址和值省略了前四位)：
上述练习应能为您提供实现堆栈回溯函数所需的信息，您应将其称为 mon_backtrace()。kern/monitor.c 中已经有了这个函数的原型。你可以完全用 C 语言实现它，但你可能会发现 inc/x86.h 中的 read_ebp() 函数很有用。您还必须将这个新函数挂接到内核监视器的命令列表中，以便用户可以交互式地调用它。
反向跟踪函数应按以下格式显示函数调用帧列表：
Stack backtrace:
ebp f0109e58 eip f0100a62 args 00000001 f0109e80 f0109e98 f0100ed2 00000031
ebp f0109ed8 eip f01000d6 args 00000000 00000000 f0100058 f0109f28 00000061
...
每一行都包含 ebp、eip 和 args。ebp 值表示该函数使用的堆栈基指针：即刚进入函数和函数序幕代码设置基指针后的堆栈指针位置。列出的 eip 值是函数的返回指令指针：函数返回时控制将返回的指令地址。返回指令指针通常指向调用指令之后的指令（为什么？）最后，args 后面列出的五个十六进制值是函数的前五个参数，这些参数会在函数被调用前被推入堆栈。当然，如果函数被调用时的参数少于五个，那么这五个值将不会全部有用。(为什么反向跟踪代码不能检测出实际有多少个参数？如何解决这一限制？）
打印的第一行反映当前执行的函数，即 mon_backtrace 本身，第二行反映调用 mon_backtrace 的函数，第三行反映调用该函数的函数，依此类推。您应该打印所有未执行的堆栈帧。通过研究 kern/entry.S，你会发现有一种简单的方法可以告诉你何时停止。
练习 11.执行上述反向跟踪函数。使用与示例中相同的格式，否则评分脚本会感到困惑。当你认为你的工作正常时，运行 make grade 看看它的输出是否符合我们的评分脚本的要求，如果不符合，就修正它。在您提交 Lab 1 代码后，欢迎您随意更改反向跟踪函数的输出格式。
如果使用 read_ebp()，请注意 GCC 可能会生成 "优化 "代码，在 mon_backtrace() 的函数序幕之前调用 read_ebp()，这将导致堆栈跟踪不完整（缺少最新函数调用的堆栈帧）。虽然我们已尝试禁用导致这种重新排序的优化，但您可能仍需要检查 mon_backtrace() 的程序集，并确保对 read_ebp() 的调用发生在函数序幕之后。
int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
// Your code here.
uint32_t* ebp;
ebp =(uint32_t *)read_ebp();
cprintf("Stack backtrace:\n");
while(ebp!=0)
{
cprintf(" ebp %08x",ebp);
cprintf(" eip %08x",*(ebp+1));
cprintf(" args");
cprintf(" %08x",*(ebp+2));
cprintf(" %08x",*(ebp+3));
cprintf(" %08x",*(ebp+4));
cprintf(" %08x",*(ebp+5));
cprintf(" %08x\n",*(ebp+6));
ebp = (uint32_t *) *ebp;
}
return 0;
}
写好函数后，在lab目录重新make qemu，输出：
此时，您的反向跟踪函数应能提供堆栈中导致 mon_backtrace() 被执行的函数调用程序的地址。不过，在实际应用中，您往往希望知道这些地址对应的函数名称。例如，您可能想知道哪些函数可能包含导致内核崩溃的错误。
为了帮助您实现这一功能，我们提供了 debuginfo_eip() 函数，它可以在符号表中查找 eip，并返回该地址的调试信息。该函数定义在 kern/kdebug.c 中。
练习 12.修改堆栈回溯函数，以显示每个 eip 对应的函数名、源文件名和行号。
在 debuginfo_eip 中，_STAB* 来自何处？这个问题的答案很长；为了帮助您找出答案，下面是您可能要做的一些事情：
在 kern/kernel.ld 文件中查找 _STAB*
运行 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 的实现。在内核监控器中添加回溯命令，并扩展 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: <unknown>+0 K>每一行都给出了堆栈帧 eip 的文件名和该文件中的一行，然后是函数名和从函数第一条指令开始的 eip 偏移量（例如，monitor+106 表示返回 eip 在 monitor 开始之后 106 字节）。
请务必将文件名和函数名分开打印，以免混淆分级脚本。
提示：printf 格式字符串为打印 STABS 表中的非空字符字符串提供了一种简单但不明显的方法。 printf("%.*s", length, string) 最多打印字符串的长度字符。请查看 printf man 页面，了解其工作原理。
您可能会发现回溯中缺少某些函数。例如，你可能会看到对 monitor() 的调用，但看不到对 runcmd() 的调用。这是因为编译器内嵌了一些函数调用。其他优化可能会导致你看到意外的行号。如果去掉 GNUMakefile 中的 -O2，回溯可能会更合理（但内核运行速度会更慢）。
练习12比较长，主要的任务有三个：
1、搞清楚__STAB_*的来源
2、在内核监控器中添加mon_backtrace命令
3、完善mon_backtrace函数
1、按照提示，查看_STAB的来源，首先查看kernel.ld中.stab的位置。
/* 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 */
}
.stabstr : {
PROVIDE(__STABSTR_BEGIN__ = .);
*(.stabstr);
PROVIDE(__STABSTR_END__ = .);
BYTE(0) /* Force the linker to allocate space
for this section */
}
再运行objdump -h obj/kern/kernel命令
运行objdump -G obj/kern/kernel，其显示debug信息
.Stab就是二进制文件的调试信息，接着看"stab.h"，要注意用红框框住的属性
2、这个任务已经在练习11中完成，就是在monitor.c文件中的commands结构体中和kerninfo一样的形式加入mon_backtrace函数。
3、完善mon_backtrace函数
查看debuginfo_eip函数，会发现这个函数就是将有关debug的信息填充到Eipdebuginfo的结构体中，接着查看一下Eipdebuginfo结构体的定义：
// 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
};
因此思路就是在mon_backtrace函数中，调用debuginfo_eip函数填充Eipdebuginfo结构体后，再读取结构体里的值输出就行了，代码如下：
int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
// Your code here.
uint32_t* ebp;
ebp =(uint32_t *)read_ebp();
cprintf("Stack backtrace:\n");
while(ebp!=0)
{
struct Eipdebuginfo info;
uint32_t eip = *(ebp+1);
debuginfo_eip(eip,&info);
cprintf(" ebp %08x",ebp);
cprintf(" eip %08x",*(ebp+1));
cprintf(" args");
cprintf(" %08x",*(ebp+2));
cprintf(" %08x",*(ebp+3));
cprintf(" %08x",*(ebp+4));
cprintf(" %08x",*(ebp+5));
cprintf(" %08x\n",*(ebp+6));
const char* filename=(&info)->eip_file;
int line = (&info)->eip_line;
const char * not_null_ter_fname=(&info)->eip_fn_name;
int offset = (int)(eip)-(int)((&info)->eip_fn_addr);
cprintf(" %s:%d: %.*s+%d\n",filename,line,info.eip_fn_namelen,not_null_ter_fname,offset);
ebp=(uint32_t *)(*ebp);
}
return 0;
}
返回lab目录，重新make qemu
已经出现了文件名以及函数的位置，但是没有行号，此时就要用到我们上面第一个任务中在stab.h中所留意的信息，在debuginfo_eip函数中补充显示行号的代码：
// 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.
//
// Hint:
// There's a particular stabs type used for line numbers.
// Look at the STABS documentation and <inc/stab.h> to find
// which one.
// Your code here.
stab_binsearch(stabs,&lline,&rline,N_SLINE,addr);
if(lline<=rline)
info->eip_line = stabs[lline].n_desc;
else
return -1;
此时再返回lab目录，重新make qemu，正确显示行号
最后再运行一下评分程序
