6.S081的Lab学习——Lab3: page tables

---

前言

一个本硕双非的小菜鸡，备战24年秋招。打算尝试6.S081，将它的Lab逐一实现，并记录期间心酸历程。
代码下载

官方网站：6.S081官方网站

安装方式：
通过 APT 安装 （Debian/Ubuntu）
确保你的 debian 版本运行的是 “bullseye” 或 “sid”（在 ubuntu 上，这可以通过运行 cat /etc/debian_version 来检查），然后运行：

sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu 
1

（“buster”上的 QEMU 版本太旧了，所以你必须单独获取。

qemu-system-misc 修复
此时此刻，似乎软件包 qemu-system-misc 收到了一个更新，该更新破坏了它与我们内核的兼容性。如果运行 make qemu 并且脚本在 qemu-system-riscv64 -machine virt -bios none -kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img，if=none，format=raw，id=x0 -device virtio-blk-device，drive=x0，bus=virtio-mmio-bus.0 之后出现挂起
，
则需要卸载该软件包并安装旧版本：

  $ sudo apt-get remove qemu-system-misc
  $ sudo apt-get install qemu-system-misc=1:4.2-3ubuntu6
1
2

在 Arch 上安装

sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-arch-extra
1

测试您的安装
若要测试安装，应能够检查以下内容：

$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (GCC) 10.1.0
...

$ qemu-system-riscv64 --version
QEMU emulator version 5.1.0
1
2
3
4
5
6

您还应该能够编译并运行 xv6： 要退出 qemu，请键入：Ctrl-a x。

# in the xv6 directory
$ make qemu
# ... lots of output ...
init: starting sh
$
1
2
3
4
5

---

一、Print a page table (easy)

编写一个打印页表内容的函数。

定义一个名为vmprint()的函数。它应当接收一个pagetable_t作为参数，并以下面描述的格式打印该页表。在exec.c中的return argc之前插入if(p->pid==1) vmprint(p->pagetable)，以打印第一个进程的页表。如果你通过了pte printout测试的make grade，你将获得此作业的满分。

现在，当您启动xv6时，它应该像这样打印输出来描述第一个进程刚刚完成exec()inginit时的页表：

page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000
1
2
3
4
5
6
7
8
9
10

第一行显示vmprint的参数。之后的每行对应一个PTE，包含树中指向页表页的PTE。每个PTE行都有一些“…”的缩进表明它在树中的深度。每个PTE行显示其在页表页中的PTE索引、PTE比特位以及从PTE提取的物理地址。不要打印无效的PTE。在上面的示例中，顶级页表页具有条目0和255的映射。条目0的下一级只映射了索引0，该索引0的下一级映射了条目0、1和2。

您的代码可能会发出与上面显示的不同的物理地址。条目数和虚拟地址应相同。

提示：

1. 你可以将vmprint()放在kernel/vm.c中
2. 使用定义在kernel/riscv.h末尾处的宏
3. 函数freewalk可能会对你有所启发
4. 将vmprint的原型定义在kernel/defs.h中，这样你就可以在exec.c中调用它了
5. 在你的printf调用中使用%p来打印像上面示例中的完成的64比特的十六进制PTE和地址

切换分支执行操作

git stash
git fetch
git checkout pgtbl
make clean
make qemu
1
2
3
4
5

解析：

没啥特别的，照着解析做就行了。其中函数freewalk有一句if判断告诉我们如何去递归遍历获取所有的页表项内容

if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0)
1

依葫芦画瓢，注意提示5要用%p打印：
用了下递归，总之不难

void
vmprint(pagetable_t pagetable)
{
  printf("page table %p\n", pagetable);
  paptprint(pagetable, 0);
}

void
paptprint(pagetable_t pagetable, int depth)
{
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if(pte & PTE_V) {
    	printf("..");
    	for(int j = 0; j < depth; j++)
      	printf(" ..");
    
    	printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    
    	if((pte & (PTE_R|PTE_W|PTE_X)) == 0) {
      	// this PTE points to a lower-level page table.
      	  uint64 child = PTE2PA(pte);
      	  paptprint((pagetable_t)child, depth + 1);
    	}
    }
  }
  return;
}
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

记得在kernel/defs.h中定义

void            vmprint(pagetable_t);
void            paptprint(pagetable_t, int);
1
2

最后在exec.c中的return argc之前插入if(p->pid==1) vmprint(p->pagetable)

