Introduction
链接 (linking) 就是将不同部分的代码和数据收集和组合成为一个单一文件的过程，这个文件可被加载（复制）到存储器并执行。
可以在程序生命周期的多个阶段执行链接：
- 编译时(compile time)，也就是在源代码被翻译成机器代码时；例如静态链接
-
加载时(load time)，也就是在程序被加载器（loader）加载到存储器并执行时（loader查询每个页表项时，动态链接所需的调用关系链路，并将相应的动态链接库映射到内存中，即在加载/运行时完成链接。这种方案可以结合静态/动态链接的优点，既可以减少内存开销，又能够动态地加载和切换不同版本的库文件。但是，实现这种形式的动态链接可能需要占用更多CPU时间。）
- 甚至执行于运行时（run time)，由应用程序来执行；例如动态链接
在早期的计算机系统中，链接是手动执行的。在现代系统中，链接是由叫做链接器（ linker）的程序自动执行的。
链接的优点？
链接器使得分离编译 (separate compilation) 成为可能，模块化，效率。我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的一个时，我们只要简单地重新编译它，并将它重新链接到应用上，而不必重新编译其他文件。
编译器驱动程序
我们通过一个示例来展示将源代码变成可执行文件的过程。
main.c
main函数的返回值看起来有点奇怪，这样做是为了让编译器不优化所有代码
1
2
3
4
5
6
7
8
int sum(int *a, int n);
int array[2] = {1, 2};
int main(){
int val = sum(array, 2);
return val;
}
sum.c
1
2
3
4
5
6
7
8
int sum(int *a, int n){
int i, s = 0;
for(i = 0; i < n; i++){
a += a[i];
}
return s;
}
大多数编译系统提供编译驱动程序 (compiler driver)，它为用户，根据需求调用语言预处理器、编译器、汇编器和链接器。例如通过如下命令使用GNU编译系统构造示例程序。
1
2
gcc -Og -o prog main.c sum.c
# -Og 是 GCC 编译器的一个选项，它是“优化等级 O1”（Optimization Level 1）和“优化等级 O2”（Optimization Level 2）之间的一种选择。该选项可以让 GCC 尝试仅仅使用那些不影响调试过程的优化实现。简而言之，这个选项可以使编译器在生成可执行文件时，可以最大程度保留程序的原始结构和语义，并且对于调试器的支持也更加友好。
上述命令其实由四部分构成：
- 预处理：在编译源代码之前，预处理器会对其进行一些预处理操作。例如，它会查找并替换源代码中定义的宏、展开头文件，以及删除注释。预处理输出的是修改后的源代码（.i文件）。
- 编译：编译器会将预处理器处理好的源代码转换为汇编代码 (.s文件)，也就是通常说的“汇编语言”。
- 汇编：汇编器会将汇编代码转换为机器码（也称为目标代码，.o文件），这是计算机硬件可以直接执行的程序。它还创建一个包含所有符号地址和其他调试信息的符号表。
- 链接：最终一步就是将所有编译和汇编的文件合并为一个可执行文件，该文件具有已解析的所有符号地址，并完成了所有的必要内存分配。链接器会扫描所有的目标文件，并将它们合并到一个二进制可执行文件中。
目标文件
目标文件有三种形式：
- 可重定位目标文件：例如.o；包含二进制代码和数据，可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
- 可执行目标文件：例如.out/.exe；包含二进制代码和数据，可以被直接复制到内存并执行。
- 共享目标文件：例如.so；一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态加载进内存被链接。
各个系统之间，目标文件格式都不相同。第一个从贝尔实验室诞生的Unix系统使用的是a.out格式（直到今天，可执行文件仍然指的是 a.out文件）。Windows使用的是叫做PE(Portable Executable，可移植可执行〉格式。Mac OS-x使用Mach-O格式。现代Unix系统–—比如Linux，还有System V Unix后来的版本，各种 BSD Unix，以及 SUN Solaris一一使用的是Unix ELF (Executable and LinkableFormat，可执行和可链接格式)。尽管我们的讨论集中在ELF上，但是不管是哪种格式，基本的概念是相似的。
可重定位目标文件
下图展示了一个典型的ELF可重定位目标文件。ELF头（ELF header）以一个16字节的序列开始，这个序列描述了生成该文件系统字的大小和字节顺序（大端字节序和小端字节序）。ELF头剩下的部分包含帮助链器解析和解释目标文件的信息。其中包括ELF头的大小、目标文件的类型（比如，可重定位、可行或者是共享的)、机器类型（比如，IA32)、节头部表 ( section header table) 的文件偏移，以及节头部表中的表目大小和数量。不同节的位置和大小是由节头部表描述的，其中目标文件中每个节有一个固定大小的表目（ entry)。
ELF文件格式是所有目标文件的通用格式
一个典型的ELF可重定位目标文件包含下面几个节：
- .text：已编译程序的机器代码。
- .rodata：只读数据，比如printf语句中的格式串和switch语句的跳转表。
- .data：已初始化的全局和静态C变量（static）。局部C变量在运行时被保存在栈中，既不出现在.data节中，也不出现在.bss 节中。
- .bss：（ better save space :) ）未初始化的全局和静态C变量（static），以及所有被初始化为0的全局和静态C变量。在目标文件中这个节不占据实际的空间，而是在程序加载时动态地分配所需的内存空间并全部置0，它仅仅是一个占位符。目标文件格式区分初始化和未初始化变量是为了空间效率。
- .symtab：一个符号表，它存放在程序中被定义和引用的函数和全局变量的信息。一些程序员错误地认为必须通过-g选项来编译一个程序，得到符号表信息。实际上，每个可重定位目标文件在.symtab中都有一张符号表。然而，和编译器中的符号表不同，.symtab符号表不包含局部变量的表目。
- .rel.text：一个.text节中位置的列表，当链接器把这个目标文件和其他文件结合时，.text节中的许多位置都需要修改。一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非使用者显式地指示链接器包含这些信息。
- .rel.data：被模块定义或引用的所有全局变量的重定位信息。一般而言，任何已初始化全局变量的初始值是全局变量或者外部定义函数的地址都需要被修改。
- .debug：一个调试符号表，其表目是程序中定义的局部变量和类型定义，有些表目是程序中定义和引用的全局变量，有些是原始的C源文件。只有以-g 选项调用编译驱动程序时，才会得到这张表。
- .line：原始C源程序中的行号和.text节中机器指令之间的映射。只有以-g选项调用编译驱动程序时，才会得到这张表。
- .strtab：一个字符串表，其内容包括.symtab和.debug 节中的符号表，以及节头部中的节名字。字符串表就是以null 结尾的字符串序列。
符号和符号表
每个可重定位目标模块m都有一个符号表，它包含m所定义和引用的符号的信息。在链接器的上下文中，在链接器的上下文，有三种不同的符号：
- 由m定义并能被其他模块引用的全局符号。全局链接器符号对应于非静态的C函数以及被定义为不带C的static属性的全局变量。
- 由其他模块定义并被模块m引用的全局符号。这些符号称为外部符号(external)，对应于定义在其他模块中的非静态C函数和全局变量。
- 只被模块m定义和引用的本地符号。本地链接器符号对应于带 static属性的C函数和全局变量。这些符号在模块m中的任何地方都是可见的，但是不能被其他模块引用。
可以使用static属性来保护变量和函数
.symtab节中包含ELF符号表：
1
2
3
4
5
6
7
8
9
typedef struct{
int name; /* String table offset */
char type:4, /* Function or data (4 bits) */
binding:4; /* Local or global (4 bits) */
char reserved; /* Unused */
short section; /* Section header index */
long value; /* Section offset or absolute address */
long size; /* Object size in bytes */
}Elf64_Symbol;
GNU READELF程序是一个查看目标文件内容的很方便的工具，具体使用方法可查看readelf manual。查看示例可重定位目标文件main.o的符号表：
1
readelf -s main.o
可以看到全局（GLOBAL）符号main定义的条目，它是一个位于.text节中偏移量为0（Value值）处的37字节函数。全局符号array是一个位于.data节中偏移量为0处的8字节目标。最后一个条目来自对外部符号sum的引用。READELF用一个整数索引（Ndx，1即.txt，3即.data）来标识每个节。
静态链接
静态链接器 ( static linker）以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的代码和数据节 ( section) 组成。指令在一个节中，初始化的全局变量在另一个节中，而未初始化的变量又在另外一个节中。
为了创建可执行文件，链接器必须完成两个主要任务:
- 符号解析（symbol resolution)：目标文件定义和引用符号，每个符号对应一个函数、一个全局变量或一个静态变量（static声明），符号解析的目的是将每个符号引用（变量、函数等等）和一个符号定义联系起来。
- 重定位 (relocation)：编译器和汇编器生成从地址零开始的代码和数据节。链接器通过把每个符号定义与一个存储器位置联系起来，然后修改所有对这些符号的引用，使得它们指向这个存储器位置，从而重定位这些节。
符号解析
链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义联系起来。对那些和引用定义在相同模块中的本地符号的引用，符号解析是非常简单明了的。编译器只允许每个模块中的每个本地符号只有一个定义。编译器还确保静态本地变量，它们也会有本地链接器符号，拥有惟一的名字。
对全局符号的符号解析很棘手，还因为相同的符号会被多个目标文件定义。
强符号（strong）和弱符号（weak）
- strong：过程、函数名称或已初始化的全局变量
- weak：未初始化的全局变量
根据强弱符号的定义，Unix链接器使用下面的规则来处理多处定义的符号:
- 规则1：不允许有多个强符号
- 规则2：如果有一个强符号和多个弱符号，那么选择强符号
- 规则3：如果有多个弱符号，那么从这些弱符号中任意选择一个
一些例子：
重定位
重定位的内容较为复杂，大概概括起来就是：
- 重定位节和符号引用：相同类型的节合并为同一类型的聚合节，并将运行时内存地址赋予聚合节
- 重定位节中的符号引用：依赖于重定位条目，修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时位置
静态链接库
所有的编译系统都提供一种机制，将所有相关的目标模块打包为一个单独的文件，称为静态库(static library)，它也可以用做链接器的输入。当链接器构造一个输出的可执行文件时，它只拷贝静态库里被应用程序引用的目标模块。
如果不使用库，一些使用ISO标准函数以及其他可重用函数的比较naive的方法：
静态库（.a文件，众多.o文件的集合，有一个头部来描述每个.o文件的大小和位置）概念被提出来，以解决上述方法的缺点。相关的函数可以被编译为独立的目标模块，然后封装成一个单独的静态库文件。在链接时，链接器将只拷贝被程序引用的目标模块（比如printf.o），这就减少了可执行文件在磁盘和存储器中的大小。另一方面，应用程序员只需要包含较少的库文件的名字（实际上，C编译器驱动程序会自动传送 libc.a给链接器)。
可以通过AR工具创建自己的静态链接库：
C标准库和C数学库
动态链接库
实际上我们通过gcc对程序进行编译链接时基本都是动态链接的，链接程序在链接时一般是优先链接动态库的，除非我们显式地使用gcc -static参数指定链接静态库。
静态链接库有许多缺点：
- 首先就是系统空间被浪费了。这是显而易见的，想象一下，如果多个程序链接了同一个库，则每一个生 成的可执行文件就都会有一个库的副本（静态链接的程序往往比动态链接的程序更大），必然会浪费系统空间（存储和内存）。
- 一旦发现了库中有bug或者是需要升级，必须把链接该库的程序找出来，然后全部需要重新编译。
动态链接库（DDLs，.so文件）的出现正是为了弥补静态库的弊端。因为动态链接库是在程序加载或运行时被链接的，所以磁盘上只要保留一份副本，因此节约了磁盘空间。如果发现了bug或要升级也很简单，只要用新的库把原来的替换掉就行了。
动态链接过程：
- prog21中并没有任何链接库的数据和代码，但包含了一些重定位和符号表信息，使得运行时可以解析对链接库的代码和数据的引用。
- 当程序在内存中加载运行时，动态链接器进行重定位完成链接。
可执行目标文件
我们已经看到链接器是如何将多个目标模块合并成一个可执行目标文件的。我们的C程序，开始时是一组ASCII文本文件，已经被转化为一个二进制文件，且这个二进制文件包含加载程序到存储器并运行它所需的所有信息。
- 可执行文件格式和可重定位文件格式类似。
- ELF头除了描述文件的总体格式，还包含程序的入口点。
- 多了段头表，一个段包含多个节（这些节已被重定位到最终运行时的内存地址，.init用于初始化程序）。
加载可执行目标文件
加载器将可执行目标文件中的代码和数据从磁盘拷贝到内存中，然后通过跳转到程序的第1条指令，即入口点（entrypoint)，来运行该程序。这个将程序拷贝到存储器并运行的过程叫做加载(loading)。
位置无关代码
共享库的一个主要目的就是允许多个正在运行的进程共享内存中相同的库代码，从而节约宝贵的内存资源。那么，多个进程是如何共享程序的一个副本的呢？一种naive的方法是给每个共享库分配一个事先预备的专用的地址空间片，然后要求加载器总是在这个地址加载共享库。虽然这种方法很简单，但是它也造成了一些严重的问题：
之所以还是写这个naive的思想，目的是为了思考这个方法的缺点是啥
- 它对地址空间的使用效率不高，因为即使一个进程不使用这个库，那部分空间还是会被分配出来。
- 它也难以管理。我们必须保证没有片会重叠。
- 每次当一个库修改了之后，我们必须确认已分配给它的片还适合它的大小。如果不适合了，必须找一个新的片。并且，如果创建了一个新的库，我们还必须为它寻找空间。随着时间的进展，假设在一个系统中有了成百个库和库的各个版本库，就很难避免地址空间分裂成大量小的、未使用而又不再能使用的小洞。
- 更糟的是，对每个系统而言，库在内存中的分配都是不同的，这就引起了更多令人头痛的管理问题。
可以加载而无需重定位的代码称为位置无关代码（Position-Independent Code，PIC）。用户对 GCC 使用 -fpic 选项指示 GNU 编译系统生成 PIC 代码。共享库的编译必须总是使用该选项。编译器通过运用以下这个有趣的事实来生成对全局变量的 PIC 引用：无论我们在内存中的何处加载一个目标模块（包括共享目标模块），数据段与代码段的距离总是保持不变。因此，代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量，与代码段和数据段的绝对内存位置是无关的。
想要生成对全局变量 PIC 引用的编译器利用了这个事实，它在数据段开始的地方创建了一个表，叫做全局偏移量表（Global Offset Table，GOT）。在 GOT 中，每个被这个目标模块引用的全局数据目标（过程或全局变量）都有一个 8 字节条目。编译器还为 GOT 中每个条目生成一个重定位记录。在加载时，动态链接器会重定位 GOT 中的每个条目，使得它包含目标的正确的绝对地址。每个引用全局目标的目标模块都有自己的 GOT。
假设程序调用一个由共享库定义的函数。编译器没有办法预测这个函数的运行时地址，因为定义它的共享模块在运行时可以加载到任意位置。正常的方法是为该引用生成一条重定位记录，然后动态链接器在程序加载的时候再解析它。不过，这种方法并不是 PIC，因为它需要链接器修改调用模块的代码段，GNU 编译系统使用了一种很有趣的技术来解决这个问题，称为延迟绑定（lazy binding），将过程地址的绑定推迟到第一次调用该过程时。
延迟绑定是通过两个数据结构之间简洁但又有些复杂的交互来实现的，这两个数据结构是：GOT 和过程链接表（Procedure Linkage Table，PLT）。如果一个目标模块调用定义在共享库中的任何函数，那么它就有自己的 GOT 和 PLT。GOT 是数据段的一部分，而 PLT 是代码段的一部分。
假设我们有两个程序 A 和 B，它们都使用了同一个动态库 libfoo.so。接下来，我们以程序 A 调用函数 foo 为例来说明 GOT 和 PLT。
-
首先，在链接程序 A 的时候，A 已经知道了在 libfoo.so 中的函数 foo 的名字和地址，但它并不知道该函数实际存在于内存中的哪个地方。所以程序初始化时会写入一个初始的表项到 Got 表中，并在链接阶段创建一个包含这个函数调用的 PLT 条目，由此 PLT 表中存储着函数 foo 在共享库中的真正地址。
-
当程序第一次调用函数 foo 时，进程跳转到 PLT 表中的条目，这个 PLT 条目将会把控制权传递给共享库的动态连接器 ld-linux.so，由其完成加载函数的过程。如果该函数已经加入到内存中，则将函数入口地址存入对应的 GOT 表项中，并跳转到该函数，否则动态连接器会载入该函数并将最终的地址填充到对应的 GOT 表项。
-
之后，如果程序需要再次调用该函数，程序可以直接通过跳转到获取到的 GOT 表项来调用其函数体，而无需再访问 PLT 表。这是因为在第一次调用函数 foo 时，PLT 已经将实际的函数地址记录到 GOT 表项中了。
总之，GOT 和 PLT 都是为了实现动态链接机制而需要的。GOT 存储全局变量和函数指针，PLT 表格存储了动态库中需要调用的函数名字，并且启动共享库的 ld-linux.so 来决定符号的追踪、加载以及 GOT 表项的更新。这种间接跳转的方式确保在程序运行时可以通过 GOT 找到函数地址并使用该锚点执行正确的代码。
库打桩机制
Linux 链接器支持一个很强大的技术，称为库打桩（library interpositioning），它允许你截获对共享库函数的调用，取而代之执行自己的代码。使用打桩机制，你可以追踪对某个特殊库函数的调用次数，验证和追踪它的输入和输出值，或者甚至把它替换成一个完全不同的实现。库打桩也通常被用来结束代码执行、输出调试信息、收集性能数据等。
下面是它的基本思想：给定一个需要打桩的目标函数，创建一个包装函数，它的原型与目标函数完全一样。使用某种特殊的打桩机制，你就可以欺骗系统调用包装函数而不是目标函数了。包装函数通常会执行它自己的逻辑，然后调用目标函数，再将目标函数的返回值传递给调用者。
打桩可以发生在编译时、链接时或当程序被加载和执行的运行时。
编译时打桩
1
2
3
4
5
6
7
8
9
10
11
// int.c
#include <stdio.h>
#include <malloc.h>
int main()
{
int *p = malloc(32);
free(p);
return(0);
}
1
2
3
4
5
6
7
// malloc.h
#define malloc(size) mymalloc(size)
#define free(ptr) myfree(ptr)
void *mymalloc(size_t size);
void myfree(void *ptr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// mymalloc.c
#ifdef COMPILETIME // 这表示只有在编译时定义了宏 COMPILETIME 时，代码块中的内容才会被编译进来。
#include <stdio.h>
#include <malloc.h>
/* malloc wrapper function */
void *mymalloc(size_t size)
{
void *ptr = malloc(size);
printf("malloc(%d)=%p\n",
(int)size, ptr);
return ptr;
}
/* free wrapper function */
void myfree(void *ptr)
{
free(ptr);
printf("free(%p)\n", ptr);
}
#endif
编译和链接这个程序。
1
2
gcc -DCOMPILETIME -c mymalloc.c
gcc -I. -o intc int.c mymalloc.o
链接时打桩
Linux 静态链接器支持用 –wrap f 标志进行链接时打桩。这个标志告诉链接器，把对符号 f 的引用解析成 _ _wrap_f，还要把对符号 _ _real_f的引用解析为 f。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// mymalloc.c
#ifdef LINKTIME
#include <stdio.h>
void *__real_malloc(size_t size);
void __real_free(void *ptr);
/* malloc wrapper function */
void *__wrap_malloc(size_t size)
{
void *ptr = __real_malloc(size); /* Call libc malloc */
printf("malloc(%d) = %p\n", (int)size, ptr);
return ptr;
}
/* free wrapper function */
void __wrap_free(void *ptr)
{
__real_free(ptr); /* Call libc free */
printf("free(%p)\n", ptr);
}
#endif
上述程序中定义了__real_malloc、__real_free、__wrap_malloc和__wrap_free，由于链接时打桩技术，会在链接时对符号进行解析时，分别解析为malloc和free（即调用libc中的相应函数）。
编译链接。
1
2
3
4
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 传递给链接器，以类似的方式传递 -Wl,--wrap,free。
运行时打桩
编译时打桩需要能够访问程序的源代码，链接时打桩需要能够访问程序的可重定位对象文件。不过，有一种机制能够在运行时打桩，它只需要能够访问可执行目标文件。这个很厉害的机制基于动态链接器的 LD_PRELOAD 环境变量。
如果 LD_PRELOAD 环境变量被设置为一个共享库路径名的列表（以空格或分号分隔），那么当你加载和执行一个程序，需要解析未定义的引用时，动态链接器（LD-LINUX.SO）会先搜索 LD_PRELOAD 库，然后才搜索任何其他的库。有了这个机制，当你加载和执行任意可执行文件时，可以对任何共享库中的任何函数打桩，包括 libc.so。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// mymalloc.c
#ifdef RUNTIME
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>
/* malloc wrapper function */
void *malloc(size_t size)
{
void *(*mallocp)(size_t size);
char *error;
mallocp = dlsym(RTLD_NEXT, "malloc"); /* Get address of libc malloc */
if ((error = dlerror()) != NULL) {
fputs(error, stderr);
exit(1);
}
char *ptr = mallocp(size); /* Call libc malloc */
printf("malloc(%d) = %p\n", (int)size, ptr);
return ptr;
}
/* free wrapper function */
void free(void *ptr)
{
void (*freep)(void *) = NULL;
char *error;
if (!ptr)
return;
freep = dlsym(RTLD_NEXT, "free"); /* Get address of libc free */
if ((error = dlerror()) != NULL) {
fputs(error, stderr);
exit(1);
}
freep(ptr); /* Call libc free */
printf("free(%p)\n", ptr);
}
#endif
每个包装函数中，对 dlsym 的调用返回指向目标 libc 函数的指针。然后包装函数调用目标函数，打印追踪记录，再返回。每个包装函数中，对 dlsym 的调用返回指向目标 libc 函数的指针。然后包装函数调用目标函数，打印追踪记录，再返回。
编译运行。
1
2
3
gcc -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl
gcc -o intr int.c
LD_PRELOAD="./mymalloc.so" ./intr
