6.S081 lab6 cow

Copy-on-Write Fork for xv6

这次 lab 只有一关,那就是为xv6实现copy on write

xv6中的fork()系统调用将父进程的用户内存全部复制到子进程中。如果父进程内存占用很大,复制可能需要很长的时间。更糟糕的是,通常来说,这个复制在很大程度上是浪费的;例如,在子进程中,fork()之后的exec()调用会导致子进程丢弃复制的内存,可能大部分内存都没有来得及使用。另一方面,如果父子双方都使用一个page,并且其中一方或双方需要写这个page,那么确实需要复制。

根据官网给的提示:

  • 使用引用计数,对每个物理页面维护一个reference count,记录物理页面被 map 的次数。

    kernel/kalloc.c

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    struct {
    struct spinlock lock;
    struct run *freelist;
    int rc[PHYSTOP / PGSIZE];
    } kmem;

    void
    freerange(void *pa_start, void *pa_end)
    {
    char *p;
    p = (char*)PGROUNDUP((uint64)pa_start);
    for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    kmem.rc[(uint64)p / PGSIZE] = 1;
    kfree(p);
    }
    }

    void
    increase_rc(uint64 pa) {
    acquire(&kmem.lock);
    kmem.rc[pa / PGSIZE]++;
    release(&kmem.lock);
    }
  • 利用 RISC-V PTE 中的RSW (reserved for software)位来标记cow页,修改uvmcopy(),在复制内存时,仅将父进程的物理页面 map 到子进程页表中,并清除双方PTE中的PTE_W标志。

    kernel/riscv.h中加入:

    1
    #define PTE_COW (1L << 8)

    kernel/vm.c中加入:

    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
    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);
    flags = PTE_FLAGS(*pte);
    // only for writable page
    if (flags & PTE_W) {
    flags = (flags | PTE_COW) & (~PTE_W);
    *pte = PA2PTE(pa) | flags;
    }
    increase_rc(pa);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
    goto err;
    }
    }
    return 0;

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

    注意mappages失败时,删掉原有的kfree(mem),因为我们没有申请新的内存。

  • 发生page falut时,在usertrap()中捕获,对cow page分配真正的物理内存。

    kernel/kalloc.c

    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
    int
    cow_alloc(pagetable_t pagetable, uint64 va) {
    uint64 pa;
    uint64 mem;
    pte_t *pte;
    if (va >= MAXVA)
    return -1;
    va = PGROUNDDOWN(va);
    pte = walk(pagetable, va, 0);
    if (pte == 0) {
    return -1;
    }
    // not a valid cow page
    if (!(*pte & PTE_V)) {
    return -2;
    }
    pa = PTE2PA(*pte);

    // only one rf, make it writable
    acquire(&kmem.lock);
    if (kmem.rc[pa / PGSIZE] == 1) {
    *pte &= ~PTE_COW;
    *pte |= PTE_W;
    release(&kmem.lock);
    return 0;
    }
    release(&kmem.lock);
    if ((mem = (uint64)kalloc()) == 0){
    return -3;
    }
    memmove((void *)mem, (void *)pa, PGSIZE);
    *pte = ((PA2PTE(mem) | PTE_FLAGS(*pte) | PTE_W) & (~PTE_COW));
    // decrease rc
    kfree((void *)pa);
    return 0;
    }

    在我的实现中,当cow page发生page fault,且reference count为 1 时,不再重新分配页面进行复制,而是直接将该页面消去PTE_COW并加上PTE_W,减少内存分配和复制操作。

    kernel/trap.c

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    else if(r_scause() == 13 || r_scause() == 15) {
    va = r_stval();
    if (va < PGROUNDDOWN(p->trapframe->sp) &&
    va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE) {
    // guard page
    p->killed = 1;
    } else {
    int ret;
    if((ret = cow_alloc(p->pagetable, va)) < 0 ) {
    p->killed = 1;
    }
    }
    }

    当使用kalloc()进行内存分配时,需要将对应pagereference count设置为 1,使用kfree()释放内存时,只能将reference count为 0 的页面放回空闲列表。

    kernel/kalloc.c

    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
    void *
    kalloc(void)
    {
    struct run *r;

    acquire(&kmem.lock);
    r = kmem.freelist;
    if(r) {
    kmem.freelist = r->next;
    kmem.rc[(uint64)r / PGSIZE] = 1;
    }
    release(&kmem.lock);

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

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

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

    acquire(&kmem.lock);
    kmem.rc[(uint64)pa / PGSIZE]--;
    if(kmem.rc[(uint64)pa / PGSIZE] <= 0) {
    memset(pa, 1, PGSIZE);
    r = (struct run*)pa;
    r->next = kmem.freelist;
    kmem.freelist = r;
    }
    release(&kmem.lock);
    }

    _注意_:kfree()中,对于kmem.rc[(uint64)pa / PGSIZE]的修改和读取必须是一个原子操作,否则内存可能被重复释放,例如对于某个物理page,同时 map 到 A、B 的页表中,之后:

    • A : ref - 1
    • B : ref - 1
    • A : ref == 0 => free
    • B : ref == 0 => free
  • 最后,我们需要修改copyout(),同lazy allocation一样,当因为系统调用切换到内核页表时,硬件无法再为写cow page产生page fault,所以我们需要手动处理:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int
    copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
    {
    uint64 n, va0, pa0;

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

    至此便完成了 lab6 copy on write。

    最终代码见GitHub 仓库

作者

Naruto210

发布于

2021-02-27

更新于

2021-04-07

许可协议

评论