diff options
| author | Hou Tao <houtao1@huawei.com> | 2024-12-06 19:06:18 +0800 |
|---|---|---|
| committer | Greg Kroah-Hartman <gregkh@linuxfoundation.org> | 2024-12-14 20:03:19 +0100 |
| commit | 412bf01fd5dbda4a1062bd16cbcc0cbdf3bb2a7b (patch) | |
| tree | 3b5221bc80226486e3eb9dc882c921315d10b4af /kernel | |
| parent | 7218e441ad9d8f76cd76402035713c3c53865129 (diff) | |
| download | linux-412bf01fd5dbda4a1062bd16cbcc0cbdf3bb2a7b.tar.gz linux-412bf01fd5dbda4a1062bd16cbcc0cbdf3bb2a7b.tar.bz2 linux-412bf01fd5dbda4a1062bd16cbcc0cbdf3bb2a7b.zip | |
bpf: Fix exact match conditions in trie_get_next_key()
[ Upstream commit 27abc7b3fa2e09bbe41e2924d328121546865eda ]
trie_get_next_key() uses node->prefixlen == key->prefixlen to identify
an exact match, However, it is incorrect because when the target key
doesn't fully match the found node (e.g., node->prefixlen != matchlen),
these two nodes may also have the same prefixlen. It will return
expected result when the passed key exist in the trie. However when a
recently-deleted key or nonexistent key is passed to
trie_get_next_key(), it may skip keys and return incorrect result.
Fix it by using node->prefixlen == matchlen to identify exact matches.
When the condition is true after the search, it also implies
node->prefixlen equals key->prefixlen, otherwise, the search would
return NULL instead.
Fixes: b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")
Reviewed-by: Toke Høiland-Jørgensen <toke@redhat.com>
Signed-off-by: Hou Tao <houtao1@huawei.com>
Link: https://lore.kernel.org/r/20241206110622.1161752-6-houtao@huaweicloud.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Sasha Levin <sashal@kernel.org>
Diffstat (limited to 'kernel')
| -rw-r--r-- | kernel/bpf/lpm_trie.c | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c index fcc5cd358d7f..010e91ac978e 100644 --- a/kernel/bpf/lpm_trie.c +++ b/kernel/bpf/lpm_trie.c @@ -646,7 +646,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key) struct lpm_trie_node **node_stack = NULL; int err = 0, stack_ptr = -1; unsigned int next_bit; - size_t matchlen; + size_t matchlen = 0; /* The get_next_key follows postorder. For the 4 node example in * the top of this file, the trie_get_next_key() returns the following @@ -685,7 +685,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key) next_bit = extract_bit(key->data, node->prefixlen); node = rcu_dereference(node->child[next_bit]); } - if (!node || node->prefixlen != key->prefixlen || + if (!node || node->prefixlen != matchlen || (node->flags & LPM_TREE_NODE_FLAG_IM)) goto find_leftmost; |