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

[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.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(-)

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

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

[Jonathan Lemon]

On 7 Jun 2019, at 19:44, Jonathan Lemon wrote:

> 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.

I just realized this doesn't handle all cases.  Will reroll a new version.
-- 
Jonathan  (sigh, #fridaynightfollies)