BPF_MAP_TYPE_BLOOM_FILTER¶
注意
BPF_MAP_TYPE_BLOOM_FILTER在内核版本 5.16 中引入
BPF_MAP_TYPE_BLOOM_FILTER 提供了一个 BPF 布隆过滤器映射。布隆过滤器是一种节省空间的概率数据结构，用于快速测试元素是否存在于集合中。在布隆过滤器中，可能出现误报，但不会出现漏报。
布隆过滤器映射没有键，只有值。创建布隆过滤器映射时，必须使用 key_size 为 0 创建。布隆过滤器映射支持两种操作
push：将元素添加到映射
peek：确定元素是否存在于映射中
BPF 程序必须使用 bpf_map_push_elem 将元素添加到布隆过滤器映射，并使用 bpf_map_peek_elem 查询映射。这些操作通过以下方式使用现有的 bpf 系统调用暴露给用户空间应用程序
BPF_MAP_UPDATE_ELEM-> pushBPF_MAP_LOOKUP_ELEM-> peek
在映射创建时指定的 max_entries 大小用于近似布隆过滤器的合理位图大小，并且不会以其他方式严格强制执行。如果用户希望在布隆过滤器中插入比 max_entries 更多的条目，可能会导致更高的误报率。
用于布隆过滤器的哈希数可以通过在映射创建时在 union bpf_attr 中的 map_extra 的低 4 位进行配置。如果未指定数字，则默认使用 5 个哈希函数。一般来说，使用更多的哈希会降低误报率和查找速度。
无法从布隆过滤器映射中删除元素。布隆过滤器映射可以用作内部映射。用户负责同步并发更新和查找，以确保不会发生误报查找。
用法¶
内核 BPF¶
bpf_map_push_elem()¶
long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
可以使用 bpf_map_push_elem() 助手将 value 添加到布隆过滤器。将条目添加到布隆过滤器时，flags 参数必须设置为 BPF_ANY。此助手在成功时返回 0，或者在失败时返回负错误。
bpf_map_peek_elem()¶
long bpf_map_peek_elem(struct bpf_map *map, void *value)
bpf_map_peek_elem() 助手用于确定 value 是否存在于布隆过滤器映射中。如果 value 可能存在于映射中，则此助手返回 0；如果 value 肯定不存在于映射中，则返回 -ENOENT。
用户空间¶
bpf_map_update_elem()¶
int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)
用户空间程序可以使用 libbpf 的 bpf_map_update_elem 函数将 value 添加到布隆过滤器。key 参数必须设置为 NULL，并且 flags 必须设置为 BPF_ANY。成功时返回 0，或者在失败时返回负错误。
bpf_map_lookup_elem()¶
int bpf_map_lookup_elem (int fd, const void *key, void *value)
用户空间程序可以使用 libbpf 的 bpf_map_lookup_elem 函数确定 value 是否存在于布隆过滤器中。key 参数必须设置为 NULL。如果 value 可能存在于映射中，则返回 0；如果 value 肯定不存在于映射中，则返回 -ENOENT。
示例¶
内核 BPF¶
此代码段显示如何在 BPF 程序中声明布隆过滤器
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER);
__type(value, __u32);
__uint(max_entries, 1000);
__uint(map_extra, 3);
} bloom_filter SEC(".maps");
此代码段显示如何在 BPF 程序中确定布隆过滤器中是否存在值
void *lookup(__u32 key)
{
if (bpf_map_peek_elem(&bloom_filter, &key) == 0) {
/* Verify not a false positive and fetch an associated
* value using a secondary lookup, e.g. in a hash table
*/
return bpf_map_lookup_elem(&hash_table, &key);
}
return 0;
}
用户空间¶
此代码段显示如何使用 libbpf 从用户空间创建布隆过滤器映射
int create_bloom()
{
LIBBPF_OPTS(bpf_map_create_opts, opts,
.map_extra = 3); /* number of hashes */
return bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER,
"ipv6_bloom", /* name */
0, /* key size, must be zero */
sizeof(ipv6_addr), /* value size */
10000, /* max entries */
&opts); /* create options */
}
此代码段显示如何从用户空间向布隆过滤器添加元素
int add_element(struct bpf_map *bloom_map, __u32 value)
{
int bloom_fd = bpf_map__fd(bloom_map);
return bpf_map_update_elem(bloom_fd, NULL, &value, BPF_ANY);
}