借り初めのひみつきち

仮ブログです。移転先募集中

CD から OS を起動する

昔の OS は CDROM で提供されていました。

TOE は標準でフロッピーから起動しますが、さいきん入手難しくなってきたので CD 起動に対応したいと思います。

ロメオとジョリエット

CDROM のファイルシステムはたくさんの規格が複雑にからんでいます。 CDROM は特定の OS に依存せず他機種間でデータ交換が容易になるよう最大公約数的な仕様が決められたので、元の最小規格では FAT の 8.3 形式よりも厳しいファイル名の制限がありました。 また、興味深い特徴としてリトルエンディアンとビッグエンディアン両方のシステムに対応するために多くのフィールドはペアで用意されています。

しかし、それでは色々不便だったので拡張規格が登場しました。 主に Windows で使われている Joliet と、 un*x 系OSで使われている Rock Ridge などが主要な拡張規格です。 また、過去には Romeo という拡張規格もあったようですが現在ではマイナーな気がします。

Joliet は Volume Descriptor 自体が標準と別に用意されてディレクトリやパステーブルも全部独自になっていること、ファイル名が UTF16 になっていることなど、 IPL では扱いにくい特徴を持っているので今回は対応しません。

El Torito

PC で CDROM から OS を起動するには El Torito という規格に従います。

El Torito では起動情報の書かれた boot.catalog というファイルが必要ですが、 mkisofs が自動的に処理してくれるので通常気にする必要はありません。 用意する必要があるのは実際に起動するファイルだけになります。

El Torito ではハードディスクエミュレーション、フロッピーエミュレーション、エミュレーションなしの3種類の起動方法があります。

フロッピーエミュレーションモードは DOS など元々 CD 起動に対応してない OS を起動するためにイメージファイルを使って仮想フロッピーを作ります。 HD エミュレーションもイメージファイルを使って仮想ディスクを作りますが、実際に使われているのを見たことはないです。 エミュレーションなしは多くの OS で使われていて直接 CD から起動できます。

今回はエミュレーションなしで行きます。 mkisofs のオプションでいうと -no-emul-boot -b cdboot.bin と指定します。

CD 起動 IPL の書き方

CDROM のセクタサイズは通常 2KB なのでエミュレーションなしの起動ファイルのサイズも 2KB になります。 フロッピーやハードディスクの 512 バイトに比べると大きいですが、そんなに複雑な処理をする余裕もないのでディスクからシステムを読み込んで実行するだけのシンプルな IPL にします。

起動してレジスタの初期値を設定したら、まずは 16 番セクタの Primary Volume Descriptor を読み出します。

ISO9660 ではなぜか Volume Descriptor の開始セクタが 16 になっていて、それ以前のセクタは通常利用しません。

f:id:neriring16:20210228142820p:plain

Volume Descriptor は最初の1バイトが種類を指してその次に "CD001" というシグネチャがあります。シグネチャが "CD001" 以外になる規格もあります(DVD など) Primary Volume Descriptor にはルートディレクトリのディレクトリエントリが埋め込まれているので +0x009E と +0x00A6 にあるルートディレクトリの開始セクタとサイズの情報を取得します。

次に、取得した情報をもとにルートディレクトリを読み出します。

f:id:neriring16:20210228143156p:plain

ディレクトリを読み込んだらエントリを1つずつチェックしてシステムファイルを探します。 ディレクトリエントリ自体は可変長で最初の1バイト目がエントリサイズで、ファイル名は +0x20 、開始セクタは +0x02 、ファイルサイズは +0x0A からそれぞれ見つけることができます。

システムファイルを見つけたら該当するセクタからファイルを読み込んで実行します。

これで起動しました。(フロッピー起動と同じ見た目なのでスクリーンショット省略します)

FM TOWNS

FM TOWNS も CDROM から起動することができますが、 El Torito 規格ができる前だったので仕様が違います。

