[RFC bpf-next 0/7] bpf: support BPF_ALU | BPF_ARSH

[RFC bpf-next 0/7] bpf: support BPF_ALU | BPF_ARSH

[Jiong Wang]

BPF_ALU | BPF_ARSH | BPF_* were rejected by commit: 7891a87efc71
("bpf: arsh is not supported in 32 bit alu thus reject it"). As explained
in the commit message, this is due to there is no complete support for them
on interpreter and various JIT compilation back-ends.

This patch set is a follow-up which completes the missing bits. This also
pave the way for running bpf program compiled with ALU32 instruction
enabled by specifing -mattr=+alu32 to LLVM for which case there is likely
have more BPF_ALU | BPF_ARSH insns that will trigger the rejection code.

test_verifier.c is updated accordingly.

I have tested this patch set on x86-64 and NFP, I need help of review and
test on the arch changes (mips/ppc/s390).

Note, to avoid merge confict, mips change needs to be applied on top of
commit: 20b880a05f06 ("mips: bpf: fix encoding bug for mm_srlv32_op"), it
is on mips-fixes branch at the moment.

Thanks.

Jiong Wang (7):
  bpf: interpreter support BPF_ALU | BPF_ARSH
  mips: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_X
  ppc: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*
  s390: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*
  nfp: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*
  bpf: verifier remove the rejection on BPF_ALU | BPF_ARSH
  selftests: bpf: update testcases for BPF_ALU | BPF_ARSH

 arch/mips/include/asm/uasm.h                 |  1 +
 arch/mips/include/uapi/asm/inst.h            |  1 +
 arch/mips/mm/uasm-micromips.c                |  1 +
 arch/mips/mm/uasm-mips.c                     |  1 +
 arch/mips/mm/uasm.c                          |  9 ++---
 arch/mips/net/ebpf_jit.c                     |  4 +++
 arch/powerpc/include/asm/ppc-opcode.h        |  2 ++
 arch/powerpc/net/bpf_jit.h                   |  4 +++
 arch/powerpc/net/bpf_jit_comp64.c            |  6 ++++
 arch/s390/net/bpf_jit_comp.c                 | 12 +++++++
 drivers/net/ethernet/netronome/nfp/bpf/jit.c | 45 ++++++++++++++++++++++++
 kernel/bpf/core.c                            | 52 ++++++++++++++++------------
 kernel/bpf/verifier.c                        |  5 ---
 tools/testing/selftests/bpf/test_verifier.c  | 29 +++++++++++++---
 14 files changed, 137 insertions(+), 35 deletions(-)

-- 
2.7.4

[RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Jiong Wang]

This patch implements interpreting BPF_ALU | BPF_ARSH. Do arithmetic right
shift on low 32-bit sub-register, and zero the high 32 bits.

Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/core.c | 52 ++++++++++++++++++++++++++++++----------------------
 1 file changed, 30 insertions(+), 22 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index f93ed66..36e31d8 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -923,32 +923,34 @@ EXPORT_SYMBOL_GPL(__bpf_call_base);
 #define BPF_INSN_MAP(INSN_2, INSN_3)		\
 	/* 32 bit ALU operations. */		\
 	/*   Register based. */			\
-	INSN_3(ALU, ADD, X),			\
-	INSN_3(ALU, SUB, X),			\
-	INSN_3(ALU, AND, X),			\
-	INSN_3(ALU, OR,  X),			\
-	INSN_3(ALU, LSH, X),			\
-	INSN_3(ALU, RSH, X),			\
-	INSN_3(ALU, XOR, X),			\
-	INSN_3(ALU, MUL, X),			\
-	INSN_3(ALU, MOV, X),			\
-	INSN_3(ALU, DIV, X),			\
-	INSN_3(ALU, MOD, X),			\
+	INSN_3(ALU, ADD,  X),			\
+	INSN_3(ALU, SUB,  X),			\
+	INSN_3(ALU, AND,  X),			\
+	INSN_3(ALU, OR,   X),			\
+	INSN_3(ALU, LSH,  X),			\
+	INSN_3(ALU, RSH,  X),			\
+	INSN_3(ALU, XOR,  X),			\
+	INSN_3(ALU, MUL,  X),			\
+	INSN_3(ALU, MOV,  X),			\
+	INSN_3(ALU, ARSH, X),			\
+	INSN_3(ALU, DIV,  X),			\
+	INSN_3(ALU, MOD,  X),			\
 	INSN_2(ALU, NEG),			\
 	INSN_3(ALU, END, TO_BE),		\
 	INSN_3(ALU, END, TO_LE),		\
 	/*   Immediate based. */		\
-	INSN_3(ALU, ADD, K),			\
-	INSN_3(ALU, SUB, K),			\
-	INSN_3(ALU, AND, K),			\
-	INSN_3(ALU, OR,  K),			\
-	INSN_3(ALU, LSH, K),			\
-	INSN_3(ALU, RSH, K),			\
-	INSN_3(ALU, XOR, K),			\
-	INSN_3(ALU, MUL, K),			\
-	INSN_3(ALU, MOV, K),			\
-	INSN_3(ALU, DIV, K),			\
-	INSN_3(ALU, MOD, K),			\
+	INSN_3(ALU, ADD,  K),			\
+	INSN_3(ALU, SUB,  K),			\
+	INSN_3(ALU, AND,  K),			\
+	INSN_3(ALU, OR,   K),			\
+	INSN_3(ALU, LSH,  K),			\
+	INSN_3(ALU, RSH,  K),			\
+	INSN_3(ALU, XOR,  K),			\
+	INSN_3(ALU, MUL,  K),			\
+	INSN_3(ALU, MOV,  K),			\
+	INSN_3(ALU, ARSH, K),			\
+	INSN_3(ALU, DIV,  K),			\
+	INSN_3(ALU, MOD,  K),			\
 	/* 64 bit ALU operations. */		\
 	/*   Register based. */			\
 	INSN_3(ALU64, ADD,  X),			\
@@ -1127,6 +1129,12 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)
 		DST = (u64) (u32) insn[0].imm | ((u64) (u32) insn[1].imm) << 32;
 		insn++;
 		CONT;
+	ALU_ARSH_X:
+		DST = (u64) (u32) ((*(s32 *) &DST) >> SRC);
+		CONT;
+	ALU_ARSH_K:
+		DST = (u64) (u32) ((*(s32 *) &DST) >> IMM);
+		CONT;
 	ALU64_ARSH_X:
 		(*(s64 *) &DST) >>= SRC;
 		CONT;
-- 
2.7.4

[RFC bpf-next 2/7] mips: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_X

[Jiong Wang]

Jitting of BPF_K is supported already, but not BPF_X. This patch complete
the support for the latter on both MIPS and microMIPS.

Cc: Paul Burton <paul.burton@mips.com>
Cc: linux-mips@vger.kernel.org
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 arch/mips/include/asm/uasm.h      | 1 +
 arch/mips/include/uapi/asm/inst.h | 1 +
 arch/mips/mm/uasm-micromips.c     | 1 +
 arch/mips/mm/uasm-mips.c          | 1 +
 arch/mips/mm/uasm.c               | 9 +++++----
 arch/mips/net/ebpf_jit.c          | 4 ++++
 6 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/arch/mips/include/asm/uasm.h b/arch/mips/include/asm/uasm.h
index 59dae37..b1990dd 100644
--- a/arch/mips/include/asm/uasm.h
+++ b/arch/mips/include/asm/uasm.h
@@ -157,6 +157,7 @@ Ip_u2u1s3(_slti);
 Ip_u2u1s3(_sltiu);
 Ip_u3u1u2(_sltu);
 Ip_u2u1u3(_sra);
+Ip_u3u2u1(_srav);
 Ip_u2u1u3(_srl);
 Ip_u3u2u1(_srlv);
 Ip_u3u1u2(_subu);
diff --git a/arch/mips/include/uapi/asm/inst.h b/arch/mips/include/uapi/asm/inst.h
index 273ef58..40fbb5d 100644
--- a/arch/mips/include/uapi/asm/inst.h
+++ b/arch/mips/include/uapi/asm/inst.h
@@ -371,6 +371,7 @@ enum mm_32a_minor_op {
 	mm_srl32_op = 0x040,
 	mm_srlv32_op = 0x050,
 	mm_sra_op = 0x080,
+	mm_srav_op = 0x090,
 	mm_rotr_op = 0x0c0,
 	mm_lwxs_op = 0x118,
 	mm_addu32_op = 0x150,
diff --git a/arch/mips/mm/uasm-micromips.c b/arch/mips/mm/uasm-micromips.c
index 24e5b0d..75ef904 100644
--- a/arch/mips/mm/uasm-micromips.c
+++ b/arch/mips/mm/uasm-micromips.c
@@ -104,6 +104,7 @@ static const struct insn insn_table_MM[insn_invalid] = {
 	[insn_sltiu]	= {M(mm_sltiu32_op, 0, 0, 0, 0, 0), RT | RS | SIMM},
 	[insn_sltu]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_sltu_op), RT | RS | RD},
 	[insn_sra]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_sra_op), RT | RS | RD},
+	[insn_srav]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_srav_op), RT | RS | RD},
 	[insn_srl]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_srl32_op), RT | RS | RD},
 	[insn_srlv]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_srlv32_op), RT | RS | RD},
 	[insn_rotr]	= {M(mm_pool32a_op, 0, 0, 0, 0, mm_rotr_op), RT | RS | RD},
