原图

装载的方式

程序执行时所需要的指令和数据必须在内存中才能够正常运行,最简单的办法就是将程序运行所需要的指令和数据全都装入内存中,这就是最简单的静态装入的办法。后来研究发现,程序运行时是有局部性原理的,所以我们可以将程序最常用的部分驻留在内存中,而将一些不太常用的数据存放在磁盘里面,这就是动态装入的基本原理。

覆盖装入(Overlay)和页映射(Paging)是两种很典型的动态装载方法,它们所采用的思想都差不多,原则上都是利用了程序的局部性原理。动态装入的思想是程序用到哪个模块,就将哪个模块装入内存,如果不用就暂时不装入,存放在磁盘中。

页映射

将内存和所有磁盘中的数据和指令按照“页(Page)”为单位划分成若干个页,以后所有的装载和操作的单位就是页。

为了演示页映射的基本机制,假设我们的 32 位机器有 16KB 的内存,每个页大小为 4096 字节,则共有 4 个页,如下表所示。

页编号 地址
F0 0x00000000 - 0xFFFFF000
F1 0x00001000 - 0x00001FFF
F2 0X00002000 - 0X00002FFF
F3 0X00003000 - 0X00003FFF

假设程序所有的指令和数据总和为 32KB,那么程序总共被分为 8 个页。我们将它们编号为 P0~P7。很明显,16KB 的内存无法同时将 32KB 的程序装入,那么我们将按照动态装入的原理来进行整个装入过程。如果程序刚开始执行时的入口地址在 P0,这时装载管理器发现程序的 P0 不在内存中,于是将内存 F0 分配给 P0,并且将 P0 的内容装入 F0;运行一段时间以后,程序需要用到 P5,于是装载管理器将 P5 装入 F1;就这样,当程序用到 P3 和 P6 的时候,它们分别被装入到了 F2 和 F3,它们的映射关系如图 6-4 所示。

很明显,如果这时候程序只需要 P0、P3、P5 和 P6 这 4 个页,那么程序就能一直运行下去。但是问题很明显,如果这时候程序需要访问 P4,那么装载管理器必须做出抉择,它必须放弃目前正在使用的 4 个内存页中的其中一个来装载 P4。至于选择哪个页,我们有很多种算法可以选择,比如可以选择 F0,因为它是第一个被分配掉的内存页(这个算法我们可以称之为 FIFO,先进先出算法):假设装载管理器发现 F2 很少被访问到,那么我们可以选择 F2(这种算法可以称之为 LUR,最少使用算法)。

从操作系统角度看可执行文件的装载

进程的建立

创建一个进程,然后装载相应的可执行文件并且执行。在有虚拟存储的情况下,上述过程最开始只需要做三件事情:

  • 创建一个独立的虚拟地址空间,建立虚拟空间到物理空间的映射关系。创建虚拟地址空间实际上只是分配一个页目录(Page Directory)就可以了,甚至不设置页映射关系,这些映射关系等到后面程序发生页错误的时候再进行设置。
  • 读取可执行文件头,建立虚拟空间与可执行文件的映射关系,是传统意义上“装载”的过程。
  • 将 CPU 的指令寄存器设置成可执行文件的入口地址,启动运行。这一步看似简单,实际上在操作系统层面上比较复杂,它涉及内核堆栈和用户堆栈的切换、CPU 运行权限的切换。不过从进程的角度看这一步可以简单地认为操作系统执行了一条跳转指令,直接跳转到可执行文件的入口地址。还记得 ELF 文件头中保存有入口地址吗?没错,就是这个地址。

让我们考虑最简单的情况,假设我们的 ELF 可执行文件只有一个代码段“.text“,它的虚拟地址为 0x08048000,它在文件中的大小为 0x000e1,对齐为 0x1000。一旦该可执行文件被装载,可执行文件与执行该可执行文件进程的虚拟空间的映射关系如图 6-5 所示。

很明显,这种映射关系只是保存在操作系统内部的一个数据结构。Linux 中将进程虚拟空间中的一个段叫做虚拟内存区域(VMA,Virtual Memory Area)。比如上例中,操作系统创建进程后,会在进程相应的数据结构中设置有一个。text 段的 VMA:它在虚拟空间中的地址为 0x08048000~0x08049000,它对应 ELF 文件中偏移为 0 的。text,它的属性为只读(一般代码段都是只读的)。

页错误

上面的步骤执行完以后,其实可执行文件的真正指令和数据都没有被装入到内存中。操作系统只是通过可执行文件头部的信息建立起可执行文件和进程虚存之间的映射关系而已。假设在上面的例子中,程序的入口地址为 0x08048000,即刚好是。text 段的起始地址。当 CPU 开始打算执行这个地址的指令时,发现页面 0x08048000~0x08049000 是个空页面,于是它就认为这是一个页错误(Page Fault)。CPU 将控制权交给操作系统,操作系统有专门的页错误处理例程来处理这种情况。这时候我们前面提到的装载过程的第二步建立的数据结构起到了很关键的作用,操作系统将查询这个数据结构,然后找到空页面所在的 VMA,计算出相应的页面在可执行文件中的偏移,然后在物理内存中分配一个物理页面,将进程中该虚拟页与分配的物理页之间建立映射关系,然后把控制权再还回给进程,进程从刚才页错误的位置重新开始执行。

随着进程的执行,页错误也会不断地产生,操作系统也会为进程分配相应的物理页面来满足进程执行的需求,如图 6-6 所示。当然有可能进程所需要的内存会超过可用的内存数量,特别是在有多个进程同时执行的时候,这时候操作系统就需要精心组织和分配物理内存,甚至有时候应将分配给进程的物理内存暂时收回等,这就涉及了操作系统的虚拟存储管理。

进程虚存空间分布

ELF 文件链接视图和执行视图

当段的数量增多时,就会产生空间浪费的问题。当我们站在操作系统装载可执行文件的角度看问题时,可以发现它实际上并不关心可执行文件各个段所包含的实际内容,只关心一些跟装载相关的问题,最主要的是段的权限(可读、可写、可执行)。基本上是三种:

  • 以代码段为代表的权限为可读可执行的段。
  • 以数据段和 BSS 段为代表的权限为可读可写的段。
  • 以只读数据段为代表的权限为只读的段。

那么我们可以找到一个很简单的方案就是:对于相同权限的段,把它们合并到一起当作一个段进行映射。比如有两个段分别叫“.text”和“.init”,它们包含的分别是程序的可执行代码和初始化代码,并且它们的权限相同,都是可读并且可执行的。假设。text 为 4097 字节,.init 为 512 字节,这两个段分别映射的话就要占用三个页面,但是,如果将它们合并成一起映射的话只须占用两个页面,如图 6-7 所示。

ELF 可执行文件引入了一个概念叫做“Segment”,一个“Segment”包含一个或多个属性类似的“Section”。正如我们上面的例子中看到的,如果将“.text”段和“.init”段合并在一起看作是一个“Segment'”,那么装载的时候就可以将它们看作一个整体一起映射,也就是说映射以后在进程虚存空间中只有一个相对应的 VMA,而不是两个,这样做的好处是可以很明显地减少页面内部碎片,从而节省了内存空间。

从链接的角度看,ELF 文件是按“Section”存储的,事实也的确如此;从装载的角度看,ELF 文件又可以按照“Segment”划分。

“Segment'”的概念实际上是从装载的角度重新划分了 ELF 的各个段。而系统正是按照、“Segment”而不是“Section”来映射可执行文件的。下面的例子是一个很小的程序,程序本身是不停地循环执行“sleep”操作,除非用户发信号给它,否则就一直运行。它的源代码如下:

1
2
3
4
5
6
7
8
9
#include <stdlib.h>

int main()
{
while(1){
sleep(1000);
}
return 0;
}

我们使用静态连接的方式将其编译连接成可执行文件,然后得到的可执行文件“SectionMapping.elf”是一个 Linux 下很典型的可执行文件:

1
$gcc -static SectionMapping.c -o SectionMapping.elf

使用 readelf 可以看到,这个可执行文件中总共有 32 个段(Section):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
vooxle@liushuai:~$ readelf -S SectionMapping.elf
There are 32 section headers, starting at offset 0xd4588:

Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .note.gnu.propert NOTE 0000000000400270 00000270
0000000000000020 0000000000000000 A 0 0 8
[ 2] .note.gnu.build-i NOTE 0000000000400290 00000290
0000000000000024 0000000000000000 A 0 0 4
[ 3] .note.ABI-tag NOTE 00000000004002b4 000002b4
0000000000000020 0000000000000000 A 0 0 4
[ 4] .rela.plt RELA 00000000004002d8 000002d8
0000000000000240 0000000000000018 AI 0 20 8
[ 5] .init PROGBITS 0000000000401000 00001000
000000000000001b 0000000000000000 AX 0 0 4
[ 6] .plt PROGBITS 0000000000401020 00001020
0000000000000180 0000000000000000 AX 0 0 16
[ 7] .text PROGBITS 00000000004011a0 000011a0
00000000000919a0 0000000000000000 AX 0 0 16
[ 8] __libc_freeres_fn PROGBITS 0000000000492b40 00092b40
0000000000001ca0 0000000000000000 AX 0 0 16
[ 9] .fini PROGBITS 00000000004947e0 000947e0
000000000000000d 0000000000000000 AX 0 0 4
[10] .rodata PROGBITS 0000000000495000 00095000
000000000001bfcc 0000000000000000 A 0 0 32
[11] .stapsdt.base PROGBITS 00000000004b0fcc 000b0fcc
0000000000000001 0000000000000000 A 0 0 1
[12] .eh_frame PROGBITS 00000000004b0fd0 000b0fd0
000000000000a5d4 0000000000000000 A 0 0 8
[13] .gcc_except_table PROGBITS 00000000004bb5a4 000bb5a4
00000000000000b1 0000000000000000 A 0 0 1
[14] .tdata PROGBITS 00000000004bd0c0 000bc0c0
0000000000000020 0000000000000000 WAT 0 0 8
[15] .tbss NOBITS 00000000004bd0e0 000bc0e0
0000000000000040 0000000000000000 WAT 0 0 8
[16] .init_array INIT_ARRAY 00000000004bd0e0 000bc0e0
0000000000000010 0000000000000008 WA 0 0 8
[17] .fini_array FINI_ARRAY 00000000004bd0f0 000bc0f0
0000000000000010 0000000000000008 WA 0 0 8
[18] .data.rel.ro PROGBITS 00000000004bd100 000bc100
0000000000002df4 0000000000000000 WA 0 0 32
[19] .got PROGBITS 00000000004bfef8 000beef8
00000000000000f0 0000000000000000 WA 0 0 8
[20] .got.plt PROGBITS 00000000004c0000 000bf000
00000000000000d8 0000000000000008 WA 0 0 8
[21] .data PROGBITS 00000000004c00e0 000bf0e0
0000000000001a50 0000000000000000 WA 0 0 32
[22] __libc_subfreeres PROGBITS 00000000004c1b30 000c0b30
0000000000000048 0000000000000000 WA 0 0 8
[23] __libc_IO_vtables PROGBITS 00000000004c1b80 000c0b80
00000000000006a8 0000000000000000 WA 0 0 32
[24] __libc_atexit PROGBITS 00000000004c2228 000c1228
0000000000000008 0000000000000000 WA 0 0 8
[25] .bss NOBITS 00000000004c2240 000c1230
0000000000001718 0000000000000000 WA 0 0 32
[26] __libc_freeres_pt NOBITS 00000000004c3958 000c1230
0000000000000028 0000000000000000 WA 0 0 8
[27] .comment PROGBITS 0000000000000000 000c1230
000000000000002a 0000000000000001 MS 0 0 1
[28] .note.stapsdt NOTE 0000000000000000 000c125c
00000000000013e8 0000000000000000 0 0 4
[29] .symtab SYMTAB 0000000000000000 000c2648
000000000000af68 0000000000000018 30 734 8
[30] .strtab STRTAB 0000000000000000 000cd5b0
0000000000006e81 0000000000000000 0 0 1
[31] .shstrtab STRTAB 0000000000000000 000d4431
0000000000000157 0000000000000000 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)

我们可以使用 readelf 命令来查看 ELF 的“Segment”。正如描述“Section”属性的结构叫做段表,描述“Segment'”的结构叫程序头(Program Header),它描述了 ELF 文件该如何被操作系统映射到进程的虚拟空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vooxle@liushuai:~$ readelf -l SectionMapping.elf

Elf file type is EXEC (Executable file)
Entry point 0x401bc0
There are 10 program headers, starting at offset 64

Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
LOAD 0x0000000000000000 0x0000000000400000 0x0000000000400000
0x0000000000000518 0x0000000000000518 R 0x1000
LOAD 0x0000000000001000 0x0000000000401000 0x0000000000401000
0x00000000000937ed 0x00000000000937ed R E 0x1000
LOAD 0x0000000000095000 0x0000000000495000 0x0000000000495000
0x0000000000026655 0x0000000000026655 R 0x1000
LOAD 0x00000000000bc0c0 0x00000000004bd0c0 0x00000000004bd0c0
0x0000000000005170 0x00000000000068c0 RW 0x1000
NOTE 0x0000000000000270 0x0000000000400270 0x0000000000400270
0x0000000000000020 0x0000000000000020 R 0x8
NOTE 0x0000000000000290 0x0000000000400290 0x0000000000400290
0x0000000000000044 0x0000000000000044 R 0x4
TLS 0x00000000000bc0c0 0x00000000004bd0c0 0x00000000004bd0c0
0x0000000000000020 0x0000000000000060 R 0x8
GNU_PROPERTY 0x0000000000000270 0x0000000000400270 0x0000000000400270
0x0000000000000020 0x0000000000000020 R 0x8
GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000
0x0000000000000000 0x0000000000000000 RW 0x10
GNU_RELRO 0x00000000000bc0c0 0x00000000004bd0c0 0x00000000004bd0c0
0x0000000000002f40 0x0000000000002f40 R 0x1

Section to Segment mapping:
Segment Sections...
00 .note.gnu.property .note.gnu.build-id .note.ABI-tag .rela.plt
01 .init .plt .text __libc_freeres_fn .fini
02 .rodata .stapsdt.base .eh_frame .gcc_except_table
03 .tdata .init_array .fini_array .data.rel.ro .got .got.plt .data __libc_subfreeres __libc_IO_vtables __libc_atexit .bss __libc_freeres_ptrs
04 .note.gnu.property
05 .note.gnu.build-id .note.ABI-tag
06 .tdata .tbss
07 .note.gnu.property
08
09 .tdata .init_array .fini_array .data.rel.ro .got

我们可以看到,这个可执行文件中共有 10 个 Segment。从装载的角度看,我们目前只关心两个“LOAD”类型的 Segment,因为只有它是需要被映射的,其他的诸如“NOTE”、“TLS”、“GNU_STACK”都是在装载时起辅助作用的,我们在这里不详细展开。可以用图 6-8 来表示“SectionMapping.elf”可执行文件的段与进程虚拟空间的映射关系。

“SectionMapping.elf”被重新划分成了三个部分,有一些段被归入可读可执行的,它们被统一映射到一个 VMA0;另外一部分段是可读可写的,它们被映射到了 VMA1;还有一部分段在程序装载时没有被映射的,它们是一些包含调试信息和字符串表等段,这些段在程序执行时没有用,所以不需要被映射。很明显,所有相同属性的“Section”被归类到一个“Segment”,并且映射到同一个 VMA。

所以总的来说,“Segment”和“Section”是从不同的角度来划分同一个 ELF 文件。这个在 ELF 中被称为不同的视图(View),从“Section”的角度来看 ELF 文件就是链接视图(Linking View),从“Segment”的角度来看就是执行视图(Execution View)。

堆和栈

在操作系统里面,VMA 除了被用来映射可执行文件中的各个“Segment'”以外,它还可以有其他的作用,操作系统通过使用 VMA 来对进程的地址空间进行管理。我们知道进程在执行的时候它还需要用到栈(Stack)、堆(Heap)等空间,事实上它们在进程的虚拟空间中的表现也是以 VMA 的形式存在的,很多情况下,一个进程中的栈和堆分别都有一个对应的 VMA。在 Linux 下,我们可以通过查看“/proc”来查看进程的虚拟空间分布:

1
2
3
4
5
6
7
8
$ ./SectionMapping.elf &
[1]21963
$ cat /proc/21963/maps
08048000-080b9000 r-xp 00000000 08:01 2801887 ./SectionMapping.elf
080b9000-080bb000 rwxp 00070000 08:01 2801887 ./SectionMapping.elf
080bb000-080de000 rwxp 080bb000 00:00 0 [heap]
bf7ec000-bf802000 rw-p bf7ec0000 00:00 0 [stack]
ffffe000-fffff000 r-xp0 000000000:0 00:00 0 [vdso]

上面的输出结果中:

  • 第一列是 VMA 的地址范围。
  • 第二列是 VMA 的权限,“r”表示可读,“w”表示可写,“x”表示可执行,“p”表示私有(COW,Copy on Write),“s"表示共享。
  • 第三列是偏移,表示 VMA 对应的 Segment 在映像文件中的偏移。
  • 第四列表示映像文件所在设备的主设备号和次设备号。
  • 第五列表示映像文件的节点号。
  • 最后一列是映像文件的路径。

我们可以看到进程中有 5 个 VMA,只有前两个是映射到可执行文件中的两个 Segment。另外三个段的文件所在设备主设备号和次设备号及文件节点号都是 0,则表示它们没有映射到文件中,这种 VMA 叫做匿名虚拟内存区域(Anonymous Virtual Memory Area)。

另外有一个很特殊的 VMA 叫做“vdso”,它的地址己经位于内核空间了(即大于 0xC0000000 的地址),事实上它是一个内核的模块,进程可以通过访问这个 VMA 来跟内核进行一些通信。

通过上面的例子,让我们小结关于进程虚拟地址空间的概念:操作系统通过给进程空间划分出一个个 VMA 来管理进程的虚拟空间;基本原则是将相同权限属性的、有相同映像文件的映射成一个 VMA;一个进程基本上可以分为如下几种 VMA 区域:

  • 代码 VMA,权限只读、可执行;有映像文件。
  • 数据 VMA,权限可读写、可执行;有映像文件。
  • 堆 VMA,权限可读写、可执行:无映像文件,匿名,可向上扩展。
  • 栈 VMA,权限可读写、不可执行;无映像文件,匿名,可向下扩展。

当我们在讨论进程虚拟空间的“Segment”的时候,基本上就是指上面的几种 VMA。现在再让我们来看一个常见进程的虚拟空间是怎么样的,如图 6-9 所示。

段地址对齐

如果有很多段的大小很小,按照 page 对齐映射会造成空间的浪费,为了解决这种问题,有些 UNIX 系统采用了一个很取巧的办法,就是让那些各个段接壤部分共享一个物理页面,然后将该物理页面分别映射多次。

Linux 内核装载 ELF 过程简介

当我们在 Linux 系统的 bash 下输入一个命令执行某个 ELF 程序时,Linux 系统是怎样装载这个 ELF 文件并且执行它的呢? 首先在用户层面,bash 进程会调用 fork() 系统调用创建一个新的进程,然后新的进程调用 execve() 系统调用执行指定的 ELF 文件,原先的 bash 进程继续返回等待刚才启动的新进程结束,然后继续等待用户输入命令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main()
{
char buf[1024]={0};
pid_t pid;
while(1)
{
printf("minibashs");
scanf("s",buf);
pid fork();
if(pid =0) {
if(execlp(buf,0) < 0) {
printf("exec error\n");
}
}
else if(pid >0) {
int status;
waitpid(pid,&status,0);
}
else
printf("fork error &d\n",pid);
}
return 0;
}

在进入 execve() 系统调用之后,Linux 内核就开始进行真正的装载工作。在内核中,execve() 系统调用相应的入口是 sys_execve(),进行一些参数的检查复制之后,调用 do_execve()。do_execve() 会首先查找被执行的文件,如果找到文件,则读取文件的前 128 个字节。(Linux 支持的可执行文件不止 ELF 一种,还有 a.out、Java 程序和以“#!”开始的脚本程序)。

当 do_execve() 读取了这 128 个字节的文件头部之后,然后调用 search_binary_handle() 去搜索和匹配合适的可执行文件装载处理过程。Linux 中所有被支持的可执行文件格式都有相应的装载处理过程,search_binary_handle() 会通过判断文件头部的魔数确定文件的格式,并且调用相应的装载处理过程。比如 ELF 可执行文件的装载处理过程叫做 load_elf_binary();a.out 可执行文件的装载处理过程叫做 load_aout_binary();而装载可执行脚本程序的处理过程叫做 load_script()。这里我们只关心 ELF 可执行文件的装载,load_elf_binary(),这个函数的代码比较长,它的主要步骤是:

  • 检查 ELF 可执行文件格式的有效性,比如魔数、程序头表中段(Segment)的数量。
  • 寻找动态链接的“.interp”段,设置动态链接器路径。
  • 根据 ELF 可执行文件的程序头表的描述,对 ELF 文件进行映射,比如代码、数据、只读数据。
  • 初始化 ELF 进程环境,比如进程启动时 EDX 寄存器的地址应该是 DT FINI 的地址。
  • 将系统调用的返回地址修改成 ELF 可执行文件的入口点,这个入口点取决于程序的链接方式,对于静态链接的 ELF 可执行文件,这个程序入口就是 ELF 文件的文件头中 e_entry 所指的地址;对于动态链接的 ELF 可执行文件,程序入口点是动态链接器。

当 load_elf_binary() 执行完毕,返回至 do_execve() 再返回至 sys_execve() 时,上面的第 5 步中已经把系统调用的返回地址改成了被装载的 ELF 程序的入口地址了。所以当 sys_execve() 系统调用从内核态返回到用户态时,EIP 寄存器直接跳转到了 ELF 程序的入口地址,于是新的程序开始执行,ELF 可执行文件装载完成。

参考文献

《程序员的自我修养》