From nobody Fri Dec 19 02:15:51 2025 Received: from mail-pl1-f202.google.com (mail-pl1-f202.google.com [209.85.214.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 BD6791F2382 for ; Thu, 10 Apr 2025 04:45:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744260352; cv=none; b=Vi+7Lhl1nPz5gsC9oo3hOTO/85L+z8aUUc5C36O8bn6bJ9EiEiK1X3dER7xPyuwv2jMRe3h0CZRwkgcvYQ4jvDhM0EdqPPisvyuV4e4ErYLGr4TcvAGR1Q5lJZN7Q7IetStLwZ79iurPl8fiQjv4kZ7EC3TIZ5QpTFadUmPsfwk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744260352; c=relaxed/simple; bh=5IWdSEs5RkgxPVslBBnAOjR4bNfmYgvr5rnu//KW2f8=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Content-Type; b=h/qIfjIubzCrTBFu0K1a0trgTeM4FGDDwQuJ8GfQhFHTximICWkauR1TZgZXI0fBj1K1fWPru33g4/KUcPSiBWyPApkJ1c7XqfYsl910k1ndNSeZr/UXPZn674aiM0/SGhxyy0xVBCTCFzYxTXRsWi/mBphu/R5jDOpKaEerLaM= 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=RWTHK1G3; arc=none smtp.client-ip=209.85.214.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 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="RWTHK1G3" Received: by mail-pl1-f202.google.com with SMTP id d9443c01a7336-225ab228a37so3790705ad.2 for ; Wed, 09 Apr 2025 21:45:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1744260350; x=1744865150; darn=vger.kernel.org; h=to:from:subject:message-id:references:mime-version:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=XcrobgRBNrn1wKrgLsSHY40XqyQBijRELNTpL5HXaa8=; b=RWTHK1G3GPc06uO9QRL6vA/N6SuV0l3oJ+x+8Ix3Nwy3juGo5aBlDSsRtOUbOFti0C JiUckLqmKOlAveBUTtLZycJppZ++CjKoqiJIr/RgM6YBm+JZTjzCz3nVOm6KKLVZhBmS 5U63EryU8Uga8tD/GOWti6ioeE02sAryCF1r+V8ypDiv0fkx8c7nrHFWeOkMQrwCS2lp vGZGCN9rp6DsdHOn9JD9EoKo87/o/j157kEC120i+TCzHItNbN7ESE9h2zFCvewD+D5Z sfyf4PnwIIyEvtaONyyOvL9CP2NR6D1ebPKm2oxLRvk7dMzuVhBo6R9FoVewXNyxPlTr 4+Zw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1744260350; x=1744865150; h=to:from:subject:message-id:references:mime-version:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=XcrobgRBNrn1wKrgLsSHY40XqyQBijRELNTpL5HXaa8=; b=I54J8hinpIB4N4sGVijoL68eMRGBFxrFzu9qre/zOydnaKolY51/tQwftpvSsBSFqQ GQfLbgkv8GTPYmPE8q+Y1tFny4Id7rNBSHV/j+U4YAVImZOK1b9ajWUmfQPJ4I8ouN+m W3ZZ20zFl4YfiUjp4/ofUELEfHaXRyF0nTwgXOWNB8Cnn6JmCBrQtrdNG2b/xwzJ55wo UxaYDQX+9oRua4hKkrNwQLSBbEkrK8LJNYml4qQ+uq9H1V9jWv4nBh3bgp1eVKQV1oUE 1nheWOdj+5DmYr9wauJYU+gDmZ/RgmmflzjlgeQ/FCTFaED17rhGAECmo595GFyFuB+h NPlA== X-Forwarded-Encrypted: i=1; AJvYcCUSTgFAzORJQOPvMscUwZwlKyX42eNumdd6Ci1BbctLflIIfwU9b9DB6Z7fKxDIJF40dw6y5MmIFq80248=@vger.kernel.org X-Gm-Message-State: AOJu0YwkaZs8tQ4e2Jyz3cS4DusQ09YHdq8vpn/Fo/3hrCOJTtKiP+BQ J9x1s7q7l1ZE0b9phEqiHSIokLUS18ovuvUobuPJ8lgTkNg5xcR/SQbzS/mfAJk5/v5iMiuYBOr 8jEzK1Q== X-Google-Smtp-Source: AGHT+IE1L1jhTV/Iqzj96GX/ADTgcRAasuICr/zf33xj4shXNQzNr2Gtp4uDqEcgLNtPkC9CEe/8mHnmT3oT X-Received: from plblc7.prod.google.com ([2002:a17:902:fa87:b0:21f:40e5:a651]) (user=irogers job=prod-delivery.src-stubby-dispatcher) by 2002:a17:902:db03:b0:223:35cb:e421 with SMTP id d9443c01a7336-22b42c2e587mr18531705ad.49.1744260349994; Wed, 09 Apr 2025 21:45:49 -0700 (PDT) Date: Wed, 9 Apr 2025 21:45:31 -0700 In-Reply-To: <20250410044532.52017-1-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250410044532.52017-1-irogers@google.com> X-Mailer: git-send-email 2.49.0.504.g3bcea36a83-goog Message-ID: <20250410044532.52017-3-irogers@google.com> Subject: [PATCH v1 2/3] perf fncache: Switch to using hashmap 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 , Xu Yang , John Garry , Dominique Martinet , Thomas Richter , Weilin Wang , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The existing fncache can get large in testing situations. As the bucket array is a fixed size this leads to it degrading to O(n) performance. Use a regular hashmap that can dynamically reallocate its array. Before: ``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m17.887s user 0m17.525s sys 0m3.310s ``` After: ``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m15.551s user 0m15.092s sys 0m3.009s ``` Signed-off-by: Ian Rogers --- tools/perf/util/fncache.c | 69 +++++++++++++++++++++------------------ tools/perf/util/fncache.h | 1 - tools/perf/util/srccode.c | 4 +-- 3 files changed, 39 insertions(+), 35 deletions(-) diff --git a/tools/perf/util/fncache.c b/tools/perf/util/fncache.c index 6225cbc52310..bf9559c55c63 100644 --- a/tools/perf/util/fncache.c +++ b/tools/perf/util/fncache.c @@ -1,53 +1,58 @@ // SPDX-License-Identifier: GPL-2.0-only /* Manage a cache of file names' existence */ +#include #include -#include #include -#include +#include +#include #include "fncache.h" +#include "hashmap.h" =20 -struct fncache { - struct hlist_node nd; - bool res; - char name[]; -}; +static struct hashmap *fncache; =20 -#define FNHSIZE 61 +static size_t fncache__hash(long key, void *ctx __maybe_unused) +{ + return str_hash((const char *)key); +} =20 -static struct hlist_head fncache_hash[FNHSIZE]; +static bool fncache__equal(long key1, long key2, void *ctx __maybe_unused) +{ + return strcmp((const char *)key1, (const char *)key2) =3D=3D 0; +} =20 -unsigned shash(const unsigned char *s) +static void fncache__init(void) { - unsigned h =3D 0; - while (*s) - h =3D 65599 * h + *s++; - return h ^ (h >> 16); + fncache =3D hashmap__new(fncache__hash, fncache__equal, /*ctx=3D*/NULL); +} + +static struct hashmap *fncache__get(void) +{ + static pthread_once_t fncache_once =3D PTHREAD_ONCE_INIT; + + pthread_once(&fncache_once, fncache__init); + + return fncache; } =20 static bool lookup_fncache(const char *name, bool *res) { - int h =3D shash((const unsigned char *)name) % FNHSIZE; - struct fncache *n; - - hlist_for_each_entry(n, &fncache_hash[h], nd) { - if (!strcmp(n->name, name)) { - *res =3D n->res; - return true; - } - } - return false; + long val; + + if (!hashmap__find(fncache__get(), name, &val)) + return false; + + *res =3D (val !=3D 0); + return true; } =20 static void update_fncache(const char *name, bool res) { - struct fncache *n =3D malloc(sizeof(struct fncache) + strlen(name) + 1); - int h =3D shash((const unsigned char *)name) % FNHSIZE; - - if (!n) - return; - strcpy(n->name, name); - n->res =3D res; - hlist_add_head(&n->nd, &fncache_hash[h]); + char *old_key =3D NULL, *key =3D strdup(name); + + if (key) { + hashmap__set(fncache__get(), key, res, &old_key, /*old_value*/NULL); + free(old_key); + } } =20 /* No LRU, only use when bounded in some other way. */ diff --git a/tools/perf/util/fncache.h b/tools/perf/util/fncache.h index fe020beaefb1..b6a0f209493e 100644 --- a/tools/perf/util/fncache.h +++ b/tools/perf/util/fncache.h @@ -1,7 +1,6 @@ #ifndef _FCACHE_H #define _FCACHE_H 1 =20 -unsigned shash(const unsigned char *s); bool file_available(const char *name); =20 #endif diff --git a/tools/perf/util/srccode.c b/tools/perf/util/srccode.c index 476e99896d5e..0f4907843ac1 100644 --- a/tools/perf/util/srccode.c +++ b/tools/perf/util/srccode.c @@ -16,7 +16,7 @@ #include "srccode.h" #include "debug.h" #include // page_size -#include "fncache.h" +#include "hashmap.h" =20 #define MAXSRCCACHE (32*1024*1024) #define MAXSRCFILES 64 @@ -92,7 +92,7 @@ static struct srcfile *find_srcfile(char *fn) struct srcfile *h; int fd; unsigned long sz; - unsigned hval =3D shash((unsigned char *)fn) % SRC_HTAB_SZ; + size_t hval =3D str_hash(fn) % SRC_HTAB_SZ; =20 hlist_for_each_entry (h, &srcfile_htab[hval], hash_nd) { if (!strcmp(fn, h->fn)) { --=20 2.49.0.504.g3bcea36a83-goog