From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.199 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1795323862; b=185sK89/IXHN99AEq68z4ZvbvE1dBsofbH2D8IMxb2YGduUKtvAN331NlQo0bMXmKbsd oIz8+b8Zi8Ltla5mnSX5V2gBMQTCEKwcoKkYihmoGfEvqWHrAlRxE6GCG5t214AScnS+0 XOQinXlSlEkolQZ63BDBzswmfphspnfqL57t8jtecpK2IRCG9nXZPS51rzdPLQ/0JN86b wxmLCkp7mMKGrdPL4bML59qeP4O5+oiO1ItOtuH6ATmGpVKo4iKAlxd3rYNz5yJXoNp6z HhFMB+EyZq1/2RP7j7h1uNNBrJVWqvMe+yGwGVl/P3UwZqilKmt2CMstOfBlooDklXg== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1795323862; h=DMARC-Filter:Received:DKIM-Signature:X-Google-DKIM-Signature: X-Forwarded-Encrypted:X-Gm-Message-State:X-Received:Date:In-Reply-To: Mime-Version:References:X-Mailer:Message-ID:Subject:From:To:Cc: Content-Type; bh=3+RVnA1KvRuho7W5JEL26qwdJaS2/5G8Cho/yb352Tg=; b=qUd6kNivumVLvV8RIY3QY6yQpR57R9PnRa5N7RMt4SbECA0ioawO3zPdsWlRSgrGF8Ds NgbY9gcBCnSb5Vc2YbmhmZSdsQ7cx+ZCoUYbEIsNVOQhlqN0LawgQuaLDXo0THPd9gIRh EH1u7+m1nC62H4iDllxbS5g6vGIXXp+qVtJwQAHj1hEL2fTEjwqhZQsuqmSGXJy7z5GUR gtVFom+22RN01ovO45Q9H5he00F3yRAlxV2srx32qjSWsDfZ03kkrwbLGY5xDqwCrwjsh 3oH3Vy2hI2RoT57ihHBCC1Btm1hV8JT8RxfZTjama+h8uwdahQ43bPdPjC9shy1xENA== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass header.d=google.com header.i=@google.com header.a=rsa-sha256 header.s=20260707 header.b=pYIb4A2Y; arc=none smtp.remote-ip=74.125.82.199 Received: from mail-dy1-f199.google.com (mail-dy1-f199.google.com [74.125.82.199]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9CDE8606A330 for ; Sun, 22 Nov 2026 05:04:21 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 9CDE8606A330 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.a=rsa-sha256 header.s=20260707 header.b=pYIb4A2Y Received: by mail-dy1-f199.google.com with SMTP id 5a478bee46e88-33c35f5ca6cso3137856eec.1 for ; Sat, 21 Nov 2026 21:04:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20260707; t=1795323861; x=1795928661; darn=vger.kernel.org; h=content-type:cc:to:from:subject:message-id:references:mime-version :in-reply-to:date:from:to:cc:subject:date:message-id:reply-to :content-type; bh=3+RVnA1KvRuho7W5JEL26qwdJaS2/5G8Cho/yb352Tg=; b=pYIb4A2YDUgJW3/cv/didT2UkN8udEvUHytxfzEl1B31hB+GgmwXH8wJj0m6xuDi7J QqjMDwaqmJHnt8WG9tOMlnmIjy/9oSSL6mceZlFXp7ohjcVh4PXq3T168T4fTQvKEfcL Qy4mSVn/jYIB9ivzPzZX3t4rFPr6jIVP3CCug3whPKI6fFVWX7gTW9WMZOTtza2xqr0q vx0rPnzFum3cbzD2Q33o96As3JqNQtMLmI0vdRoePYEs3efQxhHju8imvklYLS8OAQy/ UkLoTXH0yHWkOJTa1DZFhCeJW6TiO+1Eizxj/g8/xbOLnlciLL9LQwrRb91Xkt5R103i RitQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1795323861; x=1795928661; h=content-type:cc:to:from:subject:message-id:references:mime-version :in-reply-to:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to:content-type; bh=3+RVnA1KvRuho7W5JEL26qwdJaS2/5G8Cho/yb352Tg=; b=T1rdq0QOtNY3qf1XLyl8oo1fBzLF+TTdGzfslyXmFnawtHWMEseCtBES0no+RbaTDw mMyeWmCFzsLuDRQidBwkfDaw12X1nR5hnL/gnonYo9QbEVjvWA7HdLof1VdkNQwLM2NR 515N1fKElqeLAUsynP3ANn4p0coOWc/ulySwEPVdCzKszkfzBoY/KECR3Jga2UcXRX3b jdCjGOCCWJCuhSkuOTLwnMXHKCEFh4ytFMpvygwXgCd7dbdwETK4YjgkXKIAwp+2wnRN OaT1Xc/PV+BbXRV28PATSYhHolC5sWSkf55CYM5jHiscy7965NbBpmWF9H9oPityWlpv 5fuA== X-Forwarded-Encrypted: i=1; AL+hErFgaHdrayp5j37ymN8VyeSFHFMTfpkZma6QROTTVzetayArwWEhuHYaA1L+E6TOPnEhBf0BBt4zsq9wkrQ=@vger.kernel.org X-Gm-Message-State: APuU4Z/lTofYDpsCU9hzzKnpTZXoV16evVhibfusK2+HakEzicggwyzi LVfvu/jEtXBn+wrw5hBb/r5jCdZIo2z2Gfup/IF9S7mxPt+6As2fEKN2aLdFlrGJvf6mViFwH5k xC4iaUY5Qxg== X-Received: from dycpv11.prod.google.com ([2002:a05:7300:de0b:b0:383:7418:1e01]) (user=irogers job=prod-delivery.src-stubby-dispatcher) by 2002:a05:7301:1884:b0:374:ba43:ae2e with SMTP id 5a478bee46e88-3856f65eccamr7554250eec.14.1795323860261; Sat, 21 Nov 2026 21:04:20 -0800 (PST) Date: Sat, 21 Nov 2026 21:03:57 -0800 In-Reply-To: <20261122050405.80335-1-irogers@google.com> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list Mime-Version: 1.0 References: <20261122050405.80335-1-irogers@google.com> X-Mailer: git-send-email 2.56.1.750.gf70dc682cf-goog Message-ID: <20261122050405.80335-3-irogers@google.com> Subject: [PATCH v8 02/10] perf maps: Add tail fast-path check in first_ending_after() From: Ian Rogers To: Namhyung Kim , Arnaldo Carvalho de Melo , Alireza Haghdoost , Ian Rogers Cc: Peter Zijlstra , Ingo Molnar , Jiri Olsa , Adrian Hunter , James Clark , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Type: text/plain; charset="UTF-8" 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 # Conflicts: # tools/perf/tests/maps.c --- 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 054e4fafef3f..7f48f944aa67 100644 --- a/tools/perf/tests/maps.c +++ b/tools/perf/tests/maps.c @@ -392,10 +392,56 @@ static int test__maps__remove(struct test_suite *t __maybe_unused, int subtest _ 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 remove interface", maps__remove), + 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 672c0ace5a00..770ce43a4ce3 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -907,6 +907,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