北航操作系统实验 Lab4 系统调用与fork

实验目的

  1. 掌握系统调用的概念及流程
  2. 实现进程间通讯机制
  3. 实现 fork 函数
  4. 掌握缺页中断的处理流程

本次实验会涉及到用户态了,user文件夹下的都是用户态的。lib下是内核态。

系统调用

系统调用流程

指导书上把整个流程说的很清楚了。

  1. 调用一个封装好的用户空间的库函数(如 writefwritef会继续调用syscall_putchar 函数)
  2. 调用用户空间的 syscall_* 函数
  3. 调用 msyscall,用于陷入内核态
  4. 陷入内核,内核取得信息,执行对应的内核空间的系统调用函数(sys_*
  5. 执行系统调用,并返回用户态,同时将返回值“传递”回用户态
  6. 从库函数返回,回到用户程序调用处

系统调用的核心文件

  • user/syscall_lib.c --> 用户态的系统调用接口
  • user/syscall_wrap.S --> 执行特权指令syscall的汇编
  • lib/syscall.S --> 内核的系统调用中断入口
  • lib/syscall_all.c -->具体的系统调用的实现

1589341544382.png

syscall_* 函数处于用户态,它们和内核中的系统调用函数(sys 开头的函数)是一一对应的。

handle_sys通过系统调用号来找到对应的sys函数,系统调用号在include\unistd.h有定义。

还有就是函数的参数存储问题了。msyscall函数一共有6个参数,前4 个参数会被 syscall 开头的函数分别存入 $a0-$a3 寄存器(寄存器传参的部分)同时栈帧底部保留 16 字节的空间(不要求存入参数的值),后 2 个参数只会被存入在前 4 的参数的预留空间之上的 8 字节空间内(没有寄存器传参)。

1589349571835.png

Exercise 4.1

填写 user/syscall_wrap.S 中的 msyscall 函数,使得用户部分的系统调用机制可以正常工作。

msyscall函数的作用就是调用syscall 陷入内核态,然后函数调用返回。这部分函数传参我们不是不需要管的,参数已经存储在a0-a3寄存器和栈中了。

LEAF(msyscall)
    // TODO: execute a `syscall` instruction and return from msyscall
    // move v0, a0                 # 把系统调用号放到v0寄存器中,这句话不加也行
    syscall                        # 调用syscall
    jr        ra                    # 返回
    nop
END(msyscall)

Exercise 4.2

Exercise 4.2 按照 lib/syscall.S 中的提示,完成 handle_sys 函数,使得内核部分的系统调用机制可以正常工作。

接下来就是内核的系统调用处理程序handle_sys 了。

这里首先调用的SAVE_ALL 函数会保存现场,还记得有个get_sp宏了么,这次sp寄存器的值被设置成了KERNEL_SP

然后进程上下文被保存在栈指针sp下一块大小为sizeof(struct Trapframe) 的空间中。 这个时候sp是内核栈指针, TF_REG29(sp)才是用户态栈指针 。一方面,SAVE_ALL把我们寄存器存储在sp栈内,而我们之前系统调用一共有6个参数,前四个存储在a0 - a3了, 后两个存储在用户栈内,且偏移量为16和20的内存空间里。因此,获得第5、6个参数需要去用户栈里取出参数。

NESTED(handle_sys,TF_SIZE, sp)
    SAVE_ALL                            /* 用于保存所有寄存器的汇编宏 */
    CLI                                 /* 用于屏蔽中断位的设置的汇编宏 */
    nop
    .set at                             /* 恢复$at 寄存器的使用 */
    // 当前sp为内核栈指针
    /* TODO: 将Trapframe 的 EPC 寄存器取出,计算一个合理的值存回Trapframe 中 */
    /* EPC目前是系统调用发生的地址,系统调用的返回也需要从EPC的地方开始执行,因此将EPC+4,指向下一条指令*/
    lw        t0, TF_EPC(sp)    
    addi    t0, 4
    sw      t0, TF_EPC(sp)
    
    /* TODO: 将系统调用号“复制”入寄存器$a0 */
    lw        a0,  TF_REG4(sp)              // 序号1 
    
    addiu   a0, a0, -__SYSCALL_BASE     /* a0 <- “相对”系统调用号 */
    sll     t0, a0, 2                   /* t0 <- 相对系统调用号 * 4 */
    la      t1, sys_call_table          /* t1 <- 系统调用函数的入口表基地址 */
    addu    t1, t1, t0                  /* t1 <- 特定系统调用函数入口表项地址 */
    lw      t2, 0(t1)                   /* t2 <- 特定系统调用函数入口函数地址 */
    
    lw      t0, TF_REG29(sp)            /* t0 <- 用户态的栈指针 */
    lw      t3, 16(t0)                  /* t3 <- msyscall 的第 5 个参数 */
    lw      t4, 20(t0)                  /* t4 <- msyscall 的第 6 个参数 */

    /* TODO: 在当前栈指针分配 6 个参数的存储空间,并将 6 个参数安置到期望的位置 */
    
    lw      a0, TF_REG4(sp)                // 序号2
    lw      a1, TF_REG5(sp)                // 3
    lw      a2, TF_REG6(sp)                // 4
    lw      a3, TF_REG7(sp)                // 5
    //先将栈指针减小,以分配空间
    addiu   sp, sp, -24    
    sw      a0, 0(sp)                    // 6
    sw      a1, 4(sp)                    // 7
    sw      a2, 8(sp)                    // 8    
    sw      a3, 12(sp)                    // 9
    sw      t3, 16(sp)
    sw      t4, 20(sp)

    jalr    t2                             /* 调用sys_*函数 */
    nop
    
    /* TODO: 恢复栈指针到分配前的状态 */
    addi    sp, sp, 24
    sw      v0, TF_REG2(sp)             /* 将$v0 中的 sys_*函数返回值存入Trapframe */trapframe

    j       ret_from_exception          /* 从异常中返回(恢复现场) */
    nop
END(handle_sys)

上面代码中我标序号1-9的地方加不加都能通过测试,我咨询了助教, 这个测试刚好没有涉及到对这四个寄存器的操作,所以你取不取都能通过测试 。 但根据mips规范,这个维护操作是必要的 。

Exercise 4.3

接下来就要完成一些系统调用函数了。

Exercise 4.3 实现 lib/syscall_all.c 中的 int sys_mem_alloc(int sysno,u_int envid, u_int va, u_int perm) 函数

用户程序(用户态进程)可以通过这个系统调用给该程序所允许的虚拟内存空间内存显式地分配实际的物理内存。根据提示来写。

int sys_mem_alloc(int sysno, u_int envid, u_int va, u_int perm)
{
    // Your code here.
    struct Env *env;
    struct Page *ppage;
    int ret;
    ret = 0;
    if(va >= UTOP) return - E_INVAL;     // 判断地址的合法性,不能超过UTOP
    if((perm & PTE_COW) || ((perm & PTE_V) == 0) ) return - E_INVAL;//检测权限位
    /* checkperm参数应该需要为1,进程只可以修改自己的、或者是子进程的地址*/
    if( (ret = envid2env(envid, &env, 1)) < 0 ) return ret;    // 得到对应的进程
    if( (ret = page_alloc(&ppage) ) < 0 ) return ret;        //    申请一个物理页
    /* 将物理页插入页目录,与虚拟地址va建立映射!page_insert已经完成ppage->pp_ref++ */
    if( (ret = page_insert(env->env_pgdir, ppage, va, perm) ) < 0) return ret;
    
    return 0;
}

Exercise 4.4

Exercise 4.4 实现 lib/syscall_all.c 中的 int sys_mem_map(int sysno,u_int srcid, u_int srcva, u_int dstid, u_dstva, u_int perm) 函数

将源进程地址空间中的相应内存映射到目标进程的相应地址空间的相应虚拟内存中去。换句话说,此时两者共享着一页物理内存。两个地址对应着同一个物理页!

int sys_mem_map(int sysno, u_int srcid, u_int srcva, u_int dstid, u_int dstva,
                u_int perm)
{
    int ret;
    u_int round_srcva, round_dstva;
    struct Env *srcenv;
    struct Env *dstenv;
    struct Page *ppage;
    Pte *ppte;

    ppage = NULL;
    ret = 0;
    /* 内存要对齐 */
    round_srcva = ROUNDDOWN(srcva, BY2PG);
    round_dstva = ROUNDDOWN(dstva, BY2PG);

    //your code here
    /* 不需要判PTE_COW */
    if((perm & PTE_V) == 0 ) return - E_INVAL;
    if(round_srcva >= UTOP || round_dstva >= UTOP) return - 1;
    if((ret = envid2env(srcid, &srcenv, 1)) < 0) return ret;
    if((ret = envid2env(dstid, &dstenv, 1)) < 0) return ret;
    /* 先获得源地址对应的物理页ppage */
    if((ppage = page_lookup(srcenv->env_pgdir, round_srcva, &ppte)) == NULL ) return -1;
    //if((perm&PTE_R) && !((*ppte)&PTE_R) ) return - E_INVAL; // 不确定是否要写
    /* 再将目的地址与该物理页建立映射,这样两个地址就指向了同一个物理页 */
    if((ret = page_insert(dstenv->env_pgdir, ppage, round_dstva, perm) ) < 0) return ret;
    return 0;
}

Exercise 4.5

Exercise 4.5 实现 lib/syscall_all.c 中的 int sys_mem_unmap(int sysno,u_int en-vid, u_int va) 函数

这个系统调用的功能是解除某个进程地址空间虚拟内存和物理内存之间的映射关系。可能用到的函数:page_remove。

int sys_mem_unmap(int sysno, u_int envid, u_int va)
{
    // Your code here.
    int ret;
    struct Env *env;
    if(va >= UTOP) return -1;
    if((ret = envid2env(envid, &env, 0) ) < 0 ) return ret;
    /* 将该地址对应的物理页移除,即取消了映射*/
    page_remove(env->env_pgdir, va);
    return 0;
    //panic("sys_mem_unmap not implemented");
}

Exercise 4.6

Exercise 4.6 实现 lib/syscall_all.c 中的 void sys_yield(void) 函数

这个函数的功能主要就在于实现当前用户进程对 CPU 的放弃,即取消当前进程的执行,然后切换到另一个进程执行。

因此该函数会调用 sys_yield 函数来进行进程的调度,进程的切换会保存上下文,在env_run 函数中,我们认为进程的上下文存储在TIME_STACK 区,但是前面系统调用处理函数handle_sys 将进程的上下文存储在KERNEL_SP 区了,因此我们还需要一个复制操作,把KERNEL_SP区的内容复制到TIME_STACK区。

void sys_yield(void)
{
    // 把进程上下文复制到TIME_STACK
    bcopy((void *)(KERNEL_SP - sizeof(struct Trapframe) ), 
          (void *)(TIMESTACK - sizeof(struct Trapframe) ), sizeof(struct Trapframe)) ;
    sched_yield();
}

Exercise 4.7

这一部分就是进程间的通信了。

• IPC 的目的是使两个进程之间可以通讯
• IPC 需要通过系统调用来实现

各个进程的地址空间是相互独立的。要想传递数据,我们就需要想办法把一个地址空间中的东西传给另一个地址空间。

所有的进程都共享了内核所在的 2G空间。想要在不同空间之间交换数据,我们就需要借助于内核的空间来实现。发送和接受消息和进程有关,消息都是由一个进程发送给另一个进程的。内核里什么地方和进程最相关呢?——进程控制块!

struct Env {
    // Lab 4 IPC
    u_int env_ipc_value;            // 发给当前进程的数据
    u_int env_ipc_from;             // 发送者的envid
    u_int env_ipc_recving;          // 自身接收状态, 1表示可接收。
    u_int env_ipc_dstva;            // 接收到的页需要被映射到哪个虚地址上
    u_int env_ipc_perm;                // 页面映射权限
};

Exercise 4.7 实现 lib/syscall_all.c 中的 void sys_ipc_recv(int sysno,u_int dstva)函数和 int sys_ipc_can_send(int sysno,u_int envid, u_int value, u_int srcva, u_int perm) 函数。

首先是void sys_ipc_recv(int sysno,u_int dstva) 函数。该函数表明该进程(当前进程)准备接受其它进程的消息了。首先要将env_ipc_recving 设置为1, 之后修改 env_ipc_dstva, 然后把当前进程进程状态设为ENV_NOT_RUNNABLE, 然后当前进程放弃CPU(调用相关函数重新进行调度),即调用sys_yield函数,注意不是sched_yield 函数!!。

void sys_ipc_recv(int sysno, u_int dstva)
{
    //printf("sys_ipc_recv called\n");
    if(dstva >= UTOP) {
        printf("dstva: %x 越界了\n", dstva); 
        return ;
    }
    curenv -> env_ipc_recving = 1;
    curenv -> env_ipc_dstva = dstva;
    curenv -> env_status = ENV_NOT_RUNNABLE;
    sys_yield(); // 注意,这里是sys_yield
}

接着是int sys_ipc_can_send(int sysno,u_int envid, u_int value, u_int srcva, u_int perm) 函数,该函数用于当前进程把数据value 发送给目标进程envid, 目标进程的接收状态env_ipc_recving 必须是1。发送成功,之后清除接收进程的接收状态,修改进程控制块中相应域的值,使其可运行 (ENV_RUNNABLE),函数返回 0。值得一提的是,由于在我们的用户程序中,会大量使用 srcva 为 0 的调用来表示不需要传递物理页面,只传值。

int sys_ipc_can_send(int sysno, u_int envid, u_int value, u_int srcva,
                     u_int perm)
{
    //printf("sys_ipc_can_send called \t target %d\n", envid);
    int r;
    struct Env *e;
    struct Page *p; 
    /* 目标进程e */
    if(srcva >= UTOP ) return - E_IPC_NOT_RECV;
    if((r = envid2env(envid, &e, 0)) < 0) return - E_IPC_NOT_RECV;
    if( e -> env_ipc_recving == 0) return - E_IPC_NOT_RECV;
    e -> env_ipc_recving = 0;    //清除接收进程的接收状态
    e -> env_ipc_perm = perm;     //好像没要求?
    /* env_ipc_from设置为发送者的进程id */
    e -> env_ipc_from = curenv -> env_id;
    e -> env_ipc_value = value; 
    e -> env_status = ENV_RUNNABLE;
    /* 设置为RUNNABLE之后要插不插入调度列表取决于你的sched_yield函数写法,lab3曾提到过*/
    //LIST_INSERT_HEAD(env_sched_list, e, env_sched_link);
    //printf("sys_ipc_can_send success \t target %d\n", envid);
    return 0;
}

具体的通信可以去看 user/pingpong.cuser/ipc.c 。可以看到,一个进程调用ipc_recv 函数后,表示自己要准备接收数据了,这个进程如果没有接收到数据,那它永远不会执行,可以看到,只有其他进程调用了ipc_send 函数,并且把数据发送给了这个进程,这个进程的状态被设置成了ENV_RUNNABLE 后,这个进程才有执行的机会。

Fork

初窥Fork

fork就是创建一个子进程。在某个进程中调用 fork() 之后,将会以此为分叉分成两个进程运行。新的进程在开始运行时有着和旧进程绝大部分相同的信息,而且在新的进程中 fork 依旧有一个返回值,只是该返回值为 0。在旧进程,也就是所谓的父进程中,fork 的返回值是子进程的 env_id,是大于 0 的。在父子进程中有不同的返回值的特性,可以让我们在使用 fork 后很好地区分父子进程,从而安排不同的工作。我们可以得到以下几点信息。

  • 在 fork 之前的代码段只有父进程会执行。
  • 在 fork 之后的代码段父子进程都会执行。
  • fork 在不同的进程中返回值不一样,在父进程中返回值不为 0,在子进程中返回值为 0。
  • 父进程和子进程虽然很多信息相同,但他们的 env_id 是不同的。

子进程实际上就是按父进程的绝大多数信息和状态作为模板而雕琢出来的。需要明确:

fork 函数有两个返回值,fork 只在父进程中被调用了一次,生成了一个子进程,然后两个进程中各产生一个返回值。

fork过程流程图

fork.png

写时复制机制

在fork时,父进程会为子进程分配独立的地址空间。但是分配独立的虚拟空间并不意味着一定会分配额外的物理内存:父子进程用的是相同的物理空间。子进程的代码段、数据段、堆栈都是指向父进程的物理空间,也就是说,虽然两者的虚拟空间是不同的,但是他们所对应的物理空间是同一个。 为了实现共享的物理内存不会被任一进程修改,这里我们引入一个新的概念——写时复制(Copy On Write,简称COW)。 通俗来讲就是当父子进程中有修改内存(一般是数据段)的行为发生时,内核捕获这种缺页中断后,再为发生内存修改的进程相应的地址分配物理页面,而一般来说子进程的代码段继续共享父进程的物理空间(两者的代码完全相同)。分配物理页面后,进程就能自由的写数据了。所以, 对于所有的可被写入的内存页面,都需要通过设置页表项标识位PTE_COW的方式被保护起来。 无论父进程还是子进程何时试图写一个被保护的物理页,就会产生一个异常(一般指缺页中断Page Fault),然后系统会进行处理。

返回值

通过前面有个fork_test.c 程序,我们可以看到,调用fork函数后,父子进程会产生不同的返回值。这是系统调用syscall_env_alloc函数的功劳 。该函数用于创建一个子进程。该函数只会被父进程执行一次,但产生了两个返回值。 通过syscall_env_alloc的两个返回值区分开父子进程,好安排他们在返回之后执行不同任务。

envid = syscall_env_alloc(); 
if (envid == 0) {
    // 这里是子进程
    ...
}else{
    // 这里是父进程
    ...
}

### 为什么会有两个返回值

syscall_env_alloc 函数创建了一个子进程,子进程拥有着和旧进程绝大部分相同的信息,同时子进程的pc寄存器被设置为了epc寄存器的值。父进程执行完系统调用后返回了继续执行,同时函数有一个返回值。子进程也会被调度,它被调度的时候势必会恢复现场,而子进程的信息和父进程几乎一样,因此恢复完现场后,子进程也会从syscall_env_alloc返回,注意只是从这个地方返回,然后执行下一条指令,不会重新运行syscall_env_alloc函数。我们需要在syscall_env_alloc函数中通过设置相关寄存器来达到设置子进程返回值(即是0)的目的。

我们可以认为它们都应该经历了同样的“恢复运行现场”的过程,只不过对于父进程是从系统调用中返回的恢复现场,而对于子进程则是在进程调度时进行的现场恢复。在现场恢复后,进程会从同样的地方返回到 fork 函数中。而它们携带的函数的返回值是不同的,这也就能够在 fork函数中区分两者。

Exercise 4.8

Exercise 4.8 请根据上述步骤以及代码中的注释提示,填写 lib/syscall_all.c 中的sys_env_alloc 函数。

需要用一些当前进程的信息作为模版来填充子进程:

  • 运行现场 要复制一份当前进程的运行现场 Trapframe 到子进程的进程控制块中。
  • 程序计数器 子进程的程序计数器应该被设置为 syscall_env_alloc 返回后的地址,也就是它陷入异常地址的下一行指令的地址,这个值已经存在于 Trapframe 中。
  • 返回值有关 这个系统调用本身是需要一个返回值的(这个返回过程只会影响到父进程),对于子进程则需要对它的运行现场 Trapframe 进行一个修改。
  • 进程状态 我们当然不能让子进程在父进程 syscall_env_alloc 返回后就直接进入调度,因为这时候它还没有做好充分的准备,所以我们需要设定不能让它被加入调度队列。
  • 其他信息 如env_pri
int sys_env_alloc(void)
{
    int r;
    struct Env *e; // e就是创建的子进程
    if((r = env_alloc(&e, curenv -> env_id)) < 0 ) {
        return r;
    }
    /* 复制运行现场*/
    bcopy((void *)(KERNEL_SP - sizeof(struct Trapframe)), &(e -> env_tf), sizeof(struct Trapframe));
    e -> env_tf.pc = e -> env_tf.cp0_epc; //设置程序计数器
    e -> env_status = ENV_NOT_RUNNABLE; // 设置状态
    e -> env_pri = curenv -> env_pri;    
    // 这个很关键!!!2号寄存器是v0,也就是子进程的返回值,设为0
    e -> env_tf.regs[2] = 0;

    return e->env_id;//返回子进程的envid
    //    panic("sys_env_alloc not implemented");
}

Exercise 4.9

Exercise 4.9 按照上述提示,填写 user/fork.c 中的 fork 函数中关于 sys_env_alloc的部分和“子进程”执行的部分

怎么确认当前进程是子进程?syscall_env_alloc返回值是0!

struct Env *env 指针指向自身的进程控制块(也就是当前进程?) 子进程相关变量设置:

  1. 在子进程第一次被调度的时候(当然这时还是在 fork 函数中)它需要将用户的 env指针指向自身的进程控制块。
  2. 通过一个系统调用来取得自己的 envid,因为对于子进程而言 syscall_env_alloc返回的是一个 0 值。
  3. 根据获得的 envid,获取对应的进程控制块,将 env 指针设置为对应的进程控制块。做完上面步骤,当子进程醒来时,就可以从 fork 函数中正常返回,开始自己的旅途
    u_int newenvid;
    extern struct Env *envs;
    extern struct Env *env;
    u_int i;
    u_int parent_id = syscall_getenvid();    //先保存父进程的id
    
    /* 父进程为自身分配了异常处理栈 */
    set_pgfault_handler(pgfault);
    //alloc a new alloc
    newenvid = syscall_env_alloc();
    /* 只会被父进程执行的部分结束,接下来的代码父子进程会共同执行*/
    u_int envid;
    if(newenvid == 0) {
        //writef("******Start. This is Son's env**********\n");
        /*这个只有子进程会进入这个if语句来执行*/
        env = &envs[ENVX(syscall_getenvid())];/* 用户态不能使用envid2env*/
        env -> env_parent_id = parent_id; // 刚刚设置的parent_id
        return 0;    //子进程返回0
    }

这样fork返回后,子进程就能正常的执行了。

Exercise 4.10

上面Exercise 4.9只是我们把子进程的代码补全了。实际上,只有父进程设置完相关内容,并将把子进程的状态设为ENV_RUNNABLE, 子进程才能执行上面Exercise 4.9的代码。因此,我们继续来完成父亲需要设置的内容。父亲在儿子醒来之前则需要做更多的准备,而这些准备中最重要的一步是遍历进程的大部分用户空间页,对于所有可以写入的页面的页表项,在父进程和子进程都加以 PTE_COW 标志位保护起来。这里需要实现 duppage 函数来完成这个过程。

前面也提到了,父子进程对应着相同的物理空间。子进程的页目录和页表除了内核地址区域以外,显然都还未设置。这就需要父进程来为其完成这个工作,即完成虚拟地址到物理页的映射,并设置相关权限。由于父子进程的物理空间相同,子进程的虚拟地址和父进程虚拟地址肯定对应同一个物理页上,因此需要调用前面写过的 syscall_mem_map 函数来完成映射。显然,父进程的页目录和页表是子进程的模板,子进程的页目录和页表根据父进程的页目录和页表来设置。duppage函数的参数就是一个虚拟页和子进程envid,用于把该页以某个权限映射给子进程。父进程在duppage函数为子进程页表设置标识时,要根据自身的页表项中的权限,对不同权限的页有着不同的处理方式。

  • 只读页面:按照相同权限(只读)映射给子进程即可,即子进程的权限与父进程保持相同。
  • 共享页面:即具有PTE_LIBRARY标记的页面 ,这个也保持相同权限,同上。
  • 写时复制页面:即具有PTE_COW标记的页面,这类页面是上一次的fork的duppage的结果。对于这种,子进程肯定同样需要保持写时复制。因此也保持相同权限。
  • 可写页面:即具有PTE_R标记的页面。可写的页面,父子进程都需要设置写时复制标记。即需要给父进程和子进程的页表项都加上PTE_COW标记。

vpt和vpd

代码提示中,这部分需要使用到 vpd 和 vpt 这两个“指针的指针”, 这俩是什么呢?还记得lab3env_setup_vm函数中的e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_V | PTE_R; 这个映射么?这和vpt有什么关系呢?

先来找一下这俩的定义。

extern volatile Pte *vpt[];
extern volatile Pde *vpd[];

再来找一下这俩的值。(entry.S)

    .globl vpt
vpt:
    .word UVPT
    
    .globl vpd
vpd:
    .word (UVPT+(UVPT>>12)*4)

可以看到vpt上存放的是UVPT (0x7fc00000) , vpd上存放的是(UVPT+(UVPT>>12)*4)

所以vpt = UVPT = 0x7fc00000, vpd = 0x7fdff000 。

前面lab3我们知道了UVPT进程页表的起始地址(我认为其实只是建立了一个映射,并没有实际存放), 该段地址以只读权限开放给用户态的程序。而 0x7fdff000 这个地址是由于自映射的原因,这个地址是页目录的虚存地址。所以vpt和vpd可以当作页表页目录来使用!(*vpt)是个指针,我们可以通过类似于数组访问的形式( * vpt)[x] 就是第x个页表项。 具体是怎么得到页目录项和页表项的呢?结合e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_V | PTE_R来看。

/* va地址可以分解为三部分  VPN(va) = (va >> 12)*/
+--------10------+-------10-------+---------12----------+
| Page Directory |   Page Table   | Offset within Page  |
|      Index     |      Index     |                     |
+----------------+----------------+---------------------+
 \--- PDX(va) --/ \--- PTX(va) --/ \---- PGOFF(va) ----/
 \----------- VPN(va) -----------/

地址va对应着第VPN(va) 个虚拟页面。

vpt 访问页表项

我们知道,我们可以通过(*vpt)[VPN(va)] 来获得地址va对应的页表项。

(*vpt)[VPN(va)] --> *((*vpt) + (va >> 12) ) = *(UVPT + (va >> 12)*4)

为什么后面突然乘4了? 因为(*vpt) 是Pte类型的指针,每项占4个字节。数组访问增加一项,相当于地址增加了4个字节,因此要乘4!

$UVPT = 0x7fc00000 = 0111\, 1111\, 1100\, 00000000000000000000$。PDX(UVPT) = $0111\, 1111\, 11$

举个例子,先随便假设$ va = 0x3fff1234 = 0011\, 1111 \,1111\,1111\,0001\,0010\,0011\,0100$ , 我们想获得第VPN(va) 个页表项,即第$0011\, 1111 \,1111\,1111\,0001\,$ 个页表项。

(*vpt)[VPN(va)] --> *(UVPT + (va >> 12)*4) --> *(0111 1111 1100 1111 1111 1100 0100)

当访问(*vpt)[VPN(va)] 时,其实就是在访问地址 $addr = 0111 1111 1100 1111 1111 1100 0100$。假设当前进程页目录为pgdir。地址转换的过程在lab2就已经很熟悉了。

  1. 取出地址的PDX(addr),然后通过pgdir[PDX(addr)]访问地址addr的页目录项。可以发现PDX(addr) = PDX(UVPT) = $0111\, 1111\, 11$,因此页目录项pgdir[PDX(addr)] = pgdir[PDX(UVPT)]上的存放的物理地址就是env_cr3,这个地址仍然是页目录所在地址!因此通过页目录索引,我们得到二级页表是页目录!
  2. 取出地址的PTX(addr) = 00 1111 1111 , 由于在第一步得到的二级页表仍然是页目录,所以这次访问的是pgdir[PTX(addr)],即第PTX(addr)个页目录项,也即是第PTX(addr)个页表!这个页目录项上存放着某个页表的物理页框号,因此通过这次访问,我们得到了一个页表。和正常的访存不一样 ,正常访存第二次我们就得到了具体的某个物理页了,然后加上页内偏移就是我们想要的实际物理地址。
  3. 取出地址的PGOFF(addr) = 1111 1100 0100。由于我们第二次得到的是一张页表,并且第三次访存后就结束了,因此我们会返回该页表的第PGOFF(addr) >> 2项。为什么要右移2(即除4)?因为页表的每一项占了4B!页表每增加一项,实际地址增加了4。因此这里地址转化为具体的第几项,也要除4。

所以最终我们得到了什么?第PTX(addr)页表中的第PGOFF(addr)>>2 个页表项! 一个页表有1024个页表项。也即是我们得到了第(PTX(addr) << 10) + (PGOFF(addr)>>2)个页表项。 和我们原来的目标第VPN(va)个页表项一样吗?显然是一样的。VPN(va)一共有20位,高10位就是PTX(addr),低10位就是PGOFF(addr) >> 2。

不失一般性,addr这个地址的前10位永远都是UVPT的前10位,即$0111\, 1111\, 11$ , addr的后22位中的前20位就是(va >> 12), 最后两位是0。来看一下地址的32位分别是什么。

/* va */
+--------10------+-------10-------+---------12----------+
 \--- PDX(va) --/ \--- PTX(va) --/ \---- PGOFF(va) ----/
/* addr */
+-------10-------+-------10-------+-------10-------+---2---+
\--UVPT[31:22]--/ \--- PDX(va) --/ \--- PTX(va)---/ \--00--/

因此在进行地址转换的时候第一次访问得到的仍然是页目录。第二次访问得到的是页表,第三次得到页表项并返回。因此(*vpt)[x] 就是第x个页表项。

vpd 访问页目录项

这个和上面的过程就比较类似了,就不细展开了。

(*vpd)[va >> 22] --> *((*vpd) + (va >> 22) ) = *(UVPT+(UVPT>>12)*4 + (va >> 22)*4)
/* addr */
+-------10-------+-------10--------+-------10-------+---2---+
\--UVPT[31:22]--/ \--UVPT[31:22]--/ \--- PDX(va)---/ \--00--/

第一次取出pgdir[PDX(addr)]得到页目录,第二次pgdir[PTX(addr)] 仍然是页目录。第三次通过PGOFF(addr) >> 2 得到具体的页目录项,然后返回该页目录项。 因此(*vpd)[x] 就是第x个页目录项。

与通常寻址方式类比

通常寻址
  cr3           PDX            PTX            PGOFF  
------->页目录---------二级页表-------->物理页面-------->值
(*vpt)[x]
  cr3          PDX           PTX            PGOFF  
------->页目录---------页目录-------->二级页表-------->页表项
(*vpd)[x]
  cr3           PDX           PTX          PGOFF  
------->页目录---------页目录-------->页表录-------->页目录项

duppage函数

Exercise 4.10 结合代码注释以及上述提示,填写 user/fork.c 中的 duppage 函数

先来看一下fork函数中需要完成的, 也就是父进程需要完成的。

/*这个newenvid 是子进程的envid*/
/*1. 遍历父进程地址空间,进行 duppage*/
for( i = 0; i < VPN(USTACKTOP) ; ++ i ){
    if( ((*vpd)[i >> 10]) && ((*vpt)[i]) ) {
        duppage(newenvid, i);
    }
}

可以看到地址的上限是USTACKTOP,是因为这个地址后面一个是Invalid memory 、 一个是 user exception stack 。后面一个是缺页中断时的异常处理栈,每个进程的异常处理栈属于自己的,不能映射给子进程。

现在可以来完成这个函数了。 调用syscall_mem_map函数参数srcid = 0 代表当前进程。

static void
duppage(u_int envid, u_int pn)
{
    /* envid*/
    u_int addr;
    u_int perm;
    addr = pn * BY2PG;
    perm = (*vpt)[pn] & 0xfff;// 取出权限位
    if(!(perm & PTE_R) || !(perm & PTE_V)) {
        /* 只读页面或者无效页面,权限不变 */
        syscall_mem_map(0, addr, envid, addr, perm);
    }else if(perm&PTE_LIBRARY){
        /* 共享页面,保持共享 */
        syscall_mem_map(0, addr, envid, addr, perm);
    }else if(perm&PTE_COW){
        /* 非共享页面,写时复制页面 */
        syscall_mem_map(0, addr, envid, addr, perm);
    }else{
        /*可写页面,父进程和子进程都要设置写时复制*/
        perm |= PTE_COW;
        syscall_mem_map(0, addr, envid, addr, perm); // 一定要先映射子进程
        syscall_mem_map(0, addr, 0, addr, perm); // 父进程
    }
    //writef("duppage success!\n");
}

注意一定要先映射给子进程。 如果先给父进程加PTE_COW,父进程在执行的过程中可能会发生缺页中断,然后父进程进行写时复制,而新页没有被加上PTE_COW。此时再map子进程,子进程该页加上PTE_COW位而父进程没有。在随后程序运行中,若父进程对该页进行修改,由于父进程没有PTE_COW,因此其可以随意修改该页的数据,子进程读取该页上的数据是已经被父进程修改了,因此将会出现错误。

缺页中断

常规缺页中断

内核在捕获到一个常规的缺页中断(Page Fault)时(在 MIPS 中这个情况特指TLB 缺失),会进入到一个在 trap_init 中“注册”的 handle_tlb 的内核处理函数中,这一汇编函数的实现在 lib/genex.S 中,化名为一个叫 do_refill 的函数,由该函数和pageout函数共同来处理。

写时复制特性的缺页中断

前文中我们提到了写时复制特性,而写时复制特性也是依赖于缺页中断的。我们在trap_init 中注册了另外一个处理函数——handle_mod,这一函数会跳转到 lib/traps.c的 page_fault_handler 函数中,这个函数正是处理写时复制特性的缺页中断的内核处理函数。然而这个函数并没有做任何的页面复制操作,真正的处理过程是用户进程自身去完成的。如果需要用户进程去完成页面复制等处理过程,是不能直接使用原先的堆栈的(因为发生缺页错误的也可能是正常堆栈的页面),所以这个时候用户进程就需要一个另外的堆栈来执行处理程序,我们把这个堆栈称作异常处理栈,用于保存进程的上下文。它的栈顶对应的是宏 UXSTACKTOP。异常处理栈需要父进程为自身以及子进程分配映射物理页面。此外内核还需要知晓进程自身的处理函数所在的地址,这个地址存在于进程控制块的 env_pgfault_handler域中,这个地址也需要事先由父进程通过系统调用设置。

因此,概括一下上述内容,在我们的 MOS 操作系统中,完成写时复制的缺页中断处理大致流程可以概括为:

  1. 用户进程触发缺页中断,识别为写时复制处理,跳转到 handle_mod 函数,再跳转到 page_fault_handler 函数。
  2. page_fault_handler 函数负责将当前现场保存在异常处理栈中,并设置 epc 寄存器的值为env_pgfault_handler,退出中断后程序会从epc寄存器的地方继续执行,因而能够跳转到 env_pgfault_handler 域定义的异常处理函数。
  3. 退出中断,跳转到异常处理函数中,这个函数首先跳转到用户态的 pgfault 函数(定义在fork.c 中)进行缺页处理,这个函数才是真正的处理函数,然后恢复事先保存好的现场,并恢复 sp 寄存器的值,使得子进程恢复执行。

关于env_pgfault_handler 域定义的异常处理函数,下面会说。

Exercise 4.11

Exercise 4.11 根据上述提示以及代码注释,完成 lib/traps.c 中的 page_fault_handler函数,设置好异常处理栈以及 epc 寄存器的值。

void page_fault_handler(struct Trapframe *tf)
{
    struct Trapframe PgTrapFrame;
    extern struct Env *curenv;
    /*先将上下文临时保存起来,不保存起来,用户栈指针就丢了 */
    bcopy(tf, &PgTrapFrame, sizeof(struct Trapframe));
    /*设置异常处理栈*/
    if (tf->regs[29] >= (curenv->env_xstacktop - BY2PG) &&
        tf->regs[29] <= (curenv->env_xstacktop - 1)) {
            tf->regs[29] = tf->regs[29] - sizeof(struct  Trapframe);
            bcopy(&PgTrapFrame, (void *)tf->regs[29], sizeof(struct Trapframe));
        } else {
            tf->regs[29] = curenv->env_xstacktop - sizeof(struct  Trapframe);
            bcopy(&PgTrapFrame,(void *)curenv->env_xstacktop - sizeof(struct  Trapframe),sizeof(struct Trapframe));
        }
    //前面也说了,epc寄存器设置为env_pgfault_handler
    tf -> cp0_epc = curenv -> env_pgfault_handler ; 
    return;
}

刚进入该函数的时候,tf结构体是调用handle_mod前进程的上下文。tf -> regs[29]是用户栈指针,然后我们把他设置成了异常处理栈指针,同时把上下文拷贝到异常处理栈内。因为该函数也是由handle_mod来调用的,该函数返回到handle_mod的时候,需要有一个恢复现场的操作,可以看到,恢复完现场,栈指针就指向了异常处理栈,即刚刚设置后的tf -> regs[29],这是因为恢复完上下文,函数直接跳转到epc寄存器所在的地方,即 env_pgfault_handler 域定义的异常处理函数,去进行写时复制的缺页中断处理。等到写时复制的中断处理完成了,同样会恢复现场(上下文存储在异常处理栈内),恢复完上现场,进程就能正常执行了。

Exercise 4.12

Exercise 4.12 完成 lib/syscall_all.c 中的 sys_set_pgfault_handler 函数

让我们回到 fork 函数,在提示使用 syscall_env_alloc 之前,有另一个提示——使用pgfault.c/set_pgfault_handler 函数来“安装”处理函数。也就是我们上文总提到的 env_pgfault_handler域定义的异常处理函数。

/*这个函数会由父进程调用(见前面fork流程图),并且刚进去fork函数就要执行*/
void set_pgfault_handler(void (*fn)(u_int va))
{
    if (__pgfault_handler == 0) {
        /*0代表当前进程!为自身设置分配异常处理栈UXSTACKTOP*/
        /* 同时用系统调用来设置中断处理函数为__asm_pgfault_handler */
        if (syscall_mem_alloc(0, UXSTACKTOP - BY2PG, PTE_V | PTE_R) < 0 ||
            syscall_set_pgfault_handler(0, __asm_pgfault_handler, UXSTACKTOP) < 0) {
            writef("cannot set pgfault handler\n");
            return;
        }
        //        panic("set_pgfault_handler not implemented");
    }
    // Save handler pointer for assembly to call.
    __pgfault_handler = fn; //fn就是pgfault
}

上面的 set_pgfault_handler 函数中,进程为自身分配映射了异常处理栈,同时该函数调用了syscall_set_pgfault_handler 函数用于告知内核自身的处理程序是__asm_pgfault_handler(在 entry.S 定义),即将进程控制块的 env_pgfault_handler 域设为它。这样进程在退出page_fault_handler函数后会跳转到__asm_pgfault_handle 来完成中断的处理。函数的最后,将在entry.S 定义的字 __pgfault_handler 赋值为 fn, fn是pgfault函数。

int sys_set_pgfault_handler(int sysno, u_int envid, u_int func, u_int xstacktop)
{
    // Your code here.
    struct Env *env;
    int ret;
    if((ret = envid2env(envid, &env, 1)) < 0) return ret;
    env -> env_pgfault_handler = func ; //设置异常函数入口,即__asm_pgfault_handle
    env -> env_xstacktop = xstacktop; //设置异常处理栈顶
    return 0;
    //panic("sys_set_pgfault_handler not implemented");
}

Exercise 4.13

我们现在知道了缺页中断会返回到 entry.S 中的 __asm_pgfault_handler 函数,来看看这个函数。

__asm_pgfault_handler:
//1: j 1b
nop
    lw    a0, TF_BADVADDR(sp)    // 发生缺页中断的虚拟地址
    lw    t1, __pgfault_handler    
    jalr    t1    //跳转到__pgfault_handler函数,即pgfault函数。函数参数是a0
nop
    lw    v1,TF_LO(sp)                                       
    mtlo    v1                               
    lw    v0,TF_HI(sp)                                         
    lw    v1,TF_EPC(sp)                    
    mthi    v0                               
    mtc0    v1,CP0_EPC                                             
    lw    $31,TF_REG31(sp) 
    ... 恢复现场
    lw    k0,TF_EPC(sp)     //atomic operation needed 
    jr    k0            //
    lw    sp,TF_REG29(sp)  // 利用延时槽  

前面就提到过,handle_mod返回后,会调转到__asm_pgfault_handler 函数进行缺页中断的处理,此时的栈指针指向了异常处理栈。而且指向一个由内核复制好的 Trapframe 结构体的底部。通过宏 TF_BADVADDR 用 lw 指令取得了 Trapframe 中的 cp0_badvaddr 字段的值,这个值也正是发生缺页中断的虚拟地址。将这个地址作为第一个参数去调用了 __pgfault_handler 这个字内存储的函数,不难看出这个函数是真正进行处理的函数。

就要来实现真正进行处理的函数:user/fork.c 中的 pgfault 函数了, pgfault 需要完成这些任务:

  1. 判断页是否为写时复制的页面,是则进行下一步,否则报错
  2. 分配一个新的内存页到临时位置,将要复制的内容拷贝到刚刚分配的页中(临时页面位置可以自定义,观察 mmu.h 的地址分配查看哪个地址没有被用到,思考这个临时位置可以定在哪)
  3. 将临时位置上的内容映射到发生缺页中断的虚拟地址上,注意设定好对应的页面权限,然后解除临时位置对内存的映射

第2步,我们需要借助一个临时页面,在mmu.h中可以看到USTACKTOP开始的一段内存Invalid memory 还没有使用过,因此可以借助这块内存。

static void pgfault(u_int va)
{
    u_int *tmp;
    va = ROUNDDOWN(va, BY2PG);
    tmp = (u_int *)USTACKTOP;// 设置临时地址,这个地址开始是invalid memory。这块空间没用过
    /* 首先要判断是写时复制页面 */
    u_int perm = (*vpt)[VPN(va)] & 0xfff;
    if(!(perm & PTE_COW)) {
        user_panic("Error at fork.c/pgfault. perm has no PTE_COW\n"); 
        return ;
    }
    //map the new page at a temporary place
    /* 分配一个新的页面到临时位置tmp */
    if( syscall_mem_alloc(0, tmp, PTE_V | PTE_R) < 0 ) {
        user_panic("Error at fork.c/pgfault. syscall_mem_alloc failed\n");
        return ;
    }

    /* 将要va地址上的内容复制到刚分配的页(临时位置) */ 
    user_bcopy((void *)va, (void *)tmp, BY2PG);
    //map the page on the appropriate place
    /*让va也映射到刚刚分配的页上 */
    if( syscall_mem_map(0, tmp, 0, va, PTE_V | PTE_R) < 0){
        user_panic("Error at fork.c/pgfault. syscall_mem_map failed\n");
        return ;
    }
    //unmap the temporary place 
    /* 取消临时位置的映射 */
    if( syscall_mem_unmap(0, tmp) < 0){
        user_panic("Error at fork.c/pgfault. syscall_mem_unmap failed\n");
        return ;
    }
}

为什么不直接将va映射到刚分配的物理页上? 是因为一但直接映射,va之前对应的物理地址就找不到了,相应的数据也就找不到了。

前面也提到,父节程在刚进入fork时,就要调用set_pgfault_handler 来为自身分配异常处理栈和设置缺页中断处理函数为 __asm_pgfault_handler。因为父进程在执行得过程中也可能会碰到写时复制缺页中断。

Exercise 4.14

Exercise 4.14 填写 lib/syscall_all.c 中的 sys_set_env_status 函数

这个函数相对来说就比较简单了。父节程调用该函数将子进程的状态设为ENV_RUNNABLE 来唤醒进程。同时,因为这是首次设置状态为ENV_RUNNABLE, 子进程还未处于调度链表中,因此需要将子进程插入调度链表。

int sys_set_env_status(int sysno, u_int envid, u_int status)
{
    struct Env *env;
    int ret;
    /* 判断状态是否合法 */
    if( status > 2 || status < 0) return - E_INVAL;
    if((ret = envid2env(envid, &env, 1) ) < 0) return ret;
    env -> env_status = status;
    if(status == ENV_RUNNABLE) //插入链表
        LIST_INSERT_HEAD(env_sched_list, env, env_sched_link);
    return 0;
}

fork函数的整个流程,在前面流程图已经说了,这里就不再说了。

int fork(void)
{
    /* 只会被父进程执行的部分从这里开始 */
    u_int newenvid;
    extern struct Env *envs;
    extern struct Env *env;
    u_int i;
    u_int parent_id = syscall_getenvid();    //先保存父进程的id
    
    //The parent installs pgfault using set_pgfault_handler
    /* 父进程为自身分配了异常处理栈 */
    set_pgfault_handler(pgfault);
    //alloc a new alloc
    newenvid = syscall_env_alloc(); // 获取子进程的envid
    /* 只会被父进程执行的部分结束,接下来的代码父子进程会共同执行*/
    //writef("In fork.c/fork, 获取子进程的envid success! envid : %d\n", newenvid);
    u_int envid;
    if(newenvid == 0) {
        //writef("******Start. This is Son's env**********\n");

        /*这个只有子进程会进入这个if语句来执行*/
        env = &envs[ENVX(syscall_getenvid())];/*用户态不能使用envid2env*/
        env -> env_parent_id = parent_id; //刚刚设置的parent_id
        return 0;    //子进程返回0
    }
    //writef("***********Start fork.c/fork Father's env**********\n");
    
    /*这个newenvid 是子进程的envid*/
    /*1. 遍历父进程地址空间,进行 duppage*/
    for( i = 0; i < VPN(USTACKTOP) ; ++ i ){
        if( ((*vpd)[i >> 10]) && ((*vpt)[i]) ) {
            duppage(newenvid, i);
        }
    }

    /*2. 为子进程分配异常处理栈(异常处理栈每个进程都要有单独的) */
    if (syscall_mem_alloc(newenvid, UXSTACKTOP - BY2PG, PTE_V | PTE_R) < 0 ) {
        writef("Error at fork.c/fork. syscall_mem_alloc for Son_env failed\n");
        return -1;
    }

    /* 3. 设置子进程的处理函数,确保缺页中断可以正常执行。*/
    if(syscall_set_pgfault_handler(newenvid, __asm_pgfault_handler, UXSTACKTOP) < 0) {
        writef("Error at fork.c/fork. syscall_set_pgfault_handler for Son_env failed\n");
        return -1;
    }
    /*注意在开始的地方,父进程已经调用set_pgfault_handler,在为自身分配异常处理栈之后
     * 同时也设置了 __pgfault_handler = pgfault。 子进程不需要再次设置。*/
    /* 4.设置子进程的运行状态 */
    syscall_set_env_status(newenvid, ENV_RUNNABLE);
    return newenvid;//返回子进程的envid
}

Lab4 可以说是目前最难一个实验,需要完成的函数很多,第一次接触这个函数会觉得无从下手,同时也牵扯到用户态和内核态。Fork函数的整个流程也需要一定的时间才能理解。本实验细节也很多,需要细心,因为这个实验调试是一个很麻烦的事情,最常见的一个搞错误莫过于TOO LOW了,出错也是几乎不知道哪里出错了,只能加输入输出语句,作用也不是很大。任何一个函数出错都可能导致出错,况且这次的函数还这么多。

Last modification:August 7th, 2020 at 08:48 pm
如果觉得我的文章对你有用,请随意赞赏