BPFに関する情報収集

BPFについてサーベイしたので、それのまとめ. BPF for Dummiesのプロトタイプといえるよういしていけたら最高である。 現状は雑記状態なのでご了承いただきたい.

BPFとは,何をするためのものか

正直, 僕自身もよく分からない。 BPFはin kernelのパケットフィルタに最適な 仮想機械として設計実装されたが、現在はkernel内部のあらゆるデータフローを トレーシングやデバッグするために 用いられている。といった感じか。。。

構成

eBPFがattachできるポイントは現状で以下. ちなみにcBPFはsocketのみをサポートしている

• socket (via setsockopt) (hook skb)
• kprobe (via bcc) (func-call-infos)
• uprobe (via bcc) (func-call-infos)
• trace points (via bcc) (func-call-infos)
• syscall (via seccmomp) (system-call-infos)
• tc (no exploring)

みやすくするとこんな感じ(iovisorのスライド)

引用: https://www.iovisor.org

cBPF,eBPF

eBPF(Extended BPF)の登場後、伝統的なBPFの区別のために伝統的なBPFをcBPF (Classic BPF)とよぶようになりました。現在では一般的にBPFと呼ぶとeBPFを さしていることがほとんどのようです。

違いを簡単にまとめた.

	cBPF	eBPF
Register	32bit 2 regs	64bit 10 regs
Memory	stack	stack
Instruction	4B ld/st to stack	1-8B ld/st to stack
Instruction	1-8B ld to packet	1-8B ld/st fo packet
Instruction	Cond Jump forward	Cond Jump forward/backward
Instruction	ALU Instructions	Same + Signed Shift + Bswap
Else	.	Helper Functions
Else	.	Helper Data Structure

引用: https://www.slideshare.net/PLUMgrid/ebpf-and-linux-networking

Linuxではより高度な作業を可能にするためSKBのフィールドをマクロで参照できるよう にしている。kernel docに概要がのせられているので、以下に示す。

  len                skb->len
  proto              skb->protocol
  type               skb->pkt_type
  poff               Payload start offset
  ifidx              skb->dev->ifindex
  nla                Netlink attribute of type X with offset A
  nlan               Nested Netlink attribute of type X with offset A
  mark               skb->mark
  queue              skb->queue_mapping
  hatype             skb->dev->type
  rxhash             skb->hash
  cpu                raw_smp_processor_id()
  vlan_tci           skb_vlan_tag_get(skb)
  vlan_avail         skb_vlan_tag_present(skb)
  vlan_tpid          skb->vlan_proto
  rand               prandom_u32()

引用: https://www.kernel.org/doc/Documentation/networking/filter.txt

CPUのIDまでとれるらしい。恐ろしい。。

命令セット

ここで書くと長くなってしまうので、別の記事に分割した。 そちらを参照すること。

slankdev.hatenablog.com

slankdev.hatenablog.com

活用例

• bcc (Generic Tracing Tool)
• seccomp
• socket filter

その他キーワード

• tc
• iptables (xt_bof)
• xdp
• lwt

cBPF命令セット

ここでは単純に表と図のみでcBPFにどのような命令が含まれて、 どのように動作するのかを示す。Instruction set archの設計論などは まったく触れない。 (ただつかう段階では必要ないため。) 必要があれば、それぞれのBitにどのような意味があるかも説明していく。

Encoding

struct cbpf_insn {
    uint16_t opcode;
    uint8_t  jt;
    uint8_t  jf;
    uint32_t k;
};

    msb                                                        lsb
    +------------------------+--------+--------+----------------+
    |           k            |   jf   |   jt   |     opcode     |
    +------------------------+--------+--------+----------------+

Instruction Classは以下の3つに分類できる.

• ALU
• Memory Access
• Branch
• Misc

ALU

