Dream Once Again

0%

NJU ICS2023 PA开发日记(PA2)

Posted on In , Valine:

在这个AI时代，真的还有人看这种古法手搓代码的blog吗？/(ㄒoㄒ)/~~

2. PA2

2.1. 不停计算的机器

最简单的图灵计算机的工作方式：

1
2
3
4
5
while (1) {
  从PC指示的存储器位置取出指令;
  执行指令;
  更新PC;
}

虽然根据不同CPU的流水线设计不同而有区别，对于大部分指令来说，执行它们都可以抽象成取指-译码-执行的指令周期。

具体可以看一下我之前的一篇CPU简单介绍：

《自己动手写CPU》读后感 - 知乎

2.2. RTFSC

RTFSC(2)

这里没有啥需要我再次解释的，直接看官方文档就行RTFSC(2) · GitBook。

PS：我发现2023版本的文档挂了。。。也不知道为啥

需要注意一下的概念就是snpc和dnpc了，前者是static next PC，后者是dynamic next PC的意思，static就是当前PC的地址上紧挨着的下一条指令的地址，是当前PC加上固定长度后的值。后者是逻辑上下一条需要执行的指令地址，因为程序执行的过程中可能会有许多分支，比如使用if或者函数调用的情况，这两个概念在CPU设计中算是很重要的。

立即数背后的故事

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

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

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

A: 这两个问题的根本是要弄清楚Host ISA和Guest ISA。Host ISA是运行NEMU的机器的ISA，Guest ISA是被模拟的ISA。

第一种情况，Host ISA就是Motorola 68K，需要注意的是实现NEMU模拟器本身的代码中，所有使用指针直接访问地址的地方，例如(uint8_t *)，在这个地址基础上使用加法访问其他地址操作的时候，需要注意大小端是否正确，因为编译器编译到目标机器上肯定都是根据目标机器的大小端来生成的。

第二种情况，Guest ISA是Motorola 68K，Host ISA根据各自运行的机器而定，目前大部分都应该是x86吧，那么就是小端机器。Guest程序会被编译成Motorola 68K的大端形式，然后我们在NEMU中取指和译码的时候就需要注意大小端问题。

立即数背后的故事(2)

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

A: 一条指令不行，那就两条指令撒。实际也是这么做的，以RISCV32为例，32位常数一般是用LUI和ADDI指令实现的，LUI先复制高20bit的数，ADDI加上剩余的低12bit数即可。

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

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

A: 可以先理解一下decode.h里面的这三个宏定义：

1
2
3
4
5
6
7
8
9
10
11
12
// --- pattern matching wrappers for decode ---
#define INSTPAT(pattern, ...) do { \
  uint64_t key, mask, shift; \
  pattern_decode(pattern, STRLEN(pattern), &key, &mask, &shift); \
  if ((((uint64_t)INSTPAT_INST(s) >> shift) & mask) == key) { \
    INSTPAT_MATCH(s, ##__VA_ARGS__); \
    goto *(__instpat_end); \
  } \
} while (0)

#define INSTPAT_START(name) { const void ** __instpat_end = &&concat(__instpat_end_, name);
#define INSTPAT_END(name)   concat(__instpat_end_, name): ; }

这里主要就是运用了标签和goto这两个概念：C goto 语句 | 菜鸟教程
虽然现代C/C+++并不建议使用这两个东西，但是在这里，这种方式非常好的实现了一个解析指令的wrapper。

然后看inst.c文件中的decode_exec函数，其中的：

1
2
3
4
5
INSTPAT_START();
INSTPAT(xxx);
INSTPAT(xxx);
//...
INSTPAT_END();

展开之后的结构就是：

1
2
3
4
5
6
7
8
9
10
11
const void **__instpat_end = &&__instpat_end_;
if (match(xxx)) {
    exec_xxx();
    goto end;
}
if (match(xxx)) {
    exec_xxx();
    goto end;
}
...
__instpat_end_: ;

关于START和END这两个宏的原理，可以去了解一下GNU的labels-as-values这个概念：【GNU笔记】【C扩展系列】标签作为值_labels as values-CSDN博客

跑的有些远了，前面是让想让我们理解代码逻辑，然后回到问题本身：理解执行未实现指令的时候, NEMU具体会怎么做？

按照代码逻辑，最后一个INSTPAT定义如下：

1
INSTPAT("??????? ????? ????? ??? ????? ????? ??", inv    , N, INV(s->pc));

而INV宏定义如下：

1
#define INV(thispc) invalid_inst(thispc)

