From 1fb315892d8395cec2dae04b0cb5558731aefb37 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Tue, 29 Oct 2024 10:26:41 -0700 Subject: selftests/bpf: Test with a very short loop The test added is a simplified reproducer from syzbot report [1]. If verifier does not insert checkpoint somewhere inside the loop, verification of the program would take a very long time. This would happen because mark_chain_precision() for register r7 would constantly trace jump history of the loop back, processing many iterations for each mark_chain_precision() call. [1] https://lore.kernel.org/bpf/670429f6.050a0220.49194.0517.GAE@google.com/ Signed-off-by: Eduard Zingerman Signed-off-by: Andrii Nakryiko Acked-by: Daniel Borkmann Link: https://lore.kernel.org/bpf/20241029172641.1042523-2-eddyz87@gmail.com --- .../selftests/bpf/progs/verifier_search_pruning.c | 23 ++++++++++++++++++++++ tools/testing/selftests/bpf/veristat.cfg | 1 + 2 files changed, 24 insertions(+) (limited to 'tools') diff --git a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c index 5a14498d352f..f40e57251e94 100644 --- a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c +++ b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c @@ -2,6 +2,7 @@ /* Converted from tools/testing/selftests/bpf/verifier/search_pruning.c */ #include +#include <../../../include/linux/filter.h> #include #include "bpf_misc.h" @@ -336,4 +337,26 @@ l0_%=: r1 = 42; \ : __clobber_all); } +/* Without checkpoint forcibly inserted at the back-edge a loop this + * test would take a very long time to verify. + */ +SEC("kprobe") +__failure __log_level(4) +__msg("BPF program is too large.") +__naked void short_loop1(void) +{ + asm volatile ( + " r7 = *(u16 *)(r1 +0);" + "1: r7 += 0x1ab064b9;" + " .8byte %[jset];" /* same as 'if r7 & 0x702000 goto 1b;' */ + " r7 &= 0x1ee60e;" + " r7 += r1;" + " if r7 s> 0x37d2 goto +0;" + " r0 = 0;" + " exit;" + : + : __imm_insn(jset, BPF_JMP_IMM(BPF_JSET, BPF_REG_7, 0x702000, -2)) + : __clobber_all); +} + char _license[] SEC("license") = "GPL"; diff --git a/tools/testing/selftests/bpf/veristat.cfg b/tools/testing/selftests/bpf/veristat.cfg index 1a385061618d..e661ffdcaadf 100644 --- a/tools/testing/selftests/bpf/veristat.cfg +++ b/tools/testing/selftests/bpf/veristat.cfg @@ -15,3 +15,4 @@ test_usdt* test_verif_scale* test_xdp_noinline* xdp_synproxy* +verifier_search_pruning* -- cgit v1.3.1 From d7f214aeacb984b9d42da0146e789f595eb09068 Mon Sep 17 00:00:00 2001 From: Byeonguk Jeong Date: Sat, 26 Oct 2024 14:04:58 +0900 Subject: selftests/bpf: Add test for trie_get_next_key() 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 Acked-by: Hou Tao Link: https://lore.kernel.org/r/Zxx4ep78tsbeWPVM@localhost.localdomain Signed-off-by: Alexei Starovoitov --- .../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 (limited to 'tools') 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 +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include + +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); +} -- cgit v1.3.1 From d0b98f6a17a5cb336121302bce0c97eb5fe32d16 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Tue, 29 Oct 2024 12:39:11 -0700 Subject: bpf: disallow 40-bytes extra stack for bpf_fastcall patterns Hou Tao reported an issue with bpf_fastcall patterns allowing extra stack space above MAX_BPF_STACK limit. This extra stack allowance is not integrated properly with the following verifier parts: - backtracking logic still assumes that stack can't exceed MAX_BPF_STACK; - bpf_verifier_env->scratched_stack_slots assumes only 64 slots are available. Here is an example of an issue with precision tracking (note stack slot -8 tracked as precise instead of -520): 0: (b7) r1 = 42 ; R1_w=42 1: (b7) r2 = 42 ; R2_w=42 2: (7b) *(u64 *)(r10 -512) = r1 ; R1_w=42 R10=fp0 fp-512_w=42 3: (7b) *(u64 *)(r10 -520) = r2 ; R2_w=42 R10=fp0 fp-520_w=42 4: (85) call bpf_get_smp_processor_id#8 ; R0_w=scalar(...) 5: (79) r2 = *(u64 *)(r10 -520) ; R2_w=42 R10=fp0 fp-520_w=42 6: (79) r1 = *(u64 *)(r10 -512) ; R1_w=42 R10=fp0 fp-512_w=42 7: (bf) r3 = r10 ; R3_w=fp0 R10=fp0 8: (0f) r3 += r2 mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r2 stack= before 7: (bf) r3 = r10 mark_precise: frame0: regs=r2 stack= before 6: (79) r1 = *(u64 *)(r10 -512) mark_precise: frame0: regs=r2 stack= before 5: (79) r2 = *(u64 *)(r10 -520) mark_precise: frame0: regs= stack=-8 before 4: (85) call bpf_get_smp_processor_id#8 mark_precise: frame0: regs= stack=-8 before 3: (7b) *(u64 *)(r10 -520) = r2 mark_precise: frame0: regs=r2 stack= before 2: (7b) *(u64 *)(r10 -512) = r1 mark_precise: frame0: regs=r2 stack= before 1: (b7) r2 = 42 9: R2_w=42 R3_w=fp42 9: (95) exit This patch disables the additional allowance for the moment. Also, two test cases are removed: - bpf_fastcall_max_stack_ok: it fails w/o additional stack allowance; - bpf_fastcall_max_stack_fail: this test is no longer necessary, stack size follows regular rules, pattern invalidation is checked by other test cases. Reported-by: Hou Tao Closes: https://lore.kernel.org/bpf/20241023022752.172005-1-houtao@huaweicloud.com/ Fixes: 5b5f51bff1b6 ("bpf: no_caller_saved_registers attribute for helper calls") Signed-off-by: Eduard Zingerman Acked-by: Andrii Nakryiko Tested-by: Hou Tao Link: https://lore.kernel.org/r/20241029193911.1575719-1-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- kernel/bpf/verifier.c | 14 +----- .../selftests/bpf/progs/verifier_bpf_fastcall.c | 55 ---------------------- 2 files changed, 2 insertions(+), 67 deletions(-) (limited to 'tools') diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 3254c27085b8..bb99bada7e2e 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6804,20 +6804,10 @@ static int check_stack_slot_within_bounds(struct bpf_verifier_env *env, struct bpf_func_state *state, enum bpf_access_type t) { - struct bpf_insn_aux_data *aux = &env->insn_aux_data[env->insn_idx]; - int min_valid_off, max_bpf_stack; - - /* If accessing instruction is a spill/fill from bpf_fastcall pattern, - * add room for all caller saved registers below MAX_BPF_STACK. - * In case if bpf_fastcall rewrite won't happen maximal stack depth - * would be checked by check_max_stack_depth_subprog(). - */ - max_bpf_stack = MAX_BPF_STACK; - if (aux->fastcall_pattern) - max_bpf_stack += CALLER_SAVED_REGS * BPF_REG_SIZE; + int min_valid_off; if (t == BPF_WRITE || env->allow_uninit_stack) - min_valid_off = -max_bpf_stack; + min_valid_off = -MAX_BPF_STACK; else min_valid_off = -state->allocated_stack; diff --git a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c index 9da97d2efcd9..5094c288cfd7 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c +++ b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c @@ -790,61 +790,6 @@ __naked static void cumulative_stack_depth_subprog(void) :: __imm(bpf_get_smp_processor_id) : __clobber_all); } -SEC("raw_tp") -__arch_x86_64 -__log_level(4) -__msg("stack depth 512") -__xlated("0: r1 = 42") -__xlated("1: *(u64 *)(r10 -512) = r1") -__xlated("2: w0 = ") -__xlated("3: r0 = &(void __percpu *)(r0)") -__xlated("4: r0 = *(u32 *)(r0 +0)") -__xlated("5: exit") -__success -__naked int bpf_fastcall_max_stack_ok(void) -{ - asm volatile( - "r1 = 42;" - "*(u64 *)(r10 - %[max_bpf_stack]) = r1;" - "*(u64 *)(r10 - %[max_bpf_stack_8]) = r1;" - "call %[bpf_get_smp_processor_id];" - "r1 = *(u64 *)(r10 - %[max_bpf_stack_8]);" - "exit;" - : - : __imm_const(max_bpf_stack, MAX_BPF_STACK), - __imm_const(max_bpf_stack_8, MAX_BPF_STACK + 8), - __imm(bpf_get_smp_processor_id) - : __clobber_all - ); -} - -SEC("raw_tp") -__arch_x86_64 -__log_level(4) -__msg("stack depth 520") -__failure -__naked int bpf_fastcall_max_stack_fail(void) -{ - asm volatile( - "r1 = 42;" - "*(u64 *)(r10 - %[max_bpf_stack]) = r1;" - "*(u64 *)(r10 - %[max_bpf_stack_8]) = r1;" - "call %[bpf_get_smp_processor_id];" - "r1 = *(u64 *)(r10 - %[max_bpf_stack_8]);" - /* call to prandom blocks bpf_fastcall rewrite */ - "*(u64 *)(r10 - %[max_bpf_stack_8]) = r1;" - "call %[bpf_get_prandom_u32];" - "r1 = *(u64 *)(r10 - %[max_bpf_stack_8]);" - "exit;" - : - : __imm_const(max_bpf_stack, MAX_BPF_STACK), - __imm_const(max_bpf_stack_8, MAX_BPF_STACK + 8), - __imm(bpf_get_smp_processor_id), - __imm(bpf_get_prandom_u32) - : __clobber_all - ); -} - SEC("cgroup/getsockname_unix") __xlated("0: r2 = 1") /* bpf_cast_to_kern_ctx is replaced by a single assignment */ -- cgit v1.3.1 From ebafc1e535db19505aec3b94a4a641fe735a2eac Mon Sep 17 00:00:00 2001 From: Hou Tao Date: Wed, 30 Oct 2024 18:05:16 +0800 Subject: selftests/bpf: Add three test cases for bits_iter Add more test cases for bits iterator: (1) huge word test Verify the multiplication overflow of nr_bits in bits_iter. Without the overflow check, when nr_words is 67108865, nr_bits becomes 64, causing bpf_probe_read_kernel_common() to corrupt the stack. (2) max word test Verify correct handling of maximum nr_words value (511). (3) bad word test Verify early termination of bits iteration when bits iterator initialization fails. Also rename bits_nomem to bits_too_big to better reflect its purpose. Signed-off-by: Hou Tao Link: https://lore.kernel.org/r/20241030100516.3633640-6-houtao@huaweicloud.com Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/progs/verifier_bits_iter.c | 61 ++++++++++++++++++++-- 1 file changed, 58 insertions(+), 3 deletions(-) (limited to 'tools') diff --git a/tools/testing/selftests/bpf/progs/verifier_bits_iter.c b/tools/testing/selftests/bpf/progs/verifier_bits_iter.c index f4da4d508ddb..156cc278e2fc 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bits_iter.c +++ b/tools/testing/selftests/bpf/progs/verifier_bits_iter.c @@ -15,6 +15,8 @@ int bpf_iter_bits_new(struct bpf_iter_bits *it, const u64 *unsafe_ptr__ign, int *bpf_iter_bits_next(struct bpf_iter_bits *it) __ksym __weak; void bpf_iter_bits_destroy(struct bpf_iter_bits *it) __ksym __weak; +u64 bits_array[511] = {}; + SEC("iter.s/cgroup") __description("bits iter without destroy") __failure __msg("Unreleased reference") @@ -110,16 +112,16 @@ int bit_index(void) } SEC("syscall") -__description("bits nomem") +__description("bits too big") __success __retval(0) -int bits_nomem(void) +int bits_too_big(void) { u64 data[4]; int nr = 0; int *bit; __builtin_memset(&data, 0xff, sizeof(data)); - bpf_for_each(bits, bit, &data[0], 513) /* Be greater than 512 */ + bpf_for_each(bits, bit, &data[0], 512) /* Be greater than 511 */ nr++; return nr; } @@ -151,3 +153,56 @@ int zero_words(void) nr++; return nr; } + +SEC("syscall") +__description("huge words") +__success __retval(0) +int huge_words(void) +{ + u64 data[8] = {0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1}; + int nr = 0; + int *bit; + + bpf_for_each(bits, bit, &data[0], 67108865) + nr++; + return nr; +} + +SEC("syscall") +__description("max words") +__success __retval(4) +int max_words(void) +{ + volatile int nr = 0; + int *bit; + + bits_array[0] = (1ULL << 63) | 1U; + bits_array[510] = (1ULL << 33) | (1ULL << 32); + + bpf_for_each(bits, bit, bits_array, 511) { + if (nr == 0 && *bit != 0) + break; + if (nr == 2 && *bit != 32672) + break; + nr++; + } + return nr; +} + +SEC("syscall") +__description("bad words") +__success __retval(0) +int bad_words(void) +{ + void *bad_addr = (void *)(3UL << 30); + int nr = 0; + int *bit; + + bpf_for_each(bits, bit, bad_addr, 1) + nr++; + + bpf_for_each(bits, bit, bad_addr, 4) + nr++; + + return nr; +} -- cgit v1.3.1