Speed up system calls
思路
题目要求在每个进程初始化时为它的页表插入一个页表项，内核通过这样预先缓存页表项的操作，来加速特定系统调用的执行速度。
由于前不久刚过完一遍《OSTEP》，因此我认为自己对页表机制还算比较熟悉，应对本 Lab 理应比较轻松，但在真正上手的时候，还是觉得有些无所适从，无奈老老实实地把 xv6 手册的第 3 章对照着代码仔细研读了一番，从中提炼出了几个关键的函数：
kernel/kalloc.c:kalloc
void *kalloc(void);
遍历空闲链表，寻找一个可分配的物理页面。若找到，返回该页面的首（物理）地址；否则，返回 0 （空指针）。
kernel/kalloc.c:kfree
void kfree(void *pa);
释放已分配的首地址为 pa 的物理页面，并更新空闲链表。
kernel/proc.c:allocproc
static struct proc *allocproc(void);
遍历进程数组 proc，寻找未被使用的 struct proc。若找到，则初始化其状态，为创建一个新的页表，并返回指向它的指针；否则，返回 0（空指针）。
kernel/proc.c:freeproc
static void freeproc(struct proc *p);
释放与进程 p 相关的数据的内存空间，并清空 p 的 struct proc 的所有信息。
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 代表页面的编号）的映射。
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 指向的内存空间。
分析完几个关键函数之后，思路就比较清晰了：
- 为
struct proc结构体添加struct usyscall *usc段。 - 在
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;
- 在
freeproc()中释放usc的物理内存。
if (p->usc)
kfree((void*)p->usc);
p->usc = 0;
- 在
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;
}
- 最后，非常容易忽视的，在
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() 的实现即可，基本流程如下：
- 和 Lab System calls 一样，使用
argint()和argaddr()获取用户空间传递的参数：base、len、mask。 - 函数体内定义一个
kmask，作为mask的缓冲区。 - 从地址
base开始遍历连续的len的页面，获取该页面的页表项pte，根据pte的访问位对kmask进行置位，注意不要忘了每次遍历后将pte的访问位置 0。 - 遍历完成后，使用
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 = 0）。
要清除 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
![【PYG】Planetoid中边存储的格式，为什么打印前十条边用edge_index[:, :10]](https://img-blog.csdnimg.cn/direct/1909b053a7d7489eb61ccb86baec98e0.png)
