| Message ID | 20220822094312.175448-2-eddyz87@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | propagate nullness information for reg to reg comparisons | expand |
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 >
> 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
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);
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 >> > >
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.
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
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
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);
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(-)