CS:APP 第七章学习笔记

CS:APP 第七章 “Linking” 的学习笔记。

这章的主要内容为程序的链接。学习链接有助于：理解链接报错，避免链接相关的 bug，理解变量（函数）的作用域，理解程序运行过程中与链接相关的步骤，了解如何使用共享库（动态链接库）。

Compiler Drivers

编译源文件其实分成若干步骤，compiler driver（如 gcc）会依次调用这些步骤，可以用 gcc -v 来查看这些步骤的详细信息。

1. cpp: 预处理，源代码 .c -> intermediate file .i
2. cc1: .i -> 汇编代码 .s
3. as: .s -> relocatable object file .o
4. ld: 链接，多个 .o (或 library) -> executable object file

P.S. 中间步骤的文件也可以作为参数传递给 gcc，例如 gcc a.s -o a。

Static Linking

静态链接主要有两个任务：

1. Symbol resolution: relocatable object file 中有很多 symbol，包括函数、全局变量、静态变量等，linker 需要将每个 symbol reference 对应到一个 symbol definition。
2. Relocation: relocatable object file 中地址从 0 开始，linker 需要将每个 symbol definition 重新分配到正确的地址，并相应地修改每个 symbol reference。

Object Files

object file 分为三种：

1. Relocatable object file
2. Executable object file
3. Shared object file: 一种特殊的 relocatable object file，可以在 load time 或 run time 进行动态链接

object file 有不同的格式，Windows 使用 Portable Executable (PE) 格式，macOS 使用 Mach-O 格式，现代的 x86-64 Linux/Unix 系统使用 Executable and Linkable Format (ELF) 格式。本章会基于 ELF-64。

Relocatable Object Files

ELF relocatable object file 通常包含以下 section：

1. .text: 程序的机器码
2. .rodata: 只读的数据
3. .data: 需要初始化的全局变量和静态变量
4. .bss: 未初始化或初始化为零的全局变量和静态变量，它们在运行时会以零为初值，从而在 object file 中不占据文件大小
5. .symtab: symbol table，存储 symbol（函数、全局变量）的信息，不需要 -g 编译选项，但不含局部变量的信息
6. .rel.text: 列出了 .text 中在链接时需要修改的地方，一般是调用外部函数或引用全局变量时需要修改，而 调用本地函数不需要修改
7. .rel.data: 列出了 .data 中在链接时需要修改的地方，一般是全局变量的值为其他全局变量或外部函数的地址时需要修改
8. .debug: 调试信息，包含局部变量的信息、typedef 信息、源代码等，需要 -g 编译选项才有
9. .line: 源代码与机器码行号间的对应关系，需要 -g 编译选项才有
10. .strtab: 一堆字符，用于其它 section，可以指向其中一个位置来表示一个字符串（从这个位置起到 \0 为止）

Symbols and Symbol Tables

对 linker 来说，symbol 有三种：

1. 本地定义，可以被外部访问的: C 中非 static 的函数和全局变量
2. 外部定义的，例如 C 中 extern 的全局变量
3. 本地定义，外部不可访问的: C 中 static 的函数和变量

一个 ELF64 symbol 包含如下信息（CS:APP Figure 7.4）：

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;

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;

value 在 relocatable object file 中是 symbol 的地址相对于 section 开头的 offset，在 executable object file 中是 symbol 的绝对地址。

section 是 object file 的 section 之一（的 index），在 relocatable object file 中还可以是一个 pseudosection:

• ABS: 不应被 relocate 的 symbol
• UNDEF: 未定义（在其他 module 中定义）的 symbol
• COMMON: 多个 module 共用的 symbol（见 Symbol Resolution），此时 value 的值给出 data alignment 的要求，size 给出的是 minimum size

未初始化的静态变量以及初始化为零的全局或静态变量会放在 .bss。

未初始化的全局变量，如果启用了 -fcommon 编译选项则会放在 COMMON，否则放在 .bss。在 gcc 9 及之前默认选项是 -fcommon，而自 gcc 10 起默认选项是 -fno-common。在 C++ 中 -fcommon 是无效的，未初始化的全局变量总是放在 .bss。

可以使用 readelf -s a.o 来查看 a.o 的 .symtab。

Symbol Resolution

Symbol resolution 即把每个 symbol reference 对应到一个 symbol definition。

local symbol 的 resolution 是容易的，因为编译单个 module 时就保证了 local symbol 是唯一的。

global symbol 可能遇到几种情况：

• 只有一个 module 里定义了这个 global symbol，则使用这个 symbol
• 没有任何 module 里定义了这个 global symbol，则报错 undefined reference
• 在多个 module 里定义了这个 global symbol，则：
  • 如果其中有多个 symbol 不在 COMMON 段，则报错 multiple definition
  • 如果其中只有一个不在 COMMON 段，则使用这个 symbol
  • 如果这些 symbol 都在 COMMON 段，则使用其中 size 最大的一个（如果 size 相同则使用哪个是没有区别的）；如果这些 symbol 有不一样的 size，linker 还会给出警告

也就是说，若编译选项为 -fcommon，如果在多个 module 中定义了同一个全局变量且其中最多有一个初始化了，则可能导致意外的结果。可以理解为，multiple definition 在本质上是 multiple initialization。

在 C++ 中，函数重载、类方法会通过 mangling 来使得函数的每种重载有独特的 symbol name。

Static Libraries

Static library 其实就是一堆 object file 包装在一起，它的好处是：

1. 不用每次重新编译（比起提供源码）
2. 使得库和编译器解耦（比起将库函数内置到编译器中）
3. 只需将用到的 object file 复制到最终的可执行文件中，避免空间浪费（比起提供单个 object file）
4. 可以自动选择用到的 object file，在编译命令中只需指定少量库的名称（比起提供一堆 object file）

可以使用类似 ar rcs libabc.a a.o b.o c.o 的命令来创建一个 static library。

在编译时，有两种使用 static library 的方式：

• 直接将 static library 的路径作为参数: libabc.a
• 使用 -lname 来使用 libname.a，但需要使用 -Ldir 来将 dir 加入到 -l 的搜索路径之中: -L. -labc

特别地，编译器会自动将 libc.a 提供给 linker，不需要手动指定。

在链接时，linker 会依次处理每个参数：

• 如果一个参数是 object file 就一定会使用
• 如果是 static library，则会依次查看其中包含的每一个 object file，如果一个 object file 中定义了某个当前引用了但仍未定义的 symbol，则会使用这个 object file，而这样的过程会反复迭代进行直到没有新的 object file 被使用为止（例如 main.c 引用了 b.o 而没有引用 a.o，而 b.o 中引用了 a.o，且在 libabc.a 中 a.o 位于 b.o 之前，那么第一次迭代中只会使用 b.o，第二次迭代才会使用 a.o，而 c.o 不会被使用）

这样的过程使得编译命令中参数的顺序以及 static library 中 object file 的顺序可能影响编译结果：

• 一般来说需要将 library 放在编译命令的末尾，否则处理一个 library 时还没有引用其中的 symbol，就不会使用相应的 object file，最后就会报错 undefined reference
• 如果多个 library 之间有依赖关系，需要将被其他 library 依赖的 library 放在靠后的位置
• 如果多个 library 之间有循环依赖，可能需要在编译命令中多次指定同一个 library（或者也可以将这两个 library 合并成一个，这样的话通过多次迭代就可以解决循环依赖）
• library 的设计应当避免 multiple definition，但理论上存在不同的参数顺序或 static library 中 object file 的顺序导致 multiple definition 的可能

Relocation

relocation 分为两步：

1. 给 symbol definition 重新分配内存地址
2. 相应地修改 symbol reference

第一步是简单的，把各个 object file 中的各个 section 分别拼在一起即可。

为了让 linker 知道如何修改 symbol reference，需要让 linker 知道：

1. 需要被修改的 symbol reference 在哪
2. 需要修改成什么

在 relocatable object file 的 .rel.text 和 .rel.data 中存放了相关的信息，一条这样的信息称作一个 relocation entry，包含的内容为：

• offset: 这个 symbol reference 相对于其所在的 section 的偏移量。也就是说，在这个 reference 所在的 section 的地址的基础上加上 offset 就得到了这个 reference 的地址。
• type: 有很多种 relocation，CS:APP 中只介绍其中的 R_X86_64_PC32 和 R_X86_64_32 两种。
• symbol: 被 reference 的 symbol 在 symbol table 中的 index。
• addend: 计算 symbol 地址时加在最后的常数（见后文）。

简单来说，R_X86_64_32 使用绝对地址进行定位，R_X86_64_PC32 使用相对于 PC 的地址进行定位，且这两种类型的 relocation 都只支持 32 位的地址（如果一个程序的大小超过 2GB，就需要指定编译选项 -mcmodel=medium/large）。

• R_X86_64_32: 修改后的 reference 为 symbol 的地址加上 addend
• R_X86_64_PC32: 修改后的 reference 为 symbol 的地址与 reference 的地址之差加上 addend；需要注意的是，是与 reference 的地址之差，而不是与执行到 reference 所在语句时的 PC 之差，所以通常会需要通过 addend 来修正

可以使用 objdump -dx 以在反汇编结果中显示 relocation entry，或者使用 readelf -r 显示所有 relocation entry。

例如，使用 GCC 8.5 编译

int foo(int *arr);

int a[3] = {1, 2, 3};
int *b = &a[2];

int bar()
{
    return foo(&a[1]);
}

int foo(int *arr);

int a[3] = {1, 2, 3};
int *b = &a[2];

int bar()
{
    return foo(&a[1]);
}

readelf -r:

Relocation section '.rela.text' at offset 0x250 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000001  000a0000000a R_X86_64_32       0000000000000008 a + 4
000000000006  000b00000002 R_X86_64_PC32     0000000000000000 foo - 4

Relocation section '.rela.data' at offset 0x280 contains 1 entry:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000000  000a00000001 R_X86_64_64       0000000000000008 a + 8

Relocation section '.rela.text' at offset 0x250 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000001  000a0000000a R_X86_64_32       0000000000000008 a + 4
000000000006  000b00000002 R_X86_64_PC32     0000000000000000 foo - 4

Relocation section '.rela.data' at offset 0x280 contains 1 entry:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000000  000a00000001 R_X86_64_64       0000000000000008 a + 8

在 .rela.text 中，a 的 addend 是 4，是直接得到 a[1] 而非 a[0] 的地址；foo 的 addend 是 -4，是因为 reference 的地址是 reference 所在的 jmp 指令的下一条指令的地址减 4，导致 PC 的地址加上 foo 的地址减去 reference 的地址得到的是 foo 的地址加 4，需要 addend 来修正。

Executable Object Files

可执行文件的内容大体上和 relocatable object file 类似，主要的区别是：

• 在 ELF header 中指定了程序的 entry point
• 有一个 .init section，定义了一个简单的函数，用来初始化程序
• 有一个 program header table，描述了程序文件与内存的对应关系，即要把文件的哪一段映射到内存的哪一段，地址如何对齐，以及每一段的权限（.init、.text、.rodata 的权限为 r-x，.data 和 .bss 的权限为 rw-）
• .symtab、.debug、.line、.strtab 在执行时不会加载到内存中
• 如果 fully linked，则没有 .rel section

Loading Executable Object Files

在程序运行时，run-time memory image 大致如下图（CS:APP Figure 7.15）所示：

（errata 中指出，栈的起始地址并不是 $2^{48}-1$。）

因为地址对齐、address-space layout randomization 等原因，实际上的内存结构会与上图有一定的差异，但每一段的相对位置是和图中一致的。

loader 加载可执行文件时，首先创建 memory image，然后根据 program header table 将可执行文件的内容映射到内存中，最后跳转到程序的 entry point。C 语言程序的 entry point 是 _start 函数（在 crt1.o 中定义）的地址，_start 又会调用 __libc_start_main 函数（在 libc.so 中定义），进行运行环境的初始化，然后调用 main 函数，最后对返回值进行处理。

Dynamic Linking with Shared Libraries

静态库有一些问题：

1. 更新静态库需要重新链接
2. 每个程序都有一份库的拷贝，会造成空间的浪费

共享库 (shared library) 可以解决这些问题。共享库可以在 run time 或者 load time 被动态链接。动态链接由 dynamic linker 完成。共享库也被称作 shared object，在 Linux 中后缀名为 .so，在 Windows 中被叫做 DLL。

共享库在两个层面上被共享：

1. 在文件系统上只有一份 .so 文件，而在可执行文件中没有库的拷贝
2. 在内存中共享库的 .text section 的单份拷贝可以被多个进程同时使用

可以用类似于 gcc -shared -fpic a.c b.c c.c -o libabc.so 的命令构建共享库。编译选项中 -shared 告诉编译器要生成 shared object，-fpic 用来生成 position-independent code。

可以用类似 gcc main.c ./libabc.so -o main 的命令来使用共享库。

运行 main 时，loader 会在进入 entry point 前在 .interp section 中发现 dynamic linker ld-linux.so，于是让 dynamic linker 完成共享库的 relocation 并修改程序中的 symbol reference，最后将控制权交还给程序。

Loading and Linking Shared Libraries from Applications

除了在编译时指定要链接到的共享库并在 load time 链接，也可以在 run time 加载并使用共享库。

C 语言中的相关函数放在 dlfcn.h 头文件中，编译时需要 -ldl 来使用这些函数：

• void *dlopen(const char *filename, int flag): 加载共享库

  • 返回值: 成功加载则返回 handle，否则返回 NULL

  • filename: 共享库文件名

  • flag: 影响如何处理共享库中引用的 external symbol，必须包含 RTLD_NOW 和 RTLD_LAZY 两者之一

    • RTLD_NOW: 立即 resolve 所有 external symbol
    • RTLD_LAZY: 等到运行共享库中的代码时再 resolve external symbol
    • RTLD_GLOBAL: 之后给其他共享库 resolve external symbol 时可以使用当前这个共享库

    如果编译程序时启用了 -rdynamic 选项，在 resolve external symbol 时，除了使用其他加载时启用了 RTLD_GLOBAL 选项的共享库，也可以使用程序自身的 global symbol。

• void *dlsym(void *handle, char *symbol): 获得共享库中某个 symbol 的地址

  • symbol: symbol 名称

  • 返回值: 成功获取则返回 symbol 地址，否则返回 NULL

• int dlclose(void *handle): 关闭共享库

  • 返回值: 成功关闭则返回 0，出错则返回 -1

• const char *dlerror(void): 获取最后一次调用 dlopen / dlsym / dlclose 的报错信息，如果最后一次调用没有出错则返回 NULL

CS:APP 给出了一份参考代码 code/link/dll.c。

Position-Independent Code (PIC)

共享库的一条重要性质是它的代码段在内存中只有一份，而可以被多个进程共享，这就使得它的代码中的 symbol reference 不能在动态链接时被修改，适用于静态链接的 relocation 无法完成，所以共享库的代码需要是 position-independent 的。

PIC 的主要思路基于以下两点：

1. 虽然共享库的代码段是共享的，但数据段是每个进程各有一份的
2. 无论整个共享库被放到内存的哪个位置，代码段和数据段地址的距离是固定的（这与上一条不矛盾，应该是因为虚存）

因此，可以在数据段中存放效果相当于 relocation 的信息，来间接达到 relocation 的效果。说白了就是，因为没法修改代码段，所以把 symbol 的地址放到数据段里。具体实现中，数据段的开头有一个 global offset table (GOT)，表中每一项都是一个地址，可以由 dynamic linker 进行修改，而由于代码段和数据段的地址距离固定，就可以用 PC-relative 的方式寻址到表中的项。

PIC data reference 是简单的，只要在 GOT 中为每个 data symbol (全局或 static 变量) 创建一个表项，在动态链接时由 dynamic linker 修改这些项，而在代码中通过这个表项来间接地进行 data reference，例如 (CS:APP Figure 7.18，GOT[3] 中存放了全局变量 x 的地址)：

    movq Ox2OO8b9(%rip), %rax   # %rax = *GOT[3] = &x
    addl $0x1, (%rax)           # ++x

    movq Ox2OO8b9(%rip), %rax   # %rax = *GOT[3] = &x
    addl $0x1, (%rax)           # ++x

如果是本地定义的变量，也可以使用 PC-relative 的定位方式直接引用，而只对外部定义的变量使用 GOT，但编译器也可能选择不做这样的区分而是使用统一的方法来处理。

PIC procedure call 也可以和 data reference 一样处理（可以用 -fno-plt 编译选项来这样做），但实际上会使用名为 lazy binding 的技术进行优化。

这是因为，链接到一个共享库时，往往最终会调用的只是它提供的大量函数中的一小部分，如果对整个共享库用到的外部函数都在动态链接时计算出相应的 offset，就可能造成浪费。而 lazy binding 则是在第一次调用某个外部函数时绑定这个函数的地址。

lazy binding 基于一个名为 procedure linkage table (PLT) 的结构。PLT 位于代码段中，表中的每一项其实是三条指令，如 CS:APP Figure 7.19 所示：

整个流程就是：

1. 调用 addvec 时，实际上调用的是 PLT[2] 的地址
2. PLT[2] 的第一条指令会跳转到 GOT[4]，GOT[4] 里一开始放的是 PLT[2] 的第二条指令，所以首次调用 PLT[2] 时就从第一条指令跳到第二条指令
3. 第二条指令是往栈里压入 addvec 的 ID，是用来告诉 dynamic linker 这是哪个函数
4. 第三条指令会跳转到 PLT[0]
5. PLT[0] 的第一条指令是往栈里压入 relocation entries 的地址，第二条指令是跳转到 dynamic linker
6. dynamic linker 通过放在栈中的函数的 ID 以及 relocation entries 计算出 addvec 的地址，放在 GOT[4]，然后跳转到 addvec
7. 因为一路上都是 jmp，跳转到 addvec 后可以正常返回到调用 PLT[2] 的位置
8. 第二次调用 PLT[2] 时，GOT[4] 里已经是 addvec 的地址，所以就在 PLT[2] 的第一条指令处跳转到了 addvec

Library Interpositioning

Linux 的链接器支持一个名为 library interpositioning 的技术，可以用来把共享库的函数替换掉，一般会换成一个 wrapper function 用来 trace，但也可以换成完全不同的东西。

看了下中文版 CS:APP，这个东西竟然叫“库打桩”（

编译时的 library interpositioning 就是用 #define 换掉某个函数 ，在机房里被 #define sort random_shuffle 过的大家想必对此非常熟悉。

链接时的 library interpositioning 是给 linker 传参 --wrap foo，然后调用 foo 就会实际上调用 __wrap_foo，而调用 __real_foo 则会调用原本的 foo。一般会给 gcc 而非 ld 传参，就是用 gcc -Wl,--wrap,foo 代替 ld --wrap foo，其中 -Wl 表示给 linker 传参，后面的逗号会被换成空格。

运行时的 library interpositioning 是在运行程序时设置环境变量 LD_PRELOAD="/path/to/wrapper.so /path/to/anotherwrapper.so"，然后在使用任意共享库中的函数之前就会优先尝试使用 wrapper.so 和 anotherwrapper.so。这时，为了能在 wrapper function 中调用原本的函数，就需要 在运行时加载共享库。

如果想看具体实现，可以参考 CS:APP。

编译时的 library interpositioning 需要修改源代码，链接时的 library interpositioning 需要获取到 object file 并重新链接得到可执行文件，而运行时 library interpositioning 只需要设置环境变量，不需要对可执行文件进行任何修改，可以方便地对很多不同程序的某个函数调用进行跟踪。