Lab 10 mmap
1. LAB 基本
LAB的做法网路上很多，有困难的小伙伴可以参考这篇：https://blog.csdn.net/LostUnravel/article/details/121437327
我重点会介绍如何实现optional challenge
2. If two processes have the same file mmap-ed (as in fork_test), share their physical pages. You will need reference counts on physical pages.
根据LAB的基本要求里的HINT，它提到：
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.
也就意味着，原版本的实现，父进程和子进程会分贝各自创建自己的物理页。实际的结果是2页并没有共享。那么父子进程的写，并未相互可见。所以当实现了这个OC之后，理论上子进程改的东西可以立刻被父进程看到，那么就实现了进程间的数据交流。
我们先从一个测试用例开始, 去验证这个OC做完后的效果
void
shared_test(void)
{
int fd;
int pid;
const char * const f = "mmap.dur";
printf("shared_test starting\n");
testname = "shared_test";
makefile(f);
if ((fd = open(f, O_RDWR)) == -1)
err("open (7)");
char *p1 = mmap(0, PGSIZE*2, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
if (p1 == MAP_FAILED)
err("mmap (7)");
if (close(fd) == -1)
err("close (7)");
if((pid = fork()) < 0)
err("fork");
if (pid == 0) {
for (int i = 0; i < PGSIZE; i++)
while (p1[i] != 'B') sleep(0);
for (int i = PGSIZE; i < 2 * PGSIZE; i++)
p1[i] = 'C';
exit(0);
} else {
for (int i = 0; i < PGSIZE; i++)
p1[i] = 'B';
for (int i = PGSIZE; i < 2 * PGSIZE; i++)
while (p1[i] != 'C') sleep(0);
}
int status = -1;
wait(&status);
if(status != 0){
printf("shared_test failed\n");
exit(1);
}
if (munmap(p1, 2 * PGSIZE) == -1)
err("munmap (7)");
if ((fd = open(f, O_RDONLY)) == -1)
err("open (7)");
for (int i = 0; i < PGSIZE; i++){
char b;
if (read(fd, &b, 1) != 1)
err("read (1)");
if (b != 'B')
err("1 file does not contain modifications");
}
for (int i = PGSIZE; i < 2*PGSIZE; i++){
char b;
if (read(fd, &b, 1) != 1)
err("read (1)");
if (b != 'C')
err("2 file does not contain modifications");
}
printf("shared_test OK\n");
}
上面的代码思路大概就是，mmap之后再FORK， 父进程可以看到子进程的写，子进程可以看到父进程的读。
然后就是怎么实现 ，其实我们看第二个OC的要求，第二个OC的要求其实包含了第一个，他是更进一步。因为在把文件加载到bcache的时候，已经用了一个物理页去存了，那么我们可以让父进程，子进程和文件系统的bcache 3个共享同一个物理页，是最节约的做法。
那么我们就直接入手第二个OC TASK
3. Your solution probably allocates a new physical page for each page read from the mmap-ed file, even though the data is also in kernel memory in the buffer cache. Modify your implementation to use that physical memory, instead of allocating a new page. This requires that file blocks be the same size as pages (set BSIZE to 4096). You will need to pin mmap-ed blocks into the buffer cache. You will need worry about reference counts.
在做这个OC的时候，我提前把直接做完的LAB 5的改动给git cherry pick 过来了。
1708139470341.png
step 1. 调整BSIZE
我们需要把BSIZE 给从1024 改到4096，这样是为了缓存对齐内存页的大小。但是直接改数组的方式会报如下的错：
首先有些测试会不通过，原因是它在栈上开了一个BSIZE大的数组，但是栈的空间只有一个PGSIZE，当BSIZE==PGSIZE，就会爆栈。所以需要改一下相关测试代码：
1708141497492.png
在mmaptest里，因为n = PGSIZE/BSIZE, 所以write 1.5 page的代码逻辑会在整数除法 n/2 时失效。所以我们需要补上一段逻辑if (n %2)
//
// create a file to be mapped, containing
// 1.5 pages of 'A' and half a page of zeros.
//
void
makefile(const char *f)
{
int i;
int n = PGSIZE/BSIZE;
unlink(f);
int fd = open(f, O_WRONLY | O_CREATE);
if (fd == -1)
err("open");
memset(buf, 'A', BSIZE);
// write 1.5 page
for (i = 0; i < n + n/2; i++) {
if (write(fd, buf, BSIZE) != BSIZE)
err("write 0 makefile");
}
if (n % 2) {
if (write(fd, buf, BSIZE/2) != BSIZE/2)
err("write 1 makefile");
}
if (close(fd) == -1)
err("close");
}
把测试改对之后，依然会报错
mismatch at 0, wanted 'A', got 0x0
mmaptest: mmap_test failed: v1 mismatch (1), pid=3
原因是因为，如果我们直接改数组的大小的方式，那bcache-> data 的地址并不是页对齐的，我们在做mappages 会默认传进去的pa是页对齐的，然后用最后的10位转成PTE，恢复的时候，默认最后12位是0。
所以我们需要用kalloc 去处理b->data
1708141701615.png
1708141716237.png
step 2. 修改mmap
原先我们在page fault时，如果落在VMA的区域里，会直接alloc 一个新的物理页，我们现在需要改变这段逻辑，让它复用bcache 里已经创建出来用作cache的物理页。
- 首先判断如果是
MAP_PRIVATE，那么不应该复用。
2.如果不是private，我们要根据inode和offset找到对应的buf，然后用buf->data的地址 当作mem(physical address)，同时要增加buf的refcnt，可以用bpin的方式去维护。 - 然后把虚拟地址，映射现在page fault的
va(virtual address)，当这个mem上 - 这边如果要释放，我们应该
bunpin而不是kfree
具体代码：
int vma_handle(struct proc *p, uint64 va) {
if (va > MAXVA) return -1;
va = PGROUNDDOWN(va);
pte_t *pte = walk(p->pagetable, va, 0);
if (pte && (*pte & PTE_PG)) {
return pagein(pte);
}
for (int i = 0; i < MAX_VMA; i++) {
struct vma *vma = &p->vm_areas[i];
if (!vma->used || vma->addr > va || va >= vma->addr + vma->length) continue;
uint64 mem = 0;
int private = (vma->flags & MAP_PRIVATE);
if (private) {
// Allocate a new page if private
char *tmp;
if ((tmp = kalloc()) == 0) return -1;
memset(tmp, 0, PGSIZE);
mem = (uint64) tmp;
}
// Read file content into the new page
struct inode *ip = vma->ip;
if (ip) {
idup(ip);
ilock(ip);
if (private) {
int n;
int sz = vma->addr + vma->filesz - va;
if(sz < PGSIZE)
n = sz;
else
n = PGSIZE;
if (readi(ip, 0, (uint64)mem, vma->offset + va - vma->addr, n) < 0) {
iunlockput(ip);
kfree((void *)mem);
return -1;
}
} else if (!(mem = readblock(ip, vma->offset + va - vma->addr))) {
iunlockput(ip);
return -1;
}
iunlockput(ip);
}
// printf("%d %d %p %d\n", p->pid, mycpu()->noff, va, vma->type);
if (!mem) panic("vma_handle");
// Map the new page at the faulting address
int perm = PTE_U;
if(vma->prot & PROT_READ)
perm |= PTE_R;
if(vma->prot & PROT_WRITE)
perm |= PTE_W;
if(vma->prot & PROT_EXEC)
perm |= PTE_X;
if(mappages(p->pagetable, va, PGSIZE, mem, perm) != 0){
if (private) kfree((void *)mem);
else if (vma->file) bunpin2(mem);
return -1;
}
return 0; // Page fault handled successfully
}
return -1; // No corresponding VMA found, or other error
}
因为传统的bunpin 是传进去struct buf *b, 这里我们只有addr, 所以我自己写了一个bunpin2
void
bunpin2(uint64 addr)
{
struct buf *b;
for(b = bcache.buf; b < bcache.buf+NBUF; b++){
if ((uint64)b->data == addr) {
bunpin(b);
return;
}
}
panic("bunpin2");
}
下面我们需要一个根据IP 和 off 找到对应的文件位置的buf, 对它进行bpin, 随后返回bp->data的方法
uint64
readblock(struct inode *ip, uint off)
{
if (off % BSIZE) panic("readblock");
if(off >= ip->size)
return 0;
struct buf *bp;
uint addr = bmap(ip, off/BSIZE);
bp = bread(ip->dev, addr);
bpin(bp);
brelse(bp);
return (uint64) bp->data;
}
随后我们做进程清理的时候，我们也需要让uvmunmap 知道应该是调用bunpin2还是kfree. 所以我们需要额外加一个参数在do_free
1708143079706.png
1708143212141.png
综上我们就完成了OC 1 & 2
4. Remove redundancy between your implementation for lazy allocation and your implementation of mmap-ed files. (Hint: create a VMA for the lazy allocation area.)
这块的实现，就是我们现在的内存区域既有HEAP的静态增长区域， 又有mmap 出来的动态区域vma。我们可以把2者统一起来。
也就是把heap 区域，也当作一个VMA，这样lazy alloc 也可以复用vma 的page fault 去实现。
这里为了解决内存碎片的问题。我把VMA区域分成2块，指定地址的为静态的，开了8个VMA的空间，不指定地址的为动态，也开了8个VMA空间。那么HEAP可以放在静态区域。动态区域地址从大往小走。HEAP拓展从小往大走。如果mmap指定地址，那么放在静态空间。
// proc.h
enum vmatype {EXEC,HEAP,FIX,DYNAMIC};
#define MAX_DYN_VMA 8
#define MAX_FIX_VMA 8
#define FIX_START_ADDR MAX_DYN_VMA
#define MAX_VMA MAX_DYN_VMA + MAX_FIX_VMA
struct vma {
int used;
uint64 addr; // VMA start address
uint64 length; // mapping length
int prot; // permission mark
int flags; // MAP_SHARED or MAP_PRIVATE
struct file *file; // related file
struct inode *ip; // related file ip
uint64 offset; // Offset in the file
uint64 filesz; // related file size
enum vmatype type;
};
uint64
sys_mmap(void)
{
int fd;
uint64 addr;
int length;
int prot;
int flags;
int offset;
argaddr(0, &addr);
argint(1, &length);
argint(2, &prot);
argint(3, &flags);
argint(4, &fd);
argint(5, &offset);
struct file *f = myproc()->ofile[fd];
return vma_create(addr, length, prot, flags, f, f->ip, offset, length, addr == 0 ? DYNAMIC : FIX);
}
那么在检查space是否充足的时候，静态区域要每个都判断无交集，动态区域，我们知道地址是排序的，所以可以提前退出。
代码改动如下：
int space_enough(struct proc *p, int n)
{
if (p->sz + n < 0) return 0;
for (int i = 0; i < MAX_FIX_VMA; i++) {
int j = FIX_START_ADDR + i;
if (!p->vm_areas[j].used || p->vm_areas[j].type == HEAP) continue;
uint64 addr = p->sz + n;
if (p->vm_areas[j].addr <= addr && addr < p->vm_areas[j].addr + p->vm_areas[j].length) return 0;
}
for (int i = MAX_DYN_VMA - 1; i >= 0; i--) {
if (!p->vm_areas[i].used) continue;
if (p->sz + n > p->vm_areas[i].addr) return 0;
break;
}
return p->sz + n <= TRAPFRAME;
}
uint64 update_heap_vma(struct proc *p, uint64 addr, int n)
{
if (vma_create(addr, n, PROT_READ | PROT_WRITE, MAP_PRIVATE, 0, 0, 0, 0, HEAP) < 0) return -1;
p->sz += n;
return addr;
}
uint64 vma_sbrk(struct proc *p, int n)
{
uint64 addr = p->sz;
if (!space_enough(p, n)) {
return -1;
}
if(n < 0){
uvmdealloc(p->pagetable, p->sz, p->sz + n);
} else {
saved_page((PGROUNDUP(p->sz + n) - PGROUNDUP(p->sz)) / PGSIZE);
}
update_heap_vma(p, addr, n);
return addr;
}
vma_create 代码 取代原来的mmap_create
uint64 vma_create(uint64 addr, size_t len, int prot, int flags, struct file *f, struct inode *ip, off_t offset, size_t filesz, enum vmatype type)
{
if(f && ((!f->readable && (prot & (PROT_READ)))
|| (!f->writable && (prot & PROT_WRITE) && !(flags & MAP_PRIVATE))))
return -1;
struct proc *p = myproc();
if (type == DYNAMIC) {
uint64 end = PGROUNDDOWN(TRAPFRAME); // Start searching from address below TRAPFRAME
for (int i = 0; i < MAX_DYN_VMA; ) {
if (p->vm_areas[i].used) {
end = p->vm_areas[i].addr;
i++;
continue;
}
int j = i + 1;
for (; j < MAX_DYN_VMA; j++) {
if (p->vm_areas[j].used) break;
}
int next_end = (j == MAX_DYN_VMA) ? PGROUNDUP(p->sz) : PGROUNDUP(p->vm_areas[j].addr + p->vm_areas[j].length);
if (end - next_end >= len) {
return setup_vma(p, i, PGROUNDDOWN(end - len), len, prot, flags, f, ip, offset, filesz, type);
}
i = j;
}
} else if (type == HEAP) {
int empty = -1;
for (int i = 0; i < MAX_FIX_VMA; i++) {
int j = FIX_START_ADDR + i;
struct vma *v = &p->vm_areas[j];
if (v->used && v->type == HEAP) {
if (addr != v->addr + v->length) panic("update_heap_vma");
v->length += len;
if (v->length <= 0) {
v->used = 0;
}
return addr;
} else if (!v->used && empty == -1) {
empty = j;
}
}
if (empty != -1 && len > 0) {
return setup_vma(p, empty, addr, len, prot, flags, f, ip, offset, filesz, type);
}
} else {
for (int i = 0; i < MAX_VMA; i++) {
if (!p->vm_areas[i].used) continue;
if (p->vm_areas[i].addr <= addr && addr < p->vm_areas[i].addr + p->vm_areas[i].length) {
return -1;
}
}
for (int i = 0; i < MAX_FIX_VMA; i++) {
int j = FIX_START_ADDR + i;
if (p->vm_areas[j].used) continue;
if (ip) idup(ip);
return setup_vma(p, j, addr, len, prot, flags, f, ip, offset, filesz, type);
}
}
return -1; // No space found
}
有了上面的工作，那么其实 lazy allocation 要做的事情，可以统一用vma_handle 去概括起来。因为HEAP 用的是MAP_PRIVATE, 并且没有传fd, inode； 所以就是直接开一页内存，然后mappages。
下面就把原来lazy_alloc的代码逻辑 同一用vma_handle 替换掉
1708144359633.png
1708144393922.png
5. Modify exec to use a VMA for different sections of the binary so that you get on-demand-paged executables. This will make starting programs faster, because exec will not have to read any data from the file system.
这块首先就是要理解exec 这个函数做了哪些事
- 首先它要创建一个新的pagetable，因为要抛弃掉fork 继承过来的旧pagetable
- 其次他会根据elf里的信息去读取要运行程序的代码段和数据段； 这部分就是我们可以用VMA 去延迟加载的部分
- 设置好栈
- 配置argument，以及相关寄存器使得main函数可以正确执行
- 最后就是释放掉之前FORK来的pagetable
这里面我们要修改的代码主要是这一段
uint64 sz1;
if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz, flags2perm(ph.flags))) == 0)
goto bad;
sz = sz1;
if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
goto bad;
但我们发现这和常规的mmap有一个不同之处。常规的mmap 一般memsz 就是filesz，但是这边出现了2个不同的变量，且是不同的值。
一般memsz 会比filesz大。
如果我们这边统一用memsz，我们就会要从文件里读取要执行的代码段的时候，多读进一些本来不是执行代码的数据，当作了执行代码，就会程序出错。
如果我们使用filesz，就会本来应该在vma管辖里的内存，没有被包含进来。比如这个空间本来是留给栈放一些临时变量，但是我们用了filesz，这个空间不再vma里，就直接page fault了。
同时还有一个难点是这里我们只能拿到inode， 我们不会再有fd 和 file结构，如果没有file这个结构，那么就没有天然维护好的offset，所以这里也只能我们自己维护住file里要读的offset；
综上，我们必须要要在vma的数据结构里做扩展。
1708147814580.png
然后上面的代码，我们可以这样改：
sz = ph.vaddr + ph.memsz;
// printf("exec %d %p %d %d %d %d\n", p->pid, ph.vaddr, ph.memsz, ph.off, ph.filesz, ph.flags);
if (vma_create(ph.vaddr, ph.memsz, flags2prot(ph.flags), MAP_PRIVATE, 0, (ph.filesz ? ip : 0), ph.off, ph.filesz, EXEC) < 0) {
goto bad;
}
这里我们为EXEC单独创建了一个vma_type；
是因为
在正常mmap时，我们 fork, 需要对文件的引用计数做增加通过filedup(np->vm_areas[i].file);
但是EXEC, 没有file, 我们得直接作用在inode上
所以会有如下代码：
void vma_fork(struct proc *p, struct proc *np) {
for (int i = 0; i < MAX_VMA; i++) {
np->vm_areas[i] = p->vm_areas[i];
if(!np->vm_areas[i].used) continue;
if(np->vm_areas[i].file) {
filedup(np->vm_areas[i].file);
}
if (np->vm_areas[i].type == EXEC) {
if (np->vm_areas[i].ip) idup(np->vm_areas[i].ip);
}
}
}
另外我们注意到，现在VMA里会存要执行的代码。所以当那些代码没执行到的时候，进行fork。他依然会存在在VMA里；这时如果执行EXEC，我们时需要把EXEC 和 HEAP的VMA都进行清理。不然遇到PAGE FAULT的时候，会发生错误的执行了FORK的父进程的EXEC代码。
void vma_exec_clear(struct proc *p) {
for (int i = FIX_START_ADDR; i < MAX_VMA; i++) {
if(!p->vm_areas[i].used) continue;
if (p->vm_areas[i].type == EXEC) {
if (p->vm_areas[i].ip) iput(p->vm_areas[i].ip);
p->vm_areas[i].used = 0;
} else if (p->vm_areas[i].type == HEAP) {
p->vm_areas[i].used = 0;
}
}
}
在进程退出，clean的时候，因为我们之前idup, 我们需要用iput 去撤回idup的效果。
类似于filedup 和 fileclose
void mmap_clean(struct proc *p)
{
for (int i = 0; i < MAX_VMA; i++) {
struct vma *v = &p->vm_areas[i];
if (!v->used) continue;
if (v->flags == MAP_SHARED && writeback(v->addr, v->length, p, v) < 0)
panic("mmap clean");
uvmunmap(p->pagetable, v->addr , PGROUNDUP(v->length)/PGSIZE, (v->flags & MAP_SHARED) ? FREE_BCACHE : 1);
v->used = 0;
if (v->file)
fileclose(v->file);
if (v->type == EXEC && v->ip)
iput(v->ip);
}
}
上面2个OC，是一些优化技巧，不需要额外测试；只需要确保原来的程序可以正常运转，就说明优化是正确的。不然系统会报错。
但是做了EXEC的优化后，原来usertests 测试会有一个问题。
就是countfree 会计算运行测试前的空闲内存页，和运行测试后的空闲内存页。如果2者不一致，就说明有内存泄漏。
但是EXEC这个优化后，因为运行测试前，大部分代码并没有走到，所以这时EXEC的VMA的物理页还没有被创建出来。
而运行测试后，所有代码被走到，EXEC的VMA会创建出物理页，延迟加载了要用的程序代码。
所以前者就是会比后者多出2页。这是正常的行为。
6. Implement page-out and page-in: have the kernel move some parts of processes to disk when physical memory is low. Then, page in the paged-out memory when the process references it.
这个问题其实比较大，要实现的很好是可以花非常多的功夫。我就是挑一些最基本的点实现了一下。
交换空间（Swapping Space）可以是固定大小的，也可以是动态的，这取决于你如何配置它。交换空间通常通过以下两种方式之一实现：
首先是交换分区应该怎么设计：
- 交换分区（Swap Partition）:
交换分区是硬盘上预先分配的特定分区，用作交换空间。
分区大小在创建时设定，因此它是固定大小的。
你可以在安装Linux时或之后使用分区工具创建交换分区。
你可以有多个交换分区。
- 交换文件（Swap File）:
交换文件是一个普通文件，可以在文件系统中的任何位置。
交换文件的大小可以在创建后调整，因此它可以是动态的。
交换文件可以在需要时创建，并且可以根据需要增加或减少它们的大小。
使用交换文件不需要专门的分区，可以更灵活地使用磁盘空间。
在这里我选择实现了第1种方案。所以我在创建文件系统开始时，就用了1024个BLOCK，用来当作交换分区。所以实际的物理内存会从原来的128MB 变为 132MB. （一个BLOCK时4KB）。
代码改动如下:
1708148963658.png
其次是如何选择牺牲页。我这边使用了老化算法，原因是比较好实现，效果也还不错，非常近似LRU。具体算法可以看这篇博客： https://juejin.cn/post/7024789733498683429#%E8%80%81%E5%8C%96%E7%AE%97%E6%B3%95
在选择牺牲页中，我们得考虑到因为我们实现了copy_on_write， 所以有些页可能是被多个进程引用的。那么释放这样的页，必须先恢复copy_on_write的标志，才能牺牲。所以得不偿失。所以在检查的时候，我会去check ref_cnt为1的page.
算法代码如下:
//proc.c
uint64
find_swapping_page(int *refcnt, struct spinlock* memlock)
{
struct proc *p;
pte_t *pte, *ret = 0;
uint8 minage = 255;
uint64 res;
acquire(memlock);
for(p = proc; p < &proc[NPROC]; p++){
acquire(&p->lock);
if((p->state == RUNNING || p->state == RUNNABLE || p->state == SLEEPING) && (p->pid > 2))
{
for(int a = 0; a < p->sz; a += PGSIZE){
if((pte = walk(p->pagetable, a, 0)) == 0)
continue;
if((*pte & PTE_V) == 0)
continue;
if(*pte & PTE_COW)
continue;
if(PTE_FLAGS(*pte) == PTE_V)
panic("find_nfup_proc: not a leaf");
uint8 age = pageage(pte);
if (age < minage && refcnt[COW_REFIDX(PTE2PA(*pte))] == 1) {
minage = age;
ret = pte;
}
if (minage == 0) break;
}
}
release(&p->lock);
}
if (ret == 0) {
release(memlock);
return 0;
}
int idx = COW_REFIDX(PTE2PA(*ret));
int old_ref_cnt = refcnt[idx];
if (old_ref_cnt != 1) {
panic("find_swapping_page 2");
}
release(memlock);
res = pageout(ret);
if (res) {
acquire(memlock);
refcnt[idx] = 0;
release(memlock);
}
return res;
}
void update_page_age()
{
struct proc *p;
pte_t *pte;
for(p = proc; p < &proc[NPROC]; p++){
acquire(&p->lock);
if((p->state == RUNNING || p->state == RUNNABLE || p->state == SLEEPING) && (p->pid > 2))
{
for(int a = 0; a < p->sz; a += PGSIZE){
if((pte = walk(p->pagetable, a, 0)) == 0)
continue;
if((*pte & PTE_V) == 0)
continue;
pageage(pte);
}
}
release(&p->lock);
}
}
// trap.c
void
clockintr()
{
if (ticks % 10 == 0)
{
update_page_age();
}
acquire(&tickslock);
ticks++;
wakeup(&ticks);
release(&tickslock);
}
//swap.c
int swappg_refcnt[SWAP_SPACE_BLOCKS];
uint8 pg_age[PG_REFIDX(PHYSTOP)];
struct spinlock swaplock;
uint32 swapstart;
void initswap(int dev, struct superblock *sb) {
for (int i = 0; i < SWAP_SPACE_BLOCKS; i++) {
swappg_refcnt[i] = 0;
}
initlock(&swaplock, "swap");
for (int i = 0; i < PG_REFIDX(PHYSTOP); i++) pg_age[i] = 0;
swapstart = sb->swapstart;
}
uint8 pageage(pte_t *pte) {
uint64 pa = PTE2PA(*pte);
acquire(&swaplock);
uint8 age = pg_age[PG_REFIDX(pa)];
age >>= 1;
if (*pte & PTE_A) {
age |= (1 << 7);
*pte &= (~PTE_A);
}
pg_age[PG_REFIDX(pa)] = age;
release(&swaplock);
return age;
}
上面3块代码，主要完成了维护每一个内存页的age, 以及如何选择牺牲页的代码。
下面我们就是要实现，当物理页不够的时候，通过page-out 去获得一页新的物理页的逻辑。
可以得知直接感受到内存物理页不足的地方是当kalloc 失败的时候
1708149588500.png
然后我们找到了牺牲页，我们需要把这页存进我们的交换区域，然后设置对应的PTE_PG标志，同时取消PTE_V的标志，来触发page_fault.
// swap.c
uint64 pageout(pte_t *pte) {
uint64 pa = 0;
acquire(&swaplock);
for (int i = 0; i < SWAP_SPACE_BLOCKS; i++) {
if (swappg_refcnt[i] == 0) {
pa = PTE2PA(*pte);
swappg_refcnt[i] = 1;
*pte = PTE_PGOUT(i, PTE_FLAGS(*pte));
release(&swaplock);
struct buf *buf = bread(ROOTDEV, swapstart+i);
memmove(buf->data, (void *)pa, PGSIZE);
bwrite(buf);
brelse(buf);
acquire(&swaplock);
break;
}
}
release(&swaplock);
return pa;
}
1708157522647.png
然后我们需要实现pagein的逻辑，就是当trap 发生的时候，我们需要判断一下是不是因为由PTE_PG标志，如果是的话，说明在访问一个被pageout的界面。
同时我们要移除堆大小是否超过128M的检查，因为现在可以额外加上SWAP区域的内存了。
我们在VMA_HANDLE里考虑这种情况
1708157784278.png
下面是pagein的实现：
int pagein(pte_t *pte) {
int idx = (int)PTE2IDX(*pte);
uint64 mem = (uint64)kalloc();
if (mem == 0) return -1;
acquire(&swaplock);
if(swappg_refcnt[idx] <= 0) panic("pagein");
swappg_refcnt[idx]--;
release(&swaplock);
struct buf *buf = bread(ROOTDEV, swapstart + idx);
memmove((char *)mem, buf->data, PGSIZE);
*pte = PTE_PGIN(mem, PTE_FLAGS(*pte));
brelse(buf);
return 0;
}
最后，因为我们在释放进程时要CLEAN，这个有PTE_PG标志的页，也需要进行释放。不然SWAP区域的磁盘空间就不会被释放了。
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
uint64 a;
pte_t *pte;
if((va % PGSIZE) != 0)
panic("uvmunmap: not aligned");
for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
if((pte = walk(pagetable, a, 0)) == 0)
continue;
if(*pte & PTE_PG){
*pte &= (~PTE_PG);
swapdecget(PTE2IDX(*pte));
}
if((*pte & PTE_V) == 0)
continue;
if(PTE_FLAGS(*pte) == PTE_V)
panic("uvmunmap: not a leaf");
if(do_free){
uint64 pa = PTE2PA(*pte);
if (do_free & FREE_BCACHE)
bunpin2(pa);
if (do_free & 1)
kfree((void*)pa);
}
*pte = 0;
}
}
// swap.c
int
swapdecget(int idx)
{
acquire(&swaplock);
int res = --swappg_refcnt[idx];
release(&swaplock);
return res;
}
写pagein, pageout 的测试
我主要测试2个点，第一个是把物理内存用满，是否可以继续扩展堆。也就是开的空间要超过程序限制的128M的内存。
并且全部读取开的所有内存，确认里面的数据是正确。这样可以验证，pagein pageout 可以正确工作。
另外一个要测试的点，就是fork时， pagein, pageout 依然可以工作。
// swaptest.c
#include "kernel/param.h"
#include "kernel/fcntl.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/riscv.h"
#include "kernel/memlayout.h"
#include "kernel/fs.h"
#include "user/user.h"
void swap_page_write_read();
void swap_page_fork_test();
int
main(int argc, char *argv[])
{
swap_page_write_read();
swap_page_fork_test();
printf("swaptest: all tests succeeded\n");
exit(0);
}
void
swap_page_write_read()
{
uint64 st = (uint64)sbrk(0);
uint64 prev_a = st;
int maxpg = (PHYSTOP - KERNBASE) / PGSIZE;
int overflowpg = maxpg + 500;
for (int i = 0; i < overflowpg; i++) {
uint64 a = (uint64) sbrk(4096);
if(a == 0xffffffffffffffff){
printf("swap write failed\n");
exit(1);
}
// modify the memory to make sure it's really allocated.
*(char *)(a + 4096 - 1) = (i % 255);
prev_a = a;
}
// read all, ensure swapping dont change value in memory
int i = 0;
for (uint64 k = st; k <= prev_a; k += 4096, i++) {
if ((*(char *)(k + 4096 - 1)) != i % 255) {
printf("swap read failed\n");
exit(1);
}
}
sbrk(-overflowpg*4096);
printf("swap_page_write_read pass\n");
}
void
swap_page_fork_test()
{
uint64 st = (uint64)sbrk(0);
int maxpg = (PHYSTOP - KERNBASE) / PGSIZE;
// ensure still has phy mem to fork new process
int acquirepg = maxpg - 500;
for (int i = 0; i < acquirepg; i++) {
uint64 a = (uint64) sbrk(4096);
if(a == 0xffffffffffffffff){
printf("swap write failed\n");
exit(1);
}
*(char *)(a + 4096 - 1) = (i % 255);
}
uint64 end = (uint64)sbrk(0);
int pid = fork();
if (pid == 0) {
int i = 0;
for (uint64 k = st; k < end; k += 4096, i++) {
if ((*(char *)(k + 4096 - 1)) != i % 255) {
printf("fork chd swap read failed\n");
exit(1);
}
*(char *)(k + 4096 - 1) = 233;
}
exit(0);
}
// parent leave 1000 pg, chd alloc maxpg - 500; total phy pg size = maxpg + 500
// if no swap page, it will overflow
sbrk(-(acquirepg - 1000)*4096);
end = (uint64)sbrk(0);
int i = 0;
for (uint64 k = st; k < end; k += 4096, i++) {
if ((*(char *)(k + 4096 - 1)) != i % 255) {
printf("fork parent swap read failed\n");
exit(1);
}
}
int xstatus;
wait(&xstatus);
if (xstatus != 0) {
printf("fork swap chd failed\n");
exit(xstatus);
}
printf("swap_page_fork_test pass\n");
}
这是最后一个lab，我们终于完成了所有lab 的optional challenge