......
  p->trapframe->epc = elf.entry;  // initial program counter = main
  p->trapframe->sp = sp; // initial stack pointer
  proc_freepagetable(oldpagetable, oldsz);
  
  if(p->pid==1) vmprint(p->pagetable);

  return argc; // this ends up in a0, the first argument to main(argc, argv)
1
2
3
4
5
6
7
8

make qemu一下

二、A kernel page table per process (hard)

Xv6有一个单独的用于在内核中执行程序时的内核页表。内核页表直接映射（恒等映射）到物理地址，也就是说内核虚拟地址x映射到物理地址仍然是x。Xv6还为每个进程的用户地址空间提供了一个单独的页表，只包含该进程用户内存的映射，从虚拟地址0开始。因为内核页表不包含这些映射，所以用户地址在内核中无效。因此，当内核需要使用在系统调用中传递的用户指针（例如，传递给write()的缓冲区指针）时，内核必须首先将指针转换为物理地址。本节和下一节的目标是允许内核直接解引用用户指针。

你的第一项工作是修改内核来让每一个进程在内核中执行时使用它自己的内核页表的副本。修改struct proc来为每一个进程维护一个内核页表，修改调度程序使得切换进程时也切换内核页表。对于这个步骤，每个进程的内核页表都应当与现有的的全局内核页表完全一致。如果你的usertests程序正确运行了，那么你就通过了这个实验。

阅读本作业开头提到的章节和代码；了解虚拟内存代码的工作原理后，正确修改虚拟内存代码将更容易。页表设置中的错误可能会由于缺少映射而导致陷阱，可能会导致加载和存储影响到意料之外的物理页存页面，并且可能会导致执行来自错误内存页的指令。

提示：

1. 在struct proc中为进程的内核页表增加一个字段
2. 为一个新进程生成一个内核页表的合理方案是实现一个修改版的kvminit，这个版本中应当创造一个新的页表而不是修改kernel_pagetable。你将会考虑在allocproc中调用这个函数
3. 确保每一个进程的内核页表都关于该进程的内核栈有一个映射。在未修改的XV6中，所有的内核栈都在procinit中设置。你将要把这个功能部分或全部的迁移到allocproc中
4. 修改scheduler()来加载进程的内核页表到核心的satp寄存器(参阅kvminithart来获取启发)。不要忘记在调用完w_satp()后调用sfence_vma()
5. 没有进程运行时scheduler()应当使用kernel_pagetable
6. 在freeproc中释放一个进程的内核页表
7. 你需要一种方法来释放页表，而不必释放叶子物理内存页面。
8. 调式页表时，也许vmprint能派上用场
9. 修改XV6本来的函数或新增函数都是允许的；你或许至少需要在kernel/vm.c和kernel/proc.c中这样做（但不要修改kernel/vmcopyin.c, kernel/stats.c, user/usertests.c, 和user/stats.c）
10. 页表映射丢失很可能导致内核遭遇页面错误。这将导致打印一段包含sepc=0x00000000XXXXXXXX的错误提示。你可以在kernel/kernel.asm通过查询XXXXXXXX来定位错误。

一旦修复了编译问题，就运行sysinfotest；但由于您还没有在内核中实现系统调用，执行将失败。

sysinfo需要将一个struct sysinfo复制回用户空间；请参阅sys_fstat()(kernel/sysfile.c)和filestat()(kernel/file.c)以获取如何使用copyout()执行此操作的示例。
要获取空闲内存量，请在kernel/kalloc.c中添加一个函数
要获取进程数，请在kernel/proc.c中添加一个函数。

解析：

首先在kernel/proc.h里面的struct proc加上内核页表

  pagetable_t pagetable;       // User page table
  pagetable_t kernelpagetable;
  struct trapframe *trapframe; 
1
2
3

然后借鉴kvminit函数内容，为每个进程创建一个创建内核页表。

pagetable_t
proc_kpt_init()
{
  pagetable_t kpt = uvmcreate();
  
  // uart registers
  kummap(kpt, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  kummap(kpt, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  //这句有点疑问，有的参考文献说由于文章提示：复制到进程的内核页表，最多不超过PLIC，然后可以看到在PLIC下面只有CLINT，所以这句应该没有。我看的版本没有这个提示，就留下来了
  kummap(kpt, CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  kummap(kpt, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  kummap(kpt, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  kummap(kpt, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  kummap(kpt, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  
  return kpt;
}
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

记得修改kvminit()函数，修改为只初始化内核态的内核页表。

void
kvminit()
{
  kernel_pagetable = proc_kpt_init();
}
1
2
3
4
5

因为我们在新写的proc_kpt_init函数中新加了kummap（比kvmmap多加了个参数），所以要在函数定义中增加。

void
kummap(pagetable_t pt, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pt, va, sz, pa, perm) != 0)
    panic("kummap");
}
1
2
3
4
5
6

然后在 defs.h中修改：

void            kummap(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     proc_kpt_init(void);
1
2

之后在allocproc函数，也就是查询proc结构体的部分调用上面写好的函数。在找到然后调用的found处写就可以。跟上面那个差不多。

  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  
  p->kernelpagetable = proc_kpt_init();
  if(p->kernelpagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接下来将procinit函数中和内存栈相关的代码给剪切并将代码复制到allocproc的合适位置，放在进程内核页表被初始化的后面就不错。

  p->kernelpagetable = proc_kpt_init();
  if(p->kernelpagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  
  // Allocate a page for the process's kernel stack.
  // Map it high in memory, followed by an invalid
  // guard page.
  char *pa = kalloc();
  if(pa == 0)
    panic("kalloc");
  uint64 va = KSTACK((int) (p - proc));
  //这句记得修改
  kummap(p->kernelpagetable, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  p->kstack = va;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

接下来到了4与5，简单来说就是获取时候切上去，不用的时候切回来。
提示参阅kvminithart，这个函数在vm.c中
总共就两句，一个是设置地址空间转换参数（SATP），咱把传入参数改了就行，第二个同步虚拟内存访问，保持不动。
最后直接调用调用kvminithart函数就能把Xv6的内核页表加载回去。

这个在proc.c的scheduler里

	w_satp(MAKE_SATP(p->kernelpagetable));
	sfence_vma();
        
    swtch(&c->context, &p->context);
        
    kvminithart();
1
2
3
4
5
6

最后在freeproc中添加回收这个进程的内核页表：
这段我参考大佬写的
释放进程 p 的内核栈（kernel stack）和内核页表（kernel page table）

.......
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  if (p->kernelpagetable) {
        uvmunmap(p->kernelpagetable, p->kstack, 1, 1);
        p->kstack = 0;
        p->kstack = 0;
        free_kernel_pgtbl(p->kernelpagetable, 0);
        p->kernelpagetable = 0;
  }
  .......
1
2
3
4
5
6
7
8
9
10
11

释放进程 p 的内核栈比较简单，调用uvmunmap可以解除映射。
然后实现释放进程的内核页表

void free_kernel_pgtbl(pagetable_t pgtbl, int depth) {
    if (depth == 2) {
        kfree((void *)pgtbl);
        return;
    }

    for (int i = 0; i < 512; i++) {
        pte_t *pte = &pgtbl[i];
        if (*pte & PTE_V) {
            free_kernel_pgtbl((pagetable_t)(PTE2PA(*pte)), depth + 1);
        }
    }
    kfree((void *)pgtbl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

该函数需要递归地释放这个内核页表，并且不能真正地删除物理页面。

将新定义这函数定义添加到 kernel/defs.h 中

void            free_kernel_pgtbl(pagetable_t, int);
1

最后将修改vm.c中的kvmpa，将原先的kernel_pagetable改成myproc()->kernelpagetable，使用进程的内核页表。

//加头文件
#include "spinlock.h" 
#include "proc.h"
.......
  uint64 pa;
  
  pte = walk(myproc()->kernelpagetable, va, 0);
  if(pte == 0)
.......
1
2
3
4
5
6
7
8
9

经验之谈：注意路径！注意路径！注意路径！！！
我修改成另一个vm.c了，特别傻逼还看不出来哪错了

最后也是成功输出

三、Simplify copyin/copyinstr（hard）

内核的copyin函数读取用户指针指向的内存。它通过将用户指针转换为内核可以直接解引用的物理地址来实现这一点。这个转换是通过在软件中遍历进程页表来执行的。在本部分的实验中，您的工作是将用户空间的映射添加到每个进程的内核页表（上一节中创建），以允许copyin（和相关的字符串函数copyinstr）直接解引用用户指针。

将定义在kernel/vm.c中的copyin的主题内容替换为对copyin_new的调用（在kernel/vmcopyin.c中定义）；对copyinstr和copyinstr_new执行相同的操作。为每个进程的内核页表添加用户地址映射，以便copyin_new和copyinstr_new工作。如果usertests正确运行并且所有make grade测试都通过，那么你就完成了此项作业。

此方案依赖于用户的虚拟地址范围不与内核用于自身指令和数据的虚拟地址范围重叠。Xv6使用从零开始的虚拟地址作为用户地址空间，幸运的是内核的内存从更高的地址开始。然而，这个方案将用户进程的最大大小限制为小于内核的最低虚拟地址。内核启动后，在XV6中该地址是0xC000000，即PLIC寄存器的地址；请参见kernel/vm.c中的kvminit()、kernel/memlayout.h和文中的图3-4。您需要修改xv6，以防止用户进程增长到超过PLIC的地址。

一些提示：

1. 先用对copyin_new的调用替换copyin()，确保正常工作后再去修改copyinstr
2. 在内核更改进程的用户映射的每一处，都以相同的方式更改进程的内核页表。包括fork(), exec(), 和sbrk().
3. 不要忘记在userinit的内核页表中包含第一个进程的用户页表
4. 用户地址的PTE在进程的内核页表中需要什么权限？(在内核模式下，无法访问设置了PTE_U的页面）
5. 别忘了上面提到的PLIC限制

Linux使用的技术与您已经实现的技术类似。直到几年前，许多内核在用户和内核空间中都为当前进程使用相同的自身进程页表，并为用户和内核地址进行映射以避免在用户和内核空间之间切换时必须切换页表。然而，这种设置允许边信道攻击，如Meltdown和Spectre。

解析：

首先需要将vmcopyin.c中的copyin_new函数和copyinstr_new函数添加到在defs.h中

// vmcopyin.c
//如果编译提示没检测到这俩函数定义，那么可以试试将这两个函数定义提前
int             copyin_new(pagetable_t, char *, uint64, uint64);
int             copyinstr_new(pagetable_t, char *, uint64, uint64);
1
2
3
4

然后在vm.c中把copyin函数和copyinstr函数替换成以上两个

int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  return copyin_new(pagetable, dst, srcva, len);
}
int
copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
  return copyinstr_new(pagetable, dst, srcva, max);
}
1
2
3
4
5
6
7
8
9
10

接下来可以半参考uvmalloc和uvmcopy函数写复制函数
首先将oldsz向上取整到最近的页大小，然后就是循环遍历并复制页表条目
其中主要是对PTE进行操作。

void
kvmcopymappings(pagetable_t pagetable, pagetable_t kernelpagetable, uint64 oldsz, uint64 newsz)
{
  pte_t *pte_from, *pte_to;
  uint64 pa, i;
  uint flags;

  oldsz = PGROUNDUP(oldsz);
  for(i = oldsz; i < newsz; i += PGSIZE){
    if((pte_from = walk(pagetable, i , 0)) == 0){
      panic("kvmcopymappings: src pte does not exist");
    }
    if((pte_to = walk(kernelpagetable, i , 1)) == 0){
      panic("kvmcopymappings: pte walk failed");
    }
    pa = PTE2PA(*pte_from);
    flags = (PTE_FLAGS(*pte_from)) & (~PTE_U);
    *pte_to = PTE2PAE(pa) | flags;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

记得defs.h中添加定义

void            kvmcopymappings(pagetable_t, pagetable_t, uint64, uint64);
1

然后就是在内核更改进程的用户映射的每一处，都以相同的方式更改进程的内核页表。包括fork(), exec(), 和sbrk().
exec（这个在exec.c中）

  stackbase = sp - PGSIZE;
  
  kvmcopymappings(pagetable, p->kernelpagetable, 0, sz);

  // Push argument strings, prepare rest of stack in ustack.
  for(argc = 0; argv[argc]; argc++) {
1
2
3
4
5
6

fork（这个在proc.c中）

......
  np->sz = p->sz;
  
  kvmcopymappings(np->pagetable, np->kernelpagetable, 0, np->sz);

  np->parent = p;
1
2
3
4
5
6

sbrk（这个在sysproc.c中，叫做sys_sbrk(void)），发现本质是调用的growproc函数，分别在分配和释放的情况下调用函数。为了防止用户进程增长到超过PLIC的地址，应修改这个函数。

growproc这个函数在proc.c中
加上限制并进行复制。

  if(n > 0){
  if (PGROUNDUP(sz + n) >= PLIC){
      return -1;
    }
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    kvmcopymappings(p->pagetable, p->kernelpagetable, sz - n, sz);
  } else if(n < 0){
1
2
3
4
5
6
7
8
9

make qemu一下