CSAPP 第七章（一） Linker和静态链接

是的，我又一次发现我经常说我喜欢系统方向其实只能说说而已(大悲)，实在菜得离谱，但是是真喜欢。我还喜欢说大一下学期csapp把我引进系统方向的门，这句话好像没说错只是。。。。可能当时只理解了10%(大悲+1)，所以树莓派的bug一开始没找到。。。所以现在来重新看了。。。

1. overview: compiler drivers

Linking可能发生在编译期compile time，此时源代码被翻译成机器码；也可能发生在装载期load time，此时程序正被装载到内存中同时由loader执行；也可能发生在运行时run time，由应用程序处理。

当我们调用Linux> gcc -Og -o prog main.c sum.c时，本质上经历了如下流程

compiler driver的调用对象	执行命令	生成的结果
c预处理器cpp(c preprocessor)	`cpp [other arguments] main.c /tmp/main.i`	ASCII表示的中间文件main.i
c编译器cc1(c compiler)	`cc1 /tmp/main.i -Og [other arguments] -o /tmp/main.s`	ASCII表示的汇编文件main.s
汇编器as(assembler)	`as [other arguments] -o /tmp/main.o /tmp/main.s`	二进制可重定向目标文件main.o
链接器ld(linker)	`ld -o prog [system object files and args] /tmp/main.o /tmp/sum.o`	可执行的目标文件prog

最终，在命令行中运行程序时，shell会调用fork()，然后在子进程中执行提供的loader程序，它会把可执行文件prog的数据和代码拷贝到内存，同时将控制转移到程序的开头。

这一个post主要讨论linking。值得注意的是linking过程处理的对象是assembler输出的目标文件，这也意味着源程序此时已经被翻译为对应的汇编代码的二进制形式以及一些额外信息。

2. static linking

ld程序是Linux的静态链接器，以可重定向文件和命令行参数为输入，生成一个链接完成的可执行目标文件。链接器主要有两个任务

符号决议：符号对应着函数、全局变量或者静态变量，符号决议的目的是关联每个符号引用和符号定义。
重定位：编译器和汇编器生成的代码节(section)和数据节从地址0开始。链接器通过给每个符号定义分配内存地址重定位这些节，同时也修改所有的符号引用。链接器使用重定位条目relocation entries执行重定位操作。

3. 目标文件

目标文件有三种形式：

可重定位目标文件：二进制代码和数据，能够和其它可重定位目标文件在编译期组合在一起创建可执行目标文件。
可执行目标文件：二进制代码和数据，能够直接拷贝到内存并执行。
共享目标文件：一种特殊类型的可重定位目标文件，能够被装载到内存并动态链接，可以发生在装载时(load time)或是运行时(run time)。

目标文件依据目标文件格式(object file formats)组织代码和数据。Linux和Unix使用ELF(Executable and Linkable Format)格式，如下图

4. 可重定位目标文件

4.1. elf header

ELF格式的可重定位文件ELF header起始，前16字节的序列描述了生成该文件的系统的word size和字节序。ELF header剩余部分给出了linker需要的用于parse和解释目标文件的信息，包括了

ELF header的大小
目标文件类型（可重定位/可执行/共享）
机器类型(x86-64)
section header表的文件偏移
section header表的大小和条目数量

section header中的固定大小的条目描述了目标文件各个节的大小和位置。

在ELF header和section header表之间夹着的是目标文件的各个节。

4.2. sections

.text: 编译生成的程序的机器码
.rodata: 只读数据，例如：
- printf语句中的格式化字符串
- switch语句中的跳表
.data: 初始化过的全局和静态c变量。本地变量在运行时由栈维护，且不在.date或.bss节中出现。
.bss: 未初始化的全局和静态c变量，以及所有初始化为0的全局或静态变量。这个节在目标文件中不真正占有磁盘空间，仅作为占位符。这些变量在运行时被分配初始化为0的内存。
.symtab: 符号表包含了程序中定义和引用的函数和全局变量信息。和编译器内的符号表数据结构不同，该符号表不包括本地变量。
- 函数
- 全局变量
.rel.text: 该节包含了.text节中的一系列待修改的位置，这些位置需要linker把各个目标文件链接在一起后修改。总的来说，任何调用外部函数或引用了外部变量的指令都需要修改。调用本地函数的指令一般无需修改。注意到在可执行目标文件中，该信息是不需要的。但是该信息一般都会保留，除非用户指明linker不包含它。
- 调用外部函数的指令
- 引用外部变量的指令
.rel.data: 该节包含了本模块定义或引用的全局变量的重定位信息。总的来说，任何已初始化的全局变量，如果初始化值是一个全局变量地址或者外部定义的函数的地址，则需要被修改。
.debug: 该节包含了调试用的符号表。仅当编译期通过-g选项编译时显示。其中的条目包含了
- 本地变量
- typedef定义
- 程序中定义和引用的全局变量
.line: 该节包含了c源程序中行号和.text节的机器码指令的映射。仅当编译器通过-g选项编译时显示。
.strtab: 该节包含了一个字符串表，是一个以null结尾的字符串序列。其中的字符串用于 .symtab节、 .debug节和 section headers表中的section name。

