Re: [PATCH v2 00/18] perf symbol: Reference counting, sorted arrays, and memory shrinking

[Ian Rogers]

On Fri, Oct 30, 2026 at 7:02 AM Alireza Haghdoost <haghdoost@xxxxxxxx> wrote:
>
> Hi Ian,
>
> I applied v2 on perf-tools-next e74880764bf9 with the ELF_C_READ_MMAP
> fix and your three fixes, and compared it with the same tree without
> the 18 patches. I posted comments are on the individual patches; this is the
> summary.
>
> On a profile of a large C++ service, about 1M symbols, perf script and perf r
> eport output is byte-identical and roughly 22-32% faster:
>
> Execution time and peak RSS before and after:
> perf script                                3.3s 334 MiB vs 2.25s 332 MiB
> perf report --sort dso,sym       3.0s 389 MiB vs 2.25s 386 MiB
> perf report --children -g caller 4.6s 706 MiB vs 3.60s 703 MiB
>
> Peak RSS barely moves. sizeof(struct symbol) goes from 48 to 32 bytes,
> but the address array adds a pointer per symbol back, so the net is
> about 8 bytes per symbol before malloc rounding. That is under 1%
> here.

Thanks for your work and running the numbers! I think we should aim to
land your lazy loading patches ahead of these patches. The merge
conflicts don't look like they'll be too terrible, wdyt?

Since the merge window for Linux v7.4 is currently open, I don't see
anything landing before November 1st. So I can do a v3 incorporating
your suggestions and rebase it on top of your patches when they land.
I'll work on pulling out the fixes (you highlighted some you thought
were particularly worthwhile) to mail for v7.4 for now.

Thanks,
Ian

> Thanks
> Alireza
>
> On Wed, Oct 28, 2026 at 1:29 PM Ian Rogers <irogers@xxxxxxxxxx> wrote:
> >
> > On Tue, Oct 27, 2026 at 4:15 PM Ian Rogers <irogers@xxxxxxxxxx> wrote:
> > >
> > > 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>
> >
> > So Sashiko failed to apply the patches (local Sashiko runs were clean)
> > because I had these four patches applied locally:
> >  - Alireza's "perf symbols: Fix broken ELF_C_READ_MMAP fallback guard"
> >    https://lore.kernel.org/linux-perf-users/20261005-perf-symbol-memory-send-v5-1-165dceb2b049@xxxxxxxx/
> >  - My fixes in "perf: Fix libdw addr2line fallback, pr_debugN
> > overhead, and cumulative hist decay"
> >    https://lore.kernel.org/linux-perf-users/cover.1792995775.git.irogers@xxxxxxxxxx/
> >
> > Hopefully the patches above won't take too long to land, so I'll hold
> > off sending v3 until then.
> >
> > Thanks,
> > Ian
> >
> > > 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
> > >