基础设施(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参数.

如何生成native的可执行文件

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

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

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

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

奇怪的错误码

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

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

这是如何实现的?

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

先实现memcpy()

定义宏__NATIVE_USE_KLIB__之后, native初始化部分的代码也会调用klib. 为了保证native可以成功初始化, 你需要至少正确实现memcpy(), 否则native在初始化阶段就会触发段错误.

好了, 现在你就可以在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-testsam-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, 实现不正确的时候如何快速进行调试, 其实也属于基础设施的范畴. 思考一下, 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逐条指令地执行同一个客户程序. 双方每执行完一条指令, 就检查各自的寄存器和内存的状态, 如果发现状态不一致, 就马上报告错误, 停止客户程序的执行.

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

DiffTest的思想非常简单: 找一个正确的实现, 跟它对比结果. 事实上, 你在PA1实现的表达式生成器, 里面也蕴含着DiffTest的思想: C程序就是REF. 框架代码提供的测试用例也是: 这些测试都会先在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的`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, 框架代码会自动停止客户程序的运行.

实现DiffTest

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

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

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

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

QEMU的行为可能会随着版本的不同而不同, 在Debian 10中QEMU的版本是3.1.0, 在这个版本下, PA2中需要校准的指令有:

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

如果你使用其它版本的QEMU, 可以根据DiffTest在运行过程中的实际决定如何校准 (有同学反馈在5.x版本中, riscv32的jalr也不需要校准了).

KVM: 一个比QEMU更高效的REF

今年我们提供了一个新的REF: KVM. KVM可以借助硬件虚拟化技术直接在硬件上虚拟出一个和真机一样的计算机系统, KVM为Linux的用户程序提供了一套基于ioctl()的API, 我们可以通过这套API让硬件进入这个虚拟化模式, 将客户程序放在其中运行, 并获得客户程序的状态. 因此使用KVM作为REF可以无需像QEMU那样只能通过GDB协议来与其通信, 从而提升DiffTest的效率. 经过测试, 使用KVM作为REF的效率比QEMU高约70倍. 不过由于KVM虚拟出的计算机系统和真机一样, 而真机的ISA是x86, 因此KVM只能运行x86的客户程序.

框架代码已经为KVM实现了上述的DiffTest API, 并且在nemu/Makefile中添加了相应的规则, 如果选择的ISA是x86, 就会默认使用KVM作为REF, 否则将会默认使用QEMU作为REF. 但如果你的系统不支持KVM的运行(如Ubuntu 18.04中出现KVM相关的编译错误), 请手动将nemu/MakefileDIFF变量的定义从kvm修改为qemu.

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

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

Failed to find an available port: Address already in use

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

pkill -9 qemu

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

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

一键回归测试

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

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

bash runall.sh ISA=$ISA

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

NEMU的本质

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

我们编写的NEMU最终会被编译成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三条指令.

令人更惊讶的是, 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 ""