【CSAPP笔记】13. 链接

下面就要进入本书的第二部分——在系统上运行程序。书的第一部分，主要是研究单个应用程序，关注的是数据类型、机器指令、程序性能、存储器系统等话题。在书的第二部分，我们继续对计算机系统的探索。现代操作系统与硬件合作，（进程的概念、虚拟存储器）为每个程序提供一种假象，好像这个程序是计算机上唯一运行的程序。实际上在任何时间点，计算机上都有多个程序在运行。

链接（Linking）是将各种代码和数据收集起来组合成一个单一文件的过程。链接是由链接器（Linker）完成的。链接器在软件开发中扮演着一个关键的角色，因为它使分离编译成为可能——我们不用将一个大型程序组织为一个巨大的源文件，而是把它分解为更小、更好管理的模块，我们可以独立修改和编译这些模块。当我们修改一个模块时，只需重新编译这个模块，重新链接即可，不必编译其他文件。

特别是在现在的 IDE 都比较发达的情况下，链接通常是默默无闻的。当我们写好代码，按下“编译并运行”的按键时，我们通常不会很注意链接的过程。那学习链接的概念有什么好处呢？

• 帮助你构造大型程序
• 避免一些危险的编程错误
• 了解语言的作用域规则
• 理解其他重要系统概念，（加载和运行程序、虚拟存储器、分页、存储器映射、共享库）

编译系统

• 预处理器（cpp）：根据 # 开头的的命令，修改原始的 C 程序。会将源代码hello.c转变为hello.i，是被修改后的源文件。
• 编译器（cc1）：将文本文件hello.i翻译成hello.s，它就是 C 代码对应的汇编语言程序。汇编程序是很有用的，它以一种标准的文本格式描述低级的机器语言指令，也就为不同高级语言的不同编译器提供了通用的输出语言。
• 汇编器（as）：将hello.s翻译成机器语言指令，并打包成可重定位目标程序（relocatable object program）的形式，保存在hello.o中。hello.o是一个二进制文件，字节编码是机器语言指令。如果直接用文本编辑器打开二进制文件，将会看到乱码。
• 链接器（ld）：将对象程序hello.o和所需要的静态库lib.a经过链接器的处理，最终成为一个可执行目标文件。例如，这个 hellowolrd 程序用到了函数 printf，这个函数就存在一个名为 printf.o 的单独编译好的目标文件。链接器就负责合并两个目标文件，得到一个可执行目标文件（executable object file），简称可执行文件hello.exe
• 加载器（loader，shell 调用）：将可执行文件加载到内存中执行。

假设我们写了两个 C 语言代码，分别是main.c和sum.c，前者中代码用到了后者中定义的函数。两者分别经过编译过程（cpp、cc1、as）之后，生成可重定位目标文件main.o和sum.o，最后，执行链接操作：

ld -o sum main.o sum.o

就得到可执行文件sum。

链接的基本知识

下面来了解一些关于链接的术语。

静态链接

Unix 下 ld 程序，叫做静态链接器，以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接，可以加载运行的可执行目标文件做为输出。

目标文件

三种形式：

• 可重定位目标文件。包含二进制代码和数据。可以在链接时与其他可重定位文件结合起来，创建一个可执行目标文件
• 可执行目标文件，可以被拷贝到存储器中执行。
• 共享目标文件，一类特殊的可重定位目标文件，可以在加载或运行时动态地加载到存储器中并链接。

目标文件纯粹是字节块的集合，有的块包含程序代码，有的保存数据，或者指导链接器和加载器的数据结构。链接器对目标机器知之甚少，编译器和汇编器已经完成了大部分工作。

各个系统之间，目标文件格式不尽相同。下面讨论的是 Unix 可执行和可链接目标文件格式（Executable and Linkable Format，ELF）。虽然我们的讨论集中在 ELF 上，但是不管是那种格式，基本概念是互通的。

链接器做了什么？

链接器主要是将有关的目标文件彼此相连接生成可加载、可执行的目标文件。链接器的核心工作是：

• 符号解析（symbol resolution）
• 重定位（relocation）

符号表

来看一下典型的 ELF 可重定位目标文件的格式。

