乐趣区

关于c:MIT-6181068286S081-操作系统工程-Lab5-CopyonWrite-Fork

jiezi

前言

虚拟内存提供某种间接援用：内核能够通过将 PTE 标记为有效或只读来截获内存援用，从而导致页面谬误，也能够通过批改 PTE 来更改地址含意。计算机系统中有一个说法：任何零碎问题都能通过某种间接援用来解决。本试验探讨了一个示例：copy-on-write(COW)fork

问题

xv6 中的 fork()syscall 复制父过程所有用户空间的内存到子过程中。如果父过程很大，这个拷贝过程就会花很长时间。更蹩脚的是，这个拷贝常常被节约：fork() 函数后子过程通常追随一个exec()，这会抛弃复制的内存、通常不应用大部分内存。另一方面，若父子过程其中一个或都写入了这个复制的页面，则这个拷贝过程是须要的。

解决方案

你在实现 COW fork() 过程中的指标是，推延开拓空间和拷贝物理内存页直到真正须要这些拷贝时。
COW fork()仅为子过程创立一个页表，其中用于用户内存的 PTE 指向父过程物理页。COW fork()将父子过程所有用户 PTE 都标记为只读。当任一过程尝试写入这些 COW 页之一时，CPU 将强制呈现页谬误。内核页面谬误处理程序检测到这种状况，为谬误过程调配一页物理内存，将原始页面复制到新页面中，并在谬误过程中批改相干 PTE 以援用新页面，这次 PTE 标记为可写。当页面谬误处理程序返回时，用户过程将可能写入其页面正本。

COW fork()使开释实现用户内存的物理页面变得更加辣手。给定的物理页可能由多个过程的页表援用，并且仅当最初一个援用隐没时才应开释。在像 xv6 这样的简略内核中，这种相当简略，但在生产内核中，这可能很难正确。例如，Patching until the COWs come home.

要求

在 xv6 内核中实现 copy-on-write fork。

为帮忙你的实现，咱们曾经提供了一个程序指令 cowtest（源码在user/cowtest.c）。cowtest 运行各种测试，但如果过没有更改 xv6 即使第一个测试也会失败。
这个“简略的”测试开拓超过一半的可用物理内存，而后 fork()s。个别状况下，fork 会因为没有足够的闲暇物理内存给子过程一个残缺的拷贝而失败。
当你实现后，该当通过 cowtest usertests -q 的所有测试。

正当的 attack 打算

  1. 批改 uvmcopy() 以将父级的物理页面映射到子级，而不是调配新页面。革除子级和父级的 PTE 中已被置位 PTE_W 的PTE_W位。
  2. 批改 usertrap() 以辨认页面谬误。当最后可写的 COW 页面上产生写入页面谬误时，应用 kalloc() 调配一个新页面，将旧页面复制到新页面，并在被置位为 PTE_W 的 PTE 中装置新页面。最后为只读的页面（未映射 PTE_W，如文本段中的页面）应放弃只读并在父过程和子过程之间共享; 尝试编写此类页面的过程应该被kill()。
  3. 确保每个物理页在最初一个 PTE 援用隐没时被开释 – 但不是之前。执行此操作的一个好办法是为每个物理页面保留援用该页面的用户页表数量的“援用计数”。将页面的援用计数设置为 1 当 kalloc() 调配它时。当 fork 导致子级共享页面时，递增页面的援用计数，并在每次任何过程从其页表中删除页面时递加页面的计数。kfree()应该只在援用计数为零时将页面放回自在列表。能够将这些计数保留在固定大小的整数数组中。您必须制订一个如何索引数组以及如何抉择其大小的计划。例如，你能够用页面的物理地址除以 4096 来索引数组，并为数组提供一个数字，这个数等于 kalloc.c 中的 kinit() 搁置在闲暇列表中的任何页面的最高位物理地址。能够随便批改kalloc.c（例如kalloc(), kfree()）来保护援用计数。
  4. 批改 copyout() 以在遇到 COW 页面时应用与页面谬误雷同的计划。

提醒

  • 记录每个 PTE 是否是 COW 映射会很有用。为此，你能够应用 RISC-V PTE 的 RSW（软件预留）置位。
  • 无关页表 flags 的一些有用的宏和定义位于 kernel/riscv.h 开端。
  • 若产生一个 COW 页面谬误且内存不够，则该过程该当被kill

实现

  1. 复制页表但推延复制页表内容 ：依据提醒，我从fork() 中调用的 uvmcopy() 动手。uvmcopy()本来的作用是：把父过程页表中每个 PTE 所指内容都拷贝到新开拓的空间内并在子过程的页表上造成映射。当初须要把开拓空间这一步去掉，间接在子页表造成映射，然而要扭转 flags。为了让代码难看点、放弃逻辑清晰，我创立一个新函数 cow_uvmcopy() 并在 uvmcopy() 中调用它。新函数根本与老函数保持一致，不过去掉开拓空间、加上扭转 flags：

    int cow_uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) {
    pte_t *pte;
    uint64 pa, i;

    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 = (*pte & (~PTE_W)) | PTE_C;  // 错的！（后续阐明）if (*pte & PTE_W) {
            // 把父过程 PTE 的 PTE_W 地位 0，再加上 PTE_C 位
            *pte = (*pte & (~PTE_W)) | PTE_C;
        }
        // 间接将父过程物理地址在子过程页表中建设映射
        if(mappages(new, i, PGSIZE, (uint64)pa, PTE_FLAGS(*pte)) != 0) {goto err;}
        increaseReference(pa);  // 援用计数 +1（后续阐明）}
    return 0;

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

    无关 flags 的设置：首先要把父子过程的 PTE_W 给去掉，这样能力在未来触发 page fault。而后就是加上对于 cow 的标记，须要在 riscv.h 中自定义，能够定义在预留位上（详见 Lab3 page tables）#define PTE_C (1L << 8)。未来可通过该 bit 位判断是本来就不可读的还是 cow 机制强加的不可读。

  2. 更改 trap 以碰到 page fault 时开拓空间拷贝内容 ：依据题目给的计划第 2 点，须要在usertrap() 中辨认须要 cow 的 page fault 状况，开拓空间并拷贝，而后扭转只读的权限置位进而使程序可能写入指定内存。

    • usertrap()自身就算一个抉择构造，比方当产生零碎调用时，通过 r_scause() == 8 进入 syscall 分支调用 syscall()。因而此处只须要增加一个else if 分支来解决 page fault
    • 对于辨认须要 cow 的 page fault 状况：其实在 2020 年的课程中，本试验前边还有一个试验[Lab: xv6 lazy page allocation

    ](https://pdos.csail.mit.edu/6.828/2020/labs/lazy.html)，其中给出了对于辨认 page fault 的提醒r_scause() == 13 || r_scause() == 15（也能够只判断 15 时，13 代表读，15 代表写）。

    • 具体实现。因为 copyout 也须要解决此状况，因而把业务逻辑代码放入函数封装

      if (...) { // 其余状况
    ...
} else if (r_scause() == 13 || r_scause() == 15) { // page fault 状况
    // 页面谬误, 调配空间并拷贝
    // 在 walkaddr 函数实现状况判断和调配空间并拷贝的业务
    if (cow_walkaddr(p->pagetable, r_stval()) == 0) {goto error;  // 解决失败或遇到并非 cow 的 page fault} else {
error: 
    // 该分支通过打印信息而后 kill 掉过程来解决未知中断状况，// 对于不须要 cow 的 page fault 状况可设置标签将其跳转到此处
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("sepc=%p stval=%p\n", r_sepc(), r_stval());
    setkilled(p);
}

    • 实现状况判断和调配空间并拷贝业务的 cow_walkaddr()。参考walkaddr() 函数（通过给定 page table 和虚拟地址返回物理地址，失败返回 0）。cow_walkaddr()逻辑是：通过给定 page table 和虚拟地址，若非 cow 状况则象 walkaddr() 一样返回物理地址；若是 cow 状况，则开拓新空间、拷贝内存、接触旧的只读映射、建设新的可写映射。

      uint64 cow_walkaddr(pagetable_t pagetable, uint64 va) {
    pte_t *pte;
    uint64 pa;
    int flags;

    if(va >= MAXVA)
        return 0;

    pte = walk(pagetable, va, 0); // 虚拟地址对应 PTE
    if (pte == 0) return 0;
    else if ((*pte & PTE_V) == 0) return 0;
    else if ((*pte & PTE_U) == 0) return 0;

    pa = PTE2PA(*pte);

    flags = PTE_FLAGS(*pte);
    if (flags & PTE_W) return pa; // 若有 PTE_W 阐明不是 cow
    else if ((flags & PTE_C) == 0) return 0;  // 判断是否带 PTE_C

    void* new_mem = kalloc();  // 新页面空间    
    if (new_mem == 0) 
    return 0;

    memmove(new_mem, (const void*)pa, PGSIZE);  // 拷贝页面空间
    uvmunmap(pagetable, PGROUNDDOWN(va), 1, 1);  // 解除 map 并开释空间
    flags = (flags | PTE_W) ^ PTE_C;  // 新 flags
    // 建设新 map
    if (mappages(pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)new_mem, flags) != 0) {kfree(new_mem);
        return 0;
    }  
    return (uint64)new_mem;
}

  3. 内存空间援用计数 ：依据提醒可知基本思路是：对每个物理内存都标记一个数字示意该内存被援用次数，当kalloc() 的时候置 1，每次 fork 和 copyout 的时候 +1；而 kfree() 的时候先将该数字 -1，而后判断只有当该数字为 0 的时候才真正开释该内存。

    • 由此，在新文件 ref_cnt.c 中实现援用次数保留、援用次数减少缩小性能。

      // ref_cnt.c
#include "types.h"
#include "memlayout.h"
#include "riscv.h"
#include "defs.h"
#include "spinlock.h"

static int ref_cnts[PHYSTOP / 4096];  // 依据提醒设置数组大小
// 因为波及并发的共享内存问题，因而须要🔒
// 能够应用一个锁。// 但实际上每个援用计数之间并没有抵触，因而也能够离开应用锁
static struct spinlock locks[PHYSTOP / 4096];

void increaseReference(uint64 pa) {uint64 idx = (pa) / 4096;
    acquire(locks + idx);
    ++ref_cnts[idx];
    release(locks + idx);
}

int decreaseReference(uint64 pa) {
    int ret;
    uint64 idx = (pa) / 4096;
    acquire(locks + idx);
    ret = --ref_cnts[idx];
    release(locks + idx);
    if (ret < 0) { // 排除援用计数为正数的状况
        panic("reference count: -1");
    }
    return ret;
}

      别忘了在 defs.h 中申明函数

    • 援用计数初始化：kalloc()须要将援用计数置 1。因为没应用的内存援用计数为 0，因而这里间接采纳减少的形式初始化。
    • 援用计数减少：在刚 fork() 后父子过程共享内存时，内存实际上被援用 2 次。具体该当在 fork() 复制父页表到子页表（间接与父过程物理地址建设映射）时减少援用计数。即在 cow_uvmcopy() 中，映射建设胜利后调用increaseReference()。(前边已有标记)

    • 援用计数缩小：依据提醒，在 kfree() 中先缩小援用次数、再判断是否须要真的开释——即在 kfree() 结尾退出系列命令：

      void kfree(void *pa) {
    // 将援用计数 - 1 并判断以后援用计数是否为 0
    // 若大于 0 则间接返回函数
    if (decreaseReference((uint64)pa) > 0) return;
    ...
}

    • 其余：实际上 xv6 在初始化时会先 kfree() 一波，这时候所有援用计数都还是 0，kfree的时候会产生援用计数为 - 1 的谬误状况，因而可将所有援用计数初始化为 1 或初始调用 kfree() 前先将援用计数 +1：在 kalloc.c 的kinit()中初始化内存，调用 freerange() 来kfree内存，因而在 freerange() 中的 kfree() 之前加increaseReference():

      void freerange(void *pa_start, void *pa_end) {
    char *p;
    p = (char*)PGROUNDUP((uint64)pa_start);
    for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {increaseReference((uint64)p);
        kfree(p);
    }
}

  4. 在 copyout() 中增加同样的解决：

    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);
        // 之前曾经封装好函数，这里只须要把 walkaddr 换成 cow_walkaddr
        pa0 = cow_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;
}

遇到的问题

  1. panic: reference count = -1（援用计数为 -1）

    最开始跑的时候连第一个都过不去，就报这个援用计数 -1（本人设置的）的 panic。想了半天反馈过去：因为我依照提醒程序，先写了 cow_uvmcopy() 实现页表复制，再写援用计数，以至于再复制页表的时候忘加援用计数递增了。因而在 cow_uvmcopy() 中加上援用计数递增就解决了。

  2. textwrite failed

    这个谬误不是很显著。在过了所有 cowtest 的同时，还过了大部分 usertests。只有到这个textwrite 的时候才呈现谬误，对应了调试实践中 bug-error-failure 过程中兴许会差很多个状态转移。又试了又想了半天，才搞明确 bug，其实在提醒 2 中也有提醒：将本来可写的 PTE 设为不可写，而后触发谬误；然而对于本来就不可写的，就要统一放弃父子过程共享，不能 cow。
    我最后写 cow_uvmcopy() 的时候没有思考这一点，间接用 *pte = (*pte & (~PTE_W)) | PTE_C; 一刀切地把 PTE 的 PTE_W 去掉（因为感觉没有 PTE_W 的 PTE 这一步也没影响）而后加上 PTE_C 位（然而这一步就产生很大影响）。退出 cow 机制后，在试图写入不可写内存时有两种状况：（1）触发 cow 机制，须要开拓新内存拷贝 …（2）这个内存本来就不可写，这时候是真的 page fault。而我一刀切的办法，将本来不可写的内存也加上了 PTE_C 位，就无奈判断出第（2）种状况了，后果全是第（1）种。因而，通过退出判断本来的 PTE 是否可写再去扭转置位就能防止这种状况：

    if (*pte & PTE_W) {
    // 把父过程 PTE 的 PTE_W 地位 0，再加上 PTE_C 位
    *pte = (*pte & (~PTE_W)) | PTE_C;
}

后果

  • 运行后果
  • 测试后果

总结

  • 通过该试验对 COW 机制的基本原理有了意识和了解，也感叹计算机前辈们可能思考出并实现该机制的厉害！
  • C++ 智能指针援用计数用法也可间接在内存上应用！
  • 对创立过程有了更深刻的了解！
退出移动版