[PATCH bpf] bpf: lpm_trie: check left child of root for NULL

[Jonathan Lemon]

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.le...@gmail.com>
---
 kernel/bpf/lpm_trie.c                      | 9 +++++++--
 tools/testing/selftests/bpf/test_lpm_map.c | 6 +++---
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 09334f13a8a0..38c1397eef6d 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -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 *),
diff --git a/tools/testing/selftests/bpf/test_lpm_map.c 
b/tools/testing/selftests/bpf/test_lpm_map.c
index 02d7c871862a..79410d3857c0 100644
--- a/tools/testing/selftests/bpf/test_lpm_map.c
+++ b/tools/testing/selftests/bpf/test_lpm_map.c
@@ -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);
-- 
2.17.1