[PATCH bpf-next 00/21] bpf: Various arm64 BPF JIT improvements

[PATCH bpf-next 00/21] bpf: Various arm64 BPF JIT improvements

[Daniel Borkmann]

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 (7c11a349512b), Tetragon (3f20b90ee580), Katran
(2cd783e43a07) and the sched_ext schedulers (scx at fead94e15184 plus
tools/sched_ext) were built with clang 20 for arm64, and every program
of them that loads (817, another 121 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.37%     -7.69%    -12.10%     -6.81%     -9.58%   -3.10%   -3.47%   -3.11%   -3.11%
katran         5   -6.41%     -6.78%     -8.54%     -7.48%     -0.18%   -5.62%   -7.48%   -5.65%   -5.64%
scx          391   -6.67%     -8.43%     -5.62%     -5.54%     -4.19%   -5.81%   -4.39%   -5.93%   -5.90%
tetragon     261   -2.62%     -3.19%     -3.76%     -3.79%     -2.13%   -2.54%   -2.61%   -2.54%   -2.54%
all          817   -3.22%     -4.70%     -5.54%     -4.58%     -4.16%   -3.06%   -3.00%   -3.07%   -3.07%

Cilium gains the most cycles from its 417 divisions by NSEC_PER_SEC in
89 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 78 divisions in 35 programs, mostly by 100 and 1000000.
The rest of the cycles and most of the uops come from the branches:
38341 compares against zero and their branch become a cbz or cbnz, and
6173 sign and bit tests a tbz or tbnz, a uop and a cycle each. Then 2698
stores of zero take the zero register, 1171 loads and stores the
unscaled form, 707 xors with all ones become a mvn, 316 multiplications
shifts and adds, and 222 adds, subs and compares take an immediate
shifted by 12 in place of a move. 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:    540001c2     b.hs   #56
  48:    f940034c     ldr    x12, [x26]
  4c:    f100859f     cmp    x12, #33
  50:    54000162     b.hs   #44
  54:    9100058c     add    x12, x12, #1
  58:    9108802a     add    x10, x1, #544
  5c:    d37d7c4b     ubfiz  x11, x2, #3, #32
  60:    f86b694b     ldr    x11, [x10, x11]
  64:    b40000cb     cbz    x11, #24

Of the 817 programs, 715 get smaller, and 640, 601, 587 and 467 faster
on N1, N2, V1 and V2. The best cases:

  Impact     Largest decrease                                    Largest relative decrease
  ---------  --------------------------------------------------  ------------------------------------
  size       generic_sleepable_preload    30192 > 28292  -6.29%  pandemonium_enable 280 > 224 -20.00%
  N1 cycles  cil_to_netdev                  1331 > 1172 -11.95%  flash_select_cpu     73 > 53 -27.40%
  N2 cycles  tail_handle_ipv6_from_netdev    1070 > 828 -22.62%  flash_enqueue      202 > 118 -41.58%
  V1 cycles  generic_sleepable_preload      1118 > 1000 -10.60%  flash_stopping       65 > 49 -24.62%
  V2 cycles  tail_handle_ipv4_from_netdev     713 > 495 -30.58%  flash_enqueue       187 > 85 -54.55%

The largest gains in cycles are in Cilium's bpf_host.o, whose programs
above hold 14 to 21 of the divisions by NSEC_PER_SEC each, and in
Tetragon's generic_sleepable_preload, which turns 451 of its 667
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      5  rusty_stopping    133 > 135  +1.50%   pandemonium_cpu_offline   17 > 18  +5.88%
  N2 cycles     15  bpfland_stopping   47 > 50   +6.38%   the same
  V1 cycles     16  lavd_running      746 > 751  +0.67%   scx_pmu_switch_tc         76 > 80  +5.26%
  V2 cycles     30  fcg_runnable      114 > 119  +4.39%   mitosis_set_cpumask       53 > 57  +7.55%

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
simple_enable only in one pairing of boots. None of the 51 programs that
some model rates slower has more instructions; nearly all 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, 7 on N2, by
at most 4.12%.

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>3     9>8 5>4     9>8 4>3     9>8 4>3

Thanks,
Daniel

  [0] https://lore.kernel.org/bpf/20261013171230.523677-1-daniel@iogearbox.net/

Daniel Borkmann (21):
  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
  arm64, insn: Add the LDUR/STUR, UMULH/SMULH and TBZ/TBNZ encodings
  bpf: Move the division magic number computation out of the x86 JIT
  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: Divide by constants via multiplication with a magic number
  bpf, arm64: Use a move or mvn for the and 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
  bpf, arm64: Split 24-bit immediates of add, sub and equality compares
  selftests/bpf: Let the arm64 private stack check skip the BTI pad
  selftests/bpf: Extend the JIT instruction tests for arm64 encodings

 arch/arm64/include/asm/insn.h                 |   33 +-
 arch/arm64/lib/insn.c                         |  147 +++
 arch/arm64/net/bpf_jit.h                      |   38 +-
 arch/arm64/net/bpf_jit_comp.c                 | 1018 +++++++++++++----
 arch/x86/net/bpf_jit_comp.c                   |   97 --
 include/linux/filter.h                        |   11 +
 kernel/bpf/core.c                             |   93 ++
 .../selftests/bpf/prog_tests/jit_insns.c      |  418 ++++++-
 .../selftests/bpf/progs/jit_insns_arena.c     |  381 +++++-
 .../selftests/bpf/progs/verifier_ldsx.c       |   24 +-
 .../bpf/progs/verifier_private_stack.c        |    1 +
 11 files changed, 1865 insertions(+), 396 deletions(-)

-- 
2.43.0

[PATCH bpf-next 01/21] bpf, arm64: Free the offset table of a subprog in bpf_jit_free

[Daniel Borkmann]

bpf_int_jit_compile() keeps the context of a subprog after its first
run in jit_data, with the offset table, for the extra pass, which frees
both. When the JIT of a later subprog fails, jit_subprogs() frees the
subprogs JITed so far through bpf_jit_free(), which frees jit_data but
not the offset table in it, so every such failure leaks the table.

Free the offset table there as well, as the x86, riscv and LoongArch
JITs do.

Fixes: db496944fdaa ("bpf: arm64: add JIT support for multi-function programs")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index aaa34c739004..bcad1ed87467 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -3569,6 +3569,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();
-- 
2.43.0

[PATCH bpf-next 02/21] bpf, arm64: Free the private stack when a pass over the image fails

[Daniel Borkmann]

bpf_int_jit_compile() allocates the private stack of a program before
the sizing passes and frees it on the way out when ro_header is NULL,
which is only the case when the JIT fails before the image is
allocated, or when the pack finalize fails, which clears the pointer.
A failure in the passes over the image, or in the extra pass of a
subprog, frees the image but leaves ro_header set, so the private
stack stays allocated behind prog->aux->priv_stack_ptr of a program
that is not jited, which bpf_jit_free() then skips.

Clear ro_header and header once the image is freed, so that the exit
path frees the private stack as it does for a failure before the
allocation, like the x86 JIT does with its image pointer.

Fixes: 6c17a882d380 ("bpf, arm64: JIT support for private stack")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index bcad1ed87467..febe072a8af2 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -2528,6 +2528,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 		bpf_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;
 }
-- 
2.43.0

[PATCH bpf-next 03/21] bpf, arm64: Emit ISB SY in the speculation barriers

[Daniel Borkmann]

The Spectre-BHB loop of the epilogue and BPF_NOSPEC on cores without
FEAT_SB end in an ISB, which the JIT took from
aarch64_insn_get_isb_value(), the template of the instruction matcher
with CRm 0. The Arm ARM lists every CRm other than 0b1111 as reserved:
those encodings execute as a full system barrier, but must not be relied
upon by software. Emit ISB SY with CRm 0b1111, as the assembler does for
the isb of the kernel's own barriers.

Before/after:

  d50330df  isb #0
  d5033fdf  isb

Fixes: 0dfefc2ea2f2 ("arm64: bpf: Add BHB mitigation to the epilogue for cBPF programs")
Fixes: dff883d9e93a ("bpf, arm64, powerpc: Change nospec to include v1 barrier")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h      | 2 +-
 arch/arm64/net/bpf_jit_comp.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index b2fe6e6dcf44..af570c34a96d 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -341,6 +341,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 */
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index febe072a8af2..7d5eb949cdf4 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -1026,7 +1026,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()) {
-- 
2.43.0

[PATCH bpf-next 04/21] arm64, insn: Reject sign extending loads of 64 bits

[Daniel Borkmann]

The sign extending loads exist for bytes, halfwords and words. With the
size of a doubleword, the opc of LDRSB, LDRSH and LDRSW encodes PRFM,
so aarch64_insn_gen_load_store_imm() and
aarch64_insn_gen_load_store_reg() returned a prefetch, which leaves the
destination register as it was, instead of failing. The BPF JIT, their
only user, does not ask for one, as BPF_MEMSX has no BPF_DW form and the
verifier rejects the opcode, but return AARCH64_BREAK_FAULT for it as
for the other invalid operands.

Before/after for a sign extending load of 64 bits from x1 + 8 into x0:

  f9800420  prfm pldl1keep, [x1, #8]
  d4202000  brk #0x100

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/lib/insn.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
index e70ac0238515..98a047de5e67 100644
--- a/arch/arm64/lib/insn.c
+++ b/arch/arm64/lib/insn.c
@@ -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:
-- 
2.43.0

[PATCH bpf-next 05/21] bpf, arm64: Keep the ll/sc atomics address apart from the old value

[Daniel Borkmann]

The ll/sc versions of the fetching atomics load the old value into the
source register, or into r0 for cmpxchg, and then store through the
address register. With a zero offset the address register is dst_reg
itself, so for src_reg == dst_reg of a fetch or xchg, or dst_reg == r0
of a cmpxchg, the ldxr overwrites the address and the stlxr stores to
whatever the old value was. The verifier keeps such programs away from
the JIT today, but the JIT should not depend on it. The LSE versions are
not affected, LD<op>, SWP and CAS have no register overlap constraint.

Take a copy of the address when the register taking the old value is
the address register.

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

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 7d5eb949cdf4..b651b4ba3e63 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -870,6 +870,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;
 
@@ -883,6 +884,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) {
-- 
2.43.0

[PATCH bpf-next 06/21] arm64, insn: Add the LDUR/STUR, UMULH/SMULH and TBZ/TBNZ encodings

[Daniel Borkmann]

Add the encodings the BPF JIT needs for its shorter sequences:

  - LDUR, STUR and LDURS{B,H,W}, the loads and stores with a signed
    9-bit byte offset, for the negative and unaligned offsets the
    scaled forms cannot encode.
  - UMULH and SMULH, as data-processing (3 source) instructions with Ra
    fixed to the zero register, for the division by a constant.
  - TBZ and TBNZ, the test bit and branch within 32KB.
  - An extend parameter for the register offset loads and stores, for
    UXTW of a 32-bit offset register, which keeps the LSL form for
    UXTX, and a shift type parameter for the shifted register adds and
    subs, for LSR and ASR next to LSL.

The JIT is the only user of the two extended encoders and passes what it
emits today, along with the bpf_jit.h macros for TBZ, TBNZ and the
shifted adds and subs. The sign extending loads with a register offset
carried the equivalent SXTX in their template and take UXTX now like the
other loads and stores, the same access through a 64-bit offset
register.

Like the scaled and register offset forms, the unscaled sign extending
loads reject the 64-bit size, which would encode PRFUM.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/include/asm/insn.h |  33 ++++++++-
 arch/arm64/lib/insn.c         | 135 ++++++++++++++++++++++++++++++++++
 arch/arm64/net/bpf_jit.h      |  28 ++++++-
 3 files changed, 192 insertions(+), 4 deletions(-)

diff --git a/arch/arm64/include/asm/insn.h b/arch/arm64/include/asm/insn.h
index 1ce75a442638..f469106c1508 100644
--- a/arch/arm64/include/asm/insn.h
+++ b/arch/arm64/include/asm/insn.h
@@ -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,15 @@ enum aarch64_insn_adsb_type {
 	AARCH64_INSN_ADSB_SUB_SETFLAGS
 };
 
-/* option field of add/sub (extended register) */
+/* shift field of the shifted register forms */
+enum aarch64_insn_shift_type {
+	AARCH64_INSN_SHIFT_LSL,
+	AARCH64_INSN_SHIFT_LSR,
+	AARCH64_INSN_SHIFT_ASR,
+	AARCH64_INSN_SHIFT_ROR,
+};
+
+/* option field of add/sub (extended register) and load/store (register) */
 enum aarch64_insn_extend_type {
 	AARCH64_INSN_EXTEND_UXTB,
 	AARCH64_INSN_EXTEND_UXTH,
@@ -247,6 +260,8 @@ enum aarch64_insn_data2_type {
 enum aarch64_insn_data3_type {
 	AARCH64_INSN_DATA3_MADD,
 	AARCH64_INSN_DATA3_MSUB,
+	AARCH64_INSN_DATA3_UMULH,
+	AARCH64_INSN_DATA3_SMULH,
 };
 
 enum aarch64_insn_logic_type {
@@ -353,6 +368,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)
@@ -396,6 +414,8 @@ __AARCH64_INSN_FUNCS(sub_ext,	0x7FE00000, 0x4B200000)
 __AARCH64_INSN_FUNCS(subs_ext,	0x7FE00000, 0x6B200000)
 __AARCH64_INSN_FUNCS(madd,	0x7FE08000, 0x1B000000)
 __AARCH64_INSN_FUNCS(msub,	0x7FE08000, 0x1B008000)
+__AARCH64_INSN_FUNCS(umulh,	0xFFE0FC00, 0x9BC07C00)
+__AARCH64_INSN_FUNCS(smulh,	0xFFE0FC00, 0x9B407C00)
 __AARCH64_INSN_FUNCS(udiv,	0x7FE0FC00, 0x1AC00800)
 __AARCH64_INSN_FUNCS(sdiv,	0x7FE0FC00, 0x1AC00C00)
 __AARCH64_INSN_FUNCS(lslv,	0x7FE0FC00, 0x1AC02000)
@@ -582,6 +602,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);
 
@@ -606,6 +630,7 @@ 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,
 				    enum aarch64_insn_size_type size,
 				    enum aarch64_insn_ldst_type type);
 u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
@@ -613,6 +638,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);
@@ -650,6 +680,7 @@ u32 aarch64_insn_gen_movewide(enum aarch64_insn_register dst,
 u32 aarch64_insn_gen_add_sub_shifted_reg(enum aarch64_insn_register dst,
 					 enum aarch64_insn_register src,
 					 enum aarch64_insn_register reg,
+					 enum aarch64_insn_shift_type shift_type,
 					 int shift,
 					 enum aarch64_insn_variant variant,
 					 enum aarch64_insn_adsb_type type);
diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
index 98a047de5e67..544efe1fdefa 100644
--- a/arch/arm64/lib/insn.c
+++ b/arch/arm64/lib/insn.c
@@ -331,6 +331,48 @@ u32 aarch64_insn_gen_comp_branch_imm(unsigned long pc, unsigned long addr,
 					     offset >> 2);
 }
 
+/*
+ * TBZ and TBNZ test @bit of @reg, 0 to 63 with the 64-bit register implied
+ * from bit 32 on, and reach [-32K, 32K) bytes.
+ */
+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 insn;
+	long offset;
+
+	offset = label_imm_common(pc, addr, SZ_32K);
+	if (offset >= SZ_32K)
+		return AARCH64_BREAK_FAULT;
+
+	switch (type) {
+	case AARCH64_INSN_BRANCH_TEST_ZERO:
+		insn = aarch64_insn_get_tbz_value();
+		break;
+	case AARCH64_INSN_BRANCH_TEST_NONZERO:
+		insn = aarch64_insn_get_tbnz_value();
+		break;
+	default:
+		pr_err("%s: unknown branch encoding %d\n", __func__, type);
+		return AARCH64_BREAK_FAULT;
+	}
+
+	if (bit < 0 || bit > 63) {
+		pr_err("%s: invalid bit %d\n", __func__, bit);
+		return AARCH64_BREAK_FAULT;
+	}
+	/* b5 in bit 31 and b40 in bits [23:19] hold the bit number */
+	insn |= (u32)(bit >> 5) << 31;
+	insn |= (bit & 0x1f) << 19;
+
+	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn, reg);
+
+	return aarch64_insn_encode_immediate(AARCH64_INSN_IMM_14, insn,
+					     offset >> 2);
+}
+
 u32 aarch64_insn_gen_cond_branch_imm(unsigned long pc, unsigned long addr,
 				     enum aarch64_insn_condition cond)
 {
@@ -376,9 +418,15 @@ u32 aarch64_insn_gen_branch_reg(enum aarch64_insn_register reg,
 	return aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RN, insn, reg);
 }
 
+/*
+ * The offset register is extended per @extend: the 64-bit register as it is
+ * for UXTX and SXTX, the low 32 bits of it zero or sign extended for UXTW and
+ * SXTW. It is never scaled by the access size here.
+ */
 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,
 				    enum aarch64_insn_size_type size,
 				    enum aarch64_insn_ldst_type type)
 {
@@ -405,6 +453,20 @@ u32 aarch64_insn_gen_load_store_reg(enum aarch64_insn_register reg,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	switch (extend) {
+	case AARCH64_INSN_EXTEND_UXTW:
+	case AARCH64_INSN_EXTEND_UXTX:
+	case AARCH64_INSN_EXTEND_SXTW:
+	case AARCH64_INSN_EXTEND_SXTX:
+		/* option in bits [15:13], S in bit 12 clear for no scaling */
+		insn &= ~GENMASK(15, 12);
+		insn |= extend << 13;
+		break;
+	default:
+		pr_err("%s: invalid extend encoding %d\n", __func__, extend);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	insn = aarch64_insn_encode_ldst_size(size, insn);
 
 	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn, reg);
@@ -469,6 +531,50 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
 	return aarch64_insn_encode_immediate(AARCH64_INSN_IMM_12, insn, imm);
 }
 
+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 insn;
+
+	if (imm < -SZ_256 || imm >= SZ_256) {
+		pr_err("%s: invalid imm: %d\n", __func__, imm);
+		return AARCH64_BREAK_FAULT;
+	}
+
+	switch (type) {
+	case AARCH64_INSN_LDST_LOAD_UNSCALED_IMM_OFFSET:
+		insn = aarch64_insn_get_ldur_value();
+		break;
+	case AARCH64_INSN_LDST_SIGNED_LOAD_UNSCALED_IMM_OFFSET:
+		/* With the size of 64 bits this encodes PRFUM */
+		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_ldur_value();
+		break;
+	case AARCH64_INSN_LDST_STORE_UNSCALED_IMM_OFFSET:
+		insn = aarch64_insn_get_stur_value();
+		break;
+	default:
+		pr_err("%s: unknown load/store encoding %d\n", __func__, type);
+		return AARCH64_BREAK_FAULT;
+	}
+
+	insn = aarch64_insn_encode_ldst_size(size, insn);
+
+	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn, reg);
+
+	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RN, insn,
+					    base);
+
+	return aarch64_insn_encode_immediate(AARCH64_INSN_IMM_9, insn, imm);
+}
+
 u32 aarch64_insn_gen_load_literal(unsigned long pc, unsigned long addr,
 				  enum aarch64_insn_register reg,
 				  bool is64bit)
@@ -943,6 +1049,7 @@ u32 aarch64_insn_gen_movewide(enum aarch64_insn_register dst,
 u32 aarch64_insn_gen_add_sub_shifted_reg(enum aarch64_insn_register dst,
 					 enum aarch64_insn_register src,
 					 enum aarch64_insn_register reg,
+					 enum aarch64_insn_shift_type shift_type,
 					 int shift,
 					 enum aarch64_insn_variant variant,
 					 enum aarch64_insn_adsb_type type)
@@ -967,6 +1074,19 @@ u32 aarch64_insn_gen_add_sub_shifted_reg(enum aarch64_insn_register dst,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	switch (shift_type) {
+	case AARCH64_INSN_SHIFT_LSL:
+	case AARCH64_INSN_SHIFT_LSR:
+	case AARCH64_INSN_SHIFT_ASR:
+		/* shift type in bits [23:22], ROR is reserved for add/sub */
+		insn |= shift_type << 22;
+		break;
+	default:
+		pr_err("%s: invalid shift type encoding %d\n", __func__,
+		       shift_type);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	switch (variant) {
 	case AARCH64_INSN_VARIANT_32BIT:
 		if (shift & ~(SZ_32 - 1)) {
@@ -1167,11 +1287,26 @@ u32 aarch64_insn_gen_data3(enum aarch64_insn_register dst,
 	case AARCH64_INSN_DATA3_MSUB:
 		insn = aarch64_insn_get_msub_value();
 		break;
+	case AARCH64_INSN_DATA3_UMULH:
+		insn = aarch64_insn_get_umulh_value();
+		break;
+	case AARCH64_INSN_DATA3_SMULH:
+		insn = aarch64_insn_get_smulh_value();
+		break;
 	default:
 		pr_err("%s: unknown data3 encoding %d\n", __func__, type);
 		return AARCH64_BREAK_FAULT;
 	}
 
+	if ((type == AARCH64_INSN_DATA3_UMULH ||
+	     type == AARCH64_INSN_DATA3_SMULH) &&
+	    (variant != AARCH64_INSN_VARIANT_64BIT ||
+	     src != AARCH64_INSN_REG_ZR)) {
+		pr_err("%s: invalid variant or Ra for multiply high\n",
+		       __func__);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	switch (variant) {
 	case AARCH64_INSN_VARIANT_32BIT:
 		break;
diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index af570c34a96d..fa2a57e6d90d 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -26,6 +26,13 @@
 #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)
 
+/* 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, (imm14) << 2, ZERO)
+#define A64_TBNZ(Rt, bit, imm14) A64_TEST_BRANCH(Rt, bit, (imm14) << 2, NONZERO)
+
 /* Conditional branch (immediate) */
 #define A64_COND_BRANCH(cond, offset) \
 	aarch64_insn_gen_cond_branch_imm(0, offset, cond)
@@ -54,7 +61,7 @@
 
 /* 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_gen_load_store_reg(Rt, Rn, Rm, AARCH64_INSN_EXTEND_UXTX, \
 		AARCH64_INSN_SIZE_##size, \
 		AARCH64_INSN_LDST_##type##_REG_OFFSET)
 #define A64_STRB(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 8, STORE)
@@ -231,11 +238,26 @@
 #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, stype, shift, type) \
+	aarch64_insn_gen_add_sub_shifted_reg(Rd, Rn, Rm, \
+		AARCH64_INSN_SHIFT_##stype, shift, \
 		A64_VARIANT(sf), AARCH64_INSN_ADSB_##type)
+#define A64_ADDSUB_SREG(sf, Rd, Rn, Rm, type) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, LSL, 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, LSL, shift, ADD)
+/* Rd = Rn + (Rm >> shift) */
+#define A64_ADD_LSR(sf, Rd, Rn, Rm, shift) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, LSR, shift, ADD)
+/* Rd = Rn - (Rm << shift) */
+#define A64_SUB_LSL(sf, Rd, Rn, Rm, shift) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, LSL, shift, SUB)
+/* Rd = Rn - (Rm >> shift); signed */
+#define A64_SUB_ASR(sf, Rd, Rn, Rm, shift) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, ASR, 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 */
-- 
2.43.0

[PATCH bpf-next 07/21] bpf: Move the division magic number computation out of the x86 JIT

[Daniel Borkmann]

bpf_magic_udiv() and bpf_magic_sdiv() compute the multiplier and shift
for the division by a constant and have nothing x86 specific, so move
them to the core for the other JITs to use. They divide 64-bit values by
a divisor only known at run time, which a 32-bit kernel has no inline
form for, so they come under CONFIG_64BIT like the JITs which can use
them. No functional change.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/x86/net/bpf_jit_comp.c | 97 -------------------------------------
 include/linux/filter.h      | 11 +++++
 kernel/bpf/core.c           | 93 +++++++++++++++++++++++++++++++++++
 3 files changed, 104 insertions(+), 97 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 6a2fe3d0039d..8eeeefbde0cb 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2066,103 +2066,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
diff --git a/include/linux/filter.h b/include/linux/filter.h
index e0218e677a1d..f2e5e70c0aff 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -1483,6 +1483,17 @@ void bpf_jit_binary_pack_free(struct bpf_binary_header *ro_header,
 int bpf_jit_add_poke_descriptor(struct bpf_prog *prog,
 				struct bpf_jit_poke_descriptor *poke);
 
+#ifdef CONFIG_64BIT
+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 */
+};
+
+void bpf_magic_udiv(u64 d, int lz, struct bpf_div_magic *mag);
+void bpf_magic_sdiv(s64 d, struct bpf_div_magic *mag);
+#endif
+
 int bpf_jit_get_func_addr(const struct bpf_prog *prog,
 			  const struct bpf_insn *insn, bool extra_pass,
 			  u64 *func_addr, bool *func_addr_fixed);
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 3030beb531d9..14f643c49d84 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -1312,6 +1312,99 @@ void __weak bpf_jit_free(struct bpf_prog *fp)
 	bpf_prog_unlock_free(fp);
 }
 
+#ifdef CONFIG_64BIT
+/*
+ * 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.
+ */
+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.
+ */
+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;
+}
+#endif /* CONFIG_64BIT */
+
 int bpf_jit_get_func_addr(const struct bpf_prog *prog,
 			  const struct bpf_insn *insn, bool extra_pass,
 			  u64 *func_addr, bool *func_addr_fixed)
-- 
2.43.0

[PATCH bpf-next 08/21] bpf, arm64: Consolidate the load and store emission into a helper

[Daniel Borkmann]

The BPF_LDX, BPF_ST and BPF_STX cases each pick the base and offset of
an access through the frame pointer, and then switch over the access
size to emit the immediate offset form or the register offset fallback,
three times the same code. Add emit_ldst() for it, with the A64 size
and type derived from the instruction. The emitted code is unchanged.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 227 +++++++++++-----------------------
 1 file changed, 71 insertions(+), 156 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index b651b4ba3e63..4dc465772937 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -346,6 +346,74 @@ static bool is_lsi_offset(int offset, int scale)
 	return true;
 }
 
+/* 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)
+{
+	switch (BPF_SIZE(code)) {
+	case BPF_B:
+		*scale = 0;
+		return AARCH64_INSN_SIZE_8;
+	case BPF_H:
+		*scale = 1;
+		return AARCH64_INSN_SIZE_16;
+	case BPF_W:
+		*scale = 2;
+		return AARCH64_INSN_SIZE_32;
+	default:
+		*scale = 3;
+		return AARCH64_INSN_SIZE_64;
+	}
+}
+
+/* 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)
+{
+	if (BPF_CLASS(code) != BPF_LDX)
+		return reg_offset ? AARCH64_INSN_LDST_STORE_REG_OFFSET :
+				    AARCH64_INSN_LDST_STORE_IMM_OFFSET;
+	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;
+}
+
+/*
+ * Load or store of a BPF access size at rn + off. An access through the
+ * frame pointer goes from the stack pointer, or from the private stack
+ * pointer, with the offset adjusted by the frame size, and takes the
+ * frame pointer register for the register offset form.
+ */
+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;
+	s32 off_adj = off;
+	u8 rn_adj = rn;
+	int scale;
+
+	size = a64_ldst_size(code, &scale);
+	if (rn == bpf2a64[BPF_REG_FP]) {
+		if (ctx->priv_sp_used) {
+			rn_adj = bpf2a64[PRIVATE_SP];
+			off_adj += ctx->stack_size;
+		} else {
+			rn_adj = A64_SP;
+			off_adj += ctx->stack_size + ctx->stack_arg_size;
+		}
+	}
+
+	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);
+	} else {
+		emit_a64_mov_i(1, tmp, off, ctx);
+		emit(aarch64_insn_gen_load_store_reg(rt, rn, tmp, AARCH64_INSN_EXTEND_UXTX,
+						     size, a64_ldst_type(code, true)), ctx);
+	}
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -1444,9 +1512,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	const u8 tmp = bpf2a64[TMP_REG_1];
 	const u8 tmp2 = bpf2a64[TMP_REG_2];
 	const u8 tmp3 = bpf2a64[TMP_REG_3];
-	const u8 fp = bpf2a64[BPF_REG_FP];
 	const u8 arena_vm_base = bpf2a64[ARENA_VM_START];
-	const u8 priv_sp = bpf2a64[PRIVATE_SP];
 	const s16 off = insn->off;
 	const s32 imm = insn->imm;
 	const int i = insn - ctx->prog->insnsi;
@@ -1455,11 +1521,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	u8 jmp_cond;
 	s32 jmp_offset;
 	u32 a64_insn;
-	u8 src_adj;
-	u8 dst_adj;
-	int off_adj;
 	int ret;
-	bool sign_extend;
 
 	if (bpf_insn_is_indirect_target(env, ctx->prog, i))
 		emit_bti(A64_BTI_J, ctx);
@@ -1952,70 +2014,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			emit(A64_ADD(1, tmp2, src, arena_vm_base), ctx);
 			src = tmp2;
 		}
-		if (src == fp) {
-			src_adj = ctx->priv_sp_used ? priv_sp : A64_SP;
-			off_adj = off + ctx->stack_size;
-			if (!ctx->priv_sp_used)
-				off_adj += ctx->stack_arg_size;
-		} else {
-			src_adj = src;
-			off_adj = off;
-		}
-		sign_extend = (BPF_MODE(insn->code) == BPF_MEMSX ||
-				BPF_MODE(insn->code) == BPF_PROBE_MEMSX ||
-				 BPF_MODE(insn->code) == BPF_PROBE_MEM32SX);
-		switch (BPF_SIZE(code)) {
-		case BPF_W:
-			if (is_lsi_offset(off_adj, 2)) {
-				if (sign_extend)
-					emit(A64_LDRSWI(dst, src_adj, off_adj), ctx);
-				else
-					emit(A64_LDR32I(dst, src_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				if (sign_extend)
-					emit(A64_LDRSW(dst, src, tmp), ctx);
-				else
-					emit(A64_LDR32(dst, src, tmp), ctx);
-			}
-			break;
-		case BPF_H:
-			if (is_lsi_offset(off_adj, 1)) {
-				if (sign_extend)
-					emit(A64_LDRSHI(dst, src_adj, off_adj), ctx);
-				else
-					emit(A64_LDRHI(dst, src_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				if (sign_extend)
-					emit(A64_LDRSH(dst, src, tmp), ctx);
-				else
-					emit(A64_LDRH(dst, src, tmp), ctx);
-			}
-			break;
-		case BPF_B:
-			if (is_lsi_offset(off_adj, 0)) {
-				if (sign_extend)
-					emit(A64_LDRSBI(dst, src_adj, off_adj), ctx);
-				else
-					emit(A64_LDRBI(dst, src_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				if (sign_extend)
-					emit(A64_LDRSB(dst, src, tmp), ctx);
-				else
-					emit(A64_LDRB(dst, src, tmp), ctx);
-			}
-			break;
-		case BPF_DW:
-			if (is_lsi_offset(off_adj, 3)) {
-				emit(A64_LDR64I(dst, src_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				emit(A64_LDR64(dst, src, tmp), ctx);
-			}
-			break;
-		}
+		emit_ldst(code, dst, src, off, tmp, ctx);
 
 		ret = add_exception_handler(insn, ctx, dst);
 		if (ret)
@@ -2050,51 +2049,9 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			emit(A64_ADD(1, tmp3, dst, arena_vm_base), ctx);
 			dst = tmp3;
 		}
-		if (dst == fp) {
-			dst_adj = ctx->priv_sp_used ? priv_sp : A64_SP;
-			off_adj = off + ctx->stack_size;
-			if (!ctx->priv_sp_used)
-				off_adj += ctx->stack_arg_size;
-		} else {
-			dst_adj = dst;
-			off_adj = off;
-		}
 		/* Load imm to a register then store it */
 		emit_a64_mov_i(1, tmp, imm, ctx);
-		switch (BPF_SIZE(code)) {
-		case BPF_W:
-			if (is_lsi_offset(off_adj, 2)) {
-				emit(A64_STR32I(tmp, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp2, off, ctx);
-				emit(A64_STR32(tmp, dst, tmp2), ctx);
-			}
-			break;
-		case BPF_H:
-			if (is_lsi_offset(off_adj, 1)) {
-				emit(A64_STRHI(tmp, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp2, off, ctx);
-				emit(A64_STRH(tmp, dst, tmp2), ctx);
-			}
-			break;
-		case BPF_B:
-			if (is_lsi_offset(off_adj, 0)) {
-				emit(A64_STRBI(tmp, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp2, off, ctx);
-				emit(A64_STRB(tmp, dst, tmp2), ctx);
-			}
-			break;
-		case BPF_DW:
-			if (is_lsi_offset(off_adj, 3)) {
-				emit(A64_STR64I(tmp, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp2, off, ctx);
-				emit(A64_STR64(tmp, dst, tmp2), ctx);
-			}
-			break;
-		}
+		emit_ldst(code, tmp, dst, off, tmp2, ctx);
 
 		ret = add_exception_handler(insn, ctx, DONT_CLEAR);
 		if (ret)
@@ -2119,49 +2076,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			emit(A64_ADD(1, tmp2, dst, arena_vm_base), ctx);
 			dst = tmp2;
 		}
-		if (dst == fp) {
-			dst_adj = ctx->priv_sp_used ? priv_sp : A64_SP;
-			off_adj = off + ctx->stack_size;
-			if (!ctx->priv_sp_used)
-				off_adj += ctx->stack_arg_size;
-		} else {
-			dst_adj = dst;
-			off_adj = off;
-		}
-		switch (BPF_SIZE(code)) {
-		case BPF_W:
-			if (is_lsi_offset(off_adj, 2)) {
-				emit(A64_STR32I(src, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				emit(A64_STR32(src, dst, tmp), ctx);
-			}
-			break;
-		case BPF_H:
-			if (is_lsi_offset(off_adj, 1)) {
-				emit(A64_STRHI(src, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				emit(A64_STRH(src, dst, tmp), ctx);
-			}
-			break;
-		case BPF_B:
-			if (is_lsi_offset(off_adj, 0)) {
-				emit(A64_STRBI(src, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				emit(A64_STRB(src, dst, tmp), ctx);
-			}
-			break;
-		case BPF_DW:
-			if (is_lsi_offset(off_adj, 3)) {
-				emit(A64_STR64I(src, dst_adj, off_adj), ctx);
-			} else {
-				emit_a64_mov_i(1, tmp, off, ctx);
-				emit(A64_STR64(src, dst, tmp), ctx);
-			}
-			break;
-		}
+		emit_ldst(code, src, dst, off, tmp, ctx);
 
 		ret = add_exception_handler(insn, ctx, DONT_CLEAR);
 		if (ret)
-- 
2.43.0

[PATCH bpf-next 09/21] bpf, arm64: Use the unscaled forms for negative and unaligned offsets

[Daniel Borkmann]

A load or store with a negative offset, or with one that is not a multiple
of the access size, does not fit the scaled unsigned 12-bit immediate form
and was emitted as a mov of the offset into a temporary followed by the
register offset form. LDUR and STUR take a signed 9-bit byte offset, so
use them for the offsets from -256 to 255 the other form cannot encode,
which saves the mov. The unscaled forms have the same latency and issue
on the same pipelines as the scaled ones on Neoverse N1 through V3. LLVM
emits such offsets for every 32-bit and wider header field behind the
14-byte Ethernet header of a packet parser, and negative ones for the
container of a list or rbtree node.

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]

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 53 +++++++++++++++++++++++++++--------
 1 file changed, 41 insertions(+), 12 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 4dc465772937..b57420391282 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -346,6 +346,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)
 {
@@ -365,18 +371,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];
 }
 
 /*
@@ -389,6 +413,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;
@@ -405,12 +430,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,
-						     size, a64_ldst_type(code, true)), ctx);
+						     size, type), ctx);
 	}
 }
 
-- 
2.43.0

[PATCH bpf-next 10/21] bpf, arm64: Store zero immediates from the zero register

[Daniel Borkmann]

A store of an immediate first moves it into a temporary, also for a zero,
which the zero register provides for free. Store it from xzr, which saves
the mov on every zeroing of a stack slot, as LLVM with cpu v4 emits them
in rows to initialize the structs and arrays BPF programs hand 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]

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index b57420391282..c54f39a8b679 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -2078,9 +2078,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			emit(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)
-- 
2.43.0

[PATCH bpf-next 11/21] bpf, arm64: Zero extend the arena offset in register offset accesses

[Daniel Borkmann]

An arena access added the register holding the 32-bit arena offset to
the kernel base of the arena with a 64-bit add and went through the sum
with the immediate offset. That relies on the verifier to keep the upper
32 bits of the register zero, and any slip there would let the access
escape the 4GB arena into whatever the kernel maps next to it.

Take the register offset form with UXTW instead, which zero extends the
offset register in the access itself, so that it stays within the arena
and its guard pages whatever the upper half holds. Without an immediate
offset this also saves the add and its cycle on every access. With one,
the offset is added to the arena base first, off the path of the offset
register, which shortens that path by a cycle. The add takes offsets up
to 4095 in magnitude and multiples of 4K as its immediate, two
instructions, one fewer than before for negative offsets below -256,
unaligned ones above 255 and multiples of 4K beyond the reach of the
scaled forms, and any other offset needs a move, three instructions
where the load or store took two for most aligned offsets from 4K on.
The atomics, whose base must be a register, add the extended offset onto
the base, a cycle more on that path without an immediate offset at the
same number of instructions. The exception handler is unaffected, it
reports the fault from the offset register, which the access leaves
intact, and the immediate offset.

Update the arm64 expectations of the Arena LDSX Disasm test of
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]

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c                 | 91 +++++++++++++------
 .../selftests/bpf/progs/verifier_ldsx.c       | 24 ++---
 2 files changed, 77 insertions(+), 38 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index c54f39a8b679..8b416c74858e 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -443,6 +443,29 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off,
 	}
 }
 
+/*
+ * Load or store at an arena address: the register holds the offset into
+ * the arena in its low 32 bits, which the register offset form adds zero
+ * extended to the base register, the arena base with the immediate offset
+ * added into tmp_addr first, off the path of the register. The verifier
+ * keeps the upper 32 bits zero, the extension keeps the access in the
+ * arena and its guard regardless.
+ */
+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,
+					     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
@@ -823,6 +846,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) {
@@ -837,12 +861,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;
 	}
 
@@ -896,17 +929,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;
 	}
 
@@ -1541,7 +1584,6 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	const 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;
@@ -2039,11 +2081,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	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;
-		}
-		emit_ldst(code, dst, src, off, tmp, ctx);
+		    BPF_MODE(insn->code) == BPF_PROBE_MEM32SX)
+			emit_arena_ldst(code, dst, src, off, tmp2, tmp, ctx);
+		else
+			emit_ldst(code, dst, src, off, tmp, ctx);
 
 		ret = add_exception_handler(insn, ctx, dst);
 		if (ret)
@@ -2074,14 +2115,13 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	case 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)
@@ -2102,11 +2142,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	case 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)
diff --git a/tools/testing/selftests/bpf/progs/verifier_ldsx.c b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
index 49e8cd4bb4f9..03adebb4acbc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_ldsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
@@ -276,18 +276,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)")
-- 
2.43.0

[PATCH bpf-next 12/21] bpf, arm64: Adjust compares with unencodable immediates by one

[Daniel Borkmann]

cmp and cmn take a 12-bit immediate, optionally shifted by 12, so a
compare against any other constant moved the constant into a temporary
first. LLVM canonicalizes x <= C to x < C + 1 and x >= C to x > C - 1,
so compares against a power of two or a mask, such as a length against
a page size or a 16-bit limit, reach the JIT as compares against their
neighbors and took the extra mov. When the neighbor fits, compare
against it with the adjusted condition instead, x < C as x <= C - 1 and
x > C as x >= C + 1, unsigned and signed alike.

Before/after for if r1 < 4097 goto ... and if r1 > 65535 goto ...:

  d282002a  mov x10, #0x1001
  eb0a001f  cmp x0, x10
  54000063  b.lo ...
  f140041f  cmp x0, #0x1, lsl #12
  54000049  b.ls ...

  d29fffea  mov x10, #0xffff
  eb0a001f  cmp x0, x10
  54000068  b.hi ...
  f140401f  cmp x0, #0x10, lsl #12
  54000042  b.hs ...

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++++++++---
 1 file changed, 80 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 8b416c74858e..90cbde8f96b6 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -466,6 +466,76 @@ static void emit_arena_ldst(const u8 code, const u8 rt, const u8 reg, const s32
 					     a64_ldst_type(code, A64_LDST_REG)), ctx);
 }
 
+/*
+ * A compare against an immediate neither cmp nor cmn can encode is one
+ * against its neighbor with the adjusted condition when that one fits:
+ * x < C is x <= C - 1 and x > C is x >= C + 1, for the unsigned as for the
+ * signed conditions, as long as C - 1 or C + 1 does not wrap. LLVM
+ * canonicalizes x <= C to x < C + 1, so the compares against a power of
+ * two or a mask plus one arrive 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
@@ -1589,6 +1659,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	const 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;
@@ -1865,7 +1937,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;
@@ -1927,12 +1999,14 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	case 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;
-- 
2.43.0

[PATCH bpf-next 13/21] bpf, arm64: Materialize immediates with fewer instructions

[Daniel Borkmann]

A 32-bit immediate with a zero or an all ones half took a movz or movn
and a movk even where the shifted movz or movn alone produces it, and a
bitmask immediate, a run of ones or a repeating pattern such as all but
the sign bit, took two moves where an orr with the zero register does it
in one, at the same single cycle of latency. A 64-bit immediate with a
16-bit chunk repeating, whose replication is a bitmask immediate, takes
that orr and a movk per other chunk, which is the form of the magic
numbers of the divisions by 3, 5, 15 and 17, among others, that a later
patch emits. Try these forms before falling back to the move pairs.

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

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 77 ++++++++++++++++++++++++++++++-----
 1 file changed, 67 insertions(+), 10 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 90cbde8f96b6..d1cea58ca8ee 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -123,24 +123,49 @@ 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: a single movz
+ * or movn when one half is zero or all ones and the other half agrees with
+ * the sign the 64-bit variant extends, a single orr when it is a bitmask
+ * immediate, and the pair of a movz or movn with a movk otherwise.
+ */
 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);
 	}
 }
 
@@ -157,10 +182,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 one orr rather than two or more moves */
+	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) :
-- 
2.43.0

[PATCH bpf-next 14/21] bpf, arm64: Shorten the tail call sequence

[Daniel Borkmann]

The tail call moved the offsets of max_entries and ptrs of the array and
of bpf_func of the prog into a temporary before using them, and the tail
call limit before its compare, although all of them fit the immediate
forms, and it zero extended the index before shifting it. Use the
immediate forms and a ubfiz, which zero extends and scales the index in
one, five instructions fewer for every tail call.

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
  54000222  b.hs ...
  f940034c  ldr x12, [x26]
  f100859f  cmp x12, #0x21
  540001c2  b.hs ...
  9100058c  add x12, x12, #0x1
  9108802a  add x10, x1, #0x220
  d37d7c4b  ubfiz x11, x2, #3, #32
  f86b694b  ldr x11, [x10, x11]
  b400012b  cbz x11, ...

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h      |  3 +++
 arch/arm64/net/bpf_jit_comp.c | 23 +++++++++++++----------
 2 files changed, 16 insertions(+), 10 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index fa2a57e6d90d..a6dfff8c645f 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -220,6 +220,9 @@
 /* Zero extend */
 #define A64_UXTH(sf, Rd, Rn) A64_UBFM(sf, Rd, Rn, 0, 15)
 #define A64_UXTW(sf, Rd, Rn) A64_UBFM(sf, Rd, Rn, 0, 31)
+/* Rd = (Rn & (2^width - 1)) << lsb */
+#define A64_UBFIZ(sf, Rd, Rn, lsb, width) \
+	A64_UBFM(sf, Rd, Rn, (unsigned int)-(lsb) % ((sf) ? 64 : 32), (width) - 1)
 
 /* Sign extend */
 #define A64_SXTB(sf, Rd, Rn) A64_SBFM(sf, Rd, Rn, 0, 7)
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index d1cea58ca8ee..b21e744dab6a 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -894,13 +894,19 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 	__le32 *branch2 = NULL;
 	__le32 *branch3 = NULL;
 
+	/* 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 (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);
@@ -909,9 +915,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);
 
@@ -923,9 +928,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_ADD_I(1, tmp, r2, off), ctx);
+	emit(A64_UBFIZ(1, prg, r3, 3, 32), ctx);
 	emit(A64_LDR64(prg, tmp, prg), ctx);
 	branch3 = ctx->image + ctx->idx;
 	emit(A64_NOP, ctx);
@@ -944,8 +948,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);
 
-- 
2.43.0

[PATCH bpf-next 15/21] bpf, arm64: Divide by constants via multiplication with a magic number

[Daniel Borkmann]

LLVM strength-reduces 32-bit divisions by a constant into a 64-bit
multiplication, but has no high-half multiply for the 64-bit ones, so
these reach the JIT as BPF_DIV/BPF_MOD with BPF_K and were emitted as
udiv or sdiv, which take 5 to 20 cycles on Neoverse N1 through V3 and
block the one divider of the core until done, whereas umulh and smulh
take 3 cycles and issue twice per cycle on N2 and later, 5 cycles on N1.
Cilium divides by NSEC_PER_SEC this way in its monotonic clock helper,
which conntrack, NAT and the load balancer run for every entry they
stamp or check.

Emit the multiplication with a magic number from bpf_magic_udiv() and
bpf_magic_sdiv() instead, as the x86 JIT does: an unsigned division
becomes an umulh and a shift, with the sub/add/shift correction when the
magic number needs 65 bits, which an even divisor avoids by shifting the
dividend by its trailing zeros first, a signed one an smulh, an optional
add or sub of the dividend, an asr and the add of the sign bit, with the
shifts of the corrections folded into the adds. A modulo takes the
quotient back with an msub. A power of two is a shift or a mask, and in
the signed case a shift with the bias of 2^k - 1 for a negative dividend
taken from the sign mask. Divisors 0 and +-1, unsigned divisors above
2^63 (negative imm32) and the 32-bit divisions stay with udiv/sdiv.

On the dependent path the unsigned division by 100 goes from the 20
cycles that llvm-mca models for the udiv down to 5 on Neoverse N2, V1
and V2 and 7 on N1, for five more instructions, where no division takes
more than six more and no modulo more than seven. The emitted sequences
were run on qemu-system-aarch64 against the C division for the divisors
from -2100 to 2099 and random ones, signed and unsigned, with dividends
at the extremes, around the divisor and a multiple of it, and at random.

Before/after for r1 /= 1000000000:

  d299400a  mov x10, #0xca00
  f2a7734a  movk x10, #0x3b9a, lsl #16
  9aca0800  udiv x0, x0, x10

  d2e0088a  mov x10, #0x44000000000000
  f2d705ea  movk x10, #0xb82f, lsl #32
  f2b4136a  movk x10, #0xa09b, lsl #16
  f28b4a6a  movk x10, #0x5a53
  d349fc0b  lsr x11, x0, #9
  9bca7d6a  umulh x10, x11, x10
  d34bfd40  lsr x0, x10, #11

Before/after for r1 s/= 10 and r1 s/= 8:

  d280014a  mov x10, #0xa
  9aca0c00  sdiv x0, x0, x10

  b203e7ea  mov x10, #0x6666666666666666
  f28cccea  movk x10, #0x6667
  9b4a7c0a  smulh x10, x0, x10
  9342fd4a  asr x10, x10, #2
  8b4afd40  add x0, x10, x10, lsr #63

  d280010a  mov x10, #0x8
  9aca0c00  sdiv x0, x0, x10

  937ffc0a  asr x10, x0, #63
  8b4af40a  add x10, x0, x10, lsr #61
  9343fd40  asr x0, x10, #3

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h      |   5 ++
 arch/arm64/net/bpf_jit_comp.c | 139 ++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index a6dfff8c645f..7c681a822c06 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -306,6 +306,11 @@
 	A64_VARIANT(sf), AARCH64_INSN_DATA3_MSUB)
 /* Rd = Rn * Rm */
 #define A64_MUL(sf, Rd, Rn, Rm) A64_MADD(sf, Rd, A64_ZR, Rn, Rm)
+/* Rd = (Rn * Rm) >> 64, unsigned and signed */
+#define A64_UMULH(Rd, Rn, Rm) aarch64_insn_gen_data3(Rd, A64_ZR, Rn, Rm, \
+	AARCH64_INSN_VARIANT_64BIT, AARCH64_INSN_DATA3_UMULH)
+#define A64_SMULH(Rd, Rn, Rm) aarch64_insn_gen_data3(Rd, A64_ZR, Rn, Rm, \
+	AARCH64_INSN_VARIANT_64BIT, AARCH64_INSN_DATA3_SMULH)
 
 /* Logical (shifted register) */
 #define A64_LOGIC_SREG(sf, Rd, Rn, Rm, type) \
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index b21e744dab6a..d14a5cf6e032 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -593,6 +593,141 @@ static bool adjust_cmp_imm(u8 *op, s32 *imm)
 	return true;
 }
 
+/*
+ * Divide dst by the immediate of a 64-bit division through a multiplication
+ * with the magic number from bpf_magic_udiv() or bpf_magic_sdiv(): the high
+ * half of the product from umulh or smulh, shifted, with the corrections per
+ * Hacker's Delight. The quotient is built in tmp with tmp2 as scratch, the
+ * dividend stays in dst until a modulo takes the quotient back with msub.
+ * Returns false for the divisors left to udiv and sdiv.
+ */
+static bool emit_div_const(const struct bpf_insn *insn, struct jit_ctx *ctx)
+{
+	const bool is_mod = BPF_OP(insn->code) == BPF_MOD;
+	const bool is_signed = insn->off == 1;
+	const u8 dst = bpf2a64[insn->dst_reg];
+	const u8 tmp = bpf2a64[TMP_REG_1];
+	const u8 tmp2 = bpf2a64[TMP_REG_2];
+	const u8 q = is_mod ? tmp : dst;
+	const s32 imm = insn->imm;
+	struct bpf_div_magic mag;
+	int corr = 0, pre = 0, s;
+
+	if (is_signed) {
+		const u64 ad = imm < 0 ? -(u64)(s64)imm : imm;
+
+		/* |d| >= 2, the verifier already rewrote d == -1 */
+		if (imm >= -1 && imm <= 1)
+			return false;
+		/*
+		 * By a power of two with shifts: 2^k - 1 added to a negative
+		 * dividend rounds the arithmetic shift toward zero, the bias
+		 * is the low k bits of the sign mask, the sign bit itself for
+		 * k = 1. The modulo clears the low k bits of the biased
+		 * dividend for the multiple to subtract. A negative divisor
+		 * negates the quotient off the shift and keeps the remainder.
+		 */
+		if (is_power_of_2(ad)) {
+			const int k = ilog2(ad);
+
+			if (k == 1) {
+				emit(A64_ADD_LSR(1, tmp, dst, dst, 63), ctx);
+			} else {
+				emit(A64_ASR(1, tmp, dst, 63), ctx);
+				emit(A64_ADD_LSR(1, tmp, dst, tmp, 64 - k), ctx);
+			}
+			if (is_mod) {
+				emit(A64_AND_I(1, tmp, tmp, ~(ad - 1)), ctx);
+				emit(A64_SUB(1, dst, dst, tmp), ctx);
+			} else if (imm > 0) {
+				emit(A64_ASR(1, dst, tmp, k), ctx);
+			} else {
+				emit(A64_SUB_ASR(1, dst, A64_ZR, tmp, k), ctx);
+			}
+			return true;
+		}
+		bpf_magic_sdiv(imm, &mag);
+		/* q += n for d > 0 and m < 0, q -= n for d < 0 and m > 0 */
+		if (imm > 0 && (s64)mag.m < 0)
+			corr = 1;
+		else if (imm < 0 && (s64)mag.m > 0)
+			corr = -1;
+	} else {
+		/* d >= 2, a negative imm is a divisor above 2^63 */
+		if (imm < 2)
+			return false;
+		if (is_power_of_2(imm)) {
+			if (is_mod)
+				emit(A64_AND_I(1, dst, dst, imm - 1), ctx);
+			else
+				emit(A64_LSR(1, dst, dst, ilog2(imm)), ctx);
+			return true;
+		}
+		bpf_magic_udiv(imm, 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 && !(imm & 1)) {
+			pre = __ffs(imm) & 31;
+			bpf_magic_udiv(imm >> 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;
+
+	/* tmp = mulh(n >> pre, m) */
+	emit_a64_mov_i64(tmp, mag.m, ctx);
+	if (pre) {
+		emit(A64_LSR(1, tmp2, dst, pre), ctx);
+		emit(A64_UMULH(tmp, tmp2, tmp), ctx);
+	} else if (is_signed) {
+		emit(A64_SMULH(tmp, dst, tmp), ctx);
+	} else {
+		emit(A64_UMULH(tmp, dst, tmp), ctx);
+	}
+
+	if (is_signed) {
+		if (corr > 0)
+			emit(A64_ADD(1, tmp, tmp, dst), ctx);
+		else if (corr < 0)
+			emit(A64_SUB(1, tmp, tmp, dst), ctx);
+		if (s)
+			emit(A64_ASR(1, tmp, tmp, s), ctx);
+		/* q += q >>> 63 */
+		emit(A64_ADD_LSR(1, q, tmp, tmp, 63), ctx);
+	} else if (!mag.add) {
+		if (s)
+			emit(A64_LSR(1, q, tmp, s), ctx);
+		else if (q != tmp)
+			emit(A64_MOV(1, q, tmp), ctx);
+	} else {
+		/* q = (((n - t) >> 1) + t) >> (s - 1) */
+		emit(A64_SUB(1, tmp2, dst, tmp), ctx);
+		emit(A64_ADD_LSR(1, tmp, tmp, tmp2, 1), ctx);
+		if (s > 1)
+			emit(A64_LSR(1, q, tmp, s - 1), ctx);
+		else if (q != tmp)
+			emit(A64_MOV(1, q, tmp), ctx);
+	}
+
+	if (is_mod) {
+		/* dst = n - q * d */
+		emit_a64_mov_i(1, tmp2, imm, ctx);
+		emit(A64_MSUB(1, dst, dst, tmp, tmp2), ctx);
+	}
+	return true;
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -1930,6 +2065,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	case BPF_ALU | BPF_DIV | BPF_K:
 	case BPF_ALU64 | BPF_DIV | BPF_K:
+		if (is64 && emit_div_const(insn, ctx))
+			break;
 		emit_a64_mov_i(is64, tmp, imm, ctx);
 		if (!off)
 			emit(A64_UDIV(is64, dst, dst, tmp), ctx);
@@ -1938,6 +2075,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	case BPF_ALU | BPF_MOD | BPF_K:
 	case BPF_ALU64 | BPF_MOD | BPF_K:
+		if (is64 && emit_div_const(insn, ctx))
+			break;
 		emit_a64_mov_i(is64, tmp2, imm, ctx);
 		if (!off)
 			emit(A64_UDIV(is64, tmp, dst, tmp2), ctx);
-- 
2.43.0

[PATCH bpf-next 16/21] bpf, arm64: Use a move or mvn for the and and xor with all ones

[Daniel Borkmann]

The logical immediates cannot encode all ones, so the and, or and xor with
-1 moved the constant into a temporary and used the register form. LLVM
lowers a bitwise not to r ^= -1, as BPF has no not instruction, which the
Cilium datapath does hundreds of times. The xor with all ones is an mvn,
the 32-bit and with all ones a 32-bit mov of the register to itself and
the 64-bit one emits nothing, as the le64 of this JIT already does, and
the or with all ones a mov of -1.

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

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index d14a5cf6e032..c49f962ac229 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -2030,6 +2030,12 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	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);
@@ -2040,6 +2046,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	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);
@@ -2050,6 +2061,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	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);
-- 
2.43.0

[PATCH bpf-next 17/21] bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests

[Daniel Borkmann]

A compare against zero for equality, a test of the sign and a test of a
single bit were a cmp or tst followed by a conditional branch. CBZ and
CBNZ compare against zero and branch in one instruction with the same
19-bit offset as B.cond, and TBZ and TBNZ test a bit and branch. The
null check of a map lookup or pointer argument is the most frequent
compare in BPF programs, and LLVM emits the error checks as "if r s< 0"
and "if r s> -1", which test the sign, as do the unsigned 32-bit
compares at the sign bit. Neoverse N2, V2, V3 and N3 fuse a cmp or tst
with the following B.cond, so there the gain is the code size and a
decode slot, on cores without the fusion also the uop.

TBZ and TBNZ only reach 8K instructions where B.cond reaches 256K, so a
test takes them when its target is within reach. The sizing pass is
repeated with the offsets of the previous one until the code settles,
and where it has not after a few passes, all tests of the program keep
the compare and the branch. A branch back takes its distance from its
own position, as the offsets after it are still those of the previous
pass, which would overestimate the distance by what the code in front of
the branch shrank. The decisions are kept in a bitmap for the passes
over the image, which must not grow. A program without such a test takes
a single sizing pass as before.

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, ...

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 163 ++++++++++++++++++++++++++++++++--
 1 file changed, 157 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index c49f962ac229..08b95e3acaab 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -92,8 +92,17 @@ struct jit_ctx {
 	bool fp_used;
 	bool priv_sp_used;
 	bool write;
+	bool no_tb;
+	unsigned long *tb;
+	int tb_long;
 };
 
+/*
+ * Sizing passes in which a sign or bit test may still take the test bit and
+ * branch, see emit_tb(): the size settles within two more passes after that.
+ */
+#define TB_PASSES 8
+
 struct bpf_plt {
 	u32 insn_ldr; /* load target */
 	u32 insn_br;  /* branch to target */
@@ -314,8 +323,13 @@ static inline int bpf2a64_offset(int bpf_insn, int off,
 	/*
 	 * Whereas arm64 branch instructions encode the offset
 	 * from the branch itself, so we must subtract 1 from the
-	 * instruction offset.
+	 * instruction offset. A branch back takes its own position,
+	 * the next one emitted, as in a repeated sizing pass the
+	 * offsets from the next instruction on are still those of
+	 * the previous pass, see bpf_int_jit_compile().
 	 */
+	if (off < 0)
+		return ctx->offset[bpf_insn + off] - ctx->idx;
 	return ctx->offset[bpf_insn + off] - (ctx->offset[bpf_insn] - 1);
 }
 
@@ -593,6 +607,96 @@ static bool adjust_cmp_imm(u8 *op, s32 *imm)
 	return true;
 }
 
+/*
+ * A compare against zero or minus one for the sign, an unsigned 32-bit
+ * compare at the sign bit and a test of a single bit test a bit of the
+ * register: returns the bit, with *nonzero set when the branch is taken
+ * with it set, or -1.
+ */
+static int tb_bit(u8 op, bool is64, s32 imm, bool *nonzero)
+{
+	const int sign = is64 ? 63 : 31;
+	u64 mask;
+
+	switch (op) {
+	case BPF_JSLT:
+	case BPF_JSGE:
+		/* x < 0, x >= 0 */
+		if (imm)
+			return -1;
+		*nonzero = op == BPF_JSLT;
+		return sign;
+	case BPF_JSGT:
+	case BPF_JSLE:
+		/* x > -1, x <= -1 */
+		if (imm != -1)
+			return -1;
+		*nonzero = op == BPF_JSLE;
+		return sign;
+	case BPF_JGT:
+	case BPF_JLE:
+		/* x > 0x7fffffff, x <= 0x7fffffff in 32 bits */
+		if (is64 || imm != 0x7fffffff)
+			return -1;
+		*nonzero = op == BPF_JGT;
+		return 31;
+	case BPF_JGE:
+	case BPF_JLT:
+		/* x >= 0x80000000, x < 0x80000000 in 32 bits */
+		if (is64 || imm != INT_MIN)
+			return -1;
+		*nonzero = op == BPF_JGE;
+		return 31;
+	case BPF_JSET:
+		mask = is64 ? (u64)(s64)imm : (u32)imm;
+		if (!is_power_of_2(mask))
+			return -1;
+		*nonzero = true;
+		return ilog2(mask);
+	default:
+		return -1;
+	}
+}
+
+/*
+ * The test bit and branch reaches 8K instructions either way. Whether a
+ * test takes it is decided in the sizing passes, see bpf_int_jit_compile():
+ * the first one does not know the offsets of the instructions ahead and a
+ * later one knows them from the previous pass only, the distance back is
+ * exact in the current pass. The decision is kept in the tb bitmap for the
+ * passes over the image, where the code only shrinks as calls turn direct,
+ * so a test that fit keeps fitting, and a test that did not keeps the
+ * compare and the conditional branch, as the image must not grow. Returns
+ * false without emitting for the compare and conditional branch to take
+ * over, counted in the sizing passes for the last pass to be known.
+ */
+static bool emit_tb(bool nonzero, u8 reg, int bit, int i, s16 off, struct jit_ctx *ctx)
+{
+	int jmp_offset;
+
+	jmp_offset = bpf2a64_offset(i, off, ctx);
+
+	if (ctx->image) {
+		if (!test_bit(i, ctx->tb))
+			return false;
+	} else {
+		bool take = !ctx->no_tb &&
+			    (off < 0 || (ctx->offset[i + 1] && ctx->offset[i + 1 + off])) &&
+			    jmp_offset >= -SZ_8K && jmp_offset < SZ_8K;
+
+		__assign_bit(i, ctx->tb, take);
+		if (!take) {
+			ctx->tb_long++;
+			return false;
+		}
+	}
+	if (nonzero)
+		emit(A64_TBNZ(reg, bit, jmp_offset), ctx);
+	else
+		emit(A64_TBZ(reg, bit, jmp_offset), ctx);
+	return true;
+}
+
 /*
  * Divide dst by the immediate of a 64-bit division through a multiplication
  * with the magic number from bpf_magic_udiv() or bpf_magic_sdiv(): the high
@@ -1859,6 +1963,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	u8 jmp_cond;
 	s32 jmp_offset;
 	u32 a64_insn;
+	bool nonzero;
+	int bit;
 	int ret;
 
 	if (bpf_insn_is_indirect_target(env, ctx->prog, i))
@@ -2214,6 +2320,20 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	case BPF_JMP32 | BPF_JSLT | BPF_K:
 	case BPF_JMP32 | BPF_JSGE | BPF_K:
 	case BPF_JMP32 | BPF_JSLE | BPF_K:
+		/* A test of the sign within reach is a test bit and branch */
+		bit = tb_bit(jmp_op, is64, imm, &nonzero);
+		if (bit >= 0 && emit_tb(nonzero, dst, bit, i, off, ctx))
+			break;
+		/* A compare against zero for equality is a compare and branch */
+		if (!imm && (jmp_op == BPF_JEQ || jmp_op == BPF_JNE)) {
+			jmp_offset = bpf2a64_offset(i, off, ctx);
+			check_imm19(jmp_offset);
+			if (jmp_op == BPF_JEQ)
+				emit(A64_CBZ(is64, dst, jmp_offset), ctx);
+			else
+				emit(A64_CBNZ(is64, dst, jmp_offset), ctx);
+			break;
+		}
 		if (!is_addsub_imm(imm) && !is_addsub_imm(-(u32)imm))
 			adjust_cmp_imm(&jmp_op, &cmp_imm);
 		if (is_addsub_imm(cmp_imm)) {
@@ -2227,6 +2347,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		goto emit_cond_jmp;
 	case BPF_JMP | BPF_JSET | BPF_K:
 	case BPF_JMP32 | BPF_JSET | BPF_K:
+		/* A test of a single bit within reach is a test bit and branch */
+		bit = tb_bit(jmp_op, is64, imm, &nonzero);
+		if (bit >= 0 && emit_tb(nonzero, dst, bit, i, off, ctx))
+			break;
 		a64_insn = A64_TST_I(is64, dst, imm);
 		if (a64_insn != AARCH64_BREAK_FAULT) {
 			emit(a64_insn, ctx);
@@ -2600,6 +2724,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 	int body_idx;
 	int exentry_idx;
 	int out_cnt;
+	int pass;
 
 	if (!prog->jit_requested)
 		return prog;
@@ -2643,6 +2768,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 	ctx.offset = kvzalloc_objs(int, prog->len + 1);
 	if (ctx.offset == NULL)
 		goto out_off;
+	ctx.tb = kvzalloc_objs(unsigned long, BITS_TO_LONGS(prog->len));
+	if (ctx.tb == NULL)
+		goto out_off;
 
 	if (bpf_prog_uses_arena_insns(prog)) {
 		ctx.user_vm_start = bpf_arena_get_user_vm_start(prog->aux->arena);
@@ -2664,14 +2792,35 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 	 *
 	 * BPF line info needs ctx->offset[i] to be the offset of
 	 * instruction[i] in jited image, so build prologue first.
+	 *
+	 * Whether a sign or bit test takes the test bit and branch depends on
+	 * the distance to its target, which a pass knows for the instructions
+	 * ahead from the previous pass only, see emit_tb(). Repeat the pass
+	 * until the body settles: while the form may be taken, the code only
+	 * shrinks from one pass to the next, so a branch that fit keeps
+	 * fitting, and the form is given up after a few passes, which settles
+	 * the size within two more. A pass in which no test took the compare
+	 * and the conditional branch is the last, the next would decide the
+	 * same. The passes over the image keep the decisions, as the image
+	 * allocated for the size settled on here must not grow.
 	 */
-	if (build_prologue(&ctx, was_classic))
-		goto out_off;
+	for (pass = 1; ; pass++) {
+		int prev_end = ctx.epilogue_offset;
 
-	if (build_body(env, &ctx, extra_pass))
-		goto out_off;
+		ctx.idx = 0;
+		ctx.tb_long = 0;
+		if (build_prologue(&ctx, was_classic))
+			goto out_off;
 
-	ctx.epilogue_offset = ctx.idx;
+		if (build_body(env, &ctx, extra_pass))
+			goto out_off;
+
+		ctx.epilogue_offset = ctx.idx;
+		if (!ctx.tb_long || (pass > 1 && ctx.epilogue_offset == prev_end))
+			break;
+		if (pass == TB_PASSES)
+			ctx.no_tb = true;
+	}
 	build_epilogue(&ctx, was_classic, false);
 	build_plt(&ctx);
 
@@ -2790,6 +2939,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 			prog->aux->priv_stack_ptr = NULL;
 		}
 		kvfree(ctx.offset);
+		kvfree(ctx.tb);
 out_priv_stack:
 		kfree(jit_data);
 		prog->aux->jit_data = NULL;
@@ -3852,6 +4002,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);
+			kvfree(jit_data->ctx.tb);
 			kfree(jit_data);
 		}
 		prog->bpf_func = (void *)prog->bpf_func - cfi_get_offset();
-- 
2.43.0

[PATCH bpf-next 18/21] bpf, arm64: Multiply by constants with shifts, adds and subs

[Daniel Borkmann]

LLVM turns a multiplication by a power of two into a shift, but keeps
the other constants as a multiplication, so these reach the JIT as
BPF_MUL with BPF_K and were emitted as a move of the constant and a mul,
which takes two cycles on Neoverse N2 and later and four for the 64-bit
form on N1. Emit shifts, adds and subs instead: by 2^n a shift, by
2^n + 1 an add of the register shifted left, by 2^n - 1 a shift and a
sub, each also negated and, but for the negated 2^n + 1, times 2^m, at
most two instructions. A shifted operand beyond four takes a cycle more
than one up to four on N1 through V3, so only the forms of at most two
cycles are taken, which never fall behind the mul, and the other
constants keep it. The multiplication by 0 is a move, by -1 a negation
and by 1 nothing beyond the zero extension of the 32-bit form.

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

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 93 ++++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 08b95e3acaab..5995b925b900 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -832,6 +832,93 @@ static bool emit_div_const(const struct bpf_insn *insn, struct jit_ctx *ctx)
 	return true;
 }
 
