1. 问题来源

系统在执行代码的时候，遇到对应的函数，是如何跳转到对应函数体内运行的？函数是怎么保存在可执行文件当中的。

2. 链接器

生成可执行文件的过程可分为预处理、编译、汇编、链接。链接就是将不同的源文件组合在一起，形成一个单一可执行文件的过程，其中涉及到函数调用、全局变量。链接是由一个叫做链接器的程序自动执行的。

考虑这样一个C程序，包含两个源文件。main函数调用swap函数，它交换全局数组buf中的两个元素。

//main.c
void swap();

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

int main(){
	swap();
	return 0;
}

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

void swap() {
	int temp;
	bufp1 = &buf[1];
	temp = *bufp0;
	*bufp0 = *bufp1;
	*bufp1 = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

通过gcc编译器，c文件经过预处理、编译、汇编生成o文件（可重定位目标文件），最后再链接器的帮助下生成可执行目标文件。

gcc -c main.c
1

通过上述命令，-c代表编译、汇编指定的源文件，但不进行链接，可以生成main.o文件，也就是可重定向目标文件。

3. 可重定位目标文件

Linux系统下，o文件、可执行文件都属于ELF类型文件。下图展示了一个典型的ELF可重定位目标文件。

每一行代表一节，存储不同的信息。

• ELF头：目标文件的类型（可重定位文件、可执行文件、共享的）、机器类型等
• text:程序的机器代码；
• rodata:只读数据，比如printf语句中的格式串和switch语句的跳转表；
• data:已初始化的全局C变量；
• bss:未初始化的全局C变量，在文件当中，该段仅仅只是占位符，并没有实际的变量。因为未初始化的变量是不需要记录它的值，只需要记住它们的大小就行。
• symtab:一个符号表，它存放着程序中被定义和引用的函数和全局变量的信息；（很重要！！）

readlf -h main.o 
1

上述命令可以查看o文件的文件头详细信息。

• Type：REL，Relocatable file，即可重入文件类型。
• Size of this header：该头部的字节大小为64字节。
  还有其他各类信息。

4.符号和符号表

每个可重定位文件m，包含main.o和swap.o都有一个符号表symtab，包含三种符号：

• 由m定义并能被其他文件引用的全局符号。翻译一下，就是全局变量和不带static的函数。
• 由其他文件定义并被文件m引用的全局符号。也就是调用其他文件的函数，比如main.o中的swap函数就是其他文件定义的。
• 只被文件m定义和引用的本地符号。对应的就是带static关键字的函数和全局变量，并不能被其他文件引用。

symtab不包含任何函数内部的局部变量，这些变量在运行时由栈进行管理，链接器对此类符号不感兴趣。如果是带static的局部变量，是不在栈中管理的，编译器在data或bss中为每个变量分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。

符号表是由汇编器构造的，就是s文件中的一部分。符号表实际上就是一个数组，数组里的每一个元素叫表目，是一个结构体，里面存储着符号的具体信息。

readlf -s main.o 
1

上述命令可以查看o文件的符号表详细信息。

我们重点关注后面三个，buf是一个全局变量，main是一个全局函数，swap是一个声明的函数，但这个函数并不在main.c，甚至我还没用编写swap.c文件。

有三个特殊的伪节，他们在节表头中是没有表目的，也就是没他们的位置：ABS代表不该被重定位的符号，UND代表未定义的符号（在本文件引用，但却在其他地方定义的变量、函数）、COM代表还未被分配位置的未初始化的数据目标。

• Type：类型，FUNC代表函数，OBJECT代表变量，NOTYPE代表未知，因为没有链接之前，main.o文件是不知道swap.o的信息的。
• Ndx：代表该符号位于哪个节（段），Ndx=1代表text节，Ndx=3代表data节。main是函数，所以是放在文本段的。buf是已初始化的全局变量，所以放在data段。swap不是main.c的函数，所以是UND。
• Size：大小。buf是含有两个int的数组，一共8字节。main函数含有21字节。
• value：代表在所处节的起始位置的偏移。这里的函数和变量只有一个，所以都是在最前面的地方，偏移为0,，待会多定义几个变量看看变化。
  
  
  
  data节有两个变量，一个是buf数组，一个是a变量，它们都存储于data节，从value可以看出它们相对节开始位置的偏移，0代表无偏移，8代表偏移了8个字节，这8字节其实就是前面的buf占据的空间。

d是一个静态局部变量，Bind=LOCAL代表局部的，它存储在bss字节偏移量为0的地方（最开始），大小为4字节。后面加2294是为了区分开，同一个文件不同函数内部同名的static局部变量，让他们用于唯一的名字，类似于路人甲、路人乙。像全局变量就没这担忧，因为编译的时候就会报错。

而b是一个未初始化的静态变量，实际值并不需要保存，也不存在于bss之中，所以Ndx=COM。但会记录它的偏移和大小。value=4，是因为前面存放了一个静态局部变量d。

接下来看看swap.o的符号表。

bufp0是data节的已初始化的全局变量，buf的UND代表是引用外部的符号，bufp1的COM代表未初始化的全局变量，swap函数是text节的内容。temp是局部变量，不会出现在符号表。

到这里，基本就弄清了函数、变量是怎么被记录在符号表的，所以后面链接的工作其实就是把UND类型的变量、函数与其他文件的链接起来。

5. 符号解析

因为每个文件的本地符号只有一个定义，所以完成本地符号的解析是很简单的。但是对于全局符号就比较麻烦。当编译器遇到一个不是在本文件中定义的，就会生成一个符号表表目（上面描述的），并把这个锅甩给了后面的链接器。链接器的输入是多个o文件，如果它在其他的o文件均找不到这个被引用的符号，它就会输出一条错误信息并终止。

在C++中允许重载函数，这些函数在源文件中都有相同的名字，却有不同的参数列表。编译器就会像处理静态局部变量一样，用函数名称+参数列表类型组合生成一个唯一的名字，这样就可以区分调用到底是哪个重载函数。

链接器如何处理多处定义的全局符号? a文件定义了全局变量vec，b文件也定义了全局变量vec，在前面三部曲，预处理、汇编、编译都发现不了这个问题，因为它们互相都不知道对方的底细，只有链接器能看到全部人的底细。

链接器把符号分为强符号、弱符号，并规定了几条规则：

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

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

//a.c
void main(){}

//b.c
void main(){}
1
2
3
4
5

如上所示，两个不同的文件都定义了main函数，这是个强符号，就会因为违反规则1而报错。

//a.c
void f(void);
int x = 1;

void main(){
	f();
	printf("x = %d", x);
}

//b.c
int x;
void f(){
	x = 2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

两个文件都定义了x，但是a文件的x是已定义的，属于强符号，b文件的x是未定义的，属于弱符号。所以根据规则2，f函数内部的x指的就是a文件的那个x。最后输出x=2.

6. 重定位

一旦链接器完成了符号解析这一步，它就把代码中的每一个符号引用和确定的一个符号定义（就是某个文件中的符号表中的一个表目）联系起来。同时，链接器也知道输入的o文件text节、data节的位置和大小。

重定位这一步主要就是合并输入的o文件，并未每个符号（包括函数和变量）分配运行时的地址。重定位由两步组成：

• 聚合同类型的节。在这一步，链接器将所有相同类型的节合并为同一类型的新的聚合节。比如各个文件的data节存储的是各自文件的已初始化全局变量，全部合并成一个节，称为可执行目标文件的data节。
• 重定位节中的符号引用。在这一步，链接器修改代码节和数据节中对每个符号的引用，使得他们指向正确的运行时地址。比如main.o中swap符号就是未定义的，需要找到它正确的位置。为了执行这一步，链接器需要依靠一个数据结构，叫重定位表目。

当汇编器生成o文件（可重定位目标文件）时，它不知道这个文件不用的任何外部定义的函数或全局变量的位置，比如main文件就不知道swap函数在哪里。当汇编器遇到这种情况，就会生成一个重定位表目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码的重定位表目放在.relo.text中，已初始化数据的重定位表目放在.relo.data中，就在符号表.symtab的后面两个节。

重定位表目的数据结构如下所示：
offset是需要被修改的引用的节偏移。symbol表示需要重定位的符号。type告知链接器如何修改新的引用，重定位类型。

ELF定义了11中不同的重定位类型，需要了解最基本的两种。看不懂没关系，后面有具体的例子。

• R_386_PC32:重定位一个使用32位PC相关的地址引用。当CPU执行使用PC相关寻址的指令时，它就将再指针中编码的21位值加上PC当前运行时值。
• R_386_32:重定位一个使用32位绝对地址的引用。通过绝对寻址，CPU直接使用在指针中编码的32位值作为有效地址。

R_386_PC32执行的是相对引用，就好像在一个赛道跑步，在当前位置的基础上再往前跑100米；而R_386_32是绝对地址，也就是你跑去跑道100米的位置。

//main.c
void swap();

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

int main(){
	swap();
	return 0;
}
1
2
3
4
5
6
7
8
9

通过objdump -d main.o查看text节的反汇编代码。

从上面可以看到，callq指令(q后缀可以省略)开始于text节偏移0x09处，由1个字节的操作码0xe8（代表call）和随后的32位引用0x00000000（十进制0）组成。call指令就是调用swap函数的汇编指令。

所以重定位表目r就生成为，r.offset = 0xe ， r.symbol = swap， r.type = R_386_PC32。
这些数据告诉链接器修改开始于偏移量0xe处的32位PC相关引用，使得它在运行时指向swap函数。目前偏移量0xe这个位置并不是swap函数。因为还没开始链接。

通过gcc main.c swap.c -o main生成可执行文件main，通过objdump -d main查看可执行文件的汇编代码。

下面看看如何计算操作码0xe8后面的32位相对引用0x07。当CPU正在执行callq指令的时候，PC寄存器存储的是下一条指令的值，也就是0x4004e4，不是0x4004df。而ADDR(swap) = 0x4004eb，就可以计算出swap函数距离PC寄存器当前运行值的偏移量为0x4004eb - 0x4004e4 = 0x07 （小端字节顺序存储）。为了执行后续的swap函数，CPU执行了两个步骤：

1. 保存现场，当当前运行值0x4004eb存入栈，方便待会返回。
2. PC = PC + 0x07 = 0x4004eb

这样整个程序就跳进了swap函数的第一行，完成了函数的跳转。