当我们有两个目标文件时我们如何将它们链接起来形成可执行文件？这个过程中发生了什么？我们将使用下面两段源代码展开分析：

/* a.c */
extern int shared;

int main()
{
    int a = 100;
    swap(&a, &shared);
}

/* b.c */
int shared = 1;

void swap(int *a, int *b)
{
    *a ^= *b ^= *a ^= *b;
}

使用gcc -c 编译得到两个目标文件a.o 和b.o，a 里面引用到了b 里面的swap 和shared。接下来我们就要把a 和b 两个目标文件链接成可执行文件ab。

空间与地址分配

对于链接器来说，整个连接过程中，就是将目标文件的各个段合并到可执行文件的各个段中， 那么目标文件中各个段时怎么合并的呢？

按序叠加

最简单的方案就是将目标文件的段按照次序叠加起来。

但是这样做会非常浪费空间。假如有成百上千个这样的段，每个段都需要有一定的地址空间和对齐的要求，就会造成内存空间大量的内部碎片。

相似段合并

一个更实际的做法就是将相同性质的段合并到一起。

链接器为目标文件分配地址和空间，这里地址和空间有两个含义：

• 输出可执行文件中的空间

• 装载后虚拟地址中的虚拟地址空间

对于有实际数据的段，比如.text .data 来说，它在文件中和虚拟地址中都要分配空间。而对于.bbs 段来说分配空间只局限于虚拟地址空间，它在文件中并没有内容。

现在的链接器空间分配策略基本上都是采用相似段合并，这种策略一般都采用两步链接（Two-pass Linking） 的方法。也就是说连接过程分为下面两步。

空间与地址分配

扫描所有的输入目标文件，获得各个段的长度、属性、位置，并将目标文件中所有符号定义和符号引用收集，统一放到全局符号表。这样链接器能够计算出输出文件中各个段合并后的长度和位置，并建立影射关系。

符号解析与重定位

这一步是链接过程的核心，特别是重定位过程。我们使用链接器将输入文件链接起来$ld a.o b.o -e main -o ab，并使用objdump 查看连接后地址分配情况。

我们可以看到在链接之前VMA(虚拟地址 Virtual Memory Address)都是0，因为虚拟空间还没被分配。链接之后各个段都被分配到了相应的虚拟地址。

符号地址的确定

在上面的扫描和空间地址分配阶段，这个时候输入文件中各个段在连接后的虚拟地址已经就确定了。因为各个符号在段内的相对位置是固定的，但是链接器需要给每个符号加上一个偏移量，使符号能够调整到正确的虚拟地址。

符号解析与重定位

重定位

我们先用命令$objdump -d a.o 看下目标文件a.o 的反汇编结果：

因为是目标文件所以还未进行空间分配，目标文件代码段中起始地址为0x00000000，等空间分配完成以后，各个函数才会确定自己在虚拟空间中的位置。

我们已用粗体标记出了两个引用shared 和swap 的位置。在a.c 源码在编译时成目标文件时，编译器并不知道shared 和swap 的地址，因为它们被定义在其他目标文件中，所以编译器暂时吧地址0看作是shared的地址。而swap前面的0xe8是操作码，这条指令是近址相对位移调用指令（Call near,relative,displacement relative to next instruction） 在没有重定位之前，相对偏移被置为0xFFFFFFFC（小端），它是常量-4 的补码形式。这条指令call 的下一条指令为add，相对于add 指令偏移-4 的地址为0x2b - 4 = 0x27。所以这条指令的实际调用地址为0x27。我们可以看到0x27 存放的是0xFFFFFFFC并不是swap 的函数地址。这也是个假地址。

我们在通过命令$objdump -d ab 查看可执行文件ab 反汇编的代码段：

我们可以看到两个需要重定位的符号都已经被修正了，shared 的地址的确是0x08049108，再来看下swap，call 指令下一条指令为add 地址是0x080480bf，所以相对于add 指令偏移0x00000009 的地址为0x080480bf + 9 = 0x080480c8 刚好是swap 的函数地址。

重定位表

上篇文章提到过重定位相关的信息保存在重定位表（Relocation Table） 中，它是目标文件中的一个或者多个段。比如.text 段有需要被重定位的地方，那么会有一个相对应的段.rel.text 保存.text 段的重定位信息。

我们用命令$objdump -r a.o 查看a.o 的重定位表：

RELOCATION RECORDS FOR [.text] 表示这个重定位表是.text 段的重定位表，每个要被重定位的地方叫做一个重定位入口（Relocation Entry），我们可以看到a.o 中有两个重定位入口。重定位入口的偏移（Offset） 表示该入口在被重定位段中（这里也就是指.text段）的位置。

符号解析

我们直接使用命令$ld a.o 来链接a.o，而不将b.o 作为输入：

这时我们发现有两符号没有被定义，无法完成链接。

重定位的过程也伴随着符号解析的过程，每个目标文件都可能定义一些符号，或者引用其他目标文件定义的符号。链接器会查找由所有目标文件符号表组成的全局符号表，找到相应的符号后进行重定位。

指令修正方式

不同处理器指令寻址的方式也不同，但是对于32位x86平台下的ELF文件的重定位入口所修正的指令寻址方式只有两种：

宏定义	值	重定位修正方法
R_386_32	1	绝对寻址修正 S + A
R_386_PC32	2	相对寻址修正 S + A - P

• A = 保存在被修正位置的值

• P = 被修正的位置（相对于段开始的偏移量或者虚拟地址）

• S = 符号的真实地址，即由r_info 高24位指定的符号的实际地址

我们假设a.o 和b.o 连接成可执行文件后main 函数的虚拟地址为0x1000，swap 函数的虚拟地址为0x2000，shared 变量的虚拟地址为0x3000。

绝对寻址修正

上文图中可以看到，a.o 的第一个重定位入口即偏移为0x18的mov指令的的修正方式为R_386_32，它修正后的结果应该是S + A。

• S 是符号shared 的实际地址，即0x3000。

• A 是被修正位置的值，即0x00000000。（上文目标文件a.o 反汇编代码）

所以这个重定位入口修正后地址为：0x3000 + 0x00000000 = 0x3000。

相对寻址修正

a.o 第二个重定位入口即偏移为0x26 这条call 指令的修正方式为R_386_PC32，它修正的结果应该是 S + A - P。

• S 是符号swap 的实际地址，即0x2000

• A 是被修正位置的值，即0xFFFFFFFC（-4）

• P 为被修正的位置，当链接成可执行文件时，这个值应该是被修正位置的虚拟地址，即0x1000 + 0x27。

所以这个重定位入口修正后的地址为：0x2000 + (-4) - (0x1000 + 0x27) = 0xFD5。这条相对位移调用指令调用的地址是下一条指令的起始地址加上偏移量，即：0x102b + 0xfd5 = 0x2000，刚好是swap 函数地址。

从这两个例子介意看出，绝对寻址修正和相对寻址修正的区别就是绝对寻址修正后的地址为该符号的真实地址，相对寻址修正后的地址为符号距离被修正位置的地址差。

COMMON 块

链接器本身并不支持符号的类型，它只知道符号的名字并不知道类型。当定义多个弱符号但类型不一致时主要分三种情况：

• 两个或两个以上强符号类型不一致

• 有一个是强符号其他都是弱符号，出现类型不一致

• 两个或两个以上弱符号类型不一致

第一种情况无需处理，因为多个强符号定义本身就是违法的。链接器主要处理后两种情况。编译器和链接器都支持一种叫COMMON块（Common Block） 机制，当不同的目标文件需要的COMMON 空间大小不一致时，以最大的为准。所以对于多个弱符号类型不一致时，以占用空间最大的为准。但是如果其中一个为强符号时，那么最终输出结果符号所占用的空间与强符号相同。

所以为什么编译器不直接把未初始化的全局变量也当作未初始化的局部静态变量一样处理，为它在BBS 段分配空间，而是标记为一个COMMON 类型呢？因为编译器编译时弱符号（未初始化的全局变量就是典型的弱符号）最终所占的空间是未知的，可能在其他编译单元中该符号所占的空间更大。因为所需空间大小未知，所以编译器无法为该符号在BBS 段分配空间，但是在链接时可以确定弱符号大小，所以可以在最终输出文件中的BBS 段为其分配空间。所以总体来看，未初始化全局变量最终还是被放在BBS 段的。

静态库链接

一个静态库可以简单看成一组目标文件的集合，即很多目标文件经过压缩打包后形成的一个文件。

比如我们的源代码使用了静态库中的函数，在链接时链接器会去静态库中查找使用到的符号，把符号所在的目标文件链接。而这个目标文件很有可能还以来其他目标文件。幸好链接器会处理这些繁琐的事务，链接器会自动寻找所有需要的符号及它们所在的目标文件，将这些目标文件从静态库中解压出来，最终连接在一起成为一个可执行文件。

静态库里一般一个目标文件只包含一个函数，因为链接器在链接静态库文件的时候以目标文件为单位的。如果有很多函数放在一个目标文件中，很有可能将很多没用的函数一起链接进了输出结果中，这样会导致空间浪费。

引用

程序员的自我修养