ICS07 链接

type

status

date

slug

summary

链接 Linking

链接是将编译后的目标文件合并成可执行程序的关键步骤。它主要涉及两个关键任务：符号解析和重定位。符号解析处理不同文件中符号的引用和定义，而重定位调整代码和数据在内存中的位置，以确保程序的正确执行。

回顾编译过程

GCC (GNU Compiler Collection) 在编译工具链中充当编译器驱动程序的角色，协调不同的工具完成编译任务。典型的编译过程包含以下步骤：

预处理 (cpp): 预处理器处理源代码中以 # 开头的指令，例如宏定义、条件编译和文件包含。它生成预处理后的源代码文件 (.i 文件)。可以使用 gcc -E 命令执行预处理。

gcc -E source.c -o source.i

编译 (cc1): 编译器将预处理后的源代码翻译成汇编语言，生成汇编文件 (.s 文件)。

gcc -S source.c -o source.s

汇编 (as/gas): 汇编器将汇编代码转换成机器指令，生成可重定位的目标文件 (.o 文件)。目标文件包含不同的代码和数据节。

gcc -c source.c -o source.o

链接 (ld): 链接器将多个目标文件以及必要的库文件合并成可执行文件。

gcc source.o -o executable

链接的动机

链接的必要性源于模块化和效率的需求：

模块化: 链接支持将程序分解成独立的模块进行开发和维护。这提高了代码的可重用性和可管理性。

效率: 链接在时间和空间上都带来了效率提升。

时间效率: 允许并行编译不同的模块，从而减少编译时间。修改某个模块后只需重新编译该模块并重新链接，无需重新编译整个程序。

空间效率: 静态链接情况下，可执行文件只包含实际使用的库函数，减少了文件大小。动态链接则允许多个进程共享内存中的库代码，进一步节省内存和磁盘空间。

链接器的任务

链接器主要执行以下两个任务：

1. 符号解析

程序中的符号，例如全局变量和函数名，需要在链接过程中进行解析。每个目标文件都包含一个符号表，记录了其中定义和引用的符号。链接器使用这些符号表来解析符号引用，将每个符号引用与其定义关联起来。

2. 重定位

链接器将各个目标文件的代码和数据节合并到一起，并为它们分配最终的内存地址。这需要修改代码和数据中对符号的引用，将它们指向正确的内存位置。这个过程称为重定位。

目标文件

主要有三种类型的目标文件：

可重定位目标文件 (.o): 包含代码和数据，需要与其他可重定位文件链接成可执行文件。

可执行目标文件 (.out 或其他特定于系统的扩展名，如.exe): 可以直接加载到内存中执行。

共享目标文件 (.so 在 Linux 上, .dll 在 Windows 上): 用于动态链接，可以在程序加载或运行时动态加载和链接。

ELF文件格式

ELF (Executable and Linkable Format) 是一种通用的目标文件格式，用于表示可重定位文件、可执行文件和共享目标文件。ELF 文件包含以下主要部分：

ELF 头: 包含文件的基本信息，例如文件类型、目标体系结构、入口点等。

程序头表/段头表 (Segment Header Table, 只存在于可执行文件中): 描述程序加载到内存中的段布局。

节 (Sections): 包含代码、数据、符号表等信息。

节头表 (Section Header Table): 描述文件中各个节的信息。

ELF 文件中重要的节包括：

.text: 代码段。

.rodata: 只读数据段。

.data: 已初始化的数据段。

.bss: 未初始化的数据段。

.symtab: 符号表。

.rel.text: 代码重定位信息。

.rel.data: 数据重定位信息。

在可执行文件中，程序头表将文件分为几个片（chunk），分别映射到不同的连续内存段。

将文件的代码部分（包含ELF头、程序头、.init, .text, .rodata）映射到内存中的可读可执行段（r-x）

将文件的数据部分（.data, .bss）包含映射到内存中的可读可写不可执行段（rw-）