Opcode	Mnemonic	Pseudocode
0x0004	add k	A+=k
0x0014	sub k	A-=k
0x0024	mul k	A*=k
0x0054	and k	A&=k
0x0044	or k	A|=k
0x0034	div k	A/=k
0x0064	lsh k	A<<=k
0x0074	rsh k	A>>=k
0x000c	add x	A+=X
0x001c	sub x	A-=X
0x002c	mul x	A*=X
0x004c	or x	A|=X
0x003c	div x	A/=X
0x005c	and x	A&=X
0x006c	lsh x	A<<=X
0x007c	rsh x	A>>=X
0x0084	neg	A=-A

Memory Access

Opcode	Mnemonic	Pseudocode
0x0000	ld k	A = k
0x0001	ldx k	X = k
0x0002	st M[k]	mem[k] = A
0x0003	stx M[k]	mem[k] = X
0x0020	ld [k]	A = ntohl((i32)(p+k))
0x0028	ldh [k]	A = short(&p[k])
0x0030	ldb [k]	A = p[k]
0x0040	ld [k]	A = ntohl((i32)(p+k))
0x0048	ldh [k]	A = short(&p[k])
0x0050	ldb [k]	A = p[k]
0x0060	ld M[k]	A = mem[k]
0x0061	ldx M[k]	X = mem[k]
0x0080	ld #pktlen	A = wirelen
0x0081	(n/a)	X = wirelen
0x00b1	ldxb 4*([k]&0xf)	X = (p[k]&0xf)<<2

Branch

Opcode	Mnemonic	Pseudocode
0x0005	ja k	pc+=k
0x0015	jeq k jt jf	pc+=(A==k)?jt:jf
0x0025	jgt k jt jf	pc+=(A>k)?jt:jf
0x0035	jge k jt jf	pc+=(A>=k)?jt:jf
0x0045	jset k jt jf	pc+=(A&k)?jt:jf
0x003d	jge x jt jt	pc+=(A>=X)?jt:jf
0x001d	jeq x jt jt	pc+=(A==X)?jt:jf
0x002d	jgt x jt jf	pc+=(A>X)?jt:jf
0x004d	jset x jt jt	pc+=(A&X)?jt:jf
0x0006	ret k	return k
0x0016	ret	return A

Misc

Opcode	Mnemonic	Pseudocode
0x0087	txa	A=X
0x0007	tax	X=A

Reference

• FreeBSDのソースコード (どこだったかわすれた。)

eBPF命令セット

ここでは単純に表と図のみでeBPFにどのような命令が含まれて、 どのように動作するのかを示す。Instruction set archの設計論などは まったく触れない。 (ただつかう段階では必要ないため。)

必要があれば、それぞれのBitにどのような意味があるかも説明していく。

Encoding

struct ebpf_insn {
    uint8_t  opcode;
    uint8_t  src:4;
    uint8_t  dst:4;
    uint16_t offset;
    uint32_t imm;
};

    msb                                                        lsb
    +------------------------+----------------+----+----+--------+
    |immediate               |offset          |src |dst |opcode  |
    +------------------------+----------------+----+----+--------+

Instruction Classは以下の3つに分類できる.

• ALU
• Byteswap
• Memory Access
• Branch

ALU

64bit ALU命令

Opcode	Mnemonic	Pseudocode
0x07	add dst, imm	dst += imm
0x0f	add dst, src	dst += src
0x17	sub dst, imm	dst -= imm
0x1f	sub dst, src	dst -= src
0x27	mul dst, imm	dst *= imm
0x2f	mul dst, src	dst *= src
0x37	div dst, imm	dst /= imm
0x3f	div dst, src	dst /= src
0x47	or dst, imm	dst |= imm
0x4f	or dst, src	dst |= src
0x57	and dst, imm	dst &= imm
0x5f	and dst, src	dst &= src
0x67	lsh dst, imm	dst <<= imm
0x6f	lsh dst, src	dst <<= src
0x77	rsh dst, imm	dst >>= imm (logical)
0x7f	rsh dst, src	dst >>= src (logical)
0x87	neg dst	dst = -dst
0x97	mod dst, imm	dst %= imm
0x9f	mod dst, src	dst %= src
0xa7	xor dst, imm	dst ^= imm
0xaf	xor dst, src	dst ^= src
0xb7	mov dst, imm	dst = imm
0xbf	mov dst, src	dst = src
0xc7	arsh dst, imm	dst >>= imm (arithmetic)
0xcf	arsh dst, src	dst >>= src (arithmetic)

