RTFM

我们在上一小节中已经在概念上介绍了一条指令具体如何执行, 其中有的概念甚至显而易见得难以展开. 但当我们决定往TRM中添加各种高效指令的同时, 也意味着我们无法回避繁琐的细节.

首先你需要了解指令确切的行为, 为此, 你需要阅读生存手册中指令集相关的章节. 具体地, 无论你选择何种ISA, 相应手册中一般都会有以下内容, 尝试RTFM并寻找这些内容的位置:

  • 每一条指令具体行为的描述
  • 指令opcode的编码表格

特别地, 由于x86的指令集的复杂性, 我们为选择x86的同学提供了一个简单的阅读教程.

RISC - 与CISC平行的另一个世界

你是否觉得x86指令集的格式特别复杂? 这其实是CISC的一个特性, 不惜使用复杂的指令格式, 牺牲硬件的开发成本, 也要使得一条指令可以多做事情, 从而提高代码的密度, 减小程序的大小. 随着时代的发展, 架构师发现CISC中复杂的控制逻辑不利于提高处理器的性能, 于是RISC应运而生. RISC的宗旨就是简单, 指令少, 指令长度固定, 指令格式统一, 这和KISS法则有异曲同工之妙. 这里有一篇对比RISC和CISC的小短文.

另外值得推荐的是这篇文章, 里面讲述了一个从RISC世界诞生, 到与CISC世界融为一体的故事, 体会一下RISC的诞生对计算机体系结构发展的里程碑意义.

如果你非常幸运地选择了riscv32, 你会发现目前只需要阅读很少部分的手册内容就可以了: 在PA中, riscv32的客户程序只会由RV32I和RV32M两类指令组成. 这得益于RISC-V指令集的设计理念 - 模块化.

RISC-V - 一款设计精巧的指令集

RISC-V是一款非常年轻的指令集 - 第一版RISC-V是在2011年5月由UC Berkeley的研究团队提出的, 至今已经风靡全球. 开放性是RISC-V的最大卖点, 就连ARM和MIPS也都为之震撼, 甚至还因竞争关系而互撕... 这篇文章叙述了RISC-V的理念以及成长的一些历史.

当然, 这些和处于教学领域的PA其实没太大关系. 关键是

  • RISC-V真的很简单.
  • 简单之余, 还有非常多对程序运行深思熟虑的考量. 如果你阅读RISC-V的手册, 你就会发现里面阐述了非常多设计的推敲和取舍. 另外David Patterson教授(因推广RISC而获得2018年的图灵奖, 可谓体系结构领域的一代宗师) 还为RISC-V的推广编写了一本入门书籍The RISC-V Reader, 书中从系统的角度叙述了RISC-V大量的设计原则, 并与现有指令集进行对比, 非常值得一读. 中科院计算所的三位研究生为这本书编写了中文翻译的版本 (其中一位也算是你们的直系师兄了), 不过由于这本书并没有跟进RISC-V官方手册的最新内容, 而且书中有不少笔误(欢迎到相应的github repo中提issue), 我们还是建议你阅读RISC-V的官方手册.

RTFSC(2)

理解了上一小节的YEMU如何执行指令之后, 你就会对模拟器的框架有一个基本的认识了. NEMU要模拟一个真实的ISA, 因此代码要比YEMU复杂得多, 但其中蕴含的基本原理是和YEMU相同的. 下面我们来介绍NEMU的框架代码如何实现指令的执行.

在RTFSC的过程中, 你会遇到用于抽象ISA差异的大部分API, 因此我们建议你先阅读这个页面来对这些API的功能进行基本的了解, 将来在代码中遇到它们的时候可以进行查阅.

我们在PA1中提到:

我们可以看到cpu_exec()模拟了CPU的工作方式: 不断执行指令. fetch_decode_exec_updatepc()函数(在nemu/src/cpu/cpu-exec.c中定义) 让CPU执行当前PC指向的一条指令, 然后更新PC.

具体地, fetch_decode_exec_updatepc()接受一个Decode类型的结构体指针s, 这个结构体用于存放在执行一条指令过程中的译码和执行信息, 包括指令的PC, 执行方式, 以及操作数的信息. 还有一些信息是ISA相关的, NEMU用一个结构类型ISADecodeInfo来对这些信息进行抽象, 具体的定义在nemu/src/isa/$ISA/include/isa-def.h中. fetch_decode_exec_updatepc()首先会调用fetch_decode()进行取指和译码, fetch_decode()会先把当前的PC保存到s的成员pcsnpc中, 其中s->pc就是当前指令的PC, 而s->snpc则是下一条指令的PC, 这里的snpc是"static next PC"的意思.

然后代码会调用isa_fetch_decode()函数(在nemu/src/isa/$ISA/instr/decode.c中定义), 这是因为取指译码的具体过程是和ISA相关的, 在这里我们先不深究isa_fetch_decode()的细节. 但可以说明的是, 它会随着取指的过程修改s->snpc的值, 使得从isa_fetch_decode()返回后s->snpc正好为下一条指令的PC. 接下来将会把s->snpc的值赋给s->dnpc, 这里的dnpc是"dynamic next PC"的意思. 关于snpcdnpc的区别, 我们会在下文进行说明.

此外, isa_fetch_decode()还会返回一个编号idx, 用于对g_exec_table这一数组进行索引. g_exec_table是一个函数指针的数组, 数组中的每个元素都会指向一个用于模拟指令执行的函数, 我们把这样的函数称为"执行辅助函数"(execution helper function). 通过idx索引这个数组, 可以找到与一条指令相匹配的执行辅助函数, 并把它记录到s->EHelper中.

忽略fetch_decode()中剩下与trace相关的代码, 我们就返回到fetch_decode_exec_updatepc()中. fetch_decode_exec_updatepc()将会调用刚才记录到s->EHelper的执行辅助函数, 来模拟指令执行的真正操作. 最后会更新PC, 让PC指向下一条指令.

显然, fetch_decode_exec_updatepc()函数覆盖了指令周期的所有阶段: 取指, 译码, 执行, 更新PC. 在这些阶段中, 代码都可以对s进行记录和访问. 接下来我们来看看NEMU是如何实现指令周期的每一个阶段的.

