在认清生活的真相之后依然热爱生活

1014 字

5 分钟

xv6-lab5

2025-01-07

C/C++

/

OS

COW(copy-on-write)写时复制，也成为懒复制，在系统领域有广泛的应用，我们在fork时子进程需要复制父进程的地址空间，但是往往子进程不会用到(或是只读)父进程的全部地址空间，如果完全复制下来便会造成许多浪费，我们的任务便是在XV6中实现cow功能

Implement copy-on-write fork (Hard)#

Your task is to implement copy-on-write fork in the xv6 kernel. You are done if your modified kernel executes both the cowtest and ‘usertests -q’ programs successfully.

首先我们来分析该如何实现cow,当子进程想要复制父进程的地址空间时，我们可以选择并不为子进程分配新页，而只是复制子进程的页表，同时清除子进程和父进程对页面的写权限，此时，对页面的读操作可以正常执行(有读权限),在父/子进程想要修改页面时就会触发一个页错误，我们只需要在页错误中加入处理程序，为其重新分配一个页面即可.

大体思路有了，但是还有许多前提条件需要我们先实现. 首先我们需要添加一个PTE_COW标志来指定某一页是处于COW状态

1
#define PTE_COW (1L << 9) // copy on write

其次我们需要考虑，在普通情况下，一个页面只有一个进程所拥有，当两个进程同时拥有一个页面时，我们需要为页面添加引用次数机制(类似于shared_ptr)来放置一个进程释放了页面而另一个进程仍持有该页面的悬空地址

添加引用计数#

为每个页面维护一个引用计数是需要大量空间的，首先我们需要在地址空间中开辟一段区域来维护每个页面的引用次数

1
int * refcount;
2
int pages;
3

4
void
5
kinit()
6
{
7
  initlock(&kmem.lock, "kmem");
8
  // 计算出储存所有引用计数所需要的空间以及页数
9
  int refcount_size = (PHYSTOP - (uint64)end) / (PGSIZE / sizeof(int) + 1);
10
  pages = refcount_size / PGSIZE + 1;
11
  freerange(end, (void*)PHYSTOP);
12
}
13

14
void
15
freerange(void *pa_start, void *pa_end )
16
{
17
  char *p;
18
  p = (char*)PGROUNDUP((uint64)pa_start);
19
  // 为引用计数页分配空间
20
  refcount = (int*)p;
21
  p += (pages) * PGSIZE;
22
  memset(refcount, 0, pages * PGSIZE);
23
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
24
    kfree(p);
25
}

然后我们便可以实现类似于shared_ptr的页面分配机制

1
uint64 get_index(void *pa)
2
{
3
  return (uint64)(pa - (void *)end) / PGSIZE;
4
}
5

6
void
7
kfree(void *pa)
8
{
9
  int index = get_index(pa);
10
  if(refcount[index] > 1){
11
    refcount[index] -= 1;
12
    return;
13
  }
14
  ...
15
}
16

17
void *
18
kalloc(void)
19
{
20
  struct run *r;
21

22
  acquire(&kmem.lock);
23
  r = kmem.freelist;
24
  if(r)
25
    kmem.freelist = r->next;
26
  release(&kmem.lock);
27

28
  if(r){
29
    memset((char*)r, 5, PGSIZE); // fill with junk
30
    int index = get_index((void*)r);
31
    refcount[index] = 1;
32
  }
33

34
  return (void*)r;
35
}
36

37
void
38
add_ref(void *pa)
39
{
40
  int index = get_index(pa);
41
  refcount[index] += 1;
42
}

实现COW#

在搭建好基础设施之后，我们便可以开始着手实现COW了，首先是uvmcopy

1
int
2
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
3
{
4
  pte_t *pte;
5
  uint64 pa, i;
6
  uint flags;
7
  // char *mem;
8

9
  for(i = 0; i < sz; i += PGSIZE){
10
    if((pte = walk(old, i, 0)) == 0)
11
      panic("uvmcopy: pte should exist");
12
    if((*pte & PTE_V) == 0)
13
      panic("uvmcopy: page not present");
14
    pa = PTE2PA(*pte);
15
    add_ref((void*)pa);
16
    flags = PTE_FLAGS(*pte);
17
    // 写时复制
18
    if(flags & PTE_W || flags & PTE_COW){
19
    flags = (flags & ~PTE_W) | PTE_COW;
20
    *pte = (*pte & ~PTE_W) | PTE_COW;
21
    sfence_vma();
22
    }
23
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
24
      goto err;
25
    }
26
  }
27
  return 0;
28

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

然后我们只需要静静等候进程触发页错误

1
// trap.c usertrap
2
...
3
if (r_scause() == 0xf)  // store page fault
4
  {
5
    uint64      va = r_stval();
6
    pagetable_t pt = p->pagetable;
7
    if (va >= MAXVA) {
8
      printf("usertrap(): va=%p\n", (void *)va);
9
      printf("            sepc=%p\n", (void *)r_sepc());
10
      setkilled(p);
11
      goto exit;
12
    }
13
    pte_t *pte = walk(pt, va, 0);
14
    if (!pte) {
15
      printf("usertrap(): pte is null\n");
16
      printf("            va=%p\n", (void *)va);
17
      printf("            sepc=%p\n", (void *)r_sepc());
18
      setkilled(p);
19
      goto exit;
20
    }
21
    if (*pte & PTE_COW && *pte & PTE_U && *pte & PTE_V) {  // copy on write
22
       // change to not cow
23
      *pte &= ~PTE_COW;
24
        // change to writable
25
      *pte |= PTE_W;
26
      uint64 pa = PTE2PA(*pte);
27
      int flags = PTE_FLAGS(*pte);
28
      char *mem = kalloc();
29
      if (mem == 0) {
30
        printf("usertrap(): out of memory\n");
31
        setkilled(p);
32
        return;
33
      }
34
      memmove(mem, (char *)pa, PGSIZE);
35
      *pte = PA2PTE((uint64)mem) | flags;
36
      kfree((void *)pa);
37
      sfence_vma();
38
    } else {
39
      printf("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(),
40
             p->pid);
41
      printf("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
42
      setkilled(p);
43
    }
44
  }
45
  ...
46
exit:
47
  if (killed(p)) exit(-1);
48
  // give up the CPU if this is a timer interrupt.
49
  if (which_dev == 2) yield();
50
  usertrapret();