xv6学习，Lab3-Page tables

三、Lab3：page tables

完成实验之前，根据实验提示阅读 xv6 书籍的第 3 章，以及相关文件： kernel/memlayout.h，它记录了内存的布局。 kernel/vm.c，其中包含了大部分虚拟内存代码。 kernel/kalloc.c，其中包含了分配和释放物理内存的代码。 在阅读过程中参考 RISC-V 特权架构手册可能也会有所帮助。以下是这部分内容的主要内容，围绕官方文档的图片和代码展开：

1. 页表硬件（Paging hardware）

   • 页表是最普遍的机制，使用页表和虚拟内存的目的是为了实现进程之间的强隔离，操作系统通过该机制为每个进程提供自己的私有地址空间和内存。页表确定内存地址的含义，以及可以访问物理内存的哪些部分。它们允许xv6隔离不同进程的地址空间，并将它们多路复用到单个物理内存上。RISC-V指令（包括用户指令和内核指令）操作的是虚拟地址。机器的RAM，即物理内存，是通过物理地址来索引的。RISC-V的页表硬件将这两种地址连接起来，把每个虚拟地址映射到一个物理地址上。

   • 如图所示，对于虚拟内存地址，将划分成index和offset两个部分，index用于查找page，而offset则对应的是page中的字节，MU(内存管理单元 ，Memory Management Unit)会将index部分处理成PPN(物理页码，Physical Page Numer)，对应一个4kb的页表，offset部分对应页表中的某个字节。Xv6 在 Sv39 RISC-V 上运行，这意味着一个 64 位的虚拟地址中只有低 39 位被使用；高 25 位未被使用。在这种 Sv39 配置中，从逻辑上讲，RISC-V 页表是一个包含 2^27个页表项（PTE）的数组。每个页表项包含一个 44 位的物理页号（PPN）和一些标志位。分页硬件通过使用 39 位虚拟地址中的高 27 位来索引页表以找到一个页表项，从而将虚拟地址进行转换，并生成一个 56 位的物理地址，该物理地址的高 44 位来自页表项中的物理页号，低 12 位则从原始虚拟地址中复制而来。页表使操作系统能够以 4096（2^12）字节的块为粒度来控制虚拟地址到物理地址的转换。这样的一个块被称为一页。

   • 虚拟地址的高 25 位在地址转换中未被使用，物理地址也有扩展的空间：在页表项（PTE）格式中，物理页号还有额外 10 位的扩展空间。RISC-V 的设计者巧妙地选择了这些数字，2^39 字节等于 512GB，这对于在RISC-V计算机上运行的应用程序有足够的地址空间。

   • 接下来是RISC-V的三级页表机制，使用三级树结构存储在物理内存中，该树的根是一个 4096 字节的页表页面，其中包含 512 个PTE（页表项），这些页表项包含了树中下一级页表页面的物理地址。树中每一级的页表页面都包含 512 个 PTE，用于指向树中下一级的页表页面。如上图所示，分页硬件使用 27 位中的高 9 位来选择根页表页面中的一个 PTE，使用中间 9 位来选择树中下一级页表页面中的一个 PTE，使用低 9 位来选择最后一级的 PTE。高九位，中九位用于寻找低九位的物理地址，在低九位中存储虚拟地址对应的页表的物理地址。

   • CPU 必须从内存中加载三个PTE，以将加载/存储指令中的虚拟地址转换为物理地址，这样做降低了效率，所以使用页表缓存（TLB，Translation Look-aside Buffer）来降低从物理内存中加载 PTE 的开销。当处理器第一次查找某个虚拟地址的时候，硬件将其转换成物理地址，TLB会保存这个从虚拟地址到物理地址的映射关系。当 xv6 更改页表时，它必须告知 CPU 使相应的缓存 TLB 项失效。如果不这样做，那么在稍后的某个时刻，TLB 可能会使用旧的缓存映射，指向一个物理页面，而与此同时该物理页面可能已被分配给另一个进程，这样做可能会修改在其他进程的内存。

   • 每个页表项（PTE）都包含一些标志位，这些标志位告诉分页硬件相关的虚拟地址被允许如何使用。PTE_V 表示该页表项是否存在：如果未设置，对该页的引用会导致异常（即不被允许）。PTE_R 和PTE_W 控制是否允许指令读取或写入该页。PTE_X 控制 CPU 是否可以将该页的内容解释为指令并执行它们。PTE_U 控制用户模式下的指令是否被允许访问该页，如果 PTE_U 未设置，该页表项只能在管理模式下使用。这些标志位在（kernel/riscv.h）中定义。

   • 内核必须将根页表的物理地址写入 satp 寄存器。CPU 将使用其自身 satp 所指向的页表来转换后续指令生成的所有地址。每个 CPU 都有自己的 satp，以便不同的 CPU 可以运行不同的进程，每个进程都有由其自己的页表所描述的私有地址空间。 在进程刚启动时，只有三个页表，分别对应最高级、中间级和最低级的页表，随着代码不断运行，创建更多的页表。

2. 内核地址空间（Kernel address space）

   • Xv6 为每个进程维护一个页表，用于描述每个进程的用户地址空间，此外还有一个单独的页表用于描述内核的地址空间。内核配置其地址空间的布局，以便在可预测的虚拟地址上访问物理内存和各种硬件资源。文件（kernel/memlayout.h）声明了 Xv6 内核内存布局的常量。

   • 在Ubuntu中，我们使用QEMU模拟计算机，其物理内存从物理地址 0x80000000 开始，并至少到 0x88000000，xv6 将其称为 PHYSTOP。QEMU 还同时模拟包括磁盘接口等 I/O 设备，这些设备位于物理地址空间中 0x80000000 以下的位置，内核可以通过读写这些特殊的物理地址来与设备进行交互；这样的读写操作是与设备硬件进行通信，而不是与 RAM 进行通信。

   • 从上图可以看出，内核大多数（PHYSTOP之下）都通过“直接映射”（直线箭头）来访问 RAM 和内存映射设备寄存器；也就是说，将资源映射到虚拟地址，该虚拟地址与物理地址相等。直接映射简化了内核读写物理内存的代码。例如，当 fork 为子进程分配用户内存时，分配器返回该内存的物理地址；当 fork 将父进程的用户内存复制到子进程时，它直接将该地址用作虚拟地址。

   • 内核在运行时必须为页表、用户内存、内核栈和管道缓冲区分配和释放物理内存。 Xv6 将内核结束地址到 PHYSTOP 之间的物理内存用于运行时分配。它每次分配和释放整个 4096 字节的页面。它通过在页面自身中穿线构建一个链表来跟踪哪些页面是空闲的。分配操作包括从链表中移除一个页面；释放操作包括将已释放的页面添加到链表中。

   • 但是几个内核虚拟地址并非直接映射：

     Kernel Stack Pages，每个进程都有自己的内核栈，其被映射到较高位置，以便 xv6 在其下方留出一个未映射的保护页（图中的Guard Page）。保护页的页表项是无效的（即flag中的PTE_V 未设置），它的虚拟地址也不映射到物理地址，不造成物理地址的浪费。如果没有保护页，溢出的栈会覆盖其他内核内存，导致严重错误。

     至于Trampoline Page，它被映射到虚拟地址空间的顶部。在此我们能看到页表的一个有趣用例，一个物理页（图中物理地址被两个箭头指着的地方）在内核的虚拟地址空间中被映射了两次：一次位于虚拟地址空间的顶部，一次是直接映射。这部分内容在Chapter4中有所讲解，先按下不表。

