Skip to content

bpf: Replace bpf_patch_insn_data() with a list of deferred patches

Qiliang Yuan bpf linux-kselftest lkml 2 versions – In review

Get series with b4
b4 am [email protected] change-id 20261001-bpf-verifier-patch-batch-2442080e837d

Versions newest first

  1. v2 Latest22 patches 1 replyIn review
  2. v14 patches 3 repliesSuperseded

Changes in v2 from the cover letter

- 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

Patches in v2 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/22bpf: Add a list of deferred instruction patchesinclude/linux/bpf_verifier.h kernel/bpf/core.c+260 -00 replies
2/22bpf: Remap the verifier state through the patch listinclude/linux/bpf.h include/linux/bpf_verifier.h kernel/bpf/bpf_insn_array.c +2 more+176 -00 replies
3/22bpf: Apply single-instruction patches of the verifier in placekernel/bpf/fixups.c+9 -10 replies
4/22bpf: Queue the rewrites of bpf_do_misc_fixups()kernel/bpf/fixups.c+75 -1640 replies
5/22bpf: Expand a backward may_goto to gotol when patches push it out of rangekernel/bpf/fixups.c+31 -70 replies
6/22bpf: Drop the constant delta from bpf_do_misc_fixups()kernel/bpf/fixups.c+38 -380 replies
7/22bpf: Let the patch list remove instructionsinclude/linux/bpf_verifier.h kernel/bpf/bpf_insn_array.c kernel/bpf/core.c +1 more+176 -121 reply
8/22bpf: Remove dead code through the patch listkernel/bpf/fixups.c+3 -100 replies
9/22bpf: Strip nops through the patch listkernel/bpf/fixups.c+47 -1890 replies
10/22bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32()kernel/bpf/fixups.c+8 -140 replies
11/22bpf: Allow patching an instruction twice through the patch listkernel/bpf/core.c kernel/bpf/fixups.c+65 -40 replies
12/22bpf: Teach the patch list to insert in front of an instructioninclude/linux/bpf.h include/linux/bpf_verifier.h kernel/bpf/bpf_insn_array.c +2 more+104 -210 replies
13/22bpf: Allow inserting in front of a queued patchkernel/bpf/core.c kernel/bpf/fixups.c+16 -130 replies
14/22bpf: Move bpf_convert_ctx_accesses() to the patch listkernel/bpf/fixups.c+49 -830 replies
15/22bpf: Insert the may_goto counter setup through the patch listkernel/bpf/fixups.c+10 -630 replies
16/22bpf: Append the hidden subprog through the patch listkernel/bpf/fixups.c+10 -70 replies
17/22bpf: Inline bpf_loop() calls through the patch listkernel/bpf/fixups.c+24 -380 replies
18/22bpf: Apply the patch list without a verifier envinclude/linux/bpf_verifier.h kernel/bpf/core.c+32 -00 replies
19/22bpf: Blind constants through the patch listinclude/linux/bpf_verifier.h kernel/bpf/core.c+56 -340 replies
20/22bpf: Remove the old instruction patching codeinclude/linux/bpf.h include/linux/bpf_verifier.h include/linux/filter.h +4 more+13 -4730 replies
21/22selftests/bpf: Test jumps around patches of bpf_do_misc_fixups()tools/testing/selftests/bpf/prog_tests/verifier.c tools/testing/selftests/bpf/progs/verifier_patch_list.c+177 -00 replies
22/22selftests/bpf: Cover a backward may_goto pushed out of range by patchestools/testing/selftests/bpf/progs/verifier_patch_list.c+35 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.

Read the v2 thread

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

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/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

---
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/[email protected]

---
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,

Signature · 1 line
Qiliang Yuan <[email protected]>