前言
本來往年這里還有個Lazy Allocation的，今年不知道為啥直接給跳過去了。.
其他篇章
環(huán)境搭建
Lab1: Utilities
Lab2: System calls
Lab3: Page tables
Lab4: Traps
Lab5: Copy-on-Write Fork for xv6
參考鏈接
官網鏈接
xv6手冊鏈接，這個挺重要的，建議做lab之前最好讀一讀。
xv6手冊中文版，這是幾位先輩們的辛勤奉獻來的呀！再習慣英文文檔閱讀我還是更喜歡中文一點，開源無敵！
個人代碼倉庫
官方文檔
1. 簡單分析
寫時拷貝（Copy On Write）技術之前在15445也寫過了，這里再簡單介紹一下。我們知道，fork的過程有一條就是子進程會拷貝父進程的內存空間，但是這個拷貝是有一定開銷的，尤其是在需要拷貝的東西多的時候更明顯。但是這就引出了一個問題——我們真的需要去拷貝嗎？很顯然，從邏輯上來看，只有父進程或子進程對內存空間有修改時，這種拷貝才是有意義的，否則只是徒增開銷而已。依此便提出了COW思想——我們將拷貝的時機推遲到某個進程修改內存的時候，這樣就可以優(yōu)化掉很多無必要的開銷。
落實到實現(xiàn)策略上，Lab文檔為我們描述了一種方案——平時fork我們只需要為父子進程添加一個指向原始頁面的指針即可，這個頁面將被標記為只讀。這樣當父進程或子進程嘗試寫入頁面時，就會觸發(fā)page fault（這應該算異常吧），這個時候再由內核去重新分配內存空間，為進程提供一個可寫的頁面，處理結束，至此我們就基本實現(xiàn)了這個COW。
不過這么寫產生了一個問題，即是內存釋放，本來我們頁面的釋放是隨著進程釋放同步進行的，但是上面描述的策略中的進程不再持有真實的內存頁面，而僅僅是一個引用，為了處理釋放，我們可以采用引用計數(shù)的方法——我們可以在內存頁的元信息（meta data）中單獨保存一個值用于計數(shù)，當我們的進程釋放時，遞減引用計數(shù)，然后當計數(shù)為0時再調用內存的釋放。
需要注意的是，這個過程描述起來非常簡單，在xv6上的實現(xiàn)也不太困難，但是在實際的大型內核中總會有各種各樣的細節(jié)問題，Lab提供了一個探討COW存在的問題的鏈接，可以參考一下。
根據(jù)上面的分析，我們可以將這個Lab分為三個部分做：
- 在fork時造成內存復制的假象
- 處理page fault，在寫時真實復制內存
- 使用引用計數(shù)管理內存釋放
下面我們就來實現(xiàn)吧！
2. 在fork時實現(xiàn)頁面復用而非復制
根據(jù)我們之前l(fā)ab的經驗以及l(fā)ab中的hint，fork中執(zhí)行頁面復制的操作是在vm.c下的uvmcopy完成的：
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
char *mem;
for(i = 0; i < sz; i += PGSIZE){
// 檢查頁表合法性
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if((mem = kalloc()) == 0) // 沒有空閑內存
goto err;
memmove(mem, (char*)pa, PGSIZE); // 拷貝內存
if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
kfree(mem);
goto err;
}
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
可以看到，整體的流程是先分配一個mem，然后將父進程的pa拷貝到mem中去，然后把這個mem映射到子進程上，因此我們可以直接把pa映射過去即可：
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
for(i = 0; i < sz; i += PGSIZE){
// 檢查頁表合法性
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
*pte &= ~PTE_W; // 取消寫權限
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if(mappages(new, i, PGSIZE, pa, flags) != 0){
goto err;
}
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
3. 處理page fault
觸發(fā)page fault就會trap，而trap我們知道是在trap.c下的usertrap完成，而處理fault需要判斷fault的類型，這在xv6里面是一個選擇結構，通過r_scause()的值來判斷，在去年其實有一個Lazy Allocation的Lab的，里面有告訴我們r_scause()值為13或15為頁面錯誤，其中13為讀錯誤，15為寫錯誤，因此此處我們只需要處理值為15時的情況：
else if (r_scause() == 15) {
uint64 stval = r_stval();
if (is_cow_fault(p->pagetable, stval)) {
if (handle_cow_fault(p->pagetable, stval) < 0) {
printf("usertrap(): alloc failed!\n");
p->killed = 1; // 當內存分配完，直接kill
}
}
else {
goto unexpected;
}
}
else {
unexpected:
printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
setkilled(p);
}
框架有了，我們怎么來判斷一個fault是不是cow導致的呢？我們可以在PTE中用一位標記一下：
查看參考手冊，我們可以看到8-9位是保留位，因此我們可以把第八位用于保存COW：
并在uvmcopy處置位
*pte |= PTE_C; // 設置寫時復制標志
然后我們在vm.c實現(xiàn)上面兩個函數(shù)：
int
is_cow_fault(pagetable_t pagetable, uint64 va)
{
if (va >= MAXVA)
return 0;
pte_t* pte = walk(pagetable, PGROUNDDOWN(va), 0);
return pte && (*pte & (PTE_V | PTE_U | PTE_C));
}
int
handle_cow_fault(pagetable_t pagetable, uint64 va)
{
va = PGROUNDDOWN(va);
pte_t* pte = walk(pagetable, va, 0);
if (!pte) {
return -1;
}
uint64 pa = PTE2PA(*pte);
uint flags = (PTE_FLAGS(*pte) & ~PTE_C) | PTE_W; // 取消寫時復制標志，設置寫權限
char* mem = kalloc();
if (!mem) {
return -1;
}
memmove(mem, (char*)pa, PGSIZE);
uvmunmap(pagetable, va, 1, 1); // 取消映射
if (mappages(pagetable, va, PGSIZE, (uint64)mem, flags) != 0) {
kfree(mem);
return -1;
}
return 0;
}
并在defs.h創(chuàng)建聲明
int is_cow_fault(pagetable_t pagetable, uint64 va);
int handle_cow_fault(pagetable_t pagetable, uint64 va);
4. 引用計數(shù)管理內存釋放
首先思考一下我們的引用計數(shù)怎么實現(xiàn)，hint提示我們可以利用一個數(shù)組，直接映射對應頁的引用計數(shù)，于是我們在kalloc.c中：
// 引用計數(shù)的鎖和保存值
struct spinlock cow_ref_lock;
int cow_cnt[(PHYSTOP - KERNBASE) / PGSIZE];
#define PA2IDX(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)
初始化鎖：
void
kinit()
{
initlock(&kmem.lock, "kmem");
initlock(&cow_ref_lock, "cow_ref_lock"); // 初始化引用計數(shù)的鎖
freerange(end, (void*)PHYSTOP);
}
然后定義自增操作與自減操作：
void
inc_ref(void* pa) // 自增引用計數(shù)
{
acquire(&cow_ref_lock);
cow_cnt[PA2IDX(pa)]++;
release(&cow_ref_lock);
}
void
dec_ref(void* pa) // 自減引用計數(shù)
{
acquire(&cow_ref_lock);
cow_cnt[PA2IDX(pa)]--;
release(&cow_ref_lock);
}
完善alloc與free：
void
kfree(void *pa)
{
dec_ref(r);
if (cow_cnt[PA2IDX(r)] > 0) // 只有引用計數(shù)為1時才釋放
return;
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);
}
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r)
kmem.freelist = r->next;
release(&kmem.lock);
if(r)
{
cow_cnt[PA2IDX(r)] = 1; // 將引用計數(shù)置1
memset((char*)r, 5, PGSIZE); // fill with junk
}
return (void*)r;
}
然后我們思考一下什么時候引用計數(shù)需要增加呢？那應該是fork的時候，因此我們需要暴露出inc_ref（略）然后在uvmcopy中調用它：
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
for(i = 0; i < sz; i += PGSIZE){
// 檢查頁表合法性
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
if (*pte & PTE_W) // 對于本身可寫的頁才去取消寫權限
{
*pte &= ~PTE_W; // 取消寫權限
*pte |= PTE_C; // 設置寫時復制標志
}
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if(mappages(new, i, PGSIZE, pa, flags) != 0){
goto err;
}
inc_ref((void*)pa);
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
最后還有個問題，就是對于不會觸發(fā)trap的頁操作，這里沒有涉及到，根據(jù)提示，我們可以找到vm.c下的copyout，這個函數(shù)是通過軟件訪問頁表，我們就仿照trap里為它新增一段邏輯：文章來源：http://www.zghlxwxcb.cn/news/detail-632283.html
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
if (is_cow_fault(p->pagetable, stval)) {
if (handle_cow_fault(p->pagetable, stval) < 0) {
printf("copyout(): alloc failed!\n");
return -1;
}
}
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
n = PGSIZE - (dstva - va0);
if(n > len)
n = len;
memmove((void *)(pa0 + (dstva - va0)), src, n);
len -= n;
src += n;
dstva = va0 + PGSIZE;
}
return 0;
}
5. 測試
最后運行make grade評分即可，這里說一下我遇到過的錯：文章來源地址http://www.zghlxwxcb.cn/news/detail-632283.html
-
終端剛開回車兩下就出現(xiàn) panic: uvmunmap: not aligned :
原因是va沒有對齊，在單獨寫的那兩個函數(shù)里對vaa使用va = PGROUNDDOWN(va);即可； -
Test file測試過不了:
原因是copyout沒有改，改了就行；
到了這里，關于6.s081/6.1810（Fall 2022）Lab5: Copy-on-Write Fork for xv6的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
