bpf: Fix out-of-bounds write in trie_get_next_key()
Subsystems (3)
PATCH 1/1 bpf: Fix out-of-bounds write in trie_get_next_key()
trie_get_next_key() allocates a node stack with size trie->max_prefixlen, while it writes (trie->max_prefixlen + 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie with max_prefixlen is 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls to trie_get_next_key with _key with .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
--- kernel/bpf/lpm_trie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/lpm_trie.c +1 -1
@@ -655,7 +655,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)if (!key || key->prefixlen > trie->max_prefixlen) goto find_leftmost; - node_stack =kmalloc_array (trie->max_prefixlen, + node_stack =kmalloc_array (trie->max_prefixlen +1 ,sizeof (struct lpm_trie_node *),GFP_ATOMIC | __GFP_NOWARN);if (!node_stack)
Signature · 1 line
2.43.5
Quoted 9 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.Fixes b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")Signed-off-by Byeonguk Jeong <[email protected]>
Makes sense!
Quoted 7 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
Hmm. It sounds possible, but pls demonstrate it with a selftest. With the amount of fuzzing I'm surprised it was not discovered earlier.
pw-bot: cr
Quoted 9 lines · Alexei Starovoitov
Quoted 7 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
Quoted 4 lines
Hmm. It sounds possible, but pls demonstrate it with a selftest. With the amount of fuzzing I'm surprised it was not discovered earlier.
pw-bot: cr
With a simple test below, the kernel crashes in a minute or you can easily discover the bug on KFENCE-enabled kernels.
#!/bin/bash
bpftool map create /sys/fs/bpf/lpm type lpm_trie key 5 value 1 \
entries 16 flags 0x1name lpm
for i in {0..8}; do
bpftool map update pinned /sys/fs/bpf/lpm \ key hex 0$i 00 00 00 00 \ value hex 00 any
done
while true; do
bpftool map dump pinned /sys/fs/bpf/lpm
done
In my environment (6.12-rc4, with CONFIG_KFENCE), dmesg gave me this message as expected.
[ 463.141394] BUG: KFENCE: out-of-bounds write in trie_get_next_key+0x2f2/0x670
[ 463.143422] Out-of-bounds write at 0x0000000095bc45ea (256B right of kfence-#156): [ 463.144438] trie_get_next_key+0x2f2/0x670 [ 463.145439] map_get_next_key+0x261/0x410 [ 463.146444] __sys_bpf+0xad4/0x1170 [ 463.147438] __x64_sys_bpf+0x74/0xc0 [ 463.148431] do_syscall_64+0x79/0x150 [ 463.149425] entry_SYSCALL_64_after_hwframe+0x76/0x7e
[ 463.151436] kfence-#156: 0x00000000279749c1-0x0000000034dc4abb, size=256, cache=kmalloc-256
[ 463.153414] allocated by task 2021 on cpu 2 at 463.140440s (0.012974s ago): [ 463.154413] trie_get_next_key+0x252/0x670 [ 463.155411] map_get_next_key+0x261/0x410 [ 463.156402] __sys_bpf+0xad4/0x1170 [ 463.157390] __x64_sys_bpf+0x74/0xc0 [ 463.158386] do_syscall_64+0x79/0x150 [ 463.159372] entry_SYSCALL_64_after_hwframe+0x76/0x7e
Quoted 9 lines · Alexei Starovoitov
Quoted 7 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
Quoted 4 lines
Hmm. It sounds possible, but pls demonstrate it with a selftest. With the amount of fuzzing I'm surprised it was not discovered earlier.
pw-bot: cr
I sent this again because lkml did not understand previous one which is 8B encoded.
With a simple test below, the kernel crashes in a minute or you can discover the bug on KFENCE-enabled kernels easily.
#!/bin/bash
bpftool map create /sys/fs/bpf/lpm type lpm_trie key 5 value 1 \
entries 16 flags 0x1name lpm
for i in {0..8}; do
bpftool map update pinned /sys/fs/bpf/lpm \ key hex 0$i 00 00 00 00 \ value hex 00 any
done
while true; do
bpftool map dump pinned /sys/fs/bpf/lpm
done
In my environment (6.12-rc4, with CONFIG_KFENCE), dmesg gave me this message as expected.
[ 463.141394] BUG: KFENCE: out-of-bounds write in trie_get_next_key+0x2f2/0x670
[ 463.143422] Out-of-bounds write at 0x0000000095bc45ea (256B right of kfence-#156): [ 463.144438] trie_get_next_key+0x2f2/0x670 [ 463.145439] map_get_next_key+0x261/0x410 [ 463.146444] __sys_bpf+0xad4/0x1170 [ 463.147438] __x64_sys_bpf+0x74/0xc0 [ 463.148431] do_syscall_64+0x79/0x150 [ 463.149425] entry_SYSCALL_64_after_hwframe+0x76/0x7e
[ 463.151436] kfence-#156: 0x00000000279749c1-0x0000000034dc4abb, size=256, cache=kmalloc-256
[ 463.153414] allocated by task 2021 on cpu 2 at 463.140440s (0.012974s ago): [ 463.154413] trie_get_next_key+0x252/0x670 [ 463.155411] map_get_next_key+0x261/0x410 [ 463.156402] __sys_bpf+0xad4/0x1170 [ 463.157390] __x64_sys_bpf+0x74/0xc0 [ 463.158386] do_syscall_64+0x79/0x150 [ 463.159372] entry_SYSCALL_64_after_hwframe+0x76/0x7e
Quoted 10 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.Fixes b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")Signed-off-by Byeonguk Jeong <[email protected]>---
Without the fix, there will be KASAN report as show below when dumping all keys in the lpm-trie through bpf_map_get_next_key().
However, I have a dumb question: does it make sense to reject the element with prefixlen = 0 ? Because I can't think of a use case where a zero-length prefix will be useful.
==================================================================
BUG: KASAN: slab-out-of-bounds in trie_get_next_key+0x133/0x530 Write of size 8 at addr ffff8881076c2fc0 by task test_lpm_trie.b/446 CPU: 0 UID: 0 PID: 446 Comm: test_lpm_trie.b Not tainted 6.11.0+ #52 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), ... Call Trace: <TASK> dump_stack_lvl+0x6e/0xb0 print_report+0xce/0x610 ? trie_get_next_key+0x133/0x530 ? kasan_complete_mode_report_info+0x3c/0x200 ? trie_get_next_key+0x133/0x530 kasan_report+0x9c/0xd0 ? trie_get_next_key+0x133/0x530 __asan_store8+0x81/0xb0 trie_get_next_key+0x133/0x530 __sys_bpf+0x1b03/0x3140 ? __pfx___sys_bpf+0x10/0x10 ? __pfx_vfs_write+0x10/0x10 ? find_held_lock+0x8e/0xb0 ? ksys_write+0xee/0x180 ? syscall_exit_to_user_mode+0xb3/0x220 ? mark_held_locks+0x28/0x90 ? mark_held_locks+0x28/0x90 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7e RIP: 0033:0x7f9c5e9c9c5d ...... </TASK> Allocated by task 446: kasan_save_stack+0x28/0x50 kasan_save_track+0x14/0x30 kasan_save_alloc_info+0x36/0x40 __kasan_kmalloc+0x84/0xa0 __kmalloc_noprof+0x214/0x540 trie_get_next_key+0xa7/0x530 __sys_bpf+0x1b03/0x3140 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7e The buggy address belongs to the object at ffff8881076c2f80
which belongs to the cache kmalloc-rnd-09-64 of size 64 The buggy address is located 0 bytes to the right of allocated 64-byte region [ffff8881076c2f80, ffff8881076c2fc0)
Quoted 16 lines
kernel/bpf/lpm_trie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/bpf/lpm_trie.c +1
-1@@ -655,7 +655,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)if (!key || key->prefixlen > trie->max_prefixlen) goto find_leftmost; - node_stack =kmalloc_array (trie->max_prefixlen, + node_stack =kmalloc_array (trie->max_prefixlen +1 ,sizeof (struct lpm_trie_node *),GFP_ATOMIC | __GFP_NOWARN);if (!node_stack)
Quoted 3 lines · Hou Tao
Without the fix, there will be KASAN report as show below when dumping all keys in the lpm-trie through
bpf_map_get_next_key().
Thank you for testing.
Quoted 4 lines
However, I have a dumb question: does it make sense to reject the element with prefixlen = 0 ? Because I can't think of a use case where a zero-length prefix will be useful.
With prefixlen = 0, it would always return -ENOENT, I think. Maybe it is good to reject it earlier!
Hi,
Quoted 4 lines · Byeonguk Jeong
Quoted 2 lines · Hou Tao
Without the fix, there will be KASAN report as show below when dumping all keys in the lpm-trie through
bpf_map_get_next_key().Thank you for testing.
Alexei suggested adding a bpf self-test for the patch. I think you could reference the code in lpm_trie_map_batch_ops.c [1] or similar and add a new file that uses bpf_map_get_next_key to demonstrate the out-of-bound problem. The test can be run by ./test_maps. There is some document for the procedure in [2].
[1]: tools/testing/selftests/bpf/map_tests/lpm_trie_map_batch_ops.c [2]:
https://github.com/torvalds/linux/blob/master/Documentation/bpf/bpf_devel_QA.rst
Quoted 8 lines
Quoted 4 lines
However, I have a dumb question: does it make sense to reject the element with prefixlen = 0 ? Because I can't think of a use case where a zero-length prefix will be useful.
With prefixlen = 0, it would always return
-ENOENT, I think. Maybe it is good to reject it earlier!.
Which procedure will return -ENOENT ? I think the element with prefixlen=0 could still be found through the key with prefixlen = 0.
Hi,
Quoted 9 lines · Hou Tao
Alexei suggested adding a bpf self-test for the patch. I think you could reference the code in
lpm_trie_map_batch_ops.c[1] or similar and add a new file that usesbpf_map_get_next_keyto demonstrate the out-of-bound problem. The test can be run by ./test_maps. There is some document for the procedure in [2].[1]:
tools/testing/selftests/bpf/map_tests/lpm_trie_map_batch_ops.c[2]:
https://github.com/torvalds/linux/blob/master/Documentation/bpf/bpf_devel_QA.rst
Okay, I will add a new test. Thanks for the detailed guideline.
Quoted 2 lines
Which procedure will return
-ENOENT? I think the element with prefixlen=0 could still be found through the key with prefixlen = 0.
I mean, BPF_MAP_GET_NEXT_KEY with .prefixlen = 0 would give us -ENOENT, as it follows postorder. BPF_MAP_LOOKUP_ELEM still find the element with prefixlen 0 through the key with prefixlen 0 as you said.
Quoted 12 lines · Byeonguk Jeong
Hi,
Quoted 9 lines · Hou Tao
Alexei suggested adding a bpf self-test for the patch. I think you could reference the code in
lpm_trie_map_batch_ops.c[1] or similar and add a new file that usesbpf_map_get_next_keyto demonstrate the out-of-bound problem. The test can be run by ./test_maps. There is some document for the procedure in [2].[1]:
tools/testing/selftests/bpf/map_tests/lpm_trie_map_batch_ops.c[2]:
https://github.com/torvalds/linux/blob/master/Documentation/bpf/bpf_devel_QA.rst
Quoted 7 lines
Okay, I will add a new test. Thanks for the detailed guideline.
Quoted 2 lines
Which procedure will return
-ENOENT? I think the element with prefixlen=0 could still be found through the key with prefixlen = 0.I mean,
BPF_MAP_GET_NEXT_KEYwith .prefixlen = 0 would give us-ENOENT, as it follows postorder.BPF_MAP_LOOKUP_ELEMstill find the element with prefixlen 0 through the key with prefixlen 0 as you said.
I see. But considering the element with .prefixlen = 0 is the last one in the map, returning -ENOENT is expected.
Quoted 1 line
.
PATCH 1/1 selftests/bpf: Add test for trie_get_next_key()
In reply to Byeonguk JeongAdd a test for out-of-bounds write in trie_get_next_key() when a full path from root to leaf exists and bpf_map_get_next_key() is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.
--- .../bpf/map_tests/lpm_trie_map_get_next_key.c | 115 ++++++++++++++++++ 1 file changed, 115 insertions(+) create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +115 -0
@@ -0,0 +1,115 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* WARNING +* ------- +* This test suite may crash the kernel, thus should be run in a VM. +*/ + +#define _GNU_SOURCE +#include <linux/bpf.h> +#include <stdio.h> +#include <stdbool.h> +#include <unistd.h> +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <pthread.h> + +#include <bpf/bpf.h> +#include <bpf/libbpf.h> + +#include <test_maps.h> + +struct test_lpm_key { +__u32 prefix; +__u32 data; +}; + +struct get_next_key_ctx { +struct test_lpm_key key; +bool start; +bool stop; +int map_fd; +int loop; +}; + +static void *get_next_key_fn (void *arg) +{ +struct get_next_key_ctx *ctx = arg; +struct test_lpm_key next_key; +int i; + +while (!ctx->start) +usleep (1 ); + +while (!ctx->stop && i++ < ctx->loop) +bpf_map_get_next_key (ctx->map_fd, &ctx->key, &next_key); + +return NULL ; +} + +static void abort_get_next_key (struct get_next_key_ctx *ctx,pthread_t *tids, +unsigned int nr) +{ +unsigned int i; + + ctx->stop = true; + ctx->start = true; +for (i =0 ; i < nr; i++) +pthread_join (tids[i],NULL ); +} + +/* This test aims to prevent regression of future. As long as the kernel does +* not panic, it is considered as success. +*/ +void test_lpm_trie_map_get_next_key (void ) +{ +#define MAX_NR_THREADS 256 +LIBBPF_OPTS (bpf_map_create_opts, create_opts, + .map_flags = BPF_F_NO_PREALLOC); +struct test_lpm_key key = {}; +__u32 val =0 ; +int map_fd; +const __u32 max_prefixlen =8 * (sizeof (key) -sizeof (key.prefix)); +const __u32 max_entries = max_prefixlen +1 ; +unsigned int i, nr =MAX_NR_THREADS , loop =4096 ; +pthread_t tids[MAX_NR_THREADS ]; +struct get_next_key_ctx ctx; +int err; + + map_fd =bpf_map_create (BPF_MAP_TYPE_LPM_TRIE ,"lpm_trie_map" , +sizeof (struct test_lpm_key ),sizeof (__u32), + max_entries, &create_opts); +CHECK (map_fd ==-1 ,"bpf_map_create(), error:%s\n" , +strerror (errno)); + +for (i =0 ; i <= max_prefixlen; i++) { + key.prefix = i; + err =bpf_map_update_elem (map_fd, &key, &val,BPF_ANY ); +CHECK (err,"bpf_map_update_elem()" ,"error:%s\n" , +strerror (errno)); + } + + ctx.start = false; + ctx.stop = false; + ctx.map_fd = map_fd; + ctx.loop = loop; +memcpy (&ctx.key, &key,sizeof (key)); + +for (i =0 ; i < nr; i++) { + err =pthread_create (&tids[i],NULL , get_next_key_fn, &ctx); +if (err) { +abort_get_next_key (&ctx, tids, i); +CHECK (err,"pthread_create" ,"error %d\n" , err); + } + } + + ctx.start = true; +for (i =0 ; i < nr; i++) +pthread_join (tids[i],NULL ); + +printf ("%s:PASS\n" , __func__); + +close (map_fd); +}
Signature · 1 line
2.43.5
Daniel Borkmann
maintainerRe: [PATCH] selftests/bpf: Add test for trie_get_next_key()
Hi Byeonguk,
Quoted 6 lines · Byeonguk Jeong
Add a test for out-of-bounds write in
trie_get_next_key()when a full path from root to leaf exists andbpf_map_get_next_key()is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.Signed-off-by Byeonguk Jeong <[email protected]>
Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI cannot test both in combination (pls make sure subject has [PATCH bpf] so that our CI adds this on top of the bpf tree).
Right now the CI selftest build threw an error:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]
84 | CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
| ^~~~~ TEST-OBJ [test_maps] task_storage_map.test.o
TEST-OBJ [test_progs] access_variable_array.test.o
cc1: all warnings being treated as errors
TEST-OBJ [test_progs] align.test.o
TEST-OBJ [test_progs] arena_atomics.test.o
make: *** [Makefile:765: /tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
make: *** Waiting for unfinished jobs....
GEN-SKEL [test_progs-no_alu32] test_usdt.skel.h
make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'
Also on quick glance, please use ASSERT_*() macros instead of CHECK() as the latter is deprecated.
Thanks,
Daniel
Re: [PATCH] selftests/bpf: Add test for trie_get_next_key()
Hi Daniel,
Okay, I will submit them in a series of patches. Btw, ASSERT_* macros are not defined for map_tests. Should I add the definitions for them, or just go with CHECK?
Thanks,
Byeonguk
Quoted 35 lines · Daniel Borkmann
Hi Byeonguk,
Quoted 6 lines · Byeonguk Jeong
Add a test for out-of-bounds write in
trie_get_next_key()when a full path from root to leaf exists andbpf_map_get_next_key()is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.Signed-off-by Byeonguk Jeong <[email protected]>Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI cannot test both in combination (pls make sure subject has [PATCH bpf] so that our CI adds this on top of the bpf tree).
Right now the CI selftest build threw an error:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]84 | CHECK(map_fd == -1, "bpf_map_create(), error:%s\n", | ^~~~~TEST-OBJ [
test_maps] task_storage_map.test.o
TEST-OBJ [test_progs] access_variable_array.test.o
cc1: all warnings being treated as errors
TEST-OBJ [test_progs] align.test.o
TEST-OBJ [test_progs] arena_atomics.test.o
make: *** [Makefile:765:/tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
make: *** Waiting for unfinished jobs....
GEN-SKEL [test_progs-no_alu32]test_usdt.skel.h
make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'Also on quick glance, please use ASSERT_*() macros instead of
CHECK()as the latter is deprecated.Thanks,
Daniel
Re: [PATCH] selftests/bpf: Add test for trie_get_next_key()
Hi,
Quoted 5 lines · Byeonguk Jeong
Hi Daniel,
Okay, I will submit them in a series of patches. Btw, ASSERT_* macros are not defined for
map_tests. Should I add the definitions for them, or just go with CHECK?
For tests in map_tests, I think using CHECK() will be fine.
Quoted 40 lines
Thanks,
ByeongukQuoted 29 lines · Daniel Borkmann
Hi Byeonguk,
Quoted 6 lines · Byeonguk Jeong
Add a test for out-of-bounds write in
trie_get_next_key()when a full path from root to leaf exists andbpf_map_get_next_key()is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.Signed-off-by Byeonguk Jeong <[email protected]>Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI cannot test both in combination (pls make sure subject has [PATCH bpf] so that our CI adds this on top of the bpf tree).
Right now the CI selftest build threw an error:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
/tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]84 | CHECK(map_fd == -1, "bpf_map_create(), error:%s\n", | ^~~~~TEST-OBJ [
test_maps] task_storage_map.test.o
TEST-OBJ [test_progs] access_variable_array.test.o
cc1: all warnings being treated as errors
TEST-OBJ [test_progs] align.test.o
TEST-OBJ [test_progs] arena_atomics.test.o
make: *** [Makefile:765:/tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
make: *** Waiting for unfinished jobs....
GEN-SKEL [test_progs-no_alu32]test_usdt.skel.h
make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'Quoted 5 lines
Also on quick glance, please use ASSERT_*() macros instead of
CHECK()as the latter is deprecated.Thanks,
Daniel.
Daniel Borkmann
maintainerRe: [PATCH] selftests/bpf: Add test for trie_get_next_key()
Quoted 7 lines · Hou Tao
Quoted 4 lines · Byeonguk Jeong
Okay, I will submit them in a series of patches. Btw, ASSERT_* macros are not defined for
map_tests. Should I add the definitions for them, or just go with CHECK?For tests in
map_tests, I think usingCHECK()will be fine.
Given there is no alternative infra, agree. Would be nice to convert this over at some point.
Best,
Daniel
Re: [PATCH] selftests/bpf: Add test for trie_get_next_key()
In reply to Byeonguk JeongHi,
Quoted 17 lines · Byeonguk Jeong
Add a test for out-of-bounds write in
trie_get_next_key()when a full path from root to leaf exists andbpf_map_get_next_key()is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.Signed-off-by Byeonguk Jeong <[email protected]>--- .../bpf/map_tests/lpm_trie_map_get_next_key.c | 115 ++++++++++++++++++ 1 file changed, 115 insertions(+) create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.ctools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +0
-0
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c line 8
Quoted 8 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +8
-0@@ -0,0 +1,115 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* WARNING +* ------- +* This test suite may crash the kernel, thus should be run in a VM. +*/ +
The comments above are unnecessary, please remove it.
Quoted 23 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +23
-0+#define _GNU_SOURCE +#include <linux/bpf.h> +#include <stdio.h> +#include <stdbool.h> +#include <unistd.h> +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <pthread.h> + +#include <bpf/bpf.h> +#include <bpf/libbpf.h> + +#include <test_maps.h> + +struct test_lpm_key { +__u32 prefix; +__u32 data; +}; + +struct get_next_key_ctx { +struct test_lpm_key key; +bool start;
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c line 41
Quoted 10 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +10
-0+bool stop; +int map_fd; +int loop; +}; + +static void *get_next_key_fn (void *arg) +{ +struct get_next_key_ctx *ctx = arg; +struct test_lpm_key next_key; +int i;
int i = 0;
Quoted 17 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +17
-0+ +while (!ctx->start) +usleep (1 ); + +while (!ctx->stop && i++ < ctx->loop) +bpf_map_get_next_key (ctx->map_fd, &ctx->key, &next_key); + +return NULL ; +} + +static void abort_get_next_key (struct get_next_key_ctx *ctx,pthread_t *tids, +unsigned int nr) +{ +unsigned int i; + + ctx->stop = true; + ctx->start = true;
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c line 68
Quoted 10 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +10
-0+for (i =0 ; i < nr; i++) +pthread_join (tids[i],NULL ); +} + +/* This test aims to prevent regression of future. As long as the kernel does +* not panic, it is considered as success. +*/ +void test_lpm_trie_map_get_next_key (void ) +{ +#define MAX_NR_THREADS 256
Are 8 threads sufficient to reproduce the problem ?
Quoted 7 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +7
-0+LIBBPF_OPTS (bpf_map_create_opts, create_opts, + .map_flags = BPF_F_NO_PREALLOC); +struct test_lpm_key key = {}; +__u32 val =0 ; +int map_fd; +const __u32 max_prefixlen =8 * (sizeof (key) -sizeof (key.prefix)); +const __u32 max_entries = max_prefixlen +1 ;
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c line 85
Quoted 10 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +10
-0+unsigned int i, nr =MAX_NR_THREADS , loop =4096 ; +pthread_t tids[MAX_NR_THREADS ]; +struct get_next_key_ctx ctx; +int err; + + map_fd =bpf_map_create (BPF_MAP_TYPE_LPM_TRIE ,"lpm_trie_map" , +sizeof (struct test_lpm_key ),sizeof (__u32), + max_entries, &create_opts); +CHECK (map_fd ==-1 ,"bpf_map_create(), error:%s\n" , +strerror (errno));
CHECK(map_fd == -1, "bpf_map_create()", "error:%s\n", strerror(errno)); It seems you didn't build test it.
Quoted 30 lines
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +30
-0+ +for (i =0 ; i <= max_prefixlen; i++) { + key.prefix = i; + err =bpf_map_update_elem (map_fd, &key, &val,BPF_ANY ); +CHECK (err,"bpf_map_update_elem()" ,"error:%s\n" , +strerror (errno)); + } + + ctx.start = false; + ctx.stop = false; + ctx.map_fd = map_fd; + ctx.loop = loop; +memcpy (&ctx.key, &key,sizeof (key)); + +for (i =0 ; i < nr; i++) { + err =pthread_create (&tids[i],NULL , get_next_key_fn, &ctx); +if (err) { +abort_get_next_key (&ctx, tids, i); +CHECK (err,"pthread_create" ,"error %d\n" , err); + } + } + + ctx.start = true; +for (i =0 ; i < nr; i++) +pthread_join (tids[i],NULL ); + +printf ("%s:PASS\n" , __func__); + +close (map_fd); +}