摘  要

Hello World程序是许多程序员入门的第一个程序，其内容通常包括引用标准库，编写主函数，并打印格式字符串。虽然该程序内容十分简单，但其完整运行经历了从程序到进程（P2P），从零内存占用到零消息残余（020）的过程。本文从源代码开始，详细地讲述了程序编译、运行、执行IO操作的各个阶段的原理及内容，以Hello World为线索梳理了计算机底层的数个重要体系。

关键词：操作系统，编译，进程，虚拟内存

---

   
第一章 概述

"In the beginning, God created the heavens and the earth." - from the Bible

起初，上帝创造世界——《圣经·创世纪》，第一节

在此，我们踏上改变世界的道路

1.1 Hello简介

Hello world程序自编写到运行，大致经过了以下步骤：

        1.程序的输入和编码：字符输入进文本编辑器，形成的.c文件以字符编码的形式存储在磁盘中。

        2.程序的编译：通过编译工具链，.c文件经过预处理、汇编、编译、链接四个步骤，形成一个可执行文件。

图 1-1 编译的步骤

        3.程序的启动：通过shell，程序员指定可执行文件的路径，shell通过fork分出子进程用于运行程序。

        4.程序的加载：在fork中使用execve删除子进程原来的虚拟内存空间区域，用mmap将可执行文件的代码段和数据段映射到新创建的内存空间区域。加载器还调用动态链接器linux-ld.so将程序完全链接。

图 1-2 程序的加载

        5.程序的运行（指令层面）：可执行文件的代码段被翻译为机器指令，CPU不断地取指执行，使用流水线等技术加快取指执行的速度。

        6.程序的运行（访存层面）：CPU产生的每一个地址，都经过内存管理单元MMU进行地址翻译，它将虚拟地址经由页表转换为物理地址，然后CPU使用同一个物理地址逐级访问Cache获取数据。

图 1-3 Intel Corei7地址翻译和缓存访问的总体流程

         7.程序的运行（进程层面）：程序运行在fork出的子进程上，从程序转换为进程（P2P）。与其他许多进程一起受操作系统的调度，不断进行上下文的切换。异常处理和信号机制在此层您发挥作用

        8.程序的运行（IO层面）：程序通过IO库函数进行输入输出，这些函数最终又进行系统调用。中间涉及到读写缓冲区，键盘和显示屏的驱动方法等。

        9.程序的结束：当进程结束时，其控制块（PCB）并没有被销毁，直到它的父进程（shell）用waitpid将它回收，或者父进程也被终止，从而导致它被守护进程（init）回收。程序加载前不占用内存空间，回收后也不保留任何信息，这就是020。

1.2 环境与工具

1.2.1 硬件环境

主机硬件环境：

图 1-4  主机硬件环境

 图 1-5 服务器硬件环境    图 1-6 虚拟机硬件环境

1.3 中间结果

表 1 中间结果

文件名	内容
hello	可执行文件
hello.asm	目标文件的反汇编信息
hello.c	源文件
hello.i	预处理后文件
hello.o	可重定位目标文件
hello.s	汇编后文件
hello - elf.txt	可执行文件的readelf信息
hello - linked.asm	可执行文件的反汇编信息
hello - o - elf.txt	目标文件的readelf信息
output - gdb.txt	保存了所有函数调用的记录
output - gdb - parsed.txt	从上述文件中提取的函数调用记录
output - gdb - parsed - unique.txt	将上述文件内容排序并去掉重复的记录
parse - output - gdb.sh	从output - gdb.txt生成output - gdb - parsed.txt的脚本

1.4 本章小结

本章概述了hello world运行中经过的几个步骤，交代了使用的环境与工具，并且给出了对hello world程序进行实验的过程中产生的中间结果清单。

---

第二章 预处理

"We know what we are, but know not what we may be." - from "Hamlet" by William Shakespeare

我们知道我们是什么，但不知道我们可能成为什么。——《哈姆雷特》，威廉·莎士比亚

在此，我们成为更加完善的存在

2.1 预处理的概念与作用

在C语言的编译过程中，预处理是第一个阶段。预处理器会根据一系列以“#”开头的预处理指令来修改源代码，生成经过宏替换、条件编译和包含文件处理后的文件。预处理器还会删除源代码中的注释部分。

下表展示了一些常见的预处理指令及其作用

表 2-1 常见预处理指令及其功能

预处理指令	预处理效果	作用
#define	宏替换	定义常量、宏函数或简化代码
#undef	取消宏定义	取消先前的宏定义
#ifdef、#ifndef、#if、#elif、#endif	条件编译	根据条件选择性地编译代码，可用于防止头文件重复包含
#include	包含文件	将其他文件的内容插入到当前文件中
#pragma	特定编译器指令	发出特定于编译器的指令，如优化选项、警告设置等
#error	错误指令	在预处理阶段生成错误信息
#line	行号指令	修改行号信息，用于调试和错误报告
#pragma once	防止多重包含	确保头文件只被包含一次

2.2在Ubuntu下预处理的命令

GNU的预处理器名为cpp（C PreProcessor），通过在命令行中输入：

cpp hello.c > hello.i

可以对hello.c文件进行预处理。

图 2-1 预处理命令

2.3 Hello的预处理结果解析

预处理后的文件变得很长，我们来观察一下预处理指令在其中起到了哪些作用，以及这些指令是如何在我们的程序中发挥作用的。

2.3.1 递归地包含头文件

预处理指令最大的作用就在于包含头文件，它使得我们可以将定义和声明分开，进而为模块化开发、在不提供源码的情况下发布库提供了手段。

在hello.i的开头，我们看到了一连串以井号开头的文本，这是预处理器生成的注释，以“#”开头，后面跟着的是行号和源文件，以及一些调试信息（文件版本号）。

图 2-2 hello.i的前几行

这些文件表明，在展开hello.c的过程中，引入了stdio.h，而stdio.h从第一行到第27行都被跳过，在第27行又引入了libc-header-start.h

让我们来看看stdio.h的内容：

 图 2-3 stdio.h的1~27行

可以看到，stdio.h从1~27行都是注释和宏定义，因此没有在.i产生任何信息。但是在第27行include了一个新的文件，于是预处理器进入这个文件，开始将这个文件的内容按照类似的流程输出到.i文件中。这样，我们就能递归地将所有依赖的头文件，以及这些依赖的依赖全部输出到.i文件中。

下面的一个观察可以证实预处理器确实是按照“深度优先”的方式进行递归处理的：

图 2-4 hello.i的后几行

我们看到，预处理器先完成对libc-header-start.h第34行的处理，再完成stdio.h28行的处理。而预处理器进入时，是从stdio.h的27行进入libc-header-start.h的33行，再继续处理（见图 2-2），这是一个“后进先出”的深度优先处理过程。

2.3.2 函数、变量、类型的声明

我们知道，printf等函数必须要包含stdio.h头文件才能使用，原因就是这个头文件里包含了它们的声明。

图 2-5 hello.i中printf系列函数的声明

而标准库的IO需要用到FILE结构体，三个标准流的FILE*指针也通过递归包含在hello.i中声明：

图 2-6 hello.i中的标准流的FILE*指针

而FILE这个类型本身，在stdio.h第42行中include的FILE.h中定义：

图 2-7 hello.i中的FILE类型定义

这样，hello.i中就已经包含了所有需要用到的函数、变量、类型的声明了。

2.3.3 原本的C文件去掉注释和预处理指令后原样保留

hello.i的最后一部分内容，是处理完stdlib.h的第1035行之后，将hello.c从第十行开始原样保留到了最后。在此之前，1~5行的注释和空行，以及6、7、8行的预处理指令都已经被处理。

图 2-8 hello.i中保留的hello.c

2.4 本章小结

预处理是程序编译的这个阶段，预处理器（cpp）根据预处理指令，执行头文件包含、宏展开、条件编译、注释去除，使得最终成型的文件（.i扩展名）中包含所有依赖及其递归依赖，其中就有函数、变量和类型的声明。这样经过预处理的文件就可以作为一个独立的编译模块进行编译了。

---

第三章 编译

""Transformation is not a future event, it is a present activity." - from the book "The Power of Now" by Eckhart Tolle

“转变不是未来的事件，它是当下的活动。”——《当下的力量》，埃克哈特·托利

在此，我们成为接近本质的存在

在上面的过程中，L2就对应着“DONE”标签，因为没有ELSE语句，相关的内容被省略了。

接下来来看下面的代码：

 图 3-11 for循环对照 (左)汇编实现(右)C语言代码

可以看到，循环头语句执行完毕之后，就跳转到.L3进行判断，如果判断成立就跳回.L4，.L4的最后一句话是循环尾语句，这是被称之为jump-into-middle的翻译方法：

for(init-expr;test-expr;update-expr){ body-statements... }

init-expr; goto TEST LOOP: body-statements... update-expr   TEST： cond = test-expr if(cond) goto LOOP

在上面的过程中，.L3就对应LOOP标签，.L4就对应TEST标签。

3.3.8 函数调用：参数传递和栈帧

函数调用时，前六个参数依次通过%rdi，%rsi，%rcx，%rdx，%r8，%r9传递，返回值保存在%rax中。观察下面的两个函数调用：

 图 3-12 函数调用1 （左）汇编实现（右）C语言代码

从中可以看到，加载的字符串地址传入%rdi，调用了puts而非printf，这是一个编译器的优化。接着，参数1传入%edi，并将%rdi的高位清零，调用了exit，与C语言的参数对应。

接下来，我们观察参数更多的情况：

 图 3-13 函数调用2

从中可以看到，argv2被加载入%rdx，然后是argv1加载入%rsi，最后.LC1也就是格式字符串加载入%rdi。这个加载的顺序是倒过来的，因为当参数大于七个时，也需要将他们倒序压入栈中，所以编译器应该都是倒序准备参数的。

atoi的参数是argv3，他也加载入%rdi，注意再次调用sleep时，直接将返回值%rax移入%rdi即可（这里还涉及到前面提到的隐式转换）。

下面是没有参数并且忽略返回值的getchar，可以看到不需要进行参数的准备，也直接覆盖了它存放在%rax的返回值中。

  图 3-14 函数调用3

在函数调用的过程中，使用栈帧来进行局部变量和参数的保存。一个典型栈帧结构如下：

 图 3-15 栈帧及其在hello.s中的相关内容

 在hello.s中，使用了%rbp来保存栈基址位置，分配了32字节的空间给临时变量和对齐，然后在返回时用leave指令恢复%rbp。

3.4 本章小结

高级程序语言提供了机器无关的抽象，然而，实际的程序运行是紧密机器相关的。编译器充当了转换的媒介，为我们自动地实现类型、变量、表达式、函数调用等语意。从这个角度说，没有编译器就没有高级程序语言。

历史上第一个编译器使用了称为自举开发的基础，每次用一个语言子集实现其超集的编译，直到最后完全实现对整个语言的支持。

---

第四章 汇编

"The true alchemists do not change lead into gold; they change the world into words." - from "The Anatomy of Melancholy" by Robert Burton

“真正的炼金术士不是将铅变成金，而是将世界转化为字。”

——《忧郁的解剖》，罗伯特·伯顿

在此，我们获得改变世界的力量

4.1 汇编的概念与作用

汇编是编译过程的第三步，汇编器 (as) 将 .s汇编语言文件翻译成机器语言指令，并根据.s中的伪指令和汇编器指令，把这些指令打包成可重定位目标程序.o 文件。从这里开始，生成的文件都是二进制文件，而非文本文件了。

汇编的作用是产生机器可读的代码和数据，并且将他们分成若干节，为他们准备节头表和ELF头。

4.2 在Ubuntu下汇编的命令

as hello.s -o hello.o

图 4-1 Ubuntu下汇编的命令 

4.3 可重定位目标elf格式

使用下列指令，列出hello.o的ELF分析结果：

readelf hello.o > hello-o-elf.txt -all

可以看到，hello.o的主要内容包括ELF头、节头部表、重定位条目、符号表。

表 4-1 可重定位文件的典型结构

内容	含义
ELF 头	字大小、字节序/文件类型(.o，exec，.so)、机器类型、节头表的位置
.text 节	代码
.rodata 节	只读数据：printf的格式串、跳转表等
.data 节	数据/可读写：已初始化的全局和静态变量
.bss 节	未初始化的全局变量：未初始化/初始化为0的全局和静态变量，只有节头
.symtab 节	符号表：函数和全局/静态变量名，节名称和位置
.rel.text 节	可重定位代码：.text 节的可重定位信息，需要修改的指令地址
.rel.data 节	可重定位数据：.data 节的可重定位信息，需要修改的指针数据的地址
.debug 节	调试符号表：为符号调试提供的信息 (使用 gcc -g 编译生成)
节头表（Section header table）	每个节在文件中的偏移量、大小等

4.3.1 ELF头

图 4-2 ELF头的格式

 ELF头以一个16字节的幻数开头，标志出数据表示方式（补码小端序）、操作系统及其二进制接口（Unix-System V）等环境相关的内容。此外，还包括文件结构相关的信息，如段头表的起始位置，段头表中段的数量等。

4.2.3 节头表

节头表（section headers），用于描述文件中各个节（section）的属性和信息。每个节头表条目包含以下字段：

1. [Nr]：节头表中的条目序号。
2. Name：节的名称。
3. Type：节的类型，描述节的内容和用途。
4. Address：节在内存中的虚拟地址。
5. Offset：节在文件中的偏移量。
6. Size：节的大小（字节数）。
7. EntSize：每个条目的大小（字节数）。
8. Flags：标志位，描述节的属性和访问权限。
9. Link：链接字段，与其他节的关联。
10. Info：额外的信息字段，具体含义根据节类型而异。
11. Align：节在内存和文件中的对齐方式.

图 4-3 hello-o-elf.txt中的节头表

每个条目提供了关于相应节的详细信息，例如代码段（.text）、数据段（.data）、只读数据段（.rodata）、符号表（.symtab）等。这些信息对于链接器（linker）和调试器（debugger）等工具的操作和分析非常重要。

节头表的提供了一种结构化的方式来描述和组织可执行文件或目标文件的不同部分，使得编译器、链接器和调试器等工具能够准确地理解和操作文件的内容。

4.2.3 重定位节

汇编语言无法确定文件代码和数据该存放到何处，因此生成的.o文件中.text和.data的地址都是从零开始的，所以对于全局和静态符号引用，还无法生成有效的代码。因此，汇编器生成一个重定位条目表，记录所有这些符号的引用，并指示链接器在确定地址之后依照重定位条目修改这些引用。

重定位条目的基本内容如下：

表 4-2 重定位条目格式

内容	描述
偏移量（Offset）	指定了重定位入口的位置偏移量。
信息（Info）	提供了与重定位相关的附加信息。
类型（Type）	指定了重定位的类型，描述了需要进行何种类型的重定位。
符号值（Sym. Value）	重定位的目标符号的值（地址）。
符号名称（Sym. Name）	重定位的目标符号的名称。
添加项（Addend）	用于计算重定位的偏移量。

下图展示了hello.o中重定位节的解析结果：

图 4-4 hello-o-elf.txt中的重定位条目 

4.2.4 符号表

符号表是用于存储程序中定义和引用的符号信息的数据结构。每个条目对应一个符号。这些条目提供了有关程序中定义和引用的符号的重要信息，例如符号的类型、大小、绑定类型等。链接器可以根据符号表中的信息对符号进行解析、重定位和符号解析等操作。

下面展示了一个典型符号表条目的字段结构：

表 4-3 符号表的条目结构

条目字段	含义
Num	符号索引
Value	符号值
Size	符号大小
Type	符号类型（FILE/SECTION/FUNC...）
Bind	符号绑定（GLOBAL/LOCAL）
Vis	符号可见性
Ndx	符号所在段索引（对应于段头表）
Name	符号名称

下面是hello.o中符号表条目的解析：

图 4-5 hello-o-elf.txt中符号表条目的解析

符号表包含了一个空符号/文件名和.text .rodata的段名，此外还包括在文件中定义的main函数，以及在文件中声明但在外部定义的puts，exit，printf等函数。这些符号将在链接阶段被解析和重定位，那时符号表将提供有关符号类型和大小的信息。

4.4 Hello.o的结果解析

使用下列代码，可以将hello.o的代码反汇编到hello.asm文件中。

objdump -d -r hello.o > hello.asm

机器指令基本与汇编指令是一一对应，因为汇编本质上只是“助记符”指令。但是机器指令和汇编有以下方面的区别：

 图 4-6 汇编代码与机器代码的区别

1. mov、call指令会丢失后缀，例如0x72处的callq，0x77处的movl指令。
2. call指令的跳转地址都填写为0，这是因为对函数符号的解析尚未完成。
3. 分支、循环中的“标签”会丢失，条件跳转指令的目标变为pc相对的指令位置，例如0x86处的指令原本跳转的目标是.L4，汇编器不会保留这部分信息。

4.5 本章小结

汇编是程序编译的第三个阶段，在此，源代码文件第一次生成了二进制文件，其基本的文件结构也已经初具雏形。然而它还没有解析所有符号的定义和引用，也没有为各个节分配地址，因此还需要链接的过程才能成为可执行的程序。

---

第五章 链接

"No man is an island, entire of itself; every man is a piece of the continent."

"Meditation XVII" by John Donne

没有人是一座孤岛，完全无依无靠。每个人都像小小的泥土，连接成整个陆地

——《没有人是一座孤岛》，约翰·多恩

5.1 链接的概念与作用

链接是编译的第四个阶段，链接器（ld）将多个目标文件（或者可执行文件）中的符号引用与符号定义进行匹配和解析，并最终输出一个可执行文件。使用动态链接（ld-linux.so）可能会将这个步骤推迟到加载时。

链接器将所有目标文件中的符号引用与符号定义进行匹配，确定每个符号引用应该指向哪个符号定义。这涉及解析函数和变量的名称、类型、作用域等信息。在确定符号引用和定义之后，链接器会根据目标文件的布局信息，对符号引用的地址进行重定位，修正函数调用和全局变量访问的地址，确保它们在最终的可执行文件中指向正确的地址。

链接的作用是将分散的目标文件整合成一个可执行文件或者共享库。它使得不同模块之间能够相互调用和协作，实现模块化开发和代码复用。链接还可以优化程序的执行效率，例如通过函数的内联展开和代码的重排等操作来提高执行速度和减少空间占用。另外，链接还能够检测和解决符号冲突、重复定义等问题，确保程序的正确性和一致性。

5.2 在Ubuntu下链接的命令

链接的命令如下，不仅链接了hello.o，还将一系列必须的目标文件和动态库也一同链接。同时，还指定了动态链接器为/lib64/ld-linux-x86-64.so.2。

ld -o hello -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 
hello.o /usr/lib/x86_64-linux-gnu/libc.so 
/usr/lib/x86_64-linux-gnu/crtn.o

图 5-1 Ubuntu下链接的命令

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

运行下列命令：

readelf hello > hello-elf.txt -all

根据hello-elf.txt中的输出结果，可知hello是一个可加载可执行文件（EXEC）

 图 5-2 hello-elf.txt中的ELF头

整理程序头表（Program Headers）中的信息，可得各段信息如下：

表 5-1 程序段信息

类型	偏移量	虚拟地址	物理地址	文件大小	占用内存	权限	对齐
PHDR	0x40	0x400040	0x400040	0x2a0	0x2a0	R	8
INTERP	0x2e0	0x4002e0	0x4002e0	0x1c	0x1c	R	1
LOAD	0x0	0x400000	0x400000	0x5e0	0x5e0	R	4K
LOAD	0x1000	0x401000	0x401000	0x169	0x169	R E	4K
LOAD	0x2000	0x402000	0x402000	0xc8	0xc8	R	4K
LOAD	0x2e50	0x403e50	0x403e50	0x1fc	0x1fc	RW	4K
DYNAMIC	0x2e50	0x403e50	0x403e50	0x1a0	0x1a0	RW	8
NOTE	0x300	0x400300	0x400300	0x20	0x20	R	8
NOTE	0x320	0x400320	0x400320	0x20	0x20	R	4
GNU_PROPERTY	0x300	0x400300	0x400300	0x20	0x20	R	8
GNU_STACK	0x0	0x0	0x0	0x0	0x0	RW	16
GNU_RELRO	0x2e50	0x403e50	0x403e50	0x1b0	0x1b0	R	1

此外，链接器还生成了各节的信息，如下：

图 5-3 hello-elf.txt中的程序节表

5.4 hello的虚拟地址空间

使用edb加载hello，查看本进程的虚拟地址空间各段信息，得到其区域表如下：

图 5-4 hello的虚拟内存布局

5.4.1 只读文件头

这部分地址为0x400000-0x401000，对应程序头的第一个LOAD段（表5-1），主要包含ELF文件头、解释器路径、GNU相关信息等metadata。观察这部分内存地址，在对应段头处可以观察到响应信息，如程序头PHDR段对应的ELF MAGIC，INTERP段对应的动态链接器路径，GNU段和NOTE段中的GNU标记：

图 5-5 只读文件头内存

 剩余下是因为段要求4K对齐而分配的，没有使用。

5.4.2 只读代码段

这部分对应第二个LOAD，主要包含的就是原来文件中的只读代码段，即.text等。从中还可以看到我们的main函数：

图 5-6 只读代码段内存

5.4.3 只读数据段

这部分对应0x402000-0x403000，即程序头表中的第三个LOAD，同时也对应.rodata等节，包括printf中的字符串，还有其他的只读信息。

 图 5-7 只读数据段内存

5.4.4 读写数据段

这部分对应0x403000-0x405000，虽然hello中没有显式地引入读写数据，但是标准库中全局变量、GOT表等可读写数据都会保存在此处。例如节表中显示.data段的开始地址为0x404048，那么对应的内存处保存了相应的数据：

 图 5-8 读写数据段内存

5.4.5 动态链接库的映射区域

动态链接库映射到虚拟内存中，这部分是由加载器根据interp中的动态链接器路径的，位于0x00007f474fe9a000-0x00007f474fed6000，没有在程序头表或段表中标出对应条目。

5.4.4 栈区

栈区在程序头表中的GNU_STACK段中被设置为0地址，实际上则是由加载器控制并完成的envp/argv等参数的设置，因此也没有对应的条目。地址为0x00007ffc6a60d000-0x00007ffc6a62f000

5.5 链接的重定位过程分析

运行下列命令，可以看到链接后的文件反汇编结果：

objdump -d -r hello > hello-linked.asm

来看下面的代码示例：

 图 5-9 重定位过程

这个函数加载了一个字符串常量以调用printf，这个常量和printf分别使用了PC32和PLT32两种重定位方式。

对于PC32，我们看到这里的leaq已经有了正确的参数，0xf12(%rip)，这是因为目标地址0x40202e相对于%rip也就是0x40111c的位置恰好是0x0f12，于是lea指令的引用值就为0x12 0x0f 0x00 0x00（小端表示法）。

对于PLT32，我们看到这里printf并没有直接调用真正的地址（因为它被动态加载到了任意地址），而是调用了PLT表的地址，以便进入动态链接器内部修改相关数据，使得printf下次能正确的跳入其真正的函数体内。这里同样使用了%rip相对寻址的方式为CALL填写引用，plt相对于%rip的补码表示为0xffffff17，于是生成的跳转指令参数为0x17 0xff 0xff 0xff。

简而言之，对于重定位方式，连接器会根据符号的位置和寻址方式计算引用的值并填写。

5.6 hello的执行流程

在这里，我使用gdb工具，并用layout regs指令使其显示反汇编代码和其他信息。函数调用从_dl_start开始，而非通常认为的_start。因为执行程序的第一步是根据.interp节的内容完成动态链接。

图 5-10 gdb调试

为了导出所有的函数，我进行了以下操作：首先，启动gdb，运行一遍程序，这样它就会加载好动态库的符号。然后，用rbreak .命令给所有函数打上断点。然后，用set logging file output-gdb.txt将gdb内容输出到指定文件。然后重新运行程序，一直按continue，每次遇到断点gdb都会打印信息到指定文件。

得到输出后，用下面的脚本提取以Breakpoint开头的行，并从中取出函数调用的信息，输出到output-gdb-parsed.txt中：

#!/bin/bash



filename="output-gdb.txt"  # 替换为实际的文件名



while IFS= read -r line; do

    if [[ $line == Breakpoint* ]]; then

        content=$(echo "$line" | sed 's/.*,\(.*\)(.*/\1/')

        echo "$content"

    fi

done < "$filename"

然后，用下列命令将output-gdb-parsed.txt中的内容按字典顺序排序，并去掉重复行。

cat output-gdb-parsed.txt | sort | uniq > output-gdb-parsed-unique.txt

最终生成的内容如下所示，共150个函数调用，我相信这是最全的版本。

表 5-2 hello所有的函数调用

_IO_cleanup	_IO_default_setbuf	_IO_flush_all_lockp	_IO_new_do_write	_IO_new_file_overflow
_IO_new_file_setbuf	_IO_new_file_sync	_IO_new_file_write	_IO_new_file_xsputn	__GI__IO_default_xsputn
__GI__IO_doallocbuf	__GI__IO_file_doallocate	__GI__IO_file_stat	__GI__IO_puts	__GI__IO_setb
__GI___call_tls_dtors	__GI___close_nocancel	__GI___cxa_atexit	__GI___fstat64_nocancel	__GI___fstatat64_nocancel
__GI___getrandom	__GI___libc_cleanup_pop_restore	__GI___libc_cleanup_push_defer	__GI___libc_malloc	__GI___libc_write
__GI___open64_nocancel	__GI___overflow	__GI___pread64_nocancel	__GI___read_nocancel	__GI___sbrk
__GI___tunable_get_val	__GI___tunable_set_val	__GI___tunables_init	__GI__dl_allocate_tls_init	__GI__dl_debug_state
__GI__exit	__GI_exit	___pthread_mutex_lock	___pthread_mutex_unlock	__access
__brk	__glibc_morecore	__init_misc	__libc_scratch_buffer_set_array_size	__libc_start_call_main
__libc_start_main_impl	__minimal_calloc	__minimal_free	__minimal_malloc	__mmap64
__new_exitfn	__rtld_malloc_init_real	__rtld_malloc_init_stubs	__rtld_mutex_init	__run_exit_handlers
__sbrk	__sigjmp_save	__strdup	__tls_init_tp	__tls_pre_init_tp
__x86_cpu_features_ifunc	_dl_add_to_namespace_list	_dl_add_to_slotinfo	_dl_allocate_tls_storage	_dl_assign_tls_modid
_dl_audit_activity_map	_dl_audit_activity_nsid	_dl_audit_objclose	_dl_audit_objopen	_dl_audit_preinit
_dl_cache_libcmp	_dl_call_libc_early_init	_dl_catch_exception	_dl_cet_check	_dl_check_all_versions
_dl_check_map_versions	_dl_count_modids	_dl_debug_initialize	_dl_debug_update	_dl_determine_tlsoffset
_dl_discover_osversion	_dl_dst_count	_dl_find_object_from_map	_dl_find_object_init	_dl_fini
_dl_fixup	_dl_hwcaps_contains	_dl_hwcaps_split	_dl_hwcaps_split_masked	_dl_hwcaps_subdirs_active
_dl_important_hwcaps	_dl_init	_dl_init_paths	_dl_load_cache_lookup	_dl_lookup_direct
_dl_lookup_symbol_x	_dl_map_object	_dl_map_object_deps	_dl_map_object_from_fd	_dl_name_match_p
_dl_new_object	_dl_next_ld_env_entry	_dl_process_pt_gnu_property	_dl_receive_error	_dl_relocate_object
_dl_setup_hash	_dl_sort_maps	_dl_sort_maps_init	_dl_start	_dl_sysdep_read_whole_file
_dl_sysdep_start	_dl_sysdep_start_cleanup	_dl_tls_static_surplus_init	_dl_unload_cache	_dl_x86_init_cpu_features
_dlfo_process_initial	_dlfo_sort_mappings	_init_first	_int_malloc	call_init
check_match	check_stdfiles_vtables	dfs_traversal	dl_main	do_lookup_x
get_common_indices	handle_amd	init_cpu_features	init_tls	lookup_malloc_symbol
open_verify	openaux	ptmalloc_init	rtld_mutex_dummy	sysmalloc
tcache_init	update_active	version_check_doit	_init	puts@plt
exit@plt	_start	main	_fini	malloc@plt
ABS+0xa8720@plt	ABS+0xa89e0@plt	__tunable_get_val@plt	_dl_audit_preinit@plt	_dl_catch_exception@plt

5.7 Hello的动态链接分析

dl_init后，修改了GOT表（全局偏移量表），这是生成PIC（位置无关代码）的重要步骤：程序并不直接访问函数本身的位置，因为在静态链接时还不知道他们将被加载到何处。反之，程序通过一个称之为PLT表的结构进行动态链接的函数调用。该函数调用利用GOT进行跳转，因此，动态链接器会修改GOT，使得其指向一个合适的位置。

根据之前的节表（图5-3），我们知道got节的起始地址为0x403ff0，这是初始的got表：

 图 5-11 _dl_init前的got表和plt表

调用后，动态链接器会修改程序的got表：

 图 5-12 dl_init后的got表和plt表

可以看到，现在GOT表中的内容已经可以用于共享库的引用了。

5.8 本章小结

链接是编译的最后一步，程序完全转变为可执行文件。本章详细分析了ELF可执行文件的地址结构及其加载映射，对静态和动态链接的过程进行了简述，并详细列出了hello中的所有函数调用，包括动态链接器、标准库的函数调用。

---

第6章 hello进程管理

"The context in which a man lives determines how he will interpret his life." - from "To Kill a Mockingbird" by Harper Lee

一个人所处的上下文决定了他解释生活的方式——《杀死一只知更鸟》，哈珀·李

在此，我们在融入了盛大的世界

6.1 进程的概念与作用

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

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

（1）一个独立的逻辑控制流，它提供一个假象，好像我们的程序独占的使用处理器。

（2）一个私有的地址空间，它提供一个假象，好像我们的程序独占的使用内存系统。

进程被认为是和虚拟内存一样的，计算机中最伟大的思想之一。我认为这归功于他们实现了简单而可扩展的抽象：操作系统（在调度方面的工作）无非是维护每个进程的上下文并在适当的时机切换他们，然而正如我们所见，这个系统是一个高效、可靠的管理资源的方法。

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

shell即命令行解释器，如同它的名称一样，它是“kernel”内核外的一层“壳”，充当了“翻译官”的功能，让用户可以通过它调用系统提供的服务。一些应用软件页通过shell实现各种功能。

图 6-1 shell的作用

处理流程：（对于一个简易的shell而言，不进行标为蓝色的步骤）

1）从终端读入用户输入的命令。

2）进行一些语法展开和替换，如alias、大括号、通配符、转义字符....并且进行复合命令（&& || ；）和管道（|）的检查。如果遇到不匹配的单引号/双引号/反引号/大括号，则可能会重复1）。

1. 3）将输入的命令行按语句切分，获得一个job包含的所有命令；将每个命令展开后的字符串按空格切分，获得所有的参数。

4）检查第一个命令的第一个参数，如果它是一个内置命令就执行，否则就将其作为一个可执行文件处理。

5）fork一个子进程，在子进程里用4）获得的filename，3）获得的argv和从父进程继承的environ全局变量调用execve（或许应该是execvpe，它会自动从PATH变量中查找可执行文件）

6）如果参数中包含重定向（> >> <）内容，它还需要（在调用exec系列函数前）open对应的文件，并且将stdin或stdout用dup2映射到该文件，完成输入/输出的重定向/追加重定向。如果和下一条任务之间存在管道，可能还需要打开一条新的管道。

7）exec系列函数（execve，execvpe等）将会删除现有的虚拟内存区域，重新创建新的代码段、数据段、堆、栈，并将可执行文件的代码段和数据段映射到对应的虚拟内存区域，并用给定的argv和envp给main准备参数，然后将PC指向_start函数。_start会调用_libc_start_main，并最终调用main函数。

8）如果这是一个前台任务（行尾不包含&），就等待进程终止或停止，并将标记为前台作业，然后等待其运行完毕。如果这是一个后台进程（行尾包含&），就将其标记为后台作业，打印一条消息，然后直接返回读取下一个输入。

9）当该命令行中的任务完成时，shell获取他的返回状态，并按照&& （返回值成功则执行）||（上一个任务失败则执行） ;（无论如何都执行）的语意，执行下一个任务（回到5））。

10）当一个作业的所有任务都执行完毕，shell回收fork出去的子进程，并且为后台作业打印一条提示消息。

11）shell还要接收下面的信号，并做出对应的反应：

SIGINT（Ctrl+C）：转发给前台进程组

SIGSTP（Ctrl+Z）：转发给前台进程组

SIGQUIT（Ctrl+D）：退出登陆

6.3 Hello的fork进程创建过程

父进程通过调用fork（）函数来创建一个新的运行的子进程，新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的一份副本，包括代码和数据段、堆、共享库以及用户栈。父进程和子进程之间的最大区别是他们有不同的PID。

 fork（）函数调用一次，返回两次，父子进程并发执行，有着相同但是独立的地址空间，并且共享已经打开的文件和信号阻塞位等控制信息。

fork系统调用会原样复制父进程的PCB（进程控制块），并且为子进程新建一个内核栈，内核栈中的ax被设置为0，这也是为何子进程的fork返回0。然后，fork还将维护许多（我不了解的）内核数据结构用于控制子进程并维护父子关系。截止到目前，子进程都被标志为“不可调度”，当这些数据结构设置完成，系统使用getpid为子进程分配一个pid，并且将其标志为可以调度。当fork从内核态返回到用户态时，这个进程已经初始化完成的。

图 6-2 fork函数的实现流程

6.4 Hello的execve过程

当Shell准备好命令行切分得到的argv，并fork出了一个子进程，子进程就在返回后用shell解析得到的filename和argv调用execve。

execve 函数加载并运行可执行目标文件filename, 且带参数列表argv 和环境变量列表envp .只有当出现错误时,例如找不到filename, execve 才会返回到调用程序.所以,与fork 一次调用返回两次不同, execve 调用一次并从不返回。

execve调用驻留在内存中的被称为启动加载器的操作系统代码来执行程序,加载器删除子进程现有的虚拟内存段,并创建一组新的代码、数据、堆和栈段.新的栈和堆段被初始化为零,通过将虚拟地址空间中的页映射到可执行文件的页大小的片,新的代码和数据段被初始化为可执行文件中的内容.最后加载器设置PC指向_start地址,_start最终调用main函数。

6.5 Hello的进程执行

6.5.1 上下文、时间片与调度

一个进程的核心就在于上下文信息，基本上也就相当于PCB（进程控制块）的内容。上下文信息是操作系统内核重新启动一个挂起的进程所需要恢复的原来的状态。它由通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的信息构成。

时间片则是操作系统分配给进程的可用时间，更形式化的角度来说：一个进程执行它的控制流的一部分的每一时间段叫做时间片。

进程调度是操作系统根据时间片保存并恢复上下文信息的一种行为。在进程执行过程中，操作系统内核可以决定抢占当前进程，并重新开始一个先前被挂起的进程，这样的一种决策成为进程调度。进程调度=保存现场+恢复现场+转移控制：

①保存之前进程的上下文

②恢复要执行的新进程的上下文

③把控制转让给新恢复的进程完成上下文切换

6.5.2 用户模式、内核模式、特权级

用户模式和内核模式是Linux对4环特权模式的简化，简而言之从里到外提供了0、1、2、3四个环，ring0是超级权限，可以执行一切硬件支持的操作。ring1、2、3则是软件权限，不能使用部分特权指令。Linux没有使用ring1和ring2

 图 6-3 特权级

两种模式用一个寄存器来提供区分。用户模式权限较低，不允许执行特权指令，也不允许直接引用地址空间中内核区内的代码和数据；内核模式权限较高，可以执行任何命令，并且可以访问系统中的任何内存位置。

6.5.3 多道程序与系统调用造成的上下文切换

形式化地来说，导致上下文切换的唯一原因是异常处理，不过，我们还是从通常的应用场景来说：定时器的中断会导致上下文切换、系统调用会导致进程陷入内核模式进而切换上下文、外设的中断或程序引发的异常也会导致上下文切换，这里我们以hello为例分析前两种中断。

现代操作系统都支持多道程序，也就是同时运行多个进程，通过快速的在他们之间来回切换，让他们轮流使用处理器。物理控制流被划分成多个交错的逻辑控制流，存在并发执行的现象。一旦分配给某个进程的时间片到时，系统就根据调度算法选择下一个进程执行。

当开始运行hello时，内存为hello分配时间片，若然后在用户态下执行并保存上下文。如果在此期间内发生了异常或外设中断，则内核会休眠该进程，并在核心态中进行上下文切换，把控制权让给其他进程。如果时间片到，那么也会进行切换。

图 6-4进程上下文切换示意，图中两次切换原因是read系统调用和磁盘中断 

当hello进程执行到sleep。getchar等含有系统调用的函数时，这些系统调用会陷入内核，并且使得hello被抢占。

最后，hello在断断续续的执行中到了return，经过收尾后该进程被标志为已经终止，他的PCB暂时保留，并且等待父进程shell来回收其PCB占用的空间。

6.6 hello的异常与信号处理

异常可以分为中断、陷阱、故障和终止，在hello的运行中，会产生键盘中断、磁盘中断等，陷阱包括read/write/nanosleep/exit系统调用、故障包括缺页中断，正常情况下不包含终止。

这四类异常的处理方式见下图：

图 6-5 异常处理类别及方法

所有的这四种异常都会使得程序陷入内核，执行特定的异常处理程序，然后根据异常类型决定重启哪条指令或调用abort直接退出。

严格意义上来说，hello执行的时候，我们看到的并不是hello，而是等待hello执行完毕的shell。因此，所有的键盘信号都是发送给shell的，也是由shell处理的。除了那些通过kill指定发送给hello的信号。

表 10 Hello运行中可能出现的信号

信号名称	产生原因	处理方式
SIGHUP	终端断开连接或控制进程终止	忽略、终止或重新加载配置文件等
SIGINT	终端输入中断字符（通常是Ctrl+C）	转发给前台进程组，使得其终止
SIGQUIT	终端输入退出字符（通常是Ctrl+\）	转发给前台进程组，使得其终止并转储
SIGKILL	使用kill命令发送	无法被捕获、忽略或阻塞，直接终止进程
SIGCONT	调用bg或fg命令	恢复之前被暂停的进程
SIGCHLD	子进程状态改变	可以被捕获，用于处理子进程的退出状态或终止信号
SIGTSTP	终端挂起字符（通常是Ctrl+Z）	转发给前台进程组，使得其挂起（停止）。
SIGTTIN	后台进程尝试读取控制终端	挂起或忽略，取决于进程的后台/前台状态
SIGTTOU	后台进程尝试写入控制终端	挂起或忽略，取决于进程的后台/前台状态

下面展示了Ctrl+C发送SIGINT停止程序执行：

图 6-6 Ctrl+C停止程序

 下图展示了Ctrl+Z发送SIGTSTP挂起程序：

 图 6-7 Ctrl+Z挂起程序

下图展示了用bg命令发送SIGCONT使程序在后台恢复执行：

图 6-8 bg使程序恢复运行

下图展示了用fg命令发送SIGCONT并将程序调回前台：

图 6-9 fg将程序调回前台

下图展示了用ps -aux查看进程：

 图 6-10 ps -aux查看进程

下图展示了用KILL命令杀死进程：

图 6-11 kill杀死进程

下图展示了用KILL命令给停止中的进程发送SIGSEV，然后再让其运行，可以看到，由于进程处于停止状态，并没有立刻因为SIGSEV崩溃，而是在恢复运行之后崩溃：

 图 6-12 kill发送SIGSEV

6.7本章小结

进程是计算机系统智慧的又一结晶，是人们所想到的最有效的使用CPU的方式。得益于进程的概念，我们可以提供多道程序的并发执行，让CPU不必等待漫长的硬件中断时间。

为了实现进程的创建、执行、切换和控制，操作系统付出了很多。fork、execve负责创建和加载程序，内核调度算法执行进程的切换，异常处理程序对外设和鼓掌做出反应，而信号则给应用程序提供针对内核事务响应的渠道。

可以说，理解了进程，就理解了现代系统的效率核心。一个保证上下限、带有启发性的时间片分配和调度算法，将会赋予操作系统无比强大的力量。

---

第7章 hello的存储管理

"She danced like no one was watching, and it made the whole world stop and stare." - Unknown

“她跳舞时旁若无人，却让整个世界都停下来凝视。”——佚名

在此，我们醒来并进入生命的周期

7.1 hello的存储器地址空间

逻辑地址（Logical Address）：逻辑地址是由 CPU 生成的地址，用于访问内存。

线性地址（Linear Address）：线性地址是逻辑地址经过分段机制转换后得到的地址。逻辑地址被划分为段和偏移量，而线性地址则是将段和偏移量进行合并得到的地址。

在64位系统中，除了fs和gs外的段寄存器永远被视为0，fs和gs可以用于 提供线性地址计算的基址，但不用来做地址翻译。（见下图）

换言之，大部分情况下，64位的逻辑地址=线性地址=虚拟地址，这就是为什 么教材的地址翻译只讲了VA和PA，没有提到段。

在hello中，程序头表中各段的位置就是用偏移量和段基址址分别描述的，由 于结合了页式管理，往往分段都按照4K对齐。

 图 7-1 Intel手册提示64位下的段寄存器被忽略

虚拟地址（Virtual Address）：虚拟地址是进程在运行时使用的地址空间，对于64位Linux程序来说，虚拟地址就是线性地址。Hello中所有的地址全部都是虚拟地址。

物理地址（Physical Address）：物理地址是指实际的内存地址，它是内存中存储数据的真正位置。当Hello运行时，虚拟地址需要通过地址转换机制（如分页机制）将其转换为物理地址，以便在物理内存中访问实际的数据。

图 7-2 实模式下的地址空间变换示意

在长模式中，逻辑地址等于线性地址等于虚拟地址

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

在段式管理中，内存被划分为多个段，每个段都具有不同的属性和大小。逻辑地址由两个部分组成：段选择子（Segment Selector）和偏移量（Offset）。

段式管理是一种历经长期演化的技术。因此关于段式管理的很多描述都语焉不详，这是因为16位、32位、64位系统用完全不同的方式对待段式管理。

例如：16为实模式中简单地将段基址左移四位加偏移量就可以得到线性地址。对于当时16位数据总线和20位地址总线的体系（如8086）来说，分段是必须的。在32位保护模式中，段的高位被视为选择子，进行GDT表和LDT表的查找。在64位长模式中，虽然实际上完全放弃了段这个概念，但又总是以section等形式出现。

事实上，早在32位，linux就用平坦分段模式将段基址强制归零，名义上保留着寻址的过程，但实际上架空了段式管理。而在64位模式下，Intel禁用了段寄存器，彻底的终结了段式管理。

这部分需要同时学习过16、32、64位系统的知识才能有比较深入清晰的认识，为此，我结合8086汇编、32位操作系统、以及CSAPP教材，对参考文献[4]中的内容进行研究。给出了蓝色字体的论述和下面的举例描述。

下面是32 位（保护模式）中逻辑地址到线性地址的变换过程：

选择段描述符： 首先，根据段选择子（Segment Selector），从全局描述符表（Global Descriptor Table，GDT）或局部描述符表（Local Descriptor Table，LDT）中选择相应的段描述符。段描述符包含了段的基地址、大小、权限等信息。

计算线性地址： 使用选择的段描述符中的基地址和偏移量，计算出线性地址。线性地址的计算公式为：线性地址 = 段基地址 + 偏移量。

图 7-3 实模式下线性地址计算

 段限长检查： 在计算出线性地址后，对线性地址进行段限长检查，以确保地址不超过段的边界。如果线性地址超出了段的范围，则会触发段错误异常。

特权级检查： 在使用线性地址之前，还需要进行特权级检查，确保当前执行的代码或进程有权访问所选择的段。特权级检查是通过比较段描述符中的特权级（Descriptor Privilege Level，DPL）和当前特权级（Current Privilege Level，CPL）来实现的。

段式管理机制通过将内存划分为多个段，并为每个段分配不同的权限和属性，提供了更灵活和安全的内存管理方式。但是在64位系统上已经完全被页式管理取代了。

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

页式管理的核心思路是以页为单位，将虚拟内存缓存到物理内存中。虚拟页按照其状态可分为未缓存、已缓存、未分配。分别对应存储于磁盘、存储于物理内存、不存在的三种状态。

页表是 PTE（页表条目）的数组，每个 PTE 都有一个有效位和一个 n 位地址字段，有效位表明该虚拟页是否被缓存在 DRAM 中，地址字段表明 DRAM 中相应物理页的起始位置。如果有效位为0，它要么是一个磁盘位置（未缓存），要么是NULL（未分配）。

 图 7-4 物理内存作为虚拟内存的缓存

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

为了加速地址翻译，在 MMU 中设置一个 PTE 的缓存，称为 TLB（翻译后备缓冲器）。将VPN划分为TLBI和TLBT，进行组选择和行匹配，可以尝试从TLB中获取该虚拟页的PTE，如果获取失败则再计算其PTE地址，并从高速缓存/主存中获取。

 图 7-5 带TLB的MMU访存流程

为了减少常驻内存的页表，使用多级页表，这样不必为每个虚拟页都分配页表。多级页表的每一项都指向下一级页表的基址，VPN长为36位，正好划分为四段，用四级页表逐级查找页表进行匹配。

 图 7-6 四级页表翻译

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

得到物理地址后，CPU用同一个物理地址逐层访问缓存。每层缓存都将物理地址分为 CT（标记位）、CI(组索引) 和 CO（块偏移）。并在CI对应的组中，尝试匹配一个CT相同的有效行。如果成功，就是一个命中，缓存利用CO在块中找到对应的字，并将字返回给cpu，并且更新上层的缓存。如果不成功，就再向下层缓存发送查询这个字的请求。

 图 7-7 Core i7的三级Cache结构

7.6 hello进程fork时的内存映射

在 Shell 中运行后，通过 fork 创建的Hello拥有Shell相同的区域结构、页表等的一份副本，同时Hello也可以访问任何Shell已经打开的文件（包括stdin，stdout，stderr）。当 fork 在Hello中返回时，Hello现在的虚拟内存刚好和Shell调用 fork 时的虚拟内存相同。

当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间。例如当Hello进一步调用execve时修改栈区，就会触发一次写时复制。通过这种技术，虚拟内存将复制延迟到了最后可能的时刻。

 图 7-8 fork时的内存映射-写时复制

7.7 hello进程execve时的内存映射

execve() 系统调用借助内核代码启动加载器，在当前进程中加载并运行可执行目标文件 hello 中的程序，使我们的main函数代替了原来的main函数，运行在全新的虚拟内存空间中。加载包括以下几个步骤：

图 7-9 execve的内存映射

1. 删除已存在的用户区域，删除当前进程虚拟地址的用户部分中的已存在的区域结构。
2. 映射私有区域，为新程序的代码、数据、bss 和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为 hello 文件中的 .text 和 .data 区，bss 区域是请求二进制零的，映射到匿名文件，其大小包含在 hello 中，栈和堆地址也是请求二进制零的，初始长度为零。
3. 映射共享区域， hello 程序与共享对象 libc.so 链接，libc.so 是动态链接到这个程序中的，然后再映射到用户虚拟地址空间中的共享区域内。
4. 设置程序计数器（PC），execve() 做的最后一件事情就是设置当前进程上下文的程序计数器，使之指向代码区域的入口点（_start函数）。

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

缺页故障的处理比较特殊，因为它是系统缓存中唯一需要软硬件配合的，这是因为它处于缓存的较低级，不命中开销极大，需要非常复杂的替换算法。

当试图访问一个不存在的页时，由于PTE中有效位为0，指令触发一次缺页异常，陷入内核的异常处理程序中，如下图：

 图 7-10 缺页处理-进程视角

异常处理程序做以下事情：

首先，它选择一个物理区域放置新的页，如果内存已满，就需要替换一个页。在这里，我们假设访问的页为VP3，而VP4被替换。

接下来，异常处理程序会检查VP4是否被修改，如果被修改过就将它写回磁盘。然后将VP3从磁盘中调入到物理内存，并修改对应的页表项。

 图 7-11 缺页处理 （左）选择牺牲页 （右）调入新页，换出旧页，更新页表

当缺页处理返回时，系统会试着重新执行引发故障的指令，现在要访问的内容已经被正确地加载到物理内存中了。因此指令将正确执行。

7.9动态存储分配管理

printf会调用malloc，为FILE*分配读写内部缓冲区。下面简述了动态内存管理的基本方法与策略。

7.9.1 动态内存管理的基本方法

动态内存管理是指在程序运行时，根据需要动态分配和释放内存的过程。它允许程序在运行时根据实际需求来获取所需的内存空间，提供了灵活性和效率。通常在C语言中使用malloc/free的动态内存分配器进行动态内存申请和释放。

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。分配器将堆视为一组大小不同的，具有连续地址的块的集合来维护。将块标记为两种，已分配的块供应用程序使用，空闲块用来分配。

7.9.2 隐式空闲链表管理

在隐式空闲链表中，空闲块的信息被嵌入到已分配的内存块中。每个内存块都包含头部信息，记录块的大小和是否被分配的标志位。并且还包含一个脚部用于快速进行合并。当一个内存块被释放时，相邻的空闲块可以合并在一起形成更大的空闲块。在分配内存时，遍历内存块，找到满足需求的空闲块进行分配。

寻找一个适配的块有很多种算法，包括：

1. 首次适应（First Fit）：从空闲内存块中找到第一个满足需求的空闲块进行分配。该策略简单快速，但可能会产生内存碎片问题。
2. 最佳适应（Best Fit）：在空闲内存块中找到最小的满足需求的空闲块进行分配。更好地利用内存空间，但可能会增加搜索时间。
3. 最差适应（Worst Fit）：在空闲内存块中找到最大的满足需求的空闲块进行分配。可以减少内存碎片问题，但可能会导致较大的内部碎片。

隐式空闲链表不需要额外的数据结构来维护空闲块的信息，因此在内存开销上相对较小。典型的空闲块的结构如下：

 图 7-12 隐式空闲链表的空闲块结构

脚部与头部均为 4 个字节，用来存储块的大小，同时由于块双字对齐，块大小的 3 个最低位可以用来做flag指明这个块是否空闲，0为空闲，1 为已分配。

7.9.3 显式空闲链表管理

真实的操作系统实际上使用的是显示空闲链表管理。在显式空闲链表中，使用一个数据结构（通常是链表数组）来显式地维护已经释放的空闲内存块的信息。

每个空闲块都包含头部信息，用于记录块的大小和指向下一个空闲块的指针。当需要分配内存时，可以遍历空闲链表，找到满足需求的空闲块进行分配。当内存块被释放时，将其添加到空闲链表中，维护链表的有序性。

显示列表可以采取称为“快速适应”的适配方法来寻找空闲块：快速适应（Quick Fit）将内存块分成多个空闲链表，每个链表内的空闲块大小都是一定的，比如链表a中块都是1~8字节，链表b中块都是8~256字节...这样可以加快搜索速度，并提供更好的空间利用和内存分配效率。

还有一种分离适配的技术进一步提升显示链表快速适配的时空效率：分配完一个块后将这个块进行分割，并将剩下的块插入到适当大小类的空闲链表中。C 标准库的malloc 就用了这种方法以追求时空效率平衡。

7.10本章小结

进程运行时，需要对内存进行管理。虚拟内存是操作系统对实际的存储器的抽象，以一种无比优雅的方式完成了简洁、安全、高效的地址管理。

虚拟内存的核心思想就是地址翻译，在这个过程中，涉及到段式页式等历史遗留问题，涉及到页表TLB等加速技术，最终呈现出来的是一套复杂而完善的管理体系，将物理内存与进程解耦。

虚拟内存的核心功能就是给进程提供一个存储空间的抽象，为此，fork/execve等系统调用在幕后（内核态）完成了许多对虚拟地址的操作，其中的写时复制技术更是充分体现了计算机设计的智慧。

动态内存管理事实上已经和虚拟内存系统没有太大关系了，它是建立在虚拟内存系统之上的应用层设施。但是因为和内存有关所以也一并在这里谈论。这部分内容帮我们了解动态内存分配的原理和技巧，以及如何避免动态内存时的错误。

最后，附上程序运行时的虚拟内存示意图：

图 7-13 进程的虚拟内存示意

---

第8章 hello的IO管理

在此，我们与世界上的存在交流

8.1 Linux的IO设备管理方法

在Unix中，设备可以通过文件来进行模型化和管理。这种设备管理方式被称为Unix I/O接口或设备文件接口。它基于Unix哲学中的"一切皆文件"的概念，将设备抽象为文件，并通过文件I/O操作进行设备的读取和写入。

Unix I/O接口的核心是通过文件描述符来表示设备。每个设备被视为一个文件，可以通过打开相应的设备文件来获取文件描述符。设备文件的命名通常位于/dev目录下，例如/dev/tty表示终端设备，/dev/sda表示硬盘设备。此外，网络桃姐字页使用Unix I/O接口。

Unix I/O接口的优势是简单统一，它将设备的操作与文件I/O操作统一起来，使得对设备的读写可以像对待文件一样进行处理。这种模型化的设备管理方式提供了方便而灵活的方式来与设备进行交互，并促进了Unix系统的可扩展性和兼容性。

8.2 简述Unix IO接口及其函数

UnixIO接口包括打开、读取、写入、控制、关闭文件等。注意这些函数都是无缓冲的。虽然指定了读/写的长度，但不能保证一定能完成这么多字节的IO，尤其是对网络套接字。

表 11 Unix IO接口函数

操作	名称	参数	作用
打开设备	open()	设备文件路径，标志，打开模式	打开设备文件，获取与设备关联的文件描述符
读取设备	read()	文件描述符，读取缓冲区,要读取的长度	从设备中读取数据，存储到指定的缓冲区中
写入设备	write()	文件描述符，写缓冲区，要写入的长度	将数据写入设备的相应位置
控制设备	ioctl()	文件描述符，控制命令等参数	向设备发送控制命令，用于设备的配置、状态查询和特定操作
关闭设备	close()	文件描述符	关闭设备文件，释放相关资源

8.3 printf的实现分析

https://www.cnblogs.com/pianist/p/3315801.html，也就是大作业报告模板中给出的链接。这篇文章中的代码都是D:/~/funny/kernel中的，也就是说，这其实是作者自己写的一个玩具程序，并不是真正的标准库。

我下载了了glibc2.5.5版本的标准库，并对其中的printf进行了分析。真正的printf非常的复杂精致。下面的黑色内容基于博客，同时用蓝色字体指出其不足的地方。

printf函数内容如下：

 图 8-1 printf函数（funny版本）

它针对变长参数列表进行了解析。这种解析方式是错误的。首先，解析变长参数应该使用va_start宏。其次，这行代码将sizeof(char*)硬编码为4，作者很自信的说“sizeof的结果是个固定值，在我的机器上为4”。但事实上，这行代码仅能在32位机器上运行，因为64位机器中应该为8.下面是标准库中的printf：

 图 8-2 printf（标准库版本）

然后，调用了vsprintf来进行格式化接受确定输出格式的格式字符串fmt。用格式字符串对个数变化的参数进行格式化，产生格式化输出。funny版本的缓冲区长度为256，超出长度就会导致失败。库函数中的vfprintf有上千行，包含了极为复杂的宏定义，进行格式化、长度计算、栈上动态内存管理。这才实现了丰富的功能。

vsprintf代码如下：

 图 8-3 vsprintf函数（funny版本）

然后，这里调用了write函数，把这个字符串打印出来。注意在funny版本中，没有传递文件描述符的选项。从函数原型就可以看出来，这里的write不是Unix标准IO，并且printf不会直接调用write，因为标准库提供的IO是带缓冲区的，printf直接通过vfprintf，将格式化后的字符串（逐步地，过程中进行长度检测和换行检测地）拷贝到缓冲区中，并根据无缓冲/行缓冲/全缓冲的缓冲策略，决定是否要进行fflush以便输出缓冲区。

下图展示了标准库只有无缓冲，或行缓冲且正在输入’\n’时，才会调用_IO_write_ptr。 

图 8-4 标准库中处理缓冲的相关内容

write函数通过汇编指令准备进行系统调用（32位上int 0x80进行中断， 64位上通过syscall指令），并且将系统调用号及相关参数保存在寄存器中。

接下来，内核程序会调用对应的驱动程序：

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

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

8.4 getchar的实现分析

敲击键盘时，会产生一个键盘中断。系统进入内核态处理键盘中断处理子程序。键盘驱动反馈接受按键扫描码，再转成ascii码，保存到系统的标准输入缓冲区。

getchar等调用最终会调用read系统函数，这个系统调用读取内部的按键ascii码。默认情况下，标准输入流的输入的缓冲区是行缓冲的，因此要等到一个回车键才会真正写入这些内容。当这些内容到达时，read就从阻塞中返回了，并且提供了一个字节的字符给getchar。

8.5本章小结

任何程序的出发点和落脚点都是读取用户的输入并给出输出，而文本是最基本的形态。本章概述了Linux管理IO设备的方法和函数，并以printf和getchar为例给出了比较具体的分析。其中printf还结合了标准库的代码和博客中提供的代码进行对比，指出了博客中的代码的不足。

---

结论

Hello world程序自编写到运行，大致经过了以下步骤：

1. 程序的输入和编码：字符输入进文本编辑器，形成的.c文件以字符编码的形式存储在磁盘中。
2. 程序的编译：通过编译工具链，.c文件经过预处理、汇编、编译、链接四个步骤，形成一个可执行文件。
3. 程序的启动：通过shell，程序员指定可执行文件的路径，shell通过fork分出子进程用于运行程序。
4. 程序的加载：在fork中使用execve删除子进程原来的虚拟内存空间区域，用mmap将可执行文件的代码段和数据段映射到新创建的内存空间区域。加载器还调用动态链接器linux-ld.so将程序完全链接。
5. 程序的运行（指令层面）：可执行文件的代码段被翻译为机器指令，CPU不断地取指执行，使用流水线等技术加快取指执行的速度。
6. 程序的运行（访存层面）：CPU产生的每一个地址，都经过内存管理单元MMU进行地址翻译，它将虚拟地址经由页表转换为物理地址，然后CPU使用同一个物理地址逐级访问Cache获取数据。
7. 程序的运行（进程层面）：程序运行在fork出的子进程上，从程序转换为进程（P2P）。与其他许多进程一起受操作系统的调度，不断进行上下文的切换。异常处理和信号机制在此层您发挥作用
8. 程序的运行（IO层面）：程序通过IO库函数进行输入输出，这些函数最终又进行系统调用。中间涉及到读写缓冲区，键盘和显示屏的驱动方法等。
9. 程序的结束：当进程结束时，其控制块（PCB）并没有被销毁，直到它的父进程（shell）用waitpid将它回收，或者父进程也被终止，从而导致它被守护进程（init）回收。程序加载前不占用内存空间，回收后也不保留任何信息，这就是020。

我认为，计算机系统的核心设计就在于操作系统、编程语言。其中，虚拟内存、进程的设计又是核心的核心。操作系统给了我们管理软件的方法，编程语言给了我们管理软件的能力。虚拟内存和进程联合，实现了对处理器的高度抽象，为安全、简单、高效的系统发挥了重大作用，这也是本文的四个关键词：操作系统、编译、虚拟内存、进程。

希望我以后能在计算机系统的科研道路上走的远一些、深一些，看一看这片美妙神奇的世界上还有何种精彩的风景。我目前对操作系统的调度算法和虚拟内存的页表设计比较感兴趣。

首先，我研究过linux0.11的时间片调度算法，那是一个小巧精致的启发式调度算法，带有自适应IO敏感型任务，控制时间片上下限使得不出现饿死进程的优点。不过，我也听说linux之所以和windows相比流畅度差很多，就是因为调度算法和优先级的问题。在windows上，会根据外设种类给进程附加额外权值，甚至贴心的给声卡准备了比显卡更高的权值（人类对声音信息更敏感），这也就使得windows的运行体验整体更加丝滑流畅。

同样的例子还有基于Android（Linux）和基于iOS的苹果，苹果系统之所以可以以更低的内存做到更高的系统流畅度，就得益于贯通计算机体系结构层面的，软件和硬件相结合的，对操作系统的优化。

至于页表，我们都知道页面是现在操作系统的常用缓存中，最大的一个单位，也是不命中惩罚最高的一个单位。由于每个虚拟地址都需要翻译，访问页表的操作也是最频繁的。那么有没有办法让页表的访问更快一点？我们知道，多级线性表其实是一个时空效率相对较高，但都没有达到极限的方法。有没有诸如Hash一类的方法，能够进一步的提升地址翻译的速度？在这方面，我已经阅读乐一些论文，比如结合TLB进行的页表加速读取，比如自映射的页表设计。相关的成果都发表于计算机系统和操作系统的顶级会议上，希望我未来能够继续深入的走进这一点。

最后的最后，我想说非常感谢这门课程。感谢我的任课老师一直以来的耐心教导和考前的答疑。感谢助教一学期以来的照顾。对于这门课程，我已经尽了我最大的投入。虽然不好说当下的结果如何，但我相信我一定会在未来受益匪浅。

那么这就是2023年春季计算机系统基础课程的课程报告了。

---

附件

附表 中间结果

文件名	内容
hello	可执行文件
hello.asm	目标文件的反汇编信息
hello.c	源文件
hello.i	预处理后文件
hello.o	可重定位目标文件
hello.s	汇编后文件
hello - elf.txt	可执行文件的readelf信息
hello - linked.asm	可执行文件的反汇编信息
hello - o - elf.txt	目标文件的readelf信息
output - gdb.txt	保存了所有函数调用的记录
output - gdb - parsed.txt	从上述文件中提取的函数调用记录
output - gdb - parsed - unique.txt	将上述文件内容排序并去掉重复的记录
parse - output - gdb.sh	从output - gdb.txt生成output - gdb - parsed.txt的脚本

---

参考文献

1.  Randal E.Bryant / David O'Hallaron. 深入理解计算机系统[M]. 北京：机械工业出版社，2016
2. 俞甲子，石凡，潘爱民. 程序员的自我修养[M]. 电子工业出版社，2009
3. William Stallings. 操作系统——精髓与设计[M]. 机械工业出版社，2010
4. fork系统调用详解https://zhuanlan.zhihu.com/p/422928238
5. 现代操作系统内存管理到底是分段还是分页，段寄存器还有用吗？[OL] 现代操作系统内存管理到底是分段还是分页，段寄存器还有用吗？ - 知乎
6. gdb - 列出所有函数调用[OL] https://www.cnblogs.com/zengkefu/p/5571500.html