聊一聊Linkers和Loaders


今天开始我们来讨论下C/C++程序的链接,加载和执行,我们将把重点放在目标文件的链接和加载上。

一般来说,源文件编译完成后会生成.o文件,多个.o文件和一些lib,一起link得到可执行文件,下面是GCC的一些常用编译选项,我们稍后会用到:

  • -c: 用来生成.o文件
  • -o : 用来创建目标文件
  • -g: 编译器在输出文件中包含debug信息,产生dSYM符号表
  • -Wall:编译器编译时打出warning信息,强烈推荐使用这个选项。
  • -I+dir: 除了在main.c当前目录和系统默认目录中寻找.h外,还在dir目录寻找,注意,dir是一个绝对路径。
  • -01,-02,-03: 编译器优化程度

如果使用macOS,gcc实际上是Clang的alias,binary的结构为MachO,而不是UNIX的ELF格式,不过这并不影响理解本文的内容

Object Files

我们先从最基本的目标文件开始分析,现在假设我们有三个文件:function.h,function.mmain.c,代码如下

//function.h
#define FIRST_OPTION
#ifdef FIRST_OPTION
#define MULTIPLIER (3.0)
#else
#define MULTIPLIER (2.0)
#endif

float add_and_multiply(float x, float y);

//function.c
#include "function.h"

int nCompletionStatus = 0;
float add(float x, float y) {
    float z = x+y;
    return z;
}
float add_and_multiply(float x, float y){
    float z = add(x,y);
    z *= MULTIPLIER;
    return z;
}

//main.c
#include "function.h"

extern int nCompletionStatus;
int main() {
    float x = 1.0;
    float y = 1.5;
    float z;

    z = add_and_multiply(x,y);
    nCompletionStatus = 1;
    return 0;
}

为了生成目标文件.o,我们可以使用gcc对上述源码进行编译

gcc -c function.c
gcc -c main.c

执行上面两行命令后,我们可以得到funtion.omain.o。接下来我们来简单的分析一下目标文件的格式以及里面所包含的内容,在UNIX环境中,我们可以使用下面的工具帮助我们分析

  • nm: 显示目标文件中的symbol列表
  • objdump: 提供了一系列选项可以最目标文件做比较详细的分析,比如-S选项可以dump出汇编代码
  • readelf: 读取并显示ELF格式文件的信息

function.o为例,使用readelf -a function.o

readelf -a function.o
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:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          808 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         12
  Section header string table index: 9

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000006a  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  00000280
       0000000000000018  0000000000000018   I      10     1     8
  [ 3] .data             PROGBITS         0000000000000000  000000aa
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  000000ac
       0000000000000004  0000000000000000  WA       0     0     4
  [ 5] .comment          PROGBITS         0000000000000000  000000ac
       0000000000000036  0000000000000001  MS       0     0     1
  [ 6] .note.GNU-stack   PROGBITS         0000000000000000  000000e2
       0000000000000000  0000000000000000           0     0     1
  [ 7] .eh_frame         PROGBITS         0000000000000000  000000e8
       0000000000000058  0000000000000000   A       0     0     8
  [ 8] .rela.eh_frame    RELA             0000000000000000  00000298
       0000000000000030  0000000000000018   I      10     7     8
  [ 9] .shstrtab         STRTAB           0000000000000000  000002c8
       0000000000000059  0000000000000000           0     0     1
  [10] .symtab           SYMTAB           0000000000000000  00000140
       0000000000000108  0000000000000018          11     8     8
  [11] .strtab           STRTAB           0000000000000000  00000248
       0000000000000033  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

Relocation section '.rela.text' at offset 0x280 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000000004a  000900000002 R_X86_64_PC32     0000000000000000 add - 4

Relocation section '.rela.eh_frame' at offset 0x298 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0
000000000040  000200000002 R_X86_64_PC32     0000000000000000 .text + 24

The decoding of unwind sections for machine type Advanced Micro Devices X86-64 is not currently supported.

Symbol table '.symtab' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS function.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    6
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
     8: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    4 nCompletionStatus
     9: 0000000000000000    36 FUNC    GLOBAL DEFAULT    1 add
    10: 0000000000000024    70 FUNC    GLOBAL DEFAULT    1 add_and_multiply

上述命令给出了function.o中一些比较关键的信息,比如第一段的文件描述,第二段的section header信息,以及后面的重定位表和符号表等等。如果我们只要分析linker和loader,那么我们暂时不需要理解全部的内容,但是需要特别关注一些重要的section。实际上对于每个section,它们都是一个有起始实地址和固定长度构成的一段连续空间。其中,有四个section需要特别关注

  1. .text段,也叫代码段,用来存放汇编指令
  2. .data段,也叫数据段,用来保存程序里设置好的初始化数据信息
  3. .rela.text段,叫做重定位表(Relocation Table)。在表里,保存了所有未知跳转的指令
  4. .symtab段,也叫做符号表,用来存放当前文件里定义的函数和对应的地址

Linkers

在有了编译生成的.o文件后,Linker要做的事情就是将这些文件link在一起,具体来说过程如下,linker会扫描所有的目标文件,将所有符号表中的信息收集起来,构成一个全局的符号表,然后再根据重定位表,把所有不确定的跳转指令根据符号表里地址,进行一次修正。最后,把所有的目标文件的section分别进行合并,形成最终的可执行代码。对于前面的例子,我们有两个目标文件,linker的过程如下图所示

如果将上述步骤分解开来,则linker的执行步骤可大致分为两部分:符号解析(Symbol Resolution)和地址绑定(Relocation)

符号解析(Symbol Resolution)

我们可以使用前面提到的nm命令来快速看一下function.omain.o中都有哪些symbol

#function.o
0000000000000000    T add
0000000000000024    T add_and_multiply
0000000000000000    B nCompletionStatus

#main.o
                    U add_and_multiply
0000000000000000    T main
                    U nCompletionStatus

通过观察上面的符号表,可以发现

  1. 每个符号都有自己的类型。比如在main.o中,由于add_and_multiply是定义在另一个目标文件中,因此对于main.o来说,编译器并不知道这个符号在哪里,因此用U表示。nCompletionStatus同理。而对于function.o来说,这两个函数就定义在自身的目标文件中,编译器是知道它们的位置的,因此用TB表示。更多关于符号的含义可参考文末的附录。

  2. 每个符号都有自己的地址。它们的地址都是相对的都是相对于该目标文件的偏移,并不是虚拟内存中的地址。我们可以通过观察汇编代码来进一步验证,使用 objdump -d function.o得到function.o的汇编代码如下

Disassembly of section .text:

0000000000000000 <add>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	f3 0f 11 45 ec       	movss  %xmm0,-0x14(%rbp)
   9:	f3 0f 11 4d e8       	movss  %xmm1,-0x18(%rbp)
   e:	f3 0f 10 45 ec       	movss  -0x14(%rbp),%xmm0
  13:	f3 0f 58 45 e8       	addss  -0x18(%rbp),%xmm0
  18:	f3 0f 11 45 fc       	movss  %xmm0,-0x4(%rbp)
  1d:	f3 0f 10 45 fc       	movss  -0x4(%rbp),%xmm0
  22:	5d                   	pop    %rbp
  23:	c3                   	retq

0000000000000024 <add_and_multiply>:
  24:	55                   	push   %rbp
  25:	48 89 e5             	mov    %rsp,%rbp
  28:	48 83 ec 20          	sub    $0x20,%rsp
  2c:	f3 0f 11 45 ec       	movss  %xmm0,-0x14(%rbp)
  31:	f3 0f 11 4d e8       	movss  %xmm1,-0x18(%rbp)
  36:	f3 0f 10 45 e8       	movss  -0x18(%rbp),%xmm0
  3b:	8b 45 ec             	mov    -0x14(%rbp),%eax
  3e:	0f 28 c8             	movaps %xmm0,%xmm1
  41:	89 45 e4             	mov    %eax,-0x1c(%rbp)
  44:	f3 0f 10 45 e4       	movss  -0x1c(%rbp),%xmm0
  49:	e8 00 00 00 00       	callq  4e <add_and_multiply+0x2a>
  4e:	66 0f 7e c0          	movd   %xmm0,%eax
  52:	89 45 fc             	mov    %eax,-0x4(%rbp)
  55:	f3 0f 10 45 fc       	movss  -0x4(%rbp),%xmm0
  5a:	f3 0f 58 c0          	addss  %xmm0,%xmm0
  5e:	f3 0f 11 45 fc       	movss  %xmm0,-0x4(%rbp)
  63:	f3 0f 10 45 fc       	movss  -0x4(%rbp),%xmm0
  68:	c9                   	leaveq
  69:	c3                   	retq

因此可以猜想,linker接下来要做的事情就是将所有Undefined符号进行地址绑定(动态库中的符号暂不考虑)以及算出每个符号在虚拟内存中的真实地址

Relocation

Section的Relocation很简单,就是将所有目标文件的各个段按照某种规则进行合并,比如上面图中的,text段合并,符号表合并等等。在合并的过程中,需要计算每个段在实际虚拟内存中的地址,比如前面提到的main.o中的main符号的地址为0x0000000000000000function.oadd地址也为0x0000000000000000。显然,在实际的内存中,不管是add还是main的地址是不可能为0x0000000000000000的。这时候就需要Relocation发挥作用,将所有section的地址重新分配到合理的位置。但需要注意的是,在分配的过程中要保证每个Section的连续性不被破坏,因此linker是需要知道每个section的大小和范围。

下面我们来通过观察汇编代码来具体看一下是上述过程,我们还是使用objdump命令来反汇编目标文件

objdump -d -S main.o

main.o:     file format elf64-x86-64
Disassembly of section .text:
0000000000000000 main:
0:	55                   	push   rbp
1:	48 89 e5             	mov    rbp,rsp
4:	48 83 ec 20          	sub    rsp,0x20
8:	f3 0f 10 05 00 00 00 	movss  xmm0,DWORD PTR [rip+0x0]        # 10 <main+0x10>
f:	00
10:	f3 0f 11 45 f4       	movss  DWORD PTR [rbp-0xc],xmm0
15:	f3 0f 10 05 00 00 00 	movss  xmm0,DWORD PTR [rip+0x0]        # 1d <main+0x1d>
1c:	00
1d:	f3 0f 11 45 f8       	movss  DWORD PTR [rbp-0x8],xmm0
22:	f3 0f 10 45 f8       	movss  xmm0,DWORD PTR [rbp-0x8]
27:	8b 45 f4             	mov    eax,DWORD PTR [rbp-0xc]
2a:	0f 28 c8             	movaps xmm1,xmm0
2d:	89 45 ec             	mov    DWORD PTR [rbp-0x14],eax
30:	f3 0f 10 45 ec       	movss  xmm0,DWORD PTR [rbp-0x14]
35:	e8 00 00 00 00       	call   3a <main+0x3a>
3a:	66 0f 7e c0          	movd   eax,xmm0
3e:	89 45 fc             	mov    DWORD PTR [rbp-0x4],eax
41:	c7 05 00 00 00 00 01 	mov    DWORD PTR [rip+0x0],0x1        # 4b <main+0x4b>
48:	00 00 00
4b:	b8 00 00 00 00       	mov    eax,0x0
50:	c9                   	leave
51:	c3                   	ret

上述是main函数的汇编指令,我们发现在第#35行,有一个call的指令,参考main函数的源码可知,这个指令是用来调用add_and_multiply函数的,但是由于这个.o_add_and_multiply符号未知,call变成调用自己,显然是不正确的。因此,我们可以猜想在最终的binary中,这行指令应该会发生变化,linker会对符号进行解析和地址绑定。

$gcc function.c mian.c -o demoApp
$objdump -D demoApp

0000000000400540 main:
  400540:	55                   	push   rbp
  400541:	48 89 e5             	mov    rbp,rsp
  400544:	48 83 ec 20          	sub    rsp,0x20
  400548:	f3 0f 10 05 d4 00 00 	movss  xmm0,DWORD PTR [rip+0xd4]        # 400624 <_IO_stdin_used+0x4>
  40054f:	00
  400550:	f3 0f 11 45 f4       	movss  DWORD PTR [rbp-0xc],xmm0
  400555:	f3 0f 10 05 cb 00 00 	movss  xmm0,DWORD PTR [rip+0xcb]        # 400628 <_IO_stdin_used+0x8>
  40055c:	00
  40055d:	f3 0f 11 45 f8       	movss  DWORD PTR [rbp-0x8],xmm0
  400562:	f3 0f 10 45 f8       	movss  xmm0,DWORD PTR [rbp-0x8]
  400567:	8b 45 f4             	mov    eax,DWORD PTR [rbp-0xc]
  40056a:	0f 28 c8             	movaps xmm1,xmm0
  40056d:	89 45 ec             	mov    DWORD PTR [rbp-0x14],eax
  400570:	f3 0f 10 45 ec       	movss  xmm0,DWORD PTR [rbp-0x14]
  400575:	e8 80 ff ff ff       	call   4004fa add_and_multiply
  40057a:	66 0f 7e c0          	movd   eax,xmm0
  40057e:	89 45 fc             	mov    DWORD PTR [rbp-0x4],eax
  400581:	c7 05 a9 0a 20 00 01 	mov    DWORD PTR [rip+0x200aa9],0x1        # 601034 <nCompletionStatus>
  400588:	00 00 00
  40058b:	b8 00 00 00 00       	mov    eax,0x0
  400590:	c9                   	leave
  400591:	c3                   	ret
  400592:	66 2e 0f 1f 84 00 00 	nop    WORD PTR cs:[rax+rax*1+0x0]
  400599:	00 00 00
  40059c:	0f 1f 40 00          	nop    DWORD PTR [rax+0x0]

对比两段汇编代码,不难发现,前者的BaseAddress是0000000000000000,每条汇编指令前面的数字是该指令的offset。而后者的BaseAddreess变成了0000000000400540,说明Linker对每个目标文件的汇编指令做了地址修正,另外,call指令后的符号变成了我们期望的函数符号add_and_multiply,地址为4004fa。说明Linker完成的符号和地址的绑定。

00000000004004fa <add_and_multiply>:
4004fa:	55                   	push   rbp
4004fb:	48 89 e5             	mov    rbp,rsp
...
40051a:	f3 0f 10 45 e4       	movss  xmm0,DWORD PTR [rbp-0x1c]
40051f:	e8 b2 ff ff ff       	call   4004d6 <add>
400524:	66 0f 7e c0          	movd   eax,xmm0
...
40053e:	c9                   	leave
40053f:	c3                   	ret

另一关于Code Modification比较好的例子是Linkers and loaders这本书中的例子,假设某个目标文件在编译完后有下面x86的一段汇编代码

A1 34 12 00 00 mov a, %eax
A3 00 00 00 00 mov %eax, b

这两行代码的意思是将a中的值通过寄存器赋值给b。其中每行指令由一个opcode + 4字节的地址组成,由于a位于该目标文件内,地址为0x1234,由于x86使用的是right-to-left order,因此a的地址表示为34 12 00 00b是一个import进来的变量,在编译时,编译器并不知道b在哪里,因此地址为00 00 00 00

当link完成后,假设a所在的text段的偏移量为0x1000,因此a的地址变成了0x11234b所在的地址为0x9A12,则上述两条指令会被linker改写为

A1 34 12 10 00 mov a, %eax
A3 12 9A 00 00 mov %eax, b

当Relocation完成后,每个section和symbol的虚拟内存地址也就确定了,至此linker的任务也就完成了。

Loaders

现在我们已经有了一个link好的binary文件了,当我们执行它的时候,Loader会将binary中的section按照一定规则加载到内存中。实际上Loader的工作就这么简单,但是所谓的“一定规则”确又很复杂,具体来说Loader面临的挑战主要是如何为每个可执行文件找到一片连续的内存空间。解决这个问题有两个办法,一个是使用内存分段,一个是使用内存分页

Segmentation

内存分段的思路很简单,就是找出一段连续的物理内存,然后和虚拟内存进行映射得到虚拟内存地址,再将这个地址分给被load的binary。这种思路虽然简单,但有一个很大的问题就是内存碎片。如下图所示,当C程序退出后,释放的128MB内存成了不连续的空间,当有loader要加载D程序时,会发现没有足够的连续内存空间可以使用。

解决这个问题,可以使用内存的置换技术,即将程序B先写入到硬盘,释放内存空间来装在D,当D装载完成后,再将B读入到内存中。但是由于内存置换的成本极高,硬盘访问的速度要比内存慢太多,因此这种方案有很大的性能问题。

Paging

为了解决内存碎片和交换问题,现代操作系统采用了内存分页的技术。它将物理内存和虚拟内存均切分成4KB大小的一页。由于数据量小,这种切分带来的好处在于内存置换的成本变低了。

getconf PAGE_SIZE #4096

进一步讲,当程序加载时,loader不需要将程序一次性加载到物理内存中,而是可以按需加载,当需要用到虚拟内存里的指令和数据时,操作系统触发CPU的缺页错误,然后触发加载虚拟内存中的页到物理内存。

这并不是说一段连续完整程序可以被零散的映射物理内存中,程序的寻址空间在内存中依旧是一段连续的区域,只不过当出现内存碎片或者物理内存不足时,系统进行内存置换的成本变小了(因为置换现在是以4KB为单位,速度变快了)。如下图中,当程序A试图加载第三片虚拟内存到物理内存中时,会触发系统的内存置换

总的来说loader可以将程序和物理内存隔离开,然程序不需要考虑实际的物理内存地址,大小和分配方案,大大降低了程序编写复杂度。

Executable

当loader将程序完全加载到内存中后,程序就可以运行了。如果从C/C++程序的角度看,那么程序的入口应该就是main函数,而如果从loaders的角度看,则在main函数执行之前程序就已经start了。我们还是通过反汇编上面的demoApp来观察

注意,这里的demoApp依旧是ELF格式

Disassembly of section .text:

00000000004003e0 <_start>:
  4003e0:	31 ed                	xor    %ebp,%ebp
  4003e2:	49 89 d1             	mov    %rdx,%r9
  4003e5:	5e                   	pop    %rsi
  4003e6:	48 89 e2             	mov    %rsp,%rdx
  4003e9:	48 83 e4 f0          	and    $0xfffffffffffffff0,%rsp
  4003ed:	50                   	push   %rax
  4003ee:	54                   	push   %rsp
  4003ef:	49 c7 c0 10 06 40 00 	mov    $0x400610,%r8
  4003f6:	48 c7 c1 a0 05 40 00 	mov    $0x4005a0,%rcx
  4003fd:	48 c7 c7 40 05 40 00 	mov    $0x400540,%rdi
  400404:	e8 b7 ff ff ff       	callq  4003c0 <__libc_start_main@plt>
  400409:	f4                   	hlt
  40040a:	66 0f 1f 44 00 00    	nopw   0x0(%rax,%rax,1)

我们看到代码段(text section)的第一个函数是_start,这个函数最后又调用了__libc_start_main函数。我们先看看这个函数的原型

int __libc_start_main(
    int *(main) (int, char * *, char * *),  /* address of main function */
    int argc, 
    char * * ubp_av, 
    void (*init) (void), /* address of init function */
    void (*fini) (void), 
    void (*rtld_fini) (void), 
    void (* stack_end));

这个函数的定义在libc中,由于篇幅有限,源码就不展开分析了,但是我们可以大致猜到它的作用,即初始化程序进程中的环境变量,为main函数的执行做准备,比如某个类的构造函数使用了__attribute__((constructor))这种keyword,那么在main函数执行前,自定义的初始化逻辑将被执行。

小结

到目前为止,我们已经对linkers和loaders有了一些直观的感觉,当然这些感觉还很表面,很多细节问题还不是很清楚,比如Symbol Resolution的具体过程是怎样的,Relocation时偏移地址是如何计算的,动态库是如何加载的,等等。我们将在后面逐步讨论这些问题

Resources

nm命令

注意,nm命令不会列出DLL的entry point,除非有和它关联的符号表。

- A :absolute symbol, global
- a :absolute symbol, local
- B :uninitialized data (bss), global
- b :uninitialized data (bss), local
- D :initialized data, global
- d :initialized data, local
- F :file name
- l :line number entry (see -a option)
- N :no defined type, global; this is an unspecified type, compared to the undefined type U
- n :no defined type, local; this is an unspecified type, compared to the undefined type U
- S :section symbol, global
- s :section symbol, local
- T :text symbol, global
- t :text symbol, local (static)
- U :undefined symbol
- ? :unknown symbol