自作OSにforkを実装する

技術記事を書こうとして5億年ぶりにQiita開いたらパスワード忘れて入れなくなった。
ちょうど最近、勝手にユーザーの閲覧履歴公開して批判されてたし、なんか戻すのも面倒になったのでこっちに書きます。

今回の内容は自作OSにforkのシステムコールを追加する話です。
なんでこんな記事を書いてるのかと言うと、就活用に以前書いたOSのソースコード整理してたら大量のTODOが出てきて、 いざTODOに取り掛かろうと思ったらコードに全くコメントが無くて読み解くのに5000兆年かかったからです。 メモ（コメント）は大事、はっきりわかんだね。

さて、今回実装するのはforkシステムコールです。
親プロセスから子プロセスが生成され、親プロセスは返り値として子プロセスのPIDを、子プロセスは返り値として0を受け取ります。よくよく考えたら不思議ですよね、システムコールを出す側としては、なんで同じプログラムを走らせてるのに返り値が変わったりするんだっていう気分です。実際私も最近まで理解してませんでしたが...


とりあえずforkシステムコールの本体となる関数を見ていきましょう。

int sys_fork(void)
{
    struct proc *np;
    struct proc *curproc = user.procp;

    if ((np = palloc()) == 0)
        goto bad;
    if ((np->pgdir = copyuvm(curproc->pgdir, curproc->size)) == 0)
        goto bad;

    np->size  = curproc->size;
    np->pproc = curproc;
    *np->tf   = *curproc->tf;

    np->tf->eax = 0;

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

    np->stat = RUN;

    return np->pid;

bad:
    if (np)
        pfree(np);
    return -1;
}

はい、記述量としてはこれだけなんですが、説明がないとなんのこっちゃですね。一つずつ解説していきましょう。

まず3行目のstruct procについて。これはプロセスを管理する構造体で、次のようになっています。（今回の解説に関係のないメンバ変数は省略しています）

enum procstat { UNUSED, SET, RUN, SLEEP, ZOMB, STOP };

struct proc {
    enum procstat stat;         /* process state */
    uint32_t pid;               /* unique process id */
    struct proc *pproc;         /* parent process */
    uint32_t size;              /* size of process */
    uint32_t *pgdir;            /* page directory */
    char *kstack;               /* kernel stack */
    struct trapframe *tf;       /* trap frame */
    struct context *context;    /* context switch */
    struct inode *cwd;          /* current directory */
    struct file *ofile[NOFILE]; /* open files */
} proc[NPROC];

それぞれのメンバ変数はまぁ...使われるときに解説しましょう（面倒になった）。OSではこの構造体の配列を管理しています。

さて、4行目ではuserという構造体が使われています。この構造体はOS上で"走っている"プロセスの情報を記録しています。 user.procpは現在CPUが割り当てられているプロセス構造体のポインタです。それをcurprocという変数に移しているわけですね。

どんどん行きましょう、と言いたいところですが、6行目ではpalloc()という関数を呼び出しているようです。 この関数はproc構造体の配列から未使用のエントリを取得して、初期化して返してくれます。

struct proc *palloc()
{
    struct proc *p = 0;
    char *sp;

    pushcli();

    for (int i = 0; i < NPROC; i++) {
        if (proc[i].stat == UNUSED) {
            p = &proc[i];
            memset(p, 0, sizeof(struct proc));
            break;
        }
    }

    if (p == 0 || (p->kstack = kalloc()) == 0) {
        popcli();
        return 0;
    }

    p->stat = SET;
    p->pid  = user.nextpid++;
    popcli();

    memset(p->kstack, 0, PAGESIZE);

    sp = p->kstack + STACKSIZE;
    sp -= sizeof(struct trapframe);
    p->tf = (struct trapframe *)sp;
    sp -= sizeof(struct context);
    p->context = (struct context *)sp;

    p->context->eip  = (uint32_t)trapret;
    p->tf->eflags    = FL_IF;
    p->tf->cs        = SEG_UCODE | DPL_USER;
    p->tf->ds        = SEG_UDATA | DPL_USER;
    p->tf->es        = p->tf->ds;
    p->tf->ss        = p->tf->ds;
    p->tf->eflags    = FL_IF;
    p->ofile[STDIN]  = fget(STDIN);
    p->ofile[STDOUT] = fget(STDOUT);

    return p;
}

面倒くさくなってきましたね...玉ねぎの皮のように剥いても剥いても中身が見えないですが、これも一つずつ説明していきましょう。ここからの話はx86のアーキテクチャに深く関係してきます。

palloc()の6行目ではpushcli()という関数が、17, 23行目ではpopcli()という関数が使用されています。これはx86における割り込み禁止命令cliをネスト可能にした関数です。
このOSではタイマ割り込みによるプロセスのスケジューリングが行われるため、プロセス構造体の配列などカーネル全体で共有する変数にアクセスする際は、割り込み禁止状態にしてタイマ割り込みを防ぐ必要があります。この場合cli命令を出して割り込み禁止状態にした後、禁止区間が終わったら割り込み許可命令stiで割り込みを許可します。
しかしここで面倒なのがこのcli命令はネストができないという点。例えばある関数f1, f2があり、どちらとも割り込み禁止状態で処理したい部分があったとします。ここでf1が割り込み禁止中にf2を呼び出した場合、cli@f1(割り込み禁止)→cli@f2(無意味)→sti@f2(割り込み許可)→sti@f1(無意味)という流れになってしまい、f2からf1に返った直後からf1でも割り込み許可状態になってしまうのです。これを解決するためにカーネル内でネスト用の変数を保持しておき、cli, sti命令をセットで使う限り何回呼び出しても大丈夫なようにしています。

早速話がそれました。palloc()の8～14行目ではプロセス構造体配列から未使用なエントリを取得します。
palloc()の16行目で呼び出しているkalloc()関数は、現在使用されていない4KB空間の物理メモリアドレスを返してくれます。 このkalloc()によって確保された領域を、このプロセスがカーネル権限で動くときに使うスタック領域として使用します。 カーネル権限で動くときに使うスタックってなんだよ（困惑）っていう人のために、もう少し詳しく説明します。
プロセスがユーザー空間で実行されている場合のスタックは、プログラマにとってはお馴染みのあのスタックです。 では例えば何かしらのシステムコールを発行したとしましょう。このシステムコールを処理する際に使われるスタックはユーザー空間に存在する、先程まで使用していたスタックではありません。x86では権限の昇格が発生した際にスタックが自動で切り替わります。（もしかしたら切り替わらない方法もあるかもしれない。詳しくないです、申し訳無い）
つまりシステムコールやタイマ割り込みなどでユーザー空間からカーネル空間に切り替わる際、スタックも自動的に切り替わります。

この自動的なスタックの切り替えには、セグメントディスクリプタにTSS (Task-State Segment)をセットする必要があります。 セグメントについて話し出すと、もう明後日の方向に飛んでいくのでやめておきます。私もあんまり詳しく理解してないのでボロを出したくないですし。 というか私もわからないので詳しい人教えて下さい何でもしますから！
一応自分の理解でざっくり説明すると、権限の昇格が発生した際にはこのTSSに昇格前のレジスタが記録され、SS0がスタックセグメントレジスタに、ESP0がスタックポインタ(%esp)にセットされるという認識です。今回ユーザー空間は ring 11, カーネル空間は ring 00でやってます。SS0, ESP0が読み込まれるのはring 00を使用しているからであり、ring 01に権限が昇格する場合はSS1, ESP1が、ring 10に昇格する場合はSS2, ESP2が読み込まれると思います。


TSSは多分セグメントディスクリプタへのセットの仕方次第ではタスクスイッチにも使えるのかもしれない、というかそっちが本業なのかも。 詳しく知りたい方は Intel Software Developer’s Manual Vol. 3A 7-3 ～ 7-9を読んでください。というかSDMには全てが書いてあります（読み切れる量だとは言ってない）



えーと、何を話していたんでしたっけ...そうだ、palloc()の16行目の解説をこれで終えました。 palloc()の21行目ではプロセスの確保が完了したため、ステートをSET（セッティング中）に変更します。 ステートを変更したらもうこのプロセス構造体のエントリはpalloc()による確保の対象外となるため、割り込み禁止を解除して良いでしょう。 あ、そうだ。一応pidも設定しておきます。次に使うべきpidもuser構造体が管理しています。

palloc()の27～31行目ではカーネルスタック上にstruct trapframeとstruct contextの領域を確保しています。 構造体の解説はこの後しますが、図にするとこんな感じです。スタックはアドレスの大きい方からアドレスの小さい方に伸びていくことに注意しましょう。 ちなみにPAGESIZEとSTACKSIZEは両方とも4KB(0x1000)です。
ところで「アドレス上位」と「アドレス下位」という単語わかりにくい...わかりにくくない？この図のようにメモリ番地を図示する際はアドレスが小さい方が"上に来る"ことが多いのに、"アドレス下位"って呼ぶんですよ。これ非常にややこしくなるので自分はこれ以降も「アドレスの大きい方」「アドレスの小さい方」で統一してます。アドレス上位下位は使うとしても論文などのフォーマルな場面のみにしてほしいものですね。

さて、続くpalloc()の33～39行目では先程カーネルスタック上に確保したstruct trapframeとstruct contextに値をセットしています。ここで構造体の宣言を見ていきましょう。

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

struct trapframe { /* sizeof (trapframe) = 76 */
    // registers as pushed by pushal
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t oesp; // useless & ignored
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;

    // rest of trap frame
    uint16_t gs;
    uint16_t padding1;
    uint16_t fs;
    uint16_t padding2;
    uint16_t es;
    uint16_t padding3;
    uint16_t ds;
    uint16_t padding4;
    uint32_t trapno;

    // below here defined by x86 hardware
    uint32_t err;
    uint32_t eip;
    uint16_t cs;
    uint16_t padding5;
    uint32_t eflags;

    // below here only when crossing rings, such as from user to kernel
    uint32_t esp;
    uint16_t ss;
    uint16_t padding6;
};

このstruct contextとstruct trapframeは基本的に割り込み時に使用される領域で、カーネル空間での処理やユーザー空間へ戻る際に使用します。 はい、というわけでここからx86の割り込みについてお話します。
先程、ユーザー空間からカーネル空間へ昇格する際にスタックが切り替わるという話をしました。ではプログラムカウンタはどうなっているのでしょうか。 x86ではIDT (Interrupt Descriptor Table)と呼ばれる領域に割り込みハンドラを登録することができます。CPUにはIDTR (Interrupt Descriptor Table Register)と呼ばれるレジスタがあり、 割り込みが発生した際、その割り込み番号に応じてIDT (テーブルと言われている様にディスクリプタの配列が並んでいる)に登録されたエントリを確認し、 エントリに記録された割り込みハンドラにジャンプします。

（補足）IDTではこの割り込みがユーザー空間から呼び出し可能かという設定(Descriptor Privilege Level)もできるので、システムコールの割り込みベクタのみring 11から受け付け、それ以外の割り込みはring 00のみから受け付けるみたいなのもできるはずです。間違ってたらごめんなさい。あと同じ割り込みでもtrapとinterruptという概念があって、trapはシステムコールなどで使われ割り込み処理時もEFLAGSのFL_IF(割り込み許可フラグ)がそのまま使われる一方でinterruptはIDEの割り込みやCPU内部割り込みなどFL_IF(割り込み許可フラグ)が降ろされた状態で割り込みハンドラにジャンプします。詳しくはIntel SDM Vol.3A 6-xやwikipediaのCPUの割り込みとか見てください。あと本当はセグメントディスクリプタと掛け合わせてアドレスが算出されたりするんですが、今回セグメントディスクリプタは全アドレスを1つとして実質使用していないので説明を省いてます。

えーっと、もう少し割り込みの説明が続きます。さっきのはx86における割り込み処理についてですが、これだけだとstruct trapframeやstruct contextの意味がわかりませんよね。 はい、これら構造体はOS内部で作り出すもの（？）なので、もうちょっと説明が続きます。我慢してね。
先程、IDTに割り込みハンドラを登録すると説明しました。では今回のOSではどのような関数が登録されているか説明しましょう。

.globl alltraps
.globl vector0
vector0:
    pushl $0
    pushl $0
    jmp alltraps
.globl vector1
vector1:
    pushl $0
    pushl $1
    jmp alltraps
.globl vector2
vector2:
    pushl $0
    pushl $2
    jmp alltraps
.globl vector3
    ...