diff --git a/arch/mips/mm/uasm-mips.c b/arch/mips/mm/uasm-mips.c
index 60ceb93..6abe40f 100644
--- a/arch/mips/mm/uasm-mips.c
+++ b/arch/mips/mm/uasm-mips.c
@@ -171,6 +171,7 @@ static const struct insn insn_table[insn_invalid] = {
 	[insn_sltiu]	= {M(sltiu_op, 0, 0, 0, 0, 0), RS | RT | SIMM},
 	[insn_sltu]	= {M(spec_op, 0, 0, 0, 0, sltu_op), RS | RT | RD},
 	[insn_sra]	= {M(spec_op, 0, 0, 0, 0, sra_op),  RT | RD | RE},
+	[insn_srav]	= {M(spec_op, 0, 0, 0, 0, srav_op), RS | RT | RD},
 	[insn_srl]	= {M(spec_op, 0, 0, 0, 0, srl_op),  RT | RD | RE},
 	[insn_srlv]	= {M(spec_op, 0, 0, 0, 0, srlv_op),  RS | RT | RD},
 	[insn_subu]	= {M(spec_op, 0, 0, 0, 0, subu_op),	RS | RT | RD},
diff --git a/arch/mips/mm/uasm.c b/arch/mips/mm/uasm.c
index 57570c0..45b6264 100644
--- a/arch/mips/mm/uasm.c
+++ b/arch/mips/mm/uasm.c
@@ -61,10 +61,10 @@ enum opcode {
 	insn_mthc0, insn_mthi, insn_mtlo, insn_mul, insn_multu, insn_nor,
 	insn_or, insn_ori, insn_pref, insn_rfe, insn_rotr, insn_sb,
 	insn_sc, insn_scd, insn_sd, insn_sh, insn_sll, insn_sllv,
-	insn_slt, insn_slti, insn_sltiu, insn_sltu, insn_sra, insn_srl,
-	insn_srlv, insn_subu, insn_sw, insn_sync, insn_syscall, insn_tlbp,
-	insn_tlbr, insn_tlbwi, insn_tlbwr, insn_wait, insn_wsbh, insn_xor,
-	insn_xori, insn_yield,
+	insn_slt, insn_slti, insn_sltiu, insn_sltu, insn_sra, insn_srav,
+	insn_srl, insn_srlv, insn_subu, insn_sw, insn_sync, insn_syscall,
+	insn_tlbp, insn_tlbr, insn_tlbwi, insn_tlbwr, insn_wait, insn_wsbh,
+	insn_xor, insn_xori, insn_yield,
 	insn_invalid /* insn_invalid must be last */
 };
 
@@ -353,6 +353,7 @@ I_u2u1s3(_slti)
 I_u2u1s3(_sltiu)
 I_u3u1u2(_sltu)
 I_u2u1u3(_sra)
+I_u3u2u1(_srav)
 I_u2u1u3(_srl)
 I_u3u2u1(_srlv)
 I_u2u1u3(_rotr)
diff --git a/arch/mips/net/ebpf_jit.c b/arch/mips/net/ebpf_jit.c
index aeb7b1b..b16710a 100644
--- a/arch/mips/net/ebpf_jit.c
+++ b/arch/mips/net/ebpf_jit.c
@@ -854,6 +854,7 @@ static int build_one_insn(const struct bpf_insn *insn, struct jit_ctx *ctx,
 	case BPF_ALU | BPF_MOD | BPF_X: /* ALU_REG */
 	case BPF_ALU | BPF_LSH | BPF_X: /* ALU_REG */
 	case BPF_ALU | BPF_RSH | BPF_X: /* ALU_REG */
+	case BPF_ALU | BPF_ARSH | BPF_X: /* ALU_REG */
 		src = ebpf_to_mips_reg(ctx, insn, src_reg_no_fp);
 		dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 		if (src < 0 || dst < 0)
@@ -913,6 +914,9 @@ static int build_one_insn(const struct bpf_insn *insn, struct jit_ctx *ctx,
 		case BPF_RSH:
 			emit_instr(ctx, srlv, dst, dst, src);
 			break;
+		case BPF_ARSH:
+			emit_instr(ctx, srav, dst, dst, src);
+			break;
 		default:
 			pr_err("ALU_REG NOT HANDLED\n");
 			return -EINVAL;
-- 
2.7.4

[RFC bpf-next 3/7] ppc: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*

[Jiong Wang]

This patch implements code-gen for BPF_ALU | BPF_ARSH | BPF_*.

Cc: Naveen N. Rao <naveen.n.rao@linux.ibm.com>
Cc: Sandipan Das <sandipan@linux.ibm.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 arch/powerpc/include/asm/ppc-opcode.h | 2 ++
 arch/powerpc/net/bpf_jit.h            | 4 ++++
 arch/powerpc/net/bpf_jit_comp64.c     | 6 ++++++
 3 files changed, 12 insertions(+)

diff --git a/arch/powerpc/include/asm/ppc-opcode.h b/arch/powerpc/include/asm/ppc-opcode.h
index a6e9e31..9014592 100644
--- a/arch/powerpc/include/asm/ppc-opcode.h
+++ b/arch/powerpc/include/asm/ppc-opcode.h
@@ -342,6 +342,8 @@
 #define PPC_INST_SLW			0x7c000030
 #define PPC_INST_SLD			0x7c000036
 #define PPC_INST_SRW			0x7c000430
+#define PPC_INST_SRAW			0x7c000630
+#define PPC_INST_SRAWI			0x7c000670
 #define PPC_INST_SRD			0x7c000436
 #define PPC_INST_SRAD			0x7c000634
 #define PPC_INST_SRADI			0x7c000674
diff --git a/arch/powerpc/net/bpf_jit.h b/arch/powerpc/net/bpf_jit.h
index 47fc666..c2d5192 100644
--- a/arch/powerpc/net/bpf_jit.h
+++ b/arch/powerpc/net/bpf_jit.h
@@ -152,6 +152,10 @@
 				     ___PPC_RS(a) | ___PPC_RB(s))
 #define PPC_SRW(d, a, s)	EMIT(PPC_INST_SRW | ___PPC_RA(d) |	      \
 				     ___PPC_RS(a) | ___PPC_RB(s))
+#define PPC_SRAW(d, a, s)	EMIT(PPC_INST_SRAW | ___PPC_RA(d) |	      \
+				     ___PPC_RS(a) | ___PPC_RB(s))
+#define PPC_SRAWI(d, a, i)	EMIT(PPC_INST_SRAWI | ___PPC_RA(d) |	      \
+				     ___PPC_RS(a) | __PPC_SH(i))
 #define PPC_SRD(d, a, s)	EMIT(PPC_INST_SRD | ___PPC_RA(d) |	      \
 				     ___PPC_RS(a) | ___PPC_RB(s))
 #define PPC_SRAD(d, a, s)	EMIT(PPC_INST_SRAD | ___PPC_RA(d) |	      \
