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

[Lorenzo Stoakes (ARM)]

On Mon, Sep 14, 2026 at 12:44:13PM -0700, Josh Poimboeuf wrote:
> On Mon, Sep 14, 2026 at 10:22:14AM +0100, Lorenzo Stoakes (ARM) wrote:
> > +static struct reloc *find_reloc_sorted(struct section *rsec,
> >  				       unsigned long offset, unsigned int len)
> >  {
> > -	struct reloc *reloc, *r = NULL;
> > -	struct section *rsec;
> > -	unsigned long o;
> > +	struct reloc *relocs = rsec->relocs;
> > +	const unsigned int nr_relocs = sec_num_entries(rsec);
> > +	const unsigned long cache_idx = reloc_cache_index(offset);
> > +	unsigned int reloc_idx, i;
> >
> > -	rsec = sec->rsec;
> > -	if (!rsec)
> > +	if (cache_idx >= reloc_cache_nr_windows(rsec))
> > +		return NULL;
> > +
> > +	reloc_idx = rsec->reloc_cache[cache_idx];
> > +
> > +	/*
> > +	 * Scan through all relocations covered by cache entry to find the
> > +	 * first at or after offset. Relocations are sorted by offset.
> > +	 */
> > +	for (i = reloc_idx; i < nr_relocs; i++) {
> > +		struct reloc *reloc = &relocs[i];
> > +		const unsigned long curr_offset = reloc_offset(reloc);
> > +
> > +		if (curr_offset >= offset)
> > +			break;
> > +
> > +		reloc_idx++;
> > +	}
> > +
> > +	/* Nothing found, or the first candidate lies beyond the range. */
> > +	if (reloc_idx >= nr_relocs ||
> > +	    reloc_offset(&relocs[reloc_idx]) >= offset + len)
> >  		return NULL;
> >
> > +	/* If there are duplicate entries, return the last. */
>
> Hm, for consistency with the others, shouldn't this be returning the
> *first* match?

Ack you're right.

It was pedantically trying to recreate what the hash did exactly but no section
has two relocations at one offset anyway, so have updated to return the first
and removed the special casing.

>
> > +/* If there are multiple matches, return the first one in the range. */
> > +struct reloc *find_reloc_by_dest_range(const struct elf *elf, struct section *sec,
> > +				       unsigned long offset, unsigned int len)
> >  {
> > -	return !strncmp(sec->name, ".debug_", 7);
> > +	struct section *rsec = sec->rsec;
> > +
> > +	if (!rsec)
> > +		return NULL;
> > +
> > +	if (rsec->sorted)
> > +		return find_reloc_sorted(rsec, offset, len);
> > +
> > +	if (rsec->hashed)
> > +		return find_reloc_hash(elf, rsec, offset, len);
> > +
> > +	return find_reloc_linear(rsec, offset, len);
>
> I'm not sure there's much benefit in having two fallbacks (hashed +
> linear) instead of one.  If the vast majority of reloc sections are
> sorted, then hopefully a single (linear) fallback would be fine,
> assuming no major performance regressions.  That would help contain the
> complexity.

Ack, and it turns out we don't even need to fallback for growth either after all
- relocations objtool appends actually arrive in offset order anyway.

So we can indeed just get rid of the hash entirely :)

So now v3 fallbacks to linear if there's anything out of order (belts + braces
I'm not sure anything will do that now actually but good to have to be safe),
annnd no hash :)

Have tested locally and confirmed output is byte-identical for vmlinux.o for
gcc/clang allmodconfig and defconfig, also tested klp-build and that's all
working too for livepatch stuff.

>
> BTW, I found another initialization bug: klp-post-link.c uses
> elf_create_section() to create a reloc section, so it missing the
> initialization of rsec->hashed in elf_create_rela_section().  But that's
> moot if we just get rid of the hashing.

Thanks, with the hash gone that's now moot as you say :)

>
> --
> Josh

--
Cheers, Lorenzo