bpf, lpm: fix check prefixlen before walking trie
PATCH 1/1 bpf, lpm: fix check prefixlen before walking trie
When looking up an element in LPM trie, the condition 'matchlen == trie->max_prefixlen' will never return true, if key->prefixlen is larger than trie->max_prefixlen. Consequently all elements in the LPM trie will be visited and no element is returned in the end.
To resolve this, check key->prefixlen first before walking the LPM trie.
--- kernel/bpf/lpm_trie.c | 3 +++ 1 file changed, 3 insertions(+)
kernel/bpf/lpm_trie.c +3 -0
@@ -231,6 +231,9 @@ static void *trie_lookup_elem(struct bpf_map *map, void *_key)struct lpm_trie_node *node, *found =NULL ;struct bpf_lpm_trie_key *key = _key; +if (key->prefixlen > trie->max_prefixlen) +return NULL ; +/* Start walking the trie from the root node ... */ for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());
Signature · 1 line
2.39.2
Hi
Quoted 6 lines · Florian Lehner
When looking up an element in LPM trie, the condition 'matchlen ==
trie->max_prefixlen' will never return true, ifkey->prefixlenis larger thantrie->max_prefixlen. Consequently all elements in the LPM trie will be visited and no element is returned in the end.To resolve this, check
key->prefixlenfirst before walking the LPM trie.
Am I understanding you right that this is an optimization to avoid walking the entire trie? Because the way I read your commit-message I assume the output has always been NULL? Or am I missing something.
Do you have a specific use-case where such lookups are common? Can you explain why it is important to optimize this case? Because you now add a condition for every lookup just to optimize for the lookup-miss of a special case. I don't think I understand your reasoning here, but I might be missing some context.
Thanks!
David
Quoted 23 lines
Fixes b95a5c4db09b ("bpf: add a longest prefix match trie map implementation")Signed-off-by Florian Lehner <[email protected]>--- kernel/bpf/lpm_trie.c | 3 +++ 1 file changed, 3 insertions(+)kernel/bpf/lpm_trie.c +3
-0@@ -231,6 +231,9 @@ static void *trie_lookup_elem(struct bpf_map *map, void *_key)struct lpm_trie_node *node, *found =NULL ;struct bpf_lpm_trie_key *key = _key; +if (key->prefixlen > trie->max_prefixlen) +return NULL ; +/* Start walking the trie from the root node ... */ for (node =
rcu_dereference_check(trie->root, rcu_read_lock_bh_held());Signature · 1 line
2.39.2
Quoted 9 lines · David Rheinsberg
Hi
Quoted 5 lines · Florian Lehner
When looking up an element in LPM trie, the condition 'matchlen ==
trie->max_prefixlen' will never return true, ifkey->prefixlenis larger thantrie->max_prefixlen. Consequently all elements in the LPM trie will be visited and no element is returned in the end.
Quoted 6 lines
Am I understanding you right that this is an optimization to avoid walking the entire trie? Because the way I read your commit-message I assume the output has always been NULL? Or am I missing something.
Do you have a specific use-case where such lookups are common? Can you explain why it is important to optimize this case? Because you now add a condition for every lookup just to optimize for the lookup-miss of a special case. I don't think I understand your reasoning here, but I might be missing some context.
Thanks!
David
Hi David,
Your understanding is correct. The return value currently and with this patch is in both cases the same for the case where key->prefixlen > trie->max_prefixlen.
The optimization is to avoid the locking mechanism, walking the trie and checking its elements. It might not be the most common use case, so I see your point.
Quoted 24 lines
Quoted 24 lines
Fixes b95a5c4db09b ("bpf: add a longest prefix match trie map implementation")Signed-off-by Florian Lehner <[email protected]>--- kernel/bpf/lpm_trie.c | 3 +++ 1 file changed, 3 insertions(+)kernel/bpf/lpm_trie.c +3
-0@@ -231,6 +231,9 @@ static void *trie_lookup_elem(struct bpf_map *map, void *_key)struct lpm_trie_node *node, *found =NULL ;struct bpf_lpm_trie_key *key = _key; +if (key->prefixlen > trie->max_prefixlen) +return NULL ; +/* Start walking the trie from the root node ... */ for (node =
rcu_dereference_check(trie->root, rcu_read_lock_bh_held());Signature · 1 line
2.39.2
Hi
Quoted 7 lines · Florian Lehner
Quoted 6 lines · David Rheinsberg
Quoted 4 lines · Florian Lehner
When looking up an element in LPM trie, the condition 'matchlen ==
trie->max_prefixlen' will never return true, ifkey->prefixlenis larger thantrie->max_prefixlen. Consequently all elements in the LPM trie will be visited and no element is returned in the end.
Quoted 6 lines
Quoted 3 lines
Am I understanding you right that this is an optimization to avoid walking the entire trie? Because the way I read your commit-message I assume the output has always been NULL? Or am I missing something.
Do you have a specific use-case where such lookups are common? Can you explain why it is important to optimize this case? Because you now add a condition for every lookup just to optimize for the lookup-miss of a special case. I don't think I understand your reasoning here, but I might be missing some context.
Your understanding is correct. The return value currently and with this patch is in both cases the same for the case where
key->prefixlen>trie->max_prefixlen.
Thanks for clarifying! I think using "fix" to describe the patch is misleading and confused me. Similarly, your "Fixes:" tag implies you repaired something that was broken.
Quoted 3 lines
The optimization is to avoid the locking mechanism, walking the trie and checking its elements. It might not be the most common use case, so I see your point.
Can you elaborate on how you encountered this? Do you have an actual use-case where such lookups better be fast? Is it worth it slowing down every other lookup just to make this one faster?
The patch looks good, but I also don't see the benefit. I am not against it, though, if you insist you need it.
Thanks
David
This patch was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Quoted 8 lines · On Sun, 5 Nov 2023 09:58:01 +0100 you wrote:
When looking up an element in LPM trie, the condition 'matchlen ==
trie->max_prefixlen' will never return true, ifkey->prefixlenis larger thantrie->max_prefixlen. Consequently all elements in the LPM trie will be visited and no element is returned in the end.To resolve this, check
key->prefixlenfirst before walking the LPM trie.[...]
Here is the summary with links:
- [bpf-next] bpf, lpm: fix check prefixlen before walking trie
https://git.kernel.org/bpf/bpf-next/c/856624f12b04
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html