Skip to contentSkip to conversation

bpf, x86: Support fetching AND/OR/XOR atomics in arena

PATCH Superseded Puranjay Mohan 3 participants 6 messages Sep 23

Subsystems (5)
x86 Kselftest BPF BPF selftests +1 more subsystems

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

cover bpf, x86: Support fetching AND/OR/XOR atomics in arena

A fetching AND/OR/XOR against arena memory is rejected on x86-64:

BPF_ATOMIC stores into R1 arena is not allowed

x86-64 has no single instruction for these, so the JIT lowers them to a CMPXCHG loop. The loop performs two memory accesses, the load of the old value and the CMPXCHG itself, and either can fault when the arena page goes away. The verifier reserves one exception table entry per instruction, so there was nowhere to record the second one and bpf_jit_supports_insn() refused the three opcodes instead.

x86-64 is the only architecture that needs this. riscv64 has native AMOAND/AMOOR/AMOXOR with fetch, s390 has LAN/LAO/LAX, and arm64 with LSE has LDCLRAL/LDSETAL/LDEORAL, so all three already accept these in an arena. arm64 without LSE rejects every arena RMW atomic and is unaffected either way, since the CMPXCHG that such a lowering would need is not available there in an arena either.

Patch 1 emits the loop with R12-indexed addressing and gives each of the two accesses its own exception table entry. Both entries resume past the whole loop rather than past the faulting instruction, with the fetch destination cleared, so a fault cannot re-enter the loop. The JIT accounts for the extra entry itself by rescanning the instruction stream in bpf_int_jit_compile() before the extable is sized; s390 does the same in bpf_jit_alloc() for its BPF_XCHG lowering.

Patch 2 makes the selftests actually cover this. The existing arena and/or/xor tests discarded the returned value, so clang emitted the non-fetching instruction and the fetching one was never exercised. That was deliberate: commit 2897b1e2a2f4 ("selftests/bpf: Fix arena_atomics failure due to llvm change") switched them to __c11_atomic_fetch_*() with memory_order_relaxed specifically to obtain a non-fetching instruction, because of the limitation patch 1 removes. They go back to plain __sync_fetch_and_*() and check the old value, x86 is dropped from the exclusion list of the uaf test that covers the fault path, and a new fetch_r0 test pins the two register assignments the JIT special-cases.

Puranjay Mohan (2):
bpf, x86: Support fetching AND/OR/XOR atomics in arena selftests/bpf: Test fetching AND/OR/XOR atomics in arena

 arch/x86/net/bpf_jit_comp.c                   | 255 ++++++++++++------
 .../selftests/bpf/prog_tests/arena_atomics.c  |  32 +++
 .../selftests/bpf/progs/arena_atomics.c       | 114 +++++---
 3 files changed, 286 insertions(+), 115 deletions(-)

base-commit: 91f8613d95ad8cd99d8baf094806d1ef98bc6380

Signature · 1 line
2.53.0-Meta
#1 lore raw

PATCH 1/2 bpf, x86: Support fetching AND/OR/XOR atomics in arena

x86-64 has no single instruction for a fetching AND/OR/XOR, so the JIT lowers them to a CMPXCHG loop. That loop could not be used against arena
memory: it contains two memory accesses, the load of the old value and the CMPXCHG itself, either of which can fault when the arena page goes away, while the verifier reserves only one exception table entry per instruction.

Emit the same loop and give each of the two accesses its own exception table entry. Both resume past the whole loop rather than past the faulting instruction alone, with the fetch destination cleared, and both are reported as writes since the BPF instruction is a read-modify-write.

This repurposes the INSN_LEN field of the fixup as a resume distance rather than an instruction length. It stays within its 8 bits because the emitted sequence for one BPF insn is already capped at BPF_MAX_INSN_SIZE.

The extra entry is accounted for in the JIT, by rescanning the instruction stream in bpf_int_jit_compile() before the extable is sized. s390 adjusts aux->num_exentries the same way in bpf_jit_alloc() for its BPF_XCHG lowering. The rescan sits after the extra-pass early exit, so a program is counted exactly once.

The loop needs RAX for CMPXCHG and substitutes BPF_REG_AX for R0 when either operand is R0, so add the matching reg2pt_regs[] entry:
ex_handler_bpf() now has to name that register both as the one holding the arena address and as the one to clear on fault.

---
 arch/x86/net/bpf_jit_comp.c | 255 +++++++++++++++++++++++++-----------
 1 file changed, 179 insertions(+), 76 deletions(-)
arch/x86/net/bpf_jit_comp.c +179 -76
index d4a980140b48d..c601e42e18764 100644
@@ -236,8 +236,17 @@ static const int reg2pt_regs[] = {
 	[BPF_REG_7] = offsetof(struct pt_regs, r13),
 	[BPF_REG_8] = offsetof(struct pt_regs, r14),
 	[BPF_REG_9] = offsetof(struct pt_regs, r15),
+	/* Substituted for R0 by the CMPXCHG loop lowering below. */
+	[BPF_REG_AX] = offsetof(struct pt_regs, r10),
 };
 
+static bool is_atomic_fetch_op(const struct bpf_insn *insn)
+{
+	return insn->imm == (BPF_AND | BPF_FETCH) ||
+	       insn->imm == (BPF_OR | BPF_FETCH) ||
+	       insn->imm == (BPF_XOR | BPF_FETCH);
+}
+
 /*
  * is_ereg() == true if BPF register 'reg' maps to x86-64 r8..r15
  * which need extra byte of encoding.
@@ -1639,6 +1648,68 @@ static int emit_atomic_ld_st_index(u8 **pprog, u32 atomic_op, u32 size,
 	return 0;
 }
 
+/*
+ * A fetching AND/OR/XOR can't be implemented with a single x86 insn, so do a
+ * CMPXCHG loop. @index_reg is X86_REG_R12 for an arena access or -1 otherwise,
+ * and @dst_reg/@src_reg are already substituted for R0 by the caller.
+ *
+ * Both the load and the CMPXCHG can fault when accessing the arena, so their
+ * addresses are handed back in @fault. A fault has to resume at @resume, which
+ * is past the loop and past the move of the value that was never loaded, but
+ * before the R0 restore.
+ */
+static int emit_atomic_fetch_rmw(u8 **pprog, struct bpf_insn *insn, u32 dst_reg,
+				 u32 src_reg, int index_reg, u8 *fault[2],
+				 u8 **resume)
+{
+	bool is64 = BPF_SIZE(insn->code) == BPF_DW;
+	u8 *branch_target, *prog = *pprog;
+	int err;
+
+	branch_target = prog;
+
+	/* Load old value */
+	fault[0] = prog;
+	if (index_reg < 0)
+		emit_ldx(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg, insn->off);
+	else
+		emit_ldx_index(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg,
+			       index_reg, insn->off);
+
+	/*
+	 * Perform the (commutative) operation locally, put the result in
+	 * the AUX_REG.
+	 */
+	emit_mov_reg(&prog, is64, AUX_REG, BPF_REG_0);
+	maybe_emit_mod(&prog, AUX_REG, src_reg, is64);
+	EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
+	      add_2reg(0xC0, AUX_REG, src_reg));
+
+	/* Attempt to swap in new value */
+	fault[1] = prog;
+	if (index_reg < 0)
+		err = emit_atomic_rmw(&prog, BPF_CMPXCHG, dst_reg, AUX_REG,
+				      insn->off, BPF_SIZE(insn->code));
+	else
+		err = emit_atomic_rmw_index(&prog, BPF_CMPXCHG, BPF_SIZE(insn->code),
+					    dst_reg, AUX_REG, index_reg, insn->off);
+	if (WARN_ON(err))
+		return err;
+
+	/* ZF tells us whether we won the race. If it's cleared we need to try again. */
+	EMIT2(X86_JNE, -(prog - branch_target) - 2);
+	/* Return the pre-modification value */
+	emit_mov_reg(&prog, is64, src_reg, BPF_REG_0);
+
+	*resume = prog;
+
+	/* Restore R0 after clobbering RAX */
+	emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
+	*pprog = prog;
+	return 0;
+}
+
 /*
  * Metadata encoding for exception handling in JITed code.
  *
@@ -1652,7 +1723,11 @@ static int emit_atomic_ld_st_index(u8 **pprog, u32 atomic_op, u32 size,
  * | ARENA_ACC | ARENA_WRITE | Unused | ARENA_REG | DST_REG | INSN_LEN |
  * +-----------+-------------+--------+-----------+---------+----------+
  *
- * - INSN_LEN (8 bits): Length of faulting insn (max x86 insn = 15 bytes (fits in 8 bits)).
+ * - INSN_LEN (8 bits): How far past the faulting insn to resume. That is its own length
+ *                      for a single-insn access, but the distance to the end of the whole
+ *                      sequence where one BPF insn became several, as for the CMPXCHG loop
+ *                      of a fetching AND/OR/XOR. Bounded by the BPF_MAX_INSN_SIZE check on
+ *                      ilen below, which is what keeps this inside 8 bits.
  * - DST_REG  (8 bits): Offset of dst_reg from reg2pt_regs[] (max offset = 112 (fits in 8 bits)).
  *                      This is set to DONT_CLEAR if the insn does not read into a register.
  * - ARENA_REG (8 bits): Offset of the register that is used to calculate the
@@ -1707,6 +1782,44 @@ bool ex_handler_bpf(const struct exception_table_entry *x, struct pt_regs *regs)
 	return true;
 }
 
+/*
+ * Record an arena access that may fault. @fault_ip is the address of the
+ * faulting insn in the RO image, @resume_off how far past it execution has to
+ * resume: for a multi-insn lowering that is the end of the whole sequence, not
+ * the end of the one insn.
+ */
+static int emit_arena_exentry(struct bpf_prog *bpf_prog, u8 *image, u8 *rw_image,
+			      int *excnt, u8 *fault_ip, u32 resume_off,
+			      u32 fixup_reg, u32 arena_reg, bool is_write, s16 off)
+{
+	struct exception_table_entry *ex;
+	s64 delta;
+
+	if (!bpf_prog->aux->extable)
+		return 0;
+
+	if (*excnt >= bpf_prog->aux->num_exentries) {
+		pr_err("mem32 extable bug\n");
+		return -EFAULT;
+	}
+	ex = &bpf_prog->aux->extable[(*excnt)++];
+
+	delta = fault_ip - (u8 *)&ex->insn;
+	/* switch ex to rw buffer for writes */
+	ex = (void *)rw_image + ((void *)ex - (void *)image);
+
+	ex->insn = delta;
+	ex->data = EX_TYPE_BPF | FIELD_PREP(DATA_ARENA_OFFSET_MASK, off);
+	ex->fixup = FIELD_PREP(FIXUP_INSN_LEN_MASK, resume_off) |
+		    FIELD_PREP(FIXUP_ARENA_REG_MASK, arena_reg) |
+		    FIELD_PREP(FIXUP_REG_MASK, fixup_reg) |
+		    FIXUP_ARENA_ACCESS;
+	if (is_write)
+		ex->fixup |= FIXUP_ARENA_WRITE;
+
+	return 0;
+}
+
 static void detect_reg_usage(struct bpf_insn *insn, int insn_cnt,
 			     bool *regs_used)
 {
@@ -2584,28 +2697,8 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			}
 populate_extable:
 			{
-				struct exception_table_entry *ex;
-				u8 *_insn = image + proglen + (start_of_ldx - temp);
 				u32 arena_reg, fixup_reg;
 				bool is_write;
-				s64 delta;
-
-				if (!bpf_prog->aux->extable)
-					break;
-
-				if (excnt >= bpf_prog->aux->num_exentries) {
-					pr_err("mem32 extable bug\n");
-					return -EFAULT;
-				}
-				ex = &bpf_prog->aux->extable[excnt++];
-
-				delta = _insn - (u8 *)&ex->insn;
-				/* switch ex to rw buffer for writes */
-				ex = (void *)rw_image + ((void *)ex - (void *)image);
-
-				ex->insn = delta;
-
-				ex->data = EX_TYPE_BPF;
 
 				/*
 				 * src_reg/dst_reg holds the address in the arena region with upper
@@ -2641,14 +2734,12 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 					is_write = true;
 				}
 
-				ex->fixup = FIELD_PREP(FIXUP_INSN_LEN_MASK, prog - start_of_ldx) |
-					    FIELD_PREP(FIXUP_ARENA_REG_MASK, arena_reg) |
-					    FIELD_PREP(FIXUP_REG_MASK, fixup_reg);
-				ex->fixup |= FIXUP_ARENA_ACCESS;
-				if (is_write)
-					ex->fixup |= FIXUP_ARENA_WRITE;
-
-				ex->data |= FIELD_PREP(DATA_ARENA_OFFSET_MASK, insn->off);
+				err = emit_arena_exentry(bpf_prog, image, rw_image, &excnt,
+							 image + proglen + (start_of_ldx - temp),
+							 prog - start_of_ldx, fixup_reg,
+							 arena_reg, is_write, insn->off);
+				if (err)
+					return err;
 			}
 			break;
 
@@ -2800,20 +2891,13 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			fallthrough;
 		case BPF_STX | BPF_ATOMIC | BPF_W:
 		case BPF_STX | BPF_ATOMIC | BPF_DW: {
-			bool is64 = BPF_SIZE(insn->code) == BPF_DW;
 			u32 real_src_reg = src_reg;
 			u32 real_dst_reg = dst_reg;
+			bool is_atomic_fetch = is_atomic_fetch_op(insn);
+			u8 *fault[2], *resume;
 			u8 *old_prog;
-			bool is_atomic_fetch =
-				(insn->imm == (BPF_AND | BPF_FETCH) ||
-				 insn->imm == (BPF_OR | BPF_FETCH) ||
-				 insn->imm == (BPF_XOR | BPF_FETCH));
-			if (is_atomic_fetch) {
-				/*
-				 * Can't be implemented with a single x86 insn.
-				 * Need to do a CMPXCHG loop.
-				 */
 
+			if (is_atomic_fetch) {
 				/* Will need RAX as a CMPXCHG operand so save R0 */
 				old_prog = prog;
 				emit_mov_reg(&prog, true, BPF_REG_AX, BPF_REG_0);
@@ -2834,34 +2918,11 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 				}
 			}
 			if (is_atomic_fetch) {
-				u8 *branch_target = prog;
-				/* Load old value */
-				emit_ldx(&prog, BPF_SIZE(insn->code),
-					 BPF_REG_0, real_dst_reg, insn->off);
-				/*
-				 * Perform the (commutative) operation locally,
-				 * put the result in the AUX_REG.
-				 */
-				emit_mov_reg(&prog, is64, AUX_REG, BPF_REG_0);
-				maybe_emit_mod(&prog, AUX_REG, real_src_reg, is64);
-				EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
-				      add_2reg(0xC0, AUX_REG, real_src_reg));
-				/* Attempt to swap in new value */
-				err = emit_atomic_rmw(&prog, BPF_CMPXCHG,
-						      real_dst_reg, AUX_REG,
-						      insn->off,
-						      BPF_SIZE(insn->code));
-				if (WARN_ON(err))
+				err = emit_atomic_fetch_rmw(&prog, insn, real_dst_reg,
+							    real_src_reg, -1, fault,
+							    &resume);
+				if (err)
 					return err;
-				/*
-				 * ZF tells us whether we won the race. If it's
-				 * cleared we need to try again.
-				 */
-				EMIT2(X86_JNE, -(prog - branch_target) - 2);
-				/* Return the pre-modification value */
-				emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
-				/* Restore R0 after clobbering RAX */
-				emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
 				break;
 			}
 
@@ -2885,6 +2946,43 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			fallthrough;
 		case BPF_STX | BPF_PROBE_ATOMIC | BPF_W:
 		case BPF_STX | BPF_PROBE_ATOMIC | BPF_DW:
+			if (is_atomic_fetch_op(insn)) {
+				u32 real_src_reg = src_reg, real_dst_reg = dst_reg;
+				u8 *fault[2], *resume;
+				int j;
+
+				/* Will need RAX as a CMPXCHG operand so save R0 */
+				emit_mov_reg(&prog, true, BPF_REG_AX, BPF_REG_0);
+				if (src_reg == BPF_REG_0)
+					real_src_reg = BPF_REG_AX;
+				if (dst_reg == BPF_REG_0)
+					real_dst_reg = BPF_REG_AX;
+
+				err = emit_atomic_fetch_rmw(&prog, insn, real_dst_reg,
+							    real_src_reg, X86_REG_R12,
+							    fault, &resume);
+				if (err)
+					return err;
+
+				/*
+				 * The page may be unmapped between the load and the
+				 * CMPXCHG, so both need an entry. Both report a write,
+				 * since the BPF insn is a read-modify-write.
+				 */
+				for (j = 0; j < 2; j++) {
+					err = emit_arena_exentry(bpf_prog, image, rw_image,
+								 &excnt,
+								 image + proglen +
+									 (fault[j] - temp),
+								 resume - fault[j],
+								 reg2pt_regs[real_src_reg],
+								 reg2pt_regs[real_dst_reg],
+								 true, insn->off);
+					if (err)
+						return err;
+				}
+				break;
+			}
 			start_of_ldx = prog;
 
 			if (bpf_atomic_is_load_store(insn))
@@ -4276,6 +4374,21 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 		padding = true;
 		goto skip_init_addrs;
 	}
+
+	/*
+	 * An arena fetching AND/OR/XOR is lowered to a CMPXCHG loop whose load
+	 * and CMPXCHG can both fault, one more entry than the verifier reserved.
+	 * Only reachable on the first pass, so the count is adjusted once.
+	 */
+	for (i = 0; prog->aux->arena && i < prog->len; i++) {
+		const struct bpf_insn *insn = &prog->insnsi[i];
+
+		if (BPF_CLASS(insn->code) == BPF_STX &&
+		    BPF_MODE(insn->code) == BPF_PROBE_ATOMIC &&
+		    is_atomic_fetch_op(insn))
+			prog->aux->num_exentries++;
+	}
+
 	addrs = kvmalloc_objs(*addrs, prog->len + 1);
 	if (!addrs)
 		goto out_addrs;
@@ -4577,16 +4690,6 @@ bool bpf_jit_supports_arena(void)
 
 bool bpf_jit_supports_insn(struct bpf_insn *insn, bool in_arena)
 {
-	if (!in_arena)
-		return true;
-	switch (insn->code) {
-	case BPF_STX | BPF_ATOMIC | BPF_W:
-	case BPF_STX | BPF_ATOMIC | BPF_DW:
-		if (insn->imm == (BPF_AND | BPF_FETCH) ||
-		    insn->imm == (BPF_OR | BPF_FETCH) ||
-		    insn->imm == (BPF_XOR | BPF_FETCH))
-			return false;
-	}
 	return true;
 }
 
Signature · 1 line
2.53.0-Meta
#4 lore raw

PATCH 2/2 selftests/bpf: Test fetching AND/OR/XOR atomics in arena

In reply to Puranjay Mohan

The arena and/or/xor tests never exercised the fetching form of the instruction. Commit 2897b1e2a2f4 ("selftests/bpf: Fix arena_atomics failure due to llvm change") deliberately switched them to __c11_atomic_fetch_*() with memory_order_relaxed, which clang lowers to a non-fetching locked instruction when the result is unused, because x86-64 could not JIT the fetching one against an arena.

It can now, so go back to plain __sync_fetch_and_*() and check the returned old value. Drop the _Atomic declarations and <stdatomic.h> along with the workaround.

Add a fetch_r0 test for the two register assignments the x86 JIT has to special-case, where the operand and where the arena pointer is R0 and BPF_REG_AX is substituted for it. Clang picks its own registers and will not reliably produce either, so spell the instructions out.

Finally drop x86 from the exclusion list of the uaf test, which is what covers the fault path through both of the new exception table entries. arm64 stays excluded: whether its JIT accepts arena RMW atomics depends on LSE being present at run time, which is not a compile-time property.

---
 .../selftests/bpf/prog_tests/arena_atomics.c  |  32 +++++
 .../selftests/bpf/progs/arena_atomics.c       | 114 ++++++++++++------
 2 files changed, 107 insertions(+), 39 deletions(-)
tools/testing/selftests/bpf/prog_tests/arena_atomics.c +32 -0
index 1ad5d03d07adb..13c37b087d6e7 100644
@@ -68,6 +68,9 @@ static void test_and(struct arena_atomics *skel)
 
 	ASSERT_EQ(skel->arena->and64_value, 0x010ull << 32, "and64_value");
 	ASSERT_EQ(skel->arena->and32_value, 0x010, "and32_value");
+
+	ASSERT_EQ(skel->arena->and64_result, 0x110ull << 32, "and64_result");
+	ASSERT_EQ(skel->arena->and32_result, 0x110, "and32_result");
 }
 
 static void test_or(struct arena_atomics *skel)
@@ -85,6 +88,9 @@ static void test_or(struct arena_atomics *skel)
 
 	ASSERT_EQ(skel->arena->or64_value, 0x111ull << 32, "or64_value");
 	ASSERT_EQ(skel->arena->or32_value, 0x111, "or32_value");
+
+	ASSERT_EQ(skel->arena->or64_result, 0x110ull << 32, "or64_result");
+	ASSERT_EQ(skel->arena->or32_result, 0x110, "or32_result");
 }
 
 static void test_xor(struct arena_atomics *skel)
@@ -102,6 +108,9 @@ static void test_xor(struct arena_atomics *skel)
 
 	ASSERT_EQ(skel->arena->xor64_value, 0x101ull << 32, "xor64_value");
 	ASSERT_EQ(skel->arena->xor32_value, 0x101, "xor32_value");
+
+	ASSERT_EQ(skel->arena->xor64_result, 0x110ull << 32, "xor64_result");
+	ASSERT_EQ(skel->arena->xor32_result, 0x110, "xor32_result");
 }
 
 static void test_cmpxchg(struct arena_atomics *skel)
@@ -146,6 +155,27 @@ static void test_xchg(struct arena_atomics *skel)
 	ASSERT_EQ(skel->arena->xchg32_result, 1, "xchg32_result");
 }
 
+static void test_fetch_r0(struct arena_atomics *skel)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, topts);
+	int err, prog_fd;
+
+	/* No need to attach it, just run it directly */
+	prog_fd = bpf_program__fd(skel->progs.fetch_r0);
+	err = bpf_prog_test_run_opts(prog_fd, &topts);
+	if (!ASSERT_OK(err, "test_run_opts err"))
+		return;
+	if (!ASSERT_OK(topts.retval, "test_run_opts retval"))
+		return;
+
+	ASSERT_EQ(skel->arena->fetch_src_r0_value, 0x111, "fetch_src_r0_value");
+	ASSERT_EQ(skel->arena->fetch_src_r0_result, 0x110, "fetch_src_r0_result");
+
+	ASSERT_EQ(skel->arena->fetch_dst_r0_value, 0x111, "fetch_dst_r0_value");
+	ASSERT_EQ(skel->arena->fetch_dst_r0_result, 0x110, "fetch_dst_r0_result");
+	ASSERT_EQ(skel->arena->fetch_dst_r0_readback, 0x111, "fetch_dst_r0_readback");
+}
+
 static void test_uaf(struct arena_atomics *skel)
 {
 	LIBBPF_OPTS(bpf_test_run_opts, topts);
@@ -256,6 +286,8 @@ void serial_test_arena_atomics(void)
 		test_cmpxchg(skel);
 	if (test__start_subtest("xchg"))
 		test_xchg(skel);
+	if (test__start_subtest("fetch_r0"))
+		test_fetch_r0(skel);
 	if (test__start_subtest("uaf"))
 		test_uaf(skel);
 	if (test__start_subtest("load_acquire"))
tools/testing/selftests/bpf/progs/arena_atomics.c +75 -39

172 lines not on this page · raw message

Signature · 1 line
2.53.0-Meta
#2 lore raw
In reply to Puranjay Mohan
this isn't a bug, but does the phrase "the end of the whole sequence" match emit_atomic_fetch_rmw()'s actual behavior? The function comment says the resume point is "past the loop and past the move…
Quoted 19 lines
arch/x86/net/bpf_jit_comp.c +9 -0
index d4a980140b48..c601e42e1876 100644
@@ -236,8 +236,17 @@ static const int reg2pt_regs[] = {
 	[BPF_REG_7] = offsetof(struct pt_regs, r13),
 	[BPF_REG_8] = offsetof(struct pt_regs, r14),
 	[BPF_REG_9] = offsetof(struct pt_regs, r15),
+	/* Substituted for R0 by the CMPXCHG loop lowering below. */
+	[BPF_REG_AX] = offsetof(struct pt_regs, r10),
 };
 
+static bool is_atomic_fetch_op(const struct bpf_insn *insn)
+{
+	return insn->imm == (BPF_AND | BPF_FETCH) ||
+	       insn->imm == (BPF_OR | BPF_FETCH) ||
+	       insn->imm == (BPF_XOR | BPF_FETCH);
+}
+

[ ... ]

Quoted 82 lines
arch/x86/net/bpf_jit_comp.c +67 -1
@@ -1639,6 +1648,68 @@ static int emit_atomic_ld_st_index(u8 **pprog, u32 atomic_op, u32 size,
 	return 0;
 }
 
+/*
+ * A fetching AND/OR/XOR can't be implemented with a single x86 insn, so do a
+ * CMPXCHG loop. @index_reg is X86_REG_R12 for an arena access or -1 otherwise,
+ * and @dst_reg/@src_reg are already substituted for R0 by the caller.
+ *
+ * Both the load and the CMPXCHG can fault when accessing the arena, so their
+ * addresses are handed back in @fault. A fault has to resume at @resume, which
+ * is past the loop and past the move of the value that was never loaded, but
+ * before the R0 restore.
+ */
+static int emit_atomic_fetch_rmw(u8 **pprog, struct bpf_insn *insn, u32 dst_reg,
+				 u32 src_reg, int index_reg, u8 *fault[2],
+				 u8 **resume)
+{
+	bool is64 = BPF_SIZE(insn->code) == BPF_DW;
+	u8 *branch_target, *prog = *pprog;
+	int err;
+
+	branch_target = prog;
+
+	/* Load old value */
+	fault[0] = prog;
+	if (index_reg < 0)
+		emit_ldx(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg, insn->off);
+	else
+		emit_ldx_index(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg,
+			       index_reg, insn->off);
+
+	/*
+	 * Perform the (commutative) operation locally, put the result in
+	 * the AUX_REG.
+	 */
+	emit_mov_reg(&prog, is64, AUX_REG, BPF_REG_0);
+	maybe_emit_mod(&prog, AUX_REG, src_reg, is64);
+	EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
+	      add_2reg(0xC0, AUX_REG, src_reg));
+
+	/* Attempt to swap in new value */
+	fault[1] = prog;
+	if (index_reg < 0)
+		err = emit_atomic_rmw(&prog, BPF_CMPXCHG, dst_reg, AUX_REG,
+				      insn->off, BPF_SIZE(insn->code));
+	else
+		err = emit_atomic_rmw_index(&prog, BPF_CMPXCHG, BPF_SIZE(insn->code),
+					    dst_reg, AUX_REG, index_reg, insn->off);
+	if (WARN_ON(err))
+		return err;
+
+	/* ZF tells us whether we won the race. If it's cleared we need to try again. */
+	EMIT2(X86_JNE, -(prog - branch_target) - 2);
+	/* Return the pre-modification value */
+	emit_mov_reg(&prog, is64, src_reg, BPF_REG_0);
+
+	*resume = prog;
+
+	/* Restore R0 after clobbering RAX */
+	emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
+	*pprog = prog;
+	return 0;
+}
+
 /*
  * Metadata encoding for exception handling in JITed code.
  *
@@ -1652,7 +1723,11 @@ static int emit_atomic_ld_st_index(u8 **pprog, u32 atomic_op, u32 size,
  * | ARENA_ACC | ARENA_WRITE | Unused | ARENA_REG | DST_REG | INSN_LEN |
  * +-----------+-------------+--------+-----------+---------+----------+
  *
- * - INSN_LEN (8 bits): Length of faulting insn (max x86 insn = 15 bytes (fits in 8 bits)).
+ * - INSN_LEN (8 bits): How far past the faulting insn to resume. That is its own length
+ *                      for a single-insn access, but the distance to the end of the whole
+ *                      sequence where one BPF insn became several, as for the CMPXCHG loop
+ *                      of a fetching AND/OR/XOR. Bounded by the BPF_MAX_INSN_SIZE check on
+ *                      ilen below, which is what keeps this inside 8 bits.
  * - DST_REG  (8 bits): Offset of dst_reg from reg2pt_regs[] (max offset = 112 (fits in 8 bits)).
  *                      This is set to DONT_CLEAR if the insn does not read into a register.
  * - ARENA_REG (8 bits): Offset of the register that is used to calculate the

[ ... ]

arch/x86/net/bpf_jit_comp.c bool ex_handler_bpf(const struct exception_table_entry *x, struct pt_regs *regs) · line 1790

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +6 -0
@@ -1707,6 +1782,44 @@ bool ex_handler_bpf(const struct exception_table_entry *x, struct pt_regs *regs)
 	return true;
 }
 
+/*
+ * Record an arena access that may fault. @fault_ip is the address of the
+ * faulting insn in the RO image, @resume_off how far past it execution has to
+ * resume: for a multi-insn lowering that is the end of the whole sequence, not
+ * the end of the one insn.
+ */

this isn't a bug, but does the phrase "the end of the whole sequence" match emit_atomic_fetch_rmw()'s actual behavior? The function comment says the resume point is "past the loop and past the move of the value that was never loaded, but before the R0 restore", and the code sets *resume before the final emit_mov_reg() that restores R0.

If the resume point isn't at the true end of the emitted sequence, would "the end of the rest of the sequence that must be skipped" be clearer than "the end of the whole sequence" in both this comment and the bit-layout comment at line 1726?

Quoted 32 lines
arch/x86/net/bpf_jit_comp.c +32 -0
+static int emit_arena_exentry(struct bpf_prog *bpf_prog, u8 *image, u8 *rw_image,
+			      int *excnt, u8 *fault_ip, u32 resume_off,
+			      u32 fixup_reg, u32 arena_reg, bool is_write, s16 off)
+{
+	struct exception_table_entry *ex;
+	s64 delta;
+
+	if (!bpf_prog->aux->extable)
+		return 0;
+
+	if (*excnt >= bpf_prog->aux->num_exentries) {
+		pr_err("mem32 extable bug\n");
+		return -EFAULT;
+	}
+	ex = &bpf_prog->aux->extable[(*excnt)++];
+
+	delta = fault_ip - (u8 *)&ex->insn;
+	/* switch ex to rw buffer for writes */
+	ex = (void *)rw_image + ((void *)ex - (void *)image);
+
+	ex->insn = delta;
+	ex->data = EX_TYPE_BPF | FIELD_PREP(DATA_ARENA_OFFSET_MASK, off);
+	ex->fixup = FIELD_PREP(FIXUP_INSN_LEN_MASK, resume_off) |
+		    FIELD_PREP(FIXUP_ARENA_REG_MASK, arena_reg) |
+		    FIELD_PREP(FIXUP_REG_MASK, fixup_reg) |
+		    FIXUP_ARENA_ACCESS;
+	if (is_write)
+		ex->fixup |= FIXUP_ARENA_WRITE;
+
+	return 0;
+}
+

[ ... ]

Quoted 52 lines
arch/x86/net/bpf_jit_comp.c +7 -29
@@ -2800,20 +2891,13 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 		fallthrough;
 	case BPF_STX | BPF_ATOMIC | BPF_W:
 	case BPF_STX | BPF_ATOMIC | BPF_DW: {
-		bool is64 = BPF_SIZE(insn->code) == BPF_DW;
 		u32 real_src_reg = src_reg;
 		u32 real_dst_reg = dst_reg;
+		bool is_atomic_fetch = is_atomic_fetch_op(insn);
+		u8 *fault[2], *resume;
 		u8 *old_prog;
-		bool is_atomic_fetch =
-			(insn->imm == (BPF_AND | BPF_FETCH) ||
-			 insn->imm == (BPF_OR | BPF_FETCH) ||
-			 insn->imm == (BPF_XOR | BPF_FETCH));
-		if (is_atomic_fetch) {
-			/*
-			 * Can't be implemented with a single x86 insn.
-			 * Need to do a CMPXCHG loop.
-			 */
 
+		if (is_atomic_fetch) {
 			/* Will need RAX as a CMPXCHG operand so save R0 */
 			old_prog = prog;
 			emit_mov_reg(&prog, true, BPF_REG_AX, BPF_REG_0);
@@ -2834,34 +2918,11 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			}
 		}
 		if (is_atomic_fetch) {
-			u8 *branch_target = prog;
-			/* Load old value */
-			emit_ldx(&prog, BPF_SIZE(insn->code),
-				 BPF_REG_0, real_dst_reg, insn->off);
-			/*
-			 * Perform the (commutative) operation locally,
-			 * put the result in the AUX_REG.
-			 */
-			emit_mov_reg(&prog, is64, AUX_REG, BPF_REG_0);
-			maybe_emit_mod(&prog, AUX_REG, real_src_reg, is64);
-			EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
-			      add_2reg(0xC0, AUX_REG, real_src_reg));
-			/* Attempt to swap in new value */
-			err = emit_atomic_rmw(&prog, BPF_CMPXCHG,
-					      real_dst_reg, AUX_REG,
-					      insn->off,
-					      BPF_SIZE(insn->code));
-			if (WARN_ON(err))
+			err = emit_atomic_fetch_rmw(&prog, insn, real_dst_reg,
+						    real_src_reg, -1, fault,
+						    &resume);
+			if (err)
 				return err;
-			/*

arch/x86/net/bpf_jit_comp.c static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int * · line 2927

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +0 -8
-			 * ZF tells us whether we won the race. If it's
-			 * cleared we need to try again.
-			 */
-			EMIT2(X86_JNE, -(prog - branch_target) - 2);
-			/* Return the pre-modification value */
-			emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
-			/* Restore R0 after clobbering RAX */
-			emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
 			break;
 		}

this isn't a bug, but the non-arena atomic path declares 'u8 *fault[2], *resume;' at the top of the case block and passes them to emit_atomic_fetch_rmw(), yet this branch never builds an exception table entry, so both out-parameters are written and immediately discarded.

Could emit_atomic_fetch_rmw() accept NULL for the @fault and @resume parameters when the caller does not need them, to avoid carrying dead locals in the non-arena case?

Quoted 2 lines
arch/x86/net/bpf_jit_comp.c +0 -0
 		err = emit_atomic(&prog, insn->imm, dst_reg, src_reg, insn->off,

[ ... ]

Quoted 9 lines
arch/x86/net/bpf_jit_comp.c +5 -0
@@ -4276,6 +4374,21 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 		padding = true;
 		goto skip_init_addrs;
 	}
+
+	/*
+	 * An arena fetching AND/OR/XOR is lowered to a CMPXCHG loop whose load
+	 * and CMPXCHG can both fault, one more entry than the verifier reserved.
+	 * Only reachable on the first pass, so the count is adjusted once.

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr · line 4391

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +10 -0
+	 */
+	for (i = 0; prog->aux->arena && i < prog->len; i++) {
+		const struct bpf_insn *insn = &prog->insnsi[i];
+
+		if (BPF_CLASS(insn->code) == BPF_STX &&
+		    BPF_MODE(insn->code) == BPF_PROBE_ATOMIC &&
+		    is_atomic_fetch_op(insn))
+			prog->aux->num_exentries++;
+	}
+

this isn't a bug, but every other loop in this function uses a plain index condition, while this one re-evaluates 'prog->aux->arena' on every iteration.

Would 'if (prog->aux->arena) for (i = 0; i < prog->len; i++)' make it clearer that the arena test is a one-time fast path rather than part of the iteration condition?

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr · line 4394

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +0 -0
 	addrs = kvmalloc_objs(*addrs, prog->len + 1);
 	if (!addrs)
 		goto out_addrs;

[ ... ]

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

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

#3 lore raw
In reply to Puranjay Mohan

arch/x86/net/bpf_jit_comp.c static int emit_atomic_ld_st_index(u8 **pprog, u32 atomic_op, u32 size, · line 1677

Quoted 9 lines · Puranjay Mohan
arch/x86/net/bpf_jit_comp.c +9 -0
+	branch_target = prog;
+
+	/* Load old value */
+	fault[0] = prog;
+	if (index_reg < 0)
+		emit_ldx(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg, insn->off);
+	else
+		emit_ldx_index(&prog, BPF_SIZE(insn->code), BPF_REG_0, dst_reg,
+			       index_reg, insn->off);

can we drop the load in the arena case ?
lock cmpxchg puts the current value into rax when it fails, so the loop can start with whatever R0 has in rax. Then cmpxchg is the only insn that can fault and there is no need for the 2nd extable entry and num_exentries++ in bpf_int_jit_compile().

#5 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Test fetching AND/OR/XOR atomics in arena

In reply to Puranjay Mohan

tools/testing/selftests/bpf/progs/arena_atomics.c int and(const void *ctx) · line 105

Quoted 9 lines · Puranjay Mohan
tools/testing/selftests/bpf/progs/arena_atomics.c +2 -7
-#ifdef __BPF_FEATURE_ATOMIC_MEM_ORDERING
-	__c11_atomic_fetch_and(&and64_value, 0x011ull << 32, memory_order_relaxed);
-	__c11_atomic_fetch_and(&and32_value, 0x011, memory_order_relaxed);
-#else
-	__sync_fetch_and_and(&and64_value, 0x011ull << 32);
-	__sync_fetch_and_and(&and32_value, 0x011);
-#endif
+	and64_result = __sync_fetch_and_and(&and64_value, 0x011ull << 32);
+	and32_result = __sync_fetch_and_and(&and32_value, 0x011);

These were the only tests of non-fetching and/or/xor in arena. Pls keep them and add the fetching ones next to them.