Les éléments sont expulsés de manière incorrecte de la table de hachage eBPF LRU

Contenu de la question

J'ai observé que des éléments de la carte de hachage ebpf lru (bpf_map_type_lru_hash) n'étaient pas expulsés de manière incorrecte. Dans le code ci-dessous, j'insère une hash map lru de taille 8 et j'imprime son contenu toutes les secondes :

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

Lorsque j'exécute le programme ci-dessus, je vois ceci :

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

Étant donné que la carte comporte huit entrées, je m'attendais à ce que la quatrième ligne affiche quatre valeurs, mais elle n'en affiche que trois car l'entrée (1, 1) a été expulsée.

Si je change max_entries en 1024, j'ai remarqué que ce problème se produit après l'insertion du 200ème élément, mais parfois cela arrive après. Inconsistant.

Ce problème ne se limite pas à la création/insertion de cartes à partir de l'espace utilisateur, car j'ai observé ce problème dans un programme xdp qui a créé une carte et l'a insérée ; ce qui précède reproduit le problème que j'ai observé dans mon programme actuel. Dans mon vrai programme qui comporte également 1024 entrées, j'ai remarqué que ce problème survenait après l'insertion de 16 éléments.

J'ai testé cela sur un serveur de production exécutant le noyau Linux 5.16.7.

J'ai testé sur une machine virtuelle Linux et mis à niveau le noyau vers la version 6.2.8 et j'ai remarqué une différence dans la politique d'expulsion. Par exemple, lorsque max_entries vaut 8, j'observe :

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

Quand max_entries vaut 1024, je remarque qu'après avoir ajouté le 1025ème élément, le total des éléments est de 897. Je ne peux pas tester avec le noyau 6.2.8 sur notre serveur de production.

Bonne réponse

La carte de hachage LRU n'est pas garantie d'avoir exactementle nombre maximum d'éléments, et l'implémentation est évidemment conçue pour fournir de bonnes performances avec bien plus de 8 éléments. Un rapide coup d'œil au code et à ce que j'ai vu :

1. LRU est divisé en deux parties : « liste active » et « liste inactive », et sa tâche est de déplacer périodiquement les éléments d'une partie à l'autre selon qu'ils ont été visités récemment ou non. Ce n'est pas du vrai LRU (les éléments ne se déplacent pas vers la tête à chaque accès).

2. Lorsque la carte est pleine et que quelque chose doit être expulsé pour insérer un nouvel élément, le code expulsera jusqu'à 128 éléments de la liste inactive en un seul passage ; élément de la liste active.

3. Il existe également une "liste libre locale" par CPU d'éléments alloués en attente d'être remplie de données ; lorsqu'elle est vide, elle essaie d'extraire de la liste libre globale, si cette liste est vide, elle entrera dans le chemin d'expulsion. La taille cible de la liste gratuite locale est de 4 entrées.

Le comportement de la version 6.2.8 semble donc simple et cohérent : toutes vos clés sont probablement sur la "liste inactive" (pas trop surprenant pour un modèle d'accès de type scan, ou peut-être que c'est juste qu'elles n'ont toutes aucune chance de promotion pour l'instant), et puis tout le monde a été expulsé. Je ne sais pas grand-chose sur la version 5.16, mais cela pourrait avoir quelque chose à voir avec la liste gratuite locale et toutes les mises à jour exécutées à partir du même processeur.

Fondamentalement, je pense que le type de données n'est pas destiné à être utilisé de la façon dont vous l'utilisez, et l'erreur est celle à laquelle vous vous attendez. Si vous n'êtes pas d'accord, je pense que vous devrez en discuter avec les développeurs du noyau.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!