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

[PATCH bpf-next v3 00/24] 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 (c3fbffb08183), Tetragon (31e646a5ed0c, the variants
for kernels from 6.1 on), Katran (623234e1814b) and the sched_ext
schedulers (scx at a40cb6115e68) were built with clang 20 for arm64, and
every program of them that loads (338, another 25 fail on both kernels)
was loaded with veristat in the arm64 VM of vmtest.sh, on a kernel
before and one after this series. The size is jited_prog_len, the cycles
and uops are those of the llvm-mca 20 models of the Neoverse N1
(Graviton2, Ampere Altra), N2 (Cobalt 100), V1 (Graviton3) and V2
(Graviton4, Grace, Axion) over the JITed images as straight-line code,
without the helper calls, which llvm-mca cannot model, and the LSE
atomics, which the models have no scheduling information for. This is a
static model without the path taken, branch prediction or cache misses,
but both sides get the same program, so the delta is what the series
rewrote. All numbers are averaged over two boots of each kernel, as a
map address with a zero 16-bit halfword takes one move less.

Project    Progs     Size  N1 cycles  N2 cycles  V1 cycles  V2 cycles  N1 uOps  N2 uOps  V1 uOps  V2 uOps
---------- -----  -------  ---------  ---------  ---------  ---------  -------  -------  -------  -------
cilium       160   -3.31%     -7.36%    -11.26%     -6.86%     -9.35%   -3.52%   -3.94%   -3.53%   -3.53%
katran         5   -6.41%     -7.53%     -9.07%     -8.57%     -0.36%   -6.35%   -8.44%   -6.39%   -6.38%
scx           99   -5.95%     -7.63%     -6.60%     -7.11%     -5.43%   -5.91%   -4.79%   -6.06%   -6.02%
tetragon      74   -4.23%     -5.83%     -5.92%     -6.30%     -3.31%   -4.46%   -4.63%   -4.51%   -4.50%
all          338   -3.88%     -6.88%     -9.01%     -6.71%     -6.91%   -4.08%   -4.30%   -4.11%   -4.10%

Cilium gains the most cycles from its 355 divisions by NSEC_PER_SEC in
81 programs, which come from the monotonic clock helper that conntrack,
NAT and the load balancer run for every entry: all four models put a
64-bit udiv at 20 cycles against 11 to 13 for the magic number sequence,
and the N2 and V2 models do not pipeline the divider at all. The
schedulers have 14 divisions in 7 programs, mostly by 100 and 1000000.
The rest of the cycles and most of the uops come from the branches:
12711 compares against zero and their branch become a cbz or cbnz, and
2961 sign and bit tests a tbz or tbnz, a uop and a cycle each. Then 979
loads and stores take the unscaled form, 505 xors with all ones become a
mvn, 482 stores of zero take the zero register, 187 tail calls lose six
instructions each, and 98 multiplications become an add or sub with a
shifted register. Katran stays flat on V2, whose model dispatches 16
wide.

For a feel of the native code, the tail call of Katran's xdp_root
program, from the bounds checks to the test of the program slot.

Before:

  3c:    5280088a     mov    w10, #68
  40:    b86a682a     ldr    w10, [x1, x10]
  44:    2a0203e2     mov    w2, w2
  48:    6b0a005f     cmp    w2, w10
  4c:    54000222     b.hs   #68
  50:    5280042a     mov    w10, #33
  54:    f940034c     ldr    x12, [x26]
  58:    eb0a019f     cmp    x12, x10
  5c:    540001a2     b.hs   #52
  60:    9100058c     add    x12, x12, #1
  64:    5280440a     mov    w10, #544
  68:    8b0a002a     add    x10, x1, x10
  6c:    d37df04b     lsl    x11, x2, #3
  70:    f86b694b     ldr    x11, [x10, x11]
  74:    b40000eb     cbz    x11, #28

After:

  3c:    b940442a     ldr    w10, [x1, #68]
  40:    6b0a005f     cmp    w2, w10
  44:    540001a2     b.hs   #52
  48:    f940034c     ldr    x12, [x26]
  4c:    f100859f     cmp    x12, #33
  50:    54000142     b.hs   #40
  54:    9100058c     add    x12, x12, #1
  58:    9108802a     add    x10, x1, #544
  5c:    f862594b     ldr    x11, [x10, w2, uxtw #3]
  60:    b40000cb     cbz    x11, #24

Of the 338 programs, 303 get smaller, and 284, 270, 277 and 225 faster
on N1, N2, V1 and V2. The best cases:

  Impact     Largest decrease                                    Largest relative decrease
  ---------  --------------------------------------------------  ------------------------------------
  size       generic_usdt_filter_arg      27388 > 26256  -4.13%  pandemonium_enable 280 > 224 -20.00%
  N1 cycles  tail_handle_ipv6                922 > 807 -12.52%  flash_select_cpu     74 > 53 -28.38%
  N2 cycles  tail_handle_ipv6                760 > 605 -20.39%  flash_enqueue       179 > 98 -45.25%
  V1 cycles  tail_handle_ipv4                542 > 471 -13.10%  flash_select_cpu     66 > 41 -37.88%
  V2 cycles  tail_handle_ipv6_from_netdev    441 > 339 -23.13%  flash_enqueue       147 > 67 -54.42%

The largest gains in cycles are in Cilium's bpf_lxc.o and bpf_host.o,
whose programs above hold 7 to 11 of the divisions by NSEC_PER_SEC each,
and in Tetragon's generic_usdt_filter_arg for size, which turns 243 of
its 961 conditional branches into a cbz, cbnz, tbz or tbnz. The scx_flash
programs gain the most relative to their length, from their divisions by
100.

No project gets bigger or slower on any model. The worst cases per
program, which for the cycles are the same in every pairing of a boot
before with one after the series:

  Impact     Worse  Largest increase                             Largest relative increase
  ---------  -----  -------------------------------------------  ---------------------------------
  size           3  flash_select_cpu            616 > 640 +3.90%  the same
  N1 cycles      1  rusty_set_weight              42 > 43 +2.38%  the same
  N2 cycles      1  rusty_set_weight              37 > 38 +2.70%  the same
  V1 cycles      2  rusty_stopping                92 > 94 +2.17%  rusty_set_weight   37 > 38 +2.70%
  V2 cycles     10  tail_nodeport_nat_egress_ipv4 295 > 301 +2.03%  mitosis_dump_task 49 > 52 +6.12%

Of the three programs that grow, flash_select_cpu and flash_enqueue of
scx_flash do so by 24 and 16 bytes for their divisions by 100, and
tail_drop_notify of Cilium's bpf_xdp only in one pairing of boots. None
of the 12 programs that some model rates slower has more instructions;
their changes are compares and branches that became a cbz or cbnz, which
the model then issues in another order. The uops grow in 3 programs, 4
on N2, by at most 2.86%.

The rewrites on their own, in llvm-mca for one instance of each sequence
as the JIT emits it, in a single pass with the pipeline fill included.
An arena access at an immediate offset keeps its cycles, the add of the
offset now off the path of the offset register, at a uop more on N2.

  cycles, uops                N1          N2          V1          V2
  r2 /= 1000000000            25>13 3>7   25>11 3>7   25>11 3>7   25>11 3>7
  r3 /= 100                   24>13 2>7   24>11 2>7   24>11 2>7   24>11 2>7
  if r6 == 0 goto               5>4 2>1     5>4 2>1     5>4 2>1     5>4 2>1
  if w0 s< 0 goto               5>4 2>1     5>4 2>1     5>4 2>1     5>4 2>1
  w2 = *(u32 *)(r8 + 6)         8>7 2>1     8>7 3>1     8>7 2>1     8>7 2>1
  arena r0 = *(u64 *)(r9 + 0)   8>7 2>1     8>7 2>2     8>7 2>1     8>7 2>1
  *(u64 *)(r1 + 0) = 0          5>4 3>2     5>4 3>2     5>4 3>2     4>4 3>2
  w1 ^= -1                      5>4 2>1     5>4 2>1     5>4 2>1     5>4 2>1
  r0 *= 24                      8>5 2>2     6>5 2>2     6>5 2>2     6>5 2>2
  w1 *= 65537                   7>5 3>1     7>5 3>1     7>5 3>1     7>5 3>1
  if w2 > 0xffff goto           6>5 3>2     6>5 3>2     6>5 3>2     6>5 3>2
  tail call slot of w3          9>8 4>2     9>8 5>3     9>8 4>2     9>8 4>2

Thanks,
Daniel

v2 -> v3:
  - Divide by constants in the verifier via UHMUL/SHMUL, replacing v2 07
    and 15 and x86's emit_div_const() (Alexei)
  - x86 now keeps a div for smod and for umod by divisors that need the
    add sequence or a dividend shift
  - tbz/tbnz decided once from the pass 1 offsets, dropping extra_pass,
    max_idx and the new multi-func bound (Alexei)
  - New fix: measure branches back from the branch itself; the sizing
    pass failed conditional branches back to targets ~1MB into the image
  - int shift after the extend in the register offset encoder instead of
    the scaled flag (Alexei)
  - Dropped the A64_LDR*()/A64_STR*() macros left unused (Alexei), and
    the already unused A64_BL, A64_BTI_C and A64_LDR32LIT
  - Encoders reject what they cannot encode as given: bad extends, ADR
    beyond 4GB, STXR/LDP/STP overlaps and branch counts that wrap
  - Rebased onto the PROBE_MEM user address filter and BPF_REG_ARENA_SP
  - Kernel comment style, shorter comments and commit messages (sashiko,
    bpf ci bot)
  - New verifier_div_const test; jit_insns adds a far branch back, the
    PROBE_MEM filter offsets, the tbz/tbnz reach, jset and sign jumps
v1 -> v2:
  - Share the divisor selection with x86 via bpf_magic_div() in the core
    instead of copying it into the arm64 JIT (Alexei)
  - tailcall: ldr x11, [x10, w2, uxtw #3] in place of ubfiz + ldr, with
    a scaled flag in the register offset encoder (Xu)
  - tbz/tbnz decided once in pass 2 from the sizing pass offsets, no
    repeated sizing passes (Alexei)
  - Dropped the 24-bit immediate split which was 4 bytes for a cycle
    of latency (Alexei)
  - Arena acquire/release test insns built with __imm_insn() (bpf ci bot)

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

Daniel Borkmann (24):
  bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT
  bpf, arm64: Free the offset table of a subprog in bpf_jit_free
  bpf, arm64: Free the private stack when a pass over the image fails
  bpf, arm64: Emit ISB SY in the speculation barriers
  arm64, insn: Reject sign extending loads of 64 bits
  bpf, arm64: Keep the ll/sc atomics address apart from the old value
  bpf, arm64: Measure backward branches from the branch itself
  arm64, insn: Reject invalid and unpredictable operands in the encoders
  bpf, arm64: Widen the branch offsets before scaling them to bytes
  arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings
  bpf: Divide by constants via uhmul and shmul in the verifier
  bpf, arm64: Consolidate the load and store emission into a helper
  bpf, arm64: Use the unscaled forms for negative and unaligned offsets
  bpf, arm64: Store zero immediates from the zero register
  bpf, arm64: Zero extend the arena offset in register offset accesses
  bpf, arm64: Adjust compares with unencodable immediates by one
  bpf, arm64: Materialize immediates with fewer instructions
  bpf, arm64: Shorten the tail call sequence
  bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones
  bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests
  bpf, arm64: Multiply by constants with shifts, adds and subs
  selftests/bpf: Let the arm64 private stack check skip the BTI pad
  selftests/bpf: Test the verifier's division by constants
  selftests/bpf: Extend the JIT instruction tests for arm64 encodings

 arch/arm64/include/asm/insn.h                 |  21 +-
 arch/arm64/lib/insn.c                         | 173 +++-
 arch/arm64/net/bpf_jit.h                      |  69 +-
 arch/arm64/net/bpf_jit_comp.c                 | 769 +++++++++++++-----
 arch/x86/net/bpf_jit_comp.c                   | 219 +----
 kernel/bpf/fixups.c                           | 199 +++++
 .../selftests/bpf/prog_tests/jit_insns.c      | 753 +++++++++++++++--
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/jit_insns_arena.c     | 446 +++++++++-
 .../selftests/bpf/progs/verifier_div_const.c  | 225 +++++
 .../selftests/bpf/progs/verifier_ldsx.c       |  24 +-
 .../bpf/progs/verifier_private_stack.c        |   1 +
 12 files changed, 2340 insertions(+), 561 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_div_const.c

-- 
2.43.0

[PATCH bpf-next v3 01/24] bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT

[Daniel Borkmann]

A64_BL() and A64_LDR32LIT() never had a user. A64_BTI_C lost its last
user when commit a3f25d614bc7 ("bpf, arm64: Fix BTI type used for
freplace attached functions") made the prologue emit BTI JC. Remove
them.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 70fc329c661d..52e9d8eda3e9 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -45,7 +45,6 @@
 #define A64_BRANCH(offset, type) aarch64_insn_gen_branch_imm(0, offset, \
 	AARCH64_INSN_BRANCH_##type)
 #define A64_B(imm26)  A64_BRANCH((imm26) << 2, NOLINK)
-#define A64_BL(imm26) A64_BRANCH((imm26) << 2, LINK)
 
 /* Unconditional branch (register) */
 #define A64_BR(Rn)  aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_NOLINK)
@@ -87,8 +86,6 @@
 #define A64_LDR64I(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, LOAD)
 
 /* LDR (literal) */
-#define A64_LDR32LIT(Wt, offset) \
-	aarch64_insn_gen_load_literal(0, offset, Wt, false)
 #define A64_LDR64LIT(Xt, offset) \
 	aarch64_insn_gen_load_literal(0, offset, Xt, true)
 
@@ -324,7 +321,6 @@
 #define A64_AUTIASP A64_HINT(AARCH64_INSN_HINT_AUTIASP)
 
 /* BTI */
-#define A64_BTI_C  A64_HINT(AARCH64_INSN_HINT_BTIC)
 #define A64_BTI_J  A64_HINT(AARCH64_INSN_HINT_BTIJ)
 #define A64_BTI_JC A64_HINT(AARCH64_INSN_HINT_BTIJC)
 #define A64_NOP    A64_HINT(AARCH64_INSN_HINT_NOP)
-- 
2.43.0

[PATCH bpf-next v3 02/24] bpf, arm64: Free the offset table of a subprog in bpf_jit_free

[Daniel Borkmann]

When jit_subprogs() fails after some subprogs were already JITed, it
frees them through bpf_jit_free(). That frees jit_data, but not the
offset table that jit_data keeps for the extra pass, so every such
failure leaks the table.

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

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 6deedb169915..e72bf79d219c 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -3616,6 +3616,7 @@ void bpf_jit_free(struct bpf_prog *prog)
 		 */
 		if (jit_data) {
 			bpf_jit_binary_pack_finalize(jit_data->ro_header, jit_data->header);
+			kvfree(jit_data->ctx.offset);
 			kfree(jit_data);
 		}
 		prog->bpf_func = (void *)prog->bpf_func - cfi_get_offset();
-- 
2.43.0

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

[Daniel Borkmann]

When a pass over the image fails, including the extra pass of a
subprog, the image is freed but ro_header is left set. The exit path
then skips freeing the private stack. It stays allocated behind
priv_stack_ptr, and bpf_jit_free() does not free it either, as the
program is not marked as JITed.

Clear ro_header and header once the image is freed, so that the exit
path frees the private stack as it does for failures before the image
was allocated. The x86 JIT does the same with its image pointer.

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 e72bf79d219c..976282418909 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -2564,6 +2564,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 v3 04/24] bpf, arm64: Emit ISB SY in the speculation barriers

[Daniel Borkmann]

The Spectre-BHB loop in the epilogue and BPF_NOSPEC on CPUs without
FEAT_SB both end in an ISB. The JIT takes its encoding from the
instruction matcher's template, which leaves CRm as 0. The Arm ARM
lists that encoding as reserved.

Emit ISB SY instead, with CRm set to 0b1111. This is also what the
assembler emits for the kernel's own isb().

Before/after:

  d50330df  isb #0
  d5033fdf  isb

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-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 52e9d8eda3e9..79fb399681dd 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -343,6 +343,6 @@
 /* Barriers */
 #define A64_SB aarch64_insn_get_sb_value()
 #define A64_DSB_NSH (aarch64_insn_get_dsb_base_value() | 0x7 << 8)
-#define A64_ISB aarch64_insn_get_isb_value()
+#define A64_ISB (aarch64_insn_get_isb_value() | 0xf << 8)
 
 #endif /* _BPF_JIT_H */
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 976282418909..cb17e6daaea4 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -1044,7 +1044,7 @@ static void __maybe_unused build_bhb_mitigation(struct jit_ctx *ctx)
 		emit(A64_SUBS_I(true, r1, r1, 1), ctx);
 		emit(A64_B_(A64_COND_NE, -2), ctx);
 		emit(aarch64_insn_gen_dsb(AARCH64_INSN_MB_ISH), ctx);
-		emit(aarch64_insn_get_isb_value(), ctx);
+		emit(A64_ISB, ctx);
 	}
 
 	if (is_spectre_bhb_fw_mitigated()) {
-- 
2.43.0

[PATCH bpf-next v3 05/24] arm64, insn: Reject sign extending loads of 64 bits

[Daniel Borkmann]

With the 64-bit size, the encoding of LDRSB, LDRSH and LDRSW becomes
PRFM. So when asked for a 64-bit sign extending load, the load and
store encoders returned a prefetch instead of failing. The BPF JIT
never asks for one, as BPF_MEMSX has no BPF_DW form, but return
AARCH64_BREAK_FAULT as for other invalid operands.

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

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

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 dc483d1b8bd5..48a481aa9656 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 v3 06/24] bpf, arm64: Keep the ll/sc atomics address apart from the old value

[Daniel Borkmann]

With a zero offset, the ll/sc fetching atomics use dst_reg directly as
the address. They load the old value into src_reg, or into r0 for
cmpxchg, and then store through dst_reg. If that register is dst_reg
itself, the load overwrites the address, and the store then uses the
old value as its address. The verifier rejects such programs, but the
JIT should not rely on that.

Copy the address into a temporary when the register receiving the old
value is the address register. The LSE forms are not affected.

Before/after for r1 = atomic_fetch_add((u64 *)(r1 + 0), r1) without LSE:

  aa0003e9  mov x9, x0
  c85f7c00  ldxr x0, [x0]
  8b09000b  add x11, x0, x9
  c80cfc0b  stlxr w12, x11, [x0]
  35ffffac  cbnz w12, ...
  d5033bbf  dmb ish

  aa0003ea  mov x10, x0
  aa0003e9  mov x9, x0
  c85f7d40  ldxr x0, [x10]
  8b09000b  add x11, x0, x9
  c80cfd4b  stlxr w12, x11, [x10]
  35ffffac  cbnz w12, ...
  d5033bbf  dmb ish

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 cb17e6daaea4..fa57783d7014 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -888,6 +888,7 @@ static int emit_ll_sc_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)
 	const s32 imm = insn->imm;
 	const s16 off = insn->off;
 	const bool isdw = BPF_SIZE(code) == BPF_DW;
+	const int load_reg = bpf_atomic_load_reg(insn);
 	u8 reg = dst;
 	s32 jmp_offset;
 
@@ -901,6 +902,11 @@ static int emit_ll_sc_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)
 		emit_a64_add_i(1, tmp, reg, tmp, off, ctx);
 		reg = tmp;
 	}
+	/* The load of the old value must not clobber the address */
+	if (load_reg >= 0 && bpf2a64[load_reg] == reg) {
+		emit(A64_MOV(1, tmp, reg), ctx);
+		reg = tmp;
+	}
 
 	if (imm == BPF_ADD || imm == BPF_AND ||
 	    imm == BPF_OR || imm == BPF_XOR) {
-- 
2.43.0

[PATCH bpf-next v3 07/24] bpf, arm64: Measure backward branches from the branch itself

[Daniel Borkmann]

bpf2a64_offset() takes the position of a branch from the offset of the
next BPF instruction, which the current pass has not set yet:

  - In the sizing pass that offset is still 0, so a branch back gets
    the target's instruction index plus one as its offset. This exceeds
    the imm19 maximum of 2^18 - 1 instructions once the target is at
    index 2^18 - 1 or later, i.e. 4 bytes short of 1MB into the image,
    and check_imm19() fails the program.
  - In the second pass it still holds the value from the first pass,
    so a branch back is overestimated by however much the code in
    front of it shrank.

For a branch back, take ctx->idx instead, which is the position of the
branch in every pass.

Fixes: 2589726d12a1 ("bpf: introduce bounded loops")
Fixes: ddbe9ec55039 ("bpf, arm64: Jit BPF_CALL to direct call when possible")
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 fa57783d7014..3403f4327de8 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -267,6 +267,12 @@ static inline int bpf2a64_offset(int bpf_insn, int off,
 {
 	/* BPF JMP offset is relative to the next instruction */
 	bpf_insn++;
+	/*
+	 * A branch back counts from itself, as the offsets from the next
+	 * instruction on are not yet those of this pass.
+	 */
+	if (off < 0)
+		return ctx->offset[bpf_insn + off] - ctx->idx;
 	/*
 	 * Whereas arm64 branch instructions encode the offset
 	 * from the branch itself, so we must subtract 1 from the
-- 
2.43.0

[PATCH bpf-next v3 08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders

[Daniel Borkmann]

A few encoders return a valid instruction for operands the instruction
cannot take, instead of AARCH64_BREAK_FAULT:

  - The extended register add and sub put any @extend into the 3-bit
    option field, so -1 becomes SXTX and 8 becomes UXTB.
  - ADR truncates its offset to 32 bits before the range check, so an
    offset beyond 4GB can wrap into range.
  - STXR and STLXR accept a status register equal to the data or base
    register, LDP equal target registers, and pre- and post-index LDP
    and STP a target register equal to the base. The Arm ARM makes all
    of these CONSTRAINED UNPREDICTABLE.

Reject them. No caller passes such operands, so this only keeps a
future caller from silently emitting a wrong or unpredictable
instruction.

Also print the size, not the type, when the immediate offset load and
store encoder rejects a size.

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

diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
index 48a481aa9656..87a06bd08811 100644
--- a/arch/arm64/lib/insn.c
+++ b/arch/arm64/lib/insn.c
@@ -426,7 +426,7 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
 	u32 shift;
 
 	if (size < AARCH64_INSN_SIZE_8 || size > AARCH64_INSN_SIZE_64) {
-		pr_err("%s: unknown size encoding %d\n", __func__, type);
+		pr_err("%s: unknown size encoding %d\n", __func__, size);
 		return AARCH64_BREAK_FAULT;
 	}
 
@@ -542,6 +542,18 @@ u32 aarch64_insn_gen_load_store_pair(enum aarch64_insn_register reg1,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	/*
+	 * CONSTRAINED UNPREDICTABLE: LDP with Rt == Rt2, and a base written
+	 * back that is Rt or Rt2
+	 */
+	if ((reg1 == reg2 && (type == AARCH64_INSN_LDST_LOAD_PAIR_PRE_INDEX ||
+			      type == AARCH64_INSN_LDST_LOAD_PAIR_POST_INDEX)) ||
+	    (base != AARCH64_INSN_REG_SP && (reg1 == base || reg2 == base))) {
+		pr_err("%s: overlapping registers %d, %d, %d\n", __func__,
+		       reg1, reg2, base);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn,
 					    reg1);
 
@@ -610,6 +622,15 @@ u32 aarch64_insn_gen_load_store_ex(enum aarch64_insn_register reg,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	/* CONSTRAINED UNPREDICTABLE: the status register Rs as Rt or Rn */
+	if ((type == AARCH64_INSN_LDST_STORE_EX ||
+	     type == AARCH64_INSN_LDST_STORE_REL_EX) &&
+	    (state == reg || (state == base && base != AARCH64_INSN_REG_SP))) {
+		pr_err("%s: overlapping registers %d, %d, %d\n", __func__,
+		       state, reg, base);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	insn = aarch64_insn_encode_ldst_size(size, insn);
 
 	insn = aarch64_insn_encode_register(AARCH64_INSN_REGTYPE_RT, insn,
@@ -1042,6 +1063,12 @@ u32 aarch64_insn_gen_add_sub_extended_reg(enum aarch64_insn_register dst,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	if (extend < AARCH64_INSN_EXTEND_UXTB ||
+	    extend > AARCH64_INSN_EXTEND_SXTX) {
+		pr_err("%s: invalid extend encoding %d\n", __func__, extend);
+		return AARCH64_BREAK_FAULT;
+	}
+
 	if (shift < 0 || shift > 4) {
 		pr_err("%s: invalid shift encoding %d\n", __func__, shift);
 		return AARCH64_BREAK_FAULT;
@@ -1293,6 +1320,9 @@ u32 aarch64_insn_gen_adr(unsigned long pc, unsigned long addr,
 	switch (type) {
 	case AARCH64_INSN_ADR_TYPE_ADR:
 		insn = aarch64_insn_get_adr_value();
+		/* The s32 offset would truncate a difference beyond 4GB */
+		if ((long)(addr - pc) != (s32)(addr - pc))
+			return AARCH64_BREAK_FAULT;
 		offset = addr - pc;
 		break;
 	case AARCH64_INSN_ADR_TYPE_ADRP:
-- 
2.43.0

[PATCH bpf-next v3 09/24] bpf, arm64: Widen the branch offsets before scaling them to bytes

[Daniel Borkmann]

The branch macros shift their instruction count left by 2 as an int. A
count of magnitude 2^29 or more overflows, possibly into range, and
yields a valid branch to the wrong place instead of AARCH64_BREAK_FAULT.
No caller gets near that, but widen the count to a long before scaling
it, so that the encoders range check the full offset.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 79fb399681dd..d3e70de49b44 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -19,12 +19,16 @@
 #define A64_VARIANT(sf) \
 	((sf) ? AARCH64_INSN_VARIANT_64BIT : AARCH64_INSN_VARIANT_32BIT)
 
+/* Branch offsets in bytes, widened first so a far count cannot wrap */
+#define A64_BR_OFF(imm) ((long)(imm) * AARCH64_INSN_SIZE)
+
 /* Compare & branch (immediate) */
 #define A64_COMP_BRANCH(sf, Rt, offset, type) \
 	aarch64_insn_gen_comp_branch_imm(0, offset, Rt, A64_VARIANT(sf), \
 		AARCH64_INSN_BRANCH_COMP_##type)
-#define A64_CBZ(sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, (imm19) << 2, ZERO)
-#define A64_CBNZ(sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, (imm19) << 2, NONZERO)
+#define A64_CBZ(sf, Rt, imm19) A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), ZERO)
+#define A64_CBNZ(sf, Rt, imm19) \
+	A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), NONZERO)
 
 /* Conditional branch (immediate) */
 #define A64_COND_BRANCH(cond, offset) \
@@ -39,12 +43,12 @@
 #define A64_COND_GT	AARCH64_INSN_COND_GT /* signed > */
 #define A64_COND_LE	AARCH64_INSN_COND_LE /* signed <= */
 #define A64_COND_LT	AARCH64_INSN_COND_LT /* signed < */
-#define A64_B_(cond, imm19) A64_COND_BRANCH(cond, (imm19) << 2)
+#define A64_B_(cond, imm19) A64_COND_BRANCH(cond, A64_BR_OFF(imm19))
 
 /* Unconditional branch (immediate) */
 #define A64_BRANCH(offset, type) aarch64_insn_gen_branch_imm(0, offset, \
 	AARCH64_INSN_BRANCH_##type)
-#define A64_B(imm26)  A64_BRANCH((imm26) << 2, NOLINK)
+#define A64_B(imm26)  A64_BRANCH(A64_BR_OFF(imm26), NOLINK)
 
 /* Unconditional branch (register) */
 #define A64_BR(Rn)  aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_NOLINK)
-- 
2.43.0

[PATCH bpf-next v3 10/24] arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings

[Daniel Borkmann]

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

  - LDUR, STUR and LDURS{B,H,W}: loads and stores with a signed 9-bit
    byte offset, for the negative and unaligned offsets that the scaled
    forms cannot encode.
  - TBZ and TBNZ: test a single bit and branch, within +/-32KB.
  - Extend and shift parameters for the register offset loads and
    stores, in the same order as the extended register add and sub
    take them. They allow UXTW of a 32-bit offset register, and
    scaling the offset by the access size. UXTX gives the plain 64-bit
    register form as before.
  - A check that UMULH and SMULH use the 64-bit variant with Ra set to
    the zero register, as their encoding requires.

The JIT is the only user of the register offset encoder. It passes UXTX
without a shift, so its loads and stores stay the same, except for the
sign extending ones: their template had SXTX, which does the same for a
64-bit offset register, and they now get UXTX like the others.

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

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/include/asm/insn.h |  21 +++++-
 arch/arm64/lib/insn.c         | 129 ++++++++++++++++++++++++++++++++++
 arch/arm64/net/bpf_jit.h      |  10 +--
 3 files changed, 155 insertions(+), 5 deletions(-)

diff --git a/arch/arm64/include/asm/insn.h b/arch/arm64/include/asm/insn.h
index f38738fa54a2..4834bf8ab87e 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,7 @@ enum aarch64_insn_adsb_type {
 	AARCH64_INSN_ADSB_SUB_SETFLAGS
 };
 
-/* option field of add/sub (extended register) */
+/* option field of add/sub (extended register) and load/store (register) */
 enum aarch64_insn_extend_type {
 	AARCH64_INSN_EXTEND_UXTB,
 	AARCH64_INSN_EXTEND_UXTH,
@@ -355,6 +360,9 @@ __AARCH64_INSN_FUNCS(store_post,	0x3FE00C00, 0x38000400)
 __AARCH64_INSN_FUNCS(load_post,	0x3FE00C00, 0x38400400)
 __AARCH64_INSN_FUNCS(str_reg,	0x3FE0EC00, 0x38206800)
 __AARCH64_INSN_FUNCS(str_imm,	0x3FC00000, 0x39000000)
+__AARCH64_INSN_FUNCS(stur,	0x3FE00C00, 0x38000000)
+__AARCH64_INSN_FUNCS(ldur,	0x3FE00C00, 0x38400000)
+__AARCH64_INSN_FUNCS(signed_ldur, 0x3FE00C00, 0x38800000)
 __AARCH64_INSN_FUNCS(ldadd,	0x3F20FC00, 0x38200000)
 __AARCH64_INSN_FUNCS(ldclr,	0x3F20FC00, 0x38201000)
 __AARCH64_INSN_FUNCS(ldeor,	0x3F20FC00, 0x38202000)
@@ -586,6 +594,10 @@ u32 aarch64_insn_gen_comp_branch_imm(unsigned long pc, unsigned long addr,
 				     enum aarch64_insn_register reg,
 				     enum aarch64_insn_variant variant,
 				     enum aarch64_insn_branch_type type);
+u32 aarch64_insn_gen_test_branch_imm(unsigned long pc, unsigned long addr,
+				     enum aarch64_insn_register reg,
+				     int bit,
+				     enum aarch64_insn_branch_type type);
 u32 aarch64_insn_gen_cond_branch_imm(unsigned long pc, unsigned long addr,
 				     enum aarch64_insn_condition cond);
 
@@ -610,6 +622,8 @@ u32 aarch64_insn_gen_branch_reg(enum aarch64_insn_register reg,
 u32 aarch64_insn_gen_load_store_reg(enum aarch64_insn_register reg,
 				    enum aarch64_insn_register base,
 				    enum aarch64_insn_register offset,
+				    enum aarch64_insn_extend_type extend,
+				    int shift,
 				    enum aarch64_insn_size_type size,
 				    enum aarch64_insn_ldst_type type);
 u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
@@ -617,6 +631,11 @@ u32 aarch64_insn_gen_load_store_imm(enum aarch64_insn_register reg,
 				    unsigned int imm,
 				    enum aarch64_insn_size_type size,
 				    enum aarch64_insn_ldst_type type);
+u32 aarch64_insn_gen_load_store_unscaled(enum aarch64_insn_register reg,
+					 enum aarch64_insn_register base,
+					 int imm,
+					 enum aarch64_insn_size_type size,
+					 enum aarch64_insn_ldst_type type);
 u32 aarch64_insn_gen_load_literal(unsigned long pc, unsigned long addr,
 				  enum aarch64_insn_register reg,
 				  bool is64bit);
diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
index 87a06bd08811..540888474a71 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,16 @@ 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, then shifted left by @shift, which is 0 or the log2 of the access size.
+ */
 u32 aarch64_insn_gen_load_store_reg(enum aarch64_insn_register reg,
 				    enum aarch64_insn_register base,
 				    enum aarch64_insn_register offset,
+				    enum aarch64_insn_extend_type extend,
+				    int shift,
 				    enum aarch64_insn_size_type size,
 				    enum aarch64_insn_ldst_type type)
 {
@@ -405,6 +454,33 @@ u32 aarch64_insn_gen_load_store_reg(enum aarch64_insn_register reg,
 		return AARCH64_BREAK_FAULT;
 	}
 
+	if (size < AARCH64_INSN_SIZE_8 || size > AARCH64_INSN_SIZE_64) {
+		pr_err("%s: unknown size encoding %d\n", __func__, size);
+		return AARCH64_BREAK_FAULT;
+	}
+
+	/* S in bit 12 shifts by the access size, so only that or 0 */
+	if (shift && shift != aarch64_insn_ldst_size[size]) {
+		pr_err("%s: invalid shift encoding %d\n", __func__, shift);
+		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 for the shift */
+		insn &= ~GENMASK(15, 12);
+		insn |= extend << 13;
+		if (shift)
+			insn |= BIT(12);
+		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 +545,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)
@@ -1205,6 +1325,15 @@ u32 aarch64_insn_gen_data3(enum aarch64_insn_register dst,
 		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 d3e70de49b44..3dcc2d2cf035 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -55,11 +55,13 @@
 #define A64_BLR(Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_LINK)
 #define A64_RET(Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_RETURN)
 
-/* Load/store register (register offset) */
-#define A64_LS_REG(Rt, Rn, Rm, size, type) \
-	aarch64_insn_gen_load_store_reg(Rt, Rn, Rm, \
-		AARCH64_INSN_SIZE_##size, \
+/* Load/store register (register offset), at Rn + (EXT(Rm) << shift) */
+#define A64_LS_REG_EXT(Rt, Rn, Rm, ext, shift, size, type) \
+	aarch64_insn_gen_load_store_reg(Rt, Rn, Rm, AARCH64_INSN_EXTEND_##ext, \
+		shift, AARCH64_INSN_SIZE_##size, \
 		AARCH64_INSN_LDST_##type##_REG_OFFSET)
+#define A64_LS_REG(Rt, Rn, Rm, size, type) \
+	A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type)
 #define A64_STRB(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 8, STORE)
 #define A64_LDRB(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 8, LOAD)
 #define A64_LDRSB(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 8, SIGNED_LOAD)
-- 
2.43.0

[PATCH bpf-next v3 11/24] bpf: Divide by constants via uhmul and shmul in the verifier

[Daniel Borkmann]

LLVM has no high-half multiply to strength-reduce 64-bit divisions by a
constant, so they reach the kernel as BPF_DIV and BPF_MOD with BPF_K.
On arm64, that is a udiv or sdiv of 5 to 20 cycles.

Rewrite them in bpf_do_misc_fixups() into a uhmul or shmul by the magic
number, for the JITs that support UHMUL and SHMUL. This replaces
emit_div_const() in the x86 JIT.

With AX as the only scratch register, smod keeps the division, and so
does umod when the divisor needs the add sequence or a dividend shift.
The division is also kept for a divisor of 1, an unsigned divisor above
2^63, and for blinded or offloaded programs.

Powers of two are not special-cased, as LLVM already emits shifts for
them. The sequences were checked in user space against C division
across the imm32 range.

Like other rewrites that grow a program, this one can leave a jump at
the edge of its range over such a division unpatchable. So jit_insns'
max_jmp now divides by -7, which stays a division.

Before/after on x86 for r1 /= 1000. r1 %= 1000 is back to a div, as
1000 needs the add sequence or a dividend shift:

  50                             pushq %rax
  52                             pushq %rdx
  48 89 f8                       movq %rdi,%rax
  48 c1 e8 03                    shrq $0x3,%rax
  49 bb cf f7 53 e3 a5 9b c4 20  movabsq $0x20c49ba5e353f7cf,%r11
  49 f7 e3                       mulq %r11
  48 c1 ea 04                    shrq $0x4,%rdx
  48 89 d7                       movq %rdx,%rdi
  5a                             popq %rdx
  58                             popq %rax

  48 c1 ef 03                    shrq $0x3,%rdi
  49 ba cf f7 53 e3 a5 9b c4 20  movabsq $0x20c49ba5e353f7cf,%r10
  4d 89 d3                       movq %r10,%r11
  50                             pushq %rax
  52                             pushq %rdx
  48 89 f8                       movq %rdi,%rax
  49 f7 e3                       mulq %r11
  48 89 d7                       movq %rdx,%rdi
  5a                             popq %rdx
  58                             popq %rax
  48 c1 ef 04                    shrq $0x4,%rdi

Suggested-by: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/x86/net/bpf_jit_comp.c                   | 219 +-----------------
 kernel/bpf/fixups.c                           | 199 ++++++++++++++++
 .../selftests/bpf/prog_tests/jit_insns.c      |  26 +--
 3 files changed, 208 insertions(+), 236 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 320cf9b526b3..5bc744c42f7f 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2035,218 +2035,6 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op)
 	*pprog = prog;
 }
 
-struct bpf_div_magic {
-	u64 m;		/* multiplier, sign extended for signed division */
-	int s;		/* shift of the high half of the product */
-	bool add;	/* multiplier has 65 bits, use the add sequence */
-};
-
-/*
- * Multiplier and shift for an unsigned division by the constant d, with
- * 2 <= d < 2^64 and a dividend below 2^(64 - lz): n / d == (mulhu(n, m)
- * >> s), or with the add sequence when m needs 65 bits, (((n - t) >> 1)
- * + t) >> (s - 1) with t = mulhu(n, m). Hacker's Delight, 2nd ed., figure
- * 10-2.
- */
-static void bpf_magic_udiv(u64 d, int lz, struct bpf_div_magic *mag)
-{
-	u64 mask = ~0ULL >> (lz & 63);
-	u64 nc, delta, q1, r1, q2, r2;
-	int p;
-
-	mag->add = false;
-	/* Largest value with nc mod d == d - 1 */
-	nc = mask - (mask % d + 1) % d;
-	p = 63;
-	q1 = (1ULL << 63) / nc;			/* 2^p / nc */
-	r1 = (1ULL << 63) - q1 * nc;		/* 2^p mod nc */
-	q2 = (~0ULL >> 1) / d;			/* (2^p - 1) / d */
-	r2 = (~0ULL >> 1) - q2 * d;		/* (2^p - 1) mod d */
-	do {
-		p++;
-		if (r1 >= nc - r1) {
-			q1 = 2 * q1 + 1;
-			r1 = 2 * r1 - nc;
-		} else {
-			q1 = 2 * q1;
-			r1 = 2 * r1;
-		}
-		if (r2 + 1 >= d - r2) {
-			if (q2 >= (~0ULL >> 1))
-				mag->add = true;
-			q2 = 2 * q2 + 1;
-			r2 = 2 * r2 + 1 - d;
-		} else {
-			if (q2 >= (1ULL << 63))
-				mag->add = true;
-			q2 = 2 * q2;
-			r2 = 2 * r2 + 1;
-		}
-		delta = d - 1 - r2;
-	} while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0)));
-
-	mag->m = q2 + 1;
-	mag->s = p - 64;
-}
-
-/*
- * Multiplier and shift for a signed division by the constant d, with
- * 2 <= |d| < 2^63: q = mulhs(n, m), q += n if d > 0 and m < 0, q -= n
- * if d < 0 and m > 0, q >>= s (arithmetic), n / d == q + (q >>> 63).
- * Hacker's Delight, 2nd ed., figure 10-1.
- */
-static void bpf_magic_sdiv(s64 d, struct bpf_div_magic *mag)
-{
-	u64 ad = d < 0 ? -(u64)d : (u64)d;
-	u64 t, anc, delta, q1, r1, q2, r2;
-	int p;
-
-	t = (1ULL << 63) + (d < 0);
-	anc = t - 1 - t % ad;			/* |nc| */
-	p = 63;
-	q1 = (1ULL << 63) / anc;		/* 2^p / |nc| */
-	r1 = (1ULL << 63) - q1 * anc;		/* 2^p mod |nc| */
-	q2 = (1ULL << 63) / ad;			/* 2^p / |d| */
-	r2 = (1ULL << 63) - q2 * ad;		/* 2^p mod |d| */
-	do {
-		p++;
-		q1 = 2 * q1;
-		r1 = 2 * r1;
-		if (r1 >= anc) {
-			q1++;
-			r1 -= anc;
-		}
-		q2 = 2 * q2;
-		r2 = 2 * r2;
-		if (r2 >= ad) {
-			q2++;
-			r2 -= ad;
-		}
-		delta = ad - r2;
-	} while (q1 < delta || (q1 == delta && r1 == 0));
-
-	mag->m = q2 + 1;
-	if (d < 0)
-		mag->m = -mag->m;
-	mag->s = p - 64;
-	mag->add = false;
-}
-
-/*
- * Divide dst_reg by the constant in insn->imm of a 64-bit division through
- * a multiplication with the magic number from bpf_magic_udiv() or
- * bpf_magic_sdiv(). The dividend goes through rax and the multiplier
- * through r11, the caller saves rax and rdx unless they are dst_reg, and
- * r10 is scratch. Returns false for the divisors left to div/idiv.
- */
-static bool emit_div_const(u8 **pprog, const struct bpf_insn *insn, u32 dst_reg)
-{
-	bool is_mod = BPF_OP(insn->code) == BPF_MOD;
-	bool is_signed = insn->off == 1;
-	u32 n_reg = dst_reg, q_reg;
-	s32 imm32 = insn->imm;
-	struct bpf_div_magic mag;
-	u8 *prog = *pprog;
-	int corr = 0, pre = 0, s;
-
-	if (is_signed) {
-		/* |d| >= 2, the verifier already rewrote d == -1 */
-		if (imm32 >= -1 && imm32 <= 1)
-			return false;
-		bpf_magic_sdiv(imm32, &mag);
-		/* q += n for d > 0 and m < 0, q -= n for d < 0 and m > 0 */
-		if (imm32 > 0 && (s64)mag.m < 0)
-			corr = 1;
-		else if (imm32 < 0 && (s64)mag.m > 0)
-			corr = -1;
-	} else {
-		/* d >= 2, a negative imm32 is a divisor above 2^63 */
-		if (imm32 < 2)
-			return false;
-		bpf_magic_udiv(imm32, 0, &mag);
-		/*
-		 * Shift the dividend by the trailing zeros of an even divisor
-		 * first, the magic number of the odd part then fits without
-		 * the add sequence.
-		 */
-		if (mag.add && !(imm32 & 1)) {
-			pre = __ffs(imm32) & 31;
-			bpf_magic_udiv(imm32 >> pre, pre, &mag);
-			if (mag.add)
-				return false;
-		}
-	}
-	s = mag.s;
-	/*
-	 * The shift is at most 63, or 64 with the add sequence which shifts
-	 * by s - 1 and needs s >= 1. Never hit for d >= 2, kept as a guard
-	 * against an unencodable count.
-	 */
-	if (s > 64 - !mag.add || (mag.add && !s))
-		return false;
-
-	/* Keep the dividend when the multiplication clobbers it */
-	if ((is_mod || mag.add || corr) &&
-	    (dst_reg == BPF_REG_0 || dst_reg == BPF_REG_3)) {
-		emit_mov_reg(&prog, true, BPF_REG_AX, dst_reg);
-		n_reg = BPF_REG_AX;
-	}
-
-	/* mov rax, dst_reg; shr rax, pre; mov r11, m; mul r11 or imul r11 */
-	if (dst_reg != BPF_REG_0)
-		emit_mov_reg(&prog, true, BPF_REG_0, dst_reg);
-	if (pre)
-		emit_shift_imm(&prog, BPF_RSH, BPF_REG_0, pre, true);
-	emit_mov_imm64(&prog, AUX_REG, mag.m >> 32, (u32)mag.m);
-	EMIT3(0x49, 0xF7, is_signed ? 0xEB : 0xE3);
-	if (is_signed) {
-		/* add rdx, n_reg or sub rdx, n_reg */
-		if (corr)
-			emit_alu_reg(&prog, corr > 0 ? BPF_ADD : BPF_SUB,
-				     BPF_REG_3, n_reg, true);
-		/* sar rdx, s */
-		if (s)
-			emit_shift_imm(&prog, BPF_ARSH, BPF_REG_3, s, true);
-		/* mov rax, rdx; shr rax, 63; add rdx, rax */
-		emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_3);
-		emit_shift_imm(&prog, BPF_RSH, BPF_REG_0, 63, true);
-		emit_alu_reg(&prog, BPF_ADD, BPF_REG_3, BPF_REG_0, true);
-		q_reg = BPF_REG_3;
-	} else if (!mag.add) {
-		/* shr rdx, s */
-		if (s)
-			emit_shift_imm(&prog, BPF_RSH, BPF_REG_3, s, true);
-		q_reg = BPF_REG_3;
-	} else {
-		/* mov rax, n_reg; sub rax, rdx; shr rax, 1 */
-		emit_mov_reg(&prog, true, BPF_REG_0, n_reg);
-		emit_alu_reg(&prog, BPF_SUB, BPF_REG_0, BPF_REG_3, true);
-		emit_shift_imm(&prog, BPF_RSH, BPF_REG_0, 1, true);
-		/* add rax, rdx; shr rax, s - 1 */
-		emit_alu_reg(&prog, BPF_ADD, BPF_REG_0, BPF_REG_3, true);
-		if (s > 1)
-			emit_shift_imm(&prog, BPF_RSH, BPF_REG_0, s - 1, true);
-		q_reg = BPF_REG_0;
-	}
-
-	if (is_mod) {
-		/* imul q_reg, q_reg, imm32 */
-		maybe_emit_mod(&prog, q_reg, q_reg, true);
-		if (is_imm8(imm32))
-			EMIT3(0x6B, add_2reg(0xC0, q_reg, q_reg), imm32);
-		else
-			EMIT2_off32(0x69, add_2reg(0xC0, q_reg, q_reg), imm32);
-		/* sub n_reg, q_reg */
-		emit_alu_reg(&prog, BPF_SUB, n_reg, q_reg, true);
-		q_reg = n_reg;
-	}
-	if (q_reg != dst_reg)
-		emit_mov_reg(&prog, true, dst_reg, q_reg);
-
-	*pprog = prog;
-	return true;
-}
-
 static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
 {
 	u8 *prog = *pprog;
@@ -2901,11 +2689,6 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			if (dst_reg != BPF_REG_3)
 				EMIT1(0x52); /* push rdx */
 
-			/* LLVM strength-reduces the 32-bit ones itself */
-			if (is64 && BPF_SRC(insn->code) == BPF_K &&
-			    emit_div_const(&prog, insn, dst_reg))
-				goto div_done;
-
 			if (BPF_SRC(insn->code) == BPF_X) {
 				if (src_reg == BPF_REG_0 ||
 				    src_reg == BPF_REG_3) {
@@ -2952,7 +2735,7 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 				 dst_reg != BPF_REG_0)
 				/* mov dst_reg, rax */
 				emit_mov_reg(&prog, is64, dst_reg, BPF_REG_0);
-div_done:
+
 			if (dst_reg != BPF_REG_3)
 				EMIT1(0x5A); /* pop rdx */
 			if (dst_reg != BPF_REG_0)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 108b2aa924a9..1d33a78d9373 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -2402,6 +2402,191 @@ static int may_goto_off(struct bpf_verifier_env *env, const struct bpf_insn *ins
 	return off;
 }
 
+#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 */
+};
+
+/*
+ * m and s with n / d == mulhu(n, m) >> s for 2 <= d < 2^64 and n below
+ * 2^(64 - lz), or (((n - t) >> 1) + t) >> (s - 1) with t = mulhu(n, m) when m
+ * needs 65 bits. 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;
+}
+
+/*
+ * m and s with n / d == q + (q >> 63), q = (mulhs(n, m) +- n) s>> s, for
+ * 2 <= |d| < 2^63, adding n for d > 0 and m < 0, subtracting it for d < 0 and
+ * m > 0. 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;
+}
+
+/*
+ * 64-bit dst /= imm and dst %= imm as a uhmul or shmul by the magic number
+ * with AX as scratch, into buf. Returns the count, or 0 to keep the division,
+ * as for smod and for umod by a divisor that needs the add sequence.
+ */
+static int div_by_const(const struct bpf_insn *insn, struct bpf_insn *buf)
+{
+	bool is_mod = BPF_OP(insn->code) == BPF_MOD;
+	bool is_signed = insn->off == 1;
+	u8 dst = insn->dst_reg, ax = BPF_REG_AX;
+	struct bpf_insn *p = buf;
+	struct bpf_div_magic mag;
+	s32 d = insn->imm;
+	int pre = 0;
+
+	if (is_signed) {
+		/* |d| >= 2, d == -1 is gone already */
+		if (is_mod || (d >= -1 && d <= 1))
+			return 0;
+		bpf_magic_sdiv(d, &mag);
+	} else {
+		/* d >= 2, a negative imm is a divisor above 2^63 */
+		if (d < 2)
+			return 0;
+		bpf_magic_udiv(d, 0, &mag);
+		if (mag.add && is_mod)
+			return 0;
+		/*
+		 * 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 && !(d & 1)) {
+			pre = __ffs(d) & 31;
+			bpf_magic_udiv(d >> pre, pre, &mag);
+			if (mag.add)
+				return 0;
+		}
+	}
+	/* The add sequence shifts by s - 1. Never hit for d >= 2. */
+	if (mag.s > 64 - !mag.add || (mag.add && !mag.s))
+		return 0;
+
+	if (pre)
+		*p++ = BPF_ALU64_IMM(BPF_RSH, dst, pre);
+	/* ax = m ll */
+	*p++ = BPF_RAW_INSN(BPF_LD | BPF_DW | BPF_IMM, ax, 0, 0, (u32)mag.m);
+	*p++ = BPF_RAW_INSN(0, 0, 0, 0, mag.m >> 32);
+	if (is_signed) {
+		/* ax = (shmul(dst, m) +- dst) s>> s; dst = ax + (ax >> 63) */
+		*p++ = BPF_ALU64_REG_OFF(BPF_MUL, ax, dst, BPF_SHMUL);
+		if (d > 0 && (s64)mag.m < 0)
+			*p++ = BPF_ALU64_REG(BPF_ADD, ax, dst);
+		else if (d < 0 && (s64)mag.m > 0)
+			*p++ = BPF_ALU64_REG(BPF_SUB, ax, dst);
+		if (mag.s)
+			*p++ = BPF_ALU64_IMM(BPF_ARSH, ax, mag.s);
+		*p++ = BPF_MOV64_REG(dst, ax);
+		*p++ = BPF_ALU64_IMM(BPF_RSH, dst, 63);
+		*p++ = BPF_ALU64_REG(BPF_ADD, dst, ax);
+	} else if (is_mod) {
+		/* dst -= (uhmul(dst, m) >> s) * d */
+		*p++ = BPF_ALU64_REG_OFF(BPF_MUL, ax, dst, BPF_UHMUL);
+		if (mag.s)
+			*p++ = BPF_ALU64_IMM(BPF_RSH, ax, mag.s);
+		*p++ = BPF_ALU64_IMM(BPF_MUL, ax, d);
+		*p++ = BPF_ALU64_REG(BPF_SUB, dst, ax);
+	} else if (mag.add) {
+		/* ax = uhmul(dst, m); dst = (((dst - ax) >> 1) + ax) >> (s - 1) */
+		*p++ = BPF_ALU64_REG_OFF(BPF_MUL, ax, dst, BPF_UHMUL);
+		*p++ = BPF_ALU64_REG(BPF_SUB, dst, ax);
+		*p++ = BPF_ALU64_IMM(BPF_RSH, dst, 1);
+		*p++ = BPF_ALU64_REG(BPF_ADD, dst, ax);
+		if (mag.s > 1)
+			*p++ = BPF_ALU64_IMM(BPF_RSH, dst, mag.s - 1);
+	} else {
+		/* dst = uhmul(dst, m) >> s */
+		*p++ = BPF_ALU64_REG_OFF(BPF_MUL, dst, ax, BPF_UHMUL);
+		if (mag.s)
+			*p++ = BPF_ALU64_IMM(BPF_RSH, dst, mag.s);
+	}
+	return p - buf;
+}
+#else
+static int div_by_const(const struct bpf_insn *insn, struct bpf_insn *buf)
+{
+	return 0;
+}
+#endif
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */
@@ -2481,6 +2666,20 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
+		/* Divide by a constant via uhmul or shmul, LLVM does the 32-bit ones */
+		if ((insn->code == (BPF_ALU64 | BPF_MOD | BPF_K) ||
+		     insn->code == (BPF_ALU64 | BPF_DIV | BPF_K)) &&
+		    prog->jit_requested && !prog->blinding_requested &&
+		    !bpf_prog_is_offloaded(prog->aux) && bpf_jit_supports_hmul()) {
+			cnt = div_by_const(insn, insn_buf);
+			if (cnt) {
+				insn = bpf_patch_list_add(env, i, insn_buf, cnt);
+				if (IS_ERR(insn))
+					return PTR_ERR(insn);
+				goto next_insn;
+			}
+		}
+
 		/* Make divide-by-zero and divide-by-minus-one exceptions impossible. */
 		if (insn->code == (BPF_ALU64 | BPF_MOD | BPF_X) ||
 		    insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
diff --git a/tools/testing/selftests/bpf/prog_tests/jit_insns.c b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
index 52bffe27199b..5fd1c856ded7 100644
--- a/tools/testing/selftests/bpf/prog_tests/jit_insns.c
+++ b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
@@ -582,14 +582,10 @@ static void test_alu_imm_regs(void)
 }
 
 /*
- * Division and modulo by constants for every width, signedness and
- * destination register with a set of divisors and dividends around the
- * multiple boundaries and the extremes of each range. This covers a JIT
- * replacing the division with a multiplication by a magic number in all
- * of its forms: magic numbers needing the extra add step, zero shifts,
- * both signed corrections, and the divisors like 1, -1 and the ones
- * above 2^63 that are still emitted as a real division. The dividends
- * of the 32-bit operations carry garbage in the upper 32 bits.
+ * Division and modulo by constants for every width, signedness and register,
+ * with dividends at the multiple boundaries and the extremes: every form of
+ * the verifier's multiplication by the magic number and the divisors it keeps.
+ * The dividends of the 32-bit operations carry garbage in the upper half.
  */
 static const __s32 unsigned_divisors[] = {
 	2, 3, 7, 10, 25, 641, 1000, 4096, 65536, 1000000007, 0x7fffffff,
@@ -2486,15 +2482,9 @@ static void test_acq_rel(void)
 }
 
 /*
- * A jump with the maximal offset over instructions which expand to several
- * native ones, so that the native offset outgrows the field of a short
- * branch and takes the JITs through their branch conversion. The region
- * must not grow in the verifier, or the jump could not reach over it any
- * more: the divisions are by constants, as a division by a register gets
- * a zero check in front, and the region sticks to one width, as a 32-bit
- * result read by a 64-bit instruction gets a zero extension on the JITs
- * which need one. The region is the not taken path and ends with a result
- * different from the taken one, so a jump landing inside it fails the run.
+ * A jump with the maximal offset over insns that expand natively, through the
+ * JITs' long branch forms. The region must not grow in the verifier: one width
+ * and divisions by constants it keeps. A jump landing inside it fails the run.
  */
 static void max_jmp(bool alu32, bool taken)
 {
@@ -2524,7 +2514,7 @@ static void max_jmp(bool alu32, bool taken)
 
 		if (op == BPF_DIV || op == BPF_MOD)
 			insns[i++] = alu32 ? BPF_ALU32_IMM(op, BPF_REG_3, 7) :
-					     BPF_ALU64_IMM(op, BPF_REG_3, 7);
+					     BPF_ALU64_IMM(op, BPF_REG_3, -7);
 		else
 			insns[i++] = alu32 ? BPF_ALU32_REG(op, BPF_REG_3, BPF_REG_2) :
 					     BPF_ALU64_REG(op, BPF_REG_3, BPF_REG_2);
-- 
2.43.0

[PATCH bpf-next v3 12/24] bpf, arm64: Consolidate the load and store emission into a helper

[Daniel Borkmann]

The BPF_LDX, BPF_ST and BPF_STX cases each repeat the frame pointer
adjustment and the switch over the access size. Move that into a new
emit_ldst() helper, and remove the A64_LDR*() and A64_STR*() macros
that lose their last user. The emitted code is unchanged.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h      |  17 ---
 arch/arm64/net/bpf_jit_comp.c | 230 +++++++++++-----------------------
 2 files changed, 73 insertions(+), 174 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 3dcc2d2cf035..882404b884e1 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -62,16 +62,7 @@
 		AARCH64_INSN_LDST_##type##_REG_OFFSET)
 #define A64_LS_REG(Rt, Rn, Rm, size, type) \
 	A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type)
-#define A64_STRB(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 8, STORE)
-#define A64_LDRB(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 8, LOAD)
-#define A64_LDRSB(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 8, SIGNED_LOAD)
-#define A64_STRH(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 16, STORE)
-#define A64_LDRH(Wt, Xn, Xm)  A64_LS_REG(Wt, Xn, Xm, 16, LOAD)
-#define A64_LDRSH(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 16, SIGNED_LOAD)
-#define A64_STR32(Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, STORE)
 #define A64_LDR32(Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, LOAD)
-#define A64_LDRSW(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 32, SIGNED_LOAD)
-#define A64_STR64(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, STORE)
 #define A64_LDR64(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, LOAD)
 
 /* Load/store register (immediate offset) */
@@ -79,15 +70,7 @@
 	aarch64_insn_gen_load_store_imm(Rt, Rn, imm, \
 		AARCH64_INSN_SIZE_##size, \
 		AARCH64_INSN_LDST_##type##_IMM_OFFSET)
-#define A64_STRBI(Wt, Xn, imm)  A64_LS_IMM(Wt, Xn, imm, 8, STORE)
-#define A64_LDRBI(Wt, Xn, imm)  A64_LS_IMM(Wt, Xn, imm, 8, LOAD)
-#define A64_LDRSBI(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 8, SIGNED_LOAD)
-#define A64_STRHI(Wt, Xn, imm)  A64_LS_IMM(Wt, Xn, imm, 16, STORE)
-#define A64_LDRHI(Wt, Xn, imm)  A64_LS_IMM(Wt, Xn, imm, 16, LOAD)
-#define A64_LDRSHI(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 16, SIGNED_LOAD)
-#define A64_STR32I(Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 32, STORE)
 #define A64_LDR32I(Wt, Xn, imm) A64_LS_IMM(Wt, Xn, imm, 32, LOAD)
-#define A64_LDRSWI(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 32, SIGNED_LOAD)
 #define A64_STR64I(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, STORE)
 #define A64_LDR64I(Xt, Xn, imm) A64_LS_IMM(Xt, Xn, imm, 64, LOAD)
 
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 3403f4327de8..05ba44f47313 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -365,6 +365,73 @@ 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, from the (private) stack
+ * pointer with the frame size added for the frame pointer, which the register
+ * offset form keeps.
+ */
+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,
+						     0, size, a64_ldst_type(code, true)), ctx);
+	}
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -1468,9 +1535,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;
@@ -1479,11 +1544,8 @@ 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);
@@ -1976,15 +2038,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;
-		}
+		off_adj = off;
 		if (BPF_MODE(insn->code) == BPF_PROBE_MEM ||
 		    BPF_MODE(insn->code) == BPF_PROBE_MEMSX) {
 			/*
@@ -1995,69 +2049,15 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			 */
 			if (off) {
 				emit_a64_add_i(1, tmp2, src, tmp, off, ctx);
-				src_adj = tmp2;
+				src = tmp2;
 				off_adj = 0;
 			}
-			emit(A64_TST_I(1, src_adj, BIT(55)), ctx);
+			emit(A64_TST_I(1, src, BIT(55)), ctx);
 			emit(A64_B_(A64_COND_NE, 3), ctx);
 			emit(A64_MOVZ(1, dst, 0, 0), ctx);
 			emit(A64_B(2), ctx);
 		}
-		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_adj, tmp, ctx);
 
 		ret = add_exception_handler(insn, ctx, dst);
 		if (ret)
@@ -2092,51 +2092,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)
@@ -2161,49 +2119,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 v3 13/24] 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, needed a mov of the offset and the
register offset form. LDUR and STUR take a signed 9-bit byte offset at
the same latency. Use them for offsets from -256 to 255, which covers,
for example, packet fields behind the Ethernet header.

Before/after for r0 = *(u32 *)(r1 + 26) and r0 = *(u64 *)(r1 - 16):

  d280034a  mov x10, #0x1a
  b86a6808  ldr w8, [x0, x10]
  b841a008  ldur w8, [x0, #26]

  928001ea  mov x10, #0xfffffffffffffff0
  f86a6808  ldr x8, [x0, x10]
  f85f0008  ldur x8, [x0, #-16]

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 05ba44f47313..e20c48028f71 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -365,6 +365,12 @@ static bool is_lsi_offset(int offset, int scale)
 	return true;
 }
 
+/* The unscaled forms take a signed 9-bit byte offset instead */
+static bool is_lsu_offset(int offset)
+{
+	return offset >= -SZ_256 && offset < SZ_256;
+}
+
 /* The A64 size of a BPF load or store, and the scale of its offset */
 static enum aarch64_insn_size_type a64_ldst_size(const u8 code, int *scale)
 {
@@ -384,18 +390,36 @@ static enum aarch64_insn_size_type a64_ldst_size(const u8 code, int *scale)
 	}
 }
 
-/* The A64 type of a BPF load or store, in the immediate or register offset form */
-static enum aarch64_insn_ldst_type a64_ldst_type(const u8 code, bool reg_offset)
-{
+/* The forms of a load or store: scaled unsigned immediate, unscaled, register offset */
+enum a64_ldst_form { A64_LDST_IMM, A64_LDST_UNSCALED, A64_LDST_REG };
+
+/* The A64 type of a BPF load or store in the given form */
+static enum aarch64_insn_ldst_type a64_ldst_type(const u8 code, enum a64_ldst_form form)
+{
+	static const enum aarch64_insn_ldst_type types[][3] = {
+		[A64_LDST_IMM] = {
+			AARCH64_INSN_LDST_LOAD_IMM_OFFSET,
+			AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET,
+			AARCH64_INSN_LDST_STORE_IMM_OFFSET,
+		},
+		[A64_LDST_UNSCALED] = {
+			AARCH64_INSN_LDST_LOAD_UNSCALED_IMM_OFFSET,
+			AARCH64_INSN_LDST_SIGNED_LOAD_UNSCALED_IMM_OFFSET,
+			AARCH64_INSN_LDST_STORE_UNSCALED_IMM_OFFSET,
+		},
+		[A64_LDST_REG] = {
+			AARCH64_INSN_LDST_LOAD_REG_OFFSET,
+			AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET,
+			AARCH64_INSN_LDST_STORE_REG_OFFSET,
+		},
+	};
+
 	if (BPF_CLASS(code) != BPF_LDX)
-		return reg_offset ? AARCH64_INSN_LDST_STORE_REG_OFFSET :
-				    AARCH64_INSN_LDST_STORE_IMM_OFFSET;
+		return types[form][2];
 	if (BPF_MODE(code) == BPF_MEMSX || BPF_MODE(code) == BPF_PROBE_MEMSX ||
 	    BPF_MODE(code) == BPF_PROBE_MEM32SX)
-		return reg_offset ? AARCH64_INSN_LDST_SIGNED_LOAD_REG_OFFSET :
-				    AARCH64_INSN_LDST_SIGNED_LOAD_IMM_OFFSET;
-	return reg_offset ? AARCH64_INSN_LDST_LOAD_REG_OFFSET :
-			    AARCH64_INSN_LDST_LOAD_IMM_OFFSET;
+		return types[form][1];
+	return types[form][0];
 }
 
 /*
@@ -407,6 +431,7 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off,
 		      const u8 tmp, struct jit_ctx *ctx)
 {
 	enum aarch64_insn_size_type size;
+	enum aarch64_insn_ldst_type type;
 	s32 off_adj = off;
 	u8 rn_adj = rn;
 	int scale;
@@ -423,12 +448,16 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off,
 	}
 
 	if (is_lsi_offset(off_adj, scale)) {
-		emit(aarch64_insn_gen_load_store_imm(rt, rn_adj, off_adj, size,
-						     a64_ldst_type(code, false)), ctx);
+		type = a64_ldst_type(code, A64_LDST_IMM);
+		emit(aarch64_insn_gen_load_store_imm(rt, rn_adj, off_adj, size, type), ctx);
+	} else if (is_lsu_offset(off_adj)) {
+		type = a64_ldst_type(code, A64_LDST_UNSCALED);
+		emit(aarch64_insn_gen_load_store_unscaled(rt, rn_adj, off_adj, size, type), ctx);
 	} else {
+		type = a64_ldst_type(code, A64_LDST_REG);
 		emit_a64_mov_i(1, tmp, off, ctx);
 		emit(aarch64_insn_gen_load_store_reg(rt, rn, tmp, AARCH64_INSN_EXTEND_UXTX,
-						     0, size, a64_ldst_type(code, true)), ctx);
+						     0, size, type), ctx);
 	}
 }
 
-- 
2.43.0

[PATCH bpf-next v3 14/24] bpf, arm64: Store zero immediates from the zero register

[Daniel Borkmann]

A store of an immediate first moves it into a temporary, even when it
is zero. Store a zero from xzr instead, which saves the mov. Zero
stores are common: with cpu v4, LLVM emits runs of them to clear the
stack slots of the structs and arrays that BPF programs pass to
helpers.

Before/after for *(u64 *)(r10 - 8) = 0 with 16 bytes of stack:

  d280000a  mov x10, #0x0
  f90007ea  str x10, [sp, #8]
  f90007ff  str xzr, [sp, #8]

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 e20c48028f71..083d8c383f5b 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -2121,9 +2121,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 v3 15/24] bpf, arm64: Zero extend the arena offset in register offset accesses

[Daniel Borkmann]

An arena access added the 32-bit arena offset register to the arena
base with a 64-bit add. That relies on the verifier to keep the upper
32 bits zero, and any slip there would let the access escape the 4GB
arena.

Use the register offset form with UXTW instead. It zero extends the
offset as part of the access, which keeps the access within the arena
and its guard pages. Without an immediate offset, this saves the add.
With one, the add moves to the base, and an offset that does not fit
the add immediate needs an extra mov.

The atomics and load-acquire/store-release have no register offset
form. For them, add the arena offset to the base with UXTW instead.

Update the arm64 expectations of the Arena LDSX Disasm test in
verifier_ldsx to the new form.

Before/after for r0 = *(u64 *)(r1 + 0) and r0 = *(u64 *)(r1 + 8) in the
arena:

  8b1c000b  add x11, x0, x28
  f9400168  ldr x8, [x11]
  f8604b88  ldr x8, [x28, w0, uxtw]

  8b1c000b  add x11, x0, x28
  f9400568  ldr x8, [x11, #8]
  9100238b  add x11, x28, #0x8
  f8604968  ldr x8, [x11, w0, uxtw]

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

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 083d8c383f5b..fb56b439ee20 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -461,6 +461,26 @@ static void emit_ldst(const u8 code, const u8 rt, const u8 rn, const s32 off,
 	}
 }
 
+/*
+ * Load or store at the arena base, plus off added into tmp_addr, plus reg zero
+ * extended from 32 bits in the access, which keeps it in the arena and its
+ * guard whatever the upper bits of reg hold.
+ */
+static void emit_arena_ldst(const u8 code, const u8 rt, const u8 reg, const s32 off,
+			    const u8 tmp_addr, const u8 tmp, struct jit_ctx *ctx)
+{
+	u8 base = bpf2a64[ARENA_VM_START];
+	int scale;
+
+	if (off) {
+		emit_a64_add_i(1, tmp_addr, base, tmp, off, ctx);
+		base = tmp_addr;
+	}
+	emit(aarch64_insn_gen_load_store_reg(rt, base, reg, AARCH64_INSN_EXTEND_UXTW,
+					     0, a64_ldst_size(code, &scale),
+					     a64_ldst_type(code, A64_LDST_REG)), ctx);
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -846,6 +866,7 @@ static int emit_atomic_ld_st(const struct bpf_insn *insn, struct jit_ctx *ctx)
 	const u8 dst = bpf2a64[insn->dst_reg];
 	const u8 src = bpf2a64[insn->src_reg];
 	const u8 tmp = bpf2a64[TMP_REG_1];
+	const u8 tmp2 = bpf2a64[TMP_REG_2];
 	u8 reg;
 
 	switch (imm) {
@@ -860,12 +881,21 @@ static int emit_atomic_ld_st(const struct bpf_insn *insn, struct jit_ctx *ctx)
 		return -EINVAL;
 	}
 
-	if (off) {
-		emit_a64_add_i(1, tmp, reg, tmp, off, ctx);
-		reg = tmp;
-	}
+	/*
+	 * The arena base with the offset first and the arena offset zero
+	 * extended onto it, see emit_arena_ldst()
+	 */
 	if (arena) {
-		emit(A64_ADD(1, tmp, reg, arena_vm_base), ctx);
+		u8 base = arena_vm_base;
+
+		if (off) {
+			emit_a64_add_i(1, tmp, base, tmp, off, ctx);
+			base = tmp;
+		}
+		emit(A64_ADD_UXTW(tmp2, base, reg), ctx);
+		reg = tmp2;
+	} else if (off) {
+		emit_a64_add_i(1, tmp, reg, tmp, off, ctx);
 		reg = tmp;
 	}
 
@@ -919,17 +949,27 @@ static int emit_lse_atomic(const struct bpf_insn *insn, struct jit_ctx *ctx)
 	const u8 src = bpf2a64[insn->src_reg];
 	const u8 tmp = bpf2a64[TMP_REG_1];
 	const u8 tmp2 = bpf2a64[TMP_REG_2];
+	const u8 tmp3 = bpf2a64[TMP_REG_3];
 	const bool isdw = BPF_SIZE(code) == BPF_DW;
 	const bool arena = BPF_MODE(code) == BPF_PROBE_ATOMIC;
 	const s16 off = insn->off;
 	u8 reg = dst;
 
-	if (off) {
-		emit_a64_add_i(1, tmp, reg, tmp, off, ctx);
-		reg = tmp;
-	}
+	/*
+	 * The arena base with the offset first and the arena offset zero
+	 * extended onto it, see emit_arena_ldst()
+	 */
 	if (arena) {
-		emit(A64_ADD(1, tmp, reg, arena_vm_base), ctx);
+		u8 base = arena_vm_base;
+
+		if (off) {
+			emit_a64_add_i(1, tmp, base, tmp, off, ctx);
+			base = tmp;
+		}
+		emit(A64_ADD_UXTW(tmp3, base, reg), ctx);
+		reg = tmp3;
+	} else if (off) {
+		emit_a64_add_i(1, tmp, reg, tmp, off, ctx);
 		reg = tmp;
 	}
 
@@ -1564,7 +1604,6 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_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;
@@ -2062,11 +2101,6 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	case BPF_LDX | BPF_PROBE_MEM32SX | BPF_B:
 	case BPF_LDX | BPF_PROBE_MEM32SX | BPF_H:
 	case BPF_LDX | BPF_PROBE_MEM32SX | BPF_W:
-		if (BPF_MODE(insn->code) == BPF_PROBE_MEM32 ||
-		    BPF_MODE(insn->code) == BPF_PROBE_MEM32SX) {
-			emit(A64_ADD(1, tmp2, src, arena_vm_base), ctx);
-			src = tmp2;
-		}
 		off_adj = off;
 		if (BPF_MODE(insn->code) == BPF_PROBE_MEM ||
 		    BPF_MODE(insn->code) == BPF_PROBE_MEMSX) {
@@ -2086,7 +2120,11 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 			emit(A64_MOVZ(1, dst, 0, 0), ctx);
 			emit(A64_B(2), ctx);
 		}
-		emit_ldst(code, dst, src, off_adj, tmp, ctx);
+		if (BPF_MODE(insn->code) == BPF_PROBE_MEM32 ||
+		    BPF_MODE(insn->code) == BPF_PROBE_MEM32SX)
+			emit_arena_ldst(code, dst, src, off, tmp2, tmp, ctx);
+		else
+			emit_ldst(code, dst, src, off_adj, tmp, ctx);
 
 		ret = add_exception_handler(insn, ctx, dst);
 		if (ret)
@@ -2117,14 +2155,13 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_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)
@@ -2145,11 +2182,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 8084a428d9e2..232082428cb9 100644
--- a/tools/testing/selftests/bpf/progs/verifier_ldsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
@@ -274,18 +274,18 @@ __jited("movslq	0x10(%rdi,%r12), %r15")
 __jited("movswq	0x18(%rdi,%r12), %r15")
 __jited("movsbq	0x20(%rdi,%r12), %r15")
 __arch_arm64
-__jited("add	x11, x8, x28")
-__jited("ldrsw	x21, [x11, #0x10]")
-__jited("add	x11, x8, x28")
-__jited("ldrsh	x21, [x11, #0x18]")
-__jited("add	x11, x8, x28")
-__jited("ldrsb	x21, [x11, #0x20]")
-__jited("add	x11, x0, x28")
-__jited("ldrsw	x22, [x11, #0x10]")
-__jited("add	x11, x0, x28")
-__jited("ldrsh	x22, [x11, #0x18]")
-__jited("add	x11, x0, x28")
-__jited("ldrsb	x22, [x11, #0x20]")
+__jited("add	x11, x28, #0x10")
+__jited("ldrsw	x21, [x11, w8, uxtw]")
+__jited("add	x11, x28, #0x18")
+__jited("ldrsh	x21, [x11, w8, uxtw]")
+__jited("add	x11, x28, #0x20")
+__jited("ldrsb	x21, [x11, w8, uxtw]")
+__jited("add	x11, x28, #0x10")
+__jited("ldrsw	x22, [x11, w0, uxtw]")
+__jited("add	x11, x28, #0x18")
+__jited("ldrsh	x22, [x11, w0, uxtw]")
+__jited("add	x11, x28, #0x20")
+__jited("ldrsb	x22, [x11, w0, uxtw]")
 __arch_riscv64
 __jited("add	t2, t6, s7")
 __jited("lw	s3, 0x10(t2)")
-- 
2.43.0

[PATCH bpf-next v3 16/24] bpf, arm64: Adjust compares with unencodable immediates by one

[Daniel Borkmann]

cmp and cmn take a 12-bit immediate, optionally shifted left by 12.
LLVM turns x <= C into x < C + 1 and x >= C into x > C - 1, so a
compare against a power of two reaches the JIT as one against a power
of two plus one, or against a mask. Those often do not encode and
needed a mov.

When the immediate does not encode but its neighbour C - 1 or C + 1
does, compare against the neighbour and adjust the condition. This
covers <, <=, > and >=, both signed and unsigned.

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

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

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

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

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index fb56b439ee20..5a88740d9d0c 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -481,6 +481,73 @@ static void emit_arena_ldst(const u8 code, const u8 rt, const u8 reg, const s32
 					     a64_ldst_type(code, A64_LDST_REG)), ctx);
 }
 
+/*
+ * Compare against C - 1 or C + 1 with the adjusted condition when C does not
+ * encode, for the masks and powers of two plus one that LLVM's x >= C to
+ * x > C - 1 and x <= C to x < C + 1 bring here.
+ */
+static bool adjust_cmp_imm(u8 *op, s32 *imm)
+{
+	s64 c = *imm;
+	u8 new_op;
+
+	switch (*op) {
+	case BPF_JLT:
+	case BPF_JGE:
+		if (!c)
+			return false;
+		fallthrough;
+	case BPF_JSLT:
+	case BPF_JSGE:
+		c--;
+		break;
+	case BPF_JGT:
+	case BPF_JLE:
+		if (c == -1)
+			return false;
+		fallthrough;
+	case BPF_JSGT:
+	case BPF_JSLE:
+		c++;
+		break;
+	default:
+		return false;
+	}
+	/* Past a signed limit the neighbor does not fit the 32-bit immediate */
+	if (c != (s32)c || (!is_addsub_imm(c) && !is_addsub_imm(-(u32)c)))
+		return false;
+
+	switch (*op) {
+	case BPF_JLT:
+		new_op = BPF_JLE;
+		break;
+	case BPF_JGE:
+		new_op = BPF_JGT;
+		break;
+	case BPF_JSLT:
+		new_op = BPF_JSLE;
+		break;
+	case BPF_JSGE:
+		new_op = BPF_JSGT;
+		break;
+	case BPF_JGT:
+		new_op = BPF_JGE;
+		break;
+	case BPF_JLE:
+		new_op = BPF_JLT;
+		break;
+	case BPF_JSGT:
+		new_op = BPF_JSGE;
+		break;
+	default:
+		new_op = BPF_JSLT;
+		break;
+	}
+	*op = new_op;
+	*imm = c;
+	return true;
+}
+
 /* generated main prog prologue:
  *      bti c // if CONFIG_ARM64_BTI_KERNEL
  *      mov x9, lr
@@ -1609,6 +1676,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_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;
@@ -1886,7 +1955,7 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 emit_cond_jmp:
 		jmp_offset = bpf2a64_offset(i, off, ctx);
 		check_imm19(jmp_offset);
-		switch (BPF_OP(code)) {
+		switch (jmp_op) {
 		case BPF_JEQ:
 			jmp_cond = A64_COND_EQ;
 			break;
@@ -1948,12 +2017,14 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_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 v3 17/24] bpf, arm64: Materialize immediates with fewer instructions

[Daniel Borkmann]

A 32-bit immediate with a zero or all-ones low half often took two
moves where a single shifted movz or movn does. A bitmask immediate,
32 or 64 bits, took two or more moves where a single orr does.

A 64-bit immediate with a repeated 16-bit chunk now takes one orr of
that chunk replicated, if that is a bitmask immediate, plus a movk for
each other chunk. The verifier's magic numbers for dividing by 3, 5, 15
and 17 have that form.

Before/after for w1 = 0x10000, r1 = 0x7fffffff, r1 = 0xffffffff00000000 ll
and r1 = 0xcccccccccccccccd ll:

  52800000  mov w0, #0x0
  72a00020  movk w0, #0x1, lsl #16
  52a00020  mov w0, #0x10000

  d29fffe0  mov x0, #0xffff
  f2afffe0  movk x0, #0x7fff, lsl #16
  b2407be0  mov x0, #0x7fffffff

  d2ffffe0  mov x0, #0xffff000000000000
  f2dfffe0  movk x0, #0xffff, lsl #32
  b2607fe0  mov x0, #0xffffffff00000000

  d2f99980  mov x0, #0xcccc000000000000
  f2d99980  movk x0, #0xcccc, lsl #32
  f2b99980  movk x0, #0xcccc, lsl #16
  f29999a0  movk x0, #0xcccd
  b202e7e0  mov x0, #0xcccccccccccccccc
  f29999a0  movk x0, #0xcccd

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

diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 5a88740d9d0c..62d2f70cc412 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -125,24 +125,47 @@ static inline void emit_u32_data(const u32 data, struct jit_ctx *ctx)
 	ctx->idx++;
 }
 
+/*
+ * A 32-bit immediate, sign extended for the 64-bit variant: one movz, movn or
+ * orr where one encodes it, else a movz or movn and a movk.
+ */
 static inline void emit_a64_mov_i(const int is64, const int reg,
 				  const s32 val, struct jit_ctx *ctx)
 {
 	u16 hi = val >> 16;
 	u16 lo = val & 0xffff;
+	u32 insn;
+
+	if (hi == 0xffff) {
+		emit(A64_MOVN(is64, reg, (u16)~lo, 0), ctx);
+		return;
+	}
+	if (!hi) {
+		emit(A64_MOVZ(is64, reg, lo, 0), ctx);
+		return;
+	}
+	/* The 64-bit variant has the upper half set or clear with the sign */
+	if (!lo && (!is64 || !(hi & 0x8000))) {
+		emit(A64_MOVZ(is64, reg, hi, 16), ctx);
+		return;
+	}
+	if (lo == 0xffff && (!is64 || (hi & 0x8000))) {
+		emit(A64_MOVN(is64, reg, (u16)~hi, 16), ctx);
+		return;
+	}
+
+	insn = A64_ORR_I(is64, reg, A64_ZR, val);
+	if (insn != AARCH64_BREAK_FAULT) {
+		emit(insn, ctx);
+		return;
+	}
 
 	if (hi & 0x8000) {
-		if (hi == 0xffff) {
-			emit(A64_MOVN(is64, reg, (u16)~lo, 0), ctx);
-		} else {
-			emit(A64_MOVN(is64, reg, (u16)~hi, 16), ctx);
-			if (lo != 0xffff)
-				emit(A64_MOVK(is64, reg, lo, 0), ctx);
-		}
+		emit(A64_MOVN(is64, reg, (u16)~hi, 16), ctx);
+		emit(A64_MOVK(is64, reg, lo, 0), ctx);
 	} else {
 		emit(A64_MOVZ(is64, reg, lo, 0), ctx);
-		if (hi)
-			emit(A64_MOVK(is64, reg, hi, 16), ctx);
+		emit(A64_MOVK(is64, reg, hi, 16), ctx);
 	}
 }
 
@@ -170,10 +193,42 @@ static inline void emit_a64_mov_i64(const int reg, const u64 val,
 {
 	u64 nrm_tmp = val, rev_tmp = ~val;
 	bool inverse;
-	int shift;
+	u32 insn;
+	int shift, blocks;
 
 	if (!(nrm_tmp >> 32))
 		return emit_a64_mov_i(0, reg, (u32)val, ctx);
+	if ((s64)(s32)val == (s64)val)
+		return emit_a64_mov_i(1, reg, (s32)val, ctx);
+
+	/* A bitmask immediate in a single orr */
+	insn = A64_ORR_I(1, reg, A64_ZR, val);
+	if (insn != AARCH64_BREAK_FAULT)
+		return emit(insn, ctx);
+
+	/*
+	 * A 16-bit chunk occurring more than once whose replication is a
+	 * bitmask immediate comes from one orr, with a movk for each of
+	 * the other chunks, when that beats the moves of the chunks.
+	 */
+	blocks = min(i64_i16_blocks(nrm_tmp, true), i64_i16_blocks(nrm_tmp, false));
+	for (shift = 0; shift < 64; shift += 16) {
+		u16 chunk = val >> shift;
+		int i, n = 0;
+
+		for (i = 0; i < 64; i += 16)
+			n += (u16)(val >> i) == chunk;
+		if (n < 2 || 1 + 4 - n >= blocks)
+			continue;
+		insn = A64_ORR_I(1, reg, A64_ZR, chunk * 0x0001000100010001ULL);
+		if (insn == AARCH64_BREAK_FAULT)
+			continue;
+		emit(insn, ctx);
+		for (i = 0; i < 64; i += 16)
+			if ((u16)(val >> i) != chunk)
+				emit(A64_MOVK(1, reg, (u16)(val >> i), i), ctx);
+		return;
+	}
 
 	inverse = i64_i16_blocks(nrm_tmp, true) < i64_i16_blocks(nrm_tmp, false);
 	shift = max(round_down((inverse ? (fls64(rev_tmp) - 1) :
-- 
2.43.0

[PATCH bpf-next v3 18/24] bpf, arm64: Shorten the tail call sequence

[Daniel Borkmann]

The tail call sequence moved the offsets of max_entries, ptrs and
bpf_func, and the tail call limit, into a temporary first, although
they all fit the immediate forms. It also zero extended and shifted the
index in separate instructions before the load. Use the immediate forms
and a register offset load with UXTW #3 instead.

That saves six instructions per tail call. A64_LDR64() loses its last
user and is removed.

Before/after for the checks and the lookup of a tail call:

  5280088a  mov w10, #0x44
  b86a682a  ldr w10, [x1, x10]
  2a0203e2  mov w2, w2
  6b0a005f  cmp w2, w10
  54000282  b.hs ...
  5280042a  mov w10, #0x21
  f940034c  ldr x12, [x26]
  eb0a019f  cmp x12, x10
  54000202  b.hs ...
  9100058c  add x12, x12, #0x1
  5280440a  mov w10, #0x220
  8b0a002a  add x10, x1, x10
  d37df04b  lsl x11, x2, #3
  f86b694b  ldr x11, [x10, x11]
  b400014b  cbz x11, ...

  b940442a  ldr w10, [x1, #68]
  6b0a005f  cmp w2, w10
  54000202  b.hs ...
  f940034c  ldr x12, [x26]
  f100859f  cmp x12, #0x21
  540001a2  b.hs ...
  9100058c  add x12, x12, #0x1
  9108802a  add x10, x1, #0x220
  f862594b  ldr x11, [x10, w2, uxtw #3]
  b400012b  cbz x11, ...

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

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 882404b884e1..16c690c6cae9 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -63,7 +63,8 @@
 #define A64_LS_REG(Rt, Rn, Rm, size, type) \
 	A64_LS_REG_EXT(Rt, Rn, Rm, UXTX, 0, size, type)
 #define A64_LDR32(Wt, Xn, Xm) A64_LS_REG(Wt, Xn, Xm, 32, LOAD)
-#define A64_LDR64(Xt, Xn, Xm) A64_LS_REG(Xt, Xn, Xm, 64, LOAD)
+/* Xt = *(Xn + ((u32)Wm << 3)) */
+#define A64_LDR64_UXTW3(Xt, Xn, Wm) A64_LS_REG_EXT(Xt, Xn, Wm, UXTW, 3, 64, LOAD)
 
 /* Load/store register (immediate offset) */
 #define A64_LS_IMM(Rt, Rn, imm, size, type) \
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 62d2f70cc412..a79c401c5262 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -909,13 +909,20 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 	__le32 *branch2 = NULL;
 	__le32 *branch3 = NULL;
 
-	/* if (index >= array->map.max_entries)
+	/* The struct offsets fit the immediate forms, the count fits cmp */
+	BUILD_BUG_ON(offsetof(struct bpf_array, map.max_entries) % 4 ||
+		     offsetof(struct bpf_array, map.max_entries) > 0xfff * 4);
+	BUILD_BUG_ON(offsetof(struct bpf_array, ptrs) > 0xfff);
+	BUILD_BUG_ON(offsetof(struct bpf_prog, bpf_func) % 8 ||
+		     offsetof(struct bpf_prog, bpf_func) > 0xfff * 8);
+	BUILD_BUG_ON(MAX_TAIL_CALL_CNT > 0xfff);
+
+	/*
+	 * if ((u32)index >= array->map.max_entries)
 	 *     goto out;
 	 */
 	off = offsetof(struct bpf_array, map.max_entries);
-	emit_a64_mov_i64(tmp, off, ctx);
-	emit(A64_LDR32(tmp, r2, tmp), ctx);
-	emit(A64_MOV(0, r3, r3), ctx);
+	emit(A64_LDR32I(tmp, r2, off), ctx);
 	emit(A64_CMP(0, r3, tmp), ctx);
 	branch1 = ctx->image + ctx->idx;
 	emit(A64_NOP, ctx);
@@ -924,9 +931,8 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 	 * if ((*tail_call_cnt_ptr) >= MAX_TAIL_CALL_CNT)
 	 *     goto out;
 	 */
-	emit_a64_mov_i64(tmp, MAX_TAIL_CALL_CNT, ctx);
 	emit(A64_LDR64I(tcc, ptr, 0), ctx);
-	emit(A64_CMP(1, tcc, tmp), ctx);
+	emit(A64_CMP_I(1, tcc, MAX_TAIL_CALL_CNT), ctx);
 	branch2 = ctx->image + ctx->idx;
 	emit(A64_NOP, ctx);
 
@@ -938,10 +944,8 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 	 *     goto out;
 	 */
 	off = offsetof(struct bpf_array, ptrs);
-	emit_a64_mov_i64(tmp, off, ctx);
-	emit(A64_ADD(1, tmp, r2, tmp), ctx);
-	emit(A64_LSL(1, prg, r3, 3), ctx);
-	emit(A64_LDR64(prg, tmp, prg), ctx);
+	emit(A64_ADD_I(1, tmp, r2, off), ctx);
+	emit(A64_LDR64_UXTW3(prg, tmp, r3), ctx);
 	branch3 = ctx->image + ctx->idx;
 	emit(A64_NOP, ctx);
 
@@ -959,8 +963,7 @@ static int emit_bpf_tail_call(struct jit_ctx *ctx)
 
 	/* goto *(prog->bpf_func + prologue_offset); */
 	off = offsetof(struct bpf_prog, bpf_func);
-	emit_a64_mov_i64(tmp, off, ctx);
-	emit(A64_LDR64(tmp, prg, tmp), ctx);
+	emit(A64_LDR64I(tmp, prg, off), ctx);
 	emit(A64_ADD_I(1, tmp, tmp, sizeof(u32) * PROLOGUE_OFFSET), ctx);
 	emit(A64_BR(tmp), ctx);
 
-- 
2.43.0

[PATCH bpf-next v3 19/24] bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones

[Daniel Borkmann]

The logical immediate forms cannot encode all ones, so AND, OR and XOR
with -1 moved the constant into a temporary first. The XOR is common,
as LLVM lowers every bitwise NOT to r ^= -1.

Emit an mvn for the XOR and a mov of -1 for the OR. For the AND, emit a
32-bit mov to zero extend the 32-bit variant, and nothing for the
64-bit one.

Before/after for w1 &= -1 and w1 ^= -1:

  1280000a  mov w10, #0xffffffff
  0a0a0000  and w0, w0, w10
  2a0003e0  mov w0, w0

  1280000a  mov w10, #0xffffffff
  4a0a0000  eor w0, w0, w10
  2a2003e0  mvn w0, w0

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 a79c401c5262..b1f438d85721 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -1911,6 +1911,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);
@@ -1921,6 +1927,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);
@@ -1931,6 +1942,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 v3 20/24] bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests

[Daniel Borkmann]

A compare against zero for equality, a sign test and a single-bit test
each took a cmp or tst followed by a b.cond. CBZ/CBNZ and TBZ/TBNZ do
each in one instruction. That saves code size and a decode slot, and
also a uop on cores that do not fuse the pair. Null checks and sign
tests are the most frequent compares in BPF programs.

TBZ and TBNZ only reach +/-8K instructions, so a test uses them only
when its target is within reach in the sizing pass. The sizing pass has
the longest layout of all passes, the extra pass included, so the
target then stays in reach. The decisions are kept in a bitmap.

Before/after for if r0 == 0 goto ..., if w0 s< 0 goto ... and
if r1 & 0x8 goto ...:

  f100011f  cmp x8, #0x0
  54000040  b.eq ...
  b4000048  cbz x8, ...

  7100011f  cmp w8, #0x0
  5400004b  b.lt ...
  37f80048  tbnz w8, #0x1f, ...

  f27d001f  tst x0, #0x8
  54000041  b.ne ...
  37180040  tbnz w0, #0x3, ...

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

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 16c690c6cae9..7566698a38a8 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -30,6 +30,15 @@
 #define A64_CBNZ(sf, Rt, imm19) \
 	A64_COMP_BRANCH(sf, Rt, A64_BR_OFF(imm19), NONZERO)
 
+/* Test bit & branch (immediate) */
+#define A64_TEST_BRANCH(Rt, bit, offset, type) \
+	aarch64_insn_gen_test_branch_imm(0, offset, Rt, bit, \
+		AARCH64_INSN_BRANCH_TEST_##type)
+#define A64_TBZ(Rt, bit, imm14) \
+	A64_TEST_BRANCH(Rt, bit, A64_BR_OFF(imm14), ZERO)
+#define A64_TBNZ(Rt, bit, imm14) \
+	A64_TEST_BRANCH(Rt, bit, A64_BR_OFF(imm14), NONZERO)
+
 /* Conditional branch (immediate) */
 #define A64_COND_BRANCH(cond, offset) \
 	aarch64_insn_gen_cond_branch_imm(0, offset, cond)
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index b1f438d85721..53b2647c6a1b 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -94,6 +94,7 @@ struct jit_ctx {
 	bool fp_used;
 	bool priv_sp_used;
 	bool write;
+	unsigned long *tb;
 };
 
 struct bpf_plt {
@@ -603,6 +604,95 @@ static bool adjust_cmp_imm(u8 *op, s32 *imm)
 	return true;
 }
 
+/*
+ * The bit that a sign test, an unsigned 32-bit compare at the sign bit or a
+ * single bit test checks, with *nonzero set if it branches on a set bit, 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;
+	}
+}
+
+/*
+ * Pass 1 takes the compare and branch for every test and the indirect form for
+ * every call, no later layout is longer, so a test within reach of the test bit
+ * and branch there is within reach in every image.
+ */
+static void find_tb(struct jit_ctx *ctx)
+{
+	const struct bpf_prog *prog = ctx->prog;
+	bool nonzero;
+	int i, d;
+
+	for (i = 0; i < prog->len; i++) {
+		const struct bpf_insn *insn = &prog->insnsi[i];
+		const u8 class = BPF_CLASS(insn->code);
+
+		if ((class != BPF_JMP && class != BPF_JMP32) ||
+		    BPF_SRC(insn->code) != BPF_K)
+			continue;
+		if (tb_bit(BPF_OP(insn->code), class == BPF_JMP, insn->imm, &nonzero) < 0)
+			continue;
+		d = ctx->offset[i + 1 + insn->off] - (ctx->offset[i + 1] - 1);
+		if (d >= -SZ_8K && d < SZ_8K)
+			__set_bit(i, ctx->tb);
+	}
+}
+
+static bool emit_tb(bool nonzero, u8 reg, int bit, int i, s16 off, struct jit_ctx *ctx)
+{
+	int jmp_offset;
+
+	if (!test_bit(i, ctx->tb))
+		return false;
+	jmp_offset = bpf2a64_offset(i, off, ctx);
+	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
@@ -1740,6 +1830,8 @@ static int build_insn(const struct bpf_verifier_env *env, const struct bpf_insn
 	s32 jmp_offset;
 	u32 a64_insn;
 	int off_adj;
+	bool nonzero;
+	int bit;
 	int ret;
 
 	if (bpf_insn_is_indirect_target(env, ctx->prog, i))
@@ -2091,6 +2183,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)) {
@@ -2104,6 +2210,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);
@@ -2539,6 +2649,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);
@@ -2566,6 +2679,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 
 	if (build_body(env, &ctx, extra_pass))
 		goto out_off;
+	find_tb(&ctx);
 
 	ctx.epilogue_offset = ctx.idx;
 	build_epilogue(&ctx, was_classic, false);
@@ -2686,6 +2800,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;
@@ -3759,6 +3874,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 v3 21/24] bpf, arm64: Multiply by constants with shifts, adds and subs

[Daniel Borkmann]

LLVM leaves a multiplication by a constant other than a power of two as
is, and the JIT emitted it as a mov of the constant and a mul of two to
four cycles.

For constants of the form 2^n, 2^n + 1 or 2^n - 1, optionally negated
or multiplied by 2^m, emit at most two shifts, adds or subs instead.
Only sequences of at most two cycles are used, so they are never slower
than the mul.

A multiplication by 0 becomes a mov, by -1 a neg, and by 1 nothing
beyond the zero extension of the 32-bit variant.

Before/after for r1 *= 3, r1 *= 7 and r1 *= 24:

  d280006a  mov x10, #0x3
  9b0a7c00  mul x0, x0, x10
  8b000400  add x0, x0, x0, lsl #1

  d28000ea  mov x10, #0x7
  9b0a7c00  mul x0, x0, x10
  d37df00a  lsl x10, x0, #3
  cb000140  sub x0, x10, x0

  d280030a  mov x10, #0x18
  9b0a7c00  mul x0, x0, x10
  8b000400  add x0, x0, x0, lsl #1
  d37df000  lsl x0, x0, #3

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 arch/arm64/net/bpf_jit.h      | 12 ++++-
 arch/arm64/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++++++++++-
 2 files changed, 94 insertions(+), 4 deletions(-)

diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h
index 7566698a38a8..3bc88db350f7 100644
--- a/arch/arm64/net/bpf_jit.h
+++ b/arch/arm64/net/bpf_jit.h
@@ -227,11 +227,19 @@
 #define A64_MOVK(sf, Rd, imm16, shift) A64_MOVEW(sf, Rd, imm16, shift, KEEP)
 
 /* Add/subtract (shifted register) */
-#define A64_ADDSUB_SREG(sf, Rd, Rn, Rm, type) \
-	aarch64_insn_gen_add_sub_shifted_reg(Rd, Rn, Rm, 0, \
+#define A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, shift, type) \
+	aarch64_insn_gen_add_sub_shifted_reg(Rd, Rn, Rm, shift, \
 		A64_VARIANT(sf), AARCH64_INSN_ADSB_##type)
+#define A64_ADDSUB_SREG(sf, Rd, Rn, Rm, type) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, 0, type)
 /* Rd = Rn OP Rm */
 #define A64_ADD(sf, Rd, Rn, Rm)  A64_ADDSUB_SREG(sf, Rd, Rn, Rm, ADD)
+/* Rd = Rn + (Rm << shift) */
+#define A64_ADD_LSL(sf, Rd, Rn, Rm, shift) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, shift, ADD)
+/* Rd = Rn - (Rm << shift) */
+#define A64_SUB_LSL(sf, Rd, Rn, Rm, shift) \
+	A64_ADDSUB_SHIFT(sf, Rd, Rn, Rm, shift, SUB)
 #define A64_SUB(sf, Rd, Rn, Rm)  A64_ADDSUB_SREG(sf, Rd, Rn, Rm, SUB)
 #define A64_SUBS(sf, Rd, Rn, Rm) A64_ADDSUB_SREG(sf, Rd, Rn, Rm, SUB_SETFLAGS)
 /* Rd = -Rm */
diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c
index 53b2647c6a1b..b8d765d6ab07 100644
--- a/arch/arm64/net/bpf_jit_comp.c
+++ b/arch/arm64/net/bpf_jit_comp.c
@@ -693,6 +693,86 @@ static bool emit_tb(bool nonzero, u8 reg, int bit, int i, s16 off, struct jit_ct
 	return true;
 }
 
+/*
+ * dst *= 2^n, 2^n + 1 or 2^n - 1, negated or, but for -(2^n + 1), times 2^m,
+ * in at most two shifts, adds or subs of two cycles, never slower than the
+ * mul. The low 32 bits of the product are those of the signed or unsigned imm.
+ */
+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
@@ -2049,8 +2129,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, tmp, off, ctx);
+		if (off || !emit_mul_const(is64, dst, tmp, imm, ctx)) {
+			emit_a64_mov_i(is64, tmp, imm, ctx);
+			emit_a64_mul(is64, dst, tmp, off, ctx);
+		}
 		break;
 	case BPF_ALU | BPF_DIV | BPF_K:
 	case BPF_ALU64 | BPF_DIV | BPF_K:
-- 
2.43.0

[PATCH bpf-next v3 22/24] selftests/bpf: Let the arm64 private stack check skip the BTI pad

[Daniel Borkmann]

With CONFIG_ARM64_BTI_KERNEL, which is the default with clang before
21, the JIT emits a BTI J landing pad between the tail call counter
setup and the push of the callee-saved registers. The arm64
expectations of the "Private stack, exception in main prog" test want
the push right after the setup, so the test fails:

  WRONG LINE SUBSTR: '	stp	x19, x20, [sp, #-0x10]!'
  expecting match at line 9, actual match is at line 10

Let the expectation skip lines between the two, as other tests in the
same file already do.

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 0ce07bf6b566..e7f410a74a21 100644
--- a/tools/testing/selftests/bpf/progs/verifier_private_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_private_stack.c
@@ -286,6 +286,7 @@ __jited("	stp	x29, x30, [sp, #-0x10]!")
 __jited("	mov	x29, sp")
 __jited("	stp	xzr, x26, [sp, #-0x10]!")
 __jited("	mov	x26, sp")
+__jited("...")
 __jited("	stp	x19, x20, [sp, #-0x10]!")
 __jited("	stp	x21, x22, [sp, #-0x10]!")
 __jited("	stp	x23, x24, [sp, #-0x10]!")
-- 
2.43.0

[PATCH bpf-next v3 23/24] selftests/bpf: Test the verifier's division by constants

[Daniel Borkmann]

On the JITs that support UHMUL and SHMUL, check the uhmul and shmul
sequences that the verifier rewrites 64-bit divisions by a constant
into, one test per sequence shape, and the modulos that keep the
division. The results of the rewritten sequences are checked by
jit_insns' div_const.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/verifier_div_const.c  | 225 ++++++++++++++++++
 2 files changed, 227 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_div_const.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 0db43480cd99..4d77b8fd4eab 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -55,6 +55,7 @@
 #include "verifier_direct_packet_access.skel.h"
 #include "verifier_direct_stack_access_wraparound.skel.h"
 #include "verifier_div0.skel.h"
+#include "verifier_div_const.skel.h"
 #include "verifier_div_mod_bounds.skel.h"
 #include "verifier_div_overflow.skel.h"
 #include "verifier_flow_keys.skel.h"
@@ -263,6 +264,7 @@ void test_verifier_default_trusted_ptr(void)  { RUN_TESTS(verifier_default_trust
 void test_verifier_direct_packet_access(void) { RUN(verifier_direct_packet_access); }
 void test_verifier_direct_stack_access_wraparound(void) { RUN(verifier_direct_stack_access_wraparound); }
 void test_verifier_div0(void)                 { RUN(verifier_div0); }
+void test_verifier_div_const(void)            { RUN(verifier_div_const); }
 void test_verifier_div_mod_bounds(void)       { RUN(verifier_div_mod_bounds); }
 void test_verifier_div_overflow(void)         { RUN(verifier_div_overflow); }
 void test_verifier_flow_keys(void)            { RUN(verifier_flow_keys); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_div_const.c b/tools/testing/selftests/bpf/progs/verifier_div_const.c
new file mode 100644
index 000000000000..9601776ca2f7
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_div_const.c
@@ -0,0 +1,225 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/* BPF_REG_AX as the verifier dumps it */
+#define REG_AX "r13"
+
+/* JITs with UHMUL and SHMUL get the multiplication by the magic number */
+#if (defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || \
+	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64)) && \
+	(__clang_major__ >= 18 || defined(__BPF_FEATURE_SDIV_SMOD))
+
+SEC("socket")
+__description("udiv by 1000000000 shifts the dividend first")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: r0 >>= 9")
+__xlated("2: " REG_AX " = 0x44b82fa09b5a53")
+__xlated("4: r0 uh*= " REG_AX)
+__xlated("5: r0 >>= 11")
+__xlated("6: exit")
+__naked void udiv_shifted(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 /= 1000000000;				\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("udiv by 1000000")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x431bde82d7b634db")
+__xlated("3: r0 uh*= " REG_AX)
+__xlated("4: r0 >>= 18")
+__xlated("5: exit")
+__naked void udiv(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 /= 1000000;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("udiv by 7 takes the add sequence")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x2492492492492493")
+__xlated("3: " REG_AX " uh*= r0")
+__xlated("4: r0 -= " REG_AX)
+__xlated("5: r0 >>= 1")
+__xlated("6: r0 += " REG_AX)
+__xlated("7: r0 >>= 2")
+__xlated("8: exit")
+__naked void udiv_add(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 /= 7;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("umod by 1000000")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x431bde82d7b634db")
+__xlated("3: " REG_AX " uh*= r0")
+__xlated("4: " REG_AX " >>= 18")
+__xlated("5: " REG_AX " *= 1000000")
+__xlated("6: r0 -= " REG_AX)
+__xlated("7: exit")
+__naked void umod(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 %%= 1000000;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("umod by 1000 keeps the division")
+__success
+__xlated("...")
+__xlated("1: r0 %= 1000")
+__xlated("2: exit")
+__naked void umod_kept(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 %%= 1000;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("sdiv by 10")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x6666666666666667")
+__xlated("3: " REG_AX " sh*= r0")
+__xlated("4: " REG_AX " s>>= 2")
+__xlated("5: r0 = " REG_AX)
+__xlated("6: r0 >>= 63")
+__xlated("7: r0 += " REG_AX)
+__xlated("8: exit")
+__naked void sdiv(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 s/= 10;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("sdiv by 2 adds the dividend")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x8000000000000001")
+__xlated("3: " REG_AX " sh*= r0")
+__xlated("4: " REG_AX " += r0")
+__xlated("5: r0 = " REG_AX)
+__xlated("6: r0 >>= 63")
+__xlated("7: r0 += " REG_AX)
+__xlated("8: exit")
+__naked void sdiv_add(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 s/= 2;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("sdiv by -3 subtracts the dividend")
+__success
+__arch_x86_64 __arch_arm64 __arch_riscv64
+__load_if_JITed()
+__xlated("...")
+__xlated("1: " REG_AX " = 0x5555555555555555")
+__xlated("3: " REG_AX " sh*= r0")
+__xlated("4: " REG_AX " -= r0")
+__xlated("5: " REG_AX " s>>= 1")
+__xlated("6: r0 = " REG_AX)
+__xlated("7: r0 >>= 63")
+__xlated("8: r0 += " REG_AX)
+__xlated("9: exit")
+__naked void sdiv_sub(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 s/= -3;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("smod by 10 keeps the division")
+__success
+__xlated("...")
+__xlated("1: r0 s%= 10")
+__xlated("2: exit")
+__naked void smod_kept(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 s%%= 10;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+#else
+
+SEC("socket")
+__description("UHMUL/SHMUL or cpuv4 not supported, use a dummy test")
+__skip("UHMUL/SHMUL or cpuv4 not supported")
+__success
+int dummy_test(void)
+{
+	return 0;
+}
+
+#endif
+
+char _license[] SEC("license") = "GPL";
-- 
2.43.0

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

[Daniel Borkmann]

Cover the sequences that the arm64 JIT now emits: compares, bit tests,
constant arithmetic, immediates, sign jumps across the short branch
reach (also with a subprog call in between), arena and PROBE_MEM
addresses, and the tail call. The tests check the results, so they
apply to every JIT.

far_back_jump puts loops behind 52500 helper calls. In the arm64 sizing
pass this places them more than 1MB into the image, where a branch back
used to fail the JIT.

The arena atomics are only guarded at build time. On an arm64 CPU
without LSE, the kernel rejects them at load time, as the ll/sc atomics
have no arena support yet, so their subtests fail there on purpose.

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

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

diff --git a/tools/testing/selftests/bpf/prog_tests/jit_insns.c b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
index 5fd1c856ded7..0aaab23a2eef 100644
--- a/tools/testing/selftests/bpf/prog_tests/jit_insns.c
+++ b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
@@ -588,13 +588,14 @@ static void test_alu_imm_regs(void)
  * The dividends of the 32-bit operations carry garbage in the upper half.
  */
 static const __s32 unsigned_divisors[] = {
-	2, 3, 7, 10, 25, 641, 1000, 4096, 65536, 1000000007, 0x7fffffff,
-	-2, -10, -0x7fffffff - 1, -1, 1,
+	2, 3, 7, 10, 14, 25, 56, 641, 1000, 4096, 65536, 0x40000000, 1000000007,
+	0x7fffffff, -2, -10, -0x7fffffff - 1, -1, 1,
 };
 
 static const __s32 signed_divisors[] = {
-	2, 3, 7, 25, 1000, 0x40000000, 0x7fffffff,
-	-2, -3, -5, -7, -1000, -0x7fffffff, -0x7fffffff - 1, 1, -1,
+	2, 3, 4, 7, 8, 25, 1000, 0x80000, 0x40000000, 0x7fffffff,
+	-2, -3, -4, -5, -7, -8, -1000, -0x40000000, -0x7fffffff, -0x7fffffff - 1,
+	1, -1,
 };
 
 static int dividends(__u32 flags, __s32 imm, __u64 *n)
@@ -1119,7 +1120,8 @@ static void test_ld_imm64(void)
 	static const __u64 imms[] = {
 		0, 1, 0x7fffffff, 0x80000000, 0xffffffff, 0x100000000ULL,
 		0xffffffffffffffffULL, 0xffffffff80000000ULL, 0xffffffff7fffffffULL,
-		0x0123456789abcdefULL,
+		0x0123456789abcdefULL, 0xcccccccccccccccdULL, 0x5a5a12345a5a5a5aULL,
+		0x5a5a00005a5affffULL, 0x00ff00ff00ff00ffULL, 0x1234567812345678ULL,
 	};
 	int block = 64, bit, adj, sign, p, pattern, index, rd, i;
 	struct batch b;
@@ -1467,6 +1469,10 @@ static void test_staggered_jumps(void)
 		  BPF_JMP32_IMM(BPF_JLT, BPF_REG_1, 0x80000000, 0), 1234, 0 },
 		{ "staggered jmp32_jsge_x",
 		  BPF_JMP32_REG(BPF_JSGE, BPF_REG_1, BPF_REG_2, 0), -2, -2 },
+		{ "staggered jmp_jeq_k zero",
+		  BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 0), 0, 0 },
+		{ "staggered jmp_jslt_k zero",
+		  BPF_JMP_IMM(BPF_JSLT, BPF_REG_1, 0, 0), -1, 0 },
 	};
 	char desc[64];
 	int i, d;
@@ -1515,7 +1521,7 @@ static const __u64 inputs[] = {
 };
 
 struct prog {
-	struct bpf_insn insns[16];
+	struct bpf_insn insns[32];
 	int cnt;
 };
 
@@ -1568,7 +1574,7 @@ static void test_ldst_zero_off(void)
 	static const int aops[] = {
 		BPF_ADD, BPF_ADD | BPF_FETCH, BPF_OR, BPF_XCHG, BPF_CMPXCHG,
 	};
-	static const __s32 imms[] = { 0x5a, -1 };
+	static const __s32 imms[] = { 0x5a, -1, 0 };
 	struct prog p;
 	char desc[64];
 	int b, k, s, j, fd;
@@ -1645,12 +1651,13 @@ static void test_ldst_zero_off(void)
 				close(fd);
 			}
 
-			/* Store an immediate with a zero offset into a zeroed stack slot */
+			/* Store an immediate with a zero offset over in0 in a stack slot */
 			for (k = 0; k < ARRAY_SIZE(imms); k++) {
 				int rd = pair_reg(b, 1);
 
 				prog_start(&p);
-				EMIT(&p, BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0));
+				EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN0));
+				EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rd, -8));
 				EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
 				EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8));
 				EMIT(&p, BPF_ST_MEM(size, rb, 0, imms[k]));
@@ -1661,8 +1668,10 @@ static void test_ldst_zero_off(void)
 				fd = prog_load(&p, desc);
 				if (fd < 0)
 					return;
-				prog_run(fd, 0, 0,
-					 head_merge(0, (__u64)(__s64)imms[k], size), desc);
+				for (j = 0; j < ARRAY_SIZE(inputs); j++)
+					prog_run(fd, inputs[j], 0,
+						 head_merge(inputs[j], (__u64)(__s64)imms[k], size),
+						 desc);
 				close(fd);
 			}
 
@@ -1755,11 +1764,20 @@ static int offsets_for(int size, bool unaligned, int *off)
 	off[cnt++] = -128;
 	off[cnt++] = -128 - n;
 	off[cnt++] = -256;
+	off[cnt++] = -256 - n;
 	off[cnt++] = -4096;
 	off[cnt++] = -MEM_BASE;
+	/* The last offset of the scaled form and the first past it, 4095 to 16384 */
+	if (n < 8)
+		off[cnt++] = 0xfff * n;
+	if (n > 1 && n < 8)
+		off[cnt++] = 0x1000 * n;
 	if (n > 1 && unaligned) {
 		off[cnt++] = 13;
 		off[cnt++] = 127;
+		off[cnt++] = 255;
+		off[cnt++] = 257;
+		off[cnt++] = -257;
 		off[cnt++] = -13;
 		off[cnt++] = -129;
 	}
@@ -1971,7 +1989,7 @@ static void store_offsets(struct off_mem *m, int size, int rb, int rd, __s32 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;
@@ -2084,7 +2102,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];
@@ -2096,14 +2115,19 @@ static void test_jset_imm(void)
 
 		for (is64 = false; ; is64 = true) {
 			for (m = 0; m < ARRAY_SIZE(masks); m++) {
+				__u64 mk = is64 ? (__u64)(__s64)masks[m] : (__u32)masks[m];
+				/* The mask, its complement and its neighbors pin a single bit */
+				__u64 vals[ARRAY_SIZE(inputs) + 4] = { mk, ~mk, mk << 1, mk >> 1 };
+
+				memcpy(vals + 4, inputs, sizeof(inputs));
 				jmp_prog(&p, is64, BPF_JSET, d, masks[m], 1);
 				snprintf(desc, sizeof(desc), "jset%d dst=r%d mask=0x%x",
 					 is64 ? 64 : 32, rd, masks[m]);
 				fd = prog_load(&p, desc);
 				if (fd < 0)
 					return;
-				for (j = 0; j < ARRAY_SIZE(inputs); j++) {
-					__u64 v = inputs[j];
+				for (j = 0; j < ARRAY_SIZE(vals); j++) {
+					__u64 v = vals[j];
 					bool taken;
 
 					if (is64)
@@ -2151,7 +2175,11 @@ static bool cmp_taken(int op, bool is64, __u64 v, __u64 c)
 static void test_cmp_imm(void)
 {
 	static const __s32 imms[] = {
-		1, -1, 0x7f, 0x80, -0x80, -0x81, 0x1000, 0x7fffffff,
+		0, 1, -1, 0x7f, 0x80, -0x80, -0x81, 0x1000, 0x7fffffff,
+		0xfff, 0x1001, 0xffff, 0x10000, 0x10001, -0x1000, -0x1001,
+		-0x7fffffff - 1, 0x7ffffffe, 0x12345, -0x12345, 0xfff001,
+		0xffffff, -0xffffff, 0x1000000, -0x1000000, 0x3ffc, -0x10001,
+		0xfff000, -0xfff, -0xfff000, -0xfff001, 0x1000001,
 	};
 	static const int ops[] = {
 		BPF_JEQ, BPF_JNE, BPF_JGT, BPF_JGE, BPF_JLT, BPF_JLE,
@@ -2182,8 +2210,18 @@ static void test_cmp_imm(void)
 
 						prog_run(fd, inputs[j], 0, taken, desc);
 					}
+					/* The operands at the immediate and right next to it */
+					for (j = -1; j <= 1; j++) {
+						__s64 near = (__s64)imms[m] + j;
+						__u64 v = is64 ? (__u64)near : (__u32)near;
+						__u64 c = is64 ? (__u64)(__s64)imms[m] :
+							  (__u32)imms[m];
+						__u64 taken = cmp_taken(ops[o], is64, v, c);
+
+						prog_run(fd, v, 0, taken, desc);
+					}
 					close(fd);
-					if (m)
+					if (imms[m] < -1 || imms[m] > 1)
 						continue;
 					/* A jump over nothing lands on the same path either way */
 					jmp_prog(&p, is64, ops[o], d, imms[m], 0);
@@ -2230,12 +2268,31 @@ static void test_alu_consts(void)
 		{ BPF_ADD, 1 }, { BPF_ADD, -1 }, { BPF_SUB, 1 }, { BPF_SUB, -1 },
 		{ BPF_ADD, 128 }, { BPF_SUB, 128 }, { BPF_ADD, -128 },
 		{ BPF_AND, 0xff }, { BPF_AND, 0xffff }, { BPF_AND, 0x7f },
-		{ BPF_AND, 0x3ff }, { BPF_AND, 0x7fffffff },
-		{ BPF_OR, 0xff }, { BPF_XOR, -1 }, { BPF_XOR, 0x80 },
+		{ BPF_AND, 0x3ff }, { BPF_AND, 0x7fffffff }, { BPF_AND, -1 },
+		{ BPF_OR, 0xff }, { BPF_OR, -1 }, { BPF_XOR, -1 }, { BPF_XOR, 0x80 },
 		{ BPF_MUL, 2 }, { BPF_MUL, 3 }, { BPF_MUL, 4 }, { BPF_MUL, 5 },
 		{ BPF_MUL, 7 }, { BPF_MUL, 8 }, { BPF_MUL, 9 }, { BPF_MUL, 16 },
+		{ BPF_MUL, 17 }, { BPF_MUL, 33 }, { BPF_MUL, 0x40000001 },
 		{ BPF_MUL, 0x40000000 }, { BPF_MUL, -3 }, { BPF_MUL, -0x7fffffff - 1 },
 		{ BPF_MUL, 0 }, { BPF_MUL, 1 }, { BPF_MUL, -1 },
+		{ BPF_ADD, 0 }, { BPF_SUB, 0 }, { BPF_OR, 0 }, { BPF_XOR, 0 }, { BPF_AND, 0 },
+		{ BPF_MUL, 6 }, { BPF_MUL, 10 }, { BPF_MUL, 12 }, { BPF_MUL, 14 },
+		{ BPF_MUL, 15 }, { BPF_MUL, 24 }, { BPF_MUL, 31 }, { BPF_MUL, 48 },
+		{ BPF_MUL, 0x3fffffff }, { BPF_MUL, 0x7fffffff }, { BPF_MUL, -2 },
+		{ BPF_MUL, -4 }, { BPF_MUL, -6 }, { BPF_MUL, -7 }, { BPF_MUL, -8 },
+		{ BPF_MUL, -9 }, { BPF_MUL, -14 }, { BPF_MUL, -15 }, { BPF_MUL, -16 },
+		{ BPF_MUL, -0x40000000 }, { BPF_MUL, -0x7fffffff },
+		{ BPF_ADD, 0x10000 }, { BPF_ADD, 0x10001 }, { BPF_SUB, 0x10001 },
+		{ BPF_ADD, 0x12345 }, { BPF_ADD, -0x12345 }, { BPF_SUB, 0x12345 },
+		{ BPF_SUB, -0x12345 }, { BPF_ADD, 0xffffff }, { BPF_ADD, -0xffffff },
+		{ BPF_SUB, 0xffffff }, { BPF_ADD, 0x1000000 }, { BPF_SUB, -0x1000000 },
+		{ BPF_ADD, 0x123000 }, { BPF_ADD, 0xfff001 }, { BPF_SUB, 0x1001 },
+		{ BPF_ADD, -0x7fffffff - 1 }, { BPF_SUB, -0x7fffffff - 1 },
+		{ BPF_MUL, 66 }, { BPF_MUL, 272 }, { BPF_MUL, 240 }, { BPF_MUL, 992 },
+		{ BPF_MUL, -17 }, { BPF_MUL, -33 }, { BPF_MUL, -48 }, { BPF_MUL, -96 },
+		{ BPF_MUL, -12 }, { BPF_MUL, -24 }, { BPF_MUL, -28 },
+		{ BPF_ADD, 0x3ffc }, { BPF_ADD, -0x10001 }, { BPF_SUB, 0x3ffc },
+		{ BPF_SUB, -0x10001 },
 	};
 	struct prog p;
 	char desc[64];
@@ -2334,6 +2391,21 @@ static void test_probe_mem(void)
 		{ BPF_B, false }, { BPF_H, false }, { BPF_W, false }, { BPF_DW, false },
 		{ BPF_B, true }, { BPF_H, true }, { BPF_W, true },
 	};
+	/*
+	 * Offsets that take an add, a sub, both shifted, or a mov and an add,
+	 * into the ctx from a base moved by -base, and off NULL or user memory
+	 */
+	static const struct {
+		int size;
+		__s16 off;
+		__s16 base;
+	} probes_in[] = {
+		{ BPF_DW, 8 }, { BPF_W, 4 }, { BPF_H, 2 }, { BPF_B, 13 },
+		{ BPF_DW, 0x1008, 0x1008 }, { BPF_W, -0x1004, -0x1004 },
+	}, probes_out[] = {
+		{ BPF_DW, 0 }, { BPF_B, 13 }, { BPF_DW, -8 }, { BPF_W, 4096 }, { BPF_H, -4096 },
+		{ BPF_W, 0x1004 }, { BPF_W, -0x1004 },
+	};
 	int kfunc_id, type_id, b, k, l, j, fd;
 	struct bpf_insn call;
 	struct btf *btf;
@@ -2392,24 +2464,62 @@ static void test_probe_mem(void)
 		}
 	}
 
-	/* NULL and a user address are not touched and read as zero */
-	for (j = 0; j < 2; j++) {
-		__u64 addr = j ? 0x00007ffffffff000ULL : 0;
+	/* The offset forms through the untrusted pointer of the cast to void */
+	for (l = 0; l < ARRAY_SIZE(probes_in); l++) {
+		int size = probes_in[l].size, off = probes_in[l].off;
+		int base = probes_in[l].base;
 
 		prog_start(&p);
-		EMIT(&p, BPF_RAW_INSN(BPF_LD | BPF_DW | BPF_IMM, BPF_REG_1, 0, 0, (__u32)addr));
-		EMIT(&p, BPF_RAW_INSN(0, 0, 0, 0, addr >> 32));
-		EMIT(&p, BPF_MOV32_IMM(BPF_REG_2, type_id));
+		EMIT(&p, BPF_MOV64_REG(BPF_REG_1, BPF_REG_6));
+		if (base)
+			EMIT(&p, BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -base));
+		EMIT(&p, BPF_MOV32_IMM(BPF_REG_2, 0));
 		EMIT(&p, call);
-		EMIT(&p, BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, 0));
+		EMIT(&p, BPF_LDX_MEM(size, BPF_REG_3, BPF_REG_0, off));
 		prog_end(&p, BPF_REG_3);
-		snprintf(desc, sizeof(desc), "probe_mem addr=0x%llx", addr);
+		snprintf(desc, sizeof(desc), "probe_mem void size=%d off=%d base=%d",
+			 size, off, base);
 		fd = prog_load(&p, desc);
 		if (fd < 0)
 			return;
-		prog_run(fd, 0, 0, 0, desc);
+		for (j = 0; j < ARRAY_SIZE(inputs); j++) {
+			struct pat_ctx c = { .in0 = inputs[j], .in1 = ~inputs[j] };
+
+			prog_run(fd, c.in0, c.in1,
+				 load_bytes((__u8 *)&c + off - base, size), desc);
+		}
 		close(fd);
 	}
+
+	/*
+	 * NULL and a user address read as zero, skipped or fixed up after a
+	 * fault; no NULL plus a positive offset, as s390x has its lowcore there
+	 */
+	for (l = 0; l < ARRAY_SIZE(probes_out); l++) {
+		int size = probes_out[l].size, off = probes_out[l].off;
+
+		for (j = 0; j < 2; j++) {
+			__u64 addr = j ? 0x00007ffffffe0000ULL : 0;
+
+			if (!addr && off > 0)
+				continue;
+			prog_start(&p);
+			EMIT(&p, BPF_RAW_INSN(BPF_LD | BPF_DW | BPF_IMM, BPF_REG_1, 0, 0,
+					      (__u32)addr));
+			EMIT(&p, BPF_RAW_INSN(0, 0, 0, 0, addr >> 32));
+			EMIT(&p, BPF_MOV32_IMM(BPF_REG_2, l ? 0 : type_id));
+			EMIT(&p, call);
+			EMIT(&p, BPF_LDX_MEM(size, BPF_REG_3, BPF_REG_0, off));
+			prog_end(&p, BPF_REG_3);
+			snprintf(desc, sizeof(desc), "probe_mem addr=0x%llx size=%d off=%d",
+				 addr, size, off);
+			fd = prog_load(&p, desc);
+			if (fd < 0)
+				return;
+			prog_run(fd, 0, 0, 0, desc);
+			close(fd);
+		}
+	}
 }
 
 /*
@@ -2421,9 +2531,11 @@ static void test_probe_mem(void)
 static void test_acq_rel(void)
 {
 	static const int sizes[] = { BPF_B, BPF_H, BPF_W, BPF_DW };
+	/* The slot through the base at the slot, below it and above it */
+	static const int offs[] = { 0, 8, -8 };
 	struct prog p;
 	char desc[64];
-	int b, k, s, j, fd;
+	int b, k, s, o, j, fd;
 
 	for (b = 0; b < ARRAY_SIZE(pat_regs); b++) {
 		int rb = pat_regs[b];
@@ -2434,49 +2546,169 @@ static void test_acq_rel(void)
 			for (k = 0; k < NR_PAIRS; k++) {
 				int rd = pair_reg(b, k);
 
-				/* Load-acquire from the slot, also into the base */
-				prog_start(&p);
-				EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN0));
-				EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rd, -8));
-				EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
-				EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8));
-				EMIT(&p, BPF_ATOMIC_OP(size, BPF_LOAD_ACQ, rd, rb, 0));
-				prog_end(&p, rd);
-				snprintf(desc, sizeof(desc), "load_acq size=%d base=r%d dst=r%d",
-					 size, rb, rd);
-				fd = prog_load(&p, desc);
-				if (fd < 0)
-					return;
-				for (j = 0; j < ARRAY_SIZE(inputs); j++)
-					prog_run(fd, inputs[j], 0,
-						 head_bytes(inputs[j], size), desc);
-				close(fd);
+				for (o = 0; o < ARRAY_SIZE(offs); o++) {
+					int off = offs[o];
+
+					/* Load-acquire from the slot, also into the base */
+					prog_start(&p);
+					EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN0));
+					EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rd, -8));
+					EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
+					EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8 - off));
+					EMIT(&p, BPF_ATOMIC_OP(size, BPF_LOAD_ACQ, rd, rb, off));
+					prog_end(&p, rd);
+					snprintf(desc, sizeof(desc),
+						 "load_acq size=%d base=r%d dst=r%d off=%d",
+						 size, rb, rd, off);
+					fd = prog_load(&p, desc);
+					if (fd < 0)
+						return;
+					for (j = 0; j < ARRAY_SIZE(inputs); j++)
+						prog_run(fd, inputs[j], 0,
+							 head_bytes(inputs[j], size), desc);
+					close(fd);
+
+					if (rd == rb)
+						continue;
+					/* Store-release of in1 over the slot holding in0 */
+					prog_start(&p);
+					EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN0));
+					EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rd, -8));
+					EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN1));
+					EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
+					EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8 - off));
+					EMIT(&p, BPF_ATOMIC_OP(size, BPF_STORE_REL, rb, rd, off));
+					EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_10, -8));
+					prog_end(&p, rd);
+					snprintf(desc, sizeof(desc),
+						 "store_rel size=%d base=r%d src=r%d off=%d",
+						 size, rb, rd, off);
+					fd = prog_load(&p, desc);
+					if (fd < 0)
+						return;
+					for (j = 0; j < ARRAY_SIZE(inputs); j++) {
+						__u64 in1 = inputs[(j + 1) % ARRAY_SIZE(inputs)];
+
+						prog_run(fd, inputs[j], in1,
+							 head_merge(inputs[j], in1, size), desc);
+					}
+					close(fd);
+				}
+			}
+		}
+	}
+}
+
+/* The n-th register after pat_regs[b] that is neither it nor r0 */
+static int ptr_operand_reg(int b, int n)
+{
+	int i = b;
+
+	while (n--) {
+		do {
+			i = (i + 1) % ARRAY_SIZE(pat_regs);
+		} while (pat_regs[i] == BPF_REG_0);
+	}
+	return pat_regs[i];
+}
+
+/* rr |= bit unless ra == rb, compared in the width of size */
+static void check_eq(struct prog *p, int size, int ra, int rb, int rr, int bit)
+{
+	if (size == BPF_W)
+		EMIT(p, BPF_JMP32_REG(BPF_JEQ, ra, rb, 1));
+	else
+		EMIT(p, BPF_JMP_REG(BPF_JEQ, ra, rb, 1));
+	EMIT(p, BPF_ALU64_IMM(BPF_OR, rr, bit));
+}
+
+/*
+ * Atomics with the pointer itself as the operand (src == dst, and cmpxchg
+ * with the pointer as the new value), the bytes written checked against the
+ * operation done on a copy of the pointer made a number by two negations.
+ */
+static void test_atomic_ptr_operand(void)
+{
+	static const int sizes[] = { BPF_DW, BPF_W };
+	static const int ops[] = { BPF_ADD, BPF_AND, BPF_OR, BPF_XOR };
+	struct prog p;
+	char desc[64];
+	int b, k, s, j, fd;
+
+	for (b = 0; b < ARRAY_SIZE(pat_regs); b++) {
+		/* The pointer, a copy of it, the expected value, the memory and the result */
+		int rb = pat_regs[b], rp = ptr_operand_reg(b, 1), rv = ptr_operand_reg(b, 2);
+		int rm = ptr_operand_reg(b, 3), rr = ptr_operand_reg(b, 4);
+
+		for (s = 0; s < ARRAY_SIZE(sizes); s++) {
+			int size = sizes[s];
+			bool w = size == BPF_W;
+
+			for (k = 0; k < ARRAY_SIZE(ops); k++) {
+				int op = ops[k];
 
-				if (rd == rb)
-					continue;
-				/* Store-release of in1 over the slot holding in0 */
 				prog_start(&p);
-				EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN0));
-				EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rd, -8));
-				EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_6, IN1));
+				EMIT(&p, BPF_MOV64_IMM(rr, 0));
+				EMIT(&p, BPF_LDX_MEM(BPF_DW, rv, BPF_REG_6, IN0));
+				EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rv, -8));
 				EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
 				EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8));
-				EMIT(&p, BPF_ATOMIC_OP(size, BPF_STORE_REL, rb, rd, 0));
-				EMIT(&p, BPF_LDX_MEM(BPF_DW, rd, BPF_REG_10, -8));
-				prog_end(&p, rd);
-				snprintf(desc, sizeof(desc), "store_rel size=%d base=r%d src=r%d",
-					 size, rb, rd);
+				EMIT(&p, BPF_MOV64_REG(rp, rb));
+				EMIT(&p, BPF_ALU64_IMM(BPF_NEG, rp, 0));
+				EMIT(&p, BPF_ALU64_IMM(BPF_NEG, rp, 0));
+				/* The bytes the atomic operates on, whichever the byte order */
+				EMIT(&p, BPF_LDX_MEM(size, rv, rb, 0));
+				EMIT(&p, BPF_ATOMIC_OP(size, op, rb, rb, 0));
+				/* The memory holds in0 <op> pointer, the register the pointer */
+				if (w)
+					EMIT(&p, BPF_ALU32_REG(op, rv, rp));
+				else
+					EMIT(&p, BPF_ALU64_REG(op, rv, rp));
+				/* Read back through fp, a clobbered pointer must not fault */
+				EMIT(&p, BPF_LDX_MEM(size, rm, BPF_REG_10, -8));
+				check_eq(&p, BPF_DW, rm, rv, rr, 1);
+				check_eq(&p, BPF_DW, rb, rp, rr, 2);
+				prog_end(&p, rr);
+				snprintf(desc, sizeof(desc), "atomic%d_%s ptr=r%d",
+					 w ? 32 : 64, alu_name(op), rb);
 				fd = prog_load(&p, desc);
 				if (fd < 0)
 					return;
-				for (j = 0; j < ARRAY_SIZE(inputs); j++) {
-					__u64 in1 = inputs[(j + 1) % ARRAY_SIZE(inputs)];
-
-					prog_run(fd, inputs[j], in1,
-						 head_merge(inputs[j], in1, size), desc);
-				}
+				for (j = 0; j < ARRAY_SIZE(inputs); j++)
+					prog_run(fd, inputs[j], 0, 0, desc);
 				close(fd);
 			}
+
+			/* The pointer as the new value, r0 holds in0 and matches */
+			if (rb == BPF_REG_0)
+				continue;
+			prog_start(&p);
+			EMIT(&p, BPF_MOV64_IMM(rr, 0));
+			EMIT(&p, BPF_LDX_MEM(BPF_DW, rv, BPF_REG_6, IN0));
+			EMIT(&p, BPF_STX_MEM(BPF_DW, BPF_REG_10, rv, -8));
+			EMIT(&p, BPF_MOV64_REG(rb, BPF_REG_10));
+			EMIT(&p, BPF_ALU64_IMM(BPF_ADD, rb, -8));
+			EMIT(&p, BPF_MOV64_REG(rp, rb));
+			EMIT(&p, BPF_ALU64_IMM(BPF_NEG, rp, 0));
+			EMIT(&p, BPF_ALU64_IMM(BPF_NEG, rp, 0));
+			/* r0 holds the bytes the atomic compares with and matches */
+			EMIT(&p, BPF_LDX_MEM(size, BPF_REG_0, rb, 0));
+			EMIT(&p, BPF_MOV64_REG(rv, BPF_REG_0));
+			EMIT(&p, BPF_ATOMIC_OP(size, BPF_CMPXCHG, rb, rb, 0));
+			/* The memory holds the pointer in the width, r0 the old value */
+			EMIT(&p, BPF_LDX_MEM(size, rm, BPF_REG_10, -8));
+			check_eq(&p, size, rm, rp, rr, 1);
+			check_eq(&p, BPF_DW, BPF_REG_0, rv, rr, 2);
+			check_eq(&p, BPF_DW, rb, rp, rr, 4);
+			prog_end(&p, rr);
+			snprintf(desc, sizeof(desc), "atomic%d_cmpxchg ptr=r%d new=r%d",
+				 w ? 32 : 64, rb, rb);
+			fd = prog_load(&p, desc);
+			if (fd < 0)
+				return;
+			for (j = 0; j < ARRAY_SIZE(inputs); j++)
+				prog_run(fd, inputs[j], 0, 0, desc);
+			close(fd);
 		}
 	}
 }
@@ -2540,6 +2772,231 @@ static void test_max_jmp(void)
 	max_jmp(true, false);
 }
 
+/*
+ * A sign test forward or back over a region of n sign tests, which shrink it
+ * as they take the short branch; n sweeps the reach of the sizing pass.
+ */
+#define CHAIN_NO_CALL	0
+#define CHAIN_HELPER	1
+#define CHAIN_SUBPROG	2
+
+static void sign_jumps(int inner, bool back, int call, const char *desc)
+{
+	struct bpf_insn *insns;
+	int n = 0, top, sub = 0, i, fd;
+
+	insns = malloc((24 + 2 * inner) * sizeof(*insns));
+	if (!ASSERT_OK_PTR(insns, desc))
+		return;
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, IN0);
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_1, IN1);
+	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_2, 1);
+	if (back)
+		insns[n++] = BPF_MOV64_IMM(BPF_REG_4, -2);
+	else
+		insns[n++] = BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, 0);
+	top = n;
+	for (i = 0; i < inner; i++) {
+		insns[n++] = BPF_JMP_IMM(BPF_JSGE, BPF_REG_3, 0, 1);
+		insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1);
+	}
+	if (call != CHAIN_NO_CALL) {
+		/* The call clobbers r0 to r5: the count, the sign and the loop go to r7 to r9 */
+		insns[n++] = BPF_MOV64_REG(BPF_REG_7, BPF_REG_2);
+		insns[n++] = BPF_MOV64_REG(BPF_REG_8, BPF_REG_3);
+		if (back)
+			insns[n++] = BPF_MOV64_REG(BPF_REG_9, BPF_REG_4);
+		sub = n++;
+		insns[n++] = BPF_MOV64_REG(BPF_REG_2, BPF_REG_7);
+		insns[n++] = BPF_MOV64_REG(BPF_REG_3, BPF_REG_8);
+		if (back)
+			insns[n++] = BPF_MOV64_REG(BPF_REG_4, BPF_REG_9);
+	}
+	if (back) {
+		insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 1);
+		insns[n] = BPF_JMP_IMM(BPF_JSLT, BPF_REG_4, 0, top - n - 1);
+		n++;
+	} else {
+		insns[top - 1] = BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, n - top);
+	}
+	insns[n++] = BPF_STX_MEM(BPF_DW, BPF_REG_6, BPF_REG_2, RES);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[n++] = BPF_EXIT_INSN();
+	if (call == CHAIN_SUBPROG) {
+		insns[sub] = BPF_CALL_REL(n - sub - 1);
+		insns[n++] = BPF_MOV64_IMM(BPF_REG_0, 0);
+		insns[n++] = BPF_EXIT_INSN();
+	} else if (call == CHAIN_HELPER) {
+		insns[sub] = BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32);
+	}
+
+	fd = load_prog(insns, n, desc);
+	free(insns);
+	if (fd < 0)
+		return;
+	/* One plus the adds with the inner sign set, none with the outer one */
+	prog_run(fd, 0, -1, back ? 2 * inner + 1 : inner + 1, desc);
+	prog_run(fd, 0, 0, 1, desc);
+	prog_run(fd, -1, -1, back ? 2 * inner + 1 : 1, desc);
+	prog_run(fd, 1ULL << 63, -1, back ? 2 * inner + 1 : 1, desc);
+	close(fd);
+}
+
+/*
+ * A chain of sign tests over the region, each an instruction further out than
+ * the next, so each would fit the short reach only once the next one shrank;
+ * a call in the region shrinks it.
+ */
+static void sign_jump_chain(int inner, int outer, int call, const char *desc)
+{
+	struct bpf_insn *insns;
+	int n = 0, top, off, sub = 0, i, fd;
+
+	insns = malloc((16 + 2 * outer + 2 * inner) * sizeof(*insns));
+	if (!ASSERT_OK_PTR(insns, desc))
+		return;
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, IN0);
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_1, IN1);
+	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_2, 0);
+	top = n;
+	n += outer;
+	for (i = 0; i < inner; i++) {
+		insns[n++] = BPF_JMP_IMM(BPF_JSGE, BPF_REG_3, 0, 1);
+		insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1);
+	}
+	if (call != CHAIN_NO_CALL) {
+		insns[n++] = BPF_MOV64_REG(BPF_REG_7, BPF_REG_2);
+		sub = n++;
+		insns[n++] = BPF_MOV64_REG(BPF_REG_2, BPF_REG_7);
+	}
+	/* The i-th test jumps to the i-th add behind the region, the same offset for all */
+	off = n - top - 1;
+	for (i = 0; i < outer; i++) {
+		insns[top + i] = BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, off);
+		insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1);
+	}
+	insns[n++] = BPF_STX_MEM(BPF_DW, BPF_REG_6, BPF_REG_2, RES);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[n++] = BPF_EXIT_INSN();
+	if (call == CHAIN_SUBPROG) {
+		insns[sub] = BPF_CALL_REL(n - sub - 1);
+		insns[n++] = BPF_MOV64_IMM(BPF_REG_0, 0);
+		insns[n++] = BPF_EXIT_INSN();
+	} else if (call == CHAIN_HELPER) {
+		insns[sub] = BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32);
+	}
+
+	fd = load_prog(insns, n, desc);
+	free(insns);
+	if (fd < 0)
+		return;
+	/* The adds of the region with the inner sign set, the ones behind it always */
+	prog_run(fd, 0, -1, inner + outer, desc);
+	prog_run(fd, 0, 0, outer, desc);
+	prog_run(fd, -1, -1, outer, desc);
+	prog_run(fd, 1ULL << 63, -1, outer, desc);
+	close(fd);
+}
+
+/*
+ * A sign test forward over n fillers that keep their size, so that the short
+ * branch gets exactly the offset the sizing pass measured: n = 8190 at most.
+ */
+static void sign_jump_fill(int fill, const char *desc)
+{
+	struct bpf_insn *insns;
+	int n = 0, top, i, fd;
+
+	insns = malloc((8 + fill) * sizeof(*insns));
+	if (!ASSERT_OK_PTR(insns, desc))
+		return;
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, IN0);
+	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_2, 2);
+	top = n++;
+	for (i = 1; i < fill; i++)
+		insns[n++] = BPF_MOV64_IMM(BPF_REG_3, 0);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_2, 1);
+	insns[top] = BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, n - top - 1);
+	insns[n++] = BPF_STX_MEM(BPF_DW, BPF_REG_6, BPF_REG_2, RES);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[n++] = BPF_EXIT_INSN();
+
+	fd = load_prog(insns, n, desc);
+	free(insns);
+	if (fd < 0)
+		return;
+	prog_run(fd, -1, 0, 2, desc);
+	prog_run(fd, 0, 0, 1, desc);
+	close(fd);
+}
+
+static void test_sign_jumps(void)
+{
+	/* 2729 to 2732: a region of 8187 to 8196 instructions as the sizing pass sees it */
+	static const int inners[] = { 16, 2000, 2729, 2730, 2731, 2732, 4200 };
+	static const int chain_inners[][2] = { { 2716, 2724 }, { 4080, 4098 } };
+	char desc[80];
+	int i, inner;
+
+	for (i = 0; i < ARRAY_SIZE(inners); i++) {
+		snprintf(desc, sizeof(desc), "sign jump over %d sign jumps", inners[i]);
+		sign_jumps(inners[i], false, CHAIN_NO_CALL, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps", inners[i]);
+		sign_jumps(inners[i], true, CHAIN_NO_CALL, desc);
+	}
+	/*
+	 * The reach of the sizing pass with a subprogram call in the region,
+	 * which the extra pass makes direct
+	 */
+	for (inner = 2722; inner <= 2733; inner++) {
+		snprintf(desc, sizeof(desc), "sign jump over %d sign jumps and a subprog call",
+			 inner);
+		sign_jumps(inner, false, CHAIN_SUBPROG, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps and a subprog call",
+			 inner);
+		sign_jumps(inner, true, CHAIN_SUBPROG, desc);
+	}
+	/* The exact reach of the short branch, 8190 fillers and no more */
+	for (inner = 8189; inner <= 8192; inner++) {
+		snprintf(desc, sizeof(desc), "sign jump over %d fillers", inner);
+		sign_jump_fill(inner, desc);
+	}
+	/*
+	 * Across the reach of the shrunk region, where the tests keep the
+	 * compare and branch, also with a subprogram call in the extra pass
+	 */
+	for (inner = 4086; inner <= 4100; inner++) {
+		snprintf(desc, sizeof(desc), "sign jump over %d sign jumps at the range", inner);
+		sign_jumps(inner, false, CHAIN_NO_CALL, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps at the range",
+			 inner);
+		sign_jumps(inner, true, CHAIN_NO_CALL, desc);
+		snprintf(desc, sizeof(desc), "sign jump back over %d sign jumps and a subprog call",
+			 inner);
+		sign_jumps(inner, true, CHAIN_SUBPROG, desc);
+	}
+	/*
+	 * Chains across the reach of the sizing pass over 2716 to 2724 inner
+	 * tests, where they are decided, and of the shrunk region over 4080 to
+	 * 4098.
+	 */
+	for (i = 0; i < ARRAY_SIZE(chain_inners); i++) {
+		for (inner = chain_inners[i][0]; inner <= chain_inners[i][1]; inner++) {
+			snprintf(desc, sizeof(desc), "sign jump chain over %d sign jumps", inner);
+			sign_jump_chain(inner, 20, CHAIN_NO_CALL, desc);
+			snprintf(desc, sizeof(desc),
+				 "sign jump chain over %d sign jumps and a call", inner);
+			sign_jump_chain(inner, 20, CHAIN_HELPER, desc);
+			snprintf(desc, sizeof(desc),
+				 "sign jump chain over %d sign jumps and a subprog call", inner);
+			sign_jump_chain(inner, 20, CHAIN_SUBPROG, desc);
+		}
+	}
+}
+
 /*
  * Fillers of two and three bytes of native code on x86-64: a 32-bit and a
  * 64-bit move between two low registers, which give a region every length
@@ -2928,6 +3385,54 @@ static void test_same_len_not_converged(void)
 	close(fd);
 }
 
+/*
+ * Short loops back with a compare, a zero test and a sign test, behind enough
+ * helper calls to put them beyond 1MB into the image of the sizing pass
+ */
+static void test_far_back_jump(void)
+{
+	const struct bpf_insn loops[] = {
+		BPF_MOV64_IMM(BPF_REG_1, 0),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1),
+		BPF_JMP_IMM(BPF_JSLT, BPF_REG_1, 3, -2),
+		BPF_MOV64_IMM(BPF_REG_2, 3),
+		BPF_ALU64_IMM(BPF_SUB, BPF_REG_2, 1),
+		BPF_JMP_IMM(BPF_JNE, BPF_REG_2, 0, -2),
+		BPF_MOV64_IMM(BPF_REG_3, -3),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 1),
+		BPF_JMP_IMM(BPF_JSLT, BPF_REG_3, 0, -2),
+		/* in0 + 3 + 0 + 0 */
+		BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_1),
+		BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_2),
+		BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_3),
+		BPF_STX_MEM(BPF_DW, BPF_REG_6, BPF_REG_7, RES),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	const int calls = 52500;
+	struct bpf_insn *insns;
+	int n = 0, i, fd;
+
+	insns = malloc((2 + calls + ARRAY_SIZE(loops)) * sizeof(*insns));
+	if (!ASSERT_OK_PTR(insns, "far back jump"))
+		return;
+	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_1, IN0);
+	for (i = 0; i < calls; i++)
+		insns[n++] = BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32);
+	memcpy(insns + n, loops, sizeof(loops));
+	n += ARRAY_SIZE(loops);
+
+	fd = load_prog(insns, n, "far back jump");
+	free(insns);
+	if (fd < 0)
+		return;
+	ASSERT_GT(jited_len(fd), 0, "far back jump jited");
+	prog_run(fd, 0, 0, 3, "far back jump");
+	prog_run(fd, -1, 0, 2, "far back jump");
+	close(fd);
+}
+
 /*
  * Calls into a subprogram with all five arguments, which clobbers a subset
  * of r6-r9 and uses the deepest stack slot the budget leaves, directly or
@@ -3093,6 +3598,94 @@ static void test_helper_calls(void)
 	close(map_fd);
 }
 
+/*
+ * A tail call with the index from the packet, which the JIT scales and takes
+ * the low 32 bits of: the entries return their index plus one, an empty one
+ * and an index from the array size on TAIL_FALL, the upper 32 bits ignored.
+ */
+#define TAIL_ENTRIES	7
+#define TAIL_FALL	0xfa11
+
+static void test_tail_call(void)
+{
+	static const int filled[] = { 0, 1, 3, 5 };
+	static const struct {
+		__u64 index;
+		__u32 res;
+	} cases[] = {
+		{ 0, 1 }, { 1, 2 }, { 3, 4 }, { 5, 6 },
+		{ 2, TAIL_FALL }, { 4, TAIL_FALL }, { 6, TAIL_FALL },
+		{ TAIL_ENTRIES, TAIL_FALL }, { 0x7fffffff, TAIL_FALL }, { 0xffffffff, TAIL_FALL },
+		{ 1ULL << 32, 1 }, { (1ULL << 32) | 3, 4 }, { (~0ULL << 32) | 5, 6 },
+		{ (~0ULL << 32) | 2, TAIL_FALL }, { ~0ULL, TAIL_FALL },
+	};
+	LIBBPF_OPTS(bpf_prog_load_opts, lopts,
+		.log_buf = log,
+		.log_size = sizeof(log),
+	);
+	struct {
+		__u64 index;
+		__u64 pad;
+	} pkt = {};
+	LIBBPF_OPTS(bpf_test_run_opts, opts,
+		.data_in = &pkt,
+		.data_size_in = sizeof(pkt),
+	);
+	struct bpf_insn insns[16];
+	int map_fd, fd = -1, k, n, i;
+	char desc[64];
+
+	map_fd = bpf_map_create(BPF_MAP_TYPE_PROG_ARRAY, "tail_call", sizeof(__u32),
+				sizeof(__u32), TAIL_ENTRIES, NULL);
+	if (!ASSERT_GE(map_fd, 0, "prog array"))
+		return;
+	for (i = 0; i < ARRAY_SIZE(filled); i++) {
+		k = filled[i];
+		n = 0;
+		insns[n++] = BPF_MOV64_IMM(BPF_REG_0, k + 1);
+		insns[n++] = BPF_EXIT_INSN();
+		snprintf(desc, sizeof(desc), "tail call target %d", k);
+		fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, n, &lopts);
+		if (!ASSERT_GE(fd, 0, desc)) {
+			fprintf(stderr, "%s", log);
+			goto out;
+		}
+		ASSERT_OK(bpf_map_update_elem(map_fd, &k, &fd, BPF_ANY), desc);
+		close(fd);
+	}
+	/* The index from the packet, a call which comes back returns TAIL_FALL */
+	n = 0;
+	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[n++] = BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct xdp_md, data));
+	insns[n++] = BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data_end));
+	insns[n++] = BPF_MOV64_REG(BPF_REG_4, BPF_REG_2);
+	insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 8);
+	insns[n++] = BPF_JMP_REG(BPF_JGT, BPF_REG_4, BPF_REG_3, 5);
+	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_2, 0);
+	insns[n++] = BPF_MOV64_REG(BPF_REG_1, BPF_REG_6);
+	insns[n++] = BPF_RAW_INSN(BPF_LD | BPF_DW | BPF_IMM, BPF_REG_2, BPF_PSEUDO_MAP_FD, 0,
+				  map_fd);
+	insns[n++] = BPF_RAW_INSN(0, 0, 0, 0, 0);
+	insns[n++] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call);
+	insns[n++] = BPF_MOV64_IMM(BPF_REG_0, TAIL_FALL);
+	insns[n++] = BPF_EXIT_INSN();
+	fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, n, &lopts);
+	if (!ASSERT_GE(fd, 0, "tail call")) {
+		fprintf(stderr, "%s", log);
+		goto out;
+	}
+	for (i = 0; i < ARRAY_SIZE(cases); i++) {
+		snprintf(desc, sizeof(desc), "tail call index 0x%llx", cases[i].index);
+		pkt.index = cases[i].index;
+		if (ASSERT_OK(bpf_prog_test_run_opts(fd, &opts), desc))
+			ASSERT_EQ(opts.retval, cases[i].res, desc);
+	}
+out:
+	if (fd >= 0)
+		close(fd);
+	close(map_fd);
+}
+
 void test_jit_insns(void)
 {
 	RUN_TESTS(jit_insns_arena);
@@ -3132,20 +3725,28 @@ void test_jit_insns(void)
 		test_staggered_jumps();
 	if (test__start_subtest("max_jmp"))
 		test_max_jmp();
+	if (test__start_subtest("sign_jumps"))
+		test_sign_jumps();
 	if (test__start_subtest("convergence"))
 		test_convergence();
 	if (test__start_subtest("same_len_not_converged"))
 		test_same_len_not_converged();
+	if (test__start_subtest("far_back_jump"))
+		test_far_back_jump();
 	if (test__start_subtest("calls"))
 		test_calls();
 	if (test__start_subtest("helper_calls"))
 		test_helper_calls();
+	if (test__start_subtest("tail_call"))
+		test_tail_call();
 	if (test__start_subtest("ldst_zero_off"))
 		test_ldst_zero_off();
 	if (test__start_subtest("ldst_offsets"))
 		test_ldst_offsets();
 	if (test__start_subtest("acq_rel"))
 		test_acq_rel();
+	if (test__start_subtest("atomic_ptr_operand"))
+		test_atomic_ptr_operand();
 	if (test__start_subtest("movsx"))
 		test_movsx();
 	if (test__start_subtest("jset_imm"))
diff --git a/tools/testing/selftests/bpf/progs/jit_insns_arena.c b/tools/testing/selftests/bpf/progs/jit_insns_arena.c
index ee591f0dcf95..8f71d907ee57 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,49 @@ struct {
 #define VAL_SUM	0x11224578aaccef10
 #endif
 
+/*
+ * The load-acquire and store-release through __imm_insn(), as clang has
+ * syntax for them only with __BPF_FEATURE_LOAD_ACQ_STORE_REL.
+ */
+#define ATOMIC(SIZE, OP, DST, SRC, OFF)						\
+	{ .code = BPF_STX | BPF_ATOMIC | (SIZE), .dst_reg = DST, .src_reg = SRC,	\
+	  .off = OFF, .imm = 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
+
+#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)
+#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
+
 SEC("syscall")
 __success __retval(0)
 int arena_zero_off(void *ctx)
@@ -106,4 +149,405 @@ int cast_to_user(void *ctx)
 	return res != 0;
 }
 
+/*
+ * Every form of the arena address computation: offsets the add, the sub, the
+ * shifted add and a move take, the end of the second 4K page, the narrow sizes
+ * and immediate stores, each checked through r2 at the same address.
+ */
+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, 0, 1);		\
+	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 += 0xfff;					\
+	*(u8 *)(r7 + 0xfff) = r8;			\
+	r1 = *(u8 *)(r2 + 0);				\
+	r1 ^= 0x88;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = r5;				\
+	r1 = *(u8 *)(r7 + 0xfff);			\
+	r1 ^= 0xef;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 0x1001;					\
+	*(u8 *)(r7 + 0x1001) = r8;			\
+	r1 = *(u8 *)(r2 + 0);				\
+	r1 ^= 0x88;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = r5;				\
+	r1 = *(u8 *)(r7 + 0x1001);			\
+	r1 ^= 0xef;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = 0;				\
+	*(u64 *)(r6 - 0x1000) = r8;			\
+	r1 = *(u64 *)(r7 + 0);				\
+	r1 ^= r8;					\
+	r9 |= r1;					\
+	*(u64 *)(r7 + 0) = r5;				\
+	r1 = *(u64 *)(r6 - 0x1000);			\
+	r1 ^= r5;					\
+	r9 |= r1;					\
+	*(u64 *)(r7 + 0) = 0;				\
+	r2 = r7;					\
+	r2 += 1;					\
+	*(u8 *)(r6 - 0xfff) = r8;			\
+	r1 = *(u8 *)(r2 + 0);				\
+	r1 ^= 0x88;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = r5;				\
+	r1 = *(u8 *)(r6 - 0xfff);			\
+	r1 ^= 0xef;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = 0;				\
+	r6 += 8;					\
+	r2 = r7;					\
+	r2 += 7;					\
+	*(u8 *)(r6 - 0x1001) = r8;			\
+	r1 = *(u8 *)(r2 + 0);				\
+	r1 ^= 0x88;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = r5;				\
+	r1 = *(u8 *)(r6 - 0x1001);			\
+	r1 ^= 0xef;					\
+	r9 |= r1;					\
+	*(u8 *)(r2 + 0) = 0;				\
+	r6 += -8;					\
+	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;					\
+	r1 = *(u64 *)(r7 + 0x2000);			\
+	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, the values written through r2 */
+#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, 0, 1);		\
+	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 results read back through r6 */
+#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, 0, 1);		\
+	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;					\
+	*(u64 *)(r7 + 8) = r8;				\
+	lock *(u64 *)(r7 + 8) += r8;			\
+	r1 = *(u64 *)(r7 + 8);				\
+	r1 ^= 2;					\
+	r9 |= r1;					\
+	r6 += 8;					\
+	lock *(u64 *)(r6 - 8) += r8;			\
+	r1 = *(u64 *)(r7 + 0x1008);			\
+	r1 ^= 0x9a;					\
+	r9 |= r1;					\
+	lock *(u64 *)(r7 + 0x1000) += r8;		\
+	r1 = *(u64 *)(r7 + 0x1000);			\
+	r1 ^= 1;					\
+	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
+static const struct bpf_insn store_rel8 = ATOMIC(BPF_DW, BPF_STORE_REL, 7, 1, 8);
+static const struct bpf_insn load_acq8 = ATOMIC(BPF_DW, BPF_LOAD_ACQ, 2, 7, 8);
+static const struct bpf_insn store_rel0 = ATOMIC(BPF_W, BPF_STORE_REL, 7, 1, 0);
+static const struct bpf_insn load_acq0 = ATOMIC(BPF_B, BPF_LOAD_ACQ, 2, 7, 0);
+static const struct bpf_insn store_rel_hi = ATOMIC(BPF_DW, BPF_STORE_REL, 7, 1, 0x1000);
+static const struct bpf_insn load_acq_lo = ATOMIC(BPF_DW, BPF_LOAD_ACQ, 2, 3, -8);
+
+/*
+ * The load-acquire and store-release at an offset and at zero, checked
+ * through r3 with a plain load and store, and at the offsets of the other
+ * two immediate forms into the second 4K page.
+ */
+SEC("syscall")
+__success __retval(0)
+__naked void arena_acq_rel(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, 0, 1);		\
+	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;					\
+	r3 = r7;					\
+	r3 += 0x1008;					\
+	r1 = 0x9abc;					\
+	.8byte %[store_rel_hi];	/* store_release((u64 *)(r7 + 0x1000), r1) */	\
+	r2 = *(u64 *)(r3 - 8);				\
+	r2 ^= 0x9abc;					\
+	r9 |= r2;					\
+	r1 = 0xdef0;					\
+	*(u64 *)(r3 - 8) = r1;				\
+	.8byte %[load_acq_lo];	/* r2 = load_acquire((u64 *)(r3 - 8)) */	\
+	r2 ^= 0xdef0;					\
+	r9 |= r2;					\
+	r0 = 0;						\
+	if r9 == 0 goto 9f;				\
+	r0 = 1;						\
+9:	exit;						\
+"	:
+	: __imm_addr(arena),
+	  __imm_const(b0, ACQ_B0),
+	  __imm_insn(store_rel8, store_rel8),
+	  __imm_insn(load_acq8, load_acq8),
+	  __imm_insn(store_rel0, store_rel0),
+	  __imm_insn(load_acq0, load_acq0),
+	  __imm_insn(store_rel_hi, store_rel_hi),
+	  __imm_insn(load_acq_lo, load_acq_lo)
+	: __clobber_all);
+}
+#endif /* ARENA_ACQ_REL */
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

Re: [PATCH bpf-next v3 08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Low] arm64, insn: s32 offset truncation in aarch64_insn_gen_adr() for
  ADRP
--

commit cecf5be8cc096127beade0ea92a07c5f62e297a6
Author: Daniel Borkmann <daniel@iogearbox.net>

arm64, insn: Reject invalid and unpredictable operands in the encoders

This commit rejects out-of-range and CONSTRAINED UNPREDICTABLE operands in
several arm64 instruction encoders so they return AARCH64_BREAK_FAULT.

> diff --git a/arch/arm64/lib/insn.c b/arch/arm64/lib/insn.c
> index 48a481aa9656c..87a06bd088115 100644
> --- a/arch/arm64/lib/insn.c
> +++ b/arch/arm64/lib/insn.c

[ ... ]

> @@ -1293,6 +1320,9 @@ u32 aarch64_insn_gen_adr(unsigned long pc, unsigned long addr,
>  	switch (type) {
>  	case AARCH64_INSN_ADR_TYPE_ADR:
>  		insn = aarch64_insn_get_adr_value();
> +		/* The s32 offset would truncate a difference beyond 4GB */
> +		if ((long)(addr - pc) != (s32)(addr - pc))
> +			return AARCH64_BREAK_FAULT;
>  		offset = addr - pc;
>  		break;
>  	case AARCH64_INSN_ADR_TYPE_ADRP:

[Severity: Low]
Can the AARCH64_INSN_ADR_TYPE_ADRP branch right below still truncate into
range when storing the shifted page difference into s32 offset?

arch/arm64/lib/insn.c:aarch64_insn_gen_adr() {
	u32 insn;
	s32 offset;
    ...
	case AARCH64_INSN_ADR_TYPE_ADRP:
		insn = aarch64_insn_get_adrp_value();
		offset = (addr - ALIGN_DOWN(pc, SZ_4K)) >> 12;
		break;
    ...
	if (offset < -SZ_1M || offset >= SZ_1M)
		return AARCH64_BREAK_FAULT;
}

When addr and pc are 16 TiB or more apart, bits [51:32] of the shifted page
offset are dropped before the [-SZ_1M, SZ_1M) range check.  Declaring offset
as long (like label_imm_common()) and casting the difference to long before
shifting in the ADRP case would avoid 32-bit truncation in both branches
without needing the separate s32 comparison.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1794165614.git.daniel@iogearbox.net?part=8

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

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Medium] selftests/bpf: misaligned XDP packet load in test_tail_call()
--

commit 3e5456182ae6e38cbc6f04091b8df4d4e305b794
Author: Daniel Borkmann <daniel@iogearbox.net>

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

This commit extends the BPF JIT instruction selftests with additional test
cases covering compares, bit tests, constant arithmetic, immediates, sign
jumps, arena and PROBE_MEM accesses, and tail calls.

> diff --git a/tools/testing/selftests/bpf/prog_tests/jit_insns.c b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
> index 5fd1c856ded72..0aaab23a2eef8 100644
> --- a/tools/testing/selftests/bpf/prog_tests/jit_insns.c
> +++ b/tools/testing/selftests/bpf/prog_tests/jit_insns.c

[ ... ]

> @@ -3093,6 +3598,94 @@ static void test_helper_calls(void)
>  	close(map_fd);
>  }
>  
> +/*
> + * A tail call with the index from the packet, which the JIT scales and takes
> + * the low 32 bits of: the entries return their index plus one, an empty one
> + * and an index from the array size on TAIL_FALL, the upper 32 bits ignored.
> + */
> +#define TAIL_ENTRIES	7
> +#define TAIL_FALL	0xfa11
> +
> +static void test_tail_call(void)
> +{

[ ... ]

> +	LIBBPF_OPTS(bpf_prog_load_opts, lopts,
> +		.log_buf = log,
> +		.log_size = sizeof(log),
> +	);

[ ... ]

> +	/* The index from the packet, a call which comes back returns TAIL_FALL */
> +	n = 0;
> +	insns[n++] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
> +	insns[n++] = BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct xdp_md, data));
> +	insns[n++] = BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data_end));
> +	insns[n++] = BPF_MOV64_REG(BPF_REG_4, BPF_REG_2);
> +	insns[n++] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 8);
> +	insns[n++] = BPF_JMP_REG(BPF_JGT, BPF_REG_4, BPF_REG_3, 5);
> +	insns[n++] = BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_2, 0);
> +	insns[n++] = BPF_MOV64_REG(BPF_REG_1, BPF_REG_6);
> +	insns[n++] = BPF_RAW_INSN(BPF_LD | BPF_DW | BPF_IMM, BPF_REG_2, BPF_PSEUDO_MAP_FD, 0,
> +				  map_fd);
> +	insns[n++] = BPF_RAW_INSN(0, 0, 0, 0, 0);
> +	insns[n++] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call);
> +	insns[n++] = BPF_MOV64_IMM(BPF_REG_0, TAIL_FALL);
> +	insns[n++] = BPF_EXIT_INSN();
> +	fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, n, &lopts);
> +	if (!ASSERT_GE(fd, 0, "tail call")) {

[Severity: Medium]
As reported by bot+bpf-ci@kernel.org on v2 [1], will the verifier reject
this BPF_DW load from the XDP packet pointer on architectures without
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS?

When strict alignment is enabled and lopts does not set
BPF_F_ANY_ALIGNMENT, check_pkt_ptr_alignment() adds NET_IP_ALIGN (2) to
the packet offset and rejects the 8-byte load at offset 0 with -EACCES,
causing the tail_call subtest to fail on strict-alignment targets.

[1] https://lore.kernel.org/r/eadd9b884e7ca42ebd241f55d6bfd3dd1c9628927b1425e46db2f7197efaeecc@mail.kernel.org

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1794165614.git.daniel@iogearbox.net?part=24

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

[Daniel Borkmann]

On 11/8/26 8:45 PM, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential
> issue to consider:
> - [Medium] selftests/bpf: misaligned XDP packet load in test_tail_call()
[...]
> [Severity: Medium]
> As reported by bot+bpf-ci@kernel.org on v2 [1], will the verifier reject
> this BPF_DW load from the XDP packet pointer on architectures without
> CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS?
https://lore.kernel.org/bpf/41b4e2b6-ea57-4483-8e06-142e09cd73aa@iogearbox.net/

Re: [PATCH bpf-next v3 08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders

[Daniel Borkmann]

On 11/8/26 8:38 PM, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential
> issue to consider:
> - [Low] arm64, insn: s32 offset truncation in aarch64_insn_gen_adr() for
>    ADRP
Not used the the arm64 JIT, but I'll follow-up with a fix for this case as
well once back from travel.

Thanks,
Daniel

Re: [PATCH bpf-next v3 00/24] bpf: Various arm64 BPF JIT improvements

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Sun,  8 Nov 2026 20:26:26 +0100 you wrote:
> This series changes the arm64 BPF JIT to emit shorter and faster native
> code for the instruction patterns that LLVM-compiled programs hit in the
> real world. Every change stays within the lowering of a single BPF
> instruction. This is a similar effort as done recently for x86-64 BPF
> JIT [0].
> 
> On arm64 under vmtest.sh (qemu TCG), test_verifier, test_maps, jit_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.
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3,01/24] bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT
    https://git.kernel.org/bpf/bpf-next/c/0931830cc312
  - [bpf-next,v3,02/24] bpf, arm64: Free the offset table of a subprog in bpf_jit_free
    https://git.kernel.org/bpf/bpf-next/c/0ff09166d3d2
  - [bpf-next,v3,03/24] bpf, arm64: Free the private stack when a pass over the image fails
    https://git.kernel.org/bpf/bpf-next/c/346ea1557fd7
  - [bpf-next,v3,04/24] bpf, arm64: Emit ISB SY in the speculation barriers
    https://git.kernel.org/bpf/bpf-next/c/6a5b148dac53
  - [bpf-next,v3,05/24] arm64, insn: Reject sign extending loads of 64 bits
    https://git.kernel.org/bpf/bpf-next/c/182afb043e7e
  - [bpf-next,v3,06/24] bpf, arm64: Keep the ll/sc atomics address apart from the old value
    https://git.kernel.org/bpf/bpf-next/c/207aac32085d
  - [bpf-next,v3,07/24] bpf, arm64: Measure backward branches from the branch itself
    https://git.kernel.org/bpf/bpf-next/c/1963ac21c7c2
  - [bpf-next,v3,08/24] arm64, insn: Reject invalid and unpredictable operands in the encoders
    https://git.kernel.org/bpf/bpf-next/c/d860f6254d60
  - [bpf-next,v3,09/24] bpf, arm64: Widen the branch offsets before scaling them to bytes
    https://git.kernel.org/bpf/bpf-next/c/592f36e960d0
  - [bpf-next,v3,10/24] arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings
    https://git.kernel.org/bpf/bpf-next/c/1fdba03c72cb
  - [bpf-next,v3,11/24] bpf: Divide by constants via uhmul and shmul in the verifier
    https://git.kernel.org/bpf/bpf-next/c/ffebe8b3e369
  - [bpf-next,v3,12/24] bpf, arm64: Consolidate the load and store emission into a helper
    https://git.kernel.org/bpf/bpf-next/c/1bb1bc5be527
  - [bpf-next,v3,13/24] bpf, arm64: Use the unscaled forms for negative and unaligned offsets
    https://git.kernel.org/bpf/bpf-next/c/6b3c7bde476f
  - [bpf-next,v3,14/24] bpf, arm64: Store zero immediates from the zero register
    https://git.kernel.org/bpf/bpf-next/c/e4939b2a54b9
  - [bpf-next,v3,15/24] bpf, arm64: Zero extend the arena offset in register offset accesses
    https://git.kernel.org/bpf/bpf-next/c/07d4e6947e37
  - [bpf-next,v3,16/24] bpf, arm64: Adjust compares with unencodable immediates by one
    https://git.kernel.org/bpf/bpf-next/c/a33de9a3bba3
  - [bpf-next,v3,17/24] bpf, arm64: Materialize immediates with fewer instructions
    https://git.kernel.org/bpf/bpf-next/c/e79c67bce1a2
  - [bpf-next,v3,18/24] bpf, arm64: Shorten the tail call sequence
    https://git.kernel.org/bpf/bpf-next/c/7dd5500c2c4f
  - [bpf-next,v3,19/24] bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones
    https://git.kernel.org/bpf/bpf-next/c/4835c45b11d2
  - [bpf-next,v3,20/24] bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests
    https://git.kernel.org/bpf/bpf-next/c/abf5971d572c
  - [bpf-next,v3,21/24] bpf, arm64: Multiply by constants with shifts, adds and subs
    https://git.kernel.org/bpf/bpf-next/c/c9c277f5e08f
  - [bpf-next,v3,22/24] selftests/bpf: Let the arm64 private stack check skip the BTI pad
    https://git.kernel.org/bpf/bpf-next/c/75e665d4892b
  - [bpf-next,v3,23/24] selftests/bpf: Test the verifier's division by constants
    https://git.kernel.org/bpf/bpf-next/c/099c2e03f9a0
  - [bpf-next,v3,24/24] selftests/bpf: Extend the JIT instruction tests for arm64 encodings
    https://git.kernel.org/bpf/bpf-next/c/a9fee553d3db

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html