mirror of https://lore.kernel.org/lkml/
 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 v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking
Date: Sun, 15 Nov 2026 22:34:26 -0800	[thread overview]
Message-ID: <20261116063435.2817923-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` 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 `struct annotation`
   state even when only a tiny fraction of symbols are ever annotated.
2. `dso__symbols()` has no internal synchronization against concurrent
   readers/writers, and `struct call_path` (plus Python callchain frames
   and nodes) still retains raw `struct symbol *` pointers without
   retaining a reference on the owning `struct dso`, preventing
   unreferenced DSOs and their symbol tables from being safely reclaimed
   under memory pressure.
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, and resorts `dso->symbols` with `qsort()` even when ELF symbol
   tables are already largely ordered in ascending address runs.

Ten preparatory fixes, benchmarks, and cleanups from v4 have landed in
`perf-tools-next`. The remaining 9 patches complete DSO-owned symbol
lifetimes, remove `symbol_conf.priv_size`, speed up ELF symbol and map
loading/sorting, convert `dso->symbols` to a sorted pointer array, and add
memory shrinking APIs and unit tests:

- **DSO-owned symbol lifetimes and `priv_size` removal (Patches 1-2)**:
  - Patch 1 converts `struct call_path` and Python callchain frames/nodes
    to `struct dso_symbol` so retained symbols pin their owning `struct dso`
    for the lifetime of the call path or Python object, and adds kernel-doc
    comments to `struct dso_symbol` and `struct map_symbol` documenting the
    DSO-owned lifetime invariant.
  - Patch 2 moves `struct annotation` into an on-demand hashmap and removes
    `symbol_conf.priv_size` and `symbol__priv()`.
- **Loading and map-sorting optimizations (Patches 3-4)**:
  - Patch 3 caches ELF program and section headers in
    `dso__load_sym_internal()` and defers `elf_sym__name()` lookups until
    after non-symbol/non-allocated entries are filtered out.
  - Patch 4 adds an O(1) tail-insertion fast path and incremental binary
    insertion sort to `struct maps`.
- **Sorted symbol arrays and natural-run merge sort (Patches 5-6)**:
  - 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, galloping merge, and a sorted tail buffer with
    amortized `sqrt(N)` merge for out-of-order insertions.
- **Memory shrinking APIs and unit tests (Patches 7-9)**:
  - Patch 7 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 8 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 9 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 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
  (`symbol__start()`, `symbol__end()`, `symbol__name()`, etc.) since
  `struct symbol` is no longer wrapped in `DECLARE_RC_STRUCT(symbol)`, and
  add kernel-doc comments on `struct dso_symbol` and `struct map_symbol`
  explaining the DSO-owned symbol lifetime connection (`Patch 1`).
- Drop `SYMBOL_FLAG_ANNOTATED` from `struct symbol::flags` (avoiding the
  bit-14 overlap with lazy symbol loading) and check the `annotations`
  hashmap under `annotations_lock` with an atomic `nr_annotations` fast path
  (`Patch 2`), and return `NULL` instead of `&empty_annotation` on
  allocation failure in `symbol__annotation()` (Namhyung Kim, Alireza
  Haghdoost, Sashiko).
- Shorten `nr_maps_by_address_sorted` and `nr_maps_by_name_sorted` in
  `struct maps` to `nr_addr_sorted` and `nr_name_sorted` (`Patch 4`)
  (Namhyung Kim).
- Avoid `_dso__data_open_lock` <-> `dso__lock` lock inversion when evicting
  unreferenced DSOs or closing open DSO fds in `dsos__shrink()` /
  `dso__shrink()` (`Patch 7`), add a concurrent regression test in
  `perf test symbols` (`Patch 9`), and drop the unused `adjust` field in
  `struct elf_phdr_range` (`Patch 3`) (Sashiko).

Changes in v4:
- Add standalone fix for NULL `th` dereference on allocation failure in
  `__machine__findnew_thread()`, fix `table->lock` read-to-write
  self-deadlock in `threads__for_each_thread()`, and remove
  `perf_singlethreaded` (Sashiko).
- Handle equal-start symbol groups where a sized symbol precedes a
  zero-length or shorter alias at the same start address (`Patches 5-6`):
  use `upper_bound` plus equal-start rewind in `symbols__find_range()`,
  avoid inflating trailing zero-length aliases in `symbols__fixup_end()`
  when a sized symbol already exists at that address, scan trailing
  equal-start groups for maximum `sym->end` in `map__fixup_end()`, and
  always check the unmerged sorted tail in `symbols__find()` when
  `sorted_cnt < cnt` (Sashiko).
- Preserve owning `perf_session` across split kallsyms/kcore and ELF kernel
  DSOs, use `down_write_trylock()` in `machines__shrink()`, and add unit
  tests for equal-start aliases, unmerged tail lookups, and same-shard
  `perf_session__e_machine()` (Sashiko).

Changes in v3:
- Drop per-symbol `DECLARE_RC_STRUCT(symbol)` reference counting and
  partial symbol-table retention (`symbols__merge_retained()`) in favor of
  DSO-owned symbol lifetimes via `struct dso_symbol`, evicting a DSO's
  symbol table only as a whole when `dso` has `refcnt == 1` and no
  annotated symbols (Namhyung Kim, Alireza Haghdoost).
- Reorder the series so bug fixes and small preparatory refactorings come
  first, split the `symbols` and `maps` benchmarks, and split out the three
  independent fixes merged upstream (`c4baf52c7901`, `854dd5e7d099`,
  `baef30dd8308`) (Namhyung Kim, Alireza Haghdoost).
- Remove the `hash_bits(..., 16)` 64K-bucket cap in `annotate` and
  `db-export` hashmaps, preserve insertion order on equal-start symbols
  (`a->start <= b->start`), use stable insertion sort instead of `qsort()`
  as the allocation-failure fallback, add a sorted tail buffer with
  amortized `sqrt(N)` merge in `__symbols__insert_sorted()`, rebuild
  `symbols_by_name` on demand, and expand `perf test symbols` (Alireza
  Haghdoost, Sashiko).

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, convert `dso->symbols` to a sorted pointer array with
  natural-run merge sort, and address LKML reviewer and Sashiko feedback
  across `call-path`, `annotate`, `dso`, `map`, `symbol`, and
  `tests/symbols.c`.
- Testing performed: Built each commit (`[1/9]` through `[9/9]`) 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 (9):
  perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes
  perf annotate: Move struct annotation to a hashmap and remove
    symbol_conf.priv_size
  perf symbol-elf: Cache ELF program/section headers and defer symbol
    name lookup
  perf maps: Optimize tail insertion and small-append sorting
  perf symbol: Switch backing storage from rbtree to struct symbols
    array
  perf symbol: Optimize symbol sorting with natural-run merge sort and
    binary insertion
  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               |   16 +-
 tools/perf/builtin-kmem.c                   |   51 +-
 tools/perf/builtin-top.c                    |   21 +-
 tools/perf/tests/builtin-test.c             |    1 -
 tools/perf/tests/hists_common.c             |    5 +-
 tools/perf/tests/maps.c                     |   67 ++
 tools/perf/tests/symbols.c                  |  810 +++++++++++++-
 tools/perf/tests/vmlinux-kallsyms.c         |  181 +--
 tools/perf/ui/browser.c                     |    3 +
 tools/perf/ui/browsers/annotate.c           |   16 +-
 tools/perf/ui/browsers/hists.c              |   26 +-
 tools/perf/ui/browsers/map.c                |   62 +-
 tools/perf/ui/gtk/annotate.c                |    4 +
 tools/perf/util/annotate.c                  |  152 ++-
 tools/perf/util/annotate.h                  |    7 +-
 tools/perf/util/auxtrace.c                  |  109 +-
 tools/perf/util/block-info.c                |    2 +-
 tools/perf/util/block-range.c               |   11 +-
 tools/perf/util/call-path.c                 |   42 +-
 tools/perf/util/call-path.h                 |   10 +-
 tools/perf/util/db-export.c                 |   16 +-
 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/map_symbol.h                |   28 +
 tools/perf/util/maps.c                      |  276 ++++-
 tools/perf/util/probe-event.c               |   98 +-
 tools/perf/util/python.c                    |   53 +-
 tools/perf/util/session.c                   |   78 ++
 tools/perf/util/session.h                   |    8 +
 tools/perf/util/sort.c                      |    9 +-
 tools/perf/util/symbol-elf.c                |  251 ++++-
 tools/perf/util/symbol.c                    | 1100 +++++++++++++++----
 tools/perf/util/symbol.h                    |   92 +-
 tools/perf/util/symbol_conf.h               |    1 -
 tools/perf/util/symbol_fprintf.c            |   25 +-
 tools/perf/util/thread-stack.c              |   40 +-
 45 files changed, 3521 insertions(+), 879 deletions(-)

-- 
2.56.1.703.gf848ed807c-goog


             reply	other threads:[~2026-11-16  6:34 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16  6:34 Ian Rogers [this message]
2026-11-16  6:34 ` [PATCH v5 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes Ian Rogers
2026-11-16  6:34 ` [PATCH v5 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size Ian Rogers
2026-11-16  6:34 ` [PATCH v5 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup Ian Rogers
2026-11-16  6:34 ` [PATCH v5 4/9] perf maps: Optimize tail insertion and small-append sorting Ian Rogers
2026-11-16  6:34 ` [PATCH v5 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-16  6:34 ` [PATCH v5 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion Ian Rogers
2026-11-16  6:34 ` [PATCH v5 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-16  6:34 ` [PATCH v5 8/9] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-16  6:34 ` [PATCH v5 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers

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=20261116063435.2817923-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

all inboxes | Powered by JetHome®