* [PATCH 5/6] bitmap: find_last_bit()
@ 2008-12-01 8:18 Rusty Russell
2009-02-16 12:58 ` [PATCH] bitmap: Cleanup find_last_bit Benny Halevy
0 siblings, 1 reply; 4+ messages in thread
From: Rusty Russell @ 2008-12-01 8:18 UTC (permalink / raw)
To: linux-kernel; +Cc: Ingo Molnar, Mike Travis
Impact: New API
As the name suggests. For the moment everyone uses the generic one.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
include/linux/bitops.h | 13 ++++++++++++-
lib/Kconfig | 4 ++++
lib/Makefile | 1 +
lib/find_next_bit.c | 31 +++++++++++++++++++++++++++++++
4 files changed, 48 insertions(+), 1 deletion(-)
diff -r 22df8a8dec81 include/linux/bitops.h
--- a/include/linux/bitops.h Sat Oct 18 04:46:13 2008 +1100
+++ b/include/linux/bitops.h Tue Oct 21 17:06:35 2008 +1100
@@ -134,8 +134,19 @@ extern unsigned long find_first_bit(cons
*/
extern unsigned long find_first_zero_bit(const unsigned long *addr,
unsigned long size);
+#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
-#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
+#ifdef CONFIG_GENERIC_FIND_LAST_BIT
+/**
+ * find_last_bit - find the last set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum size to search
+ *
+ * Returns the bit number of the first set bit, or size.
+ */
+extern unsigned long find_last_bit(const unsigned long *addr,
+ unsigned long size);
+#endif /* CONFIG_GENERIC_FIND_LAST_BIT */
#ifdef CONFIG_GENERIC_FIND_NEXT_BIT
diff -r 22df8a8dec81 lib/Kconfig
--- a/lib/Kconfig Sat Oct 18 04:46:13 2008 +1100
+++ b/lib/Kconfig Tue Oct 21 17:06:35 2008 +1100
@@ -12,6 +12,10 @@ config GENERIC_FIND_FIRST_BIT
config GENERIC_FIND_NEXT_BIT
bool
+
+config GENERIC_FIND_LAST_BIT
+ bool
+ default y
config CRC_CCITT
tristate "CRC-CCITT functions"
diff -r 22df8a8dec81 lib/Makefile
--- a/lib/Makefile Sat Oct 18 04:46:13 2008 +1100
+++ b/lib/Makefile Tue Oct 21 17:06:35 2008 +1100
@@ -37,6 +37,7 @@ lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) +=
lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o
lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
+lib-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_next_bit.o
obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
obj-$(CONFIG_PLIST) += plist.o
diff -r 22df8a8dec81 lib/find_next_bit.c
--- a/lib/find_next_bit.c Sat Oct 18 04:46:13 2008 +1100
+++ b/lib/find_next_bit.c Tue Oct 21 17:06:35 2008 +1100
@@ -159,6 +159,37 @@ EXPORT_SYMBOL(find_first_zero_bit);
EXPORT_SYMBOL(find_first_zero_bit);
#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
+#ifdef CONFIG_GENERIC_FIND_LAST_BIT
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+{
+ unsigned long words;
+ unsigned long tmp;
+
+ /* Start at final word. */
+ words = size / BITS_PER_LONG;
+
+ /* Partial final word? */
+ if (size & (BITS_PER_LONG-1)) {
+ tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
+ - (size & (BITS_PER_LONG-1)))));
+ if (tmp)
+ goto found;
+ }
+
+ while (words) {
+ tmp = addr[--words];
+ if (tmp) {
+found:
+ return words * BITS_PER_LONG + __fls(tmp);
+ }
+ }
+
+ /* Not found */
+ return size;
+}
+EXPORT_SYMBOL(find_last_bit);
+#endif /* CONFIG_GENERIC_FIND_LAST_BIT */
+
#ifdef __BIG_ENDIAN
/* include/linux/byteorder does not support "unsigned long" type */
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH] bitmap: Cleanup find_last_bit
2008-12-01 8:18 [PATCH 5/6] bitmap: find_last_bit() Rusty Russell
@ 2009-02-16 12:58 ` Benny Halevy
2009-02-16 23:10 ` Rusty Russell
0 siblings, 1 reply; 4+ messages in thread
From: Benny Halevy @ 2009-02-16 12:58 UTC (permalink / raw)
To: Rusty Russell; +Cc: linux-kernel, Benny Halevy
Fix cut & paste error in header comment.
Simplify implementation a bit.
Signed-off-by: Benny Halevy <bhalevy@panasas.com>
---
Rusty, we're using a similar mechanism for finding the highest slot ID
in use in the nfsv4.1 slot table and I'm going to moev it over to
using find_last_bit in our 2.6.29 patchset.
While going over your implementation I noticed a tiny cut & paste error in
bitops.h and I'd also like to propose a couple simplifications to make
the implementation a bit more readable (at least to me :).
Benny
include/linux/bitops.h | 2 +-
lib/find_last_bit.c | 15 ++++++++-------
2 files changed, 9 insertions(+), 8 deletions(-)
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 6182913..886ebf0 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -142,7 +142,7 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
* @addr: The address to start the search at
* @size: The maximum size to search
*
- * Returns the bit number of the first set bit, or size.
+ * Returns the bit number of the last set bit, or size.
*/
extern unsigned long find_last_bit(const unsigned long *addr,
unsigned long size);
diff --git a/lib/find_last_bit.c b/lib/find_last_bit.c
index 5d202e3..e9d9cdc 100644
--- a/lib/find_last_bit.c
+++ b/lib/find_last_bit.c
@@ -24,22 +24,23 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
words = size / BITS_PER_LONG;
/* Partial final word? */
- if (size & (BITS_PER_LONG-1)) {
- tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
- - (size & (BITS_PER_LONG-1)))));
+ tmp = size & (BITS_PER_LONG-1);
+ if (tmp) {
+ tmp = addr[words] & (~0UL >> (BITS_PER_LONG - tmp));
if (tmp)
goto found;
}
while (words) {
tmp = addr[--words];
- if (tmp) {
-found:
- return words * BITS_PER_LONG + __fls(tmp);
- }
+ if (tmp)
+ goto found;
}
/* Not found */
return size;
+
+found:
+ return words * BITS_PER_LONG + __fls(tmp);
}
EXPORT_SYMBOL(find_last_bit);
--
1.6.1.3
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] bitmap: Cleanup find_last_bit
2009-02-16 12:58 ` [PATCH] bitmap: Cleanup find_last_bit Benny Halevy
@ 2009-02-16 23:10 ` Rusty Russell
2009-02-17 4:44 ` Benny Halevy
0 siblings, 1 reply; 4+ messages in thread
From: Rusty Russell @ 2009-02-16 23:10 UTC (permalink / raw)
To: Benny Halevy; +Cc: linux-kernel
On Monday 16 February 2009 23:28:40 Benny Halevy wrote:
> Fix cut & paste error in header comment.
> Simplify implementation a bit.
Hi Benny,
Nice catch! But I disagree with one change:
> /* Partial final word? */
> - if (size & (BITS_PER_LONG-1)) {
> - tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
> - - (size & (BITS_PER_LONG-1)))));
> + tmp = size & (BITS_PER_LONG-1);
> + if (tmp) {
> + tmp = addr[words] & (~0UL >> (BITS_PER_LONG - tmp));
> if (tmp)
> goto found;
> }
The overloading of tmp to the remainder size here is not really a cleanup: it
makes it into a dual-use var. I know it's called tmp, but that's a sign of
poor code too :)
I'd prefer a new final_bits var: gcc will almost certainly just slap it in
a register anyway, but it's clearer.
tmp could then be called something like... word?
Thanks!
Rusty.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] bitmap: Cleanup find_last_bit
2009-02-16 23:10 ` Rusty Russell
@ 2009-02-17 4:44 ` Benny Halevy
0 siblings, 0 replies; 4+ messages in thread
From: Benny Halevy @ 2009-02-17 4:44 UTC (permalink / raw)
To: Rusty Russell; +Cc: linux-kernel
On Feb. 17, 2009, 1:10 +0200, Rusty Russell <rusty@rustcorp.com.au> wrote:
> On Monday 16 February 2009 23:28:40 Benny Halevy wrote:
>> Fix cut & paste error in header comment.
>> Simplify implementation a bit.
>
> Hi Benny,
>
> Nice catch! But I disagree with one change:
>
>> /* Partial final word? */
>> - if (size & (BITS_PER_LONG-1)) {
>> - tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
>> - - (size & (BITS_PER_LONG-1)))));
>> + tmp = size & (BITS_PER_LONG-1);
>> + if (tmp) {
>> + tmp = addr[words] & (~0UL >> (BITS_PER_LONG - tmp));
>> if (tmp)
>> goto found;
>> }
>
> The overloading of tmp to the remainder size here is not really a cleanup: it
> makes it into a dual-use var. I know it's called tmp, but that's a sign of
> poor code too :)
>
> I'd prefer a new final_bits var: gcc will almost certainly just slap it in
> a register anyway, but it's clearer.
>
> tmp could then be called something like... word?
Yeah, I like that too.
I'm about to go on a flight
so the following was just tested to compile...
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 6182913..886ebf0 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -142,7 +142,7 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
* @addr: The address to start the search at
* @size: The maximum size to search
*
- * Returns the bit number of the first set bit, or size.
+ * Returns the bit number of the last set bit, or size.
*/
extern unsigned long find_last_bit(const unsigned long *addr,
unsigned long size);
diff --git a/lib/find_last_bit.c b/lib/find_last_bit.c
index 5d202e3..6a35783 100644
--- a/lib/find_last_bit.c
+++ b/lib/find_last_bit.c
@@ -17,29 +17,31 @@
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
+ unsigned long final_bits = size;
unsigned long words;
- unsigned long tmp;
+ unsigned long word;
/* Start at final word. */
- words = size / BITS_PER_LONG;
+ words = final_bits / BITS_PER_LONG;
/* Partial final word? */
- if (size & (BITS_PER_LONG-1)) {
- tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
- - (size & (BITS_PER_LONG-1)))));
- if (tmp)
+ size &= (BITS_PER_LONG-1);
+ if (size) {
+ word = addr[words] & (~0UL >> (BITS_PER_LONG - size));
+ if (word)
goto found;
}
while (words) {
- tmp = addr[--words];
- if (tmp) {
-found:
- return words * BITS_PER_LONG + __fls(tmp);
- }
+ word = addr[--words];
+ if (word)
+ goto found;
}
/* Not found */
- return size;
+ return final_bits;
+
+found:
+ return words * BITS_PER_LONG + __fls(word);
}
EXPORT_SYMBOL(find_last_bit);
--
1.6.1.3
>
> Thanks!
> Rusty.
^ permalink raw reply related [flat|nested] 4+ messages in thread
end of thread, other threads:[~2009-02-17 4:45 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-12-01 8:18 [PATCH 5/6] bitmap: find_last_bit() Rusty Russell
2009-02-16 12:58 ` [PATCH] bitmap: Cleanup find_last_bit Benny Halevy
2009-02-16 23:10 ` Rusty Russell
2009-02-17 4:44 ` Benny Halevy
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.