日曜研究室 LLVMによるプログラミング言語の実装 xv6ソースコードリーディング 技術 日記
日曜研究室

日曜研究室

まだ庭の小石の数を数え終わっていない

技術

[xv6 #15] Chapter 1 – The first process – Code: Process creation

投稿日
2012/2/19 日曜日
カテゴリー
技術
タグ
著者
Take it easy!

テキストの23〜25ページ

本文

この節では、xv6がどうやって最初のプロセスを生成するかについて述べる。
xv6のカーネルは、プロセスごとに多くの状態を管理する。
それらの状態はproc構造体にまとめられている。
ひとつのプロセスのカーネル状態で一番重要な部品は、それ自身のページテーブルとそれが指す物理メモリ、それ自身のカーネルスタック、それ自身の実行状態（run state）である。
proc構造体の要素を指すための記法として、p->xxxという形を用いる。

proc.hに定義されてるproc構造体

// Per-process state
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
  volatile 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)
};

プロセスのカーネル状態を、プロセスの味方上のカーネルの中で実行される、実行スレッド（or thread for short）として見るべきである。
（多分、「プロセスの味方上のカーネル」=「プロセスの仮想アドレス空間上に配置されたカーネル」。「or thread for short」の方はうまい訳が思いつかないどころかイメージも謎）
スレッドは、計算を実行する。
しかしそれは止めれるし再開も出来る。
例えば、プロセスがシステムコールを呼ぶとき、CPUはそのプロセスの実行からそのプロセスのカーネルスレッドの実行へ切り替える。
プロセスのカーネルスレッドは、システムコールの実装（例えばファイルを読んだり）を実行する。
そしてそれからプロセスに戻る。
xv6は、システムコールがカーネルの中でI/Oのために待てる（もしくは”block”できる）ようにするため、そしてI/Oが終わったときに元の実行中の場所に復帰できるようにするために、スレッドとしてシステムコールを実行する。
カーネルスレッドの多くの状態（ローカル変数、関数の戻り先アドレス）は、カーネルスレッドのスタックp->kstackに配置される。
それぞれのプロセスのカーネルスタックは、ユーザスタックを壊さないようにするために、ユーザスタックとは別になっている。
つまりプロセスを、2つの実行スレッドを持っているとみなすことができる。
一つはユーザスレッド、もう一つはカーネルスレッドである。

p->stateは、プロセスが割り当て済みか、実行準備が完了してるか、実行中か、I/O待ちか、終了中かどうかを示す。

p->pgdirは、PTEの配列を保持する。
xv6は、プロセスが実行されるとき、ページングハードウェアにそのプロセスのp->pgdirを使わせるようにする。
プロセスのページテーブルはまた、プロセスのメモリを保持するために割り当て済みの物理ページのアドレスのレコードとして動く。

最初のプロセスを生成する流れは、main関数がuserinit関数を呼ぶところから始まる。
userinit関数の最初のアクションはallocproc関数を呼ぶことである。
allocprocの仕事は、プロセステーブルにスロット（proc構造体）を割り当てることと、カーネルスレッドを実行するために必要なプロセス状態の一部の初期化である。
userinitが一番最初のプロセスのために呼ばれる間、allocprocは、全ての新しいプロセスのために呼ばれる。
allocprocは、UNUSED状態をキーにプロセステーブルをスキャンする。
未使用のプロセスを見つけたとき、allocprocは使用中を示すためEMBRYOをセットし、一意のpidを付与する。
次に、プロセスのカーネルスレッドのためのカーネルスタックを割り当てようとする。
もし割り当てが失敗したら、allocprocは状態をUNUSEDに戻し、失敗を伝えるためにゼロを返す。

main.cのmain関数（参照コミットが変わったので以前載せたものとは違うはずです。）

// Bootstrap processor starts running C code here.
// Allocate a real stack and switch to it, first
// doing some setup required for memory allocator to work.
int
main(void)
{
  kvmalloc();      // kernel page table
  mpinit();        // collect info about this machine
  lapicinit(mpbcpu());
  seginit();       // set up segments
  cprintf("\ncpu%d: starting xv6\n\n", cpu->id);
  picinit();       // interrupt controller
  ioapicinit();    // another interrupt controller
  consoleinit();   // I/O devices & their interrupts
  uartinit();      // serial port
  pinit();         // process table
  tvinit();        // trap vectors
  binit();         // buffer cache
  fileinit();      // file table
  iinit();         // inode cache
  ideinit();       // disk
  if(!ismp)
    timerinit();   // uniprocessor timer
  startothers();    // start other processors (must come before kinit)
  kinit();         // initialize memory allocator
  userinit();      // first user process  (must come after kinit)
  // Finish setting up this processor in mpmain.
  mpmain();
}

proc.cのuserinit関数とallocproc関数

//PAGEBREAK: 32
// Set up first user process.
void
userinit(void)
{
  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];
  
  p = allocproc();
  initproc = p;
  if((p->pgdir = setupkvm(kalloc)) == 0)
    panic("userinit: out of memory?");
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  p->sz = PGSIZE;
  memset(p->tf, 0, sizeof(*p->tf));
  p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
  p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
  p->tf->es = p->tf->ds;
  p->tf->ss = p->tf->ds;
  p->tf->eflags = FL_IF;
  p->tf->esp = PGSIZE;
  p->tf->eip = 0;  // beginning of initcode.S

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  p->state = RUNNABLE;
}

//PAGEBREAK: 32
// Look in the process table for an UNUSED proc.
// If found, change state to EMBRYO and initialize
// state required to run in the kernel.
// Otherwise return 0.
static struct proc*
allocproc(void)
{
  struct proc *p;
  char *sp;

  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc&#91;NPROC&#93;; p++)
    if(p->state == UNUSED)
      goto found;
  release(&ptable.lock);
  return 0;

found:
  p->state = EMBRYO;
  p->pid = nextpid++;
  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }
  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;

  return p;
}

さてここで、allocprocは新しいプロセスのカーネルスタックをセットアップしなければならない。
通常は、プロセスはforkによってのみ作られる。
なので、新しいプロセスは、親からコピーされて始まる。
forkの結果、内容は親と同じだが独立なメモリを持つ子プロセスが生まれる。
allocprocは、特別に用意されたカーネルスタックと、親と同じユーザ空間上の場所（forkシステムコールから戻る場所）に戻るためのカーネルレジスタの組で、その子プロセスのカーネルスレッドでの実行を開始するため子プロセスをセットアップする。
その用意されたカーネルスタックのレイアウトは図1-3に示す。
allocprocはこの仕事の一部を、リターンプログラムカウンタ値（return program counter values）をセットアップすることでこなす。
リターンプログラムカウンタ値は、新しいプロセスのカーネルスレッドをまずforkretで実行しそしてtrapretで実行するようにする。（allocproc関数の最後のあたりを参照。コード上ではまず戻り先のtrapretを設定してから飛び先のforkretを設定してる。）
カーネルスレッドは、p->contextからコピーされたレジスタの内容で実行を開始する。
要するに、p->context->eipをforkretに設定することは、カーネルスレッドをforkretのはじめから実行することを引き起こす。（後に載せますが、forkretは関数です。つまり関数ポインタをセットするということになります。）
この関数は、スタックの下にあるアドレスにとにかく戻る。
コンテキストスイッチのコード（以下のswitch.S参照）は、p->contextの終わりのすぐ次を指すようにスタックをセットする。
allocprocは、スタック上にp->contextを置き、そしてtrapretへのポインタをすぐその上に置く。
それがforkretの戻り先となる。
trapretは、カーネルスタックのトップに保持された値からユーザレジスタを復元し、プロセスにジャンプする。（以下のtrapasm.S参照）
このセットアップは、通常のforkや最初のプロセスの生成と同じである。
ただ、最初のプロセスの生成の場合は、forkから返ってきたところからというよりむしろ、位置ゼロから実行を始める。

図1-3 新しいカーネルスタックのセットアップ

proc.cのforkret関数

// A fork child's very first scheduling by scheduler()
// will swtch here.  "Return" to user space.
void
forkret(void)
{
  static int first = 1;
  // Still holding ptable.lock from scheduler.
  release(&ptable.lock);

  if (first) {
    // Some initialization functions must be run in the context
    // of a regular process (e.g., they call sleep), and thus cannot 
    // be run from main().
    first = 0;
    initlog();
  }
  
  // Return to "caller", actually trapret (see allocproc).
}

switch.Sのswitch（これでswitch.Sの全てです。）

# Context switch
#
#   void swtch(struct context **old, struct context *new);
# 
# Save current register context in old
# and then load register context from new.

.globl swtch
swtch:
  movl 4(%esp), %eax
  movl 8(%esp), %edx

  # Save old callee-save registers
  pushl %ebp
  pushl %ebx
  pushl %esi
  pushl %edi

  # Switch stacks
  movl %esp, (%eax)
  movl %edx, %esp

  # Load new callee-save registers
  popl %edi
  popl %esi
  popl %ebx
  popl %ebp
  ret

trapasm.Sのtrapret
.globl trapret
trapret:
  popal
  popl %gs
  popl %fs
  popl %es
  popl %ds
  addl $0x8, %esp  # trapno and errcode
  iret

第2章に載ってるが、ユーザソフトウェアからカーネルへの制御を移動する方法は、割り込みの仕組みを元にしている。
その仕組みは、システムコールや中断や例外で使われる。
プロセスが実行されてる間、制御をカーネルに移すときはいつでも、ハードウェアとxv6は、そのプロセスのカーネルスタックのトップにユーザレジスタを保存し、そのときとのコードをトラップする。
userinit関数は、もしプロセスが割り込み経由（userinit関数の中でp->tfの一連のメンバに値をセットしてる部分）でカーネルに入ったら、新しいスタックのトップに、そこにあるであろう彼らにそっくりな値を書き込む。
だから、カーネルからプロセスのユーザコードに戻る通常のコードはうまく動作する。
それらの値は、ユーザレジスタに保持されるtrapframe構造体である。
そうやってプロセスのカーネルスタックは、図1-3で示されるような準備完了状態になる。

最初のプロセスは、小さいプログラム（initcode.S）を実行する。
そのプロセスは、このプログラムを保持するための物理メモリが必要である。
そのプログラムは、そのメモリにコピーされる必要がある。
そしてそのプロセスは、そのメモリを指すページテーブルを必要とする。

initcode.S（これで全てです。）

# Initial process execs /init.

#include "syscall.h"
#include "traps.h"


# exec(init, argv)
.globl start
start:
  pushl $argv
  pushl $init
  pushl $0  // where caller pc would be
  movl $SYS_exec, %eax
  int $T_SYSCALL

# for(;;) exit();
exit:
  movl $SYS_exit, %eax
  int $T_SYSCALL
  jmp exit

# char init[] = "/init\0";
init:
  .string "/init\0"

# char *argv[] = { init, 0 };
.p2align 2
argv:
  .long init
  .long 0

userinit関数は、（最初は）カーネル用のメモリだけを対応付けるそのプロセスのためのページテーブルを作成するためにsetupkvm関数を呼ぶ。
この関数はカーネルがそれ自身のページテーブルをセットアップするために使うのと同じである。（以前、その11, 12, 14で出てきましたね。）

vm.cのsetupkvm関数

// Set up kernel part of a page table.
pde_t*
setupkvm(char* (*alloc)(void))
{
  pde_t *pgdir;
  struct kmap *k;

  if((pgdir = (pde_t*)alloc()) == 0)
    return 0;
  memset(pgdir, 0, PGSIZE);
  if (p2v(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
  for(k = kmap; k < &kmap&#91;NELEM(kmap)&#93;; k++)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start, 
                (uint)k->phys_start, k->perm, alloc) < 0)
      return 0;
  return pgdir;
}&#91;/sourcecode&#93;

最初のプロセスのメモリの初期の内容は、initcode.Sのコンパイルされたものである。
カーネルがプロセスを作る過程において、リンカはそのバイナリをカーネルに埋め込み、その位置とサイズを伝えるために、二つの特別なシンボル_binary_initcode_startと_binary_initcode_sizeを定義する。
userinit関数は、inituvm関数を使ってそのバイナリを新しいプロセスのメモリにコピーする。
inituvm関数は物理メモリの1ページを割り当て、仮想アドレス0にマップし、そのページにそのバイナリをコピーする。

vm.cのinituvm関数
&#91;sourcecode language="c"&#93;// Load the initcode into address 0 of pgdir.
// sz must be less than a page.
void
inituvm(pde_t *pgdir, char *init, uint sz)
{
  char *mem;
  
  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(pgdir, 0, PGSIZE, v2p(mem), PTE_W|PTE_U, kalloc);
  memmove(mem, init, sz);
}

そういうわけで、userinit関数は初期のユーザモードの状態とともにトラップフレームをセットアップする。
%csレジスタは、特権レベルDPL_USER（例えばユーザモードはカーネルモードではない）で実行されてるセグメントSEG_UCODEのためのセグメントセレクタを含む。
そして同様に、%ds, %es, %ssは、特権レベルDPL_USERと共にSEG_UDATAを使う。
%eflagsにFL_IFをセットしてハードウェア割り込みを許可する。
このあたりは第2章でまた説明する。
（この段落は、userinit関数の中でp->tfの一連のメンバに値をセットしてる部分の事を説明してるみたいです。）

スタックポインタ%espは、一番重要で有効な仮想アドレスp->szである。
その命令ポインタは、initcodeの開始点であるアドレス0である。

userinit関数は、主にデバッグのためにinitcodeにp->nameをセットする。
p->cwdが、そのプロセスの現在の作業ディレクトリに対応する。
namei（userinit関数内のp->cwd = namei(“/”);の部分）については第5章で説明する。

一度プロセスが初期化されたら、userinitは、p->stateをRUNABLEに設定することでスケジューリング可能である印を付ける。

感想

長かった…

プロセスの生成についての話ですが、主にproc構造体とuserinit関数を中心に説明されてます。

途中やたら指示代名詞が多くて訳どころかイメージを思い浮かべることさえ難儀した部分があります。
そもそも言葉で説明するのが難しいんでしょうね。
通常は、説明を頭に入れた上でソースを読むと理解が早かったりしますが、そういうところは一旦謎の説明は忘れて頑張ってソースをじっくり読み解くほうが理解への近道でしょう。

コメント

ご存じとは思いますが、whileには、”～の間”という意味もありますが、”一方”という意味がありますので、
”userinitが一番最初のプロセスのために呼ばれる間、allocprocは、全ての新しいプロセスのために呼ばれる。”
は
”allocprocは全ての新しいプロセスのために呼ばれ、一方でuserinitは一番最初のプロセスのためにのみ呼ばれる”
ではないでしょうか。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。