On Sat, Apr 15, 2023 at 9:32 PM 沈安琪(凛玥) <amy.saq@xxxxxxxxxxxx> wrote:
>
>
> Hi everyone,
>
> For supporting fuzzy matching in bpf map as described in the original
> question [0], we come up with a proposal that would like to have some
> advice or comments from bpf thread. Thanks a lot for all the feedback :)
>
> We plan to implement a new bpf map type, naming BPF_FM_MAP, standing for
> fuzzy matching map.
> The basic idea is implementing a trie-tree using map of map runtime
> structure.
>
> The number of tree levels equals to the number of fields in the key
> struct. Assuming that the key struct has M fields, the first (M-1) level
> of tree nodes will be hash maps with key as the value of (M-1)-th field
> and entry as the fd of next level map. The last level, regarded as leaf
> nodes, will be hash maps with key as the value of M-th field and entry
> as user-defined entry for this BPF_FM_MAP.
>
> To support fuzzy matching, we add a special value -1 as (M-1)-th field
> key if (M-1)-th field is set as general match.
>
> When looking up a target key in BPF_FM_MAP, it will lookup the first
> level hashmap, matching the entry with the same value on this field and
> with -1 if exists. Then it will lookup the next-level hashmap, whose fd
> is the value it get from the previous level hashmap. It will go through
> all the levels of tree and get a set of leaf nodes it matches. Finally,
> it will sort the set of matched leaf nodes based on their priority,
> which is defined in BPF_FM_MAP entry struct, and return the
> corresponding return value also defined in BPF_FM_MAP entry struct.
>
>
> Given a user-defined key struct and entry struct as following:
>
> struct fm_key {
> int a;
> int b;
> int c;
> }
>
> struct fm_entry {
> int priority;
> int value;
> }
>
> and declare a BPF_FM_MAP DEMO_MAP to store incoming key-value pair:
>
> struct {
> __uint(type, BPF_FM_MAP);
> __type(key, struct fm_key);
> __type(value, struct fm_entry);
> __uint(pinning, LIBBPF_PIN_BY_NAME);
> __uint(max_entries, 1024);
> __uint(map_flags, BPF_F_NO_PREALLOC);
> } DEMO_MAP SEC(".maps");
>
> Now, we add the following three key-value pairs into DEMO_MAP:
>
> |a |b |c |priority |value |
> |- |- |1 |1 |1 |
> |- |2 |1 |2 |2 |
> |3 |2 |1 |3 |3 |
>
> The tree will be constructed as following:
>
> field a field b field c
>
> fd = 3
> ---->| key | (prioriy, value) |
> | | 1 | (1, 1) |
> |
> fd = 1 |
> -->| key | val | |
> | | -1 | 3 |---- fd = 4
> | | 2 | 4 |-------->| key | (prioriy, value) |
> fd = 0 | | 1 | (2, 2) |
> | key | val | |
> | -1 | 1 |----
> | 3 | 2 |----
> | fd = 2
> -->| key | val | fd = 5
> | 2 | 5 |-------->| key | (prioriy, value) |
> | 1 | (3, 3) |
>
>
> After updating the tree, we have three target tuples to lookup in DEMO_MAP.
>
> struct fm_key t1 = {
> .a = 6,
> .b = 4,
> .c = 1
> };
>
> struct fm_key t2 = {
> .a = 5,
> .b = 2,
> .c = 1
> };
>
> struct fm_key t3 = {
> .a = 3,
> .b = 2,
> .c = 1
> };
>
> // map lookup order: 0 -> 1 -> 3
> // matched leaf nodes: (1, 1)
> // picked return value: 1
> map_lookup_elem(&DEMO_MAP, &t1) == 1
>
> // map loopup order: 0 -> 1 -> (3, 4)
> // matched leaf nodes: (1, 1), (2, 2)
> // picked return value: 2
> map_lookup_elem(&DEMO_MAP, &t2) == 2
>
> // map lookup order: 0 -> (1, 2) -> (3, 4, 5)
> // matched leaf nodes: (1, 1), (2, 2), (3, 3)
> // picked return value: 3
> map_loopup_elem(&DEMO_MAP, &t3) == 3
>
>
> Thanks a lot for reviewing this proposal and we really appreciate any
> feedback here.
This sounds like several hash maps chained together with a custom logic.
If so it's not clear why a new map type is necessary.
Just let bpf prog lookup multiple hash maps.
