From patchwork Mon Aug 29 12:53:55 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 74912 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp1618341qga; Mon, 29 Aug 2016 05:56:26 -0700 (PDT) X-Received: by 10.98.64.93 with SMTP id n90mr32965749pfa.29.1472475385904; Mon, 29 Aug 2016 05:56:25 -0700 (PDT) Return-Path: Received: from bombadil.infradead.org (bombadil.infradead.org. [2001:1868:205::9]) by mx.google.com with ESMTPS id y5si39045364pax.43.2016.08.29.05.56.25 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 29 Aug 2016 05:56:25 -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 1beM62-0003LT-R9; Mon, 29 Aug 2016 12:55:26 +0000 Received: from mail-wm0-x233.google.com ([2a00:1450:400c:c09::233]) by bombadil.infradead.org with esmtps (Exim 4.85_2 #1 (Red Hat Linux)) id 1beM58-0002Gs-Mn for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2016 12:54:34 +0000 Received: by mail-wm0-x233.google.com with SMTP id o80so90411838wme.1 for ; Mon, 29 Aug 2016 05:54:12 -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=+O0+HX0NwDpGVfxZSTGhyq9Wj6hgU6aeYn4brzSvbKI=; b=TRYU4ilInkXYs4HSKkXKkYw0flYOZgBxBJbANR3cPcs+gwySzY5aQeOyw9//CkDsqU OUML6t8Zu3rctiJ9ay0D/rzJBlPtn7yAMRMOvvzU+DevgL5JmnaoB0oO63m4SjYVx8qI d/XL8z7ml9WeHUlY5IH/xLtvh7aNMUjqJZbCw= 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=+O0+HX0NwDpGVfxZSTGhyq9Wj6hgU6aeYn4brzSvbKI=; b=JnbKzBB2FngJMVsg2nlk+SQYD1PKY09kpJJRJgV3ts4V899D9hKIhS/AYghgU/Z/oy R/FXbbg/dkKNXwEO7gEgBPoGK7Ir4TcNkZZAjmrLGLFNmtYzoCr2NsJN7cvCNO+TEZMz I3LeSODBgmGHgh7bJ7EaaentQcM2rmJgN7cmAy8uqjEMQc80wF3KvT7tylGv2H74HrfD Fsj+b7sbcj4b/fqqlMNnalDgrYkVUFtR/neps1ODWhzP7dnhxaCldCnvG1Ix2UpsCFWE I9MXtnsr/B+ds2lnrPoOBGbLKNY3HaBUWo+YsoQi2akNomR8Bl53xBC62QVPkyE/q0Pz 3ZfA== X-Gm-Message-State: AE9vXwPcasQ7RNyXrTLB/17dlFo61gikpGcG0SC9t4WU09ivqrf7k9nkvtvCbkYiQtvppqXj X-Received: by 10.28.198.142 with SMTP id w136mr10813028wmf.30.1472475251311; Mon, 29 Aug 2016 05:54:11 -0700 (PDT) Received: from localhost.localdomain ([160.165.12.73]) by smtp.gmail.com with ESMTPSA id a3sm14656816wjw.15.2016.08.29.05.54.09 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 29 Aug 2016 05:54:10 -0700 (PDT) From: Ard Biesheuvel To: linux-arm-kernel@lists.infradead.org, linux@arm.linux.org.uk, dave.martin@arm.com Subject: [PATCH v4 3/4] ARM: kernel: sort relocation sections before allocating PLTs Date: Mon, 29 Aug 2016 13:53:55 +0100 Message-Id: <1472475236-3083-4-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_055431_143034_466EA367 X-CRM114-Status: GOOD ( 22.32 ) 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:233 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 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. Tested-by: Jongsung Kim Signed-off-by: Ard Biesheuvel --- arch/arm/kernel/module-plts.c | 98 ++++++++++++++------ 1 file changed, 69 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 6f93a905eeee..ad1b98fbcd98 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,63 @@ 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; +static bool is_zero_addend_relocation(Elf32_Addr base, const Elf32_Rel *rel) +{ + u32 *tval = (u32 *)(base + rel->r_offset); + + /* + * Do a bitwise compare on the raw addend rather than fully decoding + * the offset and doing an arithmetic comparison. + * 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. + */ + switch (ELF32_R_TYPE(rel->r_info)) { + u16 upper, lower; + + case R_ARM_THM_CALL: + case R_ARM_THM_JUMP24: + upper = __mem_to_opcode_thumb16(((u16 *)tval)[0]); + lower = __mem_to_opcode_thumb16(((u16 *)tval)[1]); + + return (upper & 0x7ff) == 0x7ff && (lower & 0x2fff) == 0x2ffe; + + case R_ARM_CALL: + case R_ARM_PC24: + case R_ARM_JUMP24: + return (__mem_to_opcode_arm(*tval) & 0xffffff) == 0xfffffe; } - return 0; + BUG(); +} + +static bool duplicate_rel(Elf32_Addr base, const Elf32_Rel *rel, int num) +{ + const Elf32_Rel *prev; + + /* + * Entries are sorted by type and symbol index. That means that, + * if a duplicate entry exists, it must be in the preceding + * slot. + */ + if (!num) + return false; + + prev = rel + num - 1; + return cmp_rel(rel + num, prev) == 0 && + is_zero_addend_relocation(base, prev); } /* Count how many PLT entries we may need */ @@ -93,18 +129,8 @@ static unsigned int count_plts(const Elf32_Sym *syms, Elf32_Addr base, { unsigned int ret = 0; const Elf32_Sym *s; - u32 mask; int i; - if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) - mask = __opcode_to_mem_thumb32(0x07ff2fff); - else - mask = __opcode_to_mem_arm(0x00ffffff); - - /* - * Sure, this is order(n^2), but it's usually short, and not - * time critical - */ for (i = 0; i < num; i++) { switch (ELF32_R_TYPE(rel[i].r_info)) { case R_ARM_CALL: @@ -123,7 +149,18 @@ static unsigned int count_plts(const Elf32_Sym *syms, Elf32_Addr base, if (s->st_shndx != SHN_UNDEF) break; - if (!duplicate_rel(base, rel, i, mask)) + /* + * 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. + */ + if (!is_zero_addend_relocation(base, rel + i) || + !duplicate_rel(base, rel, i)) ret++; } } @@ -158,7 +195,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; @@ -169,6 +206,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); }