GuangchaoSun's Blog

第7章 链接

发表于  |    |   分类于   |  

学习目标

  • 编译的整个过程，各个部分的任务
  • 链接的概念
  • 链接的过程
  • 打包中常用的两种技术

编译

C语言代码最终成为机器可执行的程序，会像流水线上的产品一样接受各项处理：

  • 预处理阶段：预处理器cpp根据以字符#开头的命令，修改原始的 C 程序。预处理阶段根据已放置在文件中的预处理指令来修改源文件的内容。主要是以下几方面的处理：
    • 宏定义指令，如#define a b这种伪指令，预编译所要做的是将程序中的所有a用b替换，但作为字符串常量的a则不被替换。还有#undef，则取消对某个宏的定义，使以后该串的出现不会被替换。
    • 条件编译指令，如#ifdef，#idndef，#else，#elif，#endif等。这些伪指令的引入使得程序员可以通过定义不同的宏来决定编译程序对哪些代码进行处理。预编译程序将根据有关的文件，将那些不必要的代码过滤掉。
    • 头文件包含指令，如#include "filename"。该指令将头文件中的定义统统都加入到它所产生的输出文件中，以供编译程序对之进行处理。
    • 特殊符号，预编译程序可以识别一些特殊的符号。例如在源程序中出现的LINE标识将被解释为当前行号(十进制数)，FILE则被解释为当前被编译的C源程序的名称。预编译程序对于在源程序中出现的这些串将用合适的值进行替换。
  • 编译阶段：编译器ccl将文本文件hello.i翻译成文本文件hello.s，它包含一个汇编语言程序。编译程序所做的工作就是通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。
  • 汇编阶段：接下来，汇编器as将hello.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序(relocatable object program)的格式，并将结果保存在目标文件hello.o中。目标文件由段组成。通常一个目标文件中至少有两个段：
    • 代码段：该段中所包含的主要是程序的指令。该段一般是可读和可执行的，但一般不可写
    • 数据段：主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读，可写，可执行的
  • 链接阶段：对象程序hello.o以及所需的静态库经过链接器ld的处理最终成为可执行目标程序。
  • 加载阶段：加载器loader将可执行目标程序加载到内存并执行。

链接（linking）是将各种代码和数据部分收集起来并合并成一个单一文件的过程，这个文件可以被加载（或拷贝）到存储器执行。
下面来看一个实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void swap();
int buf[2] = {1,2};
int main(){
	swap();
	retunr 0;    
}
/*--------------------*/
extern int buf[];
int *bufp0 = &buf[0];
int *bufp1;
void swap(){
	int temp;
	bufp1 = &buf[1];
	temp = *bufp0;
	*bufp0 = *bufp1;
	*bufp1 = temp;
}

链接基本知识

为什么要使用链接器？

有如下两个原因：

  • 模块化角度考虑。我们可以把程序分散到不同的小的源代码中，而不是一个巨大的类中。这样带来的好处是可以复用常见的功能/库，比方说 Math library,standard C library.
  • 效率角度考虑。改动代码时只需要重新编译改动的文件，其他不受影响。而常用的函数和功能可以封装成库，提供给程序进行调用（节省空间）

静态链接

像unix ld这样的静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的可以加载和运行的可执行目标文件作为输出。
链接器的两个任务：

  • 符号解析(symbol resolution)。目标文件定义和引用符号。符号解析的目的是将每个符号引用刚好和一个符号定义联系起来
  • 重定位(relocation)。编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义和一个存储器位置联系起来，然后修改所有对这些符号的引用，使得它们指向这个存储器位置，从而重定位这些节。

目标文件的三种形式：

  • 可重定位目标文件Relocatable object file(.o file)
    • 包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
  • 可执行目标文件Executable object file(a.out file)
    • 包含二进制代码和数据，其形式可以被直接拷贝到存储器并执行。
  • 共享目标文件Shared object file(.so file)
    • 一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载到内存并链接。

可重定位目标文件

以上的三种对象文件有统一的格式，即（Executable and Linkable Format,ELF）。一个典型的ELF可重定位目标文件包含以下几个节：

  • ELF header
    • 包含 word size,byte ordering,file type(.o,exec,.so),machine type,etc
  • Segment header table
    • 包含 page size,virtual address memory segments(sections),segment sizes
  • .text
    • 已编译程序的机器代码
  • .rodata
    • 只读程序
  • .data
    • 已初始化的全局C变量
  • .bss
    • 未初始化的全局C变量
  • .symtab
    • 一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
  • .rel.text
    • 一个.text节中位置的列表，当链接器把这个目标文件和其他文件结合时，需要修改这些位置。
  • .rel.data
    • 被模块引用或定义的任何全局变量的重定位信息。
  • .debug
    • 一个符号调试表
  • .line
    • 原始C源程序的行号和.text节中机器指令之间的映射
  • .strtab
    • 一个字符串表

任何声明带有static属性的全局变量或者函数都是模块私有的

符号和符号表

每个可重定位目标模块m都有一个符号表，它包含m所定义和引用的符号的信息。

  • 全局符号 Global symbols
    • 由m定义并能被其他模块引用的全局符号
  • 外部符号 External symbols
    • 由其他模块定义并被m引用的全局符号
  • 本地符号 Local symbols
    • 只被模块m定义和引用的本地符号

符号表是由汇编器构造的，使用编译器输出到汇编语言.s文件中的符号。

1
2
3
4
5
6
7
8
9
10
11
typedef struct 
{
	int name;      /*String table offset*/
	int value;     /*Section offset,or VM address*/
	int size;      /*Object size in bytes*/
	char type:4,   /*Data, func, section, or src file name(4 bits)*/
		 binding:4;/*Local or global(4 bits)*/
	char reserved; /*Unused*/
	char section;  /*Scection header index, ABS, UNDEF*/
                   /*Or COMMON*/
} Elf_Symbol;

链接过程

链接器主要是将有关的目标文件彼此相连生成可加载、可执行的目标文件。链接器的核心工作就是符号表解析和重定位

第一步 符号解析 Symbol resolution

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 文件 main.c
int sum(int *a, int n);
int array[2] = {1, 2}; // 变量 array 在此定义
int main() // 定义了一个全局函数
{
    int val = sum(array, 2);
    // val 是局部变量，链接器并不知道
    // sum 函数是一个全局引用
    // array 变量是一个全局引用
    return val;
}
// -----------------------------------------
// 文件 sum.c
int sum(int *a, int n) // 定义了一个全局函数
{
    int i, s = 0;
    // i 和 s 是局部变量，链接器并不知道
    for (i = 0; i < n; i++)
        s += a[i];
    
    return s;
}

我们可以看到，链接器只知道非静态的全局变量，而对于局部变量一无所知。然后我们来看看局部非静态变量和局部静态变量的区别：

  • 局部非静态变量会保存在栈中
  • 局部静态变量会保存在.bss和.data中

如果两个文件中定义了同名的全局变量，编译器向汇编器输出的时候会有强弱之分：

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

链接器在处理强弱符号的时候遵守以下规则：

  1. 不允许出现多个强符号
  2. 如果有同名的强符号和弱符号，选择强符号，也就意味着弱符号是无效的
  3. 如果有多个弱符号，随便选择一个

如果可能，尽量避免使用全局变量
如果一定要用，注意下面几点：

  • 使用静态变量
  • 定义全局变量的时候初始化
  • 注意使用extern关键字

第二步 重定位 Relocation

一旦链接器完成了符号解析这一步，它就把代码中的每个符号引用和确定的一个符号定义（即它的一个输入目标模块中的一个符号表条目）联系起来。由下面两步组成：

  • 重定位和符号定义。链接器将所有相同类型的节合并为同一类型的新的聚合节。
  • 重定位节中的符号引用。链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的地址。

下面是重定位的过程，就是把不同重定位对象拼成可执行对象文件：

链接器的重定位算法的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
foreach section a{
	foreach reloaction entry r{
		refptr = s + r.offset;
		if(r.type == R_386_PC32){ /*Relocate a PC-relative reference*/
			refaddr = ADDR(s) + r.offset;
			*refptr = (unsigned)(ADDR(r.symbol) + *refptr - refaddr);
		}
		if(r.type == R_386_32){
			*refptr = (unsigned)(ADDR(r.symbol) + *refptr);
		}
	}
}

我们从汇编代码的角度来看看具体链接器是如何工作的：

1
2
3
4
5
6
7
int sum(int *a, int n);
int array[2] = {1, 2};c
int main()
{
    int val = sum(array, 2);
    return val;
}

通过objdump -r -d main.o反编译对应的可重定位对象文件，可以得到如下的汇编代码：

1
2
3
4
5
6
7
8
9
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               retq

这里我们可以看到，编译器用relocation entry 来标记不同的调用（对应代码后面四组数字都是零，就是留出位置让链接器在链接的时候填上对应的实际内存地址）
在完成链接之后我们得到prog这个程序，同样反编译objdump -dx prog可以看到：

1
2
3
4
5
6
7
8
9
10
11
12
00000000004004d0 <main>:
    4004d0: 48 83 ec 08      sub   $0x8, %rsp
    4004d4: be 02 00 00 00   mov   $0x2, %esi 
    4004d9: bf 18 10 60 00   mov   $0x0, %edi  # %edi = &array
    4004de: e8 05 00 00 00   callq 4004e8 <sum> # sum()
    4004e3: 48 83 c4 08      add   $0x8, %rsp
    4004e7: c3               retq 
00000000004004e8 <sum>:
    4004e8: b8 00 00 00 00   mov   $0x0, %eax
    ...
    ...
    400501: f3 c3            repz retq

对应地址已经填上去了，这里用的是相对位置，比如说0x4004de的05 00 00 00的意思实际上是说在下一句的基础上加上0x5，也就是0x4004e8，即sum函数的开始位置。
具体载入内存时：

需要注意左边的部分地址从上往下（上面的地址较小），右边则是从下往上（下面的地址较小）。

打包常用程序

静态库 Static Library

所有的编译系统都提供一种机制，将所有相关的目标模块打包称为一个单独的文件，称为静态库（static library），它可以用作链接器的输入。当构造器构造一个输出的可执行文件时，它只拷贝静态库里被应用程序引用的目标模块。相关的函数可以被编译为独立的目标模块，然后封装成一个单独的静态库文件。

Other:静态库是一个外部函数与变量的集合体。静态库的文件内容，通常包含一堆程序员自定的变量与函数，其内容不像动态链接那么复杂，在编译期间由编译器与链接器将它集成至应用程序内，并制成目标文件以及可以独立运作的可执行文件。这个可执行文件与编译可执行文件的程序，都是一种程序的静态创建(static build)
具体过程就是把不同文件的.o文件通过Archiver打包成一个.a文件。Archiver支持增量更新，如果有函数变动，只需重新编译改动的部分。

共享库 Shared Library

共享库是一个目标模块，在运行时，可以加载到任意的存储器地址，并和一个在存储器中的程序链接起来。这个过程称为动态链接（dynamic linking），是由一个叫做动态链接器（dynamic linker）的程序来执行的。
共享库在Unix系统中常用.so后缀来表示。
共享的两种方式：

  • 在文件系统中，只有一个.so文件，所以，所有引用该库的可执行目标文件共享这个.so文件中的代码和数据。
  • 在存储器中，一个共享库的.text节的副本可以被不同的正在运行的进程共享。

Linux允许应用程序在运行时加载和链接共享库

# include <dlfcn.h>
void *dlopen(const char *filename, int flag)
//返回：若成功则为指向句柄的指针，若出错则为NULL

案例学习 Library Interpositioning

Tutorial: Function Interposition in Linux

小结

链接可以在编译时由静态编译器来完成，也可以在加载和运行时由动态链接器来完成。

参考资料