取指(instruction fetch, IF)

isa_fetch_decode()做的第一件事情就是取指令. 在NEMU中, 有一个函数instr_fetch()(在nemu/include/cpu/ifetch.h中定义)专门负责取指令的工作. instr_fetch()最终会根据参数len来调用vaddr_ifetch()(在nemu/src/memory/vaddr.c中定义), 而目前vaddr_ifetch()又会通过paddr_read()来访问物理内存中的内容. 因此, 取指操作的本质只不过就是一次内存的访问而已.

isa_fetch_decode()在调用instr_fetch()的时候传入了s->snpc的地址, 因此instr_fetch()最后还会根据len来更新s->snpc, 从而让s->snpc指向下一条指令.

译码(instruction decode, ID)

译码的目的是得到指令的操作和操作对象, 这主要是通过查看指令的opcode来决定的. 不同ISA的opcode会出现在指令的不同位置, 我们只需要根据指令的编码格式, 从取出的指令中识别出相应的opcode即可.

和YEMU相比, NEMU使用一种抽象层次更高的译码方式: 模式匹配, NEMU可以通过一个模式字符串来指定指令中opcode, 例如在riscv32中有如下模式:

def_INSTR_IDTAB("??????? ????? ????? ??? ????? 01101 11", U     , lui);

模式字符串中只允许出现4种字符:

  • 0表示相应的位只能匹配0
  • 1表示相应的位只能匹配1
  • ?表示相应的位可以匹配01
  • (空格)是分隔符, 只用于提升模式字符串的可读性, 不参与匹配

其中def_INSTR_IDTAB是一个宏, 它在nemu/include/cpu/decode.h中定义, 对它进行宏展开并简单整理代码之后, 最后将会得到:

do {
  uint32_t key, mask, shift;
  pattern_decode("??????? ????? ????? ??? ????? 01101 11", 37, &key, &mask, &shift);
  if (((s->isa.instr.val >> shift) & mask) == key) {
    decode_U(s, 0);
    return table_lui(s);
  }
} while (0);

pattern_decode()函数在nemu/include/cpu/decode.h中定义, 它用于将模式字符串转换成3个整型变量, 其中key抽取了模式字符串中的01, mask表示key的掩码, 而shift则表示opcode距离最低位的比特数量, 用于帮助编译器进行优化. 具体地, 上述例子中:

key   = 0x37;
mask  = 0x7f;
shift = 0;

考虑PA1中介绍的内建客户程序中的如下指令:

0x800002b7   lui t0,0x80000

NEMU取指令的时候会把指令记录到s->isa.instr.val中, 此时指令满足上述宏展开的if语句, 表示匹配到lui指令的编码, 因此将会进行进一步的译码操作.

刚才我们只知道了指令的具体操作(比如lui是读入一个立即数到寄存器的高位), 但我们还是不知道操作对象(比如立即数是多少, 读入到哪个寄存器). 为了解决这个问题, 代码需要进行进一步的译码工作, 这是通过调用相应的译码辅助函数(decode helper function)来完成的. 译码辅助函数统一通过宏def_DHelper(在nemu/include/cpu/decode.h中定义)来定义:

#define def_DHelper(name) void concat(decode_, name) (Decode *s)

每个译码辅助函数负责进行一种类型的操作数译码, 把指令中的操作数信息分别记录在译码信息sdest成员, src1成员和src2成员中, 它们分别代表目的操作数和两个源操作数. nemu/include/cpu/decode.h中还定义了三个宏id_dest, id_src1id_src2, 用于方便地访问它们.

我们会发现, 类似寄存器和立即数这些操作数, 其实是非常常见的操作数类型. 为了进一步实现操作数译码和指令译码的解耦, 框架代码对这些操作数的译码进行了抽象封装, 指令译码过程由若干译码操作数辅助函数(decode operand helper function)组成. 译码操作数辅助函数统一通过宏def_DopHelper来定义

// nemu/src/isa/riscv32/instr/decode.c
#define def_DopHelper(name) \
  void concat(decode_op_, name) (Decode *s, Operand *op, word_t val, bool flag)

DopHelper带有一个flag参数, 不同的DopHelper可以用它来进行不同的处理. 例如寄存器的DopHelper可以通过flag来指示是否写入:

static def_DopHelper(r) {
  bool is_write = flag;
  static word_t zero_null = 0;
  op->preg = (is_write && val == 0) ? &zero_null : &gpr(val);
}

在mips和riscv中, 0号寄存器的值恒为0, 因此往0号寄存器的写入操作都会被硬件忽略. 为了实现这个功能, 上述代码会在译码的时候检查指令是否尝试往0号寄存器进行写入, 若是, 则把写入的目的修改成一个"黑洞变量", 这个变量不会被其它代码读取, 从而实现"往0号寄存器的写入操作都会被硬件忽略"的效果.

有了这些译码操作数辅助函数, 我们就可以用它们来编写译码辅助函数了, 例如riscv中I-型指令的译码过程可以通过如下代码实现:

static def_DHelper(I) {
  decode_op_r(s, id_src1, s->isa.instr.i.rs1, false);
  decode_op_i(s, id_src2, s->isa.instr.i.simm11_0, false);
  decode_op_r(s, id_dest, s->isa.instr.i.rd, true);
}
x86的变长指令

由于CISC指令变长的特性, x86指令长度和指令形式需要一边取指一边译码来确定, 而不像RISC指令集那样可以泾渭分明地处理取指和译码阶段, 因此你会在x86的译码操作数辅助函数中看到instr_fetch()的操作.

立即数背后的故事

框架代码通过instr_fetch()函数进行取指, 别看这里就这么一行代码, 其实背后隐藏着针对字节序的慎重考虑. 大部分同学的主机都是x86小端机, 当你使用高级语言或者汇编语言写了一个32位常数0x1234的时候, 在生成的二进制代码中, 这个常数对应的字节序列如下(假设这个常数在内存中的起始地址是x):

x   x+1  x+2  x+3
+----+----+----+----+
| 34 | 12 | 00 | 00 |
+----+----+----+----+

而大多数PC机都是小端架构(我们相信没有同学会使用IBM大型机来做PA), 当NEMU运行的时候,

imm = instr_fetch(pc, 4);

这行代码会将34 12 00 00这个字节序列原封不动地从内存读入imm变量中, 主机的CPU会按照小端方式来解释这一字节序列, 于是会得到0x1234, 符合我们的预期结果.

Motorola 68k系列的处理器都是大端架构的. 现在问题来了, 考虑以下两种情况:

  • 假设我们需要将NEMU运行在Motorola 68k的机器上(把NEMU的源代码编译成Motorola 68k的机器码)
  • 假设我们需要把Motorola 68k作为一个新的ISA加入到NEMU中

在这两种情况下, 你需要注意些什么问题? 为什么会产生这些问题? 怎么解决它们?

事实上不仅仅是立即数的访问, 长度大于1字节的内存访问都需要考虑类似的问题. 我们在这里把问题统一抛出来, 以后就不再单独讨论了.

立即数背后的故事(2)

mips32和riscv32的指令长度只有32位, 因此它们不能像x86那样, 把C代码中的32位常数直接编码到一条指令中. 思考一下, mips32和riscv32应该如何解决这个问题?

回到def_INSTR_IDTAB的宏展开结果, 对于lui指令, 在译码辅助函数decode_U()执行结束后, 代码将会执行table_lui(). table_lui()的定义方式比较特殊, 我们在这里先给出部分宏展开后的定义:

def_THelper(lui) {
  return EXEC_ID_lui;
}

其中宏def_THelper(在nemu/include/cpu/decode.h中定义) 用于统一定义"表格辅助函数"(table helper function). table_lui()做的事情很简单, 它直接返回一个标识lui指令的唯一ID. 这个ID会作为译码结果的返回值, 在fetch_decode()中索引g_exec_table数组.

我要被宏定义绕晕了, 怎么办?

为了理解一个宏的语义, 你可能会尝试手动对它进行宏展开, 但你可能会碰到如下困难:

  • 宏嵌套的次数越多, 理解越困难
  • 一些拼接宏会影响编辑器的代码跳转功能

事实上, 为了进行宏展开, 你并不需要手动去进行操作, 因为肯定有工具能做这件事: 我们只需要让GCC把编译预处理的结果输出出来, 就可以看到宏展开的结果了. 有了宏展开的结果, 你就可以快速理解展开之后的语义, 然后反过来理解相应的宏是如何一步步被展开的了.

当然, 最方便的做法是让GCC编译NEMU的时候顺便输出预处理的结果, 如果你对Makefile的组织有一定的认识, 这件事当然也难不倒你了.

事实上, 译码的过程可以看成是若干查表的操作, 每一条模式匹配的规则都可以看成是表格中的一个表项, 因此我们可以使用表格辅助函数来描述这些译码的规则. 以riscv为例:

def_INSTR_IDTAB("??????? ????? ????? ??? ????? 00000 11", I     , load);

这一模式字符串只能通过opcode匹配到load类型的指令, 为了进一步确定是哪一条load指令, 我们还需要匹配funct3字段, 因此我们引入一个新的表格辅助函数table_load(), 匹配到load类型指令的时候, 会进一步调用table_load(), 然后在其中通过额外的模式字符串来匹配funct3字段, 例如: 以riscv为例:

def_THelper(load) {
  def_INSTR_TAB("??????? ????? ????? 010 ????? ????? ??", lw);
  return EXEC_ID_inv;
}

这里def_INSTR_TAB也是一条字符串匹配规则, 但它并不需要调用译码辅助函数. 这条规则描述了"在load类型指令中, 如果funct3010, 则为lw指令".

事实上, NEMU把译码时的如下情况都看作是查表过程:

  • isa_fetch_decode()中查主表(main decode table)
  • 在译码过程中分别匹配指令中的每一个域(如上文介绍的table_load()
  • 译码出最终的指令时认为是一种特殊的查表操作, 直接返回标识该指令的唯一ID

如果所有模式匹配规则都无法成功匹配, 代码将会返回一个标识非法指令的ID.

执行(execute, EX)

译码过程结束之后, 接下来会返回到fetch_decode()中, 并通过返回的ID来从g_exec_table数组中选择相应的执行辅助函数(execution helper function), 然后记录到s->EHelper中. 返回到fetch_decode_exec_updatepc()后, 代码将会调用刚才记录的执行辅助函数. 执行辅助函数统一通过宏def_EHelper(在nemu/include/cpu/exec.h中定义)来定义:

#define def_EHelper(name) static inline void concat(exec_, name) (Decode *s)

它们的名字是指令操作本身. 执行辅助函数通过RTL指令来描述指令真正的执行功能(RTL指令将在下文介绍).

特别地, 对于x86来说, 大部分计算指令都可以访问内存, 来根据目的操作数类型的不同, 决定是写入寄存器还是写入内存; 而对于mips32和riscv32, 访问内存只能通过特定的访存指令进行, 因此每条指令的目的操作数类型都是唯一的.

每个执行辅助函数都需要有一个标识该指令的ID以及一个表格辅助函数与之相对应, 这一点是通过一系列宏定义来实现的. 在nemu/src/isa/$ISA/include/isa-all-instr.h中定义用于表示指令列表的宏INSTR_LIST, 它定义了NEMU支持的所有指令. 然后代码通过一种类似函数式编程的方式来定义如下相关的内容:

  • nemu/include/cpu/decode.h中为所有的执行辅助函数定义相应的ID. 以riscv32为例, 对def_all_EXEC_ID()进行宏展开后, 结果如下:
    enum { EXEC_ID_lui, EXEC_ID_lw, EXEC_ID_sw, EXEC_ID_inv, EXEC_ID_nemu_trap, TOTAL_INSTR }
    
    其中TOTAL_INSTR的值正好为目前所有指令的总数.
  • nemu/include/cpu/decode.h中为所有的执行辅助函数定义相应的表格辅助函数. 这是通过宏def_all_THelper()来定义的, 它会为每条指令定义一个表格辅助函数, 用于返回相应的ID.
  • nemu/src/cpu/cpu-exec.c中为所有的执行辅助函数定义g_exec_table.

因此, 我们只需要维护nemu/src/isa/$ISA/include/isa-all-instr.h中的指令列表, 就可以正确维护执行辅助函数和译码之间的关系了.

更新PC

更新PC的操作非常简单, 只需要把s->dnpc赋值给cpu.pc即可. 我们之前提到了snpcdnpc, 现在来说明一下它们的区别.

静态指令和动态指令

在程序分析领域中, 静态指令是指程序代码中的指令, 动态指令是指程序运行过程中的指令. 例如对于以下指令序列

100: jmp 102
101: add
102: xor

jmp指令的下一条静态指令是add指令, 而下一条动态指令则是xor指令.

有了静态指令和动态指令这两个概念之后, 我们就可以说明snpcdnpc的区别了: snpc是指代码中的下一条指令, 而dnpc是指程序运行过程中的下一条指令. 对于顺序执行的指令, 它们的snpcdnpc是一样的; 但对于跳转指令, snpcdnpc就会有所不同, dnpc应该指向跳转目标的指令. 显然, 我们应该使用s->dnpc来更新PC, 并且在执行辅助函数中正确维护s->dnpc.


上文已经把一条指令在NEMU中执行的流程进行了大概的介绍, 但还有少量的细节没有完全覆盖(例如指令组的译码表), 这些细节就交给你来去尝试理解啦. 不过为了特别照顾选择x86的同学, 我们还是准备了一个例子来RTFSC.

驾驭项目, 而不是被项目驾驭

你和一个项目的关系会经历4个阶段:

  1. 被驾驭: 你对它一无所知
  2. 一知半解: 你对其中的主要模块和功能有了基本的了解
  3. 驾轻就熟: 你对整个项目的细节都了如指掌
  4. 为你所用: 你可以随心所欲地在项目中添加你认为有用的功能

在PA中, 达到第二个阶段的主要手段是阅读讲义和代码, 达到第三个阶段的主要手段是独立完成实验内容和独立调试. 至于要达到第四个阶段, 就要靠你的主观能动性了: 代码还有哪里做得不够好? 怎么样才算是够好? 应该怎么做才能达到这个目标?

你毕业后到了工业界或学术界, 就会发现真实的项目也都是这样:

  1. 刚接触一个新项目, 不知道如何下手
  2. RTFM, RTFSC, 大致明白项目组织结构和基本的工作流程
  3. 运行项目的时候发现有非预期行为(可能是配置错误或环境错误, 可能是和已有项目对接出错, 也可能是项目自身的bug), 然后调试. 在调试过程中, 对这些模块的理解会逐渐变得清晰.
  4. 哪天需要你在项目中添加一个新功能, 你会发现自己其实可以胜任.

这说明了: 如果你一遇到bug就找大神帮你调试, 你失去的机会和能力会比你想象的多得多.

拦截客户程序访存越界的非法行为

你将来很可能会遇到客户程序访存越界的错误, NEMU的框架代码一旦检测到这一行为就会直接panic. 这一行为的检测已经极大地帮助你发现代码的问题了, 想象一下, 如果NEMU并未拦截这一error, 你可能会看到怎么样的failure?

结构化程序设计

我们刚才介绍了译码辅助函数和译码操作数辅助函数等机制, 它们的引入都是为了实现代码的解偶, 提升可维护性: 通过译码操作数辅助函数来实现译码辅助函数, 然后通过译码辅助函数来实现模式匹配的规则.

如果指令集越复杂, 指令之间的共性特征就越多, 以x86为例:

  • 对于同一条指令的不同形式, 它们的执行阶段是相同的. 例如add_I2Eadd_E2G等, 它们的执行阶段都是把两个操作数相加, 把结果存入目的操作数.
  • 对于不同指令的同一种形式, 它们的译码阶段是相同的. 例如add_I2Esub_I2E等, 它们的译码阶段都是识别出一个立即数和一个E操作数.
  • 对于同一条指令同一种形式的不同操作数宽度, 它们的译码阶段和执行阶段都是非常类似的. 例如add_I2E_b, add_I2E_wadd_I2E_l, 它们都是识别出一个立即数和一个E操作数, 然后把相加的结果存入E操作数.

这意味着, 如果独立实现每条指令不同形式不同操作数宽度的辅助函数, 将会引入大量重复的代码. 需要修改的时候, 相关的所有辅助函数都要分别修改, 遗漏了某一处就会造成bug, 工程维护的难度急速上升.

Copy-Paste - 一种糟糕的编程习惯

事实上, 第一版PA发布的时候, 框架代码就恰恰是引导大家独立实现每一个辅助函数. 大家在实现指令的时候, 都是把已有的代码复制好几份, 然后进行一些微小的改动(例如把<<改成>>). 当你发现这些代码有bug的时候, 噩梦才刚刚开始. 也许花了好几天你又调出一个bug的时候, 才会想起这个bug你好像之前在哪里调过. 你也知道代码里面还有类似的bug, 但你已经分辨不出哪些代码是什么时候从哪个地方复制过来的了. 由于当年的框架代码没有足够重视编程风格, 导致学生深深地陷入调试的泥淖中, 这也算是PA的一段黑历史了.

这种糟糕的编程习惯叫Copy-Paste, 经过上面的分析, 相信你也已经领略到它的可怕了. 事实上, 周源源教授的团队在2004年就设计了一款工具CP-Miner, 来自动检测操作系统代码中由于Copy-Paste造成的bug. 这个工具还让周源源教授收获了一篇系统方向顶级会议OSDI的论文, 这也是她当时所在学校UIUC史上的第一篇系统方向的顶级会议论文.

不过, 之后周源源教授发现, 相比于操作系统, 应用程序的源代码中Copy-Paste的现象更加普遍. 于是她们团队把CP-Miner的技术应用到应用程序的源代码中, 并创办了PatternInsight公司. 很多IT公司纷纷购买PatternInsight的产品, 并要求提供相应的定制服务, 甚至PatternInsight公司最后还被VMWare收购了.

这个故事折射出, 大公司中程序员的编程习惯也许不比你好多少, 他们也会写出Copy-Paste这种难以维护的代码. 但反过来说, 重视编码风格这些企业看中的能力, 你从现在就可以开始培养.

一种好的做法是把译码, 执行和操作数宽度的相关代码分离开来, 实现解耦, 也就是在程序设计课上提到的结构化程序设计. 在框架代码中, 实现译码和执行之间的解耦的是isa_fetch_decode()返回的编号, 这样我们就可以分别编写译码和执行的辅助函数, 然后来进行组合了: 这样的设计可以很容易实现执行行为相同但译码方式不同的多条指令. 对于x86, 实现操作数宽度和译码, 执行这两者之间的解耦的是ISADecodeInfo结构体中的width成员, 它们记录了操作数宽度, 译码和执行的过程中会根据它们进行不同的操作, 通过同一份译码辅助函数和执行辅助函数实现不同操作数宽度的功能.

用RTL表示指令行为

我们知道, x86指令作为一种CISC指令集, 不少指令的行为都比较复杂. 但我们会发现, i386手册会用一些更简单的操作来表示指令的具体行为. 这说明, 复杂的x86指令还是能继续分解成一些更简单的操作的组合. mips32和riscv32的少数较复杂指令也能够进一步进行分解. 如果我们先实现这些简单操作, 然后再用它们来实现指令, 不就可以进一步提高代码的复用率了吗?

在NEMU中, 我们使用RTL(寄存器传输语言)来描述这些简单的操作. 下面我们对NEMU中使用的RTL进行一些说明, 首先是RTL寄存器的定义. 在NEMU中, RTL寄存器统一使用rtlreg_t来定义, 而rtlreg_t(在nemu/include/common.h中定义)其实只是一个word_t类型:

typedef word_t rtlreg_t;

在NEMU中, RTL寄存器只有以下这些

  • 不同ISA的通用寄存器(在nemu/src/isa/$ISA/include/isa-def.h中定义)
  • 临时寄存器s0, s1, s2t0(在nemu/include/rtl/rtl.h中定义)
  • 零寄存器rz(在nemu/include/rtl/rtl.h中定义), 它的值总是0
  • x86的ISA相关译码信息中的内存基地址mbr
  • $ISA为x86时id_src, id_src2id_dest中的操作数内容val (在nemu/include/cpu/decode.h中定义)

有了RTL寄存器, 我们就可以定义RTL指令对它们进行的操作了. 在NEMU中, RTL指令有两种.

一种是RTL基本指令(在nemu/src/engine/interpreter/rtl-basic.h中定义), 它们的特点是不需要使用临时寄存器, 可以看做是CPU执行过程中最基本的操作. 不同的ISA都可以使用RTL基本指令, 因此它们属于ISA无关的代码. RTL基本指令包括(我们使用了一些简单的正则表达式记号):

  • 32位寄存器-寄存器类型和寄存器-立即数类型的基本算术/逻辑运算, 包括rtl_(add|sub|and|or|xor|sll|srl|sra|setrelop)i?, 它们的定义用到了nemu/src/engine/interpreter/c_op.h中的C语言运算和interpret_relop()函数
  • 32位寄存器-寄存器类型的乘法运算, 包括rtl_mulu_[lo|hi]rtl_muls_hi,
  • 32位寄存器-寄存器类型的除法运算, 包括rtl_div[u|s]_[q|r],
  • 被除数为64位的除法运算rtl_div64[u|s]_[q|r]
  • guest内存访问rtl_lm, rtl_lmsrtl_sm
  • host内存访问rtl_host_lmrtl_host_sm(在PA中不使用)
  • 跳转, 包括直接跳转rtl_j, 间接跳转rtl_jr和条件跳转rtl_jrelop
  • host调用rtl_hostcall(在nemu/src/engine/interpreter/hostcall.c中定义), 用于处理一些特殊的"非常规"功能, 如nemu_trap, 非法指令, 端口I/O等
为什么不需要rtl_muls_lo?

我们没有定义用于获取有符号数乘法结果低32位的RTL基本指令rtl_muls_lo, 你知道为什么吗?

64位ISA特有的RTL基本指令

如果你选择了riscv64, 上述寄存器操作相关的RTL基本指令是针对64位位宽的, 为了方便进行32位数据的处理, 框架代码还额外提供了32位位宽的RTL基本指令:

  • 32位寄存器-寄存器类型的基本算术/逻辑运算, 包括rtl_(add|sub|sll|srl|sra)w
  • 32位寄存器-立即数类型的基本算术/逻辑运算, 包括rtl_(add|sll|srl|sra)iw
  • 32位寄存器-寄存器类型的乘除法运算, 包括rtl_mulwrtl_(div|rem)u?w

这些RTL基本指令的语义和相应的riscv64指令非常类似, 具体可以参考riscv手册.

RTL指令和二进制翻译

我们参考riscv指令的语义来定义RTL基本指令的行为, 恰恰体现了riscv指令集的简单. 那么, 既然我们能用RTL指令来表示x86指令的行为, 是不是也有可能用类似的riscv指令来模拟一条x86指令的行为呢?

这就是二进制翻译的基本想法, QEMU就是这样工作的! 当然不仅仅是用riscv指令来模拟x86指令, 用x86指令来模拟riscv指令也是可以的, 甚至所有指令集之间都能相互模拟, 因为理论上指令集的定义就是图灵完备的. 所以当你在x86的机器中运行riscv32-qemu时, 对于客户程序的每一条riscv32指令, QEMU都会生成若干条x86指令, 当x86真机执行了这些x86指令, 就相当于完成了客户程序中相应的riscv32指令的功能.

第二种RTL指令是RTL伪指令, 它们是通过RTL基本指令或者已经实现的RTL伪指令来实现的. RTL伪指令又分两类, 包括:

  • ISA无关的RTL伪指令(在nemu/include/rtl/pseudo.h中定义), 主要包括一些常用的功能, 如立即数读入rtl_li, 寄存器传输rtl_mv, 按位取反rtl_not, 符号扩展rtl_sext等, 用于方便RTL的编写
  • ISA相关的RTL伪指令(在nemu/src/isa/$ISA/local-include/rtl.h中定义), 主要包括ISA相关性较强的功能(如x86的通用寄存器访问rtl_lrrtl_sr, 溢出和进/借位判断, EFLAGS标志位访问等)

其中大部分RTL伪指令还没有实现, 必要的时候你需要实现它们. 有了这些RTL指令之后, 我们就可以方便地通过若干条RTL指令来实现每一条指令的行为了.

小型调用约定

我们定义RTL基本指令的时候, 约定了RTL基本指令不需要使用RTL临时寄存器. 但某些RTL伪指令需要使用临时寄存器存放中间结果, 才能实现其完整功能. 这样可能会带来寄存器覆盖的问题, 例如如下RTL指令序列:

(1) rtl_mv(s, t0, s1);
(2) rtl_sext(s, s1, s0, 1);  // use t0 temporarily
(3) rtl_add(s, s0, t0, s2);

如果实现(2)的时候恰好使用到了t0作为临时寄存器, 在(3)中使用的t0就不再是(1)的结果了, 从而产生非预期的结果.

为了尽可能避免上述问题, 我们约定以下两条规则:

  • 实现RTL伪指令的时候, 尽可能不使用dest之外的寄存器存放中间结果. 由于dest最后会被写入新值, 其旧值肯定要被覆盖, 自然也可以安全地作为RTL伪指令的临时寄存器.
  • 实在需要使用临时寄存器的时候, 按照以下约定来使用:
    • t0, t1, ... - 只能在RTL伪指令的实现过程中存放中间结果
    • s0, s1, ... - 只能在译码辅助函数和执行辅助函数的实现过程中存放中间结果

仔细体会上述约定, 你也许会发现, 这和课上学习的调用约定(calling convention)有那么一点点相似之处. 如果把RTL指令看成一个函数调用, 我们刚才其实在讨论, 在这个"函数"里面究竟可以使用哪些RTL寄存器. 在调用约定中, 有些寄存器对被调用函数来说, 使用它们之前是需要先保存的. 但我们的RTL编程模型中并没有"栈"的概念, 所以在RTL中我们就不设置所谓的"被调用者保存寄存器"了. 从某种程度上来说, 这样的"小型调用约定"很难支撑大规模RTL指令的编写. 不过幸好, 在用RTL来实现指令的时候, 这一"小型调用约定"已经足够使用了.

计算机系统中的约定与未定义行为

上述例子其实折射出计算机系统工作的一种基本原则: 遵守约定.

我们定义了RTL寄存器和相应的RTL指令, 基于这些定义, 原则上可以编写出任意的RTL指令序列, 这些RTL序列最终也会按照它们原本的语义来执行. 但光靠这些定义, 我们无法避免上述RTL寄存器相互覆盖造成错误的问题. 所以我们又提出一些新的约定, 来避免这个问题. 当然, 你也可以自己提出一套新的约定(比如把t0s0的用法互换).

违反约定会发生什么呢? 最常见的就是程序无法得到正确的结果. 比如当两套约定不兼容的RTL代码放在一起的时候, 它们都分别违反了对方的约定 (你的RTL覆盖了我的t0, 我的RTL覆盖了你的s0). 当然也有可能恰好没有覆盖各自约定使用的寄存器, 撞大运地得到正确的运行结果. 总之, 违反约定的具体行为会怎么样, 还需要具体问题具体分析, 很难明确地说清楚.

既然说不清楚, 那就干脆不说吧, 于是有了未定义行为(UB, Undefined Behavior)的概念: 只要遵守约定, 就能保证程序具有遵守约定后的特性; 如果违反, 不按照说好的来, 那就不保证行为是正确的.

计算机系统就是这样工作的: 计算机系统抽象层之间的接口其实也是一种约定, 比如指令就是软件和硬件的一种接口, 所以有了ISA手册来规范每一条指令的行为.

  • 一方面, 编译器需要根据ISA手册中的约定来生成可以正确执行的代码. 如果编译器不按照手册约定来生成代码, 那么编译出的程序的行为就是未定义的.
  • 另一方面, 硬件开发者也需要根据ISA手册中的约定来设计可以正确执行指令的处理器. 如果处理器不按照手册约定来执行指令, 处理器运行程序的行为就是未定义的.

引入未定义行为还有一个好处是, 给约定的实现方式带来一定的自由度. 例如, C语言标准规定, 整数除法的除数为0时, 结果是未定义的. x86的除法指令在检测到除数为0时, 就会向CPU抛出一个异常信号. 而MIPS的除法指令则更简单暴力: 首先在MIPS指令集手册中声明, 除数为0时, 结果未定义; 然后在硬件上实现除法器电路的时候, 对除0操作就可以视而不见了. 然而给定一个除法器电路, 就算除数为0, 电路的输出也总会有一个值, 至于具体的值是什么, 就看造化了. 反正C语言标准规定除0的行为本身就是未定义的, 让除法指令随便返回一个值, 也不算违反C语言标准的约定.

未定义行为其实离你很近. 比如野指针的解引用, 会发生什么完全无法预料. 还有你经常使用的memcpy(), 如果源区间和目的区间有重叠时, 它的行为会怎么样? 如果你从来没有思考过这个问题, 你应该去man一下, 然后思考一下为什么会这样. 还有一种有人欢喜有人愁的现象是基于未定义行为的编译优化: 既然源代码的行为是未定义的, 编译器基于此进行各种奇葩优化当然也不算违反约定. 这篇文章列举了一些让你大开眼界的花式编译优化例子, 看完之后你就会刷新对程序行为的理解了.

所以这就是为什么我们强调要学会RTFM. RTFM是了解接口行为和约定的过程: 每个输入的含义是什么? 查阅对象的具体行为是什么? 输出什么? 有哪些约束条件必须遵守? 哪些情况下会报什么错误? 哪些行为是UB? 只有完全理解并遵守它们, 才能正确无误地使用查阅的对象, 大至系统设计原则, 小到一个memcpy()的行为, 都蕴含着约定与遵守的法则. 理解这些法则, 也是理解计算机系统的不二途径.

UB, 编译优化和datalab

听闻大班的lab1(datalab)曾经因为使用了debian10的新版gcc而翻车. 后来了解到, 是因为datalab的参考代码中含有int整数溢出的UB, debian 10的gcc利用了该UB进行编译优化, 导致参考代码生成了错误的参考答案.

C语言标准规定, int整数溢出的行为是未定义的, 但大部分程序员并不知道这一约定, 甚至连市面上流行的C语言教科书都认为int整数溢出的结果是wrap around. datalab是CMU设计的实验, 但原作者也会编写出含有UB的代码, 说明原作者对UB的理解也并未到位. 在旧版本的编译器中, 这些UB均未被触发. 但UB毕竟是UB, 只能说明作者写代码的时候没有充分理解C语言标准.

这篇论文对整数溢出的分类和行为进行了梳理, 并且在实际应用中找出了大量整数溢出的例子进行分析, 推荐大家阅读. 论文中提到有一个被广泛应用(包括Office和Windows)的函数库SafeInt用于避免整数溢出, 但这个函数库自身的代码就被论文作者检测出整数溢出导致的UB.

这些例子给我们的启示是: 我们不仅需要编写通过测试的代码, 而且需要编写符合语言规范的well-defined的代码. 退一步讲, 人毕竟会犯错误, 但我们至少要在出错的时候知道, 什么才是对的.

RTL寄存器中值的生存期

在程序设计课上, 我们知道C语言中不同的变量有不同的生存期: 有的变量的值会一直持续到程序结束, 但有的变量却很快消亡. 在上述定义的RTL寄存器中, 其实也有不同的生存期. 尝试根据生存期给RTL寄存器分类.

尽管目前这个分类结果并没有什么用处, 但其实将来在PA5中设计RTL优化方案的时候, 生存期的性质会给我们提供很大的优化机会.

为了提高性能, 我们在Operand结构体中定义了一个RTL寄存器的指针preg, 用于直接指向那些已经存在的RTL寄存器. 例如如果在进行译码的时候发现操作数是a0寄存器, 那么只需要通过让preg指向cpu.gpr[10], 将来就可以直接通过preg来访问到正确的操作数了, 而不需要通过rtl_mv()来将cpu.gpr[10]读到别处, 从而避免引入额外的开销. 框架代码提供了dsrc1, dsrc2ddest这三个宏, 分别用于方便地访问id_src1, id_src2id_dest对应的preg.

虽然使用指针可以提高性能, 但也会有以下几点需要注意:

  • 如果源操作数是x86寄存器的字节或半字访问, 那么其类型并不是一个完整的rtlreg_t, 不能直接被preg指向. 此时译码过程会通过rtl_lr将相应的值读入到操作数结构体Operandval成员, 然后再让preg指向val.
  • 一般来说源操作数是不应该被修改的, 如果你打算把dsrc1或者dsrc2作为RTL指令的dest, 你需要确认这是否符合指令本身的语义.
  • 如果一条指令的源操作数和目的操作数一样, 你可能需要注意一些RTL指令之间的顺序.

如果你理解不了上面的注意事项, 不必担心, 你可以把编写RTL作为一次指针的练习, 遇到问题的时候你就会对指针有更加深刻的理解了.

实现新指令

对译码, 执行和操作数宽度的解耦实现以及RTL的引入, 对在NEMU中实现客户指令提供了很大的便利, 为了实现一条新指令, 你只需要

  1. nemu/src/isa/$ISA/instr/decode.c中添加正确的模式匹配规则
  2. 用RTL实现正确的执行辅助函数, 需要注意使用RTL伪指令时要遵守上文提到的小型调用约定
  3. nemu/src/isa/$ISA/include/isa-all-instr.h中把指令添加到INSTR_LIST
  4. 必要时在nemu/src/isa/$ISA/include/isa-exec.h中添加相应的头文件
感觉RTL临时寄存器不够用了?

其实是存在够用的实现方式的, 你可以尝试挑战一下这个目标. 当然, 如果实在坚持不了的话, 你也可以定义更多的RTL临时寄存器, 如t1, t2, s3...

事实上, 如果定义了过多的RTL临时寄存器, 可能会对PA5的性能优化带来一些负面影响. 不过PA5并不记入成绩, 所以你也不用为此感到担忧.

框架代码定义了一些译码辅助函数和执行辅助函数, 你可以很方便地使用它们.

偏心的框架代码

这个"一些"对不同的ISA来说, 还是有很大差别的: 对x86来说其实是"绝大部分", 而对mips32和riscv32来说其实是"少量".

你应该能感受到, 这节讲义内容为x86提供了很多帮助, 而对mips32和riscv32的提示却很少, 甚至提供的框架代码也非常寒酸. 你也许会觉得这是yzh偏心, 但其实这恰恰反衬出x86的复杂(看看不同ISA的手册就知道了). 考虑到公平性, 选择mips32和riscv32的同学则需要独立编写大部分的译码辅助函数 (其实很少, 因为RISC指令集的格式都比较规整)和执行辅助函数 (其实很简单, 因为NEMU中的RTL就是参考riscv来定义的, 也可以看成是一种RISC指令集).

你可以与选择不同ISA的同学交流, 我们也鼓励你在二周目的时候选择不同的ISA进行新的攻略, 这样你也许就能对不同ISA之间的区别有更深刻的体会了.

如果你读过上文的扩展阅读材料中关于RISC与CISC融为一体的故事, 你也许会记得CISC风格的x86指令最终被分解成RISC风格的微指令在计算机中运行, 才让x86在这场扩日持久的性能大战中得以存活下来的传奇. NEMU在经历了第二次重构之后, 也终于引入了RISC风格的RTL来实现指令, 这也许是冥冥之中的安排吧.

RTFSC理解指令执行的过程

这一小节的细节非常多, 你可能需要多次阅读讲义和代码才能理解每一处细节. 根据往届学长学姐的反馈, 一种有效的理解方法是通过做笔记的方式来整理这些细节. 事实上, 配合GDB食用效果更佳.

为了避免你长时间对代码的理解没有任何进展, 我们就增加一道必答题吧:

请整理一条指令在NEMU中的执行过程.

除了nemu/src/devicenemu/src/isa/$ISA/system之外, NEMU的其它代码你都已经有能力理解了. 因此不要觉得讲义中没有提到的文件就不需要看, 尝试尽可能地理解每一处细节吧! 在你遇到bug的时候, 这些细节就会成为帮助你调试的线索.

运行第一个C程序

说了这么多, 现在到了动手实践的时候了. 首先克隆一个新的子项目am-kernels(你可能已经在PA1中克隆这个子项目了), 里面包含了一些测试程序:

cd ics2021
bash init.sh am-kernels

你在PA2的第一个任务, 就是实现若干条指令, 使得第一个简单的C程序可以在NEMU中运行起来. 这个简单的C程序是am-kernels/tests/cpu-tests/tests/dummy.c, 它什么都不做就直接返回了.

准备交叉编译环境

如果你选择的ISA不是x86, 你还需要准备相应的gcc和binutils, 才能正确地进行编译.

  • mips32
    • apt-get install g++-mips-linux-gnu binutils-mips-linux-gnu
  • riscv32(64)
    • apt-get install g++-riscv64-linux-gnu binutils-riscv64-linux-gnu

am-kernels/tests/cpu-tests/目录下键入

make ARCH=$ISA-nemu ALL=dummy run

编译dummy程序, 并启动NEMU运行它.

修复riscv32编译错误

如果你选择的是riscv32, 并在编译dummy程序时报告了如下错误:

/usr/riscv64-linux-gnu/include/bits/wordsize.h:28:3: error: #error "rv32i-based targets are not supported"

则需要使用sudo权限修改以下文件:

--- /usr/riscv64-linux-gnu/include/bits/wordsize.h
+++ /usr/riscv64-linux-gnu/include/bits/wordsize.h
@@ -25,5 +25,5 @@
 #if __riscv_xlen == 64
 # define __WORDSIZE_TIME64_COMPAT32 1
 #else
-# error "rv32i-based targets are not supported"
+# define __WORDSIZE_TIME64_COMPAT32 0
 #endif

如果报告的是如下错误:

/usr/riscv64-linux-gnu/include/gnu/stubs.h:8:11: fatal error: gnu/stubs-ilp32.h: No such file or directory

则需要使用sudo权限修改以下文件:

--- /usr/riscv64-linux-gnu/include/gnu/stubs.h
+++ /usr/riscv64-linux-gnu/include/gnu/stubs.h
@@ -5,5 +5,5 @@
 #include <bits/wordsize.h>

 #if __WORDSIZE == 32 && defined __riscv_float_abi_soft
-# include <gnu/stubs-ilp32.h>
+//# include <gnu/stubs-ilp32.h>
 #endif

事实上, 并不是每一个程序都可以在NEMU中运行, abstract-machine子项目专门用于编译出能在NEMU中运行的程序, 我们在下一小节中会再来介绍它.

在NEMU中运行dummy程序, 你会发现NEMU输出以下信息(以riscv32为例):

invalid opcode(PC = 0x80000000):
        13 04 00 00 17 91 00 00 ...
        00000413 00009117...
There are two cases which will trigger this unexpected exception:
1. The instruction at PC = 0x80000000 is not implemented.
2. Something is implemented incorrectly.
Find this PC(0x80000000) in the disassembling result to distinguish which case it is.

If it is the first case, see
       _                         __  __                         _ 
      (_)                       |  \/  |                       | |
  _ __ _ ___  ___ ________   __ | \  / | __ _ _ __  _   _  __ _| |
 | '__| / __|/ __|______\ \ / / | |\/| |/ _` | '_ \| | | |/ _` | |
 | |  | \__ \ (__        \ V /  | |  | | (_| | | | | |_| | (_| | |
 |_|  |_|___/\___|        \_/   |_|  |_|\__,_|_| |_|\__,_|\__,_|_|

for more details.

If it is the second case, remember:
* The machine is always right!
* Every line of untested code is always wrong!

这是因为你还没有实现0x00000413的指令, 因此, 你需要开始在NEMU中添加指令了.

为什么执行了未实现指令会出现上述报错信息

RTFSC, 理解执行未实现指令的时候, NEMU具体会怎么做.

要实现哪些指令才能让dummy在NEMU中运行起来呢? 答案就在其反汇编结果(am-kernels/tests/cpu-tests/build/dummy-$ISA-nemu.txt)中: 你只需实现那些之前还没实现的指令就可以了.

交叉编译工具链

如果你选择的ISA不是x86, 在查看客户程序的二进制信息(如objdump, readelf等)时, 需要使用相应的交叉编译版本, 如mips-linux-gnu-objdmup, riscv64-linux-gnu-readelf等. 特别地, 如果你选择的ISA是riscv32, 也可以使用riscv64为前缀的交叉编译工具链.

这里要再次强调, 你务必通过RTFM来查阅指令的功能, 不能想当然. 手册中给出了指令功能的完整描述(包括做什么事, 怎么做的, 有什么影响), 一定要仔细阅读其中的每一个单词, 对指令功能理解错误和遗漏都会给以后的调试带来巨大的麻烦.

再提供一些x86的提示吧
  • call: call指令有很多形式, 不过在PA中只会用到其中的几种, 现在只需要实现CALL rel32的形式就可以了. 至于跳转地址, 框架代码里面已经有不少提示了, 也就算作是RTFSC的一个练习吧.
  • push: 现在只需要实现PUSH r32PUSH imm32的形式就可以了, 它们可以很容易地通过rtl_push来实现
  • sub: 在实现sub指令之前, 你首先需实现EFLAGS寄存器. 你只需要在寄存器结构体中添加EFLAGS寄存器即可. EFLAGS是一个32位寄存器, 但在NEMU中, 我们只会用到EFLAGS中以下的5个位: CF, ZF, SF, IF, OF, 它们的功能可暂不实现. 关于EFLAGS中每一位的含义, 请查阅i386手册. 实现了EFLAGS寄存器之后, 再实现相关的RTL指令, 之后你就可以通过这些RTL指令来实现sub指令了
  • xor, ret: RTFM吧
运行第一个客户程序

在NEMU中通过RTL指令实现上文提到的指令, 具体细节请务必参考手册. 实现成功后, 在NEMU中运行客户程序dummy, 你将会看到HIT GOOD TRAP的信息. 如果你没有看到这一信息, 说明你的指令实现不正确, 你可以使用PA1中实现的简易调试器帮助你调试.

温馨提示

PA2阶段1到此结束.

results matching ""

    No results matching ""