[链接器的世界-原理篇01] 地址不能总靠手填：链接器的演化之路

把一个写好的函数搬到另一处，函数内部对随它一起搬动的代码和数据的引用，也必须仍然找到正确的位置。今天，编译器和汇编器可以在目标文件中留下符号与重定位记录，由链接器完成修补。最早积累子程序库的机器上，还没有这套约定。

复用代码的愿望先于链接器出现。一个开平方例程已经验证正确，接到另一个程序后面，却可能因为地址改变而失效。要让“计算方法已经正确”真正意味着“可以被别的程序使用”，必须把代码做什么与代码放在哪里分开处理。

1949：把子程序搬进内存时，地址要跟着改

最早的程序是直接写机器指令的。一条"跳到第 120 号内存单元"的指令，里面写的就是 120 这个数字，这叫绝对地址。程序只有一段的时候，这不成问题。

问题出在复用上。剑桥大学的 EDSAC 在 1949 年 5 月完成了第一次计算，它的使用者很快积累了一批常用例程，比如开平方、打印数字，编成一个子程序库，谁需要就把它接到自己的程序后面。可一个子程序被接在不同程序后面时，它在内存里的起始位置每次都不一样，里面写死的那些地址就全错了。

David Wheeler 为 EDSAC 写的启动程序 Initial Orders 2 解决了这个问题。它只有 41 条指令，却同时充当了汇编器和加载器（把程序从纸带读进内存、准备好运行的程序）：子程序里的地址可以写成"相对于本例程起点的第几个单元"，加载时由它加上这个例程实际被放到的起点，库里的子程序就这样被一个接一个地装进内存（Clemson 大学的 EDSAC 资料）。

这件事今天有一个正式的名字，叫重定位（relocation）：代码在被放进最终位置之前，先按"相对于某个起点"来写地址，等真正的位置确定了，再把地址改成正确的值。今天的链接器，最核心的工作仍是同一件事。

可是在 EDSAC 上，程序员还得自己数单元号、自己写"相对第几个单元"。程序一长，光是数地址就足够让人出错。

用名字代替数字：汇编器与符号

下一步是让机器来数地址。汇编语言用助记符代替指令的二进制编码，用名字代替地址。程序员写下 loop: 来标记一个位置，在别处写 jmp loop，至于 loop 到底是第几个字节，交给汇编器去算。

一种基本实现是分两遍处理：第一遍计算指令和数据占用的空间，把每个名字对应的位置记进一张表；第二遍生成机器码，遇到名字就去表里查。真实汇编器还可能为变长指令、对齐和跳转距离反复调整布局，两遍是理解前向引用的起点。这张表叫符号表，表里的名字叫符号（symbol）。

今天的汇编源文件一般以 .s 结尾。打开一个看看，会发现里面除了 ret、mov 这样的 CPU 指令，还有大量以点开头的行：

1
    .section .text.add,"ax",@progbits   # 切到名为 .text.add 的区域，a 表示要装入内存，x 表示可执行
2
    .globl add                          # add 这个名字对外公开
3
add:
4
    leal (%rdi,%rsi), %eax              # x86-64 上前两个整数参数在 rdi、rsi，返回值放 eax
5
    retq
6
    .section .rodata                    # 切到只读数据区
7
msg:
8
    .asciz "hello"                      # 写入 h e l l o 五个字节和结尾的 0

.section、.globl、.asciz 这些以点开头的行是写给汇编器的伪指令，CPU 永远不会执行它们，它们决定的是"哪些字节被摆在哪里"。第 2 章会逐个拆解。

有了符号，单个文件里的地址问题解决了。可程序越写越大，所有代码都放在一个文件里，改一行就要把整个程序重新汇编一遍；几个人合写一个程序，也没法各写各的。

分开编译：目标文件与链接器的诞生

汇编器和随后出现的高级语言编译器，都开始允许把一个程序拆成多个文件分别翻译。1958 年发布的 FORTRAN II 加入了 SUBROUTINE、FUNCTION、CALL 这些语句，子程序可以单独编译了（Wikipedia: Fortran）。分开编译立刻带来一个新问题：main 里调用了 add，可编译 main 的时候，add 根本不在同一个文件里，编译器和汇编器都不知道它在哪。

解决办法是把翻译的结果先存成一个半成品，也就是第 0 章见过的目标文件（.o）。它里面已经有机器码；地址还定不下来的字段先保留占位值，未必全为零，同时附上两样东西：一张符号表，写明"我这里定义了哪些名字，又用到了哪些我没有的名字"；以及一批重定位记录，每一条都像一张便条，写明"这个位置要填某个名字的地址，按某种方式计算"。

再由一个专门的程序把所有目标文件读进来，给每个"我要用"找到对应的"我定义了"，这一步叫符号解析；然后安排好每一块代码的最终位置，再按便条把地址一一填上。这个程序在 IBM 的 OS/360 上叫 linkage editor，1966 年已经有正式手册（C28-6538-3）；在 Unix 上叫 ld¹，1972 年的 Unix 第三版手册里写的是 "ld -- link editor"，到 1979 年的第七版改称 "loader"（unix-history-repo）。这就是链接器。

这套结构几十年来基本没变。下面是一个最小的例子：

1
// main.c
2
int add(int a, int b);   // 只声明，定义在 add.c 里
3
int counter = 1;
4
int main(void) { return add(counter, 2); }

在 x86-64 Linux 上用 Clang² 编译，再用 GNU³ objdump⁴ 查看。以下输出为节选，反汇编的助记符拼写和排版可能随工具版本改变：

1
$ clang -O1 -c main.c
2
$ objdump -t main.o
3
0000000000000000 g     F .text   0000000000000010 main
4
0000000000000000 g     O .data   0000000000000004 counter
5
0000000000000000         *UND*   0000000000000000 add
6

7
$ objdump -d main.o
8
   0: 8b 3d 00 00 00 00     movl  (%rip), %edi
9
   6: be 02 00 00 00        movl  $0x2, %esi
10
   b: e9 00 00 00 00        jmp   0x10
11

12
$ objdump -r main.o
13
OFFSET           TYPE              VALUE
14
0000000000000002 R_X86_64_PC32     counter-0x4
15
000000000000000c R_X86_64_PLT32    add-0x4

符号表里，g 表示全局可见，F 和 O 分别表示函数和数据对象，.text、.data 是第 0 章见过的代码节和数据节；add 被标成 *UND*，意思是未定义。反汇编里，-O1 优化把最后那次调用变成了直接跳转 jmp（尾调用），(%rip) 表示以这条指令之后的下一条指令地址为基准寻址。机器码里有两处 00 00 00 00，正是两张便条所指的位置。

R_X86_64_PC32 这种便条要求填入"目标地址减去这 4 个字节自己的地址"，也就是相对距离。若引用的位置和目标一起平移，这个距离保持不变；这能免去这处引用的加载时修补，但不能据此断定整个程序已经位置无关。可 CPU 执行时，是以下一条指令的开头为基准来算相对地址的。在这两条指令里，这 4 个字节正好是指令的最后 4 个字节，两个基准差 4，所以加数是 −4；如果字段后面还跟着别的字节，加数就会跟着变。R_X86_64_PLT32 在这里的算法和 PC32 一样，名字里的 PLT⁵ 后面讲共享库时再说。第 4 章会把这类计算逐个手算一遍。

常用的子程序被打包成静态库（Unix 上是 .a 文件，其实就是一堆 .o 的归档）。通常按尚未解决的符号引用挑选成员，而非整库复制；显式请求整库链接等规则留到第 3 章展开。

链接器的基本工作就此成形。接下来几十年的变化，大多发生在两个地方：目标文件的格式，以及谁来读链接器的输出。

格式之争：从 a.out 到 ELF

早期 Unix 的目标文件和可执行文件都叫 a.out，意思是 assembler output。它的结构非常简单：一个固定 8 个 16 位字（16 字节）的文件头，记录代码（text）、已初始化数据（data）和未初始化数据（bss）各有多大，后面跟着代码和数据本身，再加上符号表和重定位信息（Unix 第六版 a.out(5) 手册）。这里的 bss 就是第 0 章那种只记大小、加载时清零的区域。

三个固定的区域很快就不够用了。调试信息放哪？只读的字符串常量放哪？版本和注释信息放哪？1983 年，AT&T 随 System V（AT&T 自己发行的商业版 Unix）推出了 COFF⁶ 格式，最重要的改进是允许任意多个带名字的节，也就是第 0 章 readelf⁷ 输出里 .text、.data 那样的单位，以后要加什么新东西，多加一个节就行。

1980 年代后期，AT&T（其 Unix 部门后来改组为 UNIX System Laboratories）和 Sun 合作开发 System V Release 4，为它设计了新的格式 ELF⁸。1993 年，由多家厂商组成的 TIS 委员会把它采纳为跨平台标准，1995 年发布了 ELF 1.2 规范（MaskRay: ELF 演化）。它最早叫 Extensible Linking Format，规范标题后来写作 Executable and Linking Format，今天通称 Executable and Linkable Format。Linux 在 1995 年 3 月发布的内核 1.2 之后，逐步从 a.out 切换到了 ELF。

ELF 有一个关键设计：同一个文件，给两类读者准备了两张目录。一张是节头表，列出所有的节，给链接器、调试器这些需要了解细节的工具看；另一张是程序头表，也就是第 0 章里内核读的那几行，它把若干节归成更粗的段，每一段只说明"把文件的这一段映射到内存的这个地址，给可读、可写或可执行的权限"，给负责运行程序的操作系统加载器看。可重定位目标文件通常只有节头表；常规工具链生成的可执行文件通常两张表都有，但执行时不必保留供离线工具使用的节头表。

格式统一了，可另一个问题越来越突出：每个程序都把自己用到的 C 库代码完整地拷贝一份。一台机器上跑着几百个程序，内存和磁盘里就躺着几百份几乎相同的 printf。

共享库：链接被推迟到运行时

让许多程序共用同一份代码，这件事在 Unix 之外早有人做过。1965 年，MIT 的 Project MAC、通用电气和贝尔实验室开始联合设计分时操作系统 Multics。分时的意思是许多用户同时在各自的终端前使用同一台计算机。1969 年秋天，Multics 在 MIT 开始对外提供服务（Multics History）。

在 Multics 里，每个用户有自己的地址空间（一个进程能访问的全部虚拟地址），程序和数据以段为单位映射进去。这里的段是 Multics 硬件寻址的基本单位，用段号加段内位移来定位，和 ELF 程序头里的段只是同名。一个过程（procedure，相当于一个子程序）可以被许多用户共享，可它在每个人的地址空间里分到的段号都可能不同，所以过程的代码里不能写死别的段的地址。Multics 给每个过程配了一块私有的链接段（linkage section），用到的外部地址都存在这里，代码只通过一个指向链接段的寄存器间接取用。第二个用户共享这个过程时，过程本身还是同一份，链接段另有一份（Saltzer 1978，MIT 托管的 OCR 版，页眉第 94 页，下同）。

链接段里的地址要等到第一次用到时才填。编译器输出过程 a 的机器码时，顺带输出一份链接段的原型。如果 a 要调用过程 b，原型里对应的位置放的是一个假指针，里面只有一个特殊的标志位和字符串 "b"。a 第一次调用 b，硬件在解释这个假指针时碰到标志位，就触发一次陷入（trap）：CPU 暂停当前指令，保存现场，把控制权交给系统预先指定的程序。在 Multics 里接手的这个程序叫动态链接器（dynamic linker）。它取出字符串 "b"，找到 b 所在的段，把假指针改写成指向 b 入口的真指针，再让 a 从中断处接着执行。此后 a 再调用 b，就只是一次普通的间接跳转，Saltzer 的原话是，之后的调用以"寻址硬件的速度"完成（at the speed of the addressing architecture，第 100 至 101 页）。他在另一处脚注里说，动态链接（dynamic linking）这个说法就用于 Multics，而 Multics 是少数真正实现了这一想法的系统之一（第 45 页）。

动态链接器找 b 的顺序也有讲究。它先查本地址空间的一张参考名表（reference name table），已经映射进来的过程都登记在表里；查不到，再依次到调用者 a 所在的目录、当前工作目录、系统和项目的库目录里找一个名为 b 的文件。这串查找顺序叫搜索规则（search rules），用户可以自己增删和调整（第 101 至 103 页）。由于引用只在第一次执行时才解析，一个 Multics 程序即使引用了根本不存在的例程，只要那段代码从没被执行，照样能正常运行（Multics 术语表 D 部分）。

1978 年，MIT 的 J. H. Saltzer 在讲义《Naming and Binding of Objects》（收在 Springer 的 Lecture Notes in Computer Science 第 60 卷，第 99 至 208 页）里，从命名的角度把传统的装入和 Multics 的做法放在一起讨论。他以 FORTRAN 为例：把一组分别翻译的子程序放到一起，这个动作当时叫装入（loading），它会建立唯一一个全局的上下文，把每个子程序和它的名字对应起来，子程序之间按名字的调用都在这个上下文里解析（第 14 至 15 页）。这里的上下文，可以理解成一张"哪个名字对应哪个对象"的对照表。讲义把完成这件事的程序称为上下文初始化程序（context initializer），并在脚注里补充，它也叫 loader、linker、link-editor 或 binder（第 32 页）。

从这个角度看，前面讲过的几件事是同一件事。符号解析就是在建这张表；静态库按需挑选成员，在讲义里是装入程序发现有名字解析不了，就去库里找同名的子程序补进来，补进来的子程序又可能引出新的名字（第 18 页）。表只有一张，两个各自独立写成的子程序如果同名，就会冲突，这就是后来链接器报的重复定义错误，第 3 章会细讲。Saltzer 还指出，装入的结果已经不再是子程序，不能再作为下一次装入的输入（第 15 页）。今天的链接器提供了 -r 选项，输出的仍是目标文件，可以再参与下一次链接。Multics 的动态链接则把建表推迟到每个名字第一次被用到的时刻，每个地址空间各建一张。

Multics 的做法依赖它的分段寻址硬件和那个会触发陷入的标志位。Unix 早期的程序都是静态链接的，共享库要到 1980 年代才出现在 Unix 上。

1987 年，Sun 的 Robert Gingell 等人在 USENIX 会议上发表了《Shared Libraries in SunOS》，第二年随 SunOS 4.0 发布（论文 PDF）。思路是：库代码不再拷进每个程序，而是做成独立的共享库文件（今天 Linux 上的 .so），程序启动时再装进内存，多个程序共用同一份。更早的 System V Release 3 也有共享库，但每个库都得事先分配一个固定的加载地址，库一多，地址就互相冲突。

这等于把一部分链接工作推迟到了程序启动时，也就是第 0 章加载期例子里的动态链接；相对地，在链接时就全部做完的叫静态链接。SunOS 上负责这部分工作的动态链接器叫 ld.so，今天的 Linux 也沿用这个名字。它在程序启动时找到需要的共享库，装进内存，再把那些直到此刻才知道的地址补上。

麻烦在于，共享库被装到哪个地址，每个进程可能都不一样。如果加载时把库代码里所有的地址都改一遍，那这份代码在每个进程里都被改得不一样，也就没法共享了。论文给出的解决办法沿用至今。

第一，库代码要写成位置无关代码（PIC⁹，Position-Independent Code）：不把随加载位置变化的绝对地址固定在共享指令中。同一模块内部可以使用相对寻址，跨模块引用则通过可单独修补的数据间接访问；具体指令序列取决于处理器。

第二，凡是必须用绝对地址的地方，比如引用另一个库里的变量，都改成去查一张表。这张表叫 GOT¹⁰（Global Offset Table，全局偏移表），其中需要运行时解析的项由动态加载器按相应规则填入。表是每个进程一份的数据，代码仍然可以共享。

第三，调用外部函数时先跳到一小段跳板代码，这组跳板叫 PLT（Procedure Linkage Table，过程链接表）。采用惰性绑定时，第一次调用的跳板把控制权交给 ld.so，由它查出函数的真实地址、改写跳板对应的表项，之后的调用就直接跳过去。这样，没被调用过的函数就不必在启动时解析，这种做法后来被称为惰性绑定。

拿它和 Multics 对照：Multics 靠硬件陷入发现某个引用还没解析，PLT 用一小段普通的跳板代码做同一件事；每个进程一份的 GOT，也和 Multics 每个用户一份的链接段相仿。于是这套办法在没有专门寻址硬件的机器上也能用。

System V Release 4 的动态链接沿用了 SunOS 4 的设计，随 ELF 一起成为今天 Linux 的基础。程序在运行中途还可以通过 dlopen 按需加载一个共享库，插件系统就是这么实现的。第 7 章会详细拆解这套机制。

这样一来，链接器的输出就不只是一份能直接运行的程序了，还包含一份写给另一个程序（ld.so）的说明：需要哪些库，哪些地址待填，按什么规则填。

格式统一了，共享库也就位了，还有一类数据一直没有像样的格式：调试信息。a.out 时代，它只能塞进符号表的特殊条目里，各家调试器各搞一套；ELF 给了它可以随意命名的节，可节里放什么、怎么放，还没有人说了算。

调试器需要知道"我在哪"

程序崩溃时，调试器要告诉你崩溃发生在哪个源文件第几行、当时的变量是什么值。可 CPU 执行的只是机器码，源码里的行号和变量名早在编译时就丢掉了。于是编译器开始额外生成调试信息：一批把机器码地址对应回源码位置、变量和类型的数据，放进专门的节里，由链接器一起带进最终的程序。

这类数据今天最通用的格式叫 DWARF¹¹。它最初由贝尔实验室的 Brian Russell 为 System V 的调试器 sdb 设计，名字是和 ELF 开的一个玩笑：ELF 是精灵，DWARF 是矮人（DWARF FAQ）。1993 年，由 AT&T 牵头的 Unix 厂商联盟 UNIX International 发布了 DWARF 2，此后一直演进到今天的 DWARF 5（2017 年）。

DWARF 2 新增了一部分叫调用帧信息（CFI¹²，Call Frame Information）的内容，它要解决的问题是：怎样从当前正在执行的函数，一层层找回调用它的那些函数。

函数调用必须让执行能够返回，但保存方式取决于处理器和生成的代码：x86 的普通 call 把返回地址压栈，另一些处理器先把它放进链接寄存器。函数还可能在栈上保存寄存器、局部变量和临时值；这次调用所使用的栈区域称为栈帧，叶函数也可能不分配新的栈空间。早年的编译器会让每个函数在开头把一个固定寄存器（x86 上的 rbp，叫帧指针）指向自己的栈帧，并把上一层的帧指针也存在旁边，形成一条链，调试器顺着链就能一层层往回找。后来为了多腾出一个寄存器给优化用，编译器常常省掉帧指针，这条链就断了。

CFI 用另一种方式回答同一个问题：它为每个函数里的每一段指令记下"此刻怎样恢复调用者的栈状态，以及返回地址和需要恢复的寄存器应从哪里取得"。这些规则被编码成一串很紧凑的指令，一条往往只占两三个字节。它们长什么样、怎样编码，第 8 章再一个字节一个字节地拆。

调试信息是给调试器看的，平时并不装进内存。可是到了 1990 年代，C++ 普及了，有一类程序在运行时也必须一层层往回找调用者：处理异常的时候。

异常：调用帧信息被搬进内存

C++ 程序 throw 一个异常后，运行时要从抛出点开始，沿着调用链一层层往回退，每退一层都要恢复出上一层函数的寄存器和栈顶，再看这一层有没有对应的 catch、有没有局部对象需要析构，这个过程叫栈展开（unwinding）。

1989 年，Stroustrup 和 Koenig 讨论过两种实现思路。一种在每次进入 try 时用 setjmp 保存现场，抛异常时用 longjmp 跳回去，实现简单，但即使从不抛异常，每次进入 try 都要付出代价。另一种是查表：平时什么都不做，等到抛出异常时，再根据当前指令地址去查一张表，找出该怎么展开。后者通常不在正常路径上执行异常登记操作，因而被称为零开销异常；表的空间、代码布局和优化限制仍有成本。它需要精确描述代码各处的展开状态（Kleckner 与 Majnemer, LLVM 2015）。

DWARF 的调用帧信息正好就是这张表。1997 年，GCC¹³ 的 Jason Merrill 实现了基于 DWARF 2 的异常支持：把调用帧信息改造一下，放进一个运行时会被装进内存的节，叫 .eh_frame（eh 是 exception handling 的缩写）。它和调试用的 .debug_frame 格式几乎相同，只做了几处为运行时服务的改动，比如允许代码地址采用相对编码，函数记录到公共记录的引用也使用相对距离，这样共享库被装到任何地址都不用再修改它，运行时拿到一条记录也不必知道整个节从哪里开始（MaskRay: Stack unwinding）。

