Zenn
Closed31

Rustで自作OS - マルチタスキング、コンソール、ブロックデバイス、ファイルシステム

yubrotyubrot

しばらくxv6の実装を追ったりLinuxのデザインを追ったりで間が空いてしまった。また、orsの実装もMikanOS書の流れからだいぶ離れたものになった。コミットを振り返りつつ備忘録としていく。

yubrotyubrot

13章 マルチタスク (1), 14章 マルチタスク (2)

MikanOSではマルチコアをサポートしないが、実際にはコア依存な状態をグローバルに持っていたり、競合回避のための実装をシングルコア前提にしていたりする部分がどこにあるのか気になってしまうので、Symmetric Multiprocessing (SMP) をサポートしているxv6の実装を参考に、はじめからマルチコアを意識した実装にすることにした。手始めに、xv6に倣ってCPUローカルな状態を持てるようにする。

https://github.com/yubrot/ors/commit/7112fa5ddf67e2819b7c6dc04009ad8c2c12ecdc

xv6では実装の各所に struct cpu* mycpu(void) の呼び出しがある。この構造体 struct cpu がプロセッサごとの状態を表現している。

xv6では各コアをどのように区別しているかというと、Local APIC registersからLAPIC IDを読むことで区別していた。メモリマップドI/Oなので単に特定のアドレスの値を読み出す実装になるが、Local APICはコアごと内臓されており、それぞれのコアで固有な値が得られる。orsでもこれに倣って、cpuクレートを設け、 Cpu::current().info() で現在のプロセッサ上での状態を持てるようにした。

このコミットには cpu::initialize の呼び出しが含まれないが、初期化に必要なシステムのプロセッサの数、各プロセッサのLocal APIC IDなどの情報はこれまでの実装で既に得ている。前章でacpiクレートを用いて得られた PlatformInfoのprocessor_infoに含まれる。

別の方法としては、今ではほぼ使われないセグメントレジスタを用いる方法もあるようだ。

yubrotyubrot

https://zenn.dev/link/comments/8710d30d5a3da6

上のスクラップでも触れたが、マルチコア対応も視野に入れて再び排他制御について考え直す。

  • シングルコア前提では割り込みを無効にすれば済んでいたところ、マルチコアでは別のコアからも同じリソースにアクセスされるので排他制御が必要になる。
  • 単にスピンロックを排他制御に用いると、割り込みによってリソースのロックを獲得したまま制御が移ることで容易にデッドロックを引き起こしてしまう。

考慮しなければならない範囲が特定の割り込みハンドラ群のみであれば、それらのハンドラから触れるリソースについてだけ考えれば良かった。しかしこれから実装するコンテキストスイッチも含めると、考慮しなければならない範囲が広く、割り込みの有効/無効とスピンロックを個別に管理するのは非常に難しい。ということで、xv6に倣って以下の仕組みをRustで扱いやすい形で実装することにした:

  • カウンタベースのCLI (割り込みの無効化)
  • 割り込みの無効化を伴うスピンロック
yubrotyubrot

カウンタベースのCLI (Clear Interrupt Flag, 割り込みの無効化)

xv6には pushcli popcli という関数があり、 push した回数だけ pop されるまで割り込みが無効化される。これと似たような仕組みを実装する。なお、x86_64クレートにはwithout_interruptsという似たようなユーティリティが存在するが、クロージャによるスコープベースだと扱いづらいのでRAIIで表現することにした。

use  x86_64::instructions::interrupts;

pub struct Cli;

impl Cli {
    pub fn new() -> Self {
        let cli = !interrupts::are_enabled();
        interrupts::disable();
        let mut cpu = Cpu::current().info().lock();
        if cpu.ncli == 0 {
            cpu.zcli = cli;
        }
        cpu.ncli += 1;
        Self
    }
}

impl Drop for Cli {
    fn drop(&mut self) {
        assert!(!interrupts::are_enabled(), "Inconsistent interrupt flag");
        let mut cpu = Cpu::current().info().lock();
        cpu.ncli -= 1;
        let sti = cpu.ncli == 0 && !cpu.zcli;
        drop(cpu);
        if sti {
            interrupts::enable();
        }
    }
}

割り込みの有効/無効はコアごとなので、上で用意したCPUごとの状態を活用している。

  • Cli が作られたときに cpu.ncli をインクリメントする
    • このとき、他に Cli の値が存在しない (cpu.ncli == 0) 状態だったときは cpu.zcli にもともと割り込みが無効化されていたかを保持しておく
  • Cli がDropされるときに cpu.ncli をデクリメントする
    • Cli の値が存在しない状態となるとき (cpu.ncli == 0) は cpu.zcli に基づいて元々の割り込みフラグの状態を復元する

Cpu::current().info() 自体はスピンロックを用いて排他制御している。他のコアからはアクセスできないようにする (完全にCPUローカルにする) ならばロックは不要で (Aliasingに気を付ける必要はありそう)、xv6はそのように実装されているが、orsではとりあえずロックしている。

yubrotyubrot

割り込みの無効化を伴うスピンロック

https://github.com/yubrot/ors/commit/371f64d4b2c61882e22638f78b5db5a6c2eaea06

このカーネルの実装のための Mutex<T>, MutexGuard<'a, T> を用意した。ほとんどspinクレートの Mutex, MutexGuard のラッパーだが、 スピンロックを獲得する前に Cli を獲得して (割り込みを無効化して)、 MutexGuard<T> に Cli を保持させることでロックを獲得している間は割り込みが無効となるようにする。The Rust ReferenceのDestructorsによると

The fields of a struct are dropped in declaration order.

とのことなので、MutexGuardの宣言では最後にCliがDropされるように並べる。

pub struct MutexGuard<'a, T> {
    inner: spin::MutexGuard<'a, T>,
    cli: Cli,
}

この Mutex を排他制御が必要な各種リソースに用いることで、リソースの排他制御に関して、マスク可能な外部割り込みについて考慮する必要はなくなる。一方、これらリソース自体はコンテキストスイッチング等で引き続き考慮することになる。

yubrotyubrot

コンテキストスイッチ

コンテキストスイッチ (context switch) とは、複数のプロセスが1つのCPUを共有できるように、CPUの状態(コンテキスト (情報工学))を保存したり復元したりする過程のことである。コンテキストスイッチはマルチタスクオペレーティングシステムに不可欠な機能である。通常コンテキストスイッチは多くの計算機処理を必要とするため、オペレーティングシステムの設計においてはコンテキストスイッチを最適化することが重要である。

コンテキストスイッチは、MikanOS本の流れを踏襲してほとんどのレジスタの値を退避する形で実装した。 struct Context には各種レジスタが並ぶ。

https://github.com/yubrot/ors/commit/74394090cad47eac06995b5cf94ff9f511dd7300

色々と細かい話:

  • CS, SS以外のセグメントレジスタはゼロ初期化するようにした
    • 初期値がゼロでないらしく、これを退避したコンテキストへの switch_context 時に例外が発生してしまう
  • Context に saved: AtomicBool を持たせた
    • switch_context は (1)現在のコンテキストの退避、(2)次のコンテキストの適用、からなるが、(1)の完了をマルチコア間でも観測できるように(1)の完了後にこの値を xchg で更新するようにした
  • Context::new に渡すエントリポイント情報はトレイト化した
    • トレイトの実装側で rip (インストラクションポインタ) や rdi, rsi, ... (System V ABIにおいて数値型の引数をセットするレジスタ群) を初期化する想定
yubrotyubrot

タスクスケジューラ

https://github.com/yubrot/ors/blob/main/ors-kernel/src/task.rs

MikanOSとxv6を参考に、タスクの仕組みを実装した。タスクはコンテキストとそのコンテキストのためのスタック領域や、いくつかの付加情報を保持する。タスクはタスクスケジューラによって順次実行される (プリエンプティブマルチタスク)。実装orsのタスクスケジューラは以下の機能を持つ:

タスクは優先度を持つ

orsの各タスクは優先度 (Priority) を持つ。優先度はとりあえず L0, L1, L2, L3 の4段階とした。スケジューラはタスクを優先度ごとにグループ化していて、単に 実行可能な 最も優先度が高いタスク群をラウンドロビン式で実行していく。優先度の高いタスクが実行可能である限り、それより低い優先度を持つタスク群は永久にスケジュールされない。

タスクは特定の WaitChannel 待ちの状態になって休止できる

WaitChannel は「特定のリソースが準備できるまで待機する」等を表現するための識別子で、タスクスケジューラを通して自由に発行できる。
例えばキーボード入力を処理するタスクがあったとする。このタスクはキーボード入力があったときだけ実行されれば良いが、この待ち合わせに WaitChannel を用いることができる。

  • キー入力があるまで待つ: キー入力に対応するWaitChannel待ちとしてタスクを休止する
  • キー入力が起きたことを通知する: キー入力に対応するWaitChannelが解放されたとタスクスケジューラに通知する

WaitChannel は単に識別子なので、具体的なリソース (キー入力なら入力列を格納するキューなど) とは結び付かない。

ors_kernel::sync::queue は WaitChannel の典型的な使用例で、キューが空の場合とキューが満杯の場合の表現のため2つの WaitChannel を保持している。

タスクは時間ベースで休止できる

一定の時間が経過するまでタスクを休止状態とし、スケジュールされないようにできる。

yubrotyubrot

実装上も幾分hackyな点がある。コンテキストスイッチでは「現在のコンテキスト」の保存と「次のコンテキスト」の反映を一度に行うので [1]、「(現在のコンテキストを含む) 現在のタスク」をタスクスケジューラ内の runnable_tasks や pending_tasks に 追加した後に コンテキスト情報が更新されることになってしまう。可変性が完全に漏れ出しているので、 struct TaskData 上ではコンテキストを ctx: UnsafeCell<Context> として保持している。

脚注

  1. swtich_contextを参照 ↩︎

yubrotyubrot

TaskScheduler::switch のAPIもやや奇妙な形となっている。

fn switch<T>(&self, scheduling_op: impl FnOnce() -> (Option<Switch>, T)) -> T;

TaskScheduler::switch は何をするか。この関数は簡略化すると以下のような流れを取る。

  1. CPUの状態 (Cpu::current().state()) から「現在実行しているタスク」を取り出す
  2. タスクスケジューラ内部のタスクキューに「現在実行しているタスク」を渡し、「次に実行するタスク」を得る
  3. 「次に実行するタスク」をCPUの状態に「現在実行しているタスク」として保存する
  4. 2と4が異なるタスクの場合、コンテキストスイッチを実行する (「次に実行するタスク」が実際に実行中となる)

ステップ(2)において、「現在実行しているタスク」は引数に応じてタスクキューの以下のいずれかに移される:

  1. queue.pending_tasks: WaitChannel やスリープ時間の指定があり、休止状態となるとき
  2. queue.runnable_tasks: 休止状態とならず、すぐスケジュールできるとき