+/*
+ * Multiply dst by a constant with shifts, adds and subs, at most two
+ * instructions where the move of the constant and the multiply are two slower
+ * ones: by 2^n a shift, by 2^n + 1 an add of the shifted register, by 2^n - 1
+ * a shift and a sub, each also negated and, but for the negated 2^n + 1,
+ * times 2^m. The multiply takes two cycles on Neoverse N2 and later and a
+ * shifted operand beyond four a cycle more than one by up to four on N1
+ * through V3, so only the forms of two cycles at most are taken, which never
+ * fall behind the multiply. The sign of the 32-bit constant serves the low 32
+ * bits of the product as well as its unsigned value. Returns false for the
+ * constants left to mul.
+ */
+static bool emit_mul_const(bool is64, u8 dst, u8 tmp, s32 imm, struct jit_ctx *ctx)
+{
+	u64 c = imm < 0 ? -(u64)(s64)imm : imm;
+	int tz, n;
+
+	switch (imm) {
+	case 0:
+		emit_a64_mov_i(is64, dst, 0, ctx);
+		return true;
+	case 1:
+		/* The 32-bit variant still zero extends */
+		if (!is64)
+			emit(A64_MOV(0, dst, dst), ctx);
+		return true;
+	case -1:
+		emit(A64_NEG(is64, dst, dst), ctx);
+		return true;
+	}
+	/* The odd part of the magnitude and the power of two taken off it */
+	tz = __ffs(c);
+	c >>= tz;
+	if (c == 1) {
+		if (imm > 0)
+			emit(A64_LSL(is64, dst, dst, tz), ctx);
+		else
+			emit(A64_SUB_LSL(is64, dst, A64_ZR, dst, tz), ctx);
+		return true;
+	}
+	if (imm > 0) {
+		if (is_power_of_2(c - 1)) {
+			n = ilog2(c - 1);
+			/* The add of two cycles and the shift, three */
+			if (n > 4 && tz)
+				return false;
+			emit(A64_ADD_LSL(is64, dst, dst, dst, n), ctx);
+			if (tz)
+				emit(A64_LSL(is64, dst, dst, tz), ctx);
+			return true;
+		}
+		if (is_power_of_2(c + 1)) {
+			n = ilog2(c + 1);
+			/* The shift and the sub of two cycles, three */
+			if (tz > 4)
+				return false;
+			emit(A64_LSL(is64, tmp, dst, n + tz), ctx);
+			emit(A64_SUB_LSL(is64, dst, tmp, dst, tz), ctx);
+			return true;
+		}
+	} else {
+		if (is_power_of_2(c + 1)) {
+			n = ilog2(c + 1);
+			if (!tz) {
+				emit(A64_SUB_LSL(is64, dst, dst, dst, n), ctx);
+				return true;
+			}
+			/* The shift and the sub of two cycles, three */
+			if (n + tz > 4)
+				return false;
+			emit(A64_LSL(is64, tmp, dst, tz), ctx);
+			emit(A64_SUB_LSL(is64, dst, tmp, dst, n + tz), ctx);
+			return true;
+		}
+		if (!tz && is_power_of_2(c - 1)) {
+			n = ilog2(c - 1);
+			/* The add of two cycles and the neg, three */
+			if (n > 4)
+				return false;
+			emit(A64_ADD_LSL(is64, dst, dst, dst, n), ctx);
+			emit(A64_NEG(is64, dst, dst), ctx);
+			return true;
+		}
+	}
+	return false;
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -2182,8 +2269,10 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	case BPF_ALU | BPF_MUL | BPF_K:
 	case BPF_ALU64 | BPF_MUL | BPF_K:
-		emit_a64_mov_i(is64, tmp, imm, ctx);
-		emit(A64_MUL(is64, dst, dst, tmp), ctx);
+		if (!emit_mul_const(is64, dst, tmp, imm, ctx)) {
+			emit_a64_mov_i(is64, tmp, imm, ctx);
+			emit(A64_MUL(is64, dst, dst, tmp), ctx);
+		}
 		break;
 	case BPF_ALU | BPF_DIV | BPF_K:
 	case BPF_ALU64 | BPF_DIV | BPF_K:
-- 
2.43.0

[PATCH bpf-next 19/21] bpf, arm64: Split 24-bit immediates of add, sub and equality compares

[Daniel Borkmann]

An add, sub or compare with an immediate that neither the plain nor the
shifted 12-bit field takes moved the immediate into a register first,
two moves for most immediates up to 24 bits and then the add. Take two
adds or subs instead, of the upper 12 bits shifted and of the lower 12:
an instruction fewer, at a cycle more on the path of the operand, as the
two depend on each other where the moves did not, so an immediate that a
single move produces keeps the move. A compare for equality takes the
upper 12 bits off into a scratch register and compares against the lower
12, as the subtraction keeps equality.

Before/after for r2 += 0x22880 and if r1 == 0x12345 goto ...:

  d285100a  mov x10, #0x2880
  f2a0004a  movk x10, #0x2, lsl #16
  8b0a0021  add x1, x1, x10
  91408821  add x1, x1, #0x22, lsl #12
  91220021  add x1, x1, #0x880

  d28468aa  mov x10, #0x2345
  f2a0002a  movk x10, #0x1, lsl #16
  eb0a001f  cmp x0, x10
  54000040  b.eq ...
  d140480a  sub x10, x0, #0x12, lsl #12
  f10d155f  cmp x10, #0x345
  54000040  b.eq ...

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit_comp.c | 113 ++++++++++++++++++++++------------
 1 file changed, 74 insertions(+), 39 deletions(-)

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 5995b925b900..ce72039515ff 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -133,42 +133,40 @@ static inline void emit_u32_data(const u32 data, struct jit_ctx *ctx)
 }
 
 /*
- * A 32-bit immediate, sign extended for the 64-bit variant: a single movz
- * or movn when one half is zero or all ones and the other half agrees with
- * the sign the 64-bit variant extends, a single orr when it is a bitmask
- * immediate, and the pair of a movz or movn with a movk otherwise.
+ * The single instruction for a 32-bit immediate, sign extended for the
+ * 64-bit variant: a movz or movn when one half is zero or all ones and the
+ * other half agrees with the sign the 64-bit variant extends, an orr when
+ * it is a bitmask immediate, else AARCH64_BREAK_FAULT.
  */
-static inline void emit_a64_mov_i(const int is64, const int reg,
-				  const s32 val, struct jit_ctx *ctx)
+static u32 a64_mov_i_single(const int is64, const int reg, const s32 val)
 {
 	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;
-	}
+	if (hi == 0xffff)
+		return A64_MOVN(is64, reg, (u16)~lo, 0);
+	if (!hi)
+		return A64_MOVZ(is64, reg, lo, 0);
 	/* 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;
-	}
+	if (!lo && (!is64 || !(hi & 0x8000)))
+		return A64_MOVZ(is64, reg, hi, 16);
+	if (lo == 0xffff && (!is64 || (hi & 0x8000)))
+		return A64_MOVN(is64, reg, (u16)~hi, 16);
+	return A64_ORR_I(is64, reg, A64_ZR, val);
+}
+
+/* A 32-bit immediate in its single instruction, or a movz or movn with 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 = a64_mov_i_single(is64, reg, val);
 
-	insn = A64_ORR_I(is64, reg, A64_ZR, val);
 	if (insn != AARCH64_BREAK_FAULT) {
 		emit(insn, ctx);
 		return;
 	}
-
 	if (hi & 0x8000) {
 		emit(A64_MOVN(is64, reg, (u16)~hi, 16), ctx);
 		emit(A64_MOVK(is64, reg, lo, 0), ctx);
@@ -363,19 +361,52 @@ static bool is_addsub_imm(u32 imm)
 	return !(imm & ~0xfff) || !(imm & ~0xfff000);
 }
 
-static inline void emit_a64_add_i(const bool is64, const int dst, const int src,
-				  const int tmp, const s32 imm, struct jit_ctx *ctx)
+/* An immediate below 2^24 that neither add nor sub takes goes in two of them */
+static bool is_addsub_imm24(u32 imm)
+{
+	return !(imm & ~0xffffff);
+}
+
+/*
+ * dst = src + imm, or src - imm: with the immediate when an add or sub takes
+ * it, with the negated one in the other, else in two of them with the upper
+ * 12 bits shifted and the lower 12 when the move of the immediate takes two
+ * instructions, one fewer at a cycle more on the path of src, as the two
+ * depend on each other. The rest takes the move, which is off the path, and
+ * the add or sub of the register.
+ */
+static void emit_a64_addsub_i(const bool is64, const int dst, const int src, const int tmp,
+			      const s32 imm, bool sub, struct jit_ctx *ctx)
 {
+	const enum aarch64_insn_adsb_type op = sub ? AARCH64_INSN_ADSB_SUB : AARCH64_INSN_ADSB_ADD;
+	const enum aarch64_insn_adsb_type neg = sub ? AARCH64_INSN_ADSB_ADD : AARCH64_INSN_ADSB_SUB;
+	const enum aarch64_insn_variant variant = A64_VARIANT(is64);
+	const bool split = a64_mov_i_single(is64, tmp, imm) == AARCH64_BREAK_FAULT;
+	const u32 nimm = -(u32)imm;
+
 	if (is_addsub_imm(imm)) {
-		emit(A64_ADD_I(is64, dst, src, imm), ctx);
-	} else if (is_addsub_imm(-(u32)imm)) {
-		emit(A64_SUB_I(is64, dst, src, -imm), ctx);
+		emit(aarch64_insn_gen_add_sub_imm(dst, src, imm, variant, op), ctx);
+	} else if (is_addsub_imm(nimm)) {
+		emit(aarch64_insn_gen_add_sub_imm(dst, src, nimm, variant, neg), ctx);
+	} else if (split && is_addsub_imm24(imm)) {
+		emit(aarch64_insn_gen_add_sub_imm(dst, src, imm & 0xfff000, variant, op), ctx);
+		emit(aarch64_insn_gen_add_sub_imm(dst, dst, imm & 0xfff, variant, op), ctx);
+	} else if (split && is_addsub_imm24(nimm)) {
+		emit(aarch64_insn_gen_add_sub_imm(dst, src, nimm & 0xfff000, variant, neg), ctx);
+		emit(aarch64_insn_gen_add_sub_imm(dst, dst, nimm & 0xfff, variant, neg), ctx);
 	} else {
 		emit_a64_mov_i(is64, tmp, imm, ctx);
-		emit(A64_ADD(is64, dst, src, tmp), ctx);
+		emit(aarch64_insn_gen_add_sub_shifted_reg(dst, src, tmp, AARCH64_INSN_SHIFT_LSL, 0,
+							  variant, op), ctx);
 	}
 }
 
+static inline void emit_a64_add_i(const bool is64, const int dst, const int src,
+				  const int tmp, const s32 imm, struct jit_ctx *ctx)
+{
+	emit_a64_addsub_i(is64, dst, src, tmp, imm, false, ctx);
+}
+
 /*
  * There are 3 types of AArch64 LDR/STR (immediate) instruction:
  * Post-index, Pre-index, Unsigned offset.
@@ -2212,14 +2243,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 		break;
 	case BPF_ALU | BPF_SUB | BPF_K:
 	case BPF_ALU64 | BPF_SUB | BPF_K:
-		if (is_addsub_imm(imm)) {
-			emit(A64_SUB_I(is64, dst, dst, imm), ctx);
-		} else if (is_addsub_imm(-(u32)imm)) {
-			emit(A64_ADD_I(is64, dst, dst, -imm), ctx);
-		} else {
-			emit_a64_mov_i(is64, tmp, imm, ctx);
-			emit(A64_SUB(is64, dst, dst, tmp), ctx);
-		}
+		emit_a64_addsub_i(is64, dst, dst, tmp, imm, true, ctx);
 		break;
 	case BPF_ALU | BPF_AND | BPF_K:
 	case BPF_ALU64 | BPF_AND | BPF_K:
@@ -2429,6 +2453,17 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			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 if ((jmp_op == BPF_JEQ || jmp_op == BPF_JNE) &&
+			   a64_mov_i_single(is64, tmp, imm) == AARCH64_BREAK_FAULT &&
+			   (is_addsub_imm24(imm) || is_addsub_imm24(-(u32)imm))) {
+			/* Equal when the lower 12 bits remain once the upper 12 are taken off */
+			if (is_addsub_imm24(imm)) {
+				emit(A64_SUB_I(is64, tmp, dst, imm & 0xfff000), ctx);
+				emit(A64_CMP_I(is64, tmp, imm & 0xfff), ctx);
+			} else {
+				emit(A64_ADD_I(is64, tmp, dst, -(u32)imm & 0xfff000), ctx);
+				emit(A64_CMN_I(is64, tmp, -(u32)imm & 0xfff), ctx);
+			}
 		} else {
 			emit_a64_mov_i(is64, tmp, cmp_imm, ctx);
 			emit(A64_CMP(is64, dst, tmp), ctx);
-- 
2.43.0

[PATCH bpf-next 20/21] selftests/bpf: Let the arm64 private stack check skip the BTI pad

[Daniel Borkmann]

With CONFIG_ARM64_BTI_KERNEL, the default for kernels built with clang
before 21, the JIT emits the BTI J landing pad for tail calls into a
main program 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 counter setup
and fail on such a kernel:

  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 the tests of the
same file do elsewhere.

Fixes: e9f545d0d336 ("selftests/bpf: Enable private stack tests for arm64")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 tools/testing/selftests/bpf/progs/verifier_private_stack.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_private_stack.c b/tools/testing/selftests/bpf/progs/verifier_private_stack.c
index 3d9994a52464..8fe300e52760 100644
--- a/tools/testing/selftests/bpf/progs/verifier_private_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_private_stack.c
@@ -212,6 +212,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]!")
-- 
2.43.0

[PATCH bpf-next 21/21] selftests/bpf: Extend the JIT instruction tests for arm64 encodings

[Daniel Borkmann]

Cover the sequences the arm64 JIT now emits: compares, bit tests,
constant arithmetic, immediates, the sign jumps across the short branch
range, and every form of the arena address computation. The tests check
results, so they run on every JIT, the arena atomics and sign extending
loads on those that take them. On arm64:

  # PLATFORM=aarch64 CROSS_COMPILE=aarch64-linux-gnu- \
    ./vmtest.sh -- ./test_progs -t jit_insns
  [...]
  #195/1   jit_insns/arena_zero_off:OK
  #195/2   jit_insns/cast_to_user:OK
  #195/3   jit_insns/arena_offsets:OK
  #195/4   jit_insns/arena_offsets_ldsx:OK
  #195/5   jit_insns/arena_offsets_atomics:OK
  #195/6   jit_insns/arena_acq_rel:OK
  #195/7   jit_insns/alu_imm:OK
  #195/8   jit_insns/alu_reg:OK
  #195/9   jit_insns/alu_imm_regs:OK
  #195/10  jit_insns/div_const:OK
  #195/11  jit_insns/alu_reg_pairs:OK
  #195/12  jit_insns/alu_edges:OK
  #195/13  jit_insns/shifts:OK
  #195/14  jit_insns/shift_counts:OK
  #195/15  jit_insns/atomics:OK
  #195/16  jit_insns/atomic_reg_pairs:OK
  #195/17  jit_insns/xadd_chain:OK
  #195/18  jit_insns/ld_imm64:OK
  #195/19  jit_insns/jmp_imm:OK
  #195/20  jit_insns/jmp_reg:OK
  #195/21  jit_insns/jmp_reg_pairs:OK
  #195/22  jit_insns/jmp_edges:OK
  #195/23  jit_insns/staggered_jumps:OK
  #195/24  jit_insns/max_jmp:OK
  #195/25  jit_insns/sign_jumps:OK
  #195/26  jit_insns/convergence:OK
  #195/27  jit_insns/calls:OK
  #195/28  jit_insns/helper_calls:OK
  #195/29  jit_insns/ldst_zero_off:OK
  #195/30  jit_insns/ldst_offsets:OK
  #195/31  jit_insns/acq_rel:OK
  #195/32  jit_insns/atomic_ptr_operand:OK
  #195/33  jit_insns/movsx:OK
  #195/34  jit_insns/jset_imm:OK
  #195/35  jit_insns/cmp_imm:OK
  #195/36  jit_insns/alu_consts:OK
  #195/37  jit_insns/bswap:OK
  #195/38  jit_insns/probe_mem:OK
  #195     jit_insns:OK
  #196/1   jit_insns_blinded/alu_imm:OK
  #196/2   jit_insns_blinded/alu_imm_regs:OK
  #196/3   jit_insns_blinded/alu_edges:OK
  #196/4   jit_insns_blinded/div_const:OK
  #196/5   jit_insns_blinded/shifts:OK
  #196/6   jit_insns_blinded/xadd_chain:OK
  #196/7   jit_insns_blinded/ld_imm64:OK
  #196/8   jit_insns_blinded/jmp_imm:OK
  #196/9   jit_insns_blinded/jmp_edges:OK
  #196/10  jit_insns_blinded/ldst_zero_off:OK
  #196/11  jit_insns_blinded/ldst_offsets:OK
  #196/12  jit_insns_blinded/jset_imm:OK
  #196/13  jit_insns_blinded/cmp_imm:OK
  #196/14  jit_insns_blinded/alu_consts:OK
  #196     jit_insns_blinded:OK
  Summary: 2/52 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/prog_tests/jit_insns.c      | 418 +++++++++++++++---
 .../selftests/bpf/progs/jit_insns_arena.c     | 381 +++++++++++++++-
 2 files changed, 747 insertions(+), 52 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/jit_insns.c b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
index dabefdb8a353..e00130b98b6f 100644
--- a/tools/testing/selftests/bpf/prog_tests/jit_insns.c
+++ b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
@@ -592,13 +592,14 @@ static void test_alu_imm_regs(void)
  * of the 32-bit operations carry garbage in the upper 32 bits.
  */
 static const __s32 unsigned_divisors[] = {
-	2, 3, 7, 10, 25, 641, 1000, 4096, 65536, 1000000007, 0x7fffffff,
+	2, 3, 7, 10, 14, 25, 56, 641, 1000, 4096, 65536, 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)
@@ -1123,7 +1124,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;
@@ -1519,7 +1521,7 @@ static const __u64 inputs[] = {
 };
 
 struct prog {
-	struct bpf_insn insns[16];
+	struct bpf_insn insns[32];
 	int cnt;
 };
 
@@ -1572,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;
@@ -1649,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]));
@@ -1665,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);
 			}
 
@@ -1759,11 +1764,14 @@ 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;
 	if (n > 1 && unaligned) {
 		off[cnt++] = 13;
 		off[cnt++] = 127;
+		off[cnt++] = 257;
+		off[cnt++] = -257;
 		off[cnt++] = -13;
 		off[cnt++] = -129;
 	}
@@ -1975,7 +1983,7 @@ static void store_offsets(struct off_mem *m, int size, int rb, int rd, __s32 imm
 static 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;
@@ -2088,7 +2096,8 @@ static void jmp_prog(struct prog *p, bool is64, int op, int d, __s32 imm, int of
 static 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];
@@ -2155,7 +2164,10 @@ 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,
 	};
 	static const int ops[] = {
 		BPF_JEQ, BPF_JNE, BPF_JGT, BPF_JGE, BPF_JLT, BPF_JLE,
@@ -2186,8 +2198,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);
@@ -2234,12 +2256,30 @@ 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_ADD, 0x3ffc }, { BPF_ADD, -0x10001 }, { BPF_SUB, 0x3ffc },
+		{ BPF_SUB, -0x10001 },
 	};
 	struct prog p;
 	char desc[64];
@@ -2425,9 +2465,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];
@@ -2438,49 +2480,174 @@ 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, which a privileged
+ * program may do: the ones without a fetch with src == dst, and the
+ * cmpxchg with the pointer as the new value. The verifier rejects the
+ * fetching ones with src == dst, as it marks the source unknown before
+ * it checks the access. The slot holds in0, the bytes the atomic
+ * operates on are checked against the operation done on a copy of the
+ * pointer, made a number by two negations, and the pointer register
+ * against the copy.
+ */
+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);
 		}
 	}
 }
@@ -2550,6 +2717,151 @@ static void test_max_jmp(void)
 	max_jmp(true, false);
 }
 
+/*
+ * A sign test over a region of sign tests, as a conditional jump forward
+ * and as one back over it, whose form on a JIT with a short branch for a
+ * sign test depends on the length of the region, which the inner tests
+ * shrink as they take the short form themselves, so the outer test comes
+ * within reach of it only after the inner ones have and the passes of
+ * the JIT have to settle. With n inner tests each over an add, the lengths
+ * around a few thousand take the region across the reach of a short
+ * branch of a few thousand instructions both before and after the inner
+ * tests have settled, and the sweep takes it across right at the limit.
+ * r0 goes in with the value whose sign the outer test takes and r3 with
+ * the one of the inner tests, which count the adds taken, twice around for
+ * the jump back on a count the verifier can see.
+ */
+static void sign_jumps(int inner, bool back, const char *desc)
+{
+	struct bpf_insn *insns;
+	int n = 0, top, i, fd;
+
+	insns = malloc((16 + 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_IMM(BPF_REG_2, 0);
+	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 (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_1, 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;
+	/* The adds taken with the inner sign set, none with the outer one */
+	prog_run(fd, 0, -1, back ? 2 * inner : inner, desc);
+	prog_run(fd, 0, 0, 0, desc);
+	prog_run(fd, -1, -1, back ? 2 * inner : 0, desc);
+	prog_run(fd, 1ULL << 63, 1, 0, desc);
+	close(fd);
+}
+
+/*
+ * A chain of sign tests over a region of sign tests, each one an instruction
+ * further out than the next, as the targets lie an instruction apart behind
+ * the region: with the region at the reach of a short branch, each test comes
+ * within it only once the next one has shrunk, a pass per test for a JIT
+ * which decides the form from the previous pass, past the passes it allows
+ * the form before giving it up. With a helper call in the region, which may
+ * shorten once the image is placed, the region shrinks after the size is
+ * settled and the tests at the reach must keep their form. r0 goes in with
+ * the value whose sign the chain takes and r3 with the one of the inner
+ * tests, which count the adds taken, and the adds behind the region count
+ * on from the targets.
+ */
+static void sign_jump_chain(int inner, int outer, bool call, const char *desc)
+{
+	struct bpf_insn *insns;
+	int n = 0, top, off, 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) {
+		insns[n++] = BPF_MOV64_REG(BPF_REG_7, BPF_REG_2);
+		insns[n++] = BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32);
+		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();
+
+	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);
+}
+
+static void test_sign_jumps(void)
+{
+	static const int inners[] = { 16, 2000, 2731, 2732, 4200 };
+	char desc[64];
+	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, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps", inners[i]);
+		sign_jumps(inners[i], true, desc);
+	}
+	/* The region across the reach of a short branch of 8K instructions */
+	for (inner = 4086; inner <= 4100; inner++) {
+		snprintf(desc, sizeof(desc), "sign jump over %d sign jumps at the range", inner);
+		sign_jumps(inner, false, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps at the range",
+			 inner);
+		sign_jumps(inner, true, desc);
+	}
+	/* A chain of tests across the reach, with and without a call in the region */
+	for (inner = 4080; inner <= 4098; inner++) {
+		snprintf(desc, sizeof(desc), "sign jump chain over %d sign jumps", inner);
+		sign_jump_chain(inner, 20, false, desc);
+		snprintf(desc, sizeof(desc), "sign jump chain over %d sign jumps and a call",
+			 inner);
+		sign_jump_chain(inner, 20, true, 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
@@ -3085,6 +3397,8 @@ 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("calls"))
@@ -3097,6 +3411,8 @@ void test_jit_insns(void)
 		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"))
diff --git a/tools/testing/selftests/bpf/progs/jit_insns_arena.c b/tools/testing/selftests/bpf/progs/jit_insns_arena.c
index 95736eae2a58..e4eaaab670cf 100644
--- a/tools/testing/selftests/bpf/progs/jit_insns_arena.c
+++ b/tools/testing/selftests/bpf/progs/jit_insns_arena.c
@@ -13,7 +13,7 @@
 struct {
 	__uint(type, BPF_MAP_TYPE_ARENA);
 	__uint(map_flags, BPF_F_MMAPABLE);
-	__uint(max_entries, 1);
+	__uint(max_entries, 2);
 } arena SEC(".maps");
 
 /*
@@ -32,6 +32,65 @@ struct {
 #define VAL_SUM	0x11224578aaccef10
 #endif
 
+/*
+ * The load-acquire and store-release, which clang has syntax for only with
+ * __BPF_FEATURE_LOAD_ACQ_STORE_REL, as the 64-bit word of their fields for
+ * .8byte, in the byte order of the target: the two register nibbles share a
+ * byte, which the first bitfield of struct bpf_insn takes from the low end
+ * on little endian and from the high end on big endian.
+ */
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define INSN(CODE, DST, SRC, OFF, IMM)						\
+	((__u64)(__u8)(CODE) | ((__u64)(DST) << 8) | ((__u64)(SRC) << 12) |	\
+	 ((__u64)(__u16)(OFF) << 16) | ((__u64)(__u32)(IMM) << 32))
+#else
+#define INSN(CODE, DST, SRC, OFF, IMM)						\
+	(((__u64)(__u8)(CODE) << 56) | ((__u64)(DST) << 52) | ((__u64)(SRC) << 48) | \
+	 ((__u64)(__u16)(OFF) << 32) | (__u64)(__u32)(IMM))
+#endif
+#define ATOMIC(SIZE, OP, DST, SRC, OFF)	INSN(BPF_STX | BPF_ATOMIC | (SIZE), DST, SRC, OFF, OP)
+
+/* The fields of those instructions, which vmlinux.h does not carry */
+#ifndef BPF_STX
+#define BPF_STX		0x03
+#define BPF_W		0x00
+#define BPF_B		0x10
+#define BPF_DW		0x18
+#define BPF_ATOMIC	0xc0
+#endif
+#ifndef BPF_LOAD_ACQ
+#define BPF_LOAD_ACQ	0x100
+#define BPF_STORE_REL	0x110
+#endif
+
+/*
+ * The JITs that take the sign extending loads, the atomics, and the
+ * load-acquire and store-release in the arena, the last as arena_atomics.c
+ * lists them. The atomics other than loads and stores need LSE on arm64,
+ * and cmpxchg needs Zacas on riscv64.
+ */
+#if defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) ||		\
+	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64)
+#define ARENA_LDSX
+#endif
+#if defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) ||		\
+	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) ||			\
+	defined(__TARGET_ARCH_s390) || defined(__TARGET_ARCH_powerpc)
+#define ARENA_ATOMICS
+#endif
+#if defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) ||		\
+	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) ||			\
+	defined(__TARGET_ARCH_s390)
+#define ARENA_ACQ_REL
+#endif
+
+/* The first byte in memory of the u32 0x12abcdef depends on the byte order */
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define ACQ_B0	0xef
+#else
+#define ACQ_B0	0x12
+#endif
+
 #if defined(__BPF_FEATURE_ADDR_SPACE_CAST)
 SEC("syscall")
 __success __retval(0)
@@ -106,6 +165,326 @@ int cast_to_user(void *ctx)
 	: "r1", "r2", "r7", "r9");
 	return res != 0;
 }
