---
# System prepended metadata

title: Lab5 Lazy 紀錄

---

# Lab5 Lazy 紀錄

## 在處理 page fault 時，我們需要注意的幾件事情
* `stval`: 造成 page fault 的 virtual memory
* `sepc`: 造成 page fault 的 program counter
* instruction: 當下是正在執行什麼 instruction (?)
### registers
1. `stval`: va cause page fault
2. `scause`: the type of fault
    * Read
    * Write
    * Instruction
3. `sepc`: the va of instruction

## Eliminate allocation from `sbrk()`
這個 assignment 就只要根據題目的指示，把 `growproc()` 給註解掉，並且記得把 `myproc()->sz` 增加 `n` bytes

```Clike=
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  // if(growproc(n) < 0)
  //   return -1;
  myproc()->sz += n;
  return addr;
}
```
改好之後執行 `echo hi` 會爆出以下的錯誤
```=
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
            sepc=0x00000000000012ac stval=0x0000000000004008
panic: uvmunmap: not mapped
```
##### 錯誤訊息解釋
* `usertrap()`:
    * 這些錯誤訊息是從 `kernel/trap.c: usertrap()` 印出來的
* `unexpected scause 0x000000000000000f`:
    * `usertrpa()` 處理這個 trap 時，`scause` = 0x0f 此情況並沒有對應的程式碼
* `pid = 3` 是 `echo hi` 的 pid
    * 註: `sh` 的 pid 是 2
* `sepc=0x00000000000012ac`:
    * 對應到 `sh.asm` 中的 `12ac: ld	ra,56(sp)`
    * 為什麼 `sepc` 停留在 `sh` 中而沒有進入到 `echo` ?
* `stval=0x0000000000004008`:
    * 造成 page trap 的 virtual memory (`sh` or `echo`?)

### 刪掉 `growproc()` 之後，會造成什麼樣的影響
* 也就是說 `sys_sbrk()` 沒有執行 `growproc()`
* 也就是沒有執行 `uvmalloc()`
* 也就是沒有執行 `kalloc()`
* 沒有執行 `kalloc()` 就是怎麼樣了(?)
* 最終會導致 user program (sh) 使用了他沒有分配到的記憶體位置(va)
* 我的猜想:
    * 在 sh 執行 `sw	s6,8(a0)` 時，正要 access 某個 va (`8 + a0`) 的當下
        * 硬體發現這個 PTE 的 `valid` flag 為 0 (false)
        * 於是發出了 0x0f 這個 trap (page fault)
* 所以以物理上的狀況來說 page fault 就是
> 當我要 access 某一個 va 時，我發現這個 va 在 page table 上給我的回覆為：
> 此 va 並不是使用中的狀態

## Lazy allocation
當 page fault 發生時，allocate 一個新的 page，並且回到 user space 繼續執行，修改任何的 kernel code，讓 `echo hi` 可以執行

### hints
* page fault 時 `scause` 為 13 or 15
* 從 `stval` 可以得知造成 page fault 的 va 是多少
* 請偷學 `uvmalloc()`，並呼叫 `kalloc()` 以及 `mappages()`
    * 先從偷學這裡開始
    * 當這個 va 沒有被分配時，我就手動幫他分配
    * 偷學 `uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)`
        * `pagetable`: `myproc()->pagetable`
        * `oldsz`: `myproc()->sz`
        * `newsz`: `r_stval()`
* `kernel/trap.c`: `usertrap()`
```clike=
void
usertrap(void)
{
  // ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if(r_scause() == 13 || r_scause() == 15){
    uint64 va = r_stval();
    lazy_alloc(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;
  }
  
  // ...
}
```
* 當 `lazy_alloc()` 還沒有完成實作時，會發生什麼事情?

* `kernel/trap.c`: `lazy_alloc()`
```clike=
int
lazy_alloc(uint64 va)
{
  struct proc *p = myproc();
  pagetable_t pagetable = p->pagetable;
  uint64 new_page_va = PGROUNDDOWN(va);
  char *newmem = kalloc();

  if (newmem == 0)
    return -1;
  memset(newmem, 0, PGSIZE);
  if (mappages(pagetable, new_page_va, PGSIZE, (uint64) newmem,
        PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
    kfree(newmem);
    return -1;
  }
  return 0;
}
```

* `kernel/vm.c`: 
```Clike=
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");
      continue;
    if((*pte & PTE_V) == 0)
      // panic("uvmunmap: not mapped");
      continue;
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}
```
* 之所以要變成 `continue` 是為什麼
    * `procgrow()` 與 lazy alloc 的差別
        * `growproc()` 會一次 alloc 連續的數個 page
        * lazy alloc 只會 allocate **一個** page
            * 所以說那些中間的不連續的沒有被 alloc 的 va 就會產生 `PTE_V` = 0 的問題
            
現在有了最基本的 lazy alloc, 接著來繼續完成

## Lazytests and Usertests
### hints
- [x] Handle negative sbrk() arguments.
- [x] Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
- [x] Handle the parent-to-child memory copy in fork() correctly.
- [ ] Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
- [ ] Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
- [ ] Handle faults on the invalid page below the user stack. 

### Handle negative sbrk() arguments.
對於正數，只需要把 `sz` 增加 n 就好
當參數為負數時，則要實際的釋放空間
釋放空間的方法: 就用原本的 `growproc()` 就好
```Clike=
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p = myproc();

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

### Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().

澄清 lazy alloc 的意涵：
如果用 sbrk 增加記憶體空間，就增加 `sz`
真的到了 page fault 的時候再來處理 allocate 的問題就好

可是有時候遇到 page fault 並不代表這個 va 是允許存在的
以下幾種方情況並不是正常的 va 
1. `va` > `MAXVA`
1. 如果一個 page 的 `PTE_V` == 1 那麼他就一定不是 lazy alloc 因為它已經被分配了
1. `va` >= `p->sz` 因為並沒有藉由 `sbrk()` 去新增位置

解決方法:
```clike=
int
is_lazy_addr(int va)
{
  struct proc *p = myproc();

  if (va > MAXVA)
    return 0;

  pte_t *pte = walk(p->pagetable, va, 0);
  if (pte && (*pte & PTE_V))
    return 0;

  if (PGROUNDDOWN(va) > PGROUNDDOWN(p->sz))
    return 0;

  return 1;
}
```

> Handle the parent-to-child memory copy in fork() correctly.

主要在講 `kernel/proc.c: fork()` 中的呼叫的，`kernel/vm.c: uvmcopy`
原本的 `uvmcopy` 是 copy 一段連續的 memory, 可是現在使用 lazy alloc 了話，就不一定是連續的
解決方法：
`continue` 掉兩個 `panic`
```clike=
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  // ...
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      // panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      // panic("uvmcopy: page not present");
      continue;
    // ...
  }
  return 0;
}
```

### 問題一: `uvmunmap()` `walk()`
```shell=
$ lazytests
lazytests starting
running test lazy alloc
panic: uvmunmap: walk
```
`walk()` 出錯了
這跟前一個問題很像，都是因為 lazy alloc 只有 alloc 一個 page
而不是像原本的 `growproc` 是數個 page 的原因
解決方法：
```Clike=
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
    // ...
    
    if((pte = walk(pagetable, a, 0)) == 0)
      // panic("uvmunmap: walk");
      continue;
    // ...
}
```

> Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.

`copyin()` 與 `copyout()` 的問題
- [ ] trace code

## reference
* [6.S081 2020](https://pdos.csail.mit.edu/6.S081/2020/schedule.html)
* [Lab lazy](https://pdos.csail.mit.edu/6.S081/2020/labs/lazy.html)
* [xv6 book](https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf)
* [video](https://youtu.be/KSYO-gTZo0A)
* [Lazy Page Allocation 实验记录](https://ttzytt.com/2022/07/xv6_lab5_record/)
