os_lab5:用户进程管理

课程主页：https://www.xuetangx.com/course/THU08091000267/5883104?channel=i.area.learn_title
实验指导书：https://objectkuan.gitbooks.io/ucore-docs/content/
github：https://github.com/chyyuu/ucore_os_lab (master 分支)

前置知识

进程、虚拟存储、中断机制、系统调用。

改动点

相比于 lab4 源代码，lab5 主要做了如下改动：

• memlayout.h 增加用户空间的图形表示和宏定义

  宏定义 USERTOP/USERBASE 等指明用户虚拟地址空间范围，图形表示显示哪些用户空间属于合法空间。

  /* *
   * Virtual memory map:                                          Permissions
   *                                                              kernel/user
   *
   *     4G ------------------> +---------------------------------+
   *                            |                                 |
   *                            |         Empty Memory (*)        |
   *                            |                                 |
   *                            +---------------------------------+ 0xFB000000
   *                            |   Cur. Page Table (Kern, RW)    | RW/-- PTSIZE
   *     VPT -----------------> +---------------------------------+ 0xFAC00000
   *                            |        Invalid Memory (*)       | --/--
   *     KERNTOP -------------> +---------------------------------+ 0xF8000000
   *                            |                                 |
   *                            |    Remapped Physical Memory     | RW/-- KMEMSIZE
   *                            |                                 |
   *     KERNBASE ------------> +---------------------------------+ 0xC0000000
   *                            |        Invalid Memory (*)       | --/--
   *     USERTOP -------------> +---------------------------------+ 0xB0000000
   *                            |           User stack            |
   *                            +---------------------------------+
   *                            |                                 |
   *                            :                                 :
   *                            |         ~~~~~~~~~~~~~~~~        |
   *                            :                                 :
   *                            |                                 |
   *                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   *                            |       User Program & Heap       |
   *     UTEXT ---------------> +---------------------------------+ 0x00800000
   *                            |        Invalid Memory (*)       | --/--
   *                            |  - - - - - - - - - - - - - - -  |
   *                            |    User STAB Data (optional)    |
   *     USERBASE, USTAB------> +---------------------------------+ 0x00200000
   *                            |        Invalid Memory (*)       | --/--
   *     0 -------------------> +---------------------------------+ 0x00000000
   * (*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
   *     "Empty Memory" is normally unmapped, but user programs may map pages
   *     there if desired.
   *
   * */

• pmm.[ch] 添加若干与页表项、页面相关的拷贝函数

• vmm.[ch] 添加若干与 mm/vma/pgdir 相关的函数

  值得注意的是： struct mm_struct 属性内容发生变化：

  struct mm_struct {
      list_entry_t mmap_list;        
      struct vma_struct *mmap_cache; 
      pde_t *pgdir;                  
      int map_count;                 
      void *sm_priv;                 
      int mm_count;                  // 共享此 mm 的进程数量
      lock_t mm_lock;                // 互斥锁, dup_map() 实现时使用，
  };

• proc.h 扩展 proc_struct 数据结构

  proc_struct 的扩展点具体如下：

  struct proc_struct {
      ... // 同以往结构的属性
      int exit_code;                              // 当前进程的退出码，供父进程使用。
      uint32_t wait_state;                        // 当前进程的等待状态，供子进程退出时调用。
      struct proc_struct *cptr, *yptr, *optr;     
      // 若干指针存放与其他进程间的关系(孩子进程指针(总是指向最新的子进程)、更年轻的(或称为前一个)兄弟进程指针、更年长的(或称为后一个)兄弟进程指针(后面两个指针构建兄弟进程的双向链表))
  };

• proc.c 增加若干与 SYSCALL 相关的实现函数

在 ucore 中，进程与线程采用同一套管理机制，它们间的区别可能仅在于：进程之间不共享地址空间，而线程间共享某进程的地址空间 (通过共享 mm 结构即可)，因此两个术语基本可以混用。

练习一

该练习用于了解 do_exec() 的具体实现。

在 lab4 中，我们已经知道：如何创建一个内核线程，并通过调度使得其正常执行。那么我们首先看一下 lab5 中所涉的内核线程：

// proc_init() -> 构建 idleproc 和 initproc
---
int pid = kernel_thread(init_main, NULL, 0); // 此句构建 initproc，其执行 initmain 函数。
---
    
// initmain() -> 构建 user_mainproc
---
static int init_main(void *arg) {
    size_t nr_free_pages_store = nr_free_pages();
    size_t kernel_allocated_store = kallocated();

    
    int pid = kernel_thread(user_main, NULL, 0); // 此句构建 user_mainproc，属于第三个内核线程，它是 initproc 的子线程。
    if (pid <= 0) {
        panic("create user_main failed.\n");
    }

    while (do_wait(0, NULL) == 0) { // 等待 user_mainproc 结束，并回收其剩余资源(此为后话)。
        schedule();
    }
    return 0;
}
---
    
// user_main
---
static int user_main(void *arg) {
#ifdef TEST
    KERNEL_EXECVE2(TEST, TESTSTART, TESTSIZE);
#else
    KERNEL_EXECVE(exit); // 实际执行 sys_exec 系统调用，使用 do_exec() 重新配置当前进程的内存空间，并执行 exit 程序。
#endif
    panic("user_main execve failed.\n");
}
---

接下来，我们主要看看 do_exec() 的实现细节 (do_exec 等价于实际系统中的 exec() )：

int do_execve(const char *name, size_t len, unsigned char *binary, size_t size) {
    struct mm_struct *mm = current->mm;
    if (!user_mem_check(mm, (uintptr_t)name, len, 0)) {
        return -E_INVAL;
    }
    if (len > PROC_NAME_LEN) {
        len = PROC_NAME_LEN;
    }

    char local_name[PROC_NAME_LEN + 1];
    memset(local_name, 0, sizeof(local_name));
    memcpy(local_name, name, len);

    // 清空原有 mm。
    if (mm != NULL) {
        // 首先切换页目录表，以防访问到不该访问的，使得访问异常。
        lcr3(boot_cr3);
        // mm 共享数减一，如此此时为 0，则需要删除此 mm，具体包括 vma集合、页目录表和页表、实际物理空间、mm 结构。
        if (mm_count_dec(mm) == 0) {
            exit_mmap(mm);
            put_pgdir(mm);
            mm_destroy(mm);
        }
        current->mm = NULL;
    }
    int ret;
    // load_icode 用来加载并解析一个处于内存中的ELF执行文件格式的应用程序，其主要工作包括：创建 mm、填充 mm 各属性、填充与代码段，数据段，栈相关的物理页、重新设置 tf，使得能够正确返回至用户空间，并开始执行相关代码。具体涉及 ELF 文件格式，可不细理。
    if ((ret = load_icode(binary, size)) != 0) {
        goto execve_exit;
    }
    set_proc_name(current, local_name);
    return 0;

execve_exit:
    do_exit(ret);
    panic("already exit: %e.\n", ret);
}

// load_icode 涉及重置 tf 部分：
struct trapframe *tf = current->tf;
memset(tf, 0, sizeof(struct trapframe));
// 更新 cs 等段寄存器值为用户态段。那么当执行中断返回时，系统便可基于此判断是否存在特权级切换，从而正确弹栈。
tf->tf_cs = USER_CS;
tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS;
tf->tf_esp = USTACKTOP;
tf->tf_eip = elf->e_entry;
tf->tf_eflags = FL_IF;

问题回答

请在实验报告中描述当创建一个用户态进程并加载了应用程序后，CPU是如何让这个应用程 序最终在用户态执行起来的。即这个用户态进程被ucore选择占用CPU执行（RUNNING态） 到具体执行应用程序第一条指令的整个经过。

• 分析在创建了用户态进程并且加载了应用程序之后，其占用CPU执行到具体执行应用程序的整个经过：
  • 在经过调度器占用了CPU的资源之后，用户态进程调用了exec系统调用，从而转入到了系统调用的处理例程；
  • 在经过了正常的中断处理例程之后，最终控制权转移到了syscall.c中的syscall函数，然后根据系统调用号转移给了sys_exec函数，在该函数中调用了上文中提及的do_execve函数来完成指定应用程序的加载；
  • 在do_execve中进行了若干设置，包括推出当前进程的页表，换用kernel的PDT之后，使用load_icode函数，完成了对整个用户线程内存空间的初始化，包括堆栈的设置以及将ELF可执行文件的加载，之后通过current->tf指针修改了当前系统调用的trapframe，使得最终中断返回的时候能够切换到用户态，并且同时可以正确地将控制权转移到应用程序的入口处；
  • 在完成了do_exec函数之后，进行正常的中断返回的流程，由于中断处理例程的栈上面的eip已经被修改成了应用程序的入口处，而cs上的CPL是用户态，因此iret进行中断返回的时候会将堆栈切换到用户的栈，并且完成特权级的切换，并且跳转到要求的应用程序的入口处；
  • 接下来开始具体执行应用程序的第一条指令；

练习二

该练习用于了解 do_fork()->copy_mm() 的具体实现。

为了了解需要完成编码的函数的作用，不烦首先分析父进程调用fork系统调用生成子进程的过程：

• 父进程调用fork系统调用，进入正常的中断处理机制，最终交由syscall函数进行处理；
• 在syscall函数中，根据系统调用好，交由sys_fork函数处理；
• 该函数进一步调用了do_fork函数，这个函数是主要的创建子进程、并且将父进程的内存空间复制给子进程的逻辑所在；
• 在do_fork函数中，调用copy_mm进行内存空间的复制，在该函数中，进一步调用了dup_mmap，在这个函数中，遍历了父进程的所有合法虚拟内存空间，并且将这些空间的内容复制到子进程的内存空间中去，具体进行内存复制的函数就是我们在本次练习中需要完善的copy_range；
• 在copy_range函数中，对需要复制的内存空间按照页为单位从父进程的内存空间复制到子进程的内存空间中去；

copy_range函数的具体执行流程如下：

• 遍历父进程指定的某一段内存空间中的每一个虚拟页，如果这个虚拟页是存在的话，为子进程对应的同一个地址（但是页目录表是不一样的，因此不是一个内存空间）也申请分配一个物理页，然后将前者中的所有内容复制到后者中去，然后为子进程的这个物理页和对应的虚拟地址（事实上是线性地址）建立映射关系；而在本练习中需要完成的内容就是内存的复制和映射的建立，具体流程如下：

  • 找到父进程指定的某一物理页对应的内核虚拟地址；
  • 找到需要拷贝过去的子进程的对应物理页对应的内核虚拟地址；
  • 将前者的内容拷贝到后者中去；
  • 为子进程当前分配这一物理页映射上对应的在子进程虚拟地址空间里的一个虚拟页；

• 具体使用代码实现的结果如下所示：

char *src_kvaddr = page2kva(page); // 找到父进程需要复制的物理页在内核地址空间中的虚拟地址，这是由于这个函数执行的时候使用的时内核的地址空间
char *dst_kvaddr = page2kva(npage); // 找到子进程需要被填充的物理页的内核虚拟地址
memcpy(dst_kvaddr, src_kvaddr, PGSIZE); // 将父进程的物理页的内容复制到子进程中去
page_insert(to, npage, start, perm); // 建立子进程的物理页与虚拟页的映射关系

至此完成了本联系中所有需要的编码任务，从而正确地实现了操作系统的fork系统调用的功能;

练习三

该练习用于理解各系统调用的实现机理。

首先看用户空间的系统调用：

static inline int syscall(int num, ...) {
    va_list ap;
    va_start(ap, num);
    uint32_t a[MAX_ARGS];
    int i, ret;
    // 获取相关参数
    for (i = 0; i < MAX_ARGS; i ++) {
        a[i] = va_arg(ap, uint32_t);
    }
    va_end(ap);

    // 实施中断，并将相关参数传给相关寄存器，它们会进一步放置于 tf 内部。
    asm volatile (
        "int %1;"
        : "=a" (ret)
        : "i" (T_SYSCALL),
          "a" (num),
          "d" (a[0]),
          "c" (a[1]),
          "b" (a[2]),
          "D" (a[3]),
          "S" (a[4])
        : "cc", "memory");
    return ret;
}

// 如下为用户程序可调用的各种函数，它们统一使用 syscall 实现其功能。
int sys_exit(int error_code) {
    return syscall(SYS_exit, error_code);
}

