Chapter 07 Linking

7.1 编译器驱动程序

以链接 main.o, sum.o 两个文件为例

> cpp [...] main.c /tmp/main.i 
> ccl /tmp/main.i -Og [...] -o /tmp/main.s
> as [...] -o /tmp/main.o /tmp/main.s
> (the same procedure for sum.o)
> ld -o prog [...] /tmp/main.o /tmp/sum.o
> ./prog

cpp : 预处理器, C Pre Processor (not .cpp file)

ccl : 编译器

as : 汇编器

ld : 链接器

7.2 静态链接

静态链接器以一组 可重定位目标文件 和 命令行参数作为输入, 生成一个完全链接的, 可以加载和运行的可执行目标文件 作为输出.

为了构造可执行文件, 链接器需要完成两个主要任务:
- 符号解析 (symbol resolution). 将符号引用与符号定义关联起来. 符号可以是函数, 全局变量, 或静态变量 (以 static 属性声明的变量).
- 重定位 (relocation). 编译器和汇编器生成的代码和数据节地址都是从 0 开始的. 链接器要将符号定义与内存位置关联起来, 重定位这些节, 修改对符号的引用使得它们指向真实的内存位置.

7.3 目标文件

三种形式:
- 可重定位目标文件. 可以和别的可重定位目标文件链接形成可执行目标文件
- 可执行目标文件. 可被直接复制到内存并执行.
- 共享目标文件. 特殊的可重定位目标文件, 可在加载或运行时被动态地加载进内存并链接.

各个系统目标文件的格式不尽相同.
- Unix: a.out
- Windows: PE
- Mac OS-X: Mach-O
- 现代 x86-64 Linux: ELF

7.4 可重定位目标文件

• ELF 头: 16 字节序列. 描述文件的一些信息, 包括节头部表的文件便宜, 节头部表中条目的大小和数量.
• 节头部表: 不同节的位置和大小由节头部表描述, 每个节都对应一个固定大小的条目.
• 夹在 ELF 头和节头部表的都是节, 典型的 ELF 文件包含:
  • .text: 已编译的程序机器代码
  • .rodata: 只读数据
  • .data: 已初始化的全局和静态 C 变量
  • .bss: 未初始化的全局和静态 C 变量, 被初始化为 0 的全局和静态 C 变量
  • .symtab: 符号表
  • .rel.text: 可以理解成一个待办事项, 说明待会要将 text 中的什么位置重定位
  • .rel.data: 类似的
  • .debug: 调试符号表, -g 选项生成
  • .line: C 程序行号和 .text 之间映射
  • .strtab: 字符串表.

区分 .rel.text 和 .rel.data 的重定位内容

可以从字面意思来理解. .rel.text 就是机器代码中有需要被替换的内容, .rel.data 就是在符号值中有需要被替换的内容.

例如

extern int x;
int f() {
   return x + 1;
}

这里的 x 是外部符号, 在机器代码中我们可能会有这样的内容

4: 8b 05 00 00 00 00 mov 0x0(%rip),%eax

链接就是把 00 00 00 00 的占位符替换成真实地址(这里使用 %rip PC 相对寻址)

如果是

extern int x;
int p = x;

这里由于编译的时候我们不知道 x 的值, 所以 .data 节中的 p 的值是 00000000, 等到链接的时候我们再将真实的值替换, 所以是通过 .rel.data

7.5 符号和符号表

每个可重定位目标模块 m 都有一个符号表, 包含 m 定义和引用的符号信息, 有三种不同的符号.
- 由 m 定义并能被其他模块引用的 全局符号, 对应非静态的 C 函数和全局变量
- 由其他模块定义并被 m 引用的 全局符号, 被称为 外部符号, 对应于其他模块定义的非静态 C 函数和全局变量
- 只被 m 定义和引用的 局部符号, 对应于带 static 属性的 C 函数和变量.

Note

不同的作用域中可以定义相同名字的 static 局部变量, 编译器会给他们分配不同的名字.

.symtab 节包含 ELF 符号表, 符号表包含一个数组, 数组的每个元素是一个条目, 条目格式如下:

typedef struct {
    int name;
    char type:4, // 低 4 位
         binding:4; // 高 4 位
    char reserved; // 可能是用于对齐
    short section;
    long value;
    long size;
} ELF64_Symbol;

• name: 字符串表(.strtab)中的字节偏移, 指向一个字符串名字. (.strtab 中是一个个以 null 结尾的字符串, 通过偏移量一直找直到遇到 '\0' 我们可以确定唯一一个符号名字)
• value: 符号地址(不是符号的值), 可重定位模块中是距定义目标的节的起始位置的偏移, 对可执行模块就是绝对地址了. (在链接时分配虚拟地址)
• size: 目标的大小, 以字节为单位. 例如对于代码就是代码的大小
• type: 要么是数据, 要么是函数
• binding: 符号是本地的(只在当前模块可见)还是全局的(别的模块也可见)
• section: 表示符号分配到的节的索引(Ndx=1代表.text, Ndx=3 代表.data). 有三个特殊的伪节, 它们在节头部表是没有条目的:
  • ABS: 代表不该被重定位的符号(可能是一些汇编器产生的常量数据)
  • UNDEF: 未定义的符号, 在本目标模块引用却在其他地方定义的符号 (extern)
  • COMMON: 还未分配位置的未初始化的数据目标, 对于 COMMON符号, value 给出的是对齐要求(因为它还没有地址), size 给出最小的大小.
  • gcc 将未初始化的全局变量分配到 COMMON 节, 未初始化的静态变量, 初始化为 0 的全局或静态变量分到 .bss 节. 这是根据符号的强弱区分的. (理解上就是说未初始化的全局变量你不知道它是不是外部有定义)

COMMON 符号的地址确定

首先根据强弱符号的规则保留一个符号, 如果别的文件有强符号定义, 那么直接替换为强符号. 如果都是弱符号随机保留一个并创建或扩展 .bss 节

UNDEF 符号

UNDEF 符号是类似 extern int x; 的符号, 它可以直接使用外部符号的定义, 所以不用分配地址, value = 0, 在链接的时候把代码里用到 x 的地方重定位即可.

7.6 符号解析

7.6.1 链接器如何解析多重定义的全局符号

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

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

Linux 遵循以下规则处理多重定义符号名:
- 不允许多个同名强符号
- 一个强符号和多个弱符号, 选择强符号
- 多个弱符号, 任意选择一个

由于这种规则, 如果使用不同类型定义同名变量, 很容易发生意想不到的错误, 例如:

1.c

int x = 15212;
int y = 15213;

2.c

double x;
void f() {
    x = -0.0;
}

这里 2.c 的 x 会使用 1.c 的定义, 但是由于 double 是 8 字节, 所以在调用 f() 的时候会把紧邻 4 字节的 y 的值也修改了.

7.6.2 与静态库链接

静态库是为了解决调用一些标准函数的引用问题提出的.

相关的函数可以被编译为独立的目标模块, 然后封装成一个单独的静态库文件. 在链接时只复制被引用的目标模块, 这样就减少了可执行文件的大小.

Liunx 中静态库以 archive 的文件格式存放在磁盘中 (.a)

例如有 addvec.c 和 multvec.c 两个文件

> gcc -c addvec.c multvec.c # 只执行到汇编, 不链接
> ar rcs libvector.a addvec.o multvec.o

这样就创建了一个静态库.

main.c 与其链接的时候, 使用命令

> gcc -c main.c
> gcc -static -o prog main.o ./libvector.a
> 或者
> gcc -static -o prog main.o -L. -lvector

-lvector 是 libvector.a 的缩写. -L. 告诉编译器在当前目录下查找 libvector.a.

7.6.3 链接器如何使用静态库解析引用

在符号解析阶段, 链接器从左到右按照它们在命令行出现的顺序扫描可重定位目标文件和存档文件. 维护三个集合 E, U, D.

• E: 可重定位目标文件集合
• U: 引用了但未定义的符号集合
• D: 在前面文件已定义的符号集合

之后对于每个输入文件 f
- 如果 f 是可重定位目标文件, 就加入 E, 然后根据 f 修改 U 和 D.
- 如果 f 是存档文件, 尝试匹配 U 中未定义的符号, 如果某个存档文件成员 m (这是一个可重定位目标文件) 定义了这个符号, 就将 m 加入到 E 中, 根据 m 修改 U 和 D, 对存档文件所有目标文件依次执行这一过程, 直到 U, D 不再变化, 此时不包含在 E 的文件被丢弃.

因此, 文件的输入顺序非常重要, 如果一个未引用的符号的定义文件在它之前, 那么它就无法获取它的定义.

7.7 重定位

一旦链接器完成了符号解析, 每个符号引用和一个定义关联起来, 链接器就知道了它目标模块的代码节和数据节的确切大小. 现在可以开始重定位了.

重定位由两步组成:
- 重定位节和符号定义。在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。例如，来自所有输入模块的.data节被全部合并成一个节，这个节成为输出的可执行目标文件的.data节。然后，链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输人模块定义的每个符号。当这一步完成时，程序中的每条指令和全局变量都有唯一的运行时内存地址了。
- 重定位节中的符号引用。在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。要执行这一步，链接器依赖于可重定位目标模块中称为重定位条目(relocationentry)的数据结构，我们接下来将会描述这种数据结构。

7.7.1 重定位条目

格式:

typedef struct {
    long offset;
    long type: 32,
         symbol: 32;
    long addend;
} Elf64_Rela;

- offset: 要重定位的符号在它那个节的偏移
- type: 如何修改引用
- symbol: 被修改引用应该指向的符号在符号表的索引(注意我们已经为这些变量分配了绝对地址, 所以可以在符号表中找地址)
- addend: 偏移量

两种典型重定位类型:
- R_X86_64_PC32: PC相对寻址
- R_X86_64_32: 绝对寻址

7.7.2 重定位符号引用

感觉书上讲的太复杂, 用一般的相对寻址方式来理解即可.

7.8 可执行目标文件

• ELF 头: 描述文件总体格式, 包括程序入口点(第一条指令地址)
• .text, .rodata, .data 等类似
• .init 定义了 _init_ 函数, 程序初始化代码(__libc_start_main)会调用它

BSS 段的空间分配

可执行目标文件不会为 .bss 分配实际的空间, .bss 的空间是加载到内存时才分配的.

7.9 加载可执行目标文件

代码段总是从 0x400000 处开始, 后面是数据段. 运行时堆在数据段之后, 通过调用 malloc 向上增长. 堆后面的区域是为共享模块保留的. 用户栈总是从最大的合法用户地址 2^48-1 开始, 向低地址增长, 栈以上的区域是为内核保留的.

由于对齐要求, 代码段和数据段之间会有一点空隙. 分配栈等地址的时候, 还会使用地址空间布局随机化.

7.10 动态链接共享库

静态库的缺点: 需要定期维护和更新. 每一个模块会复制到每一个进程的文本段中.

共享库在运行或加载时, 可以加载到任意的内存地址, 并和一个在内存中的程序链接起来, 这个过程称为动态链接.

共享库也被称为共享目标 (shared object), Linux 中使用 .so 后缀, Windows 中使用 DLL(动态链接库)

so 文件中的代码和数据, 不是像静态库一样复制和嵌入到引用它们的可执行文件中的, 一个副本可以被不同的正在运行的进程共享.

Note

建议先学习 Chapter 09 Virtual Memory 之后再回看一遍动态链接共享库. 尤其是 mmap 和 COW 的概念.

编译时, 执行如下命令

> gcc -shared -fpic -o libvector.so addvec.c multvec.c
> gcc -o prog21 main2.c ./libvector.so

-fpic 是指定生成位置无关代码

注意, 生成 prog21 的时候没有任何代码和数据节真的被复制到了 prog21 中. 反之, 链接器复制了一些重定位和符号表信息, 使得运行的时候可以解析堆 libvector.so 中代码和数据的引用.

加载时, 加载器注意到 prog21 包含一个 .interp 节, 这一节包含动态链接器的路径名. 动态链接器本身就是一个共享目标, 加载器加载和运行它, 然后执行下面的重定位完成链接:
- 重定位 libc.so 的文本和数据到某个内存段 (每一个C程序都会动态链接这个库)
- 重定位 libvector.so 的文本和数据到另一个内存段
- 重定位 prog21 中所有对 libc.so 和 libvector.so 定义的符号的引用.

7.11 从应用程序中加载和链接共享库

前面讨论的是加载后执行前时执行的动态链接, 应用程序还可能在运行时要求动态链接器加载和链接某个共享库.

Linux 系统为动态链接器提供了一个简单的接口, 使得应用程序可以在运行时加载和链接共享库, 如果可执行文件使用了 -rdynamic 选项编译, 那么主程序的全局符号对共享库也是可见的.

#include <dlfcn.h>

void *dlopen(const char *filename, int flag);
// 返回: 若成功则为指向句柄的指针(句柄可以理解成指向这个共享库的一个标志), 出错则为 NULL
void *dlsym(void *handle, char *symbol);
// 返回: 若成功返回指向符号的指针, 若出错则为 NULL
void dlclose(void *handle);
// 返回: 若成功返回 0, 否则 -1
const char *dlerror(void);
// 返回: 如果前面有对上面三个函数的调用失败, 则为错误信息(最近的错误), 否则返回 NULL

• filename: 共享库的名字
• flag:
  
  NOW 和 LAZY 都可以和 GLOBAL 符号取或

Note

“所有外部符号引用”就是指当前正在加载的共享库中，所有对外部模块（主程序或其他库）所提供的函数和变量的使用。

GLOBAL 就是让其它的共享库也可以看到它的符号.

7.12 位置无关代码

这个用于解决共享库加载到的地址问题.

如果共享库每次加载到专门的地址, 很容易造成地址空间的浪费. 地址空间很容易被分裂成大量小的, 未使用的而不能再使用的小洞.

现代编译器使得可以把共享库加载到内存的任何位置而无需链接器修改, 可以加载而无需重定位的代码称为位置无关代码, GCC 使用 -fpic 选项指示编译系统生成 PIC (Position-Independent Code) 代码. 共享库的编译必须总是使用该选项.

对同一个目标模块符号的引用不需要特殊处理使之成为 PIC, 因为我们可以用 PC 相对寻址来编译这些引用, 构造目标文件时使用静态链接器重定位. (只要在静态链接时计算出偏移量嵌入到指令中就好了)

位置无关的核心就是利用了如下事实: 无论在内存中哪个位置加载目标模块, 数据段与代码段的距离总是保持不变. 运行时我们只需要通过 PC 相对寻址就能确定变量位置. 这是通过全局偏移量表 (GOT) 实现的. 在加载时, 动态链接器会重定位 GOT 中的每个条目, 使得它包含了目标的正确的绝对地址, 每个引用全局目标的目标模块都有自己的 GOT.

7.13 库打桩机制

截获对共享库函数的调用, 取而代之执行自己的代码.

7.13.1 编译时打桩

-Dname(=value): 相当于在源代码开头添加了一行 #define name (value)

使用

> gcc -DCOMPILETIME -c mymalloc.c
> gcc -I. -o intc int.c mymalloc.o

-I. 参数会告诉 C 预处理器在搜索通常的系统目录前先在当前目录查找 malloc.h

7.13.2 链接时打桩

使用 --wrap f 标志进行链接时打桩, 他告诉链接器把对符号 f 的引用解析成 __wrap_f 还要把对符号 __real_f 的引用解析成 f.

使用命令

> gcc -DLINKTIME -c mymalloc.c
> gcc -c int.c
> gcc -Wl,--wrap,malloc -Wl,--wrap,free -o intl int.o mymalloc.o

-Wl,option 把 option 传递给链接器, option 的每个逗号替换为空格, 因此 -Wl,--wrap,malloc 就把 --wrap malloc 传递给链接器.

7.13.3 运行时打桩

编译时打桩需要能够访问程序的源代码, 链接时打桩需要能够访问程序的可重定位对象文件, 不过运行时打桩只需要能够访问可执行目标文件.

方式是使用 LD_PRELOAD 环境变量, 它被设置成一个共享库路径名的列表(以空格或分号分隔), 当加载和执行一个程序需要解析未定义的引用时, 动态链接器会先搜索这里面的库. 这样我们就可以对共享库函数进行打桩了.