计算机系统基础之状态机-PA1-1

os
, ,

这里是学习计算机系统基础(Programming Assignment)的实验文档, 全课程从 PA0 ~ PA4 5部分, 本篇是第二篇介绍 PA1, 也就是新手上路部分, 因为篇幅原因会拆分为 1-1 ~ 1-n 多个小节.

0x00. 前言

终于见到第一章?

说实话我真没想到见到第一章都要花这么多时间, 以为几小时就搞定了, 以前写 0x00 一般都是象征性的做个开场白, 或者简单说说背景之类的, pa 课程的确是从第一章就非常对我口味, 等不及要开始探索后续的主线旅程了~

预计平均耗时: 30小时 :)

  • task PA1.1: 实现单步执行, 打印寄存器状态, 扫描内存
  • task PA1.2: 实现算术表达式求值
  • task PA1.3: 实现所有要求, 提交完整的实验报告

0x01. 红白机

这里开天辟地篇章是从图灵机开始说起, 讲述他用一些数字电路的知识创造出了一个最小的计算机的故事. 说人话就是要实现一个简化的 NEMU (全系统模拟器), 这里作者用小时候玩的红白机/魂斗罗作为例子, 有了 NEMU, 就可以玩儿时记忆中的小游戏了, 这里官方提供了一个 fceux 环境, 以及测试用的 ROM 包, 据说是可直接看看效果的, 来试试

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
36
# 下载 ROM, 然后解压 rom 包 (ctrl+alt+t 打开终端)
tar jxvf rom.tar.bz2

make ARCH=native run mainargs=f1 # mario
# 编译启动后
 PRG ROM:    1 x 16KiB
 CHR ROM:    1 x  8KiB
 ROM MD5:  0xfe6e13d1382f94dc0a5391053c4096bc
 Mapper #:  0
 Mapper name: NROM
 Mirroring: Vertical
 Battery-backed: No
 Trained: No

Power on
Initializing video...
# 还是报错了, 看看啥问题, 好像是低版缺通用库依赖的问题, 搜一下..
apt-get install -y alsa-utils
# 装完还是报错. 更新: 如果出现这个错误多半是 GUI 组件里出里问题, 如果解决不了建议快照回退..
ALSA lib confmisc.c:767:(parse_card) cannot find card '0'
ALSA lib conf.c:4528:(_snd_config_evaluate) function snd_func_card_driver returned error: No such file or directory
ALSA lib confmisc.c:392:(snd_func_concat) error evaluating strings
ALSA lib conf.c:4528:(_snd_config_evaluate) function snd_func_concat returned error: No such file or directory
ALSA lib confmisc.c:1246:(snd_func_refer) error evaluating name
ALSA lib conf.c:4528:(_snd_config_evaluate) function snd_func_refer returned error: No such file or directory
ALSA lib conf.c:5007:(snd_config_expand) Evaluate error: No such file or directory
ALSA lib pcm.c:2495:(snd_pcm_open_noupdate) Unknown PCM default
^CExit code = 00

# 解决方式先把这个 sound 屏蔽掉, 重新启动后会卡在 "Initializing video..." 哈哈
sudo vi /etc/asound.conf
# 写入如下
pcm.!default {
    type plug
    slave.pcm "null"
}

另外, 安装 ccache 为重新编译加速, export PATH="/usr/lib/ccache":$PATH 后, 重启编译计时后发现 recompile 的速度会提升许多, 完成后准备工作差不多就做完了

更新: 舒服了, 在云主机通过 vnc 连上桌面之后, 终于见到了感人的马里奥画面 (我吃了🍄), i 开始, j 跳跃, 话说怎么没有声音呢?

image-20220112211806665

让我想想, 是不是没有装音频的驱动或者静音了啥的. 在声音配置里可以测试一下, 好像没有读出音频设备, 看看 VNC 文档, 官方说音频按钮灰色是因为声音功能是收费版才有的擦, 正当我准备试用30天, 我看到了这 “Audio is not yet supported on servers running MacOS“ (Oh, Jesus…). 好吧, 暂时无缘声音了… (请确认在配置好图形化后云主机做个快照 & 镜像)

如果你发现声音相关的驱动报错, 然后你直接屏蔽了它, 可能导致运行出现段错误(segmentation fault), 然后游戏运行几秒会很快闪退, 具体原因暂时未知, 但是我们可以尝试去定位一下 (发现定位失败了)

1
2
3
4
5
6
7
8
9
10
11
# 看看系统日志里的具体报错, 发现直接屏蔽音频应该不太可取
sudo dmesg

process 'pa/fceux-am/build/fceux-native' started with executable stack
show_signal_msg: 23 callbacks suppressed
SDLAudioP1[10667]: segfault at 0 ip 0000000000000000 sp 00007fccb124fd18 error 14 in zero (deleted)[100000+1000]
Code: Unable to access opcode bytes at RIP 0xffffffffffffffd6.
SDLAudioP1[14051]: segfault at 0 ip 0000000000000000 sp 00007f464b7fdd18 error 14 in zero (deleted)[100000+1000]
Code: Unable to access opcode bytes at RIP 0xffffffffffffffd6.
#.... 省略类似
traps: SDLAudioP1[20456] general protection fault ip:7fa232dd86f0 sp:7fa22fe4ad20 error:0 in libSDL2-2.0.so.0.14.0[7fa232d16000+fc000]

0x02. 选择主线

和 RPG 游戏一样, 一般都有个多个主线可供选择, 课程提供了 x86, mips32, risc-v32/64 三个主线, 其中第二条线难度大建议二刷再考虑, x86 在 pa2 (冯诺依曼) 会是最难的, 所以普通人还是从 risc-v32/64 比较合适. (还能体会“优雅”的指令集设计)

而要实现的 NEMU, 简单说就是一个用来执行其他程序的程序, 是一个模拟的计算机系统 (包括硬件). 关于 risc-v 的基本学习和介绍放在单独一章, 开始正式篇章, 先思考 1 + 2 + … + 100 的程序计算机是如何计算的.

最早设计计算机的先驱做了一些简单约定, 它们假设 CPU 是一个没有感情的执行机器, 只会按部就班的执行人给他的指令, 并且:

  • 执行完一条指令后, 就继续执行下一条
  • 通过特殊的计数器 (program counter) 来存储地址, 从而知晓执行到第几条指令了 (X86 中称为 EIP-Extended Instruction Pointer)

那么对 CPU 来说, 它就循环的一直做下面的三件事:

  1. 读 PC (程序计数器), 然后取出要执行的指令
  2. 执行指令
  3. 更新 PC (下一条执行指令地址)

那么说回原本的 1+2..+100 , 教程给了一个简单的汇编指令和 c 的对照, 最简单的理解就是每行相当于一条指令, CPU从第 0 行开始执行, 

1
2
3
4
5
6
7
// PC: instruction    | // label: statement
0: mov  r1, 0         |  pc0: r1 = 0; // r1, r2 是两个寄存器, 存储数据
1: mov  r2, 0         |  pc1: r2 = 0;
2: addi r2, r2, 1     |  pc2: r2 = r2 + 1;   // 怎么做加法是个问题
3: add  r1, r1, r2    |  pc3: r1 = r1 + r2;
4: blt  r2, 100, 2    |  pc4: if (r2 < 100) goto pc2;   // 怎么做判断? branch if less than
5: jmp 5              |  pc5: goto pc5; // 陷入死循环?

作者把可以执行这种最简单的程序结构称为 “图灵机”, 那么这里探索一下最小的必须条件:

  1. 有存储整个执行代码的存储器
  2. 有记录 CPU 执行到第几条指令的计数器
  3. 有存储中间/最后结果的寄存器
  4. 执行计算的加法器
  5. 重复的执行 CPU 三件套: “读 PC 取指令 –> 执行指令 –> 更新 PC”

这里面, PC 也可视为是寄存器, 理解为一个仅限于计数的寄存器就可了, 上面的部件大部分都是数电出现过的, 然后计算机把它们做一下组合, 然后让他们自动化执行起来, 就是最早的计算机了. (由此也可见”存储” )

思考题: 计算机可以没有寄存器么? 可以的话, 会对硬件提供的编程模型带来哪些影响? (TODO)

程序 & 状态机

这里首先提出把简单的计算机看成两个部分, 然后结合状态机的模型 (状态机我也不知道怎么解释简单点, 类似状态切换图吧.)

  • 时序逻辑部件: 存储/寄存器等
  • 组合逻辑部件: 加减法器等

每个时钟周期, 计算机根据时序部件的状态, 配合组合部件, 计算并转移到下一个(时钟周期)状态, 就符合状态机的最基本特性, 那如果把计算机看成一个状态机, 运行在之上的程序(program) 又是什么呢? 不妨先看看下面这个开关门的状态机, “开门”和”关门”作为两个操作 (事件), 让门会在 “开着” 和 “关着” 两个状态里切换, 简单看程序就是由一行行代码, 也就是一行行指令构成的, 这些指令就类似 “开/关门” 的操作, 交给计算机去执行 (有点像古代的圣旨么?)

stateDiagram
    门关 -->  门开: open
    门开 --> 门关: close

然后这里引入了一个状态可能计算, 作者假设一个简单计算机有 4 个 8 位寄存器, 1 个 4 位 PC, 一段 16 Byte 的内存:

  1. 推算出它可以存储的所有信息量最大值是: 4 * 8 + 1 * 4 + 16 * 8 = 164 (bit)
  2. 总的状态可能是 2^n^ , 据此算出有 2^164^ 这么多的确定状态变化. (思考: 为何是2^n^ 种组合 ?)

这里卡壳了不妨先把 n 设小, 比如为 n = 2 时, 也就对应上面的开关门, 总共 4 种组合可能: (再扩展到 3 就明白了?)

  1. 门关 –开门–> 门开
  2. 门关 –关门–> 门关
  3. 门开 –开门–> 门开
  4. 门开 –关门–> 门关

话说上面的理解对么 (ww).. 然后再试图画一下1+2+..100 的状态图, 先确认有哪些是可以变化的状态 (PC + 2寄存器), 按照提示把三个可变状态转为一个三元组 : (PC, R1, R2)

graph LR

a1(0, 0, null) --> a2(1, 0, 0) --> a3(2, 0, 1) --> a4(3, 1, 1) --> a5(4, 1, 2) --> a6(5, 3, 2)--> a7(...)--> a8(201, 5040, 100)--> a9(202, 5050, 100)

不知道 PA 的数值有没有写错, 讲义提出了两个互补视角看程序:

  1. 从静态视角 (代码/指令) , 通过循环/判断等组合可少量代码实现复杂功能, 但是缺乏对执行的细节掌握
  2. 从动态视角 (状态机转移), 通过观察程序在计算机运行的本质把代码进行细化展开, 虽然有许多的状态和细节, 但是对局部变化理解更深 (Q: 例如理解递归这种静态角度看很容易晕的, 通过展开递归树是否算动态视角?)

这节着重一个概念 —- “程序是个状态机”, 有助于理解后续 pa 课程里不少内容, 否则会很难进行

0x03. 框架初探

这里主要是说 pa 课程的项目框架和代码核心, 课程把 NEMU 模拟的计算机称为 “客户(guest)计算机”, 在 NEMU 运行的程序成为”客户程序” (有点拗口?)

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
pa(ics2021) # 根目录
├── abstract-machine   # 这啥?
├── am-kernels         # 基于 abs-machine 的应用程序
├── fceux-am           # 红白机模拟器
|
├── nemu              #####(当下只需要关心此)#####
│   ├── configs       # 预先提供的一些配置文件
│   ├── include       # 存全局使用的头文件
│   ├── Kconfig       # 配置信息管理的规则
│   ├── Makefile
│   ├── resource       # 一些辅助资源
│   ├── scripts
│   ├── src           # 核心源码
│   │   ├── am-bin.S
│   │   ├── cpu       # 指令执行主流程
│   │   ├── device
│   │   ├── engine    # 解释器
│   │   ├── filelist.mk
│   │   ├── isa       # 3大 isa 的抽象实现
│   │   ├── memory    # 内存访问
│   │   ├── monitor   # 简易调试器(监视点)
│   │   ├── nemu-main.c
│   │   └── utils
│   └── tools
├── init.sh
├── Makefile

