bpf: Replace bpf_patch_insn_data() with a list of deferred patches
Get series with b4
b4 am [email protected] change-id 20261001-bpf-verifier-patch-batch-2442080e837dVersions newest first
- v2 Latest22 patches 1 replyIn review
- 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 files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/22 | bpf: Add a list of deferred instruction patchesinclude/ kernel/ | +260 | 0 replies | |
| 2/22 | bpf: Remap the verifier state through the patch listinclude/ include/ kernel/ +2 more | +176 | 0 replies | |
| 3/22 | bpf: Apply single-instruction patches of the verifier in placekernel/ | +9 | 0 replies | |
| 4/22 | bpf: Queue the rewrites of bpf_do_misc_fixups()kernel/ | +75 | 0 replies | |
| 5/22 | bpf: Expand a backward may_goto to gotol when patches push it out of rangekernel/ | +31 | 0 replies | |
| 6/22 | bpf: Drop the constant delta from bpf_do_misc_fixups()kernel/ | +38 | 0 replies | |
| 7/22 | bpf: Let the patch list remove instructionsinclude/ kernel/ kernel/ +1 more | +176 | 1 reply | |
| 8/22 | bpf: Remove dead code through the patch listkernel/ | +3 | 0 replies | |
| 9/22 | bpf: Strip nops through the patch listkernel/ | +47 | 0 replies | |
| 10/22 | bpf: Batch the patches of bpf_opt_subreg_zext_lo32_rnd_hi32()kernel/ | +8 | 0 replies | |
| 11/22 | bpf: Allow patching an instruction twice through the patch listkernel/ kernel/ | +65 | 0 replies | |
| 12/22 | bpf: Teach the patch list to insert in front of an instructioninclude/ include/ kernel/ +2 more | +104 | 0 replies | |
| 13/22 | bpf: Allow inserting in front of a queued patchkernel/ kernel/ | +16 | 0 replies | |
| 14/22 | bpf: Move bpf_convert_ctx_accesses() to the patch listkernel/ | +49 | 0 replies | |
| 15/22 | bpf: Insert the may_goto counter setup through the patch listkernel/ | +10 | 0 replies | |
| 16/22 | bpf: Append the hidden subprog through the patch listkernel/ | +10 | 0 replies | |
| 17/22 | bpf: Inline bpf_loop() calls through the patch listkernel/ | +24 | 0 replies | |
| 18/22 | bpf: Apply the patch list without a verifier envinclude/ kernel/ | +32 | 0 replies | |
| 19/22 | bpf: Blind constants through the patch listinclude/ kernel/ | +56 | 0 replies | |
| 20/22 | bpf: Remove the old instruction patching codeinclude/ include/ include/ +4 more | +13 | 0 replies | |
| 21/22 | selftests/bpf: Test jumps around patches of bpf_do_misc_fixups()tools/ tools/ | +177 | 0 replies | |
| 22/22 | selftests/bpf: Cover a backward may_goto pushed out of range by patchestools/ | +35 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.
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]>