程序, 运行时环境与AM

运行时环境

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

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

当然, 我们先来考虑最简单的运行时环境是什么样的. 换句话说, 为了运行最简单的程序, 我们需要提供什么呢? 其实答案已经在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(软件)之间的桥梁来支撑程序的运行, 是"理解程序如何在计算机上运行"这一终极目标的不二选择.

AM的诞生和Project-N的故事

在AM诞生之前, Project-N的各个主要部件就已经存在了:

  • NEMU - NJU EMUlator (系统基础实验)
  • Nanos - Nanjing U OS (操作系统实验)
  • NOOP - NJU Out-of-Order Processor (组成原理实验)
  • NCC - NJU C Compiler (编译原理实验)

但我们一直没想好, 如何把这些部件集成到一个完整的教学生态系统中.

在2017年春季的计算机系统综合实验课程中, jyy首先提出AM的思想, 把程序和架构解耦. 解耦之后, AM就成了Project-N的一把关键的钥匙: 只要实现了AM, 我们就可以在NEMU和NOOP上运行各种AM程序; 只要在AM上实现Nanos, 我们就可以把Nanos运行在NEMU和NOOP上; 只要NCC把程序编译到AM上, 我们就可以在NOOP上运行NCC编译的程序.

经过几个月的尝试, 我们很快就相信, 这条路是对的. 于是临时决定将2017年秋季的PA进行大改版, 借鉴AM的思想来设计开发NEMU, 期望大家能更好地理解"程序如何在计算机上运行". 因此2017年秋季版本的NEMU, 也算是第一次正式作为一个子项目收录到Project-N教学生态系统中.

我们已经连续两年组队参加计算机系统设计大赛"龙芯杯", 在大赛上展示我们独有的Project-N生态系统, 均获得第二名的好成绩. 我们在大赛中探索出来的好方法, 也会反馈到PA中. 这些离你其实并不遥远, 我们在PA中传递出来的做事方法和原则, 都是大赛得奖的黄金经验.

如果你对AM和Project-N感兴趣, 欢迎联系jyy或yzh.

穿越时空的羁绊

有了AM, 我们就可以把课程之间的实验打通, 做一些以前做不到的有趣的事情了. 比如今年春季的操作系统课上, 你的学长学姐在AM上编写了他们自己的小游戏. 在今年PA的后期, 你将有机会把学长学姐们编写的游戏无缝地移植到NEMU上, 作为最终系统展示的一部分, 想想都是一件激动人心的事情.

为什么要有AM? (建议二周目思考)

操作系统也有自己的运行时环境. AM和操作系统提供的运行时环境有什么不同呢? 为什么会有这些不同?

RTFSC(3)

我们来简单介绍一下AM项目的代码. 代码中nexus-am/目录下的源文件组织如下(部分目录下的文件并未列出):

nexus-am
├── am                               # AM相关
│   ├── am.h
│   ├── amdev.h
│   ├── amtrace.h
│   ├── arch                         # 编译AM代码, 构建/运行二进制文件/镜像的Makefile
│   │   ├── isa
│   │   │   ├── mips32.mk
│   │   │   ├── riscv32.mk
│   │   │   └── x86.mk
│   │   ├── mips32-nemu.mk
│   │   ├── native.mk
│   │   ├── platform
│   │   │   └── nemu.mk
│   │   ├── riscv32-nemu.mk
│   │   └── x86-nemu.mk
│   ├── include
│   ├── Makefile
│   └── src
│       ├── mips32
│       │   └── nemu                 # mips32-nemu的实现
│       │       ├── boot
│       │       │   ├── loader.ld
│       │       │   └── start.S      # 程序入口
│       │       ├── cte.c            # CTE
│       │       ├── trap.S
│       │       └── vme.c            # VME
│       ├── native
│       ├── nemu-common
│       │   ├── ioe.c                # IOE
│       │   ├── nemu-input.c
│       │   ├── nemu-timer.c
│       │   ├── nemu-video.c
│       │   └── trm.c                # TRM
│       ├── riscv32
│       │   └── nemu                 # riscv32-nemu的实现
│       └── x86
│           └── nemu                 # x86-nemu的实现
├── apps                             # 直接运行在AM上的应用
├── libs                             # 可以直接运行在AM上的库
├── Makefile
├── Makefile.app
├── Makefile.check
├── Makefile.compile
├── Makefile.lib
├── README.md                        # ???
└── tests                            # 直接运行在AM上的测试

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

  • nexus-am/am/ - 不同架构的AM API实现, 目前我们只需要关注nexus-am/am/src/$ISA/nemu/以及相应的头文件即可
  • nexus-am/tests/和nexus-am/apps/ - 一些功能测试和直接运行在AM上的应用程序
  • nexus-am/libs/ - 一些架构无关的函数库, 方便应用程序的开发

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

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

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

