過ぎるだけの時間じゃ悔しい

OSカーネルの基礎

Properties2
tagsos, kernel, os/xv6, paging, virtual-memory, mmu, x86-64, allocator, memory, slab, buddy, baremetal, rust, linux, process, signal, syscall, unix, computation/concurrent, os/linux, interrupts, exceptions, low-level, blog-os
aliasesvirtual-memory-mapping-strategies, slab-and-buddy-allocation, linux-signals-and-process-control, inter-process-communication, x86-interrupt-handling

15 min read

OSカーネルの基礎

ハードウェアを抽象化し、プロセスを保護・スケジュールする中核ソフトウェア。学習用OS xv6 を題材に基本機構を整理する。

保護と特権モード

  • kernel mode / user mode を分け、メモリ確保・ファイルR/W・I/Oなどは特権命令が必要なため kernel mode で実行する。
  • ユーザ↔カーネルの遷移は割り込み・例外で起こる。
    • interrupt: 外部イベント(キーボード、ネットワーク、タイマ)。
    • fault: プログラムの異常(不正メモリアクセス、0除算)。
    • trap: 明示的なプログラム動作(システムコール)。
    • abort: ハードウェア故障。
  • iret でユーザモードに戻る。

システムコールと割り込み

  • xv6 では int $0x40 で割り込みを起こし、eax にシステムコール番号を入れて呼ぶ。
  • 起動時に lidt で割り込み記述子テーブル(IDT)を設定し、SETGATE で各割り込みタイプのハンドラを登録する。
  • trap() が trapno を見て syscall() や exit() に振り分け、関数ポインタテーブルで個別のシステムコールへ分岐する。

メモリとコンテキストスイッチ

  • カーネルは高位アドレス(KERNBASE 以上)、ユーザは低位。プロセスごとに1つのカーネルスタックを持つ。
  • タイマ割り込みで yield() が走り、swtch() がレジスタ(context 構造体)を保存・復元してスレッド/アドレス空間を切り替える。

I/Oとシステム機能

  • mmap: ファイル↔メモリのマッピング、operating-system-kernel にも使う syscall。
  • io_uring: Linux の非同期I/O API(epoll の後継的存在)。
  • eBPF: カーネル内で安全に特定処理を走らせる仕組み(トレーシング等)。
  • systemd: .service ユニットでデーモンを管理(linux)。
  • VGA テキストバッファ(0xb8000)は自作OSの定番出力先。
  • Redox のようにファイルシステムやドライバを Scheme(URLスキーム)としてユーザランドで実装するマイクロカーネル設計もある。
  • RAID: ストレージの冗長化(0:ストライピング、1:ミラーリング、5:パリティ分散)。

関連: _moc-systems / elf-format / virtualization-hypervisor / xv6

仮想メモリのマッピング戦略 (恒等/固定オフセット/全物理/再帰)

カーネルが「物理メモリ上のページテーブルそのもの」へどうアクセスするか、という仮想アドレス空間レイアウトの設計問題。[[concepts/xv6-paging]](xv6 固有)と [[concepts/blog-os-rust-kernel]] から共通する一般論を抽出。

前提: 多段ページテーブル

  • x86-64 は 64bit VA を [48..=40]=L4, [39..=31]=L3, [30..=22]=L2, [21..=12]=L1, [11..=0]=offset に分解(上位はサインエクステンション)。512エントリ×4段。
    • 1ページ=4KB=12bit、1エントリ=64bit なので 1テーブルあたり 2^(12+3)/2^6 = 9bit のインデックス。
    • xv6 は 4096エントリ×2段([[concepts/xv6-paging]])。
  • VA→PA 変換は各段のテーブルを辿るだけ。x86_64::structures::paging::Translate::translate_addr 相当。PhysFrame がページに対応する物理領域。
  • TLB: 変換結果のキャッシュ(transparent: 利用者は存在を意識しない)。カーネルがページテーブルを書き換えたら invlpg で TLB をフラッシュする。GLOBAL フラグ付きエントリはアドレス空間切替でもフラッシュされない。
  • [[concepts/operating-system-kernel]] の page fault はこの変換失敗で起きる。

