FRV: Fix fls() to handle bit 31 being set correctly
Subsystems (2)
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
@@ -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()
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
@@ -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()
In reply to David HowellsFrom: 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
@@ -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
In reply to David HowellsFrom: 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
@@ -548,8 +548,6 @@ static int ext2_check_descriptors (strucreturn 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
@@ -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
@@ -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 @@ #endifunsigned 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
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
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 longThe 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 belog2_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
Re: [PATCH 4/6] Implement a general log2 facility in the kernel
In reply to David HowellsQuoted 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 SeedRe: [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_64patch", 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
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_64patch", 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.hgets included. If we're includingmath.hat 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
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
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
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
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
PATCH 5/6 Alter get_order() so that it can make use of long_log2() on a constant
In reply to David HowellsFrom: 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
@@ -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
PATCH 6/6 Alter roundup_pow_of_two() so that it can make use of long_log2() on a constant
In reply to David HowellsFrom: 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
@@ -155,12 +155,6 @@ #endifunsigned 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
@@ -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 */