通过链接编译复杂的软件（一）—— 主要步骤和要解决的问题

在从汇编的角度理解程序中我们了解到，程序主要是执行汇编指令来操作数据。这些汇编指令和大部分数据，除了其自身的值外，也都有固定的运行时内存位置。这些值和内存位置，由程序源码通过编译和链接而确定下来，并全部被保存在磁盘上的可执行文件中。操作系统把文件中的指令和数据值加载到内存中对应的位置，再把 PC 寄存器设置到 main 函数指令的开始内存位置，从而开始执行程序。
在编译时，源代码(.c文件)首先通过预处理器来处理宏、注释等编程语言语法上的问题，形成 ASCII 中间件文件(.i文件)。之后，编译器把编程语言翻译成 ASCII 码的汇编语言文件(.s)。最后，汇编器把汇编语言文件翻译成二进制的可执行文件。
理论上来说，只需要编译这一个步骤就能确定汇编指令和变量的值和内存位置了，但是在实际工程中运行时内存位置却是在链接时最终确定的。更详细点说，就是每份源码单独编译成一个 ELF 文件(Executable and Linkable Format，意即可被执行又可被链接)，其中只包含了该份源码本身的指令和变量的值，然后通过把所有的 ELF 文件链接在一起，为所有的指令和变量生成独特的运行时内存位置。
这样的好处是，当我们修改一个源代码文件后，只需要重新编译一个文件，再链接所有的文件。而且这种方式还附赠了一个便利：链接第三方库编译出来的 ELF 文件就能使用库提供的功能，免去了获取源码和编译源码的烦恼。
但是这些好处不是免费的，有两个明显的和内存位置相关的问题需要解决：

• 对于在此处引用但是在其它源码中定义的变量和函数，怎么找到他们？
• 怎么为每个 ELF 文件中的变量和函数生成独特且不彼此覆盖的内存位置？

解决方案分别可以用关键词概括：符号表和重定位。

一、ELF 格式的基本结构

首先我们还是得对 ELF 文件的格式有个大概了解，它既是符号表和重定位机制的仰仗，又是它们的最终目的。
我们先来考虑最简单的情况——不需要分离编译从而不用符号表和重定位的情况。
在这种情况下，我们需要为所有的函数代码和变量生成内存位置。理论上来说我们可以把内存位置设置为操作系统允许范围内的任何值，只要我们能找到它们。但是出于节省内存空间的考虑，我们希望缩小内存值的范围，小到刚刚好覆盖所有函数和变量的内存需求。同时，为了减少不必要的寻址操作以及提高寻址效率，我们希望把逻辑相关的函数和变量地址紧挨在一起。
于是，ELF 文件格式就被设计成如此的文件布局：函数代码(汇编指令)以二进制的形式集中保存在一起，中间没有任何间隔，称之为代码节。二进制的代码节被加载到内存后，保持着和原来完全相同的比特布局。于是，只要确定第一个代码指令的地址为 s 后，其它代码指令的地址也就确定 s 加上它们各自在代码块中的位置偏移。
变量也是被如此处理，所有变量以二进制形式保存它们的值，并集中在数据节。不过不是所有的变量都需要在数据节中占有一席之地。对于那些没有初始化或者初始化为零的变量，我们不需要在数据节中保存一个 0 值，只需要在加载程序的时候把这些变量在内存中初始化为 0(节省磁盘空间)。而这些变量都被映射到了一个实际不占空间的节中。

• .text 节，以二进制紧凑保存函数代码(汇编指令)；
• .rodata 节，read-only-data，只读数据节，保存比如函数中的 switch 跳转表，printf 中的格式化字符串；
• .data 节，保存已经初始化的全局变量和静态变量。局部(栈)变量保存在 .text 的汇编指令中；
• .bbs 节，一个不占任何磁盘空间的节，“保存” 那些没有初始化的静态变量，以及那些初始化为 0 的全局变量和静态变量；

虽然还有 .debug、.line 和 .strtab 节，但它们主要用作 debug 用途。如果只是为了实现编译的核心功能的话，如上四个节就够了。
除了这些之外，还有 ELF 文件头(保存这个文件的 Meta 信息, 比如大小端和字大小等等)以及节头部表(保存每个节在文件中的位置和大小)。
接下来我们逐个来解决符号引用和重定位的问题。

二、符号表是怎么发挥作用的

我们把每个单独编译的源文件称之为模块，把其中定义和引用的全局或静态函数和变量称之为符号。对于任何模块 m 中的符号 s ，根据其定义和引用的情况，可以分为三类：

• m 定义且能被其它模块引用的符号(非静态全局函数或非静态全局变量)，称之为全局符号
• 其它模块定义且被 m 引用的符号，称之为外部符号
• 只被 m 定义且只被 m 引用的符号(静态函数和静态变量)

对于模块 m 来说，链接器需要知道哪些符号是 m 没定义且引用的外部的，这样在链接时就能去向外部寻找对应的符号。它也需要知道哪些符号是 m 定义且能够给外部使用的，以便在链接时暴露给其它模块。暂且把这个问题称之为符号供需统计问题。
它还需要处理一些特殊情况，比如被 m 引用的符号在其它模块中也没有找到，或者在其中找到了多个定义。暂且把这个问题称之为符号供需不平衡问题。

2.1 用符号表统计符号供需情况

为了统计所有模块的符号供需情况，ELF 文件中额外使用 .symtab 符号表来记录所有的符号。每一个符号在符号表中都有一个对应的记录，这个记录的数据结构为:

struct {
    int     name;
    char    type:   4,
            binding: 4;
    char    reserved;
    short   section;
    long    value;
    long    size;
} symble;

其中 name 是 .strtab 字符表中的 index，使用它可以在 .strtab 中找到符号以 '\0' 结尾的名字字符串。
type 和 binding 共享一个 char 的 8 个比特，前者用于标记符号是函数还是变量，后者用于标记符号是本地的还是全局的。
section 是节头部表的 index，根据这个可以知道符号是属于 .data 节还是 .text 节，是 .common 节还是 UND(未定义)，或者是 ABS(绝对地址)。section 的值影响到如何解释 value 和 size。如果 section 的值是一个常规的数值，则 value 为符号在节中的字节偏移，size 是符号在节中的字节长度；如果 section 值是 ABS，则 value 为符号的绝对内存地址(在链接时不会被重定位)。section 为常规值或者 ABS 则意味着符号为定义已知的，如果符号是全局的话，则说明它是被供给的符号。
如果 .section 是 UND，则说明符号是在本模块引用但是没有定义的，需要在链接时需要，属于被需求的符号。
如果 section 是 COMMON 值，则 value 为符号的对齐要求，size 为符号的最小字节大小，符号映射在 .common 节。.common 之前没说，其实它和 .bbs 节很类似。初始化为 0 的静态符号以及全局符号，加上未初始化的静态符号，都指向 .bbs 节，而未初始化的全局符号都指向 .common 节。未初始化和初始化为 0 的符号，理论上都可以在加载时初始化为 0，但是初始化为 0 比不初始化带有更明确的主观意图。当符号是全局的时，如果一个符号被定义了多次，编译期就可以在二者中选择主观意图更强的(选择 .bbs 中的)。如果 section 是 COMMON 值，则说明这个符号虽然可以用作供给，但是用不用还要再做决定。
还有一个 reversed 字段，只是出于内存对齐的考虑而存在，暂时没有用途。

符号表不仅告诉我们怎么找到本模块中定义的符号，而且明白反应了哪些符号可以出口，哪些需要进口，哪些自给自足，哪些符号要看价格(主观意图)再决定。
接下来我们看看，如何通过进出口活动来解决模块的符号供需不平衡问题。

2.2 解决符号供需不平衡的问题

在链接时，链接器按照这些文件从左到右的方式依次处理它们的符号供需问题。链接器会维护三个集合：可重定位文件集合 E、找到定义的符号 D 和未找到定义的符号 U。每当链接器开始处理一个文件 f 时，执行以下操作：

• 1.把文件 f 加入到 E
• 2.在 D 里面搜寻文件 f 中定义的符号，如果找到了且找到的不是 COMMON 类型的符号则报错，一般是 redefinition of xxx，如果找到了但是 COMMON 类型的符号则随意选择一个
• 3.把 f 定义的所有符号添加到 D 里面去
• 4.在 D 里面搜寻文件 f 中引用的符号，如果没找到就把它加入到 U 里面去，如果找到了就什么都不做
• 5.当所有文件处理完后，如果 U 不是空的，则说明有符号定义未找到，此时会报错，一般是 undefined reference to xxx

三、重定位机制的细节

解决了分离编译情况下的函数和变量引用的问题后，我们再深入重定位机制的细节，看看链接器是如何为所有函数和变量找到独一无二的内存地址的。
当链接器完成符号解析的工作后，我们会得到一个包含所有目标文件的集合 E。链接器把所有这些目标文件中相同的节紧凑地合并到一起来得到最终的二进制可执行文件。和 ELF 文件一样，文件中的代码和变量在加载到内存后仍然有着相同的比特布局，因此，我们很容易就能为这些代码和变量生成独特的运行时内存地址。
问题在于，那些被引用的符号虽然有了最终的内存地址，但是之前引用这些符号时所使用的地址还没有被改过来。要解决这个问题，同样有两个子问题要处理：

• 找到文件中哪些地方是在引用符号
• 把引用符号的地方所使用的临时内存地址改成符号最终的内存地址

为了解决这两个问题，编译器在编译期间，为每个符号引用生成了一个重定位条目，并保存在独立的重定位节里面。.data 的重定位条目保存在 .rel.data 节里面，.rel.text 的重定位条目保存在 .rel.text 节里面。
重定位条目的数据结构如下所示：

struct {
    long    offset;
    long    type:32,
            symbol:32;
    long    addend;
} relocation_entry;

offset 表示要重定位的字节在节中的偏移，根据这个可以解决上述第一个子问题。 type 和 symbol 共享 64 个字节，前者表示重定位类型(相对还是绝对)，后者表示符号对应的符号条目在符号表中的 index。addend 是一个在编译期间决定的常量，一般来说，正在被重定位的字节的内存地址 refaddr 减去 addend 后得到下一个指令的地址。从重定位条目实现重定位的具体算法可以表示为：

for (const auto section : sections):
    # section 是字符数组
    for (const auto entry: relocation_entries):
        relocating_bytes_position = section + entry.offset;

        if (entry.type == R_X86_64_PC32):
            relocationg_bytes_addr = ADDR(section) + entry.offset
            *relocating_bytes_position = ADDR(entry.symbol) - (relocationg_bytes_addr - entry.addend)
        else if (entry.type == R_X86_64_32):
            *relocating_bytes_position = ADDR(entry.symbol) + entry.addend

理解这段算法的关键在于理解 relocating_bytes_position 和 relocationg_bytes_addr 的意义。前者表明我们要修改的字节 b 的位置，后者表明 b 的运行时内存地址。我们的目的是要把 *b 修改到一个合适的值 x ，以便计算出符号的运行时内存地址。在使用相对寻址时，下一条指令的地址 PC_next 加上 x 则得到符号的运行时内存地址。而 PC_next 等于 b 的运行时内存地址加上 b 自身的字节长度，记录在 entry.addend 里面。由此，我们就能得出 x 的计算公式。
那如何从 entry 计算出 ADDR(symbol)呢？可以先借助 entry.symbol 找到符号表条目，再通过符号表条目找到符号在定义它的节中的位置，从而得到符号的运行时内存地址。

四、可执行文件的基本结构

解决完重定位问题后，链接的主要工作就算完成了，此时得到的 ELF 文件已经是一个可执行文件。
可执行文件和 ELF 文件的结构大同小异，它们都包含文件最开始的 ELF 头，以及其中的 .text、 .rodata、 .data、 .bbs 、 .symtab 、.line、.strtab 节和文件末尾的节头部表。
可执行文件已经完成了所有的链接工作，所以不再需要 .rel.text 和 .rel.data 节来帮助其重定位了，但是它新增了段头部表和 .init 节。段头部表用于提高加载可执行文件到内存的性能，.init 节定义了一个 _init 的初始函数，程序在初始化时会调用它。段头部表的条目如下所示：

struct {
    long    offset;     // 段在文件中的偏移量
    long    vaddr;      // 段被 map 到的虚拟地址空间
    long    paddr;      // 段被 map 到的内存地址
    long    align;      // 段的内存对齐标准
    long    filezs;     // 段的文件大小
    long    memsz;      // 段的内存大小
    char    flags;      // 段内存的读写权限，r-w-x
} segment;

在 64 位 Linux 操作系统中，当系统执行可执行文件时，会依据段头部表把可执行文件的 .init、.text 和 .rodata 加载到以 0x400000 为起始位置的虚拟内存中(只读段)，再往上加载 .data 和初始化 .bbs (读写段)。
加载完内存后，程序跳转到入口点 _start(ctrl.o) -> __libc_start_main(libc.so) -> main(可执行文件)。

总结

汇编指令和变量都有各自独一无二的运行时内存地址，这些内存地址在编译期间就决定了并且记录在可执行文件中。
为了工程上的便利性，编译的过程被分成了两部分。首先是单独编译每个源文件为独立的模块，然后通过链接把所有的模块合并在一起。
合并在一起后，每个指令和符号拥有了独一无二的运行时内存地址，把每个符号引用所使用的地址修改为合并后的地址，就拥有了一个可以完美运行的可执行文件。