实验：Lab: COW

实验开始之前需要将git分支切换到cow分支不然有些文件你是没有的

1
2
3
$ git fetch
$ git checkout cow
$ make clean

COW

简介

普通fork的问题

一个进程调用fork后会创建和父进程一样大的物理内存空间，并拷贝父进程的物理内存的内容。这样会造成物理空间的浪费，以shell程序为例运行一个命令首先会调用fork拷贝父进程，然后使用exec将程序重新写入子进程的空间。

在这种情况下，首先创建和父进程一样大的空间会造成空间的浪费，其次将父进程的内容拷贝到子进程有使用exec覆盖内存会浪费时间。

copy-on-write fork

copy-on-write fork是缺页(异常操作)的一种应用场景，几乎在所有操作系统中都实现了这个功能。

==COW==怎样解决上述普通fork的问题？

像是惰性分配(lazy allocation)的方式，先不创建物理页表而是进程，当进程需要使用这部分内存时再分配。

所以COW fork的具体实现就是，在使用fork创建子进程时，只是给子进程创建一个页表,将子进程的虚拟页映射到父进程的物理页，并且将子进程的PTE与父进程的PTE设置为不可读(清空PTE_W位)。那么当运行子进程时，需要写入对应的物理页时就会触发缺页异常。trap处理程序会识别缺页异常，在cow处理程序中新建物理页，并重新设置页表的PTE映射到该物理页并设置标志位。

Q：为什么要将父进程也设置为不可读？

A：我们要保持父进程与子进程的隔离性，那么父进程如果可以直接写这个物理页，那么子进程就可以看见了父进程的数据了。

COW实验

要求

本次实验是在xv6中完成cow fork功能。需要通过cowtest的测试与usertests -q测试。

实验的输出结果如下：使用make grade便可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ cowtest
simple: ok
simple: ok
three: zombie!
ok
three: zombie!
ok
three: zombie!
ok
file: ok
ALL COW TESTS PASSED
$ usertests -q
...
ALL TESTS PASSED
$

提示

建议观看lecture8，这节课介绍了缺页错误的基本处理方式与COW的实现原理。

当usertrap发现错误时，可以通过scause的参数看如下的表中关于引起trap类型。在实验中我们主要是处理写入物理页错误(主要是因为PTE_W没有设置会被mmu检测出来)，那么相应的scause数值是0xf=15，代表载入缺页(store page fault)，通过scause参数我们也可以发现出现了这条命令不是中断触发的，因此这里的缺页是属于一种异常操作(读取了非法的物理地址，由mmu检查得出)。

scause

实现

开始

本次实验主要是修改fork的拷贝方式，那么首先我们要看看fork是如何拷贝的，看下述代码我们可以知道fork主要是使用了uvmcopy实现了内存的拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int
fork(void)
{
  // 为子进程创建页表并建立trapframe与trampoline的映射
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  ....
}

接着就是修改uvmcopy函数的拷贝逻辑了。

修改fork拷贝方式

在下述注释的代码中，xv6为子进程新建了物理页，拷贝父进程的内存内容，并将子进程的的虚拟地址映射到新的物理页上。

根据cow fork的原理则是将子进程的虚拟地址映射到父进程的物理页上。需要注意以下几点

  • 设置父进程与子进程的pte标志位，清空PTE_W，添加cow fork识别位(PTE_F=1L << 8)
  • 增加对于物理页的引用计数
  • mappages将子进程的虚拟地址映射到父进程的物理地址

Q：为什么要添加PTE_F位?

A：cow fork是一种特殊的缺页处理方式，将pte的写位清空后会触发缺页异常，那么当其他物理页也是只读也触发了缺页异常，显然不能够与cow fork的处理方式一样所以，需要标记这个位。

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
----vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
    ....
    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);    //parent's physical page address

      *pte &= ~PTE_W;       //clear the write flag
      *pte |= PTE_F;
      flags = PTE_FLAGS(*pte);   
      // if((mem = kalloc()) == 0)
      //   goto err;
      // memmove(mem, (char*)pa, PGSIZE);
      if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
        kfree((void*)pa);
        goto err;
      }
      increRC((void*)pa); // increase physical page's ref count, encapsulation data RC , increRC is method for it
    }
    ....
 }

改完uvmcopy函数后会出现了没有处理scause=15的缺页异常的处理函数的问题。

处理COW缺页错误(trap.c)

当uvmcopy建立好映射后，当子进程或者父进程写入物理页时就会触发缺页异常，那么根据scause的值xv6需要对15这个值进行对应的处理。

编写一个函数称为cowfault通过输入进程的页表与错误的虚拟地址便可以处理cow fork的缺页异常了。如果cowfault返回值为-1说明有非法参数，或是pte的设置错误，那么xv6会杀死对应的进程。返回值为0则是成功。

cowfault的执行流程

  1. 检测虚拟地址是否合法
  2. 通过walk获得缺页错误的虚拟地址pte，并检测pte的权限位。
  3. 生成物理地址(子进程与父进程共同使用的物理页地址)
  4. 获得这个物理页的引用计数，如果引用计数为1说明此时只有一个进程在使用这个物理页，我们只需要修改权限位即可(添加PTE_W与清空PTE_F)。
  5. 反之我们有多个进程在使用一个物理页，因此我们需要重新分配新的物理页，拷贝原理的物理页的内容。
  6. 调用kfree：这个函数会在kalloc被重新调整，通过引用计数判断是否能够释放内存。
  7. 判断虚拟地址的数据，如果va == 0的话说明这个页是代码段页，那么我们是不能修改这个页面的，也就是不能添加写位。修改pte的值将虚拟内存的地址指向新建的物理。

Q：我们为什么不用在cowfault处理函数修改父进程或子进程的pte权限位

A：首先两个进程是隔离的，我们不能获取另一个进程的页表数据。其次，如果是父进程或子进程的pte中没有写权限，那么我们仍然会触发cow fault，这样的话在cowfault函数中新建物理页并拷贝，或是新增pte的权限(上述第4点)

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
----trap.c
int
cowfault(pagetable_t pagetable,uint64 va){
    if(va >= MAXVA)
      return -1;

    pte_t* pte = walk(pagetable,va,0);

    if(pte == 0)
      return -1;

    if((*pte & PTE_U) == 0 || (*pte & PTE_V) == 0|| (*pte & PTE_F) == 0)
      return -1;
    
    uint64 pa = PTE2PA(*pte); 

    int rc = getRC((void*)pa);
    if(rc == 1){//rc == 1 means don’t copy src physical page
      *pte |= PTE_W;
      *pte &= ~PTE_F;
      return 0;
    }

    uint64 new = (uint64)kalloc();
    if(!new){
      return -1;
    }

    memmove((void*)new , (void*)pa ,PGSIZE);//copy parent's physical memory

    kfree((void*)pa); // just reduce old pg's ref count , not free the physical page
    if(PGROUNDDOWN(va) == 0){
      *pte  = PA2PTE(new) | PTE_V | PTE_R | PTE_U | PTE_X; 
    }else{
      *pte  = PA2PTE(new) | PTE_V | PTE_R | PTE_W | PTE_U | PTE_X; // remap
    }

    return 0;
}

void
usertrap(void)
{
  ....
  if(r_scause() == 8){{
      ....
  } else if((which_dev = devintr()) != 0){
    // ok
  }else if(r_scause() == 15 ){
    if(cowfault(p->pagetable,r_stval())<0){
      p->killed = 1;
    }
  }
  ....
}

引用计数(kalloc.c)

kalloc是关于物理页的分配。那么对cow的功能实现后我们需要添加物理页引用计数，不能让kfree随意的释放物理页(像是c++的share_ptr)。

实现流程

  1. 添加一个物理页编号的数组，作为物理页的引用计数。所以物理页都需要编号包括硬件设备的物理页，不然kfree释放或是kalloc分配时会因为引用计数的问题出现错误。
  2. kalloc函数：初始化物理页的引用计数，当有函数调用kalloc时说明对应的物理页已经被应用了并且将引用计数设置为1。

为什么需要加锁，因为在多核cpu下对于物理页的分配或是引用计数的操作会产生竞争

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
----kalloc.c
int RC[PHYSTOP/PGSIZE];
 
void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;

  if(r){
    kmem.freelist = r->next;
    int pn = (uint64)r/PGSIZE;
    if(RC[pn] != 0){
      panic("kalloc");
    }
    RC[pn] = 1;
  }
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  
  return (void*)r;
}
  1. kfree函数：减少物理页的引用计数，当引用计数降为1时释放这个物理页。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  acquire(&kmem.lock);
  int pn = (uint64)pa / PGSIZE;
  if(RC[pn]<1)
    panic("kfree rf");
  int tmp = --RC[pn];
  release(&kmem.lock);

  if(tmp > 0)
    return;
  ....
}

  1. 添加引用计数变量的接口(封装RC变量)：

    • getRC：便于在cowfault中判断是否只有一个进程使用该物理页。

    • increRC：便于在uvmcopy函数中调用并增加该物理页的引用计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//获得物理页的引用计数
int
getRC(void *pa){
  acquire(&kmem.lock);
  int pn = (uint64)pa/PGSIZE;
  int tmp = RC[pn];
  release(&kmem.lock);
  return tmp;
}
//增加物理页的引用计数
void 
increRC(void *pa){
  acquire(&kmem.lock);
  int pn = (uint64)pa/PGSIZE;
  if((uint64)pa >= PHYSTOP || RC[pn] < 1)
    panic("incre");
  RC[pn]++;
  release(&kmem.lock);
}
  1. 在xv6最开始时，初始化都会调用kfree清空物理内存，最开始RC数组内的变量都为0，调用kfree就会出现panic，这时只需要将RC初始为1即可。
1
2
3
4
5
6
7
8
9
10
11
12
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    //初始化所有物理页的引用计数
    RC[(uint64)p / PGSIZE] = 1;
    kfree(p);
  }
}

cow遗漏之处

Fault: 在cowtest测试中对于file测试点会出现问题：

因为pipe调用copyout将内核内存(文件描述符)拷贝到用户空间会出现了问题。

内核进程也不能够使用用户进程的虚拟地址去修改用户数据，xv6绕过mmu直接使用物理地址修改了物理页的数据，因此缺乏硬件的支持(检测虚拟地址的PTE)导致在不能写入物理页的情况下通过物理地址写入了数据，从而打破了子进程与父进程的隔离性。

处理方法：检测用户进程虚拟地址与页表对应的PTE的标志位，如果没有PTE_W并且有PTE_F位，那么说明用户进程(cow fork)与其他进程共享物理内存，就应该触发cowfault的处理函数，这样的话就实现了完善的cow fork。

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
35
36
37
38
39
40
----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;

    pte_t* pte = walk(pagetable,va0,0);

    if(pte == 0  || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0)
      return -1;

    if((*pte & PTE_F) != 0 && (*pte & PTE_W) == 0){
      if(cowfault(pagetable , va0) < 0){
        return -1;
      }
    }
      
    pa0 = PTE2PA(*pte);

    // pa0 = 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;
}

NOTE: 上述代码中需要在def.h中补上一些函数的接口

  1. 在vm.c中要调用trap.c的cowfault函数，在def.h中声明

    int cowfault(pagetable_t,uint64)

    如果需要更强的封装性就需要使用void指针，进一步的进行类型强转。

    int cowfault(void*,void*)

  2. 在trap.c与vm.c中调用了kalloc.c中的RC变量的接口也需要声明

    int getRC(void*)

    void increRC(void*)

    上述void*对应的是物理地址这个uint64变量。

总结

本次实验相对于前面的实验算是比较困难的实验，前期在做的时候实在识别不了报出的错误(没有做引用计数的管理)，于是照着看了一遍lecture12，知道了为什么有这些问题出现，并进一步的优化了代码(父进程不需要重新分配物理并将之前的页释放)。

看着教授做完，自己没有怎么过脑子。但是自己在做的过程中也遇到了一些问题，例如textwrite测试中，不能在代码段写入数据的问题。以及引用计数中，擅自释放了物理页的问题。

做完这个实验熟悉了：

  • c语言中面对对象的封装思想：
    • 在kalloc.c中对于RC(引用计数)变量，在def.h文件不能暴露RC变量，而是提供接口如increRC(增加引用计数)、getRC(获得引用计数)。
    • 使用void指针进行类型强转实现更加健硕的封装性，如在def.h中定义这个接口getRC(void *)，实际上我们传入的参数是物理地址(uint64)。
  • 提高安全代码书写的意识，检测非法变量。
  • 操作系统如何管理内存：通过页表这一个抽象实现了隔离与高性能的内存运用。

结果

cow result