From: Ian Rogers <irogers@google.com>
To: Namhyung Kim <namhyung@kernel.org>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Alireza Haghdoost <haghdoost@uber.com>,
Ian Rogers <irogers@google.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>, Jiri Olsa <jolsa@kernel.org>,
Adrian Hunter <adrian.hunter@intel.com>,
James Clark <james.clark@linaro.org>,
linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after()
Date: Fri, 20 Nov 2026 23:16:43 -0800 [thread overview]
Message-ID: <20261121071651.67118-3-irogers@google.com> (raw)
In-Reply-To: <20261121071651.67118-1-irogers@google.com>
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), and add a unit test in tools/perf/tests/maps.c
covering ascending tail insertions.
Using 'perf bench internals maps':
Before:
Average ascending insert + lookup: 63.370 usec (+- 0.476 usec)
After (-6.9%):
Average ascending insert + lookup: 58.970 usec (+- 0.609 usec)
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/perf/tests/maps.c | 46 +++++++++++++++++++++++++++++++++++++++++
tools/perf/util/maps.c | 4 ++++
2 files changed, 50 insertions(+)
diff --git a/tools/perf/tests/maps.c b/tools/perf/tests/maps.c
index ff6d25f9c043..3e8418ec6100 100644
--- a/tools/perf/tests/maps.c
+++ b/tools/perf/tests/maps.c
@@ -253,9 +253,55 @@ static int test__maps__fixup_overlap_and_insert(struct test_suite *t __maybe_unu
return TEST_OK;
}
+static int test__maps__tail_insert(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 *map, *found;
+ struct perf_env host_env;
+ struct machine *machine;
+ struct maps *maps;
+ int ret;
+
+ 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);
+ }
+
+ ret = check_maps(ascending_maps, ARRAY_SIZE(ascending_maps), maps);
+ TEST_ASSERT_VAL("tail insert check_maps failed", !ret);
+
+ found = maps__find(maps, 2500);
+ TEST_ASSERT_VAL("failed to find map_a by address", found && map__start(found) == 2000);
+ 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 tail insert fast-path", maps__tail_insert),
{ .name = NULL, }
};
diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c
index 675fe0223faa..dd3b27b568da 100644
--- a/tools/perf/util/maps.c
+++ b/tools/perf/util/maps.c
@@ -858,6 +858,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;
--
2.56.1.750.gf70dc682cf-goog
next prev parent reply other threads:[~2026-11-21 7:17 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-21 7:16 [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking Ian Rogers
2026-11-21 7:16 ` [PATCH v7 01/10] perf kmem: Fix alloc_func_regex leak on error in build_alloc_func_list() Ian Rogers
2026-11-21 7:16 ` Ian Rogers [this message]
2026-11-21 7:16 ` [PATCH v7 03/10] perf symbol: Convert map__for_each_symbol() to callback-based iteration Ian Rogers
2026-11-21 7:16 ` [PATCH v7 04/10] perf symbol: Use callback iteration instead of open-coded symbol loops Ian Rogers
2026-11-21 7:16 ` [PATCH v7 05/10] perf symbol: Switch backing storage from rbtree to struct symbols array Ian Rogers
2026-11-21 7:16 ` [PATCH v7 06/10] perf symbol: Replace qsort() with natural-run merge sort Ian Rogers
2026-11-21 7:16 ` [PATCH v7 07/10] perf symbol: Optimize incremental symbol insertion with sorted tail Ian Rogers
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261121071651.67118-3-irogers@google.com \
--to=irogers@google.com \
--cc=acme@kernel.org \
--cc=adrian.hunter@intel.com \
--cc=haghdoost@uber.com \
--cc=james.clark@linaro.org \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=namhyung@kernel.org \
--cc=peterz@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.