旅する情報系大学院生

旅と留学とプログラミング

東大のCPU実験で自作コア上の自作OS上で自作シェルを動かした話

東大の情報科学科では3年の秋学期にCPU実験という、自分たちでCPU、コンパイラ、シミュレーターを作ってレイトレーシングを動かすことが単位要件の名物実験があります。僕らの班では12月初旬に単位要件を満たすCPUは出来ていたので、2/20にあった成果報告会までの間にIwashi班という自作CPU上でlinuxを動かすことを目標とした余興班を作ってこのエントリのタイトルにあるような結果に終わったのでその報告をしたいと思います。

コンテキストスイッチしている画像:
f:id:yamaguchi_1024:20180227131550j:plain

目次

対象とする読者

  • (メイン)これから情報科学科に入ってCPU実験をして面白い余興をしようと思っている後輩
  • 後輩の進捗を覗きに来たISの先輩
  • その他面白いと思ってくれた界隈の人

CPU実験でははじめにFPGAとコンテストサーバーを渡されてレイトレをしろと言われるだけで基本的には何も教えてはくれないので学生は先輩のブログなどを読んで情報を収集します。自分達も先輩のブログに助けられたので今度は後輩が参考になるようなブログを書きたいと思います。

自己紹介

私の班でIwashi班の元となった班が6班で、メンバーは僕(コア)、maane123(コンパイラ)、mdj982(シミュレーター)とあと一人最終的に失踪してしまったしかく係*1で構成されていました。Iwashi班のメンバー*2は僕(コア書いた、linuxのデバドラ書いた、シェル書いた、発案したり人々に仕事振ったりした)、kcz146(CでフルスクラッチでOS書いた、QEMUに追加命令実装した)、mdj982(シミュレーター書いたりデバッグ手伝ってもらったり色々)、hikalium(QEMUのバグ直した、カーネルパニックさせた)です。

Adelie(6班1stアーキ)のソースコードがここ、Iwacpu(班横断2ndアーキ)のソースコードがここです。

できたこととできなかったこと

  • コアでlinux動かすのはできなかった
  • QEMU、linuxを移植してQEMU上でlinuxが起動してカーネルパニックしてるところが見れた

f:id:yamaguchi_1024:20180227171514p:plain

  • 自作OSがコア上で動いた!

シェルが動いている動画(バックで話しているのでとてもうるさい):
youtu.be

コンテキストスイッチしている動画:
youtu.be

技術的な詳細

ISA

僕らの班ではISAはriscvのものを元にした。理由は私が将来性を感じて好きだったから(当時)。東大であったriscv dayにも行ったりなどもしてriscvについてはかなり知見を深めたので今ではいいところと悪いところが見えてきた。

よかったところ

他の班はMIPSやPPCを元にしていたが、それよりはずっとマシだったと思う。MIPSやPPCは良くも悪くも古いので、なんでこんな仕様にしたんだ・・・という仕様が沢山ありそれが嫌だったので自分たちで修正しました・・というような班が多かった。その点、riscvは反省を元に作られているので単純かつ必要十分で仕様に対して怒りが湧くことはほぼなかった。おすすめできるISAである。また、riscvに関する書籍は限られているためFPGAマガジンのRISCV特集という本がとても役に立った。コンパイラとシミュレーターにRV32Iの仕様書を渡してこれでいくからよろしく!と言ったら大体形にはなる。仕様はここに書いてある。

悪かったところ

riscv, ISAは良い。ISAは良いが・・・・。他が発展途上すぎる。全体的に理想論すぎるという印象を受けている。riscvはバークレーが「オープンソースならぬオープンISAを作ることによって企業の興隆にソフトウェア資源が依存するのをやめよう」というモチベーションで始められたもので、バークレーはMIPSの開発元でもありアーキテクチャ関係ではとても強い大学なので流石にしっかりしているが、アーキテクチャの仕様というのはISAだけではないだろう。riscvはISA以外の仕様はほぼないので実装任せな部分が非常に大きく、結局実装任せじゃないか・・という気持ちになった。バークレーのOBが作ったベンチャーのSiFiveという会社がriscv実装のチップを提供していて、こことバークレーくらいしか諸々のソフトウェア資源のメンテナンスをしていない。例えば、ここからビルドできるgnu-toolchain,pkやriscv-qemu, riscv-linuxなど。実装されてはduplicateされているオプションなどもあったり、freedom-u-sdkというSiFiveが提供しているtoolchain wrapperなども32bitがunsupportedなどととても発展途上である。いくらISAが綺麗でも環境が整備されて使われなければなんの意味もないので本当に頑張ってほしい。

結論

riscvのISAは、自分で実装するのはおすすめだ。実際riscvのFounderであるKrste*3も、中小企業で小さいCPUを作らなければならなくなったら是非riscvを使って欲しいと言っていた。その需要は現に僕が使ったのであると思う。しかし、チップの性能はISAでは決まるものではないしIntelなどのCPUを量産するような大企業にとってはriscvを採用するアドバンテージが何一つないので普及するかはかなり疑問である。

1stアーキテクチャ(Adelie)で実際に使われていた命令*4:
   LUI: Load Upper Immediate *5
   JAL: Jump And Link by Immediate
   JALR: Jump And Link by Register
   BEQ: Branch on Equal
   BNE: Branch on Not Equal
   BLT: Branch on Less than
   LW: Load Word
   SW: Store Word
   ADDI: Add by Immediate
   ADD: Add
   SUB: Sub
   SLLI: Shift Left Logically by Immediate
   SRAI: Shift Right Arithmatically by Immediate
  
   FLW: Floating-point Load Word
   FSW: Floating-point Store Word
   FADDS: Floating-point Add
   FSUBS: Floating-point Sub
   FMULS: Floating-point Multiply
   FDIVS: Floating-point Divide
   FSQRTS: Floating-point Square-Root
   FEQS: FLoating-point Equal Setting
   FLES: Floating-point Less-or-Equal Setting *6
   FSGNJXS: Floating-point Sign-Injection in Xor *7
   FMVSX: Move to Floating-point register from Integer register *8
   FCVTWS: Convert to Integer register from Floating-point register *9
   FCVTSW: Convert to Floating-point register from Integer register *10
  
以下の3つはRISCVの仕様にはない独自命令
   OUT: Output *11
   IN: Input *12
   ROT: Rotate Endian *13

Iwacpuで実際に使われていた命令*14:
lui
addi
jalr
sb
sw
lw
lbu
jal
add
slli
bne
bltu
bge
blt
sub
and
andi
or
beq

in
out

ステート管理

fetch, decode, execute, writeback, memoryという5段階に加えてfloatingやuartもあるのでstoleも付けた。細かくステートで分けるのは良かったと思う。実装も難しくないし愚直に実装しても300Mz余裕で出たので結果的に結構早くなる。詳細はコードを見て欲しい、結構コメントも書いてあるので読みやすいと思う。

Floating point

IPコアが使えるので楽勝である。ISAのところでも書いたが、浮動小数点関係の命令はFLW,FSW,FADDS,FSUBS,FMULS,FDIVS,FSQRTS,FEQS,FLES,FSGNJXS,FMVSX,FCVTWS,FCVTSWを実装した。

UART

方針としては 1. axi uartliteを使う2. axi uartを使う があると思う。MMIOや夏学期に実装するオレオレuartを使う手もあるが正直全然おすすめしない。僕らの班はuartliteを使った。axi uartよりは若干単純なのでとりあえず動かしたい班にはとてもいいと思うが、僕らは最終的にOSを動かしたくてDRAMも使いたかったのでDRAMを使うモチベーションがある人はuartを使うと二度手間にならなくていいと思う。

UARTはナメている人が多いがギリギリまで完動しなかった班はUARTでバグらせていたり、UART書き換えたら完動したという班もあったのでちゃんとloopback回路を作ってbaud rate上げても大丈夫なこと確認する、としっかりやったほうが後々無限にバグらせることがなくて良いと思う。

自作OS/Shellの仕様

タイムラインのセクションでも順を追って詳しく話しているので2月のところを読んで欲しいが、まとめると以下のようになる。

動機

Linuxは冷静に考えてこの数日で無理なので、小さいOSを動かしたい。OSの本質の1つとして、タイマ割り込みからのコンテキストスイッチによるマルチタスクがあるので、ここを実装すれば、OSを動かせたことになる。(たぶん)

やること

  • ノイマン型。命令メモリ・データメモリをわけず、1つのメモリを共有する。-> とりあえずデュアルポートにしようと思う
  • シミュレータとコアに、MMUによる仮想アドレス→物理アドレス変換を実装する。
  • シミュレータとコアに、雑タイマ割り込みを実装する。
  • コンテキストスイッチをする、OS Kernelを実装する。

実装方針

1ページは4096byte。32ページによる仮想アドレス空間。つまり仮想メモリアドレスは0x20000未満。よって、下12bitがページ内オフセット、それ以外がページ番号を指す。

増えるレジスタ

  • Page Register 32bit 32個: 32個のページが、物理アドレスのどこから始まるかを表す。
  • MMU Control Register 1bit: MMUによる仮想アドレス機能を有効/無効にする。無効のときは、メモリアドレスは、そのまま物理アドレスを表す。
  • OS Handler Address Register 32bit: タイマ割り込みハンドラの関数アドレス(物理アドレス)を格納する。タイマ割り込み時は、MMUを無効に設定しつつ、この関数に飛ぶ。
  • Next Program Counter Regiter(NPC) 32bit: タイマ割り込みハンドラから戻るべき先を格納する。常に仮想アドレスが入っている。
  • (カウンタレジスタ) 適当bit: もう既にコアにもシミュレータにもあるって言ってた。MMUが有効である間、一命令実行する毎にインクリメントされる。これが一定数(1000くらい?)になったとき、タイマ割り込み動作を行う。total_cnt, 10’b1111111111ごとに初期化する。

増える命令

  • mvptg %r2, %p7 (MV GeneralReg <- PageReg)
  • mvgtp %p7, %r2 (MV PageReg <- GeneralReg)
  • iret (Return From Interruption Handler): MMUを有効化しつつ、PCにNPCを代入
  • mvgto %r7 (MV OS handler reg <- General Reg)
  • mvnpctg %r7 (MV General Reg <- NextPC)
  • mvgtnpc %r7 (MV NextPC <- General Reg)

atomic命令はnop

すべて R-type, custom-2 (opcode = 0b1011011)

mvptg %r2, %p7 (MV GeneralReg <- PageReg)
funct3=0b000
funct7=0b0000000
ps1=PageReg
rs2=0
rd= GeneralReg

mvgtp %p7, %r2 (MV PageReg <- GeneralReg)
funct3=0b000
funct7=0b0100000
rs1=GeneralReg
rs2=0
pd=PageReg

mvgto %r7 (MV OS handler reg <- General Reg)
funct3=0b001
funct7=0b0000000
rs1=GeneralReg
rs2, rd = 0

mvnpctg %r7 (MV General Reg <- NextPC)
funct3=0b010
funct7=0b0000000
rd=GeneralReg
rs1, rs2 = 0

mvgtnpc %r7 (MV NextPC <- General Reg)
funct3=0b010
funxt7=0b0100000
rs1=GeneralReg
rs2, rd = 0

iret (Return From Interruption Handler)
funct3=0b111
funct7=0b0000000
rs1, rs2, rd = 0

MMUの挙動

上述したとおり、仮想アドレスがあったとき、Offsetは下12bit。PCを元に命令をとってくるとき、およびメモリ読み出し・書き込みいずれにおいても、MMUが有効であるなら、仮想アドレスをPageNumとOffsetに分けたとき、物理アドレスPageReg[PageNum] + Offsetにアクセスする。MMUが無効であるなら、それはそのまま物理アドレスである。

タイマ割り込みの挙動

コア・シミュレータは、命令を実行するたびに、「MMUが有効であるならば、カウンタレジスタをインクリメントする」をする。この直後、カウンタレジスタが、一定値(とりあえず#define TIME_INT_PERIOD 1000とする。)以上のとき、次に示すタイマ割り込みを行う。そうでないときは、普通に次の命令に進める。

タイマ割り込み:
カウンタレジスタに0を代入
MMUを無効化する
NPCを本来次に実行すべきPCにセット
PCをOS Handler Registerの内容にセット

iretの挙動

MMUを有効化する。
PC <- NextPCをする。

Kernelの実装

コンテキストスイッチをする。

シェル

書けそうなコマンド
echo: やるだけ
kill: プロセス構造体を壊す 生きてるかどうかboolをpsに足す
ps: プロセス構造体にアクセスする

カーネルはメモリ読み込み
inでプロセス3つくらい読む、一つはshell
fib, ポエムのプロセス
in, out 終わるまで割り込まないで

タイムライン

  • 9月

初授業に出る。班がくじで決まる。mdj982が遅刻してきたので最初はしかく係だったがシミュレーター書いてくれてシミュレーターになった。

  • 10月

最初はモチベが高かったので一週間で足し算くらいは動いて中旬にはfibが動いて月末には浮動小数点数の実装を始めた。

  • 11月

11月はLLVM dev meetingなどがあり前半から中盤はコアの進捗はほぼ0、代わりにコンパイラとシミュレーターが頑張ってくれていた。後半にやる気が出て浮動小数点数やuartの実装を始めた。

  • 12月

12月に入ってから怒涛のやる気が出て4日間学校に泊まりデバッグをした結果12/05に完動した。それから1週間2nd用にmul, divの命令を増やしたりコードを読みやすくかなり書き換えたりしたが結局この期間のコードは最終的に使わなかった。冬休みより1週間早く自主冬休みにしてヨーロッパ行くなどした。

  • 1月

試験勉強をしていた。後半は研究室行ったり渡航関係の細々したことしたり人と会ったりしていて進捗は出なかった。

  • 2月

20日の発表会の2週間前から怒涛のやる気が出た。ここから細かく見ていく。

  • 2/8

riscv-toolchainを使ってとりあえずlinuxをビルドしてみる。32bitでビルドし、ブートローダーを持ってきてシミュレーターにこのlinuxとブートローダーが動くようなシミュレーター作ってとお願いする。

  • 2/9

gccをビルドする際にRV32IのみだけではなくRV32gcというデフォルトでビルドしていたためcompressed命令が含まれていてシミュレーターが頭をひねる。linuxのカーネルコンフィグをいじって最小構成にしようと試みる。
Iwashidoc - Google ドキュメント

  • 2/10

GitHub - sifive/freedom-u-sdk: Freedom Unleashed Software Development Kit このsifiveというバークレー発のriscv実装している会社が提供しているツールチェインが32bitサポートされていなくてチーンとなる。

  • 2/11

hikaliumやkczらと地下で泊まりをする。この時点ではデバドラやQEMUに追加命令は実装していない生のriscvだが、QEMU上でlinuxのカーネルパニックが見れる。

  • 2/12

寝てた。

  • 2/13

Emperorと命名して命令を足したりリファクタリングをしていた2ndコアが動かないことが判明し、1stのAdelieを元に浮動小数点数命令をはじめとした使わない命令を消して動くコアにした。

  • 2/14

linuxデバドラとQEMUに追加uart io命令を書く。シミュレーターはlinuxがelfなのでelfのヘッダー読むように変えていた。

  • 2/15

自作アーキ用にパッチを当てたlinuxがQEMU上でカーネルパニックをするようになった。次はコアだが
- kernelは展開すると仮想アドレスだしかなり大きくなってしまうので、elfやgzipなどで圧縮してブートローダで展開しないといけないが実装とてもつらい
- ハードウェアの検出部分で死んでいると考えられるのでそこらへんの関数全部無効にしないといけない
- riscvの仕様通りに仮想メモリやシステムレジスタを実装するの厳しい
等の理由でlinux移植は現実的に無理だろうという話になり、目標を自作コア上で自作OSを動かすことに軌道修正した。
f:id:yamaguchi_1024:20180221064151p:plain
その時のslack
この時kczと地下で会議をして2時間くらいで自作OSの仕様が決まり、じゃあこれを実装していこうという話になった。
自作OS仕様 - Google ドキュメント

  • 2/16

コア、シミュレーター、OS共に自作OS用に実装を始める。この日に三人とも大体実装が終わる。この日から2/20の発表会まで僕は地下に泊まり込む。TSG*15でxv6分科会をしてxv6のコードを読んだり書いたりしてたのがだいぶ役に立ったっぽい。

  • 2/17

OSがコードを綺麗にしたり微修正したりする。シミュレーターとコアはmin-rtで使われてないけどカーネルでは使われている命令(lbu, sb)などのデバッグ、カーネル用に作った命令のデバッグなどをする。コアがなんとなく動く。

  • 2/18

カーネルをcoeにしてコアに読み込ませてからのコアデバッグが始まる。MMUのon/offがちゃんとできているか、タイマー割り込みで動いているか、ちゃんと割り込みハンドラに飛んでいるか、レジスタは退避されてるか、など。in/out命令で半日以上溶かしたが、inやoutでuartで通信している際にタイマー割り込みが来るとuartのstatusを管理しているレジスタが退避されず保存されるので次のin/outで死ぬということだった。

  • 2/19

動く
f:id:yamaguchi_1024:20180221065530p:plain
シェルの実装を始める。適当に2時間くらいで書いた。せっかくマルチタスクなのでpsとkillは実装したかったのでそのためにカーネルがプロセスを起動する際にレジスタでプロセス構造体のアドレスとプロセス数を渡すように変える。シミュレーターでは動きコアは何も変えてないのに無限にバグらせていて時間を溶かしていたらgccがmul命令を吐いていてコアでは実装されてないので動かないがシミュレーターでは動くという事案でとてもああああとなっていた。gcc, どうやら構造体のサイズが一定値を超えるとオフセットでアクセスしたいのかmulをしたくなるらしい、知るかそんなの。
f:id:yamaguchi_1024:20180221070019p:plain

  • 2/20

ということでシェルが動く。ちょっとしたシェルスクリプト動くようにしてみる?ということでシミュレーターが変数を実装する。
これめっちゃ面白い。
f:id:yamaguchi_1024:20180221070239p:plain

プレゼンをする。まあまあ受けたっぽくてよかった。

感想

本当に現代のパソコンはすごい。張り合おうという気が全く起こらない。すごすぎる。

個人的に今日(2018/2/27現在)からスイスに行ってしまうので17erの最後にとても良い思い出作りが出来てよかった。メンバーの人には本当に感謝している。kczは彼の班のコアをやりながらOSを一瞬で書いてくれたしmdjは優秀だし無限に精神が安定しているので無限に頼らせて頂いた。地下で4連泊などしながら大声で喚きまくっていたので一緒にいた他の人々にも感謝である。

質問や疑問があればお気軽にどうぞ。

追記

たくさん反応やコメントを頂いて、フォロワー以外にそんなに読んでもらえると思ってなかったので驚いています。理情の後輩や先輩を対象に書いてしまったのでバックグラウンドの説明が全然なくて混乱した方もいると思います。背景や歴史が気になる方は是非先輩たちのブログを読んでみてください。
CPU実験で自作CPUにUNIXライクOS (xv6) を移植した話 - 豆腐の豆腐和え
Eureka Engineering – Medium
自作CPU向けCコンパイラをつくってOS動かした話 (CPU実験まとめ) - kw-udonの日記

頂いたコメントに対してなんとなく空中リプしてみようかと思います。

「自分たちでCPU、コンパイラ、シミュレーターを作ってレイトレーシングを動かすことが単位要件」←いつ頃からやってるんだ?CPUとかスクラッチから作るわけじゃないんだよね?

CPUとシミュレーターはサンプルコードも無く、フルスクラッチで作ります。コンパイラはmin-camlという言語のコンパイラがここにあるので、これを元にして自分たちのアーキテクチャに移植したり最適化をしたりします。

レイトレーシングだけやたら高レイヤーの話だな。レイトレーシングを指定している意図はなんだろう。記事中でレイトレの話は出てこないしどうしてたんだ。

レイトレは、min-rtというmin-camlで書かれたレイトレのコードが与えられるのでそれをコンパイルして自分のCPUで実行してこんな感じの画像が出てくるのが単位要件という話です。
f:id:yamaguchi_1024:20180301082330j:plain

車輪の再

車輪の再再再再再再再再再再 くらいですね。しかし再発明って言うからには自分で0から考えないといけない気がしますが僕らはかなり前提知識があったので再発明ですらないですね。

半期でFPGAでCPUを実装してOS乗せてアプリを走らせる、なんて授業はコンピュータアーキテクチャの勉強の総ざらいとして良さそう。大学の授業で出来る時代なのね→ほぼソフトウェアですもの

理情のハードウェア構成法の講師の先生は冗談抜きでFPGAはソフトウェアと言っているので本当にそうだと思います。

さすが。ところでトランジスタとかの組み合わせて一つ一つの CPU 命令を実装して写真の基板で一つの CPU ってこと?電子回路超苦手だった

いや流石にそんなことはないです・・。写真のFPGAはkcu105というのを使っていて授業の最初に貸し出されます。電子回路を扱う授業は2,3年でありましたがCPU実験で回路図書くようなことはない気がします。流石にタイミングチャートくらいは書きますが。

何を言ってるのかよく分からない

すいません・・・。

RISC Vがriscv表記だったので、最初なんだかわからんかった

てきとうに書いていましたが正式名称はRISC Vです。

*1:去年からFPGAのボードが新しくなりFPUがIPコアで与えられるようになったので4人班の1人が定職にあぶれ、一番最初の授業で誰かが役割の所に四角を書いたことでしかく係という名称が定着しました。僕らの班のしかく係は失踪してしまいましたが他の班ではライブラリ書いたり他の仕事をしているしかく係もいました。

*2:slackにはもっといるんだけどここではgithubにコミット履歴がある人しか書いてない

*3:奥さんが日本人ということで日本に来ていた!

*4:シミュレータがまとめてくれたものを貼っただけ。持つべきものは優秀なシミュレータである。

*5:上位20bitの即値生成、即値は全てLUIとADDIで行われる

*6:比較結果1or0を整数レジスタにセット

*7:二つの浮動小数点の符号のXorをとり、片方の浮動小数点の符号をその結果としたものを出力、ある浮動小数点数の絶対値を取る時に使われている

*8:32bitそのまま浮動小数点レジスタにコピーする、浮動小数点即値の生成に用いる

*9:浮動小数点数を、変換して整数レジスタに格納

*10:整数を、変換して浮動小数点数に格納

*11:整数レジスタの下位8bitを出力する

*12:整数レジスタの下位8bitに読み取る、上位24bitはそのまま

*13:例えば、0x12345678を0x78563412にする、INとSLLIと組み合わせて 32bit整数の読み取りに用いた。今回のコンテストサーバにはビッグエンディアンモードが一応あるが、リトルエンディアンが普通だと思ったので…

*14:sb, lbuはAdelieでは使われていなくてIwashiではchar型などをコンパイルするためにsb, lbuが新しく使われたのでバグらせた・・・。

*15:東京大学コンピュータ系サークル TSG 東大の新入生是非入部して〜〜