はい、今回は割り込み番号Nに対してvectorNという関数(？)を用意し、割り込みが入ったらエラーコードと割り込み番号をスタックにプッシュして、全ての割り込みを同じハンドラで処理します。直接ハンドラとなる関数を登録するのもありだと思いますが、個人的にはこっちのほうが管理しやすいと感じますね。あと補足ですが、割り込みによってエラーコードをプッシュするものとしないものがある（8, 10~14, 17番の割り込みはエラーコードが付いてくる。by SDM Vol.3A 6-2）ので気を付けましょう。この実装ではエラーコードがない場合、0をプッシュしてスタックの状態を均一にしています。
さて、次は各割り込みハンドラがジャンプするalltrapsを見てみましょう。

.globl alltraps
alltraps:
    # Build trap frame.
    pushl %ds
    pushl %es
    pushl %fs
    pushl %gs
    pushal
  
    # Set up data segments.
    movw $SEG_KDATA, %ax
    movw %ax, %ds
    movw %ax, %es

    # Call trap(tf), where tf=%esp
    pushl %esp
    call trap
    addl $4, %esp

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

はい、ここでstruct trapframeの形成をしています。struct trapframeの定義を確認すると
1. 権限の昇格が発生した際に積まれるレジスタ群 (esp, ss)
2. x86アーキテクチャの設計上必ず積まれることになるレジスタ群 (eflags, cs, eip err(一部))
3. 割り込みハンドラvectorNで積まれる割り込み番号 (trapno, err(2で積まれなかった場合))
4. alltrapsで積まれるセグメントレジスタ群 (ds, es, fs, gs) と汎用レジスタ (pushalで積まれるもの)
の順番になっていることが確認できます。

さて、alltrapsの14行目時点ではカーネルスタック上にstruct trapframeが形成されていることがわかりました。ちなみにこの構造体を示すポインタは現在のスタックポインタです。 そのためスタックポインタをプッシュしてtrap関数を呼び出すことで、C言語側ではtrap(struct trapframe *tf)として関数を作成することができます。
ここでtrap関数の説明を...してるともう永遠に終わらないので流石にやめておきましょうか。trap関数内では引数にとったstruct trapframeの値に応じて様々な処理をしています。





・・・これforkの解説記事だよね？
えーっと、とりあえずシステムコールの場合のtrapの処理だけ軽く解説します。 ユーザー空間からシステムコールを呼び出す際は、システムコール番号をeaxに入れてint T_SYSCALL(64)でソフトウェア割り込みを発生させています。

