MIT 6.S081 2020 Lab6 Copy-on-Write Fork for xv6 個人全流程

文章目錄

- 零、寫在前面
- 一、Implement copy-on write
- - 1.1 說明
  - 1.2 實現
  - - 1.2.1 延遲復制與釋放
    - 1.2.2 寫時復制

零、寫在前面

可以閱讀下《xv6 book》的第五章中斷和設備驅動。

問題

在 xv6 中，fork() 系統調用會將父進程的整個用戶空間內存復制到子進程中。**如果父進程占用的內存較大，復制過程會非常耗時。更糟糕的是，這種復制往往是浪費的。**例如，在子進程中調用 fork() 后緊接著執行 exec()，會導致子進程丟棄復制來的內存，很可能其中大部分根本沒有被使用。另一方面，如果父子進程都使用了某個頁面，并且有一個或兩個要寫這個頁面，那就確實需要進行復制。

解決方案

**寫時復制（COW）**的 fork() 目標是推遲為子進程分配和復制物理內存頁面，直到它們真的被需要（如果有的話）。

COW 的 fork() 僅為子進程創建一個頁表，其中用戶內存的頁表項（PTE）指向父進程的物理頁面。COW 的 fork() 會將父子進程中所有用戶頁面的頁表項標記為不可寫（即清除可寫標志）。當任一進程嘗試寫這些 COW 頁面時，CPU 會觸發一個缺頁異常（page fault）。內核的缺頁異常處理程序會識別出這是 COW 的情況，為發生異常的進程分配一個新的物理頁面，復制原頁面的內容，然后修改該進程的頁表項指向新頁面，并將其標記為可寫。異常處理程序返回后，用戶進程就可以寫這個新復制的頁面了。

COW 的 fork() 也讓用戶內存的物理頁面釋放變得更復雜。因為一個物理頁面可能會被多個進程的頁表引用，只有當最后一個引用消失時，該頁面才能被釋放。

我們發現 COW 和 Lazy alloc 的思想其實是類似的。

記得切換到 cow 分支

一、Implement copy-on write

1.1 說明

你的任務是：在 xv6 內核中實現寫時復制的 fork()。當你的內核能夠成功執行 cowtest 和 usertests 這兩個程序時，說明你完成了任務。

官網推薦的實現步驟：

修改 uvmcopy()，不要為子進程分配新頁面，而是將父進程的物理頁面映射到子進程中。清除父子兩者對應頁表項中的 PTE_W（可寫標志）。
修改 usertrap() 以識別缺頁異常。如果在 COW 頁面上發生缺頁異常，則使用 kalloc() 分配一個新頁面，將原頁面內容復制過去，并在當前進程的頁表中安裝新頁面，并設置 PTE_W。
確保物理頁面只在最后一個引用消失時才釋放。你可以為每個物理頁面維護一個“引用計數”，記錄有多少個用戶頁表引用了該頁面。
- 當 kalloc() 分配頁面時，將引用計數設為 1。
- 當 fork() 讓子進程共享頁面時，將引用計數加 1。
- 每當進程從頁表中移除頁面時，引用計數減 1。
- 只有當引用計數為 0 時，kfree() 才能將頁面放回空閑列表。
- 可以用一個定長的整數數組來存儲這些引用計數。你需要設計如何為頁面選擇索引以及數組大小。例如，你可以用頁面物理地址除以 4096 作為索引，數組元素個數可以設為 kalloc.c 中 kinit() 放入空閑列表的最高物理地址除以 4096。
修改 copyout()，當遇到 COW 頁面時，采用和處理缺頁異常一樣的方案進行處理。

官網的一些提示：

懶惰分配實驗應該讓你對實現 COW 所需的 xv6 代碼已有一定了解。但請不要在本實驗中基于你之前懶惰分配實驗的實現，而是從一個全新的 xv6 拷貝開始。
你可以使用 RISC-V 頁表項中的 RSW（軟件保留位）來記錄每個 PTE 是否為 COW 映射。
usertests 測試了一些 cowtest 沒有覆蓋的情況，所以一定要確保兩個測試都能通過。
有用的頁表標志宏和定義可以在 kernel/riscv.h 文件末尾找到。
如果在處理 COW 缺頁異常時沒有可用內存，應該終止對應進程。

1.2 實現

官網給出的步驟其實已經讓我們有一個較為清晰的思路了，下面直接實現就行了。

實現邏輯分為兩部分：

延遲復制與釋放
寫時復制

1.2.1 延遲復制與釋放

首先在 kalloc.c 中添加一個結構體保存每個頁面的引用計數
為了保證并發安全，我們額外添加一個自旋鎖
為了方便，提供一個宏用于計算引用計數數組索引，這也是官網給出的頁面物理地址除以 4096 作為索引的方法

// get cnt Array index
#define PA2IDX(p) (((uint64)(p)) / PGSIZE)struct {struct spinlock lock; // spinlock to ensure concurrency safetyint refCnt[PHYSTOP / PGSIZE]; // page ref cnt array
} pageRef;

在 kinit 中新增一行 pageRef 自旋鎖的初始化

void
kinit()
{initlock(&kmem.lock, "kmem");initlock(&pageRef.lock, "pageRef"); // initialize the lock for pageReffreerange(end, (void*)PHYSTOP);
}

在 kalloc 中對新增頁面的引用計數初始化為1

void *
kalloc(void)
{// ...if(r) {memset((char*)r, 5, PGSIZE); // fill with junkpageRef.refCnt[PA2IDX(r)] = 1;}return (void*)r;
}

然后修改 kfree 的邏輯為只有當引用計數減為0 時才釋放

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{struct run *r;if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)panic("kfree");acquire(&pageRef.lock); // acquire the lock for pageRef// not referred nowif(--pageRef.refCnt[PA2IDX(pa)] <= 0) {memset(pa, 1, PGSIZE);    // fill with junkr = (struct run*)pa;acquire(&kmem.lock);r->next = kmem.freelist;kmem.freelist = r;release(&kmem.lock);    }release(&pageRef.lock);
}

我們還要添加新增引用計數的邏輯
以及物理頁面復制的邏輯，以便后面調用
記得在defs.h添加聲明WWWWW

// if clone is needed
void *kTry_pgclone(void *pa) {acquire(&pageRef.lock);// if it only belongs to meif(pageRef.refCnt[PA2IDX(pa)] <= 1) {release(&pageRef.lock);return pa;}// apply for a new pageuint64 newpa = (uint64)kalloc();if(newpa == 0) {release(&pageRef.lock);return 0;}// copy old data to new onememmove((void*)newpa, (void*)pa, PGSIZE);// refCnt of old page decpageRef.refCnt[PA2IDX(pa)]--;release(&pageRef.lock);return (void*)newpa;
}// inc the refCnt
void kparef_inc(void *pa) {acquire(&pageRef.lock);pageRef.refCnt[PA2IDX(pa)]++;release(&pageRef.lock);
}

然后就可以修改 vm.c 中的uvmcopy的復制操作改為該物理頁面的引用次數+1
以及為子進程新建頁表

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");pa = PTE2PA(*pte);if (*pte & PTE_W) {*pte = (*pte & ~PTE_W) | PTE_COW;}flags = PTE_FLAGS(*pte);// create pte for son processif(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){goto err;}kparef_inc((void*)pa);}return 0;err:uvmunmap(new, 0, i / PGSIZE, 1);return -1;
}

1.2.2 寫時復制

即然要延遲寫操作，那么在缺頁異常的時候我們就需要知道這些頁面是否是寫時復制的共享頁面，官網也是提醒我們，可以用 PTE 的保留位來標記。

我們為COW 的缺頁錯誤編寫一個輔助函數
復制一個新頁面
設置為可寫，取消 COW標記
取消舊頁面映射，添加新映射
記得在 defs.h 中添加聲明

int cow_Helper(pagetable_t pagetable, uint64 va)
{pte_t *pte;// get pte for vaif((pte = walk(pagetable, va, 0)) == 0)panic("uvmcowcopy: walk");uint64 pa = PTE2PA(*pte);uint64 newpa;// clone pageif((newpa = (uint64)kTry_pgclone((void*)pa)) != 0){// set PTE_W and unset PTE_COWuint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;// unmap but do not free uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0);// map to new pgif(mappages(pagetable, va, 1, newpa, flags) == -1) {panic("uvmcowcopy: mappages");}return 0;}return -1;
}

然后修改copyout 的邏輯
如果發現是 cow 頁面，就調用 cow_Helper() 來處理。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{uint64 n, va0, pa0;pte_t *pte;struct proc *p = myproc();while(len > 0){va0 = PGROUNDDOWN(dstva);// cowif(va0 < p->sz && (pte = walk(pagetable, va0, 0))!=0 && *pte & PTE_V&& *pte & PTE_COW)cow_Helper(pagetable,va0);// ...
}

以及usertrap 邏輯的修改
針對我們寫時復制的頁面錯誤單獨處理

void
usertrap(void)
{int which_dev = 0;if((r_sstatus() & SSTATUS_SPP) != 0)panic("usertrap: not from user mode");// send interrupts and exceptions to kerneltrap(),// since we're now in the kernel.w_stvec((uint64)kernelvec);struct proc *p = myproc();// save user program counter.p->trapframe->epc = r_sepc();if(r_scause() == 8){// system callif(p->killed)exit(-1);// sepc points to the ecall instruction,// but we want to return to the next instruction.p->trapframe->epc += 4;// an interrupt will change sstatus &c registers,// so don't enable until done with those registers.intr_on();syscall();} else if((which_dev = devintr()) != 0){// ok} else if (r_scause() == 13 || r_scause() == 15){pte_t *pte;uint64 va = r_stval();// is va valid?if (va >= p->sz)exit(-1);pte = walk(p->pagetable, va, 0);// valid and cow ?if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_COW) == 0)exit(-1);// copy on write for cow pgif (cow_Helper(p->pagetable, va) == -1) {exit(-1);}} else {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;}if(p->killed)exit(-1);// give up the CPU if this is a timer interrupt.if(which_dev == 2)yield();usertrapret();
}

測試一下：

cowtest:

外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

usertest:

外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

官網還是寫的太詳細了（bushi

p->killed = 1;
}

if(p->killed)
exit(-1);

// give up the CPU if this is a timer interrupt.
if(which_dev == 2)
yield();

usertrapret();
}

**測試一下：****cowtest:**[外鏈圖片轉存中...(img-TxytPoKI-1748706565978)]**usertest:**[外鏈圖片轉存中...(img-kelfELYU-1748706565978)]官網還是寫的太詳細了（bushi