Skip to content

Fix invariant violations and improve branch detection

Paul Chaignon bpf 3 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest6 patches 5 repliesApplied 6/6
  2. v26 patches 32 repliesSuperseded
  3. v14 patches 10 repliesSuperseded

Changes in v3 from the cover letter

- Rename and refactor the helper functions checking for tnum-related invariant violations (Mykyta).
- Small changes to comment style in verifier changes and new selftest

Patches in v3 All 6 applied

#Subject and filesSizeRepliesApplied
1/6bpf: Refactor reg_bounds_sanity_checkkernel/bpf/verifier.c+40 -241 replyApplied
2/6bpf: Use bpf_verifier_env buffers for reg_set_min_maxinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+26 -420 repliesApplied
3/6bpf: Exit early if reg_bounds_sync gets invalid inputskernel/bpf/verifier.c+5 -01 replyApplied
4/6bpf: Simulate branches to prune based on range violationskernel/bpf/verifier.c+51 -352 repliesApplied
5/6selftests/bpf: Cover invariant violation case from syzbottools/testing/selftests/bpf/progs/verifier_bounds.c+29 -00 repliesApplied
6/6selftests/bpf: Remove invariant violation flagstools/testing/selftests/bpf/progs/verifier_bounds.c+7 -170 repliesApplied

Reviews trailers per patch

All 6 patches have a Reviewed-by or Acked-by.

PatchShung-Hsi YuMykyta YatsenkoEduard Zingerman
1/6A-b A-b
2/6A-b A-b A-b
3/6A-b A-b
4/6A-b A-b
5/6A-b
6/6A-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes. Scroll the table sideways for all 3 reviewers.

Read the v3 thread

Cover letter [PATCH bpf-next v3 0/6] Fix invariant violations and improve branch detection

This patchset fixes invariant violations on register bounds. These invariant violations cause a warning and happen when reg_bounds_sync is trying to refine register bounds while walking an impossible branch.

This patchset takes this situation as an opportunity to improve verification performance. That is, the verifier will use the invariant violations as a signal that a branch cannot be taken and process it as dead code.

This patchset implements this approach and covers it in selftests with a new invariant violation case. Some of the logic in reg_bounds_sync likely acts as a duplicate with logic from is_scalar_branch_taken. This patchset does not attempt to remove superfluous logic from is_scalar_branch_taken and leaves it to a future patchset (ex. once syzbot has confirmed that all invariant violations are fixed).

In the future, there is also a potential opportunity to simplify existing logic by merging reg_bounds_sync and range_bounds_violation (have reg_bounds_sync error out on invariant violation). That is however not needed to fix invariant violation, which we focus on in this patchset.

Changes in v3:
- Rename and refactor the helper functions checking for tnum-related invariant violations (Mykyta).
- Small changes to comment style in verifier changes and new selftest

    (Mykyta).

- Rebased.
Changes in v2:
- Moved tmp registers to env in preparatory commit (Eduard).
- Updated reg_bounds_sync to bail out in case of ill-formed registers, thus avoiding one set of invariant violation checks in simulate_both_branches_taken (Eduard).
- Drop the Fixes tag to avoid misleading backporters (Shung-Hsi).
- Improve wording of commit descriptions (Shung-Hsi, Hari).
- Fix error in code comments (AI bot).
- Rebased.

Harishankar Vishwanathan (3):
bpf: Refactor reg_bounds_sanity_check
bpf: Exit early if reg_bounds_sync gets invalid inputs
bpf: Simulate branches to prune based on range violations

Paul Chaignon (3):
bpf: Use bpf_verifier_env buffers for reg_set_min_max selftests/bpf: Cover invariant violation case from syzbot selftests/bpf: Remove invariant violation flags

 include/linux/bpf_verifier.h                  |   4 +-
 kernel/bpf/verifier.c                         | 201 ++++++++++--------
 .../selftests/bpf/progs/verifier_bounds.c     |  51 +++--
 3 files changed, 148 insertions(+), 108 deletions(-)
Signature · 1 line
2.43.0