Elemen dialih keluar secara salah daripada peta cincang eBPF LRU

Saya memerhatikan bahawa unsur-unsur dalam peta cincang ebpf lru (bpf_map_type_lru_hash) telah diusir secara salah. Dalam kod di bawah, saya memasukkan peta hash lru bersaiz 8 dan mencetak kandungannya setiap saat:

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

Apabila saya menjalankan program di atas, saya melihat ini:

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

Memandangkan peta mempunyai lapan entri, saya menjangkakan baris keempat menunjukkan empat nilai, tetapi ia hanya menunjukkan tiga kerana entri (1, 1) telah diusir.

Jika saya menukar max_entries kepada 1024, saya perasan masalah ini berlaku selepas memasukkan elemen ke-200, tetapi kadang-kadang ia berlaku selepas itu. Tidak konsisten.

Isu ini tidak terhad kepada mencipta/menyisipkan peta daripada ruang pengguna, kerana saya memerhati isu ini dalam program xdp yang mencipta peta dan memasukkannya di atas mengeluarkan semula isu yang saya perhatikan dalam program sebenar saya. Dalam program sebenar saya yang juga mempunyai 1024 entri, saya perhatikan bahawa masalah ini berlaku selepas memasukkan 16 elemen.

Saya menguji ini pada pelayan pengeluaran yang menjalankan kernel linux 5.16.7.

Saya menguji pada vm linux dan menaik taraf kernel kepada 6.2.8 dan saya melihat perbezaan dalam dasar pengusiran. Contohnya, apabila max_entries ialah 8, saya perhatikan:

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

Apabila max_entries ialah 1024, saya perhatikan bahawa selepas menambah elemen ke-1025, jumlah elemen ialah 897. Saya tidak dapat menguji dengan kernel 6.2.8 pada pelayan pengeluaran kami.

Jawapan betul

Peta cincang LRU tidak dijamin tepatmempunyai bilangan item maksimum, dan pelaksanaannya jelas direka untuk memberikan prestasi yang baik dengan lebih daripada 8 item. Pandangan pantas pada kod dan perkara yang saya lihat:

1. LRU dibahagikan kepada dua bahagian: "senarai aktif" dan "senarai tidak aktif", dan tugasnya adalah untuk memindahkan elemen secara berkala dari satu bahagian ke bahagian lain berdasarkan sama ada ia telah dilawati baru-baru ini. Ia tidak benar LRU (item tidak bergerak ke kepala pada setiap akses).

2. Apabila peta penuh dan sesuatu perlu diusir untuk memasukkan item baharu, kod akan mengusir sehingga 128 item daripada senarai tidak aktif dalam satu pas; item daripada senarai aktif.

3. Terdapat juga "senarai percuma tempatan" per-CPU bagi item yang diperuntukkan menunggu untuk diisi dengan data; apabila ia berjalan kosong, ia cuba menarik dari senarai percuma global, jika senarai itu kosong ia Akan memasuki laluan pengusiran. Saiz sasaran senarai percuma tempatan ialah 4 penyertaan.

Jadi gelagat dalam 6.2.8 kelihatan mudah dan konsisten: mungkin semua kunci anda berada dalam "senarai tidak aktif" (tidak terlalu mengejutkan untuk corak akses jenis imbasan, atau mungkin hanya kesemuanya Tiada peluang untuk dinaikkan lagi), dan kemudian semua orang ditendang keluar. Saya tidak tahu banyak tentang 5.16, tetapi ia mungkin ada kaitan dengan senarai bebas tempatan dan semua kemas kini yang dijalankan daripada CPU yang sama.

Pada asasnya, saya rasa jenis data tidak dimaksudkan untuk digunakan seperti yang anda gunakan, dan ralat adalah seperti yang anda jangkakan. Jika anda tidak bersetuju, saya fikir anda perlu membincangkannya dengan pembangun kernel.

Atas ialah kandungan terperinci Elemen dialih keluar secara salah daripada peta cincang eBPF LRU. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!