[PATCH] Fix get_order() [try #2]

[PATCH] Fix get_order() [try #2]

[David Howells]

From: David Howells <dhowells@redhat.com>

Provide an ilog2_up() that rounds its result up (ilog2() rounds down).

Fix get_order() to use ilog2_up() not ilog2() to get the correct rounding.

Adjust the documentation surrounding ilog2() and co. to indicate what rounding
they perform.

Fix roundup_pow_of_two(1) to give 1, not 0.

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

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

diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
index b55052c..c79dc23 100644
--- a/include/asm-generic/page.h
+++ b/include/asm-generic/page.h
@@ -17,11 +17,15 @@ 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;
-	return order >= 0 ? order : 0;
+	if (size <= (1UL << page_shift))
+		return 0;
+	else
+		return __ilog2_u32(size - 1) + 1 - page_shift;
 #elif BITS_PER_LONG == 64 && defined(ARCH_HAS_ILOG2_U64)
-	int order = __ilog2_u64(size) - page_shift;
-	return order >= 0 ? order : 0;
+	if (size <= (1UL << page_shift))
+		return 0;
+	else
+		return __ilog2_u64(size - 1) + 1 - page_shift;
 #else
 	int order;
 
@@ -46,7 +50,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() [try #2]

[H. Peter Anvin]

David Howells wrote:
> From: David Howells <dhowells@redhat.com>
> 
> Provide an ilog2_up() that rounds its result up (ilog2() rounds down).
> 
> Fix get_order() to use ilog2_up() not ilog2() to get the correct rounding.
> 
> Adjust the documentation surrounding ilog2() and co. to indicate what rounding
> they perform.
> 
> Fix roundup_pow_of_two(1) to give 1, not 0.

Eh? roundup_pow_of_two(1) should be 0; 2^0 = 1.

	-hpa

Re: [PATCH] Fix get_order() [try #2]

[H. Peter Anvin]

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

Why not just make it ((n) < 1 ? 0 : ...) and make it well-defined for
n == 0?

> +/**
>   * 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))		\
>  				   ) :		\

... then this can be just "1UL << ilog2_up(n)".

[Sorry about previous email.  I got confused about what 
roundup_pow_of_two() actually does.]

	-hpa

Re: [PATCH] Fix get_order() [try #2]

[David Howells]

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

> Eh? roundup_pow_of_two(1) should be 0; 2^0 = 1.

Nonono.

	roundup_pow_of_two(0)  => ?
	roundup_pow_of_two(1)  => 1
	roundup_pow_of_two(2)  => 2
	roundup_pow_of_two(3)  => 4
	roundup_pow_of_two(4)  => 4
	roundup_pow_of_two(5)  => 8
	roundup_pow_of_two(6)  => 8
	roundup_pow_of_two(7)  => 8
	roundup_pow_of_two(8)  => 8
	roundup_pow_of_two(9)  => 16
	roundup_pow_of_two(10) => 16
	roundup_pow_of_two(11) => 16
	...

David

Re: [PATCH] Fix get_order() [try #2]

[David Howells]

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

> Why not just make it ((n) < 1 ? 0 : ...) and make it well-defined for
> n == 0?

Because log2(0) is -INF or mathematically undefined or something isn't it?

David

Re: [PATCH] Fix get_order() [try #2]

[H. Peter Anvin]

David Howells wrote:
> H. Peter Anvin <hpa@zytor.com> wrote:
> 
>> Why not just make it ((n) < 1 ? 0 : ...) and make it well-defined for
>> n == 0?
> 
> Because log2(0) is -INF or mathematically undefined or something isn't it?

Yes, but it's a *rounding up* function.  In this case, it makes sense to 
round up 0 to 1.  This is, in fact, a common way to handle requests for 
zero-byte allocation in order to be able to return a unique address for 
each one, so it's not a spurious thing.

	-hpa

Re: [PATCH] Fix get_order() [try #2]

[Alexey Dobriyan]

On Tue, Mar 06, 2007 at 06:34:26PM +0000, David Howells wrote:
> Provide an ilog2_up() that rounds its result up (ilog2() rounds down).
>
> Fix get_order() to use ilog2_up() not ilog2() to get the correct rounding.
>
> Adjust the documentation surrounding ilog2() and co. to indicate what rounding
> they perform.
>
> Fix roundup_pow_of_two(1) to give 1, not 0.

> --- a/include/asm-generic/page.h
> +++ b/include/asm-generic/page.h
> @@ -17,11 +17,15 @@ static inline __attribute__((const))
>  int __get_order(unsigned long size, int page_shift)
>  {
>  #if BITS_PER_LONG == 32 && defined(ARCH_HAS_ILOG2_U32)

There is no such thing except on FRV, where it's redundant.

				      CONFIG_ARCH_HAS_ILOG2_U32
				      ^^^^^^

> -	int order = __ilog2_u32(size) - page_shift;
> -	return order >= 0 ? order : 0;
> +	if (size <= (1UL << page_shift))
> +		return 0;
> +	else
> +		return __ilog2_u32(size - 1) + 1 - page_shift;
>  #elif BITS_PER_LONG == 64 && defined(ARCH_HAS_ILOG2_U64)

ditto

> -	int order = __ilog2_u64(size) - page_shift;
> -	return order >= 0 ? order : 0;
> +	if (size <= (1UL << page_shift))
> +		return 0;
> +	else
> +		return __ilog2_u64(size - 1) + 1 - page_shift;
>  #else
>  	int order;

Re: [PATCH] Fix get_order() [try #2]

[David Howells]

Alexey Dobriyan <adobriyan@gmail.com> wrote:

> >  #if BITS_PER_LONG == 32 && defined(ARCH_HAS_ILOG2_U32)
> 
> There is no such thing except on FRV, where it's redundant.

Redundant in what way?

> 				      CONFIG_ARCH_HAS_ILOG2_U32
> 				      ^^^^^^

Grrr.  Thanks for spotting that.

> >  #elif BITS_PER_LONG == 64 && defined(ARCH_HAS_ILOG2_U64)
> 
> ditto

Ditto.

David