MIT6.828 LAB4_PartB Copy-on-Write Fork


Copy-on-Write Fork

但是,对子进程中的fork调用几乎会立即调用exec,后者用新程序替换子进程的内存。 例如,这就是shell通常所做的事情。

更高版本的 Unix 利用虚拟内存硬件来允许父子进程共享映射到各自地址空间的内存,直到其中一个进程实际修改它。 这种技术称为写时复制(Copy-on-Write Fork)。为此,在fork上,内核会将地址空间映射从父级复制到子级而不是映射页面的内容,同时将现在共享的页面标记为只读。 当其中一个进程尝试写入其中一个共享页面时,该进程会发生页面错误。

User-level page fault handling

Copy-on-Write 只是用户级页面错误处理的许多可能用途之一。

我们将利用用户级页面错误处理方式,来决定如何处理用户空间中的每个页面错误,而不采用传统的Unix方法,因为其产生的错误的破坏性较小。 这种设计的另一个好处是允许程序在定义内存区域时具有很大的灵活性; 稍后我们将使用用户级页面错误处理来映射和访问基于磁盘的文件系统上的文件。

Setting the Page Fault Handler

In order to handle its own page faults, a user environment will need to register a page fault handler entrypoint with the JOS kernel.

Exercise 8

Implement the sys_env_set_pgfault_upcall system call. Be sure to enable permission checking when looking up the environment ID of the target environment, since this is a "dangerous" system call.

static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
    // LAB 4: Your code here.
    struct Env *e;
    if (envid2env(envid, &e, 1)) 
        return -E_BAD_ENV;

    e->env_pgfault_upcall = func;
    return 0;
}

Normal and Exception Stacks in User Environments

本质上,我们将使JOS内核代表用户环境实现自动“堆栈切换”,就像x86处理器在从用户模式转换到内核模式时代表JOS实现堆栈切换一样!
到目前为止出现了三个栈:

  [KSTACKTOP-KSTKSIZE,  KSTACKTOP) 
  内核态系统栈

  [UXSTACKTOP - PGSIZE, UXSTACKTOP )
  用户态错误处理栈

  [UTEXT, USTACKTOP)
  用户态运行栈

内核态系统栈是运行内核相关程序的栈,在有中断被触发之后,CPU会将栈自动切换到内核栈上来,而内核栈是在kern/trap.c的trap_init_percpu()中设置的。

Invoking the User Page Fault Handler

我们现在需要更改kern / trap.c中的页面错误处理代码,以便在用户模式下处理页面错误,如下所示。 我们将故障时的用户环境称为 trap-time 状态。

                    <-- UXSTACKTOP
trap-time esp
trap-time eflags
trap-time eip
trap-time eax       start of struct PushRegs
trap-time ecx
trap-time edx
trap-time ebx
trap-time esp
trap-time ebp
trap-time esi
trap-time edi       end of struct PushRegs
tf_err (error code)
fault_va            <-- %esp when handler is run

Exercise 9

Implement the code in page_fault_handler in kern/trap.c required to dispatch page faults to the user-mode handler. Be sure to take appropriate precautions when writing into the exception stack. (What happens if the user environment runs out of space on the exception stack?)

struct UTrapframe {
    /* information about the fault */
    uint32_t utf_fault_va;    /* va for T_PGFLT, 0 otherwise */
    uint32_t utf_err;
    /* trap-time return state */
    struct PushRegs utf_regs;
    uintptr_t utf_eip;
    uint32_t utf_eflags;
    /* the trap-time stack to return to */
    uintptr_t utf_esp;
} __attribute__((packed));

这一小节脑袋有点晕,具体参考这位大佬的分析MIT6.828 Part B: Copy-on-Write Fork
相比于Trapframe,这里多了utf_fault_va,因为要记录触发错误的内存地址,同时还少了es,ds,ss等。因为从用户态栈切换到异常栈,或者从异常栈再切换回去,实际上都是一个用户进程,所以不涉及到段的切换,不用记录。在实际使用中,Trapframe是作为记录进程完整状态的结构体存在的,也作为函数参数进行传递;而UTrapframe只在处理用户定义错误的时候用。

  • 当正常执行过程中发生了页错误,那么栈的切换是

    • 用户运行栈—>内核栈—>异常栈
  • 而如果在异常处理程序中发生了也错误,那么栈的切换是

    • 异常栈—>内核栈—>异常栈

当异常发生时,若用户环境已经运行在异常栈上,应该在当前的栈指针tf->tf_esp下建立新的栈帧。应该首先压入32 bit的空字,然后再压入struct UTrapframe结构体。

   struct UTrapframe *utf;
    
    if (curenv->env_pgfault_upcall) {
        
        if (tf->tf_esp >= UXSTACKTOP-PGSIZE && tf->tf_esp < UXSTACKTOP) {
            // 异常模式下陷入
            utf = (struct UTrapframe *)(tf->tf_esp - sizeof(struct UTrapframe) - 4);

        }
        else {
            // 非异常模式下陷入
            utf = (struct UTrapframe *)(UXSTACKTOP - sizeof(struct UTrapframe));    
        }
        // 检查异常栈是否溢出
        user_mem_assert(curenv, (const void *) utf, sizeof(struct UTrapframe), PTE_P|PTE_W);
            
        utf->utf_fault_va = fault_va;
        utf->utf_err      = tf->tf_trapno;
        utf->utf_regs     = tf->tf_regs;
        utf->utf_eflags   = tf->tf_eflags;
        // 保存陷入时现场,用于返回
        utf->utf_eip      = tf->tf_eip;
        utf->utf_esp      = tf->tf_esp;
        // 再次转向执行
        curenv->env_tf.tf_eip        = (uint32_t) curenv->env_pgfault_upcall;
        // 异常栈
        curenv->env_tf.tf_esp        = (uint32_t) utf;
        env_run(curenv);
    }
    else {
        // Destroy the environment that caused the fault.
        cprintf("[%08x] user fault va %08x ip %08x\n",
            curenv->env_id, fault_va, tf->tf_eip);
        print_trapframe(tf);
        env_destroy(curenv);
    }

异常栈都发生 overflow 时,会进入 user_mem_assert, 然后会 destroy 这个 env 。

User-mode Page Fault Entrypoint

接下来,我们需要实现一个汇编代码块,该例程将负责调用C页面错误处理程序并在原始错误指令处继续执行。 此汇编语言例程是一个 handler, 内核将使用sys_env_set_pgfault_upcall()对其进行注册。

Exercise 10.

Implement the _pgfault_upcall routine in lib/pfentry.S. The interesting part is returning to the original point in the user code that caused the page fault. You'll return directly there, without going back through the kernel. The hard part is simultaneously switching stacks and re-loading the EIP.

_pgfault_upcall是所有用户页错误处理程序的入口,在这里调用用户自定义的处理程序,并在处理完成后,从错误栈中保存的UTrapframe中恢复相应信息,然后跳回到发生错误之前的指令,恢复原来的进程运行。这一部分的解答,需要严格注意struct UTrapFrame各个字段的大小,详细过程以注释给出。


  // Struct PushRegs size = 32 
  addl $8, %esp                 // esp+8 -> PushRegs   over utf_fault_va utf_err
    movl 0x20(%esp), %eax         // eax = (esp+0x20 -> utf_eip )
    subl $4, 0x28(%esp)           // for trap time eip 保留32bit,   esp+48 = utf_esp
    movl 0x28(%esp), %edx         // %edx = utf_esp-4  
    movl %eax, (%edx)             // %eax = eip ----> esp-4  以至于ret可以直接读取其继续执行的地址
    
    popal              // after popal esp->utf_eip

    addl $4, %esp      // esp+4 -> utf_eflags
    popfl

    popl %esp

    ret                   // 这里十分巧妙, ret会读取esp指向的第一个内容, 也就是我们第一步写入的eip

PushRegs sizeof = 32 Byte。

struct PushRegs {
    /* registers as pushed by pusha */
    uint32_t reg_edi;
    uint32_t reg_esi;
    uint32_t reg_ebp;
    uint32_t reg_oesp;        /* Useless */
    uint32_t reg_ebx;
    uint32_t reg_edx;
    uint32_t reg_ecx;
    uint32_t reg_eax;
} __attribute__((packed));

We can't call 'ret' from the exception stack either, since if we did, %esp would have the wrong value. ret有什么作用?ret会同时修改 cs and sp 寄存器。

Exercise 11

Finish set_pgfault_handler() in lib/pgfault.c.

注意sys_env_set_pgfault_upcall注册时,不要把_pgfault_upcall写成了_pgfault_handler! 不要问我怎么知道的, 我查了好久的错!

if (_pgfault_handler == 0) {
        // First time through!
        // LAB 4: Your code here.

        sys_page_alloc(sys_getenvid(), (void *) (UXSTACKTOP - PGSIZE), PTE_SYSCALL);
        sys_env_set_pgfault_upcall(sys_getenvid(), _pgfault_upcall);
        // panic("set_pgfault_handler not implemented");
    }
    
    // Save handler pointer for assembly to call.
    _pgfault_handler = handler;

到目前为止,我们为用户环境提供了一个注册定制的 page fault handler 的 system call。刚开始接触会觉得有点绕,其在page_fault_handler中进行一次判断,check 是否当前进程设定了 默认的 handler ,再根据结果转向执行。而handler的调用与返回,需要通过一个汇编程序pfentry.S实现。 这个汇编程序才对真正的用户handler进行了调用,执行完 handler 之后依据 UTrapFrame 的内容返回到最初的用户环境执行。

Implementing Copy-on-Write Fork

现在我们可以开始完整地实现 copy-on-write fork() 了。

dumfork不同的是,fork 只复制了页映射关系,并且只在尝试对页进行写操作时才进行页内容的 copy。

fork控制流如下:

  1. parent 注册 handler
  2. parent call sys_exofork 创建子进程
  3. 对每个处于 UTOP之下的可写或COW页进行复制duppage它应该将 copy-on-write 页面映射到子进程的地址空间,然后重新映射 copy-on-write 页面到它自己的地址空间。 what???

[Note] 此处的顺序十分重要——父进程在子进程之后对 COW 页进行 mark 。why ?

但是,异常堆栈不会以这种方式重新映射。 相反,我们需要在子进程中为异常堆栈分配一个新页面。 由于页面错误处理程序将在异常堆栈上执行复制以及页面错误处理程序,因此异常堆栈无法进行写时复制:谁将复制它?

  1. 父进程为子进程设定用户页 fault entrypoint。
  2. mark state runnable

每次某个环境对从未写过的COW页进行写操作时,就会发生 page fault。 接下来就要交给 user page fault handler处理:

  1. 内核将页面错误传送到_pgfault_upcall,后者调用fork()的pgfault()处理程序。
  2. pgfault() checks that the fault is a write (check for FEC_WR in the error code) and that the PTE for the page is marked PTE_COW. If not, panic.
  3. pgfault() allocates a new page mapped at a temporary location and copies the contents of the faulting page into it. Then the fault handler maps the new page at the appropriate address with read/write permissions, in place of the old read-only mapping.

1.2.1. Exercise 12

Implement fork, duppage and pgfault in lib/fork.c.

首先看一下文档中提到的clever mapping trick

1.2.2. UVPT

页表的一个很好的概念模型是由一个具有2^20个条目的数组构成,其可以通过物理页号进行索引。 x86的二级分页方案通过将巨型页表分段为多个页表和一个页目录来打破这个简单模型。

The processor just follows pointers: pd = lcr3(); pt = (pd+4PDX); page = (pt+4PTX);

如果我们把一个指向页目录自身的指针放入页目录索引V中。如下图所示。 当我们尝试用PDX,PTX操作转换V虚拟地址时,最后又会回到页目录。即一个虚拟页指向了存储页目录的页。在 JOS 中,V 等于 0X3BD,UVPD的虚拟地址是(0x3BD << 22)|(0x3BD << 12)。

相当于我们在之前实验遇到的一条语句。 kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;

现在,如果我们尝试使用PDX = V但是任意PTX!= V来翻译虚拟地址,那么从CR3跟随的三个箭头将提前一级结束(而不是在最后一种情况下的两级),也就是说结束于页表。 因此,具有PDX = V的虚拟页面集合形成4MB区域,就处理器而言,其页面内容是页面表本身。 在JOS中,V是0x3BD,因此UVPT的虚拟地址是(0x3BD << 22)。fantastic!

30x3BD = 0011_1011_1101 << 22 ---> 1110_1111_0100_0000_0000_0000_0000_0000; PDX = 0X3BD= 957;1110_1111_0100_0000_0000_0000_0000_0000 = 0xEF400000,而 UVPT = 0xef400000 !

因此,由于巧妙地将"no-op" 指针插入到页目录中,我们将这些被用作页目录和页表的页(通常几乎不可见)映射到了虚拟地址空间。其实就是说我们能通过虚拟地址访问到页目录和页表。 真的是太强了!!! 这里刚开始有点混乱,重新复习了以下页表机制就清晰了。Page Translation,重点理解图5-2。

所以我们能通过uvptand uvpd直接访问页表和页目录,其初始化在lib/entry.S中实现。不过为什么我感觉这里描述的页目录与页表与我理解的概念相反?我理解的是正确的。但不知道为什么JOS要把UVPT指向的一个PGSIZE部分描述为(Page Table)页表而不是页目录。

extern volatile pte_t uvpt[];     // VA of "virtual page table"
extern volatile pde_t uvpd[];     // VA of current page directory
.globl uvpt
.set uvpt, UVPT
.globl uvpd
// 为什么不直接写 >>10 ?
.set uvpd, (UVPT+(UVPT>>12)*4)

当我们访问 uvpt[1]时,按照我的理解,应该要访问 (UVPT + 1 << 12)才能访问页表1。但按照C语言语法,其值应该等于 UVPT + 1 4。 why?
我之前理解错了。uvpt[1]确实就能访问到第一页(以0为起点), 过程如下:

  • 循环访问一次页目录(其PDX重新指向了页目录)
  • 访问第0个页目录项
  • 进以第0个页表,获得第1个页表项(第1025页才是存在页目录第一个页目录项指向的页表里)

最后给出代码。

  1. pgfault()
    // LAB 4: Your code here.
    if (! ( (err & FEC_WR) && (uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_COW)))
        panic("Neither the fault is a write nor COW page. \n");
    // LAB 4: Your code here.
    envid_t envid = sys_getenvid();
    // cprintf("pgfault: envid: %d\n", ENVX(envid));
    // 临时页暂存
    if ((r = sys_page_alloc(envid, (void *)PFTEMP, PTE_P| PTE_W|PTE_U)) < 0)
        panic("pgfault: page allocation fault:%e\n", r);
    addr = ROUNDDOWN(addr, PGSIZE);
    memcpy((void *) PFTEMP, (const void *) addr, PGSIZE);
    if ((r = sys_page_map(envid, (void *) PFTEMP, envid, addr , PTE_P|PTE_W|PTE_U)) < 0 )
        panic("pgfault: page map failed %e\n", r);
    
    if ((r = sys_page_unmap(envid, (void *) PFTEMP)) < 0)
        panic("pgfault: page unmap failed %e\n", r);
  1. duppage()
// LAB 4: Your code here.
    pte_t *pte;
    int ret;
    // 用户空间的地址较低
    uint32_t va = pn * PGSIZE;

    if (uvpt[pn] & PTE_W || uvpt[pn] & PTE_COW) {
        if ((ret = sys_page_map(thisenv->env_id, (void *) va, envid, (void *) va, PTE_P|PTE_U|PTE_COW)) < 0)
            return ret;
        if ((ret = sys_page_map(thisenv->env_id, (void *)va, envid, (void *)va, PTE_P|PTE_U|PTE_COW)) < 0)
            return ret;
    }
    else {
        if((ret = sys_page_map(thisenv->env_id, (void *) va, envid, (void * )va, PTE_P|PTE_U)) <0 ) 
            return ret;
    }

    return 0;
  1. fork(), 首先需要为父进程设定错误处理例程。这里调用set_pgfault_handler函数是因为当前并不知道父进程是否已经建立了异常栈,没有的话就会建立一个,而sys_env_set_pgfault_upcall则不会建立异常栈。
// LAB 4: Your code here.
    envid_t envid;
    int r;
    size_t i, j, pn;
    // Set up our page fault handler
    set_pgfault_handler(pgfault);
    
    envid = sys_exofork();
    
    if (envid < 0) {
        panic("sys_exofork failed: %e", envid);
    }
    
    if (envid == 0) {
        // child
        thisenv = &envs[ENVX(sys_getenvid())];
        return 0;
    }
    // here is parent !
    // Copy our address space and page fault handler setup to the child.
    
    for (pn = PGNUM(UTEXT); pn < PGNUM(USTACKTOP); pn++) {
        if ( (uvpd[pn >> 10] & PTE_P) && (uvpt[pn] & PTE_P)) {
            // 页表
            if ( (r = duppage(envid, pn)) < 0)
                return r;
            
        }
    }
    // alloc a page and map child exception stack
    if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_U | PTE_P | PTE_W)) < 0)
        return r;
    extern void _pgfault_upcall(void);
    if ((r = sys_env_set_pgfault_upcall(envid, _pgfault_upcall)) < 0)
        return r;

    // Start the child environment running
    if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
        panic("sys_env_set_status: %e", r);
    
    return envid;

错误

Exercise12完成后,打印出以下信息,发生了错误。调试发现时fork中复制page时,把PGNUM(USTACKTOP)写成了PGNUM(UXSTACKTOP), 因为多映射了一些页面,然后不知道为什么触发了页错误,最初的页错误发生在0xeebfdf38Empty Memory 处,因为在此处没有进行映射,访问即触发了页错误。 最终终止于异常栈溢出的 assert0xeebfffcc处于异常栈内)。

[00000000] new env 00001000
1000: I am ''
[00001000] new env 00001001
[00001000] user_mem_check assertion failure for va eebfffcc
[00001000] free env 00001000
1001: I am '0'
[00001001] new env 00002000
[00001001] user_mem_check assertion failure for va eebfffcc
[00001001] free env 00001001
2000: I am '00'
[00002000] new env 00002001
[00002000] user_mem_check assertion failure for va eebfffcc
[00002000] free env 00002000
2001: I am '000'
[00002001] exiting gracefully
[00002001] free env 00002001
[00000000] new env 00001000
1000: I am ''
[00001000] new env 00001001
I'M in page_fault_handler [00001000] user fault va eebfdf38 
pgfault: envid: 0
I'M in page_fault_handler [00001000] user fault va 00802008 
[00001000] user_mem_check assertion failure for va eebfffcc
[00001000] free env 00001000

...

1.3. 问题

  1. 当系统由用户态陷入到内核态时,是如何自动切换到内核栈的?

应该与Trapframe结构体部分有关系,最下面一部分说明了,当发生ring切换时,会压入esp and ss, 所以是硬件来完成的?是的,实际上xv6讲义40页描述了这个过程。

    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding4;
  1. 为什么子进程一定要在父进程之前对COW进行标记。

父进程先标记, 会出现以下错误(出现乱码)。PTE_COW = 0x800, PTE_AVAIL = 0xE00。分析了一波,还是不知道为什么。

[00000000] new env 00001000
1000: I am ''
[00001000] new env 00001001
[00001000] new env 00001002
[00001000] exiting gracefully
[00001000] free env 00001000
1001: I am '1'
[00001001] new env 00002000
[00001001] new env 00001003
[00001001] exiting gracefully
[00001001] free env 00001001
2000: I am '11'
[00002000] new env 00002001
[00002000] new env 00001004
[00002000] exiting gracefully
[00002000] free env 00002000
2001: I am '111'
...
[00003000] free env 00003000
3001: I am '11'
...
4000: I am '111'
[00004000] exiting gracefully
[00004000] free env 00004000
2002: I am '�߿�1'
...
1004: I am '�߿�1'
[00001004] exiting gracefully
[00001004] free env 00001004

声明:一丁点儿|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - MIT6.828 LAB4_PartB Copy-on-Write Fork


勿在浮沙筑高台,每天进步一丁点儿!