XV6 Lab：mmap

Introduction

本文旨在记录作者完成课程任务的过程，可供参考。

实验仓库链接如下

xv6-2020

指导书链接如下

仓库内有多个 lab 分支，本文所提的 lab 对应的分支切换方法如下

git checkout mmap

本 lab 需要实现的系统调用如下

/* @brief 将文件内容映射到虚拟内存中
 *
 * @param addr: 永远是 0，由 kernel 决定映射地址
 * @param length: 要映射的字节数，可以和文件大小不同
 * @param prot: 只考虑 PROT_READ、PROT_WRITE，或者两者同时
 * @param flags: 只考虑 MAP_SHARED / MAP_PRIVATE，MAP_SHARED 不要求共享物理页
 * @param fd: 要映射的已打开文件的 fd
 * @param offset: 永远是 0，从文件开头开始映射
 * 
 * @return 成功：映射区域的虚拟地址；失败：(void *)0xffffffffffffffff
 */
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
/* @brief 解除映射，如果是 MAP_SHARED 并且内存发生更改，需要写回文件中。不能从中间挖洞
 *
 * @param addr: 永远是 0，由 kernel 决定映射地址
 * @param length: 要映射的字节数，可以和文件大小不同
 * 
 * @return 成功：0；失败：-1
 */
int munmap(void *addr, size_t length);

lab 并没有要求实现全部功能，只要完成测试中要求的即可

mit 指导书给出的提示如下

将 _mmaptest 添加到 Makefile 的 UPROGS 中
Be Lazy. 触发 page fault 之后在 usertrap() 中再把文件内容加载到某个页中
定义 Virtual Memory Area 结构，包括指向的文件、地址、长度、权限等，每一个 struct proc 内部都有一个固定大小的 VMA 数组，VMA 内的地址是虚拟地址
实现 mmap ：在用户地址空间中找到一片可用区域，并把 VMA 添加到 proc 的 VMA 数组中。除了保存文件指针以外，还要注意文件引用计数增加。
类似于 COW，添加代码让程序触发 page fault，来分配物理内存并用 readi() 将文件数据写入内存，设置权限
实现 munmap : 找到内存范围并且调用 uvmunmap()，减少文件引用
关于 MAP_SHARED 文件，不要求使用 Dirty bit
修改 exit 退出时释放页
修改 fork 让子进程有一样的 mmap，但不是共享的

添加系统调用接口

`user/user.h`

void *mmap(void *addr, unsigned int length, int prot, int flags, int fd, unsigned int offset);
int munmap(void *addr, unsigned int length);

`user/usys.pl`

entry("mmap");
entry("munmap");

`kernel/syscall.h`

添加系统调用号

#define SYS_mmap   22
#define SYS_munmap 23

`kernel/syscall.c`

添加声明，修改系统调用数组

extern uint64 sys_mmap(void);
extern uint64 sys_munmap(void);
static uint64 (*syscalls[])(void) = {
[SYS_fork]    sys_fork,
...
[SYS_mmap]    sys_mmap,
[SYS_munmap]  sys_munmap,
};

`kernel/sysproc.c`

添加实现

uint64
sys_mmap(void)
{
    // 待实现
}

uint64
sys_munmap(void)
{
    // 待实现
}

添加 VMA 结构体相关定义

mit 的说明中提到了

Keep track of what mmap has mapped for each process. 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. Since the xv6 kernel doesn’t have a memory allocator in the kernel, it’s OK to declare a fixed-size array of VMAs and allocate from that array as needed. A size of 16 should be sufficient.

所以我们需要定义 VMA 结构体，并且在 struct proc 里面添加 VMA 数组

#define NVMA 16

struct vma {
  // ...
};

struct proc {
  // 原来的字段
  ...
  struct vma vmas[NVMA];
};

先把函数接口里面涉及的有用的变量加到 struct vma 中，然后把说明中提到的 struct file 也添加进去，最后再加上 valid 来标记是否有效

struct vma {
  uint64 addr;
  uint64 length;
  int permissions;
  int flags;
  struct file *file;
  int valid;
};

关于位标志，仓库代码已经定义好了

// fcntl.h
#ifdef LAB_MMAP
#define PROT_NONE       0x0
#define PROT_READ       0x1
#define PROT_WRITE      0x2
#define PROT_EXEC       0x4

#define MAP_SHARED      0x01
#define MAP_PRIVATE     0x02
#endif

初始化 VMA 结构体

struct vma vmas[] 应该和其他结构体内部变量一样在 allocproc 里面被初始化，数据全部设置为 0 即可

found:
  p->pid = allocpid();
  memset(p->vmas,0,sizeof(p->vmas));

实现 `mmap` 接口

参数传递问题

由于 mmap 和文件有关，所以我还是决定将这两个函数放到了 sysfile.c 中实现，并参考了 sys_read() 等系统调用的参数传递方式

uint64
sys_mmap(void)
{
  struct file *f;
  uint64 addr;
  uint64 length;
  int prot;
  int flags;
  int fd;
  uint64 offset;

  argaddr(0, &addr);
  argaddr(1, &length);
  argint(2, &prot);
  argint(3, &flags);
  if(argfd(4, &fd, &f) < 0)
    return -1;
  argaddr(5, &offset);
  
  // check parameters
  if(addr!=0 || offset !=0)
    return -1;
  if(length==0)
    return -1;
  if (prot & ~(PROT_READ | PROT_WRITE))
    return -1;
  if (flags != MAP_SHARED && flags != MAP_PRIVATE)
    return -1;

  if (prot & PROT_READ) {
    if (!f->readable)
      return -1;
  }
  if ((prot & PROT_WRITE) && (flags == MAP_SHARED) && !f->writable) {
      return -1;
  }
  ...
  
}

注意权限检查，否则不会通过测试

在用户地址空间里面找块没用的区域

原来的用户地址空间布局大致如下

0
│
├── text
├── data + bss
├── fixed-size stack
├── expandable heap
│
│       ← 这里是很大的空闲区域
│
├──────────────────────────────
│ TRAPFRAME
├──────────────────────────────
│ TRAMPOLINE
└────────────────────────────── MAXVA

既然实验限制了 munmap 只能从 VMA 的开头、结尾或者整个区域解除映射，不能在中间打洞，那么直接从高地址往下分配即可。

TRAPFRAME
    │
    ├──────────────┐
    │ VMA #0       │
    ├──────────────┘
    │ VMA #1
    ├──────────────┘
    │
    │ free
    │
    ├────────────────
    │ heap

如果考虑 heap 和 VMA 冲突的可能，需要加入检查机制，本文暂不考虑这种情况。

为了简单，这里通过遍历 vma 数组找到最低已使用地址进行分配，不管中间的空洞。

uint64
sys_mmap(void)
{
  ...
  // allocate space
  struct proc *proc = myproc();
  uint64 end = TRAPFRAME;
  int chosen = -1;
  for (int i=0;i<NVMA;i++){
    // 取最小未使用地址作为末尾
    if (proc->vmas[i].valid){
      end = proc->vmas[i].addr < end? proc->vmas[i].addr : end;
    } else if(chosen == -1){
      chosen = i;  // 顺便取一个位置
      proc->vmas[i].length = length;
      proc->vmas[i].permissions = prot;
      proc->vmas[i].flags = flags;
      proc->vmas[chosen].file = filedup(f);  // 增加文件引用计数
    }
  }
  if (chosen == -1)
    return -1;
  // 检查合法性
  uint64 len = PGROUNDUP(length);
  if (end < len || end - len < proc->sz)
    return -1;
  // 地址需要取整
  proc->vmas[chosen].addr = end - len;
  proc->vmas[chosen].valid = 1;
  return proc->vmas[chosen].addr;
}

实现 demand paging

完成上面的更改之后，运行 mmaptest 结果如下

$ mmaptest
mmap_test starting
test mmap f
usertrap(): unexpected scause 0x000000000000000d pid=4
            sepc=0x0000000000000088 stval=0x0000003fffffc000
$

这就是 hints 所说的

Run mmaptest: the first mmap should succeed, but the first access to the mmap-ed memory will cause a page fault and kill mmaptest.

查询 scause 含义可以得到

`scause`	含义
12	Instruction page fault
13	Load page fault
15	Store/AMO page fault

usertrap 里面需要检测的就是 scause==13 和 scause==15，上面 scause=0xd 就是 Load page fault

检测逻辑大致如下

page fault
    │
    ▼
stval() 得到 fault VA
    │
    ▼
PGROUNDDOWN()
    │
    ▼
遍历 VMA
    │
    ├── 找不到 → kill
    │
    ▼
kalloc()
    │
    ▼
清零 page
    │
    ▼
readi(file, file_offset, page, PGSIZE)
    │
    ▼
根据 prot 设置 PTE_R/PTE_W
    │
    ▼
mappages()
    │
    ▼
return from trap
    │
    ▼
重新执行导致 fault 的指令

这个更改有些类似于 COW-lab. 这一过程中需要用到 readi() 函数

// Read data from inode.
// Caller must hold ip->lock.
// If user_dst==1, then dst is a user virtual address;
// otherwise, dst is a kernel address.
int readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)

大致逻辑如下

...
  } else if(r_scause() == 13 || r_scause() == 15){
    // 检查 VMAs 查看是否是 mmap 的区域，如果不是，直接跳转到错误中
    uint64 va = r_stval();
    struct vma* vma = 0;
    for(int i=0;i<NVMA;i++){
      // 取最小未使用地址作为末尾
      if(p->vmas[i].valid){
        uint64 start = p->vmas[i].addr;
        uint64 end = p->vmas[i].addr + p->vmas[i].length;
        if (start <= va && va < end)
          vma = &p->vmas[i];
      }
    }
    // 检查权限
    if(vma==0)
      goto error;
    if (r_scause() == 15 && !(vma->permissions & PROT_WRITE))
      goto error;
    if (r_scause() == 13 && !(vma->permissions & PROT_READ))
      goto error;
    // kalloc 分配内存
    char *mem = kalloc();
    if(mem== 0)
      goto kill_proc;
    // 暂时不考虑 device 和 pipe
    if(vma->file->type != FD_INODE){
      goto kill_proc;
    }
    // 需要计算出偏移量然后读文件
    uint64 va0 = PGROUNDDOWN(r_stval());
    uint64 offset = (va0 - vma->addr);
    memset(mem,0,PGSIZE);
    ilock(vma->file->ip);
    int n = readi(vma->file->ip, 0, (uint64)mem, offset, PGSIZE);
    iunlock(vma->file->ip);
    if (n < 0) {
      kfree((void*)mem);
      goto kill_proc;
    }
    // 读完添加页表
    uint flags = PTE_V | PTE_U;
    if (vma->permissions & PROT_READ)
      flags |= PTE_R;
    if (vma->permissions & PROT_WRITE)
      flags |= PTE_W;
    if (mappages(p->pagetable, va0, PGSIZE, (uint64)mem, flags)!=0){
      kfree((void*)mem);
      goto kill_proc;
    }
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
error:
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
kill_proc:
    p->killed = 1;
  }
...

改完之后变成了下面这样

$ mmaptest
mmap_test starting
test mmap f
mmaptest: mmap_test failed: munmap (1), pid=3
panic: freewalk: leaf

实现 munmap

munmap 除了修改 VMA 以外，还需要把相关的页表清除掉，本实验已经假设了清除要么从头开始，要么从末尾开始，要么清除全部，不能制造空洞

所以实现逻辑应该可以写成下面的样子

munmap(addr, length)
        │
        ▼
找到包含 addr 的 VMA
        │
        ├── 找不到 → -1
        │
        ▼
判断 munmap 的范围
        │
        ├── 中间 → -1
        │
        ├── 整个 VMA
        ├── 从头部截断
        └── 从尾部截断
        │
        ▼
MAP_SHARED ?
        │
        ├── yes → 将被解除映射的页面写回文件
        │
        ▼
uvmunmap()
        │
        ▼
修改 VMA / 删除 VMA
        │
        ▼
return 0

这里需要注意的是，length 不一定是页表大小的整数倍，需要对页表数量向上取整，参考代码如下，没有用 uvmunmap 是为了自行处理 PTE 无效问题

