陈浪平的博客
0%

xv6-2020-lab6解析

发表于 分类于 Disqus：
本文字数： 5.1k 阅读时长 ≈ 5 分钟

这个其实就是Lab5的拓展，在上一个lab中我们实现了sbrk的懒分配，到了这一lab就实现进程的写时复制。

在xv6的原始实现中，父进程是直接把自己的所有的内存复制给了子进程。

写时复制技术，在子进程的页表中创建的条目是指向父进程的物理页中的，并且让子进程页表和父进程页表中的PTE都不能写（也就是不论是父进程还是子进程，都不能写）。不论任何一方想要去写这个物理内存，就会触发一个page fault，然后为触发这个错误的进程分配一个物理页，把原来的那一页的内容复制过来，这次的PTE_W位可以设置成1。

当然写时复制技术也有棘手的地方：如果有多个进程都指向一个相同的物理内存，到时候要怎么回收？

Implement copy-on write（困难）

这里首先介绍一下xv6的测试程序：cowtest，它的第一个测试就是分配了超过物理内存一半的空间，所以如果子进程老老实实复制了，那么必然超过了内存的限制。

这里介绍一下这个测试程序会测试哪些内容：

  • 修改父进程复制物理内存的代码。在父进程和子进程都记得要把PTE_W清掉。
  • 修改中断处理程序。在其中的page fault处理函数中，使用kalloc分配新的物理页面，把旧的页面复制到新的页面中，并且设置新的页面的PTE_W。
  • 需要确保，只有当所有的进程都不引用当前的物理页之后，物理页才会被kfree掉，但是这个引用计数应该保存在哪里呢？
  • 别忘记还需要修改copyout这个函数

一些hints：

  • 上一个lazy分配的实验已经让你很熟悉相关的技术了，但是请不要基于上一个实验，忘了上一个实验吧，这里重新开始。
  • 记录一下PTE是否用于COW是很有用的，可以通过RSW的保留位来解决。
  • usertests还进行了一些别的测试，所以不要忘记使用它进行测试。
  • 在kernel/riscv.h中还有别的一些很有用的宏和定义。
  • 如果COW的页错误在没有空闲的物理页的时候发生了，那么应该干掉进程。

从上面的提示中我们可以得到几个信息，首先是我们必然需要一个数组用来记录每个物理页的引用；其次是我们可以自己定义RSW位，这里直接把图片复制过来：

image-20210421145658854

也就是图中的8和9是可以让我们自己定义的。有了这些知识，就可以开始做啦。

添加物理页的引用

我在kernel/vm.c中新增了一个数组：

1
int physical_ref[(PHYSTOP - KERNBASE) / PGSIZE]; // 每个物理页的引用计数器

新增页表的标志位

在kernel/riscv.h中，新增一个宏：

1
#define PTE_COW (1L << 8)  // cow位，表示这个页是被父子进程共享的

这里其实8和9都是OK的。

修改fork过程

fork的时候调用了uvmcopy()进行物理页的复制，所以进行物理内存的修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  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);
    // 删除掉PTE_W
    *pte = *pte & ~PTE_W;
    // 新增PTE_COW位
    *pte = *pte | PTE_COW;
    flags = PTE_FLAGS(*pte);
    // 目前不分配物理内存
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    physical_ref[(pa - KERNBASE)/PGSIZE]++;
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      // 由于上一步并没有分配物理内存，所以映射关系安装失败的话，不需要释放物理内存
      // kfree(mem);
      goto err;
    }
  }
  return 0;

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

处理physical_ref

我一开始是这么想的，当使用mappages安装对应的关系的时候，也就是此时有虚拟内存映射了物理内存，需要将引用计数加一；而uvmunmap则是解绑对应的关系，所以需要在这里将对应的引用计数进行减一处理。当减完发现是0了，才需要将物理内存清空。代码是这样的：

