csapp读书笔记part2

前言

本部分包含《深入理解计算机系统》第三版第二部分的内容,主要就是程序是如何运行起来的一个工程详解。

第七章 链接

简单来说,链接(linking)就是把代码和数据组合成一个文件的过程。链接可以发生在编译的时候、被加载到内存的时候,还可以发生在运行的时候。

7.1 编译器驱动程序

其实就是预处理器+编译器+汇编器+链接器的组合而已。

具体步骤如下:

  1. 首先使用cpp,将所有的头文件和一些预定义的东西处理一下,生成.i文件。
  2. 使用编译器将.i文件翻译成汇编语言.s。
  3. 使用as汇编器,把汇编语言变成一个可重定位目标文件,即俗称的.o文件。
  4. 通过链接器ld,把这些可重定位目标文件链接到一起,生成可执行文件。
  5. 最后如果要在shell中执行,会通过一个叫加载器的函数,该函数把对应的代码和数据都复制到内存中,并将控制权转移给程序。

7.2 静态链接

链接器简单来说就是把这些.o文件作为输入,并且生成一个能够完全链接的、可以加载和运行的可执行目标文件。链接器最为重要的是两个任务:

  • 符号解析。每个符号会对应一个函数、一个全局变量或者是一个静态变量,符号解析的目的就是把每个符号引用和一个符号定义给关联起来。
  • 重定位。由于之前的编译器和汇编器,其实它们生成的代码都是从虚拟地址0开始的,链接器则需要把符号定义和一个内存位置进行关联,这样就能重定位这些节。同时由于上面已经进行了符号解析,所以也就是符号引用也能指向内存的虚拟地址的位置了。

其实这些.o结尾的文件,就是一堆堆的块的集合,而这些块要么包含程序的代码,要么包含程序的数据,要么包含能够引导链接器和加载器的数据结构。

7.3 目标文件

目标文件有三种形式:

  • 可重定位目标文件。包含了二进制的代码以及数据。.o文件就是这类。
  • 可执行目标文件。也是包含了二进制的代码和数据,但是它可以被执行复制进内存进行执行,但是上面的那个不行,一般来说最终生成的程序就是这类。
  • 共享目标文件。特殊的可重定位目标文件,可以在加载或者运行时被动态加载进内存并且链接。

7.4 可重定位目标文件

就是7.3中介绍的第一种文件,它是如此的重要导致用了一个篇章来介绍它。

image-20201024213054997
  • ELF头部存放的是ELF头部大小、机器类型(x86-64)、节头部表的偏移。
  • .text:已经编译的机器代码
  • .rodata:只读数据,比如printf中的字符串。
  • .data:已经初始化的全局和静态变量。
  • .bss:未初始化的全局和静态变量。注意!局部变量是在栈里面的。而且在实际文件中不占空间,因为没有必要,直接在内存中初始化为0就可以了,所以如果直接初始化一个全局变量为0,其实也是放在.bss里面的。
  • .symtab:符号表,存放在程序中定义和引用的函数全局变量的信息。并不包含局部变量。
  • .rel.text:一个.text中位置的列表。
  • .rel.data:全局变量的重定位信息。
  • .debug:调试符号表。
  • .line:行号和.text中机器指令的映射。
  • .strtab:字符串表。

7.5 符号和符号表

每个可重定位目标文件中都会有一个符号表(见上图),这个表格里面有三种符号:

  • 本文件定义的,并且能够被其他文件所引用的全局符号。
  • 在其他文件中定义,但是能被本文件引用的全局符号。
  • 只有本文件能引用的局部符号。

直接用readelf -l xxx.o就可以看到这张符号表。

7.6 符号解析

符号解析简单来说就是将每一个引用和符号表里面的符号定义关联起来。

7.6.1 多重定义的全局符号

假设需要在某个文件中用到一个函数(函数也是符号),如果另外两个文件里也有相同的定义,这怎么处理?

linux对每个全局符号(主要是函数和有初始值的全局变量),都定义了它是强还是弱。所以只要满足下面规则,就不会有选择问题了:

  • 不允许有多个同名的强符号。
  • 如果有一个强符号和多个弱符号同名,那么使用强符号。
  • 如果只有多个同名的弱符号,那么任意选一个就可以了。

最常见的强符号就是main,这也保证了只能有一个main函数。上面的规则虽然可以确保不会出现编译问题,但是可能会出现违背程序员意愿的问题,所以比较推荐使用gcc -fno-common这个选项,能够告诉链接器遇到多重定义的全局符号就报错,而不是继续运行。

