virtual memory csapp

发表于 | 更新于 | 分类于 | 评论数：

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续的字节数组，每字节都有一个唯一的物理地址。物理寻址：CPU使用物理地址访问主存。
早期PC使用物理寻址，现代处理器使用虚拟寻址。通过虚拟寻址，CPU通过一个虚拟地址访问主存，这个虚拟地址在送到内存前被转换成适当的物理地址。实现地址翻译的是内存管理单元(MMU)。

地址空间

地址空间是一个非负整数地址的集合，如果地址空间是连续的，叫做线性地址空间。
带有虚拟内存的系统，CPU从一个有N个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0,1,…, N-1}，N一般是2的n次幂（n为32或者64)，也叫做n位地址空间。
这个系统还需要还有一个物理地址空间，对应系统中物理内存的M个字节：{0,1,…,M-1}。M不要求是2的幂，但是一般假设M是2的m次幂。

地址空间区分了数据对象（字节）和它们的属性（地址）。允许每个数据对象有多个独立的地址，比如主存中的每个字节可能有一个虚拟地址，也有一个物理地址。

虚拟内存作为缓存的工具

虚拟内存可以用来缓存更大的虚拟地址空间的页面。
从概念上而言，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，作为数组的索引。磁盘上数组的内容被缓存在主存中。
虚拟内存系统将虚拟内存分割成虚拟页(VP)，虚拟页存储在磁盘上。物理内存被分割成物理页(PP，也叫页帧)，物理页缓存在DRAM上。他们的大小都为P字节。

虚拟页面的集合被分为三个不相交的子集：

  1. 未分配的。虚拟内存系统还没有创建或者分配的页，未分配的块没有任何数据和他们相关联，也就不占用磁盘空间。
  2. 缓存的。已经缓存在物理内存中的已分配页。
  3. 未缓存的。未缓存在物理内存中的已分配页。

DRAM缓存的组织结构

DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页。
SRAM缓存表示CPU和主存之间的L1, L2, L3高速缓存。
DRAM缓存的不命中率要比SRAM中的不命中昂贵的多，因为DRAM不命中，需要磁盘提供服务，而SRAM不命中需要DRAM提供服务。而DRAM比SRAM慢10倍，而磁盘比DRAM慢10万倍。而且从磁盘的第一个扇区读取第一个字节的时间开销比起读这个扇区中的连续字节要慢10万被。
因为大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通过是4KB到2MB。由于大的不命中处罚，DRAM缓存是全相连的，任何虚拟页都可以放置在任何物理页中。

页表

页表是一个数据结构，它和操作系统，MMU（内存管理单元中的）地址翻译硬件，一起提供了虚拟页的缓存的查找（当前虚拟页是否缓存在某个物理页中）和替换（如果不在替换哪个）等。
页表是一个常驻的主存，它是一个页表条目(page table entry)的数组，虚拟地址空间中的每个页在页表中都有一个PTE。假设PTE是由一个有效位和n位地址空间组成的，如果设置了有效位，地址指向物理页的起始位置，如果没有设置有效位，地址指向虚拟页在磁盘上的起始位置。

页命中和缺页

DRAM缓存不命中称为缺页page fault，命中叫做页命中。

  1. 如果想要读取某个字，地址翻译硬件根据虚拟地址查找页表，然后找到一个页表项
  2. 如果页表项标记当前页被缓存了，地址翻译硬件根据PTE中的物理内存地址构造这个字的物理地址，返回。
  3. 如果页表项标记当前页没有被缓存，触发缺页异常，调用内核的缺页异常处理程序，选择一个物理页中的内存进行替换。
    替换的内容：将替换页的更新写入磁盘，以及将替换页的页表条目更新为没有缓存。将访问页从磁盘复制到主存，更新该页相应的页表项。异常处理程序返回时会重新启动导致缺页的指令，这个指令把缺页的虚拟地址重新发送到地址翻译硬件。接下来就相当于执行步骤2。

页面调度（交换）是指在磁盘和内存之间传送页的活动。
直到有不命中发生时，才进行页面调入（换入）和页面调出（换出）的策略叫做按需页面调度。

分配页面

比如调用malloc就会触发分配页面的操作：在磁盘上分配空间，然后它们映射到物理内存中的物理页面，并更新相应的页表项。

局部性和抖动

局部性使得虚拟内存的性能很好。尽管在整个运行过程中引用的不同页面总数可能超过物理内存的大小，但是局部性保证了在任意时刻，程序趋向于在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集合。
不过，当工作集的大小超过物理内存的大小时，就会发生抖动（即页面不断的被换进换出）。

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

操作系统为每个进程都提供了一个独立的页表，也就是一个独立的地址空间。多个虚拟页面可以映射到同一个物理页面。
按需页面调度和独立的虚拟地址空间结合，有很多好处：

  1. 简化链接。
  2. 简化加载。
  3. 简化共享。
  4. 简化内存分配。

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

虚拟内存通过在页表项中添加SUP，READ，WRITE等字段，控制进程的权限。设置SUP位，表示只有内核进程可以访问页面，否则就没有权限。
违反了条件，就会触发Segmentation fault。

地址翻译

形式上来说，地址翻译是一个N元素的虚拟地址空间(Virtual Adress Space)中的元素和一个M元素的物理地址空间(Phicias Adress Space)中元素之间的映射。
一个n位的虚拟地址空间包含两部分：
- 一个是n-p位的虚拟页号(Virtual Page Number, VPN)，
- 一个是p位的虚拟页面偏移(virtual page offset, VPO)。
一个物理地也包含两部分：
- 一个是m-p位的物理页号(Phicial Page Number, PPN)，
- 一个是p位的物理页面偏移(phisical page offset, VPO)。
物理和虚拟页面都是p位的，VPO和PPO是相同的。
CPU的页表基址寄存器（Page table base register, PTBR)指向当前页表。
将虚拟页号加上页表基址寄存器中的页表初始偏移，找到这个虚拟页对应的物理页号，然后将物理页号和虚拟地址中的页面偏移相结合生成物理地址。

结合高速缓存和虚拟内存

利用TLB加速地址翻译

就是一个快表，一个小的页表。

多级页表

如果只用一个单独的页表进行地址翻译，假设是32位的地址空间，4KB的页面，4字节的PTE，那么即使进程只使用了虚拟地址空间中很小的一部分，也总是需要一个4MB的页表在内存中，对于64位的更严重。为什么一定需要这么多，因为是线性寻址的。
一级页表
VP 1
VP 2
…
VP 1M
总共需要1M个页表，也就是4M内存。

可以使用多级页表来解决这个问题，比如说使用4KB的页表，4字节的PTE，1K个一级页表，1K个二级页表。
VP 1
VP 2
…
VP 1K
总共有1K个一级页表
如果一个一级页表的PTE是空的，那么对应的二级页表就不会被创建。
只有以及页表才是常驻内存的，对于二级页表，只有在需要时才创建，减少了主存压力。

Linux虚拟内存系统

一个linux进程的虚拟内存分为两部分：
一个是内核虚拟内存，一个是进程虚拟内存。
内核虚拟内存分为对每个进程一样的和每个进程不一样的。每个进程都一样的是一些系统共享的资源，比如物理内存和内核代码和数据。还有一些是内核用来区分每个进程的，包括：

  1. task_struct，包含PID，指向用户栈的指针，可执行目标文件的名字和程序计数器。其中还包含一个mm_struct。
  2. mm_struct，这个结构体描述了虚拟内存的当前状态，其中有两个字段：
    • pgd，pgd指向第一级页表的基址。
    • mmap，而mmap指向一个vm_area_structs的链表，其中每个vm_area_structs都描述了当前虚拟地址空间中的一个区域。每一个具体的vm_area_struct都包含以下的字段：
      • vm_start，这个area的起始地址
      • vm_end，这个are的结束
      • vm_prot，这个区域内虚拟页的读写权限。
      • vm_flags，这个区域内的页面是与其他进程共享的，还是这个进程私有的。
      • vm_flags，指向链表中的下一个area。
  3. page table
  4. 内核栈

进程虚拟内存就是我们常说的那些代码段，堆栈段，数据段等。

内存映射

Linux通过将一个虚拟内存区域和磁盘上的对象关联起来，初始化这个虚拟内存区域中的内容，这个过程叫做内存映射(memory mapping)。

再看共享对象

再看fork函数

调用fork函数时，内核为新进程创建一个各种各样的数据结构，并给他分配一个唯一的PID，为了给这个进程创建虚拟内存，它创建了当前进程的mm_struct，area_struct和页表的副本。他讲两个进程中的每个页面都标记为只读，并将两个进程中的area_struct都标记为私有的copy on write。
当fork在新进程返回时，新进程的虚拟内存和调用fork之间进程的虚拟内存相同。当这两个进程中的任意一个进程写操作的时候，COW就会创建新页面。因此，也就为每个进程保持了私有地址空间。

再看execve函数

execve在用新的程序替换当前的程序时，包含以下的过程：

  1. 删除已存在的用户区域。
  2. 映射私有区域。
  3. 映射共享区域。
  4. 设置程序计数器。

动态内存分配

malloc和free

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

分配器的要求和目标

碎片

实现问题

隐式空闲链表

放置已分配的块

分隔空闲块

获取额外的堆内存

合并空闲块

带边界标记的合并

实现一个简单的分配器

显式空闲链表

分离的空闲链表

垃圾收集

基本知识

Mark和Sweep垃圾收集器

C程序的保守Mark和Sweep

C中常见的内存相关错误

发生segment fault的情况[2]：

  1. 解引用空指针。
  2. 访问只读的内存地址。比如数据段中的字符串。
  3. 栈溢出。函数循环引用。
  4. 访问系统保护的内存地址。比如说把100当做地址。

怎么调试segment fault？

  1. 使用printf调试。。。
  2. 使用gdb调试，使用场景，可复现的错误。需要生成调试信息。
  3. 使用core文件。core文件是一个加了调试信息的内存映像[3]。怎么样调试一个core文件，两种方法：
    • gdb -c core
    • gdb a.out core ，这里a.out是产生这个core文件的程序。
      为什么没有产生core文件，linux为一些文件设置了大小，ulimit(1)可以查看这些大小限制，core文件一般是0，所以就看不见了，可以使用ulmit -c 1024设置core文件的大小为1024字节。
      这种方法可以不用重新运行程序。
  4. 使用dmesg找到发生错误的位置，然后使用objdump反汇编。

解引用坏指针

进程的虚拟地址空间中有较大的洞，没有映射到有意义的数。如果不小心使用了这些这些，就可能会发生segment fault，但是如果没有发生的话，更难被发现。

读取未初始化的内存

比如说，堆内存没有被显式初始化，解引用这些指针，就会发生错误。

允许栈缓冲区溢出

如果往栈中分配的临时数组写入的数据量超过了它的容量，就会发生溢出。

假设指针和它们指向的对象是相同大小的

指针的大小是不变的，在一台机器上都是确定的。

数组越界

数组越界。

引用指针，而不是它所指向的对象

对指针进行了操作，而不是对指针指向的对象进行操作。

误解引用指针

指针运算是以它们指向对象的大小为单位进行的。

引用不存在的变量

引用局部变量。

引用空闲堆块中的数据

引用被释放了的堆中的内存。

引起内存泄露

没有调用free释放内存。

参考文献

1.《CSAPP》
2.https://blog.csdn.net/qq_33249383/article/details/79483212
3.https://www.cnblogs.com/dongzhiquan/archive/2012/01/20/2328355.html
4.https://manybutfinite.com/post/how-the-kernel-manages-your-memory/