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
next prev parent reply other threads:[~2026-11-16 7:18 UTC|newest]
Thread overview: 19+ 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 7:36 ` sashiko-bot
2026-11-16 6:34 ` [PATCH v5 8/9] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-16 7:40 ` sashiko-bot
2026-11-16 6:34 ` [PATCH v5 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-16 7:45 ` sashiko-bot
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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.