Re: [PATCH v5 07/11] objtool: cache relocations, do less work, eliminate relocation hash

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

On Wed, Nov 11, 2026 at 09:45:28PM -0800, Josh Poimboeuf wrote:
> On Wed, Nov 04, 2026 at 06:20:25PM +0000, Lorenzo Stoakes (ARM) wrote:
> > Instruction relocations are looked up by destination in objtool via a hash
> > which is keyed on a 16-byte (OFFSET_STRIDE) window within the section being
> > walked.
> >
> > It iterates through each 16-byte window, looking up relocations over
> > several passes, before moving on to the next 16-byte window, caching only
> > when a relocation is not found saving further lookups in this case.
> >
> > Improve upon this by introducing a per-section relocation cache storing the
> > first relocation at or after each 64-byte window of data (an empirically
> > determined index range), indexed by chunk.
> >
> > The lookup is implemented an array lookup and touches no shared state, so
> > can be used from multiple threads.
> >
> > The index runs over the relocations in offset order. Usually this is how
> > they are input, however if not, each section is sorted once, storing
> > their offsets in reloc_order[].
> >
> > This is done lazily on lookup, so nothing pays the cost that doesn't have
> > to, and if everything is sorted nothing does.
> >
> > The output of objtool before and after this change was confirmed to be
> > byte-for-byte identical both for x86_64 defconfig and allmodconfig with
> > gcc and clang.
> >
> > objtool on the gcc allmodconfig vmlinux.o goes from 10.5s to 9.0s, clang
> > from 9.8s to 8.3s and gcc defconfig from 2.08s to 1.79s, with peak memory
> > down ~90 MiB on allmodconfig.
> >
> > Similar performance was also noted on a worst case scenario for unsorted
> > input (gcc but lld for linking), which confirms that the sorting mechanism
> > works correctly with little overhead.
> >
> > 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 defconfig, touch mm/vma.c, gcc        8.3s     8.2s    -0.14s (-2%)
> >   x86 defconfig, touch mm/vma.c, clang      7.6s     7.3s    -0.25s (-3%)
> >   x86 defconfig, clean, gcc                28.9s    28.6s    -0.22s (-1%)
> >   x86 defconfig, clean, clang              29.4s    29.1s    -0.28s (-1%)
> >   x86 allmodconfig, touch mm/vma.c, gcc    29.4s    28.0s     -1.4s (-5%)
> >   x86 allmodconfig, touch mm/vma.c, clang  27.9s    26.2s     -1.7s (-6%)
> >
> > Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
> > ---
> >  tools/objtool/elf.c                 | 280 ++++++++++++++++++++++++++++--------
> >  tools/objtool/include/objtool/elf.h |  10 +-
> >  2 files changed, 221 insertions(+), 69 deletions(-)
>
> Urgh... so the closer I looked, the more this patch revealed itself to
> be an AI slop mess.  So I ended up completely rewriting it.

Well I took time to understand, cleanup and make the patches as good as I
could (you should have seen what it came up with originally etc.), but I
fully get it and sorry about that! :)

>
> You can go ahead and drop all the objtool patches from this series, I
> will repost them after some more cleanups.

From my side will obviously drop them on any respin!

>
> And I'm dropping patch 9 altogether, it's just not worth the pain...

Sure, again understood, sorry for subjecting you to it :P there's a win
there but obviously it's all rather a trade-off!

--
Cheers, Lorenzo