前言

我們在前面花了 5 個篇章對於 trap 進行了完整的介紹，並且瞭解了 trap 處理得具體流程，今天我們將看到 page fault 所造成的 trap，並且後面提及我們可以通過 page fault 所造成的 trap，進行一些有趣的操作。

回顧虛擬記憶體

我們之所以使用虛擬記憶體，而不去使用物理實體記憶體，主要是基於以下考量

• Isolation: 前面我們看到每一個 process 都有自己的記憶體空間，而這一件事情是因為使用了虛擬記憶體才能夠達成的。也因此不會發生一個 process 因為一些操作造成其他 process 的資料遭到修改。而隔離性也可以在 kernel space 和 user space 之間可以看到。
• Level of indirection: 這個概念可以回顧下面這一張圖
  
  上面這張圖是 process 與物理實體記憶體之間的映射關係，可以看到 trampoline 這個位於 kernel virtual address 的地址空間會映射到每一個 process 上，以及 kernel virtual address 存在 guardpage 用來保護 kernel stack page。而上面這一些映射關係，都是在最一開始配置完成之後便不會再進行更動。

而通過 page fault，我們可以試著讓上面的映射關係從靜態變成動態的，通過 page fault 去動態的設置 page table。而在先前我們有看到一些 page fault 的相關例子，下面我們將整理 page fault 相關的知識。

• page fault 發生的記憶體地址 (也被稱為 Bad Address): 當發生 page fault 時，xv6 會印出發生錯誤的虛擬記憶體地址，而這個地址會儲存在 stval CSR 中。當 user space 的 process 發生了 page fault，page fault 會使用到 trap 的相關機制，而在 user space 底下發生的 trap 會使用 usertrap() 作為 trap handler，程式會切換到 supervisor mode，並在 trap 會將出錯的虛擬記憶體地址入到 stval CSR 中，這些部分可以在 Trap (supervisor mode) 篇章中可以看到 trap 硬體層面的說明 (before trap handler)。
• page fault 發生的原因: 上面說到當發生了 page fault 時，會觸發到 trap，而 trap 觸發的原因我們可以通過 sscause CSR 得知，在其中可以知道 trap 進入到 supervisor mode 的原因，從 RISC-V 的文件中可以看到下表
  
  在上表我們可以得知 12 為 指令所造成的 page fault 等等。trap 和其他的 Exception。在 usertrap() 中可以看到通過讀取 stval 來得知發生未知的 trap 發生的地址 (通過 scause 得知)

printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
setkilled(p);

• 觸發 page fault 的指令的記憶體地址 : 在 scause 這一張表中，我們知道 12 為由指令所造成的 page fault，而我們想要得知指令所觸發的記憶體地址，而指令觸發了 page fault，page fault 會觸發 trap，我們知道 trap 會儲存發生 trap 之前的 program counter，因此我們可以通過儲存 program counter 的暫存器得知造成 page fault 的指令記憶體地址，該暫存器為 sepc CSR 以及在 trapframe 中的 epc。
  我們得知觸發 page fault 的指令後，就可以在對 page table 的錯誤修補完成後，繼續的執行該指令了。

而通過 page fault，我們可以實現出下面這些功能

• lazy allocation
• copy-on-write fork
• demand paging
• memory mapped files

page fault in xv6

在 xv6 中 page fault 的處理非常的簡單，就是直接將該 process kill，而我們在 trap from supervisor mode 中看到，如果 page fault 發生在 kernel space 中，我們會產生一個 panic，而實際上在現代作業系統中，page fault 有許多種應用，如上面所列出的，而下面我們將看到如何使用 page fault 完成 lazy page allocation 的操作。

lazy page allocation

下面我們回顧先前看到的 process virtual address space

在 process 的結構，struct proc 中 sz 表示 process 的 memory 大小，而 sbrk() 為 System call，能夠讓 process 擴大自己的 heap，當一個 process 啟動時，sbrk 會指向到 heap 區域的最底端，而 p->sz 也是指向到相同的位置，表示在 process 最一開始時，在 heap 中沒有可用的記憶體空間，需要通過sbrk() System call 通過一個一個 bytes 去增加可用空間，而我們可以將先前在 C 語言的 Memory layout 的概念結合。

(xv6 中 process 的 heap 和 stack 的相對位置和 C memory layout 是反過來的)
最一開始 sbrk 指向的為 program break 的位置，而根據 linux man page 的說明，sbrk()與brk()這兩個 System call 的作用如下

brk() and sbrk() change the location of the program break, which
defines the end of the process's data segment (i.e., the program
break is the first location after the end of the uninitialized
data segment).  Increasing the program break has the effect of
allocating memory to the process; decreasing the break
deallocates memory.

program break 的位置位於 data segment 結束的位置，也就是如上圖所標示位置，而 brk() 與 sbrk() 會改變 program break 的位置，增加 process 可以使用的記憶體空間數量。而 brk() 傳入的參數為記憶體地址，會將 program break 移動到該記憶體地址。sbrk() 則是移動 program break 傳入的 bytes 位移。

在 xv6 中的 sbrk() 預設為 eager allocation。意思為程式會立即分配自己所需要使用到的物理記憶體空間，通常為了避免一些極端情況無法處理，概念上為存取 arr[10000] 的數值，為了避免無法處理這種情況，應用程式在申請記憶體空間時都會傾向申請較大的物理記憶體空間，即使實際上使用可能不會使用到這麼多，這樣的想法為 eager allocation，而我們可以使用 lazy allocation 來解決 eager allocation 浪費空間的問題。

當呼叫 sbrk()時，kernel 會分配一些物理記憶體分頁，接著將這一些記憶體分頁映射到 user space process 的記憶體空間，接著將分配的記憶體內容初始化為0，接著結束 sbrk() System call。process 通過 sbrk() 去增加或是減少記憶體的使用量。下面我們可以看到 xv6 中 sys_sbrk()的實作。

uint64
sys_sbrk(void)
{
  uint64 addr;
  int n;

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

實際上 sys_sbrk() 不會進行任何操作，這是基於 lazy allocation 的概念，而 sys_sbrk() 的目標就是移動 program break 的位置，最直觀的做法就是將 p->sz 加上 n，就可以完成移動 program break 的操作，n 表示要分配的 page 數目，但是在這個時間點，kernel 並不會分配實體物理記憶體分頁，而是在之後某一個時間點才會完成分配的操作，而在實體物理記憶體分頁分配之前，如果有其他程式去使用了 p->sz + n 的記憶體，由於還沒有物理記憶體分頁，這時候就會觸發 page fault。page fault 發生的地址會小於目前的 p->sz，也就是先前的 p->sz + n，同時會大於 stack 的記憶體地址，我們可以通過這個地址知道這是一個發生在 heap 的位置。

所以對於 page fault handler，需要使用 kalloc() 分配物理記憶體分頁，初始化分頁的內容為 0，並且將該分頁映射到 process 的 page table，接著 trap 結束時，回到原先指令的位置，繼續執行指令 (這時候我們已經完成了實體物理記憶體分頁的分配)，就能夠順利執行了。

目前上方的 sys_sbrk() 會通過 growproc(n) 調整 program break 以及去分配物理記憶體分頁，而我們可以實驗看看只有調整 program break 的位置，接著不去分配物理記憶體分頁，查看是否會發生 page fault。只要將 sys_sbrk() 修改成以下便能夠觸發。

uint64
sys_sbrk(void)
{
  uint64 addr;
  int n;

  argint(0, &n);
  addr = myproc()->sz;
  myproc()->sz = myproc()->sz + n;
  return addr;
}

可以知道在 usertrap() 中，由於沒有找到 scasue CSR 對應的 trap 發生原因，因此印出錯誤訊息，由 scause 可以知道 expection code 為 15，對應到的事件為 store page fault，接著再看到 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 call

    if(killed(p))
      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 sepc, scause, and sstatus,
    // so enable only now that we're done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    setkilled(p);
  }

可以看到我們沒有對 scause exception code 15 進行對應的處理，因此，我們需要在 scasue 為 15 時，使用 kalloc() 分配實體物理記憶體頁面，接著初始化，映射後，回到 trap 觸發的地方繼續執行並完成指令，我們需要在 usertrap() 中新增判斷，我們可以修改usertrap() 後看看是否有成功處理到這個 page fault。

if(r_scause() == 15)
{
    printf("catch\n");
}

可以看到有成功捕捉到這個 page fault，而我們看到 sepc CSR 的值代表的是發生 page fault，造成 trap 的記憶體地址，stval 為虛擬記憶體地址，我們可以通過 kernel.asm 查看發生 trap 的具體指令

if(n > 0){
    800012ac:   00904f63            bgtz    s1,800012ca <growproc+0x3c>
  }

page fault 觸發的 trap 指令發生在 growproc()中，而growproc()中有涉及malloc()等操作，因此引發了錯誤 (在尚未獲得物理記憶體分頁的位置嘗試寫入，因此跳出 not mapped 的訊息)。

我們通過上圖得到 0x800012ac 這個記憶體地址發生 trap，我們在先前的 paging 章節中看到 0x80000000 為開始的記憶體地址，接著會有一塊一塊的 page，page 大小為 4096 bytes，也就是 0x00001000，因此 0x00004008 / 0x00001000 可以得知位於第 5 個 page，xv6 的 Shell 會有 4 個page，發生 page fault 的地址在 Shell 持有的 page 以外。

而我們在 usertrap() 中已經成功捕捉到 page fault 了，接著我們將使用 lazy allocation 的方式對 page fault 進行處理。

reference

SiFive FU540-C000 Manual v1p0
xv6-riscv
Operating System Concepts, 9/e
RISC-V xv6 Book
Page Fault
Page Fault Exception Handler