六星经典CSAPP-笔记(7)加载与链接(上)

六星经典CSAPP-笔记(7)加载与链接

1.对象文件(Object File)

1.1 文件类型

对象文件有三种形式：

• 可重定位对象文件(Relocatable object file)：包含二进制代码和数据，能与其他可重定位对象文件在编译时合并创建出一个可执行文件。
• 可执行对象文件(Executable object file)：包含可以直接拷贝进行内存执行的二进制代码和数据。
• 共享对象文件(Shared object file)：一种特殊的可重定位对象文件，能在加载时或运行时，装载进内存进行动态链接。

1.2 文件格式

本质上，对象文件只是保存在磁盘文件中的一串字节，每个系统的文件格式都不尽相同：

• Bell实验室的第一个Unix系统使用 a.out格式。
• System V Unix的早期版本使用 Common Object File Format(COFF)。
• Windows NT使用COFF的变种，叫做 Portable Executable(PE)。
• 现代Unix系统，包括Linux、新版System V、BSD变种、Solaris都使用 Executable and Linkable Format(ELF)。

CSAPP中以ELF作为讲解的范例，但其实各种文件格式都是类似的。一个ELF文件包含下列Section：

1.3 编译驱动(Compile Driver)

简单的一条编译命令的实际运行过程其实是非常复杂的，之所以我们感觉简单就是因为编译驱动的存在。几乎所有编译系统都提供了driver作为统一的接口（这种设计思想与Facade设计模式异曲同工，而且在Hadoop、Mahout等框架中我们也能看到driver这个角色的存在），方便了用户的使用。

下面是一个小例子，main.c引用swap.c中实现的函数swap()，而swap.c操作main.c中声明的数据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;
}

下面逐步来看compile driver默默为我们完成的工作。尽管我们只敲了一行命令，但gcc在 背后调度了预处理器cpp、编译器cc1、汇编器as、链接器ld完成四个阶段的工作。其中编译器和汇编器能产生可重定位对象文件，包括共享对象文件，而链接器负责产生可执行对象文件：

# Delegate to compile driver
gcc -O2 -g -o p main.c swap.c# 1.Driver runs C preprocessor(cpp) to translate main.c into an ASCII intermediate file main.i:
cpp [other args] main.c /tmp/main.i# 2.Driver runs C compiler(cc1) to translate main.i into an ASCII assembly language file main.s:
cc1 /tmp/main.i main.c -O2 [other args]# 3.Driver runs assembler(as) to translate main.s into a relocatable object file main.o:
as [other args] -o /tmp/main.o /tmp/main.s# Same process to generate swap.o...# 4.Driver runs linker program(ld) to combine main.o and swap.o, along with necessary system object files to create executable object file p:
ld -o p [system object files and args] /tmp/main.o /tmp/swap.o

1.4 GCC背后的故事

下面来看我们学习如何手动完成预处理、编译、汇编、链接四个阶段的工作，以及每个阶段的输出的具体文件内容，深入理解各个阶段完成的工作，参考GCC编译的背后：

• 预处理(Pre-processing) -E选项：C语言编译器对各种预处理命令进行处理，包括 头文件的包含、宏定义的扩展、条件编译的选择 等，主要有#define, #include和#ifdef … #endif。此阶段 最重要的参数是-DXXX，将导致#ifdef XXX #endif之间的代码块包含进最终的源文件中。
• 编译阶段(Compiling) -S选项：C语言编译器会进行词法分析、语法检查（通过-std指定遵循哪个标准）和分析、代码优化（通过-O指定优化级别），最后把源代码翻译成中间语言，即汇编语言。编译器一般采取 multi-pass多趟分析的方式，例如第一遍扫描做词法分析；第二遍扫描做语法分析；第三遍扫描做代码优化和存储分配；第四遍扫描做代码生成。
• 汇编阶段(Assembling) -c选项：把编译阶段生成的”.s”文件转成二进制目标代码。
• 链接阶段(Linking) 无选项：以静态或动态链接的方式，将”.o”文件链接生成可执行文件，对符号和引用进行重定位。

可以像下面例子一样一步步来，也可以直接将.c转成任何一阶段的输出。比如gcc -c swap.c -o swap.o就对swap.c做了简略处理，直接从.c跳到了第三阶段汇编的输出swap.o。又比如最后一步链接时，参数中的.c会自动转成.o再链接。所以说driver还是非常智能的！

# Phase-1: Pre-processing
$ gcc -E main.c -o main.i
$ cat main.i
# 1 "main.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "main.c"
void swap();int buf[2] = {1, 2};int main()
{
swap();
return 0;
}# Phase-2: Compiling
$ gcc -S main.i -o main.s
$ cat main.s
.file "main.c"
.globl buf
.data
.align 4
buf:
.long 1
.long 2
.def __main; .scl 2; .type 32; .endef
.text
.globl main
.def main; .scl 2; .type 32; .endef
.seh_proc main
main:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
subq $32, %rsp
.seh_stackalloc 32
.seh_endprologue
call __main
call swap
movl $0, %eax
addq $32, %rsp
popq %rbp
ret
.seh_endproc
.ident "GCC: (GNU) 4.9.2"
.def swap; .scl 2; .type 32; .endef# Phase-3: Assembling
$ gcc -c main.s -o main.o
$ objdump -d main.omain.o: file format pe-x86-64Disassembly of section .text:0000000000000000 <main>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 20 sub $0x20,%rsp
8: e8 00 00 00 00 callq d <main+0xd>
d: e8 00 00 00 00 callq 12 <main+0x12>
12: b8 00 00 00 00 mov $0x0,%eax
17: 48 83 c4 20 add $0x20,%rsp
1b: 5d pop %rbp
1c: c3 retq
1d: 90 nop
1e: 90 nop
1f: 90 nop# Phase-4: Linking
$ gcc -c swap.c -o swap.o
$ gcc main.o swap.o -o p
$ objdump -d main.o
00000001004010e0 <main>:
1004010e0: 55 push %rbp
1004010e1: 48 89 e5 mov %rsp,%rbp
1004010e4: 48 83 ec 20 sub $0x20,%rsp
1004010e8: e8 83 00 00 00 callq 100401170 <__main>
1004010ed: e8 0e 00 00 00 callq 100401100 <swap>
1004010f2: b8 00 00 00 00 mov $0x0,%eax
1004010f7: 48 83 c4 20 add $0x20,%rsp
1004010fb: 5d pop %rbp
1004010fc: c3 retq
1004010fd: 90 nop
1004010fe: 90 nop
1004010ff: 90 nop

下面就要正式开始学习了！本章对预处理和编译原理知识讲解的很少，而 关注于第三步汇编与机器码中蕴含的符号解析规则，以及第四步的链接和装载知识。

2.对象文件查看工具

下面以之前编译出的main.o、swap.o、p文件为例，介绍对象文件的常用查看工具。

2.1 nm

nm能直接列出目标文件的符号清单。后面要介绍的readelf是个全能的工具，而nm专注于符号表这一section：

[root@vm Temp]# nm main.o
0000000000000000 D buf
0000000000000000 T main
U swap
[root@vm Temp]# nm swap.o
U buf
0000000000000000 D bufp0
0000000000000008 C bufp1
0000000000000000 T swap

2.2 objdump

objdump是个更通用的二进制文件查看工具。它使用GNU的BFD库解析对象文件，objdump -i能查看本机上BFD支持的所有对象文件类型。所以不限于某一种对象文件，如ELF文件。objdump -t也能查看符号表，但是它更强大的功能是-d选项查看.text section，即可执行代码，它能显示机器码和汇编代码的对应，是学习底层编码的必备工具！但正因为这种通用性，像ELF中的一些section，如.rel.text，objdump -h或-j.rel.text都是无法识别出来的。这时就要使用readelf专门的工具来查看了，readelf -S能列出比objdump更多的section header。

[root@vm Temp]# objdump -d main.omain.o: file format elf64-x86-64Disassembly of section .text:0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8,%rsp
4: 31 c0 xor %eax,%eax
6: e8 00 00 00 00 callq b <main+0xb>
b: 31 c0 xor %eax,%eax
d: 48 83 c4 08 add $0x8,%rsp
11: c3 retq

《程序员的自我修养—链接、装载与库》：BFD库是一个GNU项目，它的目标就是希望通过一种统一的接口来处理不同的目标文件。BFD这个项目本身是binutils项目的一个子项目。BFD把目标文件抽象成一个统一的模型，比如在这个抽象的目标文件模型中，最开始有一个描述整个目标文件总体信息的”文件头”，就跟我们实际的ELF文件一样，文件头后面是一系列的段，每个段都有名字、属性和段的内容，同时还抽象了符号表、定位表、字符串表等类似的概念，使得BFD库的程序只要通过这个抽象的目标文件模型就可以实现操作所有BFD支持的目标文件格式。

2.3 readelf

用readelf工具可以方便地查看ELF格式的对象文件的内容，例如观察一下前面main.c和swap.c例子生成的可执行文件p。观察到的内容与前面介绍的一样。首先以ELF的magic number（若不匹配，如.exe文件，则readelf会报错）、生成此对象文件的系统上的字长和字节序的标记位开始，占用16字节。然后是机器硬件信息、文件类型（EXEC可执行文件）、各种偏移量等等。后面我们会一直使用这个工具来辅助学习：

[root@linux Temp]# readelf -h -W p
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2\'s complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x400390
Start of program headers: 64 (bytes into file)
Start of section headers: 3552 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 8
Size of section headers: 64 (bytes)
Number of section headers: 36
Section header string table index: 33

2.4 ldd

ldd能查看可执行文件依赖的.so链接库，这对解决缺少依赖包的问题非常有用：

[root@BC-VM-edce4ac67d304079868c0bb265337bd4 Temp]# ldd p
linux-vdso.so.1 => (0x00007fff493ff000)
libc.so.6 => /lib64/libc.so.6 (0x0000003c07000000)
/lib64/ld-linux-x86-64.so.2 (0x0000003c06800000)

3.符号解析(Symbol Resolution)

3.1 符号

符号分为三种类型：

• 当前模块定义，被其他模块引用的全局符号**：相当于non-static的函数和全局变量。
• 当前模块引用，其他模块定义的全局符号：这样的符号叫做外部符号(external)，相当于在其他模块中定义的函数和变量。
• 当前模块定义，仅被当前模块引用的局部符号：这些符号在当前模块的任何地方都可见，但不可被其他任何模块引用。要注意的是：
  
  1. 对象文件中的section以及当前模块所在源文件的名称也都有对应的局部符号。
  2. 局部符号不是non-static局部变量，non-static局部变量是运行时在栈上维护的，链接器并不感兴趣。

符号的C语言结构定义如下。其中name是符号在.strtab section中的偏移量，指向一个以null结尾的字符串，表示符号的名字。关于value，对于可重定位模块，value是定义符号位置距离符号所在section（由char section变量指明）的偏移量，而对于可执行模块，value是运行时的绝对地址。type指明符号的类型是数据、函数、甚至是源文件的路径名等：

typedef struct {
int name; /* String table offset */
int value; /* Section offset, or VM address */
int size; /* Object size in bytes */
char type:4, /* Data, func, section, or src file name (4 bits) */
binding:4; /* Local or global (4 bits) */
char reserved; /* Unused */
char section; /* Section header index, ABS, UNDEF or COMMON */
} Elf_Symbol;

模块（module）的访问权限

C源文件扮演着模块（module）的角色。任何用static声明的变量和函数都是当前模块私有的，而未用static声明的都是可被其他任意模块访问的。对应于Java和C++中的public和private声明。

3.2 符号表

用readelf -s选项可以查看对象文件的符号表的具体内容，而且最后的Name列已经自动将.strtab中对应的字符串显示出来了，很方便！各个表项的含义对应结构Elf_Symbol中的变量。用gcc -c生成.o可重定位文件main.o和swap.o，然后观察一下main.o中的符号1、15和swap.o中的1、16、17。能够注意到有三种特殊的伪section名(Ndx)：

• ABS：表示符号不应该被重定位。例如符号1表示的main.c和swap.c。
• UNDEF：表示符号被当前模块引用但是在其他模块中定义。例如main.c中引用了swap()，所以有了符号15的UND swap。同样，swap.c引用了buf变量，所以有了符号16的UND buf。
• COMMON：表示未初始化的数据对象。例如swap.c中的bufp1就是COM，最终会在链接时分配为.bss中的一个对象。

[root@vm Temp]# readelf -s -W main.o Symbol table '.symtab' contains 17 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS main.c
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
5: 0000000000000000 0 SECTION LOCAL DEFAULT 5
6: 0000000000000000 0 SECTION LOCAL DEFAULT 6
7: 0000000000000000 0 SECTION LOCAL DEFAULT 8
8: 0000000000000000 0 SECTION LOCAL DEFAULT 10
9: 0000000000000000 0 SECTION LOCAL DEFAULT 12
10: 0000000000000000 0 SECTION LOCAL DEFAULT 14
11: 0000000000000000 0 SECTION LOCAL DEFAULT 16
12: 0000000000000000 0 SECTION LOCAL DEFAULT 17
13: 0000000000000000 0 SECTION LOCAL DEFAULT 15
14: 0000000000000000 18 FUNC GLOBAL DEFAULT 1 main
15: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND swap
16: 0000000000000000 8 OBJECT GLOBAL DEFAULT 3 buf[root@vm Temp]# readelf -s -W swap.o Symbol table '.symtab' contains 18 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS swap.c
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 5
5: 0000000000000000 0 SECTION LOCAL DEFAULT 6
6: 0000000000000000 0 SECTION LOCAL DEFAULT 7
7: 0000000000000000 0 SECTION LOCAL DEFAULT 9
8: 0000000000000000 0 SECTION LOCAL DEFAULT 11
9: 0000000000000000 0 SECTION LOCAL DEFAULT 13
10: 0000000000000000 0 SECTION LOCAL DEFAULT 15
11: 0000000000000000 0 SECTION LOCAL DEFAULT 17
12: 0000000000000000 0 SECTION LOCAL DEFAULT 18
13: 0000000000000000 0 SECTION LOCAL DEFAULT 16
14: 0000000000000000 35 FUNC GLOBAL DEFAULT 1 swap
15: 0000000000000000 8 OBJECT GLOBAL DEFAULT 3 bufp0
16: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND buf
17: 0000000000000008 8 OBJECT GLOBAL DEFAULT COM bufp1

通过readelf -S选项能查看各个section的下标，这样就能与.symtab中的Ndx字段对应上了。例如符号main和swap对应的1表示.text，符号buf和bufp0对应的3表示.data：

[root@vm Temp]# readelf -S -W main.o
There are 22 section headers, starting at offset 0x340:Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 0000000000000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 0000000000000000 000040 000012 00 AX 0 0 16
[ 2] .rela.text RELA 0000000000000000 000a70 000018 18 20 1 8
[ 3] .data PROGBITS 0000000000000000 000054 000008 00 WA 0 0 4
[ 4] .bss NOBITS 0000000000000000 00005c 000000 00 WA 0 0 4
...

3.3 全局符号解析规则

首先介绍两个概念。在编译时，编译器会输出strong或weak全局符号到汇编器。函数和初始化的全局变量会产生强符号，例如示例程序中的buf、bufp0、main和swap都是强符号。而未初始化的全局变量会产生弱符号，bufp1就是弱符号。当遇到同名的多个符号时：

• 规则-1：不允许出现多个同名的强符号。
• 规则-2：一个强符号和多个弱符号存在时，选择强符号。
• 规则-3：多个弱符号存在时，选择任意一个弱符号。

规则-1比较简单，两个源文件中同名的main()函数，或者两个int x = 1;都会产生两个同名的强符号，违反了规则-1，从而导致编译失败！

下面是一个规则-2的例子。foo3.c中的变量x是强符号，因此bar3.c中f()最终修改的其实是foo3.c中的变量x，而非bar3.c的。执行gcc -o foobar3 foo3.c bar3.c编译出可执行文件foobar3。默认情况下，编译器检测到多个定义x时是不会给出任何警告或提示的，所以运行结果就是x = 15212。

/* foo3.c */
#include <stdio.h>void f(void);int x = 15213;int main()
{
f();
printf("x = %d\n", x);
return 0;
}/* bar3.c */
int x;void f()
{
x = 15212;
}

同名符号导致的bug往往非常隐蔽而难以查找，并且因为编译器不会给出警告，一般是运行时才会出现问题，所以这些bug也非常致命！例如下面的例子，根据规则-2，bar4.c中的f()修改的的确是foo4.c中的强符号x。但由于bar4.c中变量x是double类型，编译出的指令也是操作double的指令，结果运行时不仅修改了x，还覆盖了与x相邻的变量y的值，这有可能是个非常严重的bug！

/* foo4.c */
#include <stdio.h>void f(void);int x = 15213;
int y = 15212;int main()
{
printf("before f(): x = 0x%x , y = 0x%x\n", x, y);
f();
printf("after f(): x = 0x%x , y = 0x%x\n", x, y);
return 0;
}/* bar4.c */
double x;void f()
{
x = -0.0;
}

这种问题在大型C项目中并不罕见，如果管理疏忽，不同模块很可能会有同名的符号。建议一定要使用-fno-common选项编译：

$ gcc -fno-common -o foobar4 foo4.c bar4.c
/tmp/ccE4LcpK.o:bar4.c:(.bss+0x0): multiple definition of 'x'
/tmp/ccQcdU0H.o:foo4.c:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status

3.4 符号解析算法

参考[4.1.2 静态链接中的符号解析](#4.1.2 静态链接中的符号解析)和[4.2.2 动态链接中的符号解析](#4.2.2 动态链接中的符号解析)。

4.链接

4.1 静态链接

4.1.1 为什么要静态链接

ANSI C的各种函数都以静态链接库的形式提供给链接器，当链接时从库中拷贝我们程序引用的那些模块代码，最终构建出可执行文件。例如atoi、printf、scanf、strcpy等都包含在libc.a库中。而sin、cos、sqrt等数学函数则包含在libm.a库中。那如果不用静态链接，程序世界会怎么样？

• 方案1 编译器生成：第一种方案就是编译器在编译时检测出被调用的标准函数，然后自动生成出合适的代码，Pascal语言中就是这样实现的。这种方式对我们这些应用开发者来说太爽了，不用关心各种类库，直接使用就行了！但对编译器开发者来说就是噩梦。编译将变得异常复杂，每次有标准函数添加、删除、修改时都要发布一版新的编译器。
• 方案2 所有标准函数放入一个对象模块：假如将所有标准C函数都放入到一个libc.o的可重定位对象模块中，那么就可以gcc main.c /usr/lib/libc.o编译出可执行文件。缺点就是每个可执行文件都会包含一份完整的标准函数代码，占用更多磁盘空间，运行时也占用更多内存空间。而且任何标准函数的改变都需要应用程序重新编译。那如果将libc.o拆成printf.o、scanf.o呢？这样能节省空间，但应用开发者要显示引入很多的.o文件。

静态链接就是解决上述方法中存在的缺陷的！类似方案2，库函数实现是与编译器实现解耦合的，而且静态链接也类似地引用一些静态链接库。但一来静态链接库都不会拆的那么碎；二来在不拆碎的情况下，链接器依然能够只拷贝应用程序中引用的代码，从而节省磁盘和运行时的内存空间；三来compile driver总是自动将常用的libc.a传给链接器，进一步方便了开发者。第一和第三点好说，但关于第二点它是怎么做到的呢？奥秘就在静态链接库中！

4.1.2 静态链接库

在Unix系统中，静态链接库以一种特殊的文件格式 archive格式存储在磁盘上，一个archive文件是一组可重定位对象文件的集合，以.a为文件扩展名，有一个header会描述其中每个对象文件的大小和位置。下面就来动手制作一个我们自己的静态链接库！

在本实例中，我们的静态链接库中有两个可重定位对象模块，对应下面addvec.c和multvec.c源文件，而使用它们的应用程序是main.c：

/* addvec.c */
void addvec(int *x, int *y, int *z, int n)
{
int i;
for(i = 0; i < n; i++) {
z[i] = x[i] + y[i];
}
}/* multvec.c */
void multvec(int *x, int *y, int *z, int n)
{
int i;
for(i = 0; i < n; i++) {
z[i] = x[i] * y[i];
}
}/* main2.c */
#include <stdio.h>// Add header to system path
//#include "vector.h"
void addvec(int *x, int *y, int *z, int n);
void multvec(int *x, int *y, int *z, int n);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]);
return 0;
}

下面就开始制作我们的第一个静态链接库。首先用gcc -c产生.o可重定位对象文件，之后用AR工具制作出archive静态链接库。同样gcc -c产生main2.o后，用静态链接的方式链接它和main.c产生可执行文件。通过objdump -a能够查看archive文件的头部：

$ objdump -a libvector.a
In archive libvector.a:addvec.o: file format pe-x86-64
rw-rwxr-- 1001/513 788 May 22 09:20 2015 addvec.omultvec.o: file format pe-x86-64
rw-rwxr-- 1001/513 788 May 22 09:20 2015 multvec.o

查看符号表发现没有符号multvec，通过objdump发现最终生成的可执行文件p2中确实没有multvec函数的代码。这证明了：链接器发现addvec.o被main2.o引用了，所以它拷贝addvec.o到p2中。但main2.o中没有引用multvec.o的任何符号，所以它没有拷贝multvec.o。此外，链接器还拷贝了许多系统函数，如main2.o引用的printf。

$ gcc -c addvec.c multvec.c
$ ar rcs libvector.a addvec.o multvec.o
$ gcc -O2 -c main2.c
$ gcc -static -o p2 main2.o ./libvector.a
$ ./p2
z = [4 6]
$ nm p2 | grep vec
00000001004010e0 T addvec
$ objdump -W -d p2
00000001004010e0 <addvec>:
...0000000100401180 <printf>:
...00000001004017a0 <main>:
...

4.1.3 静态链接中的符号解析

首先，为了便于理解，定义三个符号：

• E(rElocatable)：可重定位对象文件的集合。
• U(Unresolved)：未解析符号的集合（例如被引用，但是还未找到定义的符号）。
• D(Defined)：在之前输入文件中已定义的符号。

链接器按照输入文件在driver的参数列表中出现的顺序，从左向右，依次扫描每个可重定位对象文件或静态链接库archive。静态链接过程如下：

1. 若输入文件f是对象文件，则将f加入E，并将f中的符号引用和定义分别更新到U和D。
2. 若输入文件f是链接库，则尝试将f中各个.o定义的符号与U中未解析的符号匹配。如果m.o中的符号能匹配上U中的某个符号，则将m加入E，并更新U和D。未匹配U中任何符号的.o直接被丢弃。
3. 若最终U不为空，则链接器报错。否则合并E中的所有.o生成可执行文件。

不幸的是，这套链接算法会导致一些讨厌的“链接时”错误，因为链接库和对象文件在命令行中出现的顺序至关重要！如果定义符号的链接库出现在引用这个符号的对象文件之前了，那么链接就会失败。例如前面的例子，我们将main2.o放到链接库libvector.a之后：

$ gcc -static -o p2 ./libvector.a main2.o
main2.o:main2.c:(.text.startup+0x25): undefined reference to 'addvec'
main2.o:main2.c:(.text.startup+0x25): relocation truncated to fit: R_X86_64_PC32 against undefined symbol 'addvec'
collect2: error: ld returned 1 exit status

因为扫描libvector.a时，U是空的，所以libvector.a中的.o都不会被加入到E，而是直接被丢弃。于是符号addvec就无处解析了。黄金法则是：链接库放到命令行的最末尾。当有多个链接库时，如果不同链接库中的成员.o文件都是独立的，不存在引用关系，那么这些链接库可以在命令行末尾以任意顺序放置。

当链接库之间也存在引用关系时，为了链接成功，我们可以在命令行上让一个链接库出现多次，例如gcc foo.c libx.a liby.a libx.a。另一种方法就是合并相互引用的链接库，例如将libx.a和liby.a合并成一个archive文件。

4.2 动态链接

4.2.1 有了静态链接，为什么还要动态链接

静态链接虽然实现了标准库函数与编译器解耦、只拷贝被引用的代码以节省空间这两个问题，但它却有两个重要的缺点：1）每次静态链接库修改，都要重新链接生成可执行文件；2）尽管只包含了应用程序引用的函数，但像printf这种最常用的标准库函数若不能共享，那么每个程序的进程中都会包含一份printf的代码，还是极大的浪费了硬盘和内存资源。

4.2.2 动态链接库

动态链接是一种解决静态链接方式缺陷的现代创新。动态链接库就是能在运行时被加载到任意内存地址，在内存中与应用程序完成链接的对象模块。这个过程就叫做动态链接。在Unix系统中，动态链接库叫做 共享对象(shared objects)，扩展名就是.so，而在Windows中就叫做 动态链接库(dynamic link libraries)，扩展名就是我们熟悉的.dll。

动态链接库能在以下两方面实现“共享”，针对的就是静态链接的两个缺陷：

• 对于一个特定的函数库，文件系统中只有对应的一份.so文件，而不会拷贝或嵌入到任何引用它的应用程序的可执行文件中。
• 对于一个特定的函数库，拷贝到内存中的.text section也同样只有一份，并且能被不同的进程共享。这一部分内容放到第九章虚拟内存中学习。

还是前面例子中的addvec.c和multvec.c，这次我们把它俩制作成动态链接库。与前面静态链接出来的大小为65295的p2相比（不使用-O2参数），动态链接出来的p2大小是64816（没有比较二进制文件的工具）。基本思想是：在创建可执行文件时做一些静态链接的工作，在程序装载时完成动态链接过程。因此要注意的很重要一点就是：libvector.so中的代码和数据不会被拷贝到p2中，而是拷贝一些使libvector.so中的代码和数据在运行时能被正确解析的重定位和符号表信息。

$ gcc -shared -fPIC -o libvector.so addvec.c multvec.c
$ gcc -o p2 main2.c ./libvector.so

4.2.3 动态链接中的符号解析

（待补充）

5.重定位(Relocation)

符号解析完成后，每个符号引用都关联到唯一的一个符号定义，链接器知道了参数列表中所有输入对象模块.o的所有代码和数据section的确切地址，此时就可以进行重定位了。

5.1 Entry

当链接器产生对象模块.o时，因为不知道最终代码和数据在内存中的位置，更不知道引用的外部符号的位置，所以链接器每遇到一个最终位置未知的引用时，就产生一个relocation entry，代码放在.rel.text中，初始化数据放在.rel.data中。当合并对象文件成可执行文件时再去修改。下面就是ELF的entry格式，offset就是要改写的引用的位置，symbol就是相对于哪个symbol计算：

typedef struct {
int offset; /* Offset of the reference to relocate */
int symbol:24, /* Symbol the reference should point to */
type:8; /* Relocation type */
} Elf32_Rel;

ELF定义了11种类型的重定位entry，我们只关注最重要的两种：

• R_386_PC32：offset所指的引用是一个PC相对地址的偏移。当CPU执行使用PC相对地址的跳转指令时，它会将PC当前值与相对地址相加作为下一条指令的地址。因此这种引用重定位后也必须是相对地址，否则程序运行时CPU会跳转到错误的地址。
• R_386_32：offset所指的引用是一个绝对地址的偏移。程序运行时，CPU会直接使用绝对地址。

PC相对寻址(PC relative addressing)对jump指令来说尤为重要。它的优势是：一来80%~90%的jump都是if/else或while/for产生的nearby指令跳转；二来代码可以是位置独立的(position independent)，可以被加载到内存的任何位置而不用修改地址。具体参考后面PIC部分的讲解。

5.2 重定位符号引用

重定位算法的伪代码如下，主要关注R_386_PC32和R_386_32这两种类型的entry：

foreach section s {
foreach relocation entry r {
refptr = s + r.offset; /* ptr to reference to be relocated */ /* Relocate a PC-relative reference */
if (r.type == R_386_PC32) {
refaddr = ADDR(s) + r.offset; /* ref’s run-time address */
*refptr = (unsigned) (ADDR(r.symbol) + *refptr - refaddr);
} /* Relocate an absolute reference */
if (r.type == R_386_32)
*refptr = (unsigned) (ADDR(r.symbol) + *refptr);
}
}

5.2.1 相对地址重定位

上面的算法看着有些晕，ADDR(s)和ADDR(r.symbol)应该是.text section中<main>和<swap>两个符号的地址，而非.text的地址吧，因为.text里包含了很多符号标签啊！还是来看一个例子来理解重定位算法，仔细观察第11行。0xe8是call指令的opcode，后面fc ff ff ff是小尾端补码表示的-4。简单温习一下：当执行到行11时，PC已更新为16，所以此处的-4实际表达的跳转地址是当前PC+(-4)=12。

