Skip to contentSkip to conversation

FRV: Fix fls() to handle bit 31 being set correctly

PATCH In review David Howells 6 participants 15 messages Sep 13, 2006

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

From: David Howells <[email protected]>

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

---

 include/asm-frv/bitops.h |   21 +++++++++++++++++----
 1 files changed, 17 insertions(+), 4 deletions(-)
include/asm-frv/bitops.h +17 -4
index 980ae1b..97fb746 100644
@@ -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>
#1 lore raw

PATCH 2/6 FRV: Implement fls64()

From: David Howells <[email protected]>

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

---

 include/asm-frv/bitops.h |   42 +++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 41 insertions(+), 1 deletions(-)
include/asm-frv/bitops.h +41 -1
index 97fb746..591eecc 100644
@@ -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>
 
#2 lore raw

PATCH 3/6 FRV: Optimise ffs()

In reply to David Howells

From: David Howells <[email protected]>

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

---

 include/asm-frv/bitops.h |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)
include/asm-frv/bitops.h +31 -2
index 591eecc..1f70d47 100644
@@ -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>
 
#3 lore raw

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

In reply to David Howells

From: David Howells <[email protected]>

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.

---

 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(-)
fs/ext2/super.c +0 -2
index 681dea8..a4573b6 100644
@@ -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.
fs/ext3/super.c +0 -2
index 813d589..af1424d 100644
@@ -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.
include/asm-frv/bitops.h +44 -0

50 lines not on this page · raw message

include/linux/kernel.h +1 -8
index 851aa1b..e8c6c66 100644
@@ -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)
 {
include/linux/log2.h new file +179 -0

179 lines not on this page · raw message

#4 lore raw

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

Quoted 7 lines · David Howells

From: David Howells <[email protected]>

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

#5 lore raw

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

Quoted 9 lines · Tony
Quoted 5 lines

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.

Quoted 2 lines

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

#6 lore raw

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

In reply to David Howells
Quoted 6 lines · David Howells

From: David Howells <[email protected]>

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

Signature · 4 lines
       "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
#7 lore raw

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

Quoted 5 lines · Adrian Bunk
Quoted 4 lines · David Howells

From: David Howells <[email protected]>

This facility provides three entry points:

Quoted 8 lines
Quoted 2 lines
	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.

#8 lore raw

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

Quoted 15 lines · Matthew Wilcox
Quoted 5 lines · Adrian Bunk
Quoted 4 lines · David Howells

From: David Howells <[email protected]>

This facility provides three entry points:

Quoted 8 lines
Quoted 2 lines
	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.

Quoted 3 lines

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

Signature · 3 lines
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core
#9 lore raw

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

Quoted 2 lines · Russell King

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.

Quoted 1 line

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

#10 lore raw

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

Quoted 9 lines · David Howells
Quoted 2 lines · Russell King

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.

Quoted 1 line

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 -- [email protected]

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

#11 lore raw

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

Quoted 6 lines · Geert Uytterhoeven
Quoted 5 lines · David Howells
Quoted 2 lines · Russell King

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

Quoted 6 lines
Quoted 4 lines

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

Quoted 1 line

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.

Signature · 3 lines
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core
#12 lore raw

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

Quoted 10 lines · Russell King
Quoted 9 lines · Geert Uytterhoeven
Quoted 8 lines · David Howells
Quoted 2 lines · Russell King

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.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line
Quoted 1 line

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 -- [email protected]

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

#13 lore raw

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

In reply to David Howells

From: David Howells <[email protected]>

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.

---

 include/asm-generic/page.h |   14 -------------
 include/linux/log2.h       |   46 ++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 44 insertions(+), 16 deletions(-)
include/asm-generic/page.h +0 -14
index a96b5d9..a7e374e 100644
@@ -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__ */
 
include/linux/log2.h +44 -2

71 lines not on this page · raw message

#14 lore raw

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

In reply to David Howells

From: David Howells <[email protected]>

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.

---

 include/linux/kernel.h |    6 ------
 include/linux/log2.h   |   23 +++++++++++++++++++++++
 2 files changed, 23 insertions(+), 6 deletions(-)
include/linux/kernel.h +0 -6
index e8c6c66..e5947fb 100644
@@ -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);
 
include/linux/log2.h +23 -0
index a2f6858..2b55af0 100644
@@ -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 */