NJU-ICS|习题课#01

机制

编译和执行

程序最终由代码变为可执行文件实际上是跨越了编译、链接和加载执行这几个阶段的。

  • 广义上的编译

    • 广义上的编译其实指的是 .c 文件转化为 .o 文件这一整套过程。

  • 狭义上的编译

    • 而狭义上的编译指的是 .i 转化为 .s 这一段过程，剩下的其实是由汇编器，连接器来实现的。

通过 man gcc 我们很容易得出编译器提供了一些接口来实现仅让编译停留在某一阶段的功能

剧透：课程最后我们会知道其实 gcc 实际上确实是涵盖了所有的阶段，并且以外部指令的形式来调用。

预编译

首先我们先来看预编译阶段。

针对 c 语言而言，预编译阶段本质其实是字符串的拼接(和 shell 的设计哲学差不多)，又叫做元编程。

include指令

include另外的用处

#include 我们都知道是用来引用头文件的，在 c 语言中 #include 其实就是预编译阶段的一个例子，本质其实是把头文件的代码拼接到此文件中。

下面我们来看一个例子：

a.c 主函数，引用了 a.inc 文件

1
2
3
4
5
6
7
#include <stdio.h>
int main()
{
    printf(
        #include "a.inc"
        );
}

a.inc 内容如下，又引用了 b

1
#include "b"

b 内容如下

1
"HelloWorld \n"

执行

1
2
3
gcc a.c
.\a.exe
HelloWorld

可以看到上述的一个例子其实就打破了我们对于 #include 最基本的认识，这正是预编译阶段的最好体现，并且在很多大型的工程项目中都会出现 xxx.inc 文件的情况其实本质就是被引用的外部文件内容。

verbose

我们想要详细看下编译时候的各种过程，gcc 默认是不显示的，因此我们可以通过 --verbose (啰嗦)的方式来查看 gcc 的详细任务，其中包含了下面这段

1
2
3
4
5
#include "..." search starts here:
#include <...> search starts here:
 G:/DeveloperTools/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/include
 G:/DeveloperTools/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/include-fixed
 G:/DeveloperTools/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/../../../../x86_64-w64-mingw32/include

这就解释了我们在预编译阶段的 #include 中到底头文件是从那里得来的。

#inclde<>和#include””的区别

#include<> 表示会引用系统自带的标准库文件，#include"" 除了系统的文件外还会包含指定目录的 c 文件。

预编译一些有意思的code

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

int main() {
#if aa == bb
  printf("Yes\n");
#else
  printf("No\n");
#endif
}

上述代码预编译之后执行的结果其实是 Yes ，这确实是很违背常理的一个操作。

具体原因在于 预编译的阶段其实本质上是变量的复制黏贴。

  • #include → 粘贴文件
  • aa, bb → 粘贴符号

而由于我们上面 aa 和 bb 没有定义，因此这里其实第一个 if 这儿是 if 1==1 其实是成立的，因此会输出 Yes 。

宏展开

宏展开其实有点递归嵌套的意思在里面，如果使用恰当，我们可以玩的很花。

1
2
3
4
5
6
7
#define NAMES(X) \
  X(Tom) X(Jerry) X(Tyke) X(Spike)

int main() {
  #define PRINT(x) puts("Hello, " #x "!");
  NAMES(PRINT)
}
1
2
3
4
Hello, Tom!
Hello, Jerry!
Hello, Tyke!
Hello, Spike!

因此我们可以得出：宏定义的本质其实是：反复粘贴，直到没有宏可以展开为止

编译和链接

编译

其实 c 语言很接近我们的汇编语言了，基本上只需要用一些简单的代码转换即可看懂。

链接

将多个汇编完成的机器指令(二进制目标代码)拼接在一起

  • 自己写的其他文件中的 c 函数
  • 系统库中提供的函数例如 printf

加载执行

计算机本质其实是一个状态机。

C 代码的连续一段总能对应到一段连续的机器指令。

C 代码执行的状态总能对应到机器的状态。

代码、变量 (源代码视角) = 地址 + 长度 (机器指令视角)

内存 = 代码 + 数据 + 堆栈

C 里所有的数据都可以理解成是地址 (指针) + 类型 (对地址的解读)

编程实践

代码可读性

人类不可读版

1
void (*signal(int sig, void (*func)(int)))(int);

人类可读版本

1
2
typedef void (*sighandler_t)(int);
sighandler_t signal(int, sighandler_t);

注意这里的 typedef 指的是起别名。

Programs are meant to be read by humans and only incidentally for computers to execute. — D. E. Knuth

程序首先是拿给人读的，其次才是被机器执行。

实现数字电路模拟器

思路分析

假设我们现在要实现一个数字电路模拟器，一个最简单的数字累加功能。

因为是实现模拟器，数字电路本质其实就是 状态 (存储) 和 计算。因此我们的基本思路就是通过程序来模拟状态的存储以及计算。

我们都学过数字电路基础，因此这个地方通过真值表以及数逻知识可以很容易地得出如下的计算状态

  • 状态 = 变量
    • int X = 0, Y = 0;
  • 计算
    • X1 = !X && Y;
    • Y1 = !X && !Y;
    • X = X1; Y = Y1;

代码实现

下面是最初的版本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define FORALL_REGS(_)  _(X) _(Y) 
#define LOGIC           X1 = !X && Y; \
                        Y1 = !X && !Y;

#define DEFINE(X)       static int X, X##1;
#define UPDATE(X)       X = X##1;
#define PRINT(X)        printf(#X " = %d; ", X);

int main() {
  FORALL_REGS(DEFINE);
  while (1) { // 模拟时钟信号
    FORALL_REGS(PRINT); putchar('\n'); sleep(1);
    LOGIC;
    FORALL_REGS(UPDATE);
  }
}

其实现的基本思路很简单，首先对于所有的寄存器都先初始化，之后每一次时钟信号来临的时候，先打印出当前的状态，然后模拟计算，之后更新状态，以此重复操作。

新增需求

我们现在要新增一个需求，为了实现这个需求，新增了一个标识位 Z 来表示开关的状态。

这里其实就体现出了上面代码的可维护性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define FORALL_REGS(_)  _(X) _(Y) _(Z)
#define LOGIC           X1 = !X && Y; \
                        Y1 = !X && !Y; \
                        Z1 = !Z

#define DEFINE(X)       static int X, X##1;
#define UPDATE(X)       X = X##1;
#define PRINT(X)        printf(#X " = %d; ", X);

int main() {
  FORALL_REGS(DEFINE);
  while (1) { // 模拟时钟信号
    FORALL_REGS(PRINT); putchar('\n'); sleep(1);
    LOGIC;
    FORALL_REGS(UPDATE);
  }
}

我们只需要求改 FORALL_REGS() 中以及 LOGIC 中的定义即可完成新的需求的迭代。

实现 YEMU 全系统模拟器

最小的计算机

在书上其实提到了一个最简单的计算机系统，他只有五个 8 bit 的寄存器，一个 程序计数器，一个 16 byte 的内存。

同时它定义的指令集如下

1
2
3
4
5
       7 6 5 4   3 2   1 0
mov   [0 0 0 0] [ rt] [ rs]
add   [0 0 0 1] [ rt] [ rs]
load  [1 1 1 0] [   addr  ]
store [1 1 1 1] [   addr  ]

虽然是一个很简单很低配置的计算机，实际中根本不可能存在，但是我们依然可以利用它来学习 一个计算机是如何运作的。

  • 每一次其实都是从 PC 中取出指令的地址。
  • 然后执行指令，具体内存中指令的内容需要对照我们的指令集进行查找解释(一般来说是需要对寄存器或是内存进行数据操作的)。
  • 然后执行完了更新我们的寄存器数据，等待下一个时钟周期。

课件中的提炼

理论上我们可以 枚举 出这个最简单的计算机中所有的状态取值，因为每一位的 bit 我们都可以枚举出来。

如何用代码来实现

内存是 16 byte，算上 PC 一共有 5 个寄存器，因此我们的内存模型最多只需要分配 21 bytes = 168 bits 的空间。

我们很容易写出如下的代码：

1
2
3
4
5
6
#include <stdint.h>
#define NREG 4
#define NMEM 16
typedef uint8_t u8; //uint8_t 指的是我们无论是在 64/32 位的机器上都可以得到这个类型的数据为无符号 8bit 的整数数据
//然后我们定义了 8 bit 长度的 pc，寄存器数组 R（长度为4），内存数组 M （长度为16），单位都是 8bit 也就是 byte
u8 pc = 0, R[NREG], M[NMEM] = { ... };

补充：

  • 对于现在的计算机系统，8 bit 我们需要知道有一个和他一样长度的数据是 char
  • 除了 uint8_t ，在后续的框架代码中其实我们还会大量看见 intptr 这个类型，这个类型的意思指的是我们的整数类型数据的指针承接形式，因为我们都知道在 64/32 位机器上，指针类型分别是 8/4 字节的，如果我们简单地直接用 int 来承接指针类型，在64位机器上就会直接溢出，因此 PPT 这里的 quiz 其实答案就是应该使用 intptr 这个数据类型。这也解释了其实 intptr 这个数据类型本质上其实在 C 语言中就是数据+我们对指针类型的解读。

PPT上的Quiz

但是这个代码的可维护性还是不太好，比如说我们新增了一个寄存器，这个时候就需要改动 NREG 这段数据，因此我们这里可以简单重构：

1
2
3
4
5
6
7
8
9
10
11
12
//这里通过枚举的形式列出所有的寄存器
enum { RA, R1, ..., PC };
//数组初始化的时候对于每一个位置我们都清楚其内容意义
u8 R[] = {
  [RA] = 0,
  [R1] = 0,
  ...
  [PC]  = init_pc,
};

#define pc (R[PC]) // 把 PC 也作为寄存器的一部分
#define NREG (sizeof(R) / sizeof(u8)) //这里其实也很巧妙的处理了寄存器个数，让我们的整个寄存器数组大小除以每一个寄存器都是 8bit 的大小来间接计算出寄存器的个数

这里就引出了我们软件在设计的过程中代码应该如何写便于维护

模拟指令执行

我们之前已经强调很多次了，其实计算机本质就是在时钟信号的驱动下，根据(Memory,Register)来更新系统的状态。

  • 取指令 (fetch): 读出 M[R[PC]] 的一条指令
  • 译码 (decode): 根据指令集规范解析指令的语义 (顺便取出操作数)
  • 执行 (execute): 执行指令、运算后写回寄存器或内存
1
2
3
4
5
int main() {
  while (!is_halt(M[pc])) {
    idex(); //核心所在
  }
}

具体实现

这里的 idex() 其实就是上面的三个步骤，我们以课件中最简单的计算机为例来学习。

我们很容易可以写出如下的 if-else 判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void idex() {
  if ((M[pc] >> 4) == 0) {//高四位为0000
    R[(M[pc] >> 2) & 3] = R[M[pc] & 3];//mov操作  rt(低四位的高两位) = rs(低四位的低两位)
    pc++;
  } else if ((M[pc] >> 4) == 1) {//高四位为0001
    R[(M[pc] >> 2) & 3] += R[M[pc] & 3];//add操作 rt(低四位的高两位) += rs(低四位的低两位)
    pc++;
  } else if ((M[pc] >> 4) == 14) {//高四位为1110
    R[0] = M[M[pc] & 0xf]; //read操作
    pc++;
  } else if ((M[pc] >> 4) == 15) {//高四位为1111
    M[M[pc] & 0xf] = R[0];//store操作
    pc++;
  }
}

但是这个代码看着实在是太折磨了，完全没有可维护性而言。

我们可以抽取出公共部分，通过变量命名追加自然语言来提升代码的可读性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void idex() {
  u8 inst = M[pc++];//获取指令数据
  u8 op = inst >> 4;//获取指令中的操作符数据
  if (op == 0x0 || op == 0x1) {//如果为mov/add
    int rt = (inst >> 2) & 3, rs = (inst & 3);//抽取出rt和rs内容
    if      (op == 0x0) R[rt]  = R[rs];
    else if (op == 0x1) R[rt] += R[rs];
  }
  if (op == 0xe || op == 0xf) {
    int addr = inst & 0xf;
    if      (op == 0xe) R[0]    = M[addr];
    else if (op == 0xf) M[addr] = R[0];
  }
}

或者我们可以巧妙利用 c 的 union ,bitfield 以及 struct 来模拟两种不同的instruction解释行为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef union inst {
  //从低到高依次通过bitfield来获取数据
  struct { u8 rs  : 2, rt: 2, op: 4; } rtype;
  struct { u8 addr: 4,        op: 4; } mtype;
} inst_t;
#define RTYPE(i) u8 rt = (i)->rtype.rt, rs = (i)->rtype.rs;
#define MTYPE(i) u8 addr = (i)->mtype.addr;

void idex() {
  inst_t *cur = (inst_t *)&M[pc];
  switch (cur->rtype.op) {
  case 0b0000: { RTYPE(cur); R[rt]   = R[rs];   pc++; break; }
  case 0b0001: { RTYPE(cur); R[rt]  += R[rs];   pc++; break; }
  case 0b1110: { MTYPE(cur); R[RA]   = M[addr]; pc++; break; }
  case 0b1111: { MTYPE(cur); M[addr] = R[RA];   pc++; break; }
  default: panic("invalid instruction at PC = %x", pc);
  }
}
CS_Basic
#CSAPP #NJU
NJU-ICS|习题课#01
http://example.com/2022/12/12/NJU-ICS-习题课-01/
作者
Noctis64
发布于
2022年12月12日
许可协议