4.19-stable review patch. If anyone has any objections, please let me know.
------------------
From: Florian Lehner dev@der-flo.net
[ Upstream commit 9b75dbeb36fcd9fc7ed51d370310d0518a387769 ]
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.
Fixes: b95a5c4db09b ("bpf: add a longest prefix match trie map implementation") Signed-off-by: Florian Lehner dev@der-flo.net Signed-off-by: Andrii Nakryiko andrii@kernel.org Link: https://lore.kernel.org/bpf/20231105085801.3742-1-dev@der-flo.net Signed-off-by: Alexei Starovoitov ast@kernel.org Signed-off-by: Sasha Levin sashal@kernel.org --- kernel/bpf/lpm_trie.c | 3 +++ 1 file changed, 3 insertions(+)
diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c index 1a8b208f6c55..fcd3a15add41 100644 --- a/kernel/bpf/lpm_trie.c +++ b/kernel/bpf/lpm_trie.c @@ -194,6 +194,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(trie->root); node;) {