15 造轮子的方法和乐趣（2024年）

本视频是《计算机系统基础》课程的复习课，探讨了实验课的意义、PA实验的设计初衷，并深入讲解了程序执行作为状态机的核心概念。

UP主: why_hy_y · 时长: 1h21m · 🔗 B站原视频

标签: 计算机系统基础 · 大学课程 · 汇编语言 · 状态机 · PA实验

课程回顾与期末复习安排

那我们先去上课吧。我们这堂课和下一堂课应该都算是复习课。今天是用一个例子来穿插一下，看一下我们整个这个学期学了一些什么样的东西，大概我们计算机系统基础这门课程做了一些什么事情。你会发现在这个过程中，实际上我们有一些环节的设计，或者有一些环节的锻炼，大家在 PA 中已经有过一些锻炼，可能大家没有感受过，我们可以回头看一看。

下一堂课呢，我们会面向期末考试这一方面来带给大家复习一下，整个实验课跟期末考试比较相关的，用一个汇编的例子来带大家读一读那个代码。更多的理论课的复习，大家看理论课老师是怎么安排的，理论课的复习应该会跟期末考试更相关一点。

为什么需要授课型的实验课

总的来说，我们今天的这堂课就是想要回答一个问题：我们整个计算机系统基础这门课学了些什么？尤其是有了理论课之后，为什么还需要一门授课型的实验课？大家应该也有感触，我们的实验课实际上所有的得分都是 PA 实验的完成，但是我们的实验课却不是一个设计在机房让大家去完成实验、老师助教给大家答疑的这么一个形式。我们为什么需要一个在课堂上讲的类似形式的实验课？

更多的原因是因为，理论课的很多教学更多的是停留在教材上的一些例子、教材上的一些知识，老师会给大家讲一讲。但是更贴近我们现在的系统里面到底是怎么运行的，以及一些运行的细节，甚至是理论课的知识是不是正确、是不是能够反映到现实系统的一些实现（application）上，这个我们会在实验课一般带大家去过一遍。这个是实验课的主角。PA 实验不仅仅是为了得分，我们会设计这个实验，让大家在课后去融会贯通一下。

核心理念：程序的执行是一个状态机

这个问题实际上是很大，换任何一个课程，我都希望大家在学完之后，大概能够回忆得起这一个学期到底学了些什么事情。这个问题其实很多学校，包括我们学校也会在考研的时候喜欢问大家：上过这么多计算机的专业课，比如计算机网络这门课，给你留下了最深的印象是什么？大概上了一些什么课？

那计算机系统基础这门课上完之后，给大家留下的印象呢，我很不希望到时候大家可能两年之后回忆起留下的印象是：我好像上了一门不太记得上了什么课，但是我就记得我做了一个半途而废的实验。希望最后给大家留下的印象起码是：即使实验没有做完，但是我经过这一学期的学习，感觉比上这门课之前有了明显的提升。不管这个提升的幅度有多大，我觉得这门课就是有很大的效果的。因为并不是每一门课能够在上完之后，你都觉得自己专业技能上有提升了，我相信大部分同学很多的课程更多的是期末考试之前的一个预习，这也是一个常态。那我希望我们这门课作为一个实践类的课程，还是跟大家的实践能力紧密相关，能够有一些提升的。

除了实践能力的提升之外呢，是希望大家对整个计算机系统能有一个不一样的认识。其中最重要的一句话就是：我们整个计算机系统中，程序的执行是一个状态机。包括大家 PA 的完成里面的一步一步的环节，都是让大家去感受作为一个状态机，它的状态是如何转移的，它的每一个状态是如何表征的等等。

探究编译过程：从源码到可执行文件

我们先来看一下，回到我们这门课的第一堂课。当时问了大家一个问题：在大家写完之后，即使只有一两行代码，比如我们就写了一个 printf，这样的一个程序，在按完了一个 button，它编译运行产生最后的可执行文件，这个过程中到底发生了什么事情？以及我产生的可执行文件，我一点运行，它真的可以跑在我们的系统上，在屏幕上打印了一个 "hello world" 的字样，这样的一个实际运行的动态过程，它又完成了什么事情？

大家能看到这两个环节其实不太一样。一个是程序的正常运行的动态过程，一个是程序运行之前的准备阶段。这两个过程分别做了一些什么事情？我们会在课上告诉大家，前一个过程，从源码到最后可执行文件的过程中有几个部分。包括大家上编译原理课程，你会更加明显的感觉到，这个过程中分成几个部分，它有各自的一些用途。

