eBPF LRU哈希表元素被错误驱逐问题问询

问题现象 #

我发现BPF_MAP_TYPE_LRU_HASH类型的哈希表存在元素被错误驱逐的问题：当创建一个容量为8的LRU哈希表，每秒向其中插入新元素并打印当前表内元素时，预期哈希表会先填满8个元素后才开始驱逐最久未使用的条目，但实际在插入第4个元素时，就有旧条目被驱逐，导致表内元素总数始终无法达到设定的最大容量。

复现代码 #

以下Go代码可复现该问题：

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++
    }
}

内核5.16.7下的运行输出 #

运行上述代码后，输出片段如下：

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) 
...

可以看到，插入第4个元素（key=3）后，表内总数仍为3，条目(1,1)被提前驱逐。

其他场景表现 #

• 将MaxEntries改为1024后，问题会在插入第200个元素左右出现，触发时机不稳定；
• 该问题并非仅存在于用户态：在XDP程序中创建并插入LRU哈希表时，同样会出现元素提前被驱逐的情况，比如在一个MaxEntries=1024的实际程序中，插入第16个元素后就出现了驱逐。

内核6.2.8下的测试结果 #

在虚拟机中升级内核至6.2.8后，驱逐策略出现异常变化：

• 当MaxEntries=8时，插入第9个元素后，哈希表内仅剩新插入的条目(8,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)
...

• 当MaxEntries=1024时，插入第1025个元素后，哈希表内元素总数变为897，并未保留1024个元素。

请求协助 #

我无法在生产服务器上升级内核至6.2.8版本，现请求排查该问题的根本原因，并提供可在Linux内核5.16.7环境下解决该问题的方案。

内容的提问来源于stack exchange，提问作者user2233706