Elemente wurden fälschlicherweise aus der eBPF-LRU-Hashmap entfernt

Frageninhalt

Ich habe beobachtet, dass Elemente in der ebpf-lru-Hash-Map (bpf_map_type_lru_hash) falsch entfernt wurden. Im folgenden Code füge ich eine LRU-Hash-Map der Größe 8 ein und drucke ihren Inhalt jede Sekunde aus:

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

Wenn ich das obige Programm ausführe, sehe ich Folgendes:

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

Da die Karte acht Einträge hat, habe ich erwartet, dass in der vierten Zeile vier Werte angezeigt werden, aber es werden nur drei angezeigt, da der Eintrag (1, 1) geräumt wurde.

Wenn ich max_entries auf 1024 ändere, ist mir aufgefallen, dass dieses Problem nach dem Einfügen des 200. Elements auftritt, manchmal aber auch danach. Inkonsistent.

Dieses Problem ist nicht auf das Erstellen/Einfügen von Karten aus dem Benutzerbereich beschränkt, da ich dieses Problem in einem xdp-Programm beobachtet habe, das eine Karte erstellt und eingefügt hat, was das Problem reproduziert, das ich in meinem eigentlichen Programm beobachtet habe. In meinem echten Programm, das ebenfalls 1024 Einträge hat, ist mir aufgefallen, dass dieses Problem nach dem Einfügen von 16 Elementen auftrat.

Ich habe dies auf einem Produktionsserver mit Linux-Kernel 5.16.7 getestet.

Ich habe es auf einer Linux-VM getestet und den Kernel auf 6.2.8 aktualisiert und dabei einen Unterschied in der Räumungsrichtlinie festgestellt. Wenn max_entries zum Beispiel 8 ist, beobachte ich:

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

Wenn max_entries 1024 ist, stelle ich fest, dass nach dem Hinzufügen des 1025. Elements die Gesamtzahl der Elemente 897 beträgt. Ich kann mit Kernel 6.2.8 auf unserem Produktionsserver nicht testen.

Richtige Antwort

Es ist nicht garantiert, dass die LRU-Hash-Map genaudie maximale Anzahl an Elementen aufweist, und die Implementierung ist offensichtlich darauf ausgelegt, eine gute Leistung mit weit mehr als 8 Elementen zu bieten. Ein kurzer Blick auf den Code und was ich gesehen habe:

1. LRU ist in zwei Teile unterteilt: „aktive Liste“ und „inaktive Liste“, und seine Aufgabe besteht darin, Elemente regelmäßig von einem Teil in einen anderen zu verschieben, je nachdem, ob sie kürzlich besucht wurden. Es handelt sich nicht um echtes LRU (Elemente werden nicht bei jedem Zugriff an den Kopf verschoben).

2. Wenn die Karte voll ist und etwas entfernt werden muss, um ein neues Element einzufügen, entfernt der Code bis zu 128 Elemente in einem Durchgang aus der inaktiven Liste; nur wenn die inaktive Liste leer ist, wird ein einziges entfernt Element aus der aktiven Liste.

3. Es gibt auch eine „lokale freie Liste“ pro CPU, die zugewiesene Elemente enthält, die darauf warten, mit Daten gefüllt zu werden. Wenn sie leer ist, wird versucht, sie aus der globalen freien Liste abzurufen. Wenn diese Liste leer ist, wird sie eingegeben der Vertreibungsweg. Die Zielgröße der lokalen freien Liste beträgt 4 Einträge.

Das Verhalten in 6.2.8 sieht also einfach und konsistent aus: Vermutlich sind alle Ihre Schlüssel auf der „inaktiven Liste“ (nicht allzu überraschend für ein Scan-Typ-Zugriffsmuster, oder vielleicht liegt es einfach daran, dass sie alle noch keine Chance auf Beförderung haben), und dann wurden alle rausgeschmissen. Ich weiß nicht viel über 5.16, aber es könnte etwas mit der lokalen Freelist und allen Updates zu tun haben, die von derselben CPU ausgeführt werden.

Grundsätzlich denke ich, dass der Datentyp nicht für die Art und Weise gedacht ist, wie Sie ihn verwenden, und der Fehler ist das, was Sie erwarten. Wenn Sie damit nicht einverstanden sind, müssen Sie es meiner Meinung nach mit den Kernel-Entwicklern besprechen.

Das obige ist der detaillierte Inhalt vonElemente wurden fälschlicherweise aus der eBPF-LRU-Hashmap entfernt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!