page tables

这个实验是有关页表的，主要了解页表的构成，并完成将用户空间的数据拷贝到内核空间的功能。

页表

操作系统通过页表这种机制为每个进程提供独立的地址空间。页表决定了内存地址的含义，同时决定了哪些物理地址可以被访问，简单来讲页表维护了虚拟地址和物理地址之间的映射关系。通过页表这种机制可以将不同进程的地址空间隔离，同时又可以将不同进程的地址空间映射到相同的物理内存上，提高内存利用率。

分页硬件

xv6 运行在 Sv39 RISC-V 上，这意味着 64 位的虚拟地址只有低 39 位被用到，其他的高 25 位并未使用，而是用作将来的扩展，所以 xv6 的地址空间最高可以达到 $2^{39}$ 。通常一页的大小是 $2^{12}$ （4096），要映射所有的地址空间则需要 $2^{27}$ 页。每页的页表项包含一个占 44 位物理页号（PPN）和一些权限位。硬件将虚拟地址转成物理地址的过程为，通过有效 39 位中的高 27 位找到对应的页表项，通过页表项中 PPN 确定物理地址的前 44 位，后 12 位则是虚拟地址的后 12 位。

按照上面这种只使用一个页表的方案来算一下储存页表所需要的内存，要表示所有的内存空间需要 $2^{27}$ 个页表项，一个页表项的大小为 8 个字节，则存储整个页表需要 $2^{30}$ B 即 1GB。

接着我们来看一下分级页表，所谓分级页表就是将原来的一个页表，按树状结构分级，一级页表项指向二级页表的地址，二级页表项指向三级页表的地址，三级页表项（叶子节点）指向物理地址（PPN）。这里我们同样计算一下存储页表所需的内存，分级的页表每个页表只含有 $2^{9}$ （512）个页表项。第一级页表的 512 个页表项指向第二级 512 个页表，所以第二级有 $2^{18}$ 个页表项，第三级有 $2^{27}$ 个页表项，总共需要的内存为 $(2^9 + 2^{18} + 2^{27}) * 8$ B 比 1GB 多一点。这样看其实分级页表所占的存储空间还要多一点，那么为什么现在主流操作系统还是普遍采用分页呢 ? 这里有一个重要的点就是内存的寻址空间通常很大，比如这里 xv6 的寻址空间是 $2^{39}$ 即 512 G，实际使用上很少有物理内存为 512G 的情况，即使物理内存为 512 G 也不可能一开始就将这个 512 G 内存全部使用。分级页表的好处就是可以按使用情况进行页表的分配，即使我们映射所有地址空间所占的内存比单个页表所占内存多一点，但是在大多数时候真正分配的页表都只有少数，例如当物理内存为 4GB 的时候，使用分级页表只需要约 $2^{20}$ 个页表项占据空间 8MB，而使用单页表因为一开始就要分配 $2^{27}$ 个页表项，占据空间 1G。

内核地址空间

Xv6 的每个进程都有自己的页表，地址空间，内核也有一个页表，地址空间，内核通过页表映射访问物理内存和其他的硬件资源。

创建地址空间

启动时，main 调用 kvminit (kernel/vm.c:22) 创建内核页表，这里发生在开启分页之前，所以这一页是和物理地址一一对应的。这一页用来存根页表，然后调用 kvmmap 映射内核的地址空间包括 kernel text、kernel data、``PHYSTOP、设备地址等。kvmmap (kernel/vm.c:118) 调用 mappages (kernel/vm.c:149) 将某个区间的虚拟内存和物理内存对应上。mappages 调用 walk 找到虚拟地址对应的页表项 (PTE)，然后初始化页表项，将物理地址 PPN 和权限位写上。walk 函数是模拟硬件访问页表的过程，walk 函数的 alloc 参数设置为 1 时，如果访问的 PTE 无效就会重新创建新的页表并将其物理地址写入 PTE 中, 返回叶子节点的 PTE 地址。上述的操作是建立在物理地址和虚拟地址一一映射的前提下的，因为分级找 PTE 的过程其实是通过找 PTE 中的物理地址，将其作为虚拟地址寻找下一级 PTE 的，这里物理地址和虚拟地址要一一对应才可以。接下来 main调用 kvminithart 将根页表的物理地址写入 satp 寄存器， cpu 会将虚拟地址按页表的映射关系翻译成物理地址。最后 main 调用 procinit 为每个进程映射内核栈。每个页表项会缓存在 TLB，所以每次更新页表后记得让 TLB 缓存失效。

物理内存分配

内核必须在运行时分配和释放在 kernel 结束位置到 PHYSTOP 之间的物理内存。物理内存分配器是一个单向链表，每个链表元素代表一页空闲物理内存，main 调用 kinit 将 kernel 结束位置到 PHYSTOP 的物理内存加入到链表中。xv6 是可以通过硬件读取有多少可用内存的，但是这里只是假设机器内存为 128M。

进程地址空间

每个进程都有自己的页表，地址空间，当进程切换的时候，页表也会切换。一个进程的地址空间从 0 开始到 MAXVA。当进程申请内存时内核会调用 kalloc 分配物理空间，将 PTE 加到进程的页表中，同时设置权限位。这里可以看到使用页表的三个好处：

不同进程的页表将虚拟地址转换成不同的物理内存，每个进程都有自己独立的内存。
每个进程的地址空间都是连续的，但是物理地址可以不连续。
内核将 trampoline 代码映射到用户空间的顶部一页，这一页物理地址可以被所有的进程访问。

sbrk 和 exec

sbrk 是用来申请和释放进程内存的系统调用。申请和释放内存取决于参数 n 的正负， n 为正时调用 uvmalloc ，再调用 kalloc 分配物理内存, mappages 将 PTE 加到进程页表。n 为负时，通过调用 uvmdealloc 调用 walk 找到对应 PTE , 接着调用 kfree 释放 PTE 指向的物理页。

exec 创建一部分用户内存空间。exec 会读入二进制文件，然后解析 elf header 中每个段，代码段，数据段等。之后分配一个没有用户空间映射的页表，使用 uvmalloc 为每个段分配内存，将每个段加载到内存中。接着创建用户栈空间，栈里的前三个元素分别是，伪返回地址，argc 和 argv 指针，最后分配一个无法访问的页作为保护页，程序访问到这里就会触发中断，这样可以处理程序参数过大导致栈溢出的问题。

Print a page table

这里要我们实现一个打印页表的函数 vmprint ，接受页表地址为参数，分级打印页表输出。

这里可以参考 freewalk 函数访问页表，然后递归打印页表信息。

实现如下：

 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


void print_info(int level, pte_t pte, int idx) {
  for(int i = 0; i <= level; i++){
    printf("..");
    if(i != level){
      printf(" ");
    }
  }
  printf("%d: pte %p pa %p\n", idx, pte, PTE2PA(pte));
}

void vmprint_recur(pagetable_t pagetable, int level) {
  // 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){
      print_info(level, pte, i);
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      vmprint_recur((pagetable_t)child, level+1);
    } else if(pte & PTE_V){
      print_info(level, pte, i);
    }
  }
}

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

接下来有个问题问打印出来的 page 0，page2 分别是什么，以及用户态能否访问 page1 ?

首先这里是用户空间，根据用户空间的分布以及 exec 的执行过程可以知道，page0 是代码段数据段即 exec 从文件中加载到内存里的部分，page2 就是分配的用户栈空间，page1 则是保护页，在用户态是无法访问保护页的。

A kernel page table per process

因为内核的页表和进程的页表是独立的，内核并没有进程空间的映射，所以当内核想要通过用户空间传入的地址来访问内存的时候就无法找到物理地址，所以这里要我们解决这个问题。要做的就是在用户进程创建时同时拷贝一份内核的页表作为自己在内核态运行时使用的页表，在进程切换时也要切换这个内核页表，在这个阶段需要保证我们拷贝的页表和真正内核页表是一致的。

这里根据实验提示来做，首先在 proc 结构体中加入内核态使用的页表

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


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)
  pagetable_t pagetable;       // User page table
  pagetable_t kpagetable;      // per process kernel page table
  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)
};

接下来在进程创建时初始化这个页表，需要将原来在每个进程初始化时分配的内核栈移到这里来。

 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


// 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");
  }
  kvminithart();
}

void
proc_kvminit(pagetable_t kernel_pagetable)
{
  // uart registers
  if(mappages(kernel_pagetable, UART0, PGSIZE, UART0, PTE_R | PTE_W) != 0)
    panic("kvmmap");

  // virtio mmio disk interface
  if(mappages(kernel_pagetable, VIRTIO0, PGSIZE, VIRTIO0, PTE_R | PTE_W) != 0)
    panic("kvmmap");

  // CLINT
  if(mappages(kernel_pagetable, CLINT, 0x10000, CLINT, PTE_R | PTE_W) != 0)
    panic("kvmmap");

  // PLIC
  if(mappages(kernel_pagetable, PLIC, 0x400000, PLIC, PTE_R | PTE_W) != 0)
    panic("kvmmap");

  // map kernel text executable and read-only.
  if(mappages(kernel_pagetable, KERNBASE, (uint64)etext-KERNBASE, KERNBASE, PTE_R | PTE_X) != 0)
    panic("kvmmap");

  // map kernel data and the physical RAM we'll make use of.
  if(mappages(kernel_pagetable, (uint64)etext, PHYSTOP-(uint64)etext, (uint64)etext, PTE_R | PTE_W) != 0)
    panic("kvmmap");

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  if(mappages(kernel_pagetable, TRAMPOLINE, PGSIZE, (uint64)trampoline, PTE_R | PTE_X) != 0)
    panic("kvmmap");
}

pagetable_t
proc_kpagetable(struct proc *p)
{
  pagetable_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;
  proc_kvminit(pagetable);
  // 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("pkalloc");
  uint64 va = KSTACK((int) (p - proc));
  if(mappages(pagetable, va, PGSIZE, (uint64)pa, PTE_R | PTE_W) != 0)
    panic("pkvmmap");
  p->kstack = va;
  return 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
38
39
40
41
42
43


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->kpagetable));
        sfence_vma();
        swtch(&c->context, &p->context);

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;
        kvminithart();
        found = 1;
      }
      release(&p->lock);
    }
#if !defined (LAB_FS)
    if(found == 0) {
      intr_on();
      asm volatile("wfi");
    }
#else
    ;
#endif
  }
}

销毁进程时需要释放这个页表

 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


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);

  if(p->kstack){
    pte_t* pte = walk(p->kpagetable, p->kstack, 0);
    if (pte == 0)
      panic("freeproc: kstack");
    kfree((void*)PTE2PA(*pte));
  }
  p->kstack = 0;

  if(p->kpagetable)
    proc_kfreepagetable(p->kpagetable);

  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;
}

Simplify `copyin/copyinstr`

这里要我们简化 copyin/copyinstr，在这之前是通过查找进程的页表来将用户态的地址转成物理地址再传到内核，现在我们可以直接把用户态的映射放到我们刚刚创建的内核页表中，这样内核就可以直接使用用户态的地址来寻址了。我们要实现 copyin_new 和 copyinstr_new 来替换 copyin/copyinstr 。

将用户态空间和内核态空间放到同个页表中要保证两个空间没有重叠，xv6 用户态地址从 0 开始，内核态则从较高的地址 PLIC 开始，所以我们要保证用户空间不超过 PLIC。

接下来根据提示进行。

首先替换 copyin,copyinstr。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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);
}

接下来，在用户空间的页表变化的时候同时也将内核页表修改，例如 fork、exec、sbrk 调用时。

 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


void
proc_kvmcopy(pagetable_t pagetable, pagetable_t kpagetable, uint64 oldsz, uint64 newsz) {
  if (newsz> PLIC) {
    panic("newva larger than the PLIC address!");
  }
  pte_t *pte_u, *pte_k;
  uint64 va;
  for(va = oldsz; va < newsz; va += PGSIZE) {
    if((pte_u=walk(pagetable, va, 0)) == 0) {
      panic("walk user pagetable");
    }
    if((pte_k=walk(kpagetable, va, 1)) == 0) {
      panic("walk kernel pagetable");
    }
    *pte_k = *pte_u;
    *pte_k &= ~(PTE_U);
  }
  for (va = newsz; va < oldsz; va += PGSIZE){
    if((pte_k = walk(kpagetable, va, 1)) == 0) {
      panic("wakl!");
    }
    *pte_k &= ~PTE_V;
  }
}

// proc.c fork
// increment reference counts on open file descriptors.
for(i = 0; i < NOFILE; i++)
  if(p->ofile[i])
    np->ofile[i] = filedup(p->ofile[i]);
np->cwd = idup(p->cwd);

proc_kvmcopy(np->pagetable, np->kpagetable, 0, np->sz);

safestrcpy(np->name, p->name, sizeof(p->name));


//exec.c exec
// Allocate two pages at the next page boundary.
// Use the second as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE)) == 0)
  goto bad;
sz = sz1;
uvmclear(pagetable, sz-2*PGSIZE);
sp = sz;
stackbase = sp - PGSIZE;
proc_kvmcopy(pagetable, p->kpagetable, 0, sz);

// sys_sbrk
// 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;
  if(n> 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    proc_kvmcopy(p->pagetable, p->kpagetable, p->sz, sz);
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    proc_kvmcopy(p->pagetable, p->kpagetable, p->sz, sz);
  }
  p->sz = sz;
  return 0;
}

在 userinit 里将进程初始化时的用户态页表到拷贝到内核页表中。

 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


// Set up first user process.
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;
  proc_kvmcopy(p->pagetable, p->kpagetable, 0, p->sz);

  // 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);
}

内核态的页表的访问权限是内核访问，所以不能设置 PTE_U 位。

确保用户空间不超过 PLIC。

问题：为什么 srcva + len < srcva 是必要的呢？给 src，len 什么值的时候前两个测试失败，第三个测试成功呢？

src + len 可能会溢出，srcva + len < srcva 可以保证溢出时返回 - 1。

Contents

页表