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=-5.5 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,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 45EEBC433E0 for ; Tue, 23 Jun 2020 16:14:11 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (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 113A42076E for ; Tue, 23 Jun 2020 16:14:10 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="HpdcBjwD"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="o8Oqg6WA" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 113A42076E 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+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=merlin.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=rVmMgjvFLuFXK599Tl4fE00iFxlG5yl20R+pLSxF4/c=; b=HpdcBjwDRtWGwUBcYztJnHcYd /YCf0rTPiDIAefvpR3X5SrMjhadKigJGj4ix7zJKsKjsjLhMwp6Zzqq+7g5IrwvV7s6Qzk2u8qEaE A08oc9s+idOLLoZXq/LPeuzywbK9r9iuKLxOoGncn3zzAYXkV+64QvD2R2MorMf/pkuiPYxUNBybz hOhiScpfdnseCErxYyeLhQETcey1RowHR7eLo7m95D2eVDbFytjwIEe0bpk8k3UEwDVHa3WiZBQeD 7JclmG2L5BvzatAsOxmJXCTvpiFKhhD7jAGBRxXemRcEt8kQkUPHVUNz9AyTongsYdlDDc7WM+SQi 9++JXj9Qw==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jnlX3-0006Ff-Cw; Tue, 23 Jun 2020 16:12:21 +0000 Received: from mail.kernel.org ([198.145.29.99]) by merlin.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jnlX0-0006En-5a for linux-arm-kernel@lists.infradead.org; Tue, 23 Jun 2020 16:12:19 +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 3EFD32081A; Tue, 23 Jun 2020 16:12:16 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1592928737; bh=6nRc1jGM9JfCbm9AMXUpZEjUTEOQfLi5Qg96RQgjxSc=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=o8Oqg6WAtj5VPOvslTDqt6BUwgSHZhkB+0DXnYfwb0L7fa3cjFCiQh5Q+sskZ8pwE k0kfdvRZnaMLmdpKizu9J6N89rBIkUoFPPhz7IoF0M+AgnbBu8/K97R5W3kC1s7kvv kV36xNka75qLN9GjoaL6rjcFhg43GAlUT9HqwOVc= Date: Tue, 23 Jun 2020 17:12:13 +0100 From: Will Deacon To: Saravana Kannan Subject: Re: [PATCH v2] arm64/module: Optimize module load time by optimizing PLT counting Message-ID: <20200623161212.GA4819@willie-the-truck> References: <20200623011803.91232-1-saravanak@google.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20200623011803.91232-1-saravanak@google.com> User-Agent: Mutt/1.10.1 (2018-07-13) 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+linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Mon, Jun 22, 2020 at 06:18:02PM -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. > > 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, these were the results for a few downstream modules: > > Module Size (MB) > wlan 14 > video codec 3.8 > drm 1.8 > IPA 2.5 > audio 1.2 > gpu 1.8 > > Without this patch: > Module Number of entries sorted Module load time (ms) > wlan 243739 283 > video codec 74029 138 > drm 53837 67 > IPA 42800 90 > audio 21326 27 > gpu 20967 32 > > Total time to load all these module: 637 ms > > With this patch: > Module Number of entries sorted Module load time (ms) > wlan 22454 61 > video codec 10150 47 > drm 13014 40 > IPA 8097 63 > audio 4606 16 > gpu 6527 20 > > Total time to load all these modules: 247 > > Time saved during boot for just these 6 modules: 390 ms > > Cc: Ard Biesheuvel > Signed-off-by: Saravana Kannan > --- > > v1 -> v2: > - Provided more details in the commit text > - Pulled in Will's comments on the coding style > - Pulled in Ard's suggestion about skipping jumps with the same section > index (parts of Will's suggested code) > > arch/arm64/kernel/module-plts.c | 46 ++++++++++++++++++++++++++++++--- > 1 file changed, 43 insertions(+), 3 deletions(-) Nice, it looks like you were more-or-less able to use my suggestion directly! Commit message looks much better to, so: Acked-by: Will Deacon Catalin can pick this up when he starts queuing patches for 5.9. Cheers, Will _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel