プロトコルスタックを写経してネットワークを完全に理解したかった日記

2022/10/16

Webページはどうやって表示されるのでしょうか．

「ブラウザでアドレスバーにURLを入力してEnter押してからページが表示されるまでに何が起きているか説明してください」面接で使っていた質問が面白いと話題に

上記の質問には様々なレイヤーでの回答があると思うのですが，私はネットワークの動作に興味を持ちました．というのも，TCP，IP，ARP，Ethernetといったキーワードが関連しているのは教科書や講義で聞いた気がするのですが，それ以上のことはうまく説明できなかったからです．

これらのプロトコルは，普段はカーネル内部に隠れていてあまり意識できません．

しかし，以下の資料を参考にプロトコルスタックを写経すれば，少しは身近に感じられるかもしれないと思いました．

そして完成したものがこちらです．

この動画では，次のようなユーザープログラムを自作プロトコルスタック上で動作させています．

int main(int argc, char *argv[]) {
  // 接続を開き
  int soc = tcp_open_rfc793( /* ...略... */ );

  // リクエストを受け取ったら
  uint8_t buf[2048];
  tcp_receive(soc, buf, sizeof(buf));

  // それを無視して固定レスポンスを返し
  char *response =
      "HTTP/1.1 200 OK\r\n"
      "\r\n"
      "<html><head><title>hello</title></head><body>world</body></html>";
  tcp_send(soc, (uint8_t *)response, strlen(response));

  // 一方的に接続を切って
  tcp_close(soc);

  // 落ちる
  return 0;
}

はい．カスのWebサーバー です．

しかしカスであっても 「ブラウザでアドレスバーにURLを入力してEnter押してからページが表示される」 ことは確かです．

カスサーバーからのレスポンスがブラウザに表示されている

この間にプロトコルスタック内部では何が起こっていたのでしょうか．それは画面左側のログにすべて出ているのですが，

プロトコルスタックのログ

さすがに分かりづらいので，以下会話形式1でお送りします

1. プロトコルスタックのセットアップ

先程は割愛していたのですが，Webサーバーの起動前に以下のセットアップ処理を行っていました．

// Step 1: プロトコルスタックを初期化
net_init();

// Step 2: ネットワークデバイスをセットアップ
struct net_device *dev = ether_tap_init(ETHER_TAP_NAME, ETHER_TAP_HW_ADDR);

// Step 3: IPアドレスを登録
struct ip_iface *iface = ip_iface_alloc(ETHER_TAP_IP_ADDR, ETHER_TAP_NETMASK);
ip_iface_register(dev, iface);

// Step 4: プロトコルスタックを開始
net_run();

Step 1: プロトコルスタックを初期化

ユーザープログラム「プロトコルスタック初期化してくれ」

net「ワイはプロトコルスタック全体を管理するリーダーやで．よっしゃ，まずはintr君を初期化するで」

net「intr君は割り込みやタイマーでワイを呼び出してくれるんや．例えば，通信をスムーズに処理するためには受信と解析を非同期に処理することが重要なんやけど，そこで彼が役立つで」

net「intr君，初期化してくれ」

intr「各種シグナルを受信できるように設定しました」（今回のプロトコルスタックは簡単のためにユーザーランドで実装されているので，ここではシグナルを使って割り込みを再現します）

net「よし，次にarp，ip，tcp君，初期化してくれ」

arp「netさんに自身を登録するやで．プロトコルは以下のような構造体で表されているんや．まぁnetさんに管理してもらうための申請用紙みたいなもんやな」

struct net_protocol {
  struct net_protocol *next; // 複数のプロトコルを単方向リストで保持する
  uint16_t type; // プロトコルタイプ．ARPなら0x0806（https://ja.wikipedia.org/wiki/EtherType）
  struct queue_head queue; // 受信キュー
  void (*handler)(const uint8_t *data, size_t len, struct net_device *dev); // 受信時に呼び出してほしい処理
};

// 受信キューの中身
struct net_protocol_queue_entry {
  struct net_device *dev; // 受信したネットワークデバイス（後述）
  size_t len; // 受信データの長さ
  uint8_t data[]; // 受信データ
};

arp「必要な欄を埋めてnetさんに渡したら登録完了や．ARPパケットが来たら呼んでや．あと，ARPキャッシュ（後述）を掃除するタイマーも開始したで」

ip「netさんに自身を登録したで．IPパケットが来たら呼んでや」

tcp「ipさんに 自身を登録したで．TCPセグメントが来たら呼んでや．あと，セグメントの再送タイマーも開始したで」

net「初期化完了や」

Step 2: ネットワークデバイスをセットアップ

ユーザープログラム「ネットワークデバイスを初期化してくれ．デバイス名はtap0，ハードウェアアドレスは00:00:5e:00:53:01」

ether_tapデバイスドライバ「環境依存の処理はワイが担当するで．今回はユーザーランドでの実装やから，TAPデバイスを使ってパケットを受け取るで．intrさん，パケットが来たらワイを呼び出してくれ」

ether_tapデバイスドライバ「環境依存な情報は設定したから，あとはetherさん頼むわ」

ether「よし，以下のようなネットワークデバイス構造体を初期化するで」

struct net_device {
  struct net_device *next; // 次のネットワークデバイス．単方向リスト
  struct net_iface *ifaces; // 上位プロトコルによって定義されるアドレス情報（後述）
  unsigned int index; // 連番，1, 2, 3, 4...
  char name[IFNAMSIZ]; // デバイス名，tap0
  uint16_t type; // 種別．今回はEthernet
  uint16_t mtu; // 一度に送信できるペイロードの長さ．Ethernetでは1500．ジャンボフレームなどは割愛
  uint16_t flags; // 状態．UPとかDONWとか
  uint16_t hlen; // ヘッダの長さ．Ethernetでは14
  uint16_t alen; // アドレスの長さ．Ethernetでは6
  uint8_t addr[NET_DEVICE_ADDR_LEN]; // ハードウェアアドレス．00:00:5e:00:53:01
  union {
    uint8_t peer[NET_DEVICE_ADDR_LEN]; // P2Pの相手．今回は関係ない
    uint8_t broadcast[NET_DEVICE_ADDR_LEN]; // ブロードキャストアドレス．FF:FF:FF:FF:FF:FF
  };
  struct net_device_ops *ops; // 各種ハンドラ
  void *priv; // プライベートデータ．TAPのファイルディスクリプタとか
};

struct net_device_ops {
  int (*open)(struct net_device *dev); // 起動処理
  int (*close)(struct net_device *dev); // 終了処理
  int (*transmit)(struct net_device *dev, uint16_t type, const uint8_t *data, size_t len, const void *dst); // 送信関数
};

ether「これは，普段ip aコマンドなどで見るeth0やwlan0といった物理のデバイスに対応するものやな」

# ip aコマンドの例
$ ip a
# ↓ここに対応する
1: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default qlen 1000
    link/ether xx:xx:xx:xx:xx:xx brd ff:ff:ff:ff:ff:ff
    inet 192.168.0.123/24 brd 192.168.0.255 scope global dynamic noprefixroute wlan0
       valid_lft 12345sec preferred_lft 12345sec
    inet6 xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx/64 scope global temporary dynamic
       valid_lft 12345sec preferred_lft 12345sec

ether「必要な情報埋めたで」

ether_tapデバイスドライバ「netさん，デバイス作ったから報告します」

net「了解，覚えとくで」

Step 3: IPアドレスを登録

ユーザープログラム「さっきのデバイスにIPアドレス192.168.70.2/24を登録してくれ」

ip「net_iface構造体を設定するやで．これは以下のような定義で」

struct net_iface {
  struct net_iface *next; // 次のnet_iface．単方向リスト
  struct net_device *dev; // 対応するネットワークデバイス
  int family; // ファミリ．IPv4とかIPv6とか
  /* depends on implementation of protocols. */
};

// ipでは以下のように拡張して使う
typedef uint32_t ip_addr_t;
struct ip_iface {
  struct net_iface iface; // net_iface
  struct ip_iface *next; // 次のip_iface．単方向リスト
  ip_addr_t unicast; // アドレス
  ip_addr_t netmask; // ネットワークアドレス
  ip_addr_t broadcast; // ブロードキャストアドレス
};

ip「これをネットワークデバイスのifacesにつなぐから」

struct net_device {
  // ...
  struct net_iface *ifaces; // 上位プロトコルによって定義されるアドレス情報
  // ...
};

ip「ネットワークデバイスは，複数の『IPアドレス，ネットワークアドレス，ブロードキャストアドレスの組』を持つことになるわけや．ip aコマンドでも見たことあるやつやな」

# ip aコマンドの例
$ ip a
# 各ネットワークデバイスが
1: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default qlen 1000
    link/ether xx:xx:xx:xx:xx:xx brd ff:ff:ff:ff:ff:ff
    # 複数のIPアドレス，ネットワークアドレス，ブロードキャストアドレスをもつ
    inet 192.168.0.123/24 brd 192.168.0.255 scope global dynamic noprefixroute wlan0
       valid_lft 12345sec preferred_lft 12345sec
    # 複数のIPアドレス，ネットワークアドレス，ブロードキャストアドレスをもつ
    inet6 xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx/64 scope global temporary dynamic
       valid_lft 12345sec preferred_lft 12345sec

ip「最後に，今回登録された内容からわかるルート情報をルーティングテーブルに書くで．ルーティングテーブルとは，パケットを送信したい時にどのデバイスからどこ向けに送り出すかをメモした表なんや．以下のような構造になっとる」

struct ip_route {
  struct ip_route *next; // 次のルート情報．単方向リスト
  ip_addr_t network; // ネットワークアドレス
  ip_addr_t netmask; // サブネットマスク
  ip_addr_t nexthop; // 送信すべき宛先アドレス
  struct ip_iface *iface; // 送信すべきデバイス（ip_ifaceのdevからnet_deviceが取れる）
};

static struct ip_route *routes; // ルーティングテーブル．ルートの単方向リスト

ip「この表の使い方は『送信先IPアドレス & netmaskがnetworkとマッチしたら，ip_ifaceのデバイスからnexthop向けに送り出す』といったかんじやな」

ip「今回は，tap0に192.168.70.2/24が登録されたわけや．ということは，tap0は192.168.70.0/24のネットワークに接続されていることになる．当たり前やけどな」

ip「したがって，今後これらのネットワークに属するホスト，例えば192.168.70.123などと通信するときは，tap0から送信すれば直接やり取りできるのが自明や．したがってルーティングテーブルにそのことをメモしておくで」

network netmask nexthop デバイス
192.168.70.0 255.255.255.0 255.255.255.255 tap0

ip「nexthopは直接の通信に必要ないから，適当に255.255.255.255にしといたで」

ip「このように，ネットワークデバイスにIPを設定しただけで自動的に登録されるルート情報の種類は 直接接続 と呼ばれるで」

ip「ちなみに他の種類は以下のとおりや」

  • 直接接続：デバイスにIPを割り当てたら自動的に設定される情報
  • スタティック：ユーザーが手動で追加した情報
  • ダイナミック：ルーティングプロトコルによって追加された情報（本実装では割愛）

Step 4: プロトコルスタックを開始

ユーザープログラム「いろいろ設定が終わったから，プロトコルスタックを開始してくれ」

net「まずは，intr君を開始するで」

intr「無限ループでシグナルを処理するスレッドを開始します．これは，シグナルがあればその番号に対応する処理を呼び出し，それが終わるとまた即座にシグナルを待ちます」

net「次に，すべてのネットワークデバイスを立ち上げるで．tap0のnet_device_ops->openを呼ぶで」

ether_tapデバイスドライバ「net_device_ops->openはTAPの初期化処理になるようにさっき設定しといたから，ここでワイが呼ばれたで．初期化完了や」

net「よし，tap0のフラグを起動中にして…」

net「プロトコルスタック開始完了や」

2. Webサーバーの処理

以下のことを行っていました

// Step 1: TCP OPEN Call
struct ip_endpoint local;
ip_endpoint_pton("192.168.70.2:80", &local);
int soc = tcp_open_rfc793(&local, NULL, 0);

// Step 2: TCP RECEIVE Call
uint8_t buf[2048];
tcp_receive(soc, buf, sizeof(buf));

// Step 3: TCP SEND Call
char *response =
    "HTTP/1.1 200 OK\r\n"
    "\r\n"
    "<html><head><title>hello</title></head><body>world</body></html>";
tcp_send(soc, (uint8_t *)response, strlen(response));

// Step 4: TCP CLOSE Call
tcp_close(soc);

Step 1: TCP OPEN Call

ユーザープログラム「接続をパッシブオープン（相手からの接続を待つ）するよ．自分は192.168.70.2:80，相手は誰でも良いよ」

tcp「PCBを初期化するやで．PCB（Protocol Control Block）またはTCB（Transmission Control Block）とは，接続情報を管理するための以下のような構造体や」

struct tcp_pcb {
  int state; // 状態．例えば外部からの接続を待っている，接続の確立が完了しているなど
  struct ip_endpoint local; // 自分側のアドレスとポート
  struct ip_endpoint foreign; // 相手側のアドレスとポート
  struct { // 送信に関する情報
    uint32_t nxt; // 送信すべき次のシーケンス番号（シーケンス番号：扱っているデータの位置のようなもの，詳しくは後述）
    uint32_t una; // 送信したが受信を確認していない最も古いシーケンス番号
    uint16_t wnd; // 送信ウィンドウ，相手側の受信能力
    uint16_t up; // 緊急ポインタ．よくわかっていない．Telnetなどで使われるらしい：https://segmentation-fault.xyz/2017/10/14/25/
    uint32_t wl1; // 直近のウインドウ更新でのシーケンス番号
    uint32_t wl2; // 直近のウインドウ更新での確認番号
  } snd;
  uint32_t iss; // 初期送信シーケンス番号（initial send sequence number）．自分側が決めるランダムな値
  struct { // 受信に関する情報
    uint32_t nxt; // 次に受信するべきシーケンス番号
    uint16_t wnd; // 受信ウインドウ．自分側の受信能力
    uint16_t up; // 緊急ポインタ
  } rcv;
  uint32_t irs; // 初期受信シーケンス番号（initial receive sequence number）．相手側が決めるランダムな値
  uint16_t mtu; // 一度に送信できるIPヘッダ + TCPヘッダ + ペイロードのバイト数
  uint16_t mss; // 一度に送信できるペーロードのバイト数
  uint8_t buf[65535]; // 受信バッファ
  struct sched_ctx ctx; // スケジューリングに必要な情報．例えばデータが来るまで待つときに使う
  struct queue_head queue; // 送信キュー
};

// sched_ctxは環境によって異なるが，Linuxだと
struct sched_ctx {
  pthread_cond_t cond; // pthreadの条件変数
  int interrupted; // 割り込みがあったか
  int wc; // 待っている処理の数
};

tcp「今回はパッシブオープンやから，初期値は以下のようになる」

  • state: LISTEN
  • local: 192.168.70.2:80

tcp「LISTENは接続を待っている状態やで．あとは接続要求あるまでやることないな．ctxを使って一旦眠るで……」

ARP解決

ぼく「http://192.168.70.2/にアクセスしよ（ブラウザにURLを入力してEnter）」

Firefox「tcpで192.168.70.2:80をアクティブオープンするよ」

Linuxのプロトコルスタック「192.168.70.2:80を開きたいんだね．通信するならまずハードウェアアドレスが必要だ」

Linuxのプロトコルスタック「ARPキャッシュには……無いみたいだからARPで問い合わせよう」

Linuxのプロトコルスタック「『宛先はFF:FF:FF:FF:FF:FF（ブロードキャスト）．どなたか，192.168.70.2さんのハードウェアアドレスを教えてください．私のプロトコルアドレスはxxx.xxx.xxx.xxx，ハードウェアアドレスはxx:xx:xx:xx:xx:xxです』っと…」

〜〜〜

今回は，TAP（192.168.70.1）にIPフォワーディングを設定しています．そのため，自分側のプロトコルスタックには192.168.70.1から通信が届きます．

〜〜〜

TAP「通信が来た．プロトコルスタックさんを起こすか」

intr「シグナルで起こされました．シグナル番号に対応する処理は……ether_tapさんですね」

ether_tapデバイスドライバ「お，tap0に通信が来たな．TAPから読み込んだフレームをetherさんに渡すで」

ether「フレームを解析するで．IEEE 802.3によればL2のフレーム構造は以下のようになっとる．カッコの中はオクテット数や」

  • 送信先アドレス(6)：xx:xx:xx:xx:xx:xx
  • 送信元アドレス(6)：xx:xx:xx:xx:xx:xx
  • 上位プロトコルのタイプ(2)：EtherType
    • 厳密にはEthernet II（DIX）とIEEE 802.3で意味が異なるらしい．今回は割愛
  • データ(46〜1500)
  • フレームチェックシーケンス(4)：CRC

ether「送信先アドレスと自身のアドレス（tap0）を比較するで．お，一致するからワイらが処理すべきフレームやな」

ether「CRCの検証などは割愛や」

ether「netさん，処理すべきフレームが届きましたやで．上位プロトコルのタイプは0x0806やったわ」

net「了解や．登録されているプロトコルの中で0x0806は……ARP君やな．彼の受信キューにデータを積んだで」

net「受信の仕事はここで一旦終わりや．以降の処理をシグナルハンドラや割り込みサービスルーチンで行うと，その間は他の通信を受信できなくなる」

net「したがって，受信処理は必要なことだけやってさっさと終了することで，スムーズに他の通信もさばけるってわけや」

net「最後に上位プロトコルを起こすシグナルを発して終わりやで〜」

〜〜〜

intr「シグナルで起こされました．シグナル番号に対応する処理は……netさんですね」

net「お，上位プロトコルを起こすか」

net「ARP君が受信キューを持っとるな．受信ハンドラを呼び出すで」

arp「ARPパケットを処理するやで．RFC 826によれば，IPv4のARPパケットは以下のような構造になっとる」

  • ハードウェアタイプ(2)：Ethernetの場合は1
  • プロトコルタイプ(2)：上位プロトコルの種類．IPは0x0800
  • ハードウェアアドレスサイズ(1)：Ethernetは6
  • プロトコルアドレスサイズ(1)：IPは4
  • オペレーション(2)：送信者の動作．要求は1，返信は2
  • 送信先ハードウェアアドレス(6)
  • 送信元プロトコルアドレス(4)
  • 送信先ハードウェアアドレス(6)
  • 送信元プロトコルアドレス(4)

arp「今回のパケットを見る限り，相手さんもワイらと同じくIPとEthernetを使っとるみたいや．互いに通信できそうやな」

arp「せっかく相手さんの情報を得たことやし，これをARPキャッシュにメモっとくで．今後も通信のたびにARP解決するのは非効率やからな」

arp「そしたらARPリプライを返すやで．『プロトコルアドレスxxx.xxx.xxx.xxx / ハードウェアアドレスxx:xx:xx:xx:xx:xxさん，お返事します．ワイらのプロトコルアドレスは192.168.70.2，ハードウェアアドレスは00:00:5e:00:53:01です』っと……．netさん，送信お願いやで」

net「デバイスの送信処理を呼ぶで」

ether_tapデバイスドライバ「ワイが呼ばれたで．etherさん，Ethernetフレームの構築を頼みます」

ether「Ethernetフレームを構築するで．とはいっても，さっきのEthernetフレームの構造にしたがって，必要な場所を埋めるだけや」

ether「ちょっとめんどくさいのは，データの最小サイズがあるから，必要に応じてパディングする処理くらいやな」

ether「ether_tapさん．フレームできたで」

ether_tap「よし，TAPに送信するで」

TAP「おｋやで」

〜〜〜

Linuxのプロトコルスタック「お，ARPの返信だ．ふむふむ．相手さんの情報をARPキャッシュにメモしよ」

Linuxのプロトコルスタック「これで192.168.70.2:80をアクティブオープンするためのTCPセグメントを送れるようになったな」

コネクション確立

Linuxのプロトコルスタック「それでは192.168.70.2:80をアクティブオープンしよう．コネクションは3ウェイハンドシェイクによって，お互いに通信可能であることを確かめることで確立するよ」

Linuxのプロトコルスタック「もう少し詳しくいうと，ここでお互いの初期シーケンス番号を伝え合うんだ．シーケンス番号とは，ざっくりいうと送っているデータの位置なんだけど，これが第三者に偽造されると危険なデータを差し込まれてしまう場合がある（シーケンス番号予測攻撃）．そのため，初期のシーケンス番号を乱数で決めて最初だけ伝え合うことで，安全性を高めることになってるんだ」

Linuxのプロトコルスタック「通信に必要なPCBを用意して，セグメントを構築するよ．RFC 9293によれば，TCPセグメントの構造は以下のようになってる」

  • 送信元ポート番号(2)
  • 送信先ポート番号(2)：80など
  • シーケンス番号(4)：初期シーケンス番号 + 送っているデータの位置
    • ※ただし，SYNやFINなど他の要因でもシーケンス番号は消費されるため，データ位置とは単純には一致しない．
  • 確認番号(4)：このセグメントの送信者が次に受信すると予想しているシーケンス番号
    • 言い換えると，（初期シーケンス番号を差し引けば）相手が次に欲しいデータの位置
    • 確認番号がxxxだとすると「xxx - 1バイトまでのデータは受信したよ，次はxxxバイトからのデータくれるんだよね？」というかんじ
  • データのオフセット(4ビット)：セグメントの先頭からデータまでの長さ（ヘッダの長さとも呼ばれる）
  • 予約領域(3ビット)：なぞ
  • フラグ(9ビット)：例えば以下のようなフラグがある
    • SYN：初期シーケンス番号を送るよ
    • ACK：確認番号入れといたよ
    • FIN：通信終了したいよ
    • RST：問題が起きたから通信リセットしたいよ
  • ウインドウサイズ(2)：このセグメントの送信者が受信可能なデータのサイズ
    • 「私の受信能力はxxxです」というかんじ
  • チェックサム(2)
  • 緊急ポインタ(2)：なぞ
  • オプション：任意項目，今回は関係ない
  • データ：ペイロード．HTTPリクエストなど

Linuxのプロトコルスタック「『シーケンス同期したいです，初期シーケンス番号はこちらです（SYN）』っと……．送信！」

〜〜〜

TAP「フレーム来たで」

intr「シグナルで起こされました」

ether_tapデバイスドライバ「tap0にフレームが来たで」

ether「フレームを解析するで．プロトコルタイプは0x0800」

net「登録されているプロトコルの中で0x0806はIP君やな」

ip「IPパケットを解析するやで．RFC 791によると以下のような構造になってるで」

  • バージョン(4ビット)：IPv4は4
  • ヘッダ長(4ビット)：ヘッダの長さ．4オクテット単位．拡張情報が無いなら5
  • サービス種別(1)：QoS機能？今回はとりあえず0
  • 全長(2)：IPヘッダを含むパケット全体の長さ
  • 識別子(2)：フラグメントの制御に使われる．割愛
  • フラグ(3ビット)：フラグメントの制御に使われる．割愛
  • 断片位置(13ビット)：フラグメントの制御に使われる．割愛
  • 生存時間(1)：パケットの生存期間
    • ルータを通るたびにデクリメントされ，0になると破棄される．パケットがネットワーク上を無限ループするのを防ぐ
  • プロトコル(1)：上位のプロトコル番号．TCPは6
  • チェックサム(2)
  • 送信元アドレス(4)
  • 宛先アドレス(4)
  • 拡張情報：なぞ
  • データ

ip「ふむふむ，IPv4で拡張情報とフラグメントは無し，チェックサムは……よし一致するな．問題なさそうや．宛先は192.168.70.2やな．受信デバイス（tap0）に同じアドレスが付いとる，間違いなさそうや．上位のプロトコル番号は6か．ワイに登録されているプロトコルの中でこの番号なのは……TCPさんや（いうて今回はTCPさんしかおらんけど……）」

ip「tcpさん，セグメントきたで」

tcp「お，了解やで．まずセグメントのチェックサムを計算して……問題なさそうや．」

tcp「宛先に対応するPCBは……1つあるわ．状態はLISTEN，接続を待っとるな．RFC 9293の節3.10.7.2のとおりに処理を進めていくで」

tcp「まず，RSTフラグは……よし立ってないな．接続してないのに切断しようとするやつやったら無視しとったところや」

tcp「次にACKフラグ……も立ってないな．ワイらはまだ何も送信してないのに『受信しました！』とか言われたらおかしいもんな」

tcp「ではSYNフラグは……しっかり立っとるな！接続まちのワイに初期シーケンス番号を教えとるんや」

tcp「ここで，LISTEN状態でSYNを受け取ったので，SYN_RECEIVED状態に移行する必要がある」

tcp「PCBは一種のステートマシンになっていて，その状態遷移は以下の図で表されるんや」

TCP接続の状態遷移図

出典: Figure 5: TCP Connection State Diagram, RFC 9293

tcp「この図の以下のような表記は，上の条件が満たされたら下を実行して状態遷移しろってことみたいやな」

  rcv SYN
-----------
snd SYN,ACK

tcp「つまり，LISTEN状態でSYNを受け取ったら，SYN, ACKを送信してSYN_RECEIVED状態に移行しろって書いてあるわけや」

tcp「というわけで，まずはSYN, ACK応答を最優先で行ってしまうで．PCBに必要な情報を突っ込んで」

  • local（自分のアドレス）：受信セグメントの送信先
  • foreign（相手のアドレス）：受信セグメントの送信元
  • rcv.wnd（受信ウインドウ）：65535．自分のバッファは空だから
  • rcv.nxt（次に受信するシーケンス番号）：受信セグメントのシーケンス番号 + 1
    • セグメントのシーケンス番号までは受信済み
    • 相手は今回のSYNでシーケンス番号を1消費したから，次回は，+1のシーケンスを送ってくるはず
  • irs（初期受信シーケンス番号）：受信セグメントのシーケンス番号
  • iss（初期送信シーケンス番号）：ランダム値

tcp「送信セグメントのヘッダの必要な部分を埋めて，チェックサムなども計算する．セグメントの意味は『先程のSYNを受信しました（ACK），ワイらの初期シーケンス番号はこちらです（SYN）』ってかんじやな．そしたらあとはIPさんおねがいやで」

ip「了解や．まずはどのデバイスから送信するかを決めなあかんな，えーっと，ルーティングテーブルは……」

network netmask nexthop デバイス
192.168.70.0 255.255.255.0 255.255.255.255 tap0

ip「こうなっとるな．今回の宛先は192.168.70.1やから……192.168.70.0/255.255.255.0の行にヒットするな．しかもこれ，nexthopが255.255.255.255やから直接接続のルートや．したがって送信先アドレスはnexthopではなく192.168.0.1にしとくで」

ip「あとはIPヘッダの必要な部分埋めて……あ，送信先ハードウェアアドレスの部分やけど，arpさん，192.168.70.1のハードウェアアドレス知らんか？」

arp「あ，それならARPキャッシュにあるな．xx:xx:xx:xx:xx:xxやで」

ip「ありがとな，これで送信できる．netさん，お願いやで」

net「デバイスの送信処理呼ぶで」

ether_tapデバイスドライバ「etherさん，Ethernetフレームの構築を頼みます」

ether「ether_tapさん．フレームできたで」

ether_tap「よし，TAPに送信するで」

TAP「おｋやで」

tcp「これでSYN, ACKの応答完了や．最後にPCBの更新を忘れないようにするで」

  • snd.nxt（次に送信すべきシーケンス番号）：iss + 1
    • さっきSYNを送信したのでシーケンス番号を1消費
  • snd.una（送信したが受信を確認していない最も古いシーケンス番号）：iss
    • さっき送信したSYN + ACK応答のこと
  • state（状態）：SYN_RECEIVED

tcp「これで完了や」

〜〜〜

Linuxのプロトコルスタック「お！さっきのSYN要求にACKが返ってきた！加えて，相手の初期シーケンス番号もSYNで送られてきた．PCBにメモして，受信できたことをACKで応答しよう」

Linuxのプロトコルスタック「SYN_SENT状態でSYN, ACKを受け取ったから，ESTABLISHED状態に移行できるね」

TCP接続の状態遷移図

〜〜〜

TAP「フレーム来た（ｒｙ」

intr「シグナルで起こされ（ｒｙ」

ether_tapデバイスドライバ「tap0にフレームが（ｒｙ」

ether「フレームを解析（ｒｙ」

net「登録されているプロトコルの中で0x0806は（ｒｙ」

ip「tcpさん，セグメントきた（ｒｙ」

※今後ip以下は同じなので省略します

tcp「お，さっきのSYN, ACKのACKが来たで．ここからはRFC 9293の3.10.7.4節にしたがうで」

tcp「まずはシーケンス番号をチェックするで．ここでは主に，セグメントを受け入れ可能かを以下の条件でテストする」

セグメントを受け入れ可能かテストする条件の表．RFC 9293のTable 6: Segment Acceptability Tests

出典: Table 6: Segment Acceptability Tests, RFC 9293

tcp「今回は単なるACK応答やからセグメント長（データ長）は0，そして受信ウインドウは満タンや．したがって，『次に受信するべきシーケンス番号 <= 受信したセグメントのシーケンス番号 < 次に受信するべきシーケンス番号 + 受信ウインドウ』をテストする」

tcp「要するに，届いたシーケンス番号が過去に巻き戻っておらず，それを受け入れるだけのウインドウがあるってことやな．今回は良さそうや」

tcp「次に，ACKフラグがあるか確認するで．TCPでは初期の通信以外には常にACKをつけるはずや．よし，ちゃんと立ってるな」

tcp「最後に次の条件をテストするで．『送信したが受信を確認していない最も古いシーケンス番号 < 受信セグメントのack番号（相手が次に要求するシーケンス番号） <= 次に送信すべきシーケンス番号』」

tcp「つまり，『送信したが受信を確認していない最も古いシーケンス番号』が確認されて，かつ相手が要求するシーケンス番号がこちらの想定するそれを追い越していないってことやで」

tcp「ここまで確認したらESTABLISHEDに入れるな．コネクション確立やで！」

TCP接続の状態遷移図

tcp「このPCBを使ってる各所にctxで通知したろ」

〜〜〜

さっき一旦眠っていたtcp「はっ……！PCBの状態が変わったみたいやな．お！コネクション確立しとるやんけ．TCP OPEN完了やで〜」

Step 2: TCP RECEIVE Call

ユーザープログラム「さっきのソケットでTCP RECEIVE Callするよ」

tcp「了解やで．えーと，現状の受信ウインドウは65535，これは満タンやから受信バッファには何も入ってないな．なにか入ってくるまでctxで眠るで……」

〜〜〜

Firefox「コネクション確立したからHTTPリクエスト送るよ」

〜〜〜

tcp「おっ，セグメントが来たで」

tcp「まずはチェックサムを確認するで」

tcp「次に例のシーケンス番号確認や」

セグメントを受け入れ可能かテストする条件の表．RFC 9293のTable 6: Segment Acceptability Tests

tcp「今回はデータがあって受信ウインドウは満タンやから，以下のどちらかを満たせばええ」

  1. 次に受信すべきシーケンス番号 <= 受信セグメントのシーケンス番号 < 次に受信すべきシーケンス番号 + 受信ウインドウ
  2. 次に受信すべきシーケンス番号 <= 受信セグメントのシーケンス番号 + 受信セグメントのデータサイズ - 1 < 次に受信すべきシーケンス番号 + 受信ウインドウ

tcp「結局のところ，シーケンス番号が巻き戻っておらず，それを受信できるだけのウインドウがあるってことやな．本質的にはさっきと同じや」

tcp「次に，ACKがセットされていることを確認するで」

tcp「そして，次の条件をテストするで．『送信したが受信を確認していない最も古いシーケンス番号 < 受信セグメントのack番号（相手が次に要求しているシーケンス番号） <= 次に送信すべきシーケンス番号』」

tcp「これはさっきも出てきた条件やな．『送信したが受信を確認していない最も古いシーケンス番号』が確認されて，かつ相手が要求するシーケンス番号がこちらの想定するそれを追い越していない」

tcp「これを確認したら，snd.una（送信したが受信を確認していない最も古いシーケンス番号）を，受信セグメントのACK番号で更新するで．受信セグメントのACK番号は，言い換えれば相手が期待している次のシーケンス番号，つまりこのセグメントに対してワイらが後で送信するACK応答のシーケンス番号となるから，snd.unaの定義と一致するで」

tcp「次に，相手さんの受信ウインドウ（つまりこちらの送信ウインドウ）の更新を行うで．更新は以下どちらかが真なら行うで」

  1. 直近のウインドウ更新でのシーケンス番号 < 受信セグメントのシーケンス番号
  2. 直近のウインドウ更新でのシーケンス番号 == 受信セグメントのシーケンス番号 && 直近のウインドウ更新での確認番号 < 受信セグメントの確認番号

tcp「要は過去のセグメントでウインドウの更新を行わないための条件やな．今回は新しいセグメントやからPCBの値を次のように更新や」

  • snd.wnd（送信ウインドウ，相手の受信ウインドウ）：受信セグメントのウインドウ値
  • snd.wl1（ウインドウ更新でのシーケンス番号）：受信セグメントのシーケンス番号
  • snd.wl2（ウインドウ更新での確認番号）：受信セグメントの確認番号

tcp「ここでいったんctxで関係者を起こすで．もし相手の受信ウインドウが足りずに送信を待っている処理があれば，ここでそれが回復したかもしれんからな．伝えてあげなあかんで」

〜〜〜

さっき眠っていたtcp「はっ……！起こされた，けど受信バッファにまだ何も入っとらんやんけ．また寝るわ」

〜〜〜

tcp「そしたら，いよいよデータを受信バッファへコピーするで」

tcp「無事にデータを移したので，PCBを次のように更新するやで」

  • rcv.nxt（次に受信すべきシーケンス番号）：セグメントのシーケンス番号 + データサイズ
    • つまり，現状のデータの位置 + データサイズが，次に受け取るべきデータの位置となるわけやな
  • rcv.wnd（受信ウインドウ）：rcv.wnd（受信ウインドウ） - データサイズ
    • バッファが埋まった分，受信能力が減少したわけや

tcp「そしてACK応答するで」

tcp「最後に，ctxで関係者を起こさなアカンな．受信バッファの変化を待っている処理がおるかもしれんし」

〜〜〜

さっき眠っていたtcp「はっ……！お，今度は受信バッファになんか入っとるな．こいつをユーザープログラムの領域にコピーするで〜」

tcp「今回はリングバッファなどを実装していないから，読み込んだ領域を切り詰めてっと……」

tcp「最後に，読み出した分のデータサイズを受信ウインドウに加算するで．こうして受信能力が回復するわけやな」

Step 3: TCP SEND Call

ユーザープログラム「さっきのソケットでTCP SEND Callするよ．内容はHTTP/1.1 200 OK\r\n\r\n<html><head><title>hello</title></head><body>world</body></html>」

tcp「まずは相手さんが受信できるかどうか確認するやで．相手さんの受信能力は，『snd.wnd - (snd.nxt - snd.una)』となるんや」

tcp「相手さんの受信能力は基本的に送信ウインドウからわかるんやけど，これは『相手さんが申告してきた量』や．つまり，相手からの申告が追いついていない分は差し引いて送ってやる必要がある．例えば，こちらの送信したデータがまだネットワークの途中にある場合，それらを送信ウインドウから引いた量しか送れないってわけや．それが『(snd.nxt - snd.una)』の部分で，送信したけど受信を確認していないデータの量や」

tcp「今回の場合はデータも短いし，送信ウインドウも満タンやから即座に送信して終わりや．ここでもし送信できる量が0やったり，一部しか送信できなかったり，Ethernetのmtuで通信を分割しなければならなかったりする場合は，ctxで眠る必要がある」

〜〜〜

Firefox「うわ，雑なHTTPレスポンスきた．Content-Lengthが無いからもう少しコンテンツが続くのかな……？」

Step 4: TCP CLOSE Call

ユーザープログラム「TCP CLOSE Callで通信ブチ切るよ」

tcp「というわけでACK, FIN要求送るやで」

tcp「FINでシーケンス番号を1消費したから，snd.nxtをインクリメントするで」

tcp「状態をFIN_WAIT1に移行するやで」

TCP接続の状態遷移図

〜〜〜

Linuxのプロトコルスタック「あ，FIN要求だ．ACKを送信してCLOSE_WAITに移行するか．Firefoxさん，接続切られました」

Firefox「なるほど，コンテンツはここで終わりなのね．じゃあ画面にページを表示するか」

ぼく「ページが表示された！キャッキャ！」

Firefox「こっちも接続をCLOSEします」

Linuxのプロトコルスタック「じゃあこちらもFINを送信してLAST_ACK状態に遷移します」

〜〜〜

tcp「お，FINのACKが来たな．チェックサムやシーケンス番号の検査などはさっきと同様やから割愛するで」

tcp「受信セグメントの確認番号が，次に送信すべきシーケンス番号と一致することを確認したらFIN_WAIT2に移行できる」

tcp「おお，続けてFINが来たな」

tcp「そしたらFINに対するACKを応答するか」

tcp「最後に，TIME_WAITに移行して終了や．本来はここから時間が経つとPCBが削除されてCLOSEDになるんやけど，今回の実装では割愛や」

〜〜〜

Linuxのプロトコルスタック「さっきのFINにACKが来たのでCLOSED状態に移行して終了です」

3. プロトコルスタックの終了処理

先程は割愛しましたが，Webサーバーの終了後に以下のような終了処理を行っていました．

// プロトコルスタックを終了
net_shutdown();

特に難しいことはしていません．まず，すべてのネットワークデバイスの終了処理を実行します．ここでTAPデバイスのファイルディスクリプタもcloseされます．

最後に，intrのシグナル用スレッドを終了して終わりです．

おつかれさまでした．

おまけ：もう少し実用的なWebサーバーに改良してみた

このブログを配信できるようにしてみました．

まず，リクエストのたびにコネクションを切っていてはPCBがいくつあっても足りないので，ちゃんとContent-Lengthを返すようにしてコネクションを使いまわし，Keep-Aliveっぽい動作にしました． っぽい と言っているのには理由があって，このサーバーはTCP RECEIVE Callごとに1つのリクエストしか処理しません．セグメントをまたいだリクエストは無視する雑な実装です．

次に，ブラウザは6並列で接続してくるので，こちらも並列で受け付けるようにpthreadを使いました．

また，URLのパースも行いました．Getパラメタを削除したり，/で終わっているときにindex.htmlを補完したり，URIデコードを自前で行ったり……

文字がたくさん流れててかっこいいですね．

// URIデコード処理
size_t uri_decode(const char *src, const size_t srclen, char *dst) { /* ... */ }

void http_handler(int soc, uint8_t *reqbuf, size_t reqsize) {
  // URLをパースする
  // ファイルを開く
  // ファイルを読んでレスポンスする
  while (read(/* ... */) != 0) {
    tcp_send(/* ... */);
  }
}

// Worker
void *worker_thread(void *param) {
  // 通信が切れたら再度接続を待つ
  while (/* ... */) {
    int soc = tcp_open_rfc793(/*... */);
    // 接続が切れるまで同じソケットで通信する
    while (/* ... */) {
      http_handler(/* ... */);
    }

    tcp_close(soc);
  }

  return NULL;
}

int main(int argc, char *argv[]) {
  // プロトコルスタックを初期化

  pthread_t thread;
  // 16並列で受け付ける
  for (int i = 0; i < 16; i++) {
    pthread_create(/* ... */);
  }
  pthread_join(thread, NULL);

  // プロトコルスタックを終了

  return 0;
}

改良したWebサーバーのすべてのコード

まとめ

Webページが表示されるまでを，プロトコルスタックの観点から追いかけてみました．今回の例は，名前解決もTLSも無しという最も単純なものでしたが，それでも1つずつ追いかけていくと結構な分量になりました．

今回触れた内容はプロトコルスタックが持つ機能の一部にすぎません．例えばカスサーバーを動かした時のtcp.cのカバレッジを取ってみると

tcp.cのカバレッジレポート．約58％の機能しか実行されていない

約58％の機能しか実行されていません．

また，今回のプロトコルスタックは学習用のものなのでシンプルな方です．例えば，実装したtcp.cは約1,000行しかありませんが，Linux 6.0のnet/ipv4/tcp.cは約4,800行あり，関連ファイル全体（net/ipv4/tcp*）では 約30,700行 あります．こういうプログラムが書けるすごい人たちのおかげでインターネットを使えていると思うと，頭が上がりませんね……．

実際，プロトコルスタックを書くのはとても大変です．通信は，その一部が間違っているだけで全体がおかしくなります．そのたびにprintfデバッグしたり，Wiresharkと見つめ合ったまま休日が終わっちゃったり，プロトコルを間違って理解していることが判明し，潔くRFCを読んだりしてました．

しかし，普段隠れている仕組みがわかるというのは，それらの苦労を上回るくらいとっても楽しいものです．

最後になりますが，コンパクトな実装と丁寧な学習資料が無ければ，今回の勉強は確実に挫折していたと言えます．@pandax381さん，素晴らしい資料をありがとうございました．

ネットワーク初心者なので，プロトコルの理解や関西弁の使い方に間違いがあればマサカリをお願いします．

読んでいただきありがとうございました．

  1. 今回も無職 やめ太郎（本名）さん構文リスペクトで行きます．登場人物が多いので最適かと思いました．苦手な方にはすみません．↩

続けて読む…

Advent of Code 2021攻略ガイド

2021/12/28

SICPの備忘録

2023/07/29

JPHACKS2017雑記

2018/01/27

シングルユーザーモードのUbuntuにSSHする（SSH to Single User Mode Ubuntu 18.04）

2020/10/25

kurage - IT企業のフォロー関係を分析し、企業やエンジニアをランク付けする

2018/08/25

夏だからGatsbyのランタイム全部消す

2021/08/02

書いた人

sititou70のアイコン画像
sititou70

都内の社会人エンジニア4年生。Web技術、3DCG、映像制作が好き。