+
+/*
+ * Every form of the address computation of an arena access: an immediate
+ * offset the add takes, one the sub takes into the page before, one the
+ * shifted add takes, one that needs a move, the end of the second page,
+ * the narrower sizes, and the immediate stores of a zero and of another
+ * value. Each access is checked through r2, the same address computed into
+ * a register: a store is read back through it, and a load gets a value
+ * written through it, with the slot cleared again, so that a load and a
+ * store at the same wrong address, or one at the slot of another, fail.
+ */
+SEC("syscall")
+__success __retval(0)
+__naked void arena_offsets(void)
+{
+	asm volatile ("					\
+	r1 = %[arena] ll;				\
+	r2 = 0;						\
+	r3 = 2;						\
+	r4 = -1;					\
+	r5 = 0;						\
+	call bpf_arena_alloc_pages;			\
+	r7 = r0;					\
+	r0 = 1;						\
+	if r7 == 0 goto 9f;				\
+	r7 = addr_space_cast(r7, 0x0, 0x1);		\
+	r6 = r7;					\
+	r6 += 0x1000;					\
+	r9 = 0;						\
+	r8 = 0x1122334455667788 ll;			\
+	r5 = 0x0123456789abcdef ll;			\
+	r2 = r7;					\
+	r2 += 8;					\
+	*(u64 *)(r7 + 8) = r8;				\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	r1 = *(u64 *)(r7 + 8);				\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 0xff8;					\
+	*(u64 *)(r6 - 8) = r8;				\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	r1 = *(u64 *)(r6 - 8);				\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 0x1000;					\
+	*(u64 *)(r7 + 0x1000) = r8;			\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	r1 = *(u64 *)(r7 + 0x1000);			\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 0x1238;					\
+	*(u64 *)(r7 + 0x1238) = r8;			\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	r1 = *(u64 *)(r7 + 0x1238);			\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 0x1ff8;					\
+	*(u64 *)(r7 + 0x1ff8) = r8;			\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	r1 = *(u64 *)(r7 + 0x1ff8);			\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 20;					\
+	*(u32 *)(r7 + 20) = r8;				\
+	r1 = *(u32 *)(r2 + 0);				\
+	w1 ^= w8;					\
+	r9 |= r1;					\
+	*(u32 *)(r2 + 0) = r5;				\
+	r1 = *(u32 *)(r7 + 20);				\
+	w1 ^= w5;					\
+	r9 |= r1;					\
+	*(u32 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 26;					\
+	*(u16 *)(r7 + 26) = r8;				\
+	r1 = *(u16 *)(r2 + 0);				\
+	r1 ^= 0x7788;					\
+	r9 |= r1;					\
+	*(u16 *)(r2 + 0) = r5;				\
+	r1 = *(u16 *)(r7 + 26);				\
+	r1 ^= 0xcdef;					\
+	r9 |= r1;					\
+	*(u16 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 29;					\
+	*(u8 *)(r7 + 29) = r8;				\
+	r1 = *(u8 *)(r2 + 0);				\
+	r1 ^= 0x88;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = r5;				\
+	r1 = *(u8 *)(r7 + 29);				\
+	r1 ^= 0xef;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 8;					\
+	*(u64 *)(r2 + 0) = r5;				\
+	*(u64 *)(r7 + 8) = 0;				\
+	r1 = *(u64 *)(r2 + 0);				\
+	r9 |= r1;					\
+	*(u64 *)(r7 + 8) = 0x12345;			\
+	r1 = *(u64 *)(r2 + 0);				\
+	r1 ^= 0x12345;					\
+	r9 |= r1;					\
+	*(u32 *)(r7 + 8) = -1;				\
+	r1 = *(u32 *)(r2 + 0);				\
+	w1 ^= -1;					\
+	r9 |= r1;					\
+	r0 = 0;						\
+	if r9 == 0 goto 9f;				\
+	r0 = 1;						\
+9:	exit;						\
+"	:
+	: __imm_addr(arena)
+	: __clobber_all);
+}
+
+/*
+ * The sign extending loads at an offset, of a value per size written
+ * through r2, the address computed into a register.
+ */
+#ifdef ARENA_LDSX
+SEC("syscall")
+__success __retval(0)
+__naked void arena_offsets_ldsx(void)
+{
+	asm volatile ("					\
+	r1 = %[arena] ll;				\
+	r2 = 0;						\
+	r3 = 2;						\
+	r4 = -1;					\
+	r5 = 0;						\
+	call bpf_arena_alloc_pages;			\
+	r7 = r0;					\
+	r0 = 1;						\
+	if r7 == 0 goto 9f;				\
+	r7 = addr_space_cast(r7, 0x0, 0x1);		\
+	r9 = 0;						\
+	r2 = r7;					\
+	r2 += 40;					\
+	*(u8 *)(r2 + 0) = -16;				\
+	r2 = r7;					\
+	r2 += 42;					\
+	*(u16 *)(r2 + 0) = -0x1234;			\
+	r2 = r7;					\
+	r2 += 44;					\
+	*(u32 *)(r2 + 0) = -0x12345678;			\
+	r1 = *(s8 *)(r7 + 40);				\
+	r1 += 16;					\
+	r9 |= r1;					\
+	r1 = *(s16 *)(r7 + 42);				\
+	r1 += 0x1234;					\
+	r9 |= r1;					\
+	r1 = *(s32 *)(r7 + 44);				\
+	r1 += 0x12345678;				\
+	r9 |= r1;					\
+	r0 = 0;						\
+	if r9 == 0 goto 9f;				\
+	r0 = 1;						\
+9:	exit;						\
+"	:
+	: __imm_addr(arena)
+	: __clobber_all);
+}
+#endif /* ARENA_LDSX */
+
+/*
+ * The atomics at an offset and at zero, the result at the offset read
+ * through r6, the address computed into a register.
+ */
+#ifdef ARENA_ATOMICS
+SEC("syscall")
+__success __retval(0)
+__naked void arena_offsets_atomics(void)
+{
+	asm volatile ("					\
+	r1 = %[arena] ll;				\
+	r2 = 0;						\
+	r3 = 2;						\
+	r4 = -1;					\
+	r5 = 0;						\
+	call bpf_arena_alloc_pages;			\
+	r7 = r0;					\
+	r0 = 1;						\
+	if r7 == 0 goto 9f;				\
+	r7 = addr_space_cast(r7, 0x0, 0x1);		\
+	r6 = r7;					\
+	r6 += 0x1008;					\
+	r9 = 0;						\
+	r1 = 0x10;					\
+	*(u64 *)(r7 + 0x1008) = r1;			\
+	r8 = 1;						\
+	lock *(u64 *)(r7 + 0x1008) += r8;		\
+	r2 = 1;						\
+	r2 = atomic_fetch_add((u64 *)(r7 + 0x1008), r2);	\
+	r2 ^= 0x11;					\
+	r9 |= r2;					\
+	r3 = 0x77;					\
+	r3 = xchg_64(r7 + 0x1008, r3);			\
+	r3 ^= 0x12;					\
+	r9 |= r3;					\
+	r0 = 0x77;					\
+	r4 = 0x99;					\
+	r0 = cmpxchg_64(r7 + 0x1008, r0, r4);		\
+	r0 ^= 0x77;					\
+	r9 |= r0;					\
+	r1 = *(u64 *)(r6 + 0);				\
+	r1 ^= 0x99;					\
+	r9 |= r1;					\
+	w1 = 0x10;					\
+	*(u32 *)(r7 + 0) = w1;				\
+	w8 = 1;						\
+	lock *(u32 *)(r7 + 0) += w8;			\
+	w2 = 1;						\
+	w2 = atomic_fetch_add((u32 *)(r7 + 0), w2);	\
+	w2 ^= 0x11;					\
+	r9 |= r2;					\
+	w3 = 0x77;					\
+	w3 = xchg32_32(r7 + 0, w3);			\
+	w3 ^= 0x12;					\
+	r9 |= r3;					\
+	w0 = 0x77;					\
+	w4 = 0x99;					\
+	w0 = cmpxchg32_32(r7 + 0, w0, w4);		\
+	w0 ^= 0x77;					\
+	r9 |= r0;					\
+	r1 = *(u32 *)(r7 + 0);				\
+	w1 ^= 0x99;					\
+	r9 |= r1;					\
+	r0 = 0;						\
+	if r9 == 0 goto 9f;				\
+	r0 = 1;						\
+9:	exit;						\
+"	:
+	: __imm_addr(arena)
+	: __clobber_all);
+}
+#endif /* ARENA_ATOMICS */
+
+#ifdef ARENA_ACQ_REL
+/*
+ * The load-acquire and the store-release at an offset and at zero, the
+ * ones at the offset checked through r3, the address computed into a
+ * register, with a plain load and store.
+ */
+SEC("syscall")
+__success __retval(0)
+__naked void arena_acq_rel(void)
+{
+	asm volatile ("					\
+	r1 = %[arena] ll;				\
+	r2 = 0;						\
+	r3 = 1;						\
+	r4 = -1;					\
+	r5 = 0;						\
+	call bpf_arena_alloc_pages;			\
+	r7 = r0;					\
+	r0 = 1;						\
+	if r7 == 0 goto 9f;				\
+	r7 = addr_space_cast(r7, 0x0, 0x1);		\
+	r3 = r7;					\
+	r3 += 8;					\
+	r9 = 0;						\
+	r1 = 0x1234;					\
+	.8byte %[store_rel8];	/* store_release((u64 *)(r7 + 8), r1) */	\
+	r2 = *(u64 *)(r3 + 0);				\
+	r2 ^= 0x1234;					\
+	r9 |= r2;					\
+	r1 = 0x5678;					\
+	*(u64 *)(r3 + 0) = r1;				\
+	.8byte %[load_acq8];	/* r2 = load_acquire((u64 *)(r7 + 8)) */	\
+	r2 ^= 0x5678;					\
+	r9 |= r2;					\
+	w1 = 0x12abcdef;				\
+	.8byte %[store_rel0];	/* store_release((u32 *)(r7 + 0), w1) */	\
+	.8byte %[load_acq0];	/* w2 = load_acquire((u8 *)(r7 + 0)) */	\
+	r2 ^= %[b0];					\
+	r9 |= r2;					\
+	r1 = *(u32 *)(r7 + 0);				\
+	w1 ^= 0x12abcdef;				\
+	r9 |= r1;					\
+	r0 = 0;						\
+	if r9 == 0 goto 9f;				\
+	r0 = 1;						\
+9:	exit;						\
+"	:
+	: __imm_addr(arena),
+	  __imm_const(b0, ACQ_B0),
+	  __imm_const(store_rel8, ATOMIC(BPF_DW, BPF_STORE_REL, 7, 1, 8)),
+	  __imm_const(load_acq8, ATOMIC(BPF_DW, BPF_LOAD_ACQ, 2, 7, 8)),
+	  __imm_const(store_rel0, ATOMIC(BPF_W, BPF_STORE_REL, 7, 1, 0)),
+	  __imm_const(load_acq0, ATOMIC(BPF_B, BPF_LOAD_ACQ, 2, 7, 0))
+	: __clobber_all);
+}
+#endif /* ARENA_ACQ_REL */
 #endif
 
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

Re: [PATCH bpf-next 15/21] bpf, arm64: Divide by constants via multiplication with a magic number

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2231 bytes --]

> bpf, arm64: Divide by constants via multiplication with a magic number

TL;DR: Design question, not a bug: emit_div_const() in the arm64 JIT
duplicates the x86 JIT's divisor handling (sign correction, pre-shift, shift
guard). Could it be shared in kernel/bpf/core.c?

> diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
> --- a/arch/arm64/net/bpf_jit_comp.c
> +++ b/arch/arm64/net/bpf_jit_comp.c

[ ... ]

> @@ -593,6 +593,141 @@ static bool adjust_cmp_imm(u8 *op, s32 *imm)
> +static bool emit_div_const(const struct bpf_insn *insn, struct jit_ctx *ctx)
> +{

[ ... ]

> +		bpf_magic_sdiv(imm, &mag);
> +		/* q += n for d > 0 and m < 0, q -= n for d < 0 and m > 0 */
> +		if (imm > 0 && (s64)mag.m < 0)
> +			corr = 1;
> +		else if (imm < 0 && (s64)mag.m > 0)
> +			corr = -1;
> +	} else {

[ ... ]

> +		bpf_magic_udiv(imm, 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 && !(imm & 1)) {
> +			pre = __ffs(imm) & 31;
> +			bpf_magic_udiv(imm >> 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;

this isn't a bug, but the divisor handling in emit_div_const() looks the
same as in emit_div_const() in arch/x86/net/bpf_jit_comp.c: the sign
correction chosen after bpf_magic_sdiv(), the pre-shift by the trailing zeros
with the second bpf_magic_udiv() call for an even divisor, and the shift
count guard, comments included.  Only the instruction emission differs.

Could the corr/pre/shift-guard selection sit in kernel/bpf/core.c next to
bpf_magic_udiv() and bpf_magic_sdiv(), so the two JITs share one copy?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/40562673614

Re: [PATCH bpf-next 21/21] selftests/bpf: Extend the JIT instruction tests for arm64 encodings

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2149 bytes --]

> selftests/bpf: Extend the JIT instruction tests for arm64 encodings

TL;DR: Nit only, not a bug: the hand-packed INSN()/ATOMIC() macros for
load-acquire/store-release in jit_insns_arena.c could use struct bpf_insn with
__imm_insn(), dropping the byte-order variants.

> diff --git a/tools/testing/selftests/bpf/progs/jit_insns_arena.c b/tools/testing/selftests/bpf/progs/jit_insns_arena.c
> --- a/tools/testing/selftests/bpf/progs/jit_insns_arena.c
> +++ b/tools/testing/selftests/bpf/progs/jit_insns_arena.c

[ ... ]

> @@ -32,6 +32,65 @@ struct {
>  #define VAL_SUM	0x11224578aaccef10
>  #endif
>
> +/*
> + * The load-acquire and store-release, which clang has syntax for only with
> + * __BPF_FEATURE_LOAD_ACQ_STORE_REL, as the 64-bit word of their fields for
> + * .8byte, in the byte order of the target: the two register nibbles share a
> + * byte, which the first bitfield of struct bpf_insn takes from the low end
> + * on little endian and from the high end on big endian.
> + */
> +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
> +#define INSN(CODE, DST, SRC, OFF, IMM)						\
> +	((__u64)(__u8)(CODE) | ((__u64)(DST) << 8) | ((__u64)(SRC) << 12) |	\
> +	 ((__u64)(__u16)(OFF) << 16) | ((__u64)(__u32)(IMM) << 32))
> +#else
> +#define INSN(CODE, DST, SRC, OFF, IMM)						\
> +	(((__u64)(__u8)(CODE) << 56) | ((__u64)(DST) << 52) | ((__u64)(SRC) << 48) | \
> +	 ((__u64)(__u16)(OFF) << 32) | (__u64)(__u32)(IMM))
> +#endif
> +#define ATOMIC(SIZE, OP, DST, SRC, OFF)	INSN(BPF_STX | BPF_ATOMIC | (SIZE), DST, SRC, OFF, OP)

this isn't a bug, but could ATOMIC() build a struct bpf_insn compound
literal and pass it through the existing __imm_insn() from bpf_misc.h, as
progs/stream.c does for its arena load-acquire?

That would let the two byte-order variants of INSN() and most of the comment
above them go away, since __imm_insn() already gets the target byte order
from struct bpf_insn.

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/40562673614

Re: [PATCH bpf-next 21/21] selftests/bpf: Extend the JIT instruction tests for arm64 encodings

[Daniel Borkmann]

On 10/27/26 8:08 PM, bot+bpf-ci@kernel.org wrote:
>> selftests/bpf: Extend the JIT instruction tests for arm64 encodings
> 
> TL;DR: Nit only, not a bug: the hand-packed INSN()/ATOMIC() macros for
> load-acquire/store-release in jit_insns_arena.c could use struct bpf_insn with
> __imm_insn(), dropping the byte-order variants.
This and the other suggestions look good, I'll implement them and spin a v2.

Thanks,
Daniel

Re: [PATCH bpf-next 03/21] bpf, arm64: Emit ISB SY in the speculation barriers

[Luis Gerhorst]

Daniel Borkmann <daniel@iogearbox.net> writes:

> The Spectre-BHB loop of the epilogue and BPF_NOSPEC on cores without
> FEAT_SB end in an ISB, which the JIT took from
> aarch64_insn_get_isb_value(), the template of the instruction matcher
> with CRm 0. The Arm ARM lists every CRm other than 0b1111 as reserved:
> those encodings execute as a full system barrier, but must not be relied
> upon by software. Emit ISB SY with CRm 0b1111, as the assembler does for
> the isb of the kernel's own barriers.
>
> Before/after:
>
>   d50330df  isb #0
>   d5033fdf  isb
>
> Fixes: 0dfefc2ea2f2 ("arm64: bpf: Add BHB mitigation to the epilogue for cBPF programs")
> Fixes: dff883d9e93a ("bpf, arm64, powerpc: Change nospec to include v1 barrier")
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>

Tested on ThunderX2-99xx in KVM (BHB loop forced on).

Tested-by: Luis Gerhorst <luis.gerhorst@fau.de>

> ---
>  arch/arm64/net/bpf_jit.h      | 2 +-
>  arch/arm64/net/bpf_jit_comp.c | 2 +-
>  2 files changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
> index b2fe6e6dcf44..af570c34a96d 100644
> --- a/arch/arm64/net/bpf_jit.h
> +++ b/arch/arm64/net/bpf_jit.h
> @@ -341,6 +341,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 */
> diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
> index febe072a8af2..7d5eb949cdf4 100644
> --- a/arch/arm64/net/bpf_jit_comp.c
> +++ b/arch/arm64/net/bpf_jit_comp.c
> @@ -1026,7 +1026,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()) {

Re: [PATCH bpf-next 03/21] bpf, arm64: Emit ISB SY in the speculation barriers

[Daniel Borkmann]

On 10/28/26 2:29 PM, Luis Gerhorst wrote:
> Daniel Borkmann <daniel@iogearbox.net> writes:
> 
>> The Spectre-BHB loop of the epilogue and BPF_NOSPEC on cores without
>> FEAT_SB end in an ISB, which the JIT took from
>> aarch64_insn_get_isb_value(), the template of the instruction matcher
>> with CRm 0. The Arm ARM lists every CRm other than 0b1111 as reserved:
>> those encodings execute as a full system barrier, but must not be relied
>> upon by software. Emit ISB SY with CRm 0b1111, as the assembler does for
>> the isb of the kernel's own barriers.
>>
>> Before/after:
>>
>>    d50330df  isb #0
>>    d5033fdf  isb
>>
>> Fixes: 0dfefc2ea2f2 ("arm64: bpf: Add BHB mitigation to the epilogue for cBPF programs")
>> Fixes: dff883d9e93a ("bpf, arm64, powerpc: Change nospec to include v1 barrier")
>> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> 
> Tested on ThunderX2-99xx in KVM (BHB loop forced on).
> 
> Tested-by: Luis Gerhorst <luis.gerhorst@fau.de>
Thanks Luis, I'll carry your tag for v2.

Re: [PATCH bpf-next 07/21] bpf: Move the division magic number computation out of the x86 JIT

[Alexei Starovoitov]

On Tue, Oct 27, 2026 at 11:24 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
> bpf_magic_udiv() and bpf_magic_sdiv() compute the multiplier and shift
> for the division by a constant and have nothing x86 specific, so move
> them to the core for the other JITs to use. They divide 64-bit values by
> a divisor only known at run time, which a 32-bit kernel has no inline
> form for, so they come under CONFIG_64BIT like the JITs which can use
> them. No functional change.

emit_div_const() in patch 15 has a copy of 35 lines of the x86
emit_div_const(): the divisors to skip, corr, pre, the second call of
bpf_magic_udiv(), the check of the shift.
Nothing in there is x86 specific either, and it needed
commit 73a5accbfd21 ("bpf, x86: Mask the shift counts of the magic number division")
already.

can we move that part to the core too ?
Then a JIT makes one call and emits insns. bpf_magic_udiv() and
bpf_magic_sdiv() stay static, and riscv, s390, etc. don't need
a third copy.

Re: [PATCH bpf-next 17/21] bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests

[Alexei Starovoitov]

On Tue, Oct 27, 2026 at 11:24 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
> TBZ and TBNZ only reach 8K instructions where B.cond reaches 256K, so a
> test takes them when its target is within reach. The sizing pass is
> repeated with the offsets of the previous one until the code settles,
> and where it has not after a few passes, all tests of the program keep
> the compare and the branch. A branch back takes its distance from its
> own position, as the offsets after it are still those of the previous
> pass, which would overestimate the distance by what the code in front of
> the branch shrank. The decisions are kept in a bitmap for the passes
> over the image, which must not grow. A program without such a test takes
> a single sizing pass as before.

This is quite heavy.
Pass 1 doesn't know the offsets ahead. So a prog with one forward
'if r0 s< 0 goto' runs build_body() at least one more time.

Pass 1 is the maximum size already. Pass 2 turns calls into direct calls
and the image shrinks.
can we decide in pass 2 ?
The offsets ahead are from pass 1 and the code only shrinks after it.
A test that fits there fits in the image.

  pass          this patch              decide in pass 2
  ------------  ----------------------  ---------------------
  1, sizing     1 to 10 build_body()    1, with cmp + b.cond
  2, no write   reads the bitmap        sets the bitmap
  3, write      reads the bitmap        reads the bitmap

The allocation has 4 unused bytes per tbz, like 12 bytes per direct call
today. A test that gets in reach only after other code shrinks keeps
cmp + b.cond.
Then no need for the loop, TB_PASSES, no_tb and tb_long.

The encoder and tb_bit() are yours. emit_tb() is different and
bpf_int_jit_compile() only allocates the bitmap.

Something like this (not even compile tested):

diff --git a/arch/arm64/include/asm/insn.h b/arch/arm64/include/asm/insn.h
index 1ce75a4..36b199c 100644
--- a/arch/arm64/include/asm/insn.h
+++ b/arch/arm64/include/asm/insn.h
@@ -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 {
@@ -582,6 +584,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);

diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
index e70ac02..2dbc1f3 100644
--- a/arch/arm64/lib/insn.c
+++ b/arch/arm64/lib/insn.c
@@ -331,6 +331,48 @@ u32 aarch64_insn_gen_comp_branch_imm(unsigned long pc, unsigned long addr,
 					     offset >> 2);
 }

+/*
+ * TBZ and TBNZ test @bit of @reg, 0 to 63 with the 64-bit register implied
+ * from bit 32 on, and reach [-32K, 32K) bytes.
+ */
+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 insn;
+	long offset;
+
+	offset = label_imm_common(pc, addr, SZ_32K);
+	if (offset >= SZ_32K)
+		return AARCH64_BREAK_FAULT;
+
+	switch (type) {
+	case AARCH64_INSN_BRANCH_TEST_ZERO:
+		insn = aarch64_insn_get_tbz_value();
+		break;
+	case AARCH64_INSN_BRANCH_TEST_NONZERO:
+		insn = aarch64_insn_get_tbnz_value();
+		break;
+	default:
+		pr_err("%s: unknown branch encoding %d\n", __func__, type);
+		return AARCH64_BREAK_FAULT;
+	}
+
+	if (bit < 0 || bit > 63) {
+		pr_err("%s: invalid bit %d\n", __func__, bit);
+		return AARCH64_BREAK_FAULT;
+	}
+	/* b5 in bit 31 and b40 in bits [23:19] hold the bit number */
+	insn |= (u32)(bit >> 5) << 31;
+	insn |= (bit & 0x1f) << 19;
+
+	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn, reg);
+
+	return aarch64_insn_encode_immediate(AARCH64_INSN_IMM_14, insn,
+					     offset >> 2);
+}
+
 u32 aarch64_insn_gen_cond_branch_imm(unsigned long pc, unsigned long addr,
 				     enum aarch64_insn_condition cond)
 {
diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index b2fe6e6..8dbe140 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -26,6 +26,13 @@
 #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)

+/* 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, (imm14) << 2, ZERO)
+#define A64_TBNZ(Rt, bit, imm14) A64_TEST_BRANCH(Rt, bit, (imm14) << 2, NONZERO)
+
 /* Conditional branch (immediate) */
 #define A64_COND_BRANCH(cond, offset) \
 	aarch64_insn_gen_cond_branch_imm(0, offset, cond)
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index aaa34c7..9611170 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -92,6 +92,7 @@ struct jit_ctx {
 	bool fp_used;
 	bool priv_sp_used;
 	bool write;
+	unsigned long *tb;
 };

 struct bpf_plt {
@@ -257,8 +258,11 @@ static inline int bpf2a64_offset(int bpf_insn, int off,
 	/*
 	 * Whereas arm64 branch instructions encode the offset
 	 * from the branch itself, so we must subtract 1 from the
-	 * instruction offset.
+	 * instruction offset. A branch back is the next instruction
+	 * emitted. The offsets behind it are from the previous pass.
 	 */
+	if (off < 0)
+		return ctx->offset[bpf_insn + off] - ctx->idx;
 	return ctx->offset[bpf_insn + off] - (ctx->offset[bpf_insn] - 1);
 }

@@ -346,6 +350,80 @@ static bool is_lsi_offset(int offset, int scale)
 	return true;
 }

+/*
+ * A compare against zero or minus one for the sign, an unsigned 32-bit
+ * compare at the sign bit and a test of a single bit test a bit of the
+ * register: returns the bit, with *nonzero set when the branch is taken
+ * with it set, or -1.
+ */
+static int tb_bit(u8 op, bool is64, s32 imm, bool *nonzero)
+{
+	const int sign = is64 ? 63 : 31;
+	u64 mask;
+
+	switch (op) {
+	case BPF_JSLT:
+	case BPF_JSGE:
+		/* x < 0, x >= 0 */
+		if (imm)
+			return -1;
+		*nonzero = op == BPF_JSLT;
+		return sign;
+	case BPF_JSGT:
+	case BPF_JSLE:
+		/* x > -1, x <= -1 */
+		if (imm != -1)
+			return -1;
+		*nonzero = op == BPF_JSLE;
+		return sign;
+	case BPF_JGT:
+	case BPF_JLE:
+		/* x > 0x7fffffff, x <= 0x7fffffff in 32 bits */
+		if (is64 || imm != 0x7fffffff)
+			return -1;
+		*nonzero = op == BPF_JGT;
+		return 31;
+	case BPF_JGE:
+	case BPF_JLT:
+		/* x >= 0x80000000, x < 0x80000000 in 32 bits */
+		if (is64 || imm != INT_MIN)
+			return -1;
+		*nonzero = op == BPF_JGE;
+		return 31;
+	case BPF_JSET:
+		mask = is64 ? (u64)(s64)imm : (u32)imm;
+		if (!is_power_of_2(mask))
+			return -1;
+		*nonzero = true;
+		return ilog2(mask);
+	default:
+		return -1;
+	}
+}
+
+/*
+ * The test bit and branch reaches 8K instructions either way. Pass 1 sizes
+ * the image for the compare and the conditional branch. Pass 2 decides: the
+ * offsets ahead are from the previous pass and the code only shrinks, so
+ * a test that fits there fits in the image. Pass 3 keeps the decision.
+ */
+static bool emit_tb(bool nonzero, u8 reg, int bit, int i, s16 off, struct jit_ctx *ctx)
+{
+	int jmp_offset = bpf2a64_offset(i, off, ctx);
+
+	if (!ctx->image)
+		return false;
+	if (!ctx->write)
+		__assign_bit(i, ctx->tb, jmp_offset >= -SZ_8K && jmp_offset < SZ_8K);
+	if (!test_bit(i, ctx->tb))
+		return false;
+	if (nonzero)
+		emit(A64_TBNZ(reg, bit, jmp_offset), ctx);
+	else
+		emit(A64_TBZ(reg, bit, jmp_offset), ctx);
+	return true;
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -1454,6 +1532,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	int off_adj;
 	int ret;
 	bool sign_extend;
+	bool nonzero;
+	int bit;

 	if (bpf_insn_is_indirect_target(env, ctx->prog, i))
 		emit_bti(A64_BTI_J, ctx);
@@ -1788,6 +1868,20 @@ emit_cond_jmp:
 	case BPF_JMP32 | BPF_JSLT | BPF_K:
 	case BPF_JMP32 | BPF_JSGE | BPF_K:
 	case BPF_JMP32 | BPF_JSLE | BPF_K:
+		/* A test of the sign within reach is a test bit and branch */
+		bit = tb_bit(BPF_OP(code), is64, imm, &nonzero);
+		if (bit >= 0 && emit_tb(nonzero, dst, bit, i, off, ctx))
+			break;
+		/* A compare against zero for equality is a compare and branch */
+		if (!imm && (BPF_OP(code) == BPF_JEQ || BPF_OP(code) == BPF_JNE)) {
+			jmp_offset = bpf2a64_offset(i, off, ctx);
+			check_imm19(jmp_offset);
+			if (BPF_OP(code) == BPF_JEQ)
+				emit(A64_CBZ(is64, dst, jmp_offset), ctx);
+			else
+				emit(A64_CBNZ(is64, dst, jmp_offset), ctx);
+			break;
+		}
 		if (is_addsub_imm(imm)) {
 			emit(A64_CMP_I(is64, dst, imm), ctx);
 		} else if (is_addsub_imm(-(u32)imm)) {
@@ -1799,6 +1893,10 @@ emit_cond_jmp:
 		goto emit_cond_jmp;
 	case BPF_JMP | BPF_JSET | BPF_K:
 	case BPF_JMP32 | BPF_JSET | BPF_K:
+		/* A test of a single bit within reach is a test bit and branch */
+		bit = tb_bit(BPF_OP(code), is64, imm, &nonzero);
+		if (bit >= 0 && emit_tb(nonzero, dst, bit, i, off, ctx))
+			break;
 		a64_insn = A64_TST_I(is64, dst, imm);
 		if (a64_insn != AARCH64_BREAK_FAULT) {
 			emit(a64_insn, ctx);
@@ -2364,6 +2462,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 	ctx.offset = kvzalloc_objs(int, prog->len + 1);
 	if (ctx.offset == NULL)
 		goto out_off;
+	ctx.tb = kvzalloc_objs(unsigned long, BITS_TO_LONGS(prog->len));
+	if (ctx.tb == NULL)
+		goto out_off;

 	if (bpf_prog_uses_arena_insns(prog)) {
 		ctx.user_vm_start = bpf_arena_get_user_vm_start(prog->aux->arena);
@@ -2511,6 +2612,7 @@ out_off:
 			prog->aux->priv_stack_ptr = NULL;
 		}
 		kvfree(ctx.offset);
+		kvfree(ctx.tb);
 out_priv_stack:
 		kfree(jit_data);
 		prog->aux->jit_data = NULL;
@@ -3569,6 +3671,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.tb);
 			kfree(jit_data);
 		}
 		prog->bpf_func = (void *)prog->bpf_func - cfi_get_offset();

pw-bot: cr

Re: [PATCH bpf-next 19/21] bpf, arm64: Split 24-bit immediates of add, sub and equality compares

[Alexei Starovoitov]

On Tue, Oct 27, 2026 at 11:24 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
> An add, sub or compare with an immediate that neither the plain nor the
> shifted 12-bit field takes moved the immediate into a register first,
> two moves for most immediates up to 24 bits and then the add. Take two
> adds or subs instead, of the upper 12 bits shifted and of the lower 12:
> an instruction fewer, at a cycle more on the path of the operand, as the
> two depend on each other where the moves did not, so an immediate that a
> single move produces keeps the move. A compare for equality takes the
> upper 12 bits off into a scratch register and compares against the lower
> 12, as the subtraction keeps equality.

[...]

>  arch/arm64/net/bpf_jit_comp.c | 113 ++++++++++++++++++++++------------
>  1 file changed, 74 insertions(+), 39 deletions(-)

hmm Can we drop this patch?
It saves 4 bytes and adds a cycle of latency?
Doesn't seem worth it.