xv6 initプロセス ことはじめ

あるプロセスには親プロセスという生みの親がいます。その親にも親がいます。 そして、プロセスの系譜をさかのぼり続けると一つのプロセスに行き着きます。 それはinitプロセス。Unix及びUnix系のOSではこの名前がついています。*1

またタイトルにあるxv6とは、2006年MITで開発された教育用OSです*2。 ANSI Cで書かれておりソースコードリーディングに適しています。

今回はあらゆるプロセスの祖先といえるinitプロセスの生成と実行はじめまでを、xv6のソースコードを読み、観察してみましょう。（同じ内容のスライドがあります。こちらはブログと比べスタックの動的な操作がわかりやすいです。）

あらすじ

• xv6のプロセス
• initプロセスの生成
• スケジューラがinitプロセスを選択
• スケジューラからinitへのコンテキストスイッチ
• initの実行

注意

• initプロセスに話をしぼるため、ブートローダーやカーネルの設定や初期化は完了済とします。
• 掲載するソースコードのなかで今回の話に不要と思われる記述は修正や省略をしました。例えばxv6はマルチプロセッサに対応しており、排他制御を行うコードも存在します。しかし私の理解不足と紙面の都合上意図的に省略しました。
• 以下に登場するメモリ領域の図は上が high アドレスとなっており、スタックは下に積まれます。

xv6のプロセス

早速initプロセスの生成を見ていきたいところですが、その前にxv6ではプロセスをどのように実装しているのでしょう。 それはproc.hにproc構造体として定義されています。

struct proc {
    pde_t* pgdir;          
    char *kstack;          
    enum procstate state;  
    int pid;                 
    struct proc *parent;     
    struct trapframe *tf;
    struct context *context;
};

*3

フィールド	説明
pgdir	仮想メモリと物理メモリのマッピングを定める
kstack	tfやcontextを格納する領域
state	プロセスの状態を表す。proc.hにenum型として定義される
pid	プロセスに割り振られる一意な整数値
parent	親プロセス
tf	トラップの発生時に使用される。今回はinitプロセスの実行に必要なレジスタを格納する
context	コンテキストスイッチ時にレジスタを格納する、または復元するために使用される

initもプロセスであるため、その生成はproc構造体のインスタンスとして定義されます。 Cの構造体は各メンバが連続したメモリに配置されます。 つまりinitの生成は以下のようなメモリ領域を作成することと同じです。

proc構造体のメモリレイアウト

initプロセスの生成

この節では上に挙げたメモリ領域をinitのために作成することが目標です。

すでにカーネルの設定は終わっているためmain関数の中で今回の話と関係のある関数はuserinitとmpmainの２つです。

int main(void) {
    \\ カーネル、割り込みの設定のため略
    userinit();
    mpmain();
}

userinit

userinitは次の4つの仕事を行います。

1. initプロセスの生成
2. initのカーネル空間のpagingの設定
3. initのプログラムをメモリに展開
4. トラップフレームの設定

そのうち上３つを以下の関数がuserinit内で呼ばれることで、それぞれ請け負います。

1. allocproc
2. setupkvm
3. inituvm

次のコードはuserinitの前半部分です。早速allocprocが呼ばれていることがわかります。

void userinit(void) {
    struct proc *p;

    p = allocproc();

    if((p->pgdir = setupkvm()) == 0)
        panic("userinit: out of memory?");

    inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
    .....   
}

allocproc

allocprocの主な仕事は次の３つです。

• UNUSEDなプロセスをテーブルから探す
• そのプロセスの設定
  • pid, state, trapframe, etc…
• 設定したプロセスを返す

なおallocprocは１つのプロセスを生成するので、userinitからだけではなくforkからも呼び出されます。

まずプロセステーブルの中からUNUSEDなプロセスを探す処理が次のコードです。

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

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

found:
   ... 

}

プロセステーブルptableはproc.cにグローバル変数として定義されており、64個のプロセスエントリを格納します。 コードではプロセステーブルの先頭から最後まで見て、UNUSEDなプロセスを見つけた場合foundラベルへと飛びます。

foundラベル以降は次のようなコードです。

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

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

今UNUSEDなプロセスが見つかったためその初期化を行います。まずstateをEMBRYOにしています。 EMBRYOは「生まれたて」という意味があります。またpidの割り当てを行い、グローバル変数であるnextpidをインクリメントします。これにより次回のallocproc呼び出しではプラス1された整数値がpidとして割り当てられます。

次にkallocを呼び出しpのカーネルスタックを割り当てます。これにより1ページ(4096バイト)分のメモリ領域がカーネルスタックの領域として確保されました。この領域はトラップフレームやコンテキストを格納するためにあります。ここまでの処理により次のようなメモリ領域の図になります。

kalloc直後

カーネルスタックの設定

次に確保したカーネルスタック領域を複数の部分領域へ区切ります。後の処理によりそこにトラップフレームやコンテキストを格納できるようにします。

具体的なコードは次のようなものです。

   sp = p->kstack + KSTACKSIZE;

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

まずspをカーネルスタックの最上部を指すようにします。そしてsizeof *p->tf;によりspをトラップフレームのメモリ領域分を押し下げ、そのアドレスをp->tfに代入しています。

   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;

同様にまずspを4バイト下げ、関数trapretの関数ポインタを格納します。 さらにspをコンテキスト分下げ、eipの領域に関数forkretを格納します。 関数trapretとforkretはコンテキストスイッチが起こり、スケジューラからプロセスへ制御が渡された後すぐに実行されます。

最後にpをリターンして関数を抜けます。ここまでの処理によりinitは次のようなメモリ領域を構築できました。

allocproc脱出時

