Re: [PATCH bpf-next v7 4/5] bpf: verifier: Support eliding map lookup nullness

["Daniel Xu" <dxu@dxuuu.xyz>]

Hi Ilya,

On Thu, Jan 30, 2025, at 2:06 AM, Ilya Leoshkevich wrote:
> On Wed, 2025-01-29 at 10:45 -0700, Daniel Xu wrote:
>> On Wed, Jan 29, 2025 at 09:49:12AM -0700, Daniel Xu wrote:
>> > Hi Ilya,
>> > 
>> > On Wed, Jan 29, 2025 at 03:58:54PM +0100, Ilya Leoshkevich wrote:
>> > > On Tue, 2025-01-14 at 13:28 -0700, Daniel Xu wrote:
>> > > > This commit allows progs to elide a null check on statically
>> > > > known
>> > > > map
>> > > > lookup keys. In other words, if the verifier can statically
>> > > > prove
>> > > > that
>> > > > the lookup will be in-bounds, allow the prog to drop the null
>> > > > check.
>> > > > 
>> > > > This is useful for two reasons:
>> > > > 
>> > > > 1. Large numbers of nullness checks (especially when they
>> > > > cannot
>> > > > fail)
>> > > >    unnecessarily pushes prog towards
>> > > > BPF_COMPLEXITY_LIMIT_JMP_SEQ.
>> > > > 2. It forms a tighter contract between programmer and verifier.
>> > > > 
>> > > > For (1), bpftrace is starting to make heavier use of percpu
>> > > > scratch
>> > > > maps. As a result, for user scripts with large number of
>> > > > unrolled
>> > > > loops,
>> > > > we are starting to hit jump complexity verification errors. 
>> > > > These
>> > > > percpu lookups cannot fail anyways, as we only use static key
>> > > > values.
>> > > > Eliding nullness probably results in less work for verifier as
>> > > > well.
>> > > > 
>> > > > For (2), percpu scratch maps are often used as a larger stack,
>> > > > as the
>> > > > currrent stack is limited to 512 bytes. In these situations, it
>> > > > is
>> > > > desirable for the programmer to express: "this lookup should
>> > > > never
>> > > > fail,
>> > > > and if it does, it means I messed up the code". By omitting the
>> > > > null
>> > > > check, the programmer can "ask" the verifier to double check
>> > > > the
>> > > > logic.
>> > > > 
>> > > > Tests also have to be updated in sync with these changes, as
>> > > > the
>> > > > verifier is more efficient with this change. Notable, iters.c
>> > > > tests
>> > > > had
>> > > > to be changed to use a map type that still requires null
>> > > > checks, as
>> > > > it's
>> > > > exercising verifier tracking logic w.r.t iterators.
>> > > > 
>> > > > Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
>> > > > ---
>> > > >  kernel/bpf/verifier.c                         | 92
>> > > > ++++++++++++++++++-
>> > > >  tools/testing/selftests/bpf/progs/iters.c     | 14 +--
>> > > >  .../selftests/bpf/progs/map_kptr_fail.c       |  2 +-
>> > > >  .../selftests/bpf/progs/verifier_map_in_map.c |  2 +-
>> > > >  .../testing/selftests/bpf/verifier/map_kptr.c |  2 +-
>> > > >  5 files changed, 99 insertions(+), 13 deletions(-)
>> > > 
>> > > [...]
>> > > 
>> > > > @@ -9158,6 +9216,7 @@ static int check_func_arg(struct
>> > > > bpf_verifier_env *env, u32 arg,
>> > > >  	enum bpf_arg_type arg_type = fn->arg_type[arg];
>> > > >  	enum bpf_reg_type type = reg->type;
>> > > >  	u32 *arg_btf_id = NULL;
>> > > > +	u32 key_size;
>> > > >  	int err = 0;
>> > > >  
>> > > >  	if (arg_type == ARG_DONTCARE)
>> > > > @@ -9291,8 +9350,13 @@ static int check_func_arg(struct
>> > > > bpf_verifier_env *env, u32 arg,
>> > > >  			verbose(env, "invalid map_ptr to
>> > > > access map-
>> > > > > key\n");
>> > > >  			return -EACCES;
>> > > >  		}
>> > > > -		err = check_helper_mem_access(env, regno,
>> > > > meta-
>> > > > > map_ptr->key_size,
>> > > > -					      BPF_READ, false,
>> > > > NULL);
>> > > > +		key_size = meta->map_ptr->key_size;
>> > > > +		err = check_helper_mem_access(env, regno,
>> > > > key_size,
>> > > > BPF_READ, false, NULL);
>> > > > +		if (err)
>> > > > +			return err;
>> > > > +		meta->const_map_key =
>> > > > get_constant_map_key(env, reg,
>> > > > key_size);
>> > > > +		if (meta->const_map_key < 0 && meta-
>> > > > >const_map_key
>> > > > != -EOPNOTSUPP)
>> > > > +			return meta->const_map_key;
>> > > 
>> > > Mark Hartmayer reported a problem that after this commit the
>> > > verifier
>> > > started refusing to load libvirt's virCgroupV2DevicesLoadProg(),
>> > > which
>> > > contains the following snippet:
>> > > 
>> > > 53: (b7) r1 = -1                      ; R1_w=-1
>> > > 54: (7b) *(u64 *)(r10 -8) = r1        ; R1_w=-1 R10=fp0 fp-8_w=-1
>> > > 55: (bf) r2 = r10                     ; R2_w=fp0 R10=fp0
>> > > 56: (07) r2 += -8                     ; R2_w=fp-8
>> > > 57: (18) r1 = 0x9553c800              ; R1_w=map_ptr(ks=8,vs=4)
>> > > 59: (85) call bpf_map_lookup_elem#1
>> > > 
>> > > IIUC here the actual constant value is -1, which this code
>> > > confuses
>> > > with an error.
>> > 
>> > Thanks for reporting. I think I know what the issue is - will send
>> > a
>> > patch shortly.
>> > 
>> > Daniel
>> > 
>> 
>> I cribbed the source from [0] and tested before and after. I think
>> this
>> should work. Mind giving it a try?
>> 
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 9971c03adfd5..e9176a5ce215 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -9206,6 +9206,8 @@ static s64 get_constant_map_key(struct
>> bpf_verifier_env *env,
>>         return reg->var_off.value;
>>  }
>> 
>> +static bool can_elide_value_nullness(enum bpf_map_type type);
>> +
>>  static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
>>                           struct bpf_call_arg_meta *meta,
>>                           const struct bpf_func_proto *fn,
>> @@ -9354,9 +9356,11 @@ static int check_func_arg(struct
>> bpf_verifier_env *env, u32 arg,
>>                 err = check_helper_mem_access(env, regno, key_size,
>> BPF_READ, false, NULL);
>>                 if (err)
>>                         return err;
>> -               meta->const_map_key = get_constant_map_key(env, reg,
>> key_size);
>> -               if (meta->const_map_key < 0 && meta->const_map_key !=
>> -EOPNOTSUPP)
>> -                       return meta->const_map_key;
>> +               if (can_elide_value_nullness(meta->map_ptr-
>> >map_type)) {
>> +                       meta->const_map_key =
>> get_constant_map_key(env, reg, key_size);
>> +                       if (meta->const_map_key < 0 && meta-
>> >const_map_key != -EOPNOTSUPP)
>> +                               return meta->const_map_key;
>> +               }
>>                 break;
>>         case ARG_PTR_TO_MAP_VALUE:
>>                 if (type_may_be_null(arg_type) &&
>> register_is_null(reg))
>> 
>> Thanks,
>> Daniel
>> 
>> 
>> [0]:
>> https://github.com/libvirt/libvirt/blob/c1166be3475a0269f5164d87fec6227d6cb34b47/src/util/vircgroupv2devices.c#L66-L135
>
> Thanks, I tried this in isolation and it fixed the issue for me.
> I talked to Mark and he will try it with his libvirt scenario.

Thanks for testing! 

>
> The code looks reasonable to me, but I have a small concern regarding
> what will happen if the BPF code uses a -EOPNOTSUPP immediate with an
> array. Unlike other immediates, IIUC this will cause check_func_arg()
> to return 0. Is there a reason to have this special?

That's a good point. Lemme check on that.

Thanks,
Daniel