6.S081-Lab 3 page tables

发表于2022-06-08更新于2023-04-25字数统计2.1k阅读时长11分阅读次数

前言

本博客为6.S081课程的第三个Lab: page tables，这次Lab主要是调试Xv6中页表相关的部分，共设计了三个题。 Lab链接：https://pdos.csail.mit.edu/6.828/2021/labs/pgtbl.html。

关于 Xv6 的页表

在分析三个实验之前，我想先介绍下 Xv6 操作系统中的页表设计。我们知道操作系统的很大的一个作用是实现进程之间的隔离(isolation)，倘若没有操作系统，每个进程都在物理内存(DRAM)中占据一定的内存供自己使用，难免存在恶意进程企图访问并修改其他进程的地址。操作系统通过一个巧妙的设计让每个进程误以为自己享有整个内存，而不同进程又绝不可能访问到其他进程的物理地址，这个设计就是页表(Page Table)。

在真实的操作系统中，地址分为两种：虚拟地址(Virtual Address)和物理地址(Physic Address)。无论是用户态还是内核态，执行指令的地址都是虚拟地址，而操作系统操作真实内存(DRAM)时必须使用物理地址。因此操作系统借助页表硬件来实现虚拟地址和物理地址之间的映射。

Xv6 是跑在 Sv39 RISC-V 硬件上的，作为64位操作系统，虚拟地址显然是64位的，但是64位只有低位的39位被使用，高25位未被使用。目前操作系统大多是4KB大小内存作为一页，Xv6 也不例外，39位有效地址中低12位作为一页内存的索引(2^12 = 4096)，高27位作为页表的索引。页表由若干个条目(page table entries,PTE)组成，理论上，页表会有(2^27 = 134217728)个条目，而每个PTE由44位的PPN和10位的Flags组成，PPN用于找到物理地址中相应的页，Flags用于标识该页的相关权限(可读，可写，可执行，用户态能否访问等)。

如下图所示，Sv39 RISC-V的物理地址由56位组成，实际上2^56的物理地址足够容纳物理IO设备和内存DRAM的空间。当用户给出一个虚拟地址，将其高位27位作为页表索引找到相应的PTE，将该PTE中的PPN和虚拟地址的低12位组合得到最终的物理地址。这就是页表的工作原理。

操作系统为每个进程维护一个单独的页表，这样每个进程通过查自己的页表来将虚拟地址转换为物理地址，也正是这样，不同进程的相同虚拟地址可以映射到不同的物理地址上，也就实现了进程之间的隔离。实际上，为了便于内核对物理地址的访问，内核也有一个单独的页表。

倘若使用上面图中的页表，由于每个页表有(2^27 = 134217728)个条目，而每个进程有一个单独页表，这将占据很大的物理内存。因此，大多数操作系统将页表设计为多级结构，实际上 Xv6 的页表被设计为三级页表，如下图所示：

将原先用于页表索引的27位索引值分为三个9位的索引值分别作为三级页表的索引，这样每级页表只有(2^9 = 512)个条目，由于大部分条目都会被设置成无效的，这样其对应的一级和零级页表就不需要分配，所以节省大量的空间。这样从虚拟地址到物理地址的转换过程如下：首先从虚拟地址中拿到L2的9位索引从第2级页表查询得到PTE，将其PPN和L1的9位索引组合从第1级页表查询得到PTE，将其PPN和L0的9位索引组合从第0级页表查询得到PTE，然后将其PPN和虚拟地址的低12位组合得到最终的物理地址。

限于篇幅原因，这里就不过于详细的介绍内核地址空间映射等内容，可以去手册book-riscv-rev2.pdf中阅读。下面就几个实验进行分析。

Speed up system calls

我们知道，执行系统调用的时候，需要通过ecall指令陷入内核，然后在内核态执行完系统调用时再返回用户态，这样是比较耗时的。为了加速某些系统调用，可以让用户空间和内核空间共享一片只读的物理内存空间，这样可以避免用户态和内核态之间的切换。

这道题是在每个进程创建的时候分配一个额外的物理页面用于存放进程号PID，并将这个物理页面和用户地址空间某个地址(这个地址在TRAPFRAME下面，kernel/memlayout.h文件中定义的USYSCALL)进行映射。之后获取PID就可以不需要陷入内核态，直接访问这个地址就行。

为了保存这个分配的物理内存的地址，需要先在kernel/proc.h的进程结构体中定义一个指针struct usyscall*：

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
// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  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

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // 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
  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)
  struct usyscall *usyscall;   // data page for usyscall
};

然后在kernel/proc.c中的创建进程的函数allocproc中分配一个额外的物理页面，用于存放进程的pid：

1
2
3
4
5
6
7
  // Allocate a usyscall page.
if ((p->usyscall = (struct usyscall *)kalloc()) == 0) {
    freeproc(p);
    release(&p->lock);
    return 0;
}
p->usyscall->pid = p->pid;

在kernel/proc.c中的页表创建函数proc_pagetable中进行上述页面的虚拟地址和物理地址映射：

1
2
3
4
5
6
7
8
9
10
  // map the USYSCALL just below TRAPFRAME(set PTE_U for user access)
if(mappages(pagetable, USYSCALL, PGSIZE,
            (uint64)(p->usyscall), PTE_R | PTE_U) < 0) {
    printf("map usyscall failed\n");
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
}

不要忘记在进程释放函数freeproc中释放掉这个页面：

1
2
3
if(p->usyscall)
    kfree((void*)p->usyscall);
p->usyscall = 0;

以及在proc_freepagetable中解除页面映射：

1
uvmunmap(pagetable, USYSCALL, 1, 0);

Print a page table

设计一个函数用于打印页表(三级页表的内容)，就是遍历页表然后打印，需要注意格式：

在kernel/vm.c中添加函数：

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
// print the 3 level pagetable
void vmprint(pagetable_t pagetable) 
{
  // vmprint times(0, 1, 2)
  static int num = 0;
  if (num == 0)
    printf("page table %p\n", pagetable);
  for (int i = 0; i < 512; i++) {
    pte_t pte = pagetable[i];
    if (pte & PTE_V) {
      for(int j=0; j<=num; ++j) {
        printf(" ..");
      }
      if (num != 2) {
        printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
        uint64 child = PTE2PA(pte);
        ++num;
        vmprint((pagetable_t)child);
        --num;
      } else {
        // this is leaf, do not deep in
        printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
      }
    }
  }
}

在kernel/defs.h中添加声明：

1
void vmprint(pagetable_t pagetable);

Detecting which pages have been accessed

给页表Flags中添加一位用于标志页面是否被访问，并实现sys_pgaccess系统调用。

首先在kernel/riscv.h中添加相应的宏定义：

1
#define PTE_A (1L << 6) // 1 -> page accessed

在kernel/sysproc.c中实现相关系统调用，首先调用argaddr和argint获取到系统调用的三个参数，然后调用walk函数得到每个需要确认的每个0级页表PTE，判断页面标志来确认是否访问，最后不要忘记将页面的PTE_A标志清0：

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
int
sys_pgaccess(void)
{
  uint64 address;
  int len;
  uint64 mask_address;
  uint32 mask = 0;
  if (argaddr(0, &address) < 0)
    return -1;
  if (argint(1, &len) < 0 || len > 32)
    return -1;
  if (argaddr(2, &mask_address) < 0)
    return -1;
  struct proc* proc = myproc();
  for(int i=0; i<len; ++i) {
    pte_t* pte = walk(proc->pagetable, address+i*PGSIZE, 0);
    if (*pte & PTE_A) {
      mask |= 1<<i;
      *pte &= ~PTE_A;
    }
  }
  if (copyout(proc->pagetable, mask_address, (char*)&mask, 4) < 0)
    return -1;
  return 0;
}

为了使用walk函数，需要在kernel/defs.h中添加函数声明：

1
pte_t* walk(pagetable_t pagetable, uint64 va, int alloc);

测试结果

2022/6/7测试通过(这里为了通过全部测试，添加了answers-pgtbl.txt文件，这个文件用来写实验中问题的答案)：

参考文献

  1. https://pdos.csail.mit.edu/6.828/2021/schedule.html