Generic XDPを使えばXDP動作環境がお手軽に構築できるようになった

XDP (eXpress Data Path) ネタ。

パフォーマンス上の理由から、XDPのパケット処理はskbが割り当てられる前にNICドライバから直接呼び出させる。そのため、XDPプログラムの動作にはNICドライバ側でのサポートが必要となる。

5月時点での対応ドライバリストは下記エントリ末尾に記載した。Linux kernel 4.12からixgbeでXDPがサポートされる予定とは言え、ハードウェアの準備も必要であり、従来XDPの動作を気軽に試すことは少し難しかった。

yunazuno.hatenablog.com

そこでkernel 4.12から登場するのが Generic XDP と呼ばれる機能である。これはskbが割り当てられた後にXDPのパケット処理を適用するものである*1。これによりNICドライバのサポートが無くともXDPプログラムを実行可能になった。パフォーマンスを犠牲にする代わりに、XDPプログラムの開発環境として使用したりXDP自体の間口を広げることを目的としている。

動作環境

前述した通り、Generic XDPはkernel 4.12でリリース予定である。4.12 rc3時点で既に最初のコミットに加えいくつかの微修正やサンプルコードの更新もマージされている。

プログラムのアタッチ時の動作

ネットワークインタフェースにXDPプログラムをアタッチする際*2、ドライバ側でのXDPサポート状況やフラグの値により、通常のNIC-level XDPを使用するか、あるいはGeneric XDPを使用するかが決定される。

• デフォルト: まずNIC-level XDPでのアタッチを試み、失敗したら (=NICドライバがサポート外) Generic XDPを使用する
• XDP_FLAGS_SKB_MODE を指定: Generic XDPのみを使用する
• XDP_FLAGS_DRV_MODE を指定: NIC-level XDPでのアタッチのみを試みる。Generic XDPは使用しない

また、iproute2 (ipコマンド) はバージョン4.10からXDPプログラムローダとしての機能を持っている。更に次回リリースではGeneric XDPに特化したロード (上記 XDP_FLAGS_SKB_MODE に該当) もサポートされる予定である。

実際に試してみる

簡単なXDPプログラムを用意した上でそれをXDP非対応NICにアタッチし、Generic XDPが期待通り動作することを確認する。 また、XDPプログラムローダとして、過去のエントリで使用したiovisor/bccではなくiproute2を使用する。

• Kernel: 4.12 rc3 (Fedora rawhide 4.12.0-0.rc3.git0.2.fc27.x86_64)
• iproute2: 4.11+ (5a3ec4b)
• NIC: 8139cp (qemu-kvm RTL8139, ens4)
  • NIC-level XDPは非サポート

まず、全ての受信パケットをドロップするXDPプログラムを用意し、コンパイルする:

#include <linux/bpf.h>

#ifndef __section
# define __section(NAME)                  \
   __attribute__((section(NAME), used))
#endif

__section("prog")
int xdp_drop(struct xdp_md *ctx)
{
    return XDP_DROP;
}

char __license[] __section("license") = "GPL";

$ clang -O2 -Wall -target bpf -c xdp_drop.c -o xdp_drop.o

続いて、これをipコマンドでens4にアタッチする:

# ip link set dev ens4 xdp obj xdp_drop.o

ip link showの出力結果にxdpgenericという文字列が出現し、Generic XDPでXDPプログラムがアタッチされていることが確認できる*3。

# ip link show dev ens4
2: ens4: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 xdpgeneric qdisc fq_codel state UP mode DEFAULT group default qlen 1000
    link/ether 52:54:00:71:fc:9b brd ff:ff:ff:ff:ff:ff

デタッチは同様にipコマンドで:

# ip link set dev ens4 xdp off

このとき別ノードからens4宛にpingを打ってみると、XDPプログラムをアタッチしていた間、pingのレスポンスが無くなっていたことが確認できる。

$ ping 192.168.11.239
PING 192.168.11.239 (192.168.11.239) 56(84) bytes of data.
64 bytes from 192.168.11.239: icmp_seq=1 ttl=64 time=0.560 ms
64 bytes from 192.168.11.239: icmp_seq=2 ttl=64 time=0.318 ms
64 bytes from 192.168.11.239: icmp_seq=3 ttl=64 time=0.385 ms
64 bytes from 192.168.11.239: icmp_seq=8 ttl=64 time=0.594 ms
64 bytes from 192.168.11.239: icmp_seq=9 ttl=64 time=0.508 ms
64 bytes from 192.168.11.239: icmp_seq=10 ttl=64 time=0.624 ms
^C
--- 192.168.11.239 ping statistics ---
10 packets transmitted, 6 received, 40% packet loss, time 9205ms
rtt min/avg/max/mdev = 0.318/0.498/0.624/0.111 ms

References

• kernel/git/davem/net-next.git - David Miller's -next networking tree
  • Generic XDPの最初のコミット。コミットログを読めば、おおよそ背景が理解できるはず。
• Eval Generic netstack XDP patch — Prototype Kernel 0.0.1 documentation
  • Generic XDPのパフォーマンスに関する考察。
• BPF and XDP Reference Guide — Cilium v0.8 documentation
  • eBPFとXDP全般に関するリファレンスガイド。iproute2をXDPプログラムローダとして使用する際のサンプルが豊富。

*1:具体的に言うとnet/core/dev.cのnetif_receive_skb_internal

*2:netlink経由で実行する; サンプル: http://elixir.free-electrons.com/linux/v4.12-rc3/source/samples/bpf/bpf_load.c#L674

*3:通常のNIC-level XDPの場合は単に xdp と表示される

自宅のルータをAT-AR2050Vに入れ替えた & 回線をv6プラス化した

自宅マンションで光配線方式のフレッツが使えるようになったので、これを機にルータの入れ替えとv6プラス(IPv6 IPoE)化を実施したメモ。 結論から言うと、IPv4 PPPoE時代に発生していた夜間帯の輻輳が解消され、かなり快適になった。

構成変更前の環境

現住居に引っ越した時点ではフレッツのVDSL方式しか選択肢が無かったため、一旦考えるのをやめて最低限インターネットに接続できる環境だけを構築して使っていた。

• 回線: NTT東日本 フレッツ 光ネクスト マンションタイプ VDSL方式
• ISP: Biglobe
• ルータ: Buffalo BBR-4MG

ひかり電話契約は無し。VDSLモデムの下にルータが居て、そこでIPv4 PPPoEを終端するだけの単純な構成。

構成変更後の構成

回線が光配線方式に。また、Biglobe経由でJPNEのv6プラスも適用。

• 回線: NTT東日本 フレッツ 光ネクスト ギガマンション スマートタイプ 光配線方式
  • ひかり電話に新規加入
• ISP: Biglobe
  • v6プラスを使用
• ルータ: Allied Telesis AT-AR2050V

AT-AR2050Vなのは昨年末までキャンペーンで3万円弱で買えたため。昨年末、似たような価格でJuniper SRX300がeBayで大量に出回っていて気になったものの見送り。

v6プラスの効果

今回の構成変更で一番効果が有ったのは、v6プラス化したことにより夜間帯の輻輳が解消されたこと。

ようやく自宅回線をVDSLから光配線(光ネクスト スマートタイプ)に変更できたので，ついでにv6プラスに切り替えた．Biglobe PPPoEで恒常的に発生していた夜間帯のパケロス・高レイテンシが解消されてかなり快適になった． pic.twitter.com/R5yZVc5kvy

— yunazuno (@yunazuno) 2017年2月26日

特にDNS名前解決が速くなったのが体感速度向上に貢献しているように思う。帯域幅に関してはそれほど気にしていないが、試しに ftp.kddilabs.jp から適当なisoイメージをダウンロードすると400Mbps弱出ている。

ネットワーク構成

それほど複雑なことはしていない。HGW (PR-500MI) - ルータ (AT-AR2050V) - L2 (GS908M) というシンプルな構成。 AR2050Vでrouted VLAN interfaceを2個作成し、それぞれを日常生活用と各種実験用として使っている。VLANはGS908Mまでtag VLANで運び、そこでポート毎に解いている。

IPv4インターネット接続に関しはHGWでNAT(MAP-E)されて出ていく。AR2050Vの下に居るサブネット宛のstatic routeをHGWに設定する必要があるので注意。 IPv6インターネット接続に関しては、HGWからAR2050VにDHCPv6-PDで/60が振ってくるので、これをクライアントに振っている。

IPv6まわりに関しての設定例がアライドテレシスのサイトにあるので、それほど苦労せずに設定できた。

AT-AR2050V/AT-AR3050S/AT-AR4050S コマンドリファレンス 5.4.7: 設定例集#44: フレッツ 光ネクスト IPv6インターネット接続（IPv6 IPoE、DHCPv6 PD方式）

機器周辺はこんな感じ。横向きなのがHGWで、隙間に居るのはDNSフルリゾルバ兼DHCPサーバのRaspberry Pi. 上の段に居るのは各種実験用に使っているQuanta LB6M. 無線LANはHGW内蔵APは使用せず、Aterm WG1200HPをブリッジモードで使用。

Facebookはレイヤ4ロードバランサをIPVS(LVS)からXDPベースのものに乗り換えつつある

4月に開催されたnetdev 2.1で面白いセッションがあったのでメモ。

Facebookが使用しているレイヤ4のロードバランサに関する発表で、従来はIPVS (LVS) を使用していたが、XDPベースで自ら開発したものに移行しつつある、という内容。

XDP Production Usage: DDoS Protection and L4LB (slide)

www.youtube.com

XDP (eXpress Data Path) については以前のエントリで簡単に紹介した。

yunazuno.hatenablog.com

XDPを改めて簡単に紹介すると、Linuxカーネルのネットワークスタックの最下部 (NICに一番近い場所) でパケット処理を行う仕組みのことで、オーバーヘッドが非常に小さい高速パケット処理の実現を目的としている。XDPはeBPFを用いており、eBPFが提供するmapやhelper functionといった機能を用いて柔軟なプログラムが書けることに加え、JITによる高速化やカーネル自身の堅牢性をそのまま享受することができるとされている。

XDPがリリースされたのは2016年10月のカーネル4.8なので、半年程で実際の事例が出てきたことになる。

FacebookにおけるXDPのユースケース: L4LB & DDoS防御

FacebookはIPVS (LVS) ベースのレイヤ4ロードバランサ (L4LB, 通称Shiv) を利用していることが知られている。

blog.stanaka.org

yunazuno.hatenablog.com

Shivの役割はConsistent Hashによる負荷分散先の決定とIP encapsulation (IPIP) によるパケット転送である。また、ローカルにセッションキャッシュを持つことにより、Consistent Hashの弱点であるリマップ時のセッション切断問題をカバーしている。

今回の発表では、これらの機能をXDPの基盤上で実装したのちIPVSベースの既存環境を置き換えていることが明かされた。スライドでは下のグラフが示され、XDPで実装された新しいShivがIPVSベースのそれと比較して高いスループットを発揮しつつもCPU使用率が低く抑えられている、と述べられている*1。

(スライドp3より; それぞれ1本だけラインが離れているものがXDP, 固まっているものがIPVS)

また、DDoS防御のための仕組み (Dropletと呼ばれる) も併せて紹介されている。

DDoS防御にあたっては、攻撃パケットを可能な限り早い段階で検出・遮断することが望ましい。加えて、攻撃パケット検出のシグネチャはプログラマブルに構成・変更可能であることが望ましい。彼らはこれもXDP上に実装している。L4LBのプログラムの前にDDoS検出・遮断のプログラムが実行されるようにすることで、L4LBが余分なリソースを消費することを防いでいる。

