Yonghong Song wrote:
> Commit b7a0d65d80a0 ("bpf, testing: Workaround a verifier failure
> for test_progs") worked around a verifier failure where the
> register is copied to another later refined register, but the
> original register is used after refinement. Another similar example is
> https://lore.kernel.org/netdev/871019a0-71f8-c26d-0ae8-c7fd8c8867fc@xxxxxx/
>
> LLVM commit https://reviews.llvm.org/D72787 added a phase
FWIW I was going to try and see if we could refine the bounds by
walking parents chain. But that is an experiment tbd.
> to adjust optimization such that the original register is
> directly refined and used later. Another issue exposed by
> the llvm is verifier cannot handle the following code:
> call bpf_strtoul
> if w0 s< 1 then ...
> if w0 s> 7 then ...
> ... use w0 ...
>
> Unfortunately, the verifier is not able to handle the above
> code well and will reject it.
> call bpf_strtoul
> R0_w=inv(id=0) R8=invP0
> if w0 s< 0x1 goto pc-22
> R0_w=inv(id=0) R8=invP0
> if w0 s> 0x7 goto pc-23
> R0=inv(id=0) R8=invP0
> w0 += w8
> R0_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8=invP0
>
> After "w0 += w8", we got a very conservative R0 value, which
> later on caused verifier rejection.
>
> This patch added two register states, s32_min_value and s32_max_value,
> to bpf_reg_state. These two states capture the signed 32bit
> min/max values refined due to 32bit signed sle/slt/sge/sgt comparisons.
> 1. whenever refined s32_min_value, s32_max_value is captured, reg->var_off
> will be refined if possible.
> 2. For any ALU32 operation where the dst_reg will have upper 32bit cleared,
> if s32_min_value >= 0 and s32_max_value has been narrowed due to previous
> signed compare operation, the dst_reg as an input can ignore upper 32bit values,
> this may produce better output dst_reg value range.
Can you comment a bit more on the s32_min_value < 0 case? Regardless of the
s32_{min|max}_value the result should be zero extended and smin_value=0. This
is enforced by verifier_zext(), an aside but I think we should just remove
verifier_zext its not very useful if all jits have to comply imo.
If smin_value=0 && s32_max_value>=0 then we should be safe to propagate s32_max_value
into smax_Value as well.
> 3. s32_min_value and s32_max_value is reset if the corresponding register
> is redefined.
>
> The following shows the new register states for the above example.
> call bpf_strtoul
> R0_w=inv(id=0) R8=invP0
> if w0 s< 0x1 goto pc-22
> R0_w=inv(id=0,smax_value=9223372034707292159,umax_value=18446744071562067967,
> s32_min_value=1,var_off=(0x0; 0xffffffff7fffffff))
> R8=invP0
> if w0 s> 0x7 goto pc-23
> R0=inv(id=0,smax_value=9223372032559808519,umax_value=18446744069414584327,
> s32_min_value=1,s32_max_value=7,var_off=(0x0; 0xffffffff00000007))
> R8=invP0
> w0 += w8
> R0_w=inv(id=0,umax_value=7,var_off=(0x0; 0x7)) R8=invP0
And we should also have smin_value=0?
>
> With the above LLVM patch and this commit, the original
> workaround in Commit b7a0d65d80a0 is not needed any more.
>
> Signed-off-by: Yonghong Song <yhs@xxxxxx>
> ---
> include/linux/bpf_verifier.h | 2 +
> kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++-----
> 2 files changed, 65 insertions(+), 10 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 5406e6e96585..d5694308466d 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -123,6 +123,8 @@ struct bpf_reg_state {
> s64 smax_value; /* maximum possible (s64)value */
> u64 umin_value; /* minimum possible (u64)value */
> u64 umax_value; /* maximum possible (u64)value */
> + s32 s32_min_value; /* minimum possible (s32)value */
> + s32 s32_max_value; /* maximum possible (s32)value */
> /* parentage chain for liveness checking */
> struct bpf_reg_state *parent;
> /* Inside the callee two registers can be both PTR_TO_STACK like
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 1cc945daa9c8..c5d6835c38db 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -543,6 +543,14 @@ static void print_verifier_state(struct bpf_verifier_env *env,
> if (reg->umax_value != U64_MAX)
> verbose(env, ",umax_value=%llu",
> (unsigned long long)reg->umax_value);
> + if (reg->s32_min_value != reg->umin_value &&
> + reg->s32_min_value != S32_MIN)
> + verbose(env, ",s32_min_value=%d",
> + (int)reg->s32_min_value);
> + if (reg->s32_max_value != reg->umax_value &&
> + reg->s32_max_value != S32_MAX)
> + verbose(env, ",s32_max_value=%d",
> + (int)reg->s32_max_value);
> if (!tnum_is_unknown(reg->var_off)) {
> char tn_buf[48];
>
> @@ -923,6 +931,10 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
> reg->smax_value = (s64)imm;
> reg->umin_value = imm;
> reg->umax_value = imm;
> +
> + /* no need to be precise, just reset s32_{min,max}_value */
> + reg->s32_min_value = S32_MIN;
> + reg->s32_max_value = S32_MAX;
If its known it would make more sense to me to set the min/max value vs this
shortcut. Otherwise we wont have bounds to compare against on a JMP32.
> }
Still thinking through the rest, but figured it would be worth kicking the
couple comments above out.. I'm trying to understand if the coerce_reg_size()
can be made a bit cleaner.
Thanks,
John