简单的目录如上, 细节自己 tree 或者讲义看, 目前只看 nemu/src 的内容, 我下意识打开了 nemu-main.c , 详细代码在0x04里,

配置系统 kconfig

现实项目里可能会有许多配置项, 并且有些有依赖关系, 如果都让开发人员手动管理很容易出错, 例如开启 A 配置但没有关闭 B 配置, 配置系统出现就是为了解决此问题

kconfig 自己定义了一套简单的 dsl 来编写配置文件, Kconfig 的常见配置就是几类, 直接看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# config 配置普通配置, 给类型, 参数说明, 默认值, 依赖其他的参数等选项
config RT_CHECK
  bool "Enable runtime checking"
  default y  # bool 值选项 y 和 n

# choice-endchoice 组合代表n选1, 类似 switch-case
choice
  prompt "Build target"
  default TARGET_NATIVE_ELF
config TARGET_NATIVE_ELF
  bool "Executable on Linux Native"
config TARGET_AM
  bool "Application on Abstract-Machine"
endchoice

输入 make menuconfig 的过程其实就是调用 kconfig 生成配置文件的过程, 讲义让只用关注以下:

  • include/generated/autoconf.h, 看 C 代码时使用 (里面是一堆常量值)
  • include/config/auto.conf, 阅读 Makefile 时使用
项目构建

因为后续会需要新增和修改代码, 所以代码构建的流程的确需要清楚, 而且因为 c/c++ 包管理并不会特别智能, 所以很多细节还需要自己特别小心处理, 否则都容易引发连锁问题. 下面的讲解会比较枯燥, 我精简一下核心, 详细可以用到再回来翻.

1. filelist

在 src 下有一个 filelist.mk 文件, 看起来它有一些怪语法, 不过我们注意关心前 4 个变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
SRCS-y += src/nemu-main.c # 参与编译的源文件
DIRS-y += src/cpu src/monitor src/utils # 参与编译的目录 (汇到SRCS-y)
DIRS-$(CONFIG_MODE_SYSTEM) += src/memory
DIRS-BLACKLIST-$(CONFIG_TARGET_AM) += src/monitor/sdb # 不参与编译的文件

SHARE = $(if $(CONFIG_TARGET_SHARE),1,0)
LIBS += $(if $(CONFIG_TARGET_NATIVE_ELF),-lreadline -ldl -pie,)

ifdef mainargs
ASFLAGS += -DBIN_PATH=\"$(mainargs)\"
endif
SRCS-$(CONFIG_TARGET_AM) += src/am-bin.S
.PHONY: src/am-bin.S

上面一堆其实核心就是让 Makefile 统计项目编译时到底需要包含哪些文件 (SRCS-y), 上面还有一个写法是 XX 变量和$(config) 的组合, 实际是在 make menuconfig 时, 结合所选配置进行配置生成.

2. 编译和链接

上面 filelist.mk 说的是编译选择哪些文件, 然后 build.mk 说的是如何编译 (./scripts下), 打开又是一段天书, 编译相关:

1
2
3
4
5
6
# Compilation patterns, 首先这还是 Makefile 的语法, "target: files cmd..."
$(OBJ_DIR)/%.o: %.c
  @echo + CC $<
  @mkdir -p $(dir $@)
  @$(CC) $(CFLAGS) -c -o $@ $<
  $(call call_fixdep, $(@:.o=.d), $@)

