Linux Perf Users
 help / color / mirror / Atom feed
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;
>  }

  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