From: Alexei Starovoitov Tests for the patch that refines the linked registers of a conditional jump. These are the live registers and stack slots that are a tested register + a constant on every path to the jump. The existing tests of linked scalars, spills and loops cover the mechanism: a copy, an added constant, the low 32 bits, a spill and its fill, two calls, a store through a pointer. These tests are for the hazards that only a static analysis has. scev.c computes the links before the main pass, from the insns alone, without types and without states. r8 is an unbounded scalar. Each prog computes a second value from it, tests one of the two and uses the other one as an offset into a map value of 64 bytes. What loads is run. - An add that becomes ALU32: 'r3 += 1' is converted to 'w3 += 1' at fixup if r3 is an arena pointer. r3 == r7 + 1 holds modulo 2^32 only, also after 'r3 = le64 r3; r7 = le64 r7' has turned both into scalars, and also for the phi of two such adds. Rejected. A scalar + two constants in a prog with an arena is linked modulo 2^64: loads. - A store through a dynptr slice may alias the buffer on the stack: a fill before the store and a fill after it are not linked. Rejected. - An edge that the verifier adds: each iteration of the outer loop saves r3, which is r8, and restores it. may_goto that the verifier adds before the header of the nested loop leaves both loops while r3 is r7. Rejected. - A link at a loop header: two induction variables that are linked at loop entry and have the same step are linked there. Negative test: the steps differ. - A pointer is not a scalar: r3 is the address in r1 as a scalar. A bound of r3 does not bound the offset of r1. Rejected. - Big endian: a 32-bit spill goes to the first half-slot. The low 32 bits of a 64-bit fill are that spill on little endian only, also if the slot is a phi. Loads there, rejected on big endian. - An empty intersection: the range that the jump implies and the known bits of the linked register don't overlap. The register is left as it is: loads with BPF_F_TEST_REG_INVARIANTS. - A link modulo 2^8: after 'r2 = (s8)r8; if r8 > 63 goto' both fit in s8, so r2 is refined. Loads. The tests with an arena are in verifier_arena.c, the others in verifier_scev.c. Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/progs/verifier_arena.c | 39 +++++++ .../selftests/bpf/progs/verifier_scev.c | 107 ++++++++++++++++++ 2 files changed, 146 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_arena.c b/tools/testing/selftests/bpf/progs/verifier_arena.c index bebb607000a5..bf50413f6c08 100644 --- a/tools/testing/selftests/bpf/progs/verifier_arena.c +++ b/tools/testing/selftests/bpf/progs/verifier_arena.c @@ -625,6 +625,45 @@ ARENA_TEST(arena_pointer_moves, "r6 += 8;", __success NOT_UNROLLED100) ARENA_TEST(arena_pointer_becomes_a_number, "if r7 != 5 goto +1; r6 = 4096;", __failure NOT_UNROLLED100 __msg("R6 invalid mem access 'scalar'")) +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, __u32); + __type(value, char[64]); +} map64 SEC(".maps"); + +/* + * r6: 64 bytes. r8: an unbounded scalar. r3, r7: an arena pointer and a copy of it. + * The test leaves an address in r1. + */ +#define ARENA_LINKED(name, expect, body) \ +SEC("syscall") expect __load_if_JITed() \ +__naked void name(void) \ +{ \ + asm volatile ( \ + "r1 = %[arena] ll; r1 = 0; *(u32 *)(r10 - 4) = r1; r2 = r10; r2 += -4;" \ + "r1 = %[map64] ll; call %[bpf_map_lookup_elem]; if r0 == 0 goto out_%=; r6 = r0;" \ + "call %[bpf_ktime_get_ns]; r8 = r0; r3 = addr_space_cast(r8, 0, 1); r7 = r3;" \ + body \ + "r0 = *(u8 *)(r1 + 0);" \ + "out_%=: r0 = 0; exit;" \ + : \ + : __imm(bpf_map_lookup_elem), __imm(bpf_ktime_get_ns), \ + __imm_addr(map64), __imm_addr(arena) \ + : __clobber_all); \ +} + +ARENA_LINKED(scalar_plus_two_constants, __success __retval(0), + "r2 = r8; r2 += 1; r2 += 1; if r8 > 61 goto out_%=; r1 = r6; r1 += r2;") +/* 'r3 += 1' is converted to 'w3 += 1': r3 is 0 and not 1 << 32 */ +ARENA_LINKED(arena_ptr_plus_constant, __failure, + "r3 += 1; r3 = le64 r3; r7 = le64 r7; r2 = 0xffffffff ll; if r7 != r2 goto out_%=;" + "r3 >>= 32; r3 -= 1; r1 = r6; r1 += r3;") +/* At the join point r3 is phi((+ x 1)). The insn there, an add to a scalar, does not define it. */ +ARENA_LINKED(arena_ptr_plus_constant_on_two_paths, __failure, + "if r8 == 0 goto 1f; r3 += 1; goto 2f; 1: r3 += 1; 2: r8 += 1; r3 = le64 r3; r7 = le64 r7;" + "r2 = 0xffffffff ll; if r7 != r2 goto out_%=; r3 >>= 32; r3 -= 1; r1 = r6; r1 += r3;") + SEC("syscall") __description("arena: a number is not an address in arena") __failure __msg("R6 invalid mem access 'scalar'") diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c index 70aeeadcd181..1047845c916b 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scev.c +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c @@ -3307,6 +3307,113 @@ NOT_LINEAR_TEST(lsh_grows, "r7 &= 15;", "r7 <<= 1;", UNROLLED("(<< r7 1)")) NOT_LINEAR_TEST(same_constant, "r7 = 17;", "r7 &= 31;", NOT_CHANGED) NOT_LINEAR_TEST(same_wide_constant, "r7 = 0xffffffff00000011 ll;", "r7 &= -239;", NOT_CHANGED) +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, __u32); + __type(value, char[64]); +} map64 SEC(".maps"); + +/* + * A conditional jump refines the registers and stack slots that are linked to what it tests. + * r6: 64 bytes. r7: a scalar below 256. r8: an unbounded scalar. r9: the context. + * The test leaves an address in r1. + */ +#define LINKED_SEC(sec, name, expect, body) \ +SEC(sec) expect \ +__naked void name(void) \ +{ \ + asm volatile ( \ + "r9 = r1; r1 = 0; *(u32 *)(r10 - 4) = r1; r2 = r10; r2 += -4; r1 = %[map64] ll;" \ + "call %[bpf_map_lookup_elem]; if r0 == 0 goto out_%=; r6 = r0;" \ + "call %[bpf_get_prandom_u32]; r7 = r0; r7 &= 255;" \ + "call %[bpf_ktime_get_ns]; r8 = r0;" \ + body \ + "r0 = *(u8 *)(r1 + 0);" \ + "out_%=: r0 = 0; exit;" \ + : \ + : __imm(bpf_map_lookup_elem), __imm(bpf_get_prandom_u32), __imm(bpf_ktime_get_ns), \ + __imm(bpf_dynptr_from_skb), __imm(bpf_dynptr_slice_rdwr), \ + __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), \ + __imm_addr(map64), __imm_addr(ringbuf) \ + : __clobber_all); \ +} +#define LINKED(name, expect, body) LINKED_SEC("socket", name, expect, body) + +#define VALID __success __retval(0) +#define UNBOUND __failure __msg("unbounded min value") + +/* r3 is the address in r1 as a scalar. It does not bound the offset of r1. */ +LINKED(pointer_is_not_scalar, __failure, + "r7 &= 127; r1 = r6; r1 += r7; r3 = r1; r3 = le64 r3; if r3 < 64 goto out_%=; r1 += -64;") + +LINKED(sign_extension_that_fits, VALID, "r2 = (s8)r8; if r8 > 63 goto out_%=; r1 = r6; r1 += r2;") + +/* The low 3 bits of r3 are 5. It is r8 + 5 once r8 fits in s8: no overlap with [-2, 1]. */ +LINKED(empty_intersection, VALID __flag(BPF_F_TEST_REG_INVARIANTS), + "r3 = (s8)r8; if r3 & 7 goto out_%=; r3 += 5; if r3 s> 100 goto out_%=;" + "if r3 s< -100 goto out_%=; if r8 s< -7 goto out_%=; if r8 s> -4 goto out_%=;" + "r3 += 3; r1 = r6;") + +/* The low bytes of the spill to r10 - 16 come first or last */ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ +#define FIRST_BYTES_ARE_LOW VALID +#else +#define FIRST_BYTES_ARE_LOW __failure __msg("R1 unbounded memory access") +#endif + +/* r2 is the low 32 bits of the slot. The 32-bit spill is in its first half-slot. */ +LINKED(spill_32_bits_fill_64_take_low_half, FIRST_BYTES_ARE_LOW, + "*(u64 *)(r10 - 16) = r7; *(u32 *)(r10 - 16) = r8; r2 = *(u64 *)(r10 - 16); w2 = w2;" + "w3 = w8; if r2 > 63 goto out_%=; r1 = r6; r1 += r3;") +/* The slot is a phi: two paths spill distinct values to its first half-slot */ +LINKED(spill_32_bits_on_two_paths_fill_64_take_low_half, FIRST_BYTES_ARE_LOW, + "*(u64 *)(r10 - 16) = r7; *(u32 *)(r10 - 16) = r8; if r7 > 9 goto l_%=;" + "r3 = r8; r3 >>= 1; *(u32 *)(r10 - 16) = r3;" + "l_%=: r2 = *(u64 *)(r10 - 16); w2 = w2; if r2 > 63 goto out_%=;" + "r3 = *(u32 *)(r10 - 16); r1 = r6; r1 += r3;") + +/* r0 is r10 - 24 when the first 8 bytes of the packet are not in one piece */ +LINKED_SEC("tc", slot_written_through_a_slice, UNBOUND, + "r1 = r9; r2 = 0; r3 = r10; r3 += -16; call %[bpf_dynptr_from_skb];" + "r1 = r10; r1 += -16; r2 = 0; r3 = r10; r3 += -24; r4 = 8;" + "call %[bpf_dynptr_slice_rdwr]; if r0 == 0 goto out_%=;" + "r3 = *(u64 *)(r10 - 24); *(u64 *)(r0 + 0) = r8; r2 = *(u64 *)(r10 - 24);" + "if r3 > 63 goto out_%=; r1 = r6; r1 += r2;") + +/* BTF of the kfuncs that only asm calls */ +void __kfunc_btf_root(void) +{ + bpf_dynptr_from_skb(0, 0, 0); + bpf_dynptr_slice_rdwr(0, 0, 0, 0); +} + +/* Linked at the header in every iteration: r2 is r3 + 2 at loop entry, both have the step 1 */ +#define LOOP_HEADER(enter, step) \ + enter "l_%=: if r3 > 61 goto out_%=; r1 = r6; r1 += r2; r0 = *(u8 *)(r1 + 0);" step \ + "if r0 != 0 goto l_%=;" + +LINKED(linked_at_loop_header, VALID, + LOOP_HEADER("r3 = r8; r2 = r8; r2 += 1; r2 += 1;", "r2 += 1; r3 += 1;")) +LINKED(linked_at_loop_entry_only, __failure, + LOOP_HEADER("r3 = r8; r2 = r8; r2 += 1; r2 += 1;", "r2 += 2; r3 += 1;")) + +/* + * No exit of the inner loop dominates its backedges: may_goto is added before its header. The prog + * holds a reference, so may_goto goes to the exit of the outer loop: an edge that the verifier + * adds. Every iteration of the outer loop restores r3. At the header of the inner one it is r7. + */ +LINKED(added_edge, UNBOUND, + "r1 = %[ringbuf] ll; r2 = 8; r3 = 0; call %[bpf_ringbuf_reserve]; if r0 == 0 goto out_%=;" + "*(u64 *)(r10 - 16) = r0; r3 = r8;" + "o_%=: r2 = r3; r3 = r7;" + "i_%=: r1 = *(u8 *)(r6 + 0); if r1 == 1 goto a_%=; if r1 == 2 goto b_%=; goto i_%=;" + "a_%=: goto i_%=;" + "b_%=: r3 = r2; r1 = *(u8 *)(r6 + 1); if r1 == 3 goto o_%=;" + "r4 = r6; if r8 > 63 goto r_%=; r4 += r3;" + "r_%=: *(u64 *)(r10 - 24) = r4; r1 = *(u64 *)(r10 - 16); r2 = 0;" + "call %[bpf_ringbuf_discard]; r1 = *(u64 *)(r10 - 24);") + /* * r7 = ctx->data; * r8 = r7 -- 2.55.0