ソケットバッファとタイムスタンプ
sk_buff構造体
BSDのネットワークスタックで導入されたmbufが好きだ。ソースコードを読む醍醐味の一つが、実問題に対してどんなアルゴリズムやデータ構造を使って解こうとしているかにあるかと思っている。mbufを最初に知ったのは悪魔本だったかどうか記憶は曖昧だが、悪魔本とかStevensの詳解TCP/IP等を読んでなるほどよくできていると感心した。パケットはスタックの階層を行ったり来たりするときに、ヘッダを足したり引いたりする必要があるが、その際に無駄なメモリコピーを無くすというのが基本的なアイデアだ。mbufのアイデアはLinuxのsk_buff、WindowsのNET_BUFFERにも引き継がれている。
話は脱線する。就職して最初の仕事が、富岳のPL（当時東大）の石川裕先生のプロジェクトで、そのプロジェクトでの輪講用に「詳解TCP/IP」シリーズ（3分冊）のVol.1とVol.2を買った。Vol.2は4.4BSD-LiteのTCP/IPスタック15,000行の解説。悪魔本だけではわからない実装の中身はこれで学んだ。基本的な構造は変わらないので、今でも十分通用する知識だ。今だと何で勉強するのかな。いまどきのLinuxだとnet/ipv4以下だけでも100,000行だから10倍ぐらいの規模感になりそう。
$ cd net/ipv4
$ find . -type f -a -exec wc -l {} \; | awk '{lines+=$1}END{print lines}'
102268閑話休題。オリジナルのmbufは汎用的なデータ構造でシンプルだったが（いまのBSDの実装は知らない）、Linuxのsk_buffはプラグマティックというか、いろんな拡張を取り入れている。例えば、パケット毎のタイムスタンプってのはmbufにはない。これはRTTの推定に関係する。mbufの場合はTCPのコントロールブロックにひとつだけ（つまりソケットにひとつ）タイムスタンプがあるので、ウィンドウサイズが広がるとRTTの推定が難しくなる。Linuxは実に富豪的なアプローチでの実装。
sk_buffへのコミット数は557件と結構ある。
$ git log --oneline v3.0..v5.8.10 include/linux/skbuff.h |wc
557 3922 36106端から見ていくと切りがないので、めぼしそうなところをつまみ食いする。
commit 56b174256b6936ec4c1ed8f3407109ac6929d3ca
Author: Eric Dumazet <edumazet@google.com>
Date: Mon Nov 3 08:19:53 2014 -0800
net: add rbnode to struct sk_buff
<snip>
diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h
index 6c8b6f604e76..5ad9675b6fe1 100644
--- a/include/linux/skbuff.h
+++ b/include/linux/skbuff.h
<snip>
struct sk_buff {
- /* These two members must be first. */
- struct sk_buff *next;
- struct sk_buff *prev;
-
union {
- ktime_t tstamp;
- struct skb_mstamp skb_mstamp;
+ struct {
+ /* These two members must be first. */
+ struct sk_buff *next;
+ struct sk_buff *prev;
+
+ union {
+ ktime_t tstamp;
+ struct skb_mstamp skb_mstamp;
+ };
+ };
+ struct rb_node rbnode; /* used in netem & tcp stack */
};
-sk_buffが双方向リスト以外に赤黒木でも管理されるようになった。unionになっているが、コメントによると、netem（ネットワークエミュレータモジュール）とTCPの場合は赤黒木、それ以外は昔通りの双方向リストを使うようだ。これは再送パケットの管理に有効で、実際に下記のパッチで実装されている。TCPは信頼性を保証するために、ACKされるまで再送に備えてパケットを保持し続けなければいけない。ネットワークの帯域遅延積が大きくなると、その分リストが膨大になってしまうから、線形リストでは効率が悪い。
commit 75c119afe14f74b4dd967d75ed9f57ab6c0ef045
Author: Eric Dumazet <edumazet@google.com>
Date: Thu Oct 5 22:21:27 2017 -0700
tcp: implement rb-tree based retransmit queueTCPスタックとタイムスタンプ
続いてタイムスタンプ周りを見てみよう。Linuxカーネルでよく使われるタイムスタンプはktime_tとjiffies。ktime_tはナノ秒解像度で時間/時刻を格納するために使用される。jiffiesは1/HZごとにインクリメントされるので、システム依存の値になる（HZ=100なら10ミリ秒ごと、HZ=250なら4ミリ秒ごとにインクリメント）。
そもそも歴史的にはTCPスタックのタイムスタンプとしてはjiffiesが使われてきた。例えば、前述したRTTの推定や再送タイムアウト（RTO）の管理に使われる。最小RTOの定義はRFCでは1秒、Linux実装でも200ミリ秒なので、jiffiesで十分な解像度だった。しかし、データセンターではRTTはサブミリ秒になっているので、もっと高解像度なタイマが使いたいという要求が出てきた。例えば、GoogleがIETF97で発表した「TCP Options for Low Latency:
Maximum ACK Delay and Microsecond Timestamps」が参考になる。TCP incastと言って、複数のTCPストリームがスイッチに殺到して大量のパケットロスが起きたときに、RTO時間分通信が止まってしまう問題が知られているが、Googleでは2013年から最小RTOを5ミリ秒にして運用していたそうだ。この手の話はHPCの世界でも知られていた（「TCP/IPとMPI並列通信」 SACSIS2009チュートリアル）。
commit 363ec392352e55c61ce2799c3f15f89f9429bba7
Author: Eric Dumazet <edumazet@google.com>
Date: Wed Feb 26 14:02:11 2014 -0800
net: add skb_mstamp infrastructure
<snip>
+/**
+ * struct skb_mstamp - multi resolution time stamps
+ * @stamp_us: timestamp in us resolution
+ * @stamp_jiffies: timestamp in jiffies
+ */
+struct skb_mstamp {
+ union {
+ u64 v64;
+ struct {
+ u32 stamp_us;
+ u32 stamp_jiffies;
+ };
+ };
+};
<snip>
@@ -429,7 +481,10 @@ struct sk_buff {
struct sk_buff *next;
struct sk_buff *prev;
- ktime_t tstamp;
+ union {
+ ktime_t tstamp;
+ struct skb_mstamp skb_mstamp;
+ };このような背景から、sk_buffにskb_mstamp（マイクロ秒精度とjiffiesの２つのタイムスタンプを持つ構造体）が導入された。ktime_get()は解像度は十分だがコストが大きいので、local_clock()を使って軽量にマイクロ秒精度のタイムスタンプを得ようというものらしい。が、これは次のパッチでobsoleteになる。
commit 9a568de4818dea9a05af141046bd3e589245ab83
Author: Eric Dumazet <edumazet@google.com>
Date: Tue May 16 14:00:14 2017 -0700
tcp: switch TCP TS option (RFC 7323) to 1ms clock
<snip>
@@ -646,7 +586,7 @@ struct sk_buff {
union {
ktime_t tstamp;
- struct skb_mstamp skb_mstamp;
+ u64 skb_mstamp;
};
};
struct rb_node rbnode; /* used in netem & tcp stack */そもそもjiffiesなんて使わずにマイクロ秒精度のタイムスタンプで統一しようということだろう。
commit d3edd06ea8ea9e03de6567fda80b8be57e21a537
Author: Eric Dumazet <edumazet@google.com>
Date: Fri Sep 21 08:51:50 2018 -0700
tcp: provide earliest departure time in skb->tstamp
<snip>
@@ -689,7 +689,7 @@ struct sk_buff {
union {
ktime_t tstamp;
- u64 skb_mstamp;
+ u64 skb_mstamp_ns; /* earliest departure time */
};さらにskb_mstampの精度がマイクロ秒からナノ秒になっている。この辺の経緯はEarliest Departure Time (Early?)に関係していて、Van Jacobsonの「Evolving from AFAP: Teaching NICs about time」やDavid Wetherall の「From Queues To Earliest Departure Time Model」が参考になる。ネットワークが遅かった頃はパケットは可能な限り速やかに送出する（ASAP）のが鉄則だった。しかし、帯域遅延積の大きなロングファットパイプや、高速インターコネクションでつながったデータセンターになると、ルータのバッファがすぐにあふれてしまう。これを回避するために、例えばCWND * MSS / RTTにしたがってパケット間隔を広げることで、ネットワークに優しい送信を行うというパケットペーシングという手法が従来より研究されてきた。LinuxカーネルではFQ/pacingとかBBRで実装されている。これをもっと汎用な仕組みで実装しようというのがEarliest Departure Timeモデルだ。10Gbpsとか100Gbpsで送信タイミングを制御するにはナノ秒精度のタイマーが必要だということだ。個人的にはすごく既視感があるのだけど、こんなことになっていたのね。
EDTについては、日を改めて書きたい（→Earliest Departure Timeモデル）。
この記事が気に入ったらサポートをしてみませんか？