propagate nullness information for reg to reg comparisons
Subsystems (4)
Eduard Zingerman
maintainercover propagate nullness information for reg to reg comparisons
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
Signature · 1 line
2.37.1
Eduard Zingerman
maintainerRFC PATCH 1/2 bpf: propagate nullness information for reg to reg comparisons
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).
--- kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +38 -1
@@ -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);
Signature · 1 line
2.37.1
John Fastabend
reviewerRE: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 17 lines · 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 branchE.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;
Quoted 1 line
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.
Quoted 11 lines
Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 479
Quoted 8 lines
kernel/bpf/verifier.c +5
-0@@ -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.
Quoted 61 lines
kernel/bpf/verifier.c +33
-1static 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);Signature · 1 line
2.37.1
Eduard Zingerman
maintainerRe: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 1 line · John Fastabend
Hi John,
Thank you for commenting!
Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }
Quoted 8 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 479
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+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 needNOT_INITin 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
John Fastabend
reviewerRe: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 23 lines · Eduard Zingerman
Quoted 1 line · John Fastabend
Hi John,
Thank you for commenting!
Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }Quoted 8 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 479
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+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 needNOT_INITin that helper now.
Quoted 6 lines
Do you mean modifying the
__is_pointer_valueby adding a checkreg->type != NOT_INIT?I tried this out and tests are passing, but
__is_pointer_value/is_pointer_valueare 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.
Quoted 3 lines
Thanks,
Eduard
Eduard Zingerman
maintainerRe: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Hi John,
Quoted 3 lines
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_valuenow. 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
Re: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
In reply to John FastabendQuoted 18 lines · John Fastabend
Quoted 17 lines · 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 branchE.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;
Quoted 5 lines
Quoted 1 line
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.
Quoted 87 lines
Quoted 12 lines
Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +0
-0kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 479
Quoted 8 lines
kernel/bpf/verifier.c +5
-0@@ -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 needNOT_INITin that helper now.Quoted 61 lines
kernel/bpf/verifier.c +33
-1static 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);Signature · 1 line
2.37.1
John Fastabend
reviewerRe: [PATCH RFC bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 23 lines · Yonghong Song
Quoted 20 lines · John Fastabend
Quoted 18 lines · 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 branchE.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).
Quoted 9 lines
Quoted 3 lines
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
In reply to Eduard ZingermanQuoted 17 lines · 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 branchE.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;
Quoted 3 lines
It is safe to dereference r7 at point (c), because of (a) and (b).
Signed-off-by Eduard Zingerman <[email protected]>
You can remove RFC tag in the next revision.
LGTM with one nit below.
Quoted 61 lines
--- kernel/bpf/verifier.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +27
-1@@ -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 :
kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 10237
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+/* 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.
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+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);
Eduard Zingerman
maintainerRFC PATCH 2/2 selftests/bpf: check nullness propagation for reg to reg comparisons
In reply to Eduard ZingermanVerify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
--- .../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
tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c new file +186 -0
@@ -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, +},
Signature · 1 line
2.37.1
Re: [PATCH RFC bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
Quoted 4 lines · Eduard Zingerman
Verify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
Signed-off-by Eduard Zingerman <[email protected]>
LGTM with one nit below.
Quoted 23 lines
--- .../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.ctools/testing/selftests/bpf/verifier/jeq_infer_not_null.c new file +12
-0@@ -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).
tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c line 22
Quoted 10 lines
tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c new file +10
-0+* 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.
Quoted 21 lines
tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c new file +21
-0+/* 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, +},
[...]