函数调用与运行时栈

概念

上一篇讲的是"数据摆在哪"（数组、结构体、对齐）。这一篇要回答一个更根本的问题：

函数一被调用，那些局部变量是从哪儿"长出来"的？函数一返回，它们又去哪儿了？

答案是栈（stack）。 而**"栈"这件事我们在 lang/04-stack.md 已经从汇编侧完整讲过一遍了**——那篇讲的是"你要手写 addiu $sp, $sp, -8 / sw $ra, 0($sp)"。

这一篇的视角换了一下：

	`lang/04-stack.md`（汇编）	本篇（C）
谁建栈帧	你手写	编译器自动生成
栈帧内容	你按约定摆	编译器按 ABI 摆
你想做的事	让程序跑对	理解"为什么局部变量会消失"

一句话：

C 的函数调用机制，就是编译器替你写的 lang/04 那套栈帧代码

先建立最直观的图：栈是一摞"活动记录（activation record）"，也就是栈帧。

高地址  0x7FFFFFFC  ┌─────────────────────────┐
                    │  main 的栈帧             │   ← 最先进来，在最底下
                    ├─────────────────────────┤
                    │  f(5) 的栈帧             │
                    ├─────────────────────────┤
                    │  f(4) 的栈帧             │   ← 每调用一次，压一帧
                    ├─────────────────────────┤
        $sp ────►   │  f(3) 的栈帧             │   ← 当前正在跑的这层
低地址              └─────────────────────────┘
                     地址减小方向 = 栈生长方向

两个必须钉死的性质：

性质	含义
后进先出（LIFO）	最后压入的帧最先弹出——这恰好匹配"函数调用/返回"
向下生长	压栈 = `$sp` 减小（MIPS/x86/x86-64 都如此）

本篇在主线上的位置：lang/04-stack.md 讲了"栈帧怎么手搭"，lang/12-layout.md 讲了"数据怎么摆"。 本篇把两者合起来，回答"运行时（runtime）"这件事——这也是通向 L4 操作系统的必经之路：进程的栈、栈溢出、内核栈，全从这里长出来。

原理

一、栈的两个用途：保存现场 + 放局部变量

一个栈帧里装的东西，按用途分两类：

用途	装什么	为什么需要
① 保存现场	返回地址 `$ra`、旧的帧指针 `$fp`、被调用者保存的寄存器（`$s0-$s7`）	函数返回时要"恢复调用前的样子"
② 存放局部数据	局部变量、数组、结构体、临时值	它们的作用域只在函数内，用栈天然合适

为什么这两件事都用栈？ 因为它们有完全相同的生命周期——都精确地"从函数被调用到函数返回"。

对比堆（下一篇）：堆上的对象可以活过函数返回（malloc 出来的一直活到 free）。栈上的东西不行。这就是"局部变量不能返回地址"的根本原因（回链 lang/11-pointer.md 的悬垂指针）。

"保存现场"到底保存什么？ 两个层次（回链 lang/04-stack.md）：

寄存器类别	谁负责保存	原因
`$t0-$t9`（调用者保存）	调用者自己	被调用者可以随便用——叶子函数因此零保存开销
`$s0-$s7`（被调用者保存）	被调用者自己	调用者指望它们不变——长命变量一次存好
`$ra`	谁调用谁保存	`jal` 会覆盖它——非叶子函数必须先存（回链 `lang/04`）

二、调用约定：参数怎么传、结果怎么回

"调用约定（calling convention）"是 ABI 的一部分——它规定"参数放哪、返回值放哪、谁保存哪些寄存器"。

MIPS o32（本站教学口径，回链 lang/04-stack.md）：

项	约定
前 4 个参数	`$a0`~`$a3`
第 5 个起	压栈（位于 `16($sp)` 开始；`0~15` 是 `$a0`~`$a3` 的保留溢出槽）
返回值	`$v0`（第 2 个用 `$v1`）
返回地址	`$ra`
调用者保存	`$t0-$t9`、`$a0-$a3`
被调用者保存	`$s0-$s7`、`$gp`、`$sp`、`$fp`、`$ra`

x86-64 System V（对照）：

项	约定
前 6 个整数参数	`rdi, rsi, rdx, rcx, r8, r9`
前 8 个浮点参数	`xmm0`~`xmm7`
第 7 个起	压栈
返回值	`rax`
被调用者保存	`rbx, rbp, r12~r15`

一个值得注意的历史细节：32 位 x86 的 cdecl 约定把参数"从右到左"压栈——这样第一个参数就永远在栈顶 0(%esp) 的位置：

这让"可变参数函数"（printf）能工作：printf 只知道格式串在哪（第一个参数），剩下的按格式串去栈上"数着取"。 MIPS 的 a0-a3 保留溢出槽（0~15($sp)）也是同一个目的——让被调用者能把寄存器参数"溢出"到栈上，形成一个连续的参数区。

这就是为什么"第 5 个参数在 16($sp)"而不是 0($sp)——前面 16 字节是给 a0-a3 预留的位置，保证参数区在内存里是连续的。

三、栈帧的完整构成

一个非叶子函数的栈帧（MIPS o32，8 字节对齐）：

        高地址（$fp 指向帧的"顶部"，是固定锚点）
        ┌────────────────────────────────────────┐
 $fp →  │  【调用者的帧】                          │
        ├────────────────────────────────────────┤
        │  参数区（第 5 个参数起，16($sp) 处）      │  ← 调用者压入
        ├────────────────────────────────────────┤
        │  $a0~$a3 的溢出槽（0~15 字节）           │  ← 保留位置
        ├────────────────────────────────────────┤
        │  保存的 $ra                              │  ← 被调用者保存
        ├────────────────────────────────────────┤
        │  保存的 $fp                              │
        ├────────────────────────────────────────┤
        │  保存的 $s0~$s7                          │
        ├────────────────────────────────────────┤
        │  局部变量 / 数组 / 临时值                 │
        └────────────────────────────────────────┘
        低地址（$sp 指向当前栈顶，随函数内部变化）

$sp 与 $fp 的分工（回链 lang/04-stack.md）：

寄存器	变化吗	作用
`$sp`	会变（函数内 `addiu $sp, $sp, -N` 分配临时空间时会动）	当前栈顶；函数返回时用它恢复
`$fp`	整个函数内不变	局部变量的"固定锚点"——局部变量一律写成 `偏移($fp)`，就不会被 `$sp` 的波动影响

$fp 是"因为 $sp 会变"才存在的——它把"变化的栈顶"和"不变的局部变量基址"分开。所以简单函数可以省掉 $fp（编译器 -fomit-frame-pointer，x86-64 上默认开启）——局部变量改用 $sp 相对寻址，省掉存旧 $fp 的一对 sw/lw。

序曲与尾声（prologue / epilogue）——每个函数开头和结尾的固定套路：

asm

# ── prologue（序曲）：进函数先做这三件事 ──
        addiu $sp, $sp, -FRAME      # ① 分配帧
        sw    $ra, 0($sp)           # ② 保存返回地址（非叶子）
        sw    $fp, 4($sp)           # ③ 保存旧帧指针
        move  $fp, $sp              #    （若用 $fp 的话）

# ── body（函数体）──
        ...

# ── epilogue（尾声）：反着来，且必须"存与恢复对称" ──
        lw    $ra, 0($sp)           # 恢复返回地址
        lw    $fp, 4($sp)           # 恢复旧帧指针
        addiu $sp, $sp, FRAME       # 释放帧
        jr    $ra                   # 返回

"存与恢复必须对称"是 lang/04-stack.md 的铁律：存了 $s0 就必须在返回前恢复它，否则调用者的变量会被悄悄改坏。 这条铁律在 C 语言里的表现就是：你不需要管它——编译器会自动生成对称的代码。 但你得知道它在发生。

四、局部变量的生命周期：为什么未初始化是垃圾

三个概念要分清：

概念	含义	例子
作用域（scope）	编译期：名字在哪儿可见	块内 `{ }`
生命周期（lifetime）	运行期：对象什么时候存在	从进函数到出函数
存储期（storage duration）	对象存在多久	自动（栈）/ 静态 / 动态（堆）

"未初始化的局部变量是垃圾"的机制：

void f(void) { int x;  printf("%d\n", x);  /* 打印什么？—— 不知道 */ }

因为：int x 只是"把 $sp 往下挪了 4 字节"——那块内存是"上一次用过它的某个函数留下的值"。

现象	机制
第一次调用 `f` 打印出奇怪的值	那块栈内存刚被 `main` 或别的函数用过
不同机器/不同编译选项打印不同值	栈上残留内容不同
调试版一切正常、发布版出错	优化改变了栈的复用方式

这就是"未初始化变量是未定义行为（UB）"的原因——它不是"某个固定垃圾值"，而是"上次谁用过这块内存"的证据。注意：静态变量和全局变量不一样——它们在 .bss/.data 段（回链 lang/24-image.md 会讲），未初始化时被保证为 0。

块作用域的变量可以"复用同一块栈"：

void g(void) {
    { int a = 1; printf("%d\n", a); }   /* a 用栈的某处 */
    { int b = 2; printf("%d\n", b); }   /* b 很可能用同一处 —— 编译器会复用 */
}

编译器为什么要复用？ 因为两个块不会同时活着——复用能省栈空间。 代价就是"b 的初始内容是 a 留下的"。

五、递归：栈深度与栈溢出

递归不是"循环的语法糖"，它是"真的压了很多层栈帧"（回链 lang/04）：

递归的最大深度 = \frac{栈空间}{每层的帧大小}

典型数值（下面会实算）：

每帧大小	8 MiB 栈能撑多少层
8 字节（极小函数）	约 104.8 万层
64 字节（几个局部变量）	约 13.1 万层
256 字节（含一个 `char[200]` 缓冲区）	约 3.3 万层

两个必须知道的结论：

帧大小直接决定深度上限——"栈上开大数组"是递归杀手的头号原因；
线性的递归（如 sum(n) = n + sum(n-1)）深度 = n，而"二分递归"深度是 log n 但节点数爆炸——两种情况要分开分析。

"栈溢出（stack overflow）"发生时：$sp 撞到栈的边界（或撞到堆） → 触发异常 / 段错误。 操作系统会给栈设上限（Linux 默认 8 MiB，ulimit -s 可查）。

注意"栈溢出"这个词有两个意思： ① 递归太深把栈用光（本篇这个，进程崩溃）； ② 缓冲区溢出（buffer overflow）（下面第六节，写越界的数组，是安全问题）。 中文里都叫"溢出"，但机制完全不同。

六、缓冲区溢出：栈上的数组写越界会覆盖什么

"栈上的数组"和"返回地址"在同一个帧里，而且相邻——这是缓冲区溢出的全部原因：

void vulnerable(const char *input) {
    char buf[16];              /* 栈上的 16 字节 */
    strcpy(buf, input);        /* ✗ 不检查长度 */
}

帧的布局（按地址从低到高）：

        低地址
        ┌──────────────────┐
 $sp →  │  buf[0..15]      │  ← 16 字节
        ├──────────────────┤
        │  (保存的 $s0)     │
        ├──────────────────┤
        │  保存的 $ra       │  ← ★ 返回地址在这里
        ├──────────────────┤
        │  保存的 $fp       │
        └──────────────────┘
        高地址（$fp 方向）

如果 input 有 24 个字符：

写入的字节	落到哪	后果
`buf[0..15]`	`buf` 本身	正常
`buf[16..19]`	保存的 `$s0`	调用者的寄存器变量被改坏
`buf[20..23]`	保存的 `$ra`	函数返回时会跳到"攻击者指定的地址"

这就是经典的"栈溢出攻击"：覆盖 $ra，让函数返回时跳到别的地方去执行。防御手段（后面课程会讲）：栈保护（canary）、ASLR、不可执行栈（NX）、边界检查。 C 语言里的防线很朴素：用 strncpy/snprintf 带长度参数，或者用 std::string/vector（C++）。

示例

例 1：一个 C 函数 → 完整的栈帧与汇编

任务：把 f(x) = g(x) + 1 编译出的栈帧完整列出来。

int g(int x);              /* 声明 */
int f(int x) {
    int r = g(x);          /* 调用 —— 必须保存 $ra 和 x */
    return r + 1;
}

MIPS32（回链 lang/04-stack.md）：

asm

f:
        # ── prologue ──
        addiu $sp, $sp, -8        # 帧大小 8（8 的倍数，回链 lang/04 的对齐要求）
        sw    $ra, 4($sp)         # 保存返回地址（非叶子函数必须）
        sw    $a0, 0($sp)         # 保存 x —— 跨调用，$a0 会被 g 覆盖

        # ── body ──
        jal   g                   # 调用 g(x)，参数已在 $a0
        lw    $a0, 0($sp)         # 取回 x（注意：$v0 已是 g 的返回值）
        addiu $v0, $v0, 1         # r + 1

        # ── epilogue（与 prologue 严格对称）──
        lw    $ra, 4($sp)
        addiu $sp, $sp, 8
        jr    $ra

用 Python 把"逐条指令下 $sp/内存的变化"跑出来：

python

import unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

SP0 = 0x7FFFEFFC                       # main 调用 f 时的 $sp
RA_CALLER, X = 0x004000A8, 7           # 调用者的返回地址 / 实参 x
mem = {}

def line(ins, sp, note):
    print("  " + pad(ins, 26) + pad("$sp = 0x%08X" % sp, 20) + note)

print(f"  进入 f 前：$sp = {SP0:#010x}  $ra = {RA_CALLER:#010x}  $a0（=x）= {X}")
print("  " + pad("指令", 26) + pad("$sp", 20) + "说明")

sp = SP0
sp -= 8;        line("addiu $sp, $sp, -8", sp, "分配 8 字节帧")
mem[sp + 4] = RA_CALLER
line("sw $ra, 4($sp)", sp, f"存 $ra（非叶子 → 必存）→ mem[{sp+4:#x}]")
mem[sp + 0] = X
line("sw $a0, 0($sp)", sp, f"存 x = {X}（$a0 会被 g 覆盖）")

mem[sp - 8] = 0                        # g 自己的帧
line("jal g", sp, f"调用 g：$ra ← {0x004000C0:#x}（f 里 jal 的下一条）")
line("（g 执行，返回）", sp, "g 用完自己的帧，$sp 恢复")
v0 = 42                                # 假设 g(x) = 42
line("addiu $v0, $v0, 1", sp, f"$v0 = {v0} + 1 = {v0+1}")

print("\n  == epilogue：对称恢复 ==")
x_back = mem[sp + 0]
line("lw $a0, 0($sp)", sp, f"取回 x = {x_back}（供后续使用）")
ra_back = mem[sp + 4]
line("lw $ra, 4($sp)", sp, f"恢复 $ra = {ra_back:#010x}")
sp += 8;        line("addiu $sp, $sp, 8", sp, "释放帧")
line("jr $ra", sp, "返回调用者")

print(f"\n  返回时 $sp = {sp:#010x}，与进入前 {SP0:#010x} 相同 → {sp == SP0}")
print("  ★ 帧大小 8 的倍数（回链 lang/04 的 $sp 8 字节对齐要求）")
print("  ★ 存了哪些就先恢复哪些 —— 存/恢复必须对称")

预期输出：

  进入 f 前：$sp = 0x7fffeffc  $ra = 0x004000a8  $a0（=x）= 7
  指令                      $sp                 说明
  addiu $sp, $sp, -8        $sp = 0x7FFFEFF4    分配 8 字节帧
  sw $ra, 4($sp)            $sp = 0x7FFFEFF4    存 $ra（非叶子 → 必存）→ mem[0x7fffeff8]
  sw $a0, 0($sp)            $sp = 0x7FFFEFF4    存 x = 7（$a0 会被 g 覆盖）
  jal g                     $sp = 0x7FFFEFF4    调用 g：$ra ← 0x4000c0（f 里 jal 的下一条）
  （g 执行，返回）          $sp = 0x7FFFEFF4    g 用完自己的帧，$sp 恢复
  addiu $v0, $v0, 1         $sp = 0x7FFFEFF4    $v0 = 42 + 1 = 43

  == epilogue：对称恢复 ==
  lw $a0, 0($sp)            $sp = 0x7FFFEFF4    取回 x = 7（供后续使用）
  lw $ra, 4($sp)            $sp = 0x7FFFEFF4    恢复 $ra = 0x004000a8
  addiu $sp, $sp, 8         $sp = 0x7FFFEFFC    释放帧
  jr $ra                    $sp = 0x7FFFEFFC    返回调用者

  返回时 $sp = 0x7fffeffc，与进入前 0x7fffeffc 相同 → True
  ★ 帧大小 8 的倍数（回链 lang/04 的 $sp 8 字节对齐要求）
  ★ 存了哪些就先恢复哪些 —— 存/恢复必须对称

三条结论：

结论	说明
非叶子函数必须存 `$ra` 和跨调用的参数	`jal` 覆盖 `$ra`；`g` 有权改 `$a0`（两者都是调用者保存）
帧大小一定是 8 的倍数	`$sp` 必须 8 字节对齐（回链 `lang/04`）
prologue 与 epilogue 严格对称	存什么就恢复什么，顺序反过来——这是编译器自动保证的

例 2：递归阶乘——每层一帧

任务：把 fact(5) 的 6 层栈帧与 $sp 变化算出来。

int fact(int n) {
    if (n < 2) return 1;
    return n * fact(n - 1);      /* 递归 —— 必须保存 n 和返回地址 */
}

MIPS32：

asm

fact:
        addiu $sp, $sp, -8
        sw    $ra, 4($sp)         # 必须存：递归调用会覆盖 $ra
        sw    $a0, 0($sp)         # 必须存：递归调用会覆盖 $a0（= n）

        slti  $t0, $a0, 2         # n < 2 ?
        beq   $t0, $zero, rec
        li    $v0, 1              # 基本情况
        b     done

rec:
        addiu $a0, $a0, -1        # n - 1
        jal   fact                # 递归
        lw    $a0, 0($sp)         # 取回本层的 n ← ★忘了这句，结果恒 0
        mul   $v0, $v0, $a0       # n * fact(n-1)

done:
        lw    $ra, 4($sp)
        addiu $sp, $sp, 8
        jr    $ra

用 Python 算出 6 层帧的地址阶梯：

python

import unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

SP0, FRAME = 0x7FFFEFFC, 8

