CSAPP 07 - 链接

发表于 更新于 分类于 评论数： 阅读次数：

  链接就是将各种代码和数据片段收集并组合成为一个单一文件的过程。

编译过程

  大多数编译系统提供编译器驱动程序如：预处理器，编译器，汇编器，链接器。

  编译一个简单的多文件程序过程如下：

// main.c
int sum(int *a, int n);
int array[2] = {1, 2};

int main()
{
    int val = sum(array, 2);
    return val;
}

// sum.c
int sum(int *a, int n)
{
    int i , s = 0;
    for (i = 0; i < n; ++i)
        s += a[i];
    return s;
}
  1. 预处理：预处理器将源代码翻译为中间文件。

  gcc -E -o main.i main.c

  1. 编译：编译器将中间文件翻译为汇编代码文件。

  gcc -S -o main.s main.i

  1. 汇编：汇编器将汇编代码文件翻译为可重定位目标文件。

  gcc -c -o main.o main.s

  1. 链接：链接器将可重定位目标文件组合起来，输出一个可执行目标文件。

  gcc -o main main.o sum.o

静态链接

  Linux ld 这样的静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的，可以加载运行的可执行目标文件作为输出。

  链接器需要完成两个主要任务：

  • 符号解析：目标文件会定义和引用符号，而每个符号对应一个函数、全局变量或静态变量。符号解析的目的是将每个符号引用与一个符号定义相关联。
  • 重定位：编译器和汇编器生成的代码和数据节是从地址 0 开始的，链接器通过将每个符号定义和内存位置关联起来，从而重定位这些节，然后修改所有对符号的引用，使他们指向这个内存位置。

  目标文件只是字节块的集合，其中可能包含代码、数据或指导链接器和加载器的数据结构。链接器将各个块连接在一起，确定整个块的运行时位置，并修改代码和数据块中的不同位置。编译器和汇编器在生成目标文件时已经完成了大部分工作，因而链接器对目标机器的了解甚少。

目标文件

  目标文件有三种形式：

  • 可重定位目标文件：包含二进制代码和数据，可以在编译时与其他可重定位目标文件组合以创建可执行目标文件。
  • 可执行目标文件：包含二进制代码和数据形式，可直接被复制到内存中执行。
  • 共享目标文件：一种特殊类型的可重定位目标文件，可以在加载时或运行时被加载到内存中并动态链接。

  编译器和汇编器生成可重定位目标文件，链接器生成可执行目标文件。一个目标模块就是一个字节序列，而目标文件就是一个以文件形式存放在磁盘中的目标模块。

可重定位目标文件

  上面是一个典型的 ELF 可重定位目标文件的组成。其中 ELF 头以一个 16 字节的序列开始，描述了生成该文件的系统的字的大小和字节顺序。剩下的部分是帮助链接器语法分析和解析目标文件的信息：

  • ELF 头的大小
  • 目标文件的类型 (如上)
  • 机器类型 (如 x86-64)
  • 节头部表的文件偏移
  • 节头部表中条目的大小、数量 (描述了节的位置和大小)

  夹在 ELF 头和节头部表之间都是节，一个典型的 ELF 可重定位目标文件包含以下几种节：

  • .text：编译后程序的机器码。

  • .rodata：只读数据，例如 printf 中的格式字符串，Switch 语句的跳转表等。

  • .data：已初始化的全局变量和静态变量。非静态局部变量在运行时位于栈中，不会出现在 .data 或 .bss 中。

  • .bss：未初始化的静态变量，以及初始化为 0 的全局变量和静态变量。.bss 只是一个占位符，在目标文件中不占用实际空间。这些变量在运行时被分配到内存中，初始值为零。

  • .symtab：一个保存了在程序中被定义和引用的函数和全局变量信息的符号表。与编译器中的符号表不同，.symtab 中的符号表不包含任何局部变量。

  • .rel.text：当链接器将目标文件与其他文件组合时，.text 中的许多位置都需要被修改，而 .rel.text 中则保存了与之相关的重定位信息。通常，任何调用外部函数或引用全局变量的指令都需要被修改，而调用局部函数的指令则不变。可执行目标文件一般不需要重定位信息，因此这部分可以省略。

  • .rel.data：被引用或定义的任何全局变量的重定位信息。通常，所有初始值为全局变量地址或外部定义函数地址的已初始化全局变量都需要被修改。

  • .debug：调试符号表，仅在使用-g选项调用编译器驱动时出现。

  • .line：原始程序中行号与 .text 中机器代码指令之间的映射关系，仅在使用-g选项调用编译器驱动时出现。

  • .strtab：一个以 NUL 结尾，包含 .symtab 和 .debug 中的符号表以及节名称的字符串序列。

