从汇编的角度理解程序(一)—— 通过寄存器进行数据操作的指令流

我打算就汇编程序写一个系列博客。不过,其目的不是为了弄明白怎么写汇编语言,甚至不是为了弄明白如何读懂汇编程序。
它的目的只是为了揭秘黑魔法,披露计算机程序更深层本质:

  • 程序其实就是对数据进行操作的有序指令流
  • 有序的指令流能通过跳转实现程序分支和循环
  • 还能通过跳转和 stack 内存模式实现函数调用
  • 通过规范的内存布局和读写操作实现复杂的数据结构

一、程序其实就是对数据进行操作的有序指令流

直接从 CS:APP 里面的一个实例程序开始吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// mstore.c, from CS:APP
long mult2(long x, long y);

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

// main.c, from CS:APP
void multstore(long x, long y, long* dest);

int main() {
long d;
multstore(2, 3, &d);
return 0;
}

long mult2(long x, long y) {
long s = x * y;
return s;
}

编译此程序,得到的二进制文件中包含如下片段:
53 48 89 d3 e8 42 00 00 00 48 89 03 5b c3
这些数字看起来毫无意义。然而如果从汇编语境来看,每个数字(字节)都对应着汇编指令,比如 53 就对应 push %rbx
把这段字节全部翻译成汇编指令的话,我们就能得到这样的程序:

offset Binary Assembly
0 53 push %rbx
1 48 89 d3 mov %rdx, %rbx
4 e8 42 00 00 00 callq 4b
9 48 89 03 mov %rax, (%rbx)
c 5b pop %rbx
d c3 retq

在这些指令中,% 开头的符号后面是寄存器名字, %rax 代表寄存器 rax 处保存的值,以 R[%rax] 为缩写。 (%rax) 代表内存 R[%rax] 处保存的值,以 M[R[%rax]] 为缩写。 而这段程序中的每个指令的意思是:

  • R[%rsp] = R[%rsp] - 8M[R[%rsp]] = R[%rbx]
  • R[%rbx] = R[%rdx]
  • R[%rsp] = R[%rsp] - 8M[R[%rsp]] = 9%R[rip] = 4b,接下来执行 offset 为 R[%rip] 也就是 4b 处的指令(此处没有写出)
  • M[R[%rbx]] = R[%rax]
  • R[%rbx] = M[R[%rsp]]R[%rsp] = R[%rsp] + 8
  • R[%rip] = M[R[%rsp]], R[%rsp] = R[%rsp] + 8,接下来执行 offset 为 R[%rip] 处的命令

按顺序执行这些指令的话,我们基本上就是在干这种事:

  • 执行栈伸展, 保存 %rbx 处的值到栈内存顶部(top of stack memory)上
  • 复制第三个参数的值到 %rbx 处(说明当前函数至少有 3 个参数)
  • 调用某个函数,彼函数的第一个指令位置为 4b (彼函数以当前函数的前两个参数为参数,并且只有两个参数)
  • 把函数的返回值保存到内存某处(第三个参数指明的内存位置处,第三个参数是指针)
  • 把之前保存到栈内存上的 %rbx 处的值再取回到 %rbx 处,执行栈收缩
  • 从当前函数返回

可以猜到,这段字节正是函数 multstore 所做的事情。函数变成了汇编指令,成为了按顺序执行操作寄存器数据的汇编指令。
而如果我们翻译整个程序的二进制,得到的也只是一个更长汇编程序,但是还是使用同样的汇编指令集,同样的寄存器集,仍然保持着其汇编语言简单(并非容易)的特点:

  • 只是按顺序执行
  • 只通过有限寄存器进行有限数据操作

也就是说,不管一个多么复杂的软件,不管其设计模式、系统架构和软件作用如何,最后都成为了简单的有序 CPU 指令流。但是,这些简单的指令流,是如何达到复杂的软件程序的目的的呢?
在明白这些之前,我觉得需要对汇编语言本身再多一些理解,即:

  • 什么是按顺序执行?
  • 有限寄存器有哪些?
  • 有限数据操作有哪些?

二、按顺序执行

按顺序执行的意思不就是字面意思吗?但是仔细想想,“顺序”本身就是一种信息,并且这种信息是明确而没有歧义的。那么,汇编指令的顺序是怎么来的呢?
在上面的例子中我们看到有序的 6 个汇编指令实现了函数 multstore 的功能,而且它们恰好只是完成了 multstore 的功能,没有其它动作(调用一次函数和保存结果),可以说非常紧凑。
所以说,汇编指令不仅是按顺序的执行以实现软件的目的的,而且是以实现函数功能为基本单元组合在一起的。实现一个函数的汇编指令紧挨在一起,并且中间不会夹杂实现其它函数功能的指令。(把这些指令统称为一个过程,对应程序里面的一个函数)
我们知道,函数是有状态的,包含各种数据:参数、本地变量、返回值或者更复杂一点的栈空间。
而我们也汇编指令只是通过寄存器操作数据,那么,过程是如何实现函数的状态的?

三、有限寄存器

汇编指令过程只是通过寄存器操作数据,如何实现函数的状态?
解决之道是,把每个寄存器赋予明确而独立的职责,通过寄存器之间的组合实现复杂的状态。
寄存器的数量不多,大体分为三类:整数类寄存器,条件码寄存器和 PC 寄存器。其中最复杂的是整数类寄存器,CPU 大多数时候都是在读写这些寄存器。条件码寄存器用来标志操作的一些结果,比如是否为负数、是否溢出。PC 寄存器里面保存着下一条指令的内存地址。

3.1 整数类寄存器

整数类寄存器,顾名思义,就是保存整数的寄存器。其实所谓整数,就是一串比特。
目前总共有 16 个整数寄存器,每个寄存器有 64 个比特的空间,可以保存 8、16、32 和 64 位的数据类型。根据保存的数据类型的大小不同,同一个寄存器的名字也会不同。下表是所有整数寄存器的数据类型和名称的对应表,最后一列是它们所承担的职责。

64 位 32 位 16 位 8 位 职责
%rax %eax %ax %al 返回值
%rbx %ebx %bx %bl 被调用者保存
%rcx %ecx %cx %cl 第四个参数
%rdx %edx %dx %dl 第三个参数
%rsi %esi %si %sil 第二个参数
%rdi %edi %di %dil 第一个参数
%rbp %ebp %bp %bpl 帧指针
%rsp %esp %sp %spl 栈指针
%r8 %r8d %r8w %r8b 第五个参数
%r9 %r9d %r9w %r9b 第六个参数
%r10 %r10d %r10w %r10b 调用者保存
%r11 %r11d %r11w %r11b 调用者保存
%r12 %r12d %r12w %r12b 被调用者保存
%r13 %r13d %r13w %b13b 被调用者保存
%r14 %r14d %r14w %r14b 被调用者保存
%r15 %r15d %r15w %r15b 被调用者保存

数量有点多,16 * 4 = 64 个,但是其实是有规律的:

  • 最开始的 8 个比较混乱,命名序列是 abcd 四个字母、 si 和 di ,bp(base-pointer) 和 sp(stack-pointer);
  • 最开始 8 个寄存器,8 位的全部是 l 后缀,16 位的只有 abcd 序列加 x 后缀,32 位的在 16 位基础上加 e(extended) 前缀,64 位的在 16 位基础上加 r(register) 前缀;
  • 最开始 8 个寄存器,支持 4 个参数,1 个返回值,1 个帧指针,1 个栈指针,1 个被调用者保存;
  • r8 到 r15 明显是后来加入的 8 个寄存器,其后缀为 b、w、d 和空,分别代表 byte、word、double-word。byte 8 位,word 16 位,刚好对上;
  • r8 到 r15 添加了 2 个参数位置,4 个被调用者保存位置和 2 个以前没有的调用者保存位置;

简单说下职责,在后面讲栈模型时会再着重讲。

  • 被调用者保存:汇编指令虽然实现函数的功能,但是它唯一的数据存储地就是寄存器,换句话说,所有的函数实现过程共享寄存器。随着函数调用层次越深,要保存的本地变量就更多,但是寄存器的数量有限,怎么办?为了解决这个问题,汇编指令把寄存器分类成“被调用者保存”和“调用者保存”。被调用者保存的意思就是,过程 P 调用 Q 时,P 可以不用考虑 “被调用者保存”类的寄存器里面的值被修改了,因为 Q 这个被调用者有职责保证里面的值不会变。
  • 调用者保存:和“被调用者保存”相反,P 在调用 Q 后,Q 可能会改变这些寄存器的值,所以 P 这个调用者有职责保存里面的值。
  • 返回值: 属于调用者保存。一个函数有没有返回值,返回值是什么,不是取决于 %rax 里面的值,而是取决于后面的汇编指令怎么用它。如果从某个函数调用返回后,没有读取 %rax 里面的值,则说明函数没有返回值。如果读取的是 %eax, 说明返回的是 32 位的数据类型,%al 则说明返回的是 8 位的数据,如果读取的是 (%rax) 则说明返回的是指针,在从内存里面读取值。
  • 参数:属于调用者保存。最多可以通过寄存器保存 6 个参数。和 %rax 一样,汇编指令本身是没有参数的概念的,所以用几个参数、参数类型是什么,取决于后面的汇编指令怎么用它。如果参数数量超过 6 个,就需要保存到栈帧里面了。
  • 栈指针:既不属于调用者保存,也不属于被调用者保存,每次 call 和 ret 指令都会自动操作这个寄存器。用来保存函数栈顶的内存位置,而内存里面这个位置上的值通常为函数返回后要执行的下一条指令的位置。每次调用一个过程,%rbp 的值就会减 8(64 bits),从一个过程返回,就会加 8。
  • 帧指针:属于被调用者保存。用来保存函数栈帧空间的起始地址。有时候过程需要保存的数据超过了寄存器的数量,就要在栈内存上开辟空间。一般的做法是,把 %rbp 的旧值保存到栈上,把 %rsp 栈顶的值保存到 %rbp 上,把 %rsp 减去适当的值 X,减多少取决于需要分配多少的栈帧空间。根据 %rbp 的偏移量来使用栈帧空间内的其它内存位置,进行数据操作。结束后把 %rsp 的值添加 X, 从 %rbp 里面恢复 栈顶 %rsp,从栈上恢复 %rbp 的旧值。

3.2 条件码寄存器

条件码寄存器总共有 4 个,用来描述最近的那个数据操作所产生的结果的属性。

  • CF:进位标志,用来说明最近的操作是否使最高位产生了进位(无符号)
  • ZF:零标志,用来说明最近的操作结果是否为 0
  • SF:符号标志,用来说明最近的操作结果是否为负数
  • OF:溢出标志,用来说明最近的操作结果是否导致补码溢出(有符号)

基于条件码寄存器,我们就能做溢出检测和大小比较。
如果再加上跳转指令,我们就能实现分支和循环的功能了。

3.3 PC 寄存器

PC 寄存器 %rip 里面保存的是正要执行的指令的内存位置。 所以,改变 PC 寄存器的值,就是改变要执行的命令。
不过,这个值一般不能直接修改,而是在执行 callret 或者 je 等指令的时候自动改的。

四、有限数据操作

我们已经知道了汇编指令如何用寄存器和栈内存保存函数的状态,还有最重要的一部分:如何操作这些寄存器来实现函数的目的?
从本质上来说,汇编指令只有对寄存器的读写操作,但是根据其主要目的,可以把它们分为三类:

  • 传输操作,不涉及计算,单纯地设置寄存器的值,或者内存的值
  • 计算操作,对寄存器中的值进行计算并根据结果设置寄存器或者内存的值
  • 跳转操作,根据情况设置 PC 寄存器的值以实现跳转

下面分别讨论三种操作,看看它们能实现什么效果。不过,在此之前,我们还要了解一下操作数。

4.1 操作数

操作数嘛,就是“被操作的数”…之所以要单独讲一下,是因为有时候汇编指令里面的操作数自身也包含了操作在里面。

类型 格式 数值 缩写
立即数 $Imm Imm Imm
寄存器 ra 寄存器 ra 处所存储的值 R[ra]
存储器 Imm 内存 Imm 处所存储的值 M[Imm]
存储器 (ra) 内存 R[ra] 处所存储的值 M[R[ra]]
存储器 Imm(ra) 内存 Imm + R[ra] 处所存储的值 M[Imm + R[ra]]
存储器 (ra, rb) 内存 R[ra] + R[rb] 处所存储的值 M[R[ra] + R[rb]]
存储器 Imm(ra, rb) 内存 Imm + R[ra] + R[rb] 处所存储的值 M[Imm + R[ra] + R[rb]]
存储器 (,rb, s) 内存 R[rb] * s 处所存储的值 M[R[rb] * s]
存储器 Imm(,rb, s) 内存 Imm + R[rb] * s 处所存储的值 M[Imm + R[rb] * s]
存储器 (ra, rb, s) 内存 R[ra] + R[rb] * s 处所存储的值 M[R[ra] + R[rb] * s]
存储器 Imm(ra, rb, s) 内存 Imm + R[ra] + R[rb] * s 处所存储的值 M[Imm + R[ra] + R[rb] * s]

4.2 传输操作

传输操作往往是把数据从寄存器/内存传输到另一个寄存器/内存,或者单纯地只是设置设置一个寄存器/内存的值。但是,如果有两个操作数时,不能两个操作数都是内存,必须借助一个寄存器中转。
下面是一些常见的传输操作指令。

操作指令 形式 作用
movq movq S, D 把 64 位操作数 S 复制到 64 位操作数 D
movl movl S, D 把 32 位操作数 S 复制到 32 位操作数 D
movzbq movzbq S, D 把 8 位操作数 S 复制到 64 位操作数 D, 高位用 0 补充
movsbq movsbq S, D 把 8 位操作数 S 复制到 64 位操作数 D, 高位用 S 的最高位补充
pushq pushq S R[%rsp] 减 8,把 64 位操作数 S 复制到 M[R[%rsp]]
popq popq D M[R[%rsp]] 复制到 64 位操作数 D, 把 R[%rsp] 加 8
leaq leaq S, D 把 操作数 S 的地址而不是值复制到 64 位操作数 D
sete sete D ZF 寄存器的值复制到 D
sets sets D SF 寄存器的值复制到 D
setg setg D ~(SF ^ OF) & ~ZF 的值复制到 D
seta seta D ~CF & ~SF 的值复制到 D
cmove cmove S, D 如果 ZF1,复制 SD
cmovs cmovs S, D 如果 SF1, 复制 SD
cmovg cmovg S, D 如果 ~(SF ^ OF) & ~ZF1, 复制 SD
cmova cmova S, D 如果 ~CF & ~SF1, 复制 SD
cltq cltq 把 32 位 %eax 拓展到 64 位 %rax,用最高位补位
clto clto 把 64 位 %rax 拓展到 128 位 %rdx:%rax,用最高位补位

由于本文的主要目的不是讲解汇编语法,所以还有很多根据数据类型或者状态码而生成的变体指令没有列出来。比如 MOV/PUSH/POP/LEA 族里面还有 bw 对应的 8 位和 16 位数据操作都没有列出,SET/CMOV 族里面还有 nensgena 这些看字幕能猜出来意思的数据位没有列出。
不过,我觉得还是需要 MOVLEA 的区别:

  • movq 8(%rdx, %rcx, 4), %rax, 把 M[8 + R[%rdx] + R[%rcx] * 4] 复制到 %rax
  • leaq 8(%rdx, %rcx, 4), %rax, 把 8 + R[%rdx] + R[%rcx] * 4 复制到 %rax

SETCMOV 指令一般不会单独使用。setg D 的意思为:当(有符号数) A 大于 B 时,设置 D 的值为 1,这里的 AB,通常是最近某次 CMP 或者 TEST 指令中的两个数。cmovg 的意思为: 当有符号数 A 大于 B 时,复制 S 的值到 D。g(reater)/l(ess) 后缀用于有符号数,a(bove)/b(elow) 用于无符号数。
关于 cmptest 指令,接下来还会再说明。

4.3 计算操作

计算操作其实就是常见的布尔运算、加减乘除、位移和比较。

操作指令 形式 作用
OR or S, D D = D | S
XOR xor S, D D = D ^ S
AND and S, D D = D & S
NOT not D D = ~D
NEG neg D D = -D
INC inc D D = D + 1
DEC dec D D = D - 1
ADD add S, D D = D + S
SUB sub S, D D = D - S
IMUL imul S, D D = D * S, 只能用于 64 位数
MUL mulq S 64 位无符号数 SR[%rax] 相乘得到 128 位数,保存在 %rdx:%rax
IMUL imulq S 64 位有符号数 SR[%rax] 相乘得到 128 位数,保存在 %rdx:%rax
DIV div S 128 位无符号数 %rdx:%rax 除以 64 位无符号 S,余数保存在 %rdx, 商保存在 %rax
IDIV idiv S 128 位有符号数 %rdx:%rax 除以 64 位有符号 S,余数保存在 %rdx, 商保存在 %rax
SHL shl k, D D 逻辑左移 k
SAL sal k, D D 算术左移 k
SHR shr k, D D 逻辑右移 k
SAR sar k, D D 算术右移 k
CMP cmp S1, S2 S2S1 比 (S2 - S1)
TEST test S1, S2 检测 S1 & S2

以上指令表同样没有列出它们各自依据数据类型而产生的变体。这些操作指令在计算和更新目标时,也会根据计算的结果来设置标志寄存器的值。由于这不是一篇讲解汇编的文章,我就不去细说每种指令对标志寄存器的操作了。
当然,CMPTEST 指令还是不能忽略,跳转操作可少不了它们的功劳。
CMPSUB 指令执行的计算是一样的,用 S2 - S1TESTAND 的计算也是一样的, S1 & S2。 区别在于,CMPTEST 指令在计算完后不会更新 S2,只会设置条件寄存器。
我们可以用一个比较两个数大小并返回结果的函数来说明汇编指令是如何用 CMP 指令和条件寄存器达成目标的。

1
2
3
4
5
// c 函数
int comp(long a, long b) {
if (b > a) return 1;
return 0;
}

下面是汇编代码:

1
2
3
4
5
// a in %rdi, b in %rsi, return value in %eax
cmpq %rdi, %rsi // 根据 b - a 的结果设置条件寄存器
setg %al // 如果 b > a, 设置 8 位数据 al 为 1, 否则为 0
movzbl %al, %eax // 把 8 位数据 al 用零拓展到 32 位 eax
ret // 返回

上例中的 b - a 会如何设置条件寄存器呢?

  • 首先,CF 会被忽略,因为两个数都是有符号数
  • 如果 b - a == 0, 那 ZF1,否则为 0
  • 如果 b - a < 0, 那么 SF1, 否则为 0
  • 如果 b - a 产生了符号溢出,那么 OF1,否则为 0

setg 如何根据四个条件寄存器获知是否 b > a 呢?

  • 首先还是忽略 CF,因为 g 后缀用于有符号数的判断
  • ZF 不能为 1,否则 b == a,所以 ~ZF 必须为 True
  • b - a 不能小于 0,也就是说 ~SF 必须为 True
  • 但是如果考虑到溢出的情况,假设 a 为最小的负数, b2b - a 会得到一个溢出的负数,此时 b 是大于 a 的。所以 b - a 小于零也 ok,前提是有溢出,OFTrue
  • 综合第三和第四点,得到 (SF & OF) | (~SF & ~OF), 即 ~(SF ^ OF)
  • 综合第二点和第五点,得到 b > a 的条件为:~(SF ^ OF) & ~ZF

看起来非常绕,但其实这是最复杂的组合情况了,判断不相等或者小于之类的情况都要简单点。

4.4 跳转操作

如果说传输指令和计算指令是实现程序基本功能的砖和瓦,那跳转指令就是建造复杂程序架构的梁和栋了。
跳转指令不多,总共就 3 个:CALLRETJMP (和基于条件码的 je, jg etc.)。
callret 指令是一对,分别用于调用函数(过程)和返回。
call 后面的数字 X 决定着接下来要执行的指令的地址。这个地址可以是基于这个数字的绝对地址,即 X 就是指令的地址,也可以是基于 call 指令后面那条指令地址 B 的相对寻址。在相对寻址的情况下,X 被当做一个有符号数,被 call 的指令地址是 B + X
在执行 call 指令时,会首先把 R[%rsp]8,并把 M[R[%rsp]] 设置为 B(返回地址),这样就实现了栈伸展。然后 R[%rip] 被设置为 B + X, 程序跳转到被 call 的指令处开始执行。
ret 后面不接任何操作数,它会把 R[%rip] 设置为 M[R[%rsp]], 然后把 R[%rsp] 加 8,实现栈收缩,并且跳转程序到当时调用 call 指令时压入栈中的 B 位置。
JMP 指令和 CALL 指令一样有两种寻址模式,不过它不会改变 R[%rsp],也就是不会改变栈。jejgsetesetg 这些指令一样,根据条件寄存器来决定要不要跳转。可以猜到,JMP 指令可以用来实现函数内的跳转,比如分支和循环。

五、总结

不管多么复杂的软件程序,到了汇编层面(最接近硬件的层面), 都成了简单的指令流。
这些指令流虽然简单,但是已经包含了所有必须得计算指令。并且,在状态寄存器、跳转指令和栈内存模式的配合下,我们已经隐约体会到了实现复杂软件的可能性。
接下来,我们还会进一步研究汇编指令是如何把这种可能性变成事实的:

  • 如何通过跳转实现程序分支和循环
  • 如何通过跳转和 stack 内存模式实现函数调用
  • 如何通过规范的内存布局和读写操作实现复杂的数据结构