Skip to contentSkip to conversation

perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking

PATCH In review Ian Rogers 3 participants 22 messages Nov 17 – Nov 18 perf events

lore
Share & tools
lore

Ian Rogers

author reviewer
#0 lore raw

v6 cover perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking

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 v6:
- Fix symbols__find() when sorted_cnt < cnt so that if the slice (sorted prefix or unmerged sorted tail) with the higher start <= ip group ends before ip, symbols__find() returns NULL rather than falling back to an earlier outer symbol in the other slice (Patch 6), matching post-merge behavior, and add unmerged-vs-merged prefix/tail overlap and equal-start alias unit tests (Patch 9) (Sashiko).
- Use positive ENOMEM rather than -ENOMEM on symbol__annotation() failure in symbol__annotate(), symbol__annotate2(), and __hist_entry__tui_annotate() to match symbol__strerror_disassemble(), check symbol__annotate() != 0 in hist_entry__get_data_type(), and guard against NULL notes / notes->src in find_disasm_line() (Patch 2) (Sashiko).

Changes in v5:
- Rebase onto perf-tools-next (b7ff10b9ddec), dropping the 10 patches from v4 that have been applied upstream.
- Defer perf_singlethreaded removal, rwsem trylock helpers, and wiring perf_session__* allocation wrappers into symbol/DSO/thread/hist callers to follow-up work while keeping the shrinking APIs and unit tests (Namhyung Kim).
- Drop the mechanical struct symbol field-accessor refactoring patch (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).

v5: https://lore.kernel.org/linux-perf-users/[email protected]/
v4: https://lore.kernel.org/linux-perf-users/[email protected]/
v3: https://lore.kernel.org/linux-perf-users/[email protected]/
v2: https://lore.kernel.org/linux-perf-users/[email protected]/
v1: https://lore.kernel.org/lkml/[email protected]/

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                  |  841 +++++++++++++-
 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                  |  156 ++-
 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                    | 1120 +++++++++++++++----
 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, 3573 insertions(+), 882 deletions(-)
Signature · 1 line
2.56.1.703.gf848ed807c-goog
author reviewer
#1 lore raw

PATCH v6 1/9 perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes

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.

---
 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(-)
tools/perf/util/call-path.c +32 -10
index 5c60b8be1cf6..eac52a902d6b 100644
@@ -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;
 
tools/perf/util/call-path.h +6 -4
index 5875cfc8106e..e43aa7513633 100644
@@ -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
tools/perf/util/db-export.c +9 -3
index 8e08b306c8d3..e7b807e968cf 100644
@@ -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. */
tools/perf/util/map_symbol.h +28 -0
index 1781af7bd965..ee53b743fcc1 100644
@@ -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;
tools/perf/util/python.c +24 -29

127 lines not on this page · raw message

tools/perf/util/thread-stack.c +22 -18
index d452d1a7eabb..aa05acb0467c 100644
@@ -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);
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#2 lore raw

Re: [PATCH v6 1/9] perf call-path: Use struct dso_symbol to retain symbol DSO lifetimes

Sashiko has reviewed this patch and found no issues.
Quoted 15 lines

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.

Quoted 1 line

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
author reviewer
#3 lore raw

PATCH v6 2/9 perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size

In reply to Ian Rogers

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().

---
 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        | 156 +++++++++++++++++++++++++++++-
 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, 238 insertions(+), 53 deletions(-)
tools/perf/builtin-annotate.c +4 -1
index 331adbdbd635..7cb7e03d9a21 100644
@@ -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);
tools/perf/builtin-top.c +16 -5
index a3442d2d6edf..a272e6649077 100644
@@ -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);
 
tools/perf/tests/builtin-test.c +0 -1
index 327483f96401..01c78ef20b97 100644
@@ -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;
 
 
tools/perf/ui/browsers/annotate.c +14 -2
index cf36b5347f72..20345f518066 100644
@@ -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(&notes->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(&notes->src->source);
+
 	if (not_annotated || !symbol__is_annotate2(sym)) {
 		err = symbol__annotate2(ms, evsel, &browser.arch);
 		if (err) {
tools/perf/ui/browsers/hists.c +19 -4
index 593e1fd5759d..6f9d9f7aec91 100644
@@ -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",
tools/perf/ui/gtk/annotate.c +4 -0
index 094dfa045b77..13a175c1b6e7 100644
@@ -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;
tools/perf/util/annotate.c +154 -2

218 lines not on this page · raw message

tools/perf/util/annotate.h +3 -4
index 1b47c1156b9a..bc2237609d6e 100644
@@ -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);
 
tools/perf/util/block-info.c +1 -1
index 1135e54f4c7f..572cfb569849 100644
@@ -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));
tools/perf/util/block-range.c +9 -2
index 280d695c6c58..9c3d70ffcc29 100644
@@ -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;
 
tools/perf/util/sort.c +7 -2
index f4c50f191141..57d7877782d1 100644
@@ -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);
tools/perf/util/symbol.c +6 -21
index dc70bbe8514f..a1ac1cd1d2e7 100644
@@ -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)
tools/perf/util/symbol.h +1 -7
index 6347bd218ad5..a6a2ab200f98 100644
@@ -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;
tools/perf/util/symbol_conf.h +0 -1
index 37d35f42dcc1..aaa7148c3ac1 100644
@@ -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,
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#4 lore raw

Re: [PATCH v6 2/9] perf annotate: Move struct annotation to a hashmap and remove symbol_conf.priv_size

Sashiko has reviewed this patch and found no issues.
Quoted 12 lines

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.

Quoted 5 lines

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().

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
author reviewer
#5 lore raw

PATCH v6 3/9 perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup

In reply to Ian Rogers

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)
---
 tools/perf/util/symbol-elf.c | 239 ++++++++++++++++++++++++++++-------
 1 file changed, 196 insertions(+), 43 deletions(-)
tools/perf/util/symbol-elf.c +196 -43
index 98b6d7c73d23..2b7f9e30916d 100644
@@ -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;
 }
 
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#6 lore raw

Re: [PATCH v6 3/9] perf symbol-elf: Cache ELF program/section headers and defer symbol name lookup

Sashiko has reviewed this patch and found no issues.
Quoted 15 lines

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.

Quoted 6 lines

[ ... ]

    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)

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
author reviewer
#7 lore raw

PATCH v6 4/9 perf maps: Optimize tail insertion and small-append sorting

In reply to Ian Rogers

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)
---
 tools/perf/tests/maps.c |  67 ++++++++++
 tools/perf/util/maps.c  | 276 +++++++++++++++++++++++++++++++++-------
 2 files changed, 294 insertions(+), 49 deletions(-)
tools/perf/tests/maps.c +67 -0
index ff6d25f9c043..04ab425f4a87 100644
@@ -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, }
 };
 
tools/perf/util/maps.c +227 -49

470 lines not on this page · raw message

Signature · 1 line
2.56.1.703.gf848ed807c-goog
#8 lore raw

Re: [PATCH v6 4/9] perf maps: Optimize tail insertion and small-append sorting

Sashiko has reviewed this patch and found no issues.
Quoted 17 lines

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
[ ... ]
After (-6.9% ascending, -98.7% append):

Quoted 4 lines
    Average ascending insert + lookup: 58.970 usec (+- 0.609 usec)
    Average append + lookup: 96.670 usec (+- 1.353 usec)

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
maintainer
#9 lore raw

Re: [PATCH v6 4/9] perf maps: Optimize tail insertion and small-append sorting

In reply to Ian Rogers
Quoted 10 lines · Ian Rogers

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).

This looks good.

Quoted 14 lines

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.

Can you split this part? Also I'm not sure if it's worth the complexity. Isn't the first change good enough?

Maybe it can defer sorting until it's really needed when N is small. But anyway I'd like to keep this code simple as it's already complex.

Thanks,
Namhyung

Quoted 606 lines

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)
---
 tools/perf/tests/maps.c |  67 ++++++++++
 tools/perf/util/maps.c  | 276 +++++++++++++++++++++++++++++++++-------
 2 files changed, 294 insertions(+), 49 deletions(-)
tools/perf/tests/maps.c +67 -0
index ff6d25f9c043..04ab425f4a87 100644
@@ -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, }
 };
 
tools/perf/util/maps.c +227 -49
index 675fe0223faa..b420c2f2b72a 100644
@@ -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. */
Signature · 1 line
2.56.1.703.gf848ed807c-goog
author reviewer
#10 lore raw

PATCH v6 5/9 perf symbol: Switch backing storage from rbtree to struct symbols array

In reply to Ian Rogers

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)

---
 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(-)
tools/perf/arch/powerpc/util/sym-handling.c +24 -10
index 947bfad7aa59..f87d77262c00 100644
@@ -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 */
tools/perf/builtin-annotate.c +0 -11
index 7cb7e03d9a21..65846110c309 100644
@@ -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;
 	}
 
tools/perf/builtin-kmem.c +29 -22

72 lines not on this page · raw message

tools/perf/tests/hists_common.c +4 -1
index 187f12f5bc21..0d3acb03e02c 100644
@@ -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);
tools/perf/tests/symbols.c +37 -25

79 lines not on this page · raw message

tools/perf/tests/vmlinux-kallsyms.c +93 -88

217 lines not on this page · raw message

tools/perf/ui/browser.c +3 -0
index 321187b204d3..c7451f640d1d 100644
@@ -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;
tools/perf/ui/browsers/hists.c +2 -1
index 6f9d9f7aec91..ad6882744eba 100644
@@ -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;
tools/perf/ui/browsers/map.c +41 -21

92 lines not on this page · raw message

tools/perf/util/auxtrace.c +72 -37

133 lines not on this page · raw message

tools/perf/util/db-export.c +2 -2
index e7b807e968cf..b3790383237f 100644
@@ -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) {
tools/perf/util/dso.c +26 -24

85 lines not on this page · raw message

tools/perf/util/dso.h +11 -57

131 lines not on this page · raw message

tools/perf/util/intel-pt.c +45 -29

94 lines not on this page · raw message

tools/perf/util/libbfd.c +2 -1
index 58cadc93e8b5..c78865690ebb 100644
@@ -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
tools/perf/util/machine.c +18 -12
index 5b4550e97172..e8a3d8095346 100644
@@ -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.
tools/perf/util/map.c +22 -14
index d5319ffa88a7..5c75741e4cb7 100644
@@ -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)"
tools/perf/util/map.h +4 -4
index c2e31be232c8..32f1fd9a7404 100644
@@ -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
tools/perf/util/probe-event.c +58 -40

125 lines not on this page · raw message

tools/perf/util/symbol-elf.c +8 -4
index 2b7f9e30916d..bda0b92ada24 100644
@@ -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);
tools/perf/util/symbol.c +440 -203

879 lines not on this page · raw message

tools/perf/util/symbol.h +52 -20

117 lines not on this page · raw message

tools/perf/util/symbol_fprintf.c +18 -7
index 4dc8d5761f52..f818e7ad1519 100644
@@ -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;
 }
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#11 lore raw

Re: [PATCH v6 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array

Sashiko has reviewed this patch and found no issues.
Quoted 20 lines

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:
[ ... ]
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)

Quoted 1 line

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
maintainer
#12 lore raw

Re: [PATCH v6 5/9] perf symbol: Switch backing storage from rbtree to struct symbols array

In reply to Ian Rogers
Quoted 124 lines · Ian Rogers

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)

---
 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(-)
tools/perf/arch/powerpc/util/sym-handling.c +17 -7
index 947bfad7aa59..f87d77262c00 100644
@@ -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);

tools/perf/arch/powerpc/util/sym-handling.c void arch__post_process_probe_trace_events(struct perf_probe_event *pev, · line 152

Quoted 10 lines
tools/perf/arch/powerpc/util/sym-handling.c +7 -3
-				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);

Please separate the map__for_each_symbol() changes as it can be converted independently. New users can be separate commits too.

Quoted 67 lines
tools/perf/arch/powerpc/util/sym-handling.c +0 -0
 	}
 }
 #endif /* HAVE_LIBELF_SUPPORT */
tools/perf/builtin-annotate.c +0 -11
index 7cb7e03d9a21..65846110c309 100644
@@ -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;
 	}
 
tools/perf/builtin-kmem.c +23 -3
index 8693c6b135ca..87869c717266 100644
@@ -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?";

tools/perf/builtin-kmem.c static int build_alloc_func_list(void) · line 387

Quoted 4 lines
tools/perf/builtin-kmem.c +1 -0
@@ -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);

Looks like an unrelated bug fix.

Thanks,
Namhyung

Quoted 31 lines
tools/perf/builtin-kmem.c +5 -19
 		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;
 }
author reviewer
#13 lore raw

PATCH v6 6/9 perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion

In reply to Ian Rogers

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)
---
 tools/perf/util/symbol.c | 433 +++++++++++++++++++++++++++++++++++++--
 tools/perf/util/symbol.h |  11 +-
 2 files changed, 423 insertions(+), 21 deletions(-)
tools/perf/util/symbol.c +413 -20
index f1e3d7af714c..84a8b3e4c528 100644
@@ -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 (symbols->cnt > 1) {
-		qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
-		      symbols__sort_cmp);
+	if (m > symbols->cnt)
+		m = 0;
+	k = symbols->cnt - m;
+
+	if (k == 0) {
+		symbols->sorted = true;
+		return;
+	}
+
+	/*
+	 * 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;
@@ -546,7 +892,9 @@ static inline bool symbol__covers(const struct symbol *s, u64 ip)
 	return ip >= start && (ip < end || (ip == end && ip == start));
 }
 
-static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
+					  u64 ip, bool *has_candidate,
+					  u64 *candidate_start)
 {
 	unsigned int low = 0, high = cnt, idx;
 	u64 start;
@@ -559,8 +907,10 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 		else
 			high = mid;
 	}
-	if (low == 0)
+	if (low == 0) {
+		*has_candidate = false;
 		return NULL;
+	}
 
 	/*
 	 * Rewind across any equal-start group so a trailing zero-length or
@@ -569,6 +919,8 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 	 */
 	idx = low - 1;
 	start = arr[idx]->start;
+	*has_candidate = true;
+	*candidate_start = start;
 	while (idx > 0 && arr[idx - 1]->start == start)
 		idx--;
 	for (; idx < low; idx++) {
@@ -585,12 +937,38 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
 {
 	struct symbol *res;
+	bool has_prefix;
+	u64 prefix_start = 0;
 
 	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,
+				  &has_prefix, &prefix_start);
+	if (symbols->sorted_cnt < symbols->cnt) {
+		struct symbol *tail_res;
+		bool has_tail;
+		u64 tail_start = 0;
+
+		tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
+					       symbols->cnt - symbols->sorted_cnt, ip,
+					       &has_tail, &tail_start);
+		if (has_tail) {
+			if (!has_prefix || tail_start > prefix_start)
+				res = tail_res;
+			else if (tail_start == prefix_start && !res)
+				res = tail_res;
+		}
+	}
 	up_read(&symbols->lock);
 
 	return res;
@@ -735,7 +1113,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 +1127,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 +1482,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 +1557,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 +1704,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 +1734,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);
tools/perf/util/symbol.h +10 -1
index adfb1a3a89be..ce7be4b18a11 100644
@@ -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
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#14 lore raw

Re: [PATCH v6 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion

Sashiko has reviewed this patch and found no issues.
Quoted 29 lines

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)
Quoted 1 line

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=6
maintainer
#15 lore raw

Re: [PATCH v6 6/9] perf symbol: Optimize symbol sorting with natural-run merge sort and binary insertion

In reply to Ian Rogers
Quoted 6 lines · Ian Rogers

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.

This makes sense.

Quoted 11 lines

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.

Probably the same comment as my previous one. Can we have the simple merge sort change first?

Thanks,
Namhyung

Quoted 631 lines

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)
---
 tools/perf/util/symbol.c | 433 +++++++++++++++++++++++++++++++++++++--
 tools/perf/util/symbol.h |  11 +-
 2 files changed, 423 insertions(+), 21 deletions(-)
tools/perf/util/symbol.c +413 -20
index f1e3d7af714c..84a8b3e4c528 100644
@@ -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 (symbols->cnt > 1) {
-		qsort(symbols->symbols, symbols->cnt, sizeof(struct symbol *),
-		      symbols__sort_cmp);
+	if (m > symbols->cnt)
+		m = 0;
+	k = symbols->cnt - m;
+
+	if (k == 0) {
+		symbols->sorted = true;
+		return;
+	}
+
+	/*
+	 * 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;
@@ -546,7 +892,9 @@ static inline bool symbol__covers(const struct symbol *s, u64 ip)
 	return ip >= start && (ip < end || (ip == end && ip == start));
 }
 
-static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt, u64 ip)
+static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
+					  u64 ip, bool *has_candidate,
+					  u64 *candidate_start)
 {
 	unsigned int low = 0, high = cnt, idx;
 	u64 start;
@@ -559,8 +907,10 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 		else
 			high = mid;
 	}
-	if (low == 0)
+	if (low == 0) {
+		*has_candidate = false;
 		return NULL;
+	}
 
 	/*
 	 * Rewind across any equal-start group so a trailing zero-length or
@@ -569,6 +919,8 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 	 */
 	idx = low - 1;
 	start = arr[idx]->start;
+	*has_candidate = true;
+	*candidate_start = start;
 	while (idx > 0 && arr[idx - 1]->start == start)
 		idx--;
 	for (; idx < low; idx++) {
@@ -585,12 +937,38 @@ static struct symbol *symbols__find_range(struct symbol **arr, unsigned int cnt,
 static struct symbol *symbols__find(struct symbols *symbols, u64 ip)
 {
 	struct symbol *res;
+	bool has_prefix;
+	u64 prefix_start = 0;
 
 	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,
+				  &has_prefix, &prefix_start);
+	if (symbols->sorted_cnt < symbols->cnt) {
+		struct symbol *tail_res;
+		bool has_tail;
+		u64 tail_start = 0;
+
+		tail_res = symbols__find_range(&symbols->symbols[symbols->sorted_cnt],
+					       symbols->cnt - symbols->sorted_cnt, ip,
+					       &has_tail, &tail_start);
+		if (has_tail) {
+			if (!has_prefix || tail_start > prefix_start)
+				res = tail_res;
+			else if (tail_start == prefix_start && !res)
+				res = tail_res;
+		}
+	}
 	up_read(&symbols->lock);
 
 	return res;
@@ -735,7 +1113,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 +1127,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 +1482,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 +1557,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 +1704,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 +1734,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);
tools/perf/util/symbol.h +10 -1
index adfb1a3a89be..ce7be4b18a11 100644
@@ -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
Signature · 1 line
2.56.1.703.gf848ed807c-goog
author reviewer
#16 lore raw

PATCH v6 7/9 perf symbol: Add memory shrinking for symbols, DSOs, and machines

In reply to Ian Rogers

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.

---
 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(-)
tools/perf/util/dso.c +280 -31
index 3d7db37ff095..0d205015c6dc 100644
@@ -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))
tools/perf/util/dso.h +12 -2
index f23cf9957aec..962e1ad0c463 100644
@@ -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);
tools/perf/util/dsos.c +50 -0

59 lines not on this page · raw message

tools/perf/util/dsos.h +2 -0
index a26774950866..151efdba2aa4 100644
@@ -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 */
tools/perf/util/machine.c +29 -0
index e8a3d8095346..60eed6ae3ba1 100644
@@ -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;
+}
tools/perf/util/machine.h +3 -0
index 80191545ee8a..0f4c0ae5b56d 100644
@@ -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 */
tools/perf/util/session.c +8 -0
index a58b4fe44b62..d5cb5e94a54a 100644
@@ -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);
+}
tools/perf/util/session.h +2 -0
index 05ea2c1ee8c9..cbea6792a008 100644
@@ -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 */
tools/perf/util/symbol.c +66 -1

92 lines not on this page · raw message

tools/perf/util/symbol.h +3 -0
index ce7be4b18a11..d70c01609017 100644
@@ -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)
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#17 lore raw

Re: [PATCH v6 7/9] perf symbol: Add memory shrinking for symbols, DSOs, and machines

Sashiko has reviewed this patch and found no issues.
Quoted 22 lines

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.

Quoted 7 lines

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.

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=7
author reviewer
#18 lore raw

PATCH v6 8/9 perf session: Add dso__session() and session-scoped allocation wrappers

In reply to Ian Rogers

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.

---
 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(+)
tools/perf/util/dso.c +7 -0
index 0d205015c6dc..ba070611c18a 100644
@@ -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;
tools/perf/util/dso.h +2 -0
index 962e1ad0c463..0991a5ab7c8d 100644
@@ -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);
 
tools/perf/util/dsos.c +1 -0
index 52d80219ac2f..343c79c7ee37 100644
@@ -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;
tools/perf/util/dsos.h +1 -0
index 151efdba2aa4..d636e4c5cbaf 100644
@@ -19,6 +19,7 @@ struct machine;
  */
 struct dsos {
 	struct rw_semaphore lock;
+	struct machine *machine;
 	struct dso **dsos;
 	unsigned int cnt;
 	unsigned int allocated;
tools/perf/util/machine.c +1 -0
index 60eed6ae3ba1..d3a93e8a4743 100644
@@ -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);
tools/perf/util/machine.h +5 -0
index 0f4c0ae5b56d..6192bd3e33bb 100644
@@ -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);
 
tools/perf/util/session.c +70 -0

73 lines not on this page · raw message

tools/perf/util/session.h +6 -0
index cbea6792a008..c6157eddcc43 100644
@@ -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 */
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#19 lore raw

Re: [PATCH v6 8/9] perf session: Add dso__session() and session-scoped allocation wrappers

Sashiko has reviewed this patch and found no issues.
Quoted 14 lines

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.

Quoted 5 lines

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.

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
author reviewer
#20 lore raw

PATCH v6 9/9 perf test symbols: Add tests for symbol shrinking and session alloc wrappers

In reply to Ian Rogers

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().

---
 tools/perf/tests/symbols.c | 779 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 768 insertions(+), 11 deletions(-)
tools/perf/tests/symbols.c +768 -11
index 1220f97b77bb..ed98b0caddc7 100644
@@ -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,271 @@ 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 dynamic symbols into the unmerged sorted tail and verify
+	 * lookups match merged-array semantics in all prefix/tail overlap and
+	 * equal-start cases:
+	 * - [0x0, 0x40) in prefix + [0x20, 0x30) in tail: 0x24 -> inner,
+	 *   0x34 -> NULL (closer tail start shadows outer prefix symbol).
+	 * - [0x100, 0x140) in prefix + [0x80, 0x180) in tail: 0x150 -> NULL
+	 *   (closer prefix start shadows outer tail symbol).
+	 * - [0x200, 0x240) in prefix + [0x200, 0x260) in tail: 0x250 -> alias
+	 *   (equal-start group spans prefix and tail).
+	 */
+	{
+		struct symbol *inner = symbol__new(0x20, 0x10, STB_GLOBAL, STT_FUNC,
+						   "inner_tail_sym");
+		struct symbol *outer = symbol__new(0x80, 0x100, STB_GLOBAL, STT_FUNC,
+						   "outer_tail_sym");
+		struct symbol *alias = symbol__new(0x200, 0x60, STB_GLOBAL, STT_FUNC,
+						   "longer_tail_alias");
+
+		if (!inner || dso__insert_symbol(dso, inner)) {
+			symbol__delete(outer);
+			symbol__delete(alias);
+			goto out;
+		}
+		if (!outer || dso__insert_symbol(dso, outer)) {
+			symbol__delete(alias);
+			goto out;
+		}
+		if (!alias || dso__insert_symbol(dso, alias))
+			goto out;
+		if (symbols->sorted_cnt >= symbols->cnt) {
+			pr_debug("Expected unmerged sorted tail!\n");
+			goto out;
+		}
+		if (dso__find_symbol(dso, 0x24) != inner ||
+		    dso__find_symbol(dso, 0x34) != NULL ||
+		    dso__find_symbol(dso, 0x150) != NULL ||
+		    dso__find_symbol(dso, 0x250) != alias) {
+			pr_debug("Unmerged tail lookup mismatch!\n");
+			goto out;
+		}
+		symbols__sort_read_lock(symbols);
+		up_read(&symbols->lock);
+		if (dso__find_symbol(dso, 0x24) != inner ||
+		    dso__find_symbol(dso, 0x34) != NULL ||
+		    dso__find_symbol(dso, 0x150) != NULL ||
+		    dso__find_symbol(dso, 0x250) != alias) {
+			pr_debug("Merged lookup mismatch!\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 +987,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 +1038,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 +1048,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))
Signature · 1 line
2.56.1.703.gf848ed807c-goog
#21 lore raw

Re: [PATCH v6 9/9] perf test symbols: Add tests for symbol shrinking and session alloc wrappers

Sashiko has reviewed this patch and found no issues.
Quoted 26 lines

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().

Quoted 1 line

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=9