基础设施(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, 就停止客户程序的运行.

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

一键回归测试

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

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

bash runall.sh

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

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

    # 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?