xv6-labs-2020.lab5.Copy on Write

Posted on Edited on In Views:
写时复制

lab5 Copy-on-Write

1.作业链接

  • https://pdos.csail.mit.edu/6.828/2020/labs/cow.html

2. 实习内容

2.1 说明

  • 当调用 fork() 的时候，父进程会把其所有的内存都复制给子进程，但是实际上子进程可能都不会去使用这些内存中的内容（例如调用 exec() 自己设置内容）
  • 利用写时复制的技术减少无用内存空间的复制
  • 写时复制（copy-on-write）技术的要求
    • 延迟分配
    • 在必要的时候才进行物理内存的复制
      • 例如父进程写，但是子进程使用的是写之前的内容，不能共享了
  • COW 技术说明
    • 当父进程调用 fork() 的时候，我们只是为子进程创建 pagetable，PTE 指向父进程的物理页，同时标记这段父子进程共享的内存区域为 not writable
    • 当某个进程试图去写这块区域的时候，触发 pagefault，此时开一块新的物理内存区域，把之前的内容复制过去，同时标记为 writeable
    • 对于原来的部分，如果变成独享，则可以标记为 writeable
    • 共享的区域 free 的时候，只有在最后一个进程 free 的时候才真正 free

2.2 一些提示

  • 修改 vm.c:uvmcopy() 实现复制的时候，只是将子进程的 PTE 指向父进程的物理页，同时把父子进程的共享的 PTE 都设置为 not writable（清空 PTE_W 位）
    • 注意 uvmcopy() 只被 fork() 调用
  • 修改 trap.c:usertrap() 识别出 COW 页上的 pagefault，然后调用 kalloc() 分配新的物理页，将旧的物理页复制过来，装载 PTE，设置为 writable（PTE_W 位设置为 1）
  • 保证在 free 的时候，只有最后一个 PTE 引用 free 的时候才释放物理页
    • 可以为每一个物理页设置一个 reference count
    • kalloc() 分配的时候设置为 1
    • fork() 的时候将计数器 +1
      • uvmcopy()
    • kfree() 的时候将计数器 -1，若减到 0 则释放
    • 计数器的实现可以用一个全局数组去记录
      • 初始化为全1，因为有一个 kfree() 的调用
      • 通过物理地址整除 4096 （页大小）去访问
  • 修改 copyout() 去处理内核态可能发生的 cow 导致的 pagefault
    • 处理的机制相同
  • 可以使用 PTE 中的保留位 RSW (reserved for software) 去记录 PTE 指向的页是不是 COW 页
  • kernel/riscv.h 中有一些预定义的宏
  • 如果 COW 触发 pagefault 时内存耗尽，应该把该进程 kill 掉

2.3 实习

(1) 如何维护引用计数

  • 在 xv6 中，我们将 end 到 PHYSTOP 之间的区域用于动态的物理页分配，我们可以在这段区域的开头保留一段区域，将这段区域用于保存引用计数
  • 如果直接保存在栈上的话，感觉太大了，可能会导致栈溢出
  • 我们没有必要计算得很精确，可以直接把数组大小 CNT_INDEXS 设置为如下值

\[ \dfrac{PHYSTOP-end}{PAGE\_SIZE} \]

  • 对于每个元素的大小，因为 xv6 最多只允许 64 个进程，因此我们使用一个 char 去记录就够了
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
// kernel/kalloc.c
struct {
    struct spinlock lock;
    struct run *freelist;
    char *ref_cnt; // 用于记录 reference count 的一个数组
    uint64 ref_start; // 开始分配的物理内存的起始地址(用于计算偏移量)
} kmem;

void freerange(void *pa_start, void *pa_end) {
    char *p;
    // 数组元素为 char(最多 64 进程)
    // sizeof(char) = 1, 不需要乘
    // 计算大小(偏大)
    uint64 size = ((uint64) pa_end - (uint64) pa_start) >> PGSHIFT;
    // 初始化为全 1
    // memset 逐字节设置
    memset(pa_start, 1, size);
    // 开始分配物理内存的位置
    p = (char *)pa_start + size;
    p = (char *)PGROUNDUP((uint64)p);
    acquire(&kmem.lock);
    // 数组起始位置设置为 pa_start
    kmem.ref_cnt = (char *)pa_start;
    kmem.ref_start = (uint64)p;
    release(&kmem.lock);
    for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
        kfree(p);
    }
}
  • 将 kmem.ref_cnt 全部初始化为 1，因为调用 kfree() 的时候，我们会将引用计数 -1
    • 这样刚好可以把所有的物理页的引用计数初始化为 0
    • 但是起始并没有什么关系，我们每次分配的时候会将引用计数记为 0
  • 针对引用计数，我们增加一些辅助的函数
    • 具体的函数和解释见代码
1
2
3
4
// kernel/defs.h
// kalloc.c
uint64          get_ref_cnt_index(uint64);
char            ref_increment(uint64, char);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kernel/kalloc.c
/* 带锁 */
// 对引用计数进行 += inc 的操作
char ref_increment(uint64 pa, char inc) {
  acquire(&kmem.lock);
  char ans = (kmem.ref_cnt[get_ref_cnt_index(pa)] += inc);
  release(&kmem.lock);
  return ans;
}

/* 不带锁 */
// 获取引用计数
uint64 get_ref_cnt_index(uint64 pa) {
  uint64 ans = (pa - kmem.ref_start) >> PGSHIFT;
  return ans;
}

(2) kalloc/kfree

  • 在 kalloc() 分配页得时候，将引用计数置为 1
  • 在 kfree() 释放页得时候，修改并判断引用计数是否为 0
    • 如果为 0 则放回空的链表
    • 如果不为 0 则直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// kernel/kalloc.c
void * kalloc(void) {
    // ...
    if(r) {
        memset((char*)r, 5, PGSIZE); // fill with junk
        // 注意 get_ref_cnt_index() 函数是不加锁的, 因此需要在外面加锁
        kmem.ref_cnt[get_ref_cnt_index((uint64)r)] = 1;
    }
    return (void*)r;
}


void kfree(void *pa) {
    // ...
    char num = ref_increment((uint64)pa, (char)-1);
    // 引用计数不为 0
    if(num > 0) {
        return;
    }
    // ...
}

(3) 修改 uvmcopy()

  • 复制的时候，将子进程的 PTE 指向父进程的物理地址即可，不需要重新分配
  • 判断 PTE 指向的物理页是否可写
    • 如果可写，同时修改 PTE 为 not writable，并设置 PTE 的 PTE_COW 位（RSW 的低位，第 8 位）
    • 如果不可写，则不需要设置 PTE_COW / PTE_W 位
1
2
// kernel/riscv.h
#define PTE_COW (1L << 8) // COW
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
// kernel/vm.c
int uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) {
    pte_t *pte;
    uint64 pa, i;
    uint64 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);

        // 之前的 PTE_W, PTE_COW
        uint64 pte_w_cow_before = *pte & (PTE_W|PTE_COW);
        // 对于可以进行写操作的 PTE, 我们才使用 COW 策略
        // 如果这个页不可写, 我们直接不复制即可
        if(*pte & PTE_W) {
            *pte ^= PTE_W; // *pte &= ~PTE
            *pte |= PTE_COW;
        }
        flags = PTE_FLAGS(*pte);
        if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
            // kfree(mem);
            // 恢复原来的 flags
            *pte &= ~(PTE_COW | PTE_W);
            *pte |= pte_w_cow_before;
            return -1;
        }
        // 引用计数 +1
        ref_increment(pa, (char)1);
    }
    return 0;
}

(4) 识别 pagefault

  • 类似于 lazy allocation，我们需要在 usertrap() 中识别 COW 导致的 pagefault
  • 为了方便，我们封装成一个函数 cow_handler()
    • 判断是否是由于 COW 导致的 pagefault
    • 处理引用计数
    • 重新分配物理内存
    • 在重新分配内存的时候，我们需要进行的操作是直接修改返回的 PTE
      • 因为这 3 级页表的映射关系还是存在的，我们只需要将第 3 级页表中存储的 PTE 直接修改为 PPN|flags
      • 其中 PPN 是新分配的物理地址
1
2
3
// kernel/defs.h
// vm.c
uint64          cow_handler(pagetable_t, uint64);
1
2
3
4
5
6
7
8
9
10
11
12
13
// kernel/traps.c
void usertrap(void) {
    // ...
    else if(r_scause() == 0xf || r_scause() == 0xd) {
        // page fault
        // 获取虚拟页位置
        uint64 va = r_stval();
        if(cow_handler(p->pagetable, va) == 0) {
            p->killed = 1;
        }
    }
    // ...
}
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
// kernel/vm.c
/* va 需要对齐 */
uint64 cow_handler(pagetable_t pagetable, uint64 va) {
    pte_t *pte;
    uint64 pa;

    if(va >= MAXVA)
        return 0;

    pte = walk(pagetable, va, 0);
    if(pte == 0)
        return 0;
    if((*pte & PTE_V) == 0)
        return 0;
    if((*pte & PTE_U) == 0)
        return 0;
    // 不是 COW 页
    if((*pte & PTE_COW) == 0)
        return 0;
    pa = PTE2PA(*pte);

    // 没有内存了
    char *mem;
    if((mem = kalloc()) == 0)
        return 0;
    memmove(mem, (char*)pa, PGSIZE);
    uint64 flags = PTE_FLAGS(*pte);
    kfree((void*)pa);
    flags = (flags & ~PTE_COW) | PTE_W;
    *pte = PA2PTE((uint64)mem) | flags;
    return (uint64)mem;
}

(5) 识别内核态的 cow 导致的 pagefault

  • 这会发生在函数 copyout() 中，于是我们采用相同的策略，这里需要先判断是否是
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
// kernel/vm.c
int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) {
    uint64 n, va0, pa0;
    while(len > 0){
        va0 = PGROUNDDOWN(dstva);
        if (va0 >= MAXVA)
            return -1;
        // 先判断是不是 COW 页
        pte_t* pte = walk(pagetable, va0, 0);
        if(pte == 0)
            return -1;
        if((*pte & PTE_V) == 0)
            return -1;
        if((*pte & PTE_U) == 0)
            return -1;
        // 不是 COW 页
        if((*pte & PTE_COW) == 0) {
            pa0 = walkaddr(pagetable, va0);
        } else {
            pa0 = cow_handler(pagetable, va0);
        }
        // ...
    }
    return 0;
}

3. 实验结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ make qemu-gdb
(24.2s)
== Test   simple ==
  simple: OK
== Test   three ==
  three: OK
== Test   file ==
  file: OK
== Test usertests ==
$ make qemu-gdb
(211.7s)
== Test   usertests: copyin ==
  usertests: copyin: OK
== Test   usertests: copyout ==
  usertests: copyout: OK
== Test   usertests: all tests ==
  usertests: all tests: OK
== Test time ==
time: OK
Score: 110/110

4. 遇到的困难以及收获

  • 这个 lab 想起来难度并不是很大，思路在网页中也写得很清楚，但是很多细节还是很花费时间的
  • 做完 lab 之后对于 cow 整体的实现也有了更加深入的理解
  • 同时对一些细节的处理也让我收获颇丰，例如这里关于 PTE 的处理，直接修改 PTE 的内容而不是重新映射，这样的设计确实很巧妙
  • 同时通过 lazy allocation 和 cow 这两个 lab，也让我们意识到了，在设计的过程中要同时考虑用户态的内核态的异常
    • 例如 pagefault
      • 用户态的 pagefault 可以在 usertrap() 中考虑（产生后利用异常机制处理）
      • 内核态的 pagefault 需要在 copyout() 中考虑（产生的地方）

5. 对课程或 lab 的意见和建议

  • 暂时没有意见

6. 参考文献

  • https://pdos.csail.mit.edu/6.828/2019/xv6/book-riscv-rev0.pdf
  • https://pdos.csail.mit.edu/6.828/2020/labs/cow.html