链接概述

经预处理器->编译器->汇编器处理后，源文件可被转化为一组可重定位目标文件，链接器将它们组合起来形成可执行文件。

每个可重定位目标文件由不同的“代码节”和“数据节”组成，每一个节都是一个连续的字节序列。由于每个可重定位目标文件的生成是独立的，因此组合时会出现两个问题：

一是若某个可重定位目标文件中使用了外部的全局变量，而此变量定义于另一个可重定位目标文件中，怎么办？

二是生成目标文件时如何确定地址。链接器生成的可执行文件在实际运行时，需要由加载器将其代码及数据复制到内存，再将控制转移到此程序的开头，若每个链接前的目标文件都以0为起始地址，势必会造成重合，怎么办？

这就是链接器要做的两件事：符号解析与重定位

符号解析：目标文件中可能会定义或引用一定的函数，全局变量或静态变量，这些都是所谓的“符号”，符号解析的目的就是把符号的定义和引用关联起来。
重定位：如上所述，第二个问题的解决方案就是重定位，链接器会把符号的定义与内存位置相关联，重定位时将符号的引用指向此内存位置。

目标文件

目标文件有三种形式：

可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件结合起来，创建一个可执行目标文件。
可执行目标文件。包含二进制代码和数据，其形式可以被直接复制到内存并执行。
共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态的加载进内存并链接。

编译器和汇编器生成可重定位目标文件（包括共享目标文件）。链接器生成可执行目标文件。从技术上来说，一个目标模块就是一个字节序列，而一个目标文件就是一个以文件形式存放在磁盘中的目标模块。

目标文件是按照特定的目标文件格式来组织的，各个系统的目标文件格式都不相同。而我们主要讨论的就是ELF（可执行可链接格式）。

可重定位目标文件

下图展示了一个典型的ELF可重定位目标文件的格式。

ELF头：以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。其中包括ELF头的大小、目标文件的类型（如可重定位、可执行或者共享的）、机器类型（如x86-64）、节头部表的文件偏移，以及节头部表中条目的大小和数量。不同节的位置和大小是由节头部表描述的，其中目标文件中每个节都有一个固定大小的条目。
.text：已编译程序的机器代码。
.rodata：只读数据，比如printf语句中的格式串和开关语句的跳转表。
.data：已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中，既不出现在.data节中，也不出现在.bss节中。
.bss：未初始化的全局和静态C变量。，以及所有被初始化为0的全局或静态变量。在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。目标文件格式区分已初始化和未初始化变量是为了空间效率：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始值为0。
.symtab：一个符号表，存放在程序定义和引用的函数和全局变量的信息。其不包含局部变量的条目。
.rel.text：一个.text节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
.rel.data：被模块引用或定义的所有全局变量的重定位信息。
.debug：一个调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C源文件。
.line：原始C源程序中的行号和.text节中机器指令之间的映射。只有以-g选项调用编译器驱动程序，才会得到这张表。
.strtab：一个字符串表，其内容包括.symtab和.debug中的符号表，以及节头部中的节名字。字符串表就是以null结尾的字符串的序列。

符号和符号表

每个可重定位目标模块m都有一个符号表，它包含m定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

由模块m定义并能被其他模块m引用的全局符号。全局链接器符号对应于非静态的C函数和全局变量。
由其他模块定义并被模块m引用的全局符号。这些符号称为外部符号，对应于在其他模块中定义的非静态C函数和全局变量。
只被模块m定义和引用的局部符号。它们对应于带static属性的C函数和全局变量。这些符号在模块m中任何位置都可见，但是不能被其他模块引用。

符号解析

当编译器遇到一个不是当前模块定义的符号时，会生成一个链接器符号表条目，并交给链接器处理。链接器会在所有输入模块中寻找其定义，找不到时报错并终止。

多重定义的全局符号

若出现多个模块定义同名的全局符号怎么办？

Linux系统的方法：编译器向汇编器输出全局变量对应的符号时，会标记是“强”符号(函数和已初始化的全局变量)还是“弱”符号(未初始化的全局变量)，注意，静态变量独属于本模块，没有多重定义的问题，无需标记。汇编器将此信息编码在符号表内，链接器在链接时根据以下规则进行处理：

不允许有多个同名的强符号
如果有一个强符号和多个弱符号同名，选强符号。
若多个弱符号同名，随机选一个。

/* foot5.c */
#include <stdio.h>
void f(void);

int y = 15212;
int x = 15213;

int main()
{
    f();
    printf("x = 0x%x y = 0x%x \n", x, y);
    return 0;
}

/* bar5.c */
double x;

void f()
{
    x = -0.0;
}

double类型是8个字节，而int类型是4个字节。在系统中，xd地址是0x601020，y的地址是0x601024.因此，bar5.c的第6行中的赋值x=-0.0将用负零的双精度浮点表示覆盖内存中x和y的位置。

静态链接

所有的编译系统都提供一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库，它可以用链接器的输入。当链接器构造一个输出的可执行文件时，它只复制静态库里被应用程序引用的目标模块。

相关的函数可以被编译为独立的目标模块，然后封装成一个单独的静态库文件。然后，应用程序可以通过在命令行上指定单独的文件来使用这些在库中定义的函数。比如，使用C标准库和数学库中函数的程序可以用如下的命令行来编译和链接：

1	linux> gcc main.c /usr/lib/libm.a /usr/lib/libc.a

在链接时，链接器将只复制被程序引用的目标模块，这就减少了可执行文件在磁盘和内存中的大小。另一方面，应用程序员只需要包含较少的库文件的名字（实际上，C编译器驱动程序总是传送libc.a给链接器，所有前面提到的对libc.a的引用是不必要的）。

例子：

要创建这些函数的静态库，我们要使用AR工具，如下：

为了使用这个库，我们编写一个应用：

随后编译和链接输入文件main.o和libvector.a：

下图概括了链接器的行为。-static参数告诉编译器驱动程序，链接器应该构建一个完全链接的可执行目标文件。它可以加载到内存并运行，在加载时无须更进一步的链接。-lvector参数libvector.a的缩写。-L.参数告诉链接器在当前目录下查找lib-vector.a。

当链接器运行时，它判定main2.o引用了addvec.o定义的addvec符号，所以复制addvec.o到可执行文件。因为程序不引用任何由multvec.o定义的符号，所以链接器就不会复制这个模块到可执行文件。链接器还会复制libc.a中的printf.o模块，以及许多C运行时系统中的其他模块。

重定位

链接器在符号解析完成后开始进行重定位。重定位由两部分组成：

重定位节和符号定义。在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。
重定位节中的符号引用。链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。

重定位条目

无论何时汇编器遇到对最终位置的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码的重定位条目放在.rel.text中。已初始化数据的重定位条目放在.rel.data中。

上图展示了ELF重定位条目的格式。offset是需要被修改的引用的节偏移。symbol标识被修改引用应该指向的符号。types告知链接器如何修改新的引用。addend是一个有符号常数，一些类型的重定位要使用它对被修改引用的值做偏移调整。

ELF定义了32种不同的重定位类型，主要关心两种基本重定位类型：

R_X86_64_PC32。重定位一个使用32位PC相对地址的引用。
R_X86_64_32。重定位一个使用32位PC绝对地址的引用。

重定位符号引用

例子如下：

main函数引用了两个全局变量符号：array和sum。

重定位PC相对引用

全局符号sum，重定位条目如下：

假设链接器已经确定运行时.text节的地址为0x4004d0，此时：

节偏移为r.offset = 0xf，因此，sum引用的内存地址位于0x4004d0 + 0xf = 0x4004df处，即汇编代码中的第6行，位于e8后面，注意0xe8是指令的操作码。

r.symbol代表sum定义处的运行时地址，假设为0x4004e8。

r.type = R_X86_64_PC32,代表此时为相对引用。

r.addend用作偏移调整，这里是-4，我个人的理解是这代表了sum引用的内存地址到下一条指令地址的偏差，比如这里sum引用的内存地址是0x4004df，PC要执行的下一条指令的地址为0x4004e3(汇编代码中第8行)

综上，可以这么理解：由重定位条目sum我们可以定位到需要修改的引用地址为0x4004df,由r.addend可以定位到下一条指令的地址0x4004df - (-4) = 0x4004e3,这个地址与sum定义处的运行时地址相差0x4004e8 - 0x4004e3 = 0x5。因此重定位时，汇编代码第6行的指令会被改为：

（这里的表示方法是小端法，高字节放高字节，低字节放低地址）

运行时，执行到这条call指令时，PC值为0x4004e3(即下一条指令的地址)，call指令执行时，这里用PC的值和05 00 00 00决定跳转后的地址，步骤如下：

将PC压栈
PC <— PC + 0x5 = 0x4004e3 + 0x5 = 0x4004e8

此时会跳转到sum定义处的地址，执行的下一条指令就是sum例程的第一条指令。

重定位绝对引用

全局符号array,其重定位条目如下：

对array的引用位于汇编代码第4行，这是一条mov指令，起始于0x4004d0 + 0x9 = 0x4004d9处，它有1字节的操作码0xbf。

r.offset = 0xa，告诉链接器要修改位于0x4004d0 + 0xa = 0x4004da处的array引用地址

假设已经确定array定义地址为0x601018，个人理解如下：由于这里是一条mov指令，不像call指令一样，call指令执行时是根据下一条指令地址(存于PC)来决定当前call指令中的跳转值的，是相对跳转，而mov指令是数据传送指令，直接将数据存入寄存器，无需作相对跳转，因此相应的r.addend = 0,也因此重定位时直接修改此指令中的数据值即可，以下是重定位后对应的汇编代码：

可执行目标文件

可执行目标文件的格式与之前的可重定位目标文件类似。

ELF可执行目标文件被设计得很容易加载到内存，可执行文件的连续的片被映射到连续的内存段。程序头部表描述了这种映射关系。

上图为可执行目标文件的程序头部表，前两行对应代码段，flags r-x代表有读/执行权限，此段开始于内存地址0x400000处，总共占内存大小为0x69c个字节，并且被初始化为可执行目标文件的头0x69c个字节，其中包括ELF头、程序头部表以及.init、.text和.rodata节。

后两行表示数据段有读/写访问权限，开始于0x600df8处，总共占内存大小为0x230个字节，可以推出.data节始于0x600df8 - 0xdf8 = 0x600000处，目标文件中大小为0x228字节，为什么会比总共占内存小0x230 - 0x228 = 8个字节？因为.bss节的数据只是占位符，位于可重定位目标文件时不占空间，链接成可执行文件后会为其初始化，分配内存空间。

加载可执行目标文件

运行可执行目标文件，是通过调用加载器来实现的，加载器会将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程叫加载。

每个Linux程序都有一个运行时内存映像，类似上图所示。在Linux x86-64系统中，代码段总是从0x400000处开始，后面是数据段。运行时堆在数据段之后，通过调用malloc库往上增长。堆后面的区域是为共享模块保留的。用户栈总是从最大的合法用户地址（2^48 - 1）开始，向较小内存地址增长。栈上的区域，从地址2^48开始，是为内核中的代码和数据保留的，所谓内核就是操作系统驻留在内存的部分。

当加载器运行时，它创建内存映像。在重新头部表的引导下，加载器将可执行文件的片复制到代码段和数据段。接下来，加载器跳转到程序的入口点，也就是_start函数的地址。这个函数是在系统目标文件ctrl.o中定义的，对所有的C程序都是一样的。 _start函数调用系统启用函数__libc_start_main，该函数定义在linc.so中。它初始化执行环境。调用用户层的main函数，处理main函数的返回值，并且在需要的时候把控制返回给内核。