引言
链接与装载是一个比较晦涩的话题，大家往往容易陷入复杂的细节中而难以看清问题的本来面目。从本质上讲各个系统的编译、链接、装载过程都是大同小异的，或许可以用一种更抽象的形式来理解这些过程，梳理清楚宏观的来龙去脉有利于对特定系统进行深入学习。
本文主要根据《程序员的自我修养 —— 链接、装载与库》和自己的理解总结而来，书的内容是基于 GCC 的，不过笔者尽量以更抽象、更简洁的方式把问题讲清楚，避开那些恼人的细节。
一、源代码是如何运行起来的
不直接使用机器语言进行应用程序开发是为了提高开发效率，但程序终究是机器运行的，所以才有了复杂的编译链接过程，将源代码转换为机器指令。
程序员一般使用 IDE 进行应用程序开发，对于需要先编译成机器语言再运行的程序，在执行运行指令后时常会陷入漫长的等待才能运行起来，这期间计算机做了大量工作：
- 预编译：主要处理以“#”开始的预编译指令。
- 编译：
- 词法分析：将字符序列分割成一系列的记号。
- 语法分析：根据产生的记号进行语法分析生成语法树。
- 语义分析：分析语法树的语义，进行类型的匹配、转换、标识等。
- 中间代码生成：源码级优化器将语法树转换成中间代码，然后进行源码级优化，比如把 1+2 优化为 3。中间代码使得编译器被分为前端和后端，不同的平台可以利用不同的编译器后端将中间代码转换为机器代码，实现跨平台。
- 目标代码生成：此后的过程属于编译器后端，代码生成器将中间代码转换成目标代码（汇编代码），其后目标代码优化器对目标代码进行优化，比如调整寻址方式、使用位移代替乘法、删除多余指令、调整指令顺序等。
- 汇编：汇编器将汇编代码转变成机器指令。
- 静态链接：链接器将各个已经编译成机器指令的目标文件链接起来，经过重定位过后输出一个可执行文件。
- 装载：装载可执行文件、装载其依赖的共享对象。
- 动态链接：动态链接器将可执行文件和共享对象中需要重定位的位置进行修正。
- 最后，进程的控制权转交给程序入口，程序终于运行起来了。
大致流程就是如此，不同平台在细节处理上会有所不同，下面分析具体过程。
二、目标文件的结构
在静态链接之前，可以简单理解为程序员在 IDE 中写的参与运行的代码文件会转换为对应的目标文件，了解目标文件的构成是理解链接装载的前提。
目标文件中包含了编译后的机器指令、数据，还包含了用于链接的信息、调试信息等，这些内容按照属性不同以段 (Section) 的形式分开存储。
该图只是个大致结构，还有很多段没有例举出来。比如还有 Readonly Data 段存储只读数据（const 修饰变量和字符串常量），Debug 存储调试信息，以及动态链接相关的 Dynamic 段等。这些繁杂的 Section 这里不直接展开，而是优先关注图中这些具有代表性的结构。
为什么要把程序指令和程序数据分离？
- 很容易想到的理由是，这么做过后提高了查询特定数据的效率，根据待查询数据的类型直接定位到归属段，而不用每次都遍历整个目标文件。
- 对于一个进程来说，代码段是只读的，数据段是可读写的，这样可以便于操作系统对虚拟内存区域划分访问权限。
- CPU 一般设计成数据缓存和指令缓存分离，分离有利于 CPU 缓存命中。
- 多个进程可以共享内存中的只读数据，比如代码段和图片资源等（参考共享库原理），节约内存占用。
文件头
文件头是访问目标文件的入口，是一个结构体，它包含了文件类型（并不是用拓展名判断类型的）、字节序、入口地址等基本信息，这里最需要关注的是它提供了段表在目标文件中的偏移。
段表
Section Table 是一个非常重要的段，它是一个结构体数组，每一个元素包含了某个段的段名（实际上是在字符串表中的偏移）、段在目标文件的偏移、段的长度、段访问权限、段类型（并不是用段名判断类型的）、段虚拟地址等。
字符串表
目标文件中用到了段名、符号名等字符串，字符串的长度不定，无法用固定的格式表示，所以将这些字符串集中起来依次放入一个表，字符串之间用\0分割。如此，目标文件中访问字符串只需要提供一个偏移。
函数、变量等字符串往往主要是指令来访问，段表名字符串主要是链接器来访问，为了分离职责，使用 字符串表 来存储普通字符串，使用 段表字符串表 来存储段表中用到的字符串。
文件头中除了包含段表的偏移，还包含了段表字符串表在段表中的下标，由此可见，通过访问文件头就能访问到所有的段。
符号表
函数和变量统称为 符号 ，符号表记录了目标文件中用到的所有符号，值得注意的是还会包含段名，段名是编译器生成的而不是源代码中的。
符号表是一个结构体数组，每一个元素记录了某个符号的符号名（在字符串表中的下标）、符号值、符号类型（段还是函数或变量）、符号绑定信息（局部还是全局、弱符号还是强符号）、符号所在段（在段表中的下标）、符号大小（数据类型的大小）。
这里需要注意的是符号值：
- 对段来说，符号值是该段的起始地址，这是编译器生成便于后面快速查询段。
- 对函数和变量来说，符号值是它们的地址。
由此可见，符号表类似于“路由器”的角色，它能告诉我们某个符号在哪个位置，当然目标文件中的符号表并非一个已经知晓所有“路由信息”的“路由器”，在后文分享链接时会详细说明。
弱符号与强符号
符号分为弱符号与强符号，对于 C/C++ 来说，编译器默认函数和已初始化的全局变量为强符号，未初始化的全局变量为弱符号，可以使用__attribute__ ((weak))定义一个弱符号，编译器决议符号时有如下规则：
- 不允许强符号被多次定义。
- 多个符号名重复且只有一个强符号时，选择强符号。
- 多个符号名重复且都是弱符号时，选择占用空间最大的一个。
弱符号的场景：组件提供弱符号的默认函数，开发者可以使用强符号的自定义函数覆盖实现。与弱符号对应的还有弱引用，如果弱引用的符号有定义，链接器决议该符号，如果弱引用的符号未定义，链接器不认为是一个错误。
BSS 段
BSS 段存放是的未初始化的局部静态变量，不同编译器实现可能有差异，所以主要是理解思想。
BSS 段在图中之所以标记为灰色是因为它不占用目标文件空间（可以理解为不占磁盘空间），但在装载时和其它段一样分配虚拟空间。应该很容易想到，未初始化的局部静态变量之所以不占用磁盘是因为它们的默认值都为 0，既然都是 0 就没必要专门拿磁盘空间来存它们的值。如果局部静态变量初始值设置为了 0，编译器仍然可能进行优化，把它放到这个 BSS 段。
BSS 段存在的意义就很明显了：节约磁盘空间。
排除只会存在于栈中的局部变量、存在于只读数据段的常量，还有一种符号可能也会放入 BSS 段：未初始化的全局变量。GCC 不会将其放入 BSS 段，而是在符号表中将其标记为 Common（具体看静态链接 Common 块）。
二、静态链接
注意：此部分说的地址若非特别指明均指虚拟地址。
模块在编译成目标文件的过程中，编译器会试图修正内部的符号引用，如果符号是定义在模块内部的，直接修正调用地址（多是相对调用，并没有确定实际虚拟地址）；如果符号是定义在模块外部的，编译器则无法得知这个符号的调用地址。
这个外部符号可能定义在其它目标文件中（这部分不考虑定义在共享文件中的情况），如何修正外部符号的引用正是静态链接的核心问题。
静态链接是指将多个目标文件合并为一个可执行文件，直观感觉就是将所有目标文件的段合并。需要注意的是可执行文件与目标文件的结构基本一致，不同的是是否“可执行”。
另外，可执行文件要被操作系统装载到内存中运行，所以还需要为其分配虚拟地址。
空间与地址分配
注意：页映射、装载相关请看后文。
首先需要明白有页映射机制的存在，虚拟页与物理页大小一致，装载是以页为单位的，通常情况下需要保证一个虚拟页的信息的访问权限一致。
按序叠加
最简单的方式是将各个目标文件的段按顺序叠加，这样做有个很大的问题就是无法判断相邻段之间的访问权限是否一致，所以虚拟页分配时只能将每一个段都视为不同属性。那么如果页大小是 4096 字节，即使段只有 1 字节，也要占用一个虚拟页大小的地址空间，这样会造成很多内存碎片浪费空间。
相似段合并
采用相似段合并策略，将相同属性的段合并有利于管理，装载完所有段将使用更少的虚拟地址页，有效降低内存消耗（在装载部分有分析进一步的优化）。
空间分配过程完成后，每个段的虚拟地址就确定了。值得注意的是，图中段的位置并不是表示虚拟地址，而是可以理解为在磁盘中的位置。那么段的虚拟地址存放在哪儿呢？实际上就是存放在前面提到的段表里面，段表数组元素有一个属性就是段虚拟地址。
需要注意的是，所有目标文件的符号表会合并为一个 全局符号表 ，这是一个非常重要的段。
内部定义符号地址的确定
段的虚拟地址确定后，就需要确定每一个段中的符号地址，之前提到的编译时修正符号地址只是一个相对地址，比如0 + 0x66 (0x66表示符号在段中的偏移)。这里修正的方式很简单，就是段起始地址+符号偏移，比如段起始地址为0x88888888，则修正为0x88888888 + 0x66。
绝对地址引用比相对地址引用速度更快，所以链接器会尽可能的将符号引用修正为绝对地址引用。
另外，还要将 全局符号表 中对应的符号地址就行修正。
需要注意一点，这个步骤修正的仍然是某个段内部定义的符号，而对于这个段引用的外部符号仍然处于待修正状态。
重定位表
经过上面的步骤，可执行文件生成了，各个段及其内部符号引用虚拟地址确定了，还差最后一步：修正各个段中对外部符号的引用地址，这个过程称为 重定位 （各个目标文件已经合并为一个文件了，这里说的外部符号其实是对于合并之前而言）。
在这之前需要了解一下重定位入口的集合——重定位表。每一个需要重定位的段都有一个与之对应的重定位表。
重定位表也是一个结构体数组，该结构体包含：
- 重定位入口的偏移，即需要修正的位置相对于段起始的偏移。
- 重定位入口的符号在符号表中的下标。
- 重定位入口的类型。
符号解析与重定位
基于前面介绍的各种段结构，符号解析与重定位过程实际上非常简单，无非就是根据重定位入口的符号在符号表的下标，找到该符号对应的目标地址，找出重定位表对应的段，根据重定位入口的偏移填入这个目标地址。
链接器扫描完所有的重定位表，所有的重定位入口符号都能在全局符号表中找到，否则链接器就会报符号未定义错误。
Common 机制
Common 机制可以理解为延迟决议，即可能有多个不定因素影响，在考虑完所有不定因素后才能决议。
未初始化的全局变量属于弱符号，编译器将其标记为 Common。对于某个目标文件来说，它无法确定其它目标文件中是否有强符号或者占用字节更长的弱符号（强弱符号前面有讲解）。所以只有在链接器遍历完所有目标文件后才能确定这个符号的占用空间大小，那个时候再去为未初始化的全局变量在 BSS 段分配虚拟空间。
这么处理的直接原因是编译器允许符号重名。
三、装载
可执行文件存在于磁盘中，需要读入内存才能由 CPU 执行，在讨论如何将可执行文件装载之前，需要先了解物理内存分配策略。
物理内存分配策略
这里主要讨论物理内存如何为各个进程分配空间。最简单的方式就是直接为进程划分物理内存区域，这会有很多缺点：
- 地址空间不隔离。程序直接访问物理地址很容易出现进程间相互影响。
- 内存使用效率低。如果运行 A、B 两个程序就用尽了物理空间，启动 C 程序就只能将 A 或 B 换出到磁盘，然后把 C 读入内存，效率很低。
- 程序运行地址不确定。由于空闲的物理地址不确定，那么程序中使用的绝对地址引用很可能是需要重新修正的，如果运行时去做这个事情将会非常耗时。
虚拟内存
加入虚拟内存中间层，直接解决地址空间不隔离、程序运行地址不确定的问题。我们在前文所提到的地址都是指的虚拟地址，对于每一个进程来说，都是自己独占虚拟内存空间，而最终的物理地址区域由操作系统映射。
然而，单纯的将程序所占虚拟地址空间直接映射到物理内存无法解决内存使用效率低的问题，物理内存仍然会快速消耗殆尽。
页映射机制
程序局部性原理：一个程序在运行时，某段时间内只使用到了一部分程序数据。所以将虚拟地址、物理内存、磁盘空间都划分为页为单位，写入物理内存的粒度缩小为页，而非整个程序。
虚拟地址空间中的页称作 虚拟页 (VP, Virtual Page) ，物理内存中的页称作 物理页 (PP, Physical Page) ，磁盘中的页叫做 磁盘页 (DP, Disk Page) ，进程捕获到虚拟页未装载时称为 页错误 (Page Fault) ，虚拟地址到物理地址的转换一般使用 MMU (Memory Management Unit) 。
核心思路：进程读取某个地址时，其所在虚拟页 A_VP 发现未绑定物理页 A_PP，发生页错误，操作系统接管进程，找到虚拟页 A_VP 对应的磁盘页 A_DP，将 A_DP 写入物理页 A_PP（若物理页使用殆尽会使用淘汰算法去清理或压缩部分物理页），将 A_VP 与 A_PP 绑定，之后控制权交由进程，访问地址成功。
可执行文件生成时，如何提高物理内存使用率
前面已经分析了，可执行文件将段按照页整数倍来分配虚拟地址，虽然已经将所有目标文件中相似段合并了，但每个段对于一个页（比如 4096 字节）来说还是太小了，仍然会浪费很多虚拟地址空间，从而映射后也会浪费物理内存。
Segment 与 Section
对于操作系统来说，它并不关心每个段的类型，主要是关心它们的访问权限。所以，前面提到的相似段合并的过程中，不仅将多个相似 Section 合并为一个 Section，链接器还会尽量将权限相同的 Section 放在一起，称之为 Segment 。
那么链接器在进行虚拟地址分配时，就不用让每一个 Section 进行页对齐，而是让每一个 Segment 进行页对齐，如此一来进一步节约了虚拟地址空间。思考一下便知，Segment 只是在装载时有用，在分析可执行文件及其链接过程只需要关心 Section 也不会有什么问题。
装载时是以 Segment 为单位的，访问权限需要基于这个 Segment 来设置。那么实际上有一个装载时很重要的段：程序头表 。
程序头表也是结构体数组，每一个元素包含 Segment 在文件中的偏移、虚拟地址起点、访问权限（Segment 中所有 Section 访问权限一致）、虚拟地址空间长度、文件中空间长度等。
值得提出的是 关于 BSS 的处理 。对于 Segment 来说，可能并不能撑满一个页大小，那么就可以拓展一些虚拟空间，即其 虚拟地址空间长度 > 文件中空间长度 ，这表示拓展的部分只在装载时占虚拟空间而不占磁盘，这正好用来存放各个 BSS Section。考虑其访问权限，需要注意的是 BSS 可以和数据 Segment 合并，但不能和指令相关 Segment 合并。
BSS Section 见缝插针，进一步减少了内存碎片。
段地址对齐
尽管已经按照 Segment 装载可执行文件，仍然存在一些内存碎片，所以有些 UNIX 系统做了更进一步的优化：将 Segment 接壤部分共享一个物理页，然后将物理页映射两次。
然而这么做过后， Segment 的虚拟地址就不再是页大小的整数倍了，就涉及到一些计算这里不展开了。
可执行文件的装载
根据前面分析的页映射机制，可执行文件装载进内存需要两个映射关系：
- 虚拟空间 : 物理内存
- 虚拟空间 : 可执行文件
创建一个进程，或者说创建一个虚拟空间，第一步是操作系统创建一个页目录（Page Directory），也就是虚拟空间与物理内存的映射表，映射关系可在发生页错误时设置。
第二步是建立虚拟空间与可执行文件的映射关系。前面已经分析过了，可执行文件的 程序头表 已经包含了每一个 Segment 的虚拟地址、在文件中的偏移。那么通过读取程序头表就能确定每一个虚拟页对应的可执行文件区间（如果是以 Section 来装载，这个思路同样适用于段表）。
第三步就是将 CPU 指令寄存器设置为可执行文件入口，启动运行。
四、动态链接
不将某些目标文件静态链接在一起，而把链接过程推迟到运行时，这是 静态链接 的基本思想。这样能实现一个最重要的功能，就是共享的目标文件在内存中只需要存在一份，然后由多个进程进行链接使用。这种共享的目标文件一般称作 共享对象、共享库、共享模块 。
该图简明的表示了共享对象实现原理，进程 A 和 B 只使用了一份共享对象的指令内存数据。
动态链接共享对象带来的好处：
- 多个进程运行时节约物理内存。
- 减少编译和静态链接的时间消耗，降低可执行文件所占磁盘空间。
- 共享对象的更新和发布更便捷，可执行文件一般不用重新编译链接。
- 通过共享对象来做复杂的系统兼容，增强可执行文件的兼容性。
- 程序在运行时动态加载程序模块，便于制作插件。
动态链接的缺点：
- 运行时重定位拖慢了程序启动速度（通过 延迟绑定 优化）。
- 共享对象的间接寻址效率较低。
大致说明了动态链接的原理和特点，下面来具体分析技术细节。
共享对象的虚拟地址如何确定
简单方案： 共享对象虚拟地址固定 。那就得在可执行文件的段分配虚拟地址时，为所用到的共享对象预留虚拟空间，似乎能解决问题。不过细想一下，这样做存在两个问题：
- 程序每引入一个共享库或者共享库更新后占用空间更大，就需要预留更大的虚拟空间，可执行文件或许就要重新编译。
- 共享对象更新时，内部的符号地址可能变化，可执行文件又得重新编译。
这些是致命问题，所以直接舍弃这种思路。
正确的思路是：装载器根据当前虚拟地址空间空闲情况，动态分配一块虚拟空间给共享对象。
装载时重定位
共享对象并非完全能被多个进程复用（参照上面共享对象实现的图），一般只有指令部分是进程共享的，而数据部分仍然是进程独立的。原因很简单，数据部分多是可读写的，进程间只能使用独立的副本，而指令是只读的，多进程共享也没有影响。
共享对象的虚拟地址是装载器动态分配的，那么共享对象的数据段里面绝对地址引用是需要修复的。
和目标文件一样，共享对象数据段中若有绝对地址引用，会生成对应的重定位表，当动态链接器把这个共享对象装载后，会根据重定位表将数据段中的地址引用修正。这个方法叫做 装载时重定位 。
对于共享对象的指令部分来说，无法使用装载时重定位来处理 。因为我们说的装载实际上是指装载到虚拟空间，那指令部分的绝对地址引用就需要根据当前进程的虚拟地址进行修正。然而各个进程的虚拟空间是独立的，所以被修正的指令部分并不能被其它进程使用。
PIC 技术
地址无关代码 (PIC, Position-independent Code) 技术：把指令中需要被修改的部分分离出来跟数据部分放在一起，那么指令部分装载后就不需要修正内部引用地址，从而实现多进程共用。
模块内部的数据访问、调用或跳转
和目标文件一样，共享对象中的函数地址、变量的相对位置是不变的，所以调用和跳转通过相对地址调用指令就能处理了，数据可以通过当前 PC 值加上偏移量来访问。
模块间的数据访问、调用或跳转
模块间的符号引用要在装载时才能确定，这对于每一个进程来说都是需要修正的。处理方式是，在数据段里面建立一个指向这些变量的指针数组，这个指针数组称作 全局偏移表 (Global Offset Table, GOT) 。指令通过相对寻址就能找到数据段中的 GOT，从而找到需要访问变量的目标地址。
共享对象的全局变量
定义在模块内部的全局变量，有一种特殊情况：extern int global;。这时编译器其实判断不了这个符号是定义在内部还是外部的，就不知道该不该分配空间。在共享库编译时，编译器处理方式是默认把定义在模块内部的全局变量当做定义在其它模块，通过 GOT 实现。动态链接时就能进行判断：若可执行文件中有副本，指向该副本；否则指向该共享对象中的副本。
全局符号介入
加入全局符号表时，一个共享对象 里的全局符号被 另一个共享对象 同名全局符号覆盖的现象称作全局符号介入。如果一个共享对象中使用相对寻址访问这个全局符号，发生全局符号介入时就可能需要对这个引用重定位了，那么这个共享对象的指令部分就不能实现 PIC 了。所以对于全局符号来说，同样采用 GOT 方式来访问。
动态链接相关的段
Dynamic 段 类似于文件头，是动态链接重要结构，包含了动态链接符号表、动态链接重定位表、动态链接字符串表、依赖的共享文件（递归加载所有依赖）等。这些眼熟的表名字实际上功能结构和静态链接时那些表非常相似。最大的区别就是目标文件的重定位是在静态链接时完成，共享对象的重定位是在装载时完成。
值得提出的是可执行文件也可以编译为共享对象形式。
动态链接的实现
- 动态链接器 自举 。
- 根据共享对象 Dynamic 段的依赖共享文件属性可形成了一个树结构，动态链接器一般使用广度优先搜索装载这些共享文件。装载共享文件时，它的符号表合并入全局符号表。装载完所有共享文件时，全局符号表包含进程中所有的符号。
- 动态链接器遍历可执行文件和所有共享对象的重定位表，通过重定位入口符号在全局符号表中找到对应的目标地址，通过重定位入口偏移将这个目标地址填入合适的位置（这和静态链接过程基本一样）。
后语
本文的编排和《程序员的自我修养 —— 链接、装载与库》类似，有很多笔者的总结、提炼、串联的描述，总的来说算是形成了逻辑通路，希望能为读者朋友提供一些帮助。
对于编译、链接、装载相关的技术细节，可能需要深入到具体平台去研究，不然总是有些挥之不去的盲点。不过只要对基本流程原理有所把握，相信这并非难事。