所以最终会转到invalid_inst这个函数里，会报出invalid instruction的错误提示。

需要注意的是，这条INSTPAT一定要放在最后，否则会导致正常指令不能被解析匹配，因为前面的解析都是if逻辑。

指令名对照

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

A: 指令集官方文档里一般有相关的pseudo code/pseudo instruction表格，可以搜索相关关键词。或者可以查看编译器的官方文档。没有的话，只能看指令本身的编码来反查指令名了，比如通过opcode。

2.3. 程序, 运行时环境与AM

2.3.1. 运行时环境

直接引用原文档：

“应用程序的运行都需要运行时环境的支持, 包括加载, 销毁程序, 以及提供程序运行时的各种动态链接库(你经常使用的库函数就是运行时环境提供的)等. 为了让客户程序在NEMU中运行, 现在轮到你来提供相应的运行时环境的支持了.

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

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

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

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

依旧直接引用，原文已经足够好：

我们刚才讨论的运行时环境是直接位于计算机硬件之上的, 因此运行时环境的具体实现, 也是和架构相关的. 我们以”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, 就能使用运行时环境提供的相应功能.

抽象和封装最主要的作用就是把软件和硬件解耦了，不需要为每个硬件编写不同的程序，方便程序的移植和分发。

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

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的流程更加明确:

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

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

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

A: 还在单周目的我斗胆提前”猜想”一下，操作系统提供的运行时环境与OS软件本身设计的特性有关，而AM提供的运行时环境是与硬件的特性有关，抽象的层级不同。

2.3.4. RTFSC(3)

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

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

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

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

2.3.5. 实现常用的库函数

一种好的做法是把运行时环境分成两部分: 一部分是架构相关的运行时环境, 也就是我们之前介绍的AM; 另一部分是架构无关的运行时环境, 类似memcpy()这种常用的函数应该归入这部分, abstract-machine/klib/用于收录这些架构无关的库函数. klib是kernel library的意思, 用于提供一些兼容libc的基础功能。

实现string.c文件中的字符串处理函数，难度不大，大家自行搜索相关文档然后按照描述完成。

需要注意，未定义行为这个概念。这里有个关于编译器利用未定义行为进行优化的文章：

homes.cs.washington.edu/~akcheung/papers/apsys12.pdf

stdarg是如何实现的?

stdarg.h中包含一些获取函数调用参数的宏, 它们可以看做是调用约定中关于参数传递方式的抽象. 不同ISA的ABI规范会定义不同的函数参数传递方式, 如果让你来实现这些宏, 你会如何实现?

stdarg.h里最重要的就是这三个宏了：

1
2
3
#define va_start(v,l)	__builtin_va_start(v,l)
#define va_arg(v,l)		__builtin_va_arg(v,l)
#define va_end(v)		__builtin_va_end(v)

其中va_start是负责初始化 va_list，让输入参数v指向第一个可变参数，l是指向最后一个固定参数。

va_arg的功能是读取当前参数，并移动到下一个参数。

va_end的功能是结束变参访问，释放相关资源。

至于__builtin_开头的这些函数，是GCC的内置函数，得去看编译器源码，我们暂时先当作黑盒吧，他们就是编译器把不同ISA的ABI（Application Binary Interface）包装出来的一层抽象。

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

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

TRM 计算 内存申请 结束运行 打印信息
运行环境 - malloc()/free() - printf()
AM API - heap halt() putch()
ISA接口 指令 物理内存地址空间 nemu_trap指令 I/O方式
硬件模块 处理器 物理内存 Monitor 串口
电路实现 cpu_exec() pmem[] nemu_state serial_io_handler()

“程序在计算机上运行”的宏观视角: 计算机是个抽象层

每一层抽象都有它存在的理由:

  • 概念相同的一个硬件模块有着不同的实现方式, 比如处理器既可以通过NEMU中简单的解释方式来实现, 也可以通过类似QEMU中高性能的二进制翻译方式来实现, 甚至可以通过verilog等硬件描述语言来实现一个真实的处理器.
  • ISA是硬件向软件提供的可以操作硬件的接口
  • AM的API对不同ISA(如x86/mips32/riscv32)的接口进行了抽象, 为上层的程序屏蔽ISA相关的细节
  • 运行时环境可以通过对AM的API进行进一步的封装, 向程序提供更方便的功能

pa-concept

2.4. 基础设施2

2.4.1. bug诊断的利器 - 踪迹

在软件工程领域, 记录程序执行过程的信息称为踪迹(trace)). 有了踪迹信息, 我们就可以判断程序的执行过程是否符合预期, 从而进行bug的诊断.

