链接（linking）是将各种代码块组合成一个可被载入内存并执行的文件的过程。链接过程可以在编译时（compile time）进行，此时源代码已经被翻译成了机器指令；也可以在载入时（load time）进行，此时程序已经被加载入了内存并且被加载器（loader）执行；也可以在运行时（run time）进行，此时链接过程是由应用程序进行的。在早期的操作系统中，链接过程需要手动完成，而在现在的系统中，链接过程是由称为链接器（linker）的程序完成的。

链接器在软件的发展中起到了很重要的作用，因为它允许独立编译（separate compilation）。现在我们可以将一个大程序分解为较小的且更便于管理的小模块。我们对这些模块进行单独的修改和编译，而不是将整个程序编写为一个大的源文件。当我们改变这些小模块后，只需要将改变的部分简单的进行重新编译链接，而不需要重新编译其他文件。

一、编译器驱动（compiler drivers）

考虑如图7.1所示的C程序：

可以看到这个C程序包含两个源文件，main.c和swap.c。main函数调用swap，而swap的作用是交换数组buf中两个元素的值。

大多数的编译系统都会提供一个编译器驱动，这个驱动会调用我们所用编程语言的预处理器、编译器和汇编器。例如，为了利用GNU编译系统来生成上面源程序的可执行文件，我们需要在shell中利用如下的语句调用GCC驱动：

unix> gcc -O2 -g -o p main.c swap.c

下图展示了驱动将示例的程序从ASCⅡ表示的形式（源程序的文本文件）翻译为一个可执行目标文件时执行的步骤（gcc编译时带有-v选项可以观察到这些步骤）：

整个过程如下：

驱动器首先运行C预处理器（cpp），这会将C语言源程序main.c翻译为一个ASCⅡ表示的中间文件main.i：

cpp [other arguments] main.c /tmp/main.i

接下来，驱动会运行C编译器（cc1），这时main.i会被编译成一个ASCⅡ表示的汇编语言文件main.s：

cc1 /tmp/main.i main.c -O2 [other arguments] -o /tmp/main.s

然后，驱动会运行汇编器（as），这时main.s会被转化为可重定位目标文件main.o：

as [other arguments] -o /tmp/main.o /tmp/main.s

驱动器会经历同样的步骤来生成swap.o。最终，它会运行链接器程序ld。链接器将main.o和swap.o以及一些必要的系统目标文件组合在一起，最终生成可执行目标文件p：

ld -o p [system object files and args] /tmp/main.o /tmp/swap.o

然后我们就可以执行我们生成的可执行文件：

unix> ./p

这时shell会调用操作系统中的loader函数，这个函数会将可执行文件p的代码和数据拷贝进入内存，然后将CPU控制权转交给程序。

二、静态链接

Unix中以ld程序为代表的静态链接器取一组可重定位目标文件及命令行参数作为输入，生成一个链接后的可执行文件。输入的可重定位目标文件包含各种不同的数据section和代码section。

为了生成可执行文件，静态链接器必须执行如下的动作：

• 符号解析（symbol resolution）：在目标文件中我们定义并引用了符号（symbol）。符号解析的目的是将每个符号引用和具体的符号定义结合在一起。
• 重定位（relocation）：编译器和汇编器会从地址0开始生成数据section和代码section。链接器通过将具体的内存地址和每个定义的符号结合在一起来重定位这些section。接下来链接器会修改所有指向这些符号的引用，使得这些引用指向分配的内存地址。

以下几点关于链接器的知识需要了解：

• 目标文件仅仅是字节块的集合，有一些块包含代码，一些块包含数据，而另一些可能包含了指导链接器和加载器工作的数据结构。
• 链接器将各个块连接在一起，决定这些块的运行时地址，并且在代码块和数据块中修改地址。
• 链接器对于最终代码运行的机器几乎不了解
• 生成目标文件的编译器和汇编器已经完成了大部分工作

三、目标文件

目标文件有以下三种形式：

• 可重定位目标文件（relocatable object file）：这是一种可在编译时和其他可重定位目标文件结合在一起的文件形式，其中包含二进制代码和数据
• 可执行目标文件（executable object file）：这种文件形式可以直接拷贝进入内存并执行，其中包含二进制代码和数据
• 共享目标文件（shared object file）：这是一种特殊的可重定位目标文件，这种目标文件可以在运行时或者加载时载入内存并自动进行链接过程

