* [PATCH v2 bpf 2/2] selftests/bpf: Add test for trie_get_next_key()
2024-10-26 5:02 [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key() Byeonguk Jeong
@ 2024-10-26 5:04 ` Byeonguk Jeong
2024-10-29 1:33 ` Hou Tao
2024-10-29 1:32 ` [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key() Hou Tao
2024-10-29 20:50 ` patchwork-bot+netdevbpf
2 siblings, 1 reply; 5+ messages in thread
From: Byeonguk Jeong @ 2024-10-26 5:04 UTC (permalink / raw)
To: Toke Høiland-Jørgensen, Alexei Starovoitov,
Daniel Borkmann, Hou Tao, Yonghong Song
Cc: linux-kernel, bpf
Add 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.
Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
---
v1 -> v2:
- Fixed a build error.
- Removed unnecessary comments about crash-on-failure warning.
- Fix a variable to be initialized before using it.
---
.../bpf/map_tests/lpm_trie_map_get_next_key.c | 109 ++++++++++++++++++
1 file changed, 109 insertions(+)
create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
diff --git a/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
new file mode 100644
index 000000000000..0ba015686492
--- /dev/null
+++ b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
@@ -0,0 +1,109 @@
+// SPDX-License-Identifier: GPL-2.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;
+ 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 = 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;
+ 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 8
+ 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 = 65536;
+ 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);
+}
--
2.43.5
^ permalink raw reply related [flat|nested] 5+ messages in thread* Re: [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key()
2024-10-26 5:02 [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key() Byeonguk Jeong
2024-10-26 5:04 ` [PATCH v2 bpf 2/2] selftests/bpf: Add test for trie_get_next_key() Byeonguk Jeong
@ 2024-10-29 1:32 ` Hou Tao
2024-10-29 20:50 ` patchwork-bot+netdevbpf
2 siblings, 0 replies; 5+ messages in thread
From: Hou Tao @ 2024-10-29 1:32 UTC (permalink / raw)
To: Byeonguk Jeong, Toke Høiland-Jørgensen,
Alexei Starovoitov, Daniel Borkmann, Yonghong Song
Cc: linux-kernel, bpf
On 10/26/2024 1:02 PM, Byeonguk Jeong wrote:
> 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.
>
> Fixes: b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")
> Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
> Reviewed-by: Toke Høiland-Jørgensen <toke@kernel.org>
> Tested-by: Hou Tao <houtao1@huawei.com>
> ---
Acked-by: Hou Tao <houtao1@huawei.com>
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key()
2024-10-26 5:02 [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key() Byeonguk Jeong
2024-10-26 5:04 ` [PATCH v2 bpf 2/2] selftests/bpf: Add test for trie_get_next_key() Byeonguk Jeong
2024-10-29 1:32 ` [PATCH v2 bpf 1/2] bpf: Fix out-of-bounds write in trie_get_next_key() Hou Tao
@ 2024-10-29 20:50 ` patchwork-bot+netdevbpf
2 siblings, 0 replies; 5+ messages in thread
From: patchwork-bot+netdevbpf @ 2024-10-29 20:50 UTC (permalink / raw)
To: Byeonguk Jeong
Cc: toke, ast, daniel, houtao, yonghong.song, linux-kernel, bpf
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Sat, 26 Oct 2024 14:02:43 +0900 you wrote:
> 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.
>
> [...]
Here is the summary with links:
- [v2,bpf,1/2] bpf: Fix out-of-bounds write in trie_get_next_key()
https://git.kernel.org/bpf/bpf/c/13400ac8fb80
- [v2,bpf,2/2] selftests/bpf: Add test for trie_get_next_key()
https://git.kernel.org/bpf/bpf/c/d7f214aeacb9
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 5+ messages in thread