John Fastabend wrote:
> It is not possible for the current verifier to track u32 alu ops and jmps
> correctly. This can result in the verifier aborting with errors even though
> the program should be verifiable. Cilium code base has hit this but worked
> around it by changing int variables to u64 variables and marking a few
> things volatile. It would be better to avoid these tricks.
Quick bit of clarification, originally I tried to just track u32 hence
the title and above u32 reference. After runnning some programs I realized
this wasn't really enough to handle all cases so I added the signed 32-bit
bounds tracker. If I missed some spots in the descriptions that was just
because I missed it in the proof reading here. u32 above should be 32-bit
subreg.
I also forgot to give Yonhong credit. Sorry Yonghong! The original alu ops
tracking patch came from him.
>
> But, the main reason to address this now is do_refine_retval_range() was
> assuming return values could not be negative. Once we fix this in the
> next patches code that was previously working will no longer work.
> See do_refine_retval_range() patch for details.
>
> The simplest example code snippet that illustrates the problem is likelyy
> this,
>
> 53: w8 = w0 // r8 <- [0, S32_MAX],
> // w8 <- [-S32_MIN, X]
> 54: w8 <s 0 // r8 <- [0, U32_MAX]
> // w8 <- [0, X]
[...]
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 5406e6e96585..66126c411d52 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -114,6 +114,7 @@ struct bpf_reg_state {
> * with the same id as us.
> */
> struct tnum var_off;
> + struct tnum var32_off;
> /* Used to determine if any memory access using this register will
> * result in a bad access.
> * These refer to the same value as var_off, not necessarily the actual
> @@ -123,6 +124,10 @@ 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 */
> + u32 u32_min_value; /* minimum possible (u32)value */
> + u32 u32_max_value; /* maximum possible (u32)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/include/linux/limits.h b/include/linux/limits.h
> index 76afcd24ff8c..0d3de82dd354 100644
> --- a/include/linux/limits.h
> +++ b/include/linux/limits.h
> @@ -27,6 +27,7 @@
> #define S16_MAX ((s16)(U16_MAX >> 1))
> #define S16_MIN ((s16)(-S16_MAX - 1))
> #define U32_MAX ((u32)~0U)
> +#define U32_MIN ((u32)0)
I like using U32_MIN and U64_MIN defines, I think it reads better
but not necessary and could be pushed into bpf-next perhaps.
> #define S32_MAX ((s32)(U32_MAX >> 1))
> #define S32_MIN ((s32)(-S32_MAX - 1))
> #define U64_MAX ((u64)~0ULL)
> diff --git a/include/linux/tnum.h b/include/linux/tnum.h
[...]
> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> index d4f335a9a899..a444f77fb169 100644
> --- a/kernel/bpf/tnum.c
> +++ b/kernel/bpf/tnum.c
> @@ -12,6 +12,8 @@
> #define TNUM(_v, _m) (struct tnum){.value = _v, .mask = _m}
> /* A completely unknown value */
> const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
> +/* should we have a proper 32-bit tnum so math works without hacks? */
> +const struct tnum tnum32_unknown = { .value = 0, .mask = 0xffffffff };
>
> struct tnum tnum_const(u64 value)
> {
Per commit message comment ^^^^ here is the tnum logic that I suspect
should be made 32 bit types although maybe not harmful as is.
>
> /* detect if R == 0 where R is returned from bpf_map_lookup_elem().
> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
> index 87eaa49609a0..97463ad255ac 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -943,7 +943,7 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
> attr.insns = prog;
> attr.insns_cnt = prog_len;
> attr.license = "GPL";
> - attr.log_level = verbose || expected_ret == VERBOSE_ACCEPT ? 1 : 4;
> + attr.log_level = verbose || expected_ret == VERBOSE_ACCEPT ? 2 : 4;
This is just test code I'll push something to bpf-next so we can make
test_verifier more verbose. I found this helpful when debugging errors.
Seems probably useful upstream as well seeing I do this often I'm
guessing others probably do as well. Probably 'test_verifier -vv' should
do the trick.
> attr.prog_flags = pflags;
>
> fd_prog = bpf_load_program_xattr(&attr, bpf_vlog, sizeof(bpf_vlog));
>
