链接是将各种代码和数据片段收集并组合成为一个单一文件的过程。链接是软件开发中的重要过程,其使得分离编译成为可能。即我们不用将一个大型的应用程序组织成为一个巨大的源文件,而是将其分解为更小、更好管理的模块,可以独立地修改和编译这些模块。不仅如此,我们还可以链接包含某些特定函数和功能的库文件,在前人的基础上进行深度开发,而不需要每个模块都亲历亲为。
0 链接的过程
本文主要阐述我在学习《深入理解计算机系统》关于链接部分的理解,并加以整理。首先我们看以下一个例子,有四个源文件,分别为主程序main.c,计算向量成员和的sum模块,和两个隶属于静态库的libvector.a的成员的源文件addvec.c和multvec.c。
1 |
|
主函数中,在完成各种定义及初始化后,首先计算出x和y向量的成员和,再求解x和y的向量和并赋值给z,最后将所有计算结果打印出来。
首先,在Linux环境下,通过gcc工具链将每个源文件生成可重定位目标文件(.o文件),生成可重定位目标文件的具体过程可以参考我的博客《C语言编译原理浅析》。
1 | $ gcc -c main.c sum.c addvec.c multvec.c |
然后,我们将addvec.o和multvec.o两个文件合并生成静态库文件libvector.a。
1 | $ ar rcs libvector.a addvec.o multvec.o |
最后,我们将链接整个这些文件生成可执行文件main,并输出打印结果。
1 | $ gcc -o main main.o sum.o ./libvector.a && ./main |
那么,在这个过程中,链接器生成可执行文件以及可执行文件执行时调用动态库的整个过程如下图所示。首先,汇编器生成可重定位目标文件(main.o、sum.o以及libvector.a中的addvec.o),然后,链接器对可重定位目标文件进行符号解析和重定位,并最终生成可执行文件。而对于动态库的链接,在创建可执行文件时,链接器复制一些重定位和符号表信息,在运行时,动态地完成链接过程。值得注意的是:动态链接时,没有任何的代码和数据杯复制到可执行文件中,在内存中,一个共享库的代码段的一个副本可以被不同的正在运行的进程共享。下面,我们将针对以上提到的对象和过程进行详细的叙述。
1 可重定位目标文件
目标文件一般指二进制文件。目标文件是按照特定的文件格式来组织的,各个系统的目标文件格式都不相同,Windows使用可移植可执行(Portable Executable,PE)格式,而现代x86-64Linux和Unix系统使用可执行可链接格式(Executable and Linkable Format,ELF)。
简单来说,可重定位目标文件就是源文件经过预处理、编译和汇编后生成的.o文件。典型的可重定位目标文件的格式如下图所示:
1.1 ELF头
ELF头以一个16字节的序列开始,这个序列描述了生成该文件的系统的字的大小和字节序列。在Linux下,查看可重定位目标文件的ELF头只需执行以下指令,即有:
1 | $ readelf -h main.o |
可以看到,Type目录显示为REL (Relocatable file),即可重定位目标文件。另外还可以看出,其文件格式是ELF64,小端,是x86系统的目标文件等,具体信息对应如下图:
而e_ident详见下图,有关ELF头的详细信息详细信息,可查看链接。
1.2 节(section)
典型的elf可重定位目标文件的节如前图所示,具体含义如下:
.text: 已编译程序的机器代码;
.rodata: 只读数据;
.data: 已经初始化的全局和静态变量;
.bss: 未初始化的全局和静态变量,其实实际不占据空间,仅仅是个占位符。这是为了空间效率,即在目标文件中不需要占据任何实际的磁盘空间,且等到运行时,依据符号表存储信息,从内存中分配这些变量;
注意:以上4个段会在程序运行时加入到内存中,是实实在在的程序段。目标文件中还有一些辅助程序进程链接和加载的信息,这些信息并不加载到内存中。实际上,这些信息在生成最终的可执行目标文件时就已经被去掉了。
.symtab: 一个符号表,存放程序中定义和引用的函数和全局变量信息;
.rel.text: 代码段中需要的重定位信息,当链接器把这个目标文件和其它文件组合时,需要修改这些定位信息;可执行目标文件中并不需要重定位信息,通常省略;
.rel.data: 数据段中需要的重定位信息,同上,当链接器工作时,都需要被修改……
节头部表是描述以上用于描述不同节的位置和大小等信息,具体可参照《深入理解计算机系统》。在Linux下输入以下指令,可查看节头部表。
1 | $ readelf -S main.o |
静态库实质上是一组可重定位目标文件的集合,即将由相关的可重定位目标文件打包成为一个单独的文件,在Linux下,文件名一般是libxxx.a,xxx为库名。也就是说,相关函数可以被编译成独立的目标模块,然后封装成一个单独的静态库文件,应用程序可以通过制定单独的名字来使用这些在库中定义的函数,且在构造可执行文件时,只复制静态库里被应用程序引用的引用的目标模块。可以在Linux下用readelf命令查看静态库文件,其会将可重定位目标文件成员平铺展示。
2 符号解析
由前可知,每个可重定位目标模块都有一个符号表,它包含该模块定义和引用的符号信息。符号解析就是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。
2.1 符号和符号表
符号表中有三种符号:
1)由本模块定义并能被其它模块引用的全局符号,对应于非静态C函数和全局变量;
2)由其它模块定义并被本模块引用的全局符号,也称外部符号,对应于其它模块定义的非静态C函数和全局变量;
3)只被本模块定义和引用的局部符号,对应于带static属性的C函数和全局变量(书中这么写的,但是我测试发现,static属性的局部变量也会存在表中,书中后续也提到了这些,应该是笔误)。
在Linux下,我们可以输入以下指令查看可重定位目标文件的节头部表和符号表。
1 | $ readelf -Ss main.o |
上方标注了“Section Headers”的为节头部表,下方标注了“Symbol table”的即为符号表,符号表各项条目是什么意思,可以查看书籍。下面着重分析一下main.o中有关变量和函数与符号表的对应关系。每个符号表都被分配到目标文件的某个节,即标中标注Ndx栏,该字段是一个到节头部表的索引,譬如x定义为全局变量,且已经初始化,按照前面的分析,应该在.data节,对应索引为3,正好就是节头部表的.data字段,而main函数理应是.text节,对应的索引是1,即节头部表的.text字段。查看上表可知,有三个特殊的伪节(只有可重定位目标文件中有,可执行目标文件没有),他们在节头部表中没有条目,分别是:
1)ABS:代表不该被重定位的符号;
2)UNDEF:代表未定义的符号,也就是本模块引用的其它模块定义的符号;
3)COMMON:未初始化的全局变量,其value字段给出对齐要求,size字段给出最小的大小;可以看到,这和.bss字段很相似,但是二者有以下区别:gcc将未初始化的全局变量分配到COMMON,将未初始化的静态变量以及初始化为0的全局或静态变量分配到.bss,至于为什么这么做,详见下一节。
可以看到,在上述符号表中,main.c属于不该重定位的符号,分配到ABS字段;sum、addvec和printf是外部定义的函数,属于外部符号,分配到UNDEF字段;而z属于未初始化的全局变量,被分配到COMMON字段;而y、s_x和s_y属于局部变量,不在符号表中体现。
2.2 多重定义的全局符号解析
对于那些和引用定义在相同模块中的局部符号的引用,符号解析是非常简单明了的,不过对于全局符号的引用解析就棘手的多。下面分析当多个模块定义同名的全局符号,链接器将如何处理。
在编译时,编译器向汇编器输出每个全局符号,会标记为强或者是弱,汇编器将这个信息隐含地编码在可重定位目标文件的符号表内。函数和已初始化的全局变量和强符号,未初始化的全局变量是弱符号。
根据强弱符号的定义,Linux链接器使用以下规则处理多重定义的符号名:
1)不允许有多个同名的强符号;
2)如果有一个强符号和多个弱符号同名,那么选择强符号;
3)如果有多个弱符号同名,那么可以从这些弱符号中任意选择一个;
这里就解释了2.1中为什么要将未初始化的全局变量分配到COMMON字段,当编译器在编译某个模块的时候,遇到一个弱全局变量符号,譬如上述例子中的在z,他并不知道其他模块也定义了z,也无法预测链接器应该使用z的多重定义中的哪一个,所以编译器将z分配给COMMON,把决定权留给链接器。而如果z初始化为0,则其是一个强符号,那么根据规则2必须是唯一的,所以编译器会很自信地将其分配给.bss。类似地,静态符号的构造必须是唯一的,所以编译器可以自信地将他们分配成.data或.bss。具体的例子,大家可以参考书本,介绍的很详细。
综上,我们在编程的时候应该极力避免出现重名的全局变量,这样有利于避免一些难以察觉的错误。
2.3 静态库解析引用
在Linux系统中,静态库以一种称为存档(archive)的特殊文件格式存放在磁盘上。存档文件是一组连续起来可用的可重定位目标文件的集合,有一个头部用来描述每个成员的目标文件大小和位置。
在符号解析阶段,链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件的和存档文件。在这次扫描中,链接器维护三个集合:
1)一个可重定位目标文件集合E,这个集合的文件会杯合并起来形成可执行文件;
2)一个未解析的符号(即引用但尚未定义的符号)集合U;
3)一个在前面输入文件中已定义的符号集合D;
初始时,三个集合均为空。而这次扫描的处理算法如下:
- 对于命令行上每个输入文件f,链接器会判断f是一个目标文件还是存档文件。如果f是一个目标文件,那么链接器把f添加到E,修改U和D来反映f中的符号定义和引用,并继续下一个输入文件。
- 如果f是一个存档文件,那么链接器就尝试匹配U中的未解析的符号和存档文件成员定义的符号。如果某个存档文件成员m,定义了一个符号来解析U中的一个引用,那么就将m添加到E中,并且链接器修改U和D来反映m中符号定义和引用。对存档文件中所有成员目标文件都依次进行这个过程,直到U和D都不在发生变化。此时,任何不包含在E中的成员目标文件都简单地被抛弃,而链接器将继续处理下一个输入文件。
- 如果当链接器完成对命令行上输入文件的扫描后,U是非空的,那么链接器就会输出一个错误并终止。否则,它会合并和重定位E中的目标文件,构建输出的可执行文件。
以上处理算法会导致一些令人困扰的链接错误,因为命令行上目标文件的顺序非常重要。如果定义一个符号的库出现在引用这个符号的目标文件之前,那么引用就不能被解析,链接就会失败。譬如:
1 | $ gcc -o main ./libvector.a main.o sum.o |
在处理libvector.a时,U是空的,所以没有libvector.a的成员加入到E中,因此,对于main.c中addvec的引用绝不会被解析,所以链接器会产生一条错误信息并终止。
关于库的一般准则是将它们放在命令行的结尾。如果各个库的成员是相互独立的,那么这些库就的成员就是相互独立的,即可以任意顺序放在结尾。如果库不是相对独立的,那么被调用库必须放在调用者的后面。如果两个库相互依赖,则需要在命令行上重复库。譬如liba.a和libb.a相互依赖,则需在命令行上输入类似如下命令,或者将两个库合并成一个单独的库。
1 | $ gcc -o main -la -lb -la |
3 重定位
一旦链接器完成了符号解析这一步,就把代码中每个符号引用和正好一个符号定义关联起来。此时,链接器就知道它的输入目标模块中的代码节和数据节的确切大小。然后就可以进行重定位步骤了,在这个步骤中,将合并输入模块,并为每个符号分配运行时的地址。重定位由两步组成:
- 重定位节和符号定义:在这一步中,链接器将所有相同的节合并为同一类型的新的聚合节。然后,链接器将运行时内存地址赋给新的聚合节,付给模块定义的每个节及符号。这一步完成时,程序中的每条指令和全局变量都有唯一的运行时内存地址了。
- 重定位节中的符号引用:在这一步中,链接器修改代码节和数据节中对每个符号的引用,使得它们指向正确的运行时地址。要执行这一步,链接器依赖于可重定位目标文件中的重定位条目(.rel开头)的数据结构。
3.1 重定位条目
当汇编器生成一个目标模块时,它并不知道数据和代码最终存放的内存位置,也不知道其引用的外部模块的全局变量和函数的位置。所以,当汇编器遇到对最终位置未知的目标引用时,它就会生成一个重定位条目,告诉链接器在目标文件合并成可执行文件时如何修改这个引用。代码的可重定位条目放在.rel.text中;已初始化数据的重定位条目放在.rel.data中。
ELE重定位条目格式如下所示,offset是需要被修改的引用的节偏移;symbol表示被修改引用应该指向的符号;type表示重定位类型,告知链接器如何修改新的应用;addend是一个有符号常数,一些类型的重定位需要使用它对被修改引用的值做偏移调整。
1 | typedef struct { |
ELF定义了32种不同的重定位类型,我们只关心其中两种最基本的重定位类型:
- R_X86_64_PC32:重定位一个使用32位的PC相对地址的引用;
- R_X86_64_32:重定位一个使用32位绝对地址的引用;
这两种重定位类型支持x86-64小型代码模型,该模型假设文件的代码和数据总体大小小于2GB,因此可以使用32位PC相对地址来访问。GCC默认使用小型代码模型。大于2GB的程序可以用-mcmodel=medium(中型代码模型)和-mcmodel=large(大型代码模型)标志来编译。
3.2 重定位符号引用
下面是链接器的重定位算法,这里的每个节s指的是.text中对应的成员,如果你是在main函数中查找应用,那么s就表示main;r表示重定位条目,是一个类型为Elf64_Rela的结构;ADDR()表示取符号运行时地址,譬如ADDR(main)就表示main函数的地址。如果引用的是PC相对地址,那么就使用5-9行的算法;如果是绝对寻址,那么选择的就是11-13行的算法进行寻址。
1 | foreach section s { |
我们执行以下指令,可得到以下反汇编代码(未完全显示)。
1 | 0000000000000000 <main>: |
3.2.1 重定位PC相对引用
在上图的第11行中,函数main调用模块sum.o中的sum函数。从上图可以看出,对于重定位条目r的4个字段如下:
1 | r.offset = 0x22 |
其实,call指令开始的节偏移再加上一个字节的操作码0xe8的偏移就是offset值,而往后再移动四个字节的操作码偏移,这个值就是addend值,因为符号的问题,一般取-4;这样即可求得紧随在call指令后的地址address = ADDR(s) + r.offset - r.addend
;那么在此地址到sum地址的偏差bias = ADDR(s.symbol) - address = ADDR(s.symbol) + r.addend - (ADDR(s) + r.offset) = ADDR(s.symbol) + r.addend - refaddr
,此值即*refptr
。通过上式,可以计算出*refptr = 0x6a
。在Linux下对最后生成的可执行文件执行以下指令,可以验证计算正确。
1 | $ objdump -dx main |
3.2.2 重定位绝对引用
重定位条目r的4个字段如下:
1 | r.offset = 0x1d |
offset虽然在计算地址的时候并没有用,但是其表征的也是mov指令开始的节偏移再加上一个字节的操作码0xbf的偏移就是offset值。经过计算,*refptr = (unsigned) (ADDR(r.symbol) + r.addend) = (unsigned) (ADDR(r.symbol) + 0) = 0x601020
,重定位后的x的地址为:
1 | 0000000000601020 g O .data 0000000000000008 x |
在得到的可执行文件中,是引用以下重定位形式的:
1 | 400510: bf 20 10 60 00 mov $0x601020,%edi |
至此,我们梳理了从可重定向目标文件(或静态库文件)经符号解析、重定位到最终生成可执行文件的整个过程,即静态链接的整个过程基本如上所述。下面针对可执行目标文件以及动态链接展开叙述。
4 可执行目标文件
下图概括了一个典型的ELF可执行文件中的各类信息,其含有加载程序到内存并运行它所需的所有信息。
可执行目标文件的格式类似于可重定位目标文件的格式。ELF头描述了文件的总体格式,还包括了程序入口(entry point),也就是程序运行时要执行的第一条指令的地址。
1 | $ readelf -h main |
可以看到程序入口地址是0x400410,即_start的地址;另外,.text、.rodata和.data节和可重定位目标文件基本类似;且可执行文件不需要.rel节。
节(section)和段(segment)是对可执行文件一部分相同内容的不同描述映射而已,其中,节头部表(section header table)是用来描述节信息,这在上面提到过;而段头部表(program header table)是描述段信息的,这在可重定位目标文件中是没有的,但是在可执行文件中是存在的,因为文件载入内存中,是以段为单位的,用来简历可执行文件的进程映像。我们通常所说的代码段,数据段就是这里所说的段,节会被映射到各个段中,譬如.text会被组装到代码段中,而.data和.bss会被包含在数据段中,具体可以如下查看:
1 | $ readelf -l main |
如上输出所示,文件中有9个段,只有类型为LOAD的段才是运行时真正需要的。
譬如第一个LOAD段的标志为R(只读) E(可执行),其编号为02,对应下方可以看出,其包含了很多section,包括.init、.text和.rodata,表明这是只读代码段。
第二个LOAD段的标志为RW(可读写),其编号为03,包括.data和.bss段,所以是数据段。
可执行目标文件的内存映射和加载涉及到虚拟内存的知识较多,暂且不表。
5 动态链接
如第0章所述,除非在命令行上输入-static
指令,否则系统默认优先链接动态库,找不到才链接静态库。虽然有了静态库,但是静态库仍然有一些明显的缺点:
1)静态库的定期更新要求应用需要显示的重新链接整个程序,否则无法使用更新后的功能;
2)每个程序都会使用的标准I/O函数,这些代码会被大量地复制到每个进程的文本段中,造成了内存资源的极大浪费。
共享库是致力于解决上述缺陷的创新产物。共享库是一个目标模块,在运行或者加载时,可以加载到任意的内存地址,并和一个在内存中的程序链接起来,这个过程称为动态链接,是由一个叫做动态链接器的程序来执行的。
共享库有两种体现“共享”的方式:
- 所有引用该库的可执行目标文件共享这个.so文件中的代码和数据,而不是像静态库一样将库的内容复制到可执行文件中;
- 在内存中,一个共享库的.text节的一个副本可以被不同正在运行的进程共享。
5.1 加载时链接
我们将前述libvector.a静态库的成员构造成名为libvector.so的动态库,并构建新的可执行文件main1。
1 | $ gcc -shared -fpic -o libvector.so addvec.c multvec.c && gcc -o main1 main.o sum.o ./libvector.so && ./main1 |
此时查看main1,发现其中并没有addvec的函数段,也就是说,没有任何libvector.so中的代码和数据节被复制到可执行文件main1中。
main1中包含一个.interp节,包含了动态链接器的路径名,在程序加载时,加载器加载和运行这个动态链接器,动态链接器执行以下重定位完成链接任务:
- 重定位libc.so的文本和数据到某个内存段;
- 重定位libvector.so的文本和数据到另一个内存段;
- 重定位main1中所有对libc.so和libvector.so定义的符号的引用;
最后,动态链接器将控制传递给应用程序。从这个时刻开始,共享库的位置就固定了,并且在整个程序执行的过程中都不会改变。
运行时链接
应用程序还可能在它运行的时候动态地加载和链接某个共享库,而无需在编译时链接。Linux为动态链接器提供了一系列的接口,我们直接通过下面这个例子理解以下这些dl开头的函数的用法。
1 |
|
例子来源于书本,具体用法可参考书本。基本用法是利用dlopen函数打开动态库,然后根据符号名称调用dlsym函数获取所需函数指针,再调用函数指针,最后利用dlclose函数卸载掉该共享库,且还提供了dlerror函数用于描述调用前述函数是发生的错误。最后,我们执行以下指令,发现程序正确运行。
1 | $ gcc -rdynamic -o main2 dll.c -ldl && ./main2 |
6 总结
总结以上,我们可以发现,链接可以执行于编译时(可重定位目标文件和静态库的链接),也可以执行于加载时(动态库的常规调用),还可以执行于运行时(动态库的动态调用)。
在编写C工程时,应当极力避免使用重名的全局变量,以免出现一些不可预期的错误。
在生成静态库文件时,尽量不要依赖于其它私有库文件,更要避免互相依赖的情形,如两个库文件相互依赖,可以将其合并成一个库文件。