链接有哪些过程？
假如有2个源文件如下，这两个源文件生成的目标文件链接成可执行文件后，涉及到空间和地址的分配、符号解析和重地位等等过程。
/* a.c */
extern int shared;
int main()
{
int a = 100;
swap( &a, &shared);
}
/* b.c */
int shared = 1;
void swap( int* a, int* b)
{
*a ^= *b ^= *a ^= *b;
}
在a.c中引用到了b.c中的变量”shared”和函数”swap”。使用gcc编译成目标文件a.o和b.o之后，接着就需要将两个目标文件链接成一个可执行文件。
gcc -c a.c b.c
一般来说，链接过程分为两步：
- 空间和地址分配。扫描所有的输入目标文件，获得它们的各个段的长度、属性和位置，并且将输入目标文件中的符号表中所有的符号定义和符号引用收集起来，统一放到一个全局符号表。这一步中，链接器将能够获得所有目标文件的段长度，并且将它们合并，计算出输出文件 中各个段合并后的长度与位置，并建立映射关系。
- 符号解析与重定位。使用上面第一步中收集到的所有信息，读取输入文件中段的数据、重定位信息，并且进行符号解析与重定位、调整代码中的地址等。事实上第二步是链接过程的核心。
在空间和地址的分配上比较实际的方法是将相同性质的段合并到一起，比如将所有输入文件的”.text”合并到输出文件的”.text”段，接着是”.data”段、”.bss”段等。在目标文件链接之前，目标文件中的所有段的VMA(Virtual Memory Address)都是0，因为虚拟空间还没有被分配，所以它们默认都为0。等到链接之后，可执行文件中的各个段都会被分配到了相应的虚拟地址。由于操作系统的进程虚拟地址空间的分配规则不同，因此并不是所有的虚拟地址都是从0地址开始分配的，在Linux下，ELF可执行文件默认从地址0×08048000开始分配的。在第一步的扫描和空间分配阶段，链接器按照前面介绍的空间分配方法进行分配，这时候输入文件中的各个段在链接后的虚拟地址就已经确定了。
a.o的段属性，”.text”、”.data”、”.bss”的VMA全为0：
a.o: file format elf32-i386
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00000034 00000000 00000000 00000034 2**2
CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
1 .data 00000000 00000000 00000000 00000068 2**2
CONTENTS, ALLOC, LOAD, DATA
2 .bss 00000000 00000000 00000000 00000068 2**2
ALLOC
b.o的段属性，”.text”、”.data”、”.bss”的VMA也全为0：
b.o: file format elf32-i386
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 0000003e 00000000 00000000 00000034 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .data 00000004 00000000 00000000 00000074 2**2
CONTENTS, ALLOC, LOAD, DATA
2 .bss 00000000 00000000 00000000 00000078 2**2
ALLOC
ab的段属性，将a.o和b.o链接后可以看到”.text”的虚拟地址是从0×08048094开始的，而”.data”的虚拟地址是从0×08049108开始的：
ab: file format elf32-i386
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00000072 08048094 08048094 00000094 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .data 00000004 08049108 08049108 00000108 2**2
CONTENTS, ALLOC, LOAD, DATA
链接器怎么知道哪些指令是要被调整的？
事实上在ELF文件中，有一个叫重定位表（Relocation Table）的结构专门用来保存这些与重定位相关的信息（编译的时候生成）。重定位表往往就是ELF文件中的一个段，比如代码段”.text”如有要被重定位的地方，那么会有一个相对应叫”.rel.text”的段保存了代码段的重定位表；如果数据段”.data”有要被重定位的地方，就会有一个相对应叫”.rel.data”的段保存了数据段的重定位表。
重定位表也是一个有固定元素结构的数组。数组中的元素保存了每个重定位项 的入口偏移(r_offset)、入口的类型和符号(r_info)。重定位的入口偏移(r_offset)是指该重定位入口所要修正的位置的第一个字节相对于段起始的偏移。至于r_info，这个成员的低8位表示重定位入口的类型，高24位表示重定位入口的符号在符号表中的下标。
其实重定位过程也伴随着符号的解析过程，每个目标文件都可能定义一些符号，也可能引用到定义在其他目标文件的符号。重定位的过程中，每个重定位的入口都是对一个符号的引用，那么当链接器须要对某个符号的引用进行重定位时，它就要确定这个符号的目标地址。这时候链接器就会去查找由所有输入目标文件的符号表组成的全局符号表，找到相应的符号表后进行重定位。
重定位的具体过程是怎样？针对哪些指令进行重定位？
对于32位x86平台下的ELF文件的重定位入口所修正的指令寻址方式只有两种：绝对近址32位寻址和相对近址32位寻址。每个被修正的位置的长度都为32位（修正的都是地址），即4个字节。重定位入口(r_info)的低8位指明了重定位入口的类型，1表示绝对寻址修正，2表示相对寻址修正。
首先需要明确的是，程序代码里面使用的是虚拟地址，在空间分配之前，所有的全局变量和函数地址都为0，等到空间分配之后，各个函数和变量才会确定自己在虚拟地址空间中的位置。对于近址相对位移调用指令（如call），后面4个字节就是被调用函数的相对于调用指令的下一条指令的偏移量。在没有重定位之前，相对偏移被置为0xFFFFFFFC（小端），它是常量”-4″的补码形式。
把a.o反汇编之后：
a.o: file format elf32-i386 Disassembly of section .text: 00000000 <main>: 0: 8d 4c 24 04 lea 0x4(%esp),%ecx 4: 83 e4 f0 and $0xfffffff0,%esp 7: ff 71 fc pushl -0x4(%ecx) a: 55 push %ebp b: 89 e5 mov %esp,%ebp d: 51 push %ecx e: 83 ec 24 sub $0x24,%esp 11: c7 45 f8 64 00 00 00 movl $0x64,-0x8(%ebp) 18: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp) 1f: 00 20: 8d 45 f8 lea -0x8(%ebp),%eax 23: 89 04 24 mov %eax,(%esp) 26: e8 fc ff ff ff call 27 <main+0x27> 2b: 83 c4 24 add $0x24,%esp 2e: 59 pop %ecx 2f: 5d pop %ebp 30: 8d 61 fc lea -0x4(%ecx),%esp 33: c3 ret
偏移为0×18的行中，”c7 44 24 04 00 00 00 00″，前4个字节为mov的指令码，后面4个字节为”shared”变量的地址，在空间和地址分配之前值为0。偏移为0×26的行中，”e8 fc ff ff ff”，”e8″为call的指令码，”fc ff ff ff”正是swap的地址，在空间和地址分配之前为0xFFFFFFFC（小端）。
重定位的类型：
- 绝对寻址修正（类型=1）：S+A
- 相对寻址修正（类型=2）：S+A-P
其中，A是保存被修正的值，即链接前该变量或者函数的值。S是符号的实际地址，即链接后的虚拟地址，由r_info的高24位指定的符号的实际地址。P是被修正的位置，即是相对于段开始的偏移量或者虚拟地址。
将链接后的ab反汇编之后，再根据上面的计算方式简单演示一下：
ab: file format elf32-i386 Disassembly of section .text: 08048094 <main>: 8048094: 8d 4c 24 04 lea 0x4(%esp),%ecx 8048098: 83 e4 f0 and $0xfffffff0,%esp 804809b: ff 71 fc pushl -0x4(%ecx) 804809e: 55 push %ebp 804809f: 89 e5 mov %esp,%ebp 80480a1: 51 push %ecx 80480a2: 83 ec 24 sub $0x24,%esp 80480a5: c7 45 f8 64 00 00 00 movl $0x64,-0x8(%ebp) 80480ac: c7 44 24 04 08 91 04 movl $0x8049108,0x4(%esp) 80480b3: 08 80480b4: 8d 45 f8 lea -0x8(%ebp),%eax 80480b7: 89 04 24 mov %eax,(%esp) 80480ba: e8 09 00 00 00 call 80480c8 <swap> 80480bf: 83 c4 24 add $0x24,%esp 80480c2: 59 pop %ecx 80480c3: 5d pop %ebp 80480c4: 8d 61 fc lea -0x4(%ecx),%esp 80480c7: c3 ret 080480c8 <swap>: 80480c8: 55 push %ebp 80480c9: 89 e5 mov %esp,%ebp 80480cb: 53 push %ebx 80480cc: 8b 45 08 mov 0x8(%ebp),%eax 80480cf: 8b 18 mov (%eax),%ebx 80480d1: 8b 45 0c mov 0xc(%ebp),%eax 80480d4: 8b 08 mov (%eax),%ecx 80480d6: 8b 45 08 mov 0x8(%ebp),%eax 80480d9: 8b 10 mov (%eax),%edx 80480db: 8b 45 0c mov 0xc(%ebp),%eax 80480de: 8b 00 mov (%eax),%eax 80480e0: 31 c2 xor %eax,%edx 80480e2: 8b 45 08 mov 0x8(%ebp),%eax 80480e5: 89 10 mov %edx,(%eax) 80480e7: 8b 45 08 mov 0x8(%ebp),%eax 80480ea: 8b 00 mov (%eax),%eax 80480ec: 89 ca mov %ecx,%edx 80480ee: 31 c2 xor %eax,%edx 80480f0: 8b 45 0c mov 0xc(%ebp),%eax 80480f3: 89 10 mov %edx,(%eax) 80480f5: 8b 45 0c mov 0xc(%ebp),%eax 80480f8: 8b 00 mov (%eax),%eax 80480fa: 89 da mov %ebx,%edx 80480fc: 31 c2 xor %eax,%edx 80480fe: 8b 45 08 mov 0x8(%ebp),%eax 8048101: 89 10 mov %edx,(%eax) 8048103: 5b pop %ebx 8048104: 5d pop %ebp 8048105: c3 ret Disassembly of section .data: 08049108 <shared>: 8049108: 01 00 add %eax,(%eax)
首先，从”.data”段可以看到shared的实际地址为”0×08049108″，值为1，而shared的修正方式是绝对地址修正，因此，对于原偏移为0x1c的这个重定位入口，它的修正后的结果应该是S（0×08049108）+A（0×00000000）= 0×08049108。看回到偏移为18行，已经变成”c7 44 24 04 08 91 04 08″，后面的4个字节正是”0×08049108″，结果匹配。
而对于原偏移0×27的swap(call swap)的修正则是采用相对寻址修正，它的修正结果应该是S（0x080480c8）+A（0xfffffffc）-P（0x80480bb）= 0×00000009，与偏移0×27的”09 00 00 00″匹配。其实相对寻址修正就是计算地址差，可以看到从反汇编的代码中看出，链接之后swap函数的地址为”0x080480c8″，而”call swap”的下一条指令的虚拟地址为”0x080480bf”，因此”0x080480bf” + “0×00000009″ = “0x080480c8″。