第7章 链接

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

7.2 静态链接

链接器必须完成的两个任务：

1. 符号解析，将每个符号引用与符号定义关联。
2. 重定位，将符号定义和内存位置关联，再修改所有符号的引用，使其指向指定内存位置。

7.3 目标文件

三种形式：

1. 可重定位目标文件，包含二进制代码和数据的文件，可与其他可重定位文件合并，生成可执行目标文件。

2. 可执行目标文件，包含二进制代码和数据的文件，可直接复制至内存并执行。

3. 共享目标文件，特殊的可重定位目标文件，可在加载或运行时动态地加载至内存并链接。

编译器和汇编器生成可重定位目标文件，链接器生成可执行目标文件。

7.4 可重定位目标文件

典型的ELF可重定位目标文件的格式，如下：

图1 典型的ELF可重定位目标文件
ELF中各节功能及意义：

类型	功能及意义
ELF头	以16字节序列开始，描述生成该文件的系统的字的大小和字节顺序
.text	已编译程序的机器代码
.rodata	只读数据
.data	已初始化的全局和静态变量
.bas	未初始化的全局和静态变量
.symtab	存放程序中定义和引用的函数和全局变量的信息的符号表
.rel .text	.text节中位置列表，在组合目标文件和其他文件时，需修改这些位置
.rel .data	被模块引用或定义的所有全局变量的重定位信息
.debug	调试符号表，包含程序中定义的局部变量、定义和引用的全局变量以及原始的C源文件
.line	原始C源程序中的行号和.text节中机器指令之间的映射
.strtab	字符串表，包括.symtab和.debug节中的符号表，以及节头部中的节名字 节点部表

7.5 符号和符号表

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

1. 模块自身定义并能被其他模块引用的全局符号，如非静态的C函数的全局变量。
2. 引用其他模块定义的全局符号，即外部符号。
3. 模块定义和引用的局部符号，如带static属性的C函数和全局变量。

符号表由汇编器构造，.symtab节中包含ELF符号表，符号表包含一个条目的数据，每个条目的格式如下：

typedef struct {
    
	int name;			/*字符串表中的字节偏移*/
	char type : 4,		/*函数或数据 4字节*/
		binding : 4;	/*本地或全局 4字节*/
	char reserved;		/*未定义的符号*/
	short section;		/*节头部表的索引，指定分配到目标文件的某个节*/
	long value;			/*距定义目标的节的起始位置偏移*/
	long size;			/*目标的大小*/
} Elf64_Symbol;

7.6 符号解析

链接器解析符号是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。

解析多重定义的全局符号规则

1. 不允许有同名的强符号，函数和已初始化的全局变量为强符号，未初始化的全局变量为弱符号。
2. 若有一个强符号和多个弱符号同名，则选择强符号
3. 若多个弱符号同名，则随机选择一个

与静态库链接
将所有相关的目标模块打包成一个单独的文件，称为静态库。

相关的函数可以被编译为独立的目标模块，然后封装成一个单独的静态库文件。
链接时，链接器只复制被程序引用的目标模块，从而减少了可执行文件在磁盘和内存中的大小。

静态库使用示例：

1. main.c

#include <stdio.h>
#include "vector.h"
#include "windows.h"

int x[2] = {
     1, 2 };
int y[2] = {
     3, 4 };
int z[2];

int main() {
    
	addvec(x, y, z, 2);
	printf("z=[%d %d]\n", z[0], z[1]);
	system("pause");
	return 0;
}

2. vector.h

void addvec(int*, int*, int*, int);
void multivec(int*, int*, int*, int);

3. addvec.c

int addcnt = 0;

void multivec(int* x, int* y, int* z, int n) {
    
	int i;

	addcnt++;
	for (i = 0; i < n; i++)
		z[i] = x[i] + y[i];
}

4. multivec.c

int multicnt = 0;

void addvec(int* x, int* y, int* z, int n) {
    
	int i;

	multicnt++;
	for (i = 0; i < n; i++)
		z[i] = x[i] * y[i];
}

分别执行以下指令，则生成可执行目标文件file。

 gcc -c addvec.c multivec.c
 ar rcs libvector.a addvec.o multivec.o
 gcc -c main.c
 gcc -static -o file main.c libvector.a

链接器行为如下图所示：

图2 与静态库链接

链接器如何使用静态库来解析引用
符号解析阶段，链接器从左到右按照命令行上出现的次序来扫描可重定位目标文件和存档文件。
链接器维护一个可重定位目标文件集合 $E$，一个未解析符号集合$U$，一个在前面输入文件已经定义的符号集$D$。初始时，各集合全空。

• 若扫描到目标文件$f$，则链接器将$f$添加到$E$，修改$U$和$D$来反应$f$中的符号定义和引用。
• 若扫描到存档文件（静态库）$f$，则链接器尝试匹配$U$中未定义的符号和由存档文件定义的符号。若某存档成员$m$定义了$U$中的符号，则将$m$添加至$E$，并修改$U$和$D$。对存档成员目标文件，依次执行上述过程。
• 若扫描所有输入文件后，$U$是非空的，则抛出异常。否则，合并和重定位$E$中目标文件，生成可执行目标文件。

因此，命令行上库和目标文件的次序非常重要。因保证定义一个符号的库在引用这个符号的目标文件之后。
如foo.c调用libx.a中的函数，该库又调用liby.a中的函数，而liby.a有调用libx.a中的函数，则命令行格式为：

 gcc foo.c libx.a liby.a libx.a

即libx.a需重复出现，亦可将libx.a和liby.a合并。

7.7 重定位

重定位就是把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程。

完成符号解析后，代码中的每个符号和一个符号定义完成关联，此时链接器开始重定位。

• 重定位节和符号定义
  将所有相同类型的节合并为同一类型的新的聚合节。如所有输入模块的.data节被合并为新的.data节，并完成内存地址的赋值。
• 重定义节中的符号引用 修改代码节和数据节中对每个符号的引用，使其指向正确的内存地址。

重定位条目
汇编器生成目标模块时，对数据和代码在内存中的位置、模块引用的外部定义的函数或全局变量的位置均未知。对这些未知的引用都会生成一个重定位条目，用于指导链接器在合并阶段如何修改这个引用。

ELF重定位条目的格式：

typedef struct {
    
	long offset;		/*需要被修改的引用的节偏移*/
	long type : 32,		/*告知链接器如何修改新的引用*/
		symbol : 32;	/*符号表索引*/
	long addend;		/*有符号常数，对修改引用的偏移做调整*/
}Elf64_Rela;

两种基本的重定位类型：

1. $R\_X86\_64\_PC32$：重定位一个使用32位PC相对地址的引用。
2. $R\_X86\_64\_32$：重定位一个使用32位绝对地址的引用。

重定位符号引用
假设每个节s是一个字节数组，每个重定位条目r是一个类型为Elf64_Rela的结构。
重定位符号引用时，链接器已经为每个节（ADDR(s)）和每个符号(ADDR(r.symbol))都选择了运行时的地址。

伪重定位算法：

refptr = s + r.offset;
if (r.type == R_X86_64_PC32) {
    
	refaddr = ADDR(s) + r.offset;
	*refptr = (unsigned)(ADDR(r.symbol) + r.addend - refaddr);
}
if (r.type == R_X86_64_32)
	*refptr = (unsigned)(ADDR(r.symbol) + r.addend);

重定位如下实例程序的引用：

1. main.c

1	int sum(int* a, int n);
2
3	int array[2] = {
    1, 2};
4
5	int main() {
    
6	int val = sum(array, 2);
7	return val;
8	}

2. sum.c

1	int sum(int* a, int n) {
    
2		int i, s = 0;
3
4		for(i = 0; i < n; i++)
5			s += a[i];
6		}
7		return s;
8	}

main.o的反汇编代码：

// main.o
1  0000000000000000 <main>:
2    0:  48 83 ec 08              sub   $0x8, %rsp
3    4:  be 02 00 00 00           mov   $0x2, %esi	
4    9:  bf 00 00 00 00           mov   $0x0, %edi
5                           a: R_X86_64_32 array

6    e:  e8 00 00 00 00           callq 13 <main+0x13>
7                           f: R_X86_64_PC32 sum-0x4
8    13: 48 83 c4 08              add   $0x8, %rsp
9    17: c3                       retq

1. 重定位PC相对引用
   函数main调用sum函数，sum在sum.o中定义。
   已知main首地址
   $ADDR(s)=ADDR(.text)=0\times 4004d0$
   和 $sum$函数地址
   $ADDR(r.symbol)=ADDR(sum)=0\times 4004e8$。
   对于sum条目有：
   $r.offset=0xf,r.symbol=sum,r.type=R\_X86\_64\_PC32,r.addend=-4$。

链接器修改从偏移量0xf开始的32位PC相对引用，使程序指向sum入口地址。：
$$\begin{array}{l}refaddr=ADDR\left(s\right)+r.offset\\ =0\times 4004d0+0\times f\\ =0\times 4004df\end{array}$$
$$\begin{array}{l}\ast refaddr=\left(unsigned\right)\left(ADDR\left(r.symbol\right)+r.addend-refaddr\right)\\ =\left(unsigned\right)\left(0\times 4004e8+\left(-4\right)-0\times 4004df\right)\\ =\left(unsigned\right)\left(0\times 5\right)\end{array}$$

​

得到下面的重定位形式：

4004de:	e8 05 00 00 00		callq 4004e8 <sum>

运行时，call指令存放在$0\times 4004de$处，CPU执行call指令时，PC指向下一条指令即$0\times 4004e3$。由于相对地址偏移位$0\times 5$，读PC新值为$0\times 4004e3+0\times 5=0\times 4004e8$，刚好指向sum入口地址。

2.重定位绝对引用
对于array条目：
$$\begin{array}{c}r.offset=0\times a\\ r.symbol=array\\ r.type=R\_X86\_64\_32\\ r.addend=0\end{array}$$
已知$main$首地址$ADDR\left(s\right)=ADDR\left(.text\right)=0\times 4004d0$和$array$首地址$ADDR\left(r.symbol\right)=ADDR\left(array\right)=0\times 601018$

链接器修改从偏移量$0\times$开始的绝对引用，使程序指向$array$的第一个字节。

$$\begin{array}{l}refaddr=ADDR\left(s\right)+r.offset\\ =0\times 4004d0+0\times a\\ =0\times 4004da\end{array}$$
​$$\begin{array}{l}\ast refaddr=\left(unsigned\right)\left(ADDR\left(r.symbol\right)+r.addend\right)\\ =\left(unsigned\right)\left(0\times 601018+0\right)\\ =\left(unsigned\right)\left(0\times 601018\right)\end{array}$$

得到下面的重定位形式：

4004d9:	bf 18 10 60 00		mov $0x601018, %edi

已重定位的.text节，如下：

1   00000000004004d0 <main>:
2    4004d0:  48 83 ec 08                 sub    $0x8, %rsp
3    4004d4:  be 02 00 00 00              mov    $0x2, %esi
4    4004d9:  bf 18 10 60 00              mov    $0x601018, %edi
5    4004de:  e8 05 00 00 00              callq  4004e8 <sum>
6    4004e3:  48 83 c4 08                 add    $0x8, %rsp
7    4004e7:  c3                          retq

8  00000000004004e8 <sum>:
9    4004e8:  b8 00 00 00 00              mov    $0x0, %eax
10   4004ed:  ba 00 00 00 00              mov    $0xx, %edx
11   4004f2:  eb 09                       jmp    4004fd <sum+0x15>
12   4004f4:  48 63 ca                    movslq %edx, %rcx
13   4004f7:  03 04 8f                    add    (%rdi, %rcx, 4), %eax
14   4004fa:  83 c2 01                    add    $0x1, %edx
15   4004fd:  39 f2                       cmp    %esi, %edx
16   4004ff:  7c f3                       jl     4004f4 <sum+0xc>
17   400501:  f3 c3                       repz retq

已重定位的.data节，如下：

1  000000000601018 <array>:
2    601018:  01 00 00 00 02 00 00 00

7.8 可执行目标文件

典型的ELF可执行文件中的各类信息，如下：

图2 典型的ELF可执行目标文件
格式类似于可重定位目标文件格式。.init节中定义_init函数，代码初始化时调用。

可执行文件prog的程序头部表，如下：

Read-only code segment
1  Load off 0x0000000000000000  vaddr 0x0000000000400000    paddr 0x0000000000400000  align 2**21
2    filesz 0x000000000000069c  memsz   0x000000000000069c  flag r-x

Read/write data segment
3  Load off 0x0000000000000df8  vaddr 0x0000000000600df8    paddr 0x0000000000600df8  align 2**21
4    filesz 0x0000000000000228  memsz   0x0000000000000230  flag rw-

off：目标文件中的偏移； vaddr/paddr：内存地址； align：对齐要求； filesz：目标文件中的段大小；memsz：内存中的段大小； flags：运行时访问权限。

1. 1和2行（代码段），只读权限，开始于内存地址$0\times 400000$处，总共内存大小$0\times 69c$，被初始化为可执行目标文件的头$0\times 69c$个字节。

2. 3和4行（数据段），读写权限，开始于内存地址0x600df8处，总内存大小$0\times 230$字节，初始化为从目标文件中偏移$0\times df8$处开始的.data节中的$0\times 228$个字节初始化。

对于任何段s，起始地址满足：vaddr mod align = off mod align。优化对齐，便于目标文件中的段高效地传送至内存。

7.9 加载可执行目标文件

系统调用加载器将可执行目标文件的代码和数据从磁盘复制到内存，然后跳转至入口地址来运行程序，这一过程称为加载。

图3 Linux x86-64运行时内存映像
代码段总是从$0\times 400000$处开始，后面是数据段。堆在数据段之后，通过调用malloc向上增长。用户栈总是从最大的合法用户地址$2^{48}-1$处开始。

7.10 动态链接共享库

共享库，用于解决多个进程调用相同静态库造成的内存浪费问题。
共享库是一个目标模块，在运行或加载时，可以加载到任意的内存地址，并在内存中的程序链接起来（动态链接）。

共享库（so）中的代码和数据不会复制到引用它们的可执行文件中。
在内存中，共享库的.text节副本可被不同的正在运行的进程共享。

图4 动态链接共享库
使用动态链接共享库的命令行参数，如下。注：后缀.so和.dll均可。

 gcc -shared -fpic -o libvector.so addvec.c multivec.c
 gcc -o prog main.c libvector.so

7.11 从应用程序中加载和链接共享库

动态链接的功能：

1. 分法软件：利用共享库分发软件更新，可下载并替换当前版本。
2. 构建高性能服务器：基于动态链接以更有效和完善的方法生成动态内容。

7.12 位置无关代码

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

PIC数据引用
无论在内存中的何处加载一个目标模块，数据段和代码段的距离总是保持不变。
因此，代码段中的任何指令和数据段中任何变量之间的距离为常量。

基于上述原理，编译器在数据段开始处创建全局偏移量表（Global Offset Table, GOT），实现对全局变量PIC引用。

PIC函数调用
共享模块在运行时，随机加载到内存的任何位置，编译器无法预测其函数的运行地址。
GNU编译系统使用延迟绑定，将过程地址的绑定推迟到函数的第一次调用时。基于GOT和过程连接表（PLT）的交互实现。

7.13 库打桩机制

允许截获对共享库函数的调用，取而代之执行自己的代码。
打桩可发生在编译、链接以及程序加载和执行时。