page tables

最近工作太忙了，好久没有时间更新学习进度了，本周还是抽时间把lab3的内容作完了，lab3的难度感觉还是非常大的，不过最终把lab3完成后，就对虚拟内存管理有了深刻的认识。对于vm的那几个函数看了很多遍。调试了很多遍,终于发现问题,然后解决该问题了.

page

在xv6系统中，物理内存都被分成了4096byte的页，比如物理地址也分为两部分即物理页码(44bit)和页内偏移地址(12bit)offset。由下图我们可以看到虚拟地址到物理地址的映射。

但在xv6系统中虚拟地址实际只用到64位中的低39位，高位的25位并没有用到，因此我们可以知道虚拟页总共有$2^{27}$页，我们假如直接进行地址的话，则可以发现每个页表的大小可能都为$2^{27}$,这对内存来说不可取，实际上我们采用分段式的页表映射。页表中的每一项每一项实际存储的虚拟地址印刷的物理页的索引号。在xv6系统中页表采用三级页表的形式的存储，每一级页表的大小实际刚好为一页物理页的大小，因此每一级页表刚好可以存储存储$2^{9}$项。

我们通过下图可以看到一个虚拟地址实际包含5部分，保留位为25位，紧接着为9位的一级页表内的的offset，紧接着为9位的二级页表内的的offset，紧接着为9位的三级页表内的的offset，三级页表中则存储的为该虚拟地址对应的实际物理页编号，我们取出物理页编号，再加上offset即可得到实际的物理地址。

我们可以看到代码中几个比较重要的宏定义

// 每一个物理页的大小
#define PGSIZE 4096 // bytes per page
// 物理页的offset
#define PGSHIFT 12  // bits of offset within a page

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))
// shift a physical address to the right place for a PTE.
//取出物理地址转换为对应的页表项
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
//通过页表得到对应的物理页对应的编号
#define PTE2PA(pte) (((pte) >> 10) << 12)
// 取出页表项中对应的标志位
#define PTE_FLAGS(pte) ((pte) & 0x3FF)

// extract the three 9-bit page table indices from a virtual address.
#define PXMASK          0x1FF // 9 bits
#define PXSHIFT(level)  (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)

三级页表中同时存储的有flags,flags代表该页表是否有效,我们需要判断每一页的访问权，只需要判断标志位即可。
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access
我们通过虚拟地址的12~39位，实际为该虚拟地址的三级页表的偏移地址，通过三级页表的偏移地址，最终可以得到该虚拟地址对应的物理页号。

1. Print a page table

To help you learn about RISC-V page tables, and perhaps to aid future debugging, your first task is to write a function that prints the contents of a page table.

Define a function called vmprint(). It should take a pagetable_t argument, and print that pagetable in the format described below. Insert if(p->pid==1) vmprint(p->pagetable) in exec.c just before the return argc, to print the first process's page table. You receive full credit for this assignment if you pass the pte printout test of make grade.

这部分比较简单，打印出页表的内容，我们知道三级页表的原理，这个即为简单的dfs遍历即可，遍历三级页表中的内容，每一级页表有512项，每一级页表有标志位，判断标志位是否有效，即是否包含PTE_V，则表示该页表有效。如果有效则向下遍历即可。

int pteprint(pagetable_t pagetable,int level){  
  for(int i = 0; i < 512; ++i){
    pte_t *pte = &pagetable[i];
    // level page table entry
    if(*pte & PTE_V) {
      // page table is valid
      for(int j = 2; j > level; --j){
         printf(".. ");
      }
      printf("..%d: pte %p pa %p\n\r",i,*pte,(pagetable_t)PTE2PA(*pte));
      if(level >= 1){
         pteprint((pagetable_t)PTE2PA(*pte),level-1);
      }
    } 
  }

  return 0;
}

2.A kernel page table per process

Xv6 has a single kernel page table that's used whenever it executes in the kernel. The kernel page table is a direct mapping to physical addresses, so that kernel virtual address x maps to physical address x. Xv6 also has a separate page table for each process's user address space, containing only mappings for that process's user memory, starting at virtual address zero. Because the kernel page table doesn't contain these mappings, user addresses are not valid in the kernel. Thus, when the kernel needs to use a user pointer passed in a system call (e.g., the buffer pointer passed to write()), the kernel must first translate the pointer to a physical address. The goal of this section and the next is to allow the kernel to directly dereference user pointers.

Your first job is to modify the kernel so that every process uses its own copy of the kernel page table when executing in the kernel. Modify struct proc to maintain a kernel page table for each process, and modify the scheduler to switch kernel page tables when switching processes. For this step, each per-process kernel page table should be identical to the existing global kernel page table. You pass this part of the lab if usertests runs correctly.

题目本质是说进行内核空间的虚拟地址和用户空间的虚拟地址因为不在同一个页表里，所以内核的地址空间和用户的地址无法正常进行访问，必须要通过转换，特别在内核态访问用户态传过来的地址时，无法直接访问，需要通过转换才可以，因此我们需要在内核态将用户态的虚拟地址空间也需要做映射，这样我们就可以在内核态直接访问用户态的地址。
在此时，我们需要重新为进行申请一个内核态的页表，每个进程则有一个独立的内核页表，并将访问系统的所有的特殊的接口地址全部映射到该页表中，同时将该进程的内核栈也映射到该页表。每个进程都有一个独立的内核栈，由于内核栈空间与用户空间的地址映射在同一个地址表中，因此可以直接访问。

为进程建立一个内核页表，并做好地址映射。新建页表，并做好内核地址的映射。

pagetable_t
prockvminit(){
	pagetable_t pagetable = (pagetable_t) kalloc();
	if(pagetable == 0)
		panic("kalloc");
	
	// each page size is 4096 byte = 4KB
	// kernel page table
	memset(pagetable, 0, PGSIZE);

	// uart registers
	// uart mmmap
	prockvmmap(pagetable,UART0, UART0, PGSIZE, PTE_R | PTE_W);

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

	// CLINT
	//prockvmmap(pagetable,CLINT, CLINT, 0x10000, PTE_R | PTE_W);

	// PLIC
	prockvmmap(pagetable,PLIC, PLIC, 0x400000, PTE_R | PTE_W);

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

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

	return pagetable;
}

void
prockvmmap(pagetable_t pagetable,uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pagetable, va, sz, pa, perm) != 0){
  	printf("total free = %d \n\r",totalfree());
  	printf("va = %p sz = %p \n\r",va,sz);
    panic("prockvmmap");
  }
}

在进程初始化时，我们可以保持不变，初始化时即为每个进程分配内核栈，映射到全局的kernel_table中,我们在进行进程alloc时，可以将该内核栈物理页再做一遍映射，映射到进程的内核表中。

procinit(void)
{
  struct proc *p;
  
  initlock(&pid_lock, "nextpid");
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, "proc");
	  p->kallocstats = 0;
  	  p->kfreestats = 0;
	  // map kernel stack to the kernel page table
	  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;
  }
  kvminithart();
}

// map kernel stack to the kernel page table
 p->kpagetable = prockvminit();
 prockvmmap(p->kpagetable,p->kstack,kvmpa(p->kstack),PGSIZE, PTE_R | PTE_W);

 // Allocate a trapframe page.
 if((p->trapframe = (struct trapframe *)kalloc()) == 0){
   release(&p->lock);
   return 0;
 }

 // An empty user page table.
 p->pagetable = proc_pagetable(p);
 if(p->pagetable == 0){
   freeproc(p);
   release(&p->lock);
   return 0;
 }

进程释放时，也需要对该进程的内核页表进行释放,但是释放时由于内核空间只是做了物理页的映射，因此我们只需要释放页表的空间即可，不需要释放物理页的空间。但在代码中加入了对每个进程执行kalloc和kfree的次数统计,发现实际确实存在内存泄漏,申请的物理页没有被释放的问题.

// release trap frame
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  //release user page table
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  p->pagetable = 0;
  //release kernel page table and kernel stack
  if(p->kpagetable) { 
  	procfreekpt(p->kpagetable);
  }
  p->kpagetable = 0;

我们用一个遍历即可，但是总感觉这个函数写的有点问题，没有释放所有的物理页，存在内存泄漏的问题，这个问题查找了很长时间没有解决。从github上下载了几个代码运行了一下，发现也都有问题。

// Recursively free page-table pages except leaf
void procfreekpt(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_R|PTE_W|PTE_X)) {
	  uint64 child = PTE2PA(pte);
	  procfreekpt((pagetable_t)child);
	  pagetable[i] = 0;
    }
  }
  kfree((void*)pagetable);
}

进程调度时,当前进程如果被调度时,则此时我们需要将该进行的内核页表的地址加载到页表的寄存器中,此时我们访问地址进行转换时,则通过该页表查找物理页的地址.我们可以看到在完成上下文切换前,将页表加载完成即可.当前如果所有的进程都空闲时,则我们将全局的kernel pagetable进行加载.

       p->state = RUNNING;
       c->proc = p;
  
    // load kernel pagetable address into page table
    prockvminithart(p->kpagetable);
	
    // load process kernel page table
       swtch(&c->context, &p->context);

       // Process is done running for now.
       // It should have changed its p->state before coming back.
       c->proc = 0;
	// found
       found = 1;
     }
     release(&p->lock);
   }
// the current has no process runing
   if(found == 0) {
  // use kernel pagetable when no process runing
  kvminithart();
  
     intr_on();
  // load kernel page table
     asm volatile("wfi");
   }

3.copyin/copyinstr

需要自己重新写copyin和copyinstr的代码，这个其实比较简单，在上一个练习中我们将内核中的所有的地址全部挂接到内核表中，在这个练习中我们需要将所有的用户空间的地址要全部映射到内核的页表中，这样在进程运行时，内核即可进行对用户空间的虚拟地址进行访问.我们可以重写一个函数对页表的物理页进行映射.下面函数的作用即是将一个页表中的虚地址全部映射到一个页表中.实际只做了物理页的映射,而并有实际的物理页的申请.

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)
			panic("procuvmcopy: pte should exist");
		if((*pte & PTE_V) == 0)
			panic("procuvmcopy: page not present");
		pa = PTE2PA(*pte);
		flags = PTE_FLAGS(*pte);
		if(mappages(kvm, i, PGSIZE, pa, flags&(~PTE_U)) != 0){
			panic("procuvmcopy: remap");
			goto err;
		}
	}
	return 0;

err:
	uvmunmap(kvm, 0, i / PGSIZE, 1);
	return -1; 
}

我们仔细阅读提示,发现有几个函数需要进行此类操作和映射.

Replace copyin() with a call to copyin_new first, and make it work, before moving on to copyinstr.
At each point where the kernel changes a process's user mappings, change the process's kernel page table in the same way. Such points include fork(), exec(), and sbrk().
Don't forget that to include the first process's user page table in its kernel page table in userinit.
What permissions do the PTEs for user addresses need in a process's kernel page table? (A page with PTE_U set cannot be accessed in kernel mode.)
Don't forget about the above-mentioned PLIC limit.

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

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;
  
  // copy one page of the 
  procuvmcopy(p->pagetable, p->kpagetable,0,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;

  release(&p->lock);

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

// Allocate process.
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }

  np->sz = p->sz;
  np->parent = p;
  
  // Copy user memory mapper the kernel page table to child
  if(procuvmcopy(np->pagetable, np->kpagetable,0,np->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }

  // copy saved user registers.
  *(np->trapframe) = *(p->trapframe);

  // Cause fork to return 0 in the child.
  np->trapframe->a0 = 0;

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

// Save program name for debugging.
  for(last=s=path; *s; s++)
    if(*s == '/')
      last = s+1;
  safestrcpy(p->name, last, sizeof(p->name));
    
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;
  p->sz = sz;
  
  // we remove the old mapper and We mapper new pages to the kernel page table
  uvmunmap(p->kpagetable, 0, PGROUNDUP(oldsz)/PGSIZE, 0);
  if(procuvmcopy(p->pagetable,p->kpagetable,0,p->sz) < 0)
  	goto bad;
  
  p->trapframe->epc = elf.entry;  // initial program counter = main
  p->trapframe->sp = sp;          // initial stack pointer
  proc_freepagetable(oldpagetable, oldsz);

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 0x0c000000L
  	if((sz + n) >= PLIC){
	  return -1;
	}
	// malloc 
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
	// mapper user page to kernel page table
	if((procuvmcopy(p->pagetable, p->kpagetable, p->sz, sz)) < 0){
	   return -1;
	}
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
	// remove all the pages from the kernel table
	uvmunmap(p->kpagetable,PGROUNDUP(sz),(PGROUNDUP(p->sz)-PGROUNDUP(sz))/PGSIZE,0);
  }
  p->sz = sz;
  return 0;
}

总的来说这一章的lab还是非常有难度的,特别时调试的部分,花了很长时间都没有非常好的结果,感觉是目前遇到的难度最大的lab.

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 公开课学习

← 【MIT6.S081】 lab2 systemcalls 【MIT6.S081】lab1 utils →

扫描二维码，分享此文章

【MIT6.S081】 lab3 pagetable

page tables

page

1. Print a page table

2.A kernel page table per process

3.copyin/copyinstr