基础设施(2)

AM作为基础设施

编写klib, 然后在NEMU上运行string程序, 看其是否能通过测试. 表面上看, 这个做法似乎没什么不妥当, 然而如果测试不通过, 你在调试的时候肯定会思考: 究竟是klib写得不对, 还是NEMU有bug呢? 如果这个问题得不到解决, 调试的难度就会上升: 很有可能在NEMU中调了一周, 最后发现是klib的实现有bug.

之所以会有这个问题, 是因为软件(klib)和硬件(NEMU)都是你编写的, 它们的正确性都是不能100%保证的. 大家在中学的时候都学习过控制变量法: 如果能把其中一方换成是认为正确的实现, 就可以单独测试另一方的正确性了! 比如我们在真机上对klib进行测试, 如果测试没通过, 那就说明是klib的问题, 因为我们可以相信真机的硬件实现永远是对的; 相反, 如果测试通过了, 那就说明klib没有问题, 而是NEMU有bug.

一个新的问题是, 我们真的可以很容易地把软件移植到其它硬件上进行测试吗? 聪明的你应该想起来AM的核心思想了: 通过一组抽象的API把程序和架构解耦. AM的思想保证了运行在AM之上的代码(包括klib)都是架构无关的, 这恰恰增加了代码的可移植性. 想象一下, 如果string.c的代码中有一条只能在NEMU中执行的nemu_trap指令, 那么它就无法在真机上运行.

abstract-machine中有一个特殊的架构叫native, 是用GNU/Linux默认的运行时环境来实现的AM API. 例如我们通过gcc hello.c编译程序时, 就会编译到GNU/Linux提供的运行时环境; 你在PA1试玩的超级玛丽, 也是编译到native上并运行. 和$ISA-nemu相比, native有如下好处:

• 直接运行在真机上, 可以相信真机的行为永远是对的
• 就算软件有bug, 在native上调试也比较方便(例如可以使用GDB, 比NEMU的monitor方便很多)

因此, 与其在$ISA-nemu中直接调试软件, 还不如在native上把软件调对, 然后再换到$ISA-nemu中运行, 来对NEMU进行测试. 在abstract-machine中, 我们可以很容易地把程序编译到另一个架构上运行, 例如在am-kernels/tests/cpu-tests/目录下执行

make ALL=string ARCH=native run

即可将string程序编译到native并运行. 由于我们会将程序编译到不同的架构中, 因此你需要注意make命令中的ARCH参数.

与NEMU中运行程序不同, 由于cpu-tests中的测试不会进行任何输出, 我们只能通过程序运行的返回值来判断测试是否成功. 如果string程序通过测试, 终端将不会输出任何信息; 如果测试不通过, 终端将会输出

make[1]: *** [run] Error 1

当然也有可能输出段错误等信息.

别高兴太早了, 框架代码编译到native的时候默认链接到glibc, 我们需要把这些库函数的调用链接到我们编写的klib来进行测试. 我们可以通过在abstract-machine/klib/include/klib.h 中通过定义宏__NATIVE_USE_KLIB__来把库函数链接到klib. 如果不定义这个宏, 库函数将会链接到glibc, 可以作为正确的参考实现来进行对比.

好了, 现在你就可以在native上测试/调试你的klib实现了, 还可以使用putch()进行字符输出来帮助你调试, 甚至是GDB. 实现正确后, 再将程序编译到$ISA-nemu(记得移除调试时插入的putch()), 对NEMU进行测试.

测试你的klib

string程序只是简单地调用一下klib中的函数, 它本身只是作为一个客户程序来测试NEMU的实现, 但它并不能对klib的实现进行充分的测试. 为此, 你需要编写一些充分的测试用例来专门对klib的实现进行测试. 测试用例主要包含测试输入和测试输出, 如果我们希望可以高效地构造测试用例, 我们就需要寻找一种独立于测试对象的方法来得到测试输出.

 +----> 测试对象 ----> 实际输出
 |                        |
输入                      +----> 一致?
 |                        |
 +----> 某种方法 ----> 预期输出

在klib中, 需要大家实现的函数主要分成三类.

1. 内存和字符串的写入函数, 例如memset(), strcpy()等.
2. 内存和字符串的只读函数, 例如memcmp(), strlen()等.
3. 格式化输出函数, 例如sprintf()等.

针对第一类函数, 我们应该如何构造一个测试场景, 使得存在一些方法来容易地得到测试输出呢? 注意这些函数都是对一个内存区域进行写入, 考虑如下的数组:

#define N 32
uint8_t data[N];

void reset() {
  int i;
  for (i = 0; i < N; i ++) {
    data[i] = i + 1;
  }
}

这样的一个数组, 每个元素都是1个字节, 而且它们的值都各不相同. 如果我们在这个数组上进行测试, 只要实际输出有1个字节不正确, 都可以大概率被检查出来. 为了得到预期的输出, 我们还要思考测试函数的预期行为: 以上函数都是对数组中的一段连续区间进行写入, 于是我们可以把预期的输出分成三段来检查:

• 第一段是函数写入区间的左侧, 这一段区间没有被写入, 因此应该有assert(data[i] == i + 1)
• 第二段是函数写入的区间本身, 这一段区间的预期结果和函数的具体行为有关
• 第三段是函数写入区间的右侧, 这一段区间没有被写入, 因此应该有assert(data[i] == i + 1)

于是我们可以编写两个辅助函数用于检查:

// 检查[l,r)区间中的值是否依次为val, val + 1, val + 2...
void check_seq(int l, int r, int val) {
  int i;
  for (i = l; i < r; i ++) {
    assert(data[i] == val + i - l);
  }
}

// 检查[l,r)区间中的值是否均为val
void check_eq(int l, int r, int val) {
  int i;
  for (i = l; i < r; i ++) {
    assert(data[i] == val);
  }
}

有了这两个函数, 我们就可以遍历各种输入, 并且很容易地编写出测试函数的预期输出了. 例如针对memset(), 我们可以编写如下的测试代码:

void test_memset() {
  int l, r;
  for (l = 0; l < N; l ++) {
    for (r = l + 1; r <= N; r ++) {
      reset();
      uint8_t val = (l + r) / 2;
      memset(data + l, val, r - l);
      check_seq(0, l, 1);
      check_eq(l, r, val);
      check_seq(r, N, r + 1);
    }
  }
}

最后我们来看格式化输出函数. 以%d为例, 我们需要构造一些输入. 但整数的范围太大了, 不能全部遍历它们, 因此我们需要挑选一些有代表性的整数. limits.h这个C标准头文件里面包含了一些最大数和最小数的定义, 你可以打开/usr/include/limits.h来阅读它们. 一些有代表性的整数可以是:

int data[] = {0, INT_MAX / 17, INT_MAX, INT_MIN, INT_MIN + 1,
              UINT_MAX / 17, INT_MAX / 17, UINT_MAX};

为了得到相应的预期输出, 我们可以先编写一个native程序来用printf输出它们, 然后把输出结果整理到测试代码里面. cpu-tests中的预期输出也是这样生成的.

Differential Testing

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

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

我们已经在PA1中讨论过调试的方法, 然而对于指令实现的bug, 我们会发现, 这些调试的方法还是不太奏效: 我们很难通过assert()来表达指令的正确行为, 从而进行自动检查, 而printf()和GDB实际上并没有缩短error和failure的距离.

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

这实际上是一种非常奏效的测试方法, 在软件测试领域称为differential testing(后续简称DiffTest). 通常来说, 进行DiffTest需要提供一个和DUT(Design Under Test, 测试对象) 功能相同但实现方式不同的REF(Reference, 参考实现), 然后让它们接受相同的有定义的输入, 观测它们的行为是否相同.

我们刚才提到了"状态", 那"状态"具体指的是什么呢? 我们在PA1中已经认识到, 程序和计算机都可以看成是一个状态机, 状态可以表示成一个二元组S = <R, M>, 其中R是寄存器的值, M是内存的值. 要检查指令的实现是否正确, 只要检查执行指令之后DUT和REF的状态是否一致就可以了! DiffTest可以非常及时地捕捉到error, 第一次发现NEMU的状态与真机不一样的时候, 就是因为当前执行的指令实现有误导致的. 这时候其实离error非常接近, 防止了error进一步传播的同时, 要回溯找到fault也容易得多.

多么美妙的功能啊! 背后还蕴含着计算机本质的深刻原理! 但很遗憾, 不要忘记了, 真机上是运行了操作系统GNU/Linux的, 我们无法在native中运行编译到x86-nemu的AM程序, 对于mips32和riscv32的程序, 真机更是无法直接运行. 所以, 我们需要的不仅是一个ISA手册的正确实现, 而且需要在上面能正确运行$ISA-nemu的AM程序.

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

一周正确实现一个全乱序执行处理器, 并在上面运行操作系统Nanos和仙剑奇侠传