# main 调用 fact(5)：压 6 层帧（n = 5,4,3,2,1 各一层 + main 层算 1）
print(f"  初始 $sp = {SP0:#010x}   帧大小 = {FRAME} 字节")
print("\n  " + pad("层", 6) + pad("n", 4) + pad("分配后 $sp", 16) + pad("偏移(run)", 12) + "内容")
layers = [(0, "main"), (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]
sp = SP0
for i, n in layers:
    sp -= FRAME
    content = "$ra + 调用者的变量" if i == 0 else f"$ra, n = {n}"
    print("  " + pad(str(i), 6) + pad(str(n), 6) + pad("0x%08X" % sp, 16)
          + pad("%d" % (i * FRAME), 12) + content)

print(f"\n  最深时 $sp = {sp:#010x}（从 {SP0:#010x} 下降 {SP0 - sp} 字节）")
print(f"  下降量 = 层数({len(layers)}) × 帧大小({FRAME}) = {len(layers) * FRAME}  → 一致")
print("  注意：n、$ra 每层各存一份 —— 6 层就有 6 个不同的 n 同时活着")
print("        这就是递归能工作、而“单份变量”会出错的原因")

print("\n  === 返回时的拆帧（与上面严格对称）===")
sp = SP0 - len(layers) * FRAME
for i, n in reversed(layers):
    sp += FRAME
    tag = f"返回 n = {n}" if n != "main" else "返回 main"
    print("  " + pad(tag, 18) + pad("$sp = 0x%08X" % sp, 20) + "收回本层帧")
print(f"\n  最终 $sp = {sp:#010x} → 回到初始值：{sp == SP0}")
print("  ★ push 了多少层就 pop 多少层 —— $sp 必然回到原处")

print("\n  === 算一下返回值 ===")
v = 1
trace = []
for n in (2, 3, 4, 5):
    v *= n
    trace.append(f"{n} × {v // n} = {v}")
print("  fact(1)=1 → " + "  →  ".join(trace))
print(f"  fact(5) = {v}")

预期输出：

  初始 $sp = 0x7fffeffc   帧大小 = 8 字节

  层    n   分配后 $sp      偏移(run)   内容
  0     main  0x7FFFEFF4      0           $ra + 调用者的变量
  1     5     0x7FFFEFEC      8           $ra, n = 5
  2     4     0x7FFFEFE4      16          $ra, n = 4
  3     3     0x7FFFEFDC      24          $ra, n = 3
  4     2     0x7FFFEFD4      32          $ra, n = 2
  5     1     0x7FFFEFCC      40          $ra, n = 1

  最深时 $sp = 0x7fffefcc（从 0x7fffeffc 下降 48 字节）
  下降量 = 层数(6) × 帧大小(8) = 48  → 一致
  注意：n、$ra 每层各存一份 —— 6 层就有 6 个不同的 n 同时活着
        这就是递归能工作、而“单份变量”会出错的原因

  === 返回时的拆帧（与上面严格对称）===
  返回 n = 1        $sp = 0x7FFFEFD4    收回本层帧
  返回 n = 2        $sp = 0x7FFFEFDC    收回本层帧
  返回 n = 3        $sp = 0x7FFFEFE4    收回本层帧
  返回 n = 4        $sp = 0x7FFFEFEC    收回本层帧
  返回 n = 5        $sp = 0x7FFFEFF4    收回本层帧
  返回 main         $sp = 0x7FFFEFFC    收回本层帧

  最终 $sp = 0x7fffeffc → 回到初始值：True
  ★ push 了多少层就 pop 多少层 —— $sp 必然回到原处

  === 算一下返回值 ===
  fact(1)=1 → 2 × 1 = 2  →  3 × 2 = 6  →  4 × 6 = 24  →  5 × 24 = 120
  fact(5) = 120

三条结论：

结论	说明
递归 = 每层一个独立栈帧	`n`、`$ra` 每层各存一份——"单份变量"无法实现递归
深度 = 调用链长度	`fact(5)` 压 6 帧（含 `main`）→ 48 字节
必须同时保存 `$ra` 与 `$a0`	只存 `$ra` 会导致结果恒 0；只存 `$a0` 会导致死循环（回链 `lang/04`）

例 3：栈深度上限——把"能递归多深"算出来

任务：给定栈大小与帧大小，算最大递归深度。

#include <stdio.h>

/* 三种典型帧：极小 / 中等 / 带大缓冲区 */
int sum_small(int n) {                 /* 帧很小 */
    if (n == 0) return 0;
    return n + sum_small(n - 1);
}

int sum_buf(int n) {                   /* 帧里带一个 char[200] */
    char buf[200];
    buf[0] = 0;
    if (n == 0) return 0;
    return n + sum_buf(n - 1);
}

用 Python 算三种帧下的深度上限：

python

import unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

STACK = 8 * 1024 * 1024                # Linux 默认 8 MiB 栈

CASES = [
    ("极小函数（无局部变量）",   8),
    ("有 4 个 int 局部变量",     8 + 16 + 8),      # 帧对齐到 8
    ("带 char buf[200]",         8 + 200 + 8),     # 216 → 对齐仍 216
    ("带 char buf[4096]（4 KiB）", 8 + 4096 + 8),
]

print(f"  栈大小 = {STACK} 字节 = {STACK // 1024 // 1024} MiB\n")
print("  " + pad("场景", 30) + pad("帧大小", 10) + pad("最大深度", 16) + "备注")
for name, frame in CASES:
    depth = STACK // frame
    note = ""
    if depth > 1_000_000:
        note = "很深，但要小心别写成 O(n) 的深递归"
    elif depth > 10_000:
        note = "约几万层，正常业务够用"
    else:
        note = "很浅：栈上开大缓冲是递归杀手"
    print("  " + pad(name, 30) + pad(str(frame), 10) + pad(f"{depth:,}", 16) + note)

print("\n  === 结论 ===")
print(f"  8 字节/帧 → 约 {STACK // 8:,} 层（约 104.8 万）")
print(f"  216 字节/帧 → 约 {STACK // 216:,} 层（约 3.9 万）")
print("  → 帧大小每翻一倍，深度上限就减半：深度 = 栈 / 帧大小")

print("\n  === 常见“栈溢出”的真实数字 ===")
print("  不带尾递归优化的 sum(1000000)：帧 8~32 字节 → 1e6 × 32 = 32 MB > 8 MB → 崩")
print("  而 memo 化 / 改写成循环后：栈深度变成 O(1) → 立刻可行")

print("\n  === 对照：栈 vs 堆的容量 ===")
print("  栈：8 MiB（固定上限，超了就是段错误）")
print("  堆：几乎等于可用内存（理论上 GB 级）—— 所以“大数据放堆、小变量放栈”")

预期输出：

  栈大小 = 8388608 字节 = 8 MiB

  场景                          帧大小    最大深度        备注
  极小函数（无局部变量）        8         1,048,576       很深，但要小心别写成 O(n) 的深递归
  有 4 个 int 局部变量          32        262,144         约几万层，正常业务够用
  带 char buf[200]              216       38,836          约几万层，正常业务够用
  带 char buf[4096]（4 KiB）    4112      2,040           很浅：栈上开大缓冲是递归杀手

  === 结论 ===
  8 字节/帧 → 约 1,048,576 层（约 104.8 万）
  216 字节/帧 → 约 38,836 层（约 3.9 万）
  → 帧大小每翻一倍，深度上限就减半：深度 = 栈 / 帧大小

  === 常见“栈溢出”的真实数字 ===
  不带尾递归优化的 sum(1000000)：帧 8~32 字节 → 1e6 × 32 = 32 MB > 8 MB → 崩
  而 memo 化 / 改写成循环后：栈深度变成 O(1) → 立刻可行

  === 对照：栈 vs 堆的容量 ===
  栈：8 MiB（固定上限，超了就是段错误）
  堆：几乎等于可用内存（理论上 GB 级）—— 所以“大数据放堆、小变量放栈”

三条结论：

结论	说明
深度 = 栈 ÷ 帧大小	帧大小由"局部变量总量"决定
栈上开大数组 = 深度骤降	`char[4096]` 让深度只剩 2000 层
栈有硬上限（8 MiB）	"递归解百万级问题"要先估算深度（或用尾递归 / 迭代 / 显式栈）

例 4：栈上数组越界会覆盖什么

任务：把"缓冲区溢出"的覆盖顺序画出来。

#include <string.h>

void vulnerable(const char *input) {
    char buf[16];
    strcpy(buf, input);        /* ✗ 不检查长度 */
}

int main(void) {
    vulnerable("AAAAAAAAAAAAAAAAAAAAAAAA");   /* 24 个字符 */
    return 0;
}

用 Python 模拟"逐字节写栈"，看哪一字节落到 $ra：

python

import unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

# 帧布局（从低地址到高地址）：   偏移 0..15 = buf, 16..19 = 保存的 $s0, 20..23 = $ra, 24..27 = $fp
FRAME = [
    (0, 16, "buf[0..15]", "局部数组"),
    (16, 4, "保存的 $s0", "被调用者保存寄存器"),
    (20, 4, "保存的 $ra", "★ 返回地址"),
    (24, 4, "保存的 $fp", "旧帧指针"),
]
LEGIT = 16                      # buf 的合法容量
payload = "A" * 24              # 输入 24 字符

print(f"  帧布局（帧基 = 0，从低地址到高地址），buf 合法容量 = {LEGIT} 字节")
print("  " + pad("偏移", 8) + pad("字段", 18) + pad("大小", 6) + "说明")
for off, sz, name, note in FRAME:
    print("  " + pad(f"{off}~{off+sz-1}", 8) + pad(name, 18) + pad(str(sz), 6) + note)

print(f"\n  写入 {len(payload)} 字节（{payload[:8]}…）→ strcpy 一路写下去：")
print("  " + pad("写入序", 8) + pad("落到偏移", 10) + pad("命中字段", 18) + "后果")
for k in range(len(payload)):
    hit = next((n for off, sz, n, _ in FRAME if off <= k < off + sz), "越界")
    if hit == "buf[0..15]":
        eff = "正常"
    elif hit == "保存的 $s0":
        eff = "调用者的寄存器变量被改坏"
    elif hit == "保存的 $ra":
        eff = "★★ 返回地址被覆盖 → 跳到 'AAAA' 地址（0x41414141）"
    else:
        eff = "旧帧指针被改坏 → 返回后崩"
    if k < 17 or k >= 20:
        print("  " + pad(str(k + 1), 8) + pad(str(k), 10) + pad(hit, 18) + eff)
    elif k == 17:
        print("  " + pad("…", 8) + pad("…", 10) + pad("（16~19 逐字节覆盖 $s0）", 18) + "同上")

print("\n  === 关键数字 ===")
print(f"  buf 只有 {LEGIT} 字节，输入 {len(payload)} 字节 → 越界 {len(payload) - LEGIT} 字节")
print(f"  其中 {len(payload) - 16} 字节落在 $s0 上，{[20,21,22,23]} 号字节落在 $ra 上")
print(f"  0x41414141 = 'AAAA' → 若 CPU 真跳过去，就是段错误（或更糟）")

print("\n  === 正确的写法 ===")
print("  strncpy(buf, input, sizeof(buf) - 1);  buf[sizeof(buf) - 1] = 0;")
print("  snprintf(buf, sizeof(buf), \"%s\", input);")
print("  或直接用动态分配的字符串（C++ 的 std::string / 现代语言的 string）")
print("  ★ 要点不是“记住这个函数”，而是“任何写入都必须带长度上限”")

预期输出：

  帧布局（帧基 = 0，从低地址到高地址），buf 合法容量 = 16 字节
  偏移    字段              大小  说明
  0~15    buf[0..15]        16    局部数组
  16~19   保存的 $s0        4     被调用者保存寄存器
  20~23   保存的 $ra        4     ★ 返回地址
  24~27   保存的 $fp        4     旧帧指针

  写入 24 字节（AAAAAAAA…）→ strcpy 一路写下去：
  写入序  落到偏移  命中字段          后果
  1       0         buf[0..15]        正常
  2       1         buf[0..15]        正常
  3       2         buf[0..15]        正常
  4       3         buf[0..15]        正常
  5       4         buf[0..15]        正常
  6       5         buf[0..15]        正常
  7       6         buf[0..15]        正常
  8       7         buf[0..15]        正常
  9       8         buf[0..15]        正常
  10      9         buf[0..15]        正常
  11      10        buf[0..15]        正常
  12      11        buf[0..15]        正常
  13      12        buf[0..15]        正常
  14      13        buf[0..15]        正常
  15      14        buf[0..15]        正常
  16      15        buf[0..15]        正常
  17      16        保存的 $s0        调用者的寄存器变量被改坏
  …       …         （16~19 逐字节覆盖 $s0）同上
  21      20        保存的 $ra        ★★ 返回地址被覆盖 → 跳到 'AAAA' 地址（0x41414141）
  22      21        保存的 $ra        ★★ 返回地址被覆盖 → 跳到 'AAAA' 地址（0x41414141）
  23      22        保存的 $ra        ★★ 返回地址被覆盖 → 跳到 'AAAA' 地址（0x41414141）
  24      23        保存的 $ra        ★★ 返回地址被覆盖 → 跳到 'AAAA' 地址（0x41414141）

  === 关键数字 ===
  buf 只有 16 字节，输入 24 字节 → 越界 8 字节
  其中 8 字节落在 $s0 上，[20, 21, 22, 23] 号字节落在 $ra 上
  0x41414141 = 'AAAA' → 若 CPU 真跳过去，就是段错误（或更糟）

  === 正确的写法 ===
  strncpy(buf, input, sizeof(buf) - 1);  buf[sizeof(buf) - 1] = 0;
  snprintf(buf, sizeof(buf), "%s", input);
  或直接用动态分配的字符串（C++ 的 std::string / 现代语言的 string）
  ★ 要点不是“记住这个函数”，而是“任何写入都必须带长度上限”

三条结论：

结论	说明
越界写会按地址顺序"吃掉"后面所有东西	`buf` 后面就是保存的寄存器和返回地址（同一个帧！）
覆盖 `$ra` = 劫持控制流	函数返回时跳到"攻击者写的地址"——这是最经典的漏洞类型
防御靠"带长度"	任何写入都要有上限（`sizeof`）；语言层防护（`std::string`）是更好的答案

考点

1. 栈的两个用途与生长方向

保存现场（$ra、旧 $fp、$s 系列）+ 存放局部数据；
后进先出、向下生长（压栈 = $sp 减小）；
栈帧的生存期 = 函数的调用期——所以局部变量的地址不能返回（回链 lang/11）。

2. 调用约定（ABI）

	MIPS o32（本站）	x86-64 System V
参数	`$a0`~`$a3`，第 5 个起压栈（`16($sp)`）	`rdi,rsi,rdx,rcx,r8,r9`
返回	`$v0`	`rax`
返回地址	`$ra`	压栈
调用者保存	`$t0-$t9`、`$a0-$a3`	`rax, rcx, rdx, rsi, rdi, r8-r11`
被调用者保存	`$s0-$s7`、`$sp/$fp/$ra`	`rbx, rbp, r12-r15`

32 位 x86 用 cdecl：参数从右到左压栈 → 支持 printf 这类可变参数；
MIPS 的 0~15($sp) 是 $a0~$a3 的保留溢出槽——保证参数区在内存里连续。

3. 栈帧结构（必背）

从高到低：参数区 → $a0-$a3 溢出槽 → 保存的 $ra → 保存的 $fp → 保存的 $s → 局部变量。

$sp 会变（栈顶）、$fp 不变（局部变量锚点）；
帧大小一定是 8 的倍数（$sp 必须 8 字节对齐）；
prologue：addiu $sp → 存 $ra/$fp → move $fp,$sp；
epilogue 严格对称。

4. 局部变量的生命周期

作用域（编译期可见性）≠ 生命周期（运行期存在）；
未初始化局部变量的值是"上次用过这块栈的内存的残留"——不是固定值 → 未定义行为；
块作用域的变量可以复用同一块栈；
静态 / 全局变量在 .bss/.data，未初始化保证为 0。

5. 递归与栈深度（计算题）

最大深度 = \frac{栈大小}{帧大小}

Linux 默认栈 8 MiB；
8 字节/帧 → 约 104.8 万层；216 字节/帧 → 约 3.9 万层；
栈上开大数组是"深度杀手"；
递归必须同时保存 $ra 与 $a0（只存 $ra → 结果恒 0；只存 $a0 → 死循环）。

6. 缓冲区溢出

栈上的数组与返回地址在同一个帧里 → 越界写会覆盖 $ra；
覆盖 $ra = 劫持控制流（经典栈溢出攻击）；
防御：任何写入都带长度上限（strncpy/snprintf）；系统层面靠 canary / ASLR / NX；
注意两个"栈溢出"意思不同：递归太深（进程崩）vs 缓冲区越界（安全漏洞）。

7. 高频易错点

sizeof(数组参数) 得到指针大小（回链 lang/11）；
返回局部变量的地址 = 悬垂指针；
"局部变量一定在栈上"是错的——编译器可能放进寄存器（优化后 register 分配）；
不要假设"参数一定在栈上"——前几个靠寄存器传；
栈的地址每次运行可能不同（ASLR）——所以"打印地址做差"能算相对偏移，不能当绝对地址用。

小结

C 的函数调用 = 编译器替你写的 lang/04 栈帧代码：prologue → body → epilogue。
栈的两个用途：保存现场（$ra、$fp、$s）+ 放局部变量；后进先出、向下生长。
调用约定：MIPS $a0-$a3 传参、$v0 返回、$t 调用者保存、$s 被调用者保存、第 5 个参数在 16($sp)。
$sp 会变、$fp 不变：$fp 是局部变量的固定锚点（简单函数可省）。
帧大小一定是 8 的倍数（$sp 8 字节对齐）；存/恢复必须对称。
未初始化的局部变量是"上次谁用过这块栈"的残留——不是固定垃圾值，是未定义行为。
递归深度 = 栈 ÷ 帧大小：8 MiB 栈、8 字节/帧约 104.8 万层；char[4096] 则只剩 2000 层。
递归必须同时保存 $ra 和参数，否则结果恒 0 或死循环。
栈上数组越界会覆盖 $ra——这是最经典的缓冲区溢出；防御靠"写入必带长度上限"。

回到主线：到这里，"函数活着的时候"讲完了——但还有一类数据，它的要求恰恰相反：

栈上的东西"函数一返回就没了"。可程序经常需要"活得比函数久"的数据——一个链表、一个缓冲区、一块能动态长大的数组。它们放在哪？谁来管？malloc 到底做了什么、free 又怎么"还回去"？会不会有"碎片"和"泄漏"？——下一篇：动态内存分配：堆是怎么管的。

下一篇：动态内存分配：堆是怎么管的

函数调用与运行时栈

概念

原理

一、栈的两个用途：保存现场 + 放局部变量

二、调用约定：参数怎么传、结果怎么回

三、栈帧的完整构成

四、局部变量的生命周期：为什么未初始化是垃圾

五、递归：栈深度与栈溢出

六、缓冲区溢出：栈上的数组写越界会覆盖什么

示例

例 1：一个 C 函数 → 完整的栈帧与汇编

例 2：递归阶乘——每层一帧

例 3：栈深度上限——把"能递归多深"算出来

例 4：栈上数组越界会覆盖什么

考点

小结

我的笔记

评论（0）

函数调用与运行时栈 ​

概念 ​

原理 ​

一、栈的两个用途：保存现场 + 放局部变量 ​

二、调用约定：参数怎么传、结果怎么回 ​

三、栈帧的完整构成 ​

四、局部变量的生命周期：为什么未初始化是垃圾 ​

五、递归：栈深度与栈溢出 ​

六、缓冲区溢出：栈上的数组写越界会覆盖什么 ​

示例 ​

例 1：一个 C 函数 → 完整的栈帧与汇编 ​

例 2：递归阶乘——每层一帧 ​

例 3：栈深度上限——把"能递归多深"算出来 ​

例 4：栈上数组越界会覆盖什么 ​

考点 ​

小结 ​

我的笔记

评论（0）

函数调用与运行时栈

概念

原理

一、栈的两个用途：保存现场 + 放局部变量

二、调用约定：参数怎么传、结果怎么回

三、栈帧的完整构成

四、局部变量的生命周期：为什么未初始化是垃圾

五、递归：栈深度与栈溢出

六、缓冲区溢出：栈上的数组写越界会覆盖什么

示例

例 1：一个 C 函数 → 完整的栈帧与汇编

例 2：递归阶乘——每层一帧

例 3：栈深度上限——把"能递归多深"算出来

例 4：栈上数组越界会覆盖什么

考点

小结