Skip to contentSkip to conversation

bpf: lpm_trie: check left child of last leftmost node for NULL

PATCH Applied Jonathan Lemon 3 participants 3 messages Jun 8, 2019 – Jun 11, 2019

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 bpf: lpm_trie: check left child of last leftmost node for NULL

If the leftmost parent node of the tree has does not have a child on the left side, then trie_get_next_key (and bpftool map dump) will not look at the child on the right. This leads to the traversal missing elements.

Lookup is not affected.

Update selftest to handle this case.

Reproducer:

bpftool map create /sys/fs/bpf/lpm type lpm_trie key 6 \
value 1 entries 256 name test_lpm flags 1
bpftool map update pinned /sys/fs/bpf/lpm key 8 0 0 0 0 0 value 1
bpftool map update pinned /sys/fs/bpf/lpm key 16 0 0 0 0 128 value 2
bpftool map dump pinned /sys/fs/bpf/lpm

Returns only 1 element. (2 expected)

Fixes b471f2f1de8 ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE")
---
 kernel/bpf/lpm_trie.c                      |  9 +++--
 tools/testing/selftests/bpf/test_lpm_map.c | 41 ++++++++++++++++++++--
 2 files changed, 45 insertions(+), 5 deletions(-)
kernel/bpf/lpm_trie.c +7 -2
index 09334f13a8a0..ec047a3658b4 100644
@@ -710,9 +710,14 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 	 * have exact two children, so this function will never return NULL.
 	 */
 	for (node = search_root; node;) {
-		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
+		if (node->flags & LPM_TREE_NODE_FLAG_IM) {
+			node = rcu_dereference(node->child[0]);
+		} else {
 			next_node = node;
-		node = rcu_dereference(node->child[0]);
+			node = rcu_dereference(node->child[0]);
+			if (!node)
+				node = rcu_dereference(next_node->child[1]);
+		}
 	}
 do_copy:
 	next_key->prefixlen = next_node->prefixlen;
tools/testing/selftests/bpf/test_lpm_map.c +38 -3

64 lines not on this page · raw message

Signature · 1 line
2.17.1
Acked-by on v2 1/1
#1 lore raw
Quoted 4 lines · Jonathan Lemon

If the leftmost parent node of the tree has does not have a child on the left side, then trie_get_next_key (and bpftool map dump) will not look at the child on the right. This leads to the traversal missing elements.

Good catch!

maintainer Applied
#2 lore raw
In reply to Jonathan Lemon
Quoted 17 lines · Jonathan Lemon

If the leftmost parent node of the tree has does not have a child on the left side, then trie_get_next_key (and bpftool map dump) will not look at the child on the right. This leads to the traversal missing elements.

Lookup is not affected.

Update selftest to handle this case.

Reproducer:

bpftool map create /sys/fs/bpf/lpm type lpm_trie key 6 \
value 1 entries 256 name test_lpm flags 1
bpftool map update pinned /sys/fs/bpf/lpm key 8 0 0 0 0 0 value 1
bpftool map update pinned /sys/fs/bpf/lpm key 16 0 0 0 0 128 value 2
bpftool map dump pinned /sys/fs/bpf/lpm

Quoted 4 lines

Returns only 1 element. (2 expected)

Fixes b471f2f1de8 ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE")

Applied, thanks!