uint64
sys_munmap(void)
{
  uint64 addr;
  uint64 length;
  argaddr(0, &addr);
  argaddr(1, &length);
  if (length == 0)
    return -1;
  // unmap at the start, or at the end, or the whole region
  // 找到对应的 vma
  struct proc *proc = myproc();
  int chosen = -1;
  uint64 end = addr+length;
  for (int i=0;i<NVMA;i++){
    // 头匹配或者尾匹配
    if ((proc->vmas[i].valid) && ((proc->vmas[i].addr == addr) || ((proc->vmas[i].addr+proc->vmas[i].length) == end))){
      chosen = i;
      break;
    }
  }
  if (chosen == -1)
    return -1;
  if (length > proc->vmas[chosen].length)
    return -1;
  // 检查 MAP_SHARED 并决定是否写回磁盘
  if ((proc->vmas[chosen].flags & MAP_SHARED) && (proc->vmas[chosen].permissions & PROT_WRITE)){
    pte_t* pte;
    begin_op();
    ilock(proc->vmas[chosen].file->ip);
    for (uint64 va=PGROUNDDOWN(addr); va < PGROUNDUP(end); va+=PGSIZE){
      pte = walk(proc->pagetable, va, 0);
      if (pte && (*pte & PTE_V) && (*pte & PTE_D)) {    // 脏位检测，这里顺手实现了
        uint64 pa = PTE2PA(*pte);
        uint64 offset = va - proc->vmas[chosen].addr;
        int ret = (writei(proc->vmas[chosen].file->ip, 0, pa, offset, PGSIZE));
        if (ret < 0){
          iunlock(proc->vmas[chosen].file->ip);
          end_op();
          return -1;
        }
      }
    }
    iunlock(proc->vmas[chosen].file->ip);
    end_op();
  }
  // 释放页表
  pte_t* pte;
  for (uint64 va=PGROUNDDOWN(addr); va < PGROUNDUP(end); va+=PGSIZE){
    pte = walk(proc->pagetable, va, 0);
    if (pte && (*pte & PTE_V)){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
      *pte = 0;
    }
  }
  // 处理 vma 信息
  if ((proc->vmas[chosen].addr == addr) && ((proc->vmas[chosen].addr+proc->vmas[chosen].length) == end)){
    // clear all!
    fileclose(proc->vmas[chosen].file);
    proc->vmas[chosen].valid = 0;
  } else if (proc->vmas[chosen].addr == addr){
    // 删头
    proc->vmas[chosen].length -= (PGROUNDUP(end) - proc->vmas[chosen].addr);
    proc->vmas[chosen].addr = PGROUNDUP(end);
  } else {
    // 删尾巴
    proc->vmas[chosen].length -= (end - PGROUNDDOWN(addr));
    proc->vmas[chosen].addr = PGROUNDDOWN(addr);
  }
  return 0;
}

添加完这部分的代码之后再次运行应该有下面的结果

hart 2 starting
hart 1 starting
init: starting sh
$ mmaptest
mmap_test starting
test mmap f
test mmap f: OK
test mmap private
test mmap private: OK
test mmap read-only
test mmap read-only: OK
test mmap read/write
test mmap read/write: OK
test mmap dirty
test mmap dirty: OK
test not-mapped unmap
test not-mapped unmap: OK
test mmap two files
test mmap two files: OK
mmap_test: ALL OK
fork_test starting
usertrap(): unexpected scause 0x000000000000000d pid=4
            sepc=0x0000000000000088 stval=0x0000003fffffc000
fork_test failed
panic: freewalk: leaf

修改 `exit()`

Modify exit to unmap the process’s mapped regions as if munmap had been called. Run mmaptest; mmap_test should pass, but probably not fork_test.

添加一个函数供 exit 调用即可，函数逻辑类似 munmap

void
munmap_all(struct proc *p)
{
  for (int i = 0; i < NVMA; i++) {
    if (!p->vmas[i].valid)
      continue;
    struct vma *vma = &p->vmas[i];
    uint64 vma_begin = vma->addr;
    uint64 vma_end = vma->addr+vma->length;
    // 检查 MAP_SHARED 并决定是否写回磁盘
    if ((vma->flags & MAP_SHARED) && (vma->permissions & PROT_WRITE)){
      pte_t* pte;
      begin_op();
      ilock(vma->file->ip);
      for (uint64 va=vma_begin; va < vma_end; va+=PGSIZE){
        pte = walk(p->pagetable, va, 0);
        if (pte && (*pte & PTE_V) && (*pte & PTE_D)) {
          uint64 pa = PTE2PA(*pte);
          uint64 offset = va - vma->addr;
          int ret = (writei(vma->file->ip, 0, pa, offset, PGSIZE));
          if (ret < 0){
            iunlock(vma->file->ip);
            end_op();
            printf("Something wrong with munmap_all\n");
            return;
          }
        }
      }
      iunlock(vma->file->ip);
      end_op();
    }
    // 释放页表
    pte_t* pte;
    for (uint64 va=vma_begin; va < vma_end; va+=PGSIZE){
      pte = walk(p->pagetable, va, 0);
      if (pte && (*pte & PTE_V)){
        uint64 pa = PTE2PA(*pte);
        kfree((void*)pa);
        *pte = 0;
      }
    }
    fileclose(vma->file);
    vma->valid = 0;
  }
}

修改 `fork()`

Modify fork to ensure that the child has the same mapped regions as the parent. Don’t forget to increment the reference count for a VMA’s struct file. In the page fault handler of the child, it is OK to allocate a new physical page instead of sharing a page with the parent. The latter would be cooler, but it would require more implementation work. Run mmaptest; it should pass both mmap_test and fork_test.

可以写一个工具函数，把 vma 复制过去，供 fork 调用

void
vma_copy(struct proc *dst_p, struct proc *src_p){
  for (int i = 0; i < NVMA; i++) {
    if (!src_p->vmas[i].valid)
      continue;
    memmove(&(dst_p->vmas[i]), &(src_p->vmas[i]),sizeof(struct vma));
    filedup(dst_p->vmas[i].file);
  }
}

完成结果

运行 mmaptest 和 usertests 进行测试，得到结果如下

$ mmaptest
mmap_test starting
test mmap f
test mmap f: OK
test mmap private
test mmap private: OK
test mmap read-only
test mmap read-only: OK
test mmap read/write
test mmap read/write: OK
test mmap dirty
test mmap dirty: OK
test not-mapped unmap
test not-mapped unmap: OK
test mmap two files
test mmap two files: OK
mmap_test: ALL OK
fork_test starting
fork_test OK
mmaptest: all tests succeeded

这说明新增的两个系统调用 mmap,munmap 的功能通过了测试

$ usertests
usertests starting
test manywrites: OK
...
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED
$

这说明新增功能没有影响其他部分正常运行

完成！总共用时大约 7 小时。

运行 make grade 结果如下

== Test running mmaptest == 
$ make qemu-gdb
(6.1s) 
== Test   mmaptest: mmap f == 
  mmaptest: mmap f: OK 
== Test   mmaptest: mmap private == 
  mmaptest: mmap private: OK 
== Test   mmaptest: mmap read-only == 
  mmaptest: mmap read-only: OK 
== Test   mmaptest: mmap read/write == 
  mmaptest: mmap read/write: OK 
== Test   mmaptest: mmap dirty == 
  mmaptest: mmap dirty: OK 
== Test   mmaptest: not-mapped unmap == 
  mmaptest: not-mapped unmap: OK 
== Test   mmaptest: two files == 
  mmaptest: two files: OK 
== Test   mmaptest: fork_test == 
  mmaptest: fork_test: OK 
== Test usertests == 
$ make qemu-gdb
usertests: OK (254.3s) 
== Test time == 
time: OK 
Score: 140/140

Introduction#

添加系统调用接口#

user/user.h#

user/usys.pl#

kernel/syscall.h#

kernel/syscall.c#

kernel/sysproc.c#

添加 VMA 结构体相关定义#

初始化 VMA 结构体#

实现 mmap 接口#

参数传递问题#

在用户地址空间里面找块没用的区域#

实现 demand paging#

实现 munmap#

修改 exit()#

修改 fork()#

完成结果#