RTFM
我们在上一小节中已经在概念上介绍了一条指令具体如何执行, 其中有的概念甚至显而易见得难以展开. 不过x86这一庞然大物背负着太多历史的包袱, 但当我们决定往TRM中添加各种高效的x86指令时, 也同时意味着我们无法回避这些繁琐的细节.
首先你需要了解指令确切的行为, 为此, 你需要阅读i386手册中指令集相关的章节. 这里有一个简单的阅读教程.
i386手册勘误
RISC - 与CISC平行的另一个世界
RTFSC(2)
下面我们来介绍NEMU的框架代码是如何执行指令的.
数据结构
首先先对这个过程中的两个重要的数据结构进行说明.
nemu/src/cpu/exec/exec.c中的opcode_table数组. 这就是我们之前提到的译码查找表了, 这一张表通过操作码opcode来索引, 每一个opcode对应相应指令的译码函数, 执行函数, 以及操作数宽度.nemu/src/cpu/decode/decode.c中的decoding结构. 它用于记录一些全局译码信息供后续使用, 包括操作数的类型, 宽度, 值等信息. 其中的src成员,src2成员和dest成员分别代表两个源操作数和一个目的操作数.nemu/include/cpu/decode.h中定义了三个宏id_src,id_src2和id_dest, 用于方便地访问它们.
执行流程
然后对exec_wrapper()的执行过程进行简单介绍.
首先将当前的%eip保存到全局译码信息decoding的成员seq_eip中,
然后将其地址被作为参数送进exec_real()函数中.
seq代表顺序的意思, 当代码从exec_real()返回时, decoding.seq_eip将会指向下一条指令的地址.
exec_real()函数通过宏make_EHelper来定义:
#define make_EHelper(name) void concat(exec_, name) (vaddr_t *eip)
其含义是"定义一个执行阶段相关的helper函数", 这些函数都带有一个参数eip.
NEMU通过不同的helper函数来模拟不同的步骤.
在exec_real()中:
- 首先通过
instr_fetch()函数(在nemu/include/cpu/exec.h中定义)进行取指, 得到指令的第一个字节, 将其解释成opcode并记录在全局译码信息decoding中. - 根据
opcode查阅译码查找表, 得到操作数的宽度信息, 并通过调用set_width()函数将其记录在全局译码信息decoding中. - 调用
idex()对指令进行进一步的译码和执行
idex()函数会调用译码查找表中的相应的译码函数进行操作数的译码.
译码函数统一通过宏make_DHelper来定义(在nemu/src/cpu/decode/decode.c中):
#define make_DHelper(name) void concat(decode_, name) (vaddr_t *eip)
它们主要以i386手册附录A中的操作数表示记号来命名,
例如I2r表示将立即数移入寄存器, 其中I表示立即数, 2表示英文to, r表示通用寄存器,
更多的记号请参考i386手册.
译码函数会把指令中的操作数信息分别记录在全局译码信息decoding中.
这些译码函数会进一步分解成各种不同操作数的译码的组合, 以实现操作数译码的解耦.
操作数译码函数统一通过宏make_DopHelper来定义
(在nemu/src/cpu/decode/decode.c中, decode_op_rm()除外):
#define make_DopHelper(name) void concat(decode_op_, name) (vaddr_t *eip, Operand *op, bool load_val)
它们主要以i386手册附录A中的操作数表示记号来命名.
操作数译码函数会把操作数的信息记录在结构体op中,
如果操作数在指令中, 就会通过instr_fetch()将它们从eip所指向的内存位置取出.
为了使操作数译码函数更易于复用, 函数中的load_val参数会控制
是否需要将该操作数读出到全局译码信息decoding供后续使用.
例如如果一个内存操作数是源操作数, 就需要将这个操作数从内存中读出来供后续执行阶段来使用;
如果它仅仅是一个目的操作数, 就不需要从内存读出它的值了,
因为执行这条指令并不需要这个值, 而是将新数据写入相应的内存位置.
idex()函数中的译码过程结束之后, 会调用译码查找表中的相应的执行函数来进行真正的执行操作.
执行函数统一通过宏make_EHelper来定义, 它们的名字是指令操作本身.
执行函数通过RTL来描述指令真正的执行功能(RTL将在下文介绍).
其中operand_write()函数(在nemu/src/cpu/decode/decode.c中定义)
会根据第一个参数中记录的类型的不同进行相应的写操作, 包括写寄存器和写内存.
从idex()返回后, exec_real()也会返回到exec_wrapper()中,
最后会通过update_eip()对%eip进行更新.
上文已经把一条指令在NEMU中执行的流程进行了大概的介绍. 如果觉得上文的内容不易理解, 可以结合这个例子来RTFSC. 但这个例子中会描述较多细节, 阅读的时候需要一定的耐心.
立即数背后的故事
在decode_op_I()函数中通过instr_fetch()函数获得指令中的立即数.
别看这里就这么一行代码, 其实背后隐藏着针对字节序的慎重考虑.
我们知道x86是小端机, 当你使用高级语言或者汇编语言写了一个32位常数0x1234的时候,
在生成的二进制代码中, 这个常数对应的字节序列如下(假设这个常数在内存中的起始地址是x):
x x+1 x+2 x+3
+----+----+----+----+
| 34 | 12 | 00 | 00 |
+----+----+----+----+
而大多数PC机都是小端架构(我们相信没有同学会使用IBM大型机来做PA), 当NEMU运行的时候,
op_src->imm = instr_fetch(eip, 4);
这行代码会将34 12 00 00这个字节序列原封不动地从内存读入imm变量中,
主机的CPU会按照小端方式来解释这一字节序列, 于是会得到0x1234, 符合我们的预期结果.
Motorola 68k系列的处理器都是大端架构的. 现在问题来了, 考虑以下两种情况:
- 假设我们需要将NEMU运行在Motorola 68k的机器上(把NEMU的源代码编译成Motorola 68k的机器码)
- 假设我们需要编写一个新的模拟器NEMU-Motorola-68k, 模拟器本身运行在x86架构中, 但它模拟的是Motorola 68k程序的执行
在这两种情况下, 你需要注意些什么问题? 为什么会产生这些问题? 怎么解决它们?
事实上不仅仅是立即数的访问, 长度大于1字节的内存访问都需要考虑类似的问题. 我们在这里把问题统一抛出来, 以后就不再单独讨论了.
结构化程序设计
细心的你会发现以下规律:
- 对于同一条指令的不同形式, 它们的执行阶段是相同的.
例如
add_I2E和add_E2G等, 它们的执行阶段都是把两个操作数相加, 把结果存入目的操作数. - 对于不同指令的同一种形式, 它们的译码阶段是相同的.
例如
add_I2E和sub_I2E等, 它们的译码阶段都是识别出一个立即数和一个E操作数. - 对于同一条指令同一种形式的不同操作数宽度, 它们的译码阶段和执行阶段都是非常类似的.
例如
add_I2E_b,add_I2E_w和add_I2E_l, 它们都是识别出一个立即数和一个E操作数, 然后把相加的结果存入E操作数.
这意味着, 如果独立实现每条指令不同形式不同操作数宽度的helper函数, 将会引入大量重复的代码. 需要修改的时候, 相关的所有helper函数都要分别修改, 遗漏了某一处就会造成bug, 工程维护的难度急速上升.
Copy-Paste - 一种糟糕的编程习惯
事实上, 第一版PA发布的时候, 框架代码就恰恰是引导大家独立实现每一个helper函数.
大家在实现指令的时候, 都是把已有的代码复制好几份, 然后进行一些微小的改动(例如把<<改成>>).
当你发现这些代码有bug的时候, 噩梦才刚刚开始.
也许花了好几天你又调出一个bug的时候, 才会想起这个bug你好像之前在哪里调过.
你也知道代码里面还有类似的bug, 但你已经分辨不出哪些代码是什么时候从哪个地方复制过来的了.
由于当年的框架代码没有足够重视编程风格, 导致学生深深地陷入调试的泥淖中, 这也算是PA的一段黑历史了.
这种糟糕的编程习惯叫Copy-Paste, 经过上面的分析, 相信你也已经领略到它的可怕了. 事实上, 周圆圆教授的团队在2004年就设计了一款工具CP-Miner, 来自动检测操作系统代码中由于Copy-Paste造成的bug. 这个工具还让周圆圆教授收获了一篇系统方向顶级会议OSDI的论文, 这也是她当时所在学校UIUC史上的第一篇系统方向的顶级会议论文.
不过, 之后周圆圆教授发现, 相比于操作系统, 应用程序的源代码中Copy-Paste的现象更加普遍. 于是她们团队把CP-Miner的技术应用到应用程序的源代码中, 并创办了PatternInsight公司. 很多IT公司纷纷购买PatternInsight的产品, 并要求提供相应的定制服务.
这个故事折射出, 大公司中程序员的编程习惯也许不比你好多少, 他们也会写出Copy-Paste这种难以维护的代码. 但反过来说, 重视编码风格这些企业看中的能力, 你从现在就可以开始培养.
一种好的做法是把译码, 执行和操作数宽度的相关代码分离开来,
实现解耦, 也就是在程序设计课上提到的结构化程序设计.
在框架代码中, 实现译码和执行之间的解耦的是idex()函数,
它依次调用opcode_table表项中的译码和执行的helper函数,
这样我们就可以分别编写译码和执行的helper函数了.
实现操作数宽度和译码, 执行这两者之间的解耦的是id_src, id_src2和id_dest中的width成员,
它们记录了操作数宽度, 译码和执行的过程中会根据它们进行不同的操作,
通过同一份译码函数和执行函数实现不同操作数宽度的功能.
为了易于使用, 框架代码中使用了一些宏, 我们在这里把相关的宏整理出来, 供大家参考.
| 宏 | 含义 |
|---|---|
nemu/include/macro.h |
|
str(x) |
字符串"x" |
concat(x, y) |
tokenxy |
nemu/include/cpu/decode.h |
|
id_src |
全局变量decoding中源操作数成员的地址 |
id_src2 |
全局变量decoding中2号源操作数成员的地址 |
id_dest |
全局变量decoding中目的操作数成员的地址 |
make_Dhelper(name) |
名为decode_name的译码函数的原型说明 |
nemu/src/cpu/decode.c |
|
make_Dophelper(name) |
名为decode_op_name的操作数译码函数的原型说明 |
nemu/include/cpu/exec.h |
|
make_Ehelper(name) |
名为exec_name的执行函数的原型说明 |
print_asm(...) |
将反汇编结果的字符串打印到缓冲区decoding.assembly中 |
suffix_char(width) |
操作数宽度width对应的后缀字符 |
print_asm_template[1|2|3](instr) |
打印单/双/三目操作数指令instr的反汇编结果 |
用RTL表示指令行为
我们知道, x86指令作为一种CISC指令集, 不少指令的行为都比较复杂. 但我们会发现, i386手册会用一些更简单的操作来表示指令的具体行为. 这说明, 复杂的x86指令还是能继续分解成一些更简单的操作的组合. 如果我们先实现这些简单操作, 然后再用它们来实现x86指令, 不就可以进一步提高代码的复用率了吗?
在NEMU中, 我们使用RTL(寄存器传输语言)来描述这些简单的操作.
下面我们对NEMU中使用的RTL进行一些说明, 首先是RTL寄存器的定义.
在NEMU中, RTL寄存器统一使用rtlreg_t来定义,
而rtlreg_t(在nemu/include/common.h中定义)其实只是一个uint32_t类型:
typedef uint32_t rtlreg_t;
在NEMU中, RTL寄存器只有以下这些
- x86的八个通用寄存器(在
nemu/include/cpu/reg.h中定义) id_src,id_src2和id_dest中的访存地址addr和操作数内容val(在nemu/include/cpu/decode.h中定义). 从概念上看, 它们分别与MAR和MDR有异曲同工之妙- 临时寄存器
t0~t3和at(在nemu/src/cpu/decode/decode.c中定义)
有了RTL寄存器, 我们就可以定义RTL指令对它们进行的操作了.
在NEMU中, RTL指令有两种(在nemu/include/cpu/rtl.h中定义).
一种是RTL基本指令, 它们的特点是不需要使用临时寄存器, 可以看做是最基本的x86指令中的最基本的操作.
RTL基本指令包括(我们使用了一些简单的正则表达式记号):
- 立即数读入
rtl_li - 寄存器传输
rtl_mv - 32位寄存器-寄存器类型的算术/逻辑运算,
包括
rtl_(add|sub|and|or|xor|shl|shr|sar|i?mul_[lo|hi]|i?div_[q|r]), 这些运算的定义用到了include/util/c_op.h中的C语言运算 - 被除数为64位的除法运算
rtl_i?div64_[q|r] - guest内存访问
rtl_lm和rtl_sm - host内存访问
rtl_host_lm和rtl_host_sm - 关系运算
rtl_setrelop, 具体可参考src/cpu/exec/relop.c - 跳转, 包括直接跳转
rtl_j, 间接跳转rtl_jr和条件跳转rtl_jrelop - 终止程序
rtl_exit
上述RTL基本指令在nemu/include/cpu/rtl.h中定义时, 添加了interpret_前缀, 这是为了给PA5作准备,
在nemu/include/cpu/rtl-wrapper.h的作用下, 其它代码中使用到这些RTL基本指令时会自动添加interpret_前缀.
因此你在代码中使用它们的时候, 只需要编写rtl_xxx即可.
神秘的host内存访问 (建议二周目思考)
为什么需要有host内存访问的RTL指令呢?
第二种RTL指令是RTL伪指令, 它们是通过RTL基本指令或者已经实现的RTL伪指令来实现的, 包括:
- 32位寄存器-立即数类型的算术/逻辑运算,
包括
rtl_(add|sub|and|or|xor|shl|shr|sar|i?mul_[lo|hi]|i?div_[q|r])_i - 通用寄存器访问
rtl_lr和rtl_sr - EFLAGS标志位的读写
rtl_set_(CF|OF|ZF|SF)和rtl_get_(CF|OF|ZF|SF) - 其它常用功能, 如按位取反
rtl_not, 符号扩展rtl_sext等
其中大部分RTL伪指令还没有实现, 必要的时候你需要实现它们. 有了这些RTL指令之后, 我们就可以方便地通过若干条RTL指令来实现每一条x86指令的行为了.
小型调用约定
我们定义RTL基本指令的时候, 约定了RTL基本指令不需要使用RTL临时寄存器. 但某些RTL伪指令需要使用临时寄存器存放中间结果, 才能实现其完整功能. 这样可能会带来寄存器覆盖的问题, 例如如下RTL指令序列:
(1) rtl_mv(&t0, &t1);
(2) rtl_sext(&t1, &t2, 1); // use t0 temporarily
(3) rtl_add(&t2, &t0, &t1);
如果实现(2)的时候恰好使用到了t0作为临时寄存器, 在(3)中使用的t0就不再是(1)的结果了,
从而产生非预期的结果.
为了尽可能避免上述问题, 我们有两条约定:
- 实现RTL伪指令的时候, 尽可能不使用
dest之外的寄存器存放中间结果. 由于dest最后会被写入新值, 其旧值肯定要被覆盖, 自然也可以安全地作为RTL伪指令的临时寄存器. - 实在需要使用临时寄存器的时候, 使用
at.at全称是assembly temporary, 是MIPS ABI中定义的一个特殊寄存器: 编译器并不会使用它, 它可以在编写汇编代码的时候安全地作为可使用的临时寄存器. 在这里, 我们借鉴它的功能来作如下约定: 不要在RTL伪指令的内部实现之外使用at. 这样,at就可以安全地作为RTL伪指令的临时寄存器了.
仔细体会上述约定, 你也许会发现, 这和课上学习的调用约定有那么一点点相似之处. 如果把RTL伪指令看成一个函数调用, 我们刚才其实在讨论, 在这个"函数"里面究竟可以使用哪些RTL寄存器. 在调用约定中, 有些寄存器对被调用函数来说, 使用它们之前是需要先保存的. 但我们的RTL编程模型中并没有"栈"的概念, 所以在RTL中我们就不设置所谓的"被调用者保存寄存器"了. 从某种程度上来说, 这样的"小型调用约定"很难支撑大规模RTL指令的编写. 不过幸好, 在用RTL来实现x86指令的时候, 这一"小型调用约定"已经足够使用了.
计算机系统中的约定与未定义行为
上述例子其实折射出计算机系统工作的一种基本原则: 遵守约定.
我们定义了RTL寄存器和相应的RTL指令, 基于这些定义, 原则上可以编写出任意的RTL指令序列,
这些RTL序列最终也会按照它们原本的语义来执行.
但光靠这些定义, 我们无法避免上述RTL寄存器相互覆盖造成错误的问题.
所以我们又提出一些新的约定, 来避免这个问题.
当然, 你也可以自己提出一套新的约定(比如用t1替代上述at的作用).
违反约定会发生什么呢? 最常见的就是程序无法得到正确的结果.
比如当两套约定不兼容的RTL代码放在一起的时候, 它们都分别违反了对方的约定
(你的RTL覆盖了我的at, 我的RTL覆盖了你的t1).
当然也有可能恰好没有覆盖各自约定使用的寄存器, 撞大运地得到正确的运行结果.
总之, 违反约定的具体行为会怎么样, 还需要具体问题具体分析, 很难明确地说清楚.
既然说不清楚, 那就干脆不说吧, 于是有了未定义行为的概念: 只要遵守约定, 就能保证程序具有遵守约定后的特性; 如果违反, 不按照说好的来, 那就不保证行为是正确的.
计算机系统就是这样工作的: 计算机系统抽象层之间的接口其实也是一种约定, 比如指令就是软件和硬件的一种接口, 所以有了i386手册来规范每一条指令的行为, 编译器需要根据i386手册中的约定来生成可以正确执行的代码. 如果编译器不按照手册约定来生成代码, 那么编译出的程序的行为就是未定义的.
引入未定义行为还有一个好处是, 给约定的实现方式一定的自由度. 例如, C语言标准规定, 整数除法的除数为0时, 结果是未定义的. x86的除法指令在检测到除数为0时, 就会向CPU抛出一个异常信号. 而MIPS的除法指令则更简单暴力: 首先在MIPS指令集手册中声明, 除数为0时, 结果未定义; 然后在硬件上实现除法器的时候, 对除0操作就可以视而不见了. 然而给定一个除法器电路, 就算除数为0, 电路的输出也总会有一个值, 至于具体的值是什么, 就看造化了, 反正C语言标准规定除0的行为本身就是未定义的, 让除法指令随便返回一个值, 也不算违反约定.
未定义行为其实离你很近, 比如你经常使用的memcpy(),
如果源区间和目的区间有重叠时, 它的行为会怎么样?
如果你从来没有思考过这个问题, 你应该去man一下,
然后思考一下为什么会这样.
还有一种有人欢喜有人愁的现象是基于未定义行为的编译优化:
既然源代码的行为是未定义的, 编译器基于此进行各种奇葩优化当然也不算违反约定.
这篇文章列举了一些让你大开眼界的花式编译优化例子,
看完之后你就会刷新对程序行为的理解了.
所以这就是为什么我们强调要学会RTFM.
RTFM是了解接口行为和约定的过程: 每个输入的含义是什么? 查阅对象的具体行为是什么?
输出什么? 有哪些约束条件必须遵守? 哪些情况下会报什么错误?
只有完全理解并遵守它们, 才能正确无误地使用查阅的对象,
大至系统设计原则, 小到一个memcpy()的行为, 都蕴含着约定与遵守的法则.
理解这些法则, 也是理解计算机系统的不二途径.
RTL寄存器中值的生存期
在程序设计课上, 我们知道C语言中不同的变量有不同的生存期: 有的变量的值会一直持续到程序结束, 但有的变量却很快消亡. 在上述定义的RTL寄存器中, 其实也有不同的生存期. 尝试根据生存期给RTL寄存器分类.
尽管目前这个分类结果并没有什么用处, 但其实将来在PA5中设计RTL优化方案的时候, 生存期的性质会给我们提供很大的优化机会.
实现新指令
对译码, 执行和操作数宽度的解耦实现以及RTL的引入, 对在NEMU中实现一条新的x86指令提供了很大的便利, 为了实现一条新指令, 你只需要
- 在
opcode_table中填写正确的译码函数, 执行函数以及操作数宽度 - 用RTL实现正确的执行函数, 需要注意使用RTL伪指令时要遵守上文提到的小型调用约定
框架代码把绝大部分译码函数和执行函数都定义好了, 你可以很方便地使用它们.
如果你读过上文的扩展阅读材料中关于RISC与CISC融为一体的故事, 你也许会记得CISC风格的x86指令最终被分解成RISC风格的微指令在计算机中运行, 才让x86在这场扩日持久的性能大战中得以存活下来的故事. NEMU在经历了第二次重构之后, 也终于引入了RISC风格的RTL来实现x86指令, 这也许是冥冥之中的安排吧.
运行第一个C程序
说了这么多, 现在到了动手实践的时候了.
你在PA2的第一个任务, 就是实现若干条指令, 使得第一个简单的C程序可以在NEMU中运行起来.
这个简单的C程序的代码是nexus-am/tests/cputest/tests/dummy.c, 它什么都不做就直接返回了.
在nexus-am/tests/cputest/目录下键入
make ARCH=x86-nemu ALL=dummy run
编译dummy程序, 并启动NEMU运行它.
事实上, 并不是每一个程序都可以在NEMU中运行,
nexus-am/子项目专门用于编译出能在NEMU中运行的程序, 我们在下一小节中会再来介绍它.
在NEMU中运行dummy程序, 你会发现NEMU输出以下信息:
invalid opcode(eip = 0x0010000a): e8 01 00 00 00 90 55 89 ...
There are two cases which will trigger this unexpected exception:
1. The instruction at eip = 0x0010000a is not implemented.
2. Something is implemented incorrectly.
Find this eip value(0x0010000a) in the disassembling result to distinguish which case it is.
If it is the first case, see
_ ____ ___ __ __ __ _
(_)___ \ / _ \ / / | \/ | | |
_ __) | (_) |/ /_ | \ / | __ _ _ __ _ _ __ _| |
| ||__ < > _ <| '_ \ | |\/| |/ _ | '_ \| | | |/ _ | |
| |___) | (_) | (_) | | | | | (_| | | | | |_| | (_| | |
|_|____/ \___/ \___/ |_| |_|\__,_|_| |_|\__,_|\__,_|_|
for more details.
If it is the second case, remember:
* The machine is always right!
* Every line of untested code is always wrong!
这是因为你还没有实现以0xe8为首字节的指令, 因此, 你需要开始在NEMU中添加指令了.
要实现哪些指令才能让dummy在NEMU中运行起来呢?
答案就在其反汇编结果(nexus-am/tests/cputest/build/dummy-x86-nemu.txt)中.
查看反汇编结果, 你发现只需要添加call, push, sub, xor, pop, ret六条指令就可以了.
每一条指令还有不同的形式, 根据KISS法则, 你可以先实现只在dummy中出现的指令形式,
通过指令的opcode可以确定具体的形式.
call:call指令有很多形式, 不过在PA中只会用到其中的几种, 现在只需要实现CALL rel32的形式就可以了. 至于跳转地址, 框架代码里面已经有不少提示了, 也就算作是RTFSC的一个练习吧.push,pop: 现在只需要实现PUSH r32和POP r32的形式就可以了, 它们可以很容易地通过rtl_push和rtl_pop来实现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指令实现上文提到的指令, 具体细节请务必参考i386手册.
实现成功后, 在NEMU中运行客户程序dummy, 你将会看到HIT GOOD TRAP的信息.
温馨提示
PA2阶段1到此结束.