VM for user

用户应用程序也应该从灵活的虚拟内存中获得收益：使用与内核相同的机制，来产生Page Fault并响应Page Fault。为此，用户User Mode需要能够修改PTE的RW位

今天的话题是用户应用程序使用的虚拟内存，它主要是受这篇1991年的论文的启发。论文通过查看6-7种不同的应用程序，来说明用户应用程序使用虚拟内存的必要性。这些应用程序包括了：
Garbage Collector、Data Compression Application、Shared Virtual Memory

user 所需的VM特性

• user mode 需要可以感知到 page fault，并做出相应的回应，即 trap
• user 需要可以提升和降低 pte 的RW权限，即 Prot1 和 Unprot
• 需要可以查看内存是否被修改，即 dirty
• 需要可以重复映射某处内存，即 map2
• 每次修改虚拟内存权限后都需要flus TLB，需要有一种方法一次性flush 所有的 TLB，即 ProtN
  • ProtN 均摊了N个Prot1的损耗，损耗 = 修改PTE+一次flush，而非N次flush

如今这些特性都已经在现代的Unix系统中广泛支持了

syscall for user VM

mmap

memory mapped file

将某个文件（fd）的从指定偏移量（offset）开始的指定长度（length）的数据映射到指定的 addr，可以指定权限（prot）

addr填0则系统会自动分配并返回地址。不填0系统也会评估映射到指定地址的合理性，并选择是否映射到该地址

The flags argument determines whether updates to the mapping are visible to other processes mapping the same region, and whether updates are carried through to the underlying file. This behavior is determined by including exactly one of the following values in flags: MAP_SHARED 等

进而只需要方便的通过普通的指针操作，而不用调用read/write系统调用，就可以从磁盘读写文件内容。

Anonymous Memory

除了可以映射文件之外，还可以用来映射匿名的内存，即fd填-1，表示分配一段匿名内存

这是 sbrk 的替代方案，你可以向内核申请物理内存，然后映射到特定的虚拟内存地址。

munmap

memory unmap

取消某部分虚拟内存的映射

mprotect

modify protect，set protection on a region of memory

修改从某个虚拟地址开始的指定长度的虚拟内存的权限

但这是在page粒度工作，任何包含指定范围地址的pte都会被修改为指定权限

sigaction

为特定的信号相应做出特定的处理，例如用一个函数处理 segfault 信号，而非杀死程序

此时，通常需要修复Page Table，例如通过调用mprotect

之前实验中的 sigalarm 与这个很相似，但这个更通用

与特性的对应

trap：sigaction
Prot1，ProtN和Unprot：mprotect
map2：多次调用 mmap
Dirty：并没有一个直接的系统调用实现这个特性，不过你可以使用一些技巧完成它，稍后会介绍它。

VM for user 实现基础

VMAs

地址空间由硬件Page Table来体现的，此外还包含一些os相关的数据结构，统称为Virtual Memory Areas（VMAs），它们会记录一些有关连续虚拟内存地址段的信息

信息例如：文件的权限，文件描述符，文件的offset等

每个VMA对象对应一个连续地址的 section，每个section内部的所有page的 权限 一致

你可以在VMA中记录mmap系统调用参数中的文件描述符和offset

User level trap

• user 尝试操作某个地址，引发page fault跳转到kernel
• 内核调用page fault的handler，返回到用户空间执行handler
• handler 返回到内核，内核恢复原先的用户上下文执行
  • 如果出错还会再次进入内核

这并不会破坏任何隔离性，我们的接口只允许用户直接操作vm，而没有直接操纵任何与之相关的pte与pa，接口是否可以被执行需要经过一系列检查

VM for user：application

缓存表

什么是缓存表？它是用来记录一些运算结果的表单。

例如记录一个费时函数的从0到n参数的计算结果，这是一种 预计算 的方式

缓存表可能会非常巨大，这里便可以使用VM：

• 指定表单占用一个巨大的虚拟地址段
  • 但pte并未被初始化，无pa分配以及对应
• 请求某个参数的计算结果时，会根据表单查找到某个地址，此时触发 page fault
• 分配一个页，设置pte，计算页中所有项的结果
• 最后恢复原程序

即便如此物理内存人可能会耗尽，此时需要 回收 某个page，修改他们的 pte

Garbage Collector

GC是指编程语言替程序员完成内存释放，这样程序员就不用像在C语言中一样调用free来释放内存。程序员只需要调用类似malloc的函数来申请内存，但是又不需要担心释放内存的过程。

Java，Python，Golang 都有GC，即几乎除了C和Rust，其他所有的编程语言都带有GC。

copying GC

将内存空间划分为两部分，from和to。程序从from空间中申请了一些内存，并分配形成了如下图所属的树形对象指向关系，每个对象可能包含指向另一个对象的指针。

在from空间耗尽时，copying GC的思路是停止程序的运行，然后将正在使用的对象全部拷贝到to空间去

• 首先通过根指针找到根对象，将它拷贝到to空间。此时它的指针还是指向from空间的对象
• 然后通过指针找到它指向的对象，拷贝到to空间，并更新原指针指向to空间的对象。
• 然后在原来的from空间中留下一个 forwarding 指针，指向拷贝到to空间的对象
• 在继续向to空间拷贝对象时，发现它指向的from空间的对象处是一个forwarding指针，于是更新它指向to空间的对象

在所有的from空间中的正在使用的对象被拷贝到to中后，原来的一切即可被丢弃（包括forwarding 指针），于是from空间就变成了空闲区域

现在恢复程序的运行

Baker`s Real-Time GC

一种incremental GC，GC并不是一次做完，而是分批分步骤完成

• from空间耗尽时，只把根节点拷贝到to空间
• 在申请新内存时，在to空间申请，并在from空间留下几个转发指针
• dereference 时可能会解引用到from空间的对象——这是不应该的，所以编译器需要为其包装上一层检查，如果属于from空间的话，会把对象拷贝到to空间，并留下一个forward指针
• 在把from空间所有的对象forward完时，则可以继续重用from空间

论文对于这里的方案提出了两个问题：

• 第一个是每次dereference都需要有以上的额外步骤，每次dereference不再是对于内存地址的单个load或者store指令，而是多个load或者store指令，这增加了应用程序的开销。

• 第二个问题是并不能容易并行运行GC。如果程序运行在多核CPU的机器上，并且你拥有大量的空闲CPU，我们本来可以将GC运行在后台来遍历对象的图关系，并渐进的拷贝对象。但是如果应用程序也在操作对象，那么这里可能会有抢占。应用程序或许在运行dereference检查并拷贝一个对象，而同时GC也在拷贝这个对象。如果我们不够小心的话，我们可能会将对象拷贝两遍，并且最后指针指向的不是正确的位置。所以这里存在GC和应用程序race condition的可能。

VM GC

VM GC

基本idea

基本思想还是把数据从from空间拷贝到to空间，但是利用了可以使用虚拟内存来避免指针检查的损耗，同时仍是一个 incremental GC

VM GC将一个空间划分为scanned，unscanned。开始时，任何空间中的页都是unscanned，用户没有任何权限

• 开始GC时，将根节点拷贝到to空间，并标记from空间中的所有数据为unscanned
  • to空间中的根节点也是unscanned
• 尝试访问根节点时会触发page fault，handler会：
  • 扫描这个节点所在页中的所有对象
  • 将其指向的对象转发（复制）到to空间的unscanned区域
  • 恢复原页中的所有对象的权限，标记其为scanned区域
• 恢复程序的运行

VM：简化GC并发

• GC现在可以遍历未被扫描的内存Page，并且一次扫描一个Page，同时可以确保应用程序不能访问这个内存Page。这是一种显式的同步机制。
  • 应用程序尝试访问unscaned page时即会被阻塞并调用handler
• 只有GC可以访问 unscaned Page，而应用程序只能访问 scanned page。
  • 由于GC永远只会访问unscanned的页，二者永远会并行运行

map2

有一个问题：GC怎么访问无权限的unscanned页？mmap，两种权限不同的PTE。GC的视角中，我们仍然有from和to空间。在to空间的unscanned区域中，Page具有读写权限。

code 示例（略）

为了更清晰的说明上一节的内容，这里有个针对论文中方法的简单实现，可以肯定它包含了一些bug，因为我们并没有认真的测试它。

应用程序线程的工作是循环1000次，每次创建list，再检查list，这回产生大量的垃圾：

我们有两个API：new 和 readptr，在没有VM时他们会这样：