Try   HackMD

eBPF and related tools

Design/Architecture

eBPF 和原先的 BPF 十分相似，特別的地方在於 eBPF map ，它是一種能夠儲存多種不同資料型態的資料結構，在當中每種不同資料型態被當成不同的二進位記憶體區塊來看待，因此使用者只需要告訴 eBPF map 想儲存的 key size 和 value size 即可。

user process 可以透過 file descriptor 來使用 eBPF map 同時可以創建多個 eBPF map ，對於同一個 eBPF map 而言，也允許多個 eBPF program 對它進行平行存取。

其中有一種特別的 map type 稱為 program array ，這種形態的 map 當中儲存的 file descriptor 是指向其他的 eBPF program ，當一個 eBPF program 對此 map 進行 lookup 後，程式執行會導向另一個 eBPF program 的開端且不會再 return 到原先的 calling program ，不過不允許無限的 nested call ，頂多 32 層。所有存在 program array map 當中的 eBPF program 都需要事先透過 bpf() 系統呼叫載入 kernel 當中，若 map lookup 失敗則原先的程式會繼續執行。

eBPF program 在載入 kernel 前需要先通過 in-kernel verifier 的靜態檢測，它會判斷該程式是否會終止還有是否每個指令都是安全的。而 eBPF program 可以被附加在多種不同事件上，不管是監聽網路封包、追蹤事件、透過 network queueing disciplines 進行事件分類還是其他任務。相關事件的發生會觸發 eBPF program 的執行。

System call

bpf() 系統呼叫會執行對應的 eBPF 操作，由 cmd 決定要進行何種操作， attr 則是給進的參數，是一個指向 bpf_attr 的指標，沒用到的 fields 都需要填上 zero ， size 則是 attr 指向的 union 的大小。
而 cmd 目前有以下幾種

  • BPF_MAP_CREATE
  • BPF_MAP_LOOKUP_ELEM
  • BPF_MAP_UPDATE_ELEM
  • BPF_MAP_DELETE_ELEM
  • BPF_MAP_GET_NEXT_KEY
  • BPF_PROG_LOAD

eBPF map

作為 eBPF 當中關鍵的資料結構，可以儲存多種不同型態的資料，同使允許多個 eBPF program 進行存取（可以達成共享記憶體），也允許 kernel space 和 user space 程式的存取。
每個 map type 都有以下四種屬性

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

建立 eBPF map

透過 BPF_MAP_CREATE 指令來進行，會回傳一個代表該 map 的 file descriptor

int
bpf_create_map(enum bpf_map_type map_type,
             unsigned int key_size,
             unsigned int value_size,
             unsigned int max_entries)
{
  union bpf_attr attr = {
      .map_type    = map_type,
      .key_size    = key_size,
      .value_size  = value_size,
      .max_entries = max_entries
  };

  return bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}

其中 verifier 會利用 key_size, value_size 在程式嘗試載入核心時檢查程式對於 bpf_map_*_elem() 等 helper functions 的操作是否安全，嘗試獲取的 value 都不能超過 value_size 。例如一個 value_size 為 1 的 map ，但 eBPF program 卻嘗試進行以下操作

value = bpf_map_lookup_elem(...);
*(u32 *) value = 1;

這段程式就會導致該 eBPF program 無法被載入核心，因為它嘗試對 value 獲取超過 1 byte 的空間。

搜索 map

透過 BPF_MAP_LOOKUP_ELEM 來尋找 fd 代表的 map 當中 key 所對應的 value 。

