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=-8.5 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE, SPF_PASS,URIBL_BLOCKED,USER_AGENT_SANE_1 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 B2D4FC433DF for ; Tue, 16 Jun 2020 21:40:13 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 754B3208D5 for ; Tue, 16 Jun 2020 21:40:13 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="br82kwVd"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="lZ+vVY98" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 754B3208D5 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References: Message-ID:Subject:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=+k+ShpnBjT6hGO8mgkxKT6/Om2RgC9NFp3PAi3ukoZk=; b=br82kwVdyqcMaD JPNrS8P/AodN3GyzGZ0L3y56wybkyXbbIRGCNd7L/iy+1U4KQ/Cwzok8iqJgfxekbeWICUcokJrHZ jbByUw2X8otTiEcGOB+0W9QwffYUhJnjoUK8jpyC7NwSSo8rUrpEw//mIMTUwgI9/YSwZBgHBG6NK VJiXNdgpwwWFlCdCF0Bip2i3Z/i+QPwppKNkBEoxmlVm7wbyqZVBbP+0xiCa98LftJnvrJfwfpzvs S+M3TfAEz3daAHEeNEH65SgMjUWQBNWx7wckgLq7W470GSv8DZUvjpMvDZlgdQHgVtlgiesfMfmq5 z0Px7fqqTbqgd2nNdQww==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jlJJL-0003Cz-2Q; Tue, 16 Jun 2020 21:40:03 +0000 Received: from mail.kernel.org ([198.145.29.99]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jlJJG-0003CD-CP for linux-arm-kernel@lists.infradead.org; Tue, 16 Jun 2020 21:39:59 +0000 Received: from willie-the-truck (236.31.169.217.in-addr.arpa [217.169.31.236]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id D9A742082E; Tue, 16 Jun 2020 21:39:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1592343598; bh=NAcC0C5+lhAkJJBBDMO+UHb5TJKRWin2TviSHE2JPPM=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=lZ+vVY98S3MdQSrzT7nf8/jg2P0oOocyAto8BzVR96Ti+4lwAl7q/9m+10hINfM9u LrF0pCBZabIwXnZHACZ+2Hwcofw+zdq3R4f/o620KS7tOyZp+Iwbzcy/Da5x6QIXND 46h54xMlmpCise5E7WEG12r2zcRmfOKR8Uy6w4fg= Date: Tue, 16 Jun 2020 22:39:53 +0100 From: Will Deacon To: Saravana Kannan Subject: Re: [PATCH v1] arm64/module: Optimize module load time by optimizing PLT counting Message-ID: <20200616213953.GA2561@willie-the-truck> References: <20200605222257.44882-1-saravanak@google.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20200605222257.44882-1-saravanak@google.com> User-Agent: Mutt/1.10.1 (2018-07-13) X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200616_143958_455038_C8DB2178 X-CRM114-Status: GOOD ( 24.75 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Catalin Marinas , kernel-team@android.com, linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Fri, Jun 05, 2020 at 03:22:57PM -0700, Saravana Kannan wrote: > When loading a module, module_frob_arch_sections() tries to figure out > the number of PLTs that'll be needed to handle all the RELAs. While > doing this, it tries to dedupe PLT allocations for multiple > R_AARCH64_CALL26 relocations to the same symbol. It does the same for > R_AARCH64_JUMP26 relocations too. > > To make checks for duplicates easier/faster, it sorts the relocation > list by type, symbol and addend. That way, to check for a duplicate > relocation, it just needs to compare with the previous entry. > > However, sorting the entire relocation array is unnecessary and > expensive (O(n log n)) because there are a lot of other relocation types > that don't need deduping or can't be deduped. > > So this commit partitions the array into entries that need deduping and > those that don't. And then sorts just the part that needs deduping. And > when CONFIG_RANDOMIZE_BASE is disabled, the sorting is skipped entirely > because PLTs are not allocated for R_AARCH64_CALL26 and R_AARCH64_JUMP26 > if it's disabled. > > This gives significant reduction in module load time for modules with > large number of relocations with no measurable impact on modules with a > small number of relocations. In my test setup with CONFIG_RANDOMIZE_BASE > enabled, the load time for one module went down from 268ms to 100ms. > Another module went down from 143ms to 83ms. Whilst I can see that's a significant relative saving, what proportion of actual boot time are we talking about here? It would be interesting to know if there are bigger potential savings elsewhere. > This commit also disables the sorting if CONFIG_RANDOMIZE_BASE is > disabled because it looks like PLTs are not allocated for > R_AARCH64_CALL26 and R_AARCH64_JUMP26 if it's disabled. > > Cc: Ard Biesheuvel > Signed-off-by: Saravana Kannan > --- > arch/arm64/kernel/module-plts.c | 37 ++++++++++++++++++++++++++++++++- > 1 file changed, 36 insertions(+), 1 deletion(-) > > diff --git a/arch/arm64/kernel/module-plts.c b/arch/arm64/kernel/module-plts.c > index 65b08a74aec6..bf5118b3b828 100644 > --- a/arch/arm64/kernel/module-plts.c > +++ b/arch/arm64/kernel/module-plts.c > @@ -253,6 +253,36 @@ static unsigned int count_plts(Elf64_Sym *syms, Elf64_Rela *rela, int num, > return ret; > } > > +static bool rela_needs_dedup(Elf64_Rela *rela) > +{ > + return ELF64_R_TYPE(rela->r_info) == R_AARCH64_JUMP26 > + || ELF64_R_TYPE(rela->r_info) == R_AARCH64_CALL26; > +} Does this handle A53 erratum 843419 correctly? I'm worried that we skip the ADRP PLTs there. > + > +/* Group the CALL26/JUMP26 relas toward the beginning of the array. */ > +static int partition_dedup_relas(Elf64_Rela *rela, int numrels) > +{ > + int i = 0, j = numrels - 1; > + Elf64_Rela t; > + > + while (i < j) { > + while (rela_needs_dedup(rela + i) && i < j) > + i++; > + while (!rela_needs_dedup(rela + j) && i < j) > + j--; > + if (i < j) { > + t = *(rela + j); > + *(rela + j) = *(rela + i); > + *(rela + i) = t; > + } > + } This is very hard to read and I think some of the 'i < j' comparisons are redundant. Would it make more sense to assign a temporary rather than post-inc/decrement and recheck? Will _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel