* [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking
@ 2026-11-21 7:16 Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
` (10 more replies)
0 siblings, 11 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
When profiling large binaries or long-running workloads with many DSOs and
threads, symbol and DSO tables frequently dominate perf's memory footprint
and startup latency. Currently `struct symbol` still has several structural
limitations:
1. Every `struct symbol` embeds a 24-byte `struct rb_node` for the
`dso->symbols` address rbtree, scattering lookups across non-contiguous
heap nodes.
2. `dso__symbols()` has no internal synchronization against concurrent
readers/writers, and unreferenced DSOs and auxiliary symbol/debuginfo
buffers cannot yet be reclaimed under memory pressure.
3. Sorting `dso->symbols` with `qsort()` does not take advantage of
pre-ordered ascending runs in ELF symbol tables, and `first_ending_after()`
in `struct maps` runs a full binary search even for ascending
`/proc/pid/maps` synthesis.
Thirteen preparatory fixes, benchmarks, `dso_symbol` lifetime conversions,
`symbol_conf.priv_size` removal, and ELF header caching patches from v4-v6
have landed in `perf-tools-next`. The remaining 10 patches convert symbol
iteration to callbacks, replace the `dso->symbols` rbtree with a sorted
pointer array, stage natural-run merge sort and incremental symbol
insertion, and add memory shrinking APIs and unit tests:
- **Preparatory fix, `maps` tail fast-path, and symbol iteration (Patches 1-4)**:
- Patch 1 fixes an `alloc_func_regex` leak on error returns in
`builtin-kmem.c`'s `build_alloc_func_list()`.
- Patch 2 adds an O(1) tail fast-path check in `first_ending_after()` for
ascending map insertions.
- Patch 3 converts `symbols__for_each_entry()`, `dso__for_each_symbol()`,
and `map__for_each_symbol()` to callback-based iteration and updates
existing callers.
- Patch 4 converts open-coded `dso__first_symbol()` / `dso__next_symbol()`,
`rb_first_cached()`, and `dso__symbol_names()` loops to callback
helpers and removes `dso__{first,last,next}_symbol()`.
- **Sorted symbol arrays and staged sorting optimizations (Patches 5-7)**:
- Patch 5 replaces `dso->symbols` (`rb_root_cached`) and
`dso->symbol_names` with a `rw_semaphore`-protected `struct symbols`
container backed by sorted pointer arrays, removing `struct rb_node`
from `struct symbol` (shrinking `sizeof(struct symbol)` from 48 to 24
bytes, or 16 bytes net per symbol after accounting for the array
pointer).
- Patch 6 replaces `qsort()` on `struct symbols` with a stable
natural-run merge sort.
- Patch 7 optimizes incremental dynamic symbol insertions
(`dso__insert_symbol()`) and small appends using `@sorted_cnt` and a
sorted tail buffer with amortized `sqrt(N)` merge.
- **Memory shrinking APIs and unit tests (Patches 8-10)**:
- Patch 8 adds `symbols__shrink()`, `dso__shrink()`, `dsos__shrink()`,
`machine__shrink()`, `machines__shrink()`, and `perf_session__shrink()`
to reclaim `symbols_by_name`, excess array capacity, cached DSO file
descriptors/data/DWARF state, and unreferenced user DSOs (`refcnt == 1`
with no annotated symbols), with transparent on-demand reload via
`dso__load()`.
- Patch 9 adds `dso__session()` and `perf_session__malloc()` /
`zalloc()` / `calloc()` / `realloc()` / `strdup()` wrappers (leaving
production caller wiring for follow-up once lazy symbol loading is
evaluated).
- Patch 10 adds unit tests in `perf test symbols` covering sorted symbol
insertion, equal-start aliases, symbol/DSO shrinking, `dso_symbol`
lifetime pinning, inline frame/srcline cleanup ordering,
`symbols_by_name` on-demand rebuild, transparent DSO reload, and session
allocation wrappers.
Changes in v7:
- Rebase onto `perf-tools-next` (`bb27ddbaee56`), dropping the 3 patches
from v6 that have been applied upstream.
- Drop `nr_addr_sorted` and `nr_name_sorted` incremental partial-sort state
from `struct maps`, keeping only the `first_ending_after()` tail
fast-path check (`Patch 2`) (Namhyung Kim).
- Split out the `alloc_func_regex` leak fix in `builtin-kmem.c` (`Patch 1`),
the `map__for_each_symbol()` callback conversion (`Patch 3`), and the
conversion of open-coded symbol loops (`Patch 4`) ahead of the `rbtree`
to `struct symbols` array conversion (`Patch 5`) (Namhyung Kim).
- Split symbol sorting optimization into a simple natural-run merge sort
patch without galloping (`Patch 6`) followed by incremental dynamic
symbol insertion with a sorted tail (`Patch 7`) (Namhyung Kim).
Changes in v6:
- Fix `symbols__find()` when `sorted_cnt < cnt` so that if the slice
(sorted prefix or unmerged sorted tail) with the higher `start <= ip`
group ends before `ip`, `symbols__find()` returns `NULL` rather than
falling back to an earlier outer symbol in the other slice, matching
post-merge behavior, and add unmerged-vs-merged prefix/tail overlap and
equal-start alias unit tests (Sashiko).
- Use positive `ENOMEM` rather than `-ENOMEM` on `symbol__annotation()`
failure in `symbol__annotate()`, `symbol__annotate2()`, and
`__hist_entry__tui_annotate()` to match `symbol__strerror_disassemble()`,
check `symbol__annotate() != 0` in `hist_entry__get_data_type()`, and
guard against `NULL` `notes` / `notes->src` in `find_disasm_line()`
(Sashiko).
Changes in v5:
- Rebase onto `perf-tools-next` (`b7ff10b9ddec`), dropping the 10 patches
from v4 that have been applied upstream.
- Defer `perf_singlethreaded` removal, `rwsem` trylock helpers, and wiring
`perf_session__*` allocation wrappers into symbol/DSO/thread/hist callers
to follow-up work while keeping the shrinking APIs and unit tests
(Namhyung Kim).
- Drop the mechanical `struct symbol` field-accessor refactoring patch and
add kernel-doc comments on `struct dso_symbol` and `struct map_symbol`
explaining the DSO-owned symbol lifetime connection.
- Drop `SYMBOL_FLAG_ANNOTATED` from `struct symbol::flags` and check the
`annotations` hashmap under `annotations_lock` with an atomic
`nr_annotations` fast path, and return `NULL` on allocation failure in
`symbol__annotation()` (Namhyung Kim, Alireza Haghdoost, Sashiko).
- Avoid `_dso__data_open_lock` <-> `dso__lock` lock inversion in
`dsos__shrink()` / `dso__shrink()` and add a concurrent regression test
in `perf test symbols` (Sashiko).
v6: https://lore.kernel.org/linux-perf-users/20261117185305.108003-1-irogers@google.com/
v5: https://lore.kernel.org/linux-perf-users/20261116063435.2817923-1-irogers@google.com/
v4: https://lore.kernel.org/linux-perf-users/20261113171734.2188066-1-irogers@google.com/
v3: https://lore.kernel.org/linux-perf-users/20261110220803.2503416-1-irogers@google.com/
v2: https://lore.kernel.org/linux-perf-users/20261027231513.816148-1-irogers@google.com/
v1: https://lore.kernel.org/lkml/20260928075237.3055101-1-irogers@google.com/
AI Assistance Disclosure (per Documentation/process/coding-assistants.rst
and Documentation/process/generated-content.rst):
- Tools used: Google Antigravity / Jetski coding assistant and Sashiko
automated patch review (sashiko.dev and internal Sashiko).
- Summary of prompts and assistance: Interactive pair-programming session to
replace per-symbol refcounting with `struct dso_symbol` DSO-borrowed
lifetimes, split symbol callback iteration and staged natural-run merge
sort / incremental insertion patches, and address LKML reviewer and
Sashiko feedback across `kmem`, `dso`, `map`, `maps`, `symbol`, and
`tests/symbols.c`.
- Testing performed: Built each commit (`[1/10]` through `[10/10]`) with
Clang (`-Wthread-safety`), AddressSanitizer, LeakSanitizer, and `DEBUG=1`
(`REFCNT_CHECKING=1`); ran `perf test` (including `Symbols`, `Maps`, `DSO
data`, `hists`, `thread`, and `annotate` suites), `perf bench internals`
(`symbols` and `maps`), and `scripts/checkpatch.pl`.
Ian Rogers (10):
perf kmem: Fix alloc_func_regex leak on error in
build_alloc_func_list()
perf maps: Add tail fast-path check in first_ending_after()
perf symbol: Convert map__for_each_symbol() to callback-based
iteration
perf symbol: Use callback iteration instead of open-coded symbol loops
perf symbol: Switch backing storage from rbtree to struct symbols
array
perf symbol: Replace qsort() with natural-run merge sort
perf symbol: Optimize incremental symbol insertion with sorted tail
perf symbol: Add memory shrinking for symbols, DSOs, and machines
perf session: Add dso__session() and session-scoped allocation
wrappers
perf test symbols: Add tests for symbol shrinking and session alloc
wrappers
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/maps.c | 46 +
tools/perf/tests/symbols.c | 840 ++++++++++++++-
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 | 368 ++++++-
tools/perf/util/dso.h | 84 +-
tools/perf/util/dsos.c | 51 +
tools/perf/util/dsos.h | 3 +
tools/perf/util/intel-pt.c | 74 +-
tools/perf/util/libbfd.c | 3 +-
tools/perf/util/machine.c | 60 +-
tools/perf/util/machine.h | 8 +
tools/perf/util/map.c | 36 +-
tools/perf/util/map.h | 8 +-
tools/perf/util/maps.c | 4 +
tools/perf/util/probe-event.c | 98 +-
tools/perf/util/session.c | 78 ++
tools/perf/util/session.h | 8 +
tools/perf/util/symbol-elf.c | 12 +-
tools/perf/util/symbol.c | 1031 +++++++++++++++----
tools/perf/util/symbol.h | 84 +-
tools/perf/util/symbol_fprintf.c | 25 +-
30 files changed, 2711 insertions(+), 673 deletions(-)
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list()
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after() Ian Rogers
` (9 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
In build_alloc_func_list(), after regcomp(&alloc_func_regex, ...)
succeeds, the early error returns on map__load() failure and realloc()
failure return without calling regfree(&alloc_func_regex), leaking the
compiled regular expression buffer.
Call regfree(&alloc_func_regex) on both error paths before returning.
Fixes: c9758cc45699 ("perf kmem: Implement stat --page --caller")
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/builtin-kmem.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
diff --git a/tools/perf/builtin-kmem.c b/tools/perf/builtin-kmem.c
index 8693c6b135ca..1404b523a785 100644
--- a/tools/perf/builtin-kmem.c
+++ b/tools/perf/builtin-kmem.c
@@ -364,6 +364,7 @@ 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);
return -ENOENT;
}
@@ -373,8 +374,10 @@ static int build_alloc_func_list(void)
func = realloc(alloc_func_list,
(nr_alloc_funcs + 1) * sizeof(*func));
- if (func == NULL)
+ if (func == NULL) {
+ regfree(&alloc_func_regex);
return -ENOMEM;
+ }
pr_debug("alloc func: %s\n", sym->name);
func[nr_alloc_funcs].start = sym->start;
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after()
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration Ian Rogers
` (8 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
User-space map insertions (from /proc/pid/maps synthesis, runtime
PERF_RECORD_MMAP2, and jitdump) and BPF ksymbol registrations all flow
through maps__fixup_overlap_and_insert() -> first_ending_after().
Currently first_ending_after() has a fast-path check for the first map
(maps_by_address[0]), but no fast-path check for the last map
(maps_by_address[high]). Because /proc/pid/maps entries are synthesized
in ascending address order, every synthesized mapping starts at or after
maps_by_address[high]'s end, yet currently executes the full O(log N)
binary search loop.
Add a tail check in first_ending_after() so non-overlapping ascending
insertions complete in O(1), and add a unit test in tools/perf/tests/maps.c
covering ascending tail insertions.
Using 'perf bench internals maps':
Before:
Average ascending insert + lookup: 63.370 usec (+- 0.476 usec)
After (-6.9%):
Average ascending insert + lookup: 58.970 usec (+- 0.609 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/tests/maps.c | 46 +++++++++++++++++++++++++++++++++++++++++
tools/perf/util/maps.c | 4 ++++
2 files changed, 50 insertions(+)
diff --git a/tools/perf/tests/maps.c b/tools/perf/tests/maps.c
index ff6d25f9c043..3e8418ec6100 100644
--- a/tools/perf/tests/maps.c
+++ b/tools/perf/tests/maps.c
@@ -253,9 +253,55 @@ static int test__maps__fixup_overlap_and_insert(struct test_suite *t __maybe_unu
return TEST_OK;
}
+static int test__maps__tail_insert(struct test_suite *t __maybe_unused,
+ int subtest __maybe_unused)
+{
+ struct map_def ascending_maps[] = {
+ { "map_c", 1000, 2000 },
+ { "map_a", 2000, 3000 },
+ { "map_d", 4000, 5000 },
+ };
+ struct map *map, *found;
+ struct perf_env host_env;
+ struct machine *machine;
+ struct maps *maps;
+ int ret;
+
+ perf_env__init(&host_env);
+ machine = machine__new_live(&host_env, /*kernel_maps=*/false, getpid());
+ maps = maps__new(machine);
+
+ TEST_ASSERT_VAL("failed to create machine", machine);
+ TEST_ASSERT_VAL("failed to create maps", maps);
+
+ /* Exercise tail fast-path in maps__fixup_overlap_and_insert. */
+ for (unsigned int i = 0; i < ARRAY_SIZE(ascending_maps); i++) {
+ map = dso__new_map(ascending_maps[i].name);
+ TEST_ASSERT_VAL("failed to create map", map);
+ map__set_start(map, ascending_maps[i].start);
+ map__set_end(map, ascending_maps[i].end);
+ TEST_ASSERT_VAL("failed to insert sorted map",
+ maps__fixup_overlap_and_insert(maps, map) == 0);
+ map__put(map);
+ }
+
+ ret = check_maps(ascending_maps, ARRAY_SIZE(ascending_maps), maps);
+ TEST_ASSERT_VAL("tail insert check_maps failed", !ret);
+
+ found = maps__find(maps, 2500);
+ TEST_ASSERT_VAL("failed to find map_a by address", found && map__start(found) == 2000);
+ map__zput(found);
+
+ maps__zput(maps);
+ machine__delete(machine);
+ perf_env__exit(&host_env);
+ return TEST_OK;
+}
+
static struct test_case tests__maps[] = {
TEST_CASE("Test merge_in interface", maps__merge_in),
TEST_CASE("Test fix up overlap interface", maps__fixup_overlap_and_insert),
+ TEST_CASE("Test tail insert fast-path", maps__tail_insert),
{ .name = NULL, }
};
diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c
index 675fe0223faa..dd3b27b568da 100644
--- a/tools/perf/util/maps.c
+++ b/tools/perf/util/maps.c
@@ -858,6 +858,10 @@ static unsigned int first_ending_after(struct maps *maps, const struct map *map)
assert(maps__maps_by_address_sorted(maps));
if (low <= high && map__end(maps_by_address[0]) > map__start(map))
return 0;
+ if (low <= high && !RC_CHK_ACCESS(maps)->ends_broken &&
+ map__end(maps_by_address[high]) <= map__start(map)) {
+ return first;
+ }
while (low <= high) {
int mid = (low + high) / 2;
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
2026-11-21 7:16 ` [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after() Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops Ian Rogers
` (7 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
Currently symbols__for_each_entry(), dso__for_each_symbol(), and
map__for_each_symbol() are macros that expose struct rb_node * cursors to
callers and perform unlocked rb_first_cached() / rb_next() walks.
To prepare for replacing the unprotected symbol rbtree with a locked
symbol array, replace symbols__for_each_entry() with a callback-based
symbols__visit() helper and convert dso__for_each_symbol() and
map__for_each_symbol() to callback-based iteration matching
dsos__for_each_dso() and maps__for_each_map(), updating the existing
map__for_each_symbol() callers.
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/arch/powerpc/util/sym-handling.c | 34 ++--
tools/perf/builtin-kmem.c | 52 +++---
tools/perf/tests/vmlinux-kallsyms.c | 181 ++++++++++----------
tools/perf/util/dso.h | 8 +-
tools/perf/util/map.h | 8 +-
tools/perf/util/probe-event.c | 82 +++++----
tools/perf/util/symbol.c | 19 ++
tools/perf/util/symbol.h | 16 +-
8 files changed, 228 insertions(+), 172 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);
}
}
#endif /* HAVE_LIBELF_SUPPORT */
diff --git a/tools/perf/builtin-kmem.c b/tools/perf/builtin-kmem.c
index 1404b523a785..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?";
@@ -368,29 +388,13 @@ static int build_alloc_func_list(void)
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) {
- regfree(&alloc_func_regex);
- 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;
}
diff --git a/tools/perf/tests/vmlinux-kallsyms.c b/tools/perf/tests/vmlinux-kallsyms.c
index 9396c8a77c86..38f5c9584e15 100644
--- a/tools/perf/tests/vmlinux-kallsyms.c
+++ b/tools/perf/tests/vmlinux-kallsyms.c
@@ -113,6 +113,7 @@ static bool is_ignored_symbol(const char *name, char type)
struct test__vmlinux_matches_kallsyms_cb_args {
struct machine kallsyms;
struct map *vmlinux_map;
+ int err;
bool header_printed;
};
@@ -185,16 +186,101 @@ static int test__vmlinux_matches_kallsyms_cb3(struct map *map, void *data)
return 0;
}
+static int test__vmlinux_matches_kallsyms_sym_cb(struct symbol *sym, void *data)
+{
+ struct test__vmlinux_matches_kallsyms_cb_args *args = data;
+ /*
+ * Step 4:
+ *
+ * kallsyms will be internally on demand sorted by name so that we can
+ * find the reference relocation * symbol, i.e. the symbol we will use
+ * to see if the running kernel was relocated by checking if it has the
+ * same value in the vmlinux file we load.
+ */
+ struct map *kallsyms_map = machine__kernel_map(&args->kallsyms);
+ struct symbol *pair, *first_pair;
+ u64 mem_start, mem_end;
+
+ if (sym->start == sym->end)
+ return 0;
+
+ mem_start = map__unmap_ip(args->vmlinux_map, sym->start);
+ mem_end = map__unmap_ip(args->vmlinux_map, sym->end);
+
+ first_pair = machine__find_kernel_symbol(&args->kallsyms, mem_start, NULL);
+ pair = first_pair;
+
+ if (pair && UM(pair->start) == mem_start) {
+next_pair:
+ if (arch__compare_symbol_names(sym->name, pair->name) == 0) {
+ /*
+ * kallsyms don't have the symbol end, so we
+ * set that by using the next symbol start - 1,
+ * in some cases we get this up to a page
+ * wrong, trace_kmalloc when I was developing
+ * this code was one such example, 2106 bytes
+ * off the real size. More than that and we
+ * _really_ have a problem.
+ */
+ s64 skew = mem_end - UM(pair->end);
+
+ if (llabs(skew) >= page_size) {
+ pr_debug("WARN: %#" PRIx64 ": diff end addr for %s v: %#"
+ PRIx64 " k: %#" PRIx64 "\n",
+ mem_start, sym->name, mem_end,
+ UM(pair->end));
+ }
+
+ /*
+ * Do not count this as a failure, because we
+ * could really find a case where it's not
+ * possible to get proper function end from
+ * kallsyms.
+ */
+ return 0;
+ }
+ pair = machine__find_kernel_symbol_by_name(&args->kallsyms,
+ sym->name, NULL);
+ if (pair) {
+ if (UM(pair->start) == mem_start)
+ goto next_pair;
+
+ pr_debug("WARN: %#" PRIx64 ": diff name v: %s k: %s\n",
+ mem_start, sym->name, pair->name);
+ } else {
+ pr_debug("WARN: %#" PRIx64 ": diff name v: %s k: %s\n",
+ mem_start, sym->name, first_pair->name);
+ }
+
+ return 0;
+ }
+
+ if (mem_start == map__end(args->kallsyms.vmlinux_map)) {
+ /*
+ * Ignore aliases to _etext, i.e. to the end of the kernel text area,
+ * such as __indirect_thunk_end.
+ */
+ return 0;
+ }
+ if (is_ignored_symbol(sym->name, symbol__type(sym))) {
+ /*
+ * Ignore hidden symbols, see scripts/kallsyms.c for the details
+ */
+ return 0;
+ }
+ pr_debug("ERR : %#" PRIx64 ": %s not on kallsyms\n",
+ mem_start, sym->name);
+
+ args->err = -1;
+ return 0;
+}
+
static int test__vmlinux_matches_kallsyms(struct test_suite *test __maybe_unused,
int subtest __maybe_unused)
{
int err = TEST_FAIL;
- struct rb_node *nd;
- struct symbol *sym;
- struct map *kallsyms_map;
struct machine vmlinux = { 0 };
struct maps *maps;
- u64 mem_start, mem_end;
struct test__vmlinux_matches_kallsyms_cb_args args;
/*
@@ -240,16 +326,6 @@ static int test__vmlinux_matches_kallsyms(struct test_suite *test __maybe_unused
goto out;
}
- /*
- * Step 4:
- *
- * kallsyms will be internally on demand sorted by name so that we can
- * find the reference relocation * symbol, i.e. the symbol we will use
- * to see if the running kernel was relocated by checking if it has the
- * same value in the vmlinux file we load.
- */
- kallsyms_map = machine__kernel_map(&args.kallsyms);
-
/*
* Step 5:
*
@@ -279,7 +355,7 @@ static int test__vmlinux_matches_kallsyms(struct test_suite *test __maybe_unused
goto out;
}
- err = 0;
+ args.err = 0;
/*
* Step 7:
*
@@ -287,79 +363,8 @@ static int test__vmlinux_matches_kallsyms(struct test_suite *test __maybe_unused
* in the kallsyms dso. For the ones that are in both, check its names and
* end addresses too.
*/
- map__for_each_symbol(args.vmlinux_map, sym, nd) {
- struct symbol *pair, *first_pair;
-
- sym = rb_entry(nd, struct symbol, rb_node);
-
- if (sym->start == sym->end)
- continue;
-
- mem_start = map__unmap_ip(args.vmlinux_map, sym->start);
- mem_end = map__unmap_ip(args.vmlinux_map, sym->end);
-
- first_pair = machine__find_kernel_symbol(&args.kallsyms, mem_start, NULL);
- pair = first_pair;
-
- if (pair && UM(pair->start) == mem_start) {
-next_pair:
- if (arch__compare_symbol_names(sym->name, pair->name) == 0) {
- /*
- * kallsyms don't have the symbol end, so we
- * set that by using the next symbol start - 1,
- * in some cases we get this up to a page
- * wrong, trace_kmalloc when I was developing
- * this code was one such example, 2106 bytes
- * off the real size. More than that and we
- * _really_ have a problem.
- */
- s64 skew = mem_end - UM(pair->end);
- if (llabs(skew) >= page_size)
- pr_debug("WARN: %#" PRIx64 ": diff end addr for %s v: %#" PRIx64 " k: %#" PRIx64 "\n",
- mem_start, sym->name, mem_end,
- UM(pair->end));
-
- /*
- * Do not count this as a failure, because we
- * could really find a case where it's not
- * possible to get proper function end from
- * kallsyms.
- */
- continue;
- } else {
- pair = machine__find_kernel_symbol_by_name(&args.kallsyms,
- sym->name, NULL);
- if (pair) {
- if (UM(pair->start) == mem_start)
- goto next_pair;
-
- pr_debug("WARN: %#" PRIx64 ": diff name v: %s k: %s\n",
- mem_start, sym->name, pair->name);
- } else {
- pr_debug("WARN: %#" PRIx64 ": diff name v: %s k: %s\n",
- mem_start, sym->name, first_pair->name);
- }
-
- continue;
- }
- } else if (mem_start == map__end(args.kallsyms.vmlinux_map)) {
- /*
- * Ignore aliases to _etext, i.e. to the end of the kernel text area,
- * such as __indirect_thunk_end.
- */
- continue;
- } else if (is_ignored_symbol(sym->name, symbol__type(sym))) {
- /*
- * Ignore hidden symbols, see scripts/kallsyms.c for the details
- */
- continue;
- } else {
- pr_debug("ERR : %#" PRIx64 ": %s not on kallsyms\n",
- mem_start, sym->name);
- }
-
- err = -1;
- }
+ map__for_each_symbol(args.vmlinux_map, test__vmlinux_matches_kallsyms_sym_cb, &args);
+ err = args.err;
if (verbose <= 0)
goto out;
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index d5f7382d4e13..532ad3ec156f 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -365,11 +365,11 @@ int dso_id__cmp(const struct dso_id *a, const struct dso_id *b);
/* dso__for_each_symbol - iterate over the symbols of given type
*
* @dso: the 'struct dso *' in which symbols are iterated
- * @pos: the 'struct symbol *' to use as a loop cursor
- * @n: the 'struct rb_node *' to use as a temporary storage
+ * @cb: callback function invoked for each symbol
+ * @data: opaque data pointer passed to @cb
*/
-#define dso__for_each_symbol(dso, pos, n) \
- symbols__for_each_entry(dso__symbols(dso), pos, n)
+#define dso__for_each_symbol(dso, cb, data) \
+ symbols__visit(dso__symbols(dso), cb, data)
static inline void *dso__a2l(const struct dso *dso)
{
diff --git a/tools/perf/util/map.h b/tools/perf/util/map.h
index c2e31be232c8..32f1fd9a7404 100644
--- a/tools/perf/util/map.h
+++ b/tools/perf/util/map.h
@@ -146,12 +146,12 @@ struct thread;
/* map__for_each_symbol - iterate over the symbols in the given map
*
* @map: the 'struct map *' in which symbols are iterated
- * @pos: the 'struct symbol *' to use as a loop cursor
- * @n: the 'struct rb_node *' to use as a temporary storage
+ * @cb: callback function invoked for each symbol
+ * @data: opaque data pointer passed to @cb
* Note: caller must ensure map->dso is not NULL (map is loaded).
*/
-#define map__for_each_symbol(map, pos, n) \
- dso__for_each_symbol(map__dso(map), pos, n)
+#define map__for_each_symbol(map, cb, data) \
+ dso__for_each_symbol(map__dso(map), cb, data)
/* map__for_each_symbol_with_name - iterate over the symbols in the given map
* that have the given name
diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c
index 1534280c0c1d..3d506c09b749 100644
--- a/tools/perf/util/probe-event.c
+++ b/tools/perf/util/probe-event.c
@@ -3047,49 +3047,63 @@ static int __add_probe_trace_events(struct perf_probe_event *pev,
return ret;
}
-static int find_probe_functions(struct map *map, char *name,
- struct symbol **syms)
+struct find_probe_functions_args {
+ const char *name;
+ struct symbol **syms;
+ int found;
+ bool cut_version;
+};
+
+static int find_probe_functions_cb(struct symbol *sym, void *data)
{
- int found = 0;
- struct symbol *sym;
- struct rb_node *tmp;
+ struct find_probe_functions_args *args = data;
const char *norm, *ver;
char *buf = NULL;
- bool cut_version = true;
-
- if (map__load(map) < 0)
- return -EACCES; /* Possible permission error to load symbols */
- /* If user gives a version, don't cut off the version from symbols */
- if (strchr(name, '@'))
- cut_version = false;
-
- map__for_each_symbol(map, sym, tmp) {
- norm = arch__normalize_symbol_name(sym->name);
- if (!norm)
- continue;
+ norm = arch__normalize_symbol_name(sym->name);
+ if (!norm)
+ return 0;
- if (cut_version) {
- /* We don't care about default symbol or not */
- ver = strchr(norm, '@');
- if (ver) {
- buf = strndup(norm, ver - norm);
- if (!buf)
- return -ENOMEM;
- norm = buf;
- }
+ if (args->cut_version) {
+ /* We don't care about default symbol or not */
+ ver = strchr(norm, '@');
+ if (ver) {
+ buf = strndup(norm, ver - norm);
+ if (!buf)
+ return -ENOMEM;
+ norm = buf;
}
+ }
- if (strglobmatch(norm, name)) {
- found++;
- if (syms && found < probe_conf.max_probes)
- syms[found - 1] = sym;
- }
- if (buf)
- zfree(&buf);
+ if (strglobmatch(norm, args->name)) {
+ args->found++;
+ if (args->syms && args->found < probe_conf.max_probes)
+ args->syms[args->found - 1] = sym;
}
+ free(buf);
+ return 0;
+}
+
+static int find_probe_functions(struct map *map, char *name,
+ struct symbol **syms)
+{
+ struct find_probe_functions_args args = {
+ .name = name,
+ .syms = syms,
+ /* If user gives a version, don't cut off the version from symbols */
+ .cut_version = strchr(name, '@') == NULL,
+ .found = 0,
+ };
+ int ret;
+
+ if (map__load(map) < 0)
+ return -EACCES; /* Possible permission error to load symbols */
+
+ ret = map__for_each_symbol(map, find_probe_functions_cb, &args);
+ if (ret < 0)
+ return ret;
- return found;
+ return args.found;
}
void __weak arch__fix_tev_from_maps(struct perf_probe_event *pev __maybe_unused,
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index a1ac1cd1d2e7..1f7faae5a357 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -613,6 +613,25 @@ struct symbol *dso__find_symbol(struct dso *dso, u64 addr)
return dso__last_find_result_symbol(dso);
}
+int symbols__visit(struct rb_root_cached *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data)
+{
+ struct rb_node *nd;
+
+ if (!symbols)
+ return 0;
+
+ for (nd = rb_first_cached(symbols); nd; nd = rb_next(nd)) {
+ struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
+ int ret = cb(sym, data);
+
+ if (ret)
+ return ret;
+ }
+ return 0;
+}
+
struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr)
{
return symbols__find(dso__symbols(dso), addr);
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index a6a2ab200f98..5a105b10a089 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -141,16 +141,16 @@ void symbol__set_annotate2(struct symbol *sym, bool annotate2);
void symbol__set_inlined(struct symbol *sym, bool inlined);
void symbol__set_ifunc_alias(struct symbol *sym, bool ifunc_alias);
-/* symbols__for_each_entry - iterate over symbols (rb_root)
+/*
+ * symbols__visit - iterate over symbols calling @cb for each entry
*
- * @symbols: the rb_root of symbols
- * @pos: the 'struct symbol *' to use as a loop cursor
- * @nd: the 'struct rb_node *' to use as a temporary storage
+ * @symbols: the rb_root_cached of symbols
+ * @cb: callback function invoked for each symbol
+ * @data: opaque data pointer passed to @cb
*/
-#define symbols__for_each_entry(symbols, pos, nd) \
- for (nd = rb_first_cached(symbols); \
- nd && (pos = rb_entry(nd, struct symbol, rb_node)); \
- nd = rb_next(nd))
+int symbols__visit(struct rb_root_cached *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data);
static inline size_t symbol__size(const struct symbol *sym)
{
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (2 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
` (6 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
Convert open-coded dso__first_symbol() / dso__next_symbol(),
rb_first_cached() / rb_next(), and dso__symbol_names() loops across
auxtrace, intel-pt, machine, dso, probe-event, symbol_fprintf, and
tests/symbols.c to use dso__for_each_symbol(), map__for_each_symbol(),
and a new dso__for_each_symbol_by_name() callback helper.
With no remaining callers, remove dso__first_symbol(), dso__last_symbol(),
and dso__next_symbol().
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/tests/symbols.c | 61 ++++++++++-------
tools/perf/util/auxtrace.c | 109 ++++++++++++++++++++-----------
tools/perf/util/dso.c | 34 ++++++----
tools/perf/util/dso.h | 3 +
tools/perf/util/intel-pt.c | 74 +++++++++++++--------
tools/perf/util/machine.c | 28 ++++----
tools/perf/util/probe-event.c | 16 +++--
tools/perf/util/symbol.c | 52 ++++-----------
tools/perf/util/symbol.h | 7 +-
tools/perf/util/symbol_fprintf.c | 25 +++++--
10 files changed, 239 insertions(+), 170 deletions(-)
diff --git a/tools/perf/tests/symbols.c b/tools/perf/tests/symbols.c
index d3180db45ee6..b73da581f895 100644
--- a/tools/perf/tests/symbols.c
+++ b/tools/perf/tests/symbols.c
@@ -116,39 +116,50 @@ static int create_map(struct test_info *ti, char *filename, struct map **map_p)
return TEST_OK;
}
+struct test_dso_args {
+ struct symbol *last_sym;
+ int ret;
+};
+
+static int test_dso_cb(struct symbol *sym, void *data)
+{
+ struct test_dso_args *args = data;
+ struct symbol *last_sym = args->last_sym;
+
+ if (symbol__type(sym) != STT_FUNC && symbol__type(sym) != STT_GNU_IFUNC)
+ return 0;
+
+ /* Check for overlapping function symbols */
+ if (last_sym && sym->start < last_sym->end) {
+ pr_debug("Overlapping symbols:\n");
+ symbol__fprintf(last_sym, stderr);
+ symbol__fprintf(sym, stderr);
+ args->ret = TEST_FAIL;
+ }
+ /* Check for zero-length function symbol */
+ if (sym->start == sym->end) {
+ pr_debug("Zero-length symbol:\n");
+ symbol__fprintf(sym, stderr);
+ args->ret = TEST_FAIL;
+ }
+ args->last_sym = sym;
+ return 0;
+}
+
static int test_dso(struct dso *dso)
{
- struct symbol *last_sym = NULL;
- struct rb_node *nd;
- int ret = TEST_OK;
+ struct test_dso_args args = {
+ .last_sym = NULL,
+ .ret = TEST_OK,
+ };
/* dso__fprintf() prints all the symbols */
if (verbose > 1)
dso__fprintf(dso, stderr);
- for (nd = rb_first_cached(dso__symbols(dso)); nd; nd = rb_next(nd)) {
- struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
+ dso__for_each_symbol(dso, test_dso_cb, &args);
- if (symbol__type(sym) != STT_FUNC && symbol__type(sym) != STT_GNU_IFUNC)
- continue;
-
- /* Check for overlapping function symbols */
- if (last_sym && sym->start < last_sym->end) {
- pr_debug("Overlapping symbols:\n");
- symbol__fprintf(last_sym, stderr);
- symbol__fprintf(sym, stderr);
- ret = TEST_FAIL;
- }
- /* Check for zero-length function symbol */
- if (sym->start == sym->end) {
- pr_debug("Zero-length symbol:\n");
- symbol__fprintf(sym, stderr);
- ret = TEST_FAIL;
- }
- last_sym = sym;
- }
-
- return ret;
+ return args.ret;
}
static int subdivided_dso_cb(struct dso *dso, struct machine *machine __maybe_unused, void *d)
diff --git a/tools/perf/util/auxtrace.c b/tools/perf/util/auxtrace.c
index 8bb491d389a2..fdffdf60983a 100644
--- a/tools/perf/util/auxtrace.c
+++ b/tools/perf/util/auxtrace.c
@@ -2713,61 +2713,96 @@ static bool dso_sym_match(struct symbol *sym, const char *name, int *cnt,
idx < 0);
}
+struct print_duplicate_syms_args {
+ const char *sym_name;
+ bool near;
+ int cnt;
+};
+
+static int print_duplicate_syms_cb(struct symbol *sym, void *data)
+{
+ struct print_duplicate_syms_args *args = data;
+
+ if (dso_sym_match(sym, args->sym_name, &args->cnt, -1)) {
+ pr_err("#%d\t0x%"PRIx64"\t%c\t%s\n",
+ ++args->cnt, sym->start,
+ symbol__binding(sym) == STB_GLOBAL ? 'g' :
+ symbol__binding(sym) == STB_LOCAL ? 'l' : 'w',
+ sym->name);
+ args->near = true;
+ } else if (args->near) {
+ args->near = false;
+ pr_err("\t\twhich is near\t\t%s\n", sym->name);
+ }
+ return 0;
+}
+
static void print_duplicate_syms(struct dso *dso, const char *sym_name)
{
- struct symbol *sym;
- bool near = false;
- int cnt = 0;
+ struct print_duplicate_syms_args args = {
+ .sym_name = sym_name,
+ .near = false,
+ .cnt = 0,
+ };
pr_err("Multiple symbols with name '%s'\n", sym_name);
- sym = dso__first_symbol(dso);
- while (sym) {
- if (dso_sym_match(sym, sym_name, &cnt, -1)) {
- pr_err("#%d\t0x%"PRIx64"\t%c\t%s\n",
- ++cnt, sym->start,
- symbol__binding(sym) == STB_GLOBAL ? 'g' :
- symbol__binding(sym) == STB_LOCAL ? 'l' : 'w',
- sym->name);
- near = true;
- } else if (near) {
- near = false;
- pr_err("\t\twhich is near\t\t%s\n", sym->name);
- }
- sym = dso__next_symbol(sym);
- }
+ dso__for_each_symbol(dso, print_duplicate_syms_cb, &args);
pr_err("Disambiguate symbol name by inserting #n after the name e.g. %s #2\n",
sym_name);
pr_err("Or select a global symbol by inserting #0 or #g or #G\n");
}
+struct find_dso_sym_args {
+ const char *sym_name;
+ u64 *start;
+ u64 *size;
+ int idx;
+ int cnt;
+ bool duplicate;
+};
+
+static int find_dso_sym_cb(struct symbol *sym, void *data)
+{
+ struct find_dso_sym_args *args = data;
+
+ if (*args->start) {
+ if (!*args->size)
+ *args->size = sym->start - *args->start;
+ if (args->idx > 0) {
+ if (*args->size)
+ return 1;
+ } else if (dso_sym_match(sym, args->sym_name, &args->cnt, args->idx)) {
+ args->duplicate = true;
+ return 1;
+ }
+ } else if (dso_sym_match(sym, args->sym_name, &args->cnt, args->idx)) {
+ *args->start = sym->start;
+ *args->size = sym->end - sym->start;
+ }
+ return 0;
+}
+
static int find_dso_sym(struct dso *dso, const char *sym_name, u64 *start,
u64 *size, int idx)
{
- struct symbol *sym;
- int cnt = 0;
+ struct find_dso_sym_args args = {
+ .sym_name = sym_name,
+ .start = start,
+ .size = size,
+ .idx = idx,
+ .cnt = 0,
+ .duplicate = false,
+ };
*start = 0;
*size = 0;
- sym = dso__first_symbol(dso);
- while (sym) {
- if (*start) {
- if (!*size)
- *size = sym->start - *start;
- if (idx > 0) {
- if (*size)
- return 0;
- } else if (dso_sym_match(sym, sym_name, &cnt, idx)) {
- print_duplicate_syms(dso, sym_name);
- return -EINVAL;
- }
- } else if (dso_sym_match(sym, sym_name, &cnt, idx)) {
- *start = sym->start;
- *size = sym->end - sym->start;
- }
- sym = dso__next_symbol(sym);
+ dso__for_each_symbol(dso, find_dso_sym_cb, &args);
+ if (args.duplicate) {
+ print_duplicate_syms(dso, sym_name);
+ return -EINVAL;
}
if (!*start)
diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index e46cd614eb21..73d22e5c8253 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -2011,22 +2011,34 @@ static size_t dso__fprintf_buildid(struct dso *dso, FILE *fp)
return fprintf(fp, "%s", sbuild_id);
}
+struct dso__fprintf_cb_args {
+ FILE *fp;
+ size_t ret;
+};
+
+static int dso__fprintf_cb(struct symbol *pos, void *data)
+{
+ struct dso__fprintf_cb_args *args = data;
+
+ args->ret += symbol__fprintf(pos, args->fp);
+ return 0;
+}
+
size_t dso__fprintf(struct dso *dso, FILE *fp)
{
- struct rb_node *nd;
- size_t ret = fprintf(fp, "dso: %s (", dso__short_name(dso));
+ struct dso__fprintf_cb_args args = {
+ .fp = fp,
+ .ret = fprintf(fp, "dso: %s (", dso__short_name(dso)),
+ };
if (dso__short_name(dso) != dso__long_name(dso))
- ret += fprintf(fp, "%s, ", dso__long_name(dso));
- ret += fprintf(fp, "%sloaded, ", dso__loaded(dso) ? "" : "NOT ");
- ret += dso__fprintf_buildid(dso, fp);
- ret += fprintf(fp, ")\n");
- for (nd = rb_first_cached(dso__symbols(dso)); nd; nd = rb_next(nd)) {
- struct symbol *pos = rb_entry(nd, struct symbol, rb_node);
- ret += symbol__fprintf(pos, fp);
- }
+ args.ret += fprintf(fp, "%s, ", dso__long_name(dso));
+ args.ret += fprintf(fp, "%sloaded, ", dso__loaded(dso) ? "" : "NOT ");
+ args.ret += dso__fprintf_buildid(dso, fp);
+ args.ret += fprintf(fp, ")\n");
+ dso__for_each_symbol(dso, dso__fprintf_cb, &args);
- return ret;
+ return args.ret;
}
enum dso_type dso__type(struct dso *dso, struct machine *machine)
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index 532ad3ec156f..ed5cea45897e 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -371,6 +371,9 @@ int dso_id__cmp(const struct dso_id *a, const struct dso_id *b);
#define dso__for_each_symbol(dso, cb, data) \
symbols__visit(dso__symbols(dso), cb, data)
+#define dso__for_each_symbol_by_name(dso, cb, data) \
+ dso__visit_symbols_by_name(dso, cb, data)
+
static inline void *dso__a2l(const struct dso *dso)
{
return RC_CHK_ACCESS(dso)->a2l;
diff --git a/tools/perf/util/intel-pt.c b/tools/perf/util/intel-pt.c
index e8b9c8a67b0a..9b7d315ca391 100644
--- a/tools/perf/util/intel-pt.c
+++ b/tools/perf/util/intel-pt.c
@@ -2988,13 +2988,37 @@ static int intel_pt_sample(struct intel_pt_queue *ptq)
return 0;
}
+struct intel_pt_switch_ip_args {
+ struct map *map;
+ const char *name;
+ bool check_global;
+ u64 ip;
+};
+
+static int intel_pt_switch_ip_cb(struct symbol *sym, void *data)
+{
+ struct intel_pt_switch_ip_args *args = data;
+ u64 ip;
+
+ if (args->check_global && symbol__binding(sym) != STB_GLOBAL)
+ return 0;
+
+ if (!strcmp(sym->name, args->name)) {
+ ip = map__unmap_ip(args->map, sym->start);
+ if (ip >= map__start(args->map) && ip < map__end(args->map)) {
+ args->ip = ip;
+ return 1;
+ }
+ }
+ return 0;
+}
+
static u64 intel_pt_switch_ip(struct intel_pt *pt, u64 *ptss_ip)
{
struct machine *machine = pt->machine;
struct map *map;
- struct symbol *sym, *start;
- u64 ip, switch_ip = 0;
- const char *ptss;
+ struct intel_pt_switch_ip_args args;
+ u64 switch_ip = 0;
if (ptss_ip)
*ptss_ip = 0;
@@ -3006,36 +3030,28 @@ static u64 intel_pt_switch_ip(struct intel_pt *pt, u64 *ptss_ip)
if (map__load(map))
return 0;
- start = dso__first_symbol(map__dso(map));
-
- for (sym = start; sym; sym = dso__next_symbol(sym)) {
- if (symbol__binding(sym) == STB_GLOBAL &&
- !strcmp(sym->name, "__switch_to")) {
- ip = map__unmap_ip(map, sym->start);
- if (ip >= map__start(map) && ip < map__end(map)) {
- switch_ip = ip;
- break;
- }
- }
- }
+ args = (struct intel_pt_switch_ip_args) {
+ .map = map,
+ .name = "__switch_to",
+ .check_global = true,
+ .ip = 0,
+ };
+ map__for_each_symbol(map, intel_pt_switch_ip_cb, &args);
+ switch_ip = args.ip;
if (!switch_ip || !ptss_ip)
return 0;
- if (pt->have_sched_switch == 1)
- ptss = "perf_trace_sched_switch";
- else
- ptss = "__perf_event_task_sched_out";
-
- for (sym = start; sym; sym = dso__next_symbol(sym)) {
- if (!strcmp(sym->name, ptss)) {
- ip = map__unmap_ip(map, sym->start);
- if (ip >= map__start(map) && ip < map__end(map)) {
- *ptss_ip = ip;
- break;
- }
- }
- }
+ args = (struct intel_pt_switch_ip_args) {
+ .map = map,
+ .name = pt->have_sched_switch == 1 ?
+ "perf_trace_sched_switch" :
+ "__perf_event_task_sched_out",
+ .check_global = false,
+ .ip = 0,
+ };
+ map__for_each_symbol(map, intel_pt_switch_ip_cb, &args);
+ *ptss_ip = args.ip;
return switch_ip;
}
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 5b4550e97172..1c417d012bcc 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -1121,29 +1121,35 @@ int machine__create_extra_kernel_map(struct machine *machine,
return err;
}
-static u64 find_entry_trampoline(struct dso *dso)
+static int find_entry_trampoline_cb(struct symbol *sym, void *data)
{
/* Duplicates are removed so lookup all aliases */
- const char *syms[] = {
+ static const char * const syms[] = {
"_entry_trampoline",
"__entry_trampoline_start",
"entry_SYSCALL_64_trampoline",
};
- struct symbol *sym = dso__first_symbol(dso);
- unsigned int i;
+ u64 *addr = data;
- for (; sym; sym = dso__next_symbol(sym)) {
- if (symbol__binding(sym) != STB_GLOBAL)
- continue;
- for (i = 0; i < ARRAY_SIZE(syms); i++) {
- if (!strcmp(sym->name, syms[i]))
- return sym->start;
+ if (symbol__binding(sym) != STB_GLOBAL)
+ return 0;
+ for (unsigned int i = 0; i < ARRAY_SIZE(syms); i++) {
+ if (!strcmp(sym->name, syms[i])) {
+ *addr = sym->start;
+ return 1;
}
}
-
return 0;
}
+static u64 find_entry_trampoline(struct dso *dso)
+{
+ u64 addr = 0;
+
+ dso__for_each_symbol(dso, find_entry_trampoline_cb, &addr);
+ return addr;
+}
+
/*
* These values can be used for kernels that do not have symbols for the entry
* trampolines in kallsyms.
diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c
index 3d506c09b749..e3f8e3cd68c0 100644
--- a/tools/perf/util/probe-event.c
+++ b/tools/perf/util/probe-event.c
@@ -3788,6 +3788,15 @@ void cleanup_perf_probe_events(struct perf_probe_event *pevs, int npevs)
}
}
+static int show_available_funcs_cb(struct symbol *pos, void *data)
+{
+ struct strfilter *_filter = data;
+
+ if (strfilter__compare(_filter, pos->name))
+ printf("%s\n", pos->name);
+ return 0;
+}
+
int show_available_funcs(const char *target, struct nsinfo *nsi,
struct strfilter *_filter, bool user)
{
@@ -3824,12 +3833,7 @@ int show_available_funcs(const char *target, struct nsinfo *nsi,
/* Show all (filtered) symbols */
setup_pager();
- for (size_t i = 0; i < dso__symbol_names_len(dso); i++) {
- struct symbol *pos = dso__symbol_names(dso)[i];
-
- if (strfilter__compare(_filter, pos->name))
- printf("%s\n", pos->name);
- }
+ dso__for_each_symbol_by_name(dso, show_available_funcs_cb, _filter);
end:
map__put(map);
exit_probe_symbol_maps();
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 1f7faae5a357..8e724f71aa94 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -451,36 +451,6 @@ static struct symbol *symbols__find(struct rb_root_cached *symbols, u64 ip)
return NULL;
}
-static struct symbol *symbols__first(struct rb_root_cached *symbols)
-{
- struct rb_node *n = rb_first_cached(symbols);
-
- if (n)
- return rb_entry(n, struct symbol, rb_node);
-
- return NULL;
-}
-
-static struct symbol *symbols__last(struct rb_root_cached *symbols)
-{
- struct rb_node *n = rb_last(&symbols->rb_root);
-
- if (n)
- return rb_entry(n, struct symbol, rb_node);
-
- return NULL;
-}
-
-static struct symbol *symbols__next(struct symbol *sym)
-{
- struct rb_node *n = rb_next(&sym->rb_node);
-
- if (n)
- return rb_entry(n, struct symbol, rb_node);
-
- return NULL;
-}
-
static int symbols__sort_name_cmp(const void *vlhs, const void *vrhs)
{
const struct symbol *lhs = *((const struct symbol **)vlhs);
@@ -637,19 +607,21 @@ struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr)
return symbols__find(dso__symbols(dso), addr);
}
-struct symbol *dso__first_symbol(struct dso *dso)
+int dso__visit_symbols_by_name(struct dso *dso,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data)
{
- return symbols__first(dso__symbols(dso));
-}
+ if (!dso)
+ return 0;
-struct symbol *dso__last_symbol(struct dso *dso)
-{
- return symbols__last(dso__symbols(dso));
-}
+ dso__sort_by_name(dso);
+ for (size_t i = 0; i < dso__symbol_names_len(dso); i++) {
+ int ret = cb(dso__symbol_names(dso)[i], data);
-struct symbol *dso__next_symbol(struct symbol *sym)
-{
- return symbols__next(sym);
+ if (ret)
+ return ret;
+ }
+ return 0;
}
struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx)
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 5a105b10a089..784c87b72f38 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -197,10 +197,9 @@ struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr);
struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx);
struct symbol *dso__find_symbol_by_name(struct dso *dso, const char *name, size_t *idx);
-
-struct symbol *dso__first_symbol(struct dso *dso);
-struct symbol *dso__last_symbol(struct dso *dso);
-struct symbol *dso__next_symbol(struct symbol *sym);
+int dso__visit_symbols_by_name(struct dso *dso,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data);
enum dso_type dso__type_fd(int fd);
diff --git a/tools/perf/util/symbol_fprintf.c b/tools/perf/util/symbol_fprintf.c
index 4dc8d5761f52..f818e7ad1519 100644
--- a/tools/perf/util/symbol_fprintf.c
+++ b/tools/perf/util/symbol_fprintf.c
@@ -59,15 +59,26 @@ size_t symbol__fprintf_symname(const struct symbol *sym, FILE *fp)
return __symbol__fprintf_symname_offs(sym, NULL, false, false, fp);
}
+struct fprintf_symbols_by_name_args {
+ FILE *fp;
+ size_t ret;
+};
+
+static int fprintf_symbols_by_name_cb(struct symbol *pos, void *data)
+{
+ struct fprintf_symbols_by_name_args *args = data;
+
+ args->ret += fprintf(args->fp, "%s\n", pos->name);
+ return 0;
+}
+
size_t dso__fprintf_symbols_by_name(struct dso *dso,
FILE *fp)
{
- size_t ret = 0;
-
- for (size_t i = 0; i < dso__symbol_names_len(dso); i++) {
- struct symbol *pos = dso__symbol_names(dso)[i];
+ struct fprintf_symbols_by_name_args args = {
+ .fp = fp,
+ };
- ret += fprintf(fp, "%s\n", pos->name);
- }
- return ret;
+ dso__for_each_symbol_by_name(dso, fprintf_symbols_by_name_cb, &args);
+ return args.ret;
}
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (3 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort Ian Rogers
` (5 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
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.
- Update symbols__visit() and symbols__visit_by_name() to iterate the
sorted arrays under symbols->lock.
- 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/builtin-annotate.c | 11 -
tools/perf/tests/hists_common.c | 5 +-
tools/perf/ui/browser.c | 3 +
tools/perf/ui/browsers/hists.c | 3 +-
tools/perf/ui/browsers/map.c | 62 +--
tools/perf/util/db-export.c | 4 +-
tools/perf/util/dso.c | 16 +-
tools/perf/util/dso.h | 59 +--
tools/perf/util/libbfd.c | 3 +-
tools/perf/util/machine.c | 2 +-
tools/perf/util/map.c | 36 +-
tools/perf/util/symbol-elf.c | 12 +-
tools/perf/util/symbol.c | 650 ++++++++++++++++++++++----------
tools/perf/util/symbol.h | 61 ++-
14 files changed, 588 insertions(+), 339 deletions(-)
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/tests/hists_common.c b/tools/perf/tests/hists_common.c
index 187f12f5bc21..0d3acb03e02c 100644
--- a/tools/perf/tests/hists_common.c
+++ b/tools/perf/tests/hists_common.c
@@ -146,7 +146,10 @@ struct machine *setup_fake_machine(struct machines *machines)
goto out;
}
- symbols__insert(dso__symbols(dso), sym);
+ if (symbols__insert(dso__symbols(dso), sym)) {
+ dso__put(dso);
+ goto out;
+ }
}
dso__put(dso);
diff --git a/tools/perf/ui/browser.c b/tools/perf/ui/browser.c
index 321187b204d3..c7451f640d1d 100644
--- a/tools/perf/ui/browser.c
+++ b/tools/perf/ui/browser.c
@@ -622,6 +622,9 @@ static int ui_browser__color_config(const char *var, const char *value,
void ui_browser__argv_seek(struct ui_browser *browser, off_t offset, int whence)
{
+ if (browser->nr_entries == 0)
+ return;
+
switch (whence) {
case SEEK_SET:
browser->top = browser->entries;
diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index 6f9d9f7aec91..ad6882744eba 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -2532,7 +2532,8 @@ static struct symbol *symbol__new_unresolved(u64 addr, struct map *map)
return NULL;
}
- dso__insert_symbol(map__dso(map), sym);
+ if (dso__insert_symbol(map__dso(map), sym))
+ return NULL;
}
return sym;
diff --git a/tools/perf/ui/browsers/map.c b/tools/perf/ui/browsers/map.c
index be7390156edd..51a71b20947f 100644
--- a/tools/perf/ui/browsers/map.c
+++ b/tools/perf/ui/browsers/map.c
@@ -24,7 +24,7 @@ struct map_browser {
static void map_browser__write(struct ui_browser *browser, void *nd, int row)
{
- struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
+ struct symbol *sym = *(struct symbol **)nd;
struct map_browser *mb = container_of(browser, struct map_browser, b);
bool current_entry = ui_browser__is_current_entry(browser, row);
int width;
@@ -56,17 +56,16 @@ static int map_browser__search(struct map_browser *browser)
sym = map__find_symbol_by_name(browser->map, target);
if (sym != NULL) {
- struct rb_node *nd;
- u32 idx = 0;
+ struct symbol **entries = browser->b.entries;
/*
- * Walk the map browser's symbol entries to find the matching
- * symbol node and its display row index, then position the
- * browser cursor at that entry.
+ * Scan the map browser's symbol entries to find the matching
+ * symbol and its display row index, then position the browser
+ * cursor at that entry.
*/
- for (nd = rb_first(browser->b.entries); nd; nd = rb_next(nd), ++idx) {
- if (&sym->rb_node == nd) {
- browser->b.top = nd;
+ for (u32 idx = 0; idx < browser->b.nr_entries; ++idx) {
+ if (entries[idx] == sym) {
+ browser->b.top = &entries[idx];
browser->b.index = browser->b.top_idx = idx;
break;
}
@@ -109,27 +108,48 @@ static int map_browser__run(struct map_browser *browser)
int map__browse(struct map *map)
{
+ struct symbols *symbols = dso__symbols(map__dso(map));
struct map_browser mb = {
.b = {
- .entries = dso__symbols(map__dso(map)),
- .refresh = ui_browser__rb_tree_refresh,
- .seek = ui_browser__rb_tree_seek,
+ .refresh = ui_browser__argv_refresh,
+ .seek = ui_browser__argv_seek,
.write = map_browser__write,
},
.map = map,
};
- struct rb_node *nd;
+ struct symbol **entries = NULL;
+ unsigned int nr_entries = 0;
char tmp[BITS_PER_LONG / 4];
u64 maxaddr = 0;
-
- for (nd = rb_first(mb.b.entries); nd; nd = rb_next(nd)) {
- struct symbol *pos = rb_entry(nd, struct symbol, rb_node);
-
- if (maxaddr < pos->end)
- maxaddr = pos->end;
- ++mb.b.nr_entries;
+ int ret;
+
+ /*
+ * Snapshot the DSO's sorted symbol array under symbols->lock for use
+ * with ui_browser__argv_refresh and ui_browser__argv_seek.
+ */
+ symbols__sort_read_lock(symbols);
+ nr_entries = symbols->cnt;
+ if (nr_entries > 0) {
+ entries = malloc(nr_entries * sizeof(*entries));
+ if (entries) {
+ for (unsigned int idx = 0; idx < nr_entries; idx++) {
+ struct symbol *pos = symbols->symbols[idx];
+
+ entries[idx] = pos;
+ if (maxaddr < pos->end)
+ maxaddr = pos->end;
+ }
+ } else {
+ nr_entries = 0;
+ }
}
+ up_read(&symbols->lock);
+
+ mb.b.entries = entries;
+ mb.b.nr_entries = nr_entries;
mb.addrlen = snprintf(tmp, sizeof(tmp), "%" PRIx64, maxaddr);
- return map_browser__run(&mb);
+ ret = map_browser__run(&mb);
+ free(entries);
+ return ret;
}
diff --git a/tools/perf/util/db-export.c b/tools/perf/util/db-export.c
index e7b807e968cf..b3790383237f 100644
--- a/tools/perf/util/db-export.c
+++ b/tools/perf/util/db-export.c
@@ -289,8 +289,8 @@ static int db_ids_from_al(struct db_export *dbe, struct addr_location *al,
if (!al->sym) {
al->sym = symbol__new(al->addr, 0, 0, 0, "unknown");
- if (al->sym)
- dso__insert_symbol(dso, al->sym);
+ if (al->sym && dso__insert_symbol(dso, al->sym))
+ al->sym = NULL;
}
if (al->sym) {
diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 73d22e5c8253..3d7db37ff095 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -1808,12 +1808,7 @@ bool dso__loaded(const struct dso *dso)
bool dso__sorted_by_name(const struct dso *dso)
{
- return RC_CHK_ACCESS(dso)->sorted_by_name;
-}
-
-void dso__set_sorted_by_name(struct dso *dso)
-{
- RC_CHK_ACCESS(dso)->sorted_by_name = true;
+ return RC_CHK_ACCESS(dso)->symbols.sorted_by_name;
}
struct dso *dso__new_id(const char *name, const struct dso_id *id)
@@ -1831,9 +1826,7 @@ struct dso *dso__new_id(const char *name, const struct dso_id *id)
dso->id = *id;
dso__set_long_name_id(res, dso->name, false);
dso__set_short_name(res, dso->name, false);
- dso->symbols = RB_ROOT_CACHED;
- dso->symbol_names = NULL;
- dso->symbol_names_len = 0;
+ symbols__init(&dso->symbols);
dso->inlined_nodes = RB_ROOT_CACHED;
dso->srclines = RB_ROOT_CACHED;
dso->data_types = RB_ROOT;
@@ -1844,7 +1837,6 @@ struct dso *dso__new_id(const char *name, const struct dso_id *id)
dso->is_64_bit = (sizeof(void *) == 8);
dso->loaded = 0;
dso->rel = 0;
- dso->sorted_by_name = 0;
dso->has_srcline = 1;
dso->a2l_fails = 1;
dso->kernel = DSO_SPACE__USER;
@@ -1878,9 +1870,7 @@ void dso__delete(struct dso *dso)
/* free inlines first, as they reference symbols */
inlines__tree_delete(&RC_CHK_ACCESS(dso)->inlined_nodes);
srcline__tree_delete(&RC_CHK_ACCESS(dso)->srclines);
- symbols__delete(&RC_CHK_ACCESS(dso)->symbols);
- RC_CHK_ACCESS(dso)->symbol_names_len = 0;
- zfree(&RC_CHK_ACCESS(dso)->symbol_names);
+ symbols__exit(&RC_CHK_ACCESS(dso)->symbols);
annotated_data_type__tree_delete(dso__data_types(dso));
global_var_type__tree_delete(dso__global_vars(dso));
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index ed5cea45897e..85880f49ddac 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -13,6 +13,7 @@
#include "build-id.h"
#include "debuginfo.h"
#include "mutex.h"
+#include "symbol.h"
#include <internal/rc_check.h>
struct machine;
@@ -287,18 +288,12 @@ struct auxtrace_cache;
DECLARE_RC_STRUCT(dso) {
struct mutex lock;
struct dsos *dsos;
- struct rb_root_cached symbols;
- struct symbol **symbol_names;
- size_t symbol_names_len;
+ struct symbols symbols;
struct rb_root_cached inlined_nodes;
struct rb_root_cached srclines;
struct rb_root data_types;
struct rb_root global_vars;
- struct {
- u64 addr;
- struct symbol *symbol;
- } last_find_result;
u64 text_offset;
u64 text_end;
const char *short_name;
@@ -351,7 +346,6 @@ DECLARE_RC_STRUCT(dso) {
u8 is_64_bit:1;
u8 bintype_searched:1;
u8 debuginfo_searched:1;
- bool sorted_by_name;
bool loaded;
u8 rel;
char name[];
@@ -372,7 +366,7 @@ int dso_id__cmp(const struct dso_id *a, const struct dso_id *b);
symbols__visit(dso__symbols(dso), cb, data)
#define dso__for_each_symbol_by_name(dso, cb, data) \
- dso__visit_symbols_by_name(dso, cb, data)
+ symbols__visit_by_name(dso__symbols(dso), cb, data)
static inline void *dso__a2l(const struct dso *dso)
{
@@ -601,26 +595,6 @@ static inline void dso__set_kernel(struct dso *dso, enum dso_space_type kernel)
RC_CHK_ACCESS(dso)->kernel = kernel;
}
-static inline u64 dso__last_find_result_addr(const struct dso *dso)
-{
- return RC_CHK_ACCESS(dso)->last_find_result.addr;
-}
-
-static inline void dso__set_last_find_result_addr(struct dso *dso, u64 addr)
-{
- RC_CHK_ACCESS(dso)->last_find_result.addr = addr;
-}
-
-static inline struct symbol *dso__last_find_result_symbol(const struct dso *dso)
-{
- return RC_CHK_ACCESS(dso)->last_find_result.symbol;
-}
-
-static inline void dso__set_last_find_result_symbol(struct dso *dso, struct symbol *symbol)
-{
- RC_CHK_ACCESS(dso)->last_find_result.symbol = symbol;
-}
-
static inline enum dso_load_errno *dso__load_errno(struct dso *dso)
{
return &RC_CHK_ACCESS(dso)->load_errno;
@@ -733,31 +707,11 @@ static inline struct rb_root *dso__global_vars(struct dso *dso)
return &RC_CHK_ACCESS(dso)->global_vars;
}
-static inline struct rb_root_cached *dso__symbols(struct dso *dso)
+static inline struct symbols *dso__symbols(struct dso *dso)
{
return &RC_CHK_ACCESS(dso)->symbols;
}
-static inline struct symbol **dso__symbol_names(struct dso *dso)
-{
- return RC_CHK_ACCESS(dso)->symbol_names;
-}
-
-static inline void dso__set_symbol_names(struct dso *dso, struct symbol **names)
-{
- RC_CHK_ACCESS(dso)->symbol_names = names;
-}
-
-static inline size_t dso__symbol_names_len(struct dso *dso)
-{
- return RC_CHK_ACCESS(dso)->symbol_names_len;
-}
-
-static inline void dso__set_symbol_names_len(struct dso *dso, size_t len)
-{
- RC_CHK_ACCESS(dso)->symbol_names_len = len;
-}
-
static inline const char *dso__symsrc_filename(const struct dso *dso)
{
return RC_CHK_ACCESS(dso)->symsrc_filename;
@@ -826,13 +780,12 @@ bool dso__loaded(const struct dso *dso);
static inline bool dso__has_symbols(const struct dso *dso)
{
- return !RB_EMPTY_ROOT(&RC_CHK_ACCESS(dso)->symbols.rb_root);
+ return RC_CHK_ACCESS(dso)->symbols.cnt > 0;
}
char *dso__filename_with_chroot(const struct dso *dso, const char *filename);
bool dso__sorted_by_name(const struct dso *dso);
-void dso__set_sorted_by_name(struct dso *dso);
void dso__sort_by_name(struct dso *dso);
int dso__swap_init(struct dso *dso, unsigned char eidata);
@@ -956,8 +909,6 @@ struct map *dso__new_map(const char *name);
struct dso *machine__findnew_kernel(struct machine *machine, const char *name,
const char *short_name, int dso_type);
-void dso__reset_find_symbol_cache(struct dso *dso);
-
size_t dso__fprintf_symbols_by_name(struct dso *dso, FILE *fp);
size_t dso__fprintf(struct dso *dso, FILE *fp);
diff --git a/tools/perf/util/libbfd.c b/tools/perf/util/libbfd.c
index 58cadc93e8b5..c78865690ebb 100644
--- a/tools/perf/util/libbfd.c
+++ b/tools/perf/util/libbfd.c
@@ -453,7 +453,8 @@ int dso__load_bfd_symbols(struct dso *dso, const char *debugfile)
if (!symbol)
goto out_free;
- symbols__insert(dso__symbols(dso), symbol);
+ if (symbols__insert(dso__symbols(dso), symbol))
+ goto out_free;
}
#ifdef bfd_get_section
#undef bfd_asymbol_section
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 1c417d012bcc..e8a3d8095346 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -818,7 +818,7 @@ static int machine__process_ksymbol_register(struct machine *machine,
err = -ENOMEM;
goto out;
}
- dso__insert_symbol(dso, sym);
+ err = dso__insert_symbol(dso, sym);
out:
map__put(map);
dso__put(dso);
diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index d5319ffa88a7..5c75741e4cb7 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -314,27 +314,35 @@ void map__put(struct map *map)
void map__fixup_start(struct map *map)
{
- struct dso *dso = map__dso(map);
- struct rb_root_cached *symbols = dso__symbols(dso);
- struct rb_node *nd = rb_first_cached(symbols);
-
- if (nd != NULL) {
- struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
+ struct symbols *symbols = dso__symbols(map__dso(map));
- map__set_start(map, sym->start);
- }
+ symbols__sort_read_lock(symbols);
+ if (symbols->cnt > 0)
+ map__set_start(map, symbols->symbols[0]->start);
+ up_read(&symbols->lock);
}
void map__fixup_end(struct map *map)
{
- struct dso *dso = map__dso(map);
- struct rb_root_cached *symbols = dso__symbols(dso);
- struct rb_node *nd = rb_last(&symbols->rb_root);
+ struct symbols *symbols = dso__symbols(map__dso(map));
- if (nd != NULL) {
- struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
- map__set_end(map, sym->end);
+ symbols__sort_read_lock(symbols);
+ if (symbols->cnt > 0) {
+ u64 last_start = symbols->symbols[symbols->cnt - 1]->start;
+ u64 end = symbols->symbols[symbols->cnt - 1]->end;
+
+ for (unsigned int i = symbols->cnt - 1; i > 0; i--) {
+ u64 sym_end;
+
+ if (symbols->symbols[i - 1]->start != last_start)
+ break;
+ sym_end = symbols->symbols[i - 1]->end;
+ if (sym_end > end)
+ end = sym_end;
+ }
+ map__set_end(map, end);
}
+ up_read(&symbols->lock);
}
#define DSO__DELETED "(deleted)"
diff --git a/tools/perf/util/symbol-elf.c b/tools/perf/util/symbol-elf.c
index 2b7f9e30916d..bda0b92ada24 100644
--- a/tools/perf/util/symbol-elf.c
+++ b/tools/perf/util/symbol-elf.c
@@ -698,7 +698,8 @@ static int dso__synthesize_plt_got_symbols(struct dso *dso, Elf *elf,
sym = symbol__new(shdr.sh_offset + i, shdr.sh_entsize, STB_GLOBAL, STT_FUNC, buf);
if (!sym)
goto out;
- symbols__insert(dso__symbols(dso), sym);
+ if (symbols__insert(dso__symbols(dso), sym))
+ goto out;
}
err = 0;
out:
@@ -752,7 +753,8 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss)
plt_sym = symbol__new(shdr_plt.sh_offset, plt_header_size, STB_GLOBAL, STT_FUNC, ".plt");
if (!plt_sym)
goto out_elf_end;
- symbols__insert(dso__symbols(dso), plt_sym);
+ if (symbols__insert(dso__symbols(dso), plt_sym))
+ goto out_elf_end;
/* Only x86 has .plt.got */
if (machine_is_x86(ehdr.e_machine) &&
@@ -874,7 +876,8 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss)
goto out_elf_end;
plt_offset += plt_entry_size;
- symbols__insert(dso__symbols(dso), f);
+ if (symbols__insert(dso__symbols(dso), f))
+ goto out_elf_end;
++nr;
}
@@ -1938,7 +1941,8 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
arch__sym_update(f, &sym);
- __symbols__insert(dso__symbols(curr_dso), f);
+ if (symbols__insert(dso__symbols(curr_dso), f))
+ goto out_elf_end;
nr++;
}
dso__put(curr_dso);
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 8e724f71aa94..4119e061e939 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -213,57 +213,167 @@ static int choose_best_symbol(struct symbol *syma, struct symbol *symb)
return arch__choose_best_symbol(syma, symb);
}
-void symbols__fixup_duplicate(struct rb_root_cached *symbols)
+void symbols__init(struct symbols *symbols)
{
- struct rb_node *nd;
- struct symbol *curr, *next;
+ init_rwsem(&symbols->lock);
+ symbols->symbols = NULL;
+ symbols->symbols_by_name = NULL;
+ symbols->cnt = 0;
+ symbols->allocated = 0;
+ symbols->num_by_name = 0;
+ symbols->sorted = true;
+ symbols->sorted_by_name = false;
+}
+
+static void symbols__delete_locked(struct symbols *symbols)
+{
+ for (unsigned int i = 0; i < symbols->cnt; i++)
+ symbol__delete(symbols->symbols[i]);
+
+ zfree(&symbols->symbols);
+ zfree(&symbols->symbols_by_name);
+ symbols->cnt = 0;
+ symbols->allocated = 0;
+ symbols->num_by_name = 0;
+ symbols->sorted = true;
+ symbols->sorted_by_name = false;
+}
+
+void symbols__delete(struct symbols *symbols)
+{
+ down_write(&symbols->lock);
+ symbols__delete_locked(symbols);
+ up_write(&symbols->lock);
+}
+
+void symbols__exit(struct symbols *symbols)
+{
+ symbols__delete(symbols);
+ exit_rwsem(&symbols->lock);
+}
+
+/*
+ * Order symbols by start address only, preserving insertion order among
+ * symbols sharing the same start address (matching the previous rbtree
+ * __symbols__insert() behavior so alias deduplication and IFUNC resolution
+ * remain unchanged).
+ */
+static inline bool symbol__less_or_equal(const struct symbol *a, const struct symbol *b)
+{
+ return a->start <= b->start;
+}
+
+static int symbols__sort_cmp(const void *vlhs, const void *vrhs)
+{
+ const struct symbol *lhs = *((const struct symbol **)vlhs);
+ const struct symbol *rhs = *((const struct symbol **)vrhs);
+
+ if (lhs->start != rhs->start)
+ return lhs->start < rhs->start ? -1 : 1;
+ return 0;
+}
+
+static void symbols__sort_locked(struct symbols *symbols)
+{
+ if (symbols->sorted)
+ return;
+
+ if (symbols->cnt > 1) {
+ qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
+ symbols__sort_cmp);
+ }
+ symbols->sorted = true;
+}
+
+/*
+ * Acquire @symbols->lock for reading after ensuring @symbols->symbols is
+ * sorted.
+ */
+void symbols__sort_read_lock(struct symbols *symbols)
+ NO_THREAD_SAFETY_ANALYSIS
+{
+ 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);
+ }
+}
+
+/*
+ * Deduplicate symbols sharing the same start address by sorting @symbols and
+ * compacting the array in place, keeping the best symbol at each address as
+ * chosen by choose_best_symbol().
+ */
+void symbols__fixup_duplicate(struct symbols *symbols)
+{
+ unsigned int write_idx = 0;
if (symbol_conf.allow_aliases)
return;
- nd = rb_first_cached(symbols);
+ down_write(&symbols->lock);
+ symbols__sort_locked(symbols);
+ if (symbols->cnt <= 1) {
+ up_write(&symbols->lock);
+ return;
+ }
- while (nd) {
- curr = rb_entry(nd, struct symbol, rb_node);
-again:
- nd = rb_next(&curr->rb_node);
- if (!nd)
- break;
+ for (unsigned int read_idx = 1; read_idx < symbols->cnt; read_idx++) {
+ struct symbol *curr = symbols->symbols[write_idx];
+ struct symbol *next = symbols->symbols[read_idx];
- next = rb_entry(nd, struct symbol, rb_node);
- if (curr->start != next->start)
+ if (curr->start != next->start) {
+ symbols->symbols[++write_idx] = next;
continue;
+ }
if (choose_best_symbol(curr, next) == SYMBOL_A) {
if (symbol__type(next) == STT_GNU_IFUNC)
symbol__set_ifunc_alias(curr, true);
- rb_erase_cached(&next->rb_node, symbols);
symbol__delete(next);
- goto again;
} else {
if (symbol__type(curr) == STT_GNU_IFUNC)
symbol__set_ifunc_alias(next, true);
- nd = rb_next(&curr->rb_node);
- rb_erase_cached(&curr->rb_node, symbols);
symbol__delete(curr);
+ symbols->symbols[write_idx] = next;
}
}
+ symbols->cnt = write_idx + 1;
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ up_write(&symbols->lock);
}
/* Update zero-sized symbols using the address of the next symbol */
-void symbols__fixup_end(struct rb_root_cached *symbols, bool is_kallsyms)
+void symbols__fixup_end(struct symbols *symbols, bool is_kallsyms)
{
- struct rb_node *nd, *prevnd = rb_first_cached(symbols);
struct symbol *curr, *prev;
+ bool addr_has_sized;
- if (prevnd == NULL)
+ down_write(&symbols->lock);
+ symbols__sort_locked(symbols);
+
+ if (symbols->cnt == 0) {
+ up_write(&symbols->lock);
return;
+ }
- curr = rb_entry(prevnd, struct symbol, rb_node);
+ curr = symbols->symbols[0];
+ addr_has_sized = curr->end > curr->start;
- for (nd = rb_next(prevnd); nd; nd = rb_next(nd)) {
+ for (unsigned int i = 1; i < symbols->cnt; i++) {
prev = curr;
- curr = rb_entry(nd, struct symbol, rb_node);
+ curr = symbols->symbols[i];
+
+ if (curr->start == prev->start) {
+ if (curr->end > curr->start)
+ addr_has_sized = true;
+ continue;
+ }
/*
* On some architecture kernel text segment start is located at
@@ -281,39 +391,42 @@ void symbols__fixup_end(struct rb_root_cached *symbols, bool is_kallsyms)
* like in:
* ffffffffc1937000 T hdmi_driver_init [snd_hda_codec_hdmi]
*/
- if (prev->end == prev->start) {
+ if (!addr_has_sized && prev->end == prev->start) {
const char *prev_mod;
const char *curr_mod;
if (!is_kallsyms) {
prev->end = curr->start;
- continue;
- }
-
- prev_mod = strchr(prev->name, '[');
- curr_mod = strchr(curr->name, '[');
-
- /* Last kernel/module symbol mapped to end of page */
- if (!prev_mod != !curr_mod)
- prev->end = roundup(prev->end + 4096, 4096);
- /* Last symbol in the previous module */
- else if (prev_mod && strcmp(prev_mod, curr_mod))
- prev->end = roundup(prev->end + 4096, 4096);
- else
- prev->end = curr->start;
+ } else {
+ prev_mod = strchr(prev->name, '[');
+ curr_mod = strchr(curr->name, '[');
+
+ /* Last kernel/module symbol mapped to end of page */
+ if (!prev_mod != !curr_mod) {
+ prev->end = roundup(prev->end + 4096, 4096);
+ /* Last symbol in the previous module */
+ } else if (prev_mod && strcmp(prev_mod, curr_mod)) {
+ prev->end = roundup(prev->end + 4096, 4096);
+ } else {
+ prev->end = curr->start;
+ }
- /* The next module can start within that page */
- if (prev->end > curr->start)
- prev->end = curr->start;
+ /* The next module can start within that page */
+ if (prev->end > curr->start)
+ prev->end = curr->start;
- pr_debug4("%s sym:%s end:%#" PRIx64 "\n",
- __func__, prev->name, prev->end);
+ pr_debug4("%s sym:%s end:%#" PRIx64 "\n",
+ __func__, prev->name, prev->end);
+ }
}
+ addr_has_sized = curr->end > curr->start;
}
/* Last entry */
- if (curr->end == curr->start)
+ if (!addr_has_sized && curr->end == curr->start)
curr->end = roundup(curr->start, 4096) + 4096;
+
+ up_write(&symbols->lock);
}
struct symbol *symbol__new(u64 start, u64 len, u8 binding, u8 type, const char *name)
@@ -388,67 +501,116 @@ static void symbol__set_idle(struct symbol *sym, bool idle)
new_flags |= (idle_val << SYMBOL_FLAG_IDLE_SHIFT);
} while (!atomic_compare_exchange_weak(&sym->flags, &old_flags, new_flags));
}
-void symbols__delete(struct rb_root_cached *symbols)
+
+static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
{
- struct symbol *pos;
- struct rb_node *next = rb_first_cached(symbols);
+ if (symbols->cnt == symbols->allocated) {
+ unsigned int to_allocate = symbols->allocated ? symbols->allocated * 2 : 32;
+ struct symbol **temp = realloc(symbols->symbols,
+ sizeof(struct symbol *) * to_allocate);
- while (next) {
- pos = rb_entry(next, struct symbol, rb_node);
- next = rb_next(&pos->rb_node);
- rb_erase_cached(&pos->rb_node, symbols);
- symbol__delete(pos);
+ if (!temp) {
+ symbol__delete(sym);
+ return -ENOMEM;
+ }
+ symbols->symbols = temp;
+ symbols->allocated = to_allocate;
}
+
+ if (symbols->sorted && symbols->cnt > 0 &&
+ !symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym))
+ symbols->sorted = false;
+
+ symbols->symbols[symbols->cnt++] = sym;
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ return 0;
}
-void __symbols__insert(struct rb_root_cached *symbols, struct symbol *sym)
+int symbols__insert(struct symbols *symbols, struct symbol *sym)
{
- struct rb_node **p = &symbols->rb_root.rb_node;
- struct rb_node *parent = NULL;
- const u64 ip = sym->start;
- struct symbol *s;
- bool leftmost = true;
+ int ret;
- while (*p != NULL) {
- parent = *p;
- s = rb_entry(parent, struct symbol, rb_node);
- if (ip < s->start)
- p = &(*p)->rb_left;
- else {
- p = &(*p)->rb_right;
- leftmost = false;
- }
- }
- rb_link_node(&sym->rb_node, parent, p);
- rb_insert_color_cached(&sym->rb_node, symbols, leftmost);
+ down_write(&symbols->lock);
+ ret = __symbols__insert(symbols, sym);
+ up_write(&symbols->lock);
+ return ret;
+}
+
+static inline bool symbol__covers(const struct symbol *s, u64 ip)
+{
+ u64 start = s->start;
+ u64 end = s->end;
+
+ return ip >= start && (ip < end || (ip == end && ip == start));
}
-void symbols__insert(struct rb_root_cached *symbols, struct symbol *sym)
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
{
- __symbols__insert(symbols, sym);
+ unsigned int low = 0, high = cnt, idx;
+ u64 start;
+
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (arr[mid]->start <= ip)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ if (low == 0)
+ return NULL;
+
+ /*
+ * Rewind across any equal-start group so a trailing zero-length or
+ * shorter alias at the same start address cannot mask an earlier
+ * covering symbol.
+ */
+ idx = low - 1;
+ start = arr[idx]->start;
+ while (idx > 0 && arr[idx - 1]->start == start)
+ idx--;
+ for (; idx < low; idx++) {
+ if (symbol__covers(arr[idx], ip))
+ return arr[idx];
+ }
+ return NULL;
}
-static struct symbol *symbols__find(struct rb_root_cached *symbols, u64 ip)
+/*
+ * Binary search @symbols->symbols for a symbol covering @ip. Lazily sorts
+ * @symbols under @symbols->lock if unsorted.
+ */
+static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
{
- struct rb_node *n;
+ struct symbol *res;
if (symbols == NULL)
return NULL;
- n = symbols->rb_root.rb_node;
+ symbols__sort_read_lock(symbols);
+ res = symbols__find_range(symbols->symbols, symbols->cnt, ip);
+ up_read(&symbols->lock);
- while (n) {
- struct symbol *s = rb_entry(n, struct symbol, rb_node);
+ return res;
+}
- if (ip < s->start)
- n = n->rb_left;
- else if (ip > s->end || (ip == s->end && ip != s->start))
- n = n->rb_right;
- else
- return s;
+int symbols__visit(struct symbols *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data)
+{
+ int err = 0;
+
+ symbols__sort_read_lock(symbols);
+ for (unsigned int i = 0; i < symbols->cnt; i++) {
+ err = cb(symbols->symbols[i], data);
+ if (err)
+ break;
}
+ up_read(&symbols->lock);
- return NULL;
+ return err;
}
static int symbols__sort_name_cmp(const void *vlhs, const void *vrhs)
@@ -459,27 +621,50 @@ static int symbols__sort_name_cmp(const void *vlhs, const void *vrhs)
return strcmp(lhs->name, rhs->name);
}
-static struct symbol **symbols__sort_by_name(struct rb_root_cached *source, size_t *len)
+static int symbols__sort_by_name_locked(struct symbols *symbols)
{
- struct rb_node *nd;
struct symbol **result;
- size_t i = 0, size = 0;
+ unsigned int size = symbols->cnt;
+
+ if (symbols->sorted_by_name)
+ return 0;
- for (nd = rb_first_cached(source); nd; nd = rb_next(nd))
- size++;
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+
+ if (size == 0) {
+ symbols->sorted_by_name = true;
+ return 0;
+ }
result = malloc(sizeof(*result) * size);
if (!result)
- return NULL;
+ return -ENOMEM;
+
+ memcpy(result, symbols->symbols, sizeof(*result) * size);
+ qsort(result, size, sizeof(*result), symbols__sort_name_cmp);
+ symbols->symbols_by_name = result;
+ symbols->num_by_name = size;
+ symbols->sorted_by_name = true;
+ return 0;
+}
- for (nd = rb_first_cached(source); nd; nd = rb_next(nd)) {
- struct symbol *pos = rb_entry(nd, struct symbol, rb_node);
+static int symbols__sort_by_name_read_lock(struct symbols *symbols)
+ SHARED_LOCK_FUNCTION(symbols->lock)
+{
+ int err = 0;
- result[i++] = pos;
+ down_read(&symbols->lock);
+ while (!symbols->sorted_by_name) {
+ up_read(&symbols->lock);
+ down_write(&symbols->lock);
+ err = symbols__sort_by_name_locked(symbols);
+ up_write(&symbols->lock);
+ down_read(&symbols->lock);
+ if (err)
+ break;
}
- qsort(result, size, sizeof(*result), symbols__sort_name_cmp);
- *len = size;
- return result;
+ return symbols->sorted_by_name ? 0 : err;
}
int symbol__match_symbol_name(const char *name, const char *str,
@@ -548,58 +733,34 @@ static struct symbol *symbols__find_by_name(struct symbol *symbols[],
return s;
}
-void dso__reset_find_symbol_cache(struct dso *dso)
-{
- dso__set_last_find_result_addr(dso, 0);
- dso__set_last_find_result_symbol(dso, NULL);
-}
-
-void dso__insert_symbol(struct dso *dso, struct symbol *sym)
+int dso__insert_symbol(struct dso *dso, struct symbol *sym)
{
- __symbols__insert(dso__symbols(dso), sym);
-
- /* update the symbol cache if necessary */
- if (dso__last_find_result_addr(dso) >= sym->start &&
- (dso__last_find_result_addr(dso) < sym->end ||
- sym->start == sym->end)) {
- dso__set_last_find_result_symbol(dso, sym);
- }
+ return symbols__insert(dso__symbols(dso), sym);
}
void dso__delete_symbol(struct dso *dso, struct symbol *sym)
{
- rb_erase_cached(&sym->rb_node, dso__symbols(dso));
- symbol__delete(sym);
- dso__reset_find_symbol_cache(dso);
-}
-
-struct symbol *dso__find_symbol(struct dso *dso, u64 addr)
-{
- if (dso__last_find_result_addr(dso) != addr || dso__last_find_result_symbol(dso) == NULL) {
- dso__set_last_find_result_addr(dso, addr);
- dso__set_last_find_result_symbol(dso, symbols__find(dso__symbols(dso), addr));
+ struct symbols *symbols = dso__symbols(dso);
+
+ down_write(&symbols->lock);
+ for (unsigned int i = 0; i < symbols->cnt; i++) {
+ if (symbols->symbols[i] == sym) {
+ memmove(&symbols->symbols[i], &symbols->symbols[i + 1],
+ (symbols->cnt - i - 1) * sizeof(struct symbol *));
+ symbols->cnt--;
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ symbol__delete(sym);
+ break;
+ }
}
-
- return dso__last_find_result_symbol(dso);
+ up_write(&symbols->lock);
}
-int symbols__visit(struct rb_root_cached *symbols,
- int (*cb)(struct symbol *sym, void *data),
- void *data)
+struct symbol *dso__find_symbol(struct dso *dso, u64 addr)
{
- struct rb_node *nd;
-
- if (!symbols)
- return 0;
-
- for (nd = rb_first_cached(symbols); nd; nd = rb_next(nd)) {
- struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
- int ret = cb(sym, data);
-
- if (ret)
- return ret;
- }
- return 0;
+ return symbols__find(dso__symbols(dso), addr);
}
struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr)
@@ -607,30 +768,23 @@ struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr)
return symbols__find(dso__symbols(dso), addr);
}
-int dso__visit_symbols_by_name(struct dso *dso,
- int (*cb)(struct symbol *sym, void *data),
- void *data)
+struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx)
{
- if (!dso)
- return 0;
+ struct symbols *symbols;
+ struct symbol *res = NULL;
- dso__sort_by_name(dso);
- for (size_t i = 0; i < dso__symbol_names_len(dso); i++) {
- int ret = cb(dso__symbol_names(dso)[i], data);
+ if (!dso)
+ return NULL;
- if (ret)
- return ret;
+ symbols = dso__symbols(dso);
+ if (!symbols__sort_by_name_read_lock(symbols) &&
+ *idx + 1 < symbols->num_by_name) {
+ ++*idx;
+ res = symbols->symbols_by_name[*idx];
}
- return 0;
-}
-
-struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx)
-{
- if (*idx + 1 >= dso__symbol_names_len(dso))
- return NULL;
+ up_read(&symbols->lock);
- ++*idx;
- return dso__symbol_names(dso)[*idx];
+ return res;
}
/*
@@ -638,29 +792,58 @@ struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx)
*/
struct symbol *dso__find_symbol_by_name(struct dso *dso, const char *name, size_t *idx)
{
- struct symbol *s = symbols__find_by_name(dso__symbol_names(dso),
- dso__symbol_names_len(dso),
- name, SYMBOL_TAG_INCLUDE__NONE, idx);
- if (!s) {
- s = symbols__find_by_name(dso__symbol_names(dso), dso__symbol_names_len(dso),
- name, SYMBOL_TAG_INCLUDE__DEFAULT_ONLY, idx);
+ struct symbols *symbols;
+ struct symbol *s = NULL;
+
+ if (idx)
+ *idx = SIZE_MAX;
+ if (!dso)
+ return NULL;
+ symbols = dso__symbols(dso);
+ if (!symbols__sort_by_name_read_lock(symbols)) {
+ s = symbols__find_by_name(symbols->symbols_by_name,
+ symbols->num_by_name,
+ name, SYMBOL_TAG_INCLUDE__NONE, idx);
+ if (!s) {
+ s = symbols__find_by_name(symbols->symbols_by_name, symbols->num_by_name,
+ name, SYMBOL_TAG_INCLUDE__DEFAULT_ONLY, idx);
+ }
}
+ up_read(&symbols->lock);
return s;
}
void dso__sort_by_name(struct dso *dso)
{
- mutex_lock(dso__lock(dso));
- if (!dso__sorted_by_name(dso)) {
- size_t len = 0;
+ struct symbols *symbols = dso__symbols(dso);
+
+ down_read(&symbols->lock);
+ if (!symbols->sorted_by_name) {
+ up_read(&symbols->lock);
+ down_write(&symbols->lock);
+ symbols__sort_by_name_locked(symbols);
+ up_write(&symbols->lock);
+ return;
+ }
+ up_read(&symbols->lock);
+}
- dso__set_symbol_names(dso, symbols__sort_by_name(dso__symbols(dso), &len));
- if (dso__symbol_names(dso)) {
- dso__set_symbol_names_len(dso, len);
- dso__set_sorted_by_name(dso);
+int symbols__visit_by_name(struct symbols *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data)
+{
+ int err = symbols__sort_by_name_read_lock(symbols);
+
+ if (!err) {
+ for (size_t i = 0; i < symbols->num_by_name; i++) {
+ err = cb(symbols->symbols_by_name[i], data);
+ if (err)
+ break;
}
}
- mutex_unlock(dso__lock(dso));
+ up_read(&symbols->lock);
+
+ return err;
}
/*
@@ -860,7 +1043,7 @@ static int map__process_kallsym_symbol(void *arg, const char *name,
{
struct symbol *sym;
struct dso *dso = arg;
- struct rb_root_cached *root = dso__symbols(dso);
+ struct symbols *root = dso__symbols(dso);
if (!symbol_type__filter(type))
return 0;
@@ -881,9 +1064,7 @@ static int map__process_kallsym_symbol(void *arg, const char *name,
* We will pass the symbols to the filter later, in
* map__split_kallsyms, when we have split the maps per module
*/
- __symbols__insert(root, sym);
-
- return 0;
+ return symbols__insert(root, sym);
}
/*
@@ -900,25 +1081,32 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso)
{
struct symbol *pos;
int count = 0;
- struct rb_root_cached *root = dso__symbols(dso);
- struct rb_root_cached old_root = *root;
- struct rb_node *next = rb_first_cached(root);
+ struct symbols *root = dso__symbols(dso);
+ struct symbol **old_symbols;
+ unsigned int old_cnt;
if (!kmaps)
return -1;
- *root = RB_ROOT_CACHED;
-
- while (next) {
+ down_write(&root->lock);
+ symbols__sort_locked(root);
+ old_symbols = root->symbols;
+ old_cnt = root->cnt;
+ root->symbols = NULL;
+ root->cnt = 0;
+ root->allocated = 0;
+ root->sorted = true;
+ zfree(&root->symbols_by_name);
+ root->num_by_name = 0;
+ root->sorted_by_name = false;
+ up_write(&root->lock);
+
+ for (unsigned int i = 0; i < old_cnt; i++) {
struct map *curr_map;
struct dso *curr_map_dso;
char *module;
- pos = rb_entry(next, struct symbol, rb_node);
- next = rb_next(&pos->rb_node);
-
- rb_erase_cached(&pos->rb_node, &old_root);
- RB_CLEAR_NODE(&pos->rb_node);
+ pos = old_symbols[i];
module = strchr(pos->name, '\t');
if (module)
*module = '\0';
@@ -935,11 +1123,13 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso)
pos->end = map__end(curr_map);
if (pos->end)
pos->end -= map__start(curr_map) - map__pgoff(curr_map);
- symbols__insert(dso__symbols(curr_map_dso), pos);
- ++count;
+ if (symbols__insert(dso__symbols(curr_map_dso), pos) == 0)
+ ++count;
map__put(curr_map);
}
+ free(old_symbols);
+
/* Symbols have been adjusted */
dso__set_adjust_symbols(dso, true);
@@ -958,8 +1148,10 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
struct map *curr_map = map__get(initial_map);
struct symbol *pos;
int count = 0, moved = 0;
- struct rb_root_cached *root = dso__symbols(dso);
- struct rb_node *next = rb_first_cached(root);
+ struct symbols *root = dso__symbols(dso);
+ struct symbol **old_symbols;
+ unsigned int old_cnt, old_allocated;
+ unsigned int i, write_idx = 0;
int kernel_range = 0;
uint16_t e_machine = EM_NONE;
@@ -969,11 +1161,24 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
machine = maps__machine(kmaps);
e_machine = perf_env__e_machine(machine->env, /*e_flags=*/NULL);
- while (next) {
+ down_write(&root->lock);
+ symbols__sort_locked(root);
+ old_symbols = root->symbols;
+ old_cnt = root->cnt;
+ old_allocated = root->allocated;
+ root->symbols = NULL;
+ root->cnt = 0;
+ root->allocated = 0;
+ root->sorted = true;
+ zfree(&root->symbols_by_name);
+ root->num_by_name = 0;
+ root->sorted_by_name = false;
+ up_write(&root->lock);
+
+ for (i = 0; i < old_cnt; i++) {
char *module;
- pos = rb_entry(next, struct symbol, rb_node);
- next = rb_next(&pos->rb_node);
+ pos = old_symbols[i];
module = strchr(pos->name, '\t');
if (module) {
@@ -1058,7 +1263,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
ndso = dso__new(dso_name);
map__zput(curr_map);
if (ndso == NULL)
- return -1;
+ goto out_err;
dso__set_kernel(ndso, dso__kernel(dso));
if (dso__kernel(dso) == DSO_SPACE__KERNEL_GUEST) {
@@ -1073,14 +1278,14 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
curr_map = map__new2(pos->start, ndso);
if (curr_map == NULL) {
dso__put(ndso);
- return -1;
+ goto out_err;
}
map__set_mapping_type(curr_map, MAPPING_TYPE__IDENTITY);
if (maps__insert(kmaps, curr_map)) {
map__zput(curr_map);
dso__put(ndso);
- return -1;
+ goto out_err;
}
dso__put(ndso);
++kernel_range;
@@ -1093,18 +1298,35 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
if (!RC_CHK_EQUAL(curr_map, initial_map)) {
struct dso *curr_map_dso = map__dso(curr_map);
- rb_erase_cached(&pos->rb_node, root);
- symbols__insert(dso__symbols(curr_map_dso), pos);
- ++moved;
- } else
+ if (symbols__insert(dso__symbols(curr_map_dso), pos) == 0)
+ ++moved;
+ } else {
+ old_symbols[write_idx++] = pos;
++count;
+ }
continue;
discard_symbol:
- rb_erase_cached(&pos->rb_node, root);
symbol__delete(pos);
}
+ down_write(&root->lock);
+ if (root->cnt == 0) {
+ root->symbols = old_symbols;
+ root->cnt = write_idx;
+ root->allocated = old_allocated;
+ root->sorted = true;
+ old_symbols = NULL;
+ } else {
+ for (unsigned int j = 0; j < write_idx; j++)
+ __symbols__insert(root, old_symbols[j]);
+ }
+ zfree(&root->symbols_by_name);
+ root->num_by_name = 0;
+ root->sorted_by_name = false;
+ up_write(&root->lock);
+ free(old_symbols);
+
if (!RC_CHK_EQUAL(curr_map, initial_map) &&
dso__kernel(dso) == DSO_SPACE__KERNEL_GUEST &&
machine__is_default_guest(maps__machine(kmaps))) {
@@ -1112,6 +1334,29 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
}
map__put(curr_map);
return count + moved;
+
+out_err:
+ memmove(&old_symbols[write_idx], &old_symbols[i],
+ (old_cnt - i) * sizeof(struct symbol *));
+ write_idx += old_cnt - i;
+ down_write(&root->lock);
+ if (root->cnt == 0) {
+ root->symbols = old_symbols;
+ root->cnt = write_idx;
+ root->allocated = old_allocated;
+ root->sorted = (delta == 0);
+ old_symbols = NULL;
+ } else {
+ for (unsigned int j = 0; j < write_idx; j++)
+ __symbols__insert(root, old_symbols[j]);
+ root->sorted = false;
+ }
+ zfree(&root->symbols_by_name);
+ root->num_by_name = 0;
+ root->sorted_by_name = false;
+ up_write(&root->lock);
+ free(old_symbols);
+ return -1;
}
bool symbol__restricted_filename(const char *filename,
@@ -1672,7 +1917,8 @@ static int dso__load_perf_map(const char *map_path, struct dso *dso)
if (sym == NULL)
goto out_delete_line;
- symbols__insert(dso__symbols(dso), sym);
+ if (symbols__insert(dso__symbols(dso), sym))
+ goto out_delete_line;
nr_syms++;
}
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 784c87b72f38..9d7de66cc284 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -15,6 +15,7 @@
#include <errno.h>
#include "addr_location.h"
#include "path.h"
+#include "rwsem.h"
#include "symbol_conf.h"
#include "spark.h"
#include "util.h"
@@ -82,7 +83,6 @@ enum symbol_idle_kind {
* A symtab entry.
*/
struct symbol {
- struct rb_node rb_node;
/** Range of symbol [start, end). */
u64 start;
u64 end;
@@ -95,8 +95,42 @@ struct symbol {
char name[];
};
+/**
+ * struct symbols - A locked collection of symbols stored in a sorted array.
+ */
+struct symbols {
+ /** @lock: Read/write semaphore synchronizing access to the arrays. */
+ struct rw_semaphore lock;
+ /**
+ * @symbols: Dynamically allocated array of symbol pointers, sorted by
+ * address range [start, end) when @sorted is true.
+ */
+ struct symbol **symbols;
+ /**
+ * @symbols_by_name: Optional dynamically allocated array of symbol
+ * pointers sorted lexicographically by sym->name.
+ */
+ struct symbol **symbols_by_name;
+ /** @cnt: Number of valid entries in @symbols. */
+ unsigned int cnt;
+ /** @allocated: Capacity (in entries) of the @symbols allocation. */
+ unsigned int allocated;
+ /** @num_by_name: Number of valid entries in @symbols_by_name. */
+ unsigned int num_by_name;
+ /** @sorted: True when @symbols is sorted by address range. */
+ bool sorted;
+ /**
+ * @sorted_by_name: True when @symbols_by_name is populated and sorted
+ * by name.
+ */
+ bool sorted_by_name;
+};
+
void symbol__delete(struct symbol *sym);
-void symbols__delete(struct rb_root_cached *symbols);
+void symbols__init(struct symbols *symbols);
+void symbols__exit(struct symbols *symbols);
+void symbols__delete(struct symbols *symbols);
+void symbols__sort_read_lock(struct symbols *symbols) SHARED_LOCK_FUNCTION(symbols->lock);
static inline u8 symbol__type(const struct symbol *sym)
{
@@ -144,13 +178,16 @@ void symbol__set_ifunc_alias(struct symbol *sym, bool ifunc_alias);
/*
* symbols__visit - iterate over symbols calling @cb for each entry
*
- * @symbols: the rb_root_cached of symbols
- * @cb: callback function invoked for each symbol
+ * @symbols: the 'struct symbols *' of symbols
+ * @cb: callback function invoked under @symbols->lock
* @data: opaque data pointer passed to @cb
*/
-int symbols__visit(struct rb_root_cached *symbols,
+int symbols__visit(struct symbols *symbols,
int (*cb)(struct symbol *sym, void *data),
void *data);
+int symbols__visit_by_name(struct symbols *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data);
static inline size_t symbol__size(const struct symbol *sym)
{
@@ -187,8 +224,8 @@ int __dso__load_kallsyms(struct dso *dso, const char *filename, struct map *map,
bool no_kcore);
int dso__load_kallsyms(struct dso *dso, const char *filename, struct map *map);
-void dso__insert_symbol(struct dso *dso,
- struct symbol *sym);
+int dso__insert_symbol(struct dso *dso,
+ struct symbol *sym);
void dso__delete_symbol(struct dso *dso,
struct symbol *sym);
@@ -197,9 +234,6 @@ struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr);
struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx);
struct symbol *dso__find_symbol_by_name(struct dso *dso, const char *name, size_t *idx);
-int dso__visit_symbols_by_name(struct dso *dso,
- int (*cb)(struct symbol *sym, void *data),
- void *data);
enum dso_type dso__type_fd(int fd);
@@ -251,10 +285,9 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss);
char *dso__demangle_sym(struct dso *dso, int kmodule, const char *elf_name);
-void __symbols__insert(struct rb_root_cached *symbols, struct symbol *sym);
-void symbols__insert(struct rb_root_cached *symbols, struct symbol *sym);
-void symbols__fixup_duplicate(struct rb_root_cached *symbols);
-void symbols__fixup_end(struct rb_root_cached *symbols, bool is_kallsyms);
+int symbols__insert(struct symbols *symbols, struct symbol *sym);
+void symbols__fixup_duplicate(struct symbols *symbols);
+void symbols__fixup_end(struct symbols *symbols, bool is_kallsyms);
typedef int (*mapfn_t)(u64 start, u64 len, u64 pgoff, void *data);
int file__read_maps(int fd, bool exe, mapfn_t mapfn, void *data,
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (4 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
` (4 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
ELF .symtab and .dynsym sections are typically already mostly ordered by
address in ascending runs. Invoking full-array qsort() across pre-ordered
ELF runs spends avoidable CPU time in symbol comparisons and does not
guarantee relative order preservation for equal-start symbol aliases
across C library implementations.
Replace qsort() in symbols__sort_locked() with a stable natural-run merge
sort (symbols__sort_range_with_tmp() and symbols__merge_runs()), falling
back to in-place binary insertion sort (symbols__insertion_sort_range())
for small arrays (cnt <= 64) or on scratch-buffer allocation failure.
Using 'perf bench internals symbols':
Before:
Average DSO load + sort: 6.242 msec (+- 0.057 msec)
Average bulk insert + lookup: 1404.150 usec (+- 18.752 usec)
After (-7.0% load, -13.9% bulk):
Average DSO load + sort: 5.808 msec (+- 0.047 msec)
Average bulk insert + lookup: 1209.250 usec (+- 18.446 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/symbol.c | 183 +++++++++++++++++++++++++++++++++++++--
1 file changed, 174 insertions(+), 9 deletions(-)
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 4119e061e939..114fe5ea3891 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -263,14 +263,171 @@ static inline bool symbol__less_or_equal(const struct symbol *a, const struct sy
return a->start <= b->start;
}
-static int symbols__sort_cmp(const void *vlhs, const void *vrhs)
+static unsigned int symbols__upper_bound(struct symbol **arr, unsigned int len,
+ const struct symbol *sym)
{
- const struct symbol *lhs = *((const struct symbol **)vlhs);
- const struct symbol *rhs = *((const struct symbol **)vrhs);
+ unsigned int low = 0, high = len;
- if (lhs->start != rhs->start)
- return lhs->start < rhs->start ? -1 : 1;
- return 0;
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (symbol__less_or_equal(arr[mid], sym))
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ return low;
+}
+
+static void symbols__insertion_sort_range(struct symbol **arr,
+ unsigned int start,
+ unsigned int end)
+{
+ for (unsigned int i = start + 1; i < end; i++) {
+ struct symbol *sym = arr[i];
+
+ if (!symbol__less_or_equal(arr[i - 1], sym)) {
+ unsigned int pos = start +
+ symbols__upper_bound(&arr[start], i - start, sym);
+
+ memmove(&arr[pos + 1], &arr[pos],
+ (i - pos) * sizeof(struct symbol *));
+ arr[pos] = sym;
+ }
+ }
+}
+
+static void symbols__merge_runs(struct symbol **arr,
+ unsigned int left,
+ unsigned int mid,
+ unsigned int right,
+ struct symbol **tmp)
+{
+ unsigned int first_left, left_len, right_len;
+ unsigned int i, j, dst;
+
+ if (left >= mid || mid >= right)
+ return;
+ if (symbol__less_or_equal(arr[mid - 1], arr[mid]))
+ return;
+
+ first_left = left + symbols__upper_bound(&arr[left], mid - left, arr[mid]);
+ left_len = mid - first_left;
+ right_len = right - mid;
+
+ if (left_len <= right_len) {
+ memcpy(tmp, &arr[first_left], left_len * sizeof(struct symbol *));
+ i = 0;
+ j = mid;
+ dst = first_left;
+ while (i < left_len && j < right) {
+ if (symbol__less_or_equal(tmp[i], arr[j]))
+ arr[dst++] = tmp[i++];
+ else
+ arr[dst++] = arr[j++];
+ }
+ if (i < left_len)
+ memcpy(&arr[dst], &tmp[i], (left_len - i) * sizeof(struct symbol *));
+ } else {
+ memcpy(tmp, &arr[mid], right_len * sizeof(struct symbol *));
+ i = mid;
+ j = right_len;
+ dst = right;
+ while (i > first_left && j > 0) {
+ if (symbol__less_or_equal(arr[i - 1], tmp[j - 1]))
+ arr[--dst] = tmp[--j];
+ else
+ arr[--dst] = arr[--i];
+ }
+ if (j > 0)
+ memcpy(&arr[first_left], tmp, j * sizeof(struct symbol *));
+ }
+}
+
+struct symbol_run {
+ unsigned int start;
+ unsigned int len;
+};
+
+static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
+ struct symbol **tmp)
+{
+ struct symbol_run runs[64];
+ unsigned int nr_runs = 0;
+ unsigned int i = 0;
+
+ if (n <= 32) {
+ symbols__insertion_sort_range(arr, 0, n);
+ return;
+ }
+
+ while (i < n) {
+ unsigned int start = i++;
+
+ if (i < n) {
+ if (symbol__less_or_equal(arr[i - 1], arr[i])) {
+ while (i < n && symbol__less_or_equal(arr[i - 1], arr[i]))
+ i++;
+ } else {
+ while (i < n && !symbol__less_or_equal(arr[i - 1], arr[i]))
+ i++;
+ for (unsigned int lo = start, hi = i - 1; lo < hi; lo++, hi--) {
+ struct symbol *swap = arr[lo];
+
+ arr[lo] = arr[hi];
+ arr[hi] = swap;
+ }
+ }
+ }
+
+ if (i - start < 32 && i < n) {
+ i = min(start + 32U, n);
+ symbols__insertion_sort_range(arr, start, i);
+ }
+
+ runs[nr_runs++] = (struct symbol_run){
+ .start = start,
+ .len = i - start,
+ };
+
+ while (nr_runs > 1) {
+ unsigned int r = nr_runs - 2;
+
+ if (nr_runs >= 3 &&
+ runs[nr_runs - 3].len <=
+ runs[nr_runs - 2].len + runs[nr_runs - 1].len) {
+ if (runs[nr_runs - 3].len < runs[nr_runs - 1].len)
+ r = nr_runs - 3;
+ } else if (runs[nr_runs - 2].len > runs[nr_runs - 1].len &&
+ nr_runs < ARRAY_SIZE(runs)) {
+ break;
+ }
+
+ symbols__merge_runs(arr, runs[r].start,
+ runs[r + 1].start,
+ runs[r + 1].start + runs[r + 1].len,
+ tmp);
+ runs[r].len += runs[r + 1].len;
+ if (r + 2 < nr_runs)
+ runs[r + 1] = runs[r + 2];
+ nr_runs--;
+ }
+ }
+
+ while (nr_runs > 1) {
+ unsigned int r = nr_runs - 2;
+
+ if (nr_runs >= 3 && runs[nr_runs - 3].len < runs[nr_runs - 1].len)
+ r = nr_runs - 3;
+ symbols__merge_runs(arr, runs[r].start,
+ runs[r + 1].start,
+ runs[r + 1].start + runs[r + 1].len,
+ tmp);
+ runs[r].len += runs[r + 1].len;
+ if (r + 2 < nr_runs)
+ runs[r + 1] = runs[r + 2];
+ nr_runs--;
+ }
}
static void symbols__sort_locked(struct symbols *symbols)
@@ -278,9 +435,17 @@ static void symbols__sort_locked(struct symbols *symbols)
if (symbols->sorted)
return;
- if (symbols->cnt > 1) {
- qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
- symbols__sort_cmp);
+ if (symbols->cnt <= 64) {
+ symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ } else {
+ struct symbol **tmp = malloc(((symbols->cnt + 1) / 2) * sizeof(struct symbol *));
+
+ if (tmp) {
+ symbols__sort_range_with_tmp(symbols->symbols, symbols->cnt, tmp);
+ free(tmp);
+ } else {
+ symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ }
}
symbols->sorted = true;
}
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (5 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:26 ` sashiko-bot
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
` (3 subsequent siblings)
10 siblings, 1 reply; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
Dynamic symbol resolution (dso__insert_symbol()) frequently inserts one
or a few symbols into an already-sorted DSO symbol table, and small
batches of symbols may also be appended after an initial sort.
Re-running full-array merge sort on every incremental insertion or
memmoving the entire sorted array on every out-of-order dynamic
insertion spends avoidable CPU time.
Speed up incremental symbol insertions and small-append sorting:
- Track the sorted prefix length (@sorted_cnt) in struct symbols and use
an O(N) in-place binary insertion fast path in symbols__sort_locked()
when <= 8 symbols have been appended.
- Add __symbols__insert_sorted() for dso__insert_symbol() so that when
symbols->sorted is true, ascending symbols append in O(1), small
tables (cnt < 64) binary-insert in place, and larger out-of-order
insertions maintain a sorted tail buffer at symbols[sorted_cnt .. cnt)
with an amortized sqrt(N) merge threshold.
- Search both the sorted prefix and any unmerged sorted tail in
symbols__find() while preserving the single-array highest start <= ip
semantics.
Using 'perf bench internals symbols':
Before:
Average append + lookup: 40429.750 usec (+- 507.578 usec)
After (-99.6%):
Average append + lookup: 152.900 usec (+- 0.736 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/symbol.c | 192 ++++++++++++++++++++++++++++++++++++---
tools/perf/util/symbol.h | 11 ++-
2 files changed, 189 insertions(+), 14 deletions(-)
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 114fe5ea3891..0eaeced63cd4 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -219,6 +219,7 @@ void symbols__init(struct symbols *symbols)
symbols->symbols = NULL;
symbols->symbols_by_name = NULL;
symbols->cnt = 0;
+ symbols->sorted_cnt = 0;
symbols->allocated = 0;
symbols->num_by_name = 0;
symbols->sorted = true;
@@ -233,6 +234,7 @@ static void symbols__delete_locked(struct symbols *symbols)
zfree(&symbols->symbols);
zfree(&symbols->symbols_by_name);
symbols->cnt = 0;
+ symbols->sorted_cnt = 0;
symbols->allocated = 0;
symbols->num_by_name = 0;
symbols->sorted = true;
@@ -432,12 +434,47 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
static void symbols__sort_locked(struct symbols *symbols)
{
- if (symbols->sorted)
+ unsigned int m = symbols->sorted_cnt;
+ unsigned int k;
+
+ if (symbols->sorted && symbols->sorted_cnt == symbols->cnt)
+ return;
+
+ if (m > symbols->cnt)
+ m = 0;
+ k = symbols->cnt - m;
+
+ if (k == 0) {
+ symbols->sorted = true;
return;
+ }
- if (symbols->cnt <= 64) {
+ /*
+ * When only a few symbols have been appended since the last sort
+ * (including single-symbol insertions), insert them directly at
+ * their binary-searched sorted positions in O(N) without allocating.
+ */
+ if (k <= 8 || symbols->cnt <= 64) {
symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
- } else {
+ symbols->sorted_cnt = symbols->cnt;
+ symbols->sorted = true;
+ return;
+ }
+
+ if (symbols->sorted) {
+ /*
+ * Both [0 .. m) and the sorted tail [m .. cnt) are already
+ * sorted; merge them into a single sorted run.
+ */
+ struct symbol **tmp = malloc(min(m, k) * sizeof(struct symbol *));
+
+ if (tmp) {
+ symbols__merge_runs(symbols->symbols, 0, m, symbols->cnt, tmp);
+ free(tmp);
+ } else {
+ symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ }
+ } else if (m <= 1) {
struct symbol **tmp = malloc(((symbols->cnt + 1) / 2) * sizeof(struct symbol *));
if (tmp) {
@@ -446,19 +483,31 @@ static void symbols__sort_locked(struct symbols *symbols)
} else {
symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
}
+ } else {
+ struct symbol **tmp = malloc(k * sizeof(struct symbol *));
+
+ if (tmp) {
+ symbols__sort_range_with_tmp(&symbols->symbols[m], k, tmp);
+ symbols__merge_runs(symbols->symbols, 0, m, symbols->cnt, tmp);
+ free(tmp);
+ } else {
+ symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
+ }
}
+
+ symbols->sorted_cnt = symbols->cnt;
symbols->sorted = true;
}
/*
* Acquire @symbols->lock for reading after ensuring @symbols->symbols is
- * sorted.
+ * fully sorted into a single contiguous run.
*/
void symbols__sort_read_lock(struct symbols *symbols)
NO_THREAD_SAFETY_ANALYSIS
{
down_read(&symbols->lock);
- while (!symbols->sorted) {
+ while (!symbols->sorted || symbols->sorted_cnt < symbols->cnt) {
up_read(&symbols->lock);
down_write(&symbols->lock);
symbols__sort_locked(symbols);
@@ -507,6 +556,7 @@ void symbols__fixup_duplicate(struct symbols *symbols)
}
}
symbols->cnt = write_idx + 1;
+ symbols->sorted_cnt = symbols->cnt;
zfree(&symbols->symbols_by_name);
symbols->num_by_name = 0;
symbols->sorted_by_name = false;
@@ -682,9 +732,15 @@ static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
symbols->allocated = to_allocate;
}
- if (symbols->sorted && symbols->cnt > 0 &&
- !symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym))
+ if (symbols->sorted && symbols->sorted_cnt == symbols->cnt) {
+ if (symbols->cnt == 0 ||
+ symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym))
+ symbols->sorted_cnt = symbols->cnt + 1;
+ else
+ symbols->sorted = false;
+ } else {
symbols->sorted = false;
+ }
symbols->symbols[symbols->cnt++] = sym;
zfree(&symbols->symbols_by_name);
@@ -693,6 +749,69 @@ static int __symbols__insert(struct symbols *symbols, struct symbol *sym)
return 0;
}
+static int __symbols__insert_sorted(struct symbols *symbols, struct symbol *sym)
+{
+ unsigned int idx;
+
+ if (!symbols->sorted)
+ return __symbols__insert(symbols, sym);
+
+ if (symbols->cnt == symbols->allocated) {
+ unsigned int to_allocate = symbols->allocated ? symbols->allocated * 2 : 32;
+ struct symbol **temp = realloc(symbols->symbols,
+ sizeof(struct symbol *) * to_allocate);
+
+ if (!temp) {
+ symbol__delete(sym);
+ return -ENOMEM;
+ }
+ symbols->symbols = temp;
+ symbols->allocated = to_allocate;
+ }
+
+ if (symbols->sorted_cnt == symbols->cnt) {
+ if (symbols->cnt == 0 ||
+ symbol__less_or_equal(symbols->symbols[symbols->cnt - 1], sym)) {
+ symbols->symbols[symbols->cnt++] = sym;
+ symbols->sorted_cnt = symbols->cnt;
+ } else if (symbols->cnt < 64) {
+ idx = symbols__upper_bound(symbols->symbols, symbols->cnt, sym);
+ memmove(&symbols->symbols[idx + 1], &symbols->symbols[idx],
+ (symbols->cnt - idx) * sizeof(struct symbol *));
+ symbols->symbols[idx] = sym;
+ symbols->cnt++;
+ symbols->sorted_cnt = symbols->cnt;
+ } else {
+ /*
+ * Start a sorted tail buffer at symbols[sorted_cnt .. cnt)
+ * so out-of-order insertions do not memmove the entire
+ * primary sorted prefix on every call.
+ */
+ symbols->symbols[symbols->cnt++] = sym;
+ }
+ } else {
+ unsigned int tail_cnt = symbols->cnt - symbols->sorted_cnt;
+
+ idx = symbols->sorted_cnt +
+ symbols__upper_bound(&symbols->symbols[symbols->sorted_cnt],
+ tail_cnt, sym);
+ memmove(&symbols->symbols[idx + 1], &symbols->symbols[idx],
+ (symbols->cnt - idx) * sizeof(struct symbol *));
+ symbols->symbols[idx] = sym;
+ symbols->cnt++;
+ tail_cnt++;
+
+ if (tail_cnt >= 256 &&
+ (size_t)tail_cnt * tail_cnt >= symbols->sorted_cnt)
+ symbols__sort_locked(symbols);
+ }
+
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ return 0;
+}
+
int symbols__insert(struct symbols *symbols, struct symbol *sym)
{
int ret;
@@ -711,7 +830,9 @@ static inline bool symbol__covers(const struct symbol *s, u64 ip)
return ip >= start && (ip < end || (ip == end && ip == start));
}
-static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
+ u64 ip, bool *has_candidate,
+ u64 *candidate_start)
{
unsigned int low = 0, high = cnt, idx;
u64 start;
@@ -724,8 +845,10 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
else
high = mid;
}
- if (low == 0)
+ if (low == 0) {
+ *has_candidate = false;
return NULL;
+ }
/*
* Rewind across any equal-start group so a trailing zero-length or
@@ -734,6 +857,8 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
*/
idx = low - 1;
start = arr[idx]->start;
+ *has_candidate = true;
+ *candidate_start = start;
while (idx > 0 && arr[idx - 1]->start == start)
idx--;
for (; idx < low; idx++) {
@@ -750,12 +875,38 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
{
struct symbol *res;
+ bool has_prefix;
+ u64 prefix_start = 0;
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,
+ &has_prefix, &prefix_start);
+ if (symbols->sorted_cnt < symbols->cnt) {
+ struct symbol *tail_res;
+ bool has_tail;
+ u64 tail_start = 0;
+
+ tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
+ symbols->cnt - symbols->sorted_cnt, ip,
+ &has_tail, &tail_start);
+ if (has_tail) {
+ if (!has_prefix || tail_start > prefix_start)
+ res = tail_res;
+ else if (tail_start == prefix_start && !res)
+ res = tail_res;
+ }
+ }
up_read(&symbols->lock);
return res;
@@ -900,7 +1051,13 @@ static struct symbol *symbols__find_by_name(struct symbol *symbols[],
int dso__insert_symbol(struct dso *dso, struct symbol *sym)
{
- return symbols__insert(dso__symbols(dso), sym);
+ struct symbols *symbols = dso__symbols(dso);
+ int ret;
+
+ down_write(&symbols->lock);
+ ret = __symbols__insert_sorted(symbols, sym);
+ up_write(&symbols->lock);
+ return ret;
}
void dso__delete_symbol(struct dso *dso, struct symbol *sym)
@@ -908,11 +1065,15 @@ void dso__delete_symbol(struct dso *dso, struct symbol *sym)
struct symbols *symbols = dso__symbols(dso);
down_write(&symbols->lock);
- for (unsigned int i = 0; i < symbols->cnt; i++) {
+ for (unsigned int i = symbols->cnt; i-- > 0; ) {
if (symbols->symbols[i] == sym) {
memmove(&symbols->symbols[i], &symbols->symbols[i + 1],
(symbols->cnt - i - 1) * sizeof(struct symbol *));
symbols->cnt--;
+ if (i < symbols->sorted_cnt)
+ symbols->sorted_cnt--;
+ if (symbols->sorted_cnt == symbols->cnt)
+ symbols->sorted = true;
zfree(&symbols->symbols_by_name);
symbols->num_by_name = 0;
symbols->sorted_by_name = false;
@@ -1259,6 +1420,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso)
old_cnt = root->cnt;
root->symbols = NULL;
root->cnt = 0;
+ root->sorted_cnt = 0;
root->allocated = 0;
root->sorted = true;
zfree(&root->symbols_by_name);
@@ -1333,6 +1495,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
old_allocated = root->allocated;
root->symbols = NULL;
root->cnt = 0;
+ root->sorted_cnt = 0;
root->allocated = 0;
root->sorted = true;
zfree(&root->symbols_by_name);
@@ -1479,6 +1642,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
if (root->cnt == 0) {
root->symbols = old_symbols;
root->cnt = write_idx;
+ root->sorted_cnt = write_idx;
root->allocated = old_allocated;
root->sorted = true;
old_symbols = NULL;
@@ -1508,12 +1672,14 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,
if (root->cnt == 0) {
root->symbols = old_symbols;
root->cnt = write_idx;
+ root->sorted_cnt = (delta == 0) ? write_idx : 0;
root->allocated = old_allocated;
root->sorted = (delta == 0);
old_symbols = NULL;
} else {
for (unsigned int j = 0; j < write_idx; j++)
__symbols__insert(root, old_symbols[j]);
+ root->sorted_cnt = 0;
root->sorted = false;
}
zfree(&root->symbols_by_name);
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 9d7de66cc284..dfdcf026a8c1 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -113,11 +113,20 @@ struct symbols {
struct symbol **symbols_by_name;
/** @cnt: Number of valid entries in @symbols. */
unsigned int cnt;
+ /**
+ * @sorted_cnt: Number of leading entries in @symbols that form the
+ * primary sorted prefix. When @sorted is true and @sorted_cnt < @cnt,
+ * the remaining tail @symbols[@sorted_cnt .. @cnt - 1] is also sorted.
+ */
+ unsigned int sorted_cnt;
/** @allocated: Capacity (in entries) of the @symbols allocation. */
unsigned int allocated;
/** @num_by_name: Number of valid entries in @symbols_by_name. */
unsigned int num_by_name;
- /** @sorted: True when @symbols is sorted by address range. */
+ /**
+ * @sorted: True when @symbols[0 .. @sorted_cnt - 1] and any tail
+ * @symbols[@sorted_cnt .. @cnt - 1] are sorted by start address.
+ */
bool sorted;
/**
* @sorted_by_name: True when @symbols_by_name is populated and sorted
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (6 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
` (2 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
When profiling large workloads or systems with thousands of processes and
shared libraries, perf can accumulate significant memory in loaded DSO
symbol tables, secondary name-sorted symbol indices, cached DSO file data,
and DWARF/addr2line state.
Because the lifetime of struct symbol is controlled by its owning
struct dso, symbols in a referenced DSO (refcnt > 1) must remain valid for
the lifetime of the DSO reference. However, auxiliary per-DSO allocations
and unreferenced DSOs can still be reclaimed under memory pressure:
1. symbols__shrink(): Reclaims the secondary name-sorted index
(symbols_by_name, which is rebuilt on demand by dso__sort_by_name())
and trims unused over-allocated tail capacity in the symbols array.
2. dso__shrink(): Releases cached DSO resources (open file descriptor,
cached 4KB data pages, addr2line handles, and libdw DWARF contexts).
When a DSO in a dsos collection has no external references
(refcnt == 1), dso__shrink() also evicts its unannotated symbol table
via symbols__try_delete_unannotated() and marks the DSO unloaded so it
can be reloaded on demand if mapped again; otherwise it calls
symbols__shrink() to reclaim auxiliary symbol arrays.
3. dsos__shrink(), machine__shrink(), machines__shrink(), and
perf_session__shrink(): Walk the session's host and guest machines to
shrink DSOs and evict unreferenced user DSOs (refcnt == 1, not kernel,
not vDSO, not hit, and not carrying header build-ids), followed by
malloc_trim(0) on glibc to return freed heap pages to the OS.
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/dso.c | 311 ++++++++++++++++++++++++++++++++++----
tools/perf/util/dso.h | 14 +-
tools/perf/util/dsos.c | 50 ++++++
tools/perf/util/dsos.h | 2 +
tools/perf/util/machine.c | 29 ++++
tools/perf/util/machine.h | 3 +
tools/perf/util/session.c | 8 +
tools/perf/util/session.h | 2 +
tools/perf/util/symbol.c | 67 +++++++-
tools/perf/util/symbol.h | 3 +
10 files changed, 455 insertions(+), 34 deletions(-)
diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 3d7db37ff095..0d205015c6dc 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -2,6 +2,7 @@
#include "dso.h"
#include <errno.h>
+#include <stdatomic.h>
#include <stdlib.h>
#include <asm/bug.h>
@@ -15,6 +16,7 @@
#include <sys/types.h>
#include <unistd.h>
+#include "annotate.h"
#include "annotate-data.h"
#include "auxtrace.h"
#include "compress.h"
@@ -552,17 +554,20 @@ static void dso__list_add(struct dso *dso) EXCLUSIVE_LOCKS_REQUIRED(_dso__data_o
dso__data_open_cnt++;
}
-static void dso__list_del(struct dso *dso) EXCLUSIVE_LOCKS_REQUIRED(_dso__data_open_lock)
+static struct dso *dso__list_del(struct dso *dso)
+ EXCLUSIVE_LOCKS_REQUIRED(_dso__data_open_lock)
{
+ struct dso *put_dso = NULL;
+
list_del_init(&dso__data(dso)->open_entry);
#ifdef REFCNT_CHECKING
- mutex_unlock(dso__data_open_lock());
- dso__put(dso__data(dso)->dso);
- mutex_lock(dso__data_open_lock());
+ put_dso = dso__data(dso)->dso;
+ dso__data(dso)->dso = NULL;
#endif
WARN_ONCE(dso__data_open_cnt <= 0,
"DSO data fd counter out of bounds.");
dso__data_open_cnt--;
+ return put_dso;
}
static void close_first_dso(void);
@@ -729,13 +734,26 @@ static int open_dso(struct dso *dso, struct machine *machine)
return fd;
}
+static struct dso *__close_data_fd(struct dso *dso)
+ EXCLUSIVE_LOCKS_REQUIRED(_dso__data_open_lock)
+{
+ if (dso__data(dso)->fd < 0)
+ return NULL;
+
+ close(dso__data(dso)->fd);
+ dso__data(dso)->fd = -1;
+ dso__data(dso)->file_size = 0;
+ return dso__list_del(dso);
+}
+
static void close_data_fd(struct dso *dso) EXCLUSIVE_LOCKS_REQUIRED(_dso__data_open_lock)
{
- if (dso__data(dso)->fd >= 0) {
- close(dso__data(dso)->fd);
- dso__data(dso)->fd = -1;
- dso__data(dso)->file_size = 0;
- dso__list_del(dso);
+ struct dso *put_dso = __close_data_fd(dso);
+
+ if (put_dso) {
+ mutex_unlock(dso__data_open_lock());
+ dso__put(put_dso);
+ mutex_lock(dso__data_open_lock());
}
}
@@ -828,9 +846,12 @@ static void check_data_close(void) EXCLUSIVE_LOCKS_REQUIRED(_dso__data_open_lock
*/
void dso__data_close(struct dso *dso)
{
+ struct dso *put_dso;
+
mutex_lock(dso__data_open_lock());
- close_dso(dso);
+ put_dso = __close_data_fd(dso);
mutex_unlock(dso__data_open_lock());
+ dso__put(put_dso);
}
static int dso__find_binary_type_locked(struct dso *dso)
@@ -1075,12 +1096,12 @@ static int bpf_size(struct dso *dso)
#endif // HAVE_LIBBPF_SUPPORT
static void
-dso_cache__free(struct dso *dso)
+__dso_cache__free(struct dso *dso)
+ EXCLUSIVE_LOCKS_REQUIRED(dso__lock(dso))
{
struct rb_root *root = &dso__data(dso)->cache;
struct rb_node *next = rb_first(root);
- mutex_lock(dso__lock(dso));
while (next) {
struct dso_cache *cache;
@@ -1089,6 +1110,13 @@ dso_cache__free(struct dso *dso)
rb_erase(&cache->rb_node, root);
free(cache);
}
+}
+
+static void
+dso_cache__free(struct dso *dso)
+{
+ mutex_lock(dso__lock(dso));
+ __dso_cache__free(dso);
mutex_unlock(dso__lock(dso));
}
@@ -1243,27 +1271,30 @@ static struct dso_cache *dso_cache__populate(struct dso *dso,
return cache;
}
-static struct dso_cache *dso_cache__find(struct dso *dso,
- struct machine *machine,
- u64 offset,
- ssize_t *ret)
-{
- struct dso_cache *cache = __dso_cache__find(dso, offset);
-
- return cache ? cache : dso_cache__populate(dso, machine, offset, ret);
-}
-
static ssize_t dso_cache_io(struct dso *dso, struct machine *machine,
u64 offset, u8 *data, ssize_t size, bool out)
{
struct dso_cache *cache;
ssize_t ret = 0;
- cache = dso_cache__find(dso, machine, offset, &ret);
- if (!cache)
- return ret;
+ mutex_lock(dso__lock(dso));
+ cache = __dso_cache__find(dso, offset);
+ while (!cache) {
+ mutex_unlock(dso__lock(dso));
+ cache = dso_cache__populate(dso, machine, offset, &ret);
+ if (!cache)
+ return ret;
+ mutex_lock(dso__lock(dso));
+ /*
+ * Re-lookup under dso__lock(dso) in case dso__shrink() freed
+ * the cache while the lock was dropped.
+ */
+ cache = __dso_cache__find(dso, offset);
+ }
- return dso_cache__memcpy(cache, offset, data, size, out);
+ ret = dso_cache__memcpy(cache, offset, data, size, out);
+ mutex_unlock(dso__lock(dso));
+ return ret;
}
/*
@@ -1803,7 +1834,7 @@ int dso__name_len(const struct dso *dso)
bool dso__loaded(const struct dso *dso)
{
- return RC_CHK_ACCESS(dso)->loaded;
+ return atomic_load_explicit(&RC_CHK_ACCESS(dso)->loaded, memory_order_acquire);
}
bool dso__sorted_by_name(const struct dso *dso)
@@ -1835,7 +1866,7 @@ struct dso *dso__new_id(const char *name, const struct dso_id *id)
dso->binary_type = DSO_BINARY_TYPE__NOT_FOUND;
dso->dbginfo_type = DSO_BINARY_TYPE__NOT_FOUND;
dso->is_64_bit = (sizeof(void *) == 8);
- dso->loaded = 0;
+ atomic_init(&dso->loaded, false);
dso->rel = 0;
dso->has_srcline = 1;
dso->a2l_fails = 1;
@@ -1862,7 +1893,7 @@ struct dso *dso__new(const char *name)
return dso__new_id(name, NULL);
}
-void dso__delete(struct dso *dso)
+static void __dso__delete(struct dso *dso, bool close_data)
{
if (dso__dsos(dso))
pr_err("DSO %s is still in rbtree when being deleted!\n", dso__long_name(dso));
@@ -1884,7 +1915,8 @@ void dso__delete(struct dso *dso)
RC_CHK_ACCESS(dso)->long_name_allocated = false;
}
- dso__data_close(dso);
+ if (close_data)
+ dso__data_close(dso);
auxtrace_cache__free(RC_CHK_ACCESS(dso)->auxtrace_cache);
dso_cache__free(dso);
dso__free_a2l(dso);
@@ -1896,6 +1928,222 @@ void dso__delete(struct dso *dso)
RC_CHK_FREE(dso);
}
+void dso__delete(struct dso *dso)
+{
+ __dso__delete(dso, /*close_data=*/true);
+}
+
+bool dso__can_shrink_symbols(const struct dso *dso)
+{
+ const char *name;
+
+ if (!dso || !dso__loaded(dso))
+ return false;
+
+ if (dso__kernel(dso) || dso__is_kmod(dso))
+ return false;
+
+ if (dso__is_vdso(dso))
+ return false;
+
+ switch (dso__binary_type(dso)) {
+ case DSO_BINARY_TYPE__KALLSYMS:
+ case DSO_BINARY_TYPE__GUEST_KALLSYMS:
+ case DSO_BINARY_TYPE__VMLINUX:
+ case DSO_BINARY_TYPE__GUEST_VMLINUX:
+ case DSO_BINARY_TYPE__KCORE:
+ case DSO_BINARY_TYPE__GUEST_KCORE:
+ case DSO_BINARY_TYPE__BPF_PROG_INFO:
+ case DSO_BINARY_TYPE__BPF_IMAGE:
+ case DSO_BINARY_TYPE__OOL:
+ case DSO_BINARY_TYPE__JAVA_JIT:
+ case DSO_BINARY_TYPE__GUEST_KMODULE:
+ case DSO_BINARY_TYPE__GUEST_KMODULE_COMP:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_KMODULE:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_KMODULE_COMP:
+ return false;
+ case DSO_BINARY_TYPE__DEBUGLINK:
+ case DSO_BINARY_TYPE__BUILD_ID_CACHE:
+ case DSO_BINARY_TYPE__BUILD_ID_CACHE_DEBUGINFO:
+ case DSO_BINARY_TYPE__FEDORA_DEBUGINFO:
+ case DSO_BINARY_TYPE__UBUNTU_DEBUGINFO:
+ case DSO_BINARY_TYPE__MIXEDUP_UBUNTU_DEBUGINFO:
+ case DSO_BINARY_TYPE__BUILDID_DEBUGINFO:
+ case DSO_BINARY_TYPE__GNU_DEBUGDATA:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_DSO:
+ case DSO_BINARY_TYPE__OPENEMBEDDED_DEBUGINFO:
+ case DSO_BINARY_TYPE__NOT_FOUND:
+ default:
+ break;
+ }
+
+ switch (dso__symtab_type(dso)) {
+ case DSO_BINARY_TYPE__KALLSYMS:
+ case DSO_BINARY_TYPE__GUEST_KALLSYMS:
+ case DSO_BINARY_TYPE__VMLINUX:
+ case DSO_BINARY_TYPE__GUEST_VMLINUX:
+ case DSO_BINARY_TYPE__KCORE:
+ case DSO_BINARY_TYPE__GUEST_KCORE:
+ case DSO_BINARY_TYPE__BPF_PROG_INFO:
+ case DSO_BINARY_TYPE__BPF_IMAGE:
+ case DSO_BINARY_TYPE__OOL:
+ case DSO_BINARY_TYPE__JAVA_JIT:
+ case DSO_BINARY_TYPE__GUEST_KMODULE:
+ case DSO_BINARY_TYPE__GUEST_KMODULE_COMP:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_KMODULE:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_KMODULE_COMP:
+ case DSO_BINARY_TYPE__NOT_FOUND:
+ return false;
+ case DSO_BINARY_TYPE__DEBUGLINK:
+ case DSO_BINARY_TYPE__BUILD_ID_CACHE:
+ case DSO_BINARY_TYPE__BUILD_ID_CACHE_DEBUGINFO:
+ case DSO_BINARY_TYPE__FEDORA_DEBUGINFO:
+ case DSO_BINARY_TYPE__UBUNTU_DEBUGINFO:
+ case DSO_BINARY_TYPE__MIXEDUP_UBUNTU_DEBUGINFO:
+ case DSO_BINARY_TYPE__BUILDID_DEBUGINFO:
+ case DSO_BINARY_TYPE__GNU_DEBUGDATA:
+ case DSO_BINARY_TYPE__SYSTEM_PATH_DSO:
+ case DSO_BINARY_TYPE__OPENEMBEDDED_DEBUGINFO:
+ default:
+ break;
+ }
+
+ name = dso__long_name(dso);
+ if (!name || name[0] == '[' || is_perf_pid_map_name(name) ||
+ strstr(name, " (deleted)") != NULL)
+ return false;
+
+ return true;
+}
+
+static bool dso__has_annotated_inlines(struct dso *dso)
+{
+ struct rb_root_cached *tree = dso__inlined_nodes(dso);
+ struct rb_node *nd;
+
+ for (nd = rb_first_cached(tree); nd; nd = rb_next(nd)) {
+ struct inline_node *node = rb_entry(nd, struct inline_node, rb_node);
+ struct inline_list *ilist;
+
+ list_for_each_entry(ilist, &node->val, list) {
+ if (ilist->symbol && symbol__annotated(ilist->symbol))
+ return true;
+ }
+ }
+ return false;
+}
+
+static void dso__delete_inlines_and_srclines(void *ctx)
+{
+ struct dso *dso = ctx;
+
+ /* Free inlines before symbols, as inline frames reference symbols. */
+ inlines__tree_delete(dso__inlined_nodes(dso));
+ srcline__tree_delete(dso__srclines(dso));
+}
+
+size_t dso__shrink(struct dso *dso)
+ NO_THREAD_SAFETY_ANALYSIS
+{
+ size_t freed = 0;
+
+ if (!dso)
+ return 0;
+
+ if (mutex_trylock(dso__data_open_lock())) {
+ struct dso *put_dso = NULL;
+
+ if (dso__data(dso)->fd >= 0) {
+ put_dso = __close_data_fd(dso);
+ freed++;
+ }
+ mutex_unlock(dso__data_open_lock());
+ dso__put(put_dso);
+ }
+
+ if (!mutex_trylock(dso__lock(dso)))
+ return freed;
+
+ if (!dso__kernel(dso) && dso__binary_type(dso) != DSO_BINARY_TYPE__OOL &&
+ !RB_EMPTY_ROOT(&dso__data(dso)->cache)) {
+ __dso_cache__free(dso);
+ freed++;
+ }
+ if (dso__a2l(dso)) {
+ dso__free_a2l(dso);
+ freed++;
+ }
+#ifdef HAVE_LIBBFD_SUPPORT
+ if (dso__a2l_libbfd(dso)) {
+ dso__free_a2l_libbfd(dso);
+ freed++;
+ }
+#endif
+#ifdef HAVE_LIBDW_SUPPORT
+ if (dso__libdw(dso)) {
+ dso__free_libdw(dso);
+ freed++;
+ }
+#endif
+
+ if (dso__dsos(dso) && refcount_read(dso__refcnt(dso)) == 1 &&
+ dso__can_shrink_symbols(dso) && dso__has_symbols(dso) &&
+ !dso__has_annotated_inlines(dso) &&
+ symbols__try_delete_unannotated(dso__symbols(dso),
+ dso__delete_inlines_and_srclines, dso)) {
+ atomic_store_explicit(&RC_CHK_ACCESS(dso)->loaded, false,
+ memory_order_release);
+ freed++;
+ } else {
+ freed += symbols__shrink(dso__symbols(dso));
+ }
+
+ mutex_unlock(dso__lock(dso));
+ return freed;
+}
+
+/*
+ * Try to evict an unreferenced @dso from its owning struct dsos (whose write
+ * lock must be held by the caller) without blocking on any lock.
+ */
+bool dso__try_evict(struct dso *dso)
+ NO_THREAD_SAFETY_ANALYSIS
+{
+ bool can_evict;
+
+ if (!dso ||
+ dso__has_symbols(dso) ||
+ dso__header_build_id(dso) ||
+ dso__hit(dso) ||
+ dso__kernel(dso) ||
+ dso__is_vdso(dso) ||
+ refcount_read(dso__refcnt(dso)) != 1)
+ return false;
+
+ if (!mutex_trylock(dso__data_open_lock()))
+ return false;
+
+ can_evict = dso__data(dso)->fd < 0 &&
+ list_empty(&dso__data(dso)->open_entry) &&
+ refcount_read(dso__refcnt(dso)) == 1 &&
+ mutex_trylock(dso__lock(dso));
+ if (can_evict) {
+ if (dso__has_symbols(dso) || dso__has_annotated_inlines(dso))
+ can_evict = false;
+ mutex_unlock(dso__lock(dso));
+ }
+ mutex_unlock(dso__data_open_lock());
+ if (!can_evict)
+ return false;
+
+ dso__set_dsos(dso, NULL);
+ if (refcount_dec_and_test(&RC_CHK_ACCESS(dso)->refcnt))
+ __dso__delete(dso, /*close_data=*/false);
+ else
+ RC_CHK_PUT(dso);
+ return true;
+}
+
struct dso *dso__get(struct dso *dso)
{
struct dso *result;
@@ -1909,7 +2157,8 @@ struct dso *dso__get(struct dso *dso)
void dso__put(struct dso *dso)
{
#ifdef REFCNT_CHECKING
- if (dso && dso__data(dso) && refcount_read(&RC_CHK_ACCESS(dso)->refcnt) == 2)
+ if (dso && dso__data(dso) && dso__data(dso)->fd >= 0 &&
+ refcount_read(&RC_CHK_ACCESS(dso)->refcnt) == 2)
dso__data_close(dso);
#endif
if (dso && refcount_dec_and_test(&RC_CHK_ACCESS(dso)->refcnt))
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index 85880f49ddac..0a8df19383e8 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -6,6 +6,7 @@
#include <linux/types.h>
#include <linux/rbtree.h>
#include <sys/types.h>
+#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
#include <linux/bitops.h>
@@ -346,7 +347,7 @@ DECLARE_RC_STRUCT(dso) {
u8 is_64_bit:1;
u8 bintype_searched:1;
u8 debuginfo_searched:1;
- bool loaded;
+ _Atomic bool loaded;
u8 rel;
char name[];
};
@@ -602,7 +603,7 @@ static inline enum dso_load_errno *dso__load_errno(struct dso *dso)
static inline void dso__set_loaded(struct dso *dso)
{
- RC_CHK_ACCESS(dso)->loaded = true;
+ atomic_store_explicit(&RC_CHK_ACCESS(dso)->loaded, true, memory_order_release);
}
static inline struct mutex *dso__lock(struct dso *dso)
@@ -783,6 +784,15 @@ static inline bool dso__has_symbols(const struct dso *dso)
return RC_CHK_ACCESS(dso)->symbols.cnt > 0;
}
+static inline refcount_t *dso__refcnt(struct dso *dso)
+{
+ return &RC_CHK_ACCESS(dso)->refcnt;
+}
+
+bool dso__can_shrink_symbols(const struct dso *dso);
+bool dso__try_evict(struct dso *dso);
+size_t dso__shrink(struct dso *dso);
+
char *dso__filename_with_chroot(const struct dso *dso, const char *filename);
bool dso__sorted_by_name(const struct dso *dso);
diff --git a/tools/perf/util/dsos.c b/tools/perf/util/dsos.c
index e927e707abac..52d80219ac2f 100644
--- a/tools/perf/util/dsos.c
+++ b/tools/perf/util/dsos.c
@@ -6,6 +6,9 @@
#include "vdso.h"
#include "namespaces.h"
#include <errno.h>
+#ifdef __GLIBC__
+#include <malloc.h>
+#endif
#include <stdlib.h>
#include <string.h>
#include <symbol.h> // filename__read_build_id
@@ -493,3 +496,50 @@ int dsos__for_each_dso(struct dsos *dsos, int (*cb)(struct dso *dso, void *data)
up_read(&dsos->lock);
return err;
}
+
+size_t dsos__shrink(struct dsos *dsos)
+{
+ unsigned int write_idx = 0;
+ size_t freed = 0;
+ bool any_removed = false;
+
+ down_write(&dsos->lock);
+
+ for (unsigned int read_idx = 0; read_idx < dsos->cnt; read_idx++) {
+ struct dso *dso = dsos->dsos[read_idx];
+
+ freed += dso__shrink(dso);
+
+ if (dso__try_evict(dso)) {
+ any_removed = true;
+ freed++;
+ continue;
+ }
+ dsos->dsos[write_idx++] = dso;
+ }
+
+ dsos->cnt = write_idx;
+ if (any_removed) {
+ if (write_idx == 0) {
+ zfree(&dsos->dsos);
+ dsos->allocated = 0;
+ dsos->sorted = true;
+ } else if (write_idx < dsos->allocated / 2) {
+ struct dso **shrunk = realloc(dsos->dsos,
+ write_idx * sizeof(struct dso *));
+ if (shrunk) {
+ dsos->dsos = shrunk;
+ dsos->allocated = write_idx;
+ }
+ }
+ }
+
+ up_write(&dsos->lock);
+
+#ifdef __GLIBC__
+ if (freed > 0)
+ malloc_trim(0);
+#endif
+
+ return freed;
+}
diff --git a/tools/perf/util/dsos.h b/tools/perf/util/dsos.h
index a26774950866..151efdba2aa4 100644
--- a/tools/perf/util/dsos.h
+++ b/tools/perf/util/dsos.h
@@ -49,4 +49,6 @@ struct dso *dsos__find_kernel_dso(struct dsos *dsos);
int dsos__for_each_dso(struct dsos *dsos, int (*cb)(struct dso *dso, void *data), void *data);
+size_t dsos__shrink(struct dsos *dsos);
+
#endif /* __PERF_DSOS */
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index e8a3d8095346..60eed6ae3ba1 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -3441,3 +3441,32 @@ int machine__hit_all_dsos(struct machine *machine)
{
return dsos__hit_all(&machine->dsos);
}
+
+size_t machine__shrink(struct machine *machine)
+{
+ if (!machine)
+ return 0;
+
+ return dsos__shrink(&machine->dsos);
+}
+
+size_t machines__shrink(struct machines *machines)
+{
+ struct rb_node *nd;
+ size_t freed;
+
+ if (!machines)
+ return 0;
+
+ freed = machine__shrink(&machines->host);
+
+ down_read(&machines->lock);
+ for (nd = rb_first_cached(&machines->guests); nd; nd = rb_next(nd)) {
+ struct machine *pos = rb_entry(nd, struct machine, rb_node);
+
+ freed += machine__shrink(pos);
+ }
+ up_read(&machines->lock);
+
+ return freed;
+}
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index 80191545ee8a..0f4c0ae5b56d 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -338,4 +338,7 @@ int machine__resolve(struct machine *machine, struct addr_location *al,
int machine__hit_all_dsos(struct machine *machine);
+size_t machine__shrink(struct machine *machine);
+size_t machines__shrink(struct machines *machines);
+
#endif /* __PERF_MACHINE_H */
diff --git a/tools/perf/util/session.c b/tools/perf/util/session.c
index a58b4fe44b62..d5cb5e94a54a 100644
--- a/tools/perf/util/session.c
+++ b/tools/perf/util/session.c
@@ -4266,3 +4266,11 @@ uint16_t perf_session__e_machine(struct perf_session *session, uint32_t *e_flags
*/
return perf_env__e_machine_nocache(env, e_flags);
}
+
+size_t perf_session__shrink(struct perf_session *session)
+{
+ if (!session)
+ return 0;
+
+ return machines__shrink(&session->machines);
+}
diff --git a/tools/perf/util/session.h b/tools/perf/util/session.h
index 05ea2c1ee8c9..cbea6792a008 100644
--- a/tools/perf/util/session.h
+++ b/tools/perf/util/session.h
@@ -211,4 +211,6 @@ int perf_event__process_finished_round(const struct perf_tool *tool,
struct perf_env *perf_session__env(struct perf_session *session);
uint16_t perf_session__e_machine(struct perf_session *session, uint32_t *e_flags);
+size_t perf_session__shrink(struct perf_session *session);
+
#endif /* __PERF_SESSION_H */
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 0eaeced63cd4..6e2c5c16cda0 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -1,6 +1,7 @@
// SPDX-License-Identifier: GPL-2.0
#include <dirent.h>
#include <errno.h>
+#include <stdatomic.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
@@ -254,6 +255,68 @@ void symbols__exit(struct symbols *symbols)
exit_rwsem(&symbols->lock);
}
+bool symbols__try_delete_unannotated(struct symbols *symbols,
+ void (*pre_delete)(void *ctx), void *ctx)
+{
+ down_write(&symbols->lock);
+ for (unsigned int i = 0; i < symbols->cnt; i++) {
+ if (symbol__annotated(symbols->symbols[i])) {
+ up_write(&symbols->lock);
+ return false;
+ }
+ }
+
+ if (pre_delete)
+ pre_delete(ctx);
+
+ symbols__delete_locked(symbols);
+ up_write(&symbols->lock);
+ return true;
+}
+
+/*
+ * Reclaim auxiliary memory from @symbols without freeing live symbol
+ * entries (whose lifetimes are owned by the containing struct dso):
+ * - Free the secondary name-sorted index (@symbols_by_name), which is
+ * rebuilt on demand by dso__sort_by_name().
+ * - Trim unused over-allocated tail capacity in @symbols->symbols.
+ *
+ * Returns the number of buffers reclaimed/shrunk.
+ */
+size_t symbols__shrink(struct symbols *symbols)
+{
+ size_t freed = 0;
+
+ down_write(&symbols->lock);
+
+ if (symbols->symbols_by_name) {
+ zfree(&symbols->symbols_by_name);
+ symbols->num_by_name = 0;
+ symbols->sorted_by_name = false;
+ freed++;
+ }
+
+ if (symbols->cnt == 0) {
+ if (symbols->allocated > 0) {
+ zfree(&symbols->symbols);
+ symbols->allocated = 0;
+ symbols->sorted = true;
+ freed++;
+ }
+ } else if (symbols->cnt < symbols->allocated) {
+ struct symbol **shrunk = realloc(symbols->symbols,
+ symbols->cnt * sizeof(struct symbol *));
+ if (shrunk) {
+ symbols->symbols = shrunk;
+ symbols->allocated = symbols->cnt;
+ freed++;
+ }
+ }
+
+ up_write(&symbols->lock);
+ return freed;
+}
+
/*
* Order symbols by start address only, preserving insertion order among
* symbols sharing the same start address (matching the previous rbtree
@@ -2382,8 +2445,9 @@ int dso__load(struct dso *dso, struct map *map)
/* check again under the dso->lock */
if (dso__loaded(dso)) {
ret = 1;
- goto out;
+ goto out_unlock;
}
+ atomic_store_explicit(&RC_CHK_ACCESS(dso)->loaded, false, memory_order_release);
kmod = dso__is_kmod(dso);
@@ -2541,6 +2605,7 @@ int dso__load(struct dso *dso, struct map *map)
ret = 0;
out:
dso__set_loaded(dso);
+out_unlock:
mutex_unlock(dso__lock(dso));
nsinfo__mountns_exit(&nsc);
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index dfdcf026a8c1..687747661dd3 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -139,6 +139,9 @@ void symbol__delete(struct symbol *sym);
void symbols__init(struct symbols *symbols);
void symbols__exit(struct symbols *symbols);
void symbols__delete(struct symbols *symbols);
+bool symbols__try_delete_unannotated(struct symbols *symbols,
+ void (*pre_delete)(void *ctx), void *ctx);
+size_t symbols__shrink(struct symbols *symbols);
void symbols__sort_read_lock(struct symbols *symbols) SHARED_LOCK_FUNCTION(symbols->lock);
static inline u8 symbol__type(const struct symbol *sym)
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (7 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-21 7:35 ` [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking sashiko-bot
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
Add explicit session-scoped memory allocation wrappers:
- perf_session__malloc(session, size)
- perf_session__zalloc(session, size)
- perf_session__calloc(session, nmemb, size)
- perf_session__realloc(session, ptr, size)
- perf_session__strdup(session, s)
When an allocation fails and returns NULL, if a non-NULL struct
perf_session is provided, the wrapper invokes perf_session__shrink() to
evict unreferenced symbols, DSOs, and cached debuginfo across the
session's machines and then retries the allocation once. This avoids
the thrashing overhead of periodic heuristic shrinking while allowing
perf to recover from memory exhaustion.
Also plumb a back-pointer from struct dsos to its owning struct machine
so machine__session(machine) and dso__session(dso) can resolve the
active perf_session.
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/dso.c | 7 ++++
tools/perf/util/dso.h | 2 ++
tools/perf/util/dsos.c | 1 +
tools/perf/util/dsos.h | 1 +
tools/perf/util/machine.c | 1 +
tools/perf/util/machine.h | 5 +++
tools/perf/util/session.c | 70 +++++++++++++++++++++++++++++++++++++++
tools/perf/util/session.h | 6 ++++
8 files changed, 93 insertions(+)
diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 0d205015c6dc..ba070611c18a 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -1933,6 +1933,13 @@ void dso__delete(struct dso *dso)
__dso__delete(dso, /*close_data=*/true);
}
+struct perf_session *dso__session(const struct dso *dso)
+{
+ struct dsos *dsos = dso ? RC_CHK_ACCESS(dso)->dsos : NULL;
+
+ return dsos ? machine__session(dsos->machine) : NULL;
+}
+
bool dso__can_shrink_symbols(const struct dso *dso)
{
const char *name;
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index 0a8df19383e8..d4360a6ed8e0 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -20,6 +20,7 @@
struct machine;
struct map;
struct perf_env;
+struct perf_session;
#define DSO__NAME_KALLSYMS "[kernel.kallsyms]"
#define DSO__NAME_KCORE "[kernel.kcore]"
@@ -792,6 +793,7 @@ static inline refcount_t *dso__refcnt(struct dso *dso)
bool dso__can_shrink_symbols(const struct dso *dso);
bool dso__try_evict(struct dso *dso);
size_t dso__shrink(struct dso *dso);
+struct perf_session *dso__session(const struct dso *dso);
char *dso__filename_with_chroot(const struct dso *dso, const char *filename);
diff --git a/tools/perf/util/dsos.c b/tools/perf/util/dsos.c
index 52d80219ac2f..343c79c7ee37 100644
--- a/tools/perf/util/dsos.c
+++ b/tools/perf/util/dsos.c
@@ -18,6 +18,7 @@ void dsos__init(struct dsos *dsos)
{
init_rwsem(&dsos->lock);
+ dsos->machine = NULL;
dsos->cnt = 0;
dsos->allocated = 0;
dsos->dsos = NULL;
diff --git a/tools/perf/util/dsos.h b/tools/perf/util/dsos.h
index 151efdba2aa4..d636e4c5cbaf 100644
--- a/tools/perf/util/dsos.h
+++ b/tools/perf/util/dsos.h
@@ -19,6 +19,7 @@ struct machine;
*/
struct dsos {
struct rw_semaphore lock;
+ struct machine *machine;
struct dso **dsos;
unsigned int cnt;
unsigned int allocated;
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 60eed6ae3ba1..d3a93e8a4743 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -81,6 +81,7 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
memset(machine, 0, sizeof(*machine));
RB_CLEAR_NODE(&machine->rb_node);
dsos__init(&machine->dsos);
+ machine->dsos.machine = machine;
threads__init(&machine->threads);
machine->kmaps = maps__new(machine);
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index 0f4c0ae5b56d..6192bd3e33bb 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -164,6 +164,11 @@ static inline struct perf_session *machines__session(struct machines *machines)
return machines->session;
}
+static inline struct perf_session *machine__session(const struct machine *machine)
+{
+ return machine && machine->machines ? machine->machines->session : NULL;
+}
+
void machines__process_guests(struct machines *machines,
machine__process_t process, void *data);
diff --git a/tools/perf/util/session.c b/tools/perf/util/session.c
index d5cb5e94a54a..0f3e44fa4486 100644
--- a/tools/perf/util/session.c
+++ b/tools/perf/util/session.c
@@ -4274,3 +4274,73 @@ size_t perf_session__shrink(struct perf_session *session)
return machines__shrink(&session->machines);
}
+
+static __thread bool perf_session__in_shrink;
+
+static bool perf_session__try_shrink(struct perf_session *session)
+{
+ size_t freed;
+
+ if (!session || perf_session__in_shrink)
+ return false;
+
+ perf_session__in_shrink = true;
+ freed = perf_session__shrink(session);
+ perf_session__in_shrink = false;
+
+ return freed > 0;
+}
+
+void *perf_session__malloc(struct perf_session *session, size_t size)
+{
+ void *ptr = malloc(size);
+
+ if (unlikely(!ptr && size != 0) && perf_session__try_shrink(session))
+ ptr = malloc(size);
+
+ return ptr;
+}
+
+void *perf_session__zalloc(struct perf_session *session, size_t size)
+{
+ void *ptr = zalloc(size);
+
+ if (unlikely(!ptr && size != 0) && perf_session__try_shrink(session))
+ ptr = zalloc(size);
+
+ return ptr;
+}
+
+void *perf_session__calloc(struct perf_session *session, size_t nmemb, size_t size)
+{
+ void *ptr = calloc(nmemb, size);
+
+ if (unlikely(!ptr && nmemb != 0 && size != 0) && perf_session__try_shrink(session))
+ ptr = calloc(nmemb, size);
+
+ return ptr;
+}
+
+void *perf_session__realloc(struct perf_session *session, void *ptr, size_t size)
+{
+ void *new_ptr = realloc(ptr, size);
+
+ if (unlikely(!new_ptr && size != 0) && perf_session__try_shrink(session))
+ new_ptr = realloc(ptr, size);
+
+ return new_ptr;
+}
+
+char *perf_session__strdup(struct perf_session *session, const char *s)
+{
+ char *dup;
+
+ if (!s)
+ return NULL;
+
+ dup = strdup(s);
+ if (unlikely(!dup) && perf_session__try_shrink(session))
+ dup = strdup(s);
+
+ return dup;
+}
diff --git a/tools/perf/util/session.h b/tools/perf/util/session.h
index cbea6792a008..c6157eddcc43 100644
--- a/tools/perf/util/session.h
+++ b/tools/perf/util/session.h
@@ -213,4 +213,10 @@ uint16_t perf_session__e_machine(struct perf_session *session, uint32_t *e_flags
size_t perf_session__shrink(struct perf_session *session);
+void *perf_session__malloc(struct perf_session *session, size_t size);
+void *perf_session__zalloc(struct perf_session *session, size_t size);
+void *perf_session__calloc(struct perf_session *session, size_t nmemb, size_t size);
+void *perf_session__realloc(struct perf_session *session, void *ptr, size_t size);
+char *perf_session__strdup(struct perf_session *session, const char *s);
+
#endif /* __PERF_SESSION_H */
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (8 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
@ 2026-11-21 7:16 ` Ian Rogers
2026-11-21 7:35 ` [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking sashiko-bot
10 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-21 7:16 UTC (permalink / raw)
To: Namhyung Kim, Arnaldo Carvalho de Melo, Alireza Haghdoost,
Ian Rogers
Cc: Peter Zijlstra, Ingo Molnar, Jiri Olsa, Adrian Hunter,
James Clark, linux-perf-users, linux-kernel
Ensure the new symbol sorting, DSO-lifetime symbol and DSO shrinking,
dso_symbol reference pinning, on-demand DSO reload after unreferenced
eviction, and session-scoped allocation wrappers are verified by
'perf test symbols' (including under REFCNT_CHECKING=1).
Add unit tests to 'perf test symbols' covering:
- test_symbols_sorted_insert(): Verify ascending symbols__insert(),
out-of-order dso__insert_symbol() maintaining sorted order, and
unsorted symbols__insert() followed by sort-on-lookup in
dso__find_symbol().
- test_symbols_shrink(): Verify symbols__shrink() reclaims the secondary
symbols_by_name index and trims unused capacity in symbols->symbols
while keeping live symbols intact, and verify
symbols__try_delete_unannotated() preserves annotated symbol tables.
- test_dsos_shrink(): Verify dsos__shrink() evicts unreferenced user
DSOs while retaining DSOs with active external references and vDSOs.
- test_session_alloc_shrink(): Verify machine__session(),
dso__session(), perf_session__malloc/zalloc/calloc/realloc/strdup(),
and perf_session__shrink().
- test_dso_shrink_and_reload(): Verify dso__shrink() on a referenced ELF
DSO reclaims auxiliary buffers while preserving symbol pointers,
dso_symbol__copy() pins DSO symbols across dsos__shrink() until
dso_symbol__exit(), and dsos__shrink() on an unreferenced hit DSO
evicts its symbol table and transparently reloads it on a subsequent
map__find_symbol().
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/tests/symbols.c | 779 ++++++++++++++++++++++++++++++++++++-
1 file changed, 768 insertions(+), 11 deletions(-)
diff --git a/tools/perf/tests/symbols.c b/tools/perf/tests/symbols.c
index b73da581f895..6d4c2b760c7c 100644
--- a/tools/perf/tests/symbols.c
+++ b/tools/perf/tests/symbols.c
@@ -1,20 +1,34 @@
// SPDX-License-Identifier: GPL-2.0
#include <linux/compiler.h>
+#include <linux/list.h>
#include <linux/string.h>
+#include <linux/zalloc.h>
#include <sys/mman.h>
#include <elf.h>
+#include <errno.h>
#include <inttypes.h>
#include <limits.h>
+#include <pthread.h>
+#include <stdatomic.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
#include <stdlib.h>
+#include <string.h>
#include <unistd.h>
+#include "annotate.h"
#include "debug.h"
#include "dso.h"
#include "env.h"
#include "machine.h"
+#include "session.h"
+#include "srcline.h"
#include "thread.h"
#include "symbol.h"
#include "map.h"
+#include "map_symbol.h"
#include "util.h"
+#include "vdso.h"
#include "tests.h"
struct test_info {
@@ -182,6 +196,486 @@ static int process_subdivided_dso(struct machine *machine, struct dso *dso)
return ret < 0 ? TEST_FAIL : TEST_OK;
}
+static int noop_visit_cb(struct symbol *sym __maybe_unused, void *data __maybe_unused)
+{
+ return 0;
+}
+
+static int test_symbols_shrink(void)
+{
+ struct symbols symbols;
+ struct symbol *sym1, *sym2, *sym3;
+ int ret = TEST_FAIL;
+
+ symbols__init(&symbols);
+
+ sym1 = symbol__new(0x100, 0x50, STB_GLOBAL, STT_FUNC, "sym1");
+ sym2 = symbol__new(0x200, 0x50, STB_GLOBAL, STT_FUNC, "sym2");
+ sym3 = symbol__new(0x300, 0x50, STB_GLOBAL, STT_FUNC, "sym3");
+ if (!sym1 || !sym2 || !sym3) {
+ symbol__delete(sym1);
+ symbol__delete(sym2);
+ symbol__delete(sym3);
+ goto out;
+ }
+
+ symbols__insert(&symbols, sym1);
+ symbols__insert(&symbols, sym2);
+ symbols__insert(&symbols, sym3);
+ symbols__visit_by_name(&symbols, noop_visit_cb, NULL);
+ if (!symbols.symbols_by_name || symbols.allocated <= symbols.cnt) {
+ pr_debug("Expected populated symbols_by_name and excess capacity!\n");
+ goto out;
+ }
+
+ /*
+ * First shrink: reclaims symbols_by_name and trims excess capacity in
+ * symbols.symbols while keeping all 3 symbols intact.
+ */
+ if (symbols__shrink(&symbols) != 2 || symbols.cnt != 3 ||
+ symbols.allocated != 3 || symbols.symbols_by_name != NULL) {
+ pr_debug("First symbols__shrink failed (cnt=%u, allocated=%u)!\n",
+ symbols.cnt, symbols.allocated);
+ goto out;
+ }
+
+ /*
+ * Second shrink with no symbols_by_name and no excess capacity is a no-op.
+ */
+ if (symbols__shrink(&symbols) != 0 || symbols.cnt != 3) {
+ pr_debug("Second symbols__shrink failed (cnt=%u)!\n", symbols.cnt);
+ goto out;
+ }
+
+ /*
+ * Verify symbols__try_delete_unannotated() skips deletion when any
+ * symbol has an entry in the annotations hashmap and deletes all
+ * symbols once unannotated.
+ */
+ if (!symbol__annotation(sym1) || !symbol__annotated(sym1)) {
+ pr_debug("symbol__annotation(sym1) failed!\n");
+ goto out;
+ }
+ if (symbols__try_delete_unannotated(&symbols, NULL, NULL) || symbols.cnt != 3) {
+ pr_debug("symbols__try_delete_unannotated deleted annotated table!\n");
+ goto out;
+ }
+ symbol__annotation_delete(sym1);
+ if (symbol__annotated(sym1) ||
+ !symbols__try_delete_unannotated(&symbols, NULL, NULL) ||
+ symbols.cnt != 0) {
+ pr_debug("symbols__try_delete_unannotated failed after clearing annotation!\n");
+ goto out;
+ }
+
+ ret = TEST_OK;
+out:
+ symbols__exit(&symbols);
+ return ret;
+}
+
+static int test_dsos_shrink(void)
+{
+ struct dsos dsos;
+ struct dso *dso1, *dso2, *vdso;
+ int ret = TEST_FAIL;
+
+ dsos__init(&dsos);
+
+ dso1 = dsos__findnew_id(&dsos, "/tmp/perf_test_dso1", NULL);
+ dso2 = dsos__findnew_id(&dsos, "/tmp/perf_test_dso2", NULL);
+ vdso = dsos__findnew_id(&dsos, DSO__NAME_VDSO, NULL);
+ if (!dso1 || !dso2 || !vdso) {
+ dso__put(dso1);
+ dso__put(dso2);
+ dso__put(vdso);
+ goto out;
+ }
+
+ /*
+ * Keep the caller's active reference on dso1; drop caller references on
+ * dso2 and vdso.
+ */
+ dso__put(dso2);
+ dso__put(vdso);
+
+ /*
+ * First shrink: dso2 has refcnt == 1 and no symbols, so it is evicted;
+ * dso1 (refcnt == 2) and vdso (dso__is_vdso() == true) are retained.
+ */
+ if (dsos__shrink(&dsos) != 1 || dsos.cnt != 2) {
+ pr_debug("First dsos__shrink failed (cnt=%u)!\n", dsos.cnt);
+ dso__put(dso1);
+ goto out;
+ }
+
+ dso__put(dso1);
+ if (dsos__shrink(&dsos) != 1 || dsos.cnt != 1 || !dso__is_vdso(dsos.dsos[0])) {
+ pr_debug("Second dsos__shrink failed (cnt=%u)!\n", dsos.cnt);
+ goto out;
+ }
+
+ ret = TEST_OK;
+out:
+ dsos__exit(&dsos);
+ return ret;
+}
+
+struct shrink_lock_race_args {
+ struct dso *dso;
+ atomic_bool stop;
+};
+
+static void *shrink_lock_race_worker(void *arg)
+{
+ struct shrink_lock_race_args *args = arg;
+
+ while (!atomic_load_explicit(&args->stop, memory_order_relaxed))
+ dso__find_binary_type(args->dso);
+
+ return NULL;
+}
+
+static int test_session_alloc_shrink(void)
+{
+ struct perf_session *session = zalloc(sizeof(*session));
+ struct dso *dso;
+ struct thread *th;
+ pid_t pid = getpid();
+ char *p1 = NULL, *p2 = NULL, *p3 = NULL, *s = NULL, *tmp;
+ int ret = TEST_FAIL;
+
+ if (!session)
+ return TEST_FAIL;
+
+ perf_env__init(&session->header.env);
+ if (machines__init(&session->machines, session))
+ goto out;
+ session->machines.host.env = &session->header.env;
+ if (machine__session(&session->machines.host) != session) {
+ pr_debug("machine__session did not return owning session!\n");
+ goto out;
+ }
+
+ dso = machine__findnew_dso(&session->machines.host, "/tmp/perf_test_session_dso");
+ if (!dso)
+ goto out;
+ if (dso__session(dso) != session) {
+ pr_debug("dso__session did not return owning session!\n");
+ dso__put(dso);
+ goto out;
+ }
+ dso__put(dso);
+
+ p1 = perf_session__malloc(session, 64);
+ p2 = perf_session__zalloc(session, 64);
+ p3 = perf_session__calloc(session, 4, 16);
+ s = perf_session__strdup(session, "perf_session_alloc_test");
+ if (!p1 || !p2 || !p3 || !s || strcmp(s, "perf_session_alloc_test") != 0) {
+ pr_debug("perf_session allocation wrappers failed!\n");
+ goto out;
+ }
+
+ tmp = perf_session__realloc(session, p1, 128);
+ if (!tmp) {
+ pr_debug("perf_session__realloc failed!\n");
+ goto out;
+ }
+ p1 = tmp;
+
+ if (perf_session__shrink(session) == 0 || session->machines.host.dsos.cnt != 0) {
+ pr_debug("perf_session__shrink failed to evict unreferenced DSO!\n");
+ goto out;
+ }
+
+ /*
+ * Regression test for AB-BA lock inversion between dso__lock(dso_A)
+ * (held by dso__load() when calling perf_session__shrink() to evict
+ * unreferenced dso_B) and _dso__data_open_lock (acquired before
+ * dso__lock(dso_A) by dso__find_binary_type()).
+ */
+ dso = machine__findnew_dso(&session->machines.host, "/tmp/perf_test_contended_dso");
+ if (!dso)
+ goto out;
+ {
+ bool was_singlethreaded = perf_singlethreaded;
+ struct shrink_lock_race_args race_args = {
+ .dso = dso,
+ .stop = false,
+ };
+ pthread_t worker;
+
+ perf_set_multithreaded();
+ if (pthread_create(&worker, NULL, shrink_lock_race_worker, &race_args) != 0) {
+ if (was_singlethreaded)
+ perf_set_singlethreaded();
+ dso__put(dso);
+ goto out;
+ }
+ for (int i = 0; i < 200; i++) {
+ struct dso *evict = machine__findnew_dso(&session->machines.host,
+ "/tmp/perf_test_evict_dso");
+
+ dso__put(evict);
+ mutex_lock(dso__lock(dso));
+ RC_CHK_ACCESS(dso)->bintype_searched = 0;
+ perf_session__shrink(session);
+ mutex_unlock(dso__lock(dso));
+ }
+ atomic_store_explicit(&race_args.stop, true, memory_order_relaxed);
+ pthread_join(worker, NULL);
+ if (was_singlethreaded)
+ perf_set_singlethreaded();
+ }
+ dso__put(dso);
+ perf_session__shrink(session);
+
+ /*
+ * Verify perf_session__e_machine() -> threads__for_each_thread() does
+ * not self-deadlock on table->lock when a non-leader thread looks up or
+ * creates its leader thread in the same shard.
+ */
+ {
+ bool was_singlethreaded = perf_singlethreaded;
+ uint16_t e_machine;
+
+ perf_set_multithreaded();
+ th = machine__findnew_thread(&session->machines.host, pid,
+ pid + THREADS__TABLE_SIZE);
+ if (!th) {
+ if (was_singlethreaded)
+ perf_set_singlethreaded();
+ goto out;
+ }
+ thread__put(th);
+ e_machine = perf_session__e_machine(session, NULL);
+ if (was_singlethreaded)
+ perf_set_singlethreaded();
+ if (e_machine == EM_NONE) {
+ pr_debug("perf_session__e_machine failed!\n");
+ goto out;
+ }
+ }
+
+ ret = TEST_OK;
+out:
+ free(p1);
+ free(p2);
+ free(p3);
+ free(s);
+ machines__exit(&session->machines);
+ perf_env__exit(&session->header.env);
+ free(session);
+ return ret;
+}
+
+struct shrink_reload_find_args {
+ struct symbol *kept;
+ u64 first_start;
+ u64 second_start;
+ char *second_name;
+ u64 max_end;
+};
+
+static int shrink_reload_find_cb(struct symbol *sym, void *data)
+{
+ struct shrink_reload_find_args *args = data;
+
+ if (!args->kept) {
+ args->kept = sym;
+ args->first_start = sym->start;
+ args->max_end = sym->end;
+ return 0;
+ }
+ if (!args->second_name && sym->start >= args->max_end) {
+ args->second_start = sym->start;
+ args->second_name = strdup(sym->name);
+ if (!args->second_name)
+ return -ENOMEM;
+ }
+ if (sym->end > args->max_end)
+ args->max_end = sym->end;
+ return 0;
+}
+
+static int test_dso_shrink_and_reload(struct test_info *ti, char *filename, struct map **map_p)
+{
+ struct shrink_reload_find_args args = {
+ .kept = NULL,
+ .first_start = 0,
+ .second_start = 0,
+ .second_name = NULL,
+ .max_end = 0,
+ };
+ struct map *map = *map_p;
+ struct dso *dso = map__dso(map);
+ struct symbols *syms = dso__symbols(dso);
+ struct symbol *sym, *reloaded;
+ unsigned int initial_cnt;
+
+ if (!dso__can_shrink_symbols(dso) || dso__kernel(dso))
+ return TEST_SKIP;
+ initial_cnt = syms->cnt;
+ if (dso__for_each_symbol(dso, shrink_reload_find_cb, &args) < 0)
+ return TEST_FAIL;
+ if (!args.second_name)
+ return TEST_SKIP;
+
+ /*
+ * While dso is referenced by map (refcnt > 1), dso__shrink() reclaims
+ * auxiliary buffers (such as symbols_by_name) while keeping all symbols
+ * and their pointers valid.
+ */
+ dso__sort_by_name(dso);
+ if (syms->num_by_name < 2) {
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ {
+ size_t idx = 0;
+ struct symbol *expected_next = syms->symbols_by_name[1];
+ u8 hdr_byte = 0;
+
+ /* Populate dso data fd and cache so dso__shrink() reclaims them too. */
+ (void)dso__data_read_offset(dso, ti->machine, 0, &hdr_byte, 1);
+
+ if (dso__shrink(dso) == 0 || syms->cnt != initial_cnt ||
+ syms->symbols_by_name != NULL || dso__data(dso)->fd >= 0) {
+ pr_debug("dso__shrink on referenced DSO failed!\n");
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ if (dso__next_symbol_by_name(dso, &idx) != expected_next || idx != 1) {
+ pr_debug("dso__next_symbol_by_name failed to rebuild symbols_by_name!\n");
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ dso__shrink(dso);
+ }
+
+ sym = dso__find_symbol(dso, args.first_start);
+ if (sym != args.kept) {
+ pr_debug("Symbol pointer changed after dso__shrink on referenced DSO!\n");
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+
+ /*
+ * Verify struct dso_symbol retains a reference on its owning DSO even
+ * after the map reference is dropped, preventing dsos__shrink() from
+ * evicting the DSO's symbol table until dso_symbol__exit() is called.
+ */
+ dso__set_hit(dso);
+ {
+ struct dso_symbol src = {
+ .dso = dso,
+ .sym = args.kept,
+ };
+ struct dso_symbol pinned;
+ struct inline_node *inode;
+ struct symbol *inlined_sym;
+ char *srcline;
+
+ dso_symbol__copy(&pinned, &src);
+ map__zput(*map_p);
+ dsos__shrink(&ti->machine->dsos);
+ if (!dso__loaded(pinned.dso) ||
+ dso__symbols(pinned.dso)->cnt != initial_cnt ||
+ dso__find_symbol(pinned.dso, args.first_start) != pinned.sym) {
+ pr_debug("dso_symbol failed to pin DSO symbols across dsos__shrink!\n");
+ dso_symbol__exit(&pinned);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+
+ /*
+ * Populate dso->inlined_nodes (referencing both a base symbol
+ * from dso->symbols and an owned inlined symbol) and
+ * dso->srclines so dsos__shrink() exercises freeing inlines
+ * before freeing the underlying symbol table.
+ */
+ inode = zalloc(sizeof(*inode));
+ inlined_sym = new_inline_sym(pinned.dso, pinned.sym, "inlined_helper");
+ srcline = strdup("test.c:1");
+ if (!inode || !inlined_sym || !srcline) {
+ free(inode);
+ if (inlined_sym && symbol__inlined(inlined_sym))
+ symbol__delete(inlined_sym);
+ free(srcline);
+ dso_symbol__exit(&pinned);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ inode->addr = args.first_start;
+ INIT_LIST_HEAD(&inode->val);
+ if (inline_list__append(inlined_sym, SRCLINE_UNKNOWN, inode) < 0) {
+ if (symbol__inlined(inlined_sym))
+ symbol__delete(inlined_sym);
+ inline_node__delete(inode);
+ free(srcline);
+ dso_symbol__exit(&pinned);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ if (inline_list__append(pinned.sym, SRCLINE_UNKNOWN, inode) < 0) {
+ inline_node__delete(inode);
+ free(srcline);
+ dso_symbol__exit(&pinned);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ inlines__tree_insert(dso__inlined_nodes(pinned.dso), inode);
+ srcline__tree_insert(dso__srclines(pinned.dso), args.first_start, srcline);
+ dso_symbol__exit(&pinned);
+ }
+
+ if (dsos__shrink(&ti->machine->dsos) == 0) {
+ pr_debug("dsos__shrink did not reclaim unreferenced DSO symbols!\n");
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+
+ if (create_map(ti, filename, map_p) != TEST_OK) {
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ map = *map_p;
+ dso = map__dso(map);
+ syms = dso__symbols(dso);
+ if (!dso__hit(dso) || syms->cnt != 0 || dso__loaded(dso) ||
+ inlines__tree_find(dso__inlined_nodes(dso), args.first_start) != NULL ||
+ srcline__tree_find(dso__srclines(dso), args.first_start) != NULL) {
+ pr_debug("Unreferenced hit DSO state mismatch after dsos__shrink!\n");
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+
+ /* Lookup via map__find_symbol transparently reloads the DSO. */
+ reloaded = map__find_symbol(map, args.second_start);
+ if (!reloaded || strcmp(reloaded->name, args.second_name) != 0) {
+ pr_debug("Failed to reload evicted symbol %s!\n", args.second_name);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+
+ if (syms->cnt != initial_cnt || !syms->sorted || !dso__loaded(dso)) {
+ pr_debug("Reloaded symbol table state mismatch (cnt=%u vs %u, sorted=%d, loaded=%d)!\n",
+ syms->cnt, initial_cnt, syms->sorted, dso__loaded(dso));
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ for (unsigned int i = 1; i < syms->cnt; i++) {
+ if (syms->symbols[i - 1]->start > syms->symbols[i]->start) {
+ pr_debug("Reloaded symbols out of order at %u!\n", i);
+ free(args.second_name);
+ return TEST_FAIL;
+ }
+ }
+
+ free(args.second_name);
+ return TEST_OK;
+}
+
static int test_file(struct test_info *ti, char *filename)
{
struct map *map = NULL;
@@ -213,18 +707,271 @@ static int test_file(struct test_info *ti, char *filename)
/* Module dso is split into many dsos by section */
if (ret == TEST_OK && dso__kernel(dso) != DSO_SPACE__USER)
ret = process_subdivided_dso(ti->machine, dso);
+
+ if (ret == TEST_OK) {
+ int shrink_ret = test_dso_shrink_and_reload(ti, filename, &map);
+
+ if (shrink_ret != TEST_SKIP)
+ ret = shrink_ret;
+ }
out_put:
map__put(map);
return ret;
}
+static int test_symbols_sorted_insert(void)
+{
+ struct dso *dso = dso__new("/tmp/perf_test_sorted_insert");
+ struct symbols *symbols;
+ int ret = TEST_FAIL;
+
+ if (!dso)
+ return TEST_FAIL;
+
+ symbols = dso__symbols(dso);
+
+ /*
+ * Insert 100 odd-indexed symbols in ascending order via
+ * symbols__insert(), then insert 5 even-indexed symbols out of order via
+ * dso__insert_symbol() and verify symbols->sorted remains true.
+ */
+ for (unsigned int i = 0; i < 100; i++) {
+ char name[32];
+ u64 addr = (u64)(i * 2 + 1) * 0x100;
+ struct symbol *sym;
+
+ snprintf(name, sizeof(name), "sym_%u", i * 2 + 1);
+ sym = symbol__new(addr, 0x40, STB_GLOBAL, STT_FUNC, name);
+ if (!sym || symbols__insert(symbols, sym))
+ goto out;
+ }
+ if (!symbols->sorted || symbols->cnt != 100) {
+ pr_debug("Expected sorted=true, cnt=100 after ordered inserts\n");
+ goto out;
+ }
+
+ for (unsigned int i = 0; i < 5; i++) {
+ char name[32];
+ u64 addr = (u64)(i * 20) * 0x100;
+ struct symbol *sym;
+
+ snprintf(name, sizeof(name), "ins_%u", i * 20);
+ sym = symbol__new(addr, 0x40, STB_GLOBAL, STT_FUNC, name);
+ if (!sym || dso__insert_symbol(dso, sym))
+ goto out;
+ if (!symbols->sorted) {
+ pr_debug("dso__insert_symbol did not preserve sorted invariant!\n");
+ goto out;
+ }
+ }
+
+ /*
+ * Now append 95 remaining even-indexed symbols in descending order via
+ * symbols__insert() to exercise the unsorted append + sort-on-lookup path.
+ */
+ for (unsigned int i = 99; i > 0; i--) {
+ char name[32];
+ u64 addr;
+ struct symbol *sym;
+
+ if ((i * 2) % 20 == 0 && (i * 2) < 100)
+ continue;
+ addr = (u64)(i * 2) * 0x100;
+ snprintf(name, sizeof(name), "ins_%u", i * 2);
+ sym = symbol__new(addr, 0x40, STB_GLOBAL, STT_FUNC, name);
+ if (!sym || symbols__insert(symbols, sym))
+ goto out;
+ }
+ if (symbols->sorted || symbols->cnt != 200) {
+ pr_debug("Unexpected sorted=%d cnt=%u before lookup\n",
+ symbols->sorted, symbols->cnt);
+ goto out;
+ }
+
+ for (unsigned int i = 0; i < 200; i++) {
+ u64 addr = (u64)i * 0x100 + 0x10;
+ struct symbol *sym = dso__find_symbol(dso, addr);
+
+ if (!sym || sym->start != (u64)i * 0x100) {
+ pr_debug("Lookup failed at idx %u (addr=%#" PRIx64 ")\n", i, addr);
+ goto out;
+ }
+ }
+
+ /*
+ * Insert dynamic symbols into the unmerged sorted tail and verify
+ * lookups match merged-array semantics in all prefix/tail overlap and
+ * equal-start cases:
+ * - [0x0, 0x40) in prefix + [0x20, 0x30) in tail: 0x24 -> inner,
+ * 0x34 -> NULL (closer tail start shadows outer prefix symbol).
+ * - [0x100, 0x140) in prefix + [0x80, 0x180) in tail: 0x150 -> NULL
+ * (closer prefix start shadows outer tail symbol).
+ * - [0x200, 0x240) in prefix + [0x200, 0x260) in tail: 0x250 -> alias
+ * (equal-start group spans prefix and tail).
+ */
+ {
+ struct symbol *inner = symbol__new(0x20, 0x10, STB_GLOBAL, STT_FUNC,
+ "inner_tail_sym");
+ struct symbol *outer = symbol__new(0x80, 0x100, STB_GLOBAL, STT_FUNC,
+ "outer_tail_sym");
+ struct symbol *alias = symbol__new(0x200, 0x60, STB_GLOBAL, STT_FUNC,
+ "longer_tail_alias");
+
+ if (!inner || dso__insert_symbol(dso, inner)) {
+ symbol__delete(outer);
+ symbol__delete(alias);
+ goto out;
+ }
+ if (!outer || dso__insert_symbol(dso, outer)) {
+ symbol__delete(alias);
+ goto out;
+ }
+ if (!alias || dso__insert_symbol(dso, alias))
+ goto out;
+ if (symbols->sorted_cnt >= symbols->cnt) {
+ pr_debug("Expected unmerged sorted tail!\n");
+ goto out;
+ }
+ if (dso__find_symbol(dso, 0x24) != inner ||
+ dso__find_symbol(dso, 0x34) != NULL ||
+ dso__find_symbol(dso, 0x150) != NULL ||
+ dso__find_symbol(dso, 0x250) != alias) {
+ pr_debug("Unmerged tail lookup mismatch!\n");
+ goto out;
+ }
+ symbols__sort_read_lock(symbols);
+ up_read(&symbols->lock);
+ if (dso__find_symbol(dso, 0x24) != inner ||
+ dso__find_symbol(dso, 0x34) != NULL ||
+ dso__find_symbol(dso, 0x150) != NULL ||
+ dso__find_symbol(dso, 0x250) != alias) {
+ pr_debug("Merged lookup mismatch!\n");
+ goto out;
+ }
+ }
+
+ ret = TEST_OK;
+out:
+ dso__put(dso);
+ return ret;
+}
+
+static int test_symbols_equal_start_aliases(void)
+{
+ struct dso *dso = dso__new("/tmp/perf_test_equal_start_aliases");
+ struct map *map = NULL;
+ struct symbols *symbols;
+ struct symbol *sized_sym, *zero_alias, *last_sized, *last_short, *found;
+ int ret = TEST_FAIL;
+
+ if (!dso)
+ return TEST_FAIL;
+
+ map = map__new2(0, dso);
+ if (!map)
+ goto out;
+
+ symbols = dso__symbols(dso);
+ sized_sym = symbol__new(0x1000, 0x40, STB_GLOBAL, STT_FUNC, "sized_sym");
+ zero_alias = symbol__new(0x1000, 0, STB_GLOBAL, STT_FUNC, "zero_alias");
+ last_sized = symbol__new(0x2000, 0x80, STB_GLOBAL, STT_FUNC, "last_sized");
+ if (!sized_sym || !zero_alias || !last_sized) {
+ symbol__delete(sized_sym);
+ symbol__delete(zero_alias);
+ symbol__delete(last_sized);
+ goto out;
+ }
+
+ if (symbols__insert(symbols, sized_sym)) {
+ symbol__delete(zero_alias);
+ symbol__delete(last_sized);
+ goto out;
+ }
+ if (symbols__insert(symbols, zero_alias)) {
+ symbol__delete(last_sized);
+ goto out;
+ }
+ if (symbols__insert(symbols, last_sized))
+ goto out;
+
+ /*
+ * With 3 entries [0x1000..0x1040, 0x1000..0x1000, 0x2000..0x2080], a
+ * lookup at 0x1020 must rewind past the trailing zero-length alias at
+ * 0x1000 and find sized_sym.
+ */
+ found = dso__find_symbol(dso, 0x1020);
+ if (found != sized_sym) {
+ pr_debug("Expected sized_sym at 0x1020, got %s\n",
+ found ? found->name : "NULL");
+ goto out;
+ }
+
+ /*
+ * symbols__fixup_end() must not inflate zero_alias to 0x2000 when
+ * sized_sym already provides a non-zero size at 0x1000.
+ */
+ symbols__fixup_end(symbols, /*is_kallsyms=*/false);
+ if (zero_alias->end != 0x1000) {
+ pr_debug("zero_alias inflated to %#" PRIx64 "\n", zero_alias->end);
+ goto out;
+ }
+ symbols__fixup_duplicate(symbols);
+ found = dso__find_symbol(dso, 0x1020);
+ if (found != sized_sym || found->end != 0x1040) {
+ pr_debug("After dedup expected sized_sym [0x1000, 0x1040), got %s\n",
+ found ? found->name : "NULL");
+ goto out;
+ }
+
+ /*
+ * Append a shorter alias at the final start address 0x2000 (as when
+ * symbol_conf.allow_aliases is set) and verify map__fixup_end() uses
+ * the maximum end across the equal-start group.
+ */
+ last_short = symbol__new(0x2000, 0x10, STB_WEAK, STT_FUNC, "last_short");
+ if (!last_short || symbols__insert(symbols, last_short))
+ goto out;
+
+ map__fixup_end(map);
+ if (map__end(map) != 0x2080) {
+ pr_debug("Expected map end 0x2080, got %#" PRIx64 "\n", map__end(map));
+ goto out;
+ }
+
+ ret = TEST_OK;
+out:
+ map__put(map);
+ dso__put(dso);
+ return ret;
+}
+
static int test__symbols(struct test_suite *test __maybe_unused, int subtest __maybe_unused)
{
char filename[PATH_MAX];
struct test_info ti;
int ret;
+ ret = test_symbols_sorted_insert();
+ if (ret != TEST_OK)
+ return ret;
+
+ ret = test_symbols_equal_start_aliases();
+ if (ret != TEST_OK)
+ return ret;
+
+ ret = test_symbols_shrink();
+ if (ret != TEST_OK)
+ return ret;
+
+ ret = test_dsos_shrink();
+ if (ret != TEST_OK)
+ return ret;
+
+ ret = test_session_alloc_shrink();
+ if (ret != TEST_OK)
+ return ret;
+
ret = init_test_info(&ti);
if (ret != TEST_OK)
return ret;
@@ -240,24 +987,28 @@ static int test__symbols(struct test_suite *test __maybe_unused, int subtest __m
struct kallsyms_sym {
u64 start;
+ u8 binding;
const char *name;
};
/*
* kallsyms from an x86 host where nf_tables was loaded in the page right
* after the last symbol of dca, plus a kernel symbol followed closely by a
- * module and a module far away from the others.
+ * module, a weak/global alias pair at the same address, and a module far
+ * away from the others.
*/
static const struct kallsyms_sym kallsyms_syms[] = {
- { 0xffffffff81000000, "_stext" },
- { 0xffffffff81000ff0, "last_kernel_symbol" },
- { 0xffffffff81001000, "near_module_symbol\t[near]" },
- { 0xffffffffc0c4aa40, "dca_exit\t[dca]" },
- { 0xffffffffc0c4aa50, "dca_sysfs_exit\t[dca]" },
- { 0xffffffffc0c4b000, "__nft_trace_packet\t[nf_tables]" },
- { 0xffffffffc0c4b0b0, "nft_do_chain\t[nf_tables]" },
- { 0xffffffffc0c4b4e0, "nf_tables_core_module_exit\t[nf_tables]" },
- { 0xffffffffc2000000, "far_module_symbol\t[far]" },
+ { 0xffffffff81000000, STB_GLOBAL, "_stext" },
+ { 0xffffffff81000500, STB_WEAK, "weak_alias_symbol" },
+ { 0xffffffff81000500, STB_GLOBAL, "global_target_symbol" },
+ { 0xffffffff81000ff0, STB_GLOBAL, "last_kernel_symbol" },
+ { 0xffffffff81001000, STB_GLOBAL, "near_module_symbol\t[near]" },
+ { 0xffffffffc0c4aa40, STB_GLOBAL, "dca_exit\t[dca]" },
+ { 0xffffffffc0c4aa50, STB_GLOBAL, "dca_sysfs_exit\t[dca]" },
+ { 0xffffffffc0c4b000, STB_GLOBAL, "__nft_trace_packet\t[nf_tables]" },
+ { 0xffffffffc0c4b0b0, STB_GLOBAL, "nft_do_chain\t[nf_tables]" },
+ { 0xffffffffc0c4b4e0, STB_GLOBAL, "nf_tables_core_module_exit\t[nf_tables]" },
+ { 0xffffffffc2000000, STB_GLOBAL, "far_module_symbol\t[far]" },
};
static int check_symbol(struct dso *dso, u64 addr, const char *name, u64 end)
@@ -287,7 +1038,8 @@ static int test__kallsyms_fixup_end(struct test_suite *test __maybe_unused,
return TEST_FAIL;
for (unsigned int i = 0; i < ARRAY_SIZE(kallsyms_syms); i++) {
- struct symbol *sym = symbol__new(kallsyms_syms[i].start, 0, 0, 0,
+ struct symbol *sym = symbol__new(kallsyms_syms[i].start, 0,
+ kallsyms_syms[i].binding, STT_FUNC,
kallsyms_syms[i].name);
if (!sym)
@@ -296,8 +1048,13 @@ static int test__kallsyms_fixup_end(struct test_suite *test __maybe_unused,
}
symbols__fixup_end(dso__symbols(dso), true);
+ symbols__fixup_duplicate(dso__symbols(dso));
ret = TEST_OK;
+ /* Same-address weak/global alias pair resolves to global_target_symbol. */
+ if (check_symbol(dso, 0xffffffff81000510, "global_target_symbol",
+ 0xffffffff81000ff0))
+ ret = TEST_FAIL;
/* The next symbol is too close for the end of the page. */
if (check_symbol(dso, 0xffffffff81000ff8, "last_kernel_symbol",
0xffffffff81001000))
--
2.56.1.750.gf70dc682cf-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
@ 2026-11-21 7:26 ` sashiko-bot
0 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-11-21 7:26 UTC (permalink / raw)
To: Ian Rogers; +Cc: linux-perf-users
Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [Low] perf symbol: redundant prefix scan in symbols__sort_locked()
fast path
--
commit 1abf9914a30c24a8a1249efd5024c7868a9413c0
Author: Ian Rogers <irogers@google.com>
perf symbol: Optimize incremental symbol insertion with sorted tail
This commit optimizes incremental symbol insertion and small-append sorting
by tracking a sorted prefix length in struct symbols, adding an in-place
binary insertion fast path for small appends, and maintaining a sorted tail
buffer for out-of-order dynamic symbol insertions.
> diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
> index 114fe5ea38915..0eaeced63cd47 100644
> --- a/tools/perf/util/symbol.c
> +++ b/tools/perf/util/symbol.c
[ ... ]
> @@ -432,12 +434,47 @@ static void symbols__sort_range_with_tmp(struct symbol **arr, unsigned int n,
>
> static void symbols__sort_locked(struct symbols *symbols)
> {
> - if (symbols->sorted)
> + unsigned int m = symbols->sorted_cnt;
> + unsigned int k;
> +
> + if (symbols->sorted && symbols->sorted_cnt == symbols->cnt)
> + return;
> +
> + if (m > symbols->cnt)
> + m = 0;
> + k = symbols->cnt - m;
> +
> + if (k == 0) {
> + symbols->sorted = true;
> return;
> + }
>
> - if (symbols->cnt <= 64) {
> + /*
> + * When only a few symbols have been appended since the last sort
> + * (including single-symbol insertions), insert them directly at
> + * their binary-searched sorted positions in O(N) without allocating.
> + */
> + if (k <= 8 || symbols->cnt <= 64) {
> symbols__insertion_sort_range(symbols->symbols, 0, symbols->cnt);
> - } else {
> + symbols->sorted_cnt = symbols->cnt;
> + symbols->sorted = true;
> + return;
> + }
[Severity: Low]
Does passing start = 0 to symbols__insertion_sort_range() in the k <= 8 fast
path scan the entire already-sorted prefix [0 .. m)?
tools/perf/util/symbol.c:symbols__insertion_sort_range() {
for (unsigned int i = start + 1; i < end; i++) {
struct symbol *sym = arr[i];
if (!symbol__less_or_equal(arr[i - 1], sym)) {
unsigned int pos = start +
symbols__upper_bound(&arr[start], i - start, sym);
...
}
When symbols__sort_locked() is called after 1 to 8 out-of-order symbols are
appended to a large sorted table, the loop walks i from 1 through m - 1 and
dereferences every pair of adjacent struct symbol pointers in the prefix
before reaching the k new entries at index m. Starting the insertion loop at
max(m, 1U) while keeping the binary search base at index 0 would avoid
scanning the sorted prefix.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261121071651.67118-1-irogers@google.com?part=7
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (9 preceding siblings ...)
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
@ 2026-11-21 7:35 ` sashiko-bot
10 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-11-21 7:35 UTC (permalink / raw)
To: Ian Rogers; +Cc: linux-perf-users
Sashiko has finished reviewing this 10-patch series:
- Patches 1-6 and 8-10: no issues found.
- Patch 7 ("perf symbol: Optimize incremental symbol insertion w..."): 1
potential issue (1 Low)
A detailed review has been sent as a separate reply to patch 7.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261121071651.67118-1-irogers@google.com
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2026-11-21 7:35 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
2026-11-21 7:16 ` [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after() Ian Rogers
2026-11-21 7:16 ` [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration Ian Rogers
2026-11-21 7:16 ` [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops Ian Rogers
2026-11-21 7:16 ` [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-21 7:16 ` [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort Ian Rogers
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
2026-11-21 7:26 ` sashiko-bot
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-21 7:35 ` [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking sashiko-bot
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.