Skip to content

Chapter 03 Machine Level Representation of Programs

3.1 历史观点

3.1.1 Intel 处理器系列 (x86)

  • 向后兼容性: 每一代处理器都能执行上一代处理器的机器代码.
  • 摩尔定律 (Moore's Law): 晶体管数量每 18 个月翻一番.

3.2 程序编码

3.2.1 机器级代码

  • 指令集体系结构 (ISA): 定义了处理器状态, 指令的格式, 以及每条指令对状态的影响.
  • 机器代码: 字节序列, 处理器执行的实际代码.
  • 汇编代码: 机器代码的文本表示.
  • 编译器 (gcc) 将 C 语言代码转换为汇编代码 (-S), 汇编器 (as) 将汇编代码转换为机器代码 (-c), 链接器 (ld) 将目标文件组合成可执行文件.

3.2.2 汇编代码格式

  • AT&T 格式 (gcc 默认): 源操作数在左, 目的操作数在右. 寄存器前加 %, 立即数前加 $.
  • Intel 格式: 源操作数在右, 目的操作数在左.

3.3 数据格式

3.3.1 字长后缀

  • b: byte (1 字节)
  • w: word (2 字节)
  • l: double word (4 字节)
  • q: quad word (8 字节)
  • 单精度浮点数: s
  • 双精度浮点数: l (注意与 4 字节整数后缀重名)

3.4 访问信息

3.4.1 操作数指示符

  • 立即数 (Immediate): $Imm. 如 $0x1F.
  • 寄存器 (Register): %rax. R[r_a].
  • 内存引用 (Memory Reference): Imm(r_b, r_i, s).
  • 有效地址: \(Imm + R[r_b] + R[r_i] \times s\).
  • s 必须是 1, 2, 4, 8.

3.4.2 数据传送指令

  • MOV S, D: \(D \leftarrow S\).
  • movb, movw, movl, movq.
  • 不影响条件码: mov 指令只会更新目的操作数，不会改变条件码寄存器。
  • 零扩展: movzbw (byte -> word), movzbl...
  • 符号扩展: movsbw (byte -> word), movsbl...
  • cltq: 把 %eax 符号扩展到 %rax.

movl 的特殊行为

movl 指令以寄存器作为目的时, 会把该寄存器的高 4 字节设置为 0. (x86-64 的规定: 任何为寄存器生成 32 位值的指令都会把该寄存器的高 32 位清零).

3.4.3 压入和弹出栈数据

  • 栈向下增长 (高地址 -> 低地址).
  • pushq S: R[%rsp] -= 8; M[R[%rsp]] = S.
  • popq D: D = M[R[%rsp]]; R[%rsp] += 8.
  • push 和 pop 指令不影响条件码。

3.5 算术和逻辑操作

3.5.1 加载有效地址

  • leaq S, D: \(D \leftarrow \&S\).
  • 用于计算地址, 不访问内存.
  • 也常用于执行简单的算术运算 (如 x + 2*y).
  • 不影响条件码: leaq 仅用于地址计算，不会改变条件码寄存器。这是它与 add 等指令的重要区别。

3.5.2 一元和二元操作

  • 一元: inc, dec, neg, not.
  • inc 和 dec 会设置 OF, SF, ZF, 但不会改变 CF (进位标志)。这是一个常见的坑。
  • 二元: add, sub, imul, xor, or, and.
  • xor, or, and: 这些逻辑操作会清除 CF 和 OF (置为 0)，并根据结果设置 SF, ZF 和 PF。
  • 移位: sal (算术左移), shl (逻辑左移), sar (算术右移), shr (逻辑右移).
  • 移位量由 %cl 寄存器或立即数指定.
  • 移位操作的标志位: CF 被设置为最后移出的位。OF 仅在移位量为 1 时定义（如果符号位改变则置 1）。

3.5.3 特殊的算术操作

  • 128 位乘法/除法: imulq, mulq, idivq, divq.
  • 结果存储在 %rdx:%rax 中.

3.6 控制

3.6.1 条件码

  • CF (Carry Flag): 进位标志. (无符号溢出)
  • ZF (Zero Flag): 零标志. (结果为 0)
  • SF (Sign Flag): 符号标志. (结果为负)
  • OF (Overflow Flag): 溢出标志. (有符号溢出)
  • cmp 指令: 类似于 sub, 但只设置条件码, 不保存结果.
  • test 指令: 类似于 and, 但只设置条件码, 不保存结果. 常用于 testq %rax, %rax 检查 %rax 是正数、负数还是零。

指令对条件码的影响总结

  • 不改变任何标志位: leaq, mov, push, pop.
  • 修改所有标志位: add, sub, neg (CF, ZF, SF, OF).
  • 逻辑运算 (xor, and, or): CF=0, OF=0. 更新 ZF, SF.
  • 自增/自减 (inc, dec): 更新 ZF, SF, OF. CF 保持不变.
  • 移位操作: CF = 最后移出的位.

3.6.2 访问条件码

  • set 指令: 根据条件码设置目的操作数 (低 8 位) 为 0 或 1.
  • sete (Equal / Zero)
  • sets (Negative)
  • setg (Greater, signed)
  • seta (Above, unsigned)

3.6.3 跳转指令

  • jmp: 无条件跳转.
  • jcc: 条件跳转 (如 je, jne, jg, jge, jl, jle, ja, jb).
  • 跳转目标可以是直接标号或间接地址 (*).

3.6.4 跳转指令的编码

  • PC 相对编码: 目标地址 = 下一条指令地址 + 偏移量.
  • 绝对地址编码.

3.6.5 翻译条件分支

  • if-else 语句通常翻译为条件跳转.
  • goto 语句.

3.6.6 循环

  • do-while: 至少执行一次.
  • while: 可能一次都不执行 (先跳转到测试条件, 或先测试条件再跳转).
  • for: 初始化 -> 测试 -> 循环体 -> 更新.

3.6.7 条件传送指令

  • cmovcc S, R: 如果条件 cc 成立, 则 \(R \leftarrow S\).
  • 避免了控制冒险 (Control Hazard), 更有利于流水线执行 (因为不需要分支预测).
  • 限制: 源和目的操作数必须都在寄存器或内存中 (通常是寄存器), 且计算源值不能有副作用.

3.6.8 switch 语句

  • 跳转表 (Jump Table): 一个数组, 存储了代码段的地址.
  • 通过索引直接跳转到对应的代码段, 效率高 (O(1)).
  • 适用于 case 值比较密集的情况.

3.7 过程

3.7.1 运行时栈

  • 栈帧 (Stack Frame): 每个过程调用在栈中分配的一块内存区域.
  • %rsp: 栈指针, 指向栈顶.
  • %rbp: 帧指针 (可选, 用于变长栈帧或调试).
  • 对齐要求: 在调用函数 (call) 之前，栈指针 %rsp 必须是 16 字节对齐的。

3.7.2 转移控制

  • call Label:
  • 将返回地址 (下一条指令地址) 压入栈.
  • 跳转到 Label.
  • ret:
  • 从栈中弹出返回地址.
  • 跳转到返回地址.

3.7.3 数据传送

  • 前 6 个整型参数通过寄存器传递: %rdi, %rsi, %rdx, %rcx, %r8, %r9.
  • 超过 6 个的参数通过栈传递 (逆序压栈, 第 7 个参数在栈顶).
  • 返回值放在 %rax 中.

3.7.4 栈上的局部存储

  • 局部变量通常保存在寄存器中.
  • 必须保存在内存中的情况:
  • 寄存器不够用.
  • 对局部变量使用了取地址符 &.
  • 局部变量是数组或结构.

3.7.5 寄存器中的局部存储空间

  • 被调用者保存 (Callee-saved): %rbx, %rbp, %r12-%r15.
  • 被调用函数必须在返回前恢复这些寄存器的值 (通常是先 push 保存, 返回前 pop 恢复).
  • 调用者保存 (Caller-saved): %r10, %r11, 以及参数寄存器.
  • 调用者负责保存这些寄存器 (如果后续还需要用到).

3.8 数组分配和访问

3.8.1 基本原则

  • T A[N]: 分配 \(L \times N\) 字节的连续空间.
  • A[i] 的地址: \(x_A + L \times i\).

3.8.2 指针运算

  • 指针加 1, 地址增加该指针指向类型的大小 \(L\).

3.8.3 嵌套数组

  • T A[R][C]: 行优先存储.
  • A[i][j] 的地址: \(x_A + L(C \times i + j)\).

3.8.4 定长和变长数组

  • 变长数组 (C99): 允许数组维度是表达式.
  • 编译器会生成计算数组大小和偏移量的代码 (乘法).

3.9 异质数据结构

3.9.1 结构 (Structure)

  • 成员在内存中连续存放.
  • 编译器维护每个成员的偏移量.

3.9.2 联合 (Union)

  • 所有成员共享同一块内存.
  • 大小等于最大成员的大小.
  • 用于节省空间或访问同一数据的不同位模式.

3.9.3 数据对齐

  • 原则: \(K\) 字节基本对象的地址必须是 \(K\) 的倍数. (通常 \(K=1, 2, 4, 8\)).
  • 目的: 提高内存访问效率 (硬件通常一次访问对齐的块).
  • 编译器会在结构体成员之间插入填充 (Padding) 以满足对齐要求.
  • 结构体总大小必须是其最大成员对齐要求的倍数 (末尾也可能填充).

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

3.10.1 理解指针

  • 指针是地址.
  • 指针有类型 (决定了如何解释该地址处的数据以及指针运算的步长).
  • 指针可以强制转换.

3.10.2 缓冲区溢出 (Buffer Overflow)

  • C 语言不进行数组边界检查.
  • 向栈上的局部数组写入超过其长度的数据, 可能覆盖返回地址, 导致程序跳转到攻击者指定的代码 (如 Shellcode).

3.10.3 对抗缓冲区溢出攻击

  1. 栈随机化 (Stack Randomization / ASLR): 每次运行程序时栈的位置都不同. 攻击者难以猜测栈地址.
  2. 栈破坏检测 (Stack Canary): 在缓冲区和返回地址之间插入一个特殊值 (Canary). 函数返回前检查 Canary 是否被修改.
  3. 限制可执行代码区域 (NX bit): 标记栈和堆为不可执行.

3.11 浮点代码

3.11.1 浮点传送和转换操作

  • %xmm0-%%xmm15: 128 位 XMM 寄存器 (也可以看作 256 位 YMM).
  • 浮点数参数通过 %xmm0-%%xmm7 传递.
  • 返回值放在 %xmm0 中.
  • 数据传送: movss (单精度), movsd (双精度), movaps (对齐的压缩单精度), movapd (对齐的压缩双精度).

3.11.2 过程中的浮点代码

  • XMM 寄存器都是调用者保存的 (Caller-saved).

3.11.3 浮点运算操作

  • addss, addsd, subss, ...
  • 标量运算 (Scalar, 结尾 ss/sd) 只对低位分量进行运算.
  • 向量运算 (Packed, 结尾 ps/pd) 对所有分量进行并行运算 (SIMD).

3.11.4 定义和使用浮点常数

  • 通常存储在只读数据段 (.rodata) 中, 通过内存引用访问.

3.11.5 C 语言中的浮点位级操作

  • 浮点比较指令 (ucomiss, ucomisd) 设置条件码.
  • 还要考虑 NaN 的情况 (Unordered).