Received-SPF: pass (google.com: domain of linux-kernel+bounces-112580-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
Precedence: bulk
MIME-Version: 1.0
References: <20240209031441.943012-1-weilin.wang@intel.com> <20240209031441.943012-5-weilin.wang@intel.com>
In-Reply-To: <20240209031441.943012-5-weilin.wang@intel.com>
From: Ian Rogers <irogers@google.com>
Date: Sat, 23 Mar 2024 21:19:57 -0700
Message-ID: <CAP-5=fVUJayXeKwtCnSjoUrw0HMJJa00RYrMhm-stjUwxDyefQ@mail.gmail.com>
Subject: Re: [RFC PATCH v4 04/15] find_bit: add _find_last_and_bit() to
 support finding the most significant set bit
To: weilin.wang@intel.com
Cc: Kan Liang <kan.liang@linux.intel.com>, Namhyung Kim <namhyung@kernel.org>, 
	Arnaldo Carvalho de Melo <acme@kernel.org>, Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@redhat.com>, 
	Alexander Shishkin <alexander.shishkin@linux.intel.com>, Jiri Olsa <jolsa@kernel.org>, 
	Adrian Hunter <adrian.hunter@intel.com>, linux-perf-users@vger.kernel.org, 
	linux-kernel@vger.kernel.org, Perry Taylor <perry.taylor@intel.com>, 
	Samantha Alt <samantha.alt@intel.com>, Caleb Biggers <caleb.biggers@intel.com>, 
	Mark Rutland <mark.rutland@arm.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Thu, Feb 8, 2024 at 7:14=E2=80=AFPM <weilin.wang@intel.com> wrote:
>
> From: Weilin Wang <weilin.wang@intel.com>
>
> This function is required for more efficient PMU counter assignment.
>
> When we use bitmap to log available PMU counters and counters that suppor=
t 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@intel.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 lon=
g *addr, unsigned long si
>  extern unsigned long _find_first_and_bit(const unsigned long *addr1,
>                                          const unsigned long *addr2, unsi=
gned long size);
>  extern unsigned long _find_first_zero_bit(const unsigned long *addr, uns=
igned long size);
> +extern unsigned long _find_last_and_bit(const unsigned long *addr1,
> +                                        const unsigned long *addr2, unsi=
gned long size);
>
>  #ifndef find_next_bit
>  /**
> @@ -174,4 +176,20 @@ unsigned long find_first_zero_bit(const unsigned lon=
g *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 =3D *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 bi=
tmap(s)
> + * @MUNGE: The expression that post-processes a word containing found bi=
t (may be empty)
> + * @size: The bitmap size in bits
> + */
> +#define FIND_LAST_BIT(FETCH, MUNGE, size)                               =
       \
> +({                                                                      =
       \
> +       unsigned long idx, val, sz =3D (size);                           =
         \
> +                                                                        =
       \
> +       for (idx =3D ((size - 1) / BITS_PER_LONG); idx >=3D 0; idx--) {  =
                   \
> +               val =3D (FETCH);                                         =
         \
> +               if (val) {                                               =
       \
> +                       sz =3D 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 lon=
g *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@google.com>

Thanks,
Ian

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