【MIT 6.828】4. 内存管理
本节详细学习 6.828 lab 2，操作系统的内存管理
0x00 课程介绍
本次实验中，需要写操作系统内存管理的代码（译者注：我就不写了，学习 6.828 的目的是快速了解操作系统，初步学习且时间有限，能看懂就行了）。内存管理包含两大组件：
- 内核的物理内存分配器（physical memory allocator）：有了物理内存分配器，内核就可以分配和释放内存空间了。该分配器需要以 4096 字节（称为页，page，
#define PGSIZE 4096）为单位来运行。需要做的就是维护一个数据结构，该数据结构记录着哪些物理内存页是空闲的、哪些物理内存页是已分配的、多少进程共享了已分配的内存页。还需要编写申请和释放内存页的代码。 - 虚拟内存（Virtual Memory）：将内核和用户程序使用的虚拟地址映射到物理内存中的地址。x86 硬件的 MMU（内存管理单元，memory management unit）在指令将要使用内存的时候，通过查询页表（page table），进行映射操作，实验中会要求根据给定规范，修改 JOS 中 MMU 的页表（page table）。
接下来的所有实验，将会逐步构建出自己的内核代码。使用命令 git checkout -b lab2 origin/lab2 可以切换到 lab2 的代码分支，lab2 中已经加入了一些相关的源代码。
lab2 新增了如下文件：
- inc/memlayout.h
- kern/pmap.c
- kern/pmap.h
- kern/kclock.h
- kern/kclock.c
inc/memlayout.h 描述了虚拟地址空间的布局，你需要在 kern/pmap.c 中实现它。inc/memlayout.h 和 kern/pmap.h 定义了 PageInfo 结构体，你需要使用 PageInfo 结构体去跟踪物理内存的哪个页（page）是空闲的。kern/kclock.c 和 kern/kclock.h 控制 PC 的时钟和 CMOS RAM 硬件，在这两个文件里面 BIOS 记录着物理内存的总数和其他内容。kern/pmap.c 代码需要去读取设备硬件来得知它有多少物理内存，但是这部分代码已经写完了，我们暂时不需要关注 CMOS 硬件是如何工作的。
lab2 需要特别关注 inc/memlayout.h、kern/pmap.h、inc/mmu.h 文件，因为会用到这三个文件中定义的很多结构体。
0x01 Part 1: Physical Page Management
操作系统必须要跟踪物理 RAM 中哪些是空闲的、哪些是当前正在使用的。JOS 以页面（page）粒度来管理 PC 的物理内存，所以它可以使用 MMU 映射和保护分配的每一块内存。
现在需要编写物理页分配器（physical page allocator）代码。通过 PageInfo 结构体列表来跟踪哪些页面（page）是空闲的，每个 PageInfo 结构体对应一个物理页面（physical page）。在编写虚拟内存实现之前，需要先编写物理页分配器（physical page allocator）的实现，因为页表（page table）管理代码需要分配物理内存来存储页表（page table）。
kern/pmap.c 中，必须实现一下函数：
boot_alloc()
mem_init() (only up to the call to check_page_free_list(1))
page_init()
page_alloc()
page_free()
check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.
要实现上面的函数，可以根据函数的注释和 Intel 手册等资料，还是比较麻烦的。
页（page）的结构体如下：
struct PageInfo {
struct PageInfo *pp_link; // 空闲列表中的下一个 page
uint16_t pp_ref; // 记录指向该页的指针数量（引用计数）
};
每个 PageInfo 结构体存储着一个物理页的元数据。但是他不是物理页本身，但是物理页和 PageInfo 结构体有一对一的关系，可以使用 kern/pmap.h 中的 page2pa() 函数将结构体 PageInfo 映射到对应的物理地址上。
Page Directory 和 Page Table 其实就是一个列表，列表中每一项存储着具体的地址信息，目前这种方式相当于二级页表查找。线性地址（32-bit）分为三部分：页目录（10-bit）+ 页表（10-bit）+ 偏移（12-bit）。页目录可以存放 1024（2^10）个页表，每个页表可以存放 1024（2^10）个内存页，每个物理内存页是 4096 字节（4K），所以，整个线性地址可以表示 4G（4K * 1024 * 1024）的内存。如下图所示：
物理内存的管理总结起来其实就是一句话：
物理内存也是使用页（page）来管理，页（page）是由内核的物理内存分配器（physical memory allocator）来划分的，内核中的 PageInfo 结构体和物理页面一一对应。
0x02 Part 2: Virtual Memory
x86 保护模式（protected-mode）下的内存管理架构：段转换（segment translation）和页面转换（page translation）。
虚拟地址、线性地址和物理地址
在 x86 的术语中：
- 虚拟地址（virtual address）由段选择器（segment selector）和段内偏移（offset）组成
- 线性地址（linear address）是在段转换（segment translation）之后，页面转换（page translation）之前得到的地址
- 物理地址（physical address）是在段转换（segment translation）和页面转换（page translation）之后最终得到的地址，该地址最终会通过硬件总线（hardware bus）来访问 RAM
Selector +--------------+ +-----------+
---------->| | | |
| Segmentation | | Paging |
Software | |-------->| |----------> RAM
Offset | Mechanism | | Mechanism |
---------->| | | |
+--------------+ +-----------+
Virtual Linear Physical
C 语言中的指针（pointer）其实是虚拟地址中的 “offset”。在 boot/boot.S 文件中，我们安装了一个全局描述符表（GDT，Global Descriptor Table），通过设置所有段基地址（segment base address）为 0，并限制最高到 0xffffffff，有效的禁用了段转换（segment translation）。因此 “selector”（段选择器）无效，线性地址（linear address）始终等于虚拟地址（virtual address）的偏移量（offset）。
在 lab3 中，我们为了设置权限级别（privilege levels），必须与分段（segmentation）进行更多的交互，但是对于内存转换，我们可以忽略 JOS labs 中的分段（segmentation），只需要关注页面转换（page translation）。
回想一下 lab1 的 part3，我们使用了一个简单的页表（page table），这样内核就可以在其链接地址（0xf0100000）处运行，尽管它实际加载在 BIOS ROM 上面的物理地址（0x00100000），其中的原因就是由于通过页表（page table）做了一个地址映射，该页表（page table）只能映射 4M 内存。
本实验中，需要为 JOS 设置虚拟地址空间布局，我们对此进行扩展，映射物理内存的前 256M 内存，虚拟地址从 0xf0000000 开始，并映射虚拟地址空间的其他区域。
从 CPU 上的执行代码来看，一旦进入保护模式（boot/boot.S 中首先会进入保护模式），就无法直接使用线性地址和物理地址了。所有的内存引用都会被解释为虚拟地址，并由 MMU 进行转换，这意味着 C 语言中的所有指针都是虚拟地址。
JOS 内核通常将地址作为不透明的值（opaque values）或整数（integers）进行操作，而不去引用他们（例如在物理内存分配器中就是这样使用的）。有时是虚拟地址，有时是物理地址，为了方便区分，JOS 源码分成了两种类型（这两种类型实际上都是 32 位整数类型（uint32_t），因此编译器不会阻止它们相互赋值，由于它们是整数类型而不是指针，如果取消引用它们，编译器会报错）：
physaddr_t类型表示物理地址uintptr_t类型表示虚拟地址
JOS 内核需要先将 uintptr_t 强制转换（cast）成指针类型，才能对 uintptr_t 进行解引用（dereference）操作。相反的，内核不能正确的解引用（dereference）一个物理地址，因为 MMU 转换了所有内存引用。如果将 physaddr_t 强制转换（cast）为指针类型并取消引用，你虽然可以加载和存储得到的地址，但是可能无法获得到预期的内存位置，因为它被视为虚拟地址来被处理的。
C type Address type
T* Virtual
uintptr_t Virtual
physaddr_t Physical
JOS 内核有时候需要直接读取和修改物理地址对应的内存（非虚拟地址对应的内存），例如：向页表（page table）添加映射关系时可能需要申请物理内存来存储页目录（page directory），然后初始化这块内存。但是，内核不能绕过虚拟地址转换这步操作，因此不能直接加载和存储数据到物理地址。原因之一是：JOS 从物理地址 0 的位置重新映射了所有的物理内存到虚拟内存的 0xf0000000 位置，当内核只知道物理地址时，这种方式（物理地址加上 0xf0000000 就是虚拟地址）会帮助内核来读取和写入数据。为了将物理地址转换成内核可以实际读写的虚拟地址，内核必须将 0xf0000000 和物理地址相加，以在重新映射的区域中找到其相应的虚拟地址，可以使用 KADDR(pa) 函数来做加法操作。
JOS 内核有时还需要找到一个虚拟地址内存对应的物理地址（该地址存储内核的数据结构）。内核的全局变量和被 boot_alloc() 分配的内存处在内核被加载的区域（从 0xf0000000 开始的位置），这块区域包含在映射范围内。因此，要将该区域的虚拟地址转换为物理地址，内核只需要减去 0xf0000000 即可，可以使用 PADDR(va) 函数来做减法操作。
引用计数（Reference counting）
在后边的 lab 中，会经常看到多个虚拟地址映射到了相同的物理地址，我们需要在 PageInfo 结构体的 pp_ref 字段维护每个物理页面（physical page）被引用的次数。当物理页面（physical page）的引用计数为 0 时，该页就可以被释放了，因为它不再被使用。通常，物理页面（physical page）的引用计数应该等于在所有的页表（page table）范围内 UTOP 以下的区域，该物理页面（physical page）出现的次数。（UTOP 以上的区域大部分是在引导时（boot time）由内核设置的，不应该被释放掉，因此不需要对它们进行引用计数）。我们还将使用引用计数来跟踪指向 page directory 页的指针数量，还有，page directory 对 page table 页的引用数量。
使用 page_alloc 函数时一定要小心，它返回的页面（page）的引用计数始终为 0，因此当你对返回的页面（page）执行操作（比如将该 page 插入到 page table 中）以后，pp_ref 字段应该立即加 1，有时这个操作是由其他函数（例如，page_insert）处理的，有时调用 page_alloc 的函数必须直接处理。
页表管理（Page Table Management）
这里需要编写管理页表（page table）的代码：插入和删除线性地址到物理地址的映射、在需要的地方创建 page table 页。
在 kern/pmap.c 文件中，实现如下函数：
pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()
check_page(), called from mem_init(), tests your page table management routines. You should make sure it reports success before proceeding.
0x03 Part 3: Kernel Address Space
JOS 将处理器的 32 位线性地址空间（linear address space）分为两部分，分界线是由 inc/memlayout.h 中 ULIM 符号定义的，会为内核保留大约 256M 的虚拟地址空间：
- 内核会控制上面一部分的（upper part）的布局（layout）和内容
- 用户环境（user environments）会控制下面一部分（lower part）的布局（layout）和内容
这解释了为什么我们需要在 lab1 中为内核设置如此高的链接地址，如果不设置如此高的链接地址，内核的虚拟地址空间下面就没有足够的空间预留给用户环境。
权限和故障隔离（Permissions and Fault Isolation）
由于内核和用户内存都存在于每个环境的地址空间中，因此我们必须在 x86 页表（page table）中使用权限位（permission bits），以限制用户代码仅能访问地址空间中的用户部分。否则，用户代码中的错误可能会覆盖内核数据，导致系统崩溃等问题；用户代码还可能窃取其他环境的私有数据。注意：可写权限位 PTE_W 同时影响用户代码和内核代码。
内核可以读写 ULIM 符号之上的任何内存，用户环境则没有权限访问。[UTOP，ULIM] 地址范围，内核和用户环境具有相同的权限：他们可以读取但是不能写入该地址范围。此地址范围用于以只读方式向用户环境公开某些内核数据结构。最后，UTOP 下面的地址空间供用户环境使用；用户环境将设置访问此内存的权限。
初始化内核地址空间（Initializing the Kernel Address Space）
现在，我们需要设置 UTOP 上面的地址空间（地址空间中的内核部分）。我们需要使用上面实现的一些函数来设置适当的线性地址到物理地址的映射。
地址空间布局（Address Space Layout）备选方案
我们在 JOS 中使用的地址空间布局不是唯一的方案。操作系统也可以将内核映射到较低的线性地址，而将上部地址空间留给用户进程。但是，x86 内核通常不采用这种方法，因为 x86 的虚拟 8086 模式（一种向后兼容的模式）在处理器中是“硬连线”的，就是为了使用线性地址空间的底部区域，因此如果内核映射在那里的话，将无法使用。
甚至可以设计内核，使其不必为自己保留处理器线性或虚拟地址空间的任何固定部分，而是有效地允许用户级进程不受限制地使用整个 4GB 的虚拟地址空间，同时仍然充分保护内核不受这些进程的影响，并保护不同进程彼此不受影响，显而易见，这是非常困难的。