From patchwork Thu Aug 18 10:02:43 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 74148 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp264314qga; Thu, 18 Aug 2016 03:05:24 -0700 (PDT) X-Received: by 10.98.68.1 with SMTP id r1mr2541458pfa.161.1471514724801; Thu, 18 Aug 2016 03:05:24 -0700 (PDT) Return-Path: Received: from bombadil.infradead.org (bombadil.infradead.org. [2001:1868:205::9]) by mx.google.com with ESMTPS id 23si1838625pfq.32.2016.08.18.03.05.24 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Aug 2016 03:05:24 -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 1baKBS-0001VR-My; Thu, 18 Aug 2016 10:04:22 +0000 Received: from mail-wm0-x22b.google.com ([2a00:1450:400c:c09::22b]) by bombadil.infradead.org with esmtps (Exim 4.85_2 #1 (Red Hat Linux)) id 1baKAT-00013U-Ai for linux-arm-kernel@lists.infradead.org; Thu, 18 Aug 2016 10:03:24 +0000 Received: by mail-wm0-x22b.google.com with SMTP id i5so24326729wmg.0 for ; Thu, 18 Aug 2016 03:03:00 -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=T2xaGsxpLhQPIdChIgE9Q2RInSRlWHHgKyVq4wEdSJ4=; b=ip5laX8tj0RUlEk9rIOL6ierSPoXpBkHOrpzt68VSkOmUezPJgf1PQb3IijX0gPonv +0+96md47Q//G9LM6ZJcdNHUQ9TWbcslMmDFbwpeTnAx/Kfc3VmMVMA4APRbzTEx6bj+ KZxbsZBYWHNPCWrJsHc+adqhkvwJYy4SNThFE= 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=T2xaGsxpLhQPIdChIgE9Q2RInSRlWHHgKyVq4wEdSJ4=; b=ahD/ozljJ1byUYBHTZ1URmYrZZd/KSn3XxntXI4HkakX4Q+DzlMQCSFY2FFh1JYHgl ILWLf5vsdKTuN/eNfaZJVDMafcV7hpYLqOCINk9PxMgNzgLp12zUBH4wArZAETehIDHH 3MJhrOm5FSKwNiXbr/4yYEqXAJfeid5kjSFeRwuL3wESTbytnllmLrp+zB0Ulv5JJzRK HBeRT9nocAW1KNeih4xS4vz250mS+TkfPvs7h2qD5yrP2lBZWTQSAiWCdfXsL8ghIRBa JSi+jXVwSl1gsOc0yqSdlxR0L3+mh3bj8FfTGeWf7MQ/tl8RSTK3iyEKYNdCtHsRgg17 2Riw== X-Gm-Message-State: AEkoousH4rt2TKR178Bze67NRp/mZGX4z6UqVBqv+g4Ya9Uo9U0064p7r3WmvylzncOXcSWC X-Received: by 10.194.72.226 with SMTP id g2mr1392545wjv.70.1471514579203; Thu, 18 Aug 2016 03:02:59 -0700 (PDT) Received: from localhost.localdomain (46.red-81-37-107.dynamicip.rima-tde.net. [81.37.107.46]) by smtp.gmail.com with ESMTPSA id b130sm1860450wmg.19.2016.08.18.03.02.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 18 Aug 2016 03:02:58 -0700 (PDT) From: Ard Biesheuvel To: linux-arm-kernel@lists.infradead.org, linux@arm.linux.org.uk, dave.martin@arm.com Subject: [PATCH v3 4/4] arm64: kernel: avoid brute force search on PLT generation Date: Thu, 18 Aug 2016 12:02:43 +0200 Message-Id: <1471514563-28172-5-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1471514563-28172-1-git-send-email-ard.biesheuvel@linaro.org> References: <1471514563-28172-1-git-send-email-ard.biesheuvel@linaro.org> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20160818_030321_602698_5218800A X-CRM114-Status: GOOD ( 21.00 ) 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:22b 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) 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 5b000ea64fa4..a910f1db0c14 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))