源起最近看到國內兩篇文章[1][2]先後翻譯了就職於Netflix的性能分析大牛Brendan Gregg於2017年7月31日寫的《Golang bcc/BPF Function Tracing》[3]，這迅速引起了我的興趣，2016年時我曾在做MQTT伺服器端開發時便意識到軟體調試及動態追蹤技 ...

源起

最近看到國內兩篇文章[1][2]先後翻譯了就職於Netflix的性能分析大牛Brendan Gregg於2017年7月31日寫的《Golang bcc/BPF Function Tracing》[3]，這迅速引起了我的興趣，2016年時我曾在做MQTT伺服器端開發時便意識到軟體調試及動態追蹤技術的重要性，其間研究春哥（章亦春 agentzh）的《動態追蹤技術漫談》[4]時，文中提及“最近幾年 Linux 的主線開發者們，把原來用於防火牆的 netfilter 里所使用的動態編譯器，即 BPF，擴展了一下，得到了一個所謂的 eBPF，可以作為某種更加通用的內核虛擬機。”，當時並不能理解這其中的意義所在，便沒有深入瞭解，直到最近看到這兩篇文章後，我重新進行了相關的研究，並意識到這項技術所將影響到的領域。

BPF 初窺

既然春哥提到Linux，那就先從《Linux Socket Filtering aka Berkeley Packet Filter (BPF)》[5]開始，文中提及：

在Linux中BPF比在BSD中更加簡單，人們不需要關心設備，你只需要創建你的filter代碼，然後通過SO_ATTACH_FILTER的socket選項將其發送給內核，如果你的代碼通過內核的檢查，那麼你就可以立即在那個socket上開始過濾數據。你也可以通過SO_LOCK_FILTER來鎖住你attach到socket上的filter。

BPF最大的用戶可能是libpcap，執行一個高級別的過濾器命令行像tcpdump -i em1 port 22會通過libpcap內部的編譯器會生成BPF代碼通過SO_ATTACH_FILTER發往內核。

tcpdump可以以不同的形式來顯示生成的BPF代碼，下麵我將其man page列出來：

-d Dump the compiled packet-matching code in a human readable form to standard output and stop.

-d 選項會輸出人類可讀的包匹配代碼（即彙編形式的BPF代碼，下文中我將詳述）。

-dd Dump packet-matching code as a C program fragment.

-dd 選項輸出可用於C程式的包匹配代碼。

-ddd Dump packet-matching code as decimal numbers (preceded with a count).

-ddd 選項輸出十進位的包匹配代碼（最前面會輸出代碼的行數）

上面關於tcpdump的內容可能你還一時無法理解，可以暫時跳過。

儘管我們這裡僅僅講述了用於socket的BPF，但BPF已經用於Linux的很多方面，包括用於netfilter的xt_bpf（用於iptables），用於內核qdisc層的cls_bpf（用於tc，可參考tc-bpf [6]），SECCOMP-BPF (SECure COMPuting [7][8])，和其他許多地方，諸如team driver, PTP code等。

之後文中指出原始的BPF論文，即 Steven McCanne 和 Van Jacobson 於1993年寫的《The BSD packet filter: a new
architecture for user-level packet capture》[9]。

下麵我將講述原始論文中的重點部分：

文中提及最早的Unix filter evaluator是基於棧來設計的，而BPF則使用了基於寄存器的filter evaluator，並且使用了一種straightforward的buffering策略，這使得其在同樣的硬體上總體性能高於Sun的NIT的100倍。

論文中，呈現了BPF的設計，概述了其如何與系統的其餘部分進行交互，描繪了過濾機制的新方法，最後呈現了BPF、NIT、CSPF的性能度量，這顯示出BPF性能快於其他方式的原因。

論文的前半部分主要講述了新老包過濾器設計上的差異，以及BPF過濾器因為這些設計所帶來的性能上的巨大的提升。後文開始講述BPF過濾器偽機的設計。這是本文的重點內容。我將結合上文中的Linux文檔進行詳細講解。

BPF 偽機及其彙編指令

BPF偽機包括一個32位的累加器A，一個32位的索引寄存器X，一個16 x 32位的記憶體和一個隱含的程式計數器。

  Element          Description

  A                32 bit wide accumulator
  X                32 bit wide X register
  M[]              16 x 32 bit wide misc registers aka "scratch memory store", addressable from 0 to 15

在這些元素上的操作可以被分為下麵的類別：

LOAD 指令集拷貝一個值到A或X。
STORE 指令集拷貝A或X的值到記憶體。
ALU 指令集用X或常數作為操作數在累加器上執行算數或邏輯運算。
BRANCH 指令集根據常量或X與A的比較測試來改變控制流程。
RETURN 指令集終止過濾器並表明報文的哪一部分保留下來，如果返回0，報文全部被丟棄。
MISCELLANEOUS 指令集包含其他所有指令，當前是寄存器轉移指令集。

指令集為固定長度，格式如下：

|    opcode:16    |  jt:8  |  jf:8  |
|                k:32               |

其中的每一部分解釋如下：

opcode：操作碼，16位，指明瞭具體的指令及其定址模式。
jt："jump if true"，8位，用於條件跳轉指令，指明測試成功時從下一條指令到跳轉目標的偏移值。
jf："jump if false"，8位，用於條件跳轉指令，指明測試失敗時從下一條指令到跳轉目標的偏移值。
k：32位，K的含義依據不同的操作碼而不同。

下表展示了定義於<linux/filter.h>的操作碼及其定址方式：

  Instruction      Addressing mode      Description

  ld               1, 2, 3, 4, 10       Load word into A
  ldi              4                    Load word into A
  ldh              1, 2                 Load half-word into A
  ldb              1, 2                 Load byte into A
  ldx              3, 4, 5, 10          Load word into X
  ldxi             4                    Load word into X
  ldxb             5                    Load byte into X

  st               3                    Store A into M[]
  stx              3                    Store X into M[]

  jmp              6                    Jump to label
  ja               6                    Jump to label
  jeq              7, 8                 Jump on A == k
  jneq             8                    Jump on A != k
  jne              8                    Jump on A != k
  jlt              8                    Jump on A <  k
  jle              8                    Jump on A <= k
  jgt              7, 8                 Jump on A >  k
  jge              7, 8                 Jump on A >= k
  jset             7, 8                 Jump on A &  k

  add              0, 4                 A + <x>
  sub              0, 4                 A - <x>
  mul              0, 4                 A * <x>
  div              0, 4                 A / <x>
  mod              0, 4                 A % <x>
  neg                                   !A
  and              0, 4                 A & <x>
  or               0, 4                 A | <x>
  xor              0, 4                 A ^ <x>
  lsh              0, 4                 A << <x>
  rsh              0, 4                 A >> <x>

  tax                                   Copy A into X
  txa                                   Copy X into A

  ret              4, 9                 Return

下表展示了上表第二列的定址方式的具體細節：

  Addressing mode  Syntax               Description

   0               x/%x                 Register X
   1               [k]                  BHW at byte offset k in the packet
   2               [x + k]              BHW at the offset X + k in the packet
   3               M[k]                 Word at offset k in M[]
   4               #k                   Literal value stored in k
   5               4*([k]&0xf)          Lower nibble * 4 at byte offset k in the packet
   6               L                    Jump label L
   7               #k,Lt,Lf             Jump to Lt if true, otherwise jump to Lf
   8               #k,Lt                Jump to Lt if predicate is true
   9               a/%a                 Accumulator A
  10               extension            BPF extension

Linux內核有一些和load指令集一起使用的BPF擴展，它們通過“溢出”k的值為一個負的偏移值加一個特定的擴展偏移值來使用，這些BPF擴展的結果被保存到A中。可能的BPF擴展展示在下表：

  Extension                             Description

  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()

這些擴展可以以'#'為首碼。

下麵是Linux文檔中給出的BPF彙編代碼的例子：


** ARP packets:

  ldh [12]
  jne #0x806, drop
  ret #-1
  drop: ret #0

** IPv4 TCP packets:

  ldh [12]
  jne #0x800, drop
  ldb [23]
  jneq #6, drop
  ret #-1
  drop: ret #0

** (Accelerated) VLAN w/ id 10:

  ld vlan_tci
  jneq #10, drop
  ret #-1
  drop: ret #0

** icmp random packet sampling, 1 in 4
  ldh [12]
  jne #0x800, drop
  ldb [23]
  jneq #1, drop
  # get a random uint32 number
  ld rand
  mod #4
  jneq #1, drop
  ret #-1
  drop: ret #0

** SECCOMP filter example:

  ld [4]                  /* offsetof(struct seccomp_data, arch) */
  jne #0xc000003e, bad    /* AUDIT_ARCH_X86_64 */
  ld [0]                  /* offsetof(struct seccomp_data, nr) */
  jeq #15, good           /* __NR_rt_sigreturn */
  jeq #231, good          /* __NR_exit_group */
  jeq #60, good           /* __NR_exit */
  jeq #0, good            /* __NR_read */
  jeq #1, good            /* __NR_write */
  jeq #5, good            /* __NR_fstat */
  jeq #9, good            /* __NR_mmap */
  jeq #14, good           /* __NR_rt_sigprocmask */
  jeq #13, good           /* __NR_rt_sigaction */
  jeq #35, good           /* __NR_nanosleep */
  bad: ret #0             /* SECCOMP_RET_KILL_THREAD */
  good: ret #0x7fff0000   /* SECCOMP_RET_ALLOW */

上面的BPF彙編代碼可以被保存到一個文件中，然後通過bpfc[10]來生成netsniff-ng[11]、cls_bpf和tcpdump格式的代碼。

參考

[1] http://colobu.com/2017/09/22/golang-bcc-bpf-function-tracing/?from=timeline
[2] http://www.jianshu.com/p/f1781fc452f6
[3] http://www.brendangregg.com/blog/2017-01-31/golang-bcc-bpf-function-tracing.html
[4] https://openresty.org/posts/dynamic-tracing/
[5] https://www.kernel.org/doc/Documentation/networking/filter.txt
[6] http://man7.org/linux/man-pages/man8/tc-bpf.8.html
[7] https://www.kernel.org/doc/Documentation/userspace-api/seccomp_filter.rst
[8] http://man7.org/linux/man-pages/man2/seccomp.2.html
[9] http://www.tcpdump.org/papers/bpf-usenix93.pdf
[10] http://man7.org/linux/man-pages/man8/bpfc.8.html
[11] http://netsniff-ng.org/

BPF漫談

源起

BPF 初窺

BPF 偽機及其彙編指令

參考