.eh_frame 里，函数的代码范围对应展开记录；每条记录写明自己覆盖的地址范围和展开规则，一个函数也可能对应多条记录；许多函数共用的那部分规则单独存一份，各条记录指回去引用。这两种记录的格式，第 8 章细讲。

这套设计把"怎么退"和"要不要停"分给了两方。展开库只负责"一层层往回退"这件通用的事，至于"这一层要不要停下来处理这个异常"，交给每种语言自己的 personality 函数来判断，C++ 的叫 __gxx_personality_v0，Rust 的叫 rust_eh_personality。它要用到的 catch 表、析构动作表，放在另一个节 .gcc_except_table 里。这套分工由 1999 年起制定的 Itanium C++ ABI¹⁴ 规范确定下来。ABI（应用二进制接口）规定编译器、链接器和运行时在二进制层面怎么约定，比如参数放在哪个寄存器、栈怎么排、异常怎么传；这份规范由 HP、Intel、IBM、Red Hat 等公司共同参与，展开的具体流程也写在里面（Itanium C++ ABI: Exception Handling），第 8 章再讲。这个 ABI 最初为 Itanium 处理器制定，后来在大多数类 Unix 平台上被 GCC 和 Clang 采用（32 位 ARM 和 Windows 各有自己的一套）。

前面那个纯 C 的 main.c 明明没有异常，用 clang 编译出来为什么也有 .eh_frame？因为 x86-64 的 ABI 规范写明，要想在这个平台上成功展开调用栈，每个函数都必须提供 DWARF 格式的展开信息（x86-64 psABI）。C++ 的异常可能穿过 C 函数，调试器和性能分析工具也要回溯调用栈。2002 年起，GCC 在 x86-64 上默认为所有函数生成展开表。

.eh_frame 进了内存，又带出一个性能问题：抛异常时，怎样根据当前地址快速找到对应的那条记录？2001 年底，Red Hat 的 Jakub Jelinek 让 GNU 链接器在链接时就生成一张按地址排好序的索引，运行时直接二分查找（Ian Lance Taylor），细节见第 8 章。

在此之前，链接器对大多数节只是原样拷贝，再按便条打补丁；.eh_frame 则必须按格式逐条解析：拆出每一条记录，改写记录之间的指针，再额外生成一张索引。一旦链接器开始删除没用的函数（下一节就会讲到），对应的记录也得跟着删掉。

C++ 模板：同一个函数，出现在一百个目标文件里

C++ 还从另一个方向给链接器出了难题。模板和 inline 函数的定义写在头文件里，不同源文件都可能需要生成同一个函数实体的代码；是否真的生成独立函数体，还取决于使用情况和优化。这里的 inline 首先是允许满足条件的多处定义的语言规则，不等于保证把调用展开。std::vector<int>::push_back 可能出现在一百个目标文件里，按照"两个同名定义就报错"的老规则，这根本链接不起来。

GNU 工具链的第一个办法是 .gnu.linkonce 节：1996 年，Ian Lance Taylor 为 g++ 在汇编器和链接器里加入了这种特殊的节，同名的 linkonce 节只保留一份，其余丢弃。后来这个思路被标准化。COMDAT¹⁵（common data）这个说法在 Microsoft 的目标文件格式里早已存在，指"可以出现多份、链接时只留一份"的数据；1999 年为 IA-64 修订 ELF 规范时，基于 HP 的定义提出了 ELF 版的 COMDAT 节组（section group），2000 年写入 ELF 的通用规范。一个节组把一个函数的代码、数据和相关元数据捆在一起，同名的组在整个链接中只保留一组（gABI 修订记录）。

模板之外，大型程序里还有大量根本没人调用的函数。1998 年，GNU 链接器加入了 --gc-sections：从程序入口出发，顺着重定位把所有被引用到的节标记出来，没被标记的整块删掉。这里的 GC¹⁶ 是"垃圾回收"的意思，但回收的是链接时的节，不是运行时的内存。为了让删除的粒度足够细，编译器提供了 -ffunction-sections 和 -fdata-sections，让每个函数、每个全局变量各占一个节，前面那段汇编里的 .text.add，就是这样给 add 单开的节。

到这时，链接器已经习惯了按每个节的名字和属性做决定：留下哪些、丢掉哪些、怎样合并。2000 年代初，安全机制看中的也正是这一点。

安全：链接器开始替程序声明权限

2000 年代初，缓冲区溢出攻击泛滥。攻击者往栈上写入一段机器码，再设法让程序跳过去执行。硬件给出的对策是给内存页（操作系统管理内存的固定大小的块，x86-64 上通常是 4 KB）加一个"不可执行"的标志位，x86 上称为 NX 位，最早出现在 2003 年发布的 AMD64 处理器上，Intel 随后在自己的处理器里加入了同样的功能，叫 XD。