为了方便实现DiffTest, 我们在DUT和REF之间定义了如下的一组API:

// 从DUT host memory的`src`处拷贝`n`字节到REF guest memory的`dest`处
void difftest_memcpy_from_dut(paddr_t dest, void *src, size_t n);
// 获取REF的寄存器状态到`r`
void difftest_getregs(void *r);
// 设置REF的寄存器状态为`r`
void difftest_setregs(const void *r);
// 让REF执行`n`条指令
void difftest_exec(uint64_t n);
// 初始化REF的DiffTest功能
void difftest_init();

其中寄存器状态r要求寄存器的成员按照某种顺序排列, 若未按要求顺序排列, difftest_getregs()和difftest_setregs()的行为是未定义的(这样就把锅甩给你们了^_^). REF需要实现这些API, DUT会使用这些API来进行DiffTest. 在这里, REF和DUT分别是QEMU和NEMU.

NEMU的框架代码已经准备好相应的功能了. 在nemu/include/common.h中定义宏DIFF_TEST, 然后重新编译NEMU并运行即可. nemu/Makefile中已经设置了相应的规则和参数, 会自动进入nemu/tools/qemu-diff目录并编译$ISA-qemu-so, 并把其作为NEMU的一个参数传入. 定义了宏DIFF_TEST之后, nemu/src/monitor/difftest/dut.c中的 init_difftest()会额外进行以下初始化工作:

• 打开动态库文件ref_so_file, 也就是$ISA-qemu-so.
• 从动态库中分别读取上述API的符号.
• 对REF的DIffTest功能进行初始化, 此时会启动QEMU, 并输出Connect to QEMU successfully的信息. 代码还会对QEMU的状态进行一些初始化工作, 但你不需要了解这些工作的具体细节. 需要注意的是, 我们让QEMU运行在后台, 因此你将看不到QEMU的任何输出.
• 将DUT的guest memory拷贝到REF中.
• 将DUT的寄存器状态拷贝到REF中.

进行了上述初始化工作之后, QEMU和NEMU就处于相同的状态了. 接下来就可以进行逐条指令执行后的状态对比了, 实现这一功能的是difftest_step()函数(在nemu/src/monitor/difftest/dut.c中定义). 它会在cpu_exec()的主循环中被调用, 在NEMU中执行完一条指令后, 就在difftest_step()中让QEMU执行相同的指令, 然后读出QEMU中的寄存器, 并进行对比. 由于不同ISA的寄存器有所不同, 框架代码把寄存器对比抽象成一个ISA相关的API, 即isa_difftest_checkregs()函数(在nemu/src/isa/$ISA/difftest/dut.c中定义). 你需要实现isa_difftest_checkregs()函数, 把通用寄存器和PC与从QEMU中读出的寄存器的值进行比较. 若对比结果一致, 函数返回true; 如果发现值不一样, 函数返回false, 框架代码会自动停止客户程序的运行.

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

NEMU的简化会导致某些指令的行为与QEMU有所差异, 因而无法进行对比. 为了解决这个问题, 框架中准备了difftest_skip_ref()和difftest_skip_dut()这两个函数:

• 有的指令不能让QEMU直接执行, 或者执行后的行为肯定与NEMU不同, 例如nemu_trap指令, 在QEMU中, 它是一条非法指令. 此时可以通过difftest_skip_ref()进行校准, 执行它后, 在difftest_step()中会让QEMU跳过当前指令的执行, 同时把NEMU的当前的寄存器状态直接同步到QEMU中, 效果相当于"该指令的执行结果以NEMU的状态为准".
• 由于实现的特殊性, QEMU在少数时候会把几条指令打包一起执行. 这时候, 我们调用一次difftest_step(), QEMU就会执行多条指令. 但由于NEMU的isa_exec_once()是一次执行一条指令, 这样就会引入偏差. 一个例子是riscv32的jalr, 在riscv32-QEMU中, 由于某种未知的原因, 若当前pc指向的是一条jalr指令, 此时单步执行一次, 除了会执行jalr指令本身之外, 还会额外执行位于jalr目标地址的指令. 此时可以通过difftest_skip_dut(int nr_ref, int nr_dut)来进行校准, 执行它后, 会马上让QEMU单步执行nr_ref次, 然后期望NEMU可以在nr_dut条指令之内追上QEMU的状态, 期间会跳过其中所有指令的检查.

一键回归测试

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

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

bash runall.sh ISA=$ISA

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

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