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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] objtool: trailing cache windows left at 0 in reloc_cache_resize()
- [Medium] objtool: repeated cache rebuild and free in elf_create_reloc()
- [Low] objtool: compare_reloc_order() returns 1 instead of 0 for identical elements
--

commit 93b28e01d1c19629db4e088766e42dd4cdfbed56
Author: Lorenzo Stoakes (ARM) <ljs@kernel.org>

objtool: cache relocations, do less work, eliminate relocation hash

This commit replaces the global relocation hash table in objtool with a
per-section relocation cache indexed by 64-byte windows. Out-of-order
relocation sections are sorted lazily into an index array on lookup.

> diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
> index 98a110e3e8f57..bd463b5df38cd 100644
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -316,35 +316,220 @@ struct symbol *find_global_symbol_by_name(const struct elf *elf, const char *nam

[ ... ]

> +/* qsort() passes no context, so the relocations being sorted live here. */
> +static struct reloc *sort_relocs;
> +
> +static int compare_reloc_order(const void *a, const void *b)
> +{
> +	const unsigned int *idx_a = a;
> +	const unsigned int *idx_b = b;
> +	const unsigned long offset_a = reloc_offset(&sort_relocs[*idx_a]);
> +	const unsigned long offset_b = reloc_offset(&sort_relocs[*idx_b]);
> +
> +	if (offset_a < offset_b)
> +		return -1;
> +	if (offset_a > offset_b)
> +		return 1;
> +
> +	/* Equal offsets stay in file order. */
> +	if (*idx_a < *idx_b)
> +		return -1;
> +	return 1;
> +}

[Severity: Low]
As reported by Sashiko on v4 [1], when qsort() compares an element against
itself (a == b, so *idx_a == *idx_b), compare_reloc_order() returns 1
instead of 0.

Does this violate the C standard qsort() comparator contract if the libc
qsort() implementation compares the pivot element with itself during
partitioning? Returning (*idx_a > *idx_b) - (*idx_a < *idx_b) or checking
for *idx_a > *idx_b before returning 0 would ensure a strict total order.

[ ... ]

> +/* Grow the index to cover the base section, new windows start past the end. */
> +static int reloc_cache_resize(struct section *rsec)
> +{
> +	const unsigned int nr_windows = reloc_cache_index(sec_size(rsec->base)) + 1;
> +	unsigned int *cache;
> +
> +	if (nr_windows <= rsec->nr_cache_windows)
> +		return 0;
> +
> +	cache = realloc(rsec->reloc_cache, nr_windows * sizeof(*cache));
> +	if (!cache) {
> +		ERROR_GLIBC("realloc");
> +		return -1;
> +	}
> +
> +	while (rsec->nr_cache_windows < nr_windows)
> +		cache[rsec->nr_cache_windows++] = rsec->nr_indexed;
> +	rsec->reloc_cache = cache;
> +
> +	return 0;
> +}
> +
> +/*
> + * Index the next relocation. It must follow the previous one in position and
> + * offset, otherwise the index is dropped and the next lookup rebuilds it.
> + */
> +static int reloc_cache_add(struct section *rsec, unsigned int pos)
> +{
> +	struct reloc *reloc = reloc_at(rsec, pos);
> +	const unsigned long offset = reloc_offset(reloc);
> +	const unsigned long window = reloc_cache_index(offset);
> +	unsigned long first_window = 0;
> +
> +	if (pos != rsec->nr_indexed)
> +		goto unsorted;
> +
> +	if (pos) {
> +		struct reloc *prev = reloc_at(rsec, pos - 1);
> +		const unsigned long prev_offset = reloc_offset(prev);
> +
> +		if (offset < prev_offset)
> +			goto unsorted;
> +		first_window = reloc_cache_index(prev_offset) + 1;
> +	}
> +
> +	if (reloc_cache_resize(rsec))
> +		return -1;
> +	if (window >= rsec->nr_cache_windows)
> +		goto unsorted;
> +
> +	while (first_window <= window)
> +		rsec->reloc_cache[first_window++] = pos;
> +	rsec->nr_indexed = pos + 1;
> +
> +	return 0;
> +
> +unsorted:
> +	reloc_cache_free(rsec);
> +	return 0;
> +}

[ ... ]

> +/* 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)
>  {
> -	struct reloc *reloc, *r = NULL;
> -	struct section *rsec;
> -	unsigned long o;
> +	struct section *rsec = sec->rsec;
> +	unsigned long cache_idx;
> +	unsigned int pos;
>  
> -	rsec = sec->rsec;
>  	if (!rsec)
>  		return NULL;
>  
> -	for_offset_range(o, offset, offset + len) {
> -		elf_hash_for_each_possible(elf, reloc, reloc, hash,
> -					   sec_offset_hash(rsec, o)) {
> -			if (reloc->sec != rsec)
> -				continue;
> +	if (!rsec->sorted && init_reloc_cache(rsec))
> +		exit(1);
>  
> -			if (reloc_offset(reloc) >= offset &&
> -			    reloc_offset(reloc) < offset + len) {
> -				if (!r || reloc_offset(reloc) < reloc_offset(r))
> -					r = reloc;
> -			}
> -		}
> -		if (r && (reloc_offset(r) & OFFSET_STRIDE_MASK) == o)
> -			return r;
> +	cache_idx = reloc_cache_index(offset);
> +	if (cache_idx >= rsec->nr_cache_windows)
> +		return NULL;
> +
> +	/* The index gives a lower bound, scan on from there. */
> +	for (pos = rsec->reloc_cache[cache_idx]; pos < rsec->nr_indexed; pos++) {
> +		struct reloc *reloc = reloc_at(rsec, pos);
> +
> +		if (reloc_offset(reloc) >= offset)
> +			return reloc_in_range(reloc, offset, len) ? reloc : NULL;
>  	}
>  
> -	return r;
> +	return NULL;
>  }

[Severity: Medium]
As reported by Sashiko on v4 [2], during init_reloc_cache(), the first
call to reloc_cache_add(rsec, 0) invokes reloc_cache_resize(rsec) while
rsec->nr_indexed is 0. Because sec_size(rsec->base) is already the full
size of the base section, reloc_cache_resize() allocates all nr_windows
entries for the entire section at once and initializes every entry in
cache[0 .. nr_windows - 1] to 0.

Subsequent calls to reloc_cache_add(rsec, pos) see nr_windows <=
rsec->nr_cache_windows in reloc_cache_resize() and only update
rsec->reloc_cache[first_window .. window] up to the window of the last
relocation. Even when a section grows incrementally, reloc_cache_resize()
runs before rsec->nr_indexed = pos + 1 in reloc_cache_add().

Won't any 64-byte window located after the last relocation in a section
remain set to 0 in rsec->reloc_cache[], causing find_reloc_by_dest_range()
to linearly scan all rsec->nr_indexed relocations from pos = 0 on every
lookup in the trailing part of the section?

[ ... ]

> @@ -1071,8 +1251,10 @@ struct reloc *elf_init_reloc(struct elf *elf, struct section *rsec,
>  	set_reloc_type(elf, reloc, type);
>  	set_reloc_addend(elf, reloc, addend);
>  
> -	if (!is_dwarf_section(rsec->base))
> -		elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
> +	if (rsec->reloc_order)
> +		reloc_cache_free(rsec);
> +	else if (rsec->sorted && reloc_cache_add(rsec, reloc_idx))
> +		return NULL;

[Severity: Medium]
When elf_create_reloc() creates a new relocation, it first calls
find_reloc_by_dest(), and then calls elf_init_reloc():

elf_create_reloc()
  find_reloc_by_dest()
    find_reloc_by_dest_range()
      if (!rsec->sorted && init_reloc_cache(rsec))
  elf_init_reloc()
    if (rsec->reloc_order)
      reloc_cache_free(rsec);

In tools/objtool/klp-diff.c, clone_reloc() can recursively call
clone_symbol() on a target symbol in the same output section before
calling elf_create_reloc() for the caller's relocation, emitting a
relocation at a lower offset after one at a higher offset.

Once a single out-of-order relocation is added to rsec, won't every
subsequent elf_create_reloc() call on that section rebuild rsec->reloc_order
via qsort() and populate rsec->reloc_cache in find_reloc_by_dest(), only for
elf_init_reloc() to immediately free both via reloc_cache_free(rsec) because
rsec->reloc_order is non-NULL?

[1] https://lore.kernel.org/r/20260923-build-speedup-v4-17-73128809a4a4@kernel.org
[2] https://lore.kernel.org/r/20260923-build-speedup-v4-17-73128809a4a4@kernel.org

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261104-build-speedup-v5-0-0f6018be8dae@kernel.org?part=7