静态链接

程序设计的模块化是人们一直在追求的目标，因为当一个系统十分复杂的时候，我们不得不将一个复杂的系统逐步分割成小的系统以达到各个突破的目的。一个软件亦是如此，人们把每个源代码模块独立地编译，然后按照需要将它们“组装“起来，这个组装模块的过程就是链接（Linking）。链接（Linking）本质上就是把各个模块之间相互引用的部分处理好，使得各个模块之间能够正确衔接。

最基本的静态链接过程如下所示。每个模块的源代码文件（如.c）文件经过编译器编译成目标文件（Object File，一般扩展名为.o或.obj）。目标文件和 库（Library） 一起链接形成最终的可执行文件。其中，最常见的库就是运行时库（Runtime Library），它是支持程序运行的基本函数的集合。库本质上是一组目标文件的包，由一些最常用的代码编译成目标文件后打包而成。

链接过程主要包含了三个步骤：

地址与空间分配（Address and Storage Allocation）
符号解析（Symbol Resolution）
重定位（Relocation）

下面，我们通过两个源代码文件a.c和`b.c作为例子展开分析。

// 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;
}

在上述代码中，b.c定义了两个全局符号：一个是变量shared、；另一个是函数swap；a.c定义了一个全局符号：main。a.c引用了b.c中的swap和shared。接下来我们要将两个目标文件链接在一起并最终形成一个执行程文件ab。

空间与地址分配

我们知道，可执行文件中的段是由输入的目标文件中合并而来的。那么，在链接过程的产生的第一个问题便是：对于多个输入目标文件，链接器如何将它们的各个段合并到输出文件呢？或者说，输出文件中的空间如何分配给输入文件？

按序叠加

一个最简单的方案就是将输入的文件按照次序叠加起来。但是这样做的话会存在一个问题：在有很多输入文件的情况下，输出文件会有很多零散的节。这种做法非常浪费空间，因为每个节都需要有一定的地址和空间对齐要求。x86硬件的对齐要求是4KB。如果一个节的大小只有1个字节，它也要在内存在重用4KB。这样会造成大量内部碎片。所以不是一个好的方案。

相似段合并

其实，在实际的操作中我们会根据不同输入文件段的性质，将相同性质的段合并到一起，比如：将所有输入文件的 .text段合并到输出文件的 .text段，如下图所示。

其中**.bss段在目标文件和可执行文件中不占用文件的空间，但是它在装载时占用地址空间。所以链接器在合并各个段的同时，也将.bss段合并，并且分配虚拟空间。此时我们可以思考一个问题，那就是这里所谓的“空间分配”到底是什么空间？事实上，此处的空间和地址**有两层含义:

输出的可执行文件中的空间
装载后的虚拟地址中的空间

对于有实际数据的段，如.text和.data，它们在文件中和虚拟地址中都要分配空间，因为它们在这两者中都存在；对于.bss来，分配空间的意义只局限于虚拟地址空间，因为它在文件中并没有内容。我们在这里谈到的空间分配只关注于虚拟地址空间的分配，因为这关系到链接器后面的关于地址计算的步骤，而可执行文件本身的空间分配与链接的关系并不大。

现在的链接器空间分配的策略基本上都采用“合并相似节”的方法，使用这种方法的链接器一般采用一种叫 两步链接（Two-pass Linking） 的方法。即整个链接过程分为两步：

第一步地址与空间分配
扫描所有的输入目标文件，获得它们的各个段的长度、属性、位置，并将输入目标文件中的符号表中所有的符号定义和符号引用收集起来，统一放到一个全局的符号表。这一步，链接器能够获得所有输入目标文件的段的长度，并将它们合并，计算出输出文件中各个段合并后的长度与位置，并建立映射关系。
第二步符号解析与重定位
使用第一步中收集到的所有信息，读取输入文件中段的数据、重定位信息，并且进行符号解析与重定位、调整代码、调整代码中的地址等。事实上，第二步是链接过程的核心，尤其是重定位。

我们可以使用下述的命令获取链接前后地址的分配情况：

1 2	$ gcc -c -fno-builtin -fno-stack-protector *.c $ ld a.o b.o -e main -o ab

-e main 表示将main函数作为程序入口，ld默认的程序入口为_start。
-o ab 表示链接输出文件名为ab，默认为a.out。

$ objdump -h a.o

a.o:     file format elf64-x86-64

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         0000002e  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         00000000  0000000000000000  0000000000000000  0000006e  2**0
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  0000000000000000  0000000000000000  0000006e  2**0
                  ALLOC
  3 .comment      0000002a  0000000000000000  0000000000000000  0000006e  2**0
                  CONTENTS, READONLY
  4 .note.GNU-stack 00000000  0000000000000000  0000000000000000  00000098  2**0
                  CONTENTS, READONLY
  5 .eh_frame     00000038  0000000000000000  0000000000000000  00000098  2**3
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, DATA
$ objdump -h b.o

b.o:     file format elf64-x86-64

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         0000004b  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .data         00000004  0000000000000000  0000000000000000  0000008c  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  0000000000000000  0000000000000000  00000090  2**0
                  ALLOC
  3 .comment      0000002a  0000000000000000  0000000000000000  00000090  2**0
                  CONTENTS, READONLY
  4 .note.GNU-stack 00000000  0000000000000000  0000000000000000  000000ba  2**0
                  CONTENTS, READONLY
  5 .eh_frame     00000038  0000000000000000  0000000000000000  000000c0  2**3
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, DATA
$ objdump -h ab

ab:     file format elf64-x86-64

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         00000079  00000000004000e8  00000000004000e8  000000e8  2**0
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .eh_frame     00000058  0000000000400168  0000000000400168  00000168  2**3
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  2 .data         00000004  0000000000601000  0000000000601000  00001000  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  3 .comment      00000029  0000000000000000  0000000000000000  00001004  2**0
                  CONTENTS, READONLY

可以发现，链接前目标文件中所有段的 VMA（Virtual Memory Address） 都是0，因为虚拟空间还没有分配。链接后，可执行文件ab中各个段被分配到了相应的虚拟地址，如.text节被分配到了地址00000000004000e8。

那么，为什么链接器要将可执行文件ab的.text节分配到00000000004000e8？而不是从虚拟空间的0地址开始分配呢？这涉及到操作系统的进程虚拟地址空间的分配规则。在Linux x86-64系统中，代码段总是从0x0000000000400000开始的，另外.text节之前还有ELF Header、Program Header Table、.init等占用了一定的空间，所以就被分配到了00000000004000e8。

符号解析与重定位

重定位

在分析符号解析和重定位之前，我们先来看看a.o中是怎么使用外部符号的，也就是说我们在a.c的源程序里面使用shared变量和swap函数，那么编译器将在a.c编译成指令时，它如何访问shared变量和调用swap函数？

1	$ objdump -d a.o

a.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 10          	sub    $0x10,%rsp
   8:	c7 45 fc 64 00 00 00 	movl   $0x64,-0x4(%rbp)
   f:	48 8d 45 fc          	lea    -0x4(%rbp),%rax
  13:	48 8d 35 00 00 00 00 	lea    0x0(%rip),%rsi        # 1a <main+0x1a>
  1a:	48 89 c7             	mov    %rax,%rdi
  1d:	b8 00 00 00 00       	mov    $0x0,%eax
  22:	e8 00 00 00 00       	callq  27 <main+0x27>
  27:	b8 00 00 00 00       	mov    $0x0,%eax
  2c:	c9                   	leaveq
  2d:	c3                   	retq

程序的代码里面使用的都是虚拟地址，在未进行空间分配之前main的地址为0000000000000000，等到空间分配完成后，各个函数才会确定自己在虚拟地址空间中的位置。

从上述反汇编的结果可以看出a.o共定义了一个函数main。这个函数占用0x2d个字节，共12条指令；最左边那列是每条指令的偏移量，每一行代表一条指令。当源代码被编译成目标文件时，编译器并不知道shared和swap的地址，因为它们定义在其他目标文件中，所以编译器就暂时把地址0看作shared的地址，我们就看到编译器将有效地址即，0传送到指定的的寄存器（13: 48 8d 35 00 00 00 00 lea 0x0(%rip),%rsi）。

另一个是偏移为0x22的指令的一条调用指令，它其实表示对swap函数的调用。这条指令共5个字节，前面的0xE8是操作码，后面的四个字节就是被调用函数的相对于调用指令的下一条指令的偏移量。在未重定位之前，相对偏移量被置为0。紧跟着这条callq指令后面的那条指令为move指令，move指令的地址为0x27。所以这条指令的实际调用地址为0x27。实际上0x27存放的并不是swap函数的地址，和前面的shared一样是一个假地址，真正的地址计算工作留给了链接器。

1	$ objdump -d ab

ab:     file format elf64-x86-64


Disassembly of section .text:

00000000004000e8 <main>:
  4000e8:	55                   	push   %rbp
  4000e9:	48 89 e5             	mov    %rsp,%rbp
  4000ec:	48 83 ec 10          	sub    $0x10,%rsp
  4000f0:	c7 45 fc 64 00 00 00 	movl   $0x64,-0x4(%rbp)
  4000f7:	48 8d 45 fc          	lea    -0x4(%rbp),%rax
  4000fb:	48 8d 35 fe 0e 20 00 	lea    0x200efe(%rip),%rsi        # 601000 <shared>
  400102:	48 89 c7             	mov    %rax,%rdi
  400105:	b8 00 00 00 00       	mov    $0x0,%eax
  40010a:	e8 07 00 00 00       	callq  400116 <swap>
  40010f:	b8 00 00 00 00       	mov    $0x0,%eax
  400114:	c9                   	leaveq
  400115:	c3                   	retq

0000000000400116 <swap>:
  400116:	55                   	push   %rbp
  400117:	48 89 e5             	mov    %rsp,%rbp
  40011a:	48 89 7d f8          	mov    %rdi,-0x8(%rbp)
  40011e:	48 89 75 f0          	mov    %rsi,-0x10(%rbp)
  400122:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  400126:	8b 10                	mov    (%rax),%edx
  400128:	48 8b 45 f0          	mov    -0x10(%rbp),%rax
  40012c:	8b 00                	mov    (%rax),%eax
  40012e:	31 c2                	xor    %eax,%edx
  400130:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  400134:	89 10                	mov    %edx,(%rax)
  400136:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  40013a:	8b 10                	mov    (%rax),%edx
  40013c:	48 8b 45 f0          	mov    -0x10(%rbp),%rax
  400140:	8b 00                	mov    (%rax),%eax
  400142:	31 c2                	xor    %eax,%edx
  400144:	48 8b 45 f0          	mov    -0x10(%rbp),%rax
  400148:	89 10                	mov    %edx,(%rax)
  40014a:	48 8b 45 f0          	mov    -0x10(%rbp),%rax
  40014e:	8b 10                	mov    (%rax),%edx
  400150:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  400154:	8b 00                	mov    (%rax),%eax
  400156:	31 c2                	xor    %eax,%edx
  400158:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  40015c:	89 10                	mov    %edx,(%rax)
  40015e:	90                   	nop
  40015f:	5d                   	pop    %rbp
  400160:	c3                   	retq

经过修正后，shared和swap的地址分别为0x200efe和400116。

重定位表

事实上，重定位过程也伴随着符号的解析过程。链接的前两步完成之后，链接器就已经确定所有符号的虚拟地址了，那么链接器就可以根据符号的地址对每个需要重定位的指令进行地址修正。

那么链接器如何知道哪些指令是要被调整的呢？事实上，我们前面提到的ELF文件中的 重定位表（Relocation Table） 专门用来保存这些与重定位相关的信息。

对于可重定位的ELF文件来说，它必须包含重定位表，用来描述如何修改相应段的内容。对于每个要被重定位的ELF段都有一个对应的重定位表。如果.text段需要被重定位，则会有一个相对应叫.rel.text的段保存了代码段的重定位表；如果.data段需要被重定位，则会有一个相对应的.rel.tdata的段保存了数据段的重定位表。

我们可以使用objdump工具来查看目标文件中的重定位表：

$ objdump -r a.o
  
a.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
0000000000000016 R_X86_64_PC32     shared-0x0000000000000004
0000000000000023 R_X86_64_PLT32    swap-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE
0000000000000020 R_X86_64_PC32     .text

我们可以看到每个要被重定位的地方是一个 重定位入口（Relocation Entry）。重定位入口的偏移(Offset)表示该入口在要被重定位的段中的位置，RELOCATION RECORDS FOR [.text]表示这个重定位表式代码段的重定位表。对照前面反汇编结果可以知道，这里的0x16和0x23分别是代码段中lea和callq指令的地址部分。重定位表的结构也简单，它是一个Elf64_Rel结构的数组，每个数组元素对应一个重定位入口。Elf64_Rel的定义如下：

typedef struct
{
  Elf64_Addr    r_offset;               /* Address */
  Elf64_Xword   r_info;                 /* Relocation type and symbol index */
} Elf64_Rel;
// or
typedef struct
{
  Elf64_Addr    r_offset;               /* Address */
  Elf64_Xword   r_info;                 /* Relocation type and symbol index */
  Elf64_Sxword  r_addend;               /* Addend */
} Elf64_Rela;

符号解析

当我们直接使用ld来链接a.o，而不链接b.o时。链接器就会发现shared和swap两个符号没有被定义，没办法完成链接工作：

$ ld a.o
ld: warning: cannot find entry symbol _start; defaulting to 00000000004000b0
a.o: In function `main':
a.c:(.text+0x16): undefined reference to `shared'
a.c:(.text+0x23): undefined reference to `swap'

其实重定位过程也伴随着符号的解析过程。重定位过程中，每个重定位的入口都是对一个符号的引用，那么当链接器需要对某个符号的引用进行重定位时，他就要确定这个符号的目标地址。这时候链接器就会去查找由所有输入目标文件的符号表组成的全局符号表，找到相应的符号进行重定位。

比如我们查看a.o的符号表：

$ readelf -s a.o

Symbol table '.symtab' contains 12 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS a.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    6
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
     8: 0000000000000000    46 FUNC    GLOBAL DEFAULT    1 main
     9: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND shared
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
    11: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND swap

可以看到shared和swap都是UND，即undefined未定义类型，这种未定义的符号都是因为该目标文件中有关于它们的重定位项。所以在链接器扫描完所有的输入目标文件之后，所有这些未定义的符号都应该能够在全局符号表中找到，否则链接器就报符号未定义错误。

多重定义的全局符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。对那些和引用定义在相同模块的局部符号的引用，符号解析是非常简单的。编译器只允许每个模块中每个局部符号有一个定义。静态局部变量也会有本地链接器符号，编译器还要确保它们拥有唯一的名字。

然而，对于全局符号的解析要复杂得多。当编译器遇到一个不是在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。如果链接器在它的任何输入模块中都找不到这个被引用符号的定义，就输出一条错误信息并终止。

另一方面，对全局符号的解析，经常会面临多个目标文件可能会定义相同名字的全局符号。这种情况下，链接器必须要么标志一个错误，要么以某种方法选出一个定义并抛弃其他定义。

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，有些是局部符号（只对定义该符号的模块可见），有些是全局符号（对其他模块也可见）。如果多个模块定义同名的全局符号，该如何进行取舍？

Linux编译系统采用如下的方法解决多重定义的全局符号解析：

在编译时，编译器想汇编器输出每个全局符号，或者是强（strong）或者是弱（weak），而汇编器把这个信息隐含地编码在可重定位目标文件的符号表中。

根据强弱符号的定义，Linux链接器使用下面的规则来处理多重定义的符号名：

规则1：不允许有多个同名的强符号。
规则2：如果有一个强符号和多个弱符号同名，则选择强符号。
规则3：如果有多个弱符号同名，则从这些弱符号中任意选择一个。

另一方面，由于允许一个符号定义在多个文件中，所以可能会导致一个问题：如果一个弱符号定义在多个目标文件中，而它们的类型不同，怎么办？这种情况主要有三种：

情况1：两个或两个以上的强符号类型不一致。
情况2：有一个强符号，其他都是弱符号，出现类型不一致。
情况3：两个或两个以上弱符号类型不一致。

其中，情况1由于多个强符号定义本身就是非法的，所以链接器就会报错。对于后两种情况，编译器和链接器采用一种叫 COMMON块（Common Block ） 的机制来处理。其过程如下：

首先，编译器将未初始化的全局变量定义为弱符号处理。对于情况3，最终链接时选择最大的类型。对于情况2，最终输出结果中的符号所占空间与强符号相同，如果链接过程中有弱符号大于强符号，链接器会发出警告。

参考资料

Executable and Linkable Format
《程序员的自我修养——链接、装载与库》
ELF man page