[PATCH 1/6] FRV: Fix fls() to handle bit 31 being set correctly

[PATCH 1/6] FRV: Fix fls() to handle bit 31 being set correctly

[David Howells]

From: David Howells <dhowells@redhat.com>

Fix FRV fls() to handle bit 31 being set correctly (it should return 32 not 0).

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 include/asm-frv/bitops.h |   21 +++++++++++++++++----
 1 files changed, 17 insertions(+), 4 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 980ae1b..97fb746 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -161,16 +161,29 @@ #include <asm-generic/bitops/ffs.h>
 #include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/find.h>
 
-/*
- * fls: find last bit set.
+/**
+ * fls - find last bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as ffs:
+ * - return 32..1 to indicate bit 31..0 most significant bit set
+ * - return 0 to indicate no bits set
  */
 #define fls(x)						\
 ({							\
 	int bit;					\
 							\
-	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(x));	\
+	asm("	subcc	%1,gr0,gr0,icc0		\n"	\
+	    "	ckne	icc0,cc4		\n"	\
+	    "	cscan.p	%1,gr0,%0	,cc4,#1	\n"	\
+	    "	csub	%0,%0,%0	,cc4,#0	\n"	\
+	    "   csub    %2,%0,%0	,cc4,#1	\n"	\
+	    : "=&r"(bit)				\
+	    : "r"(x), "r"(32)				\
+	    : "icc0", "cc4"				\
+	    );						\
 							\
-	bit ? 33 - bit : bit;				\
+	bit;						\
 })
 
 #include <asm-generic/bitops/fls64.h>

[PATCH 2/6] FRV: Implement fls64()

[David Howells]

From: David Howells <dhowells@redhat.com>

Implement fls64() for FRV without recource to conditional jumps.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 include/asm-frv/bitops.h |   42 +++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 41 insertions(+), 1 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 97fb746..591eecc 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -186,7 +186,47 @@ ({							\
 	bit;						\
 })
 
-#include <asm-generic/bitops/fls64.h>
+/**
+ * fls64 - find last bit set in a 64-bit value
+ * @n: the value to search
+ *
+ * This is defined the same way as ffs:
+ * - return 64..1 to indicate bit 63..0 most significant bit set
+ * - return 0 to indicate no bits set
+ */
+static inline __attribute__((const))
+int fls64(u64 n)
+{
+	union {
+		u64 ll;
+		struct { u32 h, l; };
+	} _;
+	int bit, x, y;
+
+	_.ll = n;
+
+	asm("	subcc.p		%3,gr0,gr0,icc0		\n"
+	    "	subcc		%4,gr0,gr0,icc1		\n"
+	    "	ckne		icc0,cc4		\n"
+	    "	ckne		icc1,cc5		\n"
+	    "	norcr		cc4,cc5,cc6		\n"
+	    "	csub.p		%0,%0,%0	,cc6,1	\n"
+	    "	orcr		cc5,cc4,cc4		\n"
+	    "	andcr		cc4,cc5,cc4		\n"
+	    "	cscan.p		%3,gr0,%0	,cc4,0	\n"
+	    "   setlos		#64,%1			\n"
+	    "	cscan.p		%4,gr0,%0	,cc4,1	\n"
+	    "   setlos		#32,%2			\n"
+	    "	csub.p		%1,%0,%0	,cc4,0	\n"
+	    "	csub		%2,%0,%0	,cc4,1	\n"
+	    : "=&r"(bit), "=r"(x), "=r"(y)
+	    : "0r"(_.h), "r"(_.l)
+	    : "icc0", "icc1", "cc4", "cc5", "cc6"
+	    );
+	return bit;
+
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 

[PATCH 3/6] FRV: Optimise ffs()

[David Howells]

From: David Howells <dhowells@redhat.com>

Optimise ffs(x) by using fls(x & x - 1) which we optimise to use the SCAN
instruction.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 include/asm-frv/bitops.h |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 591eecc..1f70d47 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -157,8 +157,6 @@ (__builtin_constant_p(nr) ? \
  __constant_test_bit((nr),(addr)) : \
  __test_bit((nr),(addr)))
 
-#include <asm-generic/bitops/ffs.h>
-#include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/find.h>
 
 /**
@@ -227,6 +225,37 @@ int fls64(u64 n)
 
 }
 
+/**
+ * ffs - find first bit set
+ * @x: the word to search
+ *
+ * - return 32..1 to indicate bit 31..0 most least significant bit set
+ * - return 0 to indicate no bits set
+ */
+static inline __attribute__((const))
+int ffs(int x)
+{
+	/* Note: (x & -x) gives us a mask that is the least significant
+	 * (rightmost) 1-bit of the value in x.
+	 */
+	return fls(x & -x);
+}
+
+/**
+ * __ffs - find first bit set
+ * @x: the word to search
+ *
+ * - return 31..0 to indicate bit 31..0 most least significant bit set
+ * - if no bits are set in x, the result is undefined
+ */
+static inline __attribute__((const))
+int __ffs(unsigned long x)
+{
+	int bit;
+	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(x & -x));
+	return 31 - bit;
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 

[PATCH 4/6] Implement a general log2 facility in the kernel

[David Howells]

From: David Howells <dhowells@redhat.com>

This facility provides three entry points:

	log2()		Log base 2 of u32
	ll_log2()	Log base 2 of u64
	long_log2()	Log base 2 of unsigned long

These facilities can either be used inside functions on dynamic data:

	int do_something(long q)
	{
		...;
		y = log2(x)
		...;
	}

Or can be used to statically initialise global variables with constant values:

	unsigned n = log2(27);

When performing static initialisation, the compiler will report "error:
initializer element is not constant" if asked to take a log of zero or of
something not reducible to a constant.  They treat negative numbers as
unsigned.


When not dealing with a constant, they fall back to using fls() which permits
them to use arch-specific log calculation instructions - such as BSR on
x86/x86_64 or SCAN on FRV - if available.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 fs/ext2/super.c          |    2 -
 fs/ext3/super.c          |    2 -
 include/asm-frv/bitops.h |   44 +++++++++++
 include/linux/kernel.h   |    9 --
 include/linux/log2.h     |  179 ++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 224 insertions(+), 12 deletions(-)

diff --git a/fs/ext2/super.c b/fs/ext2/super.c
index 681dea8..a4573b6 100644
--- a/fs/ext2/super.c
+++ b/fs/ext2/super.c
@@ -548,8 +548,6 @@ static int ext2_check_descriptors (struc
 	return 1;
 }
 
-#define log2(n) ffz(~(n))
- 
 /*
  * Maximal file size.  There is a direct, and {,double-,triple-}indirect
  * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 813d589..af1424d 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -1294,8 +1294,6 @@ #endif
 	sb->s_flags = s_flags; /* Restore MS_RDONLY status */
 }
 