1
2
3
4
5
6
7
8
9
........
*pte = PA2PTE(pa) | perm | PTE_V;
if (pa >= KERNBASE)
{
  // 引用计数加一
  physical_ref[(pa - KERNBASE) / PGSIZE] += 1;
}
if(a == last)
........
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(do_free){
  uint64 pa = PTE2PA(*pte);
  if (pa >= KERNBASE)
  {
    // 引用计数减一
    physical_ref[(pa - KERNBASE) / PGSIZE] -= 1;
  }

  if (physical_ref[(pa - KERNBASE) / PGSIZE] == 0)
  {
    // 释放物理页
    kfree((void *)pa);
  }
}

后来想想不对劲，因为mappages函数是绑定虚拟地址到物理地址的映射关系，如果不绑定难道物理内存的引用计数就应该是0吗？同时也不应该在uvmunmap中进行引用计数减一。

仔细想想其实应该在kalloc和kfree两个函数中进行引用计数的增加和减少：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
    if ((uint64)r >= KERNBASE)
    {
      // 引用计数加一
      physical_ref[((uint64)r - KERNBASE) / PGSIZE] += 1;
    }
  }
  return (void*)r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void
kfree(void *pa)
{
  struct run *r;

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

  // 首先引用计数减一
  physical_ref[((uint64)pa - KERNBASE) / PGSIZE] -= 1;
  if(physical_ref[((uint64)pa - KERNBASE) / PGSIZE] > 0){
    // 如果此时还有引用的，那就啥也不做
    return;
  }

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

处理缺页中断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
else if(r_scause() == 13 || r_scause() == 15){
  // 进入中断处理程序
  uint64 va = r_stval();
  uint64 pa;
  uint flag;
  pte_t *pte;

  if (va >= MAXVA)
  {
    p->killed = 1;
    panic("va >= MAXVA");
  }

  if (va <= PGROUNDDOWN(p->trapframe->sp) && va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE)
  {
    p->killed = 1;
    panic("it is in guard page!");
  }
  va = PGROUNDDOWN(va);
  if ((pte = walk(p->pagetable, va, 0)) == 0 || (*pte & PTE_COW) == 0)
  {
    // 如果没有对应的pte，或者pte并不是cow，说明这次缺页中断并不是cow引发的，那处理不了
    p->killed = 1;
  }else{
    // 如果能进到这里，说明已经确定是COW引发的中断了
    pa = PTE2PA(*pte);
    flag = PTE_FLAGS(*pte);
    char *mem = kalloc();
    if (mem == 0)
    {
      // 分配物理页失败
      // panic("kalloc!");
      p->killed = 1;
      goto done;
    }
    // 复制到新开辟的页中
    memmove(mem, (char*)pa, PGSIZE);
    // 清除原来的物理页，这里不一定真正的清除
    kfree((void*)pa);
    // 修改对应的pte，把COW拿掉，W加上
    flag = (flag & ~PTE_COW) | PTE_W;
    *pte = PA2PTE((uint64)mem) | flag;
  }
}

还是抄了很多的之前的lazy分配233333。因为有了PTE_COW位判断，所以很容易很判断出是不是因为COW引发的。然后就复制一份，并且设置对应的PTE就可以了。

最后不要忘记我们的引用数组需要清零init设置、以及对freerange的时候的特殊处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void
kinit()
{
  for(int i = 0;i<(PHYSTOP - KERNBASE) / PGSIZE;i++){
    physical_ref[i] = 0;
  }
  initlock(&kmem.lock, "kmem");
  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){
    physical_ref[((uint64)p - KERNBASE)/PGSIZE]++;
    kfree(p);
  }
}

这里的freerange为什么要先1，是因为后面有一个kfree，前面的加一正好让kfree能够正常工作。

总结

这部分完成了COW，总体来说我觉得难度不大，照着思路做其实很容易。

但是上面的代码其实是有问题的，而且这一个lab是位于locking这个章节下面，所以其实它是希望你能够使用锁来对这个引用数组操作，否则可能会出现多个进程同时处理这个引用数组导致问题的发生。