マッピング戦略

カーネルがページテーブル(物理アドレス)を操作するには、その物理アドレスを指す仮想アドレスが要る。方式の比較:

  1. 恒等マッピング (identity): VA = PA。実装は単純だが、ページテーブルが物理メモリ中に散在すると仮想アドレス空間が散らかる。
  2. 固定オフセットのマッピング: VA = PA + 定数オフセット。xv6 はこの方式。オフセットをページテーブル毎に変えれば断片化を抑えられる。
  3. 物理メモリ全体をマップ: 物理メモリ全域を連続した仮想領域に張る。x86-64 の 2MiB huge page(HUGE_PAGE フラグ, L2/L3 で許可)を使えば安価。例: 32GiB を L3×1, L2×32 で覆い、132KiB のテーブル占有で済む。
  4. 一時的オフセット: (L4,L3,L2)=(0,0,0) は L1 テーブル全体(2MiB)の恒等マッピングと等価。そこのエントリの Frame に書き込むことで一時マッピングを511個作れる。
  5. 再帰的ページテーブル (recursive): 同一段のエントリが自テーブルを指すことを許すと、アクセス回数で任意段のテーブルを操作できる。x86 のページテーブル方式に強く依存する技巧。

ページテーブルエントリのフラグ

PageTableFlags(下位フラグ群): PRESENT(メモリ常駐), WRITABLE(書込可。L1 で落とすと read-only), USER_ACCESSIBLE(ring3 許可), WRITE_THROUGH/NO_CACHE(キャッシュ方針), ACCESSED/DIRTY(CPU が自動セット), HUGE_PAGE, GLOBAL, NO_EXECUTE(bit63, EFER で有効化時)。

ブートローダ([[entities/rust-osdev-tooling]])が起動時に既にページングを設定済みのため、カーネルは bootloader を修正してテーブルを書き換える必要がある。

関連

  • [[concepts/operating-system-kernel]] / [[concepts/malloc-allocator-internals]](ヒープの mmap)。

Slab / Buddy アロケーション (ベアメタルのヒープ管理)

OS やベアメタル環境([[concepts/bare-metal-rust-freestanding]])で、固定サイズブロックを高速に確保・解放するためのヒープ管理アルゴリズム。[[entities/redox-slab-allocator]] の Rust 実装を一般化した概念ページ。汎用の [[concepts/malloc-allocator-internals]](可変サイズ glibc malloc)とは設計思想が異なる。

Slab allocation

大きなメモリ領域を特定サイズの固定ブロックに切り分けて管理する方式(slab = 厚切り)。手順:

  1. 大きなメモリ領域を確保する。
  2. 領域を一定サイズのブロックに分割する(例: 4KB を 64byte×64個 = slab_64_bytes)。
  3. allocate で適切なサイズのブロックを割り当てる。
  4. dealloc で再利用可能リストへ戻す。

固定サイズなので alloc/dealloc が O(1)、かつ同一サイズだけ扱うので外部断片化が起きない。core::alloc::Layout(size, power-of-two な align)から適切な slab サイズを選ぶ。

FreeBlockList のトリック

未使用ブロック自体を管理情報の置き場に流用する。64byte の slab なら、空きブロック先頭 8byte に next: Option<&'static mut FreeBlock> を埋め込んで連結リスト(intrusive list)を作り、残り 56byte は空けておく。誰にも割り当てていない領域なのでアロケータが内部利用してよい。Rust の null pointer optimization により Option<&mut T> はポインタ1個分のサイズで表現される。

Buddy allocation

可変サイズ要求に対応するため、領域を2の冪で再帰分割する古典手法(1960年代〜)。要求サイズ以上の最小の2冪ブロックに分割し、解放時に相棒(buddy)ブロックと再併合する。slab より細やかにサイズへ追従できる。実装では空きブロック探索に de Bruijn 列で BSR(最上位ビット)を O(1) 算出する技法が使える。

