程序, 运行时环境与AM

运行时环境

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

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

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

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

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

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

我们刚才讨论的运行时环境是直接位于计算机硬件之上的, 因此运行时环境的具体实现, 也是和机器相关的. 以程序结束为例, NEMU中是使用人为添加的nemu_trap指令, 但如果我们自己用verilog设计了一个CPU, 有可能是通过一条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, 就能使用运行时环境提供的相应功能.

究竟有什么实质性的好处

也许上面的文字并不能"忽悠"清醒的你: 现在不就只有NEMU这一个机器吗(m=1)? 哪里需要抽象?

目前确实是这样. 但不妨思考一下, 如果有多个机器, 这样的抽象还会带来哪些好处呢? 你很快就会体会到这些好处了.

AM - 直接运行在计算机上的运行时环境

一方面, 正如上文提到, 应用程序的运行都需要运行时环境的支持; 另一方面, 只进行纯粹计算任务的程序在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的诞生和ProjectN的故事

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

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

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

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

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

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

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

穿越时空的羁绊

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

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

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

RTFSC(3)

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

nexus-am
├── am                               # AM相关
│   ├── am.h
│   ├── arch                         # 不同机器的AM实现
│   │   ├── native
│   │   └── x86-nemu                 # x86-nemu的AM实现
│   │       ├── img                  # 构建/运行二进制文件/镜像的脚本
│   │       │   ├── boot
│   │       │   │   ├── Makefile
│   │       │   │   └── start.S      # 程序入口
│   │       │   ├── build            # 构建脚本
│   │       │   ├── loader.ld        # 链接脚本
│   │       │   └── run              # 运行脚本
│   │       ├── include
│   │       ├── README.md
│   │       └── src
│   │           ├── cte.c            # CTE
│   │           ├── ioe.c            # IOE
│   │           ├── trap.S
│   │           ├── trm.c            # TRM
│   │           └── vme.c            # VME
│   └── Makefile
├── apps                             # 直接运行在AM上的应用
├── libs                             # 可以直接运行在AM上的库
├── Makefile
├── Makefile.app
├── Makefile.check
├── Makefile.compile
├── Makefile.lib
└── tests                            # 直接运行在AM上的测试

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

  • nexus-am/am - 不同机器的AM API实现, 目前我们只需要关注nexus-am/am/arch/x86-nemu即可
  • nexus-am/testsnexus-am/apps - 一些功能测试和直接运行在AM上的应用程序
  • nexus-am/libs - 一些机器无关的函数库, 方便应用程序的开发

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

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

堆区是给程序自由使用的一段内存区间, 为程序提供动态分配内存的功能. TRM的API只提供堆区的起始和末尾, 而堆区的分配和管理需要程序自行维护. 当然, 程序也可以不使用堆区, 例如dummy.

堆和栈在哪里?

我们知道代码和数据都在可执行文件里面, 但却没有提到堆(heap)和栈(stack). 为什么堆和栈的内容没有放入可执行文件里面? 那程序运行时刻用到的堆和栈又是怎么来的? AM的代码是否能给你带来一些启发?

_putc()作为TRM的API是一个很有趣的考虑, 我们在不久的将来再讨论它, 目前我们暂不打算运行需要调用_putc()的程序.

最后来看看_halt(). _halt()里面是一条内联汇编语句, 内联汇编语句允许我们在C代码中嵌入汇编语句. 这条指令和我们常见的汇编指令不一样(例如movl $1, %eax), 它是直接通过指令的编码给出的, 它只有一个字节, 就是0xd6. 如果你在nemu/src/cpu/exec/exec.c中查看opcode_table, 你会发现, 这条指令正是那条特殊的nemu_trap! 这其实也说明了为什么要通过编码来给出这条指令, 如果你使用以下方式来给出指令, 汇编器将会报错:

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

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

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

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

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

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

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

  1. 第一条指令从nexus-am/am/arch/x86-nemu/img/boot/start.S开始, 设置好栈顶之后就跳转到nexus-am/am/arch/x86-nemu/src/trm.c_trm_init()函数处执行.
  2. _trm_init()中调用main()函数执行程序的主体功能.
  3. main()函数返回后, 调用_halt()结束运行.

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

运行更多的程序

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

--- nexus-am/Makefile.check
+++ nexus-am/Makefile.check
@@ -7,2 +7,2 @@
-ARCH ?= native
+ARCH ?= x86-nemu
 ARCH = $(shell ls $(AM_HOME)/am/arch/)

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

make ALL=xxx run

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

上述make run的命令最终会调用nexus-am/am/arch/x86-nemu/img/run来启动NEMU. 为了使用GDB来调试NEMU, 你需要修改这一run脚本的内容:

--- nexus-am/am/arch/x86-nemu/img/run
+++ nexus-am/am/arch/x86-nemu/img/run
@@ -3,1 +3,1 @@
-make -C $NEMU_HOME run ARGS="-l `dirname $1`/nemu-log.txt $1.bin"
+make -C $NEMU_HOME gdb ARGS="-l `dirname $1`/nemu-log.txt $1.bin"

然后再执行上述make run的命令即可. 无需使用GDB调试时, 可将上述run脚本改回来.

实现更多的指令

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

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

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

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

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.

指令名对照

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

实现常用的库函数

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

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

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

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

实现字符串处理函数

根据需要实现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 ""