链接

ELF文件

如何理解ELF文件，我们从jyy的“计算机就是一个状态机”的视角来进行思考：

• 计算机就是一个状态机
• ELF放在execve系统调用中被执行
• exec类的系统调用实际上就是对状态机进行“reset”，从而改变状态机的执行流
• 一个描述了状态机的初始状态+迁移数据结构
• ELF：Executable Linkable Format
• #!：一个偷换概念的execve，当shell发现以#!开头时，execve会讲第一个参数替换
• 什么样的程序算是ELF文件，是用exec执行其他类型文件时，会发生什么？

解析可执行文件

二进制文件工具集：

• 生成可执行文件
• 解析可执行文件

可执行文件类型

ELF文件主要有三种类型，可以通过ELF Header中的e_type成员进行区分。

• 可重定位文件（Relocatable File）：ETL_REL。一般为.o文件。可以被链接成可执行文件或共享目标文件。静态链接库属于可重定位文件。
• 可执行文件（Executable File）：ET_EXEC。可以直接执行的程序。
• 共享目标文件（Shared Object File）：ET_DYN。一般为.so文件。有两种情况可以使用。

可重定位目标文件

每个可重定位目标文件都可以大致分为三部分，分别是：

• ELF header
• 不同的section
• 描述这些section的表

链接

链接是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可被加载（复制）到内存并执行

链接是由叫做链接器的程序自动执行的

链接器使得分离编译成为可能

链接可以执行于编译时，也可以执行于运行时

编译器驱动程序

大多数编译系统提供编译驱动程序（compiler driver），它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。

大家都知道的过程：

.c → .s(ASCII汇编语言文件) → .o(可重定位目标文件relocatable object file) → 运行ld将文件以及一些必要的系统目标文件组合起来，创建一个可执行目标文件

shell调用操作系统中一个叫做加载器loader的函数，它将可执行文件的代码和数据复制到内存，然后将控制转移到这个程序的开头

静态链接

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

输入的可重定位目标文件由各种不同的代码和数据节（section）组成，每一节都是一个连续的字节序列。

指令在一节中，初始化的全局变量在另一节中，而未初始化的变量又在另外一节中。

为了构造可执行文件，链接器必须完成两个主要任务：

• 符号解析 symbol resolution：目的是将每个符号引用正好和一个符号定义关联起来
• 重定位 relocation：编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使他们指向这个内存位置

具体过程：

1. 在符号解析阶段，链接器从左到右按照命令行中出现的顺序来扫描可重定位文件和静态库文件，由于编译器驱动程序总是将libc.a传给链接器，所以命令中不必显示的引用libc.a
2. 在扫描的过程中，链接器一共维护了三个集合
3. 对于命令行中每一个文件，链接器都会判断这是一个目标文件还是一个静态库文件
4. 对于不在集合E中的成员目标文件都被简单的丢弃
5. 最后链接器还要扫描libc.a文件，再删除集合U中的符号
6. 最后，如果集合U是空的，那么链接器会合并集合E中的文件来生成可执行文件；如果链接器完成对命令行上所有输入文件的扫描后，集合U非空，那就说明程序中使用了未定义的符号，此时链接器输出一个错误并终止

不幸的是，这种算法会导致一些令人困扰的错误，在命令行中文件的顺序至关重要，同时，要留意两个静态库文件中函数相互引用的情况。

重定位

经过上边的过程，链接器就可以确定要将哪些文件进行合并了，同时，链接器也获得了这些目标文件的代码节和数据节的大小信息，接下来，开始进行重定位的操作。

在这个过程中，链接器合并输入模块，并为每个符号分配运行时地址，具体的重定位过程分为两步：

1. 重定位节和符号定义 Relocating sections and symbol definitions
2. 重定位节中的符号引用 Relocating symbol references within sections

首先我们需要明确的两个事实：

1）汇编器生成一个目标模块时从地址0开始生成代码和数据节 ，它并不知道数据和代码最终将放在内存的什么位置，也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。

2）链接器在重定位步骤中，合并输入模块并将运行时地址赋给输入模块定义的每个节、符号。当这一步完成时，程序中的每条指令和全局变量才拥有唯一的运行时内存地址。

现在我们引出一个关键问题。当一个模块引用一个外部定义的函数时，既然汇编器并不知道函数的最终内存位置，它要如何定位到这个函数？毕竟如下图所示，最终的函数调用是需要指出其具体地址的，接下来我们便针对这个例子展开叙述。

重定位相对引用

我们先粗略地了解汇编器解决上述问题的做法：

可重定位条目 Relocation Entries ：用来告诉链接器在合成可执行文件时应该如何修改这个引用

当汇编器遇到一个最终位置未知的引用时，它简单地将立即数0x0放入引用处，并为这个引用生成一个重定位条目放在 .rel .text 中(代码放在.rel.text，已经初始化的数据放在.rel.data中)，而这个重定位条目拥有足够多的信息指导链接器在链接时将0x0修改为正确的数值，剩下的事就都交给链接器处理了。

c
// Relocation Entries
typedef struct {
		long offset;    // 节偏移量
		long type:32,   // --> R_X86_64_PC32(pc相对寻址)；R_X86_64_32(绝对地址)
				 symbol:32; 
		long addend;   //偏移条目
} ELF64_Rela;

重定位条目有如下对应关系：

1）offset --> f，f指立即数0x0位置的偏移量，即要修改的引用位置离main的偏移量

2）type --> RX86_64_PC32，重定位条目一共有32种type，R_X86_64_PC32表明重定位的引用使用32位PC相对地址

3）symbol --> sum，表明调用的符号是sum，在本例中是个函数

4）addend --> -0x4，这个addend可能会带来疑惑，它代表引用位置与下一条指令的相对位置关系，在此例中就是引用的偏移量 0xf 减去下一指令的偏移量 0x13 得到 -0x4，在链接器进行具体计算时我们需要用到它

链接器如何进行最后的运算？

我们知道在链接时，链接器已经赋予了main和sum运行时地址，现在我们要利用它们结合重定位条目的信息计算并修改引用位置的0x0。

首先，链接器需要根据重定位条目计算出引用的运行时地址 ，具体的计算方法是通过函数main的起始地址与重定位条目中的偏移量字段相加，这样，我们就得到了引用的运行时地址

c
		r.offset = 0xf
		r.symbol = sum
		r.type = R_X86_64_PC32
		r.addend = -4

// 通过函数main的起始地址与重定位条目中的偏移量字段相加
ref_addr = ADDR(main) + r.offset
				 = 0x4004d0 + 0xf
				 = 0x4004df

然后更新这个符号引用，使它在运行时指向相关函数。用函数的起始地址减去刚才计算得到的运行时地址。运行时当前pc的值要加多少，才能使下一个正好是call的值

c
// 实际上这一步就是求两个指令之间的相对位置
*ref_ptr = ADDR(sum) - ref_addr + r.addent

Relocation algorithm：

c
 foreach section s {
	 foreach relocation entry r {
				// s指向main，s + offset是指向引用的指针
			 refptr = s + r.offset; /* ptr to reference to be relocated */
			 /* Relocate a PC-relative reference */
			 if (r.type == R_X86_64_PC32) {
				 refaddr = ADDR(s) + r.offset; /* ref’s run-time address */
				 *refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
			}                      // ADDR(r.symbol)是sum的运行时地址
			
		 /* Relocate an absolute reference */
		  if (r.type == R_X86_64_32)
				 *refptr = (unsigned) (ADDR(r.symbol) + r.addend);
										
		 }
 }

如上图和前文所示，refptr是指向引用的指针，refaddr是引用的运行时地址，ADDR(r.symbol)是sum的运行时地址，r.addend是引用和下一条指令的相对位置。注意，第二个if语句针对使用绝对地址的引用，不在我们这个例子的考虑范围内。

当CPU执行callq指令时，PC的值为0x4004e3，即callq的下一指令地址(在处理器中，callq进入执行阶段，下一指令进入取址阶段)，为了执行callq指令，CPU将执行以下步骤：

1）将PC压入栈中

2）更新 PC <-- PC + 0x5 = 0x4004e3 + 0x5 = 0x4004e8

显然0x5是我们的重定位算法最后放在引用处的值，它对应于 sum 的运行时地址 减去 callq 下一指令的运行时地址，即：ADDR(r.symbol) - (refaddr - r.addend)

重定位绝对引用

针对上边的例子：当执行完重定位操作后，指令操作数部分就是ADDR(array)，重定条目中offend字段值默认为0

可执行目标文件

其中有一项是程序的入口，也就是程序运行时要执行的第一条指令的地址，可执行文件的.init节定义了一个名为_init的函数，程序的初始化代码会调用这个函数进行初始化

.text、rodata、以及.data section与可重定位目标文件中的节是类似的，不过这些节以及被重定位到最终的运行时内存地址上，因此，执行目标文件中不再需要rel section

执行时，程序的代码段和数据段要被加载到内存执行，不过还有一部分内容不会被加载内存，例如符号表和调试信息等

• 程序头部表 Program Header Table
• 可执行文件是如何加载运行的

动态链接共享库

是一种特殊的可重定位目标文件，在linux系统中通常以.so的后缀来表示

创建过程

shell
linux> gcc -share -fpic -o libvector.so addvec.c mulvec.c

• -share 指示编译器创建一个共享的目标文件
• -fpic 告诉编译器生产位置无关的代码

链接过程：

• 首先将libc.so中的代码和数据重定位到某个内存段
• 然后重定位制定动态库中的代码和数据到另一个内存段
• 接下来重定位prog2中有libc.so和libvector.so定义的符号引用
• 上述重定位的操作完成后，动态链接器把控制权交给应用程序prog2，从这个时刻开始，共享库的位置就固定了，并且在程序的执行过程中都不会改变

MIPS相关

参考

• csapp_2016
• 九曲阑干-深入理解计算机系统
• 详解：链接中的重定位