[PATCH] Introduce ext4_find_next_bit

[PATCH] Introduce ext4_find_next_bit

[Aneesh Kumar K.V]

I would like feedback on the arm, m68k and s390. I haven't compile tested
this on these archs 

-aneesh



Introduce ext4_find_next_bit

From: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>

This gets used by the ext4 multi block allocator patches.

Also add generic_find_next_le_bit

Signed-off-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
Cc: <linux-ext4@vger.kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/asm-arm/bitops.h                     |    2 +
 include/asm-generic/bitops/ext2-non-atomic.h |    2 +
 include/asm-generic/bitops/le.h              |    4 ++
 include/asm-m68k/bitops.h                    |    2 +
 include/asm-m68knommu/bitops.h               |    2 +
 include/asm-powerpc/bitops.h                 |    4 ++
 include/asm-s390/bitops.h                    |    2 +
 include/linux/ext4_fs.h                      |    1 +
 lib/find_next_bit.c                          |   44 ++++++++++++++++++++++++++
 9 files changed, 63 insertions(+), 0 deletions(-)


diff --git a/include/asm-arm/bitops.h b/include/asm-arm/bitops.h
index 47a6b08..5c60bfc 100644
--- a/include/asm-arm/bitops.h
+++ b/include/asm-arm/bitops.h
@@ -310,6 +310,8 @@ static inline int constant_fls(int x)
 		_find_first_zero_bit_le(p,sz)
 #define ext2_find_next_zero_bit(p,sz,off)	\
 		_find_next_zero_bit_le(p,sz,off)
+#define ext2_find_next_bit(p, sz, off) \
+		_find_next_bit_le(p, sz, off)
 
 /*
  * Minix is defined to use little-endian byte ordering.
diff --git a/include/asm-generic/bitops/ext2-non-atomic.h b/include/asm-generic/bitops/ext2-non-atomic.h
index 1697404..63cf822 100644
--- a/include/asm-generic/bitops/ext2-non-atomic.h
+++ b/include/asm-generic/bitops/ext2-non-atomic.h
@@ -14,5 +14,7 @@
 	generic_find_first_zero_le_bit((unsigned long *)(addr), (size))
 #define ext2_find_next_zero_bit(addr, size, off) \
 	generic_find_next_zero_le_bit((unsigned long *)(addr), (size), (off))
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)(addr), (size), (off))
 
 #endif /* _ASM_GENERIC_BITOPS_EXT2_NON_ATOMIC_H_ */
diff --git a/include/asm-generic/bitops/le.h b/include/asm-generic/bitops/le.h
index b9c7e5d..80e3bf1 100644
--- a/include/asm-generic/bitops/le.h
+++ b/include/asm-generic/bitops/le.h
@@ -20,6 +20,8 @@
 #define generic___test_and_clear_le_bit(nr, addr) __test_and_clear_bit(nr, addr)
 
 #define generic_find_next_zero_le_bit(addr, size, offset) find_next_zero_bit(addr, size, offset)
+#define generic_find_next_le_bit(addr, size, offset) \
+			find_next_bit(addr, size, offset)
 
 #elif defined(__BIG_ENDIAN)
 
@@ -42,6 +44,8 @@
 
 extern unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 		unsigned long size, unsigned long offset);
+extern unsigned long generic_find_next_le_bit(const unsigned long *addr,
+		unsigned long size, unsigned long offset);
 
 #else
 #error "Please fix <asm/byteorder.h>"
diff --git a/include/asm-m68k/bitops.h b/include/asm-m68k/bitops.h
index 2976b5d..83d1f28 100644
--- a/include/asm-m68k/bitops.h
+++ b/include/asm-m68k/bitops.h
@@ -410,6 +410,8 @@ static inline int ext2_find_next_zero_bit(const void *vaddr, unsigned size,
 	res = ext2_find_first_zero_bit (p, size - 32 * (p - addr));
 	return (p - addr) * 32 + res;
 }
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)(addr), (size), (off))
 
 #endif /* __KERNEL__ */
 
diff --git a/include/asm-m68knommu/bitops.h b/include/asm-m68knommu/bitops.h
index f8dfb7b..f43afe1 100644
--- a/include/asm-m68knommu/bitops.h
+++ b/include/asm-m68knommu/bitops.h
@@ -294,6 +294,8 @@ found_middle:
 	return result + ffz(__swab32(tmp));
 }
 
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)(addr), (size), (off))
 #include <asm-generic/bitops/minix.h>
 
 #endif /* __KERNEL__ */
diff --git a/include/asm-powerpc/bitops.h b/include/asm-powerpc/bitops.h
index 733b4af..220d9a7 100644
--- a/include/asm-powerpc/bitops.h
+++ b/include/asm-powerpc/bitops.h
@@ -359,6 +359,8 @@ static __inline__ int test_le_bit(unsigned long nr,
 unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 				    unsigned long size, unsigned long offset);
 
+unsigned long generic_find_next_le_bit(const unsigned long *addr,
+				    unsigned long size, unsigned long offset);
 /* Bitmap functions for the ext2 filesystem */
 
 #define ext2_set_bit(nr,addr) \
@@ -378,6 +380,8 @@ unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 #define ext2_find_next_zero_bit(addr, size, off) \
 	generic_find_next_zero_le_bit((unsigned long*)addr, size, off)
 
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)addr, size, off)
 /* Bitmap functions for the minix filesystem.  */
 
 #define minix_test_and_set_bit(nr,addr) \
diff --git a/include/asm-s390/bitops.h b/include/asm-s390/bitops.h
index 34d9a63..dba6fec 100644
--- a/include/asm-s390/bitops.h
+++ b/include/asm-s390/bitops.h
@@ -772,6 +772,8 @@ static inline int sched_find_first_bit(unsigned long *b)
 	test_and_clear_bit((nr)^(__BITOPS_WORDSIZE - 8), (unsigned long *)addr)
 #define ext2_test_bit(nr, addr)      \
 	test_bit((nr)^(__BITOPS_WORDSIZE - 8), (unsigned long *)addr)
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)(addr), (size), (off))
 
 #ifndef __s390x__
 
diff --git a/include/linux/ext4_fs.h b/include/linux/ext4_fs.h
index e8b323e..daa5b26 100644
--- a/include/linux/ext4_fs.h
+++ b/include/linux/ext4_fs.h
@@ -493,6 +493,7 @@ do {									       \
 #define ext4_test_bit			ext2_test_bit
 #define ext4_find_first_zero_bit	ext2_find_first_zero_bit
 #define ext4_find_next_zero_bit		ext2_find_next_zero_bit
+#define ext4_find_next_bit		ext2_find_next_bit
 
 /*
  * Maximal mount counts between two filesystem checks
diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c
index bda0d71..0306c04 100644
--- a/lib/find_next_bit.c
+++ b/lib/find_next_bit.c
@@ -178,4 +178,48 @@ found_middle_swap:
 
 EXPORT_SYMBOL(generic_find_next_zero_le_bit);
 
+unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
+		long size, unsigned long offset)
+{
+	const unsigned long *p = addr + BITOP_WORD(offset);
+	unsigned long result = offset & ~(BITS_PER_LONG - 1);
+	unsigned long tmp;
+
+	if (offset >= size)
+		return size;
+	size -= result;
+	offset &= (BITS_PER_LONG - 1UL);
+	if (offset) {
+		tmp = ext2_swabp(p++);
+		tmp &= (~0UL << offset);
+		if (size < BITS_PER_LONG)
+			goto found_first;
+		if (tmp)
+			goto found_middle;
+		size -= BITS_PER_LONG;
+		result += BITS_PER_LONG;
+	}
+
+	while (size & ~(BITS_PER_LONG - 1)) {
+		tmp = *(p++);
+		if (tmp)
+			goto found_middle_swap;
+		result += BITS_PER_LONG;
+		size -= BITS_PER_LONG;
+	}
+	if (!size)
+		return result;
+	tmp = ext2_swabp(p);
+found_first:
+	tmp &= (~0UL >> (BITS_PER_LONG - size));
+	if (tmp == 0UL)		/* Are any bits set? */
+		return result + size; /* Nope. */
+found_middle:
+	return result + __ffs(tmp);
+
+found_middle_swap:
+	return result + __ffs(ext2_swab(tmp));
+}
+EXPORT_SYMBOL(generic_find_next_le_bit);
+
 #endif /* __BIG_ENDIAN */

[PATCH] Introduce ext4_find_next_bit

[Aneesh Kumar K.V]

Also add generic_find_next_le_bit

This gets used by the ext4 multi block allocator patches.

Signed-off-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
---
 include/asm-generic/bitops/ext2-non-atomic.h |    2 +
 include/asm-generic/bitops/le.h              |    4 ++
 include/asm-powerpc/bitops.h                 |    4 ++
 include/linux/ext4_fs.h                      |    1 +
 lib/find_next_bit.c                          |   44 ++++++++++++++++++++++++++
 5 files changed, 55 insertions(+), 0 deletions(-)

diff --git a/include/asm-generic/bitops/ext2-non-atomic.h b/include/asm-generic/bitops/ext2-non-atomic.h
index 1697404..63cf822 100644
--- a/include/asm-generic/bitops/ext2-non-atomic.h
+++ b/include/asm-generic/bitops/ext2-non-atomic.h
@@ -14,5 +14,7 @@
 	generic_find_first_zero_le_bit((unsigned long *)(addr), (size))
 #define ext2_find_next_zero_bit(addr, size, off) \
 	generic_find_next_zero_le_bit((unsigned long *)(addr), (size), (off))
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)(addr), (size), (off))
 
 #endif /* _ASM_GENERIC_BITOPS_EXT2_NON_ATOMIC_H_ */
diff --git a/include/asm-generic/bitops/le.h b/include/asm-generic/bitops/le.h
index b9c7e5d..80e3bf1 100644
--- a/include/asm-generic/bitops/le.h
+++ b/include/asm-generic/bitops/le.h
@@ -20,6 +20,8 @@
 #define generic___test_and_clear_le_bit(nr, addr) __test_and_clear_bit(nr, addr)
 
 #define generic_find_next_zero_le_bit(addr, size, offset) find_next_zero_bit(addr, size, offset)
+#define generic_find_next_le_bit(addr, size, offset) \
+			find_next_bit(addr, size, offset)
 
 #elif defined(__BIG_ENDIAN)
 
@@ -42,6 +44,8 @@
 
 extern unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 		unsigned long size, unsigned long offset);
+extern unsigned long generic_find_next_le_bit(const unsigned long *addr,
+		unsigned long size, unsigned long offset);
 
 #else
 #error "Please fix <asm/byteorder.h>"
diff --git a/include/asm-powerpc/bitops.h b/include/asm-powerpc/bitops.h
index 8144a27..60652a3 100644
--- a/include/asm-powerpc/bitops.h
+++ b/include/asm-powerpc/bitops.h
@@ -310,6 +310,8 @@ static __inline__ int test_le_bit(unsigned long nr,
 unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 				    unsigned long size, unsigned long offset);
 
+unsigned long generic_find_next_le_bit(const unsigned long *addr,
+				    unsigned long size, unsigned long offset);
 /* Bitmap functions for the ext2 filesystem */
 
 #define ext2_set_bit(nr,addr) \
@@ -329,6 +331,8 @@ unsigned long generic_find_next_zero_le_bit(const unsigned long *addr,
 #define ext2_find_next_zero_bit(addr, size, off) \
 	generic_find_next_zero_le_bit((unsigned long*)addr, size, off)
 
+#define ext2_find_next_bit(addr, size, off) \
+	generic_find_next_le_bit((unsigned long *)addr, size, off)
 /* Bitmap functions for the minix filesystem.  */
 
 #define minix_test_and_set_bit(nr,addr) \
diff --git a/include/linux/ext4_fs.h b/include/linux/ext4_fs.h
index cdee7aa..c7b9bb2 100644
--- a/include/linux/ext4_fs.h
+++ b/include/linux/ext4_fs.h
@@ -502,6 +502,7 @@ do {									       \
 #define ext4_test_bit			ext2_test_bit
 #define ext4_find_first_zero_bit	ext2_find_first_zero_bit
 #define ext4_find_next_zero_bit		ext2_find_next_zero_bit
+#define ext4_find_next_bit		ext2_find_next_bit
 
 /*
  * Maximal mount counts between two filesystem checks
diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c
index bda0d71..0306c04 100644
--- a/lib/find_next_bit.c
+++ b/lib/find_next_bit.c
@@ -178,4 +178,48 @@ found_middle_swap:
 
 EXPORT_SYMBOL(generic_find_next_zero_le_bit);
 
+unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
+		long size, unsigned long offset)
+{
+	const unsigned long *p = addr + BITOP_WORD(offset);
+	unsigned long result = offset & ~(BITS_PER_LONG - 1);
+	unsigned long tmp;
+
+	if (offset >= size)
+		return size;
+	size -= result;
+	offset &= (BITS_PER_LONG - 1UL);
+	if (offset) {
+		tmp = ext2_swabp(p++);
+		tmp &= (~0UL << offset);
+		if (size < BITS_PER_LONG)
+			goto found_first;
+		if (tmp)
+			goto found_middle;
+		size -= BITS_PER_LONG;
+		result += BITS_PER_LONG;
+	}
+
+	while (size & ~(BITS_PER_LONG - 1)) {
+		tmp = *(p++);
+		if (tmp)
+			goto found_middle_swap;
+		result += BITS_PER_LONG;
+		size -= BITS_PER_LONG;
+	}
+	if (!size)
+		return result;
+	tmp = ext2_swabp(p);
+found_first:
+	tmp &= (~0UL >> (BITS_PER_LONG - size));
+	if (tmp == 0UL)		/* Are any bits set? */
+		return result + size; /* Nope. */
+found_middle:
+	return result + __ffs(tmp);
+
+found_middle_swap:
+	return result + __ffs(ext2_swab(tmp));
+}
+EXPORT_SYMBOL(generic_find_next_le_bit);
+
 #endif /* __BIG_ENDIAN */
-- 
1.5.3.1.91.gd3392-dirty

Re: [PATCH] Introduce ext4_find_next_bit

[Balbir Singh]

Aneesh Kumar K.V wrote:
> Also add generic_find_next_le_bit
> 
> This gets used by the ext4 multi block allocator patches.
> 

Looks like it's a straight forward on Little Endian Architectures.
I see something for powerpc, what about other architectures?

> 
> +unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
> +		long size, unsigned long offset)
> +{

Docbook style comments on the function and arguments would be nice.

> +	const unsigned long *p = addr + BITOP_WORD(offset);
> +	unsigned long result = offset & ~(BITS_PER_LONG - 1);
> +	unsigned long tmp;
> +
> +	if (offset >= size)
> +		return size;
> +	size -= result;
> +	offset &= (BITS_PER_LONG - 1UL);
> +	if (offset) {
> +		tmp = ext2_swabp(p++);
> +		tmp &= (~0UL << offset);
> +		if (size < BITS_PER_LONG)
> +			goto found_first;
> +		if (tmp)
> +			goto found_middle;
> +		size -= BITS_PER_LONG;
> +		result += BITS_PER_LONG;
> +	}
> +
> +	while (size & ~(BITS_PER_LONG - 1)) {
> +		tmp = *(p++);
> +		if (tmp)
> +			goto found_middle_swap;
> +		result += BITS_PER_LONG;
> +		size -= BITS_PER_LONG;
> +	}
> +	if (!size)
> +		return result;
> +	tmp = ext2_swabp(p);
> +found_first:
> +	tmp &= (~0UL >> (BITS_PER_LONG - size));
> +	if (tmp == 0UL)		/* Are any bits set? */
> +		return result + size; /* Nope. */
> +found_middle:
> +	return result + __ffs(tmp);
> +
> +found_middle_swap:
> +	return result + __ffs(ext2_swab(tmp));
> +}
> +EXPORT_SYMBOL(generic_find_next_le_bit);
> +
>  #endif /* __BIG_ENDIAN */


-- 
	Warm Regards,
	Balbir Singh
	Linux Technology Center
	IBM, ISTL

Re: [PATCH] Introduce ext4_find_next_bit

[Aneesh Kumar K.V]

Balbir Singh wrote:
> Aneesh Kumar K.V wrote:
>> Also add generic_find_next_le_bit
>>
>> This gets used by the ext4 multi block allocator patches.
>>
> 
> Looks like it's a straight forward on Little Endian Architectures.
> I see something for powerpc, what about other architectures?
> 
>
All include/asm-<arch>/bitops.h except powerpc have 

#include <asm-generic/bitops/ext2-non-atomic.h>

and ext2-non-atomic.h have #include <asm-generic/bitops/le.h>


-aneesh

Re: [PATCH] Introduce ext4_find_next_bit

[Andrew Morton]

On Fri, 21 Sep 2007 10:55:05 +0530 "Aneesh Kumar K.V" <aneesh.kumar@linux.vnet.ibm.com> wrote:

> Also add generic_find_next_le_bit
> 
> This gets used by the ext4 multi block allocator patches.
> 

arm allmodconfig:

fs/ext4/mballoc.c: In function `ext4_mb_generate_buddy':
fs/ext4/mballoc.c:836: error: implicit declaration of function `ext2_find_next_bit'

This patch makes my head spin.

Why did we declare generic_find_next_le_bit() in
include/asm-powerpc/bitops.h (wrong) as well as in
include/asm-generic/bitops/le.h (presumably correct)?

Why is it touching a powerpc file and no any other architectures? 
Something screwed up in powerpc land?

And why did arm break?

Shudder.  Anyway, please fix, and if that fix requires that various
braindamaged be repaired, please repair the braindamage rather than going
along with it.

Thanks.

Re: [PATCH] Introduce ext4_find_next_bit

[Aneesh Kumar K.V]

Andrew Morton wrote:
> On Fri, 21 Sep 2007 10:55:05 +0530 "Aneesh Kumar K.V" <aneesh.kumar@linux.vnet.ibm.com> wrote:
> 
>> Also add generic_find_next_le_bit
>>
>> This gets used by the ext4 multi block allocator patches.
>>
> 
> arm allmodconfig:
> 
> fs/ext4/mballoc.c: In function `ext4_mb_generate_buddy':
> fs/ext4/mballoc.c:836: error: implicit declaration of function `ext2_find_next_bit'
> 
> This patch makes my head spin.
> 
> Why did we declare generic_find_next_le_bit() in
> include/asm-powerpc/bitops.h (wrong) as well as in
> include/asm-generic/bitops/le.h (presumably correct)?
> 

I was following the coding style used for rest of the APIs
like ext4_set_bit.


> Why is it touching a powerpc file and no any other architectures? 
> Something screwed up in powerpc land?
> 
> And why did arm break?

arm and below list of arch doesn't include the asm-generic/bitops/ext2-non-atomic.h 

I did a grep and that list the below architectures as also affected.
arm, m68k, m68knommu, s390

> 
> Shudder.  Anyway, please fix, and if that fix requires that various
> braindamaged be repaired, please repair the braindamage rather than going
> along with it.
> 
> 

That should be a separate patch altogether. I wanted to do the cleanup
along with the usages such as but never got time to do the same.

#define ocfs2_set_bit ext2_set_bit
#define udf_set_bit(nr,addr) ext2_set_bit(nr,addr)
direct usage in mb
md/bitmap.c +799
md/dm-log.c +177

I will send a patch tomorrow that fix  arm and other architectures. I guess the cleanup
can be a separate patch ? 

-aneesh

Re: [PATCH] Introduce ext4_find_next_bit

[Andrew Morton]

On Wed, 14 Nov 2007 00:41:03 +0530 "Aneesh Kumar K.V" <aneesh.kumar@linux.vnet.ibm.com> wrote:

> 
> 
> Andrew Morton wrote:
> > On Fri, 21 Sep 2007 10:55:05 +0530 "Aneesh Kumar K.V" <aneesh.kumar@linux.vnet.ibm.com> wrote:
> > 
> >> Also add generic_find_next_le_bit
> >>
> >> This gets used by the ext4 multi block allocator patches.
> >>
> > 
> > arm allmodconfig:
> > 
> > fs/ext4/mballoc.c: In function `ext4_mb_generate_buddy':
> > fs/ext4/mballoc.c:836: error: implicit declaration of function `ext2_find_next_bit'
> > 
> > This patch makes my head spin.
> > 
> > Why did we declare generic_find_next_le_bit() in
> > include/asm-powerpc/bitops.h (wrong) as well as in
> > include/asm-generic/bitops/le.h (presumably correct)?
> > 
> 
> I was following the coding style used for rest of the APIs
> like ext4_set_bit.

Well.  There's quite a bit of cruft in there.  If you do come across
something which isn't right, please do try to find the time to fix it up
first.

That might be non-trivial - powerpc does seem to have gone off on a strange
tangent there.

> 
> > Why is it touching a powerpc file and no any other architectures? 
> > Something screwed up in powerpc land?
> > 
> > And why did arm break?
> 
> arm and below list of arch doesn't include the asm-generic/bitops/ext2-non-atomic.h 
> 
> I did a grep and that list the below architectures as also affected.
> arm, m68k, m68knommu, s390
> 
> > 
> > Shudder.  Anyway, please fix, and if that fix requires that various
> > braindamaged be repaired, please repair the braindamage rather than going
> > along with it.
> > 
> > 
> 
> That should be a separate patch altogether. I wanted to do the cleanup
> along with the usages such as but never got time to do the same.
> 
> #define ocfs2_set_bit ext2_set_bit
> #define udf_set_bit(nr,addr) ext2_set_bit(nr,addr)
> direct usage in mb
> md/bitmap.c +799
> md/dm-log.c +177
> 
> I will send a patch tomorrow that fix  arm and other architectures. I guess the cleanup
> can be a separate patch ? 
> 

Yes, that's a separate work, thanks.