链接装载与库：第六章——可执行文件的装载与进程

可执行文件只有装载到内存以后才能被CPU执行。早期的程序装载十分简陋，装载的基本过程就是把程序从外部存储器中读取到内存中的某个位置。随着硬件MMU的诞生，多进程、多用户、虚拟存储的操作系统出现以后，可执行文件的装载过程变得非常复杂。

一、进程虚拟地址空间

程序和进程有什么区别：程序(或者狭义上讲可执行文件)是一个静态的概念，它就是一些预先编译好的指令和数据集合的一个文件；进程则是一个动态的概念，它是程序运行时的一个过程，很多时候把动态库叫做运行时(Runtime)也有一定的含义。

每个程序被运行起来以后，它将拥有自己独立的虚拟地址空间(Virtual Address Space)，这个虚拟地址空间的大小由计算机的硬件平台决定，具体地说是由CPU的位数决定的。硬件决定了地址空间的最大理论上限，即硬件的寻址空间大小，比如32位的硬件平台决定了虚拟地址空间的地址为0到2^32 -1，即0x00000000 ~ 0xFFFFFFFF，也就是我们常说的4GB虚拟空间大小；而64位的硬件平台具有64位寻址能力，它的虚拟地址空间达到了2^64字节，即0x0000000000000000~0xFFFFFFFFFFFFFFFF，总共17179869184GB。

从程序的角度看，我们可以通过判断C语言程序中的指针所占的空间来计算虚拟地址空间的大小。一般来说，C语言指针大小的位数与虚拟地址空间的位数相同，如32位平台下的指针为32位，即4字节；64位平台下的指针为64位，即8字节。

PAE(Physical Address Extension)：从硬件层面上来讲，原先的32位地址线只能访问最多4GB的物理内存。但是自从扩展至36位地址线之后，Intel修改了页映射的方式，使得新的映射方式可以访问到更多的物理内存。Intel把这个地址扩展方式叫做PAE。扩展的物理地址空间，对于普通应用程序来说正常情况下感觉不到它的存在，因为这主要是操作系统的事，在应用程序里，只有32位的虚拟地址空间。那么应用程序该如何使用这些大于常规的内存空间呢？一个很常见的方法就是操作系统提供一个窗口映射的方法，把这些额外的内存映射到进程地址空间中来。在Windows下，这种访问内存的操作方式叫做AWE(Address Windowing Extensions)；而像Linux等UNIX类操作系统则采用mmap()系统调用来实现。

二、装载方式

程序执行时所需要的指令和数据必须在内存中才能够正常运行，最简单的方法就是将程序运行所需要的指令和数据全都装入内存中，这样程序就可以顺利运行，这就是最简单的静态装入的方法。但是很多情况下程序所需要的内存数量大于物理内存的数量，当内存的数量不够时，根本的解决办法就是添加内存，但是内存是稀有资源。人们总是想尽各种办法，在不添加内存的情况下让更多的程序运行起来。后来发现程序运行时是有局部性原理，所以我们可以将程序最常用的部分驻留在内存中，而将一些不太常用的数据存放在磁盘里面，这就是动态装入的基本原理。

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

2.1 覆盖装入

在没有发明虚拟存储之前使用比较广泛，现在已经几乎被淘汰了。覆盖装入的方法把挖掘内存嵌入的任务交给了程序员，程序员在编写程序的时候必须手工将程序分割成若干块，然后编写一个小的辅助代码来管理这些模块何时应该驻留内存而何时应该被替换掉。这个小的辅助代码就是所谓的覆盖管理器(Overlay Manager)。覆盖装入是典型的利用时间换取空间的方法。

如一个程序有主模块main(1024byte)会调用到模块A(512byte)和模块B(256byte)，但A、B之间不会互调。不考虑内存对齐和装载地址限制，理论上运行这个程序需要1792个byte。如果采用覆盖装入，内存可以按照下图安排，只需要1536个byte。模块A和B共享内存，main调A时覆盖管理器将A从文件中读入内存，调B时将B从文件读入内存。

2.2 页映射

是虚拟存储机制的一部分，它随着虚拟存储的发明而诞生。与覆盖装入的原理相似，页映射也不是一下子就把程序的所有数据和指令都装入内存，而是将内存和所有磁盘中的数据和指令按照”页(Page)”为单位划分成若干个页，以后所有的装载和操作的单位都是页。硬件规定页的大小有4096字节、8192字节、2MB、4MB等。

假设机器内存大小为16KB，程序指令和数据总和为32KB，页大小为4096字节，所以内存总共分为4个页(F0~F3)，程序分为8个页(P0~P7)。如果程序入口地址在P0，装载管理器发现P0不再内存，于是将内存F0分配给P0，并将P0的内容装入F0；运行一段时间，程序需要用到P5，将P5装入F1；就这样，当程序用到P3和P6时，分别将他们装入F2和F3，映射关系如下图所示。

如果这时候程序需要访问P4，装载管理器必须要作出抉择，必须放弃正在使用的4个内存页中的其中一个来装载P4。有很多种算法可以选择，如选择第一个分配掉的内存页F0（FIFO，先进先出算法），或者程序运行期间发现F2最少被访问到就选择F2（LUR，最少使用算法）。

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

按照刚刚描述的装载方法，假设程序有 P0-P7 8个页，内存有 M0 - M3 四个页，如果程序使用物理地址直接操作，那么每次替换页都要进行重定位，这当然是不可接受的。在虚拟存储中，硬件MMU都提供了地址转换的功能，也正是通过转换和页映射，使得动态加载可执行文件的方式和静态加载有很大区别。

3.1 进程的建立

进程间的不同的最关键特征是有独立的虚拟地址空间，我们从一个最典型的例子开始：创建一个进程，然后装载相应的可执行文件并且执行，在有虚拟存储的情况下，主要做的事情如下：

1. 创建一个独立的虚拟地址空间
2. 读取可执行文件头，并且建立虚拟空间与可执行文件的映射关系
3. 将CPU的指令寄存器设置成可执行文件的入口地址，启动执行。

创建虚拟地址空间。一个虚拟地址空间是由一组页映射函数将虚拟空间的各个页映射到相应的物理空间，那么创建一个虚拟空间实际上并不是创建空间，而是创建映射函数所需要的相应的数据结构。在i386 linux下，创建虚拟地址空间实际上只是分配了一个页目录就可以了，甚至不设置页映射关系，这些映射关系等到后面程序发生页错误的时候再进行设置。

读取可执行文件头，并且建立虚拟地址空间与可执行文件的映射关系。这一步所做是虚拟地址空间与可执行文件的映射关系。当程序执行发生页错误的时候，操作系统将从物理内存中分配一个物理页，然后将该缺页从磁盘中读取到内存中，再设置缺页的虚拟页和物理页的映射关系，这样程序才得以正常的运行。但是有一点就是，操作系统捕获到缺页错误的时候，他应该知道程序当前所需要的页在可执行文件中的哪一个位置。这就是虚拟空间与可执行文件之间的映射关系。这一步就是整个装载过程最重要的一步。

Linux把虚拟空间的一个段叫虚拟内存区域（VMA）而Windows叫虚拟段（Virtual Section）。举个例子，把某ELF从0x10000到0x1000e0（长度对齐到0x1000）的段.text映射到虚拟存储空间的0x08048000 - 0x08049000，这个进程的数据结构中就有了一个.text段的VMA，在虚拟空间的地址就是0x48000-0x49000，对应ELF中0x10000。

将CPU指令寄存器设置成可执行文件的文件入口，启动运行。操作系统通过设置CPU的指令寄存器将控制权交给进程，由此进程开始执行。
这一步看似简单，实际上涉及到内核堆栈和用户堆栈的切换、CPU权限的切换，但是对于进程来说，可以简单的认为操作系统执行了一步跳转。

3.2 页错误

通过上面的步骤执行完以后，可执行文件的真正指令和数据并没有被装入内存中。操作系统只是通过可执行文件头部的信息建立起可执行文件和进程虚存之间的映射关系而已。当CPU开始打算执行一个地址的指令时，发现对应的页面是一个空页面，就会认为这是一个页错误。CPU会将控制权交给操作系统，操作系统有专门的页错误处理例程来处理这种情况。这是用就需要用到前面提到的可执行文件和虚存之间的映射结构。操作系统会查询这个数据结构，然后知道空页面所在的VMA，计算出相应的页面在可执行文件中的偏移，然后在物理内存中分配一个物理页面，将进程中的该虚拟页与分配的物理页之间建立映射关系，然后把控制权交给进程，进程从刚才页错误的位置重新开始执行。

随着进程的执行，页错误不断的发生，操作系统也会为集成分配相应的物理页来满足进程执行的需求。当进程所需要的内存超过可用的内存数量时，特别是多个进程在同时执行的饿时候，这时操作系统就需要精心组织和分配物理内存，甚至有时候很将分配给进程的物理内存暂时回收。

四、进程虚存空间的分布

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

因为ELF文件被映射的时候，是以系统页长度为单位进行分配的，每一个段在映射时的长度都是系统页长度的整数倍。当可执行文件中的段数量很多时候，就会产生内存空间浪费的问题。

站在操作系统的角度装载可执行文件的角度，实际上操作系统并无关心可执行文件各个段所包含的实际内容，操作系统只关心一些跟装载相关的问题，主要的是就是段的权限（可读、可写、可执行）。ELF文件中，段的权限往往只有为数不多的几种组合。

• 以代码段为代表，可读可执行
• 以数据段和BSS段为代表，可读可写
• 为只读数据段为代表，只读

对于相同权限的段，把它们合并到一起当做一个段进行映射。ELF可执行文件引入Segment的概念，一个Segment包含了一个或者多个属性相似的Section。在装载的时候按照Segment整体一起映射，就是说映射以后进程虚存空间只有一个相对应的VMA，这样就可以明显的减少页面内部碎片，节省了内存空间。如下图所示：

Segment概念实际上是从装载的角度重新划分ELF的各个段。在将目标文件链接成可执行文件的时候，链接器就会尽量把相同权限的属性的段分配到同一个空间。在ELF中把这些属性相似的，连在一起的段叫做一个Segment，而系统正式按照Segment进行映射可执行文件的。

4.2 堆和栈

在操作系统中，VMA除了被用来映射可执行文件中的各个segment以外，操作系统还可以通过VMAlain对进程的地址空间进行管理。进程在执行时用到的堆和栈也是以VMA的形式存在的。很多情况下，一个称重的栈和堆都有一个对应的VMA。

上面输出第一列是VMA的地址范围，第二列是VMA的权限，r（读）w（写）x（可执行）p（私有）s（共享），第三列是偏移，表示VMA对应的segment在映像文件中的偏移。第四列是映像文件所在的设备的主设备号与次设备号。第五列表示映像文件的节点号，第六列是映像文件的路径。

我们看到进程中有5个VMA，前两个映射到可执行文件中的两个Segment。另外三个段主设备号和次设备号都是0，表示他们没有映射到文件中，这种VMA叫做匿名虚拟内存区域。有两个区域是heap和stack，这两个VMA在所有的进程中几乎都存在。栈一般也叫堆栈，每一个线程都有自己的堆栈，对于单线程来说，这个VMA堆栈就全部归自己使用。还有一个VMA叫vdso，地址位于内核空间（即大于0xc0000000），是一个内核模块，进程可以通过访问这个VMA跟内核进行通信。

综上，操作系统通过给进程空间或分出了一个个的VMA来管理进程空间的虚拟空间，基本原则就是将相同权限属性的、有相同映象文件的映射成一个VMA，一个进程分为如下几种VMA区域（这个图看着更直观）：

• 代码VMA，权限只读、可执行，有映象文件
• 数据VMA，权限可读写、可执行，有映象文件
• 堆VMA，权限可读写，可执行，无映象文件，倪敏个，向上扩展
• 栈VMA，权限可读写，不可执行，无映象文件，匿名，向下扩展。

4.3 堆的最大申请数量

linux下虚拟地址空间分配为进程本身使用的是3G。使用测试程序在linux只能2.9G，windows上只能1.5G左右。用下面小程序可以测试malloc最大申请数量：

#include 
#include 

unsigned long maximum = 0;

int main(int argn, char** argv){
  unsigned blocksize[] = { 1024 * 1024 * 1024, 1024 * 1024, 1024, 1 };
  int i, count, len = sizeof(blocksize)/sizeof(unsigned);
  for(i = 0; i < len; i++){
      for(count = 1;; count++){
        void *block = malloc(maximum + blocksize[i] * count);
        if (block) {
          maximum = maximum + blocksize[i] * count;
          free(block);
          cond++;
        } else {
          break;
        }
      }
  }
  printf("maximum malloc size = %llu Byte\n", maximum);
  printf("maximum malloc size = %llu KB\n", maximum/(1024));
  printf("maximum malloc size = %llu MB\n", maximum/(1024 * 1024));
  printf("maximum malloc size = %llu GB\n", maximum/(1024 * 1024 * 1024));
}
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

4.4 段地址对齐

按照segment进行段对齐，还是会产生内存碎片。
Unix采用了取巧的办法，即让那些各个段接壤的部分共享一个物理页面，然后该物理页面分别映射两次。

4.5 进程栈初始化

进程刚刚开始的时候，需要知道一些进程运行的环境，最基本的就是系统环境变量和进程的运行参数。最常见的一个做法就是操作系统在进程启动前将这些信息保存到进程的虚拟空间的栈中。假设系统有两个环境变量：

HOME=/home/user,
PATH=/usr/bin
1
2

然后运行命令：prog 123，再假设堆栈段底部的地址为0xBF802000，则进程初始化后的栈如下图所示：

栈顶寄存器esp指向的位置是初始化以后堆栈的顶部。最前面的四个字节是命令行参数的数量。紧接着就是分别指向这两个参数的字符串指针，后面跟一个0。接着是指向环境变量字符串的指针，后面跟一个0结尾。

进程在启动以后，程序的库部分会把堆栈里的初始化信息中的参数信息传递给main函数，也就是我们所熟知的main的argc和argv参数。

五、Linux内核装载ELF过程简介

当linux系统在bash下输入一个命令执行ELF的时候。
首先在用户层面，bash进程会调用fork系统调用创建一个新的进程，然后新的进程调用execve系统调用执行指定的ELF文件。原先的bash进程继续返回等待刚才启动的新进程结束，然后继续等待用户输入命令。
在进入execve系统调用之后，linux内核就开始进行了真正的装载工作。在内核中，execve系统调用的入口函数是sys_execve，sys_execve进行一些参数的检查和复制之后，调用do_execve，do_execve首先查抄被执行的文件，如果找到文件，则读取文件的前128个字节。读128字节是为了文件的格式、然后调用search_binary_handler去搜索和匹配合适的可执行文件装载处理过程。linux中所有被支持的可执行文件格式都有相应的装载处理过程，search_binary_handler会通过判断文件头部的魔数确定文件的格式，并且调用相应的装载处理过程。ELF客户自行文件的装载处理过程叫做load_elf_binary。load_elf_binary主要的步骤如下：

检查ELF可执行文件格式的有效性，比如魔数、程序头表中的段的数量
寻找动态链接的.interp段，设置动态链接器路径
根据ELF可执行文件的程序头表的描述，对ELF文件进行映射
初始化ELF进程环境，比如进程启动时EDX寄存器的地址应该是什么
将系统调用的返回地址修改成ELF可执行文件的入口点。
当load_elf_binary执行完毕，返回到do_execve，再返回sys_execve时，已经把系统调用的返回地址改成了被装载的ELF程序的入口地址了。当sys_execve从内核态返回用户态时，EIP寄存器直接跳转到了ELF程序的入口地址，于是程序开始执行，ELF可执行文件装载完毕。