程序是怎样运行的

程序是怎样运行的
2010年10月23日
　　此文写给希望了解c程序是如何运行的人。
　　但是了解一样东西的本来面貌是一个递归的过程，要理解a，就必须先弄懂b，而弄懂b还要知道c……一直要看到最后的东西才能开始向上层返回。所以我十分佩服国内那些编教材的人，居然能够把每个章节写得如此"高内聚，低耦合"。
　　本文从一个最简单c程序（hello）是如何被编译和链接讲起，描述了c程序的运行原理。当中穿插了一些操作系统的知识，虽然c语言本身没有关系，但是对于理解程序的运行很有帮助。
　　笔者尽可能把每个术语的英语写在后面的括号里，遇到缩写也尽量把全称写出来，如果这些名词我都恰好知道的话。因为笔者看书的时候就特别希望作者这么做。
　　一、谁动了我的代码？
　　使用IDE开发程序的人经常会有这样的疑问，代码是怎么从一个文本文件变成可执行程序的呢？代码毕竟不是咒语，一个c程序在被运行之前其实经过了4个步骤，即两次编译，汇编和链接。
　　预编译：这里我们只需要知道有一个叫预处理器（preprocessor也称预编译器）的程序会对c程序进行一些预处理工作。
　　编译：编译的过程中，编译器（compiler）把c语言程序翻译成汇编语言程序，一条c语句通常需要好几条汇编代码来取代，c编译器为了提高程序执行的效率有时候会对程序进行优化，，这就是为什么即使在c程序中声明了register变量，程序也不一定会用。了解编译器这个特性对程序员来说也很重要，比如程序员可以通过指令告诉编译器是生成"易于调试"(debug)还是"代码尽可能小"（release）的版本。
　　汇编：编译得到的汇编语言通过汇编器（assembler）再汇编成可重定位目标程序，与之相反的一个过程被称为反汇编（disassemble）。反汇编也就是所谓的逆向工程给我们带来的实惠很大，比如盗版光盘里的crack文件夹。
　　链接：可重定位目标文件不能被系统直接运行，而且通常情况下.o有很多个，程序中还要包含一些共享目标文件,比如hello程序中的printf函数，它位于静态库中，需要用链接器（linker）进行链接。printf的声明在头文件stdio.h中，如果在安装vc6.0时选择了"安装CRT源码"就可以在VC98\CRT\SRC目录找到printf.c，里面函数完整的定义。事实上很多编译器套装（比如gcc）为了提高编译的效率，已经把这个头文件中牵涉到的所有函数分别编译成单独模块并最后打包成了一个文件（放在系统固定的文件夹中），这个文件就是所谓的静态库，windows中后缀名是.lib，unix是.a，当我们link的时候，只需要在指定库中找到printf对应的那部分二进制代码添加到程序中就行了。从理论上讲hello.c中有几个printf，就会在可执行文件中嵌入几次printf的二进制模块（但如果真是这样，计算机也太傻了），而且当系统内有多个hello同时运行时每个hello都会维护一段属于自己的printf，这样做显然是一种浪费。使用共享库（shared library）可以解决这个问题，共享库也是一个目标模块（后缀名.so），它在程序运行之前会被加载到存储器中某一个特定的区域（linux中，是从地址0x40000000开始的一段区域），并和用到它的程序链接起来，这个过程被称为动态链接，因此共享库在windows中又被称为动态链接库（DLL）。比如hello在链接时其实并没有把printf模块加到可执行程序中，而只是告诉我们的hello一声，待会要用到printf的时候去共享库里找xx就行了。链接是程序再被真正执行前一个极其重要的步骤，但由于IDE给别人造成的错觉，很多程序员居然不知道有这么一步。
　　现在我们可以回答这个问题了，动了我们代码的是预编译器cpp，编译器cc，汇编器as和链接器ld。gcc提供了以上这些工具的一个集合，我们通常把gcc叫做一个编译器，其实是不完整的，编译器只是gcc的一个部分，gcc的全称应该是gnu编译器套装（gnu compiler collection），而不是gnu c compiler（gcc还有java版本）。
　　经过以上几个步骤，hello.c已经变成了可执行程序hello，我们在shell中输入./hello，屏幕上打印出"hello,world"。
　　二、存储器图像
　　我们知道可执行程序在被CPU执行以前存在于内存中，于是我们很快就有了新的疑问，二进制代码在内存中长什么样？内存其实是个模棱两可的叫法，如果说世界上只有两种存储设备，那么说其中一个是内存另一个是外存就不会有争议，但是站在CPU角度看，cache明显要比我们的内存条要内多了，而站在U盘的角度，硬盘也顿时变成了内存。内和外永远是相对的，比较科学的称呼应该是dram（[draem]，动态随机存储器）或者主存储器（main memory）。
　　在了解存储器之前我们先来区分一下进程和程序这两个概念，笔者在维基百科上找到定义是，"进程是程序执行的一个实例（instance）"。这种说法解释了为什么同一个程序在内存中能有很多个进程。有些书上写，进程是程序执行的一个过程，也没有错，但问题是说了等于没说，进程本来和过程就是同一个东西（process），我们怎么能用馒头去解释馍馍呢？
　　因此hello程序的和hello进程是两个东西，前者是留在磁盘中的一些磁信号，而后者是系统各种资源（cpu、存储器、IO设备……）共同作用的结果。如果我们要彻底理解hello是怎么运行的，首先就必须hello在内存中的布局有一个比较理性的认识。下面来看一个程序在linux上运行时存储器某一时刻的图像。
　　
　　"一个linux进程的虚拟存储器"与"linix是如何组织虚拟存储器的"（CSAPP：p620，p621，我把两张图合成了一张）
　　可能有人要问了，图中存储器的地址空间为什么有4G？（0到0xffffffff），如果计算机的只有1G主存，那岂不是溢出了？事实上现代操作系统采取了一种叫虚拟存储器（virtual memory）的机制来有效地管理存储器，即把系统的存储设备全部隐藏在背后，无论实际的物理存储器（dram）有多大都提供给我们一个固定虚拟的线性空间（IA32就是4G），系统在幕后对实际的地址进行映射（可能在dram中，也可能在磁盘上），而我们就感觉自己在使用一台存储器很大的计算机，尽管当实际的dram很小时我们还是感觉很慢，于此同时硬盘灯在不停闪烁。
　　从图中可以发现linux将虚拟存储器高端的1/4留给内核，剩下3/4全留给用户进程。0到0x08048000这段空间是浪费的，如果我们用objdump反汇编hello可执行文件会发现程序的文本段并不是从0x08048000开始的，而差了几十字节，等会我们可以看到，这些字节留给了一个叫elf header的东西。更有趣的是为什么是0x08048000这个特定的数字?
　　下面来看虚拟存储器的几个重要组成部分。
　　1.进程控制块（process control block）
　　PCB在linux中就是一个叫task_struct的结构体，结构体中的元素包含了进程所需要的所有信息，主要有pid（process identification）、指向用户栈的指针、可执行目标文件的名字（hello）以及程序计数器PC（program counter）。task的mm字段指向了结构体mm_struct，它描述了当前虚拟存储器的状态，其中mmap（memory mapping，存储器映射）字段指向一个链表结构，这个链表的每个节点（vm_area_struct）分别描述了当前虚拟存储的一个区域（如文本段、数据段、共享库），它的start和end域指向了这些区域的起始地址和终止地址，这些区域合在一起描述了整个进程占用存储器的情况。PCB中保存了进程hello的运行时的存储器图像和寄存器信息，使得一个进程重新上台的时候能够恢复现场。
　　2.栈和堆
　　我们在学习c语言的时候就知道局部变量是分配在栈（stack）上的，但是这种知道不是真的知道，因为分配局部变量向来都是编译器的工作。
　　理解栈的工作原理对于我们了解程序的运行很有好处。理解栈，须理解栈帧这种结构。笔者画了一张图，来反映程序a在调用程序b时，栈指针%esp和帧指针%ebp是如何相互配合来管理（用户）栈的。
　　
　　①某一时刻程序a栈帧的快照
　　②程序a在调用b之前，先压入过程参数
　　③程序a调用了程序b（通过call指令），返回地址入栈，指令计数器PC指向了b的代码，这说明以下的操作都需要由子程序b来完成
　　④通过将%ebp的值入栈，把a的现场保护起来。%ebp指向栈顶，当前栈帧（红色区域）从a变成了b。
　　⑤此时再将程序b要用到的寄存器也保存在栈中
　　⑥此后程序b可以通过%ebp+8来引用过程参数的值
　　整个过程中，%esp的指向一直在发生变化，而%ebp只有在调用（或返回）时才改变。%esp始终指向栈顶，%ebp始终指向当前程序帧的底部，因此可以用%ebp的值加减一个数（表示字节的个数）来定位局部变量，因此它又被成为基址寄存器，intel汇编就是这么叫的。
　　相反堆（heap）需要程序员自己手动分配（malloc）和释放（free），如果程序员忘了释放，则有垃圾收集器gc代劳。
　　简单比较一下堆和栈这两种数据结构。栈有一个最大好处就是根本不用考虑回收问题，当程序调用的层数变得很深，变量的生命周期始终满足FBLD（first born last died），程序一旦返回，退栈以后自然就把生命周期结束了的变量"释放"了。从图中可以看出堆和栈的生长方向是相反的。另外如果我们说堆栈，通常指的是栈。
　　3.文本段和数据段
　　文本段主要包括正文段（.text）和初始化段（.init）。
　　数据段包括只读数据段(.rodata)、读写数据段（.data）和未初始化数据段（.bss）。因为我们已经知道局部变量是分配在栈上的，所以.data和.bss其实就对应了已初始化和未初始化的全局c变量（包括static）。而.rodata中保存了只读数据，可能有人要问了，c语言中有不能修改的数据吗？当然有了，比如我们这个程序中的"hello,world"字符串在程序运行的过程中就是只读的。hello虽小，五脏俱全。
　　数据段和文本段都是从可执行文件加载的到存储器中的。
　　4.共享库的映射区域
　　操作系统通过将共享的对象映射到虚拟存储器的"共享区域"来使得代码能够共享，一方面提高存储器的利用率，一方面可以使得进程能够共享一些数据。正如笔者之前所说，如果某一时刻系统中有20个程序正在运行，而这些程序都需要在屏幕上打印东西，系统就没有必要为每个程序都维护一段printf的代码，只要分别从各自的.bss中取出字符串然后用同一个printf完成输出就行了。同样的道理，当有多个hello在系统中运行时，它们也完全可以共享同一个文本段。这也就是为什么会把进程定义为程序的一个实例的原因。不妨回想一下面向对象中对象的概念，我们在写class的时候定义成员字段不就是在分配数据？而定义方法字段不就是在操作这些数据？在对象被实例化以前，这些定义只不过是一些白纸黑字，而只有经过实例化，实例们才在存储器中有了自己的映像。而多个实例之间可以共享"方法"（文本）但是独有"成员"（数据）的特点，也和进程如出一辙。
　　现在我们可以大致勾勒出hello在存储器中图像了。hello的代码位于文本段中，字符串"hello，world"在只读段中，printf位于共享库的映射区域，程序在执行时用到了用户栈，用户栈从0xbfffffff开始，向下生长。以上的图景只发生在一瞬间，我们难以追踪，要想看清hello的本来模样，还是得从目标文件上寻址痕迹。
　　三、目标文件的格式
　　可重定位目标文件（hello.o）
　　这是书上典型的一个elf格式的可重定位目标文件：
　　--------------------0
　　ELF Header
　　--------------------
　　.text
　　--------------------
　　.rodata
　　---------------------
　　.data
　　---------------------
　　.bss
　　---------------------
　　.symtab         
　　---------------------
　　.rel.text       
　　--------------------- .rel.data       --------------------- .debug           --------------------- .line            --------------------- .strtab          --------------------- Section Headers --------------------- 下面我们直接来看hello.o。因为我们关心的是elf文件的组织而非汇编代码，用readelf比objdump更合适。
　　readelf -a hello.o
　　ELF Header:                                                                             //elf头
　　Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00   //前四位是elf魔数：45，4c，46 = E，L，F，第一个1表示32位机
　　Class:                             ELF32
　　Data:                              2's complement, little endian          //二进制补码，小端法表示
　　Version:                           1 (current)
　　OS/ABI:                            UNIX - System V
　　ABI Version:                       0
　　Type:                              REL (Relocatable file)                      //目标文件的类型，hello.o是可重定位的
　　Machine:                           Intel 80386
　　Version:                           0x1
　　Entry point address:               0x0
　　Start of program headers:          0 (bytes into file)
　　Start of section headers:          216 (bytes into file)                  
　　Flags:                             0x0
　　Size of this header:               52 (bytes)                                 //elf header的大小
　　Size of program headers:           0 (bytes)                              //没有程序头
　　Number of program headers:         0
　　Size of section headers:           40 (bytes)                             //Section Headers的大小
　　Number of section headers:         11                                     //即下面那张二维表的行数
　　Section header string table index: 8
　　Section Headers:                                                                 //节头目表，描述了各个节的信息并提供了入口（entry）
　　[Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al                //Aln表示2**n位对齐,n=4即1字节
　　[ 0]                   NULL            00000000 000000 000000 00      0   0  0     
　　[ 1] .text             PROGBITS        00000000 000034 000017 00  AX  0   0  4     
　　[ 2] .rel.text         REL             00000000 000344 000010 08      9   1  4         
　　[ 3] .data             PROGBITS        00000000 00004c 000000 00  WA  0   0  4
　　[ 4] .bss              NOBITS          00000000 00004c 000000 00  WA  0   0  4       
　　[ 5] .rodata           PROGBITS        00000000 00004c 00000c 00   A  0   0  1         //ro即read-only，没有"写"权力
　　[ 6] .comment          PROGBITS        00000000 000058 00002e 01  MS  0   0  1    
　　[ 7] .note.GNU-stack   PROGBITS        00000000 000086 000000 00      0   0  1
　　[ 8] .shstrtab         STRTAB          00000000 000086 000051 00      0   0  1
　　[ 9] .symtab           SYMTAB          00000000 000290 0000a0 10     10   8  4         //符号表
　　[10] .strtab           STRTAB          00000000 000330 000013 00      0   0  1
　　Key to Flags:                                                                   
　　W (write), A (alloc), X (execute), M (merge), S (strings)
　　I (info), L (link order), G (group), 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 '.rel.text' at offset 0x344 contains 2 entries:         //重定位目表
　　Offset     Info    Type            Sym.Value  Sym. Name                   
　　0000000c  00000501 R_386_32          00000000   .rodata                  //R_386_32表示绝对地址的引用
　　00000011  00000902 R_386_PC32        00000000   puts                     //R_386_PC32表示相对地址的跳转
　　There are no unwind sections in this file.
　　Symbol table '.symtab' contains 10 entries:                                    //符号表
　　Num:    Value  Size Type    Bind   Vis      Ndx Name
　　0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND            
　　1: 00000000     0 FILE    LOCAL  DEFAULT  ABS hello.c               //ABS表示不该被重定位的符号
　　2: 00000000     0 SECTION LOCAL  DEFAULT    1 
　　3: 00000000     0 SECTION LOCAL  DEFAULT    3 
　　4: 00000000     0 SECTION LOCAL  DEFAULT    4 
　　5: 00000000     0 SECTION LOCAL  DEFAULT    5 
　　6: 00000000     0 SECTION LOCAL  DEFAULT    7 
　　7: 00000000     0 SECTION LOCAL  DEFAULT    6 
　　8: 00000000    23 FUNC    GLOBAL DEFAULT    1 main
　　9: 00000000     0 NOTYPE  GLOBAL DEFAULT  UND puts                //UND表示所引用puts的定义不在该文件中
　　可执行目标文件（a.out）
　　可重定位目标文件（hello.o）离最终的可执行目标文件(a.out)只有一步之遥，这关键的一步就是链接。链接分为两步，第一步是解析符号，符号解析主要用来解决多个模块之间全局字段的协调问题，比如我们在两个.c的文件中都定义了全局变量x，或者引用了不曾定义过的函数foo()，链接器都会报错（link error）。第二步就是重定位，重定位将每个目标模块的节最终合并成一个大的节，并且根据rel.text来修改调用外部函数（printf）或者引用任何全局变量（"hello,world"）的指令。hello.o和a.out最大的区别在于，a.out的节头目表为每个节都分配了真实地址，而hello.o中的节头目表只在重定位时为链接器提供了一个快速定位节的方式。 下面是一个典型可执行目标文件（但实际上要复杂得多）
　　--------------------0
　　ELF Header
　　--------------------
　　.init
　　--------------------
　　.text
　　--------------------
　　.rodata
　　--------------------
　　.data
　　--------------------
　　.bss
　　--------------------
　　.symtab         
　　--------------------
　　.debug          
　　--------------------
　　.line           
　　--------------------
　　.strtab         
　　---------------------
　　Section Headers
　　---------------------
　　笔者在学习c的时候就听到过这么一句话--"main是程序的入口"，真的是这样吗？
　　尝试一下这条命令
　　ld hello.o -lc
　　ld: warning: cannot find entry symbol _start; defaulting to 080481a4
　　这说明编译器在_main之前会先去找一个_start符号。事实上程序在运行的初期还需要做一些初始化和清理的工作，这些代码位于crt1.o模块中，即c运行时（runtime）库，它包含了程序的入口函数_start，由它负责调用__libc_start_main初始化libc，并且调用main函数进入真正的程序主体，这部分代码必须在链接时加进来（对我们来说是透明的），否则程序根本运行不到的main。
　　当我们在shell中输入a.out的时候，shell先通过调用fork函数复制出一个子进程，然后用execve先删掉这个进程的用户区域（和shell长得一模一样），再将a.out和标准c库加载到存储器中，最后把PC指向hello的第一条语句，于是cpu就开始逐条执行指令。
　　最后说一下printf，printf的机器码位于/lib/libc.so.6的共享库中，它将在程序运行时被加载到存储器的共享库映射区域。printf中有一个系统调用（system call）来向中断输出格式串，它的原理就是将系统调用的编号放到%eax中，然后以指令的形式向系统发出一个中断信号，这种形式的中断有时被称为陷阱（trap），它通常发生在用户程序向系统请求服务的时候，而这部分的代码因为要和底层硬件打交道所以很难写，需要操作系统提供一个事先封装好的接口（这也是操作系统的意义所在）。用户程序平时运行在用户态（user mode），程序只能直接引用属于自己的代码和数据，任何试图修改内核区域或者其他程序的代码的行为都是非法的。只有通过调用这些接口才能进入内核模式（kernel mode）。于是从壳外陷入核内的中断方式，就被形象地称作陷阱。
　　另外一种中断是由中断管脚的电压变化所产生，比如当一个IO设备完成操作以后需要向cpu报告，于是就升高电压来提醒cpu，"让我的进程重新上台吧"，因此把这种通过硬件实现的中断称为"硬中断"，与"软中断"（即陷阱）相对应。
　　中断意味着cpu手头的事情还没干完，就去干另外一件事情了，但是cpu这样做是它自己的原因的，比如cpu在和IO下棋的时候，IO每走一步，cpu可以走好几十步。这样cpu就没有必要在io还在想的时候干等他，完全可以先出去踢会儿球再回来接着下，他所要做的就是记住当前棋局（保存现场）然后让IO下完这一步之后打电话给他（管脚电压变高，产生中断）。在这种情况下，cpu两不耽误，即能踢球又能够下棋，实现了进程的并发。
　　除此以外，异常（exception）也是中断的一种形式，比如说一条指令出了问题，比如除0，那么cpu就会中断然后转去寻找解决异常的方法的代码，所以说cpu其实是很呆板的，真正的军师是设计系统的人，cpu所需要做的就是跑到一个地方，先想办法自己解决，如果不能解决就打开锦囊（一张向量表），然后依计行事，接着跑向下一个地点……