链接(linking)是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可以被加载（复制）到内存并执行。链接可以执行于*编译时(compile time)，也就是在源文件被翻译成机器代码的时候；也可以执行于加载时(load time)，也就是程序被加载器(loader)加载到内存并执行时；甚至执行于运行时(run time)，也就是由应用程序来执行。在早期的计算机系统中，链接是手动完成的。在现代操作系统中链接是由链接器(linker)*的程序自动执行的。
链接使得软件中的分离编译成为了可能。我们不用将一个大型的应用程序组织成一个巨大的源文件，而是可以将它拆分成为更小的，更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的一个的时候，只需要重新编译修改的部分，并重新链接应用，而不必要重新编译整个应用。
- 理解链接器可以帮助构建大型程序。在构建大型程序的时候经常会遇到缺少模块，缺少库或者不兼容的库版本引起的链接错误。理解链接器是如何解析引用的，什么是库以及链接器是如何解析和引用库的可以帮助你排查这类错误。
- 理解链接器将帮助你避免一些危险的编程错误。这里将展示错误的全局变量的定义如何影响整个程序，并且应该如何避免它。
- 理解链接将帮助你理解语言的作用域规则是如何实现的。
- 理解链接将帮助你理解其他重要的系统概念。如加载和运行程序、虚拟内存、分页、内存映射等等。
- 理解链接将使将使你能够使用共享库。
1. 编译器驱动程序
大多数编译系统提供*编译器驱动程序(compiler driver)*，它代表用户需要调用语言预处理、编译器、汇编器和链接器。大致编译过程如下：
1 | main.c sum.c (源文件) |
最后在shell中执行prog的时候，shell调用操作系统中的一个叫做*加载器(loader)*的函数，它将可执行文件prog中的代码和数据复制到内存，然后控制转移到这个函数的开头。
2. 静态链接
像Linux LD程序这样的*静态链接器(static linker)*以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以被加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的代码和数据节(section)组成，每一节都是一个连续的字节序列。指令在一节，初始化了的全局变量在另一节，而未初始化的变量又在另外一节。
链接器主要有下面两个主要任务：
- 符号解析(symbol resolution).目标文件定义和引用符号，每个符号对应于一个函数/全局变量/静态变量。符号解析的目的是将每个符号引用正好和一个符号定义关联起来。
- 重定位(relocation). 编译器和汇编器生成的从地址0开始的代码和数据节。链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使得它们指向这个内存位置。
目标文件纯粹是字节块的集合。这些块中，有些包含程序代码，有些包含程序数据，而其他的则包含引导链接器和加载器的数据结构。链接器将这些块连接起来，确定被连接的块运行的位置，并且修改代码和数据块中的各种位置。链接器对目标机器了解非常少，产生目标文件的编译器和汇编器已经完成了大部分的工作。
3. 目标文件
目标文件有三种形式：
- 可重定位目标文件。(eg. .o文件)
- 可执行目标文件。(eg. .elf文件)
- 共享目标文件。(eg. .so文件)
目标文件是按照特定的目标文件格式来组织的，各个系统目标文件格式都不相同，如Windows使用的是PE格式，MacOS-X使用的是Mach-O格式。现代x86-64 Linux和Unix系统使用可执行可链接格式 ELF。
4. 可重定位目标文件
一个典型的ELF可重定位目标文件包含下面几节：
- .text : 已编译程序的机器代码。
- .rodata : 只读数据，如printf语句中格式串和开关语句的跳转表。
- .data : 已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中，即不出现在.data 节中，也不出现在.bss节中
- .bss : 未初始化的全局和静态C变量，以及所有被初始化为0的全局变量或者静态变量。在目标文件中这个节不占据实际的空间，仅仅作为一个占位符。
- .symtab : 一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
- .rel.text : 一个.text节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非用户显式地指示链接器包含这些信息。
- .rel.data : 被模块引用或定义的所有全局变量的重定位信息。一般而言，任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
- .debug : 一个调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C源文件。需要编译选项中加上-g
- .line : 原始C源程序中的行号和.text节中机器指令之间的映射。需要编译选项中加上-g
- .strtab : 一个字符串表，其内容包括.symtab 和.debug节中的符号表，以及节头部中的节名字。字符串表就是以null结尾的字符串的序列。
5. 符号和符号表
每个可重定位目标模块m都有一个符号表，它包含了m定义和引用的符号的信息。对于链接器的上下文中，有三种不同的符号：
- 由模块m定义并且能够被其他模块引用的全局符号。全局链接器符号对应非静态的C函数和全局变量。
- 由其他模块定义并被模块m引用的全局符号。这些符号被称为外部符号，对应于其在其他函数模块中定义的非静态C函数和全局变量。
- 只被模块m定义和引用的局部符号。它们对于带static属性的C函数和全局变量。这些符号在模块m中任何位置都可见，但是不被其他模块引用。
在C中，源文件扮演模块的角色。任何带有static属性声明的全局变量或者函数模块都是私有的。类似的，任何不带有static属性声明的全局变量和函数都是公开的，可以被其他模块访问。
6. 符号解析
链接器解析符号引用的方法是将每个引用与它输入的可重定位的目标文件的符号表中的一个确定的符号定义关联起来。
对于全局变量来说，当编译器遇到一个不是在当前模块中定义的符号(变量或者函数名)时，会假设该符号时在其他模块中定义的，生成一个链接器符号条目，并把它交给链接器处理。如果链接器在它的任何输入模块中都找不到这个被引用的符号定义，就会输出一条错误信息并终止。
对于C++和Java都允许重栽方法，这些方法在源代码中有相同的名字，却可以有不同的参数列表。因为编译器将每个唯一的方法和参数列表组合成一个对编译器来说唯一的名字。这种编码过程叫做重整(mangling)，而相反的过程叫做恢复(demangling)。
6.1 链接器如何解析多重定义的全局符号
链接器的输入是一组可重定位的目标模块。每个模块定义一组符号，有些是局部的（只对定义该符号的模块可见），有些是全局的（对其他模块也可见）。对于Linux编译系统：
在编译变得时候，编译器会向汇编器输出每个全局符号，或者是强(strong)或者是弱(weak)，汇编器将这个信息隐含的编码在可重定位的目标文件符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。根据强弱符号的定义，linux链接器使用下面规则来处理多重定义的符号名。
- 不允许有多个同名的强符号。
- 如果有一个强符号和多个弱符号同名，那么选择强符号。
- 如果有多个弱符号同名，那么从这些弱符号中任意选择一个。
6.2 与静态库链接
编译器提供了一种机制，将所有相关的目标模块打包称为一个单独的文件，称为*静态库(static library)*，它可以作为链接器的输入。当链接器构建一个输出可执行文件的时候，它只是复制静态库里被应用程序引用的目标模块。
在Linux系统中，静态库以一种称为*存档(archive)*的特殊文件格式存放在磁盘中。存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置。存档文件由后缀名.a标识。
对于链接静态库，链接器只复制.a 文件中需要的.o 文件到最终执行文件中。
6.3 链接器如何使用静态库来解析引用
对于Linux的链接器来说，链接器从左到右按照它们在编译器驱动的命令行上出现的顺序来扫描可重定位目标文件和存档文件。在这个扫描的过程中，链接器维护一个可以重定位目标文件的集合E，一个未解析的符号集合U，以及一个在前面输入文件中已经定义的符号集合D。
因为链接器是顺序扫描的，所以命令行上面库目标文件的顺序十分重要。在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不能被解析，链接就会失败。
7. 重定位
一旦链接器完成了符号解析这一步，就把代码中的每个符号引用和正好一个符号定义关联起来。此时，链接器就知道它的输入目标模块中的代码和数据节的确切大小。现在就可以开始重定位的步骤，在这个步骤中，将合并输入模块，并为每个符号分配运行时的地址。重定位由两步组成：
- 重定位节和符号定义。这里，链接器将所有相同类型的节合并成为同一类型的新的聚合节。
- 重定位节中的符号引用。这里，链接器修改代码和数据节中对每个符号的引用，使得它们指向正确的运行时的地址。这里链接器会依赖重定位的数据结构。
7.1 重定位条目
当汇编器生成一个目标模块的时候，它并不知道数据和代码最终将存放在内存中的什么位置。它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成为可执行文件的时候修改这个引用。代码的重定位条目放在.rel.text中。已初始化数据的重定位条目放在.rel.data中。
主要关心的两种重定位类型：
- R_X86_64_PC32 : 重定位一个使用32位PC相对地址的引用。当CPU执行一条使用PC相对寻址的指令的时候，他就将在指令编码中的32位值加上PC当前运行时的值，得到有效地址,PC值通常是下一条指令在内存中的地址。
- R_X86_64_32 : 重定位一个使用32位绝对地址的引用。通过绝对寻址，CPU直接使用在指令编码中的32位值作为有效地址，不需要进一步修改。
7.2 重定位符号引用
重定位算法的伪代码如下：
1 | foreach section s { |
8. 可执行目标文件
这里已经看到了链接器是如何将多个目标文件合并成为一个可执行目标文件的。对于可执行的目标二进制文件来说文件中包含了加载程序到内存并运行它所需要的所有信息。典型的ELF可执行目标文件格式如下：
1 | 0 ----> +-----------------+ ======= |
可执行目标文件的格式类似于可重定位目标文件的格式。ELF头描述文件的总体格式。它还包括程序的入口点(entry point)，也就是当程序运行时要执行的第一条指令的地址。.text .rodata .data 节与可重定位文件中的节十分相似，.init节定义了一个小函数，叫做_init，程序的初始化代码会调用它。因为可执行文件时完全链接的所以没有.rel节。
可执行文件的程序头部表: off: 目标文件中的偏移； vaddr/paddr: 内存地址；align：对齐要求；filesz：目标文件中的段大小；memsz；内存中的段大小；flags：运行时访问权限。
9. 加载可执行目标文件
要运行可执行文件prog，可以在linux shell中输入它的名字：
1 | linux > ./prog |
在这里因为prog不是一个内置的shell命令，所以shell会认为prog是一个可执行目标文件，通过调用某个驻留在存储器中称为加载器（loader）的操作系统代码来运行它。加载器将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或者入口点来运行该程序。这个将程序复制到内存中并运行的过程称之为加载。
每一个linux程序都有一个运行时的内存映像。在linux x86-64 系统中，代码段总是从地址 0x400000 处开始的，后面是数据段。linux x86-64运行时的内存映像如下：
1 | +-----------------+ ======= |
上面的图只是作为示意，并没有展示出由于段对齐要求和地址空间布局随机化(ASLR)造成的空隙，区域大小不成比例。
linux系统中每个程序都运行在一个进程上下文中，有自己的虚拟地址空间。当shell运行一个程序时，父shell进程生成一个子进程，它是父进程的一个复制。子进程通过execve系统调用启动加载器。加载器删除子进程现有的虚拟内存段，并创建一组新的代码，数据，堆和栈段。新的栈和堆段被初始化为零。通过将虚拟地址空间中的页映射到可执行文件的页大小片(chunk)，新的代码和数据段被初始化为可执行文件的内容。最后，加载器跳转到_start地址，它最终会调用应用程序的main函数。除了一些头部信息，在加载过程中没有任何从磁盘到内存的数据复制。直到CPU引用一个被映射的虚拟页时才会进行复制，此时，操作系统利用它的页面调度机制自动将页面从磁盘传送到内存。
10. 动态链接共享库
静态库和其他软件一样，需要定期维护和更新。如果应用程序员想要使用一个库的最新版本，他们必须以某种方式了解到该库的更新情况，然后显示的将它们的程序与更新的库重新链接。
*共享库(shared library)是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块，在运行或加载的时候，可以加载到任意的内存位置，并和一个在内存中的程序链接起来。这个过程被称为动态链接(dynamic linking)，是由一个叫做动态链接器(dynamic linker)*的程序来执行的。共享库也称为共享目标(shared object)，在Linux系统中通常用.so后缀来标识。
共享库是以两种不同的方式来”共享”的。首先，在任何给定的文件系统中，对于一个库只有一个.so文件。所有引用该库的可执行目标文件共享这个.so文件中的代码和数据，而不是像静态库的内容那样被复制和嵌入到引用它们的可执行文件中。其次，在内存中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享。
编译共享库链接的程序如下: gcc -shared -fpic -o libvector.so addvec multvec.c 这里-fpic是指示编译器生成与位置无关的代码。一旦创建了这个库链接到可执行程序的编译指令如下: gcc -o prog21 main2.c ./libvector.so
动态链接器通过执行下面的重定位完成链接任务：
- 重定位 libc.so的文件和数据到某个内存段
- 重定位 libvector.so 的文本和数据到另一个内存段。
- 重定位 prog21 中所有对由 libc.so 和libvector.so定义的符号引用。
11. 从应用程序中加载和链接共享库
linux为动态链接器提供了一些简单的接口: dlopen dlsym dlclose dlerror
12. 位置无关代码
共享库的一个主要目的就是允许多个正在运行的进程共享内存中相同的库代码，因而节省宝贵的内存资源。这里一种方法就是给每个共享库分配一个事先预备的专用的地址空间片，然后要求加载器总是在这个地址加载共享库。这种方式虽然简单，但是也带来了一些严重的问题。它对地址空间的使用效率不高，因为即使一个进程不使用这个库，那部分空间还是会被分配出来。这种方法也十分难以管理。我们必须保证没有片会重叠。每次当一个库修改之后，我们必须确认已分配给它的片还适合它的大小。如果不适合，则必须寻找一个新的片。
现代操作系统，编译共享模块代码段，使得可以把它们加载到内存的任何位置而无需链接器修改。使用这种方法，无限多个进程可以共享一个共享模块的代码段的单一副本。（当然不，每个进程会有它自己的读/写数据块）
这里可以加载而无需重定位的代码称为*位置无关代码(Position_Independent Code)*。对于GCC来说使用-fpic选项指示GNU编译系统生成PIC代码。
12.1 PIC数据引用
编译器通过下面的事实来生成对全局变量PIC的引用：无论我们在内存中何处加载一个目标模块(包括共享目标模块)，数据段和代码段的距离总是保持不变的。因此，代码段中任何指令和数据段中的任何变量之间的距离都是一个运行时的常量，与代码和数据段的绝对内存位置是无关的。
12.2 PIC函数调用
对于PIC函数的调用，GNU编译系统使用延迟绑定的方法，将过程地址的绑定推迟到第一次调用该过程。
13. 库打桩机制
Linux链接器有一个很强大的技术，称为库打桩(library interpositioning)，它允许你截获共享库函数的调用，取而代之执行自己的代码。库打桩的形式有：
- 编译时打桩
- 链接时打桩
- 运行时打桩
14. 处理目标文件的工具
在Linux系统中有大量的可用工具可以帮助理解和处理目标文件。
- AR : 创建静态库，插入、删除、列出和提取成员。
- STRINGS: 列出一个目标文件所有可打印的字符串。
- STRIP : 从目标文件中删除符号表的信息。
- NM : 列出一个目标文件的符号表中定义的符号。
- SIZE : 列出目标文件中节的名字和大小。
- READELF : 显示一个目标文件的完整结构，包括ELF头中编码的所有信息。包含SIZE和NM的功能。
- OBJDUMP : 能够显示一个目标文件中的所有信息
- LDD : 列出一个可执行文件在运行时所需要的共享库。