[PATCH v5 08/11] objtool: size the instruction hash to the text

["Lorenzo Stoakes (ARM)" <ljs@kernel.org>]

The instruction hash is a fixed 2^20 buckets, which for an x86-64
allmodconfig vmlinux.o of ~16 million instructions leaves find_insn()
walking chains of four or more entries.

Size it by the amount of text to be decoded instead, at one bucket per
OFFSET_STRIDE window, as sec_offset_hash() keys on those and anything
finer would sit empty.

This gives 2^20 buckets (8 MiB) for a defconfig vmlinux.o and 2^22 (32 MiB)
for allmodconfig, so it is not an egregious use of memory.

The output of objtool before and after this change was confirmed to be
byte-for-byte identical for x86_64 defconfig and allmodconfig.

On a 128-thread machine, objtool on the gcc allmodconfig vmlinux.o goes
from 9.0s to 6.8s. A defconfig vmlinux.o already had 2^20 buckets and is
unchanged.

objtool on vmlinux.o is on the serial tail of every build that links
vmlinux, no-op builds are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 allmodconfig, touch mm/vma.c, gcc    28.0s    25.7s     -2.4s (-8%)
  x86 allmodconfig, touch mm/vma.c, clang  26.2s    24.1s     -2.0s (-8%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 tools/objtool/check.c                   | 58 +++++++++++++++++++++++++++++++--
 tools/objtool/include/objtool/objtool.h |  3 +-
 tools/objtool/objtool.c                 |  1 -
 3 files changed, 58 insertions(+), 4 deletions(-)

diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 931c5c412f15..97250aa36100 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -38,12 +38,22 @@ struct disas_context *objtool_disas_ctx;
 
 size_t sym_name_max_len;
 
+static struct hlist_head *insn_hash_head(struct objtool_file *file,
+					 struct section *sec, unsigned long offset)
+{
+	/* Determine instruction hash based on section index and offset. */
+	const u32 sec_hash = sec_offset_hash(sec, offset);
+	const u32 hash = hash_min(sec_hash, file->insn_hash_bits);
+
+	return &file->insn_hash[hash];
+}
+
 struct instruction *find_insn(struct objtool_file *file,
 			      struct section *sec, unsigned long offset)
 {
 	struct instruction *insn;
 
-	hash_for_each_possible(file->insn_hash, insn, hash, sec_offset_hash(sec, offset)) {
+	hlist_for_each_entry(insn, insn_hash_head(file, sec, offset), hash) {
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 	}
@@ -404,6 +414,44 @@ static void *cfi_hash_alloc(unsigned long size)
 static unsigned long nr_insns;
 static unsigned long nr_insns_visited;
 
+/*
+ * sec_offset_hash() keys on OFFSET_STRIDE windows, so the instructions of a
+ * window share a chain and buckets beyond one per window would sit empty.
+ */
+#define INSN_HASH_BYTES_PER_BUCKET	OFFSET_STRIDE
+#define INSN_HASH_MIN_BITS		10
+
+static unsigned long total_text_size(struct objtool_file *file)
+{
+	unsigned long size = 0;
+	struct section *sec;
+
+	for_each_sec(file->elf, sec)
+		if (is_text_sec(sec))
+			size += sec_size(sec);
+
+	return size;
+}
+
+static int alloc_insn_hash(struct objtool_file *file, unsigned long text_size)
+{
+	const unsigned long nr_buckets = text_size / INSN_HASH_BYTES_PER_BUCKET;
+	const int bits = ilog2(nr_buckets);
+
+	file->insn_hash_bits = max(INSN_HASH_MIN_BITS, bits);
+	file->insn_hash = calloc(1UL << file->insn_hash_bits,
+				 sizeof(*file->insn_hash));
+	if (!file->insn_hash) {
+		ERROR_GLIBC("calloc");
+		return -1;
+	}
+
+	if (opts.stats)
+		printf("insn_hash_bits: %d\n", file->insn_hash_bits);
+
+	return 0;
+}
+
 /*
  * Call the arch-specific instruction decoder for all the instructions and add
  * them to the global instruction list.
@@ -415,6 +463,9 @@ static int decode_instructions(struct objtool_file *file)
 	unsigned long offset;
 	struct instruction *insn;
 
+	if (alloc_insn_hash(file, total_text_size(file)))
+		return -1;
+
 	for_each_sec(file->elf, sec) {
 		struct instruction *insns = NULL;
 		u8 prev_len = 0;
@@ -475,7 +526,7 @@ static int decode_instructions(struct objtool_file *file)
 			if (insn->type == INSN_BUG)
 				insn->dead_end = true;
 
-			hash_add(file->insn_hash, &insn->hash, sec_offset_hash(sec, insn->offset));
+			hlist_add_head(&insn->hash, insn_hash_head(file, sec, insn->offset));
 			nr_insns++;
 		}
 
@@ -4803,6 +4854,9 @@ void free_insns(struct objtool_file *file)
 
 	for (chunk = chunks; chunk; chunk = chunk->next)
 		free(chunk->addr);
+
+	free(file->insn_hash);
+	file->insn_hash = NULL;
 }
 
 const char *objtool_disas_insn(struct instruction *insn)
diff --git a/tools/objtool/include/objtool/objtool.h b/tools/objtool/include/objtool/objtool.h
index 6dc12a59ad00..79fe82b7397e 100644
--- a/tools/objtool/include/objtool/objtool.h
+++ b/tools/objtool/include/objtool/objtool.h
@@ -21,7 +21,8 @@ struct pv_state {
 
 struct objtool_file {
 	struct elf *elf;
-	DECLARE_HASHTABLE(insn_hash, 20);
+	struct hlist_head *insn_hash;
+	int insn_hash_bits;
 	struct list_head retpoline_call_list;
 	struct list_head return_thunk_list;
 	struct list_head static_call_list;
diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c
index a4e139dee7e9..71e048f8582a 100644
--- a/tools/objtool/objtool.c
+++ b/tools/objtool/objtool.c
@@ -29,7 +29,6 @@ struct objtool_file *objtool_open_read(const char *filename)
 	if (!file.elf)
 		return NULL;
 
-	hash_init(file.insn_hash);
 	INIT_LIST_HEAD(&file.retpoline_call_list);
 	INIT_LIST_HEAD(&file.return_thunk_list);
 	INIT_LIST_HEAD(&file.static_call_list);

-- 
2.56.0