BPF_MAP_TYPE_LPM_TRIE¶
注意
BPF_MAP_TYPE_LPM_TRIE在核心版本 4.11 中引入
BPF_MAP_TYPE_LPM_TRIE 提供了一種最長字首匹配演算法，可用於將 IP 地址與儲存的字首集進行匹配。 在內部，資料儲存在一個非平衡的 Trie 樹節點中，該節點使用 prefixlen,data 對作為其鍵。 data 以網路位元組順序（即大端序）解釋，因此 data[0] 儲存最高有效位元組。
LPM Trie 樹可以使用 8 到 2048 範圍內的最大字首長度建立，該長度是 8 的倍數。 用於查詢和更新操作的鍵是一個 struct bpf_lpm_trie_key_u8，擴充套件了 max_prefixlen/8 個位元組。
對於 IPv4 地址，資料長度為 4 個位元組
對於 IPv6 地址，資料長度為 16 個位元組
儲存在 LPM Trie 樹中的值型別可以是任何使用者定義的型別。
注意
建立 BPF_MAP_TYPE_LPM_TRIE 型別的 Map 時，必須設定 BPF_F_NO_PREALLOC 標誌。
用法¶
核心 BPF¶
bpf_map_lookup_elem()¶
void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_lookup_elem() 輔助函式找到給定資料值的最長字首條目。 此輔助函式返回指向與最長匹配 key 關聯的值的指標，如果未找到任何條目，則返回 NULL。
當執行最長字首查詢時，key 應將 prefixlen 設定為 max_prefixlen。 例如，當搜尋 IPv4 地址的最長字首匹配時，prefixlen 應設定為 32。
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() 輔助函式新增或更新字首條目。 此輔助函式以原子方式替換現有元素。
bpf_map_update_elem() 成功時返回 0，失敗時返回負錯誤。
注意
flags 引數必須是 BPF_ANY、BPF_NOEXIST 或 BPF_EXIST 之一，但該值將被忽略，從而給出 BPF_ANY 語義。
bpf_map_delete_elem()¶
long bpf_map_delete_elem(struct bpf_map *map, const void *key)
可以使用 bpf_map_delete_elem() 輔助函式刪除字首條目。 此輔助函式成功時將返回 0，失敗時返回負錯誤。
使用者空間¶
從使用者空間的訪問使用 libbpf API，API 名稱與上述相同，Map 由 fd 標識。
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() 函式遍歷 LPM Trie 樹中的條目。 可以透過呼叫 bpf_map_get_next_key() 並將 cur_key 設定為 NULL 來獲取第一個鍵。 後續呼叫將獲取當前鍵之後的下一個鍵。 bpf_map_get_next_key() 成功時返回 0，如果 cur_key 是 Trie 樹中的最後一個鍵，則返回 -ENOENT，失敗時返回負錯誤。
bpf_map_get_next_key() 將首先從最左邊的葉子遍歷 LPM Trie 樹元素。 這意味著迭代將首先返回更具體的鍵，然後再返回不太具體的鍵。
示例¶
請參閱 tools/testing/selftests/bpf/test_lpm_map.c 以獲取從使用者空間使用 LPM Trie 樹的示例。 以下程式碼段演示了 API 用法。
核心 BPF¶
以下 BPF 程式碼段顯示瞭如何宣告 IPv4 地址字首的新 LPM Trie 樹
#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>
struct ipv4_lpm_key {
__u32 prefixlen;
__u32 data;
};
struct {
__uint(type, BPF_MAP_TYPE_LPM_TRIE);
__type(key, struct ipv4_lpm_key);
__type(value, __u32);
__uint(map_flags, BPF_F_NO_PREALLOC);
__uint(max_entries, 255);
} ipv4_lpm_map SEC(".maps");
以下 BPF 程式碼段顯示瞭如何按 IPv4 地址查詢
void *lookup(__u32 ipaddr)
{
struct ipv4_lpm_key key = {
.prefixlen = 32,
.data = ipaddr
};
return bpf_map_lookup_elem(&ipv4_lpm_map, &key);
}
使用者空間¶
以下程式碼段顯示瞭如何將 IPv4 字首條目插入到 LPM Trie 樹中
int add_prefix_entry(int lpm_fd, __u32 addr, __u32 prefixlen, struct value *value)
{
struct ipv4_lpm_key ipv4_key = {
.prefixlen = prefixlen,
.data = addr
};
return bpf_map_update_elem(lpm_fd, &ipv4_key, value, BPF_ANY);
}
以下程式碼段顯示了一個使用者空間程式遍歷 LPM Trie 樹的條目
#include <bpf/libbpf.h>
#include <bpf/bpf.h>
void iterate_lpm_trie(int map_fd)
{
struct ipv4_lpm_key *cur_key = NULL;
struct ipv4_lpm_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;
}
}