Try   HackMD

lazy tracecode

sys_sbrk()

用來改變一個 proc 的大小

  • 什麼時候會需要改變 proc 的大小?
    平常寫程式的時候好像不太會使用這個功能(?)













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;
}
  • lazy allocation version:














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

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  myproc()->sz += n;
  // if(growproc(n) < 0)
  //   return -1;
  return addr;
}
  • 回傳 addr (先前的大小) 是為什麼？
  • lazy version 就只是把 sz += n

myproc()->sz 的旅程

  1. fork(): init proc
  2. freeproc(): delete proc
  3. sys_sbrk(): 真的在改變 process 大小的地方
    • growproc()
      • uvmalloc()
      • uvmdealloc()

growproc()

參數 n 可以是正數或是負數




















// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}

uvmalloc()

把一個 page table 的大小從 oldsz 變成 newsz

  • 為什麼不必 page aligned ?
    • 因為這裡 size 的 大小單位為 byte
  • newsz 要比 oldsz 大
    • 不然使用 oldsz 就好了
    • 如果 newsz 比 oldsz 小，那麼什麼事情都不會做
































// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz) // 如果 newsz 比 oldsz 小，那麼什麼事情都不會做 
    return oldsz;

  oldsz = PGROUNDUP(oldsz); // round up 是因為 oldsz 的那一個 page 應該都已經 allocate 了
                            // 看看 newsz 的那一個 page 也是一整個 page 都 allocate
                            // 其實我們也只能這麼做，因為一次 kalloc() 就是一個 page
                            // 一個 PTE 就是指到一個 pagetable 
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE); // zero the page

    // a 經由這個 pagetable mapping 到 kalloc() 出來的 mem
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}
  • uvmalloc() 的功用也就是把一個 page table 的大小從 oldsz 變成 newsz
  • 什麼?! 所以說 page table 一定要從 va 0 一直增加?
    • 所謂的 "增加" 是指這些 pte 都有指向一個被 kalloc() 出來的 memory
    • according to uvmalloc() this might be true
  • 而這裡所謂的 page table 應該都是 user program 的 page table (?)

uvmdealloc()

  • uvmdealloc() 也是把 page table 的 size 從 oldsz 變成 newsz
  • 差別在於 newsz 應該會比 oldsz 小
    • 不然就不會做任何事

















// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
uint64
uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
  }

  return newsz;
}
  • 請注意這裡的 dealloc 都必須要以一個 page 為單位去做 kalloc() 或是 unmap
  • alloc vs unmap
    • alloc: 在 freelist 中標記為使用中
    • unmap: 把 va 從 page table 拿掉
      • 不一定會 kfree() , 要看參數 do_free

uvmunmap()

  • uvmunmap() 是用來把 va 從 pagetable 中 ummap 的 function
  • unmap 時不一定會 free 掉這個 page, 要看 do_free 決定

























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){
    // alloc = 0, 如果找不到 pte，不需要新增
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    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;
  }
}
  • 在原本的版本中 PTE_V = 0 時會觸發 panic()
    • 因為必須要是正在使用的 page, 才會有 ummap 的問題
  • lazy alloc 版本中的 PTE_V = 0 時，卻不會有 panic 是因為
    • uvmunmap() 在哪裡被使用到?

之所以要 continue 的原因

  1. 思考從 growproc() 變成 lazy alloc 有什麼變化
    • 每次 lazy alloc 都只有 alloc 一個 page
    • 這就是為什麼 uvmunmap() 會卡到 PTE_V 的原因

copyin()

  • 從 user copy 到 kernel

  • 使用場景:

    • kernel/pipe.c
    • kernel/proc.c
    • kernel/syscall.c

  • arguments:

    • pagetable: user program 的 page table
    • dst: kernel virtual address
    • srcva: va in pagetable
    • len
























// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (srcva - va0);
    if(n > len)
      n = len;
    memmove(dst, (void *)(pa0 + (srcva - va0)), n);

    len -= n;
    dst += n;
    srcva = va0 + PGSIZE;
  }
  return 0;
}

在每一次的 while loop 中，把 va
我想 lazy alloc 的問題會在於 walkaddr()
因為會出現找不到 pa 的問題
可是有時候找不到 pa 並不是真的找不到 pa, 而是因為那個 va 是用 lazy alloc 的

copyout()

copyout() 是用來把，memory 的內容從 kernel 搬到 user

























// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    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;
}

同樣的在 lazy lab 也會遇到問題
同樣是在 walkaddr() 時會有找不到 va0 對應的 pa 的問題
因為這個 va0 是用 lazy alloc 的

walkaddr()

丟入 va 回傳 pa























// Look up a virtual address, return the physical address,
// or 0 if not mapped.
// Can only be used to look up user pages.
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;
}

walk() 與 addrwalk() 的差別在於

  • walk() return pte
  • addrwalk() return pa
    • 並且還會

在 lazy lab 中會遇到錯誤的狀況

  • copyout: 有可能
  • copyin: 正常情況下應該不太可能除非

memmove()

Last changed by 
 
xv6
0
60

Read more

Lab8 networking 紀錄

ip of xv6: 10.0.2.15ip of host: 10.0.2.2

Jul 12, 2023
Lab7 Multithreading 紀錄

Uthread: switching between threads user/uthread.c: 定義 context: struct context { uint64 ra; uint64 sp; // callee-saved uint64 s0;

Jun 20, 2023
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 的內容複製一份 大致上的流程: fork() 使用 uvmcopy() 把 page table 複製過去在這個 lab 中，我們希望 fork() 後 child 跟 parent 的 page table 都是 map 到相同的 pa 現在的 uvmcopy() 就是把 old 的東西複製到 new

Jun 20, 2023
Lab5 Lazy 紀錄

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

Jun 20, 2023
Read more from xv6
Published on HackMD