[PATCH] Fix get_order()

[PATCH] Fix get_order()

[David Howells]

From: David Howells <dhowells@redhat.com>

Fix get_order() to use ilog2() properly.

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

 include/asm-generic/page.h |   14 +++++++++++---
 include/linux/log2.h       |   20 ++++++++++++++++++--
 2 files changed, 29 insertions(+), 5 deletions(-)

diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
index b55052c..c37571d 100644
--- a/include/asm-generic/page.h
+++ b/include/asm-generic/page.h
@@ -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)					\
  )
 
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 57e641e..bc3a0eb 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -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)			\
  )

Re: [PATCH] Fix get_order()

[H. Peter Anvin]

David Howells wrote:
> From: David Howells <dhowells@redhat.com>
> 
> Fix get_order() to use ilog2() properly.
> 
> Signed-Off-By: David Howells <dhowells@redhat.com>
> ---
> 
>  include/asm-generic/page.h |   14 +++++++++++---
>  include/linux/log2.h       |   20 ++++++++++++++++++--
>  2 files changed, 29 insertions(+), 5 deletions(-)
> 
> diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
> index b55052c..c37571d 100644
> --- a/include/asm-generic/page.h
> +++ b/include/asm-generic/page.h
> @@ -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

Re: [PATCH] Fix get_order()

[David Howells]

H. Peter Anvin <hpa@zytor.com> wrote:

> 	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

Re: [PATCH] Fix get_order()

[Linus Torvalds]

On Tue, 6 Mar 2007, David Howells wrote:
> @@ -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

Re: [PATCH] Fix get_order()

[David Howells]

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 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

Re: [PATCH] Fix get_order()

[Linus Torvalds]

On Tue, 6 Mar 2007, David Howells wrote:
>  /**
> + * 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)

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

Re: [PATCH] Fix get_order()

[David Howells]

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> > +#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.

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

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

> The whole "get_order()" macro also has some serious lack of parenthesis. 
> In general, commit 39d61db0edb34d60b83c5e0d62d0e906578cc707 just was 
> pretty damn bad!

Unfortunately, I can't disagree.

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

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

>  - buggy

True, for N being a non-power-of-two, unfortunately; and also where evaluating
N has side-effects.

>  - untested

Not true, just that my userspace test program isn't sufficiently exhaustive.

>  - has untrue comments

Unfortunately so.

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

> 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!

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

[Oleg Verych]

> From: David Howells
> Newsgroups: gmane.linux.kernel
> Subject: Re: [PATCH] Fix get_order()
> Date: Wed, 07 Mar 2007 11:43:06 +0000
>
[]
> 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())

[Linus Torvalds]

On Wed, 7 Mar 2007, Oleg Verych wrote:
>
> 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())

[Oleg Verych]

On Wed, Mar 07, 2007 at 08:38:27AM -0800, Linus Torvalds wrote:
> 
> 
> On Wed, 7 Mar 2007, Oleg Verych wrote:
> >
> > 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.

GCC's assembler version of this macro is optimized as needed.

But i wanted to address Al's statement about using typeof():

,-*- [ Message-ID: <20061127044138.GA3078@ftp.linux.org.uk> ]
|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.

> Also, your ALIGN() macro was broken. That's not how ALIGN() is supposed to 
> work.

Yes, maybe so.
____

Re: ALIGN via ilog2 without gccisms (Re: [PATCH] Fix get_order())

[Linus Torvalds]

On Wed, 7 Mar 2007, Oleg Verych wrote:
> 
> GCC's assembler version of this macro is optimized as needed.

Not fora non-constant mask, I bet.

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

[Oleg Verych]

On Wed, Mar 07, 2007 at 08:38:27AM -0800, Linus Torvalds wrote:
> 
> 
> On Wed, 7 Mar 2007, Oleg Verych wrote:
> >
> > 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.

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

[Linus Torvalds]

On Sat, 10 Mar 2007, Oleg Verych wrote:
> 
> 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())

[Oleg Verych]

On Fri, Mar 09, 2007 at 03:15:10PM -0800, Linus Torvalds wrote:
> 
> 
> On Sat, 10 Mar 2007, Oleg Verych wrote:
> > 
> > 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.

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

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

[Oleg Verych]

On Wed, Mar 07, 2007 at 08:38:27AM -0800, Linus Torvalds wrote:
> 
> 
> On Wed, 7 Mar 2007, Oleg Verych wrote:
> >
> > 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!
____