* [PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons
@ 2022-08-22 9:43 Eduard Zingerman
2022-08-22 9:43 ` [PATCH RFC bpf-next 1/2] bpf: " Eduard Zingerman
2022-08-22 9:43 ` [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman
0 siblings, 2 replies; 11+ messages in thread
From: Eduard Zingerman @ 2022-08-22 9:43 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, yhs; +Cc: 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-22 9:43 [PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons Eduard Zingerman
@ 2022-08-22 9:43 ` Eduard Zingerman
2022-08-23 23:15 ` John Fastabend
2022-08-25 2:34 ` Yonghong Song
2022-08-22 9:43 ` [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman
1 sibling, 2 replies; 11+ messages in thread
From: Eduard Zingerman @ 2022-08-22 9:43 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, yhs; +Cc: 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
2022-08-22 9:43 [PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons Eduard Zingerman
2022-08-22 9:43 ` [PATCH RFC bpf-next 1/2] bpf: " Eduard Zingerman
@ 2022-08-22 9:43 ` Eduard Zingerman
2022-08-25 2:38 ` Yonghong Song
1 sibling, 1 reply; 11+ messages in thread
From: Eduard Zingerman @ 2022-08-22 9:43 UTC (permalink / raw)
To: bpf, ast, andrii, daniel, kernel-team, yhs; +Cc: 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* RE: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-22 9:43 ` [PATCH RFC bpf-next 1/2] bpf: " Eduard Zingerman
@ 2022-08-23 23:15 ` John Fastabend
2022-08-24 22:05 ` Eduard Zingerman
2022-08-25 2:55 ` Yonghong Song
2022-08-25 2:34 ` Yonghong Song
1 sibling, 2 replies; 11+ messages in thread
From: John Fastabend @ 2022-08-23 23:15 UTC (permalink / raw)
To: Eduard Zingerman, bpf, ast, andrii, daniel, kernel-team, yhs
Cc: Eduard Zingerman
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
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-23 23:15 ` John Fastabend
@ 2022-08-24 22:05 ` Eduard Zingerman
2022-08-25 6:21 ` John Fastabend
2022-08-25 2:55 ` Yonghong Song
1 sibling, 1 reply; 11+ messages in thread
From: Eduard Zingerman @ 2022-08-24 22:05 UTC (permalink / raw)
To: John Fastabend, bpf, ast, andrii, daniel, kernel-team, yhs
> 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-22 9:43 ` [PATCH RFC bpf-next 1/2] bpf: " Eduard Zingerman
2022-08-23 23:15 ` John Fastabend
@ 2022-08-25 2:34 ` Yonghong Song
1 sibling, 0 replies; 11+ messages in thread
From: Yonghong Song @ 2022-08-25 2:34 UTC (permalink / raw)
To: Eduard Zingerman, bpf, ast, andrii, daniel, kernel-team
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);
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
2022-08-22 9:43 ` [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman
@ 2022-08-25 2:38 ` Yonghong Song
0 siblings, 0 replies; 11+ messages in thread
From: Yonghong Song @ 2022-08-25 2:38 UTC (permalink / raw)
To: Eduard Zingerman, bpf, ast, andrii, daniel, kernel-team
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,
> +},
[...]
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-23 23:15 ` John Fastabend
2022-08-24 22:05 ` Eduard Zingerman
@ 2022-08-25 2:55 ` Yonghong Song
2022-08-25 6:19 ` John Fastabend
1 sibling, 1 reply; 11+ messages in thread
From: Yonghong Song @ 2022-08-25 2:55 UTC (permalink / raw)
To: John Fastabend, Eduard Zingerman, bpf, ast, andrii, daniel, kernel-team
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
>>
>
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-25 2:55 ` Yonghong Song
@ 2022-08-25 6:19 ` John Fastabend
0 siblings, 0 replies; 11+ messages in thread
From: John Fastabend @ 2022-08-25 6:19 UTC (permalink / raw)
To: Yonghong Song, John Fastabend, Eduard Zingerman, bpf, ast,
andrii, daniel, kernel-team
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-24 22:05 ` Eduard Zingerman
@ 2022-08-25 6:21 ` John Fastabend
2022-08-25 22:31 ` Eduard Zingerman
0 siblings, 1 reply; 11+ messages in thread
From: John Fastabend @ 2022-08-25 6:21 UTC (permalink / raw)
To: Eduard Zingerman, John Fastabend, bpf, ast, andrii, daniel,
kernel-team, yhs
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
2022-08-25 6:21 ` John Fastabend
@ 2022-08-25 22:31 ` Eduard Zingerman
0 siblings, 0 replies; 11+ messages in thread
From: Eduard Zingerman @ 2022-08-25 22:31 UTC (permalink / raw)
To: John Fastabend, bpf, ast, andrii, daniel, kernel-team, yhs
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2022-08-25 22:31 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-22 9:43 [PATCH RFC bpf-next 0/2] propagate nullness information for reg to reg comparisons Eduard Zingerman
2022-08-22 9:43 ` [PATCH RFC bpf-next 1/2] bpf: " Eduard Zingerman
2022-08-23 23:15 ` John Fastabend
2022-08-24 22:05 ` Eduard Zingerman
2022-08-25 6:21 ` John Fastabend
2022-08-25 22:31 ` Eduard Zingerman
2022-08-25 2:55 ` Yonghong Song
2022-08-25 6:19 ` John Fastabend
2022-08-25 2:34 ` Yonghong Song
2022-08-22 9:43 ` [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman
2022-08-25 2:38 ` Yonghong Song
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).