基础设施(2)

测试与调试

理解指令的执行过程之后, 添加各种指令更多的是工程实现. 工程实现难免会碰到bug, 实现不正确的时候如何快速进行调试, 其实也属于基础设施的范畴. 思考一下, 译码查找表中有那么多指令, 每一条指令又通过若干RTL指令实现, 如果其中实现有误, 我们该如何发现呢?

直觉上这貌似不是一件容易的事情, 不过让我们来讨论一下其中的缘由. 假设我们不小心把译码查找表中的某一条指令的译码函数填错了, NEMU执行到这一条指令的时候, 就会使用错误的译码函数进行译码, 从而导致执行函数拿到了错误的源操作数, 或者是将正确的结果写入了错误的目的操作数. 这样, NEMU执行这条指令的结果就违反了它原来的语义, 接下来就会导致跟这条指令有依赖关系的其它指令也无法正确地执行. 最终, 我们就会看到客户程序访问内存越界, 陷入死循环, 或者HIT BAD TRAP, 甚至是NEMU触发了段错误.

调试的工具与原理

我们可以从上面的这个例子中抽象出一些软件工程相关的概念:

  • Fault: 实现错误的代码, 例如填写了错误的译码函数
  • Error: 程序执行时不符合预期的状态, 例如客户程序的指令没有被正确地执行
  • Failure: 能直接观测到的错误, 例如HIT BAD TRAP, 段错误等

调试其实就是从观测到的failure一步一步回溯寻找fault的过程, 找到了fault之后, 我们就很快知道应该如何修改错误的代码了. 但从上面的例子也可以看出, 调试之所以不容易, 恰恰是因为:

  • fault不一定马上触发error
  • 触发了error也不一定马上转变成可观测的failure
  • error会像滚雪球一般越积越多, 当我们观测到failure的时候, 其实已经距离fault非常遥远了

理解了这些原因之后, 我们就可以制定相应的策略了:

  • 尽可能把fault转变成error. 这其实就是测试做的事情, 所以nexus-am/tests/目录下提供了各种各样的测试用例. 但并不是有了测试用例就能把所有fault都转变成error了, 因为这取决于测试的覆盖度. 要设计出一套全覆盖的测试并不是一件简单的事情, 越是复杂的系统, 全覆盖的测试就越难设计. 至少, 框架代码中提供的测试用例的覆盖度还是很有限的. 但是, 如何提高测试的覆盖度, 是学术界一直以来都在关注的问题.
  • 尽早观测到error的存在. 观测到error的时机直接决定了调试的难度: 如果等到触发failure的时候才发现error的存在, 调试就会比较困难; 但如果能在error刚刚触发的时候就观测到它, 调试难度也就大大降低了. 事实上, 你已经见识过一些有用的工具了:
    • -Wall, -Werror: 在编译时刻把潜在的fault直接转变成failure. 这种工具的作用很有限, 只能寻找一些在编译时刻也觉得可疑的fault, 例如if (p = NULL), 但也是代价最低的.
    • assert(): 在运行时刻把error直接转变成failure. assert()是一个很简单却又非常强大的工具, 只要在代码中定义好程序应该满足的特征, 就一定能在运行时刻将不满足这些特征的error拦截下来. 例如链表的实现, 我们只需要在代码中插入一些很简单的assert()(例如指针不为空), 就能够几乎告别段错误. 事实上, 客户程序之所以会HIT BAD TRAP, 其实也是因为违背了我们设置的nemu_assert(). 但是, 编写这些assert()其实需要我们对程序的行为有一定的了解, 同时在程序特征不易表达的时候, assert()的作用也较为有限.
    • printf(): 通过输出的方式观察潜在的error. 这是用于回溯fault时最常用的工具, 用于观测程序中的变量是否进入了错误的状态. 在NEMU中我们提供了输出更多调试信息的宏Log(), 它实际上封装了printf()的功能. 但由于printf()需要根据输出的结果人工判断是否正确, 在便利程度上相对于assert()的自动判断就逊色了不少.
    • GDB: 随时随地观测程序的任何状态. 调试器是最强大的工具, 但你需要在程序行为的茫茫大海中观测那些可疑的状态, 因此使用起来的代价也是最大的.

