操作系统-xv6-lab6-cow

本实验之前 fork之后 child process 立刻拷贝 parent的physical mem 并建立映射.
本实验之后：不必拷贝. copy on write.
- 思想：推迟为child分配和复制物理内存页，直到实际需要副本。
- 实现
  - 1. fork , 进行假分配
  - 1. copy on write , 进行真分配
    - 根据physical page的ref cnt(是否为1)来判断是否需要cow
    - cow分为三部分
      - 复制物理内存
      - 取消pte的cow标志位
      - proc的pgtbl上建立映射
  - 1. cow之后返回到造成pgfault的指令继续执行.
哪个process copy on write ?
- 哪个process先写，就哪个porcess的pgtbl进行copy on write.
当parent process A fork 出 BCDE process 后
- 1. A写. 触发pgfault
  - 则A进行cow. 且A只会影响自己的pgtbl. 不会改变BCDE的pgtbl
- 1. BCD写. 触发pgfault
  - 则BCD进行cow. 同1
- 1. E写.
  - 尽管此时只有E一个proc引用该mem，但仍然会pagefault. 因为E的pgtbl上的pte并没有任何改变. 仍然有cow的标志位
  - 故E也进入pgfault handler.(walkaddrforwrite)
  - E发现physical page的ref cnt = 1 , 故不再需要复制物理内存,重新建立映射. 直接去掉cow标志位即可返回.

背景

xv6 中的 fork() 系统调用将父进程的所有用户空间内存复制到子进程中。
如果父级很大，复制可能需要很长时间。更糟糕的是，工作往往大部分都被浪费了
- 例如，子进程中的 fork() 后跟 exec() 将导致子进程丢弃复制的内存，可能从未使用过大部分内存。
- 当Shell处理指令时，它会通过fork创建一个子进程。fork会创建一个Shell进程的拷贝，所以这时我们有一个父进程（原来的Shell）和一个子进程。Shell的子进程执行的第一件事情就是调用exec运行一些其他程序，比如运行echo。现在的情况是，fork创建了Shell地址空间的一个完整的拷贝，而exec做的第一件事情就是丢弃这个地址空间，取而代之的是一个包含了echo的地址空间。这里看起来有点浪费。
另一方面，如果我们让parent和child映射同一个page的话，那么当父母和孩子有一个需要对其进行写，那么就需要一个拷贝副本。
由此，就有了copy on write : 写时复制
- copy on write 的目的时推迟为child process 的 page table分配要映射到的物理页，一直使用parent的物理页。直到这个物理页被写的时候，才会拷贝一个page的副本给child process 的 pgtbl去映射。
- 也即，推迟为child分配和复制物理内存页，直到实际需要副本（如果有的话）。
hint

Solution

下面称cow pte / va为
- 该 pte / va 还没有分配属于自己的映射到的physical page，和另一个pgtbl的pte共同映射一个物理页。
- *pte &= ~PTE_W
  - 不可写，当发生写动作时触发pgfault
- *pte |= PTE_RSW_1
  - 在pgfault handler中，通过该位判断是否是cow 的pte，是则如下处理
  - 当发生对该pte对应的va的写动作时，会为该pte kalloc一个physical page 去映射。
再简洁一点，约定
- 假分配：使得一个pte/va成为cow pte /va。
- 真分配：为一个cow pte/va 分配其属于自己映射到的physical page，并更新pte。使其从一个cow pte/va变成一个普通的pte/va。
我所做的工作如下

1. fork , 进行假分配

令fork时不会立刻分配内存，并对pte进行假分配
手段：先修改fork中的相关函数：uvmcopy，并添加leafptecow。

修改uvmcopy：使得fork时不会立即分配物理内存给child。
- uvmcopy在fork中被调用，用于拷贝old user pagetable 给 new user pagetable
- 原先是新kalloc一块physical page然后映射到new user pagetable的va，现在变为直接将old user pagetable映射到的physical page(pp) 给 new user pagetable去映射。
  - mappages(new_pgtbl, i, PGSIZE, old_pa, flags)
- 并且在new user pgtbl映射到 pp 时，将pp的引用计数+1。
  - incref(pa);
添加leafptecow：使得pte为cow的pte。（其实可以将这步优化到上一步uvmcopy中去做，不过懒得做了，就这样吧）
- 下述的pte为child的user pgtbl和parent的user pgtbl的有效叶子pte。（text、data、stack、heap段的，不包括trampoline和trapframe段的）
- 使得pte均为可读不可写，以便在user对该pte指向的内存进行写时触发异常。
  - *pte &= ~(PTE_W)
- 标记pte为copy on write的pte，这样才能和其他原本就是只读的pte区分开。
  - 取pte中的RSW中的一位作为cow的标志位。
  - *pte |= PTE_RSW_1。

2. copy on write , 进行真分配

当发生写造成的pagefault时，进行copy on write。也即实现对写造成的pgfault的handler。也即对pte进行真分配。
这里就可分为两种情况下的pagefault。与lazy allocation类似。
分为在user和在kernel。

一种是在user态对cow的va进行写，

此时对于user pgtbl的使用是由mmu来负责的。mmu检测到pte为只读，故触发pagefault，进入usertrap。

因此，需要在usertrap对这种pagefault进行处理。

//  检验页面写错误
} else if(r_scause() == 15){    
//  发生页面错误的va
uint64 va = r_stval();
//  处理pagefault : 分配新physical mem，建立新映射，不再和另一process pgtbl 映射在同一physical mem
int ret = walkaddrforwrite(p->pagetable,va);
//  没有内存了. 杀掉process.不杀掉的话会陷入死循环. 回到user,发现还是不可写.然后硬件触发.然后继续到这里.还是没内存.循环往复.
if(ret == 0)
  p->killed = 1;

另一种是在kernel态，想对user cow的va进行写。

此时对于user pgtbl的使用是由软件模拟的（即walkaddr），故不会触发page fault。是一种不会触发page fault的page faulthhhh，这个page fault需要我们自己来检验，并处理。

因此，在copyout中，对user的cow的va进行检测并处理。核心代码如下，也是通过walkaddrforwrite进行检测并处理。

// Copy from kernel to user.
int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
while(condition){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddrforwrite(pagetable,va0);
    if(pa0 == 0)
    return -1;
    memmove((void *)(pa0 + (dstva - va0)), src, n);
}
return 0;
}

核心函数：walkaddrforwrite

uint64 walkaddrforwrite(pagetable_t pgtbl,uint64 va)
功能：传入va及对应的pgtbl，并返回一个va映射到的可写的pa地址。且如果之前对va进行了假分配。那么这里会对va进行真分配。
逻辑：
- 如果pte是个cow的pte，
  - 如果其指向的physical page的引用计数为1，那么直接改变该pte的控制位，并返回指向的物理内存。（因为此时只有一个user pgtbl占据这个physical page，直接变成PTE_W可写并取消RSW位即可。）
  - 如果其指向的physical page的引用计数不为1，那么为va分配新的physical page，取消原先pte的映射（会改变old physical page的引用计数），并建立pte到新pa的映射。
- 如果pte不是个cow的pte
  - 那么直接返回其映射到的pa即可。

所以可以看到，写的这个walkaddrforwrite，也可以作为page fault handler。

uint64 walkaddrforwrite(pagetable_t pgtbl,uint64 va)
{
    if(va >= MAXVA) return 0;
    pte_t *pte = walk(pgtbl,va,0);
    //  检测pte是否有效 --- 即va是否有效
    if(pte == 0 || *pte == 0) return 0;
    //  需要copy on write
    if(((*pte) & PTE_W) == 0)
    {
        if(((*pte) & PTE_RSW_1) == 0)
            panic("pte is supposed to be cow when pte_w == 0");
        else
        {
            if(getref(PTE2PA(*pte))<=1)
            {
                *pte |= PTE_W;
                *pte &= ~PTE_RSW_1; 
                return PTE2PA(*pte);
            }

            uint64 old_pa = PTE2PA(*pte);
            uint64 mem = (uint64) kalloc();
            //  没有空余内存了
            if(mem == 0)  return 0;         
            memmove((void*)mem,(const void*)old_pa,PGSIZE);
            uvmunmap(pgtbl,PGROUNDDOWN(va),1,1);   //  munmap 1 : --ref_cnt
            //  建立va到新pa的新映射
            mappages(pgtbl,PGROUNDDOWN(va),PGSIZE,mem,PTE_W|PTE_R|PTE_X|PTE_U);
            return mem;
        }
    }
    
    //  不需要copy on write
    return PTE2PA(*pte);
}

3. physical page的引用计数

重点：对physical page的引用计数

对DRAM段每一个physical page进行引用计数。
- 范围为[kernel text/data即first address after kernel,PHSTOP)。
- 因为user process的pgtbl只会映射到这里的physical page。
注意freelist上的引用计数必须都是0；kfree时检查引用计数，当为0时才能将该pp放回freelist。

什么结构来引用计数：数组

