4.2 符号解析与重定位
4.2.1 重定位
在完成空间和地址的分配步骤以后，链接器就进入了符号解析与重定位的步骤，这也是静态链接的核心内容。在分析符号解析和重定位之前，首先让我们来看看"a.o"里面是怎么使用这两个外部符号的，也就是说我们在"a.c"的源程序里面使用了"shared"变量和"swap"函数，那么编译器在将"a.c"编译成指令时，它如何访问"shared"变量？如何调用"swap"函数？
使用objdump的"-d"参数可以看到"a.o"的代码段反汇编结果：
$objdump -d 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 0xfffffffc(%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,0xfffffff8(%ebp)
18: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp)
1f: 00
20: 8d 45 f8 lea 0xfffffff8(%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 0xfffffffc(%ecx),%esp
33: c3 ret
我们知道在程序的代码里面使用的都是虚拟地址，在这里也可以看到"main"的起始地址为0x00000000，这是因为在未进行前面提到过的空间分配之前，目标文件代码段中的起始地址以0x00000000开始，等到空间分配完成以后，各个函数才会确定自己在虚拟地址空间中的位置。
我们可以很清楚地看到"a.o"的反汇编结果中，"a.o"共定义了一个函数main。这个函数占用0x33个字节，共17条指令；最左边那列是每条指令的偏移量，每一行代表一条指令（有些指令的长度很长，如第偏移为0x18的mov指令，它的二进制显示占据了两行）。我们已经用粗体标出了两个引用"shared"和"swap"的位置，对于"shared"的引用是一条"mov"指令，这条指令总共8个字节，它的作用是将"shared"的地址赋值到ESP寄存器+4的偏移地址中去，前面4个字节是指令码，后面4个字节是"shared"的地址，我们只关心后面的4个字节部分，如图4-4所示。
图4-4 绝对地址指令
当源代码"a.c"在被编译成目标文件时，编译器并不知道"shared"和"swap"的地址，因为它们定义在其他目标文件中。所以编译器就暂时把地址0看作是"shared"的地址，我们可以看到这条"mov"指令中，关于"shared"的地址部分为"0x00000000"。
另外一个是偏移为0x26的指令的一条调用指令，它其实就表示对swap函数的调用，如图4-5所示。
图4-5 相对地址指令
这条指令共5个字节，前面的0xE8是操作码（Operation Code），从Intel的IA-32体系软件开发者手册（IA-32 Intel Architecture Software Developer's Manual，参考文献里有详细介绍）可以查阅到，这条指令是一条近址相对位移调用指令（Call near, relative, displacement relative to next instruction），后面4个字节就是被调用函数的相对于调用指令的下一条指令的偏移量。在没有重定位之前，相对偏移被置为0xFFFFFFFC（小端），它是常量"-4"的补码形式。
让我们来仔细看这条指令的含义。紧跟在这条call指令后面的那条指令为add指令，add指令的地址为0x2b，而相对于add指令偏移为"-4"的地址即0x2b - 4 = 0x27。所以这条call指令的实际调用地址为0x27。我们可以看到0x27存放着并不是swap函数的地址，跟前面"shared"一样，"0xFFFFFFFC"只是一个临时的假地址，因为在编译的时候，编译器并不知道"swap"的真正地址。
编译器把这两条指令的地址部分暂时用地址"0x00000000"和"0xFFFFFFFC"代替着，把真正的地址计算工作留给了链接器。我们通过前面的空间与地址分配可以得知，链接器在完成地址和空间分配之后就已经可以确定所有符号的虚拟地址了，那么链接器就可以根据符号的地址对每个需要重定位的指令进行地位修正。我们用objdump来反汇编输出程序"ab"的代码段，可以看到main函数的两个重定位入口都已经被修正到正确的位置：
$objdump -d 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 0xfffffffc(%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,0xfffffff8(%ebp)
80480ac: c7 44 24 04 08 91 04 movl $0x8049108,0x4(%esp)
80480b3: 08
80480b4: 8d 45 f8 lea 0xfffffff8(%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 0xfffffffc(%ecx),%esp
80480c7: c3 ret
080480c8 <swap>:
80480c8: 55 push %ebp
...
经过修正以后，"shared"和"swap"的地址分别为0x08049108和0x00000009（小端字节序）。关于"shared"很好理解，因为"shared"变量的地址的确是0x08049108。对于"swap"来说稍显晦涩。我们前面介绍过，这个"call"指令是一条近址相对位移调用指令，它后面跟的是调用指令的下一条指令的偏移量，"call"指令的下一条指令是"add"，它的地址是0x080480bf，所以"相对于add指令偏移量为0x00000009"的地址为0x080480bf + 9 = 0x080480c8，即刚好是"swap "函数的地址。有兴趣的读者可以阅读后面的"指令修正方式"一节，那里我们将更加详细介绍指令修正时的地址计算方式。
4.2.2 重定位表
那么链接器是怎么知道哪些指令是要被调整的呢？这些指令的哪些部分要被调整？怎么调整？比如上面例子中"mov"指令和"call"指令的调整方式就有所不同。事实上在ELF文件中，有一个叫**重定位表（Relocation Table）**的结构专门用来保存这些与重定位相关的信息，我们在前面介绍ELF文件结构时已经提到过了重定位表，它在ELF文件中往往是一个或多个段。
对于可重定位的ELF文件来说，它必须包含有重定位表，用来描述如何修改相应的段里的内容。对于每个要被重定位的ELF段都有一个对应的重定位表，而一个重定位表往往就是ELF文件中的一个段，所以其实重定位表也可以叫重定位段，我们在这里统一称作重定位表。比如代码段".text"如有要被重定位的地方，那么会有一个相对应叫".rel.text"的段保存了代码段的重定位表；如果代码段".data"有要被重定位的地方，就会有一个相对应叫".rel.data"的段保存了数据段的重定位表。我们可以使用objdump来查看目标文件的重定位表：
$ objdump -r a.o
a.o: file format elf32-i386
RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
0000001c R_386_32 shared
00000027 R_386_PC32 swap
这个命令可以用来查看"a.o"里面要重定位的地方，即"a.o"所有引用到外部符号的地址。每个要被重定位的地方叫一个重定位入口（Relocation Entry），我们可以看到"a.o"里面有两个重定位入口。重定位入口的偏移（Offset）表示该入口在要被重定位的段中的位置，"RELOCATION RECORDS FOR [.text]"表示这个重定位表是代码段的重定位表，所以偏移表示代码段中须要被调整的位置。对照前面的反汇编结果可以知道，这里的0x1c和0x27分别就是代码段中"mov"指令和"call"指令的地址部分。
对于32位的Intel x86系列处理器来说，重定位表的结构也很简单，它是一个Elf32_Rel结构的数组，每个数组元素对应一个重定位入口。Elf32_Rel的定义如下：
typedef struct {
Elf32_Addr r_offset;
Elf32_Word r_info;
} Elf32_Rel;
4.2.3 符号解析
在我们通常的观念里，之所以要链接是因为我们目标文件中用到的符号被定义在其他目标文件，所以要将它们链接起来。比如我们直接使用ld来链接"a.o"，而不将"b.o"作为输入。链接器就会发现shared和swap两个符号没有被定义，没有办法完成链接工作：
$ ld a.o
a.o: In function `main':
a.c:(.text+0x1c): undefined reference to `shared'
a.c:(.text+0x27): undefined reference to `swap'
这也是我们平时在编写程序的时候最常碰到的问题之一，就是链接时符号未定义。导致这个问题的原因很多，最常见的一般都是链接时缺少了某个库，或者输入目标文件路径不正确或符号的声明与定义不一样。所以从普通程序员的角度看，符号的解析占据了链接过程的主要内容。
通过前面指令重定位的介绍，我们可以更加深层次地理解为什么缺少符号的定义会导致链接错误。其实重定位过程也伴随着符号的解析过程，每个目标文件都可能定义一些符号，也可能引用到定义在其他目标文件的符号。重定位的过程中，每个重定位的入口都是对一个符号的引用，那么当链接器须要对某个符号的引用进行重定位时，它就要确定这个符号的目标地址。这时候链接器就会去查找由所有输入目标文件的符号表组成的全局符号表，找到相应的符号后进行重定位。
比如我们查看"a.o"的符号表：
$ readelf -s a.o
Symbol table '.symtab' contains 10 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00000000 0 FILE LOCAL DEFAULT ABS a.c
2: 00000000 0 SECTION LOCAL DEFAULT 1
3: 00000000 0 SECTION LOCAL DEFAULT 3
4: 00000000 0 SECTION LOCAL DEFAULT 4
5: 00000000 0 SECTION LOCAL DEFAULT 6
6: 00000000 0 SECTION LOCAL DEFAULT 5
7: 00000000 52 FUNC GLOBAL DEFAULT 1 main
8: 00000000 0 NOTYPE GLOBAL DEFAULT UND shared
9: 00000000 0 NOTYPE GLOBAL DEFAULT UND swap
"GLOBAL"类型的符号，除了"main"函数是定义在代码段之外，其他两个"shared"和"swap"都是"UND"，即"undefined"未定义类型，这种未定义的符号都是因为该目标文件中有关于它们的重定位项。所以在链接器扫描完所有的输入目标文件之后，所有这些未定义的符号都应该能够在全局符号表中找到，否则链接器就报符号未定义错误。
4.2.4 指令修正方式
不同的处理器指令对于地址的格式和方式都不一样。比如对于32位Intel x86处理器来说，转移跳转指令（jmp 指令）、子程序调用指令（call 指令）和数据传送指令（mov 指令）寻址方式千差万别。直至2006年为止，Intel x86系列CPU的jmp指令有11种寻址模式；call指令有10种；mov指令则有多达34种寻址模式！这些寻址方式有如下几方面的区别：
- 近址寻址或远址寻址。
- 绝对寻址或相对寻址。
- 寻址长度为8位、16位、32位或64位。
但是对于32位x86平台下的ELF文件的重定位入口所修正的指令寻址方式只有两种：
- 绝对近址32位寻址。
- 相对近址32位寻址。
这两种重定位方式指令修正方式每个被修正的位置的长度都为32位，即4个字节。而且都是近址寻址，不用考虑Intel的段间远址寻址。唯一的区别就是绝对寻址和相对寻址。前面我们提到过，重定位入口的r_info成员低8位表示重定位入口类型，如表4-2所示。
表4-2
A = 保存在被修正位置的值
P = 被修正的位置（相对于段开始的偏移量或者虚拟地址），注意，该值可通过r_offset计算得到
S = 符号的实际地址，即由r_info的高24位指定的符号的实际地址
对照前面a.o的重定位信息，我们可以看到第一个重定位入口是对swap符号的引用，类型为R_386_PC32，查阅Intel指令手册，它的确是一条相对位移调用指令；而shared是R_386_32类型的，它修正的是一条传输指令的源，该传输指令的源是一个立即数，即shared的绝对地址。所以这两个重定位入口很具有代表性，分别代表了两种不同的重定位地址修正方式。
现在让我们假设在将a.o和b.o链接成最终可执行文件后，main函数的虚拟地址为0x1000，swap函数的虚拟地址为0x2000；shared变量的虚拟地址为0x3000。那么我们的链接器将如何修正a.o里面这两个重定位入口呢？
绝对寻址修正 让我们先看a.o的第一个重定位入口，即偏移为0x18的这条mov指令的修正，它的修正方式是R_386_32，即绝对地址修正。对于这个重定位入口，它修正后的结果应该是S + A。
- S是符号shared的实际地址，即0x3000。
- A是被修正位置的值，即0x00000000。
所以最后这个重定位入口修正后地址为：0x3000 + 0x00000000 = 0x3000。即指令修正后应该是：
...
1011: c7 45 f8 64 00 00 00 movl $0x64,0xfffffff8(%ebp)
1018: c7 44 24 04 00 30 00 movl $0x3000,0x4(%esp)
101f: 00
1020: 8d 45 f8 lea 0xfffffff8(%ebp),%eax
...
相对寻址修正* 让我们再来看看a.o的第二个重定位入口，即偏移为0x26的这条call指令的修正，它的指令修正方式是R_386_PC32，即相对寻址修正。对于这个重定位入口，它修正后的结果应该是S + A - P。
- S是符号swap的实际地址，即0x2000；
- A是被修正位置的值，即0xFFFFFFFC（-4）；
- P为被修正的位置，当链接成可执行文件时，这个值应该是被修正位置的虚拟地址，即0x1000 + 0x27。
所以最后这个重定位入口修正后地址为：0x2000 + (-4) - ( 0x1000 + 0x27) = 0xFD5。即指令修正后应该是：
...
1023: 8d 45 f8 lea 0xfffffff8(%ebp),%eax
1026: e8 d5 0f 00 00 call 0xfd5
102b: 89 04 24 mov %eax,(%esp)
...
2000<swap>:
...
这条相对位移调用指令调用的地址是该指令下一条指令的起始地址加上偏移量，即：0x102b + 0xfd5 = 0x2000，刚好是swap函数的地址。
从这两个例子可以看出来，绝对寻址修正和相对寻址修正的区别就是绝对寻址修正后的地址为该符号的实际地址；相对寻址修正后的地址为符号距离被修正位置的地址差。