Merge branch 'bpf-various-arm64-bpf-jit-improvements'
Daniel Borkmann says:
====================
bpf: Various arm64 BPF JIT improvements
This series changes the arm64 BPF JIT to emit shorter and faster native
code for the instruction patterns that LLVM-compiled programs hit in the
real world. Every change stays within the lowering of a single BPF
instruction. This is a similar effort as done recently for x86-64 BPF
JIT [0].
On arm64 under vmtest.sh (qemu TCG), test_verifier, test_maps, jit_insns
and jit_insns_blinded pass in full, and test_progs and its cpuv4 and
no_alu32 flavors only fail tests that fail without the series as well
or only under TCG. The encodings were checked against Arm's machine-readable
A64 ISA XML: every A64_* macro and directly called encoder, run with
boundary and invalid operands (39028 cases), gives the encoding and
fields the Arm ARM expects or AARCH64_BREAK_FAULT for what it cannot
encode.
To see what the series does to code that is actually deployed, the BPF
objects of Cilium (c3fbffb08183), Tetragon (31e646a5ed0c, the variants
for kernels from 6.1 on), Katran (623234e1814b) and the sched_ext
schedulers (scx at a40cb6115e68) were built with clang 20 for arm64, and
every program of them that loads (338, another 25 fail on both kernels)
was loaded with veristat in the arm64 VM of vmtest.sh, on a kernel
before and one after this series. The size is jited_prog_len, the cycles
and uops are those of the llvm-mca 20 models of the Neoverse N1
(Graviton2, Ampere Altra), N2 (Cobalt 100), V1 (Graviton3) and V2
(Graviton4, Grace, Axion) over the JITed images as straight-line code,
without the helper calls, which llvm-mca cannot model, and the LSE
atomics, which the models have no scheduling information for. This is a
static model without the path taken, branch prediction or cache misses,
but both sides get the same program, so the delta is what the series
rewrote. All numbers are averaged over two boots of each kernel, as a
map address with a zero 16-bit halfword takes one move less.
Project Progs Size N1 cycles N2 cycles V1 cycles V2 cycles N1 uOps N2 uOps V1 uOps V2 uOps
---------- ----- ------- --------- --------- --------- --------- ------- ------- ------- -------
cilium 160 -3.31% -7.36% -11.26% -6.86% -9.35% -3.52% -3.94% -3.53% -3.53%
katran 5 -6.41% -7.53% -9.07% -8.57% -0.36% -6.35% -8.44% -6.39% -6.38%
scx 99 -5.95% -7.63% -6.60% -7.11% -5.43% -5.91% -4.79% -6.06% -6.02%
tetragon 74 -4.23% -5.83% -5.92% -6.30% -3.31% -4.46% -4.63% -4.51% -4.50%
all 338 -3.88% -6.88% -9.01% -6.71% -6.91% -4.08% -4.30% -4.11% -4.10%
Cilium gains the most cycles from its 355 divisions by NSEC_PER_SEC in
81 programs, which come from the monotonic clock helper that conntrack,
NAT and the load balancer run for every entry: all four models put a
64-bit udiv at 20 cycles against 11 to 13 for the magic number sequence,
and the N2 and V2 models do not pipeline the divider at all. The
schedulers have 14 divisions in 7 programs, mostly by 100 and 1000000.
The rest of the cycles and most of the uops come from the branches:
12711 compares against zero and their branch become a cbz or cbnz, and
2961 sign and bit tests a tbz or tbnz, a uop and a cycle each. Then 979
loads and stores take the unscaled form, 505 xors with all ones become a
mvn, 482 stores of zero take the zero register, 187 tail calls lose six
instructions each, and 98 multiplications become an add or sub with a
shifted register. Katran stays flat on V2, whose model dispatches 16
wide.
For a feel of the native code, the tail call of Katran's xdp_root
program, from the bounds checks to the test of the program slot.
Before:
3c: 5280088a mov w10, #68
40: b86a682a ldr w10, [x1, x10]
44: 2a0203e2 mov w2, w2
48: 6b0a005f cmp w2, w10
4c: 54000222 b.hs #68
50: 5280042a mov w10, #33
54: f940034c ldr x12, [x26]
58: eb0a019f cmp x12, x10
5c: 540001a2 b.hs #52
60: 9100058c add x12, x12, #1
64: 5280440a mov w10, #544
68: 8b0a002a add x10, x1, x10
6c: d37df04b lsl x11, x2, #3
70: f86b694b ldr x11, [x10, x11]
74: b40000eb cbz x11, #28
After:
3c: b940442a ldr w10, [x1, #68]
40: 6b0a005f cmp w2, w10
44: 540001a2 b.hs #52
48: f940034c ldr x12, [x26]
4c: f100859f cmp x12, #33
50: 54000142 b.hs #40
54: 9100058c add x12, x12, #1
58: 9108802a add x10, x1, #544
5c: f862594b ldr x11, [x10, w2, uxtw #3]
60: b40000cb cbz x11, #24
Of the 338 programs, 303 get smaller, and 284, 270, 277 and 225 faster
on N1, N2, V1 and V2. The best cases:
Impact Largest decrease Largest relative decrease
--------- -------------------------------------------------- ------------------------------------
size generic_usdt_filter_arg 27388 > 26256 -4.13% pandemonium_enable 280 > 224 -20.00%
N1 cycles tail_handle_ipv6 922 > 807 -12.52% flash_select_cpu 74 > 53 -28.38%
N2 cycles tail_handle_ipv6 760 > 605 -20.39% flash_enqueue 179 > 98 -45.25%
V1 cycles tail_handle_ipv4 542 > 471 -13.10% flash_select_cpu 66 > 41 -37.88%
V2 cycles tail_handle_ipv6_from_netdev 441 > 339 -23.13% flash_enqueue 147 > 67 -54.42%
The largest gains in cycles are in Cilium's bpf_lxc.o and bpf_host.o,
whose programs above hold 7 to 11 of the divisions by NSEC_PER_SEC each,
and in Tetragon's generic_usdt_filter_arg for size, which turns 243 of
its 961 conditional branches into a cbz, cbnz, tbz or tbnz. The scx_flash
programs gain the most relative to their length, from their divisions by
100.
No project gets bigger or slower on any model. The worst cases per
program, which for the cycles are the same in every pairing of a boot
before with one after the series:
Impact Worse Largest increase Largest relative increase
--------- ----- ------------------------------------------- ---------------------------------
size 3 flash_select_cpu 616 > 640 +3.90% the same
N1 cycles 1 rusty_set_weight 42 > 43 +2.38% the same
N2 cycles 1 rusty_set_weight 37 > 38 +2.70% the same
V1 cycles 2 rusty_stopping 92 > 94 +2.17% rusty_set_weight 37 > 38 +2.70%
V2 cycles 10 tail_nodeport_nat_egress_ipv4 295 > 301 +2.03% mitosis_dump_task 49 > 52 +6.12%
Of the three programs that grow, flash_select_cpu and flash_enqueue of
scx_flash do so by 24 and 16 bytes for their divisions by 100, and
tail_drop_notify of Cilium's bpf_xdp only in one pairing of boots. None
of the 12 programs that some model rates slower has more instructions;
their changes are compares and branches that became a cbz or cbnz, which
the model then issues in another order. The uops grow in 3 programs, 4
on N2, by at most 2.86%.
The rewrites on their own, in llvm-mca for one instance of each sequence
as the JIT emits it, in a single pass with the pipeline fill included.
An arena access at an immediate offset keeps its cycles, the add of the
offset now off the path of the offset register, at a uop more on N2.
cycles, uops N1 N2 V1 V2
r2 /= 1000000000 25>13 3>7 25>11 3>7 25>11 3>7 25>11 3>7
r3 /= 100 24>13 2>7 24>11 2>7 24>11 2>7 24>11 2>7
if r6 == 0 goto 5>4 2>1 5>4 2>1 5>4 2>1 5>4 2>1
if w0 s< 0 goto 5>4 2>1 5>4 2>1 5>4 2>1 5>4 2>1
w2 = *(u32 *)(r8 + 6) 8>7 2>1 8>7 3>1 8>7 2>1 8>7 2>1
arena r0 = *(u64 *)(r9 + 0) 8>7 2>1 8>7 2>2 8>7 2>1 8>7 2>1
*(u64 *)(r1 + 0) = 0 5>4 3>2 5>4 3>2 5>4 3>2 4>4 3>2
w1 ^= -1 5>4 2>1 5>4 2>1 5>4 2>1 5>4 2>1
r0 *= 24 8>5 2>2 6>5 2>2 6>5 2>2 6>5 2>2
w1 *= 65537 7>5 3>1 7>5 3>1 7>5 3>1 7>5 3>1
if w2 > 0xffff goto 6>5 3>2 6>5 3>2 6>5 3>2 6>5 3>2
tail call slot of w3 9>8 4>2 9>8 5>3 9>8 4>2 9>8 4>2
Thanks,
Daniel
v2 -> v3:
- Divide by constants in the verifier via UHMUL/SHMUL, replacing v2 07
and 15 and x86's emit_div_const() (Alexei)
- x86 now keeps a div for smod and for umod by divisors that need the
add sequence or a dividend shift
- tbz/tbnz decided once from the pass 1 offsets, dropping extra_pass,
max_idx and the new multi-func bound (Alexei)
- New fix: measure branches back from the branch itself; the sizing
pass failed conditional branches back to targets ~1MB into the image
- int shift after the extend in the register offset encoder instead of
the scaled flag (Alexei)
- Dropped the A64_LDR*()/A64_STR*() macros left unused (Alexei), and
the already unused A64_BL, A64_BTI_C and A64_LDR32LIT
- Encoders reject what they cannot encode as given: bad extends, ADR
beyond 4GB, STXR/LDP/STP overlaps and branch counts that wrap
- Rebased onto the PROBE_MEM user address filter and BPF_REG_ARENA_SP
- Kernel comment style, shorter comments and commit messages (sashiko,
bpf ci bot)
- New verifier_div_const test; jit_insns adds a far branch back, the
PROBE_MEM filter offsets, the tbz/tbnz reach, jset and sign jumps
v1 -> v2:
- Share the divisor selection with x86 via bpf_magic_div() in the core
instead of copying it into the arm64 JIT (Alexei)
- tailcall: ldr x11, [x10, w2, uxtw #3] in place of ubfiz + ldr, with
a scaled flag in the register offset encoder (Xu)
- tbz/tbnz decided once in pass 2 from the sizing pass offsets, no
repeated sizing passes (Alexei)
- Dropped the 24-bit immediate split which was 4 bytes for a cycle
of latency (Alexei)
- Arena acquire/release test insns built with __imm_insn() (bpf ci bot)
[0] https://lore.kernel.org/bpf/20261013171230.523677-1-daniel@iogearbox.net/
====================
Link: https://patch.msgid.link/cover.1794165614.git.daniel@iogearbox.net
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
