静态链接

想要理解静态链接这一过程，首先我们需要明白编译器驱动程序，它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。
示例程序：

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

当我们编辑完源代码需要运行时，大致过程如下图所示：

其中，标红的地方就是这篇文章要讲述的过程。
像Linux LD程序这样的静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。
为了构造可执行文件，链接器必须完成两个主要任务：符号解析和重定位。

符号解析

目标文件中，会定义与引用符号。
符号包括：函数、全局变量、静态变量（在C语言中任何以static属性声明的变量）
注意：局部变量不属于符号。
符号解析的目的是将每个符号引用正好和一个符号定义关联起来。

重定位

编译器和汇编器生成从地址0开始的代码和数据节。
链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节。
然后修改所有对这些符号的引用，使它们准确指向定义的内存位置。
（简单来说，就是对符号定义进行重新定位，再修改符号引用指向的地址）
链接器使用汇编器产生的重定位条目的详细指令，不加甄别地执行这样的重定位。

重定位类型

当汇编器遇到对最终位置未知的目标引用时，会生成一个重定位条目：其目的是告诉链接器在将目标文件合并成可执行文件时应该如何修改这个引用。

ELF重定位条目的格式如下（offset、type、symbol、addend）：

typedef struct{
	long offset; //需要被修改的引用的偏移量，也就是入口点偏移量
	long type:32, //声明重定位的类型（相对地址引用or绝对地址引用）
		 symbol:32; //标识被修改的符号，（例如sum函数，这里就是sum）
	long addend; //有符号常数，有时候需要用该值做重定位偏移调整
}Elf64_Rela;

其中最基本的两种类型（type）：

R_X86_64_PC32： 重定位一个使用32位PC相对地址的引用。将指令中编码的32位值加上PC的当前运行值作为有效地址。（PC值通常是下一条指令在内存中的地址）
R_X86_64_32： 重定位一个使用32位绝对地址的引用。CPU直接使用在指令中编码的32位值作为有效地址。

重定位符号引用

两种重定位算法如下：

foreach section s {
	foreach relocation entry r {
		refptr = s + r.offset; //s是每个节，r是相关联重定位条目

		//相对寻址
		if (r.type == R_X86_64_PC32) {
			refaddr = ADDR(s) + r.offset; 
			//计算引用的运行时的地址。如果写题，题目会给出ADDR（s）
			*refptr = (unsigned)(ADDR(r.symbol) + r.addend - refaddr); 
			//refaddr = ADDR(s) + r.offset
			//*refptr是指令中编码的32位值(重定位引用值）。
			//后续还需读出PC值。
			//有效地址为：下一条指令地址（PC值）+ *refptr
		}

		//绝对寻址
		if (r.type == R_X86_64_32){
			*refptr = (unsigned)(ADDR(r.symbol) + r.addend);
			//*refptr是指令中编码的32位值（重定位引用值），即有效地址。
		}
	}
}

接下来我们用以下示例图（反汇编代码）来演示相对寻址与绝对寻址。
已知：
ADDR(s) = 0x4004d0；
ADDR(sum) = 0x400e8；
ADDR(array) = 0x601018；

这里main函数引用了两个全局符号：array和sum。从图中我们可以得知：
array的type是R_X86_64_32（绝对寻址）
sum的type是R_X86_64_PC32（相对寻址）

重定位PC相对引用

第一步，我们需要列出上述示例中，sum的重定位条目：

从题目图中可以得知以下信息：

所以sum的重定位条目为：

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

且题目已告知：

ADDR(s) = 0x4004d0； ADDR(sum) = 0x400e8；

第二步，根据公式可做如下计算：

refaddr = ADDR(s) + r.offset
    = 0x4004d0 + 0xf
    = 0x4004df

*refptr = (unsigned)(ADDR(r.symbol) + r.addend - refaddr)
    = 0x4004e8 + (-0x4) - 0x4004df
    = 0x5

得到重定位引用值：0x5

重定位绝对引用

第一步，我们需要列出上述示例中，sum的重定位条目：

从题目图中可以得知以下信息：

所以array的重定位条目为：

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

且题目已告知：

ADDR(array) = 0x601018；

第二步，根据公式可做如下计算：

*refptr = (unsigned)(ADDR(r.symbol) + r.addend)
    = 0x601018 + 0
    = 0x4601018

得到重定位引用值：0x4601018（同时也是有效地址）

一、空间与地址分配

链接器在连接过程中的工作就是把多个输入的目标文件加工合并成一个输出文件。有几种不同的方案：

按序叠加
按序叠加可以说是最简单的一个方案，就是将输入的目标文件按照次序叠加起来。

 从图中可以看到，在有很多输入文件的情况下，输出文件将有很多零散的段。因为每个段都要遵循空间对齐，所以这样会占用大量空间。比如，一个段长度只有1字节，但是按照空间对齐，其在内存也要占用4096个字节。

相似段合并
为了解决按需叠加所带来的问题，引入了相似段合并这个概念，就是把相同性质的段合并到一起。.bss段其实在目标文件和可执行文件中并不占用文件的空间（不占用磁盘空间），但是在装载时是要占用地址空间的。

很多书中提到的“链接器为目标文件分配地址和空间”，这一句话其实是有两个含义的。对于.text和.data这样有实际数据的段，链接器在文件中和虚拟地址中都要分配空间。但是对于.bss这样的段，在文件中就不必分配空间，目的是节约磁盘空间。
目前的链接器都不采用按序叠加的方法，而是采用相似段合并的方法。

链接器采用的是相似段合并的方法，使用这种方法的链接器一般都采用两步链接的方法。
第一步 空间与地址分配：链接器获取所有目标文件的段长度，将他们合并，计算出输出文件中各个段合并后的长度与位置，建立映射关系。
第二步 符号解析与重定位：使用上一步所收集到的信息，读取输入文件中段的数据、重定位信息、进行符号解析和重定位、调解代码中的地址。
链接器前后的程序所用的地址其实已经是程序应该在进程中使用的虚拟地址。Linux下一般从0x08048000开始分配。地址确定很简单，基址地址(0x08048000)+偏移地址（符号在进程中的地址）。

二、符号

链接的本质就是把多个不同的目标文件之间相互“粘”到一起，就像是拼图一样，把每一块“目标文件”拼接成一个完整的“程序”。
在链接中，目标文件之间相互拼合实际上就是目标文件之间地址的引用，即对函数和变量的地址的引用。将函数和变量统称为符号，函数名或变量名就是符号名。

符号的类型
定义在本目标文件的全局符号：可被其他目标文件引用
外部符号：在本目标文件中引用的全局符号
段名：由编译器产生，值为该段的起始地址。
局部符号：只在编译单元内部可见，其他目标文件不可见

特殊符号
在linux下使用ld作为链接器来链接可执行文件时，定义很多符号可以引用。这些符号称为特殊符号。以下是几个很具有代表性的特殊符号：

__executable_strat：代码段的起始地址
__etext或_etext或etext：代码段的结束地址
_edata或edata：数据段的结束地址
_end或end：程序的结束
ELF符号表结构
typedef struct
{
    Elf32_Word st_name;
    Elf32_Addr st_value;
    Elf32_Word st_size;
    unsigned char st_info;
    unsigned char st_other;
    Elf32_Half st_shndx;
}Elf32_Sym

符号修饰与函数签名
为了避免和库文件中的符号发生符号冲突，就出现了符号修饰机制。

UNIX下的C语言规定，C语言中的符号经过编译后需要在在符号名前加上下划线“_“。

int func（）
    {
        ...
    }
以上函数名被修饰成 “_func”。

在C++中则增加了名称空间  namespace

C++中的符号修饰
因为C++支持重载的特征，所以函数符号修饰相对复杂，引入术语函数签名来表示C++中函数的符号修饰。函数签名包含了一个函数的信息，包括函数名、参数类型、所在类、以及名称空间。

linux下函数签名的规则：所有符号都以_Z开头，在名称空间或类中后面紧跟N，再以E结尾。比如一个名称空间foo中的全局变量bar就会被修饰为_ZN3foo3barE。

C++解决与C的兼容问题——extern
C和C++中的符号修饰是不同的，所以就存在不兼容问题，为了解决这个兼容问题，C++中有个用来声明或定义一个C符号的extern “C” 关键字用法。以下是一个示例：

extern “C”只能定义在全局范围，不能定义在函数内

extern "C"
{
    int func(int);
    int var;
}
同时C++编译器会在编译C++文件时默认定义一个宏**“__cplusplus”**，来使得能够兼容C语言的头文件，这也是能在C++中使用#include<stdio.h>的原因。

强符号和弱符号
在编程中会出现多个目标文件中含有相同名字全局符号的定义，这种情况就叫符号重复定义。为了解决这个问题，引入了强符号和弱符号规则。在C/C++语言中，编译器默认函数和初始化了的全局变量为强符号，未初始化的全局变量为弱符号。以下是发生符号重复定义的处理规则：

强符号与强符号之间：编译器报错
强符号与弱符号之间：编译器选择强符号
弱符号与弱符号之间：编译器选择其中占用空间最大的一个

强引用和弱引用
在编译器对引用的外部符号进行决议时，如果没有找到该符号定义，编译器就会报符号未定义错误的称之为强引用，如果没有找到该符号定义，编译器就默认其为0的称之为弱引用。

库中定义的弱符号可以被用户定义的强符号所覆盖，使得用户可以让程序使用自定义版本的库函数。

三、符号解析与重定位

重定位

#include "func.c"
int main()
{
    func();
}

在这段代码中的函数func()定义在其他文件中，所以编译器就暂时把地址0看做是“func（）”的地址。等到链接器在完成地址和空间分配之后就可以确定所有符号的虚拟地址(包括func)，那么链接器就可以根据重定位表对每个需要重定位的符号进行地址修正。

符号解析

链接是因为在目标文件中用到的符号被定义在其他目标文件。这也是编译过程中出现“undefined symbol”这类编译错误的原因。

重定位的过程往往也伴随着符号的解析过程，每个重定位的入口都是对一个符号的引用，那么当链接器需要对某个符号的引用进行重定位时，它就要确定这个符号的目标地址，这时候链接器就会去查找由所输入目标文件的符号表组成的全局符号表，找到相应的符号进行重定位。

12.1 符号的重定位

1. 重定位步骤

2. 重定位信息

3. 重定位操作举例

（1）源文件

（2）链接结果

（3）R_386_PC32的重定位

main.o重定位前

R_386_PC32的重定位方式

（4） R_386_32的重定位

重定位前

R_386_32的重定位方式

swap.o重定位

重定位后

12.2 可执行文件的加载

1. 加载方法

（1）通过调用execve系统调用函数来调用加载器
（2）加载器（loader）根据可执行文件的程序（段）头表中的信息，将可执行文件的代码和数据从磁盘“拷 贝”到存储器中
（3）加载后，将PC（EIP）设定指向 Entry point(即符号_start处)，最终执行main函数，以启动程序执行

ELF头信息举例

2. 程序的加载和运行

（1） UNIX/Linux系统中，可通过调用execve()函数来启动加载器。
（2） execve()函数的功能是在当前进程上下文中加载并运行一个新程序。 execve()函数的用法如下：
     int execve(char *filename, char *argv[], *envp[]);
   ①filename：加载并运行的可执行文件名(如./hello)
   ②argv：可带参数列表
   ③envp：环境变量列表
 若错误（如找不到指定文件filename） ，则返回-1，并将控制权交给调用程序；
 若函数执行成功，则不返回 ，最终将控制权传递到可执行目标中的主函数main。
（3） 主函数main()的原型形式如下：
     int main(int argc, char **argv, char **envp);
   或者: int main(int argc, char *argv[], char *envp[]);
 argc指定参数个数，参数列表中第一个总是命令名（可执行文件名）
 例如：命令行为“ld -o test main.o test.o” 时，argc=6

3. 程序的加载和运行过程举例

Step1： 在shell命令行提示符后输入命令：$./hello[enter]
Step2： shell命令行解释器构造argv和envp

Step3： 调用fork()函数，创建一个子进程，与父进程shell完全相同（ 只读/共享），包括只读代码段、可读写数据段、堆以及用户栈等。
Step4： 调用execve()函数,在当前进程（新创建的子进程）的上下文中加载并运行hello程序。将hello中的.text节、.data节、.bss节等内容加载到当前进程的虚拟地址空间（仅修改当前进程上下文中关于存储映像的一些数据结构，不从磁盘拷贝代码、数据等内容）
Step5：调用hello程序的main()函数，hello程序开始在一个进程的上下文中运行。int main(int argc, char *argv[], char *envp[]);

12.3 共享库和动态链接

1. 动态链接的共享库（Shared Libraries）

静态库有一些缺点：
 – 库函数（如printf）被包含在每个运行进程的代码段中，对于并发运行上百个进程的系统，造成极大的主存资源浪费
 – 库函数（如printf）被合并在可执行目标中，磁盘上存放着数千个可执行文件，造成磁盘空间的极大浪费
 – 程序员需关注是否有函数库的新版本出现，并须定期下载、重新编译和链接，更新困难、使用不便
解决方案: Shared Libraries （共享库）

（1）共享库

① 是一个目标文件，包含有代码和数据
② 从程序中分离出来，磁盘和内存中都只有一个备份
③ 可以动态地在装入时或运行时被加载并链接
④ Window称其为动态链接库（Dynamic Link Libraries，.dll文件）
⑤ Linux称其为动态共享对象（Dynamic Shared Objects,.so文件）

（2）共享库的动态链接与优点

动态链接可以按以下两种方式进行：
① 在第一次加载并运行时进行(load-time linking).
 – Linux通常由动态链接器(ld-linux.so)自动处理
 – 标准C库(libc.so) 通常按这种方式动态被链接
② 在已经开始运行后进行(run-time linking).
 – 在Linux中，通过调用dlopen()等接口来实现（用于分发软件包、构建高性能Web服务器等）

共享库的优点：
① 在内存中只有一个备份，被所有进程共享，节省内存空间
② 一个共享库目标文件被所有程序共享链接，节省磁盘空间
③ 共享库升级时，被自动加载到内存和程序动态链接，使用方便
④ 共享库可分模块、独立、用不同编程语言进行开发，效率高
⑤ 第三方开发的共享库可作为程序插件，使程序功能易于扩展

（3） 自定义一个动态共享库文件

自定义库函数

	//myproc1.c
	#include <stdio.h>
	void myfunc1() 
	{  
		printf("%s","This is myfunc1!\n"); 
	} 
	
	//myproc2.c
	#include <stdio.h>
	void myfunc2() 
	{  
		printf("%s","This is myfunc2\n"); 
	} 

生成库文件

$gcc -c myproc1.c myproc2.c  //预处理、编译、汇编
$gcc -shared -fPIC -o mylib.so myproc1.o myproc2.o //生成位置无关的共享代码库文件mylib.so

2. 动态链接

（1）加载时的动态链接

（2）运行时的动态链接

  可通过动态链接器接口提供的函数在运行时进行动态链接。类UNIX系统中的动 态链接器接口定义了相应的函数，如 dlopen, dlsym, dlerror, dlclose等， 其头文件为dlfcn.h。

	#include <stdio.h> 
	#include <dlfcn.h> 
	int main() 
	{ 
		void *handle; 
		void (*myfunc1)(); 
		char *error; 
		/* 动态装入包含函数myfunc1()的共享库文件*/ 
		handle = dlopen("./mylib.so", RTLD_LAZY); 
		if (!handle) { 
			fprintf(stderr, "%s\n", dlerror()); 
			exit(1);
		} 
		/* 获得一个指向函数myfunc1()的指针myfunc1*/ 
		myfunc1 = dlsym(handle, "myfunc1"); 
		if ((error = dlerror()) != NULL) { 
			fprintf(stderr, "%s\n", error); 
			exit(1);
		} 
		/* 现在可以像调用其他函数一样调用函数myfunc1() */ 
		myfunc1(); 
		/* 关闭（卸载）共享库文件*/ 
		if (dlclose(handle)< 0) { 
			fprintf(stderr, "%s\n", dlerror()); 
			exit(1);
		} 
		return 0;
	}

3. 位置无关代码（PIC）

动态链接用到一个重要概念：
 – 位置无关代码（Position-Independent Code，PIC )
 – GCC选项 -fPIC 指示生成PIC代码
共享库代码是一种PIC
 – 共享库代码的位置可以是不确定的
 – 即使共享库代码的长度发生变化，也不影响调用它的程序
引入PIC的目的
 – 链接器无需修改代码即可将共享库加载到任意地址运行
所有引用情况
 (1) 模块内的过程调用、跳转，采用PC相对偏移寻址
 (2) 模块内数据访问，如模块内的全局变量和静态变量
 (3) 模块外的过程调用、跳转
 (4) 模块外的数据访问，如外部变量的访问
要实现动态链接， 必须生成PIC代码 ;
要生成PIC代码，主要解决(3)(4)两个问题

① 模块内的过程调用、跳转

② 模块内数据访问

③ 模块外的数据访问

④ 模块外的过程调用、跳转