xv6: process

根据OSTEP的说法，操作系统最关键的3个要素是virtualization、concurrency和persistence。关于进程的抽象是第一个关键要素virtualization的核心，是第二个关键要素concurrency的基础。进程之间通过时间分片各自独立地占有处理器，通过维护各自的分页表拥有独立的地址空间。

这是xv6系列的第6篇。以下是xv6系列的目录：

数据结构

进程

结构体proc定义了xv6中的进程：

// proc.h
struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  enum procstate state;        // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

其中包括了若干重要字段：

pid：进程ID
pgdir：分页表，各个进程维护各自的分页表，各自拥有独立的地址空间
kstack： kernel stack的底端
state：当前进程状态(UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE)
tf：trap frame。当进程需要发起system call时用于保存进入中断时建立的trap frame
context：进程间切换时用于保存/恢复寄存器状态
chan：进程间交互的通道

进程表

xv6维护一张全局的分页表ptable：

// proc.c
struct {
  struct spinlock lock;
  struct proc proc[NPROC];
} ptable;

ptable维护一个包含NPROC个proc的数组。最初进程表中所有proc都处于UNUSED状态（static variables in c are automatically initialized）。ptable使用自旋锁来避免各个进程同时操作的问题。

进程创建

allocate

allocproc函数的工作：

遍历ptable，在其中寻找一个状态为UNUSED的进程
如果找到，将它的状态设为EMBRYO，并设置它的pid（pid是一个单增的数）
通过kalloc申请一个内存页作为kernel stack
在kernel stack上为trapframe分配地址
在trapframe之后将trapret的地址压栈，这样进程从forkret函数返回之后，将进入trapret过程。trapret将清理trapframe及其他相关参数
在kernel stack上为context分配地址，设置context中的%eip使之指向forkret
最后返回指向当前进程的指针

执行allocproc之前必须先获得ptable锁。

int nextpid = 1;

static struct proc* allocproc(void) {
  struct proc *p;
  char *sp;

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == UNUSED)
      goto found;
  return 0;

found:
  p->state = EMBRYO;
  p->pid = nextpid++;

  if((p->kstack = kalloc()) == 0){   // Allocate kernel stack.
    p->state = UNUSED;
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;

  sp -= sizeof *p->tf;    // Leave room for trap frame.
  p->tf = (struct trapframe*)sp;

  // Set up new context to start executing at forkret, which returns to trapret.
  sp -= 4;
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;

  return p;
}

fork

unix在创建进程时的经典设计：将创建新进程的工作拆分成fork和exec两步。

fork的工作是从当前进程（父进程）复制出一个新进程（子进程）。父进程的正常工作流程如下：

首先锁定ptable
通过allocproc创建子进程np
复制当前进程的状态到np，包括pgdir（由copyuvm实现），trapframe和打开的文件等
将np中trapframe中的%eax设为0（根据调用规则，%eax中保存函数返回值）
将np的状态从EMBRYO更新为RUNNABLE
解锁并返回子进程np的pid

int fork(void) {
  int i, pid;
  struct proc *np;

  acquire(&ptable.lock);

  // Allocate process.
  if((np = allocproc()) == 0){
    release(&ptable.lock);
    return -1;
  }

  // Copy process state from p.
  if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){
    ... // copying user address space failed, clean up
    return -1;
  }
  np->sz = proc->sz;
  np->parent = proc;
  *np->tf = *proc->tf;

  np->tf->eax = 0; // Clear %eax so that fork returns 0 in child.

  for(i = 0; i < NOFILE; i++)
    if(proc->ofile[i])
      np->ofile[i] = filedup(proc->ofile[i]);
  np->cwd = idup(proc->cwd);

  safestrcpy(np->name, proc->name, sizeof(proc->name));
  pid = np->pid;
  np->state = RUNNABLE;

  release(&ptable.lock);

  return pid;
}

子进程的轨迹如下：

由于fork将它的状态设为RUNNABLE，它将处于可执行状态等待某个CPU的调度进程通过context switch将它切入执行状态
context swtich之后，系统将从context->eip字段中读取待执行指令的地址。由于 allocproc在设置子进程kernel stack时令这个位置指向了forkret
forkret函数返回之后，根据调用规则，系统将读取保存在栈上的return address载入%eip中。而allocproc将return address设置为trapret。于是当子进程进入trapret，它将trapframe还原到各个寄存器中
trapret的最后将执行iret从中断返回，函数返回值位于tf->eax字段中。fork将这个位置置零，所以成功的fork在子进程中返回值为0。

xv6在fork时，子进程完整地复制了父进程的各种状态，包括分页表、文件列表等。但在fork之后立即exec执行新程序的情况下，子进程的状态又立即会被重置。所以更现代的unix系统（包括linux）使用了copy-on-write的做法，让fork前后的两个进程短暂的共享地址空间，而将复制的操作延迟到有一方需要修改状态时再执行。

exec

由fork而来的子进程最初使用从父进程复制而来的分页表，于是它们使用基本相同的地址空间。但是当子进程需要进行与父进程不同的操作时，就需要通过系统函数exec从硬盘读取新的指令，并且重新设置地址空间。和所有系统函数一样，exec需要在kernel mode下执行，使用kernel stack。

exec首先调用setupkvm创建新的分页表，并设置kernel部分的地址空间：

int exec(char *path, char **argv) {
  char *s, *last;
  int i, off;
  uint argc, sz, sp, ustack[3+MAXARG+1];
  struct elfhdr elf;
  struct inode *ip;
  struct proghdr ph;
  pde_t *pgdir, *oldpgdir;

  ... // load inode and check elf header
  if((pgdir = setupkvm()) == 0)
    goto bad;
  ...

然后从硬盘读取可执行文件（elf格式），通过allocuvm分配一部分属于user部分的地址空间，并且由loaduvm将可执行代码载入：

  ...
  // Load program into memory.
  sz = 0;
  for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
    ... // read program header and sanity checks
    if((sz = allocuvm(pgdir, sz, ph.vaddr + ph.memsz)) == 0)
      goto bad;
    if(ph.vaddr % PGSIZE != 0)
      goto bad;
    if(loaduvm(pgdir, (char*)ph.vaddr, ip, ph.off, ph.filesz) < 0)
      goto bad;
  }
  ... // file operations

而后设置进程的user stack。exec通过allocuvm申请两个新的内存页。在虚拟地址空间中，两个新内存页紧跟在可执行代码所占用的地址之后。其中第一个内存页被设置为user mode下不能访问（clearpteu），它的作用是在code和stack之间做一个隔断，避免栈溢出时侵入代码部分的地址空间。第二个内存用作user stack，sp是一个指向user stack当前位置的指针。

  ...
  sz = PGROUNDUP(sz);
  if((sz = allocuvm(pgdir, sz, sz + 2*PGSIZE)) == 0)
    goto bad;
  clearpteu(pgdir, (char*)(sz - 2*PGSIZE));
  sp = sz;
  ...

然后处理参数。将参数复制到user stack上：

  ...
  // Push argument strings, prepare rest of stack in ustack.
  for(argc = 0; argv[argc]; argc++) {
    if(argc >= MAXARG)
      goto bad;
    sp = (sp - (strlen(argv[argc]) + 1)) & ~3;
    if(copyout(pgdir, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
      goto bad;
    ustack[3+argc] = sp;
  }
  ustack[3+argc] = 0;

  ustack[0] = 0xffffffff;  // fake return PC
  ustack[1] = argc;
  ustack[2] = sp - (argc+1)*4;  // argv pointer

  sp -= (3+argc+1) * 4;
  if(copyout(pgdir, sp, ustack, (3+argc+1)*4) < 0)
    goto bad;

最后切换到user mode。这里需要完成以下操作：

由于从中断返回后，进程将要执行新载入程序的main函数，所以修改trap frame中的%eip为elf.entry
同时进程将切换用user stack，所以修改trap frame中的%esp为sp
然后通过switchuvm保存kernel stack的地址到task state中。这样进程此后如果需要发起中断可以找回kernel stack的位置。

  ...
  oldpgdir = proc->pgdir;
  proc->pgdir = pgdir;
  proc->sz = sz;
  proc->tf->eip = elf.entry;  // main
  proc->tf->esp = sp;
  switchuvm(proc);
  freevm(oldpgdir);
  return 0;
}

最后，exec包含了一段异常处理代码bad：

 bad:
  if(pgdir)
    freevm(pgdir);
  ... // clean up inode related
  }
  return -1;

当exec执行出错时就跳转到这里。bad主要是清理现场，包括通过freevm清除exec中新建的分页表等。

数据结构

进程

进程表

进程创建

allocate

fork

exec

参考