Linux Perf Users
 help / color / mirror / Atom feed
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


  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