From patchwork Tue Feb 6 03:33:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197159 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299765dyb; Mon, 5 Feb 2024 19:35:54 -0800 (PST) X-Google-Smtp-Source: AGHT+IFki48+voNjcypTJicC6WxwJ09Z2bcp1udknpJHttakQN60S0o2h62/glddDlU6nvr7N7Vq X-Received: by 2002:a50:8acf:0:b0:55f:e744:71fa with SMTP id k15-20020a508acf000000b0055fe74471famr8352214edk.18.1707190554238; Mon, 05 Feb 2024 19:35:54 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190554; cv=pass; d=google.com; s=arc-20160816; b=wSuYGgRnDlHnM7KCMErjZpPI0FWm9ROnQDdbIWBqZaKzxXh8qkAUnufmPfqHBZRvE1 1Dw67+hnQEUV9Rwayk2sQT80H+lBxPRB6ba9xJ0fiLUPYymF9ufzLy8+2344dp6Noruu URrBg8h7aYja54Zd46rfbrwTA5wBRk4NFPDAjKLUbsl7Lu+SP/JLydbtOv0hgGNTn4+O ZlepmJ22SlJiCAnxgcMRnk1vqMwxJKzgcJSGGTCD+l2NTC9ngVKL8Nd3ZX/nPVY9UDsC UrhaWT50VlOcmQhgrMOFEQJwzmOZS6uDXZXAdtpitVQYIaFTbh5lqnCT/5tRbPKNZnfY gL0A== 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=80CScvWwmij1p/2L3CV7a7Pnvilwh0yQVAYET8Lhiwo=; b=Mga/fA9WHonDuPBd8g8FkxY5XvWXLew8k7NV4+2UFAlBrbsHlOpjIQjp1Fii2zzrAq 4MVOC38KZRvJB7sjpfmEFu3dI2OOYrxuHpKyBdtF6z6BABeCwLOJyLMAcybauopt3tJz rpwsBqeo8A7+I5BCX1Ba/OHUgi1gez+k/YA3GEmFxTFt2S5WtkBPx5+oUIQyUsCFiVUe aLRktBDO1+dDR5Bbby/Bt2DsApPEBq81nwH1ZUECQDk/AnI64Hdad4MW9ip7y2tGmcQu liGcMfYlO+N+uZsOUOY4UmUW8jwWebLuoZw7BgK+bUthVQiAxDF7oGyvWnu6j8mdyDeB bXAg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=tGqRuyjE; 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-54259-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54259-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCUjKnyZRSrphxvquSZNgmzICzb7CODu7TN8id6UxHNJuWnpDplFO1xLnTRubAg9mmeXttVndzbpAMMicRCM1ukqM/S3xQ== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id n19-20020a5099d3000000b005600463837bsi614270edb.543.2024.02.05.19.35.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:35:54 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54259-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=tGqRuyjE; 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-54259-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54259-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 17F9B1F23FAE for ; Tue, 6 Feb 2024 03:35:53 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 2C6217C094; Tue, 6 Feb 2024 03:33:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="tGqRuyjE" 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 50971745D8 for ; Tue, 6 Feb 2024 03:33:27 +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=1707190410; cv=none; b=nRbB1+tX0L6z+MBy3pOWWt/tSxOtt/g7tSidBpFz8YYVAUGbnXyrn2m1wrdtQ5sGCkP7bHxssewU+jMGOpu9oaz9bU9ZZD2hgryroV02u1EhM+XHd+wJK1iMZukZLVjr5tJ+Vqg1dVf6AUHef7onGnThv7KdAD9Umxpnk8yNV1E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190410; c=relaxed/simple; bh=Bz3BLNgV+pxdioqFlWJupgjErvAt9IkoS619A9vJWOQ=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=MehphPHxVZ6EDmfjZ4Kh6qJnRY5UzHez6wr5pGPgtxmJ8jTP1hp+zn1/kxMFxETKiFjsTU6Xk2jaKY/B7c+/MwSfee5gNUStO+8k7YvfxVKNYj+pOSNBHfuD71vfIRe4RmyQnabJ+HM5G+CGXo1z0vb9+5jCEHoRdWW6W1zszBo= 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=tGqRuyjE; 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-dc657e9bdc4so7049025276.0 for ; Mon, 05 Feb 2024 19:33:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190406; x=1707795206; 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=tGqRuyjEjkZbUYQlc9veCFKDsR80obJacw+XFVNyLr5we1x/uzFLDdnx9q6VPjLF1N wbifLeJHbicvEf+9a875J7El9Y4edkxZ/Cz7geGS4+tmHRM/Xssb28gt/WHH8grr6Wa+ ISg8I4UWjRMWXdHqALd9vMrSi7SOol/9bIlD55CuhVExbtBeSDHD9XiyIcmr98HMgtut fA9dPhnjvcm1C8ARxjikbIZfvQUYoMzZUHS1997fxMmSs/Ulz3LATcz+/lm1LLQnUweN Wwj9zak2/MywQ6GF9kFGo3OGR7Y0FrLy4RuXKxr9g2jBfXiEnExzvQ/hdlzHH/mXSgja G5ug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190406; x=1707795206; 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=HR1v6YlhacheZFuGnzMb9/DLs14Lg8WtKl8O9Ie+Wt6xWwoqYRw/ptXs1I07TH7mb9 N9SvpVQs6/VPbe+WOlxaKMVJq4cXh/jyaHpNXuGffUTWZ6gYj6sqpkR4/byBAJURTkLX sZRJejcJWVRa/NkR55yQiOmmsqH/19oQH6k1ux9FexJjyYig59aALMh1uBZvYGO1GokW ROV9HkIWlULToa6C0rl7FWW5TX+SQRGbGd269BDozXiDpyFO5FWgkLzudC8zuk9jnbIW sZgY1XZWoqOgjUJmPq4d8W46GqHqnkYO5z4+1rCdw3HHu6w1Xe1c7gw3qxsDzo6757Lt PkIA== X-Gm-Message-State: AOJu0YxI/z78Xl5SySs19up2kmtAoZ4W7op/oJP9gqLibjjf57yYQVbb GVyDS6k3vrr/d5mUkitrqMgUQHA7wdrWFyzmkD2DWaRW+7M4/CXJ3fCqvhz3dYSm9iMxPNg6nkT U5ufqtw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a05:6902:218b:b0:dc2:2ace:860 with SMTP id dl11-20020a056902218b00b00dc22ace0860mr16698ybb.2.1707190406404; Mon, 05 Feb 2024 19:33:26 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:15 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790119042647390991 X-GMAIL-MSGID: 1790119042647390991 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 Tue Feb 6 03:33:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197156 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299392dyb; Mon, 5 Feb 2024 19:34:33 -0800 (PST) X-Google-Smtp-Source: AGHT+IGqoPNnbtNaBUgZ83GEL5AEweStv1o5guKd9em4e64ajCuiSWSDN7NaJ235xBEr0OElxTEb X-Received: by 2002:ad4:44ac:0:b0:68c:7946:2cb8 with SMTP id n12-20020ad444ac000000b0068c79462cb8mr12862723qvt.7.1707190473750; Mon, 05 Feb 2024 19:34:33 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190473; cv=pass; d=google.com; s=arc-20160816; b=PxlTSXlA4Otue8eGSuxwboAT3VogdJ4hvWIwOTed2P2YJ5pwgb9tyltd3PJJx8ay+B 7CKQqKSFvdnr+ZL39Pa0iW/wsJR8g7NriQWf9C1eTf/0k515lHO2QNs70P/c3dZEjimv ZEDzS1eDetaFJR/4wtHBwsnv/evAg0KlNXdhfkqawEXpmxei5njYD2BKIcHbux7ccktG PaVAwhul9JEAVD4UjLnEU2gGR1lFMxkn4xGrXvPaD7M/Vgcg7OmeS7lSeTc0+JNKtWVO IvUt/JrIvMZUqj+KIAFV+5sjv/Fzn2Zl5NewQvyVC+ws5MzD7m00irG3eI4c5qwunC6Y Wfvw== 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=kq044nE0TvbClrkYZ4GheK5Ez4Yv8wMknpumYAhr8rY=; b=DEmWs6vPW1OzjF5bCE5znG3G3dFyOqfZkMJvD0LYa4Cik/IyAl9bShuYjR3jjgGFp0 HetnbzHvfbAKBy1R8NYzEGifPjzN2dTGBVsPQPz0B5XFe1KxKpc4bHYLndQWuiueTjpa AIFQ2M+S+TWmhE12Fj8+2OmbCHCc5kdvg1RAm2ZvAOhT0Qb/mfluuhXXI7oa5CNciskN pQpVzxRj9Z7O+BGK8uLh5/IKIyjNE6uGkyI4Wv83ZwwdbL7r4UpsoqKAUwVK1ozp8uKU wbHGf8hFSR9kgIi94t9HMsVWgclpyeyHoQu8WAuy/6EYtyhNlQ/0GvbFLzO9JcQG7GMS Rs5g==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=xeWG6rvk; 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-54260-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54260-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCWE4BOsDi3+6rbb5mkJnSkOTrQlYJ5FPBdTqkwT55C5khHFEWI2ppYSbQnfpgJr1cCxvzBJoKYSqlu2uaC+o0om6kJTLQ== Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id r13-20020ad4404d000000b0068cacf8a434si1511642qvp.289.2024.02.05.19.34.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:34:33 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54260-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=xeWG6rvk; 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-54260-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54260-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 7986D1C22598 for ; Tue, 6 Feb 2024 03:34:33 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 9B99B77634; Tue, 6 Feb 2024 03:33:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="xeWG6rvk" 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 D4AD5745F2 for ; Tue, 6 Feb 2024 03:33:29 +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=1707190411; cv=none; b=q/ilmID7+rXCaghaOsMo25OqomMXPBYcm/xskB6Z+/oXZJziLYm5WWAlglMeiducWcmO3lQM5F8GGSWfTSHbbkCQyhBHBA9RTRnYUkyUympsqDUMhkQGQ2xi1HfmxwkiXBMi/+22Iua8MI+vAq2zKlXUJmQBL6NC7/hGb/4kVYE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190411; c=relaxed/simple; bh=RZxmraRvUZVDCEnHDiKvvvCrdlGpPV4CU1ch1xpR8Ps=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=GLsCW5hPAb+ksx646s5oQ6nYUehPxeN2bc8mRBNYNy7laPgcn0iCCdzsu9PAFQF2b0Gl4XG9pyLS2s653wk0ay8MoqBD840EI+meNMXrRDcEX6jgQZr2bGwbwenQ/b2gzgSX0DVkJSigi4TSnEvyXitQ63wIcAuED05z+6Lpl4A= 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=xeWG6rvk; 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-dc693399655so8251559276.1 for ; Mon, 05 Feb 2024 19:33:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190409; x=1707795209; 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=xeWG6rvk2HRd3qb9bSgbxKyu2bw/5eKuXT9I9cJqDShF+60HBOvFTpcp5TwUWi3pAe JGU7WleqmzXFi756z5519IHCPCq13C3hh88GnaOjJrROWLKRW3CDQ0vXHX8/tuZ2aOq8 cXJb6v4lPaI4LAKpwZ2TyGRtAabs5fNMrKpwtProaleqQ4byJxNQwe8FQTkoyogP+ND/ VYmxiavlj8z5I1Ot/Pny5l3CJH8J0H28RPaNbwiMBAfUH8xT1ZYvTz3C2pYIYhiGXYq5 ljyQ+QUo94kuFE/oBqzVW9H6OI2H+lGPaPo3a6XMABS9PqA4/OlOaUPjXt3Ey5wO6D14 HTiw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190409; x=1707795209; 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=Kys2JOxOk6vrYEhrNaN2Cfapy4ji45M13ys5wpA63PRxeEEhQLiBCvrWECELoikjh/ b2CiQ2GXdyTH8Q1frQKcswnqQL/Wx7/BaF9r9kQZ2EXGnAdR2nxe2y1IYlPfWIW4RxXk Rm2LwAhgYwFAb2bcQ3KykQrz/Vw4I5X/GX/5AFHN8Vm8NnjZWiEEfp4O0DhrRJpb8TFH JatagAxc9/AVgYwiHWz/+F+82I0KGrIl/gHAF74GHQlWRGSYs9odx2gYCX3YkVxTrBJB unf9vdcoNDcYiXO3CtFAV6amJSHIU1u4iF8WR4lu31eq37PA8p7+rafhe2TjSPXV4EdK OzZw== X-Gm-Message-State: AOJu0YzqXL1fD3oiHCo70/1zj9INKVKAclKod977IKr/erOqyYt3tDU3 IiuV0UUM9IKl8NpTtv8FQK6QXNwSO9Ycdf0Sb1ZVPl1iFJCoKQJqZl0NSqcZwT/XoUkijEG5YrT urmC6uw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a05:6902:13ce:b0:dc6:e90a:7f2a with SMTP id y14-20020a05690213ce00b00dc6e90a7f2amr126377ybu.5.1707190408762; Mon, 05 Feb 2024 19:33:28 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:16 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790118958540346855 X-GMAIL-MSGID: 1790118958540346855 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 Tue Feb 6 03:33:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197157 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299471dyb; Mon, 5 Feb 2024 19:34:49 -0800 (PST) X-Google-Smtp-Source: AGHT+IHNhMZUV01vCawD0Ioh0u7hlFLjF2gLUfsLV/9X3tPuluGQplH1uKSeeOKIBHsS0i8ZZNBF X-Received: by 2002:a05:620a:178d:b0:785:9016:d1c7 with SMTP id ay13-20020a05620a178d00b007859016d1c7mr591871qkb.72.1707190489324; Mon, 05 Feb 2024 19:34:49 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190489; cv=pass; d=google.com; s=arc-20160816; b=dXiLBR20EoVIXwIRo8GvfdMgaoq6kT2p3Tr45mnktcyRtQj5T0+d4G1WQJKsbJs5nQ LjGjax7inRore7nI2UKURmbdtS3loB+3mpXOyS4IEbBosTy3WOOEvI4c9v6VhWiGvKrO 1iH8I8ZV6crjOL6fSavjtYjbue8INJGvwz738N0zfR88Fw321f628WNf9t10oOX9Plg7 rQ2RA0BXxmFCCT5h5XGr75ZQlAPXf7uIjXgH0oMJznHzZJH/8rRzX+iqP6dqySDgbsUX GJ/6PeRYz3Zt1G39Bumr55Kom8EsGhuiS6RL37T7+9NBkHOzQQRupMewoSi+REPEbpQ0 mS8Q== 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=GEmDxFgkZiVUulrZBu2hxntSy5Mh4UJNPfqis0sHzwk=; b=ZcncYkF8BlRKdy79pmZehO+/zv/v0uaKubv3VGmgNcP4Ro7x+/d8iGqzSS+rXyMXov fASyOqrjzAUrn+IVtON7jMrNzphPdWPf8ilYeO/tn5GTWII3Hg5xWYjbyZsz/sPL3+rO ONsUPpg3n547w/dwWcg/kGPzK0zKjtQoG9nOtaun3bpXUAuEZAH0XJ+kGZ1Ye22fXGhz tIvATcCSZrPQFHdXJceuuOfqzv9WdmDXxKFYIQkacbgvpu6JSEksFV5nzS55ePnoxkQM A86DBQZk381LQ55jUp6sdVdreBY08V16+auhu6tN5v7+ZVqHZ2CKaHXWRl6zrau9SEbc mx5g==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=jg0zMoc3; 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-54261-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54261-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCVpe+Tr/jxOpbF6E6908D74nFyEaGkQ0nGREDxW7mANkmlW7jDipZqjKFDm7DkaoCJ5HtMOjYMZHhdSFJT+BjBpTkh2eg== Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id m5-20020a05620a24c500b00783e08c89efsi1599750qkn.710.2024.02.05.19.34.49 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:34:49 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54261-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=jg0zMoc3; 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-54261-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54261-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 141E21C22958 for ; Tue, 6 Feb 2024 03:34:49 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 3DB4977F02; Tue, 6 Feb 2024 03:33:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="jg0zMoc3" 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 2C9A8745F0 for ; Tue, 6 Feb 2024 03:33:31 +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=1707190414; cv=none; b=MMl8KK4zWPGzjw3ghn3Mq8r05YbyWkTCrxIm+R8/7ZtBLxqy/3qm5KDy/66Z+mI7P9brrClNBYq/nXTHIWrt/lPiOwdXLsUeIEupz1VicWo/w4Wtksgou4PnvNRYezIp402HQmlE83KIFESLyPP6tQrvAmd8HueJkso6SQVLAHs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190414; c=relaxed/simple; bh=TNL0GOyieHu9AqHO4Zi22Cz7C0gAfBXx8CvzAmJoOYo=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=vBdUzohJIzrNu1Z9YBJmlX+FIckqX/qsu1fwXFwDv1/IYbElE1Bvov9HMR0pH959SMwLJTjiVTGWRYh5TFuleC/e295hP5dVm7RA27soIybqpRrsawg+ucp0ysuIXt+pXqXGhsk1s1quxw/NFbcK63JNfsohk8a2NVRR/eQcTqs= 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=jg0zMoc3; 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-dc6bea4c8b9so7391207276.3 for ; Mon, 05 Feb 2024 19:33:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190411; x=1707795211; 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=jg0zMoc3iXuKLN1LrNcpLm1P3O4Mo7KCJrqBCLipSxTgWfi2C6iH1Dv1SriHXh/mxq CgWmUa8nbBj10xFdM7ZKczjs0zzLPOPbnSo2iVsuctclJGUfFWGBaPvExe2ArcqKp6WK 8Msud07NetMRXVKkRix75vdXVqHyP1/MOb3qQesxSh9OjEB4mxBZ2BTaMHmeZvEekMQW TnRpHmH7rYCRU2bwulJoHc1uaTyOi6K2lzkmGt8bCnfllf7PjTPIFnQtxerf+O4gs43O wHoWVDPc5YiahEPKn2Vc9ysQUIB0wH+6XNckLZMUq/krKWkNhI3WDKl26Q/xipBXuHrn DWkg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190411; x=1707795211; 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=KBvsvoXgLmeaN+GIQN4b6P3zR53qEw+pvdpUJ300QtbBvx6Q7p8E3L3ujdse/z7eUu WTGp/YaIeRlaw/LI4R2Q4j2hApSBe1PVR1lWvPHdD6ImwKF1BFNynE5GlVyKLqkQa/QH XCRK+k7mgZKWsR0vxSZFmllXq/+E/Kc68A9pGtfODe5BOmzz3GUBAah27I5rFJl9lu+/ mYYPXUmnYGfoesW/ZT9LqXKIcQ/EzK30hDvJEUDvWqCJO/p2BAyLlI/MLsjeWr8LZQ3j 4e0D9SUkOIGSzQBHBIvSG0CpvVJyQP5KEODCNKFqYVpe7276owl5MUKLjQttSFCkPJpN hBog== X-Gm-Message-State: AOJu0Yw8QZnMRHvAy59Kw3Mlh3mI4SOuBMyCASWLoyVELUpzjOlYaiuj jskJC9U+3Fq5lj/BHQ6xBmFKIEvipqi2ZI1iqlQe8bCIGWxDJwm2szq2BZ7utgVaeZTedoTI6SZ KmsOkhg== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a05:6902:1b89:b0:dc6:d9eb:6422 with SMTP id ei9-20020a0569021b8900b00dc6d9eb6422mr16445ybb.10.1707190411197; Mon, 05 Feb 2024 19:33:31 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:17 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790118974311828182 X-GMAIL-MSGID: 1790118974311828182 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 Tue Feb 6 03:33:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197161 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299907dyb; Mon, 5 Feb 2024 19:36:21 -0800 (PST) X-Google-Smtp-Source: AGHT+IESjGDxqWT5gsmctyYStuVZsAbh0OCtZSEFNRTUo+nwyjpiyhIdPN8DblupLiAcitBwEtge X-Received: by 2002:a05:6830:921:b0:6e0:be61:850d with SMTP id v33-20020a056830092100b006e0be61850dmr1590696ott.1.1707190581212; Mon, 05 Feb 2024 19:36:21 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190581; cv=pass; d=google.com; s=arc-20160816; b=FMmrGXXY+wRv/lQzA332KAFl4wMNbUL7ACm3kCBXelMduisDmQiMAfCNWmXlrB/Ktl cBHdhYIlSg/LrcblYJ8IzaNv3LW5C+UrtJHwZSQuj4ka7+BlvAi4ltfuIJSO9N5xJKli q6KyBnSS3NGT4Sr1+H5EbZ3Nw5GhmG6Xzaf+uJmtolDBIC+Apw0fxZ932czFjlGAMEdR 3W7hk8THiUZ7SOCYdc6LqZMX8qigcfq0Dor7rMUswRglKgFwaIBN9wWMvGUlm4Kb7P/d 3lnp1/iJqmBzID4GlJrLyAW2BpZyShp7haldKXW0LqOjg06so1kg0NbuZHjQ8ZARWC8g DRtg== 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=RR0heUoXZixhzeTNHAo+pZQS+3DNOBG04h9fEonTkaE=; b=up8BiW9PTlBmk5wdPqOrCGgIMjmqjPvGEpxtxJyeMcaUJs+O4+4t4XoslY9qxUHeZD /UhEbj/zqX5e1WwOlswfBvzhQ2pJTgrVzhrPlRL+PP5UnPK4uza1Z0Xw+efWvWFtrIYZ HLz6Qaol0HqjIN7HFywwwQ4JArFE1OEZa7FwK5TJwrXJy+4QtDr3DJeqVqoeAN2uGEY5 PGseb8Oj5in63Qj24sI9de2XMsugGH8ofIlh6TttwiWayNGt3or1zoLUJUxcBlL6krr/ tvkF7YV3VT3AR0pLBwqc14eppdtN4TjBqy0oaTRWHxc39U+TLSYYq6VBCSfWTZfEXa/m gRCQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=DZ7AdCqI; 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-54262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54262-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCWxW1Iol0jDzQ94Uv+Pwzs5CK2wLTdMoZReYum36Yx4xvSbGEMaAZZLVvWSVr0gKjDVmHm9glSDqC8Xv3XjcKNRk1Au+w== Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [147.75.48.161]) by mx.google.com with ESMTPS id r13-20020a63e50d000000b005dc0af6cdbdsi918440pgh.298.2024.02.05.19.36.20 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:36:21 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=DZ7AdCqI; 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-54262-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54262-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 F0F2CB240DB for ; Tue, 6 Feb 2024 03:35:13 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id CBD367995B; Tue, 6 Feb 2024 03:33:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="DZ7AdCqI" 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 7F7D2762F3 for ; Tue, 6 Feb 2024 03:33:34 +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=1707190417; cv=none; b=KGGClSMl2nW140ckJcJHoMu5gJxewitLOZNbry8czV8BwKtth9Lf/QmVSReBaVDoD/0yXE/2L0oHGhxgLlGb7NFQUAHmMr5Bdh4j9Y4gyv5v2ejP+ZTBaJGI66XOXHDRGpira3H6JAwUURGMhfVjGvv+GBSOzescNKTLk51dHkg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190417; c=relaxed/simple; bh=5X1qsUi3skYX0+XJLWX/k8pq64P7f+cfj6l98r2VoJ8=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=BlBh4MWTKM0eLOQHbnNDEJK20tdY90NPDYxUjoSF1DB7KbZ0bg3tjfjB0KyvQ2KeTes7KliNqXFjMUSJ6JcGmdLjcHLbzcuCvnr1Umm7Daq+Fcq6EyGedX9kVonuF5sa4XKSHbug/HI6ztdolmkQgERWzly4TCey/LpwCEduq0k= 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=DZ7AdCqI; 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-dc6b26845cdso8644669276.3 for ; Mon, 05 Feb 2024 19:33:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190413; x=1707795213; 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=DZ7AdCqIW4SN2p0fFMDtzJZsQtPSR2SW8mD/U+JILSftqL8rvTaRyvTFmtXRpk77+0 usH3CaZILv3zi/4R5iZVfOOhJxmPYOKS/vbTefJmT1DdLWWLfXGUHHoB1CuUUjgqM61D SqywKLyd2ja6OT/OzJHMBpUJBWGAmniBKa+5Na0NvS9OwH2jnDHH2pnR5GasxDGYA3EX uJZ/HkhrRS5HhPQ4xQbY3xzjSYbds2vSuM2b5+3S06KwcCTjh2iK0uKKquTq5yme3OA2 Iw9Mm5nnfyj2nQ+4PXEmMhcnAZuDuABnUeURZj+EaZYfO7sf33krKCNFTxPrEg+RrVV6 Wj0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190413; x=1707795213; 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=Aurhn2Zrc4pNdzDqo97I1vpk7UnyFRwzp823ECSvQpBud7Pp1SglEaz3NOTbn2Pzgv B8H2cWR9UZVI/agXud2noPQcDPxLECQ5f0WNfXuU57xjj96Rgu7Nb7h6l2Y8diZBLy9p bWwknQsZfYu/rGV5y4+D0DoKCzS1Bk3zksGEHf2FbCBHlk5M3LGTwAT/wFUETXI7atOC kvTnATKVBaFO35oxuL6q8J593rKGQVKpcquLTSUzHAn+Am4Yrz4PunKRxQl7JKob3Vur hAxu2TafAVqDLJTubE1Y/TFCmjBzXm9CpiGz24RDX7X2UIJx7maIIASFlnqLOwxD5tLL eCdA== X-Gm-Message-State: AOJu0YyzsnU/d14e+yjO5RALLjrZkHiHOEC3kk+ZJOcu6hBmzvNiK7d4 pkL7UY01FUSv1QqJYsP+S0KsZBw2w85hpV27RA9dfrjqD2qZHznN6/FIl9dqta43xk1/fqf26HJ fbpUMYw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a05:6902:2785:b0:dc6:dfc6:4207 with SMTP id eb5-20020a056902278500b00dc6dfc64207mr113515ybb.10.1707190413407; Mon, 05 Feb 2024 19:33:33 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:18 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790119070882982021 X-GMAIL-MSGID: 1790119070882982021 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 Tue Feb 6 03:33:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197160 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299785dyb; Mon, 5 Feb 2024 19:35:57 -0800 (PST) X-Google-Smtp-Source: AGHT+IFbdqtDuJKUynoBfohR+JUtzIFCeaab3+tQhY5J18bsapv/15U2isggA/aYZ1YH+D9z83z6 X-Received: by 2002:ac8:5805:0:b0:42c:2e62:dce1 with SMTP id g5-20020ac85805000000b0042c2e62dce1mr1522654qtg.57.1707190557759; Mon, 05 Feb 2024 19:35:57 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190557; cv=pass; d=google.com; s=arc-20160816; b=Q9HL0fLjqzByorFJgHJrNe2hwx3X5DyakAShWF8HQ2BYYgB149WkA+zeFVUTG5qZ1R qxjh5EU1sDOwiUF0aUd9X7YUg9bdQsrEgpIdz74U9B8JZX7bw6YBsXjgBIUR2MGnbd9z u3vjT/un9x344WZNc51vPnB5arrPYwPoKDumIVbcGb3F41kbk+JGPqTAIZwwwljiwAvy f5MYANbDUSDTqzs9YQF6w3Q+srqGXmhIzaYpsI894QUrJmbaCwIAU/il1XeUso6pzOF8 /H8bQuYgojoD7wNCjakh4zR9HTDCNzQGw8nJYo9S8mfC/y/bkEra/xzdgk5KVwDQFMzx e/Fg== 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=PjtzHr39AeUV+4mQULy9NeNoMUD2sF0udcaZcT+VS34=; fh=/HnlbY4u6Wfdzp4lFP94GBd8mgRzseylHtcnzGudR8s=; b=Xo/b+ZCfXTmmRwyU/2buzQI/mOpuoc7lJkVxdN90yy/BcNFabjXCrcO/Ua+uXVBBu+ QhK3fm011MEjPM93TAX67sN22x+yRaULzSfwzXHSUk6iZcRv6GOqd1+Sxb6D7j7F2+wu NztaPpJWcBwDH2DRWZn0OQbXNMWcFHWZXAcd/67oE+H+RPevi1KWCecDp/N6Ar3mKGf4 IDCVLJAES5cqCJgxd7yO2UlfrhKAnp94Ix1LcXxmgJOPafm0QrxALXuH4x5w6lsHMtZv oLM/Rf+sE2/LoWvJE/DQS8swRAPKRNj3w4QKMJBoxPxrHAlrtAIc2YeSCWXpr1FnGlRK dx5w==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="Zk/B/gdB"; 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-54263-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54263-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCWgD3W3E0OXmNhhAtvaj8BlbcSAGjeFfwYpRMJabstLFr1RB5mm2vTymCGLUOF/Aal++agscZAOSRU1uGGVcvaGgt43gg== Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [147.75.199.223]) by mx.google.com with ESMTPS id ay3-20020a05622a228300b0042c31ce7ad1si1363916qtb.518.2024.02.05.19.35.57 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:35:57 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54263-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="Zk/B/gdB"; 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-54263-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54263-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 6BF1A1C22079 for ; Tue, 6 Feb 2024 03:35:57 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 27AB17C6C0; Tue, 6 Feb 2024 03:33:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="Zk/B/gdB" 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 773057765C for ; Tue, 6 Feb 2024 03:33:37 +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=1707190419; cv=none; b=i3DsyMyQ0JhfsHuu+U/kW1vb6m4BmOiLO0pdAL4Azb6XI0tDyueCbEe0MDlNRLZLaw2+hd+MCDIFWrHXABfvM5zGlg7KBwMDX82oZDUs9OsNR+rPOTOABz30W8NFsGgF+hEenHBSSkauJ1ybC7Ek2xPz6tz7PCecSOt+lO5GJJ0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190419; c=relaxed/simple; bh=k4/3nGbKkYc2v2yj1AdXPXkTss9S3lbTKRWzh3R2i4I=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=HIKBalaZK+1Qpp3H3gi6g7403suWing2pXNqKN63ITdLIzDfHrHOhYHZLGPY2KKgu1sOALOBuP8Ejhrsu0ROau3Hta9vLRPnjEUnmA+akRA4TdJgB2GarCsOp6ewg00IBqvzvLiUP+snFdlDAkXr8Nvl1a5o3qA5HYUOf+vQIsM= 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=Zk/B/gdB; 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-5ecfd153ccfso89982717b3.2 for ; Mon, 05 Feb 2024 19:33:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190416; x=1707795216; 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=PjtzHr39AeUV+4mQULy9NeNoMUD2sF0udcaZcT+VS34=; b=Zk/B/gdBvD+6ScVw0F8w/xXSyYTfIJL5FE5oAok6IdLHboIG5SF71brcc5LkjdSWzy WG73RU30Hulknsg8Nn8j9z34a1cXMdbpDerlsBZfu8Bcv+Z0CY9AU00F1J8YBeHj22Oz VQ7i6iklrzJ3Y5wC1X4E67icOPC5W+wWwGTxsdYALBHOFg+I7lk/bgDCFllLbJjkEwLG XICqBKTe6Kexx4Gx/RmB2nYxsv6rF3/FB/CFWBd/JKV3IejmD6x9ZlPLD17dHNSJ3uyr DtXEiY1+eLzX4TOZ9X9epxoXlB8Ert8vzalt5lG4rNvB4Wj+/Ra7mGOZz5pfZb2WrMtu iV+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190416; x=1707795216; 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=PjtzHr39AeUV+4mQULy9NeNoMUD2sF0udcaZcT+VS34=; b=sF7/k1QVuTdUo/zcaYnvxUQasOMLT4bqKU8qmLYuDtuXuW9cvRk/W+IwlpKQnfSB9y Ak7/se9sweZcu2/B8/Hhm3uhLBtszDPtbGvybxFNgv9kJXCOprWR8mjJIQbMYOtEuSnn ZW2vno6EpUmvYC/gA2SaWgJ7idtCBqgPm2+pvmonDH28sjwmW7kVfiaaDX6kj1QrYbPU Kt+8s8WAUjp4573r74rb+sTfApB6nmZcKxkKPptczVPW7ou1SnkQY7sR2MLlaeGdBJXH BipPu+ZzdcivkG0VKoLFQ4Ad05vTL8dS1Ic7wuReKDCOkZjoidMLpDOrHdAoh7nJONdY YhuA== X-Gm-Message-State: AOJu0YwSp/0yTyIBcy2rXXUpgaKrWwU8JwP3YVEftiSUAPQ3Q0AU6jlb eX8EmWy5Jy1tBJqFmPmhUMTbLr4bgVfMJRxKybympGU6Hwhf3oWxWqS5YrRz2tuqKUGjnny19li pUwY9hw== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a81:98d8:0:b0:5e5:e1e2:31f with SMTP id p207-20020a8198d8000000b005e5e1e2031fmr94538ywg.6.1707190416488; Mon, 05 Feb 2024 19:33:36 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:19 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790119046761939930 X-GMAIL-MSGID: 1790119046761939930 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-libunwind-local.c | 2 +- tools/perf/util/unwind-libunwind.c | 7 +- 8 files changed, 123 insertions(+), 101 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-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 Tue Feb 6 03:33:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 197158 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1299767dyb; Mon, 5 Feb 2024 19:35:54 -0800 (PST) X-Google-Smtp-Source: AGHT+IFqkWMedIe6DStQgrYxWdG4AFdnKw0n+nI+jYmsptcrWabWRvIXmSNazM0coJZtEGYMqhHE X-Received: by 2002:a50:955a:0:b0:55f:ccb4:ec84 with SMTP id v26-20020a50955a000000b0055fccb4ec84mr8420389eda.1.1707190554539; Mon, 05 Feb 2024 19:35:54 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707190554; cv=pass; d=google.com; s=arc-20160816; b=j7GPS3CyOdVRaEGVGXOVwMgobXvHqo58V/K/slLT37H+E438pfAEky8NCmeyU3ehtW cnv2eaJJYvbSe7kLpX2GbwEWY1ixr/JVaGxMqJ+cGw+IVRtMI0h9sTbud3sKVogAsSeK N7z1R8FoxlBs/oWNGrcRbRqgTFCKf06fafQMqyWc5Gj9VKyyDmOmnwvwvVRZ9cgzVXIY 3rdRsMP2PiSYlktTkbW7wyPSrtUeFKu4fYZkutd6HdmNgtBX17hrdww4Q4hBGfTiR6+U GRvkh9bPt3hHtWxR+dgO4/yo8aCRBtuGGhAEVkSXAxBOnXBvSWzGJTZYhUsn9rcOg4Gd Aicw== 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=YvrBtULQX4ISVmqY8ZE+9LzFj2ATZO5GZsBrD+xYvls=; b=rHAKuvlyPVTSgPxLCv7o5Fv22XFFPOa/RyGwemRzrnv/iHUtpaYT9IMCirs7dSTaiW EA+MJncTuxGmqczgGOtrlwkfSKAvzteD8Hw7C9KzwQCZNaYMlvzw7y6sAylpDHLITg7u jAt0pfFA4a99I0RfcWIANqU9EZboQhjJZpNxyQYVPaz4XLcyocHjWF+bNH/Rvf3FL2kc n6GDAWA+IjZEgr7K1h2qtyyNfAlg8RuRbUlydNf47Dgc4bHyl8UuuiglXTXLcYQtuwNV uJHqaUmIxPgfOqiIoHXBaWraX64LdYcZ02TPOlKcL4Sjj8Jh6MaKkmPUR7mX1FfKk4TD CMGQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="ixVwS9m/"; 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-54264-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54264-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com X-Forwarded-Encrypted: i=1; AJvYcCV7RB3HV6AEA4k5YdHc2uzbVG7dMq3NC/2tczuNb3g8ZtWFqPOQQvVD2Yv4d0R9Z+vnjQSrFplKWvWSmnOxgUBC4vW09A== Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id n19-20020a5099d3000000b005600463837bsi614270edb.543.2024.02.05.19.35.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Feb 2024 19:35:54 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-54264-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="ixVwS9m/"; 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-54264-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-54264-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 B6E041F23F56 for ; Tue, 6 Feb 2024 03:35:53 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id B75897C09D; Tue, 6 Feb 2024 03:33:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="ixVwS9m/" 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 CCF9177F2B for ; Tue, 6 Feb 2024 03:33:39 +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=1707190421; cv=none; b=jhU5HpxZB33vjXFrxFqLzQgO2SV/f14ziGFeWZ9Nb9BSvUXhQSALEWgVr8rTQiIVoRJTrNoj/hnJ2a2zCfYpXGrGvkxfaIQjFs9NCL2UOHBqGeKdRxRL/urDm8GFFouvySbioE4bXQPnnEQT+j//Oo/8yKVJCGpVPI2AdeZ5u0U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707190421; c=relaxed/simple; bh=QOZ3AXSow+69/jSpTKwTzsRv+NqoTfrDzrJ1ZUXaoRk=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=BFl6aMPf3HzFtjHJMSE7ERtDXU5d1y9laws0+mrUGUvAAoQyXk9NO8EJkDOYTen7SezCpxv09VDYVxXKV4glTIBUYgkQRvPaoWQ0cO417bY/3EsBuoW5tJSKs6rVaatPXEtDcheg4N8YWW90oDSUq5R/vxc+fgmFnSJi8LWvt94= 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=ixVwS9m/; 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-60402c8d651so82838307b3.3 for ; Mon, 05 Feb 2024 19:33:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1707190419; x=1707795219; 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=ixVwS9m/0znAw4QZkK+GbKmrknuOyRgxRPKAwxgz4Pzfd5JnseVblOETA7o0GsOPWJ n8Z+kXzC7suudMIuWBKVva54xQ2z2Q1hvaKh+pv1Q6/V5lZizFVEiHVOdB3lT4G3SuXR NaJSvfD+2NcfveM1/4UUC44quCuVgFpNlGirB1EknN5317334GM1SJ0At0TJmYSh3+SD oNcRHywDuoTW3Fz3vhLwkSTBcgytvJ9Mpfd89YlEsYYvGrRmYx9oMoHi5JhouDHYRJiy hoTGDJ8h5LfmHk+4EeyoUnkEV5rF4MQacUR3g80gObvzRJGmgHTf1+RrX8tbeLp1JBNK kiqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707190419; x=1707795219; 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=C07rfP9YYIuIjXiABIzKDgaeTxrMoFFS+/ccFJJL6Gl0YDFTciVcqqh37TXSbLivC7 Aa7hM0wBBrd+MH1S0wDb3Saqngzu7eUYRQUECJ91dw+Qeo/f6FwqzMNESnCzcGyU2oDH vDVSSQwWmeBqlKkWd14a4nnmDgBv66mx/sk6i6hv8o05aT5qWUoSCl3KxW6B8qyBHGo6 Yz/vtFXUovRLRrCzthMpLHzJnYVQfw30/VUVDaIuG6drZlB5vIG016EvtAXa7QaiL/QA bW9ixkDwmeSCSVsOEAzHPkyjm5fwGecNHAOpzrrkffk89slbzs+zw0uN8qk+prXaxwfW d2bg== X-Gm-Message-State: AOJu0YyeCwgOukd3PUxAxDahOMm2qkMMIccqUywUp1E5L2vc8ZNBszcD ms97YLICN1PbqU8eI4cE3XubA4g8xga4cqXo02/HH+qzH8EeDC26t+hr9I3SmFKc+Ub8FDG6KxT FIM+TQQ== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:326b:71bb:e465:6f39]) (user=irogers job=sendgmr) by 2002:a81:9ac1:0:b0:5f9:4fa1:1a0b with SMTP id r184-20020a819ac1000000b005f94fa11a0bmr62908ywg.0.1707190418775; Mon, 05 Feb 2024 19:33:38 -0800 (PST) Date: Mon, 5 Feb 2024 19:33:20 -0800 In-Reply-To: <20240206033320.2657716-1-irogers@google.com> Message-Id: <20240206033320.2657716-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: <20240206033320.2657716-1-irogers@google.com> X-Mailer: git-send-email 2.43.0.594.gd9cf4e227d-goog Subject: [PATCH v1 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 , liuwenyu , 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: 1790119042959490280 X-GMAIL-MSGID: 1790119042959490280 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);