MIT 6.S081入门lab10 mmap
一、参考资料阅读与总结
1.Journaling the Linux ext2fs Filesystem
- 文件系统可靠性： 磁盘崩溃前数据的稳定性；故障模式的可预测性；操作的原子性
-论文核心： 将日志事务系统加入Linux的文件系统中； - 事务系统的要求： 元数据的更新；事务系统的顺序性；数据块写入磁盘的同一性（即保证之前的事务都完成了写入）
- 文件系统相对于数据库系统的不同点： 没有事务终止；事务生命周期较短
- 复合事务： （组提交）
- 日志内容： 元数据；描述符；头标记块
- 检查点设置： 创建新事务；刷新磁盘；等待文件系统完成操作；写入日志；提交磁盘；释放日志
- 事务提交时文件系统的更新机制： 由于提交事务和文件系统更新是异步的，因此存在事务-文件系统的冲突提交问题，即新文件系统需要对正在提交的事务进行操作;解决方法是使用副本，保证刷新的一致性
- 未来工作： 压缩日志更新；快速NFS支持
2. Virtual memory for applications
- 核心动机： 用户级的程序是否能够和os一样，使用虚拟内存，即响应缺页错误
- 需要的原语： Trap；Prot1和Unprot（访问权限）；ProtN（批量操作节省TLB刷新）；Dirty（脏页标记）；Map2（多对一映射）；
- 现有机制： mmap和unmap（文件映射）；mprotect（权限保护）；sigaction（信号处理）
- 实现方式： 虚拟机制：pagetable + virtual memory area；陷阱：User-level traps
二、涉及函数
- 整体xv6的函数已经基本介绍完成，请参考之前的实现
三、课程视频观看笔记（lec16/lec17）
lec16
= 日志系统的广泛应用： 数据库，操作系统等，其主要目的是实现存储的崩溃恢复；
- xv6日志系统回顾： begin_op() -> end_op() -> bcache buffer -> log -> loc(写入header头) -> write
- 预写规则： 先写入更新到日志，再更新（更新的原子性的保证）；
- 释放规则： 只有在日志中所有内容被完全写入相对应的数据块中时，其日志缓存才能被释放；
- xv6方案的问题： 速度缓慢， end_op()d的系统调用只能同步的发生，同时，每个块写入两次（日志+数据块）
- ext3方案： 对无日志系统的修改升级（ext2） ，内存中：cache；事务块编号；硬件中：目录树+log
主要区别，其能够同时进行多事务的提交和运行 - ext3的日志系统：日志超级快（第一个有效事务的偏移量+序列号）+ 事务（块编号+块事务+提交块）...+ 事务块；
- 细节： 描述符以魔数开始
- ext3高性能核心： 异步系统调用；批处理；并发
- 异步系统调用：
即系统调用只到缓存更新，其可以允许I/O复用，同时能更好的实现批处理
风险：崩溃可能导致数据的丢失 -> fsync调用保证及时写入（数据敏感应用） - 批处理：
在任何时候，ext3中存在打开的一个大型的系统调用，在固定时间更新这个大的系统调用，从而实现批处理；
允许写吸收（便于大型和重复系统调用，减少系统调用）；
便于磁盘调度（顺序写 + 便于磁盘系统调用） - 并发：
允许多个系统调用并行： 由于系统调用是异步的，因此不必等待I/O完成
允许多个日志事务（状态）存在: 提交中事务，写入事务，打开中事务等事务的不同状态共存，使用了COW策略实现了副本之间的复用
- 异步系统调用：
- 源码结构：
- 系统调用：开始并获取事务句柄-> 获取buffer -> 对buffer进行操作 -> 关闭事务句柄
- 提交事务（内核后台线程实现）： 阻塞新系统调用 -> 等待未完成系统调用 -> 打开新系统调用 -> 写入旧事务的描述符块入日志（元数据）-> 写入旧事务的数据入日志 -> 等待写入日志完成 -> 提交日志 -> 等待提交完成 -> (存档) -> 写入数据 ->复用日志
为了预防死锁，系统调用需要实现事先声明大小； - 事务组成结构： 日志超级快 + 事务块，超级块指向了最旧事务的提交块
- 日志恢复流程： 从超级块恢复最旧事务指针->通过事务的元数据（描述符块）确定事务的结尾(通过魔术数实现对描述符块和数据块，同时在数据块中通过以全0置换魔术数的方式保证魔术数的唯一性)
- ext3在提交事务中阻塞新系统调用，并等待旧系统调用的原因： 避免新系统调用造成的对旧系统调用的影响，这会导致崩溃时候的原子性的破坏
- 日志核心： 预写规则保证了多步提交的原子性
- 日志加速： 不将数据写入日志，只写入元数据 -> 可能导致隔离性的损失 -> 通过调整写入顺序解决，即先写入数据，之后写入日志，然后提交。
lec17
- 应用程序的虚拟内存： OS使用虚拟内存提升了性能；用户程序是否可以实现同样类似的机制
- 原语需求： trap（陷阱）； prot1/unprot/protN（权限+节省TLB刷新）；Dirty(脏页)；map2（多对一映射）
- 现代unix实现：
- mmap机制（mmap和unmap）： 位置，长度，权限位，映射地址，文件描述符，offset等：map2
- mprotect： 调整权限：prot1/unprot/protN
- signaction： 信号处理程序（segfault机制）：trap
- 虚拟实现： 页表 + 虚拟内存区域（权限）
- 用户级别的trap： 类似于sigalarm，进入内核->将事件处理程序放入用户空间 -> 进入内核 -> 恢复；（由于mmu页表的隔离，因此依旧保证了隔离）
- 例：
- 庞大计算表（大于内存）： 使用vm原语，实现cow，即访问到f(i) 后触发页面错误，现场计算之后存入表；同时，如果占用内存太大，根据策略清理相应表
- 垃圾收集器：
复制垃圾收集器：将堆分为两部分，from和to，首先从to分配内存，
在to区域满后，翻转from和to区域，
在from中根据其根指针确定有效内存，并在to中申请新的内存并复制（根指针和数据），
之后丢弃from区域中的数据，使其成为空闲区域
原始方法是利用scan和unsacned指针判定其在from区域还是to区域，从而确认位置，一次转移位置（阻塞） - Baker算法： 实时+增量：类似于COW，只保存root指针，只有在调用new时再转移，同时，在取消引用时，检查其是否在from区域，如果在，则进行复制（均摊操作）
- 利用用户级别的原语，利用页面错误，将to区域设置为none（保护），实现检查和转发（复制）-> 将指针检查转移为硬件操作，同时简化了并行性
同时利用收集器和app的双重映射（不同权限）来保证收集器可以实现对unsacned区域的读写
- 现代操作系统： 5级页表+内核页表隔离 +ASID 等，其是不断变化的
四、完成lab及其代码
-
系统调用+修改Makefile
Makefile
... UPROGS=\ ... $U/_mmaptest\user/usys.pl
... entry("mmap"); entry("munmap");user/user.h
// system calls ... void *mmap(void *, uint64 , int, int, int, uint64); int munmap(void *, uint64);kernel/syscall.h
... #define SYS_mmap 22 #define SYS_munmap 23kernel/syscall.c
... extern uint64 sys_mmap(void); extern uint64 sys_munmap(void); static uint64 (*syscalls[])(void) = { ... [SYS_mmap] sys_mmap, [SYS_munmap] sys_munmap, }; -
定义常量
kernel/def.h
... struct vma; ... // syscall.c ... int vmatrylazyalloc(uint64); ... // vm.c ... void uvmaunmap(pagetable_t, uint64, uint64, struct vma *); ...kernel/memlayout.h
... #define MMAPEND TRAPFRAME //start bottomkernel/param.h
... #define NVMA 16// Number of Virtual memory areas stackkernel/riscv.h
... #define PTE_D (1L << 7) // dirty -
定义结构体
kernel/proc.h
... //virtual memory areas struct vma { int valid; // is use? uint64 vastart; uint64 sz; int prot; int flags; struct file *f; uint64 offset; }; // Per-process state struct proc { ... struct vma vmas[NVMA]; // Virtual memory areas }; -
核心实现：mmap，unmmap的实现+lazyalloc的实现
kernel/sysfile.h
... #include "memlayout.h" ... uint64 sys_mmap(void) { // printf("sys_mmap enter\n"); uint64 addr, sz, offset; uint64 vmaend = MMAPEND; int i; int prot, flags, fd; struct file *f; struct proc *p = myproc(); struct vma *vmaBuff = 0; if (argaddr(0, &addr) < 0 || argaddr(1, &sz) < 0 || argint(2, &prot) < 0 || argint(3, &flags) < 0 || argfd(4, &fd, &f) < 0 || argaddr(5, &offset) < 0 || sz == 0) { //j传参检查 return -1; } //合法性检查 if (((!f->readable) && (prot & (PROT_READ))) || ((!f->writable) && (prot & (PROT_WRITE)) && !(flags & MAP_PRIVATE))) { return -1; } //分配地址（实现addr == 0的情况） sz = PGROUNDUP(sz); for (i = 0; i < NVMA; i++) { if(p->vmas[i].valid == 0) { if(vmaBuff == 0) { vmaBuff = &p->vmas[i]; vmaBuff->valid = 1; } } else if (p->vmas[i].vastart < vmaend) { vmaend = PGROUNDDOWN(p->vmas[i].vastart); } } //初始化 if (vmaBuff != 0) { vmaBuff->vastart = vmaend - sz; vmaBuff->sz = sz; vmaBuff->prot = prot; vmaBuff->flags = flags; vmaBuff->f = f; vmaBuff->offset = offset; filedup(vmaBuff->f); return vmaBuff->vastart; } printf("mmap: no free vma\n"); return -1; } struct vma * vmaMap(struct proc *p, uint64 va) { //寻找va所对应的vmas结构体 int i; for (i = 0; i < NVMA; i++) { if ((p->vmas[i].valid == 1) && (va >= p->vmas[i].vastart) && (va < (p->vmas[i].vastart + p->vmas[i].sz))) { return &p->vmas[i]; } } return 0; } uint64 sys_munmap(void) { uint64 addr, sz; // int nummap; struct vma *vmaBuff = 0; struct proc *p = myproc(); // printf("sys_munmap enter\n"); if (argaddr(0, &addr) < 0|| argaddr(1, &sz) < 0 || sz == 0) { return -1; } //检查传入参数 //合法性检查 if ((vmaBuff = vmaMap(p, addr)) == 0) { return -1; } if ((addr > vmaBuff->vastart) && (addr + sz < vmaBuff->vastart +vmaBuff->sz) ) { return -1; } //如果不准确释放会出现内存丢失或者重复释放 uint64 addrAligned = addr; if (addr > vmaBuff->vastart) { addrAligned = PGROUNDUP(addr); } uint64 nummap = sz - (addrAligned - addr); // 为什么呢？ printf("nummap: %d", nummap); if(nummap < 0) nummap = 0; uvmaunmap(p->pagetable, addrAligned, nummap,vmaBuff); if(addr <= vmaBuff->vastart && addr + sz > vmaBuff->vastart) { vmaBuff->offset += addr + sz - vmaBuff->vastart; vmaBuff->vastart = addr + sz; } vmaBuff->sz -= sz; if(vmaBuff->sz <= 0) { fileclose(vmaBuff->f); vmaBuff->valid = 0; } return 0; } int vmatrylazyalloc(uint64 va) { struct proc *p = myproc(); struct vma *vmaBuff; void *pa; int perm = PTE_U; if ((vmaBuff = vmaMap(p, va)) == 0) { return -1; }//找到vma if ((pa = kalloc()) == 0) { panic("vmatrylazyalloc:kalloc"); } //分配内存 va = PGROUNDDOWN(va); memset(pa, 0, PGSIZE); //读取文件映射到内存 begin_op(); ilock(vmaBuff->f->ip); if(readi(vmaBuff->f->ip, 0, (uint64)pa, vmaBuff->offset + PGROUNDDOWN(va - vmaBuff->vastart), PGSIZE) < 0) { panic("vmatrylazyalloc:readi"); } iunlock(vmaBuff->f->ip); end_op(); // printf("vmatrylazyalloc:op\n"); //用户状态位和内核状态位置的转换 if (vmaBuff->prot & PROT_READ) { perm |= PTE_R; } if (vmaBuff->prot & PROT_WRITE) { perm |= PTE_W; } if (vmaBuff->prot & PROT_EXEC) { perm |= PTE_X; } // printf("vmatrylazyalloc:mappages"); if(mappages(p->pagetable, va, PGSIZE, (uint64)pa, perm) < 0) { panic("vmatrylazyalloc:mappages"); } return 0; }kernel/trap.c
... void usertrap(void) { ... } else if((which_dev = devintr()) != 0){ // ok } else if(r_scause() == 13 || r_scause () == 15){ if(vmatrylazyalloc(r_stval()) != 0) { 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 {kernel/vm.c
... #include "fcntl.h" #include "spinlock.h" #include "sleeplock.h" #include "file.h" #include "proc.h" ... void uvmaunmap(pagetable_t pagetable, uint64 va, uint64 nbytes, struct vma *v) { uint64 a; pte_t *pte; for(a = va; a < va + nbytes; a += PGSIZE){ if((pte = walk(pagetable, a, 0)) == 0) panic("uvmaunmap: walk"); if(PTE_FLAGS(*pte) == PTE_V) panic("uvmunmap: not a leaf"); if(*pte & PTE_V) { uint64 pa = PTE2PA(*pte); if ((*pte & PTE_D) && (v->flags & MAP_SHARED)) { begin_op(); ilock(v->f->ip); uint64 aoffset = a - v->vastart; if (aoffset < 0) { writei(v->f->ip, 0, pa + (- aoffset), v->offset, PGSIZE + aoffset); } else if (aoffset + PGSIZE > v->sz) { writei(v->f->ip, 0, pa, v->offset + aoffset, v->sz - aoffset); } else { writei(v->f->ip, 0, pa, v->offset + aoffset, PGSIZE); } iunlock(v->f->ip); end_op(); } kfree((void*) pa); *pte = 0; } } } -
proc相应函数修改
kernel/pro.c
static struct proc* allocproc(void) { ... found: ... //clear VMAs for (int i = 0; i < NVMA; i++) { p->vmas[i].valid = 0; } return p; } // free a proc structure and the data hanging from it, // including user pages. // p->lock must be held. static void freeproc(struct proc *p) { if(p->trapframe) kfree((void*)p->trapframe); p->trapframe = 0; for (int i = 0; i < NVMA; i++) { if(p->vmas[i].valid) { uvmaunmap(p->pagetable, p->vmas[i].vastart, p->vmas[i].sz,&p->vmas[i]); } } if(p->pagetable) proc_freepagetable(p->pagetable, p->sz); ... } ... // Create a new process, copying the parent. // Sets up child kernel stack to return as if from fork() system call. int fork(void) { ... for(i = 0; i < NVMA; i++) { struct vma *v = &p->vmas[i]; if(v->valid) { np->vmas[i] = *v; filedup(v->f); } } ... }
参考文献
「研读笔记」MIT 6.S081 Paper Virtual Memory Primitives for User Programs：https://zhuanlan.zhihu.com/p/610704237
Baker's garbage collection笔记：https://www.zhihu.com/column/c_1487476999569006592
2020版xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
28天速通MIT 6.S081操作系统公开课：https://zhuanlan.zhihu.com/p/630222721
MIT6.s081操作系统笔记：https://juejin.cn/post/7022347989683273765