From patchwork Wed Aug 17 11:59:36 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 74059 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp2473171qga; Wed, 17 Aug 2016 05:06:19 -0700 (PDT) X-Received: by 10.98.16.75 with SMTP id y72mr2525481pfi.50.1471435579264; Wed, 17 Aug 2016 05:06:19 -0700 (PDT) Return-Path: Received: from bombadil.infradead.org (bombadil.infradead.org. [2001:1868:205::9]) by mx.google.com with ESMTPS id zq10si37485823pab.103.2016.08.17.05.06.19 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 17 Aug 2016 05:06:19 -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 1bZzal-0008Bd-QU; Wed, 17 Aug 2016 12:05:07 +0000 Received: from mail-wm0-f48.google.com ([74.125.82.48]) by bombadil.infradead.org with esmtps (Exim 4.85_2 #1 (Red Hat Linux)) id 1bZzWH-00040r-Gw for linux-arm-kernel@lists.infradead.org; Wed, 17 Aug 2016 12:00:58 +0000 Received: by mail-wm0-f48.google.com with SMTP id o80so227643929wme.1 for ; Wed, 17 Aug 2016 05:00:09 -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=v5KpErqenh5pkVriPSAnMWtde8dIROT5ttAbx8TITzQ=; b=KBZzO7yJNvJ3OEKwZ4+/PDTPBd7iNW8Xk8kpN3WRb7luzdZvoogQNOIJJg5iM0bGmE Rm8s9wUFR6texXASKnrk6sHiUPs4LKXUEqjMqEAXDWOJM6lsKSGVdI/iBacnEIlXvnX/ /wU5umLM2rvluO3jykIQXxd2jFMQcyigrZolM= 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=v5KpErqenh5pkVriPSAnMWtde8dIROT5ttAbx8TITzQ=; b=HJglK7am/nfKyO7MmDMbZt9noDFVOoB6FPUMWSw5V0FOV53pVMXYkWuGeWgFPuZXQu iUmf6epEVfoGXBRhxxurcSbhJd0DsyrX5AocQ56m1R5x16xHXbmYG4xS6EydJJTb6/j2 5gwGVknmWUR4f8VtGisjJ0B55n3MYaJnmA37BLNtE4wZ4HA5RwJpQNwaN6g7CS6iX5pj DyMjZPJ6mGqgLb/8+Bv6f2F5/5wmIL9r6YNaqKyphFqmvFmQNlqJIXXXQELvTMRRK29l cH8McP/xkTWUlBriX6d4KRqWpsKTk1CHscLJt3RaoCpl02r0Pd++EdZ+9AaFgzZNWFKr Sukw== X-Gm-Message-State: AEkooutRgBiQuSgNCplVa+Wjepd47cJQbATZvFpDrEtTyd0Sk5SblW4Qe5SeeJwWDatvro9K X-Received: by 10.194.192.195 with SMTP id hi3mr40884934wjc.108.1471435207093; Wed, 17 Aug 2016 05:00:07 -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 e65sm26320844wmg.3.2016.08.17.05.00.01 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 17 Aug 2016 05:00:06 -0700 (PDT) From: Ard Biesheuvel To: linux-arm-kernel@lists.infradead.org, linux@arm.linux.org.uk, dave.martin@arm.com Subject: [PATCH v2 3/3] ARM: kernel: sort relocation sections before allocating PLTs Date: Wed, 17 Aug 2016 13:59:36 +0200 Message-Id: <1471435176-13146-4-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1471435176-13146-1-git-send-email-ard.biesheuvel@linaro.org> References: <1471435176-13146-1-git-send-email-ard.biesheuvel@linaro.org> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20160817_050030_281169_AFFFF760 X-CRM114-Status: GOOD ( 22.46 ) 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 [74.125.82.48 listed in list.dnswl.org] -0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [74.125.82.48 listed in wl.mailspike.net] -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 -0.0 RCVD_IN_MSPIKE_WL Mailspike good senders 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 The PLT allocation routines try to establish an upper bound on the number of PLT entries that will be required at relocation time, and optimize this by disregarding duplicates (i.e., PLT entries that will end up pointing to the same function). This is currently a O(n^2) algorithm, but we can greatly simplify this by - sorting the relocation section so that relocations that can use the same PLT entry will be listed adjacently, - disregard jump/call relocations with addends; these are highly unusual, for relocations against SHN_UNDEF symbols, and so we can simply allocate a PLT entry for each one we encounter, without trying to optimize away duplicates. Signed-off-by: Ard Biesheuvel --- arch/arm/kernel/module-plts.c | 108 ++++++++++++++------ 1 file changed, 79 insertions(+), 29 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 59d2fcaff7d2..7221d888b138 100644 --- a/arch/arm/kernel/module-plts.c +++ b/arch/arm/kernel/module-plts.c @@ -9,6 +9,7 @@ #include #include #include +#include #include #include @@ -63,28 +64,28 @@ u32 get_module_plt(struct module *mod, unsigned long loc, Elf32_Addr val) BUG(); } -static int duplicate_rel(Elf32_Addr base, const Elf32_Rel *rel, int num, - u32 mask) +#define cmp_3way(a,b) ((a) < (b) ? -1 : (a) > (b)) + +static int cmp_rel(const void *a, const void *b) { - u32 *loc1, *loc2; + const Elf32_Rel *x = a, *y = b; int i; - for (i = 0; i < num; i++) { - if (rel[i].r_info != rel[num].r_info) - continue; + /* sort by type and symbol index */ + i = cmp_3way(ELF32_R_TYPE(x->r_info), ELF32_R_TYPE(y->r_info)); + if (i == 0) + i = cmp_3way(ELF32_R_SYM(x->r_info), ELF32_R_SYM(y->r_info)); + return i; +} - /* - * Identical relocation types against identical symbols can - * still result in different PLT entries if the addend in the - * place is different. So resolve the target of the relocation - * to compare the values. - */ - loc1 = (u32 *)(base + rel[i].r_offset); - loc2 = (u32 *)(base + rel[num].r_offset); - if (((*loc1 ^ *loc2) & mask) == 0) - return 1; - } - return 0; +static int duplicate_rel(Elf32_Addr base, const Elf32_Rel *rel, int num) +{ + /* + * Entries are sorted by type and symbol index. That means that, + * if a duplicate entry exists, it must be in the preceding + * slot. + */ + return num > 0 && cmp_rel(rel + num, rel + num - 1) == 0; } /* Count how many PLT entries we may need */ @@ -94,11 +95,11 @@ static unsigned int count_plts(const Elf32_Sym *syms, Elf32_Addr base, unsigned int ret = 0; int i; - /* - * Sure, this is order(n^2), but it's usually short, and not - * time critical - */ for (i = 0; i < num; i++) { + u32 *tval; + s32 offset; + u32 upper, lower, sign, j1, j2; + /* * We only have to consider branch targets that resolve * to undefined symbols. This is not simply a heuristic, @@ -109,21 +110,67 @@ static unsigned int count_plts(const Elf32_Sym *syms, Elf32_Addr base, if (syms[ELF32_R_SYM(rel[i].r_info)].st_shndx != SHN_UNDEF) continue; + /* + * Jump relocations with non-zero addends against + * undefined symbols are supported by the ELF spec, but + * do not occur in practice (e.g., 'jump n bytes past + * the entry point of undefined function symbol f'). + * So we need to support them, but there is no need to + * take them into consideration when trying to optimize + * this code. So let's only check for duplicates when + * the addend is zero. + * Note that a zero-addend jump/call relocation is encoded + * taking the PC bias into account, i.e., -8 for ARM and + * -4 for Thumb2. + */ + tval = (u32 *)(base + rel[i].r_offset); + switch (ELF32_R_TYPE(rel[i].r_info)) { case R_ARM_CALL: case R_ARM_PC24: case R_ARM_JUMP24: - if (!duplicate_rel(base, rel, i, - __opcode_to_mem_arm(0x00ffffff))) + offset = (__mem_to_opcode_arm(*tval) & 0x00ffffff) << 2; + if (offset & 0x02000000) + offset -= 0x04000000; + if (offset != -8 || + !duplicate_rel(base, rel, i)) ret++; break; -#ifdef CONFIG_THUMB2_KERNEL + case R_ARM_THM_CALL: case R_ARM_THM_JUMP24: - if (!duplicate_rel(base, rel, i, - __opcode_to_mem_thumb32(0x07ff2fff))) + BUG_ON(!IS_ENABLED(CONFIG_THUMB2_KERNEL)); + + upper = __mem_to_opcode_thumb16(((u16 *)tval)[0]); + lower = __mem_to_opcode_thumb16(((u16 *)tval)[1]); + + /* + * 25 bit signed address range (Thumb-2 BL and + * B.W instructions): + * S:I1:I2:imm10:imm11:0 + * where: + * S = upper[10] = offset[24] + * I1 = ~(J1 ^ S) = offset[23] + * I2 = ~(J2 ^ S) = offset[22] + * imm10 = upper[9:0] = offset[21:12] + * imm11 = lower[10:0] = offset[11:1] + * J1 = lower[13] + * J2 = lower[11] + */ + sign = (upper >> 10) & 1; + j1 = (lower >> 13) & 1; + j2 = (lower >> 11) & 1; + offset = (sign << 24) | + ((~(j1 ^ sign) & 1) << 23) | + ((~(j2 ^ sign) & 1) << 22) | + ((upper & 0x03ff) << 12) | + ((lower & 0x07ff) << 1); + if (offset & 0x01000000) + offset -= 0x02000000; + + if (offset != -4 || + !duplicate_rel(base, rel, i)) ret++; -#endif } } return ret; @@ -157,7 +204,7 @@ int module_frob_arch_sections(Elf_Ehdr *ehdr, Elf_Shdr *sechdrs, } for (s = sechdrs + 1; s < sechdrs_end; ++s) { - const Elf32_Rel *rels = (void *)ehdr + s->sh_offset; + Elf32_Rel *rels = (void *)ehdr + s->sh_offset; int numrels = s->sh_size / sizeof(Elf32_Rel); Elf32_Shdr *dstsec = sechdrs + s->sh_info; @@ -168,6 +215,9 @@ int module_frob_arch_sections(Elf_Ehdr *ehdr, Elf_Shdr *sechdrs, if (!(dstsec->sh_flags & SHF_EXECINSTR)) continue; + /* sort by type and symbol index */ + sort(rels, numrels, sizeof(Elf32_Rel), cmp_rel, NULL); + plts += count_plts(syms, dstsec->sh_addr, rels, numrels); }