3. 相关代码

   • kernel/memlayout.h中主要就是对上图中右侧物理内存的布局进行定义，如00001000 – boot ROM, provided by qemu，02000000 – CLINT等。

   • xv6 中用于操作地址空间和页表的大部分代码位于 vm.c（kernel/vm.c:1）中。核心数据结构是 pagetable_t，它实际上是一个指向 RISC-V 根页表页的指针；pagetable_t 既可以是内核页表，也可以是每个进程的页表之一。

     核心函数是 walk，用于查找虚拟地址的页表项（PTE），以及 mappages，用于为新的映射安装 PTE。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

     // kernel/vm.c:86 // 返回页表pagetable中与虚拟地址va对应的页表项（PTE）的地址,如果alloc!= 0，则创建任何所需的页表页。 // 一个 64 位虚拟地址被分为五个字段： // 39..63 -- 必须为零。 // 30..38 -- 9 位的二级索引。 // 21..29 -- 9 位的一级索引。 // 12..20 -- 9 位的零级索引。 // 0..11 -- 页内的 12 位字节偏移量。 pte_t * walk(pagetable_t pagetable, uint64 va, int alloc) { // 如果虚拟地址超出最大值，触发panic if(va >= MAXVA) panic("walk"); // 遍历三级页表 for(int level = 2; level > 0; level--) { // 根据当前级别和虚拟地址计算页表项的索引，并获取相应的页表项指针 pte_t *pte = &pagetable[PX(level, va)]; // 如果该页表项有效（PTE_V 位被设置） if(*pte & PTE_V) { // 将页表转换为物理地址，并将其作为新的页表进行下一级的查找 pagetable = (pagetable_t)PTE2PA(*pte); } else { // 如果不允许分配或者分配页表页失败 if(!alloc || (pagetable = (pde_t*)kalloc()) == 0) return 0; // 将新分配的页表页清零 memset(pagetable, 0, PGSIZE); // 设置页表项的物理地址和有效位 *pte = PA2PTE(pagetable) | PTE_V; } } // 返回最低级页表中对应虚拟地址的页表项指针 return &pagetable[PX(0, va)]; }

     以 kvm 开头的函数用于操作内核页表；以 uvm 开头的函数用于操作用户页表；其他函数则可用于两者。copyout 和 copyin 用于将数据复制到作为系统调用参数提供的用户虚拟地址以及从该地址复制出来；它们位于 vm.c 中，因为它们需要显式地转换这些地址，以找到相应的物理内存。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

     // kernel/vm.c:377 // 从用户空间复制到内核空间 // 从给定页表中虚拟地址srcva处复制len个字节到dst // 成功返回0，失败返回-1 int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) { uint64 n, va0, pa0; while(len > 0) { // 将源虚拟地址 srcva 向下取整到页边界，得到 va0 va0 = PGROUNDDOWN(srcva); // 通过页表查找 va0 对应的物理地址 pa0 pa0 = walkaddr(pagetable, va0); // 如果找不到对应的物理地址，返回 -1 表示错误 if(pa0 == 0) return -1; // 计算本次最多可复制的字节数 n，为页大小减去 srcva 到 va0 的偏移 n = PGSIZE - (srcva - va0); // 如果 n 大于剩余要复制的字节数 len，将 n 调整为 len if(n > len) n = len; // 将源物理地址 pa0 + (srcva - va0) 处的 n 个字节复制到 dst memmove(dst, (void *)(pa0 + (srcva - va0)), n); // 减少剩余要复制的字节数 len len -= n; // 目标数据指针 dst 向前移动 n 个字节 dst += n; // 源虚拟地址 srcva 向前移动一页 srcva = va0 + PGSIZE; } return 0; }

     在xv6启动时，main 函数会调用 kvminit（位于 kernel/vm.c:54），通过 kvmmake（位于 kernel/vm.c:20）来创建内核的页表。这个调用发生在 xv6 在 RISC-V 上启用分页之前，因此地址直接指向物理内存。kvmmake 首先分配一个物理内存页来容纳根页表页。然后，它调用 kvmmap 来设置内核所需的转换。这些转换包括内核的指令和数据、直至 PHYSTOP 的物理内存，以及实际上是设备的内存范围。proc_mapstacks（位于 kernel/proc.c:33）为每个进程分配一个内核栈。它调用 kvmmap，将每个栈映射到由 KSTACK 生成的虚拟地址，这样为无效的栈保护页留出了空间。

     kvmmap（位于 kernel/vm.c:132）会调用 mappages（位于 kernel/vm.c:143），mappages 会为一系列虚拟地址到相应物理地址的范围在页表中设置映射。它会以页为间隔，针对该范围内的每个虚拟地址分别进行此操作。对于每个要映射的虚拟地址，mappages 会调用 walk 来查找该地址的页表项（PTE）的地址。然后，它会初始化该 PTE，以保存相关的物理页码、所需的权限（PTE_W、PTE_X 和/或 PTE_R），并设置 PTE_V 来标记该 PTE 为有效（位于 kernel/vm.c:158）。

     main 函数调用 kvminithart（位于 kernel/vm.c:62）来安装内核页表。它将根页表页的物理地址写入到寄存器 satp 中。在此之后，CPU 将使用内核页表来进行地址转换。由于内核使用的是恒等映射，所以下一条指令的现在的虚拟地址将映射到正确的物理内存地址。

   • 分配器位于 kalloc.c（kernel/kalloc.c:1）中。分配器的数据结构是一个可用于分配的物理内存页面的空闲链表。每个空闲页面的链表元素是一个 struct run（kernel/kalloc.c:17，上一章已经使用过）。

     函数 main 调用 kinit 来初始化分配器（kernel/kalloc.c:27）。kinit 将空闲链表初始化为包含内核结束地址到 PHYSTOP 之间的每一个页面。Xv6 应当通过解析硬件提供的配置信息来确定可用的物理内存量。然而，Xv6 假定机器有 128 兆字节的 RAM。kinit 调用 freerange，通过对每个页面调用 kfree 将内存添加到空闲链表中。一个页表项（PTE）只能引用在 4096 字节边界上对齐的物理地址（是 4096 的倍数），所以 freerange 使用 PGROUNDUP 来确保它只释放对齐的物理地址。分配器一开始没有内存；这些对 kfree 的调用为它提供了一些可管理的内存。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

     // kernel/kalloc.c // 空闲页面结构体 struct run { struct run *next; }; // 包含一个自旋锁和一个指向 run 结构体的指针（用于表示空闲链表） struct { struct spinlock lock; // 自旋锁，用于保护空闲链表的操作 struct run *freelist; // 指向空闲链表的头节点 } kmem; // 初始化内存分配器的函数 void kinit() { // 初始化 kmem 结构体中的自旋锁，锁的名称为"kmem" initlock(&kmem.lock, "kmem"); // 调用 freerange 函数，处理从 end 到 PHYSTOP 的内存范围，将其加入空闲链表 freerange(end, (void*)PHYSTOP); } // freerange 函数：将指定范围内的内存页面加入空闲链表 void freerange(void *pa_start, void *pa_end) { char *p; // 定义一个字符指针用于遍历内存范围 p = (char*)PGROUNDUP((uint64)pa_start); // 将起始地址向上取整到页面边界 for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) // 遍历内存范围，以页面大小为步长 kfree(p); // 将当前页面加入空闲链表 }

     分配器有时将地址当作整数来进行算术运算（例如，在 freerange 中遍历所有页面），有时又将地址用作指针来读写内存（例如，操作存储在每个页面中的 run 结构）；这种对地址的双重使用是分配器代码中充满 C 语言类型转换的主要原因。另一个原因是，释放和分配本质上会改变内存的类型。

     函数 kfree（kernel/kalloc.c:47）首先将被释放的内存中的每个字节设置为值 1。这样做会使得在释放内存后仍使用该内存（使用“悬空引用”）的代码读取到垃圾值，而不是原来的有效内容；希望这能使这类代码更快地出错。然后，kfree 将该页面添加到空闲链表的头部：它将 pa 强制转换为指向 struct run 的指针，将空闲链表的原起始位置记录在 r->next 中，并将空闲链表设置为 r。kalloc 会移除并返回空闲链表中的第一个元素。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

     // kernel/kalloc.c:47 // 释放由 pa 指向的物理内存页面，pa 通常应该是通过 kalloc() 调用返回的。 //（初始化分配器时是个例外，见上面的 kinit 函数。） void kfree(void *pa) { struct run *r; // 检查pa是否合法，不合法就触发 panic if(((uint64)pa % PGSIZE)!= 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); // 将被释放的内存中的每个字节设置为值 1 memset(pa, 1, PGSIZE); r = (struct run*)pa; acquire(&kmem.lock); // 将当前页面的 next 指针指向空闲链表的头部 r->next = kmem.freelist; // 将空闲链表的头部设置为当前页面 kmem.freelist = r; release(&kmem.lock); }

     每个进程都有一个单独的页表，当 xv6 在进程之间切换时，它也会更改页表。下图更详细地展示了一个进程的地址空间。一个进程的用户内存从虚拟地址 0 开始，并可以增长到 MAXVA（kernel/riscv.h:360），原则上允许一个进程寻址 256GB 的内存。 一个进程的地址空间由包含程序文本的页面、包含程序预初始化数据的页面、用于栈的页面以及用于堆的页面组成。xv6 使用权限 PTE_R、PTE_W 和 PTE_U 对数据、栈和堆进行映射。

     为了检测用户栈是否超出分配的栈内存，xv6 通过清除 PTE_U 标志在栈的下方放置一个不可访问的保护页（图中的Guard Page）。如果用户栈溢出，并且进程试图使用栈下方的地址，硬件将产生一个页面错误异常。当一个进程向 xv6 请求更多的用户内存时，xv6 会扩展该进程的堆。xv6 首先使用 kalloc 来分配物理页。然后，它会在该进程的页表中添加指向新物理页的页表项（PTE）。xv6 在这些 PTE 中设置flag标志位，当不使用这些PTE时会将 PTE_V 标志清除。

   • sbrk 是进程用于收缩或扩展其内存的系统调用，上一章也有所涉及。该系统调用由 growproc 函数（ kernel/proc.c:260 ）实现。growproc 会根据 n 的正负情况调用 uvmalloc 或 uvmdealloc 。uvmalloc（kernel/vm.c:226 ）使用 kalloc 分配物理内存，并使用 mappages 向用户页表中添加PTE。uvmdealloc 会调用 uvmunmap（ kernel/vm.c:171 ），uvmunmap 使用 walk 查找 PTE，并使用 kfree 释放它们所指向的物理内存。 Xv6 不仅使用进程的页表来告知硬件如何映射用户虚拟地址，还将其作为该进程分配了哪些物理内存页的唯一记录。这就是为什么释放用户内存（ uvmunmap 中）需要检查用户页表的原因。

   • exec 是一个系统调用，它用从一个文件（称为二进制文件或可执行文件）中读取的数据来替换一个进程的用户地址空间。二进制文件通常是编译器和链接器的输出，包含机器指令和程序数据。exec（在 kernel/exec.c:23 ）使用 namei（在 kernel/exec.c:36 ）打开指定的二进制文件路径，namei 在第 8 章中有解释。然后，它读取 ELF 头部。Xv6 二进制文件采用广泛使用的 ELF 格式，在（kernel/elf.h）中定义。一个 ELF 二进制文件由一个 ELF 头部，即 struct elfhdr（在 kernel/elf.h:6 ），以及随后的一系列程序段头部，即 struct proghdr（在 kernel/elf.h:25 ）组成。每个 proghdr 描述了应用程序中必须加载到内存中的一个部分；Xv6 程序有两个程序段头部：一个用于指令，一个用于数据。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

     // Format of an ELF executable file #define ELF_MAGIC 0x464C457FU // "\x7FELF" in little endian // File header struct elfhdr { uint magic; // must equal ELF_MAGIC uchar elf[12]; ushort type; ushort machine; uint version; uint64 entry; uint64 phoff; uint64 shoff; uint flags; ushort ehsize; ushort phentsize; ushort phnum; ushort shentsize; ushort shnum; ushort shstrndx; }; // Program section header struct proghdr { uint32 type; uint32 flags; uint64 off; uint64 vaddr; uint64 paddr; uint64 filesz; uint64 memsz; uint64 align; }; // Values for Proghdr type #define ELF_PROG_LOAD 1 // Flag bits for Proghdr flags #define ELF_PROG_FLAG_EXEC 1 #define ELF_PROG_FLAG_WRITE 2 #define ELF_PROG_FLAG_READ 4

     第一步是快速检查文件是否可能包含一个 ELF 二进制文件。ELF 二进制文件以四个字节的“Magic Number”（魔法数字？？）0x7F、’E’、’L’、’F’，即 ELF_MAGIC（在 kernel/elf.h:3 中）开头。如果 ELF 头部具有正确的Magic Number，exec 就假定该二进制文件是格式良好的。 exec 使用 proc_pagetable（在 kernel/exec.c:49 中）分配一个新的没有用户映射的页表，使用 uvmalloc（在 kernel/exec.c:65 中）为每个 ELF 段分配内存，并使用 loadseg（在 kernel/exec.c:10 中）将每个段加载到内存中。loadseg 使用 walkaddr 来查找分配的内存的物理地址，将 ELF 段的每一页写入该地址，并使用 readi 从文件中读取内容。

     用于 /init（通过 exec 创建的第一个用户程序）的程序段头部看起来像这样：

     我们看到，文本段应从文件中偏移量为 0x1000 的内容加载到内存中的虚拟地址 0x0 处（无写权限）。我们还看到，数据应加载到地址 0x1000，该地址处于页边界，且无执行权限。 程序段头部的文件大小（filesz）可能小于内存大小（memsz），这表明它们之间的差距应使用零填充（用于 C 语言全局变量），而不是从文件中读取。对于 /init，数据的文件大小为 0x10 字节，内存大小为 0x30 字节，因此 uvmalloc 分配足够容纳 0x30 字节的物理内存，但仅从文件 /init 中读取 0x10 字节。

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118

     // kernel/exec.c:36 int exec(char *path, char **argv) { // 定义一堆变量 char *s, *last; int i, off; uint64 argc, sz = 0, sp, ustack[MAXARG], stackbase; struct elfhdr elf; struct inode *ip; struct proghdr ph; pagetable_t pagetable = 0, oldpagetable; // 获取当前进程 struct proc *p = myproc(); begin_op(); // 根据路径获取文件的 inode，如果获取失败则结束操作并返回 -1 if((ip = namei(path)) == 0){ end_op(); return -1; } ilock(ip); // 锁定 inode // 检查ELF头，如果读取ELF头失败，跳转到bad处 if(readi(ip, 0, (uint64)&elf, 0, sizeof(elf))!= sizeof(elf)) goto bad; // 检查ELF的Magic Number是否正确 if(elf.magic!= ELF_MAGIC) goto bad; // 为当前进程分配页表 if((pagetable = proc_pagetable(p)) == 0) goto bad; // 将程序加载到内存中 for(i = 0, off = elf.phoff; i < elf.phnum; i++, off += sizeof(ph)){ // 读取程序头 if(readi(ip, 0, (uint64)&ph, off, sizeof(ph))!= sizeof(ph)) goto bad; // 如果出现程序头类型不是可加载类型，内存大小小于文件大小等等错误，则跳转至bad处 if(ph.type!= ELF_PROG_LOAD) continue; if(ph.memsz < ph.filesz) goto bad; if(ph.vaddr + ph.memsz < ph.vaddr) goto bad; if(ph.vaddr % PGSIZE!= 0) goto bad; uint64 sz1; // 为程序分配内存，如果分配失败则跳转到 bad 标签处 if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz, flags2perm(ph.flags))) == 0) goto bad; sz = sz1; // 将程序段加载到内存中，如果加载失败则跳转到 bad 标签处 if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0) goto bad; } iunlockput(ip); // 解锁并释放 inode end_op(); // 结束操作 ip = 0; // 将 inode 指针置为 0 p = myproc(); // 重新获取当前进程 uint64 oldsz = p->sz; // 保存旧的进程大小 // 在接下来的页边界处分配两页内存 // 使第一页不可访问作为栈保护 // 使用第二页作为用户栈 sz = PGROUNDUP(sz); // 向上取整到页边界 uint64 sz1; if((sz1 = uvmalloc(pagetable, sz, sz + 2 * PGSIZE, PTE_W)) == 0) goto bad; // 如果分配失败，跳转到 bad 标签处 sz = sz1; uvmclear(pagetable, sz - 2 * PGSIZE); // 清除第一页（栈保护页） sp = sz; // 设置栈指针 stackbase = sp - PGSIZE; // 设置栈基址 // 将参数字符串入栈中，并在 ustack 中准备好栈的其余部分 for(argc = 0; argv[argc]; argc++) { if(argc >= MAXARG) goto bad; // 如果参数数量超过最大值，跳转到 bad 标签处 sp -= strlen(argv[argc]) + 1; // 为参数字符串分配空间 sp -= sp % 16; // riscv 栈指针必须 16 字节对齐 if(sp < stackbase) goto bad; // 如果栈空间不足，跳转到 bad 标签处 // 将参数字符串复制到用户空间，如果复制失败则跳转到 bad 标签处 if(copyout(pagetable, sp, argv[argc], strlen(argv[argc]) + 1) < 0) goto bad; ustack[argc] = sp; // 将栈指针保存到ustack中 } ustack[argc] = 0; // 以空指针标记参数列表的结束 sp -= (argc + 1) * sizeof(uint64); sp -= sp % 16; // riscv 栈指针必须 16 字节对齐 if(sp < stackbase) goto bad; // 将 argv[] 指针的数组复制到用户空间，如果复制失败则跳转到 bad 标签处 if(copyout(pagetable, sp, (char *)ustack, (argc + 1) * sizeof(uint64)) < 0) goto bad; p->trapframe->a1 = sp; // 保存程序名称 for(last = s = path; *s; s++) if(*s == '/') last = s + 1; safestrcpy(p->name, last, sizeof(p->name)); // 复制程序名称 // 提交到用户映像 oldpagetable = p->pagetable; // 保存旧的页表 p->pagetable = pagetable; // 设置新的页表 p->sz = sz; // 设置新的进程大小 p->trapframe->epc = elf.entry; // 设置初始程序计数器为 main 函数的入口地址 p->trapframe->sp = sp; // 设置初始栈指针 proc_freepagetable(oldpagetable, oldsz); // 释放旧的页表和相关内存 return argc; // 返回参数数量 // 上方环节出现问题跳转到此处 bad: // 如果页表存在，释放页表和相关内存 if(pagetable) proc_freepagetable(pagetable, sz); // 如果 inode 存在，解锁并释放 inode，结束操作 if(ip){ iunlockput(ip); end_op(); } return -1; // 执行过程中出现错误，返回 -1 }

4. 真实情况

   • xv6 通过内核在虚拟地址和物理地址之间使用直接映射，以及假设在地址 0x8000000 处存在物理 RAM（内核期望在此处加载）而得到了简化。这在 QEMU 上是可行的，但在实际硬件上，这其实是一个糟糕的想法；实际硬件将 RAM 和设备放置在不可预测的物理地址上，因此（例如）在 xv6 期望能够存储内核的 0x8000000 处可能没有 RAM。更严谨的内核设计会利用页表将任意的硬件物理内存布局转换为可预测的内核虚拟地址布局。
   • RISC-V 在物理地址级别上支持保护，但 xv6 并未使用该功能。在具有大量内存的机器上，使用 RISC - V 对“超级页”的支持可能是有意义的。当物理内存较小时，小页面是有意义的，以便能够以精细的粒度进行分配和页面换出到磁盘。例如，如果一个程序只使用 8 千字节的内存，为其分配一个完整的 4 兆字节的物理超级页是浪费的。在具有大量 RAM 的机器上，较大的页面是有意义的，并且可以减少页表操作的开销。 xv6 内核缺乏一个类似 malloc 的分配器，无法为小对象提供内存，这使得内核无法使用需要动态分配的复杂数据结构。一个更复杂的内核可能会分配许多不同大小的小块，而不是像 xv6 那样只分配 4096 字节的块；一个真正的内核分配器需要处理小分配以及大分配。

1. Speed up system calls ()

Some operating systems (e.g., Linux) speed up certain system calls by sharing data in a read-only region between userspace and the kernel. This eliminates the need for kernel crossings when performing these system calls. To help you learn how to insert mappings into a page table, your first task is to implement this optimization for the getpid() system call in xv6.

向页表中插入映射，通过在用户空间和内核之间的只读区域共享数据来优化 getpid()系统调用。

当创建每个进程时，在 USYSCALL（在 memlayout.h 中定义的一个虚拟地址）处映射一个只读页面。在该页面的起始位置，存储一个 struct usyscall（同样在 memlayout.h 中定义），并将其初始化为存储当前进程的 PID。对于本实验，用户空间一侧已提供 ugetpid()，它将自动使用 USYSCALL 映射。如果在运行 pgtbltest 时，ugetpid 测试用例通过，那么您将在本实验的这部分获得满分。

• 用户空间的代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  // user/ulib.c：156 #ifdef LAB_PGTBL int ugetpid(void) { struct usyscall *u = (struct usyscall *)USYSCALL; return u->pid; } #endif // kernel/memlayout.h #ifdef LAB_PGTBL #define USYSCALL (TRAPFRAME - PGSIZE) struct usyscall { int pid; // 进程ID }; #endif

• 给kernel/proc.c中的proc添加一个usyscall用于用户空间和内核空间共享

  1 2	// kernel/proc.c struct usyscall *usyscall;

• 效仿xv6中分配Trapframe的方法来分配usyscall，在页面的整个生命周期中都要对usyscall进行相关的操作，直接在proc.c中搜索Trapframe，与之相关的函数都在下列列出并修改。首先在kernel/proc.c:110的allocproc中分配页面。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

  // kernel/proc.c:110 // 在进程表中查找一个未使用的进程 // 如果找到，初始化在内核中运行所需的状态，并在持有 p->lock 的情况下返回 // 如果没有空闲进程或内存分配失败，则返回 0 static struct proc* allocproc(void) { struct proc *p; for(p = proc; p < &proc[NPROC]; p++) { // 从进程表的起始位置开始，遍历到最后一个进程 acquire(&p->lock); // 获取进程的锁 if(p->state == UNUSED) { // 如果进程的状态为未使用 goto found; // 跳转到 found 标签处 } else { // 如果进程的状态不是未使用 release(&p->lock); // 释放进程的锁 } } return 0; // 如果没有找到未使用的进程，返回 0 found: p->pid = allocpid(); // 为进程分配一个进程 ID p->state = USED; // 将进程的状态设置为已使用 // 分配一个trapframe页面 if((p->trapframe = (struct trapframe *)kalloc()) == 0){ freeproc(p); release(&p->lock); return 0; } // lab3-1 // 为usyscall分配页面 if((p->usyscall = (struct usyscall *)kalloc()) == 0){ freeproc(p); release(&p->lock); return 0; } p->usyscall->pid = p->pid; p->pagetable = proc_pagetable(p); // 为进程分配一个用户页表 if(p->pagetable == 0){ freeproc(p); release(&p->lock); return 0; } // 设置新的上下文，以便从 forkret 开始执行，forkret 会返回到用户空间 memset(&p->context, 0, sizeof(p->context)); // 将进程上下文初始化为 0 p->context.ra = (uint64)forkret; // 设置返回地址为 forkret p->context.sp = p->kstack + PGSIZE; // 设置栈指针 return p; }

• 其次还是在kernel/proc.c中，同样参考Trapframe，释放其物理内存

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  // 释放一个进程结构以及与之相关的数据，包括用户页面。 // 必须持有 p->lock 锁。 static void freeproc(struct proc *p) { if (p->trapframe) // 如果进程的trapframe存在,释放其内存 kfree((void*)p->trapframe); p->trapframe = 0; // 将trapframe设置为 0（表示已释放） // lab3-1 if (p->usyscall) // 如果进程的usyscall存在,释放其内存 kfree((void*)p->usyscall); p->usyscall = 0; // 将tusyscall设置为 0（表示已释放） // 释放进程的页表及其相关内存 if (p->pagetable) proc_freepagetable(p->pagetable, p->sz); // 将进程的其他元素都设置为初试值 p->pagetable = 0; p->sz = 0; p->pid = 0; p->parent = 0; p->name[0] = 0; p->chan = 0; p->killed = 0; p->xstate = 0; p->state = UNUSED; }

• 还需要去kernel/proc.c的proc_pagetable方法中去建立从虚拟内存到物理内存的映射，创建进程的页表。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

  // 为给定的进程创建一个用户页表 pagetable_t proc_pagetable(struct proc *p) { pagetable_t pagetable; // 创建一个空的页表并判断合法性 pagetable = uvmcreate(); if (pagetable == 0) return 0; // 将TRAMPOLINE映射到最高的用户虚拟地址。 if (mappages(pagetable, TRAMPOLINE, PGSIZE, (uint64)trampoline, PTE_R | PTE_X) < 0) { // 尝试将跳板代码映射到页表中 uvmfree(pagetable, 0); // 如果映射失败，释放页表内存 return 0; } // 将TRAPFRAME页面映射到TRAMPOLINE页面的下方 if (mappages(pagetable, TRAPFRAME, PGSIZE, (uint64)(p->trapframe), PTE_R | PTE_W) < 0) { uvmunmap(pagetable, TRAMPOLINE, 1, 0); // 如果映射失败，取消跳板页面的映射 uvmfree(pagetable, 0); // 释放页表内存 return 0; } // lab3-1 // 将USYSCALL映射到TRAPFRAME下方 if(mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall), PTE_R | PTE_U) < 0){ uvmunmap(pagetable, TRAMPOLINE, 1, 0); // 如果映射失败，取消跳板页面的映射 uvmunmap(pagetable, TRAPFRAME, 1, 0); // 释放页表内存 uvmfree(pagetable, 0); return 0; } // 如果没出错，返回创建的页表 return pagetable; }

• 最后在进程关闭时需要解除刚才的映射，kernel/proc.c的proc_pagetable方法中解除，直接调用uvmunmap即可。

  1 2 3 4 5 6 7 8

  void proc_freepagetable(pagetable_t pagetable, uint64 sz) { //...... //lab3-1 uvmunmap(pagetable, USYSCALL, 1, 0); uvmfree(pagetable, sz); }

2.Print a page table ()

为了帮助您直观地理解 RISC-V 页表，也许还能为将来的调试提供帮助，您的第二个任务是编写一个函数来打印页表的内容。 定义一个名为 vmprint() 的函数。它应该接受一个 pagetable_t 类型的参数，并按照下面描述的格式打印该页表。

在 exec.c 中，在 return argc 之前插入 if(p->pid==1) vmprint(p->pagetable) ，以打印第一个进程的页表。如果您通过了 make grade 中的 pte printout 测试，那么您将在本实验的这部分获得满分。

第一行显示 vmprint 的参数。此后，对于每个页表项（PTE）都有一行，包括那些指向页表树中更下层页表页的 PTE。每个 PTE 行根据其在树中的深度用若干个“..”进行缩进。每个 PTE 行显示其在页表页中的 PTE 索引、PTE 位以及从 PTE 中提取的物理地址。不要打印无效的 PTE。在上述示例中，顶层页表页为条目 0 和 255 建立了映射。对于条目 0 的下一层，只有索引 0 被映射，而对于该索引 0 的底层，条目 0、1 和 2 被映射。

• 根据提示，修改kernel/exec.c

  1 2 3

  // kernel/exec.c：132 if(p->pid==1) vmprint(p->pagetable) return argc; // this ends up in a0, the first argument to main(argc, argv)

• 函数 freewalk 可供参考

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  // kernel/vm.c:279 // 递归地释放页表 // 所有叶子映射必须已经被移除。 void freewalk(pagetable_t pagetable) { for(int i = 0; i < 512; i++){ pte_t pte = pagetable[i]; // 获取当前页表项 if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){ // 如果该页表项有效（PTE_V 置位）且PTE_R、PTE_W、PTE_X 未置位 uint64 child = PTE2PA(pte); // 将页表项转换为物理地址 freewalk((pagetable_t)child); // 递归地释放更低级的页表 pagetable[i] = 0; // 将当前页表项置为 0 } else if(pte & PTE_V){ // 如果页表项有效但不符合上述条件，说明是叶子节点，抛出异常 panic("freewalk: leaf"); } } kfree((void*)pagetable); // 释放当前页表 }

• 在 kernel/defs.h 中定义 vmprint 的原型

  1 2	// ...... void vmprint(pagetable_t pagetable);

• 在kernel/vm.c中创建vmprint()，也采用递归的思想

  在 printf 函数中使用 %p 来打印出完整的 64 位十六进制 PTE（页表项）和地址

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  // 递归到的页表结点和递归深度 void recursionprint(pagetable_t pagetable,int depth){ for(int i = 0; i < 512; i++){ pte_t pte = pagetable[i]; // 如果页表项有效 if(pte & PTE_V){ uint64 child = PTE2PA(pte); // 将页表项转换为物理地址 // 如果是最高级的页表 if(depth == 0){ printf("..%d: pte %p pa %p\n",i,pte,child); } // 如果是第二级的页表 if(depth == 1){ printf(".. ..%d: pte %p pa %p\n",i,pte,child); } // 如果已经到了三级页表最后一级 if(depth == 2){ printf(".. .. ..%d: pte %p pa %p\n",i,pte,child); } // 判断还有没有下一级页表，如果是叶子结点的话，PTE_R,W,X中至少有一个为1 if((pte & (PTE_R|PTE_W|PTE_X)) == 0){ recursionprint((pagetable_t)child,depth + 1); } } } } // 调用的函数，按照要求输出内容并启动递归 void vmprint(pagetable_t pagetable){ printf("page table %p\n", pagetable); recursionprint(pagetable, 0); }

3.Detect which pages have been accessed ()

一些垃圾回收器（一种自动内存管理的形式）可以从有关哪些页面已被访问（读取或写入）的信息中受益。在本实验的这一部分中，您将为 xv6 添加一个新功能，通过检查 RISC-V 页表中的访问位，检测并向用户空间报告此信息。当 RISC-V 硬件页遍历器解决 TLB 未命中时，会在页表项（PTE）中标记这些位。

任务是实现 pgaccess() 这个系统调用，用于报告哪些页面已被访问。该系统调用有三个参数。首先，它需要一个起始的用户页面的虚拟地址作为要检查的第一个页面的地址。其次，它需要一个要检查的页面数量。最后，它需要一个用户地址，指向一个用于存储结果的缓冲区，结果以位掩码的形式存储（一种数据结构，每页使用一位，其中第一页对应最低有效位）。如果在运行 pgtbltest 时 pgaccess 测试用例通过，那么将在本实验的这部分获得满分。

• 根据实验提示，阅读 user/pgtbltest.c 中的 pgaccess_test() 以了解 pgaccess 的使用方法。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  // user/pgtbltest.c void pgaccess_test() { char *buf; unsigned int abits; printf("pgaccess_test starting\n"); testname = "pgaccess_test"; buf = malloc(32 * PGSIZE); // 分配32个页面大小的内存空间到buf if (pgaccess(buf, 32, &abits) < 0) // 调用pgaccess函数 err("pgaccess failed"); buf[PGSIZE * 1] += 1; // 对第二个页面的对应位置进行操作 buf[PGSIZE * 2] += 1; // 对第三个页面的对应位置进行操作 buf[PGSIZE * 30] += 1; // 对第三十一个页面的对应位置进行操作 if (pgaccess(buf, 32, &abits) < 0) // 再次调用 pgaccess 函数 err("pgaccess failed"); // 检查访问位是否与预期相符 if (abits!= ((1 << 1) | (1 << 2) | (1 << 30))) err("incorrect access bits set"); free(buf); // 释放空间 printf("pgaccess_test: OK\n"); }

  这里需要弄明白需要返回的结果的形式，bitmask，就以上方的代码为例，有三十二个页面，就返回一个三十二位的二进制数，每一位代表一个页面，如果这个页面被访问，就把这一位从0变成1，上方代码返回的bitmask为1000000000000000000000000000110。

• 需要在 kernel/riscv.h 中定义 PTE_A（访问位）。参考RISC-V手册（如下图）来定义PTE_A的值，这一位就用来判断该地址是否被访问过。

  1 2 3 4 5

  // kernel/riscv.h // ...... #define PTE_U (1L << 4) // user can access #define PTE_X (1L << 3) #define PTE_A (1L << 6) // lab3-3

• 在 kernel/sysproc.c 中实现 sys_pgaccess() ，需要使用 argaddr() 和 argint() 从用户空间来获取参数。 对于输出位掩码，在内核中存储一个临时缓冲区，并在填充正确的位后通过 copyout() 将其复制到用户空间会更容易。 还需要对可扫描的页面数量设置一个上限。kernel/vm.c 中的 walk() 用于找到正确的页表项（PTE）。在检查 PTE_A 是否设置后，一定要将其清除。否则，将无法确定该页面是否在上次调用 pgaccess() 后被访问过（即，该位将永远被设置）。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

  // kernel/sysproc.c #ifdef LAB_PGTBL int sys_pgaccess(void) { // 根据实验提示，使用argaddr和argint获取参数 // 三个参数，第一个是需要检查的页面的起始地址，第二个是页面数量，第三个是返回的bitmask uint64 startaddr; int pagenum; int bitmask; argaddr(0, &startaddr); argint(1, &pagenum); argint(2, &bitmask); // 获取当前进程 struct proc* p = myproc(); pte_t *pte; uint64 result = 0; // 从起始地址开始遍历页面 for(int i = 0; i < pagenum; i++){ // 使用walk通过地址获取PTE if((pte = walk(p->pagetable, startaddr + i * PGSIZE, 0)) == 0){ printf("error"); return -1; } // 如果PTE_A置位 if(*pte & PTE_A){ // 用位运算把从右到左的第i位从0变1 result = result | (1L << i); // 根据提示，调用完pgaccess后将PTE_A置0 *pte &= (~(PTE_A)); } } // 最后根据提示，把结果用copyout复制到用户空间 if(copyout(p->pagetable, bitmask, (char *)&result, sizeof(result)) < 0){ printf("error"); return -1; } return 0; } #endif

• 调用bgtbltest，没有通过测试，原因为pgtbltest: pgaccess_test failed: incorrect access bits set, pid=3，修改用户空间的函数输出abits发现为0，发现是result忘了初始化为0，上方代码已经改正。

• 简单总结，本章学习了xv6操作系统中页表的具体实现：RISC-V的三级页表机制，虚拟地址和物理地址的转换，使用页表缓存（TLB）降低加载PTE的开销，PTE的标志位，使用页表机制实现进程间的隔离以防止进程的物理内存相互污染等待。在实验部分，使用了用户空间和内核空间共享的区域来加速系统调用，学习了xv6如何查找TLB并打印，复习了以前学习过的C语言的位运算并使用位运算来操作TLB的标志位。