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/