Csapp：7.链接

链接是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可以被加载到内存并执行。

链接可以执行于编译时、加载时、运行时。

链接使得分离编译成为可能。可以将巨大的源文件分解为更小的模块，可以独立地修改和编译这些模块。当我们改变其中的一个模块时，只需简单地将其重新编译并链接，无需重新编译其他文件。

理解链接器的作用：

帮助构造大型程序
避免一些危险的编程错误。例如错误地定义多个全局变量的程序将通过链接器，不产生任何警告。
理解语言的作用域规则。如：全局和局部变量的区别；static属性的变量和函数的意义。
帮助理解其他重要的系统概念。链接器产生的可执行目标文件在重要的系统功能中扮演着关键角色。
帮助我们利用共享库。

编译器驱动程序

编译器驱动程序代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。例如我们经常使用的gcc驱动程序。

main.c$\rightarrow$main.i$\rightarrow$main.s$\rightarrow$main.o$\rightarrow$prog

源程序$\rightarrow$中间文件$\rightarrow$汇编语言文件$\rightarrow$可重定位目标文件$\rightarrow$可执行目标文件

依次使用了：预处理器、编译器、汇编器、链接器

shell执行可执行文件时调用操作系统中的加载器函数，将prog中的代码和数据复制到内存中，然后将控制转移到这个程序的开头。

linux> ./prog

静态链接

可重定位目标文件由不同的代码和数据节组成，每一节都是一个连续的字节序列。

静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。

为了构造可执行文件，链接器必须完成连个任务：

符号解析：目标文件定义和引用符号，每个符号对应一个函数、一个全局变量或一个静态变量。将每个符号引用正好和一个符号定义关联起来。（每个符号对应于一个函数、一个全局变量或一个静态变量）
重定位。编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使它们指向这个内存位置。

目标文件

共有三种：

可重定位目标文件：二进制代码和数据，可在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
可执行目标文件：二进制代码和数据，其形式可以直接被复制到内存中并执行。
共享目标文件：特殊类型的可重定位目标文件，可以在加载或运行时被动态地加载进内存并链接。

目标文件是按照特定目标文件格式来组织的，各个系统的目标文件格式都不相同。

可重定位目标文件

一个典型的ELF可重定位目标文件：

首先是16B的ELF头，描述了生成该文件的系统的字的大小和字节顺序。

然后是节：一个典型的ELF可重定位目标文件包含以下几个节：

.text：已编译程序的机器代码
.rodata：只读数据
.data：已初始化的全局和静态C变量
.bss：未初始化的全局和静态C变量，以及所有被初始化为0的全局或静态变量
.symtab：一个符号表，存放在程序中定义和引用的函数和全局变量的信息
.rel.text
.rel.data
.debug：调试符号表，以-g选项调用编译器驱动程序时才会得到这张表。
.line：原始C程序的行号和.text节中的机器指令之间的映射，以-g选项调用编译器驱动程序时才会得到这张表。
.strtab：一个字符串表，其中内容包括.symtab和.debug节中的符号表，以及节头部中的节名称。

符号和符号表

每个可重定位目标模块都有一个符号表.symtab，它包含m定义和引用的符号的信息。在链接器的上下文，有三种不同符号：

由模块m定义并能被其他模块引用的全局符号：对应非静态的C函数和全局变量。
由其他模块定义并被m引用的全局符号，称为外部符号：对应其他模块中定义的非静态的C函数和全局变量
只被模块m定义和引用的局部符号：对应于带static属性的C函数和全局变量。

本地非静态程序变量的符号在运行时在栈中被管理，不在符号表.symtab中。

C中源文件扮演模块的角色，static属性就像C++使用的public和private一样。

尽可能用static属性来保护变量和函数。

符号表由汇编器构造，使用编译器输出到汇编语言.s文件中的符号。.symtab节中包含ELF符号表。以下为符号表中每个符号条目的格式：

typedef struct {
	int name;
	char type:4,
		 binding:4;
	char reserved;
	short section;
	long value;
	long size;
} Elf64_Symbol;

name是字符串表中的字节偏移，指向符号的以null结尾的字符串名字。value是符号的地址。对于可重定位目标文件来说，value是距定义目标的节的起始位置的偏移。对于可执行目标文件来说，该值是一个绝对运行时的地址。size是目标的大小。type通常代表数据或函数。符号表还可以包含各个节的条目。binding字段表示符号是本地还是全局。

每个符号都被分配到目标文件的某个节，由section字段表示，该字段也是一个到节头部表的索引。

以下是hello_world.c文件的符号表：

#include <stdio.h>
int main() {
   printf("Hello, World!");
   return 0;
}

Symbol table '.symtab' contains 70 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000318     0 SECTION LOCAL  DEFAULT    1 
     2: 0000000000000338     0 SECTION LOCAL  DEFAULT    2 
     3: 0000000000000358     0 SECTION LOCAL  DEFAULT    3 
     4: 000000000000037c     0 SECTION LOCAL  DEFAULT    4 
     5: 00000000000003a0     0 SECTION LOCAL  DEFAULT    5 
     6: 00000000000003c8     0 SECTION LOCAL  DEFAULT    6 
     7: 0000000000000470     0 SECTION LOCAL  DEFAULT    7 
     8: 00000000000004f4     0 SECTION LOCAL  DEFAULT    8 
     9: 0000000000000508     0 SECTION LOCAL  DEFAULT    9 
    10: 0000000000000528     0 SECTION LOCAL  DEFAULT   10 
    11: 00000000000005e8     0 SECTION LOCAL  DEFAULT   11 
    12: 0000000000001000     0 SECTION LOCAL  DEFAULT   12 
    13: 0000000000001020     0 SECTION LOCAL  DEFAULT   13 
    14: 0000000000001040     0 SECTION LOCAL  DEFAULT   14 
    15: 0000000000001050     0 SECTION LOCAL  DEFAULT   15 
    16: 0000000000001060     0 SECTION LOCAL  DEFAULT   16 
    17: 00000000000011e8     0 SECTION LOCAL  DEFAULT   17 
    18: 0000000000002000     0 SECTION LOCAL  DEFAULT   18 
    19: 0000000000002014     0 SECTION LOCAL  DEFAULT   19 
    20: 0000000000002058     0 SECTION LOCAL  DEFAULT   20 
    21: 0000000000003db8     0 SECTION LOCAL  DEFAULT   21 
    22: 0000000000003dc0     0 SECTION LOCAL  DEFAULT   22 
    23: 0000000000003dc8     0 SECTION LOCAL  DEFAULT   23 
    24: 0000000000003fb8     0 SECTION LOCAL  DEFAULT   24 
    25: 0000000000004000     0 SECTION LOCAL  DEFAULT   25 
    26: 0000000000004010     0 SECTION LOCAL  DEFAULT   26 
    27: 0000000000000000     0 SECTION LOCAL  DEFAULT   27 
    28: 0000000000000000     0 SECTION LOCAL  DEFAULT   28 
    29: 0000000000000000     0 SECTION LOCAL  DEFAULT   29 
    30: 0000000000000000     0 SECTION LOCAL  DEFAULT   30 
    31: 0000000000000000     0 SECTION LOCAL  DEFAULT   31 
    32: 0000000000000000     0 SECTION LOCAL  DEFAULT   32 
    33: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS crtstuff.c
    34: 0000000000001090     0 FUNC    LOCAL  DEFAULT   16 deregister_tm_clones
    35: 00000000000010c0     0 FUNC    LOCAL  DEFAULT   16 register_tm_clones
    36: 0000000000001100     0 FUNC    LOCAL  DEFAULT   16 __do_global_dtors_aux
    37: 0000000000004010     1 OBJECT  LOCAL  DEFAULT   26 completed.8061
    38: 0000000000003dc0     0 OBJECT  LOCAL  DEFAULT   22 __do_global_dtors_aux_fin
    39: 0000000000001140     0 FUNC    LOCAL  DEFAULT   16 frame_dummy
    40: 0000000000003db8     0 OBJECT  LOCAL  DEFAULT   21 __frame_dummy_init_array_
    41: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS hello_world.c
    42: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS crtstuff.c
    43: 000000000000215c     0 OBJECT  LOCAL  DEFAULT   20 __FRAME_END__
    44: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS 
    45: 0000000000003dc0     0 NOTYPE  LOCAL  DEFAULT   21 __init_array_end
    46: 0000000000003dc8     0 OBJECT  LOCAL  DEFAULT   23 _DYNAMIC
    47: 0000000000003db8     0 NOTYPE  LOCAL  DEFAULT   21 __init_array_start
    48: 0000000000002014     0 NOTYPE  LOCAL  DEFAULT   19 __GNU_EH_FRAME_HDR
    49: 0000000000003fb8     0 OBJECT  LOCAL  DEFAULT   24 _GLOBAL_OFFSET_TABLE_
    50: 0000000000001000     0 FUNC    LOCAL  DEFAULT   12 _init
    51: 00000000000011e0     5 FUNC    GLOBAL DEFAULT   16 __libc_csu_fini
    52: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
    53: 0000000000004000     0 NOTYPE  WEAK   DEFAULT   25 data_start
    54: 0000000000004010     0 NOTYPE  GLOBAL DEFAULT   25 _edata
    55: 00000000000011e8     0 FUNC    GLOBAL HIDDEN    17 _fini
    56: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@@GLIBC_2.2.5
    57: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_
    58: 0000000000004000     0 NOTYPE  GLOBAL DEFAULT   25 __data_start
    59: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
    60: 0000000000004008     0 OBJECT  GLOBAL HIDDEN    25 __dso_handle
    61: 0000000000002000     4 OBJECT  GLOBAL DEFAULT   18 _IO_stdin_used
    62: 0000000000001170   101 FUNC    GLOBAL DEFAULT   16 __libc_csu_init
    63: 0000000000004018     0 NOTYPE  GLOBAL DEFAULT   26 _end
    64: 0000000000001060    47 FUNC    GLOBAL DEFAULT   16 _start
    65: 0000000000004010     0 NOTYPE  GLOBAL DEFAULT   26 __bss_start
    66: 0000000000001149    32 FUNC    GLOBAL DEFAULT   16 main
    67: 0000000000004010     0 OBJECT  GLOBAL HIDDEN    25 __TMC_END__
    68: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable
    69: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@@GLIBC_2.2

符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。

对于引用和定义在相同模块中的局部符号（即对应static变量）的引用，符号解析非常简洁明了。编译器只允许每个局部符号有一个定义。

对于全局符号的引用较为复杂，当编译器遇到一个不是在当前模块中定义的符号时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表，交给链接器处理。如果链接器在其他任何模块中都找不到这个被引用的符号，就输出一条错误信息并终止。

编译器通过重整的编码方式来区分重载的函数

链接器解析多重定义的全局符号

编译器向汇编器输出每个全局符号，或是强或是弱的，而汇编器把这些信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

Linux使用以下规则处理多重定义的符号名：

不允许由多个同名强符号
如果一个强符号和多个弱符号同名，选择强符号
如果有多个弱符号同名，从这些弱符号中任意选一个

与静态库链接

所有编译器都有一种机制，将所有相关的目标模块打包成一个单独的文件，称为静态库，它可以用作链接器的输入。链接器构造一个输出的可执行文件时，只复制静态库里被应用程序引用的目标模块。

Linux中，静态库以一种称为存档的特殊文件格式存放在磁盘中，存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小，存档文件名由后缀.a标识。

链接器如何使用静态库来解析引用

链接器从左到右按照在命令行上出现的顺序来扫描可重定位目标文件和存档文件。（编译器驱动程序自动将.c文件翻译为.o文件。在扫描中，链接器维护一个可重定位目标文件的集合E，一个未解析的符号集合U，以及一个在前面输入文件中已定义的符号集合D。初始时，E、U、D均为空。

对于命令行上的每个输入文件f，链接器会判断f是一个目标文件还是一个存档文件。如果是目标文件则将其添加到E中，修改U和D来反映f中的符号引用和定义
如果f是存档文件，链接器就尝试匹配U中未解析的符号和由存档文件成员定义的符号。如果某个存档文件成员m定义了一个符号来解析U中的一个引用，那么就把m加到E中，并修改U和D来反映m中的符号定义和引用。对存档文件依次重复这个过程直到U和D不发生变化。
如果链接器完成对命令行输入文件的扫描后，U是非空的，则链接器输出错误并终止。否则，合并然后重定位E中的文件，构建可执行文件。

重定位

链接器完成符号解析这一步后，就把代码中的每个符号引用和一个符号定义关联起来了，此时链接器就知道它的输入目标模块中的代码和数据节的确切大小。然后就可以开始重定位步骤了，该步骤将合并输入模块，并为每个符号分配运行时地址。共分为两步：

重定位节和符号定义：链接器将所有相同类型的节合并为同一类型的聚合节。例如，来自所有输入模块的.data节被全部合并为一个节，这个节成为输出的可执行目标文件的.data节。然后，链接器将运行时内存地址赋给新的聚合节，付给输入模块定义的每个节、每个符号。这一步完成后，程序中的每条指令和全局变量都有唯一的运行时内存地址了。
重定位节中的符号引用：链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。执行这一步，链接器依赖于可重定位目标模块中称为重定位条目的数据结构。

重定位条目

汇编器生成一个目标模块是，它并不知道数据和代码最终将放在内存中的什么位置，也不知道这个模块引用的任何外部定义的函数或全局变量的位置。所以无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码的重定位条目放在.rel.text中，已初始化的数据的重定位条目放在.rel.data中。

ELF定义了32种不同的重定位类型，我们只关心之中两种最基本的：

R_X86_64_PC32：重定位一个使用32位PC相对地址的引用。PC相对地址就是据程序计数器当前运行时值的偏移量。当CPU执行一条使用PC相对寻址的指令时，它就将在指令中编码的32位值加上PC的当前运行时值，得到有效地址。
R_X86_64_32：重定位一个使用32位绝对地址的引用。

重定位符号引用

重定位PC相对引用

重定位PC绝对引用

可执行目标文件

转化后的二进制的可执行目标文件包含加载程序到内存并运行它所需的所有信息。

ELF可执行目标文件结构

可执行目标文件格式类似于可重定位目标文件，ELF头描述文件的总体格式，还包括程序的入口点，即程序要运行时执行的第一条指令的地址。.init节定义了一个小函数_init，程序初始化代码会调用它。

以下为hello_world可执行文件的ELF头描述文件：

ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1060
  Start of program headers:          64 (bytes into file)
  Start of section headers:          16984 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         36
  Section header string table index: 35

可执行文件是完全链接的（已经被重定位），所以它不需要rel节。

ELF可执行文件被设计得很容易加载到内存，可执行文件的连续的片被映射到连续的内存段，程序段头部表描述了这种映射关系：

加载可执行目标文件

linux> ./prog

shell认为prog是一个可执行目标文件，通过调用驻留在存储器中的加载器的系统代码来运行它。加载器将可执行目标文件中的代码和数据从磁盘复制到内存，然后通过跳转到程序的入口点运行该程序。这整个过程叫做加载。

每个Linux程序都有一个运行时内存映像。在Linux x86-64中，代码段总是从地址0x400000开始，后面是数据段。运行时堆在数据段之后，通过调用malloc库向上增长。堆后面的区域是为共享模块保留的。用户栈总是从最大合法地址($2^{48}-1$)开始，向较小内存地址增长。栈上的区域，从地址$2^{48}$开始，是为内核中的代码和数据保留的。

加载与之后章节的进程、虚拟内存和内存映射有关。之后章节还会介绍。

动态链接共享库

静态库有一个缺点，需要定期维护和更新，如果应用程序需要一个新版本，必须以某种方式了解到该库的变化情况，然后显式地将其程序与更新了的库重新链接。

另一个问题是几乎每个C程序都使用标准I/O函数。运行时这些代码会被复制到每个运行进程的文本中，在一个上百个进程的系统上，这是对内存资源的极大浪费。

共享库用来解决静态库的缺陷，共享库是一个目标模块，在运行或加载时，可以加载到任意内存地址，并与一个在内存中的程序链接起来。这个过程称为动态链接，由叫做动态链接器的程序执行。Linux中用.so后缀的文件来表示共享库，Windows中使用.dll表示。

下图为动态链接共享库的过程：

动态链接共享库

任何给定文件系统中，对于一个库文件只有一个.so文件。所有引用该库的可执行目标文件共享这个.so文件中的数据和代码，不需要都复制和嵌入到引用它们的可执行文件中。

在内存中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享。第9章虚拟内存的内容中将更加详细地描述。

从应用程序中加载和链接共享库

应用程序除了在被加载后执行前加载和链接某个共享库，还可能在运行时要求动态链接器加载和链接某个共享库，无需在编译时将那些库链接到应用中。

现实中动态链接的例子：

分发软件：Windows应用开发者常使用动态库来分发软件更新，用户只要下载共享库的新版本然后替换当前版本即可。
构建高性能Web服务器：将每个生成动态内容的函数打包在共享库中。当一个来自Web浏览器的请求到达时，服务器动态地加载和链接适当的函数，然后直接调用它，而不是使用fork和execve在子进程的上下文中运行函数。函数会一直缓存在服务器的地址空间中，所以只要一个简单的函数调用的开销就可以处理随后的请求了。

位置无关代码

可以加载而无需重定位的代码称为位置无关代码（Position Independent Code, PIC）。使用这种方法，无限多个进程可以共享一个共享模块的代码段的单一副本。用户对GCC使用-fpic选项指示GNU编译系统生成PIC代码。共享库的编译必须总是使用该选项。

PIC数据引用

PIC函数调用

库打桩机制

库打桩允许我们截获对共享库函数的调用，取而代之执行自己的代码。使用该机制可以追踪对某个特殊库函数的调用次数，验证和追踪其输入输出值，或将其替换为一个完全不同的实现。

给定一个需要打桩的目标函数，创建一个包装函数，其原型与目标函数完全相同，使用某种特殊打桩机制，就可以欺骗系统调用包装函数而不是目标函数。

打桩可以发生在编译时、链接时或当程序被加载和执行的运行时。

编译时打桩

//int.c
#include <stdio.h>
#include <malloc.h>

int main() {
    int *p = malloc(32);
    free(p);

    return 0;
}

//malloc.h
#include <stdio.h>

#define malloc(size) mymalloc(size)
#define free(ptr) myfree(ptr)

void *mymalloc(size_t size);
void myfree(void *ptr);

//mymalloc.c
//#define COMPILETIME
#ifdef COMPILETIME
#include <stdio.h>
#include <malloc.h>

void *mymalloc(size_t size) {
    void *ptr = malloc(size);
    printf("malloc(%d)=%p\n", (int)size, ptr);

    return ptr;
}

void myfree(void *ptr) {
    free(ptr);
    printf("free(%p)\n", ptr);
}
#endif

运行以下命令：

$ gcc -DCOMPILETIME -c mymalloc.c
$ gcc -I. -o intc int.c mymalloc.o

运行程序intc得到结果：

$ ./intc
malloc(32)=0x561e0ca432a0
free(0x561e0ca432a0)

链接时打桩

Linux静态链接器支持用--wrap f标志进行链接时打桩。

运行时打桩

编译时打桩需要访问源程序，链接时打桩需要访问程序的可重定位目标文件。有一种机制能够在运行时打桩，它只需要能够访问可执行目标文件。这个机制基于动态链接器的LD_PRELOAD环境变量。

最后修改于 2022-01-26