int sys_fork(void) {
    return syscall(SYS_fork);
}

int sys_wait(int pid, int *store) {
    return syscall(SYS_wait, pid, store);
}

int sys_yield(void) {
    return syscall(SYS_yield);
}

int sys_kill(int pid) {
    return syscall(SYS_kill, pid);
}

int sys_getpid(void) {
    return syscall(SYS_getpid);
}

int sys_putc(int c) {
    return syscall(SYS_putc, c);
}

int sys_pgdir(void) {
    return syscall(SYS_pgdir);
}

接下来，硬件得到 T_SYSCALL 中断号，并调用相关中断处理程序进行处理：

case T_SYSCALL:
    syscall();
    break;

接下来，看看内核程序 syscall() 的具体实现：

static int sys_exit(uint32_t arg[]) {
    int error_code = (int)arg[0];
    return do_exit(error_code);
}

static int sys_fork(uint32_t arg[]) {
    struct trapframe *tf = current->tf;
    uintptr_t stack = tf->tf_esp;
    return do_fork(0, stack, tf);
}

static int sys_wait(uint32_t arg[]) {
    int pid = (int)arg[0];
    int *store = (int *)arg[1];
    return do_wait(pid, store);
}

static int sys_exec(uint32_t arg[]) {
    const char *name = (const char *)arg[0];
    size_t len = (size_t)arg[1];
    unsigned char *binary = (unsigned char *)arg[2];
    size_t size = (size_t)arg[3];
    return do_execve(name, len, binary, size);
}

static int sys_yield(uint32_t arg[]) {
    return do_yield();
}

static int sys_kill(uint32_t arg[]) {
    int pid = (int)arg[0];
    return do_kill(pid);
}

static int sys_getpid(uint32_t arg[]) {
    return current->pid;
}

static int sys_putc(uint32_t arg[]) {
    int c = (int)arg[0];
    cputchar(c);
    return 0;
}

static int sys_pgdir(uint32_t arg[]) {
    print_pgdir();
    return 0;
}

// 上述函数为 SYS_xx 的具体实现，它们会获取相关参数，并调用相关 do_xxx 进行处理，最后返回。

static int (*syscalls[])(uint32_t arg[]) = {
    [SYS_exit]              sys_exit,
    [SYS_fork]              sys_fork,
    [SYS_wait]              sys_wait,
    [SYS_exec]              sys_exec,
    [SYS_yield]             sys_yield,
    [SYS_kill]              sys_kill,
    [SYS_getpid]            sys_getpid,
    [SYS_putc]              sys_putc,
    [SYS_pgdir]             sys_pgdir,
};

#define NUM_SYSCALLS        ((sizeof(syscalls)) / (sizeof(syscalls[0])))

void syscall(void) {
    struct trapframe *tf = current->tf;
    uint32_t arg[5];
    int num = tf->tf_regs.reg_eax;
    if (num >= 0 && num < NUM_SYSCALLS) {
        if (syscalls[num] != NULL) {
            // 从 tf 中获取相关参数，放置于 arg[] 内部，并调用相应的 SYS_xxx 进行处理。
            arg[0] = tf->tf_regs.reg_edx;
            arg[1] = tf->tf_regs.reg_ecx;
            arg[2] = tf->tf_regs.reg_ebx;
            arg[3] = tf->tf_regs.reg_edi;
            arg[4] = tf->tf_regs.reg_esi;
            tf->tf_regs.reg_eax = syscalls[num](arg);
            return ;
        }
    }
    print_trapframe(tf);
    panic("undefined syscall %d, pid = %d, name = %s.\n",
            num, current->pid, current->name);
}

对于上述 sys_xxx，简要做如下分析：

• do_fork(0, stack, tf)

  第一个参数为 0，表明其会完全复制当前进程的地址空间，第二三参数，表明其会完全复制当前进程的用户栈及中断帧。如此实现，含义与实际 fork() 相同。

  由于之前早已说明 do_fork() 的实现细节，在此不再赘述。

• do_execve(name, len, binary, size)

  练习一已经说明其含义，在此不再赘述。

