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 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.