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;

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 共用的 symbolSymbol 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 有不一样的 sizelinker 还会给出警告

也就是说若编译选项为 -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.ob.o 中引用了 a.o且在 libabc.aa.o 位于 b.o 之前那么第一次迭代中只会使用 b.o第二次迭代才会使用 a.oc.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: 有很多种 relocationCS:APP 中只介绍其中的 R_X86_64_PC32R_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]);
}

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

.rela.textaaddend4是直接得到 a[1] 而非 a[0] 的地址fooaddend-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所示

Linux x86-64 run-time memory image

errata 中指出栈的起始地址并不是 24812^{48}-1

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

loader 加载可执行文件时首先创建 memory image然后根据 program header table 将可执行文件的内容映射到内存中最后跳转到程序的 entry pointC 语言程序的 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 的命令来使用共享库

运行 mainloader 会在进入 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_NOWRTLD_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.18GOT[3] 中存放了全局变量 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 所示

PLT 原理示意图

整个流程就是

  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.soanotherwrapper.so这时为了能在 wrapper function 中调用原本的函数就需要 在运行时加载共享库

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

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


  • 文章作者:
  • 原文链接:https://ouuan.moe/post/2022/10/csapp-7
  • 许可协议: 本文采用 CC BY-SA 4.0 许可协议进行授权,未满足 许可协议要求 不得转载。
  • 额外说明:本文包含少量直接从 CS:APP 中复制的代码、图片,本文作者对其不拥有版权。