根据上面的分析, 我们就可以总结出一些调试的建议:

  • 总是使用-Wall-Werror
  • 尽可能多地在代码中插入assert()
  • assert()无法捕捉到error时, 通过printf()输出可疑的变量, 期望能观测到error
  • printf()不易观测error时, 通过GDB理解程序的细致行为

Differential Testing

如果你在程序设计课上听说过上述这些建议, 相信你几乎不会遇到过运行时错误. 然而回过头来看上文提到的指令实现的bug, 我们会发现, 这些工具还是不够用: 我们很难通过assert()来表达指令的正确行为来进行自动检查, 而printf()和GDB实际上并没有缩短error和failure的距离.

如果有一种方法能够表达指令的正确行为, 我们就可以基于这种方法来进行类似assert()的检查了. 那么, 究竟什么地方表达了指令的正确行为呢? 最直接的, 当然就是i386手册了, 但是我们恰恰就是根据i386手册中的指令行为来在NEMU中实现指令的, 同一套方法不能既用于实现也用于检查. 如果有一个i386手册的参考实现就好了. 嘿! 我们用的真机不就是根据i386手册实现出来的吗? 我们让在NEMU中执行的每条指令也在真机中执行一次, 然后对比NEMU和真机的状态, 如果NEMU和真机的状态不一致, 我们就捕捉到error了!

这实际上是一种非常奏效的测试方法, 在软件测试领域称为differential testing. 我们刚才提到了"状态", 那"状态"具体指的是什么呢? 我们在PA1中已经认识到, 计算机就是一个数字电路. 那么, "计算机的状态"就恰恰是那些时序逻辑部件的状态, 也就是寄存器和内存的值. 其实仔细思考一下, 计算机执行指令, 就是修改这些时序逻辑部件的状态的过程. 要检查指令的实现是否正确, 只要检查这些时序逻辑部件中的值是否一致就可以了! Differential testing可以非常及时地捕捉到error, 第一次发现NEMU的寄存器或内存的值与真机不一样的时候, 就是因为当时执行的指令实现有误导致的. 这时候其实离error非常接近, 防止了error进一步传播的同时, 要回溯找到fault也容易得多.

多么美妙的功能啊! 背后还蕴含着计算机本质的深刻原理! 但很遗憾, 不要忘记了, 真机上是运行了操作系统GNU/Linux的, 而NEMU中的测试程序是运行在AM上的. 就如前文所说, 它们提供的运行时环境是不一样的, 我们无法在GNU/Linux中运行基于x86-nemu的AM程序. 所以, 我们需要的不仅是一个i386手册的正确实现, 而且需要在上面能正确运行基于x86-nemu的AM程序.

事实上, QEMU就是一个不错的参考实现. 它是一个虚拟出来的完整的x86计算机系统, 而NEMU的目标只是虚拟出x86的一个子集, 能在NEMU上运行的程序, 自然也能在QEMU上运行. 因此, 为了通过differential testing的方法测试NEMU实现的正确性, 我们让NEMU和QEMU逐条指令地执行同一个客户程序. 双方每执行完一条指令, 就检查各自的寄存器和内存的状态, 如果发现状态不一致, 就马上报告错误, 停止客户程序的执行.

NEMU的框架代码已经准备好相应的功能了, 在nemu/include/common.h中定义宏DIFF_TEST之后, 重新编译NEMU后运行, 你会发现NEMU多输出了Connect to QEMU successfully的信息. 定义了宏DIFF_TEST之后, monitor会多进行以下初始化工作, 你不需要了解这些工作的具体细节, 只需要知道这是在为了让QEMU进入一个和NEMU同等的状态就可以了.

  • 调用init_difftest()函数(在nemu/src/monitor/diff-test/diff-test.c中定义)来启动QEMU. 需要注意的是, 框架代码让QEMU运行在后台, 因此你将看不到QEMU的任何输出.
  • load_img()的最后将客户程序拷贝一份副本到QEMU模拟的内存中.
  • restart()中调用init_qemu_reg()函数(在nemu/src/monitor/diff-test/diff-test.c中定义), 来把QEMU的通用寄存器设置成和NEMU一样.

