页表是最流行的内存管理机制，操作系统通过页式管理可以为每个进程提供私有地址空间和内存，页表决定了内存地址的意义以及可访问的物理地址范围。

这样的机制使xv6能够隔离不同进程的地址空间和在简单物理内存中复用地址（虚拟地址相同物理地址不同）。

本次试验还会涉及到trampoline机制，这一部分我认为十分有趣。

xv6-book Chapter 3 部分内容

一、分页硬件（Paging hardware）

xv6是使用Sv39机制的64位RISC-V系统，虽然地址长度为64位，但只使用低39位（0-38）操纵虚拟地址。RAM使用物理内存（伴随着物理地址），分页硬件通过将虚拟地址映射为物理地址来连接这两种地址。

Sv39机制：64位中的高25位被预留（不使用），低39位中的低12位作为页内偏移，因此有$2^{27}$个页表项（39位中的高27位表示不同的页表）。每个页表项有64位，但只用其中的54位：包含44位物理地址和10位的标志位（flag）。图3-1为简化的逻辑页表机制。

实际上进行页表映射的时候使用了三级页表，39位中的高27位寻找页表，分为三个9位，每个页表也占一个页大小的内存（4096B），因此$\frac{4096B}{64bit}=2^9$刚好一个页可以容纳$2^9$个页表项。

三级页表还有一个好处，如果某个进程只使用从0开始的一小段内存（小于一个页大小），内核不用将所有页表都放入内存，只需要调入3个页表就可以查询到物理页，因此可以省下$511$个中间页表以及$511\times512$个底层页表。图3-2为三级页表的映射过程，图3-3为映射后物理地址表示，其中包含10bit长度的标志位，位于低10位，包含有效位和一些权限等，项目实现中会用到。

二、内核地址空间

图3-4展示了内核虚拟地址如何映射为物理地址：

QEMU模拟的内存布局分为两块：

• 物理RAM：xv6的内核地址空间的内存（RAM，由QEMU模拟）从0x80000000（KERNBASE）开始到0x88000000(PHYSTOP)。
• I/O设备（MMIO）：物理地址在0x80000000之下，用作与I/O设备（由QEMU模拟）比如磁盘交互。

内核地址的映射方式为直接映射，即：

$$Virtual\ Address(VA) = Physical\ Address(PA)$$

比如物理地址为0x80000000的内存的逻辑地址也为0x80000000，这种映射简化了代码，比如fork命令分配内存给子进程时可以直接对物理地址进行操作，不需要额外的地址转换逻辑。

但在xv6中有两个例外不使用直接映射：

• trampoline（在chapter 4中会详细介绍）：为了保证CPU特权级能够平滑切换（PC不需要特意改变），内核空间和用户空间的trampoline都位于虚拟地址最顶端（见图3-4），这一部分虚拟地址不使用直接映射。同时在内核空间中还有一份地址指向物理内存中的trampoline，这个地址使用直接映射。因此trampoline在内核空间中进行了两次映射，一个在虚拟地址的最顶端，另一个通过直接映射。

• kernel stack pages（内核栈）:为了防止内核栈溢出造成操作系统的崩溃，xv6设计了Guard Page机制，即将一个页的虚拟地址PTE设置为invalid。这样即便内核栈溢出，也只会造成panic，而不是直接修改内核空间非法地址造成系统崩溃。Guard page实际上只需要起到一个guard作用，如果给其分配物理内存没有任何作用，为了防止浪费内存，内核栈不使用直接映射。

三、创建地址空间

大部分操作地址空间和页表的代码在文件kernel/vm.c中，核心数据结构是pagetable_t（一个指向RISC-V根页表的指针），pagetable_t可以指向内核页表或者用户进程的页表。

启动时main函数调用kvminit使用kvmmake创建内核页表，此时xv6还没有启用分页，地址直接指向物理内存。kvminit首先分配一个物理页存放根页表，接下来它调用kvmmap安装内核所需的转换（包括内核指令和数据、直到PHYSTOP的物理内存以及指向I/O设备的内存）。proc_mapstacks为每个进程分配内核堆栈，调用kvmmap映射每个堆栈到KSTACK创建的虚拟地址（留下了guard page的空间）。

kvmmap调用mappages下载一个从虚拟地址到对应物理内存的页表映射，对每个将被映射的虚拟地址，mappages调用walk找到这个地址的pte的地址，接下来初始化这个pte（获取对应的物理页号、flag等）。

walk模拟了RISC-V的分页硬件（就像是它在查找pte，如图3-2）。walk每次下降三级页表的9bits，用这9bits的虚拟地址去寻找下一级或者是最终的pte的pte。如果pte不是有效的，说明所需的页没有被分配物理内存；如果alloc变量被设置了，walk会分配一个新的页表并将物理地址放进对应的pte中。最后walk返回最低级的pte的地址。

以上的代码都以来物理内存被直接映射到内核虚拟地址空间：比如当walk下降页表等级时，它将从pte获取的（物理）地址拉到更低一级的页表，接下来使用这个地址作为虚拟地址去获取更低一级的pte。

main函数调用kvminithart下载物理页表，它将根页表的物理地址写入寄存器satp。此后CPU会使用内核页表对地址进行翻译。因为内核使用直接映射（Identity Mapping），当前下一条指令的虚拟地址会映射到正确的物理内存地址。

TLB（Translation Look-aside Buffer）：每个RISC-V的CPU缓存页表入口到TLB中，当xv6改变了一个页表后，它必须让CPU将对应已经缓存的TLB入口失效。如果不这么做，在接下来的某个时刻TLB会使用一个旧的映射指向同时被分配给其他内存的物理页，因此一个进程就可能访问其他进程的内存。RISC-V有sfence.vma指令可以清空当前CPU的TLB，xv6在kvminithart重新加载satp寄存器后和在切换到一个用户页表的trampoline代码返回用户空间前执行sfence.vma。 为了避免完全清空TLB，RISC-V的CPU支持地址空间标识符（ASIDs），内核可以只清空特定地址空间的TLB入口。

四、物理内存分配代码

分配器位于kernel/kalloc.c文件中。这个分配器的数据结构是一个可用物理内存页的空闲链表。每个空闲页的链表元素是struct run，存放在每个空闲页的开头（因为空闲页中没有存储有效数据）。空闲链表由一个自旋锁保护，空闲链表和自旋锁封装在一个数据结构中，表示这个自旋锁是保护这个链表的，自旋锁有关的内容在chapter 6中详细描述。

main函数调用kinit初始化分配器。kinit初始化空闲链表来获取kernel末尾到PHYSTOP的每个页。xv6应该通过解析硬件来决定有多少物理内存是可分配的，但事实上xv6假设机器有128MB的RAM内存。kinit调用freerange通过对每一页调用kfree添加内存到空闲链表。一个pte只能指向一个对齐到4096字节边界的物理地址（是4096的倍数），所以freerange使用PGROUNDUP来确保它只释放对齐的物理地址。分配器起初没有内存，这些kfree的调用给分配器一些内存去管理。

有时分配器将地址看作整数来对其进行算术运算，有时看作指针来读写内存（比如操作存储在每个空闲页中的struct run）。

五、进程地址空间

每个进程有分离的页表，当xv6在进程间切换时，页表也会切换。当进程向xv6请求更多用户内存时，xv6首先调用kalloc分配物理页，接下来将指向新物理页的pte添加到进程页表，xv6为这些pte设置标志位。大部分用户进程不会使用整个用户地址空间，xv6将未使用的PTE_V保留为空。

以下是使用页表的一些优点：

1. 每个进程具有私有用户内存。
2. 每个进程将其内存视为连续的虚拟地址，但实际上在物理内存中分布并不连续。
3. 内核使用trampoline代码在用户地址空间的最顶部，因此一个物理页可以出现在所有的用户地址空间中。

图3-5展示了一个xv6中执行的进程的用户空间的详细内容:stack是一个单独的页，展示了exec创建的初始内容。在stack顶部是一个字符串，包含命令行参数和一个指向这些参数的一个数组；紧接着是一些值，它们可使程序从main开始执行，好像main(argc, argv)刚被调用一样。

为了检查一个用户栈的溢出行为，xv6设置了一个不可访问的guard page在栈的下方，类似于上面提到过的kernel中的guard page，此处设置PTE_U为空。现实中我们用到的操作系统可能不会这么做，反而会在栈溢出后为其分配更多的内存。

Lab3 实现

一、Speed up system calls (easy)

当进程创建后，为了提升调用system call的速度，可以将内核的一些数据映射到用户态，这样用户态使用系统调用获得这些数据的时候就不必切换到内核态，省去了中间的消耗。

这个lab以pid为例，pid原本存储在内核空间中，用户态不可以直接访问，现在创建一个只读用户页表，将一些内核空间的pid存入这个用户页表中。在页表的起始处存放一个数据结构struct usyscall，在进程创建时存放pid到这个数据结构中。

首先在进程页表映射的操作文件中使用mappages添加USYSCALL的映射，mappages的参数：进程根页表地址pagetable，要映射到虚拟地址va，映射空间大小size，被映射的物理地址pa，页表项权限（标志位）。

• 进程根页表地址由uvmcreate返回，创建完进程后就会创建用户虚拟地址空间，由于页表在内核态，因此使用直接映射。
• 要映射的地址USYSCALL在实验源码中直接给出，当前实验是在TRAPFRAME之下，因此$USYSCALL = TRAPFRAME - PGSIZE$。
• 实际存储的物理地址存储在进程控制块数据结构的usyscall变量中。
• 标志位设置为用户可访问且只读。

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

  // An empty page table.
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;

  // map the trampoline code (for system call return)
  // at the highest user virtual address.
  // only the supervisor uses it, on the way
  // to/from user space, so not PTE_U.
  if(mappages(pagetable, TRAMPOLINE, PGSIZE,
              (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the usyscall to speed up system call
  if (mappages(pagetable, USYSCALL, PGSIZE,
               (uint64)(p->usyscall), PTE_R | PTE_U) < 0){
    uvmunmap(pagetable, USYSCALL, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  return pagetable;
}

以上代码完成了地址映射相关工作，将usyscall结构体的物理地址在用户创建时映射到用户页表中。接下来的代码要实现在创建进程时添加usyscall结构体相关的页，并初始化好一些必要的变量：使用kalloc分配一个页，如果kalloc没能分配对应的内存，说明这个进程创建失败，需要使用freeproc释放此进程；如果分配成功就在此初始化一些值，此处需要初始化usyscall->pid。

static struct proc*
allocproc(void)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state == UNUSED) {
      goto found;
    } else {
      release(&p->lock);
    }
  }
  return 0;

found:
  p->pid = allocpid();
  p->state = USED;

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

  // Alloc a usyscall page.
  if ((p->usyscall = (struct usyscall *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  p->usyscall->pid = p->pid;

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

  // Set up new context to start executing at forkret,
  // which returns to user space.
  memset(&p->context, 0, sizeof(p->context));
  p->context.ra = (uint64)forkret;
  p->context.sp = p->kstack + PGSIZE;

  return p;
}

到此这个任务已经完成了将一部分内核空间中的数据映射到用户空间中，现在还缺少进程释放时将先前添加的页释放操作。

static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if(p->usyscall)
    kfree((void*)p->usyscall);
  p->usyscall = 0;
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  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;
}

类似trapframe，usyscall页在进程销毁的时候需要使用kfree对这个页进行释放，kfree会进行物理释放，也就是除了将这个页标记为未使用，还会使用memset将页内的所有数据用1覆盖，防止其他进程分配这个物理页之后读取到之前进程写入的数据。这里可以观察到在映射页表的时候映射了trampoline页，但是这里没进行释放，是因为trampoline在物理页中只有一个，初始化好之后所有进程的trampoline使用的都是这个物理页中的内容，因此不能进行释放。

二、Print a page table (easy)

为了方便可视化RISC-V的页表以及debug,第二个任务是写一个函数打印页表中的内容。当xv6启动时，会打印如下内容：描述第一个进程刚加载完init时的页表。

page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..509: pte 0x0000000021fdd813 pa 0x0000000087f76000
.. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

参考一下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){
      panic("freewalk: leaf");
    }
  }
  kfree((void*)pagetable);
}

遍历整个页表，找到有效的pte，然后打印一下信息，并对下一级页表进行递归。此外还需要在kernel/defs.h中添加一下函数签名，这里就不放代码了。

void
vmprint(pagetable_t pagetable, int level)
{
  if (level == 2) {
    printf("page table %p\n", 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){
      for (int j = level; j <= 2; j++)
        printf(" ..");
      printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
      if (level > 0) {
        uint64 child = PTE2PA(pte);
        vmprint((pagetable_t)child, level - 1);
      }
    }
  }
}

三、Detecting which pages have been accessed (hard)

在这一部分我们要为xv6添加新功能：通过监测RISC-V页表的访问位，将哪一页被访问过（读/写）的信息检测并报告给用户空间。

在kernel/riscv.h中添加访问标志位，表示是否被读写过，对应图3-2将PTE_A对应为第6位。这是一个系统调用，因此使用myproc可以获得发起调用的用户进程的进程状态信息（包括页表）。

这个系统调用有三个参数：

1. 第一个检查的用户页的虚拟地址。
2. 要检查的页的数量。
3. 用户空间中存储该系统调用结果的虚拟地址。

这个系统调用的结果用一个bitmask表示，第一个检查的页对应最低有效位。三个参数使用argaddr和argint获取，由于xv6是64位操作系统，此处设置一个limit每次最多检查64个页是否被访问过。

遍历所有要检查的页，对每个pte进行校验，这里还要注意校验有效位。校验完后要将访问位消除，否则就无法确定某个页是否在上一次pgaccess后还被访问过。

int
sys_pgaccess(void)
{
  uint64 base;
  int npage;
  uint64 bitmask_addr;
  uint64 bitmask = 0;
  struct proc *p = myproc();
  pagetable_t pagetable = p->pagetable;

  if (argaddr(0, &base) < 0 || argint(1, &npage) < 0 || argaddr(2, &bitmask_addr) < 0)
    return -1;

  if (npage > 64)
    return -1;

  for (int i = 0; i < npage; i++) {
    uint64 va = base + i * PGSIZE;
    pte_t *pte = walk(pagetable, va, 0);
    if (pte != 0 && ((*pte) & PTE_V) && ((*pte) & PTE_A)) {
      bitmask |= (1L << i);
      (*pte) &= (~(PTE_A));
    }
  }

  if (copyout(p->pagetable, bitmask_addr, (char *)&bitmask, sizeof(bitmask)) < 0)
    return -1;

  return 0;
}