CSAPP - 03.Machine-Level Programming III

机器级编程 III: 过程 (Procedures)

主要内容：
本章关注计算机如何实现逻辑控制。包括：

1. 条件码 (Condition Codes)：CPU 如何通过 ZF, SF 等标志位记住上一次计算的结果。
2. 跳转指令 (Jumps)：汇编中没有 if 和 while，只有 goto (即 jmp/je)。
3. 翻译控制结构：详细讲解了 C 语言中的 if-else、while、for 和 switch 是如何被“降维打击”成汇编中的条件跳转和跳转表的。

Motivation：
高级语言有优雅的结构（如循环、分支），但底层硬件非常“笨”，只会按顺序执行或跳转。理解这一章，你就能明白编译器是如何“欺骗”硬件来模拟复杂逻辑的，也能理解为什么某些写法（如 switch 跳转表）会比其他写法更快。

3.1 过程 (Procedures) 的机制

一个过程（或函数）的调用需要一套完整的机制来支持：

1. 传递控制 (Passing Control):
   • 在调用时，程序必须能跳转到过程的起始地址。
   • 在过程返回时，程序必须能跳转回调用指令的下一条指令。
2. 传递数据 (Passing Data):
   • 必须能够将参数 (Arguments) 传递给过程。
   • 过程必须能够返回一个返回值 (Return Value)。
3. 内存管理 (Memory Management):
   • 过程在执行期间需要能够分配 (Allocate) 内存来存储局部变量。
   • 在过程返回时，必须释放 (Deallocate) 这部分内存。

这些机制都是通过机器指令集和一套固定的策略来实现的。这些策略和选择共同构成了 应用二进制接口 (Application Binary Interface, ABI)。

3.2 x86-64 栈 (Stack) 结构

栈 (Stack) 是实现过程机制的核心数据结构。

• 栈区域: 内存中一块特殊的区域，遵循 栈 (Stack) 规则（后进先出, LIFO）来管理。
• 增长方向: 在 x86-64 架构中，栈从高地址向低地址增长，每次有压栈操作时候%rsp减8。（在64位计算机上，存储地址使用的是64 bits即8 bytes的大小）
• 栈指针 (Stack Pointer, %rsp):
  • %rsp 是一个特殊的寄存器栈指针寄存器，它始终指向栈顶 (Stack Top)。
  • “栈顶”指的是当前栈上最低的内存地址（即最后压入的数据所在的位置）。

栈操作 (Stack Operations)

• pushq Src (压栈):
  1. 从 Src 获取操作数。
  2. 将 %rsp 减 8 (因为栈向低地址增长)。
  3. 将操作数写入到 %rsp 指向的新地址。
• popq Dest (出栈):
  1. 从 %rsp 指向的地址读取值。
  2. 将 %rsp 加 8。
  3. 将读取的值写入到 Dest (通常是一个寄存器)。

3.3 调用约定 (Calling Conventions)

调用约定 (Calling Conventions) 是一套必须遵守的规则，它详细规定了过程调用如何实现。

1. 传递控制 (Passing Control)

控制流的传递依赖于 栈 (Stack) 和两条关键指令：

• call label label为地址 (过程调用):
  1. 将返回地址 (Return Address) 压入栈中。（返回地址是 call 指令之后的那条指令的地址）。
  2. 无条件跳转 (Jump) 到 label 处。
• ret (过程返回):
  1. 从栈顶弹出一个地址（这个地址就是之前 call 压入的返回地址）。
  2. 无条件跳转到这个弹出的地址。

这个例子逐步展示了在一次函数调用中，call 和 ret 指令如何利用栈 (Stack) 来精确地转移程序控制权。

这其中涉及两个关键寄存器：

• %rsp (栈指针): 始终指向栈顶。
• %rip (程序计数器): 始终指向下一条要执行的指令。

场景: 程序即将从 multstore 函数内部调用 mult2 函数。

call 0x400550 <mult2> 指令执行时，会发生两件核心事情：

1. 压入返回地址：
   • call 指令会查找它后面紧跟着的那条指令的地址 (在这个例子中是 0x400549)。
   • 它将这个 “返回地址” 压入 (push) 栈顶。
   • 因此，栈指针 %rsp 的值会减少 8 字节 (例如，从 0x120 变为 0x118)，指向这个新压入的返回地址。
2. 跳转：
   • 程序计数器 %rip 的值被更新为 call 指令的目标地址，即 mult2 函数的起始地址 0x400550。

结果: 程序控制权跳转到了 mult2 函数，并且栈上保存了"返回票根"（即返回地址），以便稍后能正确返回。

场景: mult2 函数已经执行完毕，即将执行其最后一条 ret (返回) 指令。

此时的状态：

• 程序计数器 %rip 指向 ret 指令本身的地址 (0x400557)。
• 栈指针 %rsp 仍然是 0x118，栈顶仍然保存之前存入的返回地址 0x400549。

场景: ret 指令被执行。

ret 指令会执行与 call 相反的操作：

1. 弹出返回地址:
   • ret 指令从栈顶弹出 (pop) 一个值。在这个例子中，它弹出了 0x400549。
   • 因此，栈指针 %rsp 的值会增加 8 字节 (例如，从 0x118 恢复为 0x120)，栈被"清理"干净。
2. 跳转:
   • 程序计数器 %rip 的值被更新为刚刚从栈中弹出的那个地址，即 0x400549。

结果: 程序控制权无缝地返回到了 multstore 函数中，并从 call 指令的下一行 (0x400549 处) 继续执行。

2. 传递数据 (Passing Data)

• 传递参数 (Arguments):
  • 前 6 个 整数或指针参数按顺序使用寄存器传递：
    1. %rdi
    2. %rsi
    3. %rdx
    4. %rcx
    5. %r8
    6. %r9
  • 第 7 个及以后的参数通过 栈 (Stack) 传递。
• 返回数据 (Return Value):
  • 返回值（如果是整数或指针）总是通过 %rax 寄存器返回。

3. 管理本地数据 (Managing Local Data)

支持递归 (Recursion) 的语言（如C, Java）要求过程的代码是可重入的 (Reentrant)。这意味着一个过程可以调用它自己，而不会破坏上一次调用的状态。

这是通过为每一次过程调用（每一个实例）分配一个私有的内存区域来实现的，而不是为每一个函数分配一个内存空间，这个区域称为栈帧 (Stack Frame)。

一个“栈帧”就是当一个函数（过程）被调用时，在栈上为它分配的一块专属内存区域，用来存放它运行所需的所有本地信息。

这张图解从上到下（从高内存地址到低内存地址）展示了栈的结构，分为两个部分：“Caller Frame” (调用者栈帧) 和 “Current Stack Frame” (当前栈帧)。

下面是 “当前栈帧” 各部分的详细讲解（按压栈顺序，从高地址到低地址）：

高地址 (High Address)
        |
+------------------------------+
| ...                          |
| A 的局部变量                 |
+------------------------------+ <--- A 的栈帧结束
| 参数 8 (为 B 准备)           |  \
| 参数 7 (为 B 准备)           |   }  B 的“输入” (Arguments 7+ for B)
+------------------------------+  /
| 返回地址 (Return Address)    |
+<mark>=</mark><mark>=</mark><mark>=</mark><mark>=</mark><mark>=</mark><mark>=</mark>+ <--- 分界线：B 的栈帧开始 (B's Frame)
| 保存的寄存器 (Saved Regs)    |
| B 的局部变量 (Local Vars)    |
| ...                         |
+------------------------------+
| 参数 7 (为 C 准备)           |  \
| 参数 8 (为 C 准备)           |   }  B 的“输出” (Argument Build Area)
+------------------------------+  /
        |
      低地址 (Low Address)    <--- %rsp (栈顶指针)

1. Arguments 7+ (第7个及以上的参数)
   • 这是由调用者 (Caller) 放入的。
   • 根据调用约定，前6个参数通过寄存器传递，而第7个、第8个等后续参数则在调用 call 指令之前被压入栈中，存放在这里。
2. Return Addr (返回地址)
   • 这是由 call 指令自动压入栈中的。
   • 它保存了 call 指令的下一条指令的地址。当当前函数执行 ret 指令时，CPU会从这里弹出地址，并跳转回去，从而实现函数返回。
3. Old %rbp (旧的 %rbp, 可选)
   • 这是当前栈帧的开始。
   • 如果当前函数需要使用 %rbp 作为帧指针（基址指针），它执行的第一件事就是 pushq %rbp，将调用者的 %rbp 值保存在这里。
4. Saved Registers + Local Variables (保存的寄存器 + 局部变量)
   • 这是栈帧的主体部分。
   • Saved Registers: 如果当前函数需要使用任何“被调用者保存 (Callee-Saved)”的寄存器（如 %rbx, %r12-%r15），它必须在修改它们之前，先把它们的原始值保存在这里。
   • Local Variables: 当函数的局部变量太多，寄存器不够用时，或者当有数组、结构体等大型局部变量时，它们会被存放在这里。
5. Argument Build (参数构造区, 可选)
   • 这是当前栈帧的最顶部（即最低的内存地址）。
   • 如果当前函数自己需要调用另一个函数，它就会在这里准备传递给那个新函数的参数。
   • 例如，如果它要调用的函数需要8个参数，它会把第7个和第8个参数放在这里，然后再执行 call。

• %rsp (栈指针)
  • 始终指向栈顶（即栈上已使用内存的最低地址）。在图中，它指向 “Argument Build” 区域的底部。
  • 它会随着 pushq (减小) 和 popq (增大) 或 subq / addq 指令而动态变化。
• %rbp (帧指针, 可选)
  • 如果使用，它会在函数开始时被设置为指向一个固定位置（即 “Old %rbp” 的存放位置）。
  • 它的好处是：即使 %rsp 因为构造参数等操作而移动，%rbp 仍然保持不变，使得编译器可以用固定的偏移量（如 -8(%rbp) 访问局部变量, +16(%rbp) 访问参数）来访问栈帧中的数据。
  • %rbp 寄存器随后会更新，指向这个位置，为访问局部变量和参数提供一个固定的基准点。
  • 逻辑上，利用保存的 Old %rbp 构建了一个“链表”，让我们能回溯函数的调用历史。当前函数的 %rbp指向当前栈帧的基准点（就是存放 Old %rbp 的那个地址）。这个地址里存的值（即 Old %rbp 的内容）是指向上一个栈帧基准点的指针。

在现代 x86-64 架构中，%rbp 不再强制作为栈帧基准，主要出于以下优化考虑：

1. 现代编译器的静态分析能力 (通过 %rsp 寻址)

• 旧机制：过去因为 %rsp 会随压栈/出栈频繁变动，必须用 %rbp 作为一个固定锚点来定位局部变量（如 -8(%rbp)）。
• 新机制：现代编译器非常智能，能够在编译时静态计算出任意时刻 %rsp 相对于局部变量的偏移量。因此，直接使用 %rsp 寻址（如 8(%rsp)）即可，不再需要固定的 %rbp。

2. 节省宝贵的寄存器资源

• x86-64 只有 16 个通用寄存器。如果不强制 %rbp 做帧指针，它可以被当作第 17 个通用寄存器使用，用于存储普通变量，从而提升性能。
• 这种优化通常通过编译器选项 -fomit-frame-pointer 开启。

3. 必须使用 %rbp 的特殊情况
虽然通常是可选的，但在以下场景中仍必须或建议使用：

• 变长数组 (VLA) / alloca()：当栈帧大小在编译期无法确定（动态变化）时，编译器无法计算相对于 %rsp 的固定偏移量，必须依赖 %rbp 记录栈帧起始位置。只有C99标准支持，标准C++不支持
• 调试与回溯：保留 %rbp 链表结构能让调试器（如 GDB）更轻松、直观地解析函数调用栈（Backtrace）。

4. 寄存器保存约定 (Register Saving Conventions)

问题: 当一个过程（Caller, 调用者）调用另一个过程（Callee, 被调用者）时，Callee 可能会修改 Caller 稍后还需要使用的寄存器。

解决方案: x86-64 规定了一套寄存器保存约定：

• 调用者保存 (Caller-Saved):

  • 寄存器: %rax, %rdi, %rsi, %rdx, %rcx, %r8, %r9, %r10, %r11。
  • 规则: Caller (调用者) 必须假设 Callee (被调用者) 会破坏这些寄存器的内容。
  • 行动: 如果 Caller 在 call 之后还需要这些寄存器中的值，Caller 必须自己在 call 指令之前将它们保存（例如压入栈中），并在 call 之后恢复它们。

• 被调用者保存 (Callee-Saved):

  • 寄存器: %rbx, %rbp, %r12, %r13, %r14, %r15。
  • 规则: Caller (调用者) 可以假设 Callee (被调用者) 在返回时会保持这些寄存器的值不变。
  • 行动: 如果 Callee 需要使用这些寄存器，它必须在使用前保存它们的原始值（通常是压入栈中），并在 ret 指令之前将它们恢复。

• %rsp 是特殊的，它必须在 Callee 返回时被正确恢复。

3.4 递归 (Recursion) 的实现

在 Y86-64 与 x86-64 体系结构中，递归函数的实现不需要任何特殊的硬件指令支持。它完全依赖于标准的函数调用机制，即利用栈 (Stack) 的特性和软件层面的调用约定。

1. 核心机制 (Core Mechanisms)

递归能够正常工作，主要得益于以下三个基石：

• 栈帧 (Stack Frames):
  • 每次函数调用（即使是调用自身）都会在栈上分配一段私有的存储空间。
  • 这保证了不同层级的递归（例如 pcount_r(2) 和 pcount_r(1)）虽然运行同一段代码，但拥有独立的局部变量和返回地址，互不干扰。
• 寄存器保存约定 (Register Saving Conventions):
  • 这是递归中数据“存活”的关键。
  • 被调用者保存 (Callee-Saved) 寄存器（如 %rbx）确保了当内层递归返回时，外层函数保存在其中的临时数据（如当前的计算结果）依然保持原样。
• 栈的 LIFO 特性:
  • 栈的“后进先出”规则与函数调用的 call / ret 模式（P调用Q，Q必须在P之前返回）完美契合。

2. 实例分析：统计置位位数 (pcount_r)

这个例子展示了如何利用 Callee-Saved 寄存器 (%rbx) 在递归调用之间保存局部状态。

2.1 C 语言源代码

long pcount_r(unsigned long x) {
    if (x == 0) return 0;
    // 逻辑拆解：
    // 1. 计算 (x & 1)。这个值必须保存下来，等待递归返回。
    // 2. 递归调用 pcount_r(x >> 1)。
    // 3. 将两部分结果相加。
    return (x & 1) + pcount_r(x >> 1);
}
````

#### 2.2 汇编实现详解


```Code snippet
pcount_r:
    # --- 1. 保存现场 (Prologue) ---
    pushq %rbx           # 【关键步骤】
                         # %rbx 是 Callee-Saved 寄存器。
                         # 在使用它之前，必须把调用者(上一层)的值压栈保存。
                         # 这为当前层创建了一个安全的私有寄存器空间。

    movq %rdi, %rbx      # 将参数 x 复制到 %rbx，方便后续操作。

    # --- 2. 局部计算 ---
    andl $1, %ebx        # 计算 %rbx = x & 1。
                         # 此时，%rbx 保存的是当前这一位的计算结果。
                         # 因为它在 Callee-Saved 寄存器中，所以即使下面发生了 call，
                         # 这个值也不会被覆盖。

    shrq %rdi            # 计算 x >> 1。
                         # 更新 %rdi，作为传给下一层递归的参数。

    # --- 3. 递归调用 (Recursive Call) ---
    testq %rbx, %rbx     # (可选优化) 检查 x 是否为 0，处理基准情况
    je .L_return_zero    # 如果是0，跳转处理（省略具体代码，聚焦递归流）

    call pcount_r        # 【递归发生】
                         # 此时当前函数暂停，控制权交给下一层。
                         # 关键：下一层也会遵守约定先 pushq %rbx，
                         # 所以我们放在 %rbx 里的 (x&1) 是绝对安全的。

    # --- 4. 恢复与累加 (Accumulate) ---
    # 当 call 返回时：
    # %rax = pcount_r(x>>1) 的返回值 (由下一层计算得出)
    # %rbx = (x & 1) 的值 (我们之前算好并保存住的)

    addq %rbx, %rax      # 结果 = 当前位(x&1) + 剩余位统计(%rax)

    # --- 5. 恢复现场 (Epilogue) ---
    popq %rbx            # 【关键步骤】
                         # 函数返回前，必须将栈里保存的旧 %rbx 弹回寄存器。
                         # 做到“借用完原样归还”，不破坏上一层的数据。
    ret

.L_return_zero:
    movl $0, %eax
    popq %rbx            # 即使是基准情况返回，也要配对 pop
    ret

3. 为什么必须保存寄存器？(Deep Dive)

• 问题: 为什么不能把 (x & 1) 的结果存在 %rdx 或 %rcx 这种 Caller-Saved 寄存器里？
• 原因: Caller-Saved 寄存器属于“临时工”。当你执行 call pcount_r 时，下一层函数有权随意修改 %rdx 的值。等你从 call 回来时，%rdx 里的数据可能已经变了。
• 解决: 必须使用 Callee-Saved 寄存器（如 %rbx）。约定强制要求：不管下一层函数怎么运行，它在返回时必须保证 %rbx 的值与调用前一模一样（通过它自己的 push/pop 实现）。