[PATCH bpf-next 0/4] bpf: Apply the rewrites of bpf_do_misc_fixups() at once

[Qiliang Yuan <odys.yuan@gmail.com>]

Eduard pointed out that bpf_patch_insn_data() takes a large share of the
time to load pyperf180 [1]. Every patch moves the tail of the
instruction and aux data arrays and walks the whole program to fix up
branches, so a pass that patches M instructions of an N instruction
program does O(N * M) work. Kumar's commit 261b61d3735b ("bpf: Make
post-verification instruction rewrites killable") made that work
preemptible, but its cost is still quadratic.

On current bpf-next nearly all of it comes from one place in pyperf:
bpf_do_misc_fixups() inlines each bpf_map_lookup_elem() on a hash map
into 3 instructions, 930 times in a ~24k instruction program for
pyperf180 and 1530 times in ~42k instructions for pyperf600.

Patch 1 adds a list of patches that a pass queues and then applies in
one O(N + inserted instructions) step. It keeps the semantics of
bpf_patch_insn_data(): a patched instruction is named by the first
instruction of its patch, and jumps from a patch out of it are relative
to the patch in place. Branches, aux data, subprog starts, line info,
instruction arrays, function pointers and poke descriptors are
remapped together. Patch 2 moves the main loop of bpf_do_misc_fixups()
to it, patch 3 drops the delta that is now always 0, and patch 4 adds
xlated tests for jumps around patches.

The other passes still use bpf_patch_insn_data() and can move over to
the list one at a time in follow-up series.

perf stat -B --all-kernel -r30 -- veristat -q <obj>, mean of two rounds,
x86_64 VM with 32 vCPUs:

                      base      patched
  pyperf180          0.575 s    0.458 s   -20.4%
  pyperf600          1.491 s    1.041 s   -30.2%
  strobemeta         0.531 s    0.532 s
  test_verif_scale2  0.561 s    0.562 s

For the 1042 objects of the selftests, the 2863 programs that load have
the same xlated code on both kernels, with the immediates that hold
kernel addresses or BTF ids masked. test_verifier passes on both. Of
test_progs, only missed/tp_recursion failed once on the patched kernel
in a parallel run, it passes when run alone.

On a side note, the largest part of the time to load pyperf180 is the
arg tracking analysis: analyze_subprog() takes about half of it on base,
__arg_track_join() alone about 30%.

[1] https://lore.kernel.org/bpf/a714ee96d0ad96bbc9d51037616e5c4e2790a8ec.camel@gmail.com/

Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
---
Qiliang Yuan (4):
      bpf: Add a list of deferred instruction patches
      bpf: Queue the rewrites of bpf_do_misc_fixups() and apply them at once
      bpf: Drop the constant delta from bpf_do_misc_fixups()
      selftests/bpf: Test jumps around patches of bpf_do_misc_fixups()

 include/linux/bpf.h                                |   1 +
 include/linux/bpf_verifier.h                       |  26 +
 kernel/bpf/bpf_insn_array.c                        |  18 +
 kernel/bpf/fixups.c                                | 545 ++++++++++++++-------
 kernel/bpf/verifier.c                              |   1 +
 tools/testing/selftests/bpf/prog_tests/verifier.c  |   2 +
 .../selftests/bpf/progs/verifier_patch_list.c      | 120 +++++
 7 files changed, 546 insertions(+), 167 deletions(-)
---
base-commit: 6a75c73eebd4d497ded7d08b47894f9ddbebb5a9
change-id: 20261001-bpf-verifier-patch-batch-2442080e837d

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