Skip to contentSkip to conversation

bitmap: find_last_bit()

PATCH In review Rusty Russell 2 participants 4 messages Dec 1, 2008 – Feb 17, 2009

Subsystems (2)
Library code Bitops API
lore
Share & tools
lore

Rusty Russell

author
#0 lore raw

PATCH 5/6 bitmap: find_last_bit()

Impact: New API

As the name suggests. For the moment everyone uses the generic one.

Signed-off-by Rusty Russell <[email protected]>
---
 include/linux/bitops.h |   13 ++++++++++++-
 lib/Kconfig            |    4 ++++
 lib/Makefile           |    1 +
 lib/find_next_bit.c    |   31 +++++++++++++++++++++++++++++++
 4 files changed, 48 insertions(+), 1 deletion(-)
include/linux/bitops.h +12 -1
diff -r 22df8a8dec81 include/linux/bitops.h
@@ -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
lib/Kconfig +4 -0
diff -r 22df8a8dec81 lib/Kconfig
@@ -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"
lib/Makefile +1 -0
diff -r 22df8a8dec81 lib/Makefile
@@ -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
lib/find_next_bit.c +31 -0
diff -r 22df8a8dec81 lib/find_next_bit.c
@@ -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 */
#1 lore raw

PATCH 1/1 bitmap: Cleanup find_last_bit

Fix cut & paste error in header comment.
Simplify implementation a bit.

Signed-off-by Benny Halevy <[email protected]>

---

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(-)
include/linux/bitops.h +1 -1
index 6182913..886ebf0 100644
@@ -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);
lib/find_last_bit.c +8 -7
index 5d202e3..e9d9cdc 100644
@@ -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);
Signature · 1 line
1.6.1.3
author
#2 lore raw

Re: [PATCH] bitmap: Cleanup find_last_bit

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

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

Quoted 10 lines
lib/find_last_bit.c +3 -3
 	/* 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.

#3 lore raw

Re: [PATCH] bitmap: Cleanup find_last_bit

Quoted 23 lines · Rusty Russell
Quoted 2 lines · 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:

Review

Quoted 10 lines
(quoted diff) +3 -3
 	/* 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 :)

Quoted 4 lines

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

include/linux/bitops.h +1 -1
index 6182913..886ebf0 100644
@@ -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);
lib/find_last_bit.c +14 -12
index 5d202e3..6a35783 100644
@@ -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);
Signature · 1 line
1.6.1.3
Quoted 3 lines

Thanks!
Rusty.