Lab3: page tables (hard!) 详解

Lab3: page tables (hard!)

这个实验难度被MIT的老师评价为第一，需要阅读大量代码

Print a page table (easy)

• kernel/memlayout.h，它捕获了内存的布局。
• kernel/vm.c，其中包含大多数虚拟内存（VM）代码。
• kernel/kalloc.c，它包含分配和释放物理内存的代码。

YOUR JOB

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

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

第一步

第三章的内容，可以发现是mappages初始化的PTE，所以应先阅读该函数，我加了注释

int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
    uint64 a, last;pte_t *pte;a = PGROUNDDOWN(va);last = PGROUNDDOWN(va + size - 1);for(;;){
    if((pte = walk(pagetable, a, 1)) == 0) //为虚拟地址找到PTE (最后一层)return -1;if(*pte & PTE_V)  //地址已经有效 报错panic("remap");*pte = PA2PTE(pa) | perm | PTE_V; //初始化PTE以保存相关的物理页号、所需权限（PTE_W、PTE_X或PTE_R）以及用于标记PTE有效的PTE_Vif(a == last)break;a += PGSIZE;pa += PGSIZE;}return 0;
}

第二步

读freewalk，加了点注释

void
freewalk(pagetable_t pagetable)
{
    // 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) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
     //不是最后一层// this PTE points to a lower-level page table.uint64 child = PTE2PA(pte);freewalk((pagetable_t)child); //递归pagetable[i] = 0;} else if(pte & PTE_V){
     //有效 freewalk失败panic("freewalk: leaf");}}kfree((void*)pagetable);
}

第三步

第一个任务就是打印pagetable里的内容，一共有3级，递归打印出来即可，最后一层如上所示给予了PTE_W、PTE_X或PTE_R 的权限，结合输出格式输出即可

void
proto_vmprint(pagetable_t pagetable, int level)
{
    for(int i = 0; i < 512; i++){
     //遍历每一层pte_t pte = pagetable[i];if((pte & PTE_V)){
     //有效for (int j = 0; j < level; j++){
    if (j == 0) printf("..");else printf(" ..");}uint64 child = PTE2PA(pte);printf("%d: pte %p pa %p\n", i, pte, child);if ((pte & (PTE_R|PTE_W|PTE_X)) == 0) // 不是最后一层proto_vmprint((pagetable_t)child, level + 1); // 打印下一层}}
}void
vmprint(pagetable_t pagetable) {
    printf("page table %p\n", pagetable);vmprint_helper(pagetable,1);
}

并将vmprint的原型定义在***kernel/defs.h***中，然后在exec.c中调用它即可

给每一个进程弄一个kernel_pagetable (hard)

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

YOUR JOB

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

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

提示：

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

第一步 添加一个内核页表

在vm.c中struct proc中添加一个 pagetable
为一个新进程生成一个内核页表的合理方案是实现一个修改版的
kvminit(main.c调用它为内核创建第一个页表，地址是直接引用物理内存)
添加一个用户进程自己的pagetable，kvm换成uvm开头加一个参数，自己仿照写一个uvmmap即可

// 构建每个用户进程自己的内核映射表
pagetable_t
proc_kpt_init()
{
    pagetable_t kpt; //用户进程自己的pagetablekpt = uvmcreate(); //create an empty user page table, returns 0 if out of memory.if (kpt == 0) return 0;uvmmap(kpt, UART0, UART0, PGSIZE, PTE_R | PTE_W);uvmmap(kpt, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);uvmmap(kpt, CLINT, CLINT, 0x10000, PTE_R | PTE_W);uvmmap(kpt, PLIC, PLIC, 0x400000, PTE_R | PTE_W);uvmmap(kpt, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);uvmmap(kpt, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);uvmmap(kpt, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);return kpt;
}// 添加用户进程的映射到kernel pagetable
void 
uvmmap(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm)
{
    if(mappages(pagetable, va, sz, pa, perm) != 0) //mappages初始化PTEpanic("kvmmap");
}

在allocproc中调用这个函数

  // 初始化用户进程的kernel_ptp->kernel_pt = proc_kpt_init();if (p->kernel_pt == 0){
    freeproc(p);release(&p->lock);return 0;}

第二步 确保内核页表映射到该进程的内核栈

**确保每一个进程的内核页表都关于该进程的内核栈有一个映射。**在未修改的XV6中，所有的内核栈都在procinit中设置。你将要把这个功能部分或全部的迁移到确保每一个进程的内核页表都关于该进程的内核栈有一个映射。中

先来看一下 procinit，添加了一些注释，来决定要不要把功能迁移到allocproc

// initialize the proc table at boot time.
void
procinit(void)
{
    struct proc *p;initlock(&pid_lock, "nextpid");for(p = proc; p < &proc[NPROC]; p++) {
     //遍历所有进程initlock(&p->lock, "proc"); //添加锁// 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));kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W); // 添加映射到kernel pagetablep->kstack = va; //添加va-virtual adress}kvminithart(); //将硬件页表寄存器切换到内核的页表，并启用分页。
}

这里只需要将 关于 确保每一个进程的内核页表都关于该进程的内核栈有一个映射 的部分添加进去allocproc即可，即19行的内容 (并修改kvmmap为uvmmap)。

uvmmap(p->kernel_pt, KSTACK((int) (p - proc)), kvmpa(KSTACK((int) (p - proc))), PGSIZE, PTE_R | PTE_W); // 添加映射到kernel pagetablep->kstack = KSTACK((int) (p - proc)); //添加va-virtual adress

第三步 修改scheduler

修改scheduler()来加载进程的内核页表到核心的satp寄存器(参阅kvminithart来获取启发)。不要忘记在调用完w_satp()后调用sfence_vma()

没有进程运行时scheduler()应当使用kernel_pagetable全局的那个

void
kvminithart() //将硬件页表寄存器切换到内核的页表，并启用分页。
{
    w_satp(MAKE_SATP(kernel_pagetable)); //主管地址转换和保护；保存页表的地址。sfence_vma(); //刷新 TLB。 
}static inline void 
w_satp(uint64 x)
{
    asm volatile("csrw satp, %0" : : "r" (x));
}// Scheduler never returns. It loops, doing:
// - choose a process to run.
// - swtch to start running that process.
// - eventually that process transfers control
// via swtch back to the scheduler.
void
scheduler(void)
{
    struct proc *p;struct cpu *c = mycpu();c->proc = 0;for(;;){
    // Avoid deadlock by ensuring that devices can interrupt.intr_on();int found = 0;for(p = proc; p < &proc[NPROC]; p++) {
     //遍历所以进程acquire(&p->lock);if(p->state == RUNNABLE) {
     //进程没有运行// Switch to chosen process. It is the process's job// to release its lock and then reacquire it// before jumping back to us.p->state = RUNNING;c->proc = p;//加载进程的内核页表到核心的`satp`寄存器w_satp(MAKE_SATP(p->kernel_pt));sfence_vma();swtch(&c->context, &p->context); //切换进程kvminithart(); //没有进程运行时`scheduler()`应当使用`kernel_pagetable`// Process is done running for now.// It should have changed its p->state before coming back.c->proc = 0;found = 1;}release(&p->lock);}
#if !defined (LAB_FS)if(found == 0) {
    intr_on();asm volatile("wfi");}
#else;
#endif}
}

第四步 释放内核页表

• 在freeproc中释放一个进程的内核页表
• 你需要一种方法来释放页表，而不必释放叶子物理内存页面。
• 调式页表时，也许vmprint能派上用场

在 freeproc 中加入清理进程的内核页表的代码，注意这里只需要清理三层页表，不需要清理最后一层页表实际指向的物理页，进程的内核页表只是一层额外的重复映射信息，不该管理实际物理页。

// free a proc structure and the data hanging from it,
// including user pages.
// p->lock must be held.
static void
freeproc(struct proc *p)
{
    if(p->trapframe)kfree((void*)p->trapframe);p->trapframe = 0;if(p->pagetable)proc_freepagetable(p->pagetable, p->sz);p->pagetable = 0;// 删除kernel pagetableif (p->kernel_pt)proc_freekpt(p->kernel_pt);p->kernel_pt = 0;  p->kstack = 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;
}

// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(pagetable_t pagetable)
{
    // 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) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
    // this PTE points to a lower-level page table.uint64 child = PTE2PA(pte);freewalk((pagetable_t)child);pagetable[i] = 0;} else if(pte & PTE_V){
     //如果叶子有效 报错panic("freewalk: leaf");}}kfree((void*)pagetable);
}void 
proc_freekpt(pagetable_t pagetable) //直接参考freewlk写就行，叶子就不需要再递归了,清除页表信息即可
{
    // 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)){
     //有效pagetable[i] = 0; //清空if ((pte & (PTE_R|PTE_W|PTE_X)) == 0) //不是叶子{
    uint64 child = PTE2PA(pte);proc_freekpt((pagetable_t)child);}}}kfree((void*)pagetable); //释放v指向的物理内存页，
}

简化 copyin/copyinstr（hard）

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

YOUR JOB

在kernel/proc.c中有一个copyin函数，该函数读入一个用户空间的指针，通过用户的pagetable转为内核可以识别的物理地址，然后再交给内核pagetable转换为物理地址，然后这里实验要求我们将user的pagetable直接复制一份到我们之前构造的kernel pagetable里，那从虚拟地址到物理地址只需要一步转换就可以了

==将定义在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的地址。

一些提示：

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

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

QUESTION

解释为什么在copyin_new()中需要第三个测试srcva + len < srcva：给出srcva和len值的例子，这样的值将使前两个测试为假（即它们不会导致返回-1），但是第三个测试为真 （导致返回-1）

第一步 替换copyin()、copyinstr

先用对copyin_new的调用替换copyin()，确保正常工作后再去修改copyinstr

// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
    return copyin_new(pagetable,dst,srcva,len);
}// Copy a null-terminated string from user to kernel.
// Copy bytes to dst from virtual address srcva in a given page table,
// until a '\0', or max.
// Return 0 on success, -1 on error.
int
copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
    return copyinstr_new(pagetable, dst, srcva, max);
}

第二步 复制pagetable的函数

• 在内核更改进程的用户映射的每一处，**都以相同的方式更改进程的内核页表。**包括fork(), exec(), 和sbrk().
• 用户地址的PTE在进程的内核页表中需要什么权限？(在内核模式下，无法访问设置了PTE_U的页面）

这里解读一下sbrk和exec

fork 复制进程 exec加载另一个进程
sbrk是一个用于进程减少或增长其内存的系统调用。这个系统调用由函数growproc实现

要完成的工作，即将一个进程的pagetable复制到另一个进程

重写一个函数对页表的物理页进行映射.下面函数的作用即是将一个页表中的虚地址全部映射到一个页表中.实际只做了物理页的映射,而并有实际的物理页的申请.

这里的 proc_mappages 相比 mappages 就去掉了 remap 报错的逻辑。

int 
procuvmcopy(pagetable_t uvm, pagetable_t kvm, uint64 old_sz, uint64 new_sz){
    pte_t *pte;uint64 pa, i;uint flags;old_sz = PGROUNDUP(old_sz);if (new_sz <= old_sz) return 0;for(i = old_sz; i < new_sz; i += PGSIZE){
    if((pte = walk(uvm, i, 0)) == 0) //找到PTE的物理地址panic("procuvmcopy: pte should exist");if((*pte & PTE_V) == 0)panic("procuvmcopy: page not present");// 清除PTE_U的标记位 pa = PTE2PA(*pte);flags = PTE_FLAGS(*pte);if(proc_mappages(kvm, i, PGSIZE, pa, flags&(~PTE_U)) != 0){
     //调用proc_mappages完成映射,并保存相关信息goto err;}}return 0;err:uvmunmap(kvm, 0, i / PGSIZE, 1);return -1; 
}

第三步 修改fork()，exec()，sbrk()，userint

• 在内核更改进程的用户映射的每一处，都以相同的方式更改进程的内核页表。包括fork(), exec(), 和sbrk().
• 不要忘记在userinit的内核页表中包含第一个进程的用户页表

userinit

userinit函数的修改,我们需要将initcode中加载的一个物理页进行copy映射.

// 包含第一个进程的用户页表procuvmcopy(p->pagetable, p->kernel_pt,0,PGSIZE) ;

fork()函数的修改, 我们发现uvmcopy时需要将父进程的用户空间页表全部拷贝到子进程,我们在完成拷贝时,则需要将该进程的用户空间的页表也全部拷贝一遍.将所有的页全部拷贝映射一遍即可.

// 父进程用户空间的页表也全部拷贝一遍给子进程if(procuvmcopy(np->pagetable, np->kernel_pt, 0, np->sz) < 0){
    freeproc(np);release(&np->lock);return -1;}

exec()函数,我们可以看到exec函数函数执行时,首先会将elf文件里面的所有的段加载到内存中,并将其全部映射到进程的用户态页表中.首先我们需要将该进程的所有的内核的页表中所有的物理页映射全部去掉,然后就重新将用户空间的页表全部重新映射到内核的页表中.

//删除旧的映射并将新页面映射到内核页表uvmunmap(p->kernel_pt, 0, PGROUNDUP(oldsz)/PGSIZE, 0);if(procuvmcopy(p->pagetable, p->kernel_pt, 0, p->sz) < 0)goto bad;

sbrk函数,我们实际需要修改sys_sbrk函数,当用户空间的物理内存增长时,此时我们需要将新增的地址空间页全部映射到内核的页表中,如果用户的物理内存缩小时,则此时我们需要将已经去掉的地址空间的映射全部取消掉.我们判断地址增长的时候会判断该地址是否增长超过了系统的限制.

int
growproc(int n)
{
    uint sz;struct proc *p = myproc();sz = p->sz;if(n > 0){
    // check the virtual address is no more than 0x0c000000Lif((sz + n) >= PLIC){
    return -1;}if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
    return -1;}// mapper user page to kernel page tableif((procuvmcopy(p->pagetable, p->kernel_pt, p->sz, sz)) < 0){
    return -1;}} else if(n < 0) {
    sz = uvmdealloc(p->pagetable, sz, sz + n);// remove all the pages from the kernel tableuvmunmap(p->kernel_pt,PGROUNDUP(sz),(PGROUNDUP(p->sz)-PGROUNDUP(sz))/PGSIZE,0);}p->sz = sz;return 0;
}