元素被錯誤地從 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中文網其他相關文章！