https://bpf.plus/map-in-map
截至 Linux 6.3,BPF 提供了两种 map-in-map: BPF_MAP_TYPE_ARRAY_OF_MAPS
和 BPF_MAP_TYPE_HASH_OF_MAPS
。本文以 BPF_MAP_TYPE_HASH_OF_MAPS
为例,讲述使用过程中可能遇到的陷阱。
HASH_OF_MAPS
只允许通过 BPF 系统调用插入和删除元素,这是实现上的限制。这一点与 BPF_MAP_TYPE_PROG_ARRAY
类似。
在最初的提交中:
提到:
Also, for the outer_map:
* It allows element update and delete from syscall
* It allows element lookup from bpf_prog
尝试在 BPF 程序中往 HASH_OF_MAPS
插入或者删除元素会导致验证失败:
...
14: (85) call bpf_map_delete_elem#3
cannot pass map_type 13 into func bpf_map_delete_elem#3
processed 13 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
这个限制带来一个强烈的暗示:使用 map-in-map 时,必须有一个用户程序来进行资源的分配(插入元素)和资源的回收(删除元素)。这是我们做技术选型时要考虑一个问题,是否真的必须使用 map-in-map ?大多数情况下,这个问题的答案应该是否定的。
要往 HASH_OF_MAPS
插入一个元素,我们需要创建一个 inner map
,将它的 map-fd
作为值插入 outer map
,如下:
func mapTest() {
innerSpec := &ebpf.MapSpec{
Type: ebpf.LRUHash,
KeySize: 4,
ValueSize: 4,
MaxEntries: 1024,
}
outerSpec := &ebpf.MapSpec{
Name: "map_in_map",
Type: ebpf.HashOfMaps,
KeySize: 4,
ValueSize: 4,
MaxEntries: 1024,
InnerMap: innerSpec,
}
innerMap, err := ebpf.NewMap(innerSpec)
if err != nil {
log.Fatal(err)
}
outerMap, err := ebpf.NewMap(outerSpec)
if err != nil {
log.Fatal(err)
}
key := uint32(0)
value := uint32(innerMap.FD())
err = outerMap.Update(&key, &value, ebpf.UpdateAny)
if err != nil {
log.Fatal(err)
}
log.Printf("key: %d, value: %d\n", key, value)
// 2023/05/06 15:24:59 key: 0, value: 3
}
如果我们查询刚刚插入的元素,得到的是什么呢?还是 map-fd
吗?
...
err = outerMap.Lookup(&key, &value)
if err != nil {
log.Fatal(err)
}
log.Printf("key: %d, value: %d\n", key, value)
// 2023/05/06 15:24:59 key: 0, value: 47397
和想象的不一样,这是我踩的第一个坑!
答案要去内核代码里找了,commit 14dc6f04f49d
:
bpf: Add syscall lookup support for fd array and htab
This patch allows userspace to do BPF_MAP_LOOKUP_ELEM on
BPF_MAP_TYPE_PROG_ARRAY,
BPF_MAP_TYPE_ARRAY_OF_MAPS and
BPF_MAP_TYPE_HASH_OF_MAPS.
The lookup returns a prog-id or map-id to the userspace.
The userspace can then use the BPF_PROG_GET_FD_BY_ID
or BPF_MAP_GET_FD_BY_ID to get a fd.
设计如此!查询得到的是 map-id
,我们可以进一步通过 BPF_MAP_GET_FD_BY_ID
得到 map-fd
。这种设计使得我们在不同进程看到的视图都是一致的,都是 map-id
。
与 BPF_MAP_TYPE_HASH
作对比,我们先看看 HASH_OF_MAPS
插入元素到底有多慢:
func mapTest() {
...
spec := &ebpf.MapSpec{
Type: ebpf.Hash,
KeySize: 4,
ValueSize: 4,
MaxEntries: 1024,
}
hashMap, err := ebpf.NewMap(spec)
if err != nil {
log.Fatal(err)
}
startTime := time.Now()
for i := 0; i < 1024; i++ {
key := uint32(i)
value := uint32(i)
err := hashMap.Update(&key, &value, ebpf.UpdateAny)
if err != nil {
log.Fatal(err)
}
}
log.Println(time.Since(startTime))
// 2023/05/07 02:42:20 1.503599ms
startTime = time.Now()
for i := 0; i < 1024; i++ {
key := uint32(i)
value := uint32(innerMap.FD())
err := outerMap.Update(&key, &value, ebpf.UpdateAny)
if err != nil {
log.Fatal(err)
}
}
log.Println(time.Since(startTime))
// 2023/05/07 02:42:41 21.154271695s
}
在一个八核的机器上,往 BPF_MAP_TYPE_HASH
插入 1024 个元素耗时大约 1.5ms
,而往 HASH_OF_MAPS
同样插入 1024 个元素耗时超过 21s
。
定位这个耗时问题颇费周章,可另作一文了,答案也在内核代码里:
static void maybe_wait_bpf_programs(struct bpf_map *map)
{
/* Wait for any running BPF programs to complete so that
* userspace, when we return to it, knows that all programs
* that could be running use the new map value.
*/
if (map->map_type == BPF_MAP_TYPE_HASH_OF_MAPS ||
map->map_type == BPF_MAP_TYPE_ARRAY_OF_MAPS)
synchronize_rcu();
}
为什么需要这个呢?commit 1ae80cf31938
写道:
bpf: wait for running BPF programs when updating map-in-map
The map-in-map frequently serves as a mechanism for atomic
snapshotting of state that a BPF program might record. The current
implementation is dangerous to use in this way, however, since
userspace has no way of knowing when all programs that might have
retrieved the "old" value of the map may have completed.
This change ensures that map update operations on map-in-map map types
always wait for all references to the old map to drop before returning
to userspace.
大意就是为了防止不同的进程看到的视图不一致,调用 synchronize_rcu()
,让所有的 CPU 都经过一个 Grace Period
。
这个耗时的优化需要从具体使用场景入手,原则就是尽可能地避免对 HASH_OF_MAPS
进行不必要的插入/删除,可以把相应的操作转化成对 inner map
的操作。
这个问题比较复杂,需同时满足以下条件才能触发:
HASH_OF_MAPS
时包含 BTF 信息,这个条件比较容易满足,编译的时候启用 clang -g
inner map
的 value 是一个结构体,并且不包含 bpf_timer
HASH_OF_MAPS
时,使用的 inner map
不包含 BTF 信息,如上面的例子bpf_timer
或者 backport 了相关特性具体讨论参见:
https://lore.kernel.org/all/20221126105351.2578782-2-hengqi.chen@gmail.com/
最终这个 Patch 没被接受(😠),问题不大,毕竟我们可以在用户态程序里避免。
在 BPF 开发中,map-in-map 的使用频率较低,踩了不少坑,仅作本文,为大家排雷。