Zenn
🍴

自作OSにforkシステムコールを実装する

2024/04/04に公開
Linux
OS
#
自作os
#
低レイヤ
#
x64
tech

はじめに

自作しているOS（x64）にforkシステムコールを実装しました。
forkの概念は知っているものの、Linuxなどの有名なUNIX系OSのforkの実装をほぼ見ずに想像で作ったので、かなりオレオレな実装になっていると思いますが、実装していく中で学びが多かったのでまとめがてら紹介します。
https://github.com/junyaU/uchos

今回のゴール

今回の実装では、下記のプログラムの実行結果が以下のようになることを目標にしています。

sample.c
int main(void)
{
	int pid = sys_fork();

	if (pid == 0) {
		printf("Child process");
	} else {
		printf("Parent process, child pid = %d", pid);
	}

	exit(0);
}

実行結果

Parent process, child pid = 子プロセスのID
Child process

forkについて

実装の紹介をする前に、forkがどのようなシステムコールなのかについて軽く説明します。
わかる方は飛ばしてください。

Forkシステムコール
Forkシステムコール

forkは、現在実行中のプロセスを複製して新しいプロセスを作成するシステムコールです。
このシステムコールを呼び出したプロセスを「親プロセス」と呼び、複製された新しいプロセスは「子プロセス」と呼ばれます。複製されたプロセス（子プロセス）はメモリの状態を含む親プロセスの実行状態を完全にコピーしますが、プロセスIDはコピーされず新たに割り当てられます。

子プロセスの実行は、forkの呼び出し直後から開始されます。
親プロセスと同一のメモリ状態なので、fork呼び出し前に定義された変数などもそのまま利用可能です。

また、親プロセスと子プロセスではforkの返り値が異なります。親プロセス側ではforkの返り値として子プロセスのプロセスIDが返されます。一方、子プロセス側では0が返されるので、返り値からどちらの実行かを識別することができます。

次の例は、forkの戻り値を出力するプログラムです。

sample.c
int main(void)
{
	pid_t pid = fork();
	printf("process_id = %d\n", pid);
}

実行結果

process_id = 327819
process_id = 0

ここで、327819と出力されるのは親プロセスの実行結果であり、0が出力されるのは子プロセスからのものです。このようにforkの返り値によって、呼び出し元が親プロセスであるか子プロセスであるかを判断することができます。

forkは、子プロセスに別の処理をさせたり、exec系のシステムコールと組み合わせて新しいプログラムを起動する際など、多様な用途で活用されます。
これらの特性は、UNIX系オペレーティングシステムでのプログラム実行において、重要な役割を果たしているシステムコールと言えます。

実現するために必要なことを考える

私は、以下のような流れで実装をすればforkシステムコールを実現できそうだなと考えました。

  1. 新しいプロセスの作成: 子プロセスとなる新しいプロセスを作成する。
  2. コピー: 親プロセスのカーネルスタック、物理メモリ、実行コンテキストを子プロセスにコピーする。
  3. スケジューリング: 子プロセスが実行されるようにスケジューリングする。
  4. 戻り値の処理: 子プロセスからは0を、親プロセスからは子プロセスのIDを戻り値として返す。

自作OSでは、プロセスの作成や簡単なスケジューリング、マルチタスキングなどは既に実装済みなので、今回主に実装しなければならない部分は以下となっています。

  • 実行コンテキストのコピー
  • カーネルスタックのコピー
  • 物理メモリのコピー
  • 戻り値の処理

これらの実装の詳細や、詰まった部分などを次に詳しく紹介していきます。

実装

ここからは、自作OSでのforkシステムコールの具体的な実装について紹介します。実装されたsys_fork関数は、以下のように定義されています。

