[PATCH v2 00/18] perf symbol: Reference counting, sorted arrays, and memory shrinking
From: Ian Rogers
Date: Tue Oct 27 2026 - 19:16:42 EST
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` has several structural
limitations:
1. Every `struct symbol` embeds a 24-byte `struct rb_node` for the
`dso->symbols` address rbtree, plus an optional negative-offset
allocation prefix (`symbol_conf.priv_size`) for TUI browser indices,
`db-export` IDs, or `struct annotation` state even when only a tiny
fraction of symbols are ever annotated or exported.
2. Unlike `struct map`, `struct dso`, and `struct thread`, `struct symbol`
is not reference-counted: once loaded into a `struct dso`, symbols can
never be safely evicted while `hist_entry`, `callchain_cursor_node`, or
`map_symbol` references exist, and `dso__symbols()` has no internal
synchronization against concurrent readers/writers.
3. ELF symbol table loading (`dso__load_sym_internal()`) repeatedly
invokes `libelf` section/program header lookups per symbol, calls
`elf_sym__name()` before filtering out non-function/non-allocated
symbols, runs Rust/Java demanglers on plain C symbols without fast-path
prefix checks, and resorts `dso->symbols` with `qsort()` even when ELF
symbol tables are already largely ordered in ascending address runs.
This series modernizes `struct symbol` to match the rest of `tools/perf/util`
(`DECLARE_RC_STRUCT`, `struct rw_semaphore`, sorted pointer arrays) and
introduces symbol/DSO memory shrinking and faster ELF symbol loading:
- Patch 1 adds `perf bench internals symbols` and `perf bench internals maps`
to benchmark ELF symbol loading, bulk symbol insertion/sorting/lookup,
incremental symbol appends, ascending map insertion, and incremental map
appends.
- Patch 2 adds fast-path prefix checks in `dso__demangle_sym()` (before
calling `rust_demangle_demangle()`, keeping `demangle-rust-v0.c`
unmodified relative to upstream `rustc-demangle`) and in
`java_demangle_sym()`.
- Patches 3-6 encapsulate `struct symbol` field access behind accessor
functions (annotated with `__attribute__((nonnull))`) and replace the
negative-offset `symbol_conf.priv_size` allocation prefix with on-demand
browser index calculation and per-DSO/per-exporter hashmaps for
`db-export` and `struct annotation`.
- Patch 7 replaces `dso->symbols` (`rb_root_cached`) and `dso->symbol_names`
with a locked `struct symbols` container backed by sorted pointer arrays
(`symbols` and `symbols_by_name`) protected by a `struct rw_semaphore`,
removing `struct rb_node` from `struct symbol`.
- Patch 8 wraps `struct symbol` in `DECLARE_RC_STRUCT(symbol)` with
`refcount_t` (`symbol__get()` / `symbol__put()` / `symbol__zput()`) for
sanitizer-checked reference counting across `map_symbol`, `addr_location`,
`hist_entry`, `callchain`, `thread_stack`, and `db-export`.
- Patch 9 replaces `qsort()` in `struct symbols` with a natural-run merge
sort and galloping merge (taking advantage of pre-ordered runs in
`.symtab`/`.dynsym` and `kallsyms`) plus an in-place binary insertion
fast path for small incremental appends.
- Patch 10 applies the same incremental binary-insertion sort and an O(1)
tail-insertion fast path to `struct maps` for `/proc/<pid>/maps` synthesis
and runtime `PERF_RECORD_MMAP2` / JIT map insertions.
- Patch 11 caches ELF program and section headers during
`dso__load_sym_internal()`, defers `elf_sym__name()` string table lookups
until after symbol filtering, and runs `symbols__fixup_end()` /
`symbols__fixup_duplicate()` once per DSO load.
- Patches 12-17 add `down_read_trylock()` / `down_write_trylock()`, protect
`machines->guests` with a `rw_semaphore`, implement `symbols__shrink()`,
`dso__shrink()`, `dsos__shrink()`, and `perf_session__shrink()` (with
transparent on-demand reload in `dso__load()` that preserves pointer
identity for retained symbols), and provide `perf_session__malloc()` /
`zalloc()` / `calloc()` / `realloc()` / `strdup()` wrappers that
automatically shrink unreferenced symbols and DSOs on allocation failure.
- Patch 18 adds unit tests in `perf test symbols` covering sorted symbol
insertion, symbol/DSO shrinking, transparent DSO reload after shrink, and
session allocation wrappers.
End-to-end benchmark results across the series:
perf bench internals symbols (perf binary):
Average DSO load + sort: 7.348 msec -> 5.324 msec (-27.5%)
Average DSO memory usage: 1401 KB -> 1308 KB ( -6.6%)
Average bulk insert + lookup: 1453.95 us -> 1161.00 us (-20.1%)
Average append + lookup (200 interior inserts into 10,000 symbols):
rbtree: 42.85 us -> array+qsort: 40429.75 us -> array+binary-insert: 152.70 us
perf bench internals symbols -b libLLVM.so.21.1:
Average DSO load + sort: 81.196 msec -> 62.582 msec (-22.9%)
Average DSO memory usage: 9530 KB -> 9164 KB ( -3.8%)
perf bench internals symbols -b libLLVM.so.21.1 --no-demangle:
Average DSO load + sort: 32.675 msec -> 19.122 msec (-41.5%)
Average DSO memory usage: 7589 KB -> 7229 KB ( -4.7%)
perf bench internals maps:
Average ascending insert + lookup: 63.37 us -> 58.97 us ( -6.9%)
Average append + lookup: 7477.45 us -> 96.67 us (-98.7%, 77.3x faster)
Net performance and memory trade-offs:
- Replacing the per-symbol rbtree (`struct rb_node`) and negative-offset
`symbol_conf.priv_size` allocation prefix with a contiguous sorted pointer
array reduces per-symbol heap overhead by 16 to 24+ bytes (saving 3.8% to
6.6% of total DSO symbol table heap memory unconditionally, and allowing
unreferenced symbols and DSOs to be shrunk on demand under memory
pressure).
- For the dominant symbol workloads—loading ELF binaries (`-22.9%` to
`-41.5%`) and bulk symbol insertion, sorting, and lookup (`-20.1%`)—the
contiguous array, natural-run merge sort, ELF header caching, and
demangler fast paths yield substantial speedups over the rbtree baseline.
- For synthetic single-symbol interior insertions interleaved with immediate
lookups into an already-large 10,000-symbol DSO (`dso__insert_symbol()`),
an rbtree rotation takes ~0.21 us/op (`42.85 us` for 200 ops) whereas
shifting the contiguous pointer array tail with `memmove()` after binary
search takes ~0.76 us/op (`152.70 us` for 200 ops, down from `40429.75 us`
with naive `qsort()`). In real workloads, symbols are either loaded in
bulk (`dso__load()`) or inserted into small per-prog BPF/JIT DSOs where
the array fits in a few cache lines, making this sub-microsecond
difference negligible in practice.
- Overall, the series reduces memory consumption across all workloads while
significantly improving—or remaining neutral on—runtime performance.
v2:
- Rebased onto perf-tools-next (dropping "perf symbols: Fix broken
ELF_C_READ_MMAP fallback guard", which was merged upstream, and splitting
"perf libdw: Optimize fallback logic for missing DWARF" into a separate
fixes series).
- Added 'perf bench internals symbols' and 'perf bench internals maps'
benchmarks (Patch 1) and included before/after numbers in the optimization
patches.
- Added __attribute__((nonnull)) annotations to struct symbol accessor
functions (Patch 3).
- Split the symbol_conf.priv_size removal patch into three separate patches
for map_browser (Patch 4), db-export (Patch 5), and annotate (Patch 6).
- Added dedicated optimization patches for Rust/Java demangler prefix checks
(Patch 2), natural-run merge sort and binary insertion in struct symbols
(Patch 9), tail-insertion and incremental binary-insertion sort in struct
maps (Patch 10), and ELF program/section header caching and deferred
symbol name lookup (Patch 11).
- Replaced periodic heuristic LRU shrinking and windowed ELF symbol loading
with on-demand shrinking (symbols__shrink(), dso__shrink(),
dsos__shrink(), perf_session__shrink()) triggered on allocation failure via
session-scoped allocation wrappers, plus transparent DSO reload preserving
retained symbol pointers (Patches 12-18).
v1: https://lore.kernel.org/lkml/20260928075237.3055101-1-irogers@xxxxxxxxxx/
Assisted-by: Antigravity:gemini-3.1-pro
Signed-off-by: Ian Rogers <irogers@xxxxxxxxxx>
Ian Rogers (18):
perf bench internals: Add symbols and maps benchmarks
perf demangle: Add fast-path prefix checks for Rust and Java
demanglers
perf symbol: Add accessor functions for struct symbol fields
perf map_browser: Compute symbol browser index on demand
perf db-export: Store symbol database IDs in a hashmap
perf annotate: Move struct annotation to a hashmap and remove
symbol_conf.priv_size
perf symbol: Switch backing storage from rbtree to struct symbols
array
perf symbol: Add reference counting and DECLARE_RC_STRUCT(symbol)
perf symbol: Optimize symbol sorting with natural-run merge sort and
binary insertion
perf maps: Optimize tail insertion and small-append sorting
perf symbol-elf: Cache ELF program/section headers and defer symbol
name lookup
perf rwsem: Add down_read_trylock() and down_write_trylock()
perf vdso: Constify dso parameter in dso__is_vdso()
perf machine: Protect machines->guests rbtree with a rw_semaphore
perf symbol: Add memory shrinking for symbols, DSOs, and machines
perf session: Add dso__session() and session-scoped allocation
wrappers
perf symbol: Use session allocation wrappers in symbol, DSO, thread,
and hist paths
perf test symbols: Add tests for symbol shrinking and session alloc
wrappers
tools/perf/Documentation/perf-bench.txt | 6 +
.../arch/powerpc/util/skip-callchain-idx.c | 2 +-
tools/perf/arch/powerpc/util/sym-handling.c | 40 +-
tools/perf/bench/Build | 2 +
tools/perf/bench/bench.h | 2 +
tools/perf/bench/maps.c | 186 +++
tools/perf/bench/symbols.c | 239 +++
tools/perf/builtin-annotate.c | 22 +-
tools/perf/builtin-bench.c | 2 +
tools/perf/builtin-c2c.c | 14 -
tools/perf/builtin-diff.c | 4 +-
tools/perf/builtin-kallsyms.c | 9 +-
tools/perf/builtin-kmem.c | 82 +-
tools/perf/builtin-kwork.c | 4 +-
tools/perf/builtin-lock.c | 25 +-
tools/perf/builtin-mem.c | 2 +-
tools/perf/builtin-report.c | 14 -
tools/perf/builtin-sched.c | 6 +-
tools/perf/builtin-script.c | 18 +-
tools/perf/builtin-timechart.c | 2 +-
tools/perf/builtin-top.c | 24 +-
tools/perf/builtin-trace.c | 23 +-
tools/perf/tests/builtin-test.c | 1 -
tools/perf/tests/dlfilter-test.c | 12 +-
tools/perf/tests/dwarf-unwind.c | 2 +-
tools/perf/tests/hists_common.c | 9 +-
tools/perf/tests/hists_cumulate.c | 8 +-
tools/perf/tests/hists_filter.c | 10 +-
tools/perf/tests/hists_link.c | 16 +-
tools/perf/tests/hists_output.c | 9 +-
tools/perf/tests/kallsyms-split.c | 5 +-
tools/perf/tests/maps.c | 58 +
tools/perf/tests/pe-file-parsing.c | 1 +
tools/perf/tests/symbols.c | 454 +++++-
tools/perf/tests/vmlinux-kallsyms.c | 187 ++-
tools/perf/ui/browser.c | 3 +
tools/perf/ui/browsers/annotate.c | 10 +-
tools/perf/ui/browsers/hists.c | 35 +-
tools/perf/ui/browsers/map.c | 88 +-
tools/perf/ui/gtk/annotate.c | 6 +-
tools/perf/ui/stdio/hist.c | 6 +-
tools/perf/util/addr2line.c | 8 +-
tools/perf/util/addr_location.c | 4 +
.../perf/util/annotate-arch/annotate-alpha.c | 5 +-
.../perf/util/annotate-arch/annotate-arm64.c | 12 +-
.../util/annotate-arch/annotate-loongarch.c | 15 +-
tools/perf/util/annotate-arch/annotate-s390.c | 6 +-
tools/perf/util/annotate-arch/annotate-x86.c | 14 +-
tools/perf/util/annotate-data.c | 12 +-
tools/perf/util/annotate.c | 211 ++-
tools/perf/util/annotate.h | 6 +-
tools/perf/util/auxtrace.c | 111 +-
tools/perf/util/block-info.c | 12 +-
tools/perf/util/bpf_lock_contention.c | 35 +-
tools/perf/util/c2c-function.c | 32 +-
tools/perf/util/call-path.c | 15 +-
tools/perf/util/callchain.c | 23 +-
tools/perf/util/capstone.c | 22 +-
tools/perf/util/data-convert-json.c | 4 +-
tools/perf/util/db-export.c | 99 +-
tools/perf/util/db-export.h | 8 +
tools/perf/util/debug.c | 3 +-
tools/perf/util/demangle-java.c | 23 +-
tools/perf/util/disasm.c | 69 +-
tools/perf/util/dlfilter.c | 12 +-
tools/perf/util/dso.c | 257 ++-
tools/perf/util/dso.h | 94 +-
tools/perf/util/dsos.c | 76 +
tools/perf/util/dsos.h | 3 +
tools/perf/util/event.c | 12 +-
tools/perf/util/evsel_fprintf.c | 2 +-
tools/perf/util/hist.c | 70 +-
tools/perf/util/intel-pt.c | 74 +-
tools/perf/util/libbfd.c | 14 +-
tools/perf/util/libdw.c | 5 +-
tools/perf/util/llvm.c | 8 +-
tools/perf/util/lock-contention.c | 8 +-
tools/perf/util/machine.c | 189 ++-
tools/perf/util/machine.h | 9 +
tools/perf/util/map.c | 27 +-
tools/perf/util/map.h | 18 +-
tools/perf/util/map_symbol.c | 4 +-
tools/perf/util/maps.c | 284 +++-
tools/perf/util/mutex.h | 3 +
tools/perf/util/probe-event.c | 148 +-
tools/perf/util/python.c | 36 +-
tools/perf/util/rwsem.c | 20 +
tools/perf/util/rwsem.h | 2 +
tools/perf/util/session.c | 78 +
tools/perf/util/session.h | 8 +
tools/perf/util/sort.c | 47 +-
tools/perf/util/srcline.c | 22 +-
tools/perf/util/symbol-elf.c | 311 +++-
tools/perf/util/symbol.c | 1438 +++++++++++++----
tools/perf/util/symbol.h | 187 ++-
tools/perf/util/symbol_conf.h | 1 -
tools/perf/util/symbol_fprintf.c | 37 +-
tools/perf/util/thread-stack.c | 18 +-
tools/perf/util/threads.c | 17 +-
tools/perf/util/unwind-libdw.c | 4 +-
tools/perf/util/unwind-libunwind.c | 2 +-
tools/perf/util/vdso.c | 2 +-
tools/perf/util/vdso.h | 2 +-
103 files changed, 4557 insertions(+), 1389 deletions(-)
create mode 100644 tools/perf/bench/maps.c
create mode 100644 tools/perf/bench/symbols.c
--
2.56.0.313.g2479322e68-goog