* [PATCH bpf] bpf: lpm_trie: check left child of root for NULL
@ 2019-06-08 2:44 Jonathan Lemon
2019-06-08 15:21 ` Jonathan Lemon
0 siblings, 1 reply; 2+ messages in thread
From: Jonathan Lemon @ 2019-06-08 2:44 UTC (permalink / raw)
To: yhs, ast, daniel; +Cc: kernel-team, netdev
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
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [PATCH bpf] bpf: lpm_trie: check left child of root for NULL
2019-06-08 2:44 [PATCH bpf] bpf: lpm_trie: check left child of root for NULL Jonathan Lemon
@ 2019-06-08 15:21 ` Jonathan Lemon
0 siblings, 0 replies; 2+ messages in thread
From: Jonathan Lemon @ 2019-06-08 15:21 UTC (permalink / raw)
To: yhs, ast, daniel; +Cc: kernel-team, netdev
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)
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2019-06-08 15:21 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-08 2:44 [PATCH bpf] bpf: lpm_trie: check left child of root for NULL Jonathan Lemon
2019-06-08 15:21 ` Jonathan Lemon
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).