summaryrefslogtreecommitdiffstats
path: root/kernel
diff options
context:
space:
mode:
authorJonathan Lemon <jonathan.lemon@gmail.com>2019-06-08 12:54:19 -0700
committerDaniel Borkmann <daniel@iogearbox.net>2019-06-11 13:52:37 +0200
commitda2577fdd0932ea4eefe73903f1130ee366767d2 (patch)
treec818cc12002f9d99b0b710d496f7c1b84ec379a4 /kernel
parentdce5ccccd1231c6eaec5ede80bce85f2ae536826 (diff)
downloadlinux-da2577fdd0932ea4eefe73903f1130ee366767d2.tar.gz
linux-da2577fdd0932ea4eefe73903f1130ee366767d2.tar.bz2
linux-da2577fdd0932ea4eefe73903f1130ee366767d2.zip
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: b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE") Signed-off-by: Jonathan Lemon <jonathan.lemon@gmail.com> Acked-by: Martin KaFai Lau <kafai@fb.com> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Diffstat (limited to 'kernel')
-rw-r--r--kernel/bpf/lpm_trie.c9
1 files changed, 7 insertions, 2 deletions
diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index e61630c2e50b..864e2a496376 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -716,9 +716,14 @@ find_leftmost:
* 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;