MIT6.s081 2021 Lab Page tables

Speed up system calls

思路

题目要求在每个进程初始化时为它的页表插入一个页表项，内核通过这样预先缓存页表项的操作，来加速特定系统调用的执行速度。

由于前不久刚过完一遍《OSTEP》，因此我认为自己对页表机制还算比较熟悉，应对本 Lab 理应比较轻松，但在真正上手的时候，还是觉得有些无所适从，无奈老老实实地把 xv6 手册的第 3 章对照着代码仔细研读了一番，从中提炼出了几个关键的函数：

1. kernel/kalloc.c:kalloc

void *kalloc(void);

遍历空闲链表，寻找一个可分配的物理页面。若找到，返回该页面的首（物理）地址；否则，返回 0 （空指针）。

1. kernel/kalloc.c:kfree

void kfree(void *pa);

释放已分配的首地址为 pa 的物理页面，并更新空闲链表。

1. kernel/proc.c:allocproc

static struct proc *allocproc(void);

遍历进程数组 proc，寻找未被使用的 struct proc。若找到，则初始化其状态，为创建一个新的页表，并返回指向它的指针；否则，返回 0（空指针）。

1. kernel/proc.c:freeproc

static void freeproc(struct proc *p);

释放与进程 p 相关的数据的内存空间，并清空 p 的 struct proc 的所有信息。

1. kernel/vm.c:mappages

int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm);

在页表 pagetrable 中创建从起始虚拟地址 va 到起始物理地址 pa 的页表项映射，页表项的 flags 位的访问权限部分设置为 perm，其中大小为 size，将 size 分为若干页，为这些页面创建 va + i * PGSIZE -> pa + i * PGSIZE （i 代表页面的编号）的映射。

1. kernel/vm.c:uvmunmap

void uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free);

从 pagetable 中移除从虚拟地址 va 开始的 npages 个页表项。可指定 do_free 的值，若不为 0，则在移除页表项的同时，释放页表项映射 va -> pa 中 pa 指向的内存空间。

分析完几个关键函数之后，思路就比较清晰了：

1. 为 struct proc 结构体添加 struct usyscall *usc 段。
2. 在 allocproc() 中为 usc 分配物理内存，并对其赋值：p->usc->pid = p->pid;。

if ((p->usc = (struct usyscall *)kalloc()) == 0) {
	freeproc(p);
	release(&p->lock);
	return 0;
}
p->usc->pid = p->pid;

1. 在 freeproc() 中释放 usc 的物理内存。

if (p->usc)
	kfree((void*)p->usc);
p->usc = 0;

1. 在 proc_pagetable() 中使用 mappages 插入虚拟地址 USYSCALL 的页表项。

if (mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usc), PTE_R | PTE_U) < 0) {  
	uvmunmap(pagetable, TRAMPOLINE, 1, 0);
	uvmunmap(pagetable, TRAPFRAME, 1, 0);
	uvmfree(pagetable, 0);
	return 0;
}

1. 最后，非常容易忽视的，在 proc_freepagetable() 中删除虚拟地址 USYSCALL 的页表项。

uvmunmap(pagetable, USYSCALL, 1, 0);

问题

接下来讲讲我在本题遇到的几个问题。

问题 1：

原因： p->usc->pid = p->pid 放在分配物理内存之前，导致空指针解引用。

问题 2：

原因： 未在 proc_freepagetable() 中解除 USYSCALL 的页表项映射，也就是上面提到的容易忽视的第 5 点。

代码

diff --git a/kernel/proc.c b/kernel/proc.c
index 22e7ce4..5fc573f 100644
--- a/kernel/proc.c
+++ b/kernel/proc.c
@@ -127,6 +127,14 @@ found:
     return 0;
   }
 
+  // here
+  if ((p->usc = (struct usyscall *)kalloc()) == 0) {
+	freeproc(p);
+	release(&p->lock);
+	return 0;
+  }
+  p->usc->pid = p->pid;
+
   // An empty user page table.
   p->pagetable = proc_pagetable(p);
   if(p->pagetable == 0){
@@ -153,6 +161,9 @@ freeproc(struct proc *p)
   if(p->trapframe)
     kfree((void*)p->trapframe);
   p->trapframe = 0;
+  if (p->usc) // here
+	kfree((void*)p->usc);
+  p->usc = 0;
   if(p->pagetable)
     proc_freepagetable(p->pagetable, p->sz);
   p->pagetable = 0;
@@ -195,6 +206,14 @@ proc_pagetable(struct proc *p)
     uvmfree(pagetable, 0);
     return 0;
   }
+  
+  // here
+  if (mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usc), PTE_R | PTE_U) < 0) {  
+	uvmunmap(pagetable, TRAMPOLINE, 1, 0);
+	uvmunmap(pagetable, TRAPFRAME, 1, 0);
+	uvmfree(pagetable, 0);
+	return 0;
+  }
 
   return pagetable;
 }
@@ -206,6 +225,7 @@ proc_freepagetable(pagetable_t pagetable, uint64 sz)
 {
   uvmunmap(pagetable, TRAMPOLINE, 1, 0);
   uvmunmap(pagetable, TRAPFRAME, 1, 0);
+  uvmunmap(pagetable, USYSCALL, 1, 0); // here
   uvmfree(pagetable, sz);
 }
 
diff --git a/kernel/proc.h b/kernel/proc.h
index f6ca8b7..d25a729 100644
--- a/kernel/proc.h
+++ b/kernel/proc.h
@@ -82,6 +82,8 @@ struct trapframe {
 
 enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
 
+struct usyscall;
+
 // Per-process state
 struct proc {
   struct spinlock lock;
@@ -105,4 +107,7 @@ struct proc {
   struct file *ofile[NOFILE];  // Open files
   struct inode *cwd;           // Current directory
   char name[16];               // Process name (debugging)
+  
+  // here
+  struct usyscall *usc;
 };

Print a page table

思路

仿照 freewalk 函数的写法，递归查找所有有效的页表项，并根据题干要求打印相关信息。涉及的内容较少，如果认真把上面提到的几个关键函数理清楚，并且理解了多级页表的机制，写起来还是比较轻松的，流程如下：

遍历当前页表中的所有页表项，如果页表项有效（flags 的有效位为 1），则将该页表项转换为物理地址向下递归搜索。需要注意的是在递归查找到第 3 级页表时，就不能继续向下递归了，此时得到的 pa 就是进行虚实地址转换后的物理地址。

代码

diff --git a/kernel/defs.h b/kernel/defs.h
index 3564db4..d169300 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -170,6 +170,7 @@ 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); // here
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/exec.c b/kernel/exec.c
index d62d29d..89f3d74 100644
--- a/kernel/exec.c
+++ b/kernel/exec.c
@@ -115,6 +115,11 @@ exec(char *path, char **argv)
   p->trapframe->epc = elf.entry;  // initial program counter = main
   p->trapframe->sp = sp; // initial stack pointer
   proc_freepagetable(oldpagetable, oldsz);
+  
+  // here
+  if(p->pid == 1) {
+	vmprint(p->pagetable);
+  }
 
   return argc; // this ends up in a0, the first argument to main(argc, argv)
 
diff --git a/kernel/vm.c b/kernel/vm.c
index d5a12a0..23eeec9 100644
--- a/kernel/vm.c
+++ b/kernel/vm.c
@@ -432,3 +432,25 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
     return -1;
   }
 }
+
+// here
+void vmprint_recur(pagetable_t pagetable, int depth) {
+	for (int i = 0; i < 512; ++i) {
+		pte_t pte = pagetable[i];
+		if (pte & PTE_V) { // pte is valid
+			for (int j = 0; j < depth; ++j) {
+				printf(" ..");
+			}
+			uint64 child = PTE2PA(pte);
+			printf("%d: pte %p pa %p\n", i, pte, child);
+			if (depth < 3) {
+				vmprint_recur((pagetable_t)child, depth + 1);	
+			}
+		}
+	}
+}
+
+void vmprint(pagetable_t pagetable) {
+	printf("page table %p\n", pagetable);
+	vmprint_recur(pagetable, 1);
+}

Detecting which pages have been accessed

思路

题目要求实现一个系统调用 sys_pgaccess()，获取指定虚拟页面的最近被访问信息。

算是一个大杂烩的题，把 Lab System calls 的内容和 pagetable 结合起来，不要被 hard 难度标签吓到了，只要前面的 Lab 全都认真完成，再运用一些位运算的技巧，本题其实并不 “hard”。

所有的系统调用需要的声明已经实现添加好了，我们只需要关注 sys_pgaccess() 的实现即可，基本流程如下：

1. 和 Lab System calls 一样，使用 argint() 和 argaddr() 获取用户空间传递的参数：base、len、mask。
2. 函数体内定义一个 kmask，作为 mask 的缓冲区。
3. 从地址 base 开始遍历连续的 len 的页面，获取该页面的页表项 pte，根据 pte 的访问位对 kmask 进行置位，注意不要忘了每次遍历后将 pte 的访问位置 0。
4. 遍历完成后，使用 copyout() 将 kmask 的数据存入用户空间 mask 处。

有一个值得注意的问题，根据提示：

It’s okay to set an upper limit on the number of pages that can be scanned.

可以设定一个最大扫描范围，这主要根据 kmask 的数据类型而定，这里我选择使用 long 类型，那么最大扫描范围自然就是 64（long 类型为 8 字节大小，64 bit）。

同时，在对 kmask 操作时，可以运用一些位运算的技巧：

首先可以将 kmask 置为 0（二进制位全为 0），如果页面 i 的访问位为 1，则使用 kmask |= (1 << i)，将 kmask 第 i 位置为 1 而不影响其它位（0 | 0 = 0; 1 | 0 = 1）。

要清除 pte 的访问位，可使用 *pte &= ~PTE_A，其中 PTE_A = 1L << 6，即访问位为 1，其它位都为 0，取反后，访问位为 0，其它位都为 1，与其进行按位与运算可将访问位置为 0，而不影响其它位（0 & 1 = 0; 1 & 1 = 1）。

问题

问题 1：

原因： 比较坑的一个问题，原因是 kernel/defs.h 中没有 walk 函数声明，需要手动添加。

代码

diff --git a/kernel/defs.h b/kernel/defs.h
index d169300..53f1f88 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -171,6 +171,7 @@ 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); // here
+pte_t 			*walk(pagetable_t, uint64, int);
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/riscv.h b/kernel/riscv.h
index 1691faf..6b130fe 100644
--- a/kernel/riscv.h
+++ b/kernel/riscv.h
@@ -343,6 +343,7 @@ sfence_vma()
 #define PTE_W (1L << 2)
 #define PTE_X (1L << 3)
 #define PTE_U (1L << 4) // 1 -> user can access
+#define PTE_A (1L << 6) // access bit
 
 // shift a physical address to the right place for a PTE.
 #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
diff --git a/kernel/sysproc.c b/kernel/sysproc.c
index 3bd0007..359847c 100644
--- a/kernel/sysproc.c
+++ b/kernel/sysproc.c
@@ -81,6 +81,36 @@ int
 sys_pgaccess(void)
 {
   // lab pgtbl: your code here.
+  struct proc *p = myproc();
+  void *base, *mask;
+  long kmask; // buffer
+  int len;
+  pte_t *pte;
+  
+  if (argaddr(0, (uint64 *)&base) < 0) {
+	return -1;
+  }
+  if (argint(1, &len) < 0 || len > 64) { // page limited to 64
+	return -1;
+  }
+  if (argaddr(2, (uint64 *)&mask) < 0) {
+	return -1;
+  }
+  
+  kmask = 0L; // initialize bitmask to zero
+  for (int i = 0; i < len; ++i) {
+	uint64 va = (uint64)(base + i * PGSIZE);
+	pte = walk(p->pagetable, va, 0);
+	if (*pte & PTE_A) { // pte was accessed recently
+	  kmask |= (1 << i);
+	}
+	*pte &= ~PTE_A; // clear access bit
+  }
+  
+  if (copyout(p->pagetable, (uint64)mask, (char *)&kmask, 8) < 0) {
+	return -1;
+  }
+
   return 0;
 }
 #endif