xv6 code reading (6.fork編)

forkは処理としては簡単そうに見えるけど、中々奥深い。
先ず、概要として、やっていることはprocess内でprocessを生成すること。
forkは子processだと0,親processだと子pidが帰るって仕様で、
userlandからみると、1つの処理から2つの別processが返る。
これは考えてみると奇妙だ。どう実現されているのか。

codeを読むと、大まかな処理としては、

1. process tableから空いているprocessを確保

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

2. 取得したprocessに状態,process idを挿入

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

3. kernel内のallocatorから1page(4096byte)確保し、processに確保したlowestのaddressを挿入(kernel stackとする)

if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }

4. process内のtrap frame/context領域を確保,生成したprocess内のeip(program counter)にsystem callから帰る為の一連の処理関数のaddressを挿入

sp = p->kstack + KSTACKSIZE;

  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  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;

5. 現在(親)processのpageTable,size,attachしているfile,process名,trapframeを子processにそのままcopy.

// Copy process state from proc.
  if((np->pgdir = copyuvm(curproc->pgdir, curproc->sz)) == 0){
    kfree(np->kstack);
    np->kstack = 0;
    np->state = UNUSED;
    return -1;
  }
  np->sz = curproc->sz;
  np->parent = curproc;
  *np->tf = *curproc->tf;

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

  safestrcpy(np->name, curproc->name, sizeof(curproc->name));

6. その他、copy以外の特殊処理

生成したprocessをschedulerが見つけられる様にprocess状態をrunnableにする。
trapframeのeaxレジスタの値(子processの返り値となる)を0に設定
新しい子のpidをreturn

np->state = RUNNABLE;
np->tf->eax = 0;
pid = np->pid;
return pid;

一番の肝は、kernel内部でproc構造体をallocateしているのではなく、既に規定のアドレスにallocateされているprocess tableの空きentryへのaddressをpointして、そこからalignmentされた構造体に部分的に値を挿入していくということ。

親processの方は、一応値のcopyが終わった時点で、戻ってしまい、新しく挿入されたprocess table内のentryにschedulerがさしかかるとforkからcontext内のeipに設定された関数pointerを辿って、userlandに%eax=0としながらiretで戻るという仕組み。

つまり、状態書き換え(fork)&監視(scheduler)による2つの協力があり、初めてprocess生成できるということ。

通常、このcodeだと親が先に返りそうだけど、親のprocessがreturnする前に子供が返って来ることもざらにあって、timer割り込み契機などで、schedulerが小まめに動いているケースだ。

よくpage tableはcopy on writeとかいうけど、それはuser空間の為のpageのお話で、実際にはforkで子processが返って来るためにはschedulerの対象になる必要がある。そうなると、scheduler内の切り替え対象となるcontextは、そして、それをallocateする為のkernel用page(1page)に関しては、fork時にallocateされていなければならないのだ。

kernel stackはstack領域を使うので、当然低アドレス伸長なのだけれど、trapframe(76byte)/pointer to return(4byte) function/context(20byte).
fork後に再度systemcallが呼ばれると、contextの最後尾(eipの位置)が%ebp扱いとなる。これにより、returnすると,eipに設定されたsystemcall(trapret)が機能して、kernel側からの応答が正しくregisterを介して、user側に届く様になっている.

ちなみに、trapframeってsyscallのためのx86独自のものらしいのだけど、意外に大きい(76byte)。そしてこれは用途を考えてみれば頷けるが、contextで保存するレジスタ

struct context {
  uint edi;
  uint esi;
  uint ebx;
  uint ebp;
  uint eip;
};

と被っている。それもそのはず、contextはkernel内でのschedulingの為に存在し、trapframeはsyscallの為に存在する。schedulerはsyscall(e.g. wait,sleep,exit)を含め,trapを契機に発動するのだけれど、systemcall自体は、scheduling自体は別の仕組みで動いていて両者が保存している値が一致しているという保証などないのだ。

forkに関しては、vforkやclone等面白い拡張があるので、ぜひ拡張してみよう。

Notes

- Code/Binary Reading And Vulnerability Search

xv6 code reading (6.fork編)