初探 Linux Kernel 中的 BPF 與 XDP 技術：以 Tiny Load Balancer 為例

本文目標：

• 認識 BPF（Berkeley Packet Filter）
• 認識 XDP（eXpress DataPath）
• 實戰解說：Tiny LoadBalancer

先備知識：

TCP/IP

Socket programming

Linux networking system (1) (2)

Operating System: kernel/user space, system call

什麼是 BPF？

BPF（Berkeley Packet Filter）為 Steven McCanne 和 Van Jacobson 的共同研究成果，其論文在 1993 年發表於 USENIX 研討會（是該領域中頂級的研討會之一）。

在 BPF 與相關技術問世之前，作業系統通常這麼處理（接收）網路封包：

1. 網卡收到封包的資料，將它轉為系統可識別的資料。
2. 網卡向 CPU 發出中斷。
3. 作業系統處理該（外部）中斷，將資料複製到 Kernel Space 的 buffer。
4. 代表網路封包的 buffer 進入 networking stack，從 L2 一路解析到 L3 與 L4。
5. 如果上面的處理工作順利，作業系統會將 buffer 的內容複製一份到 User Space 的 buffer 上。
6. 位於 User Space 的應用程式成功收到網路封包，進行後續處理。

而 BPF 的核心概念是讓 User Space 的應用程式可以透過額外的過濾程式來告訴作業系統它希望收到哪些網路封包，這麼做的好處顯而易見：系統可以在封包一進入到 Kernel Space 時就過濾掉沒有作用的封包，避免這些封包一路經過作業系統的 Networking Stack（網路堆疊）一路傳到 User Space 上面的應用程式。

eBPF 與 BPF 傻傻分不清楚

Linux kernel 自 3.18 版本開始，將 eBPF（extended BPF）整合自專案中，除了正常的網路封包過濾，它還可以用於非網路相關的功能，例如：將 eBPF program 附加（attach）到 pre-defined hooks上面。

網路上常見的 BPF 討論通常也都是指 eBPF 而非傳統的 BPF，如果你對傳統的 BPF 有興趣應該嘗試 Classic BPF 之類的關鍵字。

有了 eBPF，開發者可以輕易地做到作業系統層級的動態追蹤，或是針對系統的某一個部分進行最佳化。

根據 eBPF 官方網站說明，pre-defined hooks 包含：system calls、function entry/exit、kernel tracepoints、network events 等等。

圖片取自 eBPF 官網

參考上圖，任何出現 eBPF 標示的地方都是能夠注入 eBPF program 的 Hook，範圍涵蓋了檔案系統、網路以及系統呼叫層級。

如果你還不清楚 eBPF 整合自 Linux kernel 代表著什麼，你可以把它想成：你可以撰寫一個簡單的 program 附加在 Linux kernel 內部，它會以極高的效率完成你想要做到的事情（操作網路封包、追蹤系統呼叫、Kernel 的最佳化）。

如何撰寫 eBPF program？

一個 eBPF program 範例如下：

{ 0x28, 0, 0, 0x0000000c },
{ 0x15, 0, 3, 0x00000800 },
{ 0x30, 0, 0, 0x00000017 },
{ 0x15, 0, 1, 0x00000011 },
{ 0x6, 0, 0, 0x00040000 },
{ 0x6, 0, 0, 0x00000000 },

我們會將這些程式碼稱為 eBPF ByteCode，這些 eBPF program 經過使用者附加到 Linux kernel 後，都會運作在一個獨立的 eBPF VM 上，它會將這些 ByteCode 轉換為機器能夠讀懂的組合語言。

實際上，要用這些 ByteCode 造出一個可靠的應用太費工了！所以開發者會仰賴編譯器幫助我們將 C 語言撰寫的原始程式碼轉換為 eBPF ByteCode：

圖片取自 eBPF 官網

上圖表示開發者能夠使用 clang 將 C 語言撰寫的原始程式碼編譯成 eBPF program，實際上這個編譯工作還需要仰賴 LLVM 的支援。

補充：Clang 是編譯器的前端、LLVM 則是編譯器的後端。

eBPF 的工作流程

當使用者嘗試將 eBPF program 附加到特定的 hook 上，User space 的應用程式會透過系統呼叫 bpf() 將 program 注入到 kernel space：

圖片取自 eBPF 官網

為了保證使用者嘗試附加的 eBPF program 不會危害到作業系統的執行，eBPF verifier 會負責檢驗 program 的可靠性以及安全性。

待 program 驗證完畢，它便會被載入到 kernel 當中的 eBPF JIT compiler 上執行。

