[PATCH bpf-next 0/6] bpf: verifier: stop emitting zext for LDX

[PATCH bpf-next 0/6] bpf: verifier: stop emitting zext for LDX

[Puranjay Mohan]

All 64-bit architectures that support the BPF JIT do LDX + zero extension
with a single CPU instruction. Some 64-bit architectures like riscv64,
s390, mips64, etc. have bpf_jit_needs_zext() -> true. This means although
these architectures do LDX + zero extension with a single CPU instruction,
the verifier emits extra zero extension instructions after LDX | B/H/W.

After a discussion about this in [1], it was decided that the verifier
should not emit zext instructions for LDX and all JITs that can't do a LDX
+ zero extension with a single instruction should emit two instructions by
default for LDX.

All 32 bit JITs checked for ctx->prog->aux->verifier_zext and did not do
explicit zero extension after LDX if this is set by the verifier.

This patch series changes all applicable 32-bit JITs to always do a zero
extension after LDX without checking ctx->prog->aux->verifier_zext.

The last patch modifies the verifier to always mark the destination of LDX
as 64 bit which in turn stops the verifier from emitting zext after LDX.

These changes have not been tested because I don't have the hardware to do
so, I would request the JIT maintainers to help me test this. Especially,
the powerpc32 JTI where amount of code change is more.

[1] https://lore.kernel.org/all/CANk7y0j2f-gPgZwd+YfTL71-6wfvky+f=kBC_ccqsS0EHAysyA@mail.gmail.com/

Puranjay Mohan (6):
  bpf, riscv32: Always zero extend for LDX with B/W/H
  bpf, x86-32: Always zero extend for LDX with B/W/H
  bpf, parisc32: Always zero extend for LDX with B/W/H
  bpf, powerpc32: Always zero extend for LDX
  bpf, arm32: Always zero extend for LDX with B/H/W
  bpf, verifier: always mark destination of LDX as 64-bit

 arch/arm/net/bpf_jit_32.c         |  9 +++------
 arch/parisc/net/bpf_jit_comp32.c  |  9 +++------
 arch/powerpc/net/bpf_jit_comp32.c | 25 ++++++++-----------------
 arch/riscv/net/bpf_jit_comp32.c   |  9 +++------
 arch/x86/net/bpf_jit_comp32.c     |  2 --
 kernel/bpf/verifier.c             |  4 +---
 6 files changed, 18 insertions(+), 40 deletions(-)

-- 
2.39.2

[PATCH bpf-next 1/6] bpf, riscv32: Always zero extend for LDX with B/W/H

[Puranjay Mohan]

The JITs should not depend on the verifier for zero extending the upper
32 bits of the destination register when loading a byte, half-word, or
word.

A following patch will make the verifier stop patching zext instructions
after LDX.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 arch/riscv/net/bpf_jit_comp32.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp32.c b/arch/riscv/net/bpf_jit_comp32.c
index 529a83b85c1c..8f8255519ba1 100644
--- a/arch/riscv/net/bpf_jit_comp32.c
+++ b/arch/riscv/net/bpf_jit_comp32.c
@@ -847,18 +847,15 @@ static int emit_load_r64(const s8 *dst, const s8 *src, s16 off,
 	switch (size) {
 	case BPF_B:
 		emit(rv_lbu(lo(rd), 0, RV_REG_T0), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
+		emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
 		break;
 	case BPF_H:
 		emit(rv_lhu(lo(rd), 0, RV_REG_T0), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
+		emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
 		break;
 	case BPF_W:
 		emit(rv_lw(lo(rd), 0, RV_REG_T0), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
+		emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
 		break;
 	case BPF_DW:
 		emit(rv_lw(lo(rd), 0, RV_REG_T0), ctx);
-- 
2.39.2

[PATCH bpf-next 2/6] bpf, x86-32: Always zero extend for LDX with B/W/H

[Puranjay Mohan]

The JITs should not depend on the verifier for zero extending the upper
32 bits of the destination register when loading a byte, half-word, or
word.

A following patch will make the verifier stop patching zext instructions
after LDX.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 arch/x86/net/bpf_jit_comp32.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp32.c b/arch/x86/net/bpf_jit_comp32.c
index 429a89c5468b..aef9183ff107 100644
--- a/arch/x86/net/bpf_jit_comp32.c
+++ b/arch/x86/net/bpf_jit_comp32.c
@@ -2050,8 +2050,6 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 			case BPF_B:
 			case BPF_H:
 			case BPF_W:
-				if (bpf_prog->aux->verifier_zext)
-					break;
 				if (dstk) {
 					EMIT3(0xC7, add_1reg(0x40, IA32_EBP),
 					      STACK_VAR(dst_hi));
-- 
2.39.2

[PATCH bpf-next 3/6] bpf, parisc32: Always zero extend for LDX with B/W/H

[Puranjay Mohan]

The JITs should not depend on the verifier for zero extending the upper
32 bits of the destination register when loading a byte, half-word, or
word.

A following patch will make the verifier stop patching zext instructions
after LDX.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 arch/parisc/net/bpf_jit_comp32.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/arch/parisc/net/bpf_jit_comp32.c b/arch/parisc/net/bpf_jit_comp32.c
index 5ff0cf925fe9..cc3972d6c971 100644
--- a/arch/parisc/net/bpf_jit_comp32.c
+++ b/arch/parisc/net/bpf_jit_comp32.c
@@ -1026,18 +1026,15 @@ static int emit_load_r64(const s8 *dst, const s8 *src, s16 off,
 	switch (size) {
 	case BPF_B:
 		emit(hppa_ldb(off + 0, srcreg, lo(rd)), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
+		emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
 		break;
 	case BPF_H:
 		emit(hppa_ldh(off + 0, srcreg, lo(rd)), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
+		emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
 		break;
 	case BPF_W:
 		emit(hppa_ldw(off + 0, srcreg, lo(rd)), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
+		emit_hppa_copy(HPPA_REG_ZERO, hi(rd), ctx);
 		break;
 	case BPF_DW:
 		emit(hppa_ldw(off + 0, srcreg, hi(rd)), ctx);
-- 
2.39.2

[PATCH bpf-next 4/6] bpf, powerpc32: Always zero extend for LDX

[Puranjay Mohan]

The JITs should not depend on the verifier for zero extending the upper
32 bits of the destination register when loading a byte, half-word, or
word.

A following patch will make the verifier stop patching zext instructions
after LDX.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 arch/powerpc/net/bpf_jit_comp32.c | 25 ++++++++-----------------
 1 file changed, 8 insertions(+), 17 deletions(-)

diff --git a/arch/powerpc/net/bpf_jit_comp32.c b/arch/powerpc/net/bpf_jit_comp32.c
index 7f91ea064c08..0a952a2cfaac 100644
--- a/arch/powerpc/net/bpf_jit_comp32.c
+++ b/arch/powerpc/net/bpf_jit_comp32.c
@@ -936,14 +936,13 @@ int bpf_jit_build_body(struct bpf_prog *fp, u32 *image, struct codegen_context *
 				PPC_BCC_SHORT(COND_GT, (ctx->idx + 4) * 4);
 				EMIT(PPC_RAW_LI(dst_reg, 0));
 				/*
-				 * For BPF_DW case, "li reg_h,0" would be needed when
-				 * !fp->aux->verifier_zext. Emit NOP otherwise.
+				 * For BPF_DW case, "li reg_h,0" would be needed emit NOP otherwise.
 				 *
 				 * Note that "li reg_h,0" is emitted for BPF_B/H/W case,
 				 * if necessary. So, jump there insted of emitting an
 				 * additional "li reg_h,0" instruction.
 				 */
-				if (size == BPF_DW && !fp->aux->verifier_zext)
+				if (size == BPF_DW)
 					EMIT(PPC_RAW_LI(dst_reg_h, 0));
 				else
 					EMIT(PPC_RAW_NOP());
@@ -974,7 +973,7 @@ int bpf_jit_build_body(struct bpf_prog *fp, u32 *image, struct codegen_context *
 				break;
 			}
 
-			if (size != BPF_DW && !fp->aux->verifier_zext)
+			if (size != BPF_DW)
 				EMIT(PPC_RAW_LI(dst_reg_h, 0));
 
 			if (BPF_MODE(code) == BPF_PROBE_MEM) {
@@ -982,20 +981,12 @@ int bpf_jit_build_body(struct bpf_prog *fp, u32 *image, struct codegen_context *
 				int jmp_off = 4;
 
 				/*
-				 * In case of BPF_DW, two lwz instructions are emitted, one
-				 * for higher 32-bit and another for lower 32-bit. So, set
-				 * ex->insn to the first of the two and jump over both
-				 * instructions in fixup.
-				 *
-				 * Similarly, with !verifier_zext, two instructions are
-				 * emitted for BPF_B/H/W case. So, set ex->insn to the
-				 * instruction that could fault and skip over both
-				 * instructions.
+				 * Two instructions are emitted for LDX.
+				 * So, set ex->insn to the instruction that could fault and skip
+				 * over both instructions.
 				 */
-				if (size == BPF_DW || !fp->aux->verifier_zext) {
-					insn_idx -= 1;
-					jmp_off += 4;
-				}
+				insn_idx -= 1;
+				jmp_off += 4;
 
 				ret = bpf_add_extable_entry(fp, image, pass, ctx, insn_idx,
 							    jmp_off, dst_reg);
-- 
2.39.2

[PATCH bpf-next 5/6] bpf, arm32: Always zero extend for LDX with B/H/W

[Puranjay Mohan]

The JITs should not depend on the verifier for zero extending the upper
32 bits of the destination register when loading a byte, half-word, or
word.

A following patch will make the verifier stop patching zext instructions
after LDX.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 arch/arm/net/bpf_jit_32.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/arch/arm/net/bpf_jit_32.c b/arch/arm/net/bpf_jit_32.c
index 6a1c9fca5260..757a99febba5 100644
--- a/arch/arm/net/bpf_jit_32.c
+++ b/arch/arm/net/bpf_jit_32.c
@@ -1081,20 +1081,17 @@ static inline void emit_ldx_r(const s8 dst[], const s8 src,
 	case BPF_B:
 		/* Load a Byte */
 		emit(ARM_LDRB_I(rd[1], rm, off), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_a32_mov_i(rd[0], 0, ctx);
+		emit_a32_mov_i(rd[0], 0, ctx);
 		break;
 	case BPF_H:
 		/* Load a HalfWord */
 		emit(ARM_LDRH_I(rd[1], rm, off), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_a32_mov_i(rd[0], 0, ctx);
+		emit_a32_mov_i(rd[0], 0, ctx);
 		break;
 	case BPF_W:
 		/* Load a Word */
 		emit(ARM_LDR_I(rd[1], rm, off), ctx);
-		if (!ctx->prog->aux->verifier_zext)
-			emit_a32_mov_i(rd[0], 0, ctx);
+		emit_a32_mov_i(rd[0], 0, ctx);
 		break;
 	case BPF_DW:
 		/* Load a Double Word */
-- 
2.39.2

[PATCH bpf-next 6/6] bpf, verifier: always mark destination of LDX as 64-bit

[Puranjay Mohan]

All 64-bit JITs utilize a single instruction to load + zero-extend a
byte, word, or a half-word. The optimisation of emitting zext for LDX is
not useful for most of the JITs.

All the JITs that relied on the verifier for zero extension of LDX
desitination registers have been modified to always zero extend the
destination.

Now the verifier can safely mark LDX destination as 64-bit and stop
emitting zero-extension instructions for it.

Signed-off-by: Puranjay Mohan <puranjay12@gmail.com>
---
 kernel/bpf/verifier.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index dbba2b806017..02a1ac1a1327 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3028,9 +3028,7 @@ static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return false;
 
 	if (class == BPF_LDX) {
-		if (t != SRC_OP)
-			return BPF_SIZE(code) == BPF_DW;
-		/* LDX source must be ptr. */
+		/* LDX source must be a ptr. and LDX destination is always zero-extended. */
 		return true;
 	}
 
-- 
2.39.2

Re: [PATCH bpf-next 5/6] bpf, arm32: Always zero extend for LDX with B/H/W

[Russell King (Oracle)]

On Tue, Sep 12, 2023 at 10:46:53PM +0000, Puranjay Mohan wrote:
> The JITs should not depend on the verifier for zero extending the upper
> 32 bits of the destination register when loading a byte, half-word, or
> word.
> 
> A following patch will make the verifier stop patching zext instructions
> after LDX.

This was introduced by:

163541e6ba34 ("arm: bpf: eliminate zero extension code-gen")

along with an additional function. So three points:

1) the commit should probably explain why it has now become undesirable
to access this verifier state, whereas it appears it was explicitly
added to permit this optimisation.
2) you state that jits should not depend on this state, but the above
commit adds more references than you're removing, so aren't there still
references to the verifier remaining after this patch? I count a total
of 10, and the patch below removes three.
3) what about the bpf_jit_needs_zext() function that was added to
support the export of this zext state?

Essentially, the logic stated in the commit message doesn't seem to be
reflected by the proposed code change.

-- 
RMK's Patch system: https://www.armlinux.org.uk/developer/patches/
FTTP is here! 80Mbps down 10Mbps up. Decent connectivity at last!

Re: [PATCH bpf-next 5/6] bpf, arm32: Always zero extend for LDX with B/H/W

[Puranjay Mohan]

On Wed, Sep 13, 2023 at 1:04 AM Russell King (Oracle)
<linux@armlinux.org.uk> wrote:
>
> On Tue, Sep 12, 2023 at 10:46:53PM +0000, Puranjay Mohan wrote:
> > The JITs should not depend on the verifier for zero extending the upper
> > 32 bits of the destination register when loading a byte, half-word, or
> > word.
> >
> > A following patch will make the verifier stop patching zext instructions
> > after LDX.
>
> This was introduced by:
>
> 163541e6ba34 ("arm: bpf: eliminate zero extension code-gen")
>
> along with an additional function. So three points:
>
> 1) the commit should probably explain why it has now become undesirable
> to access this verifier state, whereas it appears it was explicitly
> added to permit this optimisation.

I added some details in the cover letter.

For the complete discussion see: [1]

> 2) you state that jits should not depend on this state, but the above
> commit adds more references than you're removing, so aren't there still
> references to the verifier remaining after this patch? I count a total
> of 10, and the patch below removes three.

The JITs should not depend on this state for LDX (loading
a B/H/W.
This patch removes the usage only for LDX.

> 3) what about the bpf_jit_needs_zext() function that was added to
> support the export of this zext state?

That is still applicable, The verifier will still emit zext
instructions for other
instructions like BPF_ALU / BPF_ALU64

>
> Essentially, the logic stated in the commit message doesn't seem to be
> reflected by the proposed code change.

I will try to provide more information.
Currently I have asked Alexei if we really need this in [2].
I still think this optimization is useful and we should keep it.

Thanks,
Puranjay

[1] https://lore.kernel.org/all/CANk7y0j2f-gPgZwd+YfTL71-6wfvky+f=kBC_ccqsS0EHAysyA@mail.gmail.com/
[2] https://lore.kernel.org/bpf/CANk7y0hK9sQJ-kRx3nQpVJSxpP=NzzFaLitOYq8=Pb6Dvk9fpg@mail.gmail.com/

Re: [PATCH bpf-next 5/6] bpf, arm32: Always zero extend for LDX with B/H/W

[Alexei Starovoitov]

On Tue, Sep 12, 2023 at 4:17 PM Puranjay Mohan <puranjay12@gmail.com> wrote:
>
> On Wed, Sep 13, 2023 at 1:04 AM Russell King (Oracle)
> <linux@armlinux.org.uk> wrote:
> >
> > On Tue, Sep 12, 2023 at 10:46:53PM +0000, Puranjay Mohan wrote:
> > > The JITs should not depend on the verifier for zero extending the upper
> > > 32 bits of the destination register when loading a byte, half-word, or
> > > word.
> > >
> > > A following patch will make the verifier stop patching zext instructions
> > > after LDX.
> >
> > This was introduced by:
> >
> > 163541e6ba34 ("arm: bpf: eliminate zero extension code-gen")
> >
> > along with an additional function. So three points:
> >
> > 1) the commit should probably explain why it has now become undesirable
> > to access this verifier state, whereas it appears it was explicitly
> > added to permit this optimisation.
>
> I added some details in the cover letter.
>
> For the complete discussion see: [1]
>
> > 2) you state that jits should not depend on this state, but the above
> > commit adds more references than you're removing, so aren't there still
> > references to the verifier remaining after this patch? I count a total
> > of 10, and the patch below removes three.
>
> The JITs should not depend on this state for LDX (loading
> a B/H/W.
> This patch removes the usage only for LDX.
>
> > 3) what about the bpf_jit_needs_zext() function that was added to
> > support the export of this zext state?
>
> That is still applicable, The verifier will still emit zext
> instructions for other
> instructions like BPF_ALU / BPF_ALU64
>
> >
> > Essentially, the logic stated in the commit message doesn't seem to be
> > reflected by the proposed code change.
>
> I will try to provide more information.
> Currently I have asked Alexei if we really need this in [2].
> I still think this optimization is useful and we should keep it.

Right. subreg tracking is indeed functional for narrow loads.
Let's drop this patch set.