RE: [RFC PATCH 2/4] bpf: verifier, do explicit u32 bounds tracking

[John Fastabend <john.fastabend@gmail.com>]

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));
>