5. 符号和符号表

每一个可链接的目标模块m，都包含了一个符号表，对应.symtab节。该符号表中含有三类符号：

在m中定义且被其他模块引用的全局符号。它们对应着非静态c函数和全局变量。
在m中被引用但是由其它模块定义的全局符号，称为externals。它们对应着其它模块定义的非静态c函数和全局变量。
仅被m定义和引用的本地符号。它们对应着静态c函数和带有static描述符的全局变量

linker符号由编译器(compiler)给出，例如如下程序

int f() {
    static int x = 0;
    return x;
}
int g() {
    static int x = 1;
    return x;
}

编译器会导出两个不同名的linker符号到汇编.s文件以交给汇编器(as)。接着，assembler会构建ELF目标文件中的 .symtab 节。它包含了如下条目构成的一个数组，条目的定义如下

typedef struct {
  int name; /* String table offset */
  char type:4, /* Function or data (4 bits) */
  binding:4; /* Local or global (4 bits) */
  char reserved; /* Unused */
  short section; /* Section header index */
  long value; /* Section offset or absolute address */
  long size; /* Object size in bytes */
} Elf64_Symbol;

name域： .strtab 节的字节偏移，指向null结尾的字符串。
value域：符号的地址
- 可重定位模块：value是该目标被定义的节的偏移。
- 可执行目标文件：value是运行时的绝对地址。
size域: 符号的字节数大小。
type域：通常该符号要么为data或function。也有可能表示
- 整个节的信息
- 源文件路径
binding域：表示该符号是本地或是全局的。
section域：每个符号都对应目标文件的某个节，section域给出符号对应节在section header表中的索引。有三种伪节(pseudosections)在section header表中不存在条目。且这些伪节符号仅存在于可重定位目标文件，可执行目标文件中不存在。
- ABS: 不应当被重定向的符号
- UNDEF: 在其它目标模块定义，在当前模块引用的符号
- COMMON: 未初始化的全局符号（还没有分配内存空间），
  - 对这类符号
    - value域给出对齐要求
    - size域给出最小的大小

COMMON和.bss节的区别在于

COMMON节给出：未初始化的全局变量，弱符号
.bss节给出：未初始化的静态变量，以及初始化为0的全局和静态变量

GNU readelf程序可以用于查看目标文件，例如：readelf -s main.o打印main.o目标文件中的符号表

Symbol table '.symtab' contains 12 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
0000000000000000     0 FILE    LOCAL  DEFAULT  ABS main.c
0000000000000000     0 SECTION LOCAL  DEFAULT    1 
0000000000000000     0 SECTION LOCAL  DEFAULT    3 
0000000000000000     0 SECTION LOCAL  DEFAULT    4 
0000000000000000     0 SECTION LOCAL  DEFAULT    6 
0000000000000000     0 SECTION LOCAL  DEFAULT    7 
0000000000000000     0 SECTION LOCAL  DEFAULT    5 
0000000000000000     8 OBJECT  GLOBAL DEFAULT    3 array
0000000000000000    33 FUNC    GLOBAL DEFAULT    1 main
0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND sum

注意到33字节的函数位于.text(即Ndx为1)节偏移量为0(即value值为0)处。全局的8字节的数组位于偏移量为0的.data节处。

6. 符号决议

linker在符号决议阶段需要将每一个符号引用关联到具体的符号定义。具体的符号定义由输入的可重定位目标文件的符号表给出。

目标

将每一个对符号的引用和唯一的一个符号表条目关联起来。

6.1. 编译器

本地符号和static修饰的本地静态变量的决议由编译器即可处理，只是对于static变量需要编译器生成对应的本地链接器符号(local linker symbol)。

而遇到对非本地定义的全局函数或变量的引用时，编译器假设它们在其它模块中定义，因而生成一个链接器符号表条目(linker symbol table entry)，且符号对应的section域为UND。并留给linker处理。

因而linker的符号决议主要处理全局符号。

6.2. Linker处理重复的符号名

当多个模块定义了同名符号时，Linux编译系统基于下列方法解决：

在编译期，编译器会将每个全局符号导出给汇编器并表明是strong或是weak符号。之后，汇编器会将这个信息隐含地编码在可重定位目标文件的符号表中。

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

基于上述标记，linker使用下面的规则决议符号的对应关系

不允许多个强符号由相同的名字，若出现，则编译会报错。
若一个强符号和多个弱符号具有相同的名字，选择强符号。
若多个若符号具有相同的名字，选择任意一个弱符号。

例如：不可出现两个全局main函数。不可出现两个均初始化的同名全局变量。

尤其当全局同名变量的类型不同时，规则2和3可能会引入一些bug如下：

/* foo5.c */
#include <stdio.h>
void f(void);

int y = 15212;
int x = 15213;
int main() {
    f();
    printf("x = 0x%x y = 0x%x \n", x, y);
    return 0;
}

/* bar5.c */
double x;
void f() {
    x = -0.0;
}

// 执行结果
linux> gcc -Wall -Og -o foobar5 foo5.c bar5.c
/usr/bin/ld: Warning: alignment 4 of symbol ‘x’ in /tmp/cclUFK5g.o
is smaller than 8 in /tmp/ccbTLcb9.o
linux> ./foobar5
x = 0x0 y = 0x80000000

在x86-64/Linux机器上，double占用8字节，int占用4字节。然而目标文件中x地址被决议为0x601020，y地址为紧邻的0x601024。因此当执行x = -0.0时，对x的赋值会覆写y的内存。

使用GCC时可以用-fno-common选项，当存在同名全局符号时会直接报错。或者使用-Werror选项，将所有警告都转换成error。

6.2.1. COMMON和BSS节的区别

当编译器翻译某一个模块时，它基于如下考虑对未初始化符号进行COMMON节或是BSS节的分配:

若是弱符号，则可能其它模块定义了对应的强符号，或者其它模块也定了同名的弱符号，因此需要把决定权留给链接器。
若是静态符号，则无论是否初始化，由于一定限定在当前模块。因此可以放入BSS。
若是初始化为0，则为强符号，则也可放入BSS。

6.3. 静态库链接

几乎所有编译系统都提供了静态库的功能。当构建可执行目标文件时，linker仅拷贝被应用程序引用的目标模块进行链接。

静态库的意义在于

解耦标准函数的实现和编译器的实现，减少编译器实现的复杂度（pascal语言由编译器识别标准函数并生成对应的代码）
避免任意程序都要链接完整的libc.a，也同时避免了对任意标准函数的修改需要库的开发者重新编译整个源文件
避免每个函数作为单独的可重定位文件出现时的易错性和耗时性

在静态库中，每个函数被编译成单独的目标模块，并被打包进单独的静态库文件中。应用程序之后即可使用库中定义的任意函数。例如，使用了c标准库和数学库可以使用如下命令编译和链接

1	`linux> gcc main.c /usr/lib/libm.a /usr/lib/libc.a`

Linux中，静态库以archive的文件格式被存储。archive格式由相连的可重定位目标模块构成，同时包含一个描述每一个成员目标模块大小和位置的头部。archive文件名带有 .a 后缀。

为了创建静态库，需要使用AR工具：

linux> gcc -c addvec.c multvec.c
linux> ar rcs libvector.a addvec.o multve.o

使用静态库时

linux> gcc -c main2.c
linux> gcc -static -o prog2c main2.o ./libvector.a
# 或者使用下面
linux> gcc -static -o prog2c main2.o -L. -lvector

-static参数告诉编译器驱动器linker需要构建一个完全链接的可执行目标文件，并且不需要额外load time链接即可运行
-lvector参数是libvector.a的缩写
-L.参数告诉linker在当前目录寻找libvector.a

6.4. Linker使用静态库解析引用

在符号决议阶段，linker依据在命令行中出现的顺序从左至右从可重定位目标文件中找到符号定义。linker依据以下算法工作：

构造集合$E$，可重定位目标文件集合，最终用于组合成可执行目标文件。集合$U$，未决议的符号集合。集合$D$，扫描过的文件中定义的符号。

对命令行中每一个输入文件f。若f为目标文件，将f加入$E$，更新$U$和$D$。
若f是archive文件，则linker尽可能决议$U$中的符号。即遍历archive文件中每一个成员目标文件，若包含某个$U$中的符号，则将该文件加入 $D$ ，并根据该目标文件更新$U$和$D$。linker重复该过程直到$U$和$D$不发生改变。此时$E$中不包含的archive中的目标文件会被丢弃。
若linker结束扫描时$U$非空，其会打印错误信息并终止。否则，linker合并$E$中的目标文件并构造输出可执行文件。

注意：该算法依赖于输入的archive和目标文件的顺序。若定义了某个符号的静态库在命令行参数中出现在引用了符号的目标文件之前，则该引用无法被决议。例如：

linux> gcc -static ./libvector.a main2.c
/tmp/cc9XH6Rp.o: In function ‘main’:
/tmp/cc9XH6Rp.o(.text+0x18): undefined reference to ‘addvec’

一般的静态库使用规则如下：

将库置于命令行参数的末尾
若库之间也存在依赖，则需要保证对库中对任意符号s的定义，至少应当存在于一个对s的引用之后。

7. 重定位

linker在符号决议完成之后，能够确定代码、数据节的具体大小。

之后的重定位过程会

将输入目标模块合并
为每个符号以及到它们的引用分配运行时地址

重定位的步骤如下

重定位节和符号定义：linker将所有相同类型的节合并为可执行目标文件的单个节。之后linker给每一个 输入模块的节 和 该模块定义的符号 赋予运行时地址。该步骤之后，每一条指令和程序中的全局变量都有了独一无二的运行时内存地址。
重定位各个节内部的符号引用: linker修改code和data节内的每一个符号引用并让它们指向正确的运行时地址。这一步依赖于可重定位目标文件中的可重定位条目(relocation entries)。

7.1. 可重定位条目(relocation entries)

当汇编器生成目标模块时，它不知道代码和数据最终的位置。因此， 每当汇编器遇到最终地址未定的引用，它会生成可重定位条目(relocation entry) 以让linker知道如何在合并目标文件并生成可执行文件时修改引用。代码的可重定位条目位于 .rel.text ，数据的可重定位条目位于 .rel.data 。

可重定位条目格式如下：

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: 给出linker修改引用的方式
addend: 用于某些符号的重定位

ELF定义了32种重定位类型。最基本的两种为：

R_X86_64_PC32: 重定位使用了32位PC相对地址的引用。即PC地址加上某个32位数值，该数值编码在指令中。
R_X86_64_32: 重定位使用了32位绝对地址的引用，该数值编码在指令中。

这两种重定位类型支持x86-64小代码模型。即可执行目标文件中代码和数据的总大小小于2GB，因此可在运行时使用32位PC相对地址访问（2G带正负）。使用超过2G内存的程序需要使用-mcmodel=medium或-mcmodel=large参数。

7.2. 重定位符号引用

重定位算法如下，其中的ADDR(s)表示节（section）的运行时地址，ADDR(r.symbol)表示符号的运行时地址。第三行的refptr给出了引用在节中的地址。

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

下面给出之前程序进行重定位的例子：

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 array Relocation entry
e: e8 00 00 00 00 callq 13 <main+0x13> sum()
    f: R_X86_64_PC32 sum-0x4 Relocation entry
13: 48 83 c4 08 add $0x8,%rsp
17: c3

如上给出了main.o的反汇编代码，可以使用OBJDUMP程序得到，使用objdump -dx main.o。main函数使用了两个全局变量：array和sum。汇编器给出的重定位条目展示在对应代码的下面一行

7.2.1. 重定位PC相对引用

第六行中，main调用了sum.o中定义的sum函数。call指令在节偏移0xe处，包含的一个字节的opcode为0xe8，后面跟着的是作为占位符的32位相对地址（即对sum函数的引用）。

给出的sum重定位符号各个域如下

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

假设此时有

$ADDR(s) = ADDR(.text) = 0x4004d0$ $ADDR(r.symbol) = ADDR(sum) = 0x400de8$

根据重定位算法，引用所在位置

\[refaddr = ADDR(s) + r.offset = 0x4004d0 + 0xf = 0x4004df\]

之后更新的值为

\[*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr) = (unsigned) (0x4004e8 + (-4) - 0x4004df) = (unsigned 0x5)\]

结果的可执行目标文件，call指令将有下面的格式

4004de e8 05 00 00 00 callq 4004e8 <sum>

在运行到0x4004de时，call指令会被cpu执行。当cpu执行时，pc值为0x4004e3，即代码中下一条指令的位置。为执行call指令，cpu会

push pc寄存器到栈中
pc = pc + 0x5 = 0x4004e3 + 0x5 = 0x4004e8，即对应了sum函数的位置

7.2.2. 重定位绝对引用

第四行中，mov指令将array的地址拷贝到%edi寄存器中。mov指令从节偏移0x9处开始，并包含了1字节的opcode0xbf，紧接着的是32位的array的绝对引用地址。对应的重定位条目r为：

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

此时假设linker给出

\[ADDR(r.symbol) = ADDR(array) = 0x601018\]

linker会进行如下更新

\[*ref-tr = (unsigned) (ADDR(r.symbol) + r.addend) = (unsigned) (0x601018 + 0) = (unsigned) (0x601018)\]

结果的指令为

4004d9:  bf 18 10 60 00      mov $0x601018,%edi

8. 可执行目标文件

一个ELF可执行目标文件如下图所示：

和可重定位目标文件类似，可执行目标文件的ELF header描述了文件的整体格式，同时包含了程序的entry point。

.init节包含了_init函数，会被程序的初始化代码调用。由于可执行文件已经被完全链接(fully linked)，因而不包含.rel节。

ELF可执行文件中连续的部分被映射到连续的内存段中。这种映射由segment header table描述，可以通过OBJDUMP查看，如下：

Read-only code segment
LOAD off 0x0000000000000000 vaddr 0x0000000000400000 paddr 0x0000000000400000 align 2**21
filesz 0x000000000000069c memsz 0x000000000000069c flags r-x
Read/write data segment
LOAD off 0x0000000000000df8 vaddr 0x0000000000600df8 paddr 0x0000000000600df8 align 2**21
filesz 0x0000000000000228 memsz 0x0000000000000230 flags rw

off: 目标文件偏移
vaddr/paddr: 内存地址
align: 对齐要求
filesz: 目标文件中段大小
memsz: 内存中段大小
flags: 运行时许可

注意到行1，2描述的第一个段(the code segment)具有读/执行权限，从内存地址0x400000处开始，总内存大小为0x69c字节。由可执行目标文件的前0x69c个字节进行初始化，包含了.init，.text和.rodata节。

行3，4描述的第二个段(the data segment)具有读/写权限，从内存地址0x600df8处开始，总内存大小为0x230，以文件中偏移量为0xdf8的.data节的0x228个字节进行初始化。段中剩余8字节对应着.bss中将被初始化为0的数据。

对任何段s，linker必须选择一个起始地址vaddr，使得

\[vaddr\;mod\;align = off\;mod\;align\]

其中，off是目标文件中相关节的偏移量，align是program header中定义的对齐要求。例如上述数据段有

\[vaddr\;mod\;align = 0x600df8\;mod\;0x200000 = 0xdf8\]

并且

\[off\;mod\;align = 0xdf8\;mod\;0x200000 = 0xdf8\]

这种对齐要求是一种优化。能够让目标文件中的段更高效地在执行时对应到内存。这是因为虚拟内存被组织成连续的以2为底的字节块。

9. 装载可执行目标文件

在shell中执行./prog时，shell会假设prog为可执行目标文件，通过execve函数调用loader。loader将可执行目标文件中的代码和数据从磁盘拷贝到内存中，并从entry point开始执行程序。该过程即被称为loading。

每一个运行的Linux程序的运行时内存镜像如下：

代码段从地址0x400000开始，紧接着的是数据段。然后是运行时heap和为共享模块保留的区域。用户栈从合法的最大用户地址（$2^{48}-1$）处开始，并向下增长。栈之上的从$2^{48}$地址开始的空间为内核数据和代码保留。

事实上，代码和数据段之间可能会有gap，这由于之前说的对齐要求导致。同时linker可能针对栈、共享库和堆使用ASLR(地址布局随机化)，虽然这些区域的位置在每次运行时均不同，他们的相对位置是一定的。

当loader运行时，会根据program header table将可执行目标文件拷贝到内存。之后loader会跳转到程序entry point，即_start函数的地址。该函数在系统目标文件crt1.o中定义。_start函数会调用system startup function（即libc.so中定义的__libc_start_main函数）。它会初始化执行环境、调用用户态的main函数、处理返回值，并在必要时返回控制给内核。

10. 小结

编译器、汇编器已经处理的问题：生成重定位条目。
符号决议的意义：将对全局符号的引用绑定到唯一的一个符号表项上。处理不同目标文件中符号冲突。
重定位的意义：合并多个目标文件同时分配运行时地址。
静态变量也存在于符号表中：需要重定位阶段linker分配全局地址。

11. 参考

CH7 Linking Computer Systems. A Programmer’s Perspective