乐趣区

关于操作系统:xv6-源码窥探3CoW-Fork

jiezi

前言

  • 本篇是对于 MIT 6.S081-2020-Lab6(Copy-on-Write Fork for xv6) 的实现；
  • 如果内容上发现有什么问题请不要悭吝您的键盘。

筹备工作

先大略列举一下实现 cow-fork 所要做的工作清单：

  1. 批改 uvmcopy() 函数；【√】
  2. 批改 copyout() 函数，因为它是间接对 pa 进行读写的；【√】

  3. 为 usertrap 函数增加解决 cow page write 的异样；【√】

    • 能够将 2 和 3 两个解决 cow page 的逻辑提取进去。
  4. 在 kalloc.c 中保护一个 references 的援用数组，references[i] 代表第 i 个 page 被援用的次数。先是初始化 references 数组、再是为调配、开释 page 时，增加对 references 数组的操作。【√】

留神：

  1. kalloc() 后 out of memory 时，kill 整个 process；【√】
  2. It may be useful to have a way to record, for each PTE, whether it is a COW mapping.【√】

Implement copy-on write

先在增加保护 references 数组的代码：

/* kernel/kalloc.c */

int references[PA2IDX(PHYSTOP)];
struct spinlock r_lock;

void
kinit()
{initlock(&kmem.lock, "kmem");
  initlock(&r_lock, "refereces");
  memset(references, 0, sizeof(int)*PA2IDX(PHYSTOP));
  freerange(end, (void*)PHYSTOP);
}

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  if (reference_remove((uint64)pa) > 0)
    return;

  references[PA2IDX(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);
}

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

  acquire(&kmem.lock);
  r = kmem.freelist;

  if(r) {references[PA2IDX(r)] = 1;
    kmem.freelist = r->next;
  }
  release(&kmem.lock);

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

int 
reference_find(uint64 pa)
{return references[PA2IDX(pa)];
}

int
reference_add(uint64 pa)
{
  int ref;
  acquire(&r_lock);
  ref = ++references[PA2IDX(pa)];
  release(&r_lock); 
  return ref;
}

int
reference_remove(uint64 pa)
{
  int ref;
  acquire(&r_lock);
  ref = --references[PA2IDX(pa)];
  release(&r_lock);
  return ref;
}

再是增加解决 cow 异常中断的函数，这个函数将会在 copyout() 函数和 usertrap() 函数中被独特调用：

/* kernel/trap.c */

int
cow_handle(pagetable_t pagetable, uint64 va)
{va = PGROUNDDOWN(va);

  if(va >= MAXVA)
    return -1;

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

  if ((*pte & PTE_COW) == 0)
    return 1;

  char *n_pa;
  if ((n_pa = kalloc()) != 0) {uint64 pa = PTE2PA(*pte);
    memmove(n_pa, (char*)pa, PGSIZE);
    *pte = PA2PTE(n_pa) | ((PTE_FLAGS(*pte) & ~PTE_COW) | PTE_W);
    kfree((void*)pa);

    return 0;
  } else {return -1;}
}
/* kernel/trap.c */

void
usertrap(void)
{
  ...
    syscall();} else if (r_scause() == 13 || r_scause() == 15) {uint64 va = r_stval();
    if (va >= p->sz || cow_handle(p->pagetable, va) != 0)
      p->killed = 1;

  } else if((which_dev = devintr()) != 0){...}
/* kernel/vm.c */

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  ...
    va0 = PGROUNDDOWN(dstva);
    if (cow_handle(pagetable, va0) < 0)
      return -1;

    pa0 = walkaddr(pagetable, va0);
  ...
}

最初就是在 fork() 函数调用 uvmcopy() 的代码：

/* kernel/vm.c */

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 va, pa;

  for (va = 0; va < sz; va += PGSIZE) {if ((pte = walk(old, va, 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 | PTE_COW) & ~PTE_W;

    if(mappages(new, va, PGSIZE, pa, (uint)PTE_FLAGS(*pte)) < 0)
      goto err;

    reference_add(pa);
  }
  return 0;

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

后记

以下是记录了我从开始了解试验内容后，到通过 usertests 的残缺踩坑历程：

  for (int i = 0; i < 512; i++)
    new[i] = old[i];

如果用下面这样的模式拷贝 user memory，无论是调配还是开释过程内存时，不仅要思考 page 的援用，还要思考 pagetable 的援用。尽管可能节约许多 pagetable 所占用的空间，然而太简单了，想了半天放弃了。

所以，为了简略起见，这里就抉择 mappages 函数来实现。因为如果零碎内连调配过程页表的内存空间都没有了，那么离内存齐全耗尽也就不远了，早 si 晚 si 都得 si（bushi

要想过 cowtest，只需把大体的逻辑给正确地写进去就能过了。

问题是要想过 usertests，就须要一些数据合法性的解决，尤其是在解决 cow 中断异样那块儿，但根本仿照 walkaddr() 函数的解决逻辑就能过关。

顺带一提，测试 usertests 时，test sbrkbugs 就是会产生 panic，不要认为是测试挂了……

在 usertests 的最初，输入了 FAILED -- lost some free pages 31928 (out of 31937)。这时要想找进去这一两个 pages 没有被回收的起因是比拟艰难的。

debug 的过程是颇为苦楚，我一度认为是因为我调配和开释 page 时的逻辑不对。但察看到两个 usertests 输入的 lost free pages 的数量有时是一个，有时是两个。这让我想到了可能是我没有对援用数组的增删操作加锁无关，于是随即加上了自旋锁测了下 usertests，发现还是挂了一个 sbrkfail，并且只有这一个测试点挂掉了，把 sbrkfail 正文掉了之后发现能残缺地通过 usertests，没有呈现 lost free pages 的问题（并且此时不加锁就会又呈现 lost free pages 的问题），证实至多加锁的这个思路是对的。

之前没加锁的时候，sbrkfail 还是能通过的，加锁后又不能了，但锁还是要加的，因而就看上锁和开释锁的机会对不对了。举个例子，从 ++references[i] 到 return references[i] 这两条语句之间，用可能有别的父子过程去在对 references[i] 进行操作，因而我把扭转后的援用数用一个 ref 变量保留了下来。这次终于通过了所有的 usertests。最初贴一个通过 make grade 的截图（尽管不晓得为什么 usertest 超时了也给全分）：

总的来说，因为本人还没学到锁，提醒也没给，所以没往那儿多想，踩了个大坑。

优化的空间很显著还是有的：

  1. 速度上，能够把 cow_handle() 中，测验 va 的合法性的代码搬到函数调用处去，因为否则在 copyout 中，同一个的 va 将会在 copyout() 和 cow_handle() 中 walk 页表两次，没有必要。
  2. 空间上，就不要在全局开一个 PA2IDX(PHYSTOP) 这么大的 references 数组了，开一个长度是 PA2IDX(PHYSTOP-KERNBASE) 的足矣，因为一个过程理论物理地址空间大小不会超过 PHYSTOP-KERNBASE。

太菜了，在回家放假前再做一篇多线程的试验的可能性微存（？

退出移动版