2.4.1.2. 指令环形缓冲区 - iringbuf

这个实现一个环形缓冲buf就行，so easy。

2.4.1.4. 函数调用的踪迹

需要解析ELF文件，首先可以看一下ELF的格式，使用：man 5 elf。

我们要在初始化ftrace时从ELF文件中读出符号表和字符串表，供后续使用。

ELF文件中包括许多的section，其中我们需要用到的section有如下3个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
.shstrtab
     This section holds section names.  This section is of type
              SHT_STRTAB.  No attribute types are used.

.strtab
     This section holds strings, most commonly the strings that
     represent the names associated with symbol table entries.
     If the file has a loadable segment that includes the symbol
     string table, the section's attributes will include the
     SHF_ALLOC bit.  Otherwise, the bit will be off.  This
     section is of type SHT_STRTAB.
.symtab
     This section holds a symbol table.  If the file has a
     loadable segment that includes the symbol table, the
     section's attributes will include the SHF_ALLOC bit.
     Otherwise, the bit will be off.  This section is of type
     SHT_SYMTAB.
     An object file's symbol table holds information needed to locate
     and relocate a program's symbolic definitions and references.  A
     symbol table index is a subscript into this array.

.shstrtab保存的是section name；.strtab保存的是符号表中需要用到的字符串，也就是字符串表；.symtab保存的是符号相关的信息，就是我们说的符号表。

实现ftrace的思路如下：

  1. 提前通过符号表和字符串表解析出来各个函数对应的地址（和范围）
  2. 在执行jal和jalr指令的时候，判断跳转的地址是否在第1步中解析出来的函数中。
    1. 如果是，则打印信息
    2. 如果不是，则不打印

ELF文件的最开始是一个ELF Header结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct {
    unsigned    char e_ident[16];
    uint16_t    e_type;
    uint16_t    e_machine;
    uint32_t    e_version;
    Elf64_Addr  e_entry;
    Elf64_Off   e_phoff;
    Elf64_Off   e_shoff;      // <- 节表偏移
    uint32_t    e_flags;
    uint16_t    e_ehsize;
    uint16_t    e_phentsize;
    uint16_t    e_phnum;
    uint16_t    e_shentsize;
    uint16_t    e_shnum;
    uint16_t    e_shstrndx;   // <- shstr在节表中的下标
} Elf64_Ehdr;

其中，e_shoff表示的是section header table（sht）在文件中的字节偏移，可以通过它直接定位到sht。
然后，e_shstrndx是sht中字符串表的下标，可以通过它定位到字符串表。
最后，我们需要找到符号表，找到符号表才能找到相应的函数符号。

其中e_shnum是sht数组的大小，即多少项。e_shentsize是每一项的大小。这两个是用来辅助解析sht的。

我们还需要知道的是，符号表每一项的结构体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct {
    uint32_t      st_name;
    Elf32_Addr    st_value;
    uint32_t      st_size;
    unsigned char st_info;
    unsigned char st_other;
    uint16_t      st_shndx;
} Elf32_Sym;

typedef struct {
    uint32_t      st_name;
    unsigned char st_info;
    unsigned char st_other;
    uint16_t      st_shndx;
    Elf64_Addr    st_value;
    uint64_t      st_size;
} Elf64_Sym;

其中st_info指示的是这个符号的类型，如果是它的值是STT_FUNC，那么就表示这个符号是一个函数名。

一个小坑需要注意，st_info这个成员不只是符号的类型，还有binding信息，所以还需要通过一个宏ELF32_ST_TYPE(info)来将st_info转换成TYPE类型再和STT_FUNC对比判断。

RISC-V架构中，函数的调用和返回都是通过jal或jalr指令来实现的，前者是直接跳转指令，后者是间接跳转指令。

一个典型的ELF文件的大致内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+---------------------------+
| ELF Header (Elf32_Ehdr)   |
+---------------------------+
| Program Header Table (可选)|
+---------------------------+
| Section 1 (.text)         |
+---------------------------+
| Section 2 (.data)         |
+---------------------------+
| Section 3 (.shstrtab)     |
+---------------------------+
| Section ...               |
+---------------------------+
| Section Header Table      |
+---------------------------+
| Section ...               |
+---------------------------+

实现初版的ftrace后，运行得到的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
0x8000000c: call [_trm_init@0x80000258]
0x80000268:   call [main@0x800001cc]
0x800001ec:     call [f0@0x80000010]
0x8000016c:       call [f2@0x800000a4]
0x800000f0:         call [f1@0x8000005c]
0x8000016c:           call [f2@0x800000a4]
0x800000f0:             call [f1@0x8000005c]
0x8000016c:               call [f2@0x800000a4]
0x800000f0:                 call [f1@0x8000005c]
0x8000016c:                   call [f2@0x800000a4]
0x800000f0:                     call [f1@0x8000005c]
0x8000016c:                       call [f2@0x800000a4]
0x800000f0:                         call [f1@0x8000005c]
0x80000058:                         ret [f0]		# 注释(2)
0x80000100:                       ret [f2]			# 注释(1)
0x80000184:                       call [f2@0x800000a4]
0x800000f0:                         call [f1@0x8000005c]
0x80000058:                         ret [f0]
0x80000100:                       ret [f2]
0x800001ac:                     ret [f3]			# 注释(3)
0x80000100:                   ret [f2]
0x80000184:                   call [f2@0x800000a4]
0x800000f0:                     call [f1@0x8000005c]
0x8000016c:                       call [f2@0x800000a4]
0x800000f0:                         call [f1@0x8000005c]
0x80000058:                         ret [f0]
0x80000100:                       ret [f2]
0x80000184:                       call [f2@0x800000a4]
0x800000f0:                         call [f1@0x8000005c]
0x80000058:                         ret [f0]
0x80000100:                       ret [f2]
0x800001ac:                     ret [f3]
0x80000100:                   ret [f2]

消失的符号

我们在am-kernels/tests/cpu-tests/tests/add.c中定义了宏NR_DATA, 同时也在add()函数中定义了局部变量c和形参a, b, 但你会发现在符号表中找不到和它们对应的表项, 为什么会这样？思考一下, 什么才算是一个符号(symbol)？

A：

  1. 宏定义根本不是一个符号，他在预处理阶段就被展开了，所以编译器根本不知道它的存在。

  2. 局部变量由于没有被外部调用，只是一个临时的变量，不一定需要用符号来表示存在，汇编语言中可以直接用寄存器来表示。

  3. 什么才算一个符号？

    从链接的角度：符号是一个能够被其他位置引用、需要在目标文件之间建立关联关系的名字。比如全局变量，或者函数。

寻找”Hello World!”

在Linux下编写一个Hello World程序, 编译后通过上述方法找到ELF文件的字符串表, 你发现”Hello World!”字符串在字符串表中的什么位置? 为什么会这样?

A：如果hello world程序是下面这样的：

1
2
3
4
5
6
#include <stdio.h>

int main() {
    printf("Hello world!\n");
    return 0;
}

那么这个Hello world是在.rodata section里面，因为.strtab保存的是符号表中需要用到的字符串，而链接器不需要通过符号找到这个字符串。即使你定义了一个全局指针指向这个字符串，那么在字符串表里的也是这个指针的名字，而不是Hello world本身。

不匹配的函数调用和返回​
Q：如果你仔细观察上文recursion的示例输出, 你会发现一些有趣的现象. 具体地, 注释(1)处的ret的函数是和对应的call匹配的, 也就是说, call调用了f2, 而与之对应的ret也是从f2返回; 但注释(2)所指示的一组call和ret的情况却有所不同, call调用了f1, 但却从f0返回; 注释(3)所指示的一组call和ret也出现了类似的现象, call调用了f1, 但却从f3返回。

尝试结合反汇编结果, 分析为什么会出现这一现象.

A：尾调用优化，在函数结尾简单地调用另一个函数的话，会触发编译器的尾调用优化。这里的“简单”是指仅仅调用另一个函数，而不会在调用后对返回值进行处理，例如f2函数中的“+9”。所以我们可以观察到，不匹配的call和ret是固定组合：

  1. call f1, ret f3
  2. call f1, ret f0
  3. call f0, ret f3 (这个是最外面一层call ret对)

还有一个“奇怪的”点，你可以观察到，最开始的第一个call f0函数后，call的是f2，而不是代码中的f3。实际上这也是尾调用优化的一个影响，实现尾调用的话，不需要保存返回地址到ra寄存器，而我们实现的ftrace是按照是否保存返回地址到ra判断是否是call指令的，因此，要实现真正的ftrace，还需要对jal/jalr指令进行判断，不能仅仅看是否保存地址到ra。所以目前实现的ftrace仅仅是简单版本。

通过看反汇编结果，可以发现f0和f1中调用其他两个函数的语句都是jr，即最简单的无条件跳转，并没有保存返回地址，所以从这两个函数出发去调用其他函数之后，会产生没有匹配的ret的情况。而f2和f3中的调用都是jalr指令，会保存返回地址，所以ftrace能够匹配。

关于尾调用优化（TCO）的解释，推荐一个视频：

https://www.bilibili.com/video/BV1Pb421Y7uP

冗余的符号表

在Linux下编写一个Hello World程序, 然后使用strip命令丢弃可执行文件中的符号表:

1
2
gcc -o hello hello.c
strip -s hello

用readelf查看hello的信息, 你会发现符号表被丢弃了, 此时的hello程序能成功运行吗?

目标文件中也有符号表, 我们同样可以丢弃它:

1
2
gcc -c hello.c
strip -s hello.o

用readelf查看hello.o的信息, 你会发现符号表被丢弃了. 尝试对hello.o进行链接:

1
gcc -o hello hello.o

你发现了什么问题? 尝试对比上述两种情况, 并分析其中的原因.

strip掉可执行文件中的符号表依然可以执行，但是strip掉目标文件中的符号表后再链接就会报错：

1
2
3
4
/usr/bin/ld: error in test.o(.eh_frame); no .eh_frame_hdr table will be created
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/9/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status

这是因为符号表只是用于在链接的时候定位地址。

2.4.2. AM作为基础设施

如何生成native的可执行文件

Q: 阅读相关Makefile, 尝试理解abstract-machine是如何生成native的可执行文件的。

A: 以cpu-tests下的makefile为例，当我们在cpu-tests文件夹下输入make ARCH=native run命令之后，make程序里会有一个变量ARCH被赋值为native，make程序会为每个子测试代码创建单独的临时Makefile文件：

1
2
3
Makefile.%: tests/%.c latest
	@/bin/echo -e "NAME = $*\nSRCS = $<\ninclude $${AM_HOME}/Makefile" > $@
	@if make -s -f $@ ARCH=$(ARCH) $(MAKECMDGOALS); then \

然后用子进程去运行这些临时Makefile文件单独编译运行每个test，我们在命令行输入的ARCH=native，就会传给这些子进程，由于include了AM的Makefile，在其中，会用到ARCH这个变量来选择AM的scripts目录下不同平台的编译脚本来编译。

奇怪的错误码

Q: 为什么错误码是1呢? 你知道make程序是如何得到这个错误码的吗?

A：

1
2
3
4
5
6
7
8
9
10
11
$ make ARCH=native ALL=string run
# Building string-run [native]
+ CC tests/string.c
# Building am-archive [native]
# Building klib-archive [native]
# Creating image [native]
+ LD -> build/string-native
Exit code = 01h
make[1]: *** [/home/doa/Documents/OS/ics2023/abstract-machine/scripts/native.mk:25: run] Error 1
test list [1 item(s)]: string
[        string] ***FAIL***

check函数中如果check失败的话会调用halt。native情况下，最终会调用linux的系统函数exit(code)，程序中传递的code为1，所以最终make就会检测到这个退出码并打印出来（如上面第9行），同时这里会指出是哪一行make命令执行出错，ctrl+左键可以跳转到那里去看。

PS：如果是嵌套的make，被调用的make中有出错的recipe指令，make子进程本身就会以错误码2退出（可以在ARCH=riscv32-nemu的情况下查看确认）。

这是如何实现的?

Q：为什么定义宏__NATIVE_USE_KLIB__之后就可以把native上的这些库函数链接到klib? 这具体是如何发生的? 尝试根据你在课堂上学习的链接相关的知识解释这一现象.

A：klib.h头函数中，可以定义__NATIVE_USE_KLIB__这个宏，然后即使在native的情况下，也会定义klib中实现的函数了，然后在native.mk中会通过-Wl,--whole-archive $(LINKAGE) -Wl,-no-whole-archive这个参数传递给链接器，强制链接klib中实现的一些库函数，后续就不会再链接linux本身的stdio/stdlib中的函数了。

捕捉死循环(有点难度)

Q：NEMU除了作为模拟器之外, 还具有简单的调试功能, 可以设置断点, 查看程序状态. 如果让你为NEMU添加如下功能

当用户程序陷入死循环时, 让用户程序暂停下来, 并输出相应的提示信息

你觉得应该如何实现? 如果你感到疑惑, 在互联网上搜索相关信息.

A：

这个方案有很多，但是没有一个绝对准确判定是否进入死循环的方法。因为很难区分是真的死循环还是一个超大循环。具体可以自行了解~

2.5. 输入输出

2.5.1. 设备与CPU

在程序看来, 访问设备 = 读出数据 + 写入数据 + 控制状态.

