Re: [PATCH v5 07/11] objtool: cache relocations, do less work, eliminate relocation hash
From: Josh Poimboeuf
Date: Thu Nov 12 2026 - 00:45:47 EST
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@xxxxxxxxxx>
> ---
> 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.
You can go ahead and drop all the objtool patches from this series, I
will repost them after some more cleanups.
And I'm dropping patch 9 altogether, it's just not worth the pain...
--
Josh