链接
- 静态链接
- 加载时对共享库的动态链接
- 运行时对共享库的动态链接
哪些链接问题会影响程序的性能和正确性？
系统：X86-64
文件格式：ELF对象文件格式
关键词
共享库 动态链接
什么是链接？
将许多代码段和数据段收集起来，组合成一个文件，这个文件可被加载或者复制到内存中，可被执行；
画外音：
链接的输入是代码段和数据段
链接的输出是可执行对象文件
链接发生在什么时候？
编译期，即源代码被转换成机器码时；
加载时，即程序被加载进内存，被加载器执行时；
运行时；
由谁来做链接这件事？
早期手动来做；
现在由链接器程序静默来做；
为什么要使用链接器？
链接器支持单独编译；
在软件开发中，经常将一个大型应用分解为较小的、更易于管理的模块。有了单独编译后，就可以实现：当有一个模块被修改时，只用重新编译这个模块，并重新链接应用即可，不用重新编译其他模块；
问题：
链接器是怎样解析引用？
什么是类库？
链接器是怎样使用类库来解析引用？
Linux链接器在解析符号引用时会做哪些决策？
什么是动态链接？什么是共享库？为什么要有共享库？共享库和动态链接有哪些应用实例？
为什么要学习链接？
- 理解链接器对构建大型应用有好处。
构建大型应用经常会碰到链接器错误，这些错误发生的原因有：模块缺失、类库缺失、类库版本不兼容等。除非理解了链接器是怎样解析引用、什么是类库、链接器是怎样使用类库来解析引用等原理，这类错误经常令人困惑和沮丧。 - 理解链接器可以减少严重编程错误的出现频率。
Linux链接器在解析符号引用时所作的决策会静默地影响程序的正确性。比如，在默认情况系下，如果错误地定义了多个全局变量，链接器是不会报错的。但是生成的程序会表现出令人困惑的行为，且这种程序是很难调试的。需要学习了解这种情形是怎样发生的，知道这种情形该如何避免。 - 理解链接过程有助于理解编程语言的作用域规则是如何实现的。
比如，全局变量和局部变量有什么区别？当定义了静态变量或者静态函数时，到底会意味着什么？等等 - 理解链接过程有助于理解其他重要的系统概念。
由链接器生成的可执行对象文件许多重要系统功能中发挥着关键作用，比如程序加载、程序运行、虚拟内存、内存映射等； - 理解链接有助于使用共享库。
多年来，链接被认为是相当直接和无趣的。然而，随着共享库和动态链接在现代操作系统中的重要性越来越高，链接是一个复杂的过程，它为有知识的程序员提供了强大的功能。例如，许多软件产品在运行时使用共享库来升级压缩打包的二进制文件。此外，许多web服务器依赖于共享库的动态链接来提供动态内容。
编译器驱动
gcc -v -Og -o prog main.c sum.c
gcc -Og -o prog main.c sum.c
cpp sum.c /tmp/sum.i
cpp main.c /tmp/main.i
cc1 /tmp/sum.i -Og -o /tmp/sum.s
cc1 /tmp/main.i -Og -o /tmp/main.s
as -o /tmp/main.o /tmp/main.s
as -o /tmp/sum.o /tmp/sum.s
ld -o prog /tmp/main.o /tmp/sum.o
关键词 编译系统 编译器驱动程序 语言预处理器 编译器 汇编器 链接器
大部分编译系统都提供了编译器驱动程序，根据用户的需要，调用语言预处理器、编译器、汇编器、链接器等
比如，在GNU编译系统中，gcc就是编译器驱动程序
静态编译
gcc -g -c sum.c
gcc -g -c main.c
objdump -d -M intel -S sum.o
objdump -d -M intel -S main.o
静态链接器，比如ld
- 输入
可重定位目标文件命令行参数 - 输出
链接好的可执行目标文件
可重定位目标文件
由代码段和数据段组成；
每个段都是连续的字节序列；
指令在一个节中，初始化的全局变量在另一个节中，未初始化的变量在另一个节中；
在构建可执行目标文件的过程中，链接器的两个主要任务：
符号解析
目标文件(.o)定义和引用了符号；
每个符号对应着一个函数、一个全局变量、一个静态变量等；
符号解析的作用就是给每个符号引用分配一个精确的符号定义；重定位
编译器和汇编器生成的代码段和数据段的开始地址都是0；
链接器给每个符号定义分配一个内存地址，然后修改所有对这些符号的引用，使得这些引用指向的是前面分配的内存地址；
链接器使用由汇编器生成的详细的指令(重定位条目)来执行这些重定位操作；
基本事实
目标文件只是字节块组成的集合而已；
这些块中的一些包含程序代码；
另一些块包含程序数据；
其他块包含指导链接器和加载器的数据结构；
链接器将这些块拼接在一起，生成这些拼接块的运行时位置，修改在代码块和数据块中的位置信息；
链接器对目标机器的了解是最少的，编译器和汇编器是了解最多的；
目标文件
目标共有3种形式
- 可重定位目标文件
以某种格式保存代码和数据；
在编译时，可跟其他重定位目标文件一起组合，生成可执行目标文件； - 可执行目标文件
以某种格式保存代码和数据；
可被直接加载进内存，并执行； - 共享目标文件
一种特殊的重定位目标文件；
可在加载时或者运行时，被加载进内存并动态链接；
编译器和汇编器生成重定位文件；
链接器生成可执行目标文件；
目标文件格式
Windows系统使用Portable Executbale文件格式；
Linux使用ELF文件格式；
Mac系统使用Mach-O文件格式；
重定位目标文件
目标文件为什么要区分已被初始化的变量和未被初始化的变量？
- 提高空间效率：未被初始化的变量没必要占据任何实际的硬盘空间；
在运行时，这些变量会在内存中分配空间，并初始化为0；
ELF header
- 以16字节序列开头，描述了生成这个目标文件的系统的字大小及字节序(大端还是小端);
- 其余部分包含允许链接器解析和解释对象文件的信息，比如ELF header的大小、目标文件类型(relocatable/executable/shared)、节头表的偏移量、节头表的大小和条目数；
节头表(section header table)
- 所有节的位置信息和大小信息；
- 每个节在节头表里都有一个大小固定的条目；
节(section)
.text
保存的是编译后的程序机器码.rodata
保存的是只读数据，比如printf语句中的格式化字符串，用于stwich语句的jump table等；.data
保存的是被初始化的全局变量和静态变量；
局部变量被保存在运行时栈中，所以既不会出现在.data段，也不会出现在.bss段；.bss
全称为Better Save Space；
保存的是未被初始化额全局变量和静态变量，及被初始化为0的初始变量；
在目标文件中不占据实际空间；.systab
符号表；
保存的是在程序中定义或者引用的函数、全局变量；
每个重定位文件都有一份符号表systab；
跟编译器中的符号表相比，这里的.symtab符号表里不包括局部变量符号；.rel.text
保存的是.text节(指令里)中需要重新修改的位置信息；
任何一个调用外部函数或者引用全局变量的指令的位置信息都需要被修改；
调用局部函数的指令的位置信息不需要修改；
在可执行目标文件中，不需要重定位信息，通常是被忽略的，除非指令显式地告知链接器要保存它；.rel.data
保存的是在这个目标文件里定义或者引用的任何全局变量的重定位信息；
任何一个初始化值是全局变量地址或者在外部定义的函数地址的全局变量都需要别重新定位；.debug
调试信息表，条目保存的是在程序中定义的局部变量或者通过typedef定义的变量、在程序中定义或者引用的全局变量、源代码文件等；
只有编译器驱动程序使用了-g选项，才会出现的；.line
保存的是源代码中的行数到.text中的机器指令的映射关系；
只有编译器驱动程序使用了-g选项，才会出现的；.strtab
保存的是在.symtab节和.debug节中的符号表中的字符串，及在节头表中定义的节名字的字符串；
是由以null结尾的字符序列；
符号与符号表
链接器只关心
- 全局变量
非静态全局变量(初始化.data与未初始化COMMON)、静态全局变量(初始化.data与未初始化.bss) - 函数
非静态函数(.text)、静态函数(.text)
不关心
- 局部、非静态变量
为什么链接器不关心程序中定义的局部、非静态变量？
这些变量是由运行时栈来管理的；
从链接器的角度看，有三类符号：
由目标文件
m定义的，可被其他文件引用的全局符号
比如在目标文件m中定义的非静态函数及非静态全局变量，没有使用static修饰符等；由目标文件
m引用的，但定义在其他文件中的全局符号
比如extern修饰符，对应的是定义在其他文件中的非静态函数及全局变量，没有使用static修饰符；由目标文件
m私有定义或者引用的局部符号
比如在文件m中定义的静态函数、静态全局变量，使用了static修饰符；
这些符号对于文件m是可见的，但是不能被其他文件引用；
局部链接器符号跟程序中的局部变量不一样，在.systab中，不保存任何是局部的、非静态的变量；这些变量是由运行时栈来管理的，链接器并不关心；
画外音
符号表中只保存上述三类符号：两类全局符号和一类局部符号，不保存局部的非静态变量；
在C语言中使用static定义的局部函数变量，并不是由运行时栈管理；
编译器为每个这样的变量在.bss或者.data上分配空间；
在符号表创建一个拥有唯一名字的局部链接器符号；
比如
int f()
{
static int x = 0;
return x;
}
int g()
{
static int x = 1;
return x;
}
编译器会将有两个不同名字的一对局部链接器符号导出给汇编器，比如在函数f的定义中使用x.1，在函数g的定义中使用x.2；
汇编器符号表是由汇编器生成的，使用的是由符号表导出的.s文件；
ELF符号表是被保存在目标文件的.systab节中的；
编程小建议
C程序员使用
static修饰符将变量和函数声明隐藏在模块中，就像在Java和c++中使用public和private声明一样。在C语言中，源文件扮演着模块的角色。使用static修饰符声明的任何全局变量或函数对该模块都是私有的。同理，任何没有静态属性声明的全局变量或函数都是公共的，可以被任何其他模块访问。尽可能使用static修饰符保护变量和函数是很好的编程实践。
ELF符号表
条目格式
name字段：
记录的是该符号的字符串名称在string table中的字节索引；value字段：
记录的是改符号的地址；
对于重定位文件，记录的是从定义该符号的节开始位置的偏移量；
对于可执行文件，记录的是该符号的运行时绝对地址；size字段
记录的是该符号的大小，单位是字节；type字段
有5种：FUNC、OBJECT、SECTION、FILE、NOTYPE；section字段
记录的是该符号被分配给的节在节头表中的索引；每个符号都被分配给了某个节；
符号表里也包含有关各个节的条目，有关源代码路径名的条目；binding字段
标记该符号是局部的还是全局的；
有三类特殊的伪节，在节头表中没有对应的条目：
-
ABS
记录的是不应该被重定位的符号，比如源文件的路径名等； -
UNDEF
记录的是待定的符号，即在该目标文件中被引用，但却在其他地方定义的符号，比如使用extern修饰符； -
COMMON
记录的是没被初始化且未分配空间的数据对象，即未被初始化的全局变量，这类全局变量没有使用static修饰符；
这类符号对象的value字段记录的是补齐要求，size字段给出的是最小值；
画外音：
伪节只存在于重定位目标文件，在可执行目标文件中不存在；
伪节COMMON与真节.bss的区别
伪节
COMMON记录的是未被初始化的全局变量，这类全局变量没有使用static修饰符，是公共的，可被其他文件访问；真节
.bss记录的是未被初始化的静态变量、静态全局变量、被初始化为0的静态变量，这类变量使用了static修饰符，对于该文件是私有的，其他文件是不能访问的；
工具：readelf
#查看源代码main.c
cat main.c
int sum(int *a, int n);
int array[2] = {1,2};
int main()
{
int val = sum(array, 2);
return val;
}
#查看重定位目标文件`main.o`的符号表条目
readelf -s 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 7
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 15
12: 0000000000000000 0 SECTION LOCAL DEFAULT 13
13: 0000000000000000 8 OBJECT GLOBAL DEFAULT 3 array
14: 0000000000000000 33 FUNC GLOBAL DEFAULT 1 main
15: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND _GLOBAL_OFFSET_TABLE_
16: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND sum
#查看源代码sum.c
cat sum.c
int sum(int *a, int n)
{
int i, s = 0;
for(int i=0;i<n;i++){
s += a[i];
}
return s;
}
#查看重定位目标文件`sum.o`的符号表条目
readelf -s sum.o
Symbol table '.symtab' contains 14 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS sum.c
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 2
4: 0000000000000000 0 SECTION LOCAL DEFAULT 3
5: 0000000000000000 0 SECTION LOCAL DEFAULT 4
6: 0000000000000000 0 SECTION LOCAL DEFAULT 6
7: 0000000000000000 0 SECTION LOCAL DEFAULT 7
8: 0000000000000000 0 SECTION LOCAL DEFAULT 9
9: 0000000000000000 0 SECTION LOCAL DEFAULT 11
10: 0000000000000000 0 SECTION LOCAL DEFAULT 13
11: 0000000000000000 0 SECTION LOCAL DEFAULT 14
12: 0000000000000000 0 SECTION LOCAL DEFAULT 12
13: 0000000000000000 69 FUNC GLOBAL DEFAULT 1 sum
#问题7.1
gcc -g -c swap.c
gcc -g -c m.c
readelf -s 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 4
5: 0000000000000000 0 SECTION LOCAL DEFAULT 5
6: 0000000000000000 0 SECTION LOCAL DEFAULT 7
7: 0000000000000000 0 SECTION LOCAL DEFAULT 9
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 8 OBJECT GLOBAL DEFAULT 5 bufp0
15: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND buf
16: 0000000000000008 8 OBJECT GLOBAL DEFAULT COM bufp1
17: 0000000000000000 63 FUNC GLOBAL DEFAULT 1 swap
符号解析
gcc -Wall -Og -o linkerror linkerror.c
链接器解析符号的方法是
将每个引用与输入的重定位对象文件的符号表中的一个符号定义关联起来
画外音
一个引用对应一个符号定义
有两类类符号解析
- 本地符号解析
- 全局符号解析
链接器
- 输入是重定位目标文件
- 输出是可执行目标文件
如何解析local symbols？
根据编译器规则：
(1) 编译器保证每个本地符号只有一个定义;
(2) 编译器保证静态局部变量都有唯一的名字；
可知，每个local sysmbol必存在一个符号定义。
如何解析global symbols？
当编译器遇到一个没在当前文件中定义的符号时，编译器会假设该符号在某个其他模块中定义，生成一个链接器符号表条目，将其留给链接器来处理；
如果链接器没能给输入的多个重定位对象文件里的任何一个被引用符号找到一个定义，则链接器会打印一条错误信息，并退出；
由于多个对象文件可能会定义有相同名字的全局符号，所以链接器要么抛出一个错误信息，要么选择其中一个定义，丢掉其他定义；
Linux系统采取的方法需要编译器、汇编器、链接器的写作，因此会引入一些令人头疼的bug。
链接器是如何解析重复的符号名的？
链接器的输入是多个重定位目标文件。
每个文件都定义了一套符号，
有的是局部的，只有定义它的文件才可见；
有的是全局的，其它文件也可见；
如果多个文件定义了有相同名字的全局符号，Linux编译系统是怎么处理的？
编译器将每个全局符号导出给汇编器，要么是强类型，要么是弱类型；
汇编器将这份信息隐式地保存在重定位目标文件的符号表里：函数和已被初始化的全局变量是强类型符号，未初始化的全局变量是弱类型符号；
基于符号的强弱类型，Linux链接器使用3种规则来处理有重复名字的符号：
- 不允许强类型的符号重名；
- 假设有一个强类型的符号与一个弱类型的符号重名，则选择强类型；
- 如果多个弱类型的符号重名，则随便任选一个；
gcc foo1.c bar1.c
/tmp/ccuXKJck.o: In function `main':
bar1.c:(.text+0x0): multiple definition of `main'
/tmp/ccR0rP0B.o:foo1.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status
gcc foo2.c bar2.c
/tmp/ccLi7l5m.o:(.data+0x0): multiple definition of `x'
/tmp/cc6tPrGp.o:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status
gcc -o foobar3 foo3.c bar3.c
./foobar3
x = 15212
gcc -o foobar4 foo4.c bar4.c
./foobar4
x = 15212
gcc -Wall -Og -o foobar5 foo5.c bar5.c
/usr/bin/ld: Warning: alignment 4 of symbol `x' in /tmp/ccufwmiu.o is smaller than 8 in /tmp/ccylrZmQ.o
./foobar5
#-0.0=1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
x = 0x0 y= 0x80000000
gcc -Werror -Og -o foobar5 foo5.c bar5.c
gcc -fno-common -Og -o foobar5 foo5.c bar5.c
/tmp/ccliRs14.o:(.bss+0x0): multiple definition of `x'
/tmp/ccFc8lU9.o:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status
如何链接静态类库
关键词 静态类库机制
当输入是静态类库时，链接器只复制静态类库中被应用程序引用的目标文件。
静态类库解决了什么问题？
- 编译器开发者
避免新增、删除或者修改一个标准函数需要重新编译一个新版本的编译器的麻烦； - 类库开发者
避免了对标准函数的小修改需要编译整个源文件的麻烦； - 应用开发者来说，
避免了显式地引用许多重定位目标文件的麻烦 - 应用程序来说，
避免了磁盘空间和内存空间的浪费
为什么支持静态类库机制？
- 类库开发者只需将相关的函数编译成单独的目标文件，并打包成一个静态类库文件；
- 应用程序员可以使用在类库中的任何一个函数，只需在命令行上显式地写出需要链接的文件名即可；
- 在链接时，链接器只拷贝被这个程序使用的目标文件，应用程序员需要显式链接的文件名是较少的；
ISO C99在静态类库libc.a中定义了大量的标准I/O函数、字符串操作函数、整数数学函数等，比如atoi、printf、scanf、strcpy、rand等。
ISO C99也在静态类库libm.a中定义了大量的浮点数学函数，比如sin、cos、sqrt等。
思路是考虑要是没有静态类库机制，编译器开发者会采取什么样的方法来为使用者提供上述函数。
方法一：
让编译器识别出所有对标准函数的调用，直接生成合适的代码。
两个角度：编译器开发者和应用开发者
比如，由于只提供了少量的标准函数，Pascal可以采用这种方法；
但是对于C语言来说是不灵活的，由于C语言提供了大量的标准函数。如果C语言采取这种方法，则会给编译器增加很大的复杂性，比如每次添加、删除或者修改一个函数时，都要重新一个新版本的编译器。
对应用开发者来说，这种方法非常方便，因为标准函数都是可用的。
方法二：
将C语言所有的标准函数放进一个重定位目标文件，比如libc.o。
应用程序员可以使用下面的指令将其链接到相应的可执行文件中：
gcc main.c /usr/lib/libc.o
这种方法的优势是将标准库函数的实现跟编译器的实现分离开，且对程序员来说也是很方便的；
这种方法的缺点是
- 每个可执行文件都需要一份完整的标准函数的拷贝(
libc.a大约5MB，libm.a大约2MB)，很浪费磁盘空间；这会导致每个运行的程序都在内存中各自有一份对标准函数的完整拷贝，很浪费内存空间； - 对任何一个标准函数的修改，无论多么小，都需要类库开发者重新编译整个源文件，这是一个耗时的操作，会增加开发的复杂度和标准函数的可维护性；
方法三：为每个标准函数单独创建一份重定位文件，将这些文件存放在约定好的目录。
缺点是
- 需要应用开发者显式地将相应的目标文件链接到可执行文件中，这个过程是非常耗时且容易出错的，比如
gcc main.c /usr/lib/printf.o /user/lib/scanf.o ...
方法四：静态类库
只将相关的函数编译成单独的目标文件，并打包成一个静态类库文件。
应用程序员可以使用在类库中的任何一个函数，只需在命令行上显式地写出一个文件名。
比如，一个需要使用C标准库和数学类库中的函数的程序，可以使用如下方式被编译和链接：
gcc main.c /usr/lib/libm.a /usr/lib/libc.a
在链接时，链接器只拷贝被这个程序使用的目标文件，这样就减小了可执行文件在磁盘上和内存中的大小；
应用程序员只用包括几个类库文件的名字就好了，比如C编译器驱动通常将libc.a传递给链接器，所以之前对libc.a的引用也是没有必要的；
archive文件格式
- header
描述了每个目标文件的大小和地址； - 由许多重定位目标文件拼接组成；
- 文件名后缀是
.a；
在Linux系统中，静态类库是以archive文件格式存储在磁盘上的。
静态库链接实例
#addvec.c
int addcnt = 0;
void addvec(int *x, int *y,
int *z, int n)
{
int i;
addcnt++;
for(i=0;i<n;i++)
z[i] = x[i] + y[i];
}
#multvec.c
int multcnt = 0;
void multvec(int *x, int *y,
int *z, int n)
{
int i;
multcnt++;
for(i=0;i<n;i++)
z[i] = x[i] * y[i];
}
#编译静态类库libvector.a
gcc -c addvec.c multvec.c
ar rcs libvector.a addvec.o multvec.o
#编译可执行文件prog2c
gcc -c main2.c
gcc -static -o prog2c main2.o ./libvector.a
如何使用静态类库来解析引用？
在符号解析阶段，链接器会按照在命令行上出现的顺序，从左向右，扫描所有重定位目标文件和归档文件；
在扫描过程中，链接器会维护
一个集合E：存储的是将被合并进可执行文件的重定位目标文件；
一个集合U：存储的是未被解析的符号，即被引用了但还没找到定义的符号；
一个集合D：存储的是在之前的输入文件中已被解析的符号；
初始时，三个集合都是空的
- 对命令行上出现的每个输入文件
f，链接器首先判断其的类型，是目标文件还是存档文件。如果是目标文件，则将其加入到集合E，更新集合U和集合D，反映出文件f中的符号定义和引用，接着处理下一个输入文件； - 如果
f是存档文件，链接器会对存档文件中的每个成员文件m进行迭代，并执行如下过程：尝试给在集合U中的未解析的符号匹配由该存档文件的成员目标文件定义的符号。如果某个存档成员目标文件m定义了一个符号，且该符号解析了在集合U中的一个引用，则将m加入到集合E中，更新集合U和集合D，反映成员m中的符号定义和引用。这个过程会一直执行，直到某个点，集合U和集合D不再发生变化。在这个时候，可以丢弃任何一个没有包含在集合E中的成员目标文件，链接器接着处理下一个输入文件； - 当链接器完成对命令行上的所有输入文件的扫描时，如果集合U还是非空的，则链接器就会报链接错误，并退出；否则，链接器就合并和重定位在集合
E中的所有目标文件，并生成可执行文件；
注意
由于静态类库、重定位文件在命令行上的出现次序很重要，上述算法会导致一些令人困惑的链接时错误。
如果在静态类库中定义了一个符号，但是该类库文件出现在引用该符号的目标文件之前，则该引用就不会被解析，就会报链接错误。
比如
gcc -static ./libvector.a main2.c
/tmp/ccrpOPSR.o: In function `main':
main2.c:(.text+0x1f): undefined reference to `addvec'
collect2: error: ld returned 1 exit status
使用静态类库的一般规则
- 将静态类库放在命令行的末尾
如果不用静态类库的成员目标文件是独立的，即不存在一个成员会引用一个定义在另一个成员里的符号，则类库可以被任意的顺序放在命令行的末尾；
如果静态类库之间不是独立的，则它们必须按照这样的顺序排列：如果某个存档文件中的成员目标文件里extern引用了符号s，则定义s的文件要排在引用s的文件之后；
比如，foo.c调用了在libx.a和libz.a中的函数，libx.a和libz.a中都调用了在liby.a中的函数，则libx.a和libz.a必须排在liby.a之前，即
gcc foo.c libx.z libz.a liby.a
- 在命令行上的静态类库可以根据需要重复出现
比如foo.c调用了在libx.a中的函数，libx.z中调用了liby.a中的函数，liby.a中的函数调用了libx.a中的函数，则libx.a就必须在命令行上重复，即
gcc foo.c libx.a liby.a libx.a
实例
# p.o->libx.a
gcc p.o libx.a
# p.o->libx.a->liby.a
gcc p.o libx.a liby.a
# p.o->libx.a->liby.a and liby.a->libx.a->p.o
gcc p.o libx.a liby.a libx.a
详细解释：
详细解释：
当链接器解析p.o后，
集合E：P
集合U: P中所有extern引用`libx.a`中的全局符号
集合D: P中所有局部符号和可被其他文件引用的全局符号；
当链接器解析`libx.a`后，
集合E：P+`libx.a`中定义了P里外部引用全局符号的文件
集合U：`libx.a`中所有extern引用`liby.a`中的全局符号
集合D: P中所有符号+`libx.a`中定义了P里外部引用全局符号的文件中的所有局部符号及可被其他文件引用的全局符号
当链接器解析`liby.a`后，
集合E：P+`libx.a`中定义了P里外部引用全局符号的文件+`liby.a`中定义了`libx.a`里外部引用全局符号的文件；
集合U：`liby.a`中所有extern引用`libx.a`中的全局符号
集合D: P中所有符号+`libx.a`中定义了P里外部引用全局符号的文件中的所有符号+`liby.a`中定义了`libx.a`里外部引用全局符号的文件中的所有局部符号及可被其他文件引用的全局符号
当链接器解析`liby.a`后，
集合E：P+`libx.a`中定义了P里外部引用全局符号的文件+`liby.a`中定义了`libx.a`里外部引用全局符号的文件；
集合U：空
集合D: P中所有符号+`libx.a`中定义了P里外部引用全局符号的文件中的所有符号+`liby.a`中定义了`libx.a`里外部引用全局符号的文件中的所有符号
重定位
当链接器完成符号解析后，链接器就给代码中的符号引用精确关联了一个符号定义，即链接器的某个输入目标文件中的一个符号表条目。
这时，链接器知道它的输入目标文件的代码节和数据节的精确大小；
接下来，链接器就要执行重定位了。
重定位做了哪些事？
总体上就是合并输入目标文件，给每个符号分配一个运行时地址。可分为两步：
- 重定位节和符号定义
链接器首先将相同类型的节合并，生成同类型的聚合节，比如将来自所有输入文件的.data节合并成可执行文件的.data节；
接着，给新的聚合节、在输入文件中定义的每个节即每个符号等分配运行时内存地址；
最后，在程序里的每个指令、全局变量都有唯一的运行时地址； - 重定位节内部的符号引用
链接器修改在代码体及数据节中的每个符号引用，使得其指向正确的运行时地址；
这一步需要依赖重定位条目这一数据结构；
重定位条目
当汇编器生成目标文件时，汇编器不仅不知道代码和数据在内存中的最终地址的，也不知道这个目标文件引用的外部定义的函数或者全局变量的地址；
每当汇编器遇到一个对最终地址未知的对象的引用时，汇编器就生成一个重定位条目，这个条目告诉链接器：当链接器合并这个目标文件形成可执行文件时，该如何修改这个引用；
代码中的重定位条目放在rel.text中；
数据中的重定位条目放在rel.data中；
有两类最基本的重定位数据类型
- R_X84-64_PC32
- R_X84-64_32
什么是32位PC-relative地址？
A PC-relative address is an offset from the current run-time value of the program counter (PC).When the CPU executes an instruction using PC-relative addressing, it forms the effective address (e.g., the target of the call instruction) by adding the 32-bit value encoded in the instruction to the current run-time value of the PC, which is always the address of the next instruction in memory.
什么是32位绝对地址？
With absolute addressing, the CPU directly uses the 32-bit value encoded in the instruction as the effective address, without further modifications.
重定位符号引用
#重定位条目的数据结构
typedef struct {
long offset; /* Offset of the reference to relocate */
long type:32, /* Relocation type */
symbol:32; /* Symbol table index */
long addend; /* Constant part of relocation expression */
} Elf64_Rela;
- `offset`
待修正的引用的节偏移量；
- `symbol`
待修正的引用应该指向的符号；
- `type`
告诉链接器该如何修正新的引用；
- `addend`
有符号的常数；
被某些类型的重定位用于偏置待修正引用；
#链接器的重定位算法
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_X86_64_PC32) {
refaddr = ADDR(s) + r.offset; /* ref’s run-time address */
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
}
/* Relocate an absolute reference */
if (r.type == R_X86_64_32)
*refptr = (unsigned) (ADDR(r.symbol) + r.addend);
}
}
实例 main.c+sum.c
gcc -g -c main.c sum.c
gcc -Og -o prog main.c sum.c
###############################重定位文件部分##################################
#查看main.o中的.text节
Disassembly of section .text:
0000000000000000 <main>:
objdump: Warning: source file /mnt/e/MyProject/CppProject/CAPP_3e/chapter7/main.c is more recent than object file
int sum(int *a, int n);
int array[2] = {1,2};
int main()
{
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 10 sub $0x10,%rsp
int val = sum(array, 2);
8: be 02 00 00 00 mov $0x2,%esi
d: 48 8d 3d 00 00 00 00 lea 0x0(%rip),%rdi # 14 <main+0x14>
14: e8 00 00 00 00 callq 19 <main+0x19>
19: 89 45 fc mov %eax,-0x4(%rbp)
return val;
1c: 8b 45 fc mov -0x4(%rbp),%eax
1f: c9 leaveq
20: c3 retq
#查看main.o中的.data节
objdump -j .data -S main.o
Disassembly of section .data:
0000000000000000 <array>:
int array[2] = {1,2};
0: 01 00 00 00 02 00 00 00
#查看main.o中的重定位节
readelf -r main.o
Relocation section '.rela.text' at offset 0x4a8 contains 2 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000000010 000d00000002 R_X86_64_PC32 0000000000000000 array - 4
000000000015 001000000004 R_X86_64_PLT32 0000000000000000 sum - 4
###############################可执行文件部分##################################
#查看prog的代码节
objdump -j .text -S prog
00000000000005fa <main>:
5fa: 48 83 ec 08 sub $0x8,%rsp
5fe: be 02 00 00 00 mov $0x2,%esi
603: 48 8d 3d 06 0a 20 00 lea 0x200a06(%rip),%rdi # 201010 <array>
60a: e8 05 00 00 00 callq 614 <sum>
60f: 48 83 c4 08 add $0x8,%rsp
613: c3 retq
0000000000000614 <sum>:
614: ba 00 00 00 00 mov $0x0,%edx
619: b8 00 00 00 00 mov $0x0,%eax
61e: eb 09 jmp 629 <sum+0x15>
620: 48 63 ca movslq %edx,%rcx
623: 03 04 8f add (%rdi,%rcx,4),%eax
626: 83 c2 01 add $0x1,%edx
629: 39 f2 cmp %esi,%edx
62b: 7c f3 jl 620 <sum+0xc>
62d: f3 c3 repz retq
62f: 90 nop
#查看prog的数据节
objdump -j .data prog
Disassembly of section .data:
0000000000201010 <array>:
201010: 01 00 00 00 02 00 00 00
#查看prog所有节内容
objdump -d -M intel -S prog
prog: file format elf64-x86-64
Disassembly of section .init:
00000000000004b8 <_init>:
4b8: 48 83 ec 08 sub rsp,0x8
4bc: 48 8b 05 25 0b 20 00 mov rax,QWORD PTR [rip+0x200b25] # 200fe8 <__gmon_start__>
4c3: 48 85 c0 test rax,rax
4c6: 74 02 je 4ca <_init+0x12>
4c8: ff d0 call rax
4ca: 48 83 c4 08 add rsp,0x8
4ce: c3 ret
Disassembly of section .plt:
00000000000004d0 <.plt>:
4d0: ff 35 f2 0a 20 00 push QWORD PTR [rip+0x200af2] # 200fc8 <_GLOBAL_OFFSET_TABLE_+0x8>
4d6: ff 25 f4 0a 20 00 jmp QWORD PTR [rip+0x200af4] # 200fd0 <_GLOBAL_OFFSET_TABLE_+0x10>
4dc: 0f 1f 40 00 nop DWORD PTR [rax+0x0]
Disassembly of section .plt.got:
00000000000004e0 <__cxa_finalize@plt>:
4e0: ff 25 12 0b 20 00 jmp QWORD PTR [rip+0x200b12] # 200ff8 <__cxa_finalize@GLIBC_2.2.5>
4e6: 66 90 xchg ax,ax
Disassembly of section .text:
00000000000004f0 <_start>:
4f0: 31 ed xor ebp,ebp
4f2: 49 89 d1 mov r9,rdx
4f5: 5e pop rsi
4f6: 48 89 e2 mov rdx,rsp
4f9: 48 83 e4 f0 and rsp,0xfffffffffffffff0
4fd: 50 push rax
4fe: 54 push rsp
4ff: 4c 8d 05 9a 01 00 00 lea r8,[rip+0x19a] # 6a0 <__libc_csu_fini>
506: 48 8d 0d 23 01 00 00 lea rcx,[rip+0x123] # 630 <__libc_csu_init>
50d: 48 8d 3d e6 00 00 00 lea rdi,[rip+0xe6] # 5fa <main>
514: ff 15 c6 0a 20 00 call QWORD PTR [rip+0x200ac6] # 200fe0 <__libc_start_main@GLIBC_2.2.5>
51a: f4 hlt
51b: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
0000000000000520 <deregister_tm_clones>:
520: 48 8d 3d f1 0a 20 00 lea rdi,[rip+0x200af1] # 201018 <__TMC_END__>
527: 55 push rbp
528: 48 8d 05 e9 0a 20 00 lea rax,[rip+0x200ae9] # 201018 <__TMC_END__>
52f: 48 39 f8 cmp rax,rdi
532: 48 89 e5 mov rbp,rsp
535: 74 19 je 550 <deregister_tm_clones+0x30>
537: 48 8b 05 9a 0a 20 00 mov rax,QWORD PTR [rip+0x200a9a] # 200fd8 <_ITM_deregisterTMCloneTable>
53e: 48 85 c0 test rax,rax
541: 74 0d je 550 <deregister_tm_clones+0x30>
543: 5d pop rbp
544: ff e0 jmp rax
546: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
54d: 00 00 00
550: 5d pop rbp
551: c3 ret
552: 0f 1f 40 00 nop DWORD PTR [rax+0x0]
556: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
55d: 00 00 00
0000000000000560 <register_tm_clones>:
560: 48 8d 3d b1 0a 20 00 lea rdi,[rip+0x200ab1] # 201018 <__TMC_END__>
567: 48 8d 35 aa 0a 20 00 lea rsi,[rip+0x200aaa] # 201018 <__TMC_END__>
56e: 55 push rbp
56f: 48 29 fe sub rsi,rdi
572: 48 89 e5 mov rbp,rsp
575: 48 c1 fe 03 sar rsi,0x3
579: 48 89 f0 mov rax,rsi
57c: 48 c1 e8 3f shr rax,0x3f
580: 48 01 c6 add rsi,rax
583: 48 d1 fe sar rsi,1
586: 74 18 je 5a0 <register_tm_clones+0x40>
588: 48 8b 05 61 0a 20 00 mov rax,QWORD PTR [rip+0x200a61] # 200ff0 <_ITM_registerTMCloneTable>
58f: 48 85 c0 test rax,rax
592: 74 0c je 5a0 <register_tm_clones+0x40>
594: 5d pop rbp
595: ff e0 jmp rax
597: 66 0f 1f 84 00 00 00 nop WORD PTR [rax+rax*1+0x0]
59e: 00 00
5a0: 5d pop rbp
5a1: c3 ret
5a2: 0f 1f 40 00 nop DWORD PTR [rax+0x0]
5a6: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
5ad: 00 00 00
00000000000005b0 <__do_global_dtors_aux>:
5b0: 80 3d 61 0a 20 00 00 cmp BYTE PTR [rip+0x200a61],0x0 # 201018 <__TMC_END__>
5b7: 75 2f jne 5e8 <__do_global_dtors_aux+0x38>
5b9: 48 83 3d 37 0a 20 00 cmp QWORD PTR [rip+0x200a37],0x0 # 200ff8 <__cxa_finalize@GLIBC_2.2.5>
5c0: 00
5c1: 55 push rbp
5c2: 48 89 e5 mov rbp,rsp
5c5: 74 0c je 5d3 <__do_global_dtors_aux+0x23>
5c7: 48 8b 3d 3a 0a 20 00 mov rdi,QWORD PTR [rip+0x200a3a] # 201008 <__dso_handle>
5ce: e8 0d ff ff ff call 4e0 <__cxa_finalize@plt>
5d3: e8 48 ff ff ff call 520 <deregister_tm_clones>
5d8: c6 05 39 0a 20 00 01 mov BYTE PTR [rip+0x200a39],0x1 # 201018 <__TMC_END__>
5df: 5d pop rbp
5e0: c3 ret
5e1: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0]
5e8: f3 c3 repz ret
5ea: 66 0f 1f 44 00 00 nop WORD PTR [rax+rax*1+0x0]
00000000000005f0 <frame_dummy>:
5f0: 55 push rbp
5f1: 48 89 e5 mov rbp,rsp
5f4: 5d pop rbp
5f5: e9 66 ff ff ff jmp 560 <register_tm_clones>
00000000000005fa <main>:
5fa: 48 83 ec 08 sub rsp,0x8
5fe: be 02 00 00 00 mov esi,0x2
603: 48 8d 3d 06 0a 20 00 lea rdi,[rip+0x200a06] # 201010 <array>
60a: e8 05 00 00 00 call 614 <sum>
60f: 48 83 c4 08 add rsp,0x8
613: c3 ret
0000000000000614 <sum>:
614: ba 00 00 00 00 mov edx,0x0
619: b8 00 00 00 00 mov eax,0x0
61e: eb 09 jmp 629 <sum+0x15>
620: 48 63 ca movsxd rcx,edx
623: 03 04 8f add eax,DWORD PTR [rdi+rcx*4]
626: 83 c2 01 add edx,0x1
629: 39 f2 cmp edx,esi
62b: 7c f3 jl 620 <sum+0xc>
62d: f3 c3 repz ret
62f: 90 nop
0000000000000630 <__libc_csu_init>:
630: 41 57 push r15
632: 41 56 push r14
634: 49 89 d7 mov r15,rdx
637: 41 55 push r13
639: 41 54 push r12
63b: 4c 8d 25 ae 07 20 00 lea r12,[rip+0x2007ae] # 200df0 <__frame_dummy_init_array_entry>
642: 55 push rbp
643: 48 8d 2d ae 07 20 00 lea rbp,[rip+0x2007ae] # 200df8 <__init_array_end>
64a: 53 push rbx
64b: 41 89 fd mov r13d,edi
64e: 49 89 f6 mov r14,rsi
651: 4c 29 e5 sub rbp,r12
654: 48 83 ec 08 sub rsp,0x8
658: 48 c1 fd 03 sar rbp,0x3
65c: e8 57 fe ff ff call 4b8 <_init>
661: 48 85 ed test rbp,rbp
664: 74 20 je 686 <__libc_csu_init+0x56>
666: 31 db xor ebx,ebx
668: 0f 1f 84 00 00 00 00 nop DWORD PTR [rax+rax*1+0x0]
66f: 00
670: 4c 89 fa mov rdx,r15
673: 4c 89 f6 mov rsi,r14
676: 44 89 ef mov edi,r13d
679: 41 ff 14 dc call QWORD PTR [r12+rbx*8]
67d: 48 83 c3 01 add rbx,0x1
681: 48 39 dd cmp rbp,rbx
684: 75 ea jne 670 <__libc_csu_init+0x40>
686: 48 83 c4 08 add rsp,0x8
68a: 5b pop rbx
68b: 5d pop rbp
68c: 41 5c pop r12
68e: 41 5d pop r13
690: 41 5e pop r14
692: 41 5f pop r15
694: c3 ret
695: 90 nop
696: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0]
69d: 00 00 00
00000000000006a0 <__libc_csu_fini>:
6a0: f3 c3 repz ret
Disassembly of section .fini:
00000000000006a4 <_fini>:
6a4: 48 83 ec 08 sub rsp,0x8
6a8: 48 83 c4 08 add rsp,0x8
6ac: c3 ret
问题 7.4
已知:r.addend=-0x4,ADDR(sum)=0x4004e8,ADDR(.text)=0x4004d0,*refptr=0x5,
求:refptr
根据重定位算法有：
0x5=0x4004e8-0x4-(0x4004d0+r.offset)
从而:r.offset=oxf;
则refptr=ADDR(.text)+r.offset=0x4004df;
*refptr=0x5;
问题7.5
ox4004d9: e8 0a 00 00 00 callq 0x4004e8 <swap>
