lib/find_bit.c: Add find_last_zero_bit

PATCH In review Levi Yun 4 participants 11 messages Dec 6, 2020 – Dec 8, 2020

Subsystems (4)

Library code Btrfs file system Generic include/asm header files Bitmap API

lore

Share & tools

lore

Levi Yun

author

2020-12-06 06:47 UTC #0 lore raw

PATCH v2 1/8 lib/find_bit.c: Add find_last_zero_bit

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(-)

lib/find_bit.c +62 -2

index 4a8751010d59..f9dda2bf7fa9 100644
@@ -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,

Signature · 1 line

2.27.0

Greg KH

2020-12-06 08:32 UTC #1 lore raw

Quoted 22 lines · Levi Yun

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(-)

lib/find_bit.c +1 -1

index 4a8751010d59..f9dda2bf7fa9 100644
@@ -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)

lib/find_bit.c unsigned long find_last_bit(const unsigned long *addr, unsigned long size) · line 147

Quoted 8 lines

lib/find_bit.c +1 -1

@@ -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

Yun Levi

author

2020-12-06 08:40 UTC #2 lore raw

Quoted 5 lines

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.

Quoted 42 lines · Greg KH

Quoted 22 lines · Levi Yun
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(-)
lib/find_bit.c +1 -1
index 4a8751010d59..f9dda2bf7fa9 100644
@@ -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)
lib/find_bit.c unsigned long find_last_bit(const unsigned long *addr, unsigned long size) · line 147
Quoted 8 lines
lib/find_bit.c +1 -1
@@ -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

Yun Levi

author

2020-12-06 08:46 UTC #3 lore raw

In reply to Greg KH

Sorry, in 7'th patch (not 8th).

Thanks
Levi.

Quoted 42 lines · Greg KH

Quoted 22 lines · Levi Yun
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(-)
lib/find_bit.c +1 -1
index 4a8751010d59..f9dda2bf7fa9 100644
@@ -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)
lib/find_bit.c unsigned long find_last_bit(const unsigned long *addr, unsigned long size) · line 147
Quoted 8 lines
lib/find_bit.c +1 -1
@@ -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

Yun Levi

author

2020-12-06 08:57 UTC #4 lore raw

Quoted 5 lines

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.

Greg KH

2020-12-06 09:02 UTC #5 lore raw

Quoted 9 lines · Yun Levi

Quoted 5 lines
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

Nikolay Borisov

2020-12-06 09:02 UTC #6 lore raw

In reply to Yun Levi

Quoted 6 lines · Yun Levi

Quoted 5 lines
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".

Quoted 7 lines

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?

Yun Levi

author

2020-12-06 09:16 UTC #7 lore raw

Quoted 3 lines

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..

Quoted 2 lines

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.

Quoted 22 lines · Nikolay Borisov

Quoted 6 lines · Yun Levi
Quoted 5 lines
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".
Quoted 7 lines
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?

Yun Levi

author

2020-12-08 22:55 UTC #8 lore raw

In reply to Nikolay Borisov

Quoted 3 lines

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.

Quoted 22 lines · Nikolay Borisov

Quoted 6 lines · Yun Levi
Quoted 5 lines
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".
Quoted 7 lines
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?

Andy Shevchenko

2020-12-07 15:34 UTC #9 lore raw

In reply to Levi Yun

Quoted 2 lines · Levi Yun

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)

Signature · 2 lines

With Best Regards,
Andy Shevchenko

Yun Levi

author

2020-12-07 16:05 UTC #10 lore raw

Quoted 4 lines

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>

Quoted 15 lines · Andy Shevchenko

Quoted 2 lines · Levi Yun
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