访问设备有两种方式：

  1. 端口I/O
  2. 内存映射I/O

前者使用专门的I/O指令来实现对设备（外设）的读写，每个设备有专门的端口号，但是这种方式的缺点就是可以访问的设备地址空间是有限的，这是由指令可访问的范围决定的。x86 CPU就支持这种方式（当然，它也支持内存映射）

后者直接将设备的寄存器映射到某些内存地址，访问这些内存地址就相当于访问设备内部的寄存器。这种方式非常方便。

理解volatile关键字

也许你从来都没听说过C语言中有volatile这个关键字, 但它从C语言诞生开始就一直存在. volatile关键字的作用十分特别, 它的作用是避免编译器对相应代码进行优化. 你应该动手体会一下volatile的作用, 在GNU/Linux下编写以下代码:

1
2
3
4
5
6
7
8
9
void fun() {
  extern unsigned char _end;  // _end是什么?
  volatile unsigned char *p = &_end;
  *p = 0;
  while(*p != 0xff);
  *p = 0x33;
  *p = 0x34;
  *p = 0x86;
}

然后使用-O2编译代码. 尝试去掉代码中的volatile关键字, 重新使用-O2编译, 并对比去掉volatile前后反汇编结果的不同.

Q：你或许会感到疑惑, 代码优化不是一件好事情吗? 为什么会有volatile这种奇葩的存在? 思考一下, 如果代码中p指向的地址最终被映射到一个设备寄存器, 去掉volatile可能会带来什么问题?

volatile一般是用在访问CPU外部设备寄存器的地方，它会告诉编译器：

“这个变量可能会以你无法感知的方式被改变。每次读写都必须严格按代码顺序、逐条执行，不能省略、不能合并、不能重排。”

没有 volatile 时，编译器会基于“内存只由当前代码修改”的假设进行优化。对于上述代码来说，直接被优化成一个死循环，因为*p = 0;，编译器以为没有其他地方会修改这个值，就不会去重新读取这个地址的值，所以while永远不会跳出。

通过内存进行数据交互的输入输出

我们知道S = <R, M>, 上文介绍的端口I/O和内存映射I/O都是通过寄存器R来进行数据交互的. 很自然地, 我们可以考虑, 有没有通过内存M来进行数据交互的输入输出方式呢?

其实是有的, 这种方式叫DMA. 为了提高性能, 一些复杂的设备一般都会带有DMA的功能. 不过在NEMU中的设备都比较简单, 关于DMA的细节我们就不展开介绍了.

DMA(Direct Memory Access) 的本质：数据传输不经过 R，直接在 M 和设备之间建立通道。

2.5.2. NEMU中的输入输出

RISCV32格式的NEMU中使用的是MMIO来实现设备的访问，在src/device/device.c中有相关初始化设备的init_device()函数。

NEMU项目中的设备地址定义在autoconf.h中，可以通过make menuconfig来修改定义的地址。

cpu_exec()在执行每条指令之后就会调用device_update()函数, 这个函数首先会检查距离上次设备更新是否已经超过一定时间, 若是, 则会尝试刷新屏幕, 并进一步检查是否有按键按下/释放, 以及是否点击了窗口的X按钮; 否则则直接返回, 避免检查过于频繁, 因为上述事件发生的频率是很低的.

运行hello world

设备初始化的流程：

NEMU(init_monitor)—>NEMU device(init_device)—> NEMU device(各种device init)—>NEMU device IO(add_mmio_map)

这个hello的例子中，暂时还没有用到IOE层：AM(ioe_init)—>AM层外设init

设备访问的流程：

对于RISC-V来说，就是直接写地址，然后在paddr.c中会进行地址的判断，判断是否是往MMIO的地址写入，如果是，则调用

vaddr_write—>paddr_write—>mmio_write—>map_write—>host_write(往mmio map的space中写入数据)—>调用设备的callback函数，以serial为例，那就是调用serial_io_handler函数—>serial_putc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
hello.c
  printf（测试例子中没有调用这个，直接调用putch）
    ↓
  putch
    ↓
  outb(SERIAL_PORT)
    ↓   （store 指令）
NEMU CPU 模拟
    ↓
MMIO 命中 serial
    ↓
serial_io_handler
    ↓
serial_putc
    ↓
putc(stderr)   ← Linux

理解mainargs

Q：请你通过RTFSC理解这个参数是如何从make命令中传递到hello程序中的, $ISA-nemu和native采用了不同的传递方法, 都值得你去了解一下.

A：

如果make的时候用$ISA-nemu架构编译，他的传递方式如下：

在nemu.mk这个文件中，我们在命令行中输入的mainargs参数被定义为一个宏MAINARGS：

CFLAGS += -DMAINARGS=\"$(mainargs)\"

然后在trm.c中被引用到，_trm_init()函数来调用main()函数，传递mainargs参数。

那么_trm_init()函数是怎么被用到的呢？

如果是native架构下编译运行，那么它的传递方式如下：

在platform.c的代码中的init_platform函数，会通过环境变量来获取mainargs参数：

1
2
const char *args = getenv("mainargs");
halt(main(args ? args : "")); // call main here!

为什么能通过环境变量获取到mainargs？因为我们运行的时候是通过make的命令行参数指定的mainargs：

1
make ARCH=native run mainargs=xxx

make中的recipe指令会自动继承运行make指定时的命令行变量到环境变量中（ARCH和mainargs都算命令行变量）。

RTC - 实时时钟

RTC泛指流逝速率与真实时间一致的时钟, 用户可根据RTC进行一段时间的测量. 按照这个定义, 上述两个AM抽象寄存器都属于RTC, 不过它们的侧重点有所不同: AM_TIMER_RTC强调读出的时间与现实时间完全一致, AM_TIMER_UPTIME则侧重系统启动后经过的时间, 即从0开始计数.

虽然NEMU中的设备寄存器的名称也叫RTC, 但为了支持AM_TIMER_UPTIME的功能, 它不必实现成AM_TIMER_RTC.

实现IOE

在abstract-machine/am/src/platform/nemu/ioe/timer.c中实现AM_TIMER_UPTIME的功能. 在abstract-machine/am/src/platform/nemu/include/nemu.h和 abstract-machine/am/src/$ISA/$ISA.h中有一些输入输出相关的代码供你使用.

实现后, 在$ISA-nemu中运行am-kernel/tests/am-tests中的real-time clock test测试. 如果你的实现正确, 你将会看到程序每隔1秒往终端输出一行信息. 由于我们没有实现AM_TIMER_RTC, 测试总是输出1900年0月0日0时0分0秒, 这属于正常行为, 可以忽略.

跑分的bug

实现完RTC的IOE后，运行PA中的3个benchmark，

出现了如下的bug：

1
2
3
4
5
6
7
8
9
10
Dhrystone Benchmark, Version C, Version 2.2
Trying 500000 runs through Dhrystone.
Finished in 0 ms
==================================================
Dhrystone PASS         -1 Marks
                   vs. 100000 Marks (i7-7700K @ 4.20GHz)
[src/cpu/cpu-exec.c:125 cpu_exec] nemu: HIT GOOD TRAP at pc = 0x80000d2c
[src/cpu/cpu-exec.c:92 statistic] host time spent = 8,835,660 us
[src/cpu/cpu-exec.c:93 statistic] total guest instructions = 219,508,565
[src/cpu/cpu-exec.c:94 statistic] simulation frequency = 24,843,482 inst/s

跑分为-1！

这是因为我实现AM的RTC有问题，因为要先读取RTC的高32位数据才会刷新！（看NEMU中timer.c的代码可以知道）。

2.5.3. 将输入输出抽象成IOE

设备访问的踪迹 - dtrace

因为在NEMU中MMIO是通过在map_read和map_write这两个函数来实现的，所以我们只需要实现trace，然后在这两个函数中调用就行。你可能会遇到跟我一样的问题，如下。

在utils.h中添加dtrace的函数声明如下：

1
2
3
4
5
6
// ----------- dtrace ------------
struct IOMap;

void trace_device_read(paddr_t addr, int len, struct IOMap *map);

void trace_device_write(paddr_t addr, int len, word_t data, struct IOMap *map);

其中，前向声明struct IOMap是必须的，因为这个结构体在map.h中，但是如果直接include “device/map.h”的话，会造成循环引用，从而导致以下错误：

1
2
3
4
5
6
7
8
9
10
11
+ CC src/device/device.c
In file included from /home/doa/Documents/OS/ics2023/nemu/include/device/map.h:19,
                 from /home/doa/Documents/OS/ics2023/nemu/include/utils.h:20,
                 from /home/doa/Documents/OS/ics2023/nemu/include/debug.h:21,
                 from /home/doa/Documents/OS/ics2023/nemu/include/common.h:47,
                 from src/device/device.c:16:
/home/doa/Documents/OS/ics2023/nemu/include/cpu/difftest.h: In function ‘difftest_check_reg’:
/home/doa/Documents/OS/ics2023/nemu/include/cpu/difftest.h:46:5: error: implicit declaration of function ‘Log’ [-Werror=implicit-function-declaration]
   46 |     Log("%s is different after executing instruction at pc = " FMT_WORD
      |     ^~~
cc1: all warnings being treated as errors

同时，需要将map中的结构体定义改为：

1
2
3
4
5
6
7
8
typedef struct IOMap{
  const char *name;
  // we treat ioaddr_t as paddr_t here
  paddr_t low;
  paddr_t high;
  void *space;
  io_callback_t callback;
} IOMap;

即，在struct后面也加一个IOMap名称。这样才能使用前向声明，否则也会报错。

VGA

神奇的调色板

现代的显示器一般都支持24位的颜色(R, G, B各占8个bit, 共有2^8*2^8*2^8约1600万种颜色), 为了让屏幕显示不同的颜色成为可能, 在8位颜色深度时会使用调色板的概念. 调色板是一个颜色信息的数组, 每一个元素占4个字节, 分别代表R(red), G(green), B(blue), A(alpha)的值. 引入了调色板的概念之后, 一个像素存储的就不再是颜色的信息, 而是一个调色板的索引: 具体来说, 要得到一个像素的颜色信息, 就要把它的值当作下标, 在调色板这个数组中做下标运算, 取出相应的颜色信息. 因此, 只要使用不同的调色板, 就可以在不同的时刻使用不同的256种颜色了.

在一些90年代的游戏中(比如仙剑奇侠传), 很多渐出渐入效果都是通过调色板实现的, 聪明的你知道其中的玄机吗?

这里的调色板也是放在VGA设备侧的设备寄存器，相当于一个数组，这个与“显存”是相互独立的，当时的“显存”存放的应该是调色板的索引值，而不是直接的RGB值，相当于由调色板做一层“转译”，这个转译的过程是VGA设备这一侧实现的，而不是CPU，所以对于渐入渐出的情况能达到加速的效果，因为CPU只用修改调色板的值。

2.5.4. 冯诺依曼计算机系统

在NEMU上运行NEMU编译的时候，你可能遇到以下问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/home/doa/Documents/OS/ics2023/nemu/src/engine/interpreter/hostcall.c:36:10: error: format '%x' expects argument of type 'unsigned int', but argument 11 has type 'uint32_t' {aka 'long unsigned int'} [-Werror=format=]
   36 |   printf("invalid opcode(PC = " FMT_WORD "):\n"
      |          ^~~~~~~~~~~~~~~~~~~~~~
......
   39 |       thispc, p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7], temp[0], temp[1]);
      |                                                               ~~~~~~~
      |                                                                   |
      |                                                                   uint32_t {aka long unsigned int}
/home/doa/Documents/OS/ics2023/nemu/src/engine/interpreter/hostcall.c:36:10: error: format '%x' expects argument of type 'unsigned int', but argument 12 has type 'uint32_t' {aka 'long unsigned int'} [-Werror=format=]
   36 |   printf("invalid opcode(PC = " FMT_WORD "):\n"
      |          ^~~~~~~~~~~~~~~~~~~~~~
......
   39 |       thispc, p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7], temp[0], temp[1]);
      |                                                                        ~~~~~~~
      |                                                                            |
      |                                                                            uint32_t {aka long unsigned int}
cc1: all warnings being treated as errors

这个问题一开始看得我很懵逼，因为temp是uint32_t类型的，为什么会报警告呢？即使展开成long unsigned int，也是32位呀，为什么还是报警告呢？解决起来很简单，就是把前面对应的%x改为%lx，但是我很奇怪，为很么单层NEMU得时候编译没有问题，一嵌套就报警告了呢？

编译过程中，不止这一个地方的格式有问题，还有很多类似的警告，但解决方法都是一样的。不过要注意关闭NEMU的trace噢，不然里面有一些NEMU不支持的东西。

经过一路追查，发现是由于不同编译器对uint32_t这些类型的最终实现不一定一样：

编译运行在NEMU上的NEMU时使用的是riscv32的交叉编译器，而运行在我们x86上的NEMU使用的是x86版本的编译器，对于uint32_t这种类型来说，上面这个报错说明riscv32编译器定义的是long unsigned int，所以需要加上长度修饰符l。对于这些类型的打印格式，最好使用inttype.h头文件中的可移植宏定义（PRIx32，PRIu32这种），它会根据不同平台来自动添加长度修饰符。下图是我找到的riscv32平台的inttypes.h中的定义以及最终展开的__INT32长度修饰符：

image-20260426210557109

image-20260426210444105

所以你实现的printf也要支持这些长度描述符