进行了上述初始化工作之后, QEMU和NEMU就处于相同的状态了. 接下来就要进行逐条指令执行后的状态对比了, 实现这一功能的是difftest_step()函数(在nemu/src/monitor/diff-test/diff-test.c中定义). 它会在exec_wrapper()的最后被调用, 在NEMU中执行完一条指令后, 就在difftest_step()中让QEMU执行相同的指令, 然后读出QEMU中的寄存器. 你需要添加相应的代码, 把NEMU的8个通用寄存器和eip与从QEMU中读出的寄存器的值进行比较, 如果发现值不一样, 就输出相应的提示信息, 并将diff标志设置为true. 在difftest_step()的最后, 如果检测到diff标志为true, 就停止客户程序的运行.

实现differential testing

difftest_step()中添加相应的代码, 实现differential testing的核心功能. 实现正确后, 你将会得到一款无比强大的测试工具.

体会到differential testing的强大之后, 不妨思考一下: 作为一种基础设施, differential testing能帮助你节省多少调试的时间呢?

咦? 我们不需要对内存的状态进行比较吗? 事实上, NEMU是通过一套GDB协议与QEMU通信来获取QEMU的状态的, 但是通过这一协议还是不好获取指令修改的内存位置, 而对比整个内存又会带来很大的开销, 所以我们就不对内存的状态进行比较了. 事实上, NEMU中的简化实现也会导致某些寄存器的状态与QEMU的结果不一致, 例如EFLAGS, NEMU只实现了EFLAGS中的少量标志位, 同时也简化了某些指令对EFLAGS的更新. 另外, 一些特殊的系统寄存器也没有完整实现. 因此, 我们实现的differential testing并不是完整地对比QEMU和NEMU的状态, 但是不管是内存还是标志位, 只要客户程序的一条指令修改了它们, 在不久的将来肯定也会再次用到它们, 到时候一样能检测出状态的不同. 同时框架中也准备了is_skip_nemuis_skip_qemu这两个变量, 用于跳过少量不易进行对比的指令. 因此, 我们其实牺牲了一些比较的精度, 来换取性能的提升, 但即使这样, 由于differential testing需要与QEMU进行通信, 这还是会把NEMU的运行速度拉低上百倍. 因此除非是在进行调试, 否则不建议打开differential testing的功能来运行NEMU.

一键回归测试

在实现指令的过程中, 你需要逐个测试用例地运行. 但在指令实现正确之后, 是不是意味着可以和这些测试用例说再见呢? 显然不是. 以后你还需要在NEMU中加入新的功能, 为了保证加入的新功能没有影响到已有功能的实现, 你还需要重新运行这些测试用例. 在软件测试中, 这个过程称为回归测试.

既然将来还要重复运行这些测试用例, 而手动重新运行每一个测试显然是一种效率低下的做法. 为了提高效率, 我们提供了一个用于一键回归测试的脚本. 在nemu/目录下运行

bash runall.sh

来自动批量运行nexus-am/tests/cputest/中的所有测试, 并报告每个测试用例的运行结果. 如果一个测试用例运行失败, 脚本将会保留相应的日志文件; 当使用脚本通过这个测试用例的时候, 日志文件将会被移除.

NEMU的本质

