[mit6.s081] 筆記 Lab5: Lazy Page Allocation | 記憶體頁懶分配

語言: CN / TW / HK

這是我自學 MIT6.S081 作業系統課程的 lab 程式碼筆記第五篇:Lazy page allocation。此 lab 大致耗時:5小時。

課程地址:https://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址:https://pdos.csail.mit.edu/6.S081/2020/labs/lazy.html
我的程式碼地址:https://github.com/Miigon/my-xv6-labs-2020/tree/lazy
Commits: https://github.com/Miigon/my-xv6-labs-2020/commits/lazy

本文中程式碼註釋是編寫部落格的時候加入的,原倉庫中的程式碼可能缺乏註釋或程式碼不完全相同。

Lab 5: Lazy Page Allocation

One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory. Xv6 applications ask the kernel for heap memory using the sbrk() system call. In the kernel we've given you, sbrk() allocates physical memory and maps it into the process's virtual address space. It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages; that's a huge number of allocations even if each is individually cheap. In addition, some programs allocate more memory than they actually use (e.g., to implement sparse arrays), or allocate memory well in advance of use. To allow sbrk() to complete more quickly in these cases, sophisticated kernels allocate user memory lazily. That is, sbrk() doesn't allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it. You'll add this lazy allocation feature to xv6 in this lab.

實現一個記憶體頁懶分配機制,在呼叫 sbrk() 的時候,不立即分配記憶體,而是隻作記錄。在訪問到這一部分記憶體的時候才進行實際的實體記憶體分配。

本次 lab 分為三個部分,但其實都是屬於同一個實驗的不同步驟,所以本文將三點集合到一起:

Eliminate allocation from sbrk() (easy) Lazy allocation (moderate) Lazytests and Usertests (moderate)

Lazy allocation & Tests

首先修改 sys_sbrk,使其不再呼叫 growproc(),而是隻修改 p->sz 的值而不分配實體記憶體。

c // kernel/sysproc.c uint64 sys_sbrk(void) { int addr; int n; struct proc *p = myproc(); if(argint(0, &n) < 0) return -1; addr = p->sz; if(n < 0) { uvmdealloc(p->pagetable, p->sz, p->sz+n); // 如果是縮小空間,則馬上釋放 } p->sz += n; // 懶分配 return addr; }

修改 usertrap 使用者態 trap 處理函式,為缺頁異常新增檢測,如果為缺頁異常((r_scause() == 13 || r_scause() == 15)),且發生異常的地址是由於懶分配而沒有對映的話,就為其分配實體記憶體,並在頁表建立對映:

```c // kernel/trap.c

// // handle an interrupt, exception, or system call from user space. // called from trampoline.S // void usertrap(void) { // ......

syscall();

} else if((which_dev = devintr()) != 0){ // ok } else { uint64 va = r_stval(); if((r_scause() == 13 || r_scause() == 15) && uvmshouldtouch(va)){ // 缺頁異常,並且發生異常的地址進行過懶分配 uvmlazytouch(va); // 分配實體記憶體,並在頁表建立對映 } 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; } }

// ......

} ```

uvmlazytouch 函式負責分配實際的實體記憶體並建立對映。懶分配的記憶體頁在被 touch 後就可以被使用了。
uvmshouldtouch 用於檢測一個虛擬地址是不是一個需要被 touch 的懶分配記憶體地址,具體檢測的是: 1. 處於 [0, p->sz)地址範圍之中(程序申請的記憶體範圍) 2. 不是棧的 guard page(具體見 xv6 book,棧頁的低一頁故意留成不對映,作為哨兵用於捕捉 stack overflow 錯誤。懶分配不應該給這個地址分配物理頁和建立對映,而應該直接丟擲異常)
(解決 usertests 中的 stacktest 失敗的問題) 3. 頁表項不存在

```c // kernel/vm.c

// touch a lazy-allocated page so it's mapped to an actual physical page. void uvmlazytouch(uint64 va) { struct proc p = myproc(); char mem = kalloc(); if(mem == 0) { // failed to allocate physical memory printf("lazy alloc: out of memory\n"); p->killed = 1; } else { memset(mem, 0, PGSIZE); if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){ printf("lazy alloc: failed to map page\n"); kfree(mem); p->killed = 1; } } // printf("lazy alloc: %p, p->sz: %p\n", PGROUNDDOWN(va), p->sz); }

// whether a page is previously lazy-allocated and needed to be touched before use. int uvmshouldtouch(uint64 va) { pte_t pte; struct proc p = myproc();

return va < p->sz // within size of memory for the process && PGROUNDDOWN(va) != r_sp() // not accessing stack guard page (it shouldn't be mapped) && (((pte = walk(p->pagetable, va, 0))==0) || ((*pte & PTE_V)==0)); // page table entry does not exist }

```

由於懶分配的頁,在剛分配的時候是沒有對應的對映的,所以要把一些原本在遇到無對映地址時會 panic 的函式的行為改為直接忽略這樣的地址。

uvmummap():取消虛擬地址對映

```c // kernel/vm.c // 修改這個解決了 proc_freepagetable 時的 panic 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 + npagesPGSIZE; a += PGSIZE){ if((pte = walk(pagetable, a, 0)) == 0) { continue; // 如果頁表項不存在,跳過當前地址 (原本是直接panic) } if((pte & PTE_V) == 0){ continue; // 如果頁表項不存在,跳過當前地址 (原本是直接panic) } if(PTE_FLAGS(pte) == PTE_V) panic("uvmunmap: not a leaf"); if(do_free){ uint64 pa = PTE2PA(pte); kfree((void)pa); } pte = 0; } }

```

uvmcopy():將父程序的頁表以及記憶體拷貝到子程序

```c // kernel/vm.c // 修改這個解決了 fork 時的 panic 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) continue; // 如果一個頁不存在,則認為是懶載入的頁,忽略即可 if((pte & PTE_V) == 0) continue; // 如果一個頁不存在,則認為是懶載入的頁,忽略即可 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; } ```

copyin() 和 copyout():核心/使用者態之間互相拷貝資料

由於這裡可能會訪問到懶分配但是還沒實際分配的頁,所以要加一個檢測,確保 copy 之前,使用者態地址對應的頁都有被實際分配和對映。

```c // kernel/vm.c // 修改這個解決了 read/write 時的錯誤 (usertests 中的 sbrkarg 失敗的問題) int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) { uint64 n, va0, pa0;

if(uvmshouldtouch(dstva)) uvmlazytouch(dstva);

// ......

}

int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) { uint64 n, va0, pa0;

if(uvmshouldtouch(srcva)) uvmlazytouch(srcva);

// ......

} ```

至此修改完成,在 xv6 中執行 lazytests 和 usertests 都應該能夠成功了。
如果在某一步出現了 remap 或者 leaf 之類的 panic,可能是由於頁表項沒有釋放乾淨。可以從之前 pgtbl 實驗中借用列印頁表的函式 vmprint 的程式碼,並在可能有關的系統呼叫中打出,方便對頁表進行除錯。

tip. 如果 usertests 某一步失敗了,可以用 usertests [測試名稱] 直接單獨執行某個之前失敗過的測試,例如 usertests stacktest 可以直接執行棧 guard page 的測試,而不用等待其他測試漫長的執行。