Kernel/VM Advent Calendar 4日目: Linuxのネットワークスタックのスケーラビリティについて

【お願い】私はLinuxカーネルもネットワーク周りも素人です。ここに書いてある事は間違えている可能性もあるのでおかしいなと思ったらすかさず突っ込んでください。宜しくお願い致します。

今回は、この記事の内容を全面的に見直して、再度Linuxのネットワークスタックのスケーラビリティについてまとめようと思います。

従来のLinuxネットワークスタック+従来のシングルキューNIC

以下の図は従来のLinuxネットワークスタック+従来のシングルキューNICで、あるプロセス宛のパケットを受信している時の処理の流れを表している。フォワーディングの場合やプロトコルスタック内の処理は割愛した。


プロセスがシステムコールを発行してからスリープするまで

プロセスは、システムコールを通してカーネルにパケットを取りに行く。
パケットはソケット毎のバッファに貯まるようになっているが、バッファが空だったらプロセスはパケットを待つためにfinish_waitでスリープする。
このプロセスはどのCPUで動いていても良く、NICからハードウェア割り込みを受けるCPUと違うCPUかもしれない。

パケットの受信処理

連続して多数のパケットが届いた場合、最初の一個が届いた時点でNICからハードウェア割り込みがかかり、napi_scheduleを通してソフト割り込み(NET_RX_SOFTIRQ)がスケジュールされる。
割り込みがかかるCPUはirq_balanceで時折変更される場合があるが、特定の1CPUである。このソフト割り込みは割り込みコンテキストを抜ける手前で実行される。
このソフト割り込みは必ずハードウェア割り込みがかかったCPUと同じCPUで実行される。
ソフト割り込みではnet_rx_action関数が呼ばれ、ドライバのポーリングルーチンを叩いてパケットを取りに行く。
これは、パケットが無くなるまで、或いは一定時間を経過する or 一定数のパケットを取得するまで繰り返し実行される。
ループで繰り返し処理されるパスを赤矢印で示す。
毎ループで行っている処理は以下のようなものだ:
一つパケットを一つバッファから取り出す

netif_receive_skb経由でip_rcvを呼び、IP層の処理を行う

udp_rcvかtcp_v4_tcpを呼び、UDPTCP層の処理を行う

ソケット毎に用意されたバッファにデータをキューしていき、プロセスが受け入れ可能なデータが揃ったらsk->data_readyを呼んでプロセスの起床をスケジュールする

プロセスの起床

ソフト割り込みが実行されていたCPUがプロセスが実行されているCPUと同じなら、ソフト割り込みを抜けると、スケジューラが呼ばれて起こされたプロセスへスイッチする。
プロセスが異なるCPUで実行されているならば、そのCPUで次にスケジューラが呼ばれたタイミングでプロセスが起こされる(※要確認。IPIでたたき起こしたりしてる?それともタイムスライス終了まで待つ?)

問題点

ハードウェア割り込みを受けているCPUでのみネットワークスタックが走るので、通信量が増えるとこのCPUの使用率が100%になり、通信が詰まる。
また、このCPUに割り当てられているプロセスが殆ど走れなくなってこちらの応答速度も下がる。
プロセッサ数を増やしても解決しない。
参考記事:
The S100Kps problem(ソフト割り込み毎秒10万回問題) - sdyuki-devel
アプリケーションがマルチスレッドでもマルチコアCPUを活かせない件 - blog.nomadscafe.jp

また、ハードウェア割り込みを受けているCPUとプロセスが走っているCPUが異なる場合、CPUを跨いで同じデータを扱わなくてはならずキャッシュ効率が悪い。

Receive Side Scaling(RSS) - ハードウェアによる問題の解決

上述の諸問題をハードウェアを改良する事によって解決しようとしているのがReceive Side Scalingである。
Receive Side Scaling(RSS)は一つのポートに対する受信キューが複数あるマルチキューNICである事を前提とし、パケットのプロトコル番号・送信元IP・送信先IP・ポート番号などから作ったハッシュ値と割り込み先CPU番号の対応を記録する連想記憶をNIC側に持つ。
NICはパケットが届くとハッシュ値を生成し、これを用いて連想記憶からCPU番号を引き、対応するバッファにパケットをキューし、そのCPUに対して割り込みをかける。
パケットに対応するエントリが無い場合はデフォルトのキューにパケットを入れてランダムなCPUに割り込みをかける。この際、ネットワークスタックから連想記憶にハッシュ値とCPU番号の対応を記録する事により、次に同じ種類のパケットが届いたら正しい割り込み先に届けられるようになる。
参考資料:
Intel Ethernet Drivers and Utilities - Browse /8257x Developer Manual/Revision 1.8 at SourceForge.net

以下に手順を図で示す。

1

  • パケットが届き、NICが連想記憶をハッシュ値で引くがエントリがないのでデフォルトのバッファへキュー、デフォルトのCPUへ割り込み
  • ネットワークスタックから連想記憶にハッシュ値とCPU番号を記録
  • 他のCPUにある宛先プロセスを起床
2

  • 先ほどと同じパケットが届き、今度は連想記憶を引くとエントリがあるのでCPU2が宛先だと分かる CPU2のバッファへキュー、CPU2へ割り込み
  • 今度は宛先プロセスのあるCPUでパケットを処理出来る
3

  • 別のプロセス宛のパケットが届く。連想記憶にエントリが無いので1と同じくデフォルトキューへ入れ、デフォルトCPUへ割り込んで処理する
  • このパケットのエントリも作成

4


二つのパケットのエントリを連想記憶に持つので、正しいプロセッサに割り込む事が出来ている。
CPU2でプロセスA宛のパケットを処理中でもCPU3へ割り込んでプロセスB宛のパケットを処理する事が出来る。

RPS/RFS - ソフトウェアによる問題の解決

カーネルがReceive Side Scalingに似た振る舞いをする事により、シングルキューNICでも受信処理をスケールさせるようにする機能であるRPS/RFSがGoogleの中の人によって実装され、2.6.35にマージされた。
参考記事:
Linuxカーネル2.6.35リリース、ネットワーク負荷軽減機構やH.264ハードウェアデコードなどをサポート | OSDN Magazine
Software receive packet steering [LWN.net]
rfs: Receive Flow Steering [LWN.net]

RPSは連想記憶と複数のキューを持って任意のCPUにパケットを送る機能をカーネルに実装したもの、RFSは宛先プロセスを割り出しパケットのハッシュ値とCPU番号を連想記憶に書きこむ機能をカーネルに実装したものである。

パケット学習済みな時の動作


パケット学習済みの場合は、netif_receive_skbから呼び出されたget_rps_cpuがハッシュテーブルを引いた結果得た宛先CPUのbacklogへパケットをキューイングする。
宛先CPUで既にソフト割り込みによるパケット処理が行われている場合はキューイングして終わりだが、行われていない時はプロセッサ間割り込みを送って宛先CPUでソフト割り込みを開始させる。
従来の方式ではソフト割り込みの中でネットワークスタックの重たい処理をパケット毎に行っていたが、これを宛先CPUで行わせるようになった為、割り込まれたCPUに負荷が集中する問題が解消された。
また、パケット処理はプロセスを起こすCPUで行うようになり、割り込まれたCPUではパケットを触らなくてよくなったのでキャッシュ効率も改善していると予想される。

パケット学習済みでない時の動作


パケットが学習済みでない場合は、ランダムにCPUを選んでともかくbacklogへパケットをキューイングしてしまう。
この為、もしパケットがキューイングされたCPU宛でない場合は、プロセスは第三のCPUに居る可能性があり効率が悪いようにも思えるが、ともかく割り込まれたCPUに負荷が集中する事態は避けられる。
ネットワークスタックの中で、パケットのハッシュ値を計算し宛先CPUをソケットから特定しハッシュテーブルに書きこむ。
これによって次からは正しいCPUに届ける事が出来る。

やってみた

ここまで読んでいて薄々気づいている方も多いとは思うが、以上は前振りである。
いきなり「やってみた」では訳がわからないと思って説明を書いたら長くなりすぎて死んだ。
上述のような事を知ったら、取り敢えずReceive Side Scalingを試してみたくなるのは人として当然の事だと言うのは御理解頂けると思う。
で、試してみた。

Receive Side Scaling対応デバイス

今の所、GbEでReceive Side Scaling対応と謳っておりデータシートなども確認出来たNICは以下のとおり:

BCM5708Cを試す

BroadcomのデータシートにはBCM5708Cの所にこう書いてある:

これを信用して1枚ゲットして刺してみた。
で、こんなキワモノな接続方法でLenovo Thinkpad X200ExpressCardスロットに刺してみた:
PCから抜いた図。
BCM5708が届いたのでPE3に刺して起動してみた。

Linuxを起動すると、カーネルメッセージに以下のとおり出力されていた:

[   14.516579] bnx2: Broadcom NetXtreme II Gigabit Ethernet Driver bnx2 v2.0.9 (April 27, 2010)
[   14.516605] bnx2 0000:06:00.0: PCI INT A -> GSI 19 (level, low) -> IRQ 19
[   14.517060] bnx2 0000:06:00.0: firmware: requesting bnx2/bnx2-mips-06-5.0.0.j6.fw
[   14.555567] bnx2 0000:06:00.0: firmware: requesting bnx2/bnx2-rv2p-06-5.0.0.j3.fw
[   14.580989] bnx2 0000:06:00.0: eth1: Broadcom NetXtreme II BCM5708 1000Base-T (B2) PCI-X 64-bit 133MHz found at mem f0000000, IRQ 19, node addr 00:10:18:25:62:08
[   15.922075] bnx2 0000:06:00.0: irq 30 for MSI/MSI-X
[   16.012401] bnx2 0000:06:00.0: eth1: using MSI
[   17.691141] bnx2 0000:06:00.0: eth1: NIC Copper Link is Up, 100 Mbps full duplex, receive & transmit flow control ON

…ん?割り込みが1個しかない…それじゃ複数CPUに割り込めなくね?
というか、マルチキューってMSI-X前提じゃなかったっけ…

一瞬キワモノな接続方法やノートPCのチップセットとかが悪いんだと思ったんだけど、よくみるとなんかPCI-Xとか出てるのは何故??
で、lspciしてみたらこんなのが。

05:00.0 PCI bridge: Broadcom EPB PCI-Express to PCI-X Bridge (rev c3)
06:00.0 Ethernet controller: Broadcom Corporation NetXtreme II BCM5708 Gigabit Ethernet (rev 12)

あれ?これってボード上のPCI-Xブリッジ経由経由してコントローラ繋がってる?
もしかして、それがMSI-X使えない原因?(良く分かってないけど…

さて、ソースコードを追ってみる。

7995        if (CHIP_NUM(bp) == CHIP_NUM_5709 && CHIP_REV(bp) != CHIP_REV_Ax) {
7996                if (pci_find_capability(pdev, PCI_CAP_ID_MSIX))
7997                        bp->flags |= BNX2_FLAG_MSIX_CAP;
7998        }

「チップがBCM5709だったらPCIMSI-X対応か確かめbp->flagsにBNX2_FLAG_MSIX_CAPビットを立てる」
この時点でもう悪い予感しかしない。ちなみにCHIP_NUM_6708っていうifは無い。

6207        int cpus = num_online_cpus();
6208        int msix_vecs = min(cpus + 1, RX_MAX_RINGS);
6209
6210        bp->irq_tbl[0].handler = bnx2_interrupt;
6211        strcpy(bp->irq_tbl[0].name, bp->dev->name);
6212        bp->irq_nvecs = 1;
6213        bp->irq_tbl[0].vector = bp->pdev->irq;
6214
6215        if ((bp->flags & BNX2_FLAG_MSIX_CAP) && !dis_msi)
6216                bnx2_enable_msix(bp, msix_vecs);

bp->irq_nvecs = 1で、BNX2_FLAG_MSIX_CAPがbp->flagsに立ってる時だけbnx2_enable_msixを呼ぶ。
すんごい嫌な予感しかしない。

6153static void
6154bnx2_enable_msix(struct bnx2 *bp, int msix_vecs)
6155{
6156        int i, total_vecs, rc;
6157        struct msix_entry msix_ent[BNX2_MAX_MSIX_VEC];
6158        struct net_device *dev = bp->dev;
6159        const int len = sizeof(bp->irq_tbl[0].name);
6160
6161        bnx2_setup_msix_tbl(bp);
6162        REG_WR(bp, BNX2_PCI_MSIX_CONTROL, BNX2_MAX_MSIX_HW_VEC - 1);
6163        REG_WR(bp, BNX2_PCI_MSIX_TBL_OFF_BIR, BNX2_PCI_GRC_WINDOW2_BASE);
6164        REG_WR(bp, BNX2_PCI_MSIX_PBA_OFF_BIT, BNX2_PCI_GRC_WINDOW3_BASE);
6165
6166        /*  Need to flush the previous three writes to ensure MSI-X
6167         *  is setup properly */
6168        REG_RD(bp, BNX2_PCI_MSIX_CONTROL);
6169
6170        for (i = 0; i < BNX2_MAX_MSIX_VEC; i++) {
6171                msix_ent[i].entry = i;
6172                msix_ent[i].vector = 0;
6173        }
6174
6175        total_vecs = msix_vecs;
6176#ifdef BCM_CNIC
6177        total_vecs++;
6178#endif
6179        rc = -ENOSPC;
6180        while (total_vecs >= BNX2_MIN_MSIX_VEC) {
6181                rc = pci_enable_msix(bp->pdev, msix_ent, total_vecs);
6182                if (rc <= 0)
6183                        break;
6184                if (rc > 0)
6185                        total_vecs = rc;
6186        }
6187
6188        if (rc != 0)
6189                return;
6190
6191        msix_vecs = total_vecs;
6192#ifdef BCM_CNIC
6193        msix_vecs--;
6194#endif
6195        bp->irq_nvecs = msix_vecs;
6196        bp->flags |= BNX2_FLAG_USING_MSIX | BNX2_FLAG_ONE_SHOT_MSI;
6197        for (i = 0; i < total_vecs; i++) {
6198                bp->irq_tbl[i].vector = msix_ent[i].vector;
6199                snprintf(bp->irq_tbl[i].name, len, "%s-%d", dev->name, i);
6200                bp->irq_tbl[i].handler = bnx2_msi_1shot;
6201        }
6202}

あ〜…なんかpci_enable_msix()が呼ばれてbp->irq_nvecs = msix_vecsになって、割り込み数分bp->irq_tbl[i]が初期化されてるね…

で、これが呼ばれないとbp->irq_nvecs = 1でbp->irq_tbl[0]だけ初期化されて終わるようになっている…。

6218        if ((bp->flags & BNX2_FLAG_MSI_CAP) && !dis_msi &&
6219            !(bp->flags & BNX2_FLAG_USING_MSIX)) {
6220                if (pci_enable_msi(bp->pdev) == 0) {
6221                        bp->flags |= BNX2_FLAG_USING_MSI;
6222                        if (CHIP_NUM(bp) == CHIP_NUM_5709) {
6223                                bp->flags |= BNX2_FLAG_ONE_SHOT_MSI;
6224                                bp->irq_tbl[0].handler = bnx2_msi_1shot;
6225                        } else
6226                                bp->irq_tbl[0].handler = bnx2_msi;
6227
6228                        bp->irq_tbl[0].vector = bp->pdev->irq;
6229                }
6230        }
6232        bp->num_tx_rings = rounddown_pow_of_two(bp->irq_nvecs);
6233        bp->dev->real_num_tx_queues = bp->num_tx_rings;
6234
6235        bp->num_rx_rings = bp->irq_nvecs;

Number of TX/RX Rings == 1。
はい。(´・ω・`)

更に追っていくと、bp->num_rx_rings > 1の時だけRSSテーブルを初期化するコードとか出てくる。

5243        if (bp->num_rx_rings > 1) {
5244                u32 tbl_32;
5245                u8 *tbl = (u8 *) &tbl_32;
5246
5247                bnx2_reg_wr_ind(bp, BNX2_RXP_SCRATCH_RSS_TBL_SZ,
5248                                BNX2_RXP_SCRATCH_RSS_TBL_MAX_ENTRIES);
5249
5250                for (i = 0; i < BNX2_RXP_SCRATCH_RSS_TBL_MAX_ENTRIES; i++) {
5251                        tbl[i % 4] = i % (bp->num_rx_rings - 1);
5252                        if ((i % 4) == 3)
5253                                bnx2_reg_wr_ind(bp,
5254                                                BNX2_RXP_SCRATCH_RSS_TBL + i,
5255                                                cpu_to_be32(tbl_32));
5256                }
5257
5258                val = BNX2_RLUP_RSS_CONFIG_IPV4_RSS_TYPE_ALL_XI |
5259                      BNX2_RLUP_RSS_CONFIG_IPV6_RSS_TYPE_ALL_XI;
5260
5261                REG_WR(bp, BNX2_RLUP_RSS_CONFIG, val);
5262
5263        }
5264}

うん…。

で、もしかしたら、割り込みを無効にして複数プロセッサからポーリングし、RSSとマルチキューだけ有効にしたらこのボードでもRSS出来ねぇかな?って思ったんだけど。
今の所うまく動かない(´・ω・`)←これが本来のネタになるハズだった

データシート眺めると、どうもBCM5708では足りないレジスタが色々あるような気がしてならない…。
けど、出来ないとも断定出来ず。。

気を取りなおしてみた、が…

結局BCM5709も入手して試してしまった。
今度はちゃんと割り込みが複数登録されて、複数プロセッサに割り込む事が確認出来た。
が、これ、ちゃんとプロセスのあるCPUに割り込んでいるのだろうか?
ソースコードを読んで気になった事がある。
bnx2.cでRSSのテーブルに書き込んでいるのはさっき確認したこの辺りだ。

5250                for (i = 0; i < BNX2_RXP_SCRATCH_RSS_TBL_MAX_ENTRIES; i++) {
5251                        tbl[i % 4] = i % (bp->num_rx_rings - 1);
5252                        if ((i % 4) == 3)
5253                                bnx2_reg_wr_ind(bp,
5254                                                BNX2_RXP_SCRATCH_RSS_TBL + i,
5255                                                cpu_to_be32(tbl_32));
5256                }

が、BNX2_RXP_SCRATCH_RSS_TBLで検索しても、ここ以外にこの場所を読み書きしている箇所が見当たらない…。

慌ててigbのコードも見てみる。無い… RSS周りの初期化処理はあるんだけど、後からテーブルを更新する処理は見当たらない。
そういう使い方をするものでは無いのか…?

igbのRSSに関する話題がないかググってみたら、こんなのが出てきた:
Re: [E1000-devel] RSS - Receive-Side Scaling on Intel PRO/1000 NIC

the Intel provided IGB driver on sourceforge supports full tx and rx multiple queues with MSI-X (tx multiple queues requires
a 2.6.23, recommend a 2.6.25.4 kernel) and RSS based steering to the multiple
queues. Right now the hash that steers the flows to a particular queue is
random, but can easily be made static with a simple patch.

なんか今でもrandomに振ってる?もしかして…
だとすると、こんな感じで動いてるのかもしれない。

ioctlで静的に割り付ける事が出来るような事が話題になってるような気がしないでもないんだけど。
どうなんだろう。

あと、WindowsRSS出来ててもLinuxでは出来てないNICがあるような感じに書いてある気もする。
で、Intel Pro/1000 PTを買って試したらRSSできなくて、MLに聞きに来たらVT買えって言われてるような…それどっかで聞いたことある話だなぁヲイ…。

Windowsのドライバのソースコードがあるなら読むんだけど…無いよね。
色々わからん∩( ・ω・)∩オテアゲ!