find_next_bit return type

find_next_bit return type

[Andrew Morton]

Seems that several 64-bit architectures are returning longs from
find_next_bit(), find_next_zero_bit(), etc.  x86 returns an int.  wli sent
me a patch which does

	return min(NR_CPUS, find_first_bit(srcp->bits, nbits));

so these architectures now get a zillion warnings.

We should be consistent here.  Is there any reason why these functions
cannot return integers?

Re: find_next_bit return type

[Andrew Morton]

sparc64:


diff -puN arch/sparc64/lib/find_bit.c~sparc64-bitops-fix arch/sparc64/lib/find_bit.c
--- 25-sparc64/arch/sparc64/lib/find_bit.c~sparc64-bitops-fix	2004-07-31 21:25:14.421668712 -0700
+++ 25-sparc64-akpm/arch/sparc64/lib/find_bit.c	2004-07-31 21:25:20.872688008 -0700
@@ -6,11 +6,11 @@
  * @offset: The bitnumber to start searching at
  * @size: The maximum size to search
  */
-unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+int find_next_bit(const unsigned long *addr, unsigned long size,
 				unsigned long offset)
 {
 	const unsigned long *p = addr + (offset >> 6);
-	unsigned long result = offset & ~63UL;
+	int result = offset & ~63UL;
 	unsigned long tmp;
 
 	if (offset >= size)
@@ -50,14 +50,15 @@ found_middle:
  * on Linus's ALPHA routines, which are pretty portable BTW.
  */
 
-unsigned long find_next_zero_bit(unsigned long *addr, unsigned long size, unsigned long offset)
+int find_next_zero_bit(unsigned long *addr, unsigned long size,
+			unsigned long offset)
 {
 	unsigned long *p = addr + (offset >> 6);
-	unsigned long result = offset & ~63UL;
+	int result = offset & ~63;
 	unsigned long tmp;
 
 	if (offset >= size)
-		return size;
+		return (int)size;
 	size -= result;
 	offset &= 63UL;
 	if (offset) {
diff -puN include/asm-sparc64/bitops.h~sparc64-bitops-fix include/asm-sparc64/bitops.h
--- 25-sparc64/include/asm-sparc64/bitops.h~sparc64-bitops-fix	2004-07-31 21:25:14.422668560 -0700
+++ 25-sparc64-akpm/include/asm-sparc64/bitops.h	2004-07-31 21:25:14.426667952 -0700
@@ -204,8 +204,7 @@ static __inline__ unsigned int hweight8(
  * @offset: The bitnumber to start searching at
  * @size: The maximum size to search
  */
-extern unsigned long find_next_bit(const unsigned long *, unsigned long,
-					unsigned long);
+extern int find_next_bit(const unsigned long *, unsigned long, unsigned long);
 
 /**
  * find_first_bit - find the first set bit in a memory region
@@ -223,7 +222,7 @@ extern unsigned long find_next_bit(const
  * on Linus's ALPHA routines, which are pretty portable BTW.
  */
 
-extern unsigned long find_next_zero_bit(unsigned long *, unsigned long, unsigned long);
+extern int find_next_zero_bit(unsigned long *, unsigned long, unsigned long);
 
 #define find_first_zero_bit(addr, size) \
         find_next_zero_bit((addr), (size), 0)
_

Re: find_next_bit return type

[Andrew Morton]

x86_64:


diff -puN include/asm-x86_64/bitops.h~x86_64-bitops-fix include/asm-x86_64/bitops.h
--- 25/include/asm-x86_64/bitops.h~x86_64-bitops-fix	2004-07-31 22:30:52.417209120 -0700
+++ 25-akpm/include/asm-x86_64/bitops.h	2004-07-31 22:31:28.898663096 -0700
@@ -256,8 +256,8 @@ static __inline__ int variable_test_bit(
 
 extern long find_first_zero_bit(const unsigned long * addr, unsigned long size);
 extern long find_next_zero_bit (const unsigned long * addr, long size, long offset);
-extern long find_first_bit(const unsigned long * addr, unsigned long size);
-extern long find_next_bit(const unsigned long * addr, long size, long offset);
+extern int find_first_bit(const unsigned long * addr, unsigned long size);
+extern int find_next_bit(const unsigned long * addr, long size, long offset);
 
 /* 
  * Find string of zero bits in a bitmap. -1 when not found.
diff -puN arch/x86_64/lib/bitops.c~x86_64-bitops-fix arch/x86_64/lib/bitops.c
--- 25/arch/x86_64/lib/bitops.c~x86_64-bitops-fix	2004-07-31 22:31:41.598732392 -0700
+++ 25-akpm/arch/x86_64/lib/bitops.c	2004-07-31 22:32:12.100095480 -0700
@@ -93,7 +93,7 @@ __find_first_bit(const unsigned long * a
  * Returns the bit-number of the first set bit, not the number of the byte
  * containing a bit.
  */
-long find_first_bit(const unsigned long * addr, unsigned long size)
+int find_first_bit(const unsigned long * addr, unsigned long size)
 {
 	return __find_first_bit(addr,size);
 }
@@ -104,7 +104,7 @@ long find_first_bit(const unsigned long 
  * @offset: The bitnumber to start searching at
  * @size: The maximum size to search
  */
-long find_next_bit(const unsigned long * addr, long size, long offset)
+int find_next_bit(const unsigned long * addr, long size, long offset)
 {
 	const unsigned long * p = addr + (offset >> 6);
 	unsigned long set = 0, bit = offset & 63, res;
_

Re: find_next_bit return type

[Andrew Morton]

ppc64:


diff -puN arch/ppc64/kernel/bitops.c~ppc64-bitops-fix arch/ppc64/kernel/bitops.c
--- 25-power4/arch/ppc64/kernel/bitops.c~ppc64-bitops-fix	2004-07-31 21:35:30.042080184 -0700
+++ 25-power4-akpm/arch/ppc64/kernel/bitops.c	2004-07-31 21:36:30.381907136 -0700
@@ -7,15 +7,15 @@
 #include <asm/bitops.h>
 #include <asm/byteorder.h>
 
-unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+int find_next_zero_bit(const unsigned long *addr, unsigned long size,
 				 unsigned long offset)
 {
 	const unsigned long *p = addr + (offset >> 6);
-	unsigned long result = offset & ~63UL;
+	int result = offset & ~63;
 	unsigned long tmp;
 
 	if (offset >= size)
-		return size;
+		return (int)size;
 	size -= result;
 	offset &= 63UL;
 	if (offset) {
@@ -48,15 +48,15 @@ found_middle:
 
 EXPORT_SYMBOL(find_next_zero_bit);
 
-unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+int find_next_bit(const unsigned long *addr, unsigned long size,
 			    unsigned long offset)
 {
 	const unsigned long *p = addr + (offset >> 6);
-	unsigned long result = offset & ~63UL;
+	int result = offset & ~63;
 	unsigned long tmp;
 
 	if (offset >= size)
-		return size;
+		return (int)size;
 	size -= result;
 	offset &= 63UL;
 	if (offset) {
diff -puN include/asm-ppc64/bitops.h~ppc64-bitops-fix include/asm-ppc64/bitops.h
--- 25-power4/include/asm-ppc64/bitops.h~ppc64-bitops-fix	2004-07-31 21:35:30.059077600 -0700
+++ 25-power4-akpm/include/asm-ppc64/bitops.h	2004-07-31 21:36:49.259037376 -0700
@@ -288,11 +288,11 @@ static __inline__ int ffs(int x)
 #define hweight16(x) generic_hweight16(x)
 #define hweight8(x) generic_hweight8(x)
 
-extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long offset);
+extern int find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long offset);
 #define find_first_zero_bit(addr, size) \
 	find_next_zero_bit((addr), (size), 0)
 
-extern unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset);
+extern int find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset);
 #define find_first_bit(addr, size) \
 	find_next_bit((addr), (size), 0)
 
_

Re: find_next_bit return type

[David S. Miller]

It's kind of pukey that the size and offset passed in is
unsigned long yet the return type is 'int'.

Frankly, I think the 64-bit systems have the prototype correct
this time and x86 is what ought to be "fixed" :-)

Just think, it only takes a "4GB / 8" sized bitmap to
potentially overflow that int return value :)))

Come on Andrew, you had to cringe at least a smidgen when
making these diffs :)

Re: find_next_bit return type

[Andrew Morton]

"David S. Miller" <davem@redhat.com> wrote:
>
> 
> It's kind of pukey that the size and offset passed in is
> unsigned long yet the return type is 'int'.

`size' and `offset' should be unsigned ints.

> Frankly, I think the 64-bit systems have the prototype correct
> this time and x86 is what ought to be "fixed" :-)
> 
> Just think, it only takes a "4GB / 8" sized bitmap to
> potentially overflow that int return value :)))
> 
> Come on Andrew, you had to cringe at least a smidgen when
> making these diffs :)

Kind-of.  But it's also cringeworthy to go slinging 8-byte values around
when 4-byte values would suffice.  Is it not more efficient to use
integers?

Re: find_next_bit return type

[David S. Miller]

On Sun, 1 Aug 2004 00:02:13 -0700
Andrew Morton <akpm@osdl.org> wrote:

> Kind-of.  But it's also cringeworthy to go slinging 8-byte values around
> when 4-byte values would suffice.  Is it not more efficient to use
> integers?

They all go in registers, the same register that could hold the 4-byte
values too.  There is also no computational cost to doing 64-bit add
subtract and shift (ie. simple ALU's) compared to 32-bit ones.

The int return value is also evil on many 64-bit systems because
it's going to do all of the computations in the native largest natural
word size (64-bits) then chop it down and sign extent it to 'int' (32-bits)

On 32-bitters none of this prototype crap will matter, since both int
and long are 32-bit of course.

I'm not %100 against using unsigned int, it's just that I know it will
crap up the output code a bit for 64-bitters.

Re: find_next_bit return type

[William Lee Irwin III]

On Sat, Jul 31, 2004 at 11:24:34PM -0700, Andrew Morton wrote:
> Seems that several 64-bit architectures are returning longs from
> find_next_bit(), find_next_zero_bit(), etc.  x86 returns an int.  wli sent
> me a patch which does
> 	return min(NR_CPUS, find_first_bit(srcp->bits, nbits));
> so these architectures now get a zillion warnings.
> We should be consistent here.  Is there any reason why these functions
> cannot return integers?

Not in particular, no. I'd sort of like 64-bit arches to keep their
natural wordsize as the return value as davem pointed out sign
extensions, conversions, etc. are overheads there.

To address this without a negative impact on 64-bit architectures and
to have the least code impact possible, I'd recommend the following.

(sparc32 obviously doesn't care about this issue either way)


-- wli

Index: hotplug-2.6.8-rc2/include/linux/cpumask.h
===================================================================
--- hotplug-2.6.8-rc2.orig/include/linux/cpumask.h	2004-07-29 04:44:59.000000000 -0700
+++ hotplug-2.6.8-rc2/include/linux/cpumask.h	2004-08-01 04:32:56.572244384 -0700
@@ -207,13 +207,13 @@
 #define first_cpu(src) __first_cpu(&(src), NR_CPUS)
 static inline int __first_cpu(const cpumask_t *srcp, int nbits)
 {
-	return find_first_bit(srcp->bits, nbits);
+	return min_t(int, NR_CPUS, find_first_bit(srcp->bits, nbits));
 }
 
 #define next_cpu(n, src) __next_cpu((n), &(src), NR_CPUS)
 static inline int __next_cpu(int n, const cpumask_t *srcp, int nbits)
 {
-	return find_next_bit(srcp->bits, nbits, n+1);
+	return min_t(int, NR_CPUS, find_next_bit(srcp->bits, nbits, n+1));
 }
 
 #define cpumask_of_cpu(cpu)						\

Re: find_next_bit return type

[William Lee Irwin III]

On Sun, Aug 01, 2004 at 04:53:34AM -0700, William Lee Irwin III wrote:
> Not in particular, no. I'd sort of like 64-bit arches to keep their
> natural wordsize as the return value as davem pointed out sign
> extensions, conversions, etc. are overheads there.
> To address this without a negative impact on 64-bit architectures and
> to have the least code impact possible, I'd recommend the following.
> (sparc32 obviously doesn't care about this issue either way)

Paul Jackson wants the nbits thing to be respected, so as long as the
callers sensitive to the precise size can't be identified:


Index: hotplug-2.6.8-rc2/include/linux/cpumask.h
===================================================================
--- hotplug-2.6.8-rc2.orig/include/linux/cpumask.h	2004-07-29 04:44:59.000000000 -0700
+++ hotplug-2.6.8-rc2/include/linux/cpumask.h	2004-08-01 06:32:31.615472016 -0700
@@ -207,13 +207,13 @@
 #define first_cpu(src) __first_cpu(&(src), NR_CPUS)
 static inline int __first_cpu(const cpumask_t *srcp, int nbits)
 {
-	return find_first_bit(srcp->bits, nbits);
+	return min_t(int, nbits, find_first_bit(srcp->bits, nbits));
 }
 
 #define next_cpu(n, src) __next_cpu((n), &(src), NR_CPUS)
 static inline int __next_cpu(int n, const cpumask_t *srcp, int nbits)
 {
-	return find_next_bit(srcp->bits, nbits, n+1);
+	return min_t(int, nbits, find_next_bit(srcp->bits, nbits, n+1));
 }
 
 #define cpumask_of_cpu(cpu)						\

Re: find_next_bit return type

[James Bottomley]

On Sun, 2004-08-01 at 02:24, Andrew Morton wrote:
> 
> Seems that several 64-bit architectures are returning longs from
> find_next_bit(), find_next_zero_bit(), etc.  x86 returns an int.  wli sent
> me a patch which does
> 
> 	return min(NR_CPUS, find_first_bit(srcp->bits, nbits));
> 
> so these architectures now get a zillion warnings.
> 
> We should be consistent here.  Is there any reason why these functions
> cannot return integers?

This isn't just a prototype change, it would change the actual
implementation on big endian 64 bit machines.

The find_first_bit/find_next_bit macros work fine on LE because the
lowest bit is at the start of the bitmap.  on BE machines, the highest
bit is supposed to be there.  The result is that long bitmaps are
currently implemented LE in BE chunks (the chunk size being an unsigned
long).  If you change to an unsigned int, you reduce our chunk size, and
hence the actual layout of the bitmap, so we'd need to check there were
no unintended consequences of this.

Would it not be easier simply to change the prototype on x86?

James

Re: find_next_bit return type

[William Lee Irwin III]

On Sun, Aug 01, 2004 at 11:05:07AM -0400, James Bottomley wrote:
> This isn't just a prototype change, it would change the actual
> implementation on big endian 64 bit machines.
> The find_first_bit/find_next_bit macros work fine on LE because the
> lowest bit is at the start of the bitmap.  on BE machines, the highest
> bit is supposed to be there.  The result is that long bitmaps are
> currently implemented LE in BE chunks (the chunk size being an unsigned
> long).  If you change to an unsigned int, you reduce our chunk size, and
> hence the actual layout of the bitmap, so we'd need to check there were
> no unintended consequences of this.
> Would it not be easier simply to change the prototype on x86?

I would not be averse to this.

Re: find_next_bit return type

[Paul Mackerras]

James Bottomley writes:

> On Sun, 2004-08-01 at 02:24, Andrew Morton wrote:
> > 
> > Seems that several 64-bit architectures are returning longs from
> > find_next_bit(), find_next_zero_bit(), etc.  x86 returns an int.  wli sent
> > me a patch which does
> > 
> > 	return min(NR_CPUS, find_first_bit(srcp->bits, nbits));
> > 
> > so these architectures now get a zillion warnings.
> > 
> > We should be consistent here.  Is there any reason why these functions
> > cannot return integers?
> 
> This isn't just a prototype change, it would change the actual
> implementation on big endian 64 bit machines.
> 
> The find_first_bit/find_next_bit macros work fine on LE because the
> lowest bit is at the start of the bitmap.  on BE machines, the highest
> bit is supposed to be there.  The result is that long bitmaps are
> currently implemented LE in BE chunks (the chunk size being an unsigned
> long).  If you change to an unsigned int, you reduce our chunk size, and
> hence the actual layout of the bitmap, so we'd need to check there were
> no unintended consequences of this.

I think Andrew was talking about the return type, not the type of the
bitmap.  The return type could easily be an int or unsigned int, while
still having the bitmap as an array of unsigned longs (with unchanged
layout).

Paul.

Re: find_next_bit return type

[Andi Kleen]

On Sun, Aug 01, 2004 at 12:10:26AM -0700, David S. Miller wrote:
> On Sun, 1 Aug 2004 00:02:13 -0700
> Andrew Morton <akpm@osdl.org> wrote:
> 
> > Kind-of.  But it's also cringeworthy to go slinging 8-byte values around
> > when 4-byte values would suffice.  Is it not more efficient to use
> > integers?
> 
> They all go in registers, the same register that could hold the 4-byte
> values too.  There is also no computational cost to doing 64-bit add
> subtract and shift (ie. simple ALU's) compared to 32-bit ones.

Actually at least on Intel EM64T an 64bit sub/add is slower, so it's not
generally true. And 64bit ops generate bigger code on x86-64.

But I still agree with you David that returning long here is better.
Even though I consider it unlikely that anybody will search >4GB 
bitmaps in kernel any time soon (it would be a latency disaster).
But for the usual implementation (find_* subtracting two pointers) 
the function has to do a 64bit subtraction anyways, otherwise
you get a subtle "broken when crossing 4GB boundaries" bug. 
For consistency it is better to have long here.

-Andi