程序的机器级表示

前言

了解了基础的编码知识后，下一步我们开始研究程序是如何在计算机当中表示和执行，我们将会深入了解程序中的分支、循环还有函数调用等是如何在使用机器码（机器语言）来表示，但是我们不会直接研究机器语言，毕竟机器语言都是由 0、1 组成的，实在不利于阅读和理解，我们将会研究机器语言的助记符，汇编语言，它在底层是与机器语言等效的，所以研究它其实是等同于研究机器语言的。不同的 cpu 架构的指令集架构也不同，后续的研究中将会基于 Intel 的 x86-64 架构。

硬件抽象

计算机系统使用了多种不同形式的抽象，利用更简单的抽象模型来隐藏具体的实现细节，即使是机器级代码也已经使用到了许多的抽象模型，其中两点尤为重要的。

指令集架构（ISA）
虚拟地址

指令集架构定义了处理器状态，指令的格式以及每条指令对状态的影响。大多数 ISA，比如 x86-64，arm 等，会将程序的行为描述成每条指令都是顺序执行的，一条指令执行完后，下一条才开始。可是处理器的硬件实际上要远比描述的更精密，硬件会并发的执行多条指令，但又会采取措施来保证整体行为和 ISA 指定的顺序执行的结果是一致的。

虚拟地址将机器级代码使用的内存看上去是一个巨大的字节数组，但实际上储存器系统是将多个硬件储存器和操作系统软件组合起来的。

编译

在下面的研究中，我们不会直接编写汇编代码，而是使用 c 语言来生成对应的汇编代码。

比如有以下示例代码保存在 mstore.c 文件中：

long mult2(long, long);

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

使用 gcc 的命令行选项-S 可以直接生成对应汇编码：

1	gcc -Og -S mstore.c

使用 gcc 的命令行选项-c 可以直接编译并汇编 c 代码，得到对应的机器码：

1	gcc -Og -c mstore.c

使用 objdump 来查看机器码对应的汇编码：

1	objdump -d mstore.o

数据格式

由于是从 16 位体系结构拓展位 32 位的。Intel 将术语“字（word）”表示 16 位数据格式，所以 32 位的为“双字（double words）”或者“长字（long words）”，64 位的位“四字（quad words）”。

不同的数据格式的指令会使用后缀来表示对应：

C 声明	Intel 数据类型	后缀	大小（byte）
char	字节	b	1
short	字	w	2
int	双字	l	4
long	四字	q	8
char*	四字	q	8
float	单精度	s	4
double	双精度	l	8

访问信息

x86-64 的 CPU 包含一组 16 个存储 64 位值的通用目的寄存器。

64 位寄存器	低 32 位	低 16 位	低 8 位	描述
rax	eax	ax	al	返回值
rbx	ebx	bx	bl	被调用者保存
rcx	ecx	cx	cl	第 4 个参数
rdx	edx	dx	dl	第 3 个参数
rsi	esi	si	sil	第 2 个参数
rdi	edi	di	dil	第 1 个参数
rbp	ebp	bp	bpl	被调用者保存
rsp	esp	sp	spl	栈指针
r8	r8d	r8w	r8b	第 5 个参数
r9	r9d	r9w	r9b	第 6 个参数
r10	r10d	r10w	r10b	调用者保存
r11	r11d	r11w	r11b	调用者保存
r12	r12d	r12w	r12b	被调用者保存
r13	r13d	r13w	r13b	被调用者保存
r14	r14d	r14w	r14b	被调用者保存
r15	r15d	r15w	r15b	被调用者保存

操作数指示符

大多数指令都有一个或多个操作数（operand），用于表示执行的指令中要使用的源数据值，以及防止结果的目的位置。x86-64 支持多种操作数格式，大致分为三类：

立即数：表示一个常数，书写格式为$后跟着常数，比如$-57,$0x1F
寄存器：表示一个寄存器中的值，书写格式为%后跟着寄存器名称，比如%rax，%r8d
内存引用：表示内存中具体地址的值，书写格式有很多种

类型	格式	操作数值	名称
立即数	$$Imm$	$Imm$	立即数寻址
寄存器	$r_a$	$R[r_a]$	寄存器寻址
存储器	$Imm$	$M[Imm]$	绝对寻址
存储器	$(r_a)$	$M[R[r_a]]$	间接寻址
存储器	$Imm(r_b)$	$M[Imm+R[r_b]]$	(基址+偏移量)寻址
存储器	$(r_b,r_i)$	$M[R[r_b]+R[r_i]]$	变址寻址
存储器	$Imm(r_b,r_i)$	$M[Imm+R[r_b]+R[r_i]]$	变址寻址
存储器	$(,r_i,s)$	$M[R[r_i]*s]$	比例变址寻址
存储器	$Imm(,r_i,s)$	$M[Imm+R[r_i]*s]$	比例变址寻址
存储器	$(r_b,r_i,s)$	$M[R[r_b]+R[r_i]*s]$	比例变址寻址
存储器	$Imm(r_b,r_i,s)$	$M[Imm+R[r_b]+R[r_i]*s]$	比例变址寻址

数据传送指令

MOV 类指令可以将数据从源位置复制到目的目的位置。

指令	效果	描述
MOV S, D	S -> D	传送
movb		传送字节
movw		传送字
movl		传送双字
movq		传送四字
movabsq I, R	I -> R	传送绝对的四字

其中的 S 可以为立即数，寄存器，存储器，D 可以为寄存器，存储器，但是 S 和 D 不能同时为存储器。
将数据复制到寄存器的低位时，寄存器的高位不会改变数值，但有一个例外是 movl 将数据复制到低 4 字节时，高 4 字节会置为 0，以下给出一个例子：

movabsq $0x0011223344556677, %rax  # %rax=0x0011223344556677
movb $-1, %al                      # %rax=0x00112233445566FF
movw $-1, %ax                      # %rax=0x001122334455FFFF
movl $-1, %eax                     # %rax=0x00000000FFFFFFFF
movq $-1, %rax                     # %rax=0xFFFFFFFFFFFFFFFF

以上指令是适用于源与目的的数据格式相同的情况，当目的的数据格式大于源的时候有以下指令来解决问题：

零拓展数据传送指令：

指令	效果	描述
MOVZ S, D	S -> D	进行零拓展并传送
movzbw		将做了零拓展的字节传送到字
movzbl		将做了零拓展的字节传送到双字
movzbq		将做了零拓展的字节传送到四字
movzwl		将做了零拓展的字传送到双字
movzwq		将做了零拓展的字传送到四字

提供的指令中并没有将做了零拓展的双字传送到四字，因为按照 x86-64 的采用的惯例，为寄存器生成 32 位的指令都会将该寄存器的高 4 字节置为 0 ，所以使用 movl 指令也是实现相同效果。

符号拓展数据传送指令：

指令	效果	描述
MOVS S, D	S -> D	进行符号拓展并传送
movsbw		将做了符号拓展的字节传送到字
movsbl		将做了符号拓展的字节传送到双字
movsbq		将做了符号拓展的字节传送到四字
movswl		将做了符号拓展的字传送到双字
movswq		将做了符号拓展的字传送到四字
movslq		将做了符号拓展的双字传送到四字
cltq	符号拓展(%eax) -> %rax	将%eax 符号拓展到%rax

其中的cltq指令和movslq %eax, %rax效果一致，只是该指令的编码更紧凑。

压入和弹出栈数据

以下两个指令可以将数据压入和弹出程序栈：

指令	效果	描述
pushq S	R[%rsp]-8 -> R[%rsp]; S -> M[R[%rsp]]	将四字压入栈
popq D	M[R[%rsp]] -> D; R[%rsp]+8 -> R[%rsp]	将四字弹出栈

算术和逻辑操作

这些指令类主要分为四类：加载有效地址、一元操作、二元操作、移位，每个指令类中都有四种不同大小数据格式的相应指令除了加载有效地址，地址只有 64 位的操作。

指令	效果	描述
leaq S, D	&S -> D	加载有效地址
INC D DEC D NEG D NOT D	D+1 -> D D-1 -> D -D -> D ~D -> D	加 1 减 1 取负取反
ADD S, D SUB S, D IMUL S, D XOR S, D OR S, D AND S, D	D+S -> D D-S -> D D*S -> D D^S -> D D\|S -> D D&S -> D	加减乘异或或与
SAL k, D SHL k, D SAR k, D SHR k, D	D<<k -> D D<<k -> D D>>k -> D D>>>k -> D	左移左移（等同于 SAL）算术右移逻辑右移

特殊的算术操作

两个 64 位的有符号或者无符号整数相乘得到的乘积需要 128 位来表示。x86-64 指令集对 128 位操作提供有限的支持，按照命名习惯，Intel 将 16 字节数成为八字（oct word），以下为支持产生两个 64 位数字的全 128 位乘积以及整数除法的指令：

指令	效果	描述
imulq S mulq S	S * R[%rax] -> R[%rdx]:R[%rax]	有符号全乘法无符号全乘法
cqto	符号拓展（R[%rax]） -> R[%rdx]:R[%rax]	转换为八字
idivq S	R[%rdx]:R[%rax] / S -> R[%rax] R[%rdx]:R[%rax] mod S -> R[%rdx]	有符号除法
divq S	R[%rdx]:R[%rax] / S -> R[%rax] R[%rdx]:R[%rax] mod S -> R[%rdx]	无符号除法

使用 64 位寄存器来进行全 128 位乘法时，会将乘积的高 64 位放在%rdx 中，低 64 位放在%rax 中。进行除法时，会将商放在%rax 中，余数放在%rdx 中。

控制

至此我们仅仅考虑了直线代码的行为，但是实际代码中还有分支和循环。jump 指令就可以根据条件码等信息控制 cpu 执行指定位置的指令从而实现分支和循环。

条件码

除了整数寄存器，CPU 维护着一组单个位的条件码寄存器，当进行算术逻辑操作、CMP、TEST 等指令时就会更新这几个值。

CF：进位标志。最近操作使最高位发生了进位。可以用来检测无符号操作的溢出。
ZF：零标志。最近操作得出的结果为 0。
SF：符号标志。最近操作得到的结果为负数。
OF：溢出标志。最近的操作导致一个补码溢出，正溢出或者负溢出。

CMP 和 TEST 指令：

指令	基于	描述
CMP S1, S2	S2-S1	比较
cmpb		比较字节
cmpw		比较字
cmpl		比较双字
cmpq		比较四字
TEST S1, S2	S1&S2	测试
testb		测试字节
testw		测试字
testl		测试双字
testq		测试四字

CMP 和 SUB 以及 TEST 和 AND 指令的区别在于不会将计算的结果存入寄存器当中。

访问条件码

条件码通常不会直接读取，通常的使用方法有三种：

根据条件码的组合设置一个字节为 0 或者 1
根据条件码有条件地跳转执行程序的其他部分
根据条件码有条件地传送数据

分别对应的指令为：

有条件地设置字节（SET）

指令	同义名	效果	设置条件
sete D	setz	ZF -> D	相等/零
setne D	setnz	~ZF -> D	不相等/非零
sets D		SF -> D	负数
setns D		~SF -> D	非负数
setg D	setnle	~(SF^OF) & ~ZF -> D	有符号大于
setge D	setnl	~(SF^OF) -> D	有符号大于等于
setl D	setnge	SF^OF -> D	有符号小于
setle D	setng	(SF^OF) \| ZF -> D	有符号小于等于
seta D	setnbe	~CF & ~ZF -> D	无符号大于
setae D	setnb	~CF -> D	无符号大于等于
setb D	setnae	CF -> D	无符号小于
setbe D	setna	CF \| ZF -> D	无符号小于等于

set 指令的后缀不是表示数据格式的大小，实际含义为：g，greater（有符号大于）；l，less（有符号小于）；a，above（无符号大于）；b，below（无符号小于）；e，equal（相等）；n，not（非）。

有条件地跳转（JMP）

指令	同义名	跳转条件	描述
jmp Label		1	直接跳转
jmp *Operand		1	间接跳转
je Label	jz	ZF	相等/零
jne Label	jnz	~ZF	不相等/非零
js Label		SF	负数
jns Label		~SF	非负数
jg Label	jnle	~(SF^OF) & ~ZF	有符号大于
jge Label	jnl	~(SF^OF)	有符号大于等于
jl Label	jnge	SF^OF	有符号小于
jle Label	jng	(SF^OF) \| ZF	有符号小于等于
ja Label	jnbe	~CF & ~ZF	无符号大于
jae Label	jnb	~CF	无符号大于等于
jb Label	jnae	CF	无符号小于
jbe Label	jna	CF \| ZF	无符号小于等于

后缀含义同 set 指令一致

有条件地传送（CMOV）

指令	同义名	传送条件	描述
comve S, R	cmovz	ZF	相等/零
comvne S, R	cmovnz	~ZF	不相等/非零
comvs S, R		SF	负数
comvns S, R		~SF	非负数
comvg S, R	cmovnle	~(SF^OF) & ~ZF	有符号大于
comvge S, R	cmovnl	~(SF^OF)	有符号大于等于
comvl S, R	cmovnge	SF^OF	有符号小于
comvle S, R	cmovng	(SF^OF) \| ZF	有符号小于等于
comva S, R	cmovnbe	~CF & ~ZF	无符号大于
comvae S, R	cmovnb	~CF	无符号大于等于
comvb S, R	cmovnae	CF	无符号小于
comvbe S, R	cmovna	CF \| ZF	无符号小于等于

后缀含义同 set 指令一致

跳转指令的编码

虽然在这里我们不关心机器码格式的细节，但是理解跳转指令的目标是如何编码的对后续研究链接是非常重要的。
现在有以下汇编代码及其机器码：

0000000000000000 <loop>:
   0:   f3 0f 1e fa             endbr64
   4:   89 f8                   mov    %edi,%eax
   6:   eb 02                   jmp    a <loop+0xa>
   8:   d1 f8                   sar    $1,%eax
   a:   85 c0                   test   %eax,%eax
   c:   7f fa                   jg     8 <loop+0x8>
   e:   c3                      ret

其中 jmp 指令的目标为 a <loop+0xa>，对应的编码为 0x02，即 2，而 jg 指令的目标为 8 <loop+0x8>，对应的编码为 0xfa，即-6，可以看出跳转指令的目标的编码是相对的，计算方式为下一条指令的地址加上偏移量，比如 jmp 指令的目标为 0x0a，实际上是 0x08+0x02 得到的，jg 指令的目标为 0x08，实际上是 0x0e+0xfa 得到的，这样编码的好处在于，当这个方法被重定义到其他地方中时该代码不需要发生改变。

过程

过程是软件中的一种重要的抽象，它提供了一种封装代码的方式，在不同编程语言中会有不同的形式，比如函数，方法等。所以要对过程进行机器级的支持，假设 P 调用 Q，Q 执行后返回到 P，这一个调用的动作主要包含以下机制：

传递控制，进入过程 Q 时，程序计数器需要设置为 Q 代码的起始地址，然后在返回时需要设置回 P 中调用 Q 后面的那条指令。
传递参数，P 需要能够为 Q 提供一个或多个参数，Q 必须能向 P 返回一个值。
分配和释放内存，在开始时，需要为 Q 的局部变量分配空间，在返回前，需要释放掉这些空间。

运行时栈

过程运行时超出寄存器的部分就要在内存中开辟空间，这个部分称为过程的栈帧，依然假设 P 调用 Q，在内存中会产生以下结构：

栈底

较早的帧	...		^ \| \| 地址增大 \| \|
P的帧	...
	参数n
	...
	参数7
	返回地址
Q的帧	被保存的寄存器	<- %rbp
	局部变量
	参数构造区	<- %rsp

栈“顶”

此时为 Q 运行完准备返回时的内存情况，%rsp 寄存器记录栈顶位置，%rbp 寄存器记录栈底位置

控制转移

使用 call 指令调用过程，ret 指令从过程调用中返回。
在读取完 call 指令后会将程序计数器（PC）的值压入栈中，也就是返回地址，在 x86-64 中使用%rip 来表示 PC，然后将 PC 设置为过程的起始地址，实现将控制从 P 转到 Q 中。
在读取完 ret 指令后会将 Q 中的栈帧回收，将被保护的寄存器恢复，然后将返回地址弹出，并将 PC 设置为弹出值，实现将控制从 Q 返回到 P 中。

数据传送

除了控制转移，还需要实现参数传递。在 x86-64 中大部分参数都是通过寄存器实现的，当 P 调用过程 Q 时，P 的代码必须先将参数复制到适当的寄存器当中，而当 Q 返回到 P 时，P 的代码就可访问寄存器%rax 中的返回值。
x86-64 中可以通过寄存器最多传递 6 个整型参数，寄存器的使用是有特殊顺序的，具体使用哪个长度的寄存器是根据数据格式长度决定的，规则依据下表：

参数大小（位）	参数顺序
参数大小（位）	1	2	3	4	5	6
64	%rdi	%rsi	%rdx	%rcx	%r8	%r9
32	%edi	%esi	%edx	%ecx	%r8d	%r9d
16	%di	%si	%dx	%cx	%r8w	%r9w
8	%dil	%sil	%dl	%cl	%r8b	%r9b

超过六个的参数就要通过栈来传递了，下面有一个例子：

c 代码

void proc(long a1,long* a1p,int a2,int* a2p,short a3,short* a3p,char a4,char* a4p){
    *a1p+=a1;
    *a2p+=a2;
    *a3p+=a3;
    *a4p+=a4;
}

汇编代码

proc:
    .cfi_startproc
    endbr64
    movq    16(%rsp), %rax   # 获取a4p
    addq    %rdi, (%rsi)     # *a1p+=a1
    addl    %edx, (%rcx)     # *a2p+=a2
    addw    %r8w, (%r9)      # *a3p+=a3
    movl    8(%rsp), %edx    # 获取a4
    addb    %dl, (%rax)      # *a4p+=a4
    ret
    .cfi_endproc

可以看到参数 a4 和 a4p 都是通过%rsp 加偏置量来获取的，所有通过栈传递的传递的参数都是向 8 字节对齐的。
第一个通过栈传递的传递的参数并不是栈顶数据而是栈顶的下一个数据，这是因为执行 call 指令后会将返回地址压入栈中，所以栈顶数据为返回地址。

栈上的局部存储

过程的局部变量会在栈空间存储，在过程开始时，栈指针会减小来申请空间，当过程结束时，栈指针会增加来回收申请的空间。

c 代码

long caller_proc(){
    long a1=1;
    int a2=2;
    short a3=3;
    char a4=4;
    proc(a1,&a1,a2,&a2,a3,&a3,a4,&a4);
    return (a1+a2)*(a3-a4);
}

汇编代码

caller_proc:
.LFB1:
    .cfi_startproc
    endbr64
    subq    $40, %rsp       # 申请空间
    .cfi_def_cfa_offset 48
    movq    %fs:40, %rax
    movq    %rax, 24(%rsp)
    xorl    %eax, %eax
    movq    $1, 16(%rsp)
    movl    $2, 12(%rsp)
    movw    $3, 10(%rsp)
    movb    $4, 9(%rsp)
    leaq    12(%rsp), %rcx
    leaq    16(%rsp), %rsi
    leaq    9(%rsp), %rax
    pushq   %rax
    .cfi_def_cfa_offset 56
    pushq   $4
    .cfi_def_cfa_offset 64
    leaq    26(%rsp), %r9
    movl    $3, %r8d
    movl    $2, %edx
    movl    $1, %edi
    call    proc
    movslq  28(%rsp), %rax
    addq    32(%rsp), %rax
    movswl  26(%rsp), %edx
    movsbl  25(%rsp), %ecx
    subl    %ecx, %edx
    movslq  %edx, %rdx
    imulq   %rdx, %rax
    addq    $16, %rsp
    .cfi_def_cfa_offset 48
    movq    24(%rsp), %rdx
    subq    %fs:40, %rdx
    jne     .L5
    addq    $40, %rsp       # 回收空间
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret

寄存器中的局部存储空间

寄存器组是唯一被过程共享的资源，虽然在给定时刻只有一个过程是活动的，但我们仍然要保证调用者调用被调用者时，被调用者不能覆盖调用者稍后会使用的寄存器。为此 x86-64 采用了一组惯例来保证这一点。根据惯例，寄存器%rbx，%rbp 和%r12~%r15 被划分为被调用者保存寄存器。被调用过程在过程开始时有义务保存好这些寄存器中的值，在过程结束准备返回时应当恢复这些寄存器中的值，下面有一个例子：

c 代码：

long P(long x,long y){
    long u = Q(y);
    long v = Q(x);
    return u+v;
}

汇编代码：

P:
.LFB0:
    .cfi_startproc
    endbr64
    pushq   %rbp            # 保存rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    pushq   %rbx            # 保存rbx
    .cfi_def_cfa_offset 24
    .cfi_offset 3, -24
    subq    $8, %rsp
    .cfi_def_cfa_offset 32
    movq    %rdi, %rbp
    movq    %rsi, %rdi
    movl    $0, %eax
    call    Q
    movslq  %eax, %rbx
    movq    %rbp, %rdi
    movl    $0, %eax
    call    Q
    cltq
    addq    %rbx, %rax
    addq    $8, %rsp
    .cfi_def_cfa_offset 24
    popq    %rbx            # 恢复rbx
    .cfi_def_cfa_offset 16
    popq    %rbp            # 恢复rbp
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc