Re: [PATCH bpf-next v3 3/5] bpf: Inline calls to bpf_loop when callback is known

[Eduard Zingerman <eddyz87@gmail.com>]

Hi Alexei,

> On Sat, 2022-06-04 at 16:47 +0200, Alexei Starovoitov wrote:
> > On Fri, Jun 03, 2022 at 05:10:45PM +0300, Eduard Zingerman wrote:
[...]
> > +		if (fit_for_bpf_loop_inline(aux)) {
> > +			if (!subprog_updated) {
> > +				subprog_updated = true;
> > +				subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
> 
> Instead of doing += and keeping track that the stack was increased
> (if multiple bpf_loop happened to be in a function)
> may be add subprogs[..].stack_depth_extra variable ?
> And unconditionally do subprogs[cur_subprog].stack_depth_extra = BPF_REG_SIZE * 3;
> every time bpf_loop is seen?
> Then we can do that during inline_bpf_loop().
[...]
> > @@ -12963,6 +13047,8 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
> >  			 * in adjust_btf_func() - no need to adjust
> >  			 */
> >  		}
> > +
> > +		adjust_loop_inline_subprogno(env, i, j);
> 
> This special case isn't great.
> May be let's do inline_bpf_loop() earlier?
> Instead of doing it from do_misc_fixups() how about doing it as a separate
> pass right after check_max_stack_depth() ?
> Then opt_remove_dead_code() will adjust BPF_CALL_REL automatically
> as a part of bpf_adj_branches().
[...]
> >  	if (ret == 0)
> >  		ret = check_max_stack_depth(env);
> >  
> > +	if (ret == 0)
> > +		adjust_stack_depth_for_loop_inlining(env);
> 
> With above two suggestions this will become
> if (ret == 0)
>     optimize_bpf_loop(env);
> 
> where it will call inline_bpf_loop() and will assign max_depth_extra.
> And then one extra loop for_each_subporg() max_depth += max_depth_extra.
> 
> wdyt?

I will proceed with the suggested rewrite, it simplifies a few things,
thank you!

> Also is there a test for multiple bpf_loop in a func?

Yes, please see the test case "bpf_loop_inline stack locations for
loop vars" in the patch "v3 4/5" from this series.

Also, please note Joanne's comment from a sibiling thread:

> > +       if (ret == 0)
> > +               adjust_stack_depth_for_loop_inlining(env);
> 
> Do we need to do this before the check_max_stack_depth() call above
> since adjust_stack_depth_for_loop_inlining() adjusts the stack depth?

In short, what is the meaning of the `MAX_BPF_STACK` variable?

- Is it a hard limit on BPF program stack size?

  If so, `optimize_bpf_loop` should skip the optimization if not
  enough stack space is available. But this makes optimization a bit
  'flaky'. This could be achieved by passing maximal stack depth
  computed by `check_max_stack_depth` to `optimize_bpf_loop`.

- Or is it a soft limit used by verifier to guarantee that stack space
  needed by the BPF program is limited?
  
  If so, `optimize_bpf_loop` might be executed after
  `check_max_stack_depth` w/o any data passed from one to another. But
  this would mean that for some programs actual stack usage would be
  `MAX_BPF_STACK + 24*N`. Where N is a number of functions with
  inlined loops (which is easier to compute than the max number of
  functions with inlined loop that can occur on a same stack trace).
  
  This might affect the following portion of the `do_misc_fixups`:
  
 static int do_misc_fixups(struct bpf_verifier_env *env) {
	...
		if (insn->imm == BPF_FUNC_tail_call) {
			/* If we tail call into other programs, we
			 * cannot make any assumptions since they can
			 * be replaced dynamically during runtime in
			 * the program array.
			 */
			prog->cb_access = 1;
			if (!allow_tail_call_in_subprogs(env))
here ---->     			prog->aux->stack_depth = MAX_BPF_STACK;
			...
		}
	...
 }

Thanks,
Eduard