On Thu, Nov 2, 2023 at 5:08 PM Andrii Nakryiko <andrii@xxxxxxxxxx> wrote:
>
> Generalize is_branch_taken logic for SCALAR_VALUE register to handle
> cases when both registers are not constants. Previously supported
> <range> vs <scalar> cases are a natural subset of more generic <range>
> vs <range> set of cases.
>
> Generalized logic relies on straightforward segment intersection checks.
>
> Signed-off-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
> ---
> kernel/bpf/verifier.c | 103 ++++++++++++++++++++++++++----------------
> 1 file changed, 63 insertions(+), 40 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 52934080042c..2627461164ed 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14187,82 +14187,104 @@ static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
> u8 opcode, bool is_jmp32)
> {
> struct tnum t1 = is_jmp32 ? tnum_subreg(reg1->var_off) : reg1->var_off;
> + struct tnum t2 = is_jmp32 ? tnum_subreg(reg2->var_off) : reg2->var_off;
> u64 umin1 = is_jmp32 ? (u64)reg1->u32_min_value : reg1->umin_value;
> u64 umax1 = is_jmp32 ? (u64)reg1->u32_max_value : reg1->umax_value;
> s64 smin1 = is_jmp32 ? (s64)reg1->s32_min_value : reg1->smin_value;
> s64 smax1 = is_jmp32 ? (s64)reg1->s32_max_value : reg1->smax_value;
> - u64 uval = is_jmp32 ? (u32)tnum_subreg(reg2->var_off).value : reg2->var_off.value;
> - s64 sval = is_jmp32 ? (s32)uval : (s64)uval;
> + u64 umin2 = is_jmp32 ? (u64)reg2->u32_min_value : reg2->umin_value;
> + u64 umax2 = is_jmp32 ? (u64)reg2->u32_max_value : reg2->umax_value;
> + s64 smin2 = is_jmp32 ? (s64)reg2->s32_min_value : reg2->smin_value;
> + s64 smax2 = is_jmp32 ? (s64)reg2->s32_max_value : reg2->smax_value;
>
> switch (opcode) {
> case BPF_JEQ:
> - if (tnum_is_const(t1))
> - return !!tnum_equals_const(t1, uval);
> - else if (uval < umin1 || uval > umax1)
> + /* constants, umin/umax and smin/smax checks would be
> + * redundant in this case because they all should match
> + */
> + if (tnum_is_const(t1) && tnum_is_const(t2))
> + return t1.value == t2.value;
> + /* const ranges */
> + if (umin1 == umax1 && umin2 == umax2)
> + return umin1 == umin2;
> + if (smin1 == smax1 && smin2 == smax2)
> + return smin1 == smin2;
seems like I didn't remove these checks from BPF_JEQ (but I did for
BPF_JNE below). I'll fix it in next revision, but will wait for people
to review this one first.
> + /* non-overlapping ranges */
> + if (umin1 > umax2 || umax1 < umin2)
> return 0;
> - else if (sval < smin1 || sval > smax1)
> + if (smin1 > smax2 || smax1 < smin2)
> return 0;
> break;
> case BPF_JNE:
> - if (tnum_is_const(t1))
> - return !tnum_equals_const(t1, uval);
> - else if (uval < umin1 || uval > umax1)
> + /* constants, umin/umax and smin/smax checks would be
> + * redundant in this case because they all should match
> + */
> + if (tnum_is_const(t1) && tnum_is_const(t2))
> + return t1.value != t2.value;
> + /* non-overlapping ranges */
> + if (umin1 > umax2 || umax1 < umin2)
> return 1;
> - else if (sval < smin1 || sval > smax1)
> + if (smin1 > smax2 || smax1 < smin2)
> return 1;
> break;
[...]
