Linux 核心設計: 透過 eBPF 觀察作業系統行為

Copyright (慣C) 2018 宅色夫

直播錄影

核心動態追蹤機制

動態追蹤技術（dynamic tracing）是現代軟體的進階除錯和追蹤機制，讓工程師以非常低的成本，在非常短的時間內，克服一些不是顯而易見的問題。它興起和繁榮的一個大背景是，我們正處在一個快速增長的網路互連異質運算環境，工程人員面臨著兩大方面的挑戰：

1. 規模：無論是使用者規模還是機房的規模、機器的數量都處於快速增長的時代;
2. 複雜度：業務邏輯越來越複雜，運作的軟體也變得越來越複雜，我們知道它會分成很多很多層次，包括作業系統核心和其上各種系統軟體，像資料庫和網頁伺服器，再往上有腳本語言或者其他高階語言的虛擬機器或執行環境，更上面是應用層面的各種業務邏輯的抽象層次和很多複雜的程式邏輯。

人們擁抱雲端運算和巨量資料的同時，這種大規模的生產環境中的詭異問題只會越來越多，佔據工程人員大部分的時間和精力。動態追蹤技術實際就能幫助我們實現這種願景：透過「活體分析」，整個軟體系統仍在運作，並持續提供服務，處理真實請求之際，我們就可以去對它進行分析（不管它自己願不願意），就像查詢一個數據資料庫一般。正在運作的軟體系統本身其實就包含了絕大部分的寶貴資訊，就可以被直接當作是一個即時變化的資料庫來進行「查詢」。

在動態追蹤的實作中，一般是通過探針 (probe) 這樣的機制來發起查詢。我們會在軟體系統的某個層次，或者某幾個層次上面，安置一些探針，然後我們會自己定義這些探針所關聯的處理程式，好似中醫裡面的針灸，就是說如果我們把軟體系統看成是一個人，我們可以往他的一些穴位上扎一些「針」，那麼這些針頭上面通常會有我們自己定義的一些「傳感器」，我們可以自由地採集所需要的那些穴位上的關鍵資訊，一旦訊息都彙整起來，即可產生可靠的病因診斷和可行的治療方案。

動態追蹤機制如果內建於作業系統，那麼使用者層級的程式即可隨時採集資訊，構建出一幅完整的軟體樣貌，從而有效地指導我們做一些很複雜的分析。這裡非常關鍵的一點是，它是非侵入式的。如果把軟體系統比作一個人，那我們顯然不想把一個活人開膛破肚，卻只是為了幫他診斷疾病。相反，我們會去給他拍一張 X 光，給他做一個核磁共振，給他把脈，或者最簡單的，用聽診器聽一聽，諸如此類。針對一個生產系統的診斷，其實也應如此。動態追蹤技術允許我們使用非侵入式的方式，不用去修改我們的作業系統核心內部，不用去修改我們的應用程式，也不用去修改我們的業務程式碼或者任何系統配置，就可快速高效地精確獲取我們想要的資訊。

• DTrace: 源自 Solaris 作業系統
  • Oracle 重新以 GNU GPL 釋出 DTrace 並嘗試整合到 Linux 核心
  • DTrace for Linux 2.0 在 eBPF 的基礎重新實作，不再依賴專屬的核心模組
• SystemTap: Red Hat 的實作
• ktap: 華為科技的實作

延伸閱讀: 動態追蹤技術漫談

eBPF 到底和觀察作業系統內部有何關聯？

Berkeley Packet Filter (BPF) 最初的動機的確是封包過濾機制，但擴充為 eBPF (Extended BPF) 後，就變成 Linux 核心內建的內部行為分析工具包含以下:

• 動態追蹤 (dynamic tracing);
• 靜態追蹤 (static tracing);
• profiling events;

參照 BPF Tracing Tool

