Re: Backporting callback handling fixes to stable 6.1

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2024-06-20 at 13:18 +0800, Shung-Hsi Yu wrote:
> Hi Eduard,
> 
> I'm seeking suggestions for backporting callback handling fixes to the
> stable/linux-6.1.y (and similar branches), akin to what has been done
> for 6.6[1].

Hi Shung-Hsi,

I remember that porting to 6.6 was somewhat painful,
6.1 would be much worse, probably...

> Testing with the reproducer from Andrew Werner[2] it seems 6.1 has the
> same problem where the bpf_probe_read_user() call is only verified with
> the R1_w=fp-8 state, but not the R1_w=0xDEAD state because the latter
> was incorrectly pruned. So I believe the callback fixes are need.

Yes, the main problem with callbacks was that they were verified as if
called only once. This affects all functions accepting callbacks.

> The main difference from 6.6 is that 6.1 does not have BPF open-coded
> iterator, but AFAICT it does not mean "exact states comparison for
> iterator convergence checks" patch-set[3] can be dropped. This is
> because exact-state comparison from commit 2793a8b015f7 ("bpf: exact
> states comparison for iterator convergence checks") and loop-identifying
> algorithm in commit 2a0992829ea3 ("bpf: correct loop detection for
> iterators convergence") are critical for the fix; but it should be fine
> to ignore all changes to process_iter_*().

That is correct, that is the main mechanics of the fix.

> The "verify callbacks as if they are called unknown number of
> times" patch-set[4] name already suggest that it is needed, so no doubts
> there (again, dropping iterator-related changes).

Right.

I looked at the patches migrated for 6.6 vs current state of 6.1,
some thoughts below.

1.  3c4e420cb653 ("bpf: move explored_state() closer to the beginning of verifier.c ")
    - should apply as-is;
2.  4c97259abc9b ("bpf: extract same_callsites() as utility function ")
    - should apply as-is;
3.  2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks ")
    - needs regs_exact() introduced/modified in:
      - 4a95c85c9948 ("bpf: perform byte-by-byte comparison only when necessary in regsafe()")
      - 4633a0068258 ("bpf: fix regs_exact() logic in regsafe() to remap IDs correctly")
      - 1ffc85d9298e ("bpf: Verify scalar ids mapping in regsafe() using check_ids()")
    - changes to process_iter_next_call() are not needed;
    - changes to regsafe() seem applicable;
    - changes to stacksafe() seem applicable;
    - changes to func_states_equal():
      - seem applicable, but there is a commit that removes
        memset for idmap_scratch from func_states_equal(),
        it is not necessary for this particular fix,
        but is a safety fix in itself:
        1ffc85d9298e ("bpf: Verify scalar ids mapping in regsafe() using check_ids()")
    - changes to is_state_visited():
      - ignore iterator related changes, just add a new parameter for
        states_equal() where necessary;
      - change to visited states eviction heuristic is probably needed
        (the hunk with "if (sl->miss_cnt > sl->hit_cnt * n + n)");
      - don't miss the hunk with "cur->dfs_depth = new->dfs_depth + 1;";
4.  389ede06c297 ("selftests/bpf: tests with delayed read/precision makrs in loop body ")
    [didn't look at this]
5.  2a0992829ea3 ("bpf: correct loop detection for iterators convergence ")
    - looks like it could be applied with minimal changes;
6.  64870feebecb ("selftests/bpf: test if state loops are detected in a tricky case ")
    [didn't look at this]
7.  b4d8239534fd ("bpf: print full verifier states on infinite loop detection ")
    [didn't look at this]

--- patch set boundary -------------------------------------------------------------------------

8.  977bc146d4eb ("selftests/bpf: track tcp payload offset as scalar in xdp_synproxy ")
    [didn't look at this]
9.  87eb0152bcc1 ("selftests/bpf: track string payload offset as scalar in strobemeta ")
    [didn't look at this]
10. 683b96f9606a ("bpf: extract __check_reg_arg() utility function ")
    A small refactoring, shouldn't be hard to port.
11. 58124a98cb8e ("bpf: extract setup_func_entry() utility function ")
    A small refactoring, shouldn't be hard to port.
12. ab5cfac139ab ("bpf: verify callbacks as if they are called unknown number of times ")
    - backtrack_insn() lacks Andrii's refactoring that introduces 'struct backtrack_state',
      technically it shouldn't be hard to repeat patch logic w/o that refactoring,
      but this would lead to further divergence with upstream;
    - backtrack_insn() lacks subseq_idx parameter;
    - __check_func_call() seems similar enough, so shouldn't be a big problem;
    - prepare_func_exit() similar enough;
    - check_helper_call() similar enough;
    - check_kfunc_call() it looks like kfunc KF_bpf_rbtree_add_impl
      (the only kfunc that calls a callback) is not in the kernel yet,
      so changes to check_kfunc_call are not necessary;
    - visit_insn() similar enough;
    - is_state_visited() needs a 'skip_inf_loop_check' label,
      but otherwise seems applicable;
13. 958465e217db ("selftests/bpf: tests for iterating callbacks ")
    - tools/testing/selftests/bpf/prog_tests/verifier.c is not in 6.1,
      so adding a custom progs/*.c driver program would be necessary;
14. cafe2c21508a ("bpf: widening for callback iterators ")
    - technically, this is not necessary from safety point of view,
      but exact states comparison is very restrictive,
      so porting this is probably a good idea;
    - shouldn't be hard to port if widen_imprecise_scalars() and co
      are already ported;
15. 9f3330aa644d ("selftests/bpf: test widening for iterating callbacks ")
    [didn't look at this]
16. bb124da69c47 ("bpf: keep track of max number of bpf_loop callback iterations ")
    - this is more "nice to have" patch, it fallbacks to enumeration
      of every iteration step for bpf_loop, if exact match/widening
      logic does not converge;
    - shouldn't be hard to port;
    - note also the following bug fix for this commit:
      https://lore.kernel.org/bpf/20240222154121.6991-1-eddyz87@gmail.com/
17. 57e2a52deeb1 ("selftests/bpf: check if max number of bpf_loop iterations is tracked ")
    [didn't look at this]

Also note the following patch from Alexei, relaxing exact states
comparison a bit:
https://lore.kernel.org/bpf/20240306031929.42666-3-alexei.starovoitov@gmail.com/

Hope this helps.
Sounds like a lot of work.
Feel free to ask any questions about the patch-sets.

Thanks,
Eduard