程序运行的前世今生

总结自书籍《程序员的自我修养—链接、装载与库》

1. Hello World运行中被隐藏的过程

HoelloWorld在编译运行过程中可以分为4个步骤，预处理、编译、汇编和链接。

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

• 预处理：主要处理源代码文件中以#开头的预编译指令。比如#include <stdio.h>命令告诉预处理器读取系统头文件stdio.h的内容，并把它直接插入到程序文本中，一起被预编译成一个.i文件。主要处理规则如下：
• 将所有的#define删除，并展开所有的宏定义。
• 处理所有条件预编译指令，如#if，#ifdef，#elif，#else，#endif。
• 处理#include预编译指令，将被包含的文件插入到该预编译指令的位置。
• 删除所有的注释。
• 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号。
• 保留所得的#pragma编译器指令，因为编译器需要适用他们。
• 编译：把预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后生产相应的汇编代码文件。这个过程是整个程序构建的核心部分，也是最复杂的部分之一。这样，hello.i就被翻译成文本文件hello.s。
• 汇编：将汇编代码转变成机器可以执行的指令，打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件hello.o。几乎每一条汇编语句都对应一条机器指令。
• 链接：将个模块之间相互引用的部分正确地连接，并生成一个可执行目标文件。如hello程序调用了printf函数，该函数存在于一个名为printf.o的单独的预编译好了的目标文件中，而这个文件必须合并到hello.o程序中，这就是链接器所做的事。链接的主要过程包括地址和空间分配、符号决议和重定位等步骤。

1.1 编译

编译的过程可分为6步：词法分析、语法分析、语义分析、源代码优化、代码生成和目标代码优化。

1. 词法分析：首先源代码被输入到扫描器进行词法分析，通过一种类似于有限状态机的算法将源代码的字符序列分割成一系列的记号（Token）。记号有关键字、标识符、字面量（数字、字符串等）和特殊符号（加号等号等）。在识别记号的同时，扫描器也将标识符存放到符号表，将字面量存放到文字表等，以备后续使用。

2. 语法分析：语法分析器对有扫描器产生的记号进行语法分析，产生语法树，整个过程采用了上下文无关语法（context-free Grammar）的分析手段。语法树就是以表达式为节点的树，图示为array[index] = (index + 4) * (2 + 6)的语法树。在语法分析的同时，很多运算符的优先级和含义也被确定下来，如果出现表达式不合法，编译器就会报告语法分析阶段的错误。
   

   

3. 语义分析：语法分析仅能对表达式的语法进行分析，并不能分析该语句在语法上是否合法，而这就是语义分析器的工作。编译器所能分析的语义为静态语义（即在编译期间可以确定的语义，与之对应的动态语义是指只有在运行期才能确定的语义），包括声明和类型的匹配，类型的转换等。经过语义分析后，整个语法树的表达式都被标识了类型，如果有些类型需要做隐式转换，语义分析程序就会在语法树中插入相应的转换节点。
   

   

4. 源代码优化：源代码优化器会在源代码级别对程序进行优化，例如（2+6）这个表达式可以被优化掉，因为其值能够在编译期被确定。一般源代码优化器会将整个语法树转换成中间代码（语法树的顺序表示），因为直接在语法树上做优化比较困难。常见的中间代码有三地址码和P-代码。
   中间代码使得编译器可以分为前端和后端，前端负责产生机器无关的中间代码，后端将中间代码转换成目标代码，一些该平台编译器可能针对不同平台有数个后端。

5. 目标代码生成与优化：代码生成器将中间代码转换成目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。目标代码优化器也会对生成的目标代码进行优化，如选择合适的寻址方式，使用移位代替乘法运算等。

1.2 目标文件

编译器编译源码后生成的文件叫做目标文件，目标文件除了包含编译后的机器指令代码和数据外，还包括了链接时所须的一些信息，如符号表、调试信息和字符串等。一般目标文件将这些信息按不同的属性，以段（segment）的形式存储。机器指令被放在.code或.text的代码段里，全局变量和局部静态变量经常存放在.data的数据段里，未初始化的全局变量和局部静态变量一般放在.bss的段里，以节省内存空间。目标文件的格式是ELF，其开头是一个文件头，它描述了整个文件的文件属性和段表（一个描述文件中各个段的数组，包含各段的偏移位置和属性）。

除了上述3个基本段之外，目标文件也可能含有只读数据段.rodata、注释信息段.comment和堆栈提示段.notw.GNU-stack等。

总体来说，目标代码主要分为两段：程序指令和程序数据。代码段属于程序指令，而数据段和.bss段属于程序数据。这样做有以下几点好处：

1. 当程序被装载后，数据和指令被映射到两个虚存区域，其权限被分别设置为可读写和只读，这样可以防止程序的指令被有意无意地修改。
2. 现代CPU的缓存都被设计成数据缓存和指令缓存分离，所以指令和数据分开存放可以提高CPU缓存命中率。
3. 当系统中运行着多个该程序的副本时，其指令都是一样的，所以内存中只需要保存一份该程序的指令部分。

1.3 链接的接口：符号

链接过程的本质就是把多个不同的目标文件相互粘到一起。在链接中，目标文件之间相互拼合实际上是目标文件之间对地址的引用，即对函数和变量的地址的引用。如目标文件B引用了目标文件A中的foo函数。在链接中，将函数和变量称为符号，其名字就是符号名。

因此，我们可以将符号看作是链接中的粘合剂，每一个目标文件都会有一个相应的符号表.symtab，其中记录了目标文件中用到的所有符号。每个符号有一个对应的值，叫符号值，就是变量和函数的地址。除了函数和变量之外，还存在一些其他的符号，如定义在本目标文件中的全局符号，在本文件中引用的全局符号，段名，行号，局部符号等。

不同的文件可能存在使用相同的函数或变量名的情况。C++中的命名空间，可以解决多模块的符号冲突问题。为支持C++类，继承，虚机制，重载等特性，人们发明了符号修饰的机制。

C++为了兼容C，在符号的管理上有一个用来声明或定义C的符号的extern "C"关键字。C++编译器会将在该关键字大括号内部的代码当作C语言代码除了，C++的名称修饰

extern "C"{
    int func(int);
    int var;}

2. 静态链接与动态链接

即使是最简单的程序也会依赖于别人已经写好的成熟的软件库，那么我们写的代码怎么和别人写的库集成在一起呢？这就是链接所要解决的问题。比如HelloWorld程序中的main函数引用了标准库提供的printf函数，链接所要解决的就是让我们的程序能正确地找到printf函数。解决这个问题有两个办法：一种方式是在生成可执行文件的时候，把printf函数相关的二进制指令和数据包含在最终的可执行文件中，这就是静态链接；另外一种方式是在程序运行的时候，再去加载printf函数相关的二进制指令和数据，这就是动态链接。

静态链接就是在生成可执行文件的时候，把所有需要的函数的二进制代码都包含到可执行文件中去。因此，链接器需要知道参与链接的目标文件需要哪些函数，同时也要知道每个目标文件都能提供什么函数，这样链接器才能知道是不是每个目标文件所需要的函数都能正确地链接。如果某个目标文件需要的函数在参与链接的目标文件中都找不到的话，链接器就报错了。

静态链接看起来很简单，但是有些不足。其中之一就对磁盘空间和内存空间的浪费。标准库中那些函数会被放到每个静态链接的可执行文件中，在运行的时候，这些重复的内容也会被不同的可执行文件加载到内存中去。同时，如果静态库有更新的话，所有可执行文件都得重新链接才能使用新的静态库。动态链接就是为了解决这个问题而出现的。所谓动态链接就是在运行的时候再去链接。理解动态链接需要从两个角度来看，一是从动态库的角度，二是从使用动态库的可执行文件的角度。

