Linux Perf Users
 help / color / mirror / Atom feed
From: sashiko-bot@kernel.org
To: "Ian Rogers" <irogers@google.com>
Cc: linux-perf-users@vger.kernel.org
Subject: Re: [PATCH v5 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion
Date: Mon, 16 Nov 2026 07:18:11 +0000	[thread overview]
Message-ID: <sashiko-outbox-216402@kernel.org> (raw)
In-Reply-To: <20261116063435.2817923-7-irogers@google.com>

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Medium] perf symbol: wrong lookup in symbols__find() across split
  sorted tail
--

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

perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion

This commit replaces full-array qsort() with natural-run merge sort and
binary insertion, and maintains a sorted prefix and sorted tail to speed
up incremental symbol insertions and sorting.

> diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
> index f1e3d7af714c1..8a47d1a44e5c7 100644
> --- a/tools/perf/util/symbol.c
> +++ b/tools/perf/util/symbol.c

[ ... ]

> @@ -589,8 +935,24 @@ static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
>  	if (symbols == NULL)
>  		return NULL;
>  
> -	symbols__sort_read_lock(symbols);
> -	res = symbols__find_range(symbols->symbols, symbols->cnt, ip);
> +	down_read(&symbols->lock);
> +	while (!symbols->sorted) {
> +		up_read(&symbols->lock);
> +		down_write(&symbols->lock);
> +		symbols__sort_locked(symbols);
> +		up_write(&symbols->lock);
> +		down_read(&symbols->lock);
> +	}
> +
> +	res = symbols__find_range(symbols->symbols, symbols->sorted_cnt, ip);
> +	if (symbols->sorted_cnt < symbols->cnt) {
> +		struct symbol *tail_res;
> +
> +		tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
> +					       symbols->cnt - symbols->sorted_cnt, ip);
> +		if (tail_res && (!res || tail_res->start > res->start))
> +			res = tail_res;
> +	}
>  	up_read(&symbols->lock);
>  
>  	return res;

[Severity: Medium]
Can symbols__find() return an earlier symbol instead of NULL when a
symbol with a higher start address in the other sorted slice ends before
ip?

In a single sorted array, symbols__find_range() only checks
symbol__covers() on the equal-start group with the highest start <= ip
and returns NULL if those symbols end before ip, even if an earlier
symbol still covers ip.

When dso__insert_symbol() places an out-of-order symbol into the sorted
tail (for example via symbol__new_unresolved() or db_ids_from_al()),
calling symbols__find_range() on the prefix and tail independently loses
the highest start <= ip whenever that slice's candidate does not cover
ip and returns NULL.  If the prefix has [0x0, 0x40) and the tail has
[0x20, 0x30), looking up 0x34 gets res = [0x0, 0x40) and tail_res = NULL,
so symbols__find() returns [0x0, 0x40) until the tail is later merged,
after which the same lookup returns NULL.

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

  reply	other threads:[~2026-11-16  7:18 UTC|newest]

Thread overview: 16+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16  6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-16  6:34 ` [PATCH v5 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes Ian Rogers
2026-11-16  6:44   ` sashiko-bot
2026-11-16  6:34 ` [PATCH v5 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size Ian Rogers
2026-11-16  6:51   ` sashiko-bot
2026-11-16  6:34 ` [PATCH v5 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup Ian Rogers
2026-11-16  6:48   ` sashiko-bot
2026-11-16  6:34 ` [PATCH v5 4/9] perf maps: Optimize tail insertion and small-append sorting Ian Rogers
2026-11-16  7:06   ` sashiko-bot
2026-11-16  6:34 ` [PATCH v5 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-16  7:20   ` sashiko-bot
2026-11-16  6:34 ` [PATCH v5 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion Ian Rogers
2026-11-16  7:18   ` sashiko-bot [this message]
2026-11-16  6:34 ` [PATCH v5 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-16  6:34 ` [PATCH v5 8/9] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-16  6:34 ` [PATCH v5 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=sashiko-outbox-216402@kernel.org \
    --to=sashiko-bot@kernel.org \
    --cc=irogers@google.com \
    --cc=linux-perf-users@vger.kernel.org \
    --cc=sashiko-reviews@lists.linux.dev \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox