CS:APP 第三章学习笔记

2022-09-192023-01-09436csapp学习笔记

CS:APP 第三章 “Machine-Level Representation of Programs” 的学习笔记。

这章的主要内容为汇编（machine-level programming）。

近年来，随着编译器和高级语言的发展，手写汇编、机器码的需求越来越低，但阅读、理解编译器的输出在优化程序性能、避免安全漏洞等方面依然重要。

Program Encodings

汇编/机器码中的程序状态

x86-64 的程序状态包含：

program counter，表示待执行的下一条指令的地址，用 %rip 表示
register file，16 个用来存储整型的寄存器
status flags，用来存储最近执行的运算的状态
vector registers，用来存储多个整型或浮点数

将 C 代码编译为汇编代码

可以通过 gcc -S 生成汇编代码，通过 gcc -Og 来启用“以调试体验为目标的优化”（后文中叙述的很多编译行为都是需要一些基本的优化的，如果完全不启用任何优化，可能编译结果会有很大的差别；也就是说，完全不优化和过度优化都会降低汇编代码的可读性）。

为了方便，可以用一条命令编译并不留文件地查看汇编代码: gcc a.c -Og -S -o - | bat -l asm。

例如，下面的代码：

long mult2(long, long);

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

long mult2(long, long);

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

编译为如下的汇编代码：

	.file	"a.c"
	.text
	.globl	multstore
	.type	multstore, @function
multstore:
.LFB0:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	%rdx, %rbx
	call	mult2@PLT
	movq	%rax, (%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE0:
	.size	multstore, .-multstore
	.ident	"GCC: (GNU) 12.2.0"
	.section	.note.GNU-stack,"",@progbits

	.file	"a.c"
	.text
	.globl	multstore
	.type	multstore, @function
multstore:
.LFB0:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	%rdx, %rbx
	call	mult2@PLT
	movq	%rax, (%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE0:
	.size	multstore, .-multstore
	.ident	"GCC: (GNU) 12.2.0"
	.section	.note.GNU-stack,"",@progbits

反汇编与机器码

可以通过 objdump 反汇编，例如 gcc a.c -Og -c && objdump -d a.o 得到：

a.o：     文件格式 elf64-x86-64


Disassembly of section .text:

0000000000000000 <multstore>:
   0:	53                   	push   %rbx
   1:	48 89 d3             	mov    %rdx,%rbx
   4:	e8 00 00 00 00       	call   9 <multstore+0x9>
   9:	48 89 03             	mov    %rax,(%rbx)
   c:	5b                   	pop    %rbx
   d:	c3                   	ret

a.o：     文件格式 elf64-x86-64


Disassembly of section .text:

0000000000000000 <multstore>:
   0:	53                   	push   %rbx
   1:	48 89 d3             	mov    %rdx,%rbx
   4:	e8 00 00 00 00       	call   9 <multstore+0x9>
   9:	48 89 03             	mov    %rax,(%rbx)
   c:	5b                   	pop    %rbx
   d:	c3                   	ret

可以看出，机器码就是一串 bytes，若干个 bytes 合在一起表示一条指令。而每条指令对应的 bytes 数量不同，与 operands 个数以及指令的常用程度相关（类似摩斯电码、UTF-8）。

Data Formats

由于历史原因，Intel 使用 “word” 表示 16 bits，而用 “double word” 表示 32 bits，用 “quad word” 表示 64 bits。

C 语言类型在 x86-64 中的大小：

C 语言类型	Intel 数据类型	汇编后缀	bytes
`char`	byte	`b`	1
`short`	word	`w`	2
`int`	double word	`l` (long)	4
`long`	quad word	`q`	8
指针	quad word	`q`	8
`float`	single precision	`s` (short)	4
`double`	double precision	`l` (long)	8

每种类型都有一个用在汇编指令中的后缀，表示 operand 的类型，例如 movb、movw、movl、movq。l 既用于 double word 也用于 double precision，但整数和浮点数涉及的指令不同，所以不会有歧义。（后文中 Floating-Point Code 用的 AVX2 指令并不使用 s/l 的浮点数类型后缀。）

Accessing Information

寄存器

x86-64 CPU 有 16 个 general-purpose register，可以用来存整数或指针：

quad word	double word	word	byte	用途
`%rax`	`%eax`	`%ax`	`%al`	return value
`%rbx`	`%ebx`	`%bx`	`%bl`	callee saved
`%rcx`	`%ecx`	`%cx`	`%cl`	4th argument
`%rdx`	`%edx`	`%dx`	`%dl`	3rd argument
`%rsi`	`%esi`	`%si`	`%sil`	2nd argument
`%rdi`	`%edi`	`%di`	`%dil`	1st argument
`%rbp`	`%ebp`	`%bp`	`%bpl`	callee saved
`%rsp`	`%esp`	`%sp`	`%spl`	stack pointer
`%r8`	`%r8d`	`%r8w`	`%r8b`	5th argument
`%r9`	`%r9d`	`%r9w`	`%r9b`	6th argument
`%r10`	`%r10d`	`%r10w`	`%r10b`	caller saved
`%r11`	`%r11d`	`%r11w`	`%r11b`	caller saved
`%r12`	`%r12d`	`%r12w`	`%r12b`	callee saved
`%r13`	`%r13d`	`%r13w`	`%r13b`	callee saved
`%r14`	`%r14d`	`%r14w`	`%r14b`	callee saved
`%r15`	`%r15d`	`%r15w`	`%r15b`	callee saved

每个 register 可以用四种不同的长度访问，其中短的是长的的低位。修改 byte 或 word 的值时高位不变，修改 double word 的值则会将高位清零。

不同寄存器的用途将在后文说明（主要是在 Procedures 这一节）。

Operand 格式

指令的 operand 有三种指定方式：

Immediate，即字面值，代码为 $Imm，例如 $123 表示 123，$0x123 表示 0x123
Register，代码为寄存器的名称，例如 %rax
Memory，完整形态的代码为 Imm(rb, ri, s)，表示 M[Imm + R[rb] + R[ri] * s]（其中 ri 不为 %rsp， $s \in \{1, 2, 4, 8\}$ ），例如 2(%rax, %rbx, 4) 表示 memory 中地址为 2 + %rax + 4 * %rbx 的值；Imm、rb、, ri, s 分别可以省略，例如 Imm、(rb)、Imm(, ri, s)；指定了 ri 时也可以省略 s 表示 s 为 1。

在下文中，用 imm32、r64、m16、r/m64 等方式表示指令 operand 的类型。

（在 ATT 格式中）有两个 operand 时，第一个是 source，第二个是 destination。

move 类指令

虽然叫 “move”，但实际上是复制。

MOV 指令

source 和 destination 类型相同。

movb imm/r8, r/m8
movb m8, r8
movw imm/r16, r/m16
movw m16, r16
movl imm/r32, r/m32
movl m32, r32
movq imm32/r64, r/m64
movq m64, r64
movabsq imm64, r64

其中，source 和 destination 不能同时是 memory。

特别地，movq 不接受 imm64，复制时会在 imm32 的高位补符号位；movabsq 可以接受 imm64，但 destination 只能是寄存器。这样设计的原因可以参考 assembly - why we can't move a 64-bit immediate value to memory? - Stack Overflow。实际上，支持 imm64 作为 operand 的指令是少数，后面还会看到很多不接受 imm64 的指令，一般都是高位补符号位。

MOVZ 指令

将高位补零后复制。

movzbw r/m8, r16
movzbl r/m8, r32
movzwl r/m16, r32
movzbq r/m8, r64
movzwq r/m16, r64

没有 movzlq 这条指令，因为将寄存器的值修改为一个 double word 时就会将高位清零，所以使用 movl 就可以了。

MOVS 指令

将高位补符号位后复制。

movsbw r/m8, r16
movsbl r/m8, r32
movsbq r/m8, r64
movswl r/m16, r32
movswq r/m16, r64
movslq r/m32, r64
cltq: 和 movslq %eax, %rax 效果相同（但编码更短）

push/pop stack

pushq imm32/r/m64: 将 R[%rsp] 减八，然后将 operand 复制到 M[R[%rsp]]（PUSH 指令不支持 imm64，会将 imm32 高位补符号位）
popq r/m64: 将 M[R[%rsp]] 复制到 operand，然后将 R[%rsp] 加八

可以看出，program stack 是 memory 中连续的一段，每个元素是一个 quad word，top 的地址比 bottom 低，push 时 stack pointer 减小。

由于 stack 不过是由 %rsp 标记栈顶的一段 memory，可以通过给 %rsp 加上一个 offset 访问非栈顶元素，例如 8(%rsp) 为栈顶下面的第一个元素。

Arithmetic and Logical Operations

Load Effective Address

leaq m, r64: 将 source operand 的地址复制到 destination operand（只计算 source operand 的地址，与其指向的 memory 中存储的值无关）

LEA 可以用来优化一些简单的算术，例如：

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

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

scale:
	leaq	(%rdi,%rsi,4), %rax
	leaq	(%rdx,%rdx,2), %rdx
	leaq	(%rax,%rdx,4), %rax
	ret

scale:
	leaq	(%rdi,%rsi,4), %rax
	leaq	(%rdx,%rdx,2), %rdx
	leaq	(%rax,%rdx,4), %rax
	ret

这里三个 LEA 分别计算了 $x + 4y$ , $z + 2z$ 和 $(x + 4y) + 4 (z + 2z)$ 。

一元运算

每种一元运算都有 b/w/l/q 四个类型，接受一个相应类型的 r/m，将这个 operand 计算后的结果存入这个 operand：

INC: 加一
DEC: 减一
NEG: 取反 (negate)
NOT: 按位取反 (complement)

二元运算

每种二元运算都有 b/w/l/q 四个类型，接受相应类型的 imm/r/m 作为 source（除了 imm64），相应类型的 r/m 作为 destination（source 和 destination 不能同时为 memory），效果为将 source“作用于”destination，将运算结果存入 destination。

ADD: 加
SUB: destination 减去 source
IMUL: 乘
XOR: 按位异或
OR: 按位或
AND: 按位与

特别地，类似 xorl %rdx, %rdx 的代码可以用来优化 movl $0, %rdx，参见 Practice Problem 3.11 以及 performance - What is the best way to set a register to zero in x86 assembly: xor, mov or and? - Stack Overflow。

位移

位移有 b/w/l/q 四个类型，source 只能是 imm8 或者 %cl，destination 是相应类型的 r/m。

SAL/SHL: 左移
SAR: 算术右移
SHR: 逻辑右移

结果是 operand 两倍长度的运算

128 位的整数叫做 oct word，需要存在两个寄存器中，在指令中一般高位放在 R[%rdx] 低位放在 R[%rax]。

虽然截去高位时是否有符号对编码层面的乘法没有影响，不截去高位时就需要对 signed 和 unsigned 使用不同的指令了：

imulq r/m64: 计算 operand 和 R[%rax] 作为 signed integer 相乘而不截去高位的结果，存在 R[%rdx]:R[%rax] 中。（如果有两个 operand 就是上面的二元运算了。）
mulq r/m64: 计算 operand 和 R[%rax] 作为 unsigned integer 相乘而不截去高位的结果，存在 R[%rdx]:R[%rax] 中。

除法以及取模：

cqto/cqtd: 将 R[%rax] 高位填符号位放在 R[%rdx]:R[%rax]（也就是用 R[%rax] 的符号位填满 R[%rdx]）。
idivq: 计算 R[%rdx]:R[%rax] 有符号地除以 operand，商放在 R[%rax]，余数放在 R[%rdx]。
divq: 计算 R[%rdx]:R[%rax] 无符号地除以 operand，商放在 R[%rax]，余数放在 R[%rdx]。

得到的商都是向 0 取整，所以被除数为负时余数非正。

若商溢出了，则会触发 divide error 异常。所以被除数一般会是 64 位整数（在 idivq 之前用 cqto 来设置 R[%rdx]，在 divq 之前将 R[%rdx] 置为全零），否则很可能溢出而触发异常。

这些运算也有 operand 为 32 位，结果为 64 位的版本：imull、mull、cltd、idivl、divl。它们以 %edx 和 %eax 来代替 128 位运算中的 %rdx 和 %rax。

Control

Status Flags

status flags 中存储了最近一次运算的状态，常用的 status flag 有四个：

CF: Carry Flag，表示运算过程中发生了超出 operand 长度的进位或借位，即将运算视作 unsigned 发生了溢出。
ZF: Zero Flag，表示运算结果为零。
SF: Sign Flag，表示运算结果（看作补码）为负，即运算结果的符号位。
OF: Overflow Flag，表示若将运算视作 signed 发生了溢出。

Note: ARM 中的 carry flag —— carry flag vs borrow flag

在 ARM 中，计算减法时，与 x86 相反，carry flag 为 0 表示溢出，为 1 表示没有溢出。

这是因为，计算减法有两种方式，subtract with borrow 和 subtract with carry：

subtract with borrow 相当于普通的减法竖式计算，计算过程中记录 borrow flag，最后存储在 carry flag 中，表现为若最后发生借位则 carry flag 为 1。
subtract with carry 利用了 -x = ~x + 1 的性质，通过 a + ~b + 1 来计算 a - b，而和普通加法一样计算 carry flag；而在 subtract with borrow 最后发生借位时，subtract with carry 反而 carry flag 是 0。

可以这么理解这两者间的差异：设计算是 $w$ 位的，最后计算完成时，borrow flag 表示第 $w+1$ 位上是 $-1$ ，carry flag 表示第 $w+1$ 位上是 $1$ ，而 subtract with carry 相当于先加上了 $2^w$ 再进行减法，就会将第 $w+1$ 位从 $-1$ 变成 $0$ ，从 $0$ 变成 $1$ 。

LEA 不会改变 status flags。

一元运算和二元运算都会改变 status flags。特别地，INC 和 DEC 不会改变 CF。

位移对 status flags 的影响比较复杂（可以参考 Intel Manual），简单来说 CF 会被设为最后一个移出的位，只有位移位数为 1 时才会改变 OF。

Condition Codes

condition code 是 status flags 的组合，常用的有：

condition code	名称 (意义)	取值
`e`/`z`	equal / zero	`ZF`
`ne`/`nz`	not equal / not zero	`~ZF`
`s`	sign (negative)	`SF`
`ns`	not sign (non-negative)	`~SF`
`g`/`nle`	greater / not less equal (signed $>$ )	`~(SF ^ OF) & ~ZF`
`ge`/`nl`	greater equal / not less (signed $\ge$ )	`~(SF ^ OF)`
`l`/`nge`	less / not greater equal (signed $<$ )	`SF ^ OF`
`le`/`ng`	less equal / not greater (signed $\le$ )	`(SF ^ OF) \| ZF`
`a`/`nbe`	above / not below equal (unsigned $>$ )	`~CF & ~ZF`
`ae`/`nb`	above equal / not below (unsigned $\ge$ )	`~CF`
`b`/`nae`	below / not above equal (unsigned $<$ )	`CF`
`be`/`na`	below equal / not above (unsigned $\le$ )	`CF \| ZF`

这些 condition code 都是按照减法的结果来命名的，在使用 CMP 指令时这些名称是自然的，但如果不是 CMP/SUB 则要考虑进行的运算是什么以及每个 condition code 实际的取值。

l/nge 可以理解为，溢出后会变号，所以 SF ^ OF 就是如果不溢出的符号；b/nae 是因为减法发生借位时会标记 CF。

CMP 和 TEST 指令

如果真的进行运算，destination 的值会被覆盖，所以，如果计算结果是不需要的，一般会用 CMP 和 TEST 来获取 status flags。

CMP 和 TEST 的 operands 和二元运算相同。

CMP 相当于执行 SUB 但只更新 status flags 不更新 destination。常用于比较两个数的大小。

TEST 相当于执行 AND 但只更新 status flags 不更新 destination。常见的用法有两种，一种是两个 operand 为同一个寄存器以判断其符号，另一种是 source 为 bit mask。

SETcc 指令

SETcc r/m8: 将 cc 复制到 operand 处。其后缀不是 operand 的长度，而是 condition code，例如 sete r/m8、setne r/m8、sets r/m8...

Jump 类指令

Label

在汇编中 jump 通常会使用 label 作为 jump target，例如（CS:APP P205）：

    movq $0, %rax
    jmp  .L1
    movq (%rax), %rdx
.L1:
    popq %rdx

    movq $0, %rax
    jmp  .L1
    movq (%rax), %rdx
.L1:
    popq %rdx

这里的 .L1 就是一个 label。

无条件跳转

jmp Label: 跳转到 Label 处
jmp *r/m64: 跳转到 operand 存储的 jump target 处，例如 jmp *%rax、jmp *(%rax)。

条件跳转

Jcc Label: 如果满足 cc，则跳转到 Label 处。

rep; ret

如果 ret 会作为某个分支的第一条指令（即 jump 指令的下一条指令或 jump target），一般会把 ret 换成 rep; ret，效果和 ret 一样，但可以避免错误的分支预测，从而优化性能。具体可以参考 repz ret - repz ret。

jump 指令编码

在进行汇编时，label 会被替换为 jump 指令的下一条指令（其实就是 program counter 的值）到 jump target 的地址差。而在链接时，虽然指令的地址变了，但指令之间相对的地址差不变，则 jump 指令不用改变。

例如（CS:APP P207）：

    movq %rdi, %rax
    jmp .L2
.L3:
    sarq %rax
.L2:
    testq %rax, %rax
    jg .L3
    rep; ret

    movq %rdi, %rax
    jmp .L2
.L3:
    sarq %rax
.L2:
    testq %rax, %rax
    jg .L3
    rep; ret

汇编后：

   0:	48 89 f8             	mov    %rdi,%rax
   3:	eb 03                	jmp    0x8
   5:	48 d1 f8             	sar    %rax
   8:	48 85 c0             	test   %rax,%rax
   b:	7f f8                	jg     0x5
   d:	f3 c3                	repz ret

   0:	48 89 f8             	mov    %rdi,%rax
   3:	eb 03                	jmp    0x8
   5:	48 d1 f8             	sar    %rax
   8:	48 85 c0             	test   %rax,%rax
   b:	7f f8                	jg     0x5
   d:	f3 c3                	repz ret

这里 jmp .L2 的 operand 编码为 0x03，即其下一条指令的地址 0x5 到 jump target 0x8 的距离；jg .L3 的 operand 编码为 0xf8 即 -8，也就是其下一条指令的地址 0xd 到 jump target 0x5 的距离。

链接后：

000000000000112e <foo>:
    112e:       48 89 f8                mov    %rdi,%rax
    1131:       eb 03                   jmp    1136 <foo+0x8>
    1133:       48 d1 f8                sar    %rax
    1136:       48 85 c0                test   %rax,%rax
    1139:       7f f8                   jg     1133 <foo+0x5>
    113b:       f3 c3                   repz ret

000000000000112e <foo>:
    112e:       48 89 f8                mov    %rdi,%rax
    1131:       eb 03                   jmp    1136 <foo+0x8>
    1133:       48 d1 f8                sar    %rax
    1136:       48 85 c0                test   %rax,%rax
    1139:       7f f8                   jg     1133 <foo+0x5>
    113b:       f3 c3                   repz ret

CMOVcc 指令

CMOVcc 可以在满足 cc 时将 source 复制到 destination。这条指令在 ATT 格式中没有长度类型后缀，通过 destination register 的长度来推断类型。不接受 byte 作为 operand。

CMOVcc r/m16, r16
CMOVcc r/m32, r32
CMOVcc r/m64, r64

实现 if-else 语句

实现 if-else 语句主要有两种方式：

Conditional control: 即通过 jump 指令更改指令执行的顺序。
Conditional moves: 即通过 CMOVcc 等指令，根据条件决定是否执行这一条指令，但不改变指令执行的顺序。

（具体实现方式可以参考 CS:APP 中的例子。）

conditonal control 是通用的，但 conditonal moves 只在有限的情况下可以使用。一般来说，使用 conditional moves 时需要先将两个分支都算出来，然后根据条件来进行 move，所以要求分支中没有副作用。

conditional moves 有时可以用来优化性能，主要是因为现代处理器的 pipelining，即在物理上同时执行多条指令（但在效果上和按顺序执行一致）。条件跳转使得处理器不能确定未来要执行哪些指令，而只能进行分支预测，如果预测失败 pipelining 就白费了。而 conditional move 不会破坏指令执行的顺序，也就不影响 pipelining，所以可以起到优化的效果。但是，conditional moves 除了要求分支无副作用，还需要两个 branch 都执行，所以如果分支过大，就不如 conditional control。

实现循环语句

do while: 跑完一段代码后进行测试，通过则跳转到开头。

while: 在 do while 的基础上，要么在开头直接跳转到测试 (jump to middle)，要么在开头进行一次测试，不通过则跳到结尾 (guarded do)。

for: 在 while 的基础上，开头初始化，测试前更新。

实现 switch 语句

具体例子可以参考 CS:APP，重点在于，如果 cases 的值不过于稀疏，可以建一个叫做 jump table 的数组，以 cases 的值作为下标，label 作为值，这样就可以用一次数组访问而非多次条件跳转来实现 switch 语句。jump table 也可以和条件跳转结合，以处理 default case 或者个别 cases。

Procedures

procedure 的实现主要涉及三个方面：

在不同的 procedure 之间转移控制权，即调用 procedure 时交出控制权，procedure 返回时拿回控制权
传递参数和返回值
为局部变量分配/释放内存

调用 procedure 的核心是在 push/pop stack 一节中介绍过的 runtime stack。大体上来讲，stack 会分成一堆 frame，栈顶的 frame 为当前 procedure 的相关数据，从栈顶到栈底的各个 frame 依次放着调用链上的各个 procedure，在调用一个 procedure 时会将相关数据压入栈中，返回时再弹出。

这部分会采取“简介-原则-实现”的结构，先简单介绍大概是什么样的，再说明实现需要遵循的原则，再说明具体实现，以及实现是如何满足以及利用原则的。

转移控制权

调用 procedure 时，会将当前 program counter 的值存在 stack 中，然后将 program counter 修改为 callee，在返回时再从 stack 中取出 caller 的地址设为 program counter。

具体实现会使用 CALL 和 RET 两条指令：

call Label
call *(r/m64)
ret

其中 call 的 operand 和 jmp 是一样的，效果相当于先 pushq %rip 再 jmp。ret 则相当于把 popq 的结果作为 jmp 的 operand。

传递参数

寄存器中有 6 个用来存放 procedure 的 arguments，如果参数多于 6 个，则会放在 stack 中。

bits	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`

具体实现为：

在 caller 中、call 之前：将前 6 个参数放在相应的寄存器，并将其余参数按从后向前的顺序依次压入 stack
在 caller 中、call 之后：把 stack 中的参数（如果有）弹出 (addq $8(n-6), %rsp)
在 callee 中：从相应的寄存器或 stack 中读取参数

传递返回值

具体实现就是在 ret 前确保 %rax 中放的是返回值。

存储局部变量

局部变量一般会优先放在寄存器中，如果放不下就会放在 stack 中。

特别地，如果代码中涉及到取局部变量的地址，或者局部变量是结构化数据（例如数组或结构体），则必须放在 stack 中。

如果局部变量放在寄存器中，且在使用该局部变量的过程中调用了 procedure，那么该局部变量就会需要先存起来以保证调用 procedure 之后不会改变，而这有两种方式实现：

caller saved，即在 caller 中将寄存器里的值存在 stack 里。
callee saved，即在 callee 中存储：有一些特殊的寄存器是 callee-saved register，如果把局部变量存在这些寄存器中，在 caller 中就不用担心它们的值会在调用 procedure 后被修改。

caller saved 的具体实现：在 call 之前（以及压入超过 6 个的参数之前）将局部变量入栈，call 之后（以及弹出放在栈中的参数之后）再把栈中存的弹出到寄存器中。

callee saved 的具体实现：如果一个 procedure 使用了某个 callee-saved register，则要在 procedure 的开头将这个寄存器原本的值入栈，而在 procedure 的结尾将存下来的这个原本的值弹出到相应的寄存器中。

为了尽可能使用（数量尽量少的）寄存器而非 stack，经常会有多个生命周期不交叉的的变量共用一个寄存器，或者临时地把局部变量放在一般用于存放参数或返回值的寄存器中。

可变大小的 stack frame

通常情况下一个 procedure 的 stack frame 的大小是确定的，但有时 stack frame 的大小是不能在编译时确定的（例如有非确定大小的数组）。

stack frame 大小确定主要是为了能够通过与 %rsp 即栈顶的相对距离来访问局部变量等，在 stack frame 大小不确定时，则可以通过记录 stack frame 底部的地址来访问局部变量。

具体实现为：

function_name:
    pushq %rbp
    movq %rsp, %rbp
    ……
    leave
    ret

function_name:
    pushq %rbp
    movq %rsp, %rbp
    ……
    leave
    ret

设置好 %rbp 后，就可以使用 -8(%rbp) 等方式访问相对于 stack frame 底端的位置了。

这里有一个新指令 leave: 没有 operand，相当于 move %rbp, %rsp 然后 pop %rbp。

除了使用 %rbp 作为 frame pointer，为非确定大小的数组分配栈空间还涉及到 data alignment 的问题，可以参考 CS:APP Practice Problem 3.49。

Stack Frame Alignment

x86-64 中要求 stack frame 以 16 byte 对齐。具体来说，就是执行 call 之前 %rsp 的值必须是 16 的倍数，而在进入一个 procedure 时 %rsp 的值就模 16 余 8。

为了满足这一对齐要求，有时会在 call 之前先 subq $8, %rsp，call 之后再 addq $8, %rsp。

Array Allocation and Access

简单来说，Imm(rb, ri, s) 的 operand 格式使得数组访问变得容易。

而编译器会做很多优化，例如用指针加法代替每次都算一遍乘法。

Heterogeneous Data Structures

Struct

结构体也是内存中连续的一段，会在编译时在结构体地址的基础上加上相应的 offset 来访问各个 field。

Union

union 的大小是最大的 field 的大小，每个 field 的 offset 都是 0。

在使用 union 时，byte ordering 可能非常重要。

Data Alignment

在 x86-64 中，进行 data alignment 可以提升程序效率。具体要求为，任何（主要是结构体内的）primitive type 的地址需要是其长度的倍数。

为了满足 alignment 要求，可能需要：

在结构体的不同 field 之间添加 padding
保证结构体自身的地址是其自身 alignment 的倍数
在结构体末尾添加 padding，例如在数组中需要保证下一个元素的起始地址为其 alignment 的倍数

汇编代码中会使用 .align directive 来指定 data alignment。

Thwarting Buffer Overflow Attacks

了解了 stack 的构造，就能更加明白数组越界的危害：可以修改 stack 上包括 caller address 在内的数据，导致程序出错或跳转到错误的位置，而攻击者可以利用这一漏洞跳转到设计好的位置以执行攻击代码。

下面是一些无需修改程序代码就能做到的降低 buffer overflow 危害的方法，当然，这些方法也不是万能或总是有效的。

Stack Randomization

可以修改 stack 的起始地址，以降低指令地址的可预测性，增大攻击难度。这在 Linux 中已经是标准做法了，是 address-space layout randomization (ASLR) 的一部分。

攻击者可以通过 “nop sled”，即通过大量 nop 指令来增长攻击代码的长度，来降低猜测指令地址的难度。

Stack Corruption Detection

gcc 使用 stack protector 来检测 stack corruption，以避免 corrupted stack 造成的危害。

简单来说，使用 stack protector 时，会在 stack frame 中插入一个运行时随机生成的 canary value (guard value) ，并在 ret 前检查这个值是否被修改。

Limiting Executable Code Regions

可以限制能够被执行的 memory region，以避免攻击者执行位于 stack 中的、由攻击者注入的指令。

但是，有的语言（例如 Java）可能需要能够执行动态生成的指令，这样的话就不能禁止执行 stack 中的指令。

Floating-Point Code

这部分内容基于 AVX2 指令集，可以指定 -mavx2 选项来让编译器使用 AVX2 指令。

如果不支持 AVX，则可以使用 SSE 指令集，大体上是类似的。简单来说，主要的区别就是 AVX 指令的名称会有一个 v 的前缀，而很多 AVX 中三个 operand 的指令在 SSE 中是两个 operand。

YMM 寄存器

浮点数存放在 16 个 YMM registers 中，每个寄存器有 256 bits，叫做 %ymm0-15，而低位 128 bits 叫做 %xmm0-15。

这些寄存器可以存多个浮点数 (packed data) 并对它们同时进行操作以加速计算；而如果只对单个浮点数 (scalar) 进行操作，就只涉及到 %xmm0-15 的低位。

浮点数的移动指令

下面的指令都没有列全可能的 operand 类型，仅列出 CS:APP 里讲到的常用的。

vmovss m32, xmm
vmovss xmm, m32
vmovsd m64, xmm
vmovsd xmm, m64
vmovaps xmm, xmm
vmovapd xmm, xmm

其中 v 是 AVX 指令的前缀，ss 表示 scalar single-precision，sd 表示 scalar double-precision，a 表示 aligned，ps 表示 packed single-precision，pd 表示 packed double-precision。也就是说，s 结尾的用于 float，d 结尾的用于 double。

浮点数类型转换

浮点数转为整数

vcvttss2si xmm/m32, r32
vcvttsd2si xmm/m64, r32
vcvttss2siq xmm/m32, r64
vcvttsd2siq xmm/m64, r64

其中 cvttss2si 的意思是: cvt -> convert, t -> (with) truncation, ss -> scalar single-precision, 2 -> to, si -> signed integer。

ss 用于 float，sd 用于 double；结尾为 q 的用来转成 64 位整数。

整数转为浮点数

vcvtsi2ss r/m32, xmm, xmm
vcvtsi2sd r/m32, xmm, xmm
vcvtsi2ssq r/m64, xmm, xmm
vcvtsi2sdq r/m64, xmm, xmm

这里 cvt 后少了一个 t 是因为整数转为浮点数不会 truncate。

效果是把第一个 operand 转换后放在第三个 operand 处，而第二个 operand 一般不用管，设为和第三个 operand 一样即可。（转换结果会放在 destination 的低位，而第二个 operand 用来设置 destination 的高位。）

浮点数精度转换

vcvtss2sd xmm, xmm, xmm
vcvtsd2ss xmm, xmm, xmm

operand 的作用和上面整数转为浮点数的指令一样。

函数调用中的浮点数

前 7 个浮点参数可以存在 %xmm0-7 中，其余参数存在 stack 里。
浮点函数返回值存在 %xmm0 中。
没有 callee-saved 寄存器（所有寄存器都是 caller-saved）。

看参数是第几个、放在哪个寄存器时，浮点参数和整型参数是分开算的，例如 double f1(int x, double y, long z) 和 double f2(double y, int x, long z) 的参数寄存器分配是相同的。

浮点数算术运算

下面的指令把 ss 换成 sd、m32 换成 m64 即为 double-precision 的版本。

浮点数二元运算

记三个 operand 分别为 $S_1, S_2, D$ ，则效果为计算 $S_2$ 与 $S_1$ 的运算结果，存在 $D$ 中，例如 vsubss S_1 S_2 D 是 $D \gets S_2 - S_1$ 。

vaddss xmm/m32, xmm, xmm
vsubss xmm/m32, xmm, xmm
vmulss xmm/m32, xmm, xmm
vdivss xmm/m32, xmm, xmm
vmaxss xmm/m32, xmm, xmm
vminss xmm/m32, xmm, xmm

浮点数一元运算

sqrtss xmm/m32, xmm: 将 source 开方存入 destination

这里 CS:APP 中列出的是 SSE 指令 sqrtss 而非 AVX 指令 vsqrtss，我自己编译出来也是。可能可以参考 c++ - Using AVX intrinsics instead of SSE does not improve speed -- why? - Stack Overflow。

浮点数常量

浮点数相关的指令不接受 immediate value 作为 operand，所以使用常量时需要先存下来，例如：

double foo() { return 1.8; }

double foo() { return 1.8; }

foo:
	vmovsd	.LC0(%rip), %xmm0
	ret
.LC0:
	.long	-858993459
	.long	1073532108

foo:
	vmovsd	.LC0(%rip), %xmm0
	ret
.LC0:
	.long	-858993459
	.long	1073532108

浮点数位运算

位运算都是在整个寄存器上对 packed data 进行的。

vxorps xmm/m128, xmm, xmm
vxorpd xmm/m128, xmm, xmm
vandps xmm/m128, xmm, xmm
vandpd xmm/m128, xmm, xmm

operands 格式和上面一样。

一些浮点数位运算的实际运用：

用 and 运算将 sign bit 置零，以取绝对值
用 xor 运算将 sign bit 取反，以取相反数
将 xor 的两个 source 设为同一个寄存器以得到 0

浮点数比较

vucomiss xmm/m32, xmm
vucomisd xmm/m64, xmm

效果为，计算第二个 operand 减去第一个 operand 并设置 status flags。

浮点数的比较是 “unordered” 的，即若某个 operand 是 NaN，则比较结果为 unordered。

不同的比较结果对应的 status flags 以及 condition code 为：

比较结果	CF	ZF	PF	condition code
unordered	1	1	1	`p`
$S_2 < S_1$	1	0	0	`b`
$S_2 = S_1$	0	1	0	`e`
$S_2 > S_1$	0	0	0	`a`

其中 PF 在浮点数比较中用来表示 unordered，在整数计算中也会被设置但几乎没用。

Program Encodings

汇编/机器码中的程序状态

将 C 代码编译为汇编代码

C

Assembly

反汇编与机器码

Assembly

Data Formats

Accessing Information

寄存器

Operand 格式

move 类指令

MOV 指令

MOVZ 指令

MOVS 指令

push/pop stack

Arithmetic and Logical Operations

Load Effective Address

C

Assembly

一元运算

二元运算

位移

结果是 operand 两倍长度的运算

Control

Status Flags

Condition Codes

CMP 和 TEST 指令

SETcc 指令

Jump 类指令

Label

Assembly

无条件跳转

条件跳转

rep; ret

jump 指令编码

Assembly

Assembly

Assembly

CMOVcc 指令

实现 if-else 语句

实现循环语句

实现 switch 语句

Procedures

转移控制权

传递参数

传递返回值

存储局部变量

可变大小的 stack frame

Assembly

Stack Frame Alignment

Array Allocation and Access

Heterogeneous Data Structures

Struct

Union

Data Alignment

Thwarting Buffer Overflow Attacks

Stack Randomization

Stack Corruption Detection

Limiting Executable Code Regions

Floating-Point Code

YMM 寄存器

浮点数的移动指令

浮点数类型转换

浮点数转为整数

整数转为浮点数

浮点数精度转换

函数调用中的浮点数

浮点数算术运算

浮点数二元运算

浮点数一元运算

浮点数常量

C

Assembly

浮点数位运算

浮点数比较