CPU実験で自作CPUにUNIXライクOS (xv6) を移植した話

今年のCPU実験では、有志からなる我らがX班が、おそらくCPU実験史上初である自作CPUへのOS (xv6) 移植に成功しました。コア係とコンパイラ係の面々がそれぞれまとめ記事を書いていたので、OS係から見たOS移植のまとめも書こうかなと思います。こんなことしてましたってことが伝わればいいなと思います。

この記事を読む後輩やらなんやらがいたら、ぜひ僕らがやったようなことはさっさとクリアしちゃって、さらにさらに面白いことをする踏み台にしていってほしいですね。

どなたが読んでもある程度概要が伝わるよう、まずCPU実験とは何かということをさらっと書いた後、実際にxv6を移植するにあたってやったことをまとめたいと思います。

CPU実験とは

CPU実験は僕の学科(理学部情報科学科)で3年冬に行われる、半年間にわたる学科名物演習です。

最初の週で4~5人程度の班に分けられた後、それぞれの班でオリジナルのCPUアーキテクチャを考案しそれをFPGA上に実装、加えてそのCPU用のocamlサブセットコンパイラを作り、作ったCPU上で課題のレイトレプログラムを走らせる、というものです。当然この命令セットが動く仮想マシンなんてものはこの世に存在しないので、自分たちの手でシミュレータを作る必要があります。またコンパイラの下で動くアセンブラも必要ですし、課題のプログラムがレイトレなのでCPUにはFPUも載せる必要があります。まぁこれがなかなか大変な演習で、過去には失踪者が出た例もあるとかないとか・・・。

ちなみにこのCPU、VHDLというハードウェア記述言語で作らされるのですが、大学でVHDLの書き方を習ったことは1ミリもありません。心温まるお話ですね。*1

自分たちで作ったCPUでOSを動かそう

さて、CPU実験の概要はそんな感じです。お気づきの方もいるかと思いますが、上の説明にはOSの話なんて全く出てきません。ちょっと説明を加えます。

実験の流れとして、ふつうはまずどんなに遅くてもいいから課題のプログラムが確実に動くCPUを一つ完成させます。これはよく1stアーキテクチャとか呼ばれます。で、実際に動くCPUを一つ作りさえすれば単位が確定するので、早めに完成した班はあとは割と自由な時間となるのです。ここから高速化を目指すのが正統派の班の行動なんですが、中にはゲームを作ったりスピーカーで音楽を奏で始めたりとお遊びに力を入れる班もでてきます。僕がコア係として所属していた6班は余興大好きの方の班で、CPU実験開始当初からOSを動かそうという話になっていました。この話に他班も興味を示した結果、晴れて8人くらいからなる合同班、X班が結成され、「自分たちのCPUでOSを動かすぞー!」という運びになったわけです。

xv6

移植するOSは、MITが教育用に作成した、Unix v6インスパイアなシンプルなOSであるxv6にしました。xv6はUnix v6と違ってANSI Cで書かれていて、x86上で動作します。教育用なだけあって、ユーザーランド周りやプロセス周りが少し貧弱ですが、シンプルかつUnixライクなOSとして割と十分な機能を持っています。詳しい情報はwikipedia公式サイトででも。

大変!

xv6移植する移植すると言っても、なんでもかんでもゼロから作ろうってわけですからソフトウェア側だけでも障害がいくつもあります。

  1. コンパイラどうすんねん
    CPU実験では普通mlコンパイラを作ります。当然Cなんてコンパイルできません。

  2. リンカも割とリッチなやつが必要っぽい
    xv6ではリンカスクリプトを活用してバイナリファイルをくっつけたりディスクイメージをくっつけたりします。CPU実験で作ったツールチェインにはリンカなんて高級なものはなく、だいたいアセンブラ複数ファイルをぶん投げたら一つのバイナリを吐くような作りになってしまっています。

  3. デバッグ用のシミュレーターどうすんねん
    CPU実験で作ったシミュレータはありますが、1命令1命令ずつ実行するシンプルなもので、割り込みとかありませんし仮想アドレス変換なんかもありません。

  4. というかそもそもCPUの機能には何がいるねん
    リングプロテクション?仮想アドレス?割り込み?そもそも何がいるのか不明瞭です。ここが決まらないと2のシミュレータも作れません。

  5. ハードウェア資源は足りるの?
    僕らのFPGA基盤に乗っているもので使えるメモリはだいたい4MBのSRAMだけ*2だし、通信手段はシリアルポートだけ*3です。SDカードやIDEディスクをくっつけてる余裕はなさそう。

  6. xv6、x86にべったり依存して書かれすぎ
    ブートの最初の方で4MBページ拡張使うわ、char 1byte, int 4byteであることを前提にハードコーディングするわ、スタックいじくりまくったトランポリンするわで移植性皆無です。まあxv6という名前がx86Unix "v6"から来てそうだし仕方ない。

まあこんな感じで不安点はいくらでもあったんですがX班OS移植プロジェクトは12月くらいにスタートしました。

ここからはだいたい時系列順でやったことを書いていこうかと思うのですが、かなり長いので先に動いてるOSの話を読みたい!みたいな方は3月の話以降を。

11月終わり~12月初頭

まず1個目の「コンパイラどうすんねん」が解決します。なんと「C89コンパイラフルスクラッチ」です。正直これでいくと思ってませんでした。インド人もびっくり。最初はid:wasabizgccllvmでもやるかーって話してた記憶があるんですが、うどんくん(id:kw_udon)が突然「Cコンパイラ書いてきた」と言って簡単なパーサとエミッタを積んだコンパイラを持ってきました。楽しそうだったので最速完動した3班由来のメンバーであるwasabizと@b-inaryが加わって、この3人がコンパイラ係としてフルスクラッチコンパイラを書き始めます。これが後のuccとなります。ucc開発についてはうどんくんの下の記事が詳しいです。

kw-udon.hatenablog.com

5個目の「ハードウェア資源は足りるの?」も解決します。このころはまだOSが決まっていなかったのですが、xv6が標準でシリアルで外部と通信し、しかもメモリは1MBも食わない、memfsも簡単に使えるのでディスクもいらないなどなど、我らがFPGA基盤にぴったりだということが判明し、xv6で行くことになります。コードがコンパクトなのもとてもgood。

12月中旬

OS係が動き始めます。また、12月8日に僕が作ったCPU実験本筋のCPUとシミュレーションのレイトレ結果の数ビットのdiffがようやくなくなり、6班(僕らの班)が完動します。原因は、ISE(VHDLから回路を合成してくれるすごいやつだよ)が吐くFPUの回路の挙動が、実際に書いたVHDLの挙動と食い違っていたせいでした。すごいやつって書いたけどあいつ絶対許さない。VHDL文のwhile文は合成できても使っちゃダメですよ絶対。班公式の仕事としての完動は3番目だったように思います。

ここらで6班メンバーがX班のOS係やらMMU係やらになります。OS係のメンバーが最終的なものと同じ、僕(@nullpo_head)、warelle@mhの3人に固まります。

12月終わり~1月中旬

4個目の大変ポイント、「というかそもそもCPUの機能には何がいるねん」が解決し始めます。

OS班のメンバーが固まったので、週1で輪読でxv6のソースコードリーディングを始めます。xv6にはMIT謹製の教科書があるんですが、結局これはあんまり読みませんでした。今からxv6を読みたいという人、OSの基礎的な概念を理解しているなら特に読む必要はなさそうです。このころ同時に僕はxv6をMIPSに移植し始めました。MIPS移植がなさそうだったので(ARMはある)。一週間くらいでスケジューラが動き始めるくらいまで移植が完了します。(外部周辺機器の割り込み周りの制御とユーザープログラムの起動はまだうまくいかない)ここで書き換えのためにMIPSについて、xv6の動作を理解するためにx86についてそれぞれ調べまくったので、割り込み周りの概念とMMUの概念を理解します。CPUに必要なものが見えてきます。

自作アーキテクチャシミュレータ上のxv6でも、色々コメントアウトして頑張った結果、ブートシークェンスの最初の文字

xv6...
cpu0: starting...

が表示されます。つまり、このころにはもうuccがxv6の大部分をコンパイルできるほど成長しています。uccすごい。

ここで大学のテストが挟まって、2月くらいまで一旦作業が鈍化します。

2月

テストが終わりました。OS係に本腰が入ります。全体のタスクがだいたい把握できたので4週間ほどでOS移植が完了する線表を引きました。

1日にはMIPS移植もPICあたりの初期化が完成し(マジ大変だった)、割り込みハンドラのひとまずの書き換えも完了してユーザープログラムが起動する直前まで移植されます。ここでの経験を基に自作CPUの割り込みの仕様と仮想アドレス変換の仕様を決めました。「というかそもそもCPUの機能には何がいるねん」が解決します。xv6は割り込みと仮想アドレス変換さえあれば動く!!周辺機器はタイマーとシリアルしかないので大がかりな割り込みコントローラはいらないし、デマンドページングがないのでリングプロテクションもいりません! なお、仮想アドレス変換はx86のページング部分と同じ方式にしました。一見CPUの実装が大変になるように見えますが、速さを犠牲にしてTLBが毎回ミスするような挙動にすれば実装が簡単なのではという話になっていました。(まあ最終的には優秀なコアができあがったので、TLBにあたるものもきちんと乗りました。) ちなみにOS移植が本格的に動き始めたので、MIPS移植は以降手がつけられなくなります。残念。

あとは怒涛の進捗が始まるので週区切りで記します。。。。

1週目

コメントアウトだらけのなんちゃってブートシークエンスではなく、mhにより初期化処理がきちんと移植され始めます。warelleがx86アセンブリを自作アーキテクチャのものに書き換えます。僕は、策定した仕様を基にCPU実験用のシンプルなシミュレータに割り込みシミュレーション機能をつけ、仮想アドレス変換の対応も完全にしました。シミュレータにOSを動かすのに十分な機能が付きます。またMakefileを自作アーキテクチャ用のものに書き換えました。全体として色々と開発の下地が整っていきました。

2週目

僕は大変ポイントその2、「リンカも割とリッチなやつが必要っぽい」に対応します。アセンブラ作者のb-inary先生に.setディレクティブの追加と、ファイルのアセンブル時の先頭アドレスを変更できる機能の追加をお願いします。xv6では主にカーネルの終端アドレスであるend, バイナリイメージであるfs.imgとinitcodeの先頭アドレスやサイズを得るためにldのbinary blobsを使うのですが、追加してもらった.setディレクティブさえあれば、
1. まずend, _binary_initcode_startなどには0xdeadbeefなどの適当なダミー値を.setで与えてアセンブル、ひとまずカーネルのサイズを得る
2. そのカーネルのサイズからそれぞれのシンボルの値を計算、.setディレクティブで無理やり追加
3. 計算しなおしたその値でもう一度アセンブル
4. できあがったカーネルにfs.imgやinitcodeをcatでくっつける
5. こうしてできあがったカーネルのヘッダを再計算してごにょごにょ書き換え、完成
という手順で同等のことを達成、原始的なリンカっぽいことができるようになります。ステキ。rubyスクリプトMakefileでこれらをやってやります。 先頭アドレスの変更は、もちろんカーネルのbaseアドレスやユーザープログラムのベースアドレスをそれぞれ0x80000000や0x0に返るためのものです。
warelleは割り込み周りを書き換えます。割り込み周りは理解が難しい、流れを把握するのが難しい、デバッグが難しいで難しい揃いです。僕がMIPSを移植したときにはgdbという神器があるのでまだ楽でしたが、独自シミュレータにはデバッグ機能など皆無だったのでデバッグがかなり難しかったのではないかと思います。(このときだったかどうかちょっと記憶が怪しいのですが)デバッグのしづらさに耐えかねたのかwarelleはシミュレータにディスアセンブラデバッグダンプ機能を付けてきました。これを皮切りにシミュレータのデバッグ機能はOSチームによりどんどん高機能化され、最終的には下図みたいな感じに成長します。

f:id:nullpo_head:20150324100129p:plain

このころmhはファイルシステム担当として、ファイルシステム周りを教科書を読みつつ理解していました。

3週目~

山あり谷ありで書き換えが進んだxv6、なんだかんだ言って動きません。特にuccの、charもintもともに32bitであるという仕様が響きました。実はCの仕様ではsizeof(char) <= sizeof(int)なことしか要求されてないので、これは仕様的には合法ですし僕らのアーキテクチャ上では実際問題ありませんでした。しかしxv6はx86を前提として書かれているので、sizeof(int) == 4なことを前提にポインタの値に定数をガンガン加算したりしてくるので、色々と不整合が起きてしまいます。これが生むバグが分かりづらい上に量も多かったので、結局uccの方にcharを8bitにしてくれるようお願いすることになります。このchar 32bit問題をuccチームに任せた後は、僕は最初のentry段階のページ初期化を書いたり割り込み周りがきちんと動くよう修正トライ&エラーを繰り返したりしました。要は大変ポイントその6、「xv6、x86にべったり依存して書かれすぎ」を地道につぶす作業です。

27,28日

slackを見返すとやたらこの日に進捗が生まれてます。多分悔いを残して2/29日に突入しないためだと思います。ucc班が爆速でchar 8bit対応を終わらせてくれた後なんやかんやで頑張り、ついに、初めてのユーザープログラムinitが起動します。そしてそのあと怒涛の進捗をだし、ついにシェルまで起動します。その後、MIPS移植ではたどり着かなったユーザープロセス周りの移植をどんどん進めました。
再現しづらいバグやら割り込み仕様の不備やらが発覚、潰しは発生、潰しは発生しますが、なんやかんやでなんとか乗り越えます。なんやかんやはなんやかんやです。

3月

1日、そしてxv6の移植が完了します。シミュレータ上でxv6が動きました・・・!

f:id:nullpo_head:20150324091208p:plain

線表上では3/4が完成目標だったので、結構余裕ができました。ちなみに最終発表の日数は3/17です。

余興かくあるべし

ここからはもともとお遊びだったOS移植のお遊びがさらに加速します。

まずmhの手によって4時間くらいでミニcursesが作られ、シミュレータ上でslが走ります。(遊びとなると進捗ってめっちゃ速くでるんだなあ・・・)

f:id:nullpo_head:20150324091346p:plain

warelleはなんだかマインスイーパーがしたくなりました。

f:id:nullpo_head:20150324091509p:plain

また、ここらへんで僕の趣味でディレクトリ構造をきれいにして、ヘッダファイル類をモダンなunixの構造っぽく変更、またuccチーム 謹製のlibcを移植しました。たとえば今まで

#include "types.h"
#include "stat.h"
#include "user.h"

char buf[512];

void
cat(int fd)
{
  int n;

  while((n = read(fd, buf, sizeof(buf))) > 0)
    write(1, buf, n);
  if(n < 0){
    printf(1, "cat: read error\n");
    exit();
  }
}

みたいな感じで独自仕様感がたっぷりだったcatは、

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

char buf[512];

void
cat(int fd)
{
  int n;

  while((n = read(fd, buf, sizeof(buf))) > 0)
  write(1, buf, n);
  if(n < 0){
    printf("cat: read error\n");
    exit(1);
  }
}

こうなりました。しかもwasabizの手によりX班コアGAIAも完成*4、シミュレータよりはるかに速く動くので遊びやすいし開発しやすい。満を持して、今回屈指の完成度を誇る2048が作られます。

f:id:nullpo_head:20150324091905p:plain

この2048、本当に完成度が高く、コア係のwasabizは実機上でずっとこの2048で遊んでました。
ちなみに2048では非ラインバッファリングな入力が使われていますが、xv6にはもともとこの機能はなく、read, writeに加えてioctlをdevswのアクションとして追加し、ICANONやechoを制御するtermios関連の機能を新たに追加しました。なのでこんなに完成度の高い2048が遊べるxv6はGAIA上のものだけです。
(なお、V6インスパイアなxv6としてはgtty, sttyシステムコールを追加するほうがそれっぽいとは思うんですが、xv6にはttyの概念がないのでこれを追加するのは変だなと思ったのと、ioctlがUnix V7からの登場と意外と古株だったのでioctlを採用しました)

さて、少しかっこいいお遊びとして、xv6-gaiaには小さなアセンブリが載っています。うどんくん製です。また、warelleがまさかの1日で作ってきたミニviも載っています。この二つを使うとできることが、

f:id:nullpo_head:20150324092118p:plain f:id:nullpo_head:20150324092125p:plain

こんな感じのFPGA上での動的なプログラミングです。CPU実験としてはかなりレベルが高い余興なんじゃないでしょうか。

最後の余興

CPU実験のもともとのお題は、「自作CPU上でレイトレを動かせ」でした。せっかくOSが動いたんですから、やることは決まっています。「自作CPU上"のOS上"でレイトレ」です。うどんくんとb-inaryさんが課題のmlプログラム、min-rtをCに移植してくれました。完成したのは最終発表当日ギリギリです。
が、ここで予期はしていたが目を背けていた問題が発生。完成したバイナリファイルがでかすぎ問題です。実はxv6のファイルシステム上では80kbくらいを越えるファイルが作れないのです。
まあでも予期はしていただけに解決策は用意していました。この完成したmin-rtをconsoleのようなデバイスファイルとして作ることです。consoleデバイスがreadアクションでユーザー入力を返すように、デバイスとして実装したmin-rtのreadアクションで_binary_min_rt_startから読み込んだ値を返せば、アドホックな分岐などのあまりトリッキーなことをせずに綺麗にリンクできます。ちょっとバグも埋め込んだりはしましたが、なんとか最終発表の1時間前には完成しました。

f:id:nullpo_head:20150324092158j:plain

多分どの代でも1回は冗談で言っていたであろう、「OSを作ってそのうえでレイトレ完動」が実現してしまいました。。
次はなんだろう、多分どの代でも一回は出るであろう冗談は「raytraceという1命令だけ作ってハードウェアレイトレする」ですかね。。割と対極にあるしCPUなんて作り飽きたぜ!って後輩がいれば挑戦してみるのはいいかもしれませんね。

書き残し、およびもっと技術的なことについて

GAIA版xv6には、上では書ききれてない変更がまだたくさんあります。たとえばb-inaryさんによってシェルのreadlineが強くなってたり、僕もpwdコマンド追加してたりmhによってhaltシステムコールが増えてたり。ともかくユーザーランドは割と魔改造されてるので気になる方はソースを直接見ていただければと思います。
そして上では割と軽いノリで「だいたい何をしたか」を記述するのに注力したので、OS移植の詳細は割と省いています。書ききれていない難しい箇所 or 興味深い箇所がまだまだたくさんあったりします。*5 GAIAやMIPSカーネル予約レジスタのk0, k1レジスタが必要な理由とか、興味深いことやハマりどころがまだいくつかあるので、いつかまとめられたらなーと思います。特にMIPS移植の際のMIPSに関する情報、ノウハウについてはどこかにまとめる必要性を感じています。。

感想

FPGA上へのOS移植は、やはり楽しかったです。OSの仕組みとx86MIPSについてかなり勉強になりました。CPU実験本筋でCPUも作ったしアセンブラも作ったしX班でOSも移植したしでかなり色々経験しました。 ただ振り返ってみればCPU実験にしてはこじんまりとしたことしかしなかったなという反省もあります。xv6移植に関しては、(もちろん簡単ではないことなのだけど)○○くらいのタスク量でやれそうだなという予想で始まって実際にその通りに達成して、「自分の想定内で想定通りの働きをしただけ」、という少し寂しい感想がないでもないです。実際作った線表から2日以上ずれたことなかったし。ここまで大きくなるのか!と驚かされたuccや、CPU実験であるにも関わらず割り込みもMMUも実装したGAIAコアのような、「本当にできるのか?」という感じの挑戦をしたかったかな、と少し思います。Linuxに初めから、とは言わずも、ucLinuxくらいには挑戦していればよかったかもしれない。
もっともX班の活動はこれで終わりではなく、今はうどんくんが「OS移植班全体の野望」という所のLinuxを動かすための算段を、wasabizと考えています。こっちは文句なしで難しいし実現できるか正直わからないので、頑張りたいなと思っている次第であります。
あと全然違う話ですがMIPS移植完成させねば。昨日久しぶりにMIPS版xv6を触り、TLB周りの処理を修正してinitcodeまで起動させました。初ユーザープログラムです。追試やら課題やらを回避しつつ4月初頭には完成させたいですね。

...

以上でCPU実験まとめ終わりです。後輩の方、興味を持った方、ぜひぜひCPUを作ったりOSを移植したりしてみてくださいませー

最後にX班のメンバーをまとめておきます。

...

*1:僕らの学科はほかにも心温まる話が溢れている。たとえば1回目の講義で緩くHaskellに入門したと思ったら次の週には初めて名前を聞くモナドを駆使した超ヘビーな課題を解かされ、3回目にはつい先日入門したはずのHaskellで言語処理系を書かされる

*2:本当は数百MBのDRAMがついてるのだが動かした人はいない。DRAM遅いし。

*3:USBもあるが制御が大変になる

*4:詳細がwasabiz.hatenablog.comにあります。

*5:たとえば割り込みのtrapasm.Sの先頭。割り込みが発生してトラップフレームをスタックに積む際、必ずsp以降ではなくsp - 4以降から格納します。最初はspから積んでいたのですがそれではごく稀にバグが出てしまっていました。これはspより先を使わない規約にしているつもりだったのに、callの際にどうしても1命令幅分だけspより先の領域を使うことがあり、そこで割り込みが発生した時にその領域をつぶしてしまっていたからというものでした。他にもGAIAではブートステージでx86のように4MBページ拡張を使って初期ページディレクトリーを確保することができないため、現在のpcが0x0000hogeでも0x080000hogeでも動くように作ったPICのようなCコードで初期ページディレクトリーを作ったり、少し面白い実装になっています。