Linux-RISC-V Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support
@ 2019-12-16  9:13 Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Björn Töpel
                   ` (18 more replies)
  0 siblings, 19 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

Hi!

This series contain one non-critical fix, support for far jumps. and
some optimizations for the BPF JIT.

Previously, the JIT only supported 12b branch targets for conditional
branches, and 21b for unconditional branches. Starting with this
series, 32b branching is supported.

As part of supporting far jumps, branch relaxation was introduced. The
idea is to start with a pessimistic jump (e.g. auipc/jalr) and for
each pass the JIT will have an opportunity to pick a better
instruction (e.g. jal) and shrink the image. Instead of two passes,
the JIT requires more passes. It typically converges after 3 passes.

The optimizations mentioned in the subject are for calls and tail
calls. In the tail call generation we can save one instruction by
using the offset in jalr. Calls are optimized by doing (auipc)/jal(r)
relative jumps instead of loading the entire absolute address and
doing jalr. This required that the JIT image allocator was made RISC-V
specific, so we can ensure that the JIT image and the kernel text are
in range (32b).

The last two patches of the series is not critical to the series, but
are two UAPI build issues for BPF events. A closer look from the
RV-folks would be much appreciated.

The test_bpf.ko module, selftests/bpf/test_verifier and
selftests/seccomp/seccomp_bpf pass all tests.

RISC-V is still missing proper kprobe and tracepoint support, so a lot
of BPF selftests cannot be run.


Thanks,
Björn

v1->v2: [1]
 * Removed unused function parameter from emit_branch()
 * Added patch to support far branch in tail call emit

[1] https://lore.kernel.org/bpf/20191209173136.29615-1-bjorn.topel@gmail.com/


Björn Töpel (9):
  riscv, bpf: fix broken BPF tail calls
  riscv, bpf: add support for far branching
  riscv, bpf: add support for far branching when emitting tail call
  riscv, bpf: add support for far jumps and exits
  riscv, bpf: optimize BPF tail calls
  riscv, bpf: provide RISC-V specific JIT image alloc/free
  riscv, bpf: optimize calls
  riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT
    programs
  riscv, perf: add arch specific perf_arch_bpf_user_pt_regs

 arch/riscv/include/asm/perf_event.h          |   4 +
 arch/riscv/include/asm/pgtable.h             |   4 +
 arch/riscv/include/uapi/asm/bpf_perf_event.h |   9 +
 arch/riscv/net/bpf_jit_comp.c                | 531 ++++++++++---------
 tools/include/uapi/asm/bpf_perf_event.h      |   2 +
 5 files changed, 312 insertions(+), 238 deletions(-)
 create mode 100644 arch/riscv/include/uapi/asm/bpf_perf_event.h

-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Björn Töpel
                   ` (17 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

The BPF JIT incorrectly clobbered the a0 register, and did not flag
usage of s5 register when BPF stack was being used.

Fixes: 2353ecc6f91f ("bpf, riscv: add BPF JIT for RV64G")
Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index 5451ef3845f2..1606ebd49666 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -120,6 +120,11 @@ static bool seen_reg(int reg, struct rv_jit_context *ctx)
 	return false;
 }
 
+static void mark_fp(struct rv_jit_context *ctx)
+{
+	__set_bit(RV_CTX_F_SEEN_S5, &ctx->flags);
+}
+
 static void mark_call(struct rv_jit_context *ctx)
 {
 	__set_bit(RV_CTX_F_SEEN_CALL, &ctx->flags);
@@ -596,7 +601,8 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
 
 	emit(rv_addi(RV_REG_SP, RV_REG_SP, stack_adjust), ctx);
 	/* Set return value. */
-	emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
+	if (reg == RV_REG_RA)
+		emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
 	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
 }
 
@@ -1426,6 +1432,10 @@ static void build_prologue(struct rv_jit_context *ctx)
 {
 	int stack_adjust = 0, store_offset, bpf_stack_adjust;
 
+	bpf_stack_adjust = round_up(ctx->prog->aux->stack_depth, 16);
+	if (bpf_stack_adjust)
+		mark_fp(ctx);
+
 	if (seen_reg(RV_REG_RA, ctx))
 		stack_adjust += 8;
 	stack_adjust += 8; /* RV_REG_FP */
@@ -1443,7 +1453,6 @@ static void build_prologue(struct rv_jit_context *ctx)
 		stack_adjust += 8;
 
 	stack_adjust = round_up(stack_adjust, 16);
-	bpf_stack_adjust = round_up(ctx->prog->aux->stack_depth, 16);
 	stack_adjust += bpf_stack_adjust;
 
 	store_offset = stack_adjust - 8;
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Björn Töpel
                   ` (16 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev
  Cc: Björn Töpel, linux-riscv, Luke Nelson, bpf, Xi Wang

This commit adds branch relaxation to the BPF JIT, and with that
support for far (offset greater than 12b) branching.

The branch relaxation requires more than two passes to converge. For
most programs it is three passes, but for larger programs it can be
more.

Reviewed-by: Luke Nelson <lukenels@cs.washington.edu>
Cc: Xi Wang <xi.wang@gmail.com>
Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 352 ++++++++++++++++++----------------
 1 file changed, 188 insertions(+), 164 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index 1606ebd49666..e599458a9bcd 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -461,6 +461,11 @@ static u32 rv_amoadd_d(u8 rd, u8 rs2, u8 rs1, u8 aq, u8 rl)
 	return rv_amo_insn(0, aq, rl, rs2, rs1, 3, rd, 0x2f);
 }
 
+static u32 rv_auipc(u8 rd, u32 imm31_12)
+{
+	return rv_u_insn(imm31_12, rd, 0x17);
+}
+
 static bool is_12b_int(s64 val)
 {
 	return -(1 << 11) <= val && val < (1 << 11);
@@ -484,7 +489,7 @@ static bool is_32b_int(s64 val)
 static int is_12b_check(int off, int insn)
 {
 	if (!is_12b_int(off)) {
-		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
+		pr_err("bpf-jit: insn=%d 12b < offset=%d not supported yet!\n",
 		       insn, (int)off);
 		return -1;
 	}
@@ -494,7 +499,7 @@ static int is_12b_check(int off, int insn)
 static int is_13b_check(int off, int insn)
 {
 	if (!is_13b_int(off)) {
-		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
+		pr_err("bpf-jit: insn=%d 13b < offset=%d not supported yet!\n",
 		       insn, (int)off);
 		return -1;
 	}
@@ -504,7 +509,7 @@ static int is_13b_check(int off, int insn)
 static int is_21b_check(int off, int insn)
 {
 	if (!is_21b_int(off)) {
-		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
+		pr_err("bpf-jit: insn=%d 21b < offset=%d not supported yet!\n",
 		       insn, (int)off);
 		return -1;
 	}
@@ -550,10 +555,13 @@ static void emit_imm(u8 rd, s64 val, struct rv_jit_context *ctx)
 		emit(rv_addi(rd, rd, lower), ctx);
 }
 
-static int rv_offset(int bpf_to, int bpf_from, struct rv_jit_context *ctx)
+static int rv_offset(int insn, int off, struct rv_jit_context *ctx)
 {
-	int from = ctx->offset[bpf_from] - 1, to = ctx->offset[bpf_to];
+	int from, to;
 
+	off++; /* BPF branch is from PC+1, RV is from PC */
+	from = (insn > 0) ? ctx->offset[insn - 1] : 0;
+	to = (insn + off > 0) ? ctx->offset[insn + off - 1] : 0;
 	return (to - from) << 2;
 }
 
@@ -606,6 +614,109 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
 	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
 }
 
+/* return -1 or inverted cond */
+static int invert_bpf_cond(u8 cond)
+{
+	switch (cond) {
+	case BPF_JEQ:
+		return BPF_JNE;
+	case BPF_JGT:
+		return BPF_JLE;
+	case BPF_JLT:
+		return BPF_JGE;
+	case BPF_JGE:
+		return BPF_JLT;
+	case BPF_JLE:
+		return BPF_JGT;
+	case BPF_JNE:
+		return BPF_JEQ;
+	case BPF_JSGT:
+		return BPF_JSLE;
+	case BPF_JSLT:
+		return BPF_JSGE;
+	case BPF_JSGE:
+		return BPF_JSLT;
+	case BPF_JSLE:
+		return BPF_JSGT;
+	}
+	return -1;
+}
+
+static void emit_bcc(u8 cond, u8 rd, u8 rs, int rvoff,
+		     struct rv_jit_context *ctx)
+{
+	switch (cond) {
+	case BPF_JEQ:
+		emit(rv_beq(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JGT:
+		emit(rv_bltu(rs, rd, rvoff >> 1), ctx);
+		return;
+	case BPF_JLT:
+		emit(rv_bltu(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JGE:
+		emit(rv_bgeu(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JLE:
+		emit(rv_bgeu(rs, rd, rvoff >> 1), ctx);
+		return;
+	case BPF_JNE:
+		emit(rv_bne(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JSGT:
+		emit(rv_blt(rs, rd, rvoff >> 1), ctx);
+		return;
+	case BPF_JSLT:
+		emit(rv_blt(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JSGE:
+		emit(rv_bge(rd, rs, rvoff >> 1), ctx);
+		return;
+	case BPF_JSLE:
+		emit(rv_bge(rs, rd, rvoff >> 1), ctx);
+	}
+}
+
+static void emit_branch(u8 cond, u8 rd, u8 rs, int rvoff,
+			struct rv_jit_context *ctx)
+{
+	s64 upper, lower;
+
+	if (is_13b_int(rvoff)) {
+		emit_bcc(cond, rd, rs, rvoff, ctx);
+		return;
+	}
+
+	/* Adjust for jal */
+	rvoff -= 4;
+
+	/* Transform, e.g.:
+	 *   bne rd,rs,foo
+	 * to
+	 *   beq rd,rs,<.L1>
+	 *   (auipc foo)
+	 *   jal(r) foo
+	 * .L1
+	 */
+	cond = invert_bpf_cond(cond);
+	if (is_21b_int(rvoff)) {
+		emit_bcc(cond, rd, rs, 8, ctx);
+		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
+		return;
+	}
+
+	/* 32b No need for an additional rvoff adjustment, since we
+	 * get that from the auipc at PC', where PC = PC' + 4.
+	 */
+	upper = (rvoff + (1 << 11)) >> 12;
+	lower = rvoff & 0xfff;
+
+	emit_bcc(cond, rd, rs, 12, ctx);
+	emit(rv_auipc(RV_REG_T1, upper), ctx);
+	emit(rv_jalr(RV_REG_ZERO, RV_REG_T1, lower), ctx);
+}
+
 static void emit_zext_32(u8 reg, struct rv_jit_context *ctx)
 {
 	emit(rv_slli(reg, reg, 32), ctx);
@@ -693,13 +804,6 @@ static void init_regs(u8 *rd, u8 *rs, const struct bpf_insn *insn,
 		*rs = bpf_to_rv_reg(insn->src_reg, ctx);
 }
 
-static int rv_offset_check(int *rvoff, s16 off, int insn,
-			   struct rv_jit_context *ctx)
-{
-	*rvoff = rv_offset(insn + off, insn, ctx);
-	return is_13b_check(*rvoff, insn);
-}
-
 static void emit_zext_32_rd_rs(u8 *rd, u8 *rs, struct rv_jit_context *ctx)
 {
 	emit(rv_addi(RV_REG_T2, *rd, 0), ctx);
@@ -732,13 +836,19 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
 	*rd = RV_REG_T2;
 }
 
+static bool is_signed_bpf_cond(u8 cond)
+{
+	return cond == BPF_JSGT || cond == BPF_JSLT ||
+		cond == BPF_JSGE || cond == BPF_JSLE;
+}
+
 static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 		     bool extra_pass)
 {
 	bool is64 = BPF_CLASS(insn->code) == BPF_ALU64 ||
 		    BPF_CLASS(insn->code) == BPF_JMP;
+	int s, e, rvoff, i = insn - ctx->prog->insnsi;
 	struct bpf_prog_aux *aux = ctx->prog->aux;
-	int rvoff, i = insn - ctx->prog->insnsi;
 	u8 rd = -1, rs = -1, code = insn->code;
 	s16 off = insn->off;
 	s32 imm = insn->imm;
@@ -1006,7 +1116,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 
 	/* JUMP off */
 	case BPF_JMP | BPF_JA:
-		rvoff = rv_offset(i + off, i, ctx);
+		rvoff = rv_offset(i, off, ctx);
 		if (!is_21b_int(rvoff)) {
 			pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
 			       i, rvoff);
@@ -1019,194 +1129,96 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 	/* IF (dst COND src) JUMP off */
 	case BPF_JMP | BPF_JEQ | BPF_X:
 	case BPF_JMP32 | BPF_JEQ | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_beq(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JGT | BPF_X:
 	case BPF_JMP32 | BPF_JGT | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bltu(rs, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JLT | BPF_X:
 	case BPF_JMP32 | BPF_JLT | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bltu(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JGE | BPF_X:
 	case BPF_JMP32 | BPF_JGE | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bgeu(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JLE | BPF_X:
 	case BPF_JMP32 | BPF_JLE | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bgeu(rs, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JNE | BPF_X:
 	case BPF_JMP32 | BPF_JNE | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bne(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSGT | BPF_X:
 	case BPF_JMP32 | BPF_JSGT | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_sext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_blt(rs, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSLT | BPF_X:
 	case BPF_JMP32 | BPF_JSLT | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_sext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_blt(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSGE | BPF_X:
 	case BPF_JMP32 | BPF_JSGE | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_sext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bge(rd, rs, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSLE | BPF_X:
 	case BPF_JMP32 | BPF_JSLE | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_sext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_bge(rs, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSET | BPF_X:
 	case BPF_JMP32 | BPF_JSET | BPF_X:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		if (!is64)
-			emit_zext_32_rd_rs(&rd, &rs, ctx);
-		emit(rv_and(RV_REG_T1, rd, rs), ctx);
-		emit(rv_bne(RV_REG_T1, RV_REG_ZERO, rvoff >> 1), ctx);
+		rvoff = rv_offset(i, off, ctx);
+		if (!is64) {
+			s = ctx->ninsns;
+			if (is_signed_bpf_cond(BPF_OP(code)))
+				emit_sext_32_rd_rs(&rd, &rs, ctx);
+			else
+				emit_zext_32_rd_rs(&rd, &rs, ctx);
+			e = ctx->ninsns;
+
+			/* Adjust for extra insns */
+			rvoff -= (e - s) << 2;
+		}
+
+		if (BPF_OP(code) == BPF_JSET) {
+			/* Adjust for and */
+			rvoff -= 4;
+			emit(rv_and(RV_REG_T1, rd, rs), ctx);
+			emit_branch(BPF_JNE, RV_REG_T1, RV_REG_ZERO, rvoff,
+				    ctx);
+		} else {
+			emit_branch(BPF_OP(code), rd, rs, rvoff, ctx);
+		}
 		break;
 
 	/* IF (dst COND imm) JUMP off */
 	case BPF_JMP | BPF_JEQ | BPF_K:
 	case BPF_JMP32 | BPF_JEQ | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_beq(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JGT | BPF_K:
 	case BPF_JMP32 | BPF_JGT | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_bltu(RV_REG_T1, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JLT | BPF_K:
 	case BPF_JMP32 | BPF_JLT | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_bltu(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JGE | BPF_K:
 	case BPF_JMP32 | BPF_JGE | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_bgeu(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JLE | BPF_K:
 	case BPF_JMP32 | BPF_JLE | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_bgeu(RV_REG_T1, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JNE | BPF_K:
 	case BPF_JMP32 | BPF_JNE | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_bne(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSGT | BPF_K:
 	case BPF_JMP32 | BPF_JSGT | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_sext_32_rd(&rd, ctx);
-		emit(rv_blt(RV_REG_T1, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSLT | BPF_K:
 	case BPF_JMP32 | BPF_JSLT | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_sext_32_rd(&rd, ctx);
-		emit(rv_blt(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSGE | BPF_K:
 	case BPF_JMP32 | BPF_JSGE | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_sext_32_rd(&rd, ctx);
-		emit(rv_bge(rd, RV_REG_T1, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSLE | BPF_K:
 	case BPF_JMP32 | BPF_JSLE | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
-		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_sext_32_rd(&rd, ctx);
-		emit(rv_bge(RV_REG_T1, rd, rvoff >> 1), ctx);
-		break;
 	case BPF_JMP | BPF_JSET | BPF_K:
 	case BPF_JMP32 | BPF_JSET | BPF_K:
-		if (rv_offset_check(&rvoff, off, i, ctx))
-			return -1;
+		rvoff = rv_offset(i, off, ctx);
+		s = ctx->ninsns;
 		emit_imm(RV_REG_T1, imm, ctx);
-		if (!is64)
-			emit_zext_32_rd_t1(&rd, ctx);
-		emit(rv_and(RV_REG_T1, rd, RV_REG_T1), ctx);
-		emit(rv_bne(RV_REG_T1, RV_REG_ZERO, rvoff >> 1), ctx);
+		if (!is64) {
+			if (is_signed_bpf_cond(BPF_OP(code)))
+				emit_sext_32_rd(&rd, ctx);
+			else
+				emit_zext_32_rd_t1(&rd, ctx);
+		}
+		e = ctx->ninsns;
+
+		/* Adjust for extra insns */
+		rvoff -= (e - s) << 2;
+
+		if (BPF_OP(code) == BPF_JSET) {
+			/* Adjust for and */
+			rvoff -= 4;
+			emit(rv_and(RV_REG_T1, rd, RV_REG_T1), ctx);
+			emit_branch(BPF_JNE, RV_REG_T1, RV_REG_ZERO, rvoff,
+				    ctx);
+		} else {
+			emit_branch(BPF_OP(code), rd, RV_REG_T1, rvoff, ctx);
+		}
 		break;
 
 	/* function call */
@@ -1557,6 +1569,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 {
 	bool tmp_blinded = false, extra_pass = false;
 	struct bpf_prog *tmp, *orig_prog = prog;
+	int pass = 0, prev_ninsns = 0, i;
 	struct rv_jit_data *jit_data;
 	struct rv_jit_context *ctx;
 	unsigned int image_size;
@@ -1596,15 +1609,25 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 		prog = orig_prog;
 		goto out_offset;
 	}
+	for (i = 0; i < prog->len; i++) {
+		prev_ninsns += 32;
+		ctx->offset[i] = prev_ninsns;
+	}
 
-	/* First pass generates the ctx->offset, but does not emit an image. */
-	if (build_body(ctx, extra_pass)) {
-		prog = orig_prog;
-		goto out_offset;
+	for (i = 0; i < 16; i++) {
+		pass++;
+		ctx->ninsns = 0;
+		if (build_body(ctx, extra_pass)) {
+			prog = orig_prog;
+			goto out_offset;
+		}
+		build_prologue(ctx);
+		ctx->epilogue_offset = ctx->ninsns;
+		build_epilogue(ctx);
+		if (ctx->ninsns == prev_ninsns)
+			break;
+		prev_ninsns = ctx->ninsns;
 	}
-	build_prologue(ctx);
-	ctx->epilogue_offset = ctx->ninsns;
-	build_epilogue(ctx);
 
 	/* Allocate image, now that we know the size. */
 	image_size = sizeof(u32) * ctx->ninsns;
@@ -1619,6 +1642,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	/* Second, real pass, that acutally emits the image. */
 	ctx->insns = (u32 *)jit_data->image;
 skip_init_ctx:
+	pass++;
 	ctx->ninsns = 0;
 
 	build_prologue(ctx);
@@ -1630,7 +1654,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	build_epilogue(ctx);
 
 	if (bpf_jit_enable > 1)
-		bpf_jit_dump(prog->len, image_size, 2, ctx->insns);
+		bpf_jit_dump(prog->len, image_size, pass, ctx->insns);
 
 	prog->bpf_func = (void *)ctx->insns;
 	prog->jited = 1;
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Björn Töpel
                   ` (15 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

Start use the emit_branch() function in the tail call emitter in order
to support far branching.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 22 +++-------------------
 1 file changed, 3 insertions(+), 19 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index e599458a9bcd..c38c95df3440 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -496,16 +496,6 @@ static int is_12b_check(int off, int insn)
 	return 0;
 }
 
-static int is_13b_check(int off, int insn)
-{
-	if (!is_13b_int(off)) {
-		pr_err("bpf-jit: insn=%d 13b < offset=%d not supported yet!\n",
-		       insn, (int)off);
-		return -1;
-	}
-	return 0;
-}
-
 static int is_21b_check(int off, int insn)
 {
 	if (!is_21b_int(off)) {
@@ -744,18 +734,14 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
 		return -1;
 	emit(rv_lwu(RV_REG_T1, off, RV_REG_A1), ctx);
 	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
-	if (is_13b_check(off, insn))
-		return -1;
-	emit(rv_bgeu(RV_REG_A2, RV_REG_T1, off >> 1), ctx);
+	emit_branch(BPF_JGE, RV_REG_A2, RV_REG_T1, off, ctx);
 
 	/* if (--TCC < 0)
 	 *     goto out;
 	 */
 	emit(rv_addi(RV_REG_T1, tcc, -1), ctx);
 	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
-	if (is_13b_check(off, insn))
-		return -1;
-	emit(rv_blt(RV_REG_T1, RV_REG_ZERO, off >> 1), ctx);
+	emit_branch(BPF_JSLT, RV_REG_T1, RV_REG_ZERO, off, ctx);
 
 	/* prog = array->ptrs[index];
 	 * if (!prog)
@@ -768,9 +754,7 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
 		return -1;
 	emit(rv_ld(RV_REG_T2, off, RV_REG_T2), ctx);
 	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
-	if (is_13b_check(off, insn))
-		return -1;
-	emit(rv_beq(RV_REG_T2, RV_REG_ZERO, off >> 1), ctx);
+	emit_branch(BPF_JEQ, RV_REG_T2, RV_REG_ZERO, off, ctx);
 
 	/* goto *(prog->bpf_func + 4); */
 	off = offsetof(struct bpf_prog, bpf_func);
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (2 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Björn Töpel
                   ` (14 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev
  Cc: Björn Töpel, linux-riscv, Luke Nelson, bpf, Xi Wang

This commit add support for far (offset > 21b) jumps and exits.

Reviewed-by: Luke Nelson <lukenels@cs.washington.edu>
Cc: Xi Wang <xi.wang@gmail.com>
Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 37 ++++++++++++++++-------------------
 1 file changed, 17 insertions(+), 20 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index c38c95df3440..2fc0f24ad30f 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -496,16 +496,6 @@ static int is_12b_check(int off, int insn)
 	return 0;
 }
 
-static int is_21b_check(int off, int insn)
-{
-	if (!is_21b_int(off)) {
-		pr_err("bpf-jit: insn=%d 21b < offset=%d not supported yet!\n",
-		       insn, (int)off);
-		return -1;
-	}
-	return 0;
-}
-
 static void emit_imm(u8 rd, s64 val, struct rv_jit_context *ctx)
 {
 	/* Note that the immediate from the add is sign-extended,
@@ -820,6 +810,21 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
 	*rd = RV_REG_T2;
 }
 
+static void emit_jump_and_link(u8 rd, int rvoff, struct rv_jit_context *ctx)
+{
+	s64 upper, lower;
+
+	if (is_21b_int(rvoff)) {
+		emit(rv_jal(rd, rvoff >> 1), ctx);
+		return;
+	}
+
+	upper = (rvoff + (1 << 11)) >> 12;
+	lower = rvoff & 0xfff;
+	emit(rv_auipc(RV_REG_T1, upper), ctx);
+	emit(rv_jalr(rd, RV_REG_T1, lower), ctx);
+}
+
 static bool is_signed_bpf_cond(u8 cond)
 {
 	return cond == BPF_JSGT || cond == BPF_JSLT ||
@@ -1101,13 +1106,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 	/* JUMP off */
 	case BPF_JMP | BPF_JA:
 		rvoff = rv_offset(i, off, ctx);
-		if (!is_21b_int(rvoff)) {
-			pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
-			       i, rvoff);
-			return -1;
-		}
-
-		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
+		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
 		break;
 
 	/* IF (dst COND src) JUMP off */
@@ -1245,9 +1244,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 			break;
 
 		rvoff = epilogue_offset(ctx);
-		if (is_21b_check(rvoff, i))
-			return -1;
-		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
+		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
 		break;
 
 	/* dst = imm64 */
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (3 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Björn Töpel
                   ` (13 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

Remove one addi, and instead use the offset part of jalr.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index 2fc0f24ad30f..8aa19c846881 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -552,7 +552,7 @@ static int epilogue_offset(struct rv_jit_context *ctx)
 	return (to - from) << 2;
 }
 
-static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
+static void __build_epilogue(bool is_tail_call, struct rv_jit_context *ctx)
 {
 	int stack_adjust = ctx->stack_size, store_offset = stack_adjust - 8;
 
@@ -589,9 +589,11 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
 
 	emit(rv_addi(RV_REG_SP, RV_REG_SP, stack_adjust), ctx);
 	/* Set return value. */
-	if (reg == RV_REG_RA)
+	if (!is_tail_call)
 		emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
-	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
+	emit(rv_jalr(RV_REG_ZERO, is_tail_call ? RV_REG_T3 : RV_REG_RA,
+		     is_tail_call ? 4 : 0), /* skip TCC init */
+	     ctx);
 }
 
 /* return -1 or inverted cond */
@@ -751,9 +753,8 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
 	if (is_12b_check(off, insn))
 		return -1;
 	emit(rv_ld(RV_REG_T3, off, RV_REG_T2), ctx);
-	emit(rv_addi(RV_REG_T3, RV_REG_T3, 4), ctx);
 	emit(rv_addi(RV_REG_TCC, RV_REG_T1, 0), ctx);
-	__build_epilogue(RV_REG_T3, ctx);
+	__build_epilogue(true, ctx);
 	return 0;
 }
 
@@ -1504,7 +1505,7 @@ static void build_prologue(struct rv_jit_context *ctx)
 
 static void build_epilogue(struct rv_jit_context *ctx)
 {
-	__build_epilogue(RV_REG_RA, ctx);
+	__build_epilogue(false, ctx);
 }
 
 static int build_body(struct rv_jit_context *ctx, bool extra_pass)
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (4 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16 15:09   ` Daniel Borkmann
  2019-12-16  9:13 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Björn Töpel
                   ` (12 subsequent siblings)
  18 siblings, 1 reply; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

This commit makes sure that the JIT images is kept close to the kernel
text, so BPF calls can use relative calling with auipc/jalr or jal
instead of loading the full 64-bit address and jalr.

The BPF JIT image region is 128 MB before the kernel text.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/include/asm/pgtable.h |  4 ++++
 arch/riscv/net/bpf_jit_comp.c    | 13 +++++++++++++
 2 files changed, 17 insertions(+)

diff --git a/arch/riscv/include/asm/pgtable.h b/arch/riscv/include/asm/pgtable.h
index 7ff0ed4f292e..cc3f49415620 100644
--- a/arch/riscv/include/asm/pgtable.h
+++ b/arch/riscv/include/asm/pgtable.h
@@ -404,6 +404,10 @@ static inline int ptep_clear_flush_young(struct vm_area_struct *vma,
 #define VMALLOC_END      (PAGE_OFFSET - 1)
 #define VMALLOC_START    (PAGE_OFFSET - VMALLOC_SIZE)
 
+#define BPF_JIT_REGION_SIZE	(SZ_128M)
+#define BPF_JIT_REGION_START	(PAGE_OFFSET - BPF_JIT_REGION_SIZE)
+#define BPF_JIT_REGION_END	(VMALLOC_END)
+
 /*
  * Roughly size the vmemmap space to be large enough to fit enough
  * struct pages to map half the virtual address space. Then
diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index 8aa19c846881..46cff093f526 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -1656,3 +1656,16 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 					   tmp : orig_prog);
 	return prog;
 }
+
+void *bpf_jit_alloc_exec(unsigned long size)
+{
+	return __vmalloc_node_range(size, PAGE_SIZE, BPF_JIT_REGION_START,
+				    BPF_JIT_REGION_END, GFP_KERNEL,
+				    PAGE_KERNEL_EXEC, 0, NUMA_NO_NODE,
+				    __builtin_return_address(0));
+}
+
+void bpf_jit_free_exec(void *addr)
+{
+	return vfree(addr);
+}
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (5 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Björn Töpel
                   ` (11 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

Instead of using emit_imm() and emit_jalr() which can expand to six
instructions, start using jal or auipc+jalr.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/net/bpf_jit_comp.c | 101 +++++++++++++++++++++-------------
 1 file changed, 64 insertions(+), 37 deletions(-)

diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
index 46cff093f526..8d7e3343a08c 100644
--- a/arch/riscv/net/bpf_jit_comp.c
+++ b/arch/riscv/net/bpf_jit_comp.c
@@ -811,11 +811,12 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
 	*rd = RV_REG_T2;
 }
 
-static void emit_jump_and_link(u8 rd, int rvoff, struct rv_jit_context *ctx)
+static void emit_jump_and_link(u8 rd, s64 rvoff, bool force_jalr,
+			       struct rv_jit_context *ctx)
 {
 	s64 upper, lower;
 
-	if (is_21b_int(rvoff)) {
+	if (rvoff && is_21b_int(rvoff) && !force_jalr) {
 		emit(rv_jal(rd, rvoff >> 1), ctx);
 		return;
 	}
@@ -832,6 +833,28 @@ static bool is_signed_bpf_cond(u8 cond)
 		cond == BPF_JSGE || cond == BPF_JSLE;
 }
 
+static int emit_call(bool fixed, u64 addr, struct rv_jit_context *ctx)
+{
+	s64 off = 0;
+	u64 ip;
+	u8 rd;
+
+	if (addr && ctx->insns) {
+		ip = (u64)(long)(ctx->insns + ctx->ninsns);
+		off = addr - ip;
+		if (!is_32b_int(off)) {
+			pr_err("bpf-jit: target call addr %pK is out of range\n",
+			       (void *)addr);
+			return -ERANGE;
+		}
+	}
+
+	emit_jump_and_link(RV_REG_RA, off, !fixed, ctx);
+	rd = bpf_to_rv_reg(BPF_REG_0, ctx);
+	emit(rv_addi(rd, RV_REG_A0, 0), ctx);
+	return 0;
+}
+
 static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 		     bool extra_pass)
 {
@@ -1107,7 +1130,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 	/* JUMP off */
 	case BPF_JMP | BPF_JA:
 		rvoff = rv_offset(i, off, ctx);
-		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
+		emit_jump_and_link(RV_REG_ZERO, rvoff, false, ctx);
 		break;
 
 	/* IF (dst COND src) JUMP off */
@@ -1209,7 +1232,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 	case BPF_JMP | BPF_CALL:
 	{
 		bool fixed;
-		int i, ret;
+		int ret;
 		u64 addr;
 
 		mark_call(ctx);
@@ -1217,20 +1240,9 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 					    &fixed);
 		if (ret < 0)
 			return ret;
-		if (fixed) {
-			emit_imm(RV_REG_T1, addr, ctx);
-		} else {
-			i = ctx->ninsns;
-			emit_imm(RV_REG_T1, addr, ctx);
-			for (i = ctx->ninsns - i; i < 8; i++) {
-				/* nop */
-				emit(rv_addi(RV_REG_ZERO, RV_REG_ZERO, 0),
-				     ctx);
-			}
-		}
-		emit(rv_jalr(RV_REG_RA, RV_REG_T1, 0), ctx);
-		rd = bpf_to_rv_reg(BPF_REG_0, ctx);
-		emit(rv_addi(rd, RV_REG_A0, 0), ctx);
+		ret = emit_call(fixed, addr, ctx);
+		if (ret)
+			return ret;
 		break;
 	}
 	/* tail call */
@@ -1245,7 +1257,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
 			break;
 
 		rvoff = epilogue_offset(ctx);
-		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
+		emit_jump_and_link(RV_REG_ZERO, rvoff, false, ctx);
 		break;
 
 	/* dst = imm64 */
@@ -1508,7 +1520,7 @@ static void build_epilogue(struct rv_jit_context *ctx)
 	__build_epilogue(false, ctx);
 }
 
-static int build_body(struct rv_jit_context *ctx, bool extra_pass)
+static int build_body(struct rv_jit_context *ctx, bool extra_pass, int *offset)
 {
 	const struct bpf_prog *prog = ctx->prog;
 	int i;
@@ -1520,12 +1532,12 @@ static int build_body(struct rv_jit_context *ctx, bool extra_pass)
 		ret = emit_insn(insn, ctx, extra_pass);
 		if (ret > 0) {
 			i++;
-			if (ctx->insns == NULL)
-				ctx->offset[i] = ctx->ninsns;
+			if (offset)
+				offset[i] = ctx->ninsns;
 			continue;
 		}
-		if (ctx->insns == NULL)
-			ctx->offset[i] = ctx->ninsns;
+		if (offset)
+			offset[i] = ctx->ninsns;
 		if (ret)
 			return ret;
 	}
@@ -1553,8 +1565,8 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	struct bpf_prog *tmp, *orig_prog = prog;
 	int pass = 0, prev_ninsns = 0, i;
 	struct rv_jit_data *jit_data;
+	unsigned int image_size = 0;
 	struct rv_jit_context *ctx;
-	unsigned int image_size;
 
 	if (!prog->jit_requested)
 		return orig_prog;
@@ -1599,36 +1611,51 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	for (i = 0; i < 16; i++) {
 		pass++;
 		ctx->ninsns = 0;
-		if (build_body(ctx, extra_pass)) {
+		if (build_body(ctx, extra_pass, ctx->offset)) {
 			prog = orig_prog;
 			goto out_offset;
 		}
 		build_prologue(ctx);
 		ctx->epilogue_offset = ctx->ninsns;
 		build_epilogue(ctx);
-		if (ctx->ninsns == prev_ninsns)
-			break;
+
+		if (ctx->ninsns == prev_ninsns) {
+			if (jit_data->header)
+				break;
+
+			image_size = sizeof(u32) * ctx->ninsns;
+			jit_data->header =
+				bpf_jit_binary_alloc(image_size,
+						     &jit_data->image,
+						     sizeof(u32),
+						     bpf_fill_ill_insns);
+			if (!jit_data->header) {
+				prog = orig_prog;
+				goto out_offset;
+			}
+
+			ctx->insns = (u32 *)jit_data->image;
+			/* Now, when the image is allocated, the image
+			 * can potentially shrink more (auipc/jalr ->
+			 * jal).
+			 */
+		}
 		prev_ninsns = ctx->ninsns;
 	}
 
-	/* Allocate image, now that we know the size. */
-	image_size = sizeof(u32) * ctx->ninsns;
-	jit_data->header = bpf_jit_binary_alloc(image_size, &jit_data->image,
-						sizeof(u32),
-						bpf_fill_ill_insns);
-	if (!jit_data->header) {
+	if (i == 16) {
+		pr_err("bpf-jit: image did not converge in <%d passes!\n", i);
+		bpf_jit_binary_free(jit_data->header);
 		prog = orig_prog;
 		goto out_offset;
 	}
 
-	/* Second, real pass, that acutally emits the image. */
-	ctx->insns = (u32 *)jit_data->image;
 skip_init_ctx:
 	pass++;
 	ctx->ninsns = 0;
 
 	build_prologue(ctx);
-	if (build_body(ctx, extra_pass)) {
+	if (build_body(ctx, extra_pass, NULL)) {
 		bpf_jit_binary_free(jit_data->header);
 		prog = orig_prog;
 		goto out_offset;
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (6 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-16  9:13 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Björn Töpel
                   ` (10 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

Add missing uapi header the BPF_PROG_TYPE_PERF_EVENT programs by
exporting struct user_regs_struct instead of struct pt_regs which is
in-kernel only.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/include/uapi/asm/bpf_perf_event.h | 9 +++++++++
 tools/include/uapi/asm/bpf_perf_event.h      | 2 ++
 2 files changed, 11 insertions(+)
 create mode 100644 arch/riscv/include/uapi/asm/bpf_perf_event.h

diff --git a/arch/riscv/include/uapi/asm/bpf_perf_event.h b/arch/riscv/include/uapi/asm/bpf_perf_event.h
new file mode 100644
index 000000000000..6cb1c2823288
--- /dev/null
+++ b/arch/riscv/include/uapi/asm/bpf_perf_event.h
@@ -0,0 +1,9 @@
+/* SPDX-License-Identifier: GPL-2.0 WITH Linux-syscall-note */
+#ifndef _UAPI__ASM_BPF_PERF_EVENT_H__
+#define _UAPI__ASM_BPF_PERF_EVENT_H__
+
+#include <asm/ptrace.h>
+
+typedef struct user_regs_struct bpf_user_pt_regs_t;
+
+#endif /* _UAPI__ASM_BPF_PERF_EVENT_H__ */
diff --git a/tools/include/uapi/asm/bpf_perf_event.h b/tools/include/uapi/asm/bpf_perf_event.h
index 13a58531e6fa..39acc149d843 100644
--- a/tools/include/uapi/asm/bpf_perf_event.h
+++ b/tools/include/uapi/asm/bpf_perf_event.h
@@ -2,6 +2,8 @@
 #include "../../arch/arm64/include/uapi/asm/bpf_perf_event.h"
 #elif defined(__s390__)
 #include "../../arch/s390/include/uapi/asm/bpf_perf_event.h"
+#elif defined(__riscv)
+#include "../../arch/riscv/include/uapi/asm/bpf_perf_event.h"
 #else
 #include <uapi/asm-generic/bpf_perf_event.h>
 #endif
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (7 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Björn Töpel
@ 2019-12-16  9:13 ` Björn Töpel
  2019-12-19 15:07 ` [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Daniel Borkmann
                   ` (9 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2019-12-16  9:13 UTC (permalink / raw)
  To: daniel, ast, netdev; +Cc: Björn Töpel, linux-riscv, bpf

RISC-V was missing a proper perf_arch_bpf_user_pt_regs macro for
CONFIG_PERF_EVENT builds.

Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
---
 arch/riscv/include/asm/perf_event.h | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/riscv/include/asm/perf_event.h b/arch/riscv/include/asm/perf_event.h
index aefbfaa6a781..0234048b12bc 100644
--- a/arch/riscv/include/asm/perf_event.h
+++ b/arch/riscv/include/asm/perf_event.h
@@ -82,4 +82,8 @@ struct riscv_pmu {
 	int		irq;
 };
 
+#ifdef CONFIG_PERF_EVENTS
+#define perf_arch_bpf_user_pt_regs(regs) (struct user_regs_struct *)regs
+#endif
+
 #endif /* _ASM_RISCV_PERF_EVENT_H */
-- 
2.20.1



^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2019-12-16  9:13 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Björn Töpel
@ 2019-12-16 15:09   ` Daniel Borkmann
  2019-12-18  6:23     ` Björn Töpel
  0 siblings, 1 reply; 28+ messages in thread
From: Daniel Borkmann @ 2019-12-16 15:09 UTC (permalink / raw)
  To: Björn Töpel, ast, netdev
  Cc: linux-riscv, aou, palmer, bpf, paul.walmsley

On 12/16/19 10:13 AM, Björn Töpel wrote:
> This commit makes sure that the JIT images is kept close to the kernel
> text, so BPF calls can use relative calling with auipc/jalr or jal
> instead of loading the full 64-bit address and jalr.
> 
> The BPF JIT image region is 128 MB before the kernel text.
> 
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>   arch/riscv/include/asm/pgtable.h |  4 ++++
>   arch/riscv/net/bpf_jit_comp.c    | 13 +++++++++++++
>   2 files changed, 17 insertions(+)
> 
> diff --git a/arch/riscv/include/asm/pgtable.h b/arch/riscv/include/asm/pgtable.h
> index 7ff0ed4f292e..cc3f49415620 100644
> --- a/arch/riscv/include/asm/pgtable.h
> +++ b/arch/riscv/include/asm/pgtable.h
> @@ -404,6 +404,10 @@ static inline int ptep_clear_flush_young(struct vm_area_struct *vma,
>   #define VMALLOC_END      (PAGE_OFFSET - 1)
>   #define VMALLOC_START    (PAGE_OFFSET - VMALLOC_SIZE)
>   
> +#define BPF_JIT_REGION_SIZE	(SZ_128M)
> +#define BPF_JIT_REGION_START	(PAGE_OFFSET - BPF_JIT_REGION_SIZE)
> +#define BPF_JIT_REGION_END	(VMALLOC_END)
> +

Series looks good to me, thanks; I'd like to get an ACK from Palmer/others on this one.

>   /*
>    * Roughly size the vmemmap space to be large enough to fit enough
>    * struct pages to map half the virtual address space. Then
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 8aa19c846881..46cff093f526 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -1656,3 +1656,16 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>   					   tmp : orig_prog);
>   	return prog;
>   }
> +
> +void *bpf_jit_alloc_exec(unsigned long size)
> +{
> +	return __vmalloc_node_range(size, PAGE_SIZE, BPF_JIT_REGION_START,
> +				    BPF_JIT_REGION_END, GFP_KERNEL,
> +				    PAGE_KERNEL_EXEC, 0, NUMA_NO_NODE,
> +				    __builtin_return_address(0));
> +}
> +
> +void bpf_jit_free_exec(void *addr)
> +{
> +	return vfree(addr);
> +}
> 



^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2019-12-16 15:09   ` Daniel Borkmann
@ 2019-12-18  6:23     ` Björn Töpel
  2020-01-04  1:32       ` Paul Walmsley
  0 siblings, 1 reply; 28+ messages in thread
From: Björn Töpel @ 2019-12-18  6:23 UTC (permalink / raw)
  To: Daniel Borkmann, Paul Walmsley, Palmer Dabbelt, Albert Ou
  Cc: Netdev, linux-riscv, bpf, Alexei Starovoitov

On Mon, 16 Dec 2019 at 16:09, Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> On 12/16/19 10:13 AM, Björn Töpel wrote:
> > This commit makes sure that the JIT images is kept close to the kernel
> > text, so BPF calls can use relative calling with auipc/jalr or jal
> > instead of loading the full 64-bit address and jalr.
> >
> > The BPF JIT image region is 128 MB before the kernel text.
> >
> > Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> > ---
> >   arch/riscv/include/asm/pgtable.h |  4 ++++
> >   arch/riscv/net/bpf_jit_comp.c    | 13 +++++++++++++
> >   2 files changed, 17 insertions(+)
> >
> > diff --git a/arch/riscv/include/asm/pgtable.h b/arch/riscv/include/asm/pgtable.h
> > index 7ff0ed4f292e..cc3f49415620 100644
> > --- a/arch/riscv/include/asm/pgtable.h
> > +++ b/arch/riscv/include/asm/pgtable.h
> > @@ -404,6 +404,10 @@ static inline int ptep_clear_flush_young(struct vm_area_struct *vma,
> >   #define VMALLOC_END      (PAGE_OFFSET - 1)
> >   #define VMALLOC_START    (PAGE_OFFSET - VMALLOC_SIZE)
> >
> > +#define BPF_JIT_REGION_SIZE  (SZ_128M)
> > +#define BPF_JIT_REGION_START (PAGE_OFFSET - BPF_JIT_REGION_SIZE)
> > +#define BPF_JIT_REGION_END   (VMALLOC_END)
> > +
>
> Series looks good to me, thanks; I'd like to get an ACK from Palmer/others on this one.
>

Palmer/Paul/Albert, any thoughts/input? I can respin the the series
w/o the call optimizations (excluding this patch and the next), but
I'd prefer not given it's a nice speed/clean up for calls.


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (8 preceding siblings ...)
  2019-12-16  9:13 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Björn Töpel
@ 2019-12-19 15:07 ` Daniel Borkmann
  2019-12-19 22:02 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Palmer Dabbelt
                   ` (8 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Daniel Borkmann @ 2019-12-19 15:07 UTC (permalink / raw)
  To: Björn Töpel; +Cc: netdev, linux-riscv, bpf, ast

On Mon, Dec 16, 2019 at 10:13:34AM +0100, Björn Töpel wrote:
> 
> This series contain one non-critical fix, support for far jumps. and
> some optimizations for the BPF JIT.
> 
> Previously, the JIT only supported 12b branch targets for conditional
> branches, and 21b for unconditional branches. Starting with this
> series, 32b branching is supported.
> 
> As part of supporting far jumps, branch relaxation was introduced. The
> idea is to start with a pessimistic jump (e.g. auipc/jalr) and for
> each pass the JIT will have an opportunity to pick a better
> instruction (e.g. jal) and shrink the image. Instead of two passes,
> the JIT requires more passes. It typically converges after 3 passes.
> 
> The optimizations mentioned in the subject are for calls and tail
> calls. In the tail call generation we can save one instruction by
> using the offset in jalr. Calls are optimized by doing (auipc)/jal(r)
> relative jumps instead of loading the entire absolute address and
> doing jalr. This required that the JIT image allocator was made RISC-V
> specific, so we can ensure that the JIT image and the kernel text are
> in range (32b).
> 
> The last two patches of the series is not critical to the series, but
> are two UAPI build issues for BPF events. A closer look from the
> RV-folks would be much appreciated.
> 
> The test_bpf.ko module, selftests/bpf/test_verifier and
> selftests/seccomp/seccomp_bpf pass all tests.
> 
> RISC-V is still missing proper kprobe and tracepoint support, so a lot
> of BPF selftests cannot be run.

Applied, thanks!


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (9 preceding siblings ...)
  2019-12-19 15:07 ` [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Daniel Borkmann
@ 2019-12-19 22:02 ` Palmer Dabbelt
  2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
                   ` (7 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-19 22:02 UTC (permalink / raw)
  To: Björn Töpel
  Cc: daniel, netdev, ast, Björn Töpel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:35 PST (-0800), Björn Töpel wrote:
> The BPF JIT incorrectly clobbered the a0 register, and did not flag
> usage of s5 register when BPF stack was being used.
>
> Fixes: 2353ecc6f91f ("bpf, riscv: add BPF JIT for RV64G")
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 13 +++++++++++--
>  1 file changed, 11 insertions(+), 2 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 5451ef3845f2..1606ebd49666 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -120,6 +120,11 @@ static bool seen_reg(int reg, struct rv_jit_context *ctx)
>  	return false;
>  }
>
> +static void mark_fp(struct rv_jit_context *ctx)
> +{
> +	__set_bit(RV_CTX_F_SEEN_S5, &ctx->flags);
> +}
> +
>  static void mark_call(struct rv_jit_context *ctx)
>  {
>  	__set_bit(RV_CTX_F_SEEN_CALL, &ctx->flags);
> @@ -596,7 +601,8 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
>
>  	emit(rv_addi(RV_REG_SP, RV_REG_SP, stack_adjust), ctx);
>  	/* Set return value. */
> -	emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
> +	if (reg == RV_REG_RA)
> +		emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
>  	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
>  }
>
> @@ -1426,6 +1432,10 @@ static void build_prologue(struct rv_jit_context *ctx)
>  {
>  	int stack_adjust = 0, store_offset, bpf_stack_adjust;
>
> +	bpf_stack_adjust = round_up(ctx->prog->aux->stack_depth, 16);
> +	if (bpf_stack_adjust)
> +		mark_fp(ctx);
> +
>  	if (seen_reg(RV_REG_RA, ctx))
>  		stack_adjust += 8;
>  	stack_adjust += 8; /* RV_REG_FP */
> @@ -1443,7 +1453,6 @@ static void build_prologue(struct rv_jit_context *ctx)
>  		stack_adjust += 8;
>
>  	stack_adjust = round_up(stack_adjust, 16);
> -	bpf_stack_adjust = round_up(ctx->prog->aux->stack_depth, 16);
>  	stack_adjust += bpf_stack_adjust;
>
>  	store_offset = stack_adjust - 8;

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (10 preceding siblings ...)
  2019-12-19 22:02 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Palmer Dabbelt
@ 2019-12-23 18:03 ` Palmer Dabbelt
  2020-01-07  8:13   ` Björn Töpel
  2020-01-23  2:08   ` Palmer Dabbelt
  2019-12-23 18:18 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Palmer Dabbelt
                   ` (6 subsequent siblings)
  18 siblings, 2 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:03 UTC (permalink / raw)
  To: Bjorn Topel
  Cc: daniel, netdev, ast, lukenels, Bjorn Topel, linux-riscv, bpf, xi.wang

On Mon, 16 Dec 2019 01:13:36 PST (-0800), Bjorn Topel wrote:
> This commit adds branch relaxation to the BPF JIT, and with that
> support for far (offset greater than 12b) branching.

Interesting.  We don't actually relax these in the binutils linker, but instead
just do it staticly at assembly time...

> The branch relaxation requires more than two passes to converge. For
> most programs it is three passes, but for larger programs it can be
> more.

... and that's why :).  In binutils we just worst-case the link-time
relaxations when doing assembler relaxation, which proves to be good enough.  C
code doesn't branch outside a function, so most branches end up fairly short
anyway.

> Reviewed-by: Luke Nelson <lukenels@cs.washington.edu>
> Cc: Xi Wang <xi.wang@gmail.com>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 352 ++++++++++++++++++----------------
>  1 file changed, 188 insertions(+), 164 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 1606ebd49666..e599458a9bcd 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -461,6 +461,11 @@ static u32 rv_amoadd_d(u8 rd, u8 rs2, u8 rs1, u8 aq, u8 rl)
>  	return rv_amo_insn(0, aq, rl, rs2, rs1, 3, rd, 0x2f);
>  }
>
> +static u32 rv_auipc(u8 rd, u32 imm31_12)
> +{
> +	return rv_u_insn(imm31_12, rd, 0x17);
> +}
> +
>  static bool is_12b_int(s64 val)
>  {
>  	return -(1 << 11) <= val && val < (1 << 11);
> @@ -484,7 +489,7 @@ static bool is_32b_int(s64 val)
>  static int is_12b_check(int off, int insn)
>  {
>  	if (!is_12b_int(off)) {
> -		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
> +		pr_err("bpf-jit: insn=%d 12b < offset=%d not supported yet!\n",
>  		       insn, (int)off);
>  		return -1;
>  	}
> @@ -494,7 +499,7 @@ static int is_12b_check(int off, int insn)
>  static int is_13b_check(int off, int insn)
>  {
>  	if (!is_13b_int(off)) {
> -		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
> +		pr_err("bpf-jit: insn=%d 13b < offset=%d not supported yet!\n",
>  		       insn, (int)off);
>  		return -1;
>  	}
> @@ -504,7 +509,7 @@ static int is_13b_check(int off, int insn)
>  static int is_21b_check(int off, int insn)
>  {
>  	if (!is_21b_int(off)) {
> -		pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
> +		pr_err("bpf-jit: insn=%d 21b < offset=%d not supported yet!\n",
>  		       insn, (int)off);
>  		return -1;
>  	}
> @@ -550,10 +555,13 @@ static void emit_imm(u8 rd, s64 val, struct rv_jit_context *ctx)
>  		emit(rv_addi(rd, rd, lower), ctx);
>  }
>
> -static int rv_offset(int bpf_to, int bpf_from, struct rv_jit_context *ctx)
> +static int rv_offset(int insn, int off, struct rv_jit_context *ctx)
>  {
> -	int from = ctx->offset[bpf_from] - 1, to = ctx->offset[bpf_to];
> +	int from, to;
>
> +	off++; /* BPF branch is from PC+1, RV is from PC */
> +	from = (insn > 0) ? ctx->offset[insn - 1] : 0;
> +	to = (insn + off > 0) ? ctx->offset[insn + off - 1] : 0;
>  	return (to - from) << 2;
>  }
>
> @@ -606,6 +614,109 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
>  	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
>  }
>
> +/* return -1 or inverted cond */
> +static int invert_bpf_cond(u8 cond)
> +{
> +	switch (cond) {
> +	case BPF_JEQ:
> +		return BPF_JNE;
> +	case BPF_JGT:
> +		return BPF_JLE;
> +	case BPF_JLT:
> +		return BPF_JGE;
> +	case BPF_JGE:
> +		return BPF_JLT;
> +	case BPF_JLE:
> +		return BPF_JGT;
> +	case BPF_JNE:
> +		return BPF_JEQ;
> +	case BPF_JSGT:
> +		return BPF_JSLE;
> +	case BPF_JSLT:
> +		return BPF_JSGE;
> +	case BPF_JSGE:
> +		return BPF_JSLT;
> +	case BPF_JSLE:
> +		return BPF_JSGT;
> +	}
> +	return -1;
> +}
> +
> +static void emit_bcc(u8 cond, u8 rd, u8 rs, int rvoff,
> +		     struct rv_jit_context *ctx)
> +{
> +	switch (cond) {
> +	case BPF_JEQ:
> +		emit(rv_beq(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JGT:
> +		emit(rv_bltu(rs, rd, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JLT:
> +		emit(rv_bltu(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JGE:
> +		emit(rv_bgeu(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JLE:
> +		emit(rv_bgeu(rs, rd, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JNE:
> +		emit(rv_bne(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JSGT:
> +		emit(rv_blt(rs, rd, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JSLT:
> +		emit(rv_blt(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JSGE:
> +		emit(rv_bge(rd, rs, rvoff >> 1), ctx);
> +		return;
> +	case BPF_JSLE:
> +		emit(rv_bge(rs, rd, rvoff >> 1), ctx);
> +	}
> +}
> +
> +static void emit_branch(u8 cond, u8 rd, u8 rs, int rvoff,
> +			struct rv_jit_context *ctx)
> +{
> +	s64 upper, lower;
> +
> +	if (is_13b_int(rvoff)) {
> +		emit_bcc(cond, rd, rs, rvoff, ctx);
> +		return;
> +	}
> +
> +	/* Adjust for jal */
> +	rvoff -= 4;
> +
> +	/* Transform, e.g.:
> +	 *   bne rd,rs,foo
> +	 * to
> +	 *   beq rd,rs,<.L1>
> +	 *   (auipc foo)
> +	 *   jal(r) foo
> +	 * .L1
> +	 */
> +	cond = invert_bpf_cond(cond);
> +	if (is_21b_int(rvoff)) {
> +		emit_bcc(cond, rd, rs, 8, ctx);
> +		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
> +		return;
> +	}
> +
> +	/* 32b No need for an additional rvoff adjustment, since we
> +	 * get that from the auipc at PC', where PC = PC' + 4.
> +	 */
> +	upper = (rvoff + (1 << 11)) >> 12;
> +	lower = rvoff & 0xfff;
> +
> +	emit_bcc(cond, rd, rs, 12, ctx);
> +	emit(rv_auipc(RV_REG_T1, upper), ctx);
> +	emit(rv_jalr(RV_REG_ZERO, RV_REG_T1, lower), ctx);
> +}
> +
>  static void emit_zext_32(u8 reg, struct rv_jit_context *ctx)
>  {
>  	emit(rv_slli(reg, reg, 32), ctx);
> @@ -693,13 +804,6 @@ static void init_regs(u8 *rd, u8 *rs, const struct bpf_insn *insn,
>  		*rs = bpf_to_rv_reg(insn->src_reg, ctx);
>  }
>
> -static int rv_offset_check(int *rvoff, s16 off, int insn,
> -			   struct rv_jit_context *ctx)
> -{
> -	*rvoff = rv_offset(insn + off, insn, ctx);
> -	return is_13b_check(*rvoff, insn);
> -}
> -
>  static void emit_zext_32_rd_rs(u8 *rd, u8 *rs, struct rv_jit_context *ctx)
>  {
>  	emit(rv_addi(RV_REG_T2, *rd, 0), ctx);
> @@ -732,13 +836,19 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
>  	*rd = RV_REG_T2;
>  }
>
> +static bool is_signed_bpf_cond(u8 cond)
> +{
> +	return cond == BPF_JSGT || cond == BPF_JSLT ||
> +		cond == BPF_JSGE || cond == BPF_JSLE;
> +}
> +
>  static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  		     bool extra_pass)
>  {
>  	bool is64 = BPF_CLASS(insn->code) == BPF_ALU64 ||
>  		    BPF_CLASS(insn->code) == BPF_JMP;
> +	int s, e, rvoff, i = insn - ctx->prog->insnsi;
>  	struct bpf_prog_aux *aux = ctx->prog->aux;
> -	int rvoff, i = insn - ctx->prog->insnsi;
>  	u8 rd = -1, rs = -1, code = insn->code;
>  	s16 off = insn->off;
>  	s32 imm = insn->imm;
> @@ -1006,7 +1116,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>
>  	/* JUMP off */
>  	case BPF_JMP | BPF_JA:
> -		rvoff = rv_offset(i + off, i, ctx);
> +		rvoff = rv_offset(i, off, ctx);
>  		if (!is_21b_int(rvoff)) {
>  			pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
>  			       i, rvoff);
> @@ -1019,194 +1129,96 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  	/* IF (dst COND src) JUMP off */
>  	case BPF_JMP | BPF_JEQ | BPF_X:
>  	case BPF_JMP32 | BPF_JEQ | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_beq(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JGT | BPF_X:
>  	case BPF_JMP32 | BPF_JGT | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bltu(rs, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JLT | BPF_X:
>  	case BPF_JMP32 | BPF_JLT | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bltu(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JGE | BPF_X:
>  	case BPF_JMP32 | BPF_JGE | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bgeu(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JLE | BPF_X:
>  	case BPF_JMP32 | BPF_JLE | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bgeu(rs, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JNE | BPF_X:
>  	case BPF_JMP32 | BPF_JNE | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bne(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSGT | BPF_X:
>  	case BPF_JMP32 | BPF_JSGT | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_sext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_blt(rs, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSLT | BPF_X:
>  	case BPF_JMP32 | BPF_JSLT | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_sext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_blt(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSGE | BPF_X:
>  	case BPF_JMP32 | BPF_JSGE | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_sext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bge(rd, rs, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSLE | BPF_X:
>  	case BPF_JMP32 | BPF_JSLE | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_sext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_bge(rs, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSET | BPF_X:
>  	case BPF_JMP32 | BPF_JSET | BPF_X:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		if (!is64)
> -			emit_zext_32_rd_rs(&rd, &rs, ctx);
> -		emit(rv_and(RV_REG_T1, rd, rs), ctx);
> -		emit(rv_bne(RV_REG_T1, RV_REG_ZERO, rvoff >> 1), ctx);
> +		rvoff = rv_offset(i, off, ctx);
> +		if (!is64) {
> +			s = ctx->ninsns;
> +			if (is_signed_bpf_cond(BPF_OP(code)))
> +				emit_sext_32_rd_rs(&rd, &rs, ctx);
> +			else
> +				emit_zext_32_rd_rs(&rd, &rs, ctx);
> +			e = ctx->ninsns;
> +
> +			/* Adjust for extra insns */
> +			rvoff -= (e - s) << 2;
> +		}
> +
> +		if (BPF_OP(code) == BPF_JSET) {
> +			/* Adjust for and */
> +			rvoff -= 4;
> +			emit(rv_and(RV_REG_T1, rd, rs), ctx);
> +			emit_branch(BPF_JNE, RV_REG_T1, RV_REG_ZERO, rvoff,
> +				    ctx);
> +		} else {
> +			emit_branch(BPF_OP(code), rd, rs, rvoff, ctx);
> +		}
>  		break;
>
>  	/* IF (dst COND imm) JUMP off */
>  	case BPF_JMP | BPF_JEQ | BPF_K:
>  	case BPF_JMP32 | BPF_JEQ | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_beq(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JGT | BPF_K:
>  	case BPF_JMP32 | BPF_JGT | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_bltu(RV_REG_T1, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JLT | BPF_K:
>  	case BPF_JMP32 | BPF_JLT | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_bltu(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JGE | BPF_K:
>  	case BPF_JMP32 | BPF_JGE | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_bgeu(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JLE | BPF_K:
>  	case BPF_JMP32 | BPF_JLE | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_bgeu(RV_REG_T1, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JNE | BPF_K:
>  	case BPF_JMP32 | BPF_JNE | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_bne(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSGT | BPF_K:
>  	case BPF_JMP32 | BPF_JSGT | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_sext_32_rd(&rd, ctx);
> -		emit(rv_blt(RV_REG_T1, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSLT | BPF_K:
>  	case BPF_JMP32 | BPF_JSLT | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_sext_32_rd(&rd, ctx);
> -		emit(rv_blt(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSGE | BPF_K:
>  	case BPF_JMP32 | BPF_JSGE | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_sext_32_rd(&rd, ctx);
> -		emit(rv_bge(rd, RV_REG_T1, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSLE | BPF_K:
>  	case BPF_JMP32 | BPF_JSLE | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> -		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_sext_32_rd(&rd, ctx);
> -		emit(rv_bge(RV_REG_T1, rd, rvoff >> 1), ctx);
> -		break;
>  	case BPF_JMP | BPF_JSET | BPF_K:
>  	case BPF_JMP32 | BPF_JSET | BPF_K:
> -		if (rv_offset_check(&rvoff, off, i, ctx))
> -			return -1;
> +		rvoff = rv_offset(i, off, ctx);
> +		s = ctx->ninsns;
>  		emit_imm(RV_REG_T1, imm, ctx);
> -		if (!is64)
> -			emit_zext_32_rd_t1(&rd, ctx);
> -		emit(rv_and(RV_REG_T1, rd, RV_REG_T1), ctx);
> -		emit(rv_bne(RV_REG_T1, RV_REG_ZERO, rvoff >> 1), ctx);
> +		if (!is64) {
> +			if (is_signed_bpf_cond(BPF_OP(code)))
> +				emit_sext_32_rd(&rd, ctx);
> +			else
> +				emit_zext_32_rd_t1(&rd, ctx);
> +		}
> +		e = ctx->ninsns;
> +
> +		/* Adjust for extra insns */
> +		rvoff -= (e - s) << 2;
> +
> +		if (BPF_OP(code) == BPF_JSET) {
> +			/* Adjust for and */
> +			rvoff -= 4;
> +			emit(rv_and(RV_REG_T1, rd, RV_REG_T1), ctx);
> +			emit_branch(BPF_JNE, RV_REG_T1, RV_REG_ZERO, rvoff,
> +				    ctx);
> +		} else {
> +			emit_branch(BPF_OP(code), rd, RV_REG_T1, rvoff, ctx);
> +		}
>  		break;
>
>  	/* function call */
> @@ -1557,6 +1569,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  {
>  	bool tmp_blinded = false, extra_pass = false;
>  	struct bpf_prog *tmp, *orig_prog = prog;
> +	int pass = 0, prev_ninsns = 0, i;
>  	struct rv_jit_data *jit_data;
>  	struct rv_jit_context *ctx;
>  	unsigned int image_size;
> @@ -1596,15 +1609,25 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  		prog = orig_prog;
>  		goto out_offset;
>  	}
> +	for (i = 0; i < prog->len; i++) {
> +		prev_ninsns += 32;
> +		ctx->offset[i] = prev_ninsns;
> +	}

It feels like the first-order implementation is the same as binutils here: the
first round is worst cased, after which things can be more exact.  We're only
doing one pass in binutils because most of the relaxation happens in the
linker, but this approach seems reasonable to me.  I'd be interested in seeing
some benchmarks, as it may be worth relaxing these in the binutils linker as
well -- I can certainly come up with contrived test cases that aren't relaxed,
but I'm not sure how common this is.

My only worry is that that invariant should be more explicit.  Specifically,
I'm thinking that every time offset is updated there should be some sort of
assertion that the offset is shrinking.  This is enforced structurally in the
binutils code because we only generate code once and then move it around, but
since you're generating code every time it'd be easy for a bug to sneak in as
the JIT gets more complicated.

Since most of the branches should be forward, you'll probably end up with way
fewer iterations if you do the optimization passes backwards.

> -	/* First pass generates the ctx->offset, but does not emit an image. */
> -	if (build_body(ctx, extra_pass)) {
> -		prog = orig_prog;
> -		goto out_offset;
> +	for (i = 0; i < 16; i++) {
> +		pass++;
> +		ctx->ninsns = 0;
> +		if (build_body(ctx, extra_pass)) {
> +			prog = orig_prog;
> +			goto out_offset;

Isn't this returning a broken program if build_body() errors out the first time
through?

> +		}
> +		build_prologue(ctx);
> +		ctx->epilogue_offset = ctx->ninsns;
> +		build_epilogue(ctx);
> +		if (ctx->ninsns == prev_ninsns)
> +			break;
> +		prev_ninsns = ctx->ninsns;

IDK how important the performance of the JIT is, but you could probably get
away with skipping an iteration by keeping track of some simple metric that
determines if it would be possible to 

>  	}
> -	build_prologue(ctx);
> -	ctx->epilogue_offset = ctx->ninsns;
> -	build_epilogue(ctx);
>
>  	/* Allocate image, now that we know the size. */
>  	image_size = sizeof(u32) * ctx->ninsns;
> @@ -1619,6 +1642,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  	/* Second, real pass, that acutally emits the image. */
>  	ctx->insns = (u32 *)jit_data->image;
>  skip_init_ctx:
> +	pass++;
>  	ctx->ninsns = 0;
>
>  	build_prologue(ctx);
> @@ -1630,7 +1654,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  	build_epilogue(ctx);
>
>  	if (bpf_jit_enable > 1)
> -		bpf_jit_dump(prog->len, image_size, 2, ctx->insns);
> +		bpf_jit_dump(prog->len, image_size, pass, ctx->insns);
>
>  	prog->bpf_func = (void *)ctx->insns;
>  	prog->jited = 1;


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (11 preceding siblings ...)
  2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
@ 2019-12-23 18:18 ` Palmer Dabbelt
  2019-12-23 18:18 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Palmer Dabbelt
                   ` (5 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:18 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:37 PST (-0800), Bjorn Topel wrote:
> Start use the emit_branch() function in the tail call emitter in order
> to support far branching.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 22 +++-------------------
>  1 file changed, 3 insertions(+), 19 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index e599458a9bcd..c38c95df3440 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -496,16 +496,6 @@ static int is_12b_check(int off, int insn)
>  	return 0;
>  }
>
> -static int is_13b_check(int off, int insn)
> -{
> -	if (!is_13b_int(off)) {
> -		pr_err("bpf-jit: insn=%d 13b < offset=%d not supported yet!\n",
> -		       insn, (int)off);
> -		return -1;
> -	}
> -	return 0;
> -}
> -
>  static int is_21b_check(int off, int insn)
>  {
>  	if (!is_21b_int(off)) {
> @@ -744,18 +734,14 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
>  		return -1;
>  	emit(rv_lwu(RV_REG_T1, off, RV_REG_A1), ctx);
>  	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
> -	if (is_13b_check(off, insn))
> -		return -1;
> -	emit(rv_bgeu(RV_REG_A2, RV_REG_T1, off >> 1), ctx);
> +	emit_branch(BPF_JGE, RV_REG_A2, RV_REG_T1, off, ctx);
>
>  	/* if (--TCC < 0)
>  	 *     goto out;
>  	 */
>  	emit(rv_addi(RV_REG_T1, tcc, -1), ctx);
>  	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
> -	if (is_13b_check(off, insn))
> -		return -1;
> -	emit(rv_blt(RV_REG_T1, RV_REG_ZERO, off >> 1), ctx);
> +	emit_branch(BPF_JSLT, RV_REG_T1, RV_REG_ZERO, off, ctx);
>
>  	/* prog = array->ptrs[index];
>  	 * if (!prog)
> @@ -768,9 +754,7 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
>  		return -1;
>  	emit(rv_ld(RV_REG_T2, off, RV_REG_T2), ctx);
>  	off = (tc_ninsn - (ctx->ninsns - start_insn)) << 2;
> -	if (is_13b_check(off, insn))
> -		return -1;
> -	emit(rv_beq(RV_REG_T2, RV_REG_ZERO, off >> 1), ctx);
> +	emit_branch(BPF_JEQ, RV_REG_T2, RV_REG_ZERO, off, ctx);
>
>  	/* goto *(prog->bpf_func + 4); */
>  	off = offsetof(struct bpf_prog, bpf_func);

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (12 preceding siblings ...)
  2019-12-23 18:18 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Palmer Dabbelt
@ 2019-12-23 18:18 ` Palmer Dabbelt
  2019-12-23 18:29 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Palmer Dabbelt
                   ` (4 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:18 UTC (permalink / raw)
  To: Bjorn Topel
  Cc: daniel, netdev, ast, lukenels, Bjorn Topel, linux-riscv, bpf, xi.wang

On Mon, 16 Dec 2019 01:13:38 PST (-0800), Bjorn Topel wrote:
> This commit add support for far (offset > 21b) jumps and exits.
>
> Reviewed-by: Luke Nelson <lukenels@cs.washington.edu>
> Cc: Xi Wang <xi.wang@gmail.com>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 37 ++++++++++++++++-------------------
>  1 file changed, 17 insertions(+), 20 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index c38c95df3440..2fc0f24ad30f 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -496,16 +496,6 @@ static int is_12b_check(int off, int insn)
>  	return 0;
>  }
>
> -static int is_21b_check(int off, int insn)
> -{
> -	if (!is_21b_int(off)) {
> -		pr_err("bpf-jit: insn=%d 21b < offset=%d not supported yet!\n",
> -		       insn, (int)off);
> -		return -1;
> -	}
> -	return 0;
> -}
> -
>  static void emit_imm(u8 rd, s64 val, struct rv_jit_context *ctx)
>  {
>  	/* Note that the immediate from the add is sign-extended,
> @@ -820,6 +810,21 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
>  	*rd = RV_REG_T2;
>  }
>
> +static void emit_jump_and_link(u8 rd, int rvoff, struct rv_jit_context *ctx)
> +{
> +	s64 upper, lower;
> +
> +	if (is_21b_int(rvoff)) {
> +		emit(rv_jal(rd, rvoff >> 1), ctx);
> +		return;
> +	}
> +
> +	upper = (rvoff + (1 << 11)) >> 12;
> +	lower = rvoff & 0xfff;
> +	emit(rv_auipc(RV_REG_T1, upper), ctx);
> +	emit(rv_jalr(rd, RV_REG_T1, lower), ctx);
> +}

What constrains these jumps to always be 32-bit PC relative?  We have some
issues in the module loader with references to kernel symbols being too far
away to the loaded modules, it seems like similar issues could creep in here.

>  static bool is_signed_bpf_cond(u8 cond)
>  {
>  	return cond == BPF_JSGT || cond == BPF_JSLT ||
> @@ -1101,13 +1106,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  	/* JUMP off */
>  	case BPF_JMP | BPF_JA:
>  		rvoff = rv_offset(i, off, ctx);
> -		if (!is_21b_int(rvoff)) {
> -			pr_err("bpf-jit: insn=%d offset=%d not supported yet!\n",
> -			       i, rvoff);
> -			return -1;
> -		}
> -
> -		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
> +		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
>  		break;
>
>  	/* IF (dst COND src) JUMP off */
> @@ -1245,9 +1244,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  			break;
>
>  		rvoff = epilogue_offset(ctx);
> -		if (is_21b_check(rvoff, i))
> -			return -1;
> -		emit(rv_jal(RV_REG_ZERO, rvoff >> 1), ctx);
> +		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
>  		break;
>
>  	/* dst = imm64 */


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (13 preceding siblings ...)
  2019-12-23 18:18 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Palmer Dabbelt
@ 2019-12-23 18:29 ` Palmer Dabbelt
  2019-12-23 18:30 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Palmer Dabbelt
                   ` (3 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:29 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:39 PST (-0800), Bjorn Topel wrote:
> Remove one addi, and instead use the offset part of jalr.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 13 +++++++------
>  1 file changed, 7 insertions(+), 6 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 2fc0f24ad30f..8aa19c846881 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -552,7 +552,7 @@ static int epilogue_offset(struct rv_jit_context *ctx)
>  	return (to - from) << 2;
>  }
>
> -static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
> +static void __build_epilogue(bool is_tail_call, struct rv_jit_context *ctx)
>  {
>  	int stack_adjust = ctx->stack_size, store_offset = stack_adjust - 8;
>
> @@ -589,9 +589,11 @@ static void __build_epilogue(u8 reg, struct rv_jit_context *ctx)
>
>  	emit(rv_addi(RV_REG_SP, RV_REG_SP, stack_adjust), ctx);
>  	/* Set return value. */
> -	if (reg == RV_REG_RA)
> +	if (!is_tail_call)
>  		emit(rv_addi(RV_REG_A0, RV_REG_A5, 0), ctx);
> -	emit(rv_jalr(RV_REG_ZERO, reg, 0), ctx);
> +	emit(rv_jalr(RV_REG_ZERO, is_tail_call ? RV_REG_T3 : RV_REG_RA,
> +		     is_tail_call ? 4 : 0), /* skip TCC init */
> +	     ctx);
>  }
>
>  /* return -1 or inverted cond */
> @@ -751,9 +753,8 @@ static int emit_bpf_tail_call(int insn, struct rv_jit_context *ctx)
>  	if (is_12b_check(off, insn))
>  		return -1;
>  	emit(rv_ld(RV_REG_T3, off, RV_REG_T2), ctx);
> -	emit(rv_addi(RV_REG_T3, RV_REG_T3, 4), ctx);
>  	emit(rv_addi(RV_REG_TCC, RV_REG_T1, 0), ctx);
> -	__build_epilogue(RV_REG_T3, ctx);
> +	__build_epilogue(true, ctx);
>  	return 0;
>  }
>
> @@ -1504,7 +1505,7 @@ static void build_prologue(struct rv_jit_context *ctx)
>
>  static void build_epilogue(struct rv_jit_context *ctx)
>  {
> -	__build_epilogue(RV_REG_RA, ctx);
> +	__build_epilogue(false, ctx);
>  }
>
>  static int build_body(struct rv_jit_context *ctx, bool extra_pass)

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (14 preceding siblings ...)
  2019-12-23 18:29 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Palmer Dabbelt
@ 2019-12-23 18:30 ` Palmer Dabbelt
  2019-12-23 18:58 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Palmer Dabbelt
                   ` (2 subsequent siblings)
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:30 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:40 PST (-0800), Bjorn Topel wrote:
> This commit makes sure that the JIT images is kept close to the kernel
> text, so BPF calls can use relative calling with auipc/jalr or jal
> instead of loading the full 64-bit address and jalr.
>
> The BPF JIT image region is 128 MB before the kernel text.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/include/asm/pgtable.h |  4 ++++
>  arch/riscv/net/bpf_jit_comp.c    | 13 +++++++++++++
>  2 files changed, 17 insertions(+)
>
> diff --git a/arch/riscv/include/asm/pgtable.h b/arch/riscv/include/asm/pgtable.h
> index 7ff0ed4f292e..cc3f49415620 100644
> --- a/arch/riscv/include/asm/pgtable.h
> +++ b/arch/riscv/include/asm/pgtable.h
> @@ -404,6 +404,10 @@ static inline int ptep_clear_flush_young(struct vm_area_struct *vma,
>  #define VMALLOC_END      (PAGE_OFFSET - 1)
>  #define VMALLOC_START    (PAGE_OFFSET - VMALLOC_SIZE)
>
> +#define BPF_JIT_REGION_SIZE	(SZ_128M)
> +#define BPF_JIT_REGION_START	(PAGE_OFFSET - BPF_JIT_REGION_SIZE)
> +#define BPF_JIT_REGION_END	(VMALLOC_END)
> +
>  /*
>   * Roughly size the vmemmap space to be large enough to fit enough
>   * struct pages to map half the virtual address space. Then
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 8aa19c846881..46cff093f526 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -1656,3 +1656,16 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  					   tmp : orig_prog);
>  	return prog;
>  }
> +
> +void *bpf_jit_alloc_exec(unsigned long size)
> +{
> +	return __vmalloc_node_range(size, PAGE_SIZE, BPF_JIT_REGION_START,
> +				    BPF_JIT_REGION_END, GFP_KERNEL,
> +				    PAGE_KERNEL_EXEC, 0, NUMA_NO_NODE,
> +				    __builtin_return_address(0));
> +}
> +
> +void bpf_jit_free_exec(void *addr)
> +{
> +	return vfree(addr);
> +}

Ah, I guess I should have read the whole patch set :)

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>

and feel free to put the same on whatever patch I just asked that question
on, though maybe this one should go before the others as they sort of depend on
it?


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (15 preceding siblings ...)
  2019-12-23 18:30 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Palmer Dabbelt
@ 2019-12-23 18:58 ` Palmer Dabbelt
  2020-01-07 10:14   ` Björn Töpel
  2019-12-23 18:58 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Palmer Dabbelt
  2019-12-23 18:58 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Palmer Dabbelt
  18 siblings, 1 reply; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:58 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:41 PST (-0800), Bjorn Topel wrote:
> Instead of using emit_imm() and emit_jalr() which can expand to six
> instructions, start using jal or auipc+jalr.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/net/bpf_jit_comp.c | 101 +++++++++++++++++++++-------------
>  1 file changed, 64 insertions(+), 37 deletions(-)
>
> diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> index 46cff093f526..8d7e3343a08c 100644
> --- a/arch/riscv/net/bpf_jit_comp.c
> +++ b/arch/riscv/net/bpf_jit_comp.c
> @@ -811,11 +811,12 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
>  	*rd = RV_REG_T2;
>  }
>
> -static void emit_jump_and_link(u8 rd, int rvoff, struct rv_jit_context *ctx)
> +static void emit_jump_and_link(u8 rd, s64 rvoff, bool force_jalr,
> +			       struct rv_jit_context *ctx)
>  {
>  	s64 upper, lower;
>
> -	if (is_21b_int(rvoff)) {
> +	if (rvoff && is_21b_int(rvoff) && !force_jalr) {
>  		emit(rv_jal(rd, rvoff >> 1), ctx);
>  		return;
>  	}
> @@ -832,6 +833,28 @@ static bool is_signed_bpf_cond(u8 cond)
>  		cond == BPF_JSGE || cond == BPF_JSLE;
>  }
>
> +static int emit_call(bool fixed, u64 addr, struct rv_jit_context *ctx)
> +{
> +	s64 off = 0;
> +	u64 ip;
> +	u8 rd;
> +
> +	if (addr && ctx->insns) {
> +		ip = (u64)(long)(ctx->insns + ctx->ninsns);
> +		off = addr - ip;
> +		if (!is_32b_int(off)) {
> +			pr_err("bpf-jit: target call addr %pK is out of range\n",
> +			       (void *)addr);
> +			return -ERANGE;
> +		}
> +	}
> +
> +	emit_jump_and_link(RV_REG_RA, off, !fixed, ctx);
> +	rd = bpf_to_rv_reg(BPF_REG_0, ctx);
> +	emit(rv_addi(rd, RV_REG_A0, 0), ctx);

Why are they out of order?  It seems like it'd be better to just have the BPF
calling convention match the RISC-V calling convention, as that'd avoid
juggling the registers around.

> +	return 0;
> +}
> +
>  static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  		     bool extra_pass)
>  {
> @@ -1107,7 +1130,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  	/* JUMP off */
>  	case BPF_JMP | BPF_JA:
>  		rvoff = rv_offset(i, off, ctx);
> -		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
> +		emit_jump_and_link(RV_REG_ZERO, rvoff, false, ctx);
>  		break;
>
>  	/* IF (dst COND src) JUMP off */
> @@ -1209,7 +1232,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  	case BPF_JMP | BPF_CALL:
>  	{
>  		bool fixed;
> -		int i, ret;
> +		int ret;
>  		u64 addr;
>
>  		mark_call(ctx);
> @@ -1217,20 +1240,9 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  					    &fixed);
>  		if (ret < 0)
>  			return ret;
> -		if (fixed) {
> -			emit_imm(RV_REG_T1, addr, ctx);
> -		} else {
> -			i = ctx->ninsns;
> -			emit_imm(RV_REG_T1, addr, ctx);
> -			for (i = ctx->ninsns - i; i < 8; i++) {
> -				/* nop */
> -				emit(rv_addi(RV_REG_ZERO, RV_REG_ZERO, 0),
> -				     ctx);
> -			}
> -		}
> -		emit(rv_jalr(RV_REG_RA, RV_REG_T1, 0), ctx);
> -		rd = bpf_to_rv_reg(BPF_REG_0, ctx);
> -		emit(rv_addi(rd, RV_REG_A0, 0), ctx);
> +		ret = emit_call(fixed, addr, ctx);
> +		if (ret)
> +			return ret;
>  		break;
>  	}
>  	/* tail call */
> @@ -1245,7 +1257,7 @@ static int emit_insn(const struct bpf_insn *insn, struct rv_jit_context *ctx,
>  			break;
>
>  		rvoff = epilogue_offset(ctx);
> -		emit_jump_and_link(RV_REG_ZERO, rvoff, ctx);
> +		emit_jump_and_link(RV_REG_ZERO, rvoff, false, ctx);
>  		break;
>
>  	/* dst = imm64 */
> @@ -1508,7 +1520,7 @@ static void build_epilogue(struct rv_jit_context *ctx)
>  	__build_epilogue(false, ctx);
>  }
>
> -static int build_body(struct rv_jit_context *ctx, bool extra_pass)
> +static int build_body(struct rv_jit_context *ctx, bool extra_pass, int *offset)
>  {
>  	const struct bpf_prog *prog = ctx->prog;
>  	int i;
> @@ -1520,12 +1532,12 @@ static int build_body(struct rv_jit_context *ctx, bool extra_pass)
>  		ret = emit_insn(insn, ctx, extra_pass);
>  		if (ret > 0) {
>  			i++;
> -			if (ctx->insns == NULL)
> -				ctx->offset[i] = ctx->ninsns;
> +			if (offset)
> +				offset[i] = ctx->ninsns;
>  			continue;
>  		}
> -		if (ctx->insns == NULL)
> -			ctx->offset[i] = ctx->ninsns;
> +		if (offset)
> +			offset[i] = ctx->ninsns;
>  		if (ret)
>  			return ret;
>  	}
> @@ -1553,8 +1565,8 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  	struct bpf_prog *tmp, *orig_prog = prog;
>  	int pass = 0, prev_ninsns = 0, i;
>  	struct rv_jit_data *jit_data;
> +	unsigned int image_size = 0;
>  	struct rv_jit_context *ctx;
> -	unsigned int image_size;
>
>  	if (!prog->jit_requested)
>  		return orig_prog;
> @@ -1599,36 +1611,51 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>  	for (i = 0; i < 16; i++) {
>  		pass++;
>  		ctx->ninsns = 0;
> -		if (build_body(ctx, extra_pass)) {
> +		if (build_body(ctx, extra_pass, ctx->offset)) {
>  			prog = orig_prog;
>  			goto out_offset;
>  		}
>  		build_prologue(ctx);
>  		ctx->epilogue_offset = ctx->ninsns;
>  		build_epilogue(ctx);
> -		if (ctx->ninsns == prev_ninsns)
> -			break;
> +
> +		if (ctx->ninsns == prev_ninsns) {
> +			if (jit_data->header)
> +				break;
> +
> +			image_size = sizeof(u32) * ctx->ninsns;
> +			jit_data->header =
> +				bpf_jit_binary_alloc(image_size,
> +						     &jit_data->image,
> +						     sizeof(u32),
> +						     bpf_fill_ill_insns);
> +			if (!jit_data->header) {
> +				prog = orig_prog;
> +				goto out_offset;
> +			}
> +
> +			ctx->insns = (u32 *)jit_data->image;
> +			/* Now, when the image is allocated, the image
> +			 * can potentially shrink more (auipc/jalr ->
> +			 * jal).
> +			 */
> +		}

It seems like these fragments should go along with patch #2 that introduces the
code, as I don't see anything above that makes this necessary here.

>  		prev_ninsns = ctx->ninsns;
>  	}
>
> -	/* Allocate image, now that we know the size. */
> -	image_size = sizeof(u32) * ctx->ninsns;
> -	jit_data->header = bpf_jit_binary_alloc(image_size, &jit_data->image,
> -						sizeof(u32),
> -						bpf_fill_ill_insns);
> -	if (!jit_data->header) {
> +	if (i == 16) {
> +		pr_err("bpf-jit: image did not converge in <%d passes!\n", i);
> +		bpf_jit_binary_free(jit_data->header);
>  		prog = orig_prog;
>  		goto out_offset;
>  	}
>
> -	/* Second, real pass, that acutally emits the image. */
> -	ctx->insns = (u32 *)jit_data->image;
>  skip_init_ctx:
>  	pass++;
>  	ctx->ninsns = 0;
>
>  	build_prologue(ctx);
> -	if (build_body(ctx, extra_pass)) {
> +	if (build_body(ctx, extra_pass, NULL)) {
>  		bpf_jit_binary_free(jit_data->header);
>  		prog = orig_prog;
>  		goto out_offset;


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (16 preceding siblings ...)
  2019-12-23 18:58 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Palmer Dabbelt
@ 2019-12-23 18:58 ` Palmer Dabbelt
  2019-12-23 18:58 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Palmer Dabbelt
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:58 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:42 PST (-0800), Bjorn Topel wrote:
> Add missing uapi header the BPF_PROG_TYPE_PERF_EVENT programs by
> exporting struct user_regs_struct instead of struct pt_regs which is
> in-kernel only.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/include/uapi/asm/bpf_perf_event.h | 9 +++++++++
>  tools/include/uapi/asm/bpf_perf_event.h      | 2 ++
>  2 files changed, 11 insertions(+)
>  create mode 100644 arch/riscv/include/uapi/asm/bpf_perf_event.h
>
> diff --git a/arch/riscv/include/uapi/asm/bpf_perf_event.h b/arch/riscv/include/uapi/asm/bpf_perf_event.h
> new file mode 100644
> index 000000000000..6cb1c2823288
> --- /dev/null
> +++ b/arch/riscv/include/uapi/asm/bpf_perf_event.h
> @@ -0,0 +1,9 @@
> +/* SPDX-License-Identifier: GPL-2.0 WITH Linux-syscall-note */
> +#ifndef _UAPI__ASM_BPF_PERF_EVENT_H__
> +#define _UAPI__ASM_BPF_PERF_EVENT_H__
> +
> +#include <asm/ptrace.h>
> +
> +typedef struct user_regs_struct bpf_user_pt_regs_t;
> +
> +#endif /* _UAPI__ASM_BPF_PERF_EVENT_H__ */
> diff --git a/tools/include/uapi/asm/bpf_perf_event.h b/tools/include/uapi/asm/bpf_perf_event.h
> index 13a58531e6fa..39acc149d843 100644
> --- a/tools/include/uapi/asm/bpf_perf_event.h
> +++ b/tools/include/uapi/asm/bpf_perf_event.h
> @@ -2,6 +2,8 @@
>  #include "../../arch/arm64/include/uapi/asm/bpf_perf_event.h"
>  #elif defined(__s390__)
>  #include "../../arch/s390/include/uapi/asm/bpf_perf_event.h"
> +#elif defined(__riscv)
> +#include "../../arch/riscv/include/uapi/asm/bpf_perf_event.h"
>  #else
>  #include <uapi/asm-generic/bpf_perf_event.h>
>  #endif

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs
  2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
                   ` (17 preceding siblings ...)
  2019-12-23 18:58 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Palmer Dabbelt
@ 2019-12-23 18:58 ` Palmer Dabbelt
  18 siblings, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2019-12-23 18:58 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, Bjorn Topel, linux-riscv, bpf

On Mon, 16 Dec 2019 01:13:43 PST (-0800), Bjorn Topel wrote:
> RISC-V was missing a proper perf_arch_bpf_user_pt_regs macro for
> CONFIG_PERF_EVENT builds.
>
> Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> ---
>  arch/riscv/include/asm/perf_event.h | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/arch/riscv/include/asm/perf_event.h b/arch/riscv/include/asm/perf_event.h
> index aefbfaa6a781..0234048b12bc 100644
> --- a/arch/riscv/include/asm/perf_event.h
> +++ b/arch/riscv/include/asm/perf_event.h
> @@ -82,4 +82,8 @@ struct riscv_pmu {
>  	int		irq;
>  };
>
> +#ifdef CONFIG_PERF_EVENTS
> +#define perf_arch_bpf_user_pt_regs(regs) (struct user_regs_struct *)regs
> +#endif
> +
>  #endif /* _ASM_RISCV_PERF_EVENT_H */

Reviewed-by: Palmer Dabbelt <palmerdabbelt@google.com>
Acked-by: Palmer Dabbelt <palmerdabbelt@google.com>


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2019-12-18  6:23     ` Björn Töpel
@ 2020-01-04  1:32       ` Paul Walmsley
  2020-01-07 10:24         ` Björn Töpel
  0 siblings, 1 reply; 28+ messages in thread
From: Paul Walmsley @ 2020-01-04  1:32 UTC (permalink / raw)
  To: Björn Töpel
  Cc: Albert Ou, Daniel Borkmann, Netdev, Alexei Starovoitov,
	Palmer Dabbelt, linux-riscv, bpf

[-- Attachment #1: Type: text/plain, Size: 1832 bytes --]

On Wed, 18 Dec 2019, Björn Töpel wrote:

> On Mon, 16 Dec 2019 at 16:09, Daniel Borkmann <daniel@iogearbox.net> wrote:
> >
> > On 12/16/19 10:13 AM, Björn Töpel wrote:
> > > This commit makes sure that the JIT images is kept close to the kernel
> > > text, so BPF calls can use relative calling with auipc/jalr or jal
> > > instead of loading the full 64-bit address and jalr.
> > >
> > > The BPF JIT image region is 128 MB before the kernel text.
> > >
> > > Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> > > ---
> > >   arch/riscv/include/asm/pgtable.h |  4 ++++
> > >   arch/riscv/net/bpf_jit_comp.c    | 13 +++++++++++++
> > >   2 files changed, 17 insertions(+)
> > >
> > > diff --git a/arch/riscv/include/asm/pgtable.h b/arch/riscv/include/asm/pgtable.h
> > > index 7ff0ed4f292e..cc3f49415620 100644
> > > --- a/arch/riscv/include/asm/pgtable.h
> > > +++ b/arch/riscv/include/asm/pgtable.h
> > > @@ -404,6 +404,10 @@ static inline int ptep_clear_flush_young(struct vm_area_struct *vma,
> > >   #define VMALLOC_END      (PAGE_OFFSET - 1)
> > >   #define VMALLOC_START    (PAGE_OFFSET - VMALLOC_SIZE)
> > >
> > > +#define BPF_JIT_REGION_SIZE  (SZ_128M)
> > > +#define BPF_JIT_REGION_START (PAGE_OFFSET - BPF_JIT_REGION_SIZE)
> > > +#define BPF_JIT_REGION_END   (VMALLOC_END)
> > > +
> >
> > Series looks good to me, thanks; I'd like to get an ACK from Palmer/others on this one.
> >
> 
> Palmer/Paul/Albert, any thoughts/input? I can respin the the series
> w/o the call optimizations (excluding this patch and the next), but
> I'd prefer not given it's a nice speed/clean up for calls.

Looks like Palmer's already reviewed it.  One additional request: could 
you update the VM layout debugging messages in arch/riscv/mm/init.c to 
include this new area?

thanks,

- Paul

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
  2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
@ 2020-01-07  8:13   ` Björn Töpel
  2020-01-23  2:08   ` Palmer Dabbelt
  1 sibling, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2020-01-07  8:13 UTC (permalink / raw)
  To: Palmer Dabbelt
  Cc: Daniel Borkmann, Netdev, Alexei Starovoitov, Luke Nelson,
	linux-riscv, bpf, Xi Wang

Back from the holidays; Sorry about the delayed reply.

On Mon, 23 Dec 2019 at 19:03, Palmer Dabbelt <palmerdabbelt@google.com> wrote:
>
> On Mon, 16 Dec 2019 01:13:36 PST (-0800), Bjorn Topel wrote:
> > This commit adds branch relaxation to the BPF JIT, and with that
[...]
> > @@ -1557,6 +1569,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> >  {
> >       bool tmp_blinded = false, extra_pass = false;
> >       struct bpf_prog *tmp, *orig_prog = prog;
> > +     int pass = 0, prev_ninsns = 0, i;
> >       struct rv_jit_data *jit_data;
> >       struct rv_jit_context *ctx;
> >       unsigned int image_size;
> > @@ -1596,15 +1609,25 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> >               prog = orig_prog;
> >               goto out_offset;
> >       }
> > +     for (i = 0; i < prog->len; i++) {
> > +             prev_ninsns += 32;
> > +             ctx->offset[i] = prev_ninsns;
> > +     }
>
> It feels like the first-order implementation is the same as binutils here: the
> first round is worst cased, after which things can be more exact.  We're only
> doing one pass in binutils because most of the relaxation happens in the
> linker, but this approach seems reasonable to me.  I'd be interested in seeing
> some benchmarks, as it may be worth relaxing these in the binutils linker as
> well -- I can certainly come up with contrived test cases that aren't relaxed,
> but I'm not sure how common this is.
>

Ah, interesting! Let me try to pull out some branch relaxation
statistics/benchmarks for the BPF selftests.

> My only worry is that that invariant should be more explicit.  Specifically,
> I'm thinking that every time offset is updated there should be some sort of
> assertion that the offset is shrinking.  This is enforced structurally in the
> binutils code because we only generate code once and then move it around, but
> since you're generating code every time it'd be easy for a bug to sneak in as
> the JIT gets more complicated.
>

Hmm, yes. Maybe use a checksum for the program in addition to the
length invariant, and converge condition would then be prev_len == len
&& prev_crc == crc?

> Since most of the branches should be forward, you'll probably end up with way
> fewer iterations if you do the optimization passes backwards.
>

Good idea!

> > -     /* First pass generates the ctx->offset, but does not emit an image. */
> > -     if (build_body(ctx, extra_pass)) {
> > -             prog = orig_prog;
> > -             goto out_offset;
> > +     for (i = 0; i < 16; i++) {
> > +             pass++;
> > +             ctx->ninsns = 0;
> > +             if (build_body(ctx, extra_pass)) {
> > +                     prog = orig_prog;
> > +                     goto out_offset;
>
> Isn't this returning a broken program if build_body() errors out the first time
> through?
>

Hmm, care to elaborate? I don't see how?

> > +             }
> > +             build_prologue(ctx);
> > +             ctx->epilogue_offset = ctx->ninsns;
> > +             build_epilogue(ctx);
> > +             if (ctx->ninsns == prev_ninsns)
> > +                     break;
> > +             prev_ninsns = ctx->ninsns;
>
> IDK how important the performance of the JIT is, but you could probably get
> away with skipping an iteration by keeping track of some simple metric that
> determines if it would be possible to
>

...to? Given that the programs are getting larger, performance of the
JIT is important. So, any means the number of passes can be reduced is
a good thing!


Thanks for the review/suggestions!
Björn


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls
  2019-12-23 18:58 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Palmer Dabbelt
@ 2020-01-07 10:14   ` Björn Töpel
  0 siblings, 0 replies; 28+ messages in thread
From: Björn Töpel @ 2020-01-07 10:14 UTC (permalink / raw)
  To: Palmer Dabbelt
  Cc: Netdev, linux-riscv, bpf, Alexei Starovoitov, Daniel Borkmann

On Mon, 23 Dec 2019 at 19:58, Palmer Dabbelt <palmerdabbelt@google.com> wrote:
>
> On Mon, 16 Dec 2019 01:13:41 PST (-0800), Bjorn Topel wrote:
> > Instead of using emit_imm() and emit_jalr() which can expand to six
> > instructions, start using jal or auipc+jalr.
> >
> > Signed-off-by: Björn Töpel <bjorn.topel@gmail.com>
> > ---
> >  arch/riscv/net/bpf_jit_comp.c | 101 +++++++++++++++++++++-------------
> >  1 file changed, 64 insertions(+), 37 deletions(-)
> >
> > diff --git a/arch/riscv/net/bpf_jit_comp.c b/arch/riscv/net/bpf_jit_comp.c
> > index 46cff093f526..8d7e3343a08c 100644
> > --- a/arch/riscv/net/bpf_jit_comp.c
> > +++ b/arch/riscv/net/bpf_jit_comp.c
> > @@ -811,11 +811,12 @@ static void emit_sext_32_rd(u8 *rd, struct rv_jit_context *ctx)
> >       *rd = RV_REG_T2;
> >  }
> >
> > -static void emit_jump_and_link(u8 rd, int rvoff, struct rv_jit_context *ctx)
> > +static void emit_jump_and_link(u8 rd, s64 rvoff, bool force_jalr,
> > +                            struct rv_jit_context *ctx)
> >  {
> >       s64 upper, lower;
> >
> > -     if (is_21b_int(rvoff)) {
> > +     if (rvoff && is_21b_int(rvoff) && !force_jalr) {
> >               emit(rv_jal(rd, rvoff >> 1), ctx);
> >               return;
> >       }
> > @@ -832,6 +833,28 @@ static bool is_signed_bpf_cond(u8 cond)
> >               cond == BPF_JSGE || cond == BPF_JSLE;
> >  }
> >
> > +static int emit_call(bool fixed, u64 addr, struct rv_jit_context *ctx)
> > +{
> > +     s64 off = 0;
> > +     u64 ip;
> > +     u8 rd;
> > +
> > +     if (addr && ctx->insns) {
> > +             ip = (u64)(long)(ctx->insns + ctx->ninsns);
> > +             off = addr - ip;
> > +             if (!is_32b_int(off)) {
> > +                     pr_err("bpf-jit: target call addr %pK is out of range\n",
> > +                            (void *)addr);
> > +                     return -ERANGE;
> > +             }
> > +     }
> > +
> > +     emit_jump_and_link(RV_REG_RA, off, !fixed, ctx);
> > +     rd = bpf_to_rv_reg(BPF_REG_0, ctx);
> > +     emit(rv_addi(rd, RV_REG_A0, 0), ctx);
>
> Why are they out of order?  It seems like it'd be better to just have the BPF
> calling convention match the RISC-V calling convention, as that'd avoid
> juggling the registers around.
>

BPF passes arguments in R1, R2, ..., and return value in R0. Given
that a0 plays the role of R1 and R0, how can we avoid the register
juggling (without complicating the JIT too much)? It would be nice
though... and ARM64 has the same concern AFAIK.

[...]
> > @@ -1599,36 +1611,51 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> >       for (i = 0; i < 16; i++) {
> >               pass++;
> >               ctx->ninsns = 0;
> > -             if (build_body(ctx, extra_pass)) {
> > +             if (build_body(ctx, extra_pass, ctx->offset)) {
> >                       prog = orig_prog;
> >                       goto out_offset;
> >               }
> >               build_prologue(ctx);
> >               ctx->epilogue_offset = ctx->ninsns;
> >               build_epilogue(ctx);
> > -             if (ctx->ninsns == prev_ninsns)
> > -                     break;
> > +
> > +             if (ctx->ninsns == prev_ninsns) {
> > +                     if (jit_data->header)
> > +                             break;
> > +
> > +                     image_size = sizeof(u32) * ctx->ninsns;
> > +                     jit_data->header =
> > +                             bpf_jit_binary_alloc(image_size,
> > +                                                  &jit_data->image,
> > +                                                  sizeof(u32),
> > +                                                  bpf_fill_ill_insns);
> > +                     if (!jit_data->header) {
> > +                             prog = orig_prog;
> > +                             goto out_offset;
> > +                     }
> > +
> > +                     ctx->insns = (u32 *)jit_data->image;
> > +                     /* Now, when the image is allocated, the image
> > +                      * can potentially shrink more (auipc/jalr ->
> > +                      * jal).
> > +                      */
> > +             }
>
> It seems like these fragments should go along with patch #2 that introduces the
> code, as I don't see anything above that makes this necessary here.
>

No, you're right.


Björn


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2020-01-04  1:32       ` Paul Walmsley
@ 2020-01-07 10:24         ` Björn Töpel
  2020-01-07 10:47           ` Paul Walmsley
  0 siblings, 1 reply; 28+ messages in thread
From: Björn Töpel @ 2020-01-07 10:24 UTC (permalink / raw)
  To: Paul Walmsley
  Cc: Albert Ou, Daniel Borkmann, Netdev, Alexei Starovoitov,
	Palmer Dabbelt, linux-riscv, bpf

Paul,

Back from the holidays. Sorry about the delay!

On Sat, 4 Jan 2020 at 02:32, Paul Walmsley <paul.walmsley@sifive.com> wrote:
>
[...]
>
> Looks like Palmer's already reviewed it.  One additional request: could
> you update the VM layout debugging messages in arch/riscv/mm/init.c to
> include this new area?
>

Sure, I'll send that as a follow-up! Related; Other archs, e.g. arm64,
has moved away from dumping the VM layout (commit 071929dbdd86
("arm64: Stop printing the virtual memory layout")), and instead rely
on _PTDUMP. Going forward that probably applies to riscv as well!


Cheers,
Björn


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free
  2020-01-07 10:24         ` Björn Töpel
@ 2020-01-07 10:47           ` Paul Walmsley
  0 siblings, 0 replies; 28+ messages in thread
From: Paul Walmsley @ 2020-01-07 10:47 UTC (permalink / raw)
  To: Björn Töpel
  Cc: Albert Ou, Daniel Borkmann, Netdev, Alexei Starovoitov,
	Palmer Dabbelt, linux-riscv, bpf

[-- Attachment #1: Type: text/plain, Size: 939 bytes --]

On Tue, 7 Jan 2020, Björn Töpel wrote:

> On Sat, 4 Jan 2020 at 02:32, Paul Walmsley <paul.walmsley@sifive.com> wrote:
>
> > Looks like Palmer's already reviewed it.  One additional request: could
> > you update the VM layout debugging messages in arch/riscv/mm/init.c to
> > include this new area?
> 
> Sure, I'll send that as a follow-up! 

Thanks.

> Related; Other archs, e.g. arm64, has moved away from dumping the VM 
> layout (commit 071929dbdd86 ("arm64: Stop printing the virtual memory 
> layout")), and instead rely on _PTDUMP. Going forward that probably 
> applies to riscv as well!

For the specific case of the page table dumper: we're waiting for the 
generic ptdump patchset to be merged first - hopefully for v5.6.  The 
RISC-V integration patches against it were posted to the lists back in 
October.  But, to me, that targets a different use-case than the VM layout 
debug print code.


- Paul

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
  2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
  2020-01-07  8:13   ` Björn Töpel
@ 2020-01-23  2:08   ` Palmer Dabbelt
  1 sibling, 0 replies; 28+ messages in thread
From: Palmer Dabbelt @ 2020-01-23  2:08 UTC (permalink / raw)
  To: Bjorn Topel; +Cc: daniel, netdev, ast, lukenels, linux-riscv, bpf, xi.wang

On Tue, 07 Jan 2020 00:13:56 PST (-0800), Bjorn Topel wrote:
> Back from the holidays; Sorry about the delayed reply.
>
> On Mon, 23 Dec 2019 at 19:03, Palmer Dabbelt <palmerdabbelt@google.com> wrote:
>>
>> On Mon, 16 Dec 2019 01:13:36 PST (-0800), Bjorn Topel wrote:
>> > This commit adds branch relaxation to the BPF JIT, and with that
> [...]
>> > @@ -1557,6 +1569,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>> >  {
>> >       bool tmp_blinded = false, extra_pass = false;
>> >       struct bpf_prog *tmp, *orig_prog = prog;
>> > +     int pass = 0, prev_ninsns = 0, i;
>> >       struct rv_jit_data *jit_data;
>> >       struct rv_jit_context *ctx;
>> >       unsigned int image_size;
>> > @@ -1596,15 +1609,25 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
>> >               prog = orig_prog;
>> >               goto out_offset;
>> >       }
>> > +     for (i = 0; i < prog->len; i++) {
>> > +             prev_ninsns += 32;
>> > +             ctx->offset[i] = prev_ninsns;
>> > +     }
>>
>> It feels like the first-order implementation is the same as binutils here: the
>> first round is worst cased, after which things can be more exact.  We're only
>> doing one pass in binutils because most of the relaxation happens in the
>> linker, but this approach seems reasonable to me.  I'd be interested in seeing
>> some benchmarks, as it may be worth relaxing these in the binutils linker as
>> well -- I can certainly come up with contrived test cases that aren't relaxed,
>> but I'm not sure how common this is.
>>
>
> Ah, interesting! Let me try to pull out some branch relaxation
> statistics/benchmarks for the BPF selftests.
>
>> My only worry is that that invariant should be more explicit.  Specifically,
>> I'm thinking that every time offset is updated there should be some sort of
>> assertion that the offset is shrinking.  This is enforced structurally in the
>> binutils code because we only generate code once and then move it around, but
>> since you're generating code every time it'd be easy for a bug to sneak in as
>> the JIT gets more complicated.
>>
>
> Hmm, yes. Maybe use a checksum for the program in addition to the
> length invariant, and converge condition would then be prev_len == len
> && prev_crc == crc?

That would work, but it breaks my unfinished optimization below.  I was
thinking something more like "every time offset[i] is updated, check that it
gets smaller and otherwise barf".

>> Since most of the branches should be forward, you'll probably end up with way
>> fewer iterations if you do the optimization passes backwards.
>>
>
> Good idea!
>
>> > -     /* First pass generates the ctx->offset, but does not emit an image. */
>> > -     if (build_body(ctx, extra_pass)) {
>> > -             prog = orig_prog;
>> > -             goto out_offset;
>> > +     for (i = 0; i < 16; i++) {
>> > +             pass++;
>> > +             ctx->ninsns = 0;
>> > +             if (build_body(ctx, extra_pass)) {
>> > +                     prog = orig_prog;
>> > +                     goto out_offset;
>>
>> Isn't this returning a broken program if build_body() errors out the first time
>> through?
>>
>
> Hmm, care to elaborate? I don't see how?

Ya, I don't either any more.  Hopefully I just got confused between prog and
ctx...

>> > +             }
>> > +             build_prologue(ctx);
>> > +             ctx->epilogue_offset = ctx->ninsns;
>> > +             build_epilogue(ctx);
>> > +             if (ctx->ninsns == prev_ninsns)
>> > +                     break;
>> > +             prev_ninsns = ctx->ninsns;
>>
>> IDK how important the performance of the JIT is, but you could probably get
>> away with skipping an iteration by keeping track of some simple metric that
>> determines if it would be possible to
>>
>
> ...to? Given that the programs are getting larger, performance of the
> JIT is important. So, any means the number of passes can be reduced is
> a good thing!

I guess I meant to say "determines if it would be possible to make any
modifications next time".  I was thinking something along the lines of:

* as you run through the program, keep track of the shortest branch distance
* if you didn't remove enough bytes to make that branch cross a relaxation
  boundary, then you know that next time you won't be able to do any useful
  work

You're already computing all the branch lengths, so it's just an extra min().
Since we're assuming a small number of passes (after reversing the relaxation
direction), you'll probably save more work avoiding the extra pass than it'll
take to compute the extra information.  I guess some sort of benchmark would
give a real answer, but it certainly smells like a good idea ;)

>
>
> Thanks for the review/suggestions!
> Björn


^ permalink raw reply	[flat|nested] 28+ messages in thread

end of thread, back to index

Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-12-16  9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Björn Töpel
2019-12-16 15:09   ` Daniel Borkmann
2019-12-18  6:23     ` Björn Töpel
2020-01-04  1:32       ` Paul Walmsley
2020-01-07 10:24         ` Björn Töpel
2020-01-07 10:47           ` Paul Walmsley
2019-12-16  9:13 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Björn Töpel
2019-12-16  9:13 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Björn Töpel
2019-12-19 15:07 ` [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Daniel Borkmann
2019-12-19 22:02 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Palmer Dabbelt
2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
2020-01-07  8:13   ` Björn Töpel
2020-01-23  2:08   ` Palmer Dabbelt
2019-12-23 18:18 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Palmer Dabbelt
2019-12-23 18:18 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Palmer Dabbelt
2019-12-23 18:29 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Palmer Dabbelt
2019-12-23 18:30 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Palmer Dabbelt
2019-12-23 18:58 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Palmer Dabbelt
2020-01-07 10:14   ` Björn Töpel
2019-12-23 18:58 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Palmer Dabbelt
2019-12-23 18:58 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Palmer Dabbelt

Linux-RISC-V Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-riscv/0 linux-riscv/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-riscv linux-riscv/ https://lore.kernel.org/linux-riscv \
		linux-riscv@lists.infradead.org
	public-inbox-index linux-riscv

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.infradead.lists.linux-riscv


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git