链接是将各种各样代码和数据部门收集起来并组合成为一个单一文件的过程，这个文件可被加载（或被拷贝）到存储器并执行。链接可以执行于编译时，也就是在源代码被翻译成机器代码时；也可执行于加载时，也就是在程序被加载器加载的存储器并执行时；甚至执行于运行时，由应用程序来执行。

1 编译器驱动程序

考虑如下的两个源文件：main.c和swap.c。

main.c

void swap();

int buf[2]={1,2};

int main()
{
    swap();
    return 0;
}

swap.c

extern int buf[];

int *bufp0=buf;
int *bufp1;

void swap()
{
    int temp;
    
    bufp1=&buf[1];
    temp=*bufp0;
    *bufp0=*bufp1;
    *bufp1=temp;
}

大多数编译系统提供编译驱动程序，它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。

例如：

gcc -02 -g --o p main.c swap.c

驱动程序首先调用C预处理器（cpp），它将C源程序main.c翻译成一个中间文件main.i：

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

接下来，驱动程序运行C编译器（cc1），它将main.i翻译成一个汇编语言文件main.s

cc1 /tmp/main.i main.c -02 [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

要运行可执行文件p，我们只需要输入 ./p

外壳调用操作系统中一个叫做加载器的函数，它拷贝可执行文件p中的代码和数据到存储器，然后将控制转移到这个程序的开头。

2 静态链接

 静态链接器将一组可重定位目标文件盒命令行参数作为输入，生成一个完全链接的可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的代码和数据节组成。指令在一个节中，初始化的全局变量在另一个节中，而未初始化的变量又在另一节中。

为了构造可执行文件，链接器必须完成两个主要任务：

• 符号解析。目标文件定义和引用符号。符号解析的目的是将每个符号引用刚好和一个符号定义联系起来。
• 重定位。编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个存储器联系起来，然后修改所有对这些符号的引用，使得它们指向这个存储器位置，从而重定位这些节。

3 目标文件

目标文件有三种形式：

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

编译器和汇编器生成可重定位目标文件。链接器生成可执行目标文件。从技术上来说，一个目标模板就是一个字节序列，而一个目标文件就是一个存放在磁盘文件在的目标模板。

4 可重定位目标文件

在Unix中可执行和可链接格式（ELF）。下图展示一个典型的ELF可重定位目标文件的格式。ELF投以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。

夹在ELF头和节点头部表之间的都是节。

.text:已编译程序的机器代码。

.rodata:只读数据。

.data:已初始化的全局C变量。

.bss:未初始化的全局C变量。

.symtab:一个符号表。和编译器中的符号表不同，.symtab符号表不包含局部变量的条目。

.rel.text:一个.text节中位置的列表，当链接器把这个目标文件和其他文件结合时，需要修改这些位置。

.rel.data:被模板引用或定义的任何全局变量的重定位信息。

.debug:一个调试符号表。

.line:原始C源程序中的行号和.text节中的机器指令之间的映射。

.strtab:一个字符串表，其内容包括.symtab和.debug节中的符号表。

5 符号和符号表

每个可重定位目标模块m都有一个符号表，它包含m所定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

• 由m定义并能被其他模块引用的全局符号。（不带static的全局变量）
• 由其他模块定义并被其他模块m引用的全局符号。（被extern修饰的全局变量）
• 只被模板m定义和引用的本地符号。（被static修饰的全局变量）

.symtab中的符号表不包含对应于本地非静态程序变量的任何符号。这些符号在运行时在栈中管理。

符号表是由汇编器构造的，使用编译器输出到汇编语言.s文件中的符号。

6 符号解析

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

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

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

在编译时，编译器向汇编器输出每个全局符号，或者是强或者是弱，而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局符号是弱符号。

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

规则1：不允许有多个强符号。

规则2：如果有一个强符号和多个弱符号，那么选择强符号

规则3：如果有多个弱符号，那么从这些若符号中任意选择一个。

6.2 与静态库链接

我们都是假设链接器读取一组可重定位目标文件，并把它们链接起来，成为一个输出的可执行文件。实际上，所有的编译系统都提供了一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库，它可以用作链接器的输入。当链接器构造一个输出的可执行文件时，它只拷贝静态库里被应用程序引用的目标模块。

例如：

addvec.c

void addvec(int *x,int *y,int  *z,int n)
{
    int i;
    for(i=0;i<n;++i)
        z[i]=z[i]+y[i];
}

mulvec.c

void multvec(int *x,int *y,int *x,int n)
{
    int i;
    for(i=0;i<n;++i)
        z[i]=x[i]+y[i];
}

为了创建该库，使用AR工具，

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

为了使用这个库，我们编写程序main.c,其中vector.h中包含了函数的原型：

#include<stdio.h>
#include"vector.h"

int x[2]={1,2};
int y[2]={3,4};
int z[2];

int main()
{
    addvec(x,y,z,2);
    printf("z=[%d %d]\n",z[0],z[1]);
    return 0;
}

为了创建可执行文件，执行：

gcc  -O2 -c main.c
gcc -static -o p2 main.o ./libvector.a

下图概括了链接的过程。-static参数告诉编译器驱动程序，链接器应该构建一个完全链接的可执行目标文件，它可以加载到存储器并运行，在加载时无需更进一步的链接。当链接时，它判定addvec.o定义的addvec符号是被main.o引用的，所以它只拷贝addvec.o到可执行文件。

6.3 链接器如何使用静态库来解析引用

在符号解析的阶段，链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件盒存档文件。在这次扫描中，链接器维持一个可重定位目标文件的集合E（这个集合在的文件可以被合并起来形成可执行文件），一个未解析的符号（即引用了但是尚未定义的符号）集合U，以及一个在前面输入文件中已定义的符号集合D。

通过在D中找出未解析集合U中的出现的符号，加入到E中。最后，如果U是非空的，那么链接器就会输出一个错误并终止。否则，它会合并和重定位E中的目标文件，从而构建输出可执行文件。

7 重定位

一旦链接器完成了符号解析这一步，它就把代码中的每个符号引用和确定的一个符号定义（即它的一个输入目标模块中的一个符号表条目）联系起来。在此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。现在就可以开始重定位了，在这个步骤中，将合并输入模块，并未每个符号分配运行时地址。重定位由两步组成：

• 重定位节和符号定义。在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。例如，来自输入模块的.data节被全部合并成一个节，这个节成为输出的可执行目标文件的.data节。然后，链接器将运行时存储器地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号。当这一步完成，程序中的每个指令和全局变量都有唯一的运行时存储器地址了。
• 重定位节中的符号引用。在一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。为了执行这一步，链接器依赖于称为重定位条目的可重定位目标模块中的数据结构。

8 可执行目标文件

我们已经看到链接器是如何将多个目标模块合并成一个可执行目标文件的。我们的C程序，开始是一个组ASCII文本文件，已经被转化为一个二进制文件，且这个二进制文件包含加载程序到存储器并运行它所需的所有信息。

可执行目标文件的格式类似于可重定位目标文件的格式。因为可执行文件是完全连接的（已被重定位了），所以它不再需要.rel节。

9 加载可执行目标文件

要运行可执行目标文件p，可以在Unix外壳的命令行中输入它的名字：

./p

因为p不是一个内置的外壳目命令，所以外壳会认为p是一个可执行目标文件，通过调用某个驻留在存储器称为加载器（loader）的操作系统代码来运行它。任何Unix程序都可以通过调用execve函数来调用加载器。加载器将可执行目标文件中的代码和数据从磁盘拷贝到存储器中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序拷贝到存储器并运行的过程叫做加载。

每个Unix程序都有一个运行时存储器映像，如图所示。

当加载器运行时，它创建上图的存储器映像。在可执行文件中段头部表的指导下，加载器将可执行文件的相关内容拷贝到代码和数据段。接下来，加载器跳转到程序的入口点，也就是符号_start的地址。在_start地址的启动代码时在目标文件ctrl.o中定义的，对所有的C程序都是一样的。

旁注：

加载器实际上是如何工作的呢？

Unix系统中的每个程序都运行在一个进程上下文中，有自己的虚拟地址空间。当外壳运行一个程序时，父外壳进程生成一个子进程，它是父进程的一个复制品。子进程通过execve系统调用启动加载器。加载器删除子进程现有的虚拟存储器段，并创建一组新的代码、数据、堆和栈段。新的栈和堆段被初始化为0.通过将虚拟地址空间中的页映射到可执行文件的页大小的片，新的代码和数据段被初始化为可执行文件的内容。最后，加载器跳转到_start地址，它最终会调用应用程序的main函数。除了一些头部信息，在加载过程中没有任何从磁盘到存储器的数据拷贝。直到CPU引用一个被映射的虚拟页才会进行拷贝，此时，操作系统利用它的页面调度机制自动将页面从磁盘传送到存储器。

10 动态链接共享库

静态库和所有的软件一样，需要定期维护和更新，而且静态库在内存中会有多份拷贝，浪费了系统资源。共享库是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块，在运行时，可以加载到任意的存储器地址，并和一个在存储器中的程序链接起来。这个过程称为动态链接，是由一个叫做动态链接器的程序来执行的。

共享库也称为共享目标，在Unix系统中通常用.so后缀来表示。

共享库是以两种不同的方式来实现“共享”的。首先，在任何给定的文件系统中，对于一个库只有一个.so文件。所以引用该库的可执行目标文件共享这个.so文件中的代码和数据，而不是像静态库那样被拷贝和嵌入到引用它们的可执行文件中。其次，在存储器中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享。

例如：

gcc -shared -fPIC -o libvector.so addvec.c multvec.c

一旦创建了这个库，我们就可以生成可执行目标文件p2:

gcc -o p2 main.c ./libvector.so

这样就创建了一个可执行目标文件p2，而此文件的形式使得它在运行时可以和libvector.so链接。基本的思路是当创建可执行文件时，静态执行一些链接，然后在程序加载时，动态完成链接过程。此时，没有任何libvector.so的代码和数据真正的被拷贝到可执行文件p2中。反之，链接器拷贝了一些重定位和符号表信息，它们在使得运行时可以解析对libvector.so中代码和数据的引用。

当加载器加载和运行可执行文件p2时，加载部分链接的可执行文件p2.接着，它注意到p2包含一个.interp节，这个节包含动态链接器的路径名，动态链接器本身就是一个共享目标。加载器不再像它通常那样将控制传递给应用，而是加载和运行这个动态链接器。

然后，动态链接器通过执行下面的重定位完成链接任务：

• 重定位libc.so的文本和数据到某个存储器段。
• 重定位libvector.so的文本和数据到某个存储器段。
• 重定位p2中所有对由libc.so和libvector.so定义的符号的引用。

最后，动态链接器将控制传递给应用程序。从这个时候开始，共享库的位置就固定了，并在在程序执行的过程中都不会改变了。