Date:   Wed, 2 Jan 2019 18:57:01 +0000
From:   Yonghong Song <yhs@...com>
To:     Jakub Kicinski <jakub.kicinski@...ronome.com>
CC:     "alexei.starovoitov@...il.com" <alexei.starovoitov@...il.com>,
        "daniel@...earbox.net" <daniel@...earbox.net>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        "oss-drivers@...ronome.com" <oss-drivers@...ronome.com>
Subject: Re: [RFC bpf-next v4 03/12] bpf: verifier: remove dead code



On 1/2/19 10:31 AM, Jakub Kicinski wrote:
> 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@...ronome.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?

It does make sense. I did not know env->subprog_info[env->subprog_cnt]
is valid. Have not carefully read generic verifier code for a long time 
:-(. Your current code is fine then.

> 
>>> +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.

A little bit scrutiny shows two codes are equivalent.
prog->len >= off is always true.
if i < nr_linfo, prog->len > off must true since some insns after off 
will survive. So my code can transform to your code and vice versa.
You are right. There is no need to change.
Here prog->len is the length after dead insn removal. A little bit
comment will help review and other people later code inspection.

With that, you can add my Ack to patch 1-5.
Acked-by: Yonghong Song <yhs@...com>

Powered by blists - more mailing lists