linux-kernel - [RFC][PATCH 14/16] objtool: Optimize find_rela_by_dest

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20200312135042.229372998@infradead.org>
Date:   Thu, 12 Mar 2020 14:41:21 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     tglx@...utronix.de, jpoimboe@...hat.com
Cc:     linux-kernel@...r.kernel.org, x86@...nel.org, peterz@...radead.org
Subject: [RFC][PATCH 14/16] objtool: Optimize find_rela_by_dest_range()

Perf shows there is significant time in find_rela_by_dest(); this is
because we have to iterate the address space per byte, looking for
relocation entries.

Optimize this by reducing the address space granularity.

This reduces objtool on vmlinux.o runtime from 4.8 to 4.4 seconds.

Signed-off-by: Peter Zijlstra (Intel) <peterz@...radead.org>
---
 tools/objtool/elf.c |   15 +++++++++++----
 tools/objtool/elf.h |   11 ++++++++++-
 2 files changed, 21 insertions(+), 5 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -204,7 +204,7 @@ struct symbol *find_symbol_by_name(struc
 struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
 				     unsigned int len)
 {
-	struct rela *rela;
+	struct rela *rela, *r = NULL;
 	unsigned long o;
 
 	if (!sec->rela)
@@ -212,12 +212,19 @@ struct rela *find_rela_by_dest_range(str
 
 	sec = sec->rela;
 
-	for (o = offset; o < offset + len; o++) {
+	for (o = offset & RELA_STRIDE_MASK; o < offset + len; o += RELA_STRIDE) {
 		hash_for_each_possible(sec->elf->rela_hash, rela, hash,
 				       __rela_hash(o, sec->idx)) {
-			if (rela->sec == sec && rela->offset == o)
-				return rela;
+			if (rela->sec != sec)
+				continue;
+
+			if (rela->offset >= offset && rela->offset < offset + len) {
+				if (!r || rela->offset < r->offset)
+					r = rela;
+			}
 		}
+		if (r)
+			return r;
 	}
 
 	return NULL;
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -86,9 +86,18 @@ struct elf {
 	DECLARE_HASHTABLE(rela_hash, 20);
 };
 
+#define RELA_STRIDE_BITS	4
+#define RELA_STRIDE		(1UL << RELA_STRIDE_BITS)
+#define RELA_STRIDE_MASK	(~(RELA_STRIDE - 1))
+
 static inline u32 __rela_hash(unsigned long offset, int idx)
 {
-	u32 ol = offset, oh = offset >> 32;
+	u32 ol, oh;
+
+	offset &= RELA_STRIDE_MASK;
+
+	ol = offset;
+	oh = offset >> 32;
 
 	__jhash_mix(ol, oh, idx);