linux-kernel - Re: [RFC PATCH v4 04/15] find_bit: add _find_last_and_bit() to support finding the most significant set bit

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CAP-5=fVUJayXeKwtCnSjoUrw0HMJJa00RYrMhm-stjUwxDyefQ@mail.gmail.com>
Date: Sat, 23 Mar 2024 21:19:57 -0700
From: Ian Rogers <irogers@...gle.com>
To: weilin.wang@...el.com
Cc: Kan Liang <kan.liang@...ux.intel.com>, Namhyung Kim <namhyung@...nel.org>, 
	Arnaldo Carvalho de Melo <acme@...nel.org>, Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>, 
	Alexander Shishkin <alexander.shishkin@...ux.intel.com>, Jiri Olsa <jolsa@...nel.org>, 
	Adrian Hunter <adrian.hunter@...el.com>, linux-perf-users@...r.kernel.org, 
	linux-kernel@...r.kernel.org, Perry Taylor <perry.taylor@...el.com>, 
	Samantha Alt <samantha.alt@...el.com>, Caleb Biggers <caleb.biggers@...el.com>, 
	Mark Rutland <mark.rutland@....com>
Subject: Re: [RFC PATCH v4 04/15] find_bit: add _find_last_and_bit() to
 support finding the most significant set bit

On Thu, Feb 8, 2024 at 7:14 PM <weilin.wang@...el.com> wrote:
>
> From: Weilin Wang <weilin.wang@...el.com>
>
> This function is required for more efficient PMU counter assignment.
>
> When we use bitmap to log available PMU counters and counters that support a
> given event, we want to find a most significant set bit so that we could
> starting assigning counters with larger index first. This is helpful
> because counters with smaller indexes usually are more generic and
> support more events.
>
> Signed-off-by: Weilin Wang <weilin.wang@...el.com>
> ---
>  tools/include/linux/find.h | 18 ++++++++++++++++++
>  tools/lib/find_bit.c       | 33 +++++++++++++++++++++++++++++++++
>  2 files changed, 51 insertions(+)
>
> diff --git a/tools/include/linux/find.h b/tools/include/linux/find.h
> index 38c0a542b0e2..fce336ec2b96 100644
> --- a/tools/include/linux/find.h
> +++ b/tools/include/linux/find.h
> @@ -18,6 +18,8 @@ extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long si
>  extern unsigned long _find_first_and_bit(const unsigned long *addr1,
>                                          const unsigned long *addr2, unsigned long size);
>  extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
> +extern unsigned long _find_last_and_bit(const unsigned long *addr1,
> +                                        const unsigned long *addr2, unsigned long size);
>
>  #ifndef find_next_bit
>  /**
> @@ -174,4 +176,20 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
>  }
>  #endif
>
> +#ifndef find_last_and_bit
> +static inline
> +unsigned long find_last_and_bit(const unsigned long *addr1,
> +                               const unsigned long *addr2,
> +                               unsigned long size)
> +{
> +       if (small_const_nbits(size)) {
> +               unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
> +
> +               return val ? __fls(val) : size;
> +       }
> +
> +       return _find_last_and_bit(addr1, addr2, size);
> +}
> +#endif
> +
>  #endif /*__LINUX_FIND_H_ */
> diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c
> index 6a3dc167d30e..e475a7368e36 100644
> --- a/tools/lib/find_bit.c
> +++ b/tools/lib/find_bit.c
> @@ -67,6 +67,27 @@ out:                                                                         \
>         sz;                                                                     \
>  })
>
> +/*
> + * Common helper for find_bit() function family
> + * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
> + * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
> + * @size: The bitmap size in bits
> + */
> +#define FIND_LAST_BIT(FETCH, MUNGE, size)                                      \
> +({                                                                             \
> +       unsigned long idx, val, sz = (size);                                    \
> +                                                                               \
> +       for (idx = ((size - 1) / BITS_PER_LONG); idx >= 0; idx--) {                     \
> +               val = (FETCH);                                                  \
> +               if (val) {                                                      \
> +                       sz = min(idx * BITS_PER_LONG + __fls(MUNGE(val)), sz);  \
> +                       break;                                                  \
> +               }                                                               \
> +       }                                                                       \
> +                                                                               \
> +       sz;                                                                     \
> +})
> +
>  #ifndef find_first_bit
>  /*
>   * Find the first set bit in a memory region.
> @@ -121,3 +142,15 @@ unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits
>         return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
>  }
>  #endif
> +
> +#ifndef find_last_and_bit
> +/*
> + * Find the last set bit in two memory regions.
> + */
> +unsigned long _find_last_and_bit(const unsigned long *addr1,
> +                                 const unsigned long *addr2,
> +                                 unsigned long size)
> +{
> +       return FIND_LAST_BIT(addr1[idx] & addr2[idx], /* nop */, size);

The "/* nop */" argument is weird but existing style.

Reviewed-by: Ian Rogers <irogers@...gle.com>

Thanks,
Ian

> +}
> +#endif
> \ No newline at end of file
> --
> 2.42.0
>