| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20250410044532.52017-3-irogers@google.com>
Date: Wed, 9 Apr 2025 21:45:31 -0700
From: Ian Rogers <irogers@...gle.com>
To: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>,
Arnaldo Carvalho de Melo <acme@...nel.org>, Namhyung Kim <namhyung@...nel.org>,
Mark Rutland <mark.rutland@....com>,
Alexander Shishkin <alexander.shishkin@...ux.intel.com>, Jiri Olsa <jolsa@...nel.org>,
Ian Rogers <irogers@...gle.com>, Adrian Hunter <adrian.hunter@...el.com>,
Kan Liang <kan.liang@...ux.intel.com>, James Clark <james.clark@...aro.org>,
Xu Yang <xu.yang_2@....com>, John Garry <john.g.garry@...cle.com>,
Dominique Martinet <asmadeus@...ewreck.org>, Thomas Richter <tmricht@...ux.ibm.com>,
Weilin Wang <weilin.wang@...el.com>, linux-perf-users@...r.kernel.org,
linux-kernel@...r.kernel.org
Subject: [PATCH v1 2/3] perf fncache: Switch to using hashmap
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 <irogers@...gle.com>
---
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 <pthread.h>
#include <stdlib.h>
-#include <unistd.h>
#include <string.h>
-#include <linux/list.h>
+#include <unistd.h>
+#include <linux/compiler.h>
#include "fncache.h"
+#include "hashmap.h"
-struct fncache {
- struct hlist_node nd;
- bool res;
- char name[];
-};
+static struct hashmap *fncache;
-#define FNHSIZE 61
+static size_t fncache__hash(long key, void *ctx __maybe_unused)
+{
+ return str_hash((const char *)key);
+}
-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) == 0;
+}
-unsigned shash(const unsigned char *s)
+static void fncache__init(void)
{
- unsigned h = 0;
- while (*s)
- h = 65599 * h + *s++;
- return h ^ (h >> 16);
+ fncache = hashmap__new(fncache__hash, fncache__equal, /*ctx=*/NULL);
+}
+
+static struct hashmap *fncache__get(void)
+{
+ static pthread_once_t fncache_once = PTHREAD_ONCE_INIT;
+
+ pthread_once(&fncache_once, fncache__init);
+
+ return fncache;
}
static bool lookup_fncache(const char *name, bool *res)
{
- int h = shash((const unsigned char *)name) % FNHSIZE;
- struct fncache *n;
-
- hlist_for_each_entry(n, &fncache_hash[h], nd) {
- if (!strcmp(n->name, name)) {
- *res = n->res;
- return true;
- }
- }
- return false;
+ long val;
+
+ if (!hashmap__find(fncache__get(), name, &val))
+ return false;
+
+ *res = (val != 0);
+ return true;
}
static void update_fncache(const char *name, bool res)
{
- struct fncache *n = malloc(sizeof(struct fncache) + strlen(name) + 1);
- int h = shash((const unsigned char *)name) % FNHSIZE;
-
- if (!n)
- return;
- strcpy(n->name, name);
- n->res = res;
- hlist_add_head(&n->nd, &fncache_hash[h]);
+ char *old_key = NULL, *key = strdup(name);
+
+ if (key) {
+ hashmap__set(fncache__get(), key, res, &old_key, /*old_value*/NULL);
+ free(old_key);
+ }
}
/* 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
-unsigned shash(const unsigned char *s);
bool file_available(const char *name);
#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 <internal/lib.h> // page_size
-#include "fncache.h"
+#include "hashmap.h"
#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 = shash((unsigned char *)fn) % SRC_HTAB_SZ;
+ size_t hval = str_hash(fn) % SRC_HTAB_SZ;
hlist_for_each_entry (h, &srcfile_htab[hval], hash_nd) {
if (!strcmp(fn, h->fn)) {
--
2.49.0.504.g3bcea36a83-goog
Powered by blists - more mailing lists