mit 6.S081 Lab3 page tables

这一次实验需要读xv6 book中的第三章，而且需要好好读…

Print a page table

实验大意

实现vmprint，将指定的page talbe中的信息打印出来

过程

xv6中三级页表，每级page table大小是 page 大小，并且可以容纳512个pte，所以每级Page table 需要在va中占据9位来表明PTE的位置。并且可以使用这个PTE跳转到所需要的Page table的位置。这个实验需要读一下 kernel/vm.c 的walk函数。

// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.
//
// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)]; 
    if(*pte & PTE_V) { // 如果当且页有效的话
      pagetable = (pagetable_t)PTE2PA(*pte); //获取pte中的pa
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

那么vmprint大体思路就出来了，因为pagetable中有512个pte，我们只需要遍历pte，并且如果pte指向的page 还是page table 那么就递归的调用vmprint就行，这里为了实现递归调用，我们需要一个tool函数。

//print ptes and pas from a pagetable
void
vmprint(pagetable_t pagetable)
{
  printf("page table %p\n", pagetable);
  __vmprint_tool(pagetable, 1);
}


// a tool function for vmprint
void
__vmprint_tool(pagetable_t pagetable, int depth)
{
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if((pte & PTE_V) == 0)
      continue;
    for(int j = 0; j < depth; j++)// 根据当前的深度打印..
    {
        if(j != 0)
          printf(" ");
        printf("..");
    }
    printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {//如果一个pte的标志位中，PTE_R,PTE_W,PTE_X都为零，就代表指向的是一个page table
      __vmprint_tool((pagetable_t) PTE2PA(pte), depth + 1);
    }
  }
}

最后需要在exec函数中添加一段代码，让系统初始化完成后，执行第一个进程时调用vmprint。

// kernel/exec.c
  if(p->pid == 1)
  {
    vmprint(p->pagetable);
  }

A kernel page table per process

实验大意

xv6中有一个全局Kernel page table 现在该实验让你实现每个进程都有自己的kernel page table

过程

这个实验比较麻烦，但实际上跟着hints来就可以。

首先要将 kernel/proc.h中的 struct proc 增加一个新的变量来存储kernel proc

// 这里我把它命名为kernel_pagetable
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  uint64 kstack_pa;             //kstack pa in kernel pagetable
  pagetable_t pagetable;       // User page table
  pagetable_t kernel_pagetable; // kernel_pagetable
   
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

然后我们需要魔改allocproc，这个函数是用来给一个在proc数组里，并且为UNUSED的进程初始化的， 这里我们需要添加关于kernel page table的代码， 全局page talbe初始化是用的kvminit函数。

Early in the boot sequence, main calls kvminit (kernel/vm.c:22) to create the kernel’s page
table. This call occurs before xv6 has enabled paging on the RISC-V, so addresses refer directly to
physical memory. Kvminit first allocates a page of physical memory to hold the root page-table
page.

kvminit通过kalloc，分配给kernel page table一个page，并且通过kvmmap将kernel的虚拟内存与物理内存一一对应起来。

这里映射的主要是PHYSTOP之下的内存。

