元素被错误地从 eBPF LRU 哈希图中逐出

问题内容

我观察到 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 个项目的情况下提供良好的性能。我快速浏览一下代码看到了什么：

1. LRU 分为两部分：“活动列表”和“非活动列表”，其任务是根据最近是否访问过元素，定期将元素从一个部分移动到另一个部分。它不是真正的 LRU（项目不会在每次访问时都移动到头部）。

2. 当地图已满，并且需要逐出某些内容才能插入新项目时，代码将在一次传递中从非活动列表中逐出最多 128 个项目；仅当非活动列表为空时，它才会从活动列表中逐出单个项目。

3. 还有一个每个 CPU 的“本地空闲列表”，其中包含等待填充数据的已分配项；当它运行为空时，它会尝试从全局空闲列表中拉出，如果该列表为空，它将进入逐出路径。本地空闲列表的目标大小是 4 项。

因此，6.2.8 中的行为看起来简单且一致：大概您的所有密钥都在“非活动列表”上（对于扫描类型的访问模式来说并不太令人惊讶，或者可能只是它们都没有机会还没升职），然后所有人都被赶了出去。我不太清楚 5.16，但它可能与本地空闲列表以及从同一 CPU 运行的所有更新有关。

基本上，我认为该数据类型并不适合按照您使用的方式使用，并且该错误符合您的预期。如果您不同意，我认为您必须与内核开发人员讨论。

以上是元素被错误地从 eBPF LRU 哈希图中逐出的详细内容。更多信息请关注PHP中文网其他相关文章！