From patchwork Wed Feb 7 22:36:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198106 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546551dyb; Wed, 7 Feb 2024 14:39:16 -0800 (PST) X-Google-Smtp-Source: AGHT+IEnMEg3myM7OWhEBfCdPU810IVf3/sBvVlSOqPJumHasz9GmtFJ5lvjzmvdE0t6UjRag9lO X-Received: by 2002:a05:6402:31f4:b0:55f:18fa:eb59 with SMTP id dy20-20020a05640231f400b0055f18faeb59mr732766edb.16.1707345556059; Wed, 07 Feb 2024 14:39:16 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345556; cv=pass; d=google.com; s=arc-20160816; b=YR1dt/o3tAbHufw9w2OA+2iw2YWSuOzbFx/zNTeAQLI8QFpefUnol7GvMTes+IH518 kN6qXFo1gHRKyomP5bEK6/BuHoZ8T+p8QqcJkCD74lX+yQFMiW2bYBl1xJkTRKNTCy0M 2uBXbnWycS5swwj4oDRmpY8eU+WU/6Gmwcarchm1wQJu3xerkbRk6xd7lcOf7Sr2IQTg Wz+8z+qQ9ZI+eQPu30Nx7mVxbt7Iy/u49Es4Q1veU32B7xAlKM01dz8Zk1d2v+nuoMml BItUTkn9CaeJonbjqo2PVBg/pIkN2VcOvPsuR5uVx3LW/v0YdCDpNwPj2xnQ/FbpcpJN P8OA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=Pyb7akL26WerQt/5lhyRpEs3zSD28tdMAyz8zouDRew=; fh=em0hjNsUEoHJ68lhSGLhxyr/xwQuNz/uIHboOY5/0Rs=; b=orSePjLieJKBW7m6bT1HBX8/KTAdsgES7AhSAoUAnXxYiRPS3cofMuTZc47oEVvUVo KtUHwAx8K9lH8m/AIVlflW8R3wnSbB/SxRsx9lSl4REza8IEs4SVX+ntVaFRHyOKjE2u 02yH0a5n7qHgprJDEwCSAK9JHzlEZltQbSpJ1DxAwaf3oe8E02ZTduIkO8bofwtGkCx0 IWFZwTBgizjU9O7WpGlqf869HwiNWSIFMNqnuO1HodYEi2mF403EjsvxrjYtrCu0AFzH IfJUHoA0Qy7UYGeOOdCvgTPTiO5/LGAEaeP6/W/ur5o+acWACP5GGiNKzwOjNqWjRTM3 MG8Q==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="ztpVG2/C"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57260-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57260-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCV0JnK68CgEG66mA80NFtzquSnJvw/ZZKZuzidVlgnmQEakzjKrnkzYr+PWHvb+kzhrpqEBM9w0S6LnLp3GArOFQcBohw== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id t30-20020a50d71e000000b0055f1d367f12si187414edi.1.2024.02.07.14.39.15 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:39:16 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57260-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="ztpVG2/C"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57260-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57260-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id 1BEDD1F24FF3 for ; Wed, 7 Feb 2024 22:39:15 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id AB6636A8B5; Wed, 7 Feb 2024 22:37:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="ztpVG2/C" Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 59DAB1D54C for ; Wed, 7 Feb 2024 22:37:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345432; cv=none; b=f4FG+BorCGXHre7r8bv3X2GmW97pWbPUEqpGlXWe4cy//hHeZ/DpaMMuUW89AvdUO8zZ7oq0JIRa9l6cGJJWnrsZqUg/uWY8vSHAfXT2AqP6YOS166jcAMLcb6l8gjEnEm35+08UDLnkjph3FrH01th4qx/Yk+grq3eBhVeIGAM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345432; c=relaxed/simple; bh=Bz3BLNgV+pxdioqFlWJupgjErvAt9IkoS619A9vJWOQ=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=pCoDsabfS7Rhrb/7hCbl4mTXsRItGsKLac2g4rDKM2+RDCCRi7acT6xoHWX9pvMHI5HsGgyyCC1xku9Dyy/YCBD50eUw16mXJnOVq3WJi3MIXfI1skUkI6myCb0vGVMxUq5s5lFpLeaTAtzyFPO5dyR3rWQvTgtDhW3iDALunxA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=ztpVG2/C; arc=none smtp.client-ip=209.85.219.201 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 Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dc7165d7ca3so1724319276.2 for ; Wed, 07 Feb 2024 14:37:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345428; x=1707950228; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=Pyb7akL26WerQt/5lhyRpEs3zSD28tdMAyz8zouDRew=; b=ztpVG2/CVLzlaIIv3C3X+CXYBoq4Hr5UfLGUceOuI1qcKFSQ5JPb3s4C1yruJXoAwZ 5uYEHWRSyJpkdifohm8PJkPIf/lr6K0+qHNPlTUMra8CBL/nHCR9DyjwpY9Duy6Gsclx AwsWZH5cS3m40ltSpj115j2BqR6v5uUbV+tJOGMxTl73yuLdlVEWajb4sDh7xi/lJoyH 6L5yk/0zSLQi4CqdcIczzUHRvjBaIhaqse39Rr66c4EUw/on5v39RffCekzGFc5eVWBg S++a6CxpghuDm2hm3LOf1X1lCldnbXpxEG1ona7o2Vs1YD96ZF74w8GXWc4sMN8eUcaT 6YCQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345428; x=1707950228; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=Pyb7akL26WerQt/5lhyRpEs3zSD28tdMAyz8zouDRew=; b=YIY6RW1UtJqTfburblLlWCxh706987CutjKtK1zoKV+O7TOFZXetRwLnUJdFaxqyb/ PjBb2qPCZ7mfzN/Fo80jF/iKIhaVZE4zcvG8bOYna/34wR7ufvnOVpQZW/21u917l0Mv jLsg9OoHCSc0rB/vixjh4rPOO8u2/ps7o2kNcUk8RDSl8KcReXKaRaid9u0G/2e/MzAi 8P+JjeBFRm/pUKetjDOtvDvHZVNJkZmW1cHxQlq1sql6C7bfQLFABRlazCByn/G08ljU kv7mfWoRZ4nFEifZcepNMCft5CEauVqeBPfsteRbjscRLX/a/3riPJxOcpNjS1YlHoNm 6+mA== X-Gm-Message-State: AOJu0YzPKJFKSYyxDkPNNkKCrxiKppTlyU7+X6kJycNZhKsnjylP5QlC JcgSkMJAonaDhF4o6+bKymsXWpfsXGgIeU+HXcR+Vgi8Zsc8VgsJSdMwHuecaDpngEpi4cDvp+D afExBtg== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a25:aab1:0:b0:dc7:331e:1ade with SMTP id t46-20020a25aab1000000b00dc7331e1ademr116035ybi.3.1707345428273; Wed, 07 Feb 2024 14:37:08 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:34 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-2-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 1/6] perf maps: Switch from rbtree to lazily sorted array for addresses From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281573734708680 X-GMAIL-MSGID: 1790281573734708680 Maps is a collection of maps primarily sorted by the starting address of the map. Prior to this change the maps were held in an rbtree requiring 4 pointers per node. Prior to reference count checking, the rbnode was embedded in the map so 3 pointers per node were necessary. This change switches the rbtree to an array lazily sorted by address, much as the array sorting nodes by name. 1 pointer is needed per node, but to avoid excessive resizing the backing array may be twice the number of used elements. Meaning the memory overhead is roughly half that of the rbtree. For a perf record with "--no-bpf-event -g -a" of true, the memory overhead of perf inject is reduce fom 3.3MB to 3MB, so 10% or 300KB is saved. Map inserts always happen at the end of the array. The code tracks whether the insertion violates the sorting property. O(log n) rb-tree complexity is switched to O(1). Remove slides the array, so O(log n) rb-tree complexity is degraded to O(n). A find may need to sort the array using qsort which is O(n*log n), but in general the maps should be sorted and so average performance should be O(log n) as with the rbtree. An rbtree node consumes a cache line, but with the array 4 nodes fit on a cache line. Iteration is simplified to scanning an array rather than pointer chasing. Overall it is expected the performance after the change should be comparable to before, but with half of the memory consumed. To avoid a list and repeated logic around splitting maps, maps__merge_in is rewritten in terms of maps__fixup_overlap_and_insert. maps_merge_in splits the given mapping inserting remaining gaps. maps__fixup_overlap_and_insert splits the existing mappings, then adds the incoming mapping. By adding the new mapping first, then re-inserting the existing mappings the splitting behavior matches. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/tests/maps.c | 3 + tools/perf/util/map.c | 1 + tools/perf/util/maps.c | 1197 +++++++++++++++++++++++---------------- tools/perf/util/maps.h | 54 +- 4 files changed, 771 insertions(+), 484 deletions(-) diff --git a/tools/perf/tests/maps.c b/tools/perf/tests/maps.c index bb3fbfe5a73e..b15417a0d617 100644 --- a/tools/perf/tests/maps.c +++ b/tools/perf/tests/maps.c @@ -156,6 +156,9 @@ static int test__maps__merge_in(struct test_suite *t __maybe_unused, int subtest TEST_ASSERT_VAL("merge check failed", !ret); maps__zput(maps); + map__zput(map_kcore1); + map__zput(map_kcore2); + map__zput(map_kcore3); return TEST_OK; } diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c index 54c67cb7ecef..cf5a15db3a1f 100644 --- a/tools/perf/util/map.c +++ b/tools/perf/util/map.c @@ -168,6 +168,7 @@ struct map *map__new(struct machine *machine, u64 start, u64 len, if (dso == NULL) goto out_delete; + assert(!dso->kernel); map__init(result, start, start + len, pgoff, dso); if (anon || no_dso) { diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 0334fc18d9c6..45da1ec3630c 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -10,286 +10,490 @@ #include "ui/ui.h" #include "unwind.h" -struct map_rb_node { - struct rb_node rb_node; - struct map *map; -}; - -#define maps__for_each_entry(maps, map) \ - for (map = maps__first(maps); map; map = map_rb_node__next(map)) +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++) { + struct map *map = RC_CHK_ACCESS(maps)->maps_by_address[i]; + + /* Check map is well-formed. */ + assert(map__end(map) == 0 || map__start(map) <= map__end(map)); + /* Expect at least 1 reference count. */ + assert(refcount_read(map__refcnt(map)) > 0); + + if (map__dso(map) && map__dso(map)->kernel) + assert(RC_CHK_EQUAL(map__kmap(map)->kmaps, maps)); + + if (i > 0) { + 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)); + } + } + } + } + if (RC_CHK_ACCESS(maps)->maps_by_name) { + for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) { + struct map *map = RC_CHK_ACCESS(maps)->maps_by_name[i]; -#define maps__for_each_entry_safe(maps, map, next) \ - for (map = maps__first(maps), next = map_rb_node__next(map); map; \ - map = next, next = map_rb_node__next(map)) + /* + * Maps by name maps should be in maps_by_address, so + * the reference count should be higher. + */ + assert(refcount_read(map__refcnt(map)) > 1); + } + } +#endif +} -static struct rb_root *maps__entries(struct maps *maps) +static struct map **maps__maps_by_address(const struct maps *maps) { - return &RC_CHK_ACCESS(maps)->entries; + return RC_CHK_ACCESS(maps)->maps_by_address; } -static struct rw_semaphore *maps__lock(struct maps *maps) +static void maps__set_maps_by_address(struct maps *maps, struct map **new) { - return &RC_CHK_ACCESS(maps)->lock; + RC_CHK_ACCESS(maps)->maps_by_address = new; + } -static struct map **maps__maps_by_name(struct maps *maps) +static struct map ***maps__maps_by_name_addr(struct maps *maps) { - return RC_CHK_ACCESS(maps)->maps_by_name; + return &RC_CHK_ACCESS(maps)->maps_by_name; } -static struct map_rb_node *maps__first(struct maps *maps) +static void maps__set_nr_maps_allocated(struct maps *maps, unsigned int nr_maps_allocated) { - struct rb_node *first = rb_first(maps__entries(maps)); + RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_maps_allocated; +} - if (first) - return rb_entry(first, struct map_rb_node, rb_node); - return NULL; +static void maps__set_nr_maps(struct maps *maps, unsigned int nr_maps) +{ + RC_CHK_ACCESS(maps)->nr_maps = nr_maps; } -static struct map_rb_node *map_rb_node__next(struct map_rb_node *node) +/* Not in the header, to aid reference counting. */ +static struct map **maps__maps_by_name(const struct maps *maps) { - struct rb_node *next; + return RC_CHK_ACCESS(maps)->maps_by_name; - if (!node) - return NULL; +} - next = rb_next(&node->rb_node); +static void maps__set_maps_by_name(struct maps *maps, struct map **new) +{ + RC_CHK_ACCESS(maps)->maps_by_name = new; - if (!next) - return NULL; +} - return rb_entry(next, struct map_rb_node, rb_node); +static bool maps__maps_by_address_sorted(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->maps_by_address_sorted; } -static struct map_rb_node *maps__find_node(struct maps *maps, struct map *map) +static void maps__set_maps_by_address_sorted(struct maps *maps, bool value) { - struct map_rb_node *rb_node; + RC_CHK_ACCESS(maps)->maps_by_address_sorted = value; +} - maps__for_each_entry(maps, rb_node) { - if (rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map)) - return rb_node; - } - return NULL; +static bool maps__maps_by_name_sorted(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->maps_by_name_sorted; } -static void maps__init(struct maps *maps, struct machine *machine) +static void maps__set_maps_by_name_sorted(struct maps *maps, bool value) { - refcount_set(maps__refcnt(maps), 1); - init_rwsem(maps__lock(maps)); - RC_CHK_ACCESS(maps)->entries = RB_ROOT; - RC_CHK_ACCESS(maps)->machine = machine; - RC_CHK_ACCESS(maps)->last_search_by_name = NULL; - RC_CHK_ACCESS(maps)->nr_maps = 0; - RC_CHK_ACCESS(maps)->maps_by_name = NULL; + RC_CHK_ACCESS(maps)->maps_by_name_sorted = value; } -static void __maps__free_maps_by_name(struct maps *maps) +static struct rw_semaphore *maps__lock(struct maps *maps) { /* - * Free everything to try to do it from the rbtree in the next search + * When the lock is acquired or released the maps invariants should + * hold. */ - for (unsigned int i = 0; i < maps__nr_maps(maps); i++) - map__put(maps__maps_by_name(maps)[i]); + check_invariants(maps); + return &RC_CHK_ACCESS(maps)->lock; +} - zfree(&RC_CHK_ACCESS(maps)->maps_by_name); +static void maps__init(struct maps *maps, struct machine *machine) +{ + init_rwsem(maps__lock(maps)); + RC_CHK_ACCESS(maps)->maps_by_address = NULL; + RC_CHK_ACCESS(maps)->maps_by_name = NULL; + RC_CHK_ACCESS(maps)->machine = machine; +#ifdef HAVE_LIBUNWIND_SUPPORT + RC_CHK_ACCESS(maps)->addr_space = NULL; + RC_CHK_ACCESS(maps)->unwind_libunwind_ops = NULL; +#endif + 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)->last_search_by_name_idx = 0; + RC_CHK_ACCESS(maps)->maps_by_address_sorted = true; + RC_CHK_ACCESS(maps)->maps_by_name_sorted = false; } -static int __maps__insert(struct maps *maps, struct map *map) +static void maps__exit(struct maps *maps) { - struct rb_node **p = &maps__entries(maps)->rb_node; - struct rb_node *parent = NULL; - const u64 ip = map__start(map); - struct map_rb_node *m, *new_rb_node; + struct map **maps_by_address = maps__maps_by_address(maps); + struct map **maps_by_name = maps__maps_by_name(maps); - new_rb_node = malloc(sizeof(*new_rb_node)); - if (!new_rb_node) - return -ENOMEM; + for (unsigned int i = 0; i < maps__nr_maps(maps); i++) { + map__zput(maps_by_address[i]); + if (maps_by_name) + map__zput(maps_by_name[i]); + } + zfree(&maps_by_address); + zfree(&maps_by_name); + unwind__finish_access(maps); +} - RB_CLEAR_NODE(&new_rb_node->rb_node); - new_rb_node->map = map__get(map); +struct maps *maps__new(struct machine *machine) +{ + struct maps *result; + RC_STRUCT(maps) *maps = zalloc(sizeof(*maps)); - while (*p != NULL) { - parent = *p; - m = rb_entry(parent, struct map_rb_node, rb_node); - if (ip < map__start(m->map)) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } + if (ADD_RC_CHK(result, maps)) + maps__init(result, machine); - rb_link_node(&new_rb_node->rb_node, parent, p); - rb_insert_color(&new_rb_node->rb_node, maps__entries(maps)); - return 0; + return result; } -int maps__insert(struct maps *maps, struct map *map) +static void maps__delete(struct maps *maps) { - int err; - const struct dso *dso = map__dso(map); - - down_write(maps__lock(maps)); - err = __maps__insert(maps, map); - if (err) - goto out; + maps__exit(maps); + RC_CHK_FREE(maps); +} - ++RC_CHK_ACCESS(maps)->nr_maps; +struct maps *maps__get(struct maps *maps) +{ + struct maps *result; - if (dso && dso->kernel) { - struct kmap *kmap = map__kmap(map); + if (RC_CHK_GET(result, maps)) + refcount_inc(maps__refcnt(maps)); - if (kmap) - kmap->kmaps = maps; - else - pr_err("Internal error: kernel dso with non kernel map\n"); - } + return result; +} +void maps__put(struct maps *maps) +{ + if (maps && refcount_dec_and_test(maps__refcnt(maps))) + maps__delete(maps); + else + RC_CHK_PUT(maps); +} +static void __maps__free_maps_by_name(struct maps *maps) +{ /* - * If we already performed some search by name, then we need to add the just - * inserted map and resort. + * Free everything to try to do it from the rbtree in the next search */ - if (maps__maps_by_name(maps)) { - if (maps__nr_maps(maps) > RC_CHK_ACCESS(maps)->nr_maps_allocated) { - int nr_allocate = maps__nr_maps(maps) * 2; - struct map **maps_by_name = realloc(maps__maps_by_name(maps), - nr_allocate * sizeof(map)); + for (unsigned int i = 0; i < maps__nr_maps(maps); i++) + map__put(maps__maps_by_name(maps)[i]); - if (maps_by_name == NULL) { - __maps__free_maps_by_name(maps); - err = -ENOMEM; - goto out; - } + zfree(&RC_CHK_ACCESS(maps)->maps_by_name); +} - RC_CHK_ACCESS(maps)->maps_by_name = maps_by_name; - RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate; +static int map__start_cmp(const void *a, const void *b) +{ + const struct map *map_a = *(const struct map * const *)a; + const struct map *map_b = *(const struct map * const *)b; + u64 map_a_start = map__start(map_a); + u64 map_b_start = map__start(map_b); + + if (map_a_start == map_b_start) { + u64 map_a_end = map__end(map_a); + u64 map_b_end = map__end(map_b); + + if (map_a_end == map_b_end) { + /* Ensure maps with the same addresses have a fixed order. */ + if (RC_CHK_ACCESS(map_a) == RC_CHK_ACCESS(map_b)) + return 0; + return (intptr_t)RC_CHK_ACCESS(map_a) > (intptr_t)RC_CHK_ACCESS(map_b) + ? 1 : -1; } - maps__maps_by_name(maps)[maps__nr_maps(maps) - 1] = map__get(map); - __maps__sort_by_name(maps); + return map_a_end > map_b_end ? 1 : -1; } - out: - up_write(maps__lock(maps)); - return err; + return map_a_start > map_b_start ? 1 : -1; } -static void __maps__remove(struct maps *maps, struct map_rb_node *rb_node) +static void __maps__sort_by_address(struct maps *maps) { - rb_erase_init(&rb_node->rb_node, maps__entries(maps)); - map__put(rb_node->map); - free(rb_node); + 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__set_maps_by_address_sorted(maps, true); } -void maps__remove(struct maps *maps, struct map *map) +static void maps__sort_by_address(struct maps *maps) { - struct map_rb_node *rb_node; - down_write(maps__lock(maps)); - if (RC_CHK_ACCESS(maps)->last_search_by_name == map) - RC_CHK_ACCESS(maps)->last_search_by_name = NULL; - - rb_node = maps__find_node(maps, map); - assert(rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map)); - __maps__remove(maps, rb_node); - if (maps__maps_by_name(maps)) - __maps__free_maps_by_name(maps); - --RC_CHK_ACCESS(maps)->nr_maps; + __maps__sort_by_address(maps); up_write(maps__lock(maps)); } -static void __maps__purge(struct maps *maps) +static int map__strcmp(const void *a, const void *b) { - struct map_rb_node *pos, *next; - - if (maps__maps_by_name(maps)) - __maps__free_maps_by_name(maps); + const struct map *map_a = *(const struct map * const *)a; + const struct map *map_b = *(const struct map * const *)b; + const struct dso *dso_a = map__dso(map_a); + const struct dso *dso_b = map__dso(map_b); + int ret = strcmp(dso_a->short_name, dso_b->short_name); - maps__for_each_entry_safe(maps, pos, next) { - rb_erase_init(&pos->rb_node, maps__entries(maps)); - map__put(pos->map); - free(pos); + if (ret == 0 && RC_CHK_ACCESS(map_a) != RC_CHK_ACCESS(map_b)) { + /* Ensure distinct but name equal maps have an order. */ + return map__start_cmp(a, b); } + return ret; } -static void maps__exit(struct maps *maps) +static int maps__sort_by_name(struct maps *maps) { + int err = 0; down_write(maps__lock(maps)); - __maps__purge(maps); + if (!maps__maps_by_name_sorted(maps)) { + struct map **maps_by_name = maps__maps_by_name(maps); + + if (!maps_by_name) { + maps_by_name = malloc(RC_CHK_ACCESS(maps)->nr_maps_allocated * + sizeof(*maps_by_name)); + if (!maps_by_name) + 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]); + } + } + if (!err) { + qsort(maps_by_name, + maps__nr_maps(maps), + sizeof(struct map *), + map__strcmp); + maps__set_maps_by_name_sorted(maps, true); + } + } up_write(maps__lock(maps)); + return err; } -bool maps__empty(struct maps *maps) +static unsigned int maps__by_address_index(const struct maps *maps, const struct map *map) { - return !maps__first(maps); + struct map **maps_by_address = maps__maps_by_address(maps); + + if (maps__maps_by_address_sorted(maps)) { + struct map **mapp = + bsearch(&map, maps__maps_by_address(maps), maps__nr_maps(maps), + 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; + } + } + pr_err("Map missing from maps"); + return -1; } -struct maps *maps__new(struct machine *machine) +static unsigned int maps__by_name_index(const struct maps *maps, const struct map *map) { - struct maps *result; - RC_STRUCT(maps) *maps = zalloc(sizeof(*maps)); + struct map **maps_by_name = maps__maps_by_name(maps); + + if (maps__maps_by_name_sorted(maps)) { + struct map **mapp = + bsearch(&map, maps_by_name, maps__nr_maps(maps), + 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; + } + } + pr_err("Map missing from maps"); + return -1; +} - if (ADD_RC_CHK(result, maps)) - maps__init(result, machine); +static int __maps__insert(struct maps *maps, struct map *new) +{ + struct map **maps_by_address = maps__maps_by_address(maps); + struct map **maps_by_name = maps__maps_by_name(maps); + const struct dso *dso = map__dso(new); + unsigned int nr_maps = maps__nr_maps(maps); + unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated; + + if (nr_maps + 1 > nr_allocate) { + nr_allocate = !nr_allocate ? 32 : nr_allocate * 2; + + maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new)); + if (!maps_by_address) + return -ENOMEM; + + maps__set_maps_by_address(maps, maps_by_address); + if (maps_by_name) { + maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new)); + if (!maps_by_name) { + /* + * If by name fails, just disable by name and it will + * recompute next time it is required. + */ + __maps__free_maps_by_name(maps); + } + maps__set_maps_by_name(maps, maps_by_name); + } + RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate; + } + /* Insert the value at the end. */ + maps_by_address[nr_maps] = map__get(new); + if (maps_by_name) + maps_by_name[nr_maps] = map__get(new); - return result; + nr_maps++; + RC_CHK_ACCESS(maps)->nr_maps = nr_maps; + + /* + * Recompute if things are sorted. If things are inserted in a sorted + * manner, for example by processing /proc/pid/maps, then no + * sorting/resorting will be necessary. + */ + if (nr_maps == 1) { + /* If there's just 1 entry then maps are sorted. */ + maps__set_maps_by_address_sorted(maps, true); + maps__set_maps_by_name_sorted(maps, maps_by_name != NULL); + } else { + /* Sorted if maps were already sorted and this map starts after the last one. */ + maps__set_maps_by_address_sorted(maps, + maps__maps_by_address_sorted(maps) && + map__end(maps_by_address[nr_maps - 2]) <= map__start(new)); + maps__set_maps_by_name_sorted(maps, false); + } + if (map__end(new) < map__start(new)) + RC_CHK_ACCESS(maps)->ends_broken = true; + if (dso && dso->kernel) { + struct kmap *kmap = map__kmap(new); + + if (kmap) + kmap->kmaps = maps; + else + pr_err("Internal error: kernel dso with non kernel map\n"); + } + return 0; } -static void maps__delete(struct maps *maps) +int maps__insert(struct maps *maps, struct map *map) { - maps__exit(maps); - unwind__finish_access(maps); - RC_CHK_FREE(maps); + int ret; + + down_write(maps__lock(maps)); + ret = __maps__insert(maps, map); + up_write(maps__lock(maps)); + return ret; } -struct maps *maps__get(struct maps *maps) +static void __maps__remove(struct maps *maps, struct map *map) { - struct maps *result; + struct map **maps_by_address = maps__maps_by_address(maps); + struct map **maps_by_name = maps__maps_by_name(maps); + unsigned int nr_maps = maps__nr_maps(maps); + unsigned int address_idx; + + /* Slide later mappings over the one to remove */ + address_idx = maps__by_address_index(maps, map); + map__put(maps_by_address[address_idx]); + memmove(&maps_by_address[address_idx], + &maps_by_address[address_idx + 1], + (nr_maps - address_idx - 1) * sizeof(*maps_by_address)); + + if (maps_by_name) { + unsigned int name_idx = maps__by_name_index(maps, map); + + map__put(maps_by_name[name_idx]); + memmove(&maps_by_name[name_idx], + &maps_by_name[name_idx + 1], + (nr_maps - name_idx - 1) * sizeof(*maps_by_name)); + } - if (RC_CHK_GET(result, maps)) - refcount_inc(maps__refcnt(maps)); + --RC_CHK_ACCESS(maps)->nr_maps; +} - return result; +void maps__remove(struct maps *maps, struct map *map) +{ + down_write(maps__lock(maps)); + __maps__remove(maps, map); + up_write(maps__lock(maps)); } -void maps__put(struct maps *maps) +bool maps__empty(struct maps *maps) { - if (maps && refcount_dec_and_test(maps__refcnt(maps))) - maps__delete(maps); - else - RC_CHK_PUT(maps); + return maps__nr_maps(maps) == 0; } int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data) { - struct map_rb_node *pos; + bool done = false; int ret = 0; - down_read(maps__lock(maps)); - maps__for_each_entry(maps, pos) { - ret = cb(pos->map, data); - if (ret) - break; + /* See locking/sorting note. */ + while (!done) { + down_read(maps__lock(maps)); + if (maps__maps_by_address_sorted(maps)) { + struct map **maps_by_address = maps__maps_by_address(maps); + unsigned int n = maps__nr_maps(maps); + + for (unsigned int i = 0; i < n; i++) { + struct map *map = maps_by_address[i]; + + ret = cb(map, data); + if (ret) + break; + } + done = true; + } + up_read(maps__lock(maps)); + if (!done) + maps__sort_by_address(maps); } - up_read(maps__lock(maps)); return ret; } void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data) { - struct map_rb_node *pos, *next; - unsigned int start_nr_maps; + struct map **maps_by_address; down_write(maps__lock(maps)); - start_nr_maps = maps__nr_maps(maps); - maps__for_each_entry_safe(maps, pos, next) { - if (cb(pos->map, data)) { - __maps__remove(maps, pos); - --RC_CHK_ACCESS(maps)->nr_maps; - } + maps_by_address = maps__maps_by_address(maps); + for (unsigned int i = 0; i < maps__nr_maps(maps);) { + if (cb(maps_by_address[i], data)) + __maps__remove(maps, maps_by_address[i]); + else + i++; } - if (maps__maps_by_name(maps) && start_nr_maps != maps__nr_maps(maps)) - __maps__free_maps_by_name(maps); - up_write(maps__lock(maps)); } @@ -300,7 +504,7 @@ struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp) /* Ensure map is loaded before using map->map_ip */ if (map != NULL && map__load(map) >= 0) { if (mapp != NULL) - *mapp = map; + *mapp = map; // TODO: map_put on else path when find returns a get. return map__find_symbol(map, map__map_ip(map, addr)); } @@ -348,7 +552,7 @@ int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams) if (ams->addr < map__start(ams->ms.map) || ams->addr >= map__end(ams->ms.map)) { if (maps == NULL) return -1; - ams->ms.map = maps__find(maps, ams->addr); + ams->ms.map = maps__find(maps, ams->addr); // TODO: map_get if (ams->ms.map == NULL) return -1; } @@ -393,24 +597,28 @@ size_t maps__fprintf(struct maps *maps, FILE *fp) * Find first map where end > map->start. * Same as find_vma() in kernel. */ -static struct rb_node *first_ending_after(struct maps *maps, const struct map *map) +static unsigned int first_ending_after(struct maps *maps, const struct map *map) { - struct rb_root *root; - struct rb_node *next, *first; + struct map **maps_by_address = maps__maps_by_address(maps); + int low = 0, high = (int)maps__nr_maps(maps) - 1, first = high + 1; + + assert(maps__maps_by_address_sorted(maps)); + if (low <= high && map__end(maps_by_address[0]) > map__start(map)) + return 0; - root = maps__entries(maps); - next = root->rb_node; - first = NULL; - while (next) { - struct map_rb_node *pos = rb_entry(next, struct map_rb_node, rb_node); + while (low <= high) { + int mid = (low + high) / 2; + struct map *pos = maps_by_address[mid]; - if (map__end(pos->map) > map__start(map)) { - first = next; - if (map__start(pos->map) <= map__start(map)) + if (map__end(pos) > map__start(map)) { + first = mid; + if (map__start(pos) <= map__start(map)) { + /* Entry overlaps map. */ break; - next = next->rb_left; + } + high = mid - 1; } else - next = next->rb_right; + low = mid + 1; } return first; } @@ -419,171 +627,249 @@ static struct rb_node *first_ending_after(struct maps *maps, const struct map *m * Adds new to maps, if new overlaps existing entries then the existing maps are * adjusted or removed so that new fits without overlapping any entries. */ -int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) +static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) { - - struct rb_node *next; + struct map **maps_by_address; int err = 0; FILE *fp = debug_file(); - down_write(maps__lock(maps)); +sort_again: + if (!maps__maps_by_address_sorted(maps)) + __maps__sort_by_address(maps); - next = first_ending_after(maps, new); - while (next && !err) { - struct map_rb_node *pos = rb_entry(next, struct map_rb_node, rb_node); - next = rb_next(&pos->rb_node); + maps_by_address = maps__maps_by_address(maps); + /* + * Iterate through entries where the end of the existing entry is + * greater-than the new map's start. + */ + for (unsigned int i = first_ending_after(maps, new); i < maps__nr_maps(maps); ) { + struct map *pos = maps_by_address[i]; + struct map *before = NULL, *after = NULL; /* * Stop if current map starts after map->end. * Maps are ordered by start: next will not overlap for sure. */ - if (map__start(pos->map) >= map__end(new)) + if (map__start(pos) >= map__end(new)) break; - if (verbose >= 2) { - - if (use_browser) { - pr_debug("overlapping maps in %s (disable tui for more info)\n", - map__dso(new)->name); - } else { - pr_debug("overlapping maps:\n"); - map__fprintf(new, fp); - map__fprintf(pos->map, fp); - } + if (use_browser) { + pr_debug("overlapping maps in %s (disable tui for more info)\n", + map__dso(new)->name); + } else if (verbose >= 2) { + pr_debug("overlapping maps:\n"); + map__fprintf(new, fp); + map__fprintf(pos, fp); } - rb_erase_init(&pos->rb_node, maps__entries(maps)); /* * Now check if we need to create new maps for areas not * overlapped by the new map: */ - if (map__start(new) > map__start(pos->map)) { - struct map *before = map__clone(pos->map); + if (map__start(new) > map__start(pos)) { + /* Map starts within existing map. Need to shorten the existing map. */ + before = map__clone(pos); if (before == NULL) { err = -ENOMEM; - goto put_map; + goto out_err; } - map__set_end(before, map__start(new)); - err = __maps__insert(maps, before); - if (err) { - map__put(before); - goto put_map; - } if (verbose >= 2 && !use_browser) map__fprintf(before, fp); - map__put(before); } - - if (map__end(new) < map__end(pos->map)) { - struct map *after = map__clone(pos->map); + if (map__end(new) < map__end(pos)) { + /* The new map isn't as long as the existing map. */ + after = map__clone(pos); if (after == NULL) { + map__zput(before); err = -ENOMEM; - goto put_map; + goto out_err; } map__set_start(after, map__end(new)); - map__add_pgoff(after, map__end(new) - map__start(pos->map)); - assert(map__map_ip(pos->map, map__end(new)) == - map__map_ip(after, map__end(new))); - err = __maps__insert(maps, after); - if (err) { - map__put(after); - goto put_map; - } + map__add_pgoff(after, map__end(new) - map__start(pos)); + assert(map__map_ip(pos, map__end(new)) == + map__map_ip(after, map__end(new))); + if (verbose >= 2 && !use_browser) map__fprintf(after, fp); - map__put(after); } -put_map: - map__put(pos->map); - free(pos); + /* + * If adding one entry, for `before` or `after`, we can replace + * the existing entry. If both `before` and `after` are + * necessary than an insert is needed. If the existing entry + * entirely overlaps the existing entry it can just be removed. + */ + if (before) { + map__put(maps_by_address[i]); + maps_by_address[i] = before; + /* Maps are still ordered, go to next one. */ + i++; + if (after) { + __maps__insert(maps, after); + map__put(after); + if (!maps__maps_by_address_sorted(maps)) { + /* + * Sorting broken so invariants don't + * hold, sort and go again. + */ + goto sort_again; + } + /* + * Maps are still ordered, skip after and go to + * next one (terminate loop). + */ + i++; + } + } else if (after) { + map__put(maps_by_address[i]); + maps_by_address[i] = after; + /* Maps are ordered, go to next one. */ + i++; + } else { + __maps__remove(maps, pos); + /* + * Maps are ordered but no need to increase `i` as the + * later maps were moved down. + */ + } + check_invariants(maps); } /* Add the map. */ - err = __maps__insert(maps, new); - up_write(maps__lock(maps)); + __maps__insert(maps, new); +out_err: return err; } -int maps__copy_from(struct maps *maps, struct maps *parent) +int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new) { int err; - struct map_rb_node *rb_node; + down_write(maps__lock(maps)); + err = __maps__fixup_overlap_and_insert(maps, new); + up_write(maps__lock(maps)); + return err; +} + +int maps__copy_from(struct maps *dest, struct maps *parent) +{ + /* Note, if struct map were immutable then cloning could use ref counts. */ + struct map **parent_maps_by_address; + int err = 0; + unsigned int n; + + down_write(maps__lock(dest)); down_read(maps__lock(parent)); - maps__for_each_entry(parent, rb_node) { - struct map *new = map__clone(rb_node->map); + parent_maps_by_address = maps__maps_by_address(parent); + n = maps__nr_maps(parent); + if (maps__empty(dest)) { + /* No existing mappings so just copy from parent to avoid reallocs in insert. */ + unsigned int nr_maps_allocated = RC_CHK_ACCESS(parent)->nr_maps_allocated; + struct map **dest_maps_by_address = + malloc(nr_maps_allocated * sizeof(struct map *)); + struct map **dest_maps_by_name = NULL; - if (new == NULL) { + if (!dest_maps_by_address) err = -ENOMEM; - goto out_unlock; + else { + if (maps__maps_by_name(parent)) { + dest_maps_by_name = + malloc(nr_maps_allocated * sizeof(struct map *)); + } + + RC_CHK_ACCESS(dest)->maps_by_address = dest_maps_by_address; + RC_CHK_ACCESS(dest)->maps_by_name = dest_maps_by_name; + RC_CHK_ACCESS(dest)->nr_maps_allocated = nr_maps_allocated; } - err = unwind__prepare_access(maps, new, NULL); - if (err) - goto out_unlock; + for (unsigned int i = 0; !err && i < n; i++) { + struct map *pos = parent_maps_by_address[i]; + struct map *new = map__clone(pos); - err = maps__insert(maps, new); - if (err) - goto out_unlock; + if (!new) + err = -ENOMEM; + else { + err = unwind__prepare_access(dest, new, NULL); + if (!err) { + dest_maps_by_address[i] = new; + if (dest_maps_by_name) + dest_maps_by_name[i] = map__get(new); + RC_CHK_ACCESS(dest)->nr_maps = i + 1; + } + } + if (err) + map__put(new); + } + maps__set_maps_by_address_sorted(dest, maps__maps_by_address_sorted(parent)); + if (!err) { + RC_CHK_ACCESS(dest)->last_search_by_name_idx = + RC_CHK_ACCESS(parent)->last_search_by_name_idx; + maps__set_maps_by_name_sorted(dest, + dest_maps_by_name && + maps__maps_by_name_sorted(parent)); + } else { + RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0; + maps__set_maps_by_name_sorted(dest, false); + } + } else { + /* Unexpected copying to a maps containing entries. */ + for (unsigned int i = 0; !err && i < n; i++) { + struct map *pos = parent_maps_by_address[i]; + struct map *new = map__clone(pos); - map__put(new); + if (!new) + err = -ENOMEM; + else { + err = unwind__prepare_access(dest, new, NULL); + if (!err) + err = __maps__insert(dest, new); + } + map__put(new); + } } - - err = 0; -out_unlock: up_read(maps__lock(parent)); + up_write(maps__lock(dest)); return err; } -struct map *maps__find(struct maps *maps, u64 ip) +static int map__addr_cmp(const void *key, const void *entry) { - struct rb_node *p; - struct map_rb_node *m; - - - down_read(maps__lock(maps)); - - p = maps__entries(maps)->rb_node; - while (p != NULL) { - m = rb_entry(p, struct map_rb_node, rb_node); - if (ip < map__start(m->map)) - p = p->rb_left; - else if (ip >= map__end(m->map)) - p = p->rb_right; - else - goto out; - } + const u64 ip = *(const u64 *)key; + const struct map *map = *(const struct map * const *)entry; - m = NULL; -out: - up_read(maps__lock(maps)); - return m ? m->map : NULL; + if (ip < map__start(map)) + return -1; + if (ip >= map__end(map)) + return 1; + return 0; } -static int map__strcmp(const void *a, const void *b) +struct map *maps__find(struct maps *maps, u64 ip) { - const struct map *map_a = *(const struct map **)a; - const struct map *map_b = *(const struct map **)b; - const struct dso *dso_a = map__dso(map_a); - const struct dso *dso_b = map__dso(map_b); - int ret = strcmp(dso_a->short_name, dso_b->short_name); - - if (ret == 0 && map_a != map_b) { - /* - * Ensure distinct but name equal maps have an order in part to - * aid reference counting. - */ - ret = (int)map__start(map_a) - (int)map__start(map_b); - if (ret == 0) - ret = (int)((intptr_t)map_a - (intptr_t)map_b); + struct map *result = NULL; + bool done = false; + + /* See locking/sorting note. */ + while (!done) { + down_read(maps__lock(maps)); + if (maps__maps_by_address_sorted(maps)) { + struct map **mapp = + bsearch(&ip, maps__maps_by_address(maps), maps__nr_maps(maps), + sizeof(*mapp), map__addr_cmp); + + if (mapp) + result = *mapp; // map__get(*mapp); + done = true; + } + up_read(maps__lock(maps)); + if (!done) + maps__sort_by_address(maps); } - - return ret; + return result; } static int map__strcmp_name(const void *name, const void *b) @@ -593,126 +879,113 @@ static int map__strcmp_name(const void *name, const void *b) return strcmp(name, dso->short_name); } -void __maps__sort_by_name(struct maps *maps) -{ - qsort(maps__maps_by_name(maps), maps__nr_maps(maps), sizeof(struct map *), map__strcmp); -} - -static int map__groups__sort_by_name_from_rbtree(struct maps *maps) -{ - struct map_rb_node *rb_node; - struct map **maps_by_name = realloc(maps__maps_by_name(maps), - maps__nr_maps(maps) * sizeof(struct map *)); - int i = 0; - - if (maps_by_name == NULL) - return -1; - - up_read(maps__lock(maps)); - down_write(maps__lock(maps)); - - RC_CHK_ACCESS(maps)->maps_by_name = maps_by_name; - RC_CHK_ACCESS(maps)->nr_maps_allocated = maps__nr_maps(maps); - - maps__for_each_entry(maps, rb_node) - maps_by_name[i++] = map__get(rb_node->map); - - __maps__sort_by_name(maps); - - up_write(maps__lock(maps)); - down_read(maps__lock(maps)); - - return 0; -} - -static struct map *__maps__find_by_name(struct maps *maps, const char *name) +struct map *maps__find_by_name(struct maps *maps, const char *name) { - struct map **mapp; + struct map *result = NULL; + bool done = false; - if (maps__maps_by_name(maps) == NULL && - map__groups__sort_by_name_from_rbtree(maps)) - return NULL; + /* See locking/sorting note. */ + while (!done) { + unsigned int i; - mapp = bsearch(name, maps__maps_by_name(maps), maps__nr_maps(maps), - sizeof(*mapp), map__strcmp_name); - if (mapp) - return *mapp; - return NULL; -} + down_read(maps__lock(maps)); -struct map *maps__find_by_name(struct maps *maps, const char *name) -{ - struct map_rb_node *rb_node; - struct map *map; - - down_read(maps__lock(maps)); + /* First check last found entry. */ + i = RC_CHK_ACCESS(maps)->last_search_by_name_idx; + if (i < maps__nr_maps(maps) && maps__maps_by_name(maps)) { + struct dso *dso = map__dso(maps__maps_by_name(maps)[i]); + if (dso && strcmp(dso->short_name, name) == 0) { + result = maps__maps_by_name(maps)[i]; // TODO: map__get + done = true; + } + } - if (RC_CHK_ACCESS(maps)->last_search_by_name) { - const struct dso *dso = map__dso(RC_CHK_ACCESS(maps)->last_search_by_name); + /* Second search sorted array. */ + if (!done && maps__maps_by_name_sorted(maps)) { + struct map **mapp = + bsearch(name, maps__maps_by_name(maps), maps__nr_maps(maps), + sizeof(*mapp), map__strcmp_name); - if (strcmp(dso->short_name, name) == 0) { - map = RC_CHK_ACCESS(maps)->last_search_by_name; - goto out_unlock; + if (mapp) { + result = *mapp; // TODO: map__get + i = mapp - maps__maps_by_name(maps); + RC_CHK_ACCESS(maps)->last_search_by_name_idx = i; + } + done = true; } - } - /* - * If we have maps->maps_by_name, then the name isn't in the rbtree, - * as maps->maps_by_name mirrors the rbtree when lookups by name are - * made. - */ - map = __maps__find_by_name(maps, name); - if (map || maps__maps_by_name(maps) != NULL) - goto out_unlock; - - /* Fallback to traversing the rbtree... */ - maps__for_each_entry(maps, rb_node) { - struct dso *dso; - - map = rb_node->map; - dso = map__dso(map); - if (strcmp(dso->short_name, name) == 0) { - RC_CHK_ACCESS(maps)->last_search_by_name = map; - goto out_unlock; + up_read(maps__lock(maps)); + if (!done) { + /* Sort and retry binary search. */ + if (maps__sort_by_name(maps)) { + /* + * Memory allocation failed do linear search + * through address sorted maps. + */ + struct map **maps_by_address; + unsigned int n; + + down_read(maps__lock(maps)); + maps_by_address = maps__maps_by_address(maps); + n = maps__nr_maps(maps); + for (i = 0; i < n; i++) { + struct map *pos = maps_by_address[i]; + struct dso *dso = map__dso(pos); + + if (dso && strcmp(dso->short_name, name) == 0) { + result = pos; // TODO: map__get + break; + } + } + up_read(maps__lock(maps)); + done = true; + } } } - map = NULL; - -out_unlock: - up_read(maps__lock(maps)); - return map; + return result; } struct map *maps__find_next_entry(struct maps *maps, struct map *map) { - struct map_rb_node *rb_node = maps__find_node(maps, map); - struct map_rb_node *next = map_rb_node__next(rb_node); + unsigned int i; + struct map *result = NULL; - if (next) - return next->map; + down_read(maps__lock(maps)); + i = maps__by_address_index(maps, map); + if (i < maps__nr_maps(maps)) + result = maps__maps_by_address(maps)[i]; // TODO: map__get - return NULL; + up_read(maps__lock(maps)); + return result; } void maps__fixup_end(struct maps *maps) { - struct map_rb_node *prev = NULL, *curr; + struct map **maps_by_address; + unsigned int n; down_write(maps__lock(maps)); + if (!maps__maps_by_address_sorted(maps)) + __maps__sort_by_address(maps); - maps__for_each_entry(maps, curr) { - if (prev && (!map__end(prev->map) || map__end(prev->map) > map__start(curr->map))) - map__set_end(prev->map, map__start(curr->map)); + maps_by_address = maps__maps_by_address(maps); + n = maps__nr_maps(maps); + for (unsigned int i = 1; i < n; i++) { + struct map *prev = maps_by_address[i - 1]; + struct map *curr = maps_by_address[i]; - prev = curr; + if (!map__end(prev) || map__end(prev) > map__start(curr)) + map__set_end(prev, map__start(curr)); } /* * We still haven't the actual symbols, so guess the * last map final address. */ - if (curr && !map__end(curr->map)) - map__set_end(curr->map, ~0ULL); + if (n > 0 && !map__end(maps_by_address[n - 1])) + map__set_end(maps_by_address[n - 1], ~0ULL); + + RC_CHK_ACCESS(maps)->ends_broken = false; up_write(maps__lock(maps)); } @@ -723,117 +996,93 @@ void maps__fixup_end(struct maps *maps) */ int maps__merge_in(struct maps *kmaps, struct map *new_map) { - struct map_rb_node *rb_node; - struct rb_node *first; - bool overlaps; - LIST_HEAD(merged); - int err = 0; - - down_read(maps__lock(kmaps)); - first = first_ending_after(kmaps, new_map); - rb_node = first ? rb_entry(first, struct map_rb_node, rb_node) : NULL; - overlaps = rb_node && map__start(rb_node->map) < map__end(new_map); - up_read(maps__lock(kmaps)); + unsigned int first_after_, kmaps__nr_maps; + struct map **kmaps_maps_by_address; + struct map **merged_maps_by_address; + unsigned int merged_nr_maps_allocated; + + /* First try under a read lock. */ + while (true) { + down_read(maps__lock(kmaps)); + if (maps__maps_by_address_sorted(kmaps)) + break; - if (!overlaps) - return maps__insert(kmaps, new_map); + up_read(maps__lock(kmaps)); - maps__for_each_entry(kmaps, rb_node) { - struct map *old_map = rb_node->map; + /* First after binary search requires sorted maps. Sort and try again. */ + maps__sort_by_address(kmaps); + } + first_after_ = first_ending_after(kmaps, new_map); + kmaps_maps_by_address = maps__maps_by_address(kmaps); - /* no overload with this one */ - if (map__end(new_map) < map__start(old_map) || - map__start(new_map) >= map__end(old_map)) - continue; + if (first_after_ >= maps__nr_maps(kmaps) || + map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) { + /* No overlap so regular insert suffices. */ + up_read(maps__lock(kmaps)); + return maps__insert(kmaps, new_map); + } + up_read(maps__lock(kmaps)); - if (map__start(new_map) < map__start(old_map)) { - /* - * |new...... - * |old.... - */ - if (map__end(new_map) < map__end(old_map)) { - /* - * |new......| -> |new..| - * |old....| -> |old....| - */ - map__set_end(new_map, map__start(old_map)); - } else { - /* - * |new.............| -> |new..| |new..| - * |old....| -> |old....| - */ - struct map_list_node *m = map_list_node__new(); + /* Plain insert with a read-lock failed, try again now with the write lock. */ + down_write(maps__lock(kmaps)); + if (!maps__maps_by_address_sorted(kmaps)) + __maps__sort_by_address(kmaps); + + first_after_ = first_ending_after(kmaps, new_map); + kmaps_maps_by_address = maps__maps_by_address(kmaps); + kmaps__nr_maps = maps__nr_maps(kmaps); + + if (first_after_ >= kmaps__nr_maps || + map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) { + /* No overlap so regular insert suffices. */ + int ret = __maps__insert(kmaps, new_map); + up_write(maps__lock(kmaps)); + return ret; + } + /* Array to merge into, possibly 1 more for the sake of new_map. */ + merged_nr_maps_allocated = RC_CHK_ACCESS(kmaps)->nr_maps_allocated; + if (kmaps__nr_maps + 1 == merged_nr_maps_allocated) + merged_nr_maps_allocated++; + + merged_maps_by_address = malloc(merged_nr_maps_allocated * sizeof(*merged_maps_by_address)); + if (!merged_maps_by_address) { + up_write(maps__lock(kmaps)); + return -ENOMEM; + } + maps__set_maps_by_address(kmaps, merged_maps_by_address); + maps__set_maps_by_address_sorted(kmaps, true); + zfree(maps__maps_by_name_addr(kmaps)); + maps__set_maps_by_name_sorted(kmaps, true); + maps__set_nr_maps_allocated(kmaps, merged_nr_maps_allocated); - if (!m) { - err = -ENOMEM; - goto out; - } + /* Copy entries before the new_map that can't overlap. */ + for (unsigned int i = 0; i < first_after_; i++) + merged_maps_by_address[i] = map__get(kmaps_maps_by_address[i]); - m->map = map__clone(new_map); - if (!m->map) { - free(m); - err = -ENOMEM; - goto out; - } + maps__set_nr_maps(kmaps, first_after_); - map__set_end(m->map, map__start(old_map)); - list_add_tail(&m->node, &merged); - map__add_pgoff(new_map, map__end(old_map) - map__start(new_map)); - map__set_start(new_map, map__end(old_map)); - } - } else { - /* - * |new...... - * |old.... - */ - if (map__end(new_map) < map__end(old_map)) { - /* - * |new..| -> x - * |old.........| -> |old.........| - */ - map__put(new_map); - new_map = NULL; - break; - } else { - /* - * |new......| -> |new...| - * |old....| -> |old....| - */ - map__add_pgoff(new_map, map__end(old_map) - map__start(new_map)); - map__set_start(new_map, map__end(old_map)); - } - } - } + /* Add the new map, it will be split when the later overlapping mappings are added. */ + __maps__insert(kmaps, new_map); -out: - while (!list_empty(&merged)) { - struct map_list_node *old_node; + /* Insert mappings after new_map, splitting new_map in the process. */ + for (unsigned int i = first_after_; i < kmaps__nr_maps; i++) + __maps__fixup_overlap_and_insert(kmaps, kmaps_maps_by_address[i]); - old_node = list_entry(merged.next, struct map_list_node, node); - list_del_init(&old_node->node); - if (!err) - err = maps__insert(kmaps, old_node->map); - map__put(old_node->map); - free(old_node); - } + /* Copy the maps from merged into kmaps. */ + for (unsigned int i = 0; i < kmaps__nr_maps; i++) + map__zput(kmaps_maps_by_address[i]); - if (new_map) { - if (!err) - err = maps__insert(kmaps, new_map); - map__put(new_map); - } - return err; + free(kmaps_maps_by_address); + up_write(maps__lock(kmaps)); + return 0; } void maps__load_first(struct maps *maps) { - struct map_rb_node *first; - down_read(maps__lock(maps)); - first = maps__first(maps); - if (first) - map__load(first->map); + if (maps__nr_maps(maps) > 0) + map__load(maps__maps_by_address(maps)[0]); up_read(maps__lock(maps)); } diff --git a/tools/perf/util/maps.h b/tools/perf/util/maps.h index d836d04c9402..df9dd5a0e3c0 100644 --- a/tools/perf/util/maps.h +++ b/tools/perf/util/maps.h @@ -25,21 +25,56 @@ static inline struct map_list_node *map_list_node__new(void) return malloc(sizeof(struct map_list_node)); } -struct map *maps__find(struct maps *maps, u64 addr); +/* + * Locking/sorting note: + * + * Sorting is done with the write lock, iteration and binary searching happens + * under the read lock requiring being sorted. There is a race between sorting + * releasing the write lock and acquiring the read lock for iteration/searching + * where another thread could insert and break the sorting of the maps. In + * practice inserting maps should be rare meaning that the race shouldn't lead + * to live lock. Removal of maps doesn't break being sorted. + */ DECLARE_RC_STRUCT(maps) { - struct rb_root entries; struct rw_semaphore lock; - struct machine *machine; - struct map *last_search_by_name; + /** + * @maps_by_address: array of maps sorted by their starting address if + * maps_by_address_sorted is true. + */ + struct map **maps_by_address; + /** + * @maps_by_name: optional array of maps sorted by their dso name if + * maps_by_name_sorted is true. + */ struct map **maps_by_name; - refcount_t refcnt; - unsigned int nr_maps; - unsigned int nr_maps_allocated; + struct machine *machine; #ifdef HAVE_LIBUNWIND_SUPPORT - void *addr_space; + void *addr_space; const struct unwind_libunwind_ops *unwind_libunwind_ops; #endif + refcount_t refcnt; + /** + * @nr_maps: number of maps_by_address, and possibly maps_by_name, + * entries that contain maps. + */ + unsigned int nr_maps; + /** + * @nr_maps_allocated: number of entries in maps_by_address and possibly + * maps_by_name. + */ + unsigned int nr_maps_allocated; + /** + * @last_search_by_name_idx: cache of last found by name entry's index + * as frequent searches for the same dso name are common. + */ + unsigned int last_search_by_name_idx; + /** @maps_by_address_sorted: is maps_by_address sorted. */ + bool maps_by_address_sorted; + /** @maps_by_name_sorted: is maps_by_name sorted. */ + bool maps_by_name_sorted; + /** @ends_broken: does the map contain a map where end values are unset/unsorted? */ + bool ends_broken; }; #define KMAP_NAME_LEN 256 @@ -102,6 +137,7 @@ size_t maps__fprintf(struct maps *maps, FILE *fp); int maps__insert(struct maps *maps, struct map *map); void maps__remove(struct maps *maps, struct map *map); +struct map *maps__find(struct maps *maps, u64 addr); struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp); struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp); @@ -117,8 +153,6 @@ struct map *maps__find_next_entry(struct maps *maps, struct map *map); int maps__merge_in(struct maps *kmaps, struct map *new_map); -void __maps__sort_by_name(struct maps *maps); - void maps__fixup_end(struct maps *maps); void maps__load_first(struct maps *maps); From patchwork Wed Feb 7 22:36:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198108 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546996dyb; Wed, 7 Feb 2024 14:40:22 -0800 (PST) X-Google-Smtp-Source: AGHT+IHtyRAyi9ugzyYTaT3V5xTUD4f9/iyZZj3MneT84sp9KUGKqGAsnnrUgg+t3UWhuSY7Jhi8 X-Received: by 2002:a17:90b:19c5:b0:296:36d9:eefe with SMTP id nm5-20020a17090b19c500b0029636d9eefemr3984871pjb.14.1707345622462; Wed, 07 Feb 2024 14:40:22 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345622; cv=pass; d=google.com; s=arc-20160816; b=W6lFik4nUcl4Y77/fCP/9zbMwJXUhB9Bc0Sk6/wwuDqyq96zgBIJCAMb44nI3oiohl XSYrEKPZcJ8yhBT+XRs1+W8bIbupnQvyNxPpOL9VOMWbcrvshU1Sb2Qn7LTKSOBY8unL MXAo4Cl+GV1QHel32cLVHcIB9uqLfNBCvV+vNr3wKxarndfyYyNOkONke75PMFzg+H+V 2S9Jk0gYfFJB9k1u2KV6kjWgXOqQXlv9rKqWdgNWQaSHAiAfm86Amk311r1S2S5v5lDC VrDngo9dBhRhLmTb2E86+k5G+5n+pViML7Fiyst3UjckM+uzTYOxuoucq8GqCYDJpoeq 4ScQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=BKYKLMrv5V+KXHpHJf+OrewS1WtN3SExz8bYkY92f/Q=; fh=yH6OZCD+qi3H/uKOQ0qABBZpoVL/cjvM86K5usCcrUQ=; b=uTJoruMFqIy7+qSebgHCufhaxkTm97ez1lA5i/AWtcX/KOT302KTI3HaZ6VNysOG43 lMZONHbSk5BXHC1qwdyvOe9LalosOg5WReKpw2BDJpLNr61PpQQP9vX9pkSAQHuA3cPS qYCp4wB7KwP6z8NappGfGsbn55rL64TAzIejRrCEHb1gFkLLA7HUDRPmpZzPWk6Mw/SE 59b9Mk9ADdWk5Wij0h1tJWTQdxczIuBJwJ3MahGvYtgSfvm/88/yrok842zlRu8206mm ZJkEaQhZeQJBA53slj2P48alQ2B64DMObL49BtodyaKskBLmOuzjikfM0dgIKxuNIQwQ ZaGg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=PTppDiK9; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57261-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57261-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCVbxAC939JHOlnpSBPFPTqE7WWk0j3+2aQrYILtIWCPZzntUrAgQ2G2EQAGb2GAUozwg1kuFiRT3FMG/8Qniq8c+HZgpw== Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [2604:1380:40f1:3f00::1]) by mx.google.com with ESMTPS id q65-20020a17090a17c700b002960647b16esi4207761pja.42.2024.02.07.14.40.22 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:40:22 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57261-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=PTppDiK9; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57261-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57261-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sy.mirrors.kernel.org (Postfix) with ESMTPS id 619C7B22A5E for ; Wed, 7 Feb 2024 22:38:09 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 791BA535BC; Wed, 7 Feb 2024 22:37:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="PTppDiK9" Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 61F511EB27 for ; Wed, 7 Feb 2024 22:37:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345434; cv=none; b=tVzb8ejwFWqeX8AHSjyiLGA6+uAglgbYbegSZzEOoIPLlIO8KIxSp8eyJWMFvtxemvK5Va2cGr4o451I3VATQMP0usNJCIVYBTLVb1SurXTD1C/oeLMRBEMa3bjsKuE7/n4H4MSFypd4V74M2ZFxRJbmNKQoQoyY3A8FOTAtyHE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345434; c=relaxed/simple; bh=RZxmraRvUZVDCEnHDiKvvvCrdlGpPV4CU1ch1xpR8Ps=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=Xa+67LkRqkgqwZy/dF6vuSh7U93VQ6bx4tOEaVc9UnX6UKS7NHzERnRDnK+KYgUluGJQaq00xKBbtuTdUxDPEam1UrnLck4Nhm3osLQ+bBvyW4VOpxvqj5DYBbmtqYObRjCHQEih42ZFumKUQsDkoaN9cy9rllekFWnQkS8VSDE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=PTppDiK9; arc=none smtp.client-ip=209.85.128.201 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 Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-604833eb9c3so21659937b3.1 for ; Wed, 07 Feb 2024 14:37:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345430; x=1707950230; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=BKYKLMrv5V+KXHpHJf+OrewS1WtN3SExz8bYkY92f/Q=; b=PTppDiK9MqwA29qsozPiSPPd/sEqX7IlOGnkXq1agwOQJLdBNDap/uUp/4gxPILEuA do7Sa7okhuVM52a/AYqjC2//z9kTK5RN0KxyQxxWOgrBmivwTOEAMR2XbkjEWoumia9n uaV7+jUWKa6wyeEY+zRy/xeykUv51+LcpnWMIu7VC8Iy5fQWJzetBUCIfnmRjoC4pXsK viq2eTD8CuQr2GrcHeKht44GzwnnYInwYZaiBYkx0NK4uFghYVsdLXfNahbHdFDuMq7u YrpgAvFRO18Mym1UKvKZGMQfRl0ocrY5VTibRC6vvXqSCnDDk0bCmKioLQ5XwVGni8Qh CmMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345430; x=1707950230; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=BKYKLMrv5V+KXHpHJf+OrewS1WtN3SExz8bYkY92f/Q=; b=DfAT/r2H1L/OWfKey3sWK9TrzuaqW3NxCtSIEW0JwtxLxOaOkwFRsdK45JCceS6qbG Ou9/NWfzieuSOGCdVL3M/JNW68A1diKCHsL/sLwZqgW77AABI0R6mD8MWplAVqaR6lgj Vc1w3V+5UJ7tQgzWiLJ5dbop/nXjQ26TS3eK/ygX670sRsUOboIiwrhUxa1lwGoN5F0k +JG60hHxksFMv1mxdcJqDVcW3+H0TZBYRfHhs/K6pR/0ByZsInsDg6vHwrqFST6bbBpg vDqUbNOuQAwpcosa/v8UjvQYZdpOgY3A8SWIooCvkYpkWDZuYg26FGJzt+oT6pCcrdns HMxg== X-Gm-Message-State: AOJu0YzwgUooHkmpl4Y/cPuAwysryvks3a9W3LFdwK9IbpzfO1X8nnF8 QEHUT83CB+ss7M7aGeynq02Pz8ChySaohEbnsy+fLDteb58ZZspXuCdzHG+oseipw1+RwhrPGWF 0m4ZK2w== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a81:574c:0:b0:5ff:5389:526c with SMTP id l73-20020a81574c000000b005ff5389526cmr927894ywb.2.1707345430452; Wed, 07 Feb 2024 14:37:10 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:35 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-3-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 2/6] perf maps: Get map before returning in maps__find From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281643029945036 X-GMAIL-MSGID: 1790281643029945036 Finding a map is done under a lock, returning the map without a reference count means it can be removed without notice and causing uses after free. Grab a reference count to the map within the lock region and return this. Fix up locations that need a map__put following this. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/arch/x86/tests/dwarf-unwind.c | 1 + tools/perf/tests/vmlinux-kallsyms.c | 5 ++--- tools/perf/util/bpf-event.c | 1 + tools/perf/util/event.c | 4 ++-- tools/perf/util/machine.c | 22 ++++++++-------------- tools/perf/util/maps.c | 17 ++++++++++------- tools/perf/util/symbol.c | 3 ++- 7 files changed, 26 insertions(+), 27 deletions(-) diff --git a/tools/perf/arch/x86/tests/dwarf-unwind.c b/tools/perf/arch/x86/tests/dwarf-unwind.c index 5bfec3345d59..c05c0a85dad4 100644 --- a/tools/perf/arch/x86/tests/dwarf-unwind.c +++ b/tools/perf/arch/x86/tests/dwarf-unwind.c @@ -34,6 +34,7 @@ static int sample_ustack(struct perf_sample *sample, } stack_size = map__end(map) - sp; + map__put(map); stack_size = stack_size > STACK_SIZE ? STACK_SIZE : stack_size; memcpy(buf, (void *) sp, stack_size); diff --git a/tools/perf/tests/vmlinux-kallsyms.c b/tools/perf/tests/vmlinux-kallsyms.c index 822f893e67d5..e808e6fc8f76 100644 --- a/tools/perf/tests/vmlinux-kallsyms.c +++ b/tools/perf/tests/vmlinux-kallsyms.c @@ -151,10 +151,8 @@ static int test__vmlinux_matches_kallsyms_cb2(struct map *map, void *data) u64 mem_end = map__unmap_ip(args->vmlinux_map, map__end(map)); pair = maps__find(args->kallsyms.kmaps, mem_start); - if (pair == NULL || map__priv(pair)) - return 0; - if (map__start(pair) == mem_start) { + if (pair != NULL && !map__priv(pair) && map__start(pair) == mem_start) { struct dso *dso = map__dso(map); if (!args->header_printed) { @@ -170,6 +168,7 @@ static int test__vmlinux_matches_kallsyms_cb2(struct map *map, void *data) pr_info(" %s\n", dso->name); map__set_priv(pair, 1); } + map__put(pair); return 0; } diff --git a/tools/perf/util/bpf-event.c b/tools/perf/util/bpf-event.c index 3573e0b7ef3e..83709146a48a 100644 --- a/tools/perf/util/bpf-event.c +++ b/tools/perf/util/bpf-event.c @@ -63,6 +63,7 @@ static int machine__process_bpf_event_load(struct machine *machine, dso->bpf_prog.id = id; dso->bpf_prog.sub_id = i; dso->bpf_prog.env = env; + map__put(map); } } return 0; diff --git a/tools/perf/util/event.c b/tools/perf/util/event.c index 68f45e9e63b6..198903157f9e 100644 --- a/tools/perf/util/event.c +++ b/tools/perf/util/event.c @@ -511,7 +511,7 @@ size_t perf_event__fprintf_text_poke(union perf_event *event, struct machine *ma struct addr_location al; addr_location__init(&al); - al.map = map__get(maps__find(machine__kernel_maps(machine), tp->addr)); + al.map = maps__find(machine__kernel_maps(machine), tp->addr); if (al.map && map__load(al.map) >= 0) { al.addr = map__map_ip(al.map, tp->addr); al.sym = map__find_symbol(al.map, al.addr); @@ -641,7 +641,7 @@ struct map *thread__find_map(struct thread *thread, u8 cpumode, u64 addr, return NULL; } al->maps = maps__get(maps); - al->map = map__get(maps__find(maps, al->addr)); + al->map = maps__find(maps, al->addr); if (al->map != NULL) { /* * Kernel maps might be changed when loading symbols so loading diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index b397a769006f..e8eb9f0b073f 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -896,7 +896,6 @@ static int machine__process_ksymbol_register(struct machine *machine, struct symbol *sym; struct dso *dso; struct map *map = maps__find(machine__kernel_maps(machine), event->ksymbol.addr); - bool put_map = false; int err = 0; if (!map) { @@ -913,12 +912,6 @@ static int machine__process_ksymbol_register(struct machine *machine, err = -ENOMEM; goto out; } - /* - * The inserted map has a get on it, we need to put to release - * the reference count here, but do it after all accesses are - * done. - */ - put_map = true; if (event->ksymbol.ksym_type == PERF_RECORD_KSYMBOL_TYPE_OOL) { dso->binary_type = DSO_BINARY_TYPE__OOL; dso->data.file_size = event->ksymbol.len; @@ -952,8 +945,7 @@ static int machine__process_ksymbol_register(struct machine *machine, } dso__insert_symbol(dso, sym); out: - if (put_map) - map__put(map); + map__put(map); return err; } @@ -977,7 +969,7 @@ static int machine__process_ksymbol_unregister(struct machine *machine, if (sym) dso__delete_symbol(dso, sym); } - + map__put(map); return 0; } @@ -1005,11 +997,11 @@ int machine__process_text_poke(struct machine *machine, union perf_event *event, perf_event__fprintf_text_poke(event, machine, stdout); if (!event->text_poke.new_len) - return 0; + goto out; if (cpumode != PERF_RECORD_MISC_KERNEL) { pr_debug("%s: unsupported cpumode - ignoring\n", __func__); - return 0; + goto out; } if (dso) { @@ -1032,7 +1024,8 @@ int machine__process_text_poke(struct machine *machine, union perf_event *event, pr_debug("Failed to find kernel text poke address map for %#" PRI_lx64 "\n", event->text_poke.addr); } - +out: + map__put(map); return 0; } @@ -1300,9 +1293,10 @@ static int machine__map_x86_64_entry_trampolines_cb(struct map *map, void *data) return 0; dest_map = maps__find(args->kmaps, map__pgoff(map)); - if (dest_map != map) + if (RC_CHK_ACCESS(dest_map) != RC_CHK_ACCESS(map)) map__set_pgoff(map, map__map_ip(dest_map, map__pgoff(map))); + map__put(dest_map); args->found = true; return 0; } diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 45da1ec3630c..3336d540c577 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -500,15 +500,18 @@ void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp) { struct map *map = maps__find(maps, addr); + struct symbol *result = NULL; /* Ensure map is loaded before using map->map_ip */ if (map != NULL && map__load(map) >= 0) { - if (mapp != NULL) - *mapp = map; // TODO: map_put on else path when find returns a get. - return map__find_symbol(map, map__map_ip(map, addr)); - } + if (mapp) + *mapp = map; - return NULL; + result = map__find_symbol(map, map__map_ip(map, addr)); + if (!mapp) + map__put(map); + } + return result; } struct maps__find_symbol_by_name_args { @@ -552,7 +555,7 @@ int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams) if (ams->addr < map__start(ams->ms.map) || ams->addr >= map__end(ams->ms.map)) { if (maps == NULL) return -1; - ams->ms.map = maps__find(maps, ams->addr); // TODO: map_get + ams->ms.map = maps__find(maps, ams->addr); if (ams->ms.map == NULL) return -1; } @@ -862,7 +865,7 @@ struct map *maps__find(struct maps *maps, u64 ip) sizeof(*mapp), map__addr_cmp); if (mapp) - result = *mapp; // map__get(*mapp); + result = map__get(*mapp); done = true; } up_read(maps__lock(maps)); diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c index be212ba157dc..1710b89e207c 100644 --- a/tools/perf/util/symbol.c +++ b/tools/perf/util/symbol.c @@ -757,7 +757,6 @@ static int dso__load_all_kallsyms(struct dso *dso, const char *filename) static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso) { - struct map *curr_map; struct symbol *pos; int count = 0; struct rb_root_cached old_root = dso->symbols; @@ -770,6 +769,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso) *root = RB_ROOT_CACHED; while (next) { + struct map *curr_map; struct dso *curr_map_dso; char *module; @@ -796,6 +796,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso) pos->end -= map__start(curr_map) - map__pgoff(curr_map); symbols__insert(&curr_map_dso->symbols, pos); ++count; + map__put(curr_map); } /* Symbols have been adjusted */ From patchwork Wed Feb 7 22:36:36 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198103 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546269dyb; Wed, 7 Feb 2024 14:38:33 -0800 (PST) X-Google-Smtp-Source: AGHT+IG/Gwrr8ZYYC9tubo62fsPHhoyHfMhxzt3EFwSmSjCiY2GGvRcTAXRdAyL8LknUKT4xk+jo X-Received: by 2002:a17:906:a2c2:b0:a31:3f4f:bea7 with SMTP id by2-20020a170906a2c200b00a313f4fbea7mr5453545ejb.39.1707345513428; Wed, 07 Feb 2024 14:38:33 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345513; cv=pass; d=google.com; s=arc-20160816; b=SpXbh+UV/Qh6KmioDmRFHSDfrKmV7//xCY8YBJSDldSJCTKbs4q4KeHR4KX+GckZBT VdMO3ED2j8rPMO7zAdG2OZXdzr9BYkuZxRZDa1tHvIK7790EmhndP7yS9aXSKey46FrB KEZBapTou1jLZkI2svTcmeVZEIeIQqez63XlB7pMBznDo/P/x65nvVK9D0Yg7NKUxqtQ So0idFBBG0zt29vow5JN6ewkKqvq773c9VTuh9kM8v/jw94WLDCQxBuz9x6nDtfON6Kt cqp+ckT+pX4GY9tfTRA+NOPxQduPx8erxfk0/jowkhe4L7gQ/GJLGM+IenYBEl3+hbv7 mxaA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=DWu8c5dtrh0uqi6zk1zlORUMaHx/FkkbOqGaT9PZG5U=; fh=/vO88YWExeWtduLBd3YoBSXc1cd5Pls1h/1MG1dpLtw=; b=HEvrK/yrbMCfdgkqSbdh1uydrYWwL29PgIRaG1yzWPmsaPRr5YL9sbwZ3tB00oU1q7 iJ7AUFaHltzDNUd+vGFficXYSlDxUOWF0ZXOxJZZVwz2kjM+yWQ73kYyLpSyFtOW+xgY 8eNqU9CWnyG1Heq1+NrGrn3fn0BwjF2U4T3BAhHSzTLlg8OZ3erDvndjH5aSwWJJ8uqT XqTTMyOgaD7sYU62IVQ459lFbrUWC5EW0Yptk/9SGeBXlAEOurtRBrbVVmo/Sk7tbZcG cbpH6c08Wfwkik2d+JBykFDiEyVEGJTBWbYRNEYLlgA/CC1AhLaBJ/v0VRxlyqanpfIG wjXQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=HRYwyFyU; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57262-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCWVssITpxN8xJ0KXWmVaIu8KbyWWDPnlaykpWfMB/fyNNt+M4/cA2LjzRtSK4+2X3cHkScp0uIX5Ayb40z11+3anyPv1g== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id fy10-20020a170906b7ca00b00a3a10915288si162748ejb.813.2024.02.07.14.38.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:38:33 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=HRYwyFyU; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57262-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id D6FD41F2526A for ; Wed, 7 Feb 2024 22:38:32 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 4A697692EE; Wed, 7 Feb 2024 22:37:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="HRYwyFyU" Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DECC0200DD for ; Wed, 7 Feb 2024 22:37:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345437; cv=none; b=LRS5bs+UFkiJq7DN4eb/XhrrpWiMICjZnMxgqWShOiUUfQeUnFTDxKmxta9uMIqwilE9GTPwPyCkutbooBKBwdKE0o6LCWgn5D1NVDwGcwBqnFWpnkGEfeeWTdvtG67C7xe1+xXBAQJfjHXKUqPWuiQGVs/KpVaOpXsxvCSG6iY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345437; c=relaxed/simple; bh=TNL0GOyieHu9AqHO4Zi22Cz7C0gAfBXx8CvzAmJoOYo=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=j5umKB8EhPVdzNiRAEOlPN3jFTRrO7aHHQdd2GNlNsIogWaLFF5MJygYP34gRbHTKdTZuapRN4LEvSa5EbBTFQv0AnNBSO0ArU3b7ZDtDYC4FUWR+NpCxgwMFF0IlZ3v5HPhYFwndsx+fS/euUd5sFKHENYgZGZ3B9//3VYUHRU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=HRYwyFyU; arc=none smtp.client-ip=209.85.219.202 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 Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-dc64e0fc7c8so1524160276.2 for ; Wed, 07 Feb 2024 14:37:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345433; x=1707950233; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=DWu8c5dtrh0uqi6zk1zlORUMaHx/FkkbOqGaT9PZG5U=; b=HRYwyFyU69czJRKCivZqZiq7RhaOEx20/xEPTDeGvUSoI8P3dbN9PoZ/IVptpOIrV+ J8AxjwxBZPnyGL0isz1j2S9dkVH7dLoq2K8LQBdGEfUak+sn1MATEM6MihbxE8Ar7VMk I0xc//gCMe87K5FXVouS4PPSzrZl71+xrMaDYdXEIZAc6h2Ok/33zf6eyh/Julq6xGnh HgYxREPPn8+FvDuNsO2qQ6vIQfcqztncKNKRFbddgKsNT77JsmMMyHry41idvM0LNrcw KPnCytB1lilVKoDz/oEKrorPRj9P545IBwxwntxriG/texI66ObC3AEKn9m/oGKbPHqd HR/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345433; x=1707950233; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=DWu8c5dtrh0uqi6zk1zlORUMaHx/FkkbOqGaT9PZG5U=; b=p1WwCJ2OCgGUGqs7xpD5eyex5M2pJLVsr7mynx5D9Gcw0ABudqtgCVWGOy0tLDvyWP UqDgVWjoQkAd+rIBvwjTkij7snuffSCfTSsHAX37Zyppu4uAhmtBb/HBRyrlk6DVx4kb knRbcVnvrLULTaqb2vJroBVIlAda/0SR2GjAmb1t01/UOeH6qnYQuSGKF7dEwbFuxkkl vO0xqML32Fah2n59VZeN9mYAfNnOKKDpvqFPaGDlnYfd8riMoCTf5sVC8GgdL0Aq4yjD oUABHlRw/kxsFMf8mhiG0OkAAjHjTrOURHLjMzv1702NwHfIaq+72kmfU6PkGwzPR+Am 0thw== X-Gm-Message-State: AOJu0YzmYXpWX8iXTV6JEivIlmh3HXPEy6vU6LqpTB4S75DbG8EFjxVU SeQ1Jdm9R2+Xb+EQKzEiib/D6REJ2TEjhNjrCOUgps7wOYmRP4oGrqi0n6Xf5CY5ZRP75RPUmvM J7Fy6Dg== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a05:6902:230d:b0:dc6:e077:18ff with SMTP id do13-20020a056902230d00b00dc6e07718ffmr276561ybb.1.1707345432908; Wed, 07 Feb 2024 14:37:12 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:36 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-4-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 3/6] perf maps: Get map before returning in maps__find_by_name From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281528769757563 X-GMAIL-MSGID: 1790281528769757563 Finding a map is done under a lock, returning the map without a reference count means it can be removed without notice and causing uses after free. Grab a reference count to the map within the lock region and return this. Fix up locations that need a map__put following this. Also fix some reference counted pointer comparisons. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/tests/vmlinux-kallsyms.c | 5 +++-- tools/perf/util/machine.c | 6 ++++-- tools/perf/util/maps.c | 6 +++--- tools/perf/util/probe-event.c | 1 + tools/perf/util/symbol-elf.c | 4 +++- tools/perf/util/symbol.c | 18 +++++++++++------- 6 files changed, 25 insertions(+), 15 deletions(-) diff --git a/tools/perf/tests/vmlinux-kallsyms.c b/tools/perf/tests/vmlinux-kallsyms.c index e808e6fc8f76..fecbf851bb2e 100644 --- a/tools/perf/tests/vmlinux-kallsyms.c +++ b/tools/perf/tests/vmlinux-kallsyms.c @@ -131,9 +131,10 @@ static int test__vmlinux_matches_kallsyms_cb1(struct map *map, void *data) struct map *pair = maps__find_by_name(args->kallsyms.kmaps, (dso->kernel ? dso->short_name : dso->name)); - if (pair) + if (pair) { map__set_priv(pair, 1); - else { + map__put(pair); + } else { if (!args->header_printed) { pr_info("WARN: Maps only in vmlinux:\n"); args->header_printed = true; diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index e8eb9f0b073f..7031f6fddcae 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -1537,8 +1537,10 @@ static int maps__set_module_path(struct maps *maps, const char *path, struct kmo return 0; long_name = strdup(path); - if (long_name == NULL) + if (long_name == NULL) { + map__put(map); return -ENOMEM; + } dso = map__dso(map); dso__set_long_name(dso, long_name, true); @@ -1552,7 +1554,7 @@ static int maps__set_module_path(struct maps *maps, const char *path, struct kmo dso->symtab_type++; dso->comp = m->comp; } - + map__put(map); return 0; } diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 3336d540c577..f4855e2bfd6e 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -899,7 +899,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name) struct dso *dso = map__dso(maps__maps_by_name(maps)[i]); if (dso && strcmp(dso->short_name, name) == 0) { - result = maps__maps_by_name(maps)[i]; // TODO: map__get + result = map__get(maps__maps_by_name(maps)[i]); done = true; } } @@ -911,7 +911,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name) sizeof(*mapp), map__strcmp_name); if (mapp) { - result = *mapp; // TODO: map__get + result = map__get(*mapp); i = mapp - maps__maps_by_name(maps); RC_CHK_ACCESS(maps)->last_search_by_name_idx = i; } @@ -936,7 +936,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name) struct dso *dso = map__dso(pos); if (dso && strcmp(dso->short_name, name) == 0) { - result = pos; // TODO: map__get + result = map__get(pos); break; } } diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c index a1a796043691..be71abe8b9b0 100644 --- a/tools/perf/util/probe-event.c +++ b/tools/perf/util/probe-event.c @@ -358,6 +358,7 @@ static int kernel_get_module_dso(const char *module, struct dso **pdso) map = maps__find_by_name(machine__kernel_maps(host_machine), module_name); if (map) { dso = map__dso(map); + map__put(map); goto found; } pr_debug("Failed to find module %s.\n", module); diff --git a/tools/perf/util/symbol-elf.c b/tools/perf/util/symbol-elf.c index 4b934ed3bfd1..5990e3fabdb5 100644 --- a/tools/perf/util/symbol-elf.c +++ b/tools/perf/util/symbol-elf.c @@ -1470,8 +1470,10 @@ static int dso__process_kernel_symbol(struct dso *dso, struct map *map, dso__set_loaded(curr_dso); *curr_mapp = curr_map; *curr_dsop = curr_dso; - } else + } else { *curr_dsop = map__dso(curr_map); + map__put(curr_map); + } return 0; } diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c index 1710b89e207c..0785a54e832e 100644 --- a/tools/perf/util/symbol.c +++ b/tools/perf/util/symbol.c @@ -814,7 +814,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, struct map *initial_map) { struct machine *machine; - struct map *curr_map = initial_map; + struct map *curr_map = map__get(initial_map); struct symbol *pos; int count = 0, moved = 0; struct rb_root_cached *root = &dso->symbols; @@ -858,13 +858,14 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, dso__set_loaded(curr_map_dso); } + map__zput(curr_map); curr_map = maps__find_by_name(kmaps, module); if (curr_map == NULL) { pr_debug("%s/proc/{kallsyms,modules} " "inconsistency while looking " "for \"%s\" module!\n", machine->root_dir, module); - curr_map = initial_map; + curr_map = map__get(initial_map); goto discard_symbol; } curr_map_dso = map__dso(curr_map); @@ -888,7 +889,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, * symbols at this point. */ goto discard_symbol; - } else if (curr_map != initial_map) { + } else if (!RC_CHK_EQUAL(curr_map, initial_map)) { char dso_name[PATH_MAX]; struct dso *ndso; @@ -899,7 +900,8 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, } if (count == 0) { - curr_map = initial_map; + map__zput(curr_map); + curr_map = map__get(initial_map); goto add_symbol; } @@ -913,6 +915,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, kernel_range++); ndso = dso__new(dso_name); + map__zput(curr_map); if (ndso == NULL) return -1; @@ -926,6 +929,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, map__set_mapping_type(curr_map, MAPPING_TYPE__IDENTITY); if (maps__insert(kmaps, curr_map)) { + map__zput(curr_map); dso__put(ndso); return -1; } @@ -936,7 +940,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, pos->end -= delta; } add_symbol: - if (curr_map != initial_map) { + if (!RC_CHK_EQUAL(curr_map, initial_map)) { struct dso *curr_map_dso = map__dso(curr_map); rb_erase_cached(&pos->rb_node, root); @@ -951,12 +955,12 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, symbol__delete(pos); } - if (curr_map != initial_map && + if (!RC_CHK_EQUAL(curr_map, initial_map) && dso->kernel == DSO_SPACE__KERNEL_GUEST && machine__is_default_guest(maps__machine(kmaps))) { dso__set_loaded(map__dso(curr_map)); } - + map__put(curr_map); return count + moved; } From patchwork Wed Feb 7 22:36:37 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198104 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546336dyb; Wed, 7 Feb 2024 14:38:44 -0800 (PST) X-Google-Smtp-Source: AGHT+IHXhenKI6Fh/M4oJ6KiGbMtVtDbr7w8uyhkl+hg/ClR07PNOZaZyme8iNMiqPWNpVRUjd2F X-Received: by 2002:a0c:f584:0:b0:68c:b64a:dc88 with SMTP id k4-20020a0cf584000000b0068cb64adc88mr5855930qvm.41.1707345524835; Wed, 07 Feb 2024 14:38:44 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345524; cv=pass; d=google.com; s=arc-20160816; b=WXAYnPrYrCshAppfFiDLBhkjj5ZmS7T2mEeCIpJ15IERH3kBysGiWxN5UfRk7c/u6z lcyUyTnf8RBEtZocGm8X7+YtHnqRKhs+cnNqGSI90h87az5L90mXYTswbyBRqdOJy1lO SRwf5IdbbUTB8WP3PryfDmwUUslV72MTSEWXhk48eOkFU/cPT8Z27N1XQAC9NIsqZfYf SEvEhB0xyDzAvX1bWFXO+Q2wvveukiKmjw8xgyMwUK1OMZRIcGdOnaneuHkqDZRR4TD8 82qJ1GaMTebjvCOLEwjpY99UpTBZQJfASoyM352t+mJiAp2C7l264pv9mIsmGC1cTPsG rLdg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=Ay5pESXQDW6zysG3DCALcAImBiyx5FS+UI74K+BRnd8=; fh=s1iSawccJXeuQW8HaegLMk2YNcRz09J6fH6nAWB0Y9E=; b=AIq1hLdcn8MYQtQ61hpzJuQDsbQnWAAnuOykNDqtLFR+GG4oxZfvBIm8NNLys1TwMo Lug9NwjZVLcQnP6gu7xOQ5BFRfpxnn4bRQm7zbGBx0R3OGhu9vbT6Ib90LNI4hAcDzrX yMI+hAivl+qxsm39y6eAEQf/HvpZBFd1nUNNaql6G1hJRG7uUsC2jO+Egv5M246MipGU WzSkyQfVmHt5cywLILHW+JDFgJaMxFaFcyPfUsJT1E3/cYJ5ZrgjpI2LyuOPti00zPPu +cECY6VYjpFSPdCvka6d6EWT4HKYKLDylWW7OIEUxpY4aieEWLLoUh/I7f/3VOUweHuy au8w==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=dQsXdthF; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57263-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57263-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCWAI1zuUyCqseWLMK9aOvT2qv82d83R4R11HcXleKkx2g12s7kolXg08Q7Ok/RG9NQV4bPIcfxcHnETU3VqXZC2t5/Y7A== Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id c8-20020ad44308000000b0068c891918e6si1988874qvs.93.2024.02.07.14.38.44 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:38:44 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57263-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=dQsXdthF; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57263-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57263-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id 7C21E1C236D4 for ; Wed, 7 Feb 2024 22:38:44 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 8825869301; Wed, 7 Feb 2024 22:37:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="dQsXdthF" Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 57FE620325 for ; Wed, 7 Feb 2024 22:37:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345439; cv=none; b=OlyBu+6glP72dwSxhBd5ADFCfMDduB8Dnble1nrBn8zwkiv4dy1EmkUVpWNhr9mUWh+DSYl86reA9MbqsZFW9/l4KHupMMAdBf2hVp4dy5dSPCMIeTELXG9cYjk5c68k2K1olGL5XxwrvdEewSU83VrtT6VDc62iIAMgplwlMOU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345439; c=relaxed/simple; bh=5X1qsUi3skYX0+XJLWX/k8pq64P7f+cfj6l98r2VoJ8=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=FofxzU4jIvWztczqte7xK5USDpMjrdnFPVCjH1xde7lsyhCEDcw6gx4O7eHIQyslo84LsKxhnsqiQ8Vq4DOM96pd+jfOT+tT4PJndN9+bL4ZhgsbO2eYB9RZizE+1uXCeExmwfk73eZHIv7KmFSY9aD44poTzBtYXxhGPO5CeCg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=dQsXdthF; arc=none smtp.client-ip=209.85.219.201 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 Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dc6bad01539so1673034276.3 for ; Wed, 07 Feb 2024 14:37:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345435; x=1707950235; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=Ay5pESXQDW6zysG3DCALcAImBiyx5FS+UI74K+BRnd8=; b=dQsXdthF7lP2EUNImu/ot0FOmbNBfIXa3gz4jhwCDy48qoxUU/n06nNnBW06ewwqB2 Svu6OZZoJqWdZdvhrh4U1QWvoNQjaRcEry0Iao/ARGbGn9axVs1PQnh9SveHx/365CPl HyN3yqNNXnf4x0nDTJ+s54A4JKc7G3KJrXZVGvBLkVCdBs6eJ84QdE2kwyomIX/oVJs9 7oY5KeRaTuccN2DexDY+8Dw+l7Eq9VhlGUi9QtWJDBi3+dHE3UypRfn890j06zJ7ri2Y B0SgmJn68FzCicJU5Xl9ITwK3FVB0TubEQ0iuDTKO3OmEkSmq4YUk5UK05WYPIElsLSz FbOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345435; x=1707950235; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=Ay5pESXQDW6zysG3DCALcAImBiyx5FS+UI74K+BRnd8=; b=r18ltK7XMOCSW6YMWex6Hi6tK8SpZ2p9sAmbs8tILHhMa+aFQ9H7a/DnbWlcGxuQk7 tpSXh7OeKZEN2aOhDRg/e1nf6ml7VfZ4joQfOFY10ed5MW5pjow8O0pCHOao8V0WabBU GMxF79w2pRD3R5i5X/JlUc+4tg9WB3mo7VxptrOFvMvvTPjWbbeyJfeGiKfVoNUBt4qJ QtmRuho+JmMW+vWDJMWetsZV0WSUzi3uduc7UYOpIyuJ5i4lVB26olIAQ6zKF9OcRCsS Ki2y32j3IZmzZN2s8EibDb4+I11UiBcTUrDzE548OrbDRwbuo24+1oazvdWgKuDXf1Fc +wAA== X-Gm-Message-State: AOJu0YwaFoQ/Fj0YpfD57Hh9sA6Al43rXEZsj4thzetrjgUiBt+FfRHc jiBNUiI0f3rACrhIccRk4fOO1HwUsatq5Dp1TKqwrunYpu2PmpxZJcQDIRwOUUYxk98AGaAwwva Lq1cIkA== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a05:6902:2205:b0:dbe:387d:a8ef with SMTP id dm5-20020a056902220500b00dbe387da8efmr230404ybb.1.1707345435298; Wed, 07 Feb 2024 14:37:15 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:37 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-5-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 4/6] perf maps: Get map before returning in maps__find_next_entry From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281541163591794 X-GMAIL-MSGID: 1790281541163591794 Finding a map is done under a lock, returning the map without a reference count means it can be removed without notice and causing uses after free. Grab a reference count to the map within the lock region and return this. Fix up locations that need a map__put following this. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/util/machine.c | 4 +++- tools/perf/util/maps.c | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index 7031f6fddcae..4911734411b5 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -1761,8 +1761,10 @@ int machine__create_kernel_maps(struct machine *machine) struct map *next = maps__find_next_entry(machine__kernel_maps(machine), machine__kernel_map(machine)); - if (next) + if (next) { machine__set_kernel_mmap(machine, start, map__start(next)); + map__put(next); + } } out_put: diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index f4855e2bfd6e..e577909456be 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -956,7 +956,7 @@ struct map *maps__find_next_entry(struct maps *maps, struct map *map) down_read(maps__lock(maps)); i = maps__by_address_index(maps, map); if (i < maps__nr_maps(maps)) - result = maps__maps_by_address(maps)[i]; // TODO: map__get + result = map__get(maps__maps_by_address(maps)[i]); up_read(maps__lock(maps)); return result; From patchwork Wed Feb 7 22:36:38 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198107 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546565dyb; Wed, 7 Feb 2024 14:39:18 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUNcjC5DfNPwztaDOvQDIHc0p10N5N06c2IIh6+dA5jtW+1x4yiD86z+ts4IHvROn/XefNKv7NaoCrfQDKeQyRR4rvDkg== X-Google-Smtp-Source: AGHT+IHnVuJWk6rk9R8AvgNNjo7C1+1IiRXXtyCU+0EDuWYpeCHpaZ3moZKrMFXdbLc5lf74SRA/ X-Received: by 2002:a05:620a:22f:b0:783:1522:fa89 with SMTP id u15-20020a05620a022f00b007831522fa89mr6253666qkm.47.1707345558305; Wed, 07 Feb 2024 14:39:18 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345558; cv=pass; d=google.com; s=arc-20160816; b=vNv2y3yAesCeBbLjQn7dwbuuUkC6JsdFtNyXSE+p/s8U4Nx/rW0dvDMX75UDh3d6/b JSWr0DywZTLi24AvxG/qu2XbTD0XgBvcbFzQXicUnNfUsR9jo26TePopZM/fQwEf7JWP odtMudfTm4ThJJuQtBBm6n0rENagHcG/OK58ftDshaA7enZwtISZjqzGhyLLWRxYw/2l tyi0E7RVnxMWNOMTV7iQcCWQxxEBMgObY33AZ3tI3aBIV602a3LHJqqHL7qCBNflv8G0 ONfwhGVqb7ydbR/TjWF89ocuieKD61WZv1MHSQ2jg6RkOCoNRHUvuRyLy7idOPoSCVGJ Nm5Q== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=uQl/CtWhXq1dWPMr/OrlBn5Ajy8Sb3JsjVXhwVRHryc=; fh=MdzV0OYGRWN9upRzbdMM0suui5+8GA9HWcl4qdxzoUU=; b=IrYv3RcAO+GoWkJDNdEcRYK8Nzxkg8Fs8ZNXN2urA5O3XVwY7bJxI7yzhgJBN2W2MS 7m9c4d2jYEMt0SWvmEmuZHsyZ4BfjQL2v7J05h4RbGzCSY9uL7yyAsXChimvJu+ILJBy SQN6fAKtBBatzSsjoh76AVp8cR0DshojScKCxW2EITylmvqPZT5CzyWTxPf1NFhA8BVC 6FEZBZvIkkf6m0YxhPLlURiVpuNKiI3r7OTc0ergviyVVnyA7ydh6ydNI/9f7jhIsoRg owuH+AA7bp312YBEZ8t3olwmrfvZMJ7NgIx2T+b+3ZK0RSOj7qUOTXS0VLxZsQ65/hIZ klqg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=eRwH52gp; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57264-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57264-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCVMedIXKS9YHoZGtfXRQ0HTkh4z9ENzHMYwOx1bTl6WfA+VeROQjimk634lXasZPkfRaHVxc3P8/fkSMc1Z3f4mmkygHg== Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id t30-20020a05620a005e00b0078560c46784si2032552qkt.425.2024.02.07.14.39.18 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:39:18 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57264-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=eRwH52gp; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57264-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57264-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id 0D11A1C22CB6 for ; Wed, 7 Feb 2024 22:39:18 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 95F876A8C1; Wed, 7 Feb 2024 22:37:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="eRwH52gp" Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BEB4B200DE for ; Wed, 7 Feb 2024 22:37:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345440; cv=none; b=P/5nvevhivVPz0eiojQU0A8jxmj/aD+S36Ar7mMx9vi/bGQrMyDnWuv367N4abYn2kKR2ZgATHcQej1sRVY6RZr49ih2qAUXEYYG5cPbxwEQVNdm6O11BLTKIYDVEqWNpsArrHs7dY9l87Aohpdg8QGqgFTERNjwXjSMASy/qf4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345440; c=relaxed/simple; bh=iOa82TVY8Lxs5/Tfry/dbuUTLdsx8J4d/aMHsZ9BXSU=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=gIbB2csOHL22VLZwzp+yvqSuCynwL4U80UyvGh5RXaQbFgO6CZWv6FbBYipgOQDg03L+ykdqaMtn9H7I9JTTCYyIKi7fUjE5M4Y9dXl3P8PlySMVwjbDvP68OFW7P6vWoYGAhIJW3eSKojIBkYLpFv/sPrtbGgt/i6MCT8RENE0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=eRwH52gp; arc=none smtp.client-ip=209.85.219.201 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 Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dc6cd00633dso1724499276.3 for ; Wed, 07 Feb 2024 14:37:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345438; x=1707950238; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=uQl/CtWhXq1dWPMr/OrlBn5Ajy8Sb3JsjVXhwVRHryc=; b=eRwH52gpGf2LC0G/5h7sNEDxNQOAjUGWbkmCaMwtlF72G5D7pofuhl7fHT+ozMtkjy ywnjYi2ehJA3kUqFarQ5+MSCs9dvV8Ax6oSADhdkjKKx5Sez4aozbcJoEvUjpol8rHgm vWraH6W9uzS8durQOVd9ul8B8PfqOwIxyyViV+h+oUNXCK7CJjwamwoTXY3mvnIluqqE OJBc+AfvRShHUy+CiuEggxfDwIrzmaKPs9GoPpqHaOriEC66lxGFUwP6a+eVz3L0QusR qKDFYNu5ihD+sYNoch9cDI0t6wwqh/QVOKIPI9ksh0UnZkFq1WAY55iF2ZRp0/WdrVmK cxGA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345438; x=1707950238; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=uQl/CtWhXq1dWPMr/OrlBn5Ajy8Sb3JsjVXhwVRHryc=; b=BuqyBvE6KTk+6hVdpeUs7LxZYdYl10H9L9+Ib4q+DWBKw2MAKdQtvcMOUFkK2fblWa FHcFqueZqjjcdoy49MOxNbJCU6nXwGOEyeEf5pp9bmiSoR9RANE020cNJQ6pK3i5XnQv s9zWq+M229Uh5534giG9aEp4frYEdpTzdgit+s4TdiHJSFxjSAKT65z89LXIsDG9FB8E XuAdeiZn3aud7mrKwrM9RkbMFgi9M/1/quJuBCmmVLZ10YlWliyVmNqTPIuhgEfhJwhF qYAM/JgYP2n4N80Xd1EcqqM08jGDn3o7KbIQh71b1PiZvVwUb2RCUi3v5J1P12Rd4uxR jo6w== X-Forwarded-Encrypted: i=1; AJvYcCWvUlCndoGqOP/L9jk11T3kwKO3+/MQYUyjkZyjCJ3nGVSwERaDTN2f0umI6WjtcKjj23eUBOh4H3jRXkfqcXcT/S1+8YvmibYqYZaY X-Gm-Message-State: AOJu0YzogWN+92b8BQKkMQkw3SksxrxiPN/0HZBnDcxeQECU1WM9lgfU qZNlBfVmpXgZQTaeYosE7boW5LLfoRZi4aUpvOgP9vXlCZ9c3xZNnFfX2/TcN5wGVzrw5sEv3CD 8ZOD+gw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a05:6902:2102:b0:dc6:eb86:c422 with SMTP id dk2-20020a056902210200b00dc6eb86c422mr276674ybb.5.1707345437804; Wed, 07 Feb 2024 14:37:17 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:38 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-6-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 5/6] perf maps: Hide maps internals From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281575973877399 X-GMAIL-MSGID: 1790281575973877399 Move the struct into the C file. Add maps__equal to work around exposing the struct for reference count checking. Add accessors for the unwind_libunwind_ops. Move maps_list_node to its only use in symbol.c. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/tests/thread-maps-share.c | 8 +- tools/perf/util/callchain.c | 2 +- tools/perf/util/maps.c | 96 +++++++++++++++++++++++ tools/perf/util/maps.h | 97 +++--------------------- tools/perf/util/symbol.c | 10 +++ tools/perf/util/thread.c | 2 +- tools/perf/util/unwind-libdw.c | 2 +- tools/perf/util/unwind-libunwind-local.c | 2 +- tools/perf/util/unwind-libunwind.c | 7 +- 9 files changed, 124 insertions(+), 102 deletions(-) diff --git a/tools/perf/tests/thread-maps-share.c b/tools/perf/tests/thread-maps-share.c index 7fa6f7c568e2..e9ecd30a5c05 100644 --- a/tools/perf/tests/thread-maps-share.c +++ b/tools/perf/tests/thread-maps-share.c @@ -46,9 +46,9 @@ static int test__thread_maps_share(struct test_suite *test __maybe_unused, int s TEST_ASSERT_EQUAL("wrong refcnt", refcount_read(maps__refcnt(maps)), 4); /* test the maps pointer is shared */ - TEST_ASSERT_VAL("maps don't match", RC_CHK_EQUAL(maps, thread__maps(t1))); - TEST_ASSERT_VAL("maps don't match", RC_CHK_EQUAL(maps, thread__maps(t2))); - TEST_ASSERT_VAL("maps don't match", RC_CHK_EQUAL(maps, thread__maps(t3))); + TEST_ASSERT_VAL("maps don't match", maps__equal(maps, thread__maps(t1))); + TEST_ASSERT_VAL("maps don't match", maps__equal(maps, thread__maps(t2))); + TEST_ASSERT_VAL("maps don't match", maps__equal(maps, thread__maps(t3))); /* * Verify the other leader was created by previous call. @@ -73,7 +73,7 @@ static int test__thread_maps_share(struct test_suite *test __maybe_unused, int s other_maps = thread__maps(other); TEST_ASSERT_EQUAL("wrong refcnt", refcount_read(maps__refcnt(other_maps)), 2); - TEST_ASSERT_VAL("maps don't match", RC_CHK_EQUAL(other_maps, thread__maps(other_leader))); + TEST_ASSERT_VAL("maps don't match", maps__equal(other_maps, thread__maps(other_leader))); /* release thread group */ thread__put(t3); diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c index 8262f69118db..7517d16c02ec 100644 --- a/tools/perf/util/callchain.c +++ b/tools/perf/util/callchain.c @@ -1157,7 +1157,7 @@ int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node * if (al->map == NULL) goto out; } - if (RC_CHK_EQUAL(al->maps, machine__kernel_maps(machine))) { + if (maps__equal(al->maps, machine__kernel_maps(machine))) { if (machine__is_host(machine)) { al->cpumode = PERF_RECORD_MISC_KERNEL; al->level = 'k'; diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index e577909456be..0ab19e1de190 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -6,9 +6,63 @@ #include "dso.h" #include "map.h" #include "maps.h" +#include "rwsem.h" #include "thread.h" #include "ui/ui.h" #include "unwind.h" +#include + +/* + * Locking/sorting note: + * + * Sorting is done with the write lock, iteration and binary searching happens + * under the read lock requiring being sorted. There is a race between sorting + * releasing the write lock and acquiring the read lock for iteration/searching + * where another thread could insert and break the sorting of the maps. In + * practice inserting maps should be rare meaning that the race shouldn't lead + * to live lock. Removal of maps doesn't break being sorted. + */ + +DECLARE_RC_STRUCT(maps) { + struct rw_semaphore lock; + /** + * @maps_by_address: array of maps sorted by their starting address if + * maps_by_address_sorted is true. + */ + struct map **maps_by_address; + /** + * @maps_by_name: optional array of maps sorted by their dso name if + * maps_by_name_sorted is true. + */ + struct map **maps_by_name; + struct machine *machine; +#ifdef HAVE_LIBUNWIND_SUPPORT + void *addr_space; + const struct unwind_libunwind_ops *unwind_libunwind_ops; +#endif + refcount_t refcnt; + /** + * @nr_maps: number of maps_by_address, and possibly maps_by_name, + * entries that contain maps. + */ + unsigned int nr_maps; + /** + * @nr_maps_allocated: number of entries in maps_by_address and possibly + * maps_by_name. + */ + unsigned int nr_maps_allocated; + /** + * @last_search_by_name_idx: cache of last found by name entry's index + * as frequent searches for the same dso name are common. + */ + unsigned int last_search_by_name_idx; + /** @maps_by_address_sorted: is maps_by_address sorted. */ + bool maps_by_address_sorted; + /** @maps_by_name_sorted: is maps_by_name sorted. */ + bool maps_by_name_sorted; + /** @ends_broken: does the map contain a map where end values are unset/unsorted? */ + bool ends_broken; +}; static void check_invariants(const struct maps *maps __maybe_unused) { @@ -118,6 +172,43 @@ static void maps__set_maps_by_name_sorted(struct maps *maps, bool value) RC_CHK_ACCESS(maps)->maps_by_name_sorted = value; } +struct machine *maps__machine(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->machine; +} + +unsigned int maps__nr_maps(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->nr_maps; +} + +refcount_t *maps__refcnt(struct maps *maps) +{ + return &RC_CHK_ACCESS(maps)->refcnt; +} + +#ifdef HAVE_LIBUNWIND_SUPPORT +void *maps__addr_space(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->addr_space; +} + +void maps__set_addr_space(struct maps *maps, void *addr_space) +{ + RC_CHK_ACCESS(maps)->addr_space = addr_space; +} + +const struct unwind_libunwind_ops *maps__unwind_libunwind_ops(const struct maps *maps) +{ + return RC_CHK_ACCESS(maps)->unwind_libunwind_ops; +} + +void maps__set_unwind_libunwind_ops(struct maps *maps, const struct unwind_libunwind_ops *ops) +{ + RC_CHK_ACCESS(maps)->unwind_libunwind_ops = ops; +} +#endif + static struct rw_semaphore *maps__lock(struct maps *maps) { /* @@ -453,6 +544,11 @@ bool maps__empty(struct maps *maps) return maps__nr_maps(maps) == 0; } +bool maps__equal(struct maps *a, struct maps *b) +{ + return RC_CHK_EQUAL(a, b); +} + int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data) { bool done = false; diff --git a/tools/perf/util/maps.h b/tools/perf/util/maps.h index df9dd5a0e3c0..4bcba136ffe5 100644 --- a/tools/perf/util/maps.h +++ b/tools/perf/util/maps.h @@ -3,80 +3,15 @@ #define __PERF_MAPS_H #include -#include #include #include #include -#include "rwsem.h" -#include struct ref_reloc_sym; struct machine; struct map; struct maps; -struct map_list_node { - struct list_head node; - struct map *map; -}; - -static inline struct map_list_node *map_list_node__new(void) -{ - return malloc(sizeof(struct map_list_node)); -} - -/* - * Locking/sorting note: - * - * Sorting is done with the write lock, iteration and binary searching happens - * under the read lock requiring being sorted. There is a race between sorting - * releasing the write lock and acquiring the read lock for iteration/searching - * where another thread could insert and break the sorting of the maps. In - * practice inserting maps should be rare meaning that the race shouldn't lead - * to live lock. Removal of maps doesn't break being sorted. - */ - -DECLARE_RC_STRUCT(maps) { - struct rw_semaphore lock; - /** - * @maps_by_address: array of maps sorted by their starting address if - * maps_by_address_sorted is true. - */ - struct map **maps_by_address; - /** - * @maps_by_name: optional array of maps sorted by their dso name if - * maps_by_name_sorted is true. - */ - struct map **maps_by_name; - struct machine *machine; -#ifdef HAVE_LIBUNWIND_SUPPORT - void *addr_space; - const struct unwind_libunwind_ops *unwind_libunwind_ops; -#endif - refcount_t refcnt; - /** - * @nr_maps: number of maps_by_address, and possibly maps_by_name, - * entries that contain maps. - */ - unsigned int nr_maps; - /** - * @nr_maps_allocated: number of entries in maps_by_address and possibly - * maps_by_name. - */ - unsigned int nr_maps_allocated; - /** - * @last_search_by_name_idx: cache of last found by name entry's index - * as frequent searches for the same dso name are common. - */ - unsigned int last_search_by_name_idx; - /** @maps_by_address_sorted: is maps_by_address sorted. */ - bool maps_by_address_sorted; - /** @maps_by_name_sorted: is maps_by_name sorted. */ - bool maps_by_name_sorted; - /** @ends_broken: does the map contain a map where end values are unset/unsorted? */ - bool ends_broken; -}; - #define KMAP_NAME_LEN 256 struct kmap { @@ -100,36 +35,22 @@ static inline void __maps__zput(struct maps **map) #define maps__zput(map) __maps__zput(&map) +bool maps__equal(struct maps *a, struct maps *b); + /* Iterate over map calling cb for each entry. */ int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data); /* Iterate over map removing an entry if cb returns true. */ void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data); -static inline struct machine *maps__machine(struct maps *maps) -{ - return RC_CHK_ACCESS(maps)->machine; -} - -static inline unsigned int maps__nr_maps(const struct maps *maps) -{ - return RC_CHK_ACCESS(maps)->nr_maps; -} - -static inline refcount_t *maps__refcnt(struct maps *maps) -{ - return &RC_CHK_ACCESS(maps)->refcnt; -} +struct machine *maps__machine(const struct maps *maps); +unsigned int maps__nr_maps(const struct maps *maps); +refcount_t *maps__refcnt(struct maps *maps); #ifdef HAVE_LIBUNWIND_SUPPORT -static inline void *maps__addr_space(struct maps *maps) -{ - return RC_CHK_ACCESS(maps)->addr_space; -} - -static inline const struct unwind_libunwind_ops *maps__unwind_libunwind_ops(const struct maps *maps) -{ - return RC_CHK_ACCESS(maps)->unwind_libunwind_ops; -} +void *maps__addr_space(const struct maps *maps); +void maps__set_addr_space(struct maps *maps, void *addr_space); +const struct unwind_libunwind_ops *maps__unwind_libunwind_ops(const struct maps *maps); +void maps__set_unwind_libunwind_ops(struct maps *maps, const struct unwind_libunwind_ops *ops); #endif size_t maps__fprintf(struct maps *maps, FILE *fp); diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c index 0785a54e832e..35975189999b 100644 --- a/tools/perf/util/symbol.c +++ b/tools/perf/util/symbol.c @@ -63,6 +63,16 @@ struct symbol_conf symbol_conf = { .res_sample = 0, }; +struct map_list_node { + struct list_head node; + struct map *map; +}; + +static struct map_list_node *map_list_node__new(void) +{ + return malloc(sizeof(struct map_list_node)); +} + static enum dso_binary_type binary_type_symtab[] = { DSO_BINARY_TYPE__KALLSYMS, DSO_BINARY_TYPE__GUEST_KALLSYMS, diff --git a/tools/perf/util/thread.c b/tools/perf/util/thread.c index 89c47a5098e2..c59ab4d79163 100644 --- a/tools/perf/util/thread.c +++ b/tools/perf/util/thread.c @@ -383,7 +383,7 @@ static int thread__clone_maps(struct thread *thread, struct thread *parent, bool if (thread__pid(thread) == thread__pid(parent)) return thread__prepare_access(thread); - if (RC_CHK_EQUAL(thread__maps(thread), thread__maps(parent))) { + if (maps__equal(thread__maps(thread), thread__maps(parent))) { pr_debug("broken map groups on thread %d/%d parent %d/%d\n", thread__pid(thread), thread__tid(thread), thread__pid(parent), thread__tid(parent)); diff --git a/tools/perf/util/unwind-libdw.c b/tools/perf/util/unwind-libdw.c index 6013335a8dae..b38d322734b4 100644 --- a/tools/perf/util/unwind-libdw.c +++ b/tools/perf/util/unwind-libdw.c @@ -263,7 +263,7 @@ int unwind__get_entries(unwind_entry_cb_t cb, void *arg, struct unwind_info *ui, ui_buf = { .sample = data, .thread = thread, - .machine = RC_CHK_ACCESS(thread__maps(thread))->machine, + .machine = maps__machine((thread__maps(thread))), .cb = cb, .arg = arg, .max_stack = max_stack, diff --git a/tools/perf/util/unwind-libunwind-local.c b/tools/perf/util/unwind-libunwind-local.c index dac536e28360..6a5ac0faa6f4 100644 --- a/tools/perf/util/unwind-libunwind-local.c +++ b/tools/perf/util/unwind-libunwind-local.c @@ -706,7 +706,7 @@ static int _unwind__prepare_access(struct maps *maps) { void *addr_space = unw_create_addr_space(&accessors, 0); - RC_CHK_ACCESS(maps)->addr_space = addr_space; + maps__set_addr_space(maps, addr_space); if (!addr_space) { pr_err("unwind: Can't create unwind address space.\n"); return -ENOMEM; diff --git a/tools/perf/util/unwind-libunwind.c b/tools/perf/util/unwind-libunwind.c index 76cd63de80a8..2728eb4f13ea 100644 --- a/tools/perf/util/unwind-libunwind.c +++ b/tools/perf/util/unwind-libunwind.c @@ -12,11 +12,6 @@ struct unwind_libunwind_ops __weak *local_unwind_libunwind_ops; struct unwind_libunwind_ops __weak *x86_32_unwind_libunwind_ops; struct unwind_libunwind_ops __weak *arm64_unwind_libunwind_ops; -static void unwind__register_ops(struct maps *maps, struct unwind_libunwind_ops *ops) -{ - RC_CHK_ACCESS(maps)->unwind_libunwind_ops = ops; -} - int unwind__prepare_access(struct maps *maps, struct map *map, bool *initialized) { const char *arch; @@ -60,7 +55,7 @@ int unwind__prepare_access(struct maps *maps, struct map *map, bool *initialized return 0; } out_register: - unwind__register_ops(maps, ops); + maps__set_unwind_libunwind_ops(maps, ops); err = maps__unwind_libunwind_ops(maps)->prepare_access(maps); if (initialized) From patchwork Wed Feb 7 22:36:39 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 198105 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp2546543dyb; Wed, 7 Feb 2024 14:39:14 -0800 (PST) X-Google-Smtp-Source: AGHT+IEAONgejOCKxKYqbUS5i13XMlsD3iRV14AvoRe5BgKxfOKxJwo2T6dY5wG2AgnCchh+l0Ik X-Received: by 2002:a05:6402:149a:b0:55f:c3c1:34e with SMTP id e26-20020a056402149a00b0055fc3c1034emr4479694edv.15.1707345554565; Wed, 07 Feb 2024 14:39:14 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707345554; cv=pass; d=google.com; s=arc-20160816; b=b1+FucLDi5vtmFc0ZDUdl50jc2wCGlux9j2gAEIy2pl62uPaL2vi2N3ESaN7E1h9wv oyN5CdVk/eWJIZ/FkyfdE5iL6E6INuHQOLK7Z0a5xOHa51lkCFuViT3hBGFoz3eyokEX ARuTR7ZhfN7jSMNT0Hsgm+1iWbiGETzyP29ng0pI00AEBtLZ8VzjVxzHEYhcWqqplyx4 9opfpM+xvfS0ZXQnu25H1TsQLPP8tmAzvVMVkA8TlJ91MElCX+Ndx8C6dYU4cjZ3puoc WISlGQpNvX/42oRG7IKregysAhwZMboZ/sRG6aK84cGR0vfti0pWGEx2xt2VoV3sPw2U o+5A== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=dvZ5WUWTj8QrlPAJDzYrQkQZ6y0b1KQREpo25gbb83I=; fh=orAlnOg6eX8z8IERPoSD5STLqjekeryoM9EekUQqVxQ=; b=STEFF8QQh0S4wPzAMyLWK9IDJqfOm8x1u5XFNMRDX8EaGaWwfAmsi5L/NBVKU+K5hJ +lTXNDPQi/miFF8VZBrSbdZ5Dt8s+ke1sBo36eJU3IOrmSiCq9t4ap8zD6fcX3QL/wev Omh0mFT9Jbo7pdFgoMNwDIbMnU8e4zI15B+twqEYuBKVg0KjbwO6KpX49o/W6zhrlSzq 2ubAg49iCbEZEv566+q/UvqG0d/H44evjTLFtMMasmRV00G+ZxS+7te2AnjzKQGFQilt CcQge7htdxTAimAwU5f8p2JozPkr6QTDZ8NBvdBD3BbbuBAnfQFkAG0dYL6lF4+igKrR k3fQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=cRNiyyzd; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57265-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57265-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=2; AJvYcCUtXJ0BytaGVcq2gf50FW/Hd4l2eQ8osU5pQUgqChBilpWmY/EjHy9t0QigDOg51UelmgV1QUq00bwHwOtSdSguBJbfqw== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id dn9-20020a05640222e900b0055deaaf8b06si168599edb.346.2024.02.07.14.39.14 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Feb 2024 14:39:14 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-57265-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=cRNiyyzd; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-57265-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-57265-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id ECE101F25539 for ; Wed, 7 Feb 2024 22:39:13 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 065526A8B9; Wed, 7 Feb 2024 22:37:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="cRNiyyzd" Received: from mail-yw1-f202.google.com (mail-yw1-f202.google.com [209.85.128.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EDA11692E8 for ; Wed, 7 Feb 2024 22:37:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345442; cv=none; b=JXk+lz8xMBC2KQVPDy2oyLTB06g8lwSwXMuM/uHpP3dMOs4IDECB+fI29Gtf15FFSIOefrFRRBjK0EiuMjivYDvlA8tCVC0CwKflfoo+dcW5/NnOGlbQEJ+8rKAk4sFKwHQVtO9OikbioMLTWGUm0GsdAUSXAwW+jwPO9olCwBY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707345442; c=relaxed/simple; bh=QOZ3AXSow+69/jSpTKwTzsRv+NqoTfrDzrJ1ZUXaoRk=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=ZyQ/sB75gYYCk32apOjtgUpIYI35k8PpE1FODRtKQa1c25hVGbCktkMCJZ+9kum6ZMeuR11Dr0koq9W3cWoRIAloAGGDvK6BWwe+wzweF3I5qQSQvLsSQOjs63k1q5wfLddC3hVwzuH8On3Tsyh5CwOTJ9KhqLBjdmHIG+n7ThE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=cRNiyyzd; arc=none smtp.client-ip=209.85.128.202 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 Received: by mail-yw1-f202.google.com with SMTP id 00721157ae682-5ee22efe5eeso21753647b3.3 for ; Wed, 07 Feb 2024 14:37:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707345440; x=1707950240; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=dvZ5WUWTj8QrlPAJDzYrQkQZ6y0b1KQREpo25gbb83I=; b=cRNiyyzdmB+oZrqLdqiwlC3u8oyDF1StzYlMviQhJ8GkD7AN7/N24xJaOu5e6hub27 sl/agywiSWb8moNlaIw9Dr1gnpMFkjRs/KkiGQS54kSvR6ec2lrRuQhwr8aX9AjAIKq/ 2KGgIFb4ZNxpM2fjPZf5SYyyPvrBZ1JKI+YEbuxRRZ2krwZPJcmZqnTMaopR6e0z/g0p ttZbDsGSUivaFGi5ZrqubdvmiC1H5Wkz0SZNGCFMExJnMe2Fbfw/7Qxz/sVVpAtIxdrO /2pfR+1jEGFar1SY3BMbkVj9S5guYQpYjDx8YTV9bUn+hpyvkr2JzhPKXLyYxXEg8eUX GeZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707345440; x=1707950240; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=dvZ5WUWTj8QrlPAJDzYrQkQZ6y0b1KQREpo25gbb83I=; b=pvMQNRkFqiGoOJ3AJezX5RIxyha2IOsphLfZ0CFmuRB43lB+6+HnDMtXJh4sPeomhh 8oMIcAdSxEWbZ1dOch0Kt00BDxJDQXR3WHaTJ5y/lARZPGOgcydjTcdhhdqQbJffbZS0 NzQsmYKI5UMWnuNKd/Bw2Q9U4YnzYHKsXZ6d0lTxlXPdf/73LVnTcAhxid+OAMfMeJ4I Xz9OL2dpSRwtt1nmnNVTJEr0jE5RFBdTZOqPzXNXhvsRoBN5qp9cXxnifSBpeucmEWUw 6RXCSMVmr2uL5KYD8xjTG3cmpzMG7NgyRj6x/KfRClgWEPOtWhoS9S7W7gjElu/X/1mi P0yQ== X-Gm-Message-State: AOJu0YzRb0jPiazkfRJdQ4JKAc/pUNwVL+rVsL5YpvvQvAPpwg/Hm3FM nLbXSEwExQzq1SeTzDcbaHmoDNOGdlfS1ULmdMivCd1EyWFxCmXtTih5JF4O86F+qXSW1gGuJy1 Hcm0Hmw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:b420:757c:5706:d53b]) (user=irogers job=sendgmr) by 2002:a05:6902:1a46:b0:dc6:b813:5813 with SMTP id cy6-20020a0569021a4600b00dc6b8135813mr230558ybb.9.1707345440025; Wed, 07 Feb 2024 14:37:20 -0800 (PST) Date: Wed, 7 Feb 2024 14:36:39 -0800 In-Reply-To: <20240207223639.3139601-1-irogers@google.com> Message-Id: <20240207223639.3139601-7-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240207223639.3139601-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v2 6/6] perf maps: Locking tidy up of nr_maps From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Song Liu , Miguel Ojeda , Liam Howlett , Colin Ian King , K Prateek Nayak , Artem Savkov , Changbin Du , Masami Hiramatsu , Athira Rajeev , Yang Jihong , Tiezhu Yang , James Clark , Leo Yan , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, bpf@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790281572322193174 X-GMAIL-MSGID: 1790281572322193174 After this change maps__nr_maps is only used by tests, existing users are migrated to maps__empty. Compute maps__empty under the read lock. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim --- tools/perf/util/machine.c | 2 +- tools/perf/util/maps.c | 10 ++++++++-- tools/perf/util/maps.h | 4 ++-- 3 files changed, 11 insertions(+), 5 deletions(-) diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index 4911734411b5..3da92f18814a 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -440,7 +440,7 @@ static struct thread *findnew_guest_code(struct machine *machine, return NULL; /* Assume maps are set up if there are any */ - if (maps__nr_maps(thread__maps(thread))) + if (!maps__empty(thread__maps(thread))) return thread; host_thread = machine__find_thread(host_machine, -1, pid); diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 0ab19e1de190..e59118648524 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -541,7 +541,13 @@ void maps__remove(struct maps *maps, struct map *map) bool maps__empty(struct maps *maps) { - return maps__nr_maps(maps) == 0; + bool res; + + down_read(maps__lock(maps)); + res = maps__nr_maps(maps) == 0; + up_read(maps__lock(maps)); + + return res; } bool maps__equal(struct maps *a, struct maps *b) @@ -865,7 +871,7 @@ int maps__copy_from(struct maps *dest, struct maps *parent) parent_maps_by_address = maps__maps_by_address(parent); n = maps__nr_maps(parent); - if (maps__empty(dest)) { + if (maps__nr_maps(dest) == 0) { /* No existing mappings so just copy from parent to avoid reallocs in insert. */ unsigned int nr_maps_allocated = RC_CHK_ACCESS(parent)->nr_maps_allocated; struct map **dest_maps_by_address = diff --git a/tools/perf/util/maps.h b/tools/perf/util/maps.h index 4bcba136ffe5..d9aa62ed968a 100644 --- a/tools/perf/util/maps.h +++ b/tools/perf/util/maps.h @@ -43,8 +43,8 @@ int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data) void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data); struct machine *maps__machine(const struct maps *maps); -unsigned int maps__nr_maps(const struct maps *maps); -refcount_t *maps__refcnt(struct maps *maps); +unsigned int maps__nr_maps(const struct maps *maps); /* Test only. */ +refcount_t *maps__refcnt(struct maps *maps); /* Test only. */ #ifdef HAVE_LIBUNWIND_SUPPORT void *maps__addr_space(const struct maps *maps);