xv6にネットワーク機能を実装した
在宅勤務に移行してから1ヶ月半ほど経過しました。通勤という概念が消滅したおかげで午前中から活動できるようになった @pandax381 です。
要約
フルスクラッチで自作した TCP/IP プロトコルスタックを xv6 に組み込み、一通りの機能が動作するようになりました。
I publish the implementation of TCP/IP network stack on xv6. I ported my user-mode TCP/IP stack, which was originally developed for learning, and added the e1000 driver and socket system calls. Some parts are still not enough, but they are working.https://t.co/nht9JDMVbl
— YAMAMOTO Masaya (@pandax381) March 11, 2020
経緯
かれこれ7〜8年くらい経つんですけど、ライフワークとしてお勉強用のTCP/IPプロトコルスタックの開発をほそぼそと続けています。
一般的に、プロトコルスタックはOSの機能の一部としてカーネル内部に存在しているのですが、この自作プロトコルスタックは、作りやすさを重視した都合でユーザ空間のアプリケーション用のライブラリとして実装しています。
最下層に位置するリンクレベルの入出力は PF_PACKET / BPF / TAP を利用するお手軽仕様で、純粋にパケット処理に専念できるようになっています。
やや作りが粗い部分もありますが、Ethernetフレームの送受信からTCPセグメントのやり取りまで全てを自前で処理しています。「プロトコルスタックってどんな作りになっているんだろう」と興味を持った人が、手を出して雰囲気を掴むのに丁度いいくらいのボリュームになっているんじゃないかと思います。
（物理デバイスや論理インタフェースの抽象化とかそれなりに作り込んであるので、興味があったらコード見てください）
毎年、インターンシップを希望する学生を受け入れていて、彼らの頑張りによって DHCPクライアント機能やパケット転送機能、更にはDPDKサポートといった改良が加えられいますが、いずれも1〜2週間という短い期間で成果を出してくれました。
その流れで、昨夏には KLab Expert Camp という合宿イベントを開催しました。
KLab Expert Camp 開催決定！第1回テーマは「TCP/IPプロトコルスタック自作開発」で、講師は僕が担当します。日程は 8/26〜29 の4日間での開催、交通費・宿泊費は全て KLab が負担します。プロトコルスタック自作に興味のある学生のみなさん、一緒に楽しい夏を過ごしましょう！https://t.co/SVyMOzaeq8
— YAMAMOTO Masaya (@pandax381) April 26, 2019
4日間、ひたすらプロトコルスタックを開発するというマニアックな合宿イベントにもかかわらず、全国からたくさんの学生が参加してくれ、実装解説を通じて基本的な仕組みを学んだり、別言語への移植や機能追加に取り組んでくれました。
参加者からのフィードバックがすごく良くて今後も定期的に開催したいなと思う中で、最近の動向を見ていると「自作CPUで動かしている自作コンパイラでビルドした自作OSに自作プロトコルスタックを組み込みたい」というヤバイ人が出現する可能性も十分ありそうな気がしてきます。
少なくとも、ユーザ空間での動作を前提としてたライブラリの状態からOSのカーネルに組み込もうとした際にどんな罠が潜んでいるかを把握しておかないことには、十分にサポートしてあげられないことは目に見えています。そんなわけで「まずは自分でやってみるか」というのが、この取り組みのそもそもの動機です。
手頃なOSを選定
恥ずかしながら、僕はOS自作を嗜んでおらず「自分のOS」を所有していません。30日OS自作本も「いつか読もう」と積んである始末なので、OS自作からはじめていると時間が掛かりすぎてしまします。だからと言って Linux や BSD だと、ベースにするには規模が大きすぎます。
こういった用途には、コンパクトな xv6 が向いていそうな気がします。
CPU自作関連の話題でも頻繁に登場していますし、いまさら説明するまでもないと思いますが、xv6 は Version 6 UNIX (V6) を x86（マルチプロセッサ環境）向けに再実装したものです。MITがオペレーティングシステムの講義用に開発し、MIT以外にも数多くの教育機関が教材として採用しています。
コード量は10,000行程度で、OSの実装にさほど詳しくなくても全体を見渡すことができるボリュームです。充実したドキュメントと先人たちが公開してくれている情報が豊富にあるのも心強いです。
最近は RISC-V 向けの実装に移行したようで、MITの講義資料も最新のものは RISC-V 版がベースになっています。x86 版は 2018 年度以前のアーカイブを参照しましょう。
どこからはじめるか
xv6 にはネットワーク機能が一切含まれていないため、NICのドライバから書く必要があります。自作プロトコルスタックではリンクアクセスはOSの機能（PF_PACKET や BPF）を利用していてドライバにはノータッチだったので、もう一段下の世界へ降りることになります。
xv6 は QEMU 上で動作させながら開発を進めることになるので、NIC は QEMU で使えて情報も豊富そうな e1000 (Intel 8254x) をターゲットにするのが良さそうです。
まずは、ドライバのエントリポイントのダミーを用意して Hello, World! でも出力するようなコードを書き、PCI デバイスのドライバのリストに追加してあげるところからはじめたら良さそう ...と思ったのですが、 探してもそれっぽいコードが全く見当たりません。
はい、xv6 は PCI をサポートしていないのでした。
したがって xv6 で NIC を扱うためには
- PCIバスをスキャン
- 接続されているデバイスを検出
- 対応するドライバを呼び出す
という一連の処理から作り込む必要があり、更にもう一段下の世界へ降りることになるわけです。だんだんと上昇負荷が厳しくなりそうですね。
PCI周りの処理
PCIバスのスキャン とか言うとなんだかすごく難しそうに聞こえますが、I/Oポートを叩いて情報を読む、という処理の繰り返しです。そして、この辺はOS自作界隈のみなさんが素晴らしい情報を公開してくれています。
コンフィグレーション領域ってなんぞ？という状態でしたが uchanさん の資料を読んで PCI を完全に理解しました（してません）。
以下の Linux Kernel を解説したドキュメントも参考になりました。
これらの解説を読みながら少しづつ進めていけば PCI バスをスキャンしてデバイスを検出するコードが書くのはさほど難しくないと思います。なお、xv6-net では PCI の最終的なコードは JOS という別の OS から拝借することにしました。
- https://pdos.csail.mit.edu/6.828/2018/jos.git
JOS は、xv6 と同様に MIT がオペレーティングシステムの講義で使うために開発している OS です。JOS は一部が意図的に削られている未完成のOSであり、xv6 の解説を聞いたあとに、JOS の実装を進めて完成させるという構成のようです。また、xv6 がモノリシックなカーネルであるのに対して JOS はマイクロカーネルという違いもあるようです。
読み比べてみると JOS の方が諸々整理されていてキレイに書かれている気がするものの、全体の雰囲気はかなり似ています。そして、JOS には PCI 周りのコードと e1000 ドライバのスケルトン（ほぼなにも書かれていない空っぽのファイル）が用意されているため、これを使わせてもらうことにしました。
上記の pci.c は JOS のコードそのものです。xv6 に手を出す人は高確率で JOS のコードも読んでいるはずで、それであれば僕が書き散らかしたコードよりも JOS のコードを使わせてもらったほうが読む人が理解しやすいだろうと考えた結果です（コードをそのまま組み込むため、辻褄合わせに少し手間を掛けていたりします）。
pciinit() を main() の中から呼んであげると、起動時に PCI バスをスキャンして接続されているデバイスが検出されます。
PCI: 0:0.0: 8086:1237: class: 6.0 (Bridge device) irq: 0 PCI: 0:1.0: 8086:7000: class: 6.1 (Bridge device) irq: 0 PCI: 0:1.1: 8086:7010: class: 1.1 (Storage controller) irq: 0 PCI: 0:1.3: 8086:7113: class: 6.80 (Bridge device) irq: 9 PCI: 0:2.0: 1234:1111: class: 3.0 (Display controller) irq: 0 PCI: 0:3.0: 8086:100e: class: 2.0 (Network controller) irq: 11
ベンダIDとデバイスIDをキーにドライバのエントリポイントを定義しておくと、デバイス検出時にそれを叩いてくれます。
struct pci_driver pci_attach_vendor[] = {
{ 0x8086, 0x100e, &e1000_init },
{ 0, 0, 0 },
};
NICのドライバ
PCI のデバイスを検出できるようになったら、次は NIC のドライバを書きます。
JOS のソースには kernel/e1000.c と kernel/e1000.h が含まれていますが、どちらも空っぽで、Intel のドキュメントをちゃんと読めという圧が伝わってきます。
参考になりそうなコードがないか探してみると、xv6 の RISC-V 版のリポジトリには NIC の初期化処理まで書かれたドライバの雛形がありました。初期化処理を参考にしつつ、ヘッダファイルはそのまま利用させてもらいました。
- https://github.com/mit-pdos/xv6-riscv-fall19/blob/net/kernel/e1000.c
- https://github.com/mit-pdos/xv6-riscv-fall19/blob/net/kernel/e1000_dev.h
また、大神さん が公開されている本がめちゃくちゃわかりやすくて助かりました。PCIの情報も詳しく書かれていて、こんな情報をタダで読ませてもらって良いのか...と感動しながら e1000 を完全に理解しました（してません）。EPUB版でたら買います。
OSDev.org で紹介されている以下のコードも参考にしました。
他にも、世の中には xv6 向けの e1000 ドライバを書いている人は沢山いるので、github 上でもいくつかプロジェクトを見つけることができます。ただし、どれもポーリングする前提で、割り込みがちゃんと動く状態のものは見つけられませんでした。
一連の作業の中で一番苦戦したのが、パケット受信時に割り込みを発生させることで、1週間くらいハマっていました。ちゃんと書いたつもりでもなかなか割り込みが発生しなく心が折れそうになっていたので、動いたときはめちゃくちゃ嬉しかったです。
（たぶん送受信で使うDMA用のバッファ設定がうまくできていなくて動いていなかったんじゃないかと思っています）
xv6 用の e1000 ドライバが動いたーーー！！！これで自作プロトコルスタックを xv6 へ載せるための準備が整った💪https://t.co/nht9JDMVbl pic.twitter.com/TJYkWVAKAV
— YAMAMOTO Masaya (@pandax381) February 29, 2020
この辺の詳しいことは、また別の記事か薄い本でも書こうかなと思っています。
プロトコルスタック本体の移植
NIC のドライバが動いたので、いよいよ本題のプロトコルスタック本体の移植に取り掛かるのですが、あまり躓くことなくあっさり移植できてしまいまったので、あまり書くことがなかったりします。
pthread を使っていたので mutex を spinlock に置き換えたり、cond をタスクの sleep/wakeup に置き換えたりしたくらいです。あと、タイマーが使えていないので、TCPの再送とかタイマーに依存した処理はまだ動かせていません。
まず、ARP に応答できるようになって
ARPに応答できるようになった！#プロトコルスタック自作#xv6 pic.twitter.com/zjBszDkK6t
— YAMAMOTO Masaya (@pandax381) March 2, 2020
ICMP に応答できるようになって
順調に進んで ping に応答できるようになった！#プロトコルスタック自作#xv6 https://t.co/I7BGOz4jVw pic.twitter.com/0xBivGA9LZ
— YAMAMOTO Masaya (@pandax381) March 3, 2020
UDP で通信できるようになり
自作プロトコルスタック on xv6 の進捗が素晴らしくて UDP 通信に成功した🎉🎉🎉（雑に実装したソケット風のシステムコールを通じてユーザ空間のアプリケーションがカーネル内のプロトコルスタックを利用して通信してる） pic.twitter.com/VUbbeWr0TO
— YAMAMOTO Masaya (@pandax381) March 6, 2020
最終的に TCP も動くようになりました
うぉぉぉ！！！TCP も動いたぞ！！！もともとユーザ空間で動かす前提でこしらえた自作プロトコルスタックが xv6 のカーネル空間で完全に動作してる！！！ https://t.co/juL0ntccyY pic.twitter.com/5tDU1T0B8K
— YAMAMOTO Masaya (@pandax381) March 6, 2020
ソケット
カーネル内でプロトコルスタックが動くようになってもソケットがなければユーザ空間で通信アプリケーションを書くことができません。
自作プロトコルスタックにはソケット風のAPIもあるのですが、これは単なるライブラリ関数なのでプロトコルスタックをカーネルに組み込んだ状態ではユーザ空間のアプリケーションから呼びだせません。
そんなわけで、ソケット風 ではなくガチのソケット（関連のシステムコール）を実装しました。
システムコールの追加にあたっては、xv6 の既存のシステムコールの中から似たようなプロトタイプのものを探して同じように実装しています。
socket() で作られるディスクリプタは、もともと存在しているファイルディスクリプタと互換性を持つように作っているので、ソケットのディスクリプタを close() で閉じたり、recv() / senc() の代わりに read() / write() を使うことが出来ます。
単純なソケット通信のプログラムであれば、Linux 用に書いたコードがそのまま動く程度にはちゃんと作っています。
自作プロトコルスタック on xv6 がいい感じに仕上がった！ソケット関連のシステムコールを真面目に実装したのでよくあるこんなコードがそのまま動くようになった！ちゃんとファイルディスクリプタに紐づけているので read/write を使っても動くし fork しても大丈夫！https://t.co/nht9JDMVbl pic.twitter.com/LQNvWwOpj9
— YAMAMOTO Masaya (@pandax381) March 10, 2020
ifconfig コマンド
シェルからインタフェースの状態を確認したりIPアドレスを設定するために、当初は適当なコマンド（ifget / ifset / ifup / ifdown）と対応するシステムコールを作って、その場をしのいでいました。
雑なシステムコールを実装してコマンドでネットワークインタフェースを制御できるようになった💪#xv6#プロトコルスタック自作 pic.twitter.com/T6LZNEtwOK
— YAMAMOTO Masaya (@pandax381) March 5, 2020
ただ、これだとちょっとダサいので、最終的に ifconfig コマンドを作りました。ip コマンドじゃないのは NETLINK の実装はさすがに厳しいからという理由です。
だいぶ雑だけど ifconfig 作って動くようになった（たぶん大幅に書き直すと思うけどとりあえず push した）#xv6#networking https://t.co/TEbKeGWe3m pic.twitter.com/2mh5tVGiuy
— YAMAMOTO Masaya (@pandax381) March 30, 2020
ifconfig は ioctl() を通じてインタフェースの情報を取得/設定しているので、ioctl のシステムコールを追加し、SIOCGXXX や SIOCSXXX をひたすら作り込んでいます。
おわりに
あれもこれもと作り込んでいたら「自作プロトコルスタックを xv6 に移植した」というよりは「xv6 にネットワーク機能を実装した」という気持ちになったので、このようなタイトルになりました。
あと、勢い余って reddit デビューもしました。
reddit でコメントくれた方の自作OSがしっかり作られていて感動したので紹介しておきます。
まだ先の予定を立てるのは難しいですが、イベントが開催できるような状況になったら、また KLab Expert Camp でプロトコルスタック自作の合宿をやりたいと思っています。その際は自作OSへの組み込みもサポートできるように準備しておきますので楽しみにしていてください！
@pandax381
