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@xxxxxxxxx/
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@xxxxxxxxx/
Hope this helps.
Sounds like a lot of work.
Feel free to ask any questions about the patch-sets.
Thanks,
Eduard
