diff mbox series

[11/12] tools: sync lib/find_bit implementation

Message ID 20210401003153.97325-12-yury.norov@gmail.com (mailing list archive)
State New, archived
Headers show
Series lib/find_bit: fast path for small bitmaps | expand

Commit Message

Yury Norov April 1, 2021, 12:31 a.m. UTC
Add fast paths to find_*_bit() functions as per kernel implementation.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
Acked-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 tools/include/asm-generic/bitops/find.h | 58 +++++++++++++++++++++++--
 tools/lib/find_bit.c                    |  4 +-
 2 files changed, 57 insertions(+), 5 deletions(-)

Comments

Tetsuo Handa May 10, 2021, 3:27 p.m. UTC | #1
Commit eaae7841ba83bb42 ("tools: sync lib/find_bit implementation") broke
build of 5.13-rc1 using gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3).

  DESCEND  objtool
  CC       /usr/src/linux/tools/objtool/exec-cmd.o
  CC       /usr/src/linux/tools/objtool/help.o
  CC       /usr/src/linux/tools/objtool/pager.o
  CC       /usr/src/linux/tools/objtool/parse-options.o
  CC       /usr/src/linux/tools/objtool/run-command.o
  CC       /usr/src/linux/tools/objtool/sigchain.o
  CC       /usr/src/linux/tools/objtool/subcmd-config.o
  LD       /usr/src/linux/tools/objtool/libsubcmd-in.o
  AR       /usr/src/linux/tools/objtool/libsubcmd.a
  CC       /usr/src/linux/tools/objtool/arch/x86/special.o
In file included from /usr/src/linux/tools/include/linux/kernel.h:8:0,
                 from /usr/src/linux/tools/include/linux/list.h:7,
                 from /usr/src/linux/tools/objtool/include/objtool/arch.h:10,
                 from /usr/src/linux/tools/objtool/include/objtool/check.h:11,
                 from /usr/src/linux/tools/objtool/include/objtool/special.h:10,
                 from arch/x86/special.c:4:
/usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_bit':
/usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
                     ^
/usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                              ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
   val = *addr & GENMASK(size - 1, offset);
                 ^
/usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                   ^
/usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
   ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
   val = *addr & GENMASK(size - 1, offset);
                 ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_and_bit':
/usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
                     ^
/usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                              ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
   val = *addr1 & *addr2 & GENMASK(size - 1, offset);
                           ^
/usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                   ^
/usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
   ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
   val = *addr1 & *addr2 & GENMASK(size - 1, offset);
                           ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_zero_bit':
/usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
                     ^
/usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                              ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
   val = *addr | ~GENMASK(size - 1, offset);
                  ^
/usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
 #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
                                                   ^
/usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
  (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
   ^
/usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
  (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
   ^
/usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
   val = *addr | ~GENMASK(size - 1, offset);
                  ^
make[5]: *** [/usr/src/linux/tools/objtool/arch/x86/special.o] Error 1
make[4]: *** [arch/x86] Error 2
make[3]: *** [/usr/src/linux/tools/objtool/objtool-in.o] Error 2
make[2]: *** [objtool] Error 2
make[1]: *** [tools/objtool] Error 2
make: *** [__sub-make] Error 2



Applying below diff seems to solve the build failure.
Do we need to use BUILD_BUG_ON_ZERO() here?

diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
index 7f475d59a097..0aba9294f29d 100644
--- a/tools/include/linux/bits.h
+++ b/tools/include/linux/bits.h
@@ -21,8 +21,7 @@
 #if !defined(__ASSEMBLY__)
 #include <linux/build_bug.h>
 #define GENMASK_INPUT_CHECK(h, l) \
-	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
-		__builtin_constant_p((l) > (h)), (l) > (h), 0)))
+	({ BUILD_BUG_ON(__builtin_constant_p((l) > (h)) && ((l) > (h))); 0; })
 #else
 /*
  * BUILD_BUG_ON_ZERO is not available in h files included from asm files,



Also, why the fast path of find_*_bit() functions does not check
__builtin_constant_p(offset) as well as small_const_nbits(size), for the fast
path fails to catch BUILD_BUG_ON_ZERO() when offset argument is not a constant.
Andy Shevchenko May 10, 2021, 3:44 p.m. UTC | #2
+Cc: Rikard

On Mon, May 10, 2021 at 6:31 PM Tetsuo Handa
<penguin-kernel@i-love.sakura.ne.jp> wrote:
>
> Commit eaae7841ba83bb42 ("tools: sync lib/find_bit implementation") broke
> build of 5.13-rc1 using gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3).
>
>   DESCEND  objtool
>   CC       /usr/src/linux/tools/objtool/exec-cmd.o
>   CC       /usr/src/linux/tools/objtool/help.o
>   CC       /usr/src/linux/tools/objtool/pager.o
>   CC       /usr/src/linux/tools/objtool/parse-options.o
>   CC       /usr/src/linux/tools/objtool/run-command.o
>   CC       /usr/src/linux/tools/objtool/sigchain.o
>   CC       /usr/src/linux/tools/objtool/subcmd-config.o
>   LD       /usr/src/linux/tools/objtool/libsubcmd-in.o
>   AR       /usr/src/linux/tools/objtool/libsubcmd.a
>   CC       /usr/src/linux/tools/objtool/arch/x86/special.o
> In file included from /usr/src/linux/tools/include/linux/kernel.h:8:0,
>                  from /usr/src/linux/tools/include/linux/list.h:7,
>                  from /usr/src/linux/tools/objtool/include/objtool/arch.h:10,
>                  from /usr/src/linux/tools/objtool/include/objtool/check.h:11,
>                  from /usr/src/linux/tools/objtool/include/objtool/special.h:10,
>                  from arch/x86/special.c:4:
> /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_bit':
> /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>                      ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                               ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
>    val = *addr & GENMASK(size - 1, offset);
>                  ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                    ^
> /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>    ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
>    val = *addr & GENMASK(size - 1, offset);
>                  ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_and_bit':
> /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>                      ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                               ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
>    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
>                            ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                    ^
> /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>    ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
>    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
>                            ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_zero_bit':
> /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>                      ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                               ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
>    val = *addr | ~GENMASK(size - 1, offset);
>                   ^
> /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
>  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
>                                                    ^
> /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
>   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>    ^
> /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
>   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
>    ^
> /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
>    val = *addr | ~GENMASK(size - 1, offset);
>                   ^
> make[5]: *** [/usr/src/linux/tools/objtool/arch/x86/special.o] Error 1
> make[4]: *** [arch/x86] Error 2
> make[3]: *** [/usr/src/linux/tools/objtool/objtool-in.o] Error 2
> make[2]: *** [objtool] Error 2
> make[1]: *** [tools/objtool] Error 2
> make: *** [__sub-make] Error 2
>
>
>
> Applying below diff seems to solve the build failure.

It will desynchronize this implementation with the mother's one (i.e.
in bits.h).

> Do we need to use BUILD_BUG_ON_ZERO() here?

Rikard?

>
> diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
> index 7f475d59a097..0aba9294f29d 100644
> --- a/tools/include/linux/bits.h
> +++ b/tools/include/linux/bits.h
> @@ -21,8 +21,7 @@
>  #if !defined(__ASSEMBLY__)
>  #include <linux/build_bug.h>
>  #define GENMASK_INPUT_CHECK(h, l) \
> -       (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> -               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> +       ({ BUILD_BUG_ON(__builtin_constant_p((l) > (h)) && ((l) > (h))); 0; })
>  #else
>  /*
>   * BUILD_BUG_ON_ZERO is not available in h files included from asm files,


> Also, why the fast path of find_*_bit() functions does not check
> __builtin_constant_p(offset) as well as small_const_nbits(size), for the fast
> path fails to catch BUILD_BUG_ON_ZERO() when offset argument is not a constant.

How would this help anything?

If you ask a bit from a bitmap behind the size, what do you expect to get?

And I'm a bit lost here, because I can't imagine the offset being
constant along with a size of bitmap. What do we want to achieve by
this? Any examples to better understand the case?
Yury Norov May 10, 2021, 5:21 p.m. UTC | #3
On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:
> +Cc: Rikard
> 
> On Mon, May 10, 2021 at 6:31 PM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
> >
> > Commit eaae7841ba83bb42 ("tools: sync lib/find_bit implementation") broke
> > build of 5.13-rc1 using gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3).
> >
> >   DESCEND  objtool
> >   CC       /usr/src/linux/tools/objtool/exec-cmd.o
> >   CC       /usr/src/linux/tools/objtool/help.o
> >   CC       /usr/src/linux/tools/objtool/pager.o
> >   CC       /usr/src/linux/tools/objtool/parse-options.o
> >   CC       /usr/src/linux/tools/objtool/run-command.o
> >   CC       /usr/src/linux/tools/objtool/sigchain.o
> >   CC       /usr/src/linux/tools/objtool/subcmd-config.o
> >   LD       /usr/src/linux/tools/objtool/libsubcmd-in.o
> >   AR       /usr/src/linux/tools/objtool/libsubcmd.a
> >   CC       /usr/src/linux/tools/objtool/arch/x86/special.o
> > In file included from /usr/src/linux/tools/include/linux/kernel.h:8:0,
> >                  from /usr/src/linux/tools/include/linux/list.h:7,
> >                  from /usr/src/linux/tools/objtool/include/objtool/arch.h:10,
> >                  from /usr/src/linux/tools/objtool/include/objtool/check.h:11,
> >                  from /usr/src/linux/tools/objtool/include/objtool/special.h:10,
> >                  from arch/x86/special.c:4:
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
> >    val = *addr & GENMASK(size - 1, offset);
> >                  ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
> >    val = *addr & GENMASK(size - 1, offset);
> >                  ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_and_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
> >    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
> >                            ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
> >    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
> >                            ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_zero_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
> >    val = *addr | ~GENMASK(size - 1, offset);
> >                   ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
> >    val = *addr | ~GENMASK(size - 1, offset);
> >                   ^
> > make[5]: *** [/usr/src/linux/tools/objtool/arch/x86/special.o] Error 1
> > make[4]: *** [arch/x86] Error 2
> > make[3]: *** [/usr/src/linux/tools/objtool/objtool-in.o] Error 2
> > make[2]: *** [objtool] Error 2
> > make[1]: *** [tools/objtool] Error 2
> > make: *** [__sub-make] Error 2
> >
> >
> > Applying below diff seems to solve the build failure.
> >
> It will desynchronize this implementation with the mother's one (i.e.
> in bits.h).
> 
> > Do we need to use BUILD_BUG_ON_ZERO() here?
> 
> Rikard?
>
> >
> > diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
> > index 7f475d59a097..0aba9294f29d 100644
> > --- a/tools/include/linux/bits.h
> > +++ b/tools/include/linux/bits.h
> > @@ -21,8 +21,7 @@
> >  #if !defined(__ASSEMBLY__)
> >  #include <linux/build_bug.h>
> >  #define GENMASK_INPUT_CHECK(h, l) \
> > -       (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> > -               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> > +       ({ BUILD_BUG_ON(__builtin_constant_p((l) > (h)) && ((l) > (h))); 0; })
> >  #else
> >  /*
> >   * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
 
As Andy said, we need to sync tools/GENMASK_INPUT_CHECK() with the
kernel version, and if I do this, I have many build failures:

https://pastebin.com/Fan1VLVF

Maybe in this case we should use __GENMASK() to bypass GENMASK_INPUT_CHECK()...
I'll check everything carefully this evening.
 
> > Also, why the fast path of find_*_bit() functions does not check
> > __builtin_constant_p(offset) as well as small_const_nbits(size), for the fast
> > path fails to catch BUILD_BUG_ON_ZERO() when offset argument is not a constant.
>
> How would this help anything?
> 
> If you ask a bit from a bitmap behind the size, what do you expect to get?
> 
> And I'm a bit lost here, because I can't imagine the offset being
> constant along with a size of bitmap. What do we want to achieve by
> this? Any examples to better understand the case?

If offset is constant, the existing fast path optimization would work
even better, without any modifications. (Not sure there's an example of
it in the existing codebase.) But even if the offset is not constant,
fast path works quite well - it saves ~1K of .text and improves on
performance:

https://lore.kernel.org/linux-m68k/20210321215457.588554-10-yury.norov@gmail.com/

We don't need to disable the optimization for non-constant offsets,
for sure. If asserts in GENMASK() break build, we should use __GENMASK().

Thanks,
Yury
Rikard Falkeborn May 10, 2021, 10:51 p.m. UTC | #4
On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:
> +Cc: Rikard
> 
> On Mon, May 10, 2021 at 6:31 PM Tetsuo Handa
> <penguin-kernel@i-love.sakura.ne.jp> wrote:
> >
> > Commit eaae7841ba83bb42 ("tools: sync lib/find_bit implementation") broke
> > build of 5.13-rc1 using gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3).
> >
> >   DESCEND  objtool
> >   CC       /usr/src/linux/tools/objtool/exec-cmd.o
> >   CC       /usr/src/linux/tools/objtool/help.o
> >   CC       /usr/src/linux/tools/objtool/pager.o
> >   CC       /usr/src/linux/tools/objtool/parse-options.o
> >   CC       /usr/src/linux/tools/objtool/run-command.o
> >   CC       /usr/src/linux/tools/objtool/sigchain.o
> >   CC       /usr/src/linux/tools/objtool/subcmd-config.o
> >   LD       /usr/src/linux/tools/objtool/libsubcmd-in.o
> >   AR       /usr/src/linux/tools/objtool/libsubcmd.a
> >   CC       /usr/src/linux/tools/objtool/arch/x86/special.o
> > In file included from /usr/src/linux/tools/include/linux/kernel.h:8:0,
> >                  from /usr/src/linux/tools/include/linux/list.h:7,
> >                  from /usr/src/linux/tools/objtool/include/objtool/arch.h:10,
> >                  from /usr/src/linux/tools/objtool/include/objtool/check.h:11,
> >                  from /usr/src/linux/tools/objtool/include/objtool/special.h:10,
> >                  from arch/x86/special.c:4:
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
> >    val = *addr & GENMASK(size - 1, offset);
> >                  ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:32:17: note: in expansion of macro 'GENMASK'
> >    val = *addr & GENMASK(size - 1, offset);
> >                  ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_and_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
> >    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
> >                            ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:62:27: note: in expansion of macro 'GENMASK'
> >    val = *addr1 & *addr2 & GENMASK(size - 1, offset);
> >                            ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h: In function 'find_next_zero_bit':
> > /usr/src/linux/tools/include/linux/bits.h:24:21: error: first argument to '__builtin_choose_expr' not a constant
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >                      ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:62: note: in definition of macro 'BUILD_BUG_ON_ZERO'
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                               ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
> >    val = *addr | ~GENMASK(size - 1, offset);
> >                   ^
> > /usr/src/linux/tools/include/linux/build_bug.h:16:51: error: bit-field '<anonymous>' width not an integer constant
> >  #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
> >                                                    ^
> > /usr/src/linux/tools/include/linux/bits.h:24:3: note: in expansion of macro 'BUILD_BUG_ON_ZERO'
> >   (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >    ^
> > /usr/src/linux/tools/include/linux/bits.h:38:3: note: in expansion of macro 'GENMASK_INPUT_CHECK'
> >   (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> >    ^
> > /usr/src/linux/tools/include/asm-generic/bitops/find.h:90:18: note: in expansion of macro 'GENMASK'
> >    val = *addr | ~GENMASK(size - 1, offset);
> >                   ^
> > make[5]: *** [/usr/src/linux/tools/objtool/arch/x86/special.o] Error 1
> > make[4]: *** [arch/x86] Error 2
> > make[3]: *** [/usr/src/linux/tools/objtool/objtool-in.o] Error 2
> > make[2]: *** [objtool] Error 2
> > make[1]: *** [tools/objtool] Error 2
> > make: *** [__sub-make] Error 2
> >
> >

Some background: when I added the input check to GENMASK there was
originally a check that disabled the input check if gcc versions earlier
than 4.9, since for old compilers, there was a bug [1] where for some
constructs, __builtin_constant_p() did not evaluate to a constant. This
was supposedly fixed in gcc 4.9, but apparently there are newer gcc
versions which suffer from this too.

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=19449

> >
> > Applying below diff seems to solve the build failure.
> 
> It will desynchronize this implementation with the mother's one (i.e.
> in bits.h).
> 
> > Do we need to use BUILD_BUG_ON_ZERO() here?
> 
> Rikard?

Yes, (as Yury pointed out), GENMASK is used in for example structure
initializers where  BUIlD_BUG() can not be used.
> 
> >
> > diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
> > index 7f475d59a097..0aba9294f29d 100644
> > --- a/tools/include/linux/bits.h
> > +++ b/tools/include/linux/bits.h
> > @@ -21,8 +21,7 @@
> >  #if !defined(__ASSEMBLY__)
> >  #include <linux/build_bug.h>
> >  #define GENMASK_INPUT_CHECK(h, l) \
> > -       (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> > -               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> > +       ({ BUILD_BUG_ON(__builtin_constant_p((l) > (h)) && ((l) > (h))); 0; })
> >  #else
> >  /*
> >   * BUILD_BUG_ON_ZERO is not available in h files included from asm files,

Does the following work for you? For simplicity, I copied__is_constexpr from
include/linux/minmax.h (which isn't available in tools/). A proper patch
would reuse __is_constexpr (possibly refactoring it to a separate
header since bits.h including minmax.h for that only seems smelly) and fix
bits.h in the kernel header as well, to keep the files in sync.

diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
index 7f475d59a097..7bc4c31a7df0 100644
--- a/tools/include/linux/bits.h
+++ b/tools/include/linux/bits.h
@@ -19,10 +19,13 @@
  * GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
  */
 #if !defined(__ASSEMBLY__)
+
+#define __is_constexpr(x) \
+       (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
 #include <linux/build_bug.h>
 #define GENMASK_INPUT_CHECK(h, l) \
        (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
-               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
+               __is_constexpr((l) > (h)), (l) > (h), 0)))
 #else
 /*
  * BUILD_BUG_ON_ZERO is not available in h files included from asm files,

I think any solution which results in using __GENMASK to avoid the input
check will just result in similar reports in the future.

Rikard
Andy Shevchenko May 11, 2021, 7:28 a.m. UTC | #5
On Tue, May 11, 2021 at 12:51:58AM +0200, Rikard Falkeborn wrote:
> On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:

...

> Does the following work for you? For simplicity, I copied__is_constexpr from
> include/linux/minmax.h (which isn't available in tools/). A proper patch
> would reuse __is_constexpr (possibly refactoring it to a separate
> header since bits.h including minmax.h for that only seems smelly)

I think we need to have it in something like compiler.h (top level). Under
'top level' I meant something with the function as of compiler.h but with
Linuxisms rather than compiler attributes or so.

Separate header for the (single) macro is too much...

> and fix
> bits.h in the kernel header as well, to keep the files in sync.

Right.
Rikard Falkeborn May 11, 2021, 10:36 a.m. UTC | #6
On Tue, May 11, 2021 at 10:28:50AM +0300, Andy Shevchenko wrote:
> On Tue, May 11, 2021 at 12:51:58AM +0200, Rikard Falkeborn wrote:
> > On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:
> 
> ...
> 
> > Does the following work for you? For simplicity, I copied__is_constexpr from
> > include/linux/minmax.h (which isn't available in tools/). A proper patch
> > would reuse __is_constexpr (possibly refactoring it to a separate
> > header since bits.h including minmax.h for that only seems smelly)
> 
> I think we need to have it in something like compiler.h (top level). Under
> 'top level' I meant something with the function as of compiler.h but with
> Linuxisms rather than compiler attributes or so.

Right. Will you send a patch, or do you want me to?

It would be good to get confirmation that __is_constexpr solves the
build failure.

> 
> Separate header for the (single) macro is too much...
> 

Agreed.

> > and fix
> > bits.h in the kernel header as well, to keep the files in sync.
> 
> Right.
> 
> -- 
> With Best Regards,
> Andy Shevchenko
> 
> 

With Best Regards,
Rikard
Tetsuo Handa May 11, 2021, 11:53 a.m. UTC | #7
On 2021/05/11 0:44, Andy Shevchenko wrote:
> And I'm a bit lost here, because I can't imagine the offset being
> constant along with a size of bitmap. What do we want to achieve by
> this? Any examples to better understand the case?

Because I feel that the GENMASK() macro cannot be evaluated without
both arguments being a constant.

The usage is

 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                            unsigned long offset)
 {
+       if (small_const_nbits(size)) {
+               unsigned long val;
+
+               if (unlikely(offset >= size))
+                       return size;
+
+               val = *addr & GENMASK(size - 1, offset);
+               return val ? __ffs(val) : size;
+       }
+
        return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
 }

where GENMASK() might be called even if "offset" is not a constant.

#define GENMASK(h, l) \
     (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))

#define __GENMASK(h, l) \
     (((~UL(0)) - (UL(1) << (l)) + 1) & \
       (~UL(0) >> (BITS_PER_LONG - 1 - (h))))

#define GENMASK_INPUT_CHECK(h, l) \
     (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
          __builtin_constant_p((l) > (h)), (l) > (h), 0)))

__GENMASK() does not need "h" and "l" being a constant.

Yes, small_const_nbits(size) in find_next_bit() can guarantee that "size" is a
constant and hence "h" argument in GENMASK_INPUT_CHECK() call is also a constant.
But nothing can guarantee that "offset" is a constant, and hence nothing can
guarantee that "l" argument in GENMASK_INPUT_CHECK() call is also a constant.

Then, how can (l) > (h) in __builtin_constant_p((l) > (h)) be evaluated at build time
if either l or h (i.e. "offset" and "size - 1" in find_next_bit()) lacks a guarantee of
being a constant?

But what a surprise,

On 2021/05/11 7:51, Rikard Falkeborn wrote:
> Does the following work for you? For simplicity, I copied__is_constexpr from
> include/linux/minmax.h (which isn't available in tools/). A proper patch
> would reuse __is_constexpr (possibly refactoring it to a separate
> header since bits.h including minmax.h for that only seems smelly) and fix
> bits.h in the kernel header as well, to keep the files in sync.

this works for me.

> 
> diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
> index 7f475d59a097..7bc4c31a7df0 100644
> --- a/tools/include/linux/bits.h
> +++ b/tools/include/linux/bits.h
> @@ -19,10 +19,13 @@
>   * GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
>   */
>  #if !defined(__ASSEMBLY__)
> +
> +#define __is_constexpr(x) \
> +       (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
>  #include <linux/build_bug.h>
>  #define GENMASK_INPUT_CHECK(h, l) \
>         (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> -               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> +               __is_constexpr((l) > (h)), (l) > (h), 0)))
>  #else
>  /*
>   * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
> 



On 2021/05/11 7:52, Yury Norov wrote:
> I tested the objtool build with the 8.4.0 and 7.5.0 compilers from
> ubuntu 21 distro, and it looks working. Can you please share more
> details about your system? 

Nothing special. A plain x86_64 CentOS 7.9 system with devtoolset-8.

$ /opt/rh/devtoolset-8/root/bin/gcc --version
gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3)
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ rpm -qi devtoolset-8-gcc
Name        : devtoolset-8-gcc
Version     : 8.3.1
Release     : 3.2.el7
Architecture: x86_64
Install Date: Wed Apr 22 07:58:16 2020
Group       : Development/Languages
Size        : 74838011
License     : GPLv3+ and GPLv3+ with exceptions and GPLv2+ with exceptions and LGPLv2+ and BSD
Signature   : RSA/SHA1, Thu Apr 16 19:44:43 2020, Key ID 4eb84e71f2ee9d55
Source RPM  : devtoolset-8-gcc-8.3.1-3.2.el7.src.rpm
Build Date  : Sat Mar 28 00:06:45 2020
Build Host  : c1be.rdu2.centos.org
Relocations : (not relocatable)
Packager    : CBS <cbs@centos.org>
Vendor      : CentOS
URL         : http://gcc.gnu.org
Summary     : GCC version 8
Description :
The devtoolset-8-gcc package contains the GNU Compiler Collection version 7.
Andy Shevchenko May 11, 2021, 12:17 p.m. UTC | #8
On Tue, May 11, 2021 at 1:36 PM Rikard Falkeborn
<rikard.falkeborn@gmail.com> wrote:
>
> On Tue, May 11, 2021 at 10:28:50AM +0300, Andy Shevchenko wrote:
> > On Tue, May 11, 2021 at 12:51:58AM +0200, Rikard Falkeborn wrote:
> > > On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:
> >
> > ...
> >
> > > Does the following work for you? For simplicity, I copied__is_constexpr from
> > > include/linux/minmax.h (which isn't available in tools/). A proper patch
> > > would reuse __is_constexpr (possibly refactoring it to a separate
> > > header since bits.h including minmax.h for that only seems smelly)
> >
> > I think we need to have it in something like compiler.h (top level). Under
> > 'top level' I meant something with the function as of compiler.h but with
> > Linuxisms rather than compiler attributes or so.
>
> Right. Will you send a patch, or do you want me to?

Please, go ahead!
I'm in a vacation mood (tomorrow it will start)

> It would be good to get confirmation that __is_constexpr solves the
> build failure.
Rikard Falkeborn May 11, 2021, 8:37 p.m. UTC | #9
On Tue, May 11, 2021 at 08:53:53PM +0900, Tetsuo Handa wrote:
> On 2021/05/11 0:44, Andy Shevchenko wrote:
> > And I'm a bit lost here, because I can't imagine the offset being
> > constant along with a size of bitmap. What do we want to achieve by
> > this? Any examples to better understand the case?
> 
> Because I feel that the GENMASK() macro cannot be evaluated without
> both arguments being a constant.
> 
> The usage is
> 
>  unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
>                             unsigned long offset)
>  {
> +       if (small_const_nbits(size)) {
> +               unsigned long val;
> +
> +               if (unlikely(offset >= size))
> +                       return size;
> +
> +               val = *addr & GENMASK(size - 1, offset);
> +               return val ? __ffs(val) : size;
> +       }
> +
>         return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
>  }
> 
> where GENMASK() might be called even if "offset" is not a constant.
> 
> #define GENMASK(h, l) \
>      (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
> 
> #define __GENMASK(h, l) \
>      (((~UL(0)) - (UL(1) << (l)) + 1) & \
>        (~UL(0) >> (BITS_PER_LONG - 1 - (h))))
> 
> #define GENMASK_INPUT_CHECK(h, l) \
>      (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>           __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> 
> __GENMASK() does not need "h" and "l" being a constant.
> 
> Yes, small_const_nbits(size) in find_next_bit() can guarantee that "size" is a
> constant and hence "h" argument in GENMASK_INPUT_CHECK() call is also a constant.
> But nothing can guarantee that "offset" is a constant, and hence nothing can
> guarantee that "l" argument in GENMASK_INPUT_CHECK() call is also a constant.
> 
> Then, how can (l) > (h) in __builtin_constant_p((l) > (h)) be evaluated at build time
> if either l or h (i.e. "offset" and "size - 1" in find_next_bit()) lacks a guarantee of
> being a constant?
> 

So the idea is that if (l > h) is constant, __builtin_constant_p should
evaluate that, and if it is not it should use zero instead as input to
__builtin_chose_expr(). This works with non-const inputs in many other
places in the kernel, but apparently in this case with a certain
compiler, it doesn't so I guess we need to work around it.

> But what a surprise,
> 
> On 2021/05/11 7:51, Rikard Falkeborn wrote:
> > Does the following work for you? For simplicity, I copied__is_constexpr from
> > include/linux/minmax.h (which isn't available in tools/). A proper patch
> > would reuse __is_constexpr (possibly refactoring it to a separate
> > header since bits.h including minmax.h for that only seems smelly) and fix
> > bits.h in the kernel header as well, to keep the files in sync.
> 
> this works for me.
> 

Great, thanks for testing!

I sent a patch for this here:
https://lore.kernel.org/lkml/20210511203716.117010-1-rikard.falkeborn@gmail.com/

Rikard

> > 
> > diff --git a/tools/include/linux/bits.h b/tools/include/linux/bits.h
> > index 7f475d59a097..7bc4c31a7df0 100644
> > --- a/tools/include/linux/bits.h
> > +++ b/tools/include/linux/bits.h
> > @@ -19,10 +19,13 @@
> >   * GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
> >   */
> >  #if !defined(__ASSEMBLY__)
> > +
> > +#define __is_constexpr(x) \
> > +       (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
> >  #include <linux/build_bug.h>
> >  #define GENMASK_INPUT_CHECK(h, l) \
> >         (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> > -               __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> > +               __is_constexpr((l) > (h)), (l) > (h), 0)))
> >  #else
> >  /*
> >   * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
> > 
> 
> 
> 
> On 2021/05/11 7:52, Yury Norov wrote:
> > I tested the objtool build with the 8.4.0 and 7.5.0 compilers from
> > ubuntu 21 distro, and it looks working. Can you please share more
> > details about your system? 
> 
> Nothing special. A plain x86_64 CentOS 7.9 system with devtoolset-8.
> 
> $ /opt/rh/devtoolset-8/root/bin/gcc --version
> gcc (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3)
> Copyright (C) 2018 Free Software Foundation, Inc.
> This is free software; see the source for copying conditions.  There is NO
> warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
> 
> $ rpm -qi devtoolset-8-gcc
> Name        : devtoolset-8-gcc
> Version     : 8.3.1
> Release     : 3.2.el7
> Architecture: x86_64
> Install Date: Wed Apr 22 07:58:16 2020
> Group       : Development/Languages
> Size        : 74838011
> License     : GPLv3+ and GPLv3+ with exceptions and GPLv2+ with exceptions and LGPLv2+ and BSD
> Signature   : RSA/SHA1, Thu Apr 16 19:44:43 2020, Key ID 4eb84e71f2ee9d55
> Source RPM  : devtoolset-8-gcc-8.3.1-3.2.el7.src.rpm
> Build Date  : Sat Mar 28 00:06:45 2020
> Build Host  : c1be.rdu2.centos.org
> Relocations : (not relocatable)
> Packager    : CBS <cbs@centos.org>
> Vendor      : CentOS
> URL         : http://gcc.gnu.org
> Summary     : GCC version 8
> Description :
> The devtoolset-8-gcc package contains the GNU Compiler Collection version 7.
>
Arnd Bergmann May 12, 2021, 7:48 a.m. UTC | #10
On Tue, May 11, 2021 at 10:39 PM Rikard Falkeborn
<rikard.falkeborn@gmail.com> wrote:
> On Tue, May 11, 2021 at 08:53:53PM +0900, Tetsuo Handa wrote:

> > #define GENMASK_INPUT_CHECK(h, l) \
> >      (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
> >           __builtin_constant_p((l) > (h)), (l) > (h), 0)))
> >
> > __GENMASK() does not need "h" and "l" being a constant.
> >
> > Yes, small_const_nbits(size) in find_next_bit() can guarantee that "size" is a
> > constant and hence "h" argument in GENMASK_INPUT_CHECK() call is also a constant.
> > But nothing can guarantee that "offset" is a constant, and hence nothing can
> > guarantee that "l" argument in GENMASK_INPUT_CHECK() call is also a constant.
> >
> > Then, how can (l) > (h) in __builtin_constant_p((l) > (h)) be evaluated at build time
> > if either l or h (i.e. "offset" and "size - 1" in find_next_bit()) lacks a guarantee of
> > being a constant?
> >
>
> So the idea is that if (l > h) is constant, __builtin_constant_p should
> evaluate that, and if it is not it should use zero instead as input to
> __builtin_chose_expr(). This works with non-const inputs in many other
> places in the kernel, but apparently in this case with a certain
> compiler, it doesn't so I guess we need to work around it.

I have a vague memory that __builtin_constant_p() inside of
__builtin_choose_expr()
always evaluates to false because of the order in which the compiler processes
those: If constant-folding only happens after __builtin_choose_expr(), then
__builtin_constant_p() has to be false.

        Arnd
Rasmus Villemoes May 12, 2021, 8:15 a.m. UTC | #11
On 12/05/2021 09.48, Arnd Bergmann wrote:
> On Tue, May 11, 2021 at 10:39 PM Rikard Falkeborn
> <rikard.falkeborn@gmail.com> wrote:
>> On Tue, May 11, 2021 at 08:53:53PM +0900, Tetsuo Handa wrote:
> 
>>> #define GENMASK_INPUT_CHECK(h, l) \
>>>      (BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
>>>           __builtin_constant_p((l) > (h)), (l) > (h), 0)))
>>>
>>> __GENMASK() does not need "h" and "l" being a constant.
>>>
>>> Yes, small_const_nbits(size) in find_next_bit() can guarantee that "size" is a
>>> constant and hence "h" argument in GENMASK_INPUT_CHECK() call is also a constant.
>>> But nothing can guarantee that "offset" is a constant, and hence nothing can
>>> guarantee that "l" argument in GENMASK_INPUT_CHECK() call is also a constant.
>>>
>>> Then, how can (l) > (h) in __builtin_constant_p((l) > (h)) be evaluated at build time
>>> if either l or h (i.e. "offset" and "size - 1" in find_next_bit()) lacks a guarantee of
>>> being a constant?
>>>
>>
>> So the idea is that if (l > h) is constant, __builtin_constant_p should
>> evaluate that, and if it is not it should use zero instead as input to
>> __builtin_chose_expr(). This works with non-const inputs in many other
>> places in the kernel, but apparently in this case with a certain
>> compiler, it doesn't so I guess we need to work around it.
> 
> I have a vague memory that __builtin_constant_p() inside of
> __builtin_choose_expr()
> always evaluates to false because of the order in which the compiler processes
> those: If constant-folding only happens after __builtin_choose_expr(), then
> __builtin_constant_p() has to be false.

It's more complicated than that. __builtin_constant_p on something which
is a bona-fide Integer Constant Expression (ICE) gets folded early to a
1. And then it turns out that such a __builtin_constant_p() that folds
early to a 1 can be "stronger" than a literal 1, in the sense that when
used as the controlling expression of a ?: with nonsense in the false
branch, the former is OK but the latter fails:

https://lore.kernel.org/lkml/c68a0f46-346c-70a0-a9b8-31747888f05f@rasmusvillemoes.dk/

Now what happens when the argument to __builtin_constant_p is not an ICE
is a lot more complicated. The argument _may_ be so obviously
non-constant that it can be folded early to a 0, hence still be suitable
as first argument to __b_c_e. But it is also possible that the compiler
leaves it unevaluated, in the "hope" that a later optimization stage
could prove the argument constant. And that's the case where __b_c_e
will then break, because that can't be left unevaluated for very long -
the very _type_ of the result depends on which branch is chosen.

tl;dr: there's no "order in which the compiler processes those", __b_c_p
can get evaluated (folded) early, before __b_c_e inspects it, or be left
for later stages.

Rasmus
Arnd Bergmann May 12, 2021, 8:33 a.m. UTC | #12
On Wed, May 12, 2021 at 10:16 AM Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
> It's more complicated than that. __builtin_constant_p on something which
> is a bona-fide Integer Constant Expression (ICE) gets folded early to a
> 1. And then it turns out that such a __builtin_constant_p() that folds
> early to a 1 can be "stronger" than a literal 1, in the sense that when
> used as the controlling expression of a ?: with nonsense in the false
> branch, the former is OK but the latter fails:
>
> https://lore.kernel.org/lkml/c68a0f46-346c-70a0-a9b8-31747888f05f@rasmusvillemoes.dk/
>
> Now what happens when the argument to __builtin_constant_p is not an ICE
> is a lot more complicated. The argument _may_ be so obviously
> non-constant that it can be folded early to a 0, hence still be suitable
> as first argument to __b_c_e. But it is also possible that the compiler
> leaves it unevaluated, in the "hope" that a later optimization stage
> could prove the argument constant. And that's the case where __b_c_e
> will then break, because that can't be left unevaluated for very long -
> the very _type_ of the result depends on which branch is chosen.
>
> tl;dr: there's no "order in which the compiler processes those", __b_c_p
> can get evaluated (folded) early, before __b_c_e inspects it, or be left
> for later stages.

Thanks for the detailed explanation. Checking the actual behavior of
a trivial example, I find that

int f(void)
{
    const int i = 1;
    return __builtin_choose_expr(__builtin_constant_p(i), 1, 2);
}

used to return '2' with gcc-7, which is what I remembered.
With gcc-8 and up as well as any version of clang, it returns '1' now:
https://godbolt.org/z/7eKjbMocb

I have also seen a couple of cases where __builtin_constant_p()
without a __builtin_choose_expr() ended up unexpectedly
returning true when gcc found a code path that it would be constant
(e.g. conditionally initializing a variable to one of two possible
ICEs), but then later turning that back into a non-constant
expression in a later optimization stage. There is probably also
a much more detailed explanation behind those.


        Arnd
diff mbox series

Patch

diff --git a/tools/include/asm-generic/bitops/find.h b/tools/include/asm-generic/bitops/find.h
index 9fe62d10b084..6481fd11012a 100644
--- a/tools/include/asm-generic/bitops/find.h
+++ b/tools/include/asm-generic/bitops/find.h
@@ -5,6 +5,9 @@ 
 extern unsigned long _find_next_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long nbits,
 		unsigned long start, unsigned long invert, unsigned long le);
+extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
+extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
+extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
 
 #ifndef find_next_bit
 /**
@@ -20,6 +23,16 @@  static inline
 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 			    unsigned long offset)
 {
+	if (small_const_nbits(size)) {
+		unsigned long val;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = *addr & GENMASK(size - 1, offset);
+		return val ? __ffs(val) : size;
+	}
+
 	return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
 }
 #endif
@@ -40,6 +53,16 @@  unsigned long find_next_and_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long size,
 		unsigned long offset)
 {
+	if (small_const_nbits(size)) {
+		unsigned long val;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = *addr1 & *addr2 & GENMASK(size - 1, offset);
+		return val ? __ffs(val) : size;
+	}
+
 	return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
 }
 #endif
@@ -58,6 +81,16 @@  static inline
 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 				 unsigned long offset)
 {
+	if (small_const_nbits(size)) {
+		unsigned long val;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = *addr | ~GENMASK(size - 1, offset);
+		return val == ~0UL ? size : ffz(val);
+	}
+
 	return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
 }
 #endif
@@ -72,8 +105,17 @@  unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  * Returns the bit number of the first set bit.
  * If no bits are set, returns @size.
  */
-extern unsigned long find_first_bit(const unsigned long *addr,
-				    unsigned long size);
+static inline
+unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val = *addr & GENMASK(size - 1, 0);
+
+		return val ? __ffs(val) : size;
+	}
+
+	return _find_first_bit(addr, size);
+}
 
 #endif /* find_first_bit */
 
@@ -87,7 +129,17 @@  extern unsigned long find_first_bit(const unsigned long *addr,
  * Returns the bit number of the first cleared bit.
  * If no bits are zero, returns @size.
  */
-unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size);
+static inline
+unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val = *addr | ~GENMASK(size - 1, 0);
+
+		return val == ~0UL ? size : ffz(val);
+	}
+
+	return _find_first_zero_bit(addr, size);
+}
 #endif
 
 #endif /*_TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_ */
diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c
index 589fd2f26f94..109aa7ffcf97 100644
--- a/tools/lib/find_bit.c
+++ b/tools/lib/find_bit.c
@@ -83,7 +83,7 @@  unsigned long _find_next_bit(const unsigned long *addr1,
 /*
  * Find the first set bit in a memory region.
  */
-unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
+unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 {
 	unsigned long idx;
 
@@ -100,7 +100,7 @@  unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 /*
  * Find the first cleared bit in a memory region.
  */
-unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
+unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
 {
 	unsigned long idx;