Re: [PATCH v3 15/20] perf symbol: Switch backing storage from rbtree to struct symbols array

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Medium] perf symbol: missing end address tie-breaker in
  symbols__sort_cmp()
--

commit 0573604acc8bf2d5351a71f4fe63cacfd8d508e5
Author: Ian Rogers <irogers@google.com>

perf symbol: Switch backing storage from rbtree to struct symbols array

This commit replaces the embedded rbtree node in struct symbol with a
locked, lazily-sorted pointer array in struct symbols and updates symbol
iteration and lookup callers to use it.

> diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
> index ec2a78873b903..66c5bd0386362 100644
> --- a/tools/perf/util/symbol.c
> +++ b/tools/perf/util/symbol.c
> @@ -213,57 +213,153 @@ static int choose_best_symbol(struct symbol *syma, struct symbol *symb)

[ ... ]

> +static inline bool symbol__less_or_equal(const struct symbol *a, const struct symbol *b)
> +{
> +	return symbol__start(a) <= symbol__start(b);
> +}
> +
> +static int symbols__sort_cmp(const void *vlhs, const void *vrhs)
> +{
> +	const struct symbol *lhs = *((const struct symbol **)vlhs);
> +	const struct symbol *rhs = *((const struct symbol **)vrhs);
> +
> +	if (symbol__start(lhs) != symbol__start(rhs))
> +		return symbol__start(lhs) < symbol__start(rhs) ? -1 : 1;
> +	return 0;
> +}

[ ... ]

> @@ -397,97 +495,94 @@ static void symbol__set_idle(struct symbol *sym, bool idle)

[ ... ]

> -static struct symbol *symbols__find(struct rb_root_cached *symbols, u64 ip)
> +/*
> + * Binary search @symbols->symbols for a symbol covering @ip. Lazily sorts
> + * @symbols under @symbols->lock if unsorted.
> + */
> +static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
>  {
> -	struct rb_node *n;
> +	int low, high;
> +	struct symbol *res = NULL;
>  
>  	if (symbols == NULL)
>  		return NULL;
>  
> -	n = symbols->rb_root.rb_node;
> +	symbols__sort_read_lock(symbols);
>  
> -	while (n) {
> -		struct symbol *s = rb_entry(n, struct symbol, rb_node);
> +	low = 0;
> +	high = (int)symbols->cnt - 1;
> +	while (low <= high) {
> +		int mid = low + (high - low) / 2;
> +		struct symbol *s = symbols->symbols[mid];
> +		u64 start = symbol__start(s);
> +		u64 end = symbol__end(s);
>  
> -		if (ip < symbol__start(s))
> -			n = n->rb_left;
> -		else if (ip > symbol__end(s) || (ip == symbol__end(s) && ip != symbol__start(s)))
> -			n = n->rb_right;
> -		else
> -			return s;
> +		if (ip < start)
> +			high = mid - 1;
> +		else if (ip > end || (ip == end && ip != start))
> +			low = mid + 1;
> +		else {
> +			res = s;
> +			break;
> +		}
>  	}
> +	up_read(&symbols->lock);
>  
> -	return NULL;
> +	return res;
>  }

[Severity: Medium]
Should symbol__less_or_equal() and symbols__sort_cmp() also compare
symbol__end() when two symbols share the same start address?

Because they only compare symbol__start(), a sized symbol [X, X + L) can
precede a zero-length alias [X, X) at the same start address (for example
when symbol_conf.allow_aliases is set or when both .symtab and .dynsym
define symbols at X).

If symbols__find() looks up an ip in (X, X + L) and mid lands on the
later [X, X) entry, ip > end advances low = mid + 1, skipping the
covering [X, X + L) entry to its left and returning NULL.

In addition, during ELF loading symbols__fixup_end() runs before
symbols__fixup_duplicate() and extends a trailing [X, X) entry up to the
next distinct symbol address Y, inflating its size before
choose_best_symbol() compares lengths, and map__fixup_end() can pick the
shorter symbol at symbols->symbols[symbols->cnt - 1] as the map end.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261110220803.2503416-1-irogers@google.com?part=15