BPF_MAP_TYPE_HASH，帶 PERCPU 和 LRU 變體¶
注意
BPF_MAP_TYPE_HASH在核心版本 3.19 中引入BPF_MAP_TYPE_PERCPU_HASH在版本 4.6 中引入BPF_MAP_TYPE_LRU_HASH和BPF_MAP_TYPE_LRU_PERCPU_HASH都在版本 4.10 中引入
BPF_MAP_TYPE_HASH 和 BPF_MAP_TYPE_PERCPU_HASH 提供通用雜湊對映儲存。鍵和值都可以是結構體，允許複合鍵和值。
核心負責分配和釋放鍵/值對，直到您指定的最大條目限制。雜湊對映預設使用雜湊表元素的預分配。BPF_F_NO_PREALLOC 標誌可用於在記憶體開銷過大時停用預分配。
BPF_MAP_TYPE_PERCPU_HASH 為每個 CPU 提供一個單獨的值槽。每個 CPU 的值內部儲存在一個數組中。
BPF_MAP_TYPE_LRU_HASH 和 BPF_MAP_TYPE_LRU_PERCPU_HASH 變體為其各自的雜湊表添加了 LRU 語義。當雜湊表達到容量時，LRU 雜湊將自動逐出最近最少使用的條目。LRU 雜湊維護一個內部 LRU 列表，用於選擇要逐出的元素。此內部 LRU 列表在 CPU 之間共享，但在呼叫 bpf_map_create 時，可以使用 BPF_F_NO_COMMON_LRU 標誌請求每個 CPU 的 LRU 列表。下表概述了 LRU 對映的屬性，具體取決於對映型別和用於建立對映的標誌。
標誌 |
|
|
|---|---|---|
BPF_F_NO_COMMON_LRU |
每個 CPU 的 LRU，全域性對映 |
每個 CPU 的 LRU，每個 CPU 的對映 |
!BPF_F_NO_COMMON_LRU |
全域性 LRU，全域性對映 |
全域性 LRU，每個 CPU 的對映 |
用法¶
核心 BPF¶
bpf_map_update_elem()¶
long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
可以使用 bpf_map_update_elem() 輔助函式新增或更新雜湊條目。此輔助函式原子地替換現有元素。flags 引數可用於控制更新行為
BPF_ANY將建立新元素或更新現有元素BPF_NOEXIST僅在元素不存在時建立新元素BPF_EXIST將更新現有元素
bpf_map_update_elem() 成功時返回 0，失敗時返回負錯誤碼。
bpf_map_lookup_elem()¶
void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_lookup_elem() 輔助函式檢索雜湊條目。此輔助函式返回指向與 key 關聯的值的指標，如果未找到條目，則返回 NULL。
bpf_map_delete_elem()¶
long bpf_map_delete_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_delete_elem() 輔助函式刪除雜湊條目。此輔助函式成功時返回 0，失敗時返回負錯誤碼。
每個 CPU 的雜湊¶
對於 BPF_MAP_TYPE_PERCPU_HASH 和 BPF_MAP_TYPE_LRU_PERCPU_HASH，bpf_map_update_elem() 和 bpf_map_lookup_elem() 輔助函式自動訪問當前 CPU 的雜湊槽。
bpf_map_lookup_percpu_elem()¶
void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)
可以使用 bpf_map_lookup_percpu_elem() 輔助函式在特定 CPU 的雜湊槽中查詢值。返回與 cpu 上的 key 關聯的值，如果未找到條目或 cpu 無效，則返回 NULL。
併發¶
儲存在 BPF_MAP_TYPE_HASH 中的值可以由在不同 CPU 上執行的程式併發訪問。自核心版本 5.1 起，BPF 基礎設施提供了 struct bpf_spin_lock 來同步訪問。參見 tools/testing/selftests/bpf/progs/test_spin_lock.c。
使用者空間¶
bpf_map_get_next_key()¶
int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)
在使用者空間中，可以使用 libbpf 的 bpf_map_get_next_key() 函式遍歷雜湊的鍵。透過呼叫 bpf_map_get_next_key() 並將 cur_key 設定為 NULL，可以獲取第一個鍵。後續呼叫將獲取當前鍵的下一個鍵。bpf_map_get_next_key() 成功時返回 0，如果 cur_key 是雜湊中的最後一個鍵則返回 -ENOENT，失敗時返回負錯誤碼。
請注意，如果 cur_key 被刪除，則 bpf_map_get_next_key() 將返回雜湊表中的第一個鍵，這是不希望的。如果鍵刪除與 bpf_map_get_next_key() 混用，建議使用批次查詢。
示例¶
請參閱 tools/testing/selftests/bpf 目錄以獲取功能示例。下面的程式碼片段演示了 API 用法。
此示例演示如何宣告一個帶有結構體鍵和結構體值的 LRU 雜湊。
#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>
struct key {
__u32 srcip;
};
struct value {
__u64 packets;
__u64 bytes;
};
struct {
__uint(type, BPF_MAP_TYPE_LRU_HASH);
__uint(max_entries, 32);
__type(key, struct key);
__type(value, struct value);
} packet_stats SEC(".maps");
此示例演示如何使用原子指令建立或更新雜湊值
static void update_stats(__u32 srcip, int bytes)
{
struct key key = {
.srcip = srcip,
};
struct value *value = bpf_map_lookup_elem(&packet_stats, &key);
if (value) {
__sync_fetch_and_add(&value->packets, 1);
__sync_fetch_and_add(&value->bytes, bytes);
} else {
struct value newval = { 1, bytes };
bpf_map_update_elem(&packet_stats, &key, &newval, BPF_NOEXIST);
}
}
使用者空間遍歷上述宣告的對映元素
#include <bpf/libbpf.h>
#include <bpf/bpf.h>
static void walk_hash_elements(int map_fd)
{
struct key *cur_key = NULL;
struct key next_key;
struct value value;
int err;
for (;;) {
err = bpf_map_get_next_key(map_fd, cur_key, &next_key);
if (err)
break;
bpf_map_lookup_elem(map_fd, &next_key, &value);
// Use key and value here
cur_key = &next_key;
}
}
內部實現¶
本文件的此部分面向 Linux 開發人員，描述了對映實現中不被視為穩定 ABI 的方面。以下細節可能會在核心的未來版本中發生變化。
BPF_MAP_TYPE_LRU_HASH 及其變體¶
更新 LRU 對映中的元素時，當對映容量達到上限時，可能會觸發逐出行為。更新演算法嘗試了各種步驟來強制執行 LRU 屬性，這些步驟對涉及以下操作嘗試的其他 CPU 產生了越來越大的影響
嘗試使用 CPU 本地狀態批次操作
嘗試從全域性列表中獲取
target_free空閒節點嘗試從全域性列表中拉取任何節點並將其從雜湊對映中移除
嘗試從任何 CPU 的列表中拉取任何節點並將其從雜湊對映中移除
一次從全域性列表借用的節點數量，target_free，取決於對映的大小。更大的批次大小會減少鎖競爭，但也可能耗盡全域性結構。該值在對映初始化時計算，透過將所有 CPU 的總保留限制在對映大小的一半來避免耗盡，最小值為單個元素，最大預算為每次 128 個。
此演算法在下圖中有視覺描述。有關相應操作的完整解釋，請參閱 commit 3a08c2fd7634 (“bpf: LRU List”) 中的描述
BPF_MAP_TYPE_LRU_HASH 及其變體在對映更新期間的 LRU 雜湊逐出。有關核心函式名稱程式碼引用，請參閱點檔案源。¶
對映更新從右上角的橢圓形“begin bpf_map_update()”開始，透過圖表向下推進，最終結果可能是成功更新或帶有各種錯誤程式碼的失敗。右上角的圖例提供了特定操作可能涉及的鎖的指示符。這旨在作為推理對映爭用如何影響更新操作的視覺提示，儘管對映型別和標誌可能會根據上表中描述的邏輯影響這些鎖的實際爭用。例如，如果對映是使用型別 BPF_MAP_TYPE_LRU_PERCPU_HASH 和標誌 BPF_F_NO_COMMON_LRU 建立的，則所有對映屬性都將是每個 CPU 的。