第六期第六期 学习讲义

基础设施(2)

bug诊断的利器 - 踪迹

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

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

指令执行的踪迹 - itrace

NEMU已经实现了一个简单的踪迹功能 -- itrace (instruction trace), 它可以记录客户程序执行的每一条指令. itrace的实现很简单, 代码只要记录inst_fetch()取到的每一条指令, 然后调用capstone项目在新窗口中打开提供的反汇编功能(在nemu/src/utils/disasm.c中实现). 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                00 16 56 13
      0x80002b04: slli  a1, a1, 1                00 15 95 93
      0x80002b08: or    a0, s1, a5               00 f4 e5 33
      0x80002b0c: sub   s0, s0, a5               40 f4 04 33
      0x80002b10: jal   -112                     f9 1f f0 ef
      0x80002aa0: lui   a5, 524295               80 00 77 b7
      0x80002aa4: lw    a5, 2028(a5)             7e c7 a7 83
      0x80002aa8: addi  sp, sp, -32              fe 01 01 13
  --> 0x80002aac: sw    s2, 16(sp)               01 21 28 23
      0x80002b3c: ret                            00 00 80 67
      0x80002b14: add   s2, s2, a0               00 a9 09 33
      0x80002b18: bnez  s0, -40                  fc 04 1c e3
      0x80002af0: neg   a5, s0                   40 80 07 b3
      0x80002af4: and   a5, a5, s0               00 87 f7 b3
      0x80002af8: or    a2, s3, a5               00 f9 e6 33
      0x80002afc: or    a1, s4, a5               00 fa 65 b3

实现iringbuf

根据上述内容, 在NEMU中实现iringbuf. 你可以按照自己的喜好来设计输出的格式, 如果你想输出指令的反汇编, 可以参考itrace的相关代码; 如果你不知道应该在什么地方添加什么样的代码, 你就需要RTFSC了.

内存访问的踪迹 - mtrace

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

实现mtrace

这个功能非常简单, 你已经想好如何实现了: 只需要在paddr_read()和paddr_write()中进行记录即可. 你可以自行定义mtrace输出的格式.

不过和最后只输出一次的iringbuf不同, 程序一般会执行很多访存指令, 这意味着开启mtrace将会产生大量的输出, 因此最好可以在不需要的时候关闭mtrace. 噢, 那就参考一下itrace的相关实现吧: 尝试在Kconfig和相关文件中添加相应的代码, 使得我们可以通过menuconfig来打开或者关闭mtrace. 另外也可以实现mtrace输出的条件, 例如你可能只会关心某一段内存区间的访问, 有了相关的条件控制功能, mtrace使用起来就更加灵活了.

函数调用的踪迹 - 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属性则给出了函数的大小.

消失的符号

我们在am-kernels/tests/cpu-tests/tests/add.c中定义了宏NR_DATA, 同时也在add()函数中定义了局部变量c和形参a, b, 但你会发现在符号表中找不到和它们对应的表项, 为什么会这样? 思考一下, 什么才算是一个符号(symbol)?

噢, 通过符号表, 我们可以建立函数名与其地址之间的映射关系! 但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) -----+

寻找"Hello World!"

在Linux下编写一个Hello World程序, 编译后通过上述方法找到ELF文件的字符串表, 你发现"Hello World!"字符串在字符串表中的什么位置? 为什么会这样?

现在我们就可以把一个给定的地址翻译成函数名了: 由于函数的范围是互不相交的, 我们可以逐项扫描符号表中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]

实现ftrace

根据上述内容, 在NEMU中实现ftrace. 你可以自行决定输出的格式. 你需要注意以下内容:

  • 你需要为NEMU传入一个ELF文件, 你可以通过在parse_args()中添加相关代码来实现这一功能
  • 你可能需要在初始化ftrace时从ELF文件中读出符号表和字符串表, 供你后续使用
  • 关于如何解析ELF文件, 可以参考man 5 elf
  • 如果你选择的是riscv32, 你还需要考虑如何从jal和jalr指令中正确识别出函数调用指令和函数返回指令

