@@ -657,8 +657,13 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
return -ENOENT;
/* For invalid key, find the leftmost node in the trie */
- if (!key || key->prefixlen > trie->max_prefixlen)
- goto find_leftmost;
+ if (!key || key->prefixlen > trie->max_prefixlen) {
+ if (!rcu_dereference(search_root->child[0])) {
+ next_node = search_root;
+ search_root = rcu_dereference(search_root->child[1]);
+ }
+ goto find_leftmost;
+ }
node_stack = kmalloc_array(trie->max_prefixlen,
sizeof(struct lpm_trie_node *),
@@ -573,13 +573,13 @@ static void test_lpm_get_next_key(void)
/* add one more element (total two) */
key_p->prefixlen = 24;
- inet_pton(AF_INET, "192.168.0.0", key_p->data);
+ inet_pton(AF_INET, "192.168.128.0", key_p->data);
assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
memset(key_p, 0, key_size);
assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
- key_p->data[1] == 168 && key_p->data[2] == 0);
+ key_p->data[1] == 168 && key_p->data[2] == 128);
memset(next_key_p, 0, key_size);
assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
@@ -592,7 +592,7 @@ static void test_lpm_get_next_key(void)
/* Add one more element (total three) */
key_p->prefixlen = 24;
- inet_pton(AF_INET, "192.168.128.0", key_p->data);
+ inet_pton(AF_INET, "192.168.0.0", key_p->data);
assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
memset(key_p, 0, key_size);
If the root of the tree has does not have any elements on the left branch, then trie_get_next_key (and bpftool map dump) will not look at the rightmost branch. 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") Signed-off-by: Jonathan Lemon <jonathan.lemon@gmail.com> --- kernel/bpf/lpm_trie.c | 9 +++++++-- tools/testing/selftests/bpf/test_lpm_map.c | 6 +++--- 2 files changed, 10 insertions(+), 5 deletions(-)