本文是MIT课程6.S081操作系统学习笔记的一部分：

相关的代码都放在了GitHub下了：RayZhang13/MIT-6.S081-2021

课程相关的资源、视频和教材见Lab util: Unix utilities开头。

xv6里头的细节有一点点多，跟着书上和上课的讲解看的还是有点迷… 水温有点起来了

突然意识到原来上课是要课前预习的啊（坏了，从大二后就没咋干过这种事情了）

这次的主要内容是页表和虚拟内存，我们要对页表和内存页进行相关的操作。

准备

对应课程

本次的作业是Lab Pgtbl，我们将探索页表的相关用法，并使用页表来加速特定的系统调用，并检测哪个页表刚刚被访问过了。

我们需要看掉Lecture 4，也就是 B站课程的P3，上课主要都在讨论虚拟内存和页表的相关概念，

另外请阅读教材第三章Page tables，了解虚拟内存和页表的相关概念。

系统环境

使用Arch Linux虚拟机作为实验环境～

环境依赖配置，编译使用make qemu等，如遇到问题，见第一次的Lab util: Unix utilities

使用准备

参考本次的实验说明书：Lab: page tables

从仓库clone下来课程文件：

1
git clone git://g.csail.mit.edu/xv6-labs-2021

切换到本次作业的pgtbl分支即可：

1
2
cd xv6-labs-2021
git checkout pgtbl

在作业完成后可以使用make grade对所有结果进行评分。

题目

xv6虚拟内存简介

页表简介和walk函数

在所有事情开始之前，我们先来简单地看一下xv6内部对于虚拟内存和页表的构造方式。首先我们意识到对于不同进程而言，其地址空间是相互独立的，通过虚拟内存的方式我们可以确保进程的内存空间不会被其他进程随意修改。为了完成虚拟内存到物理内存的映射，xv6为每一个进程实现了一张页表，用于根据虚拟内存地址查询对应的物理内存地址。

如上所示的就是xv6内部实现的三级页表，在xv6中，我们只使用39位作为地址，我们进一步将该39位地址分为4段，其中末尾12位为内存页地址偏移量，这也进一步验证了一个内存页的大小为4KB，即2122^{12}字节，另外三段分别是L0、L1、L2，构成了一个三级页表的结构。

当我们需要对页表进行查询时，我们首先根据寄存器satp获得页表的内存地址（注意到satp的修改是特殊的权限指令，用户程序不能随意更改，否则就会破坏隔离性），随后我们根据L2段读出的数值计算index索引位置，从一级页表中获取到二级页表的地址，随后我们进入到二级页表，根据L1段读出的数值计算index索引位置获得三级页表的位置，再进入三级页表，最后根据L0的数值计算index索引位置，读取到最终的物理地址位置。

使用多级页表的好处是显而易见的，和单级页表相比可以节省出更多的内存，例如一级页表可以在部分二级页表的入口处标记为不可用，那就节省了该条目下二级页表和二级页表下更多三级页表的内存开销，在单级页表中，每一个内存页的虚拟地址都是要做映射的，这就消耗了大量的内存资源。一个典型的单级页表如下所示：

处理三级页表的过程，相关代码存储在kernel/vm.c中，见walk函数：

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
// 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) 
  //pagetable表示一级页表的地址，va为虚拟内存地址，alloc表示是否创建条目
{
  if(va >= MAXVA) //虚拟内存地址越界，报错
    panic("walk");

  for(int level = 2; level > 0; level--) { //分三级地址
    pte_t *pte = &pagetable[PX(level, va)]; //使用位运算获取L2/L1/L0，计算索引位置
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte); //若条目有效，将页表指针指向下级页表
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0) //若无效，且alloc有设置，创建相关条目
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)]; //最后返回三级页表中映射的物理地址
}

内核地址空间

内核地址空间的映射简单来看如图所示：

可以看到物理地址0x80000000往上到PHYSTOP的空间属于RAM，都是直接映射到了内核地址空间。此外，QEMU还模拟了I/O设备，位于地址0x80000000下方的I/O设备控制寄存器也是直接进行映射的。

在内核地址空间顶部，有几个内核虚拟地址不是直接映射的：

  • trampoline页。它被映射在虚拟地址空间的顶端；用户页表也有这个映射。第 4 章讨论了 trampoline 页的作用，但我们在这里看到了页表的一个有趣的用例；一个物理页（存放 trampoline 代码）在内核的虚拟地址空间中被映射了两次：一次是在虚拟地址空间的顶部，一次是直接映射。
  • 内核栈页。每个进程都有自己的内核栈，内核栈被映射到地址高处，所以在它后面 xv6 可以留下一个未映射的守护页。守护页的 PTE 是无效的(设置 PTE_V)，这样如果内核溢出内核 stack，很可能会引起异常，内核会报错。如果没有防护页，栈溢出时会覆盖其他内核内存，导致不正确的操作。

我们接下来稍微看一下内核地址空间是如何初始化的，在kernel/main.c下的主函数下，在物理内存页初始化之后，我们调用了kvminit()来创建内核页表。我们继续深入看位于kernel/vm.c下的kvminit()：

1
2
3
4
5
6
// Initialize the one kernel_pagetable
void
kvminit(void)
{
  kernel_pagetable = kvmmake();
}

继续深入看kernel/vm.c下的kvmmake()，这里就是设置内核地址空间的核心代码了，我们可以看到内核代码对物理地址做了多次映射：

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
// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  pagetable_t kpgtbl;

  kpgtbl = (pagetable_t) kalloc();
  memset(kpgtbl, 0, PGSIZE);

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

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

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

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

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

  // map kernel stacks
  proc_mapstacks(kpgtbl);
  
  return kpgtbl;
}

其中kvmmap的各个参数是分别是内核页表kpgtbl，虚拟地址va，物理地址pa，映射大小sz和权限标志位perm：

1
2
3
4
5
6
7
8
9
// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

继续往下看mappages()，就是设置映射最底层的实现了，参数分别为页表地址pagetable，虚拟地址va，映射大小sz，物理地址pa和访问标志位perm：

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
// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  if(size == 0)
    panic("mappages: size");
  
  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    if(*pte & PTE_V)
      panic("mappages: remap");
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

kernel/main.c中在内核页表生成结束后，会调用kvminithart()来映射内核页表，将根页表页的物理地址写入寄存器satp，随后CPU使用内核页表翻译的地址工作：

1
2
3
4
5
6
7
8
// Switch h/w page table register to the kernel's page table,
// and enable paging.
void
kvminithart()
{
  w_satp(MAKE_SATP(kernel_pagetable));
  sfence_vma();
}

用户地址空间

相比之下，用户地址空间的构造情况如下：

可以看到，一个进程的用户内存从虚拟地址 0 开始，可以增长到 MAXVA，原则上允许一个进程寻址 256GB 的内存。内核会映射带有 trampoline 代码的页，该 trampoline 处于用户地址空间顶端，因此，在所有地址空间中都会出现一页物理内存。栈内存只有一页，图中显示的是由 exec 创建的初始内容。字符串的值，以及指向这些参数的指针数组，他们都位于栈的最顶端。trapframe用于保存所有用户寄存器，这点在后续章节会提及。

另外，为了检测用户栈溢出分配的栈内存，xv6 会在 stack 的下方放置一个无效的保护页。如果用户栈溢出，而进程试图使用栈下面的地址，硬件会因为该映射无效而产生一个页错误异常。

接下来看代码实现，在kernel/main.c中，我们看到main()下使用userinit()来创建第一个用户进程，我们去kernel/proc.c下查看，userinit()使用allocproc()来生成用户地址空间，同样fork()在处理新的用户子进程时也是调用了allocproc()。

那么我们继续看allocproc()，这段代码也在kernel/proc.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
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;
  }

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

首先其对进程列表进行遍历，查找到状态为UNUSED的进程，然后我们进入到found中，首先分配新的PID数值并修改进程状态，然后我们分配trapframe内存页空间（获得的地址很显然是物理地址/内核地址空间地址），并把相关的信息更新到p中，也就是一个叫proc的结构体中表示进程相关信息，见kernel/proc.h。

接下来，我们调用proc_pagetable()，根据传入的p，把信息拿出来开始构建我们的用户空间页表：

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
// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
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;
  }

  return pagetable;
}

可以看到先使用uvmcreate()创建了页表的空间，然后把trampoline和trapframe做了映射… 大致就是这么个逻辑

实现系统调用的加速

要求和提示

在这个部分中，我们要通过调整页表的映射来实现对特定的系统调用的加速。

在部分操作系统（例如Linux中），会使用用户空间和内核空间之间的一块只读区域用来进行数据共享，以此来达到加速特定的系统调用的目的，这样就消除了与内核交互产生的开销。在本部分中，我们将实现对getpid系统调用的优化。

当一个进程被创建时，我们需要将一个只读的内存页映射到USYSCALL上，其中USYSCALL是一个虚拟内存地址，见kernel/memlayout.h。在该内存页上我们需要存储一个叫struct usyscall的结构体，见kernel/memlayout.h，然后将其初始化使其存储当前进程的PID。下面是memlayout.h的节选部分：

1
2
3
4
#define USYSCALL (TRAPFRAME - PGSIZE)
struct usyscall {
  int pid;  // Process ID
};

在这个Lab中，系统在用户空间部分已经提供了ugetpid()，并会自动使用USYSCALL的映射，ugetpid函数就是我们测试时的函数，为了使得他工作正常我们需要完成相关修改。这段见user/ulib.c：

1
2
3
4
5
6
7
8
#ifdef LAB_PGTBL
int
ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;
  return u->pid;
}
#endif

相关提示：

  • 可以在kernel/proc.c下的proc_pagetable中处理内存映射问题。
  • 注意处理访问标志位使得该内存页对用户空间来说是只读的。
  • 了解mappages()的使用方法会很有帮助。
  • 不要忘记在allocproc()中分配和初始化内存页。
  • 确保在freeproc()中正确地释放了内存页。

分配并初始化usyscall

算了，看了那么多，说点人话解释一下吧… 正常情况下如果我们需要获得当前进程的PID，我们需要执行系统调用，切到内核态，从proc结构体里头把pid读出来…

现在的意思是说我们可以在内存中开辟一块空间，准确的来说是一个struct usyscall结构体，里面包装了一个pid的整型变量。我们在内核中创建一个新的用户进程的时候，为这个结构体开辟相应的内存空间，把PID填进去，然后在对应的用户进程中把它直接映射到用户虚拟内存的某个位置… 这样子就可以在用户态随时访问PID信息了。

而这个位置呢，已经明示的不能再清楚了，也就是USYSCALL，他指向的位置是TRAPFRAME - PGSIZE，也就是TRAPFRAME下面一个页的位置，我们不妨把这个内存页叫做usyspage：

接下来思考我们要做的事情：

  • 在创建用户进程时，额外开辟空间给struct usyscall，并初始化填入PID数据，制作成内存页。
  • 在创建用户地址空间的时候，将内存页映射到USYSCALL。
  • 释放进程数据的时候记得把usyscall也给释放了。

那现在考虑实现创建用户进程时，开辟struct usyscall空间并初始化。

根据刚才的分析，我们把代码增加在allocproc()中处理即可，照猫画虎。由于到时候proc_pagetable是通过读取结构体p来实现映射的…

我们需要对struct proc添加一个额外的成员，在kernel/proc.h中，我们修改为如下：

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

接下来我们在kernel/proc.c中的allocproc()下分配并初始化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
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
// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
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;
  }

  // Allocate a usyscall page
  if((p->usyspage = (struct usyscall *)kalloc()) == 0) {
      freeproc(p);
      release(&p->lock);
      return 0;
  }
  
  // Init the usyscall page
  p->usyspage->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;
}

修改proc_pagetable添加映射

接下来，我们要修改kernel/proc.c下的proc_pagetable()，将刚刚创建的struct usyscall映射到用户地址空间的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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
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 page
  if(mappages(pagetable, USYSCALL, PGSIZE,
              (uint64)(p->usyspage), PTE_R | PTE_U) < 0){
    uvmunmap(pagetable, USYSCALL, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  return pagetable;
}

很简单的操作了属于是，把刚才创建的usyspage的物理地址映射到用户空间的USYSCALL上即可。

释放进程空间

释放进程空间的时候，首先需要考虑的就是清除干净struct proc里面的东西，也就是调用freeproc()的时候需要注意的，见kernel/proc.c。我们在代码里面加入释放usyspage的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// free a proc structure and the data hanging from it,
// including user pages.
// p->lock must be held.
static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if (p->usyspage) 
    kfree((void *)p->usyspage);
  p->usyspage = 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;
}

同时注意到这里还调用了proc_freepagetable()来清除映射和释放页表占用内存，我们这里需要加入一行，同时释放USYSCALL地址上的映射，见kernel/proc.c：

1
2
3
4
5
6
7
8
9
10
// Free a process's page table, and free the
// physical memory it refers to.
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmunmap(pagetable, USYSCALL, 1, 0);
  uvmfree(pagetable, sz);
}

实现页表打印

要求和提示

在本部分中，我们需要将RISC-V的页表可视化，也就是实现一个页表内容的打印功能，作为后续调试的辅助工具。

我们需要定义一个叫做vmprint()的函数，这个函数应当传入一个类型为pagetable_t的参数，也是页表的指针，然后将页表的全部有效信息打印出来。题目要求在kernel/exec.c下的exec()中，在最后的return argc前加入一行（疯狂暗示，喂到嘴巴里）：

1
if(p->pid==1) vmprint(p->pagetable);

来实现对第一个进程的页表的打印。

题目中给出了示例，当第一个进程刚完成exec()执行了/init时的页表状态：

1
2
3
4
5
6
7
8
9
10
11
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

第一行表示了vmprint传入的参数，也就是页表入口的地址。接下来的每一行都是PTE，以及PTE下可能存在的下级页表（不用我说你也能看出来这就是一个DFS递归）。

我们用..来表示这个PTE的深度，最开始打印的数字是这个PTE在一个4KB内存页（共512个PTE）的编号，接下来会打印PTE的具体数值，这个数值嘛表面上看不出啥名堂，因为他是这样子组成的，所以打印出来就为了看个乐呵？

然后我们使用已经有的PTE2PA转换函数（其实就是个位运算），把物理地址PA从PTE这堆乱糟糟的数字里读出来。

相关提示：

  • 可以把vmprint()放在kernel/vm.c里面
  • 记得使用kernel/riscv.h最后添加的宏定义，包括但不限于PTE2PA等
  • 强烈建议参考vm.c文件中的freewalk函数（疯狂暗示，喂嘴巴里了）
  • 记得在kernel/defs.h中定义vmprint函数，以便在exec.c中成功调用
  • 在printf中使用%p来打印完整的16进制64位地址和PTE信息

核心打印函数

众所周知这是个DFS递归，我们被给到了一个递归的入口页表地址，在一个内存页，我们共有512个PTE需要遍历。每次我们需要检查该PTE是否有效，也就是检查V位，如果有效就需要我们打印。此外，我们检查R，W和X位，如果这些位没有被置为有效，说明该PTE指向下一个下级页表，要开始套娃了（相关的代码可以观察freewalk函数,实际上非常类似）。我们在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
void pgtblprint(pagetable_t pagetable, int depth) {
  for(int i = 0; i < 512; i++) {
    pte_t pte = pagetable[i];
    // if PTE is valid
    if(pte & PTE_V) {
      for(int t = 0; t < depth; t++){
        printf(" ..");
      }
      printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));

      // if this PTE points to a lower-level page table
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
        // start with new child PTE addr
        pagetable_t child = (pagetable_t)PTE2PA(pte);
        pgtblprint(child, depth + 1);
      }
    }
  }
}

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

其他设置

为了能让结果运行起来，我们还需要遵循提示中给出的指示，例如在defs.h中加入vmprint定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// vm.c
void            kvminit(void);
void            kvminithart(void);
void            kvmmap(pagetable_t, uint64, uint64, uint64, int);
int             mappages(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     uvmcreate(void);
void            uvminit(pagetable_t, uchar *, uint);
uint64          uvmalloc(pagetable_t, uint64, uint64);
uint64          uvmdealloc(pagetable_t, uint64, uint64);
int             uvmcopy(pagetable_t, pagetable_t, uint64);
void            uvmfree(pagetable_t, uint64);
void            uvmunmap(pagetable_t, uint64, uint64, int);
void            uvmclear(pagetable_t, uint64);
uint64          walkaddr(pagetable_t, uint64);
int             copyout(pagetable_t, uint64, char *, uint64);
int             copyin(pagetable_t, char *, uint64, uint64);
int             copyinstr(pagetable_t, char *, uint64, uint64);
void            vmprint(pagetable_t pagetable);

在exec.c的exec函数中的return前插入一行打印代码：

1
2
3
if(p->pid==1) vmprint(p->pagetable);

return argc; // this ends up in a0, the first argument to main(argc, argv)

测试

在目录下执行make clean; make qemu，可以看到在启动时打印出了页表的结构：

目测和给出样例一致

查询内存页访问情况

要求和提示

一些垃圾回收器可以根据内存页被访问情况的信息来进行工作。

在本部分中，我们将主要考虑为xv6实现一个新的功能，也就是检测用户空间的内存访问情况，并将信息返回给用户空间。我们需要通过检查RISC-V页表中的A标识位来实现，RISC-V硬件每当尝试解决TLB未命中问题时，访问内存页的时候就会在页表中将对应PTE的标志位置为有效。

我们的目标是实现一个叫做pgaccess的系统调用，以此来查看哪些内存页被访问过了。这个系统调用需要传入三个参数，第一个参数是开始的要查看的用户空间内存页地址，第二个参数是需要查看的内存页数量，最后传入的是一个用户地址空间，好让我们将结果写到用户地址空间，结果以bitmask的形式存储，每一位和各个内存页一一对应，第一个内存页对应最小的比特位。

相关提示：

  • 考虑在kernel/sysproc.c下实现sys_pgaccess()系统调用主要功能。
  • 需要使用argaddr()和argint()来获取系统调用传入的参数，这一块可以详见上次的Lab syscall: System calls。
  • 由于我们需要将结果返回给用户态的地址，因此有必要使用内核态中的临时缓冲区进行结果的处理，然后使用copyout()函数将结果复制到用户态，这段也可见Lab Syscall中相关内容。
  • 可以设置扫描的内存页数上限。
  • 在kernel/vm.c下的walk()函数会对找到正确的PTE很有帮助。
  • 需要在kernel/riscv.h中额外定义一下PTE_A，也就是访问标记的比特位。（不敢相信他们居然原来没有加）
  • 确保在扫描内存页结束后将标志位PTE_A清零，不然下次扫描这个页的时候你看到标志位就乱了，不知道有没有被访问过了。
  • 在调试页表的时候可以使用vmprint()，活学活用了属于是。

添加PTE_A定义

一直没想到，居然这都没加，还要我自己整，就很神奇。

那就看一下教材手册吧，貌似还是这张图：

可以看到Access标志位是第6位（从右到左，从0数起），所以在kernel/riscv.h下面，我们就照猫画虎处理一下：

1
2
3
4
5
6
#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
#define PTE_A (1L << 6) // 1 -> page accessed

系统调用配置

在之前的Lab Syscall里面，我们已经大致了解了创建一个系统调用需要哪些流程，这里可以帮忙再回顾一下：

  • 在user/user.h中添加系统调用的函数声明。
  • 在kernel/syscall.h中添加新系统调用的编号。
  • 在user/usys.pl中添加系统调用项，生成相关汇编代码，即给a7寄存器赋值，使用ecall指令陷入内核态。
  • 在kernel/syscall.c的syscalls表中添加新的映射关系，指向需要执行的函数（也需另外实现），例如fork系统调用就实现在kernel/sysproc.c和kernel/proc.c中。

定睛一看，全帮忙处理好了。谢谢有被暖心到，不用自己加了。所以我们可以专注到系统调用的核心函数sys_pgaccess怎么写了。

例行操作，我们在kernel/sysproc.c下实现sys_pgaccess()。可以看到，已经被填好模板了，不用额外创建了，暖心～

那么我们需要使用argaddr和argint来获取系统调用参数，随后从某个用户地址开始向后读取若干个内存页，并检查标志位信息，如果标志位有效读取结束需要清空。最后处理完后，将结果以bitmask的形式通过copyout()写到用户空间地址。

在这里，我们不妨规定使用64位空间来存储bitmask，因此，我们最多可以扫描的页面数量是64。代码如下：

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
#ifdef LAB_PGTBL
int
sys_pgaccess(void)
{
  uint64 va;
  int page_nums;
  uint64 out_addr;
  // get syscall params
  if(argaddr(0, &va) < 0) {
    return -1;
  }
  if(argint(1, &page_nums) < 0) {
    return -1;
  }
  if(argaddr(2, &out_addr) < 0) {
    return -1;
  }

  // check if the page numbers to scan is valid
  if(page_nums < 0 || page_nums > 64) {
    return -1;
  }

  uint64 bitmask = 0;
  pte_t *pte;
  struct proc *p = myproc();

  for(int i = 0; i < page_nums; i++) {
    // check if va is out of range
    if(va >= MAXVA) {
      return -1;
    }
    // get pte addr by va
    pte = walk(p->pagetable, va, 0);
    if(!pte) {
      return -1;
    }
    // check if accessed
    if(*pte & PTE_A) {
      bitmask |= (1 << i);
      // clear the bit afterwards
      *pte ^= PTE_A;
    }
    // move va to next mem page
    va += PGSIZE;
  }
  
  // copy bitmask to user space
  if(copyout(p->pagetable, out_addr, (char *)&bitmask, sizeof(bitmask)) < 0) {
    return -1;
  }
  return 0;
}
#endif

另外，我们还需要在kernel/defs.h中添加一下walk()函数的声明，不然貌似调用不起来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// vm.c
void            kvminit(void);
void            kvminithart(void);
void            kvmmap(pagetable_t, uint64, uint64, uint64, int);
int             mappages(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     uvmcreate(void);
void            uvminit(pagetable_t, uchar *, uint);
uint64          uvmalloc(pagetable_t, uint64, uint64);
uint64          uvmdealloc(pagetable_t, uint64, uint64);
int             uvmcopy(pagetable_t, pagetable_t, uint64);
void            uvmfree(pagetable_t, uint64);
void            uvmunmap(pagetable_t, uint64, uint64, int);
void            uvmclear(pagetable_t, uint64);
uint64          walkaddr(pagetable_t, uint64);
int             copyout(pagetable_t, uint64, char *, uint64);
int             copyin(pagetable_t, char *, uint64, uint64);
int             copyinstr(pagetable_t, char *, uint64, uint64);
void            vmprint(pagetable_t pagetable);
pte_t*          walk(pagetable_t pagetable, uint64 va, int alloc);

总结

所有任务都完成之后，看一眼测试结果。

有几点需要注意下：

  • 我们需要在目录下创建一个叫做answers-pgtbl.txt，根据官方的说法是用来填课后问题，但是这里目测没有hhh，随便填一点就好。

  • 另外，还需要创建一个time.txt来表示你完成任务所花时间。

  • 测试过程中usertests耗时略长，电脑机能不行的小伙伴可以适当将测试的超时延长一点点，请把主目录下 grade-lab-pgtbl 文件里面的 timeout 参数改大点，不然可能你的测试项目还没跑完他就跳出给你标个大大的 FAIL…

接下来，使用命令make grade来进行结果测试，结果如下，没啥问题，睡觉～