静态链接和动态链接

1. 概述

本文总结了编译过程中的链接相关的知识。模块化设计是软件开发中最常用的设计思想，链接（Linking）本质上就是把各个模块之间相互引用的部分处理好，使得各个模块之间能够正确衔接。

2. 链接过程

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

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

下面，以两个源代码文件a.c和b.c为例展开分析。

1
2
3
4
5
6
7
8
// a.c
extern int shared;

int main()
{
    int a = 100;
    swap(&a, &shared);
}
1
2
3
4
5
6
7
// 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。目前采用的比较普遍的方式为合并相同性质的节，如下图所示：

常见的链接器通常使用“两步链接（Two-pass Linking）”的方法，即：

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

2.1. 地址与空间分配

使用ld或者gcc将a.o和b.o链接起来，使用objdump工具来查看链接前后的地址分配情况。

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
$ objdump -h a.o

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         0000004f  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         00000000  0000000000000000  0000000000000000  0000008f  2**0
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  0000000000000000  0000000000000000  0000008f  2**0
                  ALLOC
  ...

$ objdump -h b.o

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
  ...

$ objdump -h ab

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  ...
  13 .text         00000202  0000000000400450  0000000000400450  00000450  2**4
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  ...
  24 .data         00000014  0000000000601028  0000000000601028  00001028  2**3
                  CONTENTS, ALLOC, LOAD, DATA
  25 .bss          00000004  000000000060103c  000000000060103c  0000103c  2**0
                  ALLOC
  ...

可以发现，链接前目标文件中所有节的VMA（Virtual Memory Address）都是0，因为虚拟空间还没有分配。链接后，可执行文件ab中各个节被分配到了相应的虚拟地址，如.text节被分配到了地址0x0000000000400450。（注意，在Linux x86-64系统中操作系统的进程虚拟地址空间的分配规则，代码段总是从0x0000000000400000开始的，另外.text节之前还有ELF Header、Program Header Table、.init等占用了一定的空间，所以就被分配到了0x0000000000400450。）

2.2. 符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。介绍一下多重定义的全局符号解析，Linux编译系统采用如下的方法解决多重定义的全局符号解析：

在编译时，编译器输出每个全局符号，或者是强（strong）或者是弱（weak），而汇编器把这个信息隐含地编码在可重定位目标文件的符号表中。根据强弱符号的定义，Linux链接器使用下面的规则来处理多重定义的符号名：

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

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

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

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

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

2.3. 重定位

链接的前两步完成之后，链接器就已经确定所有符号的虚拟地址了，那么链接器就可以根据符号的地址对每个需要重定位的指令进行地址修正。ELF文件中的重定位表（Relocation Table）专门用来保存这些与重定位相关的信息。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ objdump -r a.o

a.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
0000000000000023 R_X86_64_32       share
0000000000000030 R_X86_64_PC32     swap-0x0000000000000004
0000000000000049 R_X86_64_PC32     __stack_chk_fail-0x0000000000000004


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

可以看到每个要被重定位的地方是一个重定位入口（Relocation Entry）。利用数据结构成员包含的信息，即可完成重定位。

3. 静态链接和动态链接

3.1. 静态链接

事实上，静态链接的过程就是上文所描述的过程。在Linux中，静态链接器（static linker）ld以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的节组成，每一节都是一个连续的字节序列。

3.2. 动态链接

静态链接使得进行模块化开发，大大提供了程序的开发效率。随着，程序规模的扩大，静态链接的诸多缺点也逐渐暴露出来，如：浪费内存和磁盘空间、模块更新困难等。在静态链接中，C语言静态库是很典型的浪费空间的例子。关于模块更新，静态链接的程序有任何更新，都必须重新编译链接，用户则需要重新下载安装该程序。解决空间浪费和更新困难最简单的方法便是将程序的模块相互分割开来，形成独立文件。简而言之，就是不对那些组成程序的目标文件进行链接，而是等到程序要运行时才进行链接。

动态链接涉及运行时的链接以及多个文件的装载，必需要有操作系统的支持。因为动态链接的情况下，进程的虚拟地址空间的分布会比静态链接情况下更为复杂，还有一些存储管理、内存共享、进程线程等机制在动态链接下也会有一些微妙的变化。目前，主流操作系统都支持动态链接。在Linux中，ELF动态链接文件被称为动态共享对象（DSO，Dynamic Shared Objects），一般以.so为后缀；在Windows中，动态链接文件被称为动态链接库（Dynamic Linking Library），一般以.dll为后缀。

在Linux中，常用的C语言库的运行库glibc，其动态链接形式的版本保留在/lib目录下，文件名为libc.so。整个系统只保留一份C语言动态链接文件libc.so，所有的C语言编写的动态链接程序都可以在运行时使用它。当程序被装载时，系统的动态链接器会将程序所需要的所有动态链接库装载到进程的地址空间，并将程序中所有未解析的符号绑定到相应的动态链接库中，并进行重定位。

对于静态链接的可执行文件来说，整个进程只有一个文件要被映射，即可执行文件。而对于动态链接，除了可执行文件，还有它所依赖的共享目标文件。关于共享目标文件在内存中的地址分配，主要有两种解决方案，分别是：

  • 静态共享库（Static Shared Library）（地址固定）
  • 动态共享库（Dynamic Shared Libary）（地址不固定）

3.2.1. 静态共享库（Static Shared Library）

静态共享库的做法是将程序的各个模块统一交给操作系统进行管理，操作系统在某个特定的地址划分出一些地址块，为那些已知的模块预留足够的空间。因为这个地址对于不同的应用程序来说，都是固定的，所以称之为静态。但是静态共享库的目标地址会导致地址冲突、升级等问题。

3.2.2. 动态共享库（Dynamic Shared Libary）

采用动态共享库的方式，也称为装载时重定位（Load Time Relocation）。其基本思路是：在链接时，对所有绝对地址的引用都不作重定位，而把这一步推迟到装载时再完成。一旦模块装载地址确定，即目标地址确定，那么系统就对程序中所有的绝对地址引用进行重定位。

但是这种方式也存在一些问题。比如，动态链接模块被装载映射至虚拟空间后，指令部分是在多个进程间共享的，由于装载时重定位的方法需要修改指令，所以没有办法做到同一份指令被多个进程共享，因为指令被重定位后对于每个进程来说都是不同的。但是其中的可修改数据部分对于不同进程来说是由多个副本的，基于此，一种名为地址无关代码的技术被提出以克服这个问题。

3.2.3. 地址无关代码（PIC，Position-independent Code）

基本原理是：把指令中那些需要被修改的部分分离出来，跟数据部分放在一起，这样指令部分就可以保持不变，而数据部分可以在每个进程中拥有一个副本。共享对象模块中的地址引用按照是否为跨模块分为两类：模块内部引用、模块外部引用。按照不用的引用方式又可分为：指令引用、数据引用。以如下代码为例，可得出如下四种类型：

  • 类型1：模块内部的函数调用。
  • 类型2：模块内部的数据访问，如模块中定义的全局变量、静态变量。
  • 类型3：模块外部的函数调用。
  • 类型4：模块外部的数据访问，如其他模块中定义的全局变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int a;
extern int b;
extern void ext();

void bar()
{
    a = 1;      // 类型2：模块内部数据访问
    b = 2;      // 类型4：模块外部数据访问
}

void foo()
{
    bar();      // 类型1：模块内部函数调用
    ext();      // 类型4：模块外部函数调用
}

（1）模块内部函数调用

由于被调用的函数与调用者都处于同一模块，它们之间的相对位置是固定的。对于现代的系统来说，模块内部的调用都可以是相对地址调用，或者是基于寄存器的相对调用，所以对于这种指令是不需要重定位的。

（2）模块内部数据访问

一个模块前面一般是若干个页的代码，后面紧跟着若干个页的数据，这些页之间的相对位置是固定的，即任何一条指令与它需要访问的模块内部数据之间的相对位置是固定的，所以只需要相对于当前指令加上固定的偏移量就可以访问模块内部数据了。

（3）模块间数据访问

模块间的数据访问比模块内部稍微麻烦一些，因为模块间的数据访问目标地址要等到装载时才决定。此时，动态链接需要使用代码无关地址技术，其基本思想是把地址相关的部分放到数据段。ELF的实现方法是：在数据段中建立一个指向这些变量的指针数组，也称为全局偏移表（Global Offset Table，GOT），当代码需要引用该全局变量时，可以通过GOT中相对应的项间接引用。

当指令中需要访问变量b时，程序会先找到GOT，然后根据GOT中变量所对应的项找到变量的目标地址。每个变量都对应一个4字节的地址，链接器在装载模块时会查找每个变量所在的地址，然后填充GOT中的各个项，以确保每个指针所指向的地址正确。由于GOT本身是放在数据段的，所以它可以在模块装载时被修改，并且每个进程都可以有独立的副本，相互不受影响。

（4）模块间函数调用

对于模块间函数调用，同样可以采用类型3的方法来解决。与上面的类型有所不同的是，GOT中响应的项保存的是目标函数的地址，当模块需要调用目标函数时，可以通过GOT中的项进行间接跳转。