Raven's Blog

zhang.xingrui@foxmail.com

0%

MIT6.S081-lab-mmap

发表于 分类于

0. 前言 ·

本实验为 MIT6.s8081 的第十个实验，主题为 mmap 相关。实验要求实现简化版本的 mmap/munmap 。

1. 背景知识 ·

mmap 为 virtual memory 的扩展应用之一。通过将文件映射到 user 的 virtual memory address 中，使得 user 可以通过内存读写操作来进行文件读写。所以 mmap 涉及到 内存和 文件系统两部分。

要正确实现 mmap，首先要知道 mmap 的预期行为有哪些。查看 linux 和 mmap 相关系统调用：

mmap 相关函数有两个：

1
2
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

mmap 执行映射:

  1. addr, 要映射到哪儿的 hint（实际上并不一定映射到此处，对于本 lab 来说，addr 始终为 0，由内核选择要在 user vm addr 的哪个位置进行映射)
  2. length, 映射的长度。 可小于文件的 size， 等于文件的 size，或者超过文件的 size。如果超过了文件的 size，超出的部分填充为 0.
  3. prot, 对映射的区域的 protection 属性，本 lab 仅需支持 PROT_READ 和 PROT_WRITE。前者代表可读，后者代表可写。
  4. flags，映射的方式是什么。本 lab 仅需支持 MAP_SHARED 和 MAP_PRIVATE。 两者的区别如下：
    1. MAP_SHARED: Share this mapping. Updates to the mapping are visible to other processes mapping the same region, and (in the case of file-backed mappings) are carried through to the underlying file. 即更新对其他 process 可见，更新会写会被映射的文件。
    2. MAP_PRIVATE： Create a private copy-on-write mapping. Updates to the mapping are not visible to other processes mapping the same file, and are not carried through to the underlying file. It is unspecified whether changes made to the file after the mmap () call are visible in the mapped region. 即更新对其他 process 是不可见的，更新不会写回被映射的文件，更新采用都会在自身独有的 copy 上执行。
  5. fd， 要映射的 file 的 fd。
  6. offset， file 的 offset，本 lab 始终为 0.

munmap 取消映射:

  1. addr, 要取消映射的首地址。 该地址不一定等于 mmap 返回的地址。所以取消的地址范围可能不是 mmap 中的地址范围。对于本 lab 而言，仅需支持三种情况的 munmap， 如下图：

    对于区间中间位置段，留下一个 "hole" 的情况，不予考虑。

  2. length: 需要取消映射的范围长度。

另外需要注意的是，执行 mmap 时，并未分配实际的物理页，mmap 采用了 lazy allocation 的方案，映射只是更改了页表，后续通过 page fault 来添加需要映射的 page。

2. 实现 ·

首先添加 mmap 和 munmap 系统调用，下面仅说下签名：

1
2
3
4
5
char *mmap(void *addr, int len, int prot, int flags, int fd, int off);
int munmap(void *addr, int len);

uint64 sys_mmap(void);
uint64 sys_munmap(void);

1. 基本数据结构 ·

接着实现 vma 相关结构体，用于表示一个 mmap 的映射区：

1
2
3
4
5
6
7
8
9
10
#define NVMA 16		/* how many vma area support */

struct vma_area {
	uint64 addr;		/* start address of mapping */
	uint64 len;
	int prot;
	int flags;	
	uint64 off;
	struct file *file;	
};

一个 vma_aera 代表一次映射。由于 xv6 内核不支持内核分配器（即内核的 malloc), 模仿 ftable，实现一个 vma_table，表示全局可用的的 vma 结构：

1
2
3
4
5
struct
{
  struct spinlock lock; /* protect vma_table  */
  struct vma_area vma_table[NVMA];
} kvma;

完成对 vma 的分配，释放，初始化函数：

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
void
vmainit(void)
{
  initlock(&kvma.lock, "vma");
}

struct vma_area*
vmaalloc(void)
{
  struct vma_area* vma;

  acquire(&kvma.lock);
  for (vma = kvma.vma_table; vma < kvma.vma_table + NVMA; vma++) {
    if (vma->file == 0) {
      // zero vma
      memset(vma, 0, sizeof(struct vma_area));
      release(&kvma.lock);
      return vma;
    }
  }
  release(&kvma.lock);
  return 0;
}

void
vmafree(struct vma_area* vma)
{
  acquire(&kvma.lock);
  vma->file = 0;
  release(&kvma.lock);
}

现在 xv6 支持并发的分配和释放 vma。 接下来来看看如何实现 vma：

每个进程都有自己的 vma 映射，且可能有多组映射，因为一个进程 mmap 多次，所以更改 proc 结构，添加 vma 支持：

2. sys_mmap·

以上添加了必须的数据结构，现在来完成 mmap 主体逻辑：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// char *mmap(void *addr, int len, int prot, int flags, int fd, int off);
// the addr and offset always will be 0
uint64
sys_mmap(void)
{

  int len, prot, flags, fd, off;
  struct proc* cur_proc;
  struct file* file;
  struct vma_area *vma;

  if (argint(1, &len) < 0 || argint(2, &prot) < 0 || argint(3, &flags) < 0 || argint(4, &fd) < 0 || argint(5, &off) < 0)
    return -1;
  // check whether the file is opened or not
  cur_proc = myproc();
  if (fd < 0 || fd >= NOFILE || cur_proc->ofile[fd] == 0) {
    return -1;
  }
  // check whether the perm of prot is the subset of the perm of the file or not
  file = cur_proc->ofile[fd];
  if (prot & PROT_READ) {
    if (!file->readable) {
      return -1;
    }
  }
  if ((flags & MAP_SHARED) && (prot & PROT_WRITE)) {  // MAP_SHARED flag with PROT_WRITE indicates file must be writeable
    if (!file->writable) {
      return -1;
    }
  }

  // allocate a vma 
  if((vma = vmaalloc()) == 0) {
    panic("vmaalloc failed");
    return -1; 
  }
  vma->addr = 0;    // init addr: see code below 
  vma->len = len;
  vma->prot = prot;
  vma->flags = flags;
  vma->off = off;
  vma->file = file;
  filedup(vma->file); // increase file refcnt so that it's impossible to free the file

  acquire(&cur_proc->lock);
  // find the first continuous addr space in user page table so that this mapping can be mapped successfully
  uint64 sz = cur_proc->sz;
  // 向上页对齐, 如果不对齐，后续的page fualt handler使用的va可能低于addr
  uint64 start_addr = PGROUNDUP(sz);
  if(lazy_growproc(cur_proc, len + start_addr - sz) < 0) {
    release(&cur_proc->lock);
    fileclose(vma->file);
    vmafree(vma);
    return -1;
  }
  vma->addr = start_addr;

  // put the vam structure into proc structure
  int i;
  for(i = 0; i< NOFILE; i++) {
    if(cur_proc->vmas[i] == 0) {
      cur_proc->vmas[i] = vma;
      break;
    }
  }
  release(&cur_proc->lock);
  if(i == NOFILE) {
    panic("the vmas in proc is full");
    return -1;
  }
  return start_addr;
}

主要逻辑为：‘

  1. 获取传入参数，因为本 labaddr 始终为 0，所以从第一个参数开始获取。
  2. 做一系列的合法性检查。比如传入的 prot 包含 PROT_READ, 则打开的文件也必须支持 read。 唯一的注意点是，** 如果 file 为 readonly, 但是 map 的 flag 为 MAP_PRIVATE，prot 为 PROT_WRITE， 此时也可以写入的。** 因为这样的映射组合，并不会修改到底层的文件，所有的修改都在进程自己的拷贝副本上进行。
  3. 分配 vma，并执行初始化。内核需要在进程空间中找到一个合适的连续地址空间，用于完成本次映射请求，找到的地址空间首地址应该是 page-aligned 的， 如果不是 page-aglined 的，后续的 page_fault_handler 中会出现错误。比如当前映射的首地址为 2K， 现在要访问的地址也是 2K， 对于第一次 load page 来说，会出现 page fault， 在 page_fault_hanlder 中，懒加载的 page 需要按照 page-aligned 的方式加载 page, 所以懒加载的页地址为 0K-4K-1。其中 0K-2K-1 这部分并没有做任何映射，所以会出现问题。
  4. 最后在 proc 中找到合适的 vma slot, 存放 vma 结构即可。

第三步中，寻找合适的连续地址空间，采用的是 lazy_growproc 的方式来完成：

1
2
3
4
5
6
7
8
9
10
11
12
// Increase proc used addr space without allocating physical pages
// Return 0 on success, -1 on failure.
// NOTE: n must be larger than 0.
// NOTE: p.lock should be held
int lazy_growproc(struct proc *p, int n) 
{
  if(n <= 0) {
    return -1;
  }
  p->sz += n;
  return 0;
}

3. page_fault_handler·

至此完成了 sys_mmap, user app 执行 mmap 后，可能会对 map 的 page 执行 read/write 操作，此时会触发 page_fault, 下面是 page_fault_handler 代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// mmap allocate physical memory lazily. 
// use this function to allocate physical memory and populate the corresponding file content.
static void
page_fault_handler(struct proc* p)
{
  uint64 va = r_stval();
  struct vma_area** vma_slot;
  struct vma_area* vma;
  struct file *file;
  if (va >= p->sz) {
    p->killed = 1;
    return;
  }

  // 检查va落入到哪个 vma area
  va = PGROUNDDOWN(va);
  if((vma_slot = vmalookup(p, va)) == 0) {
    p->killed = 1;
    return;
  }
  vma = *vma_slot;

  // alloc mem
  char* mem = kalloc();
  if (mem == 0) {
    // panic("page fault handler: out of memory");
    p->killed = 1;
    return;
  }
  memset(mem, 0, PGSIZE);

  // populate file content
  uint64 start_off = va - vma->addr + vma->off;  
  file = vma->file;

  ilock(file->ip);
  if(start_off >= file->ip->size) { // mapping size is larger than file size, fill memory with zero
    iunlock(file->ip);
  } else {
    begin_op();
    uint64 ret_bytes = file->ip->size < start_off + PGSIZE ? file->ip->size - start_off : PGSIZE;
    if (readi(file->ip, 0, (uint64)mem, start_off, ret_bytes) != ret_bytes) {
      iunlock(file->ip);
      end_op();
      kfree(mem);
      p->killed = 1;
      return;
    }
    iunlock(file->ip);
    end_op();
  }

  // add map pages
  if (mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_W | PTE_R | PTE_U) != 0) {
    kfree(mem);
    p->killed = 1;
  }
}

这部分的工作为：

  1. 执行简单的合法性校验：访问 va 是否超过 process 的最大申请内存地址边界
  2. 找到包含 va 的 vma 结构。
  3. 分配实际的物理页
  4. 注入对应的文件内容。这里的注意点是，有可能 mmap 传入的 map length 是大于 file size 的，对于超过 file size 部分，全部填充为 0。
  5. 最后，向页表中添加这个物理 page 的映射。

注意，我个人的实现中，只要出现了 page fault，就单独分配了物理页给进程，但实际上 linux 中的实现，如果 flags 为 MAP_SHARED，则并不需要单独分配物理页，直接将映射绑定到 page cache 中即可，这样可以减少一次页的拷贝，提升性能。 如果 flags 为 MAP_PRIVATE， 则采用 COW 机制。 更多关于 Linux 的 mmap 描述，可参考：这里

上述代码使用到的 vmalookup 函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// find the vma slot refering to a vma structure which contains 
// va
struct vma_area **
vmalookup(struct proc* p, uint64 va)
{
  acquire(&p->lock);
  for(int i = 0; i< NOFILE; i++) {
    if(p->vmas[i] != 0 && p->vmas[i]->file != 0) {
      if(va >= p->vmas[i]->addr && va < p->vmas[i]->addr + p->vmas[i]->len) {
        release(&p->lock);
        return &p->vmas[i];
      } 
    }
  }
  release(&p->lock);
  return 0;
}

代码逻辑很简单，循环遍历 p 的 vma 结构，找到包含 va 的 vma。 之所以采用二级指针，是因为后续的 sys_munmap 中会使用到。

4. sys_munmap·

现在来看看取消映射的代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
uint64 
do_munmap(uint64 addr, int len)
{
  struct proc* cur_proc;
  struct vma_area** vma_slot;
  struct vma_area* vma;
  struct file* file;

  if(addr % PGSIZE) {
    panic("sys_munmap: addr should be PGSIZE-aligned");
  }
  // debug -- 目前仅支持addr和len都为 PGSIZE-aligned的请求
  if(len % PGSIZE) {
    panic("sys_munamp: len shoulbe be PGSIZE-aligned");
  }

  cur_proc = myproc();
  vma_slot = vmalookup(cur_proc, addr);
  if(vma_slot == 0) {
    return -1;
  }
  vma = *vma_slot;
  if (len > vma->len) {
    panic("sys_munmap: len is larger than the vma");
  }
  file = vma->file;

  // flush modified pages back to file
  // free mapged page
  if (vma->flags & MAP_SHARED) {
    ilock(file->ip);
    begin_op();
  }
  for (uint64 a = addr; a < addr + len; a += PGSIZE) {
    pte_t* pte = walk(cur_proc->pagetable, a, 0);
    if (vma->flags & MAP_SHARED) {
      if (*pte & PTE_D) { // if current page is dirty, wirte it back
        uint64 bytes = a + PGSIZE < vma->addr + vma->len ? PGSIZE : vma->len % PGSIZE;
        uint64 file_off = a - vma->addr + vma->off;
        if (writei(file->ip, 1, a, file_off, bytes) != bytes) {
          end_op();
          panic("munmap: write dirty page back failed");
        }
      }
    }
    uvmunmap(cur_proc->pagetable, a, 1, 1);
  }
  if (vma->flags & MAP_SHARED) {
    iunlock(file->ip);
    end_op();
  }

  // lab 简化了 munmap操作， 只支持映射区域全释放，头释放和尾释放
  // TODO(raven): 暂时没有考虑4k对齐的问题
  // update vma or free it
  if(vma->addr == addr && vma->len == len) { // the whole vma
    fileclose(file);
    vmafree(vma);
    *vma_slot = 0;
  } else if(vma->addr == addr && vma->len > len){ // the start region
    // update vma
    vma->addr = (addr + len);
    vma->len -= len;
  } else if(vma->addr != addr && addr + len == vma->addr + vma->len) { // the end region
    vma->len -=len;
  } else {
    panic("unsupported munmap operation: this will leading to a hole in the va");
  }
  return 0;
}

uint64
sys_munmap(void)
{
  uint64 addr;
  int len;
  if(argaddr(0, &addr) < 0 || argint(1, &len) < 0) {
    return -1;
  }
  return do_munmap(addr, len);
}

上述代码完成：

  1. 合法性检验
  2. 找到包含 addr 的 vma
  3. 对于 MAP_SHARED flag 的 map，需要将写入的数据，回写至文件，所以执行加解锁处理和文件写入。 由于仅需对 DIRTY_PAGE 进行写入，所以添加了 *pte & PTE_D 的判定。
  4. 取消页映射
  5. 更新 vma 结构：
    1. 如果释放的是整个 vma 所代表的的地址空间，则释放 vma 结构
    2. 如果释放的开头 / 结尾区间，则更新 vma 结构即可，无需释放

5. 其他 ·

调整 uvmunmap, 用于支持 lazy allocation:

调整 fork, 将父进程的 vma 继承给子进程：

调整 allocproc， 完成 proc vma 的初始化：

调整 uvmcopy, 以支持 fork 时的页表复制。

调整 exit, 释放进程未主动释放的 vma:

** 修改 main，** 完成对全局 vma_table 的初始化：

至此完成 mmap lab，执行 mmaptest 和 usertests 检验是否通过。

3. Linux 中 mmap-read 和 read 对比 ·

本节是对 mmap 方式的读取和 read 系统调用的一点感悟。仅为个人理解，可能有误，欢迎指正。

以下探讨针对 Linux 实现，并不是 xv6 中的实现。

网络上充斥着大量对 mmap 的误解，认为 mmap 方式的读取性能一定比 read 系统调用的性能好，实际上并不是的。甚至在大数据量下的随机读，mmap 性能要更差于 read 系统调用。

一种最通用的说法是，用户空间发起 read 系统调用读取请求，数据存在着两次拷贝，一次是从磁盘拷贝到内核空间（page cache) 中，另一次是从 page cache 拷贝到用户空间中，所以存在两次拷贝。而 mmap 由于读取时，可以直接将 vma 映射绑定到 page cache 中，减少了一次从 page cache 到用户空间的页拷贝（即 mmap 读取时，仅需从磁盘拷贝到内核空间 (page cache))。 相比之下，似乎 mmap 更快，毕竟减少了一次数据拷贝。

但其实不然，mmap 需要依赖 page fault 、修改页表 pte 、 invalidate TLB，这些开销是很大的。所以需要在 “多拷贝一次 page” 与 “ page fault, 修改页表，invalidate TLB” 之间做 trade off. 看哪边的成本更高。

最后谈谈个人经历：之前阅读过 LevelDB 系统源码，LevelDB 底层默认采用 mmap 的方式随机读，而与此对标的 RocksDB 底层默认采用 read 的方式随机读（具体而言是 pread)。 在实现我个人的系统时，对 mmap 和 read 两种读方式都做了测试。结果发现 read 形式的随机读性能是 mmap 方式的随机读性能的 3 倍左右。

4. 总结 ·

mmap，曾经困扰我很久的概念。在这个 lab 之后，对其有了更深的理解与感悟。

文章对你有帮助？打赏一下作者吧