Opcode	Mnemonic	Pseudocode
0x04	add32 dst, imm	dst += imm
0x0c	add32 dst, src	dst += src
0x14	sub32 dst, imm	dst -= imm
0x1c	sub32 dst, src	dst -= src
0x24	mul32 dst, imm	dst *= imm
0x2c	mul32 dst, src	dst *= src
0x34	div32 dst, imm	dst /= imm
0x3c	div32 dst, src	dst /= src
0x44	or32 dst, imm	dst |= imm
0x4c	or32 dst, src	dst |= src
0x54	and32 dst, imm	dst &= imm
0x5c	and32 dst, src	dst &= src
0x64	lsh32 dst, imm	dst <<= imm
0x6c	lsh32 dst, src	dst <<= src
0x74	rsh32 dst, imm	dst >>= imm (logical)
0x7c	rsh32 dst, src	dst >>= src (logical)
0x84	neg32 dst	dst = -dst
0x94	mod32 dst, imm	dst %= imm
0x9c	mod32 dst, src	dst %= src
0xa4	xor32 dst, imm	dst ^= imm
0xac	xor32 dst, src	dst ^= src
0xb4	mov32 dst, imm	dst = imm
0xbc	mov32 dst, src	dst = src
0xc4	arsh32 dst, imm	dst >>= imm (arithmetic)
0xcc	arsh32 dst, src	dst >>= src (arithmetic)

Byteswap

Opcode	Mnemonic	Pseudocode
0xd4 (imm == 16)	le16 dst	dst = htole16(dst)
0xd4 (imm == 32)	le32 dst	dst = htole32(dst)
0xd4 (imm == 64)	le64 dst	dst = htole64(dst)
0xdc (imm == 16)	be16 dst	dst = htobe16(dst)
0xdc (imm == 32)	be32 dst	dst = htobe32(dst)
0xdc (imm == 64)	be64 dst	dst = htobe64(dst)

Memory Access

Opcode	Mnemonic	Pseudocode
0x18	lddw dst, imm	dst = imm
0x20	ldabsw src, dst, imm	See kernel documentation
0x28	ldabsh src, dst, imm	…
0x30	ldabsb src, dst, imm	…
0x38	ldabsdw src, dst, imm	…
0x40	ldindw src, dst, imm	…
0x48	ldindh src, dst, imm	…
0x50	ldindb src, dst, imm	…
0x58	ldinddw src, dst, imm	…
0x61	ldxw dst, [src+off]	dst = (uint32_t ) (src + off)
0x69	ldxh dst, [src+off]	dst = (uint16_t ) (src + off)
0x71	ldxb dst, [src+off]	dst = (uint8_t ) (src + off)
0x79	ldxdw dst, [src+off]	dst = (uint64_t ) (src + off)
0x62	stw [dst+off], imm	(uint32_t ) (dst + off) = imm
0x6a	sth [dst+off], imm	(uint16_t ) (dst + off) = imm
0x72	stb [dst+off], imm	(uint8_t ) (dst + off) = imm
0x7a	stdw [dst+off], imm	(uint64_t ) (dst + off) = imm
0x63	stxw [dst+off], src	(uint32_t ) (dst + off) = src
0x6b	stxh [dst+off], src	(uint16_t ) (dst + off) = src
0x73	stxb [dst+off], src	(uint8_t ) (dst + off) = src
0x7b	stxdw [dst+off], src	(uint64_t ) (dst + off) = src

