bpf: Explicitly zero-extend R0 after 32-bit cmpxchg
Subsystems (4)
PATCH v3 1/1 bpf: Explicitly zero-extend R0 after 32-bit cmpxchg
As pointed out by Ilya and explained in the new comment, there's a discrepancy between x86 and BPF CMPXCHG semantics: BPF always loads the value from memory into r0, while x86 only does so when r0 and the value in memory are different. The same issue affects s390.
At first this might sound like pure semantics, but it makes a real difference when the comparison is 32-bit, since the load will zero-extend r0/rax.
The fix is to explicitly zero-extend rax after doing such a CMPXCHG. Since this problem affects multiple archs, this is done in the verifier by patching in a BPF_ZEXT_REG instruction after every 32-bit cmpxchg. Any archs that don't need such manual zero-extension can do a look-ahead with insn_is_zext to skip the unnecessary mov.
---
Differences v2->v3[1]:
- Moved patching into fixup_bpf_calls (patch incoming to rename this function)
- Added extra commentary on bpf_jit_needs_zext
- Added check to avoid adding a pointless zext(r0) if there's already one there.
Difference v1->v2[1]: Now solved centrally in the verifier instead of
specifically for the x86 JIT. Thanks to Ilya and Daniel for the suggestions!
[1] v2: https://lore.kernel.org/bpf/[email protected]/T/#t
v1: https://lore.kernel.org/bpf/[email protected]/T/#t
kernel/bpf/core.c | 4 +++ kernel/bpf/verifier.c | 26 +++++++++++++++++++ .../selftests/bpf/verifier/atomic_cmpxchg.c | 25 ++++++++++++++++++ .../selftests/bpf/verifier/atomic_or.c | 26 +++++++++++++++++++ 4 files changed, 81 insertions(+)
kernel/bpf/core.c +4 -0
@@ -2342,6 +2342,10 @@ bool __weak bpf_helper_changes_pkt_data(void *func)/* Return TRUE if the JIT backend wants verifier to enable sub-register usage * analysis code and wants explicit zero extension inserted by verifier. * Otherwise, return FALSE. +* +* The verifier inserts an explicit zero extension after BPF_CMPXCHGs even if +* you don't override this. JITs that don't want these extra insns can detect +* them using insn_is_zext. */ bool __weak bpf_jit_needs_zext (void ) {
kernel/bpf/verifier.c +26 -0
@@ -11662,6 +11662,32 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)continue ; } +/* BPF_CMPXCHG always loads a value into R0, therefore always +* zero-extends. However some archs' equivalent instruction only +* does this load when the comparison is successful. So here we +* add a BPF_ZEXT_REG after every 32-bit CMPXCHG, so that such +* archs' JITs don't need to deal with the issue. Archs that +* don't face this issue may use insn_is_zext to detect and skip +* the added instruction. +*/ +if (insn->code == (BPF_STX |BPF_W |BPF_ATOMIC ) && insn->imm ==BPF_CMPXCHG ) { +struct bpf_insn zext_patch[2 ] = { [1 ] =BPF_ZEXT_REG (BPF_REG_0 ) }; + +if (!memcmp (&insn[1 ], &zext_patch[1 ],sizeof (struct bpf_insn ))) +/* Probably done by opt_subreg_zext_lo32_rnd_hi32. */ +continue ; + + zext_patch[0 ] = *insn; + new_prog =bpf_patch_insn_data (env, i + delta, zext_patch,2 ); +if (!new_prog) +return -ENOMEM ; + + delta +=1 ; + env->prog = prog = new_prog; + insn = new_prog->insnsi + i + delta; +continue ; + } +if (insn->code != (BPF_JMP |BPF_CALL ))continue ;if (insn->src_reg ==BPF_PSEUDO_CALL )
tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c +25 -0
@@ -94,3 +94,28 @@ .result = REJECT, .errstr = "invalid read from stack", }, +{ + "BPF_W cmpxchg should zero top 32 bits", + .insns = { +/* r0 = U64_MAX; */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_0 ,1 ), +/* u64 val = r0; */ +BPF_STX_MEM (BPF_DW ,BPF_REG_10 ,BPF_REG_0 ,-8 ), +/* r0 = (u32)atomic_cmpxchg((u32 *)&val, r0, 1); */ +BPF_MOV32_IMM (BPF_REG_1 ,1 ), +BPF_ATOMIC_OP (BPF_W ,BPF_CMPXCHG ,BPF_REG_10 ,BPF_REG_1 ,-8 ), +/* r1 = 0x00000000FFFFFFFFull; */ +BPF_MOV64_IMM (BPF_REG_1 ,1 ), +BPF_ALU64_IMM (BPF_LSH ,BPF_REG_1 ,32 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_1 ,1 ), +/* if (r0 != r1) exit(1); */ +BPF_JMP_REG (BPF_JEQ ,BPF_REG_0 ,BPF_REG_1 ,2 ), +BPF_MOV32_IMM (BPF_REG_0 ,1 ), +BPF_EXIT_INSN (), +/* exit(0); */ +BPF_MOV32_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, +},
tools/testing/selftests/bpf/verifier/atomic_or.c +26 -0
@@ -75,3 +75,29 @@ }, .result = ACCEPT, }, +{ + "BPF_W atomic_fetch_or should zero top 32 bits", + .insns = { +/* r1 = U64_MAX; */ +BPF_MOV64_IMM (BPF_REG_1 ,0 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_1 ,1 ), +/* u64 val = r0; */ +BPF_STX_MEM (BPF_DW ,BPF_REG_10 ,BPF_REG_1 ,-8 ), +/* r1 = (u32)atomic_sub((u32 *)&val, 1); */ +BPF_MOV32_IMM (BPF_REG_1 ,2 ), +BPF_ATOMIC_OP (BPF_W ,BPF_OR |BPF_FETCH ,BPF_REG_10 ,BPF_REG_1 ,-8 ), +/* r2 = 0x00000000FFFFFFFF; */ +BPF_MOV64_IMM (BPF_REG_2 ,1 ), +BPF_ALU64_IMM (BPF_LSH ,BPF_REG_2 ,32 ), +BPF_ALU64_IMM (BPF_SUB ,BPF_REG_2 ,1 ), +/* if (r2 != r1) exit(1); */ +BPF_JMP_REG (BPF_JEQ ,BPF_REG_2 ,BPF_REG_1 ,2 ), +/* BPF_MOV32_IMM(BPF_REG_0, 1), */ +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ), +BPF_EXIT_INSN (), +/* exit(0); */ +BPF_MOV32_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, +},
base-commit: 45159b27637b0fef6d5ddb86fc7c46b13c77960f --
2.30.0.478.g8a0d178c01-goog
Quoted 44 lines · Brendan Jackman
As pointed out by Ilya and explained in the new comment, there's a discrepancy between x86 and BPF CMPXCHG semantics: BPF always loads the value from memory into r0, while x86 only does so when r0 and the value in memory are different. The same issue affects s390.
At first this might sound like pure semantics, but it makes a real difference when the comparison is 32-bit, since the load will zero-extend r0/rax.
The fix is to explicitly zero-extend rax after doing such a CMPXCHG. Since this problem affects multiple archs, this is done in the verifier by patching in a
BPF_ZEXT_REGinstruction after every 32-bit cmpxchg. Any archs that don't need such manual zero-extension can do a look-ahead withinsn_is_zextto skip the unnecessary mov.Reported-by Ilya Leoshkevich <[email protected]>Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")Signed-off-by Brendan Jackman <[email protected]>---
Differences v2->v3[1]:
- Moved patching intofixup_bpf_calls(patch incoming to rename this function)
- Added extra commentary onbpf_jit_needs_zext
- Added check to avoid adding a pointless zext(r0) if there's already one there.Difference v1->v2[1]: Now solved centrally in the verifier instead of specifically for the x86 JIT. Thanks to Ilya and Daniel for the suggestions!
[1] v2:
https://lore.kernel.org/bpf/[email protected]/T/#t
v1:
https://lore.kernel.org/bpf/[email protected]/T/#tkernel/bpf/core.c | 4 +++ kernel/bpf/verifier.c | 26
+++++++++++++++++++
.../selftests/bpf/verifier/atomic_cmpxchg.c | 25
++++++++++++++++++
.../selftests/bpf/verifier/atomic_or.c | 26
+++++++++++++++++++4 files changed, 81 insertions(+)
[...]
Quoted 26 lines
kernel/bpf/verifier.c +1
-0@@ -11662,6 +11662,32 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) continue; } + /* BPF_CMPXCHG always loads a value into R0,therefore always
+ * zero-extends. However some archs' equivalent instruction only
+ * does this load when the comparison is successful. So here we
+ * add aBPF_ZEXT_REGafter every 32-bit CMPXCHG, so that such
+ * archs' JITs don't need to deal with the issue. Archs that
+ * don't face this issue may useinsn_is_zextto detect and skip
+ * the added instruction.
+ */
+ if (insn->code== (BPF_STX|BPF_W|BPF_ATOMIC) &&insn->imm==BPF_CMPXCHG) {
+ structbpf_insnzext_patch[2] = { [1] =
Quoted 8 lines
BPF_ZEXT_REG(BPF_REG_0)};
+
+ if (!memcmp(&insn[1], &zext_patch[1],sizeof(struct bpf_insn)))
+ /* Probably done byopt_subreg_zext_lo32_rnd_hi32. */
+ continue;
+
Isn't opt_subreg_zext_lo32_rnd_hi32() called after fixup_bpf_calls()?
[...]
Quoted 77 lines · Ilya Leoshkevich
Quoted 44 lines · Brendan Jackman
As pointed out by Ilya and explained in the new comment, there's a discrepancy between x86 and BPF CMPXCHG semantics: BPF always loads the value from memory into r0, while x86 only does so when r0 and the value in memory are different. The same issue affects s390.
At first this might sound like pure semantics, but it makes a real difference when the comparison is 32-bit, since the load will zero-extend r0/rax.
The fix is to explicitly zero-extend rax after doing such a CMPXCHG. Since this problem affects multiple archs, this is done in the verifier by patching in a
BPF_ZEXT_REGinstruction after every 32-bit cmpxchg. Any archs that don't need such manual zero-extension can do a look-ahead withinsn_is_zextto skip the unnecessary mov.Reported-by Ilya Leoshkevich <[email protected]>Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")Signed-off-by Brendan Jackman <[email protected]>---
Differences v2->v3[1]:
- Moved patching intofixup_bpf_calls(patch incoming to rename this
function)
- Added extra commentary onbpf_jit_needs_zext
- Added check to avoid adding a pointless zext(r0) if there's
already one there.Difference v1->v2[1]: Now solved centrally in the verifier instead of
specifically for the x86 JIT. Thanks to Ilya and Daniel for the
suggestions![1] v2:
https://lore.kernel.org/bpf/[email protected]/T/#tv1:https://lore.kernel.org/bpf/[email protected]/T/#t
kernel/bpf/core.c | 4 +++ kernel/bpf/verifier.c | 26 +++++++++++++++++++ .../selftests/bpf/verifier/atomic_cmpxchg.c | 25 ++++++++++++++++++ .../selftests/bpf/verifier/atomic_or.c | 26 +++++++++++++++++++ 4 files changed, 81 insertions(+)[...]
Quoted 28 lines
kernel/bpf/verifier.c +1
-0@@ -11662,6 +11662,32 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) continue; } +/* BPF_CMPXCHG always loads a value into R0, therefore always
+ * zero-extends. However some archs' equivalent
instruction only
+ * does this load when the comparison is successful.
So here we
+ * add aBPF_ZEXT_REGafter every 32-bit CMPXCHG, so
that such
+ * archs' JITs don't need to deal with the issue.
Archs that
+ * don't face this issue may useinsn_is_zextto
detect and skipkernel/bpf/verifier.c +3
-0+* the added instruction. +*/ + if (insn->code == (BPF_STX | BPF_W | BPF_ATOMIC) &&
insn->imm==BPF_CMPXCHG) {
+ structbpf_insnzext_patch[2] = { [1] =BPF_ZEXT_REG(BPF_REG_0)};
+
Quoted 8 lines
kernel/bpf/verifier.c
Quoted 6 lines
+ if (!memcmp(&insn[1], &zext_patch[1],
sizeof(struct bpf_insn)))
+ /* Probably done byopt_subreg_zext_lo32_rnd_hi32. */kernel/bpf/verifier.c +2
-0+continue ; +Isn't
opt_subreg_zext_lo32_rnd_hi32()called afterfixup_bpf_calls()?
Indeed, this check should not be needed.
Quoted 3 lines
[...]
Quoted 88 lines · KP Singh
Quoted 77 lines · Ilya Leoshkevich
Quoted 44 lines · Brendan Jackman
As pointed out by Ilya and explained in the new comment, there's a discrepancy between x86 and BPF CMPXCHG semantics: BPF always loads the value from memory into r0, while x86 only does so when r0 and the value in memory are different. The same issue affects s390.
At first this might sound like pure semantics, but it makes a real difference when the comparison is 32-bit, since the load will zero-extend r0/rax.
The fix is to explicitly zero-extend rax after doing such a CMPXCHG. Since this problem affects multiple archs, this is done in the verifier by patching in a
BPF_ZEXT_REGinstruction after every 32-bit cmpxchg. Any archs that don't need such manual zero-extension can do a look-ahead withinsn_is_zextto skip the unnecessary mov.Reported-by Ilya Leoshkevich <[email protected]>Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")Signed-off-by Brendan Jackman <[email protected]>---
Differences v2->v3[1]:
- Moved patching intofixup_bpf_calls(patch incoming to rename this
function)
- Added extra commentary onbpf_jit_needs_zext
- Added check to avoid adding a pointless zext(r0) if there's
already one there.Difference v1->v2[1]: Now solved centrally in the verifier instead of
specifically for the x86 JIT. Thanks to Ilya and Daniel for the
suggestions![1] v2:
https://lore.kernel.org/bpf/[email protected]/T/#tv1:https://lore.kernel.org/bpf/[email protected]/T/#t
kernel/bpf/core.c | 4 +++ kernel/bpf/verifier.c | 26 +++++++++++++++++++ .../selftests/bpf/verifier/atomic_cmpxchg.c | 25 ++++++++++++++++++ .../selftests/bpf/verifier/atomic_or.c | 26 +++++++++++++++++++ 4 files changed, 81 insertions(+)[...]
Quoted 28 lines
kernel/bpf/verifier.c +1
-0@@ -11662,6 +11662,32 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) continue; } +/* BPF_CMPXCHG always loads a value into R0, therefore always
+ * zero-extends. However some archs' equivalent
instruction only
+ * does this load when the comparison is successful.
So here we
+ * add aBPF_ZEXT_REGafter every 32-bit CMPXCHG, so
that such
+ * archs' JITs don't need to deal with the issue.
Archs that
+ * don't face this issue may useinsn_is_zextto
detect and skipkernel/bpf/verifier.c +3
-0+* the added instruction. +*/ + if (insn->code == (BPF_STX | BPF_W | BPF_ATOMIC) &&
insn->imm==BPF_CMPXCHG) {
+ structbpf_insnzext_patch[2] = { [1] =BPF_ZEXT_REG(BPF_REG_0)};
+Quoted 8 lines
kernel/bpf/verifier.c
Quoted 6 lines
+ if (!memcmp(&insn[1], &zext_patch[1],
sizeof(struct bpf_insn)))
+ /* Probably done byopt_subreg_zext_lo32_rnd_hi32. */kernel/bpf/verifier.c +2
-0+continue ; +Isn't
opt_subreg_zext_lo32_rnd_hi32()called afterfixup_bpf_calls()?
Quoted 1 line
Indeed, this check should not be needed.
Ah yep, right. Do you folks think I should keep the optimisation (i.e. move this memcmp into opt_subreg_zext_lo32_rnd_hi32)? It feels like a bit of a toss-up to me.
Quoted 105 lines · Brendan Jackman
Quoted 104 lines · KP Singh
Quoted 100 lines · Ilya Leoshkevich
Quoted 55 lines · Brendan Jackman
As pointed out by Ilya and explained in the new comment, there's a
discrepancy between x86 and BPF CMPXCHG semantics: BPF always loads
the value from memory into r0, while x86 only does so when r0 and the
value in memory are different. The same issue affects s390.At first this might sound like pure semantics, but it makes a real
difference when the comparison is 32-bit, since the load will zero-extend r0/rax.The fix is to explicitly zero-extend rax after doing such a CMPXCHG. Since this problem affects multiple archs, this is done in
the verifier by patching in aBPF_ZEXT_REGinstruction after every
32-bit cmpxchg. Any archs that don't need such manual zero- extension
can do a look-ahead withinsn_is_zextto skip the unnecessary mov.Reported-by Ilya Leoshkevich <[email protected]>Fixes 5ffa25502b5a ("bpf: Add instructions foratomic_[cmp]xchg")
Signed-off-by Brendan Jackman <[email protected]>---
Differences v2->v3[1]:
- Moved patching intofixup_bpf_calls(patch incoming to rename this
function)
- Added extra commentary onbpf_jit_needs_zext
- Added check to avoid adding a pointless zext(r0) if there's already one there.Difference v1->v2[1]: Now solved centrally in the verifier instead of
specifically for the x86 JIT. Thanks to Ilya and Daniel for the suggestions![1] v2:
https://lore.kernel.org/bpf/[email protected]/T/#t
v1:
https://lore.kernel.org/bpf/[email protected]/T/#tkernel/bpf/core.c | 4 +++ kernel/bpf/verifier.c | 26
+++++++++++++++++++
.../selftests/bpf/verifier/atomic_cmpxchg.c | 25
++++++++++++++++++
.../selftests/bpf/verifier/atomic_or.c | 26
+++++++++++++++++++4 files changed, 81 insertions(+)[...]
Quoted 29 lines
kernel/bpf/verifier.c +1
-0@@ -11662,6 +11662,32 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) continue; } + /* BPF_CMPXCHG always loads a value into R0,therefore always
+ * zero-extends. However some archs' equivalent instruction only
+ * does this load when the comparison is successful.
So here we
+ * add aBPF_ZEXT_REGafter every 32-bit CMPXCHG, so
that such
+ * archs' JITs don't need to deal with the issue. Archs that
+ * don't face this issue may useinsn_is_zextto detect and skip
+ * the added instruction.
+ */
+ if (insn->code== (BPF_STX|BPF_W|BPF_ATOMIC) &&insn->imm==BPF_CMPXCHG) {
+ structbpf_insnzext_patch[2] = { [1] =Quoted 8 lines
BPF_ZEXT_REG(BPF_REG_0)};
+
+ if (!memcmp(&insn[1], &zext_patch[1],sizeof(struct bpf_insn)))
+ /* Probably done byopt_subreg_zext_lo32_rnd_hi32. */
+ continue;
+Isn't
opt_subreg_zext_lo32_rnd_hi32()called afterfixup_bpf_calls()?
Quoted 5 lines
Quoted 1 line
Indeed, this check should not be needed.
Ah yep, right. Do you folks think I should keep the optimisation (i.e. move this memcmp into
opt_subreg_zext_lo32_rnd_hi32)? It feels like a bit of a toss-up to me.
It would be good to have this on s390. In "BPF_W cmpxchg should zero top 32 bits", for example, I get:
7: (c3) r0 = atomic_cmpxchg((u32 *)(r10 -8), r0, r1) 8: (bc) w0 = w0
9: (bc) w0 = w0
With the following adjustment (only briefly tested: survives test_verifier on s390):
kernel/bpf/verifier.c +0 -0
@@ -11677,8 +11677,9 @@ static int fixup_bpf_calls(struct
bpf_verifier_env *env)
if (insn->code == (BPF_STX | BPF_W | BPF_ATOMIC) &&
insn->imm == BPF_CMPXCHG) {
struct bpf_insn zext_patch[2] = { [1] =BPF_ZEXT_REG(BPF_REG_0) };
- if (!memcmp(&insn[1], &zext_patch[1],sizeof(struct bpf_insn)))
- /* Probably done byopt_subreg_zext_lo32_rnd_hi32. */
+ aux = &env->insn_aux_data[i + delta];
+ if (aux->zext_dst && bpf_jit_needs_zext())
+ /* Will be done byopt_subreg_zext_lo32_rnd_hi32(). */
continue;
zext_patch[0] = *insn;it becomes:
7: (c3) r0 = atomic_cmpxchg((u32 *)(r10 -8), r0, r1) 8: (bc) w0 = w0
Moving the check to opt_subreg_zext_lo32_rnd_hi32() is also an option; I don't know which of the two is a better choice.