「Linuxカーネル2.6解読室」（以降、旧版）出版後、Linuxには多くの機能が追加され、エンタープライズ領域をはじめとする様々な場所で使われるようになりました。 それに伴いコードが肥大かつ複雑化し、多くのエンジニアにとって解読不能なブラックボックスとなっています。 世界中のトップエンジニア達の傑作であるLinuxカーネルにメスを入れ、ブラックボックスをこじ開けて、時に好奇心の赴くままにカーネルの世界を解読する「新Linuxカーネル解読室」プロジェクト。
本稿では、ネットワーク機能のIPレイヤーの受信処理ついてカーネルv6.8のコードをベースに解説します。
執筆者 : 須田 哲志、稲葉 貴昭
※ 「新Linuxカーネル解読室」連載記事一覧はこちら
はじめに
前回まではEthernetドライバにおけるパケットの受信処理を解説しました。 今回は、続きとなるIPレイヤーの処理について解説していきたいと思います。 まずは、これまで通りパケットの受信処理全体を概観してみましょう。
これまで、図中の⑥、すなわち「L3(IP) Processing」に入るところまでを解説しました。
*1
今回は⑥〜⑦、すなわち「L3(IP) Processing」について解説していきます。
図中の処理番号に併記されているとおり、ip_list_rcvからudp_rcvを呼び出すところまでが解説範囲となります。
1. 概要
パケットの受信処理において、IPレイヤーは一体どんな仕事をしているんでしょうか。 ざっくり表現してしまうと、「受信パケットの宛先(IPアドレス)を判別し、自ホスト宛であれば受信し、他ホスト宛であれば転送する」という処理を行っています。 *2 いわゆる、「ルーティング」と呼ばれる処理です。
図1-1に示すとおり、受信処理の場合はip_local_deliverを、転送処理の場合にはip_forwardをそれぞれ呼び出します。*3
今回の記事では、この分岐処理の実装や処理の効率化を中心に解説し、この図1-1の解像度を上げていきたいと思います。
なお、パケットの受信処理の解説ですので、パケットの転送処理(ip_forward)に関する解説は割愛します。
2. ルーティング処理
本章では、前述したパケットの受信/転送処理の分岐が、どのように実装されているかについて見ていきます。
2.1 dst_entry構造体とルーティング処理
まずは、パケットの受信/転送処理の分岐部分の実装について見ていきましょう。
この分岐処理はdst_input関数で行っています。
分岐処理ということで、if文で受信/転送処理の分岐を行うことが想像できそうですが、そうではありません。
これを実現しているのはコールバック関数です。
(処理の分岐がコールバック関数で実現されているのはLinuxカーネルあるあるですね。)
dst_input関数は、sk_buff構造体が参照するdst_entry構造体のinputコールバック関数を実行しているだけです。
(dst_entry構造体が何者かについては次節で解説します。)
これはつまり、宛先に応じたdst_entry構造体が取得できれば、受信パケットが自ホスト宛かどうか判別せずとも、dst_input関数を呼び出すだけで受信/転送処理を実行できるということになります。
*4
すなわち、実装の観点において「受信パケットの宛先に応じたdst_entry構造体を取得する」ことがルーティング処理の要と言えます。
それでは、このdst_entry構造体はどのように取得しているんでしょうか。そもそもdst_entry構造体とは一体何者なんでしょうか。
次節ではこの部分を追究していきます。
2.2 ルーティングテーブル(FIB: Forwarding Information Base)の検索処理
前節でdst_entry構造体のinputコールバック関数が受信パケットの受信/転送処理の実体であること、そしてdst_input関数がこれを実行していることを説明しました。
つまり、dst_input関数を呼び出す前に、受信パケットの宛先に応じたdst_entry構造体を取得する処理があるはずです。(図2-3参照)
このdst_entry構造体の取得は、以下の図2-4に示すとおり、ip_route_input_noref関数で行っています。
ip_route_input_noref関数では、ルーティングテーブル(FIB: Forwarding Information Base)から受信パケットの宛先(IPアドレス)と一致するエントリーを検索します。
*5
*6
このルーティングテーブルの検索結果は、最終的にルーティングキャッシュとしてrtable構造体に格納されます。
dst_entry構造体は、このrtable構造体の先頭メンバ変数であり、宛先に関する情報を集約しています。
すなわち、dst_entry構造体はルーティングキャッシュの宛先情報と言えます。
そして、ip_route_input_noref関数では、このdst_entry構造体へのポインタをsk_buff構造体の_skb_refdstに格納します。
*7
*8
*9
これで、宛先に対応したdst_entry構造体を取得することができました。
あとは、前節で解説したdst_input関数を呼び出せば、パケットの受信(もしくは転送)処理が実行されるというわけです。
3. dst_entry構造体取得の効率化
前章ではルーティングテーブルを検索して、受信パケットの宛先に応じたdst_entry構造体を取得する流れを解説しました。 ここで、前回の記事からの流れ、すなわちEthernetドライバから今回のIPレイヤーでのルーティング処理までの流れを俯瞰してみましょう。
前回のEthernetドライバの解説では、複数の受信パケット(sk_buff構造体)をリスト(サブリスト)にして、IPレイヤーに渡していることを解説しました。 すなわち、IPレイヤーにはリスト状に連なった複数の受信パケットが渡されている状態になります。 このとき、1パケットずつ、ルーティングテーブルを検索していると処理時間が長くなってしまうことが懸念されます。 そこで、Linuxカーネルでは、なるべくルーティングテーブルを検索しなくて済むよう、以下の効率化を行っています。
- 宛先が同一のパケット情報の参照
- UDP Tableの参照
本章では、これらの効率化処理について解説します。
3.1 効率化処理1: 宛先が同一のパケット情報の参照
さきほど、「IPレイヤーにはリスト状に連なった複数の受信パケットが渡されている」ことを説明しました。 本節で解説する効率化処理は、この「受信パケットをリストとして処理する」ことを利用しています。
sk_buff構造体が保持するのは、dst_entry構造体へのポインタであり、これはルーティングキャッシュの一部です。 つまり、複数のsk_buff構造体について、これらの宛先が同じであれば、同一のdst_entry構造体を参照するはずです。 そこでLinuxカーネルでは、サブリストの最初の1パケット目は、ルーティングテーブルを検索し、dst_entry構造体のポインタを取得します。 そして、サブリストの2パケット目以降は、宛先が同一である限り、1パケット目のdst_entry構造体へのポインタをコピーします。 *10
この効率化では、dst_entry構造体のポインタをコピーするだけのため、ルーティングテーブルの検索に比べて処理コストを大幅に下げることができます。 Ethernetドライバで受信パケットをリスト(サブリスト)にしてからIPレイヤーに渡していたのは、この効率化処理への伏線でもあったと言えます。
3.2 効率化処理2: UDP Tableの参照
前節では、サブリストの1パケット目のdst_entry構造体へのポインタを、後続のパケットにコピーするという効率化を解説しました。 このとき、サブリストの1パケット目は前章で解説したとおり、ルーティングテーブルの検索により、dst_entry構造体を取得しています。 本節で解説する効率化処理は、このサブリストの1パケット目の処理に関するものです。
3.2.1 効率化処理が機能するユースケース
本効率化処理は常に有効というわけではなく、特定の条件を満たしているときにのみ動作します。
その条件とは、受信側アプリケーションがconnect(2)を用いて、特定の送信元アドレスをソケットに紐付けていることです。
(※なお、別途カーネルパラメータを設定する必要はありますが、これについては後述します。)
ただし、connect(2)を使用したUDPソケットは、指定した送信元以外からのパケットが受信できなくなるという点に注意が必要です。
つまり、本効率化処理は1対1の固定的な通信が前提となります。
一方で、1対1の通信であれば、recvfrom(2)で取得した送信元アドレスを用いてconnect(2)を発行することで、本節で解説する効率化処理を機能させることができます。
それでは、効率化処理の内容を見ていきましょう。
3.2.2 UDP Tableの登場
Linuxカーネルでは、ルーティングテーブルを検索する前に、UDP Tableというテーブルの検索を試みます。 (ただし、受信パケットがUDPであるという前提ですが。そもそも上位(L4)プロトコルをどのように特定/判定しているかについては4.1節で解説します。) そして、UDP Tableの検索が成功した場合は、その検索結果からdst_entry構造体を取得します。 つまり、UDP Tableでの検索に失敗した場合にのみ、前章で解説したルーティングテーブルの検索処理を実行するという流れになります。
それではなぜ、UDP Tableを検索することが効率化になるのでしょうか。 そもそもUDP Tableとは一体何なのでしょうか。
3.2.3 UDP Early Demultiplexer: UDP Tableによるソケットの取得
UDP TableはUDPソケットを検索するためのハッシュテーブルです。
アプリケーションがbind(2)システムコールを発行すると、UDPソケットがこのUDP Tableに登録されます。
UDP Tableを参照することで、宛先IPアドレスやポート番号から配送先のUDPソケットを取得できます。
このとき、UDPソケット(sock構造体)はdst_entry構造体へのポインタを保持しており、本効率化処理ではこれを利用しています。
このUDP Tableの参照によるUDPソケットの取得は本来、UDPレイヤーで行う処理です。
そのため、IPレイヤーでUDPレイヤーの処理を先取りする、この処理(機能)はUDP Early Demultiplexerと呼ばれます。
*11
(このUDP Early Demutiplexerはカーネルパラメータとなっており、net.ipv4.udp_early_demuxで有効/無効が設定できます。)
*12
*13
要するに、本来、UDPレイヤーで行うUDPソケットの取得をIPレイヤーで先行して行うついでに、dst_entry構造体も取得しているということになります。
その他、UDP Tableの詳細やUDPソケットの取得に関しては、次回の「UDPレイヤーにおける受信処理」で解説したいと思います。
最後にUDP Early Demultiplexerのメリットと懸念点について簡単に説明します。
まず、メリットとして以下の点が考えられます。
- ルーティングテーブル(FIB)に比べてエントリー数が小さい
→ ルーティングテーブルの検索に比べて処理コストが小さくなることが期待できる。 - UDPソケットが取得できた場合、UDPレイヤーでの処理が一部省略できる
一方、以下の状況では、UDP Tableでの検索が空振りし、UDP Early Demultiplexer自体がただのオーバヘッドになってしまう懸念があります。
- サーバーが起動していない等でUDP TableにUDPソケットが登録されていない
もしくは、UDP TableにUDPソケット自体は登録されているが、connect(2)が実行されておらず、UDP Early Demultiplexerによる検索にヒットしない - 受信処理よりも転送処理のワークロードの方が高い場合
3.3 効率化処理まとめ
ここまでdst_entry構造体を取得する2つの効率化処理を説明してきました。 これらの処理をまとめると、以下のようにdst_entry構造体を取得していると言えます。 (ソースコードレベルの実装では、処理/判定順序は多少異なります。)
- サブリストの1パケット目は、UDP Early Demultiplexer(UDP Tableの参照)によるdst_entry構造体の取得を試みる
- UDP Early Demultiplexerによる取得が失敗した場合、ルーティングテーブルからdst_entry構造体を取得する
- サブリストの2パケット目以降は、1パケット目が保持する情報からdst_entry構造体を取得する
これらを図示すると図3-5のように表せます。
4. ip_local_deliver以降の処理について
ここまで、ルーティング処理における受信/転送処理の分岐について詳しく見てきました。
本記事の最後では、受信処理に分岐したあと、すなわちip_local_deliver関数からudp_rcv関数までの流れを見ていきたいと思います。
まずは、関数コールの流れを見てみましょう。
ip_local_deliver関数からudp_rcv関数までの流れは以下のように比較的シンプルです。
ip_local_deliver
└── ip_local_deliver_finish
└── ip_protocol_deliver_rcu // 本章で解説
└── udp_rcv
この中で重要なのがip_protocol_deliver_rcu関数です。
ここでは、UDP/TCPの処理への分岐やRAWソケットへの配送を行っています。
それでは、上位(L4)プロトコルの特定や、プロトコル毎の処理への分岐はどのように実装しているのでしょうか。
次節からはこれらについて解説していきます。
4.1 上位(L4)プロトコルの特定: IPヘッダとiphdr構造体
IPヘッダには、上位(L4)プロトコルを示す「Protocol」フィールドが存在します。 つまり、上位プロトコルを特定するには、この「Protocol」フィールドを見れば良いということになります。
ところで、前回のEthernetドライバの解説でも、「L3プロトコルをどのように特定するのか」という、同じような話がありました。
Ethernetドライバでは、Ethernetヘッダの「EtherType」フィールドからL3プロトコルを特定し、結果をsk_buff構造体の.protocolに記録していることを解説しました。
では、L4プロトコルに関しては、sk_buff構造体のどの変数を参照すれば良いのでしょうか。 実はsk_buff構造体には、L4プロトコルを直接示す変数はありません。 L4プロトコルを含むIPヘッダの各情報を取得するためにはiphdr構造体を介す必要があります。
このとき、sk_buff構造体の以下の2つのメンバ変数を利用します。
.head
受信パケットの格納領域の先頭アドレス(ポインタ)を指し示すポインタ変数.network_header
受信パケットの格納領域における、IPヘッダまでのオフセットを示す変数
※このとき、図4-1に示すとおり、Paddingにより「IPヘッダまでのオフセット = Ethernetヘッダサイズ」とは限りません。 *14 *15
図4-1に示すとおり、これら2つのメンバ変数を足し合わせることで、IPヘッダへのアドレス(ポインタ)を得ることができます。
*16
そして、このIPヘッダへのアドレスをiphdr構造体にキャスト(型変換)してアクセスすることで、L4プロトコル(.protocol)含むIPヘッダの各種情報にアクセスできるようになります。
(sk_buff構造体にも.protocolが存在するため紛らわしいですね。)
4.2 上位(L4)プロトコルハンドラの特定: net_protocol構造体とinet_protos配列
前節では、iphdr構造体を介して、上位(L4)プロトコルを特定できることを解説しました。
それでは各上位(L4)プロトコルに対応したハンドラ(udp_rcvやtcp_v4_rcv等)はどのように特定しているのでしょうか。
そこで登場するのがnet_protocol構造体とinet_protos配列です。 net_protocol構造体はL4プロトコルのハンドラを保持している構造体です。 すなわち、上位(L4)プロトコルに対応したnet_protocol構造体を特定できれば適切な上位ハンドラを呼び出せるということになります。
そして、このnet_protocol構造体を管理しているのがinet_protos配列です。 inet_protos配列は、図4-2に示すとおり、net_protocol構造体へのポインタの配列となっています。
inet_protos配列では、図4-2に示すとおり、対応するnet_protocol構造体のインデックスと IPヘッダの「Protocol」フィールドのプロトコル番号が対応しています。 すなわち、IPヘッダの「Protocol」フィールドの値を、そのままインデックスとしてinet_protos配列にアクセスすれば、プロトコルに対応したnet_protocol構造体が取得できます。
このように、IPヘッダの「Protocol」フィールドからnet_protocol構造体を特定できるようにすることで、上位(L4)プロトコルに対応したハンドラが取得できます。
最後に、ここまで解説したIPレイヤーの処理を概観してみたいと思います。
本章では主に上位(L4)プロトコルハンドラの分岐処理を解説してきましたが、ip_protocol_deliver_rcu関数では、他にRAWソケット*17への配送も行っています。
これを考慮すると、IPレイヤーの処理は図4-3のように表現できるでしょう。
5. 次回予告
次回はudp_rcv関数から、実際にパケットをソケットに配送するところまでを解説していきます。
*1:前回まで掲載していたブロック図と多少変更があります。前回まではEthernetドライバに着目していたため、「L3(IP) Processing」と「L4(UDP) Processing」を1つのブロックとして表現していましたが、これらを別々のブロックにしました。そのため、処理番号も1つ増えています。(①〜⑧が①〜⑨に増えています。また、処理⑥以降は処理番号に加えて、矢印の先のブロック処理へのエントリー関数を併記しています。)
*2:厳密には受信処理(ip_local_deliver)、転送処理(ip_forward)だけでなくエラー処理(ip_error)や破棄処理(dst_discard)などへのディスパッチも行っています。
*3:本記事全般に言えますが、図中で示される関数の呼び出し関係は主要な関数のみを取り上げており、途中の関数は省略することがあります。
*4:宛先が自ホスト宛かどうか判定する処理が存在しないわけではありません。この判定は結局、dst_entry構造体の生成処理で行うことになります。
*5:実際にルーティングテーブルからエントリーを検索しているのは、ip_route_input_noref関数の延長で呼び出す、fib_lookup関数になります。
*6:図2-4ではFIBをテーブルとして表現していますが、Linuxカーネル v6.8ではLC-trie(Level Compressed trie)という木構造で実装、管理しています。なお、旧版ではハッシュテーブルで実装されていました。
*7:実際に_skb_refdstにdst_entry構造体のポインタをセットしているのは、ip_route_input_noref関数の延長で呼び出す、ip_route_input_slow関数になります。
*8:_skb_refdstはdst_entry構造体へのポインタを格納していますが、変数の型はlong型となっています。これは、最下位ビットをフラグとして使っているため、厳密にはポインタ型変数ではないからです。そのため、_skb_refdstに格納している値をポインタとして参照する場合には、最下位ビットをマスクする関数(skb_dst関数)を適用する必要があります。なお、このフラグとしての利用は、メモリアライメントにより最下位ビットが常に0となる性質を利用していると思われます。
*9:dst_entry構造体はrtable構造体の先頭メンバ変数であることから、ポインタ値としては同一になります。そのため_skb_refdstをrtable構造体へのポインタとして扱う場面も存在します。
*10:宛先が同一であるかの判定はip_can_use_hint関数で行われます。ここでは、宛先IPアドレスの他にToSフィールドについても同一であるかチェックします。
*11:TCPについてもTCP Early Demultiplexerとして同様の機能が存在します。
*12:ただし、前提としてIP Early Demultiplexer(net.ipv4.ip_early_demux)が有効になっている必要があります。
*13:TCPについても同様にカーネルパラメータとなっており、net.ipv4.tcp_early_demuxで有効/無効が設定できます。
*14:このPaddingは、パケットが処理される過程で、ヘッダが追加された場合でも新たにメモリ領域を確保しないで済むように設けられていると考えられます。
*15:筆者の検証環境では、Paddingは64Byteありました。これは、受信パケットの書き込み位置をL1キャッシュのアライメント境界に合わせるためと考えられます。
*16:旧版では、IPヘッダへのポインタを指し示す.nhというメンバ変数がsk_buff構造体に存在している旨の記載がありますが、現在のv6.8では当該変数は存在しません。
*17:これはsocket(AF_INET, SOCK_RAW, IPPROTO_TCP)のようにL4レイヤーに対して作成されたRAWソケットを指しています。