莫慌, 这段也就 5 行, 猜一下, 第一行应该是选中所有 .o .c 结尾的文件, 然后接下来输出CC $< , 后面这个得查一下是啥:

  • %.o : 这里 % 是一个匹配符,
  • $(var:a=b) : 高级用法, 变量值的替换, 就是说把以 a 结尾的字符换成以 b 结尾,
  • @echo : 直接 echo 就能执行, 加个@ 的意思是
  • call: 这是内置的唯一可用来创建新参数化的函数,

特殊的一类, 高级用法之自动化变量, 是稍有些复杂, 如果完全看不下去可以先简单扫一下跳过.

  • $@ : 表示符合规则的目标集合
  • $<: 在读取%.o这类模式匹配时, 意思就是挨个取出每个符合条件的文件名

使用 make -nB 可以仅输出命令的方式输出编译过程, 直接执行会输出所有:

1
2
# 例如开头的部分, -O2 代表第三档编译器优化 (默认-O1), -Wall 输出所有警告信息, 
gcc -O2 -MMD -Wall -Werror -I/home/ubuntu/pa/nemu/include -I/home/ubuntu/pa/nemu/src/engine/interpreter -I/home/ubuntu/pa/nemu/src/isa/riscv32/include -O2    -DITRACE_COND=true -D__GUEST_ISA__=riscv32 -c -o /home/ubuntu/pa/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.o src/nemu-main.c

如果实在不习惯, 也可以用 sourcegraph 这种工具来查看

优雅退出

允许 nemu 后直接 q退出会报错 make: *** [/home/ubuntu/pa/nemu/scripts/native.mk:23: run] Error 1 , 我们来找找原因修复一下它.

0x04. 第一个程序

NEMU 是执行程序的载体, 那么如何载入这些程序呢? 核心流程在 monitor.c 中, 当 main 函数加载后, 可以看到首先就是初始化监听器, 然后启动主引擎.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <common.h>

void init_monitor(int, char *[]);
void am_init_monitor();
void engine_start();
int is_exit_status_bad();

int main(int argc, char *argv[]) {
  /* Initialize the monitor. */
#ifdef CONFIG_TARGET_AM
  am_init_monitor();
#else
  init_monitor(argc, argv);
#endif

  /* Start engine. */
  engine_start();

  return is_exit_status_bad();
}

src/monitor/monitor.c 的源码如下:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <isa.h>
#include <memory/paddr.h>

void init_rand();
void init_log(const char *log_file);
void init_mem();
void init_difftest(char *ref_so_file, long img_size, int port);
void init_device();
void init_sdb();
void init_disasm(const char *triple);

static void welcome() {
  Log("Trace: %s", MUXDEF(CONFIG_TRACE, ASNI_FMT("ON", ASNI_FG_GREEN), ASNI_FMT("OFF", ASNI_FG_RED)));
  IFDEF(CONFIG_TRACE, Log("If trace is enabled, a log file will be generated "
        "to record the trace. This may lead to a large log file. "
        "If it is not necessary, you can disable it in menuconfig"));
  Log("Build time: %s, %s", __TIME__, __DATE__);
  printf("Welcome to %s-NEMU!\n", ASNI_FMT(str(__GUEST_ISA__), ASNI_FG_YELLOW ASNI_BG_RED));
  printf("For help, type \"help\"\n");
  Log("Exercise: Please remove me in the source code and compile NEMU again.");
  assert(0);
}

#ifndef CONFIG_TARGET_AM
#include <getopt.h>

void sdb_set_batch_mode();

static char *log_file = NULL;
static char *diff_so_file = NULL;
static char *img_file = NULL;
static int difftest_port = 1234;

static long load_img() {
  if (img_file == NULL) {
    Log("No image is given. Use the default build-in image.");
    return 4096; // built-in image size
  }

  FILE *fp = fopen(img_file, "rb");
  Assert(fp, "Can not open '%s'", img_file);

  fseek(fp, 0, SEEK_END);
  long size = ftell(fp);

  Log("The image is %s, size = %ld", img_file, size);

  fseek(fp, 0, SEEK_SET);
  int ret = fread(guest_to_host(RESET_VECTOR), size, 1, fp);
  assert(ret == 1);

  fclose(fp);
  return size;
}

