前言

在前面我們介紹了 page fault 以及 lazy page allocation 的概念，而我們在 usertrap() 中通過 scause CSR 得到了 trap 發生原因的編號為15，同時通過在 usertrap() 新增部分程式碼成功 catch 了該 page fault 所發生的 trap，下面我們將針對該 trap 進行一些處理，諸如分配實體物理記憶體分頁等等。

lazy page allocation (增加 heap 大小)

在昨天，我們目前在 usertrap()中 scause = 15 如下

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

首先我們需要使用kalloc()分配實體物理記憶體分頁，而下面我們看到kalloc()的程式碼

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

可以看到kalloc()會回傳我們分配到的實體物理記憶體分頁所在的記憶體地址，而如果kalloc()回傳0，表示我們可用的物理實體記憶體分頁已經使用完畢，沒有多餘的記憶體分頁可以使用，也就是 Out of Memery (OOM)，我們要做的就是將該 process 給 kill。

如果成功分配，我們要將該記憶體分頁中的內容給清空。

if(r_scause() == 15 || r_scause() == 13){
    uint64 ka = (uint64)kalloc();
    if(ka == 0)
    {
        p->killed = 1;
    }
    else
    {
        memset((void*)ka, 0, PGSIZE);
    }
}

上面我們成功分配了實體物理記憶體分頁，接著我們要將該記憶體分頁映射到 process 的 page table 中，我們先前通過了 sscause CSR 得知發生 page fault 導致 trap 的虛擬記憶體地址為 0x00004008，我們下面要做的操作就是將該虛擬記憶體地址依照記憶體分頁大小進行對齊，在這邊我們對這個虛擬記憶體地址依照分頁的大小進行向下取整，這一件事情通過 PGROWNDDOWN() 巨集來完成。

接著通過這個向下取整的虛擬記憶體地址映射到 process page table。並且完成 PTE 的權限相關的 flag 設置。

if(r_scause() == 15 || r_scause() == 13)
{
    uint64 ka = (uint64)kalloc();
    uint64 va = r_stval();
    printf("page fault %p\n", va);
    if(ka == 0)
    {
        p->killed = 1;
    }
    else
    {
        memset((void*)ka, 0, PGSIZE);
        va = PGROUNDDOWN(va);
        if(mappages(p->pagetable, va, PGSIZE, ka, PTE_W | PTE_U | PTE_R) != 0)
        {
            kfree((void*)ka);
            p->killed = 1;
        }
    }
}

接著我們重新執行，會發現以下問題

我們發現發生了兩次 page fault，位於虛擬記憶體地址 0x00004008 以及 0x00013f48。這裡出現了 not mapped 的錯誤，在前面我們看到我們在 sys_sbrk() 中使用 lazy page allocation 的策略時發生 page fault 導致 trap 的 stval CSR 的值為 0x00004008，因此我們從上面圖片中的結果可以得出在處理發生位於 0x00004008 的 page fault 時，又引發了另外一個位於 0x00013f48 的 page fault。

這邊在 uvmunmap() 中發生了 not mapped 的錯誤，我們可以追蹤 uvmunmap() 來查看

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 + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

可以看到 uvmunmap() 嘗試獲得實體物理記憶體分頁時，由於 PTE 沒有對應到的實體物理記憶體分頁，也就是 PTE 中 V 域沒有設置，為 Invaild，因此引發了 not mapped 的錯誤，而 uvmunmap() 傳入的虛擬記憶體地址為先前經過 lazy page allocation 的記憶體地址，但是該記憶體地址還沒有分配到實體物理記憶體分頁，因此造成了上面這個錯誤。

而上面這個錯誤實際上是一個可預期的錯誤 (由於我們使用 lazy page allocation)，因此這裡觸發的 panic 我們可以忽略 (因為我們在 page fault handler 會分配實體物理記憶體分頁並且映射到 process page table 進行處理)。

if((*pte & PTE_V) == 0)
      continue;

而在執行 fork() System call 時，uvmunmap() 也需要進行同樣得處理。

接著重新執行一次，這裡我們以 echo hi 為例 (process 會 fork() 接著 exec() 執行 echo，過程中會使用到sbrk())

這裡可以看到我們便執行成功了，成功實現了 lazy page allocation。

而整個 lazy page allocation 的流程如下

• sys_sbrk() 變更 program break 位置，變成 p->sz + n，但還沒分配實體物理記憶體分頁。
• 當下面應用程式存取了 p->sz 到 p->sz + n 之間的記憶體地址，就會觸發 page fault，因為沒有對應到的實體物理記憶體地址，也就是 PTE 的相關權限控制的 flag 沒有設置。
• 上面應用程式觸發了 page fault，接著會進入到 page fault 的 handler，類似於 trap handler，我們在 page fault handler 中分配實體物理記憶體分頁，並且映射到 process page table。
• 接著上方 trap 結束之後，會回到 process 指令執行失敗處，接著會繼續執行指令，而由於 page fault handler 已經完成了實體物理記憶體分頁的分配，因此這時候指令便能夠執行成功了，而對於 process 來說，過程中這一些實體物理記憶體分頁的操作都是不可見的，也就是實現了隔離性的部分。

lazy page allocation (減少 heap 大小處理)

我們也可以通過傳入負數去移動 program break 的位置，從而去減少 heap 的大小，我們下面回憶到前面 process virtual address space。

這裡需要注意到，如果我們輸入一個數字，這個數字會導致 heap 將 stack 的區域覆蓋，我們需要避免這一件事情的發生，所以我們需要再sys_sbrk()中加入判斷，如果欲改變的 program break 的位置小於 stack pointer (指向stack) 的頂部，則出現錯誤。

if(addr + n < p->trapframe->sp)
    return -1;

只要輸入的 n 為負數，我們就使用 uvmdealloc 來減少 heap 的空間。

if (n < 0)
    uvmdealloc(p->pagetable, p->sz, p->sz + n);

發生在 supervisor mode 底下的 trap

前面我們看到我們使用發生在 user mode 底下的 trap，使用 trap handler 來處理 page fault，並在 usertrap() 中分配實體物理記憶體分頁，但是如果現在 page fault 所引發的 trap 發生在 supervisor mode 底下，會使用到 kerneltrap() 進行處理，這時候我們就需要在 kerneltrap() 中加入一些實體物理記憶體分頁的處理程式。

回顧前面 write() 這個 System call 時，會如同前面所提及的，經過 syscall()，接著通過 SYS_WRITE 找到 sys_write()，接著 sys_write() 會去呼叫 filewrite()，而在 filewrite() 中，可以看到根據不同的檔案類型會觸發到不同的行為，我們在 UART 中看到如果檔案類型為裝置時，會進行的對應處理，我們可以看對於其他類型檔案，filewrite() 所做的相對應的處理。

int
filewrite(struct file *f, uint64 addr, int n)
{
  int r, ret = 0;

  if(f->writable == 0)
    return -1;

  if(f->type == FD_PIPE){
    ret = pipewrite(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].write)
      return -1;
    ret = devsw[f->major].write(1, addr, n);
  } else if(f->type == FD_INODE){
    // write a few blocks at a time to avoid exceeding
    // the maximum log transaction size, including
    // i-node, indirect block, allocation blocks,
    // and 2 blocks of slop for non-aligned writes.
    // this really belongs lower down, since writei()
    // might be writing a device like the console.
    int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;
    int i = 0;
    while(i < n){
      int n1 = n - i;
      if(n1 > max)
        n1 = max;

      begin_op();
      ilock(f->ip);
      if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
        f->off += r;
      iunlock(f->ip);
      end_op();

      if(r != n1){
        // error from writei
        break;
      }
      i += r;
    }
    ret = (i == n ? n : -1);
  } else {
    panic("filewrite");
  }

  return ret;
}

通過傳入的 file 結構判斷其檔案類型，我們大致上可以區分成三個類型，分別為 FD_PIPE, FD_DEVICE, FD_INODE，而對於 FD_INODE 來說，我們會呼叫到 writei() 這個函式，而這個函式會呼叫到 either_copyin() 這個函式，接著 either_copyin() 會呼叫到 copyin()，而 copyin() 我們在 trace exec System call 時我們可以看到當我們位於 supervisor mode 底下時，我們需要通過 walkaddr() 得知虛擬記憶體地址對應到的物理記憶體地址。

我們可以想到，我們上面使用到 lazy page allocation 的策略，因此在 walkaddr() 中，找到的 PTE 勢必對應的權限控制的 flag 尚未設置，這時候可能就會觸發一些預期中的 panic，而我們下面需要對這一些情況進行一些處理，下面為 walkaddr() 的相關實作

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;
}

當 PTE 為 0，或是 PTE_V 為 0 或是尚未設置時，都會回傳 0，導致 copyin() 認為 walkaddr() 發生了錯誤，而實際上這個錯誤是由 lazy page allocation 所造成的，因此，我們在 walkaddr() 需要進行正確的處理，回傳分頁所對應到的物理記憶體地址。

而處理的方式如同 usertrap()，這邊我們在 walkaddr() 傳入了虛擬記憶體地址，我們需要為這個虛擬記憶體地址分配實體物理記憶體分頁，接著將這個地址回傳，完成類似於 usertrap() 中所完成的操作。

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 || (*pte & PTE_V) == 0)
    //TODO
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

首先我們要對傳入的虛擬記憶體地址進行判斷，判斷是否會超出目前 process memory 的大小，以及是否會覆蓋掉 process 的 stack memory page。

struct proc *p = myproc();
if(va >= p->sz || va < p->trapframe->sp)
    return 0;

接著我們需要分配一個實體物理記憶體分頁，並且初始化該記憶體分頁內容，並將這個實體物理記憶體分頁映射到虛擬記憶體所在的分頁，接著將 PTE 相關權限的 flag 進行設置，以便提供給 process 使用。

char *memPage = kalloc();
if(memePage == NULL) 
    return 0;
if(mappages(pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)memPage, PTE_W|PTE_R|PTE_U) != 0) 
{
    kfree(memPage);
    return 0;
}

這樣我們就處理完成如果發生在 kernel 底下的 trap，trap handler 對於 lazy page allocation 的處理了。

reference

RISC V 的中斷與異常處理
The RISC-V Instruction Set Manual
An Embedded RISC-V Blog
SiFive FU540-C000 Manual v1p0
xv6-riscv
Operating System Concepts, 9/e
RISC-V xv6 Book
Are some allocators lazy