# 链接 几十年以前，计算机刚刚诞生，人们编写程序时，将所有的代码都写在同一个源文件中，经过长期的积累，程序包含了数百万行的代码，以至于人们无法维护这个程序了。于是人们开始寻找新的方法，迫切地希望将程序源代码分散到多个文件中，一个文件一个模块，以便更好地阅读和维护，这个时候，链接器就粉墨登场了。 ## 一切都是地址 我们知道，数据是保存在内存中的，对于计算机硬件来说，必须知道它的地址才能使用。变量名、函数名等仅仅是地址的一种助记符，目的是在编程时更加方便地使用数据，当源文件被编译成可执行文件后，这些标识符都不存在了，它们被替换成了数据的地址。 假设变量 a、b、c 的地址分别为 0X1000、0X1004、0X1008，加法运算的机器指令为 1010，赋值运算的机器指令为 1110，那么在C语言中实现加法运算的代码为： c = a + b; 生成可执行文件后的机器码为： 1010 0X1000 0X1004 //将两个数据相加的值保存在一个临时区域 1110 0X1008 //将临时区域中的数据复制到地址为0X1008的内存中 编译器和链接器的一项重要任务就是将助记符替换成地址。 ## 汇编语言的诞生 任何程序的执行，最终都要依靠计算机硬件来完成。现代计算机硬件都是大规模集成电路，它只认识高低两个电平（电压），高电平一般为 5V，用`1`表示，低电平一般为 0V，用`0`表示。也就是说，在计算机底层，没有文字、数字、图像、视频等丰富多彩的可视化元素，只有 0 和 1 两个二进制数字，这就是机器语言。 计算机刚刚诞生的时候没有编程语言，人们直接使用机器语言（二进制）编程。现在假设有一种跳转指令，它的二进制形式为 0001，如果需要执行地址为 1010 的代码，那么可以这样写： 0001 1010 > 所谓跳转，就是在执行当前代码块时转而执行其他的代码块。从本质上讲，C语言中的函数就是一个代码块，当发生函数调用时，就会执行其他的代码块，这个过程就是通过跳转指令来完成的。 那么现在问题来了，程序并不是一写好就永远不变化的，它可能会经常被修改。比如我们在地址 1010 之前插入了其他指令，那么原来的代码就得往后移动，上面的跳转指令的跳转地址也得相应地调整。 在这个过程中，程序员需要人工重新计算每个子程序或者跳转的目标地址，这种重新计算各个目标地址的过程叫做重定位（Relocation）。每次程序修改时，这些位置都要重新计算，十分繁琐又耗时，并且很容易出错。 如果程序包含了多个源文件，就很可能会有跨文件的跳转，这种人工重定位的方式在程序拥有多个模块时会导致更加严重的问题。 没办法，这种黑暗的程序员生活是没办法容忍的，于是先驱们发明了汇编语言（Assembly），这相比机器语言来说是个很大的进步。 汇编语言使用接近人类的各种符号和标记来帮助记忆，比如用`jmp`表示跳转指令，用`func`表示一个子程序（C语言中的函数就是一个子程序）的起始地址，这种符号的方法使得人们从具体的机器指令和二进制地址中解放出来。 将上面的机器指令使用汇编代码来书写： jmp func 这样，不管在 func 之前增加或者减少了多少条指令导致 func 的地址发生了变化，汇编器在每次汇编程序的时候会重新计算 func 这个符号的地址，然后把所有使用到 func 的地方修正为新的地址，整个过程不需要人工参与。对于一个有成千上百个类似的符号的程序，人们终于摆脱了这种低级的繁琐的计算地址的工作，用一句政治口号来说就是“极大地解放了生产力”。 符号（Symbol）这个概念随着汇编语言的普及被广泛接受，它用来表示一个地址，这个地址可能是一段子程序（后来发展为函数）的起始地址，也可以是一个变量的地址。 ## C语言的诞生 汇编语言的主要作用是为机器指令提供了助记符，大部分汇编代码和机器指令是一一对应的，这在汇编被发明的初期确实令程序员非常欣喜。 后来随着软件规模的日渐庞大，代码量开始疯长，汇编语言的缺点逐渐暴露出来。汇编虽然提供了多种符号，但它依然非常接近计算机硬件，程序员要考虑很多细节问题和边界问题，并且不利于模块化开发，所以后来人们发明了C语言。 C语言是比汇编更加高级的编程语言，极大地提高了开发效率，以加法为例，C语言只需要一条语句，汇编却需要四五条。 ## 模块化开发 现代软件的规模往往都很大，动辄数百万行代码，程序员需要把它们分散到成百上千个模块中。这些模块之间相互依赖又相互独立，原则上每个模块都可以单独开发、编译、测试，改变一个模块中的代码不需要编译整个程序。 > 在C语言中，一个模块可以认为是一个源文件（.c 文件）。 在程序被分隔成多个模块后，需要解决的一个重要问题是如何将这些模块组合成一个单一的可执行程序。在C语言中，模块之间的依赖关系主要有两种：一种是模块间的函数调用，另外一种是模块间的变量访问。 函数调用需要知道函数的首地址，变量访问需要知道变量的地址，所以这两种方式可以归结为一种，那就是模块间的符号引用。 模块间依靠符号来“通信”类似于拼图版，定义符号的模块多出一个区域，引用符号的模块刚好少了那一块区域，两者刚好完美组合。如下图所示： ![img](http://c.biancheng.net/uploads/allimg/190122/111102B55-0.jpg) 这种通过符号将多个模块拼接为一个独立的程序的过程就叫做链接（Linking）。 ## 符号与链接器 链接（Linking）就是通过符号将各个模块组合成一个独立的程序的过程。 链接的主要内容就是把各个模块之间的相互引用部分处理好，使得各个模块能够正确地衔接。链接器所做的主要工作跟前面提到的“人工调整地址”本质上没有什么两样，只不过现代的高级语言拥有诸多的特性，使得编译器和链接器更为复杂，功能更为强大，但从原理上来讲，无非是找到符号的地址，或者把指令中使用到的地址加以修正。这个过程称为符号决议（Symbol Resolution）或者重定位（Relocation）。 对于简单的C语言程序，链接过程如下图所示。每个模块的源文件（.c 和 .h）先被编译成目标文件，再和系统库一起链接成可执行文件。库（Library）其实是一组目标文件的包，是将一些最常用的代码编译成目标文件后打包存放。 ![img](http://c.biancheng.net/uploads/allimg/190122/1112031937-0.jpg) 系统库这个概念比较模糊，专业一点应该叫做运行时库（Runtime Library）。“运行时”就是程序运行期间，“运行时库”包含了程序运行期间所需要的基本函数，是程序运行不可或缺的，例如输入输出函数 printf()、scanf()，内存管理函数 malloc()、free() 等。 链接过程并没有想象中的复杂，它还是一个比较容易理解的概念。 假设一个程序有两个模块 main.c 和 module.c，我们在 module.c 中定义了函数 func()，并在 main.c 中进行了多次调用，当所有模块被编译成一个可执行文件后，每一处对 func() 函数的调用都会被替换为一个绝对地址。但由于每个模块都是单独编译的，编译器在处理 main.c 时并不知道 func() 的地址，所以需要把这些调用 func() 的指令的目标地址搁置，等到最后链接的时候再由链接器将这些地址修正。 如果没有链接器，我们必须手工修正 func() 的地址。当 module.c 被修改并重新编译时，func() 的地址极有可能改变，那么在 main.c 中所有使用到 func() 函数的地方，都要全部重新调整地址。这些繁琐的工作将成为程序员的噩梦。 有了链接器，我们可以直接调用其他模块中的函数而无需知道它们的地址，因为在链接的时候，链接器会根据符号 func 自动去 module.c 模块查找 func 的地址，然后将 main.c 模块中所有使用到 func 的指令重新修正，让它们的目标地址成为真正的 func() 函数的地址。 这种在程序运行之前确定符号地址的过程叫做静态链接（Static Linking）；如果需要等到程序运行期间再确定符号地址，就叫做动态链接（Dynamic Linking）。 Windows 下的 .dll 或者 Linux 下的 .so 必须要嵌入到可执行程序、作为可执行程序的一部分运行，它们所包含的符号的地址就是在程序运行期间确定的，所以称为动态链接库（Dynamic Linking Library）。 变量和函数一样，都是符号，都需要确定它的地址。例如在 a.c 中有一个 int 类型的全局变量 var，现在需要在 b.c 中对它赋值 42，对应的C语言代码是： var = 100; 对应的汇编代码为： mov 0x2a, var mov 用来将一份数据移动到一个存储位置，这里表示将 0x2a 移动到 var 符号所代表的位置，也就是对 var 变量赋值。 当被编译成目标文件后，得到如下的机器指令： c705 00000000 0000002a 由于在编译时不知道变量 var 的地址，编译器将这条 mov 指令的目标地址设置为 0，等到将目标文件 a.o 和 b.o 链接起来的时候，再由链接器对其进行修正。 假设生成可执行文件后变量 var 的地址为 0x1100，那么上面的机器指令就变为： c705 00001100 0000002a 这种地址修正的过程就是前面提到的重定位，每个需要被修正的地方叫做一个重定位入口（Relocation Entry）。重定位所做的工作就是给程序中每个这样的绝对地址引用的位置“打补丁”，使它们指向正确的地址。 ## 符号的概念 函数和变量在本质上是一样的，都是地址的助记符，在链接过程中，它们被称为符号（Symbol）。链接器的一个重要任务就是找到符号的地址，并对每个重定位入口进行修正。 我们可以将符号看做是链接中的粘合剂，整个链接过程正是基于符号才能正确完成。 目标文件被分成了多个部分，其中有一个叫做符号表（Symbol Value），它的段名是`.symtab`。符号表记录了当前目标文件用到的所有符号，包括： 1. 全局符号，也就是函数和全局变量，它们可以被其他目标文件引用。 2. 外部符号（External Symbol），也就是在当前文件中使用到、却没有在当前文件中定义的全局符号。 3. 局部符号，也就是局部变量。它们只在函数内部可见，对链接过程没有作用，所以链接器往往也忽略它们。 4. 段名，这种符号往往由编译器产生，它的值就是该段的起始地址，比如`.text`、`.data`等。 对链接来说，最值得关注的是全局符号，也就是上面的第一类和第二类，其它符号都是次要的。 所有的符号都保存在符号表`.symtab`中，它一个结构体数组，每个数组元素都包含了一个符号的信息，包括符号名、符号在段中的偏移、符号大小（符号所占用的字节数）、符号类型等。 > 确切地说，真正的符号名字是保存在字符串表`.strtab`中的，符号表仅仅保存了当前符号在字符串表中的偏移。 ## 符号决议（Symbol Resolution） 当要进行链接时，链接器首先扫描所有的目标文件，获得各个段的长度、属性、位置等信息，并将目标文件中的所有（符号表中的）符号收集起来，统一放到一个全局符号表。 在这一步中，链接器会将目标文件中的各个段合并到可执行文件，并计算出合并后的各个段的长度、位置、虚拟地址等。 在目标文件的符号表中，保存了各个符号在段内的偏移，生成可执行文件后，原来各个段（Section）起始位置的虚拟地址就确定了下来，这样，使用起始地址加上偏移量就能够得到符号的地址（在进程中的虚拟地址）。 这种计算符号地址的过程被称为符号决议（Symbol Resolution）。 重定位表`.rel.text`和`.rel.data`中保存了需要重定位的全局符号以及重定位入口，完成了符号决议，链接器会根据重定位表调整代码中的地址，使它指向正确的内存位置。 至此，可执行文件就生成了，链接器完成了它的使命。 ## 全局变量和局部变量 当程序被加载到内存后，全局变量要在数据区（全局数据区）分配内存，局部变量要在栈上分配内存。 数据区在程序运行期间一直存在，全局变量的位置不会改变，地址也是固定的，所以在链接时就能够计算出全局变量的地址。而栈区内存会随着函数的调用不断被分配和释放，局部变量的地址不能预先计算，必须等到发生函数调用时才能确定，所以链接过程会忽略局部变量。 关于局部变量的定位，就是 ebp 加上偏移量，这在编译阶段就能给出计算公式（一条简单的语句），程序运行后，只要执行这条语句，就能够得到局部变量的地址。 总结起来，链接的一项重要任务就是确定函数和全局变量的地址，并对每一个重定位入口进行修正。