六星经典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：

Section	Description
header	Begins with a 16-byte sequence of word size and byte ordering of the system that generated the file. The rest contains the size of header, object file type(relocatable/executable/shared), machine type(IA32), the file offset, size and number of section header table.
.text	The machine code of the compiled program.
.rodata	Read-only data such as the format strings in printf statements, and jump tables for switch statements.
.data	Initialized global C variables. Local C variables are maintained at run time on the stack, and do not appear in either the .data or .bss sections.
.bss	Uninitialized global C variables. This section occupies no actual space in the object file; it is merely a place holder.
.symtab	A symbol table with information about functions and global variables that are defined and referenced in the program.
.rel.text	A list of locations in the .text section that will need to be modified when the linker combines this object file with others. In general, any instruction that calls an external function or references a global variable will need to be modified.
.rel.data	Relocation information for any global variables that are referenced or defined by the module.
.debug	A debugging symbol table with entries for local variables and typedefs defined in the program, global variables defined and referenced in the program, and the original C source file.
.line	A mapping between line numbers in the original C source program and machine code instructions in the .text section.
.strtab	A string table for the symbol tables in the .symtab and .debug sections, and for the section names in the section headers.

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

下面逐步来看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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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.o
 
main.o:     file format pe-x86-64
 
 
Disassembly 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

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

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
1
2
3
4
5
6
7
8
9

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.o
 
main.o:     file format elf64-x86-64
 
Disassembly 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     
1
2
3
4
5
6
7
8
9
10
11
12
13

《程序员的自我修养—链接、装载与库》：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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)
1
2
3
4

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;
1
2
3
4
5
6
7
8
9

模块（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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

通过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
  ...
1
2
3
4
5
6
7
8
9
10
11

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

同名符号导致的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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这种问题在大型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
1
2
3
4

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

下面就开始制作我们的第一个静态链接库。首先用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.o
 
 
multvec.o:     file format pe-x86-64
rw-rwxr-- 1001/513    788 May 22 09:20 2015 multvec.o
1
2
3
4
5
6
7
8
9

查看符号表发现没有符号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>:
   ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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
1
2
3
4

因为扫描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
1
2

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;
1
2
3
4
5

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);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.o
 
main.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 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.o
 
Relocation section '.rel.text' at offset 0x320 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000012  00000902 R_386_PC32        00000000   swap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

回忆一下：关于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 p
 
Symbol 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

对上面的算法做了些详细解释，终于理解了 相对地址重定位的本质就是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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

查看可执行文件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>:
 ... 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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   bufp1
 
Relocation section '.rel.data' at offset 0x3a4 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000000  00000801 R_386_32          00000000   buf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

• 行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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17