# 研讀 linux 核心之 bloom filter
[完整研究筆記](https://hackmd.io/eO4Y5Bf1Tcano4yN_6vbWw)
先釐清以下 (針對 kernel/bpf 目錄):
1. `kernel/bpf/bloom_filter.c` 的設計考量;
2. 為何使用 jhash，而非現有的 hash function?
3. bpf 如何運用 bloom filter (注意: 這段程式碼由 Meta/Facebook 貢獻，因此一定有真實世界的應用場景)，Meta 內部大量使用 bloom filter 和 eBPF;
4. 紀錄研讀 `Documentation/bpf/map_bloom_filter.rst` 的疑惑 (搭配 eBPF 閱讀)
:::warning
確保你的 Linux 系統有超過 12 GB 的容量，你需要取得完整的 Linux 核心原始程式碼並進行實驗
:::
:::success
1. `kernel/bpf/bloom_filter.c` 的設計考量;
:::
#### 1. Header file inclusion 和 macro definition 部分
```c
// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2021 Facebook */
#include <linux/bitmap.h>
#include <linux/bpf.h>
#include <linux/btf.h>
#include <linux/err.h>
#include <linux/jhash.h>
#include <linux/random.h>
#include <linux/btf_ids.h>
#define BLOOM_CREATE_FLAG_MASK \
(BPF_F_NUMA_NODE | BPF_F_ZERO_SEED | BPF_F_ACCESS_MASK)
```
#### 2. 結構定義
```c
struct bpf_bloom_filter {
struct bpf_map map; //
u32 bitset_mask;
u32 hash_seed; //
u32 nr_hash_funcs; // number of hash funciton
unsigned long bitset[];//
};
```
我覺得直觀的成員有 :
1. `hash_seed` : 用於驅動 hash functions 亂度之值
2. `nr_hash_funcs` : 即 number of hash functions k
3. `bitset[]` : 即 bloom filter 之核心 bit array
而我認為比較不值觀的是 :
1. `bpf_map` 結構之 map : 根據此 bloom filter 結構前綴有 bpf 表示此資料結構為針對 bpf 設計的一個 bloom filter ，因此內嵌一個 `bpf_map` 結構。但 bloom filter 是一通用工具，所以其他地方需要高效檢索時也能使用此 `bpf_bloom filter` 。
2. `bitset_mask` : 用於使經過 hash function 映射的過大 `h` 值限制在 bit array 大小範圍內 。 透過 `h & bitset_mask` 做類似取餘數動作(`h % nr_bits`)，取得一不超過 bit array 大小(`nr_bits`)的值作為 bit index 。
最後發現此結構是 include/linux/bpf.h 之 `bpf_map` 的改裝結構，是繼承了 `bpf_map` 再加上 bloom filter 的特定項 `bitset_mask` 、 `hash_seed` 、 `hash_funcs` 、 `bitset[]`。
#### 3. hash
src為以下
```c
static u32 hash(struct bpf_bloom_filter *bloom, void *value,
u32 value_size, u32 index)
{
u32 h;
if (likely(value_size % 4 == 0))
h = jhash2(value, value_size / 4, bloom->hash_seed + index);
else
h = jhash(value, value_size, bloom->hash_seed + index);
return h & bloom->bitset_mask;
}
```
此設計理念為根據每筆資料大小使用不同的 hash function。若每個 element 資料大小為 4 bytes 的倍數，即使用 專為處理之更高效的 jhash2。若非則使用 jhash。
而 index 的設計讓使用者只要將 index + 1 即可使用不同的 hash function，方便使用多個 hash function 之場合。
最後使用 bit array mask 與 hash value `h` 取按位元與，輸出之值為該資料經過一 hash function 之後映射到 bit array 之位置 index。
#### 4. kernel bloom filter operation function
以下為所有 function signature
```c
static long bloom_map_peek_elem(struct bpf_map *map, void *value);
static long bloom_map_push_elem(struct bpf_map *map, void *value, u64 flags);
static long bloom_map_pop_elem(struct bpf_map *map, void *value);
static long bloom_map_delete_elem(struct bpf_map *map, void *value);
static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key);
static void *bloom_map_lookup_elem(struct bpf_map *map, void *key);
static long bloom_map_update_elem(struct bpf_map *map, void *key, void *value, u64 flags);
```
真正支援的 map operation 只有兩個，`push` 與 `peek`。src 為以下 :
```c
static long bloom_map_peek_elem(struct bpf_map *map, void *value)
{
struct bpf_bloom_filter *bloom =
container_of(map, struct bpf_bloom_filter, map);
u32 i, h;
for (i = 0; i < bloom->nr_hash_funcs; i++) {
h = hash(bloom, value, map->value_size, i);
if (!test_bit(h, bloom->bitset))
return -ENOENT;
}
return 0;
}
static long bloom_map_push_elem(struct bpf_map *map, void *value, u64 flags)
{
struct bpf_bloom_filter *bloom =
container_of(map, struct bpf_bloom_filter, map);
u32 i, h;
if (flags != BPF_ANY)
return -EINVAL;
for (i = 0; i < bloom->nr_hash_funcs; i++) {
h = hash(bloom, value, map->value_size, i);
set_bit(h, bloom->bitset);
}
return 0;
}
```
peek 為檢察 value 有無在 set 裡。若有輸出 0，若無輸出 -`ENOENT`
* [`ENOENT` 全寫為 "Error NO ENTry"](https://stackoverflow.com/questions/19902828/why-does-enoent-mean-no-such-file-or-directory) ，意思為 no such file or directory。在 linux kernel 中是定義在 /include/uapi/asm-generic/errno-base.h 之 macro。定義是值為 2 之標準錯誤碼。而輸出多一個負號是因為錯誤碼形式通常為負數。
push 為將該 value 放入該 bloom filter set 中。若成功 push 進則輸出 0 ，若 flag 非輸入 BPF_ANY 則輸出 -`EINVAL`
* `EINVAL` 全寫是 "Error INvalid VALue"，意思是 Invalid argument。定義是值為 22 之標準錯誤碼。
* `BPF_ANY` 表示無條件插入或更新元素
以下是 `BPF_MAP_UPDATE_ELEM` 此 BPF_MAP operation 之 flag 設置，而 bloom filter 僅支援 `BPF_ANY`
```c
/* flags for BPF_MAP_UPDATE_ELEM command */
enum {
BPF_ANY = 0, /* create new element or update existing */
BPF_NOEXIST = 1, /* create new element if it didn't exist */
BPF_EXIST = 2, /* update existing element */
BPF_F_LOCK = 4, /* spin_lock-ed map_lookup/map_update */
};
```
而以下三個 map operation 不支援。`EOPNOTSUPP` 為標準錯誤號碼 45。
```c
static long bloom_map_pop_elem(struct bpf_map *map, void *value)
{
return -EOPNOTSUPP;
}
static long bloom_map_delete_elem(struct bpf_map *map, void *value)
{
return -EOPNOTSUPP;
}
static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
{
return -EOPNOTSUPP;
}
```
以下 map operation `lookup_elem` 與 `update_elem` 用 push、peek 取代。使用則輸出 -`EINVAL`。
```c
static void *bloom_map_lookup_elem(struct bpf_map *map, void *key)
{
/* The eBPF program should use map_peek_elem instead */
return ERR_PTR(-EINVAL);
}
static long bloom_map_update_elem(struct bpf_map *map, void *key,
void *value, u64 flags)
{
/* The eBPF program should use map_push_elem instead */
return -EINVAL;
}
```
#### 5. bpf type bloom filter 記憶體分配與管理
##### dynamic memory 分配前檢查
```c
/* Called from syscall */
static int bloom_map_alloc_check(union bpf_attr *attr)
{
if (attr->value_size > KMALLOC_MAX_SIZE)
/* if value_size is bigger, the user space won't be able to
* access the elements.
*/
return -E2BIG;
return 0;
}
```
`KMALLOC_MAX_SIZE` 是Linux核心中 `kmalloc` 函數能夠分配的最大內存塊大小。這個值通常在幾MB到幾十MB之間，具體取決於系統的配置。若 bloom filter 之 value_size 大於此大小則無法成功分配，最後輸出 -`W2BIG`。
##### 分配與初始化 map
```c
static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
{
u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
int numa_node = bpf_map_attr_numa_node(attr);
struct bpf_bloom_filter *bloom;
if (attr->key_size != 0 || attr->value_size == 0 ||
attr->max_entries == 0 ||
attr->map_flags & ~BLOOM_CREATE_FLAG_MASK ||
!bpf_map_flags_access_ok(attr->map_flags) ||
/* The lower 4 bits of map_extra (0xF) specify the number
* of hash functions
*/
(attr->map_extra & ~0xF))
return ERR_PTR(-EINVAL);
nr_hash_funcs = attr->map_extra;
if (nr_hash_funcs == 0)
/* Default to using 5 hash functions if unspecified */
nr_hash_funcs = 5;
/* For the bloom filter, the optimal bit array size that minimizes the
* false positive probability is n * k / ln(2) where n is the number of
* expected entries in the bloom filter and k is the number of hash
* functions. We use 7 / 5 to approximate 1 / ln(2).
*
* We round this up to the nearest power of two to enable more efficient
* hashing using bitmasks. The bitmask will be the bit array size - 1.
*
* If this overflows a u32, the bit array size will have 2^32 (4
* GB) bits.
*/
if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
nr_bits > (1UL << 31)) {
/* The bit array size is 2^32 bits but to avoid overflowing the
* u32, we use U32_MAX, which will round up to the equivalent
* number of bytes
*/
bitset_bytes = BITS_TO_BYTES(U32_MAX);
bitset_mask = U32_MAX;
} else {
if (nr_bits <= BITS_PER_LONG)
nr_bits = BITS_PER_LONG;
else
nr_bits = roundup_pow_of_two(nr_bits);
bitset_bytes = BITS_TO_BYTES(nr_bits);
bitset_mask = nr_bits - 1;
}
```
- 屬性設置檢查
```c
if (attr->key_size != 0 || attr->value_size == 0 ||
attr->max_entries == 0 ||
attr->map_flags & ~BLOOM_CREATE_FLAG_MASK ||
!bpf_map_flags_access_ok(attr->map_flags) ||
(attr->map_extra & ~0xF))
return ERR_PTR(-EINVAL);
```
這段程式碼驗證用戶傳入的參數是否合法，若不滿足條件則返回 -EINVAL 錯誤碼。具體檢查如下：
`attr->key_size != 0`
Bloom Filter 不需要鍵（key），因此鍵大小必須為 0。
`attr->value_size == 0`
值大小必須大於 0，因為 Bloom Filter 需要知道過濾的資料大小。
`attr->max_entries == 0`
最大條目數必須大於 0，否則地圖沒有意義。
`attr->map_flags & ~BLOOM_CREATE_FLAG_MASK`
檢查地圖標誌是否在允許範圍內。BLOOM_CREATE_FLAG_MASK 定義了有效的標誌位，若有超出範圍的位則返回錯誤。
`!bpf_map_flags_access_ok(attr->map_flags)`
進一步檢查標誌的訪問權限是否合法。
`(attr->map_extra & ~0xF)`
map_extra 的低 4 位（0xF）用於指定哈希函數數量，高位必須為 0。若高位有值，則參數無效。
若任一條件不滿足，函數立即返回錯誤，結束執行。
- hash function number 設置
```c
nr_hash_funcs = attr->map_extra;
if (nr_hash_funcs == 0)
nr_hash_funcs = 5;
```
由 `nr_hash_funcs = attr->map_extra;` 可知用戶通過 `map_extra` 的低 4 位指定 hash function number。
預設值為5：若未指定（即 nr_hash_funcs == 0），則預設為 5 個哈希函數。
- bit array 大小計算與設置
```c
if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
nr_bits > (1UL << 31)) {
bitset_bytes = BITS_TO_BYTES(U32_MAX);
bitset_mask = U32_MAX;
} else {
if (nr_bits <= BITS_PER_LONG)
nr_bits = BITS_PER_LONG;
else
nr_bits = roundup_pow_of_two(nr_bits);
bitset_bytes = BITS_TO_BYTES(nr_bits);
bitset_mask = nr_bits - 1;
}
```
分為以下步驟：
1. 理論最優 bit array 位元數
Bloom Filter 的最優位元數公式為：
$$ m = n * k / ln(2) $$
n : 預期條目數（attr->max_entries），
k : 哈希函數數量（nr_hash_funcs）。
這裡使用 7 / 5 近似 1 / ln(2)（因為 1 / ln(2) ≈ 1.4427，而 7 / 5 = 1.4），因此計算公式為：
`nr_bits` = (n * k * 7) / 5。
2. overflow 處理
使用 check_mul_overflow 檢查乘法是否溢出 u32。
若以下任一條件成立：
a. n * k 溢出，
b. (n * k / 5) * 7 溢出，
c. nr_bits > 2^31， 則設置：
`bitset_bytes = BITS_TO_BYTES(U32_MAX)`：bit array 大小設為 2^32 位元（即 4GB），轉換為位元組數。且 `bitset_mask = U32_MAX`：位掩碼設為最大值。
3. 正常情況處理(若無溢出)
- 最小值調整：若 nr_bits <= BITS_PER_LONG（通常為 64），則將 nr_bits 設為 BITS_PER_LONG，確保位陣列有最小規模。
- 向上取整：否則將 nr_bits 向上取整到最接近的 2 的冪次方（使用 roundup_pow_of_two），這是為了使用位掩碼進行高效哈希計算。
- 最終計算：
bitset_bytes = BITS_TO_BYTES(nr_bits)：將位元數轉換為位元組數（通常 8 位元 = 1 位元組）。
bitset_mask = nr_bits - 1：位掩碼用於快速取模運算（例如，若 nr_bits = 8，則 bitset_mask = 7，即 0b111）。
##### 釋放 map memory
```c
static void bloom_map_free(struct bpf_map *map)
{
struct bpf_bloom_filter *bloom =
container_of(map, struct bpf_bloom_filter, map);
bpf_map_area_free(bloom);
}
```
##### 驗證地圖為無鍵結構
```c
static int bloom_map_check_btf(const struct bpf_map *map,
const struct btf *btf,
const struct btf_type *key_type,
const struct btf_type *value_type)
{
/* Bloom filter maps are keyless */
return btf_type_is_void(key_type) ? 0 : -EINVAL;
}
```
##### 計算 memory 使用量
```c
static u64 bloom_map_mem_usage(const struct bpf_map *map)
{
struct bpf_bloom_filter *bloom;
u64 bitset_bytes;
bloom = container_of(map, struct bpf_bloom_filter, map);
bitset_bytes = BITS_TO_BYTES((u64)bloom->bitset_mask + 1);
bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long));
return sizeof(*bloom) + bitset_bytes;
}
```
#### 6. BTF(bpf type format) 之 bloom filter 之函式關係建立
src為以下
```c
BTF_ID_LIST_SINGLE(bpf_bloom_map_btf_ids, struct, bpf_bloom_filter)
const struct bpf_map_ops bloom_filter_map_ops = {
.map_meta_equal = bpf_map_meta_equal,
.map_alloc_check = bloom_map_alloc_check,
.map_alloc = bloom_map_alloc,
.map_free = bloom_map_free,
.map_get_next_key = bloom_map_get_next_key,
.map_push_elem = bloom_map_push_elem,
.map_peek_elem = bloom_map_peek_elem,
.map_pop_elem = bloom_map_pop_elem,
.map_lookup_elem = bloom_map_lookup_elem,
.map_update_elem = bloom_map_update_elem,
.map_delete_elem = bloom_map_delete_elem,
.map_check_btf = bloom_map_check_btf,
.map_mem_usage = bloom_map_mem_usage,
.map_btf_id = &bpf_bloom_map_btf_ids[0],
};
```
此部分主要是透過創建 include/uapi/linux/bpf.h `bpf_map_ops` 結構的 instance `bloom_filter_map_ops` 去連結 kernel 結構 `bpf_map` 對應成員關係，目的是讓使用者能調用 `bpf_map` 結構去呼叫到 `bloom_filter.c` 的函式。我覺得這樣子寫真是太棒了，既能讓使用者不用多記更多 API 語法，又能表達出 bloom filter 僅屬於 bpf_map 分支這樣的從屬關係。
#### BPF 整合：
```c
static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
{
if (attr->key_size != 0 || attr->value_size == 0 ||
attr->max_entries == 0 ||
attr->map_flags & ~BLOOM_CREATE_FLAG_MASK ||
!bpf_map_flags_access_ok(attr->map_flags) ||
(attr->map_extra & ~0xF))
return ERR_PTR(-EINVAL);
}
static void *bloom_map_lookup_elem(struct bpf_map *map, void *key)
{
return ERR_PTR(-EINVAL);
}
static long bloom_map_update_elem(struct bpf_map *map, void *key, void *value, u64 flags)
{
return -EINVAL;
}
const struct bpf_map_ops bloom_filter_map_ops = {
.map_push_elem = bloom_map_push_elem,
.map_peek_elem = bloom_map_peek_elem,
.map_lookup_elem = bloom_map_lookup_elem,
.map_update_elem = bloom_map_update_elem,
...
};
```
作為 BPF_MAP_TYPE_BLOOM_FILTER，專為 eBPF 設計，支援網路過濾、監控等高效場景。
無鍵設計（key_size = 0），僅儲存值，簡化操作並符合 Bloom Filter 特性。
提供 map_push_elem 和 map_peek_elem，禁用 lookup_elem、update_elem 等不適用操作，確保語義正確。
#### 靈活性與安全性：
```c
nr_hash_funcs = attr->map_extra;
if (nr_hash_funcs == 0)
nr_hash_funcs = 5;
if (!(attr->map_flags & BPF_F_ZERO_SEED))
bloom->hash_seed = get_random_u32();
int numa_node = bpf_map_attr_numa_node(attr);
bloom = bpf_map_area_alloc(sizeof(*bloom) + bitset_bytes, numa_node);
```
支援自訂雜湊函數數量（map_extra 低 4 位），預設 5 個，平衡效能與誤報率。
隨機種子（hash_seed）透過 get_random_u32() 生成（除非 BPF_F_ZERO_SEED），增強安全性。
支援 NUMA 分配（BPF_F_NUMA_NODE），提升記憶體存取效率。
#### 限制與簡化：
```c
static long bloom_map_delete_elem(struct bpf_map *map, void *value)
{
return -EOPNOTSUPP;
}
static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
{
return -EOPNOTSUPP;
}
static int bloom_map_alloc_check(union bpf_attr *attr)
{
if (attr->value_size > KMALLOC_MAX_SIZE)
return -E2BIG;
return 0;
}
```
- 不支援刪除（bloom_map_delete_elem 回傳 EOPNOTSUPP），因標準 Bloom Filter 不支援移除，簡化實作。
- 無鍵迭代（map_get_next_key 回傳 EOPNOTSUPP），因 Bloom Filter 非鍵值儲存。
- 值大小限制（KMALLOC_MAX_SIZE），避免用戶空間無法存取。
#### 錯誤處理與穩定性：
```c
/* Called from syscall */
static int bloom_map_alloc_check(union bpf_attr *attr)
{
if (attr->value_size > KMALLOC_MAX_SIZE)
/* if value_size is bigger, the user space won't be able to
* access the elements.
*/
return -E2BIG;
return 0;
}
```
分配檢查（bloom_map_alloc_check）確保參數有效（如 value_size）。
```c
if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
nr_bits > (1UL << 31)) {
bitset_bytes = BITS_TO_BYTES(U32_MAX);
bitset_mask = U32_MAX;
}
```
溢位檢查（check_mul_overflow）防止位陣列大小計算錯誤，若溢位則使用 U32_MAX（4GB 位元）。
```c
static int bloom_map_check_btf(const struct bpf_map *map,
const struct btf *btf,
const struct btf_type *key_type,
const struct btf_type *value_type)
{
return btf_type_is_void(key_type) ? 0 : -EINVAL;
}
```
BTF 檢查（bloom_map_check_btf）確保無鍵設計，檢查鍵型別為 void 以符合 BPF 規範。
:::success
2. 為何使用 jhash，而非現有的 hash function?
:::
核心之 hash 除了 jhash 外還有一些如 `hash_long`、`hash_ptr`（位於 include/linux/hash.h），用於簡單的數值或指標雜湊。或是 `siphash`（位於 include/linux/siphash.h）用於更高安全性的場景。或是在 crypto/ dir 的 `SHA-1`、`MD5` ，有複雜的計算，主要適用於驗證。
#### 高效能與低開銷
相較於加密雜湊（如 SHA），jhash 非加密用途，減少計算負擔。適合核心環境的高效能需求，尤其在網路封包處理等即時場景。
```c
if (likely(value_size % 4 == 0))
h = jhash2(value, value_size / 4, bloom->hash_seed + index);
else
h = jhash(value, value_size, bloom->hash_seed + index);
```
使用 jhash2（針對 4 字節對齊資料）或 jhash（通用情況），優化不同資料大小的處理。
#### 多雜湊支援
jhash 透過種子偏移（bloom->hash_seed + index）生成多個獨立雜湊值
```c
for (i = 0; i < bloom->nr_hash_funcs; i++) {
h = hash(bloom, value, map->value_size, i);
set_bit(h, bloom->bitset);
}
```
#### 良好分佈
是 Bob Jenkins 提出的 Jenkins 雜湊演算法的變體，專為快速、均勻分佈設計。該演算法透過多輪位元操作（移位、加法、異或）混合輸入資料，破壞輸入模式的規律性，確保輸出均勻。機制由以下概念實現
```c
#define __jhash_mix(a, b, c) \ // include/linux/jhash.h
{ \
a -= c; a ^= rol32(c, 4); c += b; \
b -= a; b ^= rol32(a, 6); a += c; \
c -= b; c ^= rol32(b, 8); b += a; \
a -= c; a ^= rol32(c, 16); c += b; \
b -= a; b ^= rol32(a, 19); a += c; \
c -= b; c ^= rol32(b, 4); b += a; \
}
```
jhash 和 jhash2 使用三個狀態變數（a, b, c）進行迭代混合，每次處理輸入資料的一部分。多次位元旋轉（rol32）與異或（^）操作打亂輸入資料的位元模式，確保小輸入差異產生大輸出差異（雪崩效應）。每輪混合將 a, b, c 相互影響，放大輸入的微小變化，減少輸出集中於特定值的可能性。
統整與其他核心 hash 比較，為何 jhash 最適合做為 bloom filter 之 hash structure
| 雜湊函數 | 均勻分佈 | 靈活性 | 安全性 | 多雜湊優化 | 效能 | 適用性 |
|------------|----------|------------------|----------------|------------------|------|----------|
| jhash | 高 | 高（任意資料） | 中（隨機種子） | 高（種子偏移） | 高 | 最適合 |
| hash_long | 低 | 低（僅數值） | 低（無種子） | 無 | 高 | 不適合 |
| hash_ptr | 低 | 低（僅指標） | 低（無種子） | 無 | 高 | 不適合 |
| siphash | 高 | 高（任意資料） | 高（隨機種子） | 中（種子偏移） | 中 | 次優 |
| SHA-1/MD5 | 高 | 高（任意資料） | 高（抗碰撞） | 低（高開銷） | 低 | 不適合 |
jhash 在均勻分佈、靈活性與安全性、多雜湊需求間取得最佳平衡，效能高且核心原生，適合 Bloom Filter 的即時場景。由 `commit b37a1b90d915` 可知道
:::success
3. bpf 如何運用 bloom filter (注意: 這段程式碼由 Meta/Facebook 貢獻，因此一定有真實世界的應用場景)，Meta 內部大量使用 bloom filter 和 eBPF;
:::
bloom filter 在 linux kernel 首次出現是由 Meta（Facebook）員工 [joanne koong 在 2021/08/31 提交的一個 patchset](https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/#t) 。且該 patchset 引入了 `BPF_MAP_TYPE_BLOOM_FILTER`。包含 5 個 patch：
1. `bpf: Add bloom filter map implementation`：核心實現（kernel/bpf/bloom_filter.c）。
2. `libbpf: Allow the number of hashes in bloom filter maps to be configurable`：支援用戶空間配置 hash function number。
3. `selftests/bpf: Add bloom filter map test cases`：添加測試用例。
4. `bpf/benchs: Add benchmark test for bloom filter maps`：基準測試。
5. `bpf/benchs: Add benchmarks for comparing hashmap lookups with vs. without bloom filter`：比較雜湊表查找性能。
從 linux kernel src [/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c](https://elixir.bootlin.com/linux/v6.12.28/source/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c) 中能看到此測試程式。而從 [v6 的 patch](https://patchwork.kernel.org/project/netdevbpf/patch/20211027234504.30744-6-joannekoong@fb.com/) 能看到 joanne koong 在benchmarks 中比較 hashmap hash table 中有無 bloom filter 中的效率。而在該 commit message 中可看到比較結果
```
This patch adds benchmark tests for comparing the performance of hashmap
lookups without the bloom filter vs. hashmap lookups with the bloom filter.
Checking the bloom filter first for whether the element exists should
overall enable a higher throughput for hashmap lookups, since if the
element does not exist in the bloom filter, we can avoid a costly lookup in
the hashmap.
On average, using 5 hash functions in the bloom filter tended to perform
the best across the widest range of different entry sizes. The benchmark
results using 5 hash functions (running on 8 threads on a machine with one
numa node, and taking the average of 3 runs) were roughly as follows:
value_size = 4 bytes -
10k entries: 30% faster
50k entries: 40% faster
100k entries: 40% faster
500k entres: 70% faster
1 million entries: 90% faster
5 million entries: 140% faster
value_size = 8 bytes -
10k entries: 30% faster
50k entries: 40% faster
100k entries: 50% faster
500k entres: 80% faster
1 million entries: 100% faster
5 million entries: 150% faster
value_size = 16 bytes -
10k entries: 20% faster
50k entries: 30% faster
100k entries: 35% faster
500k entres: 65% faster
1 million entries: 85% faster
5 million entries: 110% faster
value_size = 40 bytes -
10k entries: 5% faster
50k entries: 15% faster
100k entries: 20% faster
500k entres: 65% faster
1 million entries: 75% faster
5 million entries: 120% faster
```
此 commit message 道出 bloom filter 如何為 hashmap hash table 增加查詢效率。即是在要查表抓 key 對應之 value 前先用 bloom filter 檢查該 value 有無在表中。
對於 hash function number 部分，測試跑在一個 numa node 8 thread 的機器上之結果顯示為 5 個，能使在每種 `value_size` 都能有較好效能
從此測試結果來看，有著資料量越大，加入bloom filter 增加之效率越大。而有此定性的原因是隨著 `nr_entries` 增加，hash table query 的碰撞率和開銷上升，Bloom filter 透過快速過濾無關值（`bpf_map_peek_elem` 返回 `-ENOENT`）減少查詢次數，效率增益放大。
但單筆資料越大( `value_size` 越大)會讓 bloom filter 增加效率降低。此原因是較大的 `value_size` 增加 hash 計算（`jhash`）的開銷，因為 `bloom_map_push_elem` 和 `bloom_map_peek_elem` 需多次 hash（`nr_hash_funcs` = 5）。對應實際情況， Meta 的 packet filter（如 IP 位址，4-16 位元組）偏好小 `value_size`
結論是在數據集量大，每筆資料大小越小的情況下，增加 bloom filter 後能顯著增加 hash table 查詢效率。而最佳性能出現在高 `nr_entries`（500k-5M）和低 `value_size`（4-8 bytes），如 5M entries、value_size=8 快 150%。
#### 後續版本與改進
- v1 (2021-08-31)：初始提交，`引入 BPF_MAP_TYPE_BLOOM_FILTER`。
- v2-v6 (2021-09 至 2021-10)：
- [v3](https://lore.kernel.org/bpf/20210921210225.4095056-2-joannekoong%40fb.com/)：改進命名（如 bloom_map_* 前綴），添加 BTF 支援。
- [v4](https://lore.kernel.org/bpf/20211006222103.3631981-1-joannekoong%40fb.com/)：嘗試引入 bitset map（包含 Bloom filter 功能），後放棄。
- [v6](https://yhbt.net/lore/all/e8b531f2-71b2-044f-93be-2a42dfb3610a%40fb.com/)：最終版本，修正 `map_extra`（u64）、BTF 檢查，併入 Linux 5.16。
#### 而 bloom filter 在真實世界的應用 :
3. cache 優化：
場景：Meta 的 Presto 查詢引擎追蹤快取工作集。
> [How We Collaborated with Meta (Facebook) to Create Shadow Cache](https://hackernoon.com/how-we-collaborated-with-meta-facebook-to-create-shadow-cache)
以下是具體優化 :
(1) 追蹤工作集大小
方法：
用 Bloom Filter 記錄快取中最近訪問的鍵（例如檔案路徑、物件 ID）。
將時間窗（例如 24 小時）分段，每段用一個 Bloom Filter，形成 Bloom Filter 鏈（如 Meta 的 4 段設計）。
新資料加入最新濾器，定期移除最舊濾器，實現動態更新。
效果：
估計工作集大小（非重複鍵的數量），判斷快取是否需要擴展。
Meta 範例：用 125MB 記憶體追蹤 27TB 工作集，誤差僅 3%。
估計公式使用 Swamidass & Baldi (2007) 公式估計工作集大小
$$ n^* = -(\frac{m}{k}) * ln(1 - \frac{X}{m})$$
$n*：估計元素數$
$m：bit \ array \ 位數$
$k：雜湊函數數量$
$X：設為 1 的位數$
(2) 減少未命中查詢
方法：
在快取查詢前，先檢查 Bloom Filter：
若 Bloom Filter 說鍵不在，跳過快取和底層儲存查詢，直接返回「未找到」。
若說鍵可能在，查詢快取，若快取未命中，再查底層儲存。
Bloom Filter 儲存所有快取鍵的指紋（fingerprint）。
效果：
減少對慢速儲存（例如磁碟或遠端資料庫）的訪問，降低延遲。
Meta 範例：Shadow Cache 模擬無限快取，計算最大命中率（H2），判斷快取友好性。
(3) 計算無限快取命中率
方法：
用 Bloom Filter 模擬無限快取，記錄所有查詢鍵。
命中率 = 命中次數（鍵在 Bloom Filter 中）/ 總查詢次數。
Meta 公式：hit / queryNum，其中 hit 是 Bloom Filter 返回存在的次數。
效果：
提供理論命中率（H2），指導快取大小調整。
Meta 範例：H2 高而 H1 低時，擴展快取可提升效能。
#### 為何 Meta 選擇貢獻 linux kernel 而不私有修改 open src code 內部使用
開源生態系統的好處：
- 維護成本：私有修改（fork）需要 Meta 自行維護分支，隨著核心更新，合併成本高。公開貢獻讓上游核心（Linux 社群）承擔維護。
- 協作：其他公司（如 Google、Netflix）也使用 eBPF，公開貢獻促進協作，Meta 可從社群改進中受益。
法律與許可：
- Linux 核心使用 GPL-2.0 許可，Meta 的修改若用於內部伺服器，技術上可不公開，但若分發（如嵌入設備），需公開。
商業與聲譽：
- 技術影響力：公開貢獻（如 BPF_MAP_TYPE_BLOOM_FILTER）展示 Meta 的工程實力，吸引人才。
- 社群回饋：Meta 透過貢獻（如 Katran 負載平衡器）建立開源形象，獲業界認可。
- 標準化：公開功能（如 eBPF 映射）成為業界標準，Meta 的基礎設施與生態系統保持一致。
#### 問題思考
問題是 " bpf 如何運用 bloom filter "。首先 bpf 是 linux kernel 的 bpf 還是什麼的 bpf?對，bpf 確實是 linux kernel。因為此技術是從 BSD 作業系統來的，而最一開始(1992)此技術 bpf 本來是一個專為處理網路封包進入 kernel 或從 kernel 到 userspace 的一個 ***過濾用虛擬機器*** 。到後來被 linux 於 1975 年(kernel 版本 2.1.75)引入此經典 bpf(cbpf) 到 kernel 。且早期訴求是讓用戶定義過濾規則來捕獲特定封包。
但隨著網路和系統需求的增長，cBPF 的功能（僅限封包過濾）顯得不足，無法滿足複雜的內核級任務，如效能追蹤和安全監控。Alexei Starovoitov 等開發者開始增強 BPF，於 Linux 3.15（2014 年 6 月）推出了 eBPF，將其從單純的封包過濾器轉變為通用的內核執行引擎。以下是幾次關鍵變革 :
關鍵變革：
- Linux 3.15（2014 年）：
引入 eBPF 的基礎設施，包括更強大的虛擬機器指令集。
支援內核級程式執行，允許附加到非網路事件（如內核函數追蹤）。
- Linux 3.18（2014 年 12 月）：
引入 BPF maps，允許 eBPF 程式儲存和共享資料（如 hash table）。
支援更廣泛的內核掛鉤點（如 kprobes）。
- Linux 4.1（2015 年 6 月）：
引入 JIT（Just-In-Time）編譯器，將 eBPF 指令轉為本地機器碼，大幅提升性能。
支援更多應用場景，如網路流量控制（cls_bpf）。
- 後續發展：
後續版本（如 Linux 4.4、4.7、5.x）陸續引入 **XDP**（eXpress Data Path）、**TC（Traffic Control）**、Bloom Filter map 等功能，擴展 eBPF 的應用範圍。
例如，`BPF_MAP_TYPE_BLOOM_FILTER` 在 Linux 5.16（2021 年）引入，用於高效集合查詢。
#### 釐清 虛擬機器指令集架構 與 硬體指令集架構
虛擬機器 ISA 與硬體 ISA 不同。舉例來說硬體 ISA 是常見的如 :
1. Arm
2. Riscv
3. x86
4. MIPS
等。而虛擬機器 ISA 則是如 :
1. BPF（Berkeley Packet Filter）ISA (內核級，封包過濾和系統追蹤。)
2. JVM（Java Virtual Machine）ISA (Java 應用)
3. .NET CLR（Common Language Runtime）ISA (C# 和 .NET 生態，跨平台開發)
4. Lua VM（Lua Virtual Machine）ISA (嵌入式和遊戲腳本)
5. WebAssembly（Wasm）ISA (網頁和通用計算)
6. Python VM（CPython Bytecode）ISA (資料科學和腳本)
7. V8 JavaScript Engine ISA (JavaScript 和 Node.js)
8. Erlang BEAM ISA (高並發和電信系統)
#### eBPF 為何需要 map 結構?
從 linux kernel src 中 Documentation/bpf dir 中能看到有許多資料結構 type 的 map 如 array、hash、queue、stack、bloom filter 等。於是好奇為甚麼需要這些不同型態之 map (mapping)。
為什麼需要 map 結構？
Map 是 eBPF 程式的「資料倉庫」，提供狀態儲存、內核與用戶空間通信、高效資料管理和靈活性。沒有 map，eBPF 程式無法保存資料或實現複雜邏輯。
為什麼 map 有多种資料結構型態？
不同場景需要不同的資料結構來平衡性能（查詢速度）、功能（精確性、並發性）和記憶體效率。多型態設計讓 eBPF 適應廣泛應用（網路、安全、追蹤），並支援未來擴展。
例如，`BPF_MAP_TYPE_BLOOM_FILTER` 針對快速集合查詢，`BPF_MAP_TYPE_HASH` 適合鍵值映射，`BPF_MAP_TYPE_PERCPU_ARRAY` 優化並發性能
也就是說 map struct 是 bpf 用於處理大量資料管理所使用的資料型態集。而 bpf 其他部分
以下是 bpf 抽象架構
```
eBPF 虛擬機器 (VM)
├── BPF 程式 (Program)
│ ├── Map 結構
│ │ ├── BPF_MAP_TYPE_HASH
│ │ ├── BPF_MAP_TYPE_ARRAY
│ │ ├── BPF_MAP_TYPE_BLOOM_FILTER
│ │ └── 其他資料結構型態
│ └── 執行邏輯 (如過濾、監控)
├── 掛鉤點 (Hooks)
│ ├── XDP (網卡層)
│ ├── TC (流量控制)
│ ├── Kprobe (內核函數)
│ ├── Tracepoint
│ └── 其他事件點
├── 驗證器 (Verifier)
│ └── 安全性檢查 (防止崩潰、非法存取)
└── 用戶空間介面 (libbpf)
├── 載入程式
├── 管理 Map
└── 與內核交互
```
:::success
4. 紀錄研讀 `Documentation/bpf/map_bloom_filter.rst` 的疑惑 (搭配 eBPF 閱讀)
:::
一開始講述 bpf type bloom filter `BPF_MAP_TYPE_BLOOM_FILTER` 的一些背景諸如
1. 在 linux 版本 5.16 時加入
1. 是個 space-efficient 之結構
2. 目的是在一個 set 中檢測一 data 是否存在
3. 存在 false positive ，但不存在 false negative
然後 bloom filter map 有 2 個 operations :
1. `push` : 增加一個 element 至 map
2. `peek` : 看該 element 有無存在
:::success
講到一點是 bloom filter map 沒有 keys，只有 values ，因此當 linux 之 bloom filter 被創建以來，`key_size` 將被設為 0 。
- [x] Q : 只有 keys 沒有 values 原因是什麼?
我有以下疑惑 : hash function 中 key 與 value 是一定要存在的嗎?沒有 key 是否會增加效能?
在傳統 hash table 中，key-value 是成對出現的。而 key 作為索引， value 作為存放資料。若僅有 key 沒有 value，可以作為看 bucket 是否為空的功能。而若僅有 value 沒有 key，即是 bloom filter 的結構。從 `bloom_filter.c`中的`bloom_map_push_elem` 函式參數僅有 value 無 key 可看出。
:::
```markdown
BPF programs must use ``bpf_map_push_elem`` to add an element to the
bloom filter map and ``bpf_map_peek_elem`` to query the map. These
operations are exposed to userspace applications using the existing
``bpf`` syscall in the following way:
- ``BPF_MAP_UPDATE_ELEM`` -> push
- ``BPF_MAP_LOOKUP_ELEM`` -> peek
```
- 我將此次部分對 `bpf_map` 的 operation 與對 bloom filter map 加入元素或查詢元素僅能使用 kernel 中 `bloom_filter.c` 定義的兩函式 `bpf_map_push_elem` 與 `bpf_map_peek_elem` 搞混。兩者都是只有兩個功能，增加元素與查詢元素。而若是要在 user space 中操作 `bpf_map` ，就必須調用 bpf system call :
```c
bpf(int cmd, union bpf_attr *attr, unsigned int size)
```
將 `cmd` 參數放入 `BPF_MAP_UPDATE_ELEM` 與 `BPF_MAP_LOOKUP_ELEM` 使分別映射到 kernel function `bpf_map_push_elem` 與 `bpf_map_peek_elem`
:::success
#### 釐清在 `include/linux/bpf.h` 之 `bpf_map` 、 在 include/uapi/linux/bpf.h 中之 `BPF_MAP_TYPE_BLOOM_FILTER` 與在 kernel/bpf/bloom_filter.c 中之 `bpf_bloom_filter`
`bpf_map` 首先定義在 `include/linux/bpf.h` 。為 linux kernel 之 ebpf 基本結構 :
```C
struct bpf_map {
const struct bpf_map_ops *ops;
struct bpf_map *inner_map_meta;
#ifdef CONFIG_SECURITY // 檢查是否定義了該 MACRO，若定義則編譯後續程式碼
void *security;
#endif // 結束條件編譯區塊
enum bpf_map_type map_type; /* 類型，如 BPF_MAP_TYPE_BLOOM_FILTER */
u32 key_size; /* 鍵大小，Bloom filter 為 0 */
u32 value_size; /* 值大小 */
u32 max_entries; /* 最大條目 */
u64 map_extra; /* any per-map-type extra fields */ /* 額外配置，如 Bloom filter 雜湊數 */
u32 map_flags;
u32 id;
struct btf_record *record;
int numa_node;
u32 btf_key_type_id;
u32 btf_value_type_id;
u32 btf_vmlinux_value_type_id;
struct btf *btf;
#ifdef CONFIG_MEMCG
struct obj_cgroup *objcg;
#endif
char name[BPF_OBJ_NAME_LEN]; /* 映射名稱 */
struct mutex freeze_mutex;
atomic64_t refcnt;
atomic64_t usercnt;
/* rcu is used before freeing and work is only used during freeing */
union {
struct work_struct work;
struct rcu_head rcu;
};
atomic64_t writecnt;
/* 'Ownership' of program-containing map is claimed by the first program
* that is going to use this map or by the first program which FD is
* stored in the map to make sure that all callers and callees have the
* same prog type, JITed flag and xdp_has_frags flag.
*/
struct {
const struct btf_type *attach_func_proto;
spinlock_t lock;
enum bpf_prog_type type;
bool jited;
bool xdp_has_frags;
} owner;
bool bypass_spec_v1;
bool frozen; /* write-once; write-protected by freeze_mutex */
bool free_after_mult_rcu_gp;
bool free_after_rcu_gp;
atomic64_t sleepable_refcnt;
s64 __percpu *elem_count;
};
```
由 `bpf.h` 歸類在 `uapi` 可知該檔案在寫有關 user space API 相關的內容。因此 `bpf.h` 是 linux kernel 為 ebpf 在 user space 提供的 API ，使能在 user space 操作 kernel space bpf 功能之介面。
而以下是 `bpf.h` 中 964 行 ~ 1014 行 定義之 `bpf_map` 所能映射的所有類型 :
```c=
enum bpf_map_type {
BPF_MAP_TYPE_UNSPEC,
BPF_MAP_TYPE_HASH,
BPF_MAP_TYPE_ARRAY,
BPF_MAP_TYPE_PROG_ARRAY,
BPF_MAP_TYPE_PERF_EVENT_ARRAY,
BPF_MAP_TYPE_PERCPU_HASH,
BPF_MAP_TYPE_PERCPU_ARRAY,
BPF_MAP_TYPE_STACK_TRACE,
BPF_MAP_TYPE_CGROUP_ARRAY,
BPF_MAP_TYPE_LRU_HASH,
BPF_MAP_TYPE_LRU_PERCPU_HASH,
BPF_MAP_TYPE_LPM_TRIE,
BPF_MAP_TYPE_ARRAY_OF_MAPS,
BPF_MAP_TYPE_HASH_OF_MAPS,
BPF_MAP_TYPE_DEVMAP,
BPF_MAP_TYPE_SOCKMAP,
BPF_MAP_TYPE_CPUMAP,
BPF_MAP_TYPE_XSKMAP,
BPF_MAP_TYPE_SOCKHASH,
BPF_MAP_TYPE_CGROUP_STORAGE_DEPRECATED,
/* BPF_MAP_TYPE_CGROUP_STORAGE is available to bpf programs attaching
* to a cgroup. The newer BPF_MAP_TYPE_CGRP_STORAGE is available to
* both cgroup-attached and other progs and supports all functionality
* provided by BPF_MAP_TYPE_CGROUP_STORAGE. So mark
* BPF_MAP_TYPE_CGROUP_STORAGE deprecated.
*/
BPF_MAP_TYPE_CGROUP_STORAGE = BPF_MAP_TYPE_CGROUP_STORAGE_DEPRECATED,
BPF_MAP_TYPE_REUSEPORT_SOCKARRAY,
BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE_DEPRECATED,
/* BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE is available to bpf programs
* attaching to a cgroup. The new mechanism (BPF_MAP_TYPE_CGRP_STORAGE +
* local percpu kptr) supports all BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE
* functionality and more. So mark * BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE
* deprecated.
*/
BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE = BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE_DEPRECATED,
BPF_MAP_TYPE_QUEUE,
BPF_MAP_TYPE_STACK,
BPF_MAP_TYPE_SK_STORAGE,
BPF_MAP_TYPE_DEVMAP_HASH,
BPF_MAP_TYPE_STRUCT_OPS,
BPF_MAP_TYPE_RINGBUF,
BPF_MAP_TYPE_INODE_STORAGE,
BPF_MAP_TYPE_TASK_STORAGE,
BPF_MAP_TYPE_BLOOM_FILTER,
BPF_MAP_TYPE_USER_RINGBUF,
BPF_MAP_TYPE_CGRP_STORAGE,
BPF_MAP_TYPE_ARENA,
__MAX_BPF_MAP_TYPE
};
```
可以看到 `BPF_MAP_TYPE_BLOOM_FILTER` 在倒數第 6 行可知其為 `bpf_map` 其中一種映射類型。
而最後 `bpf_bloom_filter` 為該 `BPF_MAP_TYPE_BLOOM_FILTER` 映射類型的實現結構
:::
```markdown
The ``max_entries`` size that is specified at map creation time is used
to approximate a reasonable bitmap size for the bloom filter, and is not
otherwise strictly enforced. If the user wishes to insert more entries
into the bloom filter than ``max_entries``, this may lead to a higher
false positive rate.
```
- 此 `max_entries` 表示根據 map size(即bit array size `m`) 建議插入的 bloom filter element 數 `n` 之最大值 。 沒有強硬限制插入之 element 數，但若超過 `max_entries` 後 false positive rate 會上升。此根據 [推導與定性觀察](https://hackmd.io/Xz79jKDrS7yp-tkPDVdLDQ) ， false positive rate 隨 `n` 無條件上升而上升是合理的。
```markdown
The number of hashes to use for the bloom filter is configurable using
the lower 4 bits of ``map_extra`` in ``union bpf_attr`` at map creation
time. If no number is specified, the default used will be 5 hash
functions. In general, using more hashes decreases both the false
positive rate and the speed of a lookup.
```
- 此部分是針對 hash function number `k` 部分做講解。`k` 若未設定有預設值為 5 ，而此值與之前的 [推導與定性觀察](https://hackmd.io/Xz79jKDrS7yp-tkPDVdLDQ) 中顯示是相符合的，在值 = 5 ~ 9 時 false positive rate 為最小，因此取最小使設計最簡。此外，`k` 可以任意設定。但要從 `include/uapi/linux/bpf.h` 中的 `union bpf_attr struct` 之 member u64 `map_extra` 低 4 位做設定。因此 k 值範圍為 0 ~ 15。
- 以下是 `bpf_attr` 結構 (bpf 屬性)
```c
union bpf_attr {
struct { /* anonymous struct used by BPF_MAP_CREATE command */
__u32 map_type; /* one of enum bpf_map_type */
__u32 key_size; /* size of key in bytes */
__u32 value_size; /* size of value in bytes */
__u32 max_entries; /* max number of entries in a map */
__u32 map_flags; /* BPF_MAP_CREATE related
* flags defined above.
*/
__u32 inner_map_fd; /* fd pointing to the inner map */
__u32 numa_node; /* numa node (effective only if
* BPF_F_NUMA_NODE is set).
*/
char map_name[BPF_OBJ_NAME_LEN];
__u32 map_ifindex; /* ifindex of netdev to create on */
__u32 btf_fd; /* fd pointing to a BTF type data */
__u32 btf_key_type_id; /* BTF type_id of the key */
__u32 btf_value_type_id; /* BTF type_id of the value */
__u32 btf_vmlinux_value_type_id;/* BTF type_id of a kernel-
* struct stored as the
* map value
*/
/* Any per-map-type extra fields
*
* BPF_MAP_TYPE_BLOOM_FILTER - the lowest 4 bits indicate the
* number of hash functions (if 0, the bloom filter will default
* to using 5 hash functions).
*
* BPF_MAP_TYPE_ARENA - contains the address where user space
* is going to mmap() the arena. It has to be page aligned.
*/
__u64 map_extra;
__s32 value_type_btf_obj_fd; /* fd pointing to a BTF
* type data for
* btf_vmlinux_value_type_id.
*/
/* BPF token FD to use with BPF_MAP_CREATE operation.
* If provided, map_flags should have BPF_F_TOKEN_FD flag set.
*/
__s32 map_token_fd;
};
```
而`__u32` 定義在 `include/uapi/asm-generic/int-l64.h:typedef unsigned int __u32;`
```markdown
It is not possible to delete elements from a bloom filter map. A bloom
filter map may be used as an inner map. The user is responsible for
synchronising concurrent updates and lookups to ensure no false negative
lookups occur.
```
- 此部分提及 bloom filter 中沒有刪除 element 的操作。同時也提到 bloom filter 時常作為內部映射操作，因此很有可能產生 race condition 問題。使用者必須負責做同步處理，以免 false negative 狀況(本應該放進元素後 query 因為 race condition 變成先 query 導致應該存在的被判定為不存在)
#### 以下部分為 linux bpf 之函式使用講解
##### kernel space BPF
```c
Usage
=====
Kernel BPF
----------
bpf_map_push_elem()
~~~~~~~~~~~~~~~~~~~
.. code-block:: c
long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
A ``value`` can be added to a bloom filter using the
``bpf_map_push_elem()`` helper. The ``flags`` parameter must be set to
``BPF_ANY`` when adding an entry to the bloom filter. This helper
returns ``0`` on success, or negative error in case of failure.
bpf_map_peek_elem()
~~~~~~~~~~~~~~~~~~~
.. code-block:: c
long bpf_map_peek_elem(struct bpf_map *map, void *value)
The ``bpf_map_peek_elem()`` helper is used to determine whether
``value`` is present in the bloom filter map. This helper returns ``0``
if ``value`` is probably present in the map, or ``-ENOENT`` if ``value``
is definitely not present in the map.
```
描述如何在 kernel space 中使用 bpf 操作函式(helper) `bpf_map_push_elem` 與 `bpf_map_peek_elem` 操作 bpf bloom filter 。
- `bpf_map_push_elem`
`map` 皆放置 type 為 `BPF_MAP_TYPE_BLOOM_FILTER` 之 `bpf_map`， 而 `value` 即為 element 的值，同時要使用 bloom filter 操作時 `flags` 要設為 `BPF_ANY`。
最後成功輸出 0 ，失敗輸出 負數。
:::success
`BPF_ANY` 定義出現在 include/uapi/linux/bpf.h 中的 `BPF_MAP_UPDATE_ELEM` API
```c
* BPF_MAP_UPDATE_ELEM
* Description
* Create or update an element (key/value pair) in a specified map.
*
* The *flags* argument should be specified as one of the
* following:
*
* **BPF_ANY**
* Create a new element or update an existing element.
* **BPF_NOEXIST**
* Create a new element only if it did not exist.
* **BPF_EXIST**
* Update an existing element.
* **BPF_F_LOCK**
* Update a spin_lock-ed map element.
```
`BPF_ANY` 表示無條件插入，符合 bloom filter 特性，重複插入也無關係。而 `BPF_NOEXIST` 與 `BPF_EXIST` 僅在 key 存在時才有東西能判定，而 bloom filter 為 無鍵，因此不適用
:::
- `bpf_map_peek_elem`
`map` 與 `value` 皆與上函式同。而檢查出 element 存在輸出 0 ，不存在則輸出 `ENOENT`
:::success
`ENOENT` 定義於 include/uapi/asm-generic/errno-base.h
```C
#define ENOENT 2 /* No such file or directory */
```
:::
##### user space
```c
Userspace
---------
bpf_map_update_elem()
~~~~~~~~~~~~~~~~~~~~~
.. code-block:: c
int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)
A userspace program can add a ``value`` to a bloom filter using libbpf's
``bpf_map_update_elem`` function. The ``key`` parameter must be set to
``NULL`` and ``flags`` must be set to ``BPF_ANY``. Returns ``0`` on
success, or negative error in case of failure.
bpf_map_lookup_elem()
~~~~~~~~~~~~~~~~~~~~~
.. code-block:: c
int bpf_map_lookup_elem (int fd, const void *key, void *value)
A userspace program can determine the presence of ``value`` in a bloom
filter using libbpf's ``bpf_map_lookup_elem`` function. The ``key``
parameter must be set to ``NULL``. Returns ``0`` if ``value`` is
probably present in the map, or ``-ENOENT`` if ``value`` is definitely
not present in the map.
```
描述了在 user space 如何操作 bpf bloom filter 。不同的是 user space 是使用 `libbpf` 函式庫之函式 `bpf_map_update_elem` 、`bpf_map_lookup_elem` 作為介面。而因為是 user space 要存取 kernel space 資源，所以需要 file descriptor 的介入。 `fd` 就像是給想要存取 kernel space 之 user space 用戶的一個號碼牌，作為編號也作為單位。其中要注意的就是參數 `key` 指針要填入 NULL 以示 bloom filter 之無鍵映射。
##### kernel space 使用例子
```c
Examples
========
Kernel BPF
----------
This snippet shows how to declare a bloom filter in a BPF program:
.. code-block:: c
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER);
__type(value, __u32);
__uint(max_entries, 1000);
__uint(map_extra, 3);
} bloom_filter SEC(".maps");
This snippet shows how to determine presence of a value in a bloom
filter in a BPF program:
.. code-block:: c
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;
}
```
- 宣告 Bloom filter
使用 `SEC(".maps")` 定義 bloom filter 映射，`max_entries=1000` 估算位元陣列，`map_extra=3` 設 hash function number k。
- 查詢範例：
先用 `peek` 快速檢查，若可能存在，進一步查詢 hash table 確認。
##### user space 使用例子
```c
Userspace
---------
This snippet shows how to use libbpf to create a bloom filter map from
userspace:
.. code-block:: c
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 */
}
This snippet shows how to add an element to a bloom filter from
userspace:
.. code-block:: c
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);
}
```
- 創建 Bloom filter：
使用 `bpf_map_create` 創建映射，`key_size=0`，`max_entries=10000`，`map_extra=3`（3 個雜湊函數）。
- 添加元素：
使用 `bpf_map_update_elem` 推入值，`key` = NULL。
## references
- [Linux 核心設計: eBPF](https://hackmd.io/@RinHizakura/S1DGq8ebw)
- [张亦鸣 : eBPF 简史 （上篇）](https://cloud.tencent.com/developer/article/1006317)
- [commit b37a1b90d915（“bpf: Add bloom filter map implementation”，2021）](https://lore.kernel.org/bpf/517a137d-66aa-8aa8-a064-fad8ae0c7fa8@fb.com/)
- [SipHash - a short input PRF](https://www.kernel.org/doc/html/v5.5/security/siphash.html)
- [SipHash in the kernel](https://lwn.net/Articles/711167/)
- [kernel/bpf/bloom_filter.c](https://elixir.bootlin.com/linux/v6.12.28/source/kernel/bpf/bloom_filter.c)
- [Documentation/bpf/map_bloom_filter.rst](https://elixir.bootlin.com/linux/v6.12.28/source/Documentation/bpf/map_bloom_filter.rst)
- [Documentation/bpf/maps.rst](https://elixir.bootlin.com/linux/v6.12.28/source/Documentation/bpf/maps.rst)
- [Documentation/networking/filter.rst](https://elixir.bootlin.com/linux/v6.12.28/source/Documentation/networking/filter.rst)
Sign in with Wallet
Connect another wallet