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%)
Assisted-by: LLM
Signed-off-by: Lorenzo Stoakes (ARM) <[email protected]>
---
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 464f6c9d9ff0..62a3e1d4e9e5 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;
}
@@ -403,6 +413,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.
@@ -414,6 +462,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;
@@ -474,7 +525,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++;
}
@@ -4802,6 +4853,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.55.0
