From patchwork Mon Aug 29 12:53:56 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 74913 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp1618524qga; Mon, 29 Aug 2016 05:56:52 -0700 (PDT) X-Received: by 10.66.242.166 with SMTP id wr6mr32259531pac.147.1472475412538; Mon, 29 Aug 2016 05:56:52 -0700 (PDT) Return-Path: Received: from bombadil.infradead.org (bombadil.infradead.org. [2001:1868:205::9]) by mx.google.com with ESMTPS id az10si22312347pab.236.2016.08.29.05.56.52 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 29 Aug 2016 05:56:52 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-arm-kernel-bounces+patch=linaro.org@lists.infradead.org designates 2001:1868:205::9 as permitted sender) client-ip=2001:1868:205::9; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org; spf=pass (google.com: best guess record for domain of linux-arm-kernel-bounces+patch=linaro.org@lists.infradead.org designates 2001:1868:205::9 as permitted sender) smtp.mailfrom=linux-arm-kernel-bounces+patch=linaro.org@lists.infradead.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.85_2 #1 (Red Hat Linux)) id 1beM6Q-0003tO-UR; Mon, 29 Aug 2016 12:55:50 +0000 Received: from mail-wm0-x235.google.com ([2a00:1450:400c:c09::235]) by bombadil.infradead.org with esmtps (Exim 4.85_2 #1 (Red Hat Linux)) id 1beM5D-0002H4-7V for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2016 12:54:37 +0000 Received: by mail-wm0-x235.google.com with SMTP id o80so90413296wme.1 for ; Mon, 29 Aug 2016 05:54:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=0fhc6PdVfsljqtcjczmLO4tv+wft36sJgyz7nx0ielE=; b=bs5/RtET+PLEDCEVPw1Zr/pKj5Qwkct8N8PB0blDUC1C3yRifm2xEQ+d4iTCz2dABi PW5YSf26iwtiidaNDmIBlZRHeSjdv6uLr/bAHGVikQtaGp5zEgGpZNEiukOr4Ce3R530 4MbPFBqcpyjw8iN0EZb0uk8R+I4wzCoY0mWY0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=0fhc6PdVfsljqtcjczmLO4tv+wft36sJgyz7nx0ielE=; b=VXttwxEL9+XHxsvzgEbxKPKGhA6Wnxhexymjso1domdRjBB5UiyBVCSs1JP6wg2e1i Cw08bM/pyD4eX5RI0LfwoHR5lr+FhrhkOpPYn7pGuawlD+ktTAZOsLio8XNzWPDXR+PQ 3Mu3sxh+PIsLTv8e+J/qvRwtVsw3o752UvM+iYzo5G2pP4eD8GAMi+y5GLbNFXg/NSia sStUtyvjnjXXktPJdsQCJ8KyCxYFRDS//l3WgGhZt2/Jdj4CdhAsFIvoCVVEda2XmdSj MnfL7s8rcfI+2awMF8nLpTNXEhSG2m3Jy1QOkw1CaaZNQZm9J5nDNx/C2AtnLr2lagur OXeg== X-Gm-Message-State: AE9vXwPoBqd6k0MwIalXzVS2USkmraPx+KkwISE28a/j72mIwSbtZsEsd5iO2mOlzTC5vGNB X-Received: by 10.194.63.39 with SMTP id d7mr14912431wjs.13.1472475253405; Mon, 29 Aug 2016 05:54:13 -0700 (PDT) Received: from localhost.localdomain ([160.165.12.73]) by smtp.gmail.com with ESMTPSA id a3sm14656816wjw.15.2016.08.29.05.54.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 29 Aug 2016 05:54:12 -0700 (PDT) From: Ard Biesheuvel To: linux-arm-kernel@lists.infradead.org, linux@arm.linux.org.uk, dave.martin@arm.com Subject: [PATCH v4 4/4] ARM: kernel: avoid brute force search on PLT generation Date: Mon, 29 Aug 2016 13:53:56 +0100 Message-Id: <1472475236-3083-5-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1472475236-3083-1-git-send-email-ard.biesheuvel@linaro.org> References: <1472475236-3083-1-git-send-email-ard.biesheuvel@linaro.org> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20160829_055435_535384_91FA2D6C X-CRM114-Status: GOOD ( 21.05 ) X-Spam-Score: -2.7 (--) X-Spam-Report: SpamAssassin version 3.4.0 on bombadil.infradead.org summary: Content analysis details: (-2.7 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.7 RCVD_IN_DNSWL_LOW RBL: Sender listed at http://www.dnswl.org/, low trust [2a00:1450:400c:c09:0:0:0:235 listed in] [list.dnswl.org] -0.0 SPF_PASS SPF: sender matches SPF record -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: namhyung.kim@lge.com, youngho.shin@lge.com, arnd@arndb.de, Ard Biesheuvel , neidhard.kim@lge.com, chanho.min@lge.com MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patch=linaro.org@lists.infradead.org Given that we now sort the relocation sections in a way that guarantees that entries that can share a single PLT entry end up adjacently, there is no a longer a need to go over the entire list to look for an existing entry that matches our jump target. If such a match exists, it was the last one to be emitted, so we can simply check the preceding slot. Note that this will still work correctly in the [theoretical] presence of call/jump relocations against SHN_UNDEF symbols with non-zero addends, although not optimally. Since the relocations are presented in the same order that we checked them for duplicates, any duplicates that we failed to spot the first time around will be accounted for in the PLT allocation so there is guaranteed to be sufficient space for them when actually emitting the PLT. For instance, the following sequence of relocations: 000004d8 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 000004fc 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 0000050e 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 00000520 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 00000532 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 00000544 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 00000556 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 00000568 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 0000057a 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 0000058c 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 0000059e 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 000005b0 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 000005c2 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null 000005d4 00058b0a R_ARM_THM_CALL 00000000 warn_slowpath_null may result in several PLT entries to be allocated, and also emitted, if any of the entries in the middle refer to a Place that contains a non-zero addend (i.e., one for all the preceding zero-addend relocations, one for all the following zero-addend relocations, and one for the non-zero addend relocation itself) Tested-by: Jongsung Kim Signed-off-by: Ard Biesheuvel --- arch/arm/kernel/module-plts.c | 60 +++++++++++--------- 1 file changed, 32 insertions(+), 28 deletions(-) -- 2.7.4 _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel diff --git a/arch/arm/kernel/module-plts.c b/arch/arm/kernel/module-plts.c index ad1b98fbcd98..3a5cba90c971 100644 --- a/arch/arm/kernel/module-plts.c +++ b/arch/arm/kernel/module-plts.c @@ -33,35 +33,39 @@ struct plt_entries { u32 get_module_plt(struct module *mod, unsigned long loc, Elf32_Addr val) { - struct plt_entries *plt, *plt_end; - int c; - - plt = (void *)mod->arch.plt->sh_addr; - plt_end = (void *)plt + mod->arch.plt->sh_size; - - /* Look for an existing entry pointing to 'val' */ - for (c = mod->arch.plt_count; plt < plt_end; c -= PLT_ENT_COUNT, plt++) { - int i; - - if (!c) { - /* Populate a new set of entries */ - *plt = (struct plt_entries){ - { [0 ... PLT_ENT_COUNT - 1] = PLT_ENT_LDR, }, - { val, } - }; - mod->arch.plt_count++; - return (u32)plt->ldr; - } - for (i = 0; i < PLT_ENT_COUNT; i++) { - if (!plt->lit[i]) { - plt->lit[i] = val; - mod->arch.plt_count++; - } - if (plt->lit[i] == val) - return (u32)&plt->ldr[i]; - } + struct plt_entries *plt = (struct plt_entries *)mod->arch.plt->sh_addr; + int idx = 0; + + /* + * Look for an existing entry pointing to 'val'. Given that the + * relocations are sorted, this will be the last entry we allocated. + * (if one exists). + */ + if (mod->arch.plt_count > 0) { + plt += (mod->arch.plt_count - 1) / PLT_ENT_COUNT; + idx = (mod->arch.plt_count - 1) % PLT_ENT_COUNT; + + if (plt->lit[idx] == val) + return (u32)&plt->ldr[idx]; + + idx = (idx + 1) % PLT_ENT_COUNT; + if (!idx) + plt++; } - BUG(); + + mod->arch.plt_count++; + BUG_ON(mod->arch.plt_count * PLT_ENT_SIZE > mod->arch.plt->sh_size); + + if (!idx) + /* Populate a new set of entries */ + *plt = (struct plt_entries){ + { [0 ... PLT_ENT_COUNT - 1] = PLT_ENT_LDR, }, + { val, } + }; + else + plt->lit[idx] = val; + + return (u32)&plt->ldr[idx]; } #define cmp_3way(a,b) ((a) < (b) ? -1 : (a) > (b))