Skip to contentSkip to conversation

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

PATCH Superseded Puranjay Mohan 3 participants 6 messages Sep 25 – Sep 26

Subsystems (6)
x86 Kselftest BPF BPF selftests +2 more subsystems

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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

Changelog:
v1: https://lore.kernel.org/all/[email protected]/
v2: https://lore.kernel.org/all/[email protected]/

Changes in v3:
- Patch 2: keep the 32-bit non-fetching and/or/xor as well. v2 only kept the 64-bit ones, so the 32-bit arena lowering still lost its coverage.
- Patch 2: guard the new uaf asm on __BPF_FEATURE_ADDR_SPACE_CAST. It spells addr_space_cast textually, which needs LLVM 19, while uaf was plain C before and so built with older clang.
- Patch 3: use __sync_fetch_and_or/and in cid.bpf.h and delete the cmpxchg loop, rather than only rewording the comment that justified it. The loop was never the portability fallback it claimed to be: a JIT that rejects a fetching OR or AND in an arena rejects CMPXCHG there too.

Changes in v2:
- Patch 1: drop the initial load in the arena lowering instead of adding a second exception table entry, per Alexei's review. A losing CMPXCHG reloads RAX from memory, so the loop converges without it and the CMPXCHG is left as the only insn that can fault. This removes the entry the verifier had not reserved, and with it the aux->num_exentries rescan in bpf_int_jit_compile() that v1 needed to account for it.
- Patch 1: say in the changelog that the bpf_jit_supports_insn() rejection is dropped, since that is what newly admits these programs, and that the arena form now always executes at least two locked CMPXCHGs.
- Patch 1: rename the shared "mem32 extable bug" message, which the atomic path can now raise, let the non-arena caller pass NULL for the fault and resume out-params, correct the INSN_LEN comment about where the bound is enforced, and drop an unrelated whitespace hunk.
- Patch 2: keep one __c11_atomic_fetch_*() per operation with the result discarded. v1 converted every case to the fetching form, which left the non-fetching lowering with no coverage at all, on every architecture rather than just x86.
- Patch 2: add both R0-aliased forms to the uaf test too. v1 only exercised them on live pages, so the BPF_REG_AX substitution never reached the exception table, which is the part patch 1 actually adds.
- Patch 2: order the new globals so they open fewer holes in .addr_space.1, and correct the comment about why arm64 stays out of the uaf test.
- Patch 3: new.

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 without the initial load. A CMPXCHG that loses the comparison loads the current contents into RAX, so the loop converges from whatever R0 already holds, and the value it stores is computed from RAX, which by definition equalled memory whenever the store happened. That leaves the CMPXCHG as the only insn that can fault, so the one entry the verifier already reserved is enough and nothing has to touch aux->num_exentries. The entry resumes past the whole loop rather than past the faulting instruction, with the fetch destination cleared, so a fault cannot re-enter the loop. The first CMPXCHG compares against an unrelated value, so the arena form executes at least two locked CMPXCHGs every time; the non-arena lowering therefore keeps its load.

Patch 2 makes the selftests 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 to dodge the limitation patch 1 removes. They now check the old value via __sync_fetch_and_*(), while keeping one __c11_atomic_fetch_*() per operation with the result discarded so the non-fetching lowering does not lose its only coverage. A new fetch_r0 test pins the two register assignments the JIT special-cases, and both also go into the uaf test, since the BPF_REG_AX substitution only reaches the exception table when such an access faults. x86 is dropped from the uaf exclusion list.

Patch 3 drops the hand-rolled cmpxchg loop in sched_ext's cid.bpf.h, which only existed because of the x86 restriction patch 1 removes, and uses the fetching atomics directly. The loop was not a portability fallback either:
arm64 without LSE rejects every arena read-modify-write including CMPXCHG, so it does not work there, and riscv without Zacas rejects only CMPXCHG, so it is strictly worse than a fetching OR there. Note the arena form costs an extra locked CMPXCHG on x86-64 per patch 1, and cmask_set()/cmask_clear() pay for a fetch whose result they discard.

Puranjay Mohan (3):
bpf, x86: Support fetching AND/OR/XOR atomics in arena selftests/bpf: Test fetching AND/OR/XOR atomics in arena
sched_ext: Use fetching atomics for cmask instead of a cmpxchg loop

 arch/x86/net/bpf_jit_comp.c                   | 236 ++++++++++++------
 tools/sched_ext/include/scx/cid.bpf.h         |  79 +-----
 .../selftests/bpf/prog_tests/arena_atomics.c  |  41 +++
 .../selftests/bpf/progs/arena_atomics.c       | 167 ++++++++++---
 4 files changed, 337 insertions(+), 186 deletions(-)

base-commit: 7af653d4ebf8e2e17e288715cd67ccf7845f4631

Signature · 1 line
2.53.0-Meta
#1 lore raw

PATCH v3 1/3 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. bpf_jit_supports_insn() therefore rejected the three opcodes and such programs failed to load with

BPF_ATOMIC stores into R1 arena is not allowed

Emit the loop without the initial load. A CMPXCHG that loses the comparison loads the current contents into RAX, so the loop converges from whatever R0 already holds, and the value it stores is computed from RAX, which by definition equalled memory whenever the store happened. That leaves the CMPXCHG as the only insn that can fault, so one exception table entry is enough and the count the verifier already reserved still matches. Drop the bpf_jit_supports_insn() rejection that gated all this.

The first CMPXCHG compares against an unrelated value, so barring coincidence it always loses and the arena form executes at least two locked CMPXCHGs every time. A losing locked CMPXCHG is still a full read-modify-write, so this is a real steady-state cost rather than an occasional retry, which is why the non-arena lowering keeps its load.

The entry resumes past the whole loop rather than past the faulting instruction alone, with the fetch destination cleared, so a fault cannot re-enter the loop. This repurposes the INSN_LEN field of the fixup as a resume distance rather than an instruction length; a sequence long enough to overflow its 8 bits would first have to exceed BPF_MAX_INSN_SIZE, which do_jit() rejects before the image is used.

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 | 236 ++++++++++++++++++++++++------------
 1 file changed, 160 insertions(+), 76 deletions(-)
arch/x86/net/bpf_jit_comp.c +160 -76
index 6c7a0578760e7..570ee93a969a9 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.
@@ -1679,6 +1688,74 @@ 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.
+ *
+ * For an arena access the CMPXCHG is the only insn that can fault; its address
+ * is handed back in @fault. A fault has to resume at @resume, which is past the
+ * loop and past the move that delivers the old value, but before the R0
+ * restore. Both are NULL for the non-arena case, which needs no fixup.
+ */
+static int emit_atomic_fetch_rmw(u8 **pprog, struct bpf_insn *insn, u32 dst_reg,
+				 u32 src_reg, int index_reg, u8 **fault,
+				 u8 **resume)
+{
+	bool is64 = BPF_SIZE(insn->code) == BPF_DW;
+	u8 *branch_target, *prog = *pprog;
+	int err;
+
+	branch_target = prog;
+
+	/*
+	 * Load old value. The arena case skips it and lets the loop start from
+	 * whatever R0 happens to hold: a CMPXCHG that loses the comparison
+	 * loads the current contents into RAX, so the loop converges, and the
+	 * value it stores is computed from RAX, which by definition equalled
+	 * memory whenever the store happened. That leaves the CMPXCHG as the
+	 * only insn that can fault, which is worth an extra iteration here to
+	 * keep this to a single exception table entry.
+	 */
+	if (index_reg < 0)
+		emit_ldx(&prog, BPF_SIZE(insn->code), BPF_REG_0, 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, src_reg, is64);
+	EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
+	      add_2reg(0xC0, AUX_REG, src_reg));
+
+	/* Attempt to swap in new value */
+	if (fault)
+		*fault = 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);
+
+	if (resume)
+		*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.
  *
@@ -1692,7 +1769,12 @@ 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. A sequence long enough to overflow this
+ *                      field would first have to exceed BPF_MAX_INSN_SIZE, which do_jit()
+ *                      rejects with -EFAULT before the image is used.
  * - 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
@@ -1747,6 +1829,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("arena 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)
 {
@@ -2624,28 +2744,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
@@ -2681,14 +2781,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;
 
@@ -2840,20 +2938,12 @@ 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 *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);
@@ -2874,34 +2964,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, NULL,
+							    NULL);
+				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;
 			}
 
@@ -2925,6 +2992,33 @@ 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, *resume;
+
+				/* 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;
+
+				err = emit_arena_exentry(bpf_prog, image, rw_image, &excnt,
+							 image + proglen + (fault - temp),
+							 resume - fault,
+							 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))
@@ -4669,16 +4763,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
reviewer
#2 lore raw

Hello, Puranjay.

Quoted 5 lines · Puranjay Mohan

The first CMPXCHG compares against an unrelated value, so barring coincidence it always loses and the arena form executes at least two locked CMPXCHGs every time. A losing locked CMPXCHG is still a full read-modify-write, so this is a real steady-state cost rather than an occasional retry, which is why the non-arena lowering keeps its load.

I'd prefer the v1 lowering with the load and the second extable entry. The extra locked CMPXCHG is the common case rather than a retry, so on x86 the fetching insn ends up more expensive than the load + cmpxchg loop that BPF programs hand-roll today, e.g. the cmask helpers in tools/sched_ext/include/scx/cid.bpf.h which are being converted to the fetching builtins. As is, we'd likely keep the loop on x86 and only use the fetching atomics on the other archs, which defeats the purpose. Andrea raised the same concern on the scx side:

https://github.com/sched-ext/scx/pull/3839#pullrequestreview-5318408089

The second extable entry is some added complexity in the JIT but that's paid once, while the extra CMPXCHG is paid on every operation.

Thanks.

--
tejun

#3 lore raw

PATCH v3 2/3 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 check the returned old value with __sync_fetch_and_*(). Keep a __c11_atomic_fetch_*() of each width per operation with the result
discarded: that spelling is what selects the non-fetching insn, which would otherwise lose its only coverage, on every architecture rather than just x86. Compiling the prog before and after confirms the split: 6 non- fetching and no fetching arena and/or/xor before, 6 and 22 after.

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. Add both forms to the uaf test as well, since the substitution only reaches the exception table when such an access faults.

Both spell addr_space_cast textually, which needs LLVM 19, so uaf gains the __BPF_FEATURE_ADDR_SPACE_CAST guard that every other textual use in the file already has. It was plain C before and built on older clang.

Finally drop x86 from the exclusion list of the uaf test, which is what covers the fault path through the new exception table entry.

---
 .../selftests/bpf/prog_tests/arena_atomics.c  |  41 +++++
 .../selftests/bpf/progs/arena_atomics.c       | 167 ++++++++++++++----
 2 files changed, 169 insertions(+), 39 deletions(-)
tools/testing/selftests/bpf/prog_tests/arena_atomics.c +41 -0
index 1ad5d03d07adb..2a535815bf1dc 100644
@@ -68,6 +68,12 @@ 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");
+
+	ASSERT_EQ(skel->arena->and64_noreturn_value, 0x010ull << 32, "and64_noreturn_value");
+	ASSERT_EQ(skel->arena->and32_noreturn_value, 0x010, "and32_noreturn_value");
 }
 
 static void test_or(struct arena_atomics *skel)
@@ -85,6 +91,12 @@ 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");
+
+	ASSERT_EQ(skel->arena->or64_noreturn_value, 0x111ull << 32, "or64_noreturn_value");
+	ASSERT_EQ(skel->arena->or32_noreturn_value, 0x111, "or32_noreturn_value");
 }
 
 static void test_xor(struct arena_atomics *skel)
@@ -102,6 +114,12 @@ 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");
+
+	ASSERT_EQ(skel->arena->xor64_noreturn_value, 0x101ull << 32, "xor64_noreturn_value");
+	ASSERT_EQ(skel->arena->xor32_noreturn_value, 0x101, "xor32_noreturn_value");
 }
 
 static void test_cmpxchg(struct arena_atomics *skel)
@@ -146,6 +164,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 +295,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 +128 -39

231 lines not on this page · raw message

Signature · 1 line
2.53.0-Meta
#4 lore raw

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

Can this ordering still build on clang-17?
Quoted 4 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +0 -0
index 73bc2b835f3f..3beca5eab387 100644

[ ... ]

Quoted 15 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +7 -4
@@ -91,13 +91,22 @@ int sub(const void *ctx)
 	return 0;
 }
 
-#ifdef __BPF_FEATURE_ATOMIC_MEM_ORDERING
-_Atomic __u64 __arena_global and64_value = (0x110ull << 32);
-_Atomic __u32 __arena_global and32_value = 0x110;
-#else
+/*
+ * Discarding the result of an atomic RMW is what selects the non-fetching
+ * insn, so keep one of each width per operation to cover that lowering too.
+ * Declared together rather than per operation to keep them in one place.
+ */
+_Atomic __u64 __arena_global and64_noreturn_value = (0x110ull << 32);
+_Atomic __u64 __arena_global or64_noreturn_value = (0x110ull << 32);

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

Quoted 10 lines
tools/testing/selftests/bpf/progs/arena_atomics.c +7 -1
+_Atomic __u64 __arena_global xor64_noreturn_value = (0x110ull << 32);
+_Atomic __u32 __arena_global and32_noreturn_value = 0x110;
+_Atomic __u32 __arena_global or32_noreturn_value = 0x110;
+_Atomic __u32 __arena_global xor32_noreturn_value = 0x110;
+
 __u64 __arena_global and64_value = (0x110ull << 32);
+__u64 __arena_global and64_result = 0;
 __u32 __arena_global and32_value = 0x110;
-#endif
+__u32 __arena_global and32_result = 0;

Can this ordering still build on clang-17?

The file's existing clang-17 guard (lines 379-402) says clang-17 crashes if the .addr_space.1 ELF section has holes, and works around this by declaring variables as 64-bit. Before __BPF_FEATURE_ADDR_SPACE_CAST is defined (clang 19+), __arena_global expands to SEC(".addr_space.1"), so all of these globals go into that section.

Before this commit, the layout had no holes: add/sub (96 bytes), then and32/and64/or32/or64/xor64/xor32 filled 96-132 continuously, then cmpxchg32 x3 at 132-144 and cmpxchg64 at 144.

After this commit, the three _Atomic __u64 noreturn values fill 96-120 and the three _Atomic __u32 noreturn values fill 120-132. Then and64_value needs 8-byte alignment, creating a 4-byte hole at 132-136. The and/or/xor blocks (u64 value, u64 result, u32 value, u32 result) fill 136-208. cmpxchg32 x3 fill 208-220, then cmpxchg64_value needs 8-byte alignment, creating a second 4-byte hole at 220-224.

clang-17's BPF backend pads these holes with code nops. BPF writeNopData only handles multiples of 8, so the build fails with 'fatal error: error in backend: unable to write nop sequence of 4 bytes'. This is the same failure the x86_64-llvm-17 CI job hit when load-acquire tests were added (see lore message [email protected]; fixed only in LLVM f27c4903c43b, clang 18+).

Could the __u32 globals be reordered to avoid these holes? For example, moving xor32_noreturn_value from the grouped block to just after xor32_result, next to the three cmpxchg32 values, would give runs of 2 and 6 u32 values instead of 3 + 3, eliminating both holes. Alternatively, the existing clang-17 pattern (declaring them as 64-bit) could be used.

[ ... ]

---
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/36144954909

#5 lore raw

PATCH v3 3/3 sched_ext: Use fetching atomics for cmask instead of a cmpxchg loop

In reply to Puranjay Mohan

cid.bpf.h implements cmask_set(), cmask_clear() and the test_and_ variants with a bounded cmpxchg loop, because the x86 BPF JIT used to reject BPF_OR | BPF_FETCH and BPF_AND | BPF_FETCH on arena pointers.

It no longer does, and the loop was never the portability fallback its comment claimed. A JIT that turns down a fetching OR or AND in an arena turns down CMPXCHG there too: arm64 without LSE rejects every arena read-modify-write, so the loop does not work there either. riscv without Zacas is the other way round and rejects only CMPXCHG, which makes the loop strictly worse than the fetching insn on that configuration.

Native fetching OR and AND are therefore accepted everywhere the loop was, and in one place where it was not. Use them, and drop CMASK_CAS_TRIES along with the error paths that could only be reached from a loop that no longer exists.

---
 tools/sched_ext/include/scx/cid.bpf.h | 79 +++------------------------
 1 file changed, 8 insertions(+), 71 deletions(-)
tools/sched_ext/include/scx/cid.bpf.h +8 -71
index 69fb4e97bc771..d0d4cea19e29f 100644
@@ -3,8 +3,8 @@
  * BPF-side helpers for cids and cmasks. See kernel/sched/ext/cid.h for the
  * authoritative layout and semantics. The BPF-side helpers use the cmask_*
  * naming (no scx_ prefix); cmask is the SCX bitmap type so the prefix is
- * redundant in BPF code. Atomics use __sync_val_compare_and_swap and every
- * helper is inline (no .c counterpart).
+ * redundant in BPF code. Atomics use the __sync_* builtins and every helper
+ * is inline (no .c counterpart).
  *
  * Included by scx/common.bpf.h; don't include directly.
  *
@@ -129,101 +129,38 @@ static __always_inline bool cmask_test(u32 cid, const struct scx_cmask __arena *
 	return *__cmask_word(cid, m) & BIT_U64(cid & 63);
 }
 
-/*
- * x86 BPF JIT rejects BPF_OR | BPF_FETCH and BPF_AND | BPF_FETCH on arena
- * pointers (see bpf_jit_supports_insn() in arch/x86/net/bpf_jit_comp.c). Only
- * BPF_CMPXCHG / BPF_XCHG / BPF_ADD with FETCH are allowed. Implement
- * test_and_{set,clear} and the atomic set/clear via a cmpxchg loop.
- *
- * CMASK_CAS_TRIES is sized so exhausting it means seconds of real spinning
- * on one word - past any plausible contention. Abort hard.
- */
-#define CMASK_CAS_TRIES		(1U << 23)
-
 static __always_inline void cmask_set(u32 cid, struct scx_cmask __arena *m)
 {
-	u64 __arena *w;
-	u64 bit, old, new;
-	u32 i;
-
 	if (!__cmask_contains(cid, m))
 		return;
-	w = __cmask_word(cid, m);
-	bit = BIT_U64(cid & 63);
-	bpf_for(i, 0, CMASK_CAS_TRIES) {
-		old = *w;
-		if (old & bit)
-			return;
-		new = old | bit;
-		if (__sync_val_compare_and_swap(w, old, new) == old)
-			return;
-	}
-	scx_bpf_error("cmask_set CAS exhausted at cid %u", cid);
+	__sync_fetch_and_or(__cmask_word(cid, m), BIT_U64(cid & 63));
 }
 
 static __always_inline void cmask_clear(u32 cid, struct scx_cmask __arena *m)
 {
-	u64 __arena *w;
-	u64 bit, old, new;
-	u32 i;
-
 	if (!__cmask_contains(cid, m))
 		return;
-	w = __cmask_word(cid, m);
-	bit = BIT_U64(cid & 63);
-	bpf_for(i, 0, CMASK_CAS_TRIES) {
-		old = *w;
-		if (!(old & bit))
-			return;
-		new = old & ~bit;
-		if (__sync_val_compare_and_swap(w, old, new) == old)
-			return;
-	}
-	scx_bpf_error("cmask_clear CAS exhausted at cid %u", cid);
+	__sync_fetch_and_and(__cmask_word(cid, m), ~BIT_U64(cid & 63));
 }
 
 static __always_inline bool cmask_test_and_set(u32 cid, struct scx_cmask __arena *m)
 {
-	u64 __arena *w;
-	u64 bit, old, new;
-	u32 i;
+	u64 bit;
 
 	if (!__cmask_contains(cid, m))
 		return false;
-	w = __cmask_word(cid, m);
 	bit = BIT_U64(cid & 63);
-	bpf_for(i, 0, CMASK_CAS_TRIES) {
-		old = *w;
-		if (old & bit)
-			return true;
-		new = old | bit;
-		if (__sync_val_compare_and_swap(w, old, new) == old)
-			return false;
-	}
-	scx_bpf_error("cmask_test_and_set CAS exhausted at cid %u", cid);
-	return false;
+	return __sync_fetch_and_or(__cmask_word(cid, m), bit) & bit;
 }
 
 static __always_inline bool cmask_test_and_clear(u32 cid, struct scx_cmask __arena *m)
 {
-	u64 __arena *w;
-	u64 bit, old, new;
-	u32 i;
+	u64 bit;
 
 	if (!__cmask_contains(cid, m))
 		return false;
-	w = __cmask_word(cid, m);
 	bit = BIT_U64(cid & 63);
-	bpf_for(i, 0, CMASK_CAS_TRIES) {
-		old = *w;
-		if (!(old & bit))
-			return false;
-		new = old & ~bit;
-		if (__sync_val_compare_and_swap(w, old, new) == old)
-			return true;
-	}
-	scx_bpf_error("cmask_test_and_clear CAS exhausted at cid %u", cid);
-	return false;
+	return __sync_fetch_and_and(__cmask_word(cid, m), ~bit) & bit;
 }
 
 static __always_inline void __cmask_set(u32 cid, struct scx_cmask __arena *m)
Signature · 1 line
2.53.0-Meta