kawasin73のブログ

技術記事とかいろんなことをかくブログです

TCP/IP プロトコルスタックを自作した

RFC は裏切らない。どうも、かわしんです。僕は RFC に裏切られました。

さて、今週の頭から4日間開催された KLab Expert Camp に参加して、TCP/IP プロトコルスタックを実装してきました。今回はその体験記を書いていこうと思います。

成果物ですが、こちらになります。

github.com

ネットワークデバイスの抽象化、EthernetARP、IP、TCP を実装しました。使用言語は C 言語です。詳しくは後半で説明します。

KLab Expert Camp とは

今回参加したのは KLab 株式会社の実践的なインターンプログラムである KLab Expert Camp です。記念すべき第 1 回目として「TCP/IPプロトコルスタック自作開発」が開催されました。

応募ページはこれです。

https://klab-hr.snar.jp/jobboard/detail.aspx?id=vtS4F0TN0tQ

実はこのインターンは 21 卒以降の学生が対象であり大学4年の僕は対象外なのですが、どうしても参加したいとツイッター上で言ったところ、講師の 山本さん のご好意で特別に参加させていただけることになりました。本当にありがとうございました。

このインターンプログラムは講師の山本さんが実装して公開されている学習用の TCP/IP スタック microps がベースになっています。(マイクロピーエスと呼ぶらしいです)

github.com

プログラム自体は、山本さんの講義を受けながら microps の実装を理解する「基本コース」と、microps をベースに各自自由に何かを作る「発展コース」の 2 つを選ぶことができました。

僕は「発展コース」を選び microps を写経しながら TCP の実装を改善していました。

そして、無事修了することができました。

f:id:kawasin73:20190830155259j:plain

最後の修了証もそうですが、KLab さんのインターンはすごく待遇がよくて、懇親会での寿司やピザ、お昼ご飯、交通費全支給、遠方からの参加者の宿泊の手配など運営の方の気配りと予算がすごくて、すごくよかったので学生のみんなは参加したほうがいいと思います。(宣伝)

頑張ったこと

インターンが始まる 2 日前の 24 日から実装を始めて、全部で 6 日間実装していました。

まず、microps の下のレイヤーから写経して、都度テストで動くことを確認しながら進めていきました。やりたいことは TCP での通信だったので必要のない ICMP や IP のルーティング機能、DHCP などは飛ばしています。

僕が実装した順番はコミットログを見るとわかりやすいと思います。

github.com

IP を実装した後に ARP を実装したのですが、案外 ARP の実装が量が多くて大変でした。

全体として 5000 行くらいを書いていたことになります。

f:id:kawasin73:20190830164805p:plain

TCPRFC を実装する

全体的に microps はコメントは少ないですが実装の内容はシンプルでわかりやすかったです。また、ネットワークデバイスの抽象化などの設計もよくできていて参考になりました。しかし、TCP の実装をみるとシンプルな分色々な処理が TODO になっていたので仕様に忠実に実装するために、tcp.c は自力で RFC を読みながら実装しました。

実は昔に DMM の時のメンターさんから RFC を読んで実装する訓練をした方がいいとアドバイスされていて、ずっとやってみたかったのでちょうどいいきっかけになりました。RFC を実装することは、1 次ソースを読むことでTCP の正確な仕様を理解できるだけでなく、標準化されたドキュメントの書き方を学べたり、仕様を忠実に実装する訓練にもなります。

TCPRFC は複数にわたりますが、基礎は RFC 793 に全て書いてあります。

そして、RFC 793 の 3.9 Event Processing には TCP の基本的な処理がそれぞれのイベントごとそしてコネクションの状態ごとに全て記述してあります。中身は英語ですが、If xxxxxx then set yyyy to zzzz のように擬似コードっぽく書かれているのでそれをそのまま C 言語に書き直しました。

一番辛かったのは 65 ページ から始まる SEGMENT ARRIVESイベントのイベントハンドリングを実装していた時です。相手からの TCP セグメントのヘッダを読んで処理を行うのですが、このイベントだけで RFC の 12 ページを使って記述されています。長い。

そして、このイベントでは全部で 8 ステップに渡ってヘッダのフラグなどを検査して内部状態を変えたり TCP セグメントを送信したりします。TCP はコネクションごとにステートマシンで表され、 LISTEN, SYN-SENT, SYN-RECEIVED, ESTABLISHED, FIN-WAIT-1, FIN-WAIT-2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT, CLOSED の 11 個のうちのどれか状態を持ちます。そのため、8 ステップの各ステップでそれぞれの状態ごとに処理を書かなくてはいけません。複数の状態で処理が共通していたりするので実際には 88 種類よりは少ないですが、それでも十分多いです。正直最後の方は心が折れかけました。

実装した機能

正直 TCP の最低限の機能を実装するので精一杯でパフォーマンスの向上などはできませんでした。microps から発展させたことはだいたいこんな感じです。

  • tcp_rx のイベントハンドリングの処理を RFC に忠実に実装した
  • tcp_api_send で 1500 バイトまでの送信にしか対応していないのを、セグメント化に対応して任意の長さのバイト列を送信できるようにした
  • フロー制御を実装した
  • 再送タイムアウトだけでなく、ユーザタイムアウト、TIME-WAIT タイムアウトに対応した

最初は輻輳制御アルゴリズムをいくつか試してみるとか息巻いていたんですが、結局は輻輳制御をするところまでたどり着けませんでした。

また、microps のいくつかのバグを発見してフィードバックのプルリクエストを作成しました。

感想

C でのバイナリプロトコルの処理方法 を学ぶことができたのがよかったです。TCP は固定長のヘッダ(オプションによって拡張されますが)であるため、セグメントポインタをヘッダ構造体のポインタにキャストすることでゼロコピーでヘッダを解析できます。

もちろんエンディアンはネットワークバイトオーダなので利用時に変換をしないといけないですが、このバイト列にヘッダ構造体を被せるだけでヘッダのパースができる感覚は新鮮で、さすが生のメモリを操作する C だなと思いました。

microps では複数のネットワークデバイスの種類に対応しているのですが C 言語での抽象化 の方法を学びました。以下のようなオペレーションの関数ポインタを集めた構造体をデバイスの種類ごとに定義して多態性を実現します。

struct rawdev_ops {
  int (*open)(struct rawdev *dev);
  void (*close)(struct rawdev *dev);
  void (*rx)(struct rawdev *dev, void (*callback)(uint8_t *, size_t, void *),
             void *arg, int timeout);
  ssize_t (*tx)(struct rawdev *dev, const uint8_t *buf, size_t len);
  int (*addr)(struct rawdev *dev, uint8_t *dst, size_t size);
};

そして、案外 RFC は曖昧 であることも知れました。RFC自然言語で書かれているためどうしても曖昧さがあり、その解釈を間違えると正しく動きません。

ここのコメント にまとめてありますが、SYN-RECEIVED 状態で ACK を受け取った時に ESTABLISHED 状態に移行したあと、次のステップを処理すると思っていたのですが実は同じステップの ESTABLISHED 状態の処理を繰り返すことが期待されていたようでした。switch - case 文で break するか fall through するかはこの記述だけでは曖昧でした。

  if the ACK bit is on

    SYN-RECEIVED STATE

      If SND.UNA =< SEG.ACK =< SND.NXT then enter ESTABLISHED state
      and continue processing.

        If the segment acknowledgment is not acceptable, form a
        reset segment

RFC には裏切られることもあるので注意が必要です。

まとめ

RFC を読んで 6 日間で TCP/IP スタックを作り上げるのは結構大変でしたがなんとか形になるものが完成してよかったです。

また、このような素晴らしいインターンプログラムを素晴らしいサポートで開催していただいた KLab 株式会社の皆さんには感謝申し上げます。ありがとうございました。


最終日の成果発表の資料です。