基础设施(2)

bug诊断的利器 - 踪迹

我们已经知道程序是个状态机, 如果程序变得复杂, 这个状态机的转移情况也会变得复杂. 先不说状态机中每个状态的细节, 就连状态机进行了怎么样的转移, 我们也很难完全搞清楚.

如果通过GDB来了解这一过程, 效率就会显得有点低了. 为了提高效率, 我们可以通过printf()来输出我们关心的某些信息. 我们关心程序这个状态机转移的细节, 也说明我们关心的是程序的执行过程. 在软件工程领域, 记录程序执行过程的信息称为踪迹(trace). 有了踪迹信息, 我们就可以判断程序的执行过程是否符合预期, 从而进行bug的诊断.

apt-get install llvm-11
git clone -b ics2021 https://github.com/NJU-ProjectN/nemu.git /tmp/nemu
cd /tmp/nemu
git format-patch 09704e..58f009
cd $NEMU_HOME
# 下面的命令只能执行一次, 多次执行会导致代码混乱;
# 若不小心执行了多次, 可以通过git恢复代码, 然后重新执行
patch -p1 < /tmp/nemu/0001-use-llvm-disassembler.patch

1 out of 1 hunk FAILED -- saving rejects to file src/cpu/cpu-exec.c.rej

make menuconfig # 无需更改任何选项, 退出并保存
make run # 运行内建客户程序, 若运行后看到build/nemu-log.txt中输出了指令的反汇编,
         # 说明打补丁成功; 若发生编译错误, 请手动修复后再继续
find . -name "*.rej" -or -name "*.orig" | xargs rm
git add $NEMU_HOME
git commit -m "use llvm disassembler"
rm -rf /tmp/nemu

指令执行的踪迹 - itrace

NEMU已经实现了一个简单的踪迹功能 -- itrace (instruction trace), 它可以记录客户程序执行的每一条指令. itrace的实现很简单, 代码只要记录instr_fetch()取到的每一条指令, 然后调用llvm项目提供的反汇编功能(在nemu/src/utils/disasm.cc中实现). itrace会输出指令的PC, 二进制表示以及反汇编结果. 框架代码默认已经打开了这个功能, 客户程序执行的指令都会被记录到build/nemu-log.txt中. 查看这个文件, 你就可以知道客户程序是如何运行的了.

NEMU可以限制trace输出的时机, 你可以手动指定什么时候才输出它们, 甚至还可以自定义输出trace的条件. 具体如何指定, RTFSC. 由于目前程序的行为都是确定的, 多次运行会得到相同的结果, 这对我们了解程序什么时候出错是很有帮助的.

对于一些输出规整的trace, 我们还可以通过grep, awk, sed等文本处理工具来对它们进行筛选和处理. 因此如果你掌握一些用于文本处理的shell命令, 你就可以进一步提高调试的效率了.

指令环形缓冲区 - iringbuf

一般来说, 我们只会关心出错现场前的trace, 在运行一些大程序的时候, 运行前期的trace大多时候没有查看甚至输出的必要. 一个很自然的想法就是, 我们能不能在客户程序出错(例如访问物理内存越界)的时候输出最近执行的若干条指令呢?

要实现这个功能其实并不困难, 我们只需要维护一个很简单的数据结构 - 环形缓冲区(ring buffer)即可. 具体地, 在每执行一条指令的时候, 就把这条指令的信息写入到环形缓冲区中; 如果缓冲区满了, 就会覆盖旧的内容. 客户程序出错的时候, 就把环形缓冲区中的指令打印出来, 供调试进行参考. 一个输出的示例如下, 其中-->指示了出错的指令:

      0x80002b00: srli  a2, a2, 1                13 56 16 00
      0x80002b04: slli  a1, a1, 1                93 95 15 00
      0x80002b08: or    a0, s1, a5               33 e5 f4 00
      0x80002b0c: sub   s0, s0, a5               33 04 f4 40
      0x80002b10: jal   -112                     ef f0 1f f9
      0x80002aa0: lui   a5, 524295               b7 77 00 80
      0x80002aa4: lw    a5, 2028(a5)             83 a7 c7 7e
      0x80002aa8: addi  sp, sp, -32              13 01 01 fe
  --> 0x80002aac: sw    s2, 16(sp)               23 28 21 01
      0x80002b3c: ret                            67 80 00 00
      0x80002b14: add   s2, s2, a0               33 09 a9 00
      0x80002b18: bnez  s0, -40                  e3 1c 04 fc
      0x80002af0: neg   a5, s0                   b3 07 80 40
      0x80002af4: and   a5, a5, s0               b3 f7 87 00
      0x80002af8: or    a2, s3, a5               33 e6 f9 00
      0x80002afc: or    a1, s4, a5               b3 65 fa 00

内存访问的踪迹 - mtrace

访问内存占程序执行很大的一部分, 如果你遇到过一些和访存相关的错误(例如物理内存越界), 你一定想知道程序访存的具体行为, 然后从其中找出不正确的访存, 从而帮助你进行bug的诊断. 事实上, 我们可以很容易地对访存的结果进行追踪, 从而记录访存的踪迹(memory trace).

函数调用的踪迹 - ftrace

itrace和mtrace都是从底层状态机视角来追踪程序的运行, 但如果我们想了解程序的语义行为, itrace和mtrace就无法帮助我们了, 因此我们需要一个带有程序语义行为trace工具.

问题是, 我们应该选择怎么样的语义呢? 在程序设计课上, 我们知道一个程序由若干函数构成, 而一个函数则是由若干语句构成, 一条语句又会被编译成若干指令, 因此, 可以清晰地携带程序语义的就只有函数了. 想象一下, 如果我们能设计一个工具ftrace, 用来追踪程序执行过程中的函数调用和返回, 我们不就可以知道程序大概是如何工作的了吗?

这其实并不困难, 因为itrace已经能够追踪程序执行的所有指令了, 要实现ftrace, 我们只需要关心函数调用和返回相关的指令就可以了. 我们可以在函数调用指令中记录目标地址, 表示将要调用某个函数; 然后在函数返回指令中记录当前PC, 表示将要从PC所在的函数返回. 我们很容易在相关指令的执行辅助函数中添加代码来实现这些功能. 但目标地址和PC值仍然缺少程序语义, 如果我们能把它们翻译成函数名, 就更容易理解了!

给定一个位于代码段的地址, 如何得知它位于哪一个函数呢? 这就需要ELF文件中符号表(symbol table)的帮助了. 符号表是可执行文件的一个section, 它记录了程序编译时刻的一些信息, 其中就包括变量和函数的信息. 为了实现ftrace, 我们首先需要了解符号表中都记录了哪些信息.

以cpu-tests中add这个用户程序为例, 使用readelf命令查看ELF可执行文件的信息:

riscv64-linux-gnu-readelf -a add-riscv32-nemu.elf

你会看到readelf命令输出了很多信息, 这些信息对了解ELF的结构有很好的帮助, 我们建议你在课后仔细阅读. 目前我们只需要关心符号表的信息就可以了, 在输出中找到符号表的信息:

Symbol table '.symtab' contains 28 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 80000000     0 SECTION LOCAL  DEFAULT    1
     2: 80000108     0 SECTION LOCAL  DEFAULT    2
     3: 8000010c     0 SECTION LOCAL  DEFAULT    3
     4: 8000020c     0 SECTION LOCAL  DEFAULT    4
     5: 00000000     0 SECTION LOCAL  DEFAULT    5
     6: 00000000     0 FILE    LOCAL  DEFAULT  ABS add.c
     7: 00000000     0 FILE    LOCAL  DEFAULT  ABS trm.c
     8: 80000108     1 OBJECT  LOCAL  DEFAULT    2 mainargs
     9: 800000e8    32 FUNC    GLOBAL DEFAULT    1 _trm_init
    10: 80009000     0 NOTYPE  GLOBAL DEFAULT    4 _stack_pointer
    11: 80000108     0 NOTYPE  GLOBAL DEFAULT    1 _etext
    12: 80000000     0 NOTYPE  GLOBAL DEFAULT  ABS _pmem_start
    13: 8000022c     0 NOTYPE  GLOBAL DEFAULT    4 _bss_start
    14: 80000109     0 NOTYPE  GLOBAL DEFAULT    2 edata
    15: 80009000     0 NOTYPE  GLOBAL DEFAULT    4 _heap_start
    16: 80001000     0 NOTYPE  GLOBAL DEFAULT    4 _stack_top
    17: 80009000     0 NOTYPE  GLOBAL DEFAULT    4 end
    18: 80000010    24 FUNC    GLOBAL DEFAULT    1 check
    19: 80000108     0 NOTYPE  GLOBAL DEFAULT    1 etext
    20: 80000000     0 FUNC    GLOBAL DEFAULT    1 _start
    21: 00000000     0 NOTYPE  GLOBAL DEFAULT  ABS _entry_offset
    22: 80000028   180 FUNC    GLOBAL DEFAULT    1 main
    23: 80000109     0 NOTYPE  GLOBAL DEFAULT    2 _data
    24: 8000010c   256 OBJECT  GLOBAL DEFAULT    3 ans
    25: 80009000     0 NOTYPE  GLOBAL DEFAULT    4 _end
    26: 800000dc    12 FUNC    GLOBAL DEFAULT    1 halt
    27: 8000020c    32 OBJECT  GLOBAL DEFAULT    4 test_data

其中每一行代表一个表项, 每一列列出了表项的一些属性, 现在我们只需要关心Type属性为FUNC的表项就可以了. 仔细观察Name属性之后, 你会发现这些表项正好对应了程序中定义的函数, 相应的Value属性正好是它们的起始地址(你可以与反汇编结果进行对比), 而相应的Size属性则给出了函数的大小.

噢, 通过符号表, 我们可以建立函数名与其地址之间的映射关系! 但readelf输出的信息是已经经过解析的, 实际上符号表中Name 属性存放的是字符串在字符串表(string table)中的偏移量. 为了查看字符串表, 我们先查看readelf输出中Section Headers的信息:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        80000000 001000 000108 00  AX  0   0  4
  [ 2] .sdata2.mainargs  PROGBITS        80000108 001108 000001 00   A  0   0  4
  [ 3] .data.ans         PROGBITS        8000010c 00110c 000100 00  WA  0   0  4
  [ 4] .data.test_data   PROGBITS        8000020c 00120c 000020 00  WA  0   0  4
  [ 5] .comment          PROGBITS        00000000 00122c 00001c 01  MS  0   0  1
  [ 6] .symtab           SYMTAB          00000000 001248 0001c0 10      7   9  4
  [ 7] .strtab           STRTAB          00000000 001408 00009b 00      0   0  1
  [ 8] .shstrtab         STRTAB          00000000 0014a3 000055 00      0   0  1

从Section Headers的信息可以看到, 字符串表在ELF文件偏移为0x1408的位置开始存放. 我们可以通过以下命令直接输出ELF文件的十六进制形式:

hd add-riscv32-nemu.elf

查看这一命令输出结果中0x1408附近的部分, 我们可以看到, 字符串表只不过是把标识符的字符串拼接起来而已. 现在我们就可以厘清符号表和字符串表之间的关系了:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 7] .strtab           STRTAB          00000000 001408 00009b 00      0   0  1
                                                  |
                                   +--------------+
                        ++         V
00001400                |V         00 61 64 64 2e 63 00 74  | ........add.c.t|
00001410  72 6d 2e 63 00|6d 61 69  6e 61 72 67 73 00 5f 74  |rm.c.mainargs._t|
00001420  72 6d 5f 69 6e|69 74 00                    ^      |rm_init._stack_p|
                        |                            |
                        |                            +----------------+
                        |                                             |
                        +-----------------------------------------+   |
Symbol table '.symtab' contains 10 entries:                       |   |
   Num:    Value  Size Type    Bind   Vis      Ndx Name           |   |
     7: 00000000     0 FILE    LOCAL  DEFAULT  ABS 7 (trm.c)      |   |
     8: 80000108     1 OBJECT  LOCAL  DEFAULT    2 13(mainargs) --+   |
     9: 800000e8    32 FUNC    GLOBAL DEFAULT    1 22(_trm_init) -----+

现在我们就可以把一个给定的地址翻译成函数名了: 由于函数的范围是互不相交的, 我们可以逐项扫描符号表中Type属性为FUNC的每一个表项, 检查给出的地址是否落在区间[Value, Value + Size)内, 若是, 则根据表项中的Name属性在字符串表中找到相应的字符串, 作为函数名返回. 如果没有找到符合要求的符号表表项, 可以返回字符串"???", 不过这很可能是你的实现错误导致的, 你需要再次检查你的实现.

以运行cpu-tests中的recursion为例, ftrace的部分示例输出如下(你可以结合反汇编结果进行理解):

0x8000000c: call [_trm_init@0x80000260]
0x80000270:   call [main@0x800001d4]
0x800001f8:     call [f0@0x80000010]
0x8000016c:       call [f2@0x800000a4]
0x800000e8:         call [f1@0x8000005c]
0x8000016c:           call [f2@0x800000a4]
0x800000e8:             call [f1@0x8000005c]
0x8000016c:               call [f2@0x800000a4]
0x800000e8:                 call [f1@0x8000005c]
0x8000016c:                   call [f2@0x800000a4]
0x800000e8:                     call [f1@0x8000005c]
0x8000016c:                       call [f2@0x800000a4]
0x800000e8:                         call [f1@0x8000005c]
0x80000058:                         ret  [f0]              # 注释(2)
0x800000fc:                       ret  [f2]                # 注释(1)
0x80000180:                       call [f2@0x800000a4]
0x800000e8:                         call [f1@0x8000005c]
0x80000058:                         ret  [f0]
0x800000fc:                       ret  [f2]
0x800001b0:                     ret  [f3]                  # 注释(3)
0x800000fc:                   ret  [f2]
0x80000180:                   call [f2@0x800000a4]
0x800000e8:                     call [f1@0x8000005c]
0x8000016c:                       call [f2@0x800000a4]
0x800000e8:                         call [f1@0x8000005c]
0x80000058:                         ret  [f0]