void
kvminit()
{
  kernel_pagetable = (pagetable_t) kalloc();
  memset(kernel_pagetable, 0, PGSIZE);

  // uart registers
  kvmmap(UART0, UART0, PGSIZE, PTE_R | PTE_W);

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

  // CLINT
  kvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  kvmmap(PLIC, PLIC, 0x400000, PTE_R | PTE_W);

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

  kvmmap((uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
  // map kernel data and the phy    return 0; in the kernel.
  kvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
    // map kernel data and the physical RAM we'll make use of.

}

我们proc的kernel和全局kernel这些初始化的东西是一模一样的，所以只需要改一改kvminit以及kvmmap这两个函数就行，这两个函数是直接用的vm.c中的全局变量kernel_pagetable，那我们的kvminit需要创建一个kernel_pagetalbe并将它返回，而我们的kvmmap则用传入的pagetable代替全局的kernel_pagetable。

// kernel/vm.c

// used for proc_kvminit
// same as kvmmp
void
proc_kvmmap(pagetable_t proc_kernel_pagetable,uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(proc_kernel_pagetable, va, sz, pa, perm) != 0)
    panic("proc_kvmmap");
}



// used for porc to have a kernel pagetable
// same as kvminit
pagetable_t proc_kvminit()
{
  pagetable_t proc_kernel_pagetable = (pagetable_t) kalloc();
  if(proc_kernel_pagetable == (pagetable_t)0)
    return 0;
  memset(proc_kernel_pagetable, 0, PGSIZE);

  // uart registers
  proc_kvmmap(proc_kernel_pagetable,UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  proc_kvmmap(proc_kernel_pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  proc_kvmmap(proc_kernel_pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  proc_kvmmap(proc_kernel_pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

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

  // map kernel data and the physical RAM we'll make use of.
  proc_kvmmap(proc_kernel_pagetable, (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.
  proc_kvmmap(proc_kernel_pagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return proc_kernel_pagetable;
}

并且需要在 kernel/proc.c中的allocproc函数，调用proc_kvminit来初始化进程的kernel page table。

p->kernel_pagetable = proc_kvminit();
if(p->kernel_pagetable == 0)
{
  freeproc(p);
  release(&p->lock);
  return 0;
}

接下来需要将进程本身映射到进程的kernel pagetable中的kstack，下面这段是xv6 book中对于kstack作用的描述，个人理解是kstack是保存进程在kernel mode 时产生的数据的， 而且需要用stap寄存器保存当前进程的stap。

Each process has two stacks: a user stack and a kernel stack ( p->kstack ). When the process is
executing user instructions, only its user stack is in use, and its kernel stack is empty. When the
process enters the kernel (for a system call or interrupt), the kernel code executes on the process’s
kernel stack; while a process is in the kernel, its user stack still contains saved data, but isn’t ac-
tively used. A process’s thread alternates between actively using its user stack and its kernel stack.
The kernel stack is separate (and protected from user code) so that the kernel can execute even if a
process has wrecked its user stack.

在procinit中，是将申请内存之后的kernel stack的物理地址通过用KSTACK生成的虚拟地址，映射在kernel pagetable高地址处，并且给每个kstack配备了一个guard page（见上图）。

procinit (kernel/proc.c:26) , which is called from main , allocates a kernel stack for each pro-
cess. It maps each stack at the virtual address generated by KSTACK , which leaves room for the
invalid stack-guard pages. kvmmap adds the mapping PTEs to the kernel page table, and the call to
kvminithart reloads the kernel page table into satp so that the hardware knows about the new
PTEs.

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);
      p->kstack = va;
      p->kstack_pa = (uint64)pa;// 这是我后来添加的
  }
  kvminithart();
}

我们需要给proc自带的kernel pagetable实现kstack的映射，这里我给struct proc添加了一个变量，来存储在proinit初始化后产生的kstack的物理地址。

uint64 kstack_pa;             //kstack pa in kernel pagetable

并且给procinit添加一段保存的代码，这段代码我已经在上面给出来了。
然后我们需要在allocproc中，进行映射。

// Allocate a page for the process's own kernel stack(p->kernel_pagetable).
// Map it high in memory, followed by an invalid
// guard page.
//initlock(&p->lock, "proc");
uint64 va = p->kstack;
uint64 pa = p->kstack_pa;
if(pa == 0)
{
  printf("%p", va);
  panic("allocproc: invalid pa\n");
}
printf("%p\n", pa);
//va = KSTACK(0);
proc_kvmmap(p->kernel_pagetable ,va, (uint64)pa, PGSIZE, PTE_R | PTE_W);

我们还需要修改scheduler， 使它每次选取一个proc运行的时候，修改satp，使satp指向该proc的kernel pagetable而不是全局的kernel pagetable。

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;
        w_satp(MAKE_SATP(p->kernel_pagetable));//change the satp register to current process kernel pagetable 
        sfence_vma();
        swtch(&c->context, &p->context);
        kvminithart();// 当proc执行完之后，需要将全局kernel page table 转到 satp中
        
        // 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();
      kvminithart();
      asm volatile("wfi");
    }
#else
    ;
#endif
  }
}

完成这些之后，我们就要开始最后一步，当进程释放的时候，也要释放kernel page table 并且不能释放对应的物理内存(因为物理内存是各个kernel page table 共享的)，释放pagetable 用到了walkaddr，我们需要修改一下walkaddr，使其遇到叶子page的时候，不要调用painc，这样我们就达到了释放page table而不释放对应的物理内存。

void
proc_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);
      proc_freewalk((pagetable_t)child);
    }
  }
  kfree((void*)pagetable);
}

最后在 kernel/proc.c 中的free_proc中调用这个函数就行了。

if(p->kernel_pagetable)
    proc_freewalk(p->kernel_pagetable);

最后的最后，我在这些步骤中省略了取defs.h中声明函数或这变量的过程，在做的时候这一步不要落下。
这样我们的这一个实验就大功告成了。

Simplify copyin/copyinstr

实验大意

在上一个实验中，每个proc都有了自己的kernel pagetable，这个实验是将copyin以及copyinstr简化，copyin和copyinstr是先将传入的pagetable中va对应的pa解析出来， 然后将数据传入pa中。我们简化后的版本是不需要翻译这一步，可以直接将数据从源地址放到目标地址中。

过程

我们需要将每个proc的user pagetable复制到kernel pagetable中，并且要将PTE中的PTE_U标记删除，因为在kernel mode中，无法访问带有PTE_U标记的PTE。实现这个函数可以照着 kernel/vm.c 中的uvmcopy来，不过不需要创建新的pte，只需要将kernel pagetable中的pte改为对应的user kernel pagetable中的pte即可。

//Given a process pagetable, copy it to the process's kernel pagetable
//the copied memories page_start at va 0
//remove flage PTE_U for kernel mode
int
u2kvmcopy(pagetable_t pagetable, pagetable_t proc_kernel_pagetable, uint64 page_start, uint64 page_end)
{
  pte_t *ptefrom, *pteto;
  uint64 pa, i;
  uint flags;
  if(page_end < page_start)
    return -1;
  page_start = PGROUNDUP(page_start);
  for(i = page_start; i < page_end; i += PGSIZE){
    if((ptefrom = walk(pagetable, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((pteto = walk(proc_kernel_pagetable, i, 1)) == 0)
      panic("uvmcopy: pte should exist");
    pa = PTE2PA(*ptefrom);
    flags = PTE_FLAGS(*ptefrom);
    flags = (flags & (~PTE_U));
    *pteto = (PA2PTE(pa) | flags);//将pte指向pa
  }
  return 0;
}

然后就是修改fork(), exec(), sbrk()这些创建或更改user table的函数，使其调用上面的u2kvmcopy

if(u2kvmcopy(np->pagetable, np->kernel_pagetable, 0, np->sz) < 0){
  freeproc(np);
  release(&np->lock);
  return -1;
}

fork和exec更改方式一样，就是将上面的代码添加进对应的位置就行。
sbrk()有所不同，因为user pagetable的大小不能超过在kernel pagetable中的PLIC地址，所以需要加一个判断（sbrk是 kernel/sysproc.c中的sys_sbrk函数，并且调用的是 kernel/proc.c中的growproc函数）。

// kernel/proc.c
// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  uint old_sz = sz;
  if(n > 0){
    if(sz + n  > PLIC || (sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) { //如果增长后的地址大于PLIC，那么返回错误
      return -1;
    }
    u2kvmcopy(p->pagetable, p->kernel_pagetable, old_sz, sz);//将新增的page复制给kernel_pagetable
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}

还需要修改kernel/proc.c 中的userinit函数，这个函数是第一个进程初始化的函数，也需要调用u2kvmcopy。

void
userinit(void)
{
  struct proc *p;

  p = allocproc();
  initproc = p;
  
  // allocate one user page and copy init's instructions
  // and data into it.
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;

  // prepare for the very first "return" from kernel to user.
  p->trapframe->epc = 0;      // user program counter
  p->trapframe->sp = PGSIZE;  // user stack pointer

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  p->state = RUNNABLE;
  u2kvmcopy(p->pagetable, p->kernel_pagetable, 0, p->sz);//调用
  release(&p->lock);
  printf("%d\n", p->lock);
}

最后，需要将实验已经写好的 kernel/vmcopyin.c中的 copyin_new 以及 copyinstr_new放到 kernel/vm.c 中的 copyin以及 copyinstr中即可，还要记得将copyin_new和copyinstr_new放到defs.h中。

// kernel/vm.c
// 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);
}

实验就完成啦^_^
可以看一下实现的copynew_in，可以发现，已经取消翻译的那一步了。

// 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_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  struct proc *p = myproc();

  if (srcva >= p->sz || srcva+len >= p->sz || srcva+len < srcva)
    return -1;
  memmove((void *) dst, (void *)srcva, len);
  stats.ncopyin++;   // XXX lock
  return 0;
}