注意, 你不应该通过readelf等工具直接解析ELF文件. 在真实的项目中, 这个方案确实可以解决问题; 但作为一道学习性质的题目, 其目标是让你了解ELF文件的组织结构, 使得将来你在必要的时候(例如在裸机环境中)可以自己从中解析出所需的信息. 如果你通过readelf等工具直接解析ELF文件, 相当于自动放弃训练的机会, 与我们设置这道题目的目的背道而驰.

不匹配的函数调用和返回

如果你仔细观察上文recursion的示例输出, 你会发现一些有趣的现象. 具体地, 注释(1)处的ret的函数是和对应的call匹配的, 也就是说, call调用了f2, 而与之对应的ret也是从f2返回; 但注释(2)所指示的一组call和ret的情况却有所不同, call调用了f1, 但却从f0返回; 注释(3)所指示的一组call和ret也出现了类似的现象, call调用了f1, 但却从f3返回.

尝试结合反汇编结果, 分析为什么会出现这一现象.

冗余的符号表

在Linux下编写一个Hello World程序, 然后使用strip命令丢弃可执行文件中的符号表:

gcc -o hello hello.c
strip -s hello

用readelf查看hello的信息, 你会发现符号表被丢弃了, 此时的hello程序能成功运行吗?

目标文件中也有符号表, 我们同样可以丢弃它:

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

用readelf查看hello.o的信息, 你会发现符号表被丢弃了. 尝试对hello.o进行链接:

gcc -o hello hello.o

你发现了什么问题? 尝试对比上述两种情况, 并分析其中的原因.

trace与性能优化

我们让大家在NEMU实现trace工具, 是作为一种基础设施来帮助大家进行调试. 事实上, trace除了可以帮助大家认识程序如何运行之外, 还可以指导开发者进行程序和系统的优化, 例如:

  • 可以基于ftrace进一步分析出调用memcpy()时的参数情况, 比如dest和src是否对齐, 拷贝的内存长度是长还是短, 然后根据频繁出现的组合对memcpy()的算法实现进行优化
  • 可以基于ftrace统计函数调用的次数, 对访问次数较多的函数进行优化, 可以显著提升程序的性能
  • 可以基于itrace过滤出分支跳转指令的执行情况, 作为分支预测器(现代处理器中的一个提升性能的部件)的输入, 来调整分支预测器的实现, 从而提升处理器的性能
  • 可以基于mtrace得到程序的访存序列, 作为缓存(现代处理器中的另一个提升性能的部件)模型的输入, 对预取算法和替换算法的优化进行指导(你将会在Lab4中体会这一点)

trace对性能优化来说如此重要, 是因为trace反映了程序运行的真实行为, 如果你拍脑袋优化了程序中一个只会调用1次的函数, 可以想象这样的优化对程序总体性能几乎没有任何提升. 而trace其实向我们展示了程序运行过程中的细节事件, 如果我们对这些事件进行统计意义上的分析, 我们就可以知道哪些事件才是频繁发生的, 而优化这些频繁发生的事件, 才能从统计意义上提升程序和系统的性能, 这才是性能优化的科学方法.

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的可执行文件

阅读相关Makefile, 尝试理解abstract-machine是如何生成native的可执行文件的.

奇怪的错误码

为什么错误码是1呢? 你知道make程序是如何得到这个错误码的吗?

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

这是如何实现的?

为什么定义宏__NATIVE_USE_KLIB__之后就可以把native上的这些库函数链接到klib? 这具体是如何发生的? 尝试根据你在课堂上学习的链接相关的知识解释这一现象.

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

编写可移植的程序

为了不损害程序的可移植性, 你编写程序的时候不能再做一些架构相关的假设了, 比如"指针的长度是4字节"将不再成立, 因为在native上指针长度是8字节, 按照这个假设编写的程序, 在native上运行很有可能会触发段错误.

