CSAPP第九章 - 虚拟内存

1. 虚拟内存

1.1 DRAM 作为缓存

虚拟内存被组织为一个由存放在磁盘上连续的字节大小的单元组成的数组。DRAM 可以视为虚拟内存的缓存。

如果虚拟内存在 DRAM 上不命中的话，那么就需要从磁盘上获取，导致非常大的不命中惩罚，这就使得 DRAM 应该是全相连的。

同时，如果 DRAM 上缓存的虚拟页替换错了，那么也会导致很大的不命中惩罚，这就使得操作系统对 DRAM 缓存使用了更复杂精密的替换算法。

考虑到磁盘的写速度很慢，于是 DRAM 缓存总是使用写回而不使用直写。

1.2 地址翻译

1.2.1 MMU

计算机中使用 MMU 这个硬件来支持虚拟内存的地址翻译。

操作系统访问一个虚拟内存地址有如下的过程：

• 操作系统访问一个虚拟内存地址后，处理器将其交给 MMU。
• MMU 先根据虚拟地址计算出相应的 PTE 的地址（物理），在内存中获取 PTE。
  • 如果 PTE 有效，则说明虚拟页面命中。MMU 根据虚拟内存地址和 PTE 的信息来生成物理地址，访问内存，获取到的数据直接返回给处理器。
  • 如果 PTE 无效，说明虚拟页没有命中，发生缺页。MMU 随后调用先前设置的缺页异常处理程序。

1.2.2 结合高速缓存

我们可以在 MMU 和 DRAM 中间加高速缓存（如 L1 缓存）：

1.2.3 利用 TLB 加速翻译

CPU 每次访问一个虚拟地址，MMU 就需要先获取一个 PTE 然后再访问其对应的物理地址，也就是会从内存中多取一次数据。然而从 DRAM 访问数据需要上百个周期，这会导致性能下降地厉害。如果我们考虑到 MMU 和内存之间的高速缓存，比如 PTE 恰好缓存到 L1 中，那么开销就下降到 1 到 2 个周期。

我们还可以再使用 TLB 来使得获取 PTE 的开销更小。TLB 是一个相连度比较高的缓存（甚至是全相连）。

TLB 根据 TLBI 来选择相应的 cache set，然后根据 TLB 标记选择相应的 cache line。

TLB 是内置在 MMU 的，所以 MMU 访问 TLB 的开销极小。

虚拟地址的 VPO 和物理地址的 PPO 部分是相同的。在 Intel Core I7 上，VPO 为 12 位，L1 缓存有 64 个 cache set，每个 cache set 可容纳 8 个 cache line，一个 cache line 上有 64 个 cache block。因此，VPO 或者说是 PPO 的这 12 位刚好可以对应于某个 cache set 和 cache block。当进行地址翻译的时候，MMU 将虚拟地址的高 52 位（去掉了低 12 位）用来查 PTE 以获取物理地址的高 52 位（即 PPN）。而同时，虚拟地址的低 12 位被发送到 L1 缓存中来定位是哪个 cache set。当得到 PPN 时，L1 缓存已经准备好将 PPN 与 8 个 cache line 上的标记进行比对了。这两个过程同时执行，可以进一步增加效率。

1.3 缺页处理

在 Linux 中，操作系统还维护了当前进程虚拟内存映射的情况，比如：

当 MMU 翻译某个虚拟内存地址产生缺页时，Linux 会借助维护的这个信息对缺页原因进行判断：

• 如果虚拟内存没有落到任何区间中，那么说明产生了段错误，对应于情况 1
• 然后检查维护的权限位，判断是否为情况 2
• 如果都不是的话，说明是正常缺页

在 X86 上，PTE 最低位有一个有效位，表示其覆盖的内存区域是否存在于物理内存中。最后一级页表的 PTE 上，如果有效位为 0，则剩余的高位由操作系统自行组织，一般是用来记录位于磁盘上的位置：

