From: Namhyung Kim <namhyung@kernel.org>
To: Ian Rogers <irogers@google.com>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>,
Alireza Haghdoost <haghdoost@uber.com>,
Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>, Jiri Olsa <jolsa@kernel.org>,
Adrian Hunter <adrian.hunter@intel.com>,
James Clark <james.clark@linaro.org>,
linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH v6 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array
Date: Tue, 17 Nov 2026 22:28:11 -0800 [thread overview]
Message-ID: <av1Fe0w4_oAEPDhB@google.com> (raw)
In-Reply-To: <20261117185305.108003-6-irogers@google.com>
On Tue, Nov 17, 2026 at 10:53:01AM -0800, Ian Rogers wrote:
> Previously, DSO symbols were stored in an unprotected rb_root_cached
> with a 24-byte struct rb_node embedded inside every struct symbol. That
> design had three drawbacks:
> 1. Embedding struct rb_node (3 pointers, 24 bytes on 64-bit) accounted
> for nearly 40% of struct symbol's fixed header size and scattered
> symbol lookups across non-contiguous heap nodes.
> 2. Unlike struct dsos and struct maps, the symbol rbtree had no lock
> protecting concurrent lookups, sorting, and insertions.
> 3. Deduplicating symbols, splitting kallsyms, and trimming excess symbol
> container capacity under memory pressure benefit from operating on a
> compact array under a lock.
>
> Replace struct rb_node in struct symbol with a locked, lazily-sorted
> pointer array in struct symbols, matching the design of struct dsos and
> struct maps:
>
> - Introduce struct symbols containing a rw_semaphore lock, primary
> address-sorted symbols array, secondary name-sorted symbols_by_name
> array, counts, capacity, and sorted state flags.
> - Lazily sort symbols by start address using qsort (symbols__sort_locked)
> and use binary search in symbols__find().
> - Update symbols__fixup_duplicate(), symbols__fixup_end(),
> maps__split_kallsyms_for_kcore(), and maps__split_kallsyms() to
> operate on the sorted array and compact entries in place.
> - Convert symbols__for_each_entry(), dso__for_each_symbol(), and
> map__for_each_symbol() to callback-based iteration under
> symbols->lock, matching dsos__for_each_dso() and maps__for_each_map().
> - Remove the unsynchronized single-entry dso->last_find_result cache and
> dso__reset_find_symbol_cache() since binary search over a contiguous
> array is cache-friendly.
> - Remove the direct rb_erase_cached() workaround in builtin-annotate.c's
> add_sample().
> - Update the TUI map browser (ui/browsers/map.c) to snapshot the sorted
> symbol array into an entries array and use ui_browser__argv_refresh
> and ui_browser__argv_seek instead of ui_browser__rb_tree_refresh.
>
> Using 'perf bench internals symbols':
>
> Before (perf binary):
> Average DSO load + sort: 7.041 msec (+- 0.051 msec)
> Average DSO memory usage: 1401 KB (+- 4 KB)
> Average bulk insert + lookup: 1453.950 usec (+- 10.895 usec)
> After (perf binary, -13.5% load, -14.6% memory, -7.7% bulk):
> Average DSO load + sort: 6.089 msec (+- 0.039 msec)
> Average DSO memory usage: 1197 KB (+- 3 KB)
> Average bulk insert + lookup: 1341.500 usec (+- 21.564 usec)
>
> Before (libLLVM.so.21.1):
> Average DSO load + sort: 78.599 msec (+- 0.857 msec)
> Average DSO memory usage: 9530 KB (+- 5 KB)
> After (libLLVM.so.21.1, -22.3% load, -8.1% memory):
> Average DSO load + sort: 61.074 msec (+- 0.236 msec)
> Average DSO memory usage: 8755 KB (+- 1 KB)
>
> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
> tools/perf/arch/powerpc/util/sym-handling.c | 34 +-
> tools/perf/builtin-annotate.c | 11 -
> tools/perf/builtin-kmem.c | 51 +-
> tools/perf/tests/hists_common.c | 5 +-
> tools/perf/tests/symbols.c | 62 +-
> tools/perf/tests/vmlinux-kallsyms.c | 181 +++---
> tools/perf/ui/browser.c | 3 +
> tools/perf/ui/browsers/hists.c | 3 +-
> tools/perf/ui/browsers/map.c | 62 +-
> tools/perf/util/auxtrace.c | 109 ++--
> tools/perf/util/db-export.c | 4 +-
> tools/perf/util/dso.c | 50 +-
> tools/perf/util/dso.h | 68 +--
> tools/perf/util/intel-pt.c | 74 ++-
> tools/perf/util/libbfd.c | 3 +-
> tools/perf/util/machine.c | 30 +-
> tools/perf/util/map.c | 36 +-
> tools/perf/util/map.h | 8 +-
> tools/perf/util/probe-event.c | 98 +--
> tools/perf/util/symbol-elf.c | 12 +-
> tools/perf/util/symbol.c | 643 ++++++++++++++------
> tools/perf/util/symbol.h | 72 ++-
> tools/perf/util/symbol_fprintf.c | 25 +-
> 23 files changed, 1011 insertions(+), 633 deletions(-)
>
> diff --git a/tools/perf/arch/powerpc/util/sym-handling.c b/tools/perf/arch/powerpc/util/sym-handling.c
> index 947bfad7aa59..f87d77262c00 100644
> --- a/tools/perf/arch/powerpc/util/sym-handling.c
> +++ b/tools/perf/arch/powerpc/util/sym-handling.c
> @@ -115,13 +115,27 @@ void arch__fix_tev_from_maps(struct perf_probe_event *pev,
> }
>
> #ifdef HAVE_LIBELF_SUPPORT
> +struct post_process_probe_trace_events_args {
> + struct perf_probe_event *pev;
> + struct probe_trace_event *tev;
> + struct map *map;
> +};
> +
> +static int post_process_probe_trace_events_cb(struct symbol *sym, void *data)
> +{
> + struct post_process_probe_trace_events_args *args = data;
> +
> + if (map__unmap_ip(args->map, sym->start) == args->tev->point.address) {
> + arch__fix_tev_from_maps(args->pev, args->tev, args->map, sym);
> + return 1;
> + }
> + return 0;
> +}
> +
> void arch__post_process_probe_trace_events(struct perf_probe_event *pev,
> int ntevs)
> {
> - struct probe_trace_event *tev;
> struct map *map;
> - struct symbol *sym = NULL;
> - struct rb_node *tmp;
> int i = 0;
>
> map = get_target_map(pev->target, pev->nsi, pev->uprobes);
> @@ -129,13 +143,13 @@ void arch__post_process_probe_trace_events(struct perf_probe_event *pev,
> return;
>
> for (i = 0; i < ntevs; i++) {
> - tev = &pev->tevs[i];
> - map__for_each_symbol(map, sym, tmp) {
> - if (map__unmap_ip(map, sym->start) == tev->point.address) {
> - arch__fix_tev_from_maps(pev, tev, map, sym);
> - break;
> - }
> - }
> + struct post_process_probe_trace_events_args args = {
> + .pev = pev,
> + .tev = &pev->tevs[i],
> + .map = map,
> + };
> +
> + map__for_each_symbol(map, post_process_probe_trace_events_cb, &args);
Please separate the map__for_each_symbol() changes as it can be
converted independently. New users can be separate commits too.
> }
> }
> #endif /* HAVE_LIBELF_SUPPORT */
> diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c
> index 7cb7e03d9a21..65846110c309 100644
> --- a/tools/perf/builtin-annotate.c
> +++ b/tools/perf/builtin-annotate.c
> @@ -258,17 +258,6 @@ static int add_sample(struct perf_sample *sample,
> (al->sym == NULL ||
> strcmp(ann->sym_hist_filter, al->sym->name) != 0)) {
> /* We're only interested in a symbol named sym_hist_filter */
> - /*
> - * FIXME: why isn't this done in the symbol_filter when loading
> - * the DSO?
> - */
> - if (al->sym != NULL) {
> - struct dso *dso = map__dso(al->map);
> -
> - rb_erase_cached(&al->sym->rb_node, dso__symbols(dso));
> - symbol__delete(al->sym);
> - dso__reset_find_symbol_cache(dso);
> - }
> return 0;
> }
>
> diff --git a/tools/perf/builtin-kmem.c b/tools/perf/builtin-kmem.c
> index 8693c6b135ca..87869c717266 100644
> --- a/tools/perf/builtin-kmem.c
> +++ b/tools/perf/builtin-kmem.c
> @@ -341,13 +341,33 @@ static int callcmp(const void *a, const void *b)
> return -1;
> }
>
> +static int build_alloc_func_list_cb(struct symbol *sym, void *data)
> +{
> + regex_t *alloc_func_regex = data;
> + struct alloc_func *func;
> +
> + if (regexec(alloc_func_regex, sym->name, 0, NULL, 0))
> + return 0;
> +
> + func = realloc(alloc_func_list,
> + (nr_alloc_funcs + 1) * sizeof(*func));
> + if (func == NULL)
> + return -ENOMEM;
> +
> + pr_debug("alloc func: %s\n", sym->name);
> + func[nr_alloc_funcs].start = sym->start;
> + func[nr_alloc_funcs].end = sym->end;
> + func[nr_alloc_funcs].name = sym->name;
> +
> + alloc_func_list = func;
> + nr_alloc_funcs++;
> + return 0;
> +}
> +
> static int build_alloc_func_list(void)
> {
> int ret;
> struct map *kernel_map;
> - struct symbol *sym;
> - struct rb_node *node;
> - struct alloc_func *func;
> struct machine *machine = &kmem_session->machines.host;
> regex_t alloc_func_regex;
> static const char pattern[] = "^_?_?(alloc|get_free|get_zeroed)_pages?";
> @@ -364,30 +384,17 @@ static int build_alloc_func_list(void)
> kernel_map = machine__kernel_map(machine);
> if (map__load(kernel_map) < 0) {
> pr_err("cannot load kernel map\n");
> + regfree(&alloc_func_regex);
Looks like an unrelated bug fix.
Thanks,
Namhyung
> return -ENOENT;
> }
>
> - map__for_each_symbol(kernel_map, sym, node) {
> - if (regexec(&alloc_func_regex, sym->name, 0, NULL, 0))
> - continue;
> -
> - func = realloc(alloc_func_list,
> - (nr_alloc_funcs + 1) * sizeof(*func));
> - if (func == NULL)
> - return -ENOMEM;
> -
> - pr_debug("alloc func: %s\n", sym->name);
> - func[nr_alloc_funcs].start = sym->start;
> - func[nr_alloc_funcs].end = sym->end;
> - func[nr_alloc_funcs].name = sym->name;
> -
> - alloc_func_list = func;
> - nr_alloc_funcs++;
> - }
> + ret = map__for_each_symbol(kernel_map, build_alloc_func_list_cb, &alloc_func_regex);
> + regfree(&alloc_func_regex);
> + if (ret)
> + return ret;
>
> - qsort(alloc_func_list, nr_alloc_funcs, sizeof(*func), funcmp);
> + qsort(alloc_func_list, nr_alloc_funcs, sizeof(*alloc_func_list), funcmp);
>
> - regfree(&alloc_func_regex);
> return 0;
> }
next prev parent reply other threads:[~2026-11-18 6:28 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-17 18:52 [PATCH v6 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-17 18:52 ` [PATCH v6 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes Ian Rogers
2026-11-17 19:03 ` sashiko-bot
2026-11-17 18:52 ` [PATCH v6 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size Ian Rogers
2026-11-17 19:04 ` sashiko-bot
2026-11-17 18:52 ` [PATCH v6 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup Ian Rogers
2026-11-17 19:00 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 4/9] perf maps: Optimize tail insertion and small-append sorting Ian Rogers
2026-11-17 19:10 ` sashiko-bot
2026-11-18 6:12 ` Namhyung Kim
2026-11-17 18:53 ` [PATCH v6 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-17 19:17 ` sashiko-bot
2026-11-18 6:28 ` Namhyung Kim [this message]
2026-11-17 18:53 ` [PATCH v6 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion Ian Rogers
2026-11-17 19:03 ` sashiko-bot
2026-11-18 6:34 ` Namhyung Kim
2026-11-17 18:53 ` [PATCH v6 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-17 19:25 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 8/9] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-17 19:15 ` sashiko-bot
2026-11-17 18:53 ` [PATCH v6 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-17 19:14 ` 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=av1Fe0w4_oAEPDhB@google.com \
--to=namhyung@kernel.org \
--cc=acme@kernel.org \
--cc=adrian.hunter@intel.com \
--cc=haghdoost@uber.com \
--cc=irogers@google.com \
--cc=james.clark@linaro.org \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
/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