Writing an OS in Rustを一通りやった
文字通りRustでOSを作ってみるという内容の記事で、最新のAsync/Awaitまで写経を終わらせたので復習も兼ねて内容をまとめる
結論から書くと非常に面白い記事だった
x86_64というcrateが用意されていて、だいたいはそれを使って書いていくことになるのでアセンブラはほとんど触らず理論的な部分の学習にフォーカスできた(なので低レベル初心者の自分でもなんとかなった)
OSを構築する概念についてざっくり踏み込みたい場合に良い題材になるんじゃないかと思う。特にメモリアロケーションやCPU割り込みの仕組みに興味がある人はやってみるとイイかも
以下は各章のざっくりまとめ。個人的に印象的だった内容だけ掻い摘んで書いておく。もちろん僕の理解度で書いているので間違いがあるかも知れない
A Freestanding Rust Binary
1つ目の記事ではオレオレkernelを作成するところから始める
自作環境上ではstdのライブラリが使えなかったり、main関数が呼ばれなかったり、panicハンドラがなかったりするのでそれぞれ定義していく
いつも当たり前に使えていた仕組みが使えなくなるというのが新鮮だった
A Minimal Rust Kernel
kernelをQEMU上で動かしてHelloWorldするところまでをやる
最初にBootloaderの学習から入るが、実際にBootloaderを作るわけではなくあくまで概念を学ぶという形だった(実際の起動にはbootimageというcrateを使う)
その後はビルド環境の構築について学ぶ。設定箇所が多くてちゃんと全て理解できたかと言われると怪しい
その後実際に文字をprintする処理を実装していく
出力にはVGA text bufferこのbufferはメモリの特定のアドレス(0xb8000)が割り当てられていて、そのメモリに値を書き込むと文字が出力される
実際の処理としてはアドレスに変数代入しているだけで文字が出るので不思議な感覚だった
VGA Text Mode
先述のVGAtext bufferを使って自前のprint系マクロを作る記事
面白かったのはvolatileというキーワードで、
例えば"メモリの特定番地に書き込んだ副作用として文字がでる" という挙動はコンパイラからは知りようがなくそのままだと最適化されて消えてしまうかもしれない。
んだけれど、そういった最適化を抑制するキーワードがvolatile。変わりやすいとかの意味らしい
あとはlazy_staticという便利マクロの使い方も学ぶ。基本static変数はコンパイル時に値がわからないといけないんだけれど、それを実行後最初にアクセスされるまで遅延するというマクロになっている。内部的にはDeref時の挙動をいじっていい感じにしているとか
そんなこんなでprintln!すると文字がQEMU上で動くkernelで表示できるようになる
Testing
読んで字の如し。テストについて学ぶ。OS作るときもテストを書けるのか！という新鮮な驚きがあったけれど偏見だったかもしれない（なんやらメモリのダンプを読むとか難しいデバッグをしているイメージが合った）
実際のテストはQEMU上で動くので、SerialPortを使ったやり取りとか、テスト後にQEMUを終了する方法なんかについて学ぶ
ここからはCPUの割り込みについて学んで行く
CPU Exceptions
まずCPUの割り込みに色々あるねんで～、というところから始まる
個人的にツボだったのがDoubleFaultで、例外の中で例外が起きると発生する割り込みのことらしい（テニスか？）
じゃあDoubleFaultで例外発生したらどうなるんだ...?
と思ったらTripleFaultまであって笑ってしまった。いくらでも続くのかこれ、ということはなくTripleまで来たら一般的にはシステムが再起動するようになっているらしい
例外と例外ハンドラの割当は Interrupt Descriptor Table（IDT）というところにまとめられている
IDTにハンドラを登録しておくと、なんか例外が起きた時に対応するハンドラをCPUが自動で呼び出してくれる仕組みになっているそうな
諸々tableのformat（どのbitがこう）みたいな説明があるけど詳細は割愛。丸暗記は無理だったので雰囲気だけ掴む感じになった
続けてInterrupt Calling Convention（割り込み呼び出し規約）について学ぶ
Calling ConventionはCPUのアーキテクチャ毎に決まっている呼び出しの規則の事らしく、例えばx86_64上のC言語は関数呼び出し時にどのレジスタに変数を詰めるかなどが決まっている
ここで重要なのは、通常の関数と例外ハンドラは呼び出されるときのコンテキストが違うということ
通常の関数呼び出しでできるような操作が、例外ハンドラの呼び出しでは出来ないので変わりの仕組みがある
CPUが例外ハンドラ呼び出し時にやるあれこれを学んだあとに実際にハンドラを作っていく
extern "x86-interrupt" とすることで、x86の割り込み用の呼び出し規約に沿った関数が作れる
ちなみに最初に作るのがbreakpointの例外ハンドラで、デバッガの仕組みはCPUの例外使ってたんだなーというのがおもしろポイントだった
Double Faults
ここではDouble Faultの内容について掘り下げる。Double Faultで例外が起きると先述の通りTriple Faultシステム再起動なので、そうならないように作る必要があるという点で重要な例外処理になっている
途中で説明があるけどDouble Faultが起きる例外の組み合わせは決まっていて、何でも起きるわけではない
Double Faultの組み合わせについて学んだあとに、例外発生時にstackがoverflowしてるとどうなるの??? という話が始まる
その場合はPageFaultが複数回起きてTripleFaultに到達してシステムが再起動するので例外を扱う用のstackを別に用意すつ必要があるらしい
ここで出てくるのがIST（Interrupt Stack Table）とTSS（Task State Segment）で、
ISTはTSSの一部で、TSSはlegacyなstructureで、レジスタの状態などを保持するらしい。昔はハードウェアのコンテキストスイッチなどにも使われたらしいが、64bitモードではサポートされない機能なのでformat自体も変わったらしい
ISTをTSS上で例外のindexと割り当てて登録する（今回はDoubleFault）と、
例外発生時にISTで設定したアドレスがstackとして使われる
この時点ではメモリマネージメントが出来ないので、代わりにstaticな変数を擬似stackとして使っている
TSSは最終的にGDT（Global Discriptor Table）に登録されて使われる。あれこれ登録や初期化処理があるけどそこは割愛
CPUが何かした時に行う動作が規定されてて、そこに乗っかる形であれこれ作って行くのが面白かった。特にstack overflow時にキレイなstackが必要みたいな話は新鮮でツボだった
最終的にテストも書いてこの章はおしまい
Hardware Interrupts
この章ではキーボードの割り込みを扱って文字をprintできるようにする
キーボードからの割り込みはPIC(programmable interrupt controller)で扱う
APICというのに置き換えられているらしいけど、PICのほうがシンプルなのでまずはそれから触る
この割り込みもIDTに登録する、indexは一般的に例外の次になる32~47を使うんだそう
いきなりKeyboard割り込みを作るのではなく、シンプルなTimer割り込みを作って、その後keybord割り込みを作る。途中で既存のloopで割り込み待ちする実装だとCPUがBusyになるので、hlt命令で必要のないloopを行わないように置き換えたりする
割り込みの扱いが例外とかと同じ仕組みなのが面白かった
ここから先はメモリマネジメントの話になる。正直難しくて理解が怪しい
Introduction to Paging
ここでは仮想メモリの仕組みとして、SegmentationとPagingについて学ぶ
OSの重要な仕事の1つに個々のプログラムをisolateして、互いに干渉しないようにするというものがある
その手段としてSegmentationとPagingというアプローチについて学ぶ
Segmentationは元々アドレス可能なメモリを増やすために1978年に導入されたらしい。最初のバージョンのSegmentationha、segmentのレジスタに直接アクセス制限やオフセット情報（恐らくメモリの）が含まれていたそうな
とにかく古い仕組みなんじゃなというぐらいの理解に先に進んでしまった
ここで合わせて仮想メモリという概念が出てくるが、こっちのほうが重要かもしれない
仮想メモリは物理メモリへのアクセスを抽象化するための仕組みで、仮想メモリ上のアドレスはOS上の仕組みによって物理メモリにマッピングされる
ただ単純にoffsetを噛ませてアクセスするような仕組みだと、メモリのフラグメンテーションに対応するのが難しくなってしまう
都度並び変えれば(デフラグ的なことをすれば)もちろんフラグメンテーションの回避は可能だが、動作が重くなってしまう
これがSegmentationが多くのシステムで使われなくなった理由の1つらしい
代わりにメモリ領域を固定長のブロックで区切って扱うというアイデアを持ち込んだのがPagingという仕組みになっている。仮想メモリをPage単位で物理メモリにマッピングできるので効率が良い
ただこれも完璧ではなくて、Pageは固定長なので1byteだけはみ出るようなサイズを確保すると残りの部分は無駄になってしまうというな問題がある
Pageのマッピング情報はPageTableという構造体に定義される。各Pageには書き込み許可のフラグと物理メモリのどこにマッピングされているかの情報が入る。またアクティブなPageTableの情報はx86ではcr3というレジスタに保存されている
んじゃ単一の辞書みたいなマッピング情報を扱えばよいのかな？ と思ったらそんなに単純ではなく、ここでもまだ問題がある
というのも例えば仮想メモリ上の0~50と1000000~1000050の範囲を扱うことを考えた際に、物理メモリ上で必要なのは100byte領域だけなのに、PageTableには0~1000050のエントリが必要になってしまう
これもまたメモリの無駄なのでPageTableにlevel1のものとlevel2のものを使って、Level2>Level1>物理メモリ、という流れでマッピングするようにする
こうすると先程説明したようなメモリのムダが省ける
なお記事で説明されている通り最近のCPUではLevel4までのPageTableが存在しているらしい（ものによってはLevel5まであるそうな）
実際のメモリ配置についても学ぶけど個々では割愛
Tableを都度なめてメモリの番地引いてると時間がかかるので、TLB(TranslationLookasideBuffer)という仕組みでcacheするようになっているそうだ。これは勝手に更新されたりしないので、PageTable更新のたびにflushが必要
実装パートではPageFaultを起こしたり、実際にcr3レジスタからlevel4のpage_table引っ張ってきて値を見たりする
Paging Implementation
この章では実際にPagingを実装する
crateとして使っていたbootloaderから、BootInfoという形で物理メモリのoffsetなどの情報を受け取って、実際にlevel4tableの値を触ったりしてみる
上記に際して、PageTableから物理メモリへのアクセス(マッピング？)について、いくつか種類があることも学ぶが、実装に際してはx86_64 crateにOffsetPageTableが用意されているのでそれを元に実装した
正直この辺は説明されるまま作っていたのと、概念の難しさもあってちゃんと理解出来たとは言い難い
ただPageTableの雰囲気は掴むことが出来たので、わけわからん単語が出てきてビビるというのは減る(と思う)
Heap Allocation
この章ではHeapへのメモリアクセスについて学ぶ。これができるようになるとKernel内でBoxのようなHeapへのメモリ確保を必要とする仕組みが使えるようになる
実際この章までBoxを使うコードは登場していない
AllocatorはGlobalAllocというtraitを実装する形で行う。このtraitがallocやdeallocといった関数の定義している
GlobalAllocをimplしたstructを作り、そのstructの変数をstaticで用意して
#[global_allocator]というattributeを設定すると、Rustがメモリ確保に際して用意した変数を使用してくれるようになる
合わせて#![feature(alloc_error_handler)]をlib.rsに定義し、
#[alloc_error_handler]を設定したエラーハンドラの用意も必要になる
panicハンドラもそうだったけど、Rustの仕組みであるメモリアロケーションであっても上書きできるところがツボだった
ただallocatorを用意しても肝心のheapが確保されていなければならないので、追ってheapのinit処理も実装する
最後にcrateで用意されるlinked_list_allocatorを使ってallocのテストを書くところまでやる
linked_list_allocatorは少し非効率なのでもっと良いものに変えようという話が次の章で説明される
Allocator Designs
ここでは
・BumpAllocator
・LinkedListAllocator
・Fixed-SizeBlockAllocator
という3つのallocatorについて学ぶ。2つ目は前の章で使ったものになる
1つ目のBumpAllocatorは非常にシンプルな実装で、Heapの開始地点のアドレスからallocが呼ばれるたびにその領域分確保し、確保した分進めたアドレスと、確保した個数を保持していく
順に確保していくだけなのでめっちゃシンプル
途中Allocatorをmutableに扱う為の方法について説明が入るけどここは割愛
実装がシンプルだけどdealocするときにはまとめてソイヤで捨てないといけないので、部分的に開放してあれこれとかが出来ないという欠点がある
逆に捨てる時にまるっと捨てても問題ない状況では使うことが出来て、
DodrioというRust+wasmで作成された仮想DOMライブラリでbump allocationという概念が採用されている。仮想DOMではprevとnextの2つのvdom treeを保持できれば良いからという理解をしている
ちょうどRust触り初めたての頃に調べていた内容が出てきて面白かった(なお当時はBumpの意味がちゃんとわかっていなかった)
2つ目のLinkedListAllocatorは文字通り連結リストを用いたallocatorで、headが常に空いているアドレスの先を指している
確保に際してこの空きアドレスのサイズを調べるという処理が入る。これでdeallocした領域を再利用することができる
ただ問題としてdeallocしても領域のサイズが更新されないので、たくさん確保するとその分だけフラグメンテーションが起きる。対策としてdealloc時に前後が空き領域だったらつなげるという処理を行えばこの問題は解消するが、一方で処理速度に難が出てしまう
あとは単純に連結リストの走査が重いので、細かく大量にallocするとしんどいというのもあるようだ
Fixed-SizeBlockAllocatorはその問題を解決するためにheapのサイズを固定長で決めておいて(例えば16,32,64)、それぞれのlistを持つというもの。中途半端なサイズのallocが来たときには無駄ができるが、一方で走査する対象が減るため高速になる
この辺は有名なmalloc動画でも説明があった(この章をやったあとに動画を見直したら以前よりは分かる内容が増えててちょっと楽しかった)
そんな感じで概要を掴んだあとはがりがり実装しておしまい
Async/Await
TODO
次どうするか
月報に書いてる通り、firecrackerの仕組みに興味があったのでまずは公式のdocumentから読んで見ようと思う。そもそも先にそっち読むべきなんじゃないか？ という話はあるんだけれど、もうやってしまったので仕方がない
目移りしやすいタイプなので来月になったら別の事言ってるかもしれないけれど今までもそんな感じだったのでその時はその時
教訓
物量が物量なので、都度ブログにまとめておくべきだったと反省
そもそも一ヶ月突っ込んでやっていた内容を1日で整理してまとめられるわけもないのだった...（内容うろ覚えやし）
この記事が気に入ったらサポートをしてみませんか？