Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
And add le support about find_last_bit and find_last_zero_bit.
Signed-off-by: Levi Yun <[email protected]>
---
lib/find_bit.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 62 insertions(+), 2 deletions(-)
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 4a8751010d59..f9dda2bf7fa9 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -90,7 +90,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
EXPORT_SYMBOL(find_next_zero_bit);
#endif
-#if !defined(find_next_and_bit)
+#ifndef find_next_and_bit
unsigned long find_next_and_bit(const unsigned long *addr1,
const unsigned long *addr2, unsigned long size,
unsigned long offset)
@@ -141,7 +141,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
if (size) {
unsigned long val = BITMAP_LAST_WORD_MASK(size);
- unsigned long idx = (size-1) / BITS_PER_LONG;
+ unsigned long idx = (size - 1) / BITS_PER_LONG;
do {
val &= addr[idx];
@@ -156,6 +156,27 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
EXPORT_SYMBOL(find_last_bit);
#endif
+#ifndef find_last_zero_bit
+unsigned long find_last_zero_bit(const unsigned long *addr, unsigned long size)
+{
+ if (size) {
+ unsigned long val = BITMAP_LAST_WORD_MASK(size);
+ unsigned long idx = (size - 1) / BITS_PER_LONG;
+
+ do {
+ val &= ~addr[idx];
+ if (val)
+ return idx * BITS_PER_LONG + __fls(val);
+
+ val = ~0ul;
+ } while (idx--);
+ }
+
+ return size;
+}
+EXPORT_SYMBOL(find_last_zero_bit);
+#endif
+
#ifdef __BIG_ENDIAN
#ifndef find_next_zero_bit_le
@@ -176,6 +197,45 @@ unsigned long find_next_bit_le(const void *addr, unsigned
EXPORT_SYMBOL(find_next_bit_le);
#endif
+static unsigned long _find_last_bit_le(const unsigned long *addr,
+ unsigned long size, unsigned long invert)
+{
+ if (size) {
+ unsigned long val = BITMAP_LAST_WORD_MASK(size);
+ unsigned long tmp;
+ unsigned long idx = (size - 1) / BITS_PER_LONG;
+
+ val = swab(val);
+
+ do {
+ tmp = swab(addr[idx]);
+ tmp ^= invert;
+ val &= tmp;
+ if (val)
+ return idx * BITS_PER_LONG + __fls(val);
+
+ val = ~0ul;
+ } while (idx--);
+ }
+ return size;
+}
+
+#ifndef find_last_zero_bit_le
+unsigned long find_last_zero_bit_le(const unsigned void *addr, unsigned long size)
+{
+ return _find_last_bit_le(addr, size, ~0UL);
+}
+EXPORT_SYMBOL(find_last_zero_bit_le);
+#endif
+
+#ifdef find_last_bit_le
+unsigned long find_last_bit_le(const unsigned void *addr, unsigned long size)
+{
+ return _find_last_bit_le(addr, size, 0UL);
+}
+EXPORT_SYMBOL(find_last_bit_le);
+#endif
+
#endif /* __BIG_ENDIAN */
unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
--
2.27.0
On Sun, Dec 06, 2020 at 03:46:24PM +0900, Levi Yun wrote:
> Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
> And add le support about find_last_bit and find_last_zero_bit.
>
> Signed-off-by: Levi Yun <[email protected]>
> ---
> lib/find_bit.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++--
> 1 file changed, 62 insertions(+), 2 deletions(-)
>
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 4a8751010d59..f9dda2bf7fa9 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -90,7 +90,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
> EXPORT_SYMBOL(find_next_zero_bit);
> #endif
>
> -#if !defined(find_next_and_bit)
> +#ifndef find_next_and_bit
> unsigned long find_next_and_bit(const unsigned long *addr1,
> const unsigned long *addr2, unsigned long size,
> unsigned long offset)
> @@ -141,7 +141,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> {
> if (size) {
> unsigned long val = BITMAP_LAST_WORD_MASK(size);
> - unsigned long idx = (size-1) / BITS_PER_LONG;
> + unsigned long idx = (size - 1) / BITS_PER_LONG;
>
> do {
> val &= addr[idx];
This, and the change above this, are not related to this patch so you
might not want to include them.
Also, why is this patch series even needed? I don't see a justification
for it anywhere, only "what" this patch is, not "why".
thanks
greg k-h
> This, and the change above this, are not related to this patch so you
> might not want to include them.
>
> Also, why is this patch series even needed? I don't see a justification
> for it anywhere, only "what" this patch is, not "why".
A little part of codes are trying to find the last zero bit using
for_each_clear_bit.
For example in fs/btrfs/free-space-cache.c' s
steal_from_bitmap_to_front function
which I changed in the 8'th patch.
I think it has some overhead to find the last clear bit (it start to
find from 0 bit to specified index),
so I try to add the find_last_zero_bit function to improve this.
Maybe I have a lack explanation in the message.
Sorry to make noise.
Thanks.
Levi.
On Sun, Dec 6, 2020 at 5:31 PM Greg KH <[email protected]> wrote:
>
> On Sun, Dec 06, 2020 at 03:46:24PM +0900, Levi Yun wrote:
> > Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
> > And add le support about find_last_bit and find_last_zero_bit.
> >
> > Signed-off-by: Levi Yun <[email protected]>
> > ---
> > lib/find_bit.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++--
> > 1 file changed, 62 insertions(+), 2 deletions(-)
> >
> > diff --git a/lib/find_bit.c b/lib/find_bit.c
> > index 4a8751010d59..f9dda2bf7fa9 100644
> > --- a/lib/find_bit.c
> > +++ b/lib/find_bit.c
> > @@ -90,7 +90,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
> > EXPORT_SYMBOL(find_next_zero_bit);
> > #endif
> >
> > -#if !defined(find_next_and_bit)
> > +#ifndef find_next_and_bit
> > unsigned long find_next_and_bit(const unsigned long *addr1,
> > const unsigned long *addr2, unsigned long size,
> > unsigned long offset)
> > @@ -141,7 +141,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> > {
> > if (size) {
> > unsigned long val = BITMAP_LAST_WORD_MASK(size);
> > - unsigned long idx = (size-1) / BITS_PER_LONG;
> > + unsigned long idx = (size - 1) / BITS_PER_LONG;
> >
> > do {
> > val &= addr[idx];
>
> This, and the change above this, are not related to this patch so you
> might not want to include them.
>
> Also, why is this patch series even needed? I don't see a justification
> for it anywhere, only "what" this patch is, not "why".
>
> thanks
>
> greg k-h
Sorry, in 7'th patch (not 8th).
Thanks
Levi.
On Sun, Dec 6, 2020 at 5:31 PM Greg KH <[email protected]> wrote:
>
> On Sun, Dec 06, 2020 at 03:46:24PM +0900, Levi Yun wrote:
> > Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
> > And add le support about find_last_bit and find_last_zero_bit.
> >
> > Signed-off-by: Levi Yun <[email protected]>
> > ---
> > lib/find_bit.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++--
> > 1 file changed, 62 insertions(+), 2 deletions(-)
> >
> > diff --git a/lib/find_bit.c b/lib/find_bit.c
> > index 4a8751010d59..f9dda2bf7fa9 100644
> > --- a/lib/find_bit.c
> > +++ b/lib/find_bit.c
> > @@ -90,7 +90,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
> > EXPORT_SYMBOL(find_next_zero_bit);
> > #endif
> >
> > -#if !defined(find_next_and_bit)
> > +#ifndef find_next_and_bit
> > unsigned long find_next_and_bit(const unsigned long *addr1,
> > const unsigned long *addr2, unsigned long size,
> > unsigned long offset)
> > @@ -141,7 +141,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> > {
> > if (size) {
> > unsigned long val = BITMAP_LAST_WORD_MASK(size);
> > - unsigned long idx = (size-1) / BITS_PER_LONG;
> > + unsigned long idx = (size - 1) / BITS_PER_LONG;
> >
> > do {
> > val &= addr[idx];
>
> This, and the change above this, are not related to this patch so you
> might not want to include them.
>
> Also, why is this patch series even needed? I don't see a justification
> for it anywhere, only "what" this patch is, not "why".
>
> thanks
>
> greg k-h
> This, and the change above this, are not related to this patch so you
> might not want to include them.
> Also, why is this patch series even needed? I don't see a justification
> for it anywhere, only "what" this patch is, not "why".
I think the find_last_zero_bit will help to improve in
7th patch's change and It can be used in the future.
But if my thinking is bad.. Please let me know..
Thanks.
Levi.
On Sun, Dec 06, 2020 at 05:56:30PM +0900, Yun Levi wrote:
> > This, and the change above this, are not related to this patch so you
> > might not want to include them.
>
> > Also, why is this patch series even needed? I don't see a justification
> > for it anywhere, only "what" this patch is, not "why".
>
> I think the find_last_zero_bit will help to improve in
> 7th patch's change and It can be used in the future.
> But if my thinking is bad.. Please let me know..
You need to explain that in a 0/8 patch. But note that this seems like
a lot of work just for one tiny user, what is the real benifit here?
thanks,
greg k-h
On 6.12.20 г. 10:56 ч., Yun Levi wrote:
>> This, and the change above this, are not related to this patch so you
>> might not want to include them.
>
>> Also, why is this patch series even needed? I don't see a justification
>> for it anywhere, only "what" this patch is, not "why".
>
> I think the find_last_zero_bit will help to improve in
> 7th patch's change and It can be used in the future.
> But if my thinking is bad.. Please let me know..
>
> Thanks.
> Levi.
>
btrfs' free space cache v1 is going to be removed some time in the
future so introducing kernel-wide change just for its own sake is a bit
premature. Also do you have measurements showing it indeed improves
performances?
> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature.
Sorry, I don't know about this fact Thanks..
> Also do you have measurements showing it indeed improves
> performances?
I'm not test btrfs' free space cache directly, But I used find_bit_benchmark.c.
here is the result of find_bit_benchmark.
Start testing find_bit() with random-filled bitmap
[ +0.001874] find_next_bit: 816326 ns, 163323 iterations
[ +0.000822] find_next_zero_bit: 808977 ns, 164357 iterations
[ +0.000571] find_last_bit: 561444 ns, 163323 iterations
[ +0.000619] find_last_zero_bit: 609533 ns, 164357 iterations
[ +0.002043] find_first_bit: 2011390 ns, 16204
iterations
[ +0.000003] find_next_and_bit: 59 ns, 0 iterations
[ +0.000001]
Start testing find_bit() with sparse bitmap
[ +0.000068] find_next_bit: 34573 ns, 653 iterations
[ +0.001691] find_next_zero_bit: 1663556 ns, 327027 iterations
[ +0.000010] find_last_bit: 7864 ns, 653 iterations
[ +0.001235] find_last_zero_bit: 1216449 ns, 327027 iterations
[ +0.000664] find_first_bit: 653148 ns, 653 iterations
[ +0.000002] find_next_and_bit: 44 ns, 0 iterations
as this result, the find_last_zero_bit is a little fast, and logically,
because find_each_clear_bit is iterate till the specified index (i) times,
But find_last_zero_bit in that case call one time
(find_each_clear_bit call i times but find_last_zero_bit call only one time)
So, i think it has a slight improvement.
Thanks.
Levi.
On Sun, Dec 6, 2020 at 6:01 PM Nikolay Borisov <[email protected]> wrote:
>
>
>
> On 6.12.20 г. 10:56 ч., Yun Levi wrote:
> >> This, and the change above this, are not related to this patch so you
> >> might not want to include them.
> >
> >> Also, why is this patch series even needed? I don't see a justification
> >> for it anywhere, only "what" this patch is, not "why".
> >
> > I think the find_last_zero_bit will help to improve in
> > 7th patch's change and It can be used in the future.
> > But if my thinking is bad.. Please let me know..
> >
> > Thanks.
> > Levi.
> >
>
> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature. Also do you have measurements showing it indeed improves
> performances?
On Sun, Dec 06, 2020 at 03:46:24PM +0900, Levi Yun wrote:
> Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
> And add le support about find_last_bit and find_last_zero_bit.
Use `git format-patch ...` tool. When create a series, be sure you run it:
- with -v<n>, where <n> is a version number (makes sense from v2)
- with --thread (it will be properly formed in a thread)
- with --cover-letter (don't forget to file the patch 0/n message)
--
With Best Regards,
Andy Shevchenko
> Use `git format-patch ...` tool. When create a series, be sure you run it:
> - with -v<n>, where <n> is a version number (makes sense from v2)
> - with --thread (it will be properly formed in a thread)
> - with --cover-letter (don't forget to file the patch 0/n message)
Thanks for your advice. Then Should I submit this patch again>
On Tue, Dec 8, 2020 at 12:32 AM Andy Shevchenko
<[email protected]> wrote:
>
> On Sun, Dec 06, 2020 at 03:46:24PM +0900, Levi Yun wrote:
> > Inspired find_next_*_bit and find_last_bit, add find_last_zero_bit
> > And add le support about find_last_bit and find_last_zero_bit.
>
> Use `git format-patch ...` tool. When create a series, be sure you run it:
> - with -v<n>, where <n> is a version number (makes sense from v2)
> - with --thread (it will be properly formed in a thread)
> - with --cover-letter (don't forget to file the patch 0/n message)
>
> --
> With Best Regards,
> Andy Shevchenko
>
>
> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature
But, I think it's not quite a kernel-wide change just add the
correspondent function to find_last_bit.
So, if we add this feature, maybe some users will use it in near future.
As my fault, I sent this patch without cover in patch [0/8] to explain why
So, I will send this patch again to take some review...
Sorry to make a noise again and Thanks to advice.
On Sun, Dec 6, 2020 at 6:01 PM Nikolay Borisov <[email protected]> wrote:
>
>
>
> On 6.12.20 г. 10:56 ч., Yun Levi wrote:
> >> This, and the change above this, are not related to this patch so you
> >> might not want to include them.
> >
> >> Also, why is this patch series even needed? I don't see a justification
> >> for it anywhere, only "what" this patch is, not "why".
> >
> > I think the find_last_zero_bit will help to improve in
> > 7th patch's change and It can be used in the future.
> > But if my thinking is bad.. Please let me know..
> >
> > Thanks.
> > Levi.
> >
>
> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature. Also do you have measurements showing it indeed improves
> performances?