• 在安全方面 BPF 的測試碼最終將執行在核心內部沙盒 (sandbox) 隔離環境 (虛擬機器) 內，且用軟體的丟棄早期封包機制達到 DDoS mitigation，也就是 eXpress Data Path (也稱作 XDP ，如果封包發現錯誤，則在 protocol stack 前就會判斷是否要繼續處理或丟棄)，也提供 intrusion detection 機制。

• 在使用者層級 (user mode) 準備好 BPF 程式碼，目的是去測量 latency 或 stack traces 等資訊，BPF 程式碼最終會被編譯成 BPF bytecode 執行在核心內部的沙盒隔離執行環境，其測試的方式是：

  1. BPF 的 code 在 user mode 被編譯 BPF bytecode
     • v5.2 之前，Max 4096 instructions, 512B stack, in-kernel JIT for opcodes
     • v5.2 之後，instruction 數量上限放寬到 1 million
  2. 載入核心驗證器: 如果不安全是有權力去拒絕這份 BPF bytecode 的, 但如果被接受，他可以依照以下四種不同的形式去選擇測試
     • kprobes: kernel dynamic tracing.
     • uprobes: user level dynamic tracing.
     • tracepoints: kernel static tracing.
     • perf_events: timed sampling and PMCs(Preventive maintenance checks and services).
       
  3. 被測試完的資料有兩種方式傳回 per-event details (每個事件的詳細資料) 或 BPF map (BPF maps 可以做出直方圖，數據統計或相關矩陣…等整體性的結果)

• 使用 BPF 的先決條件

  • CONFIG_BPF_SYSCALL 編譯選項參數
  • 核心版本 4.4 版以上就有提供直方圖，統計和追蹤每個事件的功能
    (下圖綠色的字是指至少要達到多少版本才有提供該功能)
    

作業系統的核心內建虛擬機器?!

• A JIT for packet filters: Linux 核心已收錄 Berkeley Packet Filter (BPF) JITC

  • 形式上說來，BPF 就是 in-kernel virtual machine

• tcpdump 不但可分析封包的流向，連封包的內容也可以進行「監聽」

  • 鳥哥 Linux 私房菜: 第五章、 Linux 常用網路指令
  • Berkeley Packet Filter (BPF) 會透過 bytecode 和 JIT compiler 來執行

以 IP 與 port number 捕捉 eth0 這個網路介面的封包

$ sudo tcpdump -i eth0 -nn
listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes
...
22:02:05.803000 ARP, Request who-has 140.131.178.251 tell 140.131.179.254, length 46
22:06:46.922722 IP 140.131.178.244.22 > 110.50.189.175.57657: Flags [P.], seq 1502584330:1502584518, ack 1360901079, win 306, options [nop,nop,TS val 3241491854 ecr 590330642], length 188
...

你需要掌握 網路基礎 提及的概念，這樣才能理解 TCP 封包的表頭資料。以上述輸出來說:

• 22:02:05.803000 和 22:06:46.922722: 封包被擷取的時間，格式為「時:分:秒」
• ARP: 通訊協定: Address Resolution Protocol (ARP)
  
  • ARP 是 TCP/IP 設計者利用乙太網路的廣播性質﹐設計出來的位址解釋協定，主要特性和優點是它的位址對應關係是動態的﹐以查詢的方式來獲得 IP 位址和實體位址的對應。工作原理﹕
    1. 每台主機都會在 ARP 快取緩衝區 (ARP cache) 中建立一個 ARP 表格﹐用來記錄 IP 位址和實體位址的對應關係。這個 Table 的每一筆資料會根據自身的存活時間遞減而最終消失﹐以確保資料的真實性;
    2. 當發送主機有一個封包要傳送給目的主機的時候﹐並且獲得目的主機的 IP 位址﹔那發送主機會先檢查自己的 ARP 表格中有沒有該 IP 位址的實體位址對應。如果有﹐就直接使用此位址來傳送框包﹔如果沒有﹐則向網路發出一個 ARP Request 廣播封包﹐查詢目的主機的實體位址。這個封包會包含發送端的 IP 位址和實體位址資料;
    3. 這時﹐網路上所有的主機都會收到這個廣播封包﹐會檢查封包的 IP 欄位是否和自己的 IP 位址一致。如果不是則忽略﹔如果是則會先將發送端的實體位址和 IP 資料更新到自己的 ARP 表格去﹐如果已經有該 IP 的對應﹐則用新資料覆蓋原來的﹔然後再回應一個 ARP Reply 封包給對方﹐告知發送主機關於自己的實體位址;
    4. 當發送端接到 ARP Reply 之後﹐也會更新自己的 ARP 表格﹔然後就可以用此紀錄進行傳送了;
    5. 如果發送端沒有得到 ARP Reply ﹐則宣告查詢失敗。
• 140.131.178.244.22 >: 傳送端是 140.131.178.244 這個 IP，而傳送的 port number 為 22，你必須要瞭解的是，那個大於 (>) 的符號指的是封包的傳輸方向;
• 110.50.189.175.57657: 接收端是 110.50.189.175 這個 IP，且該主機開啟 port 57657 來接收;
• [P.], seq 1502584330:1502584518: 這封包帶有 PUSH 的資料傳輸標誌，且傳輸的資料為整體資料的 1502584330 ~ 1502584518 byte；
• ack 1360901079：ACK 的相關資料;

簡單來說，就是該封包是由 IP 地址 140.131.178.244 傳到 110.50.189.175，透過的 port 是由 22 到 57657，使用的是 PUSH 的旗標，而不是 SYN 之類的主動連線標誌。

變更上述命令為 $ sudo tcpdump -p -ni eth0 "arp"，即可捕捉 ARP 相關網路活動。

$ sudo tcpdump -p -ni eth0 -d "ip and udp"
(000) ldh      [12]
(001) jeq      #0x800           jt 2	jf 5
(002) ldb      [23]
(003) jeq      #0x11            jt 4	jf 5
(004) ret      #262144
(005) ret      #0

依據 tcpdump(8)

-d Dump the compiled packet-matching code in a human readable form to standard output and stop.
-dd Dump packet-matching code as a C program fragment.
JT: true; JF: false

$ sudo tcpdump -p -ni eth0 -dd "ip and udp"
{ 0x28, 0, 0, 0x0000000c },
{ 0x15, 0, 3, 0x00000800 },
{ 0x30, 0, 0, 0x00000017 },
{ 0x15, 0, 1, 0x00000011 },
{ 0x6, 0, 0, 0x00040000 },
{ 0x6, 0, 0, 0x00000000 },

上述 (000) 到 (005) 的序列就是 BPF bytecode，初步解讀:

• 000: 從封包位移量 012 載入一個 half-word (2 bytes)
• 001: 檢驗數值是否為 0x0800，若不是就跳到 005 也就是返回 0
  • This checks for the IP packet on top of an Ethernet frame.
• 002: 自封包位移量 23 載入一個 byte
  • That's the "protocol" field 9 bytes within an IP frame.
• 003: 檢驗數值是否為 0x11，若非，就跳到 005
  • 0x11 是 UDP protocol number

位於核心的 BPF 模組是整個流程之中最核心的一環：一方面接受 tcpdump 經由 libpcap 轉譯而來的濾包條件 (pseudo machine language)，另一方面也將符合條件的封包訊息從核心模式複製到使用者層級，最終經由 libpcap 發送給 tcpdump。

參照 Linux 核心文件 Linux Socket Filtering aka Berkeley Packet Filter (BPF)

XDP (eXpress Data Path) 引入後，創造更大的效益，見 How to drop 10 million packets per second

With XDP we can run eBPF code in the context of a network driver. Most importantly, this is before the skbuff memory allocation, allowing great speeds.

BPF 被引入 Linux 之後，自 v3.0 迎來了比較大的革新：在一些特定硬體平台上，BPF 有了加速用的 Just-In-Time (jit) 編譯器：個別硬體架構的 JIT 編譯器實作於 bpf_int_jit_compile() 函式，若 CONFIG_BPF_JIT 編譯選項有開啟，則傳入的 BPF bytecode 會被傳入該函式加以編譯，編譯結果被拿來替換掉預設的處理函式 sk_run_filter()。詳見核心原始程式碼 arch/<platform>/net 目錄。

Project Zero Reading privileged memory with a side-channel 揭露 ebpf jit 搭配 Spectre and Meltdown 漏洞發動攻擊的手段 (中文解說)

打開 BPF 的 JIT 很簡單，只要向 /proc/sys/net/core/bpf_jit_enable 寫入 1 即可，若改為數值 2 的話，還可在核心訊息看到載入 BPF 程式時 JIT 生成的最佳化程式碼，還能透過 bpf_jit_disasm.c，將核心的訊息的二進位轉換成對應組合語言。

之後陸續有 BPF 相關的更動:

• v3.4: 將 BPF 引入 seccomp
  • 程式有安全漏洞在所難免, 即便開發者具備良好的程式技巧跟心態, 仍有機會出現安全漏洞，因此事後的防護就很重要，seccomp 為此而生
  • 設計宗旨：指定 process 只能呼叫特定的 system call
  • 即便核心提供的 system call 有上百個，但大部份系統呼叫會被限制住，透過設定 seccomp 除了不影響原本執行結果，也能降低一旦 process 遭受攻擊對整體系統造成的影響.
• v3.14: 新增 bpf_asm 和 bpf_dbg
• v3.17: 引入 extended BPF，也就是我們探討的主角 eBPF

eBPF 整合進核心後，傳統的 BPF 仍被保留了下來，並被重命名為 classical BPF(cBPF)。相較於 cBPF，eBPF 帶來的改變相當巨大，一方面 eBPF 已是核心追蹤 (kernel tracing)、程式效能除錯/監控、流量控制 (traffic control) 等領域帶來創新。

值得留意的是，cBPF 和核心溝通的機制是 recv()，而 eBPF 則引入全新的 map 機制，運作原理如下:

由上可見，位於使用者層級的程式在核心中開闢出一塊空間，建立起一個特製資料庫，讓 eBPF 程式得以互動 (見 bpf_create_map() 函式)，而這個資料庫 key-value 儲存方式，無論是從使用者層級抑或核心內部，都可存取，當然，如此設計最大的優勢就是效率。

相較於 cBPF 仰賴系統呼叫，不時需要將資料從核心層級複製到使用者層級，map 機制下的通訊成本就顯著縮小。map 機制解決的另一個問題是通信資料的多樣性問題。cBPF 所覆蓋的功能範圍很簡單，無外乎是網路封包追蹤和 seccomp 部分，但 eBPF 的操作範圍就非常廣泛。

核心演化的描述可見 History and Context

在核心空間中處裡 uprobe 觸發的成本，有機會比在 userspace 用 SIGTRAP 或 ptrace 處理 breakpoint 觸發低。uprobe 觸發後，驅動 eBPF 執行環境，再用 eBPF map 傳資料給使用者層級。

延伸閱讀:

• BPF - the forgotten bytecode
• eBPF 簡史
• eBPF, Sockets, Hop Distance and manually writing eBPF assembly
• Why is the kernel community replacing iptables with BPF?

解說 Introduction to Linux kernel tracing and eBPF integration

解說 Netronome: Demystify eBPF JIT Compiler

Introduction to eBPF and XDP 筆記

• Building an Extensible Open vSwitch Datapath
  • lpc18-ebpf
• BPF, eBPF, XDP and Bpfilter… What are These Things and What do They Mean for the Enterprise?

開發工具集

2015 年，Linux 基金會成立新的專案 IO Visor，目標為實現高度有彈性的 data plane，以加速 NFV，關鍵軟體元件就是 eBPF，允許在核心內部實作網路封包處理，從而避免繁瑣的系統呼叫和使用者層級的資料處理。

PLUMgrid 是 eBPF 的重要貢獻公司，專注於 SDN/NFV，在 2016 年底被 VMware 收購，該公司讓 eBPF 相關成果整合到 Linux 核心 v3.16

