Rust で vmlinux を起動できる x86 ブートローダーを作ってみた話

Rust を勉強し始めたので冬休みの間に Linux の boot protocol を喋る x86ブートローダー（自称:Krabs）を作ってみました。この記事では、開発に至った動機や、作成した Krabs の特徴とか仕組み、開発中におきた嬉しかったことなどについて書きたいと思います。

## Krabs とは 
Krabs は、Rustで書かれた x86/x86_64(Legacy BIOS) 向けの４段ロケット構成のチェインローダーです。
bzip2 で圧縮された ELF 形式のカーネルを起動できます。bzip2 圧縮されたイメージを解凍して、次に展開してでてきた ELF イメージを再配置してからの、カーネルの起動となります。
内部では libbzip2 の C ライブラリを利用していますが、それ以外は全て Rust で記述されています。

[GitHub - o8vm/krabs: An x86 bootloader written in Rust.](https://github.com/o8vm/krabs)

以下の特徴があります。

* legacy BIOS に対応
* 64bit ロングモード, 32 bit プロテクトモードの両方に対応
* 最小限の x86/x86_64 Linux boot protocol に対応
* Linux boot protocol に従って kernel コマンドラインを指定し、OS 起動時の動作を制御可能
* Linux boot protocol に従って initramsfs/initrd などのモジュールをロードできる
* マルチブート仕様には対応していない。

kernel command line と initrd を活用する 64bit vmlinux の起動例は以下になります。

```shell
./tools/build.sh -k vmlinux -i initramfs.cpio.gz -c "clocksource=tsc" disk.img 
qemu-system-x86_64 --hda disk.img -m 1G
```

![cmdline.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/254122/652ea4c4-5810-4a4a-309d-e0aac6184a98.gif)

## Krabs を作ろうと思った動機
Rust の練習と Linux の習熟が目的です。OSスタックより下のレベルでのcodingもRust を使用することにより、よりモダンにできるのではないかと考えました。また。Linuxカーネル起動までの過程から、必要最小限のエッセンス部分だけを抽出し、最終的に自分にとってブラックボックスが一切存在しないブート環境を作り上げてみたいと言う思いもありました。基本的には、以下の混迷する部分、詰まりがちな部分を取り除くことを目標としました。

* GRUB/2ブートローダーや bzImage など、チェインローダーの仕組みや技法が難解
* また、そこでのアセンブリ<->Cとの往復は、素人目には超スパゲッティ状態
* 起動コードの読破は結構時間と努力が必要。かりに読破できたとしても、得られるものがあるのかどうか..
* Rust は成果物が大きくなりがちでブートローダーの記述には向いていないと言われているが、本当か？

以上を踏まえて、ブートローダーの読解や bzImage コードの追跡はいさぎよく諦め、自ら Rust でブートローダーを書き下ろすことにしました。  

## 仕組み
### Linux カーネル起動機構
Linux カーネル起動機構を bzImage や GRUB ブートローダーから眺めてしまうと難しく感じてしまいますが、実態は意外にも単純です。基本的なことは、２点です。圧縮イメージを展開し、ELF 形式のイメージを取り出したら、それをプログラムヘッダーに従って再配置すること、そして、[The Linux/x86 Boot Protocol](https://www.kernel.org/doc/html/latest/x86/boot.html) に従って初期化処理を行い、パラメーターの設定をすること。これだけです。

あっけないほど簡単に思えますが、具体的には、以下の4種類の初期化処理を行います。

**ハードウェア初期化:**

* キーボードリピート頻度の設定（最大値）
* 割り込みの禁止およびすべての割り込みレベルのマスク
* 割り込みディスクプリタ(IDT), セグメントディスクプリタ(GDT)の設定
* すべてのセレクタ(CS, DS, ES, FS, GS)は4Gバイトフラットのリニアアドレス空間を参照
* アドレスバスの32bit化(A20ラインの有効化)
* プロテクトモードへの移行
* ターゲットがELF64の場合、4Gブートページテーブルを設定し、ロングモードに移行

**ソフトウェア初期化:**

* BIOS 呼び出しによるシステム搭載メモリ容量の取得

**カーネルへの情報伝達:**

* カーネルパラメータ用に[Zero Page](https://www.kernel.org/doc/html/latest/x86/zero-page.html)を設定し、OSに送信

**イメージの配置:**

* ターゲットはELFファイルだが、Krabsはbzip2圧縮したそれを使用する。したがって、2段階の再配置が必要：1つはbzip2解凍で、もう1つはELF再配置
* initrd/initramfsなどのモジュールをロードして配置する

上記の処理を行うのに Krabs は４つのステージに分かれたプログラムで対応します。

### Krabsの構造と概要
1. stage1:   
stage1はブートセクターに書き込まれた446バイトのプログラムです。セグメントレジスタ（`CS`、`DS`、`ES`、`SS`）は`0x07C0`に設定され、スタックポインター（`ESP`）は`0xFFF0`に初期化されます。その後、stage2をアドレス`0x07C0:0x0200`にロードし、アドレス`0x07C0:0x0280`にジャンプします。 stage1の末端2byteには、stage2プログラムのセクター長（512バイト単位）を格納するための領域があります。Rust でも 446 byte に収まる1stステージローダーが書けるのです！
2. stage2:  
stage3をアドレス`0x07C0:0x6000`にロードします。bzip2圧縮されたカーネルイメージは拡張メモリ領域のアドレス`0x0350_0000`にロードされ、initrdは`0x0560_0000`にロードされます。これらのファイルの転送には、アドレス`0x07C0:0xEE00`から4Kバイトのトラックバッファーを使用しました。ディスクから読み取ったものを一時ここに格納し、さらに`INT 15h` BIOSファンクション`0x87h`を使用して適切なアドレスに転送します。 stage3、initrd、および圧縮カーネルイメージの読み込みが完了したら、アドレス`0x07C0:0x6000`にジャンプします。なお、カーネルコマンドラインは、アドレス`0x280`から120バイトの領域に保持されています。
3. stage3 + stage4:  
Stage3とStage4は、bss領域を使用する可能性があるため、`.bss`セクションのゼロクリアをサポートする必要があります。一連のハードウェアおよびソフトウェアの初期化の後、Zero Page 情報を `0x07C0:0x0000`〜`0x07C0:0x0FFF`に準備します。 A20 line を有効にし、アドレスバスを32ビットに変更して、保護モードに移行します。bzip2 解凍関数を呼び出し、bzip2圧縮されたELFカーネルイメージを拡張メモリアドレス`0x100000`以降に復元します。そして、ELF32 / ELF64ファイルをパースして、ロードします。もし、ターゲットがELF64だった場合には、4Gブートページテーブルを設定し、ロングモードに移行します。最後に、エントリポイントにジャンプしてカーネルを起動します。このとき、下位メモリに用意された Zero Page 情報の物理アドレス（0x00007C00）をESIまたはRSIレジスタに設定しておきます。
4. plankton:  
planktonはstage1 ~ stage4 に共通しているライブラリです。

### Disk 構造
KrabsはHDDとSSDに対応していますが、必ず MBR を持つ必要があります。また、いずれかのパーティションは必ず boot flag が設定されている必要があります。stage3,4, kernel, initrd は bootflag のついたブートパーティションに格納されます。

![layout.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/254122/86aa67b4-119b-9b0f-60d4-4520abac548c.png)

### 補足
ところで、なぜ legacy BIOS に対応しているのか気になっている方がいるかもしれないので、こちらについて補足させてください。以下の3点の理由から今回は legacy BIOSのみサポートしています。

* このブートローダーはもともとThinkPad 600Xと言う古の？PCで使うことを目的として作ってた。
* 現時点においては、UEFI よりもレガシーBIOS に対応したほうが幅広い環境で使える。
* 自分の PC 以外では主にクラウド環境で使用することを目的としている。クラウド環境では レガシーBIOS が主流で、またこれをUEFIに置き換えるメリットもなさそうだったので、当分生存できそう。

## Rust で書いてみた感想
Rust は低レベルなコードを書く上で C よりも圧倒的に楽。と言うのが個人的な感想です。

### コンパイルが通った時の安心感がすごい
例え問題が起きても本当に`unsafe`部分を疑うだけで済む。今回はこれ本当だった。
### パッケージ、モジュールの考え方が最高
Cみたいにオブジェクトファイルどれとどれリンクするんだっけってイライラしなくていい。
### モダンなコードをかけて楽
no_std の低レベルのコードも比較的モダンにかける。
また、あれが使えないとかこれが使えないとかそんなに悩むことはない。
体感ですが、開発速度はCよりも早いかも？
何より、Rust は書いてて楽しいです。
型を意識して書くのいいです。また、いろいろな機能を使うのも楽しいです。
### Rust でもチェインローダーが書ける
かけます。16bit/32bit もあまり不自由なくチェインローダーがかけます。
チェインローダーはそのロケット構造上、次のステージに行くために必ず unsafe な部分を記述しなければなりませんが、その unsafe な部分には、Cのときによく使う技法がそのまま使えるのもいいなと思いました。
ただし、ブートセクタ内部ではマクロとクロージャは要注意です。サイズが爆発しやすい気がします。
### Cの資産の活用と提供
FFIによりCの資産をあまり意識せずに活用できるのは大変素晴らしいと思います。
今回libbzip2を内部で使用していますが、Rust から簡単に使うことができました。
また、逆にCにRustの資産を提供することも容易かったです。libbzip2 の使用のためには`malloc`が必要ですが、これについて [Rust で簡単に実装したものを C 側に提供できました](https://github.com/ellbrid/krabs/blob/master/src/stage_4th/src/bz2d.rs#L45)。
### ハマったところ
ページテーブルを設定するのに、アラインメントを[リンカースクリプト](https://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_node/ld_14.html)や[structの属性](https://doc.rust-lang.org/reference/type-layout.html#representations)で設定しようとしましたが、いずれもうまくいかず。。。(他のデータ構造が壊れてしまっていたように見えた)。Rust のアラインメント、何かおかしいのかと思いつつそのまま放置。結局、ページテーブルを設定したい領域を手動で確保して、そこのアドレスをベタ打ちすることで対応しました。[例](https://github.com/ellbrid/krabs/blob/master/src/stage_4th/src/svm/lm.rs#L44)

## 超大物エンジニアが助けてくれた！
Krabs を作成して単純な ELF 形式のカーネルを起動できるようになってから しばらくは、なぜか vmlinux を正しく起動できず、開発が少しの期間停止していました。その間、READMEを英語で書いたり、単純な動作例をテストしたり、long mode に対応したりして、twitter 上で英語で宣伝を行っていました。  
なんでうまくいかないんだろうと毎日悩んでいて、bzImage のソースを読み込んでいたある日、とても嬉しいことが起きました。

何気なく日本語で呟いたツイートに、なんと AWS の超大物エンジニア [@_msw_](https://twitter.com/_msw_) と x86/x86-64 Linux kernel treeの長年のメンテナとして有名な[@LinuxHPA](https://twitter.com/LinuxHPA)（[Hans Peter Anvin - Wikipedia](https://en.wikipedia.org/wiki/Hans_Peter_Anvin)） が反応してアドバイスくれたのです！思わず嬉しすぎてスクショしました。
このアドバイスのおかげで、問題は一気に解決し、また、マルチブート仕様には対応しない決意を新たにしました(もともともkernel内部にパラメータを埋め込むマルチブート仕様は僕はあまり好きじゃないです)。

![advice2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/254122/c2cfd12b-df44-8b35-efa6-4a73e3d8dffa.png)

今回は日本語に反応してくれましたが、もともと英語で宣伝していたものにリアクション頂いてから繋がっていました。英語で発信しておくの大事だなと改めて思いました。

あと英語で呟くと、twitter で直接 DM をくれたり、リプライで応援メッセージを送ってもらえる頻度が上がる気がします。大変励みになります。嬉しかったメッセージを紹介します。Writing an OS in Rust の方もメッセージくれました。

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">i will study this to understand better low level programing and try &quot;upgrading &quot; templeOS</p>&mdash; rotten lung (@satanacio666) <a href="https://twitter.com/satanacio666/status/1226235051614097411?ref_src=twsrc%5Etfw">February 8, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">Very cool seeing <a href="https://twitter.com/rustlang?ref_src=twsrc%5Etfw">@rustlang</a> being used to modernize the lower levels of the OS stack <a href="https://t.co/CpXXoWDt2t">https://t.co/CpXXoWDt2t</a></p>&mdash; Dino A. Dai Zovi (@dinodaizovi) <a href="https://twitter.com/dinodaizovi/status/1226222130951544833?ref_src=twsrc%5Etfw">February 8, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">Awesome! I will definitely check it out when I have some time.</p>&mdash; Philipp Oppermann (@phil_opp) <a href="https://twitter.com/phil_opp/status/1224648491852607489?ref_src=twsrc%5Etfw">February 4, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

...これで終わるともったいないので、Krabs を体験していただくためにも、最後に 最小構成の Linux システムを構築してこれを Krabs で起動する例を扱いたいと思います。

## Minimal な Linux を起動しよう
* ブートローダー作りたい人
* 最小構成のLinuxシステムをビルドしてみたい人
* 簡単なinitramfs作ってみたい人

とかの参考になるのではと思います。（以下、CentOS7で作業してます）

### minimal な vmlinux を作ろう！
1: Linuxのソースを持ってきます。

```shell
wget https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.5.2.tar.gz
tar xf linux-5.5.2.tar.gz 
cd linux-5.5.2
```

2: Linuxのconfigを設定します。

```shell
make allnoconfig
make menuconfig
```

以下の設定を使用します。

```
64-bit kernel ---> yes
General setup ---> Initial RAM filesystem and RAM disk (initramfs/initrd) support ---> yes
General setup ---> Configure standard kernel features ---> Enable support for printk ---> yes
Executable file formats / Emulations ---> Kernel support for ELF binaries ---> yes
Executable file formats / Emulations ---> Kernel support for scripts starting with #! ---> yes
Enable the block layer ---> yes
Device Drivers ---> Generic Driver Options ---> Maintain a devtmpfs filesystem to mount at /dev ---> yes
Device Drivers ---> Generic Driver Options ---> Automount devtmpfs at /dev, after the kernel mounted the rootfs ---> yes
Device Drivers ---> Character devices ---> Enable TTY ---> yes
Device Drivers ---> Character devices ---> Serial drivers ---> 8250/16550 and compatible serial support ---> yes
Device Drivers ---> Character devices ---> Serial drivers ---> Console on 8250/16550 and compatible serial port ---> yes
Device Drivers ---> Block devices ---> yes
Device Drivers ---> PCI Support --> yes
Device Drivers ---> Serial ATA and Parallel ATA drivers (libata) ---> yes
Device Drivers ---> Serial ATA and Parallel ATA drivers (libata) ---> Intel ESB, ICH, PIIX3, PIIX4 PATA/SATA support ---> yes
Device Drivers ---> Serial ATA and Parallel ATA drivers (libata) ---> Generic ATA support ---> yes   
Device Drivers ---> SCSI device support ---> SCSI disk support
File systems ---> The Extended 4 (ext4) filesystem ---> yes
File systems ---> Pseudo filesystems ---> /proc file system support ---> yes
File systems ---> Pseudo filesystems ---> sysfs file system support ---> yes
```
もしくは、上記をすでに設定してある  [my recommended config](https://github.com/ellbrid/krabs/blob/master/resources/.config)  を用意してあるので、これを`.config`にコピーしてきます。

```shell
wget https://raw.githubusercontent.com/ellbrid/krabs/master/resources/.config -O .config
make menuconfig
```

3: vmlinuxをビルドします。

```shell
make vmlinux
```

4: カレントディレクトリに `vmlinux`が出来上がっています。

### initramfsを作ろう！
1: まず`./src/initramfs`ディレクトリを作成してここに基本的なディレクトリを構築していきます。

```shell
cd ..
mkdir --parents src/initramfs/{bin,dev,etc,lib,lib64,mnt/root,proc,root,sbin,sys}
```

2: 基本的なデバイスノードもコピーしていきます。

```shell
	1.	sudo cp --archive /dev/{null,console,tty,tty[0-4],sda,sda[1-8],mem,kmsg,random,urandom,zero} src/initramfs/dev/
```

3: 動的ライブラリなど導入して環境を構築する代わりに、busyboxを使用します。

```shell
curl -L 'https://www.busybox.net/downloads/binaries/1.31.0-defconfig-multiarch-musl/busybox-x86_64' > src/initramfs/bin/busybox
sudo chmod +x src/initramfs/bin/busybox
./src/initramfs/bin/busybox --list | sed 's:^:src/initramfs/bin/:' | xargs -n 1 ln -s busybox
```

4: `init`スクリプトを用意します。

```shell
cat >> src/initramfs/init << EOF
#!/bin/sh
mount -t devtmpfs  devtmpfs  /dev
mount -t proc      proc      /proc
mount -t sysfs     sysfs     /sys
sleep 2
cat <<END
Boot took $(cut -d' ' -f1 /proc/uptime) seconds
                                             
_____           _        __    _             
|   __|___ ___ _| |_ _   |  |  |_|___ _ _ _ _ 
|__   | .'|   | . | | |  |  |__| |   | | |_'_|
|_____|__,|_|_|___|_  |  |_____|_|_|_|___|_,_|
                  |___|                       


Welcome to Sandy Linux
END
exec sh
EOF
```

```shell
sudo chmod +x src/initramfs/init
```

5: initramfsを作ります。

```shell
cd src/initramfs
find . | cpio -o -H newc | gzip > ../../initramfs.cpio.gz
```

### diskイメージを作ろう！
1: イメージファイルを `qemu-img` で作成します。`dd`でもいいです。

```shell
qemu-img create disk.img 512M
```

2: `fdisk`でパーティションを作成します。

1st partition:

```shell
Command (m for help): n
Partition type:
   p   primary (0 primary, 0 extended, 4 free)
   e   extended
Select (default p): p
Partition number (1-4, default 1): 1
First sector (2048-1048575, default 2048): 2048
Last sector, +sectors or +size{K,M,G} (2048-1048575, default 1048575): 206848
Partition 1 of type Linux and of size 100 MiB is set
```

ブートフラグを第１パーティションに作ります:

```
Command (m for help): a
Selected partition 1
```

2nd partition:

```
Command (m for help): n
Partition type:
   p   primary (1 primary, 0 extended, 3 free)
   e   extended
Select (default p): p
Partition number (2-4, default 2): 
First sector (206849-1048575, default 208896): 
Using default value 208896
Last sector, +sectors or +size{K,M,G} (208896-1048575, default 1048575): 
Using default value 1048575
Partition 2 of type Linux and of size 410 MiB is set
```

write out:

```
Command (m for help): w
The partition table has been altered!
Syncing disks.
```

3: 第２パーティションにext4ファイルシステムを作る

```shell
$ sudo kpartx -av disk.img 
lsblk
NAME            MAJ:MIN RM  SIZE RO TYPE MOUNTPOINT
sr0              11:0    1 1024M  0 rom  
loop0             7:0    0  512M  0 loop 
├─loop0p1       253:2    0  100M  0 part 
└─loop0p2       253:3    0  410M  0 part 
$ sudo mkfs.ext4 /dev/mapper/loop0p2
$ sudo kpartx -d disk.img 
```

### Krabsで起動しよう！
以下のコマンドを実行するだけです。これで vmlinux が bzip2 圧縮されてブートローダーとともに disk.img に書き込まれます。

```shell
$ pwd
path/to/krabs
$ ./tools/build.sh -k path/to/vmlinux -i path/to/initramfs.cpio.gz path/to/disk.img 
```

それでは起動しましょう！

```
$ qemu-system-x86_64 --hda disk.img -m 1G
```

![cmdline.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/254122/652ea4c4-5810-4a4a-309d-e0aac6184a98.gif)

## あとがき
そういえば reddit のコメントで、なんで xz や gzip にしなかったのか聞かれました。あまり深く考えてませんでしたが、単に bzip2 を持ってくるのが簡単だったという理由があります。また、bzip2 を Rust に移植中のニュースを聞いていたのでそれが楽しみであるのも理由の一つです。
ただ、上記の Minimal Linux を起動する例をお試しいただいた方はお分かりいただけるかと思いますが、bzip2は大変遅いです。このため将来的には gzip もしくは xz に移行する可能性があります。

ちなみに僕はスポンジボブが好きで、このブートローダーについてカーニさんとプランクトンから名前を拝借してます。僕の起動する Linux では GRUB じゃなくて Krabs を使うのが密かな目標です。(spongeと命名した自作OSも作り始める予定です)。

Amazon EC2 で、このブートローダーを使用するオリジナルのジョーク Linux AMI を作成することも目指してます（その名も Sandy Linux AMI 笑）。Rust製の[coreutils](https://github.com/uutils/coreutils)に、init に Rust製のsystemdである[rustysd](https://github.com/KillingSpark/rustysd)を使用しようかなと考えています。sshは[これ](https://pijul.org/thrussh/)でイケる? 夢が広がりますね。

あと、githubのstarはすごい嬉しいものであることがわかったので、これからどんどんstarしていこうと思いました。

最後まで読んでいただきありがとうございました。
いいね、コメント、アドバイス、issue、プルリクとかありましたら、ぜひお願いしますmm。

https://github.com/o8vm/krabs