BPF_MAP_TYPE_BLOOM_FILTER¶
注意
BPF_MAP_TYPE_BLOOM_FILTER是在内核版本 5.16 中引入的
BPF_MAP_TYPE_BLOOM_FILTER 提供了一个 BPF Bloom 过滤器映射。Bloom 过滤器是一种空间效率高的概率数据结构，用于快速测试元素是否存在于集合中。在 Bloom 过滤器中，可能会出现假阳性，但不会出现假阴性。
Bloom 过滤器映射没有键，只有值。创建 Bloom 过滤器映射时，必须使用 key_size 为 0 创建。Bloom 过滤器映射支持两个操作
push：将元素添加到映射
peek：确定元素是否存在于映射中
BPF 程序必须使用 bpf_map_push_elem 将元素添加到 Bloom 过滤器映射，并使用 bpf_map_peek_elem 查询映射。这些操作通过以下方式使用现有的 bpf 系统调用暴露给用户空间应用程序
BPF_MAP_UPDATE_ELEM-> pushBPF_MAP_LOOKUP_ELEM-> peek
在创建映射时指定的 max_entries 大小用于近似 Bloom 过滤器的合理位图大小，否则不会严格强制执行。如果用户希望在 Bloom 过滤器中插入比 max_entries 更多的条目，这可能会导致更高的假阳性率。
用于 Bloom 过滤器的哈希数可以使用创建映射时 union bpf_attr 中 map_extra 的低 4 位进行配置。如果未指定数字，则默认使用 5 个哈希函数。通常，使用更多哈希会降低假阳性率和查找速度。
无法从 Bloom 过滤器映射中删除元素。Bloom 过滤器映射可以用作内部映射。用户负责同步并发更新和查找，以确保不会发生假阴性查找。
用法¶
内核 BPF¶
bpf_map_push_elem()¶
long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
可以使用 bpf_map_push_elem() 辅助函数将 value 添加到 Bloom 过滤器。flags 参数在向 Bloom 过滤器添加条目时必须设置为 BPF_ANY。此辅助函数在成功时返回 0，如果失败则返回负错误。
bpf_map_peek_elem()¶
long bpf_map_peek_elem(struct bpf_map *map, void *value)
bpf_map_peek_elem() 辅助函数用于确定 value 是否存在于 Bloom 过滤器映射中。如果 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 添加到 Bloom 过滤器。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 函数确定 Bloom 过滤器中是否存在 value。key 参数必须设置为 NULL。如果 value 可能存在于映射中，则返回 0，如果 value 肯定不存在于映射中，则返回 -ENOENT。
示例¶
内核 BPF¶
此代码段显示如何在 BPF 程序中声明 Bloom 过滤器
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER);
__type(value, __u32);
__uint(max_entries, 1000);
__uint(map_extra, 3);
} bloom_filter SEC(".maps");
此代码段显示如何在 BPF 程序中确定 Bloom 过滤器中是否存在值
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 从用户空间创建 Bloom 过滤器映射
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 */
}
此代码段显示如何从用户空间向 Bloom 过滤器添加元素
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);
}
参考¶
https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/