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,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 7EF52C10F05 for ; Sat, 30 Mar 2019 00:16:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 47D7C218AE for ; Sat, 30 Mar 2019 00:16:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1553904986; bh=Zr/zOER3eanxbYmjGf0Hf29Ur/gZ3kgf7gK9FLxd/JI=; h=From:To:CC:Subject:Date:In-Reply-To:References:List-ID:From; b=ljhs/No3sU3juLRrFeZePopjmDlW3kaySilFVzqY0ZhFdc915TfnqlDRDhBALxDNu 4K+VWPH7NQdcdraat5eZLPQtUPskquwU56zYEsulRG5+SrVZBFP9cAoqL3xh1RARJK 3L/SF/lUgG+xy6mU5VaxlwkLCoE5Fv+GtIFCu8O4= Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730274AbfC3AQZ convert rfc822-to-8bit (ORCPT ); Fri, 29 Mar 2019 20:16:25 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:54252 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729771AbfC3AQU (ORCPT ); Fri, 29 Mar 2019 20:16:20 -0400 Received: from pps.filterd (m0148461.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x2U0CrjC002667 for ; Fri, 29 Mar 2019 17:16:20 -0700 Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2rhwcm82f7-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Fri, 29 Mar 2019 17:16:20 -0700 Received: from mx-out.facebook.com (2620:10d:c081:10::13) by mail.thefacebook.com (2620:10d:c081:35::125) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1713.5; Fri, 29 Mar 2019 17:16:19 -0700 Received: by devbig007.ftw2.facebook.com (Postfix, from userid 572438) id F11EB760BC0; Fri, 29 Mar 2019 17:16:18 -0700 (PDT) Smtp-Origin-Hostprefix: devbig From: Alexei Starovoitov Smtp-Origin-Hostname: devbig007.ftw2.facebook.com To: CC: , , , , , Smtp-Origin-Cluster: ftw2c04 Subject: [PATCH bpf-next 3/7] bpf: improve verification speed by not remarking live_read Date: Fri, 29 Mar 2019 17:16:08 -0700 Message-ID: <20190330001612.2354959-4-ast@kernel.org> X-Mailer: git-send-email 2.20.0 In-Reply-To: <20190330001612.2354959-1-ast@kernel.org> References: <20190330001612.2354959-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-03-29_14:,, 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 --- 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; -- 2.20.0