链接器是如何一步步发明出来的？

作者：東方幽静響
链接：https://zhuanlan.zhihu.com/p/1918306243627442436
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在计算机编程的早期年代，你面临一个挥之不去的的噩梦。。。

你找了一个刚刚运行成功的程序仔细看了看：

; main.asm - 主程序
start:
    ; 初始化
    mov cx, 10
    mov dx, 20

    ; 调用math.asm中的add函数
    call 0x1234  ; 这里的0x1234是add函数在内存中的绝对地址

    ; 退出
    mov ax, 0
    int 21h

; math.asm - 数学函数模块
add:
    ; 加法函数
    mov ax, cx
    add ax, dx
    ret

你一眼就注意到main.asm中的那些数字了，0x1234和0x5678。

这些是函数在最终内存中的绝对地址，也是所有程序员的噩梦，因为这些地址都是程序员手动计算出来的！

例如，如果math.asm被加载到内存地址0x1000，而add函数在模块内的偏移是0x234，那么add的绝对地址就是0x1234。

这个过程不仅繁琐，而且极易出错，更糟糕的是维护问题。

牵一发而动全身

你清楚地知道，如果程序员在math.asm的开头添加了一个新函数，会发生什么！

; math.asm - 修改后
new_function:  ; 新增的函数
    ; 一些代码
    ret

add:  ; 位置改变了！
    mov ax, cx
    add ax, dx
    ret

这个看似无害的修改会导致add函数的位置发生变化！它的偏移量增加了，绝对地址也随之改变。现在，main.asm中的call 0x1234指令将跳转到错误的位置！

程序员必须重新计算add函数的新地址并修改所有调用add的地方。

如果程序有数十个模块，数百个函数调用，这个过程将变成一场噩梦，每次修改代码，都可能引发一连串的地址更新工作。

于是你的开始思索，需要一种机制，能够自动处理这些地址绑定，让程序员们专注于代码逻辑而非地址计算，为实现这种机制就决不能在程序中使用绝对内存地址！

穷则思变

不使用内存地址使用啥呢？

此时你想到当你找喊一个人的时候直呼其名而不是喊这个人的经纬度坐标，对了！这里也可以使用名字而不是地址来引用函数和变量，想到这里**符号（Symbol）**概念诞生了。

是啊，为啥要用内存地址硬编码，程序员可以使用符号啊：

; main.asm - 使用符号名
start:
    ; 初始化
    mov cx, 10
    mov dx, 20

    ; 使用符号名而非硬编码地址
    call add      ; 使用符号名"add"而非0x1234

    ; 退出
    mov ax, 0
    int 21h

这种方法的核心思想是：程序员只需关心名字（如add、print），而不必关心这些函数最终在内存中的确切位置。

这是一个巨大的抽象飞跃！

你设计的符号概念带来了2个关键优势：

减少错误：不再需要手动计算和更新地址，消除了一大类潜在错误。
简化维护：当函数位置变化时，只需保持符号名不变，调用代码无需修改。

最重要的是，符号为自动化解决依赖关系奠定了基础。

遗留问题

符号概念是很优雅，但问题是：如何确定符号名最终的内存地址呢？

显然这次需要有一个能够自动确定符号最终内存地址的工具，让程序员彻底摆脱地址计算的负担，到底该怎么做到呢？

要达到这个目的就不能让编译器直接生成机器码，而是把这个过程拆成两步：

编译器处理各个模块，但不必关心跨模块引用
根据各个模块提供的信息来确定符号最终的内存地址并合并所有的模块为一个最终可执行文件

就这样在你的设想中你把整个编程过程拆成了两步，第一步是编译、第二步你将其称之为链接，link。

第二步中各个模块提供的信息还是比较模糊，这个信息是什么，该怎么提供？

目标文件的诞生

既然编译器不直接生成最终的机器码，那么就需要一种文件来承接这一阶段编译器的输出，这个用来记录编译器第一阶段输出的文件就是所谓的目标文件，Object File。

这个文件包含机器码，但不去确定引用的外部符号的内存地址：

call print

你把所有这样的符号收集起来记录来目标文件中，这就是所谓的重定位表（Relocation Table），标记代码中需要在链接时填充正确地址的位置，这就是所谓的重新定位，重定位。

同时这个文件记录模块定义的所有符号（函数、变量）及其相对位置，这就是所谓符号表（Symbol Table）：记录模块定义的所有符号（函数、变量）及其相对位置。

它们可能长这样：

-- main.obj --

代码段：
  偏移 0x03: mov dx, 20
  偏移 0x06: call ???  (需要重定位，调用add)
  偏移 0x0B: mov bx, ax
  偏移 0x0D: call ???  (需要重定位，调用print)

符号表：
  start -> 偏移 0x00 (本模块定义,"我能提供什么")

重定位表：
  偏移 0x07: 需要add的地址  
  偏移 0x0E: 需要print的地址

未解析引用：
  add   (外部符号，“我需要什么”)
print (外部符号，“我需要什么”)

目标文件的意义

目标文件的出现是一个关键突破，因为它：

分离了编译和链接：编译器只需关注单个模块的翻译，不必处理跨模块引用。
明确记录了依赖关系：每个模块清楚地表达了"我提供什么"（符号表）和"我需要什么"（未解析引用）。
为自动化链接提供了数据结构：重定位表明确标记了需要修正的地址位置。

现在，你的任务就变得明确了：读取多个目标文件，解析它们的符号和依赖关系，然后将它们正确地"链接"在一起。

但如何实现这个链接过程？很明显，你需要实现两个核心算法：符号解析和重定位。

符号解析与重定位

符号解析解决一个基本问题：将每个模块的"需求"与其他模块的"供给"匹配起来。

具体来说，你需要：

收集所有符号：遍历每个目标文件的符号表，建立一个全局符号字典，记录每个符号的定义位置。
检查未解析引用：对每个模块的未解析引用，在全局符号字典中查找其定义。
处理冲突和错误：如果一个符号有多个定义（冲突）或没有定义（未解析），生成适当的错误信息。

如果所有未解析引用都能在全局符号表中找到对应的定义，符号解析就成功了。否则，你的算法会生成一个错误，这就是后来的程序员熟悉的"undefined reference to..."。

符号解析解决了"符号供需匹配"问题，重定位的任务是：确定每个模块和符号在最终内存中的确切位置。

重定位过程包括：

内存布局规划：决定各个模块在最终内存空间中的排列顺序和基址。
地址计算：根据模块基址和符号在模块内的偏移，计算每个符号的最终绝对地址。
填充重定位条目：遍历每个模块的重定位表，将正确的地址填充到代码中的相应位置。

符号解析和重定位这两个步骤解决了模块化编程中最核心的问题：如何让分散在不同文件中的代码片段正确地找到并调用彼此。