[PATCH bpf-next 00/19] bpf: JSET tests and dead code elimination

[PATCH bpf-next 00/19] bpf: JSET tests and dead code elimination

[Jakub Kicinski]

Hi!

This set starts with adding functional tests for JSET instruction.
Next verifier's understanding of JSET is improved and relevant tests
follow.  These changes allow for better dead code elimination.

Dead code removal is the next part.  For root user only all code deemed
dead by the verifier path walk is removed.  Conditional branches which
land on dead code are converted to unconditional jumps, and unconditional
jumps by 0 are removed (these most likely result from earlier dead code
elimination).

Advanced JITs need to be informed about those optimizations, as they
build up their state prior to verification.

First nfp patch is a slight clarification to the code, to avoid
confusion.  Next skip marking is split per reason.  We use skip flag
to mark BPF instructions which won't be reflected in NFP machine code.
There are safety checks which should only apply to some types of skips
so we need a way to express the reason instruction is skipped.  Next
JSET code gen is improved.  And finally we take advantage of the dead
code elimination added to the verifier.

Jakub Kicinski (19):
  selftests: bpf: add trivial JSET tests
  bpf: verifier: teach the verifier to reason about the BPF_JSET
    instruction
  selftests: bpf: verifier: add tests for JSET interpretation
  bpf: verifier: reorder stack size check with dead code sanitization
  bpf: change parameters of call/branch offset adjustment
  bpf: verifier: hard wire branches to dead code
  bpf: verifier: remove dead code
  bpf: verifier: remove unconditional branches by 0
  selftests: bpf: add tests for dead code removal
  selftests: bpf: add missing executables to .gitignore
  bpf: verifier: record original instruction index
  bpf: notify offload JITs about optimizations
  nfp: bpf: don't use instruction number for jump target
  nfp: bpf: split up the skip flag
  nfp: bpf: remove the trivial JSET optimization
  nfp: bpf: optimize codegen for JSET with a constant
  nfp: bpf: save original program length
  nfp: bpf: support optimizing dead branches
  nfp: bpf: support removing dead code

 drivers/net/ethernet/netronome/nfp/bpf/jit.c  |  69 ++-
 drivers/net/ethernet/netronome/nfp/bpf/main.h |  33 +-
 .../net/ethernet/netronome/nfp/bpf/offload.c  |   5 +-
 .../net/ethernet/netronome/nfp/bpf/verifier.c |  63 ++-
 include/linux/bpf.h                           |   7 +
 include/linux/bpf_verifier.h                  |   6 +
 include/linux/filter.h                        |   1 +
 kernel/bpf/core.c                             |  52 +-
 kernel/bpf/offload.c                          |  35 ++
 kernel/bpf/verifier.c                         | 241 ++++++++-
 tools/testing/selftests/bpf/.gitignore        |   1 +
 tools/testing/selftests/bpf/test_btf.c        | 138 +++++-
 tools/testing/selftests/bpf/test_verifier.c   | 465 ++++++++++++++++--
 13 files changed, 1006 insertions(+), 110 deletions(-)

-- 
2.19.2

[PATCH bpf-next 01/19] selftests: bpf: add trivial JSET tests

[Jakub Kicinski]

We seem to have no JSET instruction test, and LLVM does not
generate it at all, so let's add a simple hand-coded test
to make sure JIT implementations are correct.

v2:
 - extend test_verifier to handle multiple inputs and
   add the sample there (Daniel)
 - add a sign extension case

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 tools/testing/selftests/bpf/test_verifier.c | 209 +++++++++++++++++---
 1 file changed, 178 insertions(+), 31 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 6a48905772e3..884ac4092f9b 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -49,6 +49,7 @@
 #define MAX_INSNS	BPF_MAXINSNS
 #define MAX_FIXUPS	8
 #define MAX_NR_MAPS	13
+#define MAX_TEST_RUNS	8
 #define POINTER_VALUE	0xcafe4all
 #define TEST_DATA_LEN	64
 
@@ -86,6 +87,14 @@ struct bpf_test {
 	uint8_t flags;
 	__u8 data[TEST_DATA_LEN];
 	void (*fill_helper)(struct bpf_test *self);
+	uint8_t runs;
+	struct {
+		uint32_t retval, retval_unpriv;
+		union {
+			__u8 data[TEST_DATA_LEN];
+			__u64 data64[TEST_DATA_LEN / 8];
+		};
+	} retvals[MAX_TEST_RUNS];
 };
 
 /* Note we want this to be 64 bit aligned so that the end of our array is
@@ -14179,6 +14188,101 @@ static struct bpf_test tests[] = {
 		.errstr = "!read_ok",
 		.result = REJECT,
 	},
+	{
+		"jset: functional",
+		.insns = {
+			/* r0 = 0 */
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			/* prep for direct packet access via r2 */
+			BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+				    offsetof(struct __sk_buff, data)),
+			BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+				    offsetof(struct __sk_buff, data_end)),
+			BPF_MOV64_REG(BPF_REG_4, BPF_REG_2),
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 8),
+			BPF_JMP_REG(BPF_JLE, BPF_REG_4, BPF_REG_3, 1),
+			BPF_EXIT_INSN(),
+
+			BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_2, 0),
+
+			/* reg, bit 63 or bit 0 set, taken */
+			BPF_LD_IMM64(BPF_REG_8, 0x8000000000000001),
+			BPF_JMP_REG(BPF_JSET, BPF_REG_7, BPF_REG_8, 1),
+			BPF_EXIT_INSN(),
+
+			/* reg, bit 62, not taken */
+			BPF_LD_IMM64(BPF_REG_8, 0x4000000000000000),
+			BPF_JMP_REG(BPF_JSET, BPF_REG_7, BPF_REG_8, 1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+			BPF_EXIT_INSN(),
+
+			/* imm, any bit set, taken */
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_7, -1, 1),
+			BPF_EXIT_INSN(),
+
+			/* imm, bit 31 set, taken */
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_7, 0x80000000, 1),
+			BPF_EXIT_INSN(),
+
+			/* all good - return r0 == 2 */
+			BPF_MOV64_IMM(BPF_REG_0, 2),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+		.result = ACCEPT,
+		.runs = 7,
+		.retvals = {
+			{ .retval = 2,
+			  .data64 = { (1ULL << 63) | (1U << 31) | (1U << 0), }
+			},
+			{ .retval = 2,
+			  .data64 = { (1ULL << 63) | (1U << 31), }
+			},
+			{ .retval = 2,
+			  .data64 = { (1ULL << 31) | (1U << 0), }
+			},
+			{ .retval = 2,
+			  .data64 = { (__u32)-1, }
+			},
+			{ .retval = 2,
+			  .data64 = { ~0x4000000000000000ULL, }
+			},
+			{ .retval = 0,
+			  .data64 = { 0, }
+			},
+			{ .retval = 0,
+			  .data64 = { ~0ULL, }
+			},
+		},
+	},
+	{
+		"jset: sign-extend",
+		.insns = {
+			/* r0 = 0 */
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			/* prep for direct packet access via r2 */
+			BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+				    offsetof(struct __sk_buff, data)),
+			BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
+				    offsetof(struct __sk_buff, data_end)),
+			BPF_MOV64_REG(BPF_REG_4, BPF_REG_2),
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 8),
+			BPF_JMP_REG(BPF_JLE, BPF_REG_4, BPF_REG_3, 1),
+			BPF_EXIT_INSN(),
+
+			BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_2, 0),
+
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_7, 0x80000000, 1),
+			BPF_EXIT_INSN(),
+
+			BPF_MOV64_IMM(BPF_REG_0, 2),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+		.result = ACCEPT,
+		.retval = 2,
+		.data = { 1, 0, 0, 0, 0, 0, 0, 1, },
+	},
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)
@@ -14461,16 +14565,42 @@ static int set_admin(bool admin)
 	return ret;
 }
 
+static int do_prog_test_run(int fd_prog, bool unpriv, uint32_t expected_val,
+			    void *data, size_t size_data)
+{
+	__u8 tmp[TEST_DATA_LEN << 2];
+	__u32 size_tmp = sizeof(tmp);
+	uint32_t retval;
+	int err;
+
+	if (unpriv)
+		set_admin(true);
+	err = bpf_prog_test_run(fd_prog, 1, data, size_data,
+				tmp, &size_tmp, &retval, NULL);
+	if (unpriv)
+		set_admin(false);
+	if (err && errno != 524/*ENOTSUPP*/ && errno != EPERM) {
+		printf("Unexpected bpf_prog_test_run error ");
+		return err;
+	}
+	if (!err && retval != expected_val &&
+	    expected_val != POINTER_VALUE) {
+		printf("FAIL retval %d != %d ", retval, expected_val);
+		return 1;
+	}
+
+	return 0;
+}
+
 static void do_test_single(struct bpf_test *test, bool unpriv,
 			   int *passes, int *errors)
 {
 	int fd_prog, expected_ret, alignment_prevented_execution;
 	int prog_len, prog_type = test->prog_type;
 	struct bpf_insn *prog = test->insns;
+	int run_errs, run_successes;
 	int map_fds[MAX_NR_MAPS];
 	const char *expected_err;
-	uint32_t expected_val;
-	uint32_t retval;
 	__u32 pflags;
 	int i, err;
 
@@ -14494,8 +14624,6 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
 		       test->result_unpriv : test->result;
 	expected_err = unpriv && test->errstr_unpriv ?
 		       test->errstr_unpriv : test->errstr;
-	expected_val = unpriv && test->retval_unpriv ?
-		       test->retval_unpriv : test->retval;
 
 	alignment_prevented_execution = 0;
 
@@ -14507,10 +14635,8 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
 		}
 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 		if (fd_prog >= 0 &&
-		    (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS)) {
+		    (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS))
 			alignment_prevented_execution = 1;
-			goto test_ok;
-		}
 #endif
 	} else {
 		if (fd_prog >= 0) {
@@ -14537,33 +14663,54 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
 		}
 	}
 
