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

[Ian Rogers]

On Thu, Feb 8, 2024 at 7:14 PM <weilin.wang@xxxxxxxxx> wrote:
>
> From: Weilin Wang <weilin.wang@xxxxxxxxx>
>
> 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@xxxxxxxxx>
> ---
>  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@xxxxxxxxxx>

Thanks,
Ian

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