编译器和汇编器生成可重定位目标文件（包含共享目标文件）。链接器生成可执行目标文件。目标模块（object module）是字节码（byte）的序列，而目标文件（object file）是存储在硬盘上某处的目标模块，这两个术语是等价的。

目标文件的格式在不同的系统中有很大的区别。第一个Unix系统采用了a.out格式（直到今天，可执行文件依旧被称为a.out文件）。早期的V Unix系统采用了Common Object File格式（COFF）。Windows NT使用了一种COFF的变种，称为Portable Executable（PE）格式。现代的Unix系统（例如Linux）使用Unix Executable Linkable Format（ELF）。ELF是最常见的目标文件格式。

四、可重定位目标文件

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

这个ELF文件的首部（header）以一个长度为十六的字节序列作为开始。这个字节序列描述了字的大小以及系统是大端寻址还是小端寻址·。ELF文件首部的余下部分包含了允许链接器解析并解释目标文件的信息，这些信息包括ELF首部的大小，目标文件的类型（是可重定位文件、可执行文件或者共享文件）；机器类型（例如IA32）；节头表（section header table）的偏移地址以及节头表中的元素数量及元素大小。目标文件的节头表为每个section都保留了固定的大小，其中描述了每个section的地址以及大小。

夹在节头表和ELF首部之间的是各个section，一个典型的ELF可执行文件包含如下的section：

• .text：包含了编译后的机器码
• .rodata：包含了只读的数据（例如printf语句中的格式化字符串参数）和switch语句的跳跃表（jump table）
• .data：包含了已经初始化过的全局C变量。局部C变量栈上运行时进行维护，并不出现在.data或.bss段中
• .bss：包含了未初始化的全局C变量。这个段在实际目标文件中并不占用空间，仅是一个占位符。目标文件区分初始化和未初始化的变量的目的是节约空间，因为未初始化的变量无需占据任何的磁盘空间
• .symtab：存储着在程序中定义或引用的函数及全局变量信息的符号表（symbol table）。注意，并不是在编译时候带有-g选项时才能获取到符号表信息。实际上，每一个可重定位目标文件都在.symtab段内存有符号表。然而，和编译器内的符号表不同，.symtab符号表并不包含局部变量的信息。
• .rel.text：包含了当链接器将此目标文件与其他文件合并时，.text段中需要修改的位置信息。通常来讲，任何调用外部函数或引用全局变量的指令都需要修改，但是调用本地函数的指令不需要修改。注意，可执行目标文件中不需要重定位信息，除非用户明确指示链接器包含重定位信息，否则通常会忽略重定位信息。
• .rel.data ：包含了文件引用或定义的所有全局变量的重定位信息。一般来说，任何初始化完且初始值为全局变量地址或外部定义函数地址的全局变量都需要进行修改。
• .debug：包含了调试符号表，表中包含程序中定义的局部变量、typedefs、程序中定义和引用的全局变量以及原始C源文件。只有编译时指定-g选项时它才会出现。
• .line：C源代码中的行号与.text部分中的机器代码指令行号之间的映射。只有编译时指定-g选项时它才会出现。
• .strtab：A string table for the symbol tables in the .symtab and .debug sections, and for the section names in the section headers. A string table is a sequence of null-terminated character strings.

五、符号和符号表

每个可重定位目标文件m都有一个符号表，符号表内包含了在m中定义和引用的符号。对于链接器来说，存在着如下三种不同的符号：

• 在m内定义且可被其他可重定位目标文件引用的全局符号。这包括非静态的C函数和没有用static修饰的全局C属性（attribute）。
• 被m引用但并不是在m内定义的全局符号。 这些全局符号被称为外部符号（externals），指代在m外定义的C函数和变量。
• 在m内定义且仅能在m内使用的局部变量。这些局部变量中的一部分是被static修饰的C函数以及局部变量。 这些符号在m内的任何部分都是可见的，但是不能被其他文件引用。在目标文件中m的section以及源文件m的名字也会获得局部符号。

需要注意的是局部链接器符号（local linker symbols）和程序的局部变量完全不同。.symtab中的符号表中并不包含任何非静态局部程序变量的符号。这些非静态程序变量栈上运行时进行管理，链接器会无视这些变量。

注意，利用static关键字修饰的local procedure变量并不在栈上进行管理。编译器会在.data或.bss段中为这些变量创建空间，并且会在符号表中为它创建一个局部链接器符号。例如，在同一个文件中定义了如下两个函数，这两个函数都带有局部变量x：

int f(){
	static int x=0;
	return x;
}

int g(){
	static int x=1;
	return x;
}

在这种情况下，编译器会在.data段中为这两个整数分配空间，并且会为这两个整数生成不同的局部链接器符号。例如，编译器可能会使用x.1来定义f中的x，而使用x.2来定义g中的x。

符号表由汇编器利用编译器输出的汇编语言.s文件中的符号建立。ELF符号表被保存在.symtab段中，它包含了一个数组。 下图展示了数组中每个元素的格式：

其中：

• name是一个偏移量，这个偏移量指向字符串表中存储的这个符号的名字。
• value是这个符号的地址。对于可重定位目标文件来说，这个值是从符号所在的段的开始到这个符号被定义的位置偏移量。对于可执行文件来说，这个value是一个绝对运行时地址（absolute run-time address）。
• size指代这个对象的大小（以字节为单位）
• type通常有两种，或者是数据，或者是方程。符号表还可以存储individual section以及源文件路径名。所以type也可以有这些类型
• binding指明了这个符号是局部还是全局的
• section指明了每个符号相关联的section，它是节头表（section header table）中的索引。但是注意，有三个特殊的伪节在节头表中没有条目：ABS对应于不需要重定位的符号；UNDEF表示未定义的符号，即在该对象模块中引用但在其他地方定义的符号；COMMON表示尚未分配的未初始化数据对象。对于COMMON符号，值字段给出对齐要求，尺寸字段给出最小尺寸。

下面的例子给出了main.o文件中符号表的最后三个元素（利用GNU的READELF工具可以观察到这些信息）：

没有展示出的前八个元素是链接器内部使用的局部符号。

在这个例子中，可以看到第一个元素存储了全局符号buf，长度为8字节且在.data段中的偏移量为0。接下来的元素存储了全局符号main，这是一个十七字节长度的方程且在.text段中的偏移量为0。最后一个元素存储了外部符号swap的引用。READELF通过一个整数索引（integer index）来区分各个段。Ndx=1指代.text段，Ndx=3指代了.data段。

类似地，这是swap.o的符号表：

首先可以看到定义全局符号bufp0的表项，这是一个在.data段中、偏移量为0、四字节的初始化后的对象。下一个符号来自于外部符号buf的引用，这个符号在bufp0的初始化语句中出现。接下来跟着的是全局符号swap，这是一个39字节的函数，在.text段中偏移量为39的地方存储。最后一个表项来自于全局符号bufp1，这是一个四字节的未初始化数据对象，最终会被分配为一个.bss对象。

练习题 7.1

这个问题与图7.1(b)中的函数有关。对于在swap.o中定义的每个符号，指明它是否在.symtab段中存在一个符号表表项。如果存在表项，那么指明定义该变量的模块（swap.o或main.o）、符号类型（local、global或extern）及它在模块中所在的段（.text、.data或.bss）

答案：

六、符号解析

链接器通过将每个引用与可重定位目标文件的符号表中的一个符号定义相关联来解析符号引用。 同时编译器还确保获得局部链接器符号的静态局部变量有自己独特的名字。

解析全局变量的引用比较困难。当编译器遇到一个没有在当前模块定义的符号时（可以是变量或者方程名），它就假定这个符号是在其他模块被定义的。此时编译器会生成一个链接器符号表元素（linker symbol table entry），并把它留给链接器进行处理。如果链接器在任何输入的模块中都无法找到被引用符号的定义，那么它会输出错误信息并终止执行。

对于全局符号的解析是十分棘手的，因为同样的符号可能被多个目标文件定义。在这种情况下，链接器必须抛出错误或者采用其中的一个定义并弃用其他的定义。Unix系统采用的方法涉及到编译器、汇编程序和链接器之间的协作。

补充：C++和Java中的识别编码

C++和Java都允许重载方法（重载就是利用参数列表对同名函数进行区分），那么链接器是怎么区分重载方法的呢？C++和Java采用了同一种方法，编译器为每个不同的方法都定义了一个独一无二的名字。这个编码过程称为识别编码（mangling）。
C++和Java采用了兼容的识别编码方案。一个识别编码后的类名包含原类明以及一个整数。例如，Foo类会被编码成3Foo。函数会被编码成原函数名+__+识别编码后的类名+每个变量中的一个字母。例如，Foo::bar(int,long)会被编码成bar__3Fooil。识别编码全局变量和模板时也采用了类似的方案。

6.1 链接器如何解析多次定义的全局符号

编译期间编译器将每个全局符号作为强符号（strong）或弱符号（weak）导出到汇编器，汇编程序在可重定位目标文件的符号表中隐式地编码这些信息。函数和初始化过的全局变量是强符号。未初始化的全局变量是弱符号。对于图7.1中的示例程序，buf、bufp0、main和swap是强符号；bufp1是弱符号。

给定了强符号和弱符号的概念后，Unix链接器使用以下规则来处理多重定义的符号：

• 规则一：不允许定义多重强符号
• 规则二：给定了一个强符号以及多个弱符号，选择强符号
• 规则三：给定了多个弱符号，那么在弱符号中选择任意一个

例如，假设我们想要编译链接如下的两个C模块：

在这种情况下，链接器会生成一个错误信息，因为此时存在两个强符号main（违反了规则一）：

然而，如果x在一个模块中没有被初始化，那么链接器会默认选择在另一个模块中定义的强符号（规则二）：

输出结果如下：

上例中，在运行时函数f将x的值从15213修改成了15212，这对于对于main函数来说是一个意外的结果。注意在这种情况下，编译器不会给出关于多重定义的任何提示信息。

当两个定义均为弱符号时，结果是相同的，下例展示了规则三：

运行结果：

规则2和规则3的应用可能会产生一些难以发现的潜在运行时错误，特别是当重复的符号定义具有不同的类型时。考虑以下例子，其中x在一个模块中定义为int，在另一个模块中定义为double：

图 7.4

在一台IA32/Linux机器上，double类型占据8字节，而int类型占据4字节。因此，在bar5.c第六行的赋值语句x=-0.0将会覆盖x和y的内存地址（在foo5.c的第五行和第六行），此时x和y的值分别为双精度浮点数-0.0的高四位和低四位。

程序执行后，输出如下；

这是一个很难发现的bug，它通常在程序执行的很晚的时候表现出来，远离错误发生的地方。在一个有数百个模块的大型系统中，这类错误很难修复，特别是因为许多程序员不知道链接器是如何工作的。当我们有疑问时，可以使用诸如gcc-fno common标志之类的标志调用链接器，如果它遇到多个定义的全局符号，就会触发错误。

练习7.2

在这个问题中，让REF(x.i)–>DEF(x.k)表示链接器会将一个在模块i中引用的符号x指向模块k中的x的定义。对于下面的每个例子，都利用这样的表示方法来表示链接器如何在每个模块中解析多重定义的符号。如果存在违反规则一的错误，输出“ERROR”，如果链接器从弱引用中随机选择了一个（规则三），那么输出“UNKNOWN”：

(a) REF(main.1) --> DEF(___ .___ )
(b) REF(main.2) --> DEF( ___. ___)

(a) REF(main.1) --> DEF( . )
(b) REF(main.2) --> DEF( . )

(a) REF(x.1) --> DEF( ___ . ___ )
(b) REF(x.2) --> DEF( ___ . ___ )

答案：

main.1
main.2

ERROR，因为定义了两个强引用

x.2
x.2

6.2 链接器解析静态库

所有的编译系统还会提供一种将一组有关的目标文件打包成一个静态库的机制，这个静态库可以作为链接器的输入。当链接器生成可执行文件时，仅从静态库中复制那些应用程序引用过的目标模块。

在静态库中，相关的函数都被编译进入不同的目标模块并打包进入一个单独的静态库中。应用程序此时就可以通过在命令行指定文件名的方式来调用库中的任意一个函数。例如，一个使用标准C库和数学库的程序可以在命令行进行如下的调用：

unix> gcc main.c /usr/lib/libm.a /usr/lib/libc.a

