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
3git fetch
git checkout pgtbl
make clean
此外,新建一个pgtbl_dev
分支来进行实际实验。
1 |
|
在pgtbl_dev
中每通过一个作业的测试,提交(git
commit)你的代码,并将所做的修改合并(git merge)到util中,然后提交(git
push)到github。
1 |
|
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
4struct proc {
// 省略其他
struct usyscall* usyscall_info;
}
然后在proc_pagetable()
中添加映射。
NOTE:uvmumap
要把上两次map的页面也删除。
1 |
|
然后在allocproc
中分配内存,并且初始化。
NOTE:usyscall的分配要在p->pagetable
分配前实现。不然页表会映射为空。
1 |
|
最后在freeproc
中释放内存。 1
2
3
4
5static 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
4void proc_freepagetable(pagetable_t pagetable, uint64 sz) {
// 省略其他
uvmunmap(pagetable, USYSCALL, 1, 0);
}
Print a page table (easy)
Statement
在本部分中,我们需要将 RISC-V 的页表可视化,也就是实现一个页表内容的打印功能,作为后续调试的辅助工具。
我们需要定义一个
vmprint
函数。该函数应该有一个参数pagetable_t
,作为要可视化的页表,然后按下面的格式打印这个页表的信息。添加一行if (p->pid == 1) vmprimt(p->pagetable)
在exec.c
中,在返回argc
之前输出第一个进程的页面信息。
当你启动xv6
的时候,exec
完成内核加载时你应该会看到下面的信息:
1 |
|
第一行表示了 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 |
|
首先传入了一个页表,并且遍历里面的所有项。如果pte
不为空并且PTE_V
标志位为1,说明这项页面存在,并且映射了一个虚拟内存到物理内存。如果PTE_R
、PTE_R
、PRE_X
都为0,说明这个页面为高级页表,读取下一级页表的地址,递归调用freewalk
来遍历。
emmmm,然后就没什么好说的了,照着上面加点输入输出就可以。
vmprint
:
1 |
|
然后在kernel/defs.h
中添加原型:
1 |
|
在exec.c
的return
前插入代码:
1 |
|
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 |
|
然后报错说walk()
没被定义,看一眼kernel/defs.h
,发现没有walk
函数原型,所以添加一个即可。
1 |
|
Submit lab
新建time.txt
文件,输入一个整数表明完成所有实验的耗时。
运行make grade
。
这里usertests
会评测所有xv6的函数,耗时较长,如果用虚拟机或低配置机器的同学可以修改grade-lab-pgtbl
里面的timeout
,不然还没评测完就给你来一个血红色的FAIL
。
运行make handin
,
根据提示将API KEY
填入,提交完成。