S081-2021-lab5中的Copy-on-Write Fork机制是如何实现的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1332个文字，预计阅读时间需要6分钟。
Copy-on-Write + Fork + 主要依据 hins 逐步修改。COW 的思想是在 fork 时刻，子进程与父进程共享物理页面。当需要修改页面内容时，才真正分配自己的页面空间。这也是一种 +lazy allocation +co懒加载+延迟分配。
主要根据hins来一步一步修改。cow的思想是在fork的时候，子进程与父进程共享物理页，当需要修改页面内容的时候才会真正分配自己的页表空间，也就是 lazy allocation
cow使得多个va映射到了同一个pa上，所以 free 的时候我们要特别小心，因为可能别的进程还依赖这个物理页，所以我们需要对每一个 pa 对应的物理页进行引用计数。
如何计数呢？虽然硬件为操作系统保留了三个比特位让其自由发挥，但很明显这点位置是不够应用计数的，只适合用其中一位来表示当前页是否是 cow 页。
但我们知道 xv6 能够使用的最大物理地址，以及页表大小。所以只需要定义一个大小为 PGPYHA / PGSIZE 的一维数组来记录每一页的引用数即可
// riscv.h
#define PTE_COW (1L << 8) // copy on write flag
// kalloc.c
int refcount[PHYSTOP/PGSIZE];
struct spinlock reflock;
kalloc 和 kfree 会导致引用计数的增加和减少
// kalloc.c
void
incref(uint64 pa)
{
int pn = pa/PGSIZE;
acquire(&kmem.lock);
if(pa>=PHYSTOP || refcount[pn]<1){
panic("incref");
}
refcount[pn] += 1;
release(&kmem.lock);
}
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r){
kmem.freelist = r->next;
int pn = (uint64)r / PGSIZE;
acquire(&reflock);
if(refcount[pn]!=0){
panic("kalloc ref");
}
refcount[pn] = 1;
release(&reflock);
}
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
void
kfree(void *pa)
{
...
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// 因为可能有多个进程引用了同一页面，所以这里要加锁
acquire(&kmem.lock);
int pn = (uint64) pa / PGSIZE;
if(refcount[pn]<1){
panic("kfree ref");
}
refcount[pn]-=1;
int tmp = refcount[pn];
release(&kmem.lock);
// 计数不为0说明还有进程需要这一页，不能free
if(tmp>0){
return;
}
// Fill with junk to catch dangling refs.
...
}
同时我们需要在 kinit 中初始化引用计数数组为1。因为 freerange 会调用 kfree，会导致数组变为负数，抛出 painc 。
// kalloc.c
void
kinit()
{
initlock(&kmem.lock, "kmem");
char *p;
p = (char*)PGROUNDUP((uint64)end);
// 将引用计数数组初始化为1
for(; p + PGSIZE <= (char*)PHYSTOP; p += PGSIZE){
refcount[(uint64)p/ PGSIZE] = 1;
}
freerange(end, (void*)PHYSTOP);
}
因为 fork 使用了 uvmcopy 所以我们要修改这个函数，让子进程的地址空间延迟分配，先与父进程共享相同的物理页
// vm.c
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);
// 将父亲和孩子都置为写保护，并标识该页为cow
*pte &= ~PTE_W;
*pte |= PTE_COW;
flags = PTE_FLAGS(*pte);
//引用计数++
incref(pa);
//直接把pa给孩子的页表项，也就是说现在父子的va都对应父亲的pa
if(mappages(new, i, PGSIZE, pa, flags) != 0){
goto err;
}
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
因为我们将PTE_W抹去了，所以当进程需要进行写操作的时候，会发生 page fault。这时候需要在 usertrap 中处理，为子进程分配新的物理地址。
// trap.c
// 为cow page分配新页
int
cowfault(pagetable_t pagetable, uint64 va)
{
if(va >= MAXVA){
return -1;
}
pte_t *pte;
pte = walk(pagetable,va,0);
if(pte == 0 ) return -1;
if ((*pte & PTE_U) == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_COW) == 0){
return -1;
}
uint64 pa1,pa2;
pa1 = PTE2PA(*pte);
pa2 = (uint64)kalloc();
if(pa2 == 0){
return -1;
}
memmove((char*)pa2,(char*)pa1,PGSIZE);
// 只有当引用计数为0的时候才会真正free
kfree((void*)pa1);
uint flags = PTE_FLAGS(*pte);
*pte = PA2PTE(pa2) | flags | PTE_W;
*pte &= ~PTE_COW;
return 0;
}
void
usertrap(void)
{
...
else if((which_dev = devintr()) != 0){
// ok
}else if(r_scause()==15 || r_scause()==13){ // 处理page fault
if(cowfault(p->pagetable,r_stval())<0){
p->killed = 1;
}
} else {
printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
p->killed = 1;
}
...
}
最后需要注意 copyout 将 kernel 的物理地址复制给用户进程，但没有校验 PTE_W 和 PTE_COW，所以有可能直接覆盖了写保护的COW页。 而这一操作不经过 MMU ，没办法引发 page fault ，从而在 usertrap 中处理。所以我们需要修改 copyout 函数，处理的办法跟在 usertrap 中一样，为用户进程分配一个新页，以供写入覆盖。
// vm.c
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
pte_t *pte = walk(pagetable,va0,0);
if(pte == 0 || (*pte & PTE_V )==0 || (*pte & PTE_U) ==0){
return -1;
}
// 如果写保护，并且是因为COW造成的
if((*pte & PTE_W) == 0 && (*pte && PTE_COW) == 1){
// 为当前虚拟地址分配一个新的物理地址以供写入
if(cowfault(pagetable,va0)<0){
return -1;
}
}
pa0 = PTE2PA(*pte);
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;
}
参考
QA/Lab Cow
本文共计1332个文字，预计阅读时间需要6分钟。
Copy-on-Write + Fork + 主要依据 hins 逐步修改。COW 的思想是在 fork 时刻，子进程与父进程共享物理页面。当需要修改页面内容时，才真正分配自己的页面空间。这也是一种 +lazy allocation +co懒加载+延迟分配。
主要根据hins来一步一步修改。cow的思想是在fork的时候，子进程与父进程共享物理页，当需要修改页面内容的时候才会真正分配自己的页表空间，也就是 lazy allocation
cow使得多个va映射到了同一个pa上，所以 free 的时候我们要特别小心，因为可能别的进程还依赖这个物理页，所以我们需要对每一个 pa 对应的物理页进行引用计数。
如何计数呢？虽然硬件为操作系统保留了三个比特位让其自由发挥，但很明显这点位置是不够应用计数的，只适合用其中一位来表示当前页是否是 cow 页。
但我们知道 xv6 能够使用的最大物理地址，以及页表大小。所以只需要定义一个大小为 PGPYHA / PGSIZE 的一维数组来记录每一页的引用数即可
// riscv.h
#define PTE_COW (1L << 8) // copy on write flag
// kalloc.c
int refcount[PHYSTOP/PGSIZE];
struct spinlock reflock;
kalloc 和 kfree 会导致引用计数的增加和减少
// kalloc.c
void
incref(uint64 pa)
{
int pn = pa/PGSIZE;
acquire(&kmem.lock);
if(pa>=PHYSTOP || refcount[pn]<1){
panic("incref");
}
refcount[pn] += 1;
release(&kmem.lock);
}
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r){
kmem.freelist = r->next;
int pn = (uint64)r / PGSIZE;
acquire(&reflock);
if(refcount[pn]!=0){
panic("kalloc ref");
}
refcount[pn] = 1;
release(&reflock);
}
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
void
kfree(void *pa)
{
...
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// 因为可能有多个进程引用了同一页面，所以这里要加锁
acquire(&kmem.lock);
int pn = (uint64) pa / PGSIZE;
if(refcount[pn]<1){
panic("kfree ref");
}
refcount[pn]-=1;
int tmp = refcount[pn];
release(&kmem.lock);
// 计数不为0说明还有进程需要这一页，不能free
if(tmp>0){
return;
}
// Fill with junk to catch dangling refs.
...
}
同时我们需要在 kinit 中初始化引用计数数组为1。因为 freerange 会调用 kfree，会导致数组变为负数，抛出 painc 。
// kalloc.c
void
kinit()
{
initlock(&kmem.lock, "kmem");
char *p;
p = (char*)PGROUNDUP((uint64)end);
// 将引用计数数组初始化为1
for(; p + PGSIZE <= (char*)PHYSTOP; p += PGSIZE){
refcount[(uint64)p/ PGSIZE] = 1;
}
freerange(end, (void*)PHYSTOP);
}
因为 fork 使用了 uvmcopy 所以我们要修改这个函数，让子进程的地址空间延迟分配，先与父进程共享相同的物理页
// vm.c
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);
// 将父亲和孩子都置为写保护，并标识该页为cow
*pte &= ~PTE_W;
*pte |= PTE_COW;
flags = PTE_FLAGS(*pte);
//引用计数++
incref(pa);
//直接把pa给孩子的页表项，也就是说现在父子的va都对应父亲的pa
if(mappages(new, i, PGSIZE, pa, flags) != 0){
goto err;
}
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
因为我们将PTE_W抹去了，所以当进程需要进行写操作的时候，会发生 page fault。这时候需要在 usertrap 中处理，为子进程分配新的物理地址。
// trap.c
// 为cow page分配新页
int
cowfault(pagetable_t pagetable, uint64 va)
{
if(va >= MAXVA){
return -1;
}
pte_t *pte;
pte = walk(pagetable,va,0);
if(pte == 0 ) return -1;
if ((*pte & PTE_U) == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_COW) == 0){
return -1;
}
uint64 pa1,pa2;
pa1 = PTE2PA(*pte);
pa2 = (uint64)kalloc();
if(pa2 == 0){
return -1;
}
memmove((char*)pa2,(char*)pa1,PGSIZE);
// 只有当引用计数为0的时候才会真正free
kfree((void*)pa1);
uint flags = PTE_FLAGS(*pte);
*pte = PA2PTE(pa2) | flags | PTE_W;
*pte &= ~PTE_COW;
return 0;
}
void
usertrap(void)
{
...
else if((which_dev = devintr()) != 0){
// ok
}else if(r_scause()==15 || r_scause()==13){ // 处理page fault
if(cowfault(p->pagetable,r_stval())<0){
p->killed = 1;
}
} else {
printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
p->killed = 1;
}
...
}
最后需要注意 copyout 将 kernel 的物理地址复制给用户进程，但没有校验 PTE_W 和 PTE_COW，所以有可能直接覆盖了写保护的COW页。 而这一操作不经过 MMU ，没办法引发 page fault ，从而在 usertrap 中处理。所以我们需要修改 copyout 函数，处理的办法跟在 usertrap 中一样，为用户进程分配一个新页，以供写入覆盖。
// vm.c
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
pte_t *pte = walk(pagetable,va0,0);
if(pte == 0 || (*pte & PTE_V )==0 || (*pte & PTE_U) ==0){
return -1;
}
// 如果写保护，并且是因为COW造成的
if((*pte & PTE_W) == 0 && (*pte && PTE_COW) == 1){
// 为当前虚拟地址分配一个新的物理地址以供写入
if(cowfault(pagetable,va0)<0){
return -1;
}
}
pa0 = PTE2PA(*pte);
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;
}
参考
QA/Lab Cow