在链接时，链接器仅仅会从目标模块中拷贝出程序引用的部分，这减小了可执行文件在硬盘和内存中的大小。另一方面，程序员只需要包括几个库的名字（C编译器默认对链接器引入libc.a）。

在Unix系统中，静态库都被以一种特殊的archive文件格式存储在磁盘中。一个archive是一组连接起来的可重定位目标文件且archive有一个首部（header），描述了每个成员对象的大小和位置。archive文件名以.a后缀作为标记。假设我们想要提供vector程序供调用，这个程序存储在libvector.a静态库中：

图 7.5

为了创建这个库，我们需要使用AR工具：

unix> gcc -c addvec.c multvec.c
unix> ar rcs libvector.a addvec.o multvec.o

需要使用这个库时，我们可以利用如下图所示的main2.c程序，这个程序调用了addvec程序（程序开头的#include "vector.h"定义了libvector.a中的函数原型）：

图 7.6

为了建立可执行文件，我们需要编译链接两个文件，main2.o和libvector.a：

unix> gcc -O2 -c main2.c
unix> gcc -static -o p2 main2.o ./libvector.a

下图展示了链接器的活动：

-static选项告知编译器驱动，链接器应该生成一个完全链接完毕的可执行文件，这个文件可以直接被载入内存运行，不需要任何的载入时链接。当链接器工作时，它发现了由addvec.o定义的addvec符号被main.o所引用，所以它将addvec.o拷贝进入可执行文件。因为程序没有引用任何multvec.o的内容，所以链接器不会拷贝这个模块进入可执行文件。链接器还将printf.o模块从libc.a拷贝进入模块中（其实还带有一些从C语言运行时系统拷贝进入的模块）。

6.3 链接器怎么使用静态链接库来解析符号

在符号解析阶段链接器会按照命令行每行命令从左到右的顺序扫描出现的可重定位目标文件和archive（驱动会自动将.c文件翻译为.o文件）。在此扫描期间，链接器会维护一个集合E，这个集合包含了将融合形成可执行文件的重定位文件。链接器还会维护一个未解析的符号集合U（已经被引用的符号，但是还没有被定义），一个在先前输入文件已经定义了的符号集合D。初始时这三个集合都为空。

• 对于命令行的每个输入文件f，链接器首先判断f是目标文件还是archive。如果f是目标文件，那么链接器将f添加到E，并用f中的符号定义和引用来更新U和D中的内容，接下来处理下一个文件。
• 如果f是archive，那么链接器会尝试利用archive中定义的符号来匹配U中未解析的符号。如果某个archive m定义了U中的某个符号引用，那么此时驱动会将m添加到E，然后链接器会更新U和D来对应此次m中的符号定义和引用。这个过程是在archive中各个目标文件中迭代进行的，直到到达U和D不再改变。此时任何没有在E内部的目标文件都会被放弃。链接器会接着处理下一个输入文件
• 如果在链接器扫描完输入文件后U还是非空的，那么链接器会打印错误信息并终止运行，否则，链接器会对E内的目标文件进行融合和重定位来建立最终的可重定位文件。

但是需要注意，这种算法会导致一些令人费解的链接时错误，因为命令行上的库和对象文件的顺序非常重要。如果定义符号的库出现在引用该符号的对象文件之前的命令行上，则引用将不会被解析，链接将失败。例如，考虑下面的例子：

unix> gcc -static ./libvector.a main2.c
/tmp/cc9XH6Rp.o: In function ‘main’:
/tmp/cc9XH6Rp.o(.text+0x18): undefined reference to ‘addvec’

上面报错的原因就是命令行上库和对象文件的顺序错误。当我们处理libvector.a时，U是空的，所以没有libvector.a中的目标模块会被添加到E中。因此，对addvec的引用不会被解析，链接器会抛出错误信息并中止程序的运行。

对于库文件来说一个准则就是将它们放在命令的最后。如果不同库的成员是互相独立的（这意味着不会有一个成员引用定义在另外一个成员中的符号），那么各个库可以以任意的顺序被放置在命令行末尾。

但如果各个库之间并不是独立的，那么它们间的顺序必须满足引用顺序。我们可以在命令行重复引用相同的库来满足它们间的引用顺序。