💻 CSC3060 Week 14 Linking

Week 14 Linking

gcc 的四个步骤：cpp 预处理、cc1 编译、as 汇编、ld 链接；前三个步骤都属于 Translators。Source file 经过 Translators 变成 relocatable object file，然后经过 Linker 变成 executable object file。

Linker 可以：做 LTO、解开符号定义、让 segment 对 page size 对齐以优化、重定位全局变量引用和函数调用。

Why Linker?

Modularity

Linking (链接)，就是把多个代码和数据片段收集起来，组合成一个可以被加载到内存中执行的目标文件。执行链接的 Linker 很重要，因为它们让 Separate Compilation 成为可能。

Separate compilation：Translator 分别把 main.c 和 func.c 独立编译为 main.o 和 func.o (Relocatable object file)，然后 Linker 再关联两个文件产生 Executable object file。这样大型文件就可以分为小模块，更便于修改，只要修改对应模块然后重新编译并链接，不必改别的文件。

可以把常用函数打包成库或者使用公共库 (比如 libm, libc)：C 的头文件负责“声明”这些库里有什么函数、类型、变量 (#include <...>)。

Efficiency

时间效率：多个 .c 文件可以分别编译，甚至并行 (concurrent) 编译。修改一个模块不影响别的。

空间效率：很多常用函数不需要每个程序都自己写，链接器可以把库函数接进来。

  • Option 1: Static Linking，静态链接在生成 exec. 时，把用到的库函数代码直接复制进去，最终 exec. 里会包含这些函数相关的机器码。程序比较独立，但是浪费内存。
  • Option 2: Dynamic linking，动态链接后 exec. 里不直接放库函数代码，而是 run-time 加载共享库。甚至运行时多个程序都依赖某个库函数时 (比如 printf) 可以共享同一份库 (libc.so) 代码。

Linker 在做什么?

核心是 Symbol resolution (符号解析) 和 Relocation (重定位)

Symbol resolution

在链接器眼里，程序里的函数名、全局变量名等都叫 symbol，符号。

⚠️ 它只在乎全局变量、函数、外部引用函数、static 局部变量。比如：

int arr[2] = {1, 2};
int main() {
    int val = sum(array, 2);
    static s = arr[0] + 2;
    return val + s;
}

其中，Linker 需要知道以下符号的意义：

array (def. symbol)、main (def. symbol)、sum (ref. symbol)、s (def. symbol)

  • 每个 .o 文件里都有一个 symbol table (符号表)，由 assembler 创建；

  • 一个含有多条记录的数组，每个记录包括符号名字、大小、所在 section、location (offset)、类型 (def. / ref.)；

  • 普通局部变量在运行时通常放栈上，编译器自己处理，不需要 linker 解析；

  • 符号解析时，Linker 将出现的符号和符号定义记录一对一对应；

  • 符号表通过 objdump -t xxx.o 或者 readelf -s xxx.o 读取。

Relocation

即，将所有机器码和符号整理或者移动到 exe 中的最终绝对地址

  1. 合并各个 .o 文件的相同 section

  2. 给每个符号分配最终地址

  3. 修改代码和数据中对这些符号的引用


ELF

Executable and Linkable Format (ELF)：将 Relocatable object files (.o)、Executable object files (a.out)、Shared object files (.so) 三种对象文件统一二进制格式，统称为 ELF 文件

  • .so 是一种可以在加载时或运行时动态链接的目标文件，比如 libc.so、libm.so。在 Windows 中称作 Dynamic Link Libraries (DLLs)。

ELF 格式

在内存中分为多个 section，从基址开始依次是——

  • ELF Header 记录这个文件的基本信息：

    字长：32-bit / 64-bit

    字节序：little endian / big endian (大小端机)

    文件类型：.o / exec. / .so

    机器类型：x86-64 / RISC-V 等

  • exec. 单独需要 Segment header table (for OS)：Page size, virtual address memory segments (sections), segment sizes。告诉操作系统哪些内容要加载到内存，加载到什么虚拟地址，权限是什么：可读、可写、可执行

  • .text section 存放程序码 (Read Only)

  • .rodata section 存放只读数据 (Read Only)：jump tables, 字符串常量 (比如 printf("hello\n"); 的字符串) …

  • .data section 存放已初始化的全局变量和 static 变量 (R&W)，比如：

    int x = 10; static int y = 20;

  • .bss section 存放未初始化的全局变量和 static 变量的占位大小 (R&W)，比如：

    int x; static int y;

    .bss 很重要：它在 ELF 文件里 ⚠️ 不真正占用对应大小的文件空间，只记录预留大小、不存实际内容。因为初始化默认全是 0，只需在 .bss 的 section header 里记录 “运行时需要分配多少空间”。比如：

    int big_array[1000000]; 就需要记录 “运行时需要 4 MB 空间，加载时请把这 4 MB 清零”，⚠️ 而不需要 ELF 文件里傻傻的保存 4 MB 的 0。

  • .symtab section 存放符号表和 section 名/位置

  • .rel.text section 存放 .text section 的 relocation 信息，代码里有哪些地方的最终地址在 .o 中还不知道，链接时需要修正。记录在 exec. 中需要修改的代码位置和信息，比如引用函数/库函数。

  • .rel.data section 存放 .data section 的 relocation 信息，比如一个全局指针：

    int x; int *p = &x;，p 的初值依赖 x 的最终地址，因此 .data 里也可能需要 relocation

  • .debug section 记录调试信息：如果用 gcc -g 就会生成调试相关内容，供 gdb 等工具使用

  • Section Header Table 记录每个 section 的：名字、offset、大小、属性


链接器符号

Linker Symbols 分类

用 static 声明局部符号

Global symbols：某个模块定义的符号，可以被别的模块引用，e.g., ⚠️ 非静态 C 函数、非静态全局变量

External symbols：由另一个模块定义，但本模块借用的跨模块全局符号

Static Local symbols：某个模块定义且独属于它的符号，e.g, static C 函数、 static 全局变量、⚠️ 函数内的 static 局部变量

Non-static Local symbols：比如 section symbol、file symbol 等等

⚠️ Linker 的 local symbol ≠ C 语言的 local variable —— 前者是声明 static 的一切数据或函数，后者是函数/循环体内局部声明的临时变量。Linker 对于后者 (local var.) 一无所知，因为它们在 stack 上。

⚠️ Linker 能看到 ≠ 其他模块 (.c) 能引用 —— 链接器能看到也会在符号表中记录 global static variable (算一种 local symbol)，但是不可共享。如果是 global non-static variable (算一种 global symbol)，别的模块可以通过 extern 访问。

static int g = 10;        // linker local symbol，不是 local variable
static void helper() {}    // linker local symbol，不是 local variable
int f() {
    int a = 1;            // local variable，不是 linker local symbol
    static int b = 2;     // 既是 local variable，也是 linker local symbol
    return a + b + g;
}

Local Variables 不存在于 symbol table！

Local non-static C variables：栈上

Local static C variables：.bss (未初始化) 或 .data (已初始化)，某些只读的 static const 数据放到 .rodata

局部变量重名：编译器会在 .data section 给每一次定义局部变量 x 都保留一个位置，在符号表中标记为不同名字，e.g., x, x.1721, x.1724.

强符号与弱符号

Strong symbols:

  • 所有函数
  • 已初始化全局变量

Weak symbols:

  • 未初始化全局变量
  • 或者声明了 extern

Rule 1：不能有多个 strong symbols

// p1.c
int x = 1;

// p2.c
int x = 2;

链接时报错：Link time error: multiple definition of x

Rule 2：一个 strong，多个 weak，选 strong

// p1.c
int x = 42;

// p2.c
double x;

最终所有对 x 的引用都会指向 strong symbol，也就是 int x = 42 那个，但 p2.c 中仍然认为 x 属于 double。

Rule 3：多个 weak symbols，任选一个

这很危险，因为你以为两个文件里是不同变量，实际上它们却可能被合并成同一个；

用 gcc –fno-common override (覆盖) 这个默认操作。

// main.c
int x, y;
p1() {}
// help.c
double x;
p2() {}

p2 写 x 可能覆盖 y，因为 double 有 8bits，会覆盖 main 中两个 4bits 的整数。

如果 help.c 中改成 double x = 42.42，不仅仍然有覆盖风险，会触发隐式强转换 ——

Linker 不做类型检查！

// var.c
double x = 4.242;

// main.c
long int x;
int main() {
    printf("%ld\n", x);
}

根据 Rule 2，Linker 会把对弱符号 long int x 的引用指向引用强符号 double x，压根不检查 x 到底是 double 还是 long int。

最后打印出一个诡异的被隐式强转换为整型的小数，数值大到离谱。

全局变量的使用建议

⚠️ 能不用全局变量就不用。

如果必须用，那么：

  1. 能标 static 就 static：声明这个变量/函数只属于当前 .c 文件，不是对外接口，外部用 extern 引用时拒绝并报错：undefined reference to counter

  2. 定义全局变量时尽量初始化：这样大不了重复定义报错，不会拿混乱的定义的做下去

  3. 如果只是引用外部全局变量，用 extern：作为弱符号处理，如果外部未定义则报错——

    • 比如头文件只声明 extern int x 存在，.c 里要用到的位置再定义 x。

    • 错误写法是把定义塞进头文件，这样每个包含 global.h 的 .c 文件都可能产生一个 x，导致重复定义或弱符号混乱。


Relocation

所有 .c/.h 文件的 .text 和 .data section 重定位并合并到 exec. 文件的对应区域。

以 x86-64 为例：

PC-relative addressing：在 .o 阶段，编译器不知道其中某个符号 func 的最终位置，所以 assembler 先留下一个 relocation entry：R_X86_64_PC32 func-0x4 (下一条指令要减 4)，用的是 PC-relative addressing，即目标地址 = 下一条指令 + 偏移量。Linker 最后知道目标和下一条指令地址，计算出 offset 写进机器码，而不是把绝对地址硬编码进去。

  • callq/call 是 x86-64 的函数调用指令。会跳转到目标函数，并保存返回地址，类似于 jal 或 jalr；
  • callq 使用 PC-relative addressing。机器码里存的不是符号的绝对地址，而是 offset。offset = 目标函数地址 - 下一条指令地址；
  • Linker 在 relocation 阶段负责计算并填入这个 offset。

Load Exec. to Mem.

还记得虚拟内存吗？

可执行 ELF 文件会被 loader 加载到虚拟内存中 (从低地址到高地址)：0x400000 附近开始，代码段: .text, .rodata、数据段：.data, .bss、heap 向高位扩展：malloc 创建、mmap 区域：共享库、stack 向低位扩展：函数调用栈、kernel virtual memory (对用户不可见)。

程序运行前，操作系统会根据 ELF 的 program header table，把对应 segment 映射到虚拟内存中。


库

如何打包程序中常用的函数或者模块 (Math, I/O…)？

  • A. 全部放在一个 source file 中，时间和空间上都低效；
  • B. 每个函数放一个 file，效率不错，但程序员写依赖写到手抽。

静态库

C. 早期解决方案是静态库 (.a files)，本质是很多功能相近的 .o 文件打包成一个带有索引的 archive：

  • 打包：ar rs libme.a a.o b.o c.o ，ar 是 Archiver，功能很像 Linker ——都是把多个 .o 打包起来，都允许模块化修改，但输出格式不同。

  • 查看包内容：ar -t libme.a

  • 库一般命名为 libxxx.a，链接时写 gcc main.c -lxxx，比如用数学库 libm 就写 -lm。链接时 Linker 会拉 “符号表中出现的 ref. symbol 对应的 .o ” 进可执行文件，⚠️ 不一定会拉没出现的模块，这就是为什么静态库比 “一个巨大 object file” 更高效的原因。

    ⚠️ 终端输入是有序的，Linker 按命令行从左到右扫描，所以一句命令里永远是 .o 文件放前面，其依赖的库文件放后面。

有趣的是，你如果仔细想，就会发现上述 ABC 三个方案的关系很像 FAC、DMC 和 SAC 三种缓存，两者都有哈希平衡的影子。

libc.a (C 标准库) 占4.6 MB，含有 1496 个模块：I/O, memory allocation, signal handling, string handling, data and time……

libm.a (C 数学库) 占 2 MB，含有 444 个模块：floating point math (sin, cos, tan, log, exp, sqrt, …)

静态库的问题基本就是静态链接的问题——

  • 程序独立的把自己用到的库代码复制进可执行文件。如果 100 个程序都用 printf，那 100 个可执行文件里都有一份相同代码；那 100 个程序同时运行，那内存里就有 100 段相同代码，产生空间冗余。
  • 如果某个静态库里发现问题，所有静态链接过它的程序都需要重新链接，非常麻烦。

共享库 / 动态库

打包共享库：gcc -shared -o x.so y.c z.c -fpic。

现代系统大量使用 Shared Library (即上文提到的 .so / DDLs)，exec. 里不复制完整库代码， load-time / run-time 再把共享库加载进内存并完成链接。多个进程可以共享同一份库代码。

Load-time linking：程序刚被加载运行时，由 dynamic linker 完成链接。常见于 Linux，由 ld-linux.so (其 dynamic linker) 自动链接。libc.so 经常被加载时链接。

  • 链接 .so 和 .o 时，生成的 .exec 不是完全静态完成的，而是 partially linked exec.，⚠️ 其中仍保留部分 relocation 和 symbol table 信息。
  • 运行时，loader 通过 execve 加载程序，dynamic linker 加载选中的 .so 并完成剩余 relocation，然后程序开始执行。

Run-time linking：程序已经运行起来之后，再主动加载某个库。Linux 中，通过调用 dlopen() 接口。常用于插件系统、软件扩展、高性能服务器、运行时库替换。动态链接通常可以统一修改、加快编译、节约 RAM 空间。

  • dlopen：打开共享库，dlsym：查找函数地址、调用函数指针，dlclose：关闭共享库
  • 这种方式下，普通 linker 在编译主程序 (.o) 时甚至不知道依赖的 .so 的存在 (lazy binding)。库是在运行时通过字符串 "./libxxx.so" 加载的。

ELF 中需要有相关 section：

  • .interp 指定用哪个 dynamic linker，比如 ld-linux.so；ld 是 Linux 的标准 Linker

  • .dynamic 记录需要哪些动态库

  • 通过 readelf -d xxx 查看动态库，比如 (NEEDED) Shared library: [libm.so.6]

  • 通过 ldd xxx 查看动态库位置，比如 libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x… 十六位十六进制地址)

(".6" 是动态库名字中的 ABI 主版本号，用来保证运行时加载的库和程序编译时所依赖的二进制接口兼容，当然也可以是别的数字)

共享库的位置：PIC

如果多个进程共享同一份库代码，这份代码应该加载到哪里？

如果强行规定每个库固定地址，会很僵硬且容易冲突。更好的办法是让共享库代码可以加载到任意地址运行，称为 PIC：Position-Independent Code (位置无关代码)。

⚠️ 通过打包共享库时打开 flag “-fpic” 实现。

PIC 核心原理：无论被加载到内存的任意位置，对象文件的代码段和数据段之间的相对距离在运行时是固定常数。通过在 .data 段开头建立一个 GOT (Global Offset Table)，保存全局变量或外部符号的实际地址。运行时 dynamic linker 更新 GOT。

  • 用 PC-relative 方法找到 x 对应 GOT entry；从 GOT 里读出 x 的真实地址；再从真实地址读取 x 的值。

类似的，GOT 主要用于保存地址，PLT 主要用于函数调用的跳板。PLT 是内存中一段只读区域，包含一些小的跳板代码 (trampolines)，当程序调用外部函数，比如 printf。可能不是直接跳到 printf 的最终地址，而是先跳到 PLT stub (小跳板)；PLT stub 再通过 GOT 找到真正的函数地址。⚠️ PLT 存在于 read-only section (.text / .plt)。

  • GOT.plt 是 GOT 里面专门给 PLT 使用的一块区域，当然也在 .data 段。

  • GOT 和 PLT 共同支持了 dynamic linking、PIC、lazy binding


回顾

  • gcc -c main.c：不链接编译 (产生 .o)

  • gcc main.o x.o y.o -lm -o prog 链接静态库，产生 prog 可执行文件

  • objdump -rd main.o 或 objdump -d prog：查看反汇编 (-d) 和重定位 (-r)

  • objdump -t main.o 或 readelf -s main.o：查看符号表

  • ar rs libxxx.a x.o y.o：创建静态库

  • ar -t libxxx.a：查看静态库内容

  • gcc -shared -o libxxx.so x.c y.c -fpic：创建共享库

  • ldd prog 查看共享库依赖

  • Source to Executable 全流程图：

    main.c       sum.c
  ↓           ↓
main.o       sum.o
  ↓           ↓
symbol resolution
       ↓
   relocation
       ↓
 executable file
       ↓
loader loads into memory
       ↓
dynamic linker load .so
       ↓
 program runs
comments powered by Disqus