gcc -o hello hello.c
strip -s hello

gcc -c hello.c
strip -s hello.o

gcc -o hello hello.o

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参数. 如果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, 实现不正确的时候如何快速进行调试, 其实也属于基础设施的范畴. 思考一下, 译码的时候有那么多指令(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程序.

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

一周正确实现一个全乱序执行处理器, 并在上面运行自制分时多任务操作系统Nanos和复杂应用程序仙剑奇侠传

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

// 在DUT host memory的`buf`和REF guest memory的`dest`之间拷贝`n`字节,
// `direction`指定拷贝的方向, `DIFFTEST_TO_DUT`表示往DUT拷贝, `DIFFTEST_TO_REF`表示往REF拷贝
void difftest_memcpy(paddr_t addr, void *buf, size_t n, bool direction);
// `direction`为`DIFFTEST_TO_DUT`时, 获取REF的寄存器状态到`dut`;
// `direction`为`DIFFTEST_TO_REF`时, 设置REF的寄存器状态为`dut`;
void difftest_regcpy(void *dut, bool direction);
// 让REF执行`n`条指令
void difftest_exec(uint64_t n);
// 初始化REF的DiffTest功能
void difftest_init();

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

NEMU的框架代码已经准备好DiffTest的功能了, 在menuconfig中打开相应的选项:

Testing and Debugging
  [*] Enable differential testing

然后重新编译NEMU并运行即可. NEMU的配置系统会根据ISA选择合适的模拟器作为REF:

• x86: KVM. KVM可以借助硬件虚拟化技术直接在硬件上虚拟出一个和真机一样的计算机系统, KVM为Linux的用户程序提供了一套基于ioctl()的API, 我们可以通过这套API让硬件进入这个虚拟化模式, 将客户程序放在其中运行, 并获得客户程序的状态.
• mips32: QEMU. QEMU是一个完整的全系统模拟器, 支持多种ISA. 但我们只能通过基于socket的GDB协议与QEMU进行通信来获取其状态, 通信开销较大. 为了运行QEMU, 你还需要安装它:

  apt-get install qemu-system
  

• riscv32: Spike. Spike是RISC-V社区的一款全系统模拟器, 它的工作原理与NEMU非常类似. 我们在Spike中增加了少量接口来实现DiffTest的API, 感谢2018级陈璐同学的适配工作. 为了运行Spike, 你还需要安装另一个工具:

  apt-get install device-tree-compiler
  

nemu/tools/difftest.mk中已经设置了相应的规则和参数, 会自动进入nemu/tools/下的相应子目录(kvm-diff, qemu-diff或spike-diff)编译动态库, 并把其作为NEMU的--diff选项的参数传入. 打开DiffTest后, nemu/src/cpu/difftest/dut.c中的init_difftest()会额外进行以下初始化工作:

• 打开传入的动态库文件ref_so_file.
• 通过动态链接对动态库中的上述API符号进行符号解析和重定位, 返回它们的地址.
• 对REF的DIffTest功能进行初始化, 具体行为因REF而异.
• 将DUT的guest memory拷贝到REF中.
• 将DUT的寄存器状态拷贝到REF中.

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

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

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

• 有的指令不能让REF直接执行, 或者执行后的行为肯定与NEMU不同, 例如nemu_trap指令, 在REF中, 它是一条非法指令. 此时可以通过difftest_skip_ref()进行校准, 执行它后, 在difftest_step()中会让REF跳过当前指令的执行, 同时把NEMU的当前的寄存器状态直接同步到REF中, 效果相当于"该指令的执行结果以NEMU的状态为准".
• 由于实现的特殊性, QEMU在少数时候会把几条指令打包一起执行. 这时候, 我们调用一次difftest_step(), QEMU就会执行多条指令. 但由于NEMU的fetch_decode_exec_updatepc()是一次执行一条指令, 这样就会引入偏差. 此时可以通过difftest_skip_dut(int nr_ref, int nr_dut)来进行校准, 执行它后, 会马上让REF单步执行nr_ref次, 然后期望NEMU可以在nr_dut条指令之内追上REF的状态, 期间会跳过其中所有指令的检查.

一键回归测试

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

既然将来还要重复运行这些测试用例, 而手动重新运行每一个测试显然是一种效率低下的做法. 为了提高效率, 我们为cpu-tests提供了一键回归测试的功能:

make ARCH=$ISA-nemu run

即可自动批量运行cpu-tests中的所有测试, 并报告每个测试用例的运行结果.

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