-#define log2(n) ffz(~(n))
-
 /*
  * Maximal file size.  There is a direct, and {,double-,triple-}indirect
  * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 1f70d47..41a5866 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -256,6 +256,50 @@ int __ffs(unsigned long x)
 	return 31 - bit;
 }
 
+/*
+ * special slimline version of fls() for calculating log2()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_LOG2
+static inline __attribute__((const))
+int __log2(u32 n)
+{
+	int bit;
+	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(n));
+	return 31 - bit;
+}
+
+/*
+ * special slimline version of fls64() for calculating ll_log2()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_LL_LOG2
+static inline __attribute__((const))
+int __ll_log2(u64 n)
+{
+	union {
+		u64 ll;
+		struct { u32 h, l; };
+	} _;
+	int bit, x, y;
+
+	_.ll = n;
+
+	asm("	subcc		%3,gr0,gr0,icc0		\n"
+	    "	ckeq		icc0,cc4		\n"
+	    "	cscan.p		%3,gr0,%0	,cc4,0	\n"
+	    "   setlos		#63,%1			\n"
+	    "	cscan.p		%4,gr0,%0	,cc4,1	\n"
+	    "   setlos		#31,%2			\n"
+	    "	csub.p		%1,%0,%0	,cc4,0	\n"
+	    "	csub		%2,%0,%0	,cc4,1	\n"
+	    : "=&r"(bit), "=r"(x), "=r"(y)
+	    : "0r"(_.h), "r"(_.l)
+	    : "icc0", "cc4"
+	    );
+	return bit;
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 851aa1b..e8c6c66 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -13,6 +13,7 @@ #include <linux/stddef.h>
 #include <linux/types.h>
 #include <linux/compiler.h>
 #include <linux/bitops.h>
+#include <linux/log2.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -154,14 +155,6 @@ #endif
 
 unsigned long int_sqrt(unsigned long);
 
-static inline int __attribute_pure__ long_log2(unsigned long x)
-{
-	int r = 0;
-	for (x >>= 1; x > 0; x >>= 1)
-		r++;
-	return r;
-}
-
 static inline unsigned long
 __attribute_const__ roundup_pow_of_two(unsigned long x)
 {
diff --git a/include/linux/log2.h b/include/linux/log2.h
new file mode 100644
index 0000000..9bef055
--- /dev/null
+++ b/include/linux/log2.h
@@ -0,0 +1,179 @@
+/* Log base 2 calculation
+ *
+ * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_LOG2_H
+#define _LINUX_LOG2_H
+
+#include <linux/types.h>
+#include <linux/bitops.h>
+
+/*
+ * deal with unrepresentable constant logarithms
+ */
+extern __attribute__((const, noreturn))
+int ____log2_NaN(void);
+
+/*
+ * non-constant log of base 2 calculation
+ * - the arch may override these in asm/bitops.h if they can be implemented
+ *   more efficiently than using fls() and fls64()
+ */
+#ifndef ARCH_HAS_LOG2
+static inline __attribute__((const))
+int __log2(u32 n)
+{
+	return fls(n) - 1;
+}
+#endif
+
+#ifndef ARCH_HAS_LL_LOG2
+static inline __attribute__((const))
+int __ll_log2(u64 n)
+{
+	return fls64(n) - 1;
+}
+#endif
+
+/*
+ * constant-capable 32-bit log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ */
+#define log2(n)					\
+(						\
+	__builtin_constant_p(n) ? (		\
+		n < 1 ? ____log2_NaN() :	\
+		n >= (1ULL << 31) ? 31 :	\
+		n >= (1ULL << 30) ? 30 :	\
+		n >= (1ULL << 29) ? 29 :	\
+		n >= (1ULL << 28) ? 28 :	\
+		n >= (1ULL << 27) ? 27 :	\
+		n >= (1ULL << 26) ? 26 :	\
+		n >= (1ULL << 25) ? 25 :	\
+		n >= (1ULL << 24) ? 24 :	\
+		n >= (1ULL << 23) ? 23 :	\
+		n >= (1ULL << 22) ? 22 :	\
+		n >= (1ULL << 21) ? 21 :	\
+		n >= (1ULL << 20) ? 20 :	\
+		n >= (1ULL << 19) ? 19 :	\
+		n >= (1ULL << 18) ? 18 :	\
+		n >= (1ULL << 17) ? 17 :	\
+		n >= (1ULL << 16) ? 16 :	\
+		n >= (1ULL << 15) ? 15 :	\
+		n >= (1ULL << 14) ? 14 :	\
+		n >= (1ULL << 13) ? 13 :	\
+		n >= (1ULL << 12) ? 12 :	\
+		n >= (1ULL << 11) ? 11 :	\
+		n >= (1ULL << 10) ? 10 :	\
+		n >= (1ULL <<  9) ?  9 :	\
+		n >= (1ULL <<  8) ?  8 :	\
+		n >= (1ULL <<  7) ?  7 :	\
+		n >= (1ULL <<  6) ?  6 :	\
+		n >= (1ULL <<  5) ?  5 :	\
+		n >= (1ULL <<  4) ?  4 :	\
+		n >= (1ULL <<  3) ?  3 :	\
+		n >= (1ULL <<  2) ?  2 :	\
+		n >= (1ULL <<  1) ?  1 :	\
+		n >= (1ULL <<  0) ?  0 :	\
+		____log2_NaN()			\
+				   ) :		\
+	__log2(n)				\
+ )
+
+/*
+ * constant-capable 64-bit log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ */
+#define ll_log2(n)				\
+(						\
+	__builtin_constant_p(n) ? (		\
+		n < 1 ? ____log2_NaN() :	\
+		n >= (1ULL << 63) ? 63 :	\
+		n >= (1ULL << 62) ? 62 :	\
+		n >= (1ULL << 61) ? 61 :	\
+		n >= (1ULL << 60) ? 60 :	\
+		n >= (1ULL << 59) ? 59 :	\
+		n >= (1ULL << 58) ? 58 :	\
+		n >= (1ULL << 57) ? 57 :	\
+		n >= (1ULL << 56) ? 56 :	\
+		n >= (1ULL << 55) ? 55 :	\
+		n >= (1ULL << 54) ? 54 :	\
+		n >= (1ULL << 53) ? 53 :	\
+		n >= (1ULL << 52) ? 52 :	\
+		n >= (1ULL << 51) ? 51 :	\
+		n >= (1ULL << 50) ? 50 :	\
+		n >= (1ULL << 49) ? 49 :	\
+		n >= (1ULL << 48) ? 48 :	\
+		n >= (1ULL << 47) ? 47 :	\
+		n >= (1ULL << 46) ? 46 :	\
+		n >= (1ULL << 45) ? 45 :	\
+		n >= (1ULL << 44) ? 44 :	\
+		n >= (1ULL << 43) ? 43 :	\
+		n >= (1ULL << 42) ? 42 :	\
+		n >= (1ULL << 41) ? 41 :	\
+		n >= (1ULL << 40) ? 40 :	\
+		n >= (1ULL << 39) ? 39 :	\
+		n >= (1ULL << 38) ? 38 :	\
+		n >= (1ULL << 37) ? 37 :	\
+		n >= (1ULL << 36) ? 36 :	\
+		n >= (1ULL << 35) ? 35 :	\
+		n >= (1ULL << 34) ? 34 :	\
+		n >= (1ULL << 33) ? 33 :	\
+		n >= (1ULL << 32) ? 32 :	\
+		n >= (1ULL << 31) ? 31 :	\
+		n >= (1ULL << 30) ? 30 :	\
+		n >= (1ULL << 29) ? 29 :	\
+		n >= (1ULL << 28) ? 28 :	\
+		n >= (1ULL << 27) ? 27 :	\
+		n >= (1ULL << 26) ? 26 :	\
+		n >= (1ULL << 25) ? 25 :	\
+		n >= (1ULL << 24) ? 24 :	\
+		n >= (1ULL << 23) ? 23 :	\
+		n >= (1ULL << 22) ? 22 :	\
+		n >= (1ULL << 21) ? 21 :	\
+		n >= (1ULL << 20) ? 20 :	\
+		n >= (1ULL << 19) ? 19 :	\
+		n >= (1ULL << 18) ? 18 :	\
+		n >= (1ULL << 17) ? 17 :	\
+		n >= (1ULL << 16) ? 16 :	\
+		n >= (1ULL << 15) ? 15 :	\
+		n >= (1ULL << 14) ? 14 :	\
+		n >= (1ULL << 13) ? 13 :	\
+		n >= (1ULL << 12) ? 12 :	\
+		n >= (1ULL << 11) ? 11 :	\
+		n >= (1ULL << 10) ? 10 :	\
+		n >= (1ULL <<  9) ?  9 :	\
+		n >= (1ULL <<  8) ?  8 :	\
+		n >= (1ULL <<  7) ?  7 :	\
+		n >= (1ULL <<  6) ?  6 :	\
+		n >= (1ULL <<  5) ?  5 :	\
+		n >= (1ULL <<  4) ?  4 :	\
+		n >= (1ULL <<  3) ?  3 :	\
+		n >= (1ULL <<  2) ?  2 :	\
+		n >= (1ULL <<  1) ?  1 :	\
+		n >= (1ULL <<  0) ?  0 :	\
+		____log2_NaN()			\
+				   ) :		\
+	__ll_log2(n)				\
+ )
+
+/*
+ * constant-capable unsigned long log of base 2 calculation
+ * - this can be used to initialise global variables from constant data
+ */
+#if BITS_PER_LONG == 32
+#define long_log2(n) log2(n)
+#else
+#define long_log2(n) ll_log2(n)
+#endif
+
+#endif /* _LINUX_LOG2_H */

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Luck, Tony]

On Wed, Sep 13, 2006 at 02:03:00PM +0100, David Howells wrote:
> From: David Howells <dhowells@redhat.com>
> 
> This facility provides three entry points:
> 
> 	log2()		Log base 2 of u32
> 	ll_log2()	Log base 2 of u64
> 	long_log2()	Log base 2 of unsigned long

The names are rather counter-intuitive. "ll" sounds like "long long", so
why does it opearte on *unsigned* 64-bit?  Ditto for "long_log2()".
Perhaps they should be log2_u32(), log2_u64(), etc.

Even better if someone can come up with the right pre-processor magic
using sizeof/typeof so that you could just use "log2(any type)"


-Tony

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[David Howells]

Luck, Tony <tony.luck@intel.com> wrote:

> > This facility provides three entry points:
> > 
> > 	log2()		Log base 2 of u32
> > 	ll_log2()	Log base 2 of u64
> > 	long_log2()	Log base 2 of unsigned long
> 
> The names are rather counter-intuitive. "ll" sounds like "long long", so
> why does it opearte on *unsigned* 64-bit?  Ditto for "long_log2()".
> Perhaps they should be log2_u32(), log2_u64(), etc.

Well, given that you can't represent a log of a negative number, I'm not sure
it matters.

Note that long_log2() already exists and is of arch-dependent size.

