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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <hsgmutuoi4kvjkr7erm5ty2fdrhdrjpz4fpp5doe65l3pzguxv@lcbmvmjpyykq>
Date: Wed, 29 Jan 2025 09:49:12 -0700
From: Daniel Xu <dxu@...uu.xyz>
To: Ilya Leoshkevich <iii@...ux.ibm.com>
Cc: shuah@...nel.org, eddyz87@...il.com, ast@...nel.org, 
	daniel@...earbox.net, andrii@...nel.org, john.fastabend@...il.com, 
	martin.lau@...ux.dev, song@...nel.org, yonghong.song@...ux.dev, kpsingh@...nel.org, 
	sdf@...ichev.me, haoluo@...gle.com, jolsa@...nel.org, mykolal@...com, 
	bpf@...r.kernel.org, linux-kernel@...r.kernel.org, linux-kselftest@...r.kernel.org, 
	Marc Hartmayer <mhartmay@...ux.ibm.com>
Subject: Re: [PATCH bpf-next v7 4/5] bpf: verifier: Support eliding map
 lookup nullness

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@...uu.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