Lab mmap

本文记录了 Lab: mmap 的实验过程

Lab: mmap (hard)

前言

该实验是要为 xv6 实现 mmap 和 munmap 系统调用。mmap 的作用是将文件描述符 fd 对应的文件映射到进程的虚拟内存中，避免频繁地对文件进行读写；而 munmap 是释放 mmap 时分配的空间，如果有必要的话，将这块映射区域写回文件系统。这两个系统调用的具体文档可以通过 man 2 mmap 查看。

git fetch
git checkout mmap
make clean

---

定义

• 将 _mmaptest 添加到 UPROGS 中
• 首先定义 mmap 和 munmap 这两个系统调用。定义过程参考 Lab: System Call
• 为了能编译通过，在 kernel/sysfile.c 中定义 sys_mmap 和 sys_munmap 函数，函数体直接返回一个值即可

此时运行

make qemu
mmaptest

在第一次调用 mmap 的时候会失败，因为我们还没有实现它

---

mmap

实现 mmap 系统调用。在改实验中，只需要映射文件就可，它的作用是将文件描述符 fd 指向的文件映射到进程的虚拟内存中。映射的起始地址为 addr（由于实验指导书指明 addr 为 0，因此要求内核为它自动分配一个地址），length 表示映射的长度，prot 表示文件的权限（例如 PROT_READ，PROT_WRITE），flags 表示映射的类型（例如 MAP_SHARED 或者 MAP_PRIVATE），偏移 offset（该实验中可以假定偏移为 0）

实现过程

• 在 mmap 中进行 laze allocation，以触发缺页中断，然后再实际分配物理页。（参考 Lab：Lazy）
• VMA：这是管理某个映射区域的数据结构。给进程添加一个大小为 16 的 VMA 结构体数组

Q1：如何找到一个空闲的 VMA 并分配给进程？

• 可以在 VMA 中添加一个标志位 mapped，1 表示这个 VMA 已经被使用，0 表示未被使用
• 然后遍历 VMA 数组，分配 mapped 为 0 的那个 VMA 即可
• 设置这个空闲的 VMA 的对应字段，设置 mapped 为 1，表示我们已经用了这个 VMA
• 不要忘记使用 filedup 函数增加对该文件的引用

此时运行

make qemu
mmaptest

当程序访问 mmap-ed 内存时，会发生 page fault，然后杀死进程，因为我们还没编写处理 page fault 的代码。

Q2：如何响应 page fault？

• 我们知道 page fault 对应的 r_scause() 为 13 或者 15，因此我们在 usertrap 函数中对它进行处理
• 首先检查 va 是否合法，然后检查 va 在哪个 VMA 中？
• 分配物理地址，设置这一页对应的访问权限（根据 prot 字段），在页表中对 va 和 pa 建立映射关系
• 从相关的文件中读取 4096 个字节的数据到刚刚分配的那一页中（readi 函数，调用前必须对 inode 上锁）

此时运行

make qemu
mmaptest

前几个测试会通过，直到运行到 munmap 处

---

munmap

实现 munmap 系统调用。它的功能是移除指定地址范围的 mmap。如果进程修改了这块内存并且这块内存的 flags 为 MAP_SHARED，那么对这块内存的修改应该写回到文件系统中。

实现过程

• 首先找到 va 在哪一个 VMA 中
• 判断是否需要将内存写回到文件中，可以参考 filewrite 函数
• 使用 uvmunmap 函数移除 length / PGSIZE 页
• 如果这段 VMA 区域全部被释放了，那么回收这个 VMA（设置 mapped 为 0），减少该文件的引用（fileclose 函数）

---

fork/exit

1. 在 fork 函数中，复制父进程的 VMA 数组，不要忘记增加文件的引用计数。（使用 COW 很酷，但是估计工作量太大了我就没实现了）
2. 在 exit 函数中将进程使用的 VMA 释放，就像调用了 munmap 一样

---

测试

make qemu
mmaptest
usertests

make grade

Diff

diff --git a/Makefile b/Makefile
index d8509b1..cb5e39b 100644
--- a/Makefile
+++ b/Makefile
@@ -175,6 +175,7 @@ UPROGS=\
 	$U/_grind\
 	$U/_wc\
 	$U/_zombie\
+        $U/_mmaptest\
 
 
 
diff --git a/kernel/defs.h b/kernel/defs.h
index 41098f4..a8de111 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -171,6 +171,8 @@ 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);
+int             mmapalloc(struct proc*, uint64);
+int             mmapdealloc(struct proc*, uint64, int);
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/proc.c b/kernel/proc.c
index ba1a9e3..176e629 100644
--- a/kernel/proc.c
+++ b/kernel/proc.c
@@ -5,6 +5,7 @@
 #include "spinlock.h"
 #include "proc.h"
 #include "defs.h"
+#include "fcntl.h"
 
 struct cpu cpus[NCPU];
 
@@ -298,6 +299,20 @@ fork(void)
 
   safestrcpy(np->name, p->name, sizeof(p->name));
 
+  // the child has the same mapped regions as the parent
+  // Don't forget to increment the reference count for a VMA's struct file
+  for(int i = 0; i < 16; i++){
+    if(p->vmas[i].mapped == 1){
+      np->vmas[i].addr = p->vmas[i].addr;
+      np->vmas[i].end = p->vmas[i].end;
+      np->vmas[i].length = p->vmas[i].length;
+      np->vmas[i].prot = p->vmas[i].prot;
+      np->vmas[i].flags = p->vmas[i].flags;
+      np->vmas[i].offset = p->vmas[i].offset;
+      np->vmas[i].f = filedup(p->vmas[i].f);
+      np->vmas[i].mapped = 1;
+    }
+  }
   pid = np->pid;
 
   np->state = RUNNABLE;
@@ -353,6 +368,12 @@ exit(int status)
     }
   }
 
+  // unmap the process's mapped regions
+  for(int i = 0; i < 16; i++){
+    if(p->vmas[i].mapped == 1){
+      mmapdealloc(myproc(), p->vmas[i].addr, p->vmas[i].end - p->vmas[i].addr);
+    }
+  }
   begin_op();
   iput(p->cwd);
   end_op();
diff --git a/kernel/proc.h b/kernel/proc.h
index 9c16ea7..2997ae9 100644
--- a/kernel/proc.h
+++ b/kernel/proc.h
@@ -80,6 +80,20 @@ struct trapframe {
   /* 280 */ uint64 t6;
 };
 
+// Define a structure corresponding to the VMA (virtual memory area) described in Lecture 15,
+// recording the address, length, permissions, file, etc.
+// for a virtual memory range created by mmap.
+struct vma {
+  uint64 addr;
+  uint64 end;
+  int length;
+  int prot;
+  int flags;
+  int offset;
+  struct file *f;
+  int mapped;
+};
+
 enum procstate { UNUSED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
 
 // Per-process state
@@ -103,4 +117,5 @@ struct proc {
   struct file *ofile[NOFILE];  // Open files
   struct inode *cwd;           // Current directory
   char name[16];               // Process name (debugging)
+  struct vma vmas[16];         // declare a fixed-size array of VMAs and allocate from that array as needed
 };
diff --git a/kernel/syscall.c b/kernel/syscall.c
index c1b3670..7320633 100644
--- a/kernel/syscall.c
+++ b/kernel/syscall.c
@@ -104,6 +104,8 @@ extern uint64 sys_unlink(void);
 extern uint64 sys_wait(void);
 extern uint64 sys_write(void);
 extern uint64 sys_uptime(void);
+extern uint64 sys_mmap(void);
+extern uint64 sys_munmap(void);
 
 static uint64 (*syscalls[])(void) = {
 [SYS_fork]    sys_fork,
@@ -127,6 +129,8 @@ static uint64 (*syscalls[])(void) = {
 [SYS_link]    sys_link,
 [SYS_mkdir]   sys_mkdir,
 [SYS_close]   sys_close,
+[SYS_mmap]    sys_mmap,
+[SYS_munmap]  sys_munmap,
 };
 
 void
diff --git a/kernel/syscall.h b/kernel/syscall.h
index bc5f356..e7b18d6 100644
--- a/kernel/syscall.h
+++ b/kernel/syscall.h
@@ -20,3 +20,5 @@
 #define SYS_link   19
 #define SYS_mkdir  20
 #define SYS_close  21
+#define SYS_mmap   22
+#define SYS_munmap 23
diff --git a/kernel/sysfile.c b/kernel/sysfile.c
index 5dc453b..22d194b 100644
--- a/kernel/sysfile.c
+++ b/kernel/sysfile.c
@@ -484,3 +484,66 @@ sys_pipe(void)
   }
   return 0;
 }
+
+// map files into process address spaces,
+// and as part of user-level page fault schemes
+uint64
+sys_mmap()
+{
+  uint64 addr;
+  int length, prot, flags, fd, offset;
+  if(argaddr(0, &addr) || argint(1, &length) < 0 || argint(2, &prot) < 0 ||
+      argint(3, &flags) < 0 || argint(4, &fd) < 0 || argint(5, &offset) < 0)
+    return 0xffffffffffffffff;
+
+  // addr will always be zero, assume offset is zero
+  if(addr != 0 || offset != 0)
+    return -1;
+
+  struct proc *p = myproc();
+  struct file *f = p->ofile[fd];
+
+  // if file is read-only, but mmap allow write or shared, then return error
+  if(!f->writable && (prot & PROT_WRITE) && (flags & MAP_SHARED))
+    return 0xffffffffffffffff;
+
+  // find an unused region in the process's address space in which to map the file
+  int i = 0;
+  for (; i < 16; i++){
+    if(p->vmas[i].mapped == 0)
+      break;
+  }
+  if(i == 16) // no free VMA to use
+    return 0xffffffffffffffff;
+
+  filedup(f); // increment referent count for file
+  p->vmas[i].addr = (uint64)p->sz;
+  p->vmas[i].end = PGROUNDUP(p->sz + length);
+  p->vmas[i].length = length;
+  p->vmas[i].prot = prot;
+  p->vmas[i].flags = flags;
+  p->vmas[i].offset = offset;
+  p->vmas[i].f = f;
+  p->vmas[i].mapped = 1;
+
+  // laze allcation by page fault
+  p->sz += length;
+
+  return p->vmas[i].addr;
+}
+
+// remove mmap mappings in the indicated address range
+uint64
+sys_munmap()
+{
+  uint64 addr;
+  int length;
+  if(argaddr(0, &addr) < 0 || argint(1, &length) < 0)
+    return -1;
+
+  if(mmapdealloc(myproc(), addr, length) < 0){
+    return -1;
+  }
+
+  return 0;
+}
diff --git a/kernel/trap.c b/kernel/trap.c
index a63249e..b6f56e5 100644
--- a/kernel/trap.c
+++ b/kernel/trap.c
@@ -67,6 +67,11 @@ usertrap(void)
     syscall();
   } else if((which_dev = devintr()) != 0){
     // ok
+  } else if(r_scause() == 0xd || r_scause() == 0xf){
+    uint64 va = r_stval();
+    if(mmapalloc(p, va) < 0){
+      p->killed = 1;
+    }
   } else {
     printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
     printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
diff --git a/kernel/vm.c b/kernel/vm.c
index b47f111..6d001d8 100644
--- a/kernel/vm.c
+++ b/kernel/vm.c
@@ -5,6 +5,11 @@
 #include "riscv.h"
 #include "defs.h"
 #include "fs.h"
+#include "spinlock.h"
+#include "proc.h"
+#include "sleeplock.h"
+#include "file.h"
+#include "fcntl.h"
 
 /*
  * the kernel's page table.
@@ -146,7 +151,7 @@ mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
     if((pte = walk(pagetable, a, 1)) == 0)
       return -1;
     if(*pte & PTE_V)
-      panic("remap");
+      ;
     *pte = PA2PTE(pa) | perm | PTE_V;
     if(a == last)
       break;
@@ -170,9 +175,9 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
 
   for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
     if((pte = walk(pagetable, a, 0)) == 0)
-      panic("uvmunmap: walk");
+      continue;
     if((*pte & PTE_V) == 0)
-      panic("uvmunmap: not mapped");
+      continue;
     if(PTE_FLAGS(*pte) == PTE_V)
       panic("uvmunmap: not a leaf");
     if(do_free){
@@ -304,9 +309,9 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
 
   for(i = 0; i < sz; i += PGSIZE){
     if((pte = walk(old, i, 0)) == 0)
-      panic("uvmcopy: pte should exist");
+      continue;
     if((*pte & PTE_V) == 0)
-      panic("uvmcopy: page not present");
+      continue;
     pa = PTE2PA(*pte);
     flags = PTE_FLAGS(*pte);
     if((mem = kalloc()) == 0)
@@ -429,3 +434,97 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
     return -1;
   }
 }
+
+// allocate memory for mmap
+int
+mmapalloc(struct proc *p, uint64 va)
+{
+  // check va is vaild
+  va = PGROUNDDOWN(va);
+  if(va >= p->sz || va < p->trapframe->sp)
+    return -1;
+
+  int i = 0;
+  for(; i < 16; i++){
+    if(p->vmas[i].mapped && va >= p->vmas[i].addr && va < p->vmas[i].end)
+      break;
+  }
+  if(i == 16)
+    return -1;
+
+  char *pa = kalloc();
+  if(pa == 0) // no free physical memory
+    return -1;
+  memset(pa, 0, PGSIZE);
+
+  // map it into the user address space
+  // set the permissions correctly on the page
+  int prot = p->vmas[i].prot;
+  uint64 flags = PTE_U;
+  if(prot & PROT_READ)
+    flags |= PTE_R;
+  if(prot & PROT_WRITE)
+    flags |= PTE_W;
+  if(prot & PROT_EXEC)
+    flags |= PTE_X;
+  if(mappages(p->pagetable, va, PGSIZE, (uint64)pa, flags) != 0){
+    kfree(pa);
+    return -1;
+  }
+
+  // read 4096 bytes of the relevant file into that page
+  struct inode *ip = p->vmas[i].f->ip;
+  begin_op();
+  ilock(ip);
+  if(readi(ip, 1, va, va - p->vmas[i].addr, PGSIZE) < 0){
+    iunlock(ip);
+    end_op();
+    return -1;
+  }
+  iunlock(ip);
+  end_op();
+  return 0;
+}
+
+int
+mmapdealloc(struct proc *p, uint64 va, int length)
+{
+  // find the VMA for the address range
+  int i = 0;
+  for(; i < 16; i++){
+    if(p->vmas[i].mapped == 1 && va >= p->vmas[i].addr && va + length <= p->vmas[i].end)
+      break;
+  }
+  if(i == 16)
+    return -1;
+
+  // the file is mapped MAP_SHARED, write the page back to the file
+  if((p->vmas[i].flags & MAP_SHARED) && p->vmas[i].f->writable){
+    struct inode *ip = p->vmas[i].f->ip;
+    begin_op();
+    ilock(ip);
+    if(writei(ip, 1, va, 0, length) < 0){
+      iunlock(ip);
+      end_op();
+      return -1;
+    }
+    iunlock(ip);
+    end_op();
+  }
+
+  // unmap the specified pages
+  uvmunmap(p->pagetable, va, length / PGSIZE, 1);
+  
+  // munmap removes all pages of a previous mmap, it should 
+  // decrement the reference count of the corresponding struct file
+  if(length == p->vmas[i].end - p->vmas[i].addr){
+    fileclose(p->vmas[i].f);
+    p->vmas[i].mapped = 0;
+    p->sz -= length;
+    return 0;
+  }
+
+  p->vmas[i].addr += length;
+
+  return 0;
+}
diff --git a/user/user.h b/user/user.h
index b71ecda..5648874 100644
--- a/user/user.h
+++ b/user/user.h
@@ -23,6 +23,8 @@ int getpid(void);
 char* sbrk(int);
 int sleep(int);
 int uptime(void);
+void* mmap(void*, int, int, int, int, int);
+int munmap(void*, uint);
 
 // ulib.c
 int stat(const char*, struct stat*);
diff --git a/user/usys.pl b/user/usys.pl
index 01e426e..d23b9cc 100755
--- a/user/usys.pl
+++ b/user/usys.pl
@@ -36,3 +36,5 @@ entry("getpid");
 entry("sbrk");
 entry("sleep");
 entry("uptime");
+entry("mmap");
+entry("munmap");