Fix get_order()
PATCH 1/1 Fix get_order()
From: David Howells <[email protected]>
Fix get_order() to use ilog2() properly.
---
include/asm-generic/page.h | 14 +++++++++++--- include/linux/log2.h | 20 ++++++++++++++++++-- 2 files changed, 29 insertions(+), 5 deletions(-)
include/asm-generic/page.h +11 -3
@@ -17,10 +17,18 @@ static inline __attribute__((const))int __get_order (unsigned long size,int page_shift) {#if BITS_PER_LONG ==32 && defined(ARCH_HAS_ILOG2_U32 ) -int order =__ilog2_u32 (size) - page_shift; +int order; +if (size <=1 ) + order =0 ; +else + order =__ilog2_u32 (size -1 ) +1 - page_shift;return order >=0 ? order :0 ;#elif BITS_PER_LONG ==64 && defined(ARCH_HAS_ILOG2_U64 ) -int order =__ilog2_u64 (size) - page_shift; +int order; +if (size <=1 ) + order =0 ; +else + order =__ilog2_u64 (size -1 ) +1 - page_shift;return order >=0 ? order :0 ;#else int order;
@@ -46,7 +54,7 @@ int __get_order(unsigned long size, int page_shift)#define get_order (n) \ ( \ __builtin_constant_p(n) ? \ - ((n < (1UL << PAGE_SHIFT)) ? 0 : ilog2(n) - PAGE_SHIFT) : \ + ((n < (1UL << PAGE_SHIFT)) ? 0 : ilog2_up(n) - PAGE_SHIFT) : \ __get_order(n, PAGE_SHIFT) \ )
include/linux/log2.h +18 -2
@@ -70,6 +70,8 @@ unsigned long __roundup_pow_of_two(unsigned long n)* constant-capable log of base 2 calculation * - this can be used to initialise global variables from constant data, hence * the massive ternary operator construction +* - the result is rounded down +* - the result is undefined when n < 1 * * selects the appropriately-sized optimised version depending on sizeof(n) */
@@ -149,6 +151,20 @@ unsigned long __roundup_pow_of_two(unsigned long n) )/** +* ilog2_up - rounded up log of base 2 of 32-bit or a 64-bit unsigned value +* @n - parameter +* +* constant-capable log of base 2 calculation +* - this can be used to initialise global variables from constant data, hence +* the massive ternary operator construction +* - the result is rounded up +* - the result is undefined when n < 1 +* +* selects the appropriately-sized optimised version depending on sizeof(n) +*/ +#define ilog2_up (n) ((n) == 1 ? 0 : ilog2((n) - 1) + 1) + +/** * roundup_pow_of_two - round the given value up to nearest power of two * @n - parameter *
@@ -159,8 +175,8 @@ unsigned long __roundup_pow_of_two(unsigned long n)#define roundup_pow_of_two (n) \ ( \ __builtin_constant_p(n) ? ( \ - (n == 1) ? 0 : \ - (1UL << (ilog2((n) - 1) + 1)) \ + (n == 1) ? 1 : \ + (1UL << ilog2_up(n)) \ ) : \ __roundup_pow_of_two(n) \ )
Quoted 16 lines · David Howells
From: David Howells <[email protected]>
Fix
get_order()to useilog2()properly.Signed-off-by David Howells <[email protected]>---
include/asm-generic/page.h | 14 +++++++++++--- include/linux/log2.h | 20 ++++++++++++++++++-- 2 files changed, 29 insertions(+), 5 deletions(-)include/asm-generic/page.h +0
-0
include/asm-generic/page.h static inline __attribute__((const)) · line 25
Quoted 10 lines
include/asm-generic/page.h +5
-1@@ -17,10 +17,18 @@ static inline __attribute__((const))int __get_order (unsigned long size,int page_shift) {#if BITS_PER_LONG ==32 && defined(ARCH_HAS_ILOG2_U32 ) -int order =__ilog2_u32 (size) - page_shift; +int order; +if (size <=1 ) + order =0 ; +else + order =__ilog2_u32 (size -1 ) +1 - page_shift;return order >=0 ? order :0 ;
This seems a lot more complex than it should be.
Assuming page_shift is usually constant, it would seem to make more sense to do:
if (size <= (1UL << page_shift)) return 0; else return __ilog2_u32(size-1)+1-page_shift;
... instead of having *two* conditionals...
-hpa
Quoted 4 lines · H. Peter Anvin
if (size <= (1UL << page_shift)) return 0; else return __ilog2_u32(size-1)+1-page_shift;
I think you're right. That'll also defend against the result of __ilog2_u32() being less than page_shift-1.
I think I can dispense with the page_shift argument. IIRC __get_order() was overridden by some arch, but isn't now.
David
include/linux/log2.h unsigned long __roundup_pow_of_two(unsigned long n) · line 181
Quoted 10 lines · David Howells
include/linux/log2.h +2
-2@@ -159,8 +175,8 @@ unsigned long __roundup_pow_of_two(unsigned long n)#define roundup_pow_of_two (n) \ ( \ __builtin_constant_p(n) ? ( \ - (n == 1) ? 0 : \ - (1UL << (ilog2((n) - 1) + 1)) \ + (n == 1) ? 1 : \ + (1UL << ilog2_up(n)) \ ) : \ __roundup_pow_of_two(n) \
That seems bogus. "n == 1" should give "0", no?
Linus
Quoted 1 line · Linus Torvalds
That seems bogus. "n == 1" should give "0", no?
Sigh. No. The comment header says it all:
/**
* roundup_pow_of_two - round the given value up to nearest power of two
* @n - parameter
*
* round the given value up to the nearest power of two
* - the result is undefined when n == 0
* - this can be used to initialise global variables from constant data */
Ie: round, say, 30 up to 32, not 5.
David
Quoted 5 lines · David Howells
/**
+ *ilog2_up- rounded up log of base 2 of 32-bit or a 64-bit unsigned value
+ * @n - parameter
+ *
+ * constant-capable log of base 2 calculation
Quoted 8 lines
+ * - this can be used to initialise global variables from constant data, hence
+ * the massive ternary operator construction
+ * - the result is rounded up
+ * - the result is undefined when n < 1
+ *
+ * selects the appropriately-sized optimised version depending on sizeof(n)
+ */
+#defineilog2_up(n)((n) == 1 ? 0 : ilog2((n) - 1) + 1)
This is wrong. It uses "n" twice, which makes it unsafe as a macro.
It would need to be an inline function, but then the global initializer comment is wrong.
Or it could use a "__builtin_constant_p()" (which gcc defines to not have side effects) to allow the multiple use for constant data.
Or we could require that "ilog2(0)" returns -1, and then we could just say
#define ilog2_up(n) (ilog2((n)-1)+1)
Or.. ?
The whole "get_order()" macro also has some serious lack of parenthesis. In general, commit 39d61db0edb34d60b83c5e0d62d0e906578cc707 just was pretty damn bad!
I'm becoming a bit disgruntled about this whole thing, I have to admit. I'm just not sure the bugs here are worth it. Especially considering that __get_order() has apparently never even tested these things to begin with, since nobody but FRV has ever #defined the ARCH_HAS_ILOG2_U?? macros.
The whole *reason* for that mess seems to be bogus too, since at least ia64 still has its own inline "get_order()", which means that nobody can use get_order() for constant initializers *anyway*, quite unlike the comments say.
So the whole thing is:
- buggy
- untested
- has untrue comments
- makes no real sense
and I'm inclined to just revert 39d61db0 instead of adding more and more breakage to it, since it's simply not going to help with the fundamental problems!
Linus
Quoted 3 lines · Linus Torvalds
Quoted 1 line
+#define
ilog2_up(n)((n) == 1 ? 0 : ilog2((n) - 1) + 1)This is wrong. It uses "n" twice, which makes it unsafe as a macro.
Damn. I missed that.
Quoted 2 lines
Or it could use a "
__builtin_constant_p()" (which gcc defines to not have side effects) to allow the multiple use for constant data.
I should have, yes.
Quoted 3 lines
Or we could require that "ilog2(0)" returns -1, and then we could just say
#define ilog2_up(n) (ilog2((n)-1)+1)
I'd rather not do that as the inline assembly variants then have to special case ilog2(0) rather than just having an undefined result.
Quoted 3 lines
The whole "
get_order()" macro also has some serious lack of parenthesis. In general, commit39d61db0edb34d60b83c5e0d62d0e906578cc707just was pretty damn bad!
Unfortunately, I can't disagree.
Quoted 3 lines
I'm becoming a bit disgruntled about this whole thing, I have to admit. I'm just not sure the bugs here are worth it. Especially considering that
__get_order()has apparently never even tested these things to begin with,
It was tested... I've just re-examined my test program and I've realised I've only tested power-of-2 parameters. Sigh.
Quoted 1 line
since nobody but FRV has ever #defined the
ARCH_HAS_ILOG2_U?? macros.
Well, that should be CONFIG_ARCH_HAS_ILOG2_U?? macros, and powerpc defines those too.
Quoted 1 line
- buggy
True, for N being a non-power-of-two, unfortunately; and also where evaluating N has side-effects.
Quoted 1 line
- untested
Not true, just that my userspace test program isn't sufficiently exhaustive.
Quoted 1 line
- has untrue comments
Unfortunately so.
Quoted 1 line
- makes no real sense
Not true.
Various archs (including i386, x86_64, powerpc and frv) have instructions that can be used to calculate integer log2(N). The fallback position is to use a loop:
size = (size - 1) >> (PAGE_SHIFT - 1);
order = -1;
do {
size >>= 1;
order++;
} while (size);Quoted 3 lines
and I'm inclined to just revert
39d61db0instead of adding more and more breakage to it, since it's simply not going to help with the fundamental problems!
Probably a good idea. I'll work on it some more and improve my test program (which is actually quite simple to do).
David
ALIGN via ilog2 without gccisms (Re: [PATCH] Fix get_order())
Quoted 5 lines
From: David Howells
Newsgroups: gmane.linux.kernel
Subject: Re: [PATCH] Fixget_order()
Date: Wed, 07 Mar 2007 11:43:06 +0000
[]
Quoted 3 lines
Various archs (including i386,
x86_64, powerpc and frv) have instructions that can be used to calculate integer log2(N).
Probably it can be used to get rid of gccisms and "type fluff" due to bitwise arithmetics in ALIGN?
Here:
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
like that:
#define ALIGN(x,y) __ALIGN_MASK(x,ilog2(y))
#define __ALIGN_MASK(x,bits) (((((x) >> (bits)) << 1) + 2) << (bits - 1))
Note side effect, that this one always yields even result. Maybe this is good, due to avoidance of misaligned access.
____
Re: ALIGN via ilog2 without gccisms (Re: [PATCH] Fix get_order())
Quoted 3 lines · Oleg Verych
Probably it can be used to get rid of gccisms and "type fluff" due to bitwise arithmetics in ALIGN?
Hell no.
The typeof is there to make sure we have the right type, and it's simple.
The current ALIGN() macro is efficient as hell (generating just a simple mask+add). Turning it into some kind of horrible thing that uses ilog2() would be a total mistake.
Also, your ALIGN() macro was broken. That's not how ALIGN() is supposed to work.
Linus
Re: ALIGN via ilog2 without gccisms (Re: [PATCH] Fix get_order())
Quoted 7 lines · Linus Torvalds
Quoted 3 lines · Oleg Verych
Probably it can be used to get rid of gccisms and "type fluff" due to bitwise arithmetics in ALIGN?
Quoted 7 lines
Hell no.
The typeof is there to make sure we have the right type, and it's simple.
The current
ALIGN()macro is efficient as hell (generating just a simple mask+add). Turning it into some kind of horrible thing that usesilog2()would be a total mistake.
GCC's assembler version of this macro is optimized as needed.
But i wanted to address Al's statement about using typeof():
,-*- [ Message-ID: <[email protected]> ]
|IOW, gcc allows type to leak out of scope it's been defined in (and |typeof adds even more fun to the picture). It not only goes against |a _lot_ in C, it's actually not thought through by gcc folks. Just |try to mix that with variable-length arrays and watch it blow up |in interesting ways...
`-*-
As for me, this is example of assembler's need, that very hard to implement in C. Also, i doubt, C's shift doing any "type fluff" on its only argument.
Quoted 2 lines
Also, your
ALIGN()macro was broken. That's not howALIGN()is supposed to work.
Yes, maybe so.
____
Re: ALIGN via ilog2 without gccisms (Re: [PATCH] Fix get_order())
Quoted 2 lines · Oleg Verych
GCC's assembler version of this macro is optimized as needed.
Not fora non-constant mask, I bet.
Quoted 1 line
But i wanted to address Al's statement about using
typeof():
Well, that doesn't affect ALIGN(), since you can only use ALIGN() on an arithmetic type anyway (and only within scope). So the odd corner cases with typeof leaking data outside of the scope is not an issue.
Linus
Re: ALIGN (Re: [PATCH] Fix get_order())
In reply to Linus TorvaldsQuoted 7 lines · Linus Torvalds
Quoted 3 lines · Oleg Verych
Probably it can be used to get rid of gccisms and "type fluff" due to bitwise arithmetics in ALIGN?
Quoted 7 lines
Hell no.
The typeof is there to make sure we have the right type, and it's simple.
The current
ALIGN()macro is efficient as hell (generating just a simple mask+add). Turning it into some kind of horrible thing that usesilog2()would be a total mistake.
OTOH, if i would write it this way
#define BALIGN(x,bits) ((((x) >> (bits)) + 1) << (bits))
that would give more convenient way of expessing alignment (values of what are most widely used, i.e powers of two) without log2(:) requirement, no?
arch/powerpc/mm/hugetlbpage.c: addr = ALIGN(addr+1,1UL<<HTLB_AREA_SHIFT); arch/powerpc/mm/hugetlbpage.c: addr = ALIGN(addr+1,1<<SID_SHIFT);
But it's not conventional, of course, and name is ugly.
____
Re: ALIGN (Re: [PATCH] Fix get_order())
Quoted 4 lines · Oleg Verych
OTOH, if i would write it this way
#define
BALIGN(x,bits)((((x) >> (bits)) + 1) << (bits))
But that's *wrong*. It aligns something that is *already* aligned to something else.
So you'd have to do it as something like
#define ALIGN_TO_POW2(x,pow) \ ((((x)+(1<<(pow))-1)>>(pow))<<(pow))
and the thing is, that's actually both (a) less readable than what ALIGN() already does (b) unless the compiler notices that what you really want is a "bitwise and", it's really inefficient too because shifts are generally much more expensive than simple bitops.
So you're simply better off doing it as
#define ALIGN_TO_POW2(x,pow) ALIGN(x, (1ull << pow))
but then you'd still have to depend on the "typeof()" magic in ALIGN() to turn the final end result back to the type of "x".
(the "1ull" is necessary exactly because you don't know what type "x" is beforehand, so you need to make sure that the mask is at *least* as big a type as x, and not overflow to undefined C semantics).
Linus
Re: ALIGN (Re: [PATCH] Fix get_order())
Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Oleg Verych
OTOH, if i would write it this way
#define
BALIGN(x,bits)((((x) >> (bits)) + 1) << (bits))But that's *wrong*. It aligns something that is *already* aligned to something else.
Indeed. I'm confused by semantics of ALIGN macro, as from C arithmetic side, as from using side. Former confusion also yields patches like (Fix 'ALIGN()' macro, take 2), fixing that, i was wonder about.
BALIGN is like do-this alignment, and must be
void do_align(what, bits)
instead. While clear arithmetic (optimized in assembler, shifts are C shifts!), it fails in value(alignment(what, how)) kind of thing.
Quoted 12 lines
So you'd have to do it as something like
#define ALIGN_TO_POW2(x,pow) \ ((((x)+(1<<(pow))-1)>>(pow))<<(pow))and the thing is, that's actually both (a) less readable than what
ALIGN()already does (b) unless the compiler notices that what you really want is a "bitwise and", it's really inefficient too because shifts are generally much more expensive than simple bitops.So you're simply better off doing it as
Quoted 8 lines
#define ALIGN_TO_POW2(x,pow) ALIGN(x, (1ull << pow))but then you'd still have to depend on the "
typeof()" magic inALIGN()to turn the final end result back to the type of "x".(the "1ull" is necessary exactly because you don't know what type "x" is beforehand, so you need to make sure that the mask is at *least* as big a type as x, and not overflow to undefined C semantics).
Via typeof() *feature* and 1U, 1UL, 1ULL *things*, i (we?) have that, what is described above.
Examples of using ALIGN. As that, i've picked earlier,
arch/powerpc/mm/hugetlbpage.c: addr = ALIGN(addr+1,1UL<<HTLB_AREA_SHIFT); arch/powerpc/mm/hugetlbpage.c: addr = ALIGN(addr+1,1<<SID_SHIFT);
mixes two things, and i can't understand what is meant here,
lib/swiotlb.c: io_tlb_nslabs = ALIGN(io_tlb_nslabs, IO_TLB_SEGSIZE); lib/swiotlb.c: io_tlb_nslabs = ALIGN(io_tlb_nslabs, IO_TLB_SEGSIZE); lib/swiotlb.c: io_tlb_nslabs = ALIGN(io_tlb_nslabs, IO_TLB_SEGSIZE);
clear "do align", etc.
So, maybe spitting "do align" (with C shifts, without C arithmetics error-prone-due-to-C magic) and "alignment" isn't a bad idea.
Easiness is what i wanted to have. For example, like in this clean up, 'proper memory-mapped accesses rather than making up our own "volatile" pointers' in 6c0ffb9d2fd987c79c6cbb81c3f3011c63749b1a. Clear C-vs-call() rewrite.
Sorry, if i'm barking up the wrong tree here.
____
Re: ALIGN
In reply to Linus TorvaldsQuoted 10 lines · Linus Torvalds
Quoted 3 lines · Oleg Verych
Probably it can be used to get rid of gccisms and "type fluff" due to bitwise arithmetics in ALIGN?
Hell no.
The typeof is there to make sure we have the right type, and it's simple.
Right. Now i see.
Thanks!
____