借り初めのひみつきち

仮ブログです。

UEFI ゴルフの果てに

前回の記事の UEFI ゴルフの続報です。

Hello world はどの環境でも文字列出力関数(API, メソッド, etc...)を呼び出すだけなのでコードはほぼ定型となりコード部分の最適化の余地はほとんどありませんでした。
ゴルフのお題のひとつに CHARS というものがあり、これは印字可能 ASCII 文字の一覧を出力するものです。
CHARS は固定の文字列データが存在しないのでロジックの最適化で Hello world より小さくできる可能性が高いです。

ということで、試行錯誤の末にヘッダの圧縮とセットで 268 バイトまで削減することができました。

EfiMain:
    push rbx
    push rdi
    enter 0x20, 0

    mov rdi, rdx
    mov ebx, 0x20
.loop:
    mov rcx, [rdi + 0x40] ; EFI_SYSTEM_TABLE->ConOut
    lea rdx, [rbp + 0x20]
    mov [rdx], ebx
    call [rcx + 0x08] ; EFI_SIMPLE_OUTPUT_PROTOCOL->OutputString
    inc ebx
    cmp bl, 0x7F
    jb .loop

    xor eax, eax
    leave
    pop rdi
    pop rbx
    ret

なお、最後に改行を入れてないのでシェルのプロンプトによって表示が一部破壊されてしまいます。これがレギュレーション的に OK だったかどうかよく覚えてません...

f:id:neriring16:20191128231935p:plain

実際には push/pop を使わないバージョンも一応動きはするのですが、なぜか起動しません。

f:id:neriring16:20191128232634p:plain

そこですぐに ret する何もしないアプリケーションを作って nop の量を調整して調査した所、どういうわけかテキストセクションのサイズが 0x28 (40) バイトに満たないバイナリは問答無用でエラーになるようです。

つまり、これ以上ロジックを最適化しても意味がないということで、ゴルフ終了・・・?

ねり先生の次回作にご期待ください。

成果物を GitHub に公開しておきます。

github.com

最小の UEFI Hello World

UEFI は実行ファイルに PE/COFF という形式を採用しています。

PE/COFF 形式はご存知の方も多いかと思いますが Windows で現在主流の実行ファイル形式で、名前の通り昔 UN*X で使われていた COFF 形式の派生です。
COFF から PE/COFF になる際にオリジナルの COFF の機能のいくつかは廃れ、逆に Windows に必要な情報がいくつか追加されました。その際、元の COFF にあった廃れたフィールドはそのまま残し、新たに追加されたフィールドは Optional Header に追記する形で拡張されました。
またその後 Windows の進化に合わせて PE/COFF にも新しい機能が追加されたり廃れたりしました。
このような経緯のため PE/COFF のヘッダーにはほとんど使われていないフィールドが多数存在します。*1

また、 PE/COFF は DOS や古い Windows との互換性のために DOS Stub というダミーの DOS プログラムが含まれています。*2


UEFI では仕様を決める際に実行形式として PE/COFF を利用することが決まりました。
Windows のために色々な機能がてんこ盛りされた PE/COFF ですが UEFI ではほとんどの機能が不要なので使われていません。
つまり、適当なツールで適当に生成された UEFI の PE/COFF には無駄がたくさん詰まってるということになります。


というわけで、最小の UEFI Hello World に挑戦してみたのが以下になります。345 バイトになりました。

github.com

これ以上小さくするには使われていないヘッダフィールドに別のヘッダーを埋め込むようなテクニックが必要になりますが、 BaseOfCode を 0x1000 より小さくするのが難しそうだったのでヘッダーに埋め込むのは無理かもしれません。


ところで、 PE/COFF には無駄がたくさん詰まっているということは偉い人も気づいていたようで、 EFI の初期化環境である PEI 仕様では TE (Terse Executable) という形式がサポートされています。
TE 形式は PE/COFF から DOS Stub を廃止して COFF Header と Optional Header から最小限の重要な情報だけを抜粋した独自のヘッダーに差し替えたものです。

f:id:neriring16:20191104194532p:plain:w300

UEFI BIOS ROM イメージをダンプしてみると TE 形式のファイルが埋め込まれているのが確認できます。

f:id:neriring16:20191104195304p:plain:w300


PE 形式から TE 形式にコンバートするだけで COFF Header と Optional Header の無駄なフィールドがほとんど消えて数百バイト節約でき、理論上 Hello world が 120 バイト前後まで小さくできます。
しかし、試しに手元でバイナリーをいじってみたところうまく実行できませんでした。
ヘッダーの書き方が悪かったのか、それとも通常の EFI Application 実行環境ではサポートされていないのかいまのところ不明です。

*1:ただし明確に使用しないと明言されているフィールドは少なく、使われているのかどうか不明なフィールドも多数存在します。

*2:多くの場合 DOS Stub はメッセージを出すだけの小さなプログラムですが、 EXE 形式で実現可能なプログラムは何でも入れることができるのでまれに DOS Stub の部分だけでひとつのアプリケーションになっている場合もありました。

BitTest 命令

x86 には BitTest というマイナーな命令があります。

具体的には BT BTS BTR BTC の4種類あって、それぞれ特定のビットをテスト(1かどうか返す)、セット(1)する、リセット(0)する、反転する(0⇔1)命令になります。

BitTest 命令をレジスタに使った場合はちょっとだけビット操作が楽になりますが、別に AND OR XOR でもいいよね感がありました。

実は BitTest 命令はレジスタに対して実行した場合とメモリに対して実行した場合重要な違いがあります。

x86 CPU はシフト命令などでビットを指定するオペランドは 32bit (64bitオペランドの場合は64bit) に制限され、例えばシフト命令に 100 を指定しても実際には 100回もシフトしませんでした。
BitTest 命令をレジスタに対して実行した場合はシフト命令などと同様に 32bit の制限がかかっていますが、メモリに対して実行した場合は 32bit の制限がありません。
つまり、何百何万もある巨大な配列の先頭を指定して BitTest 命令を実行するとそこから何百何万番目の遥か遠くにあるビットに対してビット操作する事ができます。

また、マルチスレッドプログラミングにおいても重要な機能があり、 BitTest 命令は実行前の対象ビットの値を CF レジスタに返します。
つまり、 LOCK プレフィックスとセットで使うと Mutex などのメモリ上の特定のビット操作をアトミックに扱う事ができます。

マイナーだけど、すごい命令です。

exFAT について

exFAT というファイルシステムがあります。
FAT ファイルシステムの次世代ファイルシステムとしてリムーバブルメディアなどに採用実績がありますが、仕様が公開されておらず特許が絡むために Microsoft 製以外の OS からはあまり使い勝手がよくありませんでした。

しかし、仕様が公開され、特許の条件も緩和されようとしているようです。

docs.microsoft.com

exFAT は名前の通り FAT を改良したファイルシステムで、以下のような FAT によく似た特徴があります。

  • クラスタという単位でセクタを管理しており、最初のクラスタ番号は2である
  • FAT というテーブルによりクラスタチェインを管理している
  • 32バイト単位のディレクトリエントリでファイルを管理している

一方で以下のような相違点もあります。

  • 空き領域はビットマップで管理されており、 FAT 上で管理されていないファイルが存在する
  • 8.3 ファイル名が存在せず、通常のファイルはディレクトリエントリを複数必要とする
  • FAT には存在しなかったメタデータ拡張機能が存在する

FAT はフロッピーディスクの時代に設計されたもので小容量ではそれなりにうまく動いていましたが、メディアが GB 単位の時代になってくると色々と不都合が増えてきました。 exFAT はより大きなメディア、特にソリッドステートメモリーでうまく扱えることを前提に設計されています。

クラスタ

FAT におけるクラスタとは、生のセクタを直接扱うと量が多すぎて管理が大変になるので、複数のセクタをまとめてクラスタという名前の論理セクタとして扱うことでトータルの論理セクタ数を減らして管理を楽にするための概念です。
よく使われるクラスタサイズとして 4KiB や 32KiB などがあります。4KiBはページングのページサイズ、32KiBはよくあるフラッシュメモリーのページサイズと一致するため管理の都合が良い数値です。

クラスタ単位でディスクアクセスすることでセクタ単位でアクセスするよりも高速で効率的なディスクアクセスが可能になります。
一方で、クラスタサイズはファイルの最小単位でもあり、1バイトでも内容のあるファイルはディスク上で最低1クラスタを占有するため、クラスタサイズが大きすぎると必ずしもディスクを効率的に扱えるとは限りません。

クラスタ番号は歴史的な事情で2から開始します。*1 クラスタ番号から実際のセクタ番号に変換する場合はオフセットを考慮する必要があります。

FAT とクラスタチェーン

クラスタサイズを超えるファイルを格納するには2つ以上のクラスタが必要です。
1番目のクラスタ番号はディレクトリエントリから辿れますが、2番目以降のクラスタを探す方法が別途必要になります。
この時 FAT 系ファイルシステムは FAT というテーブルを参照する事で2番目以降のクラスタを探します。

例えばクラスタ番号123のクラスタの次のクラスタを探す場合、 FAT テーブルの123番目の要素を調べ、そこに456とあった場合は次のクラスタは456と決めることができます。

FAT では FAT の要素のサイズによって FAT12FAT16FAT32 というバリエーションがありました。*2
exFAT は稀に FAT64 という俗称で呼ばれることがありますが FAT の要素サイズは 32bit となっています。

FAT ファイルシステムでは FAT テーブルはクラスタの利用状況を管理するためにも使い、 FAT テーブル上に 0 と記述されたクラスタは空き領域、 0xF...F7 と記述されたクラスタ不良セクタや予約セクタを含んでいるのでデータとして使用禁止、という風にクラスタを管理していました。

一方、exFAT では利用状況の管理には FAT テーブルを利用せずビットマップで管理しており、クラスタが連続していることが保証されている属性のファイルは FAT 上にクラスタチェーンを形成しません。
つまり、exFAT には FAT によるクラスタチェーンで管理しているファイルと FAT を利用しないファイルの2種類のファイルがあります。

これによるメリットは2つあります。
ビットマップは FAT テーブルに比べてサイズが小さいので空き領域を割り当てる検索処理が素早くできます。空き領域をビットマップで管理するのは他のファイルシステムでも割とよく使われる方法です。
また、ファイルアクセス時に毎回 FAT 上のクラスタチェーンを辿るのはコストがかかるため、クラスタチェーンを辿らなくても連続したクラスタにアクセスできることで高速化に寄与します。

exFAT におけるファイル管理は基本的には FAT 上にクラスタチェーンを生成しないように連続した領域を割り当て、どうしても断片化してしまった時に改めてクラスタチェーンを生成するのが効率的な管理になります。 exFAT という名前でありながら基本的には FAT を利用しないのが exFAT です。

ディレクトリエントリ

FAT も exFAT も32バイト単位のディレクトリエントリという構造体でファイルの情報を管理します。

FAT のディレクトリエントリは FAT12 の時代に設計されたもので、 FAT32 の時代になるとかなり無理のある使い方をしてすでに限界に近い状態でした。
当初、ファイル名は8.3形式の短いファイル名のみサポートしていましたが、その後特殊な属性のディレクトリエントリを繋げることで長いファイル名をサポートし、互換性のために短いファイル名と長いファイル名の2つでファイルを管理していました。

exFAT でもディレクトリエントリの基本サイズは32バイトですが、ディレクトリエントリの構造を大幅に変更することで FAT よりも多くの情報を含めることができるようになり、タイムスタンプの2秒問題などが改善しています。
通常のファイルは1つのディレクトリエントリに情報が収まりきらないため3つ以上のディレクトリエントリを繋げて使用します。
8.3形式のファイル名には対応しておらず、 FAT の長いファイル名と同等の制限の緩いファイル名を使うことができます。

また、細かい違いとして従来サブディレクトリに存在した「.」「..」という存在理由のよくわからないディレクトリエントリは exFAT のボリューム上には存在しません。

メタデータ、大文字テーブル

exFAT では従来の FAT ファイルシステムにはなかったメタデータが増えています。
例えば、先述の空き領域ビットマップはメタデータとして専用のディレクトリエントリがルートディレクトリにあります。

また、 exFAT の特徴的なメタデータとして大文字テーブルというものがあります。
FAT ファイルシステムはもともとファイル名を大文字で管理し、ファイルの検索は大文字小文字を区別しません。
exFAT では大文字に変換するためのテーブルがボリューム上のメタデータとして存在します。*3
大文字テーブルで変換したファイル名からハッシュ値を計算し、ディレクトリエントリのハッシュ値と比較することで大小文字を無視したファイルの検索が高速にできるのが他のファイルシステムにはないユニークな特徴となっています。この部分が特許に絡んでいた気がしますが、ソースを見つけることができませんでした。

ソリッドステートメモリーとの親和性

exFAT は先述のようにクラスタが連続しているファイルは FAT によるクラスタチェーンを経由せず高速にアクセスできます。
また、クラスタサイズやオフセットを調整してソリッドステートメモリーのページサイズと一致させることで効率の良いアクセスが可能になっています。
そのためにソリッドステートメモリーの特性を記述できる拡張属性が定義されています。

*1:なぜ2から始まるのかはよくわかりません

*2:実は FAT32 は要素サイズは 32bit ですが 32bit 全て使っている訳ではありません

*3:しかし仕様書によると内容は固定のようです...

WASM自作PCエミュレータ制作日記/5

ついに某OSの起動画面が出ました。

f:id:neriring16:20190721020613p:plain

まだ動作が怪しいですが...

この辺ならキーボードも普通に動きます。(マウスは死んでます

f:id:neriring16:20190721020631p:plain

某OSも途中で止まります。
cpuid実装してるはずなのに認識されてないのが気になります。

f:id:neriring16:20190721020652p:plain

FreeDOS (32bit) はまだよくわからない動作をします。

f:id:neriring16:20190721020703p:plain

WASMで自作PCエミュレーター Part4

自作エミュレーターVGA に(一部)対応しました!

github.com

今までは UART 経由で端末エミュレーターに接続していました。
DOS やその上で動く多くのソフトウェアは標準入出力という概念があるので、今まではこの方法が簡単に実装できてうまく動いていました。
しかし、世の中には VRAM を直接操作してテキスト表示したり、グラフィックスを扱うソフトもたくさんあります。
また、使っていた端末エミュレーターにも色々と不満が出てきていたので置き換えたいと考えていました。
そんなわけで VGA の実装をはじめたのでした。

V・G・A!

VGA を実装するにあたって問題がひとつありました。このエミュレーターMMIO に対応していません。
要するに VRAM にメモリアクセスしたことを検知して画面を更新することができません。

UART は IO 命令を契機に画面更新ができましたが、それができなくなりました。
画面のレンダリングはとても重い作業なので毎フレーム再描画するわけにもいきません。
解決策としては一定間隔で VRAM 領域をスキャンして変更があった場合に再描画するようにしました。
徹夜で調整した結果、まぁまぁのパフォーマンスが出てるようです。

モード 3 とモード 13 のみ実装しています。モード 12 は VGA = 640x480 を象徴するメジャーな画面モードのひとつではありますが、 MMIO がないと実現不可能なのでおそらく未来永劫実装しません。

PS/2 と JS のキーボード処理の闇

端末エミュレーターを廃止したのでキーボード入力もきちんと実装する必要が出てきました。
JavaScript ではキーイベントで結構細かいところまでキー入力の値が取れるのですが、そこは闇だらけでした。
環境によって取れる値が異なったり、別のキーに対して同じキーコードが割り当てられていたりします。
さらに、英語配列を基準にキーコードを決めてるようで、日本語モードだと記号の対応がぐちゃぐちゃでした。
完全に PS/2 キーボードをエミュレーションしようとすると記号キーの対応が死んでしまうので、 ASCII コードが取れるところは文字が入力したいと判断して ASCII コードを優先するようにしました。

TL; DR

これらの改修でゲームなんかもそれなりに動くようになりました。

f:id:neriring16:20190715001621p:plain

f:id:neriring16:20190715000906p:plain

f:id:neriring16:20190715001010p:plain

f:id:neriring16:20190715001050p:plain