From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.1 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 22FF1C43381 for ; Tue, 2 Apr 2019 04:28:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id E8BA2206B8 for ; Tue, 2 Apr 2019 04:28:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1554179282; bh=6OxfhUdzNbFq/NNCDxt9PIvjUX4E8NSzavuvun4zzUo=; h=From:To:CC:Subject:Date:In-Reply-To:References:List-ID:From; b=iAJGVnmHitBgH7ZEB30U8jJ+e6GadTO6n5Nqo7et1YO6WZak66K6xW2Yj++nDYs8c p+0qxymitoE6l9vBdpLRW5080DZx4UHCm58FylWYQSQjc/FEPH3/qLqq/IC/JKww4a 6Pw8372bzx5ZnDiERbry/wln9EgcwsxzHz2ElB14= Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728849AbfDBE2A convert rfc822-to-8bit (ORCPT ); Tue, 2 Apr 2019 00:28:00 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:40036 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1728824AbfDBE16 (ORCPT ); Tue, 2 Apr 2019 00:27:58 -0400 Received: from pps.filterd (m0001303.ppops.net [127.0.0.1]) by m0001303.ppops.net (8.16.0.27/8.16.0.27) with SMTP id x324R4QW020328 for ; Mon, 1 Apr 2019 21:27:57 -0700 Received: from maileast.thefacebook.com ([199.201.65.23]) by m0001303.ppops.net with ESMTP id 2rkug60v3j-7 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Mon, 01 Apr 2019 21:27:57 -0700 Received: from mx-out.facebook.com (2620:10d:c0a1:3::13) by mail.thefacebook.com (2620:10d:c021:18::176) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1713.5; Mon, 1 Apr 2019 21:27:56 -0700 Received: by devbig007.ftw2.facebook.com (Postfix, from userid 572438) id AD004760E11; Mon, 1 Apr 2019 21:27:55 -0700 (PDT) Smtp-Origin-Hostprefix: devbig From: Alexei Starovoitov Smtp-Origin-Hostname: devbig007.ftw2.facebook.com To: CC: , , , , , Smtp-Origin-Cluster: ftw2c04 Subject: [PATCH v2 bpf-next 03/10] bpf: improve verification speed by not remarking live_read Date: Mon, 1 Apr 2019 21:27:42 -0700 Message-ID: <20190402042749.3670015-4-ast@kernel.org> X-Mailer: git-send-email 2.20.0 In-Reply-To: <20190402042749.3670015-1-ast@kernel.org> References: <20190402042749.3670015-1-ast@kernel.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8BIT X-FB-Internal: Safe Content-Type: text/plain X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-04-02_02:,, signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org 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 Reviewed-by: Jakub Kicinski Reviewed-by: Edward Cree --- kernel/bpf/verifier.c | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index a636db4a7a4e..94cf6efc5df6 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; -- 2.20.0