From: Yury Norov <yury.norov@gmail.com>
To: Yun Levi <ppbuk5246@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>,
dushistov@mail.ru, Arnd Bergmann <arnd@arndb.de>,
Andrew Morton <akpm@linux-foundation.org>,
"Gustavo A. R. Silva" <gustavo@embeddedor.com>,
William Breathitt Gray <vilhelm.gray@gmail.com>,
richard.weiyang@linux.alibaba.com, joseph.qi@linux.alibaba.com,
skalluru@marvell.com, Josh Poimboeuf <jpoimboe@redhat.com>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
linux-arch@vger.kernel.org,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Subject: Re:
Date: Wed, 2 Dec 2020 13:26:47 -0800 [thread overview]
Message-ID: <CAAH8bW-+XnNsd9p3xZ1utmyY24gaBa0ko4tngBii4T+2cMkcYg@mail.gmail.com> (raw)
In-Reply-To: <CAM7-yPRBPP6SFzdmwWF5Y99g+aWcp=OY9Uvp-5h1MSDPmsORNw@mail.gmail.com>
On Wed, Dec 2, 2020 at 10:22 AM Yun Levi <ppbuk5246@gmail.com> wrote:
>
> On Thu, Dec 3, 2020 at 2:26 AM Yury Norov <yury.norov@gmail.com> wrote:
>
> > Also look at lib/find_bit_benchmark.c
> Thanks. I'll see.
>
> > We need find_next_*_bit() because find_first_*_bit() can start searching only at word-aligned
> > bits. In the case of find_last_*_bit(), we can start at any bit. So, if my understanding is correct,
> > for the purpose of reverse traversing we can go with already existing find_last_bit(),
>
> Thank you. I haven't thought that way.
> But I think if we implement reverse traversing using find_last_bit(),
> we have a problem.
> Suppose the last bit 0, 1, 2, is set.
> If we start
> find_last_bit(bitmap, 3) ==> return 2;
> find_last_bit(bitmap, 2) ==> return 1;
> find_last_bit(bitmap, 1) ==> return 0;
> find_last_bit(bitmap, 0) ===> return 0? // here we couldn't
> distinguish size 0 input or 0 is set
If you traverse backward and reach bit #0, you're done. No need to continue.
>
> and the for_each traverse routine prevent above case by returning size
> (nbits) using find_next_bit.
> So, for compatibility and the same expected return value like next traversing,
> I think we need to find_prev_*_bit routine. if my understanding is correct.
>
>
> > I think this patch has some good catches. We definitely need to implement
> > find_last_zero_bit(), as it is used by fs/ufs, and their local implementation is not optimal.
> >
> > We also should consider adding reverse traversing macros based on find_last_*_bit(),
> > if there are proposed users.
>
> Not only this, I think 'steal_from_bitmap_to_front' can be improved
> using ffind_prev_zero_bit
> like
>
> diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
> index af0013d3df63..9debb9707390 100644
> --- a/fs/btrfs/free-space-cache.c
> +++ b/fs/btrfs/free-space-cache.c
> @@ -2372,7 +2372,6 @@ static bool steal_from_bitmap_to_front(struct
> btrfs_free_space_ctl *ctl,
> u64 bitmap_offset;
> unsigned long i;
> unsigned long j;
> - unsigned long prev_j;
> u64 bytes;
>
> bitmap_offset = offset_to_bitmap(ctl, info->offset);
> @@ -2388,20 +2387,15 @@ static bool steal_from_bitmap_to_front(struct
> btrfs_free_space_ctl *ctl,
> return false;
>
> i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
> - j = 0;
> - prev_j = (unsigned long)-1;
> - for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
> - if (j > i)
> - break;
> - prev_j = j;
> - }
> - if (prev_j == i)
> + j = find_prev_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
This one may be implemented with find_last_zero_bit() as well:
unsigned log j = find_last_zero_bit(bitmap, BITS_PER_BITMAP);
if (j <= i || j >= BITS_PER_BITMAP)
return false;
I believe the latter version is better because find_last_*_bit() is simpler in
implementation (and partially exists), has less parameters, and therefore
simpler for users, and doesn't introduce functionality duplication.
The only consideration I can imagine to advocate find_prev*() is the performance
advantage in the scenario when we know for sure that first N bits of
bitmap are all
set/clear, and we can bypass traversing that area. But again, in this
case we can pass the
bitmap address with the appropriate offset, and stay with find_last_*()
> +
> + if (j == i)
> return false;
>
> - if (prev_j == (unsigned long)-1)
> + if (j == BITS_PER_BITMAP)
> bytes = (i + 1) * ctl->unit;
> else
> - bytes = (i - prev_j) * ctl->unit;
> + bytes = (i - j) * ctl->unit;
>
> info->offset -= bytes;
> info->bytes += bytes;
>
> Thanks.
>
> HTH
> Levi.
next prev parent reply other threads:[~2020-12-02 21:27 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-12-02 1:10 [PATCH] lib/find_bit: Add find_prev_*_bit functions Yun Levi
2020-12-02 9:47 ` Andy Shevchenko
2020-12-02 10:04 ` Rasmus Villemoes
2020-12-02 11:50 ` Yun Levi
2020-12-02 12:06 ` Andy Shevchenko
[not found] ` <CAAH8bW-jUeFVU-0OrJzK-MuGgKJgZv38RZugEQzFRJHSXFRRDA@mail.gmail.com>
2020-12-02 17:37 ` Andy Shevchenko
2020-12-02 18:27 ` Yun Levi
2020-12-02 18:51 ` your mail Andy Shevchenko
2020-12-02 18:56 ` Andy Shevchenko
2020-12-02 23:16 ` Yun Levi
2020-12-02 18:22 ` Yun Levi
2020-12-02 21:26 ` Yury Norov [this message]
2020-12-02 22:51 ` Yun Levi
2020-12-03 1:23 ` Yun Levi
2020-12-03 8:33 ` Rasmus Villemoes
2020-12-03 9:47 ` Re: Yun Levi
2020-12-03 18:46 ` Re: Yury Norov
2020-12-03 18:52 ` Re: Willy Tarreau
2020-12-04 1:36 ` Re: Yun Levi
2020-12-04 18:14 ` Re: Yury Norov
2020-12-05 0:45 ` Re: Yun Levi
2020-12-05 11:10 ` Re: Rasmus Villemoes
2020-12-05 18:20 ` Re: Yury Norov
-- strict thread matches above, loose matches on Subject: below --
2018-01-24 19:54 Re: Amy Riddering
2017-11-13 14:55 Re: Amos Kalonzo
2017-02-23 15:09 Qin's Yanjun
2015-08-19 13:01 christain147
2014-12-01 13:02 Re: Quan Han
2012-10-06 23:15 (unknown), David Howells
2012-10-07 6:36 ` Geert Uytterhoeven
2012-10-11 9:57 ` Re: Will Deacon
2012-05-20 22:20 Re: Mr. Peter Wong
2011-05-23 9:11 Re: Young Chang
2010-02-25 12:08 chau chin
2009-04-27 14:42 arnd
2009-04-27 23:52 ` Greg Ungerer
2009-04-27 14:41 arnd
2009-04-27 14:50 ` Geert Uytterhoeven
2007-08-14 23:04 [PATCH 0/24] make atomic_read() behave consistently across all architectures Chris Snook
2007-08-15 6:49 ` Herbert Xu
2007-08-15 8:18 ` Heiko Carstens
2007-08-15 13:53 ` Stefan Richter
2007-08-15 14:35 ` Satyam Sharma
2007-08-15 14:52 ` Herbert Xu
2007-08-15 16:09 ` Stefan Richter
2007-08-15 16:27 ` Paul E. McKenney
2007-08-15 18:31 ` Segher Boessenkool
2007-08-15 18:57 ` Paul E. McKenney
2007-08-15 19:54 ` Satyam Sharma
2007-08-15 20:47 ` Segher Boessenkool
2007-08-16 0:36 ` Satyam Sharma
2007-08-16 1:38 ` Segher Boessenkool
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAAH8bW-+XnNsd9p3xZ1utmyY24gaBa0ko4tngBii4T+2cMkcYg@mail.gmail.com \
--to=yury.norov@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=arnd@arndb.de \
--cc=dushistov@mail.ru \
--cc=gustavo@embeddedor.com \
--cc=joseph.qi@linux.alibaba.com \
--cc=jpoimboe@redhat.com \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=ppbuk5246@gmail.com \
--cc=richard.weiyang@linux.alibaba.com \
--cc=skalluru@marvell.com \
--cc=vilhelm.gray@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).