(スライドp10より; #0 XDP Dumpはデバッグ用のもの)

ちなみに、XDPによるDDoS防御についてはCloudflareのエンジニアも同様の発表を行っている。こちらはよりBPFにフォーカスした内容。

XDP in practice: integrating XDP in our DDoS mitigation pipeline (slide)

www.youtube.com

実装の詳細

冒頭のビデオで発表部分が12分弱で収まっていることからも分かる通り、やっていること自体は非常にシンプルである。

ただその裏では、(発表内で直接は触れられていないものの) XDPやその基礎となるeBPFの機能がふんだんに使われていることが見て取れる。これらの機能はFacebookのエンジニア自身によって実装されたのちLinuxカーネルにマージされたものも少なくない。

BPF_MAP_TYPE_LRU_HASH: セッション維持のためのLRU cache

Consistent Hashを用いるL4LBではその特性上、分散先のリアルサーバが増減したタイミングで幾許かのTCPセッションが意図せず切断されてしまう。この弱点を補うため、いくつかのL4LB実装ではセッションテーブルを併用している。TCP SYNパケットがL4LBに到達すると同時にセッションテーブルにセッション情報を記録すれば、仮にConsistent Hashのリマップが発生したとしてもセッションテーブルに基づいてTCPセッションを維持できる、という仕組みである。ただセッションテーブルのサイズは有限であるため、何らかの方法でセッションテーブルのメンテナンスを行う必要がある。

そこで登場するのがeBPF map objectのひとつ、BPF_MAP_TYPE_LRU_HASHである。その名前が示す通り、Least Recently Used (LRU) なハッシュテーブルである。これを利用すれば、先に述べた要件を満たすセッションテーブルを容易に実現できる。 この機能は冒頭で紹介したセッションのスピーカーであるMartin Lauによって開発され、kernel 4.10以降で利用可能である。

xdp_adjust_head(): IP encapsulation

ShivはL3DSRによるリアルサーバへのパケット転送にIPIP方式を採用している。これはリアルサーバ宛てIPヘッダで元のVIP宛てパケットをカプセル化することでパケット転送を実現するものである*2。 これをXDPで実現するため、メモリページ上であらかじめ空間 (headroom) を確保しておき、そこにデータ(ここではリアルサーバ宛てのIPヘッダ)を追加するインタフェースが用意されている。このインタフェースがeBPF helper functionのひとつ、bpf_xdp_adjust_head()である。この機能も同じくMartin Lauによって開発され、kernel 4.10以降で利用可能である。

なお、NICドライバには通常のXDPサポートとは別にheadroom確保のサポートが要求される。

BPF_MAP_TYPE_PROG_ARRAY & tail call: 複数のeBPFプログラムを連携させる

XDPはその仕様上、1個のネットワークインタフェースに対して1個のeBPFプログラムのみアタッチすることができる。これは1個のネットワークインタフェースに対して複数の独立した処理を適用したい場合に都合が悪い。 これを解決するのがBPF_MAP_TYPE_PROG_ARRAY と bpf_tail_call() である。

yunazuno.hatenablog.com

上記エントリで紹介した通り、BPF_MAP_TYPE_PROG_ARRAYとbpf_tail_call()を組み合わせることで、複数のeBPFプログラムを連結して呼び出したり実行中のeBPFプログラムを動的に入れ替えたりできる。ちなみにこの機能を実装したAlexei StarovoitovもFacebookに在籍している*3。

余談: XDPの近況

2016年10月にXDPがリリースされてから約半年が経過したが、その間に様々なアップデートが行われた。

まず大きなトピックとしてNICドライバのサポート拡充が挙げられる。当初はMellanox mlx4のみであったものが徐々に拡充され、先日遂にIntel ixgbeサポートがnet-nextにマージされた。恐らくカーネル4.12でリリースされると思われ、XDPが利用可能な環境が大幅に広がることになる。また変わり種として、CaviumのARM SoCであるThunderXでのサポートもnet-nextにマージされている。

現時点では、下記のNICドライバで利用可能あるいは近日中に利用可能となる:

• mlx4: Mellanox ConnectX-3
• mlx5: Mellanox ConnectX-4 or later
• nfp: Netronome Agilio
• qede: QLogic FastlinQ
• virtio_net: Virtio
• bnxt_en: Broadcom NetXtreme C-Series
• ixgbe: Intel X5xx (82598, 82599) (from kernel 4.12?)
• thunderx: Cavium ThunderX (from kernel 4.12?)

また、NICドライバのサポートが無くてもXDPプログラムを実行できるようにする仕組み (“Generic XDP”) も登場した。

kernel/git/torvalds/linux.git - Linux kernel source tree - net: Generic XDP

これは主に開発用やお試し用を意図しており、パフォーマンスに関しては考慮されていない。これまでXDPプログラムを実行するには、対応NICが挿さったハードウェアを用意するか、あるいはe1000, virtio_netの環境を用意する必要があった。Generic XDPの登場により、より手軽に開発環境を整えられるようになる。

なお、各カーネルバージョン毎にサポートされるeBPF/XDP関連の機能やドライバの情報はiovisor/bccのドキュメントに纏まっている:

bcc/kernel-versions.md at master · iovisor/bcc · GitHub

XDPリリース直後の2016年12月にPLUMgrid*4がVMWareに買収される出来事があったものの、特に大きな影響も無くXDP周辺の発展は続いている様子である。eBPF自体を含め機能がどんどん拡充されており、かつXDPのユースケースも徐々に出始めてきたことで、今後の動向がますます楽しみ。

*1:正直なところ、このグラフは読み方や環境、条件がよく分からないので何とも言えないところ。もちろん、XDPがIPVSと比較して同一条件下で高スループットが得られる、という結果自体は疑いようが無いものの・・・。

*2:対してIPヘッダのDSCPフィールドを使うのがDSCP方式 https://www.nanog.org/meetings/nanog51/presentations/Monday/NANOG51.Talk45.nanog51-Schaumann.pdf

*3:当時はPLUMgrid

*4:XDPを推進していた陣営のひとつ

eBPF tail call 使い方メモ

eBPFにはtail callと呼ばれるプログラム呼び出し方法が存在する。 これは、ある実行中のBPFプログラムから別のBPFプログラムにジャンプするものである。あくまでジャンプであって、通常の関数呼び出しと違って呼び出し元に処理は戻らない。ユースケースとしては例えば、役割が違う複数のプログラムの独立性を保ったまま連携させたい場合に役立つ。

bpf: introduce bpf_tail_call() helper [LWN.net]

また、tail callの面白い点として、ジャンプ先のルックアップは BPF_MAP_TYPE_PROG_ARRAY という種類のBPF mapを使う点が挙げられる。このmapは通常のBPF map同様、プログラム実行中にユーザ空間側から動的に書き換えることができる。したがって、ジャンプ先のプログラムを動的に入れ替えたり、あるいはジャンプを取りやめるといったことが容易に実現できる。

通常の使用例

tail callを使うには、BPF_MAP_TYPE_PROG_ARRAY のBPF mapを用意した上で bpf_tail_call() helperを使えばよい。カーネルの samples/bpf/sockex3_kern.c が参考になる。

linux/sockex3_kern.c at master · torvalds/linux · GitHub

該当部分を抜粋する*1:

#define PARSE_VLAN 1
#define PARSE_MPLS 2
#define PARSE_IP 3
#define PARSE_IPV6 4

static inline void parse_eth_proto(struct __sk_buff *skb, u32 proto)
{
    switch (proto) {
    case ETH_P_8021Q:
    case ETH_P_8021AD:
        bpf_tail_call(skb, &jmp_table, PARSE_VLAN);
        break;
    case ETH_P_MPLS_UC:
    case ETH_P_MPLS_MC:
        bpf_tail_call(skb, &jmp_table, PARSE_MPLS);
        break;
    case ETH_P_IP:
        bpf_tail_call(skb, &jmp_table, PARSE_IP);
        break;
    case ETH_P_IPV6:
        bpf_tail_call(skb, &jmp_table, PARSE_IPV6);
        break;
    }
}

jmp_table がprogram arrayである。proto が ETH_P_8021Q であれば jmp_table[PARSE_VLAN] が示すファイルディスクリプタのBPFプログラムにジャンプする。なお、もしここでjmp_table[n] が有効なBPFプログラムでない場合、そのまま処理が続行(fall-through)される点に注意。逆にこの特性を利用すれば、トラブルシューティングの時だけデバッグ用のBPFプログラムを登録する、といったことが可能になる。

bccでの使用例

ここではiovisor/bccを使った場合の動作を試してみることにする。bccにはprog_array.call()という構文のsyntax sugarが用意されており、bpf_tail_call()と等価な処理を容易に実現できる。

ここでは例として、通常時は全てのパケットを通過するが、コマンドによって全てのパケットをドロップするXDPプログラムを考える*2。

XDP program

カーネル空間側で実行されるXDPのコードは下記の通り。通常時はprog_entryを実行するが、パケットをドロップさせたい時はprog_dropにジャンプさせる。jmp_tableがprogram arrayである。

なお、events.perf_submit() はログをカーネル空間からユーザ空間に送るのに使用する。これもbccのsyntax sugarで、bpf_perf_event_output()と等価である。

// xdp_chain.c
BPF_TABLE("prog", int, int, jmp_table, 8);
BPF_PERF_OUTPUT(events);

struct event_t {
    u64 timestamp;
    char message[128];
};

int prog_drop(struct xdp_md *ctx)
{
    struct event_t e = {
        .timestamp = bpf_ktime_get_ns(),
        .message = "Enter prog_drop\0",
    };
    events.perf_submit(ctx, &e, sizeof(e));

    return XDP_DROP;
}


int prog_entry(struct xdp_md *ctx)
{
    struct event_t e_enter = {
        .timestamp = bpf_ktime_get_ns(),
        .message = "Enter prog_entry\0",
    };
    events.perf_submit(ctx, &e_enter, sizeof(e_enter));

    jmp_table.call(ctx, 0);

    struct event_t e_exit = {
        .timestamp = bpf_ktime_get_ns(),
        .message = "Exit prog_entry\0",
    };
    events.perf_submit(ctx, &e_exit, sizeof(e_exit));

    return XDP_PASS;
}

動作を観察する

ここでは簡単のため、ユーザ空間側の処理はipython経由で逐次実行する。

まずは下準備としてプログラムのロードまでを実施する。ここでevents.open_perf_buffer()は前述したログを読み出すためのもので、bpf.kprobe_poll()を呼び出してログが到着するとprint_event()がコールバックされる。

$ sudo ipython
In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:import ctypes as ct
:from bcc import BPF
:
:class Event(ct.Structure):
:    _fields_ = [
:        ("timestamp", ct.c_uint64),
:        ("message", ct.c_char * 128),
:    ]
:
:def print_event(cpu, data, size):
:    event = ct.cast(data, ct.POINTER(Event)).contents
:    print event.timestamp, event.message
:
:
:bpf = BPF(src_file="./xdp_chain.c")
:
:events = bpf["events"]
:events.open_perf_buffer(print_event)
:
:prog_entry = bpf.load_func("prog_entry", BPF.XDP)
:prog_drop = bpf.load_func("prog_drop", BPF.XDP)
:<EOF>

prog_entryをインタフェースens9にアタッチ。XDPでのパケット処理が開始される。

In [2]: bpf.attach_xdp("ens9", prog_entry)

ログは以下のようになっている。jmp_table に何も登録されていないためfall-throughされていることが確認できる。

In [3]: bpf.kprobe_poll()
87485224130884 Enter prog_entry
87485224144293 Exit prog_entry
87487208201839 Enter prog_entry
87487208220583 Exit prog_entry

この状態で、jmp_table[0] に prog_drop を登録してみる。

In [4]: jmp_table = bpf["jmp_table"]
In [5]: jmp_table[0] = prog_drop.fd 

外部からens9宛のpingが通らなくなり、パケットがドロップされるようになったことが確認できる。ログを確認すると、prog_dropが実行され、かつprog_entryの末尾部分に処理が戻っていないことも確認できる。

In [6]: bpf.kprobe_poll()
87669224146031 Enter prog_entry
87669224160730 Enter prog_drop
87671208094900 Enter prog_entry
87671208110055 Enter prog_drop

jmp_table[0]を削除すれば、再び最初の状態に戻る。

In [7]: del jmp_table[0]
In [8]: bpf.kprobe_poll()
87875240128813 Enter prog_entry
87875240144164 Enter prog_drop
87877224181681 Enter prog_entry
87877224199698 Enter prog_drop
87879208128601 Enter prog_entry
87879208145440 Exit prog_entry

*1:ライセンスは抜粋元のGPLに従う

*2:もちろん実用上は全てのパケットをドロップするのではなく何らかの条件に従ってドロップすることになる

Virtio-netでXDPを動かすにはqemuのオプション変更が必要

Linuxカーネル4.10からvirtio_netがXDPをサポートするようになった。だが、動作させるには少しオプション変更が必要となる。

Qemuの起動オプションに下記を渡すことでここに記載のあるオフロード機能が無効になり、XDPが動作するようになる:

gso=off,guest_tso4=off,guest_tso6=off,guest_ecn=off,guest_ufo=off

virshであれば、該当NICのinterfaceセクションの下に下記設定を入れてあげれば良さそう:

$ virsh edit XDP-VM
<domain type='kvm'>
...
  <devices>
    ...
    <interface type='network'>
      ...
      <model type='virtio'/>
      <driver name='vhost' queues='4'>
        <host gso='off' tso4='off' tso6='off' ecn='off' ufo='off'/>
        <guest tso4='off' tso6='off' ecn='off' ufo='off'/>
      </driver>
      ...
    </interface>
    ...
  </devices>
</domain>

Pitfall

上記設定をせずにXDPを使おうとすると、NICにプログラムをアタッチする段階でEOPNOTSUPP (Operation not supported) が返ってきて失敗する。また、ゲスト側のログに下のメッセージが出る:

$ dmesg
...
[  528.046901] virtio_net virtio4 ens9: can't set XDP while host is implementing LRO, disable LRO first

このメッセージと該当部分のコードを素直に読むと、ethtoolでlroないしtso/ufo/ecnを無効にしてやれば良さそうに見える。だが実際には前述した通りqemuのオプション側でこれらの機能を無効にする必要があるので注意が必要*1。

Reference

• XDP Newbie - Re: xdp on virtio_net
• Bug 1387477 – virtual interface offload for virtio - disable host ufo only will not work

*1:詳しくは追えていないがそういうものらしい https://www.spinics.net/lists/netdev/msg409656.html

Persistent eBPF map object with bcc

Linux kernel 4.4以降には，eBPF map/programを"永続化"する仕組みが実装されている．ここではその概要を説明しつつ，iovisor/bccを使って実際にその動作を確かめてみる．

Background: eBPF objectを複数プロセスで共有したい

eBPFにmapというデータ構造があることはXDPの紹介エントリのサンプルコード内で軽く触れた．

通常，mapはそれを作成したプロセスからのみ読み書き可能である．しかし，いくつかのユースケースにおいては，mapを複数のプロセスから読み書きできると都合が良いことがある．たとえば何からの統計情報(例えばパケットカウンタ)をmapに保存してそれを外部に転送したい場合，「統計情報をmapに保存するプロセス」と「収集された統計情報を加工して外部に転送するプロセス」とに分割したほうが，実装の見通しの観点から望ましい．また，mapに何らかの設定情報(例えばIPルーティングテーブル)を保存してパケットを加工したい場合，「ルーティングテーブルを参照してパケットの加工を行うプロセス」と「ルーティングテーブルのアップデートを行うプロセス」とに分割したほうが，安定性の観点から望ましい．

Kernel 4.4以前から，mapのfile descriptorをunix domain socket経由で他プロセスに共有することで，複数プロセス間でmapを共有することは可能ではあった．

frsyuki.hatenablog.com

この方法は汎用的である反面，決して簡単とは言い難い．そこで登場したのが，今回紹介するeBPF objectに特化した仕組みである．

Solution: eBPF objectをBPF filesystemに"ピン付け"する

Linux kernel 4.4から，eBPF objectをファイルシステム上のパスに割り当てる (“pinning”) する仕組みが実装された．

まず，eBPF objectとファイルシステム上のパスのマッピングを行うファイルシステム (ここでは仮にbpffsと呼ぶことにする) が用意されている．このファイルシステムを任意のパス (一般に/sys/fs/bpf) にマウントしておく．

linux/inode.c at master · torvalds/linux · GitHub

その上で，bpf(2) syscallに追加された BPF_OBJ_PIN コマンドを使ってpinningを行う．ファイルからeBPF objectを取得する際には同様に BPF_OBJ_GET コマンドを使う．

簡単なサンプルが以下に用意されている:

• Pin: prototype-kernel/bpf.c at master · netoptimizer/prototype-kernel · GitHub
• Get: prototype-kernel/bpf.c at master · netoptimizer/prototype-kernel · GitHub

Example: bccを使って複数プロセス間でeBPF mapの読み書き

C言語のコードから直接syscallを使ってpinningを行う例は既にいくつかある (例1, 例2) ため，ここではbccを使ってpython経由でeBPF mapのpinningと他プロセスからの読み込みを試してみる．例として，受信したパケット数をeBPFプログラムでカウントしてeBPF mapに書き込み，それを他のプロセスから読み込む場合を考える．

Code

counter.py: eBPF mapへの書き込み & pinning

受信したパケット数をカウントしてeBPF map “packet_counter” に書き込むプログラムである．このプログラムはtc-bpf(8)経由でネットワークインタフェースにアタッチされる．

from bcc import BPF, libbcc
import pyroute2
import ctypes
import time
import sys

code = """
#include <uapi/linux/bpf.h>
#include <uapi/linux/pkt_cls.h>

BPF_TABLE("array", uint32_t, long, packet_counter, 1);

int counter(struct __sk_buff *ctx) {
    uint32_t index = 0;
    long *value = packet_counter.lookup(&index);
    if (value)
        *value += 1;

    return TC_ACT_OK;
}
"""


def count_packet(iface, pin_path):
    bpf = BPF(text=code, cflags=["-w"])
    func = bpf.load_func("counter", BPF.SCHED_CLS)
    counter = bpf.get_table("packet_counter")
    
    print("map fd: {}".format(counter.map_fd))
    ret = libbcc.lib.bpf_obj_pin(counter.map_fd, ctypes.c_char_p(pin_path))
    if ret != 0:
        raise Exception("Failed to pin map")
    
    print("Pinned at: {}".format(pin_path))

    ip = pyroute2.IPRoute()
    ipdb = pyroute2.IPDB(nl=ip)
    idx = ipdb.interfaces[device].index
    ip.tc("add", "clsact", idx)
    ip.tc("add-filter", "bpf", idx, ":1", fd=func.fd, name=func.name,
          parent="ffff:fff2", classid=1, direct_action=True)

    print("Hit CTRL+C to stop")
    while True:
        try:
            print(counter[0].value)
            time.sleep(1)
        except KeyboardInterrupt:
            print("Removing filter from device")
            break

    ip.tc("del", "clsact", idx)
    ipdb.release()

if __name__ == '__main__':
    iface = device = sys.argv[1]
    pin_path = sys.argv[2]
    count_packet(iface, pin_path)

実際にpinningを行っているのは下記の部分．現状，bccのpython bindingに専用のインタフェースが無いため，libbccの関数を直接呼び出している．

counter = bpf.get_table("packet_counter")
ret = libbcc.lib.bpf_obj_pin(counter.map_fd, ctypes.c_char_p(pin_path))

reader.py: pinningされたeBPF mapの読み出し

こちらのコードでmapの値を読み込む．

from bcc import libbcc, table
import ctypes
import sys

class PinnedArray(table.Array):
    def __init__(self, map_path, keytype, leaftype, max_entries):
        map_fd = libbcc.lib.bpf_obj_get(ctypes.c_char_p(map_path))
        if map_fd < 0:
            raise ValueError("Failed to open eBPF map")

        self.map_fd = map_fd
        self.Key = keytype
        self.Leaf = leaftype
        self.max_entries = max_entries


def read_counter(map_path):
    counter = PinnedArray(map_path, ctypes.c_uint32, ctypes.c_long, 1)

    return counter[0].value


if __name__ == '__main__':
    path = sys.argv[1]
    
    print(read_counter(path))

キモは下記の部分．下記コードでmapのファイルディスクリプタが取得できる．上記コードではbcc.table.Arrayを再利用している．

map_fd = libbcc.lib.bpf_obj_get(ctypes.c_char_p(map_path))

実行例

まずはbpffsをマウント．

$ sudo mount -t bpf none /sys/fs/bpf
$ mount | grep bpf
none on /sys/fs/bpf type bpf (rw,relatime)

続いてcounter.pyを実行．

$ sudo python counter.py eth0 /sys/fs/bpf/counter
map fd: 4
Pinned at: /sys/fs/bpf/counter
Hit CTRL+C to stop
0
37
38
39
70
...

/sys/fs/bpf/counter が作成されていることが確認できる．

$ ls -l /sys/fs/bpf/counter 
-rw-------. 1 root root 0 Apr  8 14:23 /sys/fs/bpf/counter

この状態でreader.pyを実行．counter.py 側の出力とほぼ同じ値が取得できるはず．

$ sudo python reader.py /sys/fs/bpf/counter
253

なお，pinningしたobjectは生成元のプロセス(ここではcounter.py)を終了したとしても削除されない．削除するには明示的にunlinkする必要がある．

$ ls -l /sys/fs/bpf/counter 
-rw-------. 1 root root 0 Apr  8 14:23 /sys/fs/bpf/counter
$ sudo unlink /sys/fs/bpf/counter
$ ls -l /sys/fs/bpf/counter 
ls: cannot access '/sys/fs/bpf/counter': No such file or directory

References

• Persistent BPF objects [LWN.net]
  • Background, solutionのセクションに書いた内容がより詳しく述べられている
  • 初期のパッチ(v1; 実際にマージされたのはv2)を元に書かれているため，実際の実装とは内容が一部異なる．(BPF_PIN_FD -> BPF_OBJ_PIN, BPF_GET_FD -> BPF_OBJ_GET)
• bpf: add support for persistent maps/progs
  • 初期実装のコミット．LWNの記事同様，背景が詳しく述べられている
• BPFの現在 // Speaker Deck
  • Map pinningだけでなく，BPF全般の最近の動向が纏まっている

Maglev Hashing with Python

今更ながら，GoogleのMaglev論文で提案されているMaglev Hashingを手元で実装してみた．

Maglev: A Fast and Reliable Software Network Load Balancer

Maglev Hashingとは

所謂Consitent Hashの一種．Maglevロードバランサにおけるリアルサーバ選択に使用されている．

上記論文のSection 3.4で詳細が説明されている．NSDI'16での発表スライドも併せて眺めると分かりやすい．

Maglev: A Fast and Reliable Software Network Load Balancer | USENIX

Slide: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_slides_eisenbud.pdf

実装

Golang実装を参考にしつつ，Pythonで実装してみた．

gist.github.com

Example

256エントリを追加した状態で，更に1エントリの追加・削除を行っている．

テーブルサイズを65537としたとき*1，1エントリの追加・削除で影響を受ける割合が 772 / 65537 = 1.2%程度に抑えられていることが分かる．

>>> h = MaglevHash(m=65537)
>>> for i in range(256):
...     h.add("172.16.1.{}".format(i))
...
>>> h.populate()
65537
>>> h.add("192.168.1.1")
>>> h.populate()
772
>>> h.lookup("10.0.0.1")
'172.16.1.111'
>>> h.remove("172.16.1.111")
>>> h.populate()
700
>>> h.lookup("10.0.0.1")
'172.16.1.68'

なお，Maglev Hashingの評価は論文のSection 5.3で示されている．

Kargerらの手法*2やRendezvousと比べ，各エントリに均等に分散されることが示されている．また，テーブルサイズ m が十分に大きければ，エントリの追加・削除によって影響を受ける割合も小さくなることも示されている．ただし，mの値を大きくすることは計算量の増大に繋がるため，考慮が必要である．

留意点

論文中では実装の詳細が割愛されている．上記実装のうち，下記の点については注意が必要である:

• offset と skip の値を決定するために使用するハッシュ関数は，論文では与えられていない．上記実装では簡単のためsha256を使用している．実用上は，短い入力に対しても高速かつ良い結果が得られるハッシュ関数*3を使用するのが望ましいと考えられる．
• lookup() で使用するハッシュ関数についても同様に論文では与えられていない．上記実装ではoffset/skip同様にsha256を使用している．実用上何を使うべきかはアプリケーションの仕様やトラフィック特性に依存する部分があるので，ケースバイケースだと考えられる．

*1:エントリ数に対して十分に大きい素数を与える

*2:元祖Consistent Hash

*3:例えばSipHash