有了硬件支持，还得知道哪些程序真的需要可执行的栈。少数代码确实需要，比如 GCC 的嵌套函数扩展（在函数里再定义函数）会在栈上临时生成一小段代码；绝大多数则不需要。2003 年，Red Hat 在 Fedora Core 1 里推出了 Exec Shield（一组让程序默认使用不可执行内存页的内核补丁），同年 6 月，Jakub Jelinek 为 GNU 工具链加入了两样东西：每个目标文件里的 .note.GNU-stack 节，用它的标志声明是否需要可执行栈；常见的不需要情形是一个不带执行标志的空节；以及可执行文件里一个 PT_GNU_STACK 程序头，由链接器汇总所有输入的声明后写入，告诉内核和 ld.so 这个程序的栈要不要可执行。

早期兼容规则很保守：在一些 x86 GNU 工具链中，缺少声明会被视为可能需要可执行栈。这个默认行为与目标及链接器构建配置有关，并不是永久固定的 ELF 规则（GNU ld 选项说明）。本次 Ubuntu GNU ld 2.46 与 LLD¹⁷ 21.1.8 对同一份缺少声明的汇编都给出不可执行的 RW 栈。显式补上声明才能把程序意图与工具默认值分开。本章使用的 Linux GCC/Clang 会自动生成这个声明，用 objdump -h 看前面那个 main.o，节列表里就有一个大小为 0 的 .note.GNU-stack；漏掉它的往往是手写的汇编文件。

一年后，Jelinek 又加入了 RELRO¹⁸（relocation read-only）：程序启动、ld.so 填完 GOT 等需要重定位的数据之后，把这些页设为只读。如果再配合 -z now 让所有函数在启动时就解析完，连 PLT 用的那部分 GOT 也能设成只读，攻击者就没法靠改写 GOT 劫持调用了。

这些机制有一个共同点：链接器负责把所有输入的声明汇总成一个结论，写进输出文件，执行的是内核和 ld.so。

功能越来越多，程序越来越大，链接越来越慢。体积的大头往往还不是代码，是调试信息。用 clang 编译一个十行、用到 std::map 和 std::vector 的 C++ 文件（-O1 -g，一级优化并生成调试信息），机器码约 2 KB，调试信息约 200 KB。单个小文件会夸大这个比例，链接时重复的字符串也会被合并，但量级说明了问题。在 Linux 上，这些调试信息要由链接器完整地搬进输出文件。到 2000 年代中期，一个大型 C++ 项目链接一次要几十秒甚至几分钟，开发者每改一行代码都要等这么久。

二十年的速度之争

当时 Linux 上的链接器是 GNU ld。它建立在一个叫 BFD 的库之上，BFD 的目标是用一套代码同时读写几十种目标文件格式。名字的来历是个玩笑：Cygnus 公司的 David Henkel-Wallace 提议做这个库时，Richard Stallman 说这很难，他回了一句"BFD"（Big F***ing Deal，"有什么大不了"），"Binary File Descriptor"是后来补上的正式解释（BFD 手册）。通用性让 GNU ld 能处理几乎所有格式，也让它很难针对 ELF 做到最快，再加上基本是单线程，大项目上越来越吃力。不过它至今对链接器脚本支持得最完整。链接器脚本是一种描述"哪些节放到哪个地址"的配置文件，普通程序很少直接用到，操作系统内核和固件这类必须放在硬件规定位置上的程序却离不开它。

2006 年，Google 的 Ian Lance Taylor 开始写一个只支持 ELF 的新链接器 gold，2008 年并入 GNU Binutils（GNU 的二进制工具集，ld、汇编器 as¹⁹、objdump 都在其中）。它放弃了 BFD 的通用抽象，支持可选的多线程，在大型 C++ 项目上比 GNU ld 快好几倍。

2015 年，Google 的植山类（Rui Ueyama）和同事重写了 LLVM²⁰ 项目的链接器 lld，先是 Windows 格式的部分，同年 7 月把同样的设计用到 ELF 上（EuroLLVM 2016）。LLVM 是 Clang 和 rustc 共用的编译器基础设施。新的 lld 数据结构更简单直接，又快了一个台阶。

2020 年，植山类开始写 mold，2021 年 12 月发布 1.0。这一次，他把并行当成第一设计原则：从读文件、符号解析到写出，几乎每一步都拆成可以并行的工作。

速度的差别有多大？Rust 团队给过一组数据：在 Linux 上以调试模式构建命令行搜索工具 ripgrep，大约一半时间花在链接上；把链接器换成 lld 后，只改了少量代码的增量构建，链接时间缩短到约七分之一，端到端时间减少约四成（Rust Blog, 2025）。到 2026 年，植山类在 mold 的发布说明里写道，mold 链接几 GB 的程序只需要一两秒，很多时候和拷贝一个同样大小的文件差不多快，"困扰开发者几十年的链接慢问题，我们已经基本解决了"（原文：we have largely solved the problem of slow linking that has frustrated developers for decades，mold 2.42.1）。

走到今天

链接耗时显著缩短之后，兼容性、平台支持和维护成本仍决定新链接器能否成为默认值。

2025 年 2 月，Binutils 2.44 宣布弃用 gold，因为已经没人维护了。同年 9 月，Rust 1.90 在 x86-64 Linux 上把官方分发的工具链默认改用 lld。苹果在 2023 年的 Xcode 15 里换上了新链接器 ld-prime，到 Xcode 27 已经不能再切回旧的 ld64。苹果平台不用 ELF，用的是自家的 Mach-O 格式。mold 宣布从 C++ 改用 Rust 重写，3.x 版本的目标之一是成为 Linux 发行版的 /usr/bin/ld，也就是 gcc 和 clang 默认调用的那个链接器，为此第一步要补齐链接器脚本支持，让它也能链接内核和固件。今天大多数 Linux 发行版的 /usr/bin/ld 仍然是 GNU ld。

格式也还在演进。2024 年，LLVM 的开发者宋方睿（MaskRay）提出了一种更紧凑的重定位格式 CREL，能明显缩小目标文件，LLVM 已经支持，但还没进入 ELF 的通用规范（MaskRay: CREL）。2023 年的 Binutils 2.40 引入了 SFrame，一种只用于回溯调用栈的精简格式，比 .eh_frame 小得多，但不包含 personality 和语言专用数据，不能用来处理 C++ 异常。

2003 年定下的那条保守规则，二十多年后出了事。2025 年 1 月底发布的 glibc²¹ 2.41（Linux 上最常用的 C 标准库，ld.so 也是它的一部分）收紧了一条规则：不需要可执行栈的程序，再通过 dlopen 加载声称需要可执行栈的共享库时，会直接失败。随着各发行版陆续升级，一批 Steam 游戏、Discord、MATLAB、Julia 在新系统上打不开了（Phoronix）。其中不少是因为库里有手写的汇编文件漏了 .note.GNU-stack，链接器按照二十多年来的保守规则，在库里写下了"需要可执行栈"。glibc 随后不得不提供了一个绕过开关。

回头看这七十多年，链接器做的事情一直在变多：1949 年它只是把子程序的地址加上一个起点；后来它要给分开编译的文件配对名字，要为共享库准备 GOT、PLT 和写给 ld.so 的说明，要读懂 .eh_frame 并生成索引，要合并重复的模板实例、删掉无用的节，还要替整个程序汇总安全声明。这些职责适合放在链接阶段，是因为它能够汇集本次链接的输入，并决定这些输入如何组合；运行时才加载的插件和库仍在这个视野之外。

这些职责里最老的一项，从 EDSAC 起就没变过：先定下每段代码放在哪里，再把名字换成地址填回去。把布局固定、每个模块的大小视为已知，就能得到一个两遍模型：第一遍定位置、记下每个名字，第二遍查表改写。真实链接器还要处理会反过来改变布局的优化与限制，但这个模型已经足以描述地址修补的基本依赖。

真实目标文件还必须把这些依赖写成可交换的数据：哪些字节属于代码，哪些名字在此定义，哪一处地址需要等到链接时再填。第 2 章从 C 源码生成的汇编与 ELF 出发，逐项拆开这种表示。本章的文本模型用于手算。

练习

练习采用第 0 章的 x86-64 Linux 环境：普通 C/C++ 编译使用 gcc、g++，静态 musl²² 程序使用 musl-gcc²³，检查文件使用 GNU ar²⁴、nm²⁵、readelf、objdump、size。示例 包含下面各项文件观察实验的完整命令，每次建立新目录并保留产物。

观察。先编译只返回 42 的静态程序，同时让链接器打印实际读入的文件，并写出链接映射：

1
printf 'int main(void) { return 42; }\n' > hello42.c
2
musl-gcc -static hello42.c -o hello42 -Wl,-t,-Map=hello42.map > link-inputs.txt
3
cat link-inputs.txt

从链接追踪中找到实际参与链接的 musl libc.a，复制到当前目录。编译器驱动的文件查询与最终链接输入不能混为一谈：musl-gcc 可以通过附加配置选择 musl，而 -print-file-name=libc.a 的查询仍可能沿用 GCC 的其他搜索设置。-Wl,-t 显示的是链接器实际打开的文件，适合用于本题的成员抽取分析；也可以直接从这份追踪中确认库路径。

1. 用 file libc.a 和 ar t libc.a | head 看这个静态库。它本身是不是 ELF 文件？先从 ar t libc.a 找到提供 printf 的成员，再用 ar x libc.a 成员名 取出它（成员名取决于库的构建方式，以归档目录为准），再用 file 看，这个成员是 a.out 还是 ELF，是哪一种 ELF 文件？
2. ar t libc.a | wc -l 数一数库里有多少个成员。链接 hello42 时，链接器拉进了其中多少个？提示：给链接命令加上 -Wl,-Map=hello42.map，让 GNU ld 写出一份链接映射文件，看开头那一段 "Archive member included to satisfy reference by file (symbol)"。对照本章 Saltzer 讲义里 FORTRAN 装入程序查库的描述。
3. 用 readelf -h hello42 看 ELF 头。Magic 的前四个字节是什么？哪两个字段说明了这个文件遵循的 ABI，它们的值为什么写着 System V？Machine 一栏为什么写的是 AMD？

手算。下面使用一个独立的文本模型，用于说明两遍处理，不是 ELF 格式。机器有 500 个字，每个字是不超过四位的十进制数，千位是操作码，后三位是操作数。每个模块有定义列表 def（符号和它在本模块内的偏移，从 0 数起）、使用列表 use（本模块引用的符号，下标从 0 起）和正文。正文每个字带一个模式：I 原样保留；R 的操作数是相对本模块起点的地址，要加上本模块的基址（模块被放到的起始地址）；E 的操作数是使用列表的下标，要换成那个符号的绝对地址。模块按出现顺序紧挨着摆放，第一个模块的基址是 0。

1
module boot
2
  use main
3
  text
4
    R 1002
5
    E 2000
6
    I 42
7
end
8
module main
9
  def main 1
10
  use put msg
11
  text
12
    I 5000
13
    E 3000
14
    E 4001
15
    R 6000
16
end
17
module lib
18
  def put 0
19
  def msg 2
20
  use main
21
  text
22
    R 7002
23
    E 8000
24
    I 104
25
end

4. 第一遍：写出每个模块的基址和长度，以及符号表。
5. 第二遍：写出地址 000 到 009 每个字的最终值。读到 boot 的第二个字时，为什么没法当场填好它？
6. 把 lib 整个挪到最前面，哪些字的最终值会变，哪些不变？

对照与改坏。

7. 用本章的 main.c 和下面这个用到 std::map 的 C++ 文件，各编译两次，一次只加 -O1 -c，一次加 -O1 -g -c（Linux 上 C++ 用 g++；这一项观察目标文件，不要求 musl C++ 工具链）。用 ls -l 比较文件大小，用 size 比较代码和数据的大小，用 objdump -h 看多出了哪些节。代码变了没有？调试信息让文件大了多少？

   1
   // words.cpp
   2
   #include <map>
   3
   #include <string>
   4
   #include <vector>
   5
   
   6
   int count_words(const std::vector<std::string> &ws) {
   7
       std::map<std::string, int> freq;
   8
       for (const auto &w : ws) freq[w]++;
   9
       return static_cast<int>(freq.size());
   10
   }
   

8. 手写一个汇编文件，故意不加 .note.GNU-stack，再用一个 C 文件调用它，分别用 GNU ld 和 ld.lld（-fuse-ld=lld）静态链接。两个链接器写出的 GNU_STACK 有什么不同？给汇编文件补上声明再链接一次。

   1
   # answer.s
   2
       .text
   3
       .globl answer
   4
   answer:
   5
       movl $42, %eax
   6
       ret
   

   1
   // use.c
   2
   int answer(void);
   3
   int main(void) { return answer(); }
   

写代码。

9. 对第 4 到 6 题的手算模型，第一遍结束时至少要留下哪些信息，第二遍才不必回头再算？如果某个 E 字引用了谁都没定义的符号，怎样在报告中明确表达错误？这是一道模型设计题，不是仓库中的实现任务。

答案

以下输出全部来自 x86-64 Linux 本机：Ubuntu 26.04、GCC 15.2、GNU ld 2.46、Clang/LLD 21.1.8。成员数、尺寸与默认权限是本机观察值；示例 保留完整复现命令。

1
$ readelf -h hello42
2
ELF Header:
3
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
4
  Class:                             ELF64
5
  Data:                              2's complement, little endian
6
  Version:                           1 (current)
7
  OS/ABI:                            UNIX - System V
8
  ABI Version:                       0
9
  Type:                              EXEC (Executable file)
10
  Machine:                           Advanced Micro Devices X86-64
11
  ...

1
$ cat ifunc.c
2
static int impl(void) { return 7; }
3
static int (*resolve(void))(void) { return impl; }
4
int pick(void) __attribute__((ifunc("resolve")));
5
$ clang -c ifunc.c -o ifunc.o
6
$ readelf -h ifunc.o | grep OS/ABI
7
  OS/ABI:                            UNIX - GNU
8
$ file ifunc.o
9
ifunc.o: ELF 64-bit LSB relocatable, x86-64, version 1 (GNU/Linux), not stripped

参考

• EDSAC 与 Initial Orders 2：Clemson 大学 EDSAC 资料
• OS/360 Linkage Editor 手册：C28-6538-3 (1966)；Unix 历代手册：unix-history-repo
• ELF 的演化：MaskRay；ELF 通用规范：gABI
• Multics：Multics History、Multics 术语表 D 部分（dynamic linking）；Daley、Dennis，"Virtual memory, processes, and sharing in Multics"，CACM 11(5)，1968
• J. H. Saltzer，"Naming and Binding of Objects"，LNCS 60，Springer，1978，pp. 99-208，MIT 托管的 OCR 版（文中页码为该版页眉页码）
• Gingell 等，Shared Libraries in SunOS (1987)
• DWARF：DWARF FAQ、DWARF 5 标准
• 异常处理：Itanium C++ ABI、MaskRay: Stack unwinding、Ian Lance Taylor: .eh_frame_hdr
• x86-64 psABI
• ELF 头与 EI_OSABI：gABI: ELF Header
• 练习题型：NYU CSCI-GA.2250 Operating Systems，Hubertus Franke，Lab 1: Linker 规格书（学生仓库转存）；Allan Gottlieb 的原始版本（转存）
• 链接器的速度：Rust Blog, 2025、mold 2.42.1 发布说明
• glibc 2.41 可执行栈事件：Phoronix
• John R. Levine，《Linkers and Loaders》；Ian Lance Taylor，Linkers 系列