其实如果使用多级页表的话，只有第一级页表需要常驻内存，其余级别的页表像普通内存区域一样可以触发缺页。

1.4 内存映射

借助虚拟内存机制，我们可以有如下的操作：

• Lazy allocation：当我们申请一块内存后，操作系统不会立刻给这块内存分配对应的物理页，而是程序实际用到的时候再分配。

• Copy on write：多个进程都含有某个对象的时候（如一个可执行文件的不同进程），可以直接让其虚拟内存映射到同一个物理内存区域。当某个进程产生修改的时候，先将被共享的页复制，再应用修改。

• Zero fill on demand：如果映射的区域全是 0 的话（比如 elf 的 bss 区域），那么操作系统不会真的去分配对应的物理页并清零，而是可能在 PTE 上标记一下，并映射到一个全为 0 的区域。当程序发生修改的时候，类似 copy on write 那样复制。

• Demand paging：如果需要将磁盘上的某个文件放入内存的话，操作系统不会直接把文件的数据复制到内存中，而是当真正需要用到的时候触发缺页进行加载。

我们可以使用 mmap 函数进行用户级的内存映射：

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

• 需要引用 unistd.h 和 sys/mman.h 两个头文件。
• 请求内核创建以 start 开始，长度为 length 的内存区域。这个内存区域去映射文件描述符 fd 对应的资源的 offset 偏移处。
• start 可以设为 NULL，此时将由内核自行决定分配到哪里。
• prot 给定了映射区域的权限位：
  • PROT_EXEC：可执行
  • PROT_READ：可读
  • PROT_WRITE：可写
  • PROT_NONE：不能被访问
• flags 给定了映射区域的特征：
  • MAP_ANON：映射区域全是 0，内核将会按照 zero fill on demand 来处理。此时 fd 和 offset 参数都给 0 就可以了。
  • MAP_PRIVATE：以私有方式进行映射。内核将使用 copy on write 机制，对映射区域的修改仅影响当前进程。
  • MAP_SHARE：以共享方式进行映射。当进行 fork 的时候父子进程之间会共享这个区域，可以用来进行进程间通信。
• 若成功则返回指向映射区域的指针，出错则返回 MAP_FAILED(-1)。

int munmap(void *start, size_t length);

• 需要引用 unistd.h 和 sys/mman.h 头文件。
• 会解除 start 开始的 length 长度的区域的映射。

使用 MAP_ANON | MAP_PRIVATE 可以创建一个全为 0 的私有区域。使用 MAP_ANON | MAP_SHARED 可以创建一个全为 0 的共享区域。如果不仅仅是父子进程之间的跨进程通信的话，可以考虑使用 shm_open 来在虚拟文件系统里创建一个文件，然后通过 mmap 来共享内存。

2. 内存分配

mmap 可以实现内存分配，但是其在不同操作系统上可能不一样。并且内存映射是以页为单位的，不能细粒度分配。并且当需要释放内存的时候 munmap 需要给出 length，这也要求我们自己再维护 mmap 的长度。综上，我们需要动态内存分配器来进行内存分配。

程序的内存布局如上，其中用户栈从高地址往低地址生长，堆从低地址往高地址生长。内核中维护了堆顶部的指针 brk。动态分配的内存会被放入堆中，堆是 zero fill on demand 的。

2.1 显式分配器

2.1.1 相关函数

void *malloc(size_t size)

• 包含在 stdlib.h 中
• 分配大小至少为 size 的内存块
• 成功则返回内存块的地址，失败返回 NULL 并设置 errno
• 由于这个内存块中会包含任何类型的数据，为了满足内存对齐的要求，在 32 位系统中返回地址是 8 的倍数（32 位系统上也能用 double），在 64 位系统中返回地址是 16 的倍数（64 位系统还要求对 SIMD 的类型有对齐支持）
• malloc 并不会初始化分配的内存块。可以使用 calloc，这个函数是 malloc 的一个包装函数，来将分配的内存初始化为零

void *realloc(void *ptr, size_t new_size)

• 包含在 stdlib.h 中
• 将原来分配的内存块的大小调整到 new_size
• ptr 必须是 malloc 返回的内容，否则会出现 UB
• 返回调整后的内存块的地址
• 一般来说 realloc 会尝试直接把原来的内存块进行扩容，如果原内存块的后方还有未分配的区域。否则，将会分配一个新的大小为 new_size 的内存块并把原来的数据复制过去

void free(void *ptr)

• 包含在 stdlib.h 中
• 将原来分配的内存块释放
• ptr 必须是 malloc 返回的内容，否则会出现 UB

void *sbrk(intptr_t incr)

• 包含在 unistd.h 中
• 将内核中的 brk 指针增加 incr，incr 既可以为正数或是负数
• 如果成功，则返回 brk 指针的旧值，否则，返回 -1 并将 errno 设置为 ENOMEM
• 一般是 malloc 内部来调用这个来自动扩容堆的

2.1.2 隐式空闲链表

一个比较简单地实现内存分配器的方法是，我们在要分配出去的内存块的前面加一个头部，来记录一些信息：

通过当前块位置和块大小就可以到达下一个块，这就相当于形成了一个隐式的链表。

假如我们要求分配的内存块是 8 字节对齐的，那么块大小的低 3 位必然是 0，因此我们可以直接让低 3 存储一些额外的信息。这里就用来标识当前块是已分配还是空闲的。

放置策略

当我们请求一个 $k$ 字节的块时，分配器搜索空闲链表，此时有一些放置策略：

• 首次适配：从头开始搜索空闲链表，如果找到一个合适的空闲块就会立刻分配
  • 优点：倾向于把大的空闲块保留在后面
  • 缺点：倾向于在前面留下碎片，增加了后续分配较大块的时间
• 下一次适配：和首次适配类似，但是不是从头开始搜索，而是从上一次分配结束的地方开始
  • 这个策略来源于这样的一个想法，如果我们上次在一个空闲块中成功适配的话，那么后面很有可能也在这个空闲块中成功适配
  • 优点：比首次适配的运行速度快一点
  • 缺点：内存利用率不如首次适配
• 最佳适配：搜索整个空闲链表，找最合适的空闲块进行分配
  • 优点：内存利用率更高
  • 缺点：需要对空闲链表进行彻底的搜索，速度很慢

碎片

• 外部碎片：随着分配和释放的进行，已经被分配出去的块可能分布的比较乱，块中间的空闲区域变得又多又小，成为了外部碎片
• 内部碎片：我们分配出去的块还需要携带一些额外信息，并且为了满足对齐要求，块会多分配一些大小进行填充。这些空间成为了内部碎片

合并策略

有可能有多个空闲块相邻，此时我们需要考虑一下合并的策略：

• 立即合并：每当一个块被释放时，就会尝试和前后的空闲块进行合并
• 推迟合并：等到某个稍晚的时候再合并。比如先不合并，直到某个分配请求失败之后再扫描整个堆进行合并（仅是例子，实际不会这么做）

立即合并也会有一个问题，比如现在有一个大的空闲块，此时反复地合并和释放，会造成反复地合并和分割。因此一个快速的内存分配器会以某种方式推迟合并。

由于合并的时候我们还需要知道前面的块的位置，所以我们可能还需要维护一个脚部，头部和脚部完全一致：

不过这样还会造成空间的浪费。更聪明的做法是在在当前块的头部记录一下上一个块是不是空闲的，然后只在空闲块中加入脚部。

2.1.3 显式空闲链表

和隐式空闲链表类似，但是空闲块还记录了前驱和后驱的数据：

这样空闲链表里就只有空闲块了，搜索的时间下降。

不过由于空闲块的额外信息，使得增大了最小块大小，增大了内部碎片的程度。

2.1.4 分离的空闲链表

这里说明一下 glibc 的 malloc 实现。参考：Understanding glibc malloc – sploitF-U-N。

首先是块的结构：

其中 P 表示前面的那个块是否被分配了。

空闲块还记录了在同一个 binlist 中的前一个 chunk 和后一个 chunk 的指针。

当我们要求 8 字节对齐之后，最小块大小为 16 字节。

chunk 被放在 bin 中。bin 是一个空闲链表，有如下几个 bin：

• fast bin
  • 有 10 个 bin，第 1 个 bin 存放 16 字节的 chunk，第 2 个 bin 存放 24 字节的 chunk ... 以此类推。
  • fast chunk 将不会和前后的空闲块合并。
• unsorted bin
  • 就一个 bin，可以存放任意大小的块。
  • 一个块被释放之后，如果没有被加入到 fast bin 中的话就会被加入到 unsorted bin。加入到 unsorted bin 时不会和前后的空闲块进行合并。
  • 所有块分割，分割出来的剩余部分都是放入 unsorted bin 中的。
• small bin：
  • 有 63 个 bin，第 1 个 bin 存放 16 字节的 chunk，第 2 个 bin 存放 24 字节的 chunk ... 以此类推，存放 16 到 512 字节。
• large bin：
  • 有 63 个 bin。其中有 32 个 bin 存放 64 字节的范围（如第一个 bin 存放大小为 513 到 576 字节的 chunk，第二个 bin 存放大小为 577 到 640 字节的 chunk...），有 16 个 bin 存放 512 字节的范围，有 8 个 bin 存放 4096 字节的范围，有 4 个 bin 存放 32768 字节的范围，有 2 个 bin 存放 262144 字节的范围，有 1 个 bin 存放剩余没有被覆盖的块大小。
  • large bin 中可以存放不同大小的块。我们维持这个 bin 中的块按从大到小的顺序排列，即大的块在链表的头部，最小的块在链表的尾部。

分配块的过程如下：

• 如果请求的块大小在 fast chunk 的大小范围
  • 从 fast bin 中查找是否有大小正好匹配的
  • 没有的话则会触发 fast bin 块合并，合并后的块放入 unsorted bin 中
• 再从 unsorted bin 中去遍历，当遍历到一个块，其大小小于请求的块大小时，会继续遍历下一个，并将这个块放入 small bin 或是 large bin 中。
• 还是找不到的话则继续从 small bin / large bin 中寻找最佳适配（可以用 bitmap 来优化这一点）

2.2 垃圾收集

2.2.1 Mark-And-Sweep

将内存视为一个有向图，其中不可达的部分就是要清除的：

其中的 Root 节点可以通过扫描栈和全局变量得到。

我们可以在 C/C++ 中实现一个保守的 Mark & Swap 的垃圾收集器：

之所以保守，是因为上述代码把一块内存中所有的数据都视为了指针。但实际上有可能出现只是单纯存储的内容有点像指针，而并非真的指针引用的情况。

朴素的 Mark and Swap 需要暂停整个程序，等待 GC 结束之后再继续运行。Nettles-O'Toole Algorithm 是其渐进版本，原理大概是先让程序运行一段时间，然后暂停，推进 GC 执行（但不必完全执行完毕），程序和 GC 交替执行。但 Nettles-O'Toole Algorithm 需要引入一个 write barrier，每当将一个对象的引用写入到另一个对象的时候，将会触发 barrier，GC 会去检查这个对象是否已经被标记，没有被标记的话就会打上标记。

2.2.2 Stop-And-Copy

和 Mark and Sweep 类似。但会使用一个 from space 和一个 to space，并使用 BFS 进行遍历，将可到达的内存块从 from space 复制到 to space，并更新指针引用，然后交换两个 space。

Stop and Copy 也有渐进的版本：Baker's Algorithm。和 Nettles-O'Toole Algorithm 不同的是其需要一个 read barrier，每当读取一个对象的时候，如果这个对象没有被复制到 to space，那么就复制过去。