[譯] Linux Socket Filtering (LSF, aka BPF)(KernelDoc,2021)

語言: CN / TW / HK

譯者序

本文翻譯自 2021 年 Linux 5.10 核心文件: Linux Socket Filtering aka Berkeley Packet Filter (BPF) , 文件原始碼見 Documentation/networking/filter.rst

Linux Socket Filtering (LSF) 是最初將 BSD 系統上的 資料包過濾技術 BPF(伯克利包過濾器)移植到 Linux 系統時使用的名稱,但後來大家還是更多稱呼其為 BPF。本文介紹了 Linux BPF 的一些 底層設計和實現 (包括 cBPF 和 eBPF),可作為 Cilium:BPF 和 XDP 參考指南(2021) 的很好補充,這兩篇可能是目前除了核心原始碼之外,學習 BPF 的最全/最好參考。 本文適合有一定 BPF 經驗的開發者閱讀,不適合初學者。

由於核心文件更新不是非常及時,文中部分內容已經與 5.10 程式碼對不上,因此(少量) 過時內容在翻譯時略去了。另外,為文中的大部分 BPF 彙編 / x86_64 彙編加了註釋, 並插入了一些 5.10 程式碼片段或連結,方便更深入理解。

由於譯者水平有限,本文不免存在遺漏或錯誤之處。如有疑問,請查閱原文。

以下是譯文。

  • ————————————————————————
  • ————————————————————————
    • 1.1 LSF (cBPF) 與 BSD BPF
    • 1.2 ATTACH / DETACH / LOCK 給定過濾器
    • 2.1 struct sock_filter
    • 2.2 struct sock_fprog
  • 3 cBPF 示例: libpcap 過濾 socket 流量
    • 3.1 setsockopt() 將位元組碼 attach 到 socket
    • 3.2 setsockopt() attach/detach/lock 時的引數
    • 3.3 libpcap 適用和不適用的場景
    • 4.1 bpf_asm :最小 BPF 彙編器(assembler)
    • 4.3 bpf_asm 實現的指令集
    • 4.4 12 種指令定址模式
    • 4.5 Linux BPF extensions(Linux BPF 擴充套件)
    • 4.6 cBPF 彙編示例若干(附程式碼解讀)
    • 4.7 用 bps_asm 編譯成位元組碼
    • 5.1 核心配置項: bpf_jit_enable
    • 5.2 工具: bpf_jit_disasm
  • ————————————————————————
  • ————————————————————————
  • 6 BPF kernel internals(eBPF)
    • 6.2 cBPF->eBPF 自動轉換
    • 6.3 eBPF 相比 cBPF 的核心變化
      • 6.3.1 暫存器數量從 2 個增加到 10 個
      • 6.3.2 暫存器位寬從 32bit 擴充套件到 64bit
      • 6.3.3 條件跳轉: jt/fall-through 取代 jt/jf
      • 6.3.4 引入 bpf_call 指令和暫存器傳參約定,實現零(額外)開銷核心函式呼叫
        • 原理:JIT 實現零(額外)開銷核心函式呼叫
        • 示例解析(一):eBPF/C 函式混合呼叫,JIT 生成的 x86_64 指令
        • eBPF 暫存器到 x86_64 硬體暫存器一一對映關係
        • 示例解析(二):C 調 eBPF 程式碼編譯成 x86_64 彙編後的樣子
    • 6.4 eBPF 程式最大指令數限制
    • 6.5 eBPF 程式上下文(ctx)引數
    • 6.6 cBPF -> eBPF 轉換若干問題
  • 7 eBPF 位元組碼編碼(opcode encoding)
      • BPF_ALU 和 BPF_JMP 的 operand
      • BPF_ALU 和 BPF_ALU64 (eBPF) 的 opcode
      • BPF_JMP 和 BPF_JMP32 (eBPF) 的 opcode
      • BPF_MISC 與 BPF_ALU64(eBPF 64bit 暫存器加法操作)
      • cBPF/eBPF BPF_RET 指令的不同
      • BPF_JMP 與 eBPF BPF_JMP32
    • 7.2 載入指令(load/store)
      • 兩個 eBPF non-generic 指令:BPF_ABS 和 BPF_IND,用於訪問 skb data
      • 通用 eBPF load/store 指令
      • 載入 64bit 立即數的 eBPF 指令
  • 8 eBPF 校驗器(eBPF verifier)
  • 9 暫存器值跟蹤(register value tracking)
    • 9.2 指標偏移(offset)觸發暫存器狀態更新
    • 9.3 條件分支觸發暫存器狀態更新
    • 9.4 有符號比較觸發暫存器狀態更新
    • 9.5 struct bpf_reg_stateid 欄位
  • 10 直接資料包訪問(direct packet access)
  • 13 理解 eBPF 校驗器提示資訊
    • 13.1 程式包含無法執行到的指令
    • 13.2 程式讀取未初始化的暫存器
    • 13.3 程式退出前未設定 R0 暫存器
    • 13.4 程式訪問超出棧空間
    • 13.5 未初始化棧內元素,就傳遞該棧地址
    • 13.6 程式執行 map_lookup_elem() 傳遞了非法的 map_fd
    • 13.7 程式未檢查 map_lookup_elem() 的返回值是否為空就開始使用
    • 13.8 程式訪問 map 內容時使用了錯誤的位元組對齊
    • 13.9 程式在 fallthrough 分支中使用了錯誤的位元組對齊訪問 map 資料
    • 13.10 程式執行 sk_lookup_tcp() ,未檢查返回值就直接將其置 NULL
    • 13.11 程式執行 sk_lookup_tcp() 但未檢查返回值是否為空
SPDX-License-Identifier: GPL-2.0

————————————————————————

cBPF 相關內容

————————————————————————

1 cBPF 引言

Linux Socket Filtering (LSF) 從 Berkeley Packet Filter(BPF) 衍生而來 。 雖然 BSD 和 Linux Kernel filtering 有一些重要不同,但 在 Linux 語境中提到 BPF 或 LSF 時 , 我們指的是 Linux 核心中的同一套 過濾機制

1.1 LSF (cBPF) 與 BSD BPF

BPF 允許使用者空間程式 向任意 socket attach 過濾器(filter) , 以此 對流經 socket 的資料進行控制 (放行或拒絕)。 LSF 完全遵循了 BSD BPF 的過濾程式碼結構(filter code structure),因此實現過濾器 (filters)時,BSD bpf.4 manpage 是很好的參考文件。

但 Linux BPF 要比 BSD BPF 簡單很多:

SO_ATTACH_FILTER

1.2 ATTACH / DETACH / LOCK 給定過濾器

  • SO_ATTACH_FILTER 用於將 filter attach 到 socket。

  • SO_DETACH_FILTER 用於從 socket 中 detach 過濾器。

    但這種情況可能比較少,因為關閉一個 socket 時,attach 在上面的所有 filters 會被 自動刪除 。 另一個不太常見的場景是:向一個已經有 filter 的 socket 再 attach 一個 filter: 核心負責將老的移除,替換成新的 —— 只要新的過濾器通過了校驗,否則還是老的在工作。

  • SO_LOCK_FILTER 選項支援將 attach 到 socket 上的 filter 鎖定 。 一旦鎖定之後,這個過濾器就 不能被刪除或修改 了。這樣就能保證下列操作之後:

    1. 程序建立 socket
    2. attach filter
    3. 鎖定 filter
    4. drop privileges

    這個 filter 就會一直執行在該 socket 上,直到後者被關閉。

1.3 LSF/BPF 使用場景

BPF 模組的 最大使用者 可能就是 libpcap 。例如,對於高層過濾命令 tcpdump -i em1 port 22

  • libpcap 編譯器 能將其編譯生成一個 cBPF 程式,然後通過前面介紹的 SO_ATTACH_FILTER 就能載入到核心;
  • -ddd 引數,可以 dump 這條命令對應的位元組碼 tcpdump -i em1 port 22 -ddd

雖然我們這裡討論的都是 socket,但 Linux 中 BPF 還可用於很多其他場景 。例如

  • netfilter 中的 xt_bpf
  • 核心 qdisc 層的 cls_bpf
  • SECCOMP-BPF ( SECure COMPuting )
  • 其他很多地方,包括 team driver、PTP。

1.4 cBPF 經典論文

最初的 BPF 論文:

Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new architecture for user-level packet capture . In Proceedings of the USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 Conference Proceedings (USENIX’93). USENIX Association, Berkeley, CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]

2 cBPF 資料結構

2.1 struct sock_filter

要開發 cBPF 應用,使用者空間程式需要 include <linux/filter.h> ,其中定義了下面的結構體:

struct sock_filter { /* Filter block */
    __u16    code;   /* Actual filter code */
    __u8    jt;      /* Jump true */
    __u8    jf;      /* Jump false */
    __u32    k;      /* Generic multiuse field */
};

這個結構體包含 code jt jf k 四個欄位。 jtjf 是 jump offset, k 是一個 code 可以使用的通用欄位。

2.2 struct sock_fprog

要實現 socket filtering,需要通過 setsockopt(2) 將一個 struct sock_fprog 指標傳遞給核心(後面有例子)。 這個結構體的定義:

struct sock_fprog {                /* Required for SO_ATTACH_FILTER. */
    unsigned short           len;  /* Number of filter blocks */
    struct sock_filter __user *filter;
};

3 cBPF 示例: libpcap 過濾 socket 流量

3.1 setsockopt() 將位元組碼 attach 到 socket

裡面用到的兩個結構體 struct sock_filterstruct sock_fprog 在前一節介紹過了:

#include <sys/socket.h>
#include <sys/types.h>
#include <arpa/inet.h>
#include <linux/if_ether.h>
/* ... */

/* From the example above: tcpdump -i em1 port 22 -dd */
struct sock_filter code[] = {
    { 0x28,  0,  0, 0x0000000c },
    { 0x15,  0,  8, 0x000086dd },
    { 0x30,  0,  0, 0x00000014 },
    { 0x15,  2,  0, 0x00000084 },
    { 0x15,  1,  0, 0x00000006 },
    { 0x15,  0, 17, 0x00000011 },
    { 0x28,  0,  0, 0x00000036 },
    { 0x15, 14,  0, 0x00000016 },
    { 0x28,  0,  0, 0x00000038 },
    { 0x15, 12, 13, 0x00000016 },
    { 0x15,  0, 12, 0x00000800 },
    { 0x30,  0,  0, 0x00000017 },
    { 0x15,  2,  0, 0x00000084 },
    { 0x15,  1,  0, 0x00000006 },
    { 0x15,  0,  8, 0x00000011 },
    { 0x28,  0,  0, 0x00000014 },
    { 0x45,  6,  0, 0x00001fff },
    { 0xb1,  0,  0, 0x0000000e },
    { 0x48,  0,  0, 0x0000000e },
    { 0x15,  2,  0, 0x00000016 },
    { 0x48,  0,  0, 0x00000010 },
    { 0x15,  0,  1, 0x00000016 },
    { 0x06,  0,  0, 0x0000ffff },
    { 0x06,  0,  0, 0x00000000 },
};

struct sock_fprog bpf = {
    .len = ARRAY_SIZE(code),
    .filter = code,
};

sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
if (sock < 0)
    /* ... bail out ... */

ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
if (ret < 0)
    /* ... bail out ... */

/* ... */
close(sock);

以上程式碼將一個 filter attach 到了一個 PF_PACKET 型別的 socket,filter 的功能是 放行所有 IPv4/IPv6 22 埠的包,其他包一律丟棄

以上只展示了 attach 程式碼;detach 時, setsockopt(2) 除了 SO_DETACH_FILTER 不需要其他引數; SO_LOCK_FILTER 可用於防止 filter 被 detach,需要帶一個整形引數 0 或 1。

注意 socket filters 並不是只能用於 PF_PACKET 型別的 socket,也可以用於其他 socket 家族。

3.2 setsockopt() attach/detach/lock 時的引數

總結前面用到的幾次系統呼叫:

  • setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
  • setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
  • setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &val, sizeof(val));

3.3 libpcap 適用和不適用的場景

lipcap 高層語法 封裝了上面程式碼中看到的那些底層操作, 功能已經 覆蓋了大部分 socket filtering 的場景 , 因此如果想開發流量過濾應用,開發者應該首選基於 libpcap。

除非遇到以下情況 ,否則不要純手工編寫過濾器:

  1. 開發環境比較特殊,無法使用或連結 libpcap;
  2. 使用的 filter 需要用到 libpcap 編譯器還沒有支援的 Linux extensions;
  3. 開發的 filter 比較複雜,libpcap 編譯器無法很好地支援該 filter;
  4. 需要對特定的 filter 程式碼做優化,而不想使用 libpcap 編譯器生成的程式碼;

libpcap 不適用的場景舉例:

  1. xt_bpf 和 cls_bpf 使用者 可能需要更加複雜的 filter 程式碼, libpcap 無法很好地表達。
  2. BPF JIT 開發者可能希望 手寫測試用例 ,因此也需要直接編寫或修改 BPF 程式碼。

4 cBPF 引擎和指令集

4.1 bpf_asm :最小 BPF 彙編器(assembler)

核心 tools/bpf/ 目錄下有個小工具 bpf_asm ,能用它來 編寫 low-level filters , 例如前面提到的一些 libpcap 不適用的場景。

BPF 語法類似彙編,在 bpf_asm 已經中實現了,接下來還會用這種彙編解釋其他一些程式 (而不是直接使用難懂的 opcodes,二者的原理是一樣的)。這種彙編語法非常接近 Steven McCanne’s and Van Jacobson’s BPF paper 中的建模。

4.2 cBPF 架構

cBPF 架構由如下幾個基本部分組成:

=======          ====================================================
Element          Description
=======          ====================================================
A                32 bit wide accumulator(32bit 位寬的累加器)
X                32 bit wide X register (32bit 位寬 X 暫存器)
M[]              16 x 32 bit wide misc registers aka "scratch memory store", addressable from 0 to 15
                 (16x32bit 陣列,陣列索引 0~15,可存放任意內容)
=======          ====================================================

BPF 程式經過 bpf_asm 處理之後 變成一個 struct sock_filter 型別的陣列 (這個結構體前面介紹過),因此陣列中的每個元素都是 以如下格式編碼 的:

op:16, jt:8, jf:8, k:32
  • op :16bit opcode,其中包括了特定的指令;
  • jt :jump if true
  • jf :jump if false
  • k :多功能欄位, 存放的什麼內容,根據 op 型別來解釋

4.3 bpf_asm 實現的指令集

指令集包括 load、store、branch、alu、return 等指令,bpf_asm 語言中 實現了這些指令 。 下面的表格列出了 bpf_asm 中具體包括的指令,對應的 opcode 定義在 linux/filter.h

===========      ===================  =====================
指令             定址模式              解釋
===========      ===================  =====================
ld               1, 2, 3, 4, 12       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, 12          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, 9, 10          Jump on A == <x>
jneq             9, 10                Jump on A != <x>
jne              9, 10                Jump on A != <x>
jlt              9, 10                Jump on A <  <x>
jle              9, 10                Jump on A <= <x>
jgt              7, 8, 9, 10          Jump on A >  <x>
jge              7, 8, 9, 10          Jump on A >= <x>
jset             7, 8, 9, 10          Jump on A &  <x>

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, 11                Return
===========      ===================  =====================

其中第二列是尋找模式,定義見下面。

4.4 12 種指令定址模式

定址模式的定義如下:

===============  ===================  ===============================================
定址模式         語法                 解釋
===============  ===================  ===============================================
 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               x/%x,Lt,Lf           Jump to Lt if true, otherwise jump to Lf
 9               #k,Lt                Jump to Lt if predicate is true
10               x/%x,Lt              Jump to Lt if predicate is true
11               a/%a                 Accumulator A
12               extension            BPF extension
===============  ===================  ===============================================

注意最後一種: BPF extensions ,這是 Linux 對 BPF 的擴充套件,下一節詳細介紹。

4.5 Linux BPF extensions(Linux BPF 擴充套件)

除了常規的一些 load 指令,Linux 核心還有一些 BPF extensions,它們用一個 負 offset 加上一個特殊的 extension offset 來 “overloading” k 欄位 , 然後將這個 結果載入到暫存器 A 中

===================================   =================================================
Extension                             描述(實際對應的結構體欄位或值)
===================================   =================================================
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()
===================================   =================================================

這些擴充套件也可以加上 # 字首。

以上提到的負 offset 和具體 extension 的 offset,定義見 include/uapi/linux/filter.h

/* RATIONALE. Negative offsets are invalid in BPF.
   We use them to reference ancillary data.
   Unlike introduction new instructions, it does not break
   existing compilers/optimizers.
 */
#define SKF_AD_OFF    (-0x1000)
#define SKF_AD_PROTOCOL 0
#define SKF_AD_PKTTYPE     4
#define SKF_AD_IFINDEX     8
#define SKF_AD_NLATTR    12
#define SKF_AD_NLATTR_NEST    16
#define SKF_AD_MARK     20
#define SKF_AD_QUEUE    24
#define SKF_AD_HATYPE    28
#define SKF_AD_RXHASH    32
#define SKF_AD_CPU    36
#define SKF_AD_ALU_XOR_X    40
#define SKF_AD_VLAN_TAG    44
#define SKF_AD_VLAN_TAG_PRESENT 48
#define SKF_AD_PAY_OFFSET    52
#define SKF_AD_RANDOM    56
#define SKF_AD_VLAN_TPID    60
#define SKF_AD_MAX    64

#define SKF_NET_OFF    (-0x100000)
#define SKF_LL_OFF    (-0x200000)

#define BPF_NET_OFF    SKF_NET_OFF
#define BPF_LL_OFF    SKF_LL_OFF

kernel/bpf/core.c 等地方使用:

/* No hurry in this branch
 *
 * Exported for the bpf jit load helper.
 */
void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)
{
    u8 *ptr = NULL;

    if (k >= SKF_NET_OFF)
        ptr = skb_network_header(skb) + k - SKF_NET_OFF;
    else if (k >= SKF_LL_OFF)
        ptr = skb_mac_header(skb) + k - SKF_LL_OFF;

    if (ptr >= skb->head && ptr + size <= skb_tail_pointer(skb))
        return ptr;

    return NULL;
}

Cilium:BPF 和 XDP 參考指南(2021) 中對此亦有提及。

譯註。

4.6 cBPF 彙編示例若干(附程式碼解讀)

過濾 ARP 包:

ldh [12]          ; 將 skb 第 12,13 兩個位元組(h 表示 half word,兩個位元組,即 skb->protocol 欄位)載入到暫存器 A
jne #0x806, drop  ; 如果暫存器 A 中的值不等於 0x0806(ARP 協議),則跳轉到 drop
ret #-1           ; (能執行到這一行,說明是 ARP 包),返回 -1
drop: ret #0      ; 返回 0

過濾 IPv4 TCP 包:

ldh [12]          ; 將 skb 第 12,13 兩個位元組(h 表示 half word,兩個位元組,即 skb->protocol 欄位)載入到暫存器 A
jne #0x800, drop  ; 如果暫存器 A 中的值不等於 0x0800(IPv4 協議),則跳轉到 drop
ldb [23]          ; 將 skb 第 23 位元組(b 表示 byte,一個位元組,即 ipv4_hdr->protocol 欄位)載入到暫存器 A
jneq #6, drop     ; 如果暫存器 A 中的值不等於 6(TCP 協議),則跳轉到 drop
ret #-1           ; (能執行到這一行,說明是 TCP 包),返回 -1
drop: ret #0      ; 返回 0

過濾 VLAN ID 等於 10 的包:

ld vlan_tci       ; 根據前面介紹的 BPF extensions,這會轉換成 skb_vlan_tag_get(skb)
jneq #10, drop    ; 如果暫存器 A 中的值不等於 10,則跳轉到 drop
ret #-1           ; (能執行到這一行說明 VLAN ID 等於 10),返回 -1
drop: ret #0      ; 返回 0

對 ICMP 包隨機採集,取樣頻率 1/4:

ldh [12]          ; 將 skb 第 12,13 兩個位元組(h 表示 half word,兩個位元組,即 skb->protocol 欄位)載入到暫存器 A
jne #0x800, drop  ; 如果暫存器 A 中的值不等於 0x0800(IPv4 協議),則跳轉到 drop
ldb [23]          ; 將 skb 第 23 位元組(b 表示 byte,一個位元組,即 ipv4_hdr->protocol 欄位)載入到暫存器 A
jneq #1, drop     ; 如果暫存器 A 中的值不等於 1(ICMP 協議),則跳轉到 drop
ld rand           ; 獲取一個 u32 型別的隨機數,存入暫存器 A
mod #4            ; 將暫存器 A 中的值原地對 4 取模(結果仍然存入 A)
jneq #1, drop     ; 如果 A 中的值(即取模的結果)不等於 1,跳轉到 drop
ret #-1           ; (能執行到這裡說明對 4 取模等於 1),返回 -1
drop: ret #0      ; 返回 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 */

4.7 用 bps_asm 編譯成位元組碼

以上程式碼片段都可以放到檔案中(下面用 foo 表示),然後用 bpf_asm 來生成 opcodes, 後者是可以被 xt_bpf 和 cls_bpf 理解的格式,能直接載入。以上面的 ARP 程式碼為例:

$ ./bpf_asm foo
4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,

也可以輸出成更容易複製貼上的與 C 類似的格式:

$ ./bpf_asm -c foo
{ 0x28,  0,  0, 0x0000000c },
{ 0x15,  0,  1, 0x00000806 },
{ 0x06,  0,  0, 0xffffffff },
{ 0x06,  0,  0, 0000000000 },

4.8 除錯

xt_bpf 和 cls_bpf 場景中可能會用到非常複雜的 BPF 過濾器,不像上面的程式碼一眼就能看懂。 因此在將這些複雜程式(過濾器)直接 attach 到真實系統之前,最好先線上下測試一遍。

bpf_dbg 就是用於這一目的的小工具,位於核心原始碼 tools/bpf/ 中。它可以測試 BPF filters,輸入是 pcap 檔案,支援單步執行、列印 BPF 虛擬機器的暫存器狀態等等。

# 使用預設 stdin/stdout
$ ./bpf_dbg

# 指定輸入輸出
$ ./bpf_dbg test_in.txt test_out.txt

此外,還支援:

~/.bpf_dbg_init
~/.bpf_dbg_history

load 命令

載入 bpf_asm 標準輸出檔案 ,或 tcpdump -ddd 輸出檔案 (例如 tcpdump -iem1 -ddd port 22 | tr '\n' ',' 的輸出):

> load bpf 6,40 0 0 12,21 0 3 2048,48 0 0 23,21 0 1 1,6 0 0 65535,6 0 0 0

注意:對於 JIT debugging(後面介紹),以上命令會 建立一個臨時 socket , 然後將 BPF 程式碼載入到核心。因此這對 JIT 開發者也有幫助。

載入標準 tcpdump pcap 檔案:

> load pcap foo.pcap

run 命令

對 pcap 內的前 n 個包執行過濾器:

> run [<n>]
bpf passes:1 fails:9

列印的是命中和未命中過濾規則的包數。

disassemble 命令

反彙編:

> disassemble
l0:    ldh [12]
l1:    jeq #0x800, l2, l5
l2:    ldb [23]
l3:    jeq #0x1, l4, l5
l4:    ret #0xffff
l5:    ret #0

dump 命令

以 C 風格列印 BPF 程式碼:

$ dump
/* { op, jt, jf, k }, */
{ 0x28,  0,  0, 0x0000000c },
{ 0x15,  0,  3, 0x00000800 },
{ 0x30,  0,  0, 0x00000017 },
{ 0x15,  0,  1, 0x00000001 },
{ 0x06,  0,  0, 0x0000ffff },
{ 0x06,  0,  0, 0000000000 },

breakpoint 命令

> breakpoint 0
breakpoint at: l0:    ldh [12]

> breakpoint 1
breakpoint at: l1:    jeq #0x800, l2, l5

run 命令

在特定指令設定斷點之後,執行 run

> run

-- register dump --
pc:       [0]                       <-- program counter
code:     [40] jt[0] jf[0] k[12]    <-- plain BPF code of current instruction
curr:     l0:    ldh [12]           <-- disassembly of current instruction
A:        [00000000][0]             <-- content of A (hex, decimal)
X:        [00000000][0]             <-- content of X (hex, decimal)
M[0,15]:  [00000000][0]             <-- folded content of M (hex, decimal)
-- packet dump --                   <-- Current packet from pcap (hex)
len: 42
    0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
32: 00 00 00 00 00 00 0a 3b 01 01
(breakpoint)

> breakpoint # 列印斷點
breakpoints: 0 1

step 命令

從當前 pc offset 開始,單步執行:

> step [-<n>, +<n>]

每執行一步,就會像 run 輸出一樣 dump 暫存器狀態。

注意這裡可以單步前進,也可以單步後退。

select 命令

選擇從第 n 個包開始執行:

> select <n> # 接下來執行 run 或 step 命令

注意與 Wireshark 一樣,n 是從 1 開始的。

quit 命令

> quit

退出 bpf_dbg。

5 cBPF JIT 編譯器

Linux 核心內建了一個 BPF JIT 編譯器,支援 x86_64、SPARC、PowerPC、ARM、ARM64、MIPS、 RISC-V 和 s390,編譯核心時需要開啟 CONFIG_BPF_JIT

5.1 核心配置項: bpf_jit_enable

啟用 JIT 編譯器:

$ echo 1 > /proc/sys/net/core/bpf_jit_enable

如果想每次編譯過濾器時,都將生成的 opcode 映象都 列印到核心日誌中 ,可以配置:

$ echo 2 > /proc/sys/net/core/bpf_jit_enable

這對 JIT 開發者和審計來說比較有用。下面是 dmesg 的輸出:

[ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
[ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
[ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
[ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
[ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
[ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3

如果在編譯時設定了 CONFIG_BPF_JIT_ALWAYS_ON bpf_jit_enable 就會 永久性設為 1 ,再設定成其他值時會報錯 —— 包括將其設為 2 時,因為 並不推薦將最終的 JIT 映象列印到核心日誌 ,通常推薦開發者通過 bpftool tools/bpf/bpftool/ 來檢視映象內容。

5.2 工具: bpf_jit_disasm

在核心 tools/bpf/ 目錄下還有一個 bpf_jit_disasm 工具,用於生成 反彙編 (disassembly),

$ ./bpf_jit_disasm
70 bytes emitted from JIT compiler (pass:3, flen:6)
ffffffffa0069c8f + <x>:
0:     push   %rbp                 ; 這些已經是 eBPF 指令而非 cBPF 指令,後面章節會詳細介紹
1:     mov    %rsp,%rbp
4:     sub    $0x60,%rsp
8:     mov    %rbx,-0x8(%rbp)
c:     mov    0x68(%rdi),%r9d
10:    sub    0x6c(%rdi),%r9d
14:    mov    0xd8(%rdi),%r8
1b:    mov    $0xc,%esi
20:    callq  0xffffffffe0ff9442
25:    cmp    $0x800,%eax
2a:    jne    0x0000000000000042
2c:    mov    $0x17,%esi
31:    callq  0xffffffffe0ff945e
36:    cmp    $0x1,%eax
39:    jne    0x0000000000000042
3b:    mov    $0xffff,%eax
40:    jmp    0x0000000000000044
42:    xor    %eax,%eax
44:    leaveq
45:    retq

-o 引數可以 對照列印位元組碼和相應的彙編指令 ,對 JIT 開發者非常有用:

# ./bpf_jit_disasm -o
70 bytes emitted from JIT compiler (pass:3, flen:6)
ffffffffa0069c8f + <x>:
0:    push   %rbp
      55
1:    mov    %rsp,%rbp
      48 89 e5
4:    sub    $0x60,%rsp
      48 83 ec 60
8:    mov    %rbx,-0x8(%rbp)
      48 89 5d f8
c:    mov    0x68(%rdi),%r9d
      44 8b 4f 68
10:   sub    0x6c(%rdi),%r9d
      44 2b 4f 6c
14:   mov    0xd8(%rdi),%r8
      4c 8b 87 d8 00 00 00
1b:   mov    $0xc,%esi
      be 0c 00 00 00
20:   callq  0xffffffffe0ff9442
      e8 1d 94 ff e0
25:   cmp    $0x800,%eax
      3d 00 08 00 00
2a:   jne    0x0000000000000042
      75 16
2c:   mov    $0x17,%esi
      be 17 00 00 00
31:   callq  0xffffffffe0ff945e
      e8 28 94 ff e0
36:   cmp    $0x1,%eax
      83 f8 01
39:   jne    0x0000000000000042
      75 07
3b:   mov    $0xffff,%eax
      b8 ff ff 00 00
40:   jmp    0x0000000000000044
      eb 02
42:   xor    %eax,%eax
      31 c0
44:   leaveq
      c9
45:   retq
      c3

5.3 JIT 開發者工具箱

對 JIT 開發者來說,我們已經介紹的這幾個工具:

  • bpf_jit_disasm
  • bpf_asm
  • bpf_dbg

都是非常有用的。

————————————————————————

eBPF 相關內容

————————————————————————

6 BPF kernel internals(eBPF)

在核心內部,直譯器(the kernel interpreter)使用的是與 cBPF 類似、但屬於 另一種指令集的格式 。 這種指令集格式的參考處理器原生指令集建模,因此 更接近底層處理器架構 , 效能更好(後面會詳細介紹)。

這種 新的指令集稱為 “eBPF” ,也叫 “internal BPF”。

注意:eBPF 這個名字源自 [e]xtended BPF (直譯為“擴充套件的 BPF”), 它與 BPF extensions (直譯為 “BPF 擴充套件”,見前面章節)並不是一個概念!

  • eBPF 是一種 指令集架構(ISA)
  • BPF extensions 是早年 cBPF 中對 BPF_LD | BPF_{B,H,W} | BPF_ABS 幾個指令 進行 overloading 的技術

6.1 eBPF 設計考慮

  • 力求 JIT 編譯時,能將 eBPF 指令一一對映到原生指令 , 這種設計也給 GCC/LLVM 等編譯器打開了方便之門,因為它們可以通過各自的 eBPF 後端生成優化的、與原生編譯之後的程式碼幾乎一樣快 的 eBPF 程式碼。
  • 最初設計時,目標是能用 “受限的 C 語言” 來編寫程式,然後 通過可選的 GCC/LLVM 後端編譯成 eBPF,因此它能以兩步最小的效能開銷,即時對映成 現代 64 位 CPU 指令,即 C -> eBPF -> native code

6.2 cBPF->eBPF 自動轉換

下列 cBPF 的經典使用場景中:

  • seccomp BPF
  • classic socket filters
  • cls_bpf traffic classifier
  • team driver’s classifier for its load-balancing mode
  • netfilter’s xt_bpf extension
  • PTP dissector/classifier
  • and much more.

cBPF 已經在核心中被 透明地轉換成了 eBPF,然後在 eBPF 直譯器中執行

在 in-kernel handlers 中,可以使用下面的函式:

bpf_prog_create()
bpf_prog_destroy()

BPF_PROG_RUN(filter, ctx) 執行過濾程式碼,它或者 透明地 觸發 eBPF 直譯器執行 ,或者 執行 JIT 編譯之後的程式碼

  • filterbpf_prog_create() 的返回值,型別是 struct bpf_prog * 型別;
  • ctx 是程式上下文(例如 skb 指標)。

在轉換成新指令之前,會通過 bpf_check_classic() 檢查 cBPF 程式是否有問題。

當前,在大部分 32 位架構上,都是用 cBPF 格式做 JIT 編譯; 而在 x86-64, aarch64, s390x, powerpc64, sparc64, arm32, riscv64, riscv32 架構上,直接從 eBPF 指令集執行 JIT 編譯。

6.3 eBPF 相比 cBPF 的核心變化

6.3.1 暫存器數量從 2 個增加到 10 個

  • 老格式(cBPF)只有兩個暫存器 A 和 X,以及一個隱藏的棧指標(frame pointer)。
  • 新格式(eBPF)擴充套件到了 10 個內部暫存器,以及一個只讀的棧指標。

傳參暫存器數量

由於 64 位 CPU 都是 通過暫存器傳遞函式引數 的,因此從 eBPF 程式 傳給核心函式(in-kernel function)的 引數數量限制到 5 個 ,另有 一個暫存器用來接收核心函式的返回值,

考慮到具體的處理器架構,

x86_64

eBPF 呼叫約定

因此, eBPF 呼叫約定 (calling convention)定義如下:

  • R0 - return value from in-kernel function, and exit value for eBPF program
  • R1 - R5 - arguments from eBPF program to in-kernel function
  • R6 - R9 - callee saved registers that in-kernel function will preserve
  • R10 - read-only frame pointer to access stack

這樣的設計,使 所有的 eBPF 暫存器都能一一對映到 x86_64、aarch64 等架構上的 硬體暫存器 ,eBPF 呼叫約定也直接對映到 64 位的核心 ABI。

在 32 位架構上,JIT 只能編譯那些只使用了 32bit 算術操作的程式,其他更復雜的程式,交給直譯器來執行。

6.3.2 暫存器位寬從 32bit 擴充套件到 64bit

原來的 32bit ALU 操作仍然是支援的,通過 32bit 子暫存器執行。 所有 eBPF 暫存器都是 64bit 的,如果對 32bit 子暫存器有寫入操作,它會被 zero-extend 成 64bit。 這種行為能直接對映到 x86_64 和 arm64 子暫存器的定義,但對其他處理器架構來說,JIT 會更加困難。

32-bit 的處理器架構上,通過直譯器執行 64-bit 的 eBPF 程式。這種平臺上的 JIT 編譯器 只能編譯那些只使用了 32bit 子暫存器的程式,其他不能編譯的程式,通過直譯器執行。

eBPF 操作都是 64 位的,原因:

  1. 64 位處理器架構上指標也是 64 位的,我們希望與核心函式互動時,輸入輸出的都是 64 位值。如果使用 32 位 eBPF 暫存器,就需要定義 register-pair ABI,導致無法 直接將 eBPF 暫存器對映到物理暫存器,JIT 就必須為與函式呼叫相關的每個暫存器承 擔 拼裝/拆分/移動 等等操作,不僅複雜,而且很容易產生 bug,效率也很低。

  2. 另一個原因是 eBPF 使用了 64 位的原子計數器(atomic 64-bit counters)。

6.3.3 條件跳轉: jt/fall-through 取代 jt/jf

cBPF 的設計中有條件判斷:

if (cond)
    jump_true;
else
    jump_false;

現在被下面的結構取代了:

if (cond)
    jump_true;

/* else fall-through */

6.3.4 引入 bpf_call 指令和暫存器傳參約定,實現零(額外)開銷核心函式呼叫

引入的暫存器傳參約定,能實現 零開銷核心函式呼叫(zero overhead calls from/to other kernel functions)。

在呼叫核心函式之前,eBPF 程式需要按照呼叫約定,將引數依次放到 R1-R5 暫存器; 然後直譯器會從這些暫存器讀取引數,傳遞給核心函式。

原理:JIT 實現零(額外)開銷核心函式呼叫

如果 R1-R5 能一一對映到處理器上的暫存器,JIT 編譯器就 無需 emit 任何額外的指令

  • 函式 引數已經在(硬體處理器)期望的位置
  • 只需要將 eBPF BPF_CALL JIT 編譯成一條處理器原生的 call 指令 就行了。
  • 這種 無效能損失的呼叫約定 設計,足以覆蓋大部分場景。

函式呼叫結束後,R1-R5 會被重置為不可讀狀態(unreadable),函式返回值存放在 R0。 R6-R9 是被呼叫方(callee)儲存的,因此函式呼叫結束后里面的值是可讀的。

示例解析(一):eBPF/C 函式混合呼叫,JIT 生成的 x86_64 指令

考慮下面的三個 C 函式:

u64 f1() { return (*_f2)(1); }
u64 f2(u64 a) { return f3(a + 1, a); }
u64 f3(u64 a, u64 b) { return a - b; }

GCC 能將 f1 和 f3 編譯成 x86_64:

f1:
movl $1, %edi         ; 將常量 1 載入到 edi 暫存器
movq _f2(%rip), %rax  ; 將 _f2 地址載入到 rax 暫存器
jmp  *%rax            ; 跳轉到 rax 暫存器中指定的地址(即函式 _f2 的起始地址)

f3:
movq %rdi, %rax       ; 將暫存器 rdi 中的值載入到暫存器 rax
subq %rsi, %rax       ; 將暫存器 rax 中的值減去暫存器 rsi 中的值(即 a-b)
ret                   ; 返回

f2 的 eBPF 程式碼可能如下:

f2:
bpf_mov R2, R1          ; 即 R2 = a
bpf_add R1, 1           ; 即 R1 = a + 1
bpf_call f3             ; 呼叫 f3,傳遞給 f3 的兩個引數分別在 R1 和 R2 中
bpf_exit                ; 退出
  • 如果 f2 是 JIT 編譯的 ,函式地址儲存為變數 _f2 ,那呼叫鏈 f1 -> f2 -> f3 及返回就都是連續的。
  • 如果 沒有 JIT ,就需要 呼叫直譯器 __bpf_prog_run() 來呼叫執行 f2。

出於一些實際考慮,

  1. 所有 eBPF 程式都只有一個引數 ctx ,放在 R1 暫存器中 ,例如 __bpf_prog_run(ctx)
  2. 函式呼叫最多支援傳遞 5 個引數,但如果將來有需要,這個限制也可以進一步放寬。

eBPF 暫存器到 x86_64 硬體暫存器一一對映關係

在 64 位架構上,所有暫存器都能一一對映到硬體暫存器。例如,由於 x86_64 ABI 硬性規定

  1. rdi、rsi、rdx、rcx、r8 、 r9 暫存器作為引數傳遞;
  2. rbx ,以及 r12 - r15 由被呼叫方(callee)儲存;

因此 x86_64 編譯會做如下對映:

R0 -> rax

R1 -> rdi  ; 傳參,呼叫方(caller)儲存
R2 -> rsi  ; 傳參,呼叫方(caller)儲存
R3 -> rdx  ; 傳參,呼叫方(caller)儲存
R4 -> rcx  ; 傳參,呼叫方(caller)儲存
R5 -> r8   ; 傳參,呼叫方(caller)儲存

R6 -> rbx  ; 被呼叫方(callee)儲存
R7 -> r13  ; 被呼叫方(callee)儲存
R8 -> r14  ; 被呼叫方(callee)儲存
R9 -> r15  ; 被呼叫方(callee)儲存
R10 -> rbp ; 被呼叫方(callee)儲存
...

示例解析(二):C 調 eBPF 程式碼編譯成 x86_64 彙編後的樣子

根據上面的對映關係,下面的 BPF 程式:

// BPF 指令格式:
// <指令>  <目的暫存器>  <源暫存器/常量>

bpf_mov  R6, R1 ; 將 ctx 儲存到 R6
bpf_mov  R2, 2  ; 將常量 2(即將呼叫的函式 foo() 的引數)載入到 R2 暫存器
bpf_mov  R3, 3
bpf_mov  R4, 4
bpf_mov  R5, 5
bpf_call foo    ; 呼叫 foo 函式
bpf_mov  R7, R0 ; 將 foo() 的返回值(在 R0 中)儲存到 R7 中
bpf_mov  R1, R6 ; 從 R6 中恢復 ctx 狀態,儲存到 R1;這樣下次執行呼叫函式呼叫時就可以繼續使用了;
bpf_mov  R2, 6  ; 將常量 2(即將呼叫的函式 bar() 的引數)載入到 R2 暫存器
bpf_mov  R3, 7
bpf_mov  R4, 8
bpf_mov  R5, 9
bpf_call bar    ; 呼叫 bar() 函式
bpf_add  R0, R7 ; 將 bar() 的返回值(在 R0 中)與 foo() 的返回值(在 R7 中)相加
bpf_exit

在 JIT 成 x86_64 之後,可能長下面這樣:

將 “eBPF 暫存器 -> x86_64 硬體暫存器” 對映關係貼到這裡方便下面程式對照

R0 -> rax
R1 -> rdi  // 傳參,呼叫方(caller)儲存
R2 -> rsi  // 傳參,呼叫方(caller)儲存
R3 -> rdx  // 傳參,呼叫方(caller)儲存
R4 -> rcx  // 傳參,呼叫方(caller)儲存
R5 -> r8   // 傳參,呼叫方(caller)儲存
R6 -> rbx  // 被呼叫方(callee)儲存
R7 -> r13  // 被呼叫方(callee)儲存
R8 -> r14  // 被呼叫方(callee)儲存
R9 -> r15  // 被呼叫方(callee)儲存
R10 -> rbp // 被呼叫方(callee)儲存
// x86_64 指令格式:注意源和目的暫存器的順序與 BPF 指令是相反的
// <指令>  <源暫存器/常量>  <目的暫存器>

// 下面這幾行是 x86_64 的初始化指令,與 eBPF 還沒有直接對應關係
// 解讀參考:https://stackoverflow.com/questions/41912684/what-is-the-purpose-of-the-rbp-register-in-x86-64-assembler
push   %rbp                // 將幀指標(frame pointer)在棧地址空間中前移,即棧空間增長一個單位(一個單位 64bit)
mov    %rsp, %rbp          // 將棧指標(stack pointer)儲存到 %rbp 位置(即上一行剛在棧上分配的位置)
sub    $0x228, %rsp        // 棧指標 rsp -= 0x228(棧向下增長,這一行表示再分配 0x228 個單位的棧空間)
mov    %rbx, -0x228(%rbp)  // 將 %rbx(對應 eBPF R6)的值儲存到新分配空間的起始處(佔用 8 個位元組),因為 eBPF 程式返回時會佔用 rbx 暫存器
mov    %r13, -0x220(%rbp)  // 將 %r13 (對應 eBPF R7)的值儲存到下一個位置(起始位置 = 0x228 - 0x8 = 0x220,也是佔用 8 個位元組),理由同上
                           // 接下來還應該有三條指令,分別將 r14、15、rbp 依次儲存到棧上,理由同上。
                           // 這樣,這 5 條指令佔用 5*8 = 40byte = 0x28 位元組。剛才總共申請了 0x228 位元組,
                           // 0x228 - 0x28 = 0x200 = 512 位元組,也就是 eBPF 文件裡常說的:eBPF 虛擬機器最大支援 512 位元組的棧空間。

// 下面這段與上面的 eBPF 指令能一一對應上
mov    %rdi, %rbx          // R6 = R1
mov    $0x2, %esi          // R2 = 2
mov    $0x3, %edx          // R3 = 3
mov    $0x4, %ecx          // R4 = 4
mov    $0x5, %r8d          // R5 = 5
callq  foo
mov    %rax, %r13          // R7 = R0
mov    %rbx, %rdi          // R1 = R6
mov    $0x6, %esi          // R2 = 6
mov    $0x7, %edx          // R3 = 7
mov    $0x8, %ecx          // R4 = 8
mov    $0x9, %r8d          // R5 = 9
callq  bar
add    %r13, %rax          // R7 += R0

mov    -0x228(%rbp), %rbx
mov    -0x220(%rbp), %r13
leaveq
retq

下面是對應的 C 程式碼:

u64 bpf_filter(u64 ctx) {
    return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
}

核心函式 foo()bar() 原型:

u64 (*)(u64 arg1, u64 arg2, u64 arg3, u64 arg4, u64 arg5);

它們從規定好的暫存器中獲取傳入引數,並將函式返回值放到 %rax 暫存器,也就是 eBPF 中的 R0 暫存器。 起始和結束的彙編片段 (prologue and epilogue)是由 JIT emit 出來的,是直譯器內建的

上面添加了對起始彙編片段的一些解讀,尤其是:為什麼 “eBPF 虛擬機器的最大棧空間是 512 位元組” 。 譯註。

R0-R5 are scratch registers,因此 eBPF 程式需要在多次函式呼叫之間儲存這些值。 下面這個程式例子是不合法的:

bpf_mov   R1, 1
bpf_call  foo
bpf_mov   R0, R1
bpf_exit

在執行 call 之後,暫存器 R1-R5 包含垃圾值,不能讀取 。 核心中的校驗器(in-kernel eBPF verifier)負責驗證 eBPF 程式的合法性。

6.4 eBPF 程式最大指令數限制

eBPF 最初限制最大指令數 4096,現在已經將這個限制放大到了 100 萬條

cBPF 和 eBPF 都是 兩運算元指令 (two operand instructions),有 助於 JIT 編譯時將 eBPF 指令一一對映成 x86 指令。

6.5 eBPF 程式上下文(ctx)引數

觸發直譯器執行時,傳遞給它的上下文指標(the input context pointer)是一個通用結構體, 結構體中的資訊是由具體場景來解析的 。例如

  • 對於 seccomp 來說,R1(也就是 ctx )指向 seccomp_data,
  • 對於 eBPF filter(包括從 cBPF 轉換過來的)來說,R1 指向一個 skb

6.6 cBPF -> eBPF 轉換若干問題

內部的 cBPF -> eBPF 轉換格式如下:

op:16, jt:8, jf:8, k:32    ==>    op:8, dst_reg:4, src_reg:4, off:16, imm:32
op

eBPF 是一個 通用目的 RISC 指令集 。在將 cBPF 轉成 eBPF 的過程中 ,不是每個暫存器和每條指令都會用到。例如,

exclusive add

某種意義上來說,eBPF 作為一個 通用匯編器 (generic assembler), 是效能優化的最後手段,

  • socket filters 和 seccomp 就是把它當做彙編器在用;
  • Tracing filters 可以用它作為彙編器,從核心生成程式碼。

6.7 eBPF 的安全性

核心內使用(in kernel usage)可能沒有安全顧慮,因為生成的 eBPF 程式碼只是用於優化 核心內部程式碼路徑,不會暴露給使用者空間。eBPF 的安全問題可能會出自校驗器本身(TBD )。因此在上述這些場景,可以把它作為一個安全的指令集來使用。

與 cBPF 類似,eBPF 執行在一個確定性的受控環境中,核心能依據下面兩個步驟,輕鬆地對 程式的安全性 作出判斷:

  1. 首先進行 深度優先搜尋 (depth-first-search),禁止迴圈;其他 CFG 驗證。
  2. 以上一步生成的指令作為輸入, 遍歷所有可能的執行路徑 。具體說 就是模擬每條指令的執行, 觀察暫存器和棧的狀態變化

7 eBPF 位元組碼編碼(opcode encoding)

為方便 cBPF 到 eBPF 的轉換,eBPF 複用了 cBPF 的大部分 opcode encoding。

7.1 算術和跳轉指令

對於算術和跳轉指令(arithmetic and jump instructions),eBPF 的 8bit op 欄位進一步分為三部分:

+----------------+--------+--------------------+
|   4 bits       |  1 bit |   3 bits           |
| operation code | source | instruction class  |
+----------------+--------+--------------------+
(MSB)                                      (LSB)

最後的 3bit 表示的是指令型別,包括:

===================     ===============
Classic BPF classes     eBPF classes
===================     ===============
BPF_LD    0x00          BPF_LD    0x00
BPF_LDX   0x01          BPF_LDX   0x01
BPF_ST    0x02          BPF_ST    0x02
BPF_STX   0x03          BPF_STX   0x03
BPF_ALU   0x04          BPF_ALU   0x04
BPF_JMP   0x05          BPF_JMP   0x05
BPF_RET   0x06          BPF_JMP32 0x06
BPF_MISC  0x07          BPF_ALU64 0x07
===================     ===============

BPF_ALU 和 BPF_JMP 的 operand

BPF_CLASS(code) == BPF_ALU or BPF_JMP 時,第 4 bit 表示的源運算元(source operand)可以是:

BPF_K     0x00 // 32bit 立即數作為源運算元(use 32-bit immediate as source operand),對 cBPF/eBPF 一樣
BPF_X     0x08 // 對 cBPF,表示用暫存器 X       作為源運算元
               // 對 eBPF,表示用暫存器 src_reg 作為源運算元

BPF_ALU 和 BPF_ALU64 (eBPF) 的 opcode

BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ] , BPF_OP(code) 可以是:

BPF_ADD   0x00
BPF_SUB   0x10
BPF_MUL   0x20
BPF_DIV   0x30
BPF_OR    0x40
BPF_AND   0x50
BPF_LSH   0x60
BPF_RSH   0x70
BPF_NEG   0x80
BPF_MOD   0x90
BPF_XOR   0xa0
BPF_MOV   0xb0  /* eBPF only: mov reg to reg */
BPF_ARSH  0xc0  /* eBPF only: sign extending shift right */
BPF_END   0xd0  /* eBPF only: endianness conversion */

BPF_JMP 和 BPF_JMP32 (eBPF) 的 opcode

BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ]BPF_OP(code) 可以是:

BPF_JA    0x00  /* BPF_JMP only */
BPF_JEQ   0x10
BPF_JGT   0x20
BPF_JGE   0x30
BPF_JSET  0x40
BPF_JNE   0x50  /* eBPF only: jump != */
BPF_JSGT  0x60  /* eBPF only: signed '>' */
BPF_JSGE  0x70  /* eBPF only: signed '>=' */
BPF_CALL  0x80  /* eBPF BPF_JMP only: function call */
BPF_EXIT  0x90  /* eBPF BPF_JMP only: function return */
BPF_JLT   0xa0  /* eBPF only: unsigned '<' */
BPF_JLE   0xb0  /* eBPF only: unsigned '<=' */
BPF_JSLT  0xc0  /* eBPF only: signed '<' */
BPF_JSLE  0xd0  /* eBPF only: signed '<=' */

指令 BPF_ADD | BPF_X | BPF_ALU 在 cBPF 和 eBPF 中都表示 32bit 加法:

A += X
dst_reg = (u32) dst_reg + (u32) src_reg

類似的, BPF_XOR | BPF_K | BPF_ALU 表示:

A ^= imm32
src_reg = (u32) src_reg ^ (u32) imm32

BPF_MISC 與 BPF_ALU64(eBPF 64bit 暫存器加法操作)

cBPF 用 BPF_MISC 型別表示 A = X 和 X = A 操作。

eBPF 中與此對應的是 BPF_MOV | BPF_X | BPF_ALU 。 由於 eBPF 中沒有 BPF_MISC 操作,因此 class 7 空出來了,用作了新指令型別 BPF_ALU64,表示 64bit BPF_ALU 操作。 因此, BPF_ADD | BPF_X | BPF_ALU64 表示 64bit 加法,例如 dst_reg = dst_reg + src_reg

cBPF/eBPF BPF_RET 指令的不同

cBPF 用整個 BPF_RET class 僅僅表示一個 ret 操作,非常浪費。 其 BPF_RET | BPF_K 表示將立即數 imm32 拷貝到返回值暫存器,然後退出函式。

eBPF 是模擬 CPU 建模的,因此 eBPF 中 BPF_JMP | BPF_EXIT 只表示退出函式操作。 eBPF 程式自己負責在執行 BPF_EXIT 之前,將返回值拷貝到 R0。

BPF_JMP 與 eBPF BPF_JMP32

Class 6 in eBPF 用作 BPF_JMP32,表示的意思與 BPF_JMP 一樣,但運算元是 32bit 的。

7.2 載入指令(load/store)

load and store 指令的 8bit code 進一步分為三部分:

+--------+--------+-------------------+
| 3 bits | 2 bits |   3 bits          |
|  mode  |  size  | instruction class |
+--------+--------+-------------------+
(MSB)                             (LSB)

2bit 的 size modifier 可以是:

BPF_W   0x00    /* word */
BPF_H   0x08    /* half word */
BPF_B   0x10    /* byte */
BPF_DW  0x18    /* eBPF only, double word */

表示的是 load/store 操作的位元組數:

B  - 1 byte
H  - 2 byte
W  - 4 byte
DW - 8 byte (eBPF only)

Mode modifier 可以是:

BPF_IMM  0x00  /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
BPF_ABS  0x20
BPF_IND  0x40
BPF_MEM  0x60
BPF_LEN  0x80  /* classic BPF only, reserved in eBPF */
BPF_MSH  0xa0  /* classic BPF only, reserved in eBPF */
BPF_XADD 0xc0  /* eBPF only, exclusive add */

兩個 eBPF non-generic 指令:BPF_ABS 和 BPF_IND,用於訪問 skb data

eBPF 有兩個 non-generic 指令,用於相容 cBPF:

BPF_ABS | <size> | BPF_LD
BPF_IND | <size> | BPF_LD

二者用來 訪問資料包中的資料 (packet data)。

  1. 這兩個指令 cBPF 中就有了,必須 eBPF 也必須要支援 ,而且 eBPF 直譯器還要 高效地執行 這兩條指令。
  2. 執行這個兩個指令時, 傳遞給直譯器的上下文 必須是 struct *sk_buff , 並且 隱含了 7 個運算元

    • R6 作為 隱式輸入 ,存放的必須是 struct *sk_buff
    • R0 作為 隱式輸出 ,存放的是從包中讀取的資料;
    • R1-R5 作為 scratch registers,不能在多次 BPF_ABS | BPF_LDBPF_IND | BPF_LD 指令之間在這幾個暫存器中儲存資料(每次呼叫執行之後,都會將這些暫存器置空);
  3. 這些指令還有隱含的程式退出條件。當 eBPF 程式試圖訪問資料包邊界之外的資料時,直譯器 會終止(abort)程式的執行。因此,eBPF JIT 編譯器也必須實現這個特性。 src_reg 和 imm32 欄位是這些指令的顯式輸入。

看個例子, BPF_IND | BPF_W | BPF_LD 翻譯成 C 語言表示: R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32)) 。 過程中會用到 R1-R5(R1-R5 were scratched)。

通用 eBPF load/store 指令

與 cBPF 指令集不同,eBPF 有通用 load/store 操作:

BPF_MEM  | <size> | BPF_STX:  *(size *)(dst_reg + off) = src_reg
BPF_MEM  | <size> | BPF_ST :  *(size *)(dst_reg + off) = imm32
BPF_MEM  | <size> | BPF_LDX:  dst_reg = *(size *)(src_reg + off)
BPF_XADD | BPF_W  | BPF_STX:  lock xadd *(u32 *)(dst_reg + off16) += src_reg
BPF_XADD | BPF_DW | BPF_STX:  lock xadd *(u64 *)(dst_reg + off16) += src_reg

其中,size 是:

BPF_B
BPF_H
BPF_W
BPF_DW

注意:這裡不支援 1 或 2 位元組的原子遞增操作。

載入 64bit 立即數的 eBPF 指令

eBPF 有一個 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM ,功能是將 64bit 立即數(imm64)載入到暫存器:

struct bpf_insn
dst_reg

cBPF 中有一個類似指令 BPF_LD | BPF_W | BPF_IMM ,功能是將一個 32bit 立即值(imm)載入到暫存器。

8 eBPF 校驗器(eBPF verifier)

eBPF 程式的安全是通過兩個步驟來保證的:

  • 首先做一次 DAG 檢查,確保沒有迴圈,並執行其他 CFG validation。特別地,這會檢查程式中是否有 無法執行到的指令(unreachable instructions,雖然 cBPF checker 是允許的)。
  • 第二步是從程式的第一條指令開始,遍歷所有的可能路徑。這一步會模擬執行每一條指令,在過程中觀察暫存器和棧的狀態變化。

8.1 模擬執行

  • 程式開始時, R1 中存放的是上下文指標 ctx ),型別是 PTR_TO_CTX

    • 接下來,如果校驗器看到 R2=R1,那 R2 的型別也變成了 PTR_TO_CTX ,並且接下來就能用在表示式的右側。
    • 如果 R1=PTR_TO_CTX 接下來的指令是 R2=R1+R1,那 R2=SCALAR_VALUE , 因為 兩個合法指標相加,得到的是一個非法指標 。(在 “secure” 模式下, 校驗器會拒絕任何型別的指標運算,以確保核心地址不會洩露給 unprivileged users)。
  • 從來沒有寫入過資料的暫存器是不可讀的,例如:

    bpf_mov R0 = R2
      bpf_exit

    將會被拒絕,因為程式開始之後,R2 還沒有初始化過。

  • 核心函式 執行完成後,R1-R5 將被重置為不可讀狀態 ,R0 儲存函式的返回值。
  • 由於 R6-R9 是被呼叫方(callee)儲存的,因此它們的狀態在函式呼叫結束之後還是有效的。

    bpf_mov  R6 = 1
      bpf_call foo
      bpf_mov  R0 = R6
      bpf_exit

    以上程式是合法的。如果換成了 R0 = R1 ,就會被拒絕。

8.2 load/store 指令檢查

load/store 指令只有當 暫存器型別合法時 才能執行,這裡的型別包括 PTR_TO_CTX、PTR_TO_MAP、PTR_TO_STACK。會對它們做邊界和對齊檢查。例如:

bpf_mov R1 = 1
bpf_mov R2 = 2
bpf_xadd *(u32 *)(R1 + 3) += R2
bpf_exit

將會被拒,因為執行到第三行時,R1 並不是一個合法的指標型別。

8.3 定製化校驗器,限制程式只能訪問 ctx 特定欄位

程式開始時,R1 型別是 PTR_TO_CTX(指向通用型別 struct bpf_context 的指標)。 可以 通過 callback 定製化校驗器 ,指定 size 和對齊,來 限制 eBPF 程式只能訪問 ctx 的特定欄位 。 例如,下面的指令:

bpf_ld R0 = *(u32 *)(R6 + 8)
is_valid_access()
[-MAX_BPF_STACK, 0)

8.4 讀取棧空間

只有程式 向棧空間寫入資料後,校驗器才允許它從中讀取資料 。cBPF 通過 M[0-15] memory slots 執行類似的檢查,例如

bpf_ld R0 = *(u32 *)(R10 - 4)
bpf_exit

是非法程式。因為雖然 R10 是隻讀暫存器,型別 PTR_TO_STACK 也是合法的,並且 R10 - 4 也在棧邊界內,但在這次讀取操作之前,並沒有往這個位置寫入資料。

8.5 其他

  • 指標暫存器(pointer register)spill/fill 操作也會被跟蹤,因為 對一些程式來說,四個 (R6-R9) callee saved registers 顯然是不夠的

  • 可通過 bpf_verifier_ops->get_func_proto() 定製允許執行哪些函式 。 eBPF 校驗器會檢查暫存器與引數限制是否匹配。呼叫結束之後,R0 用來存放函式返回值。

  • 函式呼叫 是擴充套件 eBPF 程式功能的主要機制,但每種型別的 BPF 程 序能用到的函式是不同的,例如 socket filters 和 tracing 程式。

  • 如果一個函式設計成對 eBPF 可見的,那必須從安全的角度對這個函式進行考量。校驗 器會保證呼叫該函式時,引數都是合法的。

  • cBPF 中, seccomp 的安全限制與 socket filter 是不同的,它依賴 兩個級聯的校驗器

    • 首先執行 cBPF verifier,
    • 然後再執行 seccomp verifier

    而在 eBPF 中,所有場景都共用一個(可配置的)校驗器。

更多關於 eBPF 校驗器的資訊,可參考 kernel/bpf/verifier.c

9 暫存器值跟蹤(register value tracking)

為保證 eBPF 程式的安全,校驗器必須跟蹤每個 暫存器 棧上每個槽位 (stack slot)值的範圍。這是通過 struct bpf_reg_state 實現的,定義在 include/linux/bpf_verifier.h , 它 統一了對標量和指標型別的跟蹤 (scalar and pointer values)。

每個 暫存器狀態 都有一個 型別

NOT_INIT
SCALAR_VALUE

9.1 9 種指標型別

依據它們 指向的資料結構型別 ,又可以分為:

  1. PTR_TO_CTX :指向 bpf_context 的指標。
  2. CONST_PTR_TO_MAP :指向 struct bpf_map 的指標。 是 常量 (const),因為不允許對這種型別指標進行算術操作。
  3. PTR_TO_MAP_VALUE :指向 bpf map 元素 的指標。
  4. PTR_TO_MAP_VALUE_OR_NULL :指向 bpf map 元素的指標,可為 NULL。 訪問 map 的操作 會返回這種型別的指標。 禁止算術操作
  5. PTR_TO_STACK :幀指標(Frame pointer)。
  6. PTR_TO_PACKET :指向 skb->data 的指標。
  7. PTR_TO_PACKET_END :指向 skb->data + headlen 的指標。禁止算術操作。
  8. PTR_TO_SOCKET :指向 struct bpf_sock_ops 的指標,內部有引用計數。
  9. PTR_TO_SOCKET_OR_NULL :指向 struct bpf_sock_ops 的指標,或 NULL。

    socket lookup 操作 會返回這種型別。 有引用計數 , 因此程式在執行結束時,必須通過 socket release 函式釋放引用。禁止算術操作。

這些指標都稱為 base 指標。

9.2 指標偏移(offset)觸發暫存器狀態更新

實際上,很多有用的指標都是 base 指標加一個 offset(指標算術運算的結果), 這是通過兩方面來個跟蹤的:

  1. ‘fixed offset’( 固定偏移 ):offset 是個常量(例如,立即數)。
  2. ‘variable offset’( 可變偏移 ):offset 是個變數。這種型別還用在 SCALAR_VALUE 跟蹤中,來跟蹤暫存器值的可能範圍。

校驗器對可變 offset 的知識包括:

  1. 無符號型別:最小和最大值;
  2. 有符號型別:最小和最大值;
  3. 關於每個 bit 的知識,以 ‘tnum’ 的格式: 一個 u64 ‘mask’ 加一個 u64 ‘value’。

1s in the mask represent bits whose value is unknown; 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both mask and value; no bit should ever be 1 in both。 例如,如果從記憶體載入一個位元組到暫存器,那該暫存器的前 56bit 已知是全零,而後 8bit 是未知的 —— 表示為 tnum (0x0; 0xff) 。如果我們將這個值與 0x40 進行 OR 操作,就得到 (0x40; 0xbf) ;如果加 1 就得到 (0x0; 0x1ff) ,因為可能的進位操 作。

9.3 條件分支觸發暫存器狀態更新

除了算術運算之外,條件分支也能更新暫存器狀態。例如,如果判斷一個 SCALAR_VALUE 大於 8,那

umin_value

9.4 有符號比較觸發暫存器狀態更新

有符號比較 (BPF_JSGT or BPF_JSGE)也會相應更新有符號變數 的最大最小值。

有符合和無符號邊界的資訊可以結合起來;例如如果一個值先判斷小於無 符號 8,後判斷大於有符合 4,校驗器就會得出結論這個值大於無符號 4,小於有符號 8 ,因為這個邊界不會跨正負邊界。

9.5 struct bpf_reg_stateid 欄位

struct bpf_reg_state 結構體有一個 id 欄位,

// include/linux/bpf_verifier.h

    /* For PTR_TO_PACKET, used to find other pointers with the same variable
     * offset, so they can share range knowledge.
     * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
     * came from, when one is tested for != NULL.
     * For PTR_TO_MEM_OR_NULL this is used to identify memory allocation
     * for the purpose of tracking that it's freed.
     * For PTR_TO_SOCKET this is used to share which pointers retain the
     * same reference to the socket, to determine proper reference freeing.
     */
    u32 id;

如註釋所述,該欄位針對不同指標型別有不同用途,下面分別解釋。

PTR_TO_PACKET

id 欄位對 共享同一 variable offset 的多個 PTR_TO_PACKET 指標 都是可見的,這對 skb 資料的範圍檢查 非常重要。舉個例子:

1:  A = skb->data // A 是指向包資料的指標
2:  B = A + var2  // B 是從 A 開始往前移動 var2 得到的地址
3:  A = A + 4     // A 往前移動 4 個位元組

在這個程式中,暫存器 A 和 B 將將共享同一個 id

  • A 已經從最初地址向前移動了 4 位元組(有一個固定偏移 +4),
  • 如果這個邊界通過校驗了,也就是確認小於 PTR_TO_PACKET_END ,那現在 暫存器 B 將有一個範圍至少為 4 位元組的可安全訪問範圍

更多關於這種指標的資訊,見下面的 ‘Direct packet access’ 章節。

PTR_TO_MAP_VALUE

與上面的用途型別,具體來說:

  1. 這一欄位對共享同一基礎指標的多個 PTR_TO_MAP_VALUE 指標可見;
  2. 這些指標中, 只要一個指標經驗證是非空的,就認為其他指標(副本)都是非空的 (因此減少重複驗證開銷);

另外,與 range-checking 型別,跟蹤的資訊(the tracked information)還用於 確保指標訪問的正確對齊 。 例如,在大部分系統上,packet 指標都 4 位元組對齊之後再加 2 位元組。如果一個程式將這個指標加 14(跳過 Ethernet header)然後讀取 IHL,並將指標再加上 IHL * 4 ,最終的指標將有一個 4n + 2 的 variable offset,因此,加 2 ( NET_IP_ALIGN ) gives a 4-byte alignment,因此通過這個指標進行 word-sized accesses 是安全的。

PTR_TO_SOCKET

與上面用途類似,只要一個指標驗證是非空的,其他共享同一 id 的PTR_TO_SOCKET 指標就都是非空的;此外, 還 負責跟蹤指標的引用 (reference tracking for the pointer)。

PTR_TO_SOCKET 隱式地表示對一個 struct sock 的引用。為確保引用沒有洩露,需要強制對引用進行非空(檢查), 如果非空(non-NULL),將合法引用傳給 socket release 函式。

10 直接資料包訪問(direct packet access)

對於 cls_bpf 和 act_bpf eBPF 程式,校驗器允許 直接通過 skb->dataskb->data_end 指標訪問包資料

10.1 簡單例子

1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
2:  r3 = *(u32 *)(r1 +76)  /* load skb->data */
3:  r5 = r3
4:  r5 += 14
5:  if r5 > r4 goto pc+16
R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp # 校驗器標記
6:  r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */

上面從包資料中載入 2 位元組的操作是安全的,因為 程式編寫者在第五行主動檢查了資料邊界 if (skb->data + 14 > skb->data_end) goto err ,這意味著能執行到第 6 行時(fall-through case), R3( skb->data )至少有 14 位元組的直接可訪問資料,因此 校驗器將其標記為 R3=pkt(id=0,off=0,r=14)

  • id=0 表示 沒有額外的變數加到這個暫存器上
  • off=0 表示 沒有額外的常量 offset
  • r=14 表示 安全訪問的範圍 ,即 [R3, R3+14) 指向的位元組範圍都是 OK 的。

這裡注意 R5 被標記為 R5=pkt(id=0,off=14,r=14)

  • 它也指向包資料,但 常量 14 加到了暫存器 ,因為它執行的是 skb->data + 14
  • 因此可訪問的範圍是 [R5, R5 + 14 - 14) ,也就是 0 個位元組。

10.2 複雜例子

下面是個更復雜一些的例子:

R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6:   r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
7:   r4 = *(u8 *)(r3 +12)
8:   r4 *= 14
9:   r3 = *(u32 *)(r1 +76) /* load skb->data */
10:  r3 += r4
11:  r2 = r1
12:  r2 <<= 48
13:  r2 >>= 48
14:  r3 += r2
15:  r2 = r3
16:  r2 += 8
17:  r1 = *(u32 *)(r1 +80) /* load skb->data_end */
18:  if r2 > r1 goto pc+2
R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
19:  r1 = *(u8 *)(r3 +4)

校驗器標記資訊解讀

第 18 行之後,暫存器 R3 的狀態是 R3=pkt(id=2,off=0,r=8)

  • id=2 表示 之前已經跟蹤到兩個 r3 += rX 指令 ,因此 r3 指向某個包內的某個 offset,由於程式設計師在 18 行已經做了 if (r3 + 8 > r1) goto err 檢查,因此 安全範圍 [R3, R3 + 8)
  • 校驗器 只允許對 packet 暫存器執行 add/sub 操作。其他操作會將 暫存器狀態設為 SCALAR_VALUE,這個狀態是不允許執行 direct packet access 的

操作 r3 += rX 可能會溢位,變得比起始地址 skb->data 還小 ,校驗器必須要能檢查出這種情況。 因此當它看到 r3 += rX 指令並且 rX 比 16bit 值還大時,接下來的任何將 r3 與 skb->data_end 對比的操作都 不會返回範圍資訊 ,因此嘗試通過 這個指標讀取資料的操作都會收到 invalid access to packet 錯誤。 例如,

  • r4 = *(u8 *)(r3 +12) 之後,r4 的狀態是 R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) ,意思是 暫存器的 upper 56 bits 肯定是 0,但對於低 8bit 資訊一無所知。 在執行完 r4 *= 14 之後,狀態變成 R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) ,因為一個 8bit 值乘以 14 之後, 高 52bit 還是 0,此外最低 bit 位為 0,因為 14 是偶數。

  • 類似地, r2 >>= 48 使得 R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)) ,因為移位是無符號擴充套件。 這個邏輯在函式 adjust_reg_min_max_vals() 中實現,它又會呼叫

    adjust_ptr_min_max_vals()
    adjust_scalar_min_max_vals()
    

對應的 C 程式碼

最終的結果是:eBPF 程式編寫者可以像使用普通 C 語言一樣訪問包資料:

void *data = (void *)(long)skb->data;
void *data_end = (void *)(long)skb->data_end;
struct eth_hdr *eth = data;
struct iphdr *iph = data + sizeof(*eth);
struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);

if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
    return 0;
if (eth->h_proto != htons(ETH_P_IP))
    return 0;
if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
    return 0;
if (udp->dest == 53 || udp->source == 9)
    ...;

相比使用 LD_ABS 之類的指令,這種程式寫起來方便多了。

11 eBPF maps

‘maps’ is a generic storage of different types for sharing data between kernel and userspace.

The maps are accessed from user space via BPF syscall, which has commands:

  • create a map with given type and attributes map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) using attr->map_type, attr->key_size, attr->value_size, attr->max_entries returns process-local file descriptor or negative error

  • lookup key in a given map err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value returns zero and stores found elem into value or negative error

  • create or update key/value pair in a given map err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value returns zero or negative error

  • find and delete element by key in a given map err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key

  • to delete map: close(fd) Exiting process will delete maps automatically

userspace programs use this syscall to create/access maps that eBPF programs are concurrently updating.

maps can have different types: hash, array, bloom filter, radix-tree, etc.

The map is defined by:

  • type
  • max number of elements
  • key size in bytes
  • value size in bytes

12 Pruning(剪枝)

校驗器實際上 並不會模擬執行程式的每一條可能路徑

對於每個新條件分支:校驗器首先會檢視它自己當前已經跟蹤的所有狀態。如果這些狀態 已經覆蓋到這個新分支,該分支就會被剪掉(pruned)—— 也就是說之前的狀態已經被接受 (previous state was accepted)能證明當前狀態也是合法的。

舉個例子:

  1. 當前的狀態記錄中,r1 是一個 packet-pointer
  2. 下一條指令中,r1 仍然是 packet-pointer with a range as long or longer and at least as strict an alignment,那 r1 就是安全的。

類似的,如果 r2 之前是 NOT_INIT ,那就說明之前任何程式碼路徑都沒有用到這個暫存器 ,因此 r2 中的任何值(包括另一個 NOT_INIT)都是安全的。

實現在 regsafe() 函式。

Pruning 過程不僅會看暫存器,還會看棧(及棧上的 spilled registers)。 只有證明二者都安全時,這個分支才會被 prune。這個過程實現在 states_equal() 函式。

13 理解 eBPF 校驗器提示資訊

提供幾個不合法的 eBPF 程式及相應校驗器報錯的例子。

The following are few examples of invalid eBPF programs and verifier error messages as seen in the log:

13.1 程式包含無法執行到的指令

static struct bpf_insn prog[] = {
  BPF_EXIT_INSN(),
  BPF_EXIT_INSN(),
};

Error:

unreachable insn 1

13.2 程式讀取未初始化的暫存器

BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),

Error:

0: (bf) r0 = r2
R2 !read_ok

13.3 程式退出前未設定 R0 暫存器

BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
BPF_EXIT_INSN(),

Error:

0: (bf) r2 = r1
1: (95) exit
R0 !read_ok

13.4 程式訪問超出棧空間

BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
BPF_EXIT_INSN(),

Error::

0: (7a) *(u64 *)(r10 +8) = 0
invalid stack off=8 size=8

13.5 未初始化棧內元素,就傳遞該棧地址

BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error::

0: (bf) r2 = r10
1: (07) r2 += -8
2: (b7) r1 = 0x0
3: (85) call 1
invalid indirect read from stack off -8+0 size 8

13.6 程式執行 map_lookup_elem() 傳遞了非法的 map_fd

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error:

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
fd 0 is not pointing to valid bpf_map

13.7 程式未檢查 map_lookup_elem() 的返回值是否為空就開始使用

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),

Error:

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
5: (7a) *(u64 *)(r0 +0) = 0
R0 invalid mem access 'map_value_or_null'

13.8 程式訪問 map 內容時使用了錯誤的位元組對齊

程式雖然檢查了 map_lookup_elem() 返回值是否為 NULL,但接下來使用了錯誤的對齊:

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),

Error:

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+1
 R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8

13.9 程式在 fallthrough 分支中使用了錯誤的位元組對齊訪問 map 資料

程式檢查了 map_lookup_elem() 返回值是否為 NULL,在 if 分支中使用了正確的位元組對齊, 但在 fallthrough 分支中使用了錯誤的對齊:

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),

Error:

0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+2
 R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +0) = 0
7: (95) exit

from 5 to 8: R0=imm0 R10=fp
8: (7a) *(u64 *)(r0 +0) = 1
R0 invalid mem access 'imm'

13.10 程式執行 sk_lookup_tcp() ,未檢查返回值就直接將其置 NULL

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),

Error:

0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (b7) r0 = 0
9: (95) exit
Unreleased reference id=1, alloc_insn=7

這裡的資訊提示是 socket reference 未釋放,說明 sk_lookup_tcp() 返回的是一個非空指標, 直接置空導致這個指標再也無法被解引用。

13.11 程式執行 sk_lookup_tcp() 但未檢查返回值是否為空

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_EXIT_INSN(),

Error:

0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (95) exit
Unreleased reference id=1, alloc_insn=7

這裡的資訊提示是 socket reference 未釋放,說明 sk_lookup_tcp() 返回的是一個非空指標, 直接置空導致這個指標再也無法被解引用。

14 測試(testing)

核心自帶了一個 BPF 測試模組,覆蓋了 cBPF 和 eBPF 的很多測試場景,能用來測試解釋 器和 JIT 編譯器。原始碼見 lib/test_bpf.c ,編譯是 Kconfig 啟用:

CONFIG_TEST_BPF=m

編譯之後用 insmodmodprobe 載入 test_bpf 模組。 測試結果帶有 ns 精度的時間戳日誌,列印到核心日誌( dmesg 檢視)。

15 其他(misc)

Also trinity, the Linux syscall fuzzer, has built-in support for BPF and SECCOMP-BPF kernel fuzzing.

本文作者

The document was written in the hope that it is found useful and in order to give potential BPF hackers or security auditors a better overview of the underlying architecture.

« [譯] LLVM eBPF 彙編程式設計(2020)