CSAPP 第七章 链接工作原理

进入全书的第二部分了, 之前想都没想过, 能一路读下来还都懂了. 第一部分讲的实际上是程序和硬件之间的关系, 第二部分讲的是程序和操作系统之间的关系.

第七章链接先翻了一遍, 这本书实际上是在说C语言以文件作为模块, 不同模块之间是如何互相组合成可执行文件的. 换成C语言的教学的话, 这一章主要就是在讲C语言的全局变量声明, 外部变量和static变量的关系.

1. 什么是链接
2. 目标文件结构与符号表
3. 符号解析 – 符号解析的规则
4. 符号解析 – 静态库
5. 符号解析 – 解析静态库的方式
6. 重定位

什么是链接

链接指的是将程序和数据片段收集并组合在一起成为一个单一文件的过程. 这个文件是可执行文件, 可以被加载到内存中并执行. 链接可以在编译时(源代码被翻译成机器代码), 加载时(被加载器加载到内存中), 或者运行时来进行.

执行链接动作的程序叫做链接器.

有两个小例子程序文件, 分别叫做 main.c 和 sum.c:

//main.c
int sum(int *a, int n);

int array[2] = {1,2};

int main(){
    int val = sum(array, 2);
    return val;
}

//sum.c
int sum(int *a, int n){
    int i, s = 0;
    for(i = 0; i < n; i++){
        s += a[i];
    }
}

这两个程序很简单, 在main 中声明了一个函数原型 sum, 而sum.c就是这个函数所在的文件. 下边就要对其进行编译和链接.

大多数的编译器驱动程序(编译器)并不是仅仅翻译源代码, 而是预处理器, 编译器, 汇编器和链接器的组合.

将两个文件放到同一个目录之下, 然后执行 gcc -Og -o prog main.c sum.c

就可以生成一个名为prog的可执行文件. 实际上的过程是, 先分别对main.c和sum.c调用cpp(C语言预处理器, 生成的中间文件后缀名为.i), ccl(C编译器,生成的汇编文件后缀名为.s), as(汇编器, 生成可重定位目标文件.o).

最后会调用链接器(ld, 将.o文件和其他所需的文件组合起来,创建可执行文件, linux下可执行文件的后缀名可以任意, 但一般没有后缀或者叫做out).

最后生成的可执行文件可以用 ./prog 来执行, 执行的时候, shell会调用加载器(loader), 将prog中的程序和数据复制到内存, 然后将控制转移给程序开头.

GCC这样的LD是静态链接器, 接受的文件类型是.o文件, 每一个.o文件都由各种不同的代码节和数据节组成, 每一节都是一个连续的字节序列.链接器需要完成的主要任务是:

1. 符号解析. 函数, 变量, 静态变量都是一个符号, 需要将每个符号引用与一个符号的定义关联起来
2. 重定位, 把每个符号定义与一个内存位置关联起来, 从而重定位.o文件中的所有代码节和数据节, 然后修改所有对于符号的引用, 将其指向对应的位置. 在上一步的汇编器生成的汇编文件中, 有帮助链接器工作的重定位条目.

为了理解链接, 其实就是理解链接器的这两步工作.

目标文件结构与符号表

目标文件有三种:

1. 可重定位目标文件, 就是汇编器生成的文件, 还需要进一步链接才能够形成可执行文件
2. 可执行目标文件, 包含二进制代码和数据, 其形式可以被直接复制到内存中执行
3. 共享目标文件, 这是特殊的可重定位目标文件, 可以在加载或者执行的时候动态的加载进内存并链接. 这个其实就是动态链接库.so

目标文件有着不同的格式, 在Windows系统下是PE格式, Mac系统下是Mach-O格式, 而在Linux下是ELF格式.

先来看看可重定位目标文件结构, 也就是GCC编译成的.o文件, 这是ELF格式的可重定向目标文件, 其内部格式包括一个ELF头,10个节和节头部表, 其中索引0是ELF头, 索引1-10是节:

索引0 ELF头 以一个特定的16字节序列开始, 描述了生成该文件的系统的字长和字节顺序. 剩下的部分帮助链接器语法分析和解释目标文件. 其中包括ELF头大小, 目标文件三种类型之一, 机器类型, 节头部表的偏移, 以及表中条目的大小和数量. 其中的节头部表描述了所有节的位置和大小, 每一个节在表里都有一个固定大小的条目 简单的说, ELF描述了整个可执行文件的基础信息和结构.

索引1 .text 已编译程序的机器代码

索引2 .rodata 只读数据, 比如跳转表

索引3 .data 已初始化的全局变量和静态C变量. 局部变量在运行时保存在栈中, 不会出现在这里和.bss节

索引4 .bss 未初始化的全局和静态C变量, 以及所有被初始化为0的全局和静态变量. 这个仅仅是占位符, 不占用实际的空间. 在运行的时候在内存中分配这些变量

索引5 .symtab 一个符号表, 存放所有定义和引用的函数和全局变量的信息, 不包含局部变量

索引6 .rel.text .text节中位置的列表, 链接器在链接的时候需要修改这些位置

索引7 .rel.data 被模块引用或定义的所有全局变量的重定位信息. 一般如果已经初始化的全局变量的值是一个全局变量地址或者外部定义函数, 都要修改这里.

索引8 .debug 调试符号表, 其中的条目是程序中定义的局部变量和类型定义, 定义和引用的全局变量和原始的C源文件. 只有 gcc -g才有这张表.

索引9 .line 原始C源程序的行号和.text中机器指令之间的映射, -g才会有这个表.

索引10 .strtab 一个字符串表, 包括.symtab和.debug中的符号表, 以及节头部的名字. 这个就是一个以NULL结尾的字符串的序列.到这里都是节.

节头部表, 描述整个目标文件的节.

这其中的关键是机器代码以及符号表. 符号表包含了所在的目标文件所有定义和引用的符号的信息.

对于链接器来讲, 有三种符号:

1. 在当前模块中定义, 能够被其他模块引用的全局符号, 对应非静态的C函数和全局变量
2. 有其他模块定义, 并被当前模块引用的全局符号, 对应其他模块中定义的非静态C函数和全局变量
3. 只被当前模块定义和引用的局部符号, 对应与带static修饰的C函数和全局变量, 这些变量在m内部都可见, 在其他模块不可见.

注意.symtab中不包含本地的, 不是静态的所有程序变量, 因为这些变量在运行的时候由过程在栈中管理. 链接器不会管理这种符号. 例外是用static 修饰的局部变量, 这种不是在栈中管理的, 编译器会在.data或者.bss中为每个定义分配空间, 然后在符号表中创建对应的符号.

例如:

int f(){
    static int x = 0;
}

int f(){
    static int x = 0;
}

这两个函数中的局部变量, 会被输出成两个不同名字的局部链接器符号.

简单的说, 在一个C文件里, 只有写在所有函数外边的变量, 所有函数和用static修饰的局部变量, 会出现在.symtab符号表中.

C语言实际上一个源文件代表一个模块, 用static修饰的模块级变量和函数, 都是对外不可见的.

使用GNU READELF程序可以查看目标文件的构成, 在这里找了一篇文章.

这里使用了 readelf -all main.o , 看到显示的结果:

Symbol table '.symtab' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     8: 0000000000000000     8 OBJECT  GLOBAL DEFAULT    3 array
     9: 0000000000000000    31 FUNC    GLOBAL DEFAULT    1 main
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND sum

可以看到符号表中包含其中三个, Num 指的是在字符串表中的偏移. value指的是距离所在的节的起始位置的偏移. Size表示大小, 以字节表示. Bind表示符号是本地的还是全局的.

后边的Ndx指的是所在的节. 节的顺序就按照上边ELF的索引顺序, 比如array就是索引为3也就是.data节, 偏移量为value=0的所在地.长度为8字节, 就是我们定义的两个int元素谁组成的数组.

main是长度为31字节, 定义在索引1 也就是.text节, 偏移量是0,也就是起始处的函数.

Ndx有三个特殊索引, 分别叫做ABS(不该被重定位的符号), UND(UNDEF, 未定义的符号, 即本模块中引用, 但是定义在其他地方的符号), COM(COMMON, 表示还未分配位置的未初始化的数据目标).

对于COMMON, value字段给出对齐要求, size给出最小的大小. 这三个特殊索引只在目标文件中存在, 链接之后的可执行文件是没有的.

练习 7.1 符号表

符号	.symtab条目?	符号类型	在哪个模块中定义	节
buf	是外部变量, 所以存在于符号表中	用extern修饰的外部变量	swap.o	以及初始化的全局变量, 在.data中
bufp0	也是全局变量, 已经被初始化, 也存在于符号表中	全局变量	swap.o	.data
bufp1	存在	全局变量	swap.o	尚未初始化的全局变量, 所以是在COMMON中
swap	函数名,是全局的	在swap.o中符号类型是全局FUNC	swap.o	.text
temp	这个是局部变量而且没有static修饰, 所以不存在于符号表中	无	无	无

了解了符号表之后, 就可以来学习链接器两个工作的第一个工作: 符号解析了.

符号解析 – 符号解析的规则

从符号表可以知道, 除了被static修饰的符号之外, 剩下的全局变量和函数都可能涉及到其他模块, 因此必须有一个解析的方法.

Linux下解析的方法是:

1. 先将符号分为强和弱. 函数和已经初始化的全局变量是强符号, 未初始化的全局变量是弱符号.
2. 不允许有多个重名的强符号, 如果有会报错
3. 如果有一个强符号和若干个弱符号重名, 会选择强符号
4. 如果有多个弱符号同名, 会随机挑选一个

练习 7.2 说明如何解析符号

1. 模块1中是main函数的定义, 模块2中是main函数原型声明. 所以REF(main.1) -> DEF(main.1), 而REF(main.2) -> DEF(main.1)
2. 可以看到, 强符号出现冲突.所以会产生错误
3. 强符号 double x 会覆盖弱符号, 所以 REF(x.1) -> DEF(x.2), REF(x.2) -> DEF(x.2)

符号解析 – 静态库

所谓静态库, 就是在链接过程中, 把需要的库文件直接放入到当前可执行文件内部的链接方式. 在加载和运行时无需进一步的链接.

在Linux系统中, 静态库以一个存档(.a文件)的方式存放, 是一组可重定位目标文件的集合. 在之前的Head First C已经接触了如何将程序打包成静态库.

库的名称必须叫做libxxxx.a, 然后在GCC命令行引用库的时候可以简写为 -lxxxx

举个简单的例子, 和当时学Head First C几乎一样:

//addvec.c
#include "vector.h"

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];
    }
}

//mulvec.c
#include "vector.h"

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];
    }
}

将上述两个文件通过 gcc -c addvec.c mulvec.c 生成两个可重定位目标文件, 然后再执行:

ar rcs libvector.a addvec.o mulvec.o

然后有一个主文件 main2.c:

#include <stdio.h>
#include "vector.h"

int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];

int main(){
    addvec(x, y, z, 2);
    printf("z=[%d,%d]", z[0], z[1]);
}

将刚才生成的库文件 libvector.a 和main2.c 放在一起, 去掉其他文件和main中的头文件, 然后执行编译:

gcc -static main2.c ./libvector.a

就可以成功编译, 如果将libvector.a放到系统路径之下, 就可以使用 -l参数来编译.

这里 -static 的作用是, 创建完全链接好的文件, 无需在运行的时候再链接, 使用这个开关, 会将main2.o所需要的全部库代码, 包括标准库和我们自己写的库, 都复制到可执行文件中. 这里实际复制的目标文件就是使用到的libvector库中的目标文件, 以及在libc.a中的printf.o模块.

实际上, 对于标准库, 很多都是动态库, 会在运行的时候加载的.

还记得吗, 链接的时候main2.c会被编译成main2.o ,然后再链接, 说明链接器成功的链接了静态库和main2.o

解析静态库的方式

链接器是如何解析静态库的呢, 实际上是通过三个数据结构来的.

链接器首先定义三个空的集合:

1. E – 用于存放所有需要放入到最终可执行文件中的目标文件集合
2. U – 所有未解析的符号集合
3. D – 已经有了定义的符合集合D

然后链接器开始按照命令行来读入文件, 如果是一个目标文件, 就会把目标文件添加到E里, 然后将目标文件中所有的符号定义和引用, 按照能解析的放在U里, 不能解析的放在D里.

如果读入一个存档文件, 就会按照U中的符号, 到存档文件里的各个目标文件中去找能够对应的符号, 如果能找到(即解析成功), 就把对应的目标文件放入E, 从U里删除解析成功的符号, 放入到D中.

反复执行这个过程直到所有的命令行中的文件都解析完毕, 此时检查U是不是为空, 如果为空说明成功的解析了全部符号, 如果不为空就报错.

因此, 如果库之间有引用的关系的话, 命令行的顺序就很重要了, 越靠后的依赖必须越放在后边.

练习题 7.3 解析顺序

1. p.o -> libx.a, 这个顺序是一个依赖, 所以需要使用 gcc p.o libx.a
2. p.o -> libx.a -> liby.a, 这也是顺序的依赖, 所以需要使用 gcc p.o libx.a liby.a
3. p.o -> libx.a -> liby.a -> libx.a -> p.o, 由于p.o自己的符号已经存在, 无需重复写, 所以需要使用 gcc p.o libx.a liby.a libx.a

重定位

链接器的第一步工作, 也就是符号解析已经知道了, 其本质就是在目标文件可库文件中搜寻相同名字的符号, 然后一一对应起来, 同时也知道了所有需要的目标文件.

链接器的第二步工作, 就是重新定位. 这个工作分为两步:

1. 重定位节和符号定义, 会将所有的目标文件中的同类型的节合并成新的聚合节, 然后为每个节, 每个符号都赋给运行时的内存地址. 这一步完成之后, 所有的指令和全局变量都有了唯一的运行时内存地址.
2. 重定位节中的符号引用, 会一一将代码节和数据节中的所有符号修改成正确的运行时地址. 这个依赖于可重定位条目.

第一步就是分配地址, 关键看第二步, 即已经知道了所有节和变量的地址, 如何将具体的引用替换成这些地址.

代码的重定位条目放在 .rel.text 节中, 已经初始化的数据的重定位条目放在 .rel.data 中.

每一个重定位条目有如下几个内容组成:

1. offset, 表示从节地址开头的偏移量
2. symbol, 表示对应哪个符号
3. type, 表示定位类型, 32种, 目前需要关心两种, 一种是32位地址相对重定位(R_X86_64_PC32), 一种是32位绝对地址重定位(R_X86_64_32).
4. addend, 是有符号常数, 表示偏移量调整.

举个例子就很容易说明了, 现在有如下的main.o目标文件:

0000000000000000 <main>:
    0:      48 83 ec 08             sub     $0x8, %rsp
    4:      be 02 00 00 00          mov     $0x2, %esi
    9:      bf 00 00 00 00          mov     $0x0, %edi          %edi = %array
                                    a: R_X86_64_32
    e:      e8 00 00 00 00          callq   13<main+0x13>    sum()
                                    f: R_X86_64_PC32 sum-0x4
    13:     48 83 c4 08             add     $0x8, %rsp
    17:     C3                      retq

其中所有汇编器无法确定位置的地方, 都先上了数值0, 然后在下边加上了重定位条目, 就是其中红色的部分.

在进行完第一步之后, 已经分配了如下的地址:

1. .text聚合节的开头地址 = 0x4004d0, .text聚合节存放所有的代码, 其开头地址同时也是main函数的地址.
2. sum函数开头的地址 = 0x4004e8
3. array的地址是 0x601018

然后看sum的重定位引用f: R_X86_64_PC32 sum-0x4, 其内容是:

r.offset = 0xf
r.symbol = sum
r.type = R_X86_64_PC32
r.addend = -4

这个意思是sum的对应节偏移量是0xf, 然后还需要调整-4的地址.

先计算出引用地址 = 节地址 + 节偏移量 = 0xf+ 0x4004d0 = 0x4004df.

然后其实就是用偏移量和callq的指令位置计算出位置, 即:

0x4004e8 -4 - 0x4004df = 5

算出来的5, 就放入到call q 指令的地址中去: 按照节地址重新编排之后, 就变成了:

0x4004d0 <main>:
0x4004d0:      48 83 ec 08             sub     $0x8, %rsp
0x4004d4:      be 02 00 00 00          mov     $0x2, %esi
0x4004d9:      bf 00 00 00 00          mov     $0x0, %edi          %edi = %array
                                    a: R_X86_64_32
0x4004de:      e8 05 00 00 00          callq   4004e8;    sum()
                                    f: R_X86_64_PC32 sum-0x4
0x4004e3:     48 83 c4 08             add     $0x8, %rsp
0x4004e7:     C3                      retq
0x4004e8:     sum.....

在计算出来了callq指令之后. 可以发现上边橙色的部分也就是array的地方还没有正确链接. array的重定位条目如下:

r.offset = 0xa
r.symbol = array
r.type = R_X86_64_32
r.addend = 0

这个算法就是直接使用array的地址加上addend的偏移量, 也就是array的地址 0x601018.

然后就可以替换掉地址引用:

0x4004d9:      bf 18 10 60 00          mov     $0x601018, %edi          %edi = %array

执行了上述的两步计算之后, 就将main中对sum 和array 引用的地址替换成了实际的地址. 这个程序就可以运行了.

在实际的文件中, 重定位条目并不是上边程序这样直接插入在汇编代码中的, 而是在另外的节中.

练习 7.4 回答问题

对sum重定位引用的十六进制内存地址是 0x4004df = 4004d0 + 0xf, 对重定位引用的十六进制值是5

练习 7.5 计算引用

计算引用值 = 0x4004d0+0xa = 0x4004da

计算值 = 0x4004e8 -4 – 0x4004da = 0xA

所以指令是 0x4004d9 e8 0A 00 00 00 call 4004e8

现在就知道了链接器是如何工作的, 其本质上, 就是先重新编排各个节, 函数和全局变量的内存地址, 再将程序段中所有符号替换成实际的内存地址. 虽然重定位条目的类型有很多种, 但是对于最简单的两种, 相对于PC偏移和绝对地址, 其实质就是用函数的地址加上偏移量和指令长度计算出地址然后替换.