[PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[Roland Dreier]

When code relies on a constant being a power of 2:

	#define FOO	512	/* must be a power of 2 */

it would be nice to be able to do:

	BUILD_BUG_ON(!is_power_of_2(FOO));

However applying an inline function does not result in a compile-time
constant that can be used with BUILD_BUG_ON(), so trying that gives
results in:

	error: bit-field '<anonymous>' width not an integer constant

We can fix this by changing is_power_of_2() to a macro; we leave the
inline function for the non-constant case, to avoid evaluating the
parameter more than once.  (gcc does not accept a multi-statement
expression like "({ unsigned long __n = n; ... })" as a compile-time
constant so that solution doesn't work)

Signed-off-by: Roland Dreier <rolandd@cisco.com>
---
This is somewhat of an RFC -- I'm a bit undecided whether it's really
worth making this change.  It's prompted by
http://www.mail-archive.com/linux-rdma@vger.kernel.org/msg01941.html and
http://www.mail-archive.com/linux-rdma@vger.kernel.org/msg01950.html
which do ugly things to work around is_power_of_2 not being usable in
BUILD_BUG_ON().

On the other hand maybe just

/* FOO must be a power of 2 */
#define FOO_SHIFT 9
#define FOO (1 << FOO_SHIFT)

is good enough.

 include/linux/log2.h |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)

diff --git a/include/linux/log2.h b/include/linux/log2.h
index 25b8086..248f69c 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -49,11 +49,18 @@ int __ilog2_u64(u64 n)
  */
 
 static inline __attribute__((const))
-bool is_power_of_2(unsigned long n)
+bool __is_power_of_2(unsigned long n)
 {
 	return (n != 0 && ((n & (n - 1)) == 0));
 }
 
+#define is_power_of_2(n)					\
+(								\
+	__builtin_constant_p(n) ?				\
+		(((n) != 0) && (((n) & ((n) - 1)) == 0)) :	\
+		__is_power_of_2(n)				\
+)
+
 /*
  * round up to nearest power of two
  */

Re: [PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[Andrew Morton]

On Wed, 06 Jan 2010 12:21:13 -0800
Roland Dreier <rdreier@cisco.com> wrote:

> When code relies on a constant being a power of 2:
> 
> 	#define FOO	512	/* must be a power of 2 */
> 
> it would be nice to be able to do:
> 
> 	BUILD_BUG_ON(!is_power_of_2(FOO));
> 
> However applying an inline function does not result in a compile-time
> constant that can be used with BUILD_BUG_ON(), so trying that gives
> results in:
> 
> 	error: bit-field '<anonymous>' width not an integer constant
> 
> We can fix this by changing is_power_of_2() to a macro; we leave the
> inline function for the non-constant case, to avoid evaluating the
> parameter more than once.  (gcc does not accept a multi-statement
> expression like "({ unsigned long __n = n; ... })" as a compile-time
> constant so that solution doesn't work)
> 
> Signed-off-by: Roland Dreier <rolandd@cisco.com>
> ---
> This is somewhat of an RFC -- I'm a bit undecided whether it's really
> worth making this change.  It's prompted by
> http://www.mail-archive.com/linux-rdma@vger.kernel.org/msg01941.html and
> http://www.mail-archive.com/linux-rdma@vger.kernel.org/msg01950.html
> which do ugly things to work around is_power_of_2 not being usable in
> BUILD_BUG_ON().
> 
> On the other hand maybe just
> 
> /* FOO must be a power of 2 */
> #define FOO_SHIFT 9
> #define FOO (1 << FOO_SHIFT)
> 
> is good enough.
> 
>  include/linux/log2.h |    9 ++++++++-
>  1 files changed, 8 insertions(+), 1 deletions(-)
> 
> diff --git a/include/linux/log2.h b/include/linux/log2.h
> index 25b8086..248f69c 100644
> --- a/include/linux/log2.h
> +++ b/include/linux/log2.h
> @@ -49,11 +49,18 @@ int __ilog2_u64(u64 n)
>   */
>  
>  static inline __attribute__((const))
> -bool is_power_of_2(unsigned long n)
> +bool __is_power_of_2(unsigned long n)
>  {
>  	return (n != 0 && ((n & (n - 1)) == 0));
>  }
>  
> +#define is_power_of_2(n)					\
> +(								\
> +	__builtin_constant_p(n) ?				\
> +		(((n) != 0) && (((n) & ((n) - 1)) == 0)) :	\
> +		__is_power_of_2(n)				\
> +)
> +

We've had recurring struggles with various versions of gcc screwing up
constructs of this form and trying to emit the non-constant code when
the arg was clearly a compile-time constant.  One episode which comes
to mind was when we made changes to kmalloc().

Of course, that might not bite us in this case - it would need a lot of
coverage testing to find out.


Perhaps we can avoid worrying about that via

#define BUILD_BUG_ON_NOT_POWER_OF_2(n)	\
	BUILD_BUG_ON((n != 0 && ((n & (n - 1)) == 0)))

?

Re: [PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[Roland Dreier]

 > Perhaps we can avoid worrying about that via

 > #define BUILD_BUG_ON_NOT_POWER_OF_2(n)	\
 > 	BUILD_BUG_ON((n != 0 && ((n & (n - 1)) == 0)))

Having something so specific to this particular case makes me feel like
maybe it's just not worth it.  At least in the case I'm looking at, we
could just have:

/*
 * The code relies on FOO being a power of 2.  If you break this,
 * you're dumb.
 */
#define FOO_SHIFT	6
#define FOO		(1 << FOO_SHIFT)

Your thoughts?

 - R.

Re: [PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[David Dillow]

On Wed, 2010-01-06 at 12:44 -0800, Roland Dreier wrote:
> > Perhaps we can avoid worrying about that via
> 
>  > #define BUILD_BUG_ON_NOT_POWER_OF_2(n)	\
>  > 	BUILD_BUG_ON((n != 0 && ((n & (n - 1)) == 0)))
> 
> Having something so specific to this particular case makes me feel like
> maybe it's just not worth it.  At least in the case I'm looking at, we
> could just have:
> 
> /*
>  * The code relies on FOO being a power of 2.  If you break this,
>  * you're dumb.
>  */
> #define FOO_SHIFT	6
> #define FOO		(1 << FOO_SHIFT)
> 
> Your thoughts?

I'm fine with that, but now I'll probably be the dumb one to break it
some day in the future.

Re: [PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[Andrew Morton]

On Wed, 06 Jan 2010 12:44:05 -0800
Roland Dreier <rdreier@cisco.com> wrote:

> 
>  > Perhaps we can avoid worrying about that via
> 
>  > #define BUILD_BUG_ON_NOT_POWER_OF_2(n)	\
>  > 	BUILD_BUG_ON((n != 0 && ((n & (n - 1)) == 0)))
> 
> Having something so specific to this particular case makes me feel like
> maybe it's just not worth it.

mm..  I think _something_ is worth it.  The requirement that a constant
be a power of two is a very common one in the kernel.

If you feel strongly about it and think the incremental benefit of your
version is worth the effort of screening out gcc warts then ho hum, go
for it I guess.

>  At least in the case I'm looking at, we
> could just have:
> 
> /*
>  * The code relies on FOO being a power of 2.  If you break this,
>  * you're dumb.
>  */
> #define FOO_SHIFT	6
> #define FOO		(1 << FOO_SHIFT)
> 
> Your thoughts?

Given the probably-hundreds of sites which could utilise this assertion,
that approach will be a bit of a PITA.

[PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Roland Dreier]

When code relies on a constant being a power of 2:

	#define FOO	512	/* must be a power of 2 */

it would be nice to be able to do:

	BUILD_BUG_ON(!is_power_of_2(FOO));

However applying an inline function does not result in a compile-time
constant that can be used with BUILD_BUG_ON(), so trying that gives
results in:

	error: bit-field '<anonymous>' width not an integer constant

As suggested by akpm, rather than monkeying around with is_power_of_2()
and risking gcc warts about constant expressions, just create a macro
BUILD_BUG_ON_NOT_POWER_OF_2() to encapsulate this common requirement.

Signed-off-by: Roland Dreier <rolandd@cisco.com>
--- 
 > mm..  I think _something_ is worth it.  The requirement that a constant
 > be a power of two is a very common one in the kernel.

Fair enough... here's your suggestion of BUILD_BUG_ON_NOT_POWER_OF_2().
<linux/kernel.h> does seem to be going the way of a gazillion very
specific helper macros, so I guess this fits right in.

 include/linux/kernel.h |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 3fc9f5a..a1b6652 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -734,6 +734,10 @@ struct sysinfo {
 /* Force a compilation error if condition is constant and true */
 #define MAYBE_BUILD_BUG_ON(cond) ((void)sizeof(char[1 - 2 * !!(cond)]))
 
+/* Force a compilation error if expression is not a power of 2 */
+#define BUILD_BUG_ON_NOT_POWER_OF_2(n)			\
+	BUILD_BUG_ON(((n) != 0 && (((n) & ((n) - 1)) == 0)))
+
 /* Force a compilation error if condition is true, but also produce a
    result (of value 0 and type size_t), so the expression can be used
    e.g. in a structure initializer (or where-ever else comma expressions

Re: [PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Andrew Morton]

On Wed, 06 Jan 2010 15:02:40 -0800
Roland Dreier <rdreier@cisco.com> wrote:

> Fair enough... here's your suggestion of BUILD_BUG_ON_NOT_POWER_OF_2().
> <linux/kernel.h> does seem to be going the way of a gazillion very
> specific helper macros, so I guess this fits right in.
> 
>  include/linux/kernel.h |    4 ++++
>  1 files changed, 4 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> index 3fc9f5a..a1b6652 100644
> --- a/include/linux/kernel.h
> +++ b/include/linux/kernel.h
> @@ -734,6 +734,10 @@ struct sysinfo {
>  /* Force a compilation error if condition is constant and true */
>  #define MAYBE_BUILD_BUG_ON(cond) ((void)sizeof(char[1 - 2 * !!(cond)]))
>  
> +/* Force a compilation error if expression is not a power of 2 */
> +#define BUILD_BUG_ON_NOT_POWER_OF_2(n)			\
> +	BUILD_BUG_ON(((n) != 0 && (((n) & ((n) - 1)) == 0)))
> +
>  /* Force a compilation error if condition is true, but also produce a
>     result (of value 0 and type size_t), so the expression can be used
>     e.g. in a structure initializer (or where-ever else comma expressions

ok..  I'll give it a week or so for better ideas to turn up then I'll
send this Linuswards so that ongoing work can use it.

Re: [PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Bart Van Assche]

On Thu, Jan 7, 2010 at 12:02 AM, Roland Dreier <rdreier@cisco.com> wrote:
> +/* Force a compilation error if expression is not a power of 2 */
> +#define BUILD_BUG_ON_NOT_POWER_OF_2(n)                 \
> +       BUILD_BUG_ON(((n) != 0 && (((n) & ((n) - 1)) == 0)))

Hello Roland,

Can you please change the above into the following, such that the
macro does what its name suggests:

#define BUILD_BUG_ON_NOT_POWER_OF_2(n)                 \
       BUILD_BUG_ON(((n) == 0 || (((n) & ((n) - 1)) != 0)))

Bart.

Re: [PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Roland Dreier]

 > Can you please change the above into the following, such that the
 > macro does what its name suggests:

Argh!  Good catch, thanks -- I even tested my patch, but with my brain
in reverse so I sent the bad patch.

Andrew, please replace with this one, which includes your update to the
comment as well:

===

Add BUILD_BUG_ON_NOT_POWER_OF_2()

When code relies on a constant being a power of 2:

	#define FOO	512	/* must be a power of 2 */

it would be nice to be able to do:

	BUILD_BUG_ON(!is_power_of_2(FOO));

However applying an inline function does not result in a compile-time
constant that can be used with BUILD_BUG_ON(), so trying that gives
results in:

	error: bit-field '<anonymous>' width not an integer constant

As suggested by akpm, rather than monkeying around with is_power_of_2()
and risking gcc warts about constant expressions, just create a macro
BUILD_BUG_ON_NOT_POWER_OF_2() to encapsulate this common requirement.

Signed-off-by: Roland Dreier <rolandd@cisco.com>
---
 include/linux/kernel.h |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 3fc9f5a..328bca6 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -734,6 +734,10 @@ struct sysinfo {
 /* Force a compilation error if condition is constant and true */
 #define MAYBE_BUILD_BUG_ON(cond) ((void)sizeof(char[1 - 2 * !!(cond)]))
 
+/* Force a compilation error if a constant expression is not a power of 2 */
+#define BUILD_BUG_ON_NOT_POWER_OF_2(n)			\
+	BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))
+
 /* Force a compilation error if condition is true, but also produce a
    result (of value 0 and type size_t), so the expression can be used
    e.g. in a structure initializer (or where-ever else comma expressions

Re: [PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Robert P. J. Day]

On Wed, 6 Jan 2010, Roland Dreier wrote:

> When code relies on a constant being a power of 2:
>
> 	#define FOO	512	/* must be a power of 2 */
>
> it would be nice to be able to do:
>
> 	BUILD_BUG_ON(!is_power_of_2(FOO));
>
> However applying an inline function does not result in a
> compile-time constant that can be used with BUILD_BUG_ON(), so
> trying that gives results in:
>
> 	error: bit-field '<anonymous>' width not an integer constant
>
> As suggested by akpm, rather than monkeying around with
> is_power_of_2() and risking gcc warts about constant expressions,
> just create a macro BUILD_BUG_ON_NOT_POWER_OF_2() to encapsulate
> this common requirement.

  my normal pedantry coming to the surface, but can we at least assume
that people will use this test to *legitimately* test whether or not
something is a power of two, and not that there is a single bit set
(in the case of mask bits where all settings must be mutually
exclusive)?

  there's a lot of this sort of thing throughout the kernel:

    (n) != 0 && (((n) & ((n) - 1))

but it's sometimes unclear whether someone is testing for a) power of
two, or b) single bit set.  if you're going to introduce that kind of
BUILD BUG (which is a good idea), let's try to not immediately abuse
it semantically. :-)

rday
--

========================================================================
Robert P. J. Day                               Waterloo, Ontario, CANADA

            Linux Consulting, Training and Kernel Pedantry.

Web page:                                          http://crashcourse.ca
Twitter:                                       http://twitter.com/rpjday
========================================================================

Re: [PATCH] Add BUILD_BUG_ON_NOT_POWER_OF_2()

[Stefan Richter]

Robert P. J. Day wrote:
>   my normal pedantry coming to the surface, but can we at least assume
> that people will use this test to *legitimately* test whether or not
> something is a power of two, and not that there is a single bit set
> (in the case of mask bits where all settings must be mutually
> exclusive)?
> 
>   there's a lot of this sort of thing throughout the kernel:
> 
>     (n) != 0 && (((n) & ((n) - 1))
> 
> but it's sometimes unclear whether someone is testing for a) power of
> two, or b) single bit set.  if you're going to introduce that kind of
> BUILD BUG (which is a good idea), let's try to not immediately abuse
> it semantically. :-)

It's merely about math, not about semantics.  Plus, its application is
restricted to build-time checks (of defined constants) anyway.

Hence I would argue that "check at build time whether a defined
bitmask's Hamming weight is 1; abort build if it isn't" can be
legitimately and sufficiently readably implemented by means of the new
BUILD_BUG_ON_NOT_POWER_OF_2().
-- 
Stefan Richter
-=====-==-=- ---= --===
http://arcgraph.de/sr/

Re: [PATCH] log2.h: Macro-ize is_power_of_2() for use in BUILD_BUG_ON

[Roland Dreier]

 > We've had recurring struggles with various versions of gcc screwing up
 > constructs of this form and trying to emit the non-constant code when
 > the arg was clearly a compile-time constant.  One episode which comes
 > to mind was when we made changes to kmalloc().
 > 
 > Of course, that might not bite us in this case - it would need a lot of
 > coverage testing to find out.

Actually, after thinking about this a bit more I don't think this is
much of a risk in this case.  The bad case is where gcc gets the wrong
answer for __builtin_constant_p(), and in that case, we're left with the
status quo ante, ie a call to the original inline function implementation.

This will break a call to BUILD_BUG_ON() but that's visible at compile
time.  It's hard to think of a silent failure case that actually hurts
anything -- the macro and inline implementation are identical, except
that the macro implementation will work when gcc really needs a compile
time constant.

 - R.