从动态库的角度来看，动态库像普通的可执行文件一样，有其代码段和数据段。为了使得动态库在内存中只有一份，需要保证不管动态库装载到什么位置都不需要修改动态库中代码段的内容，从而实现动态库中代码段的共享。而数据段中的内容需要做到进程间的隔离，因此必须是私有的，也就是每个进程都有一份。因此，动态库的做法是把代码段中变化的部分放到数据段中去，这样代码段中剩下的就是不变的内容，就可以装载到虚拟内存的任何位置。代码段中变化的内容主要包括了对外部函数和变量的引用。

静态链接的可执行文件在装载进入内存后就可以开始运行了，因为所有的外部函数都已经包含在可执行文件中。而动态链接的可执行文件中对外部函数的引用地址在生成可执行文件的时候是未知的，所以在这些地址被修正前是动态链接生成的可执行文件是不能运行的。因此，动态链接生成的可执行文件运行前，系统会首先将动态链接库加载到内存中，动态链接器所在的路径在可执行文件可以查到的。当所有的库都被加载进来以后，类似于静态链接，动态链接器从各个动态库中可以知道每个库都提供什么函数（符号表）和哪些函数引用需要重定位（重定位表），然后修正.got和.got.plt中的符号到正确的地址，完成之后就可以将控制权交给可执行文件的入口地址，从而开始执行我们编写的代码了。可见，动态链接器在程序运行前需要做大量的工作（修正符号地址），为了提高效率，一般采用的是延迟绑定，也就是只有用到某个函数才去修正.got.plt中地址。

总结：链接解决我们写的程序是如何和别的库组合在一起这个问题。每个参与链接的目标文件中都提供了这样的信息：我有什么符号（变量或者函数），我需要什么符号，这样链接器才能确定参与链接的目标文件和库是否能组合在一起。静态链接是在生成可执行文件的时候把需要的所有内容都包含在了可执行文件中，这导致的问题是可执行文件大，浪费磁盘和内存空间以及静态库升级的问题。动态链接是在程序运行的时候完成链接的，首先是动态链接器被加载到内存中，然后动态链接器再完成类似于静态链接器的所做的事情。

3. 装载

程序执行所需要的指令和数据（可执行文件）只有装载到内存以后才能被CPU执行，如果将其全部装入内存会导致内存占用大，甚至不够的情况。由于程序运行时是有局部性原理的，为尽可能有效地利用内存，我们可以将程序最常用的部分驻留在内存中，而将一些不太常用的数据存放在磁盘里面，这就是动态装载的基本原理。覆盖装入和页映射是两种典型的动态装载方法，覆盖装载在虚拟内存发明滞后已经很少使用，所以下面我们仅介绍页映射方法。

页映射是将内存和所有磁盘中的数据和指令按照页为单位划分为若干页。假设程序的可执行文件共32KB，那么程序可被分为8页（每页大小为4KB），并编号为P0至P7；而我们的机器只拥有16KB的内存（可被分为4页，编号为F0至F3）。很明显我们无法将32KB的程序同时装入16KB的内存中，那么我们只能将动态装入程序的指令和数据。

如果程序开始执行的入口地址为P0，这是装载器发现P0不在内存中，于是将P0装入F0；运行一段时间后程序需要用到P5，于是装载器将P5装入F1；需要P3和P6时再分别装入F2和F3。当程序运行一段时间后又需要P4，那么装载器就必须作为抉择，将一个很少访问的页面放弃（比如P0），并将P4装入对应的物理内存中（F0）。程序接着按照这样的方式运行。

4. 程序的内存布局

内存空间分为内核空间和用户空间，大多数操作系统会将一部分高位内存地址分配给内存使用，应用程序无法访问；剩下的空间则称为用户空间，他可分为以下几个区域：

• 栈：用于维护函数调用的上下文。栈通常分配在用户空间的最高地址处分配。
• 堆：用来容纳应用程序动态分配的内存区域。当程序使用malloc或new分配内存时，得到的内存来自堆。堆通常位于栈的下方。
• 可执行文件映像：存储可执行文件在内存里的映像，由装载器在装载时将可执行文件的内存读取或映射到这里。
• 保留区：内存中受到保护而禁止访问的内存区域。

上图中有一个没有介绍的“动态链接库映射区”，该区域是用于映射装载的动态链接库。图中的箭头标明了几个可变大小区域的增长方向，栈是向低地址增长的，堆是向高地址增长的。

4.1 栈与调用惯例

栈是一个遵循先入后出规则的动态内存区域，程序可以将数据压入栈中，也可以将数据从栈顶弹出。栈保存了一个函数调用所需的维护信息，被称为堆栈帧，它一般包含以下几个内容：

• 函数的返回地址和参数；
• 临时变量：包括函数的非静态局部变量和编译器自动生成的其他临时变量。
• 保存的上下文：包括在函数调用前后需要保持不变的寄存器。

在i386中，一个函数的活动记录用ebp和esp这两个寄存器划定范围。esp始终指向栈的顶部，同时也就指向了当前函数活动记录的顶部，而ebp则指向了函数活动记录的一个固定位置。ebp不会随函数的执行而变化，而esp始终指向栈顶，会随着函数的执行不断变化。edp之前保存了这个函数的返回地址和参数，edp指向的则是调用该函数之前的edp值，这样在函数返回时，edp可以通过读取这个值恢复到调用之前的值。

函数的调用方和被调用方对于函数如何调用需要有一个明确的约定，只有双方都遵守同样的约定，函数才能被正确地调用，这样的约定称为调用惯例。它包含如下几个内容：

• 函数参数的传递顺序和方式。函数参数传递最常见的是通过栈传递，函数调用方将参数按一定顺序压入栈中，函数自己再从栈中将参数取出。有些调用惯例还允许使用寄存器传递参数，以提高性能。
• 栈的维护方式。参数弹出的工作是由函数的调用方完成，还是由函数本身完成。
• 名字修饰的策略。为了链接的时候对调用惯例进行区分，调用惯例要对函数本身的名字进行修饰。不同的调用惯例有着不同的名字修饰策略。

在C语言里，默认的调用惯例为cdecl，其规定从右至左的顺序将参数压入栈中，出栈操作有函数调用方执行，名字修饰方式为直接在函数名前加一个下划线。

4.2 堆与内存管理

堆是一块巨大的内存空间，常常占据着整个虚拟空间的绝大部分。在这片空间里，程序可以请求一块连续内存，并自由地使用，并在程序主动放弃之前一直有效。

进程的内存管理并没有交给操作系统内核管理，这样做性能较差，因为每次程序申请或者释放对空间都要进行系统调用。系统调用的性能开销很大，当程序对堆的操作比较频繁时，将会严重影响程序性能。比较好的做法就是程序向操作系统申请一块适当大小的堆空间，然后由程序自己管理这块空间，而具体来讲，管理着堆空间分配往往是程序的运行库。运行库相当于向操作系统批发了一块较大的堆空间，然后“零售”给程序用。当全部“售完”或程序有大量的内存需求时，在根据实际需求向操作系统“进货”。当然运行库在向零售堆空间时，必须管理它批发来的堆空间，不能把同一块地址出售两次，导致地址的冲突。

Linux进程堆管理
进程地址空间中，除了可执行文件、共享库和栈之外，剩余的未分配的空间都可以被用来作为堆空间。Linux下的进程管理提供了两种堆分配方式，即两个系统调用：一个是brk()，另外一个是mmap()。

int brk(void* end_data_segment)
void *mmap{void *start,  size_t length, int prot, int flags, ...);

brk()的作用实际上就是设置进程数据段的结束地址，即它可以扩大或者缩小数据段。如果我们将数据段的结束地址向高地址移动，那么扩大的那部分空间就可以被我们使用，把这块空间拿来作为堆空间是最常见的做法之一。mmap的前两个参数分别用于指定需要申请的空间的起始地址和长度，如果起始地址设置为0，那么linux系统会自动挑选合适的起始地址。prot/flags这两个参数用于设置申请的空间的权限（可读，可写，可执行）以及映像类型（文件映射、匿名空间等）。

堆分配算法
在动态分配内存后，那么我们就要来思考如何管理这块大的内存。主要有三种方法，空闲链表和位图法以及对象池。

空闲链表（Free List)是把堆中各个空闲的块按照链表的方式连接起来，当用户请求一块空间时，可以遍历整个链表，直到找到合适大小的块并且将它拆分；当用户释放空间时将它合并到空闲链表中。空闲链表是这样一种结构，在堆里的每一个空闲空间的开头（或结尾）有一个头，头结构里记录了上一个和下一个空闲块的地址，也就是说，所有的空闲块形成了一个链表。如下所示：

在这样的结构下如何分配空间呢？首先在空闲链表查找足够容纳请求大小的一个空闲块，并将这个块分为两部分，程序请求的空间和剩余下来的空闲链表。然后将链表里对应原来空闲块的结构更新为新的剩下的空闲块，如果剩下的空闲块大小为0，则直接将这个结构从链表里删除。下图演示了用户请求一块和空闲块2恰好相等的内存空间后堆的状态。

这样的空闲链表尽管容易实现，但在释放空间时，给定一个已分配块的指针，堆无法确定这个块的大小。一个简单的方法就是分配空间时多分配4字节的内存用于存储该分配的大小。这样释放内存时就知道该内存块的大小了。但是，一旦链表被破坏或者记录长度的4字节被破坏，整个链表将无法正常工作。而这些数据恰恰容易被越界读写。

位图的核心思想是将整个堆划分为大量大小相同的块。当用户请求内存时，总是分配整数个块的空间给用户，第一个块我们称之为已分配区域的头，其余的称为已分配区域的主体。而我们可以使用一个整数数组来记录块的使用情况。由于每个块只有头/主体/空闲三种状态，因此仅仅需要两位即可表示一个块，因此称为位图。假设堆的大小为1MB，那么让一个块大小为128字节，那么总共就有1M/128=8k个块，可以用8k/（32/2）=512个int来存储。这有512个int的数组就是一个位图，其中每两位代表一个块。当用户请求300字节的内存时，堆分配给用户3个块，并将相应的位图的相应位置标记为头或躯体。

4.3 堆与栈的区别

1. 管理方式不同
   栈是由编译器自动管理，无需我们手工控制；而堆的释放工作由程序员控制，容易产生内存泄漏。

2. 空间大小不同
   在32位系统下，一般堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的；而栈内存一般都是有一定的空间大小的，例如在VC6.0下面默认的栈空间大小是1M（可修改）。

3. 能否产生碎片不同
   对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低；而栈则不存在这个问题， 因为栈是一种先进后出的容器，所以不可能有一个内存块从栈中间弹出。

4. 生长方向不同
   在类unix系统中，堆的生长方向是向上的，也就是向着内存地址增加的方向；而栈的生长方向是向下的，是向着内存地址减小的方向增长。(在Windows中可能会不同)

5. 分配方式不同
   堆都是动态分配的，没有静态分配的堆；栈除了有编译器静态分配内存外，还可以通过alloca函数进行动态分配，但是栈的动态分配由编译器进行释放，无需程序员手动释放。

6. 分配效率不同
   栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是比较复杂的，例如为了分配一块内存，库函数会按照堆分配算法在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间(可能是由于内存碎片太多)，就可能通过系统调用来增加程序数据段的内存空间，以获得足够大小的内存并返回。显然，堆的效率比栈要低得多。