ここで問題となり得るのが(1)の WaitChannel 待ちの時だ。例えば、あるキューがあり、キューが空のときタスクを WaitChannel 待ちに移行するとする。「キューが空であることを確認」し、空だった場合は「 TaskScheduler::switch に WaitChannel を指定して呼び出す」という流れを取ると、この2つの処理が行われる間にキューに要素が加えられる余地がある。既にキューは空でないのに、このタスクは休止状態に移行することになってしまう。このように、「WaitChannel 待ちとなるかどうかの確認」と「タスクを WaitChannel 待ちに移行する処理」の2つは、「WaitChannel を解放する処理」がこの間で発生しないよう、排他的に連続して実行されなければならない。
一方 TaskScheduler::switch はコンテキストスイッチを行うので、単純に排他制御のためのロックの獲得等を行ったまま呼び出すことはできない (現在の実行コンテキストがロックを保持したまま再度スケジュールされるまで長時間残ってしまう)。
TaskScheduler::switch が scheduling_op: impl FnOnce() -> (Option<Switch>, T) を引数に取るのはこのためで、このクロージャはタスクキューがロックされた状態で (= TaskScheduler::release について排他的に) 呼び出される。 Option<Switch> について None を返すと、コンテキストスイッチ自体がキャンセルされる。

WaitChannel を用いたors_kernel::sync::queueの Queue::dequeue は、このAPIを用いて以下のように実装されている。

pub fn dequeue(&self, timeout: Option<usize>) -> T {
    let item = loop {
        match {
            // まず単にdequeueを試みる
            self.inner.dequeue().or_else(|| {
                // キューが空らしいので、このタスクはempty_chan待ちに移行する見込み
                task::scheduler().switch(|| {
                    // 改めてdequeueを "排他的に" 試みる
                    let ret = self.inner.dequeue();
                    let switch = match ret {
                        // dequeueが成功したならコンテキストスイッチはキャンセルする
                        Some(_) => None,
                        // やはりキューが空ならそのまま "排他的に" タスクをempty_chan待ちに移行する
                        None => Some(task::Switch::Blocked(*self.empty_chan, timeout)),
                    };
                    (switch, ret)
                })
            })
        } {
            Some(item) => break item,
            None => {}
        }
    };
    task::scheduler().release(*self.full_chan);
    item
}

xv6の似たような void sleep(void *chan, struct spinlock *lk) 関数は、 chan 待ちのスリープ状態への移行とアトミックにスピンロック lk を解放する。 MutexGuard を引数に取るようなAPIデザインも考えたが、このキューの内部表現に使っているキューがロックフリーな点を活かそうと思いこのようにした。

yubrotyubrot

Async/Await (blog_os)

実装の節までは

  • 協調的マルチタスクとプリエンプティブマルチタスクの利点・欠点
  • RustのFutureトレイトの意図、Futureコンビネータの紹介
  • RustのAsync/Awaitパターンとコンパイラの仕事 (ステートマシンへの変換) の解説
  • 自己参照構造体が必要になる理由と、自己参照構造体の問題を解決するためのピン留めの導入

がよくまとまっていた。現在は、日本語で書かれたRustの非同期プログラミング周りの解説もいくつか見られるので合わせて読むと良いだろう。

yubrotyubrot

実装の方は、Rustのasync/awaitランタイムの実装については参考になった。OS開発としては、既にWaitChannelの仕組みを実装していたのもあり、目新しいものは Stream トレイトとのインテグレーション部分ぐらいだった。
Executor::sleep_if_idle について、今回はカーネルレベルなので sti hlt cli を利用しているが、一般的なユーザーレベルの非同期ランタイムではどう実装されているのか。大雑把に追ってみると、parkという名称の多くのネイティブスレッド自体が持つブロッキング/シグナリングの仕組みや、yield_nowといったAPI (sched_yieldというシステムコールに対応) が利用されるようだ。

非同期ランタイムの実装はやってないが、とりあえずこれでWriting an OS in Rustの現在公開されている章が終わった。MikanOS本も15章が章数的には折り返しなのでこのまま進めていきたい。

yubrotyubrot

15章 ターミナル, 16章 コマンド (MikanOS)

色々と右往左往している... MikanOSではこれらの章に相当する実装を行っているが、本書の流れからはだいぶ逸脱している。

引き続き、MikanOS本で扱っているウィンドウ等のグラフィカルな機能は実装しない方針で進めていく。ただ、ANSI escape codeを採用してCLIを充実させられるようにしていくことにした:

  • シェルの実装等を考えると fmt::Write を実装しているだけではやはり厳しい
  • qemuでのOS起動時に、シリアルコンソールを標準入出力と繋げているが (-serial mon:stdio)、こちらを活用する上で最低限のサポートが求められた (後述)

このあたりの実装を拡充するにあたってconsoleというモジュールを設けた。

入力側

キーボードやシリアルポートからの入力データは、統合して以下のようなデータに変換する:

#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
pub enum Input {
    Char(char),
    Ctrl(char),
    Insert,
    Home,
    End,
    PageUp,
    PageDown,
    ArrowUp,
    ArrowDown,
    ArrowLeft,
    ArrowRight,
}

全てのキー入力はサポートしていないがとりあえずは十分だろう。
キーボード入力はこれまでの実装通りpc-keyboardクレートを用いて変換するが、シリアルコンソールからの入力の解釈のためにはANSI escape codeのパースが必要だった。例えば標準入出力と繋げたqemuのシリアルコンソール上でInsertキーを押下すると、OSのシリアルポートには 0x1b, '[', '2', '~' というシーケンスが入力として与えられる [1]。

変換された入力は、 static IN: Queue<Input, 128> に enqueue し、main側のタスクで直接 dequeueしているが、後ほど /dev/console のようなデバイスファイルと対応付ける形にしたい。

脚注

  1. シリアルコンソールでANSI escape codeが一般に使われるのか、qemuのシリアルコンソールを標準入出力と繋げているからこうなっているのかは不明 ↩︎

yubrotyubrot

出力側

出力側もANSI escape codeを採用する。このエスケープシーケンスをそのままシリアルポートの出力に流すと、標準入出力と繋げたqemuのシリアルコンソール上でもエスケープシーケンスが解釈・実行される [1]。OS側で正しくエスケープシーケンスを解釈・実行できていれば、シリアルコンソール上とOSのスクリーン上で同等な表示の変化が起こると考えられる。

まず、太字のフォントも利用したかったので、ビットマップフォントを扱えるようにすることに。PCFフォントのフォーマットを実装しても良かったが、ttf/otfなら #[no_std] 環境にも適したクレートが既に存在するのでこれを活用することに。今回はab_glyphを用いた。

ANSIエスケープシーケンスのパースも粛々と行い、描画処理とマッピングしたところで、適当に exa --color=always や bat --color=always で得られた出力をOS上で流してみると、シリアルコンソールとOSのスクリーン上で同じような表示が得られるようになった。

脚注

  1. シリアルコンソールでANSI escape codeが一般に使われるのか、qemuのシリアルコンソールを標準入出力と繋げているからこうなっているのかは不明 ↩︎

yubrotyubrot

デバッグ用に非常に単純なシェルを実装する。入力欄の表示は上で実装したエスケープシーケンスを使うことで簡単に実装できる。

static INPUT_START: &str = "\x1b[G\x1b[32m$\x1b[0m "; // 行頭に飛び、greenで $ を描画
static INPUT_END: &str = "\x1b[K"; // 行末までクリア
static CURSOR_START: &str = "\x1b[30;47m"; // 背景色をwhite, 文字色をblackにしてカーソル位置を表現
static CURSOR_END: &str = "\x1b[0m";

といったエスケープシーケンスを用意しておけば、以下のように input_queue() から入力を受け取るループで実装できる。

// 入力されたコマンド用のバッファ
let mut command_buf = String::new();
// 入力カーソル位置
let mut cursor = 0;
...
loop {
    // 入力欄は毎回上書きして表示
    kprint!("{}", INPUT_START);
    for (i, c) in command_buf.chars().enumerate() {
        if i == cursor {
            kprint!("{}{}{}", CURSOR_START, c, CURSOR_END);
        } else {
            kprint!("{}", c);
        }
    }
    if cursor == command_buf.chars().count() {
        kprint!("{} {}", CURSOR_START, CURSOR_END);
    }
    kprint!("{}", INPUT_END);

    match input_queue().dequeue() {
        Input::Char('\n') => { ... } // コマンドを実行
        Input::Char('\x08') if 0 < cursor => { // 1文字削除 (BS)
            cursor -= 1;
            command_buf.remove(cursor);
        }
        Input::Char('\x7f') if cursor < command_buf.len() => { // 1文字削除 (DEL)
            command_buf.remove(cursor);
        }
        Input::Char(c) if ' ' <= c && c <= '~' => { // とりあえずprintableな文字のみ受付
            command_buf.insert(cursor, c);
            cursor += 1;
        }
        Input::Home => cursor = 0,
        Input::End => cursor = command_buf.len(),
        Input::ArrowLeft if 0 < cursor => cursor -= 1,
        Input::ArrowRight if cursor < command_buf.len() => cursor += 1,
        _ => {}
    }
}
yubrotyubrot

17章 ファイルシステム

ファイルシステムの実装の前に、HDD, SSD, USBメモリなどのブロックデバイスとデータを読み書きできる必要がある。リアルな世界では、ブロックデバイス側の高速化、それを活かすための接続規格の変化に伴ってホストコンロローラとの通信規格も変化していったようだ。x86版のxv6ではIDEという規格のドライバを実装しているが、現在はAHCI、NVMeと変化している。あるいは、USBメモリであればUSBドライバとSCSIプロトコルスタックを実装する必要がある。

いずれにしても、これら現代的な規格へのドライバを書くのは大変とのこと。MikanOS本ではこれを簡略化するため、

  • ドライバを実装する代わりに、UEFIにあるBlock I/O Protocolを用いる
  • ブロックデバイスをOSが直接制御することは諦め、ブロックデバイスのデータをまとめてメモリ上に読み出す

としている。

自分としては、ディスクの読み書きを出来るようにしたいなあ...と調べていたところ、xv6のRISC-V版ではVirtIO ブロックデバイスをサポートする形になっていた。実機で動かすモチベは特に無いのと、これなら実装が300行程度で移植を試みやすいのでやってみることにした。(追記) 実際にはSpecificationをよく読み込んで頑張って実装することになり、機械的な移植とはならなかった。

yubrotyubrot

まずqemuでの起動オプションを変更して、ドライブの接続を ide から virtio-blk-pci にした:

run_image.sh
--- a/qemu/run_image.sh
+++ b/qemu/run_image.sh
@@ -19,8 +19,9 @@ qemu-system-x86_64 \
   -m 1G \
   -drive if=pflash,format=raw,readonly=on,file=$DEVENV_DIR/OVMF_CODE.fd \
   -drive if=pflash,format=raw,file=$DEVENV_DIR/OVMF_VARS.fd \
-  -drive if=ide,index=0,media=disk,format=raw,file=$DISK_IMG \
+  -drive if=none,id=drive0,format=raw,file=$DISK_IMG \
   -device isa-debug-exit,iobase=0xf4,iosize=0x04 \
+  -device virtio-blk-pci,drive=drive0 \
   -serial mon:stdio \
   $QEMU_OPTS
 [ $? -eq 33 -o $? -eq 0 ]

qemu上での起動時にOVMFの設定画面に入り (ESCキー押下) Boot Managerの設定を調整するとすんなりと起動する。

yubrotyubrot

上の変更と順番が前後するが、VirtIOブロックデバイスをどこから見つけるか考える。Specificationを見るといくつかの選択肢があり、

  • Over PCI Bus: PCIデバイスとして認識させる
  • Over MMIO: メモリマップドI/O
  • Over Channel I/O: 上のどちらもサポートしてない仮想マシン向け

xv6のRISC-V版ではMMIOを用いている。今回は

  • MikanOSと異なりUSBのサポートをしていない関係で、PCI関連の実装が使われておらず何となく勿体ない
  • 後述のMSI-Xを用いたい
  • 複数のブロックデバイスを認識させる実装が自然に行える

といった理由でOver PCI Busで実装することにした。

yubrotyubrot

MSI (Message Signaled Interrupts)

https://zenn.dev/link/comments/65e92f406a3b5a

MSIについてはMikanOS本の7章で出てきていたが、USBをサポートしなかった関係でPCIも活用していなかったのでここで初めて利用することになる。

PCI - OSDev Wiki # Message Signaled Interrupts

実装する上で見られる特徴は、

  • 各PCIデバイスが独立した割り込みベクトルを持つ
  • MSIでは32個まで、MSI-Xでは2048個までの割り込みを持てる
  • 割り込みはI/O APICを介さず、Local APICへ直接送られる
    • 上述のPCIデバイス独立の割り込みベクトルと、MSIのMessage Address, Message Dataの設定によって通知先Local APICやAPIC上の割り込みベクトルが決定、通知される

MSI/MSI-Xの仕様についてはPCI-SIGのSpecificationsに、x86_64上でのMessage Address, Message Dataの設定についてはIntel SDMに記載があるので、これらを必要に応じて読んで黙々と実装を進めていく。以下のブログ記事も非常に参考になった。

https://mmi.hatenablog.com/entry/2017/03/28/032646

yubrotyubrot

VirtIOではMSI-Xをサポートしているので、MSI-Xの設定を行えるようにする。MSI-X Tableのエントリの設定はI/O APICのRedirection Tableのエントリの設定と似ていて、(以下のコードでは単にLocal APIC IDを直接指定する形となっているが) 通知可能なCPUの指定方法などがエントリ上にエンコードされている他、MSI-X, I/O APICそれぞれの割り込みベクトルからLocal APIC上の割り込みベクトル番号への対応付けがなされている。

pci.rs
impl MsiXTableEntry {
    ...
    pub unsafe fn enable(self, lapic_id: u32, vector: u32) {
        const ADDRESS_SUFFIX: u32 = 0xfee << 20;
        const LEVEL: u32 = 1 << 15; // Level-triggered (vs edge-)
        ...
        let reserved_bits = self.message_address() & 0xff0;
        self.set_message_address((lapic_id << 12) | ADDRESS_SUFFIX | reserved_bits);
        let reserved_bits = self.message_data() & 0xffff3800;
        self.set_message_data(vector | LEVEL | reserved_bits);
        let reserved_bits = self.vector_control() & !1; // enable
        self.set_vector_control(reserved_bits);
    }
    ...
}
pci.rs
unsafe fn initialize_io_apic() {
    const LEVEL: u64 = 0x00008000; // Level-triggered (vs edge-)
    ...

    let bsp = (Cpu::boot_strap().lapic_id().unwrap() as u64) << (24 + 32);
    ioapic.set_redirection_table_at(IRQ_KBD - PIC_8259_IRQ_OFFSET, IRQ_KBD as u64 | bsp | LEVEL);
    ...
}
yubrotyubrot

https://github.com/yubrot/ors/blob/main/ors-kernel/src/devices/virtio/configuration.rs

まずはCommon Configuration。出来上がった実装だけ見ると、ひたすら所定の操作をやるという感想になってしまう...今回は結局仕様書をひたすら読み込んで実装したので、仕様書との対応でメモしておく。

  • Transport Optionsに関わらない初期化の手順は 3 General Initialization And Device Operation に記載されていて、 Configuration::initialize の実装がこれに対応する。
  • 初期化で操作するCommon Configurationは、Over PCI Busでは 4.1.4 Virtio Structure PCI Capabilities の通りPCIのCapabilityとしてそれぞれ提供されている (4.1.4.3 Common configuration structure layout)。
    • しかし今回は、レガシーなインターフェースに沿った実装を行ったので、 4.1.4.8 Legacy Interfaces: A Note on PCI Device Layout に記載されたレガシーなCommon Configuration構造を通した実装となっている。
    • このレガシーなCommon Configuration構造は、MSI-Xが有効か否かによってレジスタが増えてオフセットが変わったりする点で注意が必要だった。また、 ISR status レジスタはMSI-Xを有効にしている場合は使用しない。
  • ドライバとデバイス間で有効にするFeatureのすり合わせを行う negotiation というフェーズがある。今回は、xv6-riscvで無効にされているものはorsでも無効にする方向で進めることで考えることを減らした。
yubrotyubrot

https://github.com/yubrot/ors/blob/main/ors-kernel/src/devices/virtio/queue.rs

Virtqueueの実装。VirtIOではデータの転送にゲスト(ドライバを実装するOS)上のメモリ空間をキューとして用いる。メモリ空間は

  • Descriptor Table
    • QUEUE_SIZE 個の Descriptor を持つ
    • 各 Descriptorに具体的なデータを指す物理アドレス、データ長を設定する
  • Available Ring
    • Descriptor がデバイスによって利用可能であることを示すためのドライバだけが書き込みできる領域
    • QUEUE_SIZE 個の Descriptor のインデックス値と、このリングバッファの先頭を示すインデックス値からなる
  • Used Ring
    • Descriptor がデバイスによって使用されドライバ側に返却されたことを示すためのデバイスだけが書き込みできる領域
    • QUEUE_SIZE 個の UsedElem (ほぼ Descriptor のインデックスと同等) と、このリングバッファの先頭を示すインデックス値からなる

