csapp chapter7:链接

链接(linking)是将各种代码和数据部分收集起来并组合成为一个单一文件的过程，这个文件可以被加载（或拷贝）到存储器并执行。链接可以执行于编译时（compile time）,也就是在源代码被翻译成为机器代码时；也可以执行于加载时（load time），也就是在程序被加载器（loader）加载到存储器并执行时；甚至执行于运行时(rum time),由应用程序来执行。

链接器使得分离编译(separate compilation)成为可能。本章将讨论从传统静态链接到加载时的共享库的动态链接，以及到运行时的共享库的动态链接。

编译器驱动程序

通过一个例子来说明一下：

# main.c
void swap();
int buf[2] = {1, 2};
int main()
{
    swap();
    return 0;
}

# swap.c
extern int buf[];
int *bufp0 = &uf[0];
int *bufp1;

void swap()
{
    int temp;
    bufp1 = &buf[1];
    temp = *bufp0;
    *bufp0 = *bufp1;
    *bufp1 = temp;
}

大多数系统提供编译驱动程序(compiler driver),它代表用户在需要时调用语言预处理器，编译器，汇编器和链接器。
运行gcc main.c swap.c -o p命令都发生了什么？

1. 预处理器先将main.c和swap.c翻译成一个ASCII码的中间文件main.i和swap.i
2. C编译器将main.i和swap.i翻译成ASCII汇编语言文件main.s和swap.s
3. 汇编器将main,s和swap.s翻译成可重定定位的目标文件main.o和swap.o
4. 连接器程序ld将main.o和swap.o以及一些必要的系统目标文件组合起来，创建可执行目标文件p

生产了可执行文件，可以通过过./p来运行，这是由外壳调用操作系统一个叫做加载器的函数,它拷贝可执行文件p中的代码和数据到存储器，然后将控制转移到这个程序的开头。

本章主要讲的是第4步的内容。

静态链接

将一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的可以加载和运行的可执行目标文件作为输出。完成这种功能的是静态连接器，为了构造可执行文件，连接器必须完成两个主要任务：

• 符号解析(symbol resolution):目标文件定义和引用符号。符号解析的目的是将每个符号引用刚好和一个符号定义联系起来。
• 重定位(relocation):编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个存储器位置联系起来，然后修改所有对这些符号的引用，使得它们指向这个存储器位置，从而重定为这些节。

目标文件

目标文件可以分为三种形式：

• 可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
• 可执行目标文件 包含二进制代码和数据，其形式可以被直接拷贝到存储器链接并执行。
• 共享目标文件：一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载到存储器这并连接。

可重定位目标文件

一个典型的可重定位目标文件(ELF)的格式如下：

• ELF头：包含生成该文件的系统的字的大小和字节顺序，以及帮助连接器分析和解释的目标文件的信息。
• .text: 已编译程序的机器代码
• .rodata: 只读数据，比如printf语句中的格式串和开关语句的跳转表
• .data: 已初始化的全局C变量。局部C变量在运行时保存在栈中。
• .bass: 未初始化的全局C变量。它仅仅是一个占位符，不占用磁盘空间。
• .symtab: 一个符号表。它存放在程序中定义和引用的函数和全局变量的信息。
• .rel.text: 一个.text节中位置的列表，当连接器把这个目标文件和其他文件结合时，需要修改这些位置。
• .rel.data: 被模块引用或定义的任何全局变量和重定位信息。
• .debug: 一个调试符号表。
• .line: 原始C源程序中的行号和.text节中机器指令之间的映射。
• .strtab:一个字符串表，其内容包括.symtab和.debug节中的符号表，及节头部中的节名字。
  其中，每个部分都称为节**

符号和符号表(.symtab)

链接器的上下文中有三种不同的符号：

• 由m定义并能被其他模块引用的全局符号。对应C语言中具有文件作用域并具有外部链接的变量
• 由其他模块定义并被模块m引用的全局符号。对应C语言中的变量与上面一样，并在本文件中用external声明
• 只被模块m定义和引用的本地符号。对应C语言中具有文件作用域但是具有内部链接的变量，如被static声明的全局变量。

符号表包含一个数组，每个元素的结构如下：