> Even better if someone can come up with the right pre-processor magic
> using sizeof/typeof so that you could just use "log2(any type)"

I then end up with 32 of these per usage if I pass in a definite 32-bit value:

	warning: comparison is always false due to limited range of data type

because of the:

		n >= (1ULL << 63) ? 63 :	\
		n >= (1ULL << 62) ? 62 :	\
		n >= (1ULL << 61) ? 61 :	\
	...

in ll_log2().

David

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Adrian Bunk]

On Wed, Sep 13, 2006 at 02:03:00PM +0100, David Howells wrote:
> From: David Howells <dhowells@redhat.com>
> 
> This facility provides three entry points:
> 
> 	log2()		Log base 2 of u32
>...

Considering that several arch maintainers have vetoed my patch to revert 
the -ffreestanding removal Andi sneaked in with his usual trick to hide 
generic patches as "x86_64 patch", such a usage of a libc function name 
with a signature different from the one defined in ISO/IEC 9899:1999 is 
a namespace violation that mustn't happen.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Matthew Wilcox]

On Wed, Sep 13, 2006 at 06:17:34PM +0200, Adrian Bunk wrote:
> On Wed, Sep 13, 2006 at 02:03:00PM +0100, David Howells wrote:
> > From: David Howells <dhowells@redhat.com>
> > 
> > This facility provides three entry points:
> > 
> > 	log2()		Log base 2 of u32
> >...
> 
> Considering that several arch maintainers have vetoed my patch to revert 
> the -ffreestanding removal Andi sneaked in with his usual trick to hide 
> generic patches as "x86_64 patch", such a usage of a libc function name 
> with a signature different from the one defined in ISO/IEC 9899:1999 is 
> a namespace violation that mustn't happen.

log2 is only defined if math.h gets included.  If we're including math.h
at any point in the kernel itself (excluding the bootloader and similar),
we're already screwed six ways from sunday.

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Russell King]

On Wed, Sep 13, 2006 at 10:31:36AM -0600, Matthew Wilcox wrote:
> On Wed, Sep 13, 2006 at 06:17:34PM +0200, Adrian Bunk wrote:
> > On Wed, Sep 13, 2006 at 02:03:00PM +0100, David Howells wrote:
> > > From: David Howells <dhowells@redhat.com>
> > > 
> > > This facility provides three entry points:
> > > 
> > > 	log2()		Log base 2 of u32
> > >...
> > 
> > Considering that several arch maintainers have vetoed my patch to revert 
> > the -ffreestanding removal Andi sneaked in with his usual trick to hide 
> > generic patches as "x86_64 patch", such a usage of a libc function name 
> > with a signature different from the one defined in ISO/IEC 9899:1999 is 
> > a namespace violation that mustn't happen.
> 
> log2 is only defined if math.h gets included.  If we're including math.h
> at any point in the kernel itself (excluding the bootloader and similar),
> we're already screwed six ways from sunday.

Adrian's point is that gcc without -ffreestanding may decide to implement
log2() itself by issuing the appropriate floating point instructions
rather than using a function call into a library to do this operation.

Therefore, re-using "log2()" is about as bad as re-using the "strcmp()"
name to implement a function which copies strings.

And, sure enough, try throwing this at a compiler:

int log2(int foo)
{
	return foo;
}

you get:

t.c:2: warning: conflicting types for built-in function 'log2'

but not if you use -ffreestanding.

