首页 > 后端开发 > Golang > 元素被错误地从 eBPF LRU 哈希图中逐出

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

PHPz
发布: 2024-02-06 09:36:11
转载
622 人浏览过

元素被错误地从 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中文网其他相关文章!

来源:stackoverflow.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板