1. LAB 基本
LAB的做法網(wǎng)路上很多俺亮，有困難的小伙伴可以參考這篇：https://blog.csdn.net/LostUnravel/article/details/121437327
我重點會介紹如何實現(xiàn)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.
根據(jù)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.
也就意味著哨啃，原版本的實現(xiàn)，父進程和子進程會分貝各自創(chuàng)建自己的物理頁拳球。實際的結(jié)果是2頁并沒有共享审姓。那么父子進程的寫，并未相互可見祝峻。所以當(dāng)實現(xiàn)了這個OC之后魔吐，理論上子進程改的東西可以立刻被父進程看到，那么就實現(xiàn)了進程間的數(shù)據(jù)交流莱找。
我們先從一個測試用例開始, 去驗證這個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， 父進程可以看到子進程的寫奥溺，子進程可以看到父進程的讀辞色。
然后就是怎么實現(xiàn) ，其實我們看第二個OC的要求浮定，第二個OC的要求其實包含了第一個相满，他是更進一步。因為在把文件加載到bcache的時候桦卒，已經(jīng)用了一個物理頁去存了立美，那么我們可以讓父進程，子進程和文件系統(tǒng)的bcache 3個共享同一個物理頁方灾，是最節(jié)約的做法建蹄。
那么我們就直接入手第二個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 過來了裕偿。
step 1. 調(diào)整BSIZE
我們需要把BSIZE 給從1024 改到4096洞慎，這樣是為了緩存對齊內(nèi)存頁的大小。但是直接改數(shù)組的方式會報如下的錯：
首先有些測試會不通過谆棱，原因是它在棧上開了一個BSIZE大的數(shù)組垃瞧，但是棧的空間只有一個PGSIZE，當(dāng)BSIZE==PGSIZE嗦锐，就會爆棧。所以需要改一下相關(guān)測試代碼：
在mmaptest里碳默，因為n = PGSIZE/BSIZE, 所以write 1.5 page的代碼邏輯會在整數(shù)除法 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
原因是因為，如果我們直接改數(shù)組的大小的方式愉适，那bcache-> data 的地址并不是頁對齊的，我們在做mappages 會默認(rèn)傳進去的pa是頁對齊的癌蓖，然后用最后的10位轉(zhuǎn)成PTE，恢復(fù)的時候用僧，默認(rèn)最后12位是0责循。
所以我們需要用kalloc 去處理b->data
step 2. 修改mmap
原先我們在page fault時秸抚，如果落在VMA的區(qū)域里，會直接alloc 一個新的物理頁吭敢，我們現(xiàn)在需要改變這段邏輯省有，讓它復(fù)用bcache 里已經(jīng)創(chuàng)建出來用作cache的物理頁。
- 首先判斷如果是
MAP_PRIVATE舷蟀，那么不應(yīng)該復(fù)用野宜。
2.如果不是private，我們要根據(jù)inode和offset找到對應(yīng)的buf闯袒，然后用buf->data的地址 當(dāng)作mem(physical address)其徙，同時要增加buf的refcnt，可以用bpin的方式去維護闹获。 - 然后把虛擬地址避诽，映射現(xiàn)在page fault的
va(virtual address)，當(dāng)這個mem上 - 這邊如果要釋放轨功，我們應(yīng)該
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
}
因為傳統(tǒng)的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");
}
下面我們需要一個根據(jù)IP 和 off 找到對應(yīng)的文件位置的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 知道應(yīng)該是調(diào)用bunpin2還是kfree. 所以我們需要額外加一個參數(shù)在do_free
綜上我們就完成了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.)
這塊的實現(xiàn)熙揍，就是我們現(xiàn)在的內(nèi)存區(qū)域既有HEAP的靜態(tài)增長區(qū)域届囚， 又有mmap 出來的動態(tài)區(qū)域vma泥耀。我們可以把2者統(tǒng)一起來痰催。
也就是把heap 區(qū)域陨囊，也當(dāng)作一個VMA，這樣lazy alloc 也可以復(fù)用vma 的page fault 去實現(xiàn)压语。
這里為了解決內(nèi)存碎片的問題扰才。我把VMA區(qū)域分成2塊衩匣，指定地址的為靜態(tài)的，開了8個VMA的空間柄延，不指定地址的為動態(tài)，也開了8個VMA空間滤奈。那么HEAP可以放在靜態(tài)區(qū)域。動態(tài)區(qū)域地址從大往小走搞糕。HEAP拓展從小往大走。如果mmap指定地址驹吮，那么放在靜態(tài)空間。
// 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是否充足的時候族沃，靜態(tài)區(qū)域要每個都判斷無交集常空，動態(tài)區(qū)域，我們知道地址是排序的昆禽，所以可以提前退出遗契。
代碼改動如下：
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 要做的事情，可以統(tǒng)一用vma_handle 去概括起來僵井。因為HEAP 用的是MAP_PRIVATE, 并且沒有傳fd, inode； 所以就是直接開一頁內(nèi)存驻债，然后mappages。
下面就把原來lazy_alloc的代碼邏輯 同一用vma_handle 替換掉
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 這個函數(shù)做了哪些事
- 首先它要創(chuàng)建一個新的pagetable，因為要拋棄掉fork 繼承過來的舊pagetable
- 其次他會根據(jù)elf里的信息去讀取要運行程序的代碼段和數(shù)據(jù)段； 這部分就是我們可以用VMA 去延遲加載的部分
- 設(shè)置好棧
- 配置argument凛剥，以及相關(guān)寄存器使得main函數(shù)可以正確執(zhí)行
- 最后就是釋放掉之前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;
但我們發(fā)現(xiàn)這和常規(guī)的mmap有一個不同之處。常規(guī)的mmap 一般memsz 就是filesz轻姿，但是這邊出現(xiàn)了2個不同的變量犁珠，且是不同的值。
一般memsz 會比filesz大互亮。
如果我們這邊統(tǒng)一用memsz犁享，我們就會要從文件里讀取要執(zhí)行的代碼段的時候，多讀進一些本來不是執(zhí)行代碼的數(shù)據(jù)豹休，當(dāng)作了執(zhí)行代碼炊昆，就會程序出錯。
如果我們使用filesz谎砾，就會本來應(yīng)該在vma管轄里的內(nèi)存郎笆，沒有被包含進來。比如這個空間本來是留給棧放一些臨時變量，但是我們用了filesz，這個空間不再vma里二驰，就直接page fault了。
同時還有一個難點是這里我們只能拿到inode妄均， 我們不會再有fd 和 file結(jié)構(gòu)，如果沒有file這個結(jié)構(gòu)，那么就沒有天然維護好的offset悲没，所以這里也只能我們自己維護住file里要讀的offset；
綜上，我們必須要要在vma的數(shù)據(jù)結(jié)構(gòu)里做擴展侦讨。
然后上面的代碼，我們可以這樣改：
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;
}
這里我們?yōu)镋XEC單獨創(chuàng)建了一個vma_type父款；
是因為
在正常mmap時结笨，我們 fork, 需要對文件的引用計數(shù)做增加通過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);
}
}
}
另外我們注意到雏掠，現(xiàn)在VMA里會存要執(zhí)行的代碼。所以當(dāng)那些代碼沒執(zhí)行到的時候庇楞，進行fork。他依然會存在在VMA里炬转；這時如果執(zhí)行EXEC薯蝎，我們時需要把EXEC 和 HEAP的VMA都進行清理婿失。不然遇到PAGE FAULT的時候，會發(fā)生錯誤的執(zhí)行了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，是一些優(yōu)化技巧瘫寝，不需要額外測試蜒蕾；只需要確保原來的程序可以正常運轉(zhuǎn)，就說明優(yōu)化是正確的矢沿。不然系統(tǒng)會報錯滥搭。
但是做了EXEC的優(yōu)化后酸纲，原來usertests 測試會有一個問題捣鲸。
就是countfree 會計算運行測試前的空閑內(nèi)存頁，和運行測試后的空閑內(nèi)存頁闽坡。如果2者不一致栽惶，就說明有內(nèi)存泄漏愁溜。
但是EXEC這個優(yōu)化后，因為運行測試前外厂，大部分代碼并沒有走到冕象，所以這時EXEC的VMA的物理頁還沒有被創(chuàng)建出來。
而運行測試后汁蝶，所有代碼被走到渐扮，EXEC的VMA會創(chuàng)建出物理頁，延遲加載了要用的程序代碼掖棉。
所以前者就是會比后者多出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.
這個問題其實比較大幔亥，要實現(xiàn)的很好是可以花非常多的功夫耻讽。我就是挑一些最基本的點實現(xiàn)了一下。
交換空間（Swapping Space）可以是固定大小的帕棉，也可以是動態(tài)的针肥，這取決于你如何配置它。交換空間通常通過以下兩種方式之一實現(xiàn)：
首先是交換分區(qū)應(yīng)該怎么設(shè)計：
- 交換分區(qū)（Swap Partition）:
交換分區(qū)是硬盤上預(yù)先分配的特定分區(qū)香伴，用作交換空間慰枕。
分區(qū)大小在創(chuàng)建時設(shè)定，因此它是固定大小的瞒窒。
你可以在安裝Linux時或之后使用分區(qū)工具創(chuàng)建交換分區(qū)捺僻。
你可以有多個交換分區(qū)。
- 交換文件（Swap File）:
交換文件是一個普通文件崇裁，可以在文件系統(tǒng)中的任何位置匕坯。
交換文件的大小可以在創(chuàng)建后調(diào)整，因此它可以是動態(tài)的拔稳。
交換文件可以在需要時創(chuàng)建葛峻，并且可以根據(jù)需要增加或減少它們的大小。
使用交換文件不需要專門的分區(qū)巴比，可以更靈活地使用磁盤空間术奖。
在這里我選擇實現(xiàn)了第1種方案。所以我在創(chuàng)建文件系統(tǒng)開始時轻绞，就用了1024個BLOCK采记，用來當(dāng)作交換分區(qū)。所以實際的物理內(nèi)存會從原來的128MB 變?yōu)?132MB. （一個BLOCK時4KB）政勃。
代碼改動如下:
其次是如何選擇犧牲頁唧龄。我這邊使用了老化算法，原因是比較好實現(xiàn)奸远，效果也還不錯既棺，非常近似LRU讽挟。具體算法可以看這篇博客： https://juejin.cn/post/7024789733498683429#%E8%80%81%E5%8C%96%E7%AE%97%E6%B3%95
在選擇犧牲頁中，我們得考慮到因為我們實現(xiàn)了copy_on_write丸冕， 所以有些頁可能是被多個進程引用的耽梅。那么釋放這樣的頁，必須先恢復(fù)copy_on_write的標(biāo)志胖烛，才能犧牲眼姐。所以得不償失。所以在檢查的時候佩番，我會去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塊代碼妥凳，主要完成了維護每一個內(nèi)存頁的age, 以及如何選擇犧牲頁的代碼。
下面我們就是要實現(xiàn)答捕，當(dāng)物理頁不夠的時候逝钥，通過page-out 去獲得一頁新的物理頁的邏輯。
可以得知直接感受到內(nèi)存物理頁不足的地方是當(dāng)kalloc 失敗的時候
然后我們找到了犧牲頁拱镐，我們需要把這頁存進我們的交換區(qū)域艘款，然后設(shè)置對應(yīng)的PTE_PG標(biāo)志，同時取消PTE_V的標(biāo)志沃琅，來觸發(fā)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;
}
然后我們需要實現(xiàn)pagein的邏輯哗咆，就是當(dāng)trap 發(fā)生的時候，我們需要判斷一下是不是因為由PTE_PG標(biāo)志益眉，如果是的話晌柬，說明在訪問一個被pageout的界面。
同時我們要移除堆大小是否超過128M的檢查郭脂，因為現(xiàn)在可以額外加上SWAP區(qū)域的內(nèi)存了年碘。
我們在VMA_HANDLE里考慮這種情況
下面是pagein的實現(xiàn)：
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標(biāo)志的頁屿衅，也需要進行釋放。不然SWAP區(qū)域的磁盤空間就不會被釋放了莹弊。
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個點涤久，第一個是把物理內(nèi)存用滿，是否可以繼續(xù)擴展堆忍弛。也就是開的空間要超過程序限制的128M的內(nèi)存响迂。
并且全部讀取開的所有內(nèi)存，確認(rèn)里面的數(shù)據(jù)是正確细疚。這樣可以驗證蔗彤，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镇防，我們終于完成了所有l(wèi)ab 的optional challenge