最后来看看_halt(). _halt()里面调用了nemu_trap()宏(在nexus-am/am/include/nemu.h中定义), 这个宏展开之后是一条内联汇编语句, 内联汇编语句允许我们在C代码中嵌入汇编语句, 显然, 这个宏的定义是和ISA相关的. 同时, 这条指令和我们常见的汇编指令不一样(例如movl $1, %eax), 它是直接通过指令的二进制编码给出的. 如果你在nemu/src/isa/$ISA/exec/exec.c中查看opcode_table, 你会发现, 这条指令正是那条特殊的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中的执行辅助函数nemu_trap()对应起来了: cpu.eax中的值将会作为程序结束的返回值传给NEMU的monitor, monitor将会根据这个返回值来报告程序结束的原因. 此外, volatile是C语言的一个关键字, 如果你想了解关于volatile的更多信息, 请查阅相关资料.

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

解决这个问题的方法是交叉编译. 我们需要在GNU/Linux下根据AM的运行时环境编译出能够在$ISA-nemu这个新环境中运行的可执行文件. 为了不让链接器ld使用默认的方式链接, 我们还需要提供描述$ISA-nemu的运行时环境的链接脚本. AM的框架代码已经把相应的配置准备好了:

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

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

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

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

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

运行更多的程序

未测试代码永远是错的, 你需要足够多的测试用例来测试你的NEMU. 我们在nexus-am/tests/cputest/目录下准备了一些简单的测试用例. 首先我们让AM项目上的程序默认编译到$ISA-nemu的AM中:

--- nexus-am/Makefile.check
+++ nexus-am/Makefile.check
@@ -12,2 +12,2 @@
 ## Check: Environment variable $ARCH must be in the supported list
-ARCH ?= native
+ARCH ?= $ISA-nemu

然后在nexus-am/tests/cputest/目录下执行

make ALL=xxx run

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

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

make ALL=xxx gdb
阅读Makefile

nexus-am项目的Makefile设计得非常巧妙, 你需要把它们看成一种代码来RTFSC, 从而理解它们是如何工作的. 这样一来, 你就知道怎么编写有一定质量的Makefile了; 同时, 如果哪天Makefile出现了非预期的行为, 你就可以尝试对Makefile进行调试了. 当然, 这少不了RTFM.

实现更多的指令

你需要实现更多的指令, 以通过上述测试用例.

你可以自由选择按照什么顺序来实现指令. 经过PA1的训练之后, 你应该不会实现所有指令之后才进行测试了. 要养成尽早做测试的好习惯, 一般原则都是"实现尽可能少的指令来进行下一次的测试". 你不需要实现所有指令的所有形式, 只需要通过这些测试即可. 如果将来仍然遇到了未实现的指令, 就到时候再实现它们.

框架代码已经实现了部分指令, 但并没有填写opcode_table. 此外, 部分函数的功能也并没有完全实现好(框架代码中已经插入了TODO()作为提示), 你还需要编写相应的功能.

由于string和hello-str还需要实现额外的内容才能运行(具体在下文介绍), 目前可以先使用其它测试用例进行测试.

不要以为只需要在TODO处写代码

过去经常有同学认为, "我只需要在出现TODO的地方写代码就可以了, 如果一个功能在框架代码中没有相应的TODO, 它就是超出必做内容的范围, 我不需要实现."

在PA中, 这种想法是错误的. 如果你RTFSC, 你会发现TODO()只是个宏, 展开之后会调用panic(). 框架代码中的TODO更多地是在NEMU运行的时候给出可读性更好的结果(如xxx未实现), 而不是让NEMU触发让你畏惧的段错误.

我们希望你可以放弃"讲义和框架代码会把我应该做的一切细节告诉我"的幻想, 为自己承担起"理解整个系统工作原理"的责任, 而不是成为框架代码的奴仆. 因此, 当你疑惑一个功能是否需要实现时, 你不应该通过框架代码中是否有TODO来进行判断, 而是应该根据你对代码的理解和当下的需求来做决定.

x86的坑 - push imm8指令行为补充

需要注意的是, push imm8指令需要对立即数进行符号扩展, 这一点在i386手册中并没有明确说明. 在IA-32手册中关于push指令有如下说明:

If the source operand is an immediate and its size is less than the operand size, a sign-extended value is pushed on the stack.

mips32的分支延迟槽

为了提升处理器的性能, mips使用了一种叫分支延迟槽的技术. 采用这种技术之后, 程序的执行顺序会发生一些改变: 我们把紧跟在跳转指令(包括有条件和无条件)之后的静态指令称为延迟槽, 那么程序在执行完跳转指令后, 会先执行延迟槽中的指令, 再执行位于跳转目标的指令. 例如

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

若beq指令的执行结果为跳转, 则相应的动态指令流为100 -> 101 -> 200; 若beq指令的执行结果为不跳转, 则相应的动态指令流为100 -> 101 -> 102; 而对于j指令, 相应的动态指令流为201 -> 202 -> 102.

你一定会对这种反直觉的技术如何提升处理器性能而感到疑惑. 不过这需要你先了解一些微结构的知识, 例如处理器流水线, 但这已经超出了ICS的课程范围了, 所以我们也不详细解释了, 感兴趣的话可以STFW.

但我们可以知道, 延迟槽技术需要软硬件协同才能正确工作: mips手册中描述了这一约定, 处理器设计者按照这一约定设计处理器, 而编译器开发者则会让编译器负责在延迟槽中放置一条有意义的指令, 使得无论是否跳转, 按照这一约定的执行顺序都能得到正确的执行结果.

如果你是编译器开发者, 你将会如何寻找合适的指令放到延迟槽中呢?

mips32-NEMU的分支延迟槽

既然mips有这样的约定, 而编译器也已经遵循这一约定, 那么对于mips32编译器生成的程序, 我们也应该遵循这一约定来解释其语义. 这意味着, mips32-NEMU作为一个模拟的mips32 CPU, 也需要实现分支延迟槽技术, 才能正确地支撑mips32程序的运行.

事实上, gcc为mips32程序的生成提供了一个-fno-delayed-branch的编译选项, 让mips32程序中的延迟槽中都放置nop指令. 这样以后, 执行跳转指令之后, 接下来就可以直接执行跳转目标的指令了, 因为延迟槽中都是nop指令, 就算不执行它, 也不会影响程序的正确性.

在AM中, Makefile已经添加了这一编译选项, 于是我们在实现mips32-NEMU的时候就可以进行简化, 无需实现分支延迟槽了.

对PA来说, 去掉延迟槽还有其它的好处, 我们会在后续内容中进行讨论.

指令名对照

AT&T格式反汇编结果中的少量指令, 与手册中列出的指令名称不符, 如x86的cltd, mips32和riscv32则有不少伪指令(pseudo instruction). 除了STFW之外, 你有办法在手册中找到对应的指令吗? 如果有的话, 为什么这个办法是有效的呢?

实现常用的库函数

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

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

一种好的做法是, 把运行时环境分成两部分: 一部分是架构相关的运行时环境, 也就是我们之前介绍的AM; 另一部分是架构无关的运行时环境, 类似memcpy()这种常用的函数应该归入这部分. 所以nexus-am/libs/用于收录架构无关的库函数.

在PA中, 我们只要关注nexus-am/libs/klib/就可以了. klib是kernel library的意思, 用于提供一些兼容libc的基础功能. 框架代码在nexus-am/libs/klib/src/string.c和nexus-am/libs/klib/src/stdio.c 中列出了将来可能会用到的库函数, 但并没有提供相应的实现.

Bug修复

我们修复了nexus-am和navy-apps中git无法跟踪代码变动的问题. 如果你在2019/10/22 22:00:00之前获取框架代码, 请根据这个页面和这个页面更新相关文件.

实现字符串处理函数

根据需要实现nexus-am/libs/klib/src/string.c中列出的字符串处理函数, 让测试用例string可以成功运行. 关于这些库函数的具体行为, 请务必RTFM.

免责声明

有一些库函数可能在将来才会使用, 目前你可以选择暂时不实现它们. 但如果将来你因为忘记实现它们而导致程序出错时, 请不要抱怨讲义没有提醒你什么时候应该去实现哪个库函数.

这其实是一个代码管理的问题, 在项目中, 这种情况还是比较常见的. 比如你一下子定义了一堆API, 但不一定来得及马上把它们全部实现. 反过来, 你应该思考, 有没有更好的方法可以在你用到某个没有实现的函数的时候提醒你, 而不是让你经历一段没有必要的调试过程才发现竟然是个让你哭笑不得的原因呢?

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

实现sprintf

实现nexus-am/libs/klib/src/stdio.c中的sprintf(), 具体行为可以参考man 3 printf. 目前你只需要实现%s和%d就能通过hello-str的测试了, 其它功能(包括位宽, 精度等)可以在将来需要的时候再自行实现.

results matching ""

    No results matching ""