CSAPP 03 - 汇编

  从汇编层次理解程序的运行过程。

基础

  对于机器级编程来说，有两种重要的抽象：

1. 指令集架构 (ISA)：ISA 用来定义机器级程序的行为和格式，它定义了处理器状态，指令格式，指令对状态的影响。多数 ISA 将程序行为描述为顺序执行每条指令。然而实际在硬件上，一些指令被并发的执行，但是通过采取措施保证整体行为和顺序执行一致。
2. 虚拟地址：机器级程序使用的内存地址是虚拟地址，虚拟地址提供了一个像是非常大的字节数组的内存模型。

  使用高级语言编程时，编译器将高级语言中的语句转换成处理器可以执行的基本指令，其中汇编代码的表示非常接近机器二进制代码，主要区别就是汇编代码使用了可读性更好的文本表示。

寄存器

  寄存器是存在于 CPU 内部的微型元器件，因为直接和 CPU 相连，CPU 访问寄存器的速度极快，同时一些寄存器的值也保存和反映着处理器的状态：

1. 程序计数器：称为 PC 寄存器，又用 %rip 表示。程序计数器保存着即将执行的下一条指令的地址。
2. 整数寄存器：包含 16 个命名的整数寄存器，可以存储 64 位数据如整数和地址，这 16 个寄存器又被称为通用寄存器，但是其中的一些寄存器有特殊含义，被用来记录特殊意义的值。
3. 条件码寄存器：保存最近执行算术和逻辑指令的状态信息。
4. 向量寄存器：向量寄存器可以存放一个和多个整数值或者是浮点数。

  x86_64 架构中的 16 个通用寄存器：

虚拟地址

  程序内存使用虚拟地址来寻址，在任意给定的时刻，只有有限的一部分虚拟地址被认为是合法的。

  x86_64 架构的虚拟地址是用一个 64 位的字来表示的，理论上它可以表示 2⁶⁴ - 1 个内存字节地址，但是在目前的实现中，虚拟地址的高 16 位必须设置为 0，所以一个 x86_64 的虚拟地址实际上能指定 2⁴⁸ (256 TB) 范围内的一个字节的地址。

  操作系统负责管理虚拟地址空间，将虚拟地址翻译成实际处理器内存中的物理地址。

工具

  可以使用工具来查看编译器编译过程中产生的汇编代码，如使用 GCC 的选项来保留编译过程中的中间信息：

gcc -E -o file.i file.c
gcc -Og -S -o file.s file.i
gcc -Og -c -o file.o file.s

  选项-Og表示尽可能的禁用编译器的优化，保留程序原有逻辑下对应的汇编代码。

  除了在编译时查看可执行文件对应的汇编代码，在没有源代码的情况下还可以使用反汇编器 objdump，将可执行文件的二进制机器码翻译为汇编代码：

objdump -d file.o
objdump -d file.o > file.s

汇编

  汇编语言有很多种：Intel style，AT&T style (GNU)，nasm style 等等，这里选择的是 AT&T 风格的汇编。

基本格式

  一个简单地 C 程序：

long mul(long a, long b)
{
    long ret = a * b;
    return ret;
}

  使用 GCC 查看其汇编代码：

    .file	"c3_1.c"
    .text
    .globl	mul
    .type	mul, @function
mul:
.LFB0:
    .cfi_startproc
    movq	%rdi, %rax
    imulq	%rsi, %rax
    ret
    .cfi_endproc
.LFE0:
    .size	mul, .-mul
    .ident	"GCC: (GNU) 13.1.1 20230614 (Red Hat 13.1.1-4)"
    .section	.note.GNU-stack,"",@progbits

  其中所有以 . 开头的指令都是伪指令，伪指令的作用是指导编译器和链接器的工作，通常可以忽略这些行。

数据格式

  C 语言将数据类型细分为 char，int 等分别用来表示整数，浮点数甚至结构体。但是在汇编中没有这些区分，基本单位是字节，类型都是一个或者多个字节的组合：

  浮点数有两种：单精度和双精度，对应 float 和 double，但是 x86 的历史上还支持过特殊的 80 位浮点数运算，C 语言中对应为 long double 类型。这种类型不建议被使用，一是不能移植到其他平台，二是实现的硬件也不如前两种浮点数运算高效。

数据传送

  大多数指令都有一个或者多个操作数，用于指示操作中要使用的源数据和放置结果的目的位置。

  操作数可以分为三种类型：

1. 立即数：用于表示常数值，使用$Imm的形式表示。
2. 寄存器：表示寄存器中存储的值，使用%rax的形式表示。
3. 内存引用：根据计算出来的地址来访问对应位置的值，有多种形式。

  有多种寻址模式，允许不同形式的内存引用：

  其中：Imm 称作偏移，r_b 是基址寄存器，r_i 是变址寄存器，s 是比例因子。比例因子 s 必须是 1，2，4，8，基址和变址寄存器都必须是 64 位寄存器。

指令

  数据传送指令用于将数据从一个位置复制到另一个位置，有三大类：

1. MOV 类

  对于 mov[b/w/l/q] 指令，请注意：

• 源操作数可以是三类，目的操作数必须是一个位置即寄存器或者内存地址。
• 两个操作数不能都指向内存位置 (x86_64)，将值从一个内存位置复制到另一个内存位置需要两条指令：

movb from, %register
mvob %register, to

• 寄存器大小必须和大小后缀b/w/l/q匹配。
• 当movl的目的操作数为寄存器时，其目的寄存器的高 32 位会被设置为 0。
• 如果movq的源操作数为立即数，那么立即数最多 32 位，然后做符号扩展到 64 位。
• 最后一个指令movabsq用于解决上面的情况，但是其目的操作数只能是寄存器。

2. MOVZ 类

  MOVZ 指令用于扩展数据，将源数据复制到目的地后，将剩余位做零扩展。

  没有从 dword 到 qword 的扩展，如果扩展的目的地是寄存器，那么使用movl就能完成。

3. MOVS 类

  MOVS 指令也用于扩展数据，但是其做的是符号扩展。

栈操作

  栈是一种数据结构，具有先进后出 (LIFO) 的性质，x86_64 中程序的栈存放在内存中某个位置，并且栈始终向下增长，最近一个入栈的元素是栈顶元素，并且栈顶元素的内存地址是栈内元素最低的。

  栈操作分为入栈和出栈，两个操作都只有一个操作数。

• 栈顶元素的地址由寄存器%rsp保存，其又叫栈指针。
• push 操作先移动栈指针，即修改%rsp的值，再向其指定位置写入数据。
• pop 操作正好相反，先读取栈顶元素的值，再增大%rsp的值。

算术操作

  以下整数操作中只有leaq没有变种，其他的指令都是指令族，包含一些列有关不同大小操作数的变种，如add指令就有四种：addb，addw，addl和addq，分别对应不同大小的操作数。

• 第二组整数操作指令都是一元操作，操作数既是源操作数又是目的操作数。
• 第三组整数操作指令都是二元操作，第二个操作数既是源操作数又是目的操作数：

subq %rax, %rbx

  其效果类似 C 语言中的*rbx -= *rax，可以理解为从 %rbx 中减去 %rax。

• 最后一组整数操作是移位操作，对于移位操作：

  第一个操作数是移位量，第二个操作数是要进行移位的数 (第二个操作数不能为立即数)。

  移位量可以是立即数，或者是单字节寄存器 %cl 中的值 (理论上可以达到 255)，但是在 x86_64 中，对 w 位长的数据进行移位时，移位量是由 %cl 中的低 m 位决定的，这里 2^m = w。

  左移的两个指令SAL和SHL效果相同，右移操作分为两种，SAR是算术右移，SHR是逻辑右移。

加载有效地址

  leaq指令作用是加载有效地址，类似 C 中的取址运算 &，其使用形式和movq相似，只不过leaq只会获取源操作数值的地址，然后将其保存在另一个寄存器中，而不会访问源操作数。注意：leaq的目的操作数必须是一个寄存器。

  利用leaq指令的特性，编译器发现了很多灵活的用法，根本就与有效地址的计算无关：

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

  编译器可能会这样处理，这只是利用了leaq计算地址的方法，但是操作数可能根本不是一个有效地址：

# long scale(long x, long y, long z)
# x in %rdi, y in %rsi, z in %rdx

scale:
    leaq    (%rdi,%rsi,4), %rax    # x + 4*y
    leaq    (%rdx,%rdx,2), %rdx    # z + 2*z = 3*z
    leaq    (%rax,%rdx,4), %rax    # (x+4*y) + 4*(3*z) = x + 4*y + 12*z
    ret

特殊算术操作

  下面是有关整数的乘法和除法操作指令：

  两个 64 位的无符号或者有符号相乘，可能需要 128 位来表示，x86_64 提供了八字 (oct word) 支持，八字使用两个寄存器组合表示 %rdx:%rax，其中 %rdx 存储高 4 字，%rax 存储低 4 字。

• 对于imulq和mulq指令：他们都将 %rax 的值当作第一个乘数，只需要提供第二个 64 位乘数，相乘的结果放在 %rdx:%rax 中。
• 对于idivq和divq指令：他们都将 %rdx:%rax 的值当作被除数，只需要提供 64 位除数，相处的得到的商放在 %rax 中，余数放在 %rdx 中。

  对于大多数 64 位除法来说，被除数也是一个 64 位值，而非 128 位，如果只设置了 %rax，此时 %rdx 也必须设置为 0 (无符号运算) 或者符号位 (有符号位)。使用cqto指令来完成该任务：

• 指令cqto没有操作数，其作用是将四字符号扩展到八字，即将 %rax 的最高有效位复制到 %rdx 中，这对于被除数是 64 位的有符号数除法很方便。

逻辑操作

  C 语言中的某些结构，如条件语句，循环语句，分支语句都要求有条件的执行，而非一定顺序执行。机器代码提供两种基本的低级机制来实现有条件的行为：测试数据值，然后根据测试结果改变控制流或者数据流。

条件码

  除了整数寄存器，CPU 还维护着一组单比特位的条件码寄存器，他们描述了最近算术或逻辑操作的属性，可以通过检测这些寄存器的值来执行条件分支指令：

1. 进位标志 CF：最近的操作使最高位产生进位，可以用来检测无符号数操作的溢出。
2. 零标志 ZF：最近操作的结果是 0。
3. 符号标志 SF：最近操作的结果是负数。
4. 溢出标志 OF：最近操作导致一个补码溢出，可能是正溢出也可能是负溢出。

  除了leaq指令，所有的整数操作都会设置以上条件码，此外，还有两类指令也用于设置条件码，并且不产生副作用：

• cmp指令根据两个操作数之间的差来设置条件值，除了不更新目的寄存器的值外，它的行为和sub一致。
• test指令除了不更新目的寄存器的值外，他的行为和and一致。

  条件码通常不会被直接读取，但是可以根据条件码的某些组合来将一个字节设置为 0 或者 1:

  set指令的目的操作数仅仅是单字节，要得到一个 32 位或 64 位的结果，则需要进行一些转换：

# int comp(long a, long b) { return a < b; }
comp:
    cmpq    %rsi, %rdi
    setl    %al
    movzbl  %al, %eax
    ret

  很多整数操作是在机器级上是不区分有符号还是无符号的，他们有相同的位级行为，只有一些特殊情况才需要区分如：整数的右移操作，除法和乘法指令。

跳转指令

  正常情况下，指令按照出现顺序一条一条的被执行，而跳转指令会导致执行切换到程序中的一个新位置。在汇编中，跳转的目的地通常用一个标号指明：

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

  .L1就是一个标号，在产生目标文件时，汇编器会确定所有带标号的指令的地址，并将跳转目标 (目的指令的地址) 编码为跳转指令的一部分。

  jmp是无条件跳转指令，它可以是直接跳转：跳转到标号指令位置，也可以是间接跳转：跳转目标是存储在寄存器或者内存中的值，此时使用语法*operand。

jmp    *%rax
jmp    *(%rax)

  除了jmp指令，其他跳转指令都是条件跳转指令，并且和set系列命名关联。

  跳转目标有两种主要的编码方式，这主要在反汇编中方便查看：

1. PC 相对编码：此时跳转目标被编码为目标指令地址 - PC 寄存器的值。
2. 绝对编码：用四个字节直接给出目标指令的地址。

  PC 寄存器即 %rip 的值是下一条将要被执行的指令，在这里，即是跳转指令的下一条指令的地址。

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

# disassembly
0:  48 89 f8    mov    %rdi,%rax
3:  eb 03       jmp    8 <loop+0x8>
5:  48 d1 f8    sar    %rax
8:  48 85 c0    test   %rax,%rax
b:  7f f8       jg     5 <loop+0x5>
d:  f3 c3       repz retq

  分析第 8 行的跳转指令，反汇编结果显示跳转目标被编码为 0xf8，根据 PC-relative 的计算方式，0xf8 = 0x05 - 0xd，并且后面还给出了 0xf8 对应的是地址为 0x05 位置的指令。

条件分支

  对于 C 语言中的条件语句，其最常见的实现方式是使用有条件和无条件跳转。并且，有些条件可以使用数据的条件转移而非控制的条件转移来实现。

if (test_expr)
    then_statement;
else
    else_statement;

  上面是 C 语言条件语句的通用形式模板，可以使用goto指令 (类似 jmp 无条件跳转) 来描述：

    t = test_expr;
    if (!t)
        goto false;
    then_statement;
    goto done;
false:
    else_statement;
done:

  实现条件操作的传统方式是使用控制的条件转移，条件满足就线性执行，条件不满足就走另一条路径，机制非常简单，但是在现代处理器上可能会非常低效。

  在一些特殊场景上，可以选用数据的条件转移来替代控制：

  上面的汇编结果使用一条条件传送指令，和条件跳转 (转移)类似，条件传送也是根据一些条件码的组合来进行某些操作，只不过它不改变控制流，而是有条件的执行数据复制操作：

  条件传送指令的源操作数和目的操作数可以是 16 位，32 位，64 位，但是不能为单字节。无条件指令如movb将操作数大小编码在指令中，而条件传送指令可以由汇编器通过目的寄存器来确定操作数长度，因此只用一条指令表示。

v = test_expr ? then_expr : else_expr;

  该三元运算通过条件传送可以抽象表示为：

v  = then_expr;
ve = else_expr;
t  = test_expr;
if (!t) v = ve;

  但是并不是所有类似的操作都可以或者适合使用条件传送来实现，一方面要考虑提前计算两个结果的复杂度，产生的代价是否低于可能失败的分支预测。另一方面，如果某个结果的计算有副作用，那么可能就不适合提前计算。

循环

  C 语言中有多种循环结构：do-while，while，for。汇编中没有直接对应的指令，但是可以用条件测试和跳转组合实现循环的效果。

1. do-while

  基本形式如下，不断地执行 body 内的语句，然后计算 test 表达式的值，如果是非 0 的话就进行下一次循环。可以发现，do-while 保证 body 最少被执行一次。

do
    body_statement;
while (test_expr);

  其对应的伪汇编代码如下：

loop:
    body_statement;
    t = test_expr;
    if (t)
        goto loop;

  一个简单的例子：

2. while

  基本形式如下，其和 do-while 循环的差异是 while 要先计算 test 表达式的值再决定是否要循环。

while (test_expr)
    body_statement;

  编译器翻译 while 循环有两种基本形式：

• jump to middle

    goto test;
loop:
    body_statement;
test:
    t = test_expr;
    if (t)
        goto loop;

• guarded-do

  首先测试条件是否不成立，如果不成立就直接跳过循环，然后将其翻译为 do-while 循环的形式。这种翻译方式可能在编译器开启优化时被启用。

t = test_expr;
if (!t)
    goto done;
loop:
    body_statement;
    t = test_expr;
    if (t)
        goto loop;
done:

3. for

  基本形式如下：

for (init_expr; test_expr; update_expr)
    body_statement;

  C 语言标准说明，这样的 for 循环的行为与使用 while 行为一样：

init_expr;
while (test_expr) {
    body_statement;
    update_expr;
}

开关

  switch 语句可以根据一个整数索引值进行多重分支。GCC 会根据开关情况数量来决定如何翻译开关语句，当情况数量较多并且值的范围跨度较小时，就会使用跳转表的结构来实现。

  跳转表是一个数组，其表项 i 是一个代码段的地址，这个代码段相当于情况为 i 时所要做的动作。使用跳转表的好处是，执行开关语句的时间与情况的数量无关。

• &&是 GCC 扩展语法，用于创建一个指向代码位置的指针。

• jt即跳转表，其索引 i 对应了 case，使用goto *jt[i]就能跳转到对应代码段。

• 经过特殊处理，索引值 n 和 cases 都减少了 100，这样他们可以放在一个长度为 7 的跳转表中。

  其对应的汇编代码如下：

switch_eg:
        subq    $100, %rsi
        cmpq    $6, %rsi
        ja      .L8
        jmp     *.L4(,%rsi,8)
.L4:
        .quad   .L7
        .quad   .L8
        .quad   .L6
        .quad   .L5
        .quad   .L3
        .quad   .L8
        .quad   .L3
.L7:
        leaq    (%rdi,%rdi,2), %rax
        leaq    (%rdi,%rax,4), %rdi
        jmp     .L2
.L6:
        addq    $10, %rdi
.L5:
        addq    $11, %rdi
.L2:
        movq    %rdi, (%rdx)
        ret
.L3:
        imulq   %rdi, %rdi
        jmp     .L2
.L8:
        movl    $0, %edi
        jmp     .L2

• 将 %rsi 和所有的 case 都减去 100，如果 %rsi 大于 6 则说明匹配到 default 了。
• 这里的jmp *.L4(,%rsi,8)是间接跳转，.L4是标签，充当基址，而%rsi * 8则是偏移量，对应 case。

过程

  过程是一种很重要的抽象，它提供了一种封装代码的方式：用一组指定的参数和一个可选的返回值来实现某种功能。设计良好的软件使用过程作为抽象机制，隐藏某个行为的具体实现，同时又提供简明的接口定义。不同的编程语言中，过程的形式多样：函数 (function)，子例程 (subroutine)，处理函数 (handler) 等。

  这里假设过程 P 调用过程 Q，Q 执行完毕后返回到 P，这些动作包含以下一个或多个机制：

1. 传递控制：进入过程 Q 的时候，PC 寄存器必须设置为 Q 代码的起始位置。在返回时，要将 PC 寄存器设置为执行 Q 后面那条指令的地址。
2. 传递数据：P 必须要能够向 Q 传递一个或者多个参数，Q 必须要能够向 P 返回一个返回值。
3. 分配和释放内存：开始时，Q 可能要为局部变量分配空间，返回前，Q 必须释放这些分配的空间。

运行时栈

  栈式内存管理是 C 语言以及大多数语言过程调用机制的核心，栈是一种 LIFO 的数据结构，在 x86_64 中，栈从高向低增长，栈指针 %rsp 始终指向栈顶元素 (存放栈顶元素的地址)。栈指针减小即在栈上分配空间，栈指针增大即释放栈上空间。

  当过程所需要的储存空间超出寄存器所能存放的大小时，就会在栈上分配空间，这个部分称为过程的栈帧：

  过程 P 调用 Q 时，如果传递的参数多于 6 个，那么就需要将超出的部分分配在自己的栈帧上，并且是从后到前入栈的。调用 Q 之前，还必须将返回地址压入自己的栈帧中。

  在过程 Q 中，如果它要使用某些特殊的寄存器，则需要将寄存器的值保存到自己的栈帧上，同时局部变量的储存空间也分配在自己的栈帧上，在返回前，Q 需要恢复刚刚使用的寄存器的值，并且移动栈指针清空栈帧。

控制转移

  过程 P 调用过程 Q 需要完成两个动作：

1. 调用 Q 之前：先将call指令后面一条指令地址 A 压入栈中作为返回地址。然后更新 PC 寄存器的值为过程 Q 的代码地址。
2. 从 Q 返回时：先移动 %rsp 清空栈帧，然后弹出返回地址 A，并将 A 设置为 PC 寄存器的值。

  call 指令可以直接调用也可以是间接调用，和 jmp 指令的间接跳转用法类似。

数据传送

  调用过程时，可能需要向过程传递参数，可以通过寄存器传递 6 个整型参数，超过 6 个参数的部分则需要分配在 caller 的栈帧上，并且是倒序入栈的。

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;
}

  其汇编结果：

# void proc(a1, a1p, a2, a2p, a3, a3p, a4, a4p)
# Arguments passed as follows:
# a1 in %rdi     (64 bits)
# a1p in %rsi    (64 bits)
# a2 in %edx     (32 bits)
# a2p in %rcx    (64 bits)
# a3 in %r8w     (16 bits)
# a3p in %r9     (64 bits)
# a4 at %rsp+8   ( 8 bits)
# a4p at %rsp+16 (64 bits)

1 proc:
2     movq    16(%rsp), %rax
3     addq    %rdi, (%rsi)
4     addl    %edx, (%rcx)
5     addw    %r8w, (%r9)
6     movl    8(%rsp), %edx
7     addb    %dl, (%rax)
8     ret

  caller 栈帧分布情况，所有的数据都向 8 的倍数对齐：

栈上局部储存

  对于一些特殊情况，局部数据必须存放在内存中如：

• 寄存器空间不足以存放本地数据。
• 获取一个局部变量的地址时 (&)。
• 某些局部变量是数组或者结构时。

  在栈上分配空间对应 %rsp 的减小，回收栈上空间对应 %rsp 的增大。

long call_proc()
{
    long x1 = 1; int x2 = 2;
    short x3 = 3; char x4 = 4;
    proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4);
    return (x1+x2)*(x3-x4);
}

  call_proc 的栈帧分布情况如下，包含了几个局部变量，以及调用 proc 时传递的两个参数：

寄存器空间

  寄存器是唯一被所有过程共享的资源，虽然在给定时刻只有一个过程在活动，但是必须确保当 caller 调用 callee 时，callee 不能覆盖 caller 稍后还要使用的寄存器值。

  为此 x86_64 制定了所有过程 (包括程序库) 都必须遵循的惯例：

• 被调用者保存：如果被调用者要使用寄存器 %rbx，%rbp 以及 %r12 ~ %r15，那么它必须保存这些寄存器的值，并且在返回之前，要恢复使用的寄存器的值。
• 调用者保存：除了 %rsp 和上面的寄存器外，调用者在调用前可以保存一些寄存器的值，那么被调用者就可以随意使用这些被保存过的寄存器了，调用返回后，调用者负责恢复寄存器的值。

  具体的汇编实现即：通过 push 操作入栈寄存器的值，在即将合适的时机 pop 出栈寄存器的值。

数组

  C 语言的数组是一种将标量数据聚集成更大数据类型的方式。

  对于数据类型 T 和整型常数 N，数组的声明方式为T A[N]：

• 它在内存中分配一个 L * N 字节的连续区域，L 为数据类型 T 的大小。
• 这里的标识符 A 可以用来作为指向数组开头元素的指针，设其值为 x_A。
• 数组元素 i 会被存放在地址为 x_A + L * i 的地方。

  假设 E 是一个 int 类型的数组，计算 E[i] 的方式，即计算 x_E + 4i：

# address of E in %rdx, i in %rcx
movl (%rdx,%rcx,4), %eax

指针运算

  C 语言允许对指针进行运算，计算出来的值会根据指针引用数据类型的大小进行伸缩。如果 p 是一个指向 T 类型数据的指针，p 的值为 x_p 数据 T 类型的大小为 L，那么 p + i 的值就为 x_p + L * i。

  假设整型数组 E 的地址和索引 i 分别存放在 %rdx 和 %rcx 中，并且 %eax 存放整型值，%rax 存放地址：

多维数组

  C 语言支持创建元素类型为数组的数组，即创建多维数组：

int A[5][3];
typedef int row3_t[3];
row3_t A[5];

  其在内存中布局为：

  对于一个二维数组T A[R][C]来说，其元素A[i][j]的地址计算方式为 x_A + L(i * C + j)。

其他信息

  C99 标准之前，数组的长度只能是常量或者常量表达式，因此数组只能是定长数组。C99 标准开始，数组可以声明为变长数组，关于这两种数组，只需注意：

• 编译器对定长数组元素的访问 (包括多维) 有很好的优化。
• 对于变长的多维数组，编译器可能无法很好的优化对元素的访问，此时，编译器可能通过乘法指令而非leaq指令计算元素地址，因为乘法指令相比leaq指令性能会下降很多。

异质结构

  C 语言中提供两种将不同类型的对象组合到一起创建数据结构类型的机制：结构 (struct) 和联合 (union)。

结构

  结构将可能不同类型的对象聚合到一个对象中。用名字来引用结构中的各个组成部分。结构的实现类似数组，结构的所有组成部分都放在内存中一段连续的区域内。指向结构的指针就是结构第一个字节的地址，编译器维护关于每个结构的类型信息，指示每个字段的字节偏移。以这些偏移和结构的地址组合来引用结构的元素。

  一个简单的结构声明如下：

struct rec {
    int i;
    int j;
    int a[2];
    int* p;
};

  它包含四个字段，两个 4 字节 int，一个长度为 2 的 int 数组，一个 int 类型的指针，总共是 24 字节：

  要计算该结构对象元素的内存地址，只需要给结构对象的地址加上适当偏移量，例如&(r->a[i])：

# registers: r in %rdi, i in %rsi
leaq 8(%rdi,%rsi,4), %rax

  可以看到，结构的各个字段的选取完全是在编译期处理的，机器代码不包含任何关于字段声明或者字段名字的信息。

联合

  联合提供了一种规避 C 语言类型系统的方式，允许以多种类型来引用一个对象，联合的声明语法和结构一样。

struct S3 {
    char c;
    int i[2];
    double v;
};

union U3 {
    char c;
    int i[2];
    double v;
}

  在 x86_64 机器上，二者字段的偏移，分布，类型大小如下：

  可以观察到：联合类型的大小等于其最大字段的大小。对于一个 U3 对象指针 p，表达式 p->c，p->i[0]，p->v 引用的都是联合对象的起始位置即第一个字节。

  对于联合，有两种惯用技巧：

• tagged union

  这是由于联合在运行期将丢失类型信息，编译器无法在编译期间确定一个联合对象当前的活跃类型，因此可以将一个 tag 和 union 绑定在一起，用 tag 来指示当前活跃类型。

typedef enum {TU_INT, TU_DOUBLE} tu_t;

struct tu {
    tu_t type;
    union {
        int i;
        double d;
    } info;
};

• 访问不同数据类型的位模式

  由于 union 所有字段的偏移都是 0，那么对所有自段的引用都是从相同位置开始的，由此产生这个技巧，但是请注意，下面的例子有端序问题。

double u2d(unsigned u0, unsigned u1)
{
    union {
        double d;
        unsigned u[2];
    } temp;
    
    temp.u[0] = u0;
    temp.u[1] = u1;
    
    return temp.d;
}

数据对齐

  许多计算机系统对基本数据类型的合法地址作出了一些限制，要求某种类型对象的地址必须是某个值 K (通常是 2，4，8) 的整数倍。这种对齐限制简化了处理器和内存系统之间接口的硬件设计。

  例如，假设一个处理器总是从内存中取 8 字节，则每个地址必须是 8 的整数倍。如果能保证所有 double 对象的地址都被对齐为 8 的整数倍，那么用一个内存操作就可以访问到该数据对象。否则可能需要执行两次 (或更多) 内存访问，因为对象可能被分开放在两个 8 字节内存块中。

  注意：无论数据是否对齐 x86_64 硬件都能正常工作，不过 Intel 还是建议将数据对齐来保证内存系统的性能。

K	Type
1	char
2	short
4	int, float
8	long, double, char*

  分析前面 tu 类型的数据对齐情况：

0: tu_t type  (4 bytes)
4: empty
8: union info (8 bytes)

  如果出现结构体嵌套，那么外层结构体的最大对齐规则还是取自最大的基本数据类型。但是同时还必须要保证嵌套结构体的内存分布不变：

struct a { /* sizeof: 16 */
    double f;
    int i;
    /* padding: 4 */
};

struct b { /* sizeof: 24, not 32 */
    struct a s;
    
    /* s expands like */
    double s.f;
    int s.i;
    /* padding: 4 */
    
    int i;
};

变长栈帧

  对于大部分函数，编译器能够预先确定为所需要的栈帧分配多少空间，但是有些函数，需要的局部存储是变长的，例如当函数调用alloca分配栈空间时，以及代码声明变长数组时。

long vframe(long n, long idx, long* q)
{
    long i;
    long *p[n];
    p[0] = &i;
    for (i = 0L; i < n; ++i)
        p[i] = q;
    return *p[idx];
}

  观察 vframe 的栈帧分布：

  为了管理变长栈帧，x86_64 使用寄存器 %rbp 作为帧指针，也叫基指针：

• 由于 %rbp 是 caller-save 的，vframe 必须先保存 %rbp 的值。
• 然后将 %rsp 的值传给 %rbp，此时 %rbp 相当于栈底，是一个位置锚点。
• 移动 %rsp 分配栈空间。

  在 vframe 返回时，必须要清空栈。此时可以直接将 %rbp 的值传给 %rsp，并且恢复 %rbp 寄存器，但是还有一个简单的指令leave，可以一步完成这两个操作：

leave
ret
# equal to
movq    %rbp, %rsp
pop     %rbp

  在较早的 x86 版本中，每个函数都使用了帧指针。而现在，只在帧可变长的情况下才使用。