注意：对于循环、私有函数调用等模块内的jump，此处12就是要跳转的地址。但对于swap这种外部symbol来说，12就是call操作数本身的地址（call的地址是11），因为此时还不知道swap的地址是什么，所以看起来有点像死循环，可以与六星经典CSAPP-笔记(3)程序的机器级表示中jump的例子对比一下就能看出了。通过后面的算法讲解能知道，计算出下一条指令的地址非常重要！所以CSAPP说 这是一个powerful trick，因为它使链接器blindly得到下一条指令地址，blissfully unaware of本机的指令编码方式，从而完成引用的重定位。通过-4这个操作数的地址（见后，保存在.rel.text中）加上Intel指令的信息也能硬生生的算出下一条指令的地址，但这样就要求链接器要知道所有机器指令的知识。

objdump -r能自动将地址12与.rel.text中的偏移量匹配，将匹配上的entry的名称显示在行11下面。用readelf -r能打印.rel.text section的内容：

[root@vm Temp]# objdump -d -r main.omain.o: file format elf32-i386Disassembly 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 04 sub $0x4,%esp
11: e8 fc ff ff ff call 12 <main+0x12>
12: R_386_PC32 swap
16: b8 00 00 00 00 mov $0x0,%eax
1b: 83 c4 04 add $0x4,%esp
1e: 59 pop %ecx
1f: 5d pop %ebp
20: 8d 61 fc lea 0xfffffffc(%ecx),%esp
23: c3 ret [root@vm Temp]# readelf -r main.oRelocation section '.rel.text' at offset 0x320 contains 1 entries:
Offset Info Type Sym.Value Sym. Name
00000012 00000902 R_386_PC32 00000000 swap

回忆一下：关于PC相对地址和地址的编码方式

之前在六星经典CSAPP笔记(2)信息的操作和表示和六星经典CSAPP-笔记(3)程序的机器级表示详细学习PC相对地址：

1. 关于PC相对地址：“对于各种跳转的地址，最常见的编码方式就是PC相对地址。即用1、2、4字节的偏移量表示跳转目标地址与jmp指令紧接着的下一条指令的地址。为什么是紧接着jmp指令的下一条指令的地址而不是jmp这一条的？其实也是有历史原因的，因为早期的处理器实现是先更新PC计数器作为第一步，然后再执行当前指令的。所以指令在执行的时候，其实PC已经指向下一条指令了，因此跳转的偏移量也就要相对下一条指令来说了。”

2. 关于地址的编码方式：“对于有符号整数呢，先说一种我们直接能想到的，用二进制表示整数的方式：用最高位当符号位，0表示整数，1表示负数。但这种方式有个重要的缺陷：整数0有正负两种表示方式。现代计算机使用的都是另一种我们耳熟能详的二进制表示方式：补码(two’s complement)！最高位是1时则最高位的值是其权值取负。所以我们看汇编或机器码时经常能看到0xFFFF…xx，就是因为最高位是权值的负数，所以要置很多个次高位为1来表示一个“小”负数。例如0xFFFFFEC8=-312。小尾端机器上也就是C8 FE FF FF。”

现在参照前面的重定位算法的伪代码，解释一下main.o和swap.o链接时，swap符号的重定位过程。先梳理一下现在要研究的问题：

• 已知条件：
  • 行11代码处的偏移量-4：objdump -d main.o查看
  • .rel.text中offset是12：readelf -r main.o查看
  • .rel.text中symbol是swap：readelf -r main.o查看
  • <main>最终地址：readelf -s p查看
  • <swap>最终地址：readelf -s p查看
• 研究问题：链接器要将-4重定位到哪，运行到行11代码时才能正确调用到swap()？

[root@vm Temp]# readelf -s pSymbol table '.symtab' contains 72 entries:
Num: Value Size Type Bind Vis Ndx Name
...
63: 08048378 54 FUNC GLOBAL DEFAULT 12 swap
64: 08049588 0 NOTYPE GLOBAL DEFAULT ABS __bss_start
65: 08049590 4 OBJECT GLOBAL DEFAULT 23 bufp1
66: 08049594 0 NOTYPE GLOBAL DEFAULT ABS _end
67: 0804957c 8 OBJECT GLOBAL DEFAULT 22 buf
68: 08049588 0 NOTYPE GLOBAL DEFAULT ABS _edata
69: 08048429 0 FUNC GLOBAL HIDDEN 12 __i686.get_pc_thunk.bx
70: 08048354 36 FUNC GLOBAL DEFAULT 12 main
71: 08048230 0 FUNC GLOBAL DEFAULT 10 _init

对上面的算法做了些详细解释，终于理解了 相对地址重定位的本质就是rewrite那些操作数是外部symbol的指令，将操作数从一种相对地址rewrite成另一种相对地址。具体说就是从相对于指令所在<main>的相对地址rewrite为相对于.rel.text中symbol的最终真正位置的相对地址：

• 通过<main>的地址和.rel.text中swap偏移：得到要rewrite的操作数在哪
• 通过要rewrite的操作数地址和操作数-4：得到指令call的下一条指令地址
• 通过<swap>的地址：得到symbol最终的真正地址

然后就万事俱备，可以开算了！

refptr = &(-4处)
r.offset = 0x12
r.symbol = swap
r.type = R_386_PC32 ADDR(s) = ADDR(.text) = 0x8048354
ADDR(r.symbol) = ADDR(swap) = 0x8048378 # 要被重定位的指令call的操作数地址
refaddr = ADDR(s) + r.offset
= <main> + offset in .rel.text section
= 0x8048354 + 0x12
= 0x8048366 # 要被重定位指令call的下一条指令，即行16处
# 因为执行call时，跳转地址12 = PC(即refNext) + (-4)
refNext = refaddr - *refptr
= 0x8048366 - (-4)
= 0x804836a # 重定位后的地址 = <swap> - call下一条指令
*refptr = ADDR(r.symbol) + *refptr - refaddr
= <swap> - refNext
= 0x8048378 - 0x804836a
= 0x0e

查看可执行文件p，发现call的操作数的确被rewrite成0e了，证明了上面分析的正确性！程序运行时，当CPU执行到e8 0e这一行，PC=下一条指令地址0x804836a，CPU计算出0x804836a + 0x0e = 0x08048378，恰好就是swap函数真正入口地址，于是程序将返回地址压入栈、修改PC后就可以继续正确地运行下去了！

[root@vm Temp]# objdump -d p
...
08048354 <main>:
8048354: 8d 4c 24 04 lea 0x4(%esp),%ecx
8048358: 83 e4 f0 and $0xfffffff0,%esp
804835b: ff 71 fc pushl 0xfffffffc(%ecx)
804835e: 55 push %ebp
804835f: 89 e5 mov %esp,%ebp
8048361: 51 push %ecx
8048362: 83 ec 04 sub $0x4,%esp
8048365: e8 0e 00 00 00 call 8048378 <swap>
804836a: b8 00 00 00 00 mov $0x0,%eax
804836f: 83 c4 04 add $0x4,%esp
8048372: 59 pop %ecx
8048373: 5d pop %ebp
8048374: 8d 61 fc lea 0xfffffffc(%ecx),%esp
8048377: c3 ret 08048378 <swap>:
...

5.2.2 绝对地址重定位

回忆一下，swap.c中int *bufp0 = &buf[0];。所以bufp0是一个初始化数据对象，将存储在swap.o中的.data section。因为引用的是符号buf的第一个元素，所以bufp0处是0x00000000。objdump默认不显示全0的字节，用objdump -z选项就能看到所有数据：

[root@vm Temp]# objdump -D -r -z swap.o swap.o: file format elf32-i386 ...
Disassembly of section .data:00000000 <bufp0>:
0: 00 00 add %al,(%eax)
0: R_386_32 buf
2: 00 00 add %al,(%eax)
...[root@vm Temp]# readelf -r swap.o Relocation section '.rel.text' at offset 0x374 contains 6 entries:
Offset Info Type Sym.Value Sym. Name
00000007 00000801 R_386_32 00000000 buf
0000000c 00000a01 R_386_32 00000004 bufp1
00000011 00000701 R_386_32 00000000 bufp0
0000001c 00000701 R_386_32 00000000 bufp0
00000021 00000a01 R_386_32 00000004 bufp1
0000002b 00000a01 R_386_32 00000004 bufp1Relocation section '.rel.data' at offset 0x3a4 contains 1 entries:
Offset Info Type Sym.Value Sym. Name
00000000 00000801 R_386_32 00000000 buf

已知条件与相对地址重定位相同：

• 行0处数据是0x00000000
• .rel.text中offset是0x00000000
• .rel.text中symbol是buf
• .data最终地址是08049578
• <buf>最终地址是0804957c

绝对地址重定位非常简单，直接用buf地址+行0处偏移0就可以了，可执行文件p中的bufp0的值是0x7c950408（小尾端存储），的确是buf[0]的起始地址0x0804957c。

[root@localhost Temp]# objdump -D p
...
Disassembly of section .data:08049578 <__data_start>:
8049578: 00 00 add %al,(%eax)
804957a: 00 00 add %al,(%eax)0804957c <buf>:
804957c: 01 00 add %eax,(%eax)
804957e: 00 00 add %al,(%eax)
8049580: 02 00 add (%eax),%al
8049582: 00 00 add %al,(%eax)08049584 <bufp0>:
8049584: 7c 95 jl 804951b <_DYNAMIC+0x83>
8049586: 04 08 add $0x8,%al