符号和符号表

  每个目标文件都有一个符号表，其中包含了该文件所定义和引用的符号信息，符号有以下三种：

  • 全局符号：由该文件定义并且可以被其他文件引用的符号。
  • 外部符号：被该文件引用但由其他文件定义的符号。
  • 局部符号：由该文件定义但无法被其他文件引用的符号，即使用static声明的函数和变量。

  在 C 程序中，全局符号的符号名是唯一的，但是在不同函数内可以声明同名的局部静态变量：

int f()
{
    static int x = 0;
    return x;
}

int g()
{
    static int x = 1;
    return x;
}

  此时两个 x 变量会生成在 .bss 或者 .data 中，编译器可能将x.1作为函数 f 中的变量符号，将x.2作为函数 g 中的变量符号。汇编器使用接收到的汇编代码文件中的符号构建符号表，其中每个条目的数据结构为：

typedef struct {
    int name;        /* String table offset */
    char type:4,     /* Function or data (4 bits) */
         binding:4;  /* Local or global (4 bits) */
    char reserved;   /* Unused */
    short section;   /* Section header index */
    long value;      /* Section offset or absolute address */
    long size;       /* Object size in bytes */
} Elf64_Symbol;
  • name：符号名在字符串表 .strtab 中的偏移量。
  • value：在可重定位目标文件中是符号在其节中的偏移量，在可执行目标文件中是符号的运行时地址。
  • size：符号的大小。
  • type：符号的类型。
  • binding：符号是局部的还是全局的。
  • section：符号所在的节在节头部表中的索引。

  注意，除了常见的几个节以外，还有三个伪节，伪节不占据可重定位目标文件中实际大小：

  • ABS：不应重定位的符号。
  • UNDEF：在此文件中引用但在其他文件中定义的符号。
  • COMMON：未初始化的全局符号，和 .bss 有细微区别。

  可以使用readelf工具查看可重定位目标文件中的符号表，使用指令readelf -s main.o。

符号解析

  链接器将每个符号引用与符号表中的符号定义相关联以完成符号解析。当编译器遇到未在当前文件中定义的符号时，它会假设该符号已在其他文件中定义，然后生成对应的符号表条目。如果链接器无法在任何输入文件中找到该符号的定义，那么它就会终止链接。

  不同文件可能定义了相同名称的全局符号。对于这种情况，链接器要么直接报错，要么选取其中之一。

重定义的全局符号

  Linux 编译系统会在编译时将全局符号分为两种类型：函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。汇编器将符号的强弱信息隐式地编码到目标文件的符号表中。

  链接器解析名称重复的符号的规则为：

  • 不允许多个强符号名称重复。
  • 若一个强符号和多个弱符号名称重复，选择强符号。
  • 若多个弱符号名称重复，从中任选其一。

  伪节 COMMON 和 .bss 的区别也在这里，如果一个可重定位目标文件中定义了一个非静态的且未初始化的全局变量，那么编译器将无法确定它在哪个文件中被定义，所以将它标记为 COMMON 并交给链接器处理。

  注意，现代编译器已经很少使用 COMMON 伪节，而是将未初始化或零初始化的全局变量和静态变量都分配到 .bss 节中。.bss 节不占据可重定位目标文件的实际大小，这些变量也被放到运行期被初始化。

链接静态库

  编译系统将一些相关的目标模块打包到一个文件中，该文件被称为静态库。在构建可执行目标文件时，链接器仅复制静态库中被应用程序引用的目标模块，从而减小了磁盘和内存中可执行文件的大小。

  Linux 系统中，静态库也是一种 ELF 文件格式，同时静态库也是一种存档文件：

// addvec.c
int addcnt = 0;

void addvec(int *x, int *y, int *z, int n)
{
    ++addcnt;
    for (int i = 0; i < n; i++)
        z[i] = x[i] + y[i];
}

// multvec.c
int multcnt = 0;

void multvec(int *x, int *y, int *z, int n)
{
    ++multvec;
    for (int i = 0; i < n; i++)
        z[i] = x[i] * y[i];
}

  要创建这些函数的一个静态库 libvector.a，可以使用ar工具：

gcc -c addvec.c multvec.c
ar rcs libvector.a addvec.o multvec.o

  使用这个静态库也十分简单：

gcc -c main.c
gcc -static -o main main.o -L. -lvector

  选项-static告诉编译器应该构造一个完全链接的可执行目标文件，它可以加载到内存并运行，在加载时无需更进一步的链接。-lvector的参数是 libvector.a 的缩写，-L.告诉编译器应该在当前目录下查找 libvector.a。

静态库的符号解析

  符号解析时，链接器会按照从左到右的顺序依次扫描命令行中的目标文件和静态库。在这个过程中，链接器维护三个集合 E U D，其中 E 为可重定位目标文件的集合，U 为被引用但还未找到定义的符号，D 为已扫描过的文件定义的符号，开始时三者均为空。

  • 若命令行中的输入文件为可重定位目标文件，则链接器将其添加到 E 中并更新 U 和 D 中的符号。
  • 若命令行中的输入文件为静态库，则链接器会将 U 中的符号与该静态库中定义的符号相匹配。匹配成功的模块会被添加到 E 中，随后链接器更新 U 和 D 中的符号。当 U 和 D 中的符号不再改变时，匹配结束，任何不在 E 中的静态库模块都将被直接丢弃。
  • 若扫描全部完成时 U 为空，则链接器合并并重定位 E 中所有的目标文件以构建可执行文件。否则，链接器将报错并终止。

  链接器的这种行为限制了命令行中的文件顺序。如果定义符号的静态库出现在引用该符号的目标文件之前，链接就会失败。为了解决这些问题，可以多次输入同一个库。

重定位

  符号解析完成后，链接器会将代码中的每个符号引用与一个符号定义相关联。接下来，链接器开始对目标文件重定位：

  • 重定位节和符号定义：链接器将所有输入模块中相同类型的节合并为一个新的聚合节，然后将运行时地址分配给每个节和符号。
  • 在节内重定位符号引用：链接器修改代码和数据段中的每个符号引用，使其指向正确的运行时地址。

重定位条目

  汇编器在生成目标文件时，并不知晓代码、数据和引用的外部符号在内存中的最终位置。它只会为每个引用生成一个重定位条目，指导链接器如何修改它们。代码的重定位条目放在 .rel.text 中，数据的重定位条目则放在 .rel.data 中。

  ELF 重定位条目的数据结构为：

typedef struct {
    long offset;    /* Offset of the reference to relocate */
    long type:32,   /* Relocation type */
         symbol:32; /* Symbol table index */
    long addend;    /* Constant part of relocation expression */
} Elf64_Rela;

  offset 是需要被修改的引用的节偏移。symbol 是引用指向的符号在符号表中的索引。type 告知链接器如何修改引用。addend 是一个有符号常量，某些类型的重定位使用它来偏置被修改的引用值。

  最基本的两种重定位类型为：

  • R_X86_64_PC32：使用 32 位 PC 相对地址重定位引用。当 CPU 执行一条使用 PC 相对地址的指令时，它会将指令中的目标地址与 PC 当前值（即下一条指令在内存中的地址）相加得到有效地址。
  • R_X86_64_32：使用 32 位绝对地址重定位引用。CPU 直接使用指令中的目标地址作为有效地址，无需进一步地修改。

重定位符号引用

  下面是链接器的重定位算法的伪代码。这里假设每个节 s 是一个字节数组，每个重定位条目 r 是一个 Elf64_Rela 的结构体：

  1. 重定位 PC 相对引用

  2. 重定位绝对引用

可执行目标文件

  链接器将多个可重定位目标文件组合在一起，形成了一个可执行文件，可执行文件也是 ELF 格式，这个二进制文件包含了加载程序到内存并运行它所需的所有信息：

  可执行文件包含程序的入口点，.text .rodata .data 节与可重定位目标文件类似，此外，.init 节定义了一个小函数，程序会调用它来初始化一些变量。因为可执行文件是完全链接的，所以它不需要 .rel 节。

  要运行可执行目标文件，可以在 Linux shell 的命令行中输入它的名字。

  shell 通过调用某个驻留在存储器中称为加载器的操作系统代码来运行程序。任何 Linux 程序都可以通过调用 execve 函数来调用加载器。

  每个 Linux 程序都有一个运行时内存映像。在 Linux x86-64 系统中，代码段总是从地址 0x400000 处开始，后面是数据段。运行时堆在数据段之后，通过调用 malloc 库往上增长。堆后面的区域是为共享模块保留的。用户栈总是从最大的合法用户地址 (248 - 1) 开始，向较小内地址增长。栈上的区域，从地址 248 开始，是为内核中的代码和数据保留的，所谓内核就是操作系统驻留在内存的部分。

  实际上，由于 .data 段有对齐要求，所以代码段和数据段之间是有间隙的。此外，链接器还会使用地址空间布局随机化技术（ASLR）。虽然每次程序运行时这些区域的地址都会改变，但是它们的相对位置是不变的。

动态链接共享库

  静态链接库存在的问题：

  • 静态库和所有的软件一样，需要定期维护和更新。如果应用程序员需要使用一个库的最新版本，他们必须以某种方式了解到该库的更新情况，然后显式地将他们的程序与更新了的库重新连接。
  • 几乎每个 C 程序都使用标准 I/O 函数，比如 printf 和 scanf。在运行时，这些函数的代码会被复制到每个运行进程的文本段中，会造成内存系统资源的极大浪费。

  解决的基本思路：当创建可执行文件时，静态执行一些链接，然后在程序加载时，动态完成链接过程。

  共享库是一个目标模块，在运行或加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。这个过程称为动态链接，在 Linux 系统中通常使用.so后缀来表示。微软的操作系统大量地使用了共享库，它们称为DLL。有两方面的共享方式：

  • 对于一个 .so 文件，所有引用该库的可执行目标文件共享这个库中的代码和数据，而不是被复制和嵌入到引用它们的可执行文件中。
  • 在内存中，一个共享库 .text 节的一个副本可以被不同的正在运行的进程共享。

  注意：静态链接器 ld 在加载器 execve 之前，而动态链接器 ld-linux.so 是在加载器之后。

  在动态链接中，程序包含一个.interp 节，其中有动态链接器的路径名，动态链接器 ld-linux.so 本身就是一个共享目标。加载器会加载和运行这个动态链接器。然后，动态链接器执行下面的重定位来完成链接任务：

  • 重定位库中的文本和数据到一个内存段。
  • 重定位程序中所有对由库定义的符号的引用。

  最后，动态链接器将控制传递给应用程序。

位置无关代码

  现代系统在编译共享库时会生成一种无需重定位即可被加载到内存中任意位置的代码，即与位置无关代码 (PIC)，这样共享库就能被多个正在运行的进程同时引用。

PIC 数据引用

  编译器在 PIC 数据段的开头创建了一个全局偏移量表 GOT，其中的每个条目都对应一个被目标模块引用的全局符号。编译器还会为这些条目生成重定位记录。加载时，动态链接器重定位每个 GOT 条目，使其包含被引用符号的绝对地址。每个引用了全局符号的目标模块都有自己的 GOT。

  无论在何处加载共享模块，其数据段与代码段之间的距离始终相同。因此，代码段中的 addl 与数据段中的 GOT[3] 之间的偏移量是一个运行时常量。当函数 addvec 引用全局变量 addcnt 时，先通过 0x2008b9(%rip) 计算得到 GOT[3] 的地址，然后从中读取加载时被动态链接器赋予的 addcnt 的绝对地址。

PIC 代码引用

  PIC 函数调用的运行时地址是在该函数第一次被调用时确定的，这种技术被称为延迟绑定。当应用程序导入了一个包含成百上千个函数的共享库，却只调用其中一小部分的函数时，这种技术可以大大减少加载时不必要的重定位操作。

  延迟绑定是通过 GOT 和过程链接表 PLT 共同实现的。只要目标模块调用了共享库中定义的函数，那么它就有自己的 GOT 和 PLT。GOT 是数据段的一部分，而 PLT 则是代码段的一部分。

  GOT 和 PLT 在运行时协同工作解析函数地址的过程如下：

  可执行文件中每个对共享库函数的调用都与 PLT 数组中的条目对应。其中，PLT[0] 是跳转到动态链接器的特殊条目，PLT[1] 对应系统启动函数__libc_start_main。从 PLT[2] 开始的条目对应用户代码调用的函数，如图中的 addvec。

  当与 PLT 一起使用时，GOT[0] 和 GOT[1] 包含了动态连接器在解析函数地址时所需的信息，GOT[2] 是动态链接器的入口点。其余的每个条目均对应于一个在运行时需要被解析地址的调用函数，以及一个 PLT 条目。例如，GOT[4] 和 PLT[2] 与 addvec 对应。

  程序第一次调用 addvec 并解析其地址的过程：

  1. PLT[2] 是该函数的入口，程序首先调用它。
  2. PLT[2] 中的第一条指令间接跳转到 GOT[4]。由于最初每个 GOT 条目都指向对应 PLT 条目中的第二条指令，因此控制权将转移到 PLT[2] 中的第二条指令。
  3. PLT[2] 中的第二条指令将 addvec 的 ID 0x1 压入栈中，第三条指令跳转到 PLT[0]。
  4. PLT[0] 中的第一条指令将 *GOT[1] 压入栈中，第二条指令通过 GOT[2] 间接跳转到动态链接器。动态链接器根据被压入栈中的两个条目确定 addvec 的运行时地址并用它覆盖 GOT[4]，最终将控制权转移给 addvec。

  程序再次调用 addvec 的过程：

  1. 程序依然首先调用 PLT[2]。
  2. 此时 GOT[4] 指向了 addvec，因此控制权将被直接转移到该函数。

库打桩

  Linux 链接器允许截获对共享库函数的调用，取而代之执行自己的代码。利用打桩机制，可以追踪对某个特殊库函数的调用次数，验证和追踪他的输出输入值，甚至把它替换成一个完全不同的实现。

  打桩机制的基本思想是：给定一个需要打桩的目标函数，创建一个包装函数，他的原型和目标函数完全一致。利用某种特殊的机制，可以欺骗系统调用包装函数而不是目标函数。

  打桩可以发生在编译时，链接时，或者当程序被加载和执行时。