我观察到 ebpf lru 哈希映射 (bpf_map_type_lru_hash) 中的元素被错误地逐出。在下面的代码中，我插入一个大小为 8 的 lru 哈希映射并每秒打印其内容：
package main
import (
"fmt"
"github.com/cilium/ebpf"
"log"
"time"
)
func main() {
spec := ebpf.mapspec{
name: "test_map",
type: ebpf.lruhash,
keysize: 4,
valuesize: 8,
maxentries: 8,
}
hashmap, err := ebpf.newmap(&spec)
if err != nil {
log.fatalln("could not create map:", err)
}
var insertkey uint32
for range time.tick(time.second) {
err = hashmap.update(insertkey, uint64(insertkey), ebpf.updateany)
if err != nil {
log.printf("update failed. insertkey=%d|value=%d|err=%s", insertkey, insertkey, err)
}
var key uint32
var value uint64
count := 0
elementsstr := ""
iter := hashmap.iterate()
for iter.next(&key, &value) {
elementsstr += fmt.sprintf("(%d, %d) ", key, value)
count++
}
log.printf("total elements: %d, elements: %s", count, elementsstr)
insertkey++
}
}
当我运行上面的程序时，我看到这个：
2023/03/29 17:32:29 total elements: 1, elements: (0, 0) 2023/03/29 17:32:30 total elements: 2, elements: (1, 1) (0, 0) 2023/03/29 17:32:31 total elements: 3, elements: (1, 1) (0, 0) (2, 2) 2023/03/29 17:32:32 total elements: 3, elements: (3, 3) (0, 0) (2, 2) ...
由于地图有八个条目，我希望第四行显示四个值，但它只显示三个，因为条目 (1, 1) 已被驱逐。
如果我将 max_entries 更改为 1024，我注意到插入第 200 个元素后会发生此问题，但有时会发生在之后。不一致。
此问题不仅限于从用户空间创建/插入映射，因为我在创建映射并插入映射的 xdp 程序中观察到此问题；上面重现了我在实际程序中观察到的问题。在我的真实程序中也有 1024 个条目，我注意到插入 16 个元素后发生了这个问题。
我在运行 linux 内核 5.16.7 的生产服务器上对此进行了测试。
我在 linux vm 上进行测试，并将内核升级到 6.2.8，我发现驱逐策略有所不同。例如，当 max_entries 为 8 时，我观察到：
2023/03/29 20:38:02 Total elements: 1, elements: (0, 0) 2023/03/29 20:38:03 Total elements: 2, elements: (0, 0) (1, 1) 2023/03/29 20:38:04 Total elements: 3, elements: (0, 0) (2, 2) (1, 1) 2023/03/29 20:38:05 Total elements: 4, elements: (0, 0) (2, 2) (1, 1) (3, 3) 2023/03/29 20:38:06 Total elements: 5, elements: (4, 4) (0, 0) (2, 2) (1, 1) (3, 3) 2023/03/29 20:38:07 Total elements: 6, elements: (4, 4) (0, 0) (2, 2) (1, 1) (5, 5) (3, 3) 2023/03/29 20:38:08 Total elements: 7, elements: (4, 4) (0, 0) (2, 2) (1, 1) (6, 6) (5, 5) (3, 3) 2023/03/29 20:38:09 Total elements: 8, elements: (7, 7) (4, 4) (0, 0) (2, 2) (1, 1) (6, 6) (5, 5) (3, 3) 2023/03/29 20:38:10 Total elements: 1, elements: (8, 8) ...
当 max_entries 为 1024 时，我注意到添加第 1025 个元素后，总元素为 897。我无法在我们的生产服务器上使用内核 6.2.8 进行测试。
正确答案
LRU 哈希映射不能保证恰好有最大数量的项目，并且该实现显然是为了在远远超过 8 个项目的情况下提供良好的性能。我快速浏览一下代码看到了什么：
-
LRU 分为两部分：“活动列表”和“非活动列表”，其任务是根据最近是否访问过元素，定期将元素从一个部分移动到另一个部分。它不是真正的 LRU（项目不会在每次访问时都移动到头部）。
-
当地图已满，并且需要逐出某些内容才能插入新项目时，代码将在一次传递中从非活动列表中逐出最多 128 个项目；仅当非活动列表为空时，它才会从活动列表中逐出单个项目。
-
还有一个每个 CPU 的“本地空闲列表”，其中包含等待填充数据的已分配项；当它运行为空时，它会尝试从全局空闲列表中拉出，如果该列表为空，它将进入逐出路径。本地空闲列表的目标大小是 4 项。
因此，6.2.8 中的行为看起来简单且一致：大概您的所有密钥都在“非活动列表”上（对于扫描类型的访问模式来说并不太令人惊讶，或者可能只是它们都没有机会还没升职），然后所有人都被赶了出去。我不太清楚 5.16，但它可能与本地空闲列表以及从同一 CPU 运行的所有更新有关。
基本上，我认为该数据类型并不适合按照您使用的方式使用，并且该错误符合您的预期。如果您不同意，我认为您必须与内核开发人员讨论。