结合

  C 对于数组的引用不进行任何边界检查，而且局部变量和状态信息都存放在栈中。这两种情况结合到一起就能导致严重的程序错误，当程序使用这个被破坏的状态，试图重新加载寄存器或执行 ret 指令时，就会出现严重错误。

  C 标准库中的 gets 函数就有这个问题：

void echo()
{
    char buf[8];
    gets(&buf);
    puts(&buf);
}

  GCC 的编译结果如下：

# void echo
echo:
    subq    $24, %rsp
    movq    %rsp, %rdi
    call    gets
    movq    %rsp, %rdi
    call    puts
    addq    $24, %rsp
    ret

  观察 caller 和 echo 的栈帧情况可以发现：

1. 如果输入的字符串长度在 0 ~ 7 (预留一个字节给 NUL)，这是安全的。
2. 如果输入的字符串长度在 8 ~ 23，即使超过了分配的 8 字节，但是由于 GCC 的行为，这还是安全的。
3. 但是，如果输入字符串长度超过了 23，此时返回地址就会被破坏，ret 指令将导致程序跳转到一个意想不到的位置。

  一个最坏的结果就是：破坏者利用上面的行为，有意的将可执行代码地址编码到字符串中，替换了返回地址。这种代码称为攻击代码，ret 指令将导致程序跳转到攻击代码中。

  缓冲区溢出攻击给计算机系统造成很多麻烦，现代编译器和操作系统实现了很多机制，以避免遭受这样的攻击。

栈随机化

  攻击者要通过字符串将攻击代码指针插入栈中，则必须确定字符串在栈中的位置，过去，程序的栈地址非常容易预测，即使在不同机器之间，栈的位置也是相对固定的。

  栈随机化的思想使得栈的位置在程序每次运行时都有变化，因此许多机器运行同样地代码，他们之间的栈地址都是不同的。实现方式是：使用分配函数alloca在栈上分配指定字节数量的空间，程序不使用这段空间，但是他会导致程序每次执行时后续的栈位置发生了变化。

int main()
{
    long local;
    printf("local at %p\n", &local);
}

  使用上面的测试代码发现，栈地址在不停的变化。

  Linux 上，栈的随机化已经变成了标准行为，栈随机化是 ASLR 技术中的一种，后者全称虚拟地址空间布局随机化，使用 ASLR 技术，可以让程序代码，库代码，栈，全局变量和堆数据都被加载到内存不同的区域。

栈破坏性检测

  计算机第二道防线是能够检测到何时栈已经被破坏，栈被破坏通常发生在写操作超越了局部缓冲区。

  GCC 在产生代码时加入了一种栈保护者机制，其思想是：在栈帧任何局部缓冲区与栈状态之间储存一个特殊的金丝雀值，也被称为哨兵值，这个值是程序每次运行时随机产生的，攻击者无法简单的知道。在恢复寄存器或返回之前，程序会检测这个值是否被某个操作改变，如果是的，那么程序异常终止。

echo:
    subq    $24, %rsp
    movq    %fs:40, %rax     # read guard value
    movq    %rax, 8(%rsp)    # sava gaurd value
    xorl    %eax, %eax       # clear register
    movq    %rsp, %rdi
    call    gets
    movq    %rsp, %rdi
    call    puts
    movq    8(%rsp), %rax
    xorq    %fs:40, %rax     # compare guard value
    je      .L9
    call    __stack_chk_fail
.L9:
    addq    $24, %rsp
    ret

  这段代码只带来很小的性能损失，并且 GCC 只会在函数中有局部 char 类型缓冲区的时候才插入这样的代码。

限制可执行代码

  最后一招是消除攻击者向系统中插入可执行代码的能力。

  在过去的 x86 体系中，任何可读的内存页也都是可执行的，栈必须是可读可写的，因此栈上的字节也都是可执行的。已经实现的很多机制能够限制一些页可读写但是不可执行，然而这些机制通常会带来严重的性能损失。

  最近的 AMD 为它的 64 位处理器的内存引入了 NX (No-Execute) 位，将读和执行模式分开，Intel 也跟进了。有了这个特性，栈可以被标志为可读写，但是不可执行，这些检查是由硬件完成的，效率上没有损失。

TODO 浮点代码

  待更新。