MIT 6.S081 Lab 10: mmap

18 Mar 2023

We spend our time envying people whom we wouldn’t wish to be.

6.S081课程的第十个Lab，为 xv6 文件系统添加添加mmap和munmap，重点关注内存映射文件。

Background

mmap 和 munmap 系统调用允许UNIX程序对它们的地址空间施加详细的控制。它们可用于在进程间共享内存、将文件映射到进程地址空间，以及作为用户级页面故障方案(如课堂上讨论的垃圾收集算法)的一部分。

mmap 的声明，

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

mmap 可以通过多种方式调用，但是该实验仅需要其与内存映射文件相关功能的一个子集。我们可以假设 addr 始终为 0，这意味着内核应决定映射文件的虚拟地址。mmap 返回该地址，或 0xffffffffffffffff。长度 length 是要映射的字节数；它可能与文件的长度不同。prot指示映射内存是否是可读取，可写入和/或可执行文件；我们可以假定 prot 是 PROT_READ 或 PROT_WRITE 或两者兼而有之。标志 flags 要么是 MAP_SHARED，这意味着对映射的内存的修改应写回文件,或 MAP_PRIVATE，这意味着它们不应该写回。我们不必在标志中实现其他任何位。fd是要映射的文件的打开文件描述符。您可以假设偏移量 offset 为零（这是文件映射的起点）。映射同一个 MAP_SHARED 文件的进程不共享物理页是可以的。

munmap 声明如下，

int munmap(void *addr, size_t length);

munmap(addr, length) 应在指定的地址范围内删除 mmap 映射。如果该过程修改了内存，且其映射为 MAP_SHARED，则应先将修改写入文件。munmap 调用可能仅覆盖 mmap-ed 区域的一部分，但我们可以假设 unmap 在区域开始位置，或整个区域（但不会在区域中间打孔）。

Implementation

添加系统调用的内容之前课程有提及，具体见 MIT 6.S081 Lab: System calls。同时定义 mmap 参数的宏，

#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

为了维护 mmap 为每个进程映射的内容。定义一个对应于第17讲的 VMA (虚拟内存区域)的结构，记录由 mmap 创建的虚拟内存范围的地址、长度、权限、文件等。由于 xv6 内核中没有内存分配器，因此可以在 struct proc 里声明一个固定大小的 VMA 数组，并根据需要从该数组中进行分配。大小为16就足够了。

// in proc.h file
#define MAXVMA 16

struct VMA {
  uint64 addr;        // address
  uint64 len;         // length
  int prot;           // permissions 
  int flags;          // flags
  struct file *f;     // file being mapped
  uint64 offset;      // offset of mapped file. Cannot share with f->off
                      // Otherwise, what if a process mmap/munmap a file f, and mmap the file again? 
                      // The file offset may be set in previous mmap/munmap call.
  uint64 ori_len;     // length of the mmapp call, used for free proc memory
  int used;           // if this vma is used
};

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct VMA mapped[MAXVMA];   // User virtual memory area
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

实现mmap：在进程的地址空间中找到一个未使用的区域（我使用 struct proc 的 sz 字段）来映射文件，并在进程的映射区域表中添加一个VMA。VMA应该包含一个指向被映射文件的结构文件的指针；mmap应该增加文件的引用计数，这样当文件关闭时结构不会消失(使用filedup)。

// file sysfile.c
uint64 
sys_mmap(void)
{
  // void *mmap(void *addr, uint64 length, int prot, int flags, int fd, uint64 offset);
  // void *addr; // unused 0th arg
  uint64 length;
  int prot, flags, fd;
  // uint64 offset; // asumed zero, unused 5th arg
  struct file *f;

  struct proc *p = myproc();
  struct VMA* pvma;

  if (argaddr(1, &length) < 0 ||
      argint(2, &prot) < 0 ||
      argint(3, &flags) < 0 ||
      argfd(4, &fd, &f) < 0) {
        
        return -1;
  }

  // if file is not writable and shared, cannot map it as writable
  // if file is private is ok.
  if(!f->writable && (prot & PROT_WRITE) && (flags & MAP_SHARED)) {
    return -1;
  }

  for(pvma = p->mapped; pvma != (p->mapped + MAXVMA); ++pvma) {
    if (0 == pvma->used) {

      pvma->addr = p->sz; 
      length = PGROUNDUP(length);
      p->sz += length;
      pvma->len = length;


      pvma->prot = prot;
      pvma->flags = flags;
      
      pvma->f = f;
      filedup(pvma->f); // incr ref count of f

      pvma->offset = 0;
      pvma->ori_len = length;
      pvma->used = 1;
      return (uint64)(pvma->addr);
    }
  }



  return ((uint64)-1);
}

需要注意将 length 进行页面大小的对齐。同时用 lazy allocation 的方式。这意味着，mmap 不应该分配物理内存或读取文件。相反，在usertrap 中(或由usertrap调用)的页错误处理代码中执行该操作。懒式分配可确保大文件的 mmap 是快速的，并且大于物理内存的文件的mmap 是可能的。

添加代码处理在 mmap-ed 区域中引起的页面故障，以分配物理内存的页面，将相关文件的4096字节（页面大小）读取到该页面中，然后将其映射到用户地址空间中。使用 readi 读取文件，在页面上正确设置权限。

else if(which_cause == 0x0d || which_cause == 0x0f ){
    // page fault, exception code 13 and 15

    // fault virtual addr
    uint64 va = r_stval();
    if(va < p->trapframe->sp || va >= p->sz ) {
      printf("usertrap(): page fault address upder sp or beyond size of process memory\n");
      goto fail;
    }

    
    int found = 0;
    for(struct VMA* vma = p->mapped; vma != (p->mapped + MAXVMA); vma++) {
      // find the vma
      if (vma->used && vma->addr <= va && va < (vma->addr + vma->len)) {
        // allocate page
        void* newPage;
        // read offset
        uint r_off;

        if(0 == (newPage = kalloc())) {
          printf("usertrap(): fail to allocate new page\n");
          goto fail;
        }

        va = PGROUNDDOWN(va); // va -> va of the fault page 

        // map page to user address space
        // PTE flag low 4 bits are XWRV, need to leftshift
        if( mappages(p->pagetable, va, PGSIZE, (uint64)newPage, ((vma->prot) << 1 | PTE_U) ) < 0) {
          printf("usertrap(): fail to map page\n");
          goto fail;
        }

        
        // fill page with 0
        memset(newPage, 0, PGSIZE);

        // va - vma->addr is relevant distance and vma->offset is absolute offset in file
        r_off = va - vma->addr + vma->offset; 
        // read 4096 bytes of the relevant file into that page
        begin_op();
        ilock(vma->f->ip);
        readi(vma->f->ip, 1, va, r_off, PGSIZE);
        iunlock(vma->f->ip);
        end_op();
        found = 1;
        break;
      }

    }
    
    if (!found) {
      printf("usertrap(): page not found in VMA\n");
      goto fail;
    }

调用 readi 时两点需要注意，

在 inode 读取前后需要加解锁。
设置在文件中读取的偏移参数时，不能使用 f->off，因为这是通过文件 f 共享的。其他系统调用如wriet/read会修改这个这个字段。应该使用 va - vma->addr + vma->offset 计算出在文件中真实的偏移。

实现munmap:找到地址范围的VMA并取消指定页面的映射(提示:使用uvmunmap)。如果munmap删除了前一个mmap的所有页，它应该减少相应结构文件的引用计数。如果修改了未映射的页面，并且文件被映射为 MAP_SHARED，则将页面写回文件。可以模仿 filewrite 函数。理想情况下，实现应该只回写程序实际修改过的 MAP_SHARED 页。如RISC-V PTE中的脏位(D)表示是否写过一页。但 xv6 没有实现相关脏位的标记，所以我选择全部写回。

// in file sysfile.c
uint64 sys_munmap(void) 
{
  // int munmap(void *addr, uint64 length);
  uint64 addr;
  uint64 length;
  int is_whole;
  struct proc* p;
  uint w_off;

  if (argaddr(0, &addr) < 0 || argaddr(1, &length) < 0)
    return -1;
  
  
  p = myproc();
  
  for(struct VMA* cur = p->mapped; cur != (p->mapped + MAXVMA); ++cur ) {
    if(cur->used && cur->addr <= addr && addr < (cur->addr + cur->len)) {

      // unmap at [start, end) or the whole region
      if(addr != cur->addr)
        panic("munmap: addr is not the start of mapped region");

      length = PGROUNDUP(length);
      w_off = cur->offset;
      if (length >= cur->len) {
        // whole region
        is_whole = 1;
        length = cur->len;
        cur->used = 0;
      } else {
        is_whole = 0;
        cur->addr += length;
        cur->offset += length;
      }
      cur->len -= length;

      

      // like uvmunmap, remove the mapped physical page from pg_table
      // and write back
      for (uint64 va = addr; va != addr + length; va += PGSIZE) {
        pte_t *pte = walk(p->pagetable, va, 0);
        if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0) {
          // like walkaddr only be used to look up user pages
          continue;
        }

        if(cur->flags & MAP_SHARED) {
          begin_op();
          ilock(cur->f->ip);
          if(writei(cur->f->ip, 1, va, w_off + va - addr, PGSIZE) != PGSIZE) {
            panic("munmap: fail to write back");
          }
          iunlock(cur->f->ip);
          end_op();
        }

        kfree((void*)PTE2PA(*pte));
        *pte = 0;
      }
      

      if(is_whole)
        fileclose(cur->f);

      return 0;
    }
  }

  return -1;
}

实现 munmap 需要注意，

在 inode 写入前后需要加解锁与开始事务。
设置在文件中写入的偏移参数时，使用原 vma->off。
因为惰式分配物理页，所以原 mapped-region 不是全部都有映射的物理页。所以需要调用 walk 检查 pte 才行。

考虑到资源回收，修改 exit 以取消进程 mapped-region 的映射，就像调用了 munmap 一样。确保多进程共享，修改 fork 以确保子进程拥有与父进程相同的映射区域。不要忘记增加 VMA 的 struct file 的引用计数。在子进程的页错误处理代码中，可以分配一个新的物理页面，而不是与父进程共享一个页面。共享当然更好，但这需要更多复杂的实现，如类似 Copy-on-write 实验中的页面引用计数。

// in file proc.c function exit(int)

  // like munmap the whole VMA region, like call munmap
  // change p->sz, physical pages in page table are free in wait 
  for(struct VMA* v = p->mapped; v != (p->mapped + MAXVMA); ++v) {
    if(v->used) {
      for (uint64 va = v->addr; va != v->addr + v->len; va += PGSIZE) {
        pte_t *pte = walk(p->pagetable, va, 0);
        if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0) {
          // like walkaddr only be used to look up user pages
          continue;
        }
        kfree((void*)PTE2PA(*pte));
        *pte = 0;
      }
      fileclose(v->f);
      p->sz -= v->ori_len;
    }
    memset(v, 0, sizeof(struct VMA));
  }

// in file proc.c function for(void)
  // Copy VMA
  for(int i=0;i<MAXVMA ; i++) {
    struct VMA *v = &p->mapped[i];
    struct VMA *nv = &np->mapped[i];
    // like call mmap
    if(v->used) {
      memmove(nv,v,sizeof(struct VMA)); 
	    filedup(nv->f);
    }
  }

同时，页表中原本的非 VMA 页仍等待到 wait 中回收。但需要注意的是，因为惰式分配，导致p->sz之下的虚拟地址有许多是未映射物理页于页表中的。所以 vm.c 中的 uvmcopy 与 uvmunmap 都需要修改遭遇 PTE_V == 0 页面的逻辑（不再panic）。

Conclusion

通过 mmap 机制我们可以实现许多场景的内存映射，如 Linux内存管理：mmap原理提到的，

映射类型	具体场景	对应的flags
私有文件映射	映射动态库	`MAP_PRIVATE`
私有匿名映射	malloc分配大内存在glibc中对应的mmap()实现	`MAP_PRIVATE MAP_ANONYMOUS`
共享文件映射	进程间读写同一文件	`MAP_SHARED`
共享匿名映射	用于进程间共享内存	`MAP_SHARED MAP_ANONYMOUS`
大页内存映射	用于申请大页内存	`MAP_PRIVATE MAP_ANONYMOUS MAP_HUGETLB`
待补充…..	…	…

实际上，现代操作系统如 Linx 的 VMA 结构相当复杂。从文章Linux的进程地址空间[二] - VMA可以看出，Linux 将 VMA 机制加入 mm_struct 一同实现了惰式分配，这比 xv6 用页表单独管理物理页映射要更简便，消除了惰式分配实现和 mmap-ed 文件实现之间的冗余。

Reference

system-programming