CSAPP 7.链接

本章的知识在《程序员的自我修养——链接、装载与库》中都有所提到，复习为主。可能有些说法和本书不同，如段Segment和节Section，希望读者自行甄别。

链接：把各种代码和数据片段组合为一个单一文件的过程，这个单一文件可以被加载到内存并执行

当下的链接主要分为静态链接和动态链接，静态链接于编译时执行，动态链接由装载或运行时执行。

链接的重要意义之一就是增量编译、分离版本控制。我们需要更新部件的时候无需编译其他部分

1 编译器驱动程序

本章将以如下两段代码作为示例

// main.c
int sum(int *a, int n);

int arr[2] = {1, 2};

int main() {
    int val = sum(arr, 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;
}

编译器驱动程序可以理解为编译各部分的封装控制器，对于gcc：

gcc -o prog main.c sum.c

它首先调用预处理器cpp，把源程序c文件翻译为ASCII码中间文件i文件main.i

接下来，它调用C编译器cc1，把main.i翻译为一个ASCII汇编语言文件main.s

然后运行汇编器as，把main.s翻译为目标文件main.o，同样的过程生成sum.o，它们是可重定位目标文件

最后运行链接程序ld，把main.o、sum.o和一些其他的系统目标文件链接起来，创建一个可执行目标文件prog

我们运行prog，shell会调用操作系统中的加载器，把prog的代码和数据复制到内存，把控制转移到prog的起始

2 静态链接

静态链接以可重定位目标文件和参数作为输入，生成一个链接后的可执行目标文件

静态链接主要完成两个任务：

• 符号解析：目标文件中会定义和引用符号，如全局变量，跳转的label、函数，连接器把它们的定义和引用进行关联
• 重定位：链接器重排布代码和数据段的位置，并对符号引用进行修改，使他们真正指向对应的虚拟内存位置

3 目标文件

目标文件主要分为三种，前两种在上面提到过了，它们是

• 可重定位目标文件：包含二进制的代码和数据，额可以在链接时与其它可重定位目标文件合并
• 可执行目标文件：可以直接被复制到内存并执行
• 共享目标文件：Shared Object so，可以在加载或运行时被动态加载进内存并链接

Windows下使用PE格式，Mac系统使用Mach-O格式，Linux和Unix使用ELF格式

4 可重定位目标文件

ELF由ELF头、段表和各段组成

ELF头中包括一些关键描述信息，如字大小、ELF版本、架构、字节顺序等，还有段表的条目大小和数量，帮助我们索引段表。

一个典型的ELF包含如下几个段：

• .text: 已编译程序的机器码
• .rodata: 只读数据，比如switch的jt
• .data: 已初始化的全局和静态变量
• .bss: 未初始化、初始化为0的全局和静态变量，它们在目标文件中不占实际空间
• .symtab: 符号表，存放引用的全局变量和函数信息（但是对执行没有影响，可以通过strip去掉）
• .rel.text：text中需要重定位的位置列表
• .rel.data: 同理
• .debug:调试符号表

5 符号和符号表

符号表包含文件定义和引用符号信息，包括如下三种：

• 由模块定义、能被其它模块引用的全局符号，对应C的非静态函数和全局变量
• 由其它模块定义、本模块引用的全局符号，也被称为外部符号，对应其它C文件的非静态函数和全局变量
• 只被当前模块定义和引用的局部符号，包括static修饰的函数和全局变量，只在模块内部可见

符号表存在于.symtab段，由Elf64_Symbol（显然，也会有32）数组组成

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

• name时字符串表中的字节偏移
• value是符号的地址，是距定义目标的setcion的起始位置的偏移
• size是目标的大小
• type区别数据和函数，binding标识符号是本地还是全局的

此外还有三个特殊的伪节，在段表中不存在

• ABS：不该被重定位的符号
• UNDEF：未定义的符号
• COMMON：未初始化的全局变量，bss是未初始化的静态、初始化为0的全局或静态

6 符号解析

把每个引用与目标文件符号表中的符号定义关联起来

局部符号：每个模块每个局部符号只能有一个定义，静态局部变量名字唯一

全局符号：遇到不在当前模块定义的符号时，假设其它模块定义该符号，生成一个链接器符号表条目，由链接器处理

6.1 多重定义的全局符号

全局符号分强弱，函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号

如下三条规则处理：

• 不允许有重名强符号
• 如果一个强符号和其它弱符号重名，选择强符号
• 如果多个弱符号重名，随机选择一个

显然，第二条和第三条规则将带来一些我们不想看到的错误，也正是由于这两条规则，才带来了bss和COMMON微小的区别，对于初始化为0或者静态变量，不会存在歧义，编译器会放在bss，对于没有初始化的全局变量，由链接器决定选择COMMON段的哪个。

6.2 静态库链接

编译系统提供一种机制：把相关的目标模块打包成一个文件，称为静态库，linux中后缀为.a的文件就是一系列目标模块的打包。

相关库函数被编译为独立的目标模块，以供链接时使用，当用户目标文件和静态库链接时，链接器复制需要的模块来链接，这避免了程序员手动链接所有目标文件的复杂性，也避免了一次链接所有文件导致的空间浪费。

举个例子，一个带printf调用的main.c，编译时gcc会自动给链接器加上libc.a的参数，ld会从libc.a中扫描到printf.o和其它printf.o引用的模块进行链接。

6.3 链接器如何使用静态库

链接器按顺序从左到右扫描目标文件和存档(archive, .a)文件，维护一个目标文件的结合E、一个未解析符号集合U、一个已定义符号集合D

• 对于输入文件f，判断f是目标文件还是存档文件，如果是目标文件，添加到E，根据f修改U和D
• 对于存档文件f，尝试匹配U中未解析符号，如果某个成员m定义了U中需要的符号，把m加到E中，修改U和D。
• 如果完成之后，U非空，输出错误，否则合并、重定位E中的文件。

注意，链接器按从左到右的顺序，意味着输入顺序很重要，库可以在命令行参数中重复，以满足依赖。

7 重定位

重定位以合并后的文件作为输入，为符号分配运行时地址

• 重定位节和符号定义：相同的节进行合并，作为输出文件的对应节。将运行时的内存地址赋给对应的节和符号
• 重定位符号引用：基于重定位条目修改所有的符号引用， 使得引用指向正确的运行时地址

7.1 重定位条目

汇编器生成目标文件，遇到不能确定最终地址的引用时，即生成一个重定位条目，代码的条目放在.rel.text，数据的放在.rel.data

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

上面这个数据结构就是重定位条目，每个条目表示一个需要重定位的引用。Elf有很多种重定位类型，我们只关心两种。

• offset：被修改的引用的段偏移
• symbol：被修改的引用指向的符号

• type：如何修改新的引用

  • R_X86_64_PC32：32位PC相对地址的引用，比如call指令，PC地址是下条指令的起始地址
  • R_X86_64_32：32位绝对地址的引用
  • 这两种类型支持“小型代码模型”，假设代码和数据的总体大小小于2G，因此可以使用32位相对地址访问。Gcc默认使用小代码模型。
• addend：一个常数，部分重定位需要使用它对被修改引用的值进行调整。

7.2 重定位符号引用

• 遍历需要重定位的节
• 对于所有当前节对应的重定位条目，根据节地址和条目offset取出需要重定位代码的地址

• 根据条目type，进入不同的分支

  • 若为相对引用，首先获取当前指令的运行时地址

    • 这里其实有点问题，取的到底是当前指令地址、当前指令的引用数据部分地址，还是下条指令的地址？
    • 根据代码的行为，我推测应该是当前指令的引用数据部分地址，再根据addend修正到下条指令的地址（事实上也是这样的）
  • 然后修改需要重定位的字节序列为符号地址+addend-当前指令运行时地址
  • 若为绝对引用，修改重定位的字节序列为符号地址+addend

8 可执行目标文件

对于可执行目标文件，其头部还包括了程序的入口点（Entry Point），记录了程序第一条指令的地址。

程序头部表：描述可执行文件映射到内存的关系，记录了段在目标文件中的偏移、内存地址、对齐、目标文件中的段大小、内存中的段大小和访问权限（rwx）。

9 可执行文件的加载

shell通过execve函数调用加载器，将ELF的代码和数据从磁盘复制到内存（实际上，应该只是简单建立映射，复制的工作似乎会由访问时的页错误完成，书中可能会在后面提到）然后跳转到程序的第一条指令或者入口点。

Linux程序都会有一个运行时内存镜像，其结构我们在第三章中应该介绍过了。

10. 动态链接库

静态库有一些缺点：

• 静态库更新时，程序员需要显式的重新链接
• 比如printf这种函数，会在上百个进程的text段中分别存放，造成极大的浪费

在内存加载时，共享库加载到内存的任意地址，并和内存中程序链接起来。Linux中为so（shared object），Win下为DLL（Dynamic Link Lib），Mac下为dylib

在给定的文件系统中，一个库只有一个so文件，所有引用该库的文件共享这个so的代码和数据（可读写的数据似乎应该是进程独立的，不知道这里书上这么说是指什么，可能是只代表只读数据）。

动态链接的过程会发生在加载时、加载器首先运行动态链接器、之后再由动态链接器把控制交还应用程序

11 应用程序中加载和链接共享库

Linux提供了一个接口，允许程序运行时加载链接库

#include <dlfcn.h>
void *dlopen(const char *filename, int flag);
void *dlsym(void* handle, char* symbol);
int dlclose(void *handle);

dlopen函数加载共享库filename，根据flag的标志决定何时进行符号解析。成功返回一个handle指针，出错为NULL

dlsym根据handle和符号名字返回符号地址

dlclose在共享库空闲时卸载该共享库。

12 位置无关代码（每次读这块都头疼）

PIC位置无关代码：可以加载而无需重定位的代码。

共享库需要通过这种方式来实现“加载到任意内存位置”，因为重定位时我们需要知道符号地址，而共享库是运行时才能确定地址的。

12.1 数据引用

全局偏移量表GOT：这个表在数据段开始的地方，每个被模块引用的全局数据目标都会在GOT表中有一个8字节条目，加载时动态链接器重定位GOT表中的每个条目，使得它包含目标正确的绝对地址。由于代码段和数据段之间距离不变，编译器产生的代码引用GOT中的条目对数据进行间接访问。

12.2 函数调用

延迟绑定：把过程地址绑定推迟到低依次调用过程时。

延迟绑定可以很好的避免加载时进行不必要的重定位，GNU通过GOT和过程链接表PLT实现这个机制。GOT时数据段的一部分，PLT时代码段的一部分。

• PLT：PLT的每个条目是16字节代码，PLT[0]跳转到动态链接器中。每个条目负责一个具体的函数

在这里，GOT除了前几个为动态链接器保留的条目外，每个条目对应一个函数，也对应一个PLT条目。GOT条目初始时指向对应的PLT条目的第二条指令。

PLT的一个条目是这样的：

4005a0: pushq *GOT[1]
4005a6: jmpq *GOT[2]
----
4005c0: jmpq *GOT[4]
4005c6: pushq $0x1
4005cb: jmpq 4005a0

GOT4对应这下面这条PLT（下面称为PLT2）。GOT0和GOT1包含动态链接器模块的地址，GOT2是动态链接器在ld-linux.so的入口点

当发生第一次调用时，程序进入PLT2，PLT2对应我们要调用的函数f

第一条PLT通过GOT4进行跳转，初始时GOT对应PLT的第二条指令，因此又跳到下面那条pushq指令上

把函数f的ID（1）压入栈之后，跳转到PLT0，PLT0通过GOT1间接的把动态链接器的参数压栈，通过GOT2跳转到动态链接器中，动态链接器利用这两个栈上参数确定f的运行时位置，把这个地址重写给GOT4，再把控制交还给f

在这之后，控制第二次传递到PLT2时，它会跳转到GOT4上保存的地址，而这个地址正是f的地址。

13 库打桩机制

我理解就是hook，可以截获调用，执行自己的代码，Hook可以发生在编译、链接和运行时。其实就是把调用函数替换成我们自己的实现嘛。这里不赘述了

14 处理目标文件的工具

• AR：创建静态库、插入删除列举提取成员
• strings：列出目标文件中可打印字符串
• strip：删除符号表信息
• nm：列出符号表中的符号
• size：列出节的名字和大小
• readelf：显示目标文件的完整结构
• objdump：显示目标文件所有信息，尤其是可以反汇编text中的指令。
• ldd：列出需要的共享库