void trap(struct trapframe *tf)
{
    if (tf->trapno == T_SYSCALL) {
        memmove(tf, user.procp->tf, sizeof(struct trapframe));
        tf->eax = syscall(tf->eax);
        return;
    }
    ...

ここのmemmove()はシステムコール中にuser構造体からstruct trapframeが触れた方が便利だったから入れてます。 まぁそこは重要じゃなくて、大事なのはシステムコールの返り値をtf->eaxに入れている点です。 x86におけるeaxは特別なレジスタで、関数の返り値を入れる際に使用されることが多いです。（あと演算速度も早いらしい）

ここでtf->eaxにセットされた値はalltrapsのcall trap終了後、trapretにてポップされます。 trapretではalltrapsで積み上げたレジスタ群を全て復元し、iret命令で割り込みからのリターンを行っています。

自分がシステムコールという関数を呼び出したと思い込んでいる一般ユーザー空間くんですが、実際にはシステムコールの割り込み要求が出されていて、その割り込みハンドラからシステムコールがカーネル内で実行されているわけですね。このカーネル内の処理が終わったらカーネルはシステムコールの返り値をさりげなくeaxにセットすることで、何も知らないユーザー空間くんはあたかも関数を呼び出したかのように錯覚するわけです。ここが一番言いたかった。ここがforkを理解する上で一番重要です。


さて、palloc()に戻りましょう。 palloc()ではstruct contextのプログラムカウンタeipにtrapretのアドレスを入れていますね。これはどういうことでしょうか？
答えは簡単で、本来であればstruct trapframeはalltrapsによって形成されるのですが、palloc()内部で新しく確保したプロセス構造体に、擬似的なstruct trapframeを生成して直接trapretにジャンプするとあら不思議、新しいプロセスの誕生です。


え、struct contextの説明が入ってないからなんでcontext->eipにtrapret入れただけでtrapretにジャンプするかわからない？しょうがねぇな...
struct contextはプロセスを切り替える時のみに使用する構造体です。プロセスの切り替えはsleep()などにより自主的に行われる場合もあれば、タイマ割り込みなどで強制的に行われる場合もあります。どっちにしろカーネルではsched()関数が呼び出され、次に実行されるプロセスとの切り替えが行われます。

void sched()
{
    /* 次に実行するプロセスを決める */

    /* メモリ空間を切り替える */

    swtch(&oldproc->context, newproc->context);
}

.globl swtch
swtch:
    movl 4(%esp), %eax
    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

ちなみに今回カーネル空間は共有しているのでカーネルのコードを書く上では気にしなくていいです。そのため、プロセスの切り替えはカーネルスタックの切り替えだけで十分です。
なぜなら最後のret命令ではスタック上に保存されたsched()を呼び出した際のリターンアドレスへジャンプするからです。 そして先程述べたcontext->eipというのは、まさにこのリターンアドレスを示しています。
要するにpalloc()で確保したプロセスのcontext->eipにtrapretを入れておけば、新しく確保されたこのプロセスがsched()により実行される際、swtch()関数から直接trapretにリターンし、擬似的に生成されたstruct trapframeからユーザー空間を構築してくれるというわけです。当然このstruct trapframeのeipにアドレスを入れておけば、そのアドレスからユーザー空間が再開されるので、execvを実装する際にはここにELFのエントリーアドレスを入れたりするわけです。今回はforkなのでしませんが。

長かったですね...pallocの説明はこれで終わりです。一応最後にstdinとstdoutのファイル構造体を開いていますが、これについてはまた今度説明しましょう。少なくとも私はもう書き疲れました。


多分もう戻って確認するのも面倒だと思うので、もう一度sys_fork()を貼っておきましょう

int sys_fork(void)
{
    struct proc *np;
    struct proc *curproc = user.procp;

    if ((np = palloc()) == 0)
        goto bad;
    if ((np->pgdir = copyuvm(curproc->pgdir, curproc->size)) == 0)
        goto bad;

    np->size  = curproc->size;
    np->pproc = curproc;
    *np->tf   = *curproc->tf;

    np->tf->eax = 0;

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

    np->stat = RUN;

    return np->pid;

bad:
    if (np)
        pfree(np);
    return -1;
}

まだ6行目ってマジ？

copyuvm()については次回説明することにしましょう。次回はexecvを説明する予定です。次回も何もこの2つしか説明する予定はないのですが・・・
ここでは簡単に全てのメモリ空間をコピーする関数とだけ伝えておきます。要するに親プロセスのメモリ空間を新しく確保したプロセスに全部コピーするわけですね。

はい次行きましょう次。11, 12行目のサイズや親プロセスの登録は飛ばして良いでしょう。大事なのは13行目のstruct trapframeのコピーですね。 先程カーネル空間からユーザー空間に戻る際、struct trapframeから全てが復元されるという話をしました。これを完全にコピーするということは、メモリ空間だけでなく 現在のユーザー空間における実行アドレスやレジスタの値も完全にコピーするということです。まさにforkの真髄ですね。


15行目。ここが今回の記事で一番伝えたかった場所です。このsys_fork()の返り値は新プロセスのPIDですが、これは親プロセス（forkシステムコールを呼び出したプロセス）のtrapframe->eaxに保存されます。これによって親プロセスはシステムコールという「関数」からの返り値として子プロセスのPIDを受け取るわけです。
ですが子プロセスは返り値として0を受け取りますよね。それはまさにこの一行によるものです。子プロセスは親プロセスのメモリ空間やstruct trapframeなど全てをコピーしてきましたが、唯一、trapframe->eaxだけ親プロセスと異なるのです。そしてこれはシステムコールの返り値として使用されるのです。これだけは伝えたかった。満足です。

まぁ後は流れで、現在開いてるファイルやカレントディレクトリの参照数をインクリメントしたりしてます。

最後、子プロセスの全設定が終わったら状態をSET(セット中)からRUN(実行可能状態)に変更することで、sched()関数の選択対象となりました。 親プロセスは子プロセスのPIDを受け取り、子プロセスはいつかsched()によって実行された際には親プロセスと同じ場所から始まるものの、唯一システムコールの返り値だけが違うという状況になりましたとさ。めでたしめでたし。