ベアメタル実装の注意

  • #[global_allocator] に core::alloc::GlobalAlloc 実装を登録すると Box/Vec が使える。core::alloc と alloc::alloc の使い分けに注意。
  • 並行アクセスは spin-lock(busy-wait, spin crate)で守る。内部可変は UnsafeCell::get(): *mut T。
  • ヒープ初期化 init_heap() では確保すべき物理領域の場所を自分で知る必要がある(std が無いので)。デバッグは print も使えず syscall 頼み。
  • Rust デフォルトのグローバルアロケータは jemalloc(現在は system allocator)だが、ベアメタルでは誰も面倒を見ないので自力管理する。

関連

  • スレッドセーフ化のための per-thread arena は [[concepts/malloc-allocator-internals]]。
  • [[concepts/operating-system-kernel]] / [[concepts/operating-system-kernel]]。

Linux のシグナルとプロセス制御 (fork/exec/wait/signal)

ptrace ベースのトレーサ/デバッガ([[concepts/ptrace-syscall-tracing]])を作る土台となる、UNIX プロセス・シグナルの基礎。『ptrace入門』(Yoshihiro Oyama)第1章から抽出。

プロセス生成と置換

  • fork: プロセスを複製。返り値で分岐する(子は 0、親は子の pid > 0)。getpid()/getppid()。
  • clone: fork より細かく引き継ぎ(アドレス空間・FD 等)を制御できる。スレッド生成の基盤。
  • execve: 現プロセス上で新しいプログラムをロードして実行。成功すると戻ってこない(失敗時のみ続行)。新プロセスにはならず、イメージが置換される。CTF の任意コード実行でも使う。exec 系 wrapper: execl/execlp/execle …
  • wait: 親が子の状態変化(停止/終了)に同期する。
  • syscall の上にライブラリ関数の層がある(例: printf → write syscall)。

典型パターン(トレーサ): fork → 子が PTRACE_TRACEME → 子が execve → 子が syscall で SIGTRAP 停止 → 親が wait → 親が reg/mem を r/w → 親が再開。

シグナル

プロセスに送られる非同期の信号。kill syscall で送る(例 kill(2384, SIGSTOP))。SEGV 時は OS が SIGSEGV を送る。他ユーザのプロセスには送れない(operation not permitted)。

主要シグナル:

  • SIGINT = 2(^C)、SIGTERM(終了要求、ハンドラ変更可)。
  • SIGKILL = 9: 強制終了。ハンドラ変更/捕捉不可(全ハンドラを潰しても KILL では止められる)。
  • SIGSTOP: 停止、ハンドラ変更不可。SIGTSTP: 端末由来の一時停止、変更可。SIGCONT: 再開。
  • SIGTRAP: トレースイベントによる実行中断。ptrace/デバッガの中核。

シグナルハンドラ

  • sigaction でハンドラを差し替える。デフォルト処理がある。
  • async-signal-safe: ハンドラから安全に呼べる関数は限られる。ハンドラ内での I/O や longjmp は原則 NG(signal-safety(7))。再入可能性の問題。

ps の STAT

S=sleep, t=デバッガにより停止(T stopped), Z=zombie(親と切れた)。トレース中の子は t で観測できる。

関連

  • これらを使って syscall をトレース/サンドボックス/デバッグするのが [[concepts/ptrace-syscall-tracing]]。
  • 現代的代替は [[entities/redox-slab-allocator]] 文脈の話ではなく eBPF。[[concepts/operating-system-kernel]] も参照。

プロセス間通信(IPC)

独立したプロセス間でデータをやり取り・同期するための機構の総称。共有資源を扱う並列処理(parallel-computing)と密接に関わる。

主な手段

  • ファイル: 最も素朴な共有。
  • シグナル(linux signal): 非同期通知。
  • メッセージキュー: OSごとに実装が異なる。
  • ソケット: ネットワーク経由を含む。WebSocket もこの系列。
  • unix pipe: シェルの ls | grep のようなパイプライン。伝統的にコピーが発生し遅いが、Linux の splice システムコールと hugepage を併用するとコピーなしで転送でき高速化できる。
  • セマフォ: 共有資源へのアクセスを制御する同期プリミティブ(デザインパターン的に使う)。
  • 共有メモリ / メモリマップドファイル: mmap でメモリ上にファイルとして共有。
  • メッセージパッシング: MPI などのインターフェース。通信方法は規定せず(デフォルトはソケット)。

