xv6-labs-2020.lab9.mmap

Posted on Edited on In Views:
内存映射

lab9 mmap

1. 作业链接

  • https://pdos.csail.mit.edu/6.828/2020/labs/mmap.html

2. 实习内容

  • 实现系统调用 mmap，munmap
1
2
3
void* mmap(void* addr, size_t length, int prot, int flags,
           int fd, off_t offset);
int munmap(void* addr, size_t length);
  • linux 下通过让一下命令查看对 mmap、munmap 的解释
1
man 2 mmap
  • mmap()
    • addr：起始地址
      • 如果为 NULL，则内核会选择一个页对齐的地址
      • 如果不为 NULL，只是一个 hint，如果不可行则会选择其他地址
    • length：申请的空间长度（字节）
    • prot：一些保护位
      • PROT_EXEC Pages may be executed.
      • PROT_READ Pages may be read.
      • PROT_WRITE Pages may be written.
      • PROT_NONE Pages may not be accessed.
    • flag：设置的 flag，表示对这块区域的操作对其它进程的影响
      • MAP_SHARED、MAP_SHARED、MAP_ANONYMOUS 等
    • fd：建立映射的文件
    • offset：被映射对象内容的起点
    • 返回值为起始地址，(void*)-1 表示失败
  • munmap()
    • addr：起始地址
    • length：空间长度（字节）

2.1 说明

  • 我们在这个实验中只需要实现简单功能即可
  • mmap
    • addr 可以认为始终为 0
      • 表示起始地址由内核决定
    • 返回值为起始地址，或者 0xffffffffffffffff 表示失败
    • length 表示需要映射内容的长度
      • 可能和文件不等长
    • prot 表示这块区域是否可读、可写、可执行
      • 我们可以假设只能是 PROT_READ 、PROT_WRITE 、二者都有
      • flags 只能是 MAP_SHARED（修改需要写回文件）、MAP_PRIVATE（不需要写回文件）
    • fd 为文件描述符
    • offset 为 0
  • 我们允许 MAP_SHARED 的映射区域不对应相同的物理页
  • munmap
    • 解除映射
    • 如果 flag 为 MAP_SHARED，则需要写回文件
    • 解除的区域可以是映射区域的一个子集，但是我们可以假设接触区域只能是如下情况
      • 整个区域
      • start 和映射区域相同
      • end 和映射区域相同

2.2 提示

  • 准备工作放在实现里面
  • mmap 本身不分配物理页，通过 page fault 分配物理页
    • usertrap 就行了，mmap 只会被用户态调用分配
    • 保证快速映射一块大区域，允许映射比实际物理内存更大的范围
  • 每个进程保存一个数据结构 VMA（virtual memory area），记录被 mmap 映射的区域
    • 简单的可以直接开一个定长的数组，16 就足够了
    • VMA 需要保存如下内容
      • address, length, permissions, file 等
  • mmap 的实现
    • 首先在进程的空闲内存区与中找到一块区域分配空间
    • 在 VMA 中找到一个空闲区域用于保存记录
    • VMA 中需要有一个 struct file* 指针，需要把 file 的引用计数+1（避免释放）
      • 可以看 filedup 的实现
    • 注意权限的检查，有 read-only 的测试样例
      • 如果把只读区域映射为可写的而且是 MAP_SHARED 则直接报错
      • MAP_PRIVATE 不会写
  • 此时由于 lazy 的结果会导致 page fault
  • 实现 page fault 时读取文件，分配物理页
    • 捕捉 page fault
    • 通过 readi 读取文件中与访问地址相近的 4096 bytes，并建立映射关系
      • readi 的时候需要给 inode 加锁
    • 正确设置权限位
  • 此时能够正确到达第一个 munmap 测试
  • 实现 munmap
    • 遍历 VMA，找到对应的 VMA，释放对应的空间即可
    • 如果是 MAP_SHARED 的话，需要将修改的内容写回文件
      • 参考 filewrite 实现
    • 如果是释放了整个映射区域的话，需要将文件的引用计数-1
  • 理论上，我们应该只写回真正被修改的页，也就是说 dirty 位设置为 1 的页
    • 但是这里没有检查，因此我们不做要求
  • exit() 退出的时候，释放所有的 VMA 中没有解除映射的块
  • fork() 的时候，子进程拥有和父进程一样的 VMA，允许在子进程遇到 page fault 的时候分配一个不和父进程一样的物理页
    • 更好的方式是和父进程共用一个物理页，但是这里不要求

2.3 实现

(1) 添加系统调用

  • Makefile
1
2
3
UPROGS=\
    # ...
    $U/_mmaptest\
  • 添加系统调用
  • user/usys.pl
1
2
entry("mmap");
entry("munmap");
  • user/user.h
1
2
void* mmap(void*, int, int, int, int, int);
int munmap(void*, int);
  • kernel/sysfile.c
1
2
3
4
5
6
7
uint64 sys_mmap (void){
  return -1;
}

uint64 sys_munmap (void){
  return -1;
}
  • kernel/syscall.h
1
2
#define SYS_mmap   22
#define SYS_munmap 23
  • kernel/syscall.c
1
2
3
4
5
6
7
extern uint64 sys_mmap(void);
extern uint64 sys_munmap(void);
static uint64 (*syscalls[])(void) = {
    // ...
    [SYS_mmap]   sys_mmap,
    [SYS_munmap]   sys_munmap,
};

(2) VMA

  • 添加数据结构 VMA
1
2
3
4
5
6
7
8
9
10
11
// kernel/proc.h
struct VMA {
    uint64 start;  // 起始地址
    uint64 end;    // 结束地址
    uint64 length; // 区域的长度
    int prot;      // 权限
    int flags;     // MAP_SHARED,MAP_PRIVATE
    struct file *file; // 对应的文件
    int offset;    // 可能释放了一个部分, 此时 offset 可能不是 0
};

  • 在 proc 中添加 VMA
1
2
3
4
5
6
// kernel/proc.h
#define MAXVMA 16
struct proc {
    // ...
    struct VMA vma[MAXVMA];
}

(3) mmap

  • 按照提示的说明实现 mmap()
  • 找到一个空闲区域，写入 VMA，修改当前进程的 sz
  • 注意上面提到的一个权限问题
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
// kernel/sysfile.c
uint64 sys_mmap(void){
    // uint64 addr; // 都为 0
    int length, prot, flags, fd;
    // int offset; // 都为 0
    struct file* f;

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

    // 如果把只读区域映射为可写的而且是 MAP_SHARED 则直接报错
    // MAP_PRIVATE 不会写
    // 有 read-only 测试
    if(!f->writable && (prot & PROT_WRITE) && (flags & MAP_SHARED))
        return -1;

    // 找到空闲区域, 找到空闲 VMA
    struct proc* p = myproc();
    for(int i = 0; i < MAXVMA; ++i) {
        struct VMA* v = &(p->vma[i]);
        if(v->length == 0) {
            v->length = length;
            v->start = p->sz;
            v->prot = prot;
            v->flags = flags;
            v->offset = 0;
            v->file = filedup(f); // 引用计数+1
            // 地址必须是页对齐的
            length = PGROUNDUP(length);
            p->sz += length;
            v->end = p->sz;
            return v->start;
        }
    }
    return -1;
}
  • 由于这里并没有分配内存，因此会触发 usertrap()

(4) usertrap

  • 在 usertrap 中处理 page fault
    • 和 lab4-lazy 比较像
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// kernel/trap.c:usertrap
// ...
} else if((which_dev = devintr()) != 0){
    // ok
} else if(r_scause() == 0xd || r_scause() == 0xf) {
    // 因为包含关系的问题, 我们直接把函数放到 sysfile.c 里面
    // printf("%p\n%p\n", r_stval(), PGROUNDDOWN(r_stval()));
    if(!map_mmap(p, r_stval())) {
        printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
        printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
        p->killed = 1;
    }
} else {
// ...
  • 因为头文件的包含问题，我们把 map_mmap() 的实现放在了 kernel/sysfile.c 里面
  • kernel/defs.h 里添加函数声明
1
2
3
// kernel/defs.h
// sysfile.c
int map_mmap(struct proc*, uint64);
  • kernel/sysfile.c 中添加实现
    • 遍历 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
32
33
34
35
36
37
38
39
40
41
42
43
// kernel/sysfile.c
// 1 成功, 0 失败
int map_mmap(struct proc *p, uint64 addr) {
    // 遍历 vma 找到具体的文件
    for(int i = 0; i < MAXVMA; ++i) {
        struct VMA* v = &(p->vma[i]);
        // 左闭右开
        if(v->length != 0 && addr < v->end && addr >= v->start) {
            uint64 start = PGROUNDDOWN(addr);
            // uint64 end = PGROUNDUP(addr);
            // 可能释放了一部分, 但是后面部分没有建立映射(offset)
            uint64 offset = start - v->start + v->offset;

            // 申请一块空间
            char* mem = kalloc();
            if(!mem) {
                return 0;
            }
            memset(mem, 0, PGSIZE);

            // PROT_NONE       0x0   PTE_V (1L << 0)
            // PROT_READ       0x1   PTE_R (1L << 1)
            // PROT_WRITE      0x2   PTE_W (1L << 2)
            // PROT_EXEC       0x4   PTE_X (1L << 3)
            //                       PTE_U (1L << 4)
            // 建立映射关系
            if(mappages(p->pagetable, start, PGSIZE,
                        (uint64)mem, (v->prot<<1)|PTE_U) != 0
              ){
                kfree(mem);
                return 0;
            }

            // 读取文件
            ilock(v->file->ip);
            // 1 表示虚拟地址
            readi(v->file->ip, 1, start, offset, PGSIZE);
            iunlock(v->file->ip);
            return 1;
        }
    }
    return 0;
}

(5) munmap

  • 遍历 VMA，找到对应的映射
  • 判断是否是从 start 开始释放，如果是，接着判断是否需要释放整个文件
    • 注意如果要释放只做标记，之后再释放，否则会出问题（不能提前释放文件）
  • 如果是 MAP_SHARED，则在释放之前需要进行写操作
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
// kernel/sysfile.c
uint64 sys_munmap(void) {
  uint64 addr;
  int length;
  // 获取参数
  if(argaddr(0, &addr) < 0 || argint(1, &length) < 0)
    return -1;
  struct proc* p = myproc();
  for(int i = 0; i < MAXVMA; ++i) {
    struct VMA* v = &(p->vma[i]);
    // 左闭右开
    if(v->length != 0 && addr < v->end && addr >= v->start) {
      int should_close = 0;
      int offset = v->offset;
      addr = PGROUNDDOWN(addr);
      length = PGROUNDUP(length);
      // 是否从 start 开始
      if(addr == v->start) {
        // 是否释放整个文件
        if(length == v->length) {
          v->length = 0;
          // 不能在这个时候释放, 得在写回之后
          should_close = 1;
        } else {
          v->start += length;
          v->length -= length;
          v->offset += length;
        }
      } else {
        // 根据要求这个时候只能是释放到结尾
        v->length -= length;
      }
      // 处理 MAP_SHARED
      if(v->flags & MAP_SHARED) {
        // 一种简单的实现就是直接把整个文件写回去
        // !!!!(不行, 可能现在的映射已经不是整个文件)
        filewrite_offset(v->file, addr, length, offset);
      }
      // 解除映射
      // 这里还有些问题, 可能并没有映射
      // if(walkaddr(p->pagetable, addr) != 0)
      uvmunmap(p->pagetable, addr, length/PGSIZE, 1);
      if(should_close)
        fileclose(v->file);
    }
  }
  return 0;
}
  • 和 filewrite() 一样的实现，只是增加一个文件的 offset
    • 我们只实现了 FINODE 的写操作
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
// kernel/sysfile.c
// Write to file f.
// addr is a user virtual address.
// 支持 offset
// 我们只进行 FINODE 的写操作
// n 表示写的字节数
int
    filewrite_offset(struct file *f, uint64 addr, int n, int offset) {
    int r, ret = 0;
    if(f->writable == 0)
        return -1;
    if(f->type != FD_INODE) {
        panic("filewrite: only FINODE implemented!");
    }

    int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;
    int i = 0;
    while(i < n) {
        int n1 = n - i;
        if(n1 > max)
            n1 = max;

        begin_op();
        ilock(f->ip);
        if ((r = writei(f->ip, 1, addr + i, offset, n1)) > 0)
            offset += r;
        iunlock(f->ip);
        end_op();

        if(r != n1) {
            break;
        }
        i += r;
    }
    ret = (i == n ? n : -1);
    return ret;
}

(6) 其他细节

  • 在 exit() 退出的时候，需要释放映射的文件区域
    • 注意文件计数需要+1
1
2
3
4
5
6
7
8
9
10
// kernel/proc/c:exit()
// ...
for(int i = 0; i < MAXVMA; i++) {
    struct VMA *v = &(p->vma[i]);
    if(v->length != 0){
        uvmunmap(p->pagetable, v->start, v->length/PGSIZE, 1);
        v->length = 0;
    }
}
// ...
  • 在 fork 的时候，将父进程的映射内容拷贝到子进程
    • 注意文件计数需要+1
1
2
3
4
5
6
7
8
9
10
11
12
// kernel/proc/c:fork()
// ...
// VMA
for(int i = 0; i < MAXVMA; ++i) {
    if(p->vma[i].length) {
        memmove(&(np->vma[i]), &(p->vma[i]), sizeof(struct VMA));
        filedup(p->vma[i].file);
    } else {
        np->vma[i].length = 0;
    }
}
// ...
  • 因为 lazy 分配的原因，我们需要做一些特殊处理
  • uvmunmap()
    • 如果没有建立映射，则不需要释放
    • 如果建立了映射，但是没有读入内存，则不需要调用 kfree()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// kernel/vm.c:uvmunmap()
// ...
for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0) continue;
    //   panic("uvmunmap: walk");
    // if((*pte & PTE_V) == 0)
    //   panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
        panic("uvmunmap: not a leaf");
    if(do_free && (*pte & PTE_V) != 0){
        uint64 pa = PTE2PA(*pte);
        kfree((void*)pa);
    }
    *pte = 0;
}
// ...

  • uvmcopy()
    • 如果尚未分配物理页，这是允许的
1
2
3
4
5
6
7
8
9
// kernel/vm.c:uvmcopy()

// 原始代码
if((*pte & PTE_V) == 0)
    panic("uvmcopy: page not present");

// 修改后的代码
if((*pte & PTE_V) == 0)
    continue;

3. 实验结果

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
== Test running mmaptest ==
$ make qemu-gdb
(23.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 (272.3s)
== Test time ==
time: OK
Score: 140/140

4. 遇到的困难以及收获

  • 这个 lab 做起来很舒服，一方面提示给得很完整，另一方面我对文件系统的理解也更加深入了
    • 这个 lab 可以说是 lab4-lazy 的延伸，lazy 机制缺失在很多地方都很有用
  • 做完这个 lab，感觉自己对 xv6 -riscv 文件系统了解更深入了

5. 对课程或 lab 的意见和建议

  • 建议提供一些关于 lab 的 debug 功能的指导

6. 参考文献

  • https://pdos.csail.mit.edu/6.828/2019/xv6/book-riscv-rev1.pdf