[PATCH bpf-next 0/3] bpf: improve BPF_JSET test coverage and verifier handling

[PATCH bpf-next 0/3] bpf: improve BPF_JSET test coverage and verifier handling

[Jakub Kicinski]

Hi!

This small set is the first step to dead code elimination I'm working
on, but it stands on its own.  I want to make the verifier understand
JSET instruction better so we can remove some trivial dead code
optimizations from the nfp JIT.

First patch adds a functional test for JSET, because AFAICT LLVM does
not generate that instruction so JITs probably don't get well tested.
Second patch make the verifier understand JSET in the same way it
already understands all the other conditional jump instructions.
Last but not least the test cases for patch 2.

Jakub Kicinski (3):
  selftests: bpf: add trivial JSET test
  bpf: verifier: teach the verifier to reason about the BPF_JSET
    instruction
  selftests: bpf: verifier: add tests for JSET interpretation

 kernel/bpf/verifier.c                       | 20 +++++
 tools/testing/selftests/bpf/test_progs.c    | 69 +++++++++++++++
 tools/testing/selftests/bpf/test_verifier.c | 96 +++++++++++++++++++++
 3 files changed, 185 insertions(+)

-- 
2.17.1

[PATCH bpf-next 1/3] selftests: bpf: add trivial JSET test

[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.

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

diff --git a/tools/testing/selftests/bpf/test_progs.c b/tools/testing/selftests/bpf/test_progs.c
index 126fc624290d..d9b7197fdf94 100644
--- a/tools/testing/selftests/bpf/test_progs.c
+++ b/tools/testing/selftests/bpf/test_progs.c
@@ -1882,6 +1882,76 @@ static void test_queue_stack_map(int type)
 	bpf_object__close(obj);
 }
 
+static void test_jset(void)
+{
+	/* LLVM does not seem to support JSET-like instructions so by hand.. */
+	static const struct bpf_insn 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(),
+	};
+	__u32 duration = 0, retval;
+	__u64 data[8] = {};
+	int err, prog_fd;
+
+	prog_fd = bpf_load_program(BPF_PROG_TYPE_SCHED_CLS, insns,
+				   ARRAY_SIZE(insns), "GPL", 0, NULL, 0);
+	if (CHECK(prog_fd < 0, "jset", "load fd %d errno %d\n", prog_fd, errno))
+		return;
+
+#define TEST(val, name, res)						\
+	do {								\
+		data[0] = (val);					\
+		err = bpf_prog_test_run(prog_fd, 1, data, sizeof(data),	\
+					NULL, NULL, &retval, &duration); \
+		CHECK(err || retval != (res), (name),			\
+		      "err %d errno %d retval %d duration %d\n",	\
+		      err, errno, retval, duration);			\
+	} while (0)
+
+	TEST((1ULL << 63) | (1U << 31) | (1U << 0), "bit63+31+0", 2);
+	TEST((1ULL << 63) | (1U << 31), "bit63+31", 2);
+	TEST((1ULL << 31) | (1U << 0), "bit31+0", 2);
+	TEST((__u32)-1, "u32", 2);
+	TEST(~0x4000000000000000ULL, "~bit62", 2);
+	TEST(0, "zero", 0);
+	TEST(~0ULL, "all", 0);
+#undef TEST
+}
+
 int main(void)
 {
 	srand(time(NULL));
@@ -1909,6 +1979,7 @@ int main(void)
 	test_reference_tracking();
 	test_queue_stack_map(QUEUE);
 	test_queue_stack_map(STACK);
+	test_jset();
 
 	printf("Summary: %d PASSED, %d FAILED\n", pass_cnt, error_cnt);
 	return error_cnt ? EXIT_FAILURE : EXIT_SUCCESS;
-- 
2.17.1

[PATCH bpf-next 2/3] 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>
---
 kernel/bpf/verifier.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8b511a4fe84a..50bb45aa4f26 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3788,6 +3788,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;
@@ -3872,6 +3878,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);
@@ -3944,6 +3957,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.17.1

[PATCH bpf-next 3/3] 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 a08c67c8767e..69f4415f0169 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -14099,6 +14099,102 @@ static struct bpf_test tests[] = {
 		.errstr_unpriv = "R1 leaks addr",
 		.result = REJECT,
 	},
+	{
+		"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.17.1

Re: [PATCH bpf-next 1/3] selftests: bpf: add trivial JSET test

[Daniel Borkmann]

On 12/13/2018 04:41 AM, Jakub Kicinski wrote:
> 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.
> 
> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> ---
>  tools/testing/selftests/bpf/test_progs.c | 71 ++++++++++++++++++++++++
>  1 file changed, 71 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/test_progs.c b/tools/testing/selftests/bpf/test_progs.c
> index 126fc624290d..d9b7197fdf94 100644
> --- a/tools/testing/selftests/bpf/test_progs.c
> +++ b/tools/testing/selftests/bpf/test_progs.c
> @@ -1882,6 +1882,76 @@ static void test_queue_stack_map(int type)
>  	bpf_object__close(obj);
>  }
>  
> +static void test_jset(void)
> +{
> +	/* LLVM does not seem to support JSET-like instructions so by hand.. */
> +	static const struct bpf_insn 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(),
> +	};
> +	__u32 duration = 0, retval;
> +	__u64 data[8] = {};
> +	int err, prog_fd;
> +
> +	prog_fd = bpf_load_program(BPF_PROG_TYPE_SCHED_CLS, insns,
> +				   ARRAY_SIZE(insns), "GPL", 0, NULL, 0);
> +	if (CHECK(prog_fd < 0, "jset", "load fd %d errno %d\n", prog_fd, errno))
> +		return;
> +
> +#define TEST(val, name, res)						\
> +	do {								\
> +		data[0] = (val);					\
> +		err = bpf_prog_test_run(prog_fd, 1, data, sizeof(data),	\
> +					NULL, NULL, &retval, &duration); \
> +		CHECK(err || retval != (res), (name),			\
> +		      "err %d errno %d retval %d duration %d\n",	\
> +		      err, errno, retval, duration);			\
> +	} while (0)
> +
> +	TEST((1ULL << 63) | (1U << 31) | (1U << 0), "bit63+31+0", 2);
> +	TEST((1ULL << 63) | (1U << 31), "bit63+31", 2);
> +	TEST((1ULL << 31) | (1U << 0), "bit31+0", 2);
> +	TEST((__u32)-1, "u32", 2);
> +	TEST(~0x4000000000000000ULL, "~bit62", 2);
> +	TEST(0, "zero", 0);
> +	TEST(~0ULL, "all", 0);
> +#undef TEST

Could we rather extend the test_verifier infrastructure in order to be able to
define data input for bpf_prog_test_run()? I think this would be very useful
for future tests there as well and avoid having to duplicate or split functionality
into test_progs.c instead.

> +}
> +
>  int main(void)
>  {
>  	srand(time(NULL));
> @@ -1909,6 +1979,7 @@ int main(void)
>  	test_reference_tracking();
>  	test_queue_stack_map(QUEUE);
>  	test_queue_stack_map(STACK);
> +	test_jset();
>  
>  	printf("Summary: %d PASSED, %d FAILED\n", pass_cnt, error_cnt);
>  	return error_cnt ? EXIT_FAILURE : EXIT_SUCCESS;

Thanks,
Daniel

Re: [PATCH bpf-next 2/3] bpf: verifier: teach the verifier to reason about the BPF_JSET instruction

[Edward Cree]

On 13/12/18 03:41, Jakub Kicinski wrote:
> 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 8b511a4fe84a..50bb45aa4f26 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3788,6 +3788,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;
> @@ -3872,6 +3878,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);
> @@ -3944,6 +3957,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);

Re: [PATCH bpf-next 1/3] selftests: bpf: add trivial JSET test

[Jakub Kicinski]

On Thu, 13 Dec 2018 16:17:37 +0100, Daniel Borkmann wrote:
> Could we rather extend the test_verifier infrastructure in order to
> be able to define data input for bpf_prog_test_run()? I think this
> would be very useful for future tests there as well and avoid having
> to duplicate or split functionality into test_progs.c instead.

No strong feelings but if it's called test_verifier, and the sample puts
no stress on the verifier it feels weird to put it there..  But okay, I
will respin.. at some point :)

Re: [PATCH bpf-next 1/3] selftests: bpf: add trivial JSET test

[Daniel Borkmann]

On 12/13/2018 07:52 PM, Jakub Kicinski wrote:
> On Thu, 13 Dec 2018 16:17:37 +0100, Daniel Borkmann wrote:
>> Could we rather extend the test_verifier infrastructure in order to
>> be able to define data input for bpf_prog_test_run()? I think this
>> would be very useful for future tests there as well and avoid having
>> to duplicate or split functionality into test_progs.c instead.
> 
> No strong feelings but if it's called test_verifier, and the sample puts
> no stress on the verifier it feels weird to put it there..  But okay, I
> will respin.. at some point :)

Well, test_verifier is running every program that passes the verifier
via bpf_prog_test_run() anyway to increase test coverage also for JIT
and runtime rather than just plain verification itself. In that sense
it includes testing what verifier has been rewritten, for example. I
just noticed we already have this feature via 93731ef086ce ("bpf:
migrate ebpf ld_abs/ld_ind tests to test_verifier"). ;-) So just adding
the test code there should suffice.