Don't re-use C standard library identifiers (or use -ffreestanding.)

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[David Howells]

Russell King <rmk+lkml@arm.linux.org.uk> wrote:

> Therefore, re-using "log2()" is about as bad as re-using the "strcmp()"
> name to implement a function which copies strings.

I should probably use ilog2() then which would at least be consistent with the
powerpc arch.

> t.c:2: warning: conflicting types for built-in function 'log2'

Which, of course, I didn't see because I didn't define it as a function,
merely as a macro.

David

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Geert Uytterhoeven]

On Wed, 13 Sep 2006, David Howells wrote:
> Russell King <rmk+lkml@arm.linux.org.uk> wrote:
> 
> > Therefore, re-using "log2()" is about as bad as re-using the "strcmp()"
> > name to implement a function which copies strings.
> 
> I should probably use ilog2() then which would at least be consistent with the
> powerpc arch.
> 
> > t.c:2: warning: conflicting types for built-in function 'log2'

And apparently gcc < 4.0 doesn't give the warning.

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Russell King]

On Wed, Sep 13, 2006 at 08:38:59PM +0200, Geert Uytterhoeven wrote:
> On Wed, 13 Sep 2006, David Howells wrote:
> > Russell King <rmk+lkml@arm.linux.org.uk> wrote:
> > 
> > > Therefore, re-using "log2()" is about as bad as re-using the "strcmp()"
> > > name to implement a function which copies strings.
> > 
> > I should probably use ilog2() then which would at least be consistent with the
> > powerpc arch.
> > 
> > > t.c:2: warning: conflicting types for built-in function 'log2'
> 
> And apparently gcc < 4.0 doesn't give the warning.

Eh?  That's gcc 3.4.3 producing that warning.  It probably depends on
the target configuration.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH 4/6] Implement a general log2 facility in the kernel

[Geert Uytterhoeven]

On Wed, 13 Sep 2006, Russell King wrote:
> On Wed, Sep 13, 2006 at 08:38:59PM +0200, Geert Uytterhoeven wrote:
> > On Wed, 13 Sep 2006, David Howells wrote:
> > > Russell King <rmk+lkml@arm.linux.org.uk> wrote:
> > > 
> > > > Therefore, re-using "log2()" is about as bad as re-using the "strcmp()"
> > > > name to implement a function which copies strings.
> > > 
> > > I should probably use ilog2() then which would at least be consistent with the
> > > powerpc arch.
> > > 
> > > > t.c:2: warning: conflicting types for built-in function 'log2'
> > 
> > And apparently gcc < 4.0 doesn't give the warning.
> 
> Eh?  That's gcc 3.4.3 producing that warning.  It probably depends on
> the target configuration.

I have to admit I didn't try all versions. So < 4.0 was a guess, based on the
(Debian) versions I have installed on my laptop...

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

[PATCH 5/6] Alter get_order() so that it can make use of long_log2() on a constant

[David Howells]

From: David Howells <dhowells@redhat.com>

Alter get_order() so that it can make use of long_log2() on a constant to
produce a constant value, retaining the ability for an arch to override it in
the non-const case.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 include/asm-generic/page.h |   14 -------------
 include/linux/log2.h       |   46 ++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 44 insertions(+), 16 deletions(-)

diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
index a96b5d9..a7e374e 100644
--- a/include/asm-generic/page.h
+++ b/include/asm-generic/page.h
@@ -6,20 +6,6 @@ #ifndef __ASSEMBLY__
 
 #include <linux/compiler.h>
 
-/* Pure 2^n version of get_order */
-static __inline__ __attribute_const__ int get_order(unsigned long size)
-{
-	int order;
-
-	size = (size - 1) >> (PAGE_SHIFT - 1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
-}
-
 #endif	/* __ASSEMBLY__ */
 #endif	/* __KERNEL__ */
 
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 9bef055..a2f6858 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -1,4 +1,4 @@
-/* Log base 2 calculation
+/* Base 2 logarithm calculation stuff
  *
  * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
  * Written by David Howells (dhowells@redhat.com)
@@ -25,6 +25,7 @@ int ____log2_NaN(void);
  * non-constant log of base 2 calculation
  * - the arch may override these in asm/bitops.h if they can be implemented
  *   more efficiently than using fls() and fls64()
+ * - the arch is not required to handle n==0 if implementing the fallback
  */
 #ifndef ARCH_HAS_LOG2
 static inline __attribute__((const))
@@ -43,6 +44,36 @@ int __ll_log2(u64 n)
 #endif
 
 /*
+ * non-const pure 2^n version of get_order
+ * - the arch may override these in asm/bitops.h if they can be implemented
+ *   more efficiently than using the arch log2 routines
+ * - we use the non-const log2() instead if the arch has defined one suitable
+ */
+#ifndef ARCH_HAS_GET_ORDER
+static inline __attribute__((const))
+int __get_order(unsigned long size, int page_shift)
+{
+#if BITS_PER_LONG == 32 && defined(ARCH_HAS_LOG2)
+	int order = __log2(size) - page_shift;
+	return order >= 0 ? order : 0;
+#elif BITS_PER_LONG == 64 && defined(ARCH_HAS_LL_LOG2)
+	int order = __ll_log2(size) - page_shift;
+	return order >= 0 ? order : 0;
+#else
+	int order;
+
+	size = (size - 1) >> (page_shift - 1);
+	order = -1;
+	do {
+		size >>= 1;
+		order++;
+	} while (size);
+	return order;
+#endif
+}
+#endif
+
+/*
  * constant-capable 32-bit log of base 2 calculation
  * - this can be used to initialise global variables from constant data, hence
  *   the massive ternary operator construction
@@ -167,7 +198,7 @@ (						\
  )
 
 /*
- * constant-capable unsigned long log of base 2 calculation
+ * constant-capable log of base 2 calculation of unsigned long
  * - this can be used to initialise global variables from constant data
  */
 #if BITS_PER_LONG == 32
@@ -176,4 +207,15 @@ #else
 #define long_log2(n) ll_log2(n)
 #endif
 
+/*
+ * calculate allocation order based on the current page size
+ * - this can be used to initialise global variables from constant data
+ */
+#define get_order(n)							\
+(									\
+	__builtin_constant_p(n) ?					\
+	((n < (1UL << PAGE_SHIFT)) ? 0 : long_log2(n) - PAGE_SHIFT) :	\
+	__get_order(n, PAGE_SHIFT)					\
+ )
+
 #endif /* _LINUX_LOG2_H */

[PATCH 6/6] Alter roundup_pow_of_two() so that it can make use of long_log2() on a constant

[David Howells]

From: David Howells <dhowells@redhat.com>

Alter roundup_pow_of_two() so that it can make use of long_log2() on a constant
to produce a constant value, retaining the ability for an arch to override it
in the non-const case.

This permits the function to be used to initialise variables.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 include/linux/kernel.h |    6 ------
 include/linux/log2.h   |   23 +++++++++++++++++++++++
 2 files changed, 23 insertions(+), 6 deletions(-)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index e8c6c66..e5947fb 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -155,12 +155,6 @@ #endif
 
 unsigned long int_sqrt(unsigned long);
 
-static inline unsigned long
-__attribute_const__ roundup_pow_of_two(unsigned long x)
-{
-	return 1UL << fls_long(x - 1);
-}
-
 extern int printk_ratelimit(void);
 extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);
 
diff --git a/include/linux/log2.h b/include/linux/log2.h
index a2f6858..2b55af0 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -74,6 +74,15 @@ #endif
 #endif
 
 /*
+ * round up to nearest power of two
+ */
+static inline __attribute__((const))
+unsigned long __roundup_pow_of_two(unsigned long n)
+{
+	return 1UL << fls_long(n - 1);
+}
+
+/*
  * constant-capable 32-bit log of base 2 calculation
  * - this can be used to initialise global variables from constant data, hence
  *   the massive ternary operator construction
@@ -218,4 +227,18 @@ (									\
 	__get_order(n, PAGE_SHIFT)					\
  )
 
+/*
+ * round up to nearest power of two
+ * - the result is undefined when n == 0
+ * - this can be used to initialise global variables from constant data
+ */
+#define roundup_pow_of_two(n)				\
+(							\
+	__builtin_constant_p(n) ? (			\
+		(n == 1) ? 0 :				\
+		(1UL << (long_log2((n) - 1) + 1))	\
+				   ) :			\
+	__roundup_pow_of_two(n)				\
+ )
+
 #endif /* _LINUX_LOG2_H */