对每一个pp的引用计数，需要用一个lock来保护。防止不同process对同一pp的ref_cnt进行操作，导致data race。

#define IDX(pa) ((pa - KERNBASE) / PGSIZE)
#define MAXN ((PHYSTOP - KERNBASE) / PGSIZE + 5)
//  仅限DRAM进行引用计数 即 pa位于 KERNBASE PHYSTOP之间
struct ref{
    struct spinlock lock;
    int ref_cnt;
} refs[MAXN];

何时改变引用计数：

++ref_cnt

kalloc时，需要++ref_cnt。也即，将physical page 从freelist上摘下来时，需要令ref_cnt = 1。

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
        incref((uint64)r);
    }
    return (void*)r;
}

uvmcopy时，当对pte进行一个假分配后，也即令一个pte成为cow pte后，需要对其映射到的pa进行一个++ref_cnt。
1
2
3
(mappages(new, i, PGSIZE, pa, flags);
// 对于两个user pgtbl都使用的mem，则引用计数++
incref(pa);

–ref_cnt

当kfree时，需要–ref_cnt，当ref_cnt为0时再释放pp.

void
kfree(void *pa)
{
    struct run *r;
    //  check whether the pa is legal
    if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
        panic("kfree");

    acquire(&kmem.lock);

    int idx = ((uint64)pa - KERNBASE) / PGSIZE;
    if(idx <= 0 ) panic("idx is expected to be > 0 ");

    acquire(&(refs[idx].lock));

    if(--refs[idx].ref_cnt < 0) panic(">= 0");

    if((refs[idx].ref_cnt) == 0)  
    {
        // Fill with junk to catch dangling refs.
        memset(pa, 1, PGSIZE);
        r = (struct run*)pa;
        r->next = kmem.freelist;
        kmem.freelist = r;
    }
    release(&(refs[idx].lock));
    
    release(&kmem.lock);
}

bug
- 1. 一开始想在run结构体增加成员 ref_cnt 代表该page正在引用的次数。
  - 想想就不行。不能在run里增加成员。因为那个也是physical page的头部。当把pg分配出去，那个结构体就被覆盖了。何谈引用计数
  - 所以单独建一个数组，来表示每个pg的引用次数。
- 1. 一开始想在mappages和munmap的时候，增加/减少引用计数。而并不是在kalloc和kfree时。结果一输入命令就panic init exiting.
  - 不能这样。因为一开始kernel pgtbl就会建立所有映射，可也没有kalloc。如果按如上方案的话，在kfree的时候，ref_cnt的引用计数应当为1，(并且我们还只对dram进行计数，还需要判断)。
  - 如果只是这样倒也罢了。可是还有一些其他地方只kalloc了，却并没有建立映射。并且从逻辑上来讲这个引用计数就应当只涉及调用了fork的user pgtbl，这样做会引入kernel pgtbl，徒增复杂性。且如hint所说，kfree() should only place a page back on the free list if its reference count is zero。调试的时候就这里耗时醉酒，赶紧放弃这种计数方法。
  - 改成在kfree和kalloc和uvmcopy时维护计数。

1. exec不需要修改

1. 开机成功
- 大部分时间都耗在了开机能正常运行命令之前，开机成功之后直接过了cowtest，然后usertests也几分钟就改完了。爽!
  - usertests过不去的test看一眼是咋写的，然后改一下就行。能正常运行命令就应该是逻辑没错误了，test出来的是极限/故意写错的情况。

bug

1. 修改fork时遇到的bug
- 我之前将pgtbl的所有pte都改变成cow的page了。结果陷入了死循环，连$都没打印出来。在这里卡了好久。
  - 调试之后发现是在从usertrapret出去之后到trampoline的userret，然后sret之后就陷入了死循环，不断进入kerneltrap再出去。
  - 原因：我认为是这样的，因为将userpgtbl映射到trapframe的pte设置为不可写，而后会有动作对trapframe进行了写，且当时(usertrapret中有intr_off)关中断。当sret打开中断后，cpu接受中断，进入kerneltrap，没处理，再离开，再进入。如此死循环。
- 所以注意child拷贝parent只是拷贝了text,data,stack,heap段，也即只有这些段是需要copy on write的。剩下的trapframe和trapoline不是cow的。
1. copy on write时遇到的问题，解决。
- 关于getref(PTE2PA(*pte) <= 1)
- 关于walkaddrforwrite的问题
  - 如果1child 1parent
    - 那么如果是一个child写的话，那么除了将child本身的这个pte重新建立映射之外，还需要将其parent置为可写。
    - 那么如果是一个parent写的话，那么除了将parent本身的这个pte重新建立映射之外，还需要将其child置为可写，那么如何获取其child？
  - 如果多child 1parent
    - 那么1child写了，只是将1child本身的相应pte进行更新，其余的仍然映射到那个pg，仍然只读
    - 如果1parent写了，只是将1parent本身的相应pte进行更新，其余的仍然映射到那个pg，仍然只读
    - 只有当最后一个写proc的时候（即其他proc都已经写过），才不需要新建mem，改变pte，重新建立映射，只要将置成pte可写，然后直接写内存即可。
  - 显然上述想法有些可笑，不必在一个user的pte进行真分配的时候考虑其他process。每个process只考虑izji就可以。
- 所以通过pagefault handler时检查physical page的引用计数解决上述问题。当引用计数为1时代表只有一个人引用这个内存。
1. 引用计数时遇到的bug
- 1. 一开始想在run结构体增加成员 ref_cnt 代表该page正在引用的次数。
  - 想想就不行。不能在run里增加成员。因为那个也是physical page的头部。当把pg分配出去，那个结构体就被覆盖了。何谈引用计数
  - 所以单独建一个数组，来表示每个pg的引用次数。
- 1. 一开始想在mappages和munmap的时候，增加/减少引用计数。而并不是在kalloc和kfree时。结果一输入命令就panic init exiting.
  - 不能这样。因为一开始kernel pgtbl就会建立所有映射，可也没有kalloc。如果按如上方案的话，在kfree的时候，ref_cnt的引用计数应当为1，(并且我们还只对dram进行计数，还需要判断)。
  - 如果只是这样倒也罢了。可是还有一些其他地方只kalloc了，却并没有建立映射。并且从逻辑上来讲这个引用计数就应当只涉及调用了fork的user pgtbl，这样做会引入kernel pgtbl，徒增复杂性。且如hint所说，kfree() should only place a page back on the free list if its reference count is zero。调试的时候就这里耗时醉酒，赶紧放弃这种计数方法。
  - 改成在kfree和kalloc和uvmcopy时维护计数。

问题

1. ok : fork在什么时候被调用。cow和那些pgtbl有关，与kernel pgtbl有关吗？
- fork只会由user process调用
- 只和user pgtbl有关。
  - cow va只会在fork情况下产生。而fork又只会由sys_fork调用，也即，只会由用户程序通过fork()调用。因此cow只和user pgtbl有关。
- 对于kernel pagetable 很显然不会有copy on write发生，因为全局始终只有一个kernel pagetable。且child拷贝pagetable也不会拷贝kernel pagetable。最一开始的fork拷贝的是initcode的pgtbl吧？
1. ok : mem被映射和被使用并不是完全相同的概念。
- 对于kernel pagetable 映射了所有的physical memory ，但是却并没有都使用。因此 mappages时不可ref_cnt++。
- 但是对于user pgtbl，其映射了一块另一个user pgtbl的所拥有的mem，即代表这块mem为本user pgtbl所拥有，则引用计数++。因此kalloc和uvmcopy都需要ref_cnt++。
1. ok : kernel给user分配dram段内存需要通过kalloc，那么kernel自己使用dram段的内存呢？
- 也需要。
- 诚然，kernel在刚一开始就全权拥有所有物理内存，鉴于直接映射，kernel也可以直接使用dram的物理内存。不过还是要通过kalloc来获取一下，以防止其使用的内存被其他地方使用或者被user使用。如下kernel使用kalloc给kernel使用

1. 同学问的问题：父进程对一个地址进行了写触发pagefault,进行了copy on write之后，子进程再写还会不会触发page fault？
- 会, 因为u
- 会 , fork的时候比如说父进程fork出ABCDEF这些个进程，他们的pagetable是一样的。（因为子进程拷贝了父进程的pagetable），然后当某一进程比如说A进程在用户态对A进程的virtual address写，会触发pagefault，因为pte之前在fork的时候就被标记成需要copy on write的，对该pte引用的地址写会被mmu检测并触发pagefault，然后在pagefault handler中，会在该A进程的page table上，找到这个va对应的pte，修改pte，为这个va建立一个到新一块物理页的映射（不再是之前和其他进程共用的物理页），然后将pte的标志位置成不需要copy on write的。然后，当又有B进程对该va进行写入，那么，同理，B pagetable的pte仍然是被标志成需要copy on write的，所以他也会触发pagefault，同样会进入pagefaulthandler，进行新物理页的分配。

大部分时间都耗在了开机之前
开机成功之后直接过了cowtest
然后usertests也几分钟就改完了.爽!