// SPDX-License-Identifier: GPL-2.0 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ #include #include #include #include #include "../../../include/linux/filter.h" #include "bpf_misc.h" #include "bpf_kfuncs.h" #define COND_TEST(name, _initial, _step, _bound, msg, body) \ SEC("xdp") \ __success \ __log_level(2) \ __flag(BPF_F_TEST_STATE_FREQ) \ __msg("loop header at {{[0-9]+}}, " msg) \ __naked void name(void) \ { \ asm volatile ( \ "r6 = %[initial] ll;" \ "r7 = %[bound] ll;" \ "r9 = 0;" \ body \ "2: r0 = 0;" \ "exit;" \ : \ : __imm_const(initial, _initial), \ __imm_const(step, _step), \ __imm_const(bound, _bound) \ : __clobber_all); \ } /* Optional assembly runs before the tested condition, preserving its latch. */ #define PRE__COND_TEST(name, op, initial, step, bound, msg, ...) \ COND_TEST(name, initial, step, bound, msg, \ "1: r8 = %[step] ll;" __VA_ARGS__ \ "if r6 " op " r7 goto 2f;" \ "r6 += r8;" \ "goto 1b;") #define POST_COND_TEST(name, op, initial, step, bound, msg, ...) \ COND_TEST(name, initial, step, bound, msg, \ "1: r8 = %[step] ll;" __VA_ARGS__ \ "r6 += r8;" \ "if r6 " op " r7 goto 1b;") /* * Bound fallback verification of otherwise infinite or extremely long loops. * JSET is not a linear condition, SCEV ignores it and the tested condition * alone decides the iteration count. */ #define LIMIT_ITERATIONS "r9 += 1; if r9 & 8 goto 2f;" #define PRE__COND_TEST2(name, op, initial, step, bound, msg) \ PRE__COND_TEST(name, op, initial, step, bound, msg, LIMIT_ITERATIONS) #define POST_COND_TEST32(name, op, initial, step, bound, msg) \ COND_TEST(name, initial, step, bound, msg, \ "1: r8 = %[step] ll;" LIMIT_ITERATIONS \ "w6 += w8;" \ "if w6 " op " w7 goto 1b;") #define ITER_U64_MAX (~0ULL) #define ITER_S64_MAX ((1ULL << 63) - 1) #define ITER_S64_MIN (1ULL << 63) #define ITER_U32_MAX ((1ULL << 32) - 1) struct map_val { char foo[1024]; }; struct { __uint(type, BPF_MAP_TYPE_HASH); __uint(max_entries, 1); __type(key, int); __type(value, struct map_val); } map SEC(".maps"); typeof(map) other_map SEC(".maps"); struct { __uint(type, BPF_MAP_TYPE_ARRAY); __uint(max_entries, 1); __type(key, int); __type(value, __u64); } small_map SEC(".maps"); struct { __uint(type, BPF_MAP_TYPE_RINGBUF); __uint(max_entries, 4096); } ringbuf SEC(".maps"); struct { __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); __uint(max_entries, 1); __type(key, int); __type(value, int); __array(values, struct { __uint(type, BPF_MAP_TYPE_ARRAY); __uint(map_flags, BPF_F_INNER_MAP); __uint(max_entries, 1); __type(key, int); __type(value, struct map_val); }); } outer_map SEC(".maps"); struct bpf_iter__bpf_map_elem { struct bpf_iter_meta *meta; struct bpf_map *map; void *key; void *value; }; SEC("xdp") __success __log_level(2) __msg_next("scev at header 1:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __naked void simple_loop1(void) { asm volatile (" \ r0 = 0; \ loop_%=: \ if r0 == 10 goto exit_%=; \ r0 += 1; \ goto loop_%=; \ exit_%=: \ r0 = 0; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __msg("8: (7b) *(u64 *)(r1 +0) = r0 ; *fp-8 (+ *fp-8 1) -> ?") __naked void indirect_write_invalidates_scev(void) { asm volatile (" \ r0 = 0; \ *(u64 *)(r10 - 8) = r0; \ loop_%=: \ r0 = *(u64 *)(r10 - 8); \ if r0 == 10 goto exit_%=; \ r0 += 1; \ *(u64 *)(r10 - 8) = r0; \ r1 = r10; \ r1 += -8; \ *(u64 *)(r1 + 0) = r0; \ goto loop_%=; \ exit_%=: \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* Even a no-op global callee can be freplaced with one that writes to *p. */ __noinline int global_noop_counter(__u64 *p) { return 0; } SEC("xdp") __success __log_level(2) __msg("8: (85) call pc+{{[0-9]+}} {{.*}}; *fp-8 (+ *fp-8 1) -> ?") __naked void global_call_invalidates_scev(void) { asm volatile ( "r0 = 0;" "*(u64 *)(r10 - 8) = r0;" "r6 = 0;" "1:" "r0 = *(u64 *)(r10 - 8);" "r0 += 1;" "*(u64 *)(r10 - 8) = r0;" "r1 = r10;" "r1 += -8;" "call global_noop_counter;" "r6 += 1;" "if r6 < 3 goto 1b;" "r0 = 0;" "exit;" ::: __clobber_all); } SEC("xdp") __success __log_level(2) __msg_next("scev at header 2:") __msg_next(" *fp-8=(+ *fp-8 1) / (linear *fp-8 1)") __msg_next(" scev at latch 3:") __msg_next(" r0=*fp-8 / (linear *fp-8 1)") __msg_next(" *fp-8=*fp-8 / (linear *fp-8 1)") __naked void simple_loop2(void) { asm volatile (" \ r0 = 0; \ *(u64 *)(r10 - 8) = r0; \ loop_%=: \ r0 = *(u64 *)(r10 - 8); \ if r0 == 10 goto exit_%=; \ r0 = *(u64 *)(r10 - 8); \ r0 += 1; \ *(u64 *)(r10 - 8) = r0; \ goto loop_%=; \ exit_%=: \ r0 = 0; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __msg_next("scev at header 2:") __msg_next(" r1=(+ r1 1) / (linear r1 1)") __naked void meet_agrees(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r1 = 0; \ 1: \ if r1 == 2 goto 3f; \ if r0 == 7 goto 2f; \ r1 += 1; \ goto 1b; \ 2: \ r1 += 1; \ goto 1b; \ 3: \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } SEC("xdp") __failure __log_level(2) __msg_next("scev at header 1:") __msg_next(" r6=(any r6 (+ r6 1)) / ?") __naked void meet_disagrees(void) { asm volatile (" \ r6 = 0; \ 1: \ if r6 == 2 goto 3f; \ call %[bpf_get_prandom_u32]; \ if r0 == 7 goto 1b; \ r6 += 1; \ goto 1b; \ 3: \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* Both entry state values for r1 should be accounted for */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev at header 2:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg_next(" r1=42 / (any r1 42)") __msg_next(" scev at latch 2:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg_next(" r1=42 / (any r1 42)") __msg("loop header at 2, widening r0 to 0..10 step 1") __msg_next("loop header at 2, widening r1 to 7..42 step 1") __naked void entry_state_join(void) { asm volatile (" \ r0 = 0; \ r1 = 7; \ 1: if r0 == 10 goto 2f; /* r1 in [7,42] */ \ r0 += 1; \ r1 = 42; \ goto 1b; \ 2: r0 = r1; \ exit; \ " ::: __clobber_all); } SEC("xdp") __log_level(2) __msg_next("scev at header 1:") __msg_next(" r6=(bswap32 (bswap32 (zext32 (- (- (zext32 (+ (>>...) 1))))))) / ?") __naked void expr_chain(void) { asm volatile (" \ r6 = 0; \ 1: \ if r6 == 2 goto 2f; \ r6 += 1; \ r6 <<= 32; \ r6 >>= 32; \ w6 += 1; \ r6 = -r6; \ w6 = -w6; \ r6 = bswap32 r6; \ r6 = bswap32 r6; \ goto 1b; \ 2: \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } #define ALU_OP(insn) "r1 = r6; " insn "; r0 += r1;" SEC("xdp") __success __log_level(2) __msg("r1 += 2 {{.*}}; r1 r6 -> (+ r6 2)") __msg("r1 += r7 {{.*}}; r1 r6 -> (+ r6 r7)") __msg("w1 += 2 {{.*}}; r1 r6 -> (zext32 (+ r6 2))") __msg("w1 += w7 {{.*}}; r1 r6 -> (zext32 (+ r6 r7))") __msg("r1 -= 2 {{.*}}; r1 r6 -> (- r6 2)") __msg("r1 -= r7 {{.*}}; r1 r6 -> (- r6 r7)") __msg("w1 -= 2 {{.*}}; r1 r6 -> (zext32 (- r6 2))") __msg("w1 -= w7 {{.*}}; r1 r6 -> (zext32 (- r6 r7))") __msg("r1 *= 2 {{.*}}; r1 r6 -> (* r6 2)") __msg("r1 *= r7 {{.*}}; r1 r6 -> (* r6 r7)") __msg("w1 *= 2 {{.*}}; r1 r6 -> (zext32 (* r6 2))") __msg("w1 *= w7 {{.*}}; r1 r6 -> (zext32 (* r6 r7))") __msg("r1 /= 2 {{.*}}; r1 r6 -> (/ r6 2)") __msg("r1 /= r7 {{.*}}; r1 r6 -> (/ r6 r7)") __msg("w1 /= 2 {{.*}}; r1 r6 -> (zext32 (/ r6 2))") __msg("w1 /= w7 {{.*}}; r1 r6 -> (zext32 (/ r6 r7))") __msg("r1 s/= 2 {{.*}}; r1 r6 -> (s/ r6 2)") __msg("r1 s/= r7 {{.*}}; r1 r6 -> (s/ r6 r7)") __msg("w1 s/= 2 {{.*}}; r1 r6 -> (zext32 (s/ r6 2))") __msg("w1 s/= w7 {{.*}}; r1 r6 -> (zext32 (s/ r6 r7))") __msg("r1 %= 2 {{.*}}; r1 r6 -> (% r6 2)") __msg("r1 %= r7 {{.*}}; r1 r6 -> (% r6 r7)") __msg("w1 %= 2 {{.*}}; r1 r6 -> (zext32 (% r6 2))") __msg("w1 %= w7 {{.*}}; r1 r6 -> (zext32 (% r6 r7))") __msg("r1 s%= 2 {{.*}}; r1 r6 -> (s% r6 2)") __msg("r1 s%= r7 {{.*}}; r1 r6 -> (s% r6 r7)") __msg("w1 s%= 2 {{.*}}; r1 r6 -> (zext32 (s% r6 2))") __msg("w1 s%= w7 {{.*}}; r1 r6 -> (zext32 (s% r6 r7))") __msg("r1 |= 2 {{.*}}; r1 r6 -> (| r6 2)") __msg("r1 |= r7 {{.*}}; r1 r6 -> (| r6 r7)") __msg("w1 |= 2 {{.*}}; r1 r6 -> (zext32 (| r6 2))") __msg("w1 |= w7 {{.*}}; r1 r6 -> (zext32 (| r6 r7))") __msg("r1 &= 2 {{.*}}; r1 r6 -> (& r6 2)") __msg("r1 &= r7 {{.*}}; r1 r6 -> (& r6 r7)") __msg("w1 &= 2 {{.*}}; r1 r6 -> (zext32 (& r6 2))") __msg("w1 &= w7 {{.*}}; r1 r6 -> (zext32 (& r6 r7))") __msg("r1 ^= 2 {{.*}}; r1 r6 -> (^ r6 2)") __msg("r1 ^= r7 {{.*}}; r1 r6 -> (^ r6 r7)") __msg("w1 ^= 2 {{.*}}; r1 r6 -> (zext32 (^ r6 2))") __msg("w1 ^= w7 {{.*}}; r1 r6 -> (zext32 (^ r6 r7))") __msg("r1 <<= 2 {{.*}}; r1 r6 -> (<< r6 2)") __msg("r1 <<= r7 {{.*}}; r1 r6 -> (<< r6 r7)") __msg("w1 <<= 2 {{.*}}; r1 r6 -> (zext32 (<< r6 2))") __msg("w1 <<= w7 {{.*}}; r1 r6 -> (zext32 (<< r6 r7))") __msg("r1 >>= 2 {{.*}}; r1 r6 -> (>> r6 2)") __msg("r1 >>= r7 {{.*}}; r1 r6 -> (>> r6 r7)") __msg("w1 >>= 2 {{.*}}; r1 r6 -> (zext32 (>> r6 2))") __msg("w1 >>= w7 {{.*}}; r1 r6 -> (zext32 (>> r6 r7))") __msg("r1 s>>= 2 {{.*}}; r1 r6 -> (s>> r6 2)") __msg("r1 s>>= r7 {{.*}}; r1 r6 -> (s>> r6 r7)") __msg("w1 s>>= 2 {{.*}}; r1 r6 -> (zext32 (s>> r6 2))") __msg("w1 s>>= w7 {{.*}}; r1 r6 -> (zext32 (s>> r6 r7))") __msg("r1 = -r1 {{.*}}; r1 r6 -> (- r6)") __msg("w1 = -w1 {{.*}}; r1 r6 -> (zext32 (- r6))") __msg("r1 = 42 {{.*}}; r1 r6 -> 42") __msg("w1 = 42 {{.*}}; r1 r6 -> (zext32 42)") __msg("r1 = r7 {{.*}}; r1 r6 -> r7") __msg("w1 = w7 {{.*}}; r1 r6 -> (zext32 r7)") __msg("r1 = (s8)r6 {{.*}}; r1 r6 -> (sext8 r6)") __msg("r1 = (s16)r6 {{.*}}; r1 r6 -> (sext16 r6)") __msg("r1 = (s32)r6 {{.*}}; r1 r6 -> (sext32 r6)") __msg("w1 = (s8)w6 {{.*}}; r1 r6 -> (zext32 (sext8 r6))") __msg("w1 = (s16)w6 {{.*}}; r1 r6 -> (zext32 (sext16 r6))") __msg("r1 = bswap16 r1 {{.*}}; r1 r6 -> (bswap16 r6)") __msg("r1 = bswap32 r1 {{.*}}; r1 r6 -> (bswap32 r6)") __msg("r1 = bswap64 r1 {{.*}}; r1 r6 -> (bswap64 r6)") #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ __msg("r1 = le16 r1 {{.*}}; r1 r6 -> (zext16 r6)") __msg("r1 = le32 r1 {{.*}}; r1 r6 -> (zext32 r6)") __msg("r1 += 1 {{.*}}; r1 r6 -> (+ r6 1)") __msg("r1 = be16 r1 {{.*}}; r1 r6 -> (bswap16 r6)") __msg("r1 = be32 r1 {{.*}}; r1 r6 -> (bswap32 r6)") __msg("r1 = be64 r1 {{.*}}; r1 r6 -> (bswap64 r6)") #else __msg("r1 = le16 r1 {{.*}}; r1 r6 -> (bswap16 r6)") __msg("r1 = le32 r1 {{.*}}; r1 r6 -> (bswap32 r6)") __msg("r1 = le64 r1 {{.*}}; r1 r6 -> (bswap64 r6)") __msg("r1 = be16 r1 {{.*}}; r1 r6 -> (zext16 r6)") __msg("r1 = be32 r1 {{.*}}; r1 r6 -> (zext32 r6)") __msg("r1 += 1 {{.*}}; r1 r6 -> (+ r6 1)") #endif __naked void alu_ops_exprs(void) { asm volatile ( "r6 = 7;" "r7 = 2;" "r8 = 0;" "1:" "r0 = 0;" ALU_OP("r1 += 2") ALU_OP("r1 += r7") ALU_OP("w1 += 2") ALU_OP("w1 += w7") ALU_OP("r1 -= 2") ALU_OP("r1 -= r7") ALU_OP("w1 -= 2") ALU_OP("w1 -= w7") ALU_OP("r1 *= 2") ALU_OP("r1 *= r7") ALU_OP("w1 *= 2") ALU_OP("w1 *= w7") ALU_OP("r1 /= 2") ALU_OP("r1 /= r7") ALU_OP("w1 /= 2") ALU_OP("w1 /= w7") ALU_OP("r1 s/= 2") ALU_OP("r1 s/= r7") ALU_OP("w1 s/= 2") ALU_OP("w1 s/= w7") ALU_OP("r1 %%= 2") ALU_OP("r1 %%= r7") ALU_OP("w1 %%= 2") ALU_OP("w1 %%= w7") ALU_OP("r1 s%%= 2") ALU_OP("r1 s%%= r7") ALU_OP("w1 s%%= 2") ALU_OP("w1 s%%= w7") ALU_OP("r1 |= 2") ALU_OP("r1 |= r7") ALU_OP("w1 |= 2") ALU_OP("w1 |= w7") ALU_OP("r1 &= 2") ALU_OP("r1 &= r7") ALU_OP("w1 &= 2") ALU_OP("w1 &= w7") ALU_OP("r1 ^= 2") ALU_OP("r1 ^= r7") ALU_OP("w1 ^= 2") ALU_OP("w1 ^= w7") ALU_OP("r1 <<= 2") ALU_OP("r1 <<= r7") ALU_OP("w1 <<= 2") ALU_OP("w1 <<= w7") ALU_OP("r1 >>= 2") ALU_OP("r1 >>= r7") ALU_OP("w1 >>= 2") ALU_OP("w1 >>= w7") ALU_OP("r1 s>>= 2") ALU_OP("r1 s>>= r7") ALU_OP("w1 s>>= 2") ALU_OP("w1 s>>= w7") ALU_OP("r1 = -r1") ALU_OP("w1 = -w1") ALU_OP("r1 = 42") ALU_OP("w1 = 42") ALU_OP("r1 = r7") ALU_OP("w1 = w7") ALU_OP("r1 = (s8)r6") ALU_OP("r1 = (s16)r6") ALU_OP("r1 = (s32)r6") ALU_OP("w1 = (s8)w6") ALU_OP("w1 = (s16)w6") ALU_OP("r1 = bswap16 r1") ALU_OP("r1 = bswap32 r1") ALU_OP("r1 = bswap64 r1") ALU_OP("r1 = le16 r1") ALU_OP("r1 = le32 r1") /* * Expressions unchanged by transfer() do not appear in the log. * Add r1 += 1 to touch the expression and make it appear in the log. */ ALU_OP("r1 = le64 r1; r1 += 1") ALU_OP("r1 = be16 r1") ALU_OP("r1 = be32 r1") ALU_OP("r1 = be64 r1; r1 += 1") "r8 += 1;" "if r8 < 2 goto 1b;" "r0 = 0;" "exit;" ::: __clobber_all); } #undef ALU_OP /* Reset operands and consume results to keep transfer changes live. */ #define ST_OP(stmt) \ "r0 = 0; r1 = 1; r2 = 2;" \ "*(u64 *)(r10 - 8) = -8;" \ stmt ";" \ "r0 += r1; r0 += r2;" \ "r3 = *(u64 *)(r10 - 8); r0 += r3;" SEC("xdp") __success __log_level(2) __msg("*(u64 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> 1") __msg("*(u32 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill32 1)") __msg("*(u16 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill16 1)") __msg("*(u8 *)(r10 -8) = r1 {{.*}}; *fp-8 -8 -> (spill8 1)") __msg("r1 = *(u64 *)(r10 -8) {{.*}}; r1 1 -> -8") #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ __msg("r1 = *(u32 *)(r10 -8) {{.*}}; r1 1 -> (zext32 -8)") __msg("r1 = *(u16 *)(r10 -8) {{.*}}; r1 1 -> (zext16 -8)") __msg("r1 = *(u8 *)(r10 -8) {{.*}}; r1 1 -> (zext8 -8)") __msg("r1 = *(s32 *)(r10 -8) {{.*}}; r1 1 -> (sext32 -8)") __msg("r1 = *(s16 *)(r10 -8) {{.*}}; r1 1 -> (sext16 -8)") __msg("r1 = *(s8 *)(r10 -8) {{.*}}; r1 1 -> (sext8 -8)") __msg("r1 = load_acquire((u8 *)(r10 -8)) {{.*}}; r1 1 -> (zext8 -8)") __msg("r1 = load_acquire((u16 *)(r10 -8)) {{.*}}; r1 1 -> (zext16 -8)") __msg("r1 = load_acquire((u32 *)(r10 -8)) {{.*}}; r1 1 -> (zext32 -8)") #else __msg("r1 = *(u32 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = *(u16 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = *(u8 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = *(s32 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = *(s16 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = *(s8 *)(r10 -8) {{.*}}; r1 1 -> _") __msg("r1 = load_acquire((u8 *)(r10 -8)) {{.*}}; r1 1 -> _") __msg("r1 = load_acquire((u16 *)(r10 -8)) {{.*}}; r1 1 -> _") __msg("r1 = load_acquire((u32 *)(r10 -8)) {{.*}}; r1 1 -> _") #endif __msg("r2 = load_acquire((u64 *)(r10 -8)) {{.*}}; r2 2 -> -8") __msg("store_release((u8 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill8 1)") __msg("store_release((u16 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill16 1)") __msg("store_release((u32 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> (spill32 1)") __msg("store_release((u64 *)(r10 -8), r1) {{.*}}; *fp-8 -8 -> 1") __msg("lock *(u64 *)(r10 -8) += r1 {{.*}}; *fp-8 -8 -> _") __msg("r1 = atomic64_fetch_add((u64 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _") __msg("r1 = atomic_fetch_add((u32 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _") __msg("r1 = atomic64_xchg((u64 *)(r10 -8), r1) {{.*}}; r1 1 -> _, *fp-8 -8 -> _") __msg("r0 = atomic64_cmpxchg((u64 *)(r10 -8), r0, r2) {{.*}}; r0 0 -> _, *fp-8 -8 -> _") __msg("*(u64 *)(r10 -8) = 42 {{.*}}; *fp-8 -8 -> 42") __msg("*(u8 *)(r10 -7) = r0 {{.*}}; *fp-8 -8 -> _") __naked void store_load_exprs(void) { asm volatile ( "r7 = 0;" "1:" ST_OP("*(u64 *)(r10 - 8) = r1") ST_OP("*(u32 *)(r10 - 8) = r1") ST_OP("*(u16 *)(r10 - 8) = r1") ST_OP("*(u8 *)(r10 - 8) = r1") ST_OP("r1 = *(u64 *)(r10 - 8)") ST_OP("r1 = *(u32 *)(r10 - 8)") ST_OP("r1 = *(u16 *)(r10 - 8)") ST_OP("r1 = *(u8 *)(r10 - 8)") ST_OP("r1 = *(s32 *)(r10 - 8)") ST_OP("r1 = *(s16 *)(r10 - 8)") ST_OP("r1 = *(s8 *)(r10 - 8)") ST_OP(".8byte %[load_acquire8]") ST_OP(".8byte %[load_acquire16]") ST_OP(".8byte %[load_acquire32]") ST_OP(".8byte %[load_acquire64]") ST_OP(".8byte %[store_release8]") ST_OP(".8byte %[store_release16]") ST_OP(".8byte %[store_release32]") ST_OP(".8byte %[store_release64]") ST_OP(".8byte %[atomic_add64]") ST_OP(".8byte %[atomic_fetch_add64]") ST_OP(".8byte %[atomic_fetch_add32]") ST_OP(".8byte %[atomic_xchg64]") ST_OP(".8byte %[atomic_cmpxchg64]") ST_OP("*(u64 *)(r10 - 8) = 42") ST_OP("*(u8 *)(r10 - 7) = r0") "r7 += 1;" "if r7 < 2 goto 1b;" "r0 = 0;" "exit;" : : __imm_insn(atomic_add64, BPF_ATOMIC_OP(BPF_DW, BPF_ADD, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(atomic_xchg64, BPF_ATOMIC_OP(BPF_DW, BPF_XCHG, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(load_acquire8, BPF_ATOMIC_OP(BPF_B, BPF_LOAD_ACQ, BPF_REG_1, BPF_REG_10, -8)), __imm_insn(load_acquire16, BPF_ATOMIC_OP(BPF_H, BPF_LOAD_ACQ, BPF_REG_1, BPF_REG_10, -8)), __imm_insn(load_acquire32, BPF_ATOMIC_OP(BPF_W, BPF_LOAD_ACQ, BPF_REG_1, BPF_REG_10, -8)), __imm_insn(load_acquire64, BPF_ATOMIC_OP(BPF_DW, BPF_LOAD_ACQ, BPF_REG_2, BPF_REG_10, -8)), __imm_insn(store_release8, BPF_ATOMIC_OP(BPF_B, BPF_STORE_REL, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(store_release16, BPF_ATOMIC_OP(BPF_H, BPF_STORE_REL, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(store_release32, BPF_ATOMIC_OP(BPF_W, BPF_STORE_REL, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(store_release64, BPF_ATOMIC_OP(BPF_DW, BPF_STORE_REL, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(atomic_cmpxchg64, BPF_ATOMIC_OP(BPF_DW, BPF_CMPXCHG, BPF_REG_10, BPF_REG_2, -8)), __imm_insn(atomic_fetch_add32, BPF_ATOMIC_OP(BPF_W, BPF_ADD | BPF_FETCH, BPF_REG_10, BPF_REG_1, -8)), __imm_insn(atomic_fetch_add64, BPF_ATOMIC_OP(BPF_DW, BPF_ADD | BPF_FETCH, BPF_REG_10, BPF_REG_1, -8)) : __clobber_all); } #undef ST_OP SEC("xdp") __success __log_level(2) __msg_next("scev at header 1:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" r7=?") __msg_next(" scev at latch 1:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" r7=?") __msg_next("scev at header 4:") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg_next(" scev at latch 4:") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __naked void nested_loop1(void) { asm volatile (" \ r6 = 0; \ 1: \ if r6 == 2 goto 2f; \ r6 += 1; \ r7 = 0; \ 3: \ if r7 == 2 goto 4f; \ r7 += 1; \ goto 3b; \ 4: \ goto 1b; \ 2: \ r0 = r7; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } SEC("xdp") __success __msg("loop at 1") __msg_next(" backedge from 4{{$}}") __msg_next(" exit from 1 to 7") __msg_next("loop at 4, nested in 1") __msg_next(" backedge from 6, latch at 4") __msg_next(" exit from 4 to 1") __msg("scev at header 1:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" r7=?") __msg_next("scev at header 4:") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg_next(" scev at latch 4:") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg("loop header at 1, latch not identified") __msg("loop header at 4, widening r7 to 0..2 step 1") __log_level(2) __naked void nested_loop_hdr_backedge1(void) { asm volatile (" \ r6 = 0; \ 1: \ if r6 == 2 goto 3f; \ r6 += 1; \ r7 = 0; \ 2: \ if r7 == 2 goto 1b; \ r7 += 1; \ goto 2b; \ 3: \ r0 = r7; \ exit; \ " ::: __clobber_all); } /* * Outer loop {2, 3, 4, 5} contains inner loop {3, 4, 5}. * The outer loop's only backedge is 4 -> 2, and its latch is also at 4, * inside the inner loop. Outer loop's latch index is not computed in * such a case, as there is no mechanism to build SCEVs for such latches * at the moment. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop at 2{{$}}") __msg_next(" backedge from 4{{$}}") __msg_next(" exit from 5 to 6") __msg_next("loop at 3, nested in 2") __msg_next(" backedge from 5, latch at 5") __msg_next(" exit from 4 to 2") __msg_next(" exit from 5 to 6") __msg("scev at header 2:") __msg_next(" r6=?") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg_next("scev at header 3:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" scev at latch 5:") __msg_next(" r6=(+ r6 1) / (linear (+ r6 1) 1)") __msg("loop header at 2, latch not identified") __msg("loop header at 3, header_count is [0..2] ") __naked void nested_loop_hdr_backedge2(void) { asm volatile (" \ r6 = 0; \ r7 = 0; \ 1: r7 += 1; \ 2: r6 += 1; \ if r7 == 2 goto 1b; \ if r6 < 2 goto 2b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * Logical nest: for (r6 = 0; r6 < 3; r6++) * for (r7 = 0; r7 < 4; r7++) r8++; * Both backedges target header 3, so the CFG has one loop. r6 advances only * on the outer backedge and r7 resets there; neither has a linear SCEV. * r8 advances on both backedges and retains its linear SCEV. */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop at 3{{$}}") __msg("scev at header 3:") __msg_next(" r6=(any r6 (+ r6 1)) / ?") __msg_next(" r7=(any (+ r7 1) 0) / ?") __msg_next(" r8=(+ r8 1) / (linear r8 1)") __msg("loop header at 3, unsupported loop: multiple backedges") __naked void nested_loops_shared_header(void) { asm volatile (" \ r6 = 0; \ r7 = 0; \ r8 = 0; \ 1: r8 += 1; \ r7 += 1; \ if r7 < 4 goto 1b; \ r7 = 0; \ r6 += 1; \ if r6 < 3 goto 1b; \ r0 = r8; \ exit; \ " ::: __clobber_all); } SEC("socket") __success __log_level(2) __msg("loop header at 1, header_count is 10") __msg("loop header at 5, header_count is 5") __flag(BPF_F_TEST_STATE_FREQ) __naked void nested_loops_outer_latch_true_branch_to_inner(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; /* outer loop */ \ r1 = 0; \ if r0 < 10 goto 2f; /* outer latch true branch jumps into inner loop */ \ goto 3f; \ 2: r1 += 1; /* inner loop */ \ if r1 < 5 goto 2b; \ goto 1b; \ 3: r0 = 0; \ exit; \ " ::: __clobber_all); } /* * Exact boundary hits for every continuation opcode. * * Example: pre_lt * * u64 r6 = 1; * while (r6 < 7) { // r6 ∈ [1,3,5,7] * r6 += 2; // r6 ∈ [3,5,7] * } */ /* name op initial step bound expected message */ PRE__COND_TEST (pre_lt, ">=", 1, 2, 7, "header_count is 4 ") POST_COND_TEST (post_lt, "<", 1, 2, 7, "header_count is 3 ") PRE__COND_TEST (pre_le, ">", 1, 2, 7, "header_count is 5 ") POST_COND_TEST (post_le, "<=", 1, 2, 7, "header_count is 4 ") PRE__COND_TEST (pre_gt, "<=", 9, -2, 3, "header_count is 4 ") POST_COND_TEST (post_gt, ">", 9, -2, 3, "header_count is 3 ") PRE__COND_TEST (pre_ge, "<", 9, -2, 3, "header_count is 5 ") POST_COND_TEST (post_ge, ">=", 9, -2, 3, "header_count is 4 ") PRE__COND_TEST (pre_slt, "s>=", -5, 2, 1, "header_count is 4 ") POST_COND_TEST (post_slt, "s<", -5, 2, 1, "header_count is 3 ") PRE__COND_TEST (pre_sle, "s>", -5, 2, 1, "header_count is 5 ") POST_COND_TEST (post_sle, "s<=", -5, 2, 1, "header_count is 4 ") PRE__COND_TEST (pre_sgt, "s<=", 5, -2, -1, "header_count is 4 ") POST_COND_TEST (post_sgt, "s>", 5, -2, -1, "header_count is 3 ") PRE__COND_TEST (pre_sge, "s<", 5, -2, -1, "header_count is 5 ") POST_COND_TEST (post_sge, "s>=", 5, -2, -1, "header_count is 4 ") PRE__COND_TEST (pre_ne, "==", 1, 2, 7, "header_count is 4 ") POST_COND_TEST (post_ne, "!=", 1, 2, 7, "header_count is 3 ") PRE__COND_TEST (pre_ne_down, "==", 9, -2, 3, "header_count is 4 ") POST_COND_TEST (post_ne_down, "!=", 9, -2, 3, "header_count is 3 ") /* * Bounds between two consecutive counter values. * * Example: pre_lt_round * * u64 r6 = 1; * while (r6 < 8) { // r6 ∈ [1,3,5,7,9] * r6 += 2; // r6 ∈ [3,5,7,9] * } */ PRE__COND_TEST (pre_lt_round, ">=", 1, 2, 8, "header_count is 5 ") PRE__COND_TEST (pre_le_round, ">", 1, 2, 8, "header_count is 5 ") PRE__COND_TEST (pre_gt_round, "<=", 9, -2, 2, "header_count is 5 ") PRE__COND_TEST (pre_ge_round, "<", 9, -2, 2, "header_count is 5 ") PRE__COND_TEST (pre_slt_round, "s>=", -5, 2, 2, "header_count is 5 ") PRE__COND_TEST (pre_sle_round, "s>", -5, 2, 2, "header_count is 5 ") PRE__COND_TEST (pre_sgt_round, "s<=", 5, -2, -2, "header_count is 5 ") PRE__COND_TEST (pre_sge_round, "s<", 5, -2, -2, "header_count is 5 ") /* * Equality on the first non-strict comparison still takes a backedge. * * Example: pre_le_eq * * u64 r6 = 7; * while (r6 <= 7) { // r6 ∈ [7,9] * r6 += 2; // r6 ∈ [9] * } */ PRE__COND_TEST (pre_le_eq, ">", 7, 2, 7, "header_count is 2 ") PRE__COND_TEST (pre_ge_eq, "<", 3, -2, 3, "header_count is 2 ") PRE__COND_TEST (pre_sle_eq, "s>", 1, 2, 1, "header_count is 2 ") PRE__COND_TEST (pre_sge_eq, "s<", -1, -2, -1, "header_count is 2 ") /* * Unsigned order across the sign bit. * * Example: pre_lt_sign * * u64 H = 1ULL << 63, r6 = H - 2; * while (r6 < H + 1) { // r6 ∈ [H-2,H-1,H,H+1] * r6 += 1; // r6 ∈ [H-1,H,H+1] * } */ PRE__COND_TEST (pre_lt_sign, ">=", ITER_S64_MAX - 1, 1, ITER_S64_MIN + 1, "header_count is 4 ") PRE__COND_TEST (pre_gt_sign, "<=", ITER_S64_MIN + 1, -1, ITER_S64_MAX - 1, "header_count is 4 ") /* * The first latch comparison is false. * * Example: pre_lt_false * * u64 r6 = 7; * while (r6 < 7) { // r6 ∈ [7] * r6 += 2; // unreachable * } */ PRE__COND_TEST (pre_lt_false, ">=", 7, 2, 7, "can't compute iterations count") PRE__COND_TEST (pre_le_false, ">", 8, 2, 7, "can't compute iterations count") PRE__COND_TEST (pre_gt_false, "<=", 3, -2, 3, "can't compute iterations count") PRE__COND_TEST (pre_ge_false, "<", 2, -2, 3, "can't compute iterations count") PRE__COND_TEST (pre_slt_false, "s>=", 1, 2, 1, "can't compute iterations count") PRE__COND_TEST (pre_sle_false, "s>", 2, 2, 1, "can't compute iterations count") PRE__COND_TEST (pre_sgt_false, "s<=", -1, -2, -1, "can't compute iterations count") PRE__COND_TEST (pre_sge_false, "s<", -2, -2, -1, "can't compute iterations count") PRE__COND_TEST (pre_ne_false, "==", 7, 2, 7, "can't compute iterations count") /* * The counter moves away from the exit; bound fallback verification. * * Example: pre_lt_dir * * u64 r6 = 5, r9 = 0; * while (++r9 <= 8 && r6 < 7) { // r6 ∈ [5,3,1,U64_MAX] * r6 -= 2; // r6 ∈ [3,1,U64_MAX] * } */ PRE__COND_TEST2(pre_lt_dir, ">=", 5, -2, 7, "can't compute iterations count") PRE__COND_TEST2(pre_le_dir, ">", 5, -2, 7, "can't compute iterations count") PRE__COND_TEST2(pre_gt_dir, "<=", 5, 2, 3, "can't compute iterations count") PRE__COND_TEST2(pre_ge_dir, "<", 5, 2, 3, "can't compute iterations count") PRE__COND_TEST2(pre_slt_dir, "s>=", -1, -2, 1, "can't compute iterations count") PRE__COND_TEST2(pre_sle_dir, "s>", -1, -2, 1, "can't compute iterations count") PRE__COND_TEST2(pre_sgt_dir, "s<=", 1, 2, -1, "can't compute iterations count") PRE__COND_TEST2(pre_sge_dir, "s<", 1, 2, -1, "can't compute iterations count") /* * The predicted exit would wrap the counter. * * Example: pre_lt_wrap * * u64 M = U64_MAX, r6 = M - 1, r9 = 0; * while (++r9 <= 8 && r6 < M) { // r6 ∈ [M-1,0,2,...,14] * r6 += 2; // r6 ∈ [0,2,...,14] * } */ PRE__COND_TEST2(pre_lt_wrap, ">=", ITER_U64_MAX - 1, 2, ITER_U64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_le_wrap, ">", ITER_U64_MAX, 1, ITER_U64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_gt_wrap, "<=", 1, -2, 0, "can't compute iterations count") PRE__COND_TEST2(pre_ge_wrap, "<", 0, -1, 0, "can't compute iterations count") PRE__COND_TEST2(pre_slt_wrap, "s>=", ITER_S64_MAX - 1, 2, ITER_S64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_sle_wrap, "s>", ITER_S64_MAX, 1, ITER_S64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_sgt_wrap, "s<=", ITER_S64_MIN + 1, -2, ITER_S64_MIN, "can't compute iterations count") PRE__COND_TEST2(pre_sge_wrap, "s<", ITER_S64_MIN, -1, ITER_S64_MIN, "can't compute iterations count") /* * The non-strict count itself would overflow u64. * * Example: pre_le_count_ovf * * u64 r6 = 0, r9 = 0; * while (++r9 <= 8 && r6 <= U64_MAX) { // r6 ∈ [0..8] * r6 += 1; // r6 ∈ [1..8] * } */ PRE__COND_TEST2(pre_le_count_ovf, ">", 0, 1, ITER_U64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_ge_count_ovf, "<", ITER_U64_MAX, -1, 0, "can't compute iterations count") PRE__COND_TEST2(pre_sle_count_ovf, "s>", ITER_S64_MIN, 1, ITER_S64_MAX, "can't compute iterations count") PRE__COND_TEST2(pre_sge_count_ovf, "s<", ITER_S64_MAX, -1, ITER_S64_MIN, "can't compute iterations count") /* * JNE divisibility and equality across unsigned wraparound. * * Example: pre_ne_rem * * u64 r6 = 1, r9 = 0; * while (++r9 <= 8 && r6 != 8) { // r6 ∈ [1,3,...,17] * r6 += 2; // r6 ∈ [3,5,...,17] * } */ PRE__COND_TEST2(pre_ne_rem, "==", 1, 2, 8, "can't compute iterations count") PRE__COND_TEST2(pre_ne_rem_down, "==", 9, -2, 2, "can't compute iterations count") PRE__COND_TEST (pre_ne_wrap_up, "==", ITER_U64_MAX - 1, 2, 0, "header_count is 2 ") PRE__COND_TEST (pre_ne_wrap_down, "==", 1, -2, ITER_U64_MAX, "header_count is 2 ") /* * Largest supported header count, sentinel, and u32 overflow. * * Example: pre_lt_max_hdrs * * u64 r6 = 0, r9 = 0; * while (++r9 <= 8 && r6 < U32_MAX - 2) { // r6 ∈ [0..8] * r6 += 1; // r6 ∈ [1..8] * } */ PRE__COND_TEST2(pre_lt_max_hdrs, ">=", 0, 1, ITER_U32_MAX - 2, "header_count is [0..4294967294] ") PRE__COND_TEST2(pre_lt_sentinel, ">=", 0, 1, ITER_U32_MAX - 1, "can't compute iterations count") PRE__COND_TEST2(pre_lt_hdr_ovf, ">=", 0, 1, ITER_U32_MAX, "can't compute iterations count") /* * The extreme signed step values remain valid unsigned magnitudes. * * Example: pre_lt_step_max * * u64 r6 = 0; * while (r6 < S64_MAX) { // r6 ∈ [0,S64_MAX] * r6 += S64_MAX; // r6 ∈ [S64_MAX] * } */ PRE__COND_TEST (pre_lt_step_max, ">=", 0, ITER_S64_MAX, ITER_S64_MAX, "header_count is 2 ") PRE__COND_TEST (pre_gt_step_min, "<=", ITER_S64_MIN, ITER_S64_MIN, 0, "header_count is 2 ") PRE__COND_TEST (pre_ne_step_min, "==", 0, ITER_S64_MIN, ITER_S64_MIN, "header_count is 2 ") /* * A zero step cannot establish a finite iteration count. * * Example: pre_lt_zero_step * * u64 r6 = 1, r9 = 0; * while (++r9 <= 8 && r6 < 7) { // r6 ∈ [1], nine header visits * r6 += 0; // r6 ∈ [1] * } */ PRE__COND_TEST2(pre_lt_zero_step, ">=", 1, 0, 7, "can't compute iterations count") /* * Signed JMP32 comparisons sign-extend the initial value, bound and step. * Encode negative operands as positive u32 constants so the conversion matters. * post32_sgt also checks that an exit exactly at S32_MIN is accepted. */ /* name op initial step bound expected message */ POST_COND_TEST32(post32_slt, "s<", -7u, 2, -1u, "header_count is [0..3] ") POST_COND_TEST32(post32_sle, "s<=", -7u, 2, -1u, "header_count is [0..4] ") POST_COND_TEST32(post32_sgt, "s>", (__u32)INT32_MIN + 6, -2u, (__u32)INT32_MIN, "header_count is [0..3] ") POST_COND_TEST32(post32_sge, "s>=", -1u, -2u, -7u, "header_count is [0..4] ") /* * When computing 32-bit iteration bounds, scev.c:compute_max_iters() does * the computation in the 64-bit domain first. For unsigned JMP32 comparisons, * it zero-extends the initial value and bound, but sign-extends the step. * Hence pick negative 64-bit initial values and bounds, and encode negative * steps as positive u32 constants, so both conversions affect the computation. * post32_lt also checks that an exit exactly at U32_MAX is accepted. */ POST_COND_TEST32(post32_lt, "<", -7, 2, -1, "header_count is [0..3] ") POST_COND_TEST32(post32_le, "<=", -9, 2, -3, "header_count is [0..4] ") POST_COND_TEST32(post32_gt, ">", -1, -2u, -7, "header_count is [0..3] ") POST_COND_TEST32(post32_ge, ">=", -1, -2u, -7, "header_count is [0..4] ") POST_COND_TEST32(post32_ne, "!=", -1, -2u, -7, "header_count is [0..3] ") /* An exit exactly at S32_MAX is accepted as well. */ POST_COND_TEST32(post32_slt_max, "s<", INT32_MAX - 6, 2, INT32_MAX, "header_count is [0..3] ") /* * The first iteration fits in 32 bits, but the predicted exit overshoots the bound * by one and wraps. */ POST_COND_TEST32(post32_slt_wrap, "s<", INT32_MAX - 3, 2, INT32_MAX, "can't compute iterations count") POST_COND_TEST32(post32_sgt_wrap, "s>", (__u32)INT32_MIN + 3, -2u, (__u32)INT32_MIN, "can't compute iterations count") POST_COND_TEST32(post32_lt_wrap, "<", -4, 2, -1, "can't compute iterations count") SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 10 ") __msg("loop header at 1, widening r0 to 0..9 step 1") __msg("processed 5 insns") __naked void post_cond_jlt(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; \ if r0 < 10 goto 1b; \ exit; \ " ::: __clobber_all); } /* * Explore with r7=10 first, r7=4096 next. * Should trigger invalid stack read if r7 is marked precise. * * r0 = 0; * r6 = 0; * r7 = bpf_get_prandom_u32() == 42 ? 10 : 4096; * do { * r0++; * r6++; * r3 = *(fp - r0); * } while (r6 < r7); * return r0; */ SEC("xdp") __failure __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 6, header_count is 10 ") __msg("mark_precise: frame0: parent state regs=r6,r7 stack=:") __msg("loop header at 6, widening r0 to 0..9 step 1") __msg("loop header at 6, header_count is 4096 ") __msg("loop header at 6, widening r0 to 0..4095 step 1") __msg("invalid variable-offset read from stack R2") __naked void mark_bound_precise(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r7 = 4096; \ if r0 != 42 goto 1f; \ r7 = 10; \ 1: r0 = 0; \ r6 = 0; \ 2: r0 += 1; \ r6 += 1; \ r2 = r0; \ r2 = -r2; \ r2 += r10; \ r3 = *(u8 *)(r2 + 0); \ if r6 < r7 goto 2b; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Explore with r6=4086 first, r6=0 next. * Should trigger invalid stack read if r6 is marked precise. * * r0 = 0; * r6 = bpf_get_prandom_u32() == 42 ? 4086 : 0; * do { * r0++; * r6++; * r3 = *(fp - r0); * } while (r6 < 4096); * return r0; */ SEC("xdp") __failure __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 5, header_count is 10 ") __msg("mark_precise: frame0: parent state regs=r6 stack=:") __msg("loop header at 5, widening r0 to 0..9 step 1") __msg("loop header at 5, header_count is 4096 ") __msg("loop header at 5, widening r0 to 0..4095 step 1") __msg("invalid variable-offset read from stack R2") __naked void mark_base_precise(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r6 = 0; \ if r0 != 42 goto 1f; \ r6 = 4086; \ 1: r0 = 0; \ 2: r0 += 1; \ r6 += 1; \ r2 = r0; \ r2 = -r2; \ r2 += r10; \ r3 = *(u8 *)(r2 + 0); \ if r6 < 4096 goto 2b; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Spill size should be taken into account when evaluating bound scev. * * r0 = 256; * *(u8 *)(r10 - 8) = r0; * r0 = 0; * do { * r0++; * r1 = *(u64 *)(r10 - 8); * if (r0 & 0x200) break; // hidden from scev, limit main pass iterations. * } while (r0 < r1); * return r0; */ SEC("xdp") __success __log_level(2) __msg("scev at header 3:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg("loop header at 3, can't compute iterations count") __naked void eval_expr_small_spill_bound(void) { asm volatile (" \ r0 = 256; \ *(u8 *)(r10 - 8) = r0; \ r0 = 0; \ 1: r0 += 1; \ r1 = *(u64 *)(r10 - 8); \ if r0 & 0x200 goto 2f; \ if r0 < r1 goto 1b; \ 2: exit; \ " ::: __clobber_all); } /* Even when the saved value fits, the upper bytes of the slot are unknown. */ SEC("xdp") __success __log_level(2) __msg("scev at header 3:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg("loop header at 3, can't compute iterations count") __naked void eval_expr_small_spill_bound_fits(void) { asm volatile (" \ r0 = 10; \ *(u8 *)(r10 - 8) = r0; \ r0 = 0; \ 1: r0 += 1; \ r1 = *(u64 *)(r10 - 8); \ if r0 & 0x80 goto 2f; \ if r0 < r1 goto 1b; \ 2: exit; \ " ::: __clobber_all); } /* * r0 = 255; * *(u8 *)(r10 - 8) = r0; // narrow spill * do { * r0 = *(u64 *)(r10 - 8); // wide load, widening should bail out here. * r0++; * *(u64 *)(r10 - 8) = r0; * } while (r0 < 265); * return r0; */ SEC("xdp") __success __log_level(2) __msg("scev at header 2:") __msg_next(" *fp-8=(+ *fp-8 1) / (linear *fp-8 1)") __msg("loop header at 2, can't compute iterations count") __not_msg("widening") __naked void no_widen_small_spill_counter(void) { asm volatile (" \ r0 = 255; \ *(u8 *)(r10 - 8) = r0; \ 1: r0 = *(u64 *)(r10 - 8); \ r0 += 1; \ *(u64 *)(r10 - 8) = r0; \ if r0 < 265 goto 1b; \ exit; \ " ::: __clobber_all); } /* Full-width counterpart: the counter can be widened from 5 to 14. */ SEC("xdp") __success __log_level(2) __msg("scev at header 2:") __msg_next(" *fp-8=(+ *fp-8 1) / (linear *fp-8 1)") __msg("loop header at 2, widening *fp-8 to 5..14 step 1") __naked void widen_full_spill_counter(void) { asm volatile (" \ r0 = 5; \ *(u64 *)(r10 - 8) = r0; \ 1: r0 = *(u64 *)(r10 - 8); \ r0 += 1; \ *(u64 *)(r10 - 8) = r0; \ if r0 < 15 goto 1b; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __msg("scev at header 2:") __msg_next(" *fp-8=(+ *fp-8 1) / (linear *fp-8 1)") __msg("loop header at 2, widening *fp-8 to 5..14 step 1") __naked void widen_acquire_release_counter(void) { asm volatile ( "r0 = 5;" "*(u64 *)(r10 - 8) = r0;" "1:" ".8byte %[load_acquire];" "r0 += 1;" ".8byte %[store_release];" "if r0 < 15 goto 1b;" "exit;" : : __imm_insn(load_acquire, BPF_ATOMIC_OP(BPF_DW, BPF_LOAD_ACQ, BPF_REG_0, BPF_REG_10, -8)), __imm_insn(store_release, BPF_ATOMIC_OP(BPF_DW, BPF_STORE_REL, BPF_REG_10, BPF_REG_0, -8)) : __clobber_all); } /* * r6 scev is (any r6 *fp-8). The byte store leaves memory at zero, * but the spill metadata retains 256. Widen r6 to an unknown scalar * instead of [1,256], which would exclude the zero loaded from memory. * * r0 = 0; * *(u64 *)(r10 - 8) = r0; * r0 = 256; * *(u8 *)(r10 - 8) = r0; // narrow spill * r6 = 1; * r7 = 0; * do { * r0 = r6; * r6 = *(u64 *)(r10 - 8); * r7++; * } while (r7 < 2); * return r0; */ SEC("xdp") __success __retval(0) __log_level(2) __msg("scev at header 6:") __msg_next(" r6=*fp-8 / (any r6 *fp-8)") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg("loop header at 6, widening r6 to 0x8000000000000000..0x7fffffffffffffff step 1") __naked void widen_any_small_spill_leaf(void) { asm volatile (" \ r0 = 0; \ *(u64 *)(r10 - 8) = r0; \ r0 = 256; \ *(u8 *)(r10 - 8) = r0; \ r6 = 1; \ r7 = 0; \ 1: r0 = r6; \ r6 = *(u64 *)(r10 - 8); \ r7 += 1; \ if r7 < 2 goto 1b; \ exit; \ " ::: __clobber_all); } /* * Widening (any *fp-8 7) must allocate the slot before writing its state. * The unallocated entry value makes the union an unknown scalar. * * r6 = 0; * do { * if (r6 == 1) * *(u64 *)(r10 - 8) = 7; * r0 = *(u64 *)(r10 - 8); * r6++; * } while (r6 < 3); * return r0; */ SEC("xdp") __success __retval(7) __log_level(2) __msg("scev at header 1:") __msg_next("r6=(+ r6 1) / (linear r6 1)") __msg_next("*fp-8=(any *fp-8 7) / (any *fp-8 7)") __msg("loop header at 1, widening r6 to 0..2 step 1") __msg("2: (7a) *(u64 *)(r10 -8) = 7 ; R10=fp0 fp-8=7 loop_stack=1") __naked void widen_any_unallocated_slot(void) { asm volatile (" \ r6 = 0; \ 1: if r6 != 1 goto 2f; \ *(u64 *)(r10 - 8) = 7; \ 2: r0 = *(u64 *)(r10 - 8); \ r6 += 1; \ if r6 < 3 goto 1b; \ exit; \ " ::: __clobber_all); } /* A spilled zero entry contributes zero to the union. */ SEC("xdp") __success __retval(7) __log_level(2) __msg("loop header at 2, widening *fp-8 to 0..7 step 1") __naked void widen_any_zero_spill(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r6 = 0; \ 1: if r6 != 1 goto 2f; \ *(u64 *)(r10 - 8) = 7; \ 2: r0 = *(u64 *)(r10 - 8); \ r6 += 1; \ if r6 < 3 goto 1b; \ exit; \ " ::: __clobber_all); } /* A byte store inside the slot leaves STACK_MISC and an unknown scalar value. */ SEC("xdp") __success __retval(7) __log_level(2) __msg("scev at header 2:") __msg_next("r6=(+ r6 1) / (linear r6 1)") __msg_next("*fp-8=(any *fp-8 7) / (any *fp-8 7)") __msg("loop header at 2, widening r6 to 0..2 step 1") __msg("3: (79) r1 = *(u64 *)(r10 -8) ; R1=scalar() R10=fp0 fp-8=m???????") __naked void widen_any_misc_slot(void) { asm volatile (" \ *(u8 *)(r10 - 1) = 1; \ r6 = 0; \ 1: if r6 != 1 goto 2f; \ r1 = *(u64 *)(r10 - 8); \ *(u64 *)(r10 - 8) = 7; \ 2: r0 = *(u64 *)(r10 - 8); \ r6 += 1; \ if r6 < 3 goto 1b; \ exit; \ " ::: __clobber_all); } __naked __noinline __used static int probe_read_stack(void) { asm volatile ( "r2 = 8;" "r3 = 0;" "call %[bpf_probe_read_kernel];" "exit;" : : __imm(bpf_probe_read_kernel) : __clobber_all); } /* * r3 = r8 + 4 is linked to r8 when it enters the loop. Widening drops the link. If * it leaves the 4 behind then r4 = r3 + 1 is taken for r3 - 3 when r3 is compared: * r4 <= 7 instead of r4 <= 11, and the read of r9 looks like dead code. */ SEC("socket") __failure __msg("R9 !read_ok") __naked void widened_reg_is_not_linked(void) { asm volatile ( "call %[bpf_get_prandom_u32];" "r8 = r0;" "r8 &= 0xff;" "r3 = r8;" "r3 += 4;" "r1 = 0;" "1:" "r4 = r3;" "r4 += 1;" "if r3 > 10 goto 3f;" "if r4 <= 7 goto 2f;" "r0 = *(u64 *)(r9 + 0);" "2:" "r3 += 1;" "r1 += 1;" "if r1 < 2 goto 1b;" "3:" "r0 = r8;" "exit;" : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* The unknown SCEV of an unbound STACK_MISC slot must not prevent widening. */ SEC("tracepoint") __success __log_level(2) __msg("scev at header 4:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" *fp-8=?") __msg("loop header at 4, widening r6 to 0..9 step 1") __naked void widen_subprog_probe_read(void) { asm volatile ( "r1 = r10;" "r1 += -8;" "call probe_read_stack;" "r6 = 0;" "1:" "r0 = *(u64 *)(r10 - 8);" "r1 = r10;" "r1 += -8;" "call probe_read_stack;" "r6 += 1;" "if r6 < 10 goto 1b;" "r0 = 0;" "exit;" ::: __clobber_all); } /* An induction variable whose range overflows s64 is widened to the full range. */ SEC("socket") __success __log_level(2) __msg("loop header at 4, header_count is 10") __msg("loop header at 4, widening r1 to 0..9 step 1") __msg("loop header at 4, widening r6 to 0x8000000000000000..0x7fffffffffffffff step 1") __flag(BPF_F_TEST_STATE_FREQ) __naked void widen_overflowing_range(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r6 = r0; \ r6 |= 1; /* not an unknown scalar, those need no widening */ \ r1 = 0; \ 1: r6 += 24; \ r1 += 1; \ if r1 < 10 goto 1b; \ r0 = r6; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * The bound slot is unallocated at the first loop header. SCEV must * treat it as an unknown scalar. JSET limits main-pass iterations. * * r0 = 0; * do { * r0++; * r1 = *(u64 *)(r10 - 8); * if (r0 & 0x80) break; * } while (r0 < r1); * return 0; */ SEC("xdp") __success __retval(0) __log_level(2) __msg("scev at header 1:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg("loop header at 1, can't compute iterations count") __not_msg("widening") __naked void eval_expr_unallocated_stack_bound(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; \ r1 = *(u64 *)(r10 - 8); \ if r0 & 0x80 goto 2f; \ if r0 < r1 goto 1b; \ 2: r0 = 0; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 3, header_count is 8") __msg("loop header at 3, widening r0 to 2..9 step 1") __msg("3: R0=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=9,{{.*}})") __msg("processed 6 insns") __naked void post_cond_jlt_with_base(void) { asm volatile (" \ r7 = 10 ll; /* ldimm64 for a twist */ \ r0 = 2; \ 1: r0 += 1; \ if r0 < r7 goto 1b; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 4 ") __naked void latch_base_differs_from_step(void) { asm volatile (" \ r0 = 0; \ 1: r1 = r0; \ r1 += 1; \ if r1 >= 10 goto 2f; \ r0 += 4; \ goto 1b; \ 2: r0 = r1; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 11") __msg("loop header at 1, widening r0 to 0..10 step 1") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=10,{{.*}})") __msg("processed 5 insns") __naked void post_cond_jle(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; \ if r0 <= 10 goto 1b; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 10") __msg("loop header at 1, widening r0 to 0..9 step 1") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=9,{{.*}})") __msg("processed 6 insns") __naked void post_cond_jge(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; \ if r0 >= 10 goto 2f; \ goto 1b; \ 2: exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 11") __msg("loop header at 1, widening r0 to 0..10 step 1") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=10,{{.*}})") __msg("processed 6 insns") __naked void pre_cond_jge(void) { asm volatile (" \ r0 = 0; \ 1: if r0 >= 10 goto 2f; \ r0 += 1; \ goto 1b; \ 2: exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg_next("scev at header 1:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg_next(" scev at latch 2:") __msg_next(" r0=(+ r0 1) / (linear (+ r0 1) 1)") __msg("loop header at 1, widening r0") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})") __msg("1: (07) r0 += 1 ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})") __msg("2: (55) if r0 != 0x3 goto pc-2") __msg("3: (95) exit") __msg("loop header at 1, clamping r0") __msg("from 2 to 1: safe") __msg("processed 5 insns") __naked void post_cond_jne(void) { asm volatile (" \ r0 = 0; \ 1: r0 += 1; \ if r0 != 3 goto 1b; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg_next("scev at header 1:") __msg_next(" r0=(+ r0 -1) / (linear r0 -1)") __msg_next(" scev at latch 2:") __msg_next(" r0=(+ r0 -1) / (linear (+ r0 -1) -1)") __msg("loop header at 1, header_count is 3 ") __msg("loop header at 1, widening r0 to 1..3 step 1") __msg("1: R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,var_off=(0x0; 0x3)) loop_stack=1") __msg("loop header at 1, clamping r0 to 1..3 step 1") __msg("processed 5 insns") __naked void post_cond_jne_neg_step(void) { asm volatile (" \ r0 = 3; \ 1: r0 += -1; \ if r0 != 0 goto 1b; \ exit; \ " ::: __clobber_all); } /* * r1 and r3 are widened independently, so the r3 == 5 path reaches the back * edge with r3 past the last value it takes at the header. */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, header_count is 5 ") __msg("loop header at 2, widening r1 to 0..4 step 1") __msg("loop header at 2, widening r3 to 0..4 step 1") __msg("3: (55) if r3 != 0x5 goto pc+1 {{.*}}; R3=5") __msg("loop header at 2, clamping r3 to 0..4 step 1") __msg("from 6 to 2: safe") __naked void clamp_dependent_overshoot(void) { asm volatile (" \ r1 = 0; \ r3 = 0; \ 1: r3 += 1; \ if r3 != 5 goto 2f; \ r2 = 0; \ 2: r1 += 1; \ if r1 != 5 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* Same with a 32-bit dependent register, SCEV (zext32 (linear r3 1)) */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, header_count is 5 ") __msg("loop header at 2, widening r1 to 0..4 step 1") __msg("loop header at 2, widening r3 to 0..4 step 1") __msg("3: (56) if w3 != 0x5 goto pc+1 {{.*}}; R3=5") __msg("loop header at 2, clamping r3 to 0..4 step 1") __msg("from 6 to 2: safe") __naked void clamp_dependent_overshoot32(void) { asm volatile (" \ r1 = 0; \ w3 = 0; \ 1: w3 += 1; \ if w3 != 5 goto 2f; \ r2 = 0; \ 2: r1 += 1; \ if r1 != 5 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg_next("scev at header 1:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg_next(" scev at latch 1:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg("loop header at 1, widening r0") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=3,{{.*}})") __msg("1: (15) if r0 == 0x3 goto pc+2 ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})") __msg("2: (07) r0 += 1 ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})") __msg("3: (05) goto pc-3") __msg("loop header at 1, clamping r0") __msg("1: safe") __msg("from 1 to 4: R0=3") __msg("4: R0=3") __msg("4: (95) exit") __msg("processed 6 insns") __naked void pre_cond_je1(void) { asm volatile (" \ r0 = 0; \ 1: if r0 == 3 goto 2f; \ r0 += 1; \ goto 1b; \ 2: exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg_next("scev at header 1:") __msg_next(" r0=(zext32 (+ r0 1)) / (zext32 (linear r0 1))") __msg_next(" scev at latch 2:") __msg_next(" r0=(zext32 (+ r0 1)) / (zext32 (linear (+ r0 1) 1))") __msg("loop header at 1, widening r0") __msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})") __msg("1: (04) w0 += 1 ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})") __msg("2: (56) if w0 != 0x3 goto pc-2") __msg("3: (95) exit") __msg("loop header at 1, clamping r0") __msg("from 2 to 1: safe") __msg("processed 5 insns") __naked void post_cond_jne32(void) { asm volatile (" \ w0 = 0; \ 1: w0 += 1; \ if w0 != 3 goto 1b; \ exit; \ " ::: __clobber_all); } /* w0 ∈ {0xffffffff, 2, 5}, w0 % 3 ∈ {0, 2, 2} ⇒ step 3 can't be preserved */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev at header 1:") __msg_next(" r0=(zext32 (+ r0 3)) / (zext32 (linear r0 3))") __msg_next(" scev at latch 2:") __msg_next(" r0=(zext32 (+ r0 3)) / (zext32 (linear (+ r0 3) 3))") __msg("entering loop 1") __msg_next("loop header at 1, header_count is 2") __msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..2) step 1") __msg("1: R0=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=2,{{.*}})") __naked void post_cond_jne32_overflow(void) { asm volatile (" \ w0 = 0xffffffff; \ 1: w0 += 3; \ if w0 != 5 goto 1b; \ exit; \ " ::: __clobber_all); } /* * w0 ∈ {0, 3, ..., 0xffffffff, 2, 5}, w0 % 3 ∈ {0, 0, ..., 0, 2, 2} * ⇒ step 3 can't be preserved. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, header_count is 1431655767") __msg("loop header at 2, widening r0 to 0..0xffffffff step 1") __naked void post_cond_jne32_full_range(void) { asm volatile (" \ w0 = 0; \ w1 = 0; \ 1: w0 += 3; \ w1 += 1; \ if w1 != 1431655767 goto 1b; \ exit; \ " ::: __clobber_all); } /* r0 ∈ {-6, 0xfffffff7, 0xfffffff4}, r0 % 3 ∈ {0, 1, 1} ⇒ step 3 can't be preserved. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 2") __msg("loop header at 1, widening r0 to -6..0xfffffffa (s32 -9..-6) step 1") __naked void post_cond_jne32_base_mismatch(void) { asm volatile (" \ r0 = -6; \ 1: w0 += -3; \ if w0 != -12 goto 1b; \ exit; \ " ::: __clobber_all); } /* * r0 ∈ {0, 0xffffffff, 0xfffffffe}, * ⇒ the 64-bit header bounds are [0, U32_MAX], 32-bit header bounds are [-1, 0]. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 2") __msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..0) step 1") __naked void post_cond_jne32_neg_step(void) { asm volatile (" \ w0 = 0; \ 1: w0 += -1; \ if w0 != -2 goto 1b; \ exit; \ " ::: __clobber_all); } /* * r0 ∈ {S64_MIN + 1, 3, 5}, r0 % 2 ∈ {1, 1, 1} * ⇒ step 2 and base 1 can be preserved. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, header_count is 2") __msg("loop header at 2, widening r0 to 0x8000000000000000..0x7fffffffffffffff (s32 1..3) step 2") __msg("2: R0=scalar({{.*}}step=1+2)") __naked void post_cond_jne32_signed_boundary(void) { asm volatile (" \ r0 = %[initial] ll; \ 1: w0 += 2; \ if w0 != 5 goto 1b; \ exit; \ " : : __imm_const(initial, ITER_S64_MIN + 1) : __clobber_all); } /* The pre-condition also visits the header with the terminating value 3. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 4") __msg("loop header at 1, widening r0 to 0..3 step 1") __msg("loop header at 1, clamping r0") __msg("4: R0=3") __naked void pre_cond_je32(void) { asm volatile (" \ w0 = 0; \ 1: if w0 == 3 goto 2f; \ w0 += 1; \ goto 1b; \ 2: exit; \ " ::: __clobber_all); } /* ALU32 keeps r0 in [0, U32_MAX], so the 64-bit comparison never becomes false. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 4, can't compute iterations count") __naked void post_cond_alu32_jmp64(void) { asm volatile (" \ w0 = 0; \ r1 = 0x100000003 ll; \ r9 = 0; \ 1: " LIMIT_ITERATIONS "w0 += 1; \ if r0 != r1 goto 1b; \ 2: exit; \ " ::: __clobber_all); } /* The signed 32-bit comparison is always true, even when r0 exceeds INT32_MAX. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, can't compute iterations count") __naked void post_cond_alu64_jmp32(void) { asm volatile (" \ r0 = %[initial]; \ r9 = 0; \ 1: " LIMIT_ITERATIONS "r0 += 1; \ if w0 s<= %[bound] goto 1b; \ 2: exit; \ " : : __imm_const(initial, INT32_MAX - 1), __imm_const(bound, INT32_MAX) : __clobber_all); } /* ALU32 values above INT32_MAX remain positive in a signed 64-bit comparison. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 3, header_count is 3") __msg("loop header at 3, widening r0 to 0xfffffffc..0xfffffffe (s32 -4..-2) step 1") __naked void post_cond_alu32_jmp64_bounded(void) { asm volatile (" \ w0 = -4; \ r1 = 0xffffffff ll; \ 1: w0 += 1; \ if r0 s< r1 goto 1b; \ exit; \ " ::: __clobber_all); } /* The negative 64-bit counter and its exit value fit in the signed 32-bit range. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is 3") __msg("loop header at 1, widening r0 to -6..-2 step 2") __naked void post_cond_alu64_jmp32_bounded(void) { asm volatile (" \ r0 = -6; \ 1: r0 += 2; \ if w0 s< 0 goto 1b; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 1, header_count is [0..3] ") __naked void one_backedge_two_exits(void) { asm volatile (" \ r6 = 0; \ 1: call %[bpf_get_prandom_u32]; \ if r0 == 0 goto 2f; \ r6 += 1; \ if r6 != 3 goto 1b; \ 2: r0 = r6; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg_next("scev at header 11:") __msg_next(" r0=(+ r0 1) / (linear r0 1)") __msg_next(" r1=(+ r1 2) / (linear r1 2)") __msg_next(" scev at latch 16:") __msg_next(" r0=(+ r0 1) / (linear (+ r0 1) 1)") __msg_next(" r1=(+ r1 2) / (linear (+ r1 2) 2)") __msg("loop header at 11, widening r0") __msg("loop header at 11, widening r1") __msg("11: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=7,var_off=(0x0; 0x7)) R1=scalar(smin=smin32=0,smax=umax=smax32=umax32=14,var_off=(0x0; 0xe),step=0+2)") /* loop exit */ __msg("16: (a5) if r0 < 0x8 goto pc-6") __msg("exiting loop 11") __msg("17: (95) exit") /* second iteration */ __msg("loop header at 11, clamping r0") __msg("loop header at 11, clamping r1") /* iteration convergence */ __msg("from 16 to 11: safe") __not_msg("{{^}}11:") /* map lookup error path */ __msg("from 7 to 17: safe") __naked void correlated_regs(void) { asm volatile (" \ r1 = 0; \ *(u64*)(r10 - 8) = r1; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r0 = 0; \ r1 = 0; \ 1: r2 = r6; \ r2 += r1; \ *(u8 *)(r2 + 0) = 1; \ r0 += 1; \ r1 += 2; \ if r0 < 8 goto 1b; \ 2: exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* * k = 0 * for (i = 0; i < 4; i++): * for (j = 0; j < 4; j++): * k += 1 * k <<= 1 // make SCEV construction not possible * k >>= 1 * map[k] = 1 // make k precise */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("19: (72) *(u8 *)(r4 +0) = 1 ; R4=map_value(id={{.*}},map=map,ks=4,vs=1024,imm=16)") __not_msg("19: ") __msg("processed 106 insns") __naked void nested_loops_precise_var1(void) { asm volatile (" \ *(u64*)(r10 - 8) = 0; \ r1 = %[map] ll; \ r2 = r10; \ r2 += -8; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 3f; \ r1 = 0; \ r3 = 0; \ /* outer loop */ \ 1: r2 = 0; \ /* inner loop */ \ 2: r2 += 1; \ r3 += 1; \ r3 <<= 1; \ r3 >>= 1; \ if r2 < 4 goto 2b; \ r1 += 1; \ if r1 < 4 goto 1b; \ r4 = r0; \ r4 += r3; \ *(u8 *)(r4 + 0) = 1; \ r0 = 0; \ 3: exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } SEC("xdp") __success __log_level(2) __msg("loop header at 2, header_count is 100 ") __msg("loop header at 4, header_count is [0..100] ") __msg("loop header at 6, header_count is [0..100] ") __msg("processed 20 insns") __flag(BPF_F_TEST_STATE_FREQ) __naked void nested_loop_with_two_exits(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r6 = 0; \ 1: r6 += 1; \ r7 = 0; \ 2: r7 += 1; \ r8 = 0; \ 3: r8 += 1; \ call %[bpf_get_prandom_u32]; \ if r0 == 42 goto +1; \ goto 4f; \ if r8 < 100 goto 3b; \ if r7 < 100 goto 2b; \ 4: if r6 < 100 goto 1b; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } SEC("xdp") __success __log_level(2) __naked void exit_loop_into_loop_header(void) { asm volatile (" \ r1 = 0; \ r2 = 0; \ loop_a_%=: \ r1 += 1; \ if r1 < 10 goto loop_a_%=; \ loop_b_%=: \ r2 += 1; \ if r2 < 10 goto loop_b_%=; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * This exercises verifier.c:loop_stack_{pop,push}() implementation, * at 'goto d' loops 'b' and 'a' have to be popped from stack, * while loops 'c' and 'd' have to be pushed to stack. * * loop a: // header 5 * loop b: // header 6 * if (rand) goto d; // 8 -> 12, side entry into inner loop d * ... * loop c: // header 11 * loop d: // header 12 * ... */ SEC("xdp") __log_level(2) __msg("loop at 5") __msg("loop at 6, nested in 5") __msg("loop at 11, irreducible") __msg("loop at 12, nested in 11") /* entry via if r0 == 5 goto d_%= false branch */ __msg("loop header at 12, header_count is 3 ") __msg("loop header at 12, widening r9 to 0..2 step 1") __msg("12: R8=1 R9=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,var_off=(0x0; 0x3)) loop_stack=11,12") /* entry via if r0 == 5 goto d_%= true branch */ __msg("loop header at 12, header_count is 3 ") __msg("loop header at 12, widening r9 to 0..2 step 1") __msg("from 8 to 12: R8=0 R9=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,var_off=(0x0; 0x3)) R10=fp0 loop_stack=11,12") __naked void enter_nested_loop_from_side(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r6 = 0; \ r7 = 0; \ r8 = 0; \ r9 = 0; \ a_%=: r6 += 1; \ b_%=: r7 += 1; \ call %[bpf_get_prandom_u32]; \ if r0 == 5 goto d_%=; \ if r7 < 3 goto b_%=; \ if r6 < 3 goto a_%=; \ c_%=: r8 += 1; \ d_%=: r9 += 1; \ if r9 < 3 goto d_%=; \ if r8 < 3 goto c_%=; \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Loop A (counter in r6) contains irreducible loop B (header 5), * which contains C (counter in r9). * Entering B at 'body' saves and restores r6, making it appear invariant. * Entering B at 'alternate' skips the save and modifies r6 instead. * Hence A must not infer a SCEV expression for r6. * SCEV expression for r9 in C should still be computed. * * 0: r6 = 0; * do { // A * 1: r6++; * 2: r0 = bpf_get_prandom_u32(); * 3: r7 = 0; * 4: if (r0 > 5) goto alternate; * 5: B: r8 = r6; // B * 6: goto body; * 7: alternate: * r8 = r6; * 8: r8++; * 9: body: * r6 = r8; * 10: r9 = 0; * do { // C * 11: r9++; * 12: } while (r9 < 3); * 13: r7++; * 14: if (r7 < 4) goto B; * 15: } while (r6 < 4); * 16: r0 = 0; * 17: return r0; */ SEC("xdp") __success __log_level(2) __msg("loop at 1{{$}}") __msg("loop at 5, nested in 1, irreducible") __msg("loop at 11, nested in 5") __msg("scev at header 1:") __msg_next(" r6=?") __msg("scev at header 11:") __msg_next(" r9=(+ r9 1) / (linear r9 1)") __msg("loop header at 11, widening r9 to 0..2 step 1") __not_msg("loop header at 1, widening r6") __naked void nested_irreducible_loop(void) { asm volatile (" \ r6 = 0; \ a_%=: r6 += 1; \ call %[bpf_get_prandom_u32]; \ r7 = 0; \ if r0 > 5 goto alternate_%=; \ b_%=: r8 = r6; \ goto body_%=; \ alternate_%=: \ r8 = r6; \ r8 += 1; \ body_%=: \ r6 = r8; \ r9 = 0; \ c_%=: r9 += 1; \ if r9 < 3 goto c_%=; \ r7 += 1; \ if r7 < 4 goto b_%=; \ if r6 < 4 goto a_%=; \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Loop A (counter in r6) contains irreducible loop B. * Loop B has an exit edge from A. This is a corner case * observed during testing: insn_aux_data[l1].need_scev == true, * but SCEV environment is not constructed. * * r6 = 0; * do { // A * r6++; * r0 = bpf_get_prandom_u32(); * r7 = 0; * if (r0 > 5) goto alternate; * do { // B * r7++; * alt: r0 = bpf_get_prandom_u32(); * l1: if (r0 == 42) * goto exit; * r7++; * } while (r7 < 4); * } while (r6 < 4); * r0 = 0; * exit: return r0; */ SEC("xdp") __success __log_level(2) __naked void nested_irreducible_loop2(void) { asm volatile (" \ r6 = 0; \ a_%=: r6 += 1; \ call %[bpf_get_prandom_u32]; \ r7 = 0; \ if r0 > 5 goto alternate_%=; \ b_%=: r7 += 1; \ alternate_%=: \ call %[bpf_get_prandom_u32]; \ if r0 == 42 goto exit_%=; \ r7 += 1; \ if r7 < 4 goto b_%=; \ if r6 < 4 goto a_%=; \ r0 = 0; \ exit_%=:exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Induction variable seeded from a non-constant value. r7 enters the loop as a * range aligned to 2 (prandom & 0x6 -> {0,2,4,6}) and is incremented by a * non-power-of-2 slope of 6. Since the entry value is not a single point, only * the power-of-two alignment shared by the entry value and the slope can be * guaranteed, so the widened step is 2. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 4, widening r7 to 0..18 step 2") __msg("R7=scalar(smin=smin32=0,smax=umax=smax32=umax32=18,var_off=(0x0; 0x1e),step=0+2)") __naked void widen_nonconst_base(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r7 = r0; \ r7 &= 0x6; \ r6 = 0; \ 1: r7 += 6; \ r6 += 1; \ if r6 < 3 goto 1b; \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * After excluding zero from {0,4,8,12}, the interval starts at 1 while the * values remain multiples of 4. Widening over three iterations must preserve * base 0 and include 20. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 5, header_count is 3 ") __msg("5: R7=scalar({{.*}}smax=umax=smax32=umax32=20,{{.*}}step=0+4)") __naked void widen_nonconst_base_refined(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r7 = r0; \ r7 &= 0xc; \ if r7 < 1 goto 2f; \ r8 = 0; \ 1: r7 += 4; \ r8 += 1; \ if r8 < 3 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Two nested loops with (1) exiting directly to (2): * * for (r6 = 0; r6 < 4; r6++) { * r7 = 0; * for (; r7 < 3; r7++) {} // (1) * for (; r7 != 0; r7--) {} // (2) * } */ SEC("xdp") __success __log_level(2) __msg("loop header at 1, widening r6 to 0..3 step 1") __msg("loop header at 2, widening r7 to 0..2 step 1") __msg("exiting loop 2") __msg("entering loop 4") __msg("loop header at 4, widening r7 to 1..3 step 1") __naked void sibling_inner_loops(void) { asm volatile (" \ r6 = 0; \ 1: r7 = 0; \ 2: r7 += 1; \ if r7 < 3 goto 2b; \ 3: r7 += -1; \ if r7 != 0 goto 3b; \ r6 += 1; \ if r6 < 4 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } SEC("socket") __success __log_level(2) __msg("loop header at 0, can't compute iterations count") __naked void uninit_slot_counter(void) { asm volatile (" \ 1: r0 = *(u64 *)(r10 - 8); \ r0 += 1; \ *(u64 *)(r10 - 8) = r0; \ if r0 < 10 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * The assignment happens only on the second iteration: * * r7 = 5; * for (r6 = 0; r6 < 3; r6++) * if (r6 == 1) * r7 = 10; * if (r7 != 10) * invalid_stack_read(); * * R7 is always 10 at the real exit. Widening loses the correlation between * R6 and R7, leaving R7 in [5, 10] both at the loop header and after the loop. * The verifier therefore rejects the possible invalid stack read. */ SEC("xdp") __failure __log_level(2) __msg("2: {{.*}}R7=scalar(smin=umin=smin32=umin32=5,smax=umax=smax32=umax32=10,var_off=(0x0; 0xf))") __msg("7: R7=scalar(smin=umin=smin32=umin32=5,smax=umax=smax32=umax32=10,var_off=(0x0; 0xf))") __msg("invalid read from stack R10 off=0 size=8") __naked void conditional_assignment_on_second_iteration(void) { asm volatile (" \ r7 = 5; \ r6 = 0; \ 1: if r6 >= 3 goto 3f; \ if r6 != 1 goto 2f; \ r7 = 10; \ 2: r6 += 1; \ goto 1b; \ 3: if r7 == 10 goto 4f; \ r0 = *(u64 *)(r10 + 0); \ 4: r0 = 0; \ exit; \ " ::: __clobber_all); } /* * The latch bound has header SCEV (any r7 100), so it is not invariant: * * u64 i = 0, n = 3; * for (;;) { * ++i; * if (i >= n) * break; * if (i == 1) * n = 100; * } * * The ANY expression must also appear at the latch, rather than a bare r7 * that would incorrectly be treated as a loop-invariant bound. */ SEC("xdp") __success __log_level(2) __msg("scev at header 2:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" r7=(any r7 100) / (any r7 100)") __msg_next(" scev at latch 3:") __msg_next(" r6=(+ r6 1) / (linear (+ r6 1) 1)") __msg_next(" r7=r7 / (any r7 100)") __naked void no_widen_changing_latch_bound(void) { asm volatile (" \ r6 = 0; \ r7 = 3; \ loop_%=: \ r6 += 1; \ if r6 >= r7 goto exit_%=; \ if r6 != 1 goto next_%=; \ r7 = 100; \ next_%=: \ goto loop_%=; \ exit_%=: \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * Join two stack pointer offsets via (any r7 r8), with r8 loop-invariant. * The joined range [-16, -8] still points to initialized stack memory, * so dereferencing r7 after the loop is safe. */ SEC("xdp") __success __retval(0) __log_level(2) __msg("loop header at 7, widening r7 to -16..-8 step 1") __msg("7: {{.*}}R7=fp(smin=smin32=-16,smax=smax32=-8,") __msg("12: R7=fp(smin=smin32=-16,smax=smax32=-8,") __naked void conditional_stack_pointer_assignment(void) { asm volatile (" \ *(u64 *)(r10 - 16) = 0; \ *(u64 *)(r10 - 8) = 0; \ r7 = r10; \ r7 += -16; \ r8 = r10; \ r8 += -8; \ r6 = 0; \ 1: if r6 >= 3 goto 3f; \ if r6 != 1 goto 2f; \ r7 = r8; \ 2: r6 += 1; \ goto 1b; \ 3: r0 = *(u64 *)(r7 + 0); \ exit; \ " ::: __clobber_all); } /* * Both choices are valid, but combining their offsets while retaining * small_map's metadata would invent small_map + 32, outside its value. * * r6 = lookup(small_map, 0); * r7 = lookup(map, 0) + 32; * for (r8 = 0; r8 < 3; r8++) { * if (r8 == 1) * r6 = r7; * r0 = *(u32 *)(r6 + 0); * } */ SEC("xdp") __success __retval(0) __log_level(2) __msg("loop header at {{[0-9]+}}, can't widen r6, expr is") __not_msg("widening") __naked void no_widen_any_map_origin(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[small_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 3f; \ r6 = r0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 3f; \ r7 = r0; \ r7 += 32; \ r8 = 0; \ 1: if r8 != 1 goto 2f; \ r6 = r7; \ 2: r0 = *(u32 *)(r6 + 0); \ r8 += 1; \ if r8 < 3 goto 1b; \ 3: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(small_map), __imm_addr(map) : __clobber_all); } __naked __noinline __used static int any_stack_origin_callee(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r6 = r1; \ r7 = r10; \ r7 += -8; \ r8 = 0; \ 1: if r8 != 1 goto 2f; \ r6 = r7; \ 2: r8 += 1; \ if r8 < 3 goto 1b; \ r0 = *(u64 *)(r6 + 0); \ exit; \ " ::: __clobber_all); } /* * The callee chooses between caller fp-16 and its own fp-8: * * r6 = r1; * r7 = fp - 8; * for (r8 = 0; r8 < 3; r8++) * if (r8 == 1) * r6 = r7; * return *(u64 *)r6; * * Both locations hold zero. Their offsets belong to different frames * and cannot be combined into one stack pointer. */ SEC("xdp") __success __retval(0) __log_level(2) __msg("loop header at {{[0-9]+}}, can't widen r6, expr is") __not_msg("widening") __naked void no_widen_any_stack_origin(void) { asm volatile (" \ *(u64 *)(r10 - 16) = 0; \ r1 = r10; \ r1 += -16; \ call any_stack_origin_callee; \ exit; \ " ::: __clobber_all); } __naked __noinline __used static int scrub_slot_callee(void) { asm volatile (" \ *(u32 *)(r1 + 4) = 1; \ call %[bpf_get_prandom_u32]; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * The callee turns the caller's fp-8 into misc, so the states at the call site * differ between the first and the second iteration, while the states inside * the callee are identical. Verification fails with an infinite loop error if * states.c:current_loop() does not search upper frames for active loops. */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 3, widening r6 to 0..9 step 1") __msg("loop header at 3, clamping r6 to 0..9 step 1") __msg("12: safe") __naked void clamp_callee_state_pruning(void) { asm volatile (" \ w1 = 1; \ *(u32 *)(r10 - 8) = r1; \ r6 = 0; \ 1: r1 = r10; \ r1 += -8; \ call scrub_slot_callee; \ r6 += 1; \ if r6 < 10 goto 1b; \ r0 = *(u32 *)(r10 - 8); \ exit; \ " ::: __clobber_all); } /* * The inner loop turns fp-8 from a spill into misc. On the next outer * iteration, the states inside the inner loop match its first invocation. */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 3, widening r6 to 0..9 step 1") __msg("loop header at 4, widening r7 to 0..2 step 1") __msg("loop header at 3, clamping r6 to 0..9 step 1") __naked void clamp_nested_loop_state_pruning(void) { asm volatile (" \ w1 = 1; \ *(u32 *)(r10 - 8) = r1; \ r6 = 0; \ 1: r7 = 0; \ 2: *(u32 *)(r10 - 4) = 1; \ r7 += 1; \ if r7 < 3 goto 2b; \ r6 += 1; \ if r6 < 10 goto 1b; \ r0 = *(u32 *)(r10 - 8); \ exit; \ " ::: __clobber_all); } /* * Same as above, but the inner loop is not recognized by SCEV and is unrolled * with a precise r7. The states at its header still match between the outer * iterations and must not be reported as an infinite loop: the path between * them crosses the back edge of the terminating outer loop. */ SEC("socket") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 3, widening r6 to 0..9 step 1") __msg("loop header at 5, can't compute iterations count") __msg("loop header at 3, clamping r6 to 0..9 step 1") __naked void clamp_nested_unrolled_loop_state_pruning(void) { asm volatile (" \ w1 = 1; \ *(u32 *)(r10 - 8) = r1; \ r6 = 0; \ 1: *(u32 *)(r10 - 4) = 1; \ r7 = 1; \ 2: r7 *= 2; \ if r7 < 4 goto 2b; \ r6 += 1; \ if r6 < 10 goto 1b; \ r0 = *(u32 *)(r10 - 8); \ exit; \ " ::: __clobber_all); } /* * r7 starts as 1 + 6*k and invariant r8 as 1 + 9*k (0 <= k <= 3). * The (any r7 r8) union must preserve base 1 and step gcd(6, 9) = 3. */ SEC("xdp") __success __retval(1) __log_level(2) __msg("r7 += 1 {{.*}}step=1+6)") __msg("r8 += 1 {{.*}}step=1+9)") __msg("loop header at 9, widening r7 to 1..28 step 3") __msg("9: {{.*}}R7=scalar({{.*}},step=1+3)") __msg("14: R7=scalar({{.*}},step=1+3)") __naked void conditional_scalar_assignment_gcd(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r0 &= 3; \ r7 = r0; \ r7 *= 6; \ r7 += 1; \ r8 = r0; \ r8 *= 9; \ r8 += 1; \ r6 = 0; \ 1: if r6 >= 3 goto 3f; \ if r6 != 1 goto 2f; \ r7 = r8; \ 2: r6 += 1; \ goto 1b; \ 3: r0 = r7; \ r0 %%= 3; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * r7 = ctx->data; * r8 = r7 * for (r6 = 0; r6 < 10 && random() != 42; r7++, r6++); * if (r7 >= ctx->data_end) * return; * *(r8 + 4); // At this point the loop executed unknown number of times. * // Hence, r7 range gives no information about r8. */ SEC("tc") __failure __msg("R8 min value is outside of the allowed memory range") __naked void break_pkt_pointers_id(void) { asm volatile (" \ r7 = *(u32*)(r1 + %[__sk_buff_data]); \ r8 = r7; \ r9 = *(u32*)(r1 + %[__sk_buff_data_end]); \ r6 = 0; \ 1: call %[bpf_get_prandom_u32]; \ if r0 == 42 goto 3f; \ r6 += 1; \ r7 += 1; \ if r6 < 10 goto 1b; \ 3: if r7 >= r9 goto 2f; \ r0 = *(u8*)(r8 + 4); \ 2: r0 = 0; \ exit; \ " : : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end)), __imm(bpf_get_prandom_u32) : __clobber_all); } /* * A loop induction variable used to compute the base address of a store to the * stack must not be widened: the spill offset would become varying, which the * verifier does not track. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking") __naked void no_widen_stack_spill(void) { asm volatile (" \ r0 = 0; \ r2 = 0; \ 1: r3 = r10; \ r3 += -64; \ r3 += r2; \ *(u64 *)(r3 + 0) = r0; \ r0 += 1; \ r2 += 8; \ if r0 < 4 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * Same hazard across a loop nest: the outer induction variable r2 addresses a * stack store performed inside the inner loop. The dependency is pulled up from * the inner loop, so the outer loop must not widen r2. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 2, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking") __msg("loop header at 3, widening r1 to 0..1 step 1") __naked void no_widen_stack_spill_nested(void) { asm volatile (" \ r0 = 0; \ r2 = 0; \ 1: r1 = 0; \ 2: r3 = r10; \ r3 += -64; \ r3 += r2; \ *(u64 *)(r3 + 0) = r1; \ r1 += 1; \ if r1 < 2 goto 2b; \ r0 += 1; \ r2 += 8; \ if r0 < 4 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * The inner loop restores r6 on its backedge but exits with r6 = -1000 on break. * Outer loop must account for the exit value instead of deriving r6 = r6_entry + n. * On the first outer backedge r6 is -999, so the next map access is invalid. * * u8 *r7 = map_value; * s64 r6 = 0; * do { * 1: r9 = 0; * r0 = r7[r6]; * while (true) { * 2: r8 = r6; * r6 = -1000; * if (++r9 > 5) * break; * r6 = r8; * 3: } * r6++; * } while (r6 < 3); */ SEC("xdp") __failure __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev at header 9:") __msg_next(" r6=(+ ? 1) / ?") __msg_next(" scev at latch 20:") __msg_next(" r6=(+ ? 1) / (+ ? 1)") __msg_next("scev at header 13:") __msg_next(" r9=(+ r9 1) / (linear r9 1)") __msg_next(" scev at latch 16:") __msg_next(" r6=-1000 / -1000") __msg_next(" r8=r6 / r6") __msg_next(" r9=(+ r9 1) / (linear (+ r9 1) 1)") __msg("R6=-999") __msg("R1 min value is negative") __naked void nested_loop_exit_clobbers_reg(void) { asm volatile ( "*(u64 *)(r10 - 8) = 0;" "r2 = r10;" "r2 += -8;" "r1 = %[map] ll;" "call %[bpf_map_lookup_elem];" "if r0 == 0 goto 4f;" "r7 = r0;" "r6 = 0;" "1:" "r9 = 0;" "r1 = r7;" "r1 += r6;" "r0 = *(u8 *)(r1 + 0);" "2:" "r8 = r6;" "r6 = -1000;" "r9 += 1;" "if r9 > 5 goto 3f;" "r6 = r8;" "goto 2b;" "3:" "r6 += 1;" "if r6 s< 3 goto 1b;" "4:" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* * The inner loop exits both nested loops with r6 unchanged, or exits only itself with r6 = -1000. * The middle loop repairs the latter exit with a stack fill. It therefore preserves r6, * so the outermost loop must retain r6_entry + n. * * r6 = 0; * do { * r7 = 0; * do { * spill = r6; * r9 = 0; * do { * r8 = r6; * if (random() & 1) * goto next; * r6 = -1000; * if (++r9 >= 2) * break; * r6 = r8; * } while (true); * r6 = spill; * } while (++r7 < 2); * next: * r6++; * } while (r6 < 3); */ SEC("xdp") __success __retval(3) __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("r6 = *(u64 *)(r10 -8) {{.*}}; r6 ? -> r6") __msg("scev at header 1:") __msg_next(" r6=(+ r6 1) / (linear r6 1)") __msg_next(" scev at latch 16:") __msg_next(" r6=(+ r6 1) / (linear (+ r6 1) 1)") __msg("scev at header 2:") __msg_next(" r7=(+ r7 1) / (linear r7 1)") __msg("scev at header 4:") __msg_next(" r9=(+ r9 1) / (linear r9 1)") __msg(" scev at latch 9:") __msg_next(" r8=r6 / r6") __msg_next(" r9=(+ r9 1) / (linear (+ r9 1) 1)") __naked void nested_loop_exit_preserves_reg(void) { asm volatile ( "r6 = 0;" "1:" "r7 = 0;" "2:" "*(u64 *)(r10 - 8) = r6;" "r9 = 0;" "3:" "r8 = r6;" "call %[bpf_get_prandom_u32];" "if r0 & 1 goto 5f;" "r6 = -1000;" "r9 += 1;" "if r9 >= 2 goto 4f;" "r6 = r8;" "goto 3b;" "4:" "r6 = *(u64 *)(r10 - 8);" "r7 += 1;" "if r7 < 2 goto 2b;" "5:" "r6 += 1;" "if r6 < 3 goto 1b;" "r0 = r6;" "exit;" : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Complement of no_widen_stack_spill: a sub-register (1-byte) store to the stack * lands as STACK_MISC and carries no tracked value, so the induction variable * addressing it (r2) is still widened. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("widening r2 to 0..24 step 8") __naked void widen_byte_stack_store(void) { asm volatile (" \ r0 = 0; \ r2 = 0; \ 1: r3 = r10; \ r3 += -64; \ r3 += r2; \ *(u8 *)(r3 + 0) = r0; \ r0 += 1; \ r2 += 8; \ if r0 < 4 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * A fill (BPF_LDX) at a varying stack offset loses precision just like a spill, * so the induction variable computing the load base (r2) must not be widened. * The slots are initialized up front so the fill itself is a valid read. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 6, can't widen r2, expr is (+ r2 8), requires exact stack-offset tracking") __naked void no_widen_stack_fill(void) { asm volatile (" \ r0 = 0; \ *(u64 *)(r10 - 64) = r0; \ *(u64 *)(r10 - 56) = r0; \ *(u64 *)(r10 - 48) = r0; \ *(u64 *)(r10 - 40) = r0; \ r2 = 0; \ 1: r3 = r10; \ r3 += -64; \ r3 += r2; \ r4 = *(u64 *)(r3 + 0); \ r0 += 1; \ r2 += 8; \ if r0 < 4 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * struct xdp_md *slots[2] = { ctx, ctx }; * * r7 = 0; * for (r8 = 0; r8 < 2; r8++) { * value = slots[r7]->data; * if (i == 0) * r7 = 1; * } * * SCEV expression for r7 is (any r7 8) and r7 is used to * address the stack memory. Avoid widening it, otherwise * verifier won't know the type of the slots[r7] expression. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev at header 4:") __msg_next("r7=(any r7 8) / (any r7 8)") __msg("loop header at 4, can't widen r7, expr is {{.*}}, requires exact stack-offset tracking") __naked void no_widen_stack_fill_any(void) { asm volatile (" \ *(u64 *)(r10 - 16) = r1; \ *(u64 *)(r10 - 8) = r1; \ r7 = 0; \ r8 = 0; \ 1: r2 = r10; \ r2 += -16; \ r2 += r7; \ r3 = *(u64 *)(r2 + 0); /* slots[r7] */ \ r0 = *(u32 *)(r3 + 0); /* slots[r7]->data */ \ if r8 != 0 goto 2f; \ r7 = 8; /* conditionally update r7 */ \ 2: r8 += 1; \ if r8 < 2 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* * A dynptr/iter/irq/res_spin_lock call initializes a stack object through a * pointer argument, which acts like a spill base: the induction variable * computing that argument's varying stack offset must not be widened, otherwise * the slot can't be resolved. Here each iteration constructs an xdp dynptr at * &dptrs[i]. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("can't widen {{.*}}, requires exact stack-offset tracking") #ifndef __clang__ /* The issue is unrelated to SCEV */ __skip("GCC emits a stack-pointer loop condition the verifier cannot resolve") #endif int no_widen_dynptr_kfunc_arg(struct xdp_md *ctx) { struct bpf_dynptr dptrs[4]; int i; #ifdef __clang__ #pragma clang loop unroll(disable) #else #pragma GCC unroll 0 #endif for (i = 0; i < 4; i++) bpf_dynptr_from_xdp(ctx, 0, &dptrs[i]); return 0; } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("header_count is 4 ") __msg("widening r6 to -16..-13 step 1") __naked void ptr_stack(void) { asm volatile (" \ r6 = r10; \ r6 += -16; \ r7 = r6; \ r7 += 4; \ 1: r6 += 1; \ if r6 < r7 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } __naked __noinline __used static int ptr_stack_callee(void) { asm volatile (" \ r6 = r10; \ r6 += -16; \ r7 = r1; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 4f; /* bound main pass iteration, but hide it from SCEV */ \ if r6 < r7 goto 1b; /* r6 and r7 are from different frames, can't be widened */ \ 4: r0 = 0; \ exit; \ " ::: __clobber_all); } /* The end pointer belongs to the caller's frame. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (fp), r7 (fp)") __not_msg("widening r6") __naked void ptr_stack_other_frame(void) { asm volatile (" \ r1 = r10; \ r1 += -12; \ call ptr_stack_callee; \ exit; \ " ::: __clobber_all); } SEC("xdp") __success __log_level(2) __msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") __msg("loop header at 11, can't compute iterations count at 14") __naked void ptr_map_value_jmp32(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r7 = r6; \ r7 += 4; \ r9 = 0; \ 1:" LIMIT_ITERATIONS \ " r6 += 1; \ if w6 < w7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } SEC("xdp") __failure __log_level(2) __msg("loop header at 11, can't compute iterations count") __msg("R6 32-bit pointer arithmetic prohibited") __naked void ptr_map_value_alu32_latch(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r7 = r6; \ r7 += 4; \ r9 = 0; \ 1:" LIMIT_ITERATIONS \ " w6 += 1; \ if r6 < r7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } SEC("xdp") __success __log_level(2) __msg("loop header at 11, can't compute iterations count") __naked void ptr_map_value_alu32_latch2(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r7 = r6; \ r7 += 4; \ r9 = 0; \ 1:" LIMIT_ITERATIONS \ " r6 += 1; \ w8 = w6; \ if r8 < r7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } SEC("xdp") __success __log_level(2) __msg("loop header at 8, can't widen r0, expr is (zext32 (+ r0 1))") __naked void ptr_map_value_alu32_non_latch(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r1 = 0; \ 1: r1 += 1; \ w0 = w0; \ w0 += 1; \ if r1 < 4 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* Metadata and packet data have different origins. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (pkt_meta), r7 (pkt)") __not_msg("widening r6") __naked void ptr_packet_meta_other_origin(void) { asm volatile (" \ r6 = *(u32 *)(r1 + %[data_meta]); \ r7 = *(u32 *)(r1 + %[data]); \ r7 += 4; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 4f; \ if r6 < r7 goto 1b; \ 4: r0 = 0; \ exit; \ " : : __imm_const(data, offsetof(struct xdp_md, data)), __imm_const(data_meta, offsetof(struct xdp_md, data_meta)) : __clobber_all); } /* Two lookups in a 1-element array count as the same memory origin. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("header_count is 4 ") __msg("widening r6 to 0..3 step 1") __naked void ptr_map_value_two_lookups(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[small_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r2 = r10; \ r2 += -8; \ r1 = %[small_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r7 = r0; \ r7 += 4; \ 1: r6 += 1; \ if r6 < r7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(small_map) : __clobber_all); } /* * For inner array maps with BPF_F_INNER_MAP flag the actual array size * might differ from metadata in map declaration. Hence, r6 and r7 below * cannot be directly compared / iterations count can't be inferred. * * r8 = bpf_map_lookup_elem(outer_map, ...); // inner map * r6 = bpf_map_lookup_elem(r8, ...); * r7 = bpf_map_lookup_elem(r8, ...); * r7 += 4; * do { r6++; ... } while (r6 < r7); */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") __not_msg("widening r6") __naked void ptr_map_value_two_lookups_inner_map(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[outer_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r8 = r0; \ r2 = r10; \ r2 += -8; \ r1 = r8; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r1 = r8; \ r2 = r10; \ r2 += -8; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r7 = r0; \ r7 += 4; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 2f; /* main pass iteration guard */ \ if r6 < r7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(outer_map) : __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("header_count is 4 ") __msg("widening r6 to 0..3 step 1") __naked void ptr_map_value(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r7 = r6; \ r7 += 4; \ 1: r6 += 1; \ if r6 < r7 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* Equal offsets into different maps do not establish a common origin. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") __not_msg("widening r6") __naked void ptr_map_value_other_map(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r6 = r0; \ r2 = r10; \ r2 += -8; \ r1 = %[other_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto 2f; \ r7 = r0; \ r7 += 4; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 4f; \ if r6 < r7 goto 1b; \ 4: \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map), __imm_addr(other_map) : __clobber_all); } SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("header_count is 4 ") __msg("widening r6 to 0..3 step 1") __naked void ptr_mem(void) { asm volatile (" \ r1 = %[ringbuf] ll; \ r2 = 8; \ r3 = 0; \ call %[bpf_ringbuf_reserve]; \ if r0 == 0 goto 2f; \ r8 = r0; \ r6 = r0; \ r7 = r6; \ r7 += 4; \ 1: r6 += 1; \ if r6 < r7 goto 1b; \ r1 = r8; \ r2 = 0; \ call %[bpf_ringbuf_discard]; \ 2: r0 = 0; \ exit; \ " : : __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(ringbuf) : __clobber_all); } /* Separate reservations have different pointer IDs. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (ringbuf_mem), r7 (ringbuf_mem)") __not_msg("widening r6") __naked void ptr_mem_other_reservation(void) { asm volatile (" \ r1 = %[ringbuf] ll; \ r2 = 8; \ r3 = 0; \ call %[bpf_ringbuf_reserve]; \ if r0 == 0 goto 3f; \ r8 = r0; \ r6 = r0; \ r1 = %[ringbuf] ll; \ r2 = 8; \ r3 = 0; \ call %[bpf_ringbuf_reserve]; \ if r0 == 0 goto 2f; \ r9 = r0; \ r7 = r0; \ r7 += 4; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 4f; \ if r6 < r7 goto 1b; \ 4: r1 = r9; \ r2 = 0; \ call %[bpf_ringbuf_discard]; \ 2: r1 = r8; \ r2 = 0; \ call %[bpf_ringbuf_discard]; \ 3: r0 = 0; \ exit; \ " : : __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(ringbuf) : __clobber_all); } /* An access to a buffer at a variable offset is rejected: the pointer must not be widened. */ SEC("iter/bpf_map_elem") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("header_count is 4 ") __msg("can't widen r6, expr is (+ r6 8)") __naked void ptr_buf(void) { asm volatile (" \ r6 = *(u64 *)(r1 + %[value]); \ if r6 == 0 goto 2f; \ r7 = 0; \ 1: r0 = *(u32 *)(r6 + 0); \ r6 += 8; \ r7 += 1; \ if r7 < 4 goto 1b; \ 2: r0 = 0; \ exit; \ " : : __imm_const(value, offsetof(struct bpf_iter__bpf_map_elem, value)) : __clobber_all); } /* Separate context loads receive different pointer IDs. */ SEC("iter/bpf_map_elem") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r6 (buf), r7 (buf)") __not_msg("widening r6") __naked void ptr_buf_other_load(void) { asm volatile (" \ r6 = *(u64 *)(r1 + %[value]); \ if r6 == 0 goto 2f; \ r7 = *(u64 *)(r1 + %[value]); \ if r7 == 0 goto 2f; \ r7 += 4; \ r0 = 0; \ 1: r6 += 1; \ r0 += 1; \ if r0 & 8 goto 4f; \ if r6 < r7 goto 1b; \ 4: \ 2: r0 = 0; \ exit; \ " : : __imm_const(value, offsetof(struct bpf_iter__bpf_map_elem, value)) : __clobber_all); } /* A pointer-versus-scalar latch must not establish an iteration count. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("scev: incompatible latch operands r1 (map_value), scalar 4") __not_msg("widening r1") __naked void ptr_vs_scalar_no_widen(void) { asm volatile (" \ *(u64 *)(r10 - 8) = 0; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 == 0 goto out_%=; \ r1 = r0; \ r0 = 0; \ loop_%=: \ r1 += 1; \ r0 += 1; \ if r0 & 8 goto out_%=; \ if r1 < 4 goto loop_%=; \ out_%=: \ r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* A nullable pointer must not be widened before its null check. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop header at 9, can't widen r1, expr is (+ r1 8)") __naked void no_widen_maybe_null(void) { asm volatile (" \ r1 = 0; \ *(u64 *)(r10 - 8) = r1; \ r2 = r10; \ r2 += -8; \ r1 = %[map] ll; \ call %[bpf_map_lookup_elem]; \ r1 = r0; \ r6 = 0; \ loop_%=: \ if r1 == 0 goto exit_%=; \ r1 += 8; \ r6 += 1; \ if r6 < 3 goto loop_%=; \ exit_%=: \ r0 = 0; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); } /* * A terminating inner loop does not prove termination of the outer loop. * * u64 r7 = 0; * while (bpf_get_prandom_u32() != 42) { * r7 = (r7 + 1) & 0xf; * u64 r8 = 0; * do { * r8++; * } while (r8 < 3); * } * return 0; */ SEC("xdp") __failure __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("The sequence of 8193 jumps is too complex.") __naked void nested_terminating_prune(void) { asm volatile (" \ r7 = 0; \ outer_%=: \ r7 += 1; \ r7 &= 0xf; \ call %[bpf_get_prandom_u32]; \ if r0 == 42 goto out_%=; \ r8 = 0; \ inner_%=: \ r8 += 1; \ if r8 < 3 goto inner_%=; \ goto outer_%=; \ out_%=: \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * Returning directly from the inner loop to the outer header changes the * active stack from [1, 4] to [1]. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg("loop at 1{{$}}") __msg("loop at 4, nested in 1") __msg("entering loop 1") __msg("entering loop 4") __msg("exiting loop 4") __not_msg("entering loop 1") __msg("from 4 to 1:") __msg("loop_stack=1{{$}}") __naked void nested_loop_backedge_to_outer_header(void) { asm volatile (" \ r6 = 0; \ outer_%=: \ if r6 == 3 goto exit_%=; \ r6 += 1; \ r7 = 0; \ inner_%=: \ if r7 == 2 goto outer_%=; \ r7 += 1; \ goto inner_%=; \ exit_%=: \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* Induction variable as the src operand of the latch compare. */ SEC("socket") __success __log_level(2) __msg("loop header at 2, header_count is 10") __msg("loop header at 2, widening r1 to 0..9 step 1") __flag(BPF_F_TEST_STATE_FREQ) __naked void post_cond_ivar_src(void) { asm volatile (" \ r1 = 0; \ r2 = 10; \ 1: r1 += 1; \ if r2 != r1 goto 1b; \ r0 = 0; \ exit; \ " ::: __clobber_all); } /* Early exit dominates the latch and gives a tighter bound. */ SEC("socket") __success __log_level(2) __msg(" backedge from 4, latch at 4, dominating exits at 2") __msg("loop header at 2, header_count is [0..15]") __msg("loop header at 2, widening r1 to 0..14 step 1") __flag(BPF_F_TEST_STATE_FREQ) __naked void dominating_exit_bounds_count(void) { asm volatile (" \ r1 = 0; \ r2 = 14; \ 1: if r2 == r1 goto 2f; \ r1 += 1; \ if r1 != 63 goto 1b; \ 2: r0 = 0; \ exit; \ " ::: __clobber_all); } /* * The counter is copied to a callee-saved register for the call and the copy is compared. */ SEC("xdp") __success __log_level(2) __flag(BPF_F_TEST_STATE_FREQ) __msg(" scev at latch 5:") __msg(" r7=(zext32 r1) / (zext32 (linear r1 2))") __msg("loop header at 1, header_count is 100 ") __msg("loop header at 1, widening r1 to 0..198 step 2") __naked void post_cond_jlt32_copy(void) { asm volatile (" \ w1 = 0; \ 1: w7 = w1; \ call %[bpf_get_prandom_u32]; \ w1 = w7; \ w1 += 2; \ if w7 < 198 goto 1b; \ r0 = 0; \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } /* * r6 is a pointer to ringbuf memory with a step of 1. bpf_ringbuf_discard() in the first iteration * makes a number of it. The offsets 0..1 of the pointer are not the range of this number: it's an * address. The flag in the 32-bit spill is not widened, so the second iteration is verified * on its own. */ SEC("socket") __failure __msg("math between map_value pointer and register with unbounded min value") __naked void clamp_released_pointer(void) { asm volatile ( "r1 = 0;" "*(u32 *)(r10 - 12) = r1;" "r2 = r10;" "r2 += -12;" "r1 = %[small_map] ll;" "call %[bpf_map_lookup_elem];" "if r0 == 0 goto 9f;" "r8 = r0;" "r1 = %[ringbuf] ll;" "r2 = 16;" "r3 = 0;" "call %[bpf_ringbuf_reserve];" "if r0 == 0 goto 9f;" "r6 = r0;" "r7 = r0;" "r9 = 0;" "w1 = 0;" "*(u32 *)(r10 - 8) = r1;" "1:" "w4 = *(u32 *)(r10 - 8);" "if w4 == 0 goto 2f;" "r1 = r8;" "r1 += r6;" "r0 = *(u8 *)(r1 + 0);" "goto 3f;" "2:" "r1 = r7;" "r2 = 0;" "call %[bpf_ringbuf_discard];" "3:" "w4 = 1;" "*(u32 *)(r10 - 8) = r4;" "r6 += 1;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(small_map), __imm_addr(ringbuf) : __clobber_all); } /* The same with a packet pointer and bpf_skb_pull_data() */ SEC("tc") __failure __msg("math between map_value pointer and register with unbounded min value") __naked void clamp_invalidated_pkt_pointer(void) { asm volatile ( "r7 = r1;" "r1 = 0;" "*(u32 *)(r10 - 12) = r1;" "r2 = r10;" "r2 += -12;" "r1 = %[small_map] ll;" "call %[bpf_map_lookup_elem];" "if r0 == 0 goto 9f;" "r8 = r0;" "r6 = *(u32 *)(r7 + %[data]);" "r9 = 0;" "w1 = 0;" "*(u32 *)(r10 - 8) = r1;" "1:" "w4 = *(u32 *)(r10 - 8);" "if w4 == 0 goto 2f;" "r1 = r8;" "r1 += r6;" "r0 = *(u8 *)(r1 + 0);" "goto 3f;" "2:" "r1 = r7;" "r2 = 0;" "call %[bpf_skb_pull_data];" "3:" "w4 = 1;" "*(u32 *)(r10 - 8) = r4;" "r6 += 1;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm(bpf_skb_pull_data), __imm_addr(small_map), __imm_const(data, offsetof(struct __sk_buff, data)) : __clobber_all); } /* * The compare with data_end is for r6 of this iteration: 100 bytes from r6 are in the packet. Then * r6 moves by 100. The range that the compare found is not for the r6 that returns to the head. */ SEC("tc") __failure __msg("invalid access to packet") __naked void clamp_pkt_pointer_keeps_no_range(void) { asm volatile ( "r7 = *(u32 *)(r1 + %[data_end]);" "r6 = *(u32 *)(r1 + %[data]);" "r9 = 0;" "w1 = 0;" "*(u32 *)(r10 - 8) = r1;" "1:" "w4 = *(u32 *)(r10 - 8);" "if w4 == 0 goto 2f;" /* second iteration: nothing compared this r6 with data_end */ "r0 = *(u64 *)(r6 + 56);" "2:" "r5 = r6;" "r5 += 100;" "if r5 > r7 goto 9f;" "w4 = 1;" "*(u32 *)(r10 - 8) = r4;" "r6 += 100;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" : : __imm_const(data, offsetof(struct __sk_buff, data)), __imm_const(data_end, offsetof(struct __sk_buff, data_end)) : __clobber_all); } /* A compare in front of the loop is for all iterations: the range at the entry stays */ SEC("tc") __success __retval(0) __naked void clamp_pkt_pointer_keeps_range_of_entry(void) { asm volatile ( "r7 = *(u32 *)(r1 + %[data_end]);" "r6 = *(u32 *)(r1 + %[data]);" "r5 = r6;" "r5 += 40;" "if r5 > r7 goto 9f;" "r9 = 0;" "1:" "r0 = *(u64 *)(r6 + 0);" "r6 += 8;" "r9 += 1;" "if r9 < 4 goto 1b;" "9:" "r0 = 0;" "exit;" : : __imm_const(data, offsetof(struct __sk_buff, data)), __imm_const(data_end, offsetof(struct __sk_buff, data_end)) : __clobber_all); } /* * r4 is 0, 8 .. 48, but its umax is 50. @bytes from r6 are in the packet: the range of r6 is * @start + 50 + @bytes. */ #define PKT_PLUS_R4(start, bytes) \ "r7 = *(u32 *)(r1 + %[data_end]);" \ "r6 = *(u32 *)(r1 + %[data]);" \ "r4 = *(u32 *)(r1 + %[mark]);" \ "r4 &= 0x38;" \ "if r4 > 50 goto 9f;" \ "r6 += " #start ";" \ "r6 += r4;" \ "r5 = r6;" \ "r5 += " #bytes ";" \ "if r5 > r7 goto 9f;" #define PKT_IMMS \ __imm_const(data, offsetof(struct __sk_buff, data)), \ __imm_const(data_end, offsetof(struct __sk_buff, data_end)), \ __imm_const(mark, offsetof(struct __sk_buff, mark)) /* * r6 is 0..58 at the head, and 0..56 with the step of 8. The range must go from 58 to 56 too: * in the second iteration no byte from r6 is in the packet. */ SEC("tc") __failure __msg("invalid access to packet, off=56 size=2, R6(id=2,off=56,r=56)") __naked void widen_pkt_pointer_step_lowers_umax(void) { asm volatile ( PKT_PLUS_R4(0, 8) "r9 = 0;" "1:" "r0 = *(u16 *)(r6 + 0);" "r6 += 8;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* The pointer goes down. 8 bytes from the first r6 are in the packet, not 10. */ SEC("tc") __failure __msg("invalid access to packet, off=120 size=2, R6(id=2,off=120,r=120)") __naked void widen_pkt_pointer_step_lowers_umax_down(void) { asm volatile ( PKT_PLUS_R4(64, 8) "r9 = 0;" "1:" "r0 = *(u16 *)(r6 + 8);" "r6 += -8;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* * r6 is -8..50 at the head, and -8..48 with the step of 8. Its umax is U64_MAX in the two cases. * r5 is 0..56 and has the range of r6. In the first iteration no byte from r5 is in the packet. */ SEC("tc") __failure __msg("invalid access to packet, off=56 size=2, R5(id=2,off=56,r=56)") __naked void widen_pkt_pointer_negative_offset(void) { asm volatile ( PKT_PLUS_R4(0, 8) "r9 = 0;" "1:" "r5 = r6;" "r5 += 8;" "r0 = *(u16 *)(r5 + 0);" "r6 += -8;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* The access is in the second iteration only: the verifier gets to it after the clamp */ SEC("tc") __failure __msg("invalid access to packet, off=56 size=2, R6(id=3,off=56,r=56)") __naked void clamp_pkt_pointer_step_lowers_umax(void) { asm volatile ( PKT_PLUS_R4(0, 8) "r9 = 0;" "w1 = 0;" "*(u32 *)(r10 - 8) = r1;" "1:" "w1 = *(u32 *)(r10 - 8);" "if w1 == 0 goto 2f;" "r0 = *(u16 *)(r6 + 0);" "2:" "w1 = 1;" "*(u32 *)(r10 - 8) = r1;" "r6 += 8;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* r5 is r5 = r6 + 8 or r6 at the head. Here var_off lowers umax. No byte from r6 + 8 is valid. */ SEC("tc") __failure __msg("invalid access to packet, off=56 size=2, R5(id=2,off=56,r=56)") __naked void union_pkt_pointer_var_off_lowers_umax(void) { asm volatile ( PKT_PLUS_R4(0, 8) "r9 = 0;" "1:" "r0 = *(u16 *)(r5 + 0);" "r5 = r6;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* 16 bytes from r6 are in the packet: two iterations read 8 bytes each */ SEC("tc") __success __retval(0) __naked void widen_pkt_pointer_keeps_valid_bytes(void) { asm volatile ( PKT_PLUS_R4(0, 16) "r9 = 0;" "1:" "r0 = *(u64 *)(r6 + 0);" "r6 += 8;" "r9 += 1;" "if r9 < 2 goto 1b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } /* * r6 is beyond pkt_end in front of the loop and comes back into the packet. The mark is not for * all iterations: the verifier must look at the two branches of the compare in the first pass. */ SEC("tc") __success __log_level(2) __msg("widening r6 to 32..96 step 32") __msg("6: R6=pkt(id=1,r=0,smin=umin=smin32=umin32=32,smax=umax=smax32=umax32=96") __naked void widen_pkt_pointer_beyond_pkt_end(void) { asm volatile ( "r7 = *(u32 *)(r1 + %[data_end]);" "r6 = *(u32 *)(r1 + %[data]);" "r6 += 96;" "if r6 > r7 goto 1f;" "goto 9f;" "1:" "r9 = 0;" "2:" "if r6 > r7 goto 3f;" "r0 = *(u8 *)(r6 - 1);" "3:" "r6 += -32;" "r9 += 1;" "if r9 < 3 goto 2b;" "9:" "r0 = 0;" "exit;" :: PKT_IMMS : __clobber_all); } char _license[] SEC("license") = "GPL";