节	内容
ELF header	描述生成该文件的系统的字的大小、字节顺序、目标文件类型、机器类型等，帮助链接器语法分析和解释目标文件的信息
.text	编译后的机器代码
.rodata	只读数据
.data	已初始化的全局变量
.bss	未初始化的全局变量，在目标文件不占实际空间，是“better save space”的缩写
symtab	符号表，存放在程序中定义和引用的函数与全局变量的信息
.rel.text	.text节的重定位信息，当链接时，指令的位置就被修改
.rel.data	.data节的重定位信息，当链接时，变量的位置就被修改
.debug	调试符号表
Section Header Table	节头部表，存放每个节的偏移和大小

每个可重定位目标模块 m ，都有一张符号表。符号表实际上是一个结构体数组，每一个元素包含名称、大小和符号的位置。符号表存放如下三种符号：

• 在 m 中定义，且能被其他模块引用全局符号，也就是不带 static 的全局变量。
• 在其他模块中定义，并被 m 引用的全局符号，是其他模块中的全局变量或者函数。这些符号叫做外部符号（external）
• 在 m 中定义的带 static 的全局变量，这些符号对 m 是随处可见的，但不能被其他模块所引用。

我们知道，局部变量会由栈来管理。局部静态变量，会存放到.bss或者.data节中，也不由符号表来管理。

符号解析

链接时，符号解析就是将对每个符号的引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义联系起来。

看下面两张图，可以理解符号表的作用，以及链接器对哪种类型的符号感兴趣：

符号解析的过程：对定义和引用在相同模块中的本地符号，符号解析相当简单。编译器只允许每个模块中每个本地符号只有一个定义。不过，对全局符号的引用解析就麻烦得多，当编译器遇到一个不是在本模块中定义的符号（变量名或函数名）时，它会假设这是在某个其他模块中定义的，并把后续工作交给链接器处理。如果链接器在所有的模块都找不到这个被引用的符号的定义，它就会输出报错信息并终止。一般来说，报错信息就是：undefined reference to something。

解析多重定义的符号

符号解析时，符号有强弱之分：

• 强符号：函数和初始化的全局变量。
• 弱符号：未初始化的全局变量。

根据下面的规则来处理多重定义的符号：

• 不允许有多个重名强符号。
• 如果有一个强符号和多个弱符号，选择强符号
• 多个弱符号，那么就从中任意选择一个。

在上图的main.c中，time是弱符号，其余的符号是强符号。

如果说在两个不同的文件中定义了同名的函数，由于函数都是强符号，链接时就会报错。

下面看一个特殊的例子：

//文件1
#include<stdio.h>
void f(void);

int x = 15213;
int y = 15212;

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

//文件2
double x;
void f()
{
    x = -0.0;
}

实验结果如下，可以看到，变量 y 的值也被改变了。

上述代码的问题在于，文件2中定义的变量 x 是弱定义，在调用 f 函数对 x 进行写入的时候，实际上操作的应该是文件1中定义的强符号。在文件2中，x 的类型是 double，占 8 个字节，赋值语句 x = -0.0 会导致文件1中定义的强符号 y 的数据也被覆盖。在 linux 下，编译会发出一条警告，提示我们，两个同名符号的大小不同。

由上面的例子可以知道，对链接知识的不了解，可能导致意想不到的错误，而且编译器不会报 error。因此，我们可以得到一些很重要的编程经验：

• 避免使用全局变量
• 如果一定要使用全局变量：
  • 加上 static，使其成为静态变量。
  • 定义全局变量时初始化，使其成为强符号。
  • 使用 extern 来标识是从其他模块引用的全局符号。

重定位

重定位就是当链接器完成了符号解析这一步之后，链接器就知道了输入模块的代码节和数据节的确切大小，可以开始重定位了。看下图：

重定位说白了就是把不同可重定位对象文件拼成可执行对象文件。在这个合并的步骤中，为每个符号分配运行时地址。

重定位分两步：

• 重定位节和符号定义（合并）。将所有相同的节合并为新的聚合节。然后，链接器确定运行时存储器地址赋给新的节，再根据偏移量赋给每个符号。此时，程序中的每个指令和全局变量都有唯一的运行时地址了。
• 重定位节中的符号引用。链接器修改代码节和数据节中对每个符号的引用，使其指向正确的运行时地址。

下面是一个实验，源文件relocation.c如下：

int sum(int *a, int n);
int array[2] = {1, 2};
int main()
{
    int val = sum(array, 2);
    return val;
}

源文件sum.c如下：

int sum(int *a, int n)
{
    int i, result = 0;
    for(i = 0;i < n; i++)
        result += a[i];
    return result;
}

使用指令：gcc -c relocation.c -o relocation.o，-c 选项的意思是只编译不链接，我们可以由此得到可重定位目标文件。

使用指令：objdump -r -d relocation.o反编译对应的可重定位对象文件，可以得到如下的汇编代码：

全局数组array需要重定位。call 指令调用函数 sum，这也是一个需要重定位的符号。我们将目光移到 call 指令这一行。e8是 call 的字节编码，可以看到，后面的操作数都是零，就是留出位置让链接器在链接的时候填上对应的实际内存地址。同理bf是mov的字节编码，array的首地址也是链接完成后才知道的，因此还没有确定地址。

call 指令的下一行，有一句13: R_X86_64_PC32 sum-0x4，这个东西叫做重定位条目（relocation entry），无论何时汇编器遇到了对最终位置未知的符号引用，就会生成一个重定位条目，也就是存放在.rel.text和.rel.data节中的数据。objdump为了方便，将汇编代码和重定位条目放到一起显示，虽然他们实际存储不在一起。

PC相对引用重定位

我们现在来看一下链接器如何确定 call 调用的实际位置。重定位条目13: R_X86_64_PC32 sum-0x4告诉链接器要修改位于目标文件偏移量 0x13 （数一下机器编码的字节数，可以发现 call 指令刚好是第 0x13 个字节）的 PC相对引用（PC是指程序计数器），使得它在运行时指向 sum 的偏移量 -0x4 位置。

使用指令

gcc -o relocation relocation.c sum.c
objdump -dx relocation

在可执行文件的反汇编代码中找到 main 这一节，main 的地址是0x4004d6，sum 的地址是0x4004f5。这也就是链接器为节选择了运行时地址。

ADDR(.text) = 0x4004d6
ADDR(sum) = 0x4004f5

//计算引用的运行时，程序计数器的地址
refaddr = ADDR(.text) + offset = 0x4004d6 + 0x13 = 0x4004e9

//因此 call 的目标地址是 （第二个refptr是 0 ，计算前 call 后的操作数）
*refptr = unsigned(ADDR(sum) - refaddr) -0x4
        = unsigned(0x4004f5 - 0x4004e9) -0x4
        = 0x8 

以上就是 PC 相对重定位的过程。链接器将结果填入可执行目标文件，call 指令有了如下的重定位形式：

4004e8:     e8 08 00 00 00          callq   4004f5 <sum>

绝对引用重定位

对于全局数组 array 的重定位条目：e：R_X86_64_32 array，重定位条目告诉链接器，这是一个绝对引用，将要修改位于目标文件偏移量 0xe 的绝对引用，使其指向符号 array。绝对引用就相对简单，只需要把链接器确定的数组开头的运行时地址，即&array[0]填入相应的地方即可。

共享库

我们目前为止做的工作都是链接器读取一组可重定位目标文件，并把它们链接起来。那在处理一大堆常用的标准函数，例如printf、scanf、malloc等，我们要怎么做呢？

• 思路1：让编译器辨认出对标准函数的调用，生成相应的代码
  • 缺点：对于有大量标准函数的编程语言，这种方法会显著增加编译器的复杂性。
• 思路2：将所有的标准函数放到一个单独的可重定位目标文件中，程序员将其与他们自己的目标文件链接生成可执行文件。
  • 缺点：这样做的话，对于每个可执行文件，都存在一份所有标准函数的集合，很浪费空间。
• 思路3：将每个标准函数创建一个独立的可重定位目标文件，然后链接的时候显示地链接标准函数
  • 缺点：耗时，容易出错。

共同的缺点：对于标准函数的任何改变，都需要修改新的编译器版本或要重新编译整个可重定位目标文件，这十分耗时。

解决的方法就是引入库（library）的概念。

静态库

比较老式的做法就是所谓的静态库（Static Libraries, .a 后缀表示 archive files，归档文件）。

