答复: [PATCH v3 1/2] lib: bitmap: add find_last_bit_from() and _find_last_bit_from()

[孙毅 (Yi Sun)]

> -----邮件原件-----
> 发件人: Yury Norov <ynorov@xxxxxxxxxx>
> 发送时间: 2026年5月15日 0:49
> 收件人: 孙毅 (Yi Sun) <Yi.Sun@xxxxxxxxxx>
> 抄送: yury.norov@xxxxxxxxx; mnazarewicz@xxxxxxxxx; akpm@linux-
> foundation.org; mina86@xxxxxxxxxx; akinobu.mita@xxxxxxxxx; linux-
> kernel@xxxxxxxxxxxxxxx
> 主题: Re: [PATCH v3 1/2] lib: bitmap: add find_last_bit_from() and
> _find_last_bit_from()
> 
> 
> 注意: 这封邮件来自于外部。除非你确定邮件内容安全，否则不要点击任何链
> 接和附件。
> CAUTION: This email originated from outside of the organization. Do not click links
> or open attachments unless you recognize the sender and know the content is
> safe.
> 
> 
> 
> On Thu, May 14, 2026 at 05:06:06PM +0800, Yi Sun wrote:
> > In some scenarios, it's not desirable to keep searching through the
> > beginning of the bitmap, but rather to search within a specific part.
> > The newly added function can accomplish this quickly.
> >
> > Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
> 
> On the previous round you said:
> 
>   find_last_bit_range() is only used here for now, but I believe it will be useful in
> the future.
> 
> And didn't let me answer by outdating that discussion with two new
> versions. Please don't do like that.
> 
> So my answer to the sentence above is: unless that bright future comes
> true, the find_last_bit_range() is unused, except for one in-house
> case. This makes it questionable if we really need the new exposed API
> at all...
> 
> There are 63 references of the find_last_bit(). Please inspect them all.
> If there will be another user, this question will be out of the table.
> 
> > ---
> >  include/linux/find.h | 33 +++++++++++++++++++++++++++++++++
> >  lib/find_bit.c       | 22 ++++++++++++++++++++++
> >  2 files changed, 55 insertions(+)
> >
> > diff --git a/include/linux/find.h b/include/linux/find.h
> > index 6c2be8ca615d..17f1db7b41fb 100644
> > --- a/include/linux/find.h
> > +++ b/include/linux/find.h
> > @@ -33,6 +33,8 @@ unsigned long _find_first_and_and_bit(const unsigned
> long *addr1, const unsigned
> >                                     const unsigned long *addr3, unsigned long size);
> >  extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned
> long size);
> >  extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long
> size);
> > +extern unsigned long _find_last_bit_from(const unsigned long *addr, unsigned
> long size,
> > +                                     unsigned long offset);
> >
> >  #ifdef __BIG_ENDIAN
> >  unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long
> size);
> > @@ -413,6 +415,37 @@ unsigned long find_last_bit(const unsigned long *addr,
> unsigned long size)
> >  }
> >  #endif
> >
> > +/**
> > + * find_last_bit_from - find the last set bit in a memory region
> > + * @addr: The address to base the search on
> > + * @size: The bitmap size in bits
> > + * @offset: The bit number to start searching at
> > + *
> > + * Compared to the find_last_bit(),
> > + * find_last_bit_from() has an additional parameter @offset,
> > + * so it can search within a specific range of the bitmap,
> > + * just like the find_next_bit().
> > + *
> > + * Returns the bit number of the last set bit, or size.
> > + */
> > +static __always_inline
> > +unsigned long find_last_bit_from(const unsigned long *addr, unsigned long
> size,
> > +                             unsigned long offset)
> > +{
> > +     if (small_const_nbits(size)) {
> > +             unsigned long val;
> > +
> > +             if (unlikely(offset >= size))
> > +                     return size;
> > +
> > +             val = *addr & GENMASK(size - 1, offset);
> > +
> > +             return val ? __fls(val) : size;
> > +     }
> > +
> > +     return _find_last_bit_from(addr, size, offset);
> > +}
> 
> On the previous round I suggested the implementation based on
> find_last_bit(), so that you don't need to create an outline
> _find_last_bit_from() function and expose it. Can you compare the
> implementations for the performance impact. If they are on par,
> I'd stick to one re-using the existing code.

Using the new API find_last_bit_from() is about 4% faster than using find_last_bit().
This is likely because find_last_bit() requires additional offset calculations.
as shown below:
index_bits_align = round_down(index, BITS_PER_LONG);
index_idx = index / BITS_PER_LONG;
i = find_last_bit(map + index_idx, end - index_bits_align) + index_bits_align;


So which approach do you prefer? Using the new API or not?
I will send patch v4 (including testing code) based on your suggestion.

> 
> Thanks,
> Yury
> 
> > +
> >  /**
> >   * find_next_and_bit_wrap - find the next set bit in both memory regions
> >   * @addr1: The first address to base the search on
> > diff --git a/lib/find_bit.c b/lib/find_bit.c
> > index 5ac52dfce730..196b946dafff 100644
> > --- a/lib/find_bit.c
> > +++ b/lib/find_bit.c
> > @@ -237,6 +237,28 @@ unsigned long _find_last_bit(const unsigned long
> *addr, unsigned long size)
> >  EXPORT_SYMBOL(_find_last_bit);
> >  #endif
> >
> > +unsigned long _find_last_bit_from(const unsigned long *addr, unsigned long
> size,
> > +                             unsigned long offset)
> > +{
> > +     unsigned long val, idx, start_idx;
> > +
> > +     if (unlikely(offset >= size))
> > +             return size;
> > +
> > +     start_idx = offset / BITS_PER_LONG;
> > +     idx = (size - 1) / BITS_PER_LONG;
> > +     val = addr[idx] & BITMAP_LAST_WORD_MASK(size);
> > +
> > +     while (!val && idx > start_idx)
> > +             val = addr[--idx];
> > +
> > +     if (idx == start_idx)
> > +             val &= BITMAP_FIRST_WORD_MASK(offset);
> > +
> > +     return val ? idx * BITS_PER_LONG + __fls(val) : size;
> > +}
> > +EXPORT_SYMBOL(_find_last_bit_from);
> > +
> >  unsigned long find_next_clump8(unsigned long *clump, const unsigned long
> *addr,
> >                              unsigned long size, unsigned long offset)
> >  {
> > --
> > 2.34.1