[RFC] A new bpf map type for fuzzy matching key

* [RFC] A new bpf map type for fuzzy matching key
@ 2023-04-16  4:26 沈安琪(凛玥)
  2023-04-16 18:23 ` Alexei Starovoitov
  0 siblings, 1 reply; 3+ messages in thread
From: 沈安琪(凛玥) @ 2023-04-16  4:26 UTC (permalink / raw)
  To: bpf
  Cc: ast, daniel, andrii, martin.lau, 谈鉴锋,
	周强(中航),
	朱辉(茶水),
	张绪峰(云伯)

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.

[0]: 
https://lore.kernel.org/bpf/2172a7a7-323b-9798-f990-00df69b136d0@antgroup.com/T/#u

Sincerely,
Amy

^ permalink raw reply	[flat|nested] 3+ messages in thread