メッセージング指向のモデル

  • MPSC (Multi-producer, single consumer): チャネルベースのメッセージングモデル。rust-lang では std::sync::mpsc や tokio の mpsc で利用する。送信機(tx)/受信機(rx)でデータを受け渡す。
  • 上位の RPC として gRPC があり、k8s と組み合わせた分散処理でも使われる。

関連トピック

関連: _moc-systems / parallel-computing

x86-64 割り込み・例外処理 (IDT / GDT / TSS / double fault)

x86-64 CPU が例外・割り込みを受けたときの制御移行の仕組み。[[concepts/blog-os-rust-kernel]] の CPU 例外章の核を抽出した概念ページ。[[concepts/bare-metal-rust-freestanding]] の上で実装する。

例外の分類

割り込みで例外ハンドラを呼ぶ。x86 には約20種類の例外があり、代表例:

  • page fault: 未マップ/権限違反のメモリアクセス。[[concepts/operating-system-kernel]] と直結。
  • invalid opcode, general protection fault(アクセス違反系)。
  • double fault: 例外ハンドラ実行中の例外、またはハンドラ未登録時に発生。
  • triple fault: double fault ハンドラ処理中に更に例外 → 致命的(CPU リセット/再起動ループ)。ハンドラ未登録だと page fault → double fault → triple fault と連鎖し、QEMU が boot ループでチカチカする。

IDT (Interrupt Descriptor Table)

  • CPU に IDT を登録しておくと、例外番号に対応するエントリのハンドラへ自動でジャンプする。
  • 例外発生時の流れ: 命令ポインタ(rip)と RFLAGS をスタックに push → IDT エントリを参照 → 割り込みゲートならハードウェア割り込みを無効化 → 指定 GDT セレクタを CS にロード → ハンドラへ jmp。

x86-interrupt 呼出規約

  • 例外は関数呼び出しに似るが「いつでも発生しうる」点が異なる。通常の呼出規約では scratch(caller-saved)レジスタ が破壊される前提だが、例外は任意命令間で割り込むため caller 側に退避コードが無い。
  • そこで extern "x86-interrupt" を付けると、上書きされる全レジスタ(preserved/scratch 両方)を自動でバックアップ・復元するコードが生成される。
  • 割り込みスタックフレーム: sp を16バイトアラインし、旧 sp / RFLAGS / rip / cs / (あれば)エラーコードを push してからハンドラを呼ぶ。x86-interrupt がこの一連を隠蔽する。
  • int3 (= 0xcc) はブレークポイント例外を発生させ、デバッガの一時停止に使われる。[[concepts/ptrace-syscall-tracing]] の breakpoint セットと同根。

GDT / TSS / IST によるスタックオーバーフロー対策

  • ガードページ(スタック底の特別なページ)でスタックオーバーフローを page fault として検出。だが割り込みスタックフレームを壊れたスタックに push しようとして失敗 → double → triple fault になる。
  • 解決: IST (Interrupt Stack Table) — 例外専用スタック(最大7本)の sp 配列を用意し、特定例外は別スタックに切り替えて処理する。
  • TSS (Task State Segment): 64bit ではタスク固有情報を持たなくなり、特権スタックテーブルと IST の2つを保持する構造体。IST は TSS の一部。
  • GDT (Global Descriptor Table): 歴史的にはセグメンテーション用だが、64bit でも kernel/user モード設定と TSS ロードのために必要。CPU へ教える手順は CS 再ロード → load_tss → IDT エントリ更新(double_fault に IST index を割当)。

関連

  • 実装支援 crate x86_64 / bootloader は [[entities/rust-osdev-tooling]]。
  • ページング各論は [[concepts/xv6-paging]] / [[concepts/operating-system-kernel]]。

Graph View

Backlinks