当然, 解决问题的方法还是有的, 至于要怎么做, 老规矩, STFW吧.

测试你的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);
    }
  }
}

编写更多的测试

尝试理解上述测试代码是如何进行测试的, 并在am-kernels/tests/目录下新增一个针对klib的测试集klib-tests, 测试集的文件结构可以参考am-kernels/tests/am-tests或am-kernels/kernels/hello.

然后针对上文所述的第一类写入函数编写相应的测试代码. 编写测试的时候需要注意一些地方:

  • memcpy()的行为在区间重叠的时候是UB, 你可以在遍历的时候检查区间是否重叠, 若是, 则跳过此次检查; 或者使用另一个相同的数组来作为src, 这样就不会出现重叠的情况
  • 字符串处理函数需要额外注意\0和缓冲区溢出的问题

编写后, 你可以先在native上用glibc的库函数来测试你编写的测试代码, 然后在native上用这些测试代码来测试你的klib实现, 最后再在NEMU上运行这些测试代码来测试你的NEMU实现.

这些库函数这么简单, 我可以不测试吗?

可以. 不过未测试代码永远是错的, 以后你还会使用这些库函数来编写更复杂的程序(例如OS), 如果你以后不想被自己坑了, 现在还是好好花时间来测试一下吧. 另外, 如果你以后想优化这些库函数(例如memcpy()和memset()是以后用得比较多的两个函数), 你可能会编写一个稍微复杂一些的算法, 到了那时候, 你就会发现这些测试是多么重要了.

编写更多的测试(2)

尝试为klib-tests添加针对第二类只读函数的测试, 例如memcmp(), strlen()等. 思考一下, 应该如何得到函数的预期输出?

最后我们来看格式化输出函数. 以%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中的预期输出也是这样生成的.

编写更多的测试(3)

尝试为klib-tests添加针对格式化输出函数的测试. 你可以先通过sprintf()把实际输出打印到一个缓冲区中, 然后通过strcmp()来和预期输出进行对比.

你也可以考虑实现位宽, 精度, 长度修饰符等功能, 然后生成相应的测试用例来进行测试.

Differential Testing

理解指令的执行过程之后, 添加各种指令更多的是工程实现. 工程实现难免会碰到bug, 实现不正确的时候如何快速进行调试, 其实也属于基础设施的范畴. 思考一下, 译码的时候有那么多指令(x86的指令本身就很多), 有一些指令的行为可能还比较复杂(大部分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和另一个模拟器逐条指令地执行同一个客户程序. 双方每执行完一条指令, 就检查各自的寄存器和内存的状态, 如果发现状态不一致, 就马上报告错误, 停止客户程序的执行.

基础设施 - 龙芯杯获胜的秘诀

DiffTest的思想非常简单: 找一个正确的实现, 跟它对比结果. 事实上, 你在PA1实现的表达式生成器, 里面也蕴含着DiffTest的思想: C程序就是REF. am-kernels中提供的cpu-tests也是: 这些测试都会先在native上运行, 得到正确的结果, 你其实是把native作为REF, 来对比程序运行的结果(HIT GOOD/BAD TRAP).

当然, 这里介绍的DiffTest的粒度就更细致了: 我们不仅仅是对比程序运行的结果, 而是对比每条指令的行为. 这样可以帮助我们快速发现并定位指令实现的bug. 我们在龙芯杯比赛中继承了这套思想, 把用verilog/chisel写的CPU作为DUT, 用已经实现好的NEMU作为REF, 很快就可以发现并修复verilog/chisel中的bug. 借助DiffTest, 我们在第二届龙芯杯大赛中书写了

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

的神话在新窗口中打开.

另一个体现DiffTest强大的例子是2020年7月的一个热门话题, 中国科学院大学五位本科生的超硬核毕业证书: 带着自己设计的处理器芯片毕业. 在教师团队的指导下, 学生借助DiffTest让处理器设计与NEMU进行在线对比, 5天成功启动Linux并运行Busybox套件, 4天成功启动Debian并运行GCC和QEMU等复杂应用. 学生还分别在2020年度联盟技术研讨会在新窗口中打开(video在新窗口中打开, slide在新窗口中打开) 和RISC-V全球论坛在新窗口中打开(video在新窗口中打开, slide在新窗口中打开)上分享处理器设计的经验, 其中DiffTest都是作为关键技术进行分享.

上述例子反复地体现了基础设施的重要性: 完善的基础设施使得CPU设计变得高效简单, 甚至完成了前人无法完成的任务. 有了基础设施, 令人望而却步的处理器硬件设计也可以脱胎换骨, 浴火重生: 你几乎不需要再看那些让你晕头转向的波形来调试硬件代码了. 最近硬件设计领域也掀起一股敏捷开发在新窗口中打开的热潮, 基础设施在其中扮演的角色就不言而喻了. 如果你对此感兴趣, 欢迎联系我们, 和我们一同探索基础设施完善的方向.

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

// 在DUT host memory的`buf`和REF guest memory的`addr`之间拷贝`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包含较多源文件, 编译过程可能需要花费数分钟. 为了运行Spike, 你还需要安装另一个工具:
apt-get install device-tree-compiler

忽略编译Spike过程中的如下信息

以下信息不影响Spike的编译结果, 你可以忽略它们.

Makefile:349: warning: overriding recipe for target 'disasm.o'
Makefile:349: warning: ignoring old recipe for target 'disasm.o'
make[2]: Circular libcustomext.so <- libcustomext.so dependency dropped.
make[2]: Circular libsoftfloat.so <- libsoftfloat.so dependency dropped.

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, 框架代码会自动停止客户程序的运行. 特别地, isa_difftest_checkregs()对比结果不一致时, 第二个参数pc应指向导致对比结果不一致的指令, 可用于打印提示信息.

实现DiffTest

上文在介绍API约定的时候, 提到了寄存器状态r需要把寄存器按照某种顺序排列. 你首先需要RTFSC, 从中找出这一顺序, 并检查你的NEMU实现是否已经满足约束.

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

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

咦? 我们不需要对内存的状态进行比较吗? 事实上, 获取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的状态, 期间会跳过其中所有指令的检查.

需要校准的指令

PA2中需要校准的指令有:

  • x86: 无
  • riscv32: 无
  • mips32: 各种跳转指令
    • 这是因为mips32-NEMU没有实现分支延迟槽, 可以通过difftest_skip_dut(2, 1)来校准

匪夷所思的QEMU行为 (有点难度)

在一些旧版的mips32-QEMU中, 仅在上述指令的PC值后12位为0xffc时, 才会进行指令打包. 这个打包条件看上去非常奇怪, 你知道可能的原因是什么吗?

Spike不支持不对齐的访存

RISC-V作为一个RISC架构, 通常是不支持不对齐访存的, 在Spike中执行一条地址不对齐的访存指令将会抛出异常, 让PC跳转到0. 但NEMU为了简化, 没有实现这样的功能, 因此如果让NEMU和Spike同时执行这样的指令, DiffTest将会报错. 不过这很可能是你的软件实现(例如klib)有问题, 请检查并修改相关代码.

使用QEMU作为REF时, 不要同时运行两份NEMU

DiffTest会通过一个固定的端口连接到QEMU, 同时运行两份打开DiffTest的NEMU会出现以下信息:

Failed to find an available port: Address already in use

如果你确信没有同时运行两份NEMU, 但仍然遇到上述信息, 可以通过执行以下命令把残留在后台的QEMU杀掉

pkill -9 qemu

一键回归测试

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

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

make ARCH=$ISA-nemu run

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

NEMU的本质

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

我们编写的NEMU最终会被编译成x86机器代码, 用x86指令来模拟客户指令的执行. 事实上在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, dec和jne三条指令.

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

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

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

捕捉死循环(有点难度)

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

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

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

温馨提示

PA2阶段2到此结束.