Open9

Writing an OS in Rustをやる

YuheiNakasakaYuheiNakasaka

A Freestanding Rust Binary

OSに一切依存せず実行できるバイナリを作る準備をする。

panicを実装しないとビルドが通らないので書く。

ランタイムが使えないのでmainは消す。代わりに多くのOSのエントリポイントとして使われるfn _startを実装。

デフォルトだとOSのランタイム(ここではC runtime)で実行するようにビルドされてしまうのでベアメタル環境としてthumbv7em-none-eabihfを追加する。この環境向けにビルドするとうまくいく。

YuheiNakasakaYuheiNakasaka

A Minimal Rust Kernel

BIOSによるkernelの起動

BIOSを起動時のハードウェア周りのシステムセットアップをやつやつ。
マザーボードのBIOS -> flash memoryに移動。テストの実行と初期化。その時にブートディスク(OS)を探してブートローダー(起動時に動くプログラムでOSを読み出して実行する)に転送。ブートローダーがカーネルイメージの場所を決めてメモリにロードする。またCPUを16bit リアルモードから32bit プロテクトモード・64bitロングモードに切り替える。メモリマップのような情報をBIOSから取得してOSカーネルに受け渡す。自前で実装はせずこの章ではbootimageを使う。

マルチブートスタンダード

ブートローダーとOSのインターフェースを標準化するもの。GNU GRUBが最も有名な実装。マルチブートヘッダーファイルを組み込むだけで対応させられるので便利だが、いくつか問題もある。なので自前で実装はせずこの章ではbootimageにマルチブートの機能を追加する方向で進める。

A Minimal Kernel

Rustはnightlyのバージョンが良いとのことなのでrustup override set nightlyを実行。

まずはHello World!を出力できるdisk imageを作成することをゴールにする。

最初はベアメタルのターゲット用のカスタムを色々やっていく。

llvmのビルドターゲットをベアメタル用にカスタムする。

linkerはLLD(LLVMのリンカ)を使う。

"disable-redzone": true,の追加はred zoneを避けるため。ちなみにred zoneはスタックポイントの下の128bytesの領域を使ってしまうSystem V ABIによる最適化。しばしば例外やハードウェア割り込みを伴う大きな問題につながるのでオフにする。

SIMD(複数命令を単一命令で実行できるための設計方式)はオフにする。SIMDをオンにしておくと割り込みなどが発生するたびに割とデカめの命令の状態をいちいちメモリやディスクに保存してリストアしてを繰り返さないといけなくなりパフォーマンス問題が発生してしまうので。

Rust Compilerに含まれてるcoreライブラリはカスタムターゲートに対応してないのでカスタムターゲット向けに再コンパイルしないといけないっぽい。build-stdという機能を使う。この標準ライブラリの再コンパイルはnightlyビルドでないと使えない。また再コンパイルするのでソースコードが必要となるためrustup component add rust-srcをする。

メモリ関連の組み込み関数

ベアメタルでCライブラリを使えないのでいくつかのメモリ関連のいくつかの関数が使えない。よってno_mangleを使って自前実装する。とはいえメモリ周りの実装を自前でやるのは最初は危険なのでbuild-std-featuresに含まれる同様の関数を使うようにする。ビルドオプションで有効にするとbuild-std-featuresに含まれるmem関連の関数が#[no_mangle](ビルドされた時に関数名が最適化されて別名にならずソースコードのままでビルドされるようにするアノテーション)になって利用できるようになる。

スクリーンへ出力

VGA Text Bufferを使う。HELLO WORLD!のstringをVGA bufferに変換する。

カーネルの実行

bootloaderとbootimageをcargoでインストール。
bootimageはカーネルのコードとbootloaderをコンパイルしてリンクし、QEMU(VM emulator)で実行可能disk imageを作ってくれる。

QEMUはhomebrewでinstallした。結構時間かかる。

YuheiNakasakaYuheiNakasaka

VGA Text Mode

VGA Text Modeをメモリ安全に利用するための実装をやっていく。

The VGA Text Buffer

テキストを出力するにはVGA text bufferに直接書き込む必要がある。

VGA text bufferはmemory-mapped IO(memoryと一対一になってる)のでメモリへのアクセス=VGA text bufferのアドレスへの直接アクセスとなる。

A Rust Model

VGA Text Bufferの読み書き用のModuleを作成する。

Color

文字の色と文字を表す構造体を作っていく。

repr(transparent)はstructの指定のデータ型と同じレイアウトになることを保証するために使用する。

repr(C)はstructのfieldが定義順になることを保証する。

Volatile

Rustコンパイラの最適化でVGA Bufferは意図せず消される可能性があるので明示的にvolatileであることでコードで示さないといけない。

volatile crateを使う。

Newlines

改行は文字を上に移動させて、新しい行は空白で埋めることで実現させる。

A Global Iterface

staticのような変数はコンパイル時に初期化される。これをConstant Evaluationという。通常は割り当てる値側にconstを用いれば解決するが、Bufferでは直接ポインタを弄ってるのでコンパイル時に生のポインタを参照に変換できない。

lazy_statticを利用するとこれを解決できる。コンパイル時ではなく最初に利用する時に一度だけ初期化されるようにする仕組み。

このままだとstaticなのでmutableな値を出力するのに使えない。mutable static、static mut、interior mutabilityを提供するRefCellやUnsafeCellなど色々あるがどれも非推奨だったりデータレースの危険があったりで使いにくい。

そこでMutexを使ってinterior mutabilityを得たい。が、このkernelにはblockingがまだサポートされてないのでspinlockというループを使ってひたすらロックを待つシンプルな仕組みを用いる。

Macro

文字の出力をどこでも使えるようにするためにマクロを定義する。

#[macro_export]を使うとcrate::に定義されるのでどこからでも使えるようになる。

YuheiNakasakaYuheiNakasaka

Testing

#[no_std]なので標準ライブラリが使えない。よって標準のtestingライブラリも使えないのでcustom_test_frameworkを使う。

テスト結果はQEMUに先ほど作ったprintln!マクロで表示させる。

Exiting QEMU

QEMUを手で消さないといけないのだるい。が、正攻法でいくとAPM(OSのコントロールシステム)やACPI(電源システムをコントロールする仕組み)を実装しないといけない。これは流石にきついのでQEMUにisa-debug-exit deviceを通じてゲスト側からexitさせる方法を利用する。

I/O Ports

周辺機器とCPUのやり取りに関しては memory-mapped I/O と port-mapped I/Oがある。前者はVGA text bufferでやったようにmemoryのアドレスに直接書き込む方法。後者はI/O busを使ってCPUのin,out命令で行う。isa-debug-exit deviceはport-mapped I/Oを使う。

Printing to the Console

QEMUにテスト情報等を出力してたがcargo testしたら即QEMUがshut downするので不便。コンソール側に出力させたい。

Serial Port

データを送受信するためにUARTsと呼ばれるシリアルポート(device間でbit情報をone to oneで送受信するインターフェース)を利用する。

Timeouts

無限ループをしてしまった際にタイムアウトを設定できた方がいいので設定する。デフォルトは5分らしい。

YuheiNakasakaYuheiNakasaka

CPU Exceptions

CPUの例外について。20種類以上のCPUの例外がある。例えば、

  • ページフォールト: 不正なメモリアクセス
  • 不正なオペコード: 存在しないCPU命令を実行
  • protection fault: 予約済みレジスタに書き込もうとしたりユーザーレベルでadmin専用領域にアクセスしようとしたり
  • ダブルフォールト: 例外ハンドラを呼び出してる時に別の例外ハンドラも呼び出した時に発生する。また存在しない例外ハンドラを呼ぼうとした時も同じく。
  • トリプルフォールト: ダブルフォールトの時にさらに例外ハンドラ呼び出しをした時に発生。この時はたいていOSがリブートする。

などなど。

The Interrupt Descriptor Table

例外の捕捉と対処について。IDT(interrupt descriptor table)という16byteの構造の例外対処ハンドラを利用する。

IDTでは不正なオペコードならindexは6、ページフォールトならindexは14というふうに決まっている。

例外が起きた時、CPUは概ねこんな感じで動く。

  • 命令ポインタ、RFLAGS(CPUの現在の状態を表すレジスタ)を含むレジスタをスタックにpushする
  • IDTから一致するエントリ(ページフォルトなら14)を読み込む
  • 存在するエントリかチェックする。しないならダブルフォルト。
  • エントリが割り込みゲート(bit 40がセットされてない)ならハードウェア割り込みをオフにする
  • 特定のGDTセレクタをCSセグメントにロードする
  • 特定のハンドラ関数にジャンプ

extern(外部のAPIを呼び出すことを示す。extern "x86-interrupt"はx86-interruptとやりとりすることを定義してる)

The Interrupt Calling Convention

例外と関数呼び出しの違いは全ての命令で発生しうるかどうか。

関数呼び出しにはレジスタのどこにパラメータを配置しどのような結果が返されるかの詳細なルールがある。これをCalling Conventionと呼ぶ。

Calling Conventionにおいてレジスタはプレザーブドレジスタとスクラッチレジスタに分けられる。前者は関数が実行される時に一旦stackに状態を保存し、returnされる前(関数を抜ける前)に上書きしたりしたとしてもレジスタを元の状態に戻しておかないといけない。一方で後者はその制限がない。

例外呼び出しではコンパイル時にどんな例外が発生するかはわからない。なので全ての例外呼び出しにおいてレジスタの状態を上書きされた部分に関しては全てstackに保持しておいてreturn時に全て元に戻す(上記で言うところのプレザーブドレジスタ方式)。

The Interrupt Stack Frame

割り込み時のスタックフレームについて。

https://os.phil-opp.com/cpu-exceptions/exception-stack-frame.svg

Behind the Scenes

x86 calling conventionsは例外処理の複雑な処理を隠蔽する便利な抽象。引数の取得、iretqを使ったreturn(通常の関数呼び出しのreturnで使うretは使えない)、エラーコードの処理、スタックの再割り当てなど。

Implements

ブレークポイント例外の実装からはじめる(プログラムを一時停止させるやつ。デバッガーとかでよく見るあれ。CPUの命令を一時的にint3で置き換えることで実現する)。

IDT(stack)はCPUからプログラム実行中どこからでもアクセスされる可能性があるのでライフタイムは'staticが望ましい。

static mut IDT: InterruptDescriptorTable = InterruptDescriptorTable::new(); // 読み書き可能でヒープに確保
pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        IDT.load();
    }
}

これはlazy_static!マクロで書くと初回アクセス時にのみ初期化されるようにできる。VGA bufferでやったやつ。

ちなみにヒープとスタックのおさらい。ヒープはざっくり自由にサイズを確保できるメモリ領域。スタックは決められたサイズが割り当てられたメモリ領域。ヒープはサイズが可変のものやあらかじめこちらでライフタイムをハンドリングしたいものなどを割り当て、スタックはライフタイムが短いもの(ローカル変数とか)を割り当てるイメージ。本格的にCを書いてきてないのでこの辺弱すぎる...

YuheiNakasakaYuheiNakasaka

Double Faults

What is a Double Fault?

ダブルフォールトはCPUが例外処理に失敗した時に発生する例外。IDTに存在しない例外が発生した場合などに発生する。ダブルフォールトを処理できないとトリプルフォールトになる。これはハードウェアのリセット(リブート)になってしまう。

A Double Fault Handler

breakpointの時と同様にIDTにexception handlerを登録する。処理を止めて欲しいので-> !をreturnしpanicさせる。

ほとんどのDouble Faultsはこれで対応できる。

Causes of Double Faults

CPUが例外処理に失敗する時をより厳密に定義。

  • IDTにハンドラが登録されてない
  • ハンドラがスワップされてしまった
  • ハンドラ自体に例外が紛れ込んでいた
    等々...

AMDのマニュアルに厳密な定義がある。この定義の順番で発生した例外がDouble Faultsとなる。

Kernel Stack Overflow

カーネルがスタックを超えてガードページ領域までアクセスしてしまったらどうなるか？

この場合まずページフォールトが発生する。CPUはIDTからハンドラを探す。そしてinterrupt stack frameをstackにpushしようとする。しかしstack pointerは存在しないガードページ領域を指している。よってまたページフォールトが発生し、ダブルフォールトとなる。が、CPUはこのダブルフォールト用にスタックにinterrupt stack frameを書き込もうとする。しかしそこはまたガードページ領域であるのでついにはトリプルフォールトが発生する。

Switching Stacks

上記を防ぐためにx86_64は事前に定義されたIST(Interrupt Stack Table)という専用のスタックをハードウェアレベルで保持している。

The IST and TSS

ISTはTask State Segmentと呼ばれるレガシー機構の一部。TSSにはPrivilege Stack TableやI/O Map Base Addressなんかもある。

Creating a TSS

まだメモリ管理システムがないのでstatic mutとunsafeで擬似的にメモリを確保する。

また、CPUにこのTSSを使わせるように設定するのがちょっとトリッキーで、Globack Descriptor Table(GDT)とLoad Task Register(ltr)命令を利用する。

The Global Descriptor Table

Global Descriptor Table (GDT)はページングがデファクトになる前のメモリのセグメンテーションのデファクトだった。GDTはプログラムをそれぞれ独立させるための古いアーキテクチャである。

この辺のOSの詳しい話についてはOperating Systems - Three Easy Piecesに書かれているらしいので後で読む。

The final Steps

新しいGDTをレジスタに認識させるようにする。

セグメントレジスタをリロードし、TSSを読み込ませ、IDTをアップデートする。これでCPUは新しいISTを参照するようになるのでダブルフォールトをハンドリングできる。

YuheiNakasakaYuheiNakasaka

Hardware Interrupts

Overview

割り込みはkernelがチェックするのではなく割り込みを起こす側(キーボードとか周辺機器等)が通知して、それをkernelがキャッチして処理する仕組み。

これらの通知はseparate interrupt controllerがまとめてからCPUへ引き渡されるようになっている。

またそれぞれの割り込みには優先度が設定されている。keyboardよりtimerの方を優先するといった感じで。

例外と異なる点としてはこの種の割り込みは非同期で実行されることである(=並列性)。Rustではownershipモデルのおかげでmutableなグローバルstateへのアクセスが禁じられているので並列な処理はバグになりづらいが、それでもdead lockの危険はあるので考慮が必要である。

The 8259 PIC

Intel 8259は1976年に登場したProgrammable Interrupt Controller(PIC)である。APICという新しいPICが今は使われているがまだ後方互換性の観点でIntel 8259も一部で使われている。Intel 8259はセットアップも容易なのでこれを実装していく。

一つのIntel 8259は8つの割り込み線を持っている。一般的なシステムでは2つのPICが設置されていて、セカンダリのPICの1つの割り込み線がプライマリのPICにつながっている。

15本の線は固定でマッピングされている。それぞれのPICはコマンドportとデータportという２つのI/O portsで設定される。プライマリのPICは0x20がコマンドportで0x21がデータport。セカンダリのPICは0xa0がコマンドportで0xa1がデータport。

Implementation

PICのデフォルトのマッピングナンバーは0~15だが、これはすでにCPUの例外で使われているレンジ。なのでこのままでは不便なので再定義する。例外は32個(0~31)なのでPICには32~を割り当てる。

PICの実装にはpics8259というcrateのChainedPicsという構造体を使う。

Handling Timer Interrupts

Timer用の割り込みハンドラの登録をする。普通の例外と同じようにすればok。

End of Interrupt

PICは割り込みの処理が終了したことを知らせるEOI命令を待っている。

Configuring the Timer

Programmable Interval Time(PIT)

Deadlocks

ここまでの実装でタイマーの割り込みにより並列性を獲得したが、まだデッドロック(スレッドが開放し得ないlockを獲得しようとして起きるバグ)の可能性はある。

例えばWRITERからのprint!による書き込みで_startからVGA bufferへ書き込もうとして例外が発生した場合。WRITERはlockされたままだが例外ハンドラでもprint!を使っているので元のWRITERのlockがfreeになるのを待ってしまう。一方_startも例外ハンドラの処理が終わるのを待ってしまうのでデッドロックとなってしまう。

これを避けるためにはMutexのlockを使っている時は例外を発生させないようにする。

Fixing a Race Condition

テストでレースコンディション(競合状態)が発生するので直す。WRITERのロックをテスト中開放しないようにして例外も止める。これで意図しない割り込みを防げる。

The hlt Instruction

_startでloop()を使っているのでCPU使用率は常にほぼ100%。エコじゃないのでCPUを完全に止める方法を持てるようにする。

Keyboard Input

キーボードの割り込みに対応 = キーボード入力をできるようにする。

Reading the Scancodes

scancodeはどのキーをキーボードで押されたかを表すデータ。これをKeywordのI/O portを通じて読み込む。

Interpreting the Scancodes

今度は読み込んだscancodeを変換しないといけない。変換の仕方にはIBM XTとIBM 3270 PCとIBM ATがある。PS/2 KeyboardはデフォルトでIBM XTを使う。この実装は後ろの7bitのscancodeはkeyの定義し、最も重要なbitはpressかreleaseかを定義している。IBM XTのオリジナルに存在しないエンターキーのようなkeyは2つのscancodesを生成する。

YuheiNakasakaYuheiNakasaka

Introduction to Paging

Memory Protection

プロセスを独立させて他のプロセスから自分のプロセスのメモリへアクセスさせないようにしたい。

アーキテクチャごとに様々なアプローチがあり、例えばARMのCortex-MではMemory Protection Unit(MPU)というメモリ保護機能がある。これはリージョンとパーミッションを決めて管理する仕組み。

x86の場合はセグメンテーションとページングのアプローチがある。

Segmentation

セグメンテーションは1978年に導入された機能。背景としてはCPUが16bitアドレスしか使えない中でアクセスできるメモリ領域をより広げる(この場合は1MiBまで可能に)するために考えられた。

セグメントレジスタはfetchにはCS、スタック操作にはSS、DSとESはその他の命令がデータセグメントを利用するのに利用された。またFSとGSは自由に使えるようになっている。

初期のセグメンテーションはセグメントレジスタが直接オフセットアドレスを持ち、アクセスコントロールもなかった。その後プロテクションモードが導入。このモードではセグメントはディスクリプタテーブル(要はプロセス毎にどのメモリをどのくらい使用しているのかを保持したテーブル)にインデックス・オフセットアドレス・セグメントサイズ・アクセス権を保持している。それぞれのプロセスはこのディスクリプタテーブルにアクセスすることによってプロセスを独立させることができる。

Virtual Memory

Fragmentation

セグメンテーションにはフラグメンテーションを起こす問題がある。仕組みとしてはメモリを割り当てる時に物理の空きメモリが偏在していてまとまって論理アドレスに割り当てられない時に発生する。

この時メモリをコピーして整列させて論理アドレスを更新するという作業(デフラグ)が必要だがこの作業は非常にパフォーマンスを落とすしランダムで発生して予測できない。このことからセグメンテーションはもうほとんどのシステムで実装されていない。

Paging

ページングは論理メモリをページという固定の小さなサイズのブロックに分割し、物理メモリの方をフレームという同じく小さなブロックに分割し、それぞれを個別でマッピングする仕組み。これによってセグメンテーションで発生していたような問題は起きなくなる。

Hidden Fragmentation

基本的にはページングではフラグメンテーションは発生しないが、全てのメモリサイズが等倍ではないのでいくつかの隠れたフラグメンテーション(内部的なフラグメンテーション)は存在する。

Page Tables

論理メモリと物理メモリのページとフレームをマッピングの情報を記録しておくテーブルがページテーブル。
ページテーブルにはページとフレームのオフセットとアーキテクチャによってはアクセス権限の情報が格納されている。

CPUは今アクティブなテーブルへのポインタのみレジスタ(CR3)に読み込みそれに合致するページテーブルのフレームを引っ張ってくる。

これらの論理メモリ<->物理メモリ間の翻訳処理を向上させるためにアーキテクチャごとに最後にアクセスした翻訳情報のキャッシュを持っていたりする。

Multilevel Page Tables

上述のページテーブルはたくさんのアドレス空間を消費してしまいメモリが無駄になる問題がある。

マルチレベルページテーブルを使うと使用していない物理メモリにまでページテーブルを作る必要がなくなるので論理メモリと直接マッピングされてるページテーブルのページ数を大きく減らすことができる。

Paging on x86_64

x86_64のページテーブルは512エントリで合計4KiB。このテーブルが4つある(4Level)。1エントリのサイズは8B。512 * 8B = 4KiBとなる。

ページテーブル(64bit)は0~12bitsは4KiBのページへのオフセット(2^12=4KiB)。12~21bitsはLevel1 index、21~30はLevel2 index, 30~39bitsはLevel3 index, 39~48bitsはLevel4 index。48~64bitsは空きスペース。

Example Translation

ページインデックスを辿って物理メモリを参照する手順の例。CR3にあるLevel 4 indexから巡っていく流れがが下図。

Page Table Format

下の表の通り。ページテーブルはメモリ上に確保される。

The Translation Lookaside Buffer

Translation Lookaside Buffer(TLB)はページテーブルと論理アドレスの変換をキャッシュする機構。

TLBはCPUのキャッシュと異なりKernel側でキャッシュの削除や更新を行う必要がある。invlpg(invalidate page)というCPU命令を使うことで削除更新が行える。またCR3レジスタ(アクティブなエントリへのポインタを格納するレジスタ)をリロードすることでTLB全てをフラッシュ(全て消せる)できる。

ページテーブルにしてもTLBにしてもx86_64 crateに全て実装されている。ええんか...

Implementation

今まで実装してきたkernelはすでにページングで動いている。bootloaderがすでにページのアクセス権限の設定などやってくれている。なのでkernelからアクセスするメモリはすでに論理アドレス。VGA bufferだけは0xb8000が物理アドレスの0xb8000にマッピングされているので異なるが。

Page Faults

ページフォールトが発生するとCR2レジスタにページフォールトを起こしたアドレスが格納される。

Accessing the Page Tables

ページテーブルを通じてしか物理メモリへアクセスする手段がない。

また今のままだとCR3には物理アドレスしか表示されないのでページテーブルにアクセスできない。