コア係とコンパイラ係の面々がそれぞれまとめ記事を書いていたので、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を動かすぞー!」という運びになったわけです。v6インスパイアなシンプルなOSであるxv6にしました。Cで書かれていて、x86上で動作します。教育用なだけあって、ユーザーランド周りやプロセス周りが少し貧弱ですが、シンプルかつUnixライクなOSとして割と十分な機能を持っています。詳しい情報はwikipediaか公式サイトででも。大変!xv6移植する移植すると言っても、なんでもかんでもゼロから作ろうってわけですからソフトウェア側だけでも障害がいくつもあります。コンパイラどうすんねんCPU実験では普通mlコンパイラを作ります。Cなんてコンパイルできません。リンカも割とリッチなやつが必要っぽいxv6ではリンカスクリプトを活用してバイナリファイルをくっつけたりディスクイメージをくっつけたりします。CPU実験で作ったツールチェインにはリンカなんて高級なものはなく、だいたいアセンブラに複数ファイルをぶん投げたら一つのバイナリを吐くような作りになってしまっています。デバッグ用のシミュレーターどうすんねんCPU実験で作ったシミュレータはありますが、1命令1命令ずつ実行するシンプルなもので、割り込みとかありませんし仮想アドレス変換なんかもありません。いうかそもそもCPUの機能には何がいるねんリングプロテクション?仮想アドレス?割り込み?そもそも何がいるのか不明瞭です。ここが決まらないと2のシミュレータも作れません。ハードウェア資源は足りるの?僕らのFPGA基盤に乗っているもので使えるメモリはだいたい4MBのSRAMだけ*2だし、通信手段はシリアルポートだけ*3です。SDカードやIDEディスクをくっつけてる余裕はなさそう。4byteであることを前提にハードコーディングするわ、スタックいじくりまくったトランポリンするわで移植性皆無です。"v6"から来てそうだし仕方ない。こんな感じで不安点はいくらでもあったんですがX班OS移植プロジェクトは12月くらいにスタートしました。ここからはだいたい時系列順でやったことを書いていこうかと思うのですが、かなり長いので先に動いてるOSの話を読みたい!みたいな方は3月の話以降を。11月終わり~12月初頭まず1個目の「コンパイラどうすんねん」が解決します。なんと「C89コンパイラフルスクラッチ」です。これでいくと思ってませんでした。最初はid:wasabizとgccかllvmでもやるかーって話してた記憶があるんですが、うどんくん(id:kw_udon)が突然「Cコンパイラ書いてきた」と言って簡単なパーサとエミッタを積んだコンパイラを持ってきました。楽しそうだったので最速完動した3班由来のメンバーであるwasabizと@b-inaryが加わって、この3人がコンパイラ係としてフルスクラッチでコンパイラを書き始めます。これが後のuccとなります。ucc開発についてはうどんくんの下の記事が詳しいです。kw-udon.hatenablog.com5個目の「ハードウェア資源は足りるの?」も解決します。このころはまだ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に必要なものが見えてきます。starting...が表示されます。このころにはもうuccがxv6の大部分をコンパイルできるほど成長しています。ここで大学のテストが挟まって、2月くらいまで一旦作業が鈍化します。2月テストが終わりました。OS係に本腰が入ります。全体のタスクがだいたい把握できたので4週間ほどでOS移植が完了する線表を引きました。1日にはMIPS移植もPICあたりの初期化が完成し(マジ大変だった)、割り込みハンドラのひとまずの書き換えも完了してユーザープログラムが起動する直前まで移植されます。ここでの経験を基に自作CPUの割り込みの仕様と仮想アドレス変換の仕様を決めました。「というかそもそもCPUの機能には何がいるねん」が解決します。仮想アドレス変換はx86のページング部分と同じ方式にしました。CPUの実装が大変になるように見えますが、速さを犠牲にしてTLBが毎回ミスするような挙動にすれば実装が簡単なのではという話になっていました。(まあ最終的には優秀なコアができあがったので、TLBにあたるものもきちんと乗りました。ちなみにOS移植が本格的に動き始めたので、MIPS移植は以降手がつけられなくなります。あとは怒涛の進捗が始まるので週区切りで記します。1週目コメントアウトだらけのなんちゃってブートシークエンスではなく、mhにより初期化処理がきちんと移植され始めます。warelleがx86のアセンブリを自作アーキテクチャのものに書き換えます。僕は、策定した仕様を基にCPU実験用のシンプルなシミュレータに割り込みシミュレーション機能をつけ、仮想アドレス変換の対応も完全にしました。シミュレータにOSを動かすのに十分な機能が付きます。Makefileを自作アーキテクチャ用のものに書き換えました。全体として色々と開発の下地が整っていきました。僕は大変ポイントその2、「リンカも割とリッチなやつが必要っぽい」に対応します。アセンブラ作者のb-inary先生に.setディレクティブの追加と、ファイルのアセンブル時の先頭アドレスを変更できる機能の追加をお願いします。してできあがったカーネルのヘッダを再計算してごにょごにょ書き換え、完成という手順で同等のことを達成、原始的なリンカっぽいことができるようになります。rubyスクリプトとMakefileでこれらをやってやります。先頭アドレスの変更は、もちろんカーネルのbaseアドレスやユーザープログラムのベースアドレスをそれぞれ0x80000000や0x0に返るためのものです。warelleは割り込み周りを書き換えます。割り込み周りは理解が難しい、流れを把握するのが難しい、デバッグが難しいで難しい揃いです。僕がMIPSを移植したときにはgdbという神器があるのでまだ楽でしたが、独自シミュレータにはデバッグ機能など皆無だったのでデバッグがかなり難しかったのではないかと思います。(このときだったかどうかちょっと記憶が怪しいのですが)デバッグのしづらさに耐えかねたのかwarelleはシミュレータにディスアセンブラとデバッグダンプ機能を付けてきました。これを皮切りにシミュレータのデバッグ機能はOSチームによりどんどん高機能化され、最終的には下図みたいな感じに成長します。このころmhはファイルシステム担当として、ファイルシステム周りを教科書を読みつつ理解していました。3週目~山あり谷ありで書き換えが進んだxv6、なんだかんだ言って動きません。uccの、charもintもともに32bitであるという仕様が響きました。sizeof(int)なことしか要求されてないので、これは仕様的には合法ですし僕らのアーキテクチャ上では実際問題ありませんでした。4なことを前提にポインタの値に定数をガンガン加算したりしてくるので、色々と不整合が起きてしまいます。これが生むバグが分かりづらい上に量も多かったので、結局uccの方にcharを8bitにしてくれるようお願いすることになります。32bit問題をuccチームに任せた後は、僕は最初のentry段階のページ初期化を書いたり割り込み周りがきちんと動くよう修正トライ&エラーを繰り返したりしました。要は大変ポイントその6、「xv6、x86にべったり依存して書かれすぎ」を地道につぶす作業です。27,28日slackを見返すとやたらこの日に進捗が生まれてます。悔いを残して2/29日に突入しないためだと思います。8bit対応を終わらせてくれた後なんやかんやで頑張り、ついに、初めてのユーザープログラムinitが起動します。そのあと怒涛の進捗をだし、ついにシェルまで起動します。その後、MIPS移植ではたどり着かなったユーザープロセス周りの移植をどんどん進めました。再現しづらいバグやら割り込み仕様の不備やらが発覚、潰しは発生、潰しは発生しますが、なんやかんやでなんとか乗り越えます。なんやかんやはなんやかんやです。3月1日、そしてxv6の移植が完了します。シミュレータ上でxv6が動きました・・・!線表上では3/4が完成目標だったので、結構余裕ができました。ちなみに最終発表の日数は3/17です。余興かくあるべしここからはもともとお遊びだったOS移植のお遊びがさらに加速します。mhの手によって4時間くらいでミニcursesが作られ、シミュレータ上でslが走ります。(遊びとなると進捗ってめっちゃ速くでるんだなあ・・・)warelleはなんだかマインスイーパーがしたくなりました。謹製のlibcを移植しました。wasabizの手によりX班コアGAIAも完成*4、シミュレータよりはるかに速く動くので遊びやすいし開発しやすい。満を持して、今回屈指の完成度を誇る2048が作られます。この2048、本当に完成度が高く、コア係のwasabizは実機上でずっとこの2048で遊んでました。writeに加えてioctlをdevswのアクションとして追加し、ICANONやechoを制御するtermios関連の機能を新たに追加しました。こんなに完成度の高い2048が遊べるxv6はGAIA上のものだけです。V7からの登場と意外と古株だったのでioctlを採用しました)さて、少しかっこいいお遊びとして、xv6-gaiaには小さなアセンブリが載っています。warelleがまさかの1日で作ってきたミニviも載っています。この二つを使うとできることが、こんな感じの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時間前には完成しました。どの代でも1回は冗談で言っていたであろう、「OSを作ってそのうえでレイトレ完動」が実現してしまいました。次はなんだろう、多分どの代でも一回は出るであろう冗談は「raytraceという1命令だけ作ってハードウェアレイトレする」ですかね。対極にあるしCPUなんて作り飽きたぜ!って後輩がいれば挑戦してみるのはいいかもしれませんね。書き残し、およびもっと技術的なことについてGAIA版xv6には、上では書ききれてない変更がまだたくさんあります。b-inaryさんによってシェルのreadlineが強くなってたり、僕もpwdコマンド追加してたりmhによってhaltシステムコールが増えてたり。ユーザーランドは割と魔改造されてるので気になる方はソースを直接見ていただければと思います。上では割と軽いノリで「だいたい何をしたか」を記述するのに注力したので、OS移植の詳細は割と省いています。興味深い箇所がまだまだたくさんあったりします。k1レジスタが必要な理由とか、興味深いことやハマりどころがまだいくつかあるので、いつかまとめられたらなーと思います。MIPS移植の際のMIPSに関する情報、ノウハウについてはどこかにまとめる必要性を感じています。感想FPGA上へのOS移植は、やはり楽しかったです。OSの仕組みとx86とMIPSについてかなり勉強になりました。CPU実験本筋でCPUも作ったしアセンブラも作ったしX班でOSも移植したしでかなり色々経験しました。振り返ってみればCPU実験にしてはこじんまりとしたことしかしなかったなという反省もあります。xv6移植に関しては、(もちろん簡単ではないことなのだけど)○○くらいのタスク量でやれそうだなという予想で始まって実際にその通りに達成して、「自分の想定内で想定通りの働きをしただけ」、という少し寂しい感想がないでもないです。実際作った線表から2日以上ずれたことなかったし。ここまで大きくなるのか!と驚かされたuccや、CPU実験であるにも関わらず割り込みもMMUも実装したGAIAコアのような、「本当にできるのか?」という感じの挑戦をしたかったかな、と少し思います。Linuxに初めから、とは言わずも、ucLinuxくらいには挑戦していればよかったかもしれない。X班の活動はこれで終わりではなく、今はうどんくんが「OS移植班全体の野望」という所のLinuxを動かすための算段を、wasabizと考えています。こっちは文句なしで難しいし実現できるか正直わからないので、頑張りたいなと思っている次第であります。あと全然違う話ですがMIPS移植完成させねば。昨日久しぶりにMIPS版xv6を触り、TLB周りの処理を修正してinitcodeまで起動させました。初ユーザープログラムです。追試やら課題やらを回避しつつ4月初頭には完成させたいですね。...以上でCPU実験まとめ終わりです。最後にX班のメンバーをまとめておきます。CPU)...*1:僕らの学科はほかにも心温まる話が溢れている。1回目の講義で緩くHaskellに入門したと思ったら次の週には初めて名前を聞くモナドを駆使した超ヘビーな課題を解かされ、3回目にはつい先日入門したはずのHaskellで言語処理系を書かされる*2:本当は数百MBのDRAMがついてるのだが動かした人はいない。