netdev - Re: [PATCH bpf-next 3/7] bpf: improve verification speed by not remarking live

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <4b3f4129-f787-d9e4-164c-f7d6484bdd55@solarflare.com>
Date:   Mon, 1 Apr 2019 16:38:28 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Alexei Starovoitov <ast@...nel.org>, <davem@...emloft.net>
CC:     <daniel@...earbox.net>, <jakub.kicinski@...ronome.com>,
        <jannh@...gle.com>, <netdev@...r.kernel.org>,
        <bpf@...r.kernel.org>, <kernel-team@...com>
Subject: Re: [PATCH bpf-next 3/7] bpf: improve verification speed by not
 remarking live_read

On 30/03/2019 00:16, Alexei Starovoitov wrote:
> With large verifier speed improvement brought by the previous patch
> mark_reg_read() becomes the hottest function during verification.
> On a typical program it consumes 40% of cpu.
> mark_reg_read() walks parentage chain of registers to mark parents as LIVE_READ.
> Once the register is marked there is no need to remark it again in the future.
> Hence stop walking the chain once first LIVE_READ is seen.
> This optimization drops mark_reg_read() time from 40% of cpu to <1%
> and overall 2x improvement of verification speed.
> For some programs the longest_mark_read_walk counter improves from ~500 to ~5
>
> Signed-off-by: Alexei Starovoitov <ast@...nel.org>
Reviewed-by: Edward Cree <ecree@...arflare.com>
> ---
>  kernel/bpf/verifier.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b18512ac205e..6dfd148b58f6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1151,6 +1151,15 @@ static int mark_reg_read(struct bpf_verifier_env *env,
>  				parent->var_off.value, parent->off);
>  			return -EFAULT;
>  		}
> +		if (parent->live & REG_LIVE_READ)
> +			/* The parentage chain never changes and
> +			 * this parent was already marked as LIVE_READ.
> +			 * There is no need to keep walking the chain again and
> +			 * keep re-marking all parents as LIVE_READ.
> +			 * This case happens when the same register is read
> +			 * multiple times without writes into it in-between.
> +			 */
> +			break;
>  		/* ... then we depend on parent's value */
>  		parent->live |= REG_LIVE_READ;
>  		state = parent;