// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
#include <linux/bpf.h>
#include <stdbool.h>
#include <stdint.h>
#include <bpf/bpf_helpers.h>
#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";