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

[Josh Poimboeuf]

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?

> +/* 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.

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.

-- 
Josh