BPF verifier defers instruction patches to cut large-program load times

The Linux BPF verifier is dropping its long-standing habit of rewriting the instruction stream on every single patch. A series from Qiliang Yuan replaces that path with a deferred, sorted patch list that is applied once, cutting the cost of verifier passes that touch many instructions from O(N*M) to roughly O(N).

Until now, each rewrite moved the tail of the instruction and auxiliary arrays and walked the whole program to fix branches and every table that names instructions. Eduard had flagged that this work dominated load time for large programs such as pyperf180; with constant blinding under bpf_jit_harden=2, or with many nops to strip, loads could stretch into minutes.

Passes now queue patches in instruction order. At commit time the verifier builds a single old-to-new index map and relocates jumps, subprogs, line info, poke descriptors, and related tables through it. Insertions in front of an instruction, double patches (for example a barrier followed by a rewrite of the same site), removals of dead code and nops, context-access conversion, may_goto counter setup, hidden exception subprogs, bpf_loop inlining, and classic BPF constant blinding all move onto the same mechanism. Code that applied patches immediately is removed once every caller has switched.

On an x86_64 VM the gains are sharpest where many patches land. pyperf180 drops from about 0.51 s to 0.35 s in the ordinary case and from roughly 3.2 s to 0.36 s with bpf_jit_harden=2; pyperf600 falls from nearly 10 s to under a second under the same hardening. A million-instruction constant-blinding stress case that previously failed to finish in 15 minutes completes in about five seconds. Selftests cover jumps into, over, and out of patched regions, range overflow into gotol, and related edge cases.

The change matters for anyone loading large or heavily rewritten BPF programs: verifier and JIT preparation no longer scale with the product of program size and number of patches.