[PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons

[PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Hi Everyone,

This patchset adds ability to propagates nullness information for
branches of register to register equality compare instructions. The
following rules are used:
- suppose register A maybe null
- suppose register B is not null
- for JNE A, B, ... - A is not null in the false branch
- for JEQ A, B, ... - A is not null in the true branch

E.g. for program like below:

  r6 = skb->sk;
  r7 = sk_fullsock(r6);
  r0 = sk_fullsock(r6);
  if (r0 == 0) return 0;    (a)
  if (r0 != r7) return 0;   (b)
  *r7->type;                (c)
  return 0;

It is safe to dereference r7 at point (c), because of (a) and (b).

The utility of this change came up while working on BPF CLang backend
issue [1]. Specifically, while debugging issue with selftest
`test_sk_lookup.c`. This test has the following structure:

    int access_ctx_sk(struct bpf_sk_lookup *ctx __CTX__)
    {
        struct bpf_sock *sk1 = NULL, *sk2 = NULL;
        ...
        sk1 = bpf_map_lookup_elem(&redir_map, &KEY_SERVER_A);
        if (!sk1)           // (a)
            goto out;
        ...
        if (ctx->sk != sk1) // (b)
            goto out;
        ...
        if (ctx->sk->family != AF_INET ||     // (c)
            ctx->sk->type != SOCK_STREAM ||
            ctx->sk->state != BPF_TCP_LISTEN)
            goto out;
            ...
    }

- at (a) `sk1` is checked to be not null;
- at (b) `ctx->sk` is verified to be equal to `sk1`;
- at (c) `ctx->sk` is accessed w/o nullness check.

Currently Global Value Numbering pass considers expressions `sk1` and
`ctx->sk` to be identical at point (c) and replaces `ctx->sk` with
`sk1` (not expressions themselves but corresponding SSA values).
Since `sk1` is known to be not null after (b) verifier allows
execution of the program.

However, such optimization is not guaranteed to happen. When it does
not happen verifier reports an error.

[1] https://reviews.llvm.org/D131633#3722231

Thanks,
Eduard

Eduard Zingerman (2):
  bpf: propagate nullness information for reg to reg comparisons
  selftests/bpf: check nullness propagation for reg to reg comparisons

 kernel/bpf/verifier.c                         |  39 +++-
 .../bpf/verifier/jeq_infer_not_null.c         | 186 ++++++++++++++++++
 2 files changed, 224 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
-- 
2.37.1

[PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Propagate nullness information for branches of register to register
equality compare instructions. The following rules are used:
- suppose register A maybe null
- suppose register B is not null
- for JNE A, B, ... - A is not null in the false branch
- for JEQ A, B, ... - A is not null in the true branch

E.g. for program like below:

  r6 = skb->sk;
  r7 = sk_fullsock(r6);
  r0 = sk_fullsock(r6);
  if (r0 == 0) return 0;    (a)
  if (r0 != r7) return 0;   (b)
  *r7->type;                (c)
  return 0;

It is safe to dereference r7 at point (c), because of (a) and (b).

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2c1f8069f7b7..c48d34625bfd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
 	return type & PTR_MAYBE_NULL;
 }
 
+static bool type_is_pointer(enum bpf_reg_type type)
+{
+	return type != NOT_INIT && type != SCALAR_VALUE;
+}
+
 static bool is_acquire_function(enum bpf_func_id func_id,
 				const struct bpf_map *map)
 {
@@ -10046,6 +10051,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	struct bpf_verifier_state *other_branch;
 	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
 	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
+	struct bpf_reg_state *eq_branch_regs;
 	u8 opcode = BPF_OP(insn->code);
 	bool is_jmp32;
 	int pred = -1;
@@ -10155,7 +10161,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	/* detect if we are comparing against a constant value so we can adjust
 	 * our min/max values for our dst register.
 	 * this is only legit if both are scalars (or pointers to the same
-	 * object, I suppose, but we don't support that right now), because
+	 * object, I suppose, see the next if block), because
 	 * otherwise the different base pointers mean the offsets aren't
 	 * comparable.
 	 */
@@ -10199,6 +10205,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 					opcode, is_jmp32);
 	}
 
+	/* if one pointer register is compared to another pointer
+	 * register check if PTR_MAYBE_NULL could be lifted.
+	 * E.g. register A - maybe null
+	 *      register B - not null
+	 * for JNE A, B, ... - A is not null in the false branch;
+	 * for JEQ A, B, ... - A is not null in the true branch.
+	 */
+	if (!is_jmp32 &&
+	    BPF_SRC(insn->code) == BPF_X &&
+	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
+	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
+		eq_branch_regs = NULL;
+		switch (opcode) {
+		case BPF_JEQ:
+			eq_branch_regs = other_branch_regs;
+			break;
+		case BPF_JNE:
+			eq_branch_regs = regs;
+			break;
+		default:
+			/* do nothing */
+			break;
+		}
+		if (eq_branch_regs) {
+			if (type_may_be_null(src_reg->type))
+				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
+			else
+				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
+		}
+	}
+
 	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
 	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
 		find_equal_scalars(this_branch, dst_reg);
-- 
2.37.1

[PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Eduard Zingerman]

Verify that nullness information is porpagated in the branches of
register to register JEQ and JNE operations.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/verifier/jeq_infer_not_null.c         | 186 ++++++++++++++++++
 1 file changed, 186 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
new file mode 100644
index 000000000000..1af9fdd31f00
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
@@ -0,0 +1,186 @@
+{
+	/* This is equivalent to the following program:
+	 *
+	 *   r6 = skb->sk;
+	 *   r7 = sk_fullsock(r6);
+	 *   r0 = sk_fullsock(r6);
+	 *   if (r0 == 0) return 0;    (a)
+	 *   if (r0 != r7) return 0;   (b)
+	 *   *r7->type;                (c)
+	 *   return 0;
+	 *
+	 * It is safe to dereference r7 at point (c), because of (a) and (b).
+	 * The test verifies that relation r0 == r7 is propagated from (b) to (c).
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* if (r0 == r7) r0 = *(r7->type); */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_0, BPF_REG_7, 1), /* Use ! JNE ! */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = ACCEPT,
+},
+{
+	/* Same as above, but verify that another branch of JNE still
+	 * prohibits access to PTR_MAYBE_NULL.
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL unchanged for JNE true branch",
+	.insns = {
+	/* r6 = skb->sk */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* if (r0 == r7) return 0; */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_0, BPF_REG_7, 2), /* Use ! JNE ! */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r0 = *(r7->type); */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = REJECT,
+	.errstr = "R7 invalid mem access 'sock_or_null'",
+},
+{
+	/* Same as a first test, but not null should be inferred for JEQ branch */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JEQ true branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* if (r0 != r7) return 0; */
+	BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_7, 2), /* Use ! JEQ ! */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r0 = *(r7->type); */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = ACCEPT,
+},
+{
+	/* Same as above, but verify that another branch of JNE still
+	 * prohibits access to PTR_MAYBE_NULL.
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL unchanged for JEQ false branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* if (r0 != r7) r0 = *(r7->type); */
+	BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_7, 1), /* Use ! JEQ ! */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = REJECT,
+	.errstr = "R7 invalid mem access 'sock_or_null'",
+},
+{
+	/* Maps are treated in a different branch of `mark_ptr_not_null_reg`,
+	 * so separate test for maps case.
+	 */
+	"jne/jeq infer not null, PTR_TO_MAP_VALUE_OR_NULL -> PTR_TO_MAP_VALUE",
+	.insns = {
+	/* r9 = &some stack to use as key */
+	BPF_ST_MEM(BPF_W, BPF_REG_10, -8, 0),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_9, -8),
+	/* r8 = process local map */
+	BPF_LD_MAP_FD(BPF_REG_8, 0),
+	/* r6 = map_lookup_elem(r8, r9); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_9),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	/* r7 = map_lookup_elem(r8, r9); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_9),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* if (r6 != r7) return 0; */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_6, BPF_REG_7, 1),
+	/* read *r7; */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_xdp_sock, queue_id)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_xskmap = { 3 },
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.result = ACCEPT,
+},
-- 
2.37.1

RE: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[John Fastabend]

Eduard Zingerman wrote:
> Propagate nullness information for branches of register to register
> equality compare instructions. The following rules are used:
> - suppose register A maybe null
> - suppose register B is not null
> - for JNE A, B, ... - A is not null in the false branch
> - for JEQ A, B, ... - A is not null in the true branch
> 
> E.g. for program like below:
> 
>   r6 = skb->sk;
>   r7 = sk_fullsock(r6);
>   r0 = sk_fullsock(r6);
>   if (r0 == 0) return 0;    (a)
>   if (r0 != r7) return 0;   (b)
>   *r7->type;                (c)
>   return 0;
> 
> It is safe to dereference r7 at point (c), because of (a) and (b).

I think the idea makes sense. Perhaps Yonhong can comment seeing he was active
on the LLVM thread. I just scanned the LLVM side for now will take a look
in more detail in a bit.

> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 38 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2c1f8069f7b7..c48d34625bfd 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
>  	return type & PTR_MAYBE_NULL;
>  }
>  
> +static bool type_is_pointer(enum bpf_reg_type type)
> +{
> +	return type != NOT_INIT && type != SCALAR_VALUE;
> +}
> +

Instead of having another helper is_pointer_value() could work here?
Checking if we need NOT_INIT in that helper now.

>  static bool is_acquire_function(enum bpf_func_id func_id,
>  				const struct bpf_map *map)
>  {
> @@ -10046,6 +10051,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>  	struct bpf_verifier_state *other_branch;
>  	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
>  	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
> +	struct bpf_reg_state *eq_branch_regs;
>  	u8 opcode = BPF_OP(insn->code);
>  	bool is_jmp32;
>  	int pred = -1;
> @@ -10155,7 +10161,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>  	/* detect if we are comparing against a constant value so we can adjust
>  	 * our min/max values for our dst register.
>  	 * this is only legit if both are scalars (or pointers to the same
> -	 * object, I suppose, but we don't support that right now), because
> +	 * object, I suppose, see the next if block), because
>  	 * otherwise the different base pointers mean the offsets aren't
>  	 * comparable.
>  	 */
> @@ -10199,6 +10205,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>  					opcode, is_jmp32);
>  	}
>  
> +	/* if one pointer register is compared to another pointer
> +	 * register check if PTR_MAYBE_NULL could be lifted.
> +	 * E.g. register A - maybe null
> +	 *      register B - not null
> +	 * for JNE A, B, ... - A is not null in the false branch;
> +	 * for JEQ A, B, ... - A is not null in the true branch.
> +	 */
> +	if (!is_jmp32 &&
> +	    BPF_SRC(insn->code) == BPF_X &&
> +	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
> +	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
> +		eq_branch_regs = NULL;
> +		switch (opcode) {
> +		case BPF_JEQ:
> +			eq_branch_regs = other_branch_regs;
> +			break;
> +		case BPF_JNE:
> +			eq_branch_regs = regs;
> +			break;
> +		default:
> +			/* do nothing */
> +			break;
> +		}
> +		if (eq_branch_regs) {
> +			if (type_may_be_null(src_reg->type))
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
> +			else
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
> +		}
> +	}
> +
>  	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
>  	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
>  		find_equal_scalars(this_branch, dst_reg);
> -- 
> 2.37.1
> 

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

> On Tue, 2022-08-23 at 16:15 -0700, John Fastabend wrote:

Hi John,

Thank you for commenting!

> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 2c1f8069f7b7..c48d34625bfd 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> >  	return type & PTR_MAYBE_NULL;
> >  }
> >  
> > +static bool type_is_pointer(enum bpf_reg_type type)
> > +{
> > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > +}
> > +
> 
> Instead of having another helper is_pointer_value() could work here?
> Checking if we need NOT_INIT in that helper now.

Do you mean modifying the `__is_pointer_value` by adding a check
`reg->type != NOT_INIT`?

I tried this out and tests are passing, but __is_pointer_value /
is_pointer_value are used in a lot of places, seem to be a scary
change, to be honest.

Thanks,
Eduard

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Yonghong Song]

On 8/22/22 2:43 AM, Eduard Zingerman wrote:
> Propagate nullness information for branches of register to register
> equality compare instructions. The following rules are used:
> - suppose register A maybe null
> - suppose register B is not null
> - for JNE A, B, ... - A is not null in the false branch
> - for JEQ A, B, ... - A is not null in the true branch
> 
> E.g. for program like below:
> 
>    r6 = skb->sk;
>    r7 = sk_fullsock(r6);
>    r0 = sk_fullsock(r6);
>    if (r0 == 0) return 0;    (a)
>    if (r0 != r7) return 0;   (b)
>    *r7->type;                (c)
>    return 0;
> 
> It is safe to dereference r7 at point (c), because of (a) and (b).
> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

You can remove RFC tag in the next revision.

LGTM with one nit below.

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>   kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>   1 file changed, 38 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2c1f8069f7b7..c48d34625bfd 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
>   	return type & PTR_MAYBE_NULL;
>   }
>   
> +static bool type_is_pointer(enum bpf_reg_type type)
> +{
> +	return type != NOT_INIT && type != SCALAR_VALUE;
> +}
> +
>   static bool is_acquire_function(enum bpf_func_id func_id,
>   				const struct bpf_map *map)
>   {
> @@ -10046,6 +10051,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   	struct bpf_verifier_state *other_branch;
>   	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
>   	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
> +	struct bpf_reg_state *eq_branch_regs;
>   	u8 opcode = BPF_OP(insn->code);
>   	bool is_jmp32;
>   	int pred = -1;
> @@ -10155,7 +10161,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   	/* detect if we are comparing against a constant value so we can adjust
>   	 * our min/max values for our dst register.
>   	 * this is only legit if both are scalars (or pointers to the same
> -	 * object, I suppose, but we don't support that right now), because
> +	 * object, I suppose, see the next if block), because
>   	 * otherwise the different base pointers mean the offsets aren't
>   	 * comparable.
>   	 */
> @@ -10199,6 +10205,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   					opcode, is_jmp32);
>   	}
>   
> +	/* if one pointer register is compared to another pointer
> +	 * register check if PTR_MAYBE_NULL could be lifted.
> +	 * E.g. register A - maybe null
> +	 *      register B - not null
> +	 * for JNE A, B, ... - A is not null in the false branch;
> +	 * for JEQ A, B, ... - A is not null in the true branch.
> +	 */
> +	if (!is_jmp32 &&
> +	    BPF_SRC(insn->code) == BPF_X &&
> +	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
> +	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
> +		eq_branch_regs = NULL;
> +		switch (opcode) {
> +		case BPF_JEQ:
> +			eq_branch_regs = other_branch_regs;
> +			break;
> +		case BPF_JNE:
> +			eq_branch_regs = regs;
> +			break;
> +		default:
> +			/* do nothing */
> +			break;
> +		}
> +		if (eq_branch_regs) {
> +			if (type_may_be_null(src_reg->type))
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
> +			else
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
> +		}
> +	}

I suggest put the above code after below if condition so the new code 
can be closer to other codes with make_ptr_not_null_reg.

> +
>   	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
>   	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
>   		find_equal_scalars(this_branch, dst_reg);

Re: [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Yonghong Song]

On 8/22/22 2:43 AM, Eduard Zingerman wrote:
> Verify that nullness information is porpagated in the branches of
> register to register JEQ and JNE operations.
> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

