doomgeneric

自作OS on Raspberry Pi 5 - Part 5. FS の最適化と Doom 「気が向いたので自作 OS on Raspberry Pi 5 in Zig を書いてみよう」シリーズのパート5です。 github.com/smallkirby/urthr/tree/584d4426ef0ee12e… 概要 2校目の自動車学校に通い続けてはや5ヶ月。残る教習も8回程度となり、目新しいこともなくなって、そろそろ飽きてきた今日この頃です。やはり何事も一番楽しいのは初めての事をやる時で、その後に待っている反復練習・フィードバックと改善というのは面白くないものです。こと自作 OS においてもつまらないものがあります。それがパフォーマンス最適化です。とりわけ Urthr では FS に対する操作がめちゃくちゃに遅く、Urthr 上で tar 解凍をするだけで数十分かかるという問題がありました。今回はこいつをどうにかして速くします。 測定環境 以下の条件で FS のパフォーマンスを測定します: ワークロード: fio seq: 64MiB のファイルを 4KiB ずつ sequential write。その後 4KiB ずつ sequential read する。既存ファイルに対する RW のパフォーマンス。 smallfiles: 4KiB のファイルを 2000 個作成し、その後すべてを 4KiB ずつ読む。ファイルの作成及び複数ファイルに対する操作のパフォーマンス。 ビルドタイプ: ReleaseFast 対象ボード: q35 (QEMU x64) デバイス: virtio-blk ファイルシステム: FAT32 Urthr は本命の RPi5 を含む4ボードをサポートしていますが、未だに実機の電源をホストPCから制御するための機材を持っていないので、RPi5 実機は使わず Q35 (QEMU) ターゲットを測定対象に使います。 測定対象のデバイスすら、エミュレートされた SDHC ではなく virtio-blk を使っています。これには一応理由があり、そもそも I/O が遅い場合の対処法は以下の3つしか無いと思っています: 速いストレージデバイスを買う ドライバをぎりぎりまでチューニングする I/O をできるだけ発行しない 1 についてはお金がかかるし面白くないので論外です。2については一応やる価値はありますが、ドライバで縮められる要素はそんなに多くないという印象を持っています。というわけで、I/O のパフォーマンスを良くするためには、できるだけ I/O をしないというのが最適解のはずです、多分。そのため、背後にあるデバイスとして virtio-blk を使っても最適化をする上ではそんなに困らない & イテレーションが速くて楽という2点から QEMU ターゲットで測定をします。文句がある人はかかってきてください、全力で逃げ出します。 試した改善案たち 以下が実際に試した改善案たちです: A. Negative Dcache の導入 Urthr では他の多くの OS と同様に、i-node と FS ツリーを関係付けるのに dcache を使っています。dcache は親ディレクトリの dcache と名前を持ち、その両方をキーとしたマップとしてキャッシュされます。例えば /home/neko/inu というパス文字列があった場合、neko の dcache と inu という名前をキーとしてキャッシュを探索し、見つかった場合はすぐに inu の dcache/i-node が得られ、見つからなければ実際のファイルシステムに問い合わせるという感じです。 ところで、今までは存在しないファイル名はキャッシュしていなかったため、存在しないファイルに対するパス解決は毎回実ファイルシステムにリクエストが飛んでいました。これを解決するために、「このパスは存在しない」ことを記憶する negative dcache を導入しました。 B. FAT32 のセクタキャッシュの 4-way 化 FAT32 は 512B のセクタという単位で読み書きします (仕様上は他のサイズもあり得る)。割当てはセクタ単位ではできず、クラスタという単位 (4KiB とか 8KiB とか) で行います。割り当てたクラスタはチェイン構造で繋がっており、このチェインのメタ情報を格納するのが FAT という領域です。また、ディレクトリは子ファイルの一覧を保持しており、ファイルの開始クラスタ位置や名前等を記録しています。 ファイルの I/O には傾向があり、著しくアクセス回数が多いセクタが存在します。前述した FAT が入ったセクタや、ディレクトリを探索するためのディレクトリエントリが入ったセクタはアクセス回数が多いです。よって、このセクタを読み込むたびにキャッシュに載せれば I/O を発行することなく頻繁に読み込まれるセクタを read することができます。 今まではこのセクタキャッシュを単に 64 セクタ分用意していたのですが、頻繁にアクセスされるセクタの個数が 64 を超えており大量のスラッシングが発生していました。また、単純な LRU で管理するとアクセスパターンによってはやはりホットなセクタがキャッシュから追い出されるという問題が発生していました。 そこで、セクタキャッシュを 4-way set associative とし、セット数を 64 から 1024 に増やしました。この 4-way と 1024 という値は、完全に勘です。 C. FAT32 の FAT チェインのキャッシュ 前述したように、クラスタ同士のつながりは FAT チェインによって表現されます。例えばファイルのオフセット 1024 にアクセスしたい場合には、ディレクトリエントリから最初のクラスタ番号を取得 → FAT から次のクラスタ番号を取得 → 1024 バイト目を含むクラスタまで繰り返すという流れになります。チェインを辿るたびに I/O を発行することになるため、Urthr では最後に読み書きしたファイルオフセットと、それに対応するクラスタ番号をキャッシュすることにしました。 D. FAT32 のゼロ埋めのバッチ化 truncate 等のシステムコールは、ファイルの拡張時に拡張分の領域をゼロ埋めします。FAT32 ではゼロ埋め用の専用の機構がないため、ゼロ埋めするには本当にゼロを書き込む必要があります。これまでは1セクタ (512B) ずつゼロを書き込んでいましたが、ゼロ埋め用の予めゼロが書き込まれたメモリ領域を 32 セクタ分用意し、ゼロ埋めする際には最大 32 セクタまで一回の write で書き込めるようにしました。なお、ゼロを書き込みたい、メモリの内容がゼロであることを想定する場面は他にもある気がするため、汎用的に使えるゼロ専用のページを用意しようかとも考えています (mmap の demand mapping における、まだ fault が発生していないページに対する read なんかも、このゼロページにアクセスしますね、多分)。 E. VFS にページキャッシュを入れる めんどうだなぁと思い続けてやらずにいたものの、流石に必要だろうと観念して入れたやつです。どの OS にも存在する、VFS 層のページキャッシュ。読んで字のごとく、ブロックデバイスから読んだデータを DRAM 上にページ単位でキャッシュします。最初は面倒だったので write-through にしていた のですが、これまた観念して write-back にしました。これのおかげで sync 系の syscall を生やしたりする必要がありました。また、Linux に存在するような定期的に write-back してくれる kernel thread はまだ存在しないため、明示的に sync しない限りは2度目以降のディスクアクセスが発生しません。良いのだろうか...。 F. virtio-blk の flush 遅延 デバドラ層の最適化はたかが知れていると言ったのですが、あまりにも virtio-blk のレスポンスが遅すぎるので入れました。virtio はデバイスごとにデバイス (ホスト) に対して有効にする機能を negotiate することができます。virtio-blk の場合には、VIRTIO_BLK_F_FLUSH という feature があり、ホスト側のストレージに対するフラッシュタイミングをゲスト側から明示的に指定することができます。これをしない場合、virtio-blk デバイスに書き込むたびにホスト側で sync が走るようです。今までこの feature を無効化していたので、有効化 しました。 結果 以上の改善やその他書くのが面倒だった改善を含む、計20個の改善を入れました。その結果、 fio ベンチマークの結果は以下のようになりました (プロット by Claude Code です。あいつにできる仕事はこれくらい)。 fio-seq の実行時間 fio-seq のディスク I/O 回数 fio-smallfiles の実行時間 fio-smallfiles の I/O 回数 横軸は入れた改善案の個数で、個別に効果を測定したものではなく、それより左の改善案を含めた合計の改善度合いになります。効果が大きかった改善案のインデックスは以下です: 2: A. Negative Dcache 3: F. virtio-blk の flush 遅延 4: C. FAT32 セクタキャッシュの 4-way set associative 化 6: B. FAT32 クラスタキャッシュ 8: D. FAT32 のゼロ埋めバッチ化 11: E. VFS のページキャッシュ ベースラインと最終結果の比較表はこちら: Workload 実行時間 (sec) Read Ops Write Ops fio-seq Before 325.41 1,677,990 198,741 After 1.15 792 17,929 fio-smallfiles Before 200.21 9,312,011 44,734 After 5.92 2,072 10,311 Doom なんか書くことなくなったので、Doom が動いた図を貼っておきます。エンジンが doomgeneric (fork) で、アセットが Freedoom です。中期目標として始めたものの、doomgeneric が移植しやす過ぎて2日で終わってしまい、少し悲しいです。やった作業は /dev/fbN (fbdev) と /dev/events/inputN (evdev) を生やすことくらいでした。 Doom あと Urthr 上で Zig コンパイラを使って適当なサンプルアプリもコンパイル・実行することもできるようになりました。FS 改善前はサンプルアプリのビルドに 9 分かかっていたのですが、改善後はコールドビルドで 6 秒です。 Zig on Urthr サンプルプログラムに ミーム を使うとはいい度胸していますね。 アウトロ 最近めっきり寒い。ぽっきり寒い。眠い。

しくみ：ozkl/doomgeneric をemscriptenでC→WASM→pure js化して、(cohtmlがcanvas書きかえ非対応のため)毎フレームBMP作って<img>に流し込んでます