Skip to contentSkip to conversation

bpf: x86: Explicitly zero-extend rax after 32-bit cmpxchg

PATCH Superseded Brendan Jackman 4 participants 8 messages Feb 15, 2021 – Feb 16, 2021

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

v1 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: x86: Explicitly zero-extend rax 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.

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are implemented), the new mov is superfluous because there's already a mov generated afterwards that will zero-extend r0. We could avoid this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit of correctness (it generates the correct x86 code for a certain set of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")
---
 arch/x86/net/bpf_jit_comp.c                   | 10 +++++++
 .../selftests/bpf/verifier/atomic_cmpxchg.c   | 25 ++++++++++++++++++
 .../selftests/bpf/verifier/atomic_or.c        | 26 +++++++++++++++++++
 3 files changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +10 -0
index 79e7a0ec1da5..7919d5c54164 100644
@@ -834,6 +834,16 @@ static int emit_atomic(u8 **pprog, u8 atomic_op,
 
 	emit_insn_suffix(&prog, dst_reg, src_reg, off);
 
+	if (atomic_op == BPF_CMPXCHG && bpf_size == BPF_W) {
+		/*
+		 * BPF_CMPXCHG unconditionally loads into R0, which means it
+		 * zero-extends 32-bit values. However x86 CMPXCHG doesn't do a
+		 * load if the comparison is successful. Therefore zero-extend
+		 * explicitly.
+		 */
+		emit_mov_reg(&prog, false, BPF_REG_0, BPF_REG_0);
+	}
+
 	*pprog = prog;
 	return 0;
 }
tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c +25 -0
index 2efd8bcf57a1..6e52dfc64415 100644
@@ -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
index 70f982e1f9f0..e0811eb11542 100644
@@ -75,3 +75,29 @@
 	},
 	.result = ACCEPT,
 },
+{
+	"BPF_W atomic 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: 5e1d40b75ed85ecd76347273da17e5da195c3e96

Signature · 1 line
2.30.0.478.g8a0d178c01-goog
Acked-by on v1 1/1
#1 lore raw
Quoted 6 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.

Quoted 8 lines

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are

I think this should be okay and was also suggested by Alexei in:

https://lore.kernel.org/bpf/CAADnVQ+gnQED7WYAw7Vmm5=omngCKYXnmgU_NqPUfESBerH8gQ@mail.gmail.com/

Quoted 11 lines

implemented), the new mov is superfluous because there's already a mov generated afterwards that will zero-extend r0. We could avoid this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit of correctness (it generates the correct x86 code for a certain set of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")

Thanks for fixing this!

maintainer
#2 lore raw
In reply to Brendan Jackman
Quoted 36 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.

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are implemented), the new mov is superfluous because there's already a mov generated afterwards that will zero-extend r0. We could avoid this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit of correctness (it generates the correct x86 code for a certain set of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")
---
  arch/x86/net/bpf_jit_comp.c                   | 10 +++++++
  .../selftests/bpf/verifier/atomic_cmpxchg.c   | 25 ++++++++++++++++++
  .../selftests/bpf/verifier/atomic_or.c        | 26 +++++++++++++++++++
  3 files changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +0 -0
index 79e7a0ec1da5..7919d5c54164 100644
@@ -834,6 +834,16 @@ static int emit_atomic(u8 **pprog, u8 atomic_op,
 

arch/x86/net/bpf_jit_comp.c static int emit_atomic(u8 **pprog, u8 atomic_op, · line 844

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +8 -0
  	emit_insn_suffix(&prog, dst_reg, src_reg, off);
 
+	if (atomic_op == BPF_CMPXCHG && bpf_size == BPF_W) {
+		/*
+		 * BPF_CMPXCHG unconditionally loads into R0, which means it
+		 * zero-extends 32-bit values. However x86 CMPXCHG doesn't do a
+		 * load if the comparison is successful. Therefore zero-extend
+		 * explicitly.
+		 */
+		emit_mov_reg(&prog, false, BPF_REG_0, BPF_REG_0);

How does the situation look on other archs when they need to implement this in future? Mainly asking whether it would be better to instead to move this logic into the verifier instead, so it'll be consistent across all archs.

Quoted 75 lines
arch/x86/net/bpf_jit_comp.c +2 -0
+	}
+
  	*pprog = prog;
  	return 0;
  }
tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c +25 -0
index 2efd8bcf57a1..6e52dfc64415 100644
@@ -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
index 70f982e1f9f0..e0811eb11542 100644
@@ -75,3 +75,29 @@
  	},
  	.result = ACCEPT,
  },
+{
+	"BPF_W atomic 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: 5e1d40b75ed85ecd76347273da17e5da195c3e96

#3 lore raw
Quoted 54 lines · Daniel Borkmann
Quoted 53 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.

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are implemented), the new mov is superfluous because there's already a mov generated afterwards that will zero-extend r0. We could avoid this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit of correctness (it generates the correct x86 code for a certain set of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")

---
  arch/x86/net/bpf_jit_comp.c                   | 10 +++++++ .../selftests/bpf/verifier/atomic_cmpxchg.c   | 25
++++++++++++++++++
  .../selftests/bpf/verifier/atomic_or.c        | 26
+++++++++++++++++++

  3 files changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +0 -0
index 79e7a0ec1da5..7919d5c54164 100644
@@ -834,6 +834,16 @@ static int emit_atomic(u8 **pprog, u8
 atomic_op,


        emit_insn_suffix(&prog, dst_reg, src_reg, off);

+       if (atomic_op == BPF_CMPXCHG && bpf_size == BPF_W) { +               /*
+                * BPF_CMPXCHG unconditionally loads into R0, which means it
+                * zero-extends 32-bit values. However x86 CMPXCHG doesn't do a
+                * load if the comparison is successful. Therefore zero-extend
+                * explicitly.

Quoted 8 lines
Quoted 2 lines

+                */
+               emit_mov_reg(&prog, false, BPF_REG_0, BPF_REG_0);

How does the situation look on other archs when they need to implement this in future?
Mainly asking whether it would be better to instead to move this logic into the verifier
instead, so it'll be consistent across all archs.

I have exactly the same check in my s390 wip patch. So having a common solution would be great.

[...]

maintainer
#4 lore raw
Quoted 64 lines · Ilya Leoshkevich
Quoted 54 lines · Daniel Borkmann
Quoted 53 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.

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are implemented), the new mov is superfluous because there's already a mov generated afterwards that will zero-extend r0. We could avoid this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit of correctness (it generates the correct x86 code for a certain set of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")
---
   arch/x86/net/bpf_jit_comp.c                   | 10 +++++++
   .../selftests/bpf/verifier/atomic_cmpxchg.c   | 25
++++++++++++++++++
   .../selftests/bpf/verifier/atomic_or.c        | 26
+++++++++++++++++++
   3 files changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +3 -0
index 79e7a0ec1da5..7919d5c54164 100644
@@ -834,6 +834,16 @@ static int emit_atomic(u8 **pprog, u8
 atomic_op,
 
         emit_insn_suffix(&prog, dst_reg, src_reg, off);
 
+       if (atomic_op == BPF_CMPXCHG && bpf_size == BPF_W) {
+               /*
+                * BPF_CMPXCHG unconditionally loads into R0, which

means it
+                * zero-extends 32-bit values. However x86 CMPXCHG doesn't do a
+                * load if the comparison is successful. Therefore zero-extend
+                * explicitly.

Quoted 8 lines
Quoted 2 lines

+                */
+               emit_mov_reg(&prog, false, BPF_REG_0, BPF_REG_0);

How does the situation look on other archs when they need to implement this in future?
Mainly asking whether it would be better to instead to move this logic into the verifier
instead, so it'll be consistent across all archs.

Quoted 2 lines

I have exactly the same check in my s390 wip patch. So having a common solution would be great.

We do rewrites for various cases like div/mod handling, perhaps would be best to emit an explicit BPF_MOV32_REG(insn->dst_reg, insn->dst_reg) there, see the fixup_bpf_calls().

#5 lore raw
Quoted 78 lines · Daniel Borkmann
Quoted 77 lines · Ilya Leoshkevich
Quoted 75 lines · Daniel Borkmann
Quoted 60 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.

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.

Note that this doesn't generate totally optimal code: at one of emit_atomic's callsites (where BPF_{AND,OR,XOR} | BPF_FETCH are implemented), the new mov is superfluous because there's already a
mov generated afterwards that will zero-extend r0. We could avoid
this unnecessary mov by just moving the new logic outside of emit_atomic. But I think it's simpler to keep emit_atomic as a unit
of correctness (it generates the correct x86 code for a certain set
of BPF instructions, no further knowledge is needed to use it correctly).

Fixes 5ffa25502b5a ("bpf: Add instructions for

atomic_[cmp]xchg")

---
   arch/x86/net/bpf_jit_comp.c                   | 10 +++++++ .../selftests/bpf/verifier/atomic_cmpxchg.c   | 25
++++++++++++++++++
   .../selftests/bpf/verifier/atomic_or.c        | 26
+++++++++++++++++++

   3 files changed, 61 insertions(+)
arch/x86/net/bpf_jit_comp.c +0 -0
index 79e7a0ec1da5..7919d5c54164 100644
@@ -834,6 +834,16 @@ static int emit_atomic(u8 **pprog, u8
 atomic_op,


         emit_insn_suffix(&prog, dst_reg, src_reg, off);
+       if (atomic_op == BPF_CMPXCHG && bpf_size == BPF_W) { +               /*
+                * BPF_CMPXCHG unconditionally loads into R0, which
means it
+                * zero-extends 32-bit values. However x86 CMPXCHG

Quoted 8 lines

doesn't do a
+                * load if the comparison is successful. Therefore
zero-extend
+                * explicitly.
+                */
+               emit_mov_reg(&prog, false, BPF_REG_0, BPF_REG_0);

How does the situation look on other archs when they need to implement this in future?
Mainly asking whether it would be better to instead to move this logic into the verifier
instead, so it'll be consistent across all archs.

Quoted 8 lines
Quoted 2 lines

I have exactly the same check in my s390 wip patch. So having a common solution would be great.

We do rewrites for various cases like div/mod handling, perhaps would be
best to emit an explicit BPF_MOV32_REG(insn->dst_reg, insn->dst_reg) there,
see the fixup_bpf_calls().

How about BPF_ZEXT_REG? Then arches that don't need this (I think aarch64's instruction always zero-extends) can detect this using insn_is_zext() and skip such insns.

#6 lore raw
Quoted 1 line · Ilya Leoshkevich

[...]

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

How does the situation look on other archs when they need to implement this in future?
Mainly asking whether it would be better to instead to move this logic into the verifier
instead, so it'll be consistent across all archs.

Quoted 8 lines
Quoted 8 lines
Quoted 2 lines

I have exactly the same check in my s390 wip patch. So having a common solution would be great.

We do rewrites for various cases like div/mod handling, perhaps would be
best to emit an explicit BPF_MOV32_REG(insn->dst_reg, insn->dst_reg) there,
see the fixup_bpf_calls().

Agreed, this would be better.

Quoted 5 lines

How about BPF_ZEXT_REG? Then arches that don't need this (I think aarch64's instruction always zero-extends) can detect this using insn_is_zext() and skip such insns.

+1

maintainer
#7 lore raw
Quoted 23 lines · KP Singh
Quoted 1 line · Ilya Leoshkevich

[...]

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

How does the situation look on other archs when they need to implement this in future?
Mainly asking whether it would be better to instead to move this logic into the verifier
instead, so it'll be consistent across all archs.

Quoted 8 lines
Quoted 8 lines
Quoted 2 lines

I have exactly the same check in my s390 wip patch. So having a common solution would be great.

We do rewrites for various cases like div/mod handling, perhaps would be
best to emit an explicit BPF_MOV32_REG(insn->dst_reg, insn->dst_reg) there,
see the fixup_bpf_calls().

Agreed, this would be better.

Quoted 1 line
Quoted 6 lines
Quoted 4 lines

How about BPF_ZEXT_REG? Then arches that don't need this (I think aarch64's instruction always zero-extends) can detect this using insn_is_zext() and skip such insns.

+1

That would be nicer indeed.