[PATCH bpf-next v1 1/2] bpf: states with loop entry have incomplete read/precision marks

[Eduard Zingerman <eddyz87@gmail.com>]

Suppose the verifier state exploration graph looks as follows:

    .-> A --.    Suppose:
    |   |   |    - state A is at iterator 'next';
    |   v   v    - path A -> B -> A is verified first;
    '-- B   C    - path A -> C is verified next;
                 - B does not impose a read mark for register R1;
                 - C imposes a read mark for register R1;

Under such conditions:
- when B is explored and A is identified as its loop entry, the read
  marks are copied from A to B by propagate_liveness(), but these
  marks do not include R1;
- when C is explored, the read mark for R1 is propagated to A,
  but not to B.
- at this point, state A has its branch count at zero, but state
  B has incomplete read marks.

The same logic applies to precision marks.
This means that states with a loop entry can have incomplete read and
precision marks, regardless of whether the loop entry itself has
branches.

The current verification logic does not account for this. An example
of an unsafe program accepted by the verifier is the selftest included
in the next patch.

Fix this by removing bpf_verifier_state->branches checks for loop
entries in clean_live_states() and is_state_visited().

Verification performance impact for selftests and sched_ext:

========= selftests: master vs patch =========

File                                Program            States (A)  States (B)  States (DIFF)
----------------------------------  -----------------  ----------  ----------  -------------
iters.bpf.o                         clean_live_states          66          67    +1 (+1.52%)
verifier_iterating_callbacks.bpf.o  cond_break2                10          13   +3 (+30.00%)

Total progs: 3579
Old success: 2061
New success: 2061
States diff min:    0.00%
States diff max:   30.00%
   0 .. 5    %: 3578
  30 .. 35   %: 1

========= sched_ext: master vs patch =========

File            Program           States (A)  States (B)  States (DIFF)
--------------  ----------------  ----------  ----------  -------------
bpf.bpf.o       layered_dispatch         501         516   +15 (+2.99%)
bpf.bpf.o       layered_dump             237         252   +15 (+6.33%)
bpf.bpf.o       layered_init             423         432    +9 (+2.13%)
bpf.bpf.o       p2dq_init                142         144    +2 (+1.41%)
scx_pair.bpf.o  pair_dispatch            111         138  +27 (+24.32%)
scx_qmap.bpf.o  qmap_dump                 22          30   +8 (+36.36%)
scx_qmap.bpf.o  qmap_init                654         656    +2 (+0.31%)

Total progs: 216
Old success: 186
New success: 186
States diff min:    0.00%
States diff max:   36.36%
   0 .. 5    %: 213
   5 .. 15   %: 1
  20 .. 30   %: 1
  35 .. 40   %: 1

Fixes: 2a0992829ea3 ("bpf: correct loop detection for iterators convergence")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3303a3605ee8..6c18628fa9d8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18111,7 +18111,7 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 		if (sl->state.branches)
 			continue;
 		loop_entry = get_loop_entry(env, &sl->state);
-		if (!IS_ERR_OR_NULL(loop_entry) && loop_entry->branches)
+		if (!IS_ERR_OR_NULL(loop_entry))
 			continue;
 		if (sl->state.insn_idx != insn ||
 		    !same_callsites(&sl->state, cur))
@@ -18816,7 +18816,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	struct bpf_verifier_state_list *sl;
 	struct bpf_verifier_state *cur = env->cur_state, *new, *loop_entry;
 	int i, j, n, err, states_cnt = 0;
-	bool force_new_state, add_new_state, force_exact;
+	bool force_new_state, add_new_state;
 	struct list_head *pos, *tmp, *head;
 
 	force_new_state = env->test_state_freq || is_force_checkpoint(env, insn_idx) ||
@@ -18996,9 +18996,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		loop_entry = get_loop_entry(env, &sl->state);
 		if (IS_ERR(loop_entry))
 			return PTR_ERR(loop_entry);
-		force_exact = loop_entry && loop_entry->branches > 0;
-		if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
-			if (force_exact)
+		if (states_equal(env, &sl->state, cur, loop_entry ? RANGE_WITHIN : NOT_EXACT)) {
+			if (loop_entry)
 				update_loop_entry(env, cur, loop_entry);
 hit:
 			sl->hit_cnt++;
-- 
2.48.1