剩下的.symtab, .debug, .line, .strtab和节头表不被加载到内存中，仅用于调试。

程序头表存储各个片在文件中的偏移量off、要被分配到的内存地址vaddr、对齐要求align、段大小filesz/memsz、运行时访问权限flags

程序移动到内存时需要遵循对齐规则：。其原因与字节在内存中的组织有关，便于传送。

符号解析

符号表

每个可重定位目标模块都包含一个符号表，其中包含了该模块中定义和引用的符号信息。符号的类型包括：

全局符号（Global）: 可以在其他模块中访问的符号。

外部符号（Extern）: 在本模块中引用但在其他模块中定义的符号。

局部符号（Local）: 只能在本模块内部访问的符号，例如静态函数和静态变量。

符号表中的每个条目包含以下信息：

name: 符号名称在字符串表中的偏移量。

type 和 binding: 符号的类型 (函数或数据) 和绑定属性 (局部或全局)。

section: 符号所在的节。

value: 符号在节内的偏移量或绝对地址。

size: 符号的大小。

特殊符号和节

伪节: ABS (存放绝对符号), UNDEF (存放未定义符号), COMMON (存放未初始化全局变量)。

将未初始化的全局变量放在COMMOM节中而非.bss中的原因见后文“强符号和弱符号”。

符号解析规则

链接器按照命令行中指定的顺序扫描目标文件和库文件，并进行符号解析。其规则如下：

维护一个未解决符号的集合。

扫描每个目标文件，将其中定义的符号添加到已解决符号集合中，并将未解决符号集合中已解决的符号移除。

扫描静态库文件，只将包含未解决符号定义的目标文件添加到链接过程中。

如果扫描所有文件后仍有未解决符号，则链接器报错。

静态库（archive libraries） 使用archive文件，把每个库函数独立成一个.o模块，然后封装存放在.a文件中，维护一个头来描述各个成员模块的大小和位置。链接时，只需从archive文件中提取出使用的函数所在的目标模块进行链接，而不必与整个静态库进行链接。静态库减少了对磁盘和内存的占用，但是仍然会产生不必要的拷贝。

在链接过程中，库的顺序会影响符号解析的正确性。链接器按命令行中的顺序处理库，当遇到未解析的符号时，只会在后续的库中查找。若被依赖的库出现在依赖它的库之前，可能导致符号无法解析。

假设有两个静态库 libfoo.a 和 libbar.a，以及一个主程序 main.c：

libbar.a 定义函数 bar()。

libfoo.a 定义函数 foo()，而 foo() 内部调用了 bar()。

main.c 调用 foo()。

首先，编译库和目标文件：

链接时，正确顺序应该是先 libfoo，后 libbar

链接器工作时：

解析 main.o，发现未解析的 foo()。

查找 libfoo.a，找到 foo()，但发现 foo() 需要 bar()。

继续查找 libbar.a，找到 bar()，解析成功。

链接的错误顺序：先 libbar，后 libfoo

链接器工作时：

解析 main.o，发现未解析的 foo()。

查找 libbar.a，无 foo()，跳过。

查找 libfoo.a，找到 foo()，但 foo() 需要 bar()。

后续已无库可查，报错：undefined reference to 'bar'。

原因分析

链接器按从左到右的顺序处理库。当处理 libfoo.a 时，若需要的 bar() 定义在尚未处理的库中（如 libbar.a 在右侧），可以正常解析。若 libbar.a 已被处理（在左侧），链接器不会回溯查找，导致 bar() 未定义。

结论

被依赖的库应放在依赖它的库之后。调整顺序确保每个未解析的符号能在后续库中找到。对于复杂依赖（例如库A和库B互相调用），可多次列出库（如gcc main.c -lA -lB -lA -L.）或使用链接器选项（如 --start-group 和 --end-group）强制重复扫描。

强符号和弱符号

强符号: 已初始化的全局变量和函数名。

弱符号: 未初始化的全局变量。

链接器处理强弱符号的规则如下：

多个强符号定义同一个符号：链接错误。

一个强符号和多个弱符号定义同一个符号：使用强符号。

多个弱符号定义同一个符号：随机选择其中一个 (通常是第一个)。

因此，当编译器遇到文件A中未初始化的全局变量var时，它不知道之后要与A链接的其他文件中有没有对var 的强定义。例如，如果文件B中定义了已初始化的全局变量var （这是一个强符号），则应该使用文件B中的定义；但如果没有文件再定义var ，应该使用文件A中的定义。因此，编译器会暂缓对var 的解析，而是将其放入COMMON节中，等待链接器定夺。

重定位

重定位是链接过程中的关键步骤，它修改代码和数据中对符号的引用，使它们指向正确的内存地址。

重定位条目

可重定位目标文件（.o）包含重定位条目，用于指示需要修改的代码或数据位置。重定位条目包含以下信息：

offset: 需要修改的位置相对于节起始地址的偏移量。

type: 重定位类型。

symbol: 被引用的符号。

addend: 一个常量加数。

重定位类型

常见的重定位类型包括：

R_x86_64_PC32: 32 位 PC 相对地址。

R_x86_64_32: 32 位绝对地址。

重定位算法

重定位算法根据重定位类型计算新的地址，并将其写入需要修改的位置。

以下示例基于x86-64小型代码模型（代码和数据总大小小于2GB），使用两种重定位类型：R_X86_64_PC32（PC相对地址）和R_X86_64_32（绝对地址）。

1. `R_X86_64_PC32`：PC相对地址

例如我们有以下汇编代码：

那么编译器会生成以下重定位条目：

OFFSET=0x1：重定位条目位于 .text 段的偏移 0x1 处（因为call指令对应的机器码只占用一个字节，之后有四个字节存放着目标地址）。

TYPE=R_X86_64_PC32：需要计算 sum-4 的PC相对偏移。

链接器完成符号解析后，先取定各段的运行时地址，再进行重定位。假设.text 段的起始地址为 0x400400，而 sum 符号的地址为 0x400420

链接器根据以下原则进行重定位： *(ADDR(sec)+offset) = (unsigned)(ADDR(symbol)+addend - (ADDR(sec)+offset)) 其中，ADDR(sec) 是重定位目标所在的节的起始地址，在这里是 .text 节的起始地址 0x400400 ；offset 是重定位目标相对 .text 段的偏移 0x1 ；ADDR(r.symbol) 是链接器取定的目标符号所在的地址，在这里是sum 的地址 0x400420 ；addend 是常量加数。

ADDR(sum) + addend = 0x400420 - 0x4 = 0x40041C 
 ADDR(sec) + offset = 0x400400 + 0x1 = 0x400401

因此应填充的值应为 0x40041C - 0x400401 = 0x1B

call 指令的操作数字段会被替换为 0x1B（32位有符号偏移）。

在x86-64架构下，使用 R_X86_64_PC32 重定位类型调用函数时，addend经常是-4

在 x86-64 中，callq 指令用于调用函数。这条指令的长度是5字节，由1字节的call指令机器码0xE8和4字节的地址偏移量组成。它将返回地址（调用指令之后指令的地址）压入栈中，然后跳转到目标地址。

R_X86_64_PC32 重定位类型使用 PC 相对寻址。这意味着目标地址是相对于调用指令之后指令的地址 (也就是返回地址) 计算的。由于重定位条目指向的是4字节地址偏移量，而 PC 相对寻址的基准是call指令的下一条指令的地址（也即PC的值），比前者多了4字节。为了抵消这个 4，addend 被设置为 -4。这样，最终计算出的目标地址就是正确的函数地址。在上面的例子中，标注出重定位之后的指令和对应地址：

程序执行到call 指令时，将此时的PC值/%rip值0x400005 加上4字节的偏移量0x1B ，得到要跳转到的地址0x400020 ，说明我们关于重定位条目的计算是正确的。

2. `R_X86_64_32`：绝对地址

假设我们有以下汇编代码：

那么编译器会生成如下重定位条目：

OFFSET=0x1：重定位条目位于 .text 段的偏移 0x1 处（即 mov 指令的操作数字段）。

TYPE=R_X86_64_32：需要计算 array+4 的绝对地址。

假设链接器已经取定了运行时地址：.data 段起始地址为 0x600000； array 符号地址为0x600000（位于 .data 段起始处）。链接器将依据以下公式进行重定位：

*(sec+offset) = (unsigned)(ADDR(symbol)+addend)

而 ADDR(array) + addend = 0x600000 + 0x4 = 0x600004

因此 mov 指令的操作数字段会被替换为 0x600004（32位绝对地址）。

R_X86_64_PC32 一般用于指令跳转或PC相对寻址（如 call、jmp、lea）。偏移量动态计算，与代码位置无关，适用于位置无关代码（PIC）。

R_X86_64_32 用于直接访问全局变量或静态数据的绝对地址。地址在链接时固定。

加载（Load）可执行文件

在你通过命令行运行ELF文件时，操作系统要先启动加载器对该文件进行加载（load）。

首先，操作系统为加载器启动一个新的进程。之后，加载器将程序复制到内存。具体而言，将不同的段（segments）放到进程虚拟地址空间（详见第九章）的对应位置。之后，加载器初始化程序条件，如寄存器值、程序计数器值等。这一切执行完毕后，进程跳转到该ELF文件的入口，开始执行（Execute）。

_start 是程序的入口点，由链接器设置。它负责初始化C程序的运行时环境，然后调用__libc_start_main，之后再调用main 函数。

进程的运行时内存（也即虚拟地址空间）由低到高为：只读代码段、读写数据段、堆、共享库内存映射区域、用户栈、内核内存（内核是操作系统驻留在内存的部分）

链接的演化

早期的链接方式直接将所有目标文件合并。这种“朴素链接”存在明显的缺陷，具体而言，为了使用户源代码可以调用标准函数，主要有两种方法：

方法一：由编译器直接转换标准函数：对于拥有大量标准函数的 C 语言来说，这种方法效率低下且不切实际。

方法二：库文件链接：一些标准函数被封装在一个库文件中（如libc），与用户源代码汇编后的文件进行链接。然而，这使得每个程序都会保留标准库的完整副本，造成磁盘和内存空间的浪费。同时，修改标准函数需要重新编译整个库，并重新链接所有使用该库的程序。

为了解决资源浪费问题，引入了静态库（archive libraries）。静态库将每个标准函数编译成独立的 .o 模块，并封装到 .a （archive）文件中。链接时，只提取程序需要的目标模块。虽然静态库减少了磁盘和内存占用，但仍会生成不必要的副本，并且修改库函数仍然需要重新链接所有相关程序。

现代操作系统采用共享库（shared libraries）和动态链接（dynamic linking）技术。共享库（Linux 中的 .so 文件，Windows 中的 .dll 文件）可以在加载时或运行时与程序链接。磁盘和（物理）内存上均只有一个共享库副本，多个程序共享（物理）内存中的代码段，从而节省了磁盘和内存空间。

我们将在第九章中学习虚拟内存相关的知识。你将知道，程序可见的运行时内存是“虚拟内存”，程序对内存的读写需要经过MMU的地址映射，也即将虚拟地址映射为物理地址。每个进程都有独立的虚拟内存空间，操作系统可以只在物理内存中保留一份共享库的副本，而将不同进程的一部分虚拟内存空间均指向物理内存中的该副本。这部分虚拟内存空间也即运行时内存的“共享库映射区域”。

通过以下命令行指令来创建共享库 .so 文件：

使用共享库来编译主程序：

lmath 指示链接器使用 libmath.so 库，L. 指定库的搜索路径为当前目录。

动态链接 (Dynamic Linking)

动态链接分为两种：加载时链接和运行时链接。

加载时链接 (Load-time Linking)

程序首次加载时进行动态链接。在（广义）编译中，（静态）链接器 ld 将共享库的重定位和符号表信息复制到可执行文件中。加载器加载程序时，检测到 .interp 节，其中包含动态链接器 (ld.so) 的路径。加载器调用动态链接器，将程序与共享库的代码和数据进行完全链接，最后将控制权交给程序。

运行时链接 (Run-time Linking)

程序运行时，每次需要使用库函数时才进行动态链接。这种方式允许在运行时修改库函数，方便维护长期运行的程序，例如 Web 服务器。更新软件时，只需更新共享库即可。缺点是每次调用函数都需要链接，略微降低了性能。

C 语言提供了以下几个函数来实现运行时链接：

void *dlopen(const char *filename, int flag)：加载和链接共享库（dynamic library open)

flag参数可以是以下宏的一个或几个，使用按位或 | 进行连接。（RTLD：Run Time Linking Dynamics）

RTLD_LAZY: 即仅在需要时解析符号（如链接函数）。这样可以加快程序的启动速度，因为不需要在加载时解析所有符号。
RTLD_NOW: 立即解析所有的符号，在库加载的时候就进行。这有助于在运行时尽早捕获任何未解析的符号错误。
RTLD_GLOBAL: 使得该库中的符号对于随后加载的所有库可见。这可以用于跨库共享符号，但是可能引发符号冲突。
RTLD_LOCAL: 这是默认行为，即将符号的可见性限制在加载该库的上下文中，后续加载的库不能访问这些符号。

dlopen返回一个void*型句柄（把手？），可以理解为指向共享库的指针。若出错则返回NULL

void *dlsym(void *handle, char *symbol)：解析handle指向的共享库中symbol对应的符号，若没有则返回NULL

int dlclose(void *handle)：关闭并卸载共享库。成功返回0，失败返回-1. 也可以在dlopen时可以选择宏RTLD_NODELETE，使dlclose不会卸载共享库。

const char *dlerror(void)返回最近发生的错误。

将以上函数组织起来，得到一份运行时链接的模板：

动态链接器的工作流程

查找共享库：基于环境变量 (LD_LIBRARY_PATH) 和系统默认路径，找到共享库在磁盘中的位置。

内存映射：将共享库的各个段映射到进程的虚拟地址空间（“共享库映射区域”）。.text 段在多个进程间共享物理内存页，.data 和 .bss 段使用写时复制 (Copy On Write, COW) 机制。

符号解析和重定位： 解析共享库中的符号，并执行重定位，使进程能够调用共享库提供的函数和访问变量。

位置无关代码 (PIC)

位置无关代码 (PIC) 可加载到内存的任意位置，而无需修改代码段。共享库必须编译成 PIC 格式。PIC 的核心要求：在不修改代码段的前提下，代码能够访问任何全局目标（过程/变量）。

为了实现 PIC，编译器在数据段开头维护全局偏移表 (GOT)，每个全局目标占用一个条目。加载时，动态链接器重定位 GOT 中的每个条目，使其指向正确的绝对地址。每个引用全局目标的模块都有自己的 GOT。

为了实现函数调用，GNU 使用延迟绑定 (lazy binding)，将过程地址的绑定推迟到第一次调用时。这避免了加载时不必要的重定位。如果模块调用共享库中的函数，则它拥有自己的 GOT 和过程链接表 (PLT)。PLT 是代码段的一部分，每个条目包含跳转到 GOT 对应条目的指令。GOT 初始状态未设置，第一次调用函数时，PLT 中的代码会调用动态链接器来解析函数地址并更新 GOT。

这部分内容授课时未提到，也不在考试范围内；笔者因为负责回课而总结了以下内容，比较杂乱，敬请谅解。

为了生成PIC代码，我们需要处理目标模块中，代码对全局目标（包括全局过程和全局变量）的访问：（以下内容只考虑加载时链接）

目标模块对相同目标模块的引用无需处理，可以使用PC-relative寻址方式，由静态链接器重定位。

为了使PIC代码访问其他目标模块的全局变量，编译器需要让数据段.data和代码段.text的距离总维持不变，并在数据段开头维护全局偏移表（Global Offset Table, GOT），每个全局变量在其中占用一个8字节条目，记录该变量在内存中的地址。加载时，动态链接器重定位GOT中的每个条目，使其指向正确的绝对地址。每个引用全局目标的目标模块都具有自己的GOT。实际上，是将访问全局目标的指令的PC作为索引，加上固定偏移量访问GOT，得到所需变量的地址。

访问其他目标模块中的全局函数，与访问全局变量有何区别呢？想象我们正在处理两个共享库A和B（它们必须被编译为PIC）；重点在于，在绝大多数情况下，共享库中的全局函数都是远远多于全局变量的。库A中的函数一般只会调用库B中的少量全局变量，但可能极其频繁地调用了库B中的许多函数（可以是成千上万个）。若我们仍使用全局变量的访问模式来访问全局函数（使用GOT来进行二次跳转），那么当库A被加载进内存时，动态链接器就需要对这成千上万个GOT条目进行重定位，使它们正确指向库B中的全局函数。然而，我们的主程序可能仅仅只调用其中的几个库函数，这造成了严重的资源浪费。

为了解决以上问题，GCC使用延迟绑定（lazy binding），将函数地址的绑定推迟到第一次调用该过程时。这能避免动态链接器在加载时进行不必要的重定位。若目标模块调用共享库中的函数，则其有自己的GOT和过程链接表（Procedure Linkage Table，PLT），PLT是代码段的一部分，每个条目占用16字节（attacklab中揭示了函数地址要对16对齐）。PLT实际上是模块访问全局函数的一次索引，已被设置好且始终不变；GOT为二次索引，初始状态未被设置好，需要在函数被调用时被设置。

PLT每个条目是长为16字节的代码，第0项调用动态链接器，格式为push+jmp；第1项为调用系统启动函数；之后每一项都用于调用一个函数，格式为jmp（GOT对应索引）+push（函数信息）+jmp（PLT第0项，调用动态链接器）

GOT的第0、第1个条目记录了动态链接器解析函数地址中会使用的信息；GOT[2]是动态链接器（在ld.so中）的入口点；之后每一项都维护着函数地址，初始设置为对应PLT条目的第二条（push+jmp）

第一次调用函数时，跳转到PLT对应条目，条目第一行跳转到GOT对应条目指向位置，但GOT未被设置好，所以跳转回来到PLT条目第二行，它将要定位的函数ID压栈，跳转到PLT第0项，它将GOT[1]指向的重定位条目压栈，调用GOT[2]指向的动态链接器；动态链接器根据栈中的两个参数（ID和重定位条目），重写GOT对应条目为函数地址，再把控制传递给对应函数。由于全部过程中没有ret，对应函数执行完毕后直接ret到调用函数的位置。

最后附上笔者回课的PPT：

动态链接11.13.pdf

447.3KB

库插桩/标记 (Library Interpositioning)

库插桩允许在不修改源代码的情况下修改库函数行为，例如进行监控或调试。

假设原代码使用了 malloc 函数。我们可以通过以下步骤进行库插桩：

编写自定义的 my_malloc 函数，并将其编译成 .o 文件。

编写本地 malloc.h 头文件，使用宏将 malloc 替换为 my_malloc。

编译源代码时，使用 L 参数优先使用本地库。

通过这种方式，可以在不修改源代码的情况下监控 malloc 函数的调用。

.lazy-image-placeholder{ background: linear-gradient(90deg,#0001 33%,#0005 50%,#0001 66%) #f2f2f2; background-size:300% 100%; animation: l1 1s infinite linear; } @keyframes l1 { 0% {background-position: right} } ICS07 链接