• do_exit(error_code)

  do_exit() 用于回收该进程的内存资源，并设置 PROC_ZOMBIE 状态以等待父进程处理。如果当前进程存在子进程，需要将它们置为 initproc 的子进程。

• do_wait(pid, store)

  do_wait() 用于等待子进程处于 PROC_ZOMBIE 状态，并回收其剩余资源 (指代内核栈、PCB)。

  某进程资源的回收工作具体分为两步：**do_exit() 自主回收内存资源，do_wait() 由父进程回收内核资源**。之所以如此实现，原因在于：进程回收内核资源，则其必定在使用内核栈，而内核资源包括内核栈，因此存在一个矛盾。另外，父进程可通过回收资源过程，获取其子进程的运行结果，然后动态施行相关操作。

• do_yield()

  do_yield() 用于释放 CPU，并让其调度处理其他进程。

• do_kill(pid)

  do_kill() 用于设置特定进程的 flags |= PF_EXITING;。

• sys_getpid/sys_putc/sys_pgdir

  此三者都比较简单，没什么可说的。

需要注意：do_yield() 和 do_kill() 功能实现的部分代码在相应的do_xxx函数内部，部分代码位于 trap() 内部，trap() 内部的实现如下：

void trap(struct trapframe *tf) {
    if (current == NULL) {
        trap_dispatch(tf);
    }
    else {
        // 如此保存旧 tf，保证实现中断嵌套。
        struct trapframe *otf = current->tf;
        current->tf = tf;
    
        bool in_kernel = trap_in_kernel(tf);
    
        trap_dispatch(tf);
    
        current->tf = otf;
        if (!in_kernel) {
            // do_kill 发挥作用就比较慢，当特定进程再次进入中断后，才会让它触动回收。
            // 进程进入中断的方式主要存在两种：1. 系统调用 2. 时钟中断。
            if (current->flags & PF_EXITING) {
                do_exit(-E_KILLED);
            }
            
            // do_yield 设置字段后，中断返回前即会重新调度。
            if (current->need_resched) {
                schedule();
            }
        }
    }
}

ucore中一个用户态进程的执行状态生命周期图（包执行状态，执行状态之间的变换关系，以及产生变换的事件或函数调用）

                                            RUNNING----------------+
                                               A |                  |
                                               | |                  |
                                            proc_run()            exit()  
                                               | |                  |
                                               | V                  V
--alloc_page()--> UNINIT --wakeup_proc()--> RUNNABLE --exit()--> ZOMBIE
                                               A                    A
                                               |                    |
                                           子进程exit()            exit()
                                               |                    |
                                               |                    |
                                            SLEEPING----------------+

扩展练习一

该练习用于实现 Copy on Write(COW) 机制。

COW 机制实现比较复杂，并没有实现。在此简要说明其思想。

当执行 do_fork(0, stack, tf) -> copy_mm() 时，复制 vma 集合、页目录表等内容，共享当前进程的物理页，并设置相关条目为只读 (而非原先的复制物理页)。

当新旧进程需要写共享物理页时，触发中断，执行 do_pgfault()。如果该页面为只读，且其共享数大于 1，则表明存在新旧进程在共享物理页，因此复制该物理页给当前进程，并设置相关条目为读写。

如何创建用户线程？

借助于 do_fork()/do_execve()，我们成功创建用户进程 (也可称作该进程对应的主线程)，它所对应的栈直接位于虚拟地址空间中的栈区。

用户进程的栈大小默认为 8M。当栈所占实际空间小于 8M 时，它会因缺页中断而动态增长；当栈所占实际空间大于 8M 时，便会触发 栈溢出。

对于用户线程而言，它们需要共享用户进程资源 (例如：地址空间、打开的文件列表)，而独占栈空间、寄存器组等资源。

经过上面的实现，共享进程资源比较简单，无非就是设置相关指针以指向相同结构体；独占寄存器组也比较简单，使用 proc.context 保存即可；唯一难点在于：如何独占栈空间的同时，实现共享该进程的地址空间？

Linux 系统的解决方案是这样的：创建用户线程之时，在当前地址空间的堆区直接分配栈空间，以此作为该线程的栈。

用户线程的栈大小默认为 16K，最大为 2M。

注：Linux 的解决方案中，线程栈空间直接分配，它不会动态增长。