函数的特殊用法 — 递归与内联汇编:越过高级语言的边界Copy Anchor Link

这一章讲什么: 两件事。第一,递归——函数调用自己,你会看到它在机器层 「没有任何新机制」,栈帧一层套一层就是它的全部实现;第二,当 C 语言够不到某个硬件特性 (进位/溢出标志)时,怎么用汇编把它够到——要么整个函数用汇编写,要么在 C 里内联汇编。 主线例子: factorial(3) 在 gdb 里一层层展开成三个栈帧,再一层层收拢返回 6; 以及一个「会报溢出」的 addTwo——C 版写了十几行比较,汇编版四行。

1. 递归:栈帧自己会套娃Copy Anchor Link

概念:自己调用自己,直到基准条件Copy Anchor Link

递归(recursion)就是函数调用自己来算一个更简单的子问题,再把结果用回当前问题。 每个递归算法都必须有一个基准条件(base case)——不需要再递归、直接能答的最小问题; 没有它,调用会无限进行下去,直到栈溢出¹。

书里的例子是阶乘:

n! = n × (n − 1)!     ← 递归定义:用更小的 (n−1)! 定义 n!
0! = 1                ← 基准条件:到 0 就停

对比迭代定义 n! = n × (n−1) × … × 1:计算量一样,但递归版「更简洁, 对有些人来说更直观」¹。C 实现(清单 15-3)就是一个 if:

unsigned int current = 1;      /* 先按基准条件假设 */
if (n != 0)                    /* 没到基准? */
    current = n * factorial(n - 1);   /* 递归算 (n-1)! 再乘 n */
return current;

机器层:机制上零新东西,代价在栈Copy Anchor Link

清单 15-4(编译器版)揭示了递归的唯一技术要点:参数 n 从 rdi 进来后, 必须立刻存进栈帧。原因?马上要用 rdi 传新参数(n−1)去做递归调用, 而调用返回后还需要 n 的原始值来算 n × (n−1)!——不存栈,n 就没了²。 除此之外,递归函数的汇编和普通函数一模一样:if-then 是第 13 章的, 序言结语是第 11 章的,协议是第 14 章的 17 条。

主线例子:gdb 里看 factorial(3) 的三层栈帧Copy Anchor Link

作者用 gdb 对汇编版 factorial(3) 设了两个断点:递归调用处(call)和返回处(done)。 跟着它的实录走³:

第一次断下(main 刚调进来,n=3):

rdi = 0x2            ← 正准备传 (3−1)=2 去递归
rbp = 0x7fffffffde40
x/4xg 0x7fffffffde30:
  0x7fffffffde30: 0x00007ffff7fb1fc8  0x00000003555551b0
                                     ↑ 小端序的坑:n=3 藏在这 8 字节的第 5 字节(0x03)
  0x7fffffffde40: 0x7fffffffde60      0x0000555555555156
                  ↑ 上一层 rbp        ↑ 返回地址,回 main

第三次断下(n 已到 0,基准条件):

rdi = 0x0            ← 递归终点:n=0
rbp = 0x7fffffffde00 ← 比第一次低了 0x40:64 字节,正好两层栈帧

内存里能同时看到三层栈帧:两个返回地址相同(都回 factorial 的 call 之后), 最老一层的返回地址指向 main³。

收拢:每次 done 断点命中,rsp 回到本层的 rbp、pop、ret—— 栈帧像洋葱一样一层层剥掉,最后回到 main 时 rax = 6,打印 3! = 6³。

两个实操提醒,都是书里的原话级别经验:

• 用小固定值(3)调试递归——栈帧一多,gdb 输出就淹没人了;
• 读栈上 4 字节变量要当心小端序:x/g 按 8 字节显示,n 坐在那 8 字节的「右侧第 5 字节」³。

手写版:用 eax 当「当前结果」Copy Anchor Link

清单 15-5 的手写版有个漂亮的简化:eax 就是 current。基准条件假设(eax=1)先行, 是基准就直接 ret(返回值恰好在它该在的寄存器);不是基准就递归, 返回后 mul 指令拿 eax 里的 (n−1)! 乘上栈里的 n——乘积又落回 eax,还是返回值的位置⁴。 顺带一提:作者选了无符号乘法 mul 而编译器选了 imul,因为阶乘定义在非负整数上; 两条指令的完整差异第 16 章讲⁵。

递归的账单,书里算得很清楚Copy Anchor Link

「递归函数调用使用了大量的栈空间……每种递归解决方案都有一个等价的迭代解决方案, 后者在时间和栈使用方面往往更有效。」但话锋一转:许多问题(某些排序算法)用递归 描述更自然,「代码的简洁性通常值得选择递归」⁶。这就是本章对「递归好不好」的 全部裁决:不站队,给账,让你按问题选。

2. 用汇编够到 C 够不到的硬件特性Copy Anchor Link

动机:OF 标志在 C 里看不见Copy Anchor Link

第 3 章说过:加法产生进位/溢出时,CPU 会把标志写进 rflags。 但 C 和 C++没有任何办法直接读这些标志——语言压根没暴露这个概念⁷。 书里给的问题是:两个整数相加,怎么知道溢出了?

办法有两条,都演示:

路线一:C 里硬算(没有汇编时的笨办法)Copy Anchor Link

清单 15-8 的 C 版 addTwo 用纯逻辑补 flag 的缺:同号相加得到异号结果,就是溢出——

if (((a > 0) && (b > 0) && (temp < 0)) ||
    ((a < 0) && (b < 0) && (temp > 0)))
    overflow = 1;

编译出来(清单 15-9)是一大串 cmp/jle/js/jns——六七次比较加跳转,全是在复刻 CPU 早就免费算好的东西⁸。笨,但纯 C,哪里都能跑。

路线二:汇编版 addTwo,四行解决Copy Anchor Link

addTwo:
    add  edi, esi      # x + y,CPU 顺手设好 OF
    seto al            # 把 OF 抄成 0/1,送进 al
    movzx eax, al      # 扩展成 int(返回值规格)
    mov  [rdx], edi    # *c = 和
    ret

核心是新指令 setcc(条件字节):cc 条件为真就把一个 8 位寄存器写成 1,否则写成 0; cc 的词汇表和条件跳转 jcc 完全同一张表(表 13-1 那 16 种)⁹。 所以 seto 读溢出标志、setc 读进位、setz 读零标志……一套语义两种出口: jcc 改 rip 走分支,setcc 留下 0/1 做值。「标志 → 数值」这座桥,就是把硬件特性 变成 C 可用返回值的机关。

作者加了两个风格注释:这个版本没用红区(他偏好完整栈帧,「这样就不必担心在更改函数 时使用栈」),也没存输入参数(参数寄存器本来就不需要保存)¹⁰。 行数对比:汇编版大约是编译器从 C 版生成的一半——但书里立刻自我提醒: 「程序的执行速度不仅取决于指令数量」,这个例子的真正价值是「不必使用比较复杂的 C 语言代码来获知溢出情况」¹¹。这段自我提醒值得背下来:拿指令数炫技是反模式。

路线三:内联汇编——把汇编嵌进 C 函数里Copy Anchor Link

把整个函数用汇编写,要付一次函数调用的价。更 surgical(外科手术式)的做法是 内联汇编(inline assembly):gcc 扩展,在 C 代码中间插一段汇编¹²。语法骨架:

asm (汇编语句
     : 输出操作数        /* 会被这段汇编修改的 C 变量, "=rm"(z) */
     : 输入操作数        /* 只读的 C 变量, "rm"(x) */
     : 会被改写的寄存器); /* clobbers: "rax", "rdx", "cc" */

三个要点,全是坑的位置¹³:

• %n 按序号引用 C 变量:n 从 0 数起,先输出后输入。例中 z=0、overflow=1、 x=2、y=3,所以 mov edi, %2 是把 x 装进 edi;
• 约束字母说玩法:= 表示写,r 表示放寄存器,m 表示放内存,+rm 表示读写都行; 编译器按约束决定把变量安置在哪;
• clobbers 是「我动过的东西」清单:凡被这段汇编显式改写的寄存器都要申报, cc 表示条件标志也被改过——不申报,编译器不知道它的变量还活着没。

清单 15-12 的溢出检查就嵌在 main 中间:add 必须在 asm 块里执行, 紧跟着 seto——如果在 C 里先加、再在 asm 里查,编译器可能在中间插入别的指令, 把标志改得面目全非¹³。这条「谁产生标志、谁就必须紧跟检查」的纪律,和第 13 章 「jcc 必须紧跟 cmp」是同一条。

书里的安全提示也照收:内联汇编和编译器生成的代码未必相安无事,用 -S 生成整函数的 汇编、通读一遍,确认没有阴差阳错¹⁴。

判断(我们的,不是书里的): 三条路线排个实用序:内联汇编最锋利但最危险 (和编译器的寄存器分配博弈),独立汇编函数最稳(走正常 ABI,工具链全认识), 纯 C 模拟最可移植(任何平台编译器都懂)。日常工程里的真实顺序往往相反: 先纯 C(够快、可移植),不够再独立汇编函数,内联汇编留给「非它不可」的少数场景 (如读取时间戳计数器、特定指令)。如果错,会错在: 在内核等禁用内联汇编的 环境里,或面对会大幅重排代码的优化器时,「独立函数」与「内联」的优劣要重排。

判断(我们的,不是书里的): 递归一段的 gdb 实录,是全书「用调试器学概念」 教法的最佳样本:没有画抽象示意图,而是让你在两个断点之间,亲手看着 rbp 降下去、 再看着它升回来。「栈帧会套娃」这个抽象,三次 i r rbp 就刻骨铭心了。 如果错,会错在: 依赖具体环境(地址、行号、编译器版本)的实录, 换机器复现时数字全变——读者可能把「地址值」当知识背,而真正的知识是「地址差值」 (每层 0x20)。

3. 作者的判断与证据Copy Anchor Link

4. 边界与局限Copy Anchor Link

• 只展示了「递归 vs 迭代」的浅层对比——尾递归优化(编译器把递归改循环)没提, 而开 -O2 后 gcc 确实会对尾递归出手;书中的账是 -O0 口径。
• mul/imul 只给了「够用」的一瞥,完整语义(单操作数双累加器形态等)推到第 16 章⁵。
• 内联汇编是 gcc 方言,Clang 大体兼容,MSVC 的语法完全不同(__asm 块); 书中语法别直接搬去别的编译器。
• 没有讲 C 标准库的信号量 feraiseexcept/<fenv.h>——其实标准 C 有一套浮点标志的 间接查询手段;书里「C 完全够不到」的说法对整数标志成立,对浮点标志略绝对。 (补充,不在书里,依据通用知识。)

5. 可带走的Copy Anchor Link

1. 递归 = 函数调自己 + 基准条件;机器层零新机制,每轮一个新栈帧;
2. 递归函数的参数寄存器必须先存栈,否则递归调用会把原值冲掉;
3. 调递归用小值 + gdb 双断点(调用处/返回处),看 rbp 的升降;
4. 读栈上窄变量注意小端序:4 字节值坐在 8 字节显示的「右侧第 5 字节」;
5. C 读不到整数溢出标志;「同号相加得异号」是纯 C 的模拟判据;
6. setcc reg 把条件标志抄成 0/1 放进 8 位寄存器,cc 词汇表与 jcc 同表;
7. 「标志 → setcc → movzx → 返回值」是把硬件特性递回 C 的标准三段桥;
8. 内联汇编 asm(语句 : 输出 : 输入 : clobbers),%n 从 0 数、先输出后输入;
9. 产生标志的运算和检查它的 setcc/jcc 必须紧挨,中间不容插入;
10. 指令条数 ≠ 速度;独立汇编函数最稳,内联汇编最锋利也最危险。

6. 原文地图Copy Anchor Link