eBPF program 如何與 user space program 溝通？

eBPF 提供 map 作為兩者之間共享資訊的方式，User space 的應用程式同樣可以透過呼叫 bpf() 存取 map 當中的資訊：

#include <linux/bpf.h>
int bpf(int cmd, union bpf_attr *attr, unsigned int size);

其中的 cmd 參數用來表示要如何操作這個 map，它包含：

• BPF_MAP_CREATE：建立一個 map，建立成功後它會回傳 map 的 file descriptor。
• BPF_MAP_LOOKUP_ELEM：使用 key 查詢特定的 map 的內容。
• BPF_MAP_UPDATE_ELEM：使用 key 更新特定的 map 的內容。
• BPF_MAP_DELETE_ELEM：使用 key 刪除特定的 map 的內容。
• BPF_MAP_GET_NEXT_KET：找到 map 中下一個元素的 key。

上面僅列出與 map 有關的 command，如果對 bpf() 系統呼叫有興趣，可以參考 Linux manual page 找到更多內容。

使用 libbpf 開發 eBPF program

實務上，如果僅使用 bpf() 系統呼叫開發出我們想要的功能仍需要耗費不少時間。因此，開源社群的貢獻者開始為 eBPF 生態系發展眾多工具，其中 libbpf 就封裝了許多方便的 API。

以一個計算網路封包接收量的例子來看：eBPF program 已經附加到 kernel space 並且正常工作中，當有封包送往主機，它會更新 map 裡面的內容：

struct datarec {
 __u64 rx_packets;
 __u64 rx_bytes;
};

// ...

SEC("xdp_recv")
int  xdp_recv_func(struct xdp_md *ctx)
{
    // ...
    __u64 bytes = data_end - data;
    lock_xadd(&rec->rx_bytes, bytes);

    return XDP_PASS;
}

接著我們會在 user space 的應用程式中利用 libbpf 的 API 蒐集這些資料：

// Ref: https://github.com/xdp-project/xdp-tutorial/

void map_get_value_percpu_array(int fd, __u32 key, struct datarec *value)
{
 /* For percpu maps, userspace gets a value per possible CPU */
 unsigned int nr_cpus = bpf_num_possible_cpus();
 struct datarec values[nr_cpus];
 __u64 sum_bytes = 0;
 __u64 sum_pkts = 0;
 int i;

 if ((bpf_map_lookup_elem(fd, &key, values)) != 0) {
  fprintf(stderr,
   "ERR: bpf_map_lookup_elem failed key:0x%X\n", key);
  return;
 }

 /* Sum values from each CPU */
 for (i = 0; i < nr_cpus; i++) {
  sum_pkts  += values[i].rx_packets;
  sum_bytes += values[i].rx_bytes;
 }
 value->rx_packets = sum_pkts;
 value->rx_bytes   = sum_bytes;
}

上面的範例中，map 的類型是 BPF_MAP_TYPE_PERCPU_ARRAY，讓每個 CPU 分別維護一份資料，再由 user space 的應用程式將每個 CPU 維護的 counter 加總。

實際上，eBPF 的 map 有多種類型，詳情同樣可以參考 Linux manual page。

什麼是 XDP？

XDP（eXpress Data Path）是一種基於 eBPF 技術的高效能 data path，透過它我們可以在網路封包進入到 Networking Stack 之前完成封包的處理。

筆者補充：

XDP 一詞很常與 DPDK 擺在一起比較，不過 XDP 與 DPDK 從底層來說是完全不一樣的技術。前者是希望作業系統儘早的處理掉封包，後者則是希望封包可以在繞過作業系統的情況下就完成處理。

圖片來源：https://sematext.com/blog/ebpf-and-xdp-for-processing-packets-at-bare-metal-speed/

觀察上圖，當我們將 eBPF program 附加到 XDP Hook 上，當 NIC（網路卡）接收到來自其他主機的封包，它會判斷應該對該封包做出何種行為：

• 丟棄封包（XDP_DROP）：假設我們撰寫了一個 DDoS 偵測器，eBPF program 判定該封包為惡意封包時便可以在 XDP Hook 階段將封包丟棄。
• 接受封包（XDP_PASS）：如果 eBPF program 認為封包沒有問題，也不需要對該封包進行任何修改（改變封包的內容，可能是修改 source IP、destination IP），eBPF program 可以回傳 XDP_PASS 讓封包流入作業系統的 Networking Stack。經過 kernel space 一系列的處理後，位於 user space 的 backend application 就能收到該封包了。
• 傳送封包（XDP_TX）：如果我們使用 XDP 實作一個 Proxy 或是 Load balancer，在修改封包內容後，eBPF program 應該回傳 XDP_TX，讓封包直接離開主機。
• 轉送封包（XDP_REDIRECT）：行為與 XDP_TX 雷同，不過網路封包會導向至其他網路卡處理。
• 異常封包處理（XDP_ABORTED）：行為與 XDP_DROP 雷同，但是 eBPF program 會在 tracepoint 上提供錯誤訊息的 log。

實戰：Tiny Load Balancer

什麼是 TinyLB？

該專案受 eBPF Summit 2021: An eBPF Load Balancer from scratch 啟發，並且修改自 lb-from-scratch 專案。是一個規模不到 100 行的 Load balancer 實作。

TinyLB 提供 Docker compose 來模擬網路拓墣：

筆者補充：

1. Load Balancer 常見於各種網路服務的架構，其目的是為了讓網路流量可以有效的分配給空閒的工作節點，進一步提升網路封包的吞吐量。

2. 以 AWS 為例，它就提供了 L4 與 L7 的 Load Balancer 供客戶使用，架構師可以依據企業的使用場景選擇最合適的解決方案。

3. 企業對於網路服務除了基本的功能要求，可能還需要考慮服務的可用性，如果在系統架構上使用到 Proxy 或是 Load Balancer 這類的服務，也可以考慮結合 Keepalived 這類的工具達到功效。

當我們啟動 docker compose 後，使用 client 向運作 TinyLB 的主機發送 http request，我們預期會隨機收到來自不同 server 的 http response：

ianchen0119@ubuntu:~/tinyLB$ docker exec -it client bash
root@b60c1a10494d:/# curl 192.17.0.5
Server address: 192.17.0.3:80
Server name: c95fff50b9b8
Date: 11/Dec/2022:11:29:24 +0000
URI: /
Request ID: 8adb3231c99ae0838a66bf330f8a6f71
root@b60c1a10494d:/# 

Client 的請求會被 Load balancer 導向到隨機的後端伺服器

原始程式碼解說

讓我們透過閱讀原始程式碼的方式逐步的實作 TinyLB：

#include "xdp_lb_kern.h"

#define IP_ADDRESS(x) (unsigned int)(192 + (17 << 8) + (0 << 16) + (x << 24))
#define BACKEND_A 2
#define BACKEND_B 3
#define CLIENT 4
#define LB 5
#define HTTP_PORT 80

SEC("xdp_lb")
int xdp_load_balancer(struct xdp_md *ctx)
{

}

char _license[] SEC("license") = "GPL";

首先，我們定義了：

• 一個取得 IP 的 macro IP_ADDRESS，它只是方便我們將 IP 轉換成與網路方包 raw data 一致的格式，比如說：IP_ADDRESS(5) 表示 192.17.0.5，即 tinyLB 的 IP 位址。
• 宣告一個 eBPF program（xdp_lb）
• 宣告範例的 License

接著，讓我們思考一下當作業系統從網路卡收到一個 HTTP 請求的網路封包，它應該是什麼樣子：

| ETHERNET HEADER (L2) | IP HEADER (L3) | TCP HEADER (L4) | DATA (L5) |

因此，我們應該先從 L2 開始解析：

void *data = (void *)(long)ctx->data;
void *data_end = (void *)(long)ctx->data_end;

struct ethhdr *eth = data;
if (data + sizeof(struct ethhdr) > data_end)
    return XDP_ABORTED;

if (bpf_ntohs(eth->h_proto) != ETH_P_IP)
    return XDP_PASS;

• 上面的程式碼會檢查封包的長度是否合法：如果封包的起始位址加上 ETHERNET HEADER 的大小後，記憶體空間會超過封包的截止位址，那麽該封包就是非法的。
• 同時，我們也會檢查 L3 的網路協定是否為 IP，如果不是，我們就讓它直接進入到作業系統的 Networking Stack（因為如果不是 IP 封包，那麼它一定不是 HTTP 封包）。

確認封包的正確性後，開始處理 L3 的部分：

struct iphdr *iph = data + sizeof(struct ethhdr);
if (data + sizeof(struct ethhdr) + sizeof(struct iphdr) > data_end)
    return XDP_ABORTED;

if (iph->protocol != IPPROTO_TCP)
    return XDP_PASS;

• 首先一樣驗證封包的長度是否合法，由於已經進入到 L3 了，所以我們會把 IP HEADER 加進去計算。
• 接著，我們進一步驗證 L4 的網路協定是否為 TCP，如果不是就讓封包進入 Networking Stack。