Branch

Opcode	Mnemonic	Pseudocode
0x05	ja +off	PC += off
0x15	jeq dst, imm, +off	PC += off if dst == imm
0x1d	jeq dst, src, +off	PC += off if dst == src
0x25	jgt dst, imm, +off	PC += off if dst > imm
0x2d	jgt dst, src, +off	PC += off if dst > src
0x35	jge dst, imm, +off	PC += off if dst >= imm
0x3d	jge dst, src, +off	PC += off if dst >= src
0x45	jset dst, imm, +off	PC += off if dst & imm
0x4d	jset dst, src, +off	PC += off if dst & src
0x55	jne dst, imm, +off	PC += off if dst != imm
0x5d	jne dst, src, +off	PC += off if dst != src
0x65	jsgt dst, imm, +off	PC += off if dst > imm (signed)
0x6d	jsgt dst, src, +off	PC += off if dst > src (signed)
0x75	jsge dst, imm, +off	PC += off if dst >= imm (signed)
0x7d	jsge dst, src, +off	PC += off if dst >= src (signed)
0x85	call imm	Function call
0x95	exit	return r0

Reference

• The official documentation for the eBPF instruction set
• https://github.com/iovisor

The White Paper of Packet Processing 作成のためのMemo

完成はしないが、お勉強は大事である。 なんかしっていたら教えてください。。。涙

Hardware と Softwareでの選択はどのようにしておこなうのか。

下にいくについれて高性能だがフレキシブルでなくなる. とくにASICはできるまでに2年間くらいかかることもある.

1. Sofoware
   • In Kernel Software (NFV Migrationとか)
   • Kernel Bypass (DPDK, Netmap)
2. Hybrid
   • Reconf hard, FPGA (slow clockなのでAsicには性能が及ばないが、フレキシブル)
   • percial offload
3. Hardware
   • Full IO Offload (Asic Config)

目的(Target)によって選択を変える.

それぞれのポイント

• コスト
  • Opex (Operationg)
  • Capex (Capital)
• フレキシブルさ
• 性能

具体例

• Software
  • BPF
• Hybrid
  • FPGA
• Hardware
  • Flow Director
  • P4 Asic
  • Whitebox Switch
  • Hardware Switch

組織

• Community
  • FD.io
  • SONiC (Software for Open Networking in the Cloud)
• Campany
  • RedHat (OS以外 よくしらない)
  • Cviun (NW処理のチップベンダ, P4のASICもつくっている)
  • snaproute
• Mechanism
  • SAI (Switch Abstruction Interface)
  • Rack-scale Computing (MicroSoft HPC?)

その他

• Open vSwitchをFPGAでやりたいひとがいる

BPFにおけるJITとインタプリタの性能計測

gist.github.com

Thread Affinityによる性能実験

雑記状態なので、この記事もとても汚いことを了承してください。

DPDKはpthreadwを用いてスレッド操作を行っている。 内部でset affinityを行い、複数のCPUでスレッドを共有しないように固定している らしいが、実際に複数CPUで共有実行を行った場合と、単一CPUで動作をおこなった場合 どの程度性能に差がでるのかを検証してみた。

比較対象, 評価方法

比較対象

• 単一CPUで固定して動作させるthread
• 固定しないで動作させたthread

評価方法

• thread遅延 (無限loopの一回の遅延[clock])

ソースコード

#include <slankdev/system.h>
#include <slankdev/cpuset.h>
#include <slankdev/thread.h>


uint64_t func(int loop_count, bool setaffinity_1core)
{
  if (setaffinity_1core) {
    slankdev::cpuset cpuset(0x2);
    slankdev::thread_self th;
    th.setaffinity_np(sizeof(cpu_set_t), cpuset.get_native());
  }

  uint64_t before = slankdev::rdtsc();
  for (size_t i=0; i<loop_count; i++) ;
  uint64_t latency = slankdev::rdtsc() - before;
  return latency;
}


int main()
{
  for (size_t i=0; i<10; i++) {
    printf("test%zd\n", i);
    uint64_t affinity_true  = func(1000000000, true);
    uint64_t affinity_false = func(1000000000, false);
    printf("+ affinity true : %lu \n", affinity_true );
    printf("+ affinity false: %lu \n", affinity_false);
  }
}

実験結果

以下に示す

test0
+ affinity true : 4681434790
+ affinity false: 4634806268
test1
+ affinity true : 4637598020
+ affinity false: 4663916764
test2
+ affinity true : 4591219566
+ affinity false: 4599745108
test3
+ affinity true : 4612664322
+ affinity false: 4619733254
test4
+ affinity true : 4570637696
+ affinity false: 4547641394
test5
+ affinity true : 4606940932
+ affinity false: 4582990918
test6
+ affinity true : 4576054526
+ affinity false: 4612506292
test7
+ affinity true : 4552900718
+ affinity false: 4551479516
test8
+ affinity true : 4559223794
+ affinity false: 4556642934
test9
+ affinity true : 4600009958
+ affinity false: 4597938462

空のループなので、とくに性能の変化は大きくは見えなかった。 メモリアクセスとかいろいろやったらもしかしたら変わるかもしれないので、 今後少しずつ結果を伸ばしていきたい.

Linux Network Stack Debugging using eBPF

とりあえずLinux Kernelのネットワークスタックのデバッグ/トレースをしてみようと思う。

Bccを用いたトレース手順

1. デバッグ対象を決める
   • hookポイント
   • trace内容
2. それに対して必要なスクリプトを書く (bcc, bpf, python, c)
3. スクリプトを動かしてTraceを確認する

今回は例としてaf_packet socketで開いたsocketでのpacket送信をtraceして、どのようなpacketが 送信されているのかをしらべてみる. また, trace開始時からどれだけパケットを送信したかもカウントする。 まとめると以下ような内容になる。

• packet_sendmsg関数にhook pointを仕掛ける
• traceする関数では以下を行う
  • どのようなパケットが送られているかをprintkする
  • パケット送信回数をカウントする

パケット情報表示では、ほんとはバイナリ表示したかったが、packet長のみを表示することになってしまった。 (eBPFのスクリプトが大きくなりすぎて、エラーが出てしまいできなかった。今後もしらべて行きます。。。)

実践

今回traceする関数は以下の関数です。

github.com

トレースをするために動作確認用としてpacket socketを用いてパケット送信を行うsample programを用意しました。 このプログラムを実行するとpacket socketからarpパケットが一つだけ送信されます。 gist.github.com

このプログラムで用いるlibslankdevの使用方法はこちらを参照してください github.com

本題のトレーススクリプトは以下のようになります。

gist.github.com

実行結果を以下に示す。

$ sudo ./trace.py
[1]:
+ sock=ffff88030b9d2f80
+ msg=ffff8802daac7dc0
+ len=42
[2]:
+ sock=ffff88030b9d2f80
+ msg=ffff8802daac7dc0
+ len=42
[3]:
+ sock=ffff88030b9d2f80
+ msg=ffff8802daac7dc0
+ len=42
[4]:
+ sock=ffff88030b9d2f80
+ msg=ffff8802daac7dc0
+ len=42
^C%
$

今回は簡単なtraceのみだったが、もっと複雑なことができるはず、と信じてもっと勉強しよう。 デバイスドライバの関数とかもhookできるか時間があったらしらべたい。

参考文献

• bcc/reference_guide.md at master · iovisor/bcc · GitHub
• bcc/tutorial.md at master · iovisor/bcc · GitHub
• bcc/tutorial_bcc_python_developer.md at master · iovisor/bcc · GitHub
• bccでuprobes - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