Chap.1 Linking and Loading

Linker和Loader做了什么？

Linker和Loader做的事情很简单：将抽象的名字绑定到具体的名字上：地址绑定。抽象的名字，就是函数或变量名，具体的名字，就是函数指令或变量数据在内存中的具体位置。

地址绑定的历史

最早的计算机编程领域中，是直接编写机器指令的，如果程序员想要使用符号代表某个函数，就在编写的指令中用特殊的标记表示符号的定义和使用，最后再将这些标记替换为符号代表的地址。手工完成这项工作非常枯燥，而且每次修改程序后都需要重新进行一遍这项工作，如果程序比较小，这项工作还算比较容易进行，但对于一个大型的，使用了大量库函数的程序而言，这项工作变得非常困难且易错。
最初的计算机存储介质，如磁带，存储空间非常小，当时不同的子过程存储在不同的磁带上，调用子过程就是将另一盘磁带内容加载到计算机中，然后从指定的位置开始执行。完成这项任务的程序，就是最早的loader。
随着后来多算机操作系统的发展，linker、loader的概念开始出现。最早的操作系统没有提供虚拟内存，所有程序都被加载到一个加载时确定的内存位置，只访问自己管理的那部分内存。这导致在编写程序时，无法确定指令地址，必须要在加载时调整指令。这导致程序必须依靠linker和loader来运行，编译时由linker标记程序的哪些部分需要调整，加载时由linker完成调整。
程序的大小很快超出了计算机的内存大小，因此linker提供了一种“overlay”技术，允许按需将程序的不同部分加载到内存中，这项技术可以被视作是虚拟内存的前身，在没有提供虚拟内存机制的平台上，这种技术被广泛使用。“overlay”技术要求程序员自行确定程序被载入和移出内存的时机，是针对特定程序手动实现的虚拟内存机制，因此能够达成更好的性能，在性能受限的平台上，或是在要求严格实时性的平台上，没有提供虚拟内存机制，依然在使用这种overlay技术。
随着硬件重定位（即CPU支持的多任务切换）和虚拟内存技术的进步，linker和loader的任务一度减轻了很多，因为虚拟内存令每个程序都能够获得整个地址空间的控制权，程序又一次可以假定它们会被加载到特定内存位置处，因此可以在编译时确定指令所需的地址。但是，新的需求要求更复杂的linker和loader实现：希望一个程序（共享库）在一台计算机上，存在多个实例时，多个实例能够共享程序的不变的部分（即代码和常量），只有会变化的部分在每个实例内存在。linker和loader，配合特别设计的目标文件格式，提供了共享库文件（shared object）实现了这一目标。
静态连接的库相对简单，因为所有的符号都定义在这个库文件内部，linker在对这个库进行链接时就能够确定所有符号的地址，但是静态库不够灵活和方便，因为每当静态库变化时，依赖静态库的程序都需要重新进行链接。系统后来提供了动态库，只有在使用动态库的程序开始执行时，或者只有当函数被调用时，动态库的符号才会被解析到确定的地址上，因此动态库可以被动态的替换，并且动态库可以依赖其他的动态库。动态链接的库还可以在程序执行期间被加载。

Linking vs Loading

Linker和Loader负责相关但不相同的几个任务：

Program Loading: 将程序从磁盘加载到内存中，准备执行。这个过程还涉及空间分配、为内存设置protection bit、设置虚拟内存页和磁盘的映射关系；
Relocation: Compiler和Assembler一般创建起始地址为0的目标文件，但很少有机器允许将程序真的加载到0地址处。Linker负责将多个子程序组合起来，创建一个新的起始位置为0的目标文件，每个子程序的内容都被重新安排到新的目标文件的各个部分中。当程序最终被加载时，系统会将程序加载到一个特定地址，然后程序会作为一个整体根据加载地址被重定位。
Symbol Resolution: 当程序是由多个子程序组合而来时，不同子程序间的联系通过Symbol建立。Linker会记录符号在库文件中的位置，并对目标文件进行patching（即通过符号表）来将使用符号的指令和符号定义关联上。

虽然在Linking和Loading二者中间有很多重合的部分，还是把负责程序linking的程序称作linker，把负责程序loading的程序称作loader。linker和loader都需要做relocation工作。存在同时完成以上三种任务的，同时作为linker和loader的程序。
linker和loader的一个共同点是它们都是基于object file进行patch完成工作的。

Two-Pass Linking

Linker需要首先扫描所有的输入目标文件，记录所有被引用过的符号、所有定义的符号，利用这些信息linker在第一次扫描后可以建立好符号定义表和符号导出导入表，并且确定所有符号的地址和尺寸、要输出的目标文件的布局。
第二次扫描时，利用上面收集的信息，将符号替换为具体地址，并且根据要输出的目标文件的布局调整输入文件的内容，将修改后的内容写入到输出目标文件中。同时被写入到输出目标文件中的还包括目标文件头信息、重定位表、符号表。如果涉及到动态链接，符号表中还会包含runtime linker所需的解析动态符号必要的信息，以及为了调用动态库过程所需要的胶水代码。
不论是否涉及到动态链接，输出的目标文件中都可以包含符号表信息，程序运行不需要这些信息，但是其他以目标文件作为输入的程序可以利用这些信息。包含符号表信息的动态库文件可以作为linker的输出目标文件参与链接。

Object code libraries

目标文件库，其一种是静态库，是一组目标文件经过打包压缩后产生的文件，本质上就是多个目标文件的集合。但是和目标文件不同的是，linker在查找符号定义时，总是会先从参与链接的目标文件找起，在无法从目标文件中找到符号定义时才会去静态库中查找（这意味着如果所有符号都可以从目标文件中找到，则静态库根本不会参与链接）。
另一种目标文件库是动态库，由于将部分工作延迟到了库加载时，动态库的工作比静态库麻烦些。在linker工作期间，将最终由动态库提供定义的符号标记起来，将负责提供符号定义的动态库名称写入到目标文件中，在程序加载时才最终完成符号绑定工作。

Relocation and code modification

重定位和代码修正是linker和loader任务的核心。当compiler和assembler生成目标文件时，会为文件中定义的符号生成未重定位的地址，为当前文件中没有定义的外部符号生成全0地址。在链接阶段，由linker来修改目标文件以反映符号的实际地址。
示例：

mov a,%eax
mov %eax,b
# 在x86机器上，假设符号a是当前目标文件中定义的，并且其定义处于文件的第0x1234字节处，b是其他文件定义的，则生成的目标文件中上面的指令会变成（其中A1和A3代表mov指令，x86是小端表示的机器，因此字节序看起来是反的）：
A1 34 12 00 00 mov a,%eax
A3 00 00 00 00 mov %eax,b
# 可以看到，当前文件中定义的符号其地址就是符号在当前文件中的地址，其他文件中定义的符号其地址是0
# 假设linker处理了这个目标文件，将a所处的位置相对之前的目标文件向后移动了0x10000，并且b定义在了新目标文件中的0x9A12处，那么上面的这段代码会被修改成：
A1 34 12 01 00 mov a,%eax
A3 12 9A 00 00 mov %eax,b
# 可以看到，由于符号a所处的位置被改变了，linker因此改变了所有引用符号a的代码，将其地址加上了0x10000

在较老的平台上，地址空间一般较小，并且使用绝对地址，对目标文件的修改工作一般比较简单直接，基本上只有像上面那样的重定位工作需要完成。但是在新的平台上需要使用更复杂的技术：

单个指令没有足够的位来容纳直接地址，编译阶段需要插入一些最终会被linker覆盖掉的假指令，最终linker将这些指令所占的bit位替换为符号地址；
编译时让指令引用一个address pool（具体做法是先将address pool基地址加载到一个寄存器处，指令再引用寄存器内容加上address pool中某一项的偏移，来访问address pool中的某一项），linker负责在链接时，将正确的地址填入address pool，并且在调整address pool的同时修正代码中相关的地址。

大多数平台如今支持position independent code，这样的代码即使不经过重定位也能够被加载到任意内存位置正确执行，这样的代码可以在多个程序中共享，但是涉及到引用本模块没有定义的符号时，重定位技术依然是必要的。

Compiler Drivers

大多数情况下程序员感知不到linker的存在，因为在编译的过程中自动调用了linker。多数编译系统都提供了Compiler Driver，在有多个目标文件参与编译时会自动调用linker来生成最终的目标文件。
具体来说，Compiler Driver会首先调用compiler为每个源文件生成目标文件，然后用linker链接所有的目标文件生成最终的目标文件。
在C++这类提供了更多特性的语言的编译过程中，compiler driver做的事情更复杂也更巧妙，例如C++为了按需生成模板代码，就可以先完全不实例化模板，在调用linker检测到linker报错后，再尝试根据linker的错误信息完成模板实例化。

C/C 知识

Linkers And Loaders