Re: [PATCH v3 15/20] objtool: cache relocations, do less work, eliminate relocation hash

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

On Mon, Sep 21, 2026 at 09:16:21PM -0700, Josh Poimboeuf wrote:
> On Thu, Sep 17, 2026 at 05:06:25PM +0100, Lorenzo Stoakes (ARM) wrote:
> > This relies upon the entries within a section being sorted, which is the
> > case for all sections supplied to objtool by the link step during the
> > kernel build.
>
> This is wrong (or at least actively misleading).  Objtool doesn't *only*
> run on linked objects.  In some configs it runs on individual .o files.
> And GCC doesn't sort relocs:
>
>   Relocation section '.rela.text' at offset 0xc0d0 contains 724 entries:
>       Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
>       ...
>   0000000000005c50  0000009000000004 R_X86_64_PLT32         0000000000000000 _raw_spin_lock - 4
>   0000000000005c65  0000009100000004 R_X86_64_PLT32         0000000000000000 _raw_spin_unlock - 4
>   0000000000005c6d  0000019f00000004 R_X86_64_PLT32         0000000000000000 put_files_struct - 4
>   000000000000004d  0000008f00000004 R_X86_64_PLT32         0000000000000000 __x86_return_thunk - 4
>   0000000000000075  0000008f00000004 R_X86_64_PLT32         0000000000000000 __x86_return_thunk - 4
>   00000000000000cd  0000008f00000004 R_X86_64_PLT32         0000000000000000 __x86_return_thunk - 4
>
> (JMP target relocations are emitted in a second pass, for whatever
> reason)
>
> So the hash may actually be needed as a fallback after all.  Or some
> other scheme.

Ack, that's fair enough.

Definitely need something that isn't the linear scan as a truly worst case can
be horrible.

I think the hash can be avoided though, Do the read_relocs() without ordering,
track whether things are in order, on decode if sorted then just read from
relocs[], if not can allocate an order[] array and qsort() and build the index
over that.

So O(n lg n) at that point, but avoids bothering to sort for anything not looked
up, works similarly for added sections.

So still avoids all of the hash stuff, but efficient when things are actually
out of order.

>
> Either way it's overkill to have more than a single fallback.  No second
> fallback for "just in case".  Attempting to search an unhashed section
> (DWARF) can just be a fatal error instead of the "just in case"
> WARN+linear fallback thing.

Honestly this is what I instinctively preferred, but objtool is not my realm so
I worried there'd be some odd outlier thing that it'd somehow break!

>
> > @@ -1168,19 +1286,26 @@ static int read_relocs(struct elf *elf)
> >  				return -1;
> >  			}
> >
> > -			elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
> >  			set_sym_next_reloc(reloc, sym->relocs);
> >  			sym->relocs = reloc;
> >
> >  			nr_reloc++;
> >  		}
> >  		max_reloc = max(max_reloc, nr_reloc);
> > +
> > +		/* DWARF relocs are never looked up, so are not worth indexing. */
> > +		if (is_dwarf_section(rsec->base))
> > +			continue;
>
> This DWARF reloc skipping is a standalone improvement, can you split
> this out to another patch?

Ack will do!

>
> --
> Josh

--
Cheers, Lorenzo