MIT 6.S081 lab3:page tables | 页表

lab3 - page table

前置准备

主要内容为熟悉页表遍历以及地址转换。

根据课程官网的要求,需要阅读完教材的第三章\(Page \space tables\)。并且读懂下列源代码:kernel/memlayout.h, kernel/vm.c, kernel/kalloc.c, kernel/riscv.h, user/exec.c

相关笔记参考: lecture 3 Notes

syscall分支所有内容都上传仓库后,执行下列命令来切换分支

1
2
3
git fetch
git checkout pgtbl
make clean

此外,新建一个pgtbl_dev分支来进行实际实验。

1
git checkout -b pgtbl_dev

pgtbl_dev中每通过一个作业的测试,提交(git commit)你的代码,并将所做的修改合并(git merge)到util中,然后提交(git push)到github。

1
2
3
4
5
git add .
git commit -m "xxxxxxxx"
git checkout pgtbl
git merge pgtbl_dev
git push github pgtbl:pgtbl

Speed up system calls (easy)

Statement

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

当一个进程被创建时,映射一块只读的页面在USYSCALL(一个虚拟地址,定义在kernel/memlayout.h)。在该内存页上我们需要存储一个叫struct usyscall的结构体(同样定义在kernel/memlayout.h),将其初始化为当前进程的PID

Hints

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

Analysis & Solution

先看看proc_pagetable(),可以看到就是用mappages()来将虚拟地址映射到物理地址。权限只需要设置PTE_R保证能读取,PTE_U保证用户内存能访问即可。

然后看一眼allocproc(), 就是调用kalloc()来个struct proc里面的各个部分分配空间。

最后在看看freeproc(), 对应把allocproc分配的东西,该free的free,该置0的置0。

所以我们要做的就很明显了:

  • 创建进程时,多存储一个struct usyscall
  • 创建进程页面时,将struct usyscall映射到USYSCALL
  • 销毁进程时,将struct usyscall释放,并且清空页表。

struct proc添加struct usyscall成员变量。

1
2
3
4
struct proc {
// 省略其他
struct usyscall* usyscall_info;
}

然后在proc_pagetable()中添加映射。

NOTE:uvmumap要把上两次map的页面也删除。

1
2
3
4
5
6
7
8
9
proc_pagetable() {
// 省略其他
if (mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall), PTE_R | PTR_U) < ) {
uvmunmap(pagetable, TRAMPOLINE, 1, 0);
uvmunmap(pagetable, TRAPFRAME, 1, 0);
uvmfree(pagetable, 0);
return 0;
}
}

然后在allocproc中分配内存,并且初始化。

NOTE:usyscall的分配要在p->pagetable分配前实现。不然页表会映射为空。

1
2
3
4
5
6
7
8
9
static struct proc* allocproc(void) {
// 省略其他
if ((p->usyscall_info = (struct usyscall*)kalloc()) == 0) {
freeproc(p);
release(&p->lock);
return 0;
}
p->usyspage->pid = p->pid;
}

最后在freeproc中释放内存。

1
2
3
4
5
static void freeproc(struct proc *) {
// 省略其他
if (p->usyscall_info) kfree((void*)p->usyscall_info);
p->usyscall_info = 0;
}

然后运行会喜提一个panic: freewalk leaf。翻一下freewalk这个函数,发现如果PTE_V没有设置,或者pte为空,就会有这个panic。

刚才只有mappages中修改到了页表。查看mappages函数的代码。由于并没有提示panic:mappages remap,说明PTE_V被正常设置。那问题只能是freewalk中的pte为空了。

一通检查,发现页表freeproc中的uvmfree只是把所有项都置为0,并不清空映射,所以映射出来就为空了。然后找到proc_freepagetable()这个函数(在kernel/proc.h中),删除USYSCALL的映射即可。

1
2
3
4
void proc_freepagetable(pagetable_t pagetable, uint64 sz) {
// 省略其他
uvmunmap(pagetable, USYSCALL, 1, 0);
}

Statement

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

我们需要定义一个vmprint函数。该函数应该有一个参数pagetable_t,作为要可视化的页表,然后按下面的格式打印这个页表的信息。添加一行if (p->pid == 1) vmprimt(p->pagetable)exec.c中,在返回argc之前输出第一个进程的页面信息。

当你启动xv6的时候,exec完成内核加载时你应该会看到下面的信息:

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 下可能存在的下级页表(学过算法的都应该看出来了这是一个递归)。我们用.. 来表示这个 PTE 的深度,最开始打印的数字是这个 PTE 在一个 4KB 内存页(共 512 个 PTE)的编号,接下来会打印 PTE 的具体数值。

Hints

  • 可以把vmprint实现在kernel/vm.c文件里面。
  • 记得使用kernel/riscv.h中的宏定义,包括但不限于PTE2PA等,来方便你转换PTE到物理地址。
  • 如果你无从下手,记得阅读freewalk函数。
  • kernel/defs.h中添加vmprint的原型,一遍在exec.c中正确调用。
  • print中使用%p来打印完整的64位地址信息。

Analysis & Solution

提示里面说了freewalk函数很重要,所以外面先读一下这个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Recursively free page-table pages.
// All leaf mappings must already have been removed.
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不为空并且PTE_V标志位为1,说明这项页面存在,并且映射了一个虚拟内存到物理内存。如果PTE_RPTE_RPRE_X都为0,说明这个页面为高级页表,读取下一级页表的地址,递归调用freewalk来遍历。

emmmm,然后就没什么好说的了,照着上面加点输入输出就可以。

vmprint:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// lab3 - exercise 2
// print a page table
void vmprint(pagetable_t pagetable, int depth) {
if (depth == 1)
printf("page table %p\n", pagetable);
for (int i = 0;i < 512;i ++) {
pte_t pte = pagetable[i];
// printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
if (pte & PTE_V) {
for (int j = 1;j <= depth;j ++)
printf("..%s", j == depth ? "" : " ");
printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
if ((pte & (PTE_R | PTE_W | PTE_X)) == 0) {
pagetable_t child = (pagetable_t)PTE2PA(pte);
vmprint((pagetable_t)child, depth + 1);
}
}
}
}

然后在kernel/defs.h中添加原型:

1
2
// vm.c
void vmprint(pagetable_t pagetable);

exec.creturn前插入代码:

1
2
3
if(p->pid==1) 
vmprint(p->pagetable);
return argc; // this ends up in a0, the first argument to main(argc, argv)

Detecting which pages have been accessed

Statement

一些垃圾回收器(一种自动内存管理的形式),可以从已经被访问的内存(写或读)中获得信息。在这部分实验,你将要给xv6内核添加一个新特性,通过检查RISC-V页表中的访问页来给用户空间传递这一信息。每当RISC-V硬件解决TLB未命中问题的时候,都会在PTE的标志位中标记对应位。(即不用考虑TLB和页表潜在不同步问题)。

你的目标是实现pgaccess(),一个用于报告当前进程哪些页面已被访问过的系统调用。它需要3个参数。首先,它需要第一个要检查的用户页面的起始虚拟地址。其次,它接受要检查的页面数。最后,它需要一个缓冲区的用户地址,以便将结果存储到位掩码(一种数据结构,每页使用一位,其中第一页对应的是最小有效位)中。如果在运行 pgtbltest 时通过了 pgaccess 测试用例,这部分实验将获得满分。

Hints

  • 首先在 kernel/sysproc.c 中实现 sys_pgaccess()
  • 需要使用 argaddr()argint() 解析参数。
  • 对于输出位掩码,在内核中存储一个临时缓冲区并在填入正确的位后将其拷贝给用户(通过 copyout())会更容易一些
  • kernel/vm.c 中的 walk() 对于找到正确的 PTE 非常有用。
  • 需要在 kernel/riscv.h 中定义访问位 PTE_A。请查阅 RISC-V 手册确定其值。
  • 在检查 PTE_A 是否被设置后,请务必将其清除。否则,将无法确定上次调用 pgaccess() 后是否访问过页面(即该位将永远被设置)。
  • vmprint() 可能会在调试页表时派上用场。

Analysis & Solution

大概意思可能和cache中的脏位差不多。检测到上一次调用sys_pgaccess()这段时间内,哪些页表项被访问过。可能完整的 UNIX 系统中会用这个信息来实现TLB和页表的同步。

需要注意的是,PTE_A位是由RISC-V硬件来维护的,在xv6中则是由qemu模拟器来负责维护,我们不用考虑什么时候将PTE_A置为1。

还是教材上这张图, RISC-V硬件页表的标记位:

可以看到 \(access\) 标志位是第 \(6\) 位(从 \(0\) 数起,从左到右)。所以在 kernel/riscv.h下面,添加一位PTE_A的定义。

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) // Lab pgtbl: Whether it has been visited

按照lab-2的内容看看系统调用需要添加的东西,真良心全添加好了。所以我们只用考虑怎么来实现。 在kernel/sysproc.c

1
2
3
4
5
6
#ifdef LAB_PGTBL
int sys_pgaccess(void) {
// lab pgtbl: your code here.
return 0;
}
#endif

我们用一个 \(64\) 位的整数来当作bitmask,一位表示一张页表,所以只能访问 \(64\) 张页表。即参数里的pgnums不能超过 \(64\)。然后就是从用户进程页表中的va开始,往下访问pgnums张页表项,如果当前PTE的access位为1,对应的bitmask位也置为1。由于sys_pgaccess()也会访问页表,这个操作也会将PTE_A置为1,所以在标记完bitmask之后,需要将PTE_A重置。

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
int sys_pgaccess(void) {
// virtual address
uint64 va;
if (argaddr(0, &va) < 0) {
return -1;
}

// the number of page table to check.
int pgnums;
if (argint(1, &pgnums) < 0) {
return -1;
}

// user virtual address
uint64 ua;
if (argaddr(2, &ua) < 0) {
return -1;
}

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

for (int i = 0; i < pgnums; i++) {
if (va >= MAXVA) return -1;
pte_t *pte = walk(p->pagetable, va, 0);
if ((*pte & PTE_V) && (*pte & PTE_A)) {
bitmask |= (1 << i);
*pte ^= PTE_A;
}
va += PGSIZE;
}

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

return 0;
}

然后报错说walk()没被定义,看一眼kernel/defs.h,发现没有walk函数原型,所以添加一个即可。

1
2
int copyinstr(pagetable_t, char*, uint64, uint64);
pte_t* walk(pagetable_t, uint64, int);

Submit lab

新建time.txt文件,输入一个整数表明完成所有实验的耗时。

运行make grade

这里usertests会评测所有xv6的函数,耗时较长,如果用虚拟机或低配置机器的同学可以修改grade-lab-pgtbl里面的timeout,不然还没评测完就给你来一个血红色的FAIL

运行make handin, 根据提示将API KEY填入,提交完成。


MIT 6.S081 lab3:page tables | 页表
https://acmicpc.top/2024/02/28/MIT-6.S081-lab03/
作者
江欣婷
发布于
2024年2月28日
许可协议