Re: [PATCH v2 15/21] objtool: cache relocations, do less work

[Josh Poimboeuf <jpoimboe@kernel.org>]

On Mon, Sep 14, 2026 at 01:06:37PM -0700, Linus Torvalds wrote:
> Talking about "getting rid of the hashing": the instruction hashing is
> obviously a big deal judging by the hash size expansion in that other
> patch.
> 
> Do we actually look up all instructions by hash in the first place?
> From a quick glance, it looks like almost every user of "find_insn()"
> is looking for just certain *kinds* of instructions: calls, branches,
> returns, endbr.  And branch targets.
> 
> Maybe stack updates? I didn't check.
> 
> Yet we seem to hash them all - even if they are just some random
> ALU-only instruction that is in the middle of a function and never a
> target of anything and has no impact on any code flow.
> 
> So the question becomes: do we actually need to hash those
> instructions at all? Are they ever actually looked up?
> 
> I don't know this codebase at all, so maybe that's just a really
> stupid question. Feel free to look at me condescendinly, shake your
> head and say "Poor Linus has lost the plot".
> 
> [ And yes, I see that whole "next_insn_same_sec()" thing, which
> obviously *does* look up all the instructions when you iterate over
> that function, but it strikes me that using a hash table for that is a
> bit strange when the natural way to do it would be with juyst a
> "struct instruction *next" field instead.. ]
> 
> So if hashing was such a big deal that it showed up clearly on
> profiles, maybe the answer isn't just a "make the hash table larger".
> If a "next" field were to not only make the hash table much smaller,
> but also mean that next_insn_same_{func,sec}() would become a "follow
> one pointer", mayeb hashing would become rather cheaper?
> 
> Stupid? Or maybe "not completely stupid, but too painful to change"?

The find_insn() in next_insn_same_sec() is a bit odd, that was itself
part of a performance optimization, but yes, a 'next' pointer could be
used instead.  Though, IIRC, that instruction struct is the biggest
overall user of memory, and it just barely fits inside a cache line
boundary, which we do take advantage of by putting them in adjacent
blocks.

But as you alluded to, find_insn() has a lot more users beyond just
next_insn_same_sec(), like finding jump targets, alternatives, annotated
instructions, and quite a bit more.  Determining in advance which subset
of instructions need to be hashed is likely somewhere between "too
painful to change" and "not feasible" IMO.

There might be more efficient ways to structure the considerable amount
of data, like replacing "struct instruction" with "struct basic_block"
or so, but it's hard to know whether that would be a net positive.

At least the current design is a somewhat tolerable balance of
CPU/memory usage and maintainability.  Peter and I already fixed most of
the major performance issues, so I'm not overly motivated to squeeze the
last remaining juice of performance, especially if it's going to hurt
maintainability (maintainer bandwidth is also a precious resource).

-- 
Josh