NJU-ICS 2019 概要总结

因为QDU软工的机组实在是过于水,我这门课一节都没有听过就考完试了(当然肯定也过了),所以翻出了之前在知乎上看到的南京大学 计算机科学与技术系 计算机系统基础 课程实验 2019,打算在这个寒假做一做巩固基础。

NJU的ICS实验是要写一个类似于QEMU但是简单很多的虚拟机,最后在上面跑NES游戏,架构也可以在 x86mipsrisc-v 里任选。因为我对 x86 比较熟,一周目就先选它好了,以后再有机会可以选 risc-v 玩玩。

在这里随便说一说几个比较重要的点,其它的细节因为太懒所以不太会说。

PA1 - 开天辟地的篇章: 最简单的计算机

第一节主要是完善调试功能,感觉也不是很难?

实现x86的寄存器结构体

简要的说就是,有一个结构体CPU_state,让你用匿名union安排其结构以实现下面的功能。

1
2
3
1. cpu.gpr[0]._16 在数值上等于 (cpu.gpr[0]._32) & ((~0U) >> 16)
(也就是它的前16位)
2. cpu.gpr[0]._32 等价于 cpu.eax

1 看懂cpu寄存器那张图之后,很明显可以用union把_32_16_8[2]包起来就行了。

1
2
3
4
5
6
7
typedef struct { 
union {
uint32_t _32;
uint16_t _16;
uint8_t _8[2];
} gpr[8];
} CPU_state;

2 也就是在内存位置上让gpr[0]等价于eaxgpr[1]等价于ecx,所以应该把gpr数组和eax,ecx…用union包起来。但是注意的是需要先把eax,ecx…这些先放进一个struct里才行。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct {
union {
union {
uint32_t _32;
uint16_t _16;
uint8_t _8[2];
} gpr[8];

struct {
rtlreg_t eax, ecx, edx, ebx, esp, ebp, esi, edi;
};
};
} CPU_state;

感觉实现比较巧,并运用了匿名的特性。

如果不懂,可以先弄清楚C语言中union的原理。

实现算术表达式的词法分析

这里是根据正则表达式按字符串从左到右提取出相关符号(比如加减乘除、数字、圆括号等等,它们都叫做token),然后记录信息。换句话说就是把它们抽象出来便于后续处理。正则表达式库用的是POSIX的regex.h

然而有几个坑点:

  1. 它不支持\d+来匹配数字,可以用([0-9]+)代替。

  2. 如果假设你要匹配!=(不等号)和!(逻辑非),你要保证先匹配前者,再匹配后者才行,不解释。

  3. 假设获得了匹配成功后的子串substr和其长度sublen,调用strncpy(new_str,substr,sublen)拷贝指定sublen长度的字符串。注意此时strncpy指定的长度不包括\0,所以不会在新字符串末尾添上\0,要手动补上new_str[sublen]='\0';

当然这些都可以调试出来,所以不太算是难点。

实现算术表达式的递归求值

这里硬写就行。注意多考虑边缘条件,多用Log宏输出就能使大部分调试变得轻松。

实现表达式生成器

这里要注意中间过程的数字表示。假如你生成的表达式的数字是直接表示的,比如1+2+3,这里的1、2、3肯定都是有符号的,所以在C语言的求值过程中的整数都是有符号的。但如果你在求值的中间过程中用了无符号,当中间过程遇到负数时答案就与生成的答案不符了。所以要么中间过程用有符号整型,最后把答案转化成uint32_t;要么生成1U+2U+3U这样的表达式。

关于除以0的问题,一部分可以特判“当有除号时右边的数字不能是‘0’”来解决,但是当3/(1-1)这种的情况就行不通了。

这里先解释一下生成原理:先生成表达式字符串,在把它塞进这样一个C语言代码字符串里:

1
2
3
4
5
6
"#include <stdio.h>\n"
"int main() { "
" unsigned result = %s; "
" printf(\"%%u\", result); "
" return 0; "
"}";

然后输出到文件里,调用gcc编译运行并获得输出结果。

然后发现gcc会在编译时对代码里的常量表达式求值,并在除以0的时候提warning,所以可以先用-Werror编译选项把这些warning变成error,然后检查system("gcc /tmp/.code.c -o /tmp/.expr -Werror")调用的返回值是否非0,如果非0就说明编译出现error,产生了除以0的情况,这样就能完美解决第二部分的问题。

扩展表达式求值的功能

要先注意运算符的优先级顺序。

如何解决负数和间接引用运算符呢?首先可以看出,可供选择的主运算符肯定都是双目运算符,即该运算符左右两边连接了两个表达式。而负号和间接引用都是单目运算符,它们的优先级顺序肯定是最高的,肯定比所有双目运算符高。所以先选择主运算符,当表达式中无主运算符时在根据第一个token的信息处理单目运算符。

还要注意当选择双目运算符时跳过括号内的token和所有单目运算符。如何判断是单目还是双目(比如*-)?判断一下此运算符左边的token是不是表达式就行了,即是不是数字或右圆括号。

最后建议读一下这个并想想为什么int3只有1字节长。

PA2 - 简单复杂的机器: 冯诺依曼计算机系统

PART 1 2

这节就是实现各种x86指令的模拟,做之前需要阅读大量的手册和代码,才能明白如何正确的实现。因为内容实在是过于琐碎所以反而没有太多要说的,写之前多读代码和手册就行。否则即使你暂时写对了,也会发现其实做了很多无用功。

建议每实现一个指令都好好测试一遍,否则到了之后跑test失败后再去一堆汇编里挑出有bug的指令就很麻烦了。我的绝大多数时间也都浪费在了这上面。虽然有时候可能就是在实现时某个指令时的一个小小的错误,但当小雪球慢慢滚大了之后就会在莫名其妙的地方崩掉,这时候才是所谓的调试地狱。

程序, 运行时环境与AM

这节主要是手写string.hstdio.h里的大多数函数,这里强烈建议实现时对照cpprefence手册里的说明一步步来。

另外说一下在实现*printf时的一个坑:首先测试时提供了实机运行和模拟器运行两种方式,但是前者是x86-64但后者是i386。而va_list在两种平台上的实现并不相同。比如说你要调用一个需要用到va_list的函数a,当调用完之后你也需要继续用到va_list。这时候需要传指针进去才能保证va_list是a调用后的状态。但是这样做会在前者崩掉;如果只传va_list又会使得后者工作不正常。根本原因就是va_list在两种平台上其实是两种类型完全不同的东西。所以我们需要一种解决方法使得对平台无关:可以定义一个全局的va_list,当a返回前用通用的va_copy宏将用过的va_list拷贝过去,a结束后在从全局的va_list里copy一下更新状态。不过我这里就简单的用宏判断平台并插入不同的代码解决了。关于为什么传指针会在64位平台上崩掉,我会在下面说明。

AM作为基础设施

这里引入了一种新的测试手段:通过在后台运行一个QEMU,然后每执行一个指令后比较两者的9个寄存器(8个常用+pc)是否一致。这种通过引入一个正确的实现然后两者比较的手段很像对拍,且功能强大。在大多数时候当在某个指令运行后出错了,那十有八九就只有它有问题。只不过它不比对eflags和内存,所以很多时候还是要滚回去看汇编和源代码。

还有这个计算的极限,建议看看。

输入输出

没啥可说的。这里为了让这里写的运行时移植方便,所以又将输入输出部分单独抽离,做成了几个“抽象寄存器”。这样移植的时候时候只要实现相关的“抽象寄存器”就好了。

最后运行litenes,然而只有3fps,卡成ppt,喷了。

最后说一下有关C\C++里有关inline函数的一切。

有关C\C++里有关inline函数的一切

inline修饰的函数,本意是指将该函数的指令直接嵌入被调用的地方(称为内联),这样对于短小用的又多的函数来说就省去了函数调用开销。然而该关键字并不强迫编译器强行内联,所以实际上你写不写inline和编译器是不是真的inline关系不大。

如果在不同的编译单元里存在多份某个inline函数,会怎么办呢?在C++里是随便在这些版本中随便挑一个,只保留一份版本。因为它默认所有版本的函数实现都是相同的,即使是不同的。所以很多人会直接把函数实现写在头文件里并标注inline,这样虽然被引用该头文件的不同的编译单元插入了多次,最终编译后只会保留一份。但如果标注static,最终编译后则会使相同的函数版本保留多份。

对于C语言,情况就复杂了,具体可以看这里。C语言的函数有内联定义和外部定义两种,如果编译器想内联就用内联定义,否则用外部定义。所以如果你还向上面那样在头文件里写inline函数,当编译器不内联时就会找不到外部定义而报错。所以要么用extern inline把其他编译单元的某个副本变成外部定义,要么在头文件里把inline改成static inline,这样当内联失败时就会把它当static看待并使用。

1
2
3
4
5
6
- "static inline" means "we have to have this function, if you use it
but don't inline it, then make a static version of it in this
compilation unit"

- "extern inline" means "I actually _have_ an extern for this function,
but if you want to inline it, here's the inline-version"

Extern Vs Static Inline

当然实际上,即使是static函数编译器也会尝试将它内联,所以static inline 和 static 实际上差别不大。

64位平台上的va_list

建议先看这个

64位平台上的va_list实际上是一个结构体数组:

1
2
3
typedef struct xxx {
// 这里记录着可变参数的位置偏移量等信息
} [1] va_list;

为什么要这样写呢,打个比方:

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
34
35
#include <stdio.h>
#include <stdarg.h>

void foo(va_list *args) {
for (int i = 0; i < 3; ++i) {
int n = va_arg(*args, int);
printf("%d ", n);
}
}

void foo2(int count, va_list args) {
for (int i = 0; i < 2; ++i) {
int n = va_arg(args, int);
printf("%d ", n);
}
count -= 2;
foo(&args);
count -= 3;
for (int i = 0; i < count; ++i) {
int n = va_arg(args, int);
printf("%d ", n);
}
}

void foo1(int count, ...) {
va_list arg;
va_start(arg, count);
foo2(count, arg);
va_end(arg);
}

int main() {
foo1(5, 1, 2, 3, 4, 5, 6, 7);
// 正常应该输出 1 2 3 4 5 6 7
}

这里foo2把va_list传给foo后因为要继续用,就遇到va_list需要更新的情况。一般来说是给foo传va_list的指针,但是这里只用传va_list就行了。为什么?

在C里函数形参如果是个type类型的数组,那么它实际上是type类型的指针。所以在foo2里args的类型就已经变成struct xxx *了,所以参数va_list,实际上就相当于struct xxx *,这样就方便了很多,碰到类似问题不用再想什么更不更新传指针的问题了,直接无脑va_list,非常巧的设计。

但是遇到32位机上取地址的代码时,就出现问题了。比如上面,foo(&args)里实际上是传的是struct xxx*指针的地址,但是foo的参数类型是va_list,即指向struct xxx[1]的指针,少了一层解引用。这样编译时只会报一个warning,而且乍一看foo的参数也很符合直觉,似乎没错,然而巨坑。可不可以直接改成struct xxx**呢?struct xxx是标准库实现自己定义的东西,直接用不太好。所以其他不变,foo参数那里改成`va_list*或者直接全用va_list`。

Next

剩下的好像都是OS的东西了,所以暂时先摸掉