最后一个，也是最有挑战性的一项 coding 任务，是所有前置 lab 的知识综合。
Preparation
切换到对应分支
1$ git fetch
2$ git checkout mmap
3$ make clean
我们需要实现的 mmap() 与 munmap() 这两个是系统调用，那就要修改若干文件，这在之前的 lab 中已经操作过很多次了，跳过不聊。
从 mmap 开始
void* mmap(void* addr, size_t length, int prot, int flags, int fd, off_t offset);
其作用是将某一文件 fd 从偏移量 offset 开始 length 个字节的长度映射到内存中。操作系统不仅要为其分配物理内存空间 pa，还需要在进程的虚拟地址空间为其分配一块虚拟内存 va，这样才能通过页表机制进行内存的访问。其中 addr 就是用户指定的虚拟地址。如果 addr 为 0，则由操作系统进行目标虚拟地址的挑选。
prot 指定了映射内存区域 pa 的访问权限，flags 指定了映射内存是否应当在 unmap 时将所有修改写回文件。这两者对应的标志位都定义在 kernel/fcntl.h 中。
本 lab 中，入参
addr可以假设恒为 0。
如何映射？
假设，对于文件 f，我们选择从 offset 处开始 2 个 PGSIZE 大小的内容进行映射，操作系统会为我们分配 2 个 PGSIZE 大小的虚拟空间，起始地址为 va，长度 length = 2*PGSIZE，并记录下对应文件的偏移量 offset。操作系统还会在合适的时间分配内存，但要注意的是，虽然虚拟地址空间是连续的，但是分配的物理内存并不一定连续，这两页可能会分别映射到两个离散的地址 pa1 和 pa2。其中 pa1 中的内容为 f 中 offset 开始的一个 PGSIZE 的数据，而 pa2 中的内容为 f 中 offset+PGSIZE 开始的一个 PGSIZE 的数据。
| 文件 | 虚拟地址 | 物理地址 |
|---|---|---|
| offset | va | pa1 |
| offset+PGSIZE | va+PGSIZE | pa2 |
实现 VMA
根据手册，第一次调用 mmap() 时，我们不必为其分配物理内存，而是仅仅在虚拟空间划出一块区域并返回相应的 va，等到通过 va 访问内存时，发现页表中没有相应 pte，这个时候再去分配物理内存。
这就是和 lab COW 一样利用了 page fault，防止映射大文件时一次 alloc 所有空间导致物理内存不够用的情况。
那么第一步我们就要解决「在虚拟空间划出一块区域」这个问题了。然而，内核中并没有虚拟地址空间的分配器，但是对我们而言，虚拟地址之所以「虚拟」，是因为我们只需要记住一定的数据，最后 usertrap() 里根据这些数据，在页表中建立页表项并且映射到物理地址即可。所以，进程结构体中可以增加这样一个字段，用于分配并追踪某个虚拟地址的使用情况。
这个字段除了标明某一对映射的虚拟地址、长度，还要有偏移量以及标志位等信息，以及对应的文件信息，那么就有：
1struct vma {
2 int valid; // 该字段是否有效
3
4 uint64 va; // 虚拟起始地址
5 uint64 length; // 长度，可以不是 PGSIZE 的整数倍
6 int prot; // 权限标志位
7 int flags; // 脏数据处理标志位
8 int fd; // 文件描述符
9 struct file* f; // 文件
10 int offset; // 相对于文件的偏移量
11};
如果 valid 为 1，那么就表明从 va 开始 length 个 bytes 的这段虚拟空间已经被使用了，下次要分配时也应当避开这段空间。一个进程很可能调用多次 mmap() 进行多个文件的映射，那么就不能只存一条记录，而是实现为数组的形式。手册中提示我们 16 是个合适的大小。
现在还有一个问题，该怎样为 va 赋值？回想之前写 lab Page Table 的时候，我们实现了一个功能，是通过固定的虚拟地址加快 getpid()。当时分配的虚拟地址是位于虚拟空间最末端，TRAMPOLINE 和 TRAPFRAME 之前，这是因为虚拟空间非常大，完全可以把后面那点用不到的空间利用起来。
根据这一经验，我们完全可以在进程中建立一个字段 max_VMA，它会在新建进程时初始化为 MAXVA-2*PGSIZE，每次分配时往低地址增长：当调用 mmap() 时，max_VMA 会减去待映射的长度 length，然后找到一个 valid=0 的 vma，进行 vma.va = max_VMA 的赋值。
1struct proc {
2 ...
3#define NVMA 16
4 struct vma vma[NVMA]; // mmap record
5 uint64 max_VMA; // trampoline and trapframe
6};
到此，虚拟内存的分配记录就完成了。
sys_mmap
读取参数，找到可用 vma 并设置数据即可。
1uint64
2sys_mmap(void)
3{
4 uint64 addr;
5 int length;
6 int prot;
7 int flags;
8 int fd;
9 struct file *f;
10 int offset;
11 if (argaddr(0, &addr) < 0 || argint(1, &length) < 0 || argint(2, &prot) < 0 ||
12 argint(3, &flags) < 0 || argfd(4, &fd, &f) < 0 || argint(5, &offset) < 0) {
13 return -1;
14 }
15
16 // 权限不匹配
17 if (!f->readable && (prot & PROT_READ)) {
18 return -1;
19 }
20 if (!f->writable && (prot & PROT_WRITE) && (flags & MAP_PRIVATE) == 0) { // 如果文件不可写，但是允许对 MAP_PRIVATE 模式映射的内存进行写操作，反之不行
21 return -1;
22 }
23
24 uint64 va = -1;
25 struct proc *p = myproc();
26 struct vma *vma;
27 for (int i = 0; i < NVMA; i++) {
28 if (!p->vma[i].valid) {
29 vma = &p->vma[i];
30 break;
31 }
32 }
33
34 vma->valid = 1;
35
36 if (addr == 0) {
37 p->max_VMA -= PGROUNDUP(length);
38 vma->va = va = p->max_VMA;
39 }
40 // else { // 现有测试不会跳到这一个分支
41 // vma->va = va = addr;
42 // }
43
44 vma->length = length;
45 vma->prot = prot;
46 vma->flags = flags;
47 vma->fd = fd;
48 vma->f = filedup(f); // 映射会增加文件引用计数
49 vma->offset = offset;
50 return va;
51}
page fault
当出现读/写的 page fault 时，就需要检查是否是在 mmap 内存上引起的。如果是，那就进行物理内存的分配，页表项的建立，以及文件数据的拷贝。注意需要逐页进行物理内存分配。
1void
2usertrap(void)
3{
4 ...
5 if (r_scause() == 13 || r_scause() == 15) {
6 // page fault occured by reading or writing a mmap virtual address
7 // that hasn't been allocated any physical page
8 if(p->killed)
9 exit(-1);
10
11 uint64 va = PGROUNDDOWN(r_stval());
12 if (va >= MAXVA)
13 exit(-1);
14
15 // 找到相应的字段
16 struct vma *vma = 0;
17 for (int i = 0; i < NVMA; i++) {
18 if (p->vma[i].valid && p->vma[i].va <= va && p->vma[i].va + PGROUNDUP(p->vma[i].length) > va) {
19 vma = &p->vma[i];
20 break;
21 }
22 }
23
24 // 如果没有找到，说明出错的虚拟地址没有进行映射，直接退出
25 if (!vma) {
26 exit(-1);
27 }
28
29 // 完善页表项的标志位
30 int flags = PTE_U;
31 if (vma->prot & PROT_READ) {
32 flags |= PTE_R;
33 }
34 if (vma->prot & PROT_WRITE) {
35 flags |= PTE_W;
36 }
37 if (vma->prot & PROT_EXEC) {
38 flags |= PTE_X;
39 }
40
41 uint64 pa;
42 uint64 following = vma->va - va + PGROUNDUP(vma->length);
43 // 逐页进行映射+拷贝操作
44 ilock(vma->f->ip);
45 for (uint64 off = 0; off < following; off += PGSIZE) {
46 // 如果当前地址已有映射，跳过
47 if ((pa = walkaddr(p->pagetable, va+off)) != 0) {
48 continue;
49 }
50 // 无可用内存，报错
51 if ((pa = (uint64)kalloc()) == 0) {
52 panic("no free memory");
53 }
54
55 // 清空数据，并建立映射，再进行拷贝
56 memset((void*)pa, 0, PGSIZE);
57 if (mappages(p->pagetable, va+off, PGSIZE, pa, flags) != 0) {
58 panic("cannot map");
59 }
60 if (readi(vma->f->ip, 0, pa, vma->offset+off, PGSIZE) == -1) {
61 panic("read file failed");
62 }
63 }
64 iunlock(vma->f->ip);
65 }
66 ...
67}
进行 munmap
int munmap(void *addr, int length)
munmap() 是对指定地址 addr 上长度为 length 的地址解除映射，即释放对应内存，删除页表项，并且还要修改相应的 vma 字段。
比如对之前表格中进行 munmap(va+PGSIZE, PGSIZE)，就会导致文件映射长度减少，那么 vma 的 length 字段就需要改为 PGSIZE（原来是 2*PGSIZE）。
而如果进行 munmap(va, PGSIZE)，那么还会额外导致 vma 的 va 字段改为 va+PGSIZE，并且偏移量 offset 也会增加 PGSIZE。
当然，调用 munmap(va, 2*PGSIZE) 会使 vma 的 length 和 offset 直接归零，此时意味着该文件的映射区域被完全解除，应降低该文件的引用计数，并且重置相应 vma 的所有字段（即归零）。
这很合理，毕竟解除了某一区域的映射，那么 vma 中文件的映射长度与偏移量肯定也会发生变化，不然就会出现不一致的问题。下次对已解除区域重新
mmap()时，经查 vma 数组发现已经有映射了，这显然与现实矛盾。
sys_munmap
1uint64
2sys_munmap(void)
3{
4 uint64 addr;
5 int length;
6
7 if (argaddr(0, &addr) < 0 || argint(1, &length) < 0) {
8 return -1;
9 }
10
11 struct proc *p = myproc();
12 struct vma *vma = 0;
13 for (int i = 0; i < NVMA; i++) {
14 if (p->vma[i].valid && p->vma[i].va <= addr && p->vma[i].va + PGROUNDUP(p->vma[i].length) > addr) {
15 vma = &p->vma[i];
16 break;
17 }
18 }
19
20 if (vma) {
21 vmaunmap(p, vma, addr, length);
22 return 0;
23 }
24
25 return -1;
26}
其中 vmaunmap() 就是做了所需要的全部工作——修改 page table、释放内存、修改 vma。
还不够
进程结束的时候，可能用户会忘记调用 munmap()，而进程只会释放 TRAMPOLINE 和 TRAPFRAME 以及低虚拟地址处的内存，对于文件映射内存区域，还需要我们额外加入代码进行处理。手册提示我们加在 exit() 函数里，我想是因为所有进程正常退出时都会调用该函数，并且我尝试在 freeproc() 中进行内存释放和数据写回，发现会在 bcache 上产生死锁的问题，但并未深究。
以及还要在 allocproc() 与 freeproc() 里增加对 vma[] 与 max_VMA 的初始化与重置。
哦对，调用 fork() 创建子进程时，只需要拷贝 vma[] 与 max_VMA 即可，而不需要拷贝物理内存，这也是利用了 page fault 的 lazy allocation 策略——用到再分配。
当然，还要增加 vma[] 中记录的文件的引用计数。
1static struct proc*
2allocproc(void)
3{
4 ...
5found:
6 ...
7 memset(&p->vma, 0, sizeof(p->vma));
8 p->max_VMA = PGROUNDUP(MAXVA) - PGSIZE*2;
9 ...
10}
11
12static void
13freeproc(struct proc *p)
14{
15 ...
16 memset(&p->vma, 0, sizeof(p->vma));
17 p->max_VMA = 0;
18}
19
20void
21exit(int status)
22{
23 ...
24 for (int i = 0; i < NVMA; i++) {
25 struct vma* vma = &p->vma[i];
26 if (vma->valid) {
27 vmaunmap(p, vma, vma->va, vma->length);
28 }
29 }
30 p->max_VMA = 0;
31 ...
32}
33
34int
35fork(void)
36{
37 ...
38 for (int i = 0; i < NVMA; i++) {
39 np->vma[i] = p->vma[i];
40 if (np->vma[i].f) {
41 np->vma[i].f->ref++;
42 }
43 np->max_VMA = p->max_VMA;
44 }
45 ...
46}
测试结果
1$ make grade
2...
3== Test running mmaptest ==
4$ make qemu-gdb
5(3.9s)
6== Test mmaptest: mmap f ==
7 mmaptest: mmap f: OK
8== Test mmaptest: mmap private ==
9 mmaptest: mmap private: OK
10== Test mmaptest: mmap read-only ==
11 mmaptest: mmap read-only: OK
12== Test mmaptest: mmap read/write ==
13 mmaptest: mmap read/write: OK
14== Test mmaptest: mmap dirty ==
15 mmaptest: mmap dirty: OK
16== Test mmaptest: not-mapped unmap ==
17 mmaptest: not-mapped unmap: OK
18== Test mmaptest: two files ==
19 mmaptest: two files: OK
20== Test mmaptest: fork_test ==
21 mmaptest: fork_test: OK
22== Test usertests ==
23$ make qemu-gdb
24usertests: OK (129.9s)
25 (Old xv6.out.usertests failure log removed)
26== Test time ==
27time: OK
28Score: 140/140
最后的工作
git commit -am ""将所有修改提交到本地;- 执行
make handin。由于 lab0 保存了 APIKey，故直接成功提交；
可选的挑战再说吧，没有什么想做的欲望。