第七章—链接

简介

链接(linking)是将各种代码和数据收集并组合成一个单一文件的过程, 这个文件可被加载(复制, 在程序员的自我修养中称为”装载”)到内存中并执行.

链接按照发生的时间可以分为三类:

链接执行在编译时: 也就是在源代码被翻译成机器代码的时候
链接执行在加载时: 也就是程序在被加载器(load time)加载到内存并执行时
链接执行在运行时: 也就是程序来执行

7.1 编译器驱动程序(compiler driver)

编译器驱动程序, 其代表用户在需要时调用: 语言预处理器, 编译器, 汇编器和链接器.

书中给出的实例

Untitled

我们使用编译器驱动程序(是GNU编译系统中的GCC)来将其翻译成可执行程序

输入下面的指令:

1
2
3

linux> gcc -Og -o prog main.c sum.c

如果想看详细的步骤,  可以是-v选项来云心GCC

这是将源码翻译成可以执行程序的流程

Untitled

步骤一

cpp [other arguments] main.c /tmp/main.i

驱动程序首先运行C预处理器(cpp),  将源码mian.c翻译成ASCII码的中间文件mian.i

步骤二

cc1 /tmp/main.i -Og [other arguments] -o /tmp/main.s

驱动程序运行C编辑器(cc1),  它将mian.i翻译成一个ASCII汇编语言文件main.s

步骤三

as [other arguments] -o /tmp/main.o /tmp/main.s 
r

驱动程序运行汇编器(as),  它将mian.s 翻译成一个可重定位目标文件(relo-catable object file)main.o

步骤四(最后一步)

ld -o prog [system object files and args] /tmp/main.o /tmp/sum.o(sum.o也是经过了上面的三个步骤得到的)

驱动程序运行链接程序(ld),  将mian.o和sum.o以及一些必要的系统目标文件组合起来,  创建了一个可执行目标文件prog

7.2 静态链接

静态链接器以一组可重定位目标文件和命令参数作为输入, 生成一个完全链接的, 可以加载和运行的可执行目标文件作为输出.

输入的可重定位目标文件由各种不同的代码和数据节(section, 在程序员的自我修养中有解释: 是为了和segment区分, 中文就将section译作节, segment译作段, 段后面也会提到), 每一个节都是一个连续的字节序列.

为了构造可执行文件, 链接器必须完成两个主要任务:

符号解析(symbol resolution): 目标文件定义和引用符号, 每个符号对应一个函数, 一个全局变量或一个静态变量, 目的: 将每个符号引用正好和一个符号定义关联起来
重定位(relocation): 链接器通过把每个符号定义与一个内存位置关联起来, 从而重定位这些节, 然后修改所有对这些符号的引用, 使得它们指向这个内存位置. (使用重定位条目的详细指令)

可以看到这两个任务的重点就是: 引用符号与 (符号定义, 内存位置之间的关联)

7.3 目标文件

目标文件有三种形式:

可重定位目标文件: 包含二进制代码, 可以与其他可重定位目标文件合并起来, 创建可执行目标文件
可执行目标文件: 其形式可以被直接复制到内存并执行
共享目标文件: 特殊的目标文件, 在加载或运行时被动态地加载进内存进行链接

三者间的关系: 可重定位目标文件和共享目标文件链接后成为了可执行目标文件

7.4 可重定位目标文件

一个经典的ELF可重定位目标文件的格式如下图所示:

Untitled

下面我们来逐个分析单个的节:

(开头)ELF头: 首先, 是一个16字节的序列: 描述了系统的字的大小和字节顺序. 然后, 是一些信息: ELF头的大小(用来确定.text节的位置, 来自程序员的自我修养), 目标文件的类型, 机器类型, 节头部表(section header table)的文件偏移, 节头部表中条目的大小和数量.
(结尾)节头部表: 描述不同节的位置和大小, 每个节在节头部表中都会有对应的条目
.text: 代码节
.rodata: 只读数据节, 比如printf()中的”123”
.data: 已初始化的全局变量 & 静态C变量(注意我们用的很多的局部变量是由栈来进行管理的)
.bss: 未初始化的全局变量 & 静态C变量 & 所有被初始化为0的全局或者静态变量(相当于未初始化), 在可重定位目标文件中不占空间, 但在运行时, 在内存中分配这些变量, 初始值为0
.symtab: 符号表, 存放了程序中定义和引用的符号信息(注意, 符号表不包含局部变量的条目)
.rel.text: .text重定位表(csapp原文的描述是”一个.text节中位置的列表”, 不论正确与否, 看的实在是难以理解, 但是在程序员的自我修养中描述是”针对.text的重定位表 ”) 记录需要修改的位置(引用外部的函数或全局变量).
.rel.data: .data的重定位表, 记录被模块引用或定义的所有全局变量的重定位信息.
.debug: 调试符号表, 用于调试, 不重要
.line: 源代码和机器指令之间的映射, 不重要
.strtab: 字符串表, .symtab和.debug会用到

7.5 符号和符号表

每个可重定位目标文件都会有符号表, 包含了其定义和引用的符号信息.

符号

有三种不同的符号:

由模块本身定义并能被其他模块引用的全局符号, 对应: 非静态C函数, 全局变量
外部符号, 由其他模块定义并能被本模块引用的全局符号, 对应: 其他模块定义的非静态C函数, 和全局变量
只被本模块定义和引用的局部符号, 对应: 带static属性的C函数和全局变量.

符号表

符号表其实就是一个结构体的数组, 每个结构体元素对应一个符号

Untitled

我们来解释以下各个结构的意义

name: 其值为字符串表中的偏移, 指向的是字符的名字
value: 是符号的地址, 对于可重定位目标文件来说, 是距离定义目标的节的偏移; 对于可执行目标文件来说, 是一个绝对运行时地址(这里的地址指的就是符号本身的地址, 而不是符号表中条目的地址)
size: 是目标的大小(单位字节)
type: 分为数据和函数
binding: 表示符号是本地还是全局
section: 表示符号被分配到的节

这里注意当section的值为以下三个, 表示其为伪节(在节头部表(在程序员的自我修养中叫做段表)没有条目):

ABS: 表示不该被重定位的符号
UNDEF: 表示未定义的符号, 也就是在本模块中引用, 却在其他模块中定义的符号
COMMON: 表示还未分配位置的未初始化目标, 特别的, 对于COMMON来说, value意义是对齐要求, size意义是最小的大小

又要注意COMMON跟.bss之间的区别

COMMON 未初始化的全局变量
.bss 未初始化的静态变量, 以及初始化为 0 的全局或静态变量

7.6 符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来

7.6.1 链接器如何解析多重定义的全局符号

不同的模块中可能会有相同的符号, 比如模块a中有一个全局变量为x, 模块b中也有一个全局变量为x

这样就需要一些规则来确定我们引用的符号是指的哪一个, 也就是强符号和弱符号:

函数和已初始化的全局变量是强符号
未初始化的全局变量是弱符号

具体的规则:

规则1: 不允许有多个同名的强符号
规则2: 如果同时有强符号和多个弱符号, 则为强符号
规则3: 多个弱符号同名, 那么从其中任意选一个(但是在程序员的自我修养中的解释是: 选择所占空间的大的那个, 就比如int类型跟double类型, 则会选择double类型的弱符号)

7.6.2 与静态库(static library)链接

将很多相关模块打包在一起, 就是静态库. (就像是我们组装汽车, 有人提供了一个发动, 我们需要为它提供车轮, 地盘, 车身, 但是东找西找的很麻烦, 我们就提供了一个工具包, 里面把一个汽车所有的零件都提供, 只需要我们提供一个发动机就可以直接组装成一个汽车了, 这就是静态库)

如果不用静态库, 如何提供所需函数:

方法一: 让编译器识别对标准函数的调用, 并生成相应代码. 缺点是添加, 删除或修改都需要更新编译器版本, 太麻烦
方法二: 让所有标准函数都放在一个单独的可重定位目标模块中. 优点: 将编译器和标准函数实现分开. 缺点: 每个可执行文件都包含一份函数集合的完全副本(没用的函数也包含进去了), 浪费极大的内存, 同时改变这个集合中的一小部分, 那整个集合都要重新编译, 跟方法一的编译器更新很相似