你已经知道, NEMU是一个用来执行其它程序的程序. 在可计算理论中, 这种程序有一个专门的名词, 叫通用程序(Universal Program), 它的通俗含义是: 其它程序能做的事情, 它也能做. 通用程序的存在性有专门的证明, 我们在这里不做深究, 但是, 我们可以写出NEMU, 可以用Docker/虚拟机做实验, 乃至我们可以在计算机上做各种各样的事情, 其背后都蕴含着通用程序的思想: NEMU和各种模拟器只不过是通用程序的实例化, 我们也可以毫不夸张地说, 计算机就是一个通用程序的实体化. 通用程序的存在性为计算机的出现奠定了理论基础, 是可计算理论中一个极其重要的结论, 如果通用程序的存在性得不到证明, 我们就没办法放心地使用计算机, 同时也不能义正辞严地说"机器永远是对的".

我们编写的NEMU最终会被编译成x86机器代码, 用x86指令来模拟x86程序的执行. 事实上在30多年前(1983年), Martin Davis教授 就在他出版的"Computability, complexity, and languages: fundamentals of theoretical computer science"一书中 提出了一种仅有三种指令的程序设计语言L语言, 并且证明了L语言和其它所有编程语言的计算能力等价. L语言中的三种指令分别是:

V = V + 1
V = V - 1
IF V != 0 GOTO LABEL

用x86指令来描述, 就是inc, decjne三条指令. 假设除了输入变量之外, 其它变量的初值都是0, 并且假设程序执行到最后一条指令就结束, 你可以仅用这三种指令写一个计算两个正整数相加的程序吗?

    # Assume a = 0, x and y are initialized with some positive integers.
    # Other temporary variables are initialized with 0.
    # Let "jne" carries a variable: jne v, label.
    # It means "jump to label if v != 0".
    # Compute a = x + y used only these three instructions: inc, dec, jnz.
    # No other instructions can be used.
    # The result should be stored in variable "a".
    # Have a try?

令人更惊讶的是, Martin Davis教授还证明了, 在不考虑物理限制的情况下(认为内存容量无限多, 每一个内存单元都可以存放任意大的数), 用L语言也可以编写出一个和NEMU类似的通用程序! 而且这个用L语言编写的通用程序的框架, 竟然还和NEMU中的cpu_exec()函数如出一辙: 取指, 译码, 执行... 这其实并不是巧合, 而是模拟(Simulation)在计算机科学中的应用.

早在Martin Davis教授提出L语言之前, 科学家们就已经在探索什么问题是可以计算的了. 回溯到19世纪30年代, 为了试图回答这个问题, 不同的科学家提出并研究了不同的计算模型, 包括Gödel, HerbrandKleen研究的递归函数, Church提出的λ-演算, Turing提出的图灵机, 后来发现这些模型在计算能力上都是等价的; 到了40年代, 计算机就被制造出来了. 后来甚至还有人证明了, 如果使用无穷多个算盘拼接起来进行计算, 其计算能力和图灵机等价! 我们可以从中得出一个推论, 通用程序在不同的计算模型中有不同的表现形式. NEMU作为一个通用程序, 在19世纪30年代有着非凡的意义. 如果你能在80年前设计出NEMU, 说不定"图灵奖"就要用你的名字来命名了. 计算的极限这一篇科普文章叙述了可计算理论的发展过程, 我们强烈建议你阅读它, 体会人类的文明(当然一些数学功底还是需要的). 如果你对可计算理论感兴趣, 可以选修宋方敏老师的计算理论导引课程.

把思绪回归到PA中, 通用程序的性质告诉我们, NEMU的潜力是无穷的. 为了创造出一个缤纷多彩的世界, 你觉得NEMU还缺少些什么呢?

捕捉死循环(有点难度)

NEMU除了作为模拟器之外, 还具有简单的调试功能, 可以设置断点, 查看程序状态. 如果让你为NEMU添加如下功能

当用户程序陷入死循环时, 让用户程序暂停下来, 并输出相应的提示信息

你觉得应该如何实现? 如果你感到疑惑, 在互联网上搜索相关信息.

温馨提示

PA2阶段2到此结束. 此阶段需要实现较多指令, 你有两周的时间来完成所有内容.

results matching ""

    No results matching ""