-	if (fd_prog >= 0) {
-		__u8 tmp[TEST_DATA_LEN << 2];
-		__u32 size_tmp = sizeof(tmp);
-
-		if (unpriv)
-			set_admin(true);
-		err = bpf_prog_test_run(fd_prog, 1, test->data,
-					sizeof(test->data), tmp, &size_tmp,
-					&retval, NULL);
-		if (unpriv)
-			set_admin(false);
-		if (err && errno != 524/*ENOTSUPP*/ && errno != EPERM) {
-			printf("Unexpected bpf_prog_test_run error\n");
-			goto fail_log;
+	run_errs = 0;
+	run_successes = 0;
+	if (!alignment_prevented_execution && fd_prog >= 0) {
+		uint32_t expected_val;
+		int i;
+
+		if (!test->runs) {
+			expected_val = unpriv && test->retval_unpriv ?
+				test->retval_unpriv : test->retval;
+
+			err = do_prog_test_run(fd_prog, unpriv, expected_val,
+					       test->data, sizeof(test->data));
+			if (err)
+				run_errs++;
+			else
+				run_successes++;
 		}
-		if (!err && retval != expected_val &&
-		    expected_val != POINTER_VALUE) {
-			printf("FAIL retval %d != %d\n", retval, expected_val);
-			goto fail_log;
+
+		for (i = 0; i < test->runs; i++) {
+			if (unpriv && test->retvals[i].retval_unpriv)
+				expected_val = test->retvals[i].retval_unpriv;
+			else
+				expected_val = test->retvals[i].retval;
+
+			err = do_prog_test_run(fd_prog, unpriv, expected_val,
+					       test->retvals[i].data,
+					       sizeof(test->retvals[i].data));
+			if (err) {
+				printf("(run %d/%d) ", i + 1, test->runs);
+				run_errs++;
+			} else {
+				run_successes++;
+			}
 		}
 	}
-#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
-test_ok:
-#endif
-	(*passes)++;
-	printf("OK%s\n", alignment_prevented_execution ?
-	       " (NOTE: not executed due to unknown alignment)" : "");
+
+	if (!run_errs) {
+		(*passes)++;
+		if (run_successes > 1)
+			printf("%d cases ", run_successes);
+		printf("OK");
+		if (alignment_prevented_execution)
+			printf(" (NOTE: not executed due to unknown alignment)");
+		printf("\n");
+	} else {
+		printf("\n");
+		goto fail_log;
+	}
 close_fds:
 	close(fd_prog);
 	for (i = 0; i < MAX_NR_MAPS; i++)
-- 
2.19.2

[PATCH bpf-next 02/19] bpf: verifier: teach the verifier to reason about the BPF_JSET instruction

[Jakub Kicinski]

Some JITs (nfp) try to optimize code on their own.  It could make
sense in case of BPF_JSET instruction which is currently not interpreted
by the verifier, meaning for instance that dead could would not be
detected if it was under BPF_JSET branch.

Teach the verifier basics of BPF_JSET, JIT optimizations will be
removed shortly.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Jiong Wang <jiong.wang@netronome.com>
Acked-by: Edward Cree <ecree@solarflare.com>
---
 kernel/bpf/verifier.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7cd8cde01d08..7857c2625a64 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3859,6 +3859,12 @@ static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
 		if (tnum_is_const(reg->var_off))
 			return !tnum_equals_const(reg->var_off, val);
 		break;
+	case BPF_JSET:
+		if ((~reg->var_off.mask & reg->var_off.value) & val)
+			return 1;
+		if (!((reg->var_off.mask | reg->var_off.value) & val))
+			return 0;
+		break;
 	case BPF_JGT:
 		if (reg->umin_value > val)
 			return 1;
@@ -3943,6 +3949,13 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
 		 */
 		__mark_reg_known(false_reg, val);
 		break;
+	case BPF_JSET:
+		false_reg->var_off = tnum_and(false_reg->var_off,
+					      tnum_const(~val));
+		if (is_power_of_2(val))
+			true_reg->var_off = tnum_or(true_reg->var_off,
+						    tnum_const(val));
+		break;
 	case BPF_JGT:
 		false_reg->umax_value = min(false_reg->umax_value, val);
 		true_reg->umin_value = max(true_reg->umin_value, val + 1);
@@ -4015,6 +4028,13 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
 		 */
 		__mark_reg_known(false_reg, val);
 		break;
+	case BPF_JSET:
+		false_reg->var_off = tnum_and(false_reg->var_off,
+					      tnum_const(~val));
+		if (is_power_of_2(val))
+			true_reg->var_off = tnum_or(true_reg->var_off,
+						    tnum_const(val));
+		break;
 	case BPF_JGT:
 		true_reg->umax_value = min(true_reg->umax_value, val - 1);
 		false_reg->umin_value = max(false_reg->umin_value, val);
-- 
2.19.2

[PATCH bpf-next 03/19] selftests: bpf: verifier: add tests for JSET interpretation

[Jakub Kicinski]

Validate that the verifier reasons correctly about the bounds
and removes dead code based on results of JSET instruction.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 tools/testing/selftests/bpf/test_verifier.c | 96 +++++++++++++++++++++
 1 file changed, 96 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 884ac4092f9b..824748048c16 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -14283,6 +14283,102 @@ static struct bpf_test tests[] = {
 		.retval = 2,
 		.data = { 1, 0, 0, 0, 0, 0, 0, 1, },
 	},
+	{
+		"jset: known const compare",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 1),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.retval_unpriv = 1,
+		.result_unpriv = ACCEPT,
+		.retval = 1,
+		.result = ACCEPT,
+	},
+	{
+		"jset: known const compare bad",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.errstr_unpriv = "!read_ok",
+		.result_unpriv = REJECT,
+		.errstr = "!read_ok",
+		.result = REJECT,
+	},
+	{
+		"jset: unknown const compare taken",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.errstr_unpriv = "!read_ok",
+		.result_unpriv = REJECT,
+		.errstr = "!read_ok",
+		.result = REJECT,
+	},
+	{
+		"jset: unknown const compare not taken",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.errstr_unpriv = "!read_ok",
+		.result_unpriv = REJECT,
+		.errstr = "!read_ok",
+		.result = REJECT,
+	},
+	{
+		"jset: half-known const compare",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_ALU64_IMM(BPF_OR, BPF_REG_0, 2),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 3, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.result_unpriv = ACCEPT,
+		.result = ACCEPT,
+	},
+	{
+		"jset: range",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_ALU64_IMM(BPF_AND, BPF_REG_1, 0xff),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_1, 0xf0, 3),
+			BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 0x10, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_1, 0x10, 1),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 0x10, 1),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+		.result_unpriv = ACCEPT,
+		.result = ACCEPT,
+	},
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)
-- 
2.19.2

[PATCH bpf-next 04/19] bpf: verifier: reorder stack size check with dead code sanitization

[Jakub Kicinski]

Reorder the calls to check_max_stack_depth() and sanitize_dead_code()
to separate functions which can rewrite instructions from pure checks.

No functional changes.

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7857c2625a64..e608c7556e10 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6983,10 +6983,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	free_states(env);
 
 	if (ret == 0)
-		sanitize_dead_code(env);
+		ret = check_max_stack_depth(env);
 
+	/* instruction rewrites happen after this point */
 	if (ret == 0)
-		ret = check_max_stack_depth(env);
+		sanitize_dead_code(env);
 
 	if (ret == 0)
 		/* program is valid, convert *(u32*)(ctx + off) accesses */
-- 
2.19.2

[PATCH bpf-next 05/19] bpf: change parameters of call/branch offset adjustment

[Jakub Kicinski]

In preparation for code removal change parameters to branch
and call adjustment functions to be more universal.  The
current parameters assume we are patching a single instruction
with a longer set.

A diagram may help reading the change, this is for the patch
single case, patching instruction 1 with a replacement of 4:
   ____
0 |____|
1 |____| <-- pos                ^
2 |    | <-- end old  ^         |
3 |    |              |  delta  |  len
4 |____|              |         |  (patch region)
5 |    | <-- end new  v         v
6 |____|

end_old = pos + 1
end_new = pos + delta + 1

If we are before the patch region - curr variable and the target
are fully in old coordinates (hence comparing against end_old).
If we are after the region curr is in new coordinates (hence
the comparison to end_new) but target is in mixed coordinates,
so we just check if it falls before end_new, and if so it needs
the adjustment.

Note that we will not fix up branches which land in removed region
in case of removal, which should be okay, as we are only going to
remove dead code.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 kernel/bpf/core.c | 40 +++++++++++++++++++++-------------------
 1 file changed, 21 insertions(+), 19 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5cdd8da0e7f2..2eb7cc9822bb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -306,15 +306,16 @@ int bpf_prog_calc_tag(struct bpf_prog *fp)
 	return 0;
 }
 
-static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, u32 delta,
-				u32 curr, const bool probe_pass)
+static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, s32 end_old,
+				s32 end_new, u32 curr, const bool probe_pass)
 {
 	const s64 imm_min = S32_MIN, imm_max = S32_MAX;
+	s32 delta = end_new - end_old;
 	s64 imm = insn->imm;
 
-	if (curr < pos && curr + imm + 1 > pos)
+	if (curr < pos && curr + imm + 1 >= end_old)
 		imm += delta;
-	else if (curr > pos + delta && curr + imm + 1 <= pos + delta)
+	else if (curr >= end_new && curr + imm + 1 < end_new)
 		imm -= delta;
 	if (imm < imm_min || imm > imm_max)
 		return -ERANGE;
@@ -323,15 +324,16 @@ static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, u32 delta,
 	return 0;
 }
 
-static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, u32 delta,
-				u32 curr, const bool probe_pass)
+static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, s32 end_old,
+				s32 end_new, u32 curr, const bool probe_pass)
 {
 	const s32 off_min = S16_MIN, off_max = S16_MAX;
+	s32 delta = end_new - end_old;
 	s32 off = insn->off;
 
-	if (curr < pos && curr + off + 1 > pos)
+	if (curr < pos && curr + off + 1 >= end_old)
 		off += delta;
-	else if (curr > pos + delta && curr + off + 1 <= pos + delta)
+	else if (curr >= end_new && curr + off + 1 < end_new)
 		off -= delta;
 	if (off < off_min || off > off_max)
 		return -ERANGE;
@@ -340,10 +342,10 @@ static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, u32 delta,
 	return 0;
 }
 
-static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta,
-			    const bool probe_pass)
+static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, s32 end_old,
+			    s32 end_new, const bool probe_pass)
 {
-	u32 i, insn_cnt = prog->len + (probe_pass ? delta : 0);
+	u32 i, insn_cnt = prog->len + (probe_pass ? end_new - end_old : 0);
 	struct bpf_insn *insn = prog->insnsi;
 	int ret = 0;
 
@@ -355,8 +357,8 @@ static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta,
 		 * do any other adjustments. Therefore skip the patchlet.
 		 */
 		if (probe_pass && i == pos) {
-			i += delta + 1;
-			insn++;
+			i = end_new;
+			insn = prog->insnsi + end_old;
 		}
 		code = insn->code;
 		if (BPF_CLASS(code) != BPF_JMP ||
@@ -366,11 +368,11 @@ static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta,
 		if (BPF_OP(code) == BPF_CALL) {
 			if (insn->src_reg != BPF_PSEUDO_CALL)
 				continue;
-			ret = bpf_adj_delta_to_imm(insn, pos, delta, i,
-						   probe_pass);
+			ret = bpf_adj_delta_to_imm(insn, pos, end_old,
+						   end_new, i, probe_pass);
 		} else {
-			ret = bpf_adj_delta_to_off(insn, pos, delta, i,
-						   probe_pass);
+			ret = bpf_adj_delta_to_off(insn, pos, end_old,
+						   end_new, i, probe_pass);
 		}
 		if (ret)
 			break;
@@ -420,7 +422,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	 * we afterwards may not fail anymore.
 	 */
 	if (insn_adj_cnt > cnt_max &&
-	    bpf_adj_branches(prog, off, insn_delta, true))
+	    bpf_adj_branches(prog, off, off + 1, off + len, true))
 		return NULL;
 
 	/* Several new instructions need to be inserted. Make room
@@ -452,7 +454,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	 * the ship has sailed to reverse to the original state. An
 	 * overflow cannot happen at this point.
 	 */
-	BUG_ON(bpf_adj_branches(prog_adj, off, insn_delta, false));
+	BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));
 
 	bpf_adj_linfo(prog_adj, off, insn_delta);
 
-- 
2.19.2

[PATCH bpf-next 06/19] bpf: verifier: hard wire branches to dead code

[Jakub Kicinski]

Loading programs with dead code becomes more and more
common, as people begin to patch constants at load time.
Turn conditional jumps to unconditional ones, to avoid
potential branch misprediction penalty.

This optimization is enabled for privileged users only.

For branches which just fall through we could just mark
them as not seen and have dead code removal take care of
them, but that seems less clean.

v0.2:
 - don't call capable(CAP_SYS_ADMIN) twice (Jiong).

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 kernel/bpf/verifier.c | 43 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 42 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e608c7556e10..7db2a48ea7f7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6252,6 +6252,40 @@ static void sanitize_dead_code(struct bpf_verifier_env *env)
 	}
 }
 
+static bool insn_is_cond_jump(u8 code)
+{
+	u8 op;
+
+	if (BPF_CLASS(code) != BPF_JMP)
+		return false;
+
+	op = BPF_OP(code);
+	return op != BPF_JA && op != BPF_EXIT && op != BPF_CALL;
+}
+
+static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env)
+{
+	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
+	struct bpf_insn ja = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
+	struct bpf_insn *insn = env->prog->insnsi;
+	const int insn_cnt = env->prog->len;
+	int i;
+
+	for (i = 0; i < insn_cnt; i++, insn++) {
+		if (!insn_is_cond_jump(insn->code))
+			continue;
+
+		if (!aux_data[i + 1].seen)
+			ja.off = insn->off;
+		else if (!aux_data[i + 1 + insn->off].seen)
+			ja.off = 0;
+		else
+			continue;
+
+		memcpy(insn, &ja, sizeof(ja));
+	}
+}
+
 /* convert load instructions that access fields of a context type into a
  * sequence of instructions that access fields of the underlying structure:
  *     struct __sk_buff    -> struct sk_buff
@@ -6892,6 +6926,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	struct bpf_verifier_env *env;
 	struct bpf_verifier_log *log;
 	int ret = -EINVAL;
+	bool is_priv;
 
 	/* no program is valid */
 	if (ARRAY_SIZE(bpf_verifier_ops) == 0)
@@ -6955,7 +6990,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	if (!env->explored_states)
 		goto skip_full_check;
 
-	env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
+	is_priv = capable(CAP_SYS_ADMIN);
+	env->allow_ptr_leaks = is_priv;
 
 	ret = check_subprogs(env);
 	if (ret < 0)
@@ -6986,6 +7022,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 		ret = check_max_stack_depth(env);
 
 	/* instruction rewrites happen after this point */
+	if (is_priv) {
+		if (ret == 0)
+			opt_hard_wire_dead_code_branches(env);
+	}
+
 	if (ret == 0)
 		sanitize_dead_code(env);
 
-- 
2.19.2

[PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Jakub Kicinski]

Instead of overwriting dead code with jmp -1 instructions
remove it completely for root.  Adjust verifier state and
line info appropriately.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 include/linux/filter.h |   1 +
 kernel/bpf/core.c      |  12 ++++
 kernel/bpf/verifier.c  | 139 ++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 149 insertions(+), 3 deletions(-)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 537e9e7c6e6f..c99969022493 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void)
 
 struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 				       const struct bpf_insn *patch, u32 len);
+int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
 
 void bpf_clear_redirect_map(struct bpf_map *map);
 
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 2eb7cc9822bb..e3498d82eb74 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	return prog_adj;
 }
 
+int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
+{
+	/* Branch offsets can't overflow when program is shrinking, no need
+	 * to call bpf_adj_branches(..., true) here
+	 */
+	memmove(prog->insnsi + off, prog->insnsi + off + cnt,
+		sizeof(struct bpf_insn) * (prog->len - off - cnt));
+	prog->len -= cnt;
+
+	return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
+}
+
 void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
 {
 	int i;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7db2a48ea7f7..98a276f4c4e6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6226,6 +6226,113 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	return new_prog;
 }
 
+static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
+					      u32 off, u32 cnt)
+{
+	int i, j;
+
+	/* find first prog starting at or after off (first to remove) */
+	for (i = 0; i < env->subprog_cnt; i++)
+		if (env->subprog_info[i].start >= off)
+			break;
+	/* find first prog starting at or after off + cnt (first to stay) */
+	for (j = i; j < env->subprog_cnt; j++)
+		if (env->subprog_info[j].start >= off + cnt)
+			break;
+	/* if j doesn't start exactly at off + cnt, we are just removing
+	 * the front of previous prog
+	 */
+	if (env->subprog_info[j].start != off + cnt)
+		j--;
+
+	if (j > i) {
+		/* move fake 'exit' subprog as well */
+		int move = env->subprog_cnt + 1 - j;
+
+		memmove(env->subprog_info + i,
+			env->subprog_info + j,
+			sizeof(*env->subprog_info) * move);
+		env->subprog_cnt -= j - i;
+	}
+
+	/* convert i from "first prog to remove" to "first to adjust" */
+	if (env->subprog_info[i].start == off)
+		i++;
+
+	/* update fake 'exit' subprog as well */
+	for (; i <= env->subprog_cnt; i++)
+		env->subprog_info[i].start -= cnt;
+
+	return 0;
+}
+
+static void bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
+				       u32 cnt)
+{
+	struct bpf_prog *prog = env->prog;
+	u32 i, l_off, l_cnt, nr_linfo;
+	struct bpf_line_info *linfo;
+
+	nr_linfo = prog->aux->nr_linfo;
+	if (!nr_linfo || !cnt)
+		return;
+
+	linfo = prog->aux->linfo;
+
+	for (i = 0; i < nr_linfo; i++)
+		if (linfo[i].insn_off >= off)
+			break;
+
+	l_off = i;
+	l_cnt = 0;
+	for (; i < nr_linfo; i++)
+		if (linfo[i].insn_off < off + cnt)
+			l_cnt++;
+		else
+			break;
+
+	/* Remove the line info which refers to the removed instructions */
+	if (l_cnt) {
+		memmove(linfo + l_off, linfo + i,
+			sizeof(*linfo) * (nr_linfo - i));
+
+		prog->aux->nr_linfo -= l_cnt;
+		nr_linfo = prog->aux->nr_linfo;
+	}
+
+	/* Pull all linfo[i].insn_off >= off + cnt in by cnt */
+	for (i = l_off; i < nr_linfo; i++)
+		linfo[i].insn_off -= cnt;
+
+	/* Fix up all subprogs (incl. 'exit') which start >= off */
+	for (i = 0; i <= env->subprog_cnt; i++)
+		if (env->subprog_info[i].linfo_idx > l_off + l_cnt)
+			env->subprog_info[i].linfo_idx -= l_cnt;
+		else if (env->subprog_info[i].linfo_idx > l_off)
+			env->subprog_info[i].linfo_idx = l_off;
+}
+
+static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
+{
+	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
+	unsigned int orig_prog_len = env->prog->len;
+	int err;
+
+	if (!cnt)
+		return 0;
+
+	err = bpf_remove_insns(env->prog, off, cnt);
+	if (err)
+		return err;
+
+	bpf_adj_linfo_after_remove(env, off, cnt);
+
+	memmove(aux_data + off,	aux_data + off + cnt,
+		sizeof(*aux_data) * (orig_prog_len - off - cnt));
+
+	return adjust_subprog_starts_after_remove(env, off, cnt);
+}
+
 /* The verifier does more data flow analysis than llvm and will not
  * explore branches that are dead at run time. Malicious programs can
  * have dead code too. Therefore replace all dead at-run-time code
@@ -6286,6 +6393,30 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env)
 	}
 }
 
+static int opt_remove_dead_code(struct bpf_verifier_env *env)
+{
+	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
+	int insn_cnt = env->prog->len;
+	int i, err;
+
+	for (i = 0; i < insn_cnt; i++) {
+		int j;
+
+		j = 0;
+		while (i + j < insn_cnt && !aux_data[i + j].seen)
+			j++;
+		if (!j)
+			continue;
+
+		err = verifier_remove_insns(env, i, j);
+		if (err)
+			return err;
+		insn_cnt = env->prog->len;
+	}
+
+	return 0;
+}
+
 /* convert load instructions that access fields of a context type into a
  * sequence of instructions that access fields of the underlying structure:
  *     struct __sk_buff    -> struct sk_buff
@@ -7025,11 +7156,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	if (is_priv) {
 		if (ret == 0)
 			opt_hard_wire_dead_code_branches(env);
+		if (ret == 0)
+			ret = opt_remove_dead_code(env);
+	} else {
+		if (ret == 0)
+			sanitize_dead_code(env);
 	}
 
-	if (ret == 0)
-		sanitize_dead_code(env);
-
 	if (ret == 0)
 		/* program is valid, convert *(u32*)(ctx + off) accesses */
 		ret = convert_ctx_accesses(env);
-- 
2.19.2

[PATCH bpf-next 08/19] bpf: verifier: remove unconditional branches by 0

[Jakub Kicinski]

Unconditional branches by 0 instructions are basically noops
but they can result from earlier optimizations, e.g. a conditional
jumps which would never be taken or a conditional jump around
dead code.

Remove those branches.

v0.2:
 - s/opt_remove_dead_branches/opt_remove_nops/ (Jiong).

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 98a276f4c4e6..92f9f2ee0f7f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6417,6 +6417,27 @@ static int opt_remove_dead_code(struct bpf_verifier_env *env)
 	return 0;
 }
 
+static int opt_remove_nops(struct bpf_verifier_env *env)
+{
+	const struct bpf_insn ja = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
+	struct bpf_insn *insn = env->prog->insnsi;
+	int insn_cnt = env->prog->len;
+	int i, err;
+
+	for (i = 0; i < insn_cnt; i++) {
+		if (memcmp(&insn[i], &ja, sizeof(ja)))
+			continue;
+
+		err = verifier_remove_insns(env, i, 1);
+		if (err)
+			return err;
+		insn_cnt--;
+		i--;
+	}
+
+	return 0;
+}
+
 /* convert load instructions that access fields of a context type into a
  * sequence of instructions that access fields of the underlying structure:
  *     struct __sk_buff    -> struct sk_buff
@@ -7158,6 +7179,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 			opt_hard_wire_dead_code_branches(env);
 		if (ret == 0)
 			ret = opt_remove_dead_code(env);
+		if (ret == 0)
+			ret = opt_remove_nops(env);
 	} else {
 		if (ret == 0)
 			sanitize_dead_code(env);
-- 
2.19.2

[PATCH bpf-next 09/19] selftests: bpf: add tests for dead code removal

[Jakub Kicinski]

Add tests for newly added dead code elimination.  Both verifier
and BTF tests are added.  BTF test infrastructure has to be
extended to be able to account for line info which is eliminated
during dead code removal.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 tools/testing/selftests/bpf/test_btf.c      | 138 ++++++++++++++++-
 tools/testing/selftests/bpf/test_verifier.c | 160 ++++++++++++++++++++
 2 files changed, 296 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_btf.c b/tools/testing/selftests/bpf/test_btf.c
index 8024b7d4c354..dde20b6fa7b6 100644
--- a/tools/testing/selftests/bpf/test_btf.c
+++ b/tools/testing/selftests/bpf/test_btf.c
@@ -4070,6 +4070,8 @@ static struct prog_info_raw_test {
 	__u32 line_info_rec_size;
 	__u32 nr_jited_ksyms;
 	bool expected_prog_load_failure;
+	__u32 dead_code_cnt;
+	__u32 dead_code_mask;
 } info_raw_tests[] = {
 {
 	.descr = "func_type (main func + one sub)",
@@ -4469,6 +4471,127 @@ static struct prog_info_raw_test {
 	.expected_prog_load_failure = true,
 },
 
+{
+	.descr = "line_info (dead start)",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0int\0/* dead jmp */\0int a=1;\0int b=2;\0return a + b;\0return a + b;"),
+	.insns = {
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_1, 2),
+		BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+		BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+	.func_info_cnt = 0,
+	.line_info = {
+		BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(1, 0, NAME_TBD, 2, 9),
+		BPF_LINE_INFO_ENC(2, 0, NAME_TBD, 3, 8),
+		BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 4, 7),
+		BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 5, 6),
+		BTF_END_RAW,
+	},
+	.line_info_rec_size = sizeof(struct bpf_line_info),
+	.nr_jited_ksyms = 1,
+	.dead_code_cnt = 1,
+	.dead_code_mask = 0x01,
+},
+
+{
+	.descr = "line_info (dead end)",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0int\0int a=1;\0int b=2;\0return a + b;\0/* dead jmp */\0return a + b;\0/* dead exit */"),
+	.insns = {
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_1, 2),
+		BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+		BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1),
+		BPF_EXIT_INSN(),
+		BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+	.func_info_cnt = 0,
+	.line_info = {
+		BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 12),
+		BPF_LINE_INFO_ENC(1, 0, NAME_TBD, 2, 11),
+		BPF_LINE_INFO_ENC(2, 0, NAME_TBD, 3, 10),
+		BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 4, 9),
+		BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 5, 8),
+		BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 6, 7),
+		BTF_END_RAW,
+	},
+	.line_info_rec_size = sizeof(struct bpf_line_info),
+	.nr_jited_ksyms = 1,
+	.dead_code_cnt = 2,
+	.dead_code_mask = 0x28,
+},
+
+{
+	.descr = "line_info (dead code + subprog + func_info)",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_FUNC_PROTO_ENC(1, 1),			/* [2] */
+			BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1),
+		BTF_FUNC_ENC(NAME_TBD, 2),			/* [3] */
+		BTF_FUNC_ENC(NAME_TBD, 2),			/* [4] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0int\0x\0sub\0main\0int a=1+1;\0/* dead jmp */"
+		    "\0/* dead */\0/* dead */\0/* dead */\0/* dead */"
+		    "\0/* dead */\0/* dead */\0/* dead */\0/* dead */"
+		    "\0return func(a);\0b+=1;\0return b;"),
+	.insns = {
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1),
+		BPF_MOV64_REG(BPF_REG_1, BPF_REG_2),
+		BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 8),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_MOV64_IMM(BPF_REG_2, 1),
+		BPF_CALL_REL(1),
+		BPF_EXIT_INSN(),
+		BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
+		BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+	.func_info_cnt = 2,
+	.func_info_rec_size = 8,
+	.func_info = { {0, 4}, {14, 3} },
+	.line_info = {
+		BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(7, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(8, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(9, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(10, 0, NAME_TBD, 1, 10),
+		BPF_LINE_INFO_ENC(11, 0, NAME_TBD, 2, 9),
+		BPF_LINE_INFO_ENC(12, 0, NAME_TBD, 2, 9),
+		BPF_LINE_INFO_ENC(14, 0, NAME_TBD, 3, 8),
+		BPF_LINE_INFO_ENC(16, 0, NAME_TBD, 4, 7),
+		BTF_END_RAW,
+	},
+	.line_info_rec_size = sizeof(struct bpf_line_info),
+	.nr_jited_ksyms = 2,
+	.dead_code_cnt = 9,
+	.dead_code_mask = 0x3fe,
+},
+
 };
 
 static size_t probe_prog_length(const struct bpf_insn *fp)
@@ -4610,6 +4733,7 @@ static int test_get_linfo(const struct prog_info_raw_test *test,
 	struct bpf_prog_info info = {};
 	__u32 *jited_func_lens = NULL;
 	__u64 cur_func_ksyms;
+	__u32 dead_insns;
 	int err;
 
 	jited_cnt = cnt;
@@ -4720,12 +4844,20 @@ static int test_get_linfo(const struct prog_info_raw_test *test,
 		goto done;
 	}
 
+	dead_insns = 0;
+	while (test->dead_code_mask & (1 << dead_insns))
+		dead_insns++;
+
 	CHECK(linfo[0].insn_off, "linfo[0].insn_off:%u",
 	      linfo[0].insn_off);
 	for (i = 1; i < cnt; i++) {
 		const struct bpf_line_info *expected_linfo;
 
-		expected_linfo = patched_linfo + (i * test->line_info_rec_size);
+		while (test->dead_code_mask & (1 << (i + dead_insns)))
+			dead_insns++;
+
+		expected_linfo = patched_linfo +
+			((i + dead_insns) * test->line_info_rec_size);
 		if (CHECK(linfo[i].insn_off <= linfo[i - 1].insn_off,
 			  "linfo[%u].insn_off:%u <= linfo[%u].insn_off:%u",
 			  i, linfo[i].insn_off,
@@ -4883,7 +5015,9 @@ static int do_test_info_raw(unsigned int test_num)
 	if (err)
 		goto done;
 
-	err = test_get_linfo(test, patched_linfo, attr.line_info_cnt, prog_fd);
+	err = test_get_linfo(test, patched_linfo,
+			     attr.line_info_cnt - test->dead_code_cnt,
+			     prog_fd);
 	if (err)
 		goto done;
 
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 824748048c16..d34172575914 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -14379,6 +14379,166 @@ static struct bpf_test tests[] = {
 		.result_unpriv = ACCEPT,
 		.result = ACCEPT,
 	},
+	{
+		"dead code: start",
+		.insns = {
+			BPF_JMP_IMM(BPF_JA, 0, 0, 2),
+			BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 2),
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, -4),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: mid 1",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 0, 1),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 0),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: mid 2",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+				     BPF_FUNC_get_prandom_u32),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 4),
+			BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 2),
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 1),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 1,
+	},
+	{
+		"dead code: end 1",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1),
+			BPF_EXIT_INSN(),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: end 2",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 12),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: end 3",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+			BPF_MOV64_IMM(BPF_REG_0, 12),
+			BPF_JMP_IMM(BPF_JA, 0, 0, -5),
+		},
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: tail of main + func",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1),
+			BPF_EXIT_INSN(),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 12),
+			BPF_EXIT_INSN(),
+		},
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: tail of main + two functions",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1),
+			BPF_EXIT_INSN(),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 12),
+			BPF_EXIT_INSN(),
+		},
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: function in the middle and mid of another func",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_1, 7),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 3),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 12),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_IMM(BPF_REG_0, 7),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 7, 1),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -5),
+			BPF_EXIT_INSN(),
+		},
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.result = ACCEPT,
+		.retval = 7,
+	},
+	{
+		"dead code: middle of main before call",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_1, 2),
+			BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 2, 1),
+			BPF_MOV64_IMM(BPF_REG_1, 5),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
+			BPF_EXIT_INSN(),
+		},
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.result = ACCEPT,
+		.retval = 2,
+	},
+	{
+		"dead code: start of a function",
+		.insns = {
+			BPF_MOV64_IMM(BPF_REG_1, 2),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 0),
+			BPF_MOV64_REG(BPF_REG_0, BPF_REG_1),
+			BPF_EXIT_INSN(),
+		},
+		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+		.result_unpriv = REJECT,
+		.result = ACCEPT,
+		.retval = 2,
+	},
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)
-- 
2.19.2

[PATCH bpf-next 10/19] selftests: bpf: add missing executables to .gitignore

[Jakub Kicinski]

