On Thu, 2025-03-13 at 12:28 -0700, Eduard Zingerman wrote:
[...]
> Which makes me wonder.
> If read/precision marks for B are not final and some state D outside
> of the loop becomes equal to B, the read/precision marks for that
> state would be incomplete as well:
>
> D------. // as some read/precision marks are missing from C
> | // propagate_liveness() won't copy all necessary
> .-> A --. | // marks to D.
> | | | |
> | v v |
> '-- B C |
> ^ |
> '------'
>
> This makes comparison with 'loop_entry' states contagious,
> propagating incomplete read/precision mark flag up to the root state.
> This will have verification performance implications.
>
> Alternatively read/precision marks need to be propagated in the state
> graph until fixed point is reached. Like with DFA analysis.
>
> Решето.
And below is an example that verifier does not catch.
Another possibility is to forgo loop entries altogether and upon
states_equal(cached, cur, RANGE_WITHIN) mark all registers in the
`cached` state as read and precise, propagating this info in `cur`.
I'll try this as well.
--- 8< --------------------------------
SEC("?raw_tp")
__flag(BPF_F_TEST_STATE_FREQ)
__failure __msg("misaligned stack access off 0+-31+0 size 8")
__naked int absent_mark_in_the_middle_state2(void)
{
asm volatile (
"call %[bpf_get_prandom_u32];"
"r8 = r0;"
"r7 = 0;"
"r6 = -32;"
"r0 = 0;"
"*(u64 *)(r10 - 16) = r0;"
"r1 = r10;"
"r1 += -8;"
"r2 = 0;"
"r3 = 10;"
"call %[bpf_iter_num_new];"
"call %[bpf_get_prandom_u32];"
"if r0 == r8 goto change_r6_%=;"
"call %[bpf_get_prandom_u32];"
"before_loop_%=:"
"if r0 == r8 goto jump_into_loop_%=;"
"loop_%=:"
"r1 = r10;"
"r1 += -8;"
"call %[bpf_iter_num_next];"
"if r0 == 0 goto loop_end_%=;"
"call %[bpf_get_prandom_u32];"
"if r0 == r8 goto use_r6_%=;"
"goto loop_%=;"
"loop_end_%=:"
"r1 = r10;"
"r1 += -8;"
"call %[bpf_iter_num_destroy];"
"r0 = 0;"
"exit;"
"use_r6_%=:"
"r0 = r10;"
"r0 += r6;"
"r1 = 7;"
"*(u64 *)(r0 + 0) = r1;"
"goto loop_%=;"
"change_r6_%=:"
"r6 = -31;"
"jump_into_loop_%=: "
"goto +0;"
"goto loop_%=;"
:
: __imm(bpf_iter_num_new),
__imm(bpf_iter_num_next),
__imm(bpf_iter_num_destroy),
__imm(bpf_get_prandom_u32)
: __clobber_all
);
}
-------------------------------- >8 ---
[...]
