Re: [PATCH bpf-next v1 3/4] bpf: use SCC info instead of loop_entry

[Eduard Zingerman <eddyz87@gmail.com>]

Alexei Starovoitov <alexei.starovoitov@gmail.com> writes:

> On Mon, Apr 28, 2025 at 12:26 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>>
>>
>> It is simmetrical in a way.
>
> is it possible to make them the same?
>
>> Operations on bpf_verifier_state->branches:
>> - do_check_common() initializes env->cur_state->branches == 1
>>   (and this is maintained as invariant);
>> - push_stack() does env->cur_state->parent->branches++;
>> - update_branch_counts() does env->cur_state->parent->branches--
>>   (and continues recursively).
>>
>> Operations on bpf_scc_info->branches:
>> - is_state_visited() does insn_scc(env->cur_state->parent->insn_idx)->branches++
>
> But this is not the same as = 1 at init time.
> do_check_common() does it for current state,
> while this extra parent_scc_enter() in is_state_visited()
> after a new state is created is doing it for the parent.
> Which is not the same at all.
> After new state is created st->branches = 1,
> but scc(cur_idx)->branches = 0 while scc(parent->insn_idx) got incremented
> and now may be 1 or higher.

Right after is_state_visited() for parent -> cur_state pair it is an
invariant, that:
- scc(parent)->branches == 1
  (because this state just became a parent it only has one child state atm);
- scc(cur_state)->branches == 0

So, the difference is in a state after is_state_visited() {1,0} vs {1,1}.

>> - push_stack() does insn_scc(env->cur_state->parent->insn_idx)->branches++;
>
> this one is equivalent indeed.
>
>> - update_branch_counts() does
>>   insn_scc(env->cur_state->parent->insn_idx)->branches--
>>   (and continues recursively);
>
> But this one is not.
> It's doing scc(parent)->branches-- only after st->branches reaches zero.
> It's not touching scc(cur_idx)->branches at all.
>
>> The main difference is that bpf_verifier_state->branches is initialized to 1,
>> while bpf_scc_info->branches is initialized to 0.
>> Hence a call to parent_scc_enter() in is_state_visited().
>
> Hmm, extra scc_enter doesn't look equivalent to init to 1.
> Maybe scc branches need this different counting logic,
> but being different from st->branches makes everything harder
> to understand.
> Maybe st->branches should be converted to this new counting?
> Logically they are supposed to count the same thing.
> Both are counting the number of branches being explored.
> And push_stack() doing it exactly the same way for both is
> a sign that they should be the same in decrements too.
> But they're not.

Ok, I'll try to make these identical to avoid confusion.
Effectively, what's needed is a ->branches counter of a state
that entered SCC first for current state chain,
but I didn't want to store a pointer in bpf_scc_info.

---

Here is another bummer.
I figured out a test to cover my mistake with frame_insn_idx() [1].

[1] https://lore.kernel.org/bpf/20250426104634.744077-1-eddyz87@gmail.com/T/#me1944d603de3438e5db7266fab5159c6c315268f

A simple modification, really:

  diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
  index 646dc0fdd44d..12030aa340b2 100644
  --- a/tools/testing/selftests/bpf/progs/iters.c
  +++ b/tools/testing/selftests/bpf/progs/iters.c
  @@ -1683,6 +1683,7 @@ __naked int absent_mark_in_the_middle_state(void)
                  "call %[bpf_get_prandom_u32];"
                  "if r0 == r8 goto change_r6_%=;"
          "loop_%=:"
  +               "call noop;"
                  "r1 = r10;"
                  "r1 += -8;"
                  "call %[bpf_iter_num_next];"
  @@ -1714,6 +1715,15 @@ __naked int absent_mark_in_the_middle_state(void)
          );
   }
  
  +__used __naked
  +static int noop(void)
  +{
  +       asm volatile (
  +               "r0 = 0;"
  +               "exit;"
  +       );
  +}
  +
   SEC("?raw_tp")
   __flag(BPF_F_TEST_STATE_FREQ)
   __failure __msg("misaligned stack access off 0+-31+0 size 8")

But it showed a much deeper bug. SCCs are computed for an
intera-procedural CFG. Which means that verifier is inside a loop if any
IP in current emulated call stack is in an SCC.

So either:
(a) each IP in the emulated call stack needs to be checked
    if it is a member of an SCC;
(b) or insn_succesors() for SCC construction needs to return
    called sub-program entry as a successor for bpf pseudo call.

(b) is simpler but might get too pessimistic if same sub-program is
called both inside and outside the loop. (a) -- needs some thought.
I'll try (b) and check how it affects selftests and scx.