userinit

再びuserinitに処理が戻ってきました。次は以下の３行です。

   if((p->pgdir = setupkvm()) == 0)
       panic("userinit: out of memory?");
   inituvm(p->pgdir, _binary_initcode_start, _binary_initcode_size);

まずsetupkvmによりinit用のページテーブルを設定します。ページテーブルにより仮想アドレスと物理アドレスのマッピングが設定されます。inituvmはこのマッピングにもとづいて仮想アドレスの0番地にinit用のプログラムinitcodeを展開します。

initcode用のメモリ確保＆展開

次にinitのトラップフレームの設定を行います。

    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

コメントにもある通りp->tf->eip = 0;でinitcodeが格納されている0番地をeipが来るようにしています。eipはx86アーキテクチャの32bit版命令ポインタで、実行する次のアドレスを格納します。今p->tf->eipが0となっているため、コンテキストスイッチ後に0番地から実行できるよう下準備をしました。

userinitの最後はpの状態をRUNNABLEにして関数を抜けます。

    p->state = RUNNABLE;

これまで作成したinitのメモリは次のようになります。

スケジューラがinitプロセスを選択

xv6のスケジューラはシンプルに実装されています。プロセステーブルを先頭から調べstateがRUNNABLEなプロセスをみつけたらそのプロセスへとコンテキストスイッチします。

以下がスケジューラのコードの一部です。for文が入れ子になっており、外側のループは無限ループになっています。

void scheduler(void) {
    struct proc *p;
    struct cpu *c = mycpu();
    c->proc = 0;
    
    for(;;) {
        
        ...
        for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
            if (p->state != RUNNABLE)
                continue;

            c->proc = p;
            
            switchuvm(p);
            p->state = RUNNING;

            swtch(&(c->scheduler), p->context);

            ...
        }

    }
}

RUNNABLEなプロセスを見つけると、まずswitchuvm(p);が呼ばれます。今RUNNABLEなプロセスはinitしかいません。 そのためswtchuvmではinitのページング設定をcr3レジスタにロードし、スケジューラのアドレス空間からinitプロセスのアドレス空間へ切り替えます。

次にinitをRUNNNIG状態にします。そしてようやくswtch関数によるコンテキストスイッチです。 swtchの第一引数と第二引数には、それぞれ古いコンテキスト（のアドレス、理由は後述）と新しいコンテキストを指定します。 今swtch(&(c->scheduler), p->context);であるためスケジューラからinitプロセスへとコンテキストスイッチすることがわかります。

スケジューラからinitへのコンテキストスイッチ

swtch

関数swtchはswtch.Sにアセンブリで書かれています。

.glonl swtch
swtch:
    # load `old`
    movl 4(%esp), %eax
    # load `new`
    movl 8(%esp), %edx

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

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

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

swtch呼び出し直後はスケジューラのカーネルスタックに、第二引数p-context, 第一引数&(c->scheduler), swtchの戻り先のアドレスの順に積みます。

まず先頭２行のアセンブリでeaxとedxに、それぞれスイッチ先のプロセスのコンテキストとスケジューラのアドレスを代入します。

    # load `old`
    movl 4(%esp), %eax
    # load `new`
    movl 8(%esp), %edx

次の4つのpushl命令によりスケジューラのコンテキストを保存します。

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

次に２つのmovl命令が続きます。

    movl %esp, (%eax)
    movl %edx, %esp

１つ目の命令movl %esp, (%eax)によりスケジューラのコンテキストを保存します。(実際はスケジューラのコンテキストの先頭を指すスタックポインタespの値を保存します。スケジューラのコンテキストの保存先は&(c->scheduler)で定まる特定のアドレスであり、このためにアンパサンドがついていました。)

２つ目の命令movl %edx, %espがコンテキストスイッチの肝です。今までスケジューラのスタックを指していたespをプロセスのスタックを指すようにします。つまり

スケジューラのカーネルスタック

から

プロセスのカーネルスタック

へとespが移動しました。

残りは下準備したinitのコンテキストへ切り替えるためpop命令を繰り返します。

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

４度のpoplによりespは次の位置まであがります。

ret命令により、eipに格納されているforkret関数ポインタをポップし、そこにジャンプします。 forkretはC言語の関数として定義されていますが、関数を抜ける際にスタックをポップし、 そこへとジャンプすることは変わりません。よってtrapret関数の関数ポインタがポップされ、関数の先頭へジャンプします。

trapret呼び出し直後

残るトラップフレームのポップはtrapretによって行われます。trapretは次のようなアセンブリで書かれています。

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

トラップフレーム内のレジスタに注目するため、一つ上に載せたカーネルスタックからトラップフレームの部分を拡大します。それは次のような図になります。今espはトラップフレームの最下部を指していることに注意してください。

まずpopalにより汎用レジスタを復元します。次の4つのpopl命令によりセグメントレジスタを復元します。そして次のaddl命令によりespを8バイト押し上げ、trapnoとerrcodeを無視します。最後のiretにより残るレジスタの復元を行います。具体的にはeip, cs, eflags, esp, ssが復元されます。特にeipとespの復元により、initcode（initプロセスの実行プログラム）のために格納した4096バイトの最下部と最上部を、それぞれeipとespが指すようになり、無事initcodeの実行が始まります。

参考文献

• xv6
  • https://github.com/mit-pdos/xv6-public
• book-rev11.pdf
  • https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf
• xv6実装の詳解(マルチタスク処理 switching編)
  • https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c

*1:https://ja.wikipedia.org/wiki/Init

*2:https://pdos.csail.mit.edu/6.828/2019/xv6.html

*3:本テーマと不要なメンバは省略しています