[PATCH v7 02/10] perf maps: Add tail fast-path check in first_ending_after()

From: Ian Rogers

Date: Sat Nov 21 2026 - 02:17:22 EST


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@xxxxxxxxxx>
---
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