[2018 HIT CSAPP大作业] 程序人生 Hello’s P2P

发表于 | 更新于 | | 阅读次数：

摘 要

计算机系统是由硬件和软件组成的，它们共同工作来运行应用程序。即使是最简单的一个应用程序，也需要计算机系统中的每个主要组成部分协调工作。本文以hello程序的运行为切入点，解释了当在系统上运行hello程序时，系统发生的编译、链接、加载、进程管理、存储管理等过程，以及它们的运行机制。
关键词：操作系统；计算机组成原理；汇编

第1章 概述

1.1 Hello简介

Hello的P2P（Program to process）和020（From Zero to Zero）过程
用户在文本编辑器中编写代码得到hello.c。hello.c经过预处理（cpp）变成hello.i（修改了的源程序），经过编译（ccl）生成hello.s（汇编程序），经过汇编生成hello.o（可重定位目标程序），经过链接（ld）生成hello（可执行目标程序）。
用户键入命令，bash自行fork一个process，并在这个process中调用execve执行hello。execve加载hello，并调用_start函数，不久控制权被转移到hello的main函数。
hello调用write等系统函数在屏幕打印信息，随后退出，接下来终止的hello进程被父进程bash回收。
实验中所用的hello.c代码如下：

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
// 大作业的 hello.c 程序
// gcc -m64 -no-pie -fno-PIC hello.c -o hello
// 程序运行过程中可以按键盘，如不停乱按，包括回车，Ctrl-Z，Ctrl-C等。
// 可以 运行 ps  jobs  pstree fg 等命令

#include <stdio.h>
#include <unistd.h> 
#include <stdlib.h>

int sleepsecs=2.5;

int main(int argc,char *argv[])
{
	int i;

	if(argc!=3)
	{
		printf("Usage: Hello 学号 姓名！\n");
		exit(1);
	}
	for(i=0;i<10;i++)
	{
		printf("Hello %s %s\n",argv[1],argv[2]);
		sleep(sleepsecs);
	}
	getchar();
	return 0;
}

1.2 环境与工具

硬件环境：Intel(R) Core(TM) i5-3320M 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；hexedit

1.3 中间结果

为编写本论文，生成的中间结果文件的名字以及文件的作用。

文件名称 文件作用
hello.i hello预处理之后的文本文件
hello.s hello编译之后的汇编文件
hello.o hello汇编之后的可重定位目标文件
hello hello链接之后的可执行目标文件
hello_o.objdump hello.o的反汇编代码
hello_o.elf hello.o的ELF文件信息
hello.objdump hello的反汇编代码
hello.elf hello的ELF文件信息
test.c 测试用代码

1.4 本章小结

本章简要介绍了hello的P2P，O2O过程，并列出了本次实验的环境和中间结果。

第2章 预处理

2.1 预处理的概念与作用

预处理器（cpp）根据以字符#开头的命令，修改原始的C程序。比如hello.c中第1行的#include <stdio.h>命令告诉预处理器读取系统头文件stdio.h的内容，并把它直接插入程序文本中。结果就得到了另一个C程序，通常是以.i作为文件拓展名。
这个过程为接下来的编译过程“简化”了代码。

2.2在Ubuntu下预处理的命令

预处理命令：cpp hello.c > hello.i
pic1

2.3 Hello的预处理结果解析

pic2
经过预处理的hello代码被展开，在main之前插入了大量代码。这些代码是根据#include从stdio.h、unistd.h、stdlib.h中提取的，其中包含了printf的声明等。
pic3

2.4 本章小结

hello.c在编译之前需要经过预处理步骤，该步骤会根据hello.c中以#开头的命令展开相应代码并修改原始的C程序，以便下一步编译。

第3章 编译

3.1 编译的概念与作用

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

3.2 在Ubuntu下编译的命令

编译命令：gcc -S hello.i -o hello.s
pic4

3.3 Hello的编译结果解析

3.3.1 hello.s中出现的标识

  • .file 源文件
  • .data 数据段
  • .globl 全局标识符
  • .string 字符串类型
  • .long long类型
  • .text 代码段

3.3.2 数据类型

hello.c中出现的数据类型有整数类型（int）、字符串、字符指针数组。

整数类型

hello.c中的整数类型有全局变量int sleepsecs，main的参数int argc，局部变量int i。
全局变量int sleepecs的定义如下，可以看到第六行为其分配大小4字节，第八行为其赋初值2。
pic5
对sleepecs的调用采用了PC相对寻址：
pic6
参数int argc，局部变量i出现在main的栈帧中，它们没有标识符，也不需要被声明，而是直接使用。
pic7
pic8

字符串和字符指针数组

两个printf语句中的格式字符串出现在.rodata段。
pic9
作为main参数的char *argv[]则出现在栈帧中。
pic10

3.3.3运算与操作

赋值操作

源程序21行对i赋值为零的操作使用mov语句实现的。
pic11

比较操作

hello.c中的两个比较操作被解析为cmpl操作。
argc!=3
pic12
i<10
pic13

算术运算

for循环中的i++采用addl来实现。
pic14

数组操作

argv[1]：首先从-32(%rbp)读取argv地址存入rax，接下来rax增加8个字节，此时rax中存放的是&(argv[1])，读取此地址指向的argv[1]放入rax，最后存入rsi。
pic15
argv[2]：首先从-32(%rbp)读取argv地址存入rax，接下来rax增加16个字节，此时rax中存放的是&(argv[2])，读取此地址指向的argv[2]放入rdx。
pic16

3.3.4控制转移

if语句

if(argc!=3) {}
比较argc与3的大小，然后通过条件跳转je，实现若argc==3，则跳过if语句的代码块。
pic17
pic18

for循环

.L2初始化
pic19
.L3判断循环条件

pic20
.L4循环块（51行为迭代i）
pic21
首先给i赋值为0，然后跳转到.L3以比较i是否小于等于9，如果小于等于9，则跳转到循环块.L4，否则继续执行循环外的语句getchar。而循环块执行到末尾会继续执行循环判断条件.L3，重复以上步骤直至循环结束。

3.3.5 函数调用

对printf的调用，参数被存放在寄存器传递。以printf(“Hello %s %s\n”,argv[1],argv[2]);为例，格式化字符串被存放在edi传递，argv[1]被放在rsi，argv[2]被放在rdx。使用call来调用printf，而printf的返回值则会被存入eax返回。
pic22
对exit函数的调用，参数被存放在edi传递，然后使用call调用exit。
pic23
对sleep的调用，参数被存放在edi传递，然后使用call调用sleep。
pic24
对getchar的调用直接使用了call。
main函数的返回值放在eax传递。
pic25

3.4 本章小结

本章主要阐述了汇编操作是怎样处理源程序中的数据、各种操作、控制转移、函数调用的。
编译器将C语言代码转换成汇编代码，并最终转换生成机器码。这个转换过程中需要对原始代码中的数据和操作进行映射得到相应汇编代码下的解决方案，而由于全局变量引用等因素的影响，这个过程不是简单的一一映射关系。

第4章 汇编

4.1 汇编的概念与作用

汇编器（as）将hello.s翻译成机器指令，把这些指令打包成可重定位目标程序（relocatable object program）的格式，并将结果保存在目标文件hello.o中。hello.o文件是一个二进制文件，它包含的17个字节是函数main的指令编码。

4.2 在Ubuntu下汇编的命令

汇编命令as hello.s -o hello.o

pic26

4.3 可重定位目标elf格式

分析hello.o的ELF格式，用readelf等列出其各节的基本信息，特别是重定位项目分析。

名称 作用
ELF头 描述了生成该文件的系统的大小和字节顺序以及帮助链接器语法分析和解释目标文件的信息
.text 已编译的程序的机器代码
.rodata 只读数据
.data 已初始化的全局和静态C变量
.bss 未初始化的全局和静态C变量
.symtab 一个符号表，存放在程序中定义和引用的函数和全局变量的信息
.rel.text .text节的重定位记录表
.rel.data 被模块引用或定义的所有全局变量的重定位信息
.debug 一个调试符号表
.line 原始C源程序的行号和.text节中机器指令之间的映射
.strtab 一个字符串表
节头部表 每个节的偏移量大小

ELF头（ELF header）以一个16字节的序列开始，这个序列描述了生成该文件的系统的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。其中包括ELF头的大小、目标文件的类型（如可重定位、可执行或者共享的）、机器类型（如x86-64）、节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量。
pic27
不同节的位置和大小是由节头部表描述的，其中目标文件中每个节都有一个固定大小的条目。
pic28
.rela.text 一个.text节中位置的列表，当链接器把这个目标文件和其它文件组合时，需要修改这些位置。一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。另一方面，调用本地函数的指令则不需要修改。
如下图中有八个重定位记录。重定位记录的结构如下所示：

1
2
3
4
5
typedef struct {
	int offset;    /* Offset of the reference to relocate */ 
	int symbol:24, /* Symbol of the reference should point to */
	type:8;	       /* Relocation type */
} Elf32_Rel;

以下图对sleepsecs的重定位记录为例。它的offset为0x5c，即需要修改的位置是.text段偏移量0x5c处；sybol为0x9，对应.symtab中第9号索引（sleepsecs）；type是0x2，即类型为重定位PC相对引用。
pic29
pic30
.symtab 一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。和编译器中的符号表不同，.symtab符号表不包含局部变量的条目。

4.4 Hello.o的结果解析

pic31
hello.o的反汇编与hello.s的差别总体不大，主要体现在以下几方面：

  1. 全局变量引用 hello.o反汇编采用的是offset(%rip)的形式，而hello.s采用的是symbol(%rip)的形式。
  2. 函数调用 hello.o反汇编采用的是call offset的形式，而hello.s采用call symbol的形式。
  3. 分支转移 hello.o反汇编采用的是jmp offset的形式，而hello.s采用jmp Label的形式。
  4. 栈帧大小不同。
    机器指令由指令指示符、（寄存器指示符）、（常数字）组成。

机器语言与汇编语言大致具有一一对应的关系。但有些特殊情况，比如：

  1. 转移控制 汇编语言中的jmp指令有直接跳转（在hello.o的反汇编中这个地址为绝对地址）和间接跳转，而转换成机器码后跳转指令会有几种不同的编码，最常用的是PC相对的，还有给出绝对地址的。而汇编器和链接器会选择适当的跳转目的编码。
  2. 一条指令可能有多个汇编码中的别名，例如jle和jg。
  3. 函数调用，在hello.o的反汇编文件中，call的地址是下一条指令的地址，而对应机器码中的操作码为0。这是因为hello.c中调用的函数都是共享库中的函数，在链接后才能确定函数的最终地址。因而在hello.o中只是将call的地址置为下一条指令的地址，而机器码的操作数则为目标位置（这里为下一条指令）相对于下一条指令的偏移，即0。

4.5 本章小结

本章阐述了hello从hello.s到hello.o的汇编过程。分析了hello.o的ELF格式，并通过查看比较反汇编代码和汇编代码分析了汇编语言与机器码的关系。
汇编过程将汇编语言转换为机器码，生成可重定位目标文件，这个文件根据ELF格式对机器码进行打包，并为接下来的链接过程做好了准备。

第5章 链接

5.1 链接的概念与作用

链接是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可以被加载（复制）到内存执行。链接可以执行于编译时，也可以执行于加载时，甚至执行于运行时。
链接器使得分离编译成为可能。我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的其中一个时，只需简单地重新编译它，并重新链接应用，而不必重新编译其它文件。

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/5/crtbegin.o hello.o -lc /usr/lib/gcc/x86_64-linux-gnu/5/crtend.o /usr/lib/x86_64-linux-gnu/crtn.o -z relro -o hello.out
pic32

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

Linux的ELF文件格式如下：

名称 作用
ELF头 描述文件的总体格式，包括程序的入口点
段头部表 将连续的文件映射到运行时内存段
.init 定义了一个小函数_init
.text 已编译的程序的机器代码
.rodata 只读数据
.data 已初始化的全局和静态C变量
.bss 未初始化的全局和静态C变量
.symtab 一个符号表，存放在程序中定义和引用的函数和全局变量的信息
.debug 一个调试符号表
.line 原始C源程序的行号和.text节中机器指令之间的映射
.strtab 一个字符串表
节头部表 每个节的偏移量大小

hello的ELF头

pic33
节头部表 节头部表对hello中所有的节进行了声明，其中Size是每个节的大小，Offset是每个节在程序中的偏移量，Address是程序被载入后各段的虚拟地址。
pic34

段头部表

pic35

5.4 hello的虚拟地址空间

.plt 位于代码段的plt表
pic36
.text 代码段 如图为hello!_start函数
pic37
.rodata 只读数据段
pic38
.data 数据段
pic39
.bss 位初始化和被初始化为零的数据段
pic40
.got 初始化前的got表
pic41

5.5 链接的重定位过程分析

hello相比hello多了许多节，如:

节 作用
.interp 保存ld.so的路径
.rela.plt .plt的重定位项目
.init 初始化代码
.plt 动态链接过程链接表
.got 动态链接全局偏移量表，用于存放变量
.got.plt 动态链接全局偏移量表，用于存放函数

hello.o的objdump与hello的objdump主要有以下几点不同：

  1. hello.o的objdump没有_init函数、_start函数、plt表等。
  2. hello.o的objdump中对全局变量的引用地址均为0，函数调用的地址也只是当前指令的下一条指令的地址。

hello的重定位记录有两种，分别是PC相对地址的引用和绝对地址的引用。
进行重定位时，hello根据.rela.text和.rela.data中的重定位记录，在.symtab中查找需要修改的记录的符号，并结合符号与重定位记录中的位置信息对目标位置进行 修改。如果需要修改的符号是本地符号，则计算偏移量并修改目标位置；如果是共享库中的符号，则创建.got表项（如果是函数还需创建.plt项），并创建新的重定位记录指向.got表项。

5.6 hello的执行流程

hello执行过程中调用的函数 函数的地址
_dl_start 0x7fb78d93ac38
_dl_init 0x7fb78d9424e0
_start 0x400550
__libc_start_main@plt 0x7fb78d590740
__libc_csu_init 0x4006d0
init 0x4004a8
main 0x400646
__GI_exit 0x7fb78d5aa030
__run_exit_handlers 0x7fb78d5a9f10
_dl_fini 0x7fb78d94aab0
_IO_cleanup 0x7fb78d5ec310
_IO_flush_all_lockp 0x7fb785ec020

5.7 Hello的动态链接分析

无论在内存中的何处加载一个目标模块（包括共享目标模块），数据段与代码段的距离总是保持不变。因此，代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量，与代码段和数据段的绝对内存位置是无关的。
而要生成对全局变量PIC引用的编译器利用了这个事实，它在数据段开始的地方创建了一个表，叫做全局偏移量表（GOT）。在GOT中，每个被这个目标模块引用的全局数据目标（过程或全局变量）都有一个8字节条目。编译器还为GOT中每个条目生成 一个重定位记录。在加载时，动态链接器会重定位GOT中的每个条目，使得它包含目标的正确的绝对地址。
hello中对.got的初始化是由_dl_start函数执行的。下面的四张图片反应了这一过程：

pic42
.got _dl_start执行前
pic43
.got.plt _dl_start执行前
pic44
.got _dl_start执行后
pic45
.got.plt _dl_start执行后

hello要调取由共享库定义的函数puts，printf，而程序调用一个由共享库定义的函数，编译器没有办法预测这个函数的运行地址，因为定义它的共享模块在运行时可以加载到任何位置。为了解决这个问题，GNU编译系统使用了延迟绑定技术：
当hello尝试调用puts时，不直接调用puts，而是调用进入puts对应的PLT条目。这个条目会尝试利用GOT项进行间接跳转。
pic46
第一次被调用时，GOT项的值为PLT条目中的下一条指令地址，因而接下来会跳回PLT条目，在把puts的ID 0压入栈后，会转到PLT[0]的位置，PLT[0]通过GOT[1]间接地把动态链接器的一个参数压入栈中，然后通过GOT[2]跳转进动态链接器中。动态链接器使用两个栈条目来确定puts的运行时位置，用这个地址重写puts的GOT项，再把控制传递给puts。
pic47
在下一次执行到puts对应的PLT条目时，GOT项已经被修改，因此利用GOT项进行的间接跳转会直接跳转到puts函数。
pic48

5.8 本章小结

本章讨论了hello的链接过程。链接过程可以发生在编译时，也可以发生在加载时，甚至可以发生在程序执行时。静态链接直接将目标文件和库文件打包至一个可执行文件中，而动态链接则只在可执行目标文件中添加相应重定向记录，并通过GOT表项和延迟绑定的方法实现对目标模块中符号的引用。

第6章 hello进程管理

6.1 进程的概念与作用

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

作用：进程提供给应用程序两个关键抽象：

  1. 逻辑控制流
    a) 每个程序似乎独占地使用CPU
    b) 通过OS内核的上下文切换机制提供
  2. 私有地址空间
    a) 每个程序似乎独占地使用内存系统
    b) OS内核的虚拟内存机制提供

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

概念：shell是一个交互型的应用级程序，它代表用户运行其它程序。它执行一系列的读/求值步骤，然后终止。其中读步骤读取来自用户的一个命令行，求值步骤解析命令行，并代表用户运行程序。

处理流程：读取来自用户的命令行并解析，如果是内部命令则直接执行内部命令，否则fork一个shell进程，并在这个进程中用execve加载目标程序，按照命令中的参数决定在前台或者后台运行目标程序，当前台程序结束时用waitpid回收进程。

6.3 Hello的fork进程创建过程

在bash中输入 ./hello 1******* *** 并敲击回车后，bash解析此条命令，发现./hello不是bash内置命令，于是在当前目录尝试寻找并执行hello文件。此时bash使用fork函数创建一个子进程（这个子进程得到与父进程用户级虚拟地址空间相同但是独立的一份副本），并更改这个子进程的进程组编号。并准备在这个子进程执行execve。

6.4 Hello的execve过程

在新创建的子进程中，execve函数加载并运行hello，且带参数列表argv和环境变量envp。在execve加载了hello之后，它调用_start，_start设置栈，并将控制传递给新程序的主函数。

6.5 Hello的进程执行

在输入合适参数执行hello程序之后，hello进程一开始运行在用户模式。内核为hello维持一个上下文，它由一系列的值组成，这些对象包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构（比如页表、进程表、文件表）。

在hello运行时，也有一些其它进程在并行地运行，这些进程的逻辑流的执行时间与hello的逻辑流重叠，称为并发流。而一个进程和其它进程轮流运行的概念叫作多任务，一个进程执行它的控制流的一部分的每一时间段叫做时间片。因此，多任务也叫做时间分片。
pic49
不久hello调用printf与sleep，这两个函数引发系统调用，系统调用使得进程从用户模式变为内核模式，处理程序运行在内核模式中，当它返回到应用程序代码时，处理器就把模式从内核模式改回到用户模式，而执行sleep系统调用时，内核可能会执行上下文切换而非将控制返回给hello进程。在切换的第一部分中，内核代表hello在内核模式下执行指令，然后在某一时刻，它开始代表另一个进程在内核模式下执行指令，在切换之后，内核代表那个进程在用户模式下执行指令。
而这个切换过程可以分为三个步骤
1) 保存当前进程的上下文
2) 恢复某个先前被抢占的进程被保存的上下文
3) 将控制传递给这个新恢复的进程。

pic50
这时我们说内核调度了一个新的进程，在内核调度了一个新的进程后，它就抢占了当前进程。
不仅仅是系统调用会导致上下文切换，中断也会。当hello执行了一段时间（通常是1-10ms）后，定时器引发的中断也会导致内核执行上下文切换并调度一个新的进程。
接下来的十秒中，内核继续执行上下文切换，轮流运行hello与其它进程，十次循环结束后，hello返回，程序终止。

6.6 hello的异常与信号处理

6.6.1 hello在运行时可能会出现的异常

故障：缺页异常 加载完成后hello进程的页表被映射到hello文件，但还未将实际代码拷贝至内存，在执行到相应地址的代码时会引发缺页异常，拷贝相关代码。
中断：如来自键盘的信号（见下文） 定时器中断
陷阱：系统调用造成，如sleep函数
终止：不可恢复的错误，如hello执行时硬件被物理伤害造成奇偶校验错误。

6.6.2 hello在运行时可能会接受到的信号

SIGINT 中断信号 当用户键入ctrl+c时会产生这个信号，接受这个信号，程序默认终止，如果有已经定义的handler，则会执行handler。
pic51
SIGTSTP 停止信号 当用户键入ctrl+z时会产生这个信号，接受这个信号的默认行为是中止程序，这个默认行为不可更改。
pic52
SIGKILL 终止信号 使用kill -9向hello发出这个信号，接受这个信号的默认行为是终止程序，这个默认行为不可更改。
pic53
SIGCHLD 子进程信号 hello终止或中止时会向父进程（bash）发出这个信号。如果hello中止；则bash会将其标记为中止状态，如果hello已经终止，则bash会回收hello进程。

6.7本章小结

本章介绍了进程的概念与作用，并通过hello程序演示了进程的执行过程。
简要介绍了shell的工作流程，并分析了linux下的异常处理机制，介绍了应用程序的信号处理。

shell执行程序是通过fork函数以及execve创建新的进程并执行程序的。
程序运行中可能会遇到异常，异常分为中断、陷阱、故障、终止四类，由异常处理子程序来处理，信号作为一种特殊的异常，实现了对程序运行终止等操作的控制。

第7章 hello的存储管理

7.1 hello的存储器地址空间

逻辑地址空间：段地址：偏移地址
23：8048000 段寄存器（CS等16位）：偏移地址（16/32/64）

  • 实模式下：逻辑地址CS：EA=物理地址CS * 16 + EA
  • 保护模式下：以段描述符作为下标，到GDT/LDT表查表获得段地址，
    段地址+偏移地址=线性地址。

线性地址空间: 非负整数地址的有序集合:：{0, 1, 2, 3 … }
虚拟地址空间: N = 2n 个虚拟地址的集合=线性地址空间
{0, 1, 2, 3, …, N-1}
物理地址空间: M = 2m 个物理地址的集合
{0, 1, 2, 3, …, M-1}
Intel采用段页式存储管理（MMU实现）
段式管理： 逻辑地址->线性地址==虚拟地址
页式管理： 虚拟地址->物理地址

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

实模式下：逻辑地址CS：EA=物理地址CS * 16 + EA
保护模式下：以段描述符作为下标，到GDT/LDT表查表获得段地址，
段地址+偏移地址=线性地址。
pic54

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

hello的线性地址到物理地址的变换需要查询页表得出，hello的线性地址被分成两个部分，第一部分虚拟页号VPN用于在页表查询物理页号PPN，而第二部分虚拟页偏移量VPO则与查询到的物理页号PPN一起组成物理地址。
pic55

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

pic56
虚拟地址VA被分成VPN和VPO两部分，VPN被分为TLBT和TLBI用于在TLB中查询。根据TLBI确定TLB中的组索引，并根据TLBT判断PPN是否已被缓存到TLB中，如果TLB命中，则直接返回PPN，否则会到页表中查询PPN。在页表中查询PPN时，VPN会被分为四个部分，分别用作一二三四级页表的索引，而前三级页表的查询结果为下一级页表的基地址，第四级页表的查询结果为PPN。将查询到的PPN与VPO组合，得到物理地址PA。

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

MMU发送物理地址PA给L1缓存，L1缓存从物理地址中抽取出缓存偏移CO、缓存组索引CI以及缓存标记CT。高速缓存根据CI找到缓存中的一组，并通过CT判断是否已经缓存地址对应的数据，若缓存命中，则根据偏移量直接从缓存中读取数据并返回；若缓存不命中，则继续从L2、L3缓存中查询，若仍未命中，则从主存中读取数据。

7.6 hello进程fork时的内存映射

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

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

7.7 hello进程execve时的内存映射

execve函数在当前进程中加载并运行包含在可执行文件hello中的程序，加载并运行hello时出现的内存映射有：

  1. 映射私有区域 为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为hello文件中的.text和.data区。Bss区域时请求二进制零的，映射到匿名文件，其大小包含在hello中。栈和堆区域也是请求二进制零的，初始长度为零。
  2. 映射共享区域 如果hello程序与共享对象（或目标链接），比如C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
    pic57

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

缺页故障：虚拟内存中的字不在物理内存中（DRAM缓存不命中）
如下图，VP3已经被映射到页表中，但却没有被缓存到物理内存中，此时堆VP3的引用会引发缺页故障。
pic58
缺页会导致页面出错引发一个缺页中断，而缺页异常处理程序会选择一个牺牲页（如下图选择了VP4，将VP4从内存交换到磁盘，并从磁盘读取VP3交换到物理内存）。
pic59
此时令导致缺页的指令重新启动，就可以使得页面命中了。

7.9动态存储分配管理

printf会调用malloc，接下来提一下动态内存分配的基本原理。

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。系统之间细节不同，但是不失通用性，假设堆是一个请求二进制零的区域，它紧接在未初始化的数据区域后开始，并向上生长。对于每个进程，内核维护着一个变量brk，它指向堆的顶部。分配器将堆视为一组不同大小的块的集合来维护，每个块就是一个连续的需内存片，要么是已分配的，要么是空闲的。已分配的块显示地保留为供应用程序使用。空闲块可以用来分配。空闲块保持空闲，直到它显示地被应用所分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显示执行的，要么是内存分配器自身隐式执行的。

两种堆的数据结构组织形式：

带标签的隐式空闲链表

带标签的隐式空闲链表的数据组织方式如下图：
pic60
空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

显式空闲链表

显式空闲链表将链表的指针存放在空闲块的主体里面。堆被组织成一个双向空闲链表，在每个空闲块中，都包含一个pred和succ指针，如下图所示：
pic61

7.10本章小结

现代操作系统多采用虚拟内存系统，访存时地址需要从逻辑地址翻译到虚拟地址并进一步翻译成物理地址。
操作系统通过地址的页式管理来实现对磁盘的缓存、内存管理、内存保护等功能。
虚拟内存为便捷的加载、进程管理提供了可能。
程序运行过程中往往涉及动态内存分配，动态内存分配通过动态内存分配器完成。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

一个linux文件就是一个m个字节的序列：
B0, B1, … Bk, …, Bm-1

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

8.2 简述Unix IO接口及其函数

打开和关闭文件

int open(char *filename, int flags, mode_t mode);
open函数将filename转换为一个文件描述符，并返回描述符数字。返回的描述符总是在进程中当前没有打开的最小描述符。flags参数指明了进程打算如何访问这个文件，mode参数指定了新文件的访问权限位。
int close(int fd);
进程通过调用close关闭一个打开的文件。

读和写文件

ssize_t read(int fd, void *buf, size_t n);
read函数从描述符为fd的当前文件位置复制最多n个字节到内存位置buf。返回值-1表示一个错误，而返回值0表示EOF。否则，返回值表示的是实际传送的字节数量。
ssize_t write(int fd, const void *buf, size_t n);
write函数从内存位置buf复制之多n个字节到描述符fd的当前文件位置。
DIO *opendir(const char *name);
函数opendir以路径名为参数，返回指向目录流的指针。流是对条目有序列表的抽象，在这里是指目录项的列表。
struct dirent *readdir(DIR *dirp);
每次对readdir的调用返回的都是指向流dirp中下一个目录项的指针，或者，如果没有更过目录项则返回NULL。
int closedir(DIR *dirp);
函数closedir关闭流并释放其所有的资源。

I/O重定向

int dup2(int oldfd, int newfd);
dup2函数复制描述符表表项oldfd到描述符表项newfd，覆盖描述符表表项newfd以前的内容。如果newfd已经打开了，dup2会在复制oldfd之前关闭newfd。

8.3 printf的实现分析

printf函数的实现大致与下面代码一致：

1
2
3
4
5
6
7
8
9
10
11
int printf(const char *fmt, ...)
{
    int i;
    char buf[256];

    va_list arg = (va_list)((char *)(&fmt) + 4);
    i = vsprintf(buf, fmt, arg);
    write(buf, i);

    return i;
}

其中va_list_arg是边长参数列表中的第一个参数的地址，vsprintf的作用是以fmt作为格式字符串，根据arg中的参数，向buf中输出格式化后的字符串。write则是Unix I/O接口，它将栈中参数存入寄存器，并由它来进行系统调用。write的实现大致如下，其中ecx是字符个数，ebx存放第一个字符地址：
write:

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

接下来syscall将字符串从寄存器中通过总线复制到显卡显存中。字符显示驱动子程序通过ASCII码在字模库中找到点阵信息并将其存储到vram中。接下来显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。此时字符串就被打印到了屏幕上。

8.4 getchar的实现分析

getchar函数的大致实现如下：

1
2
3
4
5
int getchar(void)
{
    char c;
    return (read(0,&c,1)==1)?(unsigned char)c:EOF
}

getchar函数通过调用read函数来读取字符。read函数由三个参数，第一个参数为文件描述符fd，fd为0表示标准输入；第二个参数为输入内容的指针；第三个参数为读入字符的个数。read函数的返回值是读入字符的个数，若出错则返回-1。

当用户按键时，键盘接口会产生一个键盘扫描码和一个中断请求，中断处理程序会从键盘接口取得按键扫描码并把它转换成ASCII码，保存到系统的键盘缓冲区。

read执行一个系统调用，按照系统调用从键盘缓冲区读取按键ASCII码，直到接受到回车键才返回。

8.5本章小结

I/O时在主存和外部设备之间复制数据的过程。在Linux中，I/O的实现是通过Unix I/O函数来执行的。Linux把所有的I/O设备模型化为文件，并提供统一的Unix I/O接口，这使得所有的输入输出都能以一种统一且一致的方式来执行。

结论

hello的一生

  1. 用户从键盘输入，得到hello.c源文件。
  2. 编译器和汇编器对hello.c进行预处理，然后对其进行编译和汇编，得到可重定位目标文件hello.o。
  3. 链接器对hello.o进行链接，并得到可执行目标文件hello，此时hello已经可以被操作系统加载和执行。
  4. bash执行hello，首先bash会fork一个进程，然后在这个新的进程中execve hello，execve会清空当前进程的数据并加载hello，然后把rip指向hello的程序入口，把控制权交给hello。
  5. hello与许多进程并行执行，执行过程中由于系统调用或者计时器中断，会导致上下文切换，内核会选择另一个进程进行调度，并抢占当前的hello进程。
  6. hello执行的过程中可能收到来自键盘或者其它进程的信号，当收到信号时hello会调用信号处理程序来进行处理，可能出现的行为有停止终止忽略等。
  7. hello输出信息时需要调用printf和getchar，而printf和getchar的实现需要调用Unix I/O中的write和read函数，而它们的实现需要借助系统调用。
  8. hello中的访存操作，需要经历逻辑地址到线性地址最后到物理地址的变换，而访问物理地址的数据可能已被缓存至高速缓冲区，也可能位于主存中，也可能位于磁盘中等待被交换到主存。
  9. hello结束进程后，bash作为hello的父进程会回收hello进程。

在Kernighan和Ritchie的关于C编程语言的经典教材中，他们通过一个简单的hello程序来向读者介绍C。尽管hello非常简单，但是为了让它实现运行，系统的每个主要组成部分都需要协调工作。从某种意义上来说，计算机系统课程的学习，就是让我们了解当在系统上执行hello程序时，系统发生了什么以及为什么会这样。