BPF 圖資料結構

本文件描述了新式“圖”資料結構（linked_list、rbtree）的實現細節，特別關注驗證器對這些資料結構特定語義的實現。

儘管本文件中沒有引用任何特定的驗證器程式碼，但本文件假定讀者對 BPF 驗證器內部、BPF 對映和 BPF 程式編寫有一般性瞭解。

請注意，本文件的目的是描述這些圖資料結構的當前狀態。此處不作或不暗示語義或 API 的任何穩定性保證。

引言

BPF 對映 API 歷來是暴露各種型別資料結構供 BPF 程式使用的主要方式。一些資料結構與對映 API (HASH, ARRAY) 自然契合，而另一些則不然。因此，對於沒有 BPF 經驗的核心程式設計師來說，與後一類資料結構互動的程式可能難以理解。

幸運的是，一些曾導致必須使用 BPF 對映語義的限制已不再相關。隨著 kfuncs、kptrs 和任意上下文 BPF 分配器的引入，現在可以實現 BPF 資料結構，其 API 和語義與核心其餘部分暴露的 API 和語義更接近。

兩種此類資料結構——linked_list 和 rbtree——有許多共同的驗證細節。因為兩者都有“根”（linked_list 的“頭”）和“節點”，所以驗證器程式碼和本文件將共同功能稱為“graph_api”、“graph_root”、“graph_node”等。

除非另有說明，以下示例和語義適用於這兩種圖資料結構。

不穩定 API

使用 BPF 對映 API 實現的資料結構歷來使用 BPF 輔助函式——無論是標準的對映 API 輔助函式（如 bpf_map_update_elem）還是特定於對映的輔助函式。新式圖資料結構則使用 kfuncs 來定義其操作輔助函式。由於 kfuncs 沒有穩定性保證，因此這些資料結構的 API 和語義可以以在必要時打破向後相容性的方式演進。

新資料結構的根型別和節點型別在 uapi/linux/bpf.h 標頭檔案中不透明地定義。

鎖

新式資料結構是侵入式的，其定義類似於其原生核心對應物。

struct node_data {
  long key;
  long data;
  struct bpf_rb_node node;
};

struct bpf_spin_lock glock;
struct bpf_rb_root groot __contains(node_data, node);

linked_list 和 rbtree 的“根”型別都期望位於一個 map_value 中，該 map_value 也包含一個 bpf_spin_lock——在上面的示例中，兩個全域性變數都放置在單個值的 arraymap 中。驗證器認為此 spin_lock 與 bpf_rb_root 相關聯，因為它們都在同一個 map_value 中，並且在驗證操作樹的 BPF 程式時將強制要求持有正確的鎖。由於此鎖檢查發生在驗證時，因此沒有執行時開銷。

非擁有引用

動機

考慮以下 BPF 程式碼

struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */

bpf_spin_unlock(&lock);

從驗證器的角度來看，從 bpf_obj_new 返回的指標 n 的型別為 PTR_TO_BTF_ID | MEM_ALLOC，其中 btf_id 為 struct node_data 且 ref_obj_id 非零。由於它持有 n，因此程式擁有被指向物件（由 n 指向的物件）的生命週期。BPF 程式必須在退出前傳遞所有權——要麼透過 bpf_obj_drop （它 free 該物件），要麼透過 bpf_rbtree_add 將其新增到 tree 中。

（示例中的 ACQUIRED 和 PASSED 註釋分別表示“獲取所有權”和“傳遞所有權”的語句）

所有權傳遞後，驗證器應該如何處理 n？如果物件已透過 bpf_obj_drop free，答案很明顯：驗證器應該拒絕在 bpf_obj_drop 之後嘗試訪問 n 的程式，因為該物件不再有效。底層記憶體可能已被重用於其他分配、已解除對映等。

當所有權透過 bpf_rbtree_add 傳遞給 tree 時，答案就不那麼明顯了。驗證器可以強制執行與 bpf_obj_drop 相同的語義，但這會導致具有有用、常見編碼模式的程式被拒絕，例如：

int x;
struct node_data *n = bpf_obj_new(typeof(*n)); /* ACQUIRED */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n); /* PASSED */
x = n->data;
n->data = 42;

bpf_spin_unlock(&lock);

對 n->data 的讀取和寫入都將被拒絕。然而，驗證器可以做得更好，利用兩個細節：

  • 圖資料結構 API 只能在持有與圖根關聯的 bpf_spin_lock 時使用

  • 兩種圖資料結構都具有指標穩定性

    • 因為圖節點是透過 bpf_obj_new 分配的，並且從根新增/刪除涉及操作節點結構的 bpf_{list,rb}_node 欄位，所以在任一操作之後，圖節點都將保持在相同的地址。

因為任何新增或刪除的程式都必須持有相關的 bpf_spin_lock，所以如果我們在該鎖所限定的臨界區內，我們知道在臨界區結束之前，沒有其他程式可以新增或刪除。這與指標穩定性相結合意味著，在臨界區結束之前，即使在用於傳遞所有權之後，我們也可以透過 n 安全地訪問圖節點。

驗證器將此類引用視為非擁有引用。透過 bpf_obj_new 返回的引用因此被視為擁有引用。這兩個術語目前僅在圖節點和 API 的上下文中才有意義。

細節

讓我們列舉兩種引用型別的屬性。

擁有引用

  • 此引用控制被指向物件的生命週期

  • 被指向物件的所有權必須透過將其傳遞給某些圖 API kfunc 或透過 bpf_obj_drop （其 free 被指向物件）來“釋放”

    • 如果在程式結束前未釋放，驗證器將認為程式無效

  • 訪問被指向物件的記憶體不會發生頁面錯誤

非擁有引用

  • 此引用不擁有被指向物件

    • 它不能用於將圖節點新增到圖根，也不能透過 bpf_obj_drop free

  • 沒有明確的生命週期控制，但可以根據非擁有引用的存在推斷有效生命週期（參見下文解釋）

  • 訪問被指向物件的記憶體不會發生頁面錯誤

從驗證器的角度來看，非擁有引用只能存在於 spin_lock 和 spin_unlock 之間。為什麼？在 spin_unlock 之後，另一個程式可以對資料結構執行任意操作，例如透過 bpf_obj_drop 刪除和 free。對某個已被刪除、free 且透過 bpf_obj_new 重用的記憶體塊的非擁有引用將指向完全不同的東西。或者記憶體可能消失。

為了防止這種邏輯違反，驗證器會在臨界區結束後使所有非擁有引用失效。這是確保非擁有引用的“不會頁面錯誤”屬性所必需的。因此，如果驗證器尚未使非擁有引用失效，訪問它就不會發生頁面錯誤。

目前，臨界區內不允許使用 bpf_obj_drop，因此如果存在有效的非擁有引用，我們必然處於臨界區內，並且可以得出結論，該引用的記憶體尚未被釋放或被釋放後重用。

對 rbtree 中節點的任何引用_必須_是非擁有的，因為樹控制著被指向物件的生命週期。類似地，對不在 rbtree 中的節點的任何引用_必須_是擁有的。這產生了一個很好的特性：圖 API 的新增/刪除實現無需檢查節點是否已新增（或已刪除），因為所有權模型允許驗證器透過簡單地檢查型別來防止這種狀態有效。

然而，指標別名對上述“良好特性”提出了一個問題。考慮以下示例：

struct node_data *n, *m, *o, *p;
n = bpf_obj_new(typeof(*n));     /* 1 */

bpf_spin_lock(&lock);

bpf_rbtree_add(&tree, n);        /* 2 */
m = bpf_rbtree_first(&tree);     /* 3 */

o = bpf_rbtree_remove(&tree, n); /* 4 */
p = bpf_rbtree_remove(&tree, m); /* 5 */

bpf_spin_unlock(&lock);

bpf_obj_drop(o);
bpf_obj_drop(p); /* 6 */

假設在程式執行之前樹是空的。如果我們在此處使用上面註釋中的數字跟蹤驗證器狀態變化：

  1. n 是一個擁有引用

  2. n 是一個非擁有引用，它已被新增到樹中

  3. n 和 m 是非擁有引用，它們都指向同一個節點

  4. o 是一個擁有引用，n 和 m 是非擁有引用，它們都指向同一個節點

  5. o 和 p 是擁有引用，n 和 m 是非擁有引用，它們都指向同一個節點

  6. 發生了雙重釋放，因為 o 和 p 指向同一個節點，並且 o 在前一條語句中已被 free

狀態 4 和 5 違反了我們的“良好特性”，因為存在指向不在 rbtree 中的節點的非擁有引用。由於此違反，語句 5 將嘗試移除一個已移除的節點。狀態 6 是危險的雙重釋放。

我們至少應該防止狀態 6 的發生。如果我們也無法阻止狀態 5，那麼我們必須放棄我們的“良好特性”，並在執行時檢查節點是否已被移除。

我們透過泛化 bpf_spin_unlock 的“使非擁有引用失效”行為並在 bpf_rbtree_remove 之後進行類似的失效處理來防止這兩者。這裡的邏輯是，任何圖 API kfunc，如果它：

  • 接受一個任意節點引數

  • 將其從資料結構中移除

  • 返回對移除節點的擁有引用

都可能導致某個其他非擁有引用指向同一節點的狀態。因此，remove 型別的 kfuncs 也必須被視為非擁有引用失效點。