commit 435f90a338ae ("selftests/bpf: add a test case for sock_ops
perf-event notification") missed adding new test to gitignore.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
---
 tools/testing/selftests/bpf/.gitignore | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/testing/selftests/bpf/.gitignore b/tools/testing/selftests/bpf/.gitignore
index 1b799e30c06d..4a9785043a39 100644
--- a/tools/testing/selftests/bpf/.gitignore
+++ b/tools/testing/selftests/bpf/.gitignore
@@ -27,3 +27,4 @@ test_flow_dissector
 flow_dissector_load
 test_netcnt
 test_section_names
+test_tcpnotify_user
-- 
2.19.2

[PATCH bpf-next 11/19] bpf: verifier: record original instruction index

[Jakub Kicinski]

The communication between the verifier and advanced JITs is based
on instruction indexes.  We have to keep them stable throughout
the optimizations otherwise referring to a particular instruction
gets messy quickly.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 include/linux/bpf_verifier.h | 1 +
 kernel/bpf/verifier.c        | 8 +++++---
 2 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index c233efc106c6..414d1aeba897 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -176,6 +176,7 @@ struct bpf_insn_aux_data {
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
 	int sanitize_stack_off; /* stack slot to be cleared */
 	bool seen; /* this insn was processed by the verifier */
+	unsigned int orig_idx; /* original instruction index */
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 92f9f2ee0f7f..b03dfc1c1057 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7077,7 +7077,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 {
 	struct bpf_verifier_env *env;
 	struct bpf_verifier_log *log;
-	int ret = -EINVAL;
+	int i, len, ret = -EINVAL;
 	bool is_priv;
 
 	/* no program is valid */
@@ -7092,12 +7092,14 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 		return -ENOMEM;
 	log = &env->log;
 
+	len = (*prog)->len;
 	env->insn_aux_data =
-		vzalloc(array_size(sizeof(struct bpf_insn_aux_data),
-				   (*prog)->len));
+		vzalloc(array_size(sizeof(struct bpf_insn_aux_data), len));
 	ret = -ENOMEM;
 	if (!env->insn_aux_data)
 		goto err_free_env;
+	for (i = 0; i < len; i++)
+		env->insn_aux_data[i].orig_idx = i;
 	env->prog = *prog;
 	env->ops = bpf_verifier_ops[env->prog->type];
 
-- 
2.19.2

[PATCH bpf-next 12/19] bpf: notify offload JITs about optimizations

[Jakub Kicinski]

Let offload JITs know when instructions are replaced and optimized
out, so they can update their state appropriately.  Use the recently
added original instruction index as instructions may get renumbered.
The optimizations are best effort, if JIT returns an error from any
callback verifier will stop notifying it as state may now be out of
sync, but the verifier continues making progress.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 include/linux/bpf.h          |  7 +++++++
 include/linux/bpf_verifier.h |  5 +++++
 kernel/bpf/offload.c         | 35 +++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c        |  7 +++++++
 4 files changed, 54 insertions(+)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index e734f163bd0b..3851529062ec 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -268,9 +268,15 @@ struct bpf_verifier_ops {
 };
 
 struct bpf_prog_offload_ops {
+	/* verifier basic callbacks */
 	int (*insn_hook)(struct bpf_verifier_env *env,
 			 int insn_idx, int prev_insn_idx);
 	int (*finalize)(struct bpf_verifier_env *env);
+	/* verifier optimization callbacks (called after .finalize) */
+	int (*replace_insn)(struct bpf_verifier_env *env, u32 off,
+			    struct bpf_insn *insn);
+	int (*remove_insns)(struct bpf_verifier_env *env, u32 off, u32 cnt);
+	/* program management callbacks */
 	int (*prepare)(struct bpf_prog *prog);
 	int (*translate)(struct bpf_prog *prog);
 	void (*destroy)(struct bpf_prog *prog);
@@ -283,6 +289,7 @@ struct bpf_prog_offload {
 	void			*dev_priv;
 	struct list_head	offloads;
 	bool			dev_state;
+	bool			opt_failed;
 	void			*jited_image;
 	u32			jited_len;
 };
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 414d1aeba897..ff6653fc8c45 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -253,5 +253,10 @@ int bpf_prog_offload_verifier_prep(struct bpf_prog *prog);
 int bpf_prog_offload_verify_insn(struct bpf_verifier_env *env,
 				 int insn_idx, int prev_insn_idx);
 int bpf_prog_offload_finalize(struct bpf_verifier_env *env);
+void
+bpf_prog_offload_replace_insn(struct bpf_verifier_env *env, u32 off,
+			      struct bpf_insn *insn);
+void
+bpf_prog_offload_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt);
 
 #endif /* _LINUX_BPF_VERIFIER_H */
diff --git a/kernel/bpf/offload.c b/kernel/bpf/offload.c
index 54cf2b9c44a4..19377ad221e2 100644
--- a/kernel/bpf/offload.c
+++ b/kernel/bpf/offload.c
@@ -173,6 +173,41 @@ int bpf_prog_offload_finalize(struct bpf_verifier_env *env)
 	return ret;
 }
 
+void
+bpf_prog_offload_replace_insn(struct bpf_verifier_env *env, u32 off,
+			      struct bpf_insn *insn)
+{
+	const struct bpf_prog_offload_ops *ops;
+	struct bpf_prog_offload *offload;
+	int ret = -ENODEV;
+
+	down_read(&bpf_devs_lock);
+	offload = env->prog->aux->offload;
+	if (offload) {
+		ops = offload->offdev->ops;
+		if (!offload->opt_failed && ops->replace_insn)
+			ret = ops->replace_insn(env, off, insn);
+		offload->opt_failed |= ret;
+	}
+	up_read(&bpf_devs_lock);
+}
+
+void
+bpf_prog_offload_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
+{
+	struct bpf_prog_offload *offload;
+	int ret = -ENODEV;
+
+	down_read(&bpf_devs_lock);
+	offload = env->prog->aux->offload;
+	if (offload) {
+		if (!offload->opt_failed && offload->offdev->ops->remove_insns)
+			ret = offload->offdev->ops->remove_insns(env, off, cnt);
+		offload->opt_failed |= ret;
+	}
+	up_read(&bpf_devs_lock);
+}
+
 static void __bpf_prog_offload_destroy(struct bpf_prog *prog)
 {
 	struct bpf_prog_offload *offload = prog->aux->offload;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b03dfc1c1057..bfef387ddfaa 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6321,6 +6321,9 @@ static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 	if (!cnt)
 		return 0;
 
+	if (bpf_prog_is_dev_bound(env->prog->aux))
+		bpf_prog_offload_remove_insns(env, aux_data[off].orig_idx, cnt);
+
 	err = bpf_remove_insns(env->prog, off, cnt);
 	if (err)
 		return err;
@@ -6389,6 +6392,10 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env)
 		else
 			continue;
 
+		if (bpf_prog_is_dev_bound(env->prog->aux))
+			bpf_prog_offload_replace_insn(env, aux_data[i].orig_idx,
+						      &ja);
+
 		memcpy(insn, &ja, sizeof(ja));
 	}
 }
-- 
2.19.2

[PATCH bpf-next 13/19] nfp: bpf: don't use instruction number for jump target

[Jakub Kicinski]

Instruction number is meaningless at code gen phase.  The target
of the instruction is overwritten by nfp_fixup_branches().  The
convention is to put the raw offset in target address as a place
holder.  See cmp_* functions.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 662cbc21d909..284a6a98a4fc 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -3189,7 +3189,7 @@ bpf_to_bpf_call(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 		wrp_immed_relo(nfp_prog, imm_b(nfp_prog), 0, RELO_IMMED_REL);
 	} else {
 		ret_tgt = nfp_prog_current_offset(nfp_prog) + 2;
-		emit_br(nfp_prog, BR_UNC, meta->n + 1 + meta->insn.imm, 1);
+		emit_br(nfp_prog, BR_UNC, meta->insn.imm, 1);
 		offset_br = nfp_prog_current_offset(nfp_prog);
 	}
 	wrp_immed_relo(nfp_prog, ret_reg(nfp_prog), ret_tgt, RELO_IMMED_REL);
-- 
2.19.2

[PATCH bpf-next 14/19] nfp: bpf: split up the skip flag

[Jakub Kicinski]

We fail program loading if jump lands on a skipped instruction.
This is for historical reasons, it used to be that we only skipped
instructions optimized out based on prior context, and therefore
the optimization would be buggy if we jumped directly to such
instruction (because the context would be skipped by the jump).

There are cases where instructions can be skipped without any
context, for example there is no point in generating code for:

	 r0 |= 0

We will also soon support dropping dead code, so make the skip
logic differentiate between "optimized with preceding context"
vs other skip types.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c  | 38 ++++++++++---------
 drivers/net/ethernet/netronome/nfp/bpf/main.h |  9 ++++-
 2 files changed, 27 insertions(+), 20 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 284a6a98a4fc..188270c681fc 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -1266,7 +1266,7 @@ wrp_alu64_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 	u64 imm = insn->imm; /* sign extend */
 
 	if (skip) {
-		meta->skip = true;
+		meta->flags |= FLAG_INSN_SKIP_NOOP;
 		return 0;
 	}
 
@@ -1296,7 +1296,7 @@ wrp_alu32_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 	const struct bpf_insn *insn = &meta->insn;
 
 	if (skip) {
-		meta->skip = true;
+		meta->flags |= FLAG_INSN_SKIP_NOOP;
 		return 0;
 	}
 
@@ -3055,7 +3055,7 @@ static int jset_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 	swreg tmp_reg;
 
 	if (!imm) {
-		meta->skip = true;
+		meta->flags |= FLAG_INSN_SKIP_NOOP;
 		return 0;
 	}
 
@@ -3402,7 +3402,7 @@ static int nfp_fixup_branches(struct nfp_prog *nfp_prog)
 	int err;
 
 	list_for_each_entry(meta, &nfp_prog->insns, l) {
-		if (meta->skip)
+		if (meta->flags & FLAG_INSN_SKIP_MASK)
 			continue;
 		if (BPF_CLASS(meta->insn.code) != BPF_JMP)
 			continue;
@@ -3446,7 +3446,7 @@ static int nfp_fixup_branches(struct nfp_prog *nfp_prog)
 
 		jmp_dst = meta->jmp_dst;
 
-		if (jmp_dst->skip) {
+		if (jmp_dst->flags & FLAG_INSN_SKIP_PREC_DEPENDENT) {
 			pr_err("Branch landing on removed instruction!!\n");
 			return -ELOOP;
 		}
@@ -3696,7 +3696,7 @@ static int nfp_translate(struct nfp_prog *nfp_prog)
 				return nfp_prog->error;
 		}
 
-		if (meta->skip) {
+		if (meta->flags & FLAG_INSN_SKIP_MASK) {
 			nfp_prog->n_translated++;
 			continue;
 		}
@@ -3744,10 +3744,10 @@ static void nfp_bpf_opt_reg_init(struct nfp_prog *nfp_prog)
 		/* Programs start with R6 = R1 but we ignore the skb pointer */
 		if (insn.code == (BPF_ALU64 | BPF_MOV | BPF_X) &&
 		    insn.src_reg == 1 && insn.dst_reg == 6)
-			meta->skip = true;
+			meta->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
 
 		/* Return as soon as something doesn't match */
-		if (!meta->skip)
+		if (!(meta->flags & FLAG_INSN_SKIP_MASK))
 			return;
 	}
 }
@@ -3762,7 +3762,7 @@ static void nfp_bpf_opt_neg_add_sub(struct nfp_prog *nfp_prog)
 	list_for_each_entry(meta, &nfp_prog->insns, l) {
 		struct bpf_insn insn = meta->insn;
 
-		if (meta->skip)
+		if (meta->flags & FLAG_INSN_SKIP_MASK)
 			continue;
 
 		if (BPF_CLASS(insn.code) != BPF_ALU &&
@@ -3836,7 +3836,7 @@ static void nfp_bpf_opt_ld_mask(struct nfp_prog *nfp_prog)
 		if (meta2->flags & FLAG_INSN_IS_JUMP_DST)
 			continue;
 
-		meta2->skip = true;
+		meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
 	}
 }
 
@@ -3876,8 +3876,8 @@ static void nfp_bpf_opt_ld_shift(struct nfp_prog *nfp_prog)
 		    meta3->flags & FLAG_INSN_IS_JUMP_DST)
 			continue;
 
-		meta2->skip = true;
-		meta3->skip = true;
+		meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
+		meta3->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
 	}
 }
 
@@ -4072,7 +4072,8 @@ static void nfp_bpf_opt_ldst_gather(struct nfp_prog *nfp_prog)
 				}
 
 				head_ld_meta->paired_st = &head_st_meta->insn;
-				head_st_meta->skip = true;
+				head_st_meta->flags |=
+					FLAG_INSN_SKIP_PREC_DEPENDENT;
 			} else {
 				head_ld_meta->ldst_gather_len = 0;
 			}
@@ -4105,8 +4106,8 @@ static void nfp_bpf_opt_ldst_gather(struct nfp_prog *nfp_prog)
 			head_ld_meta = meta1;
 			head_st_meta = meta2;
 		} else {
-			meta1->skip = true;
-			meta2->skip = true;
+			meta1->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
+			meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT;
 		}
 
 		head_ld_meta->ldst_gather_len += BPF_LDST_BYTES(ld);
@@ -4131,7 +4132,7 @@ static void nfp_bpf_opt_pkt_cache(struct nfp_prog *nfp_prog)
 		if (meta->flags & FLAG_INSN_IS_JUMP_DST)
 			cache_avail = false;
 
-		if (meta->skip)
+		if (meta->flags & FLAG_INSN_SKIP_MASK)
 			continue;
 
 		insn = &meta->insn;
@@ -4217,7 +4218,7 @@ static void nfp_bpf_opt_pkt_cache(struct nfp_prog *nfp_prog)
 	}
 
 	list_for_each_entry(meta, &nfp_prog->insns, l) {
-		if (meta->skip)
+		if (meta->flags & FLAG_INSN_SKIP_MASK)
 			continue;
 
 		if (is_mbpf_load_pkt(meta) && !meta->ldst_gather_len) {
@@ -4253,7 +4254,8 @@ static int nfp_bpf_replace_map_ptrs(struct nfp_prog *nfp_prog)
 	u32 id;
 
 	nfp_for_each_insn_walk2(nfp_prog, meta1, meta2) {
-		if (meta1->skip || meta2->skip)
+		if (meta1->flags & FLAG_INSN_SKIP_MASK ||
+		    meta2->flags & FLAG_INSN_SKIP_MASK)
 			continue;
 
 		if (meta1->insn.code != (BPF_LD | BPF_IMM | BPF_DW) ||
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h
index 941277936475..40291aedd895 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/main.h
+++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h
@@ -243,6 +243,13 @@ struct nfp_bpf_reg_state {
 #define FLAG_INSN_IS_JUMP_DST			BIT(0)
 #define FLAG_INSN_IS_SUBPROG_START		BIT(1)
 #define FLAG_INSN_PTR_CALLER_STACK_FRAME	BIT(2)
+/* Instruction is pointless, noop even on its own */
+#define FLAG_INSN_SKIP_NOOP			BIT(3)
+/* Instruction is optimized out based on preceding instructions */
+#define FLAG_INSN_SKIP_PREC_DEPENDENT		BIT(4)
+
+#define FLAG_INSN_SKIP_MASK		(FLAG_INSN_SKIP_NOOP | \
+					 FLAG_INSN_SKIP_PREC_DEPENDENT)
 
 /**
  * struct nfp_insn_meta - BPF instruction wrapper
@@ -271,7 +278,6 @@ struct nfp_bpf_reg_state {
  * @n: eBPF instruction number
  * @flags: eBPF instruction extra optimization flags
  * @subprog_idx: index of subprogram to which the instruction belongs
- * @skip: skip this instruction (optimized out)
  * @double_cb: callback for second part of the instruction
  * @l: link on nfp_prog->insns list
  */
@@ -319,7 +325,6 @@ struct nfp_insn_meta {
 	unsigned short n;
 	unsigned short flags;
 	unsigned short subprog_idx;
-	bool skip;
 	instr_cb_t double_cb;
 
 	struct list_head l;
-- 
2.19.2

[PATCH bpf-next 15/19] nfp: bpf: remove the trivial JSET optimization

[Jakub Kicinski]

The verifier will now understand the JSET instruction, so don't
mark the dead branch in the JIT as noop.  We won't generate any
code, anyway.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c | 5 -----
 1 file changed, 5 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 188270c681fc..6e83bd4707fb 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -3054,11 +3054,6 @@ static int jset_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 	u64 imm = insn->imm; /* sign extend */
 	swreg tmp_reg;
 
-	if (!imm) {
-		meta->flags |= FLAG_INSN_SKIP_NOOP;
-		return 0;
-	}
-
 	if (imm & ~0U) {
 		tmp_reg = ur_load_imm_any(nfp_prog, imm & ~0U, imm_b(nfp_prog));
 		emit_alu(nfp_prog, reg_none(),
-- 
2.19.2

[PATCH bpf-next 16/19] nfp: bpf: optimize codegen for JSET with a constant

[Jakub Kicinski]

The top word of the constant can only have bits set if sign
extension set it to all-1, therefore we don't really have to
mask the top half of the register.  We can just OR it into
the result as is.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c | 22 +++++++++-----------
 1 file changed, 10 insertions(+), 12 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 6e83bd4707fb..054382b9cbe6 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -3052,21 +3052,19 @@ static int jset_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
 {
 	const struct bpf_insn *insn = &meta->insn;
 	u64 imm = insn->imm; /* sign extend */
+	u8 dst_gpr = insn->dst_reg * 2;
 	swreg tmp_reg;
 
-	if (imm & ~0U) {
-		tmp_reg = ur_load_imm_any(nfp_prog, imm & ~0U, imm_b(nfp_prog));
-		emit_alu(nfp_prog, reg_none(),
-			 reg_a(insn->dst_reg * 2), ALU_OP_AND, tmp_reg);
-		emit_br(nfp_prog, BR_BNE, insn->off, 0);
-	}
-
-	if (imm >> 32) {
-		tmp_reg = ur_load_imm_any(nfp_prog, imm >> 32, imm_b(nfp_prog));
+	tmp_reg = ur_load_imm_any(nfp_prog, imm & ~0U, imm_b(nfp_prog));
+	emit_alu(nfp_prog, imm_b(nfp_prog),
+		 reg_a(dst_gpr), ALU_OP_AND, tmp_reg);
+	/* Upper word of the mask can only be 0 or ~0 from sign extension,
+	 * so either ignore it or OR the whole thing in.
+	 */
+	if (imm >> 32)
 		emit_alu(nfp_prog, reg_none(),
-			 reg_a(insn->dst_reg * 2 + 1), ALU_OP_AND, tmp_reg);
-		emit_br(nfp_prog, BR_BNE, insn->off, 0);
-	}
+			 reg_a(dst_gpr + 1), ALU_OP_OR, imm_b(nfp_prog));
+	emit_br(nfp_prog, BR_BNE, insn->off, 0);
 
 	return 0;
 }
-- 
2.19.2

[PATCH bpf-next 17/19] nfp: bpf: save original program length

[Jakub Kicinski]

Instead of passing env->prog->len around, and trying to adjust
for optimized out instructions just save the initial number
of instructions in struct nfp_prog.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/jit.c     |  4 ++--
 drivers/net/ethernet/netronome/nfp/bpf/main.h    |  6 ++++--
 drivers/net/ethernet/netronome/nfp/bpf/offload.c |  3 ++-
 .../net/ethernet/netronome/nfp/bpf/verifier.c    | 16 +++++++---------
 4 files changed, 15 insertions(+), 14 deletions(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
index 054382b9cbe6..3308fd92c017 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
@@ -4327,7 +4327,7 @@ int nfp_bpf_jit(struct nfp_prog *nfp_prog)
 	return ret;
 }
 
-void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt)
+void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog)
 {
 	struct nfp_insn_meta *meta;
 
@@ -4355,7 +4355,7 @@ void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt)
 		else
 			dst_idx = meta->n + 1 + meta->insn.off;
 
-		dst_meta = nfp_bpf_goto_meta(nfp_prog, meta, dst_idx, cnt);
+		dst_meta = nfp_bpf_goto_meta(nfp_prog, meta, dst_idx);
 
 		if (pseudo_call)
 			dst_meta->flags |= FLAG_INSN_IS_SUBPROG_START;
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h
index 40291aedd895..07879eee3d46 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/main.h
+++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h
@@ -462,6 +462,7 @@ struct nfp_bpf_subprog_info {
  * @subprog_cnt: number of sub-programs, including main function
  * @map_records: the map record pointers from bpf->maps_neutral
  * @subprog: pointer to an array of objects holding info about sub-programs
+ * @n_insns: number of instructions on @insns list
  * @insns: list of BPF instruction wrappers (struct nfp_insn_meta)
  */
 struct nfp_prog {
@@ -494,6 +495,7 @@ struct nfp_prog {
 	struct nfp_bpf_neutral_map **map_records;
 	struct nfp_bpf_subprog_info *subprog;
 
+	unsigned int n_insns;
 	struct list_head insns;
 };
 
@@ -510,7 +512,7 @@ struct nfp_bpf_vnic {
 };
 
 bool nfp_is_subprog_start(struct nfp_insn_meta *meta);
-void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt);
+void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog);
 int nfp_bpf_jit(struct nfp_prog *prog);
 bool nfp_bpf_supported_opcode(u8 code);
 
@@ -531,7 +533,7 @@ int nfp_net_bpf_offload(struct nfp_net *nn, struct bpf_prog *prog,
 
 struct nfp_insn_meta *
 nfp_bpf_goto_meta(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
-		  unsigned int insn_idx, unsigned int n_insns);
+		  unsigned int insn_idx);
 
 void *nfp_bpf_relo_for_vnic(struct nfp_prog *nfp_prog, struct nfp_bpf_vnic *bv);
 
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
index f0283854fade..c10aab392cf6 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
@@ -163,8 +163,9 @@ nfp_prog_prepare(struct nfp_prog *nfp_prog, const struct bpf_insn *prog,
 
 		list_add_tail(&meta->l, &nfp_prog->insns);
 	}
+	nfp_prog->n_insns = cnt;
 
-	nfp_bpf_jit_prepare(nfp_prog, cnt);
+	nfp_bpf_jit_prepare(nfp_prog);
 
 	return 0;
 }
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
index 337bb862ec1d..2712ab17d57c 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
@@ -18,15 +18,15 @@
 
 struct nfp_insn_meta *
 nfp_bpf_goto_meta(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
-		  unsigned int insn_idx, unsigned int n_insns)
+		  unsigned int insn_idx)
 {
 	unsigned int forward, backward, i;
 
 	backward = meta->n - insn_idx;
 	forward = insn_idx - meta->n;
 
-	if (min(forward, backward) > n_insns - insn_idx - 1) {
-		backward = n_insns - insn_idx - 1;
+	if (min(forward, backward) > nfp_prog->n_insns - insn_idx - 1) {
+		backward = nfp_prog->n_insns - insn_idx - 1;
 		meta = nfp_prog_last_meta(nfp_prog);
 	}
 	if (min(forward, backward) > insn_idx && backward > insn_idx) {
@@ -629,7 +629,7 @@ int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx,
 	struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
 	struct nfp_insn_meta *meta = nfp_prog->verifier_meta;
 
-	meta = nfp_bpf_goto_meta(nfp_prog, meta, insn_idx, env->prog->len);
+	meta = nfp_bpf_goto_meta(nfp_prog, meta, insn_idx);
 	nfp_prog->verifier_meta = meta;
 
 	if (!nfp_bpf_supported_opcode(meta->insn.code)) {
@@ -690,8 +690,7 @@ nfp_assign_subprog_idx_and_regs(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static unsigned int
-nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog, unsigned int cnt)
+static unsigned int nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog)
 {
 	struct nfp_insn_meta *meta = nfp_prog_first_meta(nfp_prog);
 	unsigned int max_depth = 0, depth = 0, frame = 0;
@@ -726,7 +725,7 @@ nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog, unsigned int cnt)
 
 		/* Find the callee and start processing it. */
 		meta = nfp_bpf_goto_meta(nfp_prog, meta,
-					 meta->n + 1 + meta->insn.imm, cnt);
+					 meta->n + 1 + meta->insn.imm);
 		idx = meta->subprog_idx;
 		frame++;
 		goto process_subprog;
@@ -778,8 +777,7 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env)
 
 	nn = netdev_priv(env->prog->aux->offload->netdev);
 	max_stack = nn_readb(nn, NFP_NET_CFG_BPF_STACK_SZ) * 64;
-	nfp_prog->stack_size = nfp_bpf_get_stack_usage(nfp_prog,
-						       env->prog->len);
+	nfp_prog->stack_size = nfp_bpf_get_stack_usage(nfp_prog);
 	if (nfp_prog->stack_size > max_stack) {
 		pr_vlog(env, "stack too large: program %dB > FW stack %dB\n",
 			nfp_prog->stack_size, max_stack);
-- 
2.19.2

[PATCH bpf-next 18/19] nfp: bpf: support optimizing dead branches

[Jakub Kicinski]

Verifier will now optimize out branches to dead code, implement
the replace_insn callback to take advantage of that optimization.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/main.h | 14 +++++++++++
 .../net/ethernet/netronome/nfp/bpf/offload.c  |  1 +
 .../net/ethernet/netronome/nfp/bpf/verifier.c | 24 +++++++++++++++++++
 3 files changed, 39 insertions(+)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h
index 07879eee3d46..a33aa7df1979 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/main.h
+++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h
@@ -412,6 +412,17 @@ static inline bool is_mbpf_div(const struct nfp_insn_meta *meta)
 	return is_mbpf_alu(meta) && mbpf_op(meta) == BPF_DIV;
 }
 
+static inline bool is_mbpf_cond_jump(const struct nfp_insn_meta *meta)
+{
+	u8 op;
+
+	if (BPF_CLASS(meta->insn.code) != BPF_JMP)
+		return false;
+
+	op = BPF_OP(meta->insn.code);
+	return op != BPF_JA && op != BPF_EXIT && op != BPF_CALL;
+}
+
 static inline bool is_mbpf_helper_call(const struct nfp_insn_meta *meta)
 {
 	struct bpf_insn insn = meta->insn;
@@ -520,6 +531,9 @@ int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx,
 		    int prev_insn_idx);
 int nfp_bpf_finalize(struct bpf_verifier_env *env);
 
+int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off,
+			     struct bpf_insn *insn);
+
 extern const struct bpf_prog_offload_ops nfp_bpf_dev_ops;
 
 struct netdev_bpf;
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
index c10aab392cf6..877c1b8f95e2 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
@@ -592,6 +592,7 @@ int nfp_net_bpf_offload(struct nfp_net *nn, struct bpf_prog *prog,
 const struct bpf_prog_offload_ops nfp_bpf_dev_ops = {
 	.insn_hook	= nfp_verify_insn,
 	.finalize	= nfp_bpf_finalize,
+	.replace_insn	= nfp_bpf_opt_replace_insn,
 	.prepare	= nfp_bpf_verifier_prep,
 	.translate	= nfp_bpf_translate,
 	.destroy	= nfp_bpf_destroy,
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
index 2712ab17d57c..02a4d1050a89 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
@@ -786,3 +786,27 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env)
 
 	return 0;
 }
+
+int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off,
+			     struct bpf_insn *insn)
+{
+	struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
+	struct nfp_insn_meta *meta = nfp_prog->verifier_meta;
+
+	meta = nfp_bpf_goto_meta(nfp_prog, meta, off);
+	nfp_prog->verifier_meta = meta;
+
+	/* conditional jump to jump conversion */
+	if (is_mbpf_cond_jump(meta) &&
+	    insn->code == (BPF_JMP | BPF_JA | BPF_K)) {
+		if (!insn->off) {
+			meta->jmp_dst = list_next_entry(meta, l);
+			meta->jump_neg_op = false;
+		}
+		return 0;
+	}
+
+	pr_vlog(env, "unsupported instruction replacement %hhx -> %hhx\n",
+		meta->insn.code, insn->code);
+	return -EINVAL;
+}
-- 
2.19.2

[PATCH bpf-next 19/19] nfp: bpf: support removing dead code

[Jakub Kicinski]

Add a verifier callback to the nfp JIT to remove the instructions
the verifier deemed to be dead.

Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Reviewed-by: Quentin Monnet <quentin.monnet@netronome.com>
---
 drivers/net/ethernet/netronome/nfp/bpf/main.h |  6 ++++-
 .../net/ethernet/netronome/nfp/bpf/offload.c  |  1 +
 .../net/ethernet/netronome/nfp/bpf/verifier.c | 23 +++++++++++++++++++
 3 files changed, 29 insertions(+), 1 deletion(-)

diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h
index a33aa7df1979..5813c3e13ebe 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/main.h
+++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h
@@ -247,9 +247,12 @@ struct nfp_bpf_reg_state {
 #define FLAG_INSN_SKIP_NOOP			BIT(3)
 /* Instruction is optimized out based on preceding instructions */
 #define FLAG_INSN_SKIP_PREC_DEPENDENT		BIT(4)
+/* Instruction is optimized by the verifier */
+#define FLAG_INSN_SKIP_VERIFIER_OPT		BIT(5)
 
 #define FLAG_INSN_SKIP_MASK		(FLAG_INSN_SKIP_NOOP | \
-					 FLAG_INSN_SKIP_PREC_DEPENDENT)
+					 FLAG_INSN_SKIP_PREC_DEPENDENT | \
+					 FLAG_INSN_SKIP_VERIFIER_OPT)
 
 /**
  * struct nfp_insn_meta - BPF instruction wrapper
@@ -533,6 +536,7 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env);
 
 int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off,
 			     struct bpf_insn *insn);
+int nfp_bpf_opt_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt);
 
 extern const struct bpf_prog_offload_ops nfp_bpf_dev_ops;
 
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
index 877c1b8f95e2..1bf37b2c7eef 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c
@@ -593,6 +593,7 @@ const struct bpf_prog_offload_ops nfp_bpf_dev_ops = {
 	.insn_hook	= nfp_verify_insn,
 	.finalize	= nfp_bpf_finalize,
 	.replace_insn	= nfp_bpf_opt_replace_insn,
+	.remove_insns	= nfp_bpf_opt_remove_insns,
 	.prepare	= nfp_bpf_verifier_prep,
 	.translate	= nfp_bpf_translate,
 	.destroy	= nfp_bpf_destroy,
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
index 02a4d1050a89..df584e035f9e 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
@@ -810,3 +810,26 @@ int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off,
 		meta->insn.code, insn->code);
 	return -EINVAL;
 }
+
+int nfp_bpf_opt_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
+{
+	struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
+	struct nfp_insn_meta *meta;
+	unsigned int i;
+
+	meta = nfp_bpf_goto_meta(nfp_prog, nfp_prog->verifier_meta, off);
+
+	for (i = 0; i < cnt; i++) {
+		if (WARN_ON_ONCE(&meta->l == &nfp_prog->insns))
+			return -EINVAL;
+
+		/* doesn't count if it already has the flag */
+		if (meta->flags & FLAG_INSN_SKIP_VERIFIER_OPT)
+			i--;
+
+		meta->flags |= FLAG_INSN_SKIP_VERIFIER_OPT;
+		meta = list_next_entry(meta, l);
+	}
+
+	return 0;
+}
-- 
2.19.2

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Alexei Starovoitov]

On Wed, Dec 19, 2018 at 10:29:18AM -0800, Jakub Kicinski wrote:
> Instead of overwriting dead code with jmp -1 instructions
> remove it completely for root.  Adjust verifier state and
> line info appropriately.
> 
> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> ---
>  include/linux/filter.h |   1 +
>  kernel/bpf/core.c      |  12 ++++
>  kernel/bpf/verifier.c  | 139 ++++++++++++++++++++++++++++++++++++++++-
>  3 files changed, 149 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 537e9e7c6e6f..c99969022493 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void)
>  
>  struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>  				       const struct bpf_insn *patch, u32 len);
> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
>  
>  void bpf_clear_redirect_map(struct bpf_map *map);
>  
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 2eb7cc9822bb..e3498d82eb74 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>  	return prog_adj;
>  }
>  
> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
> +{
> +	/* Branch offsets can't overflow when program is shrinking, no need
> +	 * to call bpf_adj_branches(..., true) here
> +	 */
> +	memmove(prog->insnsi + off, prog->insnsi + off + cnt,
> +		sizeof(struct bpf_insn) * (prog->len - off - cnt));
> +	prog->len -= cnt;
> +
> +	return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
> +}
> +
>  void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
>  {
>  	int i;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 7db2a48ea7f7..98a276f4c4e6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6226,6 +6226,113 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
>  	return new_prog;
>  }
>  
> +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
> +					      u32 off, u32 cnt)
> +{
> +	int i, j;
> +
> +	/* find first prog starting at or after off (first to remove) */
> +	for (i = 0; i < env->subprog_cnt; i++)
> +		if (env->subprog_info[i].start >= off)
> +			break;
> +	/* find first prog starting at or after off + cnt (first to stay) */
> +	for (j = i; j < env->subprog_cnt; j++)
> +		if (env->subprog_info[j].start >= off + cnt)
> +			break;
> +	/* if j doesn't start exactly at off + cnt, we are just removing
> +	 * the front of previous prog
> +	 */

I think this will break func_info, since it's not adjusted here.
Also iirc line_info is relying on first insn to always have line_info.
If first insn is dead, second insn might not have a line_info generated
and things won't go well.

Martin, Yonghong, please chime in.

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Yonghong Song]

On 12/19/18 4:45 PM, Alexei Starovoitov wrote:
> On Wed, Dec 19, 2018 at 10:29:18AM -0800, Jakub Kicinski wrote:
>> Instead of overwriting dead code with jmp -1 instructions
>> remove it completely for root.  Adjust verifier state and
>> line info appropriately.
>>
>> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
>> ---
>>   include/linux/filter.h |   1 +
>>   kernel/bpf/core.c      |  12 ++++
>>   kernel/bpf/verifier.c  | 139 ++++++++++++++++++++++++++++++++++++++++-
>>   3 files changed, 149 insertions(+), 3 deletions(-)
>>
>> diff --git a/include/linux/filter.h b/include/linux/filter.h
>> index 537e9e7c6e6f..c99969022493 100644
>> --- a/include/linux/filter.h
>> +++ b/include/linux/filter.h
>> @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void)
>>   
>>   struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>>   				       const struct bpf_insn *patch, u32 len);
>> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
>>   
>>   void bpf_clear_redirect_map(struct bpf_map *map);
>>   
>> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
>> index 2eb7cc9822bb..e3498d82eb74 100644
>> --- a/kernel/bpf/core.c
>> +++ b/kernel/bpf/core.c
>> @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>>   	return prog_adj;
>>   }
>>   
>> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
>> +{
>> +	/* Branch offsets can't overflow when program is shrinking, no need
>> +	 * to call bpf_adj_branches(..., true) here
>> +	 */
>> +	memmove(prog->insnsi + off, prog->insnsi + off + cnt,
>> +		sizeof(struct bpf_insn) * (prog->len - off - cnt));
>> +	prog->len -= cnt;
>> +
>> +	return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
>> +}
>> +
>>   void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
>>   {
>>   	int i;
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 7db2a48ea7f7..98a276f4c4e6 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -6226,6 +6226,113 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
>>   	return new_prog;
>>   }
>>   
>> +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
>> +					      u32 off, u32 cnt)
>> +{
>> +	int i, j;
>> +
>> +	/* find first prog starting at or after off (first to remove) */
>> +	for (i = 0; i < env->subprog_cnt; i++)
>> +		if (env->subprog_info[i].start >= off)
>> +			break;
>> +	/* find first prog starting at or after off + cnt (first to stay) */
>> +	for (j = i; j < env->subprog_cnt; j++)
>> +		if (env->subprog_info[j].start >= off + cnt)
>> +			break;
>> +	/* if j doesn't start exactly at off + cnt, we are just removing
>> +	 * the front of previous prog
>> +	 */
> 
> I think this will break func_info, since it's not adjusted here.
> Also iirc line_info is relying on first insn to always have line_info.
> If first insn is dead, second insn might not have a line_info generated
> and things won't go well.

Right, func_info needs to be adjusted as well. The first line_info for 
each func must have insn_off = 0. In case of dead code elimination from
the start, if the first remaining insn has a line_info, just use it.
Otherwise, you can use the old first line_info.


> 
> Martin, Yonghong, please chime in.
> 

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Jakub Kicinski]

On Thu, 20 Dec 2018 07:19:06 +0000, Yonghong Song wrote:
> > I think this will break func_info, since it's not adjusted here.
> > Also iirc line_info is relying on first insn to always have line_info.
> > If first insn is dead, second insn might not have a line_info generated
> > and things won't go well.  
> 
> Right, func_info needs to be adjusted as well. The first line_info for 
> each func must have insn_off = 0. In case of dead code elimination from
> the start, if the first remaining insn has a line_info, just use it.
> Otherwise, you can use the old first line_info.

I think I got it (see the incremental diff below).  I want to also
tackle the JIT linfo offsets for offloads while at it and post an RFC
(unless you're handling that already Martin?)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e2ba323e7a57..a75ba4beae2f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6254,13 +6254,26 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 		j--;
 
 	if (j > i) {
+		struct bpf_prog_aux *aux = env->prog->aux;
+		int move;
+
 		/* move fake 'exit' subprog as well */
-		int move = env->subprog_cnt + 1 - j;
+		move = env->subprog_cnt + 1 - j;
 
 		memmove(env->subprog_info + i,
 			env->subprog_info + j,
 			sizeof(*env->subprog_info) * move);
 		env->subprog_cnt -= j - i;
+
+		/* remove func_info */
+		if (aux->func_info) {
+			move = aux->func_info_cnt - j;
+
+			memmove(aux->func_info + i,
+				aux->func_info + j,
+				sizeof(*aux->func_info) * move);
+			aux->func_info_cnt -= j - i;
+		}
 	}
 
 	/* convert i from "first prog to remove" to "first to adjust" */
@@ -6274,23 +6287,37 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static void bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
-				       u32 cnt)
+static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
+				      u32 cnt)
 {
+	struct bpf_subprog_info *need_first_linfo;
 	struct bpf_prog *prog = env->prog;
 	u32 i, l_off, l_cnt, nr_linfo;
 	struct bpf_line_info *linfo;
 
 	nr_linfo = prog->aux->nr_linfo;
 	if (!nr_linfo || !cnt)
-		return;
+		return 0;
 
 	linfo = prog->aux->linfo;
 
+	/* progs are already adjusted, if any program starts on off, it may had
+	 * its start cut off and its line info may need to be preserved
+	 */
+	for (i = 0; i < env->subprog_cnt; i++)
+		if (env->subprog_info[i].start >= off)
+			break;
+	if (i < env->subprog_cnt && env->subprog_info[i].start == off)
+		need_first_linfo = &env->subprog_info[i];
+	else
+		need_first_linfo = NULL;
+
+	/* find first line info to remove */
 	for (i = 0; i < nr_linfo; i++)
 		if (linfo[i].insn_off >= off)
 			break;
 
+	/* count lines to be removed */
 	l_off = i;
 	l_cnt = 0;
 	for (; i < nr_linfo; i++)
@@ -6299,7 +6326,32 @@ static void bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
 		else
 			break;
 
-	/* Remove the line info which refers to the removed instructions */
+	/* either we didn't actually cut the start of we can just use line info
+	 * of first instruction if it exists
+	 */
+	if (i < nr_linfo && linfo[i].insn_off == off + cnt)
+		need_first_linfo = NULL;
+	if (need_first_linfo) {
+		if (WARN_ONCE(!l_cnt,
+			      "verifier bug - no linfo removed, yet its missing"))
+			return -EINVAL;
+		if (WARN_ONCE(need_first_linfo->linfo_idx < l_off ||
+			      need_first_linfo->linfo_idx >= l_off + l_cnt,
+			      "verifier bug - removed prog linfo not in removed range"))
+			return -EINVAL;
+		/* subprog linfo_idx is not adjusted yet, so just find out
+		 * which line it used to be and swap it
+		 */
+		memmove(linfo + l_off, linfo + need_first_linfo->linfo_idx,
+			sizeof(*linfo));
+		need_first_linfo->linfo_idx = l_off;
+		linfo[l_off].insn_off = off;
+
+		l_off++;
+		l_cnt--;
+	}
+
+	/* remove the line info which refers to the removed instructions */
 	if (l_cnt) {
 		memmove(linfo + l_off, linfo + i,
 			sizeof(*linfo) * (nr_linfo - i));
@@ -6308,16 +6360,17 @@ static void bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
 		nr_linfo = prog->aux->nr_linfo;
 	}
 
-	/* Pull all linfo[i].insn_off >= off + cnt in by cnt */
+	/* pull all linfo[i].insn_off >= off + cnt in by cnt */
 	for (i = l_off; i < nr_linfo; i++)
 		linfo[i].insn_off -= cnt;
 
-	/* Fix up all subprogs (incl. 'exit') which start >= off */
-	for (i = 0; i <= env->subprog_cnt; i++)
-		if (env->subprog_info[i].linfo_idx > l_off + l_cnt)
+	/* fix up all subprogs (incl. 'exit') which start >= off */
+	for (i = 0; i <= env->subprog_cnt; i++) {
+		if (env->subprog_info[i].linfo_idx >= l_off + l_cnt)
 			env->subprog_info[i].linfo_idx -= l_cnt;
-		else if (env->subprog_info[i].linfo_idx > l_off)
-			env->subprog_info[i].linfo_idx = l_off;
+	}
+
+	return 0;
 }
 
 static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
@@ -6333,12 +6386,18 @@ static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 	if (err)
 		return err;
 
-	bpf_adj_linfo_after_remove(env, off, cnt);
+	err = adjust_subprog_starts_after_remove(env, off, cnt);
+	if (err)
+		return err;
+
+	err = bpf_adj_linfo_after_remove(env, off, cnt);
+	if (err)
+		return err;
 
 	memmove(aux_data + off,	aux_data + off + cnt,
 		sizeof(*aux_data) * (orig_prog_len - off - cnt));
 
-	return adjust_subprog_starts_after_remove(env, off, cnt);
+	return 0;
 }
 
 /* The verifier does more data flow analysis than llvm and will not
-- 
2.19.2

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Martin Lau]

On Fri, Dec 21, 2018 at 03:46:32PM -0800, Jakub Kicinski wrote:

> I want to also
> tackle the JIT linfo offsets for offloads while at it and post an RFC
> (unless you're handling that already Martin?)
No. I am not :)

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Alexei Starovoitov]

On Fri, Dec 21, 2018 at 03:46:32PM -0800, Jakub Kicinski wrote:
> On Thu, 20 Dec 2018 07:19:06 +0000, Yonghong Song wrote:
> > > I think this will break func_info, since it's not adjusted here.
> > > Also iirc line_info is relying on first insn to always have line_info.
> > > If first insn is dead, second insn might not have a line_info generated
> > > and things won't go well.  
> > 
> > Right, func_info needs to be adjusted as well. The first line_info for 
> > each func must have insn_off = 0. In case of dead code elimination from
> > the start, if the first remaining insn has a line_info, just use it.
> > Otherwise, you can use the old first line_info.
> 
> I think I got it (see the incremental diff below).  I want to also
> tackle the JIT linfo offsets for offloads while at it and post an RFC
> (unless you're handling that already Martin?)

that may work, but I think it's too much extra complexity for
artificial corner case.
The first insn of the program and subprog will be valid insn
otherwise check_cfg would have rejected the prog earlier.
The only way it can become 'dead' is if the user manually created
bpf prog with 'ja pc+0' as the first insn just to triger this dead
code optimization pass. In such case I think it's better to leave
that insn as-is instead going out of the way adjusting prog_info, line_info
and other things that may depend on the first insn in the future.

I'm having seconds thoughts regarding the whole idea of dead code elimination.
We are relying on user space to optimize BPF code. Due to this choice we
avoided adding optimization passes to the kernel (few optimizations that
we do in the verifier and JITs cannot be done by the user space).
The way 'dead code' is used now is kinda border line.
May be we should teach libbpf to do this instead?
I'm happy to be convinced that kernel really needs to do it,
but I want to see examples where libbpf approach cannot fit.

Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

[Jakub Kicinski]

On Fri, 21 Dec 2018 17:24:01 -0800, Alexei Starovoitov wrote:
> On Fri, Dec 21, 2018 at 03:46:32PM -0800, Jakub Kicinski wrote:
> > On Thu, 20 Dec 2018 07:19:06 +0000, Yonghong Song wrote:
> > > > I think this will break func_info, since it's not adjusted here.
> > > > Also iirc line_info is relying on first insn to always have line_info.
> > > > If first insn is dead, second insn might not have a line_info generated
> > > > and things won't go well.
> > >
> > > Right, func_info needs to be adjusted as well. The first line_info for
> > > each func must have insn_off = 0. In case of dead code elimination from
> > > the start, if the first remaining insn has a line_info, just use it.
> > > Otherwise, you can use the old first line_info.
> >
> > I think I got it (see the incremental diff below).  I want to also
> > tackle the JIT linfo offsets for offloads while at it and post an RFC
> > (unless you're handling that already Martin?)
>
> that may work, but I think it's too much extra complexity for
> artificial corner case.
> The first insn of the program and subprog will be valid insn
> otherwise check_cfg would have rejected the prog earlier.
> The only way it can become 'dead' is if the user manually created
> bpf prog with 'ja pc+0' as the first insn just to triger this dead
> code optimization pass. In such case I think it's better to leave
> that insn as-is instead going out of the way adjusting prog_info, line_info
> and other things that may depend on the first insn in the future.

I just use ja pc+0 because its simplest, but its possible that a
subprog will have a conditional jump based on an argument which is
always taken or not taken, and therefore can be removed.

> I'm having seconds thoughts regarding the whole idea of dead code elimination.
> We are relying on user space to optimize BPF code. Due to this choice we
> avoided adding optimization passes to the kernel (few optimizations that
> we do in the verifier and JITs cannot be done by the user space).
> The way 'dead code' is used now is kinda border line.
> May be we should teach libbpf to do this instead?
> I'm happy to be convinced that kernel really needs to do it,
> but I want to see examples where libbpf approach cannot fit.

I shouldn't have posted this incremental diff, it's quite messy, I
changed comments around and reshuffled things :(  I think the code ended
up reasonably clean and readable.

The case that prompted me to look at this was legit dead code, not
result of patching in constants.  Let me post the full set after
Christmas and perhaps you can judge the whole thing..

I quite like the ability to correct the line info and subprog info, for
code space constrained architectures removing code whenever possible is
really important.