Lab6 Copy-on-Write Fork for xv6 紀錄

題目的意圖

fork() 時會把整個 page table 也複製給 child, 但是大多數時候，child 並不會使用這個 page table
常常都是在 fork() 去執行 exec() 這時 exec() 又會把原本的 page table 蓋掉, 這樣太浪費 physical memory 了，
比較好的作法是：fork() 時先讓 parent 跟 child 都指向同樣的 pa , 直到要寫入時，才真正的把 physical memory 的內容複製一份

大致上的流程:

1. fork() 使用 uvmcopy() 把 page table 複製過去

   • 在這個 lab 中，我們希望 fork() 後 child 跟 parent 的 page table 都是 map 到相同的 pa

2. 現在的 uvmcopy() 就是把 old 的東西複製到 new

3. 根據題目的需求，我們必須要做到以下幾件事情:

   • 把 new 跟 old 的 pte_w 都關掉，這樣想要寫入的時候，就會進入 trap() 處理
   • new 跟 old 都要立起 pte_c，這樣在 trap() 中就可以認出真正的 write page fault
   • 遇到 write page fault 時，check pte_c
   • ref count 在 kfree() 的時候減少 1
   • ref count 在 kalloc() 的時候設為 1
   • ref count 在 uvmcopy() 的時候設增加 1:

幾個重要的時間點:

fork()

• fork() 使用 uvmcopy() 把 child 的 page table 建立出來，
• fork() 結束之後，child 跟 parent 會得到相同的 virtual memory

uvmcopy()

fork() 使用 uvmcopy() 把 parent 的 page table 複製一份給 child

• 原版 uvmcopy(): parent 的 memory 內容真正的複製出來 (使用了 kalloc())
• cow 的版本: 只有把 page table 複製給 child, prarent 與 child 實際上是指到同樣的 physical memory

write page fault

在 kernel/trap.c: usertrap() (r_scause() == 15)

• 遇到 write page fault ，並且 pte_c off: 真正的 page fault
• 遇到 write page fault ，並且 pte_c on: 準備執行 copy on write
  • 這時候才要真正的把 page 的內容複製一份出來，因為

kalloc() 與 kfree()

原版執行 kfree() 的時候就是真的把這個 page free 掉了
可是 cow 的版本中會有問題

使用 cow 了話，有可能會有很多個 page table 指向同一個 page，
而這時候什麼時候要 free 掉這個 page 就成為了一個很大的問題
因為其中一個 process 要 free 掉這個 page 時，這個 page 可能正同時被其他 process 使用

解決方法：使用 counter 去計算各個 page 被多少個 process 使用，如果沒有任何 process 使用，
才需要真正的 free 掉這個 page

破解步驟

1. 在 uvmcopy() 中，刪掉 child 以及 parent 的所有 pte_w
   • 原本的 pte_w 所記載的資訊去哪了
2. 之後遇到 write page-fault 時
   • 並不是真正的 page-fault，他原本是 writeable 的
   • kalloc() 出一個新的 page 並且把 old page 的內容複製到 new page，並且 set pte_w
   • 原本 readonly 的區域，child 就使用 old page 的內容就好
   • 如果 child 想要修改 readonly 的內容，一樣要把他 kill 掉
3. 要新增 reference count 的功能
4. 在 copyout() 中使用跟 page fault 時一樣的方法
   • 也就是並不是真正的 page fault 的意思

需要修改與新增的 function

• uvmcopy():
• usertrap():
• uncopied_cow(): 還沒有被 copy 出來的 cow page
• cow_alloc():
• copyout():

實驗紀錄

1. modify uvmcopy() to map the parent's physical pages into the child, instead of allocating new pages. clear pte_w in the ptes of both child and parent for pages that have pte_w set.

• 修改 uvmcopy(), 讓 fork() 使用 uvmcopy() 複製 parent 的 va 內容給 child 時
  讓 child 的 page_table map 到 parent 的 physical page

讓 usertrap() 有辦法分辨真正的 write page fault 與 copy-on-write

• 使用 PTE_C
• 原本是 PTE_W on 的 page:
  • PTE_W 變成 off
  • PTE_C 變成 on
• 原本是 PTE_W off 的 page
  • PTE_W 維持原本的 off
  • PTE_W 維持原本的 off

如此一來 usertrap() 遇到 r_scause() ==並且 PTE_C 為 on 15，
就進入 copy-on-write 的情形處理

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);
    if (*pte & PTE_W) {
      *pte &= ~PTE_W; // for copy on write: clear parent's PTE_W
      *pte |= PTE_C; // for copy on write: set PTE_C
    }
    flags = PTE_FLAGS(*pte);
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    mem = (char *) pa;
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
    prefcnt_inc(pa);
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

2. modify usertrap() to recognize page faults. when a write page-fault occurs on a cow page that was originally writeable, allocate a new page with kalloc(), copy the old page to the new page, and install the new page in the pte with pte_w set. pages that were originally read-only (not mapped pte_w, like pages in the text segment) should remain read-only and shared between parent and child; a process that tries to write such a page should be killed.

修改 userteap()

• kernel/trap.c: usertrap():

// ...
  } else if((r_scause() == 15) && uncopied_cow(p->pagetable, r_stval())){
    if (cow_alloc(p->pagetable, r_stval()) < 0)
      p->killed = 1;
// ...

• kernel/vm.c: uncopied_cow()

int
uncopied_cow(pagetable_t pagetable, uint64 va)
{
  if (va >= MAXVA)
    return 0;
  pte_t *pte;
  if ((pte = walk(pagetable, va, 0)) == 0)
    return 0;
  if ((*pte & PTE_V) == 0)
    return 0;
  if ((*pte & PTE_U) == 0)
    return 0;
  return (*pte & PTE_C);
}

• kernel/vm.c: cow_alloc()

int
cow_alloc(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;
  uint flags;
  char *mem;

  va = pgrounddown(va);
  if (pte = walk(pagetable, va, 0) == 0)
    return -1;
  pa = pte2pa(*pte);
  flags = pte_flags(*pte);
  flags |= pte_w;
  if ((mem = kalloc()) == 0)
    return -1;
  memove(mem, (char *)pa, pgsize);
  if (mappages(pagetable, va, pgsize, (uint64)mem, flags) != 0) {
    kfree(mem);
    return -1;
  }
  return 0;
}

3. ensure that each physical page is freed when the last pte reference to it goes away – but not before. a good way to do this is to keep, for each physical page, a "reference count" of the number of user page tables that refer to that page. set a page's reference count to one when kalloc() allocates it. increment a page's reference count when fork causes a child to share the page, and decrement a page's count each time any process drops the page from its page table. kfree() should only place a page back on the free list if its reference count is zero. it's ok to to keep these counts in a fixed-size array of integers. you'll have to work out a scheme for how to index the array and how to choose its size. for example, you could index the array with the page's physical address divided by 4096, and give the array a number of elements equal to highest physical address of any page placed on the free list by kinit() in kalloc.c. feel free to modify kalloc.c (e.g., kalloc() and kfree()) to maintain the reference counts.

因為一個已分配的 memory 可能會被多個 process 使用，我們必須要紀錄這個 page 有多少個 process 使用才行，如果使用人數為 0 時，才要真正的把這個 page 刪除掉。

• kinit() 時初始化
• kalloc() 時增加
• kfree() 時增加

複習 xv6 的 memory layout

• 從 kinit() 可以看到，kalloc() 可以使用的範圍就存放在 end ~ phystop
  • end: 從 kernel/kernel.ld 可以得知他被存放在 kernel 的 .text 與 .data 之後
    • end 的位置不太確定，反正 linker 會幫我們弄好
    • 從圖上來看了話，end 是 free memory 的開始
    • free memory 也就是 kalloc() 可以使用的範圍
  • phystop: phycical address 的實際上的最大的 address = 0x88000000

從 end 與 phystop
先定義一些 macro

#define pa2refindex(pa) ((pgrounddown(pa) - kernbase) / pgsize)
uint prefcnt[(phystop - kernbase) / pgsize];

• kfree()

• kalloc()

  • 把最後回傳的那個 page 對應到的 count 的值設為 1
  • 請注意，增加 count 是在 fork() 做的事情

• init

• kernel/kalloc.c:

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

#define NUM_PREF_COUNT (PHYSTOP - KERNBASE) / PGSIZE
#define PA2REFIDX(pa) ((PGROUNDDOWN(pa) - KERNBASE) / PGSIZE)
#define PA2CNT(pa) prefcnt.count[PA2REFIDX((uint64) pa)]

struct {
  struct spinlock lock;
  uint count[NUM_PREF_COUNT];
} prefcnt;

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&prefcnt.lock, "prefcnt");
  freerange(end, (void*)PHYSTOP);
}

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    acquire(&prefcnt.lock);
    PA2CNT(p) = 1;
    release(&prefcnt.lock);
    kfree(p);
  }
}

// Free the page of physical memory pointed at by pa,
// 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(&prefcnt.lock);
  if (--PA2CNT(pa) <= 0) {
    // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);

    r = (struct run*)pa;
    acquire(&kmem.lock);
    r->next = kmem.freelist;
    kmem.freelist = r;
    release(&kmem.lock);
  }

  release(&prefcnt.lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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
    acquire(&prefcnt.lock);
    PA2CNT(r) = 1;
    release(&prefcnt.lock);
  }
  return (void*)r;
}

void
prefcnt_inc(uint64 pa)
{
  acquire(&prefcnt.lock);
  PA2CNT(pa)++;
  release(&prefcnt.lock);
}

4. modify copyout() to use the same scheme as page faults when it encounters a cow page.

copy 出去的時候，不要指到跟 kernel 一樣的 pa, （要自己 copy 一份給 user mode 使用）

• kernel/vm.c: copyout():

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if (uncopied_cow(pagetable, va0)) {
      if (cow_alloc(pagetable, va0) == -1)
        return -1;
    }
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

debug

• freelist 並沒有被正確的初始化

  • 解決方法: pa2cnt(p) = 1 in freerange

• panic: mappages: remap

  • 不應該出現 remap
    在

2  0x0000000080000e8e in cow_alloc (pagetable=0x87f73000, va=16384)
    at kernel/vm.c:487

出現了 panic: mappages: remap 的錯誤

照裡來說不應該出現 remap 的情況
cow_alloc() 由 usertrap() 遇到 write page fault 時呼叫
在 cow_alloc() 的情況下應該要

在 cow_alloc() 中的 uvmunmap() 必須要 do_free 這樣

先用執行 cowtests 來發現錯誤會比較容易

• 現在 pipe() failed 來看看是為什麼
  • 使用 gdb 得知為 sys_pipe() 中的 copyout() 發生了錯誤
  • 而且遇到的
    [] 使用紙筆畫出 filetest() 的流程
    [] 強烈建議好好檢查 cowalloc() in copyout()
    [] 不可 write 的 page 就維持不可以 write

reference

6.1810
lab cow
mit 6.s081 xv6 lab6 cow 实验记录
https://five-embeddev.com/riscv-isa-manual/latest/supervisor.html#sec:scause
11分鐘讀懂 linker scripts