---

零、寫在前面

可以閱讀下4.6頁面錯誤異常

像應用程序申請內存，內核分配和映射這些內存其實是很耗費時間的。比如，一個 GB 的內存包含 262,144 個 4096 字節的頁；即便每次分配的開銷很小，這么多次操作累積起來仍然非常耗時。

此外，一些程序會分配比實際使用更多的內存（例如，為了實現稀疏數組），或者會提前分配內存但遲遲不使用。為加快 sbrk() 的執行速度，現代內核采用了一種稱為懶惰分配的技術：sbrk() 不再立即分配物理內存，而是僅記錄下哪些用戶地址被分配了，并在用戶頁表中將這些地址標記為無效。

當進程首次嘗試訪問這些**“懶惰分配”**的頁面時，CPU 會觸發一次缺頁異常（page fault）。內核在處理該異常時，會分配一頁物理內存、將其清零，并將其映射到進程的地址空間中。

總的來說，懶惰分配是一種常見的降低均攤成本的操作。

在本實驗中，你將為 xv6 添加這個懶惰分配的功能。

記得先切換分支到lazy

一、Eliminate allocation from sbrk()

1.1 說明

你的第一個任務是從 sbrk(n) 系統調用的實現中刪除物理頁面分配。該系統調用對應的函數是 sysproc.c 文件中的 sys_sbrk()。

sbrk(n) 系統調用的作用是將當前進程的內存大小增加 n 字節，并返回新分配區域的起始地址（即原來的內存大小）。你需要修改 sbrk(n) 的實現，使其僅僅將進程的大小（myproc()->sz）增加 n 字節并返回舊的大小。

注意：不應該在這里分配物理內存，因此需要刪除對 growproc() 的調用。但你仍然需要更新進程的大小字段。

試著猜一猜：這個修改會導致什么問題？會有什么地方出錯？

進行上述修改后，啟動 xv6，并在 shell 中輸入 echo hi。你應該會看到類似下面的輸出：

init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped

其中，usertrap(): ... 是來自 trap.c 中用戶異常處理函數（user trap handler）的信息；它捕獲到了一個它不知道如何處理的異常。你需要弄清楚為什么會發生這個缺頁異常（page fault）。

信息中的 stval=0x0000000000004008 表示導致缺頁異常的虛擬地址是 0x4008。

1.2 實現

我們先來看看初始的sys_sbrk：

uint64 sys_sbrk(void) {int addr;int n;if(argint(0, &n) < 0)return -1;addr = myproc()->sz;if(growproc(n) < 0)return -1;return addr;
}

• 從寄存器a0拿出n
• growproc(n) 來分配n byte 的物理內存
• 返回addr

修改后：

• 刪除分配物理內存的邏輯
• 如果n 大于0，我們增加sz
• 否則，我們dealloc 掉n個字節

uint64 sys_sbrk(void) {int addr;int n;if(argint(0, &n) < 0)return -1;struct proc* p = myproc();addr = p->sz;//  if(growproc(n) < 0)//    return -1;// allocif (n > 0){(p->sz) += n;} else {// shrinkuint sz = p->sz;p->sz = uvmdealloc(p->pagetable, sz, sz + n);}return addr;
}

我們啟動xv6來測試下：

和預期一致，我們接著做后面的作業。

二、Lazy allocation

2.1 說明

修改 trap.c 中的代碼，使其能在用戶空間發生缺頁異常時，為發生異常的地址映射一頁新分配的物理內存，然后返回用戶空間，讓進程繼續執行。你應當在打印 "usertrap(): ..." 的那條 printf 語句之前加入你的處理代碼。此外，你還需要根據需要修改 xv6 內核中的其他代碼，使 echo hi 能夠正常運行。

官網的一些提示：

• 你可以在 usertrap() 中通過檢查 r_scause() 是否為 13 或 15 來判斷是否是頁面異常（page fault）：
  • 13 表示加載時的頁面異常（load page fault）
  • 15 表示存儲時的頁面異常（store page fault）
• r_stval() 返回 RISC-V 的 stval 寄存器的值，它表示觸發異常的虛擬地址。
• 你可以參考 vm.c 中的 uvmalloc() 函數的代碼，這是 sbrk() 通過 growproc() 最終調用的函數。你會用到以下兩個函數：
  • kalloc()：用于分配一頁物理內存。
  • mappages()：用于將虛擬地址映射到物理頁。
• 使用 PGROUNDDOWN(va) 宏將發生異常的虛擬地址向下對齊到頁邊界。
• uvmunmap() 默認會觸發 panic；你需要修改它的行為，使其在取消映射時不會因為某些頁未映射就 panic。
• 如果內核崩潰了，你可以查找 kernel/kernel.asm 中的 sepc 來定位異常發生的位置。
• 使用你在頁表實驗（pgtbl lab）中寫的 vmprint 函數來打印頁表內容，輔助調試。
• 如果你遇到 incomplete type proc 的錯誤，記得先 #include "spinlock.h"，再 #include "proc.h"。

如果一切順利，你的懶惰分配（lazy allocation）代碼應該能使 echo hi 正常工作。在執行過程中，系統應該至少會發生一次頁面異常（觸發懶惰分配），也可能會觸發兩次。

2.2 實現

• 按照官網提示，在trap.c 中的usertrap 的 printf else分支前添加處理代碼
• 如果 是 13（load page fault）或 15（store page fault）我們就調用 uvmalloc() 函數分配物理內存，并映射用戶頁表。

// ...
} else if((which_dev = devintr()) != 0){// ok
} else if(r_scause() == 13 || r_scause() == 15) {uint64 va = r_stval();if (uvmalloc(p->pagetable, PGROUNDDOWN(va), PGROUNDDOWN(va) + PGSIZE) == 0)p->killed = 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;
}

值得注意的是，因為我們是利用缺頁異常實現延遲分配，所以 uvmunmap 中的無法根據虛擬地址找到實際物理頁面的情況需要取消panic，改為continue，否則就會觸發panic：

然后我們運行一下：

三、Lazytests and Usertests

3.1 說明

我們為你提供了一個名為 lazytests 的 xv6 用戶程序，它會測試一些特定情況，這些情況可能會對你的懶惰內存分配器造成壓力。請修改你的內核代碼，使 lazytests 和 usertests 中的所有測試都能通過。

你需要處理以下幾種情況：

• 處理 sbrk() 的負數參數：即當進程釋放內存時，要正確縮小進程的地址空間。
• 如果進程在訪問一個高于 sbrk() 分配范圍的虛擬地址時發生缺頁異常，應終止該進程。
• 正確處理 fork() 中父進程到子進程的內存拷貝，包括懶惰分配頁的復制。
• 當進程將一個來自 sbrk() 的合法地址傳遞給系統調用（如 read 或 write），但該地址尚未實際分配物理內存時，也應正確處理并觸發分配。
• 正確處理內存耗盡的情況：如果在頁面異常處理函數中 kalloc() 失敗，表示系統已無可用內存，應該終止當前進程。
• 處理位于用戶棧下方的非法頁面上的訪問異常。

你的實現是合格的，如果你的內核能夠通過 lazytests 和 usertests 的全部測試，如下所示：

$ lazytests
lazytests starting
running test lazy alloc
test lazy alloc: OK
running test lazy unmap...
usertrap(): ...
test lazy unmap: OK
running test out of memory
usertrap(): ...
test out of memory: OK
ALL TESTS PASSED$ usertests
...
ALL TESTS PASSED$

3.2 實現

先跑一下看看哪里報錯，結合官網提示去調：

3.2.1 lazytests

~~然后它就死了。~~但是給了很多信息。

我們先看uvmcopy，原代碼：

• 這個函數會把給定的父進程頁表拷貝內存到子進程頁表，頁表和物理內存都進行拷貝
• 官網提示我們正確完成拷貝包括懶惰分配頁的復制

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
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;
}

然后注意到 panic(“uvmcopy: page not present”);被觸發顯然是因為遇到了我們假分配的頁面

那就很簡單了，注釋掉panic，改為continue即可。

再跑一遍：

它又死了，這次報錯在 freewalk

我們查看一下源碼：

• 它會遞歸釋放頁表頁
• 所以葉子映射都必須已經釋放

// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void freewalk(pagetable_t pagetable)
{// there are 2^9 = 512 PTEs in a page table.for(int i = 0; i < 512; i++){pte_t pte = pagetable[i];if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){// this PTE points to a lower-level page table.uint64 child = PTE2PA(pte);freewalk((pagetable_t)child);pagetable[i] = 0;} else if(pte & PTE_V){panic("freewalk: leaf");}}kfree((void*)pagetable);
}

鈉根據該函數的描述，我們知道說明有葉子節點沒有被釋放。

這其實是比較奇怪的，然后看到官網這一條提示：

• 如果進程在訪問一個高于 sbrk() 分配范圍的虛擬地址時發生缺頁異常，應終止該進程。

于是合理懷疑是因為測試點里面有對于非法地址的訪問，觸發缺頁異常，然后讓我們誤以為是懶惰分配，從而分配了物理內存。

于是在最早的usertrap中的邏輯中加一個地址界限的判斷：

這次就沒問題了：

3.2.2 usertests

同樣的，我們根據錯誤找問題：

通過vscode找到這個sbrkarg函數是在 usertest.c 下

• 用來測試對分配內存的讀寫
• 我們報錯是在write的地方報錯了

// test reads/writes from/to allocated memory
void sbrkarg(char *s)
{char *a;int fd, n;a = sbrk(PGSIZE);fd = open("sbrk", O_CREATE|O_WRONLY);unlink("sbrk");if(fd < 0)  {printf("%s: open sbrk failed\n", s);exit(1);}if ((n = write(fd, a, PGSIZE)) < 0) {printf("%s: write sbrk failed\n", s);exit(1);}close(fd);// test writes to allocated memorya = sbrk(PGSIZE);if(pipe((int *) a) != 0){printf("%s: pipe() failed\n", s);exit(1);} 
}

官網有著這樣一條提示：

• 當進程將一個來自 sbrk() 的合法地址傳遞給系統調用（如 read 或 write），但該地址尚未實際分配物理內存時，也應正確處理并觸發分配。

那其實很好理解了，我們沒有對 write 訪問假分配時進行分配物理內存。

這個就需要我們去查看write 系統調用的實現，以及寫邏輯。

先找到 sys_write

uint64 sys_write(void)
{struct file *f;int n;uint64 p;if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)return -1;return filewrite(f, p, n);
}

發現調用了 filewrite

然后查看 filewrite 發現它又調用了 writei 來進行寫邏輯

writei 又調用了either_copyin，而either_copyin又調用了copyin

最終在 copyin 中發現了對于pagetable 的訪問

總而言之是這么個邏輯：

sys_write() -> filewrite() -> writei() -> either_copyin() -> copyin() -> walkaddr()

查看 walkaddr：

• 果然有問題，如果訪問到空頁或者無效頁，它直接返回0了（0代表未映射）

uint64 walkaddr(pagetable_t pagetable, uint64 va)
{pte_t *pte;uint64 pa;if(va >= MAXVA)return 0;pte = walk(pagetable, va, 0);if(pte == 0)return 0;if((*pte & PTE_V) == 0)return 0;if((*pte & PTE_U) == 0)return 0;pa = PTE2PA(*pte);return pa;
}

我們特判嘗試物理分配即可：

值得注意的是兩個頭文件的引用順序：

測試一下：