Re: [RFC bpf-next v4 03/12] bpf: verifier: remove dead code

[Jakub Kicinski <jakub.kicinski@netronome.com>]

On Wed, 2 Jan 2019 05:25:49 +0000, Yonghong Song wrote:
> On 12/31/18 5:37 PM, Jakub Kicinski wrote:
> > Instead of overwriting dead code with jmp -1 instructions
> > remove it completely for root.  Adjust verifier state and
> > line info appropriately.
> > 
> > v2:
> >   - adjust func_info (Alexei);
> >   - make sure first instruction retains line info (Alexei).
> > v4: (Yonghong)
> >   - remove unnecessary if (!insn to remove) checks;
> >   - always keep last line info if first live instruction lacks one.
> > 
> > Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>

> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 30e2cd399b4a..2f786acb65ce 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -6233,6 +6233,141 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
> >   	return new_prog;
> >   }
> >   
> > +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
> > +					      u32 off, u32 cnt)
> > +{
> > +	int i, j;
> > +
> > +	/* find first prog starting at or after off (first to remove) */
> > +	for (i = 0; i < env->subprog_cnt; i++)
> > +		if (env->subprog_info[i].start >= off)
> > +			break;
> > +	/* find first prog starting at or after off + cnt (first to stay) */
> > +	for (j = i; j < env->subprog_cnt; j++)
> > +		if (env->subprog_info[j].start >= off + cnt)
> > +			break;
> > +	/* if j doesn't start exactly at off + cnt, we are just removing
> > +	 * the front of previous prog
> > +	 */
> > +	if (env->subprog_info[j].start != off + cnt)
> > +		j--;  
> 
> It is possible that j = env->subprog_cnt here.
> 
> Looks like the following case is not properly covered:
> for
>     func1:
>       insn1
>       insn2
>     func2:
>       insn3
>       insn4
> 
>    case (1): insn3 removed
>    case (2): insn3 and insn4 removed, func2 subprog_info should be remeoved.
> 
> Maybe a change like below will work to include handling of the last subprog:
> 
> -       if (env->subprog_info[j].start != off + cnt)
> +       if ((j == env->subprog_cnt && env->prog->len > off) ||
> +           (j < env->subprog_cnt && env->subprog_info[j].start != off + cnt))
>                  j--;

As I think Ed alluded to there is another "exit" subprog at the
env->subprog_cnt index.  So accessing env->subprog_info[env->subprog_cnt]
is correct (which is quite handy).  test_verifier: "dead code: tail of
main + two functions" should cover this.  Would that make sense?

> > +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
> > +				      u32 cnt)
> > +{
> > +	struct bpf_prog *prog = env->prog;
> > +	u32 i, l_off, l_cnt, nr_linfo;
> > +	struct bpf_line_info *linfo;
> > +
> > +	nr_linfo = prog->aux->nr_linfo;
> > +	if (!nr_linfo)
> > +		return 0;
> > +
> > +	linfo = prog->aux->linfo;
> > +
> > +	/* find first line info to remove, count lines to be removed */
> > +	for (i = 0; i < nr_linfo; i++)
> > +		if (linfo[i].insn_off >= off)
> > +			break;
> > +
> > +	l_off = i;
> > +	l_cnt = 0;
> > +	for (; i < nr_linfo; i++)
> > +		if (linfo[i].insn_off < off + cnt)
> > +			l_cnt++;
> > +		else
> > +			break;
> > +
> > +	/* first live insn doesn't match first live linfo, inherit */
> > +	if (prog->len != off && l_cnt &&
> > +	    (i == nr_linfo || linfo[i].insn_off != off + cnt)) {
> > +		l_cnt--;
> > +		linfo[--i].insn_off = off + cnt;  
> 
> The same here. The handling the last line_info seems not sufficient.
> It depends on whether all insns covered by last linfo have been removed 
> or not.
> 
> Maybe something like below?
> +       if (l_cnt &&
> +           ((i == nr_linfo && prog->len > off) ||
> +            (i < nr_linfo && linfo[i].insn_off != off + cnt))) {
>                  l_cnt--;
>                  linfo[--i].insn_off = off + cnt;
> 
> Please double check whether my suggested fix is correct or not.
> You may want to add test cases to cover these cases as well.

Hm..  We only need to "inherit" the linfo, if the first instruction
after removed region doesn't have linfo.  So if there are no
instructions after the removed regions (we remove tail, off ==
prog->len) we can't possibly need to inherit.  No?  

I think your code is correct (because if there is no code there can't
be any linfo after, either) but I'm not sure why it would be necessary.