netdev - Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code

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 for Android: free password hash cracker in your pocket

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

Message-ID: <88765f51-a1a3-e3a5-df8b-ea4016b88f71@fb.com>
Date:   Thu, 20 Dec 2018 07:19:06 +0000
From:   Yonghong Song <yhs@...com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Jakub Kicinski <jakub.kicinski@...ronome.com>
CC:     "daniel@...earbox.net" <daniel@...earbox.net>,
        "oss-drivers@...ronome.com" <oss-drivers@...ronome.com>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        Martin Lau <kafai@...com>
Subject: Re: [PATCH bpf-next 07/19] bpf: verifier: remove dead code



On 12/19/18 4:45 PM, Alexei Starovoitov wrote:
> On Wed, Dec 19, 2018 at 10:29:18AM -0800, Jakub Kicinski wrote:
>> Instead of overwriting dead code with jmp -1 instructions
>> remove it completely for root.  Adjust verifier state and
>> line info appropriately.
>>
>> Signed-off-by: Jakub Kicinski <jakub.kicinski@...ronome.com>
>> ---
>>   include/linux/filter.h |   1 +
>>   kernel/bpf/core.c      |  12 ++++
>>   kernel/bpf/verifier.c  | 139 ++++++++++++++++++++++++++++++++++++++++-
>>   3 files changed, 149 insertions(+), 3 deletions(-)
>>
>> diff --git a/include/linux/filter.h b/include/linux/filter.h
>> index 537e9e7c6e6f..c99969022493 100644
>> --- a/include/linux/filter.h
>> +++ b/include/linux/filter.h
>> @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void)
>>   
>>   struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>>   				       const struct bpf_insn *patch, u32 len);
>> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
>>   
>>   void bpf_clear_redirect_map(struct bpf_map *map);
>>   
>> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
>> index 2eb7cc9822bb..e3498d82eb74 100644
>> --- a/kernel/bpf/core.c
>> +++ b/kernel/bpf/core.c
>> @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
>>   	return prog_adj;
>>   }
>>   
>> +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
>> +{
>> +	/* Branch offsets can't overflow when program is shrinking, no need
>> +	 * to call bpf_adj_branches(..., true) here
>> +	 */
>> +	memmove(prog->insnsi + off, prog->insnsi + off + cnt,
>> +		sizeof(struct bpf_insn) * (prog->len - off - cnt));
>> +	prog->len -= cnt;
>> +
>> +	return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
>> +}
>> +
>>   void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
>>   {
>>   	int i;
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 7db2a48ea7f7..98a276f4c4e6 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -6226,6 +6226,113 @@ 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
>> +	 */
> 
> I think this will break func_info, since it's not adjusted here.
> Also iirc line_info is relying on first insn to always have line_info.
> If first insn is dead, second insn might not have a line_info generated
> and things won't go well.

Right, func_info needs to be adjusted as well. The first line_info for 
each func must have insn_off = 0. In case of dead code elimination from
the start, if the first remaining insn has a line_info, just use it.
Otherwise, you can use the old first line_info.


> 
> Martin, Yonghong, please chime in.
>