handler.cpp
task_t sys_fork(void)
{
	context current_ctx;
	__asm__ volatile("mov %%rdi, %0" : "=r"(current_ctx.rdi));
	get_current_context(&current_ctx);

	task* t = CURRENT_TASK;
	if (t->parent_id != -1) {
		return 0;
	}

	task* child = copy_task(t, &current_ctx);
	if (child == nullptr) {
		return ERR_FORK_FAILED;
	}

	schedule_task(child->id);

	return child->id;
}
task.cpp
task* copy_task(task* parent, context* parent_ctx)
{
	task* child = create_task(parent->name, 0, false);
	if (child == nullptr) {
		return nullptr;
	}
	child->parent_id = parent->id;

	memcpy(&child->ctx, parent_ctx, sizeof(context));

	if (IS_ERR(child->copy_parent_stack(*parent_ctx))) {
		printk(KERN_ERROR, "Failed to copy parent stack : %s", parent->name);
		return nullptr;
	}

	if (IS_ERR(child->copy_parent_page_table())) {
		prnitk(KERN_ERROR, "Failed to copy parent page table : %s", parent->name);
		return nullptr;
	}

	return child;
}

コンテキストのコピー

handler.cpp
context current_ctx;
// 1. RDIを取得しcurrent_ctxに格納する
__asm__ volatile("mov %%rdi, %0" : "=r"(current_ctx.rdi));
// 2. RDI以外の汎用レジスタ、RSP,RIPなどをcurrent_ctxに格納する
get_current_context(&current_ctx);
get_current_contextの実装
; System V AMD64 Calling Convention
; Registers(args): RDI, RSI, RDX, RCX, R8, R9
; Caller-saved registers: RAX, RDI, RSI, RDX, RCX, R8, R9, R10, R11
; Callee-saved registers: RBX, RBP, R12, R13, R14, R15

get_current_context:
    pushfq
    pop qword [rdi + 0x10] ; save RFLAGS

    mov [rdi + 0x40], rax
    mov [rdi + 0x48], rbx
    mov [rdi + 0x50], rcx
    mov [rdi + 0x58], rdx
    mov [rdi + 0x68], rsi
    mov [rdi + 0x70], rsp
    mov [rdi + 0x78], rbp
    mov [rdi + 0x80], r8
    mov [rdi + 0x88], r9
    mov [rdi + 0x90], r10
    mov [rdi + 0x98], r11
    mov [rdi + 0xa0], r12
    mov [rdi + 0xa8], r13
    mov [rdi + 0xb0], r14
    mov [rdi + 0xb8], r15
    fxsave [rsi + 0xC0] ; save FPU state

    mov rax, cr3
    mov [rdi + 0x00], rax
    mov rax, [rsp] ; save RIP
    mov [rdi + 0x08], rax
    lea rax, [rsp + 8] ; save stack pointer
    mov [rdi + 0x70], rax
    xor rax, rax
    mov ax, cs
    mov [rdi + 0x20], rax
    mov ax, ss
    mov [rdi + 0x28], rax
    mov ax, fs
    mov [rdi + 0x30], rax
    mov ax, gs
    mov [rdi + 0x38], rax

    ret

親プロセスと全く同じ状態を持った子プロセスを作り出すために、現在実行中のプロセス（親プロセス）の実行コンテキストを正確に取得し、この情報を子プロセスにコピーする必要があります。
実行コンテキストとは、プロセスの現在の実行状態を示すデータであり、主にCPUのレジスタの値から構成されます。このデータには、次に実行される命令のアドレス（プログラムカウンタ）、現在の関数呼び出しのスタック位置（スタックポインタ）、およびその他のレジスタ状態が含まれます。

上記のコードでは、以下の手順で現在のコンテキスト情報をcurrent_ctxに保存しています。

  1. RDIレジスタの値の保存: RDIレジスタは関数の第一引数の保存場所として使われる（System V AMD64 ABIの場合）。get_current_contextで第一引数を使用するので、元のRDIの値が上書きされてしまう。そのためRDIの値を先にcurrent_ctxに格納しておく必要がある。
  2. RDI以外のレジスタの値の保存: RDI以外のレジスタ、特にプログラムカウンタ（RIP）、スタックポインタ（RSP）、およびその他の汎用レジスタの値をcurrent_ctxに格納する。これによって、親プロセスの完全な実行状態がcurrent_ctxに保存される。
System V AMD64 ABIについて

System V AMD64 ABIは、x86-64アーキテクチャ向けのABIであり、Linuxをはじめとする多くのUNIX系OSで採用されています。
このABIにより、関数呼び出し時の引数の渡し方や戻り値の扱い方が標準化されており、以下のレジスタが引数の受け渡しに使用されます。

  • 第一引数: RDI
  • 第二引数: RSI
  • 第三引数: RDX
  • 第四引数: RCX
  • 第五引数: R8
  • 第六引数: R9

コンテキストの取得ができたら、それを子プロセスにコピーする必要があります。

task.cpp
// 現在実行中のプロセス
task* t = CURRENT_TASK;
if (t->parent_id != -1) {
    return 0;
}

task* child = copy_task(t, &current_ctx);
if (child == nullptr) {
    return ERR_FORK_FAILED;
}

このコードでは、まず現在実行中のプロセスが子プロセスであるかどうかをチェックしています。子プロセスの場合は0を返して終了させています。

親プロセスの場合はcopy_taskを呼び出して新しい子プロセスを作成します。この関数はプロセスの複製を行う関数であり今回の実装で重要な部分になります。引数には親プロセスと先ほど作成したcurrent_ctxを渡します。

task.cpp
task* copy_task(task* parent, context* parent_ctx)
{
        // プロセスの作成
	task* child = create_task(parent->name, 0, false);
	if (child == nullptr) {
		return nullptr;
	}

        // 親プロセスを設定
	child->parent_id = parent->id;

        // コンテキストのコピー
	memcpy(&child->ctx, parent_ctx, sizeof(context));

親プロセスのコンテキストを子プロセスにコピーします。これによって、子プロセスは親プロセスと同じ実行コンテキストを持つようになり、子プロセスの実行開始位置はget_current_contextの直後からになります。

カーネルスタックのコピー

task.cpp
error_t task::copy_parent_stack(const context& parent_ctx)
{
	task* parent = tasks[parent_id];
	if (parent == nullptr) {
		return ERR_NO_TASK;
	}

        // 1.親プロセスのスタックのデータを子プロセスにコピーする
	size_t parent_stack_size = parent->stack.size();
	stack.resize(parent_stack_size);
	memcpy(stack.data(), parent->stack.data(), parent_stack_size * sizeof(uint64_t));

        // 2. rspとrbpを計算し、設定する
        auto parent_stack_top = reinterpret_cast<uint64_t>(&parent->stack[parent_stack_size]);
	auto child_stack_top = reinterpret_cast<uint64_t>(&stack[parent_stack_size]);
	uint64_t rsp_offset = parent_stack_top - parent_ctx.rsp;
	uint64_t rbp_offset = parent_stack_top - parent_ctx.rbp;

	ctx.rsp = child_stack_top - rsp_offset;
	ctx.rbp = child_stack_top - rbp_offset;

	uint64_t kernel_sp_offset = parent_stack_top - parent->kernel_stack_ptr;
	kernel_stack_ptr = child_stack_top - kernel_sp_offset;

	return OK;
}

コンテキストのコピーを行った後、次に必要なのは子プロセスのカーネルスタックとそのポインタ（RSPとRBP）を適切に設定することです。
コンテキストのコピーにより、子プロセスは親プロセスのRSPとRBPの値を引き継ぐことになります。しかし、これをそのまま利用すると、子プロセスが親プロセスのカーネルスタックを使用することになってしまいます。これでは、両プロセスが同一のスタック領域で作業を行うことになり、予期せぬ動作やデータの競合が発生します。（実際動きませんでした）

なので、親プロセスと子プロセスを独立して安全に動作させるためには、それぞれが専用のカーネルスタックを用意しRSPとRBPを適切に設定する必要があります。

システムコールとカーネルスタックについて

システムコールが実行される際、CPUはユーザーモードからカーネルモードに切り替わり、カーネルがユーザープログラムに求められた処理を行います。このカーネル内での操作が行われる際に利用されるスタックが、カーネルスタックです。カーネルスタックは、プロセスごとに割り当てられた専用のスタックであり、プロセスが要求するシステムコールの処理を実行するために用いられます。

カーネルスタックはOSがシステムコールを処理する際に不可欠な要素であり、プロセスごとに独立したスタックを持つことで各プロセスのシステムコール処理を隔離して、システムの安定性とセキュリティを確保することができます。

上記のコードでは以下の手順で子プロセスのカーネルスタックの設定を行っています。
カーネルスタックのコピー
カーネルスタックのコピー

  1. スタックデータのコピー: 親プロセスのスタックデータを子プロセスのスタック領域にコピーする。これにより親プロセスのカーネルスタックと全く同じカーネルスタックが子プロセスに構築される。
  2. RSPとRBPの再計算: 親プロセスのスタック先頭からRSPとRBPのオフセットを計算し、それを子プロセスの先頭から引くことで、子プロセスのRSPとRBPを求める。

これで、親プロセスのカーネルスタックと同じ状態のカーネルスタックを作り出すことができました。

物理メモリのコピー

task.cpp
error_t task::copy_parent_page_table()
{
	task* parent = tasks[parent_id];
	if (parent == nullptr) {
		return ERR_NO_TASK;
	}

        // 1. オリジナルのページテーブルを保存
	parent->page_table_snapshot = reinterpret_cast<page_table_entry*>(parent->ctx.cr3);

        // 2. 親プロセスのページテーブルをオリジナルからコピーし、設定する
	page_table_entry* parent_table = clone_page_table(parent->page_table_snapshot, false);
	set_cr3(reinterpret_cast<uint64_t>(parent_table));

        // 3. 子プロセスのページテーブルをオリジナルからコピーし、設定する
	page_table_entry* child_table = clone_page_table(parent->page_table_snapshot, false);
	ctx.cr3 = reinterpret_cast<uint64_t>(child_table);

	return OK;
}

スタックのコピーをした後は親プロセスのメモリ空間のコピーを行います。これにより、子プロセスは親プロセスと同じ実行コード、データセグメント、ヒープなどのメモリ状態を持つことになります。コピーにはCoW(Copy on Write)という手法を使用しています。

CoWについて

CoWは物理メモリの遅延複製を可能にする技術です。子プロセスが親プロセスのメモリを直接コピーするのではなく、最初は親プロセスのメモリの参照を共有するようにします。これは親プロセスのページテーブルを子プロセスにコピーすることによって実現できます。
ページテーブルを複製する
ページテーブルを複製する
両プロセスは読み取り専用のメモリ領域（例えば実行コードなど）については、共有されたメモリをそのまま読み取ることができます。しかし、いずれかのプロセスでメモリに書き込み操作（データの更新など）が発生した場合、書き込み操作が発生した部分のメモリのみ複製され、その複製された新しい領域に書き込みが行われます。
書き込み発生時
書き込み発生時
メモリのコピーは処理時間がかかる上に、コピーされた領域が必ずしも全て使用されるわけではありません。CoWを利用することで、実際に必要とされるメモリ領域のみをコピーし、メモリコピーの処理時間を大幅に短縮することができます。

ページテーブルが何かについてはこの記事では触れません。
過去に軽く勉強したメモがあるので貼っておきます。
https://github.com/junyaU/os_study_memo/blob/master/paging/paging.md

ページテーブルの設定
ページテーブルの設定
上記のコードでは以下の手順で物理メモリコピー（CoW）の設定を行っています。

  1. オリジナルのページテーブルを保存する: 親プロセスの現在のページテーブルをオリジナルとして保存する。このオリジナルのページテーブルは直接使用せず、必要に応じてコピーを作成して利用する。
  2. 親プロセスのページテーブルの更新: オリジナルのページテーブルからCoWの設定を適用したコピーを作成し、これを親プロセスのページテーブルとして設定する。CR3レジスタは親プロセスのオリジナルを指しているのでコピーを指すようにしておく。
  3. 子プロセスのページテーブルの設定: オリジナルのページテーブルから同様にCoW設定を適用したコピーを作成し、これを子プロセスのページテーブルとして設定する。この手順により、子プロセスも親プロセスと同様のメモリ状態を持つことができる。

私ははじめ、親プロセスのページテーブルを直接コピーし、そのコピーを子プロセスのページテーブルとして適用していました。しかし、この方法ではプロセスは正常に動作しませんでした。
なぜなら、子プロセスが親プロセスのページテーブルを直接コピーしてしまうと、親プロセスが処理を進めることで発生するメモリデータの変更が子プロセス側にも影響を与えてしまうためです。両プロセスが干渉しあってしまい、意図しない動作を引き起こしてしまいます。

そのため、データ変更が行われる前の状態を示すオリジナルのページテーブルを保存しておき、そのコピーを親と子プロセスにそれぞれ適用しておくことで、プロセス間でメモリの変更が互いに影響を与えることなく、各プロセスが独立して動作するようになります。

clone_page_tableの中でCoWの設定を行っています。

CoWの実装について

処理の流れ

  1. 親プロセスのページテーブルを読み取り専用として複製する
  2. 子または親プロセスがページに書き込もうとすると、読み取り専用設定によりページフォルトが発生する
  3. ページフォルトのハンドラが動作し、フォルトが発生したアドレスに対応するページの複製を行う
  4. フォルトが発生したページを新しく複製したページに対応するように、ページテーブルを更新する。これにより、書き込み操作は複製したページに対して行われるようになる。
  5. ページフォルトの処理が完了すると、元の書き込み操作を続行することができる。

長くなりそうなので詳細は取り上げませんがコードをのリンクを貼っておきます。

フォルトハンドラ
https://github.com/junyaU/uchos/blob/master/kernel/interrupt/fault.hpp
ページテーブル周り
https://github.com/junyaU/uchos/blob/master/kernel/memory/paging.cpp

子プロセスのスケジューリングと実行

handler.cpp
task_t sys_fork(void)
{
	context current_ctx;
	memset(&current_ctx, 0, sizeof(context));
	get_current_context(&current_ctx);
        // 3. 子プロセスはここから再開される

	task* t = CURRENT_TASK;
	if (t->parent_id != -1 && strcmp(t->name, tasks[t->parent_id]->name) == 0) {
            // 4. forkの返り値を返す（子プロセス）
		return 0;
	}

	task* child = copy_task(t, &current_ctx);
	if (child == nullptr) {
		return ERR_FORK_FAILED;
	}

        // 1. 子プロセスをスケジューリングする
	schedule_task(child->id);

        // 2. forkの返り値を返す(親プロセス)
	return child->id;
}

copy_taskで子プロセスを作った後は、スケジューリングして子プロセスが実行されるようにし、それぞれのプロセスに別の返り値を渡す必要があります。

具体的な手順は以下になります。

  1. 子プロセスのスケジューリング: 子プロセスが正常に作成された後、子プロセスをスケジューリングする。これによって子プロセスが実行可能状態になり、CPU時間が割り当てられると子プロセスの実行が始まる。
  2. 親プロセスにforkの返り値を返す: 親プロセスは、子プロセスのIDを返り値として返し、自身の処理（fork後の処理）を継続する。
  3. 子プロセスの実行開始: 子プロセスは、get_current_contextで取得したコンテキストの状態で実行を開始する。これは、子プロセスがget_current_contextの呼び出し直後から実行を開始することを意味する。
  4. 子プロセスにforkの返り値を渡す: 子プロセスの返り値は0となる。

これでforkの処理は完了なので、先ほどのプログラムを自作OS上で動かしてみたいと思います。

サンプルプログラム実行の様子
サンプルプログラム実行の様子
期待通りの出力がされることが確認できました。（やったー☺）
とはいえ、エラーハンドリングを全然ちゃんとしていなかったり、ファイルディスクリプタやシグナルハンドラなどのコピーは一切考慮していなかったり...と課題が山積みの半端な実装なので、のんびり実装していきたいなと思います。

おわりに

forkシステムコールを自作OSに実装して、無事に動かすことができました。
（ページテーブル周りで詰まってしまい、forkの実装に１週間ほど費やしてしまいましたが...）
この実装を通して、プロセス複製の仕組みやメモリに対する解像度が上がったので良い勉強になりました。
次はexecファミリーのシステムコールを実装したい。

参考

https://www.shuwasystem.co.jp/book/9784798068718.html
https://book.mynavi.jp/ec/products/detail/id=121220

Discussion