読者です 読者をやめる 読者になる 読者になる

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

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

構成変更前の環境

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

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

構成変更後の構成

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

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

v6プラスの効果

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

特に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をブリッジモードで使用。

f:id:yunazuno:20170513161528j:plain

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

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

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

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

f:id:yunazuno:20170507222600p:plain (スライド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_ARRAYbpf_tail_call() である。

yunazuno.hatenablog.com

上記エントリで紹介した通り、BPF_MAP_TYPE_PROG_ARRAYbpf_tail_call()を組み合わせることで、複数のeBPFプログラムを連結して呼び出したり実行中のeBPFプログラムを動的に入れ替えたりできる。ちなみにこの機能を実装したAlexei StarovoitovFacebookに在籍している*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*4VMWareに買収される出来事があったものの、特に大きな影響も無く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である。protoETH_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であれば、該当NICinterfaceセクションの下に下記設定を入れてあげれば良さそう:

$ 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

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

Reference

*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 コマンドを使う.

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

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を行っているのは下記の部分.現状,bccpython 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らの手法*2Rendezvousと比べ,各エントリに均等に分散されることが示されている.また,テーブルサイズ m が十分に大きければ,エントリの追加・削除によって影響を受ける割合も小さくなることも示されている.ただし,mの値を大きくすることは計算量の増大に繋がるため,考慮が必要である.

留意点

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

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

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

*2:元祖Consistent Hash

*3:例えばSipHash

Linuxカーネルの新機能 XDP (eXpress Data Path) を触ってみる

先日netdev 1.2に参加してみたところ,XDP(eXpress Data Path)の話題で持ち切りといった感じだった. というわけで,XDPについて一通り調べつつ,実際に触ってみた.

XDPとは何か?

誤解を恐れずに一言で言うと,「Intel DPDKのような高速パケット処理基盤をLinuxカーネル自身が用意したもの」であると理解している.このスライドでは

A programmable, high performance, specialized application, packet processor in the Linux networking data path

と言っている.

DPDKはユーザランドアプリケーションがNICを直接叩く(=カーネルのネットワークスタックをバイパスする)ことで高速処理を実現している.一方XDPは,カーネル内の最もNICドライバに近い場所でフックしてeBPFを実行することによりパケット処理を実現する.

f:id:yunazuno:20161010181639p:plain (iovisor.orgより)

eBPFはカーネル内でプログラムを実行するための汎用的な仕組みで,パフォーマンス計測やセキュリティ方面で使用されている,らしい.これまでもtc-bpf(8)のようにeBPFでパケット処理を行う仕組み自体は用意されていたが,XDPによってより早い段階でパケット処理を行えるようになった.

XDPの概要についてはiovisor.orgの説明ページや冒頭で触れたスライドが詳しい.

XDP | IO Visor Project

bpf-docs/Express_Data_Path.pdf at master · iovisor/bpf-docs · GitHub

パフォーマンス

パフォーマンスは現時点において,受信したパケットを全てドロップするケースで20Mpps, L3フォワーディングでも10Mpps程度を達成するとされている.

youtu.be (6:46あたりから)

Next steps for Linux Network stack approaching 100Gbit/s by Jesper Dangaard Brouer @ Netfilter Workshop, June 27, 2016

動作環境

XDPを利用するには,カーネル自体に加えてNICドライバでもサポートが必要となる. 先日リリースされた4.8でXDPサポートおよびMallanox mlx4ドライバサポートが取り込まれたので,少なくともこれ以降のカーネルが必要となる.

開発用としてe1000をサポートするパッチも出ているが,まだリリースされていない.

xdp-vagrantでXDPを手軽に試す

ここまでに書いたように,XDPが動作する環境を準備するのは若干敷居が高い.そこで便利なのがxdp-vagrant.

github.com

これを使うと,XDPサポート済みカーネル*1 + e1000サポートパッチ + BCC導入済みな環境がvagrantで簡単に手に入る.

BCC(BPF Compiler Collection)はユーザランドで動作するツール群で,XDPプログラムの読み込みやカーネル側のデータの操作を補助してくれる.Pythonバインディングが用意されているので,XDPプログラムはCで書きつつ*2ユーザランド側のマネジメント廻りをpythonで書く,ということが容易に実現できる.

github.com

ちなみに,ユーザランドカーネルの両方をCで書く場合のサンプルコードは下記にある.

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

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

vagrant upまで

Vagrantfileがlibvirt providerを前提に書かれいているので,vagrant-libvirtプラグインが利用可能な環境を事前に作っておく必要がある.更に,vagrant-restartプラグインも必要. 加えて,オリジナルのVagrantfileだと何故か ubuntu/trusty64 boxが指定されているが,このboxはlibvirt pluginに対応していない.自分でlibvirt対応boxを用意するか,他のlibvirt対応boxで代用する必要がある.ここでは s3than/trusty64 を使うことにする.

$ git clone https://github.com/iovisor/xdp-vagrant
$ cd xdp-vagrant
$ cat <<EOF | patch -p1
diff --git a/Vagrantfile b/Vagrantfile
index 2ee7327..c4392c6 100644
--- a/Vagrantfile
+++ b/Vagrantfile
@@ -5,7 +5,7 @@
 end

 Vagrant.configure('2') do |config|
-  config.vm.box = "ubuntu/trusty64" # Ubuntu 14.04
+  config.vm.box = "s3than/trusty64" # Ubuntu 14.04
   config.vm.network "private_network", ip: "192.168.50.4"

   # fix issues with slow dns https://www.virtualbox.org/ticket/13002
EOF
$ vagrant plugin install vagrant-libvirt vagrant-reload
$ vagrant up
$ vagrant ssh -c "uname -a"
Linux vagrant-ubuntu-trusty-64 4.7.0-07282016-torvalds+ #28 SMP Thu Jul 28 11:52:33 PDT 2016 x86_64 x86_64 x86_64 GNU/Linux

特定ポート宛パケットをドロップする例

bccに含まれるサンプルコード xdp_drop_count.py を参考に,80/tcpと8080/tcp宛てパケットを全てドロップしつつ,ドロップした総パケット数をポート毎にカウントするプログラムを書いてみた.

XDP: drop 80/tcp and 8080/tcp

パケットが到着するたびに drop_80_8080 が呼ばれる.この関数でXDP_PASSを返せばパケットは通常のネットワークスタックに送られる.XDP_DROPでドロップ,XDP_TXでTX queueに直接送り込まれる.

上記のプログラムを実行した状態でホスト側からvagrant VMのeth1宛にncやcurlでパケットを送ると,ドロップカウンタがカウントアップしていくことが分かる.ドロップカウンタのインクリメントはカーネル側で行い,それをユーザランドpythonプログラムから参照して出力している.

vagrant$ $ ls -l 
total 8
-rw-rw-r-- 1 vagrant vagrant 2034 Oct 10 06:10 drop_80_8080.c
-rwxrwxr-x 1 vagrant vagrant  807 Oct 10 06:06 loader.py

vagrant# ./drop_packet.py eth1
In file included from /virtual/main.c:4:
In file included from include/linux/if_ether.h:23:
In file included from include/linux/skbuff.h:34:
In file included from include/linux/dma-mapping.h:6:
In file included from include/linux/device.h:24:
In file included from include/linux/pinctrl/devinfo.h:21:
In file included from include/linux/pinctrl/consumer.h:17:
In file included from include/linux/seq_file.h:10:
include/linux/fs.h:2658:9: warning: comparison of unsigned enum expression < 0 is always false [-Wtautological-compare]
        if (id < 0 || id >= READING_MAX_ID)
            ~~ ^ ~
1 warning generated.
XDP loaded.
80: 1
80: 2
80: 2
8080: 1
80: 2
8080: 2
80: 2
8080: 2
80: 2
8080: 2
host$ echo | nc 192.168.50.4 80    # timeout as no response
host$ echo | nc 192.168.50.4 8080  # timeout as no response
host$ echo | nc 192.168.50.4 81
Ncat: Connection refused.

まとめ

Linuxカーネルに最近追加された高速パケット処理基盤XDPを少しだけ触ってみた.まだリリースされて間も無いということもあって利用可能な環境や関連資料は少ないものの,MellanoxをはじめとしたNICベンダも(eBPF hardware offload含め)サポートに積極的であるように見えるので,今後徐々に盛り上がっていくと思われる.

DPDKと比較してどうか,という部分に関しては,既存のネットワークスタックとの共存やeBPF関連ツールの流用が効く,といった点がアプリケーションを書く側にとって嬉しい点になりそう.

何れにしても,今後の展開が楽しみ.

*1:4.8ではなく4.8 rc

*2:clangでeBPFにコンパイルされる