程序的机器级表示

内容大纲

历史观点

• 1978 年 Intel 发布了第一款微处理器-8086，在接下来的四十多年里，Intel 不断地推出新的处理器，从最早的 16 位扩展到 32 位，近些年又扩展到 64 位

程序编码

机器级编码

机器级编程抽象

1. 指令集架构（ISA）：定义机器级程序的格式和行为，定义了处理器状态、指令的格式以及每条指令对状态的影响
2. 使用的内存地址为虚拟地址，提供的内存模型看上去是一个非常大的字节数组

与机器代码的二进制格式相比，汇编代码的主要特点是它用可读性更好的文本格式表示

x86-64的机器代码和原始的C代码差别非常大

• 程序计数器 （PC， 在x86-64中用%rip表示）给出将要执行的下一条指令在内存中的地址
• 整数寄存器文件包含16个命名的位置，分别存储64位的值。可以存储地址或整数数据。
• 条件码寄存器保存着最近执行的算法或逻辑指令的状态信息。他们用来实现控制数据流中的条件变化，比如用来实现if和while语句。
• 一组向量寄存器可以存放一个或多个整数或浮点数值。

代码示例

定义一个C语言代码文件mstore.c

long mult2(long, long);

void multstore(long x, long y,  long *dest) {
  long t = mult2(x, y);
  *dest = t;
}

在命令行上使用"-S"选项，产生汇编代码mstore.s

(base) [cyl@cyl temp]$ gcc -Og -S  mstore.c

• 编译选项-Og 是用来告诉编译器生成符合原始 C 代码整体结构的机器代码。在实际项目中，为了获得更高的性能，会使用-O1 或者-O2，甚至更高的编译优化选项。但使用高级别的优化产生的代码会严重变形，导致产生的机器代码与最初的源代码之间的关系难以理解，这里为了理解方便，因此选择-Og 这个优化选项。

• -o 后面跟的参数 prog 表示生成可执行文件的文件名

汇编文件内容

	.file	"mstore.c"
	.text
	.globl	multstore
	.type	multstore, @function
multstore:
.LFB0:
	.cfi_startproc
	pushq	%rbx # 将寄存器 rbx 的值压入程序栈进行保存
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	%rdx, %rbx # 将寄存器 rbx 的内容复制到寄存器 rdx
	call	mult2
	movq	%rax, (%rbx) # 将寄存器 rbx 的内容复制到寄存器 rax
	popq	%rbx # 在函数返回之前, 使用了 pop 指令，恢复寄存器 rbx 的内容
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE0:
	.size	multstore, .-multstore
	.ident	"GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-44)"
	.section	.note.GNU-stack,"",@progbits

数据格式

早期的机器是 16 位，后才扩展到 32 位。

• Intel 用字 (word) 来表示 16 位的数据类型，因此，32 位数据类型为双字，64 位称为四字。下表给出了 C 语言的基本类型对应的汇编后缀表示，movq 的"q"表示四字

GCC 数据传送指令四个变种，分别为：movb（传送字节）、movw（传送字）、movl（传送双字节） 以及 movq（传送四字）

访问信息

1. 寄存器发展史 最早 8086 的处理器中，包含 8 个 16 位的通用寄存器

每个寄存器都有特殊的功能，它们的名字就反映了不同的用途，当处理器从16位扩展到 32 位时，寄存器的位数也随之扩展到了 32 位

直到今天，原来 8 个 16 位寄存器已经扩展成了 64 位。此外还增加了 8个新的寄存器

在一般的程序中，不同的寄存器扮演着不同的角色，相应的编程规范规定了如何使用这些寄存器。例如寄存器 rax 目来保存函数的返回值，寄存器 rsp 来保存程序栈的结束位置，除此之外，还有 6 个寄存器可以用来传递函数参数

操作数指示符

大多数指令包含两部分：操作码和操作数。

操作数分为三种类型

1. 立即数，用来表示常数值
   • 在ATT格式的汇编代码中，立即数的书写方式是‘$'后买安加一个用标准C语言法表示的整数，比如$0x1F
2. 寄存器
   • 即使在 64 位的处理器上，不仅 64 位的寄存器可以为操作数，32 位、16 位甚至 8 位的寄存器都可以作为操作数
3. 内存引用
   • 我们通常将内存抽象成一个字节数组，当需要从内存中存取数据时，需要获得目的数据的起始地址 addr，以及数据长度 b。为了简便，通常会省略下标 b。

有效地址是通过立即数与基址寄存器的值相加，再加上变址寄存器与比例因子的乘积

Imm($r_b$ ,$r_i$ ,s) → Imm + R[$r_b$] + R[$r_i$] · s

比例因子 s 的取值必须是 1、2、4 或者 8。实际上比例因子的取值是与源代码中定义的数组类型的是相关的，编译器会根据数组的类型来确定比例因子的数值，例如定义 char 类型的数组，比例因子就是 1，int 类型，比例因子就是 4，至于 double类型比例因子就是 8

其他的形式的内存引用都是这种普通形式的变种，省略了其中的某些部分，图中列出了内存引用的其他形式，需要特别注意的两种写法是：不带 $ 符号的立即数和带了括号的寄存器

数据传送指令

• 对于 mov 类指令，含有两个操作数，个称为源操作数，另外一个称为目的操作数。

• 对于源操作数，可以是一个立即数、一个寄存器，或者是内存引用。由于目的操作数是用来存放源操作数的内容，所以目的操作数要么是一个寄存器，要么是一个内存引用，注意目的操作数不能是一个立即数

• 除此之外，x86-64 处理器有一条限制，就是 mov 指令的源操作数和目的操作数不能都是内存的地址，那么当需要将一个数从内存的一个位置复制到另一个位置时，需要两条 mov 指令来完成：第一条指令将内存源位置的数值加载到寄存器；第二条指令再将该寄存器的值写入内存的目的位置

mov 指令还有几种特殊情况，当 movq 指令的源操作数是立即数时，该立即数只能是 32 位的补码表示，对该数符号位扩展后，将得到的 64 位数传送到目的位置。

这个限制会带来一个问题，当立即数是 64 位时应该如何处理? 这里引入一个新的指令 movabsq，该指令的源操作数可以是任意的 64 位立即数，需要注意的是目的操作数只能是寄存器。

接下来，我们通过一个例子来看一下使用 mov 指令进行数据传送时，对目的寄存器的修改结果是怎样的。首先使用 movabsq 指令将一个 64 位的立即数复制到寄存器rax。

movabsq, $0x0011223344556677, %rax

此时，寄存器 rax 内保存的数值如图所示

接下来，使用 movb 指令将立即数-1 复制到寄存器 al，寄存器 al 的长度为 8，与movb 指令所操作的数据大小一致

movb, $ − 1 %al

此时寄存器 rax 的低 8 位发生了改变

第三条指令 movw 是将立即数-1 复制到寄存器 ax。

movw $ − 1 %ax

此时寄存器 rax 的低 16 位发生了改变。

当指令 movl 将立即数-1 复制到寄存器 eax 时，此时寄存器 rax 不仅仅是低 32 位发生了变化，而且高 32 位也发了变化。

当 movl 的目的操作数是寄存器时，它会把该寄存器的高 4 字节设置为 0，这是x86-64 处理器的一个规定，即任何位寄存器生成 32 位值的指令都会把该寄存器的高位部分置为 0 。

零扩展数据传送指令有 5 条，其中字符 z 是 zero 的缩写。指令最后两个字符都是大小指示符，第一个字母表示源操作数的大小，第二个字母表示目的操作数的大小。

符号位扩展传送指令有 6 条，其中字符 s 是 sign 的缩写，同样指令最后的两个字符也是大小指示符。

对比零扩展和符号扩展，我们可以发现符号扩展比零扩展多一条 4 字节到 8 字节的扩展指令，为什么零扩展没有 movzlq 的指令呢？是因为这种情况的数据传送可以使用 movl 指令来实现

当源操作数的数位小于目的操作数时，需要对目的操作数剩余的字节进行零扩展或者符号位扩展以 x86-64 处理器为例，寄存器 rax 的大小是 64 个比特位 (8 个字节)

实际上，在一些程序的执行过程中，需要在 CPU 和内存之间进行频繁的数存取。例如 CPU 执行一个简单的加法操作 c=a +b。那么首先通过 CPU 执行数据传送指令将 a 和 b 的值从内存读到寄存器内，寄存器就是 CPU 内的一种数据存储部件，只不过是容量比较小

最后，符号位扩展还有一条没有操作数的特殊指令 cltq，该指令的源操作数总是寄存器 eax，目的操作数总是寄存器是 rax

• 如果变量 a 是long 类型，需要占用 8 个字节，因此，寄存器 rax 全部的数据位都用来保存变量 a；

• 如果变量 a 是 int 类型，那么只需要用 4 个字节来存储该变量，那么只需要用到寄存器的低 32 位就够了

• 如果变量 a 是 short 类型，则只需要用到寄存器的低 16 位；

• 对于寄存器 rax，如果使用全部的 64 位，用符号%rax 来表示；如果是只用到低32 位，可以用符号%eax 来表示；对于低 16 位和低 8 位的，分别用%ax 和%al来表示

• 虽然用了不同的表示符号，但实际上只是针对同一寄存器的不同数位进行操作，处理器完成加法运算之后，再通过一条数据传送指令将计算结果保存到内存

• 正是因为数据传送在计算机系统中是一个非常频繁的操作，所以了解一下数据传输指令对理解计算机系统会有很大的帮助

数据传送示例

1 int main(){
2 long a = 4;
3 long b = exchange(&a, 3);
4 printf("a = %1d, b = %1d\n", a, b);
5 return 0;
6 }
7 long exchange(long *xp, long y){
8 long x = *xp;
9 *xp = y;
10 return x;
11 }

变量 a 的值会替换成 3，变量 b 将保存变量 a 原来的值 4。重点看函数exchange 所对应的汇编指令：函数 exchange 由三条指令实现，包括两条数据传送指令和一条返回指令。根据寄存器的使用惯例，寄存器 rdi 和 rsi 分别用来保存函数传递的第一个参数和第二个参数，因此，寄存器 rdi 中保存了 xp 的值，寄存器 rsi 保存了变量 y 的值。这段汇编代码中并没有显式的将这部分表示出来，需要注意一下。

• 第一条 mov 指令从内存中读取数值到寄存器，内存地址保存在寄存器 rdi 中，目的操作数是寄存器 rax，这条指令对应于代码的 long x = *xp; 由于最后函数exchange 需要返回变量 x 的值，所以这里直接将变量 x 放到寄存器 rax 中。

• 第二条 mov 指令将变量 y 的值写到内存里，变量 y 存储在寄存器 rsi 中，内存地址保存在寄存器 rdi 中，也就是 xp 指向的内存位置。这条指令对应函数exchange 中的 *xp = y;

通过这个例子，我们可以看到 C 语言中所谓的指针其实就是地址。

压入和弹出栈数据

此外，还有两个数据传送指令需要借助程序栈，程序栈本质上是内存中的一个区域。栈的增长方向是从高地址向低地址，因此，栈顶的元素是所有栈中元素地址中最低的。根据惯例，栈是倒过来画的，栈顶在图的底部，栈底在顶部。 例如我们们需要保存寄存器 rax 内存储的数据 0x123，可以使用 pushq 指令把数据压入栈内。该指令执行的过程可以分解为两步：

1. 首先指向栈顶的寄存器的 rsp 进行一个减法操作，例如压栈之前，栈顶指针 rsp指向栈顶的位置，此处的内存地址 0x108；压栈的第一步就是寄存器 rsp 的值减 8，此时指向的内存地址是 0x100

1. 然后将需要保存的数据复制到新的栈顶地址，此时，内存地址 0x100 处将保存寄存器 rax 内存储的数据 0x123。实际上 pushq 的指令等效于图中 subq 和movq 这两条指令。它们之间的区别是在于 pushq 这一条指令只需要一个字节，而 subq 和 movq 这两条指令需要 8 个字节

说到底，push 指令的本质还是将数据写入到内存中，那么与之对应的 pop 指令就是从内存中读取数据，并且修改栈顶指针。例如图中这条 popq 指令就是将栈顶保存的数据复制到寄存器 rbx 中

pop 指令的操作也可以分解为两步：

1. 首先从栈顶的位置读出数据，复制到寄存器 rbx。此时，栈顶指针 rsp 指向的内存地址是 0x100。

1. 然后将栈顶指针加 8，pop 后栈顶指针 rsp 指向的内存地址是 0x108。

因此 pop 操作也可以等效 movq 和 addq 这两条指令。实际上 pop 指令是通过修改栈顶指针所指向的内存地址来实现数据删除的，此时，内存地址 0x100 内所保存的数据 0x123 仍然存在，直到下次 push 操作，此处保存的数值才会被覆盖.

算术和逻辑操作

首先我们看一下指令 leaq，它实现的功能是加载有效地址，q 表示地址的长度是四个字，由于 x86-64 位处理器上，地址长度都是 64 位，因此不存在 leab、leaw 这类有关大小的变种。

leaq S, D → Load Effective Address

加载有效地址

首先我们看一下指令 leaq，它实现的功能是加载有效地址，q 表示地址的长度是四个字，由于 x86-64 位处理器上，地址长度都是 64 位，因此不存在 leab、leaw 这类有关大小的变种。

leaq S, D → Load Effective Address

例如下面的这条指令，它表示的含义是把有效地址复制到寄存器 rax 中。

leaq 7(%rdx,%rdx,4),%rax

这个源操作数看上去与内存引用的格式类似，有效地址的计算方式与之前讲到的内存地址的计算方式一致，可以通过下列中的公式计算得到.

Imm($r_b$ ,$r_i$ ,s) → Imm + R[$r_b$] + R[$r_i$] · s

假设寄存器 rdx 内保存的数值为 x，那么有效地址的值为 7 + %rdx + %rdx * 4 = 7+ 5x。注意，对于 leaq 指令所执行的操作并不是去内存地址 (5x+7) 处读取数据，而是将有效地址 (5x+7) 这个值直接写入到目的寄存器 rax。

除了加载有效地址的功能，leaq 指令还可以用来表示加法和有限的乘法运算

1 long scale(long x, long y, long z){
2 long t = x + 4 * y + 12 * z;
3 return t;
4 }

经过编译后，这段代码是通过三条 leaq 指令来实现。

接下来我们看一下，如何通过 leaq 指令实现算术运算。

根据寄存器的使用惯例，参数 x，y，z 分别保存在寄存器 rdi、rsi 以及 rdx 中，还是根据内存引用的计算公式，第一条指令的源操作数就对应于 x+4*y，具体过程如图所示。

指令 leaq 将该数值保存到目的寄存 rax 中

接下来关于 z*12 的乘法运算会有一些复杂，需要分成两步：

1. 首先计算 3*z 的数值. 第二条的 leaq 指令执行完毕，此时寄存器 rdx 中保存的值是 3z。
2. 把 3z 作为一个整体乘以 4。

为什么不能使用下列这条指令，直接一步得到我们期望的结果？ leaq (%rax, %rdx, 12), %rax → %rax + 12 ∗ %rdx = (x + 4 ∗ y) + 12 ∗ z

这里主要是由于比例因子取值只能是 1,2,4,8 这四个数中的一个，因此要把 12 进行 分解。

一元操作

一元操作指令只有一个操作数，因此该操作数既是源操作数也是目的操作数，操作数可以是寄存器，也可以是内存地址。

二元操作

二元操作指令包含两个操作数，第一个操作数是源操作数，这个操作数可以是立即数、寄存器或者内存地址；第二个操作数既是源操作数也是目的操作数，这个操作数可以是寄存器或者内存地址，但不能是立即数。

移位

左移指令有两个，分别是 SAL 和 SHL，二者的效果是一样的，都是在右边填零；右移指令不同，分为算术右移和逻辑右移，算术右移需要填符号位，逻辑右移需要填零，这与 C 语言中所讲述的移位操作是一致的。

对于移位量 k，可以是一个立即数，或者是放在寄存器 cl 中的数，对于移位指令只允许以特定的寄存器 cl 作为操作数，其他寄存器不行，这里需要特别注意一下。

由于寄存器 cl 的长度为 8，原则上移位量的编码范围可达 $2^8$ - 1 (255)，实际上，对于 w 位的操作数进行移位操作，移位量是由寄存器 cl 的低 m 位来决定，也就是说，对于指令 salb，当目的操作数是 8 位，移位量由寄存器 cl 的低 3 位来决定。

对于指令 salw，移位量则是由寄存器 cl 的低 4 位来决定

以此类推，双字对应的是低 5 位，四字对应的是低 6 位。

控制

条件码

• 进位标志，当 CPU 最近执行的一条指令最高位产生了进位时，进位标志 (CF）会被置为 1，它可以用来检查无符号数操作的溢出。
• 零标志，当最近操作的结果等于零时，零标志 (ZF) 会被置 1。
• 符号标志，当最近的操作结果小于零时，符号标志 (SF) 会被置 1
• 溢出标志，针对有符号数，最近的操作导致正溢出或者负溢出时溢出标志 (OF)会被置 1。

条件码寄存器的值是由 ALU 在执行算术和运算指令时写入的，下图中的这些算术和逻辑运算指令都会改变条件码寄存器的内容。

访问条件码

对于不同的指令也定义了相应的规则来设置条件码寄存器。例如逻辑操作指令 xor，进位标志 (CF) 和溢出标志 (OF) 会置 0；对于加一指令和减一指令会设置溢出标志(OF) 和零标志 (ZF)，但不会改变进位标志 (CF)。

除此之外，还有两类指令可以设置条件码寄存器：cmp 指令和 test 指令。

• cmp 指令是根据两个操作数的差来设置条件码寄存器。cmp 指令和减法指令(sub）类似，也是根据两个操作是的差来设置条件码，二者不同的是 cmp 指令只是设置条件码寄存器，并不会更新目的寄存器的值。
• test 指令和 and 指令类似，同样 test 指令只是设置条件码寄存器，而不改变目的寄存器的值

接下来的这条指令 sete 看起来就有点费解了，这是因为通常情况下，并不会直接去读条件码寄存器。其中一种方式是根据条件码的某种组合，通过 set 类指令，将一个字节设置为 0 或者 1。在这个例子中，指令 sete 根据需标志 (ZF) 的值对寄存器al 进行赋值，后缀 e 是equal 的缩写。如果零标志等于 1，指令 sete 将寄存器 al 置为 1；如果零标志等于 0，指令 sete 将寄存器 al 置为 0

然后 mov 指令对寄存器 al 进行零扩展，最后返回判断结果

于无符号数的比较情况，需要注意一下，指令 cmp 会设置进位标志，因而针对无符号数的比较，采用的是进位标志和零标志的组合，具体的条件码组合如图所示。

跳转指令

1 long absdiff_se(long x, long y){
2 long result;
3 if(x < y){result = y - x;} else{result = x - y;}
4 return result;
5 }

条件语句 x 小于 y 由指令 cmp 来实现，指令 cmp 会根据 (x-y) 的结果来设置符号标志 (SF) 和溢出标志 (OF)。图中的跳转指令 jl，根据符号标志 (SF）和溢出标志(OF) 的异或结果来判断究竟是顺序执行，还是跳转到 L4 处执行。当 x 大于 y 时，指令顺序执行，然后返回执行结果，L4 处的指令不会被执行；当 x 小于 y 时，程序跳转到 L4 处执行，然后返回执行结果，跳转指令会根据条件寄存器的某种组合来决定是否进行跳转

用条件传送来实现条件分支

对于代码中的 if-else 语句，当满足条件时，程序沿着一条执行路径执行，当不满足条件时，就走另外一条路径。这种机制比较简单和通用，但是在现代处理器上，它的执行效率可能会比较低。

针对这种情况，有一种替代的策略，就是使用数据的条件转移来代替控制的条件转移。还是针对两个数差的绝对值问题，给出了另外一种实现方式，具体如下所示。

1 long comvdiff_se(long x, long y){
2 long rval = y - x; long eval = x - y;
3 long ntest = x >= y;
4 if(ntest){rval = eval;} return rval;
5 }

我们既要计算 y-x 的值，也要计算 x-y 的值，分别用两个变量来记录结果，然后再判断 x 与 y 的大小，根据测试情况来判断是否更新返回值。这两种写法看上去差别不大，但第二种效率更高。第二种代码的汇编指令如下所示。

前面这几条指令都是普通的数据传送和减法操作。cmovge 是根据条件码的某种组合来进行有条件的传送数据，当满足规定的条件时，将寄存器 rdx 内的数据复制到寄存器 rax 内。在这个例子中，只有当 x 大于等于 y 时，才会执行这一条指令。

更多条件传送指令如下表所示

为什么基于条件传送的代码会比基于跳转指令的代码效率高呢？这里涉及到现代处理器通过流水线来获得高性能。当遇到条件跳转时，处理器会根据分支预测器来猜测每条跳转指令是否执行，当发生错误预测时，会浪费大量的时间，导致程序性能严重下降。

循环

C 语言中提供了三种循环结构，即 do-while、while 以及 for 语句，汇编语言中没有定义专内的指令来实现循环结构，循环语句是通过条件测试导跳转的结合来实现的。

接下来，我们分别用这三种循环结构来实现 N 的阶乘。

1. do-while

我们可以发现指令 cmp 与跳转指令的组合实现了循环操作。

当 n 大于 1 时，跳转到 L2 处执行循环，直到 n 的值减小到 1，循环结束

1. while 对比 do-while 循环和 while 循环的实现方式，我们可以发现这两种循环的差别在于，N 大于 1 这个循环测试的位置不同

do-while 循环是先执行循环体的内容，然后再进行循环测试，while 循环则是先进行循环测试，根据测试结果是否执行循环体内容

1. for

对比 for 循环和 while 循环产生的汇编代码，可以发现除了这一句跳转指令不同，其他部分都是一致的。

• 这两个汇编代码是采用-Og 选项产生的。
• 综上所述，三种形式的循环语句都是通过条件测试和跳转指令来实现。

  switch语句

1 void switch_eg(long x, long n, long *dest){
2 long val = x;
3 switch(n){
4 case 0: val *= 13; break;
5 case 2: val += 10; break;
6 case 3: val += 11; break;
7 case 4:
8 case 6: val += 11; break;
9 default: val = 0;
10 }
11 *dest = val;
12 }

在针对一个测试有多种可能的结果时，switch 语言特别有用，switch 语句通过跳转表这种数据结构，使得实现更加的高效。接下来我们通看看所对应的汇编指令。

指令 cmp 判断参数 n 与立即数 6 的大小，如果 n 大于 6，程序跳转到 default 对应的 L8 程序段。case0 case6 的情况，可以通过跳转表来访问不同分支。代码将跳转表声明为一个长度为 7 的数组，每个元素都是一个指向代码位置的指针，具体对应关系如图所示。

数组的长度为 7，是因为需要覆盖 Case0 Case6 的情况，对重复的情况 case4 和case6，使用相同的标号。

对于缺失的 case1 和 case5 的情况，使用默认情况的标号。

在这个例子中，程序使用跳转表来处理多重分支，甚至当 switch 有上百种情况时，虽然跳转表的长度会增加，但是程序的执行只需要一次跳转也能处理复杂分支的情况，与使用一组很长的 if-else 相比，使用跳转表的优点是执行 switch 语句的时间与case 的数量是无关的。因此在处理多重分支的时，与一组很长的 if-else 相比，switch 的执行效率要高

过程

在大型软件的构建过程中，需要对复杂功能进行切分，过程提供了一种封装代码的方式，它可以隐藏某个行为的具体实现，同时提供清晰简洁的接口定义，在不同的编程语言中，过程的具体实现又是多种多样的。例如 C 语言中的函数，Java 语言中的方法等

运行时栈

程序的运行时内存分布中，栈为函数调用提供了后进先出的内存管理机制。

在函数 P 调用函数 Q 的例子中，当函数 Q 正在执行时，函数 P 以及相关调用链上的函数都会被暂时挂起。

我们先来介绍一下栈帧的概念，当函数执行所需要的存储空间超出寄存器能够存放的大小时，就会借助栈上的存储空间，我们把这部分存储空间称为函数的栈帧。对于函数 P 调用函数 Q 的例子，包括较早的帧、调用函数 P 的帧，还有正在执行函数 Q 的帧，具体如图所示

转移控制

函数 P 调用函数 Q 时，会把返回地址压入栈中，该地址指明了当函数 Q 执行结束返回时要从函数 P 的哪个位置继续执行。这个返回地址的压栈操作并不是由指令push 来执行的，而是由函数调用 call 来实现的。

以 main 函数调用 multstore 函数为例来解释一下指令 call 和指令 ret 的执行情况

main函数

1 #include<stdio.h>
2 void multstore(long, long, long *);
3 int main(){
4 long d;
5 mulstore(2, 3, &d);
6 printf("2 ∗ 3 −−> %d\n", d);
7 return 0;
8 }
9 long mult2(long a, long b){
10 long s = a * b;
11 return s;
12 }

multstore

1 long mult2(long, long);
2 void multstore(long x, long y, long *dest){
3 long t = mult2(x, y);
4 *dest = t;
5 }

由于涉及地址的操作，我们需要查看这两个函数的反汇编代码。

这一条 call 指令对应 multstore 函数的调用。指令 call 不仅要将函数 multstore 的第一条指令的地址写入到程序指令寄存器 rip中，以此实现函数调用。

同时还要将返回地址压入栈中。

这个返回地址就是函数 multstore 调用执行完毕后，下一条指令的地址。

当函数 multstore 执行完毕，指令 ret 从栈中将返回地址弹出，写入到程序指令寄存器 rip 中。

函数返回，继续执行 main 函数中相关的操作。以上整个过程就是函数调用与返回所涉及的操作

数据传送

如果一个函数的参数数量大于 6，超出的部分就要通过栈来传递。假设函数 P 有 n 个整型参数，当 n 的值大于 6 时，参数 7参数 n 需要用到栈来传递。

参数 1 参数 6 的传递可以使用对应的寄存器。

1 void proc(long a1, long *a1p,
2   int a2, long *a2p,
3   short a3, long *a3p,
4   char a4, long *a4p){
5   a1p += a1;
6   a2p += a2;
7   a3p += a3;
8   a4p += a4;
9 }

代码中函数有 8 个参数，包括字节数不同的整数以及不同类型的指针，参数 1 到参数 6 是通过寄存器来传递，参数 7 和参数 8 是通过栈来传递。

这里有两点需要注意一下：

1. 通过栈来传递参数时，所有数据的大小都是向 8 的倍数对齐，虽然变量 a4 只占一个字节，但是仍然为其分配了 8 个字节的存储空间。由于返回地址占用了栈顶的位置，所以这两个参数距离栈顶指针的距离分别为 8 和 16。

2. 使用寄存器进行参数传递时，寄存器的使用是有特殊顺序规定的，此外，寄存器名字的使用取决于传递参数的大小。如果第一个参数大小是 4 字节，需要用寄存器 edi 来保存。

栈上的局部存储

当代码中对一个局部变量使用地址运算符时，我们需要在栈上为这个局部变量开辟相应的存储空间，接下来我们看一个与地址运算符相关的例子。

1 long caller(){
2   long arg1 = 534;
3   long arg2 = 1057;
4   long sum = swap(&arg1, &arg2);
5   long diff = arg1 - arg2;
6   return sum * diff;
7 }

函数 caller 定义了两个局部变量 arg1 和 arg2，函数 swap 的功能是交换这两个变量的值，最后返回二者之和

1 long swap(long *xp, long * yp){
2   long x = *xp;
3   long y = *yp;
4   *xp = y;
5   *yp = x;
6   return x + y;
7 }

我们通过分析函数 caller 的汇编代码来看一下地址运算符的处理方式。

第一条减法指令将栈顶指针减去 16，它表示的含义是在栈上分配 16 个字节的空间

根据接着的两条 mov 指令，可以推断出变量 arg1 和 arg2 存储在函数 caller 的栈帧上，接下来，分别计算变量 arg1 和 arg2 存储的地址，参数准备完毕，执行 call 指令调用 swap 函数。最后函数 caller 返回之前，通过栈顶指针加上 16 的操作来释放栈帧。

寄存器中的局部存储空间

对于 16 个通用寄存器，除了寄存器 rsp 之外，其他 15 个寄存器分别被定义为调用者保存和被调用者保存，具体如图所示。

从上面的例子我们可以看到，当函数运行需要局部存储空间时，栈提供了内存分配与回收的机制。在程序执行的过程中，寄存器是被所有函数共享的一种资源，为了避免寄存器的使用过程中出现数据覆盖的问题，处理器规定了寄存器的使用的惯例，所有的函数调用都必须遵守这个惯例

接下来，我们看一个栈保存寄存器数值的例子

由于函数 Q 需要使用寄存器 rdi 来传递参数，因此，函数 P 需要保存寄存器rdi 中的参数 x；保存参数 x 使用了寄存器 rbp，根据寄存器使用规则，寄存器rbp 被定义为被调用者保存寄存器，所以便有了开头的这条指令 pushq %rbp，至于 pushq %rbx 也是类似的道理。

在函数 P 返回之前，使用 pop 指令恢复寄存器 rbp 和 rbx 的值。由于栈的规则是后进先出，所以弹出的顺序与压入的顺序相反。

递归过程

最后，我们再来看一个递归调用的例子。

这段代码是关于 N 的阶乘的递归实现，我们假设 n=3 时，看一些汇编代码的执行情况。由于使用寄存器 rbx 来保存 n 的值，根据寄存器使用惯例，首先保存寄存器rbx 的值。

由于 n=3，所以跳转指令 jle 不会跳转到 L35 处执行。

指令 leaq 是用来计算 n-1，然后再次调用该函数。

可以看出，递归调用一个函数本身与调用其他陋数是一样的，每次函数调用都有它自己私有的状态信息，栈分配与释放的规则与函数调用返回的顺序也是匹配的，不过当 N 的值非常大时，并不建议使用递归调用，至于原因应该是一目了然了。

数据分配和访问

C语言的一个不同寻常的特点是可以产生指向数组中元素的指针，并对这些指针进行运算。在机器代码中，这些指针会被翻译成地址计算。

基本原则

首先看几个数组的例子，数组 A 是由 8 个 char 类型的元素组成，每个元素的大小是一个字节。假设数组 A 的起始地址是 Xa，那么数组元素 A[i] 的地址就是$X_{a+i}$。

我们再来看一个 int 类型的数组，数组 B 是由 4 个整数组成，每个元素占 4 个字节，因此数组 B 总的大小为 16 个字节。假设数组 B 的起始地址是$X_b$，那么数组元素B[i] 的地址就是$X_{b+4i}$。

指针运算

在 C 语言中，允许对指针进行运算，例如，我们声明了一个指向 char 类型的指针p，和一个指向 int 类型的指针 q。为了方便理解，我们还是把内存抽象成一个大的数组。假设指针 p 和指针 q 都指向 0x100（内存地址）处。

现在分别对指针 p 和指针 q 进行加一的操作，指针 p 加 1 指向 0x101 处，而指针 q加 1 后指向 0x104 处。

虽然都是对指针进行加一的运算，但是得到的结果却不同。这是因为对指针进行运算时，计算结果会根据该指针引用的数据类型进行相应的伸缩

通常我们习惯使用数组引用的方式来访问数组中的元素，例如可以使用图中的表达式来访问数组中的元素

除此之外，还有另外一种方式，具体如图所示，其中表达式 E+2 表示数组第二个元素的存储地址，大写字母 E 表示数组的起始地址 (第 0 个元素)，此处加 2 的操作与指针加 2 的运算类似，也是与数据类型相关。

指针运算符 * 可以理解成从该地址处取数据，指针是 C 语言中最难理解的部分，我们理解了内存地址的概念之后，可以发现指针其实就是地址的抽象表述。

嵌套的数组

嵌套数组也被称为二维数组，图中我们声明了一个数组 A，数组 A 可以被看成 5 行3 列的二维数组，这种理解方式与矩阵的排列类似。在计算机系统中，我们通常把内存抽象为一个巨大的数组，对于二维数组在内存中是按照"行优先"的顺序进行存储的，基于这个规则，我们可以画出数组 A 在内存中的存储情况。

关于数组的理解，还有一种方式，就是可以把数组 A 看成一个有 5 个元素的数组，其中每个元素都是一个长度为 3 的数组，这便是嵌套数组的理解方式。

无论用何种方式来理解，数组元素在内存中的存储位置都是一样的。下面我们来看一下数组元素的地址是如何计算的，对于数组 D 任意一个元素可以通过图中的计算公式来计算地址。 对于一个声明如下的数组： T D[R][C] 它的数组元素D[i][j]的内存地址为

$ \&D[i][j] = $x_0$ + L(C * i + j )$ 其中，$X_D$表示数组的起始地址；L 表示数据类型 T 的大小，如果 T 是 int 类型，L就等于 4，T 是 char 类型，L 就等于 1；在具体的示例中，C、i、j 都是常数。

假设数组起始地址 Xa 在寄存器 rdi 中，索引值 i 和 j 分别在寄存器 rsi 和 rdx 中，我们可以用图中的汇编代码将 A[i][i] 的值复制到寄存器 eax 中，具体如图所示。

定长数组

接下来，我们看一下编译器对定长多维数组的优化。首先使用以下方式将数据类型 fix_matrix 声明为 16*16 的整型数组。

• #define N 16
• typedef int fix_matrix[N][N]; 通过 define 声明将 N 与常数 16 关联到一起，之后的代码中就可以使用 N 来代替常数 16，当需要修改数组的长度时，只需要简单的修改 define 声明即可。

  1 #define N 16
  2 typedef int fix_matrix[N][N]
  3 int matrix(fix_matrix A, fix_matrix B, long i, long k){
  4 long j;
  5 int result = 0;
  6 for(j = 0; j < N; j++){
  7 result += A[i][j] * B[j][k];
  8 }
  9 return result;
  10 
  

  

为了方便表述，这里我们引入三个指针来记录这三个地址，接下来，我们介绍一下循环的实现。

首先读取指针 Aptr 指向元素的数据，然后将指针 Aptr 指向的元素与指针 Bptr 指向的元素相乘，最后将乘积结果进行累加，结果保存到寄存器 eax 中。 计算完成之后，分别移动指针 Aptr 和 Bptr 指向下一个元素，由于 int 类型占 4 个字节，对寄存器 rdi 加 4 的这个操作，对应于移动指针 Aptr 指向数组 A 的下一个元素。由于数组 B 一行元素的数量为 16 个，每个元素占 4 个字节，因此相邻列元素的地址相差为 64 个字节，对寄存器 rcx 进行加 64 的操作对应移动指针 Bptr 指向数组 B 的下一个元素。

判断循环结束的条件是：指针 Bptr 指针与指针 Bend 是否指向同一个内存地址，如果二者不相等，继续跳转到 L7 处执行，如果二者相等，循环结束。

变长数组

在 C89 的标准中，程序员在使用变长数组时需要使用 malloc 这类函数，为数组动态分配存储空间。在 ISO C99 的标准中，引入了变长数组的概念，因此，我们可以通过下列代码的方式来声明一个变长数组。

1 int A[expr1][expr2];
2 long var_ele(long n, int A[n][n], long i, long k){
3   return A[i][j];
4 }

它可以作为一个局部变量，也可以作为函数的参数，当变长数组作为函数参数时，参数 n 必须在数组 A 之前

变长数组元素的地址计算与定长数组类似，不同点在于新增了参数 n，需要使用乘法指令来计算 n 乘以 i。

还是矩阵 A 和矩阵 B 内积的例子，如果采用变长数组来存储矩阵 A 和矩阵 B，与定长数组相比 C 代码的实现几乎没有差别。

异质的数据结构

C语言提供了两种将不同类型的对象组合到一起创建数据类型的机制：

• 结构（structure），用关键字struct来声明，将多个对象集合到一个单位中
• 联合（union），用关键字union来声明，允许用几种不同的类型来引用一个对象

  结构

  结构体的声明

  1 struct rec{
  2 int i;
  3 int j;
  4 int a[2];
  5 int *p;
  6 }
  

  这个结构体包含四个字段：两个 int 类型的变量，个 int 类型的数组和一个 int 类型的指针。

我们可以画出各个字段相对于结构体起始地址处的字节偏移。

从这个图上可以看出数组 a 的元素是嵌入到结构体中的。接下来，我们看一下如何访问结构体中的字段。

例如，我们声明一个结构体类型指针变量 r，它指向结构体的起始地址。

假设 r 存放在寄存器 rdi 中，可以使用下图的汇编指令将字段 i 的值复制到字段 j中。

联合

与结构体不同，联合体中的所有字段共享同一存储区域，因此联合体的大小取决于它最大字段的大小

变量 v 和数组 i 的大小都是 8 个字节，因此，这个联合体的占 8 个字节的存储空间。

联合体的一种应用情况是：我们事先知道两个不同字段的使用是互斥的，那么我们可以将这两个字段声明为一个联合体。原理就是不会让不可能有数据的字段白白浪费内存。 例如，我们定义一个二叉树的数据结构，这个二叉树分为内部节点和叶子节点，其中每个内部节点不含数据，都有指向两个孩子节点的指针，每个叶子节点都有两个double 类型的数据值。

我们可以用结构体来定义该二叉树的节点。

1 struct node_s{
2   struct node_s *left;
3   struct node_s *right;
4   double data[2];
5 };

那么每个节点需要 32 个字节，由于该二叉树的特殊性，我们事先知道该二叉树的任意一个节点不是内部节点就是叶子节点，因此，我们可以用联合体来定义节点.

1 union node_u{
2 struct{
3 union node_s *left;
4 union node_s *right;
5 }internal;
6 double data[2];
7 };

这样，每个节点只需要 16 个字节的存储空间，相对于结构体的定义方式，可以节省一半的空间。不过，这种编码方式存在一个问题，就是没有办法来确定一个节点到底是叶子节点还是内部节点，通常的解决方法是引入一个枚举类型，然后创建一个结构体，它包含一个标签和一个联合体

1 typedef enum{N_LEAF, N_INTERNAL} nodetype_t;
2 struct node_t{
3   nodetype_t type;
4   union{
5     struct{
6       union node_s *left;
7       union node_s *right;
8    }internal;
9    double data[2];
10   }info;
11 };

其中 type 占 4 个字节，联合体占 16 个字节，type 和联合体之间需要加入 4 个间隙，因此，整个结构体的大小为 24 个字节。在这种例子中，虽然使用联合体可以节省存储空间，但是相对于给代码编写造成的麻烦，这样的节省意义不大。因此，对于有较多字段的情况，使用联合体带来的空间节省才会更吸引人。 除此之外，联合体还可以用来访问不同数据类型的位模式，当我们使用简单的强制类型转换，将 double 类型的数据转换成 unsigned long 类型时，除了 d 等于 0 的情况，二者的二进制位表示差别很大，这时我们可以将这两种类型的变量声明为一个联合体，这样就是可以以一种类型来存储，以另外一种类型来访问，变量 u 和 d 就具有相同的位表示。

数据对齐

对于图中的结构体，它包含两个 int 类型的变量和一个 char 类型的变量。

struct S1 {
	int i;
	char c;
	int j;
}

根据前面的知识，我们会直观的认为该结构体占用 9 个字节的存储空间，但是当使用 sizeof 函数对该结构体的大小进行求值时，得到的结果却是 12 个字节。原因是为了提高内存系统的性能，系统对于数据存储的合法地址做出了一些限制

例如变量 j 是 int 类型，占 4 个字节，它的起始地址必须是 4 的倍数，因此，编译器会在变量 c 和变量 j 之间插入一个 3 字节的间隙，这样变量 j 相对于起始地址的偏移量就为 8，整个结构体的大小就变成了 12 个字节。

对于不同的数据类型，地址对齐的原则是任何 K 字节的基本对象的地址必须是 K的倍数。也就是说对于 short 类型，起始地址必须是 2 的倍数；对于占 8 个字节的数据类型，起始地址必须是 8 的倍数。

基于上表的规则，编译器可能需要在字段的地址空间分配时插入间隙，以此保证每个结构体的元素都满足对齐的要求。 除此之外，结构体的末尾可能需要填充间隙，还是刚才的这个结构体，可以通过调整字段 j 和字段 c 的排列顺序，使得所有的字段都满足了数据对齐的要求

但是当我们声明一个结构体数组时，分配 9 个字节的存储空间，是无法满足所有数组元素的对齐要求，因此，编译器会在结构体的末端增加 3 个字节的填充，这样一来，所有的对齐限制都满足了

根据上述对齐原则，我们看一个复杂的示例。

1. 变量 a 是一个指针变量，占 8 个字节。
2. 变量 b 是 short 类型，占两个字节，它起始地址的字节偏移量是 8，满足对齐规则的 2 的倍数。
3. 由于变量 c 是 double 类型，占 8 个字节，因此，该变量起始地址的偏移量需要是 8 的倍数，所以需要在变量 b 之后插入 6 个字节的间隙。
4. 对于变量 d 只占一个字节，顺序排列即可。
5. 由于变量 e 占 4 个字节，它的偏移量需要是 4 的倍数，因此，需要在变量 d 之后插入 3 个字节的间隙。
6. 同样变量 f 是 char 类型，顺序排列即可。
7. 由于变量 g 占 8 个字节，因此需要在变量 f 之后插入 7 个字节的间隙。
8. 最后一个变量 h 占 4 个字节，此时结构体的大小为 52 个字节，为了保证每个元素都满足对齐要求，还需要在结构体的尾端填充 4 个字节的间隙

在机器级程序中间控制与数据结合起来

理解指针

指针是C语言的一个核心特色

1. 每个指针都对应一个类型，这个类型表明该指针指向的是哪一类对象
2. 每个指针都有一个值，这个值是某个指定类型的对象的地址
3. 指针用&运算符创建
4. * 操作符用于简介引用指针
5. 整数与数组紧密联系，一个数组的名字可以像一个指针变量一样引用
6. 将指针从一种类型强制转换为另一种类型，只需改变它的类型，而不改变它的值
7. 指针也可以指向函数

内存越界引用和缓冲区溢出

我们通过一个代码示例看一下什么是缓冲区溢出

1 void echo(){
2 char buf[8];
3 gets(buf);
4 puts(buf);
5 }

echo 函数声明了一个长度为 8 的字符数组。gets 函数是 C 语言标准库中定义的函数，它的功能是从标准输入读入一行字符串，在遇到回车或者某个错误的情况时停止，gets 函数将这个字符串复制到参数 buf 指明的位置，并在字符串结束的位置加上 null 字符。注意 gets 函数会有一个问题，就是它无法确定是否有足够大的空间来保存整个字符串，长一些字符串可能会导致栈上的其他信息被覆盖，通过汇编代码，我们可以发现实际上栈上分配了 24 个字节的存储空间。

实际上当输入字符串的长度不超过 23 时，不会发生严重的后果，超过以后，返回地址以及更多的状态信息会被破坏，那么返回指令会导致程序跳转到一 个完全意想不到的地方。

对抗缓冲区溢出攻击

历史上许多计算机病毒就是利用缓冲区溢出的方式对计算机系统进行攻击的，针对缓冲区溢出的攻击，现在编译器和操作系统实现了很多机制，来限制入侵者通过这种攻击方式来获得系统控制权。

例如栈随机化、栈破坏检测以及限制可执行代码区域等。

• 栈随机化

1 int main(){
2 long local;
3 printf(" local at %p\n", &local);
4 return 0;
5 }

在过去，程序的栈地址非常容易预测，如果一个攻击者可以确定一个 web 服务器所使用的栈空间，那就可以设计一个病毒程序来攻击多台机器，栈随机化的思想是栈的位置在程序每次运行时都有变化，上面这段代码只是简单的打印 main 函数中局部变量 local 的地址，每次运行打印结果都可能不同。

在 64 位 linux 系统上，地址的范围：0x7fff0001b698 0x7ffffffaa4a8。因此，采用了栈随机化的机制，即使许多机器都运行相同的代码，它们的栈地址也是不同的。 在 linux 系统中，栈随机化已经成为标准行为，它属于地址空间布局随机化的一种，简称 ASLR，采用 ASLR，每次运行时程序的不同部分都会被加载到内存的不同区域，这类技术的应用增加了系统的安全性，降低了病毒的传播速度。

• 栈破坏检测

编译器会在产生的汇编代码中加入一种栈保护者的机制来检测缓冲区越界，就是在缓冲区与栈保存的状态值之间存储一个特殊值，这个特殊值被称作金丝雀值，之所以叫这个名字，是因为从前煤矿工人会根据金丝雀的叫声来判断煤矿中有毒气体的含量。

金丝雀值是每次程序运行时随机产生的，因此攻击者想要知道这个金丝雀值具体是什么并不容易，在函数返回之前，检测金丝雀值是否被修改来判断是否遭受攻击。接下来，我们通过汇编代码看一下编译器是如何避免栈溢出攻击的。

图中这两行代码是从内存中读取一个数值，然后将该数值放到栈上，其中这个数值就是刚才提到的金丝雀值，存放的位置与程序中定义的缓冲区是相邻的。其中指令源操作数%fs:40 可以简单的理解为一个内存地址，这个内存地址属于特殊的段，被操作系统标记为"只读"，因此，攻击者是无法修改金丝雀值的。

函数返回之前，我们通过指令 xor 来检查金丝雀值是否被更改。如果金丝雀值被更改，那么程序就会调用一个错误处理例程，如果没有被更改，程序就正常执行。

• 限制可执行代码区域

最后一种机制是消除攻击者向系统中插入可执行代码的能力，其中一种方法是限制哪些内存区域能够存放可执行代码。

以前，x86 的处理器将可读和可执行的访问控制合并成一位标志，所以可读的内存页也都是可执行的，由于栈上的数据需要被读写，因此栈上的数据也是可执行的。

虽然实现了一些机制能够限制一些页可读且不可执行，但是这些机制通常会带来严重的性能损失，后来，处理器的内存保护引入了不可执行位，将读和可执行访问模式分开了。有了这个特性，栈可以被标记为可读和可写，但是不可执行。检查页是否可执行由硬件来完成，效率上没有损失。

以上这三种机制，都不需要程序员做任何额外的工作，都是通过编译器和操作系统 来实现的，单独每一种机制都能降低漏洞的等级，组合起来使用会更加有效

参考资料

Datawhale CSAPP组队学习