所以最终的解决方案是:

静态库: 为每个相关函数一个独立的目标模块, 然后封装成一个静态库文件.

使用

linux> gcc mian.c /usr/lib/libm.a /usr/lib/libc.a
                    一个静态库libm.a  另一个静态库libc.a

优点是: 1, 只复制被引用的模块, 减少了内存的浪费; 2, 只需要较少的库文件名字(一个库有很多模块)

7.6.3 链接器如何使用静态库来解析引用

要知道的解析规则: 链接器从左到右按照命令行上出现的顺序(上面实例的顺序是libm.a到libc.a)扫描可重定位目标文件和存档文件(archive, 也就是静态库的存储格式 .a)

书本给出了具体实例:

前提条件:
可重定位目标文件集合E,  一个未解析符号集合U,  一个在前面输入文件中已定义的符号集合D

输入文件f

过程:
首先链接器会判断f为目标文件还是存档文件
f为目标文件:  链接器把f添加到E,同时修改U和D反映f中的符号定义和引用, 接着扫描下一个
f为存档文件:  链接器尝试匹配U中未解析的符号和存档文件成员定义的符号(函数,全局变量), 如果存在m定义
了U中的一个引用,说明匹配成功, m从U地洞到E
链接器一直进行上面的过程,  知道U和D都不再发生变化.最后不包含在E中的成员目标文件都被抛弃,链接器继续
处理下一个输入文件

ps:
其实一开始, 我还在担心如果最先扫描的是目标文件而不是存档文件,  那么U中都是目标文件的引用, 到最后都
没有相应的匹配项.  这个想法很明显是错误的, 因为每次识别完f的两种类型, E和U的集合都不会清空, 也就是
第一次的目标文件可以跟第二次的存档文件匹配.

结果:
当上面所有的步骤结束后,  U是非空的(代表还有未解析的符号), 链接器就会输出一个错误并终止.
如果成功了,  就会合并和重定位E中的目标文件,  构建输出的可执行文件

注意:
输入的库和目标文件的顺序非常重要

另一要求:

E是空的没有问题,但是U是空的就会出现问题
还是上面ps中的例子,  我们先目标文件后存档文件没有问题,  但是交换二者的位置不行,因为存档文件只会扫
描一次.
所以,  我们都是先把库放在后面

再就是库不是相互独立的, 使得先匹配调用模块,  后匹配被引用模块(这有点像是我们文件的路径查询, 不能
跳过任何一个路径)
比如a, b引用了c,  则命令行中a,b必须在c前

7.7 重定位

链接器王城了符号解析后: 代码中的每个符号引用与正好一个符号定义关联起来了

然后进行重定位操作, 分为两步:

重定位节和符号定义:

首先, 所有相同类型()的节合并为新的聚合节(如全部.data合并为一个新的.data节).

然后, 将运行时地址赋给新的聚合节, 赋给输入模块的每个节, 以及赋给输入模块定义的每个符号. 然后, 程序中的每条指令和全局变量都有为的运行时内存地址了

重定位节中的符号引用: 修改代码节和数据节中对每个符号的引用, 使得它们指向正确的运行时地址.

第一步确定了整体的运行时地址, 当这个确定的时候也就代表着每一个符号地址的确定, 第二步就是修改引用, 使得指向确定的符号地址

7.7.1 重定位条目(重定位表)

作用: 遇到了对最终位置未知的目标引用, 条目会告诉链接器如何修改这个引用

Untitled

我们来了解一下这个结构题:

offset: 需要被修改的引用的节偏移

symbol: 标识被修改引用应该指向的符号

type: 告诉链接器如何修改新的引用

addend: 有符号常数, 一些类型需要它对偏移offset做调整

下面时两种基本的重定位类型:

R_X86_64_PC32: 相对地址引用, 使用PC下条指令作为基点得出偏移值
R_X86_64_32: 绝对地址引用

