Linux Perf Users
 help / color / mirror / Atom feed
From: Ian Rogers <irogers@google.com>
To: Namhyung Kim <namhyung@kernel.org>,
	Arnaldo Carvalho de Melo <acme@kernel.org>,
	 Alireza Haghdoost <haghdoost@uber.com>,
	Ian Rogers <irogers@google.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>, Jiri Olsa <jolsa@kernel.org>,
	 Adrian Hunter <adrian.hunter@intel.com>,
	James Clark <james.clark@linaro.org>,
	 linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking
Date: Fri, 20 Nov 2026 23:16:41 -0800	[thread overview]
Message-ID: <20261121071651.67118-1-irogers@google.com> (raw)

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


             reply	other threads:[~2026-11-21  7:17 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-21  7:16 Ian Rogers [this message]
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

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261121071651.67118-1-irogers@google.com \
    --to=irogers@google.com \
    --cc=acme@kernel.org \
    --cc=adrian.hunter@intel.com \
    --cc=haghdoost@uber.com \
    --cc=james.clark@linaro.org \
    --cc=jolsa@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-perf-users@vger.kernel.org \
    --cc=mingo@redhat.com \
    --cc=namhyung@kernel.org \
    --cc=peterz@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox