CSAPP第七章 - 链接

1. 编译器驱动程序

有如下的程序：

其中的 main.c 引用了另外一个 sum.c 文件的函数。我们可以通过 gcc -Og -o prog main.c sum.c 来把这两个文件链接到一块编译出一个产物。这里的 gcc 相当于是一个编译器驱动程序，代替用户执行预处理器、编译器、汇编器、链接器来生成一个可执行文件。

上述 gcc 驱动编译的详细过程如下：

• 首先把源码 main.c 翻译成一个中间文件 main.i：cpp [other arguments] main.c /tmp/main.i
• 然后将这个中间文件翻译成汇编的文件 main.s：cc1 /tmp/main.i -Og -o /tmp/main.s
• 然后驱动程序运行汇编器，将 main.s 翻译成一个可重定位目标文件 main.o：as -o /tmp/main.o /tmp/main.s
• 然后驱动程序经过相同的过程生成 sum.o
• 最后驱动程序运行链接器将 main.o 和 sum.o 和其他的必要文件组合起来，生成一个可执行目标文件 prog：ld -o prog [system object files and args] /tmp/main.o /tmp/sum.o

2. 目标文件（ELF）

目标文件有三种：

• 可重定位目标文件（.o 格式）：由汇编器生成，仅经过了编译但是还没链接。链接器后续会将其与其他的可重定位目标文件合并，生成可执行目标文件
• 可执行目标文件：可以被直接被加载到内存中执行
• 共享目标文件：一种特殊类型的可重定位目标文件，可以在编译时或是加载时被静态或是动态链接到程序中。静态链接对应的是 .a 格式，动态链接对应的是 .so 格式。

在 Linux 系统上，目标文件是 ELF 格式的。

同时内核模块（.ko 文件），内核转储文件（coredump）也会使用 ELF 格式。

ELF 文件总体上分成四个部分：ELF Header、Program Header Table、Section Header Table 和中间的部分。

2.1 ELF 头部

64 位的 ELF 头部有 64 字节：

名称	字节数	说明
e_ident	16	一些标志信息（具体见后面）
e_type	2	ELF 文件类型（具体见后面）
e_machine	2	指定 ELF 运行的 CPU 架构，具体看 这里
e_version	4	指定 ELF 版本，一般为 1
e_entry	8	elf 代码运行的入口，是一个虚拟地址。操作系统应在加载程序后直接执行该虚拟地址处的代码
e_phoff	8	Program Header Table 在文件中的偏移量
e_shoff	8	Section Header Table 在文件中的偏移量
e_flags	4	处理器特性标签，不太了解
e_ehsize	2	ELF 头的大小，单位为字节
e_phentsize	2	Program Header Table 中每个条目的大小
e_phnum	2	Program Header Table 中条目的数量
e_shentsize	2	Section Header Table 中每个条目的大小
e_shnum	2	Section Header Table 中条目的数量
e_shstrndx	2	每个 Section 都有一个名称。其中有一个 Section （.shstrtab）专门用来存储其他 Section 的名称。该值则表示储存名称的 Section 在 Section Header Table 中的索引

其中要展开说的如下：

• e_ident，16字节

名称	字节数	说明
ELF 魔数	4	固定为 0x7f 0x45 0x4c 0x46 ，表示这是一个合法的 elf 文件
EI_CLASS	1	表示文件是 32 位还是 64 位，0x01 为 32 位，0x02 为 64 位
EI_DATA	1	指定大小端，0x01 为小端，0x02 为大端
EI_VERSION	1	ELF 规范版本。目前固定为 0x01
EI_OSABI	1	是否启用一些基于操作系统或者 CPU 特性。一般为 0x00
EI_ABIVERSION	1	指定当前 ABI 版本，配合 EI_OSABI 使用。一般也是为 0x00
EI_PAD	6	预留，一般都为 0x00
EI_NIDENT	1	不太清楚，文档上说的是 e_ident[] 数组大小

​ 实际上最后 9 个字节 ELF 标准没有定义，一般填 0，有些平台会使用这 9 个字节作为扩展标志。

• e_type，2 字节，表示 ELF 文件类型，常用的如下：

  现代的可执行文件中该字段为 ET_DYN，表示该可执行文件中的代码都是位置无关代码，操作系统在加载时会启用 ASLR，以应对缓冲区溢出和 ROP 攻击。在加载时会随机选择一个基址，然后将 ELF 文件的各个部分在虚拟空间的位置对这个基址进行偏移，同时还会把把这个偏移施加到 e_entry 上，作为实际的跳转入口。

  ET_EXEC 则表示传统的可执行文件，其代码会被加载到固定位置。

  使用 g++ -no-pie 选项进行编译，可以使得编译器产生 ET_EXEC 类型的可执行文件。

名称	数值	说明
ET_NONE	0	非文件类型
ET_REL	1	可重定位文件
ET_EXEC	2	可执行文件
ET_DYN	3	共享库（动态链接）
ET_CORE	4	内核转储文件
ET_LOOS	0xfe00	操作系统特定文件
ET_HIOS	0xfeff	操作系统特定文件
ET_LOPROC	0xff00	处理器特定文件
ET_HIPROC	0xffff	处理器特定文件

• e_phoff ， e_phentsize 和 e_phnum 表明了 Program Header Table 的信息
• e_shoff ， e_shentsize 和 e_shnum 表明了 Section Header Table 的信息

2.2 可重定位目标文件

可重定位目标文件用不到 Program Header Table，所以就没有。

可重定位目标文件将中间的部分称为节。

一个 Section Header Table 的表项占 64 字节，结构如下：

名称	字节数	说明
sh_name	4	表示节的名称。存储的是名称的第一个字符在 .shstrtab 节的偏移
sh_type	4	节的类型（具体见后面）
sh_flags	8	节的属性，每一位表示不同的标志（具体见后面）
sh_addr	8	如果节将被加载到进程的虚拟内存中，那么该字段给出节的虚拟内存地址。否则，此字段设为 0
sh_offset	8	如果节出现在文件中，则该字段给出节在文件中的偏移。否则，该字段设为 0（比如 BSS 段）
sh_size	8	表示节的大小，单位字节
sh_link	4	一般为 0。否则表示这个节和某个节有关联，存储的是相关联的节在 Section Header Table 中的索引。具体的解释依赖于节的类型
sh_info	4	节的额外信息。具体的解释依赖于节的类型
sh_addralign	8	某些节的地址有对齐约束。这个值只允许 0 以及 2 的正整数幂。取 0 或是 1 时表示没有对齐约束。当开启对齐约束时，sh_addr 必须是 sh_addralign 的倍数
sh_entsize	8	如果这个节也是一个表（如符号表）的话，那么这个值就表示表里每个条目的大小。反之则为 0。

其中需要具体说明的如下：

• sh_type，常见取值如下

名称	数值	说明
SHT_NULL	0	无效段
SHT_PROGBITS	1	表示存放代码或者数据，如 .text 和 .data
SHT_SYMTAB	2	符号表
SHT_STRTAB	3	表示存放字符串表，如 .shstrtab
SHT_RELA	4	重定位表，该段包含了重定位信息
SHT_HASH	5	符号表的哈希表
SHT_DYNAMIC	6	动态链接信息
SHT_NOTE	7	提示性信息
SHT_NOBITS	8	表示这个节不在 ELF 文件中存放数据，含有的数据都是未初始化的数据。如 .bss。
SHT_REL	9	包含了重定位信息
SHT_SHLIB	10	保留
SHT_DNYSYM	11	动态链接的符号表

• sh_flags

名称	值	说明
SHF_WRITE	0x1	表示该节是可写的
SHF_ALLOC	0x2	表示该节需要分配内存
SHF_EXECINSTR	0x4	表示该节可执行
SHF_MERGE	0x10	表示该节可以被合并
SHF_STRINGS	0x20	表示该节包含字符串
SHF_INTO_LINK	0x40	表示 sh_info 字段包含额外的语义信息
SHF_LINK_ORDER	0x80	表示该节的链接顺序依赖于另一个节
SHF_OS_NONCONFORMING	0x100	表示该节需要操作系统特殊处理
SHF_GROUP	0x200	表示该节属于一个节组
SHF_TLS	0x400	表示该节包含线程本地存储
SHF_MASKOS	0x0ff00000	保留给操作系统特定的语义
SHF_MASKPROC	0xf0000000	保留给处理器架构特定的语义

• 如果节的类型是与链接相关的（不管是动态链接还是静态链接），比如重定位表、符号表，那么 sh_link 和 sh_info 这两个成员的意义如下。对于其他类型的节，这两个成员没有意义：

sh_type	sh_link	sh_info
SHT_DYNAMIC	该 section 所使用的字符串表在 section header table 中的下标	0
SHT_HASH	该 section 所使用的符号表在 section header table 中的下标	0
SHT_REL	该 section 所使用的相应符号表在 section header table 中的下标	该重定位表所作用的 section 在 header table 中的下标
SHT_RELA	同上	同上
SHT_SYMTAB	操作系统相关	操作系统相关
SHT_DYNSYM	同上	同上
其他	SHN_UNDEF	0

一般包含如下的几个节：

名称	sh_type	sh_flag	说明
.text	SHT_PROGBITS	SHF_ALLOC+SHF_EXECINSTR	已编译的程序的机器代码
.rodata	SHT_PROGBITS	SHF_ALLOC	常量信息，是只读的
.rodata1	SHT_PROGBITS	SHF_ALLOC	和 .rodata 差不多
.data	SHT_PROGBITS	SHF_ALLOC+SHF_WRITE	有初始值的全局变量和静态局部变量
.data1	SHT_PROGBITS	SHF_ALLOC+SHF_WRITE	和 .data1 差不多
.bss	SHT_NOBITS	SHF_ALLOC+SHF_WRITE	没有初始值的全局变量和静态局部变量。这个节并不在 ELF 中占用实际的大小，而是在运行的时候直接在虚拟内存中进行映射，并由程序来给内存清零。.bss 可以认为是 Better Save Space ，一种节约文件大小的方式（尽管实际上 .bss 的来源不是这个）
.rel.text	SHT_REL		存放 .text 节中需要重定位的位置，用于后续重定位
.rel.data	SHT_REL		存放 .data 节中需要重定位的位置，同上
.debug	SHT_PROGBITS	none	调试符号表，只有在编译时添加 -g 选项才会被生成。调试符号表将会存放程序中定义的各种变量的信息，以及原始的 C 语言文件，用于调试
.line	SHT_PROGBITS	none	编译时添加 -g 选项才会被生成。存放原始的 C 语言文件中的行号和 .text 中机器指令的映射关系
.symtab	SHT_SYMTAB	如果 ELF 文件中有可装载的段需要用到该符号表，那么该符号表也被装载到进程空间，则有 SHF_ALLOC 标识位	符号表，程序中定义的全局变量和引用的全局变量的信息都存放在这里。符号表将用于后续的链接的重定位
.shstrtab	SHT_STRTAB	none	节头部表的节名字并没有直接存到相应的位置，而是存储到 .shstrtab 中。原来的位置上只存储文本在 .shstrtab 中的偏移。
.strtab	SHT_STRTAB	如果 ELF 文件中有可装载的段需要用到该字符串表，那么该字符串表也被装载到进程空间，则有 SHF_ALLOC 标识位	同上，但是 .strtab 是存 .symtab 和 .debug 中的符号的
.dynamic	SHT_DYNAMIC	SHF_ALLOC+SHF_WRITE（在有些系统下可能是只读的，没有 SHF_WRITE 标识位）	动态链接信息
.hash	SHT_HASH	SHF_ALLOC	符号哈希表
.note	SHT_NOTE	none	额外的编译器信息，比如程序的公司名，发布版本号等
.plt			用于动态链接
.got			用于动态链接
.init			用于 C++ 全局构造
.fini			用于 C++ 全局析构

其中的字符串表的类型的节主要长这样：

2.3 可执行目标文件

可执行目标文件和可重定位目标文件大致差不多，区别在于：

• .text 、.rodata、.data 中的内容已经经过重定位了。
• 新增了一个 .init 节，里面定义了一个小函数，叫做 __init，用于程序的初始化，后文的加载过程会细说。
• 由于重定位完毕，所以不需要 .rel 相关的节。

有意思的是，尽管可执行目标文件不需要再与其他文件链接了，.symtab 还是存在。我们可以使用 strip 命令特意去掉。

节提供了非常细粒度的程序组织方式，这对于编译器和链接器很有用。但是对于加载器来说就不需要这么细粒度的组织了。于是在加载器的视角，把文件的中间部分称作段，将具有相似属性（如内存权限）的多个节组合在一起，一个段可能包含若干个节，从而简化了加载过程。

由于加载器不从节的角度看待 ELF，所以最后不带 Section Header Table 似乎问题不大。

一个 Program Header Table 里的表项占 56 字节，结构如下：

名称	字节数	说明
p_type	4	段的类型
p_flags	4	标记，主要用于 PT_LOAD 中的虚拟内存权限位，而对于其他类型的段可能有不同的含义
p_offset	8	段内的内容在 elf 文件内的偏移
p_vaddr	8	段加载到的虚拟内存地址，主要用于 PT_LOAD 类型的段。其他类型的段可能用不到
p_paddr	8	段加载到的物理内存地址，主要用于一些不支持虚拟内存的硬件上面。对于大部分支持虚拟内存的平台上，这个值用不到。
p_filesz	8	该段在文件中的大小
p_memsz	8	该段在内存中的大小。存在 p_memsz > p_filesz 的情况，比如 .bss 段
p_align	8	该段的对齐方式

对于 p_type，有如下的取值：

类型	说明
PT_NULL	好像没啥用，会被忽略掉
PT_LOAD	表示当前段需要从文件中加载到虚拟内存
PT_DYNAMIC	包含动态链接器所需要的信息，比如共享库的依赖，符号表位置等
PT_INTEPR	包含动态链接器的路径的字符串
其他	还有很多其他的类型，不过好像是可有可无的

当 p_type == PT_LOAD 时，p_flags 有如下的可选选项（p_flags 的值是下面的取值按位与得到的）

值	名称	说明
0x1	PF_X	可执行
0x2	PF_W	可写
0x4	PF_R	可读

3. 符号解析

3.1 符号表

一个 C 文件中定义的全局符号，有可能只是占位，实际上是要引用另一个文件的全局符号。同时一个 C 文件中定义的全局符号有可能也要被其他 C 文件引用。全局符号将会存在 ELF 的 .symtab 中，在与其他文件链接时提供信息。

.symtab 中的条目结构如下：

字段	字节数	说明
st_name	4	符号名字在字符串表（.strtab）中的索引。如果该值为 0，说明该符号没有名称
st_info	1	低四位表示符号的类型，高四位表示符号的链接性
st_other	1	暂时为 0，含义没有被定义
st_shndx	2	这个符号的定义是存在于哪个节中，存储的是 Section Header Table 的索引
st_value	8	指明这个符号的定义存在于哪个位置。对于可重定位目标文件，这里存储的是相对于其所在的节中的偏移（配合 st_shndx 就知道其绝对位置）。对于可执行目标文件，这里存储的直接就是符号的定义的虚拟内存地址。
st_size	8	该符号对应的目标所占用的大小，如果符号没有大小或大小未知，则该成员为 0

对于 st_info

• 符号链接性部分可取如下的值：

  • STB_LOCAL：局部符号（不是局部变量，局部变量在符号表中没有对应条目）

  • STB_GLOBAL：全局符号

  • STB_WEAK：弱符号

• 符号类型部分可取如下的值：

  • STT_NOTYPE：未知类型

  • STT_OBJECT：该符号是个数据对象，比如变量等

  • STT_FUNC：该符号是个函数或其他可执行代码

  • STT_SECTION：该符号表示一个段，这种符号的类型必然是 STB_LOCAL

  • STT_FILE：该符号表示文件名，其符号类型必然是 STB_LOCAL，其 st_shndx 必然是 SHN_ABS

• st_shndx 可取一些特殊值，称为伪节：

  • SHN_ABS 表明这个符号不应该被重定位，比如表示文件名的符号

  • SHN_UNDEF 表明这个符号的定义在当前文件中虽被定义了，但具体定义在外部的文件中。

  • SHN_COMMON 则存储弱符号。

3.2 特殊符号

使用 ld 作为链接器时，在产生最终可执行文件的时候会自动为我们添加如下符号，这些符号可以直接声明并引用：

• __executable_start：程序的起始地址（不是入口地址）
• __etext 或 ``_etext或etext：.text` 段的结束地址
• _edata 或 edata：.data 段结束地址
• _end 或 end：程序的结束地址
• 还有其他更多。。。

这些符号只是表明一个“位置”，符号并没有对应任何的数据。链接时，如果产生的是位置无关代码，那么会以 PC 相对的方式来引用这些符号，这些符号所表明地址会由于 ASLR 发生变化：

c
1
2
3
4
5
6
7
8
9
#include <stdio.h>

extern char _end[];

int main(void)
{
	printf("_end = %p\n", (void *)_end);
	return 0;
}

3.3 符号修饰

同时由于历史原因，Visual C++ 编译器会在 C 语言的符号前面加 _，GCC 在 Windows 平台下的版本（cygwin、mingw）也会这样。对于后者，可以添加 -fleading-underscore 或是 -fno-leading-underscore 选项来打开或是关闭这种行为。

C++ 中支持函数重载，同时又引入命名空间。这些特性需要对同名符号进行修饰，使得其在链接的时候能够相互区别。

GCC 的符号修饰：

c++filt 工具可以用来解析被修饰过的名称：

Unknown
1
2
$ c++filt _ZN1N1C4funcEi
N::C::func(int)

Visual C++ 的符号修饰：

extern C

C++ 为了与 C 兼容，有一个 extern "C" 关键字，这个关键字可以用来修饰声明/定义，也可以在后面跟一个大括号来包裹多个声明/定义。被该关键字修饰的符号会被视为 C 符号，不再进行 C++ 符号的修饰规则：

c++
1
2
3
4
5
6
7
extern "C" int func(int);
extern "C" int var;
// or
extern "C" {
    int func(int);
    int var;
}

但是由于在 Windows 平台上，C 语言的符号还是会在开头追加 _ ，因此上述两个符号其实还是被修饰成 _func 和 _var。

头文件

对于 C 语言编写的共享库，其提供的头文件如果想要给 C++ 程序使用的话，需要 extern "C" 包裹头文件的符号以确保能够正确链接。这样一来一个头文件就需要编写 C++ 和 C 两个版本，有点麻烦。

C++ 编译器会在编译 C++ 时自动定义 __cplusplus 这个宏，于是我们可以借此来判断当前编译单元是否为 C++ 代码，从而使得一个头文件可以用作 C 和 C++：

c++
1
2
3
4
5
6
7
8
9
#ifdef __cplusplus
extern "C" {
#endif

void *memset(void *, int, size_t);
   
#ifdef __cplusplus
}
#endif

3.4 符号解析

C 语言中，链接器首先对每一个翻译单元的符号的链接性和符号位置进行判定：

• 链接性

  • 如果符号被 static 修饰，那么这个符号直接被判定为内部链接性，为 STB_LOCAL，不参与跨文件的符号解析。（但是还会参与重定位）
  • 对于 STB_WEAK 的符号，不同编译器有不同的语法来声明。GCC/Clang 中使用 __attribute__((weak)) 修饰的符号的链接性为 STB_WEAK
  • 其余的符号均为 STB_GLOBAL

• 符号位置

  • 带函数体、有初值的变量，符号的 st_shndx 均为其定义的节中

    如果其初始值为 0，则会判定这个符号属于 .bss 节。如果其初始值不为 0，则会判定这个符号属于 .data 节

  • 没有函数体的函数定义、被 extern 修饰的函数或是变量，被判定在 SHN_UNDEF 节中

  • 没有初始值的全局变量，被 __attribute__((weak)) 修饰则判定为 SHN_UNDEF 节中，反之则判定在 SHN_COMMON 节中

然后对于 STB_GLOBAL 和 STB_WEAK 类型的符号进行跨文件引用解析：

• 如果存在 STB_GLOBAL + 真实节定义，那么其余所有的同名引用都绑定到这个定义上。如果这样的定义不止一个，则报告链接错误。

• 否则的话，再去找 STB_GLOBAL + SHN_COMMON 定义。如果有多个这样的定义，则随机选取一个（或者说具体怎么选取看链接器的实现），然后其余所有的同名引用都绑定到这个定义上。这个定义会被判定在 .bss 上。

• 否则的话，再去找 STB_WEAK + 非 SHN_UNDEF 定义。如果有多个这样的定义，则随机选取一个，然后其余所有的同名引用都绑定到这个定义上。

• 否则的话，说明这个符号没有任何定义

  于是将所有的 STB_WEAK + SHN_UNDEF 引用全部解析到地址 0。这主要是用于 dlopen 配合 RTLD_GLOBAL 选项使用的，允许该符号在运行时再解析。

  如果存在 STB_GLOBAL + SHN_UNDEF 引用则报告链接错误（特别地，如果是编译动态库（编译时带了 -shared 参数选项）那么就不会报告链接错误）。

如果我们把 STB_WEAK 符号和 STB_GLOBAL + SHN_COMMON 符号称为弱符号，其他 STB_GLOBAL 符号称为强符号，我们可以总结有如下的强弱符号规则来处理多个文件之间的全局符号引用：

• 强符号：所有的函数和有初始值的全局变量
• 弱符号：没有初始值的全局变量

对于多个重名的全局符号，链接器有如下的规则进行选取：

• 规则 1：不允许有多个同名的的强符号
• 规则 2：如果有一个强符号和多个弱符号，选择强符号
• 规则 3：如果有多个弱符号，随机选择一个

现代的链接器默认自动开启 -fno-common 选项，使得存在重名符号的时候（即使不是强符号重名）也会直接报错。我们可以手动添加 -fcommon 来允许弱符号重名。

common

我们可以把多个重名的 SHN_COMMON 符号理解成是，这些重名的符号共享同一个内存空间（反正这些符号初值都是零，随便选取哪个符号作为绑定目标都无所谓）。

共享的这个空间在最后会开在 .bss 段上。那么现在我们关心的是空间分配多大。编译器在符号解析的过程中，只关心符号的名称，而不关心符号的类型，符号类型不会用来区分重名符号。实际上，分配的空间为同名的符号中最大的数据类型大小。这也就是为什么要有 SHN_COMMON 而不是直接判定到 .bss 上。

C++

而对于 C++，没有了强弱符号机制，而是有一个 ODR （One Definition Rule），全局符号一律不允许重名。如果在一个文件中想要引用另一个文件中的符号，则需要在当前文件的定义中添加 extern 修饰。编译器会将这个符号判定为属于 UNDEF 节中。

SEE ALSO ：Effective C++ 读书笔记，链接：TODO

4. 链接

C 语言规范中定义了一组函数，这些函数放在 libc 库中，如 printf、scanf 等。为了支持这些库函数，一种方式是直接让编译器识别出这些函数，然后生成相应的代码。但是这样会增加编译器的复杂性。

另一种方法是将所有的函数放到一个单独的可重定位目标文件中，如 libc.o ，然后 gcc main.c /usr/lib/libc.o 即可让引入库函数。不过这样的话，每个编译出来的程序都会携带一个完整的 libc.o ，会浪费内存。

又一种方法是为每个函数创建一个单独的可重定位目标文件。不过这样做需要程序员自行链接合适的文件：gcc main.c /usr/lib/printf.o /usr/lib/scanf.o。但是这样很麻烦又容易出错。

4.1 静态链接

静态库将若干个可重定位目标文件组合到一个 .a 后缀的静态库文件中。这个文件的头部描述了其包含成员目标的信息。使用静态库文件时，链接器会自动抽取静态库文件中被使用到的成员，没被使用的则不会被抽取。

4.1.1 生成共享库

如我们创建一个 libvector 库：

使用 gcc -c addvec.c multvec.c 可以编译得到 addvec.o 和 multvec.o

然后我们可以使用 ar rcs libvector.a addvec.o multvec.o 来打包得到静态库文件。

4.1.2 使用共享库

使用时需要先有个头文件，头文件包含库函数的定义。

然后使用如下命令编译：

gcc -static -o prog2c main2.o -L. -lvector

其中 -static 参数告诉编译驱动程序，链接器应该构建一个完全链接的可执行目标文件，可以直接加载到内存中运行。这个参数使得可执行文件不需要任何动态链接。

-L. 表明寻找静态库的位置

-lvector 是 libvector.a 的缩写

4.1.3 链接过程

在静态链接时，链接器维护一个将要被合并的目标文件集合 $E$，一个未解析的符号集合 $U$，一个在前面输入文件中已经定义的符号集合 $D$。

• 对于命令行上的每个输入文件 $f$，链接器则会判断 $f$ 是一个目标文件还是一个存档文件
• 如果 $f$ 是目标文件，则会把 $f$ 放入 $E$ 中，用 $D$ 尝试解决 $f$ 中未解析的符号，再用把剩余未被解析的符号加入 $U$ 中（注意是剩余，如果 $f$ 中引用的符号已经存在于 $D$ 了，那么就不放入 $U$ 了）
• 如果 $f$ 是静态库文件，则在 $f$ 中的成员（即静态库中包含的目标文件）所定义的符号中寻找当前未被解析的元素。把对解析有帮助的成员目标文件放入 $E$，更新 $U$ 和 $D$。对解析没有帮助的则会直接丢弃
• 进行完毕之后，如果 $U$ 是非空的，则会报错

由于链接器在遇到静态库的时候，是根据当前 $U$ 来按需抽取静态库成员的，所以我们在编译时，命令行上放置的静态库文件的顺序非常重要，必须要使得前面未被解析的符号在后面的文件中存在定义。如：

gcc -static ./libvector.a main2.c，处理 libvector.a 时，$U$ 是空的，这个库文件不会解决后面的 main2.c 的符号解析，所以会报错。所以我们最好是把静态库文件放在命令行的后面。

同时我们还需要注意静态库文件的依赖关系。比如 foo.c 调用 libx.a 和 libz.a，而这两个库又调用 liby.a，那么我们需要这么写：gcc foo.c libx.a libz.a liby.a。

如果出现循环依赖，我们可以在命令行上重复添加文件，比如 libx.a 调用 liby.a，而 liby.a 也调用了 libx.a，则有：gcc foo.c libx.a liby.a libx.a。当然另一个解决方法是把 libx.a 和 liby.a 合并成一个单独的静态库文件。

4.1.4 重定位

链接器需要把多个可重定位目标文件中，名字相同的节合并，比如把各个文件的 .text 合并成一个 .text。但是合并之后，一些全局符号的地址就会发生改变。

编译器会提前知道哪些全局符号的地址暂时无法确定，于是在引用这些符号的地方，先不设置具体的地址，而是先留空，并记录这些位置，生成重定位条目，放到 .rel 相关的节上。重定位文件合并之后，各个符号的地址就确定下来了，链接器会进行重定位，就是根据重定位条目，设置好具体的地址。

重定位表就是一个元素为重定位条目的数组，重定位条目的结构如下：

其中的 offset 表明需要重定位的地址。地址是相对于其所在节的偏移。

symbol 表明这个要被重定位的引用，是引用了哪个符号，存储的是在符号表中的下标。

addend 表明计算出重定位地址之后还需要进行的调整量。常用于重定位为 PC 相对地址时。

type 表明重定位类型。由于架构的指令集格式有所不同，以及不同指令的寻址方式也不同，所以重定位类型有非常多，这里讲两种最基本的类型：

• R_X86_64_PC32：重定位为一个 PC 相对地址
• R_X86_64_32：重定位为一个绝对的地址

上述类型重定位的地址都是 32 位的，这是因为这两个类型是基于 x86-64 小型代码模型。这个模型假设可执行目标文件的大小小于 2GB，32 位的寻址就足够，GCC 默认使用这个模型。

重定位算法如下：

其先枚举了要重定位的节，然后枚举该节下的重定位条目。令 ADDR(r.symbol) 为引用的符号的真实地址。

• 对于 R_X86_64_PC32 类型，将会将要重定位的地方的值设置为 ADDR(r.symbol) + r.append - refaddr，其中 refaddr 表示被重定位的地方的地址。
• 对于 R_X86_64_32 类型，将会将要重定位的地方的值设置为 ADDR(r.symbol) + r.append。

4.2 动态链接

静态库直接编译进程序了，这导致程序和静态库两者之间不能独立更新。同时，每个程序都会含有重复的静态库代码，仍然造成了很大的浪费。

共享库可以解决上述缺陷。程序在编译时不去将共享库加入编译产物中，而是简单的记录共享库的名称，程序在加载的时候再去载入共享库。同时，利用虚拟内存技术，我们可以只加载一个共享库文件到内存中，让多个程序共享这块内存。

4.2.1 ELF

.interp 中保存了一个字符串，表示该程序需要的动态链接器的路径。

.gynamic 中保存了动态链接器所需要的基本信息：

• .dynsym 的文件偏移
• .dynstr 的文件偏移
• 所有依赖的动态库的名称

.dynsym 存放着当前 ELF 需要的符号（导入符号）和导出的符号（如果是共享库的话）。.dynstr 用来存放符号的名称。这两个东西与 .symtab 和 .strtab 的结构几乎一致。动态链接时可能需要对符号表进行查找，所以往往还存在一个符号哈希表 .hash 来辅助我们查找。

4.2.2 位置无关代码

不同的进程的虚拟内存布局都有所不同，所以共享库会被加载到不同的位置。此时共享库本身需要考虑到这点，有两种解决方案：

装载时重定位

产生共享库时生成一个重定位表（.rel.dyn），然后加载器在加载时，根据这个重定位表和共享库的加载位置重定位所有的引用。

但这存在缺陷，首先这样会使得 .text 节可写，会有漏洞隐患。其次，这样的话，每个进程都需要独立的代码段的副本，而现代的操作系统，每个进程都共享一个代码段以节省内存。而且对于一个比较大的程序，加载时重定位所有引用的话也会严重拖慢程序的加载速度。

目前编译器不允许共享库使用这种方案，强制要求共享库是位置无关代码。

位置无关代码

不仅是共享库可以有位置无关代码，可执行文件也可以有。

对于共享库，编译时需要加上 -fpic 选项才会产生位置无关代码。对于可执行程序，编译时需要加上 -fpie，现代的编译器往往默认带上了这个选项，可以通过 -fno-pie 选项来组织产生位置无关代码。

共享库中的引用主要有如下几种：

• 共享库内部的函数调用（非 SHN_UNDEF 符号）：由于共享库在静态链接时，同一个编译单元内的 .text 还是都在一起，所以只需要使用 PC 相对的跳转指令即可，甚至无需重定位。

• 共享库内部的数据访问（非 SHN_UNDEF 符号）：

  首先数据一般会放入别的段中，而静态链接时各个段又会重新组合，因此需要重定位。

  此外还需要 PC 相对寻址。

  • 对于 64 位的 X86，可以使用 (%rip) 之类的进行 PC 相对寻址。
  • 而对于 32 位的 X86，不能直接用 %eip 来进行寻址，需要使用一些奇怪的手段：先调用一个函数，此时当前 PC 值会被压入栈中，我们把 (%esp) 存下来就可以得到 PC 值了。

• 共享库之间的访问

  共享库会在 .got 段存放一个 GOT 表。这个表中每个条目都是 8 字节，表示一个地址。编译器会在 GOT 中给程序中的所有引用的外部符号都建立一个条目，初始时为空，等待重定位，GOT 会对应一个重定位表。加载时，动态链接器无需重定位代码段，只需要重定位 GOT 表即可。每个可执行文件和共享库实例都有一个独立 GOT 表，也就是加载他们的时候只需要建立 GOT 表和重定位 GOT 表的代价。

上面还漏了种情况：对于 SHN_UNDEF 符号的引用。

编译器在编译每个编译单元时，如果遇到 SHN_UNDEF 符号，则推测其在链接时可能有两种情况：这个符号在后续静态链接中就可以解决，或是这个符号在后续动态链接中才会解决。对于后者，就需要使用 GOT 表了。所以在编译位置无关代码时，编译器为这些符号的引用搞一个特殊的重定位类型：既可能静态链接时就可以直接重定位到目标地址，又可能需要建立 GOT 表然后重定位到 GOT 表上。（编译时不产生 GOT）

假如后续静态链接时，正好遇到了这个符号的定义，那么链接器会根据产生文件的类型做出不同的选择：

• 对于可执行文件，链接器会直接重定位到对应的符号定义的地方，不需要使用 GOT 了

• 而对于动态库，动态库存在符号插入机制，即默认动态库中的这些符号都是可以在后续被其他动态库给覆盖掉的。所以尽管链接器可以直接重定位到符号定义的地方，但还是选择保留 GOT，只不过把符号定义的地方放到了 GOT 中。

  可以通过给符号加上 __attribute__((visibility("hidden"))) 来防止该符号被外部符号覆盖掉，同时也能避免引用该符号时经过 GOT 中转。

GOT 表的重定位信息放在了 .rel.dyn 中。

还存在一种特殊情况：

c
1
2
static int a = 1;
static int b = &a;

全局变量的地址需要在运行时才会被确定。此时编译器会在 .rel.dyn 中加入一条 R_X86_64_RELATIVE 类型的重定位条目，等待后续动态链接器重定位。

4.2.3 PLT

使用 GOT 表就可以解决很多问题了。但是现代编译系统引入了 PLT 来支持动态绑定机制。比如我们的代码用到了外部库中成千上百个函数，如果如果在加载时，将这些函数对应在 GOT 表中的项目全部重定位，会造成很大的性能开销。

PLT 表位于 .plt 中。表中每个条目都是一个 16 字节代码。 PLT 拥有可执行权限。

PLT 要配合 GOT 表使用。配合 PLT 的 GOT 表专门存在 .got.plt 中。.got.plt 的前三项有特殊含义：

• 第一项 GOT[0] 表明 .dynamic 节的地址
• 第二项 GOT[1] 表明 .rel.plt 的地址
• 第三项 GOT[2] 表明动态链接器中的 _dl_runtime_resolve 的地址。

PLT 表的第一项 PLT[0] 对应的代码是将 GOT[1] 压入栈中并调用动态链接器。

每个外部函数在 .rel.plt 段会有一项，表明该函数的符号名称之类的。同时还会在 PLT 中有一个对应的条目。

当程序调用外部函数的时候，会先跳转到外部函数对应的 PLT 条目中，PLT 条目中的第一个执行是跳转指令，跳转到其对应的 GOT 条目中指向的地址。

在初始时，这个地址又指向 PLT 条目的第二条指令，这个指令会将其对应的函数在 .rel.plt 段的索引放入栈中，然后跳到 PLT[0] 中，来调用动态链接器。

_dl_runtime_resolve 根据压入栈中的 .rel.plt 段的索引来拿到要调用函数的符号，然后寻找到对应函数的真实地址，然后再写回 GOT 中，然后再调用对应函数。

后续再次调用外部函数的时候，从 PLT 跳到 GOT 对应的条目时，这个条目已经指明了外部函数的地址，可以直接跳过去：

这也就实现了延迟绑定。

4.2.4 生成共享库

我们可以使用如下命令生成共享库：

gcc -shared -fpic -o libvector.so addvec.c multvec.c

-shared 指明打包成共享库，-fpic 指明要生成与位置无关代码（这个参数是必须的）

4.2.5 使用共享库

编译时链接

gcc -o prog2l main2.c ./libvector.so

其中 ./libvector.so 会参与符号解析，只不过不会将其中的内容合入到输出的文件中。

运行时使用

需添加编译参数 -ldl 来使得可执行文件链接动态加载器，以使用运行时链接的功能。

在 dlfcn.h 头文件中，有如下的函数：

void *dlopen(const char *filename, int flag);

• 加载和链接共享库 filename

  • 如果这个路径为绝对路径，则该函数会直接打开该动态库
  • 如果为相对路径，那么该函数会以一定的顺序去查找该动态库
  • 如果将 filename 设为 $0$，那么该函数会返回全局符号的句柄（类似高级语言的反射机制）

• flag 可选如下选项

  • RTLD_GLOBAL 将共享库的符号直接合并到当前程序的全局符号空间。
    • 这样，可执行文件中只需要在 dlopen 之后直接调用这个符号即可，不用再使用 dlsym 了（不过需要先使用 __attribute__((weak)) 声明对应符号）
    • 同时，合并到全局符号空间之后，后续再次加载的共享库能够调用之前加载的共享库。
    • 如果当前可执行文件编译时添加了 -rdynamic 选项，那么共享库还能去使用当前可执行文件中的符号。
  • RTLD_NOW 立即解析共享库的符号引用，这样加载时比较耗时，但是使用符号的时候非常快。
  • RTLD_LAZY 将符号解析推迟到使用时，这样加载时很快，但是初次使用符号的时候比较慢

• dlopen 加载动态库时会执行动态库 .init 段的内容。

• 函数调用成功则返回一个指向句柄的指针，如果出错则返回 NULL

void *dlsym(void *handle, char *symbol);

• 获取加载的共享库中的某个符号的地址

• handle 为 dlopen 返回的句柄指针，symbol 指明要引用的符号名称

• 成功则返回指向符号的指针，出错则返回 NULL

• 有一些符号是对外不可见的，比如编译单元文件名的符号，他们是 SHN_ABS。但是 dlsym 仍能获取到他们。

• dlopen 打开的动态库可能又依赖于别的动态库，dlsym 会以打开的动态库为根节点开始，按 BFS 的顺序查找符号。

int dlclose(void *handle);

• 卸载某个共享库
• handle 为 dlopen 返回的句柄指针
• 成功则返回 0，失败返回 -1
• 可能有多个动态库依赖于同一个动态库，所以将一个动态库卸载后，其依赖的动态库未必会跟着卸载。动态链接器会维护一个类似于引用计数的东西。当一个动态库的引用计数归零时，这个动态库就会被真的卸载掉，此时会执行该动态库的 .finit 段的代码，然后去除相应的符号，并释放相关内存。

const char *dlerror(void);

• 如果前面的函数调用失败了，那么可以根据这个函数获取最近一次失败的消息
• 如果前面的函数存在错误则返回错误文本的指针，如果前面没发生过错误则返回 NULL

6. 加载

6.1 内存准备

文件映射

操作系统首先为要加载的可执行文件准备虚拟内存空间，具体的内容涉及到操作系统，这里不多说了。

值得注意的是，操作系统将 PT_LOAD 段加载到内存时，不会产生数据的复制，而是把文件的内容映射到虚拟内存中，按需加载。

虚拟内存的权限是按内存分页为单位设置的，理论上来说 ELF 文件中的段要按页大小对齐，但是这样的话对齐引入的空隙可能会占不少的空间。实际上的做法是，每个段只需要满足如下的对齐要求：

$$\text{p\_vaddr}\bmod{\text{p\_align}} = \text{p\_offset} \bmod {\text{p\_align}}$$

p_align 一般就是取当前操作系统的分页大小。不过好像还可能取分页大小的倍数，这就不太清楚为什么了。

这个对齐要求可以确保一个段的开头在一个分页内的偏移，等于将这个文件按分页大小切割后段开头在切割出来的部分内的偏移。

操作系统在映射时，两个段的交界部分可能会被映射两次到虚拟内存。第一次映射主要是为了映射前面的段的部分，然后顺带映射了一点后面段的部分的数据。第二次映射主要是为了映射后面的段的部分，然后顺带映射了一点前面段的部分的数据。

进程栈初始化

操作系统将启动该进程时的参数和环境变量通过栈传递给该进程。

操作系统将控制权交给进程前，栈的顶部存放着参数的数量，再往上是参数字符串的指针，再往上是 0，再往上是环境变量字符串的指针，再往上是 0，再往上是辅助向量（图中没画出来），再往上是 0，再往上是参数和环境变量的字符串。

其中辅助向量包含一些辅助信息，是一个数组结构，由若干个 (key, value) 对构成，key 表示类型，value 表示数据。辅助向量主要供动态链接器和 glibc 使用。

6.2 动态链接

如果被加载的 ELF 文件中存在 .interp 的话，那么说明该 ELF 文件用到了动态链接，操作系统需要先加载动态链接器。

加载动态链接器前，内核会在上面提到辅助向量里面加入如下的信息：

• 动态链接器访问 ELF 的方式。有两种：

  一种是直接从内存中访问，这个方式要求操作系统把整个 ELF 文件都映射到了内存中，同时需要后面提供如下的信息：

  • Program Header Table 的虚拟地址
  • Program Header Table 每个项目的大小
  • Program Header Table 内项目的数量
  • 可执行文件的入口地址

  另一种是动态链接器自己去读 ELF 文件，这需要后面提供：

  • 可执行文件的句柄

• 动态链接器本身的装载地址

这个辅助信息数组会放在栈中，位置为环境变量指针的后面，字符串数据的前面。

随后操作系统将控制权交给动态链接器。

一些动态链接器由于各种原因，存在全局变量的初始值包含其他全局符号的地址，即存在 R_X86_64_RELATIVE 类型的重定位条目。此时动态链接器需要自己完成这个重定位工作，即要完成自举。自举代码先找到自己的 GOT 表，GOT 表保存着 .dynamic 段的偏移地址，自举代码凭借 .dynamic 的信息获得动态链接器本身的重定位表和符号表等，进行重定位工作。

动态链接器接下来维护一个全局符号表。首先会把动态链接器本身的符号和加载的可执行文件的符号加入到全局符号表中。接着，根据可执行文件的 .dynamic 信息，加载可执行文件所依赖的动态库，这些动态库又可能依赖于别的动态库，于是就这样不断地加载。

动态链接器一般采用 BFS 的顺序来加载各个共享库的符号到全局符号表中。注意符号加载到全局符号表的顺序：LD_PRELOAD（见后面运行时打桩）-> 可执行文件本身和动态链接器的符号 -> BFS 顺序加载其他库的符号。如果某个符号在加载时，发现全局符号表中已经有了一个和其同名的符号，那么这个符号就被跳过了。所以先加载的动态库可以屏蔽掉后加载的符号。

接下来动态链接器编译可执行文件和所有加载的动态库的 .rel.dyn ，并据此进行重定位。

重定位完成后，如果加载的动态库有 .init 段，那么动态链接器就会加载这个段的代码，以实现动态库特有的初始化过程（比如 C++ 的全局对象构造）。可执行文件的 .init 段就不由动态链接器执行了。

这些都做完，动态链接器就把控制权交给程序的入口了。

6.3 C 运行时

程序的入口并非是 main，而是 glibc 的 _start。该函数使用汇编编写，主要收集一些参数来调用 __libc_start_main。

__libc_start_main 需要七个参数：

• main 函数的地址
• argc
• argv：只需要传 argv 就可以得到环境变量的指针了，因为参数的指针后面紧跟着就是 0，后面紧跟着就是环境变量的指针
• init：初始化函数的指针，一般为 __libc_csu_init
• fini：结束时要执行的函数的指针，一般为 __libc_csu_fini
• rtld_fini：动态链接器结束时要执行的函数的指针。一般是动态链接器约定，在跳转到可执行文件的入口前，会把对应的函数的指针放入到某个寄存器上
• stack_end：栈底地址

__libc_start_main 接下来会干这些事：

• 从 argv 中把环境变量的指针取出来
• 执行 __pthread_initialize_minimal，进行一些线程相关的初始化
• 通过 __cxa_atexit 将 rtld_fini 挂载到结束时要执行的函数的链上。
• 执行 __libc_init_first ，完成 glibc 内一些信息的初始化
• 通过 __cxa_atexit 将 fini 挂载到结束时要执行的函数的链上。
• 执行 init 函数（即 __libc_csu_init）

__libc_csu_init 一般会干下面两个事：

• 执行 .init 里面的 _init() 函数。这是一个比较老式的初始化机制了，现在好像基本用不到，不过为了保持兼容还是存在这个。
• 遍历 .init_array，这个部分是一个数组，里面存放着初始化时要执行的函数的指针，一般全局变量的构造函数的指针就被放在这里。我们可以使用 __attribute__((constructor)) 把自己的函数也给注册进来。

好像在较新版本的 glibc 中，__libc_csu_init 和 __libc_csu_fini 被移除了

然后调用 main 函数。

最后，会将 main 函数的返回值作为参数，去调用 exit()。exit() 会遍历由 __cxa_atexit 注册的所有函数。

• rtld_fini 会负责执行已经加载的动态库的 .fini 和 .fini.array
• __libc_csu_fini 会负责执行当前可执行文件的 .fini 和 .fini.array

然后 exit() 会跳转到 _exit，这个函数使用汇编编写，执行系统调用来退出进程。

5. 库打桩

库打桩可以让我们拦截对一个共享库的调用，反而执行自己的代码。

5.1 编译时打桩

首先有一个我们自己的函数：

然后编译 gcc -DCOMPILETIME -c mymalloc.c

然后我们再编写一个自己的头文件，在这个头文件里通过宏来更改调用函数的名称：

编译：gcc -I. -o intc int.c mymalloc.o

其中 -I. 是打桩的关键。这个参数将会让编译器优先从当前目录下寻找头文件，所以编译器会使用我们的 malloc.h 而不是标准的 malloc.h。

5.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 intc int.o mymalloc.o

其中 -Wl,option 用于将 option 传递给链接器，并且 option 中的每个逗号都被替换成空格。

5.3 运行时打桩

有一个全局变量 LD_PRELOAD，程序在加载共享库时，动态链接器会先从 LD_PRELOAD 中寻找对应的共享库。我们把要拦截的函数写成一个共享库之后，把路径添加到 LD_PRELOAD 中就可以实现打桩。

6. 相关工具

• gcc

  • -c：只编译不链接，生成 .o 目标文件

• objdump

  • -h：把 ELF 文件的各个段的基本信息打印出来
  • -s：将所有段的内容以十六进制打印出来
  • -d：将所有包含指令的段反汇编

• readelf

  • -h：打印 ELF 文件的头部信息
  • -S：显示 ELF 的 section table
  • -s：显示 ELF 的符号表
  • -r：显示重定位表
  • -d：查看 .dynamic 段的内容
  • -dS：查看与动态链接相关的符号表

• ar：创建静态库，插入、删除、列出、提取成员。
  • -t：查看静态库中的成员
  • -x：将静态库中的成员全部提取出来
• strings：列出一个目标文件中所有可打印的字符串。
• strip：从目标文件中删除符号表信息。
• nm：列出一个目标文件的符号表中定义的符号。
• size：列出目标文件中节的名字和大小。
• readelf：显示一个目标文件的完整结构，包括 ELF 头中编码的所有信息。包含 size 和 nm 的功能。
• objdump：显示目标文件的所有信息，主要用于反编译 .text 的指令
• ldd：列出可执行文件在运行时需要的共享库