具体的操作回头来看书.

7.8 可执行目标文件

链接后得到了我们的可执行目标文件, 结构图如下:

Untitled

再来分析一下各个部分:

ELF头: 描述文件总体格式, 并还有入口点(entry point)
.init: 定义一个小函数_init, 程序调用它来初始化代码
.text: 代码段
.rodata: 只读数据段
.data: 数据段

注意, 由于已经链接完成(说明重定位也完成了), 所以重定位表被删去

可执行文件的连续的片(chunk)被连续映射到连续的内存段(注意这里出现的段, 也就是我们上面说的segment和section之间的区别)

段的分类是按照: 只读, 可写, 执行等属性进行划分的, 程序头部表描述了这种映射关系.

说实话程序头部表在书中出现的有点突兀, 在前面的结构图中也没有出现, 查了一下其他版本的ELF可执行目标程序结构图

Untitled

发现节头部表时跟Section header table相对应的, 所以可以猜测Program header table(也就是段头部表)跟程序头部表也是对应的(也许是翻译的问题, 跟前面的text重定位表类似)

再加上段头部表的结构体

Untitled

描述的都是与段相关的内容, 所以大概率是指段头部表

7.9 加载可执行目标文件

系统代码加载器(loader)回运行我们的可执行目标文件

加载器将可执行文件中的代码和数据从磁盘复制到内存, 然后陶砖到程序的第一条指令或入口点来运行该程序. 将程序复制到内存并与运行的过程叫做加载

加载后的内存视图如下

Untitled

Linux程序的起始地址(虚拟地址)的开始一般为0x400000

后面紧跟数据段

再后面是运行时堆(向高地址增长)

堆后内存为共享模块保留

然后是栈, 其位置也是相对固定的(向低地址增长)

最后是内核

这些创建完上面这些后 :

加载器在程序头部表(段头部表, 段表)指引下将可执行文件的片(chunk)复制到代码段和数据段.
然后跳转到入口点(_start())
*start()*调用系统启动函数__libc_start_main(), 该函数初始化执行环境, 并调用main函数, 处理mian函数返回值
最后控制返回内核

7.10 动态链接共享库

静态库的缺点: 1, 跟程序一样还是需要更新, 那原本的程序就需要重新连接; 2, 每个进程都是用同一个函数, 一百个程序就链接一百个printf, 浪费了很多内存

所以有了动态库, 在程序运行或加载时, 加载到任意内存地址, 冰河一个内存中的程序链接起来, 这个过程叫动态链接, 该过程由动态链接器完成, 共享库也叫共享目标, (Linux中有.so文件, Windows中有DLL)

下面看一下动态链接的流程图:

Untitled

首先我们要明白两点:

一个库只有一个.so文件, 所有引用该库的可执行目标文件共享这个.so的代码和数据
在内存中, 一个共享库的.text节的一个副本可以被不同的正在运行的程序共享

输入以下命令行

linux> gcc -shared -fpic -o libvector.so addvec.c multvec.c

								动态链接的对象是 libc 和 libvector

linux> gcc -o prog2l mian2.c ./libvector.so

得到了可执行目标文件prog2l, 且文件的形式使得它在运行时可以和libvector.so链接, 原因在: 讲台执行了部分链接, 然后再程序加载时, 动态完成全部链接过程

动态链接器通过下面的重定位来完成链接任务:

重定位libc.so的文本和数据到某个内存段
重定位libvector.so的文本和数据到另一个内存段
重定位prog21中所有对由libc.so和libvector.so的符号的引用
最后动态链接器将控制传递给应用程序.

7.11 从应用程序中加载和链接共享库

Linux系统为动态链接器提供了一个简单的接口, 使应用陈鼓型再运行时加载和链接共享库

dlopen(): 加载和链接第一个参数filename, 第二个参数falg有两个: RTLD_NOW表示链接器立即解析对外部符号的引用, RTLD_LAZY表示链接器推迟符号解析知道执行来自库的代码

1
2
3

#include <dlfcn.h>

void *dlopen(const char *filename, int flag);

dlsym(): 返回符号的地址, 否则返回NULL. 第一个参数handle时共享库的句柄, 第二个参数symbol是查找的符号名

1
2
3

#include <dlfcn.h>

void dlclose (void *handle, char *symbol);

dlclose(): 如果不需要这个共享库, 这个函数可以删除共享库

1
2
3

#include <dlfcn.h>

int dlclose (void *handle);

dlerror(): 返回一个字符串, 描述前三个函数最近发生的错误, 没错误就返回NULL

1
2
3

#include <dlfcn.h>

const char *dlerror(void)

7.12 位置无关代码

使多个进程共享程序的一个副本的方法:

给每个共享库分配一个预备好的空间片, 然后要求加载器总是从这个地址加载共享库, 缺点: 地址空间效率低, 不适用的库也腾出了空间

另一个方法就是我们现在使用的:

使用位置无关代码(Position-Independent Code, PIC), 可以让共享模块加载到内存任何位置而无需链接器修改.

1. PIC数据引用

因为程序加载至内存中时, 每个段之间的相对距离就固定了, 所以我们可以使用相对距离(一个系数)来表示位置, 所以有了一个全局偏移量表(Global Offset Table, GOT)

全局偏移量表(GOT): 每个引用的全局数据目标都有一个条目, 每个条目都拥有一个重定位记录, 链接器重定位每个GOT条目得到绝对地址.

2. PIC函数调用

共享库重定位的两种方法:

正常来说, 引用一个条重定位记录, 动态链接器再加载时解析它, 并修改代码段
PIC, 则无需修改, 而是使用一个称为延迟绑定(Lazy Binding)的方法

延迟绑定

把函数地址的解析推迟到它实际被调用的地方, 避免动态链接器再加载时进行多余的重定位

这样的实现是通过两个结构的交互实现的, 分别是GOT和过程链接表(Procedure Linkage Table, PLT)

我们先看看两个表的内容:

过程链接表(PLT): 是一个数组, PLT[0]为特殊条目, 用来跳转到动态链接器中. 每个库函数都有对应的PLT条目,
全局偏移量表(GOT): 上面讲到过, 条目拥有重定位记录.

二者联合使用的时候:

GOT[0]和GOT[1]包含动态链接器在解析函数地址时会用到的信息
GOT[2]为动态链接器在ld-linux.so模块的入口点
其余条目对应一个被调用函数

下面时一个PIC函数调用分析的实例

Untitled

GOT和PLT协同工作过程:

不直接调用addvec(), 而是进入PLT2
第一条PLT指令通过GOT[4]进行间接跳转. GOT条目初始时都指向对应PLT条目的第二条指令, 所以就相当于PLT[2] → GOT[4] → PLT[2]
PLT[2]将addvec的ID压入栈中后, 控制回到PLT[0]
PLT[0]通过GOT[1]间接将动态链接器的一个参数压入栈中, 后通过[GOT2]跳至动态链接器中, 动态链接器使用两个栈条目(一个是addvec的ID, 一个是动态链接器的参数)确定addvec的位置, 将这个地址重写进GOT[4](重写的是GOT条目, 而不是指令, 这就是PIC不修改指令的方法), 再将控制权给addvec

首次加载完后我们看到的变化是: GOT[4]的内容指向的不再是PLT[2]的第二个指令了, 而是addvec运行时的地址.

所以, 以后的运行流程要简单的多:

控制传到PLT[2]的第一条指令, 会间接跳转到GOT[4]
GOT[4]指向的是addvec的位置, 程序直接跳转到addvec

7.13 库打桩机制

将库函数替换或者是包装成你自己的函数

基本思想: 给定一个需要打桩的目标函数, 创建一个包装函数(条件是函数原型和目标函数完全一样). 使用特殊的打桩机制, 就可欺骗系统调用包装函数而不是目标函数. 注意, 包装函数通常执行自己的逻辑, 然后调用目标函数, 将目标函数的返回值传递给调用者.

打桩根据不同的时机分类:

编译时打桩
链接时打桩
运行时打桩