7.6.2 静态库链接

静态库的存在就是把这些.o文件做一个集合,这样可以方便程序员调用。

最常见的静态链接库是libc.a,在ubuntu18中位于/usr/lib/x86_64-linux-gnu/libc.a,它里面定义了printfscanf等函数。同样还有libm.a里面定义了一些数学函数。

所以其实可以完全不使用#include<stdio.h>来使用printf的,可以在编译的时候-L /usr/lib/x86_64-linux-gnu/libc.a就可以了(其实是默认增加这个静态库的,所以其实是可以不写的)。

实际中只会使用静态库中被使用到的那些函数。

7.6.3 如何使用静态库

链接器是通过从左到右的顺序,按照文件出现在命令行中的顺序,来进行扫描的。

而在扫描的过程中,链接器维护一个可重定位目标文件的集合E,一个未解析的符号集合U,一个在已经定义过了的符号集合D,显然一开始三个都是空集。

然后扫描开始,如果碰到的文件是需要目标文件,那么就加入E,并且也需要修改U和D;如果是类似.o或者.a文件,那么就需要看看这个文件里面,有没有U里面的符号,如果有那么就需要把这个函数加入到E里面,说明有这个函数的实现。对于每个函数都进行这个过程。

当处理完所有的文件,如果U里面还有,说明还有符号没解析,那当然是失败了。

可以看到这个算法中,顺序是非常重要的。一个简单的原则就是先给出定义的,然后再给出实现的(也就是库文件需要放后面)

7.7 重定位

现在已经能够知道符号引用和符号定义的关联关系了。那么只需要把所有相同类型的section合并成一个即可。然后把新的内存地址赋值给新聚合的section,就完成了对虚拟内存地址的分配了,此时每条指令,每个全局变量和函数都有对应的唯一的内存地址了。

7.7.1 重定位条目

当汇编器(注意不是链接器)在生成.o文件的时候,它是不知道最后这些函数和全局变量应该被放到哪里的,因为这里面可能会有对别的文件的引用,所以它不得不生成一个重定位条目,也就是上面的.rel开头的这两个,分别保存了代码和数据。

这样当链接器工作的时候,就可以知道在合并的时候,怎么样进行修改。

重定位相关的信息可以通过readelf -r xxx.o进行查看,其中有两类地址,一类是相对地址,另外一类是绝对地址。

7.7.2 重定位符号引用

相关算法:

image-20201027120523007

最外层的函数相当于对应的每个节section,然后是对应每个条目entry。

首先先看看在main.o中,执行的语句是int val = sum(array, 2);,可以看到把常数2放到了esi中,然后

image-20201027135936853

可以看到绿色框中就是对这些地址的引用,通过算法就可以在link的时候算出最终的虚拟内存地址,并不再进行改变。

7.8 可执行文件

其实可执行文件(姑且就叫exe文件好了…)和可重定位文件(.o)结构非常类似,只是还加了一个程序的.init的section而已。而在这个段里面,会有对应的小函数叫_init,程序一开始执行就会调用这个,而且因为可执行文件已经完全链接了,所以不在需要rel节了。

7.9 加载可执行目标文件

直接在命令行进行输入,然后内存中有一个叫加载器(loader)的东西就会来运行可执行文件,加载器实际上是通过execve来调用的。加载器会把代码段和数据段从磁盘中加载到内存中,并且跳转到_start中,也就是把控制权交给可执行文件。接着_start会调用__libc_start_main,它会进行环境的初始化,并且执行真正的main函数。

这一部分会在下面一章中进行介绍。

7.10 动态链接库

之前说了printfscanf其实是可以在静态链接库中找到的,但是实际上一般不推荐使用静态链接库来作为实现,这样的话每个程序几乎都会带上这些代码,会显得非常臃肿——于是就有了动态链接库。动态链接库的思想很简单,就是它可以被加载到内存的任何地址中,然后在内存中的程序能和动态链接库进行链接,这个链接过程是由一个叫动态链接器的程序来做的。

当加载器加载可执行程序到内存的时候,会发现可执行程序包含了一个.interp的节,这个里面会有动态链接器的路径,然后由这个动态链接器来完成所有的重定位工作,一旦完成之后,就把控制权转交给应用程序,并且此时共享库的路径就无法再发生改变了。

7.11 从应用程序中加载和连接共享库

我们实际中可以通过使用linux系统提供的接口来实现自己的应用程序在运行时加载和链接共享库。

java中也有一个概念叫java本地接口(Java Native Interface,JNI技术),它能够让java调用本地的C/C++函数,其实底层就是利用了dlopen这个接口来动态链接一个共享库,然后调用对应的函数。

7.12 位置无关代码

这里需要考虑如何让多个进程能够共享一个程序的副本呢?现代系统使用的是一项叫做位置无关代码(Position-Independent Code,PIC)的技术。

7.13 库打桩技术

跳过。个人感觉非常类似于AOP技术。

7.14 工具

在linux平台下可以使用sudo apt install binutils安装对目标文件

  • ar:创建静态库,能够对静态库进行成员的插入、删除和列出所有的.o文件。
  • strings:列出一个目标文件中所有可以打印的字符串。
  • strip:删除符号表信息
  • nm:列出目标文件中符号表定义的符号
  • size:列出节的名字和大小
  • readelf:显示目标文件的完整结构
  • objdump:基本用来做反汇编,不过功能强大。
  • ldd:列出一个可执行文件在运行时需要的共享库。

第八章 异常控制流

最简单的CPU模型就是通过使用平滑的控制流,即内存中相邻的指令一条条运行下去,可能会在运行的时候遇到jmp或者是call来进行跳转。但是上面所说的其实都是在程序中,也就是程序其实是能操控的。但是如果一个定时器发出了一个信号,或者是一个网络中的包到达了机器,也可能是子进程终止的时候父进程需要得到通知,这个都是需要解决的,而且都无法通过这些指令序列来完成。

现代操作系统是通过使控制流发生突变来对这些情况作出反应,这些突变就叫做异常控制流(Exceptional Control Flow,ECF),而这个ECF则是在每个层次都有:

  • 硬件层次:例如时钟会每隔固定的时间进行一次硬件的操作。
  • 操作系统:内核会通过上下文切换把控制权从一个进程转移到另外一个进程。
  • 应用层:利用信号完成信息的传递。

当然作为java程序员,可能会和java中的try/catch的异常捕获机制进行混淆,严格上来说,java中的异常,其实是一种非本地跳转(即它没有遵守相应的栈规则),而非本地跳转是一种应用层的ECF,在C里面是通过setjmp和longjmp来实现的。

8.1 异常

异常一部分由硬件实现,一部分由软件来实现。简单来说,当处理器状态发生变化的时候,我们说一个事件发生了。而在任何情况下,只要处理器检测到有事件发生了,就会通过异常表来进行一个函数调用处理异常。当异常处理完成之后,可能会把控制权返回给当前指令、下一条指令或者直接终止被中断的程序。

8.1.1 异常处理

每一种异常都有唯一的一个非负标号,而这些标号一部分是CPU的设计者分配的(除以零、缺页、溢出等异常),另外一部分是操作系统分配的(IO、系统调用等)。这里需要注意,就算是硬件触发的异常,也是由软件来进行处理的。

而异常表则是在CPU加电的时候进行初始化的,可以理解为就是一个异常号 - 异常处理程序的 kv表格,而这个表格的地址则是被存放在了一个特殊的寄存器里面。异常处理程序是运行在内核模式之下的,拥有完全的访问权限。

8.1.2 异常的类别

类别 原因 异步/同步 返回行为
中断(interrupt) 来自IO设备的信号,属于硬件 异步 总是返回下一条指令
陷阱(trap) 有意发生的异常,属于软件,有人称之为软中断 同步 总是返回下一条指令
故障 可恢复的错误 同步 可能返回当前指令
终止 不可恢复的错误 同步 不返回
中断

显然中断是由于CPU外部的设备引起的,一般都是IO设备,而这个中断也不是由任何的指令引起的,而是硬件引起的。具体的过程是这样子的,外部的这些IO设备在完成任务之后,会给CPU的引脚发送一个信号(比如一个高电平),并会把异常号放到总线上去,这个异常号就标识了引起中断的设备。CPU会执行完当前正在执行的这条指令,然后去检查一下,那么CPU自然是能够知道自己的引脚电平发生了变化,于是就去总线上读取了异常号,进行对应的处理,处理完成之后返回到下一条指令继续执行。

陷阱和系统调用

陷阱不同于中断,它是执行一条指令的结果。陷阱最最重要的,就是在用户程序和系统内核之间提供了一个接口,也就是我们俗称的系统调用。在64位系统中,如果用户程序希望执行系统调用,那么可以执行syscall x,其中的x是系统调用号;而在32位系统中则是通过int 0x80来陷入内核。

故障

一个典型的故障就是缺页中断,当发生缺页中断的时候,会启动对应的处理程序去加载页到内存中,并且重新执行当前的指令

当然如果发现这个故障处理不了,那么就需要使用abort来终止应用程序了。

终止

当发生致命硬件错误的时候,就不会把控制返回给应用程序了,而是直接调用abort来终止程序。

8.1.3 操作系统中的异常

异常一共有256种,其中的0~31是由Intel架构师来设计的,而32~255则是由操作系统定义的。

linux中的故障和终止
  • 除法错误。比如除零错误,这个会导致shell报告浮点异常。
  • 一般保护故障。比如程序试图往只读段里写数据,会发生段错误。
系统调用

C程序使用了一个叫syscall的函数,可以直接使用任何的系统调用。当然Libc同时也提供了一组包装函数,非常实用。

在x86-64中,系统调用是通过syscall的陷阱指令来做的,而且所有的参数都是通过寄存器传递的(不要担心不够,六个参数足以对付所有的系统调用了),而系统调用的号码则是通过rax进行传递的

8.2 进程

要搞清楚进程,首先需要了解什么是进程的上下文context。上下文应该包括,存放在内存中的程序的代码、数据、堆、栈,通用寄存器、程序计数器、环境变量(其实环境变量应该算栈)以及打开的文件的集合。所以简单点说,其实上下文就包含三样东西:内存地址空间、CPU状态和打开的文件(但是打开的文件其实也在内存里面的)。

8.2.1 逻辑控制流

emm 没什么可记录的。

8.2.2 并发流

并发的概念,假设现在有两个进程X和Y,那么当且仅当X在Y开始之后执行,且在Y结束之前执行;才能叫做并发执行。

如果两个流并发地运行在不同的处理器核上,那么就称为并行流。

虽然书上是这么定义的,不过我个人觉得,并行是真正意义上的同时执行,并发只是通过超高速切换使得两个任务是同时运行的而已。

8.2.3 私有地址空间

image-20201027163628821

上图是x86-64操作系统中运行的进程的地址空间,其中内核虚拟内存是对用户程序不可见的,其中也是存放的代码数据和栈这些东西。

8.2.4 用户模式和内核模式

权限控制,其实是由CPU来进行支持的。在CPU中有一个特殊的寄存器,该寄存器中有一个模式位能够提供这种功能。

在运行应用程序的时候,初始时是在用户模式中的,如果希望进入到内核模式,那么唯一的方法是使用异常(中断、系统调用)。

8.2.5 上下文切换

内核会为每一个进程维持一个上下文,并且进行切换。

8.3 系统调用的错误处理

系统级函数遇到错误的时候,会返回-1,并且同时设置一个全局整数变量errno,可以使用strerror(int errorNumber)来转化成刻度的信息。

8.4 进程控制

8.4.1 获取进程ID

1
2
3
4
5
#include <sys/types.h>
#include <unistd.h>

pid_t getpid(void);
pid_t getppid(void);

pid_t其实就是一个int。

8.4.2 创建和终止进程

进程有三种状态:运行、停止和终止。运行就是可以被执行或者正在执行。停止其实应该说的挂起会更加合适。当进程收到SIGSTOPSIGTSTP(可以被无视)、SIGTTIN或者是SIGTTOU的时候,就会进入挂起状态。只有当进程收到SIGCONT信号的时候,才会开始到运行状态。而终止就是永远停止了。进程会因为三种原因终止:收到终止信号、从主程序返回、调用exit函数。

其实exit的退出和从主程序return是一样的。

进程创建的话用的是fork,它会几乎完全复制一份父进程的虚拟内存空间地址、一样的文件标识符,它们最大的区别就是PID了。

fork也是唯一一个调用一次,但是返回两次的函数。

8.4.3 回收子进程

当一个进程由于某种原因终止的时候,内核并不会马上把它从系统中清除,而是会保持着终止的状态。此时就是僵尸进程。只有当内核把子进程退出状态给父进程后,这个子进程才会消失。

可以使用waitpid来等待一个子进程集合中的任何一个子进程终止,如果调用waitpid的时候,子进程已经终止了,那么就会立即返回。

8.4.4 让进程休眠

sleep函数会让进程休眠(挂起)一段时间,它是有一个返回值的。当然如果正常就会返回0,如果sleep函数是被一个信号中断而过早返回,那么就返回剩余的时间。

还有另外一个函数是pause,它是收到信号之后才会苏醒。

8.4.5 加载并运行程序

1
2
3
#include <unistd.h>

int execve(const char *filename, const char *argv[], const char *envp[]);

execve函数会在当前进程的上下文中加载并且运行一个新的程序。

execve是很神奇的,它只调用一次,但是从来不返回(除非出现错误,比如无法找到指定的文件)。其中的argv[0]指向的是可执行目标文件的名字,而环境变量的数组则是一个key-value数值对。

通过跟踪execve函数,我们也可以发现main函数真正的样子:int main(int argc, char *argv[], char *envp[]);,也就是,其实函数就算声明不接受参数,仍然可以给它传参(这在java中是不行的)

其中的argv和envp这两个字符数组都是用末尾的一个null来进行分割的(这一点可以用来遍历数组)。同样linux也提供了几个系统函数能够设置和获取到环境变量。

1
2
3
4
5
#include <stdlib.h>

char *getenv(const char *name);
int setenv(const char *name, const char *newvalue, int overwrite);
void unsetenv(const char *name);

8.4.6 利用fork和execve来运行程序

shell以及一些古老的服务器大量使用了fork和execve函数。可以在学习了信号之后再来手动写一个自己简单的shell实现,加深理解。

8.5 信号

信号可以理解为就是一个消息,就是一个发送给进程的小消息,通知进程发生了一些事件。信号提供了一种机制,能够让内核通知进程发生了什么事情。信号的本质一定要搞清楚,它其实就是一个数字而已,而且其实并没有所谓的发送和接受,只不过是修改了对应的字段而已。

8.5.1 信号术语

显然从日常发送微信中,也可以知道信号这个机制需要两个步骤:发送和接受。

  • 发送信号:发送信号有两种原因,一种是内核发现有问题了,那就会主动发送信号给进程;另外一种是进程调用了kill这个系统调用(需要权限才可以)。一个进程可以给自己发送信号。
  • 接收信号:内核会强迫目的进程以某种方式对信号进行反应,这就是信号的接收。当然接收了之后,进程可以忽略信号(除非特殊的信号实在无法忽略),一般情况下是用一个函数捕获这个信号。

如果一个信号发出了但是没有被接收,那么就叫做待处理信号。在任何时候一个种类最多只会有一个待处理信号,就算发送了多个同种类型的信号,其余的全部被丢弃。所以进程可以阻塞一个信号,这样同种类的信号就会全部被丢掉了。底层其实是一个bitmap来实现的。同样的也有一个叫blocked的bitmap来存放阻塞的信号。

8.5.2 发送信号

进程组

进程组就是一堆进程是一个组的,可以通过getpgrp获得,当然也可以通过对应的函数设置某个进程的进程组。

利用kill发送信号

kill这个命令可能是shell自带的,也可能是/bin/kill,需要注意区分。

从键盘发送信号

这里需要提到,在shell中的一整行的命令行,都算是一个作业(job),而一个作业本质上其实就是一个进程组,所以通过键盘发送信号,其实是发送到了一个进程组中的每一个进程中,最常见的就是ctrl+c发送了SIGINT信号,ctrl+z发送了一个SIGTSTP信号。

利用kill函数发送信号

kill本身也是一个函数,可以给特定的进程、进程组发送信号。

利用alarm函数发送信号

进程可以通过alarm函数,在x秒之后给自己发送信号。

8.5.3 接收信号

当内核把进程从内核态切回用户态的时候,内核会检查这个进程中有没有待处理的信号,如果有,内核会强制进程接收这个信号。只有当进程处理完所有的信号的时候,才会把控制权交到下一条指令中。

进程是可以通过signal函数来修改默认的行为的,但是有两个信号无法改变:SIGSTOP和SIGKILL。

比较神奇的一点:当一个进程正在处于信号处理函数的时候,它可以被别的信号处理程序所中断,然后跳到别的中断处理程序中去处理。

8.5.4 阻塞信号和解除阻塞

分成两种机制,一种是隐式阻塞机制,即内核会自动阻塞相同的信号。比如一个进程正在处理信号,那么另外一个相同类型的信号是无法被接收的。另外一种就是通过制定的函数来明确阻塞和解除阻塞了。

8.5.5 编写信号处理程序

虽然看上去信号处理函数很简单,但是其实上由于需要考虑一些共享的问题,就会比较复杂。但是由于这是并发下面的问题,所以这里只是先暂时简单讨论一下。

8.5.6 同步流以避免并发错误

也是放到并发那章去讲述。

8.6 非本地跳转

非本地跳转其实是通过setjmp和longjmp来提供的。简单来说就是把控制从一个函数转移到另一个正在执行的函数中。

首先是通过setjmp函数保存当前的调用环境,并且返回0,而且由于特殊的原因,setjmp的返回值并不能被赋值给变量。

longjmp则是从env缓冲区中恢复调用环境,并且触发一次setjmp的返回(这里就让人很疑惑),然后longjmp本身并不返回。

在更高级的语言中,可以把catch语句当成是setjmp,而throw语句就类似于longjmp语句。

8.7 操作进程的工具

linux系统自带一些监控和操作进程的工具。

  • strace:打印一个正在运行的程序和它的子进程的每个系统调用的痕迹,推荐使用-static进行编译处理。
  • ps:列出所有的进程
  • top:打印出关于当前进程资源使用的信息。
  • pmap:显示进程的内存映射。

第九章 虚拟内存

虚拟内存提供的三大好处:

  • 它把内存看成了磁盘的高速缓存,并且在内存中保存活跃的数据,相当于把内存看成了磁盘的高速缓存,并且把数据在两者之间进行传输。
  • 它为每一个进程提供了一致的地址空间,简化内存管理,统一编程模型。
  • 它能够保护每一个进程的内存地址空间不被破坏。

9.1 物理和虚拟寻址

物理寻址简单来说就是把内存看成是一个M个连续字节的数组,并且每个字节都有对应的物理地址。虚拟寻址其实就是在物理寻址的中间,加入了一个MMU(在CPU内部)的硬件,虽然是硬件,但是里面的内容(也就是映射的表格)是由操作系统来进行管理的。

9.2 地址空间

地址空间(address space)是一个非负证书地址的有序集合。如果说空间中的整数是连续的,那么就说它是一个线性地址空间(linear address space),而之后的讨论全部是基于线性地址空间来进行讨论的。

现在的操作系统中,每一个字节,都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

9.3 虚拟内存作为缓存的工具

虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组(它们在物理内存中可不一定连续,而且虚拟内存是磁盘上的概念!)。系统会将虚拟内存分割为虚拟页(VP),物理内存分割成物理页(PP),而且两者大小相等。虚拟页面分成三种,一种是尚未分配的;一种是已经缓存了磁盘中的页;还有一种是还未缓存分配的页。

9.3.1 DRAM缓存的结构

在CPU和内存之间,存在L1、L2和L3这些高速缓存,这些缓存统称为SRAM缓存(S=Static)。而DRAM(D=Dynamic)则是表示虚拟内存系统的缓存(其实就是内存条)。其中SRAM因为物理的原因,价格高速度快,而DRAM则是价格相对较低。

内存和CPU的高速缓存相比,大概慢了10倍,但是磁盘和内存相比,却是慢了非常非常多,所以DRAM一定要命中,否则就会很慢很慢。

9.3.2 页表

页表其实就是一个由页表条目组成的一个数组,而每一个页表项是一个有效位加一个地址组成的:

image-20201028155716871

从上图中也可以看到,页表其实可以指向物理内存,也可以指向磁盘。

9.3.3 页命中

就是能够直接通过页表找到在物理内存中的页。

9.3.4 缺页

如果在物理内存中无法命中,那么就叫缺页(page fault,fault是异常之一哦),缺页会触发一个异常,执行对应的异常处理程序,这个处理程序会选择一个页进行换出,如果要被换出的这个页已经被标记为修改了,那么还需要把它复制回磁盘中。然后把磁盘中需要加载进物理内存的页加载进来,并且更新页表。最后重新启动导致缺页的指令

虽然有页面预测技术(在页还没有被实际引用之前就换入物理内存),但是现在所有的操作系统用的都是按需页面调入。

9.3.5 分配页面

虚拟内存分配的过程就是在磁盘上创建空间,并且更新页表,使页表指向这块磁盘空间。

9.3.6 局部性原理

局部性原理保证了,在任意时刻,程序所使用的页面会在一个较小的集合上,这个集合就叫做工作集。如果工作集的大小超出了实际物理内存的大小,那么就会发生抖动的问题,在这个情况下页面会不断换进换出。

9.4 虚拟内存作为内存管理的工具

按需页面调度和独立的虚拟地址空间的结合,对整个系统中内存的使用和管理造成了深远的影响:

  • 简化链接。程序的代码段都是从虚拟地址0x40000开始的,然后跟着数据段,并且栈是从最高地址开始的,这些实现都是通过虚拟内存来做的。
  • 简化加载。在加载的时候,linux加载器会为代码和数据段分配虚拟页,并且把它们标记为无效的,也就是说,只有真正执行的时候,才触发缺页中断把真正的页面换入到内存中。
  • 简化共享。比如几乎所有进程都需要使用printf,那么就可以让所有的这些虚拟页面映射到相同的物理页面。
  • 简化内存分配。比如用户进程希望能够用malloc分配空间,操作系统就只需要分配连续的虚拟内存页面就可以了。

9.5 虚拟内存作为内存保护的工具

要保证进程的只读代码不能被修改、同样要保证内核的代码不能被访问,这个通过虚拟内存就很容易做到——只需要在页表里面加上一些额外的位置就可以了。如果有一条指令违反了这些位置规定的内容,那么CPU就会触发一个异常(故障),将控制传递给异常处理程序,一般会报告为段错误。

9.6 地址翻译

地址翻译本质上其实就是做了一个虚拟地址空间(VAS)到一个物理地址空间(PAS)的映射。这种映射关系是通过MMU加上页表来实现的。CPU中有一个叫做Page Table Base Register的寄存器,用来指向页表。而页表也分成两部分,分别是虚拟页号VPN加上一个虚拟页偏移量(VPO),MMU就是利用了VPN来作为对应的key,然后到页表中找到value,把这个value加上VPO就是真正的物理地址。具体过程如下:

  • CPU得到虚拟内存地址,并且将这个虚拟内存地址交给MMU。
  • MMU生成PTE地址,能够从高速缓存/内存中得到它。
  • MMU根据PTE来构造对应的物理地址,并且从高速缓存/内存获取到。

如果MMU发现PTE里面的有效位置是零,那么就需要触发一次异常,并且把控制权交给异常处理程序。异常处理程序会换出页面,并且将需要的页面换入。之后再次执行导致缺页的指令。

9.6.1 结合高速缓存和虚拟内存

如果有系统既使用虚拟内存和SRAM,那到底应该使用物理地址来访问SRAM还是用虚拟地址来访问的问题。大部分系统使用的是物理地址,因为这样比较方便共享。而且如果使用物理地址,那么意味着经过了地址翻译,而在地址翻译过程中就可以做权限检查,就避免了乱访问的问题发生。

9.6.2 利用TLB加速地址翻译

除了直接利用页表进行翻译,MMU里面还包括了一个叫TLB(Translation Lookaside Buffer)的这么一个东西,而这个东西是存放在CPU芯片里面的,其他基本和页表一致。

9.6.3 多级页表

多级页表的存在就是使用了时间换空间的技术,这里不再多说。需要注意的一点是:如果内存是满的,也就是把所有内存都用完了,那么使用多级页表反而造成了内存的浪费。但是实际中绝大部分的内存其实是空的,所以如果二级页表是空的,那么就不会有对应的页表,从这里可以节省下很大一笔空间。

而且由于TLB技术的存在加上局部性原理,其实多级页表也并不会比单级页表慢多少。

9.7 Intel Core i7/Linux

9.7.1 Core i7地址翻译

在Intel Core i7中,每一个核心都会有自己的L1、L2和MMU,但是所有的核共享一个L3缓存。具体过程跳过。

9.7.2 linux虚拟内存系统

关于用户虚拟内存的布局已经介绍过多次了,这里开始介绍内核虚拟内存。

image-20201028191150112

linux会将内核中的一部分(32位系统下是896M给直接映射到一组连续的物理页面中,这就为内核提供了一种便利的方式来访问物理内存中任意的位置)。

linux虚拟内存区域

linux将虚拟内存分成了一个一个的段(也叫区域),然后所有的虚拟页面必然都是在某个段中的。所以这样就可以不用记录那些额外的不存在的资源。

可以看到其实就是一个task_struct里面的一个mm指向了一个mm_struct对象,然后这个对象又指向了一个链表,这个链表可以表示所有的内存区域。

linux缺页异常处理

当MMU在试图翻译一个虚拟地址A的时候,它需要知道此时A这个虚拟地址是否是合法的。那么可以遍历上图中的链表,然后判断A到底是不是在链表中某个节点的合法地址。但是我们都知道链表遍历比较费时,所以其实使用的是一棵树来进行构造的

如果虚拟地址A能够找到,那么可以很容易得到对它允许的操作,假设是一个只读页面,但是操作是写,就会触发异常。

最后,虚拟地址能够找到,而且操作合法,那么就按照对应的操作来进行:选择一个页面,牺牲掉它,换入新的指令。

9.8 内存映射

内存映射就是linux通过将一个虚拟内存的区域与一个磁盘上的对象关联起来的过程。虚拟内存可以映射到两种类型的对象:

  • 普通文件。
  • 匿名文件。

一旦虚拟页面被初始化了,就会在内核维护的专门的交换文件之间换来换去,也就是swap空间。

9.8.1 再看共享对象

如果虚拟内存系统可以集成到传统的文件系统中,就能提供一种简单而高效的方法把程序和数据加载到内存中。

一个对象可以被映射到虚拟内存的一个区域,那么它要么是共享对象,要么是私有对象。

共享对象其实就是可以理解为共享内存,而私有对象则是使用了一种称为写时复制(copy-on-write)的技术,也就是如果只是读取私有对象,那么其实本质上内核是把它们映射到同一个区域的,只有当其中的一个进程试图写自己的私有区域的时候,这个写操作会触发一个保护故障,这个保护故障会在物理内存中创建一个副本,更改页表指向这个副本,然后返回并且重新执行这个程序。

9.8.2 再看fork函数

显然fork在创建子进程的时候,也用到了写时复制技术。

9.8.3 再看execve函数

现在可以更加清楚execve加载elf文件的步骤了,假设要运行a.out:

  1. 删除已经存在的用户区域。
  2. 映射私有区域。为新程序的代码、数据、堆栈等区域创建新的区域结构。显然这些区域都是写时复制的。简单点就是把a.out对应的区域给映射到execve里面。
  3. 映射共享区域。如果a.out里面有对应的共享库,那么就将这些共享库映射到共享内存区域。
  4. 设置程序计数器。就是把控制权指向了程序的入口。之后linux执行的时候,就会使用对应的缺页中断处理来换入对应的页。

9.8.4 使用mmap函数的用户级内存映射

在linux中可以使用mmap函数来创建新的虚拟内存映射区域,并将对象映射到这些区域中。通俗点讲,就是负责把文件内容映射到进程的虚拟内存空间,通过对这段内存的读取和修改,来实现对文件的读取和修改,而不需要再调用read,write等操作。

1
2
3
4
#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

9.9 动态内存分配

实际使用中,一般会使用动态内存分配器来分配虚拟内存会更加好。动态内存分配器维护的所谓的虚拟内存的区域,就是heap,也就是堆。堆紧紧挨着bss段,且堆是从低地址往高地址增长的,由brk变量来指向堆的顶部(堆的高地址处)。

9.9.1 malloc和free函数

malloc会返回一个指定size大小的虚拟内存块,但是实际上由于数据对齐的存在,可能会略微比要求的大一些。malloc并不初始化分配的内存,如果需要初始化,可以使用calloc,想要改变已经分配的内存,可以使用realloc函数。

malloc底层其实是mmap或者是sbrk,取决于分配的堆内存大小,如果比较小,那么直接用sbrk来把brk指针往上移就可以了;如果要的堆空间比较大,那么就只能用mmap了。

free函数就是用来释放对应的堆空间的。

9.9.2 为什么要使用动态内存分配

为什么要动态分配?理由很简单,因为我们不能在编写程序的时候就确定某些数据结构的大小。最常见的就是,如何动态分配一个数组了。

9.9.3 分配器的要求和目标

分配器要能够处理任何的请求序列,当然对于free在malloc之前的错误序列就不用处理。不允许分配器为了提高性能而重新排列或者缓冲请求。

9.9.4 碎片

介绍外部碎片和内部碎片。内部碎片就是分配了一块空间,但是这个空间没有用完,而剩余的这些空间也无法被使用了。外部碎片就是所有的碎片空间加起来是能够满足要求的,但是却没有一个单独的块能够满足要求。

剩下的内容讲的是,如何实现对应的malloc和free底层的结构。不太感兴趣就先跳过了。

9.10 垃圾收集

垃圾收集器是一种动态内存分配器,它能够自动释放程序不再需要的且已经分配的块。这些块被称为垃圾,而回收过程就叫做垃圾收集。

9.10.1 垃圾收集器的基本知识

垃圾收集器将内存视为一张有向可达图,如果一个堆节点指向了另外一个堆节点,那么就进行连线。其中还有一些根节点,从根节点出发构建这些有向图。

9.10.2 Mark & Sweep垃圾收集器

emm 学过java表示这块还算比较容易,就先跳过了。

9.11 C程序中常见的内存错误

做java的,先跳过了。