总结：堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；并且可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，ebp和局部变 量都采用栈的方式存放。所以，推荐大家尽量用栈，而不是用堆。虽然栈有如此众多的好处，但是向堆申请内存更加灵活，有时候分配大量的内存空间，还是用堆好一些。

5. 运行库与系统调用

5.1 入口函数和程序初始化

程序肯定不是从main开始执行的，进入main函数之前，全局变量的初始化已经结束，全局变量如果是某个函数的返回值，那么这个函数也已经被调用过；main函数的两个参数已经被传递进来；堆和栈也已经被初始化；系统I/O也被初始化了，所以可以使用printf函数。atexit（*p（void））；在main函数结束之后调用函数。

main函数之前和之后的代码，称为入口函数或入口点。他们负责准备main函数执行需要的环境并调用main函数，这时，main函数中就可以申请内存、使用系统调用、触发异常、访问I/O等。

操作系统在创建进程后，控制权交给程序的入口函数，这个入口一般是运行库中的函数，入口函数会对程序运行环境初始化，包括堆、I/O、线程、全局变量构造等。入口函数初始化之后调用main函数，直到main函数返回到入口函数，入口函数在进行清理，包括全局变量析构、堆销毁、关闭I/O等，然后系统调用结束进程。

一个典型的程序运行步骤如下：

• 操作系统在创建进程后，将控制权交给了程序的入口，这个入口通常是运行库的某个入口函数
• 入口函数对运行库和程序运行环境进行初始化，包括堆，IO，线程，全局变量的构成
• 入口函数完成初始化后，调用 main 函数，正式执行程序主题
• main函数执行完毕后，返回到入口函数，入口函数进行清理，包括全局变量析构，堆销毁，关闭I/O等，然后进行系统调用结束进程。

5.2 C语言运行库

任何一个C程序，它的背后都有一套庞大的代码来支撑着，使得该程序能够正常运行，这样的一个代码集合叫做运行时库（Runtime Library）。C语言的运行库即为C运行库CRT，它大致包含如下功能：

• 启动与退出：包括入口函数及入口函数所依赖的其他函数等。
• 标准函数：由C语言标准规定的C语言标准库所拥有的函数实现。
• IO：IO功能的封装与实现
• 堆：堆的封装与实现
• 语言实现：语言中的一些特殊功能的是实现。
• 调试：实现调试功能的代码。

运行库是与平台相关的，它与操作系统结合得非常紧密。Linux和Windows平台下的C语言运行库分别为glibc和MSVCRT。

5.3 系统调用

系统调用是应用程序访问系统资源的接口，这些接口往往通过中断来实现，比如Linux使用0x80号作为系统调用的入口，Windows采用0x2E号中断作为系统调用入口。我们可以通过系统调用创建退出进程和线程，对系统资源（文件、网络、进程间通信，硬件设备）进行访问。系统调用往往从一开始定以后就基本不做改变，而仅仅是增加新的调用接口，以保持向后兼容。

系统调用完成了应用程序和内核交流的工作，因此理论上只需要系统调用就可以完成一些程序。但是，系统调用往往使用不便（接口过于原始），且各个操作系统之间的系统调用并不兼容。而运行库作为系统调用和程序之间的一个抽象层具有使用简便，形式统一等特点，能够很大程度上掩盖直接使用系统调用的弊端。

运行时库将不同的操作系统的系统调用包装为统一固定的接口，使得同样的代码在不同的操作系统下都可以直接编译，并产生一致的效果。但是为保持平台兼容，C语言运行库智能取个平台之间功能的交集。一旦程序用到了CRT之外的接口，程序就很难保持各个平台之间的兼容性。

在现代操作系统中存在两个特权级别：用户态和内核态。这样系统就可以让不同的代码运行在不同的模式下，以限制它们的权利，提高系统的稳定性和安全性。系统调用是运行在内核态，而应用程序基本都是运行在用户态的。操作系统一般是通过中断从用户态切换到内核态。下图描述了Linux中应用程序调用系统调用fork的执行过程。