bpf: Various arm64 BPF JIT improvements
Daniel Borkmann
maintainerv3 cover 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/[email protected]/
Daniel Borkmann (24):
bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT bpf, arm64: Free the offset table of a subprog in bpf_jit_free bpf, arm64: Free the private stack when a pass over the image fails bpf, arm64: Emit ISB SY in the speculation barriers
arm64, insn: Reject sign extending loads of 64 bits
bpf, arm64: Keep the ll/sc atomics address apart from the old value bpf, arm64: Measure backward branches from the branch itself arm64, insn: Reject invalid and unpredictable operands in the encoders bpf, arm64: Widen the branch offsets before scaling them to bytes arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings
bpf: Divide by constants via uhmul and shmul in the verifier bpf, arm64: Consolidate the load and store emission into a helper bpf, arm64: Use the unscaled forms for negative and unaligned offsets bpf, arm64: Store zero immediates from the zero register bpf, arm64: Zero extend the arena offset in register offset accesses bpf, arm64: Adjust compares with unencodable immediates by one bpf, arm64: Materialize immediates with fewer instructions bpf, arm64: Shorten the tail call sequence
bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests bpf, arm64: Multiply by constants with shifts, adds and subs selftests/bpf: Let the arm64 private stack check skip the BTI pad selftests/bpf: Test the verifier's division by constants selftests/bpf: Extend the JIT instruction tests for arm64 encodings
arch/arm64/include/asm/insn.h | 21 +- arch/arm64/lib/insn.c | 173 +++- arch/arm64/net/bpf_jit.h | 69 +- arch/arm64/net/bpf_jit_comp.c | 769 +++++++++++++----- arch/x86/net/bpf_jit_comp.c | 219 +---- kernel/bpf/fixups.c | 199 +++++ .../selftests/bpf/prog_tests/jit_insns.c | 753 +++++++++++++++-- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/jit_insns_arena.c | 446 +++++++++- .../selftests/bpf/progs/verifier_div_const.c | 225 +++++ .../selftests/bpf/progs/verifier_ldsx.c | 24 +- .../bpf/progs/verifier_private_stack.c | 1 + 12 files changed, 2340 insertions(+), 561 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_div_const.c
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 1/24 bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT
A64_BL() and A64_LDR32LIT() never had a user. A64_BTI_C lost its last user when commit a3f25d614bc7 ("bpf, arm64: Fix BTI type used for freplace attached functions") made the prologue emit BTI JC. Remove them.
--- arch/arm64/net/bpf_jit.h | 4 ---- 1 file changed, 4 deletions(-)
arch/arm64/net/bpf_jit.h +0 -4
@@ -45,7 +45,6 @@#define A64_BRANCH (offset, type) aarch64_insn_gen_branch_imm(0, offset, \ AARCH64_INSN_BRANCH_##type)#define A64_B (imm26) A64_BRANCH((imm26) << 2, NOLINK) -#define A64_BL (imm26) A64_BRANCH((imm26) << 2, LINK)/* Unconditional branch (register) */ #define A64_BR (Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_NOLINK)
@@ -87,8 +86,6 @@#define A64_LDR64I (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, LOAD)/* LDR (literal) */ -#define A64_LDR32LIT (Wt, offset) \ - aarch64_insn_gen_load_literal(0, offset, Wt, false)#define A64_LDR64LIT (Xt, offset) \ aarch64_insn_gen_load_literal(0, offset, Xt, true)
@@ -324,7 +321,6 @@#define A64_AUTIASP A64_HINT(AARCH64_INSN_HINT_AUTIASP)/* BTI */ -#define A64_BTI_C A64_HINT(AARCH64_INSN_HINT_BTIC)#define A64_BTI_J A64_HINT(AARCH64_INSN_HINT_BTIJ)#define A64_BTI_JC A64_HINT(AARCH64_INSN_HINT_BTIJC)#define A64_NOP A64_HINT(AARCH64_INSN_HINT_NOP)
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 2/24 bpf, arm64: Free the offset table of a subprog in bpf_jit_free
In reply to Daniel BorkmannWhen jit_subprogs() fails after some subprogs were already JITed, it frees them through bpf_jit_free(). That frees jit_data, but not the offset table that jit_data keeps for the extra pass, so every such failure leaks the table.
Free the offset table there as well, as the x86, riscv and LoongArch JITs do.
--- arch/arm64/net/bpf_jit_comp.c | 1 + 1 file changed, 1 insertion(+)
arch/arm64/net/bpf_jit_comp.c +1 -0
@@ -3616,6 +3616,7 @@ void bpf_jit_free(struct bpf_prog *prog)*/ if (jit_data) {bpf_jit_binary_pack_finalize (jit_data->ro_header, jit_data->header); +kvfree (jit_data->ctx.offset);kfree (jit_data); } prog->bpf_func = (void *)prog->bpf_func -cfi_get_offset ();
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 3/24 bpf, arm64: Free the private stack when a pass over the image fails
In reply to Daniel BorkmannWhen a pass over the image fails, including the extra pass of a subprog, the image is freed but ro_header is left set. The exit path then skips freeing the private stack. It stays allocated behind priv_stack_ptr, and bpf_jit_free() does not free it either, as the program is not marked as JITed.
Clear ro_header and header once the image is freed, so that the exit path frees the private stack as it does for failures before the image was allocated. The x86 JIT does the same with its image pointer.
--- arch/arm64/net/bpf_jit_comp.c | 3 +++ 1 file changed, 3 insertions(+)
arch/arm64/net/bpf_jit_comp.c +3 -0
@@ -2564,6 +2564,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_prbpf_arch_text_copy (&ro_header->size, &header->size,sizeof (header->size));bpf_jit_binary_pack_free (ro_header, header); +/* The private stack goes with the image, see out_off */ + ro_header =NULL ; + header =NULL ; } goto out_off; }
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 4/24 bpf, arm64: Emit ISB SY in the speculation barriers
In reply to Daniel BorkmannThe Spectre-BHB loop in the epilogue and BPF_NOSPEC on CPUs without FEAT_SB both end in an ISB. The JIT takes its encoding from the instruction matcher's template, which leaves CRm as 0. The Arm ARM lists that encoding as reserved.
Emit ISB SY instead, with CRm set to 0b1111. This is also what the assembler emits for the kernel's own isb().
Before/after:
d50330df isb #0
d5033fdf isb
--- arch/arm64/net/bpf_jit.h | 2 +- arch/arm64/net/bpf_jit_comp.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
arch/arm64/net/bpf_jit.h +1 -1
@@ -343,6 +343,6 @@/* Barriers */ #define A64_SB aarch64_insn_get_sb_value()#define A64_DSB_NSH (aarch64_insn_get_dsb_base_value() | 0x7 << 8) -#define A64_ISB aarch64_insn_get_isb_value() +#define A64_ISB (aarch64_insn_get_isb_value() | 0xf << 8)#endif /* _BPF_JIT_H */
arch/arm64/net/bpf_jit_comp.c +1 -1
@@ -1044,7 +1044,7 @@ static void __maybe_unused build_bhb_mitigation(struct jit_ctx *ctx)emit (A64_SUBS_I (true, r1, r1,1 ), ctx);emit (A64_B_ (A64_COND_NE ,-2 ), ctx);emit (aarch64_insn_gen_dsb (AARCH64_INSN_MB_ISH ), ctx); -emit (aarch64_insn_get_isb_value (), ctx); +emit (A64_ISB , ctx); }if (is_spectre_bhb_fw_mitigated ()) {
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 5/24 arm64, insn: Reject sign extending loads of 64 bits
In reply to Daniel BorkmannWith the 64-bit size, the encoding of LDRSB, LDRSH and LDRSW becomes PRFM. So when asked for a 64-bit sign extending load, the load and store encoders returned a prefetch instead of failing. The BPF JIT never asks for one, as BPF_MEMSX has no BPF_DW form, but return AARCH64_BREAK_FAULT as for other invalid operands.
Before/after for a 64-bit sign extending load from x1 + 8 into x0:
f9800420 prfm pldl1keep, [x1, #8]
d4202000 brk #0x100
--- arch/arm64/lib/insn.c | 12 ++++++++++++ 1 file changed, 12 insertions(+)
arch/arm64/lib/insn.c +12 -0
@@ -389,6 +389,12 @@ u32 aarch64_insn_gen_load_store_reg(enum aarch64_insn_register reg, insn =aarch64_insn_get_ldr_reg_value ();break ;case AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET : +/* With the size of 64 bits this encodes PRFM */ +if (size ==AARCH64_INSN_SIZE_64 ) { +pr_err ("%s: invalid size for a signed load %d\n" , + __func__, size); +return AARCH64_BREAK_FAULT ; + } insn =aarch64_insn_get_signed_ldr_reg_value ();break ;case AARCH64_INSN_LDST_STORE_REG_OFFSET :
@@ -437,6 +443,12 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg, insn =aarch64_insn_get_ldr_imm_value ();break ;case AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET : +/* With the size of 64 bits this encodes PRFM */ +if (size ==AARCH64_INSN_SIZE_64 ) { +pr_err ("%s: invalid size for a signed load %d\n" , + __func__, size); +return AARCH64_BREAK_FAULT ; + } insn =aarch64_insn_get_signed_load_imm_value ();break ;case AARCH64_INSN_LDST_STORE_IMM_OFFSET :
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 6/24 bpf, arm64: Keep the ll/sc atomics address apart from the old value
In reply to Daniel BorkmannWith a zero offset, the ll/sc fetching atomics use dst_reg directly as the address. They load the old value into src_reg, or into r0 for cmpxchg, and then store through dst_reg. If that register is dst_reg itself, the load overwrites the address, and the store then uses the old value as its address. The verifier rejects such programs, but the JIT should not rely on that.
Copy the address into a temporary when the register receiving the old value is the address register. The LSE forms are not affected.
Before/after for r1 = atomic_fetch_add((u64 *)(r1 + 0), r1) without LSE:
aa0003e9 mov x9, x0 c85f7c00 ldxr x0, [x0] 8b09000b add x11, x0, x9 c80cfc0b stlxr w12, x11, [x0] 35ffffac cbnz w12, ... d5033bbf dmb ish
aa0003ea mov x10, x0 aa0003e9 mov x9, x0 c85f7d40 ldxr x0, [x10] 8b09000b add x11, x0, x9 c80cfd4b stlxr w12, x11, [x10] 35ffffac cbnz w12, ... d5033bbf dmb ish
--- arch/arm64/net/bpf_jit_comp.c | 6 ++++++ 1 file changed, 6 insertions(+)
arch/arm64/net/bpf_jit_comp.c +6 -0
@@ -888,6 +888,7 @@ static int emit_ll_sc_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)const s32 imm = insn->imm;const s16 off = insn->off;const bool isdw =BPF_SIZE (code) ==BPF_DW ; +const int load_reg =bpf_atomic_load_reg (insn);u8 reg = dst;s32 jmp_offset;
@@ -901,6 +902,11 @@ static int emit_ll_sc_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)emit_a64_add_i (1 , tmp, reg, tmp, off, ctx); reg = tmp; } +/* The load of the old value must not clobber the address */ +if (load_reg >=0 && bpf2a64[load_reg] == reg) { +emit (A64_MOV (1 , tmp, reg), ctx); + reg = tmp; + }if (imm ==BPF_ADD || imm ==BPF_AND || imm ==BPF_OR || imm ==BPF_XOR ) {
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 7/24 bpf, arm64: Measure backward branches from the branch itself
In reply to Daniel Borkmannbpf2a64_offset() takes the position of a branch from the offset of the next BPF instruction, which the current pass has not set yet:
- In the sizing pass that offset is still 0, so a branch back gets the target's instruction index plus one as its offset. This exceeds the imm19 maximum of 2^18 - 1 instructions once the target is at index 2^18 - 1 or later, i.e. 4 bytes short of 1MB into the image, and check_imm19() fails the program.
- In the second pass it still holds the value from the first pass, so a branch back is overestimated by however much the code in front of it shrank.
For a branch back, take ctx->idx instead, which is the position of the branch in every pass.
--- arch/arm64/net/bpf_jit_comp.c | 6 ++++++ 1 file changed, 6 insertions(+)
arch/arm64/net/bpf_jit_comp.c +6 -0
@@ -267,6 +267,12 @@ static inline int bpf2a64_offset(int bpf_insn, int off, {/* BPF JMP offset is relative to the next instruction */ bpf_insn++; +/* +* A branch back counts from itself, as the offsets from the next +* instruction on are not yet those of this pass. +*/ +if (off <0 ) +return ctx->offset[bpf_insn + off] - ctx->idx;/* * Whereas arm64 branch instructions encode the offset * from the branch itself, so we must subtract 1 from the
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 8/24 arm64, insn: Reject invalid and unpredictable operands in the encoders
In reply to Daniel BorkmannA few encoders return a valid instruction for operands the instruction cannot take, instead of AARCH64_BREAK_FAULT:
- The extended register add and sub put any @extend into the 3-bit option field, so -1 becomes SXTX and 8 becomes UXTB.
- ADR truncates its offset to 32 bits before the range check, so an offset beyond 4GB can wrap into range.
- STXR and STLXR accept a status register equal to the data or base register, LDP equal target registers, and pre- and post-index LDP and STP a target register equal to the base. The Arm ARM makes all of these CONSTRAINED UNPREDICTABLE.
Reject them. No caller passes such operands, so this only keeps a future caller from silently emitting a wrong or unpredictable instruction.
Also print the size, not the type, when the immediate offset load and store encoder rejects a size.
--- arch/arm64/lib/insn.c | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-)
arch/arm64/lib/insn.c +31 -1
@@ -426,7 +426,7 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,u32 shift;if (size <AARCH64_INSN_SIZE_8 || size >AARCH64_INSN_SIZE_64 ) { -pr_err ("%s: unknown size encoding %d\n" , __func__, type); +pr_err ("%s: unknown size encoding %d\n" , __func__, size);return AARCH64_BREAK_FAULT ; }
@@ -542,6 +542,18 @@ u32 aarch64_insn_gen_load_store_pair(enum aarch64_insn_register reg1,return AARCH64_BREAK_FAULT ; } +/* +* CONSTRAINED UNPREDICTABLE: LDP with Rt == Rt2, and a base written +* back that is Rt or Rt2 +*/ +if ((reg1 == reg2 && (type ==AARCH64_INSN_LDST_LOAD_PAIR_PRE_INDEX || + type ==AARCH64_INSN_LDST_LOAD_PAIR_POST_INDEX )) || + (base !=AARCH64_INSN_REG_SP && (reg1 == base || reg2 == base))) { +pr_err ("%s: overlapping registers %d, %d, %d\n" , __func__, + reg1, reg2, base); +return AARCH64_BREAK_FAULT ; + } + insn =aarch64_insn_encode_register (AARCH64_INSN_REGTYPE_RT , insn, reg1);
@@ -610,6 +622,15 @@ u32 aarch64_insn_gen_load_store_ex(enum aarch64_insn_register reg,return AARCH64_BREAK_FAULT ; } +/* CONSTRAINED UNPREDICTABLE: the status register Rs as Rt or Rn */ +if ((type ==AARCH64_INSN_LDST_STORE_EX || + type ==AARCH64_INSN_LDST_STORE_REL_EX ) && + (state == reg || (state == base && base !=AARCH64_INSN_REG_SP ))) { +pr_err ("%s: overlapping registers %d, %d, %d\n" , __func__, + state, reg, base); +return AARCH64_BREAK_FAULT ; + } + insn =aarch64_insn_encode_ldst_size (size, insn); insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn,
@@ -1042,6 +1063,12 @@ u32 aarch64_insn_gen_add_sub_extended_reg(enum aarch64_insn_register dst,return AARCH64_BREAK_FAULT ; } +if (extend <AARCH64_INSN_EXTEND_UXTB || + extend >AARCH64_INSN_EXTEND_SXTX ) { +pr_err ("%s: invalid extend encoding %d\n" , __func__, extend); +return AARCH64_BREAK_FAULT ; + } +if (shift <0 || shift >4 ) {pr_err ("%s: invalid shift encoding %d\n" , __func__, shift);return AARCH64_BREAK_FAULT ;
@@ -1293,6 +1320,9 @@ u32 aarch64_insn_gen_adr(unsigned long pc, unsigned long addr,switch (type) {case AARCH64_INSN_ADR_TYPE_ADR : insn =aarch64_insn_get_adr_value (); +/* The s32 offset would truncate a difference beyond 4GB */ +if ((long )(addr - pc) != (s32)(addr - pc)) +return AARCH64_BREAK_FAULT ; offset = addr - pc;break ;case AARCH64_INSN_ADR_TYPE_ADRP :
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf-next v3 08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider: - [Low] arm64, insn: s32 offset truncation in aarch64_insn_gen_adr() for ADRP --
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Low] arm64, insn: s32 offset truncation in aarch64_insn_gen_adr() for ADRP
--
commit cecf5be8cc096127beade0ea92a07c5f62e297a6
Author: Daniel Borkmann <[email protected]>
arm64, insn: Reject invalid and unpredictable operands in the encoders
This commit rejects out-of-range and CONSTRAINED UNPREDICTABLE operands in several arm64 instruction encoders so they return AARCH64_BREAK_FAULT.
Quoted 4 lines
arch/arm64/lib/insn.c +0
-0
[ ... ]
arch/arm64/lib/insn.c u32 aarch64_insn_gen_adr(unsigned long pc, unsigned long addr, · line 1328
Quoted 10 lines
arch/arm64/lib/insn.c +3
-0@@ -1293,6 +1320,9 @@ u32 aarch64_insn_gen_adr(unsigned long pc, unsigned long addr,switch (type) {case AARCH64_INSN_ADR_TYPE_ADR : insn =aarch64_insn_get_adr_value (); +/* The s32 offset would truncate a difference beyond 4GB */ +if ((long )(addr - pc) != (s32)(addr - pc)) +return AARCH64_BREAK_FAULT ; offset = addr - pc;break ;case AARCH64_INSN_ADR_TYPE_ADRP :
[Severity: Low]
Can the AARCH64_INSN_ADR_TYPE_ADRP branch right below still truncate into range when storing the shifted page difference into s32 offset?
arch/arm64/lib/insn.c:aarch64_insn_gen_adr() {
u32 insn;
s32 offset;
...
case AARCH64_INSN_ADR_TYPE_ADRP:
insn = aarch64_insn_get_adrp_value();
offset = (addr - ALIGN_DOWN(pc, SZ_4K)) >> 12;
break;
...
if (offset < -SZ_1M || offset >= SZ_1M)
return AARCH64_BREAK_FAULT;
}When addr and pc are 16 TiB or more apart, bits [51:32] of the shifted page offset are dropped before the [-SZ_1M, SZ_1M) range check. Declaring offset as long (like label_imm_common()) and casting the difference to long before shifting in the ADRP case would avoid 32-bit truncation in both branches without needing the separate s32 comparison.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Daniel Borkmann
maintainerRe: [PATCH bpf-next v3 08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders
Quoted 4 lines · On 11/8/26 8:38 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Low] arm64, insn: s32 offset truncation inaarch64_insn_gen_adr()for ADRP
Not used the the arm64 JIT, but I'll follow-up with a fix for this case as well once back from travel.
Thanks,
Daniel
Daniel Borkmann
maintainerPATCH v3 9/24 bpf, arm64: Widen the branch offsets before scaling them to bytes
In reply to Daniel BorkmannThe branch macros shift their instruction count left by 2 as an int. A count of magnitude 2^29 or more overflows, possibly into range, and yields a valid branch to the wrong place instead of AARCH64_BREAK_FAULT. No caller gets near that, but widen the count to a long before scaling it, so that the encoders range check the full offset.
--- arch/arm64/net/bpf_jit.h | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-)
arch/arm64/net/bpf_jit.h +8 -4
@@ -19,12 +19,16 @@#define A64_VARIANT (sf) \ ((sf) ? AARCH64_INSN_VARIANT_64BIT : AARCH64_INSN_VARIANT_32BIT) +/* Branch offsets in bytes, widened first so a far count cannot wrap */ +#define A64_BR_OFF (imm) ((long)(imm) * AARCH64_INSN_SIZE) +/* Compare & branch (immediate) */ #define A64_COMP_BRANCH (sf, Rt, offset, type) \ aarch64_insn_gen_comp_branch_imm(0, offset, Rt, A64_VARIANT(sf), \ AARCH64_INSN_BRANCH_COMP_##type) -#define A64_CBZ (sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, (imm19) << 2, ZERO) -#define A64_CBNZ (sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, (imm19) << 2, NONZERO) +#define A64_CBZ (sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), ZERO) +#define A64_CBNZ (sf, Rt, imm19) \ + A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), NONZERO)/* Conditional branch (immediate) */ #define A64_COND_BRANCH (cond, offset) \
@@ -39,12 +43,12 @@#define A64_COND_GT AARCH64_INSN_COND_GT/* signed > */ #define A64_COND_LE AARCH64_INSN_COND_LE/* signed <= */ #define A64_COND_LT AARCH64_INSN_COND_LT/* signed < */ -#define A64_B_ (cond, imm19) A64_COND_BRANCH(cond, (imm19) << 2) +#define A64_B_ (cond, imm19) A64_COND_BRANCH(cond, A64_BR_OFF(imm19))/* Unconditional branch (immediate) */ #define A64_BRANCH (offset, type) aarch64_insn_gen_branch_imm(0, offset, \ AARCH64_INSN_BRANCH_##type) -#define A64_B (imm26) A64_BRANCH((imm26) << 2, NOLINK) +#define A64_B (imm26) A64_BRANCH(A64_BR_OFF(imm26), NOLINK)/* Unconditional branch (register) */ #define A64_BR (Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_NOLINK)
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 10/24 arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings
In reply to Daniel BorkmannAdd the encodings that the BPF JIT needs for its shorter sequences:
- LDUR, STUR and LDURS{B,H,W}: loads and stores with a signed 9-bit byte offset, for the negative and unaligned offsets that the scaled forms cannot encode.
- TBZ and TBNZ: test a single bit and branch, within +/-32KB.
- Extend and shift parameters for the register offset loads and stores, in the same order as the extended register add and sub take them. They allow UXTW of a 32-bit offset register, and scaling the offset by the access size. UXTX gives the plain 64-bit register form as before.
- A check that UMULH and SMULH use the 64-bit variant with Ra set to the zero register, as their encoding requires.
The JIT is the only user of the register offset encoder. It passes UXTX without a shift, so its loads and stores stay the same, except for the sign extending ones: their template had SXTX, which does the same for a 64-bit offset register, and they now get UXTX like the others.
Like the scaled and register offset forms, the unscaled sign extending loads reject the 64-bit size, which would encode PRFUM.
--- arch/arm64/include/asm/insn.h | 21 +++++- arch/arm64/lib/insn.c | 129 ++++++++++++++++++++++++++++++++++ arch/arm64/net/bpf_jit.h | 10 +-- 3 files changed, 155 insertions(+), 5 deletions(-)
arch/arm64/include/asm/insn.h +20 -1
@@ -170,6 +170,8 @@ enum aarch64_insn_branch_type {AARCH64_INSN_BRANCH_RETURN ,AARCH64_INSN_BRANCH_COMP_ZERO ,AARCH64_INSN_BRANCH_COMP_NONZERO , +AARCH64_INSN_BRANCH_TEST_ZERO , + AARCH64_INSN_BRANCH_TEST_NONZERO, }; enum aarch64_insn_size_type {
@@ -196,6 +198,9 @@ enum aarch64_insn_ldst_type {AARCH64_INSN_LDST_STORE_REL_EX ,AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET ,AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET , +AARCH64_INSN_LDST_LOAD_UNSCALED_IMM_OFFSET , +AARCH64_INSN_LDST_STORE_UNSCALED_IMM_OFFSET , + AARCH64_INSN_LDST_SIGNED_LOAD_UNSCALED_IMM_OFFSET, }; enum aarch64_insn_adsb_type {
@@ -205,7 +210,7 @@ enum aarch64_insn_adsb_type {AARCH64_INSN_ADSB_SUB_SETFLAGS }; -/* option field of add/sub (extended register) */ +/* option field of add/sub (extended register) and load/store (register) */ enum aarch64_insn_extend_type {AARCH64_INSN_EXTEND_UXTB ,AARCH64_INSN_EXTEND_UXTH ,
@@ -355,6 +360,9 @@ __AARCH64_INSN_FUNCS(store_post, 0x3FE00C00, 0x38000400) __AARCH64_INSN_FUNCS(load_post, 0x3FE00C00, 0x38400400) __AARCH64_INSN_FUNCS(str_reg, 0x3FE0EC00, 0x38206800) __AARCH64_INSN_FUNCS(str_imm, 0x3FC00000, 0x39000000) +__AARCH64_INSN_FUNCS(stur, 0x3FE00C00, 0x38000000) +__AARCH64_INSN_FUNCS(ldur, 0x3FE00C00, 0x38400000) +__AARCH64_INSN_FUNCS(signed_ldur, 0x3FE00C00, 0x38800000) __AARCH64_INSN_FUNCS(ldadd, 0x3F20FC00, 0x38200000) __AARCH64_INSN_FUNCS(ldclr, 0x3F20FC00, 0x38201000)__AARCH64_INSN_FUNCS (ldeor,0x3F20FC00 ,0x38202000 )
@@ -586,6 +594,10 @@ u32 aarch64_insn_gen_comp_branch_imm(unsigned long pc, unsigned long addr,enum aarch64_insn_register reg, enum aarch64_insn_variant variant, enum aarch64_insn_branch_type type); +u32 aarch64_insn_gen_test_branch_imm (unsigned long pc,unsigned long addr, +enum aarch64_insn_register reg, +int bit, +enum aarch64_insn_branch_type type);u32 aarch64_insn_gen_cond_branch_imm (unsigned long pc,unsigned long addr,enum aarch64_insn_condition cond);
@@ -610,6 +622,8 @@ u32 aarch64_insn_gen_branch_reg(enum aarch64_insn_register reg,u32 aarch64_insn_gen_load_store_reg (enum aarch64_insn_register reg,enum aarch64_insn_register base,enum aarch64_insn_register offset, +enum aarch64_insn_extend_type extend, +int shift,enum aarch64_insn_size_type size,enum aarch64_insn_ldst_type type); u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
@@ -617,6 +631,11 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,unsigned int imm, enum aarch64_insn_size_type size, enum aarch64_insn_ldst_type type); +u32 aarch64_insn_gen_load_store_unscaled (enum aarch64_insn_register reg, +enum aarch64_insn_register base, +int imm, +enum aarch64_insn_size_type size, +enum aarch64_insn_ldst_type type);u32 aarch64_insn_gen_load_literal (unsigned long pc,unsigned long addr,enum aarch64_insn_register reg,bool is64bit);
arch/arm64/lib/insn.c +129 -0
162 lines not on this page · raw message
arch/arm64/net/bpf_jit.h +6 -4
@@ -55,11 +55,13 @@#define A64_BLR (Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_LINK)#define A64_RET (Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_RETURN) -/* Load/store register (register offset) */ -#define A64_LS_REG (Rt, Rn, Rm, size, type) \ - aarch64_insn_gen_load_store_reg(Rt, Rn, Rm, \ - AARCH64_INSN_SIZE_##size, \ +/* Load/store register (register offset), at Rn + (EXT(Rm) << shift) */ +#define A64_LS_REG_EXT (Rt, Rn, Rm, ext, shift, size, type) \ + aarch64_insn_gen_load_store_reg(Rt, Rn, Rm, AARCH64_INSN_EXTEND_##ext, \ + shift, AARCH64_INSN_SIZE_##size, \ AARCH64_INSN_LDST_##type##_REG_OFFSET) +#define A64_LS_REG (Rt, Rn, Rm, size, type) \ + A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type)#define A64_STRB (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 8, STORE)#define A64_LDRB (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 8, LOAD)#define A64_LDRSB (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 8, SIGNED_LOAD)
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 11/24 bpf: Divide by constants via uhmul and shmul in the verifier
In reply to Daniel BorkmannLLVM has no high-half multiply to strength-reduce 64-bit divisions by a constant, so they reach the kernel as BPF_DIV and BPF_MOD with BPF_K. On arm64, that is a udiv or sdiv of 5 to 20 cycles.
Rewrite them in bpf_do_misc_fixups() into a uhmul or shmul by the magic number, for the JITs that support UHMUL and SHMUL. This replaces emit_div_const() in the x86 JIT.
With AX as the only scratch register, smod keeps the division, and so does umod when the divisor needs the add sequence or a dividend shift. The division is also kept for a divisor of 1, an unsigned divisor above 2^63, and for blinded or offloaded programs.
Powers of two are not special-cased, as LLVM already emits shifts for them. The sequences were checked in user space against C division across the imm32 range.
Like other rewrites that grow a program, this one can leave a jump at the edge of its range over such a division unpatchable. So jit_insns' max_jmp now divides by -7, which stays a division.
Before/after on x86 for r1 /= 1000. r1 %= 1000 is back to a div, as 1000 needs the add sequence or a dividend shift:
50 pushq %rax 52 pushq %rdx 48 89 f8 movq %rdi,%rax 48 c1 e8 03 shrq $0x3,%rax 49 bb cf f7 53 e3 a5 9b c4 20 movabsq $0x20c49ba5e353f7cf,%r11 49 f7 e3 mulq %r11 48 c1 ea 04 shrq $0x4,%rdx 48 89 d7 movq %rdx,%rdi 5a popq %rdx 58 popq %rax
48 c1 ef 03 shrq $0x3,%rdi 49 ba cf f7 53 e3 a5 9b c4 20 movabsq $0x20c49ba5e353f7cf,%r10 4d 89 d3 movq %r10,%r11 50 pushq %rax 52 pushq %rdx 48 89 f8 movq %rdi,%rax 49 f7 e3 mulq %r11 48 89 d7 movq %rdx,%rdi 5a popq %rdx 58 popq %rax 48 c1 ef 04 shrq $0x4,%rdi
--- arch/x86/net/bpf_jit_comp.c | 219 +----------------- kernel/bpf/fixups.c | 199 ++++++++++++++++ .../selftests/bpf/prog_tests/jit_insns.c | 26 +-- 3 files changed, 208 insertions(+), 236 deletions(-)
arch/x86/net/bpf_jit_comp.c +1 -218
@@ -2035,218 +2035,6 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) *pprog = prog; } -struct bpf_div_magic { -u64 m;/* multiplier, sign extended for signed division */ -int s;/* shift of the high half of the product */ -bool add;/* multiplier has 65 bits, use the add sequence */ -}; - -/* -* Multiplier and shift for an unsigned division by the constant d, with -* 2 <= d < 2^64 and a dividend below 2^(64 - lz): n / d == (mulhu(n, m) -* >> s), or with the add sequence when m needs 65 bits, (((n - t) >> 1) -* + t) >> (s - 1) with t = mulhu(n, m). Hacker's Delight, 2nd ed., figure -* 10-2. -*/ -static void bpf_magic_udiv (u64 d,int lz,struct bpf_div_magic *mag) -{ -u64 mask = ~0ULL >> (lz &63 ); -u64 nc, delta, q1, r1, q2, r2; -int p; - - mag->add = false; -/* Largest value with nc mod d == d - 1 */ - nc = mask - (mask % d +1 ) % d; - p =63 ; - q1 = (1ULL <<63 ) / nc;/* 2^p / nc */ - r1 = (1ULL <<63 ) - q1 * nc;/* 2^p mod nc */ - q2 = (~0ULL >>1 ) / d;/* (2^p - 1) / d */ - r2 = (~0ULL >>1 ) - q2 * d;/* (2^p - 1) mod d */ -do { - p++; -if (r1 >= nc - r1) { - q1 =2 * q1 +1 ; - r1 =2 * r1 - nc; - }else { - q1 =2 * q1; - r1 =2 * r1; - } -if (r2 +1 >= d - r2) { -if (q2 >= (~0ULL >>1 )) - mag->add = true; - q2 =2 * q2 +1 ; - r2 =2 * r2 +1 - d; - }else { -if (q2 >= (1ULL <<63 )) - mag->add = true; - q2 =2 * q2; - r2 =2 * r2 +1 ; - } - delta = d -1 - r2; - }while (p <128 && (q1 < delta || (q1 == delta && r1 ==0 ))); - - mag->m = q2 +1 ; - mag->s = p -64 ; -} - -/* -* Multiplier and shift for a signed division by the constant d, with -* 2 <= |d| < 2^63: q = mulhs(n, m), q += n if d > 0 and m < 0, q -= n -* if d < 0 and m > 0, q >>= s (arithmetic), n / d == q + (q >>> 63). -* Hacker's Delight, 2nd ed., figure 10-1. -*/ -static void bpf_magic_sdiv (s64 d,struct bpf_div_magic *mag) -{ -u64 ad = d <0 ? -(u64 )d : (u64 )d; -u64 t, anc, delta, q1, r1, q2, r2; -int p; - - t = (1ULL <<63 ) + (d <0 ); - anc = t -1 - t % ad;/* |nc| */ - p =63 ; - q1 = (1ULL <<63 ) / anc;/* 2^p / |nc| */ - r1 = (1ULL <<63 ) - q1 * anc;/* 2^p mod |nc| */ - q2 = (1ULL <<63 ) / ad;/* 2^p / |d| */ - r2 = (1ULL <<63 ) - q2 * ad;/* 2^p mod |d| */ -do { - p++; - q1 =2 * q1; - r1 =2 * r1; -if (r1 >= anc) { - q1++; - r1 -= anc; - } - q2 =2 * q2; - r2 =2 * r2; -if (r2 >= ad) { - q2++; - r2 -= ad; - } - delta = ad - r2; - }while (q1 < delta || (q1 == delta && r1 ==0 )); - - mag->m = q2 +1 ; -if (d <0 ) - mag->m = -mag->m; - mag->s = p -64 ; - mag->add = false; -} - -/* -* Divide dst_reg by the constant in insn->imm of a 64-bit division through -* a multiplication with the magic number from bpf_magic_udiv() or -* bpf_magic_sdiv(). The dividend goes through rax and the multiplier -* through r11, the caller saves rax and rdx unless they are dst_reg, and -* r10 is scratch. Returns false for the divisors left to div/idiv. -*/ -static bool emit_div_const (u8 **pprog,const struct bpf_insn *insn,u32 dst_reg) -{ -bool is_mod =BPF_OP (insn->code) ==BPF_MOD ; -bool is_signed = insn->off ==1 ; -u32 n_reg = dst_reg, q_reg; -s32 imm32 = insn->imm; -struct bpf_div_magic mag; -u8 *prog = *pprog; -int corr =0 , pre =0 , s; - -if (is_signed) { -/* |d| >= 2, the verifier already rewrote d == -1 */ -if (imm32 >=-1 && imm32 <=1 ) -return false; -bpf_magic_sdiv (imm32, &mag); -/* q += n for d > 0 and m < 0, q -= n for d < 0 and m > 0 */ -if (imm32 >0 && (s64 )mag.m <0 ) - corr =1 ; -else if (imm32 <0 && (s64 )mag.m >0 ) - corr =-1 ; - }else { -/* d >= 2, a negative imm32 is a divisor above 2^63 */ -if (imm32 <2 ) -return false; -bpf_magic_udiv (imm32,0 , &mag); -/* -* Shift the dividend by the trailing zeros of an even divisor -* first, the magic number of the odd part then fits without -* the add sequence. -*/ -if (mag.add && !(imm32 &1 )) { - pre =__ffs (imm32) &31 ; -bpf_magic_udiv (imm32 >> pre, pre, &mag); -if (mag.add) -return false; - } - } - s = mag.s; -/* -* The shift is at most 63, or 64 with the add sequence which shifts -* by s - 1 and needs s >= 1. Never hit for d >= 2, kept as a guard -* against an unencodable count. -*/ -if (s >64 - !mag.add || (mag.add && !s)) -return false; - -/* Keep the dividend when the multiplication clobbers it */ -if ((is_mod || mag.add || corr) && - (dst_reg ==BPF_REG_0 || dst_reg ==BPF_REG_3 )) { -emit_mov_reg (&prog, true,BPF_REG_AX , dst_reg); - n_reg =BPF_REG_AX ; - } - -/* mov rax, dst_reg; shr rax, pre; mov r11, m; mul r11 or imul r11 */ -if (dst_reg !=BPF_REG_0 ) -emit_mov_reg (&prog, true,BPF_REG_0 , dst_reg); -if (pre) -emit_shift_imm (&prog,BPF_RSH ,BPF_REG_0 , pre, true); -emit_mov_imm64 (&prog,AUX_REG , mag.m >>32 , (u32 )mag.m); -EMIT3 (0x49 ,0xF7 , is_signed ?0xEB :0xE3 ); -if (is_signed) { -/* add rdx, n_reg or sub rdx, n_reg */ -if (corr) -emit_alu_reg (&prog, corr >0 ?BPF_ADD :BPF_SUB , -BPF_REG_3 , n_reg, true); -/* sar rdx, s */ -if (s) -emit_shift_imm (&prog,BPF_ARSH ,BPF_REG_3 , s, true); -/* mov rax, rdx; shr rax, 63; add rdx, rax */ -emit_mov_reg (&prog, true,BPF_REG_0 ,BPF_REG_3 ); -emit_shift_imm (&prog,BPF_RSH ,BPF_REG_0 ,63 , true); -emit_alu_reg (&prog,BPF_ADD ,BPF_REG_3 ,BPF_REG_0 , true); - q_reg =BPF_REG_3 ; - }else if (!mag.add) { -/* shr rdx, s */ -if (s) -emit_shift_imm (&prog,BPF_RSH ,BPF_REG_3 , s, true); - q_reg =BPF_REG_3 ; - }else { -/* mov rax, n_reg; sub rax, rdx; shr rax, 1 */ -emit_mov_reg (&prog, true,BPF_REG_0 , n_reg); -emit_alu_reg (&prog,BPF_SUB ,BPF_REG_0 ,BPF_REG_3 , true); -emit_shift_imm (&prog,BPF_RSH ,BPF_REG_0 ,1 , true); -/* add rax, rdx; shr rax, s - 1 */ -emit_alu_reg (&prog,BPF_ADD ,BPF_REG_0 ,BPF_REG_3 , true); -if (s >1 ) -emit_shift_imm (&prog,BPF_RSH ,BPF_REG_0 , s -1 , true); - q_reg =BPF_REG_0 ; - } - -if (is_mod) { -/* imul q_reg, q_reg, imm32 */ -maybe_emit_mod (&prog, q_reg, q_reg, true); -if (is_imm8 (imm32)) -EMIT3 (0x6B ,add_2reg (0xC0 , q_reg, q_reg), imm32); -else -EMIT2_off32 (0x69 ,add_2reg (0xC0 , q_reg, q_reg), imm32); -/* sub n_reg, q_reg */ -emit_alu_reg (&prog,BPF_SUB , n_reg, q_reg, true); - q_reg = n_reg; - } -if (q_reg != dst_reg) -emit_mov_reg (&prog, true, dst_reg, q_reg); - - *pprog = prog; -return true; -} -static void emit_priv_frame_ptr (u8 **pprog,void __percpu *priv_frame_ptr) {u8 *prog = *pprog;
@@ -2901,11 +2689,6 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *if (dst_reg !=BPF_REG_3 )EMIT1 (0x52 );/* push rdx */ -/* LLVM strength-reduces the 32-bit ones itself */ -if (is64 &&BPF_SRC (insn->code) ==BPF_K && -emit_div_const (&prog, insn, dst_reg)) - goto div_done; -if (BPF_SRC (insn->code) ==BPF_X ) {if (src_reg ==BPF_REG_0 || src_reg ==BPF_REG_3 ) {
@@ -2952,7 +2735,7 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int * dst_reg != BPF_REG_0)/* mov dst_reg, rax */ emit_mov_reg (&prog, is64, dst_reg,BPF_REG_0 ); -div_done: +if (dst_reg !=BPF_REG_3 )EMIT1 (0x5A );/* pop rdx */ if (dst_reg !=BPF_REG_0 )
kernel/bpf/fixups.c +199 -0
211 lines not on this page · raw message
tools/testing/selftests/bpf/prog_tests/jit_insns.c +8 -18
@@ -582,14 +582,10 @@ static void test_alu_imm_regs(void) }/* -* Division and modulo by constants for every width, signedness and -* destination register with a set of divisors and dividends around the -* multiple boundaries and the extremes of each range. This covers a JIT -* replacing the division with a multiplication by a magic number in all -* of its forms: magic numbers needing the extra add step, zero shifts, -* both signed corrections, and the divisors like 1, -1 and the ones -* above 2^63 that are still emitted as a real division. The dividends -* of the 32-bit operations carry garbage in the upper 32 bits. +* Division and modulo by constants for every width, signedness and register, +* with dividends at the multiple boundaries and the extremes: every form of +* the verifier's multiplication by the magic number and the divisors it keeps. +* The dividends of the 32-bit operations carry garbage in the upper half. */ static const __s32 unsigned_divisors[] = {2 ,3 ,7 ,10 ,25 ,641 ,1000 ,4096 ,65536 ,1000000007 ,0x7fffffff ,
@@ -2486,15 +2482,9 @@ static void test_acq_rel(void) }/* -* A jump with the maximal offset over instructions which expand to several -* native ones, so that the native offset outgrows the field of a short -* branch and takes the JITs through their branch conversion. The region -* must not grow in the verifier, or the jump could not reach over it any -* more: the divisions are by constants, as a division by a register gets -* a zero check in front, and the region sticks to one width, as a 32-bit -* result read by a 64-bit instruction gets a zero extension on the JITs -* which need one. The region is the not taken path and ends with a result -* different from the taken one, so a jump landing inside it fails the run. +* A jump with the maximal offset over insns that expand natively, through the +* JITs' long branch forms. The region must not grow in the verifier: one width +* and divisions by constants it keeps. A jump landing inside it fails the run. */ static void max_jmp (bool alu32,bool taken) {
@@ -2524,7 +2514,7 @@ static void max_jmp(bool alu32, bool taken)if (op ==BPF_DIV || op ==BPF_MOD ) insns[i++] = alu32 ?BPF_ALU32_IMM (op,BPF_REG_3 ,7 ) : -BPF_ALU64_IMM (op,BPF_REG_3 ,7 ); +BPF_ALU64_IMM (op,BPF_REG_3 ,-7 );else insns[i++] = alu32 ?BPF_ALU32_REG (op,BPF_REG_3 ,BPF_REG_2 ) :BPF_ALU64_REG (op,BPF_REG_3 ,BPF_REG_2 );
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 12/24 bpf, arm64: Consolidate the load and store emission into a helper
In reply to Daniel BorkmannThe BPF_LDX, BPF_ST and BPF_STX cases each repeat the frame pointer adjustment and the switch over the access size. Move that into a new emit_ldst() helper, and remove the A64_LDR*() and A64_STR*() macros that lose their last user. The emitted code is unchanged.
--- arch/arm64/net/bpf_jit.h | 17 --- arch/arm64/net/bpf_jit_comp.c | 230 +++++++++++----------------------- 2 files changed, 73 insertions(+), 174 deletions(-)
arch/arm64/net/bpf_jit.h +0 -17
@@ -62,16 +62,7 @@ AARCH64_INSN_LDST_##type##_REG_OFFSET)#define A64_LS_REG (Rt, Rn, Rm, size, type) \ A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type) -#define A64_STRB (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 8, STORE) -#define A64_LDRB (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 8, LOAD) -#define A64_LDRSB (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 8, SIGNED_LOAD) -#define A64_STRH (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 16, STORE) -#define A64_LDRH (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 16, LOAD) -#define A64_LDRSH (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 16, SIGNED_LOAD) -#define A64_STR32 (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, STORE)#define A64_LDR32 (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, LOAD) -#define A64_LDRSW (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 32, SIGNED_LOAD) -#define A64_STR64 (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, STORE)#define A64_LDR64 (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, LOAD)/* Load/store register (immediate offset) */
@@ -79,15 +70,7 @@aarch64_insn_gen_load_store_imm (Rt, Rn, imm, \ AARCH64_INSN_SIZE_##size, \ AARCH64_INSN_LDST_##type##_IMM_OFFSET) -#define A64_STRBI (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 8, STORE) -#define A64_LDRBI (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 8, LOAD) -#define A64_LDRSBI (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 8, SIGNED_LOAD) -#define A64_STRHI (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 16, STORE) -#define A64_LDRHI (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 16, LOAD) -#define A64_LDRSHI (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 16, SIGNED_LOAD) -#define A64_STR32I (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 32, STORE)#define A64_LDR32I (Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 32, LOAD) -#define A64_LDRSWI (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 32, SIGNED_LOAD)#define A64_STR64I (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, STORE)#define A64_LDR64I (Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, LOAD)
arch/arm64/net/bpf_jit_comp.c +73 -157
283 lines not on this page · raw message
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 13/24 bpf, arm64: Use the unscaled forms for negative and unaligned offsets
In reply to Daniel BorkmannA load or store with a negative offset, or with one that is not a multiple of the access size, needed a mov of the offset and the register offset form. LDUR and STUR take a signed 9-bit byte offset at the same latency. Use them for offsets from -256 to 255, which covers, for example, packet fields behind the Ethernet header.
Before/after for r0 = *(u32 *)(r1 + 26) and r0 = *(u64 *)(r1 - 16):
d280034a mov x10, #0x1a b86a6808 ldr w8, [x0, x10] b841a008 ldur w8, [x0, #26]
928001ea mov x10, #0xfffffffffffffff0 f86a6808 ldr x8, [x0, x10] f85f0008 ldur x8, [x0, #-16]
--- arch/arm64/net/bpf_jit_comp.c | 53 +++++++++++++++++++++++++++-------- 1 file changed, 41 insertions(+), 12 deletions(-)
arch/arm64/net/bpf_jit_comp.c +41 -12
@@ -365,6 +365,12 @@ static bool is_lsi_offset(int offset, int scale)return true; } +/* The unscaled forms take a signed 9-bit byte offset instead */ +static bool is_lsu_offset (int offset) +{ +return offset >= -SZ_256 && offset <SZ_256 ; +} +/* The A64 size of a BPF load or store, and the scale of its offset */ static enum aarch64_insn_size_type a64_ldst_size (const u8 code,int *scale) {
@@ -384,18 +390,36 @@ static enum aarch64_insn_size_type a64_ldst_size(const u8 code, int *scale) } } -/* The A64 type of a BPF load or store, in the immediate or register offset form */ -static enum aarch64_insn_ldst_type a64_ldst_type (const u8 code,bool reg_offset) -{ +/* The forms of a load or store: scaled unsigned immediate, unscaled, register offset */ +enum a64_ldst_form {A64_LDST_IMM ,A64_LDST_UNSCALED ,A64_LDST_REG }; + +/* The A64 type of a BPF load or store in the given form */ +static enum aarch64_insn_ldst_type a64_ldst_type (const u8 code,enum a64_ldst_form form) +{ +static const enum aarch64_insn_ldst_type types[][3 ] = { + [A64_LDST_IMM ] = { +AARCH64_INSN_LDST_LOAD_IMM_OFFSET , +AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET , +AARCH64_INSN_LDST_STORE_IMM_OFFSET , + }, + [A64_LDST_UNSCALED ] = { +AARCH64_INSN_LDST_LOAD_UNSCALED_IMM_OFFSET , +AARCH64_INSN_LDST_SIGNED_LOAD_UNSCALED_IMM_OFFSET , +AARCH64_INSN_LDST_STORE_UNSCALED_IMM_OFFSET , + }, + [A64_LDST_REG ] = { +AARCH64_INSN_LDST_LOAD_REG_OFFSET , +AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET , +AARCH64_INSN_LDST_STORE_REG_OFFSET , + }, + }; +if (BPF_CLASS (code) !=BPF_LDX ) -return reg_offset ?AARCH64_INSN_LDST_STORE_REG_OFFSET : -AARCH64_INSN_LDST_STORE_IMM_OFFSET ; +return types[form][2 ];if (BPF_MODE (code) ==BPF_MEMSX ||BPF_MODE (code) ==BPF_PROBE_MEMSX ||BPF_MODE (code) ==BPF_PROBE_MEM32SX ) -return reg_offset ?AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET : -AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET ; -return reg_offset ?AARCH64_INSN_LDST_LOAD_REG_OFFSET : -AARCH64_INSN_LDST_LOAD_IMM_OFFSET ; +return types[form][1 ]; +return types[form][0 ]; }/*
@@ -407,6 +431,7 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off, const u8 tmp, struct jit_ctx *ctx) { enum aarch64_insn_size_type size; +enum aarch64_insn_ldst_type type;s32 off_adj = off;u8 rn_adj = rn;int scale;
@@ -423,12 +448,16 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off, }if (is_lsi_offset (off_adj, scale)) { -emit (aarch64_insn_gen_load_store_imm (rt, rn_adj, off_adj, size, -a64_ldst_type (code, false)), ctx); + type =a64_ldst_type (code,A64_LDST_IMM ); +emit (aarch64_insn_gen_load_store_imm (rt, rn_adj, off_adj, size, type), ctx); + }else if (is_lsu_offset (off_adj)) { + type =a64_ldst_type (code,A64_LDST_UNSCALED ); +emit (aarch64_insn_gen_load_store_unscaled (rt, rn_adj, off_adj, size, type), ctx); }else { + type =a64_ldst_type (code,A64_LDST_REG );emit_a64_mov_i (1 , tmp, off, ctx);emit (aarch64_insn_gen_load_store_reg (rt, rn, tmp,AARCH64_INSN_EXTEND_UXTX , -0 , size,a64_ldst_type (code, true)), ctx); +0 , size, type), ctx); } }
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 14/24 bpf, arm64: Store zero immediates from the zero register
In reply to Daniel BorkmannA store of an immediate first moves it into a temporary, even when it is zero. Store a zero from xzr instead, which saves the mov. Zero stores are common: with cpu v4, LLVM emits runs of them to clear the stack slots of the structs and arrays that BPF programs pass to helpers.
Before/after for *(u64 *)(r10 - 8) = 0 with 16 bytes of stack:
d280000a mov x10, #0x0 f90007ea str x10, [sp, #8] f90007ff str xzr, [sp, #8]
--- arch/arm64/net/bpf_jit_comp.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
arch/arm64/net/bpf_jit_comp.c +4 -3
@@ -2121,9 +2121,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnemit (A64_ADD (1 , tmp3, dst, arena_vm_base), ctx); dst = tmp3; } -/* Load imm to a register then store it */ -emit_a64_mov_i (1 , tmp, imm, ctx); -emit_ldst (code, tmp, dst, off, tmp2, ctx); +/* A zero comes from the zero register, any other imm through a register */ +if (imm) +emit_a64_mov_i (1 , tmp, imm, ctx); +emit_ldst (code, imm ? tmp :A64_ZR , dst, off, tmp2, ctx); ret =add_exception_handler (insn, ctx,DONT_CLEAR );if (ret)
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 15/24 bpf, arm64: Zero extend the arena offset in register offset accesses
In reply to Daniel BorkmannAn arena access added the 32-bit arena offset register to the arena base with a 64-bit add. That relies on the verifier to keep the upper 32 bits zero, and any slip there would let the access escape the 4GB arena.
Use the register offset form with UXTW instead. It zero extends the offset as part of the access, which keeps the access within the arena and its guard pages. Without an immediate offset, this saves the add. With one, the add moves to the base, and an offset that does not fit the add immediate needs an extra mov.
The atomics and load-acquire/store-release have no register offset form. For them, add the arena offset to the base with UXTW instead.
Update the arm64 expectations of the Arena LDSX Disasm test in verifier_ldsx to the new form.
Before/after for r0 = *(u64 *)(r1 + 0) and r0 = *(u64 *)(r1 + 8) in the arena:
8b1c000b add x11, x0, x28 f9400168 ldr x8, [x11] f8604b88 ldr x8, [x28, w0, uxtw]
8b1c000b add x11, x0, x28 f9400568 ldr x8, [x11, #8] 9100238b add x11, x28, #0x8 f8604968 ldr x8, [x11, w0, uxtw]
--- arch/arm64/net/bpf_jit_comp.c | 90 +++++++++++++------ .../selftests/bpf/progs/verifier_ldsx.c | 24 ++--- 2 files changed, 75 insertions(+), 39 deletions(-)
arch/arm64/net/bpf_jit_comp.c +63 -27
@@ -461,6 +461,26 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off, } } +/* +* Load or store at the arena base, plus off added into tmp_addr, plus reg zero +* extended from 32 bits in the access, which keeps it in the arena and its +* guard whatever the upper bits of reg hold. +*/ +static void emit_arena_ldst (const u8 code,const u8 rt,const u8 reg,const s32 off, +const u8 tmp_addr,const u8 tmp,struct jit_ctx *ctx) +{ +u8 base = bpf2a64[ARENA_VM_START ]; +int scale; + +if (off) { +emit_a64_add_i (1 , tmp_addr, base, tmp, off, ctx); + base = tmp_addr; + } +emit (aarch64_insn_gen_load_store_reg (rt, base, reg,AARCH64_INSN_EXTEND_UXTW , +0 ,a64_ldst_size (code, &scale), +a64_ldst_type (code,A64_LDST_REG )), ctx); +} +/* generated main prog prologue: * bti c // if CONFIG_ARM64_BTI_KERNEL * mov x9, lr
@@ -846,6 +866,7 @@ static int emit_atomic_ld_st(const struct bpf_insn *insn, struct jit_ctx *ctx)const u8 dst = bpf2a64[insn->dst_reg];const u8 src = bpf2a64[insn->src_reg];const u8 tmp = bpf2a64[TMP_REG_1 ]; +const u8 tmp2 = bpf2a64[TMP_REG_2 ];u8 reg;switch (imm) {
@@ -860,12 +881,21 @@ static int emit_atomic_ld_st(const struct bpf_insn *insn, struct jit_ctx *ctx)return -EINVAL ; } -if (off) { -emit_a64_add_i (1 , tmp, reg, tmp, off, ctx); - reg = tmp; - } +/* +* The arena base with the offset first and the arena offset zero +* extended onto it, see emit_arena_ldst() +*/ if (arena) { -emit (A64_ADD (1 , tmp, reg, arena_vm_base), ctx); +u8 base = arena_vm_base; + +if (off) { +emit_a64_add_i (1 , tmp, base, tmp, off, ctx); + base = tmp; + } +emit (A64_ADD_UXTW (tmp2, base, reg), ctx); + reg = tmp2; + }else if (off) { +emit_a64_add_i (1 , tmp, reg, tmp, off, ctx); reg = tmp; }
@@ -919,17 +949,27 @@ static int emit_lse_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)const u8 src = bpf2a64[insn->src_reg];const u8 tmp = bpf2a64[TMP_REG_1 ];const u8 tmp2 = bpf2a64[TMP_REG_2 ]; +const u8 tmp3 = bpf2a64[TMP_REG_3 ];const bool isdw =BPF_SIZE (code) ==BPF_DW ;const bool arena =BPF_MODE (code) ==BPF_PROBE_ATOMIC ;const s16 off = insn->off;u8 reg = dst; -if (off) { -emit_a64_add_i (1 , tmp, reg, tmp, off, ctx); - reg = tmp; - } +/* +* The arena base with the offset first and the arena offset zero +* extended onto it, see emit_arena_ldst() +*/ if (arena) { -emit (A64_ADD (1 , tmp, reg, arena_vm_base), ctx); +u8 base = arena_vm_base; + +if (off) { +emit_a64_add_i (1 , tmp, base, tmp, off, ctx); + base = tmp; + } +emit (A64_ADD_UXTW (tmp3, base, reg), ctx); + reg = tmp3; + }else if (off) { +emit_a64_add_i (1 , tmp, reg, tmp, off, ctx); reg = tmp; }
@@ -1564,7 +1604,6 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnconst u8 tmp = bpf2a64[TMP_REG_1 ];const u8 tmp2 = bpf2a64[TMP_REG_2 ];const u8 tmp3 = bpf2a64[TMP_REG_3 ]; -const u8 arena_vm_base = bpf2a64[ARENA_VM_START ];const s16 off = insn->off;const s32 imm = insn->imm;const int i = insn - ctx->prog->insnsi;
@@ -2062,11 +2101,6 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insncase BPF_LDX |BPF_PROBE_MEM32SX |BPF_B :case BPF_LDX |BPF_PROBE_MEM32SX |BPF_H :case BPF_LDX |BPF_PROBE_MEM32SX |BPF_W : -if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 || -BPF_MODE (insn->code) ==BPF_PROBE_MEM32SX ) { -emit (A64_ADD (1 , tmp2, src, arena_vm_base), ctx); - src = tmp2; - } off_adj = off;if (BPF_MODE (insn->code) ==BPF_PROBE_MEM ||BPF_MODE (insn->code) ==BPF_PROBE_MEMSX ) {
@@ -2086,7 +2120,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnemit (A64_MOVZ (1 , dst,0 ,0 ), ctx);emit (A64_B (2 ), ctx); } -emit_ldst (code, dst, src, off_adj, tmp, ctx); +if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 || +BPF_MODE (insn->code) ==BPF_PROBE_MEM32SX ) +emit_arena_ldst (code, dst, src, off, tmp2, tmp, ctx); +else +emit_ldst (code, dst, src, off_adj, tmp, ctx); ret =add_exception_handler (insn, ctx, dst);if (ret)
@@ -2117,14 +2155,13 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insncase BPF_ST |BPF_PROBE_MEM32 |BPF_H :case BPF_ST |BPF_PROBE_MEM32 |BPF_W :case BPF_ST |BPF_PROBE_MEM32 |BPF_DW : -if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 ) { -emit (A64_ADD (1 , tmp3, dst, arena_vm_base), ctx); - dst = tmp3; - }/* A zero comes from the zero register, any other imm through a register */ if (imm)emit_a64_mov_i (1 , tmp, imm, ctx); -emit_ldst (code, imm ? tmp :A64_ZR , dst, off, tmp2, ctx); +if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 ) +emit_arena_ldst (code, imm ? tmp :A64_ZR , dst, off, tmp3, tmp2, ctx); +else +emit_ldst (code, imm ? tmp :A64_ZR , dst, off, tmp2, ctx); ret =add_exception_handler (insn, ctx,DONT_CLEAR );if (ret)
@@ -2145,11 +2182,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insncase BPF_STX |BPF_PROBE_MEM32 |BPF_H :case BPF_STX |BPF_PROBE_MEM32 |BPF_W :case BPF_STX |BPF_PROBE_MEM32 |BPF_DW : -if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 ) { -emit (A64_ADD (1 , tmp2, dst, arena_vm_base), ctx); - dst = tmp2; - } -emit_ldst (code, src, dst, off, tmp, ctx); +if (BPF_MODE (insn->code) ==BPF_PROBE_MEM32 ) +emit_arena_ldst (code, src, dst, off, tmp2, tmp, ctx); +else +emit_ldst (code, src, dst, off, tmp, ctx); ret =add_exception_handler (insn, ctx,DONT_CLEAR );if (ret)
tools/testing/selftests/bpf/progs/verifier_ldsx.c +12 -12
@@ -274,18 +274,18 @@ __jited("movslq 0x10(%rdi,%r12), %r15") __jited("movswq 0x18(%rdi,%r12), %r15") __jited("movsbq 0x20(%rdi,%r12), %r15") __arch_arm64 -__jited("add x11, x8, x28") -__jited("ldrsw x21, [x11, #0x10]") -__jited("add x11, x8, x28") -__jited("ldrsh x21, [x11, #0x18]") -__jited("add x11, x8, x28") -__jited("ldrsb x21, [x11, #0x20]") -__jited("add x11, x0, x28") -__jited("ldrsw x22, [x11, #0x10]") -__jited("add x11, x0, x28") -__jited("ldrsh x22, [x11, #0x18]") -__jited("add x11, x0, x28") -__jited("ldrsb x22, [x11, #0x20]") +__jited("add x11, x28, #0x10") +__jited("ldrsw x21, [x11, w8, uxtw]") +__jited("add x11, x28, #0x18") +__jited("ldrsh x21, [x11, w8, uxtw]") +__jited("add x11, x28, #0x20") +__jited("ldrsb x21, [x11, w8, uxtw]") +__jited("add x11, x28, #0x10") +__jited("ldrsw x22, [x11, w0, uxtw]") +__jited("add x11, x28, #0x18") +__jited("ldrsh x22, [x11, w0, uxtw]") +__jited("add x11, x28, #0x20") +__jited("ldrsb x22, [x11, w0, uxtw]") __arch_riscv64 __jited("add t2, t6, s7")__jited ("lw s3, 0x10(t2)" )
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 16/24 bpf, arm64: Adjust compares with unencodable immediates by one
In reply to Daniel Borkmanncmp and cmn take a 12-bit immediate, optionally shifted left by 12. LLVM turns x <= C into x < C + 1 and x >= C into x > C - 1, so a compare against a power of two reaches the JIT as one against a power of two plus one, or against a mask. Those often do not encode and needed a mov.
When the immediate does not encode but its neighbour C - 1 or C + 1 does, compare against the neighbour and adjust the condition. This covers <, <=, > and >=, both signed and unsigned.
Before/after for if r1 < 4097 goto ... and if r1 > 65535 goto ...:
d282002a mov x10, #0x1001 eb0a001f cmp x0, x10 54000043 b.lo ... f140041f cmp x0, #0x1, lsl #12 54000049 b.ls ...
d29fffea mov x10, #0xffff eb0a001f cmp x0, x10 54000048 b.hi ... f140401f cmp x0, #0x10, lsl #12 54000042 b.hs ...
--- arch/arm64/net/bpf_jit_comp.c | 83 ++++++++++++++++++++++++++++++++--- 1 file changed, 77 insertions(+), 6 deletions(-)
arch/arm64/net/bpf_jit_comp.c +77 -6
@@ -481,6 +481,73 @@ static void emit_arena_ldst(const u8 code, const u8 rt, const u8 reg, const s32 a64_ldst_type(code, A64_LDST_REG)), ctx); } +/* +* Compare against C - 1 or C + 1 with the adjusted condition when C does not +* encode, for the masks and powers of two plus one that LLVM's x >= C to +* x > C - 1 and x <= C to x < C + 1 bring here. +*/ +static bool adjust_cmp_imm (u8 *op,s32 *imm) +{ +s64 c = *imm; +u8 new_op; + +switch (*op) { +case BPF_JLT : +case BPF_JGE : +if (!c) +return false; + fallthrough; +case BPF_JSLT : +case BPF_JSGE : + c--; +break ; +case BPF_JGT : +case BPF_JLE : +if (c ==-1 ) +return false; + fallthrough; +case BPF_JSGT : +case BPF_JSLE : + c++; +break ; +default : +return false; + } +/* Past a signed limit the neighbor does not fit the 32-bit immediate */ +if (c != (s32 )c || (!is_addsub_imm (c) && !is_addsub_imm (-(u32 )c))) +return false; + +switch (*op) { +case BPF_JLT : + new_op =BPF_JLE ; +break ; +case BPF_JGE : + new_op =BPF_JGT ; +break ; +case BPF_JSLT : + new_op =BPF_JSLE ; +break ; +case BPF_JSGE : + new_op =BPF_JSGT ; +break ; +case BPF_JGT : + new_op =BPF_JGE ; +break ; +case BPF_JLE : + new_op =BPF_JLT ; +break ; +case BPF_JSGT : + new_op =BPF_JSGE ; +break ; +default : + new_op =BPF_JSLT ; +break ; + } + *op = new_op; + *imm = c; +return true; +} +/* generated main prog prologue: * bti c // if CONFIG_ARM64_BTI_KERNEL * mov x9, lr
@@ -1609,6 +1676,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnconst int i = insn - ctx->prog->insnsi;const bool is64 =BPF_CLASS (code) ==BPF_ALU64 ||BPF_CLASS (code) ==BPF_JMP ; +u8 jmp_op =BPF_OP (code); +s32 cmp_imm = imm;u8 jmp_cond;s32 jmp_offset;u32 a64_insn;
@@ -1886,7 +1955,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn emit_cond_jmp: jmp_offset =bpf2a64_offset (i, off, ctx);check_imm19 (jmp_offset); -switch (BPF_OP (code)) { +switch (jmp_op) {case BPF_JEQ : jmp_cond =A64_COND_EQ ;break ;
@@ -1948,12 +2017,14 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insncase BPF_JMP32 |BPF_JSLT |BPF_K :case BPF_JMP32 |BPF_JSGE |BPF_K :case BPF_JMP32 |BPF_JSLE |BPF_K : -if (is_addsub_imm (imm)) { -emit (A64_CMP_I (is64, dst, imm), ctx); - }else if (is_addsub_imm (-(u32 )imm)) { -emit (A64_CMN_I (is64, dst, -imm), ctx); +if (!is_addsub_imm (imm) && !is_addsub_imm (-(u32 )imm)) +adjust_cmp_imm (&jmp_op, &cmp_imm); +if (is_addsub_imm (cmp_imm)) { +emit (A64_CMP_I (is64, dst, cmp_imm), ctx); + }else if (is_addsub_imm (-(u32 )cmp_imm)) { +emit (A64_CMN_I (is64, dst, -cmp_imm), ctx); }else { -emit_a64_mov_i (is64, tmp, imm, ctx); +emit_a64_mov_i (is64, tmp, cmp_imm, ctx);emit (A64_CMP (is64, dst, tmp), ctx); } goto emit_cond_jmp;
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 17/24 bpf, arm64: Materialize immediates with fewer instructions
In reply to Daniel BorkmannA 32-bit immediate with a zero or all-ones low half often took two moves where a single shifted movz or movn does. A bitmask immediate, 32 or 64 bits, took two or more moves where a single orr does.
A 64-bit immediate with a repeated 16-bit chunk now takes one orr of that chunk replicated, if that is a bitmask immediate, plus a movk for each other chunk. The verifier's magic numbers for dividing by 3, 5, 15 and 17 have that form.
Before/after for w1 = 0x10000, r1 = 0x7fffffff, r1 = 0xffffffff00000000 ll and r1 = 0xcccccccccccccccd ll:
52800000 mov w0, #0x0 72a00020 movk w0, #0x1, lsl #16 52a00020 mov w0, #0x10000
d29fffe0 mov x0, #0xffff f2afffe0 movk x0, #0x7fff, lsl #16 b2407be0 mov x0, #0x7fffffff
d2ffffe0 mov x0, #0xffff000000000000 f2dfffe0 movk x0, #0xffff, lsl #32 b2607fe0 mov x0, #0xffffffff00000000
d2f99980 mov x0, #0xcccc000000000000 f2d99980 movk x0, #0xcccc, lsl #32 f2b99980 movk x0, #0xcccc, lsl #16 f29999a0 movk x0, #0xcccd b202e7e0 mov x0, #0xcccccccccccccccc f29999a0 movk x0, #0xcccd
--- arch/arm64/net/bpf_jit_comp.c | 75 ++++++++++++++++++++++++++++++----- 1 file changed, 65 insertions(+), 10 deletions(-)
arch/arm64/net/bpf_jit_comp.c +65 -10
@@ -125,24 +125,47 @@ static inline void emit_u32_data(const u32 data, struct jit_ctx *ctx) ctx->idx++; } +/* +* A 32-bit immediate, sign extended for the 64-bit variant: one movz, movn or +* orr where one encodes it, else a movz or movn and a movk. +*/ static inline void emit_a64_mov_i (const int is64,const int reg,const s32 val,struct jit_ctx *ctx) {u16 hi = val >>16 ;u16 lo = val &0xffff ; +u32 insn; + +if (hi ==0xffff ) { +emit (A64_MOVN (is64, reg, (u16 )~lo,0 ), ctx); +return ; + } +if (!hi) { +emit (A64_MOVZ (is64, reg, lo,0 ), ctx); +return ; + } +/* The 64-bit variant has the upper half set or clear with the sign */ +if (!lo && (!is64 || !(hi &0x8000 ))) { +emit (A64_MOVZ (is64, reg, hi,16 ), ctx); +return ; + } +if (lo ==0xffff && (!is64 || (hi &0x8000 ))) { +emit (A64_MOVN (is64, reg, (u16 )~hi,16 ), ctx); +return ; + } + + insn =A64_ORR_I (is64, reg,A64_ZR , val); +if (insn !=AARCH64_BREAK_FAULT ) { +emit (insn, ctx); +return ; + }if (hi &0x8000 ) { -if (hi ==0xffff ) { -emit (A64_MOVN (is64, reg, (u16 )~lo,0 ), ctx); - }else { -emit (A64_MOVN (is64, reg, (u16 )~hi,16 ), ctx); -if (lo !=0xffff ) -emit (A64_MOVK (is64, reg, lo,0 ), ctx); - } +emit (A64_MOVN (is64, reg, (u16 )~hi,16 ), ctx); +emit (A64_MOVK (is64, reg, lo,0 ), ctx); }else {emit (A64_MOVZ (is64, reg, lo,0 ), ctx); -if (hi) -emit (A64_MOVK (is64, reg, hi,16 ), ctx); +emit (A64_MOVK (is64, reg, hi,16 ), ctx); } }
@@ -170,10 +193,42 @@ static inline void emit_a64_mov_i64(const int reg, const u64 val, {u64 nrm_tmp = val, rev_tmp = ~val;bool inverse; -int shift; +u32 insn; +int shift, blocks;if (!(nrm_tmp >>32 ))return emit_a64_mov_i (0 , reg, (u32 )val, ctx); +if ((s64 )(s32 )val == (s64 )val) +return emit_a64_mov_i (1 , reg, (s32 )val, ctx); + +/* A bitmask immediate in a single orr */ + insn =A64_ORR_I (1 , reg,A64_ZR , val); +if (insn !=AARCH64_BREAK_FAULT ) +return emit (insn, ctx); + +/* +* A 16-bit chunk occurring more than once whose replication is a +* bitmask immediate comes from one orr, with a movk for each of +* the other chunks, when that beats the moves of the chunks. +*/ + blocks =min (i64_i16_blocks (nrm_tmp, true),i64_i16_blocks (nrm_tmp, false)); +for (shift =0 ; shift <64 ; shift +=16 ) { +u16 chunk = val >> shift; +int i, n =0 ; + +for (i =0 ; i <64 ; i +=16 ) + n += (u16)(val >> i) == chunk; +if (n <2 ||1 +4 - n >= blocks) +continue ; + insn =A64_ORR_I (1 , reg,A64_ZR , chunk *0x0001000100010001ULL ); +if (insn ==AARCH64_BREAK_FAULT ) +continue ; +emit (insn, ctx); +for (i =0 ; i <64 ; i +=16 ) +if ((u16)(val >> i) != chunk) +emit (A64_MOVK (1 , reg, (u16)(val >> i), i), ctx); +return ; + } inverse =i64_i16_blocks (nrm_tmp, true) <i64_i16_blocks (nrm_tmp, false); shift = max(round_down((inverse ? (fls64(rev_tmp) - 1) :
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 18/24 bpf, arm64: Shorten the tail call sequence
In reply to Daniel BorkmannThe tail call sequence moved the offsets of max_entries, ptrs and bpf_func, and the tail call limit, into a temporary first, although they all fit the immediate forms. It also zero extended and shifted the index in separate instructions before the load. Use the immediate forms and a register offset load with UXTW #3 instead.
That saves six instructions per tail call. A64_LDR64() loses its last user and is removed.
Before/after for the checks and the lookup of a tail call:
5280088a mov w10, #0x44 b86a682a ldr w10, [x1, x10] 2a0203e2 mov w2, w2 6b0a005f cmp w2, w10 54000282 b.hs ... 5280042a mov w10, #0x21 f940034c ldr x12, [x26] eb0a019f cmp x12, x10 54000202 b.hs ... 9100058c add x12, x12, #0x1 5280440a mov w10, #0x220 8b0a002a add x10, x1, x10 d37df04b lsl x11, x2, #3 f86b694b ldr x11, [x10, x11] b400014b cbz x11, ...
b940442a ldr w10, [x1, #68] 6b0a005f cmp w2, w10 54000202 b.hs ... f940034c ldr x12, [x26] f100859f cmp x12, #0x21 540001a2 b.hs ... 9100058c add x12, x12, #0x1 9108802a add x10, x1, #0x220 f862594b ldr x11, [x10, w2, uxtw #3] b400012b cbz x11, ...
--- arch/arm64/net/bpf_jit.h | 3 ++- arch/arm64/net/bpf_jit_comp.c | 27 +++++++++++++++------------ 2 files changed, 17 insertions(+), 13 deletions(-)
arch/arm64/net/bpf_jit.h +2 -1
@@ -63,7 +63,8 @@#define A64_LS_REG (Rt, Rn, Rm, size, type) \ A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type)#define A64_LDR32 (Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, LOAD) -#define A64_LDR64 (Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, LOAD) +/* Xt = *(Xn + ((u32)Wm << 3)) */ +#define A64_LDR64_UXTW3 (Xt, Xn, Wm) A64_LS_REG_EXT(Xt, Xn, Wm, UXTW, 3, 64, LOAD)/* Load/store register (immediate offset) */ #define A64_LS_IMM (Rt, Rn, imm, size, type) \
arch/arm64/net/bpf_jit_comp.c +15 -12
@@ -909,13 +909,20 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)__le32 *branch2 =NULL ;__le32 *branch3 =NULL ; -/* if (index >= array->map.max_entries) +/* The struct offsets fit the immediate forms, the count fits cmp */ + BUILD_BUG_ON(offsetof(struct bpf_array, map.max_entries) % 4 || + offsetof(struct bpf_array, map.max_entries) > 0xfff * 4); +BUILD_BUG_ON (offsetof(struct bpf_array , ptrs) >0xfff ); +BUILD_BUG_ON (offsetof(struct bpf_prog , bpf_func) %8 || + offsetof(struct bpf_prog , bpf_func) >0xfff *8 ); +BUILD_BUG_ON (MAX_TAIL_CALL_CNT >0xfff ); + +/* +* if ((u32)index >= array->map.max_entries) * goto out; */ off = offsetof(struct bpf_array, map.max_entries); -emit_a64_mov_i64 (tmp, off, ctx); -emit (A64_LDR32 (tmp, r2, tmp), ctx); -emit (A64_MOV (0 , r3, r3), ctx); +emit (A64_LDR32I (tmp, r2, off), ctx);emit (A64_CMP (0 , r3, tmp), ctx); branch1 = ctx->image + ctx->idx;emit (A64_NOP , ctx);
@@ -924,9 +931,8 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)* if ((*tail_call_cnt_ptr) >= MAX_TAIL_CALL_CNT) * goto out; */ -emit_a64_mov_i64 (tmp,MAX_TAIL_CALL_CNT , ctx);emit (A64_LDR64I (tcc, ptr,0 ), ctx); -emit (A64_CMP (1 , tcc, tmp), ctx); +emit (A64_CMP_I (1 , tcc,MAX_TAIL_CALL_CNT ), ctx); branch2 = ctx->image + ctx->idx;emit (A64_NOP , ctx);
@@ -938,10 +944,8 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)* goto out; */ off = offsetof(struct bpf_array , ptrs); -emit_a64_mov_i64 (tmp, off, ctx); -emit (A64_ADD (1 , tmp, r2, tmp), ctx); -emit (A64_LSL (1 , prg, r3,3 ), ctx); -emit (A64_LDR64 (prg, tmp, prg), ctx); +emit (A64_ADD_I (1 , tmp, r2, off), ctx); +emit (A64_LDR64_UXTW3 (prg, tmp, r3), ctx); branch3 = ctx->image + ctx->idx;emit (A64_NOP , ctx);
@@ -959,8 +963,7 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)/* goto *(prog->bpf_func + prologue_offset); */ off = offsetof(struct bpf_prog , bpf_func); -emit_a64_mov_i64 (tmp, off, ctx); -emit (A64_LDR64 (tmp, prg, tmp), ctx); +emit (A64_LDR64I (tmp, prg, off), ctx);emit (A64_ADD_I (1 , tmp, tmp,sizeof (u32) *PROLOGUE_OFFSET ), ctx);emit (A64_BR (tmp), ctx);
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 19/24 bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones
In reply to Daniel BorkmannThe logical immediate forms cannot encode all ones, so AND, OR and XOR with -1 moved the constant into a temporary first. The XOR is common, as LLVM lowers every bitwise NOT to r ^= -1.
Emit an mvn for the XOR and a mov of -1 for the OR. For the AND, emit a 32-bit mov to zero extend the 32-bit variant, and nothing for the 64-bit one.
Before/after for w1 &= -1 and w1 ^= -1:
1280000a mov w10, #0xffffffff 0a0a0000 and w0, w0, w10 2a0003e0 mov w0, w0
1280000a mov w10, #0xffffffff 4a0a0000 eor w0, w0, w10 2a2003e0 mvn w0, w0
--- arch/arm64/net/bpf_jit_comp.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
arch/arm64/net/bpf_jit_comp.c +16 -0
@@ -1911,6 +1911,12 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnbreak ;case BPF_ALU |BPF_AND |BPF_K :case BPF_ALU64 |BPF_AND |BPF_K : +/* All ones only zero extends the 32-bit variant */ +if (imm ==-1 ) { +if (!is64) +emit (A64_MOV (0 , dst, dst), ctx); +break ; + } a64_insn =A64_AND_I (is64, dst, dst, imm);if (a64_insn !=AARCH64_BREAK_FAULT ) {emit (a64_insn, ctx);
@@ -1921,6 +1927,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnbreak ;case BPF_ALU |BPF_OR |BPF_K :case BPF_ALU64 |BPF_OR |BPF_K : +/* The or with all ones is the move of -1 */ +if (imm ==-1 ) { +emit (A64_MOVN (is64, dst,0 ,0 ), ctx); +break ; + } a64_insn =A64_ORR_I (is64, dst, dst, imm);if (a64_insn !=AARCH64_BREAK_FAULT ) {emit (a64_insn, ctx);
@@ -1931,6 +1942,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insnbreak ;case BPF_ALU |BPF_XOR |BPF_K :case BPF_ALU64 |BPF_XOR |BPF_K : +/* The xor with all ones is the not */ +if (imm ==-1 ) { +emit (A64_MVN (is64, dst, dst), ctx); +break ; + } a64_insn =A64_EOR_I (is64, dst, dst, imm);if (a64_insn !=AARCH64_BREAK_FAULT ) {emit (a64_insn, ctx);
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 20/24 bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests
In reply to Daniel BorkmannA compare against zero for equality, a sign test and a single-bit test each took a cmp or tst followed by a b.cond. CBZ/CBNZ and TBZ/TBNZ do each in one instruction. That saves code size and a decode slot, and also a uop on cores that do not fuse the pair. Null checks and sign tests are the most frequent compares in BPF programs.
TBZ and TBNZ only reach +/-8K instructions, so a test uses them only when its target is within reach in the sizing pass. The sizing pass has the longest layout of all passes, the extra pass included, so the target then stays in reach. The decisions are kept in a bitmap.
Before/after for if r0 == 0 goto ..., if w0 s< 0 goto ... and if r1 & 0x8 goto ...:
f100011f cmp x8, #0x0 54000040 b.eq ... b4000048 cbz x8, ...
7100011f cmp w8, #0x0 5400004b b.lt ... 37f80048 tbnz w8, #0x1f, ...
f27d001f tst x0, #0x8 54000041 b.ne ... 37180040 tbnz w0, #0x3, ...
--- arch/arm64/net/bpf_jit.h | 9 +++ arch/arm64/net/bpf_jit_comp.c | 116 ++++++++++++++++++++++++++++++++++ 2 files changed, 125 insertions(+)
arch/arm64/net/bpf_jit.h +9 -0
@@ -30,6 +30,15 @@#define A64_CBNZ (sf, Rt, imm19) \ A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), NONZERO) +/* Test bit & branch (immediate) */ +#define A64_TEST_BRANCH (Rt, bit, offset, type) \ + aarch64_insn_gen_test_branch_imm(0, offset, Rt, bit, \ + AARCH64_INSN_BRANCH_TEST_##type) +#define A64_TBZ (Rt, bit, imm14) \ + A64_TEST_BRANCH(Rt, bit, A64_BR_OFF(imm14), ZERO) +#define A64_TBNZ (Rt, bit, imm14) \ + A64_TEST_BRANCH(Rt, bit, A64_BR_OFF(imm14), NONZERO) +/* Conditional branch (immediate) */ #define A64_COND_BRANCH (cond, offset) \ aarch64_insn_gen_cond_branch_imm(0, offset, cond)
arch/arm64/net/bpf_jit_comp.c +116 -0
170 lines not on this page · raw message
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 21/24 bpf, arm64: Multiply by constants with shifts, adds and subs
In reply to Daniel BorkmannLLVM leaves a multiplication by a constant other than a power of two as is, and the JIT emitted it as a mov of the constant and a mul of two to four cycles.
For constants of the form 2^n, 2^n + 1 or 2^n - 1, optionally negated or multiplied by 2^m, emit at most two shifts, adds or subs instead. Only sequences of at most two cycles are used, so they are never slower than the mul.
A multiplication by 0 becomes a mov, by -1 a neg, and by 1 nothing beyond the zero extension of the 32-bit variant.
Before/after for r1 *= 3, r1 *= 7 and r1 *= 24:
d280006a mov x10, #0x3 9b0a7c00 mul x0, x0, x10 8b000400 add x0, x0, x0, lsl #1
d28000ea mov x10, #0x7 9b0a7c00 mul x0, x0, x10 d37df00a lsl x10, x0, #3 cb000140 sub x0, x10, x0
d280030a mov x10, #0x18 9b0a7c00 mul x0, x0, x10 8b000400 add x0, x0, x0, lsl #1 d37df000 lsl x0, x0, #3
--- arch/arm64/net/bpf_jit.h | 12 ++++- arch/arm64/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++++++++++- 2 files changed, 94 insertions(+), 4 deletions(-)
arch/arm64/net/bpf_jit.h +10 -2
@@ -227,11 +227,19 @@#define A64_MOVK (sf, Rd, imm16, shift) A64_MOVEW(sf, Rd, imm16, shift, KEEP)/* Add/subtract (shifted register) */ -#define A64_ADDSUB_SREG (sf, Rd, Rn, Rm, type) \ - aarch64_insn_gen_add_sub_shifted_reg(Rd, Rn, Rm, 0, \ +#define A64_ADDSUB_SHIFT (sf, Rd, Rn, Rm, shift, type) \ + aarch64_insn_gen_add_sub_shifted_reg(Rd, Rn, Rm, shift, \ A64_VARIANT(sf), AARCH64_INSN_ADSB_##type) +#define A64_ADDSUB_SREG (sf, Rd, Rn, Rm, type) \ + A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, 0, type)/* Rd = Rn OP Rm */ #define A64_ADD (sf, Rd, Rn, Rm) A64_ADDSUB_SREG(sf, Rd, Rn, Rm, ADD) +/* Rd = Rn + (Rm << shift) */ +#define A64_ADD_LSL (sf, Rd, Rn, Rm, shift) \ + A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, shift, ADD) +/* Rd = Rn - (Rm << shift) */ +#define A64_SUB_LSL (sf, Rd, Rn, Rm, shift) \ + A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, shift, SUB)#define A64_SUB (sf, Rd, Rn, Rm) A64_ADDSUB_SREG(sf, Rd, Rn, Rm, SUB)#define A64_SUBS (sf, Rd, Rn, Rm) A64_ADDSUB_SREG(sf, Rd, Rn, Rm, SUB_SETFLAGS)/* Rd = -Rm */
arch/arm64/net/bpf_jit_comp.c +84 -2
98 lines not on this page · raw message
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 22/24 selftests/bpf: Let the arm64 private stack check skip the BTI pad
In reply to Daniel BorkmannWith CONFIG_ARM64_BTI_KERNEL, which is the default with clang before 21, the JIT emits a BTI J landing pad between the tail call counter setup and the push of the callee-saved registers. The arm64 expectations of the "Private stack, exception in main prog" test want the push right after the setup, so the test fails:
WRONG LINE SUBSTR: ' stp x19, x20, [sp, #-0x10]!'
expecting match at line 9, actual match is at line 10
Let the expectation skip lines between the two, as other tests in the same file already do.
--- tools/testing/selftests/bpf/progs/verifier_private_stack.c | 1 + 1 file changed, 1 insertion(+)
tools/testing/selftests/bpf/progs/verifier_private_stack.c +1 -0
@@ -286,6 +286,7 @@ __jited(" stp x29, x30, [sp, #-0x10]!") __jited(" mov x29, sp") __jited(" stp xzr, x26, [sp, #-0x10]!") __jited(" mov x26, sp") +__jited("...") __jited(" stp x19, x20, [sp, #-0x10]!") __jited(" stp x21, x22, [sp, #-0x10]!")__jited (" stp x23, x24, [sp, #-0x10]!" )
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 23/24 selftests/bpf: Test the verifier's division by constants
In reply to Daniel BorkmannOn the JITs that support UHMUL and SHMUL, check the uhmul and shmul sequences that the verifier rewrites 64-bit divisions by a constant into, one test per sequence shape, and the modulos that keep the division. The results of the rewritten sequences are checked by jit_insns' div_const.
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_div_const.c | 225 ++++++++++++++++++ 2 files changed, 227 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_div_const.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -55,6 +55,7 @@#include "verifier_direct_packet_access.skel.h" #include "verifier_direct_stack_access_wraparound.skel.h" #include "verifier_div0.skel.h" +#include "verifier_div_const.skel.h" #include "verifier_div_mod_bounds.skel.h" #include "verifier_div_overflow.skel.h" #include "verifier_flow_keys.skel.h"
@@ -263,6 +264,7 @@ void test_verifier_default_trusted_ptr(void) { RUN_TESTS(verifier_default_trustvoid test_verifier_direct_packet_access (void ) {RUN (verifier_direct_packet_access); }void test_verifier_direct_stack_access_wraparound (void ) {RUN (verifier_direct_stack_access_wraparound); }void test_verifier_div0 (void ) {RUN (verifier_div0); } +void test_verifier_div_const (void ) {RUN (verifier_div_const); }void test_verifier_div_mod_bounds (void ) {RUN (verifier_div_mod_bounds); }void test_verifier_div_overflow (void ) {RUN (verifier_div_overflow); }void test_verifier_flow_keys (void ) {RUN (verifier_flow_keys); }
tools/testing/selftests/bpf/progs/verifier_div_const.c new file +225 -0
225 lines not on this page · raw message
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v3 24/24 selftests/bpf: Extend the JIT instruction tests for arm64 encodings
In reply to Daniel BorkmannCover the sequences that the arm64 JIT now emits: compares, bit tests, constant arithmetic, immediates, sign jumps across the short branch reach (also with a subprog call in between), arena and PROBE_MEM addresses, and the tail call. The tests check the results, so they apply to every JIT.
far_back_jump puts loops behind 52500 helper calls. In the arm64 sizing pass this places them more than 1MB into the image, where a branch back used to fail the JIT.
The arena atomics are only guarded at build time. On an arm64 CPU without LSE, the kernel rejects them at load time, as the ll/sc atomics have no arena support yet, so their subtests fail there on purpose.
# PLATFORM=aarch64 CROSS_COMPILE=aarch64-linux-gnu- ./vmtest.sh -- ./test_progs -t jit_insns [...]
#200/1 jit_insns/arena_zero_off:OK #200/2 jit_insns/cast_to_user:OK #200/3 jit_insns/arena_offsets:OK #200/4 jit_insns/arena_offsets_ldsx:OK #200/5 jit_insns/arena_offsets_atomics:OK #200/6 jit_insns/arena_acq_rel:OK #200/7 jit_insns/alu_imm:OK #200/8 jit_insns/alu_reg:OK #200/9 jit_insns/alu_imm_regs:OK #200/10 jit_insns/div_const:OK #200/11 jit_insns/alu_reg_pairs:OK #200/12 jit_insns/alu_edges:OK #200/13 jit_insns/shifts:OK #200/14 jit_insns/shift_counts:OK #200/15 jit_insns/atomics:OK #200/16 jit_insns/atomic_reg_pairs:OK #200/17 jit_insns/xadd_chain:OK #200/18 jit_insns/ld_imm64:OK #200/19 jit_insns/jmp_imm:OK #200/20 jit_insns/jmp_reg:OK #200/21 jit_insns/jmp_reg_pairs:OK #200/22 jit_insns/jmp_edges:OK #200/23 jit_insns/staggered_jumps:OK #200/24 jit_insns/max_jmp:OK #200/25 jit_insns/sign_jumps:OK #200/26 jit_insns/convergence:OK #200/27 jit_insns/same_len_not_converged:OK #200/28 jit_insns/far_back_jump:OK #200/29 jit_insns/calls:OK #200/30 jit_insns/helper_calls:OK #200/31 jit_insns/tail_call:OK #200/32 jit_insns/ldst_zero_off:OK #200/33 jit_insns/ldst_offsets:OK #200/34 jit_insns/acq_rel:OK #200/35 jit_insns/atomic_ptr_operand:OK #200/36 jit_insns/movsx:OK #200/37 jit_insns/jset_imm:OK #200/38 jit_insns/cmp_imm:OK #200/39 jit_insns/alu_consts:OK #200/40 jit_insns/bswap:OK #200/41 jit_insns/probe_mem:OK #200 jit_insns:OK #201/1 jit_insns_blinded/alu_imm:OK #201/2 jit_insns_blinded/alu_imm_regs:OK #201/3 jit_insns_blinded/alu_edges:OK #201/4 jit_insns_blinded/div_const:OK #201/5 jit_insns_blinded/shifts:OK #201/6 jit_insns_blinded/xadd_chain:OK #201/7 jit_insns_blinded/ld_imm64:OK #201/8 jit_insns_blinded/jmp_imm:OK #201/9 jit_insns_blinded/jmp_edges:OK #201/10 jit_insns_blinded/ldst_zero_off:OK #201/11 jit_insns_blinded/ldst_offsets:OK #201/12 jit_insns_blinded/jset_imm:OK #201/13 jit_insns_blinded/cmp_imm:OK #201/14 jit_insns_blinded/alu_consts:OK #201 jit_insns_blinded:OK
Summary: 2/55 PASSED, 0 SKIPPED, 0/0 FAILED
--- .../selftests/bpf/prog_tests/jit_insns.c | 727 ++++++++++++++++-- .../selftests/bpf/progs/jit_insns_arena.c | 446 ++++++++++- 2 files changed, 1109 insertions(+), 64 deletions(-)
tools/testing/selftests/bpf/prog_tests/jit_insns.c +664 -63
@@ -588,13 +588,14 @@ static void test_alu_imm_regs(void)* The dividends of the 32-bit operations carry garbage in the upper half. */ static const __s32 unsigned_divisors[] = { -2 ,3 ,7 ,10 ,25 ,641 ,1000 ,4096 ,65536 ,1000000007 ,0x7fffffff , --2 ,-10 ,-0x7fffffff -1 ,-1 ,1 , +2 ,3 ,7 ,10 ,14 ,25 ,56 ,641 ,1000 ,4096 ,65536 ,0x40000000 ,1000000007 , +0x7fffffff ,-2 ,-10 ,-0x7fffffff -1 ,-1 ,1 , };static const __s32 signed_divisors[] = { -2 ,3 ,7 ,25 ,1000 ,0x40000000 ,0x7fffffff , --2 ,-3 ,-5 ,-7 ,-1000 ,-0x7fffffff ,-0x7fffffff -1 ,1 ,-1 , +2 ,3 ,4 ,7 ,8 ,25 ,1000 ,0x80000 ,0x40000000 ,0x7fffffff , +-2 ,-3 ,-4 ,-5 ,-7 ,-8 ,-1000 ,-0x40000000 ,-0x7fffffff ,-0x7fffffff -1 , +1 ,-1 , };static int dividends (__u32 flags,__s32 imm,__u64 *n)
@@ -1119,7 +1120,8 @@ static void test_ld_imm64(void)static const __u64 imms[] = {0 ,1 ,0x7fffffff ,0x80000000 ,0xffffffff ,0x100000000ULL ,0xffffffffffffffffULL ,0xffffffff80000000ULL ,0xffffffff7fffffffULL , -0x0123456789abcdefULL , +0x0123456789abcdefULL ,0xcccccccccccccccdULL ,0x5a5a12345a5a5a5aULL , +0x5a5a00005a5affffULL ,0x00ff00ff00ff00ffULL ,0x1234567812345678ULL , };int block =64 , bit, adj, sign, p, pattern, index, rd, i;struct batch b;
@@ -1467,6 +1469,10 @@ static void test_staggered_jumps(void) BPF_JMP32_IMM(BPF_JLT, BPF_REG_1, 0x80000000, 0), 1234, 0 }, {"staggered jmp32_jsge_x" , BPF_JMP32_REG(BPF_JSGE, BPF_REG_1, BPF_REG_2, 0), -2, -2 }, + { "staggered jmp_jeq_k zero", + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 0), 0, 0 }, + { "staggered jmp_jslt_k zero", + BPF_JMP_IMM(BPF_JSLT, BPF_REG_1, 0, 0), -1, 0 }, };char desc[64 ];int i, d;
@@ -1515,7 +1521,7 @@ static const __u64 inputs[] = { };struct prog { -struct bpf_insn insns[16 ]; +struct bpf_insn insns[32 ];int cnt; };
@@ -1568,7 +1574,7 @@ static void test_ldst_zero_off(void)static const int aops[] = {BPF_ADD ,BPF_ADD |BPF_FETCH ,BPF_OR ,BPF_XCHG ,BPF_CMPXCHG , }; -static const __s32 imms[] = {0x5a ,-1 }; +static const __s32 imms[] = {0x5a ,-1 ,0 };struct prog p;char desc[64 ];int b, k, s, j, fd;
@@ -1645,12 +1651,13 @@ static void test_ldst_zero_off(void)close (fd); } -/* Store an immediate with a zero offset into a zeroed stack slot */ +/* Store an immediate with a zero offset over in0 in a stack slot */ for (k =0 ; k <ARRAY_SIZE (imms); k++) {int rd =pair_reg (b,1 );prog_start (&p); -EMIT (&p,BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 )); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN0 )); +EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rd,-8 ));EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 ));EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 ));EMIT (&p,BPF_ST_MEM (size, rb,0 , imms[k]));
@@ -1661,8 +1668,10 @@ static void test_ldst_zero_off(void) fd =prog_load (&p, desc);if (fd <0 )return ; -prog_run (fd,0 ,0 , -head_merge (0 , (__u64 )(__s64 )imms[k], size), desc); +for (j =0 ; j <ARRAY_SIZE (inputs); j++) +prog_run (fd, inputs[j],0 , +head_merge (inputs[j], (__u64 )(__s64 )imms[k], size), + desc);close (fd); }
@@ -1755,11 +1764,20 @@ static int offsets_for(int size, bool unaligned, int *off) off[cnt++] =-128 ; off[cnt++] =-128 - n; off[cnt++] =-256 ; + off[cnt++] =-256 - n; off[cnt++] =-4096 ; off[cnt++] = -MEM_BASE ; +/* The last offset of the scaled form and the first past it, 4095 to 16384 */ +if (n <8 ) + off[cnt++] =0xfff * n; +if (n >1 && n <8 ) + off[cnt++] =0x1000 * n;if (n >1 && unaligned) { off[cnt++] =13 ; off[cnt++] =127 ; + off[cnt++] =255 ; + off[cnt++] =257 ; + off[cnt++] =-257 ; off[cnt++] =-13 ; off[cnt++] =-129 ; }
@@ -1971,7 +1989,7 @@ static void store_offsets(struct off_mem *m, int size, int rb, int rd, __s32 immstatic void test_ldst_offsets (void ) {static const int sizes[] = {BPF_B ,BPF_H ,BPF_W ,BPF_DW }; -static const __s32 imms[] = {-1 ,0x7fffffff ,-0x7fffffff -1 }; +static const __s32 imms[] = {0 ,-1 ,0x7fffffff ,-0x7fffffff -1 };int b, k, s, i, nr, off[32 ];struct off_mem m = {};bool unaligned;
@@ -2084,7 +2102,8 @@ static void jmp_prog(struct prog *p, bool is64, int op, int d, __s32 imm, int ofstatic void test_jset_imm (void ) {static const __s32 masks[] = { -0x1 ,0x40 ,0x80 ,0xff ,0x100 ,0x7fff ,0x7fffffff ,-1 ,-0x7fffffff -1 , +0x1 ,0x2 ,0x40 ,0x80 ,0xff ,0x100 ,0x7fff ,0x8000 ,0x10000 ,0x7fffffff , +0x40000000 ,-1 ,-0x7fffffff -1 , };struct prog p;char desc[64 ];
@@ -2096,14 +2115,19 @@ static void test_jset_imm(void)for (is64 = false; ; is64 = true) {for (m =0 ; m <ARRAY_SIZE (masks); m++) { +__u64 mk = is64 ? (__u64 )(__s64 )masks[m] : (__u32 )masks[m]; +/* The mask, its complement and its neighbors pin a single bit */ +__u64 vals[ARRAY_SIZE (inputs) +4 ] = { mk, ~mk, mk <<1 , mk >>1 }; + +memcpy (vals +4 , inputs,sizeof (inputs));jmp_prog (&p, is64,BPF_JSET , d, masks[m],1 );snprintf (desc,sizeof (desc),"jset%d dst=r%d mask=0x%x" , is64 ?64 :32 , rd, masks[m]); fd =prog_load (&p, desc);if (fd <0 )return ; -for (j =0 ; j <ARRAY_SIZE (inputs); j++) { -__u64 v = inputs[j]; +for (j =0 ; j <ARRAY_SIZE (vals); j++) { +__u64 v = vals[j];bool taken;if (is64)
@@ -2151,7 +2175,11 @@ static bool cmp_taken(int op, bool is64, __u64 v, __u64 c)static void test_cmp_imm (void ) {static const __s32 imms[] = { -1 ,-1 ,0x7f ,0x80 ,-0x80 ,-0x81 ,0x1000 ,0x7fffffff , +0 ,1 ,-1 ,0x7f ,0x80 ,-0x80 ,-0x81 ,0x1000 ,0x7fffffff , +0xfff ,0x1001 ,0xffff ,0x10000 ,0x10001 ,-0x1000 ,-0x1001 , +-0x7fffffff -1 ,0x7ffffffe ,0x12345 ,-0x12345 ,0xfff001 , +0xffffff ,-0xffffff ,0x1000000 ,-0x1000000 ,0x3ffc ,-0x10001 , +0xfff000 ,-0xfff ,-0xfff000 ,-0xfff001 ,0x1000001 , };static const int ops[] = {BPF_JEQ ,BPF_JNE ,BPF_JGT ,BPF_JGE ,BPF_JLT ,BPF_JLE ,
@@ -2182,8 +2210,18 @@ static void test_cmp_imm(void)prog_run (fd, inputs[j],0 , taken, desc); } +/* The operands at the immediate and right next to it */ +for (j =-1 ; j <=1 ; j++) { +__s64 near = (__s64 )imms[m] + j; +__u64 v = is64 ? (__u64 )near : (__u32 )near; +__u64 c = is64 ? (__u64 )(__s64 )imms[m] : + (__u32 )imms[m]; +__u64 taken =cmp_taken (ops[o], is64, v, c); + +prog_run (fd, v,0 , taken, desc); + }close (fd); -if (m) +if (imms[m] <-1 || imms[m] >1 )continue ;/* A jump over nothing lands on the same path either way */ jmp_prog (&p, is64, ops[o], d, imms[m],0 );
@@ -2230,12 +2268,31 @@ static void test_alu_consts(void) { BPF_ADD, 1 }, { BPF_ADD, -1 }, { BPF_SUB, 1 }, { BPF_SUB, -1 }, { BPF_ADD, 128 }, { BPF_SUB, 128 }, { BPF_ADD, -128 }, { BPF_AND, 0xff }, { BPF_AND, 0xffff }, { BPF_AND, 0x7f }, - { BPF_AND, 0x3ff }, { BPF_AND, 0x7fffffff }, - { BPF_OR, 0xff }, { BPF_XOR, -1 }, { BPF_XOR, 0x80 }, + { BPF_AND, 0x3ff }, { BPF_AND, 0x7fffffff }, { BPF_AND, -1 }, + { BPF_OR, 0xff }, { BPF_OR, -1 }, { BPF_XOR, -1 }, { BPF_XOR, 0x80 }, { BPF_MUL, 2 }, { BPF_MUL, 3 }, { BPF_MUL, 4 }, { BPF_MUL, 5 }, { BPF_MUL, 7 }, { BPF_MUL, 8 }, { BPF_MUL, 9 }, { BPF_MUL, 16 }, + { BPF_MUL, 17 }, { BPF_MUL, 33 }, { BPF_MUL, 0x40000001 }, { BPF_MUL, 0x40000000 }, { BPF_MUL, -3 }, { BPF_MUL, -0x7fffffff - 1 }, { BPF_MUL, 0 }, { BPF_MUL, 1 }, { BPF_MUL, -1 }, + { BPF_ADD, 0 }, { BPF_SUB, 0 }, { BPF_OR, 0 }, { BPF_XOR, 0 }, { BPF_AND, 0 }, + { BPF_MUL, 6 }, { BPF_MUL, 10 }, { BPF_MUL, 12 }, { BPF_MUL, 14 }, + { BPF_MUL, 15 }, { BPF_MUL, 24 }, { BPF_MUL, 31 }, { BPF_MUL, 48 }, + { BPF_MUL, 0x3fffffff }, { BPF_MUL, 0x7fffffff }, { BPF_MUL, -2 }, + { BPF_MUL, -4 }, { BPF_MUL, -6 }, { BPF_MUL, -7 }, { BPF_MUL, -8 }, + { BPF_MUL, -9 }, { BPF_MUL, -14 }, { BPF_MUL, -15 }, { BPF_MUL, -16 }, + { BPF_MUL, -0x40000000 }, { BPF_MUL, -0x7fffffff }, + { BPF_ADD, 0x10000 }, { BPF_ADD, 0x10001 }, { BPF_SUB, 0x10001 }, + { BPF_ADD, 0x12345 }, { BPF_ADD, -0x12345 }, { BPF_SUB, 0x12345 }, + { BPF_SUB, -0x12345 }, { BPF_ADD, 0xffffff }, { BPF_ADD, -0xffffff }, + { BPF_SUB, 0xffffff }, { BPF_ADD, 0x1000000 }, { BPF_SUB, -0x1000000 }, + { BPF_ADD, 0x123000 }, { BPF_ADD, 0xfff001 }, { BPF_SUB, 0x1001 }, + { BPF_ADD, -0x7fffffff - 1 }, { BPF_SUB, -0x7fffffff - 1 }, + { BPF_MUL, 66 }, { BPF_MUL, 272 }, { BPF_MUL, 240 }, { BPF_MUL, 992 }, + { BPF_MUL, -17 }, { BPF_MUL, -33 }, { BPF_MUL, -48 }, { BPF_MUL, -96 }, + { BPF_MUL, -12 }, { BPF_MUL, -24 }, { BPF_MUL, -28 }, + { BPF_ADD, 0x3ffc }, { BPF_ADD, -0x10001 }, { BPF_SUB, 0x3ffc }, + { BPF_SUB, -0x10001 }, };struct prog p;char desc[64 ];
@@ -2334,6 +2391,21 @@ static void test_probe_mem(void) { BPF_B, false }, { BPF_H, false }, { BPF_W, false }, { BPF_DW, false }, { BPF_B, true }, { BPF_H, true }, { BPF_W, true }, }; +/* +* Offsets that take an add, a sub, both shifted, or a mov and an add, +* into the ctx from a base moved by -base, and off NULL or user memory +*/ +static const struct { +int size; +__s16 off; +__s16 base; + } probes_in[] = { + {BPF_DW ,8 }, {BPF_W ,4 }, {BPF_H ,2 }, {BPF_B ,13 }, + {BPF_DW ,0x1008 ,0x1008 }, {BPF_W ,-0x1004 ,-0x1004 }, + }, probes_out[] = { + {BPF_DW ,0 }, {BPF_B ,13 }, {BPF_DW ,-8 }, {BPF_W ,4096 }, {BPF_H ,-4096 }, + {BPF_W ,0x1004 }, {BPF_W ,-0x1004 }, + };int kfunc_id, type_id, b, k, l, j, fd;struct bpf_insn call;struct btf *btf;
@@ -2392,24 +2464,62 @@ static void test_probe_mem(void) } } -/* NULL and a user address are not touched and read as zero */ -for (j =0 ; j <2 ; j++) { -__u64 addr = j ?0x00007ffffffff000ULL :0 ; +/* The offset forms through the untrusted pointer of the cast to void */ +for (l =0 ; l <ARRAY_SIZE (probes_in); l++) { +int size = probes_in[l].size, off = probes_in[l].off; +int base = probes_in[l].base;prog_start (&p); -EMIT (&p,BPF_RAW_INSN (BPF_LD |BPF_DW |BPF_IMM ,BPF_REG_1 ,0 ,0 , (__u32 )addr)); -EMIT (&p,BPF_RAW_INSN (0 ,0 ,0 ,0 , addr >>32 )); -EMIT (&p,BPF_MOV32_IMM (BPF_REG_2 , type_id)); +EMIT (&p,BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 )); +if (base) +EMIT (&p,BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 , -base)); +EMIT (&p,BPF_MOV32_IMM (BPF_REG_2 ,0 ));EMIT (&p, call); -EMIT (&p,BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_0 ,0 )); +EMIT (&p,BPF_LDX_MEM (size,BPF_REG_3 ,BPF_REG_0 , off));prog_end (&p,BPF_REG_3 ); -snprintf (desc,sizeof (desc),"probe_mem addr=0x%llx" , addr); +snprintf (desc,sizeof (desc),"probe_mem void size=%d off=%d base=%d" , + size, off, base); fd =prog_load (&p, desc);if (fd <0 )return ; -prog_run (fd,0 ,0 ,0 , desc); +for (j =0 ; j <ARRAY_SIZE (inputs); j++) { +struct pat_ctx c = { .in0 = inputs[j], .in1 = ~inputs[j] }; + +prog_run (fd, c.in0, c.in1, +load_bytes ((__u8 *)&c + off - base, size), desc); + }close (fd); } + +/* +* NULL and a user address read as zero, skipped or fixed up after a +* fault; no NULL plus a positive offset, as s390x has its lowcore there +*/ +for (l =0 ; l <ARRAY_SIZE (probes_out); l++) { +int size = probes_out[l].size, off = probes_out[l].off; + +for (j =0 ; j <2 ; j++) { +__u64 addr = j ?0x00007ffffffe0000ULL :0 ; + +if (!addr && off >0 ) +continue ; +prog_start (&p); +EMIT (&p,BPF_RAW_INSN (BPF_LD |BPF_DW |BPF_IMM ,BPF_REG_1 ,0 ,0 , + (__u32 )addr)); +EMIT (&p,BPF_RAW_INSN (0 ,0 ,0 ,0 , addr >>32 )); +EMIT (&p,BPF_MOV32_IMM (BPF_REG_2 , l ?0 : type_id)); +EMIT (&p, call); +EMIT (&p,BPF_LDX_MEM (size,BPF_REG_3 ,BPF_REG_0 , off)); +prog_end (&p,BPF_REG_3 ); +snprintf (desc,sizeof (desc),"probe_mem addr=0x%llx size=%d off=%d" , + addr, size, off); + fd =prog_load (&p, desc); +if (fd <0 ) +return ; +prog_run (fd,0 ,0 ,0 , desc); +close (fd); + } + } }/*
@@ -2421,9 +2531,11 @@ static void test_probe_mem(void)static void test_acq_rel (void ) {static const int sizes[] = {BPF_B ,BPF_H ,BPF_W ,BPF_DW }; +/* The slot through the base at the slot, below it and above it */ +static const int offs[] = {0 ,8 ,-8 };struct prog p;char desc[64 ]; -int b, k, s, j, fd; +int b, k, s, o, j, fd;for (b =0 ; b <ARRAY_SIZE (pat_regs); b++) {int rb = pat_regs[b];
@@ -2434,49 +2546,169 @@ static void test_acq_rel(void)for (k =0 ; k <NR_PAIRS ; k++) {int rd =pair_reg (b, k); -/* Load-acquire from the slot, also into the base */ -prog_start (&p); -EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN0 )); -EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rd,-8 )); -EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 )); -EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 )); -EMIT (&p,BPF_ATOMIC_OP (size,BPF_LOAD_ACQ , rd, rb,0 )); -prog_end (&p, rd); -snprintf (desc,sizeof (desc),"load_acq size=%d base=r%d dst=r%d" , - size, rb, rd); - fd =prog_load (&p, desc); -if (fd <0 ) -return ; -for (j =0 ; j <ARRAY_SIZE (inputs); j++) -prog_run (fd, inputs[j],0 , -head_bytes (inputs[j], size), desc); -close (fd); +for (o =0 ; o <ARRAY_SIZE (offs); o++) { +int off = offs[o]; + +/* Load-acquire from the slot, also into the base */ +prog_start (&p); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN0 )); +EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rd,-8 )); +EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 )); +EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 - off)); +EMIT (&p,BPF_ATOMIC_OP (size,BPF_LOAD_ACQ , rd, rb, off)); +prog_end (&p, rd); +snprintf (desc,sizeof (desc), +"load_acq size=%d base=r%d dst=r%d off=%d" , + size, rb, rd, off); + fd =prog_load (&p, desc); +if (fd <0 ) +return ; +for (j =0 ; j <ARRAY_SIZE (inputs); j++) +prog_run (fd, inputs[j],0 , +head_bytes (inputs[j], size), desc); +close (fd); + +if (rd == rb) +continue ; +/* Store-release of in1 over the slot holding in0 */ +prog_start (&p); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN0 )); +EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rd,-8 )); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN1 )); +EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 )); +EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 - off)); +EMIT (&p,BPF_ATOMIC_OP (size,BPF_STORE_REL , rb, rd, off)); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_10 ,-8 )); +prog_end (&p, rd); +snprintf (desc,sizeof (desc), +"store_rel size=%d base=r%d src=r%d off=%d" , + size, rb, rd, off); + fd =prog_load (&p, desc); +if (fd <0 ) +return ; +for (j =0 ; j <ARRAY_SIZE (inputs); j++) { +__u64 in1 = inputs[(j +1 ) %ARRAY_SIZE (inputs)]; + +prog_run (fd, inputs[j], in1, +head_merge (inputs[j], in1, size), desc); + } +close (fd); + } + } + } + } +} + +/* The n-th register after pat_regs[b] that is neither it nor r0 */ +static int ptr_operand_reg (int b,int n) +{ +int i = b; + +while (n--) { +do { + i = (i +1 ) %ARRAY_SIZE (pat_regs); + }while (pat_regs[i] ==BPF_REG_0 ); + } +return pat_regs[i]; +} + +/* rr |= bit unless ra == rb, compared in the width of size */ +static void check_eq (struct prog *p,int size,int ra,int rb,int rr,int bit) +{ +if (size ==BPF_W ) +EMIT (p,BPF_JMP32_REG (BPF_JEQ , ra, rb,1 )); +else +EMIT (p,BPF_JMP_REG (BPF_JEQ , ra, rb,1 )); +EMIT (p,BPF_ALU64_IMM (BPF_OR , rr, bit)); +} + +/* +* Atomics with the pointer itself as the operand (src == dst, and cmpxchg +* with the pointer as the new value), the bytes written checked against the +* operation done on a copy of the pointer made a number by two negations. +*/ +static void test_atomic_ptr_operand (void ) +{ +static const int sizes[] = {BPF_DW ,BPF_W }; +static const int ops[] = {BPF_ADD ,BPF_AND ,BPF_OR ,BPF_XOR }; +struct prog p; +char desc[64 ]; +int b, k, s, j, fd; + +for (b =0 ; b <ARRAY_SIZE (pat_regs); b++) { +/* The pointer, a copy of it, the expected value, the memory and the result */ +int rb = pat_regs[b], rp =ptr_operand_reg (b,1 ), rv =ptr_operand_reg (b,2 ); +int rm =ptr_operand_reg (b,3 ), rr =ptr_operand_reg (b,4 ); + +for (s =0 ; s <ARRAY_SIZE (sizes); s++) { +int size = sizes[s]; +bool w = size ==BPF_W ; + +for (k =0 ; k <ARRAY_SIZE (ops); k++) { +int op = ops[k]; -if (rd == rb) -continue ; -/* Store-release of in1 over the slot holding in0 */ prog_start (&p); -EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN0 )); -EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rd,-8 )); -EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_6 ,IN1 )); +EMIT (&p,BPF_MOV64_IMM (rr,0 )); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rv,BPF_REG_6 ,IN0 )); +EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rv,-8 ));EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 ));EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 )); -EMIT (&p,BPF_ATOMIC_OP (size,BPF_STORE_REL , rb, rd,0 )); -EMIT (&p,BPF_LDX_MEM (BPF_DW , rd,BPF_REG_10 ,-8 )); -prog_end (&p, rd); -snprintf (desc,sizeof (desc),"store_rel size=%d base=r%d src=r%d" , - size, rb, rd); +EMIT (&p,BPF_MOV64_REG (rp, rb)); +EMIT (&p,BPF_ALU64_IMM (BPF_NEG , rp,0 )); +EMIT (&p,BPF_ALU64_IMM (BPF_NEG , rp,0 )); +/* The bytes the atomic operates on, whichever the byte order */ +EMIT (&p,BPF_LDX_MEM (size, rv, rb,0 )); +EMIT (&p,BPF_ATOMIC_OP (size, op, rb, rb,0 )); +/* The memory holds in0 <op> pointer, the register the pointer */ +if (w) +EMIT (&p,BPF_ALU32_REG (op, rv, rp)); +else +EMIT (&p,BPF_ALU64_REG (op, rv, rp)); +/* Read back through fp, a clobbered pointer must not fault */ +EMIT (&p,BPF_LDX_MEM (size, rm,BPF_REG_10 ,-8 )); +check_eq (&p,BPF_DW , rm, rv, rr,1 ); +check_eq (&p,BPF_DW , rb, rp, rr,2 ); +prog_end (&p, rr); +snprintf (desc,sizeof (desc),"atomic%d_%s ptr=r%d" , + w ?32 :64 ,alu_name (op), rb); fd =prog_load (&p, desc);if (fd <0 )return ; -for (j =0 ; j <ARRAY_SIZE (inputs); j++) { -__u64 in1 = inputs[(j +1 ) %ARRAY_SIZE (inputs)]; - -prog_run (fd, inputs[j], in1, -head_merge (inputs[j], in1, size), desc); - } +for (j =0 ; j <ARRAY_SIZE (inputs); j++) +prog_run (fd, inputs[j],0 ,0 , desc);close (fd); } + +/* The pointer as the new value, r0 holds in0 and matches */ +if (rb ==BPF_REG_0 ) +continue ; +prog_start (&p); +EMIT (&p,BPF_MOV64_IMM (rr,0 )); +EMIT (&p,BPF_LDX_MEM (BPF_DW , rv,BPF_REG_6 ,IN0 )); +EMIT (&p,BPF_STX_MEM (BPF_DW ,BPF_REG_10 , rv,-8 )); +EMIT (&p,BPF_MOV64_REG (rb,BPF_REG_10 )); +EMIT (&p,BPF_ALU64_IMM (BPF_ADD , rb,-8 )); +EMIT (&p,BPF_MOV64_REG (rp, rb)); +EMIT (&p,BPF_ALU64_IMM (BPF_NEG , rp,0 )); +EMIT (&p,BPF_ALU64_IMM (BPF_NEG , rp,0 )); +/* r0 holds the bytes the atomic compares with and matches */ +EMIT (&p,BPF_LDX_MEM (size,BPF_REG_0 , rb,0 )); +EMIT (&p,BPF_MOV64_REG (rv,BPF_REG_0 )); +EMIT (&p,BPF_ATOMIC_OP (size,BPF_CMPXCHG , rb, rb,0 )); +/* The memory holds the pointer in the width, r0 the old value */ +EMIT (&p,BPF_LDX_MEM (size, rm,BPF_REG_10 ,-8 )); +check_eq (&p, size, rm, rp, rr,1 ); +check_eq (&p,BPF_DW ,BPF_REG_0 , rv, rr,2 ); +check_eq (&p,BPF_DW , rb, rp, rr,4 ); +prog_end (&p, rr); +snprintf (desc,sizeof (desc),"atomic%d_cmpxchg ptr=r%d new=r%d" , + w ?32 :64 , rb, rb); + fd =prog_load (&p, desc); +if (fd <0 ) +return ; +for (j =0 ; j <ARRAY_SIZE (inputs); j++) +prog_run (fd, inputs[j],0 ,0 , desc); +close (fd); } } }
@@ -2540,6 +2772,231 @@ static void test_max_jmp(void)max_jmp (true, false); } +/* +* A sign test forward or back over a region of n sign tests, which shrink it +* as they take the short branch; n sweeps the reach of the sizing pass. +*/ +#define CHAIN_NO_CALL 0 +#define CHAIN_HELPER 1 +#define CHAIN_SUBPROG 2 + +static void sign_jumps (int inner,bool back,int call,const char *desc) +{ +struct bpf_insn *insns; +int n =0 , top, sub =0 , i, fd; + + insns =malloc ((24 +2 * inner) *sizeof (*insns)); +if (!ASSERT_OK_PTR (insns, desc)) +return ; + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_0 ,BPF_REG_1 ,IN0 ); + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_1 ,IN1 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_2 ,1 ); +if (back) + insns[n++] =BPF_MOV64_IMM (BPF_REG_4 ,-2 ); +else + insns[n++] =BPF_JMP_IMM (BPF_JSLT ,BPF_REG_0 ,0 ,0 ); + top = n; +for (i =0 ; i < inner; i++) { + insns[n++] =BPF_JMP_IMM (BPF_JSGE ,BPF_REG_3 ,0 ,1 ); + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ); + } +if (call !=CHAIN_NO_CALL ) { +/* The call clobbers r0 to r5: the count, the sign and the loop go to r7 to r9 */ + insns[n++] =BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_2 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_8 ,BPF_REG_3 ); +if (back) + insns[n++] =BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_4 ); + sub = n++; + insns[n++] =BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_7 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_3 ,BPF_REG_8 ); +if (back) + insns[n++] =BPF_MOV64_REG (BPF_REG_4 ,BPF_REG_9 ); + } +if (back) { + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_4 ,1 ); + insns[n] =BPF_JMP_IMM (BPF_JSLT ,BPF_REG_4 ,0 , top - n -1 ); + n++; + }else { + insns[top -1 ] =BPF_JMP_IMM (BPF_JSLT ,BPF_REG_0 ,0 , n - top); + } + insns[n++] =BPF_STX_MEM (BPF_DW ,BPF_REG_6 ,BPF_REG_2 ,RES ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[n++] =BPF_EXIT_INSN (); +if (call ==CHAIN_SUBPROG ) { + insns[sub] =BPF_CALL_REL (n - sub -1 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[n++] =BPF_EXIT_INSN (); + }else if (call ==CHAIN_HELPER ) { + insns[sub] =BPF_EMIT_CALL (BPF_FUNC_get_prandom_u32); + } + + fd =load_prog (insns, n, desc); +free (insns); +if (fd <0 ) +return ; +/* One plus the adds with the inner sign set, none with the outer one */ +prog_run (fd,0 ,-1 , back ?2 * inner +1 : inner +1 , desc); +prog_run (fd,0 ,0 ,1 , desc); +prog_run (fd,-1 ,-1 , back ?2 * inner +1 :1 , desc); +prog_run (fd,1ULL <<63 ,-1 , back ?2 * inner +1 :1 , desc); +close (fd); +} + +/* +* A chain of sign tests over the region, each an instruction further out than +* the next, so each would fit the short reach only once the next one shrank; +* a call in the region shrinks it. +*/ +static void sign_jump_chain (int inner,int outer,int call,const char *desc) +{ +struct bpf_insn *insns; +int n =0 , top, off, sub =0 , i, fd; + + insns =malloc ((16 +2 * outer +2 * inner) *sizeof (*insns)); +if (!ASSERT_OK_PTR (insns, desc)) +return ; + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_0 ,BPF_REG_1 ,IN0 ); + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_1 ,IN1 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_2 ,0 ); + top = n; + n += outer; +for (i =0 ; i < inner; i++) { + insns[n++] =BPF_JMP_IMM (BPF_JSGE ,BPF_REG_3 ,0 ,1 ); + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ); + } +if (call !=CHAIN_NO_CALL ) { + insns[n++] =BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_2 ); + sub = n++; + insns[n++] =BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_7 ); + } +/* The i-th test jumps to the i-th add behind the region, the same offset for all */ + off = n - top -1 ; +for (i =0 ; i < outer; i++) { + insns[top + i] =BPF_JMP_IMM (BPF_JSLT ,BPF_REG_0 ,0 , off); + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ); + } + insns[n++] =BPF_STX_MEM (BPF_DW ,BPF_REG_6 ,BPF_REG_2 ,RES ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[n++] =BPF_EXIT_INSN (); +if (call ==CHAIN_SUBPROG ) { + insns[sub] =BPF_CALL_REL (n - sub -1 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[n++] =BPF_EXIT_INSN (); + }else if (call ==CHAIN_HELPER ) { + insns[sub] =BPF_EMIT_CALL (BPF_FUNC_get_prandom_u32); + } + + fd =load_prog (insns, n, desc); +free (insns); +if (fd <0 ) +return ; +/* The adds of the region with the inner sign set, the ones behind it always */ +prog_run (fd,0 ,-1 , inner + outer, desc); +prog_run (fd,0 ,0 , outer, desc); +prog_run (fd,-1 ,-1 , outer, desc); +prog_run (fd,1ULL <<63 ,-1 , outer, desc); +close (fd); +} + +/* +* A sign test forward over n fillers that keep their size, so that the short +* branch gets exactly the offset the sizing pass measured: n = 8190 at most. +*/ +static void sign_jump_fill (int fill,const char *desc) +{ +struct bpf_insn *insns; +int n =0 , top, i, fd; + + insns =malloc ((8 + fill) *sizeof (*insns)); +if (!ASSERT_OK_PTR (insns, desc)) +return ; + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_0 ,BPF_REG_1 ,IN0 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_2 ,2 ); + top = n++; +for (i =1 ; i < fill; i++) + insns[n++] =BPF_MOV64_IMM (BPF_REG_3 ,0 ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_2 ,1 ); + insns[top] =BPF_JMP_IMM (BPF_JSLT ,BPF_REG_0 ,0 , n - top -1 ); + insns[n++] =BPF_STX_MEM (BPF_DW ,BPF_REG_6 ,BPF_REG_2 ,RES ); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insns[n++] =BPF_EXIT_INSN (); + + fd =load_prog (insns, n, desc); +free (insns); +if (fd <0 ) +return ; +prog_run (fd,-1 ,0 ,2 , desc); +prog_run (fd,0 ,0 ,1 , desc); +close (fd); +} + +static void test_sign_jumps (void ) +{ +/* 2729 to 2732: a region of 8187 to 8196 instructions as the sizing pass sees it */ +static const int inners[] = {16 ,2000 ,2729 ,2730 ,2731 ,2732 ,4200 }; +static const int chain_inners[][2 ] = { {2716 ,2724 }, {4080 ,4098 } }; +char desc[80 ]; +int i, inner; + +for (i =0 ; i <ARRAY_SIZE (inners); i++) { +snprintf (desc,sizeof (desc),"sign jump over %d sign jumps" , inners[i]); +sign_jumps (inners[i], false,CHAIN_NO_CALL , desc); +snprintf (desc,sizeof (desc),"sign jump back over %d sign jumps" , inners[i]); +sign_jumps (inners[i], true,CHAIN_NO_CALL , desc); + } +/* +* The reach of the sizing pass with a subprogram call in the region, +* which the extra pass makes direct +*/ +for (inner =2722 ; inner <=2733 ; inner++) { +snprintf (desc,sizeof (desc),"sign jump over %d sign jumps and a subprog call" , + inner); +sign_jumps (inner, false,CHAIN_SUBPROG , desc); +snprintf (desc,sizeof (desc),"sign jump back over %d sign jumps and a subprog call" , + inner); +sign_jumps (inner, true,CHAIN_SUBPROG , desc); + } +/* The exact reach of the short branch, 8190 fillers and no more */ +for (inner =8189 ; inner <=8192 ; inner++) { +snprintf (desc,sizeof (desc),"sign jump over %d fillers" , inner); +sign_jump_fill (inner, desc); + } +/* +* Across the reach of the shrunk region, where the tests keep the +* compare and branch, also with a subprogram call in the extra pass +*/ +for (inner =4086 ; inner <=4100 ; inner++) { +snprintf (desc,sizeof (desc),"sign jump over %d sign jumps at the range" , inner); +sign_jumps (inner, false,CHAIN_NO_CALL , desc); +snprintf (desc,sizeof (desc),"sign jump back over %d sign jumps at the range" , + inner); +sign_jumps (inner, true,CHAIN_NO_CALL , desc); +snprintf (desc,sizeof (desc),"sign jump back over %d sign jumps and a subprog call" , + inner); +sign_jumps (inner, true,CHAIN_SUBPROG , desc); + } +/* +* Chains across the reach of the sizing pass over 2716 to 2724 inner +* tests, where they are decided, and of the shrunk region over 4080 to +* 4098. +*/ +for (i =0 ; i <ARRAY_SIZE (chain_inners); i++) { +for (inner = chain_inners[i][0 ]; inner <= chain_inners[i][1 ]; inner++) { +snprintf (desc,sizeof (desc),"sign jump chain over %d sign jumps" , inner); +sign_jump_chain (inner,20 ,CHAIN_NO_CALL , desc); +snprintf (desc,sizeof (desc), +"sign jump chain over %d sign jumps and a call" , inner); +sign_jump_chain (inner,20 ,CHAIN_HELPER , desc); +snprintf (desc,sizeof (desc), +"sign jump chain over %d sign jumps and a subprog call" , inner); +sign_jump_chain (inner,20 ,CHAIN_SUBPROG , desc); + } + } +} +/* * Fillers of two and three bytes of native code on x86-64: a 32-bit and a * 64-bit move between two low registers, which give a region every length
@@ -2928,6 +3385,54 @@ static void test_same_len_not_converged(void)close (fd); } +/* +* Short loops back with a compare, a zero test and a sign test, behind enough +* helper calls to put them beyond 1MB into the image of the sizing pass +*/ +static void test_far_back_jump (void ) +{ +const struct bpf_insn loops[] = { +BPF_MOV64_IMM (BPF_REG_1 ,0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,1 ), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_1 ,3 ,-2 ), +BPF_MOV64_IMM (BPF_REG_2 ,3 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_2 ,1 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_2 ,0 ,-2 ), +BPF_MOV64_IMM (BPF_REG_3 ,-3 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_3 ,1 ), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,0 ,-2 ), +/* in0 + 3 + 0 + 0 */ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_7 ,BPF_REG_1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_7 ,BPF_REG_2 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_7 ,BPF_REG_3 ), +BPF_STX_MEM (BPF_DW ,BPF_REG_6 ,BPF_REG_7 ,RES ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), + }; +const int calls =52500 ; +struct bpf_insn *insns; +int n =0 , i, fd; + + insns =malloc ((2 + calls +ARRAY_SIZE (loops)) *sizeof (*insns)); +if (!ASSERT_OK_PTR (insns,"far back jump" )) +return ; + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_7 ,BPF_REG_1 ,IN0 ); +for (i =0 ; i < calls; i++) + insns[n++] =BPF_EMIT_CALL (BPF_FUNC_get_prandom_u32); +memcpy (insns + n, loops,sizeof (loops)); + n +=ARRAY_SIZE (loops); + + fd =load_prog (insns, n,"far back jump" ); +free (insns); +if (fd <0 ) +return ; +ASSERT_GT (jited_len (fd),0 ,"far back jump jited" ); +prog_run (fd,0 ,0 ,3 ,"far back jump" ); +prog_run (fd,-1 ,0 ,2 ,"far back jump" ); +close (fd); +} +/* * Calls into a subprogram with all five arguments, which clobbers a subset * of r6-r9 and uses the deepest stack slot the budget leaves, directly or
@@ -3093,6 +3598,94 @@ static void test_helper_calls(void)close (map_fd); } +/* +* A tail call with the index from the packet, which the JIT scales and takes +* the low 32 bits of: the entries return their index plus one, an empty one +* and an index from the array size on TAIL_FALL, the upper 32 bits ignored. +*/ +#define TAIL_ENTRIES 7 +#define TAIL_FALL 0xfa11 + +static void test_tail_call (void ) +{ +static const int filled[] = {0 ,1 ,3 ,5 }; +static const struct { +__u64 index; +__u32 res; + } cases[] = { + {0 ,1 }, {1 ,2 }, {3 ,4 }, {5 ,6 }, + {2 ,TAIL_FALL }, {4 ,TAIL_FALL }, {6 ,TAIL_FALL }, + {TAIL_ENTRIES ,TAIL_FALL }, {0x7fffffff ,TAIL_FALL }, {0xffffffff ,TAIL_FALL }, + {1ULL <<32 ,1 }, { (1ULL <<32 ) |3 ,4 }, { (~0ULL <<32 ) |5 ,6 }, + { (~0ULL <<32 ) |2 ,TAIL_FALL }, { ~0ULL ,TAIL_FALL }, + }; +LIBBPF_OPTS (bpf_prog_load_opts, lopts, + .log_buf = log, + .log_size = sizeof(log), + ); +struct { +__u64 index; +__u64 pad; + } pkt = {}; +LIBBPF_OPTS (bpf_test_run_opts, opts, + .data_in = &pkt, + .data_size_in = sizeof(pkt), + ); +struct bpf_insn insns[16 ]; +int map_fd, fd =-1 , k, n, i; +char desc[64 ]; + + map_fd =bpf_map_create (BPF_MAP_TYPE_PROG_ARRAY ,"tail_call" ,sizeof (__u32), +sizeof (__u32),TAIL_ENTRIES ,NULL ); +if (!ASSERT_GE (map_fd,0 ,"prog array" )) +return ; +for (i =0 ; i <ARRAY_SIZE (filled); i++) { + k = filled[i]; + n =0 ; + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 , k +1 ); + insns[n++] =BPF_EXIT_INSN (); +snprintf (desc,sizeof (desc),"tail call target %d" , k); + fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, n, &lopts); +if (!ASSERT_GE (fd,0 , desc)) { +fprintf (stderr,"%s" , log); + goto out; + } +ASSERT_OK (bpf_map_update_elem (map_fd, &k, &fd,BPF_ANY ), desc); +close (fd); + } +/* The index from the packet, a call which comes back returns TAIL_FALL */ + n =0 ; + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , offsetof(struct xdp_md , data)); + insns[n++] =BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , offsetof(struct xdp_md , data_end)); + insns[n++] =BPF_MOV64_REG (BPF_REG_4 ,BPF_REG_2 ); + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_4 ,8 ); + insns[n++] =BPF_JMP_REG (BPF_JGT ,BPF_REG_4 ,BPF_REG_3 ,5 ); + insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_2 ,0 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ); + insns[n++] =BPF_RAW_INSN (BPF_LD |BPF_DW |BPF_IMM ,BPF_REG_2 ,BPF_PSEUDO_MAP_FD ,0 , + map_fd); + insns[n++] =BPF_RAW_INSN (0 ,0 ,0 ,0 ,0 ); + insns[n++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_tail_call); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,TAIL_FALL ); + insns[n++] =BPF_EXIT_INSN (); + fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, n, &lopts); +if (!ASSERT_GE (fd,0 ,"tail call" )) { +fprintf (stderr,"%s" , log); + goto out; + } +for (i =0 ; i <ARRAY_SIZE (cases); i++) { +snprintf (desc,sizeof (desc),"tail call index 0x%llx" , cases[i].index); + pkt.index = cases[i].index; +if (ASSERT_OK (bpf_prog_test_run_opts (fd, &opts), desc)) +ASSERT_EQ (opts.retval, cases[i].res, desc); + } +out: +if (fd >=0 ) +close (fd); +close (map_fd); +} +void test_jit_insns (void ) {RUN_TESTS (jit_insns_arena);
@@ -3132,20 +3725,28 @@ void test_jit_insns(void)test_staggered_jumps ();if (test__start_subtest ("max_jmp" ))test_max_jmp (); +if (test__start_subtest ("sign_jumps" )) +test_sign_jumps ();if (test__start_subtest ("convergence" ))test_convergence ();if (test__start_subtest ("same_len_not_converged" ))test_same_len_not_converged (); +if (test__start_subtest ("far_back_jump" )) +test_far_back_jump ();if (test__start_subtest ("calls" ))test_calls ();if (test__start_subtest ("helper_calls" ))test_helper_calls (); +if (test__start_subtest ("tail_call" )) +test_tail_call ();if (test__start_subtest ("ldst_zero_off" ))test_ldst_zero_off ();if (test__start_subtest ("ldst_offsets" ))test_ldst_offsets ();if (test__start_subtest ("acq_rel" ))test_acq_rel (); +if (test__start_subtest ("atomic_ptr_operand" )) +test_atomic_ptr_operand ();if (test__start_subtest ("movsx" ))test_movsx ();if (test__start_subtest ("jset_imm" ))
tools/testing/selftests/bpf/progs/jit_insns_arena.c +445 -1
462 lines not on this page · raw message
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH bpf-next v3 24/24] selftests/bpf: Extend the JIT instruction tests for arm64 encodings
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider: - [Medium] selftests/bpf: misaligned XDP packet load in test_tail_call() --
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Medium] selftests/bpf: misaligned XDP packet load in test_tail_call() --
commit 3e5456182ae6e38cbc6f04091b8df4d4e305b794
Author: Daniel Borkmann <[email protected]>
selftests/bpf: Extend the JIT instruction tests for arm64 encodings
This commit extends the BPF JIT instruction selftests with additional test cases covering compares, bit tests, constant arithmetic, immediates, sign jumps, arena and PROBE_MEM accesses, and tail calls.
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/jit_insns.c +0
-0
[ ... ]
Quoted 14 lines
tools/testing/selftests/bpf/prog_tests/jit_insns.c +10
-0@@ -3093,6 +3598,94 @@ static void test_helper_calls(void)close (map_fd); } +/* +* A tail call with the index from the packet, which the JIT scales and takes +* the low 32 bits of: the entries return their index plus one, an empty one +* and an index from the array size on TAIL_FALL, the upper 32 bits ignored. +*/ +#define TAIL_ENTRIES 7 +#define TAIL_FALL 0xfa11 + +static void test_tail_call (void ) +{
[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/jit_insns.c +4
-0+LIBBPF_OPTS (bpf_prog_load_opts, lopts, + .log_buf = log, + .log_size = sizeof(log), + );
[ ... ]
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/jit_insns.c +8
-0+/* The index from the packet, a call which comes back returns TAIL_FALL */ + n =0 ; + insns[n++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); + insns[n++] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , offsetof(struct xdp_md , data)); + insns[n++] =BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , offsetof(struct xdp_md , data_end)); + insns[n++] =BPF_MOV64_REG (BPF_REG_4 ,BPF_REG_2 ); + insns[n++] =BPF_ALU64_IMM (BPF_ADD ,BPF_REG_4 ,8 ); + insns[n++] =BPF_JMP_REG (BPF_JGT ,BPF_REG_4 ,BPF_REG_3 ,5 );
tools/testing/selftests/bpf/prog_tests/jit_insns.c static void test_helper_calls(void) · line 3673
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/jit_insns.c +10
-0+ insns[n++] =BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_2 ,0 ); + insns[n++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ); + insns[n++] =BPF_RAW_INSN (BPF_LD |BPF_DW |BPF_IMM ,BPF_REG_2 ,BPF_PSEUDO_MAP_FD ,0 , + map_fd); + insns[n++] =BPF_RAW_INSN (0 ,0 ,0 ,0 ,0 ); + insns[n++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_tail_call); + insns[n++] =BPF_MOV64_IMM (BPF_REG_0 ,TAIL_FALL ); + insns[n++] =BPF_EXIT_INSN (); + fd =bpf_prog_load (BPF_PROG_TYPE_XDP ,NULL ,"GPL" , insns, n, &lopts); +if (!ASSERT_GE (fd,0 ,"tail call" )) {
[Severity: Medium]
As reported by [email protected] on v2 [1], will the verifier reject this BPF_DW load from the XDP packet pointer on architectures without CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS?
When strict alignment is enabled and lopts does not set BPF_F_ANY_ALIGNMENT, check_pkt_ptr_alignment() adds NET_IP_ALIGN (2) to the packet offset and rejects the 8-byte load at offset 0 with -EACCES, causing the tail_call subtest to fail on strict-alignment targets.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=24
Daniel Borkmann
maintainerRe: [PATCH bpf-next v3 24/24] selftests/bpf: Extend the JIT instruction tests for arm64 encodings
Quoted 3 lines · On 11/8/26 8:45 PM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Medium] selftests/bpf: misaligned XDP packet load intest_tail_call()
[...]
Quoted 4 lines
[Severity: Medium]
As reported by [email protected] on v2 [1], will the verifier reject thisBPF_DWload from the XDP packet pointer on architectures withoutCONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS?
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 15 lines · On Sun, 8 Nov 2026 20:26:26 +0100 you wrote:
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_insnsandjit_insns_blindedpass in full, andtest_progsand its cpuv4 andno_alu32flavors 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 orAARCH64_BREAK_FAULTfor what it cannot encode.
Quoted 1 line
[...]
Here is the summary with links:
- [bpf-next,v3,01/24] bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT
https://git.kernel.org/bpf/bpf-next/c/0931830cc312 - [bpf-next,v3,02/24] bpf, arm64: Free the offset table of a subprog in bpf_jit_free https://git.kernel.org/bpf/bpf-next/c/0ff09166d3d2 - [bpf-next,v3,03/24] bpf, arm64: Free the private stack when a pass over the image fails https://git.kernel.org/bpf/bpf-next/c/346ea1557fd7 - [bpf-next,v3,04/24] bpf, arm64: Emit ISB SY in the speculation barriers https://git.kernel.org/bpf/bpf-next/c/6a5b148dac53 - [bpf-next,v3,05/24] arm64, insn: Reject sign extending loads of 64 bits https://git.kernel.org/bpf/bpf-next/c/182afb043e7e - [bpf-next,v3,06/24] bpf, arm64: Keep the ll/sc atomics address apart from the old value https://git.kernel.org/bpf/bpf-next/c/207aac32085d - [bpf-next,v3,07/24] bpf, arm64: Measure backward branches from the branch itself https://git.kernel.org/bpf/bpf-next/c/1963ac21c7c2 - [bpf-next,v3,08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders https://git.kernel.org/bpf/bpf-next/c/d860f6254d60 - [bpf-next,v3,09/24] bpf, arm64: Widen the branch offsets before scaling them to bytes https://git.kernel.org/bpf/bpf-next/c/592f36e960d0 - [bpf-next,v3,10/24] arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings https://git.kernel.org/bpf/bpf-next/c/1fdba03c72cb - [bpf-next,v3,11/24] bpf: Divide by constants via uhmul and shmul in the verifier https://git.kernel.org/bpf/bpf-next/c/ffebe8b3e369 - [bpf-next,v3,12/24] bpf, arm64: Consolidate the load and store emission into a helper https://git.kernel.org/bpf/bpf-next/c/1bb1bc5be527 - [bpf-next,v3,13/24] bpf, arm64: Use the unscaled forms for negative and unaligned offsets https://git.kernel.org/bpf/bpf-next/c/6b3c7bde476f - [bpf-next,v3,14/24] bpf, arm64: Store zero immediates from the zero register https://git.kernel.org/bpf/bpf-next/c/e4939b2a54b9 - [bpf-next,v3,15/24] bpf, arm64: Zero extend the arena offset in register offset accesses https://git.kernel.org/bpf/bpf-next/c/07d4e6947e37 - [bpf-next,v3,16/24] bpf, arm64: Adjust compares with unencodable immediates by one https://git.kernel.org/bpf/bpf-next/c/a33de9a3bba3 - [bpf-next,v3,17/24] bpf, arm64: Materialize immediates with fewer instructions https://git.kernel.org/bpf/bpf-next/c/e79c67bce1a2 - [bpf-next,v3,18/24] bpf, arm64: Shorten the tail call sequence https://git.kernel.org/bpf/bpf-next/c/7dd5500c2c4f - [bpf-next,v3,19/24] bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones https://git.kernel.org/bpf/bpf-next/c/4835c45b11d2 - [bpf-next,v3,20/24] bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests https://git.kernel.org/bpf/bpf-next/c/abf5971d572c - [bpf-next,v3,21/24] bpf, arm64: Multiply by constants with shifts, adds and subs https://git.kernel.org/bpf/bpf-next/c/c9c277f5e08f - [bpf-next,v3,22/24] selftests/bpf: Let the arm64 private stack check skip the BTI pad https://git.kernel.org/bpf/bpf-next/c/75e665d4892b - [bpf-next,v3,23/24] selftests/bpf: Test the verifier's division by constants https://git.kernel.org/bpf/bpf-next/c/099c2e03f9a0 - [bpf-next,v3,24/24] selftests/bpf: Extend the JIT instruction tests for arm64 encodings https://git.kernel.org/bpf/bpf-next/c/a9fee553d3db
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html