到了 L4，我們除了檢驗封包長度之外，還會需要對封包動手腳：

// PART 0
struct tcphdr *tcph = data + sizeof(struct ethhdr) + sizeof(struct iphdr);
if (data + sizeof(struct ethhdr) + sizeof(struct iphdr) + sizeof(struct tcphdr) > data_end)
    return XDP_ABORTED;

// PART 1
int flag = 1;

if (iph->saddr == IP_ADDRESS(CLIENT) && bpf_ntohs(tcph->dest) == HTTP_PORT)
{
    bpf_printk("Got http request from %x", iph->saddr);
    char dst = BACKEND_A;
    if (bpf_ktime_get_ns() % 2)
        dst = BACKEND_B;

    iph->daddr = IP_ADDRESS(dst);
    eth->h_dest[5] = dst;
} else if (iph->saddr == IP_ADDRESS(BACKEND_A) || iph->saddr == IP_ADDRESS(BACKEND_B))
{
    // PART 2
    bpf_printk("Got the http response from backend [%x]: forward to client %x", iph->saddr, iph->daddr);
    iph->daddr = IP_ADDRESS(CLIENT);
    eth->h_dest[5] = CLIENT;
} else {
    // PART 3
    flag = 0;
}

• 首先，我們預設該封包是需要修改的（令 flag 為 1），接著檢查封包的來源是否為 Client，如果是，我們再檢查它的 Dst port 是否為 80（HTTP 使用的 Port Number）。如果前面的條件都符合，eBPF program 就會修改該封包的 Dst IP，讓他能夠傳送到 BACKEND_A 或是 BACKEND_B。
• 如果上述條件不符合，則進一步檢查封包的來源是否為 BACKEND_A 或是 BACKEND_B（我們在這個情境假設這兩個 Server 除了回應 HTTP response 以外，不會向 Load Balancer 傳送 TCP 封包）。如果條件符合，我們判斷這是回應先前 Client 請求的 response，因此，eBPF program 會將該封包的 Dst IP 修改為 Client 的 IP。
• 如果上述條件都不符合，我們就判斷這是屬於其他 traffic 的網路封包，將它標記為不修改。

前面的範例都是修改封包的 DST IP，要讓網路封包能夠順利轉發，我們需要連封包的來源 IP 與 checksum 一起更新：

if (!flag) {
    return XDP_PASS;
}
iph->saddr = IP_ADDRESS(LB);
eth->h_source[5] = LB;

iph->check = iph_csum(iph);

return XDP_TX;

• 如果標記為不修改，讓該封包進入 Networking Stack。
• 否則修改它的 Source IP 與 Checksum 然後轉發出去。

如果想要查看 Load Balancer 的 log，我們可以在運作 compose 的主機中輸入下列命令：

sudo cat /sys/kernel/debug/tracing/trace_pipe

預期的輸出結果

筆者補充：

如果對於 Load Balancer 與 Reverse Proxy 的差別感到疑惑，建議可以參考這篇國外文章：Proxy vs Reverse Proxy vs Load Balancer。

總結

在這篇文章中，筆者快速地向各位介紹 eBPF 以及 XDP 兩大技術，在這個微服務架構當道的世代，eBPF 與 XDP 其實已經被應用到許多成熟的專案上，像是：

• 由 Meta 維護的 L4 Load Balancer：Katran
• Cilium
• Linux Foundation 維護的 IO Visor
• 可用於追蹤微服務 network traffic 的 coroot 專案

不僅如此，對於系統維運者，eBPF 技術除了追蹤系統狀態，還能被應用於惡意流量的阻擋（詳細資訊可以參考這篇文章：使用 xdp-filter 進行高性能流量過濾以防止 DDoS 攻擊 | Red Hat）。

1. 完整的程式碼請參考：https://github.com/ENSREG/tinyLB

2. 如果對作業系統的網路處理議題有興趣，也可以參考筆者今年的鐵人賽系列文：5G 核心網路與雲原生開發之亂彈阿翔

3. 如果你對於擔任系統程式教材的翻譯志工有興趣，也歡迎留言讓我知道。

最後，如果覺得小弟的文章寫得不錯，也歡迎追蹤我的 GitHub 以及 Medium 唷！

參考資料

• https://lpc.events/event/7/contributions/671/attachments/561/992/xdp-multiprog.pdf
• https://github.com/xdp-project/xdp-tutorial
• https://www.youtube.com/watch?v=L3_AOFSNKK8
• https://github.com/ENSREG/tinyLB
• https://hackmd.io/@sysprog/linux-ebpf