LGTM with one nit below.

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>   .../bpf/verifier/jeq_infer_not_null.c         | 186 ++++++++++++++++++
>   1 file changed, 186 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> 
> diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> new file mode 100644
> index 000000000000..1af9fdd31f00
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> @@ -0,0 +1,186 @@
> +{
> +	/* This is equivalent to the following program:
> +	 *
> +	 *   r6 = skb->sk;
> +	 *   r7 = sk_fullsock(r6);
> +	 *   r0 = sk_fullsock(r6);
> +	 *   if (r0 == 0) return 0;    (a)
> +	 *   if (r0 != r7) return 0;   (b)
> +	 *   *r7->type;                (c)
> +	 *   return 0;
> +	 *
> +	 * It is safe to dereference r7 at point (c), because of (a) and (b).
> +	 * The test verifies that relation r0 == r7 is propagated from (b) to (c).
> +	 */
> +	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch",
> +	.insns = {
> +	/* r6 = skb->sk; */
> +	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
> +	/* if (r6 == 0) return 0; */
> +	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 2),
> +	BPF_MOV64_IMM(BPF_REG_0, 0),
> +	BPF_EXIT_INSN(),

In general, for each test case, we only have one
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_EXIT_INSN()
to simulate the C generated code. It would be good if
we keep this way. The same for other test cases.

> +	/* r7 = sk_fullsock(skb); */
> +	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
> +	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
> +	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
> +	/* r0 = sk_fullsock(skb); */
> +	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
> +	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
> +	/* if (r0 == null) return 0; */
> +	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
> +	BPF_MOV64_IMM(BPF_REG_0, 0),
> +	BPF_EXIT_INSN(),
> +	/* if (r0 == r7) r0 = *(r7->type); */
> +	BPF_JMP_REG(BPF_JNE, BPF_REG_0, BPF_REG_7, 1), /* Use ! JNE ! */
> +	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
> +	/* return 0 */
> +	BPF_MOV64_IMM(BPF_REG_0, 0),
> +	BPF_EXIT_INSN(),
> +	},
> +	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
> +	.result = ACCEPT,
> +},
[...]

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Yonghong Song]

On 8/23/22 4:15 PM, John Fastabend wrote:
> Eduard Zingerman wrote:
>> Propagate nullness information for branches of register to register
>> equality compare instructions. The following rules are used:
>> - suppose register A maybe null
>> - suppose register B is not null
>> - for JNE A, B, ... - A is not null in the false branch
>> - for JEQ A, B, ... - A is not null in the true branch
>>
>> E.g. for program like below:
>>
>>    r6 = skb->sk;
>>    r7 = sk_fullsock(r6);
>>    r0 = sk_fullsock(r6);
>>    if (r0 == 0) return 0;    (a)
>>    if (r0 != r7) return 0;   (b)
>>    *r7->type;                (c)
>>    return 0;
>>
>> It is safe to dereference r7 at point (c), because of (a) and (b).
> 
> I think the idea makes sense. Perhaps Yonhong can comment seeing he was active
> on the LLVM thread. I just scanned the LLVM side for now will take a look
> in more detail in a bit.

The issue is discovered when making some changes in llvm compiler.
I think it is good to add support in verifier so in the future
if compiler generates such code patterns, user won't get
surprised verification failure.

> 
>>
>> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
>> ---
>>   kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++-
>>   1 file changed, 38 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 2c1f8069f7b7..c48d34625bfd 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
>>   	return type & PTR_MAYBE_NULL;
>>   }
>>   
>> +static bool type_is_pointer(enum bpf_reg_type type)
>> +{
>> +	return type != NOT_INIT && type != SCALAR_VALUE;
>> +}
>> +
> 
> Instead of having another helper is_pointer_value() could work here?
> Checking if we need NOT_INIT in that helper now.
> 
>>   static bool is_acquire_function(enum bpf_func_id func_id,
>>   				const struct bpf_map *map)
>>   {
>> @@ -10046,6 +10051,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>>   	struct bpf_verifier_state *other_branch;
>>   	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
>>   	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
>> +	struct bpf_reg_state *eq_branch_regs;
>>   	u8 opcode = BPF_OP(insn->code);
>>   	bool is_jmp32;
>>   	int pred = -1;
>> @@ -10155,7 +10161,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>>   	/* detect if we are comparing against a constant value so we can adjust
>>   	 * our min/max values for our dst register.
>>   	 * this is only legit if both are scalars (or pointers to the same
>> -	 * object, I suppose, but we don't support that right now), because
>> +	 * object, I suppose, see the next if block), because
>>   	 * otherwise the different base pointers mean the offsets aren't
>>   	 * comparable.
>>   	 */
>> @@ -10199,6 +10205,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>>   					opcode, is_jmp32);
>>   	}
>>   
>> +	/* if one pointer register is compared to another pointer
>> +	 * register check if PTR_MAYBE_NULL could be lifted.
>> +	 * E.g. register A - maybe null
>> +	 *      register B - not null
>> +	 * for JNE A, B, ... - A is not null in the false branch;
>> +	 * for JEQ A, B, ... - A is not null in the true branch.
>> +	 */
>> +	if (!is_jmp32 &&
>> +	    BPF_SRC(insn->code) == BPF_X &&
>> +	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
>> +	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
>> +		eq_branch_regs = NULL;
>> +		switch (opcode) {
>> +		case BPF_JEQ:
>> +			eq_branch_regs = other_branch_regs;
>> +			break;
>> +		case BPF_JNE:
>> +			eq_branch_regs = regs;
>> +			break;
>> +		default:
>> +			/* do nothing */
>> +			break;
>> +		}
>> +		if (eq_branch_regs) {
>> +			if (type_may_be_null(src_reg->type))
>> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
>> +			else
>> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
>> +		}
>> +	}
>> +
>>   	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
>>   	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
>>   		find_equal_scalars(this_branch, dst_reg);
>> -- 
>> 2.37.1
>>
> 
> 

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[John Fastabend]

Yonghong Song wrote:
> 
> 
> On 8/23/22 4:15 PM, John Fastabend wrote:
> > Eduard Zingerman wrote:
> >> Propagate nullness information for branches of register to register
> >> equality compare instructions. The following rules are used:
> >> - suppose register A maybe null
> >> - suppose register B is not null
> >> - for JNE A, B, ... - A is not null in the false branch
> >> - for JEQ A, B, ... - A is not null in the true branch
> >>
> >> E.g. for program like below:
> >>
> >>    r6 = skb->sk;
> >>    r7 = sk_fullsock(r6);
> >>    r0 = sk_fullsock(r6);
> >>    if (r0 == 0) return 0;    (a)
> >>    if (r0 != r7) return 0;   (b)
> >>    *r7->type;                (c)
> >>    return 0;
> >>
> >> It is safe to dereference r7 at point (c), because of (a) and (b).
> > 
> > I think the idea makes sense. Perhaps Yonhong can comment seeing he was active
> > on the LLVM thread. I just scanned the LLVM side for now will take a look
> > in more detail in a bit.
> 
> The issue is discovered when making some changes in llvm compiler.
> I think it is good to add support in verifier so in the future
> if compiler generates such code patterns, user won't get
> surprised verification failure.
> 

I agree. Read the LLVM thread as well.

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[John Fastabend]

Eduard Zingerman wrote:
> > On Tue, 2022-08-23 at 16:15 -0700, John Fastabend wrote:
> 
> Hi John,
> 
> Thank you for commenting!
> 
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 2c1f8069f7b7..c48d34625bfd 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> > >  	return type & PTR_MAYBE_NULL;
> > >  }
> > >  
> > > +static bool type_is_pointer(enum bpf_reg_type type)
> > > +{
> > > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > > +}
> > > +
> > 
> > Instead of having another helper is_pointer_value() could work here?
> > Checking if we need NOT_INIT in that helper now.
> 
> Do you mean modifying the `__is_pointer_value` by adding a check
> `reg->type != NOT_INIT`?
> 
> I tried this out and tests are passing, but __is_pointer_value /
> is_pointer_value are used in a lot of places, seem to be a scary
> change, to be honest.

Agree it looks scary I wanted to play around with it more. I agree
its not the same and off to investigate a few places we use
__is_pointer_value now. Might add a few more tests while I'm at it.

> 
> Thanks,
> Eduard

Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Hi John,

> Agree it looks scary I wanted to play around with it more. I agree
> its not the same and off to investigate a few places we use
> __is_pointer_value now. Might add a few more tests while I'm at it.

I think that update to `__is_pointer_value` should probably be done
but is unrelated to this patch. And, as you mention, would require
crafting some number of test cases for NOT_INIT case :)

I'd prefer to keep the current predicate as is and reuse it at some
later point in the updated `__is_pointer_value` function.

What do you think?

Thanks,
Eduard