Received: by 2002:ab2:1689:0:b0:1f7:5705:b850 with SMTP id d9csp1558882lqa; Mon, 29 Apr 2024 11:52:13 -0700 (PDT) X-Forwarded-Encrypted: i=3; AJvYcCWvWqSMlG6Ah7IgenCe2r7NAzSo5iOyNqv3RxOsfAJSb8j9+htDODc7lbNFpEjxEUaYwX5jOZYsIIc7BXOLx5dDNGkVbXb+ou2Hg8iIpg== X-Google-Smtp-Source: AGHT+IFfaaBp3sKBDeH3BeDzzgTGKwqv1QpOQpn1U7O4ptud5bdh+zp4wF+NsXcr/PMR0WNWBWaU X-Received: by 2002:a17:90b:b93:b0:2af:1d61:e65e with SMTP id bd19-20020a17090b0b9300b002af1d61e65emr10452625pjb.17.1714416733416; Mon, 29 Apr 2024 11:52:13 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1714416733; cv=pass; d=google.com; s=arc-20160816; b=RpVFikyA9K3gSwRPpKJkPlCPHw18LO3TBiZIBpp47su72XQFXimh4juud4w4ieP8En 6cDJKHBy4XfUnGTX5DGjFpNkswMTO3MxD3jQSnMctCpluCQ4shu9+P9xSTQ4sjrqUq2r Lh7GFJKt1Pyhsu4WiR3rZ146LfVwyoZYYUSg8Ng9DWw3ctdO8+0Z1E/c0z/eWWW1Dj0R V5ILWtfGQggbX4waQ+lop0IsczecTlWz2RnD07uK+1HxPiaWvJvcvU3URdWcvUO08yDX DWl49huzw9daiEJFitSQCtVtoKjAzWQMgNNpzrkzWQB6oA+D5Xy8l4l+jyto+oGsIULl eevA== 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=Xf9DU2dnw7wispX/TBVDNkoG04QwKWtFDLd1toiCdnE=; fh=5jsacG0cQ7EeAJZixohl72HH2NGvgHdAUQF/CjrrL00=; b=VTZFQptuGX2vvAixZvLeTYu6Tqs+QHPwzYceASreOGTpAPpKi2gZ6JvMOUPtAiBhEe c8MeHljMsmm46LsAVe4YhSJLqS72FQm+ZuGaXr/oHrYDf0z3uJSvtQCQpZ/y7k5iVdkL 0A2EharHtddm1BOGbQ2u+c9upPpNu5iX59DY8I+O8PcGtjV2iBoBpKxaVoVFOzSdmlCm BMiZ7BqjU4HJewMRFl3ZJjf5EICra7SyQ+xdEE0/CX02QsP6TshT8PFv3HXKNjJ+tu9O ULf6W5QxFe2MNppJc/JVvFThugR7rOmmgIOATX2nUnhUXN79k9s1c/+/GPNqqwqKWpTg pk7g==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="1EhD1x/v"; 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-162847-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-162847-linux.lists.archive=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [2604:1380:40f1:3f00::1]) by mx.google.com with ESMTPS id h4-20020a17090a580400b0029bb32706b9si21913703pji.47.2024.04.29.11.52.12 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 29 Apr 2024 11:52:13 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel+bounces-162847-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="1EhD1x/v"; 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-162847-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-162847-linux.lists.archive=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 08019B21D98 for ; Mon, 29 Apr 2024 18:46:51 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 93A0913AD38; Mon, 29 Apr 2024 18:46:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="1EhD1x/v" 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 D06DF13AA3A for ; Mon, 29 Apr 2024 18:46:27 +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=1714416389; cv=none; b=KcwevMIfO3CeYLGpA6DZ1P0j+C2Gc5NBgBm8uVZh2UP+d6kKypC4i9wdvftPo7HROBUiAF7ra5kqPRDoRMP7tnWcqBUxcWjLQKpUVgD7CsCjPs1M67Mb4lYZUhgnGqRJQpQ5wDWmZr4IF+c2bWWDTb1nfkZGu4p+zpCp8HzJl/8= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714416389; c=relaxed/simple; bh=C/lc+AGf/Tq5IYjiIijITz1XV9PrHM6TD0L9DK0tCu0=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=tpcmBgfnzsSHL6T0ZpqMY9ATD27NF+vjtTxWtDWggoSXeEUTGrhN35tEzyeJwvE9X9/Eu2FVzq/IwVTBn3fsWC7SVlZcNXmh+hcYeu+hAtrg5a+iU/sqreS0yBnerk9tjF8/UAMVolNUmz5wyUX0dVdBybzoyNaHU0H1RV6xI0c= 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=1EhD1x/v; 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-61b2ef746c9so88430257b3.1 for ; Mon, 29 Apr 2024 11:46:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714416387; x=1715021187; 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=Xf9DU2dnw7wispX/TBVDNkoG04QwKWtFDLd1toiCdnE=; b=1EhD1x/vEJEJsM4FWkHlSvGz5DaSghgDPxeBN1dgoCAn/w0JPuK2PfPrjbdxGBZvLO 6GytW+O1KFeFXzh6MMIpYPVwCsbbcsTezpDvTotdIwXXpk6SJAYeCEV3Ti7Eo/A3JMbO 3ajObT9fSFwPKDGZeLqpa0iH01C+e2zoRCHSS+58SKv0PWo+CNKKh8lSkOLV9KoQ2Wec NOpQEbND5rQ39m8BViUf0S7PCmQzpKy+6KnGQutVuW3LNgE+r24Jq3leBbooFWYENpbt 9YSma0BYibNLj4hP8GUlDpU+3NjQI7Aq4dqDjLCcQTosoSDvtau6uF+cakLxY6n1OtMG oNkQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714416387; x=1715021187; 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=Xf9DU2dnw7wispX/TBVDNkoG04QwKWtFDLd1toiCdnE=; b=Qa0wCeVNIN7PYYaMxYqOokt71teaEVYRW8SI+Ak+7ZEWXZHQg0+mK4y9K3rKNS8r3V c4VLnNdC3GGOantVxblEXi/EMgOUB1V62hBqiUqrpHIHGW/haIO7ytVA3tTA2Y3yjUXR +iYqSNIKWRmyFzkN3kmUMiXPf5Lz26ApIP6L24UuER2qNnx2x/nwL95mULncR9gY+5DP OgDrt5mwkjJHRaXCWDwC4VVyqcmgNCqwv/3sHq3Sw+54LTDjnbpfB+14zC/W4xgcsoyb +OM3phN/W8Lv3aPknnLSNM5fzwk/J2P/jFYx/dHvNSIZl0CnT09IJWHw/idNxX8S83A3 PDtQ== X-Forwarded-Encrypted: i=1; AJvYcCX3tJGBRd5AlwVbm3fwRUm46tvx/u1Mj7A5+SBX++27/B+PAraUsxyU/78gI+Rx6A0WrcXaORlxGt4eeQ6cWNUeqV5enTKQ9xh4pLas X-Gm-Message-State: AOJu0Yx4tIELljXzksaDvXJqcsNLQ0iPlpwd1sZlF1yW4qsQf5wPWRDT CSx/seaCmq38tZWxnIfQ/tZqcSpqEC8bVN7FnHsFGXvwyHw5mO5pFmRFrcteEtqNebPUDIBzj6J ZA6TS9w== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:c137:aa10:25e1:8f1e]) (user=irogers job=sendgmr) by 2002:a81:6cd2:0:b0:618:80c0:1a2e with SMTP id h201-20020a816cd2000000b0061880c01a2emr2918407ywc.6.1714416386799; Mon, 29 Apr 2024 11:46:26 -0700 (PDT) Date: Mon, 29 Apr 2024 11:46:08 -0700 In-Reply-To: <20240429184614.1224041-1-irogers@google.com> Message-Id: <20240429184614.1224041-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: <20240429184614.1224041-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.769.g3c40516874-goog Subject: [PATCH v5 1/7] perf dsos: Switch backing storage to array from rbtree/list From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , James Clark , Athira Rajeev , Colin Ian King , nabijaczleweli@nabijaczleweli.xyz, Leo Yan , Song Liu , Ilkka Koskinen , Ben Gainey , K Prateek Nayak , Yanteng Si , Sun Haiyong , Changbin Du , Andi Kleen , Thomas Richter , Masami Hiramatsu , Dima Kogan , zhaimingbing , Paran Lee , Li Dong , Tiezhu Yang , Yang Jihong , Chengen Du , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Type: text/plain; charset="UTF-8" DSOs were held on a list for fast iteration and in an rbtree for fast finds. Switch to using a lazily sorted array where iteration is just iterating through the array and binary searches are the same complexity as searching the rbtree. The find may need to sort the array first which does increase the complexity, but add operations have lower complexity and overall the complexity should remain about the same. The set name operations on the dso just records that the array is no longer sorted, avoiding complexity in rebalancing the rbtree. Tighter locking discipline is enforced to avoid the array being resorted while long and short names or ids are changed. The array is smaller in size, replacing 6 pointers with 2, and so even with extra allocated space in the array, the array may be 50% unoccupied, the memory saving should be at least 2x. Signed-off-by: Ian Rogers --- tools/perf/util/dso.c | 67 +++++++++------ tools/perf/util/dso.h | 10 +-- tools/perf/util/dsos.c | 188 ++++++++++++++++++++++++++--------------- tools/perf/util/dsos.h | 21 +++-- 4 files changed, 177 insertions(+), 109 deletions(-) diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c index ad562743d769..3caca60a6ce3 100644 --- a/tools/perf/util/dso.c +++ b/tools/perf/util/dso.c @@ -1241,35 +1241,35 @@ struct dso *machine__findnew_kernel(struct machine *machine, const char *name, return dso; } -static void dso__set_long_name_id(struct dso *dso, const char *name, struct dso_id *id, bool name_allocated) +static void dso__set_long_name_id(struct dso *dso, const char *name, bool name_allocated) { - struct rb_root *root = dso->root; + struct dsos *dsos = dso->dsos; if (name == NULL) return; - if (dso->long_name_allocated) - free((char *)dso->long_name); - - if (root) { - rb_erase(&dso->rb_node, root); + if (dsos) { /* - * __dsos__findnew_link_by_longname_id() isn't guaranteed to - * add it back, so a clean removal is required here. + * Need to avoid re-sorting the dsos breaking by non-atomically + * renaming the dso. */ - RB_CLEAR_NODE(&dso->rb_node); - dso->root = NULL; + down_write(&dsos->lock); } + if (dso->long_name_allocated) + free((char *)dso->long_name); + dso->long_name = name; dso->long_name_len = strlen(name); dso->long_name_allocated = name_allocated; - if (root) - __dsos__findnew_link_by_longname_id(root, dso, NULL, id); + if (dsos) { + dsos->sorted = false; + up_write(&dsos->lock); + } } -static int __dso_id__cmp(struct dso_id *a, struct dso_id *b) +static int __dso_id__cmp(const struct dso_id *a, const struct dso_id *b) { if (a->maj > b->maj) return -1; if (a->maj < b->maj) return 1; @@ -1297,7 +1297,7 @@ static int __dso_id__cmp(struct dso_id *a, struct dso_id *b) return 0; } -bool dso_id__empty(struct dso_id *id) +bool dso_id__empty(const struct dso_id *id) { if (!id) return true; @@ -1305,15 +1305,22 @@ bool dso_id__empty(struct dso_id *id) return !id->maj && !id->min && !id->ino && !id->ino_generation; } -void dso__inject_id(struct dso *dso, struct dso_id *id) +void __dso__inject_id(struct dso *dso, struct dso_id *id) { + struct dsos *dsos = dso->dsos; + + /* dsos write lock held by caller. */ + dso->id.maj = id->maj; dso->id.min = id->min; dso->id.ino = id->ino; dso->id.ino_generation = id->ino_generation; + + if (dsos) + dsos->sorted = false; } -int dso_id__cmp(struct dso_id *a, struct dso_id *b) +int dso_id__cmp(const struct dso_id *a, const struct dso_id *b) { /* * The second is always dso->id, so zeroes if not set, assume passing @@ -1332,20 +1339,34 @@ int dso__cmp_id(struct dso *a, struct dso *b) void dso__set_long_name(struct dso *dso, const char *name, bool name_allocated) { - dso__set_long_name_id(dso, name, NULL, name_allocated); + dso__set_long_name_id(dso, name, name_allocated); } void dso__set_short_name(struct dso *dso, const char *name, bool name_allocated) { + struct dsos *dsos = dso->dsos; + if (name == NULL) return; + if (dsos) { + /* + * Need to avoid re-sorting the dsos breaking by non-atomically + * renaming the dso. + */ + down_write(&dsos->lock); + } if (dso->short_name_allocated) free((char *)dso->short_name); dso->short_name = name; dso->short_name_len = strlen(name); dso->short_name_allocated = name_allocated; + + if (dsos) { + dsos->sorted = false; + up_write(&dsos->lock); + } } int dso__name_len(const struct dso *dso) @@ -1381,7 +1402,7 @@ struct dso *dso__new_id(const char *name, struct dso_id *id) strcpy(dso->name, name); if (id) dso->id = *id; - dso__set_long_name_id(dso, dso->name, id, false); + dso__set_long_name_id(dso, dso->name, false); dso__set_short_name(dso, dso->name, false); dso->symbols = RB_ROOT_CACHED; dso->symbol_names = NULL; @@ -1406,9 +1427,6 @@ struct dso *dso__new_id(const char *name, struct dso_id *id) dso->is_kmod = 0; dso->needs_swap = DSO_SWAP__UNSET; dso->comp = COMP_ID__NONE; - RB_CLEAR_NODE(&dso->rb_node); - dso->root = NULL; - INIT_LIST_HEAD(&dso->node); INIT_LIST_HEAD(&dso->data.open_entry); mutex_init(&dso->lock); refcount_set(&dso->refcnt, 1); @@ -1424,9 +1442,8 @@ struct dso *dso__new(const char *name) void dso__delete(struct dso *dso) { - if (!RB_EMPTY_NODE(&dso->rb_node)) - pr_err("DSO %s is still in rbtree when being deleted!\n", - dso->long_name); + if (dso->dsos) + pr_err("DSO %s is still in rbtree when being deleted!\n", dso->long_name); /* free inlines first, as they reference symbols */ inlines__tree_delete(&dso->inlined_nodes); diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h index 2c295438226d..b22dec8b3f3a 100644 --- a/tools/perf/util/dso.h +++ b/tools/perf/util/dso.h @@ -146,9 +146,7 @@ struct auxtrace_cache; struct dso { struct mutex lock; - struct list_head node; - struct rb_node rb_node; /* rbtree node sorted by long name */ - struct rb_root *root; /* root of rbtree that rb_node is in */ + struct dsos *dsos; struct rb_root_cached symbols; struct symbol **symbol_names; size_t symbol_names_len; @@ -238,8 +236,8 @@ static inline void dso__set_loaded(struct dso *dso) dso->loaded = true; } -int dso_id__cmp(struct dso_id *a, struct dso_id *b); -bool dso_id__empty(struct dso_id *id); +int dso_id__cmp(const struct dso_id *a, const struct dso_id *b); +bool dso_id__empty(const struct dso_id *id); struct dso *dso__new_id(const char *name, struct dso_id *id); struct dso *dso__new(const char *name); @@ -248,7 +246,7 @@ void dso__delete(struct dso *dso); int dso__cmp_id(struct dso *a, struct dso *b); void dso__set_short_name(struct dso *dso, const char *name, bool name_allocated); void dso__set_long_name(struct dso *dso, const char *name, bool name_allocated); -void dso__inject_id(struct dso *dso, struct dso_id *id); +void __dso__inject_id(struct dso *dso, struct dso_id *id); int dso__name_len(const struct dso *dso); diff --git a/tools/perf/util/dsos.c b/tools/perf/util/dsos.c index b7fbfb877ae3..cfc10e1a6802 100644 --- a/tools/perf/util/dsos.c +++ b/tools/perf/util/dsos.c @@ -14,24 +14,30 @@ void dsos__init(struct dsos *dsos) { - INIT_LIST_HEAD(&dsos->head); - dsos->root = RB_ROOT; init_rwsem(&dsos->lock); + + dsos->cnt = 0; + dsos->allocated = 0; + dsos->dsos = NULL; + dsos->sorted = true; } static void dsos__purge(struct dsos *dsos) { - struct dso *pos, *n; - down_write(&dsos->lock); - list_for_each_entry_safe(pos, n, &dsos->head, node) { - RB_CLEAR_NODE(&pos->rb_node); - pos->root = NULL; - list_del_init(&pos->node); - dso__put(pos); + for (unsigned int i = 0; i < dsos->cnt; i++) { + struct dso *dso = dsos->dsos[i]; + + dso__put(dso); + dso->dsos = NULL; } + zfree(&dsos->dsos); + dsos->cnt = 0; + dsos->allocated = 0; + dsos->sorted = true; + up_write(&dsos->lock); } @@ -46,9 +52,8 @@ static int __dsos__for_each_dso(struct dsos *dsos, int (*cb)(struct dso *dso, void *data), void *data) { - struct dso *dso; - - list_for_each_entry(dso, &dsos->head, node) { + for (unsigned int i = 0; i < dsos->cnt; i++) { + struct dso *dso = dsos->dsos[i]; int err; err = cb(dso, data); @@ -119,16 +124,47 @@ static int dso__cmp_short_name(struct dso *a, struct dso *b) return __dso__cmp_short_name(a->short_name, &a->id, b); } +static int dsos__cmp_long_name_id_short_name(const void *va, const void *vb) +{ + const struct dso *a = *((const struct dso **)va); + const struct dso *b = *((const struct dso **)vb); + int rc = strcmp(a->long_name, b->long_name); + + if (!rc) { + rc = dso_id__cmp(&a->id, &b->id); + if (!rc) + rc = strcmp(a->short_name, b->short_name); + } + return rc; +} + /* * Find a matching entry and/or link current entry to RB tree. * Either one of the dso or name parameter must be non-NULL or the * function will not work. */ -struct dso *__dsos__findnew_link_by_longname_id(struct rb_root *root, struct dso *dso, - const char *name, struct dso_id *id) +struct dso *__dsos__findnew_link_by_longname_id(struct dsos *dsos, + struct dso *dso, + const char *name, + struct dso_id *id, + bool write_locked) { - struct rb_node **p = &root->rb_node; - struct rb_node *parent = NULL; + int low = 0, high = dsos->cnt - 1; + + if (!dsos->sorted) { + if (!write_locked) { + up_read(&dsos->lock); + down_write(&dsos->lock); + dso = __dsos__findnew_link_by_longname_id(dsos, dso, name, id, + /*write_locked=*/true); + up_write(&dsos->lock); + down_read(&dsos->lock); + return dso; + } + qsort(dsos->dsos, dsos->cnt, sizeof(struct dso *), + dsos__cmp_long_name_id_short_name); + dsos->sorted = true; + } if (!name) name = dso->long_name; @@ -136,11 +172,11 @@ struct dso *__dsos__findnew_link_by_longname_id(struct rb_root *root, struct dso /* * Find node with the matching name */ - while (*p) { - struct dso *this = rb_entry(*p, struct dso, rb_node); + while (low <= high) { + int mid = (low + high) / 2; + struct dso *this = dsos->dsos[mid]; int rc = __dso__cmp_long_name(name, id, this); - parent = *p; if (rc == 0) { /* * In case the new DSO is a duplicate of an existing @@ -161,56 +197,53 @@ struct dso *__dsos__findnew_link_by_longname_id(struct rb_root *root, struct dso } } if (rc < 0) - p = &parent->rb_left; + high = mid - 1; else - p = &parent->rb_right; - } - if (dso) { - /* Add new node and rebalance tree */ - rb_link_node(&dso->rb_node, parent, p); - rb_insert_color(&dso->rb_node, root); - dso->root = root; + low = mid + 1; } + if (dso) + __dsos__add(dsos, dso); return NULL; } -void __dsos__add(struct dsos *dsos, struct dso *dso) +int __dsos__add(struct dsos *dsos, struct dso *dso) { - list_add_tail(&dso->node, &dsos->head); - __dsos__findnew_link_by_longname_id(&dsos->root, dso, NULL, &dso->id); - /* - * It is now in the linked list, grab a reference, then garbage collect - * this when needing memory, by looking at LRU dso instances in the - * list with atomic_read(&dso->refcnt) == 1, i.e. no references - * anywhere besides the one for the list, do, under a lock for the - * list: remove it from the list, then a dso__put(), that probably will - * be the last and will then call dso__delete(), end of life. - * - * That, or at the end of the 'struct machine' lifetime, when all - * 'struct dso' instances will be removed from the list, in - * dsos__exit(), if they have no other reference from some other data - * structure. - * - * E.g.: after processing a 'perf.data' file and storing references - * to objects instantiated while processing events, we will have - * references to the 'thread', 'map', 'dso' structs all from 'struct - * hist_entry' instances, but we may not need anything not referenced, - * so we might as well call machines__exit()/machines__delete() and - * garbage collect it. - */ - dso__get(dso); + if (dsos->cnt == dsos->allocated) { + unsigned int to_allocate = 2; + struct dso **temp; + + if (dsos->allocated > 0) + to_allocate = dsos->allocated * 2; + temp = realloc(dsos->dsos, sizeof(struct dso *) * to_allocate); + if (!temp) + return -ENOMEM; + dsos->dsos = temp; + dsos->allocated = to_allocate; + } + dsos->dsos[dsos->cnt++] = dso__get(dso); + if (dsos->cnt >= 2 && dsos->sorted) { + dsos->sorted = dsos__cmp_long_name_id_short_name(&dsos->dsos[dsos->cnt - 2], + &dsos->dsos[dsos->cnt - 1]) + <= 0; + } + dso->dsos = dsos; + return 0; } -void dsos__add(struct dsos *dsos, struct dso *dso) +int dsos__add(struct dsos *dsos, struct dso *dso) { + int ret; + down_write(&dsos->lock); - __dsos__add(dsos, dso); + ret = __dsos__add(dsos, dso); up_write(&dsos->lock); + return ret; } -static struct dso *__dsos__findnew_by_longname_id(struct rb_root *root, const char *name, struct dso_id *id) +static struct dso *__dsos__findnew_by_longname_id(struct dsos *dsos, const char *name, + struct dso_id *id, bool write_locked) { - return __dsos__findnew_link_by_longname_id(root, NULL, name, id); + return __dsos__findnew_link_by_longname_id(dsos, NULL, name, id, write_locked); } struct dsos__find_id_cb_args { @@ -231,7 +264,8 @@ static int dsos__find_id_cb(struct dso *dso, void *data) } -static struct dso *__dsos__find_id(struct dsos *dsos, const char *name, struct dso_id *id, bool cmp_short) +static struct dso *__dsos__find_id(struct dsos *dsos, const char *name, struct dso_id *id, + bool cmp_short, bool write_locked) { struct dso *res; @@ -245,7 +279,7 @@ static struct dso *__dsos__find_id(struct dsos *dsos, const char *name, struct d __dsos__for_each_dso(dsos, dsos__find_id_cb, &args); return args.res; } - res = __dsos__findnew_by_longname_id(&dsos->root, name, id); + res = __dsos__findnew_by_longname_id(dsos, name, id, write_locked); return res; } @@ -254,7 +288,7 @@ struct dso *dsos__find(struct dsos *dsos, const char *name, bool cmp_short) struct dso *res; down_read(&dsos->lock); - res = __dsos__find_id(dsos, name, NULL, cmp_short); + res = __dsos__find_id(dsos, name, NULL, cmp_short, /*write_locked=*/false); up_read(&dsos->lock); return res; } @@ -296,8 +330,13 @@ static struct dso *__dsos__addnew_id(struct dsos *dsos, const char *name, struct struct dso *dso = dso__new_id(name, id); if (dso != NULL) { - __dsos__add(dsos, dso); + /* + * The dsos lock is held on entry, so rename the dso before + * adding it to avoid needing to take the dsos lock again to say + * the array isn't sorted. + */ dso__set_basename(dso); + __dsos__add(dsos, dso); } return dso; } @@ -309,10 +348,10 @@ struct dso *__dsos__addnew(struct dsos *dsos, const char *name) static struct dso *__dsos__findnew_id(struct dsos *dsos, const char *name, struct dso_id *id) { - struct dso *dso = __dsos__find_id(dsos, name, id, false); + struct dso *dso = __dsos__find_id(dsos, name, id, false, /*write_locked=*/true); if (dso && dso_id__empty(&dso->id) && !dso_id__empty(id)) - dso__inject_id(dso, id); + __dso__inject_id(dso, id); return dso ? dso : __dsos__addnew_id(dsos, name, id); } @@ -403,18 +442,27 @@ struct dso *dsos__findnew_module_dso(struct dsos *dsos, down_write(&dsos->lock); - dso = __dsos__find_id(dsos, m->name, NULL, /*cmp_short=*/true); + dso = __dsos__find_id(dsos, m->name, NULL, /*cmp_short=*/true, /*write_locked=*/true); + if (dso) { + up_write(&dsos->lock); + return dso; + } + /* + * Failed to find the dso so create it. Change the name before adding it + * to the array, to avoid unnecessary sorts and potential locking + * issues. + */ + dso = dso__new_id(m->name, /*id=*/NULL); if (!dso) { - dso = __dsos__addnew(dsos, m->name); - if (dso == NULL) - goto out_unlock; - - dso__set_module_info(dso, m, machine); - dso__set_long_name(dso, strdup(filename), true); - dso->kernel = DSO_SPACE__KERNEL; + up_write(&dsos->lock); + return NULL; } + dso__set_basename(dso); + dso__set_module_info(dso, m, machine); + dso__set_long_name(dso, strdup(filename), true); + dso->kernel = DSO_SPACE__KERNEL; + __dsos__add(dsos, dso); -out_unlock: up_write(&dsos->lock); return dso; } diff --git a/tools/perf/util/dsos.h b/tools/perf/util/dsos.h index 50bd51523475..c1b3979ad4bd 100644 --- a/tools/perf/util/dsos.h +++ b/tools/perf/util/dsos.h @@ -14,20 +14,22 @@ struct kmod_path; struct machine; /* - * DSOs are put into both a list for fast iteration and rbtree for fast - * long name lookup. + * Collection of DSOs as an array for iteration speed, but sorted for O(n) + * lookup. */ struct dsos { - struct list_head head; - struct rb_root root; /* rbtree root sorted by long name */ struct rw_semaphore lock; + struct dso **dsos; + unsigned int cnt; + unsigned int allocated; + bool sorted; }; void dsos__init(struct dsos *dsos); void dsos__exit(struct dsos *dsos); -void __dsos__add(struct dsos *dsos, struct dso *dso); -void dsos__add(struct dsos *dsos, struct dso *dso); +int __dsos__add(struct dsos *dsos, struct dso *dso); +int dsos__add(struct dsos *dsos, struct dso *dso); struct dso *__dsos__addnew(struct dsos *dsos, const char *name); struct dso *dsos__find(struct dsos *dsos, const char *name, bool cmp_short); @@ -35,8 +37,11 @@ struct dso *dsos__findnew_id(struct dsos *dsos, const char *name, struct dso_id bool dsos__read_build_ids(struct dsos *dsos, bool with_hits); -struct dso *__dsos__findnew_link_by_longname_id(struct rb_root *root, struct dso *dso, - const char *name, struct dso_id *id); +struct dso *__dsos__findnew_link_by_longname_id(struct dsos *dsos, + struct dso *dso, + const char *name, + struct dso_id *id, + bool write_locked); size_t dsos__fprintf_buildid(struct dsos *dsos, FILE *fp, bool (skip)(struct dso *dso, int parm), int parm); -- 2.44.0.769.g3c40516874-goog