From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.198 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1794941598; b=n9WbeeGeu9nl+4OpVafJMThv+mNdeaFdsKH6Cam1VDADpYdK+Oq3Td3GsITC4lo2F+sL +zobe+BU4s9agtXWD56l/LlB/eKr8KEsuFiVKYzALJi0HBu1ahY2g2UegYRiaxx2YvM7p UmWkSLRPbuGYUZaMmHNfllBVx4TbX39E0GIPRSlNiuRMpihHteengQM+YSyendzgRNgji /Wl2TFnb1fOtuF0XVCFUa1y7czPCsghG3YzcM9rXVBFOjKWnndUDI21xqFjElfpVPt25o eSokg0jVZzFtkxZR98PqgZi248NHfgh+ArQxn8G7u5/QJka/Fahw9/IXe2zjxUHrFIg== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1794941598; 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=HJDQxPYa0GAj7A61+fE8Awdi8wFHW3qKC9OAlJkGjcg=; b=bhX1oMY5TtpdPj8J81fN1w9cE3bY45qZ2IBywB8jzxOgwqeojc71CS7+caZpee8HyePb Uyw8ZuHq7iJsTK1mo20ACfkNgErJRtRDWKYJcG2HvvRo5zGh5HbIDPziv41NWglQhcsw3 Q7qZjbw4s7xeX8oT2jSVgdg4ojGejwaaU50ODYNi+labgowXEbviAEYpYVD71R7B3tILM BjxrWbVFr1zsImcDf1eTpazLETR4OTJw5wk/13eif1H3u2gvy/5RAjSoslC4pJxSkHO5U +yXcPfXx/eIkQjHBRQ3TaNvkdcjzSORg4onQwCfIP6ipxvi/ORBdHdcbZkQSObmceGQ== 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=hPcGfJ83; arc=none smtp.remote-ip=74.125.82.198 Received: from mail-dy1-f198.google.com (mail-dy1-f198.google.com [74.125.82.198]) (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 4BF27606A330 for ; Tue, 17 Nov 2026 18:53:18 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 4BF27606A330 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=hPcGfJ83 Received: by mail-dy1-f198.google.com with SMTP id 5a478bee46e88-38131260a5dso541176eec.0 for ; Tue, 17 Nov 2026 10:53:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20260707; t=1794941597; x=1795546397; 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=HJDQxPYa0GAj7A61+fE8Awdi8wFHW3qKC9OAlJkGjcg=; b=hPcGfJ837Amirn+JTQNpEo4sieT2EsKYc96n9PVaC0fhLqAcuu+6Txh7tuz4g5/KGw VuSPStaSxvjcfDVzWMkBp1EaN2LDDjd+YMBLIIoP8/G5wvgvmm6XqcV87nMqfOttys0x iUWPoOZ+UmwUwHrUa4aZRSl9jl92idNob9OncNNJ7itCqwZt270DHnONHZyogW6zI1Fo AP+UnDcTebP7nPLIR6dP/kfCyVhlXTUNUd/rqDhBOI5zfkJOWYv2xuHKOYi8L6RBF7mz g8hoUsYsH89p8HNOsGWzbY1cVZLgG7/+cjZuKyi1Z0NXEwGEDnpvtpf5eg3gLy3QKVga Eh/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1794941597; x=1795546397; 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=HJDQxPYa0GAj7A61+fE8Awdi8wFHW3qKC9OAlJkGjcg=; b=clh5tU/7AyYUrnxF5pZURv5KJor/G2RJ9CAsJ6yqP2iH1I7/NTKqnCII5EZ7TNloXR FivS8jNqp4N3CJxFfQNBntvajjey8yUPyXBuzUUh59W5M8RxkRsFX5At55NA5fs63UwB iYZ6OtioCkeYRSM/9OBl4c0pN9hkThUoT8ekExjxcAfRq7NR1XeB9KPA40e7ZSPPifI0 95VQ/HEBdaPapcnnp5qQv18lTWN2LdajM6i1Qmece5lWGMqqsOfaOTAscgRfsOpHmnWC mbmMIEOeAUPHitZ6u5TnxF/XT/9nCBENau7M021SGwp4x/ZZsbMG7m43NhJWw+I5BV74 Ys9A== X-Forwarded-Encrypted: i=1; AL+hErEhKMLcVl16ACsgv7uAV990xb4Iyz0sjIA0k0SdRSDglzds3RTTS5+Bi99szOL9ToX+QXe13Z5oyotufxQxolqx@vger.kernel.org X-Gm-Message-State: APuU4Z/nusHMQcOysokjzUAZi68F73wBgOocIFl+TJTAj3TbRT/bHwKU oXDVm7o6da5meHHI7d4o1zXvwln8neGyX8o4+vonAFLuLTB6jpVazXR+4QYccXhZ5tNLAxsENB6 uW8kmFxRxmg== X-Received: from dlbph19.prod.google.com ([2002:a05:7022:3713:b0:1b2:649c:7a14]) (user=irogers job=prod-delivery.src-stubby-dispatcher) by 2002:a05:7022:7e85:b0:1a6:7a2:cfc3 with SMTP id a92af1059eb24-1b543ce6b18mr478396c88.13.1794941596884; Tue, 17 Nov 2026 10:53:16 -0800 (PST) Date: Tue, 17 Nov 2026 10:53:00 -0800 In-Reply-To: <20261117185305.108003-1-irogers@google.com> X-Mailing-List: linux-perf-users@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list Mime-Version: 1.0 References: <20261117185305.108003-1-irogers@google.com> X-Mailer: git-send-email 2.56.1.703.gf848ed807c-goog Message-ID: <20261117185305.108003-5-irogers@google.com> Subject: [PATCH v6 4/9] perf maps: Optimize tail insertion and small-append sorting 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). Additionally, track the sorted prefix lengths (nr_addr_sorted and nr_name_sorted) in struct maps: - In __maps__sort_by_address() and maps__sort_by_name(), when the unsorted tail is small (k <= 8) or the total map count is small (n <= 64), binary-insert the newly appended maps into the sorted prefix instead of re-running qsort() over the entire array. This avoids O(N^2 log N) re-sorting when maps__find_by_name() is called repeatedly between single-map maps__insert() calls in dso__process_kernel_symbol() and dso__split_kallsyms(). - In maps__by_address_index() and maps__by_name_index(), binary-search the known-sorted prefix before scanning only the unsorted tail. - Add a unit test in tools/perf/tests/maps.c covering the tail fast-path and incremental binary-insertion sort. Using 'perf bench internals maps': Before: Average ascending insert + lookup: 63.370 usec (+- 0.476 usec) Average append + lookup: 7477.450 usec (+- 20.829 usec) After (-6.9% ascending, -98.7% append): Average ascending insert + lookup: 58.970 usec (+- 0.609 usec) Average append + lookup: 96.670 usec (+- 1.353 usec) Signed-off-by: Ian Rogers --- tools/perf/tests/maps.c | 67 ++++++++++ tools/perf/util/maps.c | 276 +++++++++++++++++++++++++++++++++------- 2 files changed, 294 insertions(+), 49 deletions(-) diff --git a/tools/perf/tests/maps.c b/tools/perf/tests/maps.c index ff6d25f9c043..04ab425f4a87 100644 --- a/tools/perf/tests/maps.c +++ b/tools/perf/tests/maps.c @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-2.0 #include #include +#include #include #include #include "debug.h" @@ -253,9 +254,75 @@ static int test__maps__fixup_overlap_and_insert(struct test_suite *t __maybe_unu return TEST_OK; } +static int test__maps__incremental_sort(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_def out_of_order = { "map_b", 3000, 4000 }; + struct map *map, *found; + struct perf_env host_env; + struct machine *machine; + struct maps *maps; + + 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); + } + + /* Populate maps_by_name and verify lookup. */ + found = maps__find_by_name(maps, "map_a"); + TEST_ASSERT_VAL("failed to find map_a by name", found && map__start(found) == 2000); + map__zput(found); + + /* Append out-of-order map via maps__insert and verify binary-insertion sort. */ + map = dso__new_map(out_of_order.name); + TEST_ASSERT_VAL("failed to create map_b", map); + map__set_start(map, out_of_order.start); + map__set_end(map, out_of_order.end); + TEST_ASSERT_VAL("failed to insert map_b", maps__insert(maps, map) == 0); + + found = maps__find(maps, 3500); + TEST_ASSERT_VAL("failed to find map_b by address", RC_CHK_EQUAL(found, map)); + map__zput(found); + + found = maps__find_by_name(maps, "map_b"); + TEST_ASSERT_VAL("failed to find map_b by name", RC_CHK_EQUAL(found, map)); + map__zput(found); + + maps__remove(maps, map); + map__zput(map); + + found = maps__find_by_name(maps, "map_d"); + TEST_ASSERT_VAL("failed to find map_d after removal", found && map__start(found) == 4000); + 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 incremental sort and tail insert", maps__incremental_sort), { .name = NULL, } }; diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 675fe0223faa..b420c2f2b72a 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-2.0 #include #include +#include #include #include "debug.h" #include "dso.h" @@ -56,6 +57,16 @@ DECLARE_RC_STRUCT(maps) { * maps_by_name. */ unsigned int nr_maps_allocated; + /** + * @nr_addr_sorted: number of leading entries in + * maps_by_address that are known to be sorted. + */ + unsigned int nr_addr_sorted; + /** + * @nr_name_sorted: number of leading entries in maps_by_name + * that are known to be sorted. + */ + unsigned int nr_name_sorted; /** * @last_search_by_name_idx: cache of last found by name entry's index * as frequent searches for the same dso name are common. @@ -72,8 +83,17 @@ DECLARE_RC_STRUCT(maps) { static void check_invariants(const struct maps *maps __maybe_unused) { #ifndef NDEBUG - assert(RC_CHK_ACCESS(maps)->nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated); - for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) { + unsigned int nr_maps = RC_CHK_ACCESS(maps)->nr_maps; + unsigned int nr_addr_sorted = RC_CHK_ACCESS(maps)->nr_addr_sorted; + unsigned int nr_name_sorted = RC_CHK_ACCESS(maps)->nr_name_sorted; + + assert(nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated); + assert(nr_addr_sorted <= nr_maps); + assert(!RC_CHK_ACCESS(maps)->maps_by_address_sorted || nr_addr_sorted == nr_maps); + assert(nr_name_sorted <= nr_maps); + assert(!RC_CHK_ACCESS(maps)->maps_by_name_sorted || nr_name_sorted == nr_maps); + + for (unsigned int i = 0; i < nr_maps; i++) { struct map *map = RC_CHK_ACCESS(maps)->maps_by_address[i]; /* Check map is well-formed. */ @@ -84,28 +104,25 @@ static void check_invariants(const struct maps *maps __maybe_unused) if (map__dso(map) && dso__kernel(map__dso(map))) assert(RC_CHK_EQUAL(map__kmap(map)->kmaps, maps)); - if (i > 0) { + if (i > 0 && i < nr_addr_sorted) { struct map *prev = RC_CHK_ACCESS(maps)->maps_by_address[i - 1]; - /* If addresses are sorted... */ - if (RC_CHK_ACCESS(maps)->maps_by_address_sorted) { - /* Maps should be in start address order. */ - assert(map__start(prev) <= map__start(map)); - /* - * If the ends of maps aren't broken (during - * construction) then they should be ordered - * too. - */ - if (!RC_CHK_ACCESS(maps)->ends_broken) { - assert(map__end(prev) <= map__end(map)); - assert(map__end(prev) <= map__start(map) || - map__start(prev) == map__start(map)); - } + /* Maps in sorted prefix should be in start address order. */ + assert(map__start(prev) <= map__start(map)); + /* + * If the ends of maps aren't broken (during + * construction) then they should be ordered + * too. + */ + if (!RC_CHK_ACCESS(maps)->ends_broken) { + assert(map__end(prev) <= map__end(map)); + assert(map__end(prev) <= map__start(map) || + map__start(prev) == map__start(map)); } } } if (RC_CHK_ACCESS(maps)->maps_by_name) { - for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) { + for (unsigned int i = 0; i < nr_maps; i++) { struct map *map = RC_CHK_ACCESS(maps)->maps_by_name[i]; /* @@ -137,6 +154,14 @@ static void maps__set_nr_maps_allocated(struct maps *maps, unsigned int nr_maps_ static void maps__set_nr_maps(struct maps *maps, unsigned int nr_maps) { RC_CHK_ACCESS(maps)->nr_maps = nr_maps; + if (RC_CHK_ACCESS(maps)->maps_by_address_sorted || + RC_CHK_ACCESS(maps)->nr_addr_sorted > nr_maps) { + RC_CHK_ACCESS(maps)->nr_addr_sorted = nr_maps; + } + if (RC_CHK_ACCESS(maps)->maps_by_name_sorted || + RC_CHK_ACCESS(maps)->nr_name_sorted > nr_maps) { + RC_CHK_ACCESS(maps)->nr_name_sorted = nr_maps; + } } /* Not in the header, to aid reference counting. */ @@ -160,6 +185,8 @@ static bool maps__maps_by_address_sorted(const struct maps *maps) static void maps__set_maps_by_address_sorted(struct maps *maps, bool value) { RC_CHK_ACCESS(maps)->maps_by_address_sorted = value; + if (value) + RC_CHK_ACCESS(maps)->nr_addr_sorted = maps__nr_maps(maps); } static bool maps__maps_by_name_sorted(const struct maps *maps) @@ -170,6 +197,8 @@ static bool maps__maps_by_name_sorted(const struct maps *maps) static void maps__set_maps_by_name_sorted(struct maps *maps, bool value) { RC_CHK_ACCESS(maps)->maps_by_name_sorted = value; + if (value) + RC_CHK_ACCESS(maps)->nr_name_sorted = maps__nr_maps(maps); } struct machine *maps__machine(const struct maps *maps) @@ -241,6 +270,8 @@ static void maps__init(struct maps *maps, struct machine *machine) refcount_set(maps__refcnt(maps), 1); RC_CHK_ACCESS(maps)->nr_maps = 0; RC_CHK_ACCESS(maps)->nr_maps_allocated = 0; + RC_CHK_ACCESS(maps)->nr_addr_sorted = 0; + RC_CHK_ACCESS(maps)->nr_name_sorted = 0; RC_CHK_ACCESS(maps)->last_search_by_name_idx = 0; RC_CHK_ACCESS(maps)->maps_by_address_sorted = true; RC_CHK_ACCESS(maps)->maps_by_name_sorted = false; @@ -313,6 +344,7 @@ static void __maps__free_maps_by_name(struct maps *maps) zfree(&RC_CHK_ACCESS(maps)->maps_by_name); /* Consistent with maps__init(). When maps_by_name == NULL, maps_by_name_sorted == false */ + RC_CHK_ACCESS(maps)->nr_name_sorted = 0; maps__set_maps_by_name_sorted(maps, false); } @@ -339,15 +371,54 @@ static int map__start_cmp(const void *a, const void *b) return map_a_start > map_b_start ? 1 : -1; } +static unsigned int maps__by_address_upper_bound(struct map **arr, unsigned int len, + const struct map *map) +{ + unsigned int low = 0, high = len; + + while (low < high) { + unsigned int mid = low + (high - low) / 2; + + if (map__start_cmp(&arr[mid], &map) <= 0) + low = mid + 1; + else + high = mid; + } + return low; +} + static void __maps__sort_by_address(struct maps *maps) { + struct map **maps_by_address; + unsigned int n, m, k; + if (maps__maps_by_address_sorted(maps)) return; - qsort(maps__maps_by_address(maps), - maps__nr_maps(maps), - sizeof(struct map *), - map__start_cmp); + maps_by_address = maps__maps_by_address(maps); + n = maps__nr_maps(maps); + m = RC_CHK_ACCESS(maps)->nr_addr_sorted; + if (m > n) + m = 0; + k = n - m; + + if (k <= 8 || n <= 64) { + for (unsigned int i = max(m, 1U); i < n; i++) { + struct map *map = maps_by_address[i]; + + if (map__start_cmp(&maps_by_address[i - 1], &map) > 0) { + unsigned int pos = + maps__by_address_upper_bound(maps_by_address, i, map); + + memmove(&maps_by_address[pos + 1], + &maps_by_address[pos], + (i - pos) * sizeof(*maps_by_address)); + maps_by_address[pos] = map; + } + } + } else { + qsort(maps_by_address, n, sizeof(struct map *), map__start_cmp); + } maps__set_maps_by_address_sorted(maps, true); } @@ -373,6 +444,22 @@ static int map__strcmp(const void *a, const void *b) return ret; } +static unsigned int maps__by_name_upper_bound(struct map **arr, unsigned int len, + const struct map *map) +{ + unsigned int low = 0, high = len; + + while (low < high) { + unsigned int mid = low + (high - low) / 2; + + if (map__strcmp(&arr[mid], &map) <= 0) + low = mid + 1; + else + high = mid; + } + return low; +} + static int maps__sort_by_name(struct maps *maps) { int err = 0; @@ -380,6 +467,7 @@ static int maps__sort_by_name(struct maps *maps) down_write(maps__lock(maps)); if (!maps__maps_by_name_sorted(maps)) { struct map **maps_by_name = maps__maps_by_name(maps); + unsigned int n = maps__nr_maps(maps); if (!maps_by_name) { maps_by_name = malloc(RC_CHK_ACCESS(maps)->nr_maps_allocated * @@ -388,18 +476,38 @@ static int maps__sort_by_name(struct maps *maps) err = -ENOMEM; else { struct map **maps_by_address = maps__maps_by_address(maps); - unsigned int n = maps__nr_maps(maps); maps__set_maps_by_name(maps, maps_by_name); for (unsigned int i = 0; i < n; i++) maps_by_name[i] = map__get(maps_by_address[i]); + RC_CHK_ACCESS(maps)->nr_name_sorted = 0; } } if (!err) { - qsort(maps_by_name, - maps__nr_maps(maps), - sizeof(struct map *), - map__strcmp); + unsigned int m = RC_CHK_ACCESS(maps)->nr_name_sorted; + unsigned int k; + + if (m > n) + m = 0; + k = n - m; + if (k <= 8 || n <= 64) { + for (unsigned int i = max(m, 1U); i < n; i++) { + struct map *map = maps_by_name[i]; + + if (map__strcmp(&maps_by_name[i - 1], &map) > 0) { + unsigned int pos = + maps__by_name_upper_bound(maps_by_name, + i, map); + + memmove(&maps_by_name[pos + 1], + &maps_by_name[pos], + (i - pos) * sizeof(*maps_by_name)); + maps_by_name[pos] = map; + } + } + } else { + qsort(maps_by_name, n, sizeof(struct map *), map__strcmp); + } maps__set_maps_by_name_sorted(maps, true); } } @@ -411,19 +519,27 @@ static int maps__sort_by_name(struct maps *maps) static unsigned int maps__by_address_index(const struct maps *maps, const struct map *map) { struct map **maps_by_address = maps__maps_by_address(maps); + unsigned int nr_sorted = RC_CHK_ACCESS(maps)->nr_addr_sorted; + unsigned int nr_maps = maps__nr_maps(maps); - if (maps__maps_by_address_sorted(maps)) { + if (nr_sorted > nr_maps) + nr_sorted = 0; + + if (nr_sorted > 0) { struct map **mapp = - bsearch(&map, maps__maps_by_address(maps), maps__nr_maps(maps), + bsearch(&map, maps_by_address, nr_sorted, sizeof(*mapp), map__start_cmp); if (mapp) return mapp - maps_by_address; - } else { - for (unsigned int i = 0; i < maps__nr_maps(maps); i++) { - if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map)) - return i; - } + } + for (unsigned int i = nr_sorted; i < nr_maps; i++) { + if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map)) + return i; + } + for (unsigned int i = 0; i < nr_sorted; i++) { + if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map)) + return i; } pr_err("Map missing from maps"); return -1; @@ -432,19 +548,27 @@ static unsigned int maps__by_address_index(const struct maps *maps, const struct static unsigned int maps__by_name_index(const struct maps *maps, const struct map *map) { struct map **maps_by_name = maps__maps_by_name(maps); + unsigned int nr_sorted = RC_CHK_ACCESS(maps)->nr_name_sorted; + unsigned int nr_maps = maps__nr_maps(maps); - if (maps__maps_by_name_sorted(maps)) { + if (nr_sorted > nr_maps) + nr_sorted = 0; + + if (nr_sorted > 0) { struct map **mapp = - bsearch(&map, maps_by_name, maps__nr_maps(maps), + bsearch(&map, maps_by_name, nr_sorted, sizeof(*mapp), map__strcmp); if (mapp) return mapp - maps_by_name; - } else { - for (unsigned int i = 0; i < maps__nr_maps(maps); i++) { - if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map)) - return i; - } + } + for (unsigned int i = nr_sorted; i < nr_maps; i++) { + if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map)) + return i; + } + for (unsigned int i = 0; i < nr_sorted; i++) { + if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map)) + return i; } pr_err("Map missing from maps"); return -1; @@ -521,7 +645,10 @@ static int __maps__insert(struct maps *maps, struct map *new) maps__maps_by_address_sorted(maps) && map__end(maps_by_address[nr_maps - 2]) <= map__start(new) && map__start_cmp(&maps_by_address[nr_maps - 2], &new) <= 0); - maps__set_maps_by_name_sorted(maps, false); + maps__set_maps_by_name_sorted(maps, + maps_by_name && + maps__maps_by_name_sorted(maps) && + map__strcmp(&maps_by_name[nr_maps - 2], &new) <= 0); } if (map__end(new) < map__start(new)) RC_CHK_ACCESS(maps)->ends_broken = true; @@ -553,6 +680,8 @@ static void __maps__remove(struct maps *maps, struct map *map) memmove(&maps_by_address[address_idx], &maps_by_address[address_idx + 1], (nr_maps - address_idx - 1) * sizeof(*maps_by_address)); + if (address_idx < RC_CHK_ACCESS(maps)->nr_addr_sorted) + --RC_CHK_ACCESS(maps)->nr_addr_sorted; if (maps_by_name) { unsigned int name_idx = maps__by_name_index(maps, map); @@ -561,9 +690,16 @@ static void __maps__remove(struct maps *maps, struct map *map) memmove(&maps_by_name[name_idx], &maps_by_name[name_idx + 1], (nr_maps - name_idx - 1) * sizeof(*maps_by_name)); + if (name_idx < RC_CHK_ACCESS(maps)->nr_name_sorted) + --RC_CHK_ACCESS(maps)->nr_name_sorted; } - --RC_CHK_ACCESS(maps)->nr_maps; + --nr_maps; + RC_CHK_ACCESS(maps)->nr_maps = nr_maps; + if (RC_CHK_ACCESS(maps)->nr_addr_sorted == nr_maps) + RC_CHK_ACCESS(maps)->maps_by_address_sorted = true; + if (maps_by_name && RC_CHK_ACCESS(maps)->nr_name_sorted == nr_maps) + RC_CHK_ACCESS(maps)->maps_by_name_sorted = true; } void maps__remove(struct maps *maps, struct map *map) @@ -604,7 +740,9 @@ int maps__mutate_mapping(struct maps *maps, struct map *map, err = mutate_cb(map, data); + RC_CHK_ACCESS(maps)->nr_addr_sorted = 0; RC_CHK_ACCESS(maps)->maps_by_address_sorted = false; + RC_CHK_ACCESS(maps)->nr_name_sorted = 0; RC_CHK_ACCESS(maps)->maps_by_name_sorted = false; up_write(maps__lock(maps)); @@ -858,6 +996,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; @@ -925,7 +1067,17 @@ static int __maps__insert_sorted(struct maps *maps, unsigned int first_after_ind maps_by_name[nr_maps + 1] = map__get(new2); } RC_CHK_ACCESS(maps)->nr_maps = nr_maps + to_add; - maps__set_maps_by_name_sorted(maps, false); + RC_CHK_ACCESS(maps)->nr_addr_sorted = nr_maps + to_add; + if (maps_by_name) { + if (nr_maps == 0 && to_add == 1) { + maps__set_maps_by_name_sorted(maps, true); + } else { + maps__set_maps_by_name_sorted(maps, + maps__maps_by_name_sorted(maps) && + map__strcmp(&maps_by_name[nr_maps - 1], &new1) <= 0 && + (!new2 || map__strcmp(&new1, &new2) <= 0)); + } + } map__set_kmap_maps(new1, maps); map__set_kmap_maps(new2, maps); @@ -1049,9 +1201,16 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) map__set_kmap_maps(new, maps); if (maps_by_name) { + unsigned int nr_maps = maps__nr_maps(maps); + map__put(maps_by_name[ni]); - maps_by_name[ni] = map__get(new); - maps__set_maps_by_name_sorted(maps, false); + memmove(&maps_by_name[ni], + &maps_by_name[ni + 1], + (nr_maps - ni - 1) * sizeof(*maps_by_name)); + maps_by_name[nr_maps - 1] = map__get(new); + if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted) + --RC_CHK_ACCESS(maps)->nr_name_sorted; + maps__set_maps_by_name_sorted(maps, nr_maps <= 1); } err = __maps__insert_sorted(maps, i + 1, after, NULL); @@ -1077,8 +1236,13 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) if (maps_by_name) { map__put(maps_by_name[ni]); - maps_by_name[ni] = map__get(new); - maps__set_maps_by_name_sorted(maps, false); + memmove(&maps_by_name[ni], + &maps_by_name[ni + 1], + (nr_maps - ni - 1) * sizeof(*maps_by_name)); + maps_by_name[nr_maps - 1] = map__get(new); + if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted) + --RC_CHK_ACCESS(maps)->nr_name_sorted; + maps__set_maps_by_name_sorted(maps, nr_maps <= 1); } check_invariants(maps); @@ -1094,14 +1258,20 @@ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) memmove(&maps_by_address[i], &maps_by_address[i + 1], (nr_maps - i - 1) * sizeof(*maps_by_address)); + --RC_CHK_ACCESS(maps)->nr_addr_sorted; if (maps_by_name) { map__put(maps_by_name[ni]); memmove(&maps_by_name[ni], &maps_by_name[ni + 1], (nr_maps - ni - 1) * sizeof(*maps_by_name)); + if (ni < RC_CHK_ACCESS(maps)->nr_name_sorted) + --RC_CHK_ACCESS(maps)->nr_name_sorted; } --RC_CHK_ACCESS(maps)->nr_maps; + if (maps_by_name && + RC_CHK_ACCESS(maps)->nr_name_sorted == RC_CHK_ACCESS(maps)->nr_maps) + RC_CHK_ACCESS(maps)->maps_by_name_sorted = true; check_invariants(maps); /* * Maps are ordered but no need to increase `i` as the @@ -1181,9 +1351,17 @@ int maps__copy_from(struct maps *dest, struct maps *parent) if (err) map__put(new); } - maps__set_maps_by_address_sorted(dest, maps__maps_by_address_sorted(parent)); + if (maps__maps_by_address_sorted(parent)) { + maps__set_maps_by_address_sorted(dest, true); + } else { + RC_CHK_ACCESS(dest)->nr_addr_sorted = + min(RC_CHK_ACCESS(parent)->nr_addr_sorted, + RC_CHK_ACCESS(dest)->nr_maps); + maps__set_maps_by_address_sorted(dest, false); + } RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0; /* Values were copied into the name array in address order. */ + RC_CHK_ACCESS(dest)->nr_name_sorted = 0; maps__set_maps_by_name_sorted(dest, false); } else { /* Unexpected copying to a maps containing entries. */ -- 2.56.1.703.gf848ed807c-goog