静态库是一个外部函数与变量的集合体。静态库的文件内容，通常包含一堆程序员自定的变量与函数，在编译期间，静态库没有把全部内容链接，只是把需要的代码链接进去这个可执行文件与编译可执行文件的程序，都是一种程序的静态创建（static build）。

具体过程就是把不同文件的 .o 文件通过 Archiver 打包成为一个 .a 文件。Archiver 支持增量更新，如果有函数变动，只需要重新编译改动的部分。

在 C 语言中最常用的是 C 标准库与 C 数学库。C 标准库一般可以通过 libc.a 来进行引用，大小 4.6 MB，包含 1496 个对象文件，主要负责输入输出、内存分配、信号处理、字符串处理、操作数据、生成随机数及整型的数学运算。C 数学库可以通过 libm.a 来引用，大小 2 MB，包含 444 个对象文件，主要是提供浮点数运算的支持（比如三角函数、幂次等等）

下面看一个具体例子，各个文件代码如下：

使用如下指令：

只编译不链接，获得两个目标文件：
gcc -c addvec.c multvec.c

将两个目标文件打包成一个后缀为 .a 的静态库：
ar rcs libvector.a addvec.o multvec.o 

使用静态库链接
gcc -c main.c -o main.o
gcc -static -o p main.o ./libvector.a

-static 参数告诉编译器，链接器应当构建一个完全链接的可执行文件。

链接器会判断：addvec.o 中的符号 addvec 被 main.o 引用，因此拷贝这个模块到可执行文件。由于没有用到 multvec.o 中的符号，因此不会拷贝这个模块到可执行文件。此外，由于用到了函数 printf ，链接器还会拷贝 libc.a 中的 printf.o 模块，以及许多其他运行时需要用到的模块。下图很清晰的展现了静态库的好处：

动态链接共享库

静态库仍有缺点：需要定期维护和更新。如果程序员想要用一个库的最新版本，那么就必须先更新该库，然后再将更新的库与他们的程序重新链接。以及，几乎每个 C 程序都要用到标准 I/O 函数，例如 printf和scanf 之类。按照静态库的思路，这些代码会被拷贝到每个运行的进程的文本段中，在一个运行了几十个进程的系统上，会造成存储器资源的极大浪费。

共享库（shared library）就是致力解决静态库缺陷的现代创新产物。共享库是一个模块，可以在运行时加载到任何的存储器位置，并和一个存储器中的程序链接起来。这个过程就叫动态链接（dynamic linking），由动态链接器（dynamic linking）来完成。

共享库也叫共享目标（shared object），在 Unix 系统下常用后缀名 .so 来表示。在 Windows 中大量利用了动态链接库，就是 DLL（dynamic linking library）。

如果还是以上面的例子，但是以动态链接的方式，工作原理如下图：

创建一个共享的目标文件
gcc -shared -fPIC -o libvector.so addvec.c mutlvec.c

创建可执行目标文件 p2，这个文件的形式是可以在运行时与 libvector.so 动态链接
gcc -o p2 main.c ./libvector.so

-fPIC 指示编译器生成与位置无关的代码。目的就是允许多个正在运行的进程共享存储区中相同的库代码，节约了存储器空间。

基本的思路是：创建可执行文件时，静态地执行一部分链接，当程序被加载运行时，动态地完成剩余的链接过程。

可执行目标文件、加载运行

下图可以看到一个可执行目标文件的形式，它是由多个目标文件合并而来的。我们最开始的 C 源代码，是一个 ASCII 码文件，已经被转换成一个二进制文件，包含了加载程序且运行它所需的所有信息。

运行可执行目标文件，就是在外壳中输入它的名字，外壳会调用一个叫做加载器（loader）的操作系统代码来运行它。加载器将可执行目标文件的代码和数据从磁盘拷贝到存储器中，然后跳转到程序的入口点，运行该程序。

总结

链接是一种运行程序由多个目标文件构造得来的技术。链接可以发生在编译时（静态链接）、加载时、运行时（动态链接）。理解链接的相关知识点，我们从代码级进入到系统级，有益于我们了解操作系统是如何完成各种复杂工作的。

---

参考链接

• CMU 2017年春季学期 ICS课程网站
• wiki -静态库
• C编译器、链接器、加载器详解