一、链接概述
链接通常是一个让人比较费解的过程，为什么汇编器不直接输出可执行文件而是输出一个目标文件呢？链接过程到底包含了什么内容？为什么要链接？
很久以前，人们编写程序时，将所有源代码都写在同一个文件中，发展到后来一个程序源代码的文件长达数百万行，以至于人们没有能力维护这个程序。
后来，出现了模块化。现代的大型软件往往拥有成千上万个模块，这些模块之间相互依赖又相对独立。这种按照层次化及模块化存储和组织源代码有很多好处，比如代码更容易阅读、理解、重用，每个模块可以单独开发、编译、测试，改变部分代码不需要编译整个程序等。
在一个程序被分割成多个模块以后，这些模块之间最后如何组合形成一个单一的程序是须解决的问题。模块之间如何组合的问题可以归结为模块之间如何通信的问题，最常见的属于静态语言的C/C++模块之间通信有两种方式，一种是模块间的函数调用，另外一种是模块间的变量访问。函数访问须知道目标函数的地址，变量访问也须知道目标变量的地址，所以这两种方式都可以归结为一种方式，那就是模块间符号的引用。模块间依靠符号来通信类似于拼图版，定义符号的模块多出一块区域，引用该符号的模块刚好少了那一块区域，两者一拼接刚好完美组合。这个模块的拼接过程就是：链接
综上所述，链接的主要内容就是把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确地衔接。现代的高级语言的诸多特性和功能，使得编译器、链接器更为复杂，功能更为强大，但从原理上来讲，链接器的工作无非就是把一些指令对其他符号地址的引用加以修正。链接过程主要包括了地址和空间分配（Address and StorageAllocation）、符号决议（Symbol Resolution）和重定位 （Relocation）等这些步骤。（符号可以理解为函数名和变量名）
链接分为静态链接、动态链接。本篇只讲静态链接及静态链接器。
- 静态链接是把目标文件（一个或多个）和需要的静态库链接成可执行文件。
- 动态链接是在可执行文件装载、运行时进行的文件的链接。
二、静态链接
2.1 链接器
lld链接器是LLVM的一个子项目，旨在为LLVM开发一个内置的，平台独立的链接器，去除对所有第三方链接器的依赖。在2017年5月，lld已经支持ELF、PE/COFF、和Mach-O。在lld支持不完全的情况下，用户可以使用其他项目，如 GNU ld 链接器。
lld支持链接时优化。当LLVM链接时优化被启用时，LLVM可以输出bitcode而不是本机代码，而本机代码生成由链接器优化处理。
2.2 静态链接过程
2.2.1 两步链接
我们知道，可执行文件中的代码段和数据段都是由输入的目标文件中合并而成的。那么链接过程就产生了第一个问题：对于多个输入目标文件，链接器如何将它们的各个段合并到输出文件？或者说，输出文件中的空间如何分配给输入文件？
按序叠加：一个最简单的方案就是将输入的目标文件按照次序叠加起来。（比如按照编译顺序，先编译的在前）。
缺点：在有很多输入文件的情况下，输出文件将会有很多零散的段。假如有数百个目标文件，且都分别有.text段、.data段、.bss段，那最后的输出文件将会有成百上千个零散的段。这种做法非常浪费空间，因为每个段都须要有一定的地址和空间对齐要求(x86中，段的装载地址和空间的对齐单位是页，也就是4096字节)。
相似段合并：将相同性质的段合并到一起。
现在的链接器空间分配的策略基本上都会使相似段(Section)合并，使用这种方法的链接器一般都采用一种叫两步链接（Two-pass Linking）的方法。也就是说整个链接过程分两步：
2.2.2 符号表与符号
以下示例来自iOS程序员的自我修养-MachO文件静态链接（三），过程很简单，就是对于目标文件、可执行文件的MachOView的分析，目标文件、可执行文件是链接过程的输入、输出，通过对两个文件中的符号表Symbols、代码段__TEXT.__text来看一下引用符号的空间与地址分配、地址绑定过程。关于目标文件、可执行文件的生成上一篇文章已经讲过，本篇文章就直接看分析结果。
1 | // a.c 文件 |
1 | # 生成a.o b.o |
请注意，生成的a.o和b.o目标文件，都是基于arm64。a.o和b.o目标文件通过静态链接后生成可执行文件ab。（由于基于arm64，其实链接过程，也有动态链接库libSystem.B.dylib(系统库)参与,但本文忽略动态链接的参与，只讨论静态链接）。
在可执行文件ab中，之所以__TEXT.text段的虚拟地址为0x100000000，而在文件中的位置(偏移)为0，是因为在链接生成可执行文件时，产生的一个特殊的段__PAGEZERO，这个段，在可执行文件中不占空间File Offest、File Size都为0，而在虚拟地址空间中，占用了很大的空间，VMSize为0x100000000(4G).
在进入重定位之前，这里还需要再介绍一下符号表相关的知识点：符号表的加载命令、符号表的结构。
1. 符号表的加载命令
1 | //定义在<mach-o/loader.h>中 |
2. 符号表
符号表也是一个数组，里面元素是结构体nlist_64。符号表示意图见下方。
1 | struct nlist_64 { |
左侧是a.o的符号表，右侧是可执行文件的(全局)符号表：
相比于a.o、b.o目标文件，此时，可执行文件ab中的全局符号表中，每个符号都有了对应的(虚拟空间)地址，这是重定位的前提。
3. 符号表中符号的几种类型
每个可重定位模块都有一个符号表，它包含了在本模块中定义和引用的符号，有三种链接器符号：
| 类型 | 特征 | 举例 |
|---|---|---|
| Global symbols（模块内部定义的全局符号） | 由本模块定义并能被其他模块引用的符号 | 例如，非static C函数和非 static的C全局变量（指不带static的全局变量） |
| External symbols（外部定义的全局符号） | 由其他模块定义并被本模块引用了的全局符号 | 例如，在本模块中extern声明的其它模块中定义的符号 |
| Local symbols（本模块的局部符号） | 仅由本模块内定义和引用的本地符号 | 例如，在本模块中定义的带static 的C函数和全局变量。 |
注意：链接器局部符号
- 不是指程序中的局部变量（分配在栈中的临时性变量），链接器是不关心这种局部变量的。
- 个人理解：局部符号在本模块内定义并引用，按照符号解析的功能来看，其是不参与符号解析的。这也是为什么多个目标文件中出现同名的局部符号，在链接时，却不会报符号重定义的原因。并且查看链接后的可执行文件，符号表中，是可以同时存在多个同名局部符号的。
2.2.3 第一步 空间与地址分配
“链接器为目标文件分配地址和空间”这句话中的“地址和空间”其实有两个含义：
- 第一个是在输出的可执行文件中的空间；
- 第二个是在装载后的虚拟地址中的虚拟地址空间。
对于有实际数据的段，比如“.text”和“.data”来说，它们在文件中和虚拟地址中都要分配空间，因为它们在这两者中都存在；而对于“.bss”这样的段来说，分配空间的意义只局限于虚拟地址空间，因为它在文件中并没有内容。
事实上，我们在这里谈到的空间分配只关注于虚拟地址空间的分配，因为这个关系到链接器后面的关于地址计算的步骤，而可执行文件本身的空间分配与链接过程关系并不是很大。
1. 相似段合并
扫描所有的输入目标文件，并且获得它们的各个段的长度、属性和位置，并且将输入目标文件中的符号表中所有的符号定义和符号引用收集起来，统一放到一个全局符号表。这一步中，链接器将能够获得所有输入目标文件的段长度，并且将它们合并，计算出输出文件中各个段合并后的长度与位置，并建立映射关系。
应该说地址与空间分配，地址：分配到哪；空间：分配多大。链接器的地址与空间分配，既是指在可执行文件中的分配，也指在虚拟地址空间中的分配。
- 可执行文件的地址空间与目标文件中一样，地址从0开始。
- 虚拟地址空间中的地址并非从0开始，比如Linux下，ELF可执行文件中的数据，在进程虚拟地址空间中，默认从0x08048000开始分配。
我们在这里谈到的空间分配只关注于虚拟地址空间的分配，因为这个关系到下一步重定位中，关于地址计算的步骤(重定位中，地址修正是修正为符号的虚拟地址空间中的地址)，而且可执行文件本身的空间分布、分配与链接过程关系并不是很大。
这一步过程：
- 会将多个输入模块(目标文件)的数据收集，相似段进行合并，见上图。
- 重新计算段在可执行文件中的偏移、大小。
- 重新计算段在虚拟地址空间中的偏移、大小。
这些信息在LC_SEGMENT_64中看到：
1 | struct segment_command_64 { /* for 64-bit architectures */ |
2. 符号地址的确定(rebase)
当前面一步完成之后，链接器开始计算各个符号的虚拟地址。(这一步修正地址的符号是本文件内定义的(数据、函数)符号，关于外部符号的引用重定位在第二步)
一个mach-o的二进制文件中，包含了text段和data段。我们知道在代码中，我们可以用指针来引用，那么在一个文件中怎么代表引用呢，那就是偏移(目标文件中符号表中的符号的地址，都是相对于text段起始的偏移)。
当目标文件、动态库文件等二进制文件加载到内存中的时候，起始地址就是申请的内存的起始地址（slide)，不会是0，那么如何再能够找到这些引用的正确内存位置呢？ 把偏移加上(slide)就好了。
2.2.4 第二步 符号解析与重定位
使用上面第一步中收集到的所有信息，读取输入文件中段的数据、重定位信息，并且进行符号解析与重定位、调整代码中的地址等。事实上第二步是链接过程的核心，特别是重定位过程。
1. 符号解析
符号解析：解析每个模块中引用的符号，将其与某个目标模块中的符号定义建立关联。
- 每个定义的符号在代码段或数据段中都被分配了存储空间，将符号引用与符号定义建立关联后，就可在重定位时将引用的符号的地址重定位为相关联的定义的符号的地址。
- 如果没找到定义，会给出一个类似
“undefined reference to 'xxx'”、“Undefined symbols”类似的链接错误。导致这个问题的原因很多，最常见的一般都是链接时缺少了某个库、输入目标文件路径不正确、符号的声明与定义不一样等。 - 如果找到了，进行符号决议(绑定)：
- 如果找到了一个，直接绑定；
- 如果链接器在输入模块中找到了一个以上的外部符号定义，会按照它的规则选择其中一个符号定义或者报错。强弱符号规则：
- 对于C/C++语言来说，编译器默认函数和已初始化的全局变量为强符号，未初始化的全局变量为弱符号。
- 强符号只能被定义一次，否则报符号重复定义错误。符号的重复定义错误与类型无关，只要经过符号修饰机制后产生的符号相同，就报符号重复
“ld: dumplicate symbols” - 如果一个符号在某个目标文件中是强符号，在其他文件中都是弱符号，那么选强符号。(Xcode中默认设置了clang编译参数，遇到强弱符号会报重复定义错误)
- 如果一个符号在所有目标文件中都是弱符号，会选择占用空间最大的一个（《程序员的自我修养》）
- 动态库链接中还有全局符号介入规则(如果相同符号名的符号已存在，则后加入的符号被忽略))。
符号决议有时候也被叫做符号绑定（Symbol Binding）、名称绑定 （Name Binding）、名称决议（Name Resolution），甚至还有叫做地址绑定（Address Binding）、指令绑定（Instruction Binding）的。
大体上它们的意思都一样，但从细节角度来区分，它们之间还是存在一定区别的，比如“决议”更倾向于静态链接，而“绑定”更倾向于动态链接，即它们所使用的范围不一样。在静态链接，我们将统一称为符号决议。
符号解析时会选择一个确切的定义，即每个全局符号仅占一处存储空间。
编码建议：
- 尽量避免使用全局变量
- 一定要用时：
- 尽量使用内部链接定义，如用static修饰
- 全局变量要赋初值，避免潜在的强弱符号造成的不可知错误，赋初值后，编译器检测到重复定义会报错，提醒开发者修正。
- 头文件中，不能写
Global symbols的定义(否则若头文件若被多处#include，预处理后展开，文件内容替换该行，就相当于直接在多个源文件中出现全局符号定义，会报错)。如果要定义全局变量，一定要用static修饰，设置为Local symbols。
符号解析完成，全局符号表中符号都有对应的定义处的地址。接下来就是重定位工作：根据重定位表Relocations中符号信息，在全局符号表Symbols中找到符号的定义地址，然后找到符号在代码段__TEXT.text中的使用地址，进行指令的地址修正。
2. 重定位
重定位就是指针修正的过程。
假设有A、B两个目标文件，B中引用了A中的一个变量并对其进行赋值，对应AT&T汇编为movl $0x2a, var。
由于在编译目标文件B的时候，编译器并不知道变量var的目标地址，所以编译器在没法确定地址的情况下，将这条mov指令的目标地址置为 0，等待链接器在将目标文件A和B链接起来的时候再将其修正。我们假设A和B链接后，变量var的地址确定下来为0x1000，那么链接器将会把这个指令的目标地址部分修改成0x10000。这个地址修正的过程也被叫做重定位（Relocation），每个要被修正的地方叫一个重定位入口（Relocation Entry）。重定位所做的就是给程序中每个这样的绝对地址引用的位置“打补丁”，使它们指向正确的地址。
从上面的示例中，可以看到：a文件使用了B文件中的global_var和func两个符号，那是怎么知道这两个符号的地址呢？
在a.o目标文件中：
- global_var（地址0）和func（地址0x2c，这条指令本身地址）都是假地址。编译器暂时用0x0和0x2c替代着，把真正地址计算工作留给链接器。
- 通过前面的空间与地址分配可以得知，链接器在完成地址与空间分配后，就可以确定所有符号的虚拟地址了。
- 此时，链接器根据符号的地址对每个需要重定位的指令进行地址修正。
在链接后的ab可执行文件中：
可以看到global_var（地址0x100008000，指向data段，值为1）和func（地址0x100007f90，指向func函数地址）都是真正的地址。
链接器是怎么知道a模块里哪些指令要被调整，这些指令如何调整。事实上a.o里，有一个重定位表，专门保存这些与重定位相关的信息。而且每个section的section_64的header的reloff（重定位入口的文件偏移，即在重定位表里的偏移）和nreloc（几个需要重定位的符号），让链接器知道a模块的哪个section里的指令需要调整。
1 | struct section_64 { |
3. 重定位表
重定位表可以认为是一个数组，数组里的元素为结构体relocation_info。
1 | //定义在<mach-o/reloc.h>里 |
可以看出：
- a.o文件的重定位表中记录符号了_func和_global_var两个需要重定位的符号，并且
r_address给出了两个符号在代码段section的位置，r_symbolnum指向了符号在符号表的index。 - 链接时候，a.o里面有这两符号的引用，然后b.o里面有这两符号的定义，一起合并到全局符号表里（见上方符号表部分中的示意图）。
- 在全局符号表里，可以找到这两个符号的虚拟内存位置和其它信息，就可以完成重定位工作(对指令进行地址修正)了。
2.3 静态库链接
一个静态库可以简单看成一组目标文件的集合，即多个目标文件经过压缩打包后形成的一个文件。
静态库链接：是指自己的模块与静态库里的某个模块（用到的某个目标文件，或多个目标文件）链接成可执行文件。其实和静态链接概念一样，只是这里，我们这里取了静态库里的某个/多个目标文件与我们自己的目标文件一起作为输入。
Q：为什么静态运行库里面一个目标文件只包含一个函数？比如libc.a静态库里面printf.o只有printf()函数、strlen.o只有strlen()函数，为什么要这样组织？
A：我们知道，链接器在链接静态库的时候是以目标文件为单位的。比如我们引用了静态库中的printf()函数，那么链接器就会把库中包含printf()函数的那个目标文件链接进来，如果很多函数都放在一个目标文件中，很可能很多没用的函数都被一起链接进了输出结果中。由于运行库有成百上千个函数，数量非常庞大，每个函数独立地放在一个目标文件中可以尽量减少空间的浪费，那些没有被用到的目标文件（函数）就不要链接到最终的输出文件中。