👩Introduction

在这个实验中，将会编写操作系统的内存管理模块的代码。内存管理模块有两个组件：

• 物理内存分配单元：
  • 通过物理内存分配单元内核可以分配内存，然后释放内存
  • 物理内存分配器将以 4096 字节为单位运行，称为页
  • 我们的任务是维护数据结构，记录空闲的物理页，被分配的页，以及有多少进程共享每个分配的页
  • 还将编写分配和释放内存页的例程
• 虚拟内存：
  • 它将内核和用户软件使用的虚拟地址映射到物理内存中的地址
  • x86 硬件的内存管理单元（MMU）在指令使用内存时执行映射，查询一组页表
  • 根据提供的规范修改 JOS 以设置 MMU 的页表

Lab 2 包含以下新的源文件，我们在实验中会主要使用、查看这些文件：

• inc/memlayout.h
• kern/pmap.c
• kern/pmap.h
• kern/kclock.h
• kern/kclock.c

memlayout.h 描述必须通过修改 pmap.c 实现的虚拟地址空间的布局。
memlayout.h和 pmap.h 定义 PageInfo 结构，用于跟踪哪些物理内存页是空闲的。
kclock.c 和 kclock.h 操作 PC 的电池支持时钟和 CMOS RAM 硬件，其中 BIOS 记录 PC 包含的物理内存量等。
pmap.c 中的代码需要读取设备硬件才能计算出有多少物理内存。

👨Physical Page Management

操作系统必须跟踪物理 RAM 的哪些部分是空闲的，哪些部分当前正在使用。JOS 以页粒度管理 PC 的物理内存，这样它就可以使用 MMU 来映射和保护每个分配的内存。
现在将首先编写物理页分配单元，它通过 PageInfo 结构体的链表跟踪哪些页是空闲的，每个结构体对应于一个物理页。在编写虚拟内存实现的其余部分之前，需要先编写物理页分配单元，因为页表管理代码将需要分配物理内存来存储页表。

👧Virtual Memory

🎆Virtual, Linear, and Physical Addresses

在 x86 术语中，虚拟地址由段选择器和段内的偏移量组成。线性地址是在段翻译之后但在页翻译之前得到的地址。物理地址是在段和页转换之后最终得到的地址，也是最终通过硬件总线传输到 RAM 的地址。

           Selector  +--------------+         +-----------+
          ---------->|              |         |           |
                     | Segmentation |         |  Paging   |
Software             |              |-------->|           |---------->  RAM
            Offset   |  Mechanism   |         | Mechanism |
          ---------->|              |         |           |
                     +--------------+         +-----------+
            Virtual                   Linear                Physical

AC 指针是虚拟地址的“偏移”部分。在 boot/boot.S 中，我们设置了一个全局描述符表（Global Descriptor Table，GDT），它通过将所有段基址设置为 0 并将限制设置为 0，有效地禁用了段转换。因此“选择器”无效，线性地址总是等于虚拟地址的偏移量。
在 Lab3 中，我们需要与分段进行更多的交互来设置特权级别，但是对于内存转换，我们可以忽略分段，而只关注页转换。
在 Lab1 的 Part3 中，内核可以在其链接地址 0xf010000 处运行，即使它实际上加载在物理内存中，刚好位于ROM BIOS 的 0x00100000 处。此页表仅映射 4MB 内存。现在，我们将对其进行扩展，以映射从虚拟地址 0xf000000 开始的第一个 256MB 物理内存，并映射虚拟地址空间的许多其他区域。
从 CPU 上执行的代码来看，一旦进入保护模式（在 boot/boot.S 中首先进入保护模式），就无法直接使用线性或物理地址。所有内存引用都被解释为虚拟地址，并由 MMU 进行转换，这意味着 C 中的所有指针都是虚拟地址。
JOS 内核通常需要将地址作为不透明值或整数进行操作，而不解引用它们。例如在物理内存分配器中：有时使用虚拟地址，有时使用物理地址。
为了规范代码，JOS 源代码区分了两种情况：

• 类型 uintptr_t 与 T* 表示不透明的虚拟地址
• 类型 physaddr_t 表示物理地址

这两种类型实际上只是 32 位整数（uint32_t），因此编译器不会阻止您将一种类型分配给另一种类型！ 由于它们是整数类型（不是指针），如果您尝试对它们解引用，编译器就会给出警告或错误：

