* [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking
@ 2026-11-16 6:34 Ian Rogers
2026-11-16 6:34 ` [PATCH v5 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes Ian Rogers
` (8 more replies)
0 siblings, 9 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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` 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v5 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
@ 2026-11-16 6:34 ` Ian Rogers
2026-11-16 6:44 ` sashiko-bot
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
` (7 subsequent siblings)
8 siblings, 1 reply; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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
struct call_path stores resolved function symbols for the lifetime of a
call_path_root (in thread-stack call/return processing and db-export)
without holding a map reference. Similarly, Python callchain frames and
nodes store resolved symbols across Python object lifetimes.
Replace bare struct symbol * fields in struct call_path,
struct pyrf_callchain_frame, and struct pyrf_callchain_node with
struct dso_symbol so that each retained symbol pins its owning
struct dso until call_path_root__free() or Python deallocation. In
python.c, this also avoids duplicating symbol names for call_path frames
and allows pyrf_callchain_node__get_dso() to report the DSO of resolved
call_path symbols whose ip was zeroed. Also document the DSO-owned
symbol lifetime invariants in kernel-doc comments on struct dso_symbol
and struct map_symbol.
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/call-path.c | 42 ++++++++++++++++++++-------
tools/perf/util/call-path.h | 10 ++++---
tools/perf/util/db-export.c | 12 ++++++--
tools/perf/util/map_symbol.h | 28 ++++++++++++++++++
tools/perf/util/python.c | 53 +++++++++++++++-------------------
tools/perf/util/thread-stack.c | 40 +++++++++++++------------
6 files changed, 121 insertions(+), 64 deletions(-)
diff --git a/tools/perf/util/call-path.c b/tools/perf/util/call-path.c
index 5c60b8be1cf6..eac52a902d6b 100644
--- a/tools/perf/util/call-path.c
+++ b/tools/perf/util/call-path.c
@@ -10,13 +10,21 @@
#include <stdlib.h>
#include "call-path.h"
+#include "dso.h"
static void call_path__init(struct call_path *cp, struct call_path *parent,
- struct symbol *sym, u64 ip, bool in_kernel)
+ const struct dso_symbol *ds, u64 ip, bool in_kernel)
{
+ struct symbol *sym = ds ? ds->sym : NULL;
+
cp->parent = parent;
- cp->sym = sym;
- cp->ip = sym ? 0 : ip;
+ if (sym) {
+ dso_symbol__copy(&cp->ds, ds);
+ cp->ip = 0;
+ } else {
+ cp->ds = (struct dso_symbol){};
+ cp->ip = ip;
+ }
cp->db_id = 0;
cp->in_kernel = in_kernel;
RB_CLEAR_NODE(&cp->rb_node);
@@ -39,7 +47,13 @@ void call_path_root__free(struct call_path_root *cpr)
{
struct call_path_block *pos, *n;
+ if (!cpr)
+ return;
+
+ dso_symbol__exit(&cpr->call_path.ds);
list_for_each_entry_safe(pos, n, &cpr->blocks, node) {
+ for (size_t i = 0; i < CALL_PATH_BLOCK_SIZE; i++)
+ dso_symbol__exit(&pos->cp[i].ds);
list_del_init(&pos->node);
free(pos);
}
@@ -48,7 +62,7 @@ void call_path_root__free(struct call_path_root *cpr)
static struct call_path *call_path__new(struct call_path_root *cpr,
struct call_path *parent,
- struct symbol *sym, u64 ip,
+ const struct dso_symbol *ds, u64 ip,
bool in_kernel)
{
struct call_path_block *cpb;
@@ -69,17 +83,20 @@ static struct call_path *call_path__new(struct call_path_root *cpr,
n = cpr->next++ & CALL_PATH_BLOCK_MASK;
cp = &cpb->cp[n];
- call_path__init(cp, parent, sym, ip, in_kernel);
+ call_path__init(cp, parent, ds, ip, in_kernel);
return cp;
}
struct call_path *call_path__findnew(struct call_path_root *cpr,
struct call_path *parent,
- struct symbol *sym, u64 ip, u64 ks)
+ const struct dso_symbol *ds,
+ u64 ip, u64 ks)
{
struct rb_node **p;
struct rb_node *node_parent = NULL;
+ struct symbol *sym = ds ? ds->sym : NULL;
+ const void *dso_ptr = (sym && ds->dso) ? RC_CHK_ACCESS(ds->dso) : NULL;
struct call_path *cp;
bool in_kernel = ip >= ks;
@@ -87,23 +104,28 @@ struct call_path *call_path__findnew(struct call_path_root *cpr,
ip = 0;
if (!parent)
- return call_path__new(cpr, parent, sym, ip, in_kernel);
+ return call_path__new(cpr, parent, ds, ip, in_kernel);
p = &parent->children.rb_node;
while (*p != NULL) {
+ const void *cp_dso_ptr;
+
node_parent = *p;
cp = rb_entry(node_parent, struct call_path, rb_node);
+ cp_dso_ptr = cp->ds.dso ? RC_CHK_ACCESS(cp->ds.dso) : NULL;
- if (cp->sym == sym && cp->ip == ip)
+ if (cp->ds.sym == sym && cp_dso_ptr == dso_ptr && cp->ip == ip)
return cp;
- if (sym < cp->sym || (sym == cp->sym && ip < cp->ip))
+ if (sym < cp->ds.sym ||
+ (sym == cp->ds.sym && dso_ptr < cp_dso_ptr) ||
+ (sym == cp->ds.sym && dso_ptr == cp_dso_ptr && ip < cp->ip))
p = &(*p)->rb_left;
else
p = &(*p)->rb_right;
}
- cp = call_path__new(cpr, parent, sym, ip, in_kernel);
+ cp = call_path__new(cpr, parent, ds, ip, in_kernel);
if (!cp)
return NULL;
diff --git a/tools/perf/util/call-path.h b/tools/perf/util/call-path.h
index 5875cfc8106e..e43aa7513633 100644
--- a/tools/perf/util/call-path.h
+++ b/tools/perf/util/call-path.h
@@ -11,12 +11,13 @@
#include <linux/types.h>
#include <linux/rbtree.h>
+#include "map_symbol.h"
/**
* struct call_path - node in list of calls leading to a function call.
* @parent: call path to the parent function call
- * @sym: symbol of function called
- * @ip: only if sym is null, the ip of the function
+ * @ds: DSO and symbol of function called
+ * @ip: only if ds.sym is null, the ip of the function
* @db_id: id used for db-export
* @in_kernel: whether function is a in the kernel
* @rb_node: node in parent's tree of called functions
@@ -27,7 +28,7 @@
*/
struct call_path {
struct call_path *parent;
- struct symbol *sym;
+ struct dso_symbol ds;
u64 ip;
u64 db_id;
bool in_kernel;
@@ -63,6 +64,7 @@ void call_path_root__free(struct call_path_root *cpr);
struct call_path *call_path__findnew(struct call_path_root *cpr,
struct call_path *parent,
- struct symbol *sym, u64 ip, u64 ks);
+ const struct dso_symbol *ds,
+ u64 ip, u64 ks);
#endif
diff --git a/tools/perf/util/db-export.c b/tools/perf/util/db-export.c
index 8e08b306c8d3..e7b807e968cf 100644
--- a/tools/perf/util/db-export.c
+++ b/tools/perf/util/db-export.c
@@ -361,12 +361,18 @@ static struct call_path *call_path_from_sample(struct db_export *dbe,
db_ids_from_al(dbe, &al, &dso_db_id, &sym_db_id, &offset);
/* add node to the call path tree if it doesn't exist */
- current = call_path__findnew(dbe->cpr, current,
- al.sym, node->ip,
- kernel_start);
+ {
+ struct dso_symbol ds = dso_symbol__from_al(&al);
+
+ current = call_path__findnew(dbe->cpr, current,
+ &ds, node->ip,
+ kernel_start);
+ }
callchain_cursor_advance(cursor);
addr_location__exit(&al);
+ if (!current)
+ break;
}
/* Reset the callchain order to its prior value. */
diff --git a/tools/perf/util/map_symbol.h b/tools/perf/util/map_symbol.h
index 1781af7bd965..ee53b743fcc1 100644
--- a/tools/perf/util/map_symbol.h
+++ b/tools/perf/util/map_symbol.h
@@ -11,11 +11,39 @@ struct maps;
struct map;
struct symbol;
+/**
+ * struct dso_symbol - A symbol paired with a reference to its owning DSO.
+ * @dso: Reference-counted DSO (dso__get() / dso__put()) whose symbol table
+ * owns the lifetime of @sym. May be %NULL when @sym is %NULL or points
+ * to a synthetic symbol not owned by a DSO.
+ * @sym: Non-reference-counted symbol pointer borrowed from @dso.
+ *
+ * struct symbol is not independently reference counted; its memory is owned
+ * by the symbol table of its containing struct dso. Callers that retain a
+ * struct symbol pointer beyond a transient lookup without needing the mapping
+ * context of a struct map must hold a reference on @dso (managed via
+ * dso_symbol__from_al(), dso_symbol__copy(), and dso_symbol__exit()) so @dso
+ * and its symbol table cannot be shrunk or freed while @sym is in use.
+ */
struct dso_symbol {
struct dso *dso;
struct symbol *sym;
};
+/**
+ * struct map_symbol - A resolved symbol together with its thread and mapping.
+ * @thread: Optional reference-counted thread (thread__get() / thread__put())
+ * in whose address space @map was resolved.
+ * @map: Reference-counted mapping (map__get() / map__put()). Holding a
+ * reference on @map transitively pins map__dso(@map), which in turn
+ * keeps @sym alive for the lifetime of this struct map_symbol.
+ * @sym: Non-reference-counted symbol pointer borrowed from map__dso(@map).
+ *
+ * Unlike struct dso_symbol, struct map_symbol preserves the virtual-address
+ * mapping (@map) and optional @thread context in addition to pinning @sym's
+ * lifetime transitively through @map's reference on its struct dso (managed
+ * via map_symbol__copy() and map_symbol__exit()).
+ */
struct map_symbol {
struct thread *thread;
struct map *map;
diff --git a/tools/perf/util/python.c b/tools/perf/util/python.c
index 902157c472b3..18dfe21104f4 100644
--- a/tools/perf/util/python.c
+++ b/tools/perf/util/python.c
@@ -937,14 +937,13 @@ struct pyrf_callchain_node {
PyObject_HEAD
u64 ip;
struct map *map;
- struct symbol *sym;
- char *sym_name;
+ struct dso_symbol ds;
};
static void pyrf_callchain_node__delete(struct pyrf_callchain_node *pnode)
{
map__put(pnode->map);
- free(pnode->sym_name);
+ dso_symbol__exit(&pnode->ds);
Py_TYPE(pnode)->tp_free((PyObject *)pnode);
}
@@ -957,27 +956,22 @@ static PyObject *pyrf_callchain_node__get_ip(struct pyrf_callchain_node *pnode,
static PyObject *pyrf_callchain_node__get_symbol(struct pyrf_callchain_node *pnode,
void *closure __maybe_unused)
{
- if (pnode->sym_name)
- return PyUnicode_FromString(pnode->sym_name);
- if (pnode->sym)
- return PyUnicode_FromString(pnode->sym->name);
+ if (pnode->ds.sym)
+ return PyUnicode_FromString(pnode->ds.sym->name);
return PyUnicode_FromString("[unknown]");
}
static PyObject *pyrf_callchain_node__get_dso(struct pyrf_callchain_node *pnode,
void *closure __maybe_unused)
{
+ struct dso *dso = pnode->ds.dso ?: (pnode->map ? map__dso(pnode->map) : NULL);
const char *dsoname = "[unknown]";
- if (pnode->map) {
- struct dso *dso = map__dso(pnode->map);
-
- if (dso) {
- if (symbol_conf.show_kernel_path && dso__long_name(dso))
- dsoname = dso__long_name(dso);
- else
- dsoname = dso__name(dso);
- }
+ if (dso) {
+ if (symbol_conf.show_kernel_path && dso__long_name(dso))
+ dsoname = dso__long_name(dso);
+ else
+ dsoname = dso__name(dso);
}
return PyUnicode_FromString(dsoname);
}
@@ -987,11 +981,11 @@ static PyObject *pyrf_callchain_node__get_sym_offset(struct pyrf_callchain_node
{
u64 addr;
- if (!pnode->sym)
+ if (!pnode->ds.sym || (!pnode->map && !pnode->ip))
Py_RETURN_NONE;
addr = pnode->map ? map__map_ip(pnode->map, pnode->ip) : pnode->ip;
- return PyLong_FromUnsignedLongLong(addr - pnode->sym->start);
+ return PyLong_FromUnsignedLongLong(addr - pnode->ds.sym->start);
}
static PyGetSetDef pyrf_callchain_node__getset[] = {
@@ -1015,8 +1009,7 @@ static PyTypeObject pyrf_callchain_node__type = {
struct pyrf_callchain_frame {
u64 ip;
struct map *map;
- struct symbol *sym;
- char *sym_name;
+ struct dso_symbol ds;
};
struct pyrf_callchain {
@@ -1030,7 +1023,7 @@ static void pyrf_callchain__delete(struct pyrf_callchain *pchain)
if (pchain->frames) {
for (u64 i = 0; i < pchain->nr_frames; i++) {
map__put(pchain->frames[i].map);
- free(pchain->frames[i].sym_name);
+ dso_symbol__exit(&pchain->frames[i].ds);
}
free(pchain->frames);
}
@@ -1060,8 +1053,7 @@ static PyObject *pyrf_callchain__item(PyObject *obj, Py_ssize_t i)
pnode->ip = pchain->frames[i].ip;
pnode->map = map__get(pchain->frames[i].map);
- pnode->sym = pchain->frames[i].sym;
- pnode->sym_name = pchain->frames[i].sym_name ? strdup(pchain->frames[i].sym_name) : NULL;
+ dso_symbol__copy(&pnode->ds, &pchain->frames[i].ds);
return (PyObject *)pnode;
}
@@ -1111,10 +1103,16 @@ static int pyrf_sample_event__resolve_callchain(struct pyrf_event *pevent)
return -ENOMEM;
}
for (u64 i = 0; i < pchain->nr_frames; i++) {
+ struct dso_symbol ds;
+
node = callchain_cursor_current(cursor);
+ ds = (struct dso_symbol){
+ .dso = (node->ms.sym && node->ms.map) ? map__dso(node->ms.map) : NULL,
+ .sym = node->ms.sym,
+ };
pchain->frames[i].ip = node->ip;
pchain->frames[i].map = map__get(node->ms.map);
- pchain->frames[i].sym = node->ms.sym;
+ dso_symbol__copy(&pchain->frames[i].ds, &ds);
callchain_cursor_advance(cursor);
}
pevent->callchain = (PyObject *)pchain;
@@ -4504,10 +4502,9 @@ static PyObject *pyrf_call_path__to_callchain(const struct call_path *cp,
struct pyrf_callchain_frame *frame = &pchain->frames[--nr_frames];
frame->ip = pos->ip;
- frame->sym = NULL;
- frame->sym_name = pos->sym ? strdup(pos->sym->name) : NULL;
+ dso_symbol__copy(&frame->ds, &pos->ds);
frame->map = NULL;
- if (thread) {
+ if (thread && !pos->ds.sym) {
struct addr_location al;
u8 cpumode = pos->in_kernel ? PERF_RECORD_MISC_KERNEL
: PERF_RECORD_MISC_USER;
@@ -4515,8 +4512,6 @@ static PyObject *pyrf_call_path__to_callchain(const struct call_path *cp,
addr_location__init(&al);
thread__find_map(thread, cpumode, pos->ip, &al);
frame->map = map__get(al.map);
- if (frame->map)
- frame->sym = pos->sym;
addr_location__exit(&al);
}
}
diff --git a/tools/perf/util/thread-stack.c b/tools/perf/util/thread-stack.c
index d452d1a7eabb..aa05acb0467c 100644
--- a/tools/perf/util/thread-stack.c
+++ b/tools/perf/util/thread-stack.c
@@ -11,6 +11,7 @@
#include <errno.h>
#include <stdlib.h>
#include <string.h>
+#include "addr_location.h"
#include "thread.h"
#include "event.h"
#include "machine.h"
@@ -823,7 +824,7 @@ static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts,
if (ts->cnt == 1) {
struct thread_stack_entry *tse = &ts->stack[0];
- if (tse->cp->sym == sym)
+ if (tse->cp->ds.sym == sym)
return thread_stack__call_return(thread, ts, --ts->cnt,
timestamp, ref, false);
}
@@ -862,21 +863,21 @@ static int thread_stack__bottom(struct thread_stack *ts,
struct addr_location *to_al, u64 ref)
{
struct call_path_root *cpr = ts->crp->cpr;
+ struct dso_symbol ds;
struct call_path *cp;
- struct symbol *sym;
u64 ip;
if (sample->ip) {
ip = sample->ip;
- sym = from_al->sym;
+ ds = dso_symbol__from_al(from_al);
} else if (sample->addr) {
ip = sample->addr;
- sym = to_al->sym;
+ ds = dso_symbol__from_al(to_al);
} else {
return 0;
}
- cp = call_path__findnew(cpr, &cpr->call_path, sym, ip,
+ cp = call_path__findnew(cpr, &cpr->call_path, &ds, ip,
ts->kernel_start);
return thread_stack__push_cp(ts, ip, sample->time, ref, cp,
@@ -908,8 +909,8 @@ static int thread_stack__no_call_return(struct thread *thread,
{
struct call_path_root *cpr = ts->crp->cpr;
struct call_path *root = &cpr->call_path;
- struct symbol *fsym = from_al->sym;
- struct symbol *tsym = to_al->sym;
+ struct dso_symbol fds = dso_symbol__from_al(from_al);
+ struct dso_symbol tds = dso_symbol__from_al(to_al);
struct call_path *cp, *parent;
u64 ks = ts->kernel_start;
u64 addr = sample->addr;
@@ -925,7 +926,7 @@ static int thread_stack__no_call_return(struct thread *thread,
/* If the stack is empty, push the userspace address */
if (!ts->cnt) {
- cp = call_path__findnew(cpr, root, tsym, addr, ks);
+ cp = call_path__findnew(cpr, root, &tds, addr, ks);
return thread_stack__push_cp(ts, 0, tm, ref, cp, true,
false);
}
@@ -941,7 +942,7 @@ static int thread_stack__no_call_return(struct thread *thread,
else
parent = root;
- if (parent->sym == from_al->sym) {
+ if (parent->ds.sym == from_al->sym) {
/*
* At the bottom of the stack, assume the missing 'call' was
* before the trace started. So, pop the current symbol and push
@@ -955,7 +956,7 @@ static int thread_stack__no_call_return(struct thread *thread,
}
if (!ts->cnt) {
- cp = call_path__findnew(cpr, root, tsym, addr, ks);
+ cp = call_path__findnew(cpr, root, &tds, addr, ks);
return thread_stack__push_cp(ts, addr, tm, ref, cp,
true, false);
@@ -965,7 +966,7 @@ static int thread_stack__no_call_return(struct thread *thread,
* Otherwise assume the 'return' is being used as a jump (e.g.
* retpoline) and just push the 'to' symbol.
*/
- cp = call_path__findnew(cpr, parent, tsym, addr, ks);
+ cp = call_path__findnew(cpr, parent, &tds, addr, ks);
err = thread_stack__push_cp(ts, 0, tm, ref, cp, true, false);
if (!err)
@@ -979,13 +980,13 @@ static int thread_stack__no_call_return(struct thread *thread,
* pop 'from'.
*/
- cp = call_path__findnew(cpr, parent, tsym, addr, ks);
+ cp = call_path__findnew(cpr, parent, &tds, addr, ks);
err = thread_stack__push_cp(ts, addr, tm, ref, cp, true, false);
if (err)
return err;
- cp = call_path__findnew(cpr, cp, fsym, ip, ks);
+ cp = call_path__findnew(cpr, cp, &fds, ip, ks);
err = thread_stack__push_cp(ts, ip, tm, ref, cp, true, false);
if (err)
@@ -1052,7 +1053,8 @@ static int thread_stack__x86_retpoline(struct thread_stack *ts,
{
struct thread_stack_entry *tse = &ts->stack[ts->cnt - 1];
struct call_path_root *cpr = ts->crp->cpr;
- struct symbol *sym = tse->cp->sym;
+ struct symbol *sym = tse->cp->ds.sym;
+ struct dso_symbol tds = dso_symbol__from_al(to_al);
struct symbol *tsym = to_al->sym;
struct call_path *cp;
@@ -1068,7 +1070,7 @@ static int thread_stack__x86_retpoline(struct thread_stack *ts,
* graph, since all the original branches are left unchanged.
*/
ts->cnt -= 1;
- sym = ts->stack[ts->cnt - 2].cp->sym;
+ sym = ts->stack[ts->cnt - 2].cp->ds.sym;
if (sym && sym == tsym && to_al->addr != tsym->start) {
/*
* Target is back to the middle of the symbol we came
@@ -1087,7 +1089,7 @@ static int thread_stack__x86_retpoline(struct thread_stack *ts,
return 0;
}
- cp = call_path__findnew(cpr, ts->stack[ts->cnt - 2].cp, tsym,
+ cp = call_path__findnew(cpr, ts->stack[ts->cnt - 2].cp, &tds,
sample->addr, ts->kernel_start);
if (!cp)
return -ENOMEM;
@@ -1147,6 +1149,7 @@ int thread_stack__process(struct thread *thread, struct comm *comm,
if (sample->flags & PERF_IP_FLAG_CALL) {
bool trace_end = sample->flags & PERF_IP_FLAG_TRACE_END;
+ struct dso_symbol tds = dso_symbol__from_al(to_al);
struct call_path_root *cpr = ts->crp->cpr;
struct call_path *cp;
u64 ret_addr;
@@ -1160,7 +1163,7 @@ int thread_stack__process(struct thread *thread, struct comm *comm,
return 0; /* Zero-length calls are excluded */
cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
- to_al->sym, sample->addr,
+ &tds, sample->addr,
ts->kernel_start);
err = thread_stack__push_cp(ts, ret_addr, sample->time, ref,
cp, false, trace_end);
@@ -1209,6 +1212,7 @@ int thread_stack__process(struct thread *thread, struct comm *comm,
} else if (sample->flags & PERF_IP_FLAG_BRANCH &&
from_al->sym != to_al->sym && to_al->sym &&
to_al->addr == to_al->sym->start) {
+ struct dso_symbol tds = dso_symbol__from_al(to_al);
struct call_path_root *cpr = ts->crp->cpr;
struct call_path *cp;
@@ -1219,7 +1223,7 @@ int thread_stack__process(struct thread *thread, struct comm *comm,
* when a ret pops the stack, all jmps must be popped off first.
*/
cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
- to_al->sym, sample->addr,
+ &tds, sample->addr,
ts->kernel_start);
err = thread_stack__push_cp(ts, 0, sample->time, ref, cp, false,
false);
--
2.56.1.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
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 ` Ian Rogers
2026-11-16 6:51 ` sashiko-bot
2026-11-16 6:34 ` [PATCH v5 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup Ian Rogers
` (6 subsequent siblings)
8 siblings, 1 reply; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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, enabling annotation added sizeof(struct annotation) to
symbol_conf.priv_size, bloating every loaded struct symbol in every DSO
even though only a small fraction of symbols are ever annotated.
Move struct annotation storage to an on-demand hashmap in
util/annotate.c keyed by struct symbol pointer, guarded by
annotations_lock, with an atomic nr_annotations count so unannotated
sessions skip lock and teardown overhead while symbol__annotated()
checks the hashmap under a read lock. Return NULL from
symbol__annotation() on allocation failure and check for NULL at
entry-point callers.
With annotation, TUI map browser indices, and db-export symbol IDs no
longer using negative-offset space ahead of struct symbol, remove
symbol_conf.priv_size and symbol__priv().
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/builtin-annotate.c | 5 +-
tools/perf/builtin-top.c | 21 ++++-
tools/perf/tests/builtin-test.c | 1 -
tools/perf/ui/browsers/annotate.c | 16 +++-
tools/perf/ui/browsers/hists.c | 23 ++++-
tools/perf/ui/gtk/annotate.c | 4 +
tools/perf/util/annotate.c | 152 +++++++++++++++++++++++++++++-
tools/perf/util/annotate.h | 7 +-
tools/perf/util/block-info.c | 2 +-
tools/perf/util/block-range.c | 11 ++-
tools/perf/util/sort.c | 9 +-
tools/perf/util/symbol.c | 27 ++----
tools/perf/util/symbol.h | 8 +-
tools/perf/util/symbol_conf.h | 1 -
14 files changed, 235 insertions(+), 52 deletions(-)
diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c
index 331adbdbd635..7cb7e03d9a21 100644
--- a/tools/perf/builtin-annotate.c
+++ b/tools/perf/builtin-annotate.c
@@ -441,8 +441,11 @@ static void hists__find_annotations(struct hists *hists,
goto find_next;
}
+ if (!symbol__annotated(he->ms.sym))
+ goto find_next;
+
notes = symbol__annotation(he->ms.sym);
- if (notes->src == NULL) {
+ if (!notes || notes->src == NULL) {
find_next:
if (key == K_LEFT || key == '<')
nd = rb_prev(nd);
diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c
index a3442d2d6edf..a272e6649077 100644
--- a/tools/perf/builtin-top.c
+++ b/tools/perf/builtin-top.c
@@ -140,6 +140,12 @@ static int perf_top__parse_source(struct perf_top *top, struct hist_entry *he)
}
notes = symbol__annotation(sym);
+ if (!notes) {
+ pr_err("Not enough memory for annotating '%s' symbol!\n",
+ sym->name);
+ sleep(1);
+ return err;
+ }
annotation__lock(notes);
if (!symbol__hists(sym, evlist__nr_entries(top->evlist))) {
@@ -213,13 +219,16 @@ static void perf_top__record_precise_ip(struct perf_top *top,
return;
notes = symbol__annotation(sym);
+ if (!notes) {
+ err = -ENOMEM;
+ } else {
+ if (!annotation__trylock(notes))
+ return;
- if (!annotation__trylock(notes))
- return;
-
- err = hist_entry__inc_addr_samples(he, sample, ip);
+ err = hist_entry__inc_addr_samples(he, sample, ip);
- annotation__unlock(notes);
+ annotation__unlock(notes);
+ }
if (unlikely(err)) {
/*
@@ -255,6 +264,8 @@ static void perf_top__show_details(struct perf_top *top)
symbol = he->ms.sym;
notes = symbol__annotation(symbol);
+ if (!notes)
+ return;
annotation__lock(notes);
diff --git a/tools/perf/tests/builtin-test.c b/tools/perf/tests/builtin-test.c
index 327483f96401..01c78ef20b97 100644
--- a/tools/perf/tests/builtin-test.c
+++ b/tools/perf/tests/builtin-test.c
@@ -2431,7 +2431,6 @@ int cmd_test(int argc, const char **argv)
test_timeout = 0;
}
- symbol_conf.priv_size = sizeof(int);
symbol_conf.try_vmlinux_path = true;
diff --git a/tools/perf/ui/browsers/annotate.c b/tools/perf/ui/browsers/annotate.c
index cf36b5347f72..f2a46eabe5a1 100644
--- a/tools/perf/ui/browsers/annotate.c
+++ b/tools/perf/ui/browsers/annotate.c
@@ -597,6 +597,11 @@ static bool annotate_browser__callq(struct annotate_browser *browser,
}
notes = symbol__annotation(dl->ops.target.sym);
+ if (!notes) {
+ ui__warning("Not enough memory for annotating '%s' symbol!\n",
+ dl->ops.target.sym->name);
+ return true;
+ }
annotation__lock(notes);
if (!symbol__hists(dl->ops.target.sym, evlist__nr_entries(evsel->evlist))) {
@@ -1174,7 +1179,7 @@ int __hist_entry__tui_annotate(struct hist_entry *he, struct map_symbol *ms,
struct hist_browser_timer *hbt, u64 al_addr)
{
struct symbol *sym = ms->sym;
- struct annotation *notes = symbol__annotation(sym);
+ struct annotation *notes;
struct annotate_browser browser = {
.b = {
.refresh = annotate_browser__refresh,
@@ -1190,7 +1195,7 @@ int __hist_entry__tui_annotate(struct hist_entry *he, struct map_symbol *ms,
};
struct dso *dso;
int ret = -1, err;
- int not_annotated = list_empty(¬es->src->source);
+ int not_annotated;
if (sym == NULL)
return -1;
@@ -1199,6 +1204,13 @@ int __hist_entry__tui_annotate(struct hist_entry *he, struct map_symbol *ms,
if (dso__annotate_warned(dso))
return -1;
+ notes = symbol__annotation(sym);
+ if (!notes) {
+ annotate_browser__symbol_annotate_error(&browser, -ENOMEM);
+ return -1;
+ }
+ not_annotated = !notes->src || list_empty(¬es->src->source);
+
if (not_annotated || !symbol__is_annotate2(sym)) {
err = symbol__annotate2(ms, evsel, &browser.arch);
if (err) {
diff --git a/tools/perf/ui/browsers/hists.c b/tools/perf/ui/browsers/hists.c
index 593e1fd5759d..6f9d9f7aec91 100644
--- a/tools/perf/ui/browsers/hists.c
+++ b/tools/perf/ui/browsers/hists.c
@@ -796,7 +796,10 @@ static void hist_browser__show_callchain_entry(struct hist_browser *browser,
{
int color, width;
char folded_sign = callchain_list__folded(chain);
- bool show_annotated = browser->show_dso && chain->ms.sym && symbol__annotation(chain->ms.sym)->src;
+ struct annotation *notes = (browser->show_dso && chain->ms.sym &&
+ symbol__annotated(chain->ms.sym)) ?
+ symbol__annotation(chain->ms.sym) : NULL;
+ bool show_annotated = notes && notes->src;
color = HE_COLORSET_NORMAL;
width = browser->b.width - (offset + 2);
@@ -2486,8 +2489,11 @@ do_annotate(struct hist_browser *browser, struct popup_action *act)
perf_env__lookup_objdump(browser->env, &annotate_opts.objdump_path))
return 0;
+ if (!symbol__annotated(act->ms.sym))
+ return 0;
+
notes = symbol__annotation(act->ms.sym);
- if (!notes->src)
+ if (!notes || !notes->src)
return 0;
if (browser->block_evsel)
@@ -2537,6 +2543,7 @@ add_annotate_opt(struct popup_action *act, char **optstr,
struct map_symbol *ms,
u64 addr)
{
+ struct annotation *notes;
struct dso *dso;
if (!ms->map || (dso = map__dso(ms->map)) == NULL || dso__annotate_warned(dso))
@@ -2545,7 +2552,11 @@ add_annotate_opt(struct popup_action *act, char **optstr,
if (!ms->sym)
ms->sym = symbol__new_unresolved(addr, ms->map);
- if (ms->sym == NULL || symbol__annotation(ms->sym)->src == NULL)
+ if (ms->sym == NULL || !symbol__annotated(ms->sym))
+ return 0;
+
+ notes = symbol__annotation(ms->sym);
+ if (!notes || notes->src == NULL)
return 0;
if (asprintf(optstr, "Annotate %s", ms->sym->name) < 0)
@@ -3204,7 +3215,11 @@ static int evsel__hists_browse(struct evsel *evsel, int nr_events, const char *h
do_annotate(browser, &hotkey_act);
map_symbol__exit(&hotkey_act.ms);
} else {
- if (symbol__annotation(browser->selection->sym)->src == NULL) {
+ struct annotation *notes;
+
+ notes = symbol__annotated(browser->selection->sym) ?
+ symbol__annotation(browser->selection->sym) : NULL;
+ if (!notes || notes->src == NULL) {
ui_browser__warning(&browser->b, delay_secs * 2,
"No samples for the \"%s\" symbol.\n\n"
"Probably appeared just in a callchain",
diff --git a/tools/perf/ui/gtk/annotate.c b/tools/perf/ui/gtk/annotate.c
index 094dfa045b77..13a175c1b6e7 100644
--- a/tools/perf/ui/gtk/annotate.c
+++ b/tools/perf/ui/gtk/annotate.c
@@ -44,6 +44,8 @@ static int perf_gtk__get_percent(char *buf, size_t size, struct symbol *sym,
return 0;
notes = symbol__annotation(sym);
+ if (!notes || !notes->src)
+ return 0;
symhist = annotation__histogram(notes, evsel);
entry = annotated_source__hist_entry(notes->src, evsel, dl->al.offset);
if (entry)
@@ -116,6 +118,8 @@ static int perf_gtk__annotate_symbol(GtkWidget *window, struct map_symbol *ms,
char s[512];
notes = symbol__annotation(sym);
+ if (!notes || !notes->src)
+ return 0;
for (i = 0; i < MAX_ANN_COLS; i++) {
col_types[i] = G_TYPE_STRING;
diff --git a/tools/perf/util/annotate.c b/tools/perf/util/annotate.c
index 86a4beec6528..59d20bd2d861 100644
--- a/tools/perf/util/annotate.c
+++ b/tools/perf/util/annotate.c
@@ -8,6 +8,10 @@
#include <errno.h>
#include <inttypes.h>
+#include <pthread.h>
+#include <stdatomic.h>
+#include <stdbool.h>
+#include <stddef.h>
#include <stdlib.h>
#include "util.h" // hex_width()
#include "ui/ui.h"
@@ -35,6 +39,7 @@
#include "string2.h"
#include "dwarf-regs.h"
#include "util/event.h"
+#include "util/rwsem.h"
#include "util/sharded_mutex.h"
#include "arch/common.h"
#include "namespaces.h"
@@ -118,6 +123,7 @@ static __maybe_unused void annotated_source__delete(struct annotated_source *src
if (src == NULL)
return;
+ annotated_source__purge(src);
if (src->samples) {
hashmap__for_each_entry(src->samples, cur, bkt)
zfree(&cur->pvalue);
@@ -156,9 +162,141 @@ annotated_source__hist_entry(struct annotated_source *src, const struct evsel *e
return entry;
}
+/*
+ * Map from struct symbol pointer to struct annotation. Allocated on demand so
+ * unannotated symbols do not pay the memory cost of struct annotation.
+ */
+static struct rw_semaphore _annotations_lock;
+static struct hashmap *annotations GUARDED_BY(_annotations_lock);
+static atomic_size_t nr_annotations;
+
+static void annotations_lock_init(void)
+{
+ init_rwsem(&_annotations_lock);
+}
+
+static struct rw_semaphore *annotations_lock(void) LOCK_RETURNED(_annotations_lock)
+{
+ static pthread_once_t annotations_lock_once = PTHREAD_ONCE_INIT;
+
+ pthread_once(&annotations_lock_once, annotations_lock_init);
+ return &_annotations_lock;
+}
+
+static size_t sym_ptr_hash(long key, void *ctx __maybe_unused)
+{
+ return (size_t)key;
+}
+
+static bool sym_ptr_equal(long key1, long key2, void *ctx __maybe_unused)
+{
+ return key1 == key2;
+}
+
+bool symbol__annotated(const struct symbol *sym)
+{
+ bool found;
+
+ if (!sym || atomic_load_explicit(&nr_annotations, memory_order_acquire) == 0)
+ return false;
+
+ down_read(annotations_lock());
+ found = annotations && hashmap__find(annotations, (long)sym, NULL);
+ up_read(annotations_lock());
+ return found;
+}
+
+struct annotation *symbol__annotation(struct symbol *sym)
+{
+ struct annotation *notes = NULL;
+ long val = 0;
+
+ if (!sym)
+ return NULL;
+
+ /* Fast path: look up existing annotation under read lock. */
+ if (atomic_load_explicit(&nr_annotations, memory_order_acquire) > 0) {
+ down_read(annotations_lock());
+ if (annotations && hashmap__find(annotations, (long)sym, &val))
+ notes = (struct annotation *)val;
+ up_read(annotations_lock());
+ if (notes)
+ return notes;
+ }
+
+ down_write(annotations_lock());
+ if (!annotations) {
+ annotations = hashmap__new(sym_ptr_hash, sym_ptr_equal, NULL);
+ if (IS_ERR(annotations)) {
+ annotations = NULL;
+ up_write(annotations_lock());
+ return NULL;
+ }
+ } else if (hashmap__find(annotations, (long)sym, &val)) {
+ notes = (struct annotation *)val;
+ up_write(annotations_lock());
+ return notes;
+ }
+
+ notes = zalloc(sizeof(*notes));
+ if (!notes)
+ goto err_free_hashmap;
+
+ annotation__init(notes);
+ if (hashmap__add(annotations, (long)sym, notes) < 0) {
+ annotation__exit(notes);
+ free(notes);
+ goto err_free_hashmap;
+ }
+ atomic_fetch_add_explicit(&nr_annotations, 1, memory_order_release);
+ up_write(annotations_lock());
+ return notes;
+
+err_free_hashmap:
+ if (hashmap__size(annotations) == 0) {
+ hashmap__free(annotations);
+ annotations = NULL;
+ }
+ up_write(annotations_lock());
+ return NULL;
+}
+
+void symbol__annotation_delete(struct symbol *sym)
+{
+ struct annotation *notes = NULL;
+ long val = 0;
+
+ /* Unannotated symbols avoid taking annotations_lock for write on teardown. */
+ if (!symbol__annotated(sym))
+ return;
+
+ down_write(annotations_lock());
+ if (annotations && hashmap__delete(annotations, (long)sym, NULL, &val)) {
+ notes = (struct annotation *)val;
+ atomic_fetch_sub_explicit(&nr_annotations, 1, memory_order_release);
+ if (hashmap__size(annotations) == 0) {
+ hashmap__free(annotations);
+ annotations = NULL;
+ }
+ }
+ up_write(annotations_lock());
+
+ if (notes) {
+ annotation__exit(notes);
+ free(notes);
+ }
+}
+
void symbol__annotate_zero_histograms(struct symbol *sym)
{
- struct annotation *notes = symbol__annotation(sym);
+ struct annotation *notes;
+
+ if (!symbol__annotated(sym))
+ return;
+
+ notes = symbol__annotation(sym);
+ if (!notes)
+ return;
annotation__lock(notes);
if (notes->src != NULL) {
@@ -334,6 +472,9 @@ struct annotated_source *symbol__hists(struct symbol *sym, int nr_hists)
{
struct annotation *notes = symbol__annotation(sym);
+ if (!notes)
+ return NULL;
+
if (notes->src == NULL) {
notes->src = annotated_source__new();
if (notes->src == NULL)
@@ -1074,6 +1215,9 @@ void symbol__calc_percent(struct symbol *sym, struct evsel *evsel)
{
struct annotation *notes = symbol__annotation(sym);
+ if (!notes || !notes->src)
+ return;
+
annotation__calc_percent(notes, evsel, symbol__size(sym));
}
@@ -1139,6 +1283,9 @@ int symbol__annotate(struct map_symbol *ms, struct evsel *evsel,
if (parch)
*parch = arch;
+ if (!notes)
+ return -ENOMEM;
+
if (notes->src && !list_empty(¬es->src->source))
return 0;
@@ -2340,6 +2487,9 @@ int symbol__annotate2(struct map_symbol *ms, struct evsel *evsel,
size_t size = symbol__size(sym);
int err;
+ if (!notes)
+ return -ENOMEM;
+
err = symbol__annotate(ms, evsel, parch);
if (err)
return err;
diff --git a/tools/perf/util/annotate.h b/tools/perf/util/annotate.h
index 1b47c1156b9a..bc2237609d6e 100644
--- a/tools/perf/util/annotate.h
+++ b/tools/perf/util/annotate.h
@@ -449,10 +449,9 @@ static inline struct sym_hist *annotation__histogram(struct annotation *notes,
struct sym_hist_entry *
annotated_source__hist_entry(struct annotated_source *src, const struct evsel *evsel, u64 offset);
-static inline struct annotation *symbol__annotation(struct symbol *sym)
-{
- return (void *)sym - symbol_conf.priv_size;
-}
+bool symbol__annotated(const struct symbol *sym);
+struct annotation *symbol__annotation(struct symbol *sym);
+void symbol__annotation_delete(struct symbol *sym);
int addr_map_symbol__inc_samples(struct addr_map_symbol *ams, struct perf_sample *sample);
diff --git a/tools/perf/util/block-info.c b/tools/perf/util/block-info.c
index 1135e54f4c7f..572cfb569849 100644
--- a/tools/perf/util/block-info.c
+++ b/tools/perf/util/block-info.c
@@ -134,7 +134,7 @@ int block_info__process_sym(struct hist_entry *he, struct block_hist *bh,
static struct addr_location al;
u64 cycles = 0;
- if (!he->ms.map || !he->ms.sym)
+ if (!he->ms.map || !he->ms.sym || !symbol__annotated(he->ms.sym))
return 0;
memset(&al, 0, sizeof(al));
diff --git a/tools/perf/util/block-range.c b/tools/perf/util/block-range.c
index 280d695c6c58..9c3d70ffcc29 100644
--- a/tools/perf/util/block-range.c
+++ b/tools/perf/util/block-range.c
@@ -1,6 +1,7 @@
// SPDX-License-Identifier: GPL-2.0
#include "block-range.h"
#include "annotate.h"
+#include "symbol.h"
#include <assert.h>
#include <stdlib.h>
@@ -323,10 +324,16 @@ double block_range__coverage(struct block_range *br)
}
sym = br->sym;
- if (!sym)
+ if (!sym || !symbol__annotated(sym))
return -1;
- branch = symbol__annotation(sym)->branch;
+ branch = NULL;
+ {
+ struct annotation *notes = symbol__annotation(sym);
+
+ if (notes)
+ branch = notes->branch;
+ }
if (!branch)
return -1;
diff --git a/tools/perf/util/sort.c b/tools/perf/util/sort.c
index f4c50f191141..57d7877782d1 100644
--- a/tools/perf/util/sort.c
+++ b/tools/perf/util/sort.c
@@ -793,14 +793,19 @@ static int hist_entry__sym_ipc_snprintf(struct hist_entry *he, char *bf,
{
struct symbol *sym = he->ms.sym;
- struct annotated_branch *branch;
+ struct annotated_branch *branch = NULL;
double ipc = 0.0, coverage = 0.0;
char tmp[64];
if (!sym)
return repsep_snprintf(bf, size, "%-*s", width, "-");
- branch = symbol__annotation(sym)->branch;
+ if (symbol__annotated(sym)) {
+ struct annotation *notes = symbol__annotation(sym);
+
+ if (notes)
+ branch = notes->branch;
+ }
if (branch && branch->hit_cycles)
ipc = branch->hit_insn / ((double)branch->hit_cycles);
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index dc70bbe8514f..a1ac1cd1d2e7 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -319,19 +319,11 @@ void symbols__fixup_end(struct rb_root_cached *symbols, bool is_kallsyms)
struct symbol *symbol__new(u64 start, u64 len, u8 binding, u8 type, const char *name)
{
size_t namelen = strlen(name) + 1;
- struct symbol *sym = calloc(1, (symbol_conf.priv_size +
- sizeof(*sym) + namelen));
+ struct symbol *sym = calloc(1, sizeof(*sym) + namelen);
+
if (sym == NULL)
return NULL;
- if (symbol_conf.priv_size) {
- if (symbol_conf.init_annotation) {
- struct annotation *notes = (void *)sym;
- annotation__init(notes);
- }
- sym = ((void *)sym) + symbol_conf.priv_size;
- }
-
sym->start = start;
sym->end = len ? start + len : start;
atomic_init(&sym->flags, (type << SYMBOL_FLAG_TYPE_SHIFT) |
@@ -347,14 +339,10 @@ struct symbol *symbol__new(u64 start, u64 len, u8 binding, u8 type, const char *
void symbol__delete(struct symbol *sym)
{
- if (symbol_conf.priv_size) {
- if (symbol_conf.init_annotation) {
- struct annotation *notes = symbol__annotation(sym);
-
- annotation__exit(notes);
- }
- }
- free(((void *)sym) - symbol_conf.priv_size);
+ if (!sym)
+ return;
+ symbol__annotation_delete(sym);
+ free(sym);
}
void symbol__set_ignore(struct symbol *sym, bool ignore)
@@ -2479,7 +2467,6 @@ int symbol__annotation_init(void)
return -1;
}
- symbol_conf.priv_size += sizeof(struct annotation);
symbol_conf.init_annotation = true;
return 0;
}
@@ -2522,8 +2509,6 @@ int symbol__init(struct perf_env *env)
if (symbol_conf.initialized)
return 0;
- symbol_conf.priv_size = PERF_ALIGN(symbol_conf.priv_size, sizeof(u64));
-
symbol__elf_init();
if (symbol_conf.try_vmlinux_path && vmlinux_path__init(env) < 0)
diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h
index 6347bd218ad5..a6a2ab200f98 100644
--- a/tools/perf/util/symbol.h
+++ b/tools/perf/util/symbol.h
@@ -79,8 +79,7 @@ enum symbol_idle_kind {
#define SYMBOL_FLAG_ANNOTATE2 (1 << 12)
#define SYMBOL_FLAG_IFUNC_ALIAS (1 << 13)
/**
- * A symtab entry. When allocated this may be preceded by an annotation (see
- * symbol__annotation) and/or a browser_index (see symbol__browser_index).
+ * A symtab entry.
*/
struct symbol {
struct rb_node rb_node;
@@ -174,11 +173,6 @@ static inline int __symbol__join_symfs(char *bf, size_t size, const char *path)
extern int vmlinux_path__nr_entries;
extern char **vmlinux_path;
-static inline void *symbol__priv(struct symbol *sym)
-{
- return ((void *)sym) - symbol_conf.priv_size;
-}
-
struct ref_reloc_sym {
const char *name;
u64 addr;
diff --git a/tools/perf/util/symbol_conf.h b/tools/perf/util/symbol_conf.h
index 37d35f42dcc1..aaa7148c3ac1 100644
--- a/tools/perf/util/symbol_conf.h
+++ b/tools/perf/util/symbol_conf.h
@@ -42,7 +42,6 @@ struct symbol_conf {
/* Was hybrid_merge given on the command line rather than in a config file? */
bool hybrid_merge_set;
bool nanosecs;
- unsigned short priv_size;
bool try_vmlinux_path,
init_annotation,
force,
--
2.56.1.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
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 ` Ian Rogers
2026-11-16 6:48 ` sashiko-bot
2026-11-16 6:34 ` [PATCH v5 4/9] perf maps: Optimize tail insertion and small-append sorting Ian Rogers
` (5 subsequent siblings)
8 siblings, 1 reply; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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
Profiling dso__load_sym_internal() on large binaries showed significant
time spent in repeated libelf section and program header lookups
(elf_section_by_idx() and elf_read_program_header()) for each symbol and
in resolving elf_sym__name() before filtering out non-symbol and
non-allocated entries.
Speed up ELF symbol table loading in dso__load_sym_internal():
- Pre-load PT_LOAD program headers into struct elf_phdr_cache and cache
per-section metadata in a 64-entry direct-mapped table in
dso__load_sym_internal() to avoid repeated libelf section and program
header lookups during symbol iteration.
- Defer elf_sym__name() lookup until after non-allocated and non-symbol
entries have been filtered out.
Using 'perf bench internals symbols':
Before (perf binary):
Average DSO load + sort: 5.808 msec (+- 0.047 msec)
After (perf binary, -8.3%):
Average DSO load + sort: 5.324 msec (+- 0.045 msec)
Before (perf binary, --no-demangle):
Average DSO load + sort: 3.948 msec (+- 0.064 msec)
After (perf binary, --no-demangle, -13.7%):
Average DSO load + sort: 3.408 msec (+- 0.034 msec)
Before (libLLVM.so.21.1, --no-demangle):
Average DSO load + sort: 22.433 msec (+- 0.260 msec)
After (libLLVM.so.21.1, --no-demangle, -14.8%):
Average DSO load + sort: 19.122 msec (+- 0.226 msec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/symbol-elf.c | 239 ++++++++++++++++++++++++++++-------
1 file changed, 196 insertions(+), 43 deletions(-)
diff --git a/tools/perf/util/symbol-elf.c b/tools/perf/util/symbol-elf.c
index 98b6d7c73d23..2b7f9e30916d 100644
--- a/tools/perf/util/symbol-elf.c
+++ b/tools/perf/util/symbol-elf.c
@@ -267,6 +267,116 @@ static int elf_read_program_header(Elf *elf, u64 vaddr, GElf_Phdr *phdr)
return -1;
}
+struct elf_phdr_range {
+ u64 vaddr;
+ u64 end;
+ GElf_Phdr phdr;
+};
+
+struct elf_phdr_cache {
+ struct elf_phdr_range inline_ranges[16];
+ struct elf_phdr_range *ranges;
+ size_t nr_ranges;
+ size_t last_idx;
+};
+
+static void elf_phdr_cache__init(struct elf_phdr_cache *cache, Elf *elf)
+{
+ size_t i, phdrnum = 0, cnt = 0;
+
+ cache->ranges = cache->inline_ranges;
+ cache->nr_ranges = 0;
+ cache->last_idx = 0;
+
+ if (!elf || elf_getphdrnum(elf, &phdrnum) || phdrnum == 0)
+ return;
+
+ if (phdrnum > ARRAY_SIZE(cache->inline_ranges)) {
+ cache->ranges = calloc(phdrnum, sizeof(*cache->ranges));
+ if (!cache->ranges) {
+ cache->ranges = cache->inline_ranges;
+ phdrnum = ARRAY_SIZE(cache->inline_ranges);
+ }
+ }
+
+ for (i = 0; i < phdrnum; i++) {
+ GElf_Phdr phdr;
+ u64 sz;
+
+ if (gelf_getphdr(elf, i, &phdr) == NULL)
+ break;
+ if (phdr.p_type != PT_LOAD)
+ continue;
+ sz = max(phdr.p_memsz, phdr.p_filesz);
+ if (!sz)
+ continue;
+ cache->ranges[cnt].vaddr = phdr.p_vaddr;
+ cache->ranges[cnt].end = phdr.p_vaddr + sz;
+ cache->ranges[cnt].phdr = phdr;
+ cnt++;
+ }
+ cache->nr_ranges = cnt;
+}
+
+static void elf_phdr_cache__exit(struct elf_phdr_cache *cache)
+{
+ if (cache->ranges && cache->ranges != cache->inline_ranges)
+ free(cache->ranges);
+}
+
+static const struct elf_phdr_range *
+elf_phdr_cache__find(struct elf_phdr_cache *cache, u64 vaddr)
+{
+ if (cache->nr_ranges == 0)
+ return NULL;
+
+ if (cache->last_idx < cache->nr_ranges) {
+ const struct elf_phdr_range *r = &cache->ranges[cache->last_idx];
+
+ if (vaddr >= r->vaddr && vaddr < r->end)
+ return r;
+ }
+ for (size_t i = 0; i < cache->nr_ranges; i++) {
+ const struct elf_phdr_range *r = &cache->ranges[i];
+
+ if (vaddr >= r->vaddr && vaddr < r->end) {
+ cache->last_idx = i;
+ return r;
+ }
+ }
+ return NULL;
+}
+
+#define ELF_SEC_CACHE_SIZE 64
+
+struct elf_sec_cache_entry {
+ uint32_t shndx;
+ bool valid;
+ bool is_alloc;
+ bool is_label_sec;
+ bool has_phdr;
+ u64 phdr_vaddr;
+ u64 phdr_end;
+ const char *section_name;
+ GElf_Shdr shdr;
+ GElf_Phdr phdr;
+};
+
+static inline const GElf_Phdr *
+elf_sec_cache__phdr(const struct elf_sec_cache_entry *sce,
+ struct elf_phdr_cache *phdr_cache,
+ u64 vaddr)
+{
+ const struct elf_phdr_range *pr;
+
+ if (sce->has_phdr && vaddr >= sce->phdr_vaddr && vaddr < sce->phdr_end)
+ return &sce->phdr;
+ pr = elf_phdr_cache__find(phdr_cache, vaddr);
+ if (!pr)
+ return NULL;
+ return &pr->phdr;
+}
+
struct rel_info {
u32 nr_entries;
u32 *sorted;
@@ -1538,6 +1648,8 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
int nr = 0;
bool remap_kernel = false, adjust_kernel_syms = false;
u64 max_text_sh_offset = 0;
+ struct elf_phdr_cache phdr_cache = {};
+ struct elf_sec_cache_entry sec_cache[ELF_SEC_CACHE_SIZE];
if (kmap && !kmaps)
return -1;
@@ -1629,14 +1741,18 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
if (kmodule && adjust_kernel_syms)
max_text_sh_offset = max_text_section(runtime_ss->elf, &runtime_ss->ehdr);
+ elf_phdr_cache__init(&phdr_cache, runtime_ss->elf);
+ memset(sec_cache, 0, sizeof(sec_cache));
+
curr_dso = dso__get(dso);
elf_symtab__for_each_symbol(syms, nr_syms, idx, sym) {
struct symbol *f;
- const char *elf_name = elf_sym__name(&sym, symstrs);
+ const char *elf_name = NULL;
char *demangled = NULL;
int is_label = elf_sym__is_label(&sym);
const char *section_name;
bool used_opd = false;
+ struct elf_sec_cache_entry *sce;
if (!is_label && !elf_sym__filter(&sym))
continue;
@@ -1647,6 +1763,7 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
* output:
*/
if (ehdr.e_machine == EM_ARM || ehdr.e_machine == EM_AARCH64) {
+ elf_name = elf_sym__name(&sym, symstrs);
if (elf_name[0] == '$' && strchr("adtx", elf_name[1])
&& (elf_name[2] == '\0' || elf_name[2] == '.'))
continue;
@@ -1654,13 +1771,19 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
/* Reject RISCV ELF "mapping symbols" */
if (ehdr.e_machine == EM_RISCV) {
+ if (!elf_name)
+ elf_name = elf_sym__name(&sym, symstrs);
if (elf_name[0] == '$' && strchr("dx", elf_name[1]))
continue;
}
/* Reject kernel mapping symbols for kernel DSOs only */
- if (dso__kernel(dso) && is_ignored_kernel_symbol(elf_name))
- continue;
+ if (dso__kernel(dso)) {
+ if (!elf_name)
+ elf_name = elf_sym__name(&sym, symstrs);
+ if (is_ignored_kernel_symbol(elf_name))
+ continue;
+ }
if (runtime_ss->opdsec && sym.st_shndx == runtime_ss->opdidx) {
u32 offset = sym.st_value - syms_ss->opdshdr.sh_addr;
@@ -1683,16 +1806,56 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
if (sym.st_shndx == SHN_ABS)
continue;
- sec = elf_getscn(syms_ss->elf, sym.st_shndx);
- if (!sec) {
- if (dynsym && ehdr.e_shnum &&
- sym.st_shndx < SHN_LORESERVE &&
- sym.st_shndx >= ehdr.e_shnum)
- continue;
- goto out_elf_end;
- }
+ sce = &sec_cache[sym.st_shndx & (ELF_SEC_CACHE_SIZE - 1)];
+ if (!sce->valid || sce->shndx != sym.st_shndx) {
+ const struct elf_phdr_range *pr;
- gelf_getshdr(sec, &shdr);
+ sec = elf_getscn(syms_ss->elf, sym.st_shndx);
+ if (!sec) {
+ if (dynsym && ehdr.e_shnum &&
+ sym.st_shndx < SHN_LORESERVE &&
+ sym.st_shndx >= ehdr.e_shnum)
+ continue;
+ goto out_elf_end;
+ }
+
+ gelf_getshdr(sec, &shdr);
+ secstrs = secstrs_sym;
+
+ /*
+ * We have to fallback to runtime when syms' section
+ * header has NOBITS set. NOBITS results in file offset
+ * (sh_offset) not being incremented. So sh_offset used
+ * below has different values for syms (invalid) and
+ * runtime (valid).
+ */
+ if (shdr.sh_type == SHT_NOBITS && (shdr.sh_flags & SHF_ALLOC)) {
+ sec = elf_getscn(runtime_ss->elf, sym.st_shndx);
+ if (!sec)
+ goto out_elf_end;
+
+ gelf_getshdr(sec, &shdr);
+ secstrs = secstrs_run;
+ }
+
+ sce->shndx = sym.st_shndx;
+ sce->valid = true;
+ sce->is_alloc = (shdr.sh_flags & SHF_ALLOC) != 0;
+ if (sce->is_alloc) {
+ sce->shdr = shdr;
+ sce->section_name = elf_sec__name(&shdr, secstrs);
+ sce->is_label_sec = elf_sec__filter(&shdr, secstrs) != 0;
+ pr = elf_phdr_cache__find(&phdr_cache, shdr.sh_addr);
+ if (pr) {
+ sce->has_phdr = true;
+ sce->phdr_vaddr = pr->vaddr;
+ sce->phdr_end = pr->end;
+ sce->phdr = pr->phdr;
+ } else {
+ sce->has_phdr = false;
+ }
+ }
+ }
/*
* If the attribute bit SHF_ALLOC is not set, the section
@@ -1702,30 +1865,13 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
* the section aren't loaded to memory during process execution,
* so skip them.
*/
- if (!(shdr.sh_flags & SHF_ALLOC))
+ if (!sce->is_alloc)
continue;
- secstrs = secstrs_sym;
-
- /*
- * We have to fallback to runtime when syms' section header has
- * NOBITS set. NOBITS results in file offset (sh_offset) not
- * being incremented. So sh_offset used below has different
- * values for syms (invalid) and runtime (valid).
- */
- if (shdr.sh_type == SHT_NOBITS) {
- sec = elf_getscn(runtime_ss->elf, sym.st_shndx);
- if (!sec)
- goto out_elf_end;
-
- gelf_getshdr(sec, &shdr);
- secstrs = secstrs_run;
- }
-
- if (is_label && !elf_sec__filter(&shdr, secstrs))
+ if (is_label && !sce->is_label_sec)
continue;
- section_name = elf_sec__name(&shdr, secstrs);
+ section_name = sce->section_name;
/* On ARM, symbols for thumb functions have 1 added to
* the symbol address as a flag - remove it */
@@ -1735,7 +1881,7 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
--sym.st_value;
if (dso__kernel(dso)) {
- if (dso__process_kernel_symbol(dso, map, &sym, &shdr,
+ if (dso__process_kernel_symbol(dso, map, &sym, &sce->shdr,
kmaps, kmap, &curr_dso,
section_name,
adjust_kernel_syms,
@@ -1745,17 +1891,20 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
goto out_elf_end;
} else if ((used_opd && runtime_ss->adjust_symbols) ||
(!used_opd && syms_ss->adjust_symbols)) {
- GElf_Phdr phdr;
+ const GElf_Phdr *phdr;
- if (elf_read_program_header(runtime_ss->elf,
- (u64)sym.st_value, &phdr)) {
+ phdr = elf_sec_cache__phdr(sce, &phdr_cache,
+ (u64)sym.st_value);
+ if (!phdr) {
pr_debug4("%s: failed to find program header for "
"symbol: %s st_value: %#" PRIx64 "\n",
- __func__, elf_name, (u64)sym.st_value);
+ __func__, elf_sym__name(&sym, symstrs),
+ (u64)sym.st_value);
pr_debug4("%s: adjusting symbol: st_value: %#" PRIx64 " "
"sh_addr: %#" PRIx64 " sh_offset: %#" PRIx64 "\n",
- __func__, (u64)sym.st_value, (u64)shdr.sh_addr,
- (u64)shdr.sh_offset);
+ __func__, (u64)sym.st_value,
+ (u64)sce->shdr.sh_addr,
+ (u64)sce->shdr.sh_offset);
/*
* Fail to find program header, let's rollback
* to use shdr.sh_addr and shdr.sh_offset to
@@ -1764,16 +1913,18 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
* still need to handle java JIT symbols in this
* case.
*/
- sym.st_value -= shdr.sh_addr - shdr.sh_offset;
+ sym.st_value -= sce->shdr.sh_addr - sce->shdr.sh_offset;
} else {
pr_debug4("%s: adjusting symbol: st_value: %#" PRIx64 " "
"p_vaddr: %#" PRIx64 " p_offset: %#" PRIx64 "\n",
- __func__, (u64)sym.st_value, (u64)phdr.p_vaddr,
- (u64)phdr.p_offset);
- sym.st_value -= phdr.p_vaddr - phdr.p_offset;
+ __func__, (u64)sym.st_value, (u64)phdr->p_vaddr,
+ (u64)phdr->p_offset);
+ sym.st_value -= phdr->p_vaddr - phdr->p_offset;
}
}
+ if (!elf_name)
+ elf_name = elf_sym__name(&sym, symstrs);
demangled = dso__demangle_sym(dso, kmodule, elf_name);
if (demangled != NULL)
elf_name = demangled;
@@ -1791,9 +1942,11 @@ dso__load_sym_internal(struct dso *dso, struct map *map, struct symsrc *syms_ss,
nr++;
}
dso__put(curr_dso);
+ elf_phdr_cache__exit(&phdr_cache);
return nr;
out_elf_end:
dso__put(curr_dso);
+ elf_phdr_cache__exit(&phdr_cache);
return -1;
}
--
2.56.1.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 4/9] perf maps: Optimize tail insertion and small-append sorting
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (2 preceding siblings ...)
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 ` Ian Rogers
2026-11-16 6:34 ` [PATCH v5 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
` (4 subsequent siblings)
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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).
Additionally, track the sorted prefix lengths (nr_addr_sorted and
nr_name_sorted) in struct maps:
- In __maps__sort_by_address() and maps__sort_by_name(), when the
unsorted tail is small (k <= 8) or the total map count is small
(n <= 64), binary-insert the newly appended maps into the sorted
prefix instead of re-running qsort() over the entire array. This
avoids O(N^2 log N) re-sorting when maps__find_by_name() is called
repeatedly between single-map maps__insert() calls in
dso__process_kernel_symbol() and dso__split_kallsyms().
- In maps__by_address_index() and maps__by_name_index(), binary-search
the known-sorted prefix before scanning only the unsorted tail.
- Add a unit test in tools/perf/tests/maps.c covering the tail
fast-path and incremental binary-insertion sort.
Using 'perf bench internals maps':
Before:
Average ascending insert + lookup: 63.370 usec (+- 0.476 usec)
Average append + lookup: 7477.450 usec (+- 20.829 usec)
After (-6.9% ascending, -98.7% append):
Average ascending insert + lookup: 58.970 usec (+- 0.609 usec)
Average append + lookup: 96.670 usec (+- 1.353 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/tests/maps.c | 67 ++++++++++
tools/perf/util/maps.c | 276 +++++++++++++++++++++++++++++++++-------
2 files changed, 294 insertions(+), 49 deletions(-)
diff --git a/tools/perf/tests/maps.c b/tools/perf/tests/maps.c
index ff6d25f9c043..04ab425f4a87 100644
--- a/tools/perf/tests/maps.c
+++ b/tools/perf/tests/maps.c
@@ -1,6 +1,7 @@
// SPDX-License-Identifier: GPL-2.0
#include <inttypes.h>
#include <unistd.h>
+#include <internal/rc_check.h>
#include <linux/compiler.h>
#include <linux/kernel.h>
#include "debug.h"
@@ -253,9 +254,75 @@ static int test__maps__fixup_overlap_and_insert(struct test_suite *t __maybe_unu
return TEST_OK;
}
+static int test__maps__incremental_sort(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_def out_of_order = { "map_b", 3000, 4000 };
+ struct map *map, *found;
+ struct perf_env host_env;
+ struct machine *machine;
+ struct maps *maps;
+
+ 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);
+ }
+
+ /* Populate maps_by_name and verify lookup. */
+ found = maps__find_by_name(maps, "map_a");
+ TEST_ASSERT_VAL("failed to find map_a by name", found && map__start(found) == 2000);
+ map__zput(found);
+
+ /* Append out-of-order map via maps__insert and verify binary-insertion sort. */
+ map = dso__new_map(out_of_order.name);
+ TEST_ASSERT_VAL("failed to create map_b", map);
+ map__set_start(map, out_of_order.start);
+ map__set_end(map, out_of_order.end);
+ TEST_ASSERT_VAL("failed to insert map_b", maps__insert(maps, map) == 0);
+
+ found = maps__find(maps, 3500);
+ TEST_ASSERT_VAL("failed to find map_b by address", RC_CHK_EQUAL(found, map));
+ map__zput(found);
+
+ found = maps__find_by_name(maps, "map_b");
+ TEST_ASSERT_VAL("failed to find map_b by name", RC_CHK_EQUAL(found, map));
+ map__zput(found);
+
+ maps__remove(maps, map);
+ map__zput(map);
+
+ found = maps__find_by_name(maps, "map_d");
+ TEST_ASSERT_VAL("failed to find map_d after removal", found && map__start(found) == 4000);
+ 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 incremental sort and tail insert", maps__incremental_sort),
{ .name = NULL, }
};
diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c
index 675fe0223faa..b420c2f2b72a 100644
--- a/tools/perf/util/maps.c
+++ b/tools/perf/util/maps.c
@@ -1,6 +1,7 @@
// SPDX-License-Identifier: GPL-2.0
#include <errno.h>
#include <stdlib.h>
+#include <linux/kernel.h>
#include <linux/zalloc.h>
#include "debug.h"
#include "dso.h"
@@ -56,6 +57,16 @@ DECLARE_RC_STRUCT(maps) {
* maps_by_name.
*/
unsigned int nr_maps_allocated;
+ /**
+ * @nr_addr_sorted: number of leading entries in
+ * maps_by_address that are known to be sorted.
+ */
+ unsigned int nr_addr_sorted;
+ /**
+ * @nr_name_sorted: number of leading entries in maps_by_name
+ * that are known to be sorted.
+ */
+ unsigned int nr_name_sorted;
/**
* @last_search_by_name_idx: cache of last found by name entry's index
* as frequent searches for the same dso name are common.
@@ -72,8 +83,17 @@ DECLARE_RC_STRUCT(maps) {
static void check_invariants(const struct maps *maps __maybe_unused)
{
#ifndef NDEBUG
- assert(RC_CHK_ACCESS(maps)->nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated);
- for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
+ unsigned int nr_maps = RC_CHK_ACCESS(maps)->nr_maps;
+ unsigned int nr_addr_sorted = RC_CHK_ACCESS(maps)->nr_addr_sorted;
+ unsigned int nr_name_sorted = RC_CHK_ACCESS(maps)->nr_name_sorted;
+
+ assert(nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated);
+ assert(nr_addr_sorted <= nr_maps);
+ assert(!RC_CHK_ACCESS(maps)->maps_by_address_sorted || nr_addr_sorted == nr_maps);
+ assert(nr_name_sorted <= nr_maps);
+ assert(!RC_CHK_ACCESS(maps)->maps_by_name_sorted || nr_name_sorted == nr_maps);
+
+ for (unsigned int i = 0; i < nr_maps; i++) {
struct map *map = RC_CHK_ACCESS(maps)->maps_by_address[i];
/* Check map is well-formed. */
@@ -84,28 +104,25 @@ static void check_invariants(const struct maps *maps __maybe_unused)
if (map__dso(map) && dso__kernel(map__dso(map)))
assert(RC_CHK_EQUAL(map__kmap(map)->kmaps, maps));
- if (i > 0) {
+ if (i > 0 && i < nr_addr_sorted) {
struct map *prev = RC_CHK_ACCESS(maps)->maps_by_address[i - 1];
- /* If addresses are sorted... */
- if (RC_CHK_ACCESS(maps)->maps_by_address_sorted) {
- /* Maps should be in start address order. */
- assert(map__start(prev) <= map__start(map));
- /*
- * If the ends of maps aren't broken (during
- * construction) then they should be ordered
- * too.
- */
- if (!RC_CHK_ACCESS(maps)->ends_broken) {
- assert(map__end(prev) <= map__end(map));
- assert(map__end(prev) <= map__start(map) ||
- map__start(prev) == map__start(map));
- }
+ /* Maps in sorted prefix should be in start address order. */
+ assert(map__start(prev) <= map__start(map));
+ /*
+ * If the ends of maps aren't broken (during
+ * construction) then they should be ordered
+ * too.
+ */
+ if (!RC_CHK_ACCESS(maps)->ends_broken) {
+ assert(map__end(prev) <= map__end(map));
+ assert(map__end(prev) <= map__start(map) ||
+ map__start(prev) == map__start(map));
}
}
}
if (RC_CHK_ACCESS(maps)->maps_by_name) {
- for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
+ for (unsigned int i = 0; i < nr_maps; i++) {
struct map *map = RC_CHK_ACCESS(maps)->maps_by_name[i];
/*
@@ -137,6 +154,14 @@ static void maps__set_nr_maps_allocated(struct maps *maps, unsigned int nr_maps_
static void maps__set_nr_maps(struct maps *maps, unsigned int nr_maps)
{
RC_CHK_ACCESS(maps)->nr_maps = nr_maps;
+ if (RC_CHK_ACCESS(maps)->maps_by_address_sorted ||
+ RC_CHK_ACCESS(maps)->nr_addr_sorted > nr_maps) {
+ RC_CHK_ACCESS(maps)->nr_addr_sorted = nr_maps;
+ }
+ if (RC_CHK_ACCESS(maps)->maps_by_name_sorted ||
+ RC_CHK_ACCESS(maps)->nr_name_sorted > nr_maps) {
+ RC_CHK_ACCESS(maps)->nr_name_sorted = nr_maps;
+ }
}
/* Not in the header, to aid reference counting. */
@@ -160,6 +185,8 @@ static bool maps__maps_by_address_sorted(const struct maps *maps)
static void maps__set_maps_by_address_sorted(struct maps *maps, bool value)
{
RC_CHK_ACCESS(maps)->maps_by_address_sorted = value;
+ if (value)
+ RC_CHK_ACCESS(maps)->nr_addr_sorted = maps__nr_maps(maps);
}
static bool maps__maps_by_name_sorted(const struct maps *maps)
@@ -170,6 +197,8 @@ static bool maps__maps_by_name_sorted(const struct maps *maps)
static void maps__set_maps_by_name_sorted(struct maps *maps, bool value)
{
RC_CHK_ACCESS(maps)->maps_by_name_sorted = value;
+ if (value)
+ RC_CHK_ACCESS(maps)->nr_name_sorted = maps__nr_maps(maps);
}
struct machine *maps__machine(const struct maps *maps)
@@ -241,6 +270,8 @@ static void maps__init(struct maps *maps, struct machine *machine)
refcount_set(maps__refcnt(maps), 1);
RC_CHK_ACCESS(maps)->nr_maps = 0;
RC_CHK_ACCESS(maps)->nr_maps_allocated = 0;
+ RC_CHK_ACCESS(maps)->nr_addr_sorted = 0;
+ RC_CHK_ACCESS(maps)->nr_name_sorted = 0;
RC_CHK_ACCESS(maps)->last_search_by_name_idx = 0;
RC_CHK_ACCESS(maps)->maps_by_address_sorted = true;
RC_CHK_ACCESS(maps)->maps_by_name_sorted = false;
@@ -313,6 +344,7 @@ static void __maps__free_maps_by_name(struct maps *maps)
zfree(&RC_CHK_ACCESS(maps)->maps_by_name);
/* Consistent with maps__init(). When maps_by_name == NULL, maps_by_name_sorted == false */
+ RC_CHK_ACCESS(maps)->nr_name_sorted = 0;
maps__set_maps_by_name_sorted(maps, false);
}
@@ -339,15 +371,54 @@ static int map__start_cmp(const void *a, const void *b)
return map_a_start > map_b_start ? 1 : -1;
}
+static unsigned int maps__by_address_upper_bound(struct map **arr, unsigned int len,
+ const struct map *map)
+{
+ unsigned int low = 0, high = len;
+
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (map__start_cmp(&arr[mid], &map) <= 0)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ return low;
+}
+
static void __maps__sort_by_address(struct maps *maps)
{
+ struct map **maps_by_address;
+ unsigned int n, m, k;
+
if (maps__maps_by_address_sorted(maps))
return;
- qsort(maps__maps_by_address(maps),
- maps__nr_maps(maps),
- sizeof(struct map *),
- map__start_cmp);
+ maps_by_address = maps__maps_by_address(maps);
+ n = maps__nr_maps(maps);
+ m = RC_CHK_ACCESS(maps)->nr_addr_sorted;
+ if (m > n)
+ m = 0;
+ k = n - m;
+
+ if (k <= 8 || n <= 64) {
+ for (unsigned int i = max(m, 1U); i < n; i++) {
+ struct map *map = maps_by_address[i];
+
+ if (map__start_cmp(&maps_by_address[i - 1], &map) > 0) {
+ unsigned int pos =
+ maps__by_address_upper_bound(maps_by_address, i, map);
+
+ memmove(&maps_by_address[pos + 1],
+ &maps_by_address[pos],
+ (i - pos) * sizeof(*maps_by_address));
+ maps_by_address[pos] = map;
+ }
+ }
+ } else {
+ qsort(maps_by_address, n, sizeof(struct map *), map__start_cmp);
+ }
maps__set_maps_by_address_sorted(maps, true);
}
@@ -373,6 +444,22 @@ static int map__strcmp(const void *a, const void *b)
return ret;
}
+static unsigned int maps__by_name_upper_bound(struct map **arr, unsigned int len,
+ const struct map *map)
+{
+ unsigned int low = 0, high = len;
+
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (map__strcmp(&arr[mid], &map) <= 0)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ return low;
+}
+
static int maps__sort_by_name(struct maps *maps)
{
int err = 0;
@@ -380,6 +467,7 @@ static int maps__sort_by_name(struct maps *maps)
down_write(maps__lock(maps));
if (!maps__maps_by_name_sorted(maps)) {
struct map **maps_by_name = maps__maps_by_name(maps);
+ unsigned int n = maps__nr_maps(maps);
if (!maps_by_name) {
maps_by_name = malloc(RC_CHK_ACCESS(maps)->nr_maps_allocated *
@@ -388,18 +476,38 @@ static int maps__sort_by_name(struct maps *maps)
err = -ENOMEM;
else {
struct map **maps_by_address = maps__maps_by_address(maps);
- unsigned int n = maps__nr_maps(maps);
maps__set_maps_by_name(maps, maps_by_name);
for (unsigned int i = 0; i < n; i++)
maps_by_name[i] = map__get(maps_by_address[i]);
+ RC_CHK_ACCESS(maps)->nr_name_sorted = 0;
}
}
if (!err) {
- qsort(maps_by_name,
- maps__nr_maps(maps),
- sizeof(struct map *),
- map__strcmp);
+ unsigned int m = RC_CHK_ACCESS(maps)->nr_name_sorted;
+ unsigned int k;
+
+ if (m > n)
+ m = 0;
+ k = n - m;
+ if (k <= 8 || n <= 64) {
+ for (unsigned int i = max(m, 1U); i < n; i++) {
+ struct map *map = maps_by_name[i];
+
+ if (map__strcmp(&maps_by_name[i - 1], &map) > 0) {
+ unsigned int pos =
+ maps__by_name_upper_bound(maps_by_name,
+ i, map);
+
+ memmove(&maps_by_name[pos + 1],
+ &maps_by_name[pos],
+ (i - pos) * sizeof(*maps_by_name));
+ maps_by_name[pos] = map;
+ }
+ }
+ } else {
+ qsort(maps_by_name, n, sizeof(struct map *), map__strcmp);
+ }
maps__set_maps_by_name_sorted(maps, true);
}
}
@@ -411,19 +519,27 @@ static int maps__sort_by_name(struct maps *maps)
static unsigned int maps__by_address_index(const struct maps *maps, const struct map *map)
{
struct map **maps_by_address = maps__maps_by_address(maps);
+ unsigned int nr_sorted = RC_CHK_ACCESS(maps)->nr_addr_sorted;
+ unsigned int nr_maps = maps__nr_maps(maps);
- if (maps__maps_by_address_sorted(maps)) {
+ if (nr_sorted > nr_maps)
+ nr_sorted = 0;
+
+ if (nr_sorted > 0) {
struct map **mapp =
- bsearch(&map, maps__maps_by_address(maps), maps__nr_maps(maps),
+ bsearch(&map, maps_by_address, nr_sorted,
sizeof(*mapp), map__start_cmp);
if (mapp)
return mapp - maps_by_address;
- } else {
- for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
- if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map))
- return i;
- }
+ }
+ for (unsigned int i = nr_sorted; i < nr_maps; i++) {
+ if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map))
+ return i;
+ }
+ for (unsigned int i = 0; i < nr_sorted; i++) {
+ if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map))
+ return i;
}
pr_err("Map missing from maps");
return -1;
@@ -432,19 +548,27 @@ static unsigned int maps__by_address_index(const struct maps *maps, const struct
static unsigned int maps__by_name_index(const struct maps *maps, const struct map *map)
{
struct map **maps_by_name = maps__maps_by_name(maps);
+ unsigned int nr_sorted = RC_CHK_ACCESS(maps)->nr_name_sorted;
+ unsigned int nr_maps = maps__nr_maps(maps);
- if (maps__maps_by_name_sorted(maps)) {
+ if (nr_sorted > nr_maps)
+ nr_sorted = 0;
+
+ if (nr_sorted > 0) {
struct map **mapp =
- bsearch(&map, maps_by_name, maps__nr_maps(maps),
+ bsearch(&map, maps_by_name, nr_sorted,
sizeof(*mapp), map__strcmp);
if (mapp)
return mapp - maps_by_name;
- } else {
- for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
- if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map))
- return i;
- }
+ }
+ for (unsigned int i = nr_sorted; i < nr_maps; i++) {
+ if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map))
+ return i;
+ }
+ for (unsigned int i = 0; i < nr_sorted; i++) {
+ if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map))
+ return i;
}
pr_err("Map missing from maps");
return -1;
@@ -521,7 +645,10 @@ static int __maps__insert(struct maps *maps, struct map *new)
maps__maps_by_address_sorted(maps) &&
map__end(maps_by_address[nr_maps - 2]) <= map__start(new) &&
map__start_cmp(&maps_by_address[nr_maps - 2], &new) <= 0);
- maps__set_maps_by_name_sorted(maps, false);
+ maps__set_maps_by_name_sorted(maps,
+ maps_by_name &&
+ maps__maps_by_name_sorted(maps) &&
+ map__strcmp(&maps_by_name[nr_maps - 2], &new) <= 0);
}
if (map__end(new) < map__start(new))
RC_CHK_ACCESS(maps)->ends_broken = true;
@@ -553,6 +680,8 @@ static void __maps__remove(struct maps *maps, struct map *map)
memmove(&maps_by_address[address_idx],
&maps_by_address[address_idx + 1],
(nr_maps - address_idx - 1) * sizeof(*maps_by_address));
+ if (address_idx < RC_CHK_ACCESS(maps)->nr_addr_sorted)
+ --RC_CHK_ACCESS(maps)->nr_addr_sorted;
if (maps_by_name) {
unsigned int name_idx = maps__by_name_index(maps, map);
@@ -561,9 +690,16 @@ static void __maps__remove(struct maps *maps, struct map *map)
memmove(&maps_by_name[name_idx],
&maps_by_name[name_idx + 1],
(nr_maps - name_idx - 1) * sizeof(*maps_by_name));
+ if (name_idx < RC_CHK_ACCESS(maps)->nr_name_sorted)
+ --RC_CHK_ACCESS(maps)->nr_name_sorted;
}
- --RC_CHK_ACCESS(maps)->nr_maps;
+ --nr_maps;
+ RC_CHK_ACCESS(maps)->nr_maps = nr_maps;
+ if (RC_CHK_ACCESS(maps)->nr_addr_sorted == nr_maps)
+ RC_CHK_ACCESS(maps)->maps_by_address_sorted = true;
+ if (maps_by_name && RC_CHK_ACCESS(maps)->nr_name_sorted == nr_maps)
+ RC_CHK_ACCESS(maps)->maps_by_name_sorted = true;
}
void maps__remove(struct maps *maps, struct map *map)
@@ -604,7 +740,9 @@ int maps__mutate_mapping(struct maps *maps, struct map *map,
err = mutate_cb(map, data);
+ RC_CHK_ACCESS(maps)->nr_addr_sorted = 0;
RC_CHK_ACCESS(maps)->maps_by_address_sorted = false;
+ RC_CHK_ACCESS(maps)->nr_name_sorted = 0;
RC_CHK_ACCESS(maps)->maps_by_name_sorted = false;
up_write(maps__lock(maps));
@@ -858,6 +996,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;
@@ -925,7 +1067,17 @@ static int __maps__insert_sorted(struct maps *maps, unsigned int first_after_ind
maps_by_name[nr_maps + 1] = map__get(new2);
}
RC_CHK_ACCESS(maps)->nr_maps = nr_maps + to_add;
- maps__set_maps_by_name_sorted(maps, false);
+ RC_CHK_ACCESS(maps)->nr_addr_sorted = nr_maps + to_add;
+ if (maps_by_name) {
+ if (nr_maps == 0 && to_add == 1) {
+ maps__set_maps_by_name_sorted(maps, true);
+ } else {
+ maps__set_maps_by_name_sorted(maps,
+ maps__maps_by_name_sorted(maps) &&
+ map__strcmp(&maps_by_name[nr_maps - 1], &new1) <= 0 &&
+ (!new2 || map__strcmp(&new1, &new2) <= 0));
+ }
+ }
map__set_kmap_maps(new1, maps);
map__set_kmap_maps(new2, maps);
@@ -1049,9 +1201,16 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
map__set_kmap_maps(new, maps);
if (maps_by_name) {
+ unsigned int nr_maps = maps__nr_maps(maps);
+
map__put(maps_by_name[ni]);
- maps_by_name[ni] = map__get(new);
- maps__set_maps_by_name_sorted(maps, false);
+ memmove(&maps_by_name[ni],
+ &maps_by_name[ni + 1],
+ (nr_maps - ni - 1) * sizeof(*maps_by_name));
+ maps_by_name[nr_maps - 1] = map__get(new);
+ if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted)
+ --RC_CHK_ACCESS(maps)->nr_name_sorted;
+ maps__set_maps_by_name_sorted(maps, nr_maps <= 1);
}
err = __maps__insert_sorted(maps, i + 1, after, NULL);
@@ -1077,8 +1236,13 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
if (maps_by_name) {
map__put(maps_by_name[ni]);
- maps_by_name[ni] = map__get(new);
- maps__set_maps_by_name_sorted(maps, false);
+ memmove(&maps_by_name[ni],
+ &maps_by_name[ni + 1],
+ (nr_maps - ni - 1) * sizeof(*maps_by_name));
+ maps_by_name[nr_maps - 1] = map__get(new);
+ if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted)
+ --RC_CHK_ACCESS(maps)->nr_name_sorted;
+ maps__set_maps_by_name_sorted(maps, nr_maps <= 1);
}
check_invariants(maps);
@@ -1094,14 +1258,20 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
memmove(&maps_by_address[i],
&maps_by_address[i + 1],
(nr_maps - i - 1) * sizeof(*maps_by_address));
+ --RC_CHK_ACCESS(maps)->nr_addr_sorted;
if (maps_by_name) {
map__put(maps_by_name[ni]);
memmove(&maps_by_name[ni],
&maps_by_name[ni + 1],
(nr_maps - ni - 1) * sizeof(*maps_by_name));
+ if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted)
+ --RC_CHK_ACCESS(maps)->nr_name_sorted;
}
--RC_CHK_ACCESS(maps)->nr_maps;
+ if (maps_by_name &&
+ RC_CHK_ACCESS(maps)->nr_name_sorted == RC_CHK_ACCESS(maps)->nr_maps)
+ RC_CHK_ACCESS(maps)->maps_by_name_sorted = true;
check_invariants(maps);
/*
* Maps are ordered but no need to increase `i` as the
@@ -1181,9 +1351,17 @@ int maps__copy_from(struct maps *dest, struct maps *parent)
if (err)
map__put(new);
}
- maps__set_maps_by_address_sorted(dest, maps__maps_by_address_sorted(parent));
+ if (maps__maps_by_address_sorted(parent)) {
+ maps__set_maps_by_address_sorted(dest, true);
+ } else {
+ RC_CHK_ACCESS(dest)->nr_addr_sorted =
+ min(RC_CHK_ACCESS(parent)->nr_addr_sorted,
+ RC_CHK_ACCESS(dest)->nr_maps);
+ maps__set_maps_by_address_sorted(dest, false);
+ }
RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0;
/* Values were copied into the name array in address order. */
+ RC_CHK_ACCESS(dest)->nr_name_sorted = 0;
maps__set_maps_by_name_sorted(dest, false);
} else {
/* Unexpected copying to a maps containing entries. */
--
2.56.1.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (3 preceding siblings ...)
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 ` 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
` (3 subsequent siblings)
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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.
- Convert symbols__for_each_entry(), dso__for_each_symbol(), and
map__for_each_symbol() to callback-based iteration under
symbols->lock, matching dsos__for_each_dso() and maps__for_each_map().
- 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/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/symbols.c | 62 +-
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 | 50 +-
tools/perf/util/dso.h | 68 +--
tools/perf/util/intel-pt.c | 74 ++-
tools/perf/util/libbfd.c | 3 +-
tools/perf/util/machine.c | 30 +-
tools/perf/util/map.c | 36 +-
tools/perf/util/map.h | 8 +-
tools/perf/util/probe-event.c | 98 +--
tools/perf/util/symbol-elf.c | 12 +-
tools/perf/util/symbol.c | 643 ++++++++++++++------
tools/perf/util/symbol.h | 72 ++-
tools/perf/util/symbol_fprintf.c | 25 +-
23 files changed, 1011 insertions(+), 633 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-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/builtin-kmem.c b/tools/perf/builtin-kmem.c
index 8693c6b135ca..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?";
@@ -364,30 +384,17 @@ 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;
}
- 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)
- 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/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/tests/symbols.c b/tools/perf/tests/symbols.c
index d3180db45ee6..1220f97b77bb 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);
-
- if (symbol__type(sym) != STT_FUNC && symbol__type(sym) != STT_GNU_IFUNC)
- continue;
+ dso__for_each_symbol(dso, test_dso_cb, &args);
- /* 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)
@@ -487,3 +498,4 @@ struct test_suite suite__symbols = {
.desc = "Symbols",
.test_cases = tests__symbols,
};
+
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/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/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/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 e46cd614eb21..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));
@@ -2011,22 +2001,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 d5f7382d4e13..f23cf9957aec 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[];
@@ -365,11 +359,14 @@ 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__for_each_entry(dso__symbols(dso), cb, data)
+
+#define dso__for_each_symbol_by_name(dso, cb, data) \
+ symbols__visit_by_name(dso__symbols(dso), cb, data)
static inline void *dso__a2l(const struct dso *dso)
{
@@ -598,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;
@@ -730,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;
@@ -823,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);
@@ -953,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/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/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 5b4550e97172..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);
@@ -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/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/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..e3f8e3cd68c0 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;
+}
- return found;
+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 args.found;
}
void __weak arch__fix_tev_from_maps(struct perf_probe_event *pev __maybe_unused,
@@ -3774,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)
{
@@ -3810,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-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 a1ac1cd1d2e7..f1e3d7af714c 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;
+
+ down_write(&symbols->lock);
+ symbols__sort_locked(symbols);
- if (prevnd == NULL)
+ 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,97 +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)
-{
- struct symbol *pos;
- struct rb_node *next = rb_first_cached(symbols);
- 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);
- }
-}
-
-void __symbols__insert(struct rb_root_cached *symbols, struct symbol *sym)
+static 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;
+ 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 (*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;
+ if (!temp) {
+ symbol__delete(sym);
+ return -ENOMEM;
}
+ symbols->symbols = temp;
+ symbols->allocated = to_allocate;
}
- rb_link_node(&sym->rb_node, parent, p);
- rb_insert_color_cached(&sym->rb_node, symbols, leftmost);
+
+ 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)
{
- __symbols__insert(symbols, sym);
+ int ret;
+
+ down_write(&symbols->lock);
+ ret = __symbols__insert(symbols, sym);
+ up_write(&symbols->lock);
+ return ret;
}
-static struct symbol *symbols__find(struct rb_root_cached *symbols, u64 ip)
+static inline bool symbol__covers(const struct symbol *s, u64 ip)
{
- struct rb_node *n;
+ u64 start = s->start;
+ u64 end = s->end;
- if (symbols == NULL)
- return NULL;
+ return ip >= start && (ip < end || (ip == end && ip == start));
+}
- n = symbols->rb_root.rb_node;
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
+{
+ unsigned int low = 0, high = cnt, idx;
+ u64 start;
- while (n) {
- struct symbol *s = rb_entry(n, struct symbol, rb_node);
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
- if (ip < s->start)
- n = n->rb_left;
- else if (ip > s->end || (ip == s->end && ip != s->start))
- n = n->rb_right;
+ if (arr[mid]->start <= ip)
+ low = mid + 1;
else
- return s;
+ 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__first(struct rb_root_cached *symbols)
+/*
+ * 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 = rb_first_cached(symbols);
-
- if (n)
- return rb_entry(n, struct symbol, rb_node);
-
- return NULL;
-}
+ struct symbol *res;
-static struct symbol *symbols__last(struct rb_root_cached *symbols)
-{
- struct rb_node *n = rb_last(&symbols->rb_root);
+ if (symbols == NULL)
+ return NULL;
- if (n)
- return rb_entry(n, struct symbol, rb_node);
+ symbols__sort_read_lock(symbols);
+ res = symbols__find_range(symbols->symbols, symbols->cnt, ip);
+ up_read(&symbols->lock);
- return NULL;
+ return res;
}
-static struct symbol *symbols__next(struct symbol *sym)
+int symbols__for_each_entry(struct symbols *symbols,
+ int (*cb)(struct symbol *sym, void *data),
+ void *data)
{
- struct rb_node *n = rb_next(&sym->rb_node);
+ int err = 0;
- if (n)
- return rb_entry(n, struct symbol, rb_node);
+ 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)
@@ -489,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;
- for (nd = rb_first_cached(source); nd; nd = rb_next(nd)) {
- struct symbol *pos = rb_entry(nd, struct symbol, rb_node);
+ 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;
+}
+
+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,
@@ -578,39 +733,34 @@ static struct symbol *symbols__find_by_name(struct symbol *symbols[],
return s;
}
-void dso__reset_find_symbol_cache(struct dso *dso)
+int dso__insert_symbol(struct dso *dso, struct symbol *sym)
{
- 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)
-{
- __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 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;
+ }
+ }
+ up_write(&symbols->lock);
}
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));
- }
-
- return dso__last_find_result_symbol(dso);
+ return symbols__find(dso__symbols(dso), addr);
}
struct symbol *dso__find_symbol_nocache(struct dso *dso, u64 addr)
@@ -618,28 +768,23 @@ 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)
-{
- return symbols__first(dso__symbols(dso));
-}
-
-struct symbol *dso__last_symbol(struct dso *dso)
-{
- return symbols__last(dso__symbols(dso));
-}
-
-struct symbol *dso__next_symbol(struct symbol *sym)
-{
- return symbols__next(sym);
-}
-
struct symbol *dso__next_symbol_by_name(struct dso *dso, size_t *idx)
{
- if (*idx + 1 >= dso__symbol_names_len(dso))
+ struct symbols *symbols;
+ struct symbol *res = NULL;
+
+ if (!dso)
return NULL;
- ++*idx;
- return dso__symbol_names(dso)[*idx];
+ 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];
+ }
+ up_read(&symbols->lock);
+
+ return res;
}
/*
@@ -647,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;
}
/*
@@ -869,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;
@@ -890,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);
}
/*
@@ -909,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';
@@ -944,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);
@@ -967,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;
@@ -978,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) {
@@ -1067,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) {
@@ -1082,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;
@@ -1102,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))) {
@@ -1121,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,
@@ -1681,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 a6a2ab200f98..adfb1a3a89be 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)
{
@@ -141,16 +175,19 @@ 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__for_each_entry - 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 'struct symbols *' of symbols
+ * @cb: callback function invoked under @symbols->lock
+ * @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__for_each_entry(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);
@@ -198,10 +235,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);
-struct symbol *dso__first_symbol(struct dso *dso);
-struct symbol *dso__last_symbol(struct dso *dso);
-struct symbol *dso__next_symbol(struct symbol *sym);
-
enum dso_type dso__type_fd(int fd);
int filename__read_build_id(const char *filename, struct build_id *id);
@@ -252,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,
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.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (4 preceding siblings ...)
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 ` Ian Rogers
2026-11-16 6:34 ` [PATCH v5 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
` (2 subsequent siblings)
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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, and dynamic symbol resolution
(dso__insert_symbol()) frequently inserts one or a few symbols into an
already-sorted DSO symbol table. Invoking full-array qsort() on every
sort after incremental insertions or across pre-ordered ELF runs spends
avoidable CPU time in symbol comparisons.
Speed up symbol array sorting and out-of-order symbol insertions:
- Track the sorted prefix length (@sorted_cnt) in struct symbols and
replace full-array qsort() with a natural-run merge sort
(symbols__sort_range_with_tmp()) and galloping binary-search merge
(symbols__merge_runs()), plus an O(N) in-place binary insertion fast
path when <= 8 symbols are appended.
- Insert directly into sorted position in dso__insert_symbol() when
symbols->sorted is true so dynamic single-symbol insertions maintain
the sorted invariant without triggering full re-sorts.
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)
Average append + lookup: 40429.750 usec (+- 507.578 usec)
After (-7.0% load, -13.9% bulk, -99.6% append):
Average DSO load + sort: 5.808 msec (+- 0.047 msec)
Average bulk insert + lookup: 1209.250 usec (+- 18.446 usec)
Average append + lookup: 152.900 usec (+- 0.736 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/util/symbol.c | 413 +++++++++++++++++++++++++++++++++++++--
tools/perf/util/symbol.h | 11 +-
2 files changed, 405 insertions(+), 19 deletions(-)
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index f1e3d7af714c..8a47d1a44e5c 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;
@@ -263,37 +265,311 @@ 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 unsigned int symbols__lower_bound(struct symbol **arr, unsigned int len,
+ const struct symbol *sym)
+{
+ unsigned int low = 0, high = len;
+
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+
+ if (!symbol__less_or_equal(sym, arr[mid]))
+ 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, last_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]);
+ right_len = right - mid;
+
+ if (mid - first_left <= right_len) {
+ left_len = mid - first_left;
+ 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 (right - j >= 16 &&
+ (right - j) > 8 * (left_len - i) &&
+ !symbol__less_or_equal(tmp[i], arr[j])) {
+ unsigned int step =
+ symbols__lower_bound(&arr[j], right - j, tmp[i]);
+
+ if (step > 0) {
+ memmove(&arr[dst], &arr[j],
+ step * sizeof(struct symbol *));
+ dst += step;
+ j += step;
+ }
+ }
+ }
+ }
+ if (i < left_len)
+ memcpy(&arr[dst], &tmp[i], (left_len - i) * sizeof(struct symbol *));
+ return;
+ }
+
+ last_left = first_left +
+ symbols__upper_bound(&arr[first_left], mid - first_left, arr[right - 1]);
+ left_len = last_left - first_left;
+
+ memcpy(tmp, &arr[mid], right_len * sizeof(struct symbol *));
+ if (last_left < mid) {
+ memmove(&arr[last_left + right_len], &arr[last_left],
+ (mid - last_left) * sizeof(struct symbol *));
+ }
+
+ if (first_left == last_left) {
+ memcpy(&arr[first_left], tmp, right_len * sizeof(struct symbol *));
+ return;
+ }
+
+ i = last_left;
+ j = right_len;
+ dst = last_left + right_len;
+ 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 (i - first_left >= 16 &&
+ (i - first_left) > 8 * j &&
+ !symbol__less_or_equal(arr[i - 1], tmp[j - 1])) {
+ unsigned int pos = first_left +
+ symbols__upper_bound(&arr[first_left],
+ i - first_left,
+ tmp[j - 1]);
+ unsigned int step = i - pos;
+
+ if (step > 0) {
+ dst -= step;
+ i = pos;
+ memmove(&arr[dst], &arr[pos],
+ step * sizeof(struct symbol *));
+ }
+ }
+ }
+ }
+ 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)
{
- 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 > 1) {
- qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
- symbols__sort_cmp);
+ /*
+ * 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);
+ 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) {
+ symbols__sort_range_with_tmp(symbols->symbols, symbols->cnt, tmp);
+ free(tmp);
+ } 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);
@@ -342,6 +618,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;
@@ -517,9 +794,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);
@@ -528,6 +811,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;
@@ -589,8 +935,24 @@ static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
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);
+ if (symbols->sorted_cnt < symbols->cnt) {
+ struct symbol *tail_res;
+
+ tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
+ symbols->cnt - symbols->sorted_cnt, ip);
+ if (tail_res && (!res || tail_res->start > res->start))
+ res = tail_res;
+ }
up_read(&symbols->lock);
return res;
@@ -735,7 +1097,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)
@@ -743,11 +1111,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;
@@ -1094,6 +1466,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);
@@ -1168,6 +1541,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);
@@ -1314,6 +1688,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;
@@ -1343,12 +1718,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 adfb1a3a89be..ce7be4b18a11 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.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (5 preceding siblings ...)
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 ` 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
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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 f23cf9957aec..962e1ad0c463 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 8a47d1a44e5c..e8b1445fd198 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
@@ -2428,8 +2491,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);
@@ -2587,6 +2651,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 ce7be4b18a11..d70c01609017 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.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 8/9] perf session: Add dso__session() and session-scoped allocation wrappers
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (6 preceding siblings ...)
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 ` 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
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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 962e1ad0c463..0991a5ab7c8d 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.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH v5 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
` (7 preceding siblings ...)
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 ` Ian Rogers
8 siblings, 0 replies; 13+ messages in thread
From: Ian Rogers @ 2026-11-16 6:34 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 | 748 ++++++++++++++++++++++++++++++++++++-
1 file changed, 737 insertions(+), 11 deletions(-)
diff --git a/tools/perf/tests/symbols.c b/tools/perf/tests/symbols.c
index 1220f97b77bb..29b46ee43e71 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,240 @@ 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 a dynamic symbol into the unmerged sorted tail inside an
+ * existing primary-prefix symbol's [0x0, 0x40) range and verify lookup
+ * resolves to the closer tail symbol rather than the outer prefix one.
+ */
+ {
+ struct symbol *inner = symbol__new(0x20, 0x10, STB_GLOBAL, STT_FUNC,
+ "inner_tail_sym");
+
+ if (!inner || dso__insert_symbol(dso, inner))
+ goto out;
+ if (symbols->sorted_cnt >= symbols->cnt) {
+ pr_debug("Expected unmerged sorted tail!\n");
+ goto out;
+ }
+ if (dso__find_symbol(dso, 0x24) != inner) {
+ pr_debug("Tail symbol lookup returned outer prefix symbol!\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 +956,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 +1007,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 +1017,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.703.gf848ed807c-goog
^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v5 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes
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:44 ` sashiko-bot
0 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-11-16 6:44 UTC (permalink / raw)
To: Ian Rogers; +Cc: linux-perf-users
> struct call_path stores resolved function symbols for the lifetime of a
> call_path_root (in thread-stack call/return processing and db-export)
> without holding a map reference. Similarly, Python callchain frames and
> nodes store resolved symbols across Python object lifetimes.
>
> Replace bare struct symbol * fields in struct call_path,
> struct pyrf_callchain_frame, and struct pyrf_callchain_node with
> struct dso_symbol so that each retained symbol pins its owning
> struct dso until call_path_root__free() or Python deallocation. In
> python.c, this also avoids duplicating symbol names for call_path frames
> and allows pyrf_callchain_node__get_dso() to report the DSO of resolved
> call_path symbols whose ip was zeroed. Also document the DSO-owned
> symbol lifetime invariants in kernel-doc comments on struct dso_symbol
> and struct map_symbol.
>
> Signed-off-by: Ian Rogers <irogers@google.com>
Sashiko has reviewed this patch and found no issues.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261116063435.2817923-1-irogers@google.com?part=1
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v5 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup
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:48 ` sashiko-bot
0 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-11-16 6:48 UTC (permalink / raw)
To: Ian Rogers; +Cc: linux-perf-users
> Profiling dso__load_sym_internal() on large binaries showed significant
> time spent in repeated libelf section and program header lookups
> (elf_section_by_idx() and elf_read_program_header()) for each symbol and
> in resolving elf_sym__name() before filtering out non-symbol and
> non-allocated entries.
>
> Speed up ELF symbol table loading in dso__load_sym_internal():
>
> - Pre-load PT_LOAD program headers into struct elf_phdr_cache and cache
> per-section metadata in a 64-entry direct-mapped table in
> dso__load_sym_internal() to avoid repeated libelf section and program
> header lookups during symbol iteration.
> - Defer elf_sym__name() lookup until after non-allocated and non-symbol
> entries have been filtered out.
>
> [ ... ]
> Average DSO load + sort: 22.433 msec (+- 0.260 msec)
> After (libLLVM.so.21.1, --no-demangle, -14.8%):
> Average DSO load + sort: 19.122 msec (+- 0.226 msec)
>
> Signed-off-by: Ian Rogers <irogers@google.com>
Sashiko has reviewed this patch and found no issues.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261116063435.2817923-1-irogers@google.com?part=3
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v5 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size
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:51 ` sashiko-bot
0 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-11-16 6:51 UTC (permalink / raw)
To: Ian Rogers; +Cc: linux-perf-users
> Previously, enabling annotation added sizeof(struct annotation) to
> symbol_conf.priv_size, bloating every loaded struct symbol in every DSO
> even though only a small fraction of symbols are ever annotated.
>
> Move struct annotation storage to an on-demand hashmap in
> util/annotate.c keyed by struct symbol pointer, guarded by
> annotations_lock, with an atomic nr_annotations count so unannotated
> sessions skip lock and teardown overhead while symbol__annotated()
> checks the hashmap under a read lock. Return NULL from
> symbol__annotation() on allocation failure and check for NULL at
> entry-point callers.
>
> With annotation, TUI map browser indices, and db-export symbol IDs no
> longer using negative-offset space ahead of struct symbol, remove
> symbol_conf.priv_size and symbol__priv().
>
> Signed-off-by: Ian Rogers <irogers@google.com>
Sashiko has reviewed this patch and found no issues.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261116063435.2817923-1-irogers@google.com?part=2
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2026-11-16 6:51 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-16 6:34 [PATCH v5 0/9] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
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:44 ` sashiko-bot
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:51 ` sashiko-bot
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:48 ` sashiko-bot
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
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox