程序, 运行时环境与AM

运行时环境

你已经成功在TRM上运行dummy程序了, 然而这个程序什么都没做就结束了, 一点也不过瘾啊. 为了让NEMU支持大部分程序的运行, 你还需要实现更多的指令. 但并不是有了足够的指令就能运行更多的程序. 我们之前提到"并不是每一个程序都可以在NEMU中运行", 现在我们来解释一下背后的缘由.

从直觉上来看, 让仅仅只会"计算"的TRM来支撑一个功能齐全的操作系统的运行还是不太现实的. 这给我们的感觉就是, 计算机也有一定的"功能强弱"之分, 计算机越"强大", 就能跑越复杂的程序. 换句话说, 程序的运行其实是对计算机的功能有需求的. 在你运行Hello World程序时, 你敲入一条命令(或者点击一下鼠标), 程序就成功运行了, 但这背后其实隐藏着操作系统开发者和库函数开发者的无数汗水. 一个事实是, 应用程序的运行都需要运行时环境的支持, 包括加载, 销毁程序, 以及提供程序运行时的各种动态链接库(你经常使用的库函数就是运行时环境提供的)等. 为了让客户程序在NEMU中运行, 现在轮到你来提供相应的运行时环境的支持了.

根据KISS法则, 我们先来考虑最简单的运行时环境是什么样的. 换句话说, 为了运行最简单的程序, 我们需要提供什么呢? 其实答案已经在PA1中了: 只要把程序放在正确的内存位置, 然后让PC指向第一条指令, 计算机就会自动执行这个程序, 永不停止.

不过, 虽然计算机可以永不停止地执行指令, 但一般的程序都是会结束的, 所以运行时环境需要向程序提供一种结束运行的方法. 聪明的你已经能想到, 我们在PA1中提到的那条人工添加的nemu_trap指令, 就是让程序来结束运行的.

所以, 只要有内存, 有结束运行的方式, 加上实现正确的指令, 就可以支撑最简单程序的运行了. 而这, 也可以算是最简单的运行时环境了.

将运行时环境封装成库函数

我们刚才讨论的运行时环境是直接位于计算机硬件之上的, 因此运行时环境的具体实现, 也是和架构相关的. 我们以"ISA-平台"的二元组来表示一个架构, 例如mips32-nemu. 以程序结束为例, NEMU中是使用人为添加的nemu_trap指令, 而不同ISA的nemu_trap指令的格式肯定不同; 但如果我们自己用verilog设计了一个riscv32 CPU, 这个riscv32-mycpu的架构, 有可能是通过一条mycpu_trap指令来结束程序, 它和nemu_trap指令有很大概率是不一样的. 而结束运行是程序共有的需求, 为了让n个程序运行在m个架构上, 难道我们要维护n*m份代码? 有没有更好的方法呢?

对于同一个程序, 如果能把m个版本不同的部分都转换成相同的代码, 我们就只需要维护一个版本就可以了. 而实现这个目标的杀手锏, 就是你在程序设计课上学过的抽象! 我们只需要定义一个结束程序的API, 比如void halt(), 它对不同架构上程序的不同结束方式进行了抽象: 程序只要调用halt()就可以结束运行, 而不需要关心自己运行在哪一个架构上. 经过抽象之后, 之前m个版本的程序, 现在都统一通过halt()来结束运行, 我们就只需要维护这一个通过halt()来结束运行的版本就可以了. 然后, 不同的架构分别实现自己的halt(), 就可以支撑n个程序的运行! 这样以后, 我们就可以把程序和架构解耦了: 我们只需要维护n+m份代码(n个程序和m个架构相关的halt()), 而不是之前的n*m.

这个例子也展示了运行时环境的一种普遍的存在方式: 库. 通过库, 运行程序所需要的公共要素被抽象成API, 不同的架构只需要实现这些API, 也就相当于实现了支撑程序运行的运行时环境, 这提升了程序开发的效率: 需要的时候只要调用这些API, 就能使用运行时环境提供的相应功能.

AM - 裸机(bare-metal)运行时环境

一方面, 正如上文提到, 应用程序的运行都需要运行时环境的支持; 另一方面, 只进行纯粹计算任务的程序在TRM上就可以运行, 更复杂的应用程序对运行时环境必定还有其它的需求: 例如你之前玩的超级玛丽需要和用户进行交互, 至少需要运行时环境提供输入输出的支持. 要运行一个现代操作系统, 还要在此基础上加入更高级的功能.

如果我们把这些需求都收集起来, 将它们抽象成统一的API提供给程序, 这样我们就得到了一个可以支撑各种程序运行在各种架构上的库了! 具体地, 每个架构都按照它们的特性实现这组API; 应用程序只需要直接调用这组API即可, 无需关心自己将来运行在哪个架构上. 由于这组统一抽象的API代表了程序运行对计算机的需求, 所以我们把这组API称为抽象计算机.

AM(Abstract machine)项目就是这样诞生的. 作为一个向程序提供运行时环境的库, AM根据程序的需求把库划分成以下模块

AM = TRM + IOE + CTE + VME + MPE

• TRM(Turing Machine) - 图灵机, 最简单的运行时环境, 为程序提供基本的计算能力
• IOE(I/O Extension) - 输入输出扩展, 为程序提供输出输入的能力
• CTE(Context Extension) - 上下文扩展, 为程序提供上下文管理的能力
• VME(Virtual Memory Extension) - 虚存扩展, 为程序提供虚存管理的能力
• MPE(Multi-Processor Extension) - 多处理器扩展, 为程序提供多处理器通信的能力 (MPE超出了ICS课程的范围, 在PA中不会涉及)

AM给我们展示了程序与计算机的关系: 利用计算机硬件的功能实现AM, 为程序的运行提供它们所需要的运行时环境. 感谢AM项目的诞生, 让NEMU和程序的界线更加泾渭分明, 同时使得PA的流程更加明确:

(在NEMU中)实现硬件功能 -> (在AM中)提供运行时环境 -> (在APP层)运行程序
(在NEMU中)实现更强大的硬件功能 -> (在AM中)提供更丰富的运行时环境 -> (在APP层)运行更复杂的程序

这个流程其实与PA1中开天辟地的故事遥相呼应: 先驱希望创造一个计算机的世界, 并赋予它执行程序的使命. 亲自搭建NEMU(硬件)和AM(软件)之间的桥梁来支撑程序的运行, 是"理解程序如何在计算机上运行"这一终极目标的不二选择.

RTFSC(3)

你已经在PA0的最后获得了AM的子项目abstract-machine, 下面我们来简单介绍一下AM项目的代码. 代码中abstract-machine/目录下的源文件组织如下(部分目录下的文件并未列出):

abstract-machine
├── am                                  # AM相关
│   ├── include
│   │   ├── amdev.h
│   │   ├── am.h
│   │   └── arch                        # 架构相关的头文件定义
│   ├── Makefile
│   └── src
│       ├── native
│       ├── nemu                        # 以NEMU为平台的AM实现
│       │   ├── include
│       │   │   └── nemu.h
│       │   ├── ioe                     # IOE
│       │   │   ├── audio.c
│       │   │   ├── gpu.c
│       │   │   ├── input.c
│       │   │   ├── ioe.c
│       │   │   └── timer.c
│       │   ├── isa
│       │   │   ├── mips32              # mips32相关的实现
│       │   │   │   ├── boot
│       │   │   │   │   ├── loader.ld   # 链接脚本
│       │   │   │   │   └── start.S     # 程序入口
│       │   │   │   ├── cte.c           # CTE
│       │   │   │   ├── trap.S
│       │   │   │   └── vme.c           # VME
│       │   │   ├── riscv32             # riscv32相关的实现
│       │   │   ├── riscv64             # riscv64相关的实现
│       │   │   └── x86                 # x86相关的实现
│       │   ├── mpe.c                   # MPE, 当前为空
│       │   ├── scripts
│       │   │   └── section.ld          # 链接脚本
│       │   └── trm.c                   # TRM
│       ├── riscv32.h
│       ├── riscv64.h
│       └── x86.h
├── klib                                # 常用函数库
├── Makefile                            # 公用的Makefile规则
└── scripts                             # 构建/运行二进制文件/镜像的Makefile
    ├── isa
    │   ├── mips32.mk
    │   ├── riscv32.mk
    │   ├── riscv64.mk
    │   └── x86.mk
    ├── mips32-nemu.mk
    ├── native.mk
    ├── platform
    │   └── nemu.mk
    ├── riscv32-nemu.mk
    ├── riscv64-nemu.mk
    └── x86-nemu.mk

整个AM项目分为两大部分:

• abstract-machine/am/ - 不同架构的AM API实现, 目前我们只需要关注NEMU相关的内容即可. 此外, abstract-machine/am/include/am.h列出了AM中的所有API, 我们会在后续逐一介绍它们.
• abstract-machine/klib/ - 一些架构无关的库函数, 方便应用程序的开发

阅读abstract-machine/am/src/nemu/trm.c中的代码, 你会发现只需要实现很少的API就可以支撑起程序在TRM上运行了:

• Area heap结构用于指示堆区的起始和末尾
• void putch(char ch)用于输出一个字符
• void halt(int code)用于结束程序的运行
• void _trm_init()用于进行TRM相关的初始化工作

堆区是给程序自由使用的一段内存区间, 为程序提供动态分配内存的功能. TRM的API只提供堆区的起始和末尾, 而堆区的分配和管理需要程序自行维护. 当然, 程序也可以不使用堆区, 例如dummy. 把putch()作为TRM的API是一个很有趣的考虑, 我们在不久的将来再讨论它, 目前我们暂不打算运行需要调用putch()的程序.

最后来看看halt(). halt()里面调用了nemu_trap()宏(在abstract-machine/am/src/nemu/include/nemu.h中定义), 这个宏展开之后是一条内联汇编语句, 内联汇编语句允许我们在C代码中嵌入汇编语句, 显然, 这个宏的定义是和ISA相关的. 同时, 这条指令和我们常见的汇编指令不一样(例如movl $1, %eax), 它是直接通过指令的二进制编码给出的. 如果你查看nemu/src/isa/$ISA/exec/exec.c, 你会发现, 这条指令正是那条特殊的nemu_trap! 这其实也说明了为什么要通过编码来给出这条指令, 以x86为例, 如果你使用以下方式来给出指令, 汇编器将会报错:

asm volatile("nemu_trap" : : "a" (0))

因为这条特殊的指令是我们人为添加的, 标准的汇编器并不能识别它. 如果你查看objdump的反汇编结果, 你会看到nemu_trap指令被标识为(bad), 原因是类似的: objdump并不能识别我们人为添加的nemu_trap指令. "a"(0)是x86的专用记号, 表示在执行内联汇编语句给出的汇编代码之前, 先将0读入%eax寄存器. 这样, 这段汇编代码的功能就和nemu/src/isa/x86/exec/special.c中的执行辅助函数exec_nemu_trap()对应起来了: cpu.eax中的值将会作为程序结束的返回值传给NEMU的monitor, monitor将会根据这个返回值来报告程序结束的原因. 此外, volatile是C语言的一个关键字, 如果你想了解关于volatile的更多信息, 请查阅相关资料.

am-kernels子项目用于收录一些可以在AM上运行的测试集和简单程序:

am-kernels
├── benchmarks                  # 可用于衡量性能的基准测试程序
│   ├── coremark
│   ├── dhrystone
│   └── microbench
├── kernels                     # 可展示的应用程序
│   ├── hello
│   ├── litenes                 # 简单的NES模拟器
│   ├── slider                  # 简易图片浏览器
│   ├── thread-os               # 内核线程操作系统
│   └── typing-game             # 打字小游戏
└── tests                       # 一些具有针对性的测试集
    ├── am-tests                # 针对AM API实现的测试集
    └── cpu-tests               # 针对CPU指令实现的测试集

在让NEMU运行客户程序之前, 我们需要将客户程序的代码编译成可执行文件. 需要说明的是, 我们不能使用gcc的默认选项直接编译, 因为默认选项会根据GNU/Linux的运行时环境将代码编译成运行在GNU/Linux下的可执行文件. 但此时的NEMU并不能为客户程序提供GNU/Linux的运行时环境, 在NEMU中无法正确运行上述可执行文件, 因此我们不能使用gcc的默认选项来编译用户程序.

解决这个问题的方法是交叉编译. 我们需要在GNU/Linux下根据AM的运行时环境编译出能够在$ISA-nemu这个新环境中运行的可执行文件. 为了不让链接器ld使用默认的方式链接, 我们还需要提供描述$ISA-nemu的运行时环境的链接脚本. AM的框架代码已经把相应的配置准备好了, 上述编译和链接选项主要位于abstract-machine/Makefile 以及abstract-machine/scripts/目录下的相关.mk文件中. 编译生成一个可以在NEMU的运行时环境上运行的程序的过程大致如下:

• gcc将$ISA-nemu的AM实现源文件编译成目标文件, 然后通过ar将这些目标文件作为一个库, 打包成一个归档文件abstract-machine/am/build/am-$ISA-nemu.a
• gcc把应用程序源文件(如am-kernels/tests/cpu-tests/tests/dummy.c)编译成目标文件
• 通过gcc和ar把程序依赖的运行库(如abstract-machine/klib/)也编译并打包成归档文件
• 根据Makefile文件abstract-machine/scripts/$ISA-nemu.mk中的指示, 让ld根据链接脚本abstract-machine/am/src/nemu/isa/$ISA/boot/loader.ld, 将上述目标文件和归档文件链接成可执行文件

上述链接脚本会包含位于abstract-machine/am/src/nemu/scripts/section.ld的另一个链接脚本. 根据它的指示, 可执行程序重定位后的节从0x100000或0x80100000开始(取决于_pmem_start的值), 首先是.text节, 其中又以abstract-machine/am/src/nemu/isa/$ISA/boot/start.S中自定义的entry节开始, 然后接下来是其它目标文件的.text节. 这样, 可执行程序起始处总是放置start.S的代码, 而不是其它代码, 保证客户程序总能从start.S开始正确执行. 链接脚本也定义了其它节(包括.rodata, .data, .bss)的链接顺序, 还定义了一些关于位置信息的符号, 包括每个节的末尾, 栈顶位置, 堆区的起始和末尾.

我们对编译得到的可执行文件的行为进行简单的梳理:

1. 第一条指令从abstract-machine/am/src/nemu/isa/$ISA/boot/start.S开始, 设置好栈顶之后就跳转到abstract-machine/am/src/nemu/trm.c的_trm_init()函数处执行.
2. 在_trm_init()中调用main()函数执行程序的主体功能, main()函数还带一个参数, 目前我们暂时不会用到, 后面我们再介绍它.
3. 从main()函数返回后, 调用halt()结束运行.

有了TRM这个简单的运行时环境, 我们就可以很容易地在上面运行各种"简单"的程序了. 当然, 我们也可以运行"不简单"的程序: 我们可以实现任意复杂的算法, 甚至是各种理论上可计算的问题, 都可以在TRM上解决.

运行更多的程序

未测试代码永远是错的, 你需要足够多的测试用例来测试你的NEMU. 我们在am-kernels/tests/cpu-tests/目录下准备了一些简单的测试用例. 在该目录下执行

make ARCH=$ISA-nemu ALL=xxx run

其中xxx为测试用例的名称(不包含.c后缀).

上述make run的命令最终会启动NEMU, 并运行相应的客户程序. 如果你需要使用GDB来调试NEMU运行客户程序的情况, 可以执行以下命令:

make ARCH=$ISA-nemu ALL=xxx gdb

100: beq 200
101: add
102: xor
...
200: sub
201: j   102
202: slt

实现常用的库函数

我们已经在TRM上运行了不少简单的程序了, 但如果想在TRM上编写一些稍微复杂的程序, 我们就会发现有点不方便. 目前TRM这个最简单的运行时环境只提供了堆区和halt(), 但我们平时经常使用的像memcpy()这样的库函数却没有提供. 既然没有提供, 那就让我们来实现一下吧.

既然叫得起库函数, 那说明很多程序都可以用到它们, 所以我们可以像AM那样, 把它们组织成一个库. 然而和AM不同的是, 这些库函数的具体实现可以是和架构无关的: 与halt()不同, 在NEMU上, 或者在你将来用verilog实现的CPU上, 甚至是其它的架构, memcpy()都可以通过相同的方式来实现. 所以, 如果在AM中来实现这些常用的库函数, 就会引入不必要的重复代码.

一种好的做法是把运行时环境分成两部分: 一部分是架构相关的运行时环境, 也就是我们之前介绍的AM; 另一部分是架构无关的运行时环境, 类似memcpy()这种常用的函数应该归入这部分, abstract-machine/klib/用于收录这些架构无关的库函数. klib是kernel library的意思, 用于提供一些兼容libc的基础功能. 框架代码在abstract-machine/klib/src/string.c和abstract-machine/klib/src/stdio.c 中列出了将来可能会用到的库函数, 但并没有提供相应的实现.

为了运行测试用例hello-str, 你还需要实现库函数sprintf(). 和其它库函数相比, sprintf()比较特殊, 因为它的参数数目是可变的. 为了获得数目可变的参数, 你可以使用C库stdarg.h中提供的宏, 具体用法请查阅man stdarg.

重新认识计算机: 计算机是个抽象层

我们在PA1中介绍了"程序在计算机上运行"的微观视角: 程序是个状态机. 状态机视角可以从指令层次精确地描述程序运行的每一处细节, 但这丢失了程序的语义. 对于一些简单的程序, 你还可以把状态机画出来, 但面对一些复杂的程序, 状态机视角就不能帮助我们了. 为了更好地理解复杂程序, 我们需要从一个新的视角来切入.

我们先来讨论在TRM上运行的程序, 我们对这些程序的需求进行分类, 来看看我们的计算机系统是如何支撑这些需求的.

• 计算. 这是程序最基本的需求, 以至于它甚至不属于运行时环境和AM的范畴. 所有计算相关的代码(顺序语句, 分支, 循环, 函数调用等), 都会被编译器编译成功能等价的指令序列, 最终在CPU上执行. 在NEMU中, 我们通过fetch_decode_exec()这个函数以及相应的辅助函数来实现"CPU执行指令"的功能.
• 内存申请. 有的程序需要在运行时刻动态地申请内存来使用. 和libc类似, klib提供了malloc()和free()来实现内存的动态管理(你将来会实现它们), 它们又会使用TRM中提供的API heap来获得堆区的起始和末尾. 而heap的区间又是由ISA-平台这个二元组对应的物理内存地址空间来决定的. 这一地址空间对应着物理内存的大小, 在NEMU中, 它就是大数组pmem[]的大小.
• 结束运行. 一般程序都会有结束运行的时候, TRM提供了一个halt()的API来实现这一功能. 由于这个需求过于简单, 因此无需运行时环境提供更复杂的接口. halt()的具体实现和ISA有关, 我们使用了人为添加的nemu_trap指令来实现这一点. 执行nemu_trap指令会让NEMU从CPU执行指令的循环中跳出, 返回到Monitor中, 这是通过设置Monitor中的一个状态变量nemu_state来实现的.
• 打印信息. 输出是程序的另一个基本需求. 程序可以调用klib中的printf()来输出, 它会通过TRM的API putch()来输出字符. 不同的ISA-平台有不同的字符输出方式, 在$ISA-nemu中, putch()通过I/O相关的指令把字符写入到串口, 最终在NEMU中通过serial_io_handler()将字符打印到终端. 关于输入输出的更多细节会在PA2的最后部分进行介绍.