int
bpf_lookup_elem(int fd, const void *key, void *value)
{
  union bpf_attr attr = {
      .map_fd = fd,
      .key    = ptr_to_u64(key),
      .value  = ptr_to_u64(value),
  };

  return bpf(BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
}

若對應元素被找到，則該系統呼叫會回傳 0 ，並且將元素的值存進 value 當中，指向一個大小為 value_size 的 buffer 。

更新 map

透過 BPF_MAP_UPDATE_ELEM 來建立或更新 key/value 元素。

int
bpf_update_elem(int fd, const void *key, const void *value,
              uint64_t flags)
{
  union bpf_attr attr = {
      .map_fd = fd,
      .key    = ptr_to_u64(key),
      .value  = ptr_to_u64(value),
      .flags  = flags,
  };

  return bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
}

其中 flags 需要是以下三者其中一個

  • BPF_ANY : 建立新元素或更新已存在的元素
  • BPF_NOEXIST : 當對應元素不存在時，建立該元素
  • BPF_EXIST : 更新已存在的元素

刪除 map 當中元素

透過 BPF_MAP_DELETE_ELEM 指令來刪除 key 對應的元素。

int
bpf_delete_elem(int fd, const void *key)
{
  union bpf_attr attr = {
      .map_fd = fd,
      .key    = ptr_to_u64(key),
  };

  return bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
}

注意若沒找到對應元素則會回傳錯誤。

獲取 map 下一個元素

透過 BPF_MAP_GET_NEXT_KEY 來搜索 key 對應之元素並將 next_key 指向下一個元素。

int
bpf_get_next_key(int fd, const void *key, void *next_key)
{
  union bpf_attr attr = {
      .map_fd   = fd,
      .key      = ptr_to_u64(key),
      .next_key = ptr_to_u64(next_key),
  };

  return bpf(BPF_MAP_GET_NEXT_KEY, &attr, sizeof(attr));
}

若有找到 key 並且存在下一個元素，則回傳 0 並把 next_key 指向下一個元素的 key 。若找不到 key 則回傳 0 並把 next_key 指向第一個元素的 key 。若 key 指向最後一個元素，則回傳 -1 。這個方法可以用來歷遍 map 當中所有元素。

eBPF map types

  • BPF_MAP_TYPE_HASH
    • 由使用者層級程式創建與刪除，使用者與核心 eBPF program 皆可以進行查詢、更新與刪除的操作。
    • 核心層級負責配置空間與刪除 key/value pair
    • 當元素數量超過 max_entries 時 map_update_elem() 會失敗
    • map_update_elem() 若找到對應的元素，則更新過程是 atomic 的。
    • 優勢在於查詢速度
  • BPF_MAP_TYPE_ARRAY
    • verifier compiler 可能可以把 constant key 變為 constant pointer ，若為 non-constant key 也可以轉為 direct pointer arithmetic ，因為 value_size 在 eBPF program life time 都不會變。
    • 所有陣列當中元素空間都會被事先配置好並進行 zero initialization 。
    • key 即是 array index ，而且大小必為 4 bytes 。
    • map_delete_elem() 必回傳 EINVAL ，因為元素不能被刪除
    • map_update_elem() 更新元素的方式為 nonatomic ，若要進行 atomic update ，應該使用 hash-table map 。使用 array maps 的情況可能有以下幾種
      • global eBPF variable : 只有一個元素的 array 而 key 必定為 0 ， values 則是 eBPF program 用來讓 events 之間溝通的 global variables 集合。
      • 把追蹤事件的行為整合為一個固定大小的集合
      • 統計 networking events
  • BPF_MAP_TYPE_PROG_ARRAY
    同樣是 array map 但 values 只保存代表其他 eBPF program 的 file descriptors 。所以 key_size , value_size 都會是 4 bytes 。通常會和 bpf_tail_call() 一起使用。

eBPF programs

BPF_PROG_LOAD 可以用來將 eBPF program 載入核心空間，若成功則會回傳對應的 file descriptor 。

char bpf_log_buf[LOG_BUF_SIZE];

int
bpf_prog_load(enum bpf_prog_type type,
             const struct bpf_insn *insns, int insn_cnt,
             const char *license)
{
   union bpf_attr attr = {
       .prog_type = type,
       .insns     = ptr_to_u64(insns),
       .insn_cnt  = insn_cnt,
       .license   = ptr_to_u64(license),
       .log_buf   = ptr_to_u64(bpf_log_buf),
       .log_size  = LOG_BUF_SIZE,
       .log_level = 1,
   };

   return bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}

其中不同的參數解說如下

  • insns : 代表 struct bpf_insn 指令的陣列
  • insn_cnt : insns 當中指令的數量
  • license : license string ，為 GPL compatible 來使該 eBPF program 可以呼叫 gpl_only 的 helper function 。
  • log_buf : 一個指向 caller-allocated buffer 的指標， in-kernel verifier 會在當中儲存 verification log 。我們可以利用當中的訊息來了解為何 verifier 會判定該 eBPF program 為不安全的。
  • log_size : 表示 log_buf 指向的 buffer 的大小，若該大小不足以存放所有 verifier messages ，則會回傳 -1 。

eBPF program types

prog_type 會決定該 eBPF program 可以呼叫哪些 kernel helper function 。同時也決定了程式的 intput format ，也就是 struct bpf_context 的格式。目前有以下數種 program types

  • BPF_PROG_TYPE_SOCKET_FILTER
  • BPF_PROG_TYPE_KPROBE
  • BPF_PROG_TYPE_SCHED_CLS
  • BPF_PROG_TYPE_SCHED_ACT

Functions

在 eBPF 當中， function, program, sub-program 等詞經常被交替使用。 program 代表一個只有單一參數的 function ，且 program 可以被附加在 hook point 上。 sub-programs 同時也被稱為 BPF-to-BPF functions ，為含有零到五個參數的函式，無法被 attach 到 hook point 上，通常由一個 program 或其他特殊機制來呼叫。

Calling convention

R0 register 是用來作為回傳值，函式在回傳前應該將該暫存器設定好值，除非他是 void function 。而 R1-R5 是用來當作參數的， R1 為第一個參數， R2 第二個，依此類推。注意此處參數的傳遞從來不會透過 stack 來傳，因此函式至多有五個參數，這是一個 hard limit 。 R1-5 在函式呼叫後會被限制住，並且無法從中讀取數值，直到它們被設為某個任意值。 R6-9 則是作為 callee 的暫存器，他們會在函式呼叫之間被保存。

BPF to BPF functions (sub-programs)

這個 feature 使得 BPF program 可以重複利用相同的 program logic 。每個函式最多可以有五個參數，每個函式開始時都會被分配一個全新的 stack frame ，而程式離開時會被釋放並重新利用。如果指向 stack 的指標也被當成參數傳入函式，則函式也能存取該 stack 的記憶體空間。而函式的呼叫深度至多 8 ，因此想用遞迴來完成函式幾乎不可能。

Function inlining

預設上編譯器會宣則將 function inline 或者將他保持為一個分開的函式。可以透過 __attribute((always_inline)) 或 __attribute__((noinline)) 來鼓勵編譯器是否將函式進行 inline 。 inlined function 在函式呼叫時不會造成 overhead 因為他們會被當作原本呼叫函式的一部分。

Tail calls

當函式呼叫搭配 tail calls 時，每個 program 可用的 stack size 會從 512 bytes 變為 256 bytes 。使用到 tail call 的函式可以重複利用當前的 stack frame 。預設上 kernel threads 可用的 stack size 僅有 8k 。透過減少最大可用的 stack size ，程式就比較不會用盡 stack space 或 overflow 。

Function by function verification

在 v5.6 前， verifier 會檢查每一次函式呼叫，也就是假設一個函式會被呼叫 10 次，則 verifier 針對每一次呼叫的不同參數都會進行一次檢查。

自從 v5.6 後， "static" function 和 "global" function 被區分開來， static function 依舊是用原本的方式檢查，但 global function 的檢驗則是利用 function by function verification 。這代表 verifier 會對所有函式進行一次檢驗，即使順序不固定。它會假設所有的 input value 都是可能的，因為它不會對每次函式呼叫都進行檢查。因次函式需要通過更多的 input checking 來通過 verifier 。

libbpf

Overview

包含一個 BPF loader ，會接收編譯後的 bpf object file 並準備將它們載入 linux kernel 當中，負責用來將 bpf program 給 loading, verifying 並 attach 到不同的 kernel hooks 上，使得 bpf developer 可以專注在 BPF program 的正確性和效能上。

  • 提供 high-level, low-level API 使得 userspace program 可以輕易的和 BPF program 互動， low-level API 則是包裝了所有 bpf system call 功能。
  • 提供 BPF object skeleton file 。 skeleton file 簡化了使用者層級程式和 BPF program 互動的方式，並且可以更輕易的取得 global variable 。
  • 提供 BPF-side API ，包括 BPF helper definition 、 BPF maps support 、 tracing helpers ，使得我們可以更簡單的撰寫 BPF program 。
  • 提供 BPF CO-RE ( Compile Once - Run Everywhere ) 機制，使得 BPF developer 撰寫的 BPF program 可以僅被編譯一次就在不同的 kernel version 中運作。

BPF App lifecycle and libbpf APIs

一個 BPF application 由數個 BPF program 、 BPF maps 和 global variables 組成。 這數個 BPF program 共享 global variable 。 libbpf 提供的 API 使得使用者層級的程式可以透過觸發 BPF application lifecycle 當中不同的 phase 來操控 BPF program 。

  • Open phase
    libbpf 解析 BPF object file 並探索 BPF maps 、 BPF program 和 global variables 。當 BPF application 被開啟後，使用者層級可以在所有 entities 被創建並載入之前對其內容進行更動。
  • Load Phase
    libbpf 建立 BPF maps ，處理 relocation 問題，並 verifiy 、 load BPF program into kernel 。在這個步驟 libbpf 會驗證 BPF application 的每個部分並將 BPF program 載入 kernel 當中，但沒有 BPF program 會被執行。在 Load phase 之後，我們可以對 BPF map state 進行初始化而不會因為 BPF program 的執行產生競爭。
  • Attachment phase
    libbpf 將 BPF program attach 到數個 BPF hook points 上。在這個步驟當中， BPF program 可以執行不同工作例如處理封包、更新 BPF maps 和 global variable 。
  • Tear down phase
    libbpf 將 BPF program 進行 detach 並從 kernel 當中卸載。刪除 BPF maps ，並且所有 BPF application 使用的資源都會被釋放。

BPF Object Skeleton File

BPF skeleton 提供一個介面讓 libbpf API 可以操作 BPF object 。 Skeleton code 會將 libbpf API 進行抽象化使得使用者層級操作 BPF program 更為簡單。 Skeleton code 同時也包含了 BPF object file 的 bytecode 表示法，簡化了部署你的 BPF code 的過程。由於將 BPF bytecode 進行內嵌，我們不需要在我們的 application binary 之外部署多餘的檔案。

透過將 BPF object 傳送給 bpftool 可以產生 skeleton header file (.skel.h) ，產生的檔案包含以下幾個函式，分別對應到不同的 BPF lifecycle 。

  • <name>__open() : 建立並開啟 BPF application 。
  • <name>__load() : 初始化、載入並驗證 BPF application 。
  • <name>__attach() : attach all auto-attachable BPF programs
  • <name>__destroy() : detache all BPF programs and free up all used resources

使用 skeleton code 可以輕鬆的和 BPF program 互動，包括存取底下對應的 BPF object ，原本透過 generic libbpf API 可以做的事，透過 BPF skeleton 依舊可行。包括以下更多的優點

  • BPF skeleton 提供的介面使得使用者層級可以使用 BPF global variable 。利用 memory map 將 global variable 映射到使用者層級的 struct ，使用者層級程式可以在 BPF load phase 之前透過這個 struct 對 BPF program 做初始化，並在之後對 BPF program 做 fetch 或 update 。
  • skel.h 檔案會將 BPF object file 當中的 maps, program 全部列出，透過上述提到的 struct fields 可以直接存取這些 BPF maps 和 program ，使得我們不需要使用 bpf_object_find_map_by_name(), bpf_object_find_program_by_name() 等 string-based lookups ，減少 BPF source code 造成的錯誤還有和 userspace program 進行同步的成本。
  • Ojbect file 的 embedded bytecode 表示法保證 skeleton 和 BPF object file 總是同步的。

BPF helpers

libbpf 提供給 BPF program 的 BPF-side API 使得他們可以和系統互動。例如印出 debugging message ，取得開機後的時間，和 BPF maps 互動等等。詳細可見 bpf-helpers(7)

eBPF verifier

eBPF 程式的安全性由以下兩個步驟決定

第一步進行 DAG check 來阻擋可能的 loops 以及其他 CFG validation ，特別是可以偵測到不會被執行到的指令。
第二步則是從第一個 insn 開始往下模擬所以可能路徑來檢查每個 insn 並觀察 registers 和 stack 的狀態改變。

假設程式一開始 register R1 存有的是一個 pointer to context ，型別是 PTR_TO_CTX ，此時如果 verifier 看見一個指令是 R2=R1 ，則 R2 的型別也會是 PTR_TO_CTX 。如果 R1 型別是 PTR_TO_CTX 但 R2=R1+R1 ，則 R2 型別會是 SCALAR_VALUE ，因為兩個 valid pointer 相加會組成一個 invalid pointer 。( 在 secure mode 當中， verifier 會拒絕這樣的程式)

若一個 register 從來沒有被寫入，則它為 unreadable

bpf_mov R0 = R2
bpf_exit

此程式會被拒絕，因爲 R2 從程式的開頭就為 unreadable

Last changed by 
 
I-HSIN Cheng
https://vax-r.github.io/
0
367

Read more

Rust learning note (2)

Rust 的錯誤大致分為兩種主要的種類， recoverable 和 unrecoverable ，對於 recoverable errors 例如找不到對應檔案，最有可能的處理方式是回報該問題並且重新嘗試該操作，對於 unrecoverable error 來說，那總是代表 bugs 的特徵，此情況會立即將程式停止。

Mar 1, 2025
Concurrency 學習筆記

電腦系統當中把排程任務的基本單元稱為行程，

Dec 20, 2024
Control Groups 解說

官方的定義是 cgroup 將 tasks 集合映射到子系統 (subsystem) 的集合上。 subsystem

Sep 11, 2024
sched_ext(6) : kernel branch breakdown

sched_ext kernel branch 提供給 scx 一個完整的 bpf 介面得以讓使用者利用 scx 撰寫自己的排程器，相較於將完整排程策略實作在 kernel space 當中， sched_ext 僅僅是提供一個雛形，有預設的排程策略，但實際上會利用 scx 載入的排程器。同時 EXT scheduling class 的優先權和 fair class 是相同的。

Jul 23, 2024
Read more from I-HSIN Cheng
Published on HackMD