Lab5 Copy on Write | AthenaCrafter

MIT6.S081

发布日期: 2024-09-21

题目

xv6 fork 系统调用会将父进程的所有内存数据复制给子进程。若父进程内存占用大，复制耗时久，且若子进程后续执行exec，复制的内存大概率被丢弃，造成资源浪费。

本实验要求实现写时复制（Copy-on-Write, COW）功能，优化 fork 系统调用：初始时，子进程与父进程共享物理内存页，仅当任一进程尝试写入共享页面时，才真正为该进程分配新的物理页并复制内容，从而减少不必要的内存拷贝，提升性能。

思路

物理页引用计数

使用写时复制机制时，多个页表项可能映射到同一物理页。因此，kfree 不能立即释放物理页，而应通过引用计数记录当前被引用的次数。仅当引用计数降为零时，才真正释放该物理页。

引用计数结构体

#define FREE_MAX_CNT PHYSTOP/PGSIZE
struct ref_cnt {
  struct spinlock lock[FREE_MAX_CNT];
  int cnt[FREE_MAX_CNT];
};

初始化

void kinit() {
  for(i = 0; i < FREE_MAX_CNT; i++) {
    initlock(&kmem.counter.lock[i], "");
    kmem.counter.cnt[i] = 1;
  }	
}

分配

void *kalloc(void) {
  if(r) {
    ref_cnt_idx = (uint64)((void*)r) / PGSIZE;
    kmem.counter.cnt[ref_cnt_idx] = 1;
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
}

释放

void kfree(void *pa) {
  ref_cnt_idx = (uint64)pa / PGSIZE;

  acquire(&kmem.counter.lock[ref_cnt_idx]);
  kmem.counter.cnt[ref_cnt_idx]--;
  if(kmem.counter.cnt[ref_cnt_idx] > 0) {
    release(&kmem.counter.lock[ref_cnt_idx]);
    return;
  }
  release(&kmem.counter.lock[ref_cnt_idx]);
}

Copy-on-Write 初始化

系统调用 fork 创建子进程时，并不会立即为子进程申请新页并复制父进程的每一页，而是让子进程的页表直接映射到父进程原有的物理页上

同时，在父子进程的页表中，清除所有数据页的写入权限并添加 COW 标志，以此将它们设置为 COW 页

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");

    // clean parent's pte flag PTE_W & add parent's pte flag PTE_COW
    *pte = (*pte | PTE_COW) & ~PTE_W;

    // child process map to parent process's physical address pa
    // grant child's pte flag permission the same as parent
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
    krefcnt_add((void*)pa);
  }
  return 0;

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

Copy-on-Write 处理

当父进程或子进程任意一方尝试写入 COW 共享页时，会触发 page fault ，并进入 usertrap 或 kerneltrap

此时进程既可能处于用户态，也可能处于内核态：

应用程序向 COW 页写会触发 page fault ，进入usertrap

if(r_scause() == 15) {
    if(cowhandler(r_stval()) != 0)
      p->killed = 1;
}

应用程序在内核态使用copyout()向写用户内存空间的COW页写入，也会触发 page fault ，进而进入kerneltrap

int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) {
  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    // ensure the user address va0 is handled for copy-on-write.
    cowhandler(va0);
    // ...
  }
  return 0;
}

将 COW 造成的 page fault 处理流程封装为 cowhandler() 函数，包括以下步骤：

获取缺页地址：通过 r_stval() 获取触发缺页的虚拟地址
查找并验证页表项：使用 walk() 获取该地址的页表项
验证合理性：检查发生缺页的进程的页表项是否有效且具有 COW 标志，排除对代码区等真正只读页的误写
申请新页，复制原页内容
释放原页引用：调用 kfree() 释放原物理页的引用（递减计数，计数归零则真正释放）
更新发生缺页的进程的页表项的映射位置，指向新页
更新两个进程的页表项的权限：赋予写权限，清除 COW 标志

// copy-on-write fault handler
int cowhandler(uint64 va) {
  struct proc *p;
  uint64 pa;
  uint flags;
  pte_t *pte;
  char *mem;

  p = myproc();

  if(va >= MAXVA) {
    printf("cow: faulting virtual address exceeds MAXVA\n");
    return -1;
  }
  va = PGROUNDDOWN(va);

  // find the page table entry (pte) of the faulting virtual address (va)
  if((pte = walk(p->pagetable, va, 0)) == 0) {
    printf("cow: the page table entry (pte) of va does not exist\n");
    return -1;
  }

  // verify if the page is marked as Copy-On-Write (COW)
  if((*pte & PTE_COW) == 0) {
    return 1;
  }

  // copy contents from original page to new page, then free the original page
  if((mem = kalloc()) == 0) {
    printf("cow: failed to allocate new physical page\n");
    return -1;
  }
  pa = PTE2PA(*pte);
  memmove(mem, (char*)pa, PGSIZE);
  kfree((void*)pa);

  // clear COW flag, grant write permission
  flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;

  // remap virtual address to new physical page with updated flags
  uvmunmap(p->pagetable, va, 1, 0);
  if(mappages(p->pagetable, va, PGSIZE, (uint64)mem, flags) != 0){
    uvmunmap(p->pagetable, va, 1, 0);
    printf("cow: failed to remap virtual address\n");
    return -1;
  }
  return 0;
}