diff --git a/arch/powerpc/net/bpf_jit_comp64.c b/arch/powerpc/net/bpf_jit_comp64.c
index 17482f5..c685b4f 100644
--- a/arch/powerpc/net/bpf_jit_comp64.c
+++ b/arch/powerpc/net/bpf_jit_comp64.c
@@ -529,9 +529,15 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,
 			if (imm != 0)
 				PPC_SRDI(dst_reg, dst_reg, imm);
 			break;
+		case BPF_ALU | BPF_ARSH | BPF_X: /* (s32) dst >>= src */
+			PPC_SRAW(dst_reg, dst_reg, src_reg);
+			break;
 		case BPF_ALU64 | BPF_ARSH | BPF_X: /* (s64) dst >>= src */
 			PPC_SRAD(dst_reg, dst_reg, src_reg);
 			break;
+		case BPF_ALU | BPF_ARSH | BPF_K: /* (s32) dst >>= imm */
+			PPC_SRAWI(dst_reg, dst_reg, imm);
+			break;
 		case BPF_ALU64 | BPF_ARSH | BPF_K: /* (s64) dst >>= imm */
 			if (imm != 0)
 				PPC_SRADI(dst_reg, dst_reg, imm);
-- 
2.7.4

[RFC bpf-next 4/7] s390: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*

[Jiong Wang]

This patch implements code-gen for BPF_ALU | BPF_ARSH | BPF_*.

Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
Cc: Heiko Carstens <heiko.carstens@de.ibm.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 arch/s390/net/bpf_jit_comp.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/arch/s390/net/bpf_jit_comp.c b/arch/s390/net/bpf_jit_comp.c
index d7052cb..3ff758e 100644
--- a/arch/s390/net/bpf_jit_comp.c
+++ b/arch/s390/net/bpf_jit_comp.c
@@ -821,10 +821,22 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp, int i
 	/*
 	 * BPF_ARSH
 	 */
+	case BPF_ALU | BPF_ARSH | BPF_X: /* ((s32) dst) >>= src */
+		/* sra %dst,%dst,0(%src) */
+		EMIT4_DISP(0x8a000000, dst_reg, src_reg, 0);
+		EMIT_ZERO(dst_reg);
+		break;
 	case BPF_ALU64 | BPF_ARSH | BPF_X: /* ((s64) dst) >>= src */
 		/* srag %dst,%dst,0(%src) */
 		EMIT6_DISP_LH(0xeb000000, 0x000a, dst_reg, dst_reg, src_reg, 0);
 		break;
+	case BPF_ALU | BPF_ARSH | BPF_K: /* ((s32) dst >> imm */
+		if (imm == 0)
+			break;
+		/* sra %dst,imm(%r0) */
+		EMIT4_DISP(0x8a000000, dst_reg, REG_0, imm);
+		EMIT_ZERO(dst_reg);
+		break;
 	case BPF_ALU64 | BPF_ARSH | BPF_K: /* ((s64) dst) >>= imm */
 		if (imm == 0)
 			break;
-- 
2.7.4

[RFC bpf-next 5/7] nfp: bpf: implement jitting of BPF_ALU | BPF_ARSH | BPF_*

[Jiong Wang]

BPF_X support needs indirect shift mode, please see code comments for
details.

Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c | 45 ++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 97d33bb..662cbc2 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -2382,6 +2382,49 @@ static int neg_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 	return 0;
 }
 
+static int __ashr_imm(struct nfp_prog *nfp_prog, u8 dst, u8 shift_amt)
+{
+	/* Set signedness bit (MSB of result). */
+	emit_alu(nfp_prog, reg_none(), reg_a(dst), ALU_OP_OR, reg_imm(0));
+	emit_shf(nfp_prog, reg_both(dst), reg_none(), SHF_OP_ASHR, reg_b(dst),
+		 SHF_SC_R_SHF, shift_amt);
+	wrp_immed(nfp_prog, reg_both(dst + 1), 0);
+
+	return 0;
+}
+
+static int ashr_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
+{
+	const struct bpf_insn *insn = &meta->insn;
+	u64 umin, umax;
+	u8 dst, src;
+
+	dst = insn->dst_reg * 2;
+	umin = meta->umin_src;
+	umax = meta->umax_src;
+	if (umin == umax)
+		return __ashr_imm(nfp_prog, dst, umin);
+
+	src = insn->src_reg * 2;
+	/* NOTE: the first insn will set both indirect shift amount (source A)
+	 * and signedness bit (MSB of result).
+	 */
+	emit_alu(nfp_prog, reg_none(), reg_a(src), ALU_OP_OR, reg_b(dst));
+	emit_shf_indir(nfp_prog, reg_both(dst), reg_none(), SHF_OP_ASHR,
+		       reg_b(dst), SHF_SC_R_SHF);
+	wrp_immed(nfp_prog, reg_both(dst + 1), 0);
+
+	return 0;
+}
+
+static int ashr_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
+{
+	const struct bpf_insn *insn = &meta->insn;
+	u8 dst = insn->dst_reg * 2;
+
+	return __ashr_imm(nfp_prog, dst, insn->imm);
+}
+
 static int shl_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 {
 	const struct bpf_insn *insn = &meta->insn;
@@ -3286,6 +3329,8 @@ static const instr_cb_t instr_cb[256] = {
 	[BPF_ALU | BPF_DIV | BPF_K] =	div_imm,
 	[BPF_ALU | BPF_NEG] =		neg_reg,
 	[BPF_ALU | BPF_LSH | BPF_K] =	shl_imm,
+	[BPF_ALU | BPF_ARSH | BPF_X] =	ashr_reg,
+	[BPF_ALU | BPF_ARSH | BPF_K] =	ashr_imm,
 	[BPF_ALU | BPF_END | BPF_X] =	end_reg32,
 	[BPF_LD | BPF_IMM | BPF_DW] =	imm_ld8,
 	[BPF_LD | BPF_ABS | BPF_B] =	data_ld1,
-- 
2.7.4

[RFC bpf-next 6/7] bpf: verifier remove the rejection on BPF_ALU | BPF_ARSH

[Jiong Wang]

This patch remove the rejection on BPF_ALU | BPF_ARSH as we have supported
them on interpreter and all JIT back-ends

Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c | 5 -----
 1 file changed, 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ce8a1c3..8ed868e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3649,11 +3649,6 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			return -EINVAL;
 		}
 
-		if (opcode == BPF_ARSH && BPF_CLASS(insn->code) != BPF_ALU64) {
-			verbose(env, "BPF_ARSH not supported for 32 bit ALU\n");
-			return -EINVAL;
-		}
-
 		if ((opcode == BPF_LSH || opcode == BPF_RSH ||
 		     opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
 			int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
-- 
2.7.4

[RFC bpf-next 7/7] selftests: bpf: update testcases for BPF_ALU | BPF_ARSH

[Jiong Wang]

"arsh32 on imm" and "arsh32 on reg" now are accepted. Also added two new
testcases to make sure arsh32 won't be treated as arsh64 during
interpretation or JIT code-gen for which case the high bits will be moved
into low halve that the testcases could catch them.

Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 tools/testing/selftests/bpf/test_verifier.c | 29 +++++++++++++++++++++++++----
 1 file changed, 25 insertions(+), 4 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 18d0b7f..e7f1bc7 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -721,8 +721,18 @@ static struct bpf_test tests[] = {
 			BPF_ALU32_IMM(BPF_ARSH, BPF_REG_0, 5),
 			BPF_EXIT_INSN(),
 		},
-		.result = REJECT,
-		.errstr = "unknown opcode c4",
+		.result = ACCEPT,
+		.retval = 0,
+	},
+	{
+		"arsh32 on imm 2",
+		.insns = {
+			BPF_LD_IMM64(BPF_REG_0, 0x1122334485667788),
+			BPF_ALU32_IMM(BPF_ARSH, BPF_REG_0, 7),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = -16069393,
 	},
 	{
 		"arsh32 on reg",
@@ -732,8 +742,19 @@ static struct bpf_test tests[] = {
 			BPF_ALU32_REG(BPF_ARSH, BPF_REG_0, BPF_REG_1),
 			BPF_EXIT_INSN(),
 		},
-		.result = REJECT,
-		.errstr = "unknown opcode cc",
+		.result = ACCEPT,
+		.retval = 0,
+	},
+	{
+		"arsh32 on reg 2",
+		.insns = {
+			BPF_LD_IMM64(BPF_REG_0, 0xffff55667788),
+			BPF_MOV64_IMM(BPF_REG_1, 15),
+			BPF_ALU32_REG(BPF_ARSH, BPF_REG_0, BPF_REG_1),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 43724,
 	},
 	{
 		"arsh64 on imm",
-- 
2.7.4

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[David Miller]

From: Jiong Wang <jiong.wang@netronome.com>
Date: Tue,  4 Dec 2018 04:56:29 -0500

> This patch implements interpreting BPF_ALU | BPF_ARSH. Do arithmetic right
> shift on low 32-bit sub-register, and zero the high 32 bits.
> 
> Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> Signed-off-by: Jiong Wang <jiong.wang@netronome.com>

I just want to say that this behavior is interesting because on most
cpus that have a 32-bit and 64-bit variant, the 32-bit arithmetic
right shift typically sign extends to 64-bit rather than zero extends
which is what is being defined here.

Well, definitely, sparc64 behaves this way.

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Alexei Starovoitov]

On Tue, Dec 04, 2018 at 08:43:11AM -0800, David Miller wrote:
> From: Jiong Wang <jiong.wang@netronome.com>
> Date: Tue,  4 Dec 2018 04:56:29 -0500
> 
> > This patch implements interpreting BPF_ALU | BPF_ARSH. Do arithmetic right
> > shift on low 32-bit sub-register, and zero the high 32 bits.
> > 
> > Reviewed-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> > Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
> 
> I just want to say that this behavior is interesting because on most
> cpus that have a 32-bit and 64-bit variant, the 32-bit arithmetic
> right shift typically sign extends to 64-bit rather than zero extends
> which is what is being defined here.
> 
> Well, definitely, sparc64 behaves this way.

interesting. I think on x64 and arm64 any arithemtic operation on 32-bit
subregister zero extends upper 32-bits. I wonder why sparc went with
sign-extend. I guess sparc doesn't really have 32 subregisters.
All registers are considered 64-bit. It has 32-bit alu ops on 64-bit
registers instead.

Regarding the set... It looks good to me. Pls resubmit without RFC tag
and probably include mips patch as patch 1, so we can apply the whole
thing to bpf-next. git will take care of same patch being in two trees.

Re: [oss-drivers] Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Jakub Kicinski]

On Tue, 4 Dec 2018 11:29:55 -0800, Alexei Starovoitov wrote:
> Regarding the set... It looks good to me. Pls resubmit without RFC tag
> and probably include mips patch as patch 1, so we can apply the whole
> thing to bpf-next. git will take care of same patch being in two trees.

Doesn't it only take care if the commit id matches?  I.e. if you were
to pull the MIPS tree?

Re: [oss-drivers] Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Alexei Starovoitov]

On Tue, Dec 04, 2018 at 11:42:54AM -0800, Jakub Kicinski wrote:
> On Tue, 4 Dec 2018 11:29:55 -0800, Alexei Starovoitov wrote:
> > Regarding the set... It looks good to me. Pls resubmit without RFC tag
> > and probably include mips patch as patch 1, so we can apply the whole
> > thing to bpf-next. git will take care of same patch being in two trees.
> 
> Doesn't it only take care if the commit id matches?  I.e. if you were
> to pull the MIPS tree?

I think we've tried that before. As long as all text of the patch
is the same (including commit log), git will not complain.
fingers crossed :)

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[David Miller]

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date: Tue, 4 Dec 2018 11:29:55 -0800

> I guess sparc doesn't really have 32 subregisters.  All registers
> are considered 64-bit. It has 32-bit alu ops on 64-bit registers
> instead.

Right.

Anyways, sparc will require two instructions because of this, the
'sra' then a 'srl' by zero bits to clear the top 32-bits.

I'll code up the sparc JIT part when this goes in.

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Jiong Wang]

On 04/12/2018 20:10, David Miller wrote:
> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Date: Tue, 4 Dec 2018 11:29:55 -0800
>
>> I guess sparc doesn't really have 32 subregisters.  All registers
>> are considered 64-bit. It has 32-bit alu ops on 64-bit registers
>> instead.
> Right.
>
> Anyways, sparc will require two instructions because of this, the
> 'sra' then a 'srl' by zero bits to clear the top 32-bits.
>
> I'll code up the sparc JIT part when this goes in.

Hmm, I had been going through all JIT backends, and saw there is
do_alu32_trunc after jitting sra for BPF_ALU. That's what needed?

Regards,
Jiong

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[Alexei Starovoitov]

On Tue, Dec 04, 2018 at 12:10:05PM -0800, David Miller wrote:
> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Date: Tue, 4 Dec 2018 11:29:55 -0800
> 
> > I guess sparc doesn't really have 32 subregisters.  All registers
> > are considered 64-bit. It has 32-bit alu ops on 64-bit registers
> > instead.
> 
> Right.
> 
> Anyways, sparc will require two instructions because of this, the
> 'sra' then a 'srl' by zero bits to clear the top 32-bits.
> 
> I'll code up the sparc JIT part when this goes in.

You already did :)
As far as I can see sparc64 JIT supports it properly.
Just like x64.
Hence the patches for these JITs are missing in Joing's set.

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[David Miller]

From: Jiong Wang <jiong.wang@netronome.com>
Date: Tue, 4 Dec 2018 20:14:11 +0000

> On 04/12/2018 20:10, David Miller wrote:
>> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
>> Date: Tue, 4 Dec 2018 11:29:55 -0800
>>
>>> I guess sparc doesn't really have 32 subregisters.  All registers
>>> are considered 64-bit. It has 32-bit alu ops on 64-bit registers
>>> instead.
>> Right.
>>
>> Anyways, sparc will require two instructions because of this, the
>> 'sra' then a 'srl' by zero bits to clear the top 32-bits.
>>
>> I'll code up the sparc JIT part when this goes in.
> 
> Hmm, I had been going through all JIT backends, and saw there is
> do_alu32_trunc after jitting sra for BPF_ALU. That's what needed?

Yes, it clears the top 32-bits of a register after a 32-bit
ALU op beccause BPF's semantics require it.

In fact, we call it too much, we even call it for 32-bit
shift right instructions which automatically clear those
top bits.  I've been meaning to optimize that.

Meanwhile, again the answer to your question is yes.

Re: [RFC bpf-next 1/7] bpf: interpreter support BPF_ALU | BPF_ARSH

[David Miller]

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date: Tue, 4 Dec 2018 12:16:04 -0800

> You already did :)

Amazing, I'll take the rest of the day off, thanks! :)