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: 13+ 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:26 ` sashiko-bot
2026-11-21 7:16 ` [PATCH v7 08/10] perf symbol: Add memory shrinking for symbols, DSOs, and machines Ian Rogers
2026-11-21 7:16 ` [PATCH v7 09/10] perf session: Add dso__session() and session-scoped allocation wrappers Ian Rogers
2026-11-21 7:16 ` [PATCH v7 10/10] perf test symbols: Add tests for symbol shrinking and session alloc wrappers Ian Rogers
2026-11-21 7:35 ` [PATCH v7 00/10] perf symbol: Sorted arrays, DSO-owned lifetimes, and memory shrinking sashiko-bot
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261121071651.67118-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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox