| Message ID | 20230330104243.2120761-1-jani.nikula@intel.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | log2: make is_power_of_2() more generic | expand |
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 <christian.koenig@amd.com> 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 <jani.nikula@intel.com> 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 <jani.nikula@intel.com> 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 <David.Laight@ACULAB.COM> 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
From: Andrew Morton > Sent: 30 March 2023 23:19 > > On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <David.Laight@ACULAB.COM> 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 <akpm@linux-foundation.org> wrote: > On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <David.Laight@ACULAB.COM> 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.
On 31/03/2023 09:31, Jani Nikula wrote: > On Thu, 30 Mar 2023, Andrew Morton <akpm@linux-foundation.org> wrote: >> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <David.Laight@ACULAB.COM> 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 <steven.price@arm.com> wrote: > On 31/03/2023 09:31, Jani Nikula wrote: >> On Thu, 30 Mar 2023, Andrew Morton <akpm@linux-foundation.org> wrote: >>> On Thu, 30 Mar 2023 21:53:03 +0000 David Laight <David.Laight@ACULAB.COM> 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.