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;
}
}