儘管可用 C 程式來處理 BPF，但編譯出來的卻仍然是 ELF 檔案，開發者需要手動析出真正可以注入核心的檔案。於是 BPF Compiler Collection (BCC) 作為 IOVisor 子計畫被提出，讓進行 BPF 的開發只需要專注於 C 語言注入於核心的邏輯和流程，剩下的工作，包括編譯、解析 ELF、載入 BPF 代碼塊以及建立 map 等等基本可以由 BCC 一力承擔，無需多勞開發者費心。

• BPF Compiler Collection (BCC)
  • BCC is a toolkit for creating efficient kernel tracing and manipulation programs, and includes several useful tools and examples. It makes use of eBPF (Extended Berkeley Packet Filters), a new feature that was first added to Linux 3.15.
• Writing eBPF tracing tools in Rust
• Linux System Monitoring with eBPF by Circonus
  • BPF metrics: This plugin captures high frequency low level metrics on Linux system v4.3+
  • latencies of all syscalls as histograms: bpf syscall latency
  • counts of all syscalls as numeric metric: bpf syscall count
  • latencies of all block devices as histograms: bpf bio latency
  • latencies of all scheduler events (run-queue latencies) as histogram: bpf runq latency

解說 Kernel Analysis Using eBPF - Daniel Thompson, Linaro

• video / slides

實驗前請確保安裝必要的套件:

$ sudo apt install -y linux-headers-$(uname -r) bpfcc-tools python3-bpfcc libbpfcc libbpfcc-dev

• BPF bytecode 實驗

• a.c

int f(int x) {
    return x + 1;
}

$ clang -c -S -emit-llvm a.c 得到 a.ll (LLVM IR)
$ clang -c -S -target bpf a.c 得到 a.s (eBPF)

• $ clang -c -target bpf a.c 得到 a.o (eBPF bytecode)
  ​​​​$ file a.o 
  ​​​​a.o: ELF 64-bit LSB relocatable, no machine, version 1 (SYSV), not stripped
  ​​​​$ objdump -x a.o
  ​​​​a.o:     file format elf64-little
  ​​​​a.o
  ​​​​architecture: UNKNOWN!, flags 0x00000010:
  ​​​​HAS_SYMS
  ​​​​start address 0x0000000000000000
  ​​​​
  ​​​​Sections:
  ​​​​Idx Name          Size      VMA               LMA                   File off  Algn
  ​​​​  0 .text         00000030  0000000000000000      0000000000000000  00000040  2**3
  ​​​​                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  ​​​​SYMBOL TABLE:
  ​​​​0000000000000000 g       .text	0000000000000000 f
  

$ objcopy -I elf64-little -O binary a.o a.bin 抽出 eBPF bytecode

$ ubpf-disassembler a.bin a.s

實際操作

Linux 發展之初，只是一個以 single thread 為導向的作業系統，multi-threaded 與 SMP 也在發展 10 年後才納入，早期甚至得用彆腳的 LinuxThread 套件來實現 multi-threading，而 Mach 與 Hurd 在設計初期，就已經考慮這些需求。在 NPTL 出現之前，Linux 的 multi-threaded 實做非常奇怪，仍然把 process 當作最基本的abstraction，也就是說 scheduling, context switch 等基本操作對象仍是 process，而thread / LWP 只是和別人分享定址空間和資源的 process。因此：

• 用 clone(2) 產生的 thread  本質上仍是 process，可以說  Linux 核心中定義的 "thread" 只做到了資源共享，而不構成執行工作的最基本單位
• 嚴格來說，Linux 只實做了一半的 thread，但這並不是壞事，因為許多的應用程式不見得用到 thread，而且簡化 thread 實做的結果，使得 process 管理變得更有效率，副作用是產生出來的 "thread" 比其它作業系統的實做，顯得更 heavy-weight，可以說，過去 Linux 犧牲 thread 的效率，以換取 process 的效率
• 以 abstraction 的角度來看  Linux 過去並非在本質上支援 thread，但以 programming model 來看，Linux 的確是有 thread 可用，儘管效率較差

clone(2) 指出: One use of clone() is to implement threads: multiple flows of control in a program that run concurrently in a shared address space.
When the child process is created with clone(), it commences execution by calling the function pointed to by the argument fn. (This differs from fork(2), where execution continues in the child from the point of the fork(2) call.)

早期 Linux 的 process 和 thread 的效能和其他作業系統的客觀數據比較，可參照論文 "An Overview of the Singularity Project"  (Microsoft Research, 2005 年) 的第 31 頁

以下透過 eBPF 追蹤 clone 系統呼叫的使用狀況。

• hello.py: 每當 clone 系統呼叫觸發，就印出訊息

#!/usr/bin/env python
from bcc import BPF

# bpf program in restricted C language.
prog = """
int hello_world(void *ctx) {
  bpf_trace_printk("Hello, World!\\n");
  return 0;
}
"""

b = BPF(text=prog)

# attaching hello_world function to sys_clone system call.
b.attach_kprobe(event="sys_clone", fn_name="hello_world")

# reading from /sys/kernel/debug/tracing/trace_pipe
b.trace_print(fmt="Program:{0} Message:{5}")

可能會遇到以下錯誤訊息:

cannot attach kprobe, probe entry may not exist

是因原本的 sys_clone 在新的 Linux 版本 (commit d5a0052) 已變更符號名稱，找不到 sys_clone 這符號。以下命令可檢查該符號是否存在:

$ cat /proc/kallsyms | grep sys_clone

• count.py: 計算 clone 系統呼叫在一定時間內的統計量

#!/usr/bin/env python
from bcc import BPF

prog = """
BPF_TABLE("array", u32, u32, stats, 1);
int hello_world(void *ctx) {
  u32 key = 0, value = 0, *val;
  val = stats.lookup_or_init(&key, &value);
  (*val)++;
  bpf_trace_printk("total fork syscall:%d\\n", *val);
  return 0;
}
"""

b = BPF(text=prog, debug=4)
b.attach_kprobe(event="sys_clone", fn_name="hello_world")
b.trace_print()

• freq.py: 計算 clone 系統呼叫的發生頻率

#!/usr/bin/env python
from bcc import BPF
from time import sleep

prog = """
BPF_TABLE("array", u32, u32, stats, 1);
int hello_world(void *ctx) {
  u32 key = 0, value = 0, *val;
  val = stats.lookup_or_init(&key, &value);
  lock_xadd(val, 1);
  return 0;
}
"""

b = BPF(text=prog)

# getting shared kernel map
stats_map = b.get_table("stats")
b.attach_kprobe(event="sys_clone", fn_name="hello_world")

for x in range(0, 20):
    stats_map[ stats_map.Key(0) ] = stats_map.Leaf(0)
    sleep(1)
    print "Total sys_clone per second =", stats_map[ stats_map.Key(0) ].value;

Hist Triggers in Linux 4.7

BPF Socket Filtering Demo

• demo-client sends arbitrary user supplied messages in UDP datagrams to demo-server.
• demo-server accepts and prints received messages. A BPF for udp will be installed onto the socket when demo-server receives a "block" message. Any further communication from the demo-client will be filtered out.

待整理

• eBPF - Understanding How It Works
• BPF and formal verification
• From High Ceph Latency to Kernel Patch with eBPF/BCC
• Extending Vector with eBPF to inspect host and container performance
• lockstat
• eBPF can't count?!
• Full-system dynamic tracing on Linux using eBPF and bpftrace
• awesome-ebpf
• Extending the Kernel with eBPF

  Android 包含一個 eBPF 載入器和程式庫，它會在 Android 啟動時載入 eBPF 程式以擴展核心功能，這可用於從核心收集統計資訊，進行監控或追蹤

• eBPF Traffic Monitoring
• sqreen-bpf: Slides and Workshop Instructions for a BPF Introduction
• MicroBPF: Probe TCP metrics and latencies from the kernel with BCC
• eBPF Standard Documentation