• JOS 内核可以将 uintptr_t 转换为指针类型并解引用它
• JOS 内核不能解引用物理地址，因为 MMU 会转换所有内存引用。如果将 physaddr_t 转换为指针并解引用它，您可以加载并存储到结果地址（硬件会将其解释为虚拟地址），但无法获得预期的内存位置。

JOS 内核有时需要读取或修改内存信息，但是只知道物理地址。例如，向页表添加映射可能需要分配物理内存来存储页目录，然后初始化该内存。但是，内核不能绕过虚拟地址转换，因此不能直接加载和存储到物理地址。
JOS 将所有物理内存从物理地址 0 重新映射到虚拟地址 0xf000000 的一个原因是帮助内核读写它只知道物理地址的内存。为了将物理地址转换为内核可以实际读写的虚拟地址，内核必须将物理地址加上 0xf000000，以便在重新映射的区域中找到相应的虚拟地址。你应该用宏定义的函数 KADDR(pa)。
JOS 内核有时还需要能够在给定存储内核数据结构的内存虚拟地址的情况下找到物理地址。内核全局变量和分配的内存位于加载内核的区域，从 0xf000000 开始，正是我们映射所有物理内存的区域。因此，要将此区域中的虚拟地址转换为物理地址，内核只需减去 0xf000000 即可。你应该用宏定义的函数 PADDR(va)。

🎋Reference counting

在后续的 Lab 中，需要同时在多个虚拟地址（或在多个环境的地址空间）映射相同的物理页。您将在与物理页对应的字段中记录对每个物理页的引用数。当物理页的计数变为零时，该页可以被释放，因为它不再被使用。一般来说，这个计数应该等于物理页在所有页表中出现在 UTOP 下面的次数。
使用 page_alloc 时，它返回的页面的引用计数始终为 0。因此对返回的页面执行操作时（例如将其插入页面表），pp_ref 就应该递增。pp_ref 的递增可能由其他函数完成，如，page_insert，有时获取到页时就要立即递增。

🎁Page Table Management

完成 Exercise 4。

👦Kernel Address Space

JOS 将处理器的 32 位线性地址空间分为两部分：

• 在 Lab3 中开始加载和运行的用户环境（进程）将控制下部的布局和内容
• 内核始终保持对上部的完全控制

分界线是由 inc/memlayout.h 中的符号任意定义的，为内核保留了大约 256MB 的虚拟地址空间。
这就解释了为什么我们需要在 Lab1 中为内核提供如此高的链接地址，否则内核的虚拟地址空间将没有足够的空间同时映射到它下面的用户环境中。

🎇Permissions and Fault Isolation

由于内核和用户内存都存在于每个环境的地址空间中，因此我们必须在 x86 页表中使用权限位，以允许用户代码只访问地址空间的用户部分。否则，用户代码中的 bug 可能会覆盖内核数据，导致崩溃和故障；用户代码也可能会窃取其他环境的私有数据。（需要注意的是，可写权限位（PTE_W）同时影响用户和内核代码！）

• 用户环境将无权访问内核部分任何内存，而内核将能够读取和写入该内存
• 对于地址范围，内核和用户环境具有相同的权限：它们可以读取但不能写入此地址范围。地址范围用于向用户环境以只读方式公开某些内核数据结构
• 最后，下面的地址空间供用户环境使用；用户环境将设置访问此内存的权限

  🎍Initializing the Kernel Address Space

  设置内核部分地址空间。inc/memlayout.h 显示应该使用的布局。您将使用刚刚编写的函数来设置适当的线性地址到物理地址的映射。
  完成 Exercise 5。

  🎗Address Space Layout Alternatives

  在 JOS 中使用的地址空间布局不是唯一的。操作系统可以将内核映射到低线性地址，同时将线性地址空间的上部留给用户进程。但是 x86 内核一般不采用这种方法，因为 x86 需要向后兼容，称为虚拟 8086 模式，在处理器中“硬连线”使用线性地址空间的底部。因此如果内核映射到那里，就无法使用。

  🧑Exercise And Question

  🎈No1

  在 kern/pmap.c 文件中，实现以下函数：

  • boot_alloc()
  • mem_init()（仅限于调用 check_page_free_list(1)）
  • page_init()
  • page_alloc()
  • page_free()

  check_page_free_list() 和check_page_alloc()，测试编写的物理页分配单元。您应该引导、启动 JOS 并查看check_page_alloc() 是否报告成功。修正代码，直至通过。

🚗boot_alloc()

首先查看 boot_alloc() 函数，在 page 初始化完成前，使用 boot_alloc() 函数分配内存，后面常常看到的标识内存状态的 pages 数组就是这个函数分配的。
函数接受一个参数，代表需要多少字节内存。函数将这个字节数上调到 page 大小的边界，也就是调整为离这个字节数最近的 4096 的整数倍，以求每次分配都是以 page 为单位的。接下来我们看一下其具体的实现：

// ./inc/types.h
// 四舍五入到 n 的最近倍数
#define ROUNDUP(a, n)                                     \
  ({                                                      \
    uint32_t __n = (uint32_t)(n);                         \
    (typeof(a))(ROUNDDOWN((uint32_t)(a) + __n - 1, __n)); \
  })
// ./kern/pmap.c
// 这是一个仅在 JOS 设置虚拟内存系统时使用的简单的物理内存分配器.
// page_alloc() 才是真正的内存分配器.
//
// 如果 n > 0, 分配足够的连续物理内存页以容纳 'n' Bytes.
// 不要初始化内存. 返回内核虚拟地址.
//
// 如果 n == 0, 返回下一个没有分配任何东西的空闲页的地址.
//
// 如果内存溢出, boot_alloc 应该引发异常.
// 这个函数只在 page_free_list 链表被设置之前初始化时使用.
static void* boot_alloc(uint32_t n) {
  static char* nextfree;  // 下一个空闲的虚拟内存地址
  char* result;
  // 在第一次调用时初始化 nextfree.
  // 'end' 是连接器自动生成的魔术符号,
  // 他指向内核 bss 段的结束地址:
  // 第一个没有被连接器分配给任何内核代码和全局变量的虚拟地址.
  if (!nextfree) {
    extern char end[];
    nextfree = ROUNDUP((char*)end, PGSIZE);
  }
  // 分配一个足够大的块来容纳 n 个字节, 然后更新 nextfree.
  // 确保 nextfree 对齐 PGSIZE 的整数倍.
  //
  // LAB 2: Your code here.
  result = nextfree;
  nextfree = ROUNDUP(nextfree + n, PGSIZE);
  // out of memory panic
  if (nextfree > (char*)0xf0400000) {
    panic("boot_alloc: out of memory, nothing changed, returning NULL...\n");
    nextfree = result;
    return NULL;
  }
  return result;
}

🚕mem_init()

在初始化内存组件的函数 mem_init() 中，首先调用了函数 i386_detect_memory() 获得了内存硬件信息，其底层实现在 kern/kclock.c 中，通过一系列汇编指令得到硬件信息；具体的运行方式和执行的汇编指令我们就不再关心了；最后函数运行的结果得到两个整数：

• npages：内存的 page 个数
• npages_basemem：在拓展内存之前的 page 个数

接着我们需要在其中分配 pages 的初始内存：

//////////////////////////////////////////////////////////////////////
// 分配一个长度为 npages 的 'struct PageInfo' 数组并存储在 'pages'.
// 内核使用这个数组追踪物理页: 对于每一个物理页对应数组中的一项.
// 使用 memset 初始化 pages 数组中所有的 PageInfo 为 0.
// Your code goes here:
pages = boot_alloc(sizeof(struct PageInfo) * npages);
memset(pages, 0, sizeof(struct PageInfo) * npages);

mem_init() 函数的其余部分仅仅调用需要的验证函数，这里我们就不再赘述了。

🚓page_init()

直接查看 page_init() 函数，这个函数初始化页结构和内存可用列表。本函数执行完成后，不再使用 boot_alloc 函数。只能使用下面的 page_alloc 函数通过页空闲列表分配和释放物理内存。
我们需要知道哪些内存是空闲的，那些内存是被占用的：

1. 将物理页 0 标识为正在使用；通过这个方式我们保存实模式下的 IDT 和 BIOS 结构，以防万一需要使用他们
2. 剩余的内存，[PGSIZE, npages_basemem * PGSIZE) 是空闲的
3. IO hole [IOPHYSMEM, EXTPHYSMEM)，绝对不能被分配，是被 IO 设备占用的
4. 拓展内存 [EXTPHYSMEM, …)；其中的一些是在使用的，一些是空闲的。内核在哪些物理内存中？哪些内存已经被页表和其他数据结构使用？可以使用 boot_alloc(0) 得到空闲空间的开始地址。

完成的函数如下：

struct PageInfo {
  // Next page on the free list.
  struct PageInfo* pp_link;
  // pp_ref is the count of pointers (usually in page table entries)
  // to this page, for pages allocated using page_alloc.
  // Pages allocated at boot time using pmap.c's
  // boot_alloc do not have valid reference count fields.
  uint16_t pp_ref;
};
void page_init(void) {
  //  1) Mark physical page 0 as in use.
  pages[0].pp_ref = 1;
  // declare i
  size_t i;
  //  2) [PGSIZE, npages_basemem * PGSIZE) is free.
  for (i = 1; i < npages_basemem; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }
  //  3) The IO hole [IOPHYSMEM, EXTPHYSMEM), which must never be allocated.
  for (; i < EXTPHYSMEM / PGSIZE; i++) {
    pages[i].pp_ref = 1;
  }
  //  4) Then extended memory [EXTPHYSMEM, ...).
  physaddr_t first_free_addr = PADDR(boot_alloc(0));
  for (; i < first_free_addr / PGSIZE; i++) {
    pages[i].pp_ref = 1;
  }
  // mark other pages as free
  for (; i < npages; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }
}

要解释上面的函数我们需要事先知道内存的布局与我们需要管理的内存范围是什么：

                  +--------------------+
                  |                    |
                  /\/\/\/\/\/\/\/\/\/\/\    <-- ext
                  \/\/\/\/\/\/\/\/\/\/\/
                  |                    |
boot_alloc(0) --> +--------------------+
                  |                    |
                  /\/\/\/\/\/\/\/\/\/\/\    <-- data
                  \/\/\/\/\/\/\/\/\/\/\/
                  |                    |
                  +--------------------+
                  |                    |
                  /\/\/\/\/\/\/\/\/\/\/\    <-- kernel
                  \/\/\/\/\/\/\/\/\/\/\/
                  |                    |
0x00100000 -->    +--------------------+    <-- 1MB
                  |                    |
                  /\/\/\/\/\/\/\/\/\/\/\    <-- IO hole
                  \/\/\/\/\/\/\/\/\/\/\/
                  |                    |
0x000a0000 -->    +--------------------+
                  |                    |
                  /\/\/\/\/\/\/\/\/\/\/\    <-- 空闲区域
                  \/\/\/\/\/\/\/\/\/\/\/
                  |                    |
0x00001000 -->    +--------------------+
                  |                    |    <-- IDT 和 BIOS 结构
0x00000000 -->    +--------------------+

可以从上图简单的看出物理内存的布局依次是：

• IDT 和 BIOS 结构
• 空闲区域
• IO Hole
• Kernel
• Data
• 空闲区域

总结一下，我们需要管理的部分就是两个空闲区域，并且需要将其他区域标识为不能被分配，所以有了上面的代码。

🛺page_alloc()

接下来我们来看分配页的代码。

• 如果没有空闲内存返回 NULL，否则分配新的一页
• 在新分配页是，如果 (alloc_flags & ALLOC_ZERO)，用 ‘\0’ 填充整个返回的物理页。需要注意不增加页的引用（调用者必须在必要时执行这些操作）

请确保将分配页的 pp_link 字段设置为 NULL，以便 page_free 可以检查双重释放错误。
提示：

• 使用 page2kva 得到 PageInfo 对应的实际地址

• 使用 memset 进行初始化

  struct PageInfo* page_alloc(int alloc_flags) {
  // Out of memory
  if (!page_free_list) {
    return NULL;
  }
  // Get first free Page
  struct PageInfo* target = page_free_list;
  page_free_list = page_free_list->pp_link;
  target->pp_link = NULL;
  if (alloc_flags && ALLOC_ZERO) {
    // Get page real address
    char* head_address = page2kva(target);
    // Init the '\0' to target
    memset(head_address, 0, PGSIZE);
  }
  return target;
  }

  🚙page_free()

  接下来我们来看释放页的代码，比较简单就不再额外分析了：

  //
  // 将一个页归还到 free list 中.
  // (只有当 pp->pp_ref 达到 0 时才应调用此函数.)
  //
  void page_free(struct PageInfo* pp) {
  // Fill this function in
  // Hint: You may want to panic if pp->pp_ref is nonzero or
  // pp->pp_link is not NULL.
  if (pp->pp_ref != 0 || pp->pp_link != NULL) {
    panic("Page double free or freeing a referenced page...\n");
  }
  pp->pp_link = page_free_list;
  page_free_list = pp;
  }

  运行结果如下：

  wangjq@ubuntu:~/MIT/lab$ make qemu
  qemu-system-i386 -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb tcp::26000 -D qemu.log 
  6828 decimal is 015254 octal!
  Physical memory: 131072K available, base = 640K, extended = 130432K
  check_page_free_list() succeeded!
  check_page_alloc() succeeded!
  kernel panic at kern/pmap.c:711: assertion failed: page_insert(kern_pgdir, pp1, 0x0, PTE_W) < 0
  Welcome to the JOS kernel monitor!
  Type 'help' for a list of commands.
  k>

  🎄No2

  略，主要是分页分段机制各自的作用与区别。

  🎀No3

  使用 GDB 工具，查看我们 Lab1 初始化的虚拟内存值是对应的。即验证虚拟地址 0xf010000 处的数据与物理地址 0x0010000 处的数据是相同的（本练习需要使用定制的 qemu 以使用 xp 命令）。

在第一个终端中运行 make qemu-gdb 命令，在第二个终端中运行 make gdb 命令，分别运行 qemu 模拟器与 gdb 工具。
在 gdb 终端中输入 c 执行程序，在键入 ctrl+c 使其停止执行，查看 0xf010000 处的数据如下：

(gdb) c
Continuing.
^C
Program received signal SIGINT, Interrupt.
The target architecture is assumed to be i386
=> 0xf0100173 <cons_intr+56>:    cmp    $0xffffffff,%eax
0xf0100173 in cons_intr (proc=0xf010011c <serial_proc_data>)
    at kern/console.c:558
558      while ((c = (*proc)()) != -1) {
(gdb) x/16xw 0xf0100000
0xf0100000 <_start+4026531828>:    0x1badb002    0x00000000    0xe4524ffe    0x7205c766
0xf0100010 <entry+4>:    0x34000004    0x2000b812    0x220f0011    0xc0200fd8
0xf0100020 <entry+20>:    0x0100010d    0xc0220f80    0x10002fb8    0xbde0fff0
0xf0100030 <relocated+1>:    0x00000000    0x112000bc    0x0002e8f0    0xfeeb0000
(gdb)

在 gdb 终端中输入 c 让程序接着运行，然后在 qemu 终端中输入 ctrl+a、c 打开 qemu 终端，之后使用 xp 命令查看物理内存处的数据：

K> QEMU 2.3.0 monitor - type 'help' for more information
(qemu) xp/16xw 0x100000
0000000000100000: 0x1badb002 0x00000000 0xe4524ffe 0x7205c766
0000000000100010: 0x34000004 0x2000b812 0x220f0011 0xc0200fd8
0000000000100020: 0x0100010d 0xc0220f80 0x10002fb8 0xbde0fff0
0000000000100030: 0x00000000 0x112000bc 0x0002e8f0 0xfeeb0000
(qemu)

可以看到对应的数据是相同的，也就验证了我们的虚拟内存在正常的工作。

🎢Q1

假设下面的 JOS 内核代码是正确的，那么变量 x 的类型是 uintptr_t 还是 physaddr_t？

mystery_t x;
char* value = return_a_pointer();
*value = 10;
x = (mystery_t) value;

x 的类型是 uintptr_t 因为对物理地址解引用在 JOS 内核中是没有意义的，既然这里可以对其进行解引用，所以肯定为 uintptr_t 类型。

👓No4

在 kern/pmap.c 文件中，实现以下函数：

• pgdir_walk()
• boot_map_region()
• page_lookup()
• page_remove()
• page_insert()

使用 check_page() 进行测试。

🚑页表介绍

首先，我们先看看分页机制里面的页目录表、页表、页之间的关系。
分页机制是用于将一个线性地址转换为一个物理地址的方式。
在 I32 CPU 环境里面，首先通过设置 CR0 寄存器，打开保护模式、开启分页机制。然后将页目录表的物理地址基址给 CR3 寄存器。开启分页机制后，I32将全部的物理内存空间、线性地址空间划分为一个个的页。每个页可以是 4KB 或者 4MB。
页目录表里面存放页目录表项，每个页目录表项指向页表。其中页目录表项的高20位为对应页表的物理地址的高20位。低12位为属性位。

页表里面存放着页表项，每个页表项指向页。其中页表项的高20位为对应页的物理地址的高20位，低12为属性位。

各个标志位的含意如下：

• 【P】：存在位。为1表示页表或者页位于内存中。否则，表示不在内存中，必须先予以创建或者从磁盘调入内存后方可使用
• 【R/W】：读写标志。为1表示页面可以被读写，为0表示只读。当处理器运行在0、1、2特权级时，此位不起作用。页目录中的这个位对其所映射的所有页面起作用
• 【U/S】：用户/超级用户标志。为1时，允许所有特权级别的程序访问；为0时，仅允许特权级为0、1、2的程序访问。页目录中的这个位对其所映射的所有页面起作用
• 【PWT】：Page级的Write-Through标志位。为1时使用Write-Through的Cache类型；为0时使用Write-Back的Cache类型。当CR0.CD=1时（Cache被Disable掉），此标志被忽略。对于我们的实验，此位清零
• 【PCD】：Page级的Cache Disable标志位。为1时，物理页面是不能被Cache的；为0时允许Cache。当CR0.CD=1时，此标志被忽略。对于我们的实验，此位清零
• 【A】：访问位。该位由处理器固件设置，用来指示此表项所指向的页是否已被访问（读或写），一旦置位，处理器从不清这个标志位。这个位可以被操作系统用来监视页的使用频率
• 【D】：脏位。该位由处理器固件设置，用来指示此表项所指向的页是否写过数据
• 【PS】：Page Size位。为0时，页的大小是4KB；为1时，页的大小是4MB（for normal 32-bit addressing ）或者2MB（if extended physical addressing is enabled)
• 【G】：全局位。如果页是全局的，那么它将在高速缓存中一直保存。当CR4.PGE=1时，可以设置此位为1，指示Page是全局Page，在CR3被更新时，TLB内的全局Page不会被刷新。
• 【AVL】：被处理器忽略，软件可以使用

经过上面这三个结构，CPU 就有了将线性地址转换为物理地址的基础。
所以一个线性地址 “la”包含下面三部分数据结构：

+--------10------+-------10-------+---------12----------+
| Page Directory |   Page Table   | Offset within Page  |
|      Index     |      Index     |                     |
+----------------+----------------+---------------------+
 \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
 \---------- PGNUM(la) ----------/

当 CPU 拿到一个线性地址后，需要将其转换为物理地址。其中一个 32 位的线性地址分为三部分：最高 10 位，中 10 位，低 12 位。

• 高 10 位表示这个物理地址属于页目录表的那一项管辖，通过这个页目录表项就可以得到对应指向的页表的物理基址
• 中 10 位表示这个物理地址属于上一步得到的页表里面第几项管辖。通过这个页表项就可以得到这个物理地址所在的页的物理基址
• 低 12 位表示这个物理地址在所属的页（上一步确定了这个页的物理基址）里面的偏移

  🚌mmu.h 中的定义

  我们在具体编写这几个函数之前，先来看看 inc/mmu.h 中有用的说明与定义： ```c // page number field of address

  define PGNUM(la) (((uintptr_t)(la)) >> PTXSHIFT)

// page directory index

define PDX(la) ((((uintptr_t)(la)) >> PDXSHIFT) & 0x3FF)

// page table index

define PTX(la) ((((uintptr_t)(la)) >> PTXSHIFT) & 0x3FF)

// offset in page

define PGOFF(la) (((uintptr_t)(la)) & 0xFFF)

// construct linear address from indexes and offset

define PGADDR(d, t, o) ((void*)((d) << PDXSHIFT | (t) << PTXSHIFT | (o)))

<a name="qDl24"></a>
### 🚐pgdir_walk()
接下来我们就可以正式编写函数了，首先是 pgdir_walk()，这个函数给定一个指向页目录的指针“pgdir”，一个线性地址“va”，pgdir_walk 返回指向“va”的页表条目 (PTE) 指针，这个操作需要遍历两级页表结构。<br />相关页表页可能不存在，如果出现了这样的情况：
- 并且 create==false，pgdir_walk 返回 NULL
- 否则，pgdir_walk 将使用 page_alloc 分配一个新的页表页
   - 如果分配失败，pgdir_walk 将返回 NULL
   - 否则，新页的引用计数将递增
完成之后 pgdir_walk 返回指向新页表页的指针。<br />提示：
1. 可以使用 kern/pmap.h 中的 page2pa() 将 PageInfo* 转换为它引用的页面的物理地址
1. x86 MMU 检查页目录和页表中的权限位，因此页目录中的权限较为宽松是安全的
1. 查看 inc/mmu.h 中有用的宏, 这些宏操作页表和页目录条目
函数完成如下：
```c
pte_t* pgdir_walk(pde_t* pgdir, const void* va, int create) {
  // 页目录项
  pde_t* pde;
  // 页表项
  pte_t* pte;
  // 若不存在分配的新页
  struct PageInfo* pp;
  // 通过 va 得到此地址在页目录和页表中分别的偏移
  uintptr_t pdx = PDX(va);
  uintptr_t ptx = PTX(va);
  // 获得页目录项
  pde = &pgdir[pdx];
  // 通过 PTE_P (Present) 位判断页目录项是否存在
  if (*pde & PTE_P) {
    // 如果 pde 存在
    // 通过 PTE_ADDR 得到页表的起始物理地址
    // 再通过 KADDR 得到虚拟地址
    pte = KADDR(PTE_ADDR(*pde));
    // 返回指向该页表项的指针
    return &pte[ptx];
  }
  // 如果 pde 不存在
  // 当 create==false 时, 返回 NULL
  if (!create) {
    return NULL;
  }
  // 如果页分配失败, 返回 NULL
  if (!(pp = page_alloc(ALLOC_ZERO))) {
    return NULL;
  }
  // 将页引用数加一
  pp->pp_ref++;
  // 得到 PageInfo 实际对应的内存地址
  pte = page2kva(pp);
  // 通过 PADDR 得到 pte 对应的物理地址, 
  // 并设置标志位, 具体含义见上
  *pde = PADDR(pte) | (PTE_P | PTE_W | PTE_U);
  // 返回指向该页表项的指针
  return &pte[ptx];
}

🚎boot_map_region()

将虚拟地址为 [va，va+size) 的空间映射到根在 pgdir 的页表中的物理地址为 [pa，pa+size) 的空间。size是 PGSIZE 的倍数，va 和 pa 都是页对齐的。对条目使用 perm | PTE_P 权限位。
此函数仅用于在 UTOP 上设置“静态”映射。因此，它不应该更改映射页上的 pp_ref 字段。

static void boot_map_region(pde_t* pgdir,
                            uintptr_t va,
                            size_t size,
                            physaddr_t pa,
                            int perm) {
  // 得到总页数
  size_t sizes = size / PGSIZE;
  for (int i = 0; i < sizes; i++) {
    // 得到对应的或新的页表条目
    pte_t* pte = pgdir_walk(pgdir, (void*)va, 1);
    if (!pte) {
      panic("boot_map_region(): out of memory\n");
    }
    // 设置页表项的值
    *pte = PTE_ADDR(pa) | perm | PTE_P;
    // pa 与 va 递增
    pa += PGSIZE;
    va += PGSIZE;
  }
}

🚒page_lookup()

page_lookup() 函数返回映射到虚拟地址“va”的页。
如果 pte_store 不为零，则我们将该页的 pte 地址存储在其中。由 page_remove 使用，可用于验证 syscall 参数的页面权限，但大多数调用者不应使用。如果“va”处没有映射页，则返回 NULL。
提示：使用 pgdir_walk 和 pa2page

struct PageInfo* page_lookup(pde_t* pgdir, void* va, pte_t** pte_store) {
  pte_t* pte = pgdir_walk(pgdir, va, 0);
  if (!(pte && (*pte & PTE_P))) {
    return NULL;
  }
  if (pte_store) {
    *pte_store = pte;
  }
  return pa2page(PTE_ADDR(*pte));
}

🚚page_remove()

取消映射虚拟地址“va”处的物理页；如果该地址没有物理页，则不执行任何操作。
要求：

• 物理页中的 pp_ref 计数应该减少
• 如果 ref_count 归零，则应释放物理页
• 如果存在此 PTE，则与“va”对应的 PTE 条目应设置为 0
• 如果从页表中删除条目，则 TLB 必须无效。

提示：使用 page_lookup、tlb_invalidate 和 page_decref 实现

void page_remove(pde_t* pgdir, void* va) {
  pte_t* pte;
  pte_t** pte_store = &pte;
  struct PageInfo* pp;
  pp = page_lookup(pgdir, va, pte_store);
  if (!pp) {
    return;
  }
  // 减引用归零释放
  page_decref(pp);
  // 释放页表项
  **pte_store = 0;
  // 释放 TLB
  tlb_invalidate(pgdir, va);
}

🚛page_insert()

将物理页“pp”映射到虚拟地址“va”；页表条目的权限（低12位）应设置为“perm | PTE_P”。
要求：

• 如果已经有一个页面映射到“va”，那么应该调用 page_remove() 函数释放
• 如有必要，应根据需要分配页表并将其插入“pgdir”
• 如果插入成功，pp->pp_ref应该递增
• 如果“va”以前存在页，则必须清除 TLB

返回值：

• 成功时返回 0
• 如果无法分配页表，则返回 -E_NO_MEM（注意那个负号）

提示：使用 pgdir_walk、page_remove 和 page2pa 实现

int page_insert(pde_t* pgdir, struct PageInfo* pp, void* va, int perm) {
  // 页表项不存在或新建页表项失败则返回 -E_NO_MEM
  pte_t* pte = pgdir_walk(pgdir, va, 1);
  if (!pte) {
    return -E_NO_MEM;
  }
  // 如果页表项的值有效
  if (*pte & PTE_P) {
    // 不同释放 相同 ref 减一
    if (PTE_ADDR(*pte) == page2pa(pp)) {
      pp->pp_ref--;
    } else {
      page_remove(pgdir, va);
    }
  }
  // 设置映射
  pp->pp_ref++;
  *pte = page2pa(pp) | perm | PTE_P;
  return 0;
}

运行结果如下，可以看到 check_page 运行成功了：

wangjq@ubuntu:~/MIT/lab$ make qemu
qemu-system-i386 -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb tcp::26000 -D qemu.log 
6828 decimal is 015254 octal!
Physical memory: 131072K available, base = 640K, extended = 130432K
check_page_free_list() succeeded!
check_page_alloc() succeeded!
check_page() succeeded!
kernel panic at kern/pmap.c:711: assertion failed: check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K>

👖No5

补充 mem_init() 中 check_page() 后缺少的代码。 现在代码应该通过 check_kern_pgdir() 函数和 check_page_installed_pgdir() 函数。

// 要求把 pages 数组所在的页和虚拟地址 UPAGES 相互映射
boot_map_region(kern_pgdir, UPAGES,
                ROUNDUP(sizeof(struct PageInfo) * npages, PGSIZE),
                PADDR(pages), PTE_U | PTE_P);
// 映射内核栈 KSTACKTOP
boot_map_region(kern_pgdir, (KSTACKTOP - KSTKSIZE), KSTKSIZE,
                PADDR(bootstack), PTE_W);
// 映射所有的物理内存
uint32_t kern_size = ROUNDUP((0xFFFFFFFF - KERNBASE), PGSIZE);
boot_map_region(kern_pgdir, KERNBASE, kern_size, 0, PTE_W);

只要注意一下大小的计算即可，其他的没什么好说的。

🎭Q2

此时已填写页面目录中的哪些条目？它们映射到什么地址？它们指向哪里？换言之，请尽可能填写此表

🖼Q3

我们将内核和用户环境放在同一个地址空间中。为什么用户程序不能读写内核的内存？什么特定的机制保护内核内存？

页表项中有读写保护位，以及 PTE_U 区分内核和用户，MMU 实现这种保护机制。

🎨Q4

此操作系统可以支持的最大物理内存量是多少？为什么？

4GB，因为 32 位地址线，可以寻址 4GB 大小。

🧵Q5

如果我们实际拥有最大数量的物理内存，管理内存的空间开销是多少？这个开销是怎么分解的？

页表个数：

每个页表项大小为 4B。
所以页表总大小：

此时我们还需要加上页目录的大小，页目录大小为：

我们还需要加上 pages 数组的大小，这个数组用来记录页面的引用关系：

🧶Q6

重新查看 kern/entry.S 和 kern/entrypgdir.c 中的页表设置。打开分页后，EIP 仍然是一个较低的数字（略高于1MB）。我们在什么时候过渡到在 KERNBASE 之上的 EIP 上运行？在启用分页和开始在 KERNBASE 之上的 EIP 上运行之间，是什么使我们能够继续在低 EIP 下执行呢？为什么这种转变是必要的？