答复: [PATCH v4 1/2] lib: bitmap: reduce the number of goto again in bitmap_find_next_zero_area_off()

[孙毅 (Yi Sun)]

> -----邮件原件-----
> 发件人: Yury Norov <yury.norov@xxxxxxxxx>
> 发送时间: 2026年6月9日 6:15
> 收件人: 孙毅 (Yi Sun) <Yi.Sun@xxxxxxxxxx>
> 抄送: yury.norov@xxxxxxxxx; mnazarewicz@xxxxxxxxx; akpm@linux-
> foundation.org; mina86@xxxxxxxxxx; akinobu.mita@xxxxxxxxx; linux-
> kernel@xxxxxxxxxxxxxxx
> 主题: Re: [PATCH v4 1/2] lib: bitmap: reduce the number of goto again in
> 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 Mon, Jun 01, 2026 at 05:42:33PM +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 "goto again" calls.
> >
> > Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
> > ---
> >  lib/bitmap.c | 10 +++++++---
> >  1 file changed, 7 insertions(+), 3 deletions(-)
> >
> > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > index b9bfa157e095..7d0fbcbe6973 100644
> > --- a/lib/bitmap.c
> > +++ b/lib/bitmap.c
> > @@ -432,7 +432,7 @@ unsigned long
> bitmap_find_next_zero_area_off(unsigned long *map,
> >                                            unsigned long align_mask,
> >                                            unsigned long align_offset)
> >  {
> > -     unsigned long index, end, i;
> > +     unsigned long index, end, i, index_bits_align, index_idx;
> >  again:
> 
> Can you make an extra step, and remove the 'goto again' completely
> with the more high-level for(), do-while() or similar?
> 
> >       index = find_next_zero_bit(map, size, start);
> >
> > @@ -442,8 +442,12 @@ unsigned long
> bitmap_find_next_zero_area_off(unsigned long *map,
> >       end = index + nr;
> >       if (end > size)
> >               return end;
> > -     i = find_next_bit(map, end, index);
> > -     if (i < end) {
> > +
> > +     index_bits_align = round_down(index, BITS_PER_LONG);
> > +     index_idx = index / BITS_PER_LONG;
> 
> Too many indexes here. Can you find some better, meaningful names?
> 
> > +
> > +     i = find_last_bit(map + index_idx, end - index_bits_align) + index_bits_align;
> > +     if (i > index && i < end) {
> >               start = i + 1;
> >               goto again;
> >       }
> 
> I spent a couple cycles trying to understand why it works better,
> comparing to find_next_bit(). The thing is that the distance between
> first set bit and the beginning of the area is greater than between
> the last bit and the beginning, so we make bigger steps traversing the
> butmap. Is that right? Can you add a step-by-step explanation in the
> commit message for both versions, for clarity?
That's right.

> 
> Still wondering why the 'last_bit' version is slower here. Looking at
> the find_bit_benchmark output, the 'last_bit' is generally faster than
> the 'next_bit'...
Performance test results on my hardware:
                    before  after   change  p-value
    dense           1211    688     -43.2%  8.3e-11
    sparse          13.3    13.4    0.8%    0.27
I am unable to reproduce the slowdown issue with sparse cases.

> 
> Thanks,
> Yury
> 
> > --
> > 2.34.1