CSAPP大作业 hello的一生

摘 要

本文在linux操作系统下对C语言程序hello.c的运行全过程进行了分析。分析了从c文件转化为可执行文件过程中的预处理、编译、汇编和链接阶段，和可执行文件执行过程中的进程管理、存储空间管理和I/O管理的原理。

第1章 概述

1.1 Hello简介

Hello的P2P，020的整个过程：

程序员通过编辑器创建hello.c。预处理器根据以字符#开始的命令修改hello.c得到另一个C程序hello.i。编译器将hello.i翻译成文本文件hello.s，它包含一个汇编语言程序。汇编器将hello.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件hello.o中。再经过链接器的处理，就得到了可执行目标文件hello。

用户键入命令，shell会fork一个子进程，并在这个子进程中调用execve加载hello。然后程序会跳转到_start地址，最终调用hello的main函数。hello通过调用sleep getchar exit等系统函数运行程序，程序结束后会被shell回收。

1.2 环境与工具

硬件环境：Intel® Core™ i7-7700HQ CPU; 8.00GB RAM

软件环境：Windows 10 64位；Vmware Workstation 14 Pro；Ubuntu 16.04 LTS 64位

开发工具：CodeBlocks 64位；Visual Studio Code；GCC 5.4.0；objdump；EDB；readelf；

1.3 中间结果

文件	作用
hello.i	hello.c预处理之后的文本文件
hello.s	hello.i编译之后的文本文件
hello.o	hello.s汇编之后的二进制文件
hello	hello.o链接之后的二进制文件
hello.asm	hello的反汇编文件
helloo.asm	hello.o的反汇编文件
hello.elf	hello的elf文件信息
helloo.elf	hello.o的elf文件信息

1.4 本章小结

本章简要介绍了Hello的P2P，020的整个过程以及实验的环境、工具和中间产物。

第2章 预处理

2.1 预处理的概念与作用

预处理一般是指由预处理器对程序源代码文本进行处理的过程。预处理器(cpp)根据以字符#开头的命令,修改原始的C程序。结果是得到另一个C程序,通常是以.i作为文件扩展名。

作用：

C语言的预处理主要有三个方面的内容：宏定义、文件包含和条件编译。

1.宏定义：将宏名替换为文本（字符串或代码）。

2.文件包含：预处理程序将查找指定的被包含文件，并将其复制插入到#include命令出现的位置上。比如hello.c中第1行的#include命令告诉预处理器读取系统头文件stdio.h的内容,并把它直接插人程序文本中。

3.条件编译：有些语句希望在条件满足时才编译，预处理过程中根据条件决定需要编译的代码。

2.2在Ubuntu下预处理的命令

命令：cpp hello.c > hello.i

2.3 Hello的预处理结果解析

可以看出，预处理后的文件是一个3118行的c语言文件，其中3098行后的内容对应hello.c中第10行之后的内容。之前的内容是头文件stdio.h unistd.h stdlib.h被复制并插入到#include命令出现的位置上产生的。被包含文件还可能包含其他文件，因此该过程可能是嵌套进行的。

2.4 本章小结

本章阐述了预处理的概念，作用和命令，并对hello.c的预处理结果进行了解析。

第3章 编译

3.1 编译的概念与作用

编译是编译器(ccl)将文本文件hello.i翻译成文本文件hello.s的过程, hello.s包含一个汇编语言程序。

过程：1.词法分析 2.语法分析 3.语义分析 4.源代码优化 5.代码生成，目标代码优化。

作用：把代码翻译成汇编语言。

注意：这儿的编译是指从 .i 到 .s 即预处理后的文件到生成汇编语言程序

3.2 在Ubuntu下编译的命令

命令：gcc -S hello.i -o hello.s

3.3 Hello的编译结果解析

3.3.1数据

1.int sleepsecs：

sleepsecs是一个全局变量，存在.data段中。由于sleepsecs为int类型，赋值时发生了类型的强制转换。

2.int i：

i是一个局部变量。局部变量一般存在寄存器或堆栈中。由i的赋值语句可以看出i存放的位置是-4(%rbp)

3.字符串：

程序中有两个字符串：“Usage: Hello 学号 姓名！\n"和"Hello %s %s\n”

都存在只读数据段中。

4.数组：

程序中有一个数组argv[]，argv[[1]]和argv[[2]]作为for循环中printf的参数。

由取argv[[1]]和argv[[2]]值的汇编语句可知argv的首地址是-32(%rbp)。

取argv[[2]]的汇编语句：

5.其他数据以立即数的形式出现。

3.3.2 赋值

1.int sleepsecs=2.5：

sleepsecs是全局变量，在.data节中被赋值。

2.i=0：

MOV类的数据传送指令：

3.3.3 类型转换

将float类型的2.5赋值给int类型的sleepsecs时发生了强制类型转换。2.5被向下取整为2.

3.3.4 算术操作

常用的整数算术操作：

程序中出现的算术操作是for循环中的i++，被编译为：

3.3.5 关系操作

比较和测试指令：

程序中出现的比较指令：

argc!=3被编译为：

for循环中的i<10被编译为：

3.3.6 数组/指针/结构操作

循环体中取数组元素值的操作被编译成：

程序中对argv[[1]],argv[[2]]的寻址被编译为基址+偏移的寻址方式。

-32(%rbp)存放的是argv的首地址，在首地址上+8，+16得到argv[[1]],argv[[2]]的地址。

3.3.7 控制转移

跳转指令：

程序中的控制转移通过比较+跳转实现：

1.if(argc!=3)：

如果argc == 3，执行接下来的语句，否则跳转到L2处

2.for(i=0;i<10;i++)：

如果i <= 9，跳转到L4处执行循环体内的语句。

3.3.8 函数操作

函数调用大概包括以下几个步骤（32位）：

(1)参数入栈：将参数从右向左依次压入系统栈中。

(2)返回地址入栈：将当前代码区调用指令的下一条指令地址压入栈中，供函数返回时继续执行。

(3)代码区跳转：处理器从当前代码区跳转到被调用函数的入口处。

(4)栈帧调整：具体包括：

　　<1>保存当前栈帧状态值，已备后面恢复本栈帧时使用(EBP入栈)。

　　 <2>将当前栈帧切换到新栈帧(将ESP值装入EBP，更新栈帧底部)。

　　<3>给新栈帧分配空间(把ESP减去所需空间的大小，抬高栈顶)。

函数返回的步骤如下：

(1)保存返回值，通常将函数的返回值保存在寄存器EAX中。

(2)弹出当前帧，恢复上一个栈帧。具体包括：

　　<1>在堆栈平衡的基础上，给ESP加上栈帧的大小，降低栈顶，回收当前栈帧的空间。

　　<2>将当前栈帧底部保存的前栈帧EBP值弹入EBP寄存器，恢复出上一个栈帧。

　　<3>将函数返回地址弹给EIP寄存器。

(3)跳转：按照函数返回地址跳回母函数中继续执行。

程序中的函数调用主要有如下几个：

1.main函数

被系统启动函数__libc_start_main调用

2.printf函数

printf(“Usage: Hello 学号 姓名！\n”)：

printf(“Hello %s %s\n”,argv[1],argv[2])：

3.exit函数

exit(1)：

4.sleep函数

Sleep(sleepsecs)：

5.getchar函数

getchar()：

3.4 本章小结

本章阐述了编译的概念，作用和命令。并结合hello.i的编译结果，就C语言中的数据与操作如何被翻译成汇编语言进行了总结和分析。

第4章 汇编

4.1 汇编的概念与作用

汇编器(as)将hello.s翻译成机器语言指令,把这些指令打包成一种叫做可重定位目标程序(relocatable object program)的格式,并将结果保存在目标文件hello.o中。

作用：将汇编代码转变为机器指令，生成目标文件。

注意：这儿的汇编是指从 .s 到 .o 即编译后的文件到生成机器语言二进制程序的过程。

4.2 在Ubuntu下汇编的命令

命令：gcc -c hello.s -o hello.o

4.3 可重定位目标elf格式

1.ELF头：

ELF头以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息，其中包括ELF头的大小、目标文件的类型、机器类型、节头部表的文件偏移，节头部表中条目的大小和数量等。

2.节头表

记录了每个节的名称、类型、属性（读写权限）、在ELF文件中所占的长度、对齐方式和偏移量

3.重定位节

重定位条目告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。如图，偏移量是需要被修改的引用的节偏移，符号标识被修改引用应该指向的符号。类型告知链接器如何修改新的引用，加数是一个有符号常数，一些类型的重定位要用它对被修改引用的值做偏移调整。

ELF重定位条目：

r_offset:

此成员指定应用重定位操作的位置。不同的目标文件对于此成员的解释会稍有不同。

r_info:

此成员指定必须对其进行重定位的符号表索引以及要应用的重定位类型。

重定位类型特定于处理器。重定位项的重定位类型或符号表索引是将 ELF32_R_TYPE 或 ELF32_R_SYM 分别应用于项的r_info成员所得的结果。

r_addend:

此成员指定常量加数，用于计算将存储在可重定位字段中的值。

重定位类型：

R_X86_64_PC3：重定位一个使用32位PC相对地址的引用。在指令中编码的32位值加上PC的当前运行时值，得到有效地址。

R_X86_64_32：重定位一个使用32位PC绝对地址的引用。直接使用在指令中编码的32位值作为有效地址。

4.符号表

它存放在程序中定义和引用的函数和全局变量的信息,.symtab符号表不包含局部变量的条目。

4.4 Hello.o的结果解析

1.反汇编代码与hello.s差别不大。

2. hello.s使用十进制，反汇编代码中使用的是16进制。

3.分支转移：hello.s中使用段的标号（如：.L3）作为分支后跳转的地址，反汇编代码中用相对main函数起始地址的偏移表示跳转的地址。

4.函数调用：hello.s中函数调用后直接跟着函数的名字，反汇编代码中函数调用的目标地址是当前的下一条指令。在机器语言中call后的地址为全0.在重定位节中有对应的重定位条目，链接之后确定地址。

5.全局变量：hello.s中使用段名称+%rip访问，反汇编代码中使用0+%rip访问。机器语言中待访问的全局变量地址为全0.在重定位节中有对应的重定位条目，链接之后确定地址。

4.5 本章小结

这章介绍了汇编的概念、作用和命令。分析了可重定位目标文件的格式，比较了反汇编代码与hello.s的相同点与不同点。

第5章 链接

5.1 链接的概念与作用

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程。

作用：将函数库中相应的代码组合到目标文件中。

注意：这儿的链接是指从 hello.o 到hello生成过程。

5.2 在Ubuntu下链接的命令

命令：ld -dynamic-linker /lib64/ld-linux-x86-64.so.2 /usr/lib/x86_64-linux-gnu/crt1.o /usr/lib/x86_64-linux-gnu/crti.o /usr/lib/gcc/x86_64-linux-gnu/7/crtbegin.o /usr/lib/gcc/x86_64-linux-gnu/7/crtend.o /usr/lib/x86_64-linux-gnu/crtn.o hello.o -lc -z relro -o hello

5.3 可执行目标文件hello的格式

1.节头表：

.text节是保存了程序代码指令的代码节。一段可执行程序，存在Phdr，.text就会存在于text段中。由于.text节保存了程序代码，因此节的类型为SHT_PROGBITS。

.rodata 保存只读数据。类型SHT_PROGBITS。

.plt 过程链接表（Procedure Linkage Table），包含动态链接器调用从共享库导入的函数所必须的相关代码。存在于text段中，类型SHT_PROGBITS。

.bss节保存未初始化全局数据，是data的一部分。程序加载时数据被初始化成0，在程序执行期间可以赋值，未保存实际数据，类型SHT_NOBITS。

.got节保存全局偏移表。它和.plt节一起提供了对导入的共享库函数访问的入口。由动态链接器在运行时进行修改。如果攻击者获得堆或者.bss漏洞的一个指针大小写原语，就可以对该节任意修改。类型SHT_PROGBITS。

.dynsym节保存共享库导入的动态符号信息，该节在text段中，类型SHT_DYNSYM。

.dynstr保存动态符号字符串表，存放一系列字符串，代表了符号的名称，以空字符作为终止符。

.rel节保存重定位信息，类型SHT_REL。

.hash节，也称为.gnu.hash,保存一个查找符号散列表。

.symtab节，保存了ElfN_Sym类型的符号信息，类型SHT_SYMTAB。

strtab节，保存符号字符串表，表中内容被.symtab的ElfN_Sym结构中的st_name条目引用。类型SHT_SYMTAB。

.shstrtab节，保存节头字符串表，以空字符终止的字符串集合，保存了每个节节名，如.text，.data等。有个e_shsrndx的ELF文件头条目会指向.shstrtab节，e_shstrndx中保存了.shstrtab的偏移量。这节的类型是SHT_SYMTAB。

.ctors和.dtors节，前者构造器，后者析构器，指向构造函数和析构函数的函数指针，构造函数是在main函数执行前需要执行的代码，析构是main函数之后需要执行的代码。

2.程序头表：

可以看出，程序包含八个段。

1.PTDR: 指定程序头表在文件及程序内存映像中的位置和大小。

2.INTERP: 指定要作为解释程序调用的以空字符结尾的路径名的位置和大小。对于动态可执行文件，必须设置此类型。

3.LOAD: 指定可装入段，通过p_filesz和p_memsz进行描述。文件中的字节会映射到内存段的起始位置。

4.DYNAMIC: 指定动态链接信息。

5.NOTE: 指定辅助信息的位置和大小。

6.GNU_STACK: 权限标志，标志栈是否是可执行的。

7.GNU_RELRO: 指定在重定位结束之后那些内存区域是需要设置只读。

5.4 hello的虚拟地址空间

1.连接后的hello属于elf可执行目标文件，所包含的各类信息如下：

2.虚拟地址空间各段信息：

（1）.PDHR:起始位置为0x400040,大小为0x1c0

（2）.INTERP:起始位置为0x400200,大小为0x1c

（3）.LOAD：起始位置为0x400000，大小为0x81c

（4）.LOAD：起始位置为0x600e00,大小为0x258

同理可以找到其他段的位置和内容。

5.5 链接的重定位过程分析

1.hello中增加了许多节和被调用的函数。

2.对rodata的引用：在hello.o的反汇编文件中对printf参数字符串的引用使用全0替代。在hello中则使用确定地址，这是因为链接后全局变量的地址能够确定。

3.hello.o中main 的地址从0开始，hello中main的地址不再是0.库函数的代码都链接到了程序中。

5.6 hello的执行流程

使用edb执行hello，说明从加载hello到_start，到call main,以及程序终止的所有过程。请列出其调用与跳转的各个子程序名或程序地址。

程序名称	程序地址
ld-2.27.so!_dl_start	0x7f5d6118fea0
ld-2.27.so!_dl_init	0x7f5d6119e630
hello!_start	0x400500
[email protected]	0x4004b0
[email protected]	0x4004e0

5.7 Hello的动态链接分析

程序调用一个由共享库定义的函数时，编译器没有办法预测这个函数的运行时地址，因为定义它的共享模块在运行时可以加载到任意位置。GNU编译系统使用延迟绑定的技术解决这个问题，将过程地址的延迟绑定推迟到第一次调用该过程时。

延迟绑定要用到全局偏移量表（GOT）和过程链接表（PLT）两个数据结构。如果一个目标模块调用定义在共享库中的任何函数，那么它就有自己的GOT和PLT。

PLT：PLT是一个数组，其中每个条目是16字节代码。PLT[0]是一个特殊条目，跳转到动态链接器中。每个条目都负责调用一个具体的函数。PLT[[1]]调用系统启动函数 （__libc_start_main）。从PLT[[2]]开始的条目调用用户代码调用的函数。

GOT：GOT是一个数组，其中每个条目是8字节地址。和PLT联合使用时，GOT[0]和GOT[[1]]包含动态链接器在解析函数地址时会使用的信息。GOT[[2]]是动态链接器在ld-linux.so模块中的入口点。其余的每个条目对应于一个被调用的函数，其地址需要在运行时被解析。

分析：

在节头表中找到GOT的起始位置为601000

调用_dl_start之前可以看出有16个为0的字节：

调用_dl_start之后发现这些值发生了变化

GOT[[2]]是动态链接器在ld-linux.so模块中的入口点，共享库模块：

注意第一次调用puts之前的跳转地址：

调用一次puts之后的跳转地址：

可以说明调用后printf链接到了动态库。

5.8 本章小结

本章介绍了链接的概念和作用，分析了hello的格式、虚拟地址空间、重定位过程、执行流程和动态链接分析。

第6章 hello进程管理

6.1 进程的概念与作用

进程是一个执行中程序的实例。是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

作用：进程的概念为我们提供这样一种假象，就好像我们的程序是系统中当前运行的唯一程序一样，我们的程序好像是独占地使用处理器和内存，处理器好像是无间断地一条接一条地执行我们程序中的指令，我们程序中的代码和数据好像是系统内存中唯一的对象。

6.2 简述壳Shell-bash的作用与处理流程

Shell俗称壳，是指“为使用者提供操作界面”的软件（命令解析器）。它接收用户命令，然后调用相应的应用程序。

1.功能：命令解释。Linux系统中的所有可执行文件都可以作为Shell命令来执行。

2.处理流程：

1）当用户提交了一个命令后，Shell首先判断它是否为内置命令，如果是就通过Shell内部的解释器将其解释为系统功能调用并转交给内核执行。

2）若是外部命令或应用程序就试图在硬盘中查找该命令并将其调入内存，再将其解释为系统功能调用并转交给内核执行。

6.3 Hello的fork进程创建过程

在终端中输入./hello 学号 姓名，shell判断它不是内置命令，于是会加载并运行当前目录下的可执行文件hello.此时shell通过fork创建一个新的子进程。新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份副本，包括代码和数据段、堆、共享库和用户栈。子进程还获得与父进程任何打开文件描述符相同的副本，这就意味着当父进程调用fork时，子进程可以读写父进程中打开的任何文件。子进程与父进程有不同的pid。fork被调用一次，返回两次。在父进程中fork返回子进程的pid，在子进程中fork返回0.父进程与子进程是并发运行的独立进程。

6.4 Hello的execve过程

execve函数在新创建的子进程的上下文中加载并运行hello程序。execve函数加载并运行可执行目标文件filename，且带参数列表argv和环境变量列表envp。只有发生错误时execve才会返回到调用程序。所以，execve调用一次且从不返回。

加载并运行hello需要以下几个步骤：

1.删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。

2.映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区被映射为hello文件中的.text和.data区。bss区域是请求二进制零的，映射到匿名文件，其大小包含在hello中。栈和堆区域也是请求二进制零的，初始长度为零。

3.映射共享区域。如果hello程序与共享对象链接，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。

4.设置程序计数器。设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。下一次调度这个进程时，它将从这个入口点开始执行。

6.5 Hello的进程执行

系统中的每个程序都运行在某个进程的上下文中。上下文是由程序正确运行所需的状态组成的。这个状态包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。

一个进程执行它的控制流的一部分的每一时间段叫做时间片。

处理器通常用某个控制寄存器的一个模式位来提供用户模式和内核模式的功能。设置了模式位时，进程就运行在内核模式中，该进程可以执行指令集中的任何指令，可以访问系统中的任何内存位置。没有设置模式位时，进程就运行在用户模式中，用户模式中的进程不允许执行特权指令。

在进程执行的某些时刻，内核可以决定抢占当前进程，并重新开始一个先前被抢占了的进程的决定叫做调度。

程序在执行sleep函数时，sleep系统调用显式地请求让调用进程休眠，调度器抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。sleep的倒计时结束后，控制会回到hello进程中。程序调用getchar()时，内核可以执行上下文切换，将控制转移到其他进程。getchar()的数据传输结束之后，引发一个中断信号，控制回到hello进程中。

调用sleep:

调用getchar:

6.6 hello的异常与信号处理

异常的类别：

信号：

信号的处理：当内核把进程p从内核模式切换到用户模式时，它会检查进程p的未被阻塞的待处理信号的集合。如果集合非空，内核强制p接收信号k。收到这个信号会触发进程采取某种行为，一旦完成行为，控制就传递回p的逻辑控制流中的下一条指令，每个信号类型都有一种默认行为，也可以通过设置signal函数改变和信号signum相关联的行为。

1.正常退出：

程序结束后，进程被回收。

2.随便乱按：

乱按会将输入的内容存到缓冲区，作为接下来的命令行输入。

3.Ctrl+c:

Ctrl+c会使内核发送一个SIGINT信号。信号处理程序会回收子进程。

4.Ctrl+z:

6.7本章小结

本章阐述了进程的定义和作用，shell的作用和处理流程，执行hello时的fork和execve过程。分析了hello的进程执行和异常与信号处理过程。

第7章 hello的存储管理

7.1 hello的存储器地址空间

逻辑地址：在有地址变换功能的计算机中，访内指令给出的地址 (操作数) 叫逻辑地址，也叫相对地址。要经过寻址方式的计算或变换才得到内存储器中的实际有效地址，即物理地址。是hello.o中的相对偏移地址。

线性地址：线性地址（Linear Address）是逻辑地址到物理地址变换之间的中间层。在分段部件中逻辑地址是段中的偏移地址，然后加上基地址就是线性地址。

虚拟地址：程序访问存储器所使用的逻辑地址称为虚拟地址。是hello里的虚拟内存地址。

物理地址：在存储器里以字节为单位存储信息，为正确地存放或取得信息，每一个字节单元给以一个唯一的存储器地址，称为物理地址。是hello里虚拟内存地址对应的物理地址。

7.2 Intel逻辑地址到线性地址的变换-段式管理

1.基本原理：

在段式存储管理中，将程序的地址空间划分为若干个段(segment)，这样每个进程有一个二维的地址空间。在段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在内存的不同分区中。程序加载时，操作系统为所有段分配其所需内存，这些段不必连续，物理内存的管理采用动态分区的管理方法。

在为某个段分配物理内存时，可以采用首先适配法、下次适配法、最佳适配法等方法。

在回收某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。

段式存储管理也需要硬件支持，实现逻辑地址到物理地址的映射。

程序通过分段划分为多个模块，如代码段、数据段、共享段：

–可以分别编写和编译

–可以针对不同类型的段采取不同的保护

–可以按段为单位来进行共享，包括通过动态链接进行代码共享

这样做的优点是：可以分别编写和编译源程序的一个文件，并且可以针对不同类型的段采取不同的保护，也可以按段为单位来进行共享。

总的来说，段式存储管理的优点是：没有内碎片，外碎片可以通过内存紧缩来消除；便于实现内存共享。缺点与页式存储管理的缺点相同，进程必须全部装入内存。

2.段式管理的数据结构：

为了实现段式管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理地分配内存空间。

·进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(baseaddress)，即段内地址。

在系统中为每个进程建立一张段映射表，如图：

·系统段表：系统所有占用段（已经分配的段）。

·空闲段表：内存中所有空闲段，可以结合到系统段表中。

3.段式管理的地址变换

在段式 管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。为了完成进程逻辑地址到物理地址的映射，处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，得到实际的物理地址。这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器的特定寄存器当中。这个寄存器一般被称作段表地址寄存器。

7.3 Hello的线性地址到物理地址的变换-页式管理

1.基本原理

将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)。程序加载时，可将任意一页放入内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是虚拟页号（VPN），后一部分为虚拟页偏移量（VPO）：

页式管理方式的优点是：

1）没有外碎片

2）一个程序不必连续存放。

3）便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。

缺点是：要求程序全部装入内存，没有足够的内存，程序就不能执行。

2.页式管理的数据结构

在页式系统中进程建立时，操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间，如果允许进程动态地申请空间，操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能，必须记录系统内存中实际的页框使用情况。操作系统还要在进程切换时，正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能，—个页式系统中，一般要采用如下的数据结构。

页表：页表将虚拟内存映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。页表是一个页表条目（PTE）的数组。虚拟地址空间的每个页在页表中一个固定偏移量处都有一个PTE。假设每个PTE是由一个有效位和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配。否则，这个地址就指向该虚拟页在磁盘上的起始位置。

3.页式管理地址变换

MMU利用VPN来选择适当的PTE，将列表条目中PPN和虚拟地址中的VPO串联起来，就得到相应的物理地址。

7.4 TLB与四级页表支持下的VA到PA的变换

虚拟地址被划分成4个VPN和1个VPO。每个VPNi都是一个到第i级页表的索引，其中1<=i<=4.第j级页表中的每个PTE，1<=j<=3，都指向第j+1级的某个页表的基址。第四级页表中的每个PTE包含某个物理页面的PPN，或者一个磁盘块的地址。为了构造物理地址，在能够确定PPN之前，MMU必须访问4个PTE。将得到的PPN和虚拟地址中的VPO串联起来，就得到相应的物理地址。

7.5 三级Cache支持下的物理内存访问

L1 d-cache的结构如图所示：通过6-11位的组索引找到对应的组，将组中每一行的tag与CT比较，若标记位匹配且有效位为1，说明命中，根据0-5位的块偏移取出数据，如果没有匹配成功，则向下一级缓存中查找数据。取回数据后，如果有空闲块则放置在空闲块中，否则根据替换策略选择牺牲块。

7.6 hello进程fork时的内存映射

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的pid。为了给这个新进程创建虚拟内存。它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记位只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面。

7.7 hello进程execve时的内存映射

加载并运行hello需要以下几个步骤：

1.删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。

2.映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区被映射为hello文件中的.text和.data区。bss区域是请求二进制零的，映射到匿名文件，其大小包含在hello中。栈和堆区域也是请求二进制零的，初始长度为零。

3.映射共享区域。如果hello程序与共享对象链接，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。

4.设置程序计数器。设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。下一次调度这个进程时，它将从这个入口点开始执行。

加载器如何映射用户地址空间的区域：

7.8 缺页故障与缺页中断处理

在虚拟内存的习惯说法中，DRAM缓存不命中称为缺页。例如：CPU引用了VP3中的一个字，VP3并未缓存在DRAM中。地址翻译硬件从内存中读取PTE3，从有效位推断出VP3未被缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4。如果VP4已经被修改了，那么内核就会将它复制回磁盘。无论哪种情况，内核都会修改VP4的页表条目，反映出VP4不再缓存在主存中这一事实。缺页之前：

接下来，内核从磁盘复制VP3到内存中的PP3，更新PTE3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在VP3已经缓存在主存中了，那么也命中也能由地址翻译硬件正常处理了。缺页之后：

7.9动态存储分配管理

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用。空闲块可用来分配。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。

1.隐式空闲链表：

空闲块通过头部中的大小字段隐含地连接着。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

（1）放置策略：首次适配、下一次适配、最佳适配。

首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配从上一次查询结束的地方开始。最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。

（2）合并策略：立即合并、推迟合并。

立即合并就是在每次一个块被释放时，就合并所有的相邻块；推迟合并就是等到某个稍晚的时候再合并空闲块。

带边界标记的合并:

在每个块的结尾添加一个脚部，分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，从而使得对前面块的合并能够在常数时间之内进行。

2.显式空闲链表

每个空闲块中，都包含一个pred（前驱）和succ（后继）指针。使用双向链表使首次适配的时间减少到空闲块数量的线性时间。

空闲链表中块的排序策略：一种是用后进先出的顺序维护链表，将新释放的块放置在链表的开始处，另一种方法是按照地址顺序来维护链表，链表中每个块的地址都小于它后继的地址。

分离存储：维护多个空闲链表，每个链表中的块有大致相等的大小。将所有可能的块大小分成一些等价类，也叫做大小类。

分离存储的方法：简单分离存储和分离适配。

7.10本章小结

本章讨论了存储器地址空间，段式管理、页式管理，TLB与四级页表支持下的VA到PA的变换，三级Cache支持下的物理内存访问，hello进程fork时和execve时的内存映射，缺页故障与缺页中断处理和动态存储分配管理。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

所有的I/O设备（例如网络、磁盘和终端）都被模型化为文件，而所有的输入和输出都被当做对相应文件的读和写来执行。这种将设备优雅地映射为文件的方式，允许Linux内核引出一个简单、低级的应用接口，称为Unix I/O，这使得所有的输入和输出都能以一种统一且一致的方式来执行。

8.2 简述Unix IO接口及其函数

I/O接口操作

1.打开文件：一个应用程序通过要求内核打开相应的文件，来宣告它想要访问一个I/O设备。内核返回一个小的非负整数，叫做描述符，它在后续对此文件的所有操作中标识这个文件。内核记录有关这个打开文件的所有信息。应用程序只需记住这个描述符。

2.Linux shell创建的每个进程开始时都有三个打开的文件：标准输入、标准输出和标准错误。

3.改变当前的文件位置：对于每个打开的文件，内核保持着一个文件位置k，初始为0.这个文件位置是从文件开头起始的字节偏移量。应用程序能够通过执行seek操作，显式地设置文件的当前位置为k。

4.读写文件：一个读操作就是从文件复制n>0个字节到内存，从当前文件位置k开始，然后将k增加到k+n。给定一个大小为m字节的文件，当k>=m时执行读操作会触发一个称为end-of-file（EOF）的条件，应用程序能检测到这个条件。在文件结尾处并没有明确的“EOF符号”。

类似地，写操作就是从内存复制n>0个字节到一个文件，从当前文件位置k开始，然后更新k。

5.关闭文件：当应用完成了对文件的访问之后，它就通知内核关闭这个文件。作为响应，内核释放文件打开时创建的数据结构，并将这个描述符恢复到可用的描述符池中。无论一个进程因为何种原因终止时，内核都会关闭所有打开的文件并释放它们的内存资源。

函数：

1.int open(char *filename, int flags, mode_t mode)

进程通过调用open函数来打开一个已存在的文件或者创建一个新文件。open函数将filename转换为一个文件描述符，而且返回描述符数字。flags参数指明了进程打算如何访问这个文件。mode参数指定了新文件的访问权限位。

2.int close(int fd)

进程通过调用close函数关闭一个打开的文件。

3.ssize_t read(int fd, void *buf, size_t n)

应用程序通过调用read函数来执行输入。read函数从描述符为fd的当前文件位置复制最多n个字节到内存位置buf。返回值-1表示一个错误，返回值0表示EOF。否则返回值表示的是实际传送的字节数量。

4.ssize_t write(int fd, const void *buf, size_t n)

应用程序通过调用write函数来执行输出。write函数从内存位置buf复制至多n个字节到描述符fd的当前文件位置。

8.3 printf的实现分析

https://www.cnblogs.com/pianist/p/3315801.html

printf的代码：

1.	int printf(const char *fmt, ...)   
2.	{   
3.	     int i;   
4.	     char buf[256];   
5.	      
6.	     va_list arg = (va_list)((char*)(&fmt) + 4);   
7.	     i = vsprintf(buf, fmt, arg);   
8.	     write(buf, i);   
9.	      
10.	     return i;   
11.	}   
           

其中，va_list是一个字符指针，arg表示函数的第二个参数。

vsprintf的代码：

1.	int vsprintf(char *buf, const char *fmt, va_list args)   
2.	{   
3.	    char* p;   
4.	    char tmp[256];   
5.	    va_list p_next_arg = args;   
6.	     
7.	    for (p=buf;*fmt;fmt++) {   
8.	    if (*fmt != '%') {   
9.	    *p++ = *fmt;   
10.	    continue;   
11.	    }   
12.	     
13.	    fmt++;   
14.	     
15.	    switch (*fmt) {   
16.	    case 'x':   
17.	    itoa(tmp, *((int*)p_next_arg));   
18.	    strcpy(p, tmp);   
19.	    p_next_arg += 4;   
20.	    p += strlen(tmp);   
21.	    break;   
22.	    case 's':   
23.	    break;   
24.	    default:   
25.	    break;   
26.	    }   
27.	    }   
28.	     
29.	    return (p - buf);   
30.	}   
           

vsprintf的作用是格式化。它接受确定输出格式的格式字符串fnt。用格式字符串对个数变化的参数进行格式化，产生格式化输出，并返回要打印的字符串的长度。

write的代码：

mov eax, _NR_write 
     mov ebx, [esp + 4] 
     mov ecx, [esp + 8] 
     int INT_VECTOR_SYS_CALL 
           

先给寄存器传了几个参数，然后通过系统调用sys_call

sys_call：
call save 
    
     push dword [p_proc_ready] 
    
     sti 
    
     push ecx 
     push ebx 
     call [sys_call_table + eax * 4] 
     add esp, 4 * 3 
    
     mov [esi + EAXREG - P_STACKBASE], eax 
    
     cli 
    
     ret 
           

syscall将字符串中的字节从寄存器中通过总线复制到显卡的显存中，显存中存储的是字符的ASCII码。

字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。

显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。

8.4 getchar的实现分析

1.int getchar(void)    
2.	{    
3.	    static char buf[BUFSIZ];    
4.	    static char *bb = buf;    
5.	    static int n = 0;    
6.	    if(n == 0)    
7.	    {    
8.	        n = read(0, buf, BUFSIZ);    
9.	        bb = buf;    
10.	    }    
11.	    return(--n >= 0)?(unsigned char) *bb++ : EOF;    
12.	}   
           

getchar函数调用read函数，将整个缓冲区都读到buf里，并将缓冲区的长度赋值给n。返回时返回buf的第一个元素，除非n<0。

异步异常-键盘中断的处理：键盘中断处理子程序。接受按键扫描码转成ascii码，保存到系统的键盘缓冲区。

getchar等调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。

8.5本章小结

本章简述了Linux的I/O设备管理机制，Unix I/O接口及函数，并简要分析了printf函数和getchar函数的实现。

结论

1.程序员通过编辑器创建hello.c。

2.预处理器根据以字符#开始的命令修改hello.c得到另一个C程序hello.i。

3.编译器将hello.i翻译成文本文件hello.s，它包含一个汇编语言程序。

4.汇编器将hello.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件hello.o中。

5.再经过链接器的处理，就得到了可执行目标文件hello。

6.用户键入命令，shell会fork一个子进程。

7.在这个子进程中调用execve加载hello。

8.然后程序会跳转到_start地址，最终调用hello的main函数。

9.hello通过调用sleep getchar exit等系统函数运行程序。

10.进程结束后会被shell回收。

做大作业的过程相当于复习了一下这个学期的知识，尤其是通过分析各种文件，我对编译汇编等过程的理解更加深刻了。这个大作业要求我们分析了hello程序运行各个阶段的底层实现，使我具体地认识到计算机系统的各个部分是怎样协调工作的。

参考文献

为完成本次大作业你翻阅的书籍与网站等

1.深入理解计算机系统第三版

2.https://baike.baidu.com/item/预处理命令/10204389

3.https://blog.csdn.net/shiyongraow/article/details/81454995

4.https://blog.csdn.net/u011555996/article/details/70211315

5.https://docs.oracle.com/cd/E26926_01/html/E25910/chapter6-54839.html

6.https://baike.baidu.com/item/逻辑地址/3283849?fr=aladdin

7.https://baike.baidu.com/item/线性地址

8.https://baike.baidu.com/item/虚拟地址

9.https://www.cnblogs.com/huangwentian/p/7487670.html

10.https://blog.csdn.net/youyou519/article/details/82659007

11.https://docs.oracle.com/cd/E26926_01/html/E25910/chapter6-83432.html

12.https://www.cnblogs.com/pianist/p/3315801.html