[PATCH bpf-next v2 00/22] bpf: Replace bpf_patch_insn_data() with a list of deferred patches

[Qiliang Yuan]

bpf_patch_insn_data() and bpf_patch_insn_single() apply a patch right
away: they move the tail of the instruction and aux data arrays and walk
the whole program to fix up branches and every table that names
instructions. Removing instructions works the same way.

A pass that patches M instructions of an N instruction program does
O(N * M) work. Eduard pointed out that this takes a large share of the
time to load pyperf180 [1], and with bpf_jit_harden=2 or many nops to
remove it gets to minutes.

Replace them with a list that a pass fills with patches and commits
once in O(N + inserted instructions). Following the layout of Jiong's
RFC [2], the list goes to core.c and the verifier side to fixups.c,
then each pass moves over and the last patch removes the old code. As
Andrii suggested there, map every old index to a new one once and
relocate all jumps through that map. Since passes queue patches in
increasing order of the instruction they replace, keep the list in a
sorted array instead of a linked list.

  1-3   the patch list in core.c and in the verifier
  4-6   bpf_do_misc_fixups(), gotol for a backward may_goto
  7-9   removal of instructions, dead code and nops
  10    zext
  11-13 patching an instruction twice, inserting in front of one
  14-17 ctx accesses, may_goto counter setup, hidden subprog, bpf_loop()
  18-19 commit without a verifier env, constant blinding
  20    removal of the old code
  21-22 selftests

Load times on an x86_64 VM with 32 vCPUs, the base commit below with
and without the series, measured in one round: perf stat -r30 --
veristat -q <obj> averaged over two runs, -r10 for BPF_F_TEST_RND_HI32
and bpf_jit_harden=2, three runs of loading 131072 "ja 0":

                                   base       patched
  pyperf180                       0.512 s    0.350 s
  pyperf600                       1.407 s    0.885 s
  strobemeta                      0.591 s    0.588 s
  test_verif_scale2               0.643 s    0.646 s
  pyperf180, BPF_F_TEST_RND_HI32  1.708 s    0.360 s
  pyperf600, BPF_F_TEST_RND_HI32  5.161 s    0.891 s
  pyperf180, bpf_jit_harden=2     3.185 s    0.362 s
  pyperf600, bpf_jit_harden=2     9.879 s    0.899 s
  131072 "ja 0" removed          53.146 s    0.769 s

With bpf_jit_harden=2, test_verifier's "ld_dw: xor semi-random 64 bit
imms, test 5" doesn't load within 900 s on base and loads in 5 s with
the series.

For the 1052 objects of the selftests, every program that loads has the
same xlated code, line info and func info on both kernels, by default,
with BPF_F_TEST_RND_HI32 and with bpf_jit_harden=2, masking the
immediates that hold addresses, BTF ids and blinding constants.
test_verifier passes on both, test_bpf fails the same 53 tests on both
when hardened, and test_progs only shows failures that are flaky in
parallel runs.

[1] https://lore.kernel.org/bpf/a714ee96d0ad96bbc9d51037616e5c4e2790a8ec.camel@xxxxxxxxx/
[2] https://lore.kernel.org/bpf/1562275611-31790-1-git-send-email-jiong.wang@xxxxxxxxxxxxx/

Signed-off-by: Qiliang Yuan <odys.yuan@xxxxxxxxx>
---
V1 -> V2:
- Convert every pass and remove the old patching code (Alexei)
- Build the new image in core.c, so that blinding without a verifier env
  uses the list too
- Let the list remove instructions, insert in front of one and patch one
  twice
- Pick JEQ or gotol for a backward may_goto from its offset grown by the
  patches in between, v1 picked JEQ when that offset was -32768 (CI bot)
- Test a backward may_goto expanded to gotol
- Test a jump that the patches push out of its 16-bit range, and a gotox
  to a patched insn
- Rebase onto current bpf-next, which adds the arena_scalar rewrite

v1: https://lore.kernel.org/r/20261001-bpf-verifier-patch-batch-v1-0-a12df8a09160@xxxxxxxxx

---
Qiliang Yuan (22):
      bpf: Add a list of deferred instruction patches
      bpf: Remap the verifier state through the patch list
      bpf: Apply single-instruction patches of the verifier in place
      bpf: Queue the rewrites of bpf_do_misc_fixups()
      bpf: Expand a backward may_goto to gotol when patches push it out of range
      bpf: Drop the constant delta from bpf_do_misc_fixups()
      bpf: Let the patch list remove instructions
      bpf: Remove dead code through the patch list
      bpf: Strip nops through the patch list
      bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32()
      bpf: Allow patching an instruction twice through the patch list
      bpf: Teach the patch list to insert in front of an instruction
      bpf: Allow inserting in front of a queued patch
      bpf: Move bpf_convert_ctx_accesses() to the patch list
      bpf: Insert the may_goto counter setup through the patch list
      bpf: Append the hidden subprog through the patch list
      bpf: Inline bpf_loop() calls through the patch list
      bpf: Apply the patch list without a verifier env
      bpf: Blind constants through the patch list
      bpf: Remove the old instruction patching code
      selftests/bpf: Test jumps around patches of bpf_do_misc_fixups()
      selftests/bpf: Cover a backward may_goto pushed out of range by patches

 include/linux/bpf.h                                |    4 +-
 include/linux/bpf_verifier.h                       |   87 +-
 include/linux/filter.h                             |   16 -
 kernel/bpf/bpf_insn_array.c                        |   35 +-
 kernel/bpf/core.c                                  |  552 ++++++---
 kernel/bpf/fixups.c                                | 1285 +++++++++-----------
 kernel/bpf/verifier.c                              |   46 +-
 tools/testing/selftests/bpf/prog_tests/verifier.c  |    2 +
 .../selftests/bpf/progs/verifier_patch_list.c      |  210 ++++
 9 files changed, 1240 insertions(+), 997 deletions(-)
---
base-commit: 7101b10cf281f629ac58c99697ca6f6d082b99a7
change-id: 20261001-bpf-verifier-patch-batch-2442080e837d

Best regards,
-- 
Qiliang Yuan <odys.yuan@xxxxxxxxx>