对象符号解析与重定位

形式陈述

编译器与汇编器可以先生成尚不知道最终地址的代码。对象文件保存字节节、符号定义和“这里以后要补哪个地址”的重定位记录。链接器先决定布局与符号所指，再修改目标字段；把机器码字节简单拼接并不能完成这份接口。

本页定义一个教学对象格式和教学 ISA，不是 ELF 文件编码，也不是任何真实处理器 ABI。节内容是有限字节数组；地址为32位字节地址，整数按小端编码；节有名字、字节串和正的二次幂对齐。符号是 (名字,绑定种类,所属节,节内偏移)；仅支持 local 和唯一 strong-global，外部引用可以未定义。local 以“对象身份、名字”为键，global 以名字为键；同名局部可以共存，重复全局定义和最终未解析强引用都报错。

重定位为 (对象,目标节,字段偏移,种类,符号键,显式加数A)。字段地址记 P，解析所得符号绝对地址记 S。本模型仅有 ABS32：写 $S+A$ ，要求处于 $[0,2^{32})$ ；PCREL16：写 $S+A-P$ ，要求处于 $[-2^{15},2^{15}-1]$ 。先检查范围，再编码有符号二补数；截断模数不是合法溢出处理。

教学 CALL 指令为4字节：前2字节为操作码，后2字节为有符号位移；执行时把下一条指令地址 pc+4 压入调用栈，再跳到 pc+4+disp。因此重定位字段 P=pc+2，CALL 到符号 S 要用 A=−2，才有 disp=S−2−P=S−(pc+4)。P 不能一会儿指字段、一会儿指指令。

算法依次做四步。第一，按输入次序将同类节放到指定区域，位置更新为 align_up(cursor,a) 再加节大小，检查区间不重叠、不超32位地址空间。第二，验证符号偏移属于本节并建立 local/global 地址表。第三，验证每条重定位字段完整落在目标节内，字段互不重叠，符号可解析，值可编码；先把全部补丁算进临时列表。第四，全部成功才复制节字节并应用补丁，返回输出镜像。任何前三步失败都不改变输入对象或已完成镜像。

直觉

符号解决“找的是哪个函数或对象”，重定位解决“找到以后，按这条指令的格式把什么数写到哪里”。偏移、地址和编码字段各有自己的坐标系，最常见的错误正是把它们混成一个整数。

源名字解析以词法作用域连接声明，链接器以对象文件边界和可见性连接定义。两个模块各有 local scratch 是合法状态；若仅按字符串建一个全局大表，就会让其中一个局部对象错误覆盖另一个。

例子与边界

两对象的完整地址账本

.text 区域从0x1000开始，.data 从0x2000开始。对象 A 的 text 大小12、对齐4，data 大小8、对齐8；对象 B 的 text 大小8、对齐8，data 大小8、对齐8。按 A、B 次序布置，得到 A.text=0x1000，B.text=0x1010，中间4字节填充；A.data=0x2000，B.data=0x2008。

定义 A 的 global main 在 text+0、local scratch 在 data+4；B 的 global inc 在 text+0、global counter 在 data+0、local scratch 在 data+4。因此 main=0x1000，inc=0x1010，counter=0x2008；A.scratch=0x2004，B.scratch=0x200c。

补丁位置	类型、符号、A	计算	小端写入
A.text+2，P=0x1002	PCREL16 inc, −2	0x1010−2−0x1002=12	0c 00
A.data+0，P=0x2000	ABS32 counter, +4	0x2008+4=0x200c	0c 20 00 00
B.text+2，P=0x1012	PCREL16 main, −2	0x1000−2−0x1012=−20	ec ff

从 A.text 的 CALL 执行时，返回地址0x1004加12得到0x1010，恰为 inc。B.text 的反向 CALL 从下一地址0x1014加−20回到0x1000。这两个 CALL 用作地址接口探针，不作为会正常终止的互相调用程序；终点的执行器分别单步验证目标，不虚构“main 已正常退出”。

A和B的text节之间有四字节对齐填充；CALL字段P位于指令加二，位移从下一指令位置到目标inc — 布局、字段位置与执行PC分别标示

若忘掉4字节对齐空洞，误以为 inc=0x100c，会写入08 00，CALL 跳进填充或错误地址。若保留正确布局却取 A=0，会写入0e 00，跳到0x1012，正好落在 inc 指令内部。字段算式看起来只差2或4，却已经破坏可执行性。

装载重基址与动态绑定

静态链接完成不等于所有地址永久不变。若上例整份镜像的 text、data 都平移 Δ=0x3000，内部 PC 相对值中的 S、P 同加 Δ，所以12和−20不变；绝对指针必须从0x200c改成0x500c。若只搬 B 而不搬 A，内部 CALL 也须重算；“PC 相对”只对共同平移不变。

装载时动态绑定可以用一个明确的扩展：保留导入名 inc 与可写指针槽 G，装载器先按约定的模块查找次序找到 inc 的运行地址，例如0x7010，再将 G 写成0x7010；代码执行 call_indirect(load G)。本模型采用全部导入先绑定、成功后才允许程序入口运行的 eager 协议。模块缺失、重复强定义、地址越界都在运行前失败，不存在第一次调用时偷偷补丁的行为。

真实 ELF 的动态依赖、可见性、弱符号、版本、GOT/PLT、TLS 和处理器专用 relocation 远多于这个扩展。[1][2] 本页没有产生可交给系统 loader 的 ELF，教学 PCREL16 尤其不能冠以某个 RISC-V 或 x86 relocation 名称。动态符号搜索次序也是装载契约，不能假设任意平台都只选同名列表第一项。

推论与应用

布局不变量保证每个节有独立对齐区间，符号表保证每个允许引用有唯一目标，补丁检查保证每个改写字段合法且不与其他补丁冲突。提交之后，每个字段按所声明公式指向解析对象；CALL 再代入 ISA 方程，就得到正确目标地址。这是地址连接正确性，不证明函数参数与返回值遵守调用约定，也不证明源程序语义正确。

设节数 q、符号数 s、重定位数 r、输出字节及填充总量 B。字典操作期望常数时，布局与解析为 $O(q+s+r)$ ，输出复制为 $O(B)$ ；验证字段互不重叠若逐字节标记，额外为补丁总宽度 W，本模型 W≤4r。检查器为防御任意区域基址，先排序全部节区间再查重叠，额外花 $O(q\log q)$ ；它的 image 用稀疏地址字典仅存节字节，对齐填充另在 region_spans 中计量，尚未生成完整可装载字节文件。总空间含输出 $O(B)$ 、表与待提交补丁 $O(q+s+r)$ 。若使用排序检查任意宽字段，需另记 $O(r\log r)$ ，不能假定所有 overlap 检查都免费。

迁移任务：只把 B.text 改为对齐16。此时 B 仍在0x1010，所以全部答案不变；再把 A.text 增到20字节，B.text 到0x1020，A→B 位移变28（1c 00），B→A 变−36（dc ff）。把 inc 放到0x90000，PCREL16 越界，应在提交前失败；不能截成低16位。再令 B 的 local scratch 与 A 同名，两个地址依旧分别为0x200c与0x2004，全局解析不受影响。

双对象链接终点提供输入清单、补丁、错误模式以及可复算装载重基址任务；它与运行时回收任务共享文档入口，但使用独立状态机。

参考资料

[1] Xinuos，ELF Object File Format 4.3 DRAFT，2026-10-08查阅，§5.1–5.2 符号表与绑定；§6.1 Relocation Entry的字段偏移、显式/隐式加数及处理器专用类型。本页采用显式加数，但教学字段不是 Elf32_Rela 的文件布局。

[2] 同规范，§8 Dynamic Linking，§8.3 的 DF_BIND_NOW 与 §8.4 “Shared Object Dependencies”。用于界定装载前绑定和依赖解析；本页未实现该规范的完整动态链接器。

形式陈述 ​

两对象的完整地址账本 ​

装载重基址与动态绑定 ​

反向链接

形式陈述

两对象的完整地址账本

装载重基址与动态绑定