「ゼロからのOS自作入門」を Rust でやる (第17章)

いつの間にかこのシリーズも10記事を超えていました。 本記事で11記事目です。 難所をいくつも越え、なんとか最終章まで続けられそうな気がしてきました。 頑張っていきましょう。

第17章

FATファイルシステムを扱えるようにする章です。 この章ではFATファイルシステムのルートディレクトリのファイル一覧を出力できるようにします。

FAT ファイルシステムカーネルから参照できるようにする (day17a)

「ゼロからのOS自作入門」ではファイルシステムの実装にあたり、ブロックデバイスからの読み書きはサポートしていません。 代わりに、メモリの一部分をブロックデバイスと見なし、メモリ上にファイルシステムを構築します。

C++ 版実装では UEFI のブロックデバイス読み取り機能を使い、 OS のブートイメージの先頭部分をメモリ上にコピーすることでメモリ上にファイルシステムを構築していました。

Rust 版実装では、ブートローダーは bootloader クレートを利用しているため UEFI に手を入れるのは面倒です (bootloader クレートを fork しないといけない)。 今回は、build.rs で必要なファイルを含んだFATイメージファイルを作成し、バイナリデータとしてカーネル本体にリンクするようにしました。 カーネルのバイナリサイズが16MiB増加しますが、許容範囲でしょう。

github.com

build.rs の処理の流れは以下の通りです。

  1. FAT ファイルシステムのイメージファイルを作成
  2. llvm-objcopy で上記イメージファイルの内容を含むオブジェクトファイルを作成 (_binary_fs_fat_start というシンボルでファイルシステムにアクセスできるようにする)
  3. llvm-ar で上記オブジェクトファイルを含む静的ライブラリを作成し、成果物にリンクするよう cargo に指示する

当初は16Mi要素のバイト配列を定義した Rust ソースコードを出力し、カーネルソースコードから include!() する方式を試していましたが、カーネルコンパイルが終わらなくなってしまったため、静的ライブラリをリンクする方式に変更しました。

FAT ファイルシステムの作成には fatfs クレート を利用しました。 「ゼロからのOS自作入門」で紹介されていた mkfs.fatmount. を使う方法と異なり、root 権限が不要になるのが良いですね。

ルートディレクトリのファイルを一覧する (day17b)

前節で追加したファイルシステムからルートディレクトリのファイル一覧を取得し表示するコマンド ls を追加します。

github.com

C++版と同じように実装すれば良いかと思いきや、結構引っかかりました。 というのも、「ゼロからのOS自作入門」ではファイルシステムFAT32 であることを前提としたいたのですが、 今回 Rust 版でカーネルにリンクされたファイルシステムFAT16 であったため、構造体メンバのアクセス方法などが大きく異なっていたためです。 FAT の仕様上 FAT32 にできるのはボリュームサイズが 32MiB 以上の場合のみで、今回作成した 16MiB のファイルシステムFAT12FAT16 にせざるを得なかったようです。

仕方がないので、 FAT12/FAT16/FAT32 に対応できるようにしました。 実装にあたり、以下のサイトを大いに参考にさせて頂きました。

ファイルシステムの詳細はできるだけ fat モジュールに閉じるようにして、 terminal モジュールからは詳細をあまり意識しなくて良いようにしようとしています。 まだ抽象化は十分ではない感じなので、これから機能を追加しながら綺麗にしていけたらなあと思います。

まとめ

比較的短い章でしたが、 FAT12/16 でのファイルアクセス方法を調べながらコーディングする必要がありなかなか大変でした。 次章はついにアプリケーションが実行できるようになります。 ユーザーランドのプログラムも rust で書きたいものですが、果たしてうまくいくのでしょうか? 次章もお楽しみに。

「ゼロからのOS自作入門」を Rust でやる (第14章~第16章)

ブログの更新は間が空いてしまいましたが、OSの移植じたいは細々と続けていました。 今回はまとめて3章分です。

第14章

第13章に引き続きプリエンプティブマルチタスクを実装する章です。 第14章ではタスクのスリープや優先度を実装します。

タスクのスリープ (day14a)

タスクのスリープを実装します。また、 s キー、 w キーの入力でタスクBをスリープ状態にしたり実行状態にしたりします。

github.com

実装は C++ 版とおおよそ同じです。 Rust 版固有の作り込みとして、コンテキストスイッチ時の Arc の取り扱いがあります。

static TASK_MANAGER: OnceCell<Mutex<TaskManager>> = OnceCell::uninit();

#[derive(Debug)]
struct TaskManager {
    tasks: BTreeMap<TaskId, Arc<Task>>,
    wake_queue: VecDeque<TaskId>,
}

impl SwitchTask {
    fn switch(self) {
        assert!(Arc::strong_count(&self.next_task) > 1);
        assert!(Arc::strong_count(&self.current_task) > 1);
        unsafe {
            let next_task_ptr = Arc::as_ptr(&self.next_task);
            let current_task_ptr = Arc::as_ptr(&self.current_task);
            drop(self.next_task);
            drop(self.current_task);
            #[allow(clippy::unwrap_used)]
            let next_task = next_task_ptr.as_ref().unwrap();
            #[allow(clippy::unwrap_used)]
            let current_task = current_task_ptr.as_ref().unwrap();

            Task::switch(next_task, current_task)
        }
    }
}

Task 構造体は TaskManager 構造体の tasks フィールドに Arc<Task> という形で格納されています。 TaskManager 構造体は複数のコンテキストからアクセスするために static 変数 TASK_MANAGER に保持されており、アクセスするためには Mutex ロックの取得が必要です。 このため、コンテキストスイッチ時にロックを取得したままだと次回のコンテキストスイッチ時にロックを取得しようとしてデッドロックになってしまうため、以下のような順序で処理するようにしました。

  1. TASK_MANAGER のロックを取得
  2. 現在実行中のタスクと次にコンテキストスイッチするタスクの Arc<Task> のクローンを取得
  3. TASK_MANAGER のロックを解除
  4. コンテキストスイッチ対象の Arc<Task> から *const Task を取得し、 Arc<Task>drop する
  5. コンテキストスイッチを実行

4 で *const Task を取得しているのは、 Arc<Task>drop (参照カウントのデクリメント) をコンテキストスイッチ前に行いたいためです。 4~5 の時点では TaskManagerArc<Task> を保持しているため、ポインタの指す先の領域が解放されることはないはずです。

イベント発生時にタスクを起床させる & アイドル時にタスクをスリープさせる (day14b)

イベント待ち状態になったタスクをスリープ状態にする & 他タスクに対してイベント通知をする際に当該タスクを起床状態にするという節です。 これにより、OS の応答性が向上します。

C++ 版ではタスク間でイベントをやりとりするためのイベントキュー関連処理でタスクの起床/スリープを行っていました。 Rust 版では async-await の仕組みを採用しているため、 async-await の waker の仕組みと連携できると良さそうです。

まずは、新たに生成されたタスクで async-await が使えるよう、タスクごとにランタイム (executor) を持つようにしました。

github.com

従来は Task::new の引数にタスクのエントリーポイントとなる関数ポインタを渡していました。 修正後は impl Future<Output=()> を渡すようにしています。 エントリポイントは全タスクで共通化し、第一引数 rax に格納されたポインタから Box<EntryPointArg> を復元し、その中に含まれる executor の run メソッドを実行することで CoTask が実行できるようになりました。

次に、 async-wait の waker をタスクの wake/sleep に対応させます。

github.com

waker が CoTask を起床させる際に、当該 CoTask が所属するタスクも起床させるようにしました。 また、各タスクの Executor で処理可能な CoTask が存在しなくなったら自タスクをスリープさせるようにしました。 これだけでイベント発生時のタスク起床 & アイドル時のタスクスリープが実現できます。 簡単ですね!

タスクに優先度をつける (day14c)

個々のタスクに優先度 (レベル) を設け、優先度の高いタスクが優先的に実装されるようにします。

github.com

C++版とは少し実装方法が異なりますが、簡単に実装することができました。

アイドルタスクを追加 (day14d)

すべてのタスクがスリープ状態になった時にCPU消費を抑えられるよう、 hlt を実行するだけの低優先度タスクであるアイドルタスクを追加します。

github.com

バグ修正

Rust 版のタスク優先度設定にはバグがあり、高優先度のタスクが実行可能状態の場合にタイマー割り込み契機のコンテキストスイッチ要求が発生すると、低優先度のタスクにスイッチしてしまうという問題がありましたので修正しました。

github.com

もうひとつのバグとして、割り込みコンテキストでのコンテキストスイッチ時にメモリ獲得を行ってしまう可能性がありました。 タスクの spawn 時に必要な領域獲得を行うようにして、割り込みコンテキストではメモリ獲得が行われないようにしました。

github.com

第15章

端末を実装する章です。

ウインドウ描画をメインタスクで行うようにする (day15a)

Rust 実装では元々描画処理はメインタスクで行うようにしていたため、この節の対応は不要でした。

アクティブウインドウの追加 (day15b)

アクティブウインドウの概念を導入し、タイトルバーの色を変えたり、キー入力イベントの送信先タスクを限定したりします。

まずは、ウインドウ描画処理を共通化します。 具体的には、タイトルバーや枠のあるウインドウを意味する FramedWindow 構造体を追加しました。

github.com

C++ 版では ToplevelWindow という名前でしたが、あまりしっくり来ない名前だったので FramedWindow としています。 また、C++版では ToplevelWindowWindow を継承していましたが、Rust 版では継承ではなくコンポジションでコードの再利用を実現しています (Rust 版では LayerWindow を保持しないため Window 型とのサブタイピング関係が不要であるという事情もあります)。

次にアクティブウインドウを管理する ActiveLayer 構造体を追加します。

github.com

だいたいC++版と同じ実装です。

続いて、ウインドウの状態に応じてタイトルバーの色を変更します。

github.com

ウインドウごとにイベント通知用のキューを保持するようにし、 ActiveLayer が各 Window の active/inactive を変更した時に、当該キュー経由でイベント通知するようにしました。

更にこのキューを利用して、キーボード入力イベントはアクティブウインドウに送信するようにしました。

github.com

これにて最初の節はおしまいです。

ターミナルの追加 (day15c)

ターミナルのウインドウを追加します。

github.com

C++版とだいたい同じです。

描画速度の高速化 (day15d)

従来はウインドウの一部に更新があるとウインドウ全体を再描画していました。 再描画時に必要な範囲だけ描画するよう描画範囲を指定することで描画処理を高速化します。

github.com

C++ 版ではターミナルのカーソル点滅の処理のみ描画範囲指定して高速化していました。 描画が必要な範囲は Window に描画する側のコードで計算する必要があります。 Rust 版では描画処理において再描画が必要な範囲も記憶するようにすることで、描画する側のコードで特殊な考慮をする必要がなくなり、カーソルの点滅以外のすべての描画処理で高速化の恩恵を受けられます。

バグ修正

第15章まで実装したあたりで、並列処理関連のバグ (デッドロックやクラッシュ) が高頻度で発生するようになってしまったため、関連バグを修正しました。

デッドロックが発生した原因は、スピンロックとタスクの優先度の実装方法にあります。 スピンロックは、ロック取得に失敗した場合タスクをスリープさせるのではなく、無限ループで他のタスクがロックを解放するのを待ちます。 また、現時点では高優先度のタスクが実行可能状態で存在する限り、低優先度のタスクは実行されません。 結果として、以下のようなデッドロックが発生する可能性があります。

  1. 低優先度のタスクがスピンロックを取得する
  2. 低優先度のタスクがロックを解放する前に高優先度のタスクにコンテキストスイッチする
  3. 高優先度のタスクが当該ロックを取得しようとすると、いつまで経ってもロックが取得できず待ち続けてしまう

この現象を回避するため、ロック取得失敗時にタスクをスリープさせるような Mutex を実装しました。 (スケジューラーのロジックを変更するのでも良いのですが、 Mutex はいずれにせよ必要になるため実装しました)

github.com

Mutex ロック取得失敗時、タスクIDを Mutex の保持するキューに追加します。 Mutex ロック取得に成功したタスクは、アンロック時にこのキューに含まれるタスクIDのタスクを起床させます。 (上記コミットのソースにはレースコンディションがあったため、後のコミットで修正しています。)

Mutex の実装に SegQue を利用したため、 allocator の排他制御に Mutex は利用できなくなってしまいました。 このため、メモリ割り当て処理中は割り込みを抑止するようにしました。

github.com

Mutex のキューにヒープの領域ではなくスタックの領域を利用するなどすれば allocator の排他制御にも Mutex が利用できるかもしれないですね。

また、複数タスクからロックが取得される可能性がある箇所については Mutex を利用するようにしました。

github.com

ここまでの修正でデッドロックやパニックの発生頻度はかなり低下しました。 ArrayQueue 関連処理が wait-free でないため同様のデッドロックが発生する可能性は残っているのですが、ひとまずはこれでヨシとしました。

ついでに、割り込みコンテキストから allocator が呼び出されたことを検知できるようアサーションも追加しています。

github.com

並列処理が関連すると問題のあるコードがたまたま動いてしまうことが多く、バグがあっても再現性がなくて原因調査が大変だったりするので、アサーションを入れるに越したことはないでしょう。

第16章

ターミナル上での入力やコマンド実行を実装する章です。 全体的にC++実装と同じで難しいことはあまりないので、コメントは省略します。

github.com github.com github.com github.com github.com github.com

まとめ

プリエンプティブマルチタスクと協調的マルチタスク (async-await) をうまく連携させることができました。 Rustらしい実装ができたのではないかと思います。 また、並列処理に関するバグも修正でき、動作の安定度も上がっています。

次章ではファイルシステムを取り扱います。どうなることか。お楽しみに。

「ゼロからのOS自作入門」を Rust でやる (第13章)

13章もなかなかに難産でした。 マルチスレッドプログラミングは難しい...

第13章の前に

第13章に取り組む前にいくつかバグ修正をしました。

unaligned memory access を修正

デバッグモードでビルドしたOSを起動したところ、 debug_assert!() で異常終了してしまいました。 原因は、XSDTのエントリ (u64) が 8byte 境界に揃えられていなかったためです (4byteずれていた)。 x86_64 は unaligned なメモリアクセスも可能なので修正前のプログラムでも動いてしまうのですが、 デバッグビルドを動作させられないのも困るので修正しました。

github.com

修正自体は簡単で、ポインタの指す先を一度 [u8; 4] として読み込んだ後、 u64::from_le_bytesu64 へと変換しているだけです。

オーバーフローの修正

同じくデバッグモードで検出したバグです。 タイマーの初期化時に整数のオーバーフローを検出していました。

github.com

let lapic_timer_freq = elapsed * 10;

上記が問題のあった処理です。 上記の演算結果が u32::MAX を越えてしまうためオーバーフローが発生していました。 オーバーフローが発生しないよう修正しました。

第13章

プリエンプティブマルチタスクを実装する章です。

コンテキストスイッチの実装 (day13a)

コンテキストスイッチを実装します。

github.com

コンテキストスイッチのためにはアセンブリでの実装が必要です。 Rust のインラインアセンブラを使いたかったので、 naked function を使ってみました (関数のプロローグ・エピローグを生成させないため)。

コンテキストスイッチを実装しましたが、この節の段階では協調的マルチタスクの実装であること、また、C++版と異なりウインドウへの画像描画ではなくコンソールへの文字列出力しかしていないため、この段階では特に難しいことはありませんでした。

Makefile + Cargo から Cargo への以降

本筋とは関係ないのですが、 Makefile を利用するのをやめ、 Cargo だけで OS をビルド & 実行できるようにしました。

github.com

また、ユニットテストも実行できるようにしました。

github.com

saibos のブートローダーである bootloader クレートに example が追加されたので、それを参考に実装しました。

ユニットテストが書けるようになると複雑なロジックもある程度安心して書くことができますね。

ログのリフォーム

ログ関連コードを整理しました。

github.com

具体的な修正内容は以下です。

  • ログをシリアルポート経由で QEMU を起動した端末にも出力する
  • ログ出力関数呼び出し元のファイル名、行番号をログに出力する
  • ログレベルに Trace を追加し、 USB ドライバ関連ログのレベルを落とした

LayerWindow が描画バッファを共有していたのをやめる

従来処理では LayerArc<Mutex<Window>> を所有し、描画処理時はロックを取得していました。 このような構造では描画スレッドと Window 関連処理のスレッドが同時に Window にアクセスしようとした場合、片方のスレッドが次のコンテキストスイッチ発生まで長時間待たされてしまいます。 描画スレッドが待ち状態になってしまうと、他の Window の描画も行われなくなるため問題です。 この問題を解消するため、 LayerWindow を所有しなくなるように修正しました。

github.com

従来処理では layer_managerCoTask に描画を依頼するために DrawLayer イベントを送信していましたが、同時に描画するデータを含むバッファも送信するようにしました。 描画完了後バッファを元の CoTask に oneshot チャンネル経由で返却します。 これにより、画面描画処理時に Mutex ロックを取得する必要がなくなります。

サブタスクからウインドウを描画する

従来はメインタスクからのみウインドウの更新をしていましたが、サブタスクでもウインドウの描画を更新するようにしました。 前節までの準備が実を結びましたね。

github.com

メインタスクとサブタスクが同時に oneshot チャンネルのロックを取得する場合があったため、ロック待ち時に panic するのではなく、コンテキストスイッチ発生までスピンロックで待ち続けるようにしました。

定期的なコンテキストスイッチ (day13b)

タイマー契機で複数のタスク間でコンテキストスイッチを発生させるようにしました。 プリエンプティブマルチタスクです!

github.com

実行してみると、動作が非常に遅いです。 タスクBではウインドウの描画を更新する度に oneshot チャンネルからバッファを受信するのですが、このときメインタスク側の処理が実行されるまで待ち続けてしまうため、タスクBのコンテキストではほとんど処理が進まずフリーズして見えることが原因のようです。

描画処理ではロックを使わないようにしたのですが、それだけではだめで、待ち時間をなくさなければならないようですね。 なんてこった...

トリプルバッファの導入

タスクが待たされてしまう問題に対してどうしたものかと思い悩みいろいろ調べてみたところ、どうやらトリプルバッファというものが利用できそうということが分かりましたので、実装してみました。

github.com

トリプルバッファにはいろいろな流儀があるようなのですが、ここでは以下のような仕組みを実装しています。

  • in_progress, ready, present の3種類のバッファを用意する
  • 描画内容生成元タスク (producer) は in_progress バッファを所有する
  • 画面への描画処理タスク (consumer) は present バッファを所有する
  • producer は描画処理完了後、 in_progress バッファと readyスワップする (アトミック操作)
  • consumer は画面への描画開始時、 ready バッファと present バッファを比較し、 ready バッファの内容の方が新しい場合、 両者をスワップする (アトミック操作)

この仕組みにより、producer (consumer) は常時 in_progress バッファ (present バッファ) にアクセス可能 (=待ち時間がなし) になります。

トリプルバッファのアルゴリズムは 以下を参考にしました。

codereview.stackexchange.com

値が一致しない場合に値を差し替えるアトミック操作 (compare and swap の逆?) の実装は以下を参考にしました。

stackoverflow.com

ロックフリーアルゴリズムは頭の体操みたいで楽しいのですが、難しいですね...

また、例によってアトミック操作のオーダーについては自信が持てなかったので、複数スレッドによりアクセスされる領域の操作は SeqCst にしています。

トリプルバッファの実装にあたり、デバッグのためにユニットテストが非常に役立ちました。

トリプルバッファを使ってウインドウを描画する

前の節で用意したトリプルバッファでウインドウを描画するようにしました。 合わせてコードの整理も行っています (Window 生成にビルダーパターンを使うようにした)。

github.com

タスクBが動作している間は画面の描画は更新されませんが、画面描画は高速化されました。いい感じですね。 なお、タスクBが動作している間に大量のイベントがキューイングされるため、 layer_managerCoTask のキューのサイズを大きくしています。

まとめ

プリエンプティブマルチタスクの仕組みを実装しました。 トリプルバッファを導入するなど C++ とは実装が大きく乖離したため、結構大変な章でした。 まだ性能はイマイチなのですが、次章以降で改善していきましょう。

「ゼロからのOS自作入門」を Rust でやる (第10章~第12章)

今回はまとめて3章です。

第10章

ウィンドウを表示して操作できるようにする章です。 一気にGUIっぽくなりますね。

マウスカーソルが画面外に飛び出すのを修正 (day10a)

マウスカーソルを画面端に動かすと画面端から飛び出してしまうのを修正しました。

github.com

C++版では画面から飛び出したマウスが反対側の端から現れるようになっていました。 Rust 版では描画時に座標の範囲チェックを行っているためそのような動作にはなっていませんでしたが、 マウスが画面端から移動して隠れてしまうようにはなっていたため修正しました。

メインウインドウを追加 (day10b)

メインウインドウを追加します。

github.com

メインウインドウ処理専用の CoTask を作成し、表示するようにしています。

高速カウンタを追加 (day10c)

イベントループのループ毎にカウントアップするカウンタを作成し、値をメインウインドウに表示します。

github.com

C++版とは構造が異なりイベントループは async/await の executor として実装されているため、ループ内に簡単にカウントアップ処理を追加することはできません。 このため、一度イベントループに制御を戻した後即復帰するような Future である Yield を作成し main_window のイベント処理中で利用するようにしました。 これにより、 main_windowCoTask からイベントループに一旦制御を戻せるようになります。 制御を戻した回数をカウントすることでカウンターの代替としました。

描画範囲の制限による高速化 (day10d)

従来処理では画面の一部分が変更された場合でも画面全体を再描画していました。 これを更新があったウインドウの範囲のみ再描画するように変更し、画面描画を高速化します。

github.com

実装方針はC++版と同じです。

WindowWindowDrawer を統合する

WindowWindowDrawer はそれぞれ別の構造体として定義していましたが、両者を統合し、 WindowDraw を実装するようにしました。

github.com

コードがシンプルになりました。

Mutex::with_lock を追加

CoTask のイベントループ内で一時的に Window のロックを取得し、描画完了後アンロックするという処理が何度も登場しています。ロック & アンロックの区間を制御するため以下のようにブロックが必要なのですが、コードが読みづらく感じたため、引数のクロージャにロックを取った値を渡す Mutex::with_lock を用意しました。

// 既存処理
let mut window = ...;
{
    let mut window = window.lock();
    window.fill_rect(...);
    window.fill_rect(...);
}

// 改造後処理
window.with_lock(|window| {
    window.fill_rect(...);
    window.fill_rect(...);
});

github.com

後者の方がロック区間が明確になって良いかなーという気持ちです。

バックバッファによりちらつきを解消する (day10e)

これまでは画面の描画時に直接フレームバッファに描画していました。 このため、描画途中の状態が画面に表示されるため、マウスカーソルなどがちらついて表示されることがありました。 これを解消するため、バックバッファをというバッファを導入します。 各ウインドウの描画時に直接フレームバッファに描画するのではなく、一旦バックバッファにすべてのウインドウを描画し、 完了後にバックバッファの内容をフレームバッファにコピーするという実装へと変更します。 これによりちらつきが完全に解消します。

github.com

ウインドウをドラッグできるようにする (day10f)

ウインドウをドラッグすることで移動できるようにします。

github.com

mouseCoTask でマウスのボタン押下を検知できるようにし、それに応じてウインドウをドラッグできるようにします。 マウスカーソルの下にあるウインドウの LayerId を取得するため、 LayerManager へ問い合わせるようなインタフェースを用意しています。 これまでの LayerManager 関連処理と異なり、 LayerManager 側関数からの戻り値を呼び出し元へ返す必要がありますが、mouselayer_manager はそれぞれ異なる CoTask で動作しているため、通常の関数のように値を渡すことはできません。 CoTask 間を跨がって値をやりとりするためにはチャンネルが利用可能ですが、これまでに作成したチャンネルは何度も繰り返して値を送信するためのものであり、関数の戻り値といった値を一度だけ渡すような使い方には向いていません。 このため、 oneshot というチャンネルを作成し使うようにしています。

マウスのドラッグ関連処理を layerCoTask へと移動する

先ほどの節でマウスのドラッグ処理を実装したばかりですが、今後このようなマウスからの入力に応じてウインドウを制御するような処理が増えてくると、 mouselayerCoTask 間でのやりとりが増えることとなり、効率が悪いですし、なによりもプログラミングがめんどくさいです。 このため、 mouseCoTask はマウスボタンの押下有無等を判定するだけとし、 layerCoTask でドラッグ等の処理を行うようにしました。

github.com

CoTask 間の役割分担が明確になって良い感じですね。

メインウインドウだけをドラッグ可能にする (day10g)

従来の実装では Window により実装されているすべての要素がドラッグ可能だったため、コンソールやデスクトップの背景もドラッグ可能になってしまっていました。 main_window だけドラッグできるように改造します。

github.com

Layerdraggable というメンバーを追加し、当該メンバが true の場合のみドラッグ処理を実行するようにします。 先の節で layerCoTask にドラッグ関係の処理を移動したことで、簡単に実装することができました。 (mouseCoTask で各レイヤのドラッグ可否を取得しようとすると、layerCoTask とのメッセージやりとりを増やす必要があるため)

第11章

Local ACPI によるタイマーを実装する章です。

ソースコードの整理 (day11a)

ソースコードのモジュール構造を整理する節です。 Rust版では最初からモジュール構造を整理していたため、特に何も行っていません。

タイマー割り込み (day11b)

Local ACPI によるタイマー割り込みを実装します。

github.com

実装は xHC の割り込みとほとんど同じですが、割り込みの発生有無だけが分かれば良い xHC と異なり、割り込みが発生した回数が重要なため、割り込み発生回数を AtomicU64 でカウントするようにしています。

タイマー間隔の短縮とタイマーマネージャーの追加 (day11c)

タイマーの設定により割り込み間隔を短縮するのと、タイマーを管理する TimerManager を追加します。

github.com

複数のタイマーへ対応する (day11d)

プログラムの複数箇所で同時にタイマーによる待ち合わせができるようにします。

github.com

前の節で追加した TimerManager に、タイマーの登録とタイムアウトの通知機能を実装します。 timerCoTask では ACPI タイマーの割り込みと他の CoTask からのタイマー登録依頼という異なるキューからの二種類のイベントを処理しないといけないため、 futures_util::select_biased マクロを利用しています。 select マクロは std が必要ですが、 select_biasedstd 不要なのでフリースタンディング環境でも利用できます。

なお、タイマー割り込みで使うかと思い動的に CoTaskspawn できるようにする仕組みを Executor に追加しましたが、結局使いませんでした。 今後利用出来る場面があるかと思い、実装はそのままにしています。

RSDP を取得する (day11e)

正確な時刻が分かる ACPI PM タイマーを利用するための準備の節です。

github.com

Rust 実装で利用しているブートローダーである bootloader クレートでは、起動時のパラメータとして RSDP へのポインタが渡されるため、カーネル側の実装は特に難しいことはありませんでした (例によって RSDP の物理アドレスが仮想アドレスにマッピングされていなかったため、ページテーブルの書き換えは行っていますが)。

問題があったのは bootloader 側の実装でした。 具体的には、 ACPI v1 と v2 の両方の RSDP が存在する場合に、 ACPI v1 側の RSDP をカーネルへ渡す場合があるためです。 これは、UEFIブートローダー実装で ACPI v1 と ACPI v2 の RSDP のうち、先に見つかった方をカーネルへ渡すようになっているためです。

github.com

筆者のQEMU環境では必ず ACPI v1 の RSDP が渡されるようでした。 ACPI PM タイマー利用のためには ACPI v2 の RSDP が必要なのでこれでは困ってしまいます。

ひとまず、 bootloader にパッチを当て、 ACPI v1 の RSDP は無視するようにしました。

github.com

また、 bootloaderGitHub リポジトリに issue を立てました。

github.com

作者の方にも反応頂いたので、そのうち解決されるといいなー。

第12章

ACPI PM タイマを使えるようにするのと、キーボードからの入力に対応する章です。

FADT を検索する (day12a)

前の節で検索した RSDP をたどって XSDT を取得、そこから更に FADT を検索するという節です。

github.com

だいたい C++ 実装と同じですね。 Rust のイテレーターではメソッドチェーンで検索処理を簡潔に書けるのが良いですね。

ACPI PM タイマーによりタイマー間隔を補正する (day12b)

正確な時間が分かるタイマーである ACPI PM タイマーにより、周期が不明なタイマーである Local APIC タイマーの周期を測定します。

github.com

これもまた C++ 実装と同じです。 余談ですが、筆者環境だとどうも時間が正しく計れていないような気がしています。 1秒間隔のはずが、3秒間隔くらいになっています。 筆者は WSL2 上で QEMU を動作させているのですが、 WSL2 では (まだ) Nested VM がサポートされていないため、 QEMU の動作が遅いことが原因なのでしょうか。

キーボードからの入力を処理する (day12c)

キー入力を受け取って画面に出力する節です。

github.com

C++ 実装と同じで特に書くことがありません...

修飾キーを処理する (day12d)

Ctrl や Shift などの修飾キーを処理できるようにします。

github.com

C++ と同じですね。

テキストボックスを表示する (day12e)

テキストボックスを含むウインドウを作成し、キー入力に応じてテキストボックス内に文字を表示します。

github.com

テキストボックスのウインドウを独立した CoTask として実装しています。 また、キーボード入力を処理する keyboard CoTask からは mpsc::Sender 経由でキー入力イベントをテキストボックスの CoTask へ直接送信するようにしています。 将来的には送信先 CoTask を動的に切り替える処理が必要になるでしょうが、とりあえずはこのような簡単な実装にしておきます。

点滅するカーソルを描画する (day12f)

テキストボックスに入力位置を示すカーソルを描画します。

github.com

0.5秒ごとにタイマーイベントを発生させ、イベント契機ごとにカーソルの描画、削除を繰り返します。 定期的に実行されるタイマーである timer::interval を追加し、簡単に利用できるようにしています。

まとめ

C++ 実装とだいたい同じで書くことがだんだん無くなってきましたが、メモ代わりにブログ記事は残しておこうかとは思っています。

次章はついにプリエンプティブマルチタスクの実装です。Rust でうまく実装できるのか。楽しみですね。

「ゼロからのOS自作入門」を Rust でやる (第9章)

改造量の多い章だと時間がかかってしまいますが、ゆるゆると続けております。

第9章

マウスカーソルを動かすと背景やコンソールの文字が消えてしまう問題を解決するために、重ね合わせ処理 (レイヤー) を導入する章です。

重ね合わせの実装 (day09a)

以下を実装しました。

  • マウスカーソル、デスクトップ背景など個別の描画要素を意味する Window 構造体と、 Window への描画機能を有する WindowDrawer 構造体の追加
  • 重ね合わせの個々の階層を意味する Layer 構造体
  • Layer の重ね合わせ順序や Frame Buffer への描画を制御する LayerManger 構造体
  • Console 構造体の動作変更 (LayerManager の初期化までは直接フレームバッファに描画、初期化後は Window に描画しフレームバッファへの描画は LayerManager が行う)

github.com

実施していることは C++ 版と同様なのですが、実装の詳細が異なります。 具体的には以下の差異があります。

  • C++ 版: LayerManagerグローバル変数として定義し各 Window の更新処理から直接メソッドを実行
  • Rust 版: 各 Window の更新処理および LayerManager の処理はそれぞれ専用の CoTask で実施。 Window の更新処理により画面の再描画が必要になった場合、 LayerManagerCoTask へとイベントを通知し、それを受けた LayerManager のタスクが描画を行う

上記を実現するために、 sync::mpsc::{Sender, Receiver} のような async/await 対応したキューを作成しました。 (マウスカーソル移動の時に作成したものを共通的に使える構造体として定義しなおしました)

tokio の mpsc キュー の実装は複雑なのでこのような構造体を定義するのは難しいと思っていたのですが、機能を絞れば簡単に実装することができました。 例えば、今回作成したキューでは tokioReceiver or Senderdrop 後に send/recvErr で復帰させる機能などは実装していません。

EmergencyConsole の追加

重ね合わせ処理の導入により LayerManager 初期化後は、 Console に書き込んだ文字列の描画は LayerManagerCoTask が行うようになりました。 Console へ書き込んだ文字列が画面に表示されるためには async/await のランタイム (Executor) や各 CoTask が正常に動作している必要があります。 通常の処理で Console を使う限りは問題ないのですが、パニックハンドラーや例外ハンドラーの中で文字列を出力したい場合、これでは問題があります。 ハンドラー実行以降はプログラムの実行が停止してしまいランタイムも動作しないため画面に文字列が描画されないためです。

この問題に対処するため、パニックハンドラーや例外ハンドラーからの文字列表示のため EmergencyConsole を導入しました。 Console を改造しても良かったのですが、パニックハンドラーや例外ハンドラーから複雑な処理を行うと正しく動作しない可能性があったため、シンプルな別構造体として追加しました。

github.com

EmergencyConsole ではフレームバッファを利用して画面描画するのですが、ハンドラー呼出し時の状況によってはフレームバッファのロックが取られており、普通にロックをとるとデッドロックしてしまう可能性があります。 これに対処するため、 EmergencyConsole からロック取得する場合は、既存のロックを強制的にアンロックした上でロックを取得するようにしています。

タイマーの実装 (day09b)

性能測定のために Local APIC タイマーを使えるようにする節です。

github.com

実装については特にコメントはないです。

シャドウバッファの追加 (day09c)

従来処理ではフレームバッファへの描画時に毎回 Color 構造体からフレームバッファの byte 配列フォーマットへの pixel 毎に変換していました。画面サイズが大きいと、この処理の負荷は大きくなります。

これを改善するため、フレームバッファと同じフォーマットでデータを保持するシャドウバッファを各 Window に持たせ、 フレームバッファへの描画時はこのシャドウバッファの内容をコピー (memcpy) するような方式へと変更しました。 これにより Color 構造体から byte 配列フォーマットへの変換が描画の度に毎回行われることがなくなり、性能が改善されます。

github.com

C++ 版とは異なり、 ShadowBuffer という専用構造体を用意しています (この後のコミットで変更されますが)。

コンソールのスクロール速度を測定する (day09d)

コンソールのスクロール速度を測定するためタイマーを設定しています。

github.com

C++ 版とは異なり、実際の描画処理は LayerManagerCoTask で行われるので、時間測定処理も当該 CoTask に追加しています。 また、どの CoTask からの描画依頼かを区別するため、 CoTask 間でやりとりするメッセージに描画時間測定対象か否かを意味するフラグを追加しています。

ShadowBufferFrameBuffer の実装共通化

先の節で ShawdorBufferFrameBuffer は別の構造体として実装していました。 両者共画面の描画を行うという点は共通で、描画対象が Vec<u8>FrameBuffer かが違うだけです。 実装共通化のため Vec<u8>FrameBuffer を抽象化する Buffer トレイトを設け、 Buffer トレイトを実装した型に対して描画する BufferDrawer という構造体を導入しました。

github.com

コンソールの性能改善 (day09e)

コンソールのスクロール時、コンソールの描画範囲全体に対して文字の再描画を行っていました。 文字の描画のためには各文字の字形に応じてドット単位で描画する必要があり、非常に時間がかかります。 これを、描画範囲全体を上方向に移動させることで単純な memcpy で済むようにし処理を高速化しました。

github.com

まとめ

重ね合わせ処理を実装し、マウスカーソルを動かしても背景が消えることがなくなりました。 また、重ね合わせ処理の性能改善により、マウスカーソルの描画自体も高速になった気がします。

また、 C++ 実装もなかなかに Rust らしい実装へと変更できているのではないでしょうか。 この調子で次章も進んでいきたいです。

「ゼロからのOS自作入門」を Rust でやる (第7章)

引き続き Rust で OS を作っていきます。 今回は、Rust 1.39 で安定化されたあの機能が登場します!!!

第7章

割り込みハンドリングの章です。 謎の現象が起きてなかなか実装に苦労した章です。

割り込み契機でマウスカーソルを動かすようにする (day07a)

6章までの実装では無限ループでポーリングすることで xHC のイベント発生を検知していました。 本章では xHCI で定められた割り込みの発生方法である、 MSI (Message Signaled Interrupts) に対応し、 MSI 割り込みを受け取った契機でマウスカーソルを動かすようにします。

github.com

C++実装の通りに割り込みハンドラを定義し、 IDT (Interrupt Descriptor Table) を設定し、 PCI コンフィグレーション空間の読み書きで MSI を設定しました。

さっそくQEMUで動かしてみたところ、割り込み呼び出し箇所で Page Fault や Double Fault や Segment Not Present やらの例外が発生して正しく動作しません。 なにが起きているのかよく分からないのですが、各例外発生時の情報を見て想像するに、どうやらセグメントがおかしいのが原因のようです。

github.com

というわけで GDT (Global Descriptor Table) でセグメント設定するようにしてみました。 コードセグメントを設定するだけではだめだったので、スタックセグメントも設定したところ、うまく動作するようになりました。 理屈は全く理解できていませんが、ひとまず動くようになったのでヨシ!ということで先にすすめたいと思います。

ヒープへ対応

C++ 実装でヒープに対応するのは第9章ですが、この次に実装するものでヒープが必要だったので先にヒープを実装してしまいます。 C++ 実装では brk を実装することで newlib の malloc を利用できるようにしていたのですが、 Rust ではこれ以上 newlib に依存するのは避けたかったので、 "Writing an OS in Rust" の "Allocator Designs" の記事 を参考に独自のメモリアロケータを作成しました (ほぼほぼコピペですが...)。

github.com

このメモリアロケータ実装ではヒープ領域とするフレームの数と同じ回数だけ FrameAllocator::allocate() を呼び出します。 今回ヒープ領域は 128MiB としているので当該関数は 128MiB / 4KiB = 32,768 回呼び出されることになります。 FrameAllocator (BitmapMemoryManager) の実装そのままでは処理に時間が掛かりすぎ、OSの起動に長時間かかるようになってしまったため、 BitmapMemoryManager の実装を高速化しています。 具体的には、割り当て可能なフレームを探索する範囲を意味する BitmapMemoryAllocator::range の値を、フレームの割り当ての度に更新することで不要な探索を削減するようにしています。 (フレームの割り当て回数 N に対し、従来は N^ 2 / 2 回処理が発生していたところを N 回の処理で済むように改善しました)

これで BoxRcArc が使えるようになりました。

BIOS で起動しなくなっていたのを修正する (修正できなかった)

ここまで開発してきた機能は主に UEFIブートローダーで動作するか確認していたのですが、 BIOSブートローダーで確認したところ、起動処理中に panic が発生するようになってしまっていましたので修正します。

github.com

一つ目の問題は、ブートローダーに渡されたメモリのマッピング情報から各フレームの使用状況を更新する処理にありました。 具体的には、BIOSブートローダーから渡されるメモリのマッピング情報に含まれるアドレスがフレーム境界に揃っていなかったためエラーとなっていたのでした。 このアドレスをフレーム境界に合うように丸めることで問題に対処しました。 なお、他の用途で使われているフレームを使用可能として扱ってはいけないため、フレーム全体が使用可能なフレームのみ使用可能としています。

これで一つ目の問題は解決したのですが、依然として C++ 側処理のログ出力処理で Segment Not Present の例外が発生してしまいます。 どうも浮動小数関連のレジスタを操作している箇所が問題で、 va_start などが関係していそうな気がするのですが、原因がよく分からないですし、 UEFI 側では問題なく動作しているようなので、ひとまず放っておくことにします。

async/await を使えるようにする

"Writing an OS in Rust" の "Async/Await" の章 に感銘を受けたので、 sabios にも実装します。 割り込み契機のイベント処理のために async/await が使えると非常に便利で綺麗に書けると思います。 これがやりたかったがために MikanOS の Rust 移植を始めたと言っても過言ではありません。

github.com

Executor 等の実装は "Writing an OS in Rust" のほぼコピペです。 これだけのコードで非同期ランタイムが作れてしまうのはすごいですよね。

タスクを意味する構造体の名前は、 CoTask (Cooperative Task)としました。 Task ではなく CoTask としたのは、後の章で出てくるプリエンプティブなタスクと区別するためです。

async/await で割り込みを処理する (day07b)

割り込みハンドラ内でイベント処理を行っていたのを、割り込みハンドラ内ではイベントを通知しメインのタスクで通知を受け取りイベント処理するように変更する節です。 Rust 実装ではグローバルなイベントキューではなく async/await を使います!

github.com

今回は割り込みが発生したか否かという情報だけを割り込みハンドラから CoTask へ通知すれば良いので、キューではなく AtomicBool で割り込み発生有無を通知するようにしました。 OrderingRelaxed で良い...はず... (あまり自信がないです)

github.com

ついでにマウスカーソル移動時のイベント処理についても CoTask にしました。 従来処理では C++ から呼び出されるコールバック関数内で mouse_cursorframebuffer のロックを取得していたため、ロック順序の整合性がとれているか不安だったのですが、今回の改造によりコールバック関数の中ではロックを取得しなくなったので、安心度が上がりました。

まとめ

割り込みに対応し、割り込み契機でマウスカーソルを動かせるようにしました。 また、 async/await で割り込みをエレガントに処理できるようにしました。 一方、BIOSブートローダーではなぜか動作しなくなってしまいました。謎です。。。

さて、8章の内容は先日やってしまったので、次は9章です。 どんどん OS が高機能化していって Rust で実装する楽しみが増えそうですね! 次回もお楽しみに。

「ゼロからのOS自作入門」を Rust でやる (第6章 その2)

ちょっと間が空いてしまいましたが、第6章の続きです。 今回はついにマウスカーソルを動かせるようになります!

第6章

第6章 その1 の記事では C++ の USB ドライバをコンパイル & カーネルにリンクした上で Rust 側コードから呼び出すようにしましたが、XHC との通信を行う MMIO 領域へアクセスするとページフォールトが発生してしまったのでした。

今回はページテーブル等の設定を行う事で USB マウスでマウスカーソルを動かせるようにします。

MMIO 領域に仮想アドレスを割り当てる

第8章 で用意した部品を使って、 xhc_mmio_base から 64KiB 分のフレームを仮想アドレスにマッピングします。 マッピングするアドレスは物理アドレスと同じアドレスとします (アイデンティティマッピング)。 アイデンティティマッピングとすることでアイデンティティマッピングを前提としている USB ドライバ実装の変更が不要になります。

github.com

64KiB マッピングしているのは、 Intel のリファレンスのページ にそう書いてあるためです (This gives 64 KB of relocatable memory space aligned to 64 KB boundaries.)。

マッピングをしているのは以下処理です。

    {
        // Map [xhc_mmio_base..(xhc_mmio_base+64kib)] as identity map
        use x86_64::structures::paging::PageTableFlags as Flags;
        let base_page = Page::from_start_address(VirtAddr::new(xhc_mmio_base))?;
        let base_frame = PhysFrame::from_start_address(PhysAddr::new(xhc_mmio_base))?;
        let flags = Flags::PRESENT | Flags::WRITABLE;
        let mut allocator = memory::lock_memory_manager();
        for i in 0..16 {
            let page = base_page + i;
            let frame = base_frame + i;
            unsafe { mapper.map_to(page, frame, flags, &mut *allocator) }?.flush();
        }
    }

x86_64 クレートx86_64::structures::paging::mapper::Mapper トレイト を使い、 pageframeマッピングしています。 ページテーブルを配置するための物理メモリを割り当てる必要があるため allocator を引数に渡しています。

この対応により無事ページフォールトは発生しなくなりました! やったね!

続きの部分の実装

残りの処理も実装しました。

github.com

C++ 実装と大きな差異はありません。

一通り実装して動かしてみたのですが... 動きません。 なぜでしょうか。 ページフォールトなどの例外も発生していないようです。

デバッグ

どうやら C++ のコードがうまく動作していないようです。 それなりの規模のコードをデバッガなしでデバッグするのはつらいので、 gdbデバッグを試してみましょう。

まず、 QEMU の起動オプションに以下を追加します。

$ qemu-system-x86_64 ... -gdb tcp::1234

これにより localhost のポート 1234 で gdb の接続を受け付けるようになります。 別の端末から以下のように gdb を起動するとアタッチできます。

$ gdb ./target/x86_64-sabios/debug/sabios -ex "target remote localhost:1234"

実行中のコード行やバックトレースも表示され、 ユーザーランドの普通のプログラムをデバッグしているかのようですね。

gdb でステップ実行などして調べてみると usb::xhci::ProcessEvent 関数 の振る舞いがおかしいようです。 当該関数ではどこからか通知されたイベントを処理しているようですが、イベントがひとつもキューイングされてきていないようです。 イベントをキューイングする処理が正しく動作していないのかもしれません。

次に、イベントをキューイングしているのは誰かを調べてみましょう。 PrimaryEventRing() で返ってくるのは usb::xhc::EventRing 型の参照なので、 EventRing の実装を調べるのが良さそうです。

ProcessEvent 関数で呼び出している EventRing::HasFront メソッドでは ReadDequeuePointer というメソッドを呼び出しています。 ReadDequeuePointer の実装 では interrupter_->ERDP.Read().Pointer() を呼び出しています。 interrupter_ は、EventRing::Initialize 呼出し時 に渡されるもので、 InterrupterRegisterSets() で返される配列の先頭へのポインタです。 InterruptRegisterSets の定義 より、これは xhc_mmio_base に一定のオフセットを加算した領域のようです。また、当該関数の戻り値型である InterrupterRegisterSetArrayメモリマップされたレジスタを意味する構造体 (の配列) のようです。 interrupter_->ERDP.Read().Pointer() の意味するところは、 ERDP というメモリマップドレジスタの値を読み込んでいるようですね。

まとめると、EventRing ではメモリマップドレジスタの値を読み込み、値が特定の条件を満たしている場合にイベントが発生したと判断するようです。 イベントが発生していないということは、このメモリマップドレジスタの値の更新が (XHC により?) 行われていないというのではないでしょうか。 もしそうであれば、 XHC の初期化処理が正しく行われていないのではないかと想像されます。 この観点でもう少し調べて見ましょう。

手始めに EventRint::Initialize の実装を見てみましょう。 ざっと読むと、以下のような処理を行っているようです。

  1. AllocArray を呼び出し、 buf_erst_ の領域を確保
  2. ERSTSZ レジスタerstsz (erst のサイズ?) をセット
  3. ERDP レジスタbuf_ のアドレスをセット
  4. ERSTBA レジスタerst_ のアドレスをセット

ここで ERDPERSTBA にセットされるアドレスはどのようなものなのでしょうか。 AllocArray の実装 を見てみると、グローバル変数として静的に獲得された領域のようです。 C++プログラム上で取り扱っているアドレスをそのままレジスタにセットしているため、設定される値は当然仮想アドレスです。 一方、XHC 側が必要とするアドレスは物理アドレスだと想像されます。 仮想アドレスが物理アドレスと一致しないために、 EventRing は正しく動作しないのではないでしょうか。

仮想アドレスと物理アドレスが一致していないかどうか確認するため、 bootloader のソースを確認してみましょう。 bootloader のカーネルをロードする処理 では、セグメントをロードする物理アドレスはファイル中のセグメント位置に固定値 (self.kernel_offset) を足したもの、仮想アドレスはセグメントで指定された仮想アドレスにロードしているようです。 self.kernel_offset の値は、 カーネルと同じサイズ (?) の static 変数の先頭アドレス でした。 この実装を見る限り、仮想アドレスと物理アドレスが必ず一致するようなソースにはなっていないようですね。

対処

どうやら、XHC のレジスタに渡すアドレスが適切な物理アドレスになっていないところに問題がありそうです。 他にも問題はあるかもしれませんが、まずはこの問題に対処してみましょう。以下の方針が考えられそうです。

  1. ブートローダーのカーネルのロード処理を改造し、カーネルをロードした範囲では仮想アドレスと物理アドレスが一致するようにする
  2. USB ドライバーを改造し、メモリマップドIOに利用するバッファ領域を仮想アドレスと物理アドレスが一致している領域に配置する
  3. USB ドライバーを改造し、アドレスをレジスタにセットする処理で仮想アドレスを物理アドレスへ変換した上でセットするようにする

1, 3 は大変そうなので、簡単な2を採用しました。

github.com

static 変数で 32 * 4096 バイトの領域を確保していたところを、 FrameAllocator 32フレーム獲得した上でアイデンティティマッピングを設定し、その仮想アドレスをバッファのアドレスとしてセットするようにしました。

ドキドキしながら実行してみたところ、無事マウスカーソルがマウスの動きに連動して動作するようになりました。やったーーー!!!

まとめ

紆余曲折ありましたが、無事USBドライバを動作させマウスの動きをキャプチャできるようになりました。 C++とのFFIに苦戦するかと思っていたのですが、そこは思ったよりすんなりとできました。 苦労したのは bootloader のメモリの使い方の差異への対応でしたが、なんとか解決できて良かったです。 また、C++のUSBドライバ実装にも少しだけ詳しくなれた気がします。

一つ大きな山を越えられたので、この先もどんどん実装していきたいと思います。