is_power_of_2() only works for types <= sizeof(unsigned long) and it's
also not a constant expression. There are a number of places in kernel
where is_power_of_2() is called on u64, which fails on 32-bit
builds. Try to remedy that. While at it, make it a constant expression
when possible.
I admit I've only lightly tested this, and I haven't tried it with
allmodconfig.
Jani Nikula (4):
log2: add helper __IS_POWER_OF_2()
log2: have is_power_of_2() support bigger types than unsigned long
log2: allow use of is_power_of_2() in constant expressions
drm/i915/reg: use is_power_of_2() from log2.h
drivers/gpu/drm/i915/i915_reg_defs.h | 7 +------
include/linux/log2.h | 25 ++++++++++++++++++++-----
2 files changed, 21 insertions(+), 11 deletions(-)
--
2.39.2
Add a helper to avoid duplication in the subsequent changes.
Cc: Andrew Morton <[email protected]>
Cc: Christian König <[email protected]>
Cc: David Gow <[email protected]>
Signed-off-by: Jani Nikula <[email protected]>
---
include/linux/log2.h | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 9f30d087a128..19e773116ae3 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -33,6 +33,8 @@ int __ilog2_u64(u64 n)
}
#endif
+#define __IS_POWER_OF_2(n) ((n) != 0 && (((n) & ((n) - 1)) == 0))
+
/**
* is_power_of_2() - check if a value is a power of two
* @n: the value to check
@@ -44,7 +46,7 @@ int __ilog2_u64(u64 n)
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
- return (n != 0 && ((n & (n - 1)) == 0));
+ return __IS_POWER_OF_2(n);
}
/**
--
2.39.2
is_power_of_2() does not work properly for e.g. u64 in 32-bit
builds. Choose an unsigned long long version if the argument is bigger
than unsigned long.
Cc: Andrew Morton <[email protected]>
Cc: Christian König <[email protected]>
Cc: David Gow <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Jani Nikula <[email protected]>
---
include/linux/log2.h | 21 ++++++++++++++++-----
1 file changed, 16 insertions(+), 5 deletions(-)
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 19e773116ae3..4027d1eecd7f 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -35,6 +35,18 @@ int __ilog2_u64(u64 n)
#define __IS_POWER_OF_2(n) ((n) != 0 && (((n) & ((n) - 1)) == 0))
+static inline __attribute__((const))
+bool __is_power_of_2_ull(unsigned long long n)
+{
+ return __IS_POWER_OF_2(n);
+}
+
+static inline __attribute__((const))
+bool __is_power_of_2(unsigned long n)
+{
+ return __IS_POWER_OF_2(n);
+}
+
/**
* is_power_of_2() - check if a value is a power of two
* @n: the value to check
@@ -43,11 +55,10 @@ int __ilog2_u64(u64 n)
* *not* considered a power of two.
* Return: true if @n is a power of 2, otherwise false.
*/
-static inline __attribute__((const))
-bool is_power_of_2(unsigned long n)
-{
- return __IS_POWER_OF_2(n);
-}
+#define is_power_of_2(n) \
+ __builtin_choose_expr(sizeof(n) > sizeof(unsigned long), \
+ __is_power_of_2_ull(n), \
+ __is_power_of_2(n))
/**
* __roundup_pow_of_two() - round up to nearest power of two
--
2.39.2
Even though the static inline functions are __attribute__((const)) you
can't use them in constant expressions. Make is_power_of_2() a constant
expression if possible.
Cc: Andrew Morton <[email protected]>
Cc: Christian König <[email protected]>
Cc: David Gow <[email protected]>
Signed-off-by: Jani Nikula <[email protected]>
---
include/linux/log2.h | 8 +++++---
1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 4027d1eecd7f..447a85102de0 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -56,9 +56,11 @@ bool __is_power_of_2(unsigned long n)
* Return: true if @n is a power of 2, otherwise false.
*/
#define is_power_of_2(n) \
- __builtin_choose_expr(sizeof(n) > sizeof(unsigned long), \
- __is_power_of_2_ull(n), \
- __is_power_of_2(n))
+ __builtin_choose_expr(__is_constexpr(n), \
+ __IS_POWER_OF_2(n), \
+ __builtin_choose_expr(sizeof(n) > sizeof(unsigned long), \
+ __is_power_of_2_ull(n), \
+ __is_power_of_2(n)))
/**
* __roundup_pow_of_two() - round up to nearest power of two
--
2.39.2
Now that log2.h is_power_of_2() supports constant expressions, use it.
Signed-off-by: Jani Nikula <[email protected]>
---
drivers/gpu/drm/i915/i915_reg_defs.h | 7 +------
1 file changed, 1 insertion(+), 6 deletions(-)
diff --git a/drivers/gpu/drm/i915/i915_reg_defs.h b/drivers/gpu/drm/i915/i915_reg_defs.h
index be43580a6979..44e99a9a381f 100644
--- a/drivers/gpu/drm/i915/i915_reg_defs.h
+++ b/drivers/gpu/drm/i915/i915_reg_defs.h
@@ -52,11 +52,6 @@
__is_constexpr(__low) && \
((__low) < 0 || (__high) > 63 || (__low) > (__high)))))
-/*
- * Local integer constant expression version of is_power_of_2().
- */
-#define IS_POWER_OF_2(__x) ((__x) && (((__x) & ((__x) - 1)) == 0))
-
/**
* REG_FIELD_PREP() - Prepare a u32 bitfield value
* @__mask: shifted mask defining the field's length and position
@@ -71,7 +66,7 @@
((u32)((((typeof(__mask))(__val) << __bf_shf(__mask)) & (__mask)) + \
BUILD_BUG_ON_ZERO(!__is_constexpr(__mask)) + \
BUILD_BUG_ON_ZERO((__mask) == 0 || (__mask) > U32_MAX) + \
- BUILD_BUG_ON_ZERO(!IS_POWER_OF_2((__mask) + (1ULL << __bf_shf(__mask)))) + \
+ BUILD_BUG_ON_ZERO(!is_power_of_2((__mask) + (1ULL << __bf_shf(__mask)))) + \
BUILD_BUG_ON_ZERO(__builtin_choose_expr(__is_constexpr(__val), (~((__mask) >> __bf_shf(__mask)) & (__val)), 0))))
/**
--
2.39.2
Am 30.03.23 um 12:42 schrieb Jani Nikula:
> is_power_of_2() only works for types <= sizeof(unsigned long) and it's
> also not a constant expression. There are a number of places in kernel
> where is_power_of_2() is called on u64, which fails on 32-bit
> builds. Try to remedy that. While at it, make it a constant expression
> when possible.
>
> I admit I've only lightly tested this, and I haven't tried it with
> allmodconfig.
Looks good to me from a one mile high level pov. But I'm really not an
expert on that type of compiler magic, so only:
Acked-by: Christian König <[email protected]>
for the series.
Regards,
Christian.
>
>
> Jani Nikula (4):
> log2: add helper __IS_POWER_OF_2()
> log2: have is_power_of_2() support bigger types than unsigned long
> log2: allow use of is_power_of_2() in constant expressions
> drm/i915/reg: use is_power_of_2() from log2.h
>
> drivers/gpu/drm/i915/i915_reg_defs.h | 7 +------
> include/linux/log2.h | 25 ++++++++++++++++++++-----
> 2 files changed, 21 insertions(+), 11 deletions(-)
>
On Thu, 30 Mar 2023 13:42:39 +0300 Jani Nikula <[email protected]> wrote:
> is_power_of_2() only works for types <= sizeof(unsigned long) and it's
> also not a constant expression. There are a number of places in kernel
> where is_power_of_2() is called on u64, which fails on 32-bit
> builds. Try to remedy that. While at it, make it a constant expression
> when possible.
Yes, the current `is_power_of_2(unsigned long n)' isn't very general.
But wouldn't all these issues be addressed by simply doing
#define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
?
(With suitable tweaks to avoid evaluating `n' more than once)
From: Andrew Morton
> Sent: 30 March 2023 20:51
>
> On Thu, 30 Mar 2023 13:42:39 +0300 Jani Nikula <[email protected]> wrote:
>
> > is_power_of_2() only works for types <= sizeof(unsigned long) and it's
> > also not a constant expression. There are a number of places in kernel
> > where is_power_of_2() is called on u64, which fails on 32-bit
> > builds. Try to remedy that. While at it, make it a constant expression
> > when possible.
>
> Yes, the current `is_power_of_2(unsigned long n)' isn't very general.
>
> But wouldn't all these issues be addressed by simply doing
>
> #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
>
> ?
>
> (With suitable tweaks to avoid evaluating `n' more than once)
I think you need to use the 'horrid tricks' from min() to get
a constant expression from constant inputs.
For non-constants this looks ok (see https://godbolt.org/z/G73MTr9jn)
David
static inline int lisp2(unsigned long n)
{
return n && !(n & (n - 1));
}
static inline int llisp2(unsigned long long lln)
{
#if 0 // I think this looks worse, esp. for gcc on x86
return lln && !(lln & (lln - 1));
#else
unsigned long n = lln;
if (lln >= 1ull << 32) {
if (n)
return 0;
n = lln >> 32;
}
return lisp2(n);
#endif
}
#define isp2(n) (sizeof ((n)+0) == sizeof (long) ? lisp2(n) : llisp2(n))
int is12(unsigned long long i)
{
return isp2(i);
}
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <[email protected]> wrote:
> > But wouldn't all these issues be addressed by simply doing
> >
> > #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
> >
> > ?
> >
> > (With suitable tweaks to avoid evaluating `n' more than once)
>
> I think you need to use the 'horrid tricks' from min() to get
> a constant expression from constant inputs.
This
--- a/include/linux/log2.h~a
+++ a/include/linux/log2.h
@@ -41,11 +41,11 @@ int __ilog2_u64(u64 n)
* *not* considered a power of two.
* Return: true if @n is a power of 2, otherwise false.
*/
-static inline __attribute__((const))
-bool is_power_of_2(unsigned long n)
-{
- return (n != 0 && ((n & (n - 1)) == 0));
-}
+#define is_power_of_2(_n) \
+ ({ \
+ typeof(_n) n = (_n); \
+ n != 0 && ((n & (n - 1)) == 0); \
+ })
/**
* __roundup_pow_of_two() - round up to nearest power of two
_
worked for me in a simple test.
--- a/fs/open.c~b
+++ a/fs/open.c
@@ -1564,3 +1564,10 @@ int stream_open(struct inode *inode, str
}
EXPORT_SYMBOL(stream_open);
+
+#include <linux/log2.h>
+
+int foo(void)
+{
+ return is_power_of_2(43);
+}
_
foo:
# fs/open.c:1573: }
xorl %eax, %eax #
ret
Is there some more tricky situation where it breaks?
From: Andrew Morton
> Sent: 30 March 2023 23:19
>
> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <[email protected]> wrote:
>
> > > But wouldn't all these issues be addressed by simply doing
> > >
> > > #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
> > >
> > > ?
> > >
> > > (With suitable tweaks to avoid evaluating `n' more than once)
> >
> > I think you need to use the 'horrid tricks' from min() to get
> > a constant expression from constant inputs.
>
> This
>
> --- a/include/linux/log2.h~a
> +++ a/include/linux/log2.h
> @@ -41,11 +41,11 @@ int __ilog2_u64(u64 n)
> * *not* considered a power of two.
> * Return: true if @n is a power of 2, otherwise false.
> */
> -static inline __attribute__((const))
> -bool is_power_of_2(unsigned long n)
> -{
> - return (n != 0 && ((n & (n - 1)) == 0));
> -}
> +#define is_power_of_2(_n) \
> + ({ \
> + typeof(_n) n = (_n); \
> + n != 0 && ((n & (n - 1)) == 0); \
> + })
>
> /**
> * __roundup_pow_of_two() - round up to nearest power of two
> _
>
> worked for me in a simple test.
>
> --- a/fs/open.c~b
> +++ a/fs/open.c
> @@ -1564,3 +1564,10 @@ int stream_open(struct inode *inode, str
> }
>
> EXPORT_SYMBOL(stream_open);
> +
> +#include <linux/log2.h>
> +
> +int foo(void)
> +{
> + return is_power_of_2(43);
> +}
> _
>
>
> foo:
> # fs/open.c:1573: }
> xorl %eax, %eax #
> ret
>
>
> Is there some more tricky situation where it breaks?
Try:
static int x = is_power_of_2(43);
I suspect that some (all?) of the compile-time assert checks won't
like ({...}) either.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On Thu, 30 Mar 2023, Andrew Morton <[email protected]> wrote:
> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <[email protected]> wrote:
>
>> > But wouldn't all these issues be addressed by simply doing
>> >
>> > #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
>> >
>> > ?
>> >
>> > (With suitable tweaks to avoid evaluating `n' more than once)
>>
>> I think you need to use the 'horrid tricks' from min() to get
>> a constant expression from constant inputs.
>
> This
>
> --- a/include/linux/log2.h~a
> +++ a/include/linux/log2.h
> @@ -41,11 +41,11 @@ int __ilog2_u64(u64 n)
> * *not* considered a power of two.
> * Return: true if @n is a power of 2, otherwise false.
> */
> -static inline __attribute__((const))
> -bool is_power_of_2(unsigned long n)
> -{
> - return (n != 0 && ((n & (n - 1)) == 0));
> -}
> +#define is_power_of_2(_n) \
> + ({ \
> + typeof(_n) n = (_n); \
> + n != 0 && ((n & (n - 1)) == 0); \
> + })
>
> /**
> * __roundup_pow_of_two() - round up to nearest power of two
> _
>
> worked for me in a simple test.
>
> --- a/fs/open.c~b
> +++ a/fs/open.c
> @@ -1564,3 +1564,10 @@ int stream_open(struct inode *inode, str
> }
>
> EXPORT_SYMBOL(stream_open);
> +
> +#include <linux/log2.h>
> +
> +int foo(void)
> +{
> + return is_power_of_2(43);
> +}
> _
>
>
> foo:
> # fs/open.c:1573: }
> xorl %eax, %eax #
> ret
>
>
> Is there some more tricky situation where it breaks?
It doesn't work with BUILD_BUG_ON_ZERO().
test.c:
#define IS_POWER_OF_2(_n) \
({ \
typeof(_n) n = (_n); \
n != 0 && ((n & (n - 1)) == 0); \
})
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#define FOO(n) ((n) + BUILD_BUG_ON_ZERO(!IS_POWER_OF_2(n)))
int main(void)
{
return FOO(2);
}
$ gcc test.c
test.c: In function ‘main’:
test.c:16:51: error: bit-field ‘<anonymous>’ width not an integer constant
16 | #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
| ^
test.c:18:23: note: in expansion of macro ‘BUILD_BUG_ON_ZERO’
18 | #define FOO(n) ((n) + BUILD_BUG_ON_ZERO(!IS_POWER_OF_2(n)))
| ^~~~~~~~~~~~~~~~~
test.c:22:9: note: in expansion of macro ‘FOO’
22 | return FOO(2);
| ^~~
BR,
Jani.
--
Jani Nikula, Intel Open Source Graphics Center
On 31/03/2023 09:31, Jani Nikula wrote:
> On Thu, 30 Mar 2023, Andrew Morton <[email protected]> wrote:
>> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <[email protected]> wrote:
>>
>>>> But wouldn't all these issues be addressed by simply doing
>>>>
>>>> #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
>>>>
>>>> ?
>>>>
>>>> (With suitable tweaks to avoid evaluating `n' more than once)
>>>
>>> I think you need to use the 'horrid tricks' from min() to get
>>> a constant expression from constant inputs.
>>
>> This
>>
>> --- a/include/linux/log2.h~a
>> +++ a/include/linux/log2.h
>> @@ -41,11 +41,11 @@ int __ilog2_u64(u64 n)
>> * *not* considered a power of two.
>> * Return: true if @n is a power of 2, otherwise false.
>> */
>> -static inline __attribute__((const))
>> -bool is_power_of_2(unsigned long n)
>> -{
>> - return (n != 0 && ((n & (n - 1)) == 0));
>> -}
>> +#define is_power_of_2(_n) \
>> + ({ \
>> + typeof(_n) n = (_n); \
>> + n != 0 && ((n & (n - 1)) == 0); \
>> + })
>>
>> /**
>> * __roundup_pow_of_two() - round up to nearest power of two
>> _
>>
>> worked for me in a simple test.
>>
>> --- a/fs/open.c~b
>> +++ a/fs/open.c
>> @@ -1564,3 +1564,10 @@ int stream_open(struct inode *inode, str
>> }
>>
>> EXPORT_SYMBOL(stream_open);
>> +
>> +#include <linux/log2.h>
>> +
>> +int foo(void)
>> +{
>> + return is_power_of_2(43);
>> +}
>> _
>>
>>
>> foo:
>> # fs/open.c:1573: }
>> xorl %eax, %eax #
>> ret
>>
>>
>> Is there some more tricky situation where it breaks?
>
> It doesn't work with BUILD_BUG_ON_ZERO().
Like most programming problems, you just need another layer of
indirection! The below works for me in all the cases I could think of
(including __uint128_t).
#define __IS_POWER_OF_2(n) (n != 0 && ((n & (n - 1)) == 0))
#define _IS_POWER_OF_2(n, unique_n) \
({ \
typeof(n) unique_n = (n); \
__IS_POWER_OF_2(unique_n); \
})
#define is_power_of_2(n) \
__builtin_choose_expr(__is_constexpr((n)), \
__IS_POWER_OF_2((n)), \
_IS_POWER_OF_2(n, __UNIQUE_ID(_n)))
Although Jani's original might be easier to understand.
Steve
On Wed, 05 Apr 2023, Steven Price <[email protected]> wrote:
> On 31/03/2023 09:31, Jani Nikula wrote:
>> On Thu, 30 Mar 2023, Andrew Morton <[email protected]> wrote:
>>> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <[email protected]> wrote:
>>>
>>>>> But wouldn't all these issues be addressed by simply doing
>>>>>
>>>>> #define is_power_of_2(n) (n != 0 && ((n & (n - 1)) == 0))
>>>>>
>>>>> ?
>>>>>
>>>>> (With suitable tweaks to avoid evaluating `n' more than once)
>>>>
>>>> I think you need to use the 'horrid tricks' from min() to get
>>>> a constant expression from constant inputs.
>>>
>>> This
>>>
>>> --- a/include/linux/log2.h~a
>>> +++ a/include/linux/log2.h
>>> @@ -41,11 +41,11 @@ int __ilog2_u64(u64 n)
>>> * *not* considered a power of two.
>>> * Return: true if @n is a power of 2, otherwise false.
>>> */
>>> -static inline __attribute__((const))
>>> -bool is_power_of_2(unsigned long n)
>>> -{
>>> - return (n != 0 && ((n & (n - 1)) == 0));
>>> -}
>>> +#define is_power_of_2(_n) \
>>> + ({ \
>>> + typeof(_n) n = (_n); \
>>> + n != 0 && ((n & (n - 1)) == 0); \
>>> + })
>>>
>>> /**
>>> * __roundup_pow_of_two() - round up to nearest power of two
>>> _
>>>
>>> worked for me in a simple test.
>>>
>>> --- a/fs/open.c~b
>>> +++ a/fs/open.c
>>> @@ -1564,3 +1564,10 @@ int stream_open(struct inode *inode, str
>>> }
>>>
>>> EXPORT_SYMBOL(stream_open);
>>> +
>>> +#include <linux/log2.h>
>>> +
>>> +int foo(void)
>>> +{
>>> + return is_power_of_2(43);
>>> +}
>>> _
>>>
>>>
>>> foo:
>>> # fs/open.c:1573: }
>>> xorl %eax, %eax #
>>> ret
>>>
>>>
>>> Is there some more tricky situation where it breaks?
>>
>> It doesn't work with BUILD_BUG_ON_ZERO().
>
> Like most programming problems, you just need another layer of
> indirection! The below works for me in all the cases I could think of
> (including __uint128_t).
>
>
> #define __IS_POWER_OF_2(n) (n != 0 && ((n & (n - 1)) == 0))
>
> #define _IS_POWER_OF_2(n, unique_n) \
> ({ \
> typeof(n) unique_n = (n); \
> __IS_POWER_OF_2(unique_n); \
> })
>
> #define is_power_of_2(n) \
> __builtin_choose_expr(__is_constexpr((n)), \
> __IS_POWER_OF_2((n)), \
> _IS_POWER_OF_2(n, __UNIQUE_ID(_n)))
>
>
> Although Jani's original might be easier to understand.
I dropped the ball since I couldn't make heads or tails what I should be
doing. And a year has passed. I'll note that the kernel has a number of
helpers for "is power of 2" for u64 and for constant expressions,
outside of log2.h.
I tried to make is_power_of_2() work for all the cases. Would it be more
palatable if I just added all the variants separately to log2.h?
- Leave is_power_of_2() as is
- Add is_power_of_2_u64() for 32-bit build compatible 64-bit checks
- Add IS_POWER_OF_2() macro for constant expressions
Please just tell me what to do and I'll do it.
BR,
Jani.
--
Jani Nikula, Intel