からなる。キューのサイズは初期化後は固定長で、それぞれの領域も以下のように定まる。

Virtqueue part Size
Descriptor Table 16 * queue_size
Available Ring 6 + 2 * queue_size
Used Ring 6 + 8 * queue_size

初期化のコードは以下のような手続きになる。 configuration が上述のCommon Configurationを指す。

impl<T> VirtQueue<T> {
    pub unsafe fn new(configuration: Configuration, queue_index: u16, msi_x_vector: u16) -> Self {
        // このVirtIOデバイスのqueue_index番目についての設定を開始
        configuration.set_queue_select(queue_index);

        let queue_size = configuration.queue_size() as usize;
        assert!(queue_size != 0);

        // このキューに対応する割り込みベクトルを設定
        configuration.set_queue_msix_vector(vector);

        // このqueue_sizeに必要なデータ領域とレイアウトを計算、ページフレームを確保
        let layout = Self::compute_layout(queue_size);
        let frame = frame_manager().allocate(layout.num_frames);

        // Queue Addressレジスタに所定の方法でメモリ領域を指定
        configuration.set_queue_address((frame.phys_addr().as_u64() / Frame::SIZE as u64) as u32);

        // 以降、以下の各データ領域を操作する
        // used_ringはデバイスによって操作されるためread-only
        let descriptor_table = base_ptr.add(layout.descriptor_table_offset) as *mut Descriptor;
        let available_ring = base_ptr.add(layout.available_ring_offset) as *mut AvailableRing;
        let used_ring = base_ptr.add(layout.used_ring_offset) as *mut UsedRing;

        Ok(Self {
            queue_size,
            frame,
            descriptor_table,
            available_ring,
            used_ring,
            ...
        })
    }
}
yubrotyubrot

ドライバがデバイスへのデータ転送

  1. 利用可能なDescriptorを確保
  2. 各Descriptorにデータへの物理アドレス等を設定
  3. Available Ringの先頭(index)にDescriptorのインデックスをセット、indexをインクリメント
  4. Available RingにDescriptorが加わったことを通知するため、Queue Notifyレジスタに書き込み (Available Buffer Notification)

デバイスからドライバへのデータ転送の受け取り

Virtqueueはドライバ側のメモリ空間を使用するため、デバイスからのデータ転送がいきなり始まることはない。事前にAvailable Ringを通してDescriptorをデバイスに与えておくことで、デバイスはそれを使用し、Used Ringの先頭(index)に使用済みのDescriptorのインデックスをセット、indexをインクリメントすることでドライバ側にDescriptorを返却する。

  1. Used RingにDescriptorが加わったことを通知するため、デバイスは割り込みを通知 (Used Buffer Notification)
  2. ドライバは、自身が別途保持している処理済みのインデックス self.last_used_idx とUsed Ringのindexを比較
  3. 3が異なる場合はDescriptorを回収、データを処理
  4. 回収したDescriptorを解放する (orsでは self.first_free_descriptor からリンクリストの形で保持している)

実装はDescriptorチェイン (リンクリスト) の処理などがありもう少し複雑になっている他、デバイスからのデータ転送時に 誰がそのデータを処理するべきなのか を記憶するため、各Descriptorに 関連付けられたデータ T を VirtQueue<T> が別途保持できるようにしている。 VirtQueue<T> のユーザは Descriptor を直接触ることはなく、 Buffer<T> として各 Descriptor のためのデータを与える。

境界チェック等を省いた簡易コードにすると以下の通り:

//ドライバからデバイスへのデータ転送
for buffer in buffers { // buffer: Buffer<T>
    // first_free_descriptorからDescriptorを一つ確保
    let i = self.first_free_descriptor;
    self.first_free_descriptor = self.descriptor_at(i).next();

    // デバイスに共有される具体的なデータ領域 (addr, len) を指すように
    self.descriptor_at(i).refer(buffer.addr, buffer.len, buffer.write);

    // bufferに関連付けられたデータ: T を別途保持
    self.buffer_associated_data[i] = Some(buffer.associated_data);

    ...  // i は後ほどavailable_ringに加えられる
}

// デバイスからドライバへのデータ転送の受け取り
// 割り込みからこの手続きが呼ばれる
while self.last_used_idx != self.used_ring.idx {
    // Used RingからDescriptorのインデックスを取り出し
    let i = self.used_ring_at(self.last_used_idx);
    self.last_used_idx = self.last_used_idx.wrapping_add(1);

    // first_free_descriptorを更新
    // (なお、実際の実装ではDescriptorのチェインを処理する必要がある)
    let prev_first_free_descriptor = self.first_free_descriptor;
    self.first_free_descriptor = i;
    self.descriptor_at(i).set_next(prev_first_free_descriptor);

    // 別途保持していた関連付けられたデータ: T を取り出す
    let associated_data = self.buffer_associated_data[i].take().unwrap();
    handle(associated_data);
}

次に実装するブロックデバイスではこの T を Option<task::WaitChannel> として、ブロックデバイスへの読み書きの完了通知に使用している。

yubrotyubrot

https://github.com/yubrot/ors/blob/main/ors-kernel/src/devices/virtio/block.rs

ブロックデバイスの実装。ブロックデバイスは単一のVirtqueue (requestq) からなり、やり取りするデータも比較的単純なもので済む。データ構造と主要なメソッド2つの簡易コードは以下の通り:

#[derive(Debug)]
pub struct Block {
    configuration: Configuration,
    requestq: Mutex<VirtQueue<Option<task::WaitChannel>>>,
}

impl Block {
    // 読み込みのリクエスト (ドライバ -> デバイス)
    pub fn read(&self, sector: u64, buf: &mut [u8]) -> Result<(), Error> {
        self.check_capacity(sector, buf.len())?;

        let header = RequestHeader::new(RequestHeader::IN, 0, sector);
        let mut footer = RequestFooter::new(0);
        let complete_channel = task::WaitChannel::from_ptr(&footer);

        // ブロックデバイスは3つのDescriptorでリクエストを表現する
        // RequestHeader, RequestFooterの定義は実装とVirtIOのSpecificationを参照
        let mut buffers = [
            Buffer::from_ref(&header, None).unwrap(),
            Buffer::from_bytes_mut(buf, None).unwrap(),
            Buffer::from_ref_mut(&mut footer, Some(complete_channel)).unwrap(), // FooterにWaitChannelを関連付け
        ]
        .into_iter();

        // VirtQueue::transfer によってAvailable RingにDescriptorを加える
        let mut requestq = self.requestq.lock();
        loop {
            match requestq.transfer(buffers) {
                Ok(()) => break,
                Err(unused_buffers) => { ... /* リトライ処理 */ }
            }
        }
        unsafe { self.configuration.set_queue_notify(0) };

        // complete_channelを通して完了が通知されるまでタスクをブロック
        task::scheduler().block(complete_channel, None, requestq);

        fence(Ordering::SeqCst);
        footer.into_result()
    }

    // 完了したリクエストの回収 (デバイス -> ドライバの受け取り)
    // 割り込みから呼ばれる想定
    pub fn collect(&self) {
        let mut requestq = self.requestq.lock();
        requestq.collect(|chan| {
            if let Some(chan) = chan {
                // 完了待ちでブロックしているタスクを解放
                task::scheduler().release(chan);
            }
        });
        ...
    }
}
yubrotyubrot

ファイルシステムについて考える前にパーティションについて。

LBA (論理ブロックアドレス)

LBAとは、ストレージ（外部記憶装置）の記憶メディア上の個々の記憶単位（セクタ）の位置を表す方法の一つで、すべてのセクタに通し番号を付けて先頭からのセクタ数で位置を識別する方式。

ブロックデバイスのドライバの実装に出てきた sectorがそのままLBA値となる。現在は48bit LBA? 48bitで128PiBまで扱える。

GPT

GPT - OSDev Wiki

これまで disk.img を直接 mkfs.fat でフォーマットしていたが、パーティショニングを行う場合はFATのようなファイルシステムはディスクの特定のパーティションに置かれる。UEFIはブート時にEFI System Partitionを認識してUEFIアプリケーションを起動する。

GPTによるパーティションをサポートする場合、

  • qemu-img create, mkfs.fat, mount 等で行っている disk.img 作成の調整
  • ブートローダ側の対応: 今はUEFIのSimple File System Protocolで ors-kernel.elf を直接開いてロードしているが、カーネル本体を別のパーティションに置くならPartition Information Protocolあたりも必要になる
  • カーネル側の対応: GPTパーティションを読み取ってそれぞれをブロックデバイスとして上位のレイヤーに提供する

等が必要となりそうだ。今回はMikanOS本に倣ってFAT32を読めるようにする (パーティションをサポートしない)。

yubrotyubrot

FAT (File Allocation Table) ファイルシステム

FATファイルシステムのコアのデザインは非常にシンプルだと感じた。細部を見ると、互換性の維持などのためにしんどい仕様などを含むが、コアはその名の通りファイルの割り当てを記録するテーブルがあるだけだ。

以下、FAT12/16については省略するが、必要であれば (仕様を満たすなら本来必須だが...) FAT32の実装をベースにFAT12/16に対応する実装も特に問題なく行えるかと思う。実装はors-kernal/src/fs/fat.rsに行った。

ボリュームのレイアウト

FATはボリュームを「予約領域」「FAT領域」「データ領域」に分ける。

  • 「予約領域」にはファイルシステムの重要な情報が集約されている。特に、予約領域やFAT領域のセクタ数、クラスタ(後述)のセクタ数などは、ボリュームのセクタ0に置かれる ブートセクタ に格納されている。
  • 「FAT領域」はFile Allocation Tableが格納される。File Allocation Tableは、単にFATエントリ(後述、32bitの数値)の配列で表現される。 [1]
  • 「データ領域」はファイルやディレクトリなどのデータ本体が格納される。データは「クラスタ」という単位で分割されている。

クラスタのサイズは固定長で、いくつか (2のn乗個) のセクタを束ねたものになっている。例えばボリュームのセクタサイズが512バイトで、 BootSector.SecPerClus が4なら、クラスタは連続した4セクタで2048バイト長となる。

どのクラスタが使用中 (割り当て済み) で、どのクラスタが未使用かどうかはFATエントリに記録される。 各FATエントリは各クラスタと1:1で対応している。 あるFATエントリNの値が 0x00000000 (未使用) でなければ、そのFATエントリNに対応するクラスタNは使用中となる。

なぜFATエントリは32bit長なのか? [2] 使用有無だけの表現を目的とするならFATエントリに32bitも必要ないはずだ。理由は クラスタはチェインできる ところにある。クラスタは固定長なので、格納したいデータ (ファイルやディレクトリの内容) が収まらない場合がある。このようなときに、クラスタNから別のクラスタMにチェインして、クラスタMにデータの続きを格納でき、チェイン先をFATエントリに格納する (M = FAT[N])。

FATエントリの値 説明
0x00000000 未使用
0x00000001 (予約)
0x00000002:0x0FFFFFF6 使用中 (値は次のクラスタ番号)
0x0FFFFFF7 不良
0x0FFFFFF8:0x0FFFFFFF 使用中 (チェインの終端)

まとめると、

  • 特定のファイルやディレクトリの内容は、データ領域のどこかのクラスタ (のチェイン) に格納されている
  • クラスタとFATエントリは1:1で対応しているので、FATエントリを見るとどのクラスタが割り当て可能かわかる

それでは、ファイルの情報やディレクトリの構造はデータ領域にどのように記録されるのか?

ディレクトリ

ディレクトリは通常のファイルと同様に特定のクラスタに割り当てられるが、そのデータは ディレクトリエントリの配列 として格納される。各ディレクトリエントリは32バイトの固定長で、ファイル名、ファイル属性、最終書き込み日時、 ファイルの内容を格納するクラスタの番号 といった情報を保持している。FATファイルシステムにおいては、ファイルに対応したクラスタにはファイルの中身のみが格納され、ファイル名などのファイルのメタ情報は、ディレクトリエントリ上に全て保持される形となっている。

struct DirEntry {
    name: [u8; 11],
    attr: u8,
    ...
    fst_clus_hi: u16,
    wrt_time: u16,
    wrt_date: u16,
    fst_clus_lo: u16,
    file_size: u32,
}

サブディレクトリも、ファイル属性にフラグ 0x10 が立ったディレクトリエントリとして記録される。ディレクトリ名などのサブディレクトリのメタ情報は、ファイルと同様にディレクトリエントリ上に全て保持される。

最後に、ルートディレクトリは BootSector.RootClus が指すクラスタに格納されるため、ここからこのボリュームのディレクトリツリーを辿ることができる。[3]

Long File Name

ディレクトリエントリが固定長、あるいは32バイトと聞いて不思議に思われたかもしれない。ファイル名は32バイトを優に超える文字列長になり得る。実際のところ DirEntry に名前のために割り当てられた空間は11バイトしかない。FATでは Short File Name に適合しないファイル名を Long File Name として区別しており、互換性を保つために涙ぐましい方法でディレクトリエントリのシーケンスにファイル名情報を含めている。これの解説はしんどいので上で紹介したページを参照。MikanOS本でもLFNは省略しているが、SFNしか使えないのはだいぶ哀しいのでorsではLFNの読み取りも実装した。

脚注

  1. File Allocation Tableは破損したときの影響が大きいため冗長化されている。FAT領域はFATが BootSector.NumFATs 個複製されて並んでいる領域となっている。 今回のorsの実装ではコピーは完全に無視している ↩︎

  2. FATエントリの上位4bitは予約されているので現在のバージョン(0x0000)で利用されるのは28bit ↩︎

  3. ルートディレクトリのメタ情報を保持する場所がないが、ボリュームラベルといった一部の情報については別途ブートセクタや特殊なファイル属性が付いたディレクトリエントリに保持するようだ ↩︎

yubrotyubrot

また間が空いてしまった...間に色々やっていた。

spinlockとsleeplock

xv6 (RISC-V版) にあるspinlockとsleeplockを共にorsにも実装することにした。sleeplockではロックの獲得のためにブロックされるときはタスクスケジューラを介して待ち状態になる (つまり、spinlockのようにループしない) ので、ロックの獲得後に割り込みを許可できる。後述のボリュームの読み書きに必要になった。実装はいずれも簡単:

元の sync::mutex::Mutex は sync::spin::Spin にリネームし、sleeplockを Mutex という命名にした。

yubrotyubrot

ボリュームセクタのバッファリング

xv6でいうバッファキャッシュ層を設けた。ボリュームのセクタの読み書きをin-memoryなバッファを介したものにし、実際のボリュームの読み書きはバッファキャッシュからキャッシュが弾き出されるとき (または commit したとき) になる。

https://github.com/yubrot/ors/blob/main/ors-kernel/src/fs/volume.rs

こちらは最終的には実装を読むのが一番理解が早いのでメモっておくことが無いような感触だが...

  • LRU (Least Recently Used) なセクタを再利用するなどの判断を担う、バッファリングされたセクタ群を保持する BufferedSectors はスピンロックで排他的に扱う。このスピンロックの獲得中は (ブロックしうる) ボリュームの読み書きは行えない。
  • BufferedSectors のスピンロックの解放後に、 BufferedSector のスリープロックを獲得して必要なボリュームの読み書きを行う。
  • 特定の処理がバッファをユニークに所有するxv6と異なり、 BufferedSector は Arc<BufferedSector> として共有される。バッファリングされたセクタをまず獲得した上で、読み書きに際してセクタ単位のロックを獲得するようにした。これはパフォーマンス計測等してそうしたというわけではなく、実装上その方が都合が良かった。
  • Arc<BufferedSector> は直接返されず、 BufferedSectorRef に包んで返される。Dropトレイトによって BufferedSectors への返却が自動的に行われる。
yubrotyubrot

ファイルの読み書きができるように。非常にI/Oが遅い…が、逆に思い当たるところがありすぎる。何よりも遅いのはブロックデバイスの読み書きだろう...リクエストキューに一つリクエストを積むたびレスポンス待ちで実行コンテキストを止めている。他、ファイルシステム実装のレベルではFATを毎回先頭から探索しているのも非常に効率が悪い。そもそもFATは全部メモリキャッシュしても良さそうだ。

また設計の面でも、並行した操作に対する安全性だとかエラーへの耐性だとかの考慮が全然出来ていない。FATファイルシステムの仕様上不可能なこともあるが、このファイルシステムで実現出来る限界のレベルにも遠い。自作言語でもそうだったが、それ以上に、自作OSでは様々な領域の実装を扱うので、「最低限実装する」から「ある程度使えるよう実装する」まで持ち上げるのも非常に大変だなあとか思う。ファイルシステムの実装はそれ一つで非常に大きなタスクだ…

このスクラップは2022/02/01にクローズされました