程序编译和链接详解

引言

一直想探究下二进制程序在Linux系统上是如何加载执行的。本文先研究下程序是如何编译和链接的。

本文所用的gcc版本是5.4, Linux环境是VMware+Ubuntu16。

程序编译

以如下代码为例。

//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;
}

编译分4步：

预处理： gcc -E main.c -o main.i
编译：gcc -S main.i //生成汇编代码，生成的文件为main.s
汇编：gcc -c main.s //生成一个可重定位目标文件，包括将汇编代码编译成机器码
链接：gcc -o prog main.o sum.o //生成可执行目标文件

静态链接

像Linux ld程序这样的静态链接器，以一组可重定位目标文件为输入，以一个完全链接的、可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的代码和数据节组成，每一节都是一个连续的字节序列。

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

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

链接器对目标机器知之甚少，产生目标文件的编译器和汇编器已经完成了大部分工作。

目标文件

目标文件有三种形式：

可重定位目标文件：包含代码和数据，可与其它可重定位目标文件合并起来，创建一个可执行目标文件
可执行目标文件：包含代码和数据，可以被直接复制到内存并执行
共享目标文件：一种特殊的可重定位目标文件，可以被动态的加载进内存并链接

编译器和汇编器生成可重定位目标文件（包括共享目标文件），链接器生成可执行目标文件。

ELF格式

ELF文件格式主要分为三部分，按顺序为：

ELF header
各个section
section header table

典型的节(section)有：

.text: 代码段
.rodata: 只读数据，比如字符串
.data: 已初始化全局变量
.bss: 未初始化全局变量
.symtab: 不加-g选项也有，存放函数和全局变量信息

符号和符号表

每个可重定位目标文件都有一个符号表，它包含这个模块定义和引用的符号信息。在链接器的上下文中有三种不同的符号：

由本模块定义并被其它模块引用的全局符号。对应于非static的函数和非static的全局变量。
由其它模块定义被本模块引用的全局符号。
只被本模块定义和引用的局部符号，对应于带static属性的C函数和带static属性的全局变量。

.symtab节包含符号表，这张符号表包含所有符号的条目，每个条目的结构如下：

typedef struct {
	int name;		//符号名称
	char type: 4,	//类型：函数或数据
		 binding: 4;//本地or全局
	char reserved;
	short section;	//属于那个节
	long value;		//距离节起始位置的偏移；对于可执行文件则是绝对运行时地址
	long size;		//目标大小
} Elf64_Symbol;

符号解析

符号解析即是链接器将一个引用与定义这个引用的目标文件的符号表中的一个符号对应起来。

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

链接器的输入是一组可重定位的目标模块。每个模块定义一组符号，有些是局部的，有些是全局的。如果多个模块定义同名的全局符号，会发生什么呢？

下面是Linux编译系统采用的方法：在编译时，编译器向汇编器输出每个全局符号，或者是强，或者是弱。汇编器将这个强弱信息编码在符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

Linux链接器用下面的规则来处理多重定义的符号：

规则1：不允许有多个同名的强符号
规则2：如果同名的有一个强符号和多个若符号，选择强符号
规则3：如果有多个弱符号同名，那么从这些若符号中任意选择一个

与静态库链接

编译系统还有一个机制，将所有相关的目标模块打包成一个单独的文件，称为静态库，它可以用做链接器的输入。

当链接器链接生成可执行文件时，它只复制静态库里被应用程序引用的模块。也就是说，将多个模块打包成一个静态库文件，链接时链接器只复制被引用的模块。

在Linux系统中，静态库以一种称为存档的特殊文件格式存放在磁盘中。存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置。

链接器如何使用静态库来解析引用

在符号解析阶段，链接器按照输入顺序依次扫描输入的可重定位目标文件和存档文件。

扫描过程中，链接器维护一个可重定位目标文件集合E，一个未解析的符号集合U，以及已定义符合集合D。初始时，E、U和D均为空。

如果被扫描的文件是可重定位目标文件，则将其加入E，同时修改U和D
如果被扫描的文件是存档文件，链接器尝试匹配U和存档文件，如果某个存档文件成员和U匹配，则将这个文档成员加入到E中，并修改U和D，直到U不再变化。
如果连接器完成对所有文件的扫描后，U是非空的，那么链接器就会输出一个错误并终止。否则合并E中的文件，输出可执行文件

不幸的的是，这种算法使得输入文件的顺序很重要。如果库在前，目标文件在后，目标文件中引用的符号可能不被解析。

重定位

重定位要完成的工作：合并输入模块，为每个符号分配运行时地址。

重定位由两步组成：

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

重定位条目

当汇编器生成一个模块时，它并不知道数据和代码最终将放在内存中的什么位置，也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。即本模块和其它模块定义的函数最终在内存中的位置都是未知的。

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

typedef struct {
	long offset;		//这个要修改的条目的位置，相对节起始位置的偏移
	long type: 32,		//
		 symbol: 32;	//引用的符号名称，对应符号表中的index
	long addend;		//常数
} Elf64_Rela

type有两种最基本的类型：

R_X86_64_PC32: 重定位一个相对地址的引用。即相对于当前地址的偏移量。
R_X86_64_32：重定位一个绝对地址引用。

重定位符号引用

下面是重定位符号的伪代码：

foreach section s { //遍历每个节
	foreach relocation entry r { //遍历每个节的每个重定位条目
		refptr = s + r.offset;  //计算引用所在的地址，即节的起始地址加上偏移
		//重定位一个相对地址的引用
		if (r.type == R_X86_64_PC32) {
			refaddr = ADDR(s) + r.offset;  //引用所在的运行时地址，即节的运行时地址加上偏移
			*refptr = ADDR(r.symbol) + r.addend - refaddr;  //引用的最终地址 - 引用所在地址，差值填到引用所在地址
		}
		//重定位一个绝对引用
		if (r.type == R_X86_64_32) {
			*refptr = ADDR(r.symbol) + r.addend
		}
	}
}

接下来举一个详细的例子：以main.c为例，通过objdump -dx main.o产生main.o的反汇编：

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 10          	sub    $0x10,%rsp
   8:	be 02 00 00 00       	mov    $0x2,%esi
   d:	bf 00 00 00 00       	mov    $0x0,%edi
			e: R_X86_64_32	array
  12:	e8 00 00 00 00       	callq  17 <main+0x17>
			13: R_X86_64_PC32	sum-0x4
  17:	89 45 fc             	mov    %eax,-0x4(%rbp)
  1a:	8b 45 fc             	mov    -0x4(%rbp),%eax
  1d:	c9                   	leaveq 
  1e:	c3                   	retq

可以看到main函数引用了两个全局符号，array和sum，也就是说main.o有两个重定位条目。这两个条目的信息是：

e: R_X86_64_32	array		//此引用位置相对于.text节的offset是e，类型是绝对地址，符号名是array
13: R_X86_64_PC32	sum-0x4	//此引用位置相对于.text节的offset是13，类型是相对地址，符号名是sum，常数是4

下面来看如何重定位这些引用：

1 重定位PC相对引用：

再还原下sum这个引用的重定位条目信息：

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

假设链接器已确定ADDR(.text)=0x4004d6和ADDR(sum)=0x4004f5 根据上面讲的伪代码：

refaddr = ADDR(s) + r.offset 
		= 0x4004d6 + 0x13
		= 0x4004e9
*refptr = ADDR(r.symbol) + r.addend - refaddr
		= 0x4004f5 - 4 - 0x4004e9
		= 0x8

即这里的call指令由e8 00 00 00 00，改为e8 08 00 00 00。 e8这条指令的位置是0x4004e8，当执行到这条指令时，PC指向下一条指令，这时PC的值为0x4004ed；接下来将PC压入栈中；然后PC = PC + 0x8 = 0x4004ed + 0x8 = 0x4004f5，即sum符号的地址。

2 重定位绝对引用

还原下array这个引用的重定位条目信息：

r.offset = e
r.symbol = array
r.type = R_X86_64_32
r.addend = 0

假设链接器已确定ADDR(array) = 0x601030，那么

*refptr = ADDR(r.symbol) + r.addend = 0x601030

于是这里的指令bf 00 00 00 00再连接时会被修改为bf 30 10 60 00。

加载可执行目标文件

shell中输入./prog来执行目标文件prog，shell会调用加载器来运行它。加载器将ELF文件的代码和数据从磁盘复制到内存中，然后跳转到该程序的入口点。

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

动态连接共享库(.so)

静态库有两个明显的缺点：

如果静态库更新了，则需要显示的重新链接生成目标程序
静态库里的代码会被复制到最终的目标程序，这对内存是很大的浪费

共享库是一个创新产物，共享库可以加载到任意内存地址，并和一个内存中的程序链接起来。这个过程叫动态链接。

创建共享库的命令：

gcc -shared -fpic -o libvector.so addvec.c multvec.c

这里-fpic是必须的，表示生成与位置无关的代码。

位置无关代码

可以加载而无需重定位的代码称为位置无关代码，Position Independent Code, PIC。

在一个x86-64系统中，对同一个目标程序(模块)中的符号引用自然是PIC的，因为可以用相对寻址来编译这些引用。然而对so中定义的符号的引用，需要一些特殊的技巧。

1 PIC数据引用

无论我们在内存中的何处加载一个共享目标模块，数据段与代码段的距离总是保持不变的。因此，代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量。要想生成对全局变量PIC引用的编译器利用了这个事实，它在数据段开始的地方创建了一个表，叫做全局偏移量表(GOT)。在GOT中，每个全局数据引用对应一个8字节条目，编译器为每个条目生成一个重定位记录。加载时，动态链接器会重定位GOT中的每个条目。

2 PIC函数调用

假设程序调用一个共享库定义的函数，编译器没办法在编译时知道这个函数的运行时地址。正常的方法是为该引用生成一个重定位记录，然后动态链接器在程序加载的时候再解析它。不过这种方法不是PIC，因为它需要链接器修改调用模块的代码段。

GNU编译系统使用一种称为延迟绑定的技术来解决这个问题，将函数地址的绑定推迟到第一次调用该函数时。延迟绑定，在第一次调用共享库中的函数时，运行时开销很大，但是其后的每次调用都只会花费一条指令和一个间接的内存引用。

延迟绑定是通过两个数据结构之间的交互来实现的，这个两个数据结构是GOT(Global Offset Table)和PLT(Procedure Linkage Table)。如果一个目标模块调用了共享库中的任何函数，那么它就有自己的GOT和PLT。 GOT是数据段的一部分，PLT是代码段的一部分。

具体的PLT和GOT如何协作这里不再展开，总之PIC的思路是，代码上访问的符号是表的地址，动态链接器会在表中填入符号真正的地址。