ISO9660では最初の 16 セクタを使用しませんが、 FM TOWNS は最初のセクタを IPL として読み込みます。 起動時点で El Torito と読み込むファイルが全く違うので機種専用の IPL になります。

基本的な処理は PC 用と同じ流れになります。 BIOS 呼び出す部分が違う程度です。

というわけで FM TOWNS でも CD 起動できました。

f:id:neriring16:20210228144302p:plain

UEFI

今回は対応しませんが、 UEFI で CD 起動する場合は通常のメディアと同じように /EFI/BOOT/BOOTX64.EFIブートローダーを置いておけば同じようにたぶん起動します。

いかがでしたか?

以上のように CDROM から TOE を起動することができるようになりました。 これでフロッピーが入手できなくなっても安心できそうな気がします。

MEGFS

古の MEG-OS は MEGFS という独自ファイルシステムをサポートしていました。

それ、 FAT でよくね?

MEGFS はファイル管理にファイルアロケーションテーブル (いわゆる FAT) を採用するなど FAT によく似た特徴を備えており、 FAT と MEGFS の違いは FAT と exFAT の違いと同程度のものでした。

細かい仕様は失われてしまったので筆者もよく覚えていませんが、 ファイルの読み書きをするために専用のツールが必要で面倒なだけでとくにメリットもなかったのですぐに使われなくなりました。

もうひとつの特徴

MEGFS では論理フォーマット以上に興味深い特徴として、特殊な物理フォーマットを採用していました。

実は、素のフロッピーディスクは普段使っているよりも多くの情報を格納することができます。

例えば、 2HD は 1.2MB もしくは 1.4MB というイメージがあるかと思いますが、ディスク本体は 2MB くらいのビットを書き込める磁性体が使われています。 両者の容量のギャップはどうして存在するかというと、物理メディアを回転してデータを読み書きするため、回転によるムラやヘッドのズレでデータが失われないようにする緩衝帯などの役割があります。

初期のドライブは回転ムラも大きかったようで、標準的なフロッピーのフォーマットは緩衝帯を大きめにとって容量が決められました。 やがてドライブの性能が向上してくると緩衝帯が過剰になってきました。

また、当時日本の PC でよく使われていた 1.2MB の 2HD では本来ドライブもメディアも 80 シリンダまで使える状態であえて 77 シリンダに制限して使われていました。*1

そこで、 MEGFS はフォーマット時のパラメータを調整して PC-98 で標準的に 1.2MB になるディスクを 1.4MB で使えるようになっていました。

IBM PC 2HD NEC PC98 2HD MEGFS 1.4M
容量 1440KB 1232KB 1440KB
バイト/セクタ 512 1024 1024
RPM 300 360 360
C 80 77 80
H 2 2 2
R 18 8 9
N 2 3 3

IBM PC の 1.4MB と MEGFS 1.4MB は容量が同じですが物理フォーマットが違います。*2 このように比較すると NEC PC98 の 2HD をベースに 1.4MB 使えるように拡張したことがわかるでしょう。

ゆめのあと

このように頑張って容量稼ぎをしていた MEGFS ですが、本格的に IBM PC の時代がやってくると普通に 1.4MB 使えるようになり、フロッピーの時代の終わりも見えていた当時フロッピー以上の大容量のメディアでは FAT 同様に問題があることが既に分かっていたファイルシステムを発展させるモチベーションも乏しく、 MEG-OS の開発終了とともに MEGFS もしずかに終了しました。

*1:5インチだったか8インチだったかで既に使われていたフォーマットと合わせたと言われています

*2:地味ですが、容量が同じだったので論理フォーマットレベルでは両者を区別できず、イメージファイルは同じものが使えました

新しい自作 OS 始めました

前回の日記で作り始めたもの、それは新しい OS でした。

概要欄

今のところ特徴を myos と比較すると以下のようになります。 myos のサブセット的な感じになっていて一部ソースを流用しています。

MYOS TOE
コードネーム myos toe
アーキテクチャ x86-64 x86
プラットフォーム PC IBM PC, PC-98, FM Towns
動作モード ロングモード プロテクテッドモード
ページング 部分的 なし
セグメンテーション 32bit App のみ 未定
ブートモード UEFI Legacy BIOS
SMP サポート なし
カラーモード ARGB32 8bit インデックスカラー
透過 アルファブレンディング クロマキー

主な特徴

今まで筆者の作った OS の中ではじめてページングを使わない純粋なプロテクトモードで動作します。 これはメモリ保護に MMU を使うのは辞めてみようというという myos の考え方の延長線上にあります。

また、ページングに対応していない拙作 PC エミュレーターで動かしたかったという理由もあります。 *1 この OS を開発したおかげで拙作 PC エミュレーターのバグもいくつか発見・修正されています。笑

f:id:neriring16:20210206215627p:plain

MEG-OS Lite を Rust で再実装したものに近い感じとなっていて、 オリジナルの MEG-OS Lite と同様に NEC PC98 や FM Towns でもほぼそのまま動作します。 (実機の動作保証はありません)

f:id:neriring16:20210206220355p:plain

f:id:neriring16:20210206220403p:plain

386 と 486 の壁

x86 32bit モードは 386 で完成したと思われがちですが、実は 386 と 486 には結構違いがあって 386 には近代的な同期の命令が不足しています。 ターゲットを 486 以降にした方が簡潔になる一方、 486 命令を正しく実装していないエミュレーターもいくつか発見していて、 最終的なターゲットを 386 にするか 486 にするか判断が難しいところです。

myos はどうなるの?

myos を実装始めた頃は Rust を覚えたてのよくわからない時に設計したので、今考えると未熟な部分もあります。 toe は myos に近いアーキテクチャで Rust の理解がより深まって洗練されている部分もあるので、いずれは myos にバックポートしようと思います。

今後

現状は実質 myos のサブセットとなっていますが、最終的にどんな方向に落ち着くか若干まだ未定となっています。

toe のますますの発展をお祈りします。

*1:件のエミュレーターはページング前提の構造になっておらず、もしページングに対応するなら最初から作り直した方が早いと思ってます

妖精さんとなかよくなるほうほう

年初まで x64 や WebAssembly で Rust を色々いじってましたが、少しお休みして x86 でコードを書いてみようと思います。

動かす環境はベアメタル ʕ•ᴥ•ʔ になりますが、 Rust はベアメタルの適切なターゲットがありません。 CPU さえ合ってれば OS はどうでも良さそうだったのでメジャーなターゲットでいくつか試してみました。 しかし、どうやらターゲットごとに適切なリンカーが必要になるようです。

リンカーに困ったら LLVM

ということで、 LLVM をインストールして LLD を読み込むように指定しました。

具体的には .cargo/config に

[target.i586-unknown-linux-gnu]
linker = "/opt/homebrew/opt/llvm/bin/ld.lld"

みたいな記述を加えます。 これ、環境依存ですよね・・・

いかがだったでしょうか?

ということで、 ELF 形式のバイナリ出力できるようになったのでローダーを作るための準備をします。

Program Header と Section Header

ELF には Program Header と Section Header というよく似た2種類のヘッダーがあります。何が違うでしょうか?

ELF というのは Executable and Linking Format の略で、アセンブルコンパイルの出力である .o ファイルも、それらをリンクした実行ファイルも両方サポートしちゃう規格だぜということになります。

Section Header は主に .o ファイルの状態で使うヘッダーで、セクションの役割ごとに細かく分かれています。 Program Header はリンクされた実行可能ファイルだけに存在するヘッダーで、 Section Header に比べると実行時にメモリに読み込むための最低限の情報だけにまとまっています。 つまり、通常の ELF ローダーは Program Header だけ見れば OK ということになります。

Section Header では別のセクションに分かれていても、アドレスがすぐ近くにあって属性が同じ場合 Program Header では同じセグメントにまとまっていることがよくあります。

Program Header には、セグメントの属性、ファイル上の位置とサイズ、メモリ上のアドレスとサイズ、などの情報があるので、それらをパースして実行に必要なアドレスにセグメントの内容をコピーしていきます。

リロケーションがなければこれだけでロードできます。簡単ですね。

GOT - 神ではない

ELF には GOT というテーブルがあります。これは PIC/PIE というリロケーショナルなコードの実行に必要な ELF 特有のデータ構造となります。

アーキテクチャによっては GOT がないとまともに動かせない場合もあったりした気がしますが、 x86 で配置固定のコードを書く場合は全く必要ありません。 むしろ GOT へアクセスするために無駄な機械語が生成されてメモリ消費的にも実行速度的にも無駄です。

ということで、 GOT 使わないコードに書き換えましょう。

.cargo/config に

[build]
rustflags = ["-C", "relocation-model=static"]

のような記述を追加すると配置が完全に固定されたオブジェクトになる代わりに GOT を一切使わなくなります。

配置アドレス決まってるしこれでいいのです。

おめーのせきねぇです?・ヮ・

このようにして ELF さんと仲良くなりましたが、そもそも ELF って割といろんなメタデータが含まれていてバイナリが大きくなります。 デバッグには便利なメタデータですが、実行時にはセクションの配置情報とコード・データセグメントの内容以外必要ありません。 今回のターゲットは割とメモリをタイトにしたいので無駄なメタデータは削減したいです。

ということでバイナリを変換します。

objcopy でバイナリに変換した場合はメモリ上に展開したイメージそのまま出力されて ELF の状態から失われる情報量が多すぎます。 それに実はセグメントの隙間のパディングとか bss もそのままバイナリに出力されるので効率もあまりよくないです。 一方、 strip した場合は ELF として汎用的な情報が多く残っているのでもうちょっと削減したいです。

折半案として独自のツールを作ってセグメントの配置情報と内容だけ別ファイルに抜き出して独自のバイナリ形式にすることにします。 何年か前に似たようなことやったな・・・

ロードに必要な情報をまとめてみましょう。

セグメントの属性

全てのセグメントが読み書き実行可能でその他のメタデータなどがない場合は不要ですが、今回は念の為最低限の情報を残します。

ファイル上のセグメントデータの位置

ファイル上のどこからセグメントの内容を読み込めばいいのか判断するために必要ですが、 最初のセグメントがヘッダの直後につづき、2つ目以降のセグメントは以前のセグメントデータの直後に続いてるというルールがある場合は不要です。

ファイル上のセグメントデータのサイズ

実際に何バイトコピーすればいいのかわからないので必要な情報です。

メモリ上のアドレス

メモリ上のどこに配置すればいいのかわからないので必要な情報です。

メモリ上のサイズ

bss のように初期値 0 のデータを含む場合はファイル上のセグメントサイズとメモリ上のセグメントサイズが異なるので必要になりますが、 全てのセグメントが連続していてファイルヘッダーで bss のサイズがわかる場合、この情報は不要です。

アライン情報など

仮想メモリを使ってストレージ上にスワップする場合、リロケーションをする場合などにセグメントのアライン情報が必要になる場合があります。 現状必要ないし、今後も必要になる可能性が低いのでカットします。

自分の足を撃ち抜く方法

以上のように必要な情報だけを抜き出した単純なヘッダに変換したバイナリができました。 いよいよローダーを作ります。

世の中には ブートローダーをほぼ Rust だけで作ってしまう強者 もいるようです。 しかし、低レベルすぎる操作は高級言語だと逆に使いづらい面もあるかと思ったので、ローダー部分はアセンブリで書くことにしました。

    movzx edx, byte [ebp + N_SECS]
    lea ebx, [ebp + OFF_SECHDR]
    mov esi, edx
    shl esi, 4
    add esi, ebx
.loop:
    mov al, [ebx]
    and al, 0x07
    jz .no_load
    mov ecx, [ebx + S_FILESZ]
    jecxz .no_load
    mov edi, [ebx + S_VADDR]
    rep movsb
.no_load:
    add ebx, SIZE_SECHDR
    dec edx
    jnz .loop

結構シンプルですね。 出来上がったバイナリを自作 PC エミュレーターで動かしてみます。

f:id:neriring16:20210119232112p:plain

これで x86 のベアメタルで Rust が使えるようになりました💪

ぬるぽ警察24時

myos では Null Pointer Exception は発生しません。

理由は2つあって、言語に Rust を採用しているというのと、 Null Pointer Exception が発生するようにページングを設定していないからです。

事件編

Rust には Null Pointer Exception によく似た別のエラーがあります。

それは、 Option<T>None に対して unwrap() することで発生する panic です。

Rust では unwrap() はお行儀の悪い方法なので基本的に他の手段を検討するべきです。 しかし、言語仕様上変数や戻り値を Option にしないといけないことがしばしばあり、本来 None が返ってくることはないのでハンドリングが面倒で unwrap() を使ってしまいます。*1

そして、想定外の現象が起きた時に、本来起こり得ないはずの panic が発生します。

最近それが発生しました。 WebAssembly で特定の条件を満たすと current_thread の current_personality を取得する処理で発生します。

WebAssembly のシステムコール呼び出しをするとき、システムコール関数はランタイムのインスタンスを持っていないので current_thread の current_personality から取得する必要があります。 システムコールを呼び出すのは WebAssembly の内部だけなので current_personality (Option<Box<dyn Personality>>) が設定されているはずです。

しかし、現実には稀に None を返して unwrap() に失敗しました。

解決編

さて、 current_thread を知っているのは誰でしょうか?もちろんスケジューラです。

ただし、ちょっと注意が必要です。

myos のスケジューラーは SMP に対応していて、それぞれのコアが別々のスレッドを実行しています。 つまり、コアごとに実行中のスレッドを管理する必要があります。

現在実行中のスレッドを調べるには、現在実行中の CPU コアの ID を取得する必要があります。 そして、コア ID からコア個別のデータを探して現在実行中のスレッドを特定する必要があります。

以前の myos ではこの処理で割り込みを禁止していませんでした。 それによってどんなことが起きるでしょうか?

現在実行中の CPU コアを特定してコア個別のデータから現在実行中のスレッドを調べる一連の処理の途中でたまたま割り込みが発生した場合、コンテキストスイッチが発生してスレッドキューに戻されることがあります。 そしてスレッドキューに実行待ちのスレッドが多かったりたまたま別のコアがコンテキストスイッチをした場合、最初に実行していたコアとは別のコアでスレッドが復帰する可能性があります。

これらの条件が重なった時、現在実行中のコアとは別のコアのデータを読み出し、現在実行中のスレッドを誤判別するという現象が発生します。

色々な偶然が重ならないと発生しないので確率は低いですが、割り込みやコンテキストスイッチは一秒間に何回も実行しているのでいつでも発生する可能性があります。

今までこのバグが発覚しなかったのは、そもそも現在実行中のスレッドを取得する処理がそこまで頻繁に実行されなかったためです。 WebAssembly から頻繁に API 呼び出しをして画面を書き換えるテストアプリの実行中にやっと発見されました。

教訓

そもそも現在実行中のスレッドを取得するだけの処理で割り込み禁止したり実行中のコアを調べるのは少々複雑すぎな気がしませんか?

毎回割り込み禁止にするのは良くないので、スタックポインタから逆算できたり通常変更しないレジスタから取得できるようにした方がいい気もします。

*1:似たような事例として Result の unwrap もあります

myos の描画アーキテクチャ

myos のウィンドウ描画アーキテクチャについて解説します。

執筆時点での情報なのでバージョンによっては詳細が異なる場合があります。 なお、ここにあるのはカーネルの構造なので、アプリケーションレイヤーではラッピングしたオブジェクトなど詳細は異なります。

クラス名やメソッド名が違いますが myos の基礎となった moe も類似した構造になっています。

Bitmap

Bitmap は画像だったりバッファだったり画面そのものだったり myos が色々な場面で利用しているグラフィックスオブジェクトで、サイズやピクセルの配列などの情報を持っています。 Bitmap に対する描画命令もたくさんあります。

また、ウィンドウバッファの内容場合、枠線やタイトルバーを除外したビットマップビューという特殊な状態の Bitmap を扱うことがあります。

WindowManager

WindowManager はウィンドウ制御に関するマネージャクラスで、以下のようなメンバーを持っています。(一部抜粋)

main_screen

実際のスクリーンに相当するビットマップオブジェクトです。 ブートローダーから渡された EfiGraphicsOutputProtocol の値を使って初期化しています。

    main_screen: &'static Bitmap,

off_screen

実際のスクリーンと同じサイズのビットマップでオフスクリーン描画に使います。 myos ではアルファブレンディング処理のために一旦全てのウィンドウを重ねて描画する必要があるため(現在はほぼ全てのウィンドウが影付きのため)、いったんこのバッファで合成して描画します。

    off_screen: Box<Bitmap>,

実装上のポリシーとして、現状このバッファは複数のスレッドから同時に描画する可能性があり、一時的に画面が乱れることがあります。(半透明のウィンドウが濃く描画されるなど) この解決方法はいくつか考えられますが、実装コストや速度低下の見返りに画面が一時的に乱れる現象を許容しています。

sem_redraw

sem_redraw にシグナルを送信するとウィンドウマネージャがアクティブになります。 主にマウスカーソルを移動した際の再描画に使われます。

    sem_redraw: Semaphore,

root window

他の全てのウィンドウの最背面に位置するウィンドウでいわゆるデスクトップです。 ウィンドウヒエラルキーのルートになります。

    root: Option<WindowHandle>,

Rust の言語仕様上現行は Option で定義されています。

pointer window

マウスポインターの描画に使われるウィンドウです。他の全てのウィンドウよりも最前面に表示されます。

    pointer: Option<WindowHandle>,

Rust の言語仕様上現行は Option で定義されています。

ウィンドウヒエラルキーとウィンドウレベル

画面に表示されているすべてのウィンドウはウィンドウヒエラルキーという階層を持っていて、ウィンドウの表示・非表示はウィンドウヒエラルキーへの追加・削除と同義になります。 デスクトップウィンドウが再背面、マウスポインターが最前面で、それ以外のウィンドウはその中間にあります。

また、全てのウィンドウはウィンドウレベル (WindowLevel) を持っていて、レベルの高いウィンドウの方が前面に表示されます。 ウィンドウレベルが同じ場合、後から表示された(ウィンドウヒエラルキーに追加された)ウィンドウの方が前面に表示されます。

一般のウィンドウは WindowLevel::NORMALWindowLevel::FLOATING のどちらかを選択することができます。システムが管理している特殊ウィンドウではそれ以外のレベル (WindowLevel::ROOTWindowLevel::POINTER など) もあります。

WindowHandle

WindowHandle はウィンドウのハンドルで、どのウィンドウに対する操作なのかをウィンドウマネージャと他のプログラムの間で情報交換するために使います。 WindowHandle の実体はただの整数値です。

RawWindow

RawWindow は実際のウィンドウ管理に使われているオブジェクトです。 アプリケーションから直接アクセスする方法はありませんが、 WindowHandle が有効なウィンドウを指している場合にウィンドウマネージャ内部で RawWindow に変換して処理します。

ウィンドウの内容は bitmap というメンバーに描画され、その他ウィンドウの位置やサイズなどに関する情報も持っています。

ウィンドウの描画は3ステップあります。

フレームの描画

システムが必要と判断したときに RawWindow.draw_frame() で枠線やタイトルバーを描画します。

ウィンドウ内容の描画

アプリが WindowHandle.draw() などを呼び出すと RawWindow.bitmap から枠線やタイトルバーを除外したビットマップのビューを返却されるのでその中でウィンドウ内容を描画することができます。

画面への反映

WindowHandle.set_needs_display() を呼び出してイベントループが WindowMessage::Draw を受け取った場合、 WindowHandle.set_needs_display() を呼び出した後に WindowHandle.refresh_if_needed() を呼び出した場合、 WindowHandle.draw() を呼び出した場合、 ウィンドウ本体を移動した場合、 ウィンドウの上にあるウィンドウの状態が変わってシステムで再描画が必要と判断された場合などに画面に描画します。

最終的に RawWindow.draw_to_screen() の中で RawWindow.draw_into() を呼び出して RawWindow.bitmap の内容をオフスクリーンバッファに合成し、最後にメインスクリーンに転送します。

つまり通常の描画は RawWindow.bitmapoff_screenmain_screen というトリプルバッファになり、さらにアプリ側で個別にバッファを設けている場合はクワドロプルバッファになります。

このように myos の描画は複数のバッファを経由するため、直接描画する場合に比べて若干ラグがあります。

Rust の Null Pointer Optimization

古き良き C 言語では NULL ポインターがよく使われましたが、 NULL の発明者は10億ドルを超える莫大な経済損失を引き起こしたとのちに後悔しました。 モダンな言語は NULL に対する安全性を担保する仕組みを持っています。

Rust では Null 安全性のために Option<T> という型をよく使います。

Option<T>

Option<T> は、 NULL のような値を使わずに値が存在する場合と存在しない場合を明確に区別するために使います。 なぜこれで Null 安全性を確保できるかというと、 Option<T>T は明確に別の型になっているので、値が Null かどうか検証されてない状況でコードが動いてしまう危険な状況を回避できます。

Option<T> の実体は以下のような単なる enum です。

pub enum Option<T> {
    None,
    Some(T),
}

Option<usize> の実際のメモリ配置を考えてみると、 NoneSome を判別するための usize 値、 Some(v) の場合の値 v の2つの usize 値が必要です。

すべての Option<T> でこのようなメモリ配置を採用するととても嵩張ってしまいますが、実は多くの場合この配置を使いません。 それが Null Pointer Optimization と呼ばれている最適化です。

Null Pointer Optimization

Rust では有効な参照、 NonNull<T>、あるいは NonZeroUsize のような型は絶対に Null あるいは 0 の値を取りません。 これらの値を Option<T> でラッピングした場合、実際のメモリ上では Some(v) の場合は元の値そのまま、 None の場合は値 0 を使います。 NoneSome の判別は値が 0 かどうかで判別できますし、 Some(v) だった場合は元の値をそのままアンラップで取り出せます。

内部でこのような最適化を行うことで、 Option<T> は実際のメモリ上の値は T と同じ領域しか使わないように節約しながら Null 安全性を担保することができます。

なお、この最適化は実際には Option に限定されるわけではなくいくつかの条件を満たした他の enum でも同様の最適化が行われるようです。

という事までは以前から知っていました。

Option<char> の場合

Option<char> の場合を考えてみます。

char 型は任意の Unicode コードポイントリテラルなので 0 (U+00000) になり得ます。 一方、現行の UnicodeU+10FFFF までが有効なコードポイントです。

つまり、 char 型は 0x0000_0000 〜 0x0010_FFFF までの範囲を取ることができ、 0x0011_0000 〜 0xFFFF_FFFF の範囲の値にはなることができません。

実際に Rust で Option<char> を使ったコードをビルドして出力バイナリをみていたところ、 1114112 という値と比較する処理が見つかりました。 1114112 というのは 0x0011_0000 のことを指しています。

つまり、 Option<char> では char 型として不正な値の 0x0011_0000 を None の代わりに使うことで Null Pointer Optimization と同じような最適化をしていることがわかりました。

いかがだったでしょうか?

Rust でよく使われる Option<T> には追加のリソースをほとんど使わずに Null 安全性を担保するための高度が仕組みがあることがわかりましたが、 Option<char> にも同様の少しトリッキーな最適化がされていることもわかりました。