typedef struct {
    int name; //字符串表(strtab)中的字节偏移。
    int value; //符号地址，是距定义目标的节的起始位置的偏移。对可执行文件来说是一个绝对运行时地址。
    int size; //目标大小
    int type:4, //是变量或者函数
        binding:4; //表示是本地的还是全局的
    char reserved; //保留的
    char section; //表示符号和目标文件的某个节相关联,也就是这个符号在那个节中
} Elf_Symbol;

看一下main.o的符号表中最后三个条目:

Num(name):	Value	Size	Type	Bind	Ot	Ndx(section)	Name
8:	0(偏移为0)	8(8字节大小)	OBJECT(变量对象)	GLOBAL(全局的符号)	0	3(表示第三个节.data)	buf(符号名)
9:	0(偏移为0)	17(17字节大小)	FUNC(函数对象)	GLOBAL(全局的符号)	0	1(表示第一个节.text)	main(符号名)
10:	0	0	NOTYPE	GLOBAL	0	UND(表示外部符号引用)	swap(符号名)

这个地方有点晕，因为前面说第一个是自己偏移，下面这个变成了name, 最有一个是符号名Name,但是上面结构中并没有说有这个字段, 表格中和结构中的字段写法不一样，实在是太难理解～
总而言之，符号表就是对每个符号的信息描述，这个符号表什么时候用呢？符号解析的时候。

符号解析

链接器对多个可重定位目标文件进行解析的时候，读取每个文件的符号表，然后根据符号表的信息，与这个符号在代码中的确定的定义联系起来，目的是为了把所有的符号都合并在一起，形成一个完整的符号表，再加上其他信息，就变成了可执行文件。

这个过程在这里详细介绍一下，因为这里设计的链接器最核心的部分：如何变成可执行文件。

链接器如何解析多重定义的全局符号

把符号分为强和弱。对于函数和已初始化的全局变量是强符号， 对于未初始化的变量是弱符号。unix链接器使用下面的规则来处理多重定义的符号：

• 不允许有多个强符号
• 如果一个强符号和多个弱符号，那么选择强符号。
• 如果有多个弱符号，那么从这些弱符号中任意选择一个。

重定位

一旦链接器完成了符号解析这一步，它就把代码中的每个符号引用和确定的一个符号定义（即它的一个输入目标模块中的一个符号表条目）联系起来。链接器根据输入目标模块中的代码节和数据节的确切大小，就可以开始重定位了：

• 重定位节和符号定义：链接器将所有相同类型的节合并为同一类型的新的聚合节。然后链接器将运行时存储器地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号。当这一步完成时，程序中的每个指令和全局变量都有唯一的运行时存储器地址了。
• 重定位节中的符号引用。在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。为了执行这一步，链接器严重依赖称为重定位条目的可重定位目标模块中的数据结构。

重定位条目

由于汇编器生成目标模块时，并不知道数据和代码最终将存放在存储器中的什么位置，所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器将目标文件合成可执行文件时如何修改这个引用。
代码的重定位条目放在.rel.text中。已初始化的数据重定位条目放在.rel.data中。

typedef struct{
    int offset; //偏移位置
    in symbol:24, //指向引用的节
        type:8; //重定位类型
}Elf32_Rel;

重定位类型有11种，没种的实现方式不一样，这里只介绍两种最基本的：

• R_386_PC32: 使用一个32位PC（程序计数器）相对地址的引用。当CPU执行一条使用PC相对寻址的指令时，它就将在指令中编码的32位值加上PC的当前运行值，得到有效地址。
• R_386_32: 重定位一个使用32位绝地地址的引用。通过绝对寻址，CPU直接使用在指令种编码 的32位值作为有效地址，不需要进一步修改。

通过反汇编可执行文件，我们可看到重定位后的.text节的内容。

可执行目标文件

已经知道链接器将多个目标模块合并成一个可执行目标文件的。我们的C程序已经从ASCII码转化成了一个二进制文件，且这个二进制文件包含加载程序到存储器并运行它所需的所有信息。下图是一个典型的ELF可执行文件中的各类信息。

由于可执行文件是完全链接的(已被重定位)，所以它不再需要.rel节。我们发现还多了一个.init节，这个节定义了一个小函数，叫做_init,程序的初始化代码会调用它。