答复: [PATCH v5 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()

[孙毅 (Yi Sun)]

> -----邮件原件-----
> 发件人: Yury Norov <yury.norov@xxxxxxxxx>
> 发送时间: 2026年6月18日 14:15
> 收件人: 孙毅 (Yi Sun) <Yi.Sun@xxxxxxxxxx>
> 抄送: yury.norov@xxxxxxxxx; mina86@xxxxxxxxxx; 279644543@xxxxxx;
> mnazarewicz@xxxxxxxxx; akpm@xxxxxxxxxxxxxxxxxxxx;
> akinobu.mita@xxxxxxxxx; linux-kernel@xxxxxxxxxxxxxxx; john.stultz@xxxxxxxxxx;
> tjmercier@xxxxxxxxxx; qiang.zhao@xxxxxxxxxxxxx; scottwood@xxxxxxxxxxxxx;
> benjamin.gaignard@xxxxxxxxxx; fvdl@xxxxxxxxxx; tglx@xxxxxxxxxx;
> andreas.herrmann@xxxxxxxxxxx; song@xxxxxxxxxx; hch@xxxxxx;
> sasha.levin@xxxxxxxxxx; minchan@xxxxxxxxxx
> 主题: Re: [PATCH v5 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()
> 
> 
> 注意: 这封邮件来自于外部。除非你确定邮件内容安全，否则不要点击任何链
> 接和附件。
> 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, Jun 18, 2026 at 09:52:52AM +0800, Yi Sun wrote:
> > Finding a contiguous free region in a highly fragmented
> > bitmap is not easy and may require many repeated attempts.
> > Therefore, find_next_bit(map, end, index) is not the optimal choice.
> > This is because there may be multiple scattered free regions
> > within the range [index, end) and none of them will meet the length
> > requirement of @nr.
> > Instead, it's sufficient to directly find the last bit within
> > the range [index, end), thus reducing unnecessary repeated calls.
> >
> > An example of a bitmap:
> > Bits 0-3:   cleared(4 bits)
> > Bits 4-5:   set    (2 bits)
> > Bits 6-8:   cleared(4 bits)
> > Bits 9-10:  set    (2 bits)
> > Bits 11-20: cleared(10 bits)
> >
> > The goal is to find a 10-bit free region.
> >
> > The old code logic is as follows:
> > find_next_zero_bit(start = 0, find bit 0) -> find_next_bit(find bit 4) ->
> > goto again ->
> > find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) ->
> > goto again ->
> > find_next_zero_bit(start = 10, find bit 11) -> success
> >
> > The new code logic is as follows:
> > find_next_zero_bit(start = 0, find bit 0) -> find_last_bit(find bit 9) ->
> > goto again ->
> > find_next_zero_bit(start = 10, find bit 11) -> success
> 
> In new logic there's no goto, right?

ok, I will make changes in v6.

> 
> > Performance test results on my hardware(use lib/find_bit_benchmark.c):
> >
> >               before  after   change  p-value
> > dense         1211    688     -43.2%  8.3e-11
> > sparse                13.3    13.4    0.8%    0.27
> >
> > Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
> > ---
> >  lib/bitmap.c | 35 +++++++++++++++++++++--------------
> >  1 file changed, 21 insertions(+), 14 deletions(-)
> >
> > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > index b9bfa157e095..a2c4bd22d875 100644
> > --- a/lib/bitmap.c
> > +++ b/lib/bitmap.c
> > @@ -432,22 +432,29 @@ unsigned long
> bitmap_find_next_zero_area_off(unsigned long *map,
> >                                            unsigned long align_mask,
> >                                            unsigned long align_offset)
> >  {
> > -     unsigned long index, end, i;
> > -again:
> > -     index = find_next_zero_bit(map, size, start);
> > -
> > -     /* Align allocation */
> > -     index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
> > -
> > -     end = index + nr;
> > -     if (end > size)
> > -             return end;
> > -     i = find_next_bit(map, end, index);
> > -     if (i < end) {
> > +     unsigned long find_idx, end, i, find_word_idx, find_word_off;
> > +
> > +     for (;;) {
> 
> "Infinite" loop is nothing better than the backward goto.
> Can you try this:
> 
>         unsigned long end, i, off;
> 
>         for_each_clear_bit_from(start, map, size) {
>                 start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
>                 end = start + nr;
>                 if (end > size)
>                         break;
> 
>                 off = round_down(start, BITS_PER_LONG);
>                 i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off;
>                 if (i >= end || i < start)
>                         return start;
> 
>                 start = i;
>         }
> 
>         return size;
> 
> If it works for you, let's move with the for_each() version.
> Can you test and add my Co-developed-by please?

ok, I will test and make changes in v6.

> 
> Thanks,
> Yury
> 
> > +             find_idx = find_next_zero_bit(map, size, start);
> > +
> > +             /* Align allocation */
> > +             find_idx = __ALIGN_MASK(find_idx + align_offset,
> > +                     align_mask) - align_offset;
> > +
> > +             end = find_idx + nr;
> > +             if (end > size)
> > +                     return end;
> > +
> > +             find_word_idx = find_idx / BITS_PER_LONG;
> > +             find_word_off = find_word_idx * BITS_PER_LONG;
> > +
> > +             i = find_last_bit(map + find_word_idx,
> > +                     end - find_word_off) + find_word_off;
> > +             if (i >= end || i < find_idx)
> > +                     return find_idx;
> > +
> >               start = i + 1;
> > -             goto again;
> >       }
> > -     return index;
> >  }
> >  EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
> >
> > --
> > 2.34.1