linux-kernel - Re: [PATCH v2 1/2] perf sharded_mutex: Introduce sharded

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

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAM9d7cigCUz4i-t2rHaz9Ch0oWxjYWmvnVB73uV1cm+47DtpXw@mail.gmail.com>
Date:   Tue, 20 Jun 2023 15:15:30 -0700
From:   Namhyung Kim <namhyung@...nel.org>
To:     Ian Rogers <irogers@...gle.com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Mark Rutland <mark.rutland@....com>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        Jiri Olsa <jolsa@...nel.org>,
        Adrian Hunter <adrian.hunter@...el.com>,
        Yuan Can <yuancan@...wei.com>,
        Kan Liang <kan.liang@...ux.intel.com>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Huacai Chen <chenhuacai@...nel.org>,
        Andres Freund <andres@...razel.de>,
        linux-kernel@...r.kernel.org, linux-perf-users@...r.kernel.org
Subject: Re: [PATCH v2 1/2] perf sharded_mutex: Introduce sharded_mutex

On Wed, Jun 14, 2023 at 9:07 PM Ian Rogers <irogers@...gle.com> wrote:
>
> Per object mutexes may come with significant memory cost while a
> global mutex can suffer from unnecessary contention. A sharded mutex
> is a compromise where objects are hashed and then a particular mutex
> for the hash of the object used. Contention can be controlled by the
> number of shards.
>
> Signed-off-by: Ian Rogers <irogers@...gle.com>

Acked-by: Namhyung Kim <namhyung@...nel.org>

Thanks,
Namhyung

>
> v2. Use hashmap.h's hash_bits in case of contention from alignment of
>     objects.
> ---
>  tools/perf/util/Build           |  1 +
>  tools/perf/util/sharded_mutex.c | 33 +++++++++++++++++++++++++++++++++
>  tools/perf/util/sharded_mutex.h | 29 +++++++++++++++++++++++++++++
>  3 files changed, 63 insertions(+)
>  create mode 100644 tools/perf/util/sharded_mutex.c
>  create mode 100644 tools/perf/util/sharded_mutex.h
>
> diff --git a/tools/perf/util/Build b/tools/perf/util/Build
> index ff2fd1a36bb8..96f4ea1d45c5 100644
> --- a/tools/perf/util/Build
> +++ b/tools/perf/util/Build
> @@ -145,6 +145,7 @@ perf-y += mem2node.o
>  perf-y += clockid.o
>  perf-y += list_sort.o
>  perf-y += mutex.o
> +perf-y += sharded_mutex.o
>
>  perf-$(CONFIG_LIBBPF) += bpf-loader.o
>  perf-$(CONFIG_LIBBPF) += bpf_map.o
> diff --git a/tools/perf/util/sharded_mutex.c b/tools/perf/util/sharded_mutex.c
> new file mode 100644
> index 000000000000..e11e8d0945a7
> --- /dev/null
> +++ b/tools/perf/util/sharded_mutex.c
> @@ -0,0 +1,33 @@
> +// SPDX-License-Identifier: GPL-2.0
> +#include "sharded_mutex.h"
> +
> +#include <stdlib.h>
> +
> +struct sharded_mutex *sharded_mutex__new(size_t num_shards)
> +{
> +       struct sharded_mutex *result;
> +       size_t size;
> +       unsigned int bits;
> +
> +       for (bits = 0; ((size_t)1 << bits) < num_shards; bits++)
> +               ;
> +
> +       size = sizeof(*result) + sizeof(struct mutex) * (1 << bits);
> +       result = malloc(size);
> +       if (!result)
> +               return NULL;
> +
> +       result->cap_bits = bits;
> +       for (size_t i = 0; i < ((size_t)1 << bits); i++)
> +               mutex_init(&result->mutexes[i]);
> +
> +       return result;
> +}
> +
> +void sharded_mutex__delete(struct sharded_mutex *sm)
> +{
> +       for (size_t i = 0; i < ((size_t)1 << sm->cap_bits); i++)
> +               mutex_destroy(&sm->mutexes[i]);
> +
> +       free(sm);
> +}
> diff --git a/tools/perf/util/sharded_mutex.h b/tools/perf/util/sharded_mutex.h
> new file mode 100644
> index 000000000000..7325e969eee3
> --- /dev/null
> +++ b/tools/perf/util/sharded_mutex.h
> @@ -0,0 +1,29 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef PERF_SHARDED_MUTEX_H
> +#define PERF_SHARDED_MUTEX_H
> +
> +#include "mutex.h"
> +#include "hashmap.h"
> +
> +/*
> + * In a situation where a lock is needed per object, having a mutex can be
> + * relatively memory expensive (40 bytes on x86-64). If the object can be
> + * constantly hashed, a sharded mutex is an alternative global pool of mutexes
> + * where the mutex is looked up from a hash value. This can lead to collisions
> + * if the number of shards isn't large enough.
> + */
> +struct sharded_mutex {
> +       /* mutexes array is 1<<cap_bits in size. */
> +       unsigned int cap_bits;
> +       struct mutex mutexes[];
> +};
> +
> +struct sharded_mutex *sharded_mutex__new(size_t num_shards);
> +void sharded_mutex__delete(struct sharded_mutex *sm);
> +
> +static inline struct mutex *sharded_mutex__get_mutex(struct sharded_mutex *sm, size_t hash)
> +{
> +       return &sm->mutexes[hash_bits(hash, sm->cap_bits)];
> +}
> +
> +#endif  /* PERF_SHARDED_MUTEX_H */
> --
> 2.41.0.162.gfafddb0af9-goog
>