但是这几个部分到底是不是真的存在？还是说比如你写一个 GCC 的命令行，让它把 a.c 编译运行，编译、汇编、链接整个过程完成之后产生 a.out，实际上是一个可执行程序。看起来命令行中就是一个 gcc a.c，那为什么我们会说这个过程中有几个明显的步骤风格呢？为什么不是计算机一个工具就做完了这一堆事情，没有中间的这些步骤，就是一个完整的大模块呢？

这个问题很天然，因为大一小朋友刚进来，刚写 hello.c，根本不知道中间有这么多步骤，就知道 IDE 能够帮我把源码一下子变成了最后的可执行代码，中间的整个环节对他来说就是一瞬。那到底是一步这样的理解比较正确呢，还是按步骤理解会更合适一点呢？我们能不能明显地给出一些证据，能够告诉我们这几个步骤真的是存在的？

观察状态机与系统调用

为了去做这件事情，我们可以看一看。假如这件事情真的存在，实际上我们应该能够观察到，比如点一个 button 或者用 gcc a.c 这一条命令的背后，这个编译运行的过程，它也是一个程序运行在我们的系统中。所以我们对这个程序本身的理解，也肯定是可以把它理解成一个状态机。因为我们说过所有程序的执行都是一个状态机，它运行在我们的系统中，就是把这个状态从一个状态经过某条指令到另一个状态，不断地去转移，不断地向下走。

在这个过程中，如果 gcc a.c 能够整个过程被分成编译、汇编、链接，那我们是不是应该能够在状态机中明显地看出，有一部分的状态转移是跟编译相关，有一部分是跟汇编相关，有一部分是跟链接相关的呢？我们应该能明显看到。但是作为一个普通的程序，你想一个很简单很简单的程序，它的状态机转移的状态数量都是很高的。那 GCC 做了一个编译源码并且能够生成可执行代码，整个这个过程中应该会考虑很多很多的事情，它的状态数量肯定是已经超出了我们能 handle 的一个量级了。那我怎么样去观察它、分析这样的一个状态机呢？

权限管理与系统调用（System Calls）

我们之前讲过，比如大家自己写一个 C 程序，你会能够看到你在程序中写的更多的是一些赋值语句，操作数和算术计算的一些语句等等。这些东西更多的是在做什么事情呢？就是从内存中去读一个数据、写一个数据，或者把内存中的几个数据加加减减做一些操作，更多的就是 computation。

除此之外呢，比如我们想跟 IO 去做交互，想从键盘中去读一个键，你会发现我们实际上没有写出直接的代码要去跟哪一个 IO 或者是哪一个 IO 的端口去做交互。这些代码我们是没有写过的。那我为什么能够用 printf 这个函数的调用就能够实现往屏幕上打印东西呢？大家能够写的更多的只是对内存跟数据的一个算术任务，那这些跟外界的交互，这种看起来跟算术任务很不一样的东西，到底是怎么实现的呢？

这种 IO 的操作超出了一个低权限下客户程序能够做到的一件事。我们之前讲到过，有一个建立权限管理的 ring 的图。比如我们把 ring 0 一个高权限和一个低权限的图分开画，我们自己写出的客户程序就是一个低权限，而像 Linux 操作系统就是一个高权限。高权限和低权限能做的事情肯定是不同的。我们能够往屏幕上去打印东西，真正把这个东西传给屏幕，实际上是有一个低权限向高权限请求，把一些东西发送给它，借助于高权限开放给低权限下的一个方式——也就是以我们常说的系统调用的方式。

低权限的程序想做一些打印屏幕跟 IO 操作，本身是不可以做的，可以利用操作系统开放的系统调用接口，利用系统调用来实现各类超出权限的任务。所以实际上在观察一个 hello.c 程序的打印，观察这个程序运行的过程中调用了哪些系统调用，我们可以用 strace 直接去看。你实际能够发现 printf 的这一行代码，最终慢慢往里挖，你是能够看到 printf 最终是投到了一个 write 的系统调用中。这个 write 的系统调用才是一个高权限下能够跟外界 IO 打交道的方式，它才能够给屏幕去输出。所以这个中间都是借助于系统调用。

使用 strace 追踪 GCC 编译过程

这里我们想要去观察作为一个 gcc a.c，它在整个运行过程中最重要的是什么呢？我可以排除掉另外一些跟系统调用无关的，我就想要看其中比较关键的系统调用到底用了一些什么样的东西。我就可以在这个过程中通过观察哪一些指令是跟系统调用相关，把一个很长、不好分析的序列变得精简一点。

如果我们想从指令的角度去理解这个状态机，跟系统调用相关的最重要的指令就是这条 int 指令。我们之前讲到过 int 指令是引发中断，后面跟的数字代表不同的含义。这里 int 0x80 就是一个代表系统调用的中断。系统调用要做的事情就是让 CPU 在执行本身程序的过程中，做当前任务和另一个任务之间的一个切换。所以就会借助于中断，借助于这一条中断的指令，跳到更高权限下的系统调用该做的事情上面。所以这个时候我们可以观察这个 int 0x80 到底什么时候出现。

更多的呢，比如我们想观察所有的系统调用，一种办法是每个系统调用一定会以 int 0x80 开始，我们还可以直接利用 strace 这样的一个工具。strace 这个工具本身大家去看文档就会发现，它能够追踪所有的系统调用。所以我们用 strace gcc a.c，你就能够看到编译 a.c 这个文件的整个过程中，一共用到了哪些系统调用。

临时文件与 vfork 系统调用

我们可以来大概先看一眼。在这个过程中，你能够看到里面其实有很多很多的系统调用。比如有一些不同的 access，还有一些 pipe，这是管道的建立，还有 unlink。最后这个是整个系统调用最后的几行，虽然东西太多了，但是我们能看到有一些熟悉的东西。比如 GCC 带不同的选项时，你可以让它输出中间的一些临时文件，比如 .i、.s、.o。这些东西默认不保存，但是你可以通过给它选项让它输出。现在我没有给它选项，你直接 strace 去打印的时候，你会发现最后在它结束的时候，它真的做了一个 unlink 某一个文件，而这个文件当前是临时文件的名称，并且它的后缀是 .o、.s。看起来就像是我们真的是经过编译生成的 .s，经过汇编生成的 .o 这样的目标文件，好像真的是存在的。只是它在我生成 a.out 之后，就把中间用到的这些临时文件给删掉了。所以从临时文件的角度，还是有几个步骤的。

除了这个之外呢，我们在这个上面还能够看到一些系统调用，比如 close 关闭管道，然后 read 从某一个管道中读取特定的字节数。这里有一个最重要的是做 vfork。

fork 与 vfork 的区别

vfork 是什么意思呢？虽然之前课上没有讲到过 vfork，但是我们讲到过 fork。当时讲解 fork 的时候跟大家说，fork 就像是一个叉子，它做的事情是把当前进程在调用 fork 这个点的状态机原封不动地拷贝一份，创建它的子进程。当时我们说子进程当前跟父进程之间是没有任何差别的，除了它的进程号。然后我们就可以在这样的两个完全一致的状态机基础之上，一边执行 NEMU，一边执行 QEMU，形成了 differential testing（差异测试）。

那这个 vfork 跟 fork 概念上好像是很像的，它们俩唯一的区别在什么？fork 当时生成的父进程和子进程，这两个东西是完全独立的，两边做不同的任务，它们俩之间的内存数据是不共享的。那 vfork 稍微有一点点不一样。vfork 是父进程通过 vfork 出一个子进程，父进程是需要等待子进程去执行结束，然后父进程再往后走。并且子进程当前虽然拷贝了父进程的状态，但这个时候子进程并不是一个完全独立的进程，它可以共享父进程的内存数据。这个是 vfork 和 fork 不太一样的一个地方。

所以 fork 有点像是我这边真的是两个完全独立的进程，互相之间是没有影响的；但是 vfork 有点像是在我主的父进程的基础之上，在这做了一个子进程，做完一堆事情，父进程再接着往下去走。就好像是在那个状态机上叉出来一条旁路，要等待旁路完成之后，父进程再往前走。

strace 的子进程追踪与管道重定向技巧

我们就可以看到用 strace 直接去打印 gcc a.c，你能够看到调用了很多的系统调用。在这个时候，我们看 vfork 在这里生成的这个子进程，其实这个子进程是一定要跟管道相关的。因为我们在 vfork 之前是关闭了管道 4，建立了 4 到 5 之间的一个映射，然后 vfork 跟子进程创建好了之后，关闭管道 5。你会发现子进程创建完了之后，这个管道就立刻被关闭了。子进程到底做了什么事呢？难道子进程一个系统调用都没用过吗？这里 vfork 内部产生的这个子进程，它所有用到的系统调用当前没有被追踪到。因为 strace 直接去追踪，你给它传入一个进程，它只会去观察当前你给我的这个进程的系统调用，不会去再往下走，它引发的各种各样的子进程我是不会再去追踪的。所以直接 strace 这样看，我其实没有办法追踪到一个父进程通过 vfork 创建出来的子进程内部的系统调用。所以这个东西不全，并不是 gcc a.c 所有关联的创建的系统调用的全貌。

还有一个小的注意点，比如我直接 strace gcc a.c，因为输出的东西很多，你不太能往上翻。所以一种常见的操作是把它通过管道给 less 做一个分页，你就可以上下去翻。一般这么做都没有什么问题，但是你如果 strace gcc a.c 直接给 less，你一按上键翻页，它就会变成空白。为什么呢？因为你通过竖杠的管道做的事情，是把前面的标准输出（stdout）给了后面这个可执行文件的标准输入（stdin）。但是我们实际跟输入输出相关的流有三个：标准输入流、标准输出流，还有标准错误流（stderr）。strace 的很多输出是以 stderr 输出的。所以这个时候你直接给它，你会发现输出的东西不完全是你想要的。

那还有一种办法，你可以通过 strace 的 -o 选项让它去输出，或者在它输出给 less 之前，对它做一个管道的重定向，把 stderr 重定向给 stdout，然后再把标准输出通过管道给 less（即 2>&1 | less）。这是一个小的 trick，这样才能够做到给了 less 之后可以上下翻页。

识别编译与汇编的子进程环

我们可以把所有的输出放到 Vim 里，这件事情我们之前也做过。放到 Vim 里有一个最大的好处，就是我们可以挑挑拣拣，把不关心的或者跟分析目标无关的删掉，精简到最关心的部分。比如我们把一些辅助的 log 删掉之后，因为现在 strace 还没有给它任何的选项，所以 vfork 暴露出来的子进程还是没有被追踪。但是我们起码可以知道每一次 vfork 产生的时候，我都应该是在父进程的状态机中创建了一个子进程。虽然子进程当前的系统调用没有被追踪，但是我知道在这儿有一个。完了呢，实际上 close 的时候子进程是结束了的。

这个时候你会在这里面看到不止一个 vfork，出现了一个类似小环的结构。我们看一下每一个小环做了一些什么样的事情。比如在 vfork 之前，父进程用 open 这个系统调用打开一个文件，如果不存在就创建它。所以它实际上是创建了一个临时文件，当前是空的。然后 vfork 子进程做了一些事情，实际上是在这个临时文件中写入了一些东西。所以大家都可以想到，这个子进程是不是应该做的是汇编？汇编步骤最终会创建一个 .o 的文件，所以这个 vfork 实际上是在创建这个 .o 的文件。

在这个步骤之前呢，有个几乎一模一样的系统调用序列，也是父进程创建了一个 .s 的文件，然后子进程做编译，把原来的 .c 文件编译成 .s 文件。最后你会发现，最终它又在整个 gcc a.c 退出之前，把这些生成的所有临时文件都 unlink 掉，等于是销毁掉。

深入追踪：execve 与 cc1 编译器

现在因为我没有追踪子进程做了些什么事，我还不知道这个环到底是不是真的做了汇编、真的做了编译。我们就可以让 strace 读一个选项，给一个 -f 的选项。因为这是一个很常见的功能，我想要追踪不止你传入的这个进程，还有以这个进程为基础创建出来的各种各样的子进程，我都希望不断地往下追下去。所以我们就可以给它一个 -f 的选项，这也是 strace 支持的。

如果我们通过 -f 的选项再去重跑一下，比较明显的区别是，我们刚刚 vfork 结束之后立马只看到了一个 close，但是这个时候因为给了 -f 选项，你能够看到在 vfork 创建出来的子进程没有结束的时候，下面他们在做的是子进程和父进程通过 PID 区分开来。为了区分，它就会把子进程的进程号和父进程的进程号都给你标上。你就能够知道，在这我用 vfork 创建出来一个子进程，并且子进程实际上做的事情最重要的就是这个 execve 的系统调用。

execve 做的事情是要求操作系统执行一个可执行文件，并且以后续的这些选项作为参数。在这一行之前，父进程先创建了一个临时文件 .s，然后 vfork 真正做的是执行 cc1 的程序。cc1 就是一个编译器，所以实际上 GCC 编译这个部分，它执行的是目录下的 cc1 可执行程序。在传入的选项中，你能看到 a.c 源码，还有 -o 选项，传入的就是要求它编译源码产生 .s 文件，这个文件的名称就是刚刚父进程创建出来的空的 .s。所以我们就知道，第一次 vfork 的基础上，调用了一个 cc1 的程序去做编译器。这个环是调用了一个外部的 cc1 编译器去完成编译。

汇编器 (as) 与链接器 (ld) 的调用过程

类似的环我们往下继续去看。编译完了之后，再往下走我们就能够类似地看到汇编也会是基于 vfork 做的。因为每一次在子进程中去调用外部的程序，调用编译器、汇编器、链接器，都是以 execve 为媒介去做的，所以我们可以直接搜索这个。这个时候父进程先生成了一个 .o 的临时文件，然后调用外部的汇编器。

你这个时候能够看到的好像跟刚刚有点不一样，它这里有多个不同的 execve，每一个都调用了一个以 as 结束的汇编器。这件事在做什么？它会有一个 ENOENT（No such file or directory），是不是很像我们之前说要找命令在哪个目录下，报 command not found？它做的事情是在你的环境变量的 PATH 下拼接，在所有的 PATH 中去找到有没有我想要的这个汇编器。如果找不到，就拼下一个 PATH。所以这个是在找一个合法的汇编器。

如果能够成功找到，实际上做的事情就是调用 as 这个汇编器，并且给它传入了一系列的选项，包括一个 -o 的 .o 文件。这个 .o 文件就是父进程事先生成好的空文件，它会在子进程中把目标代码写入这个 .o 文件。这个就是汇编的过程。

结束完了之后，最后父进程会调用 collect2，还会有一个子进程做的事情是 ld 链接器。它调用的方式就跟之前起了一个子进程执行 as 一样，又起了一个子进程执行 ld。这个链接器会基于前面写入的 .o 文件，以及除了 a.o 之外，还会负责链接很多标准库的 .o。我们之前有一堂课给大家演示过，直接用 ld 这个命令去做链接，它不会默认帮你去链接 libc 的代码，所以你是不能够正常运行你的代码的。但是 GCC 可以，就是因为 GCC 在起 ld 这个子进程的时候，它会把你所需要的各种各样的处理代码、库里的 .o 帮你补在这个参数列表里。这就是 ld。

你会看到在 ld 之前好像还是调用了一个 collect2。很多时候课程上会把 collect2 和 ld 一块讲。collect2 更像是在 ld 链接之前，对生成的 .o 文件先做一个事先的符号提取。比如我们之前讲过有 __attribute__((constructor))、__attribute__((destructor)) 这种特别的符号，它就可以在 collect2 的时候提取完，这样最后链接生成的可执行文件在执行的时候，就知道 main 函数运行以外的部分还需要做一些什么样的处理。

GCC 的本质：串联工具链的“胶水”

这个时候我们就很明显地看到，gcc 这个可执行文件，它没有真的做汇编，也没有真的做链接。它做的事情是把这几个环给我串起来。它不是一个链接器，也不是一个汇编器，它做的是把我外部要用的这些工具给我粘起来。所以 GCC 更像是一个胶水（glue），它能够在适当的时候传入适当的选项，调用适当的编译器、汇编器、链接器，把这个链条打通，实现从 a.c 到最终的 a.out。

有了这个过程，当然是可以说服别人，GCC 的编译过程确实是有这么几个不同的步骤，不是一个 button 直接一个程序就运行完了。你能够看到每一个子进程的环就是执行了一个子任务，调用了一个外部的可执行文件。这也解释了为什么 GCC 传入特定选项可以把中间文件保存下来，因为它真的是存在的，无非就是把最终 unlink 的那一条给去掉，保留下来就可以了。

使用 GDB 与 ptrace 观察编译过程

除了这一种方式，strace 本身底层也是基于一个叫 ptrace 的系统调用去执行的。ptrace 是比较强大的一个系统调用，它能够去观察另一个进程的执行，甚至可以观察另一个进程的内存中的某些数据，并且把它改掉。我们的 strace 加上比如 GDB，都是基于 ptrace 去做的。GDB 也可以去观察另一个进程，可以 attach 上去，发指令单步控制它往前走，观察内存中的变量。

所以我们也可以基于 GDB，而不是用 strace 直接去观察。我们可以给 GDB 传入一个脚本，产生预先准备的指令。因为 GDB 可以打断点，我们刚刚发现所有的子进程调用 cc1、as、ld 都是基于 execve 系统调用，所以我们只要在 execve 这个地方打上断点，每次遇到 execve，就应该能明确知道它到底执行的是哪一个外部程序，并且还能知道传入的是哪些参数。

首先最重要的是 set detach-on-fork off，因为 GDB 默认不会沿着 fork 出来的子进程继续追踪，把它 off 关掉，它就会沿着子进程往下看有没有 execve。停在 execve 之前，我想知道括号里的东西到底是什么？只要它是一个函数调用，它就遵循我们函数调用的 convention（调用约定）。想知道传入 execve 的第一个参数是什么，只要去读 rdi 寄存器里面的东西；rsi 寄存器就是传入的各种选项的数组。这是 x86-64 的 convention。所以你直接读这个能够读到，在这个里面遍历数组，就能读到调用了什么外部程序、以什么选项去执行。

GDB 实操：验证文件生成与工具调用

我们就可以真的去跑一下。在 GDB 调试的时候，可以用 -x 把脚本事先给它。你会发现它第一次停在 execve 的时候，是执行了一个 gcc，传入了 a.c。我们 continue 一下，第二次停下来遇到 execve，这个时候执行的是 cc1 程序，并且选项是希望把 a.c 编译生成 .s 文件。这个时候你也可以打印当前被 GDB 追踪的所有进程，你能看到当前 vfork 出来的子进程执行了 execve。

甚至因为我们可以用 GDB 观察内存状态，可以在停下来的时候，用 shell ls -l 看一下这个 .s 文件当前的大小。在没有真正执行 cc1 之前，它的大小是 0；continue 之后，下一次停下来时，编译过程已经结束了，你再看一眼，发现 .s 文件的大小不再是 0，确实被写入了东西。你甚至可以打开这个 .s 文件，看到熟悉的汇编代码。再往下走，你就能看到 as 的 execve，只不过那个时候会停很多次，因为它在找 as 是否存在，不存在就会找下一个路径，所以会有很多个断点被触发。

编译过程追踪总结

这个就是我们第一堂课，希望能让大家把这个链条里所有的系统调用拆出来看一看。今天我们就用了两种方式，一种是 strace，一种是 GDB，其实换汤不换药，都是想要去观察 int 0x80 触发的系统调用，到底是通过什么样的系统调用能让我们去执行完整个编译的大环节。

里面的故事也不复杂，就是 vfork 创建子进程，每个子进程用 execve 执行外部的编译器、汇编器、链接器。如果有人问你 GCC 到底用的是什么汇编器、链接器，你就可以去看那个参数，知道用的是系统哪个目录下的工具，甚至能发现链接了哪些标准库的 .o 文件。

程序的加载与运行机制

在知道这个过程之后，我们就可以来看一下，a.out 是怎么样在我们的系统中运行起来的。如果不考虑动态链接，假设 ld 做静态链接，所有的东西都被塞到 a.out 里了。那这样一个 a.out 应该怎么样去加载运行呢？最简单的，只要从 ELF 文件的 entry 处读到它的 entry point，读到 PC 要指的第一个位置在哪，然后下面就开始 next PC，去执行大循环，一直到程序结束。这个加载执行的整个过程，大家在 PA 里面应该已经反复熟悉过了，因为 PA2 就是让大家去完成取指、译码、执行的这么一个大循环。我们先下课，下一堂课继续看这里面还有些什么样的事情。

PA 实验与“造轮子”：表达式求值与编译器雏形

第二堂课我们来看一看，源码在计算机系统中运行的整个阶段有很多很多的轮子，实际上大家已经在这个过程中有很大一部分的轮子在 PA 中得到锻炼了。虽然大家有时候会觉得 PA 的设计好像跟最终验收通过的那个东西没有什么大相关，但实际上也是在锻炼各个模块，自己完成一部分的需求，也是在反复造轮子的一个过程。

比如 PA1 里面有一个表达式求值，当时应该也挺折磨人的。表达式求值说到底就是要完成的核心功能：读入一个字符串，在上面用正则表达式匹配 token，分析字符串输出计算结果。当时大家算表达式求值，也是会建立类似语法树的东西。如果不是追求把结果算出来，而是把每一个步骤翻译成一些指令输出出来，比如借助栈去做，push a, push b, add, push c, push d, add, mul，这个指令序列就差不多呈现了当时大家算表达式求值的过程。

除了算指令序列，还有算 token，用什么样的正则表达式去匹配它。输入一个字符串，匹配 token，再输出指令序列，这个就是我们正常的一个编译器的流程。当然编译器不只包含这一个部分，还包含词法分析、语法分析、中间代码生成、死代码消除等等。但是表达式求值大概描述了一个简单的编译器的输入输出，所以大家当时做表达式求值也 partially 做了一个很简易的编译器的思路。

编译器的核心组件与优化

只不过想要做一个完整的编译器，困难程度还是比较高的。如果有编译原理的课程，你就会知道编译器要做词法分析。我们当时表达式求值只有那几类 token，所以大家写得很容易。C 语言里的词法分析有很多，到底是一个声明、是一个 identifier 还是什么东西，都是不同的匹配模式。然后就是语法树，比表达式求值的计算树要更复杂一点。然后生成中间代码，就有点像输出指令序列。

现在的编译器已经有很多优化的能力在里面了，即使输出了中间代码，还可以再做一次优化，比如去掉死代码、做公共子表达式消除、代码转换等。我们之前上程序优化也讲过，把不变式从循环中提取出来等，这些都是在编译器的最后部分去做优化，把生成的中间代码变成效率更高的一种中间代码。这个就是编译器，PA1 大家稍微接触到了一点点。

汇编与反汇编：Decode 的逆向思维

再往后看，汇编器 as 的这个部分大家实际上没有做。as 是把中间代码翻译成 0101 或者是 16 进制的表达。大家正向的没有做，但是反向的，能够理解一串 0101 的序列并分析出它对应哪一条指令，大家在 PA2 里的 decode 类似做了一个反向的需求。

PA 的框架是通过 pattern matching（模式匹配）的方式，让大家把那个 0101 串根据 RISC-V 指令集分析出来属于哪一条指令，然后这条指令应该怎么运行。分析出来属于哪一条指令，就是 as 的反向需求。所以这个轮子即使大家不知道，但是你对需求的输入输出还是知道的。如果你想要做一个汇编器，就是把大家的 decode 去做一个逆向。虽然单纯做一个函数的逆非常困难，但是你已经做过 decode 了，想要去开发一个正向的汇编需求应该也不是很困难。

理解 ELF 文件格式

除了指令翻译，还要去生成一个符合 ELF 规范的二进制目标文件。ELF 二进制文件其实挺麻烦的，它有一个 ELF header，里面每一个段是怎么分布的。包括里面会出现动态链接器的字样。虽然这些功能大家没有做，但是这一部分是关心到一个 ELF 文件的格式理解。我知道 ELF 文件每一个段是如何组织的，它在 header 里面的 table 到底是有什么样的 offset。虽然没有让大家生成合法的 ELF 文件，但是 PA 里有一个任务是让大家去分析一个合法的 ELF 文件，输出它的 magic number。所以你大概知道 ELF 文件应该怎么去读取，每一块存了什么内容。

链接器的核心任务：段合并与重定位

链接器最终生成的 ELF 文件，它的来源是多的。要把翻译完的指令在多个 .o 文件中按各个段全部拼起来。即使考虑简单的静态链接，把多个 relocatable（可重定位）文件合并拼起来，也不是那么容易的。首先拼出来的 ELF 文件得满足合法规范。到底每一个段应该如何去拼？

一开始的第一个步骤，需要遵循合并链接的思路，知道最终的 .text 段是由哪些 .text 段拼起来的。这件事实际上写在了 ld 链接的脚本里。ld 真正去把这些 .o 文件链接起来的时候，它执行的这个脚本写的是目标文件中的 .data 段应该有哪些来源，不同的段如何拼起来。ld 链接器就像是这个脚本的解释器加执行器，按照脚本的方式去拼。

第二件事情就是静态链接还有一个重定位（relocation）。待拼的 .o 文件是 relocatable 文件，代表有些指令的东西是不全的，中间挖了一个洞填的是零，该往哪跳转当时是不知道的。拼完之后，需要把各个地方重定位的洞按顺序填上。这就需要解析各个 .o 文件的符号表，知道在哪个地方要填的洞应该是往哪个符号跳转的。把这些洞全部填上，才能得到一个静态链接后合法的 ELF 文件。

虽然没有让大家真的去开发一个链接器，但是做完前三个 PA 之后，你大概知道一个 ELF 文件是怎么组织的。如果让你去执行一个简单的静态链接，只是把几个东西拼起来，我觉得大家还是能够做到的。

加载器与 PA 实验的本质

除了这个之外，就是加载器。加载器这个部分 PA 里面涉及的就更多了。加载器就是把一个 a.out 可执行文件真的跑起来。我们的 PA 不就是在做这件事吗？输入一个二进制文件，模拟计算机系统，找到 PC 指针指向的指令，把指令解析出来，根据指令集的说明操作内存、计算，把计算结果在模拟的系统中 apply 进去。我们模拟了内存、寄存器，甚至是模拟了取指、译码、执行的大循环。这个就是 PA 设计最重要的部分，就是在模拟一个加载器。

所以虽然 PA 整个是在做加载运行，但是在正式加载运行之前的编译、汇编、链接这几个部分，还是有一些小功能被揉到 PA 的设计里的。经过一个学期的学习，你对这里面大概做了一些什么事，是比较清楚的了。

单元测试与自动化生成

除了 PA 最重要的是做了一个加载器，我们里面也用到了各种各样小的轮子。比如单元测试的框架，这是折磨大家在 PA1 最大的一个原因，因为我们没有提供一个单元测试给大家。我们提供了一个怎么造测试用例的 Python 脚本，它可以让大家批量生成表达式。但是怎么生成满足要求的表达式，以及把表达式跟 oracle 组成一个合适的单元测试框架，这件事我们没有完全提供。

当时课上或者 NEMU 的代码里能看到类似单元测试的代码，它实际上就是一个简单的 assertion，能够把测试用例期望的 oracle 输出和程序执行结果比较，并且完全自动化。这就等于是搭出了一个测试框架。当时我们给了一个能批量造表达式的脚本，但我相信大部分同学是自己手动测几个，然后让 OJ 帮他测，把 OJ 当作第三方测试工具。但我们提醒过，OJ 其实没有多少测试用例，整个 PA1 也就十来个。测试用例的设计，质量是比数量更重要的。

这件事未来大家去工业界一定会去做。只不过现在有大语言模型了，未来写测试用例这件事慢慢就不需要大家写了。但是怎么样指导大模型生成单元测试？你有这个思路指导，才能生成好的测试用例。没有思路，大模型生成的未必能测出 bug。所以我们要做的，是知道怎么指导自动化工具更好地生成。

差异测试 (Differential Testing)

到 PA2，我们就真的是把测试框架给了大家。当时 differential testing（差异测试）的框架，我们也花了半堂课给大家看了一下，里面具体是以什么样的代码方式实现了两个状态机按步往前走。当时是用 fork 爆出来一个子进程，让 QEMU 往前走，父进程 NEMU 往前走，并且在 NEMU 进程上通过 GDB 远程控制，使得 QEMU 每次单步往前走，达到交叉测试的目的。这个轮子在各个领域也有成熟的工具了，比如深度学习模型的 differential testing，这些都有成熟工具可以直接用。

调试器的底层实现原理：断点与 int3 指令

不管是单元测试还是 differential testing，主要功能就是希望大家能更好地测试自己的实现，发现 bug。发现 bug 后，我能观测到一个 value，那到底这个 bug 在哪，我应该怎么样修复它？这就跟调试相关。调试器其实我们这学期没有深入涉及过，只是在讲调试理论的时候稍微讲了一下 big picture，概念上怎么融合 printf 分割状态机和 GDB 按步追踪状态机。

但调试器本身是怎么实现的呢？调试器最关键的就是它有一种能力控制程序停在哪。所谓的调试就是让程序停在某一个 PC，那应该是我当前在这个 PC 处打了一个断点。CPU 怎么知道在这个 PC 处应该停下来呢？一种最简单的办法是每次取 next PC 的时候都去匹配一下，但这会极大地拖慢程序执行效率。老的 CPU 上，有专门的一块调试寄存器，可能就 8 个或 16 个，里面存下打的断点 PC。CPU 每次执行时跟这个寄存器做匹配。但限制在于调试寄存器不多，能打的断点数就不多。

那我们现在的 GDB 是如何实现的呢？它没有打多少个断点的限制。其实就是把本来要执行的指令替换成 int3。int3 是一个软中断，跟调试相关。CPU 执行到这儿就会触发中断，跳出去做调试。调试完回来，GDB 再把 int3 删掉，改回原来的代码。只要有方法修改代码，就可以无所谓打多少个断点。

这学期的课就差不多到这，下一堂课就是真正的复习了。不管大家 PA 做得怎么样，能够坚持到现在也是很厉害了。鼓励大家还有一段时间稍微再撑一撑，希望大家能有一个好的成绩。好，下课。