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

[Eduard Zingerman <eddyz87@gmail.com>]

Hi Joanne, thanks for the review!

> On Fri, 2022-06-03 at 17:06 -0700, Joanne Koong wrote:
> Should this be moved to include/linux/bpf.h since
> kernel/bpf/bpf_iter.c also uses this? Then we don't need the "#include
> <linux/bpf_verifier.h>" in bpf_iter.c

Will do.

> Also, as a side-note, I think if we have an "is_valid" field, then we
> don't need both the "callback_is_constant" and "flags_is_zero" fields.
> If the flags is not zero or the callback subprogno is not the same on
> each invocation of the instruction, then we could represent that by
> just setting is_valid to false.

Agree, I'll update the declaration as follows:

struct bpf_loop_inline_state {
	bool initialized; /* set to true upon first entry */
	bool can_inline; /* true if callback function
			  * is the same at each call
			  * and flags are always zero */
	u32 callback_subprogno; /* valid when can_inline is true */
	/* stack offset for loop vars;
	 * u16 since bpf_subprog_info.stack_depth is u16;
	 * we take the negative of it whenever we use it
	 * since the stack grows downwards
	 */
	u16 stack_base;
};

> Is placing this inside the union in "struct bpf_insn_aux_data" an option?

This is an option indeed, will do.

> > +
> > +               if (fit_for_bpf_loop_inline(aux)) {
> > +                       if (!subprog_updated) {
> > +                               subprog_updated = true;
> > +                               subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
> > +                               stack_base = -subprogs[cur_subprog].stack_depth;
> > +                       }
> > +                       aux->loop_inline_state.stack_base = stack_base;
> > +               }
> > +               if (i == subprog_end - 1) {
> > +                       subprog_updated = false;
> > +                       cur_subprog++;
> > +                       if (cur_subprog < env->subprog_cnt)
> > +                               subprog_end = subprogs[cur_subprog + 1].start;
> > +               }
> > +       }
> > +
> > +       env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
> 
> In the case where a subprogram that is not subprogram 0 is a fit for
> the bpf loop inline and thus increases its stack depth, won't
> env->prog->aux->stack_depth need to also be updated?

As far as I understand the logic in `do_check_main` and `jit_subprogs`
`env->prog->aux->stack_depth` always reflects the stack depth of the
first sub-program (aka `env->subprog_info[0].stack_depth`). So the
last line of `adjust_stack_depth_for_loop_inlining` merely ensures
this invariant. The stack depth for each relevant subprogram is
updated earlier in the function:

static void adjust_stack_depth_for_loop_inlining(struct bpf_verifier_env *env)
{
	...
	for (i = 0; i < insn_cnt; i++) {
		...
		if (fit_for_bpf_loop_inline(aux)) {
			if (!subprog_updated) {
				subprog_updated = true;
here  ---->			subprogs[cur_subprog].stack_depth += BPF_REG_SIZE * 3;
				...
			}
			...
		}
		if (i == subprog_end - 1) {
			subprog_updated = false;
			cur_subprog++;
			...
		}
	}
	...
}

Also, the patch v3 4/5 in a series has a test case "bpf_loop_inline
stack locations for loop vars" which checks that stack offsets for
spilled registers are assigned correctly for subprogram that is not a
first subprogram.

> > @@ -15030,6 +15216,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
> >         if (ret == 0)
> >                 ret = check_max_stack_depth(env);
> > 
> > +       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?

This is an interesting question. I used the following reasoning
placing `adjust_stack_depth_for_loop_inlining` after the
`check_max_stack_depth`:

1. If `adjust_stack_depth_for_loop_inlining` is placed before
   `check_max_stack_depth` some of the existing BPF programs might
   stop loading, because of increased stack usage.
2. To avoid (1) it is possible to do `check_max_stack_depth` first,
   remember actual max depth and apply
   `adjust_stack_depth_for_loop_inlining` only when there is enough
   stack space. However there are two downsides:
   - the optimization becomes flaky, similarly simple changes to the
     code of the BPF program might cause loop inlining to stop
     working;
   - the precise verification itself is non-trivial as each possible
     stack trace has to be analyzed in terms of stack size with loop
     inlining / stack size without loop inlining. If necessary, I will
     probably use a simpler heuristic where stack budget for register
     spilling would be computed as
     `MAX_BPF_STACK - actual_max_stack_depth`
3. Things are simpler if MAX_BPF_STACK is a soft limit that ensures
   that BPF programs consume limited amount of stack. In such case
   current implementation is sufficient.

So this boils down to the question what is `MAX_BPF_STACK`:
- a hard limit for the BPF program stack size?
- a soft limit used to verify that programs consume a limited amount
  of stack while executing?

If the answer is "hard limit" I'll proceed with implementation for
option (2).

Thanks,
Eduard