《汇编语言程序设计》学习笔记

这门课是 2021 年暑期学期开设的计算机系专业课，应该也算是为下学期的《计算机组成原理》课程做预备，所以还打算好好学一下。

课程基本介绍

汇编语言介绍

汇编语言可以认为是机器指令的一种表记方式，其表述了计算机硬件系统对外开放的主要接口和规格，是计算机系统之中的软硬件的分界。所以说要了解汇编语言，就首先需要了解机器指令。

机器指令系统一般分为两类：

• CLSC，即复杂指令系统。一般而言具有多种指令，寻址方式复杂，单条指令的功能较为复杂。较为经典的代表是 X86。

• RISC，即精简指令系统。考虑到实际使用的指令大多都是简要指令，故该系统只具有常用的精简指令。在这样的条件下，该指令系统依赖于编译器产生高效的代码（依赖编译器优化）。较为经典的代表为 MIPS。

目前，CLSC 和 RISC 之间的差别渐渐缩小。但是还是具有明显的区分方式的，即：

It loads / stores [with / without] other operations.

借助于连接软硬件的机器指令集，计算机系统实现了软硬件解耦合。这样软硬件可以独立编写，从而促进了计算机的发展。

注解：软硬件的分离的一个重要基石是图灵完备性。也就是说软件使用的高级语言是图灵完备的，硬件的指令序列也是图灵完备的，这两者完全等价。这样才保证了分离的可行性。

X86 指令集介绍

X86 指令集具有以下的基本特征：

• 向下兼容、变长指令、多种寻址方式

• 通用寄存器个数有限（X86-32 具有 8 个通用寄存器，X86-64 具有 16 个通用寄存器）

• 至多允许一个操作数在内存中，另外一个操作数需要在寄存器中或者是立即数

这里提到了寄存器。X86 之中的寄存器命名为：

寄存器名称【 X86-64 名称】	X86-32 名称	寄存器名称【 X86-64 名称】	X86-32 名称
%rax	%eax	%r8	%r8d
%rdx	%edx	%r9	%r9d
%rcx	%ecx	%r10	%r10d
%rbx	%ebx	%r11	%r11d
%rsi	%esi	%r12	%r12d
%rdi	%edi	%r13	%r13d
%rsp	%esp	%r14	%r14d
%rbp	%ebp	%r15	%r15d

由于 X86 重视向下兼容，所以其指令集越来越趋向于庞杂，所以其一个缺点就是资源利用率低。

MIPS 指令集介绍

MIPS 的设计思想是充分利用处理器的流水线结构，目标是让流水线各段负载均匀，这样可以让处理器频率得到提高。其特征包括：

• 以寄存器为中心，只有 Load 以及 Store 命令可以访问内存

• 所有计算操作均是从寄存器堆之中读取数据并将结果保存到寄存器堆，一共具有 32 个通用寄存器

• 指令格式规整、定长，且操作码位置固定，指令类型少（MIPS32 的指令只有 register / immediate / jump 三类）

• 寻址方式简单，每一条指令的操作过程简单

当然，MIPS 也具有一些被扩展过的扩展指令集，如 MIPS16e 等等。

此外，RISC-V 也是一种常用指令集。但其几乎和 MIPS 同源，故这里不作详细介绍。

整数的表示与计算

首先我们介绍一些简要表记，即 K / M / G / T / P / E。符号 K 表示 \(2^{10}\)，之后有 \({\rm M} = 2^{10} \cdot {\rm K}\) 以及 \({\rm G} = 2^{10} \cdot {\rm M}\)，依此类推。

同时我们将一个二进制位称为比特（bit），将八个比特称为字节（byte）。在 X86 架构下，两个字节称为一个字（word），而在 MIPS 架构下则是四个字节。

对于数的进制、二进制数的逻辑运算，这里不进行介绍。

机器字和字节序

首先引入机器字的概念，机器字指的是计算机进行一次整数运算所能处理的二进制数据组，也可以是一个数据地址。相应的，机器字长指的就是一个机器字的位数。对于 32 位字长的计算机，其地址能够表示的空间大小为 4GB 左右。机器字长越大的计算机，其地址的表示空间就越大。

机器字的定位为这个机器字第一个字节的地址，所以说相邻机器字的地址之差在 32 位系统之中为 4，而在 64 位系统之中为 8。

字节序指的就是一个机器字所包含的字节在机器字之中的排列的顺序，分为大端序（Big endian）以及小端序（Little endian）。大端序指的是低位字节占据高地址，小端序则相反。

比如说十六进制数据 0x01234567，如果这个机器字地址为 0x100。那么在大端序之下，0x100, 0x101, 0x102, 0x103 的字节内容分别为 01, 23, 45, 67。而在小端序下则是 67, 45, 23, 01。

整数的二进制编码

我们首先复习一下 C 语言之中各个数据类型的大小，这里以字节作为单位：

数据类型	经典 32 位系统	X86-32	X86-64
char	1	1	1
short	2	2	2
int	4	4	4
long	4	4	8
long long	8	8	8
float	4	4	4
double	8	8	8
long double	8	10 / 12	10 / 16
指针	4	4	8

这里我们为了简便，使用 16 位系统来演示整数的编码方式，也就是说机器字长为 16 位，一个整数使用 2 个字节表示。

有符号数的编码

对于非负的整数，显然可以直接使用其二进制表示作为其编码。比如说十进制数 12345，其二进制表示为 00110000 00111001，那么其编码就是 00110000 00111001。

对于负数，一种解决方式是使用最高位表记符号，最高位为 1 的数为负数，为 0 的数为非负数。然而这样会导致加法器在运算的时候需要首先验证符号位，计算出结果后还需要计算符号为，比较繁杂。所以说这里引入了补码（two's complement），用补码表示的整数可以简化有符号整数的计算。

非负数的补码就是其二进制表示，负数的补码是其绝对值的二进制表示按位取反之后加一。

比如说十进制数 -12345，由于 12345 的二进制表示为 00110000 00111001，首先按位取反得到 11001111 11000110，最后加一得到其补码为 11001111 11000111。

这个时候符号位依然存在，也就是说补码表示下负数最高位为 1，非负数最高位为 0。

补码的优越性在于简化了有符号整数的加法计算。如果我们使用 \({\rm TC}_w(x)\) 表示字长为 \(w\) 的系统下整数 \(x\) 的补码（比如 -12345 的补码为 11001111 11000111，后者直接转换为十进制表示的是 53191，那么定义 \({\rm TC}_w(-12345) = 53191\)）。实际上可以发现对于非负数 \({\rm TC}_w(x)=x\)，而对于负数：

\[ {\rm TC}_w(x) = 1 + \mathop{\sim}(-x) \]

而对于字长为 \(w\) 的系统，\(x + (\mathop{\sim}x) = 2^w - 1\)，所以说对于负数 \(x\) 有：

\[ {\rm TC}_w(x) = 1 + 2^w - 1 - (-x) = 2^w + x \]

所以无论如何我们都可以断定：

\[ {\rm TC}_w(x) \equiv x\ ({\rm mod}\ 2^w) \]

在这样的条件下做加法是简单的，因为一个整数和其补码在模 \(2^w\) 意义下等价。后面讨论补码条件下的加法的时候，即使出现截断，由于所截断的 1 必然位于不低于 \(2^w\) 的位上，所以截断还是不会影响模的结果。

对于字长为 \(w\) 的系统，按照补码表示的有符号数系统之中，最大的数为 \(2^{w - 1} - 1\)，而最小的数为 \(-2^{w - 1}\)。

无符号数的编码

无符号数的编码是简单的，因为其只需要考虑非负数，所以直接使用二进制表示作为编码就可以了。

这种系统之下，最大的数为 \(2^w - 1\)，而最小的数为 \(0\)。

有符号数和无符号数的关系和转换

现在我们已经给出了有符号和无符号整数的表示方式了。现在考虑将一个有符号整数强制类型转换为无符号整数，比如说在机器字长为 4 的时候，-4 的补码为 1010，而强转为无符号整数的时候，1010 则表示 12。其实不难证明对于字长为 \(w\) 的系统，有这样的关系：

\[ (\text{unsigned})x = \begin{cases} x & x \geq 0 \\ x + 2^w & x < 0 \end{cases} \]

这里提一下，在 C 语言的比较运算之中如果同时出现有符号数和无符号数，则会将有符号数强制转换为无符号数。当然，如果两边都是有符号数，则按照有符号数的比较规则进行。

事实上，由于这样的隐式转换，如果我们给声明为无符号整数的变量赋予一个负数值，就有可能被强制转换为一个大整数，从而导致违反直觉的结果，甚至导致错误。所以说我们应当谨慎使用无符号整数，一般而言，只有涉及到模运算或者单纯使用位运算的时候无符号整数比较适合。

整数的计算

无符号整数的加法

对于字长为 \(w\) 的系统，两个整数的加法可能会需要 \(w + 1\) 位才能表示，这个时候就会发生溢出。计算机的一般处理方式是舍去最高位，强制仅用 \(w\) 位表达计算结果，其实相当于对 \(2^w\) 取了模。也就是说，字长为 \(w\) 的、带有截断的无符号整数加法为（这里，符号 \(+^{\text u}_w\) 表示的是字长为 \(w\) 的系统下无符号整数的加法）：

\[ x +^{\text{u}}_w y =\begin{cases} x + y & x + y < 2^w \\ x + y - 2^w & x + y \geq 2^w \end{cases} \]

有符号整数的加法

在字长为 \(w\) 的、使用补码的系统下，对于有符号整数 \(x, y\)，其加法是有可能溢出的。

一种是两个大正数相加，超越了补码能表示的最大整数。此时补码的符号位承接了较低位溢出的 1，也就是说补码之和实际上代表一个负数。由于负数 \(u\) 的补码 \({\rm TC}_w(u) = u + 2^w\)，这个负数实际上就是 \(x + y - 2^w\)。这种情况被称为正溢出。

另外一种是两个绝对值很大的负数相加，超越了补码能表示的最小整数。此时补码符号位两个 1 相加得到 10，溢出为 \(w + 1\) 位数，但是最高位的 1 被截断。另外，较低的 \(w - 1\) 位不会向上进位（绝对值很大的负数的补码较低位所表示的数实际上会很小）。此时结果的补码符号位为 0，代表一个正数。由于负数 \(u\) 的补码 \({\rm TC}_w(u) = u + 2^w\)，考虑到截断了一个 1，所以该正数为：

\[ (x + 2^w) + (y + 2^w) - 2^w = x + y + 2^w \]

这种情况被称为负溢出。

对于求和结果在表示范围内的，补码的和（截断为 \(w\) 位后）就是和的补码。这是因为 \(x, y\) 的补码相加后截断，所代表的数与 \(x + y\) 模 \(2^w\) 同余，而 \(x + y\) 位于补码能表示的范围内，所以 \(x, y\) 的补码相加后截断得到的就是 \(x + y\) 的补码。

总而言之，字长为 \(w\) 的、带有截断的有符号整数加法为（这里，符号 \(+^{\text t}_w\) 表示的是字长为 \(w\) 的系统下无符号整数的加法）：

\[ x +^{\text{t}}_w y = \begin{cases} x + y - 2^w & x + y \geq 2^{w - 1} \\ x + y & -2^{w - 1} \leq x + y < 2^{w - 1} \\ x + y + 2^w & x + y < -2^{w - 1} \end{cases} \]

无符号整数除以 2 的幂

一般而言在计算机中，除法计算消耗的时间是相当长的。但是对于除数是 2 的幂的情况，我们可以使用移位的方式简化计算。

左移是很好理解的，溢出的部分会被截断，低位会用 0 补齐。但是右移的时候，低位截断是自然的，但是高位如何补齐则有两种方式。如果高位用 0 补齐，这种移位称为逻辑右移。如果用原数的最高位补齐（这里的最高位可以是 0，比如 16 位系统之中的 00000000 00000001 的最高位为 0），这种移位称为算术右移。

在字长为 \(w\) 的系统下，我们将无符号的逻辑右移标记为 \(>^{\text{ul}}_w\)，无符号的算术右移则标记为 \(>^{\text{um}}_w\)。

注解：有符号的右移则将上标的 \(\text{u}\) 替换为 \(\text{t}\)。

其实对于无符号整数 \(x\) 不难得到：

\[ x >^{\text{ul}}_w k = \left\lfloor \frac{x}{2^k} \right\rfloor \]

有符号整数除以 2 的幂

首先说明，我们希望除法的结果向 0 舍入，也就是说 23.6 舍为 23，-24.6 舍为 -24。

这里我们依然使用右移来简化除法计算。但是我们注意到负数除以 2 的幂之后必然还是负数，所以不能使用逻辑右移，只能使用算数右移。这个时候，对于有符号整数 \(x\) 我们可以简单地使用 \(x >^{\text{tm}}_w k\) 来计算 \(x / 2^k\)。

对于正数，这样的计算显然是正确的。但是对于负数，比如说 -15213，其补码为 11000100 10010011。我们计算其除以 256 的商，按照上面的计算方式即将其补码算术右移 8 位，得到 11111111 11000100，结果为 -60。然而我们知道实际的结果应当为 -59.43，按照舍入应当保留为 -59。

事实上我们可以说明：

\[ x >^{\text{tm}}_w k = \left\lfloor \frac{x}{2^k} \right\rfloor \]

也就是说使用算术右移计算有符号整数的时候永远得到向下舍入的结果。我们只要说明负数的情况即可，对于负数 \(x\) 的补码 \(x_{w - 1}x_{w - 2} \cdots x_0\)，我们设二进制数 \(x_{w - 1}x_{w - 2} \cdots x_k\) 表示数 \(x'\)，二进制数 \(x_{k - 1}x_{k - 2} \cdots x_0\) 表示数 \(x'' < 2^k\)。显然：

\[ 2^k x' + x'' = {\rm TC}_w(x) = 2^w + x \]

而 \(x >^{\text{tm}}_w k\) 得到的是 \(x_{w - 1}x_{w - 1} \cdots x_{w - 1}x_{w - 2} \cdots x_k\)，其表示数：

\[ x' + \sum_{i = w - k}^{w - 1} 2^i = x' + 2^{w - k}(2^k - 1) \]

按照补码去解读这个二进制串的话，其结果为 \(x' + 2^{w - k}(2^k - 1) - 2^w = x' - 2^{w - k}\)。也就能够计算得到：

\[ \left\lfloor \frac{x}{2^k} \right\rfloor = \left\lfloor \frac{2^k x' + x'' - 2^w}{2^k} \right\rfloor = \left\lfloor x' - 2^{w - k} + \frac{x''}{2^k} \right\rfloor = x' - 2^{w - k} = x >^{\text{tm}}_w k \]

为了修正这个舍入问题，我们可以尝试使用这样的一个性质：

\[ \left\lceil \frac{x}{y} \right\rceil = \left\lfloor \frac{x + y - 1}{y} \right\rfloor\ (y > 0) \]

也就是说我们只要在计算负数 \(x\) 的时候改变为：

\[ \left\lfloor \frac{x + 2^k - 1}{2^k} \right\rfloor = [x +^{\text{t}}_w (2^k - 1)] >^{\text{tm}}_w k \]

即可。

小数的表示

IEEE 浮点数标准

对于一个有小数部分的数 \(B\)，我们总是能找到唯一的 \(s \in \{0, 1\}\) 以及实数 \(M \in [1, 2)\) 和整数 \(E\) 满足：

\[ B = (-1)^s M \cdot 2^E \]

这里 \(s, E, M\) 分别称为符号、阶码和尾数。

基于这样的性质，我们可以给出小数的表示方式。将一片数据区域的最高位用于放置符号位 \(s\)，然后后面分割为两部分，即 exp 域和 frac 域，分别放置 \(E\) 以及 \(M\)。exp 域和 frac 域的具体大小有两种常见的制式（即单精度浮点和双精度浮点）。当然还有一些不太常用的分区方式，具体见表：

标准	exp 域长度	frac 域长度	浮点总长	备注
单精度浮点	8 bits	23 bits	4 字节
双精度浮点	11 bits	52 bits	8 字节
扩展精度浮点	15 bits	63 bits	10 字节	空置 1 bit
半精度浮点	5 bits	10 bits	2 字节

在具体存储的时候，尾数由于整数部分必然为 1，所以只需要将小数部分按顺序存储即可，而阶码使用无符号整数方法存储。

这里注意，阶码理应是有可能为负数的，但一般存储的时候会将阶码加上一个固定的偏置变成正数之后存储。如果阶码长度为 \(e\)，那么这个偏置就是 \(b = 2^{e - 1} - 1\)。

比如说按照单精度浮点的方式存储数 15213.0，其二进制表示为 \(1.1101101101101 \times 2^{13}\)。所以符号位为 0，尾数取小数部分前 23 位，即 1101101 10110100 00000000。阶码为 13，加上偏置 \(2^{7} - 1 = 127\) 得到 140，即 10001100。所以最后的存储方式为：

Bits

01000110 01101101 10110100 00000000

浮点数的非规格化

事实上，浮点数标准保留一部分阶码用于表示特殊的数字。一般而言，阶码全 1 和全 0 是被保留的。具体而言，阶码全 1 和全 0 的、表述特殊数字的浮点数被称为非规格化浮点数（denormalized float point），其余的被称为规格化浮点数（normalized float point）。

全 0 的阶码如果按照上述的标准解读的话，表示的是相当接近于零的小数。但是由于默认了尾数的整数部分为 1，所以说还按照原有解读方式的话，浮点数无法表示 0。这个时候作出规定，就是阶码全 0 的时候，尾数的整数部分变为 0。相应的，为了配合尾数解读方式的调整，阶码的偏置减去一。

假设某浮点数标准之中阶码长为 \(e\)，尾数长为 \(m\)。那么规格化的条件下最小的正浮点数应当是阶码为 00...01，尾数全 0。此时表示的数为 \(2^{1 - (2^{e - 1} - 1)} = 2^{2 - 2^{e - 1}}\)。在非规格化条件下，如果将尾数按照无符号整数解析得到的非负整数标记为 \(n\)，那么该浮点数应该为 \(2^{2 - 2^{e - 1}} \cdot 2^{-m}n\)。这里非负整数 \(n\) 取值范围为 \(0\) 到 \(2^m - 1\)。

所以说非规格化的浮点数所能表述的非负数序列为：

\[ 0, \ 2^{2 - 2^{e - 1}} \cdot 2^{-m} \cdot 1, \ \cdots, \ 2^{2 - 2^{e - 1}} \cdot 2^{-m}(2^m - 1) \]

这是一个公差为 \(2^{2 - 2^{e - 1}} \cdot 2^{-m}\) 的等差数列，而且最后正好可以和规格化浮点数所表述的最小正数 \(2^{2 - 2^{e - 1}}\) “无缝衔接”。所以说非规格化浮点数是一个合理的拓展。

但是，注意非规格化浮点数之中有 +0 和 -0 的区别。

全 1 的阶码用于表示很大的浮点数。一般而言尾数全 0 的时候该浮点数被保留用于表示无穷。而尾数有非 0 位的时候，该浮点数被保留用于表示 NaN。

---

现在补全了非规格化浮点数之后，可以发现浮点数的大小比较实际上几乎可以按照无符号整数从高位直接比较到低位的逻辑进行。因为阶码大的数一定大，阶码一样的时候尾数大的数一定大，包括无穷大也可以纳入进来。但是要考虑这样的例外：

• 考虑符号位

• 考虑 +0 和 -0 的特例

• 考虑 NaN 的问题

浮点数的舍入问题

由于部分数不能表述为有限的二进制小数，所以在转化为浮点数表示的时候需要舍入。一般而言向上舍入、向下舍入、向零舍入都会带来统计误差，而计算机之中常常使用向偶数舍入。其舍入的规则是向最接近的数舍入。如果向两边舍入的距离一致，那么优先舍入到偶数。比如说下列数之中，向百分位的舍入为：

\[ \begin{aligned} & 12.324999 \Rightarrow 12.32 \\ & 12.325001 \Rightarrow 12.33 \\ & 12.325000 \Rightarrow 12.32 \\ & 12.335000 \Rightarrow 12.34 \\ \end{aligned} \]

回到二进制上的话，由于十进制的 0.5 相当于二进制的 0.1。也就是说如果二进制小数之中后面需要舍去的部分大于 100... 则向上舍入，小于 100... 则向下舍入，恰好是 100... 则向偶数舍入（舍入完毕后尾数为 0）。

这里要注意一点，舍入是有可能导致溢出。

---

至此，小数的计算机编码方式基本就介绍完毕了。其具体过程为：

• 根据使用的浮点数标准，判定使用规格化的浮点数还是非规格化的浮点数

• 据此判定符号位、阶码和尾数

• 对尾数进行舍入后转化为二进制表示

C 语言的浮点数

C 语言之中，int 类型以及 float 类型是 4 字节的，double 则是 8 字节。它们之间的互相转换满足这样的规则：

• int 可以精确转换为 double 类型

• int 转换为 float 类型不会溢出，但有可能被舍入

• float 以及 double 转换为 int 时尾数截断，如果发生溢出则产生 UB

汇编语言基本知识

在这一部分，我们使用指令集架构（Instruction Set Architecture, ISA）来定义机器级程序的行为。在这个架构之中，CPU 内有一个记录下一条指令在主存储器之中位置的指令寄存器（Program Counter, PC），这个寄存器在 X86 体系中被命名为 %rip。CPU 之中同时还具有若干个寄存器，以及一个用于存储最近执行指令的结果状态信息的条件码寄存器。除去 CPU 外，这个架构之中还有主存储器，其可以认为是以字节为单元的一片连续的地址空间。

汇编语言的数据类型

和 C 语言不同，汇编语言不区分具体的数据类别，其不关心某一组二进制数据具体代表什么类型的数据。其不区分有符号和无符号的整数，甚至不区分指针和整数。其一般只区分数据的长度为字节、字、双字、四字。在处理这四种长度的数据的时候，指令的后缀分别为 b, w, l, q。比如说传送数据的命令为 mov，在传送字节的时候该命令写为 movb，在传送单字的时候该命令写为 movw 等等。

汇编语言的数据操作

汇编语言的基本操作只包括对寄存器或主存数据进行运算、在寄存器和主存内部或者之间传递数据、转移程序执行位置这三种。

在 X86-64 系统之下，寄存器是四字长的、通过名称访问的一片空间。但实际上有的时候指令可以不用访问整个四字长的寄存器空间，其可以通过 32 位操作访问四个字之中较低位的两个字，通过 16 位操作访问四个字中最低位的字，也可以通过字节操作访问最低位的字节。相应的，指代这一片寄存器空间的名称有所改变：

64 位操作	32 位操作	16 位操作	字节操作	64 位操作	32 位操作	16 位操作	字节操作
%rax	%eax	%ax	%al	%r8	%r8d	%r8w	%r8b
%rdx	%edx	%dx	%dl	%r9	%r9d	%r9w	%r9b
%rcx	%ecx	%cx	%cl	%r10	%r10d	%r10w	%r10b
%rbx	%ebx	%bx	%bl	%r11	%r11d	%r11w	%r11b
%rsi	%esi	%si	%sil	%r12	%r12d	%r12w	%r12b
%rdi	%edi	%di	%dil	%r13	%r13d	%r13w	%r13b
%rsp	%esp	%sp	%spl	%r14	%r14d	%r14w	%r14b
%rbp	%ebp	%bp	%bpl	%r15	%r15d	%r15w	%r15b

实际上，有的时候我们还可以用字节操作访问 %rax, %rbx, %rcx, %rdx 这四个寄存器的倒数第二低位的字节，指代这一部分空间的名称则为 %ah, %bh, %ch, %dh。

在具体进行操作的时候，一个机器指令往往需要跟随若干的操作数具体规定操作方法（如传送数据的时候，需要通过操作数指定传送的起始位置和终止位置）。操作数有三种表述方式：

• 立即数。其是一个整型的常数，写法为 $ 后接上一个 C 风格的数字表示这个立即数的值。比如说 $-521 以及 $0x4FD。

• 寄存器数值。直接使用寄存器的名称访问，如 %rbp 就代表这个寄存器之中的数据。但是注意，寄存器 %rsp 一般而言是被保留的。

• 主存数值。使用地址访问，其地址由某一个寄存器之中的数据指定，写法为寄存器名称加括号。比如说要访问某一个主存数值，其地址存储在寄存器 %rax 之中，那么其写法为 (%rax)。

汇编语言的寻址方式

X86 系统的变址寻址方式

但实际上，在 X86 系统中访问主存数值的方式（这也被称为寻址方式）并不是单一的。除去直接使用寄存器之中的数据作为地址去访问，X86 系统提供了包含变址、立即数偏移的寻址模式，其表记一般为 IMM(a, b, s)。这里 IMM 为一个立即数，称为立即数偏移，a, b 为两个寄存器名，分别称为定址寄存器和变址寄存器，s 为 1, 2, 4, 8 之中的一个数，称为比例因子。这个记号所代表的地址为：

\[ {\rm IMM} + {\rm R}(a) + {\rm R}(b) \cdot s \]

这里符号 \({\rm R}(a)\) 表示寄存器 a 之中的数据。

这个表记存在一系列简写：

• 当不存在定址和变址寄存器的时候，简写为 IMM。这个时候相当于不经过寄存器直接指定主存中的某一个地址，称为绝对寻址。

• 当 IMM 为 0，不存在变址寄存器的时候，简写为 (a)。这也就是最简单的寻址方式，即直接将寄存器数值作为地址解读，称为间接寻址。

• 当存在变址寄存器但 s 为 1 的时候，简写为 IMM(a, b)。

---

现在我们就可以尝试解读一些汇编代码了，比如：

X86-64 Assembly

movq $-147, (%rax)

这个指令的意思是按照四字数据转移的方式，将立即数 -147 写入主存，写入地址为寄存器 %rax 的数值。

利用寻址进行整数计算

地址实际上也可以被解读为整数，而机器进行寻址的时候实际上就在完成整数计算。根据上面给出的变址寻址方式，我们可以利用寻址命令来计算类似 \(x + ky\) 的整数算式。

首先需要知道指令：

X86-64 Assembly

leaq [SRC], [DEST]

这里 [SRC] 是一个寻址表达式，其计算出来的结果将赋给 [DEST]。比如 leaq (%rdi, %rdi, 2), %rax 会将前面寻址计算出来的地址赋予寄存器 %rax。

实际上在编译器优化之中，部分整数运算都会被优化为地址计算。比如说 x * 12 这个代码有可能会被转化为如下的汇编代码：

X86-64 Assembly

leaq (%rdi, %rdi, 2), %rax
salq $2, %rax

第一步使用地址计算实际上计算了 x + x * 2，即三倍的 x。第二步命令为左移，左移两位即再次乘以 4 得到最后结果。

汇编语言常用的整数计算命令

汇编语言计算整数运算的时候，会有如下表所列出的常用命令。

命令格式	等价的 C 代码	备注
addq [SRC], [DEST]	DEST = DEST + SRC
subq [SRC], [DEST]	DEST = DEST - SRC
imulq [SRC], [DEST]	DEST = DEST * SRC	结果取较低的 64 位截断
salq [SRC], [DEST]	DEST = DEST << SRC	与逻辑左移 shll 等价
sarq [SRC], [DEST]	DEST = DEST >> SRC	算术右移
shrq [SRC], [DEST]	DEST = DEST >> SRC	逻辑右移
xorq [SRC], [DEST]	DEST = DEST ^ SRC
andq [SRC], [DEST]	DEST = DEST & SRC
orq [SRC], [DEST]	DEST = DEST | SRC
incq [DEST]	DEST = DEST + 1
decq [DEST]	DEST = DEST - 1
negq [DEST]	DEST = -DEST
notq [DEST]	DEST = ~DEST

条件码与其应用

当程序运行的时候，部分和当前程序运行状态相关的数据将会被 CPU 保存。我们已经介绍过指向下一条指令的程序计数器 %rip，存储临时数据的寄存器堆。另外我们要提到的是被保留的寄存器 %rsp 其用于存储栈顶地址。另外提一下条件码，条件码一般分为四个：

条件码标记	名称	备注
CF	Carry Flag	进位标记
ZF	Zero Flag	运算数为零标记
SF	Sign Flag	运算数符号标记
OF	Overflow Flag	补码运算溢出标记

条件码一般是由算术指令运算过程中隐含地设定的，具体如何设定条件码需要查看具体的命令运行方式。这里额外指出，leaq 指令计算的时候不设置条件码。

推知操作数关系

若干以 set 为前缀的命令可以读取条件码的内容并存入某寄存器的最低位字节（使用字节操作）。比如说 setle 命令实际上会读取 SF, OF, ZF 三个条件码，将 (SF ^ OF) | ZF 的计算结果存入指定字节。

这个计算结果其实就代表了两个操作数之间的一个关系。比如说 cmpq [SRC], [DEST] 指令在 SRC == DEST 的时候会将 ZF 置真，在 DEST - SRC < 0 的时候将 SF 置真，在运算溢出的时候将 OF 置真。那么 setle 所计算的结果为真实际上就代表 DEST <= SRC。

这里给出具体示例，比如以下 C 语言代码：

C++

int gt(int x, int y) { return x > y; }

会被汇编为：

X86-64 Assembly

cmpq   %rsi, %rdi
setg   %al
movzbl %al, %eax
ret

其含义为首先使用 cmpq 命令更新条件码，然后使用 setg 命令读取条件码，最后使用 movzbl 将计算结果移动到表示函数返回值的寄存器。

实现程序跳转

对于 C 语言之中的 if, goto 等涉及到程序跳转的语句，汇编之中也应当有相应的可以跳转执行的命令，而条件码及其相关运算结果会控制程序是否跳转。与 set 系列命令一致，汇编之中还有 j 系列命令，如 je。其会读取条件码并计算，结果为真则会触发程序跳转。

比如这样的 C 代码：

C++

long absdiff(long x, long y) {
    long result;
    if (x > y) result = x - y;
    else result = y - x;
    return result;
} 

会被汇编为：

X86-64 Assembly

absdiff:
    cmpq %rsi, %rdi
    jle  .L4
    movq %rdi, %rax
    subq %rsi, %rax
    ret
.L4:
    movq %rsi, %rax
    subq %rdi, %rax
    ret

这里第三行就会读取 cmpq 命令设置的条件码，如果满足了跳转条件，就会跳转到 .L4 标记处继续执行，否则向下继续执行。

实际上，汇编代码的跳转基本和 C 语言之中的 goto 类似，所以我们可以将 if 转为等价的 goto 表达式，这样的话就可以得到和汇编代码形式类似的 C 代码。对于以下的 C 代码：

C++

if (CASE) { /* IF BLOCK */ }
else { /* ELSE BLOCK */ }

实际上等价于以下 C 代码：

C++

if (!CASE) goto Else;
    /* IF BLOCK */
    goto Done;
Else:
    /* ELSE BLOCK*/
Done:

使用条件码实现程序跳转的方式称为条件跳转。但实际上，条件跳转一般会拖慢整个系统的速度。这是因为现代的流水线式处理器一般要求系统能够基本精确得知接下来应当运行的指令是什么，这样才能保证并发执行，获得高效率。

为了解决这个问题，一种方法是提高处理器对下面具体运行哪一个分支的预测准确率，一种方法是使用条件转移。

条件转移指的是将两个分支的结果都计算出来，最后再根据条件码决定取用哪一个。比如说上面的 absdiff 函数，现代编译器一般会把 x - y 和 y - x 都计算出来，最后根据条件码取其中一个放到返回值寄存器上。

但是条件转移的使用是有局限性的，比如说下面两种情况就并不适合：

• 某一个分支有副作用，比如说修改了某些其他数据

• 某一个分支的计算量过于庞大

除去 if，C 语言中还可以使用 switch 语句实现程序跳转。switch 语句可以翻译为若干的 if-else 组，但是更常见的解读方式是构建跳转表。

TODO

实现程序循环

C 语言之中使用关键字 do, while, for 可以实现程序循环，同样我们可以使用条件码和 j 系列命令完成等价汇编代码编写，实际上我们只需要改写为等价的 goto 表达的 C 代码就可以。

对于 do ... while 循环，等价改写为：

C++

/* do ... while */

do { /* CONTENT */ } while (CASE)

/* goto */

Loop:
    /* CONTENT */
if (CASE) goto Loop;

对于 while 循环，等价改写为：

C++

/* while */

while (CASE) { /* CONTENT */ }

/* goto v1 */

goto Test;
Loop:
    /* CONTENT */
Test:
    if (CASE) goto Loop;

/* goto v2 */

if (!CASE) goto Done;
Loop:
    /* CONTENT */
if (CASE) goto Loop;
Done:

而 for 循环一般是改写为等价的 while 循环后再改写为 goto 版本：

C++

/* for */

for (/* INIT */; CASE; /* UPDATE */) { /* CONTENT */ }

/* while */

/* INIT */
while (CASE) {
    /* CONTENT */
    /* UPDATE */
}

函数调用与程序栈

程序栈和相关指令

X86 系统中，将一片内存区域按照栈的方式管理，其中高地址为栈底，这片内存区域就被称为程序栈，其栈顶地址由寄存器 %rsp 管理。

对程序栈有两种最为基本的操作，即压栈和出栈。压栈操作命令为 pushq [SRC]，含义是将 [SRC] 写入程序栈，寄存器 %rsp 减小一个字节（即减去 8）。而出栈命令为 popq [DEST]，含义是将程序栈栈顶字节写入 [DEST]，寄存器 %rsp 增加一个字节（即加上 8）。

函数调用

有关函数调用的两个命令为 call 和 ret，两者分别代指调用某一个函数和某一个函数返回。

注解：似乎在汇编之中，更习惯把函数调用说成过程调用，我们之后也使用这样的名称。

call 的命令格式为 callq 40050 <mul>。两个参数分别为需要调用的过程的机器码在主存里的位置，系统根据这个参数令程序指针 %rip 跳转。第二个参数则是调用的过程的名称。

call 命令一共会完成两个任务。第一个任务是将返回地址（返回地址指的是 call 指令下一条指令的地址）压入程序栈，这一步是为了在调用的过程终结返回的时候能够返回到正确的位置继续执行。第二个任务是将 %rip 设置为要跳转的过程在主存之中的地址，实现真正的跳转。

而 ret 命令所完成的就是将程序栈的栈顶写入 %rip，让系统回到原先位置继续执行。其不需要接受参数，一般只需要命令本身即可。

---

有的时候调用过程需要传递参数。在 X86 架构之下，如果传递参数不多于 6 个，则使用 %rdi, %rsi, %rdx, %rcx, %r8, %r9 一共 6 个寄存器进行传递。如果参数多余 6 个，则使用程序栈传递，序号越大的参数越在栈底。而函数返回值默认存放在 %rax 之中。

栈帧

类似 C 之类的语言，会支持函数的递归调用，这就说明了这些语言的代码支持重入（Reentrant），即允许多个实例同时运行同一块代码。基于这样的要求，我们不仅需要在程序栈之中记录返回地址，我们还需要记录是哪一个实例调用了过程。而每一次过程调用就会在程序栈之中生成一片用于记录这次调用的数据（包括这一次调用的临时变量、返回地址、寄存器副本等），这就是一个栈帧（Stack frame）。

栈帧的管理也是简单的，在过程被调用的时候分配空间、创建栈帧，在过程返回之后，该栈帧被释放。由于栈帧一般多于一个字节，所以除去栈顶指针 %rsp 外，还设定了栈帧指针 %rbp 标记栈帧的起始地址，所以 %rbp 和 %rsp 之间的程序栈指代栈顶的栈帧。

---

另外我们也需要指出，有的时候系统会做出一些“明明没有分配栈帧（%rsp 没有动）但相当于创建了临时栈帧”的行为。一种可能是使用栈空间进行数据传递，这个时候栈就类似于寄存器。比如说系统可以在不动 %rsp 的条件下将数据通过比 %rsp 低一个字节的位置传递一定的数据。但栈空间的也是有限制的，比 %rsp 低多于 128 字节的栈空间一般是被保留的，不能直接使用。

寄存器使用惯例

在一个过程调用另外一个过程的时候，往往会出现寄存器冲突，比如说两者都需要使用 %rdi 存放参数。这个时候一般需要将寄存器数据复制到栈帧之中暂且保存，将寄存器空出给另外一方使用。

而到底由调用者还是被调用者的栈帧暂存寄存器，则一般遵循一些惯例。在 X86 架构下寄存器 %rbx, %rbp, %r12, %r13, %r14, %r15 称为被调用者保存（Callee saved）寄存器，即被调用者的栈帧保存这些寄存器的数据，在过程返回之前将栈帧数据复原。寄存器 %r10, %r11 和所有的传递参数的寄存器称为调用者保存（Caller saved）寄存器，即调用者的栈帧保存寄存器的数据，在调用结束后将栈帧数据复原。

数组及结构的存储表示

数组的存储

数组 T a[N] 在主存之中存储的基本原则为连续存储，也就是将连续 N * sizeof(T) 字节的空间用于存储这个数组。

而对于二维数组，我们还是会使用连续的存储空间进行存储，而且一般遵循行优先原则。对于 int a[3][5]，其在主存之中的存储顺序为 a[0][0], a[0][1], ..., a[0][4], a[1][0], ..., a[2][4]。这种存储方式称为嵌套数组（Nested array）。

除了嵌套数组，还有一种存储方式是多级指针数组（Multi-level pointer array）。其基本想法为在根数组上存若干指针，这些指针指向下一级数组的起始地址。这样的存储方式方便进行多级扩展，但相应的由于内存空间不连续，而且读取指针并定位需要多次寻址，一定程度上降低了效率。

结构的存储

一个结构体的数据是将其成员按照声明顺序，在一片连续的空间内存储的。比如说：

C++

struct node {
    int[4] val;
    size_t i;
    node* next;
};

其将会在连续的 32 个字节中存储这个结构体，其中低地址的 16 字节存放 val，中间的 8 字节存放 i，高地址的 8 字节存放 next。

而在实际存储的时候是需要考虑对齐问题的：

C++

struct align {
    char val;
    align* next;
};

如果按照正常思维推测，一个字符和一个指针应该只需要 9 字节，但在 X86-64 架构下，实际上会占用 16 字节，其中低地址的 8 字节仅有最低一个字节存储了 val，而剩余的为占位符。

原因是简单的，现代的 CPU 在从主存之中读取数据的时候是同时读取多个，比如说一次性读取 8 个字节。实际上这种读取方式就将每 8 个字节的存储空间划分为了一个机器字（机器字的定义见 绪论），如果数据在同一个机器字之中，那么一次读取就可以将所有数据读出来。但如果数据跨越了两个机器字，那么就需要两次读取。

所以说编译器会故意在存储结构的空间内部塞入若干的空白空间让每一个成员的数据不跨越机器字以保证读取效率。

另外我们也注意到，变量的声明顺序实际上会影响具体的空间分配。比如说：

C++

struct S1 {
    char a;
    S1* next;
    char b;
};

struct S2 {
    char a;
    char b;
    S2* next;
};

这里，结构 S1 占用 24 字节，而结构 S2 占用 16 字节。这是因为 S1 在存放 a 后不得不空出 7 字节，否则 next 就会跨机器字。而 S2 中可以先把 a, b 都放置好之后，只需要空出 6 字节就可以让 next 不跨机器字。

联合数据的存储

联合数据类型可以定义多个成员，但是一个联合数据类型的变量在任何时候只能指代某一个成员。这些成员享有同一片存储空间，而联合所占据的空间即其中最大成员占据的空间。比如说：

C++

union U1 {
    int[2] i;
    char c;
    double v;
} *p;

这里联合的三个成员分别应该占用 1 字节、 8 字节、 8 字节，所以最后联合占据 8 字节。

程序的链接

链接的基本概念

多个源代码文件编译成为可执行文件的时候需要经过一个重要过程，即链接（Linking），含义就是将各个独立的文件链接为单一的最终文件。这样做的好处是，某一个文件发生修改，只需要对这个文件编译并重新链接即可，不需要再次编译其他文件。同时，一些常用函数可以事先编译为一个库，需要使用的时候再将其链接进入最后的可执行文件即可。

链接之前，编译器首先会将每一个源代码文件之中每一个符号存储起来，存储的内容包括符号名称、其占据的内存大小和其在主存之中的地址，这就构成了符号表（Symbol table）。随后链接器将所有源代码文件综合为单个文件后，会将符号表之中的地址更新为绝对地址。

ELF 格式和符号分析

可以被链接的文件一般有可重定向对象文件和共享对象文件，前者扩展名通常为 .o，后者则多为 .dll / .so。后者是特殊类型的重定向对象文件，可以被装载入内存后进行动态链接，其链接可以在装载时或者运行时完成。上述两种文件以及可执行文件，这三种二进制文件都必须要符合 ELF（Executable & Linkable Format）格式。

ELF 格式的文件依次具有以下的部分：

• ELF header 部分。这一部分会存储与这个文件相关的基本信息。

• Segment header table。这一部分只有可执行文件具有，会存储一些和可执行相关的内容。

• .text 部分。这一部分存储代码。

• .rodata 部分。这一部分存储只读数据，比如说跳转表。

• .data 部分。这一部分存储初始化过的全局变量。

• .bss 部分。这一部分存储未初始化的全局变量。

• .symtab 部分。这一部分存储符号表。

• .rel.text 部分。这一部分是 .text 部分的重定向信息。

• .rel.data 部分。这一部分是 .data 部分的重定向信息。

后续还有一些部分，这里暂且不用讨论。

这里可以提一下 .bss 区设立的原因。.bss 区域的数据不会存储数据类型，并且会默认将这一部分数据的每一个字节全部置 0x00，作为系统默认的初始化。这样做显然要比既要存储数据类型，又要存储数据初始值的 .data 区高效。而能够这样粗暴解决问题的原因是系统约定了非静态全局变量的默认初始化方式为全 0，以及汇编并不区分各种不同的数据类型。

---

在叙述链接过程之前，我们首先要叙述符号的概念。一个程序之中的符号分为三类，即全局符号、局部符号和外部符号。注意，这里全局符号和局部符号的区别不是全局变量和局部变量的区别。局部符号指的是在该模块定义且只可以让该模块引用的符号，包括静态和非静态的局部变量、静态函数和静态全局变量。而全局符号则是可以供给其他模块使用的符号，包括非静态的全局变量和函数。

首先说外部符号，其含义很简单，就是引用的其他模块的符号。包括其他模块开放的非静态全局变量和函数。可以用 extern 关键字声明外部符号，即声明该符号将会在链接的时候再具体给出定义，本文件只是做一个引用。

程序中定义的非静态局部变量，链接器并不会分析。非静态局部变量将会在运行的时候被存储在程序栈之中，使用完立刻释放。

而静态局部变量会被存放在可重定向文件之中的 .data 或者 .bss 部分。对于命名冲突的静态局部变量，编译的时候会给他们赋予后缀以示区分。

对于静态的全局变量和函数，其实际上是局部符号（static 关键字限制了这些变量和函数只能在本模块之中使用），所以其存放在可重定向文件之中的 .data, .bss, .text 部分。其中函数存放在 .data 部分。而如果多个文件中声明了同名的静态全局变量和函数，并不会冲突。

非静态的全局变量和函数一般也是存放在 .data, .bss, .text 部分。这个时候也有可能出现命名冲突，但此时必须作出区分。此时需要引入强符号（Strong symbol）和弱符号（Weak symbol）的定义。这个定义只对非静态的全局变量和函数成立，其中未被初始化的非静态全局变量被称为弱符号，否则是强符号。

链接器的原则是：

• 不允许出现强符号命名冲突，否则链接失败。

• 有强符号和弱符号的命名冲突则将弱符号的指代指向强符号（强制覆盖弱符号）。

• 弱符号之间的命名冲突，则任取其中之一作为代表，其余弱符号指向被选中的弱符号。

由于存在强制覆盖，我们应当减少全局变量的使用，或者使用静态的全局变量。如果需要使用，尽量将其初始化变为强符号。并且在使用其他模块的全局变量的时候，尽量先使用 extern 关键字声明这个变量。

代码和数据重定向

在处理完毕符号后，就可以开始链接了。现在有若干的可重定向对象文件，其中 .text 部分存储着代码，.data 部分存储着变量数据。这些文件的代码之中可能包含着函数调用，而我们知道函数调用需要知道函数在内存之中的位置。编译器在编译生成可重定向对象文件的时候有两个重要信息是不了解的：

• 这个模块之中的函数最终会被存放在内存的什么地方。

• 这个模块所引用的其他模块的函数的地址是什么。

针对第一个问题，编译器会存放相对地址，也就是这个模块之中的所有函数的地址都是相对于这个模块而言的，而不能表示最后的绝对地址。针对第二个问题，编译器可能会选择将地址留空，比如使用 0x00 留空，之后会在 .rel.data 或者 .rel.text 部分留下信息告诉链接器要补全这里的地址。

到这里，编译器的任务就完成了，接下来链接器会修正相对地址并填充留空地址。

首先链接器会将所有可重定向对象文件的 .data 部分拼接为可执行文件的 .data 部分，.text 部分也如此。拼接完成后，所有函数和全局变量的绝对地址就确定了，链接器会将所有需要调整的相对地址调整为目前的绝对地址，并填充留空地址。

库链接

我们提到过，一些常用函数会被事先编译为可重定向对象文件，在使用的时候再链接进入程序。但是一般而言这样的函数库是很大的，如果完全链接进入，则相当消耗时间空间。所以有另外一个解决方案，就是将每一个函数都打包为可重定向对象文件，然后把这些可重定向对象文件打包为静态库文件，也称归档文件（Archive file）。归档文件的扩展名常常为 .a。

归档文件之中每一个可重定向对象文件是具有索引的，基于此，我们让链接器能够在用户编写的代码之中解析外部符号，并且能够在静态库之中寻找出相应的可重定向对象文件进行链接。

现代的静态库一般允许增量更新。

静态库的缺点在于可执行文件以及运行时内存之中会重复包含库文件函数和数据，同时如果库文件发生变动，则所有的相关文件都需要重新链接。目前已有的解决方式是使用共享库文件，其特征在 ELF 格式和符号分析 部分已经说明。

内存布局与缓冲区

在 X86-64 架构下，主存的最高地址部分是程序栈，其栈顶由 %rsp 管理，且栈空间向低地址增长。程序栈一般具有 8MB 的空间限制。程序栈用于存放局部变量等数据。

之后就是分配给每一个任务的存储空间，每一个任务都会在主存之中占用一片空间，这片空间从高地址到低地址的分配为：

• 堆。堆空间可以根据程序需要动态分配，如 C 语言的 malloc 函数。堆空间向高地址增长。

• 静态数据。这一部分数据会在将可执行文件加载到主存的时候写入内容，写入的内容就是可执行文件的 .data 部分，称为数据段。

• 机器代码。这一部分就是可执行文件的 .text 部分，称为代码段。

而程序栈的构成，先前已经叙述过。即分为若干的栈帧，其中栈帧高地址的 8 字节存放这个栈帧的返回地址，剩余的部分存放临时变量等数据。

---

这个时候就可以引入缓冲区溢出攻击了。这个攻击利用的是类似 gets() 等不限制读入长度的函数，可能会越过预留空间对程序栈进行非法写入的漏洞。

比如说函数 foo() 之中调用了 gets()：

C++

void foo() {
    char buf[4];
    gets(buf);
}

而函数 foo() 执行的时候是会分配一个栈帧给这个函数存放 buf 这个临时变量的。但是由于 gets() 不限制读入长度，所以我们可以输入相当长的字符串，这样的话就会一直向栈帧的高地址写入，从而会覆写掉返回地址，甚至是上一个函数的栈帧。这样，在 foo() 结束进行返回的时候，就可以控制其跳转到指定的位置执行我们注入的程序。

防御这种攻击的方法也很多。一种是使用可以限制读入长度的函数，如 fgets()。一种是给栈内部加入随机长度的无意义数据，让攻击方无法准确预测 PC 应当跳转到何处。还有比如说可以限制执行权限，让这一片区域的内存不能作为机器指令执行。此外还可以让函数在返回之前检查栈帧是否被修改等等。

X86 汇编编程基础

TODO

异常

基本原理

异常（Exception）指的是会阻止程序正常执行，并且会引起状态切换（比如从用户态切换到内核态）的事件。异常分为同步异常和异步异常。

同步异常一般有三种，即 Trap、Fault 以及 Abort。其中，Trap 一般是由程序主动触发的，比如说产生了系统调用 syscall，或者是触发了断点或者是使用了 Trap 命令，其恢复之后会跳转到原命令的下一条继续执行。Fault 往往是由程序出现的一些问题触发的，一般这种问题都是可以恢复的，恢复之后会重新执行原命令。Abort 则是由不可恢复的问题触发的异常，会引起程序退出。

异步异常则一般由外部事件触发，比如说 IO 设备中断，发生系统重置等等。一般而言，在 MIPS 架构下，如果发生的时候命令已经执行完毕 MEM 阶段，系统会保证这条命令的流水线执行完毕。否则这条流水线会被废弃。这里有关 MIPS 流水线的叙述可以查看下面的 MIPS32 基础。

虚拟内存

基本原理

我们先前提到过，每一个进程都会分配到一片内存空间，用于存放数据段、代码段并且分配堆空间。但是我们也会注意到，有的进程用不到如此大的内存空间，很容易出现分配了空间但几乎不可能使用的现象。这个问题的一个解决方案是虚拟内存（Virtual memory），其相当类似于懒分配，即真正使用到某一块内存的时候再进行分配。

虚拟内存的工作原理大致为，对于每一个新进程，会分配连续的虚拟内存空间。进程使用到某一个存储地址的时候，处理器会去虚存地址和物理内存地址对照表（这个表一般称为页表（Page table），并且每个进程都会有自己的页表）之中寻找这个虚拟内存地址所对应的真实地址，如果发现还没有给这个虚存地址分配物理内存空间，则会分配并建立两者之间的映射。

虚拟内存地址通常简称为虚址（Virtual address）。上述过程中负责将虚址转换为物理地址的单元称为内存管理单元（MMU）。

页和页缺失

一般而言，我们会将一片固定大小的连续虚存集合起来成为一个页（Page），而每一个虚存的页映射到物理地址空间也是一片连续的空间，这被称为页帧（Page frame）。相对应的页和页帧具有相同的大小。MMU 进行地址映射的时候都是以页为单位的。

基于页的结构，处理器实际上传输给 MMU 进行转换的虚地址可以分为两个部分。前半部分为虚页码（Virtual page number / VPN），后半部分是页内偏置（Page offset）。虚页码指明了虚存之中我需要映射的字节位于具体哪一页，而页内偏置则表明了我需要映射的字节在页内是第几个字节。

MMU 所进行的页码映射就是将虚页码根据页表映射为物理页码（Physical page number / PPN），之后根据页内偏置获取最后实际的数据。

如果某次映射之中，某个页没有找到对应的页帧，就会触发页缺失（Page fault）。页缺失产生后，系统会转入内核态，调用异常处理代码将所需要的数据从外部存储读入内存以解决异常。

页表项的附加标记

采用虚存机制还有一种好处，就是可以通过页表实现权限管理。页表之中的每一项除去记录页和页帧的映射之外，还可以记录这个进程对物理内存的访问权限，权限控制的具体实现则由硬件完成。

另外，页表项还可以记录目前这个映射是否成立，这一位也常常被称为 valid 位。其为 1 则说明对应的页帧已经被加载到物理内存之中，否则代表对应的页帧还需要从外部存储之中获取。页缺失就会在 valid 位为 0 的时候发生。

快表机制

记住这一句话就可以了：

快表（TLB）和页表的关系，就是缓存（Cache）和内存的关系。

TLB 相当于页表的一个高速缓存，其出现的原因是处理器所请求的内存地址往往是聚集的，也就是说某一小部分地址占据了处理器的大部分请求。所以这个时候我们可以将常用地址缓存到 TLB 之中，请求内存的时候首先查询 TLB 有无相关映射，命中则直接使用。否则再去页表之中查找，命中则直接使用，同时将这个映射缓存到 TLB 之中。TLB 满了之后会触发淘汰机制，删去使用较少的映射项。

之所以提到缓存，因为内存之中的常使用部分会被加载到 cache 之中。而系统从 MMU 获取物理地址之后也会先去 cache 之中查找，找不到才会去内存之中查找。这个过程和 TLB 机制几乎一致。

内存映射

TODO: We may learn it later from OS class.

MIPS32 基础

MIPS 架构的特征可以查看本文最开头的部分，有较为详细的介绍。

这里补充一些其他的 MIPS 基础知识。这些知识并不是重点，但是会影响对 MIPS 架构细节的理解，故不单独开一个二级标题但还是需要分点一条条列出：

• MIPS 架构之中，一个字等于四个字节

• MIPS 架构下返回地址不保存在栈上，而是保存在 31 号寄存器之中

• MIPS 架构下 0 号寄存器永远存储常数 0

• MIPS 架构不具有条件码，条件的表示全部使用寄存器

• MIPS32 架构除去 32 个通用寄存器，还有高位寄存器 %hi 以及低位寄存器 %lo。这两者都是 32 位寄存器，其出现的原因是需要处理整数的乘除法。另外需要注意，MIPS32 架构的立即数通常只允许 16 位，而寄存器是 32 位的，所以通常会使用这两个寄存器将 32 位数拆开表示。记号上，%hi($1) 这种写法代表 1 号寄存器的 16 位高位

• MIPS 架构下有四个传参寄存器，即 4 到 7 号寄存器。多余的参数使用栈传递

• MIPS 架构的命令后缀 i 表示立即数，u 表示不启用溢出检测。比如说 addiu 命令表示将某一个寄存器加上一个立即数，溢出的话取模放入结果寄存器

流水线结构与延迟槽

在 MIPS 架构之中，任何指令的执行都会分为五个步骤，这五个步骤由不同的硬件完成。这些步骤分别是：

• 读取指令（IF）

• 读取寄存器（RD）

• 代数或逻辑运算（ALU）

• 访问内存（MEM）

• 回写（WB）

一个指令的五个执行步骤构成一条流水线，而不同指令的流水线是可以并发执行的，只要保证它们不会同时调用某一个硬件资源（比如说两条指令不可以同时在 IF 过程中）。

而这种并行的流水线架构的优越之处就是可以最大程度利用硬件资源。比如说考虑这样的 MIPS 汇编代码：

MIPS32 Assembly

jal  printf
move $4, $6
op

这里 jal 类似于 X86 的 call 命令，用于调用过程。但是，与这条指令间隔一条的 op 指令才是 printf 返回后调用的指令（返回地址）。

原因是 jal 指令流水线执行到 ALU 阶段的时候才会发生实质跳转，从 jal 的 IF 阶段结束到实质跳转这段时间 IF 硬件是空闲的，这段时间就被称为延迟槽（Delay slot）。但是我们可以让 IF 硬件立刻执行 move $4, $6 的 IF 阶段，这样在实质跳转发生前的这段延迟槽就被利用了。

能这样做的原因是 move 指令在 RD 阶段结束后就执行完毕了，后续的阶段可以忽略或者说当成不存在。如果说 jal 命令之后跟随了一些需要实质 ALU 的命令，则可能会因为和 jal 或者所调用的过程发生硬件冲突而导致异常。所以有的时候我们可以填入 nop 回避掉可能的问题。

多线程操作

在多线程编程之中，我们往往会涉及到多个线程对共享资源的读写操作。在 MIPS 架构中，针对这个场景，有 ll 和 sc 两个命令。

ll 全称为链接加载（Load linked），在使用这个命令从内存之中加载数据之后，处理器会记住这一次操作，这一次操作访问的地址也会被暂时保存。

sc 全称为条件存储（Store conditional），使用这个命令将寄存器 v 之中的数据存储到内存的时候，处理器会首先检查上一次 ll 命令操作的内存区域有没有被改动。如果没有被改动过，则存储成功，v 之中的值也会被写为 1 表示操作成功。反之，写入失败，内存不会被修改，v 之中的值也会被写为 0 表示操作失败。

协处理器与异常处理

协处理器是用于协助处理器处理类似内存管理、内存映射、异常等工作的硬件，其在可以被认为是一系列拓展寄存器。这里我们主要关注 MIPS 架构下协处理器之中的 Cause 和 Status 寄存器。

MIPS 系统的一个优点就是支持精确异常处理，也就是说保证发生异常的命令之前的所有命令都可以被执行完毕，之后的命令不进行处理。而为了实现这一点，就需要精确记录异常位置，并且处理好延迟槽机制带来的问题。

借助协处理器，MIPS 系统处理异常的步骤大致为：

• 保存异常现场信息。协处理器利用异常程序计数器（Exception program counter / EPC）记录异常命令的位置，Cause 寄存器会记录异常原因，且其 BD 位会记录延迟槽信息，Status 寄存器的异常标志位（EXL）被置 1。另外，一些相关寄存器的值也会被保存，另外 26 和 27 号寄存器会被留给异常处理。

• 根据具体类型判定处理异常的方式。这里会使用 Cause 寄存器获取异常类型。

• 开辟异常处理内存空间。系统会开辟出空间并且保留一部分通用寄存器用于异常处理。

• 处理完毕后返回。此时协处理器清空相关寄存器，跳转到原有命令继续执行。

这里要注意一点，一般异常处理会在内核态下运行，而正常的程序会在用户态下运行。为了防止异常处理机制被不正当利用于在内核态下执行攻击代码，系统要求状态转换和程序跳转回原有命令必须同时。

MIPS 内存管理

MIPS 使用虚存机制，其虚址一般按照下述方式分配：

• 高于 0xC0000000 的虚址为 kseg2 空间，其仅可以由核心态使用，使用的时候需要经过 MMU 转换，也就是说这一部分是 Mapped memory。

• 介于 0xA0000000 和 0xC0000000 之间的虚址是 kseg1 空间，其不可以在用户态下使用，使用的时候不需要经过 MMU 转换（其虚址最高三位清零就是物理地址）。另外，这一部分不会被缓存，也就是说这一部分是 Unmapped uncached memory。

• 介于 0x80000000 和 0xA0000000 之间的虚址是 kseg0 空间，其不可以在用户态下使用，使用的时候不需要经过 MMU 转换（其虚址最高一位清零就是物理地址）。另外，这一部分可以被缓存，也就是说这一部分是 Unmapped cached memory。

• 低于 0x80000000 的虚址为 kuseg 空间，是用户态空间，使用的时候需要经过 MMU 转换，也就是说这一部分是 Mapped memory。

这样划分的意图就是区分内核态和用户态对内存的访问。另外，上述划分之中有 unmapped 的内存空间，这一部分设置的缘由是系统刚启动的时候 TLB 并未初始化，不可以进行正常的地址转换，故使用 unmapped 的空间进行操作。

另外，为了区分某虚拟地址属于哪一个进程，MIPS 会给虚拟地址附上 ASID 进程标识符。

---

MIPS 架构支持一种特殊的快表，即 JTLB。其内部记录的是虚页码除以 2 之后的结果和两个物理页码之间的关系，两个映射项都标注了是否 valid 以及是否允许写入（一般称为是否 dirty，如果一个页面不是 dirty 的，则会禁止写入）。

这个时候的转换需要将虚页码先去掉末位进行查表，最后如果命中，则需要根据虚页码末位选取最终的映射项。