static int parse_args(int argc, char *argv[]) {
  const struct option table[] = {
    {"batch"    , no_argument      , NULL, 'b'},
    {"log"      , required_argument, NULL, 'l'},
    {"diff"     , required_argument, NULL, 'd'},
    {"port"     , required_argument, NULL, 'p'},
    {"help"     , no_argument      , NULL, 'h'},
    {0          , 0                , NULL,  0 },
  };
  int o;
  while ( (o = getopt_long(argc, argv, "-bhl:d:p:", table, NULL)) != -1) {
    switch (o) {
      case 'b': sdb_set_batch_mode(); break;
      case 'p': sscanf(optarg, "%d", &difftest_port); break;
      case 'l': log_file = optarg; break;
      case 'd': diff_so_file = optarg; break;
      case 1: img_file = optarg; return optind - 1;
      default:
        printf("Usage: %s [OPTION...] IMAGE [args]\n\n", argv[0]);
        printf("\t-b,--batch              run with batch mode\n");
        printf("\t-l,--log=FILE           output log to FILE\n");
        printf("\t-d,--diff=REF_SO        run DiffTest with reference REF_SO\n");
        printf("\t-p,--port=PORT          run DiffTest with port PORT\n");
        printf("\n");
        exit(0);
    }
  }
  return 0;
}

void init_monitor(int argc, char *argv[]) {
  /* Perform some global initialization. */

  /* Parse arguments. */
  parse_args(argc, argv);

  /* Set random seed. */
  init_rand();

  /* Open the log file. */
  init_log(log_file);

  /* Initialize memory. */
  init_mem();

  /* Initialize devices. */
  IFDEF(CONFIG_DEVICE, init_device());

  /* Perform ISA dependent initialization. */
  init_isa();

  /* Load the image to memory. This will overwrite the built-in image. */
  long img_size = load_img();

  /* Initialize differential testing. */
  init_difftest(diff_so_file, img_size, difftest_port);

  /* Initialize the simple debugger. */
  init_sdb();

  IFDEF(CONFIG_ITRACE, init_disasm(
    MUXDEF(CONFIG_ISA_x86,     "i686",
    MUXDEF(CONFIG_ISA_mips32,  "mipsel",
    MUXDEF(CONFIG_ISA_riscv32, "riscv32",
    MUXDEF(CONFIG_ISA_riscv64, "riscv64", "bad")))) "-pc-linux-gnu"
  ));

  /* Display welcome message. */
  welcome();
}
#else // CONFIG_TARGET_AM
static long load_img() {
  extern char bin_start, bin_end;
  size_t size = &bin_end - &bin_start;
  Log("img size = %ld", size);
  memcpy(guest_to_host(RESET_VECTOR), &bin_start, size);
  return size;
}

void am_init_monitor() {
  init_rand();
  init_mem();
  init_isa();
  load_img();
  IFDEF(CONFIG_DEVICE, init_device());
  welcome();
}
#endif

然后其他代码不贴了, 需要的同学可以自行查阅, 放一下关键的结构体:

1
2
3
4
5
6
7
8
9
typedef struct Decode { // 读取指令的解码器
  vaddr_t pc;
  vaddr_t snpc; // static next pc
  vaddr_t dnpc; // dynamic next pc
  void (*EHelper)(struct Decode *);
  Operand dest, src1, src2;
  ISADecodeInfo isa;
  IFDEF(CONFIG_ITRACE, char logbuf[128]);
} Decode;

0x0n.

参考资料:

  1. Introduction of C - RuanYiFeng
  2. Linux C - one step studying (recommend)
  3. How to write Makefile - Doc - 陈皓
  4. 南大-计算机系统基础 - 蒋炎岩