BPF_MAP_TYPE_LPM_TRIE¶
注意
BPF_MAP_TYPE_LPM_TRIE在内核版本4.11中引入
BPF_MAP_TYPE_LPM_TRIE 提供最长前缀匹配算法，可用于将 IP 地址与存储的前缀集进行匹配。在内部，数据存储在一个不平衡的节点 trie 中，该 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 类型的映射时，必须设置 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，其名称与上述相同，映射由 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 元素。这意味着迭代将先返回更具体的键，然后再返回不太具体的键。
示例¶
有关从用户空间使用 LPM trie 的示例，请参阅 tools/testing/selftests/bpf/test_lpm_map.c。以下代码片段演示了 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;
}
}