Skip to contentSkip to conversation

lib/find_bit: fast path for small bitmaps

PATCH Applied Yury Norov 8 participants 34 messages Apr 1, 2021 – May 12, 2021

Subsystems (6)
lore
Share & tools
lore

Yury Norov

author maintainer
#0 lore raw

v6 cover lib/find_bit: fast path for small bitmaps

Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.c we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.

find_*_bit() API lacks this functionality; but users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG.

v6 is mostly a resend. The only change comparing to v5 is a fix of small_const_nbits() synchronization patch.

v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: https://patchwork.kernel.org/project/linux-sh/cover/[email protected]/
v5: https://lore.kernel.org/linux-arch/[email protected]/T/
v6: - sync small_const_nbits() properly (patch 6).
- Rasmus' ack added.

Yury Norov (12):
tools: disable -Wno-type-limits
tools: bitmap: sync function declarations with the kernel
tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel
arch: rearrange headers inclusion order in asm/bitops for m68k and sh
lib: extend the scope of small_const_nbits() macro
tools: sync small_const_nbits() macro with the kernel
lib: inline _find_next_bit() wrappers
tools: sync find_next_bit implementation
lib: add fast path for find_next_*_bit()
lib: add fast path for find_first_*_bit() and find_last_bit()
tools: sync lib/find_bit implementation
MAINTAINERS: Add entry for the bitmap API

 MAINTAINERS                             |  16 ++++
 arch/m68k/include/asm/bitops.h          |   6 +-
 arch/sh/include/asm/bitops.h            |   5 +-
 include/asm-generic/bitops/find.h       | 108 +++++++++++++++++++++---
 include/asm-generic/bitops/le.h         |  38 ++++++++-
 include/asm-generic/bitsperlong.h       |  12 +++
 include/linux/bitmap.h                  |   8 --
 include/linux/bitops.h                  |  12 ---
 lib/find_bit.c                          |  68 ++-------------
 tools/include/asm-generic/bitops/find.h |  85 +++++++++++++++++--
 tools/include/asm-generic/bitsperlong.h |   3 +
 tools/include/linux/bitmap.h            |  18 ++--
 tools/lib/bitmap.c                      |   4 +-
 tools/lib/find_bit.c                    |  56 +++++-------
 tools/scripts/Makefile.include          |   1 +
 15 files changed, 284 insertions(+), 156 deletions(-)
Signature · 1 line
2.25.1
author maintainer
#1 lore raw

PATCH v6 1/12 tools: disable -Wno-type-limits

GENMASK(h, l) may be passed with unsigned types. In such case, type-limits warning is generated for example in case of GENMASK(h, 0).

---
 tools/scripts/Makefile.include | 1 +
 1 file changed, 1 insertion(+)
tools/scripts/Makefile.include +1 -0
index 84dbf61a7eca..15e99905cb7d 100644
@@ -38,6 +38,7 @@ EXTRA_WARNINGS += -Wswitch-enum
 EXTRA_WARNINGS += -Wundef
 EXTRA_WARNINGS += -Wwrite-strings
 EXTRA_WARNINGS += -Wformat
+EXTRA_WARNINGS += -Wno-type-limits
 
 CC_NO_CLANG := $(shell $(CC) -dM -E -x c /dev/null | grep -Fq "__clang__"; echo $$?)
 
Signature · 1 line
2.25.1
author maintainer
#2 lore raw

PATCH v6 2/12 tools: bitmap: sync function declarations with the kernel

In reply to Yury Norov

Some functions in tools/include/linux/bitmap.h declare nbits as int. In the kernel nbits is declared as unsigned int.

---
 tools/include/linux/bitmap.h | 8 ++++----
 tools/lib/bitmap.c           | 4 ++--
 2 files changed, 6 insertions(+), 6 deletions(-)
tools/include/linux/bitmap.h +4 -4
index 477a1cae513f..7cbd23e56d48 100644
@@ -30,7 +30,7 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len);
 #define small_const_nbits(nbits) \
 	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
 
-static inline void bitmap_zero(unsigned long *dst, int nbits)
+static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
 		*dst = 0UL;
@@ -66,7 +66,7 @@ static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
 	return find_first_zero_bit(src, nbits) == nbits;
 }
 
-static inline int bitmap_weight(const unsigned long *src, int nbits)
+static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
 		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
@@ -74,7 +74,7 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
 }
 
 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
-			     const unsigned long *src2, int nbits)
+			     const unsigned long *src2, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
 		*dst = *src1 | *src2;
@@ -141,7 +141,7 @@ static inline void bitmap_free(unsigned long *bitmap)
  * @buf: buffer to store output
  * @size: size of @buf
  */
-size_t bitmap_scnprintf(unsigned long *bitmap, int nbits,
+size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,
 			char *buf, size_t size);
 
 /**
tools/lib/bitmap.c +2 -2
index 5043747ef6c5..f4e914712b6f 100644
@@ -28,11 +28,11 @@ void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 		dst[k] = bitmap1[k] | bitmap2[k];
 }
 
-size_t bitmap_scnprintf(unsigned long *bitmap, int nbits,
+size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,
 			char *buf, size_t size)
 {
 	/* current bit is 'cur', most recently seen range is [rbot, rtop] */
-	int cur, rbot, rtop;
+	unsigned int cur, rbot, rtop;
 	bool first = true;
 	size_t ret = 0;
 
Signature · 1 line
2.25.1
author maintainer
#3 lore raw

PATCH v6 3/12 tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel

In reply to Yury Norov

Kernel version generates better code.

---
 tools/include/linux/bitmap.h | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)
tools/include/linux/bitmap.h +1 -6
index 7cbd23e56d48..4aabc23ec747 100644
@@ -20,12 +20,7 @@ int __bitmap_equal(const unsigned long *bitmap1,
 void bitmap_clear(unsigned long *map, unsigned int start, int len);
 
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
-
-#define BITMAP_LAST_WORD_MASK(nbits)					\
-(									\
-	((nbits) % BITS_PER_LONG) ?					\
-		(1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL		\
-)
+#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
 
 #define small_const_nbits(nbits) \
 	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
Signature · 1 line
2.25.1
author maintainer
#4 lore raw

PATCH v6 4/12 arch: rearrange headers inclusion order in asm/bitops for m68k and sh

In reply to Yury Norov

m68k and sh include bitmap/{find,le}.h prior to ffs/fls headers. New fast-path implementation in find.h requires ffs/fls. Reordering the headers inclusion sequence helps to prevent compile-time implicit function declaration error.

---
 arch/m68k/include/asm/bitops.h | 6 +++---
 arch/sh/include/asm/bitops.h   | 5 +++--
 2 files changed, 6 insertions(+), 5 deletions(-)
arch/m68k/include/asm/bitops.h +3 -3
index 10133a968c8e..7b414099e5fc 100644
@@ -440,8 +440,6 @@ static inline unsigned long ffz(unsigned long word)
 
 #endif
 
-#include <asm-generic/bitops/find.h>
-
 #ifdef __KERNEL__
 
 #if defined(CONFIG_CPU_HAS_NO_BITFIELDS)
@@ -525,10 +523,12 @@ static inline int __fls(int x)
 #define __clear_bit_unlock	clear_bit_unlock
 
 #include <asm-generic/bitops/ext2-atomic.h>
-#include <asm-generic/bitops/le.h>
 #include <asm-generic/bitops/fls64.h>
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
+#include <asm-generic/bitops/le.h>
 #endif /* __KERNEL__ */
 
+#include <asm-generic/bitops/find.h>
+
 #endif /* _M68K_BITOPS_H */
arch/sh/include/asm/bitops.h +3 -2
index 450b5854d7c6..3b6c7b5b7ec9 100644
@@ -58,15 +58,16 @@ static inline unsigned long __ffs(unsigned long word)
 	return result;
 }
 
-#include <asm-generic/bitops/find.h>
 #include <asm-generic/bitops/ffs.h>
 #include <asm-generic/bitops/hweight.h>
 #include <asm-generic/bitops/lock.h>
 #include <asm-generic/bitops/sched.h>
-#include <asm-generic/bitops/le.h>
 #include <asm-generic/bitops/ext2-atomic.h>
 #include <asm-generic/bitops/fls.h>
 #include <asm-generic/bitops/__fls.h>
 #include <asm-generic/bitops/fls64.h>
 
+#include <asm-generic/bitops/le.h>
+#include <asm-generic/bitops/find.h>
+
 #endif /* __ASM_SH_BITOPS_H */
Signature · 1 line
2.25.1
author maintainer
#5 lore raw

PATCH v6 5/12 lib: extend the scope of small_const_nbits() macro

In reply to Yury Norov

find_bit would also benefit from small_const_nbits() optimizations. The detailed comment is provided by Rasmus Villemoes.

---
 include/asm-generic/bitsperlong.h | 12 ++++++++++++
 include/linux/bitmap.h            |  8 --------
 2 files changed, 12 insertions(+), 8 deletions(-)
include/asm-generic/bitsperlong.h +12 -0
index 3905c1c93dc2..1023e2a4bd37 100644
@@ -23,4 +23,16 @@
 #define BITS_PER_LONG_LONG 64
 #endif
 
+/*
+ * small_const_nbits(n) is true precisely when it is known at compile-time
+ * that BITMAP_SIZE(n) is 1, i.e. 1 <= n <= BITS_PER_LONG. This allows
+ * various bit/bitmap APIs to provide a fast inline implementation. Bitmaps
+ * of size 0 are very rare, and a compile-time-known-size 0 is most likely
+ * a sign of error. They will be handled correctly by the bit/bitmap APIs,
+ * but using the out-of-line functions, so that the inline implementations
+ * can unconditionally dereference the pointer(s).
+ */
+#define small_const_nbits(nbits) \
+	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
+
 #endif /* __ASM_GENERIC_BITS_PER_LONG */
include/linux/bitmap.h +0 -8
index 2cb1d7cfe8f9..a36cfcec4e77 100644
@@ -230,14 +230,6 @@ int bitmap_print_to_pagebuf(bool list, char *buf,
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
 
-/*
- * The static inlines below do not handle constant nbits==0 correctly,
- * so make such users (should any ever turn up) call the out-of-line
- * versions.
- */
-#define small_const_nbits(nbits) \
-	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
-
 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
Signature · 1 line
2.25.1
Acked-by on v6 5/12
#6 lore raw

Re: [PATCH 05/12] lib: extend the scope of small_const_nbits() macro

Quoted 3 lines · Yury Norov

find_bit would also benefit from small_const_nbits() optimizations. The detailed comment is provided by Rasmus Villemoes.

Thanks, now it looks good!

Quoted 51 lines
---
 include/asm-generic/bitsperlong.h | 12 ++++++++++++
 include/linux/bitmap.h            |  8 --------
 2 files changed, 12 insertions(+), 8 deletions(-)
include/asm-generic/bitsperlong.h +12 -0
index 3905c1c93dc2..1023e2a4bd37 100644
@@ -23,4 +23,16 @@
 #define BITS_PER_LONG_LONG 64
 #endif
 
+/*
+ * small_const_nbits(n) is true precisely when it is known at compile-time
+ * that BITMAP_SIZE(n) is 1, i.e. 1 <= n <= BITS_PER_LONG. This allows
+ * various bit/bitmap APIs to provide a fast inline implementation. Bitmaps
+ * of size 0 are very rare, and a compile-time-known-size 0 is most likely
+ * a sign of error. They will be handled correctly by the bit/bitmap APIs,
+ * but using the out-of-line functions, so that the inline implementations
+ * can unconditionally dereference the pointer(s).
+ */
+#define small_const_nbits(nbits) \
+       (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
+
 #endif /* __ASM_GENERIC_BITS_PER_LONG */
include/linux/bitmap.h +0 -9
index 2cb1d7cfe8f9..a36cfcec4e77 100644
@@ -230,14 +230,6 @@ int bitmap_print_to_pagebuf(bool list, char *buf,
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
 
-/*
- * The static inlines below do not handle constant nbits==0 correctly,
- * so make such users (should any ever turn up) call the out-of-line
- * versions.
- */
-#define small_const_nbits(nbits) \
-       (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
-
 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
        unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
--

2.25.1

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#7 lore raw

PATCH v6 6/12 tools: sync small_const_nbits() macro with the kernel

In reply to Yury Norov

Sync implementation with the kernel and move the macro from tools/include/linux/bitmap.h to tools/include/asm-generic/bitsperlong.h

---
 tools/include/asm-generic/bitsperlong.h | 3 +++
 tools/include/linux/bitmap.h            | 3 ---
 2 files changed, 3 insertions(+), 3 deletions(-)
tools/include/asm-generic/bitsperlong.h +3 -0
index 8f2283052333..2093d56ddd11 100644
@@ -18,4 +18,7 @@
 #define BITS_PER_LONG_LONG 64
 #endif
 
+#define small_const_nbits(nbits) \
+	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
+
 #endif /* __ASM_GENERIC_BITS_PER_LONG */
tools/include/linux/bitmap.h +0 -3
index 4aabc23ec747..330dbf7509cc 100644
@@ -22,9 +22,6 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len);
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
 
-#define small_const_nbits(nbits) \
-	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
-
 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
Signature · 1 line
2.25.1
author maintainer
#8 lore raw

PATCH v6 7/12 lib: inline _find_next_bit() wrappers

In reply to Yury Norov

lib/find_bit.c declares five single-line wrappers for _find_next_bit(). We may turn those wrappers to inline functions. It eliminates unneeded function calls and opens room for compile-time optimizations.

---
 include/asm-generic/bitops/find.h | 28 ++++++++++++----
 include/asm-generic/bitops/le.h   | 17 +++++++---
 lib/find_bit.c                    | 56 ++-----------------------------
 3 files changed, 37 insertions(+), 64 deletions(-)
include/asm-generic/bitops/find.h +22 -6
index 9fdf21302fdf..7ad70dab8e93 100644
@@ -2,6 +2,10 @@
 #ifndef _ASM_GENERIC_BITOPS_FIND_H_
 #define _ASM_GENERIC_BITOPS_FIND_H_
 
+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);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
@@ -12,8 +16,12 @@
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
-		size, unsigned long offset);
+static inline
+unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+			    unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_and_bit
@@ -27,9 +35,13 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_and_bit(const unsigned long *addr1,
+static inline
+unsigned long find_next_and_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long size,
-		unsigned long offset);
+		unsigned long offset)
+{
+	return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_zero_bit
@@ -42,8 +54,12 @@ extern unsigned long find_next_and_bit(const unsigned long *addr1,
  * Returns the bit number of the next zero bit
  * If no bits are zero, returns @size.
  */
-extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned
-		long size, unsigned long offset);
+static inline
+unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+				 unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
+}
 #endif
 
 #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
include/asm-generic/bitops/le.h +13 -4
index 188d3eba3ace..21305f6cea0b 100644
@@ -2,6 +2,7 @@
 #ifndef _ASM_GENERIC_BITOPS_LE_H_
 #define _ASM_GENERIC_BITOPS_LE_H_
 
+#include <asm-generic/bitops/find.h>
 #include <asm/types.h>
 #include <asm/byteorder.h>
 
@@ -32,13 +33,21 @@ static inline unsigned long find_first_zero_bit_le(const void *addr,
 #define BITOP_LE_SWIZZLE	((BITS_PER_LONG-1) & ~0x7)
 
 #ifndef find_next_zero_bit_le
-extern unsigned long find_next_zero_bit_le(const void *addr,
-		unsigned long size, unsigned long offset);
+static inline
+unsigned long find_next_zero_bit_le(const void *addr, unsigned
+		long size, unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
+}
 #endif
 
 #ifndef find_next_bit_le
-extern unsigned long find_next_bit_le(const void *addr,
-		unsigned long size, unsigned long offset);
+static inline
+unsigned long find_next_bit_le(const void *addr, unsigned
+		long size, unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
+}
 #endif
 
 #ifndef find_first_zero_bit_le
lib/find_bit.c +2 -54

74 lines not on this page · raw message

Signature · 1 line
2.25.1
Acked-by on v6 7/12
#9 lore raw

Re: [PATCH 07/12] lib: inline _find_next_bit() wrappers

Quoted 4 lines · Yury Norov

lib/find_bit.c declares five single-line wrappers for _find_next_bit(). We may turn those wrappers to inline functions. It eliminates unneeded function calls and opens room for compile-time optimizations.

Quoted 191 lines
---
 include/asm-generic/bitops/find.h | 28 ++++++++++++----
 include/asm-generic/bitops/le.h   | 17 +++++++---
 lib/find_bit.c                    | 56 ++-----------------------------
 3 files changed, 37 insertions(+), 64 deletions(-)
include/asm-generic/bitops/find.h +22 -6
index 9fdf21302fdf..7ad70dab8e93 100644
@@ -2,6 +2,10 @@
 #ifndef _ASM_GENERIC_BITOPS_FIND_H_
 #define _ASM_GENERIC_BITOPS_FIND_H_
 
+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);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
@@ -12,8 +16,12 @@
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
-               size, unsigned long offset);
+static inline
+unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+                           unsigned long offset)
+{
+       return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_and_bit
@@ -27,9 +35,13 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_and_bit(const unsigned long *addr1,
+static inline
+unsigned long find_next_and_bit(const unsigned long *addr1,
                const unsigned long *addr2, unsigned long size,
-               unsigned long offset);
+               unsigned long offset)
+{
+       return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_zero_bit
@@ -42,8 +54,12 @@ extern unsigned long find_next_and_bit(const unsigned long *addr1,
  * Returns the bit number of the next zero bit
  * If no bits are zero, returns @size.
  */
-extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned
-               long size, unsigned long offset);
+static inline
+unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+                                unsigned long offset)
+{
+       return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
+}
 #endif
 
 #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
include/asm-generic/bitops/le.h +13 -4
index 188d3eba3ace..21305f6cea0b 100644
@@ -2,6 +2,7 @@
 #ifndef _ASM_GENERIC_BITOPS_LE_H_
 #define _ASM_GENERIC_BITOPS_LE_H_
 
+#include <asm-generic/bitops/find.h>
 #include <asm/types.h>
 #include <asm/byteorder.h>
 
@@ -32,13 +33,21 @@ static inline unsigned long find_first_zero_bit_le(const void *addr,
 #define BITOP_LE_SWIZZLE       ((BITS_PER_LONG-1) & ~0x7)
 
 #ifndef find_next_zero_bit_le
-extern unsigned long find_next_zero_bit_le(const void *addr,
-               unsigned long size, unsigned long offset);
+static inline
+unsigned long find_next_zero_bit_le(const void *addr, unsigned
+               long size, unsigned long offset)
+{
+       return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
+}
 #endif
 
 #ifndef find_next_bit_le
-extern unsigned long find_next_bit_le(const void *addr,
-               unsigned long size, unsigned long offset);
+static inline
+unsigned long find_next_bit_le(const void *addr, unsigned
+               long size, unsigned long offset)
+{
+       return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
+}
 #endif
 
 #ifndef find_first_zero_bit_le
lib/find_bit.c +2 -55
index f67f86fd2f62..b03a101367f8 100644
@@ -29,7 +29,7 @@
  *    searching it for one bits.
  *  - The optional "addr2", which is anded with "addr1" if present.
  */
-static unsigned long _find_next_bit(const unsigned long *addr1,
+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)
 {
@@ -68,37 +68,7 @@ static unsigned long _find_next_bit(const unsigned long *addr1,
 
        return min(start + __ffs(tmp), nbits);
 }
-#endif
-
-#ifndef find_next_bit
-/*
- * Find the next set bit in a memory region.
- */
-unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
-                           unsigned long offset)
-{
-       return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
-}
-EXPORT_SYMBOL(find_next_bit);
-#endif
-
-#ifndef find_next_zero_bit
-unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
-                                unsigned long offset)
-{
-       return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
-}
-EXPORT_SYMBOL(find_next_zero_bit);
-#endif
-
-#if !defined(find_next_and_bit)
-unsigned long find_next_and_bit(const unsigned long *addr1,
-               const unsigned long *addr2, unsigned long size,
-               unsigned long offset)
-{
-       return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
-}
-EXPORT_SYMBOL(find_next_and_bit);
+EXPORT_SYMBOL(_find_next_bit);
 #endif
 
 #ifndef find_first_bit
@@ -157,28 +127,6 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 EXPORT_SYMBOL(find_last_bit);
 #endif
 
-#ifdef __BIG_ENDIAN
-
-#ifndef find_next_zero_bit_le
-unsigned long find_next_zero_bit_le(const void *addr, unsigned
-               long size, unsigned long offset)
-{
-       return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
-}
-EXPORT_SYMBOL(find_next_zero_bit_le);
-#endif
-
-#ifndef find_next_bit_le
-unsigned long find_next_bit_le(const void *addr, unsigned
-               long size, unsigned long offset)
-{
-       return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
-}
-EXPORT_SYMBOL(find_next_bit_le);
-#endif
-
-#endif /* __BIG_ENDIAN */
-
 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
                               unsigned long size, unsigned long offset)
 {
--

2.25.1

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#10 lore raw

PATCH v6 8/12 tools: sync find_next_bit implementation

In reply to Yury Norov

Sync the implementation with recent kernel changes.

---
 tools/include/asm-generic/bitops/find.h | 27 ++++++++++---
 tools/lib/find_bit.c                    | 52 ++++++++++---------------
 2 files changed, 42 insertions(+), 37 deletions(-)
tools/include/asm-generic/bitops/find.h +21 -6
index 16ed1982cb34..9fe62d10b084 100644
@@ -2,6 +2,10 @@
 #ifndef _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_
 #define _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_
 
+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);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
@@ -12,8 +16,12 @@
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
-		size, unsigned long offset);
+static inline
+unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+			    unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_and_bit
@@ -27,13 +35,16 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long
  * Returns the bit number for the next set bit
  * If no bits are set, returns @size.
  */
-extern unsigned long find_next_and_bit(const unsigned long *addr1,
+static inline
+unsigned long find_next_and_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long size,
-		unsigned long offset);
+		unsigned long offset)
+{
+	return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
+}
 #endif
 
 #ifndef find_next_zero_bit
-
 /**
  * find_next_zero_bit - find the next cleared bit in a memory region
  * @addr: The address to base the search on
@@ -43,8 +54,12 @@ extern unsigned long find_next_and_bit(const unsigned long *addr1,
  * Returns the bit number of the next zero bit
  * If no bits are zero, returns @size.
  */
+static inline
 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
-				 unsigned long offset);
+				 unsigned long offset)
+{
+	return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
+}
 #endif
 
 #ifndef find_first_bit
tools/lib/find_bit.c +21 -31

77 lines not on this page · raw message

Signature · 1 line
2.25.1
author maintainer
#11 lore raw

PATCH v6 9/12 lib: add fast path for find_next_*_bit()

In reply to Yury Norov

Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word inline. In the very best case, the compiler may replace a function call with a few instructions.

This is the quite typical find_next_bit() user:

	unsigned int cpumask_next(int n, const struct cpumask *srcp)
	{
		/* -1 is a legal arg here. */
		if (n != -1)
			cpumask_check(n);
		return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1);
	}
	EXPORT_SYMBOL(cpumask_next);

Currently, on ARM64 the generated code looks like this:

	0000000000000000 <cpumask_next>:
	   0:   a9bf7bfd        stp     x29, x30, [sp, #-16]!
	   4:   11000402        add     w2, w0, #0x1
	   8:   aa0103e0        mov     x0, x1
	   c:   d2800401        mov     x1, #0x40                       // #64
	  10:   910003fd        mov     x29, sp
	  14:   93407c42        sxtw    x2, w2
	  18:   94000000        bl      0 <find_next_bit>
	  1c:   a8c17bfd        ldp     x29, x30, [sp], #16
	  20:   d65f03c0        ret
	  24:   d503201f        nop

After applying this patch:

	0000000000000140 <cpumask_next>:
	 140:   11000400        add     w0, w0, #0x1
	 144:   93407c00        sxtw    x0, w0
	 148:   f100fc1f        cmp     x0, #0x3f
	 14c:   54000168        b.hi    178 <cpumask_next+0x38>  // b.pmore
	 150:   f9400023        ldr     x3, [x1]
	 154:   92800001        mov     x1, #0xffffffffffffffff         // #-1
	 158:   9ac02020        lsl     x0, x1, x0
	 15c:   52800802        mov     w2, #0x40                       // #64
	 160:   8a030001        and     x1, x0, x3
	 164:   dac00020        rbit    x0, x1
	 168:   f100003f        cmp     x1, #0x0
	 16c:   dac01000        clz     x0, x0
	 170:   1a800040        csel    w0, w2, w0, eq  // eq = none
	 174:   d65f03c0        ret
	 178:   52800800        mov     w0, #0x40                       // #64
	 17c:   d65f03c0        ret

find_next_bit() call is replaced with 6 instructions. find_next_bit() itself is 41 instructions plus function call overhead.

Despite inlining, the scripts/bloat-o-meter report smaller .text size after applying the series:

	add/remove: 11/9 grow/shrink: 233/176 up/down: 5780/-6768 (-988)
---
 include/asm-generic/bitops/find.h | 30 ++++++++++++++++++++++++++++++
 include/asm-generic/bitops/le.h   | 21 +++++++++++++++++++++
 2 files changed, 51 insertions(+)
include/asm-generic/bitops/find.h +30 -0
index 7ad70dab8e93..4148c74a1e4d 100644
@@ -20,6 +20,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 +50,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 +78,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
include/asm-generic/bitops/le.h +21 -0
index 21305f6cea0b..5a28629cbf4d 100644
@@ -5,6 +5,7 @@
 #include <asm-generic/bitops/find.h>
 #include <asm/types.h>
 #include <asm/byteorder.h>
+#include <linux/swab.h>
 
 #if defined(__LITTLE_ENDIAN)
 
@@ -37,6 +38,16 @@ static inline
 unsigned long find_next_zero_bit_le(const void *addr, unsigned
 		long size, unsigned long offset)
 {
+	if (small_const_nbits(size)) {
+		unsigned long val = *(const unsigned long *)addr;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = swab(val) | ~GENMASK(size - 1, offset);
+		return val == ~0UL ? size : ffz(val);
+	}
+
 	return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
 }
 #endif
@@ -46,6 +57,16 @@ static inline
 unsigned long find_next_bit_le(const void *addr, unsigned
 		long size, unsigned long offset)
 {
+	if (small_const_nbits(size)) {
+		unsigned long val = *(const unsigned long *)addr;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = swab(val) & GENMASK(size - 1, offset);
+		return val ? __ffs(val) : size;
+	}
+
 	return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
 }
 #endif
Signature · 1 line
2.25.1
Acked-by on v6 9/12
#12 lore raw

Re: [PATCH 09/12] lib: add fast path for find_next_*_bit()

Quoted 49 lines · Yury Norov

Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word inline. In the very best case, the compiler may replace a function call with a few instructions.

This is the quite typical find_next_bit() user:

        unsigned int cpumask_next(int n, const struct cpumask *srcp)
        {
                /* -1 is a legal arg here. */
                if (n != -1)
                        cpumask_check(n);
                return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1);
        }
        EXPORT_SYMBOL(cpumask_next);

Currently, on ARM64 the generated code looks like this:

        0000000000000000 <cpumask_next>:
           0:   a9bf7bfd        stp     x29, x30, [sp, #-16]!
           4:   11000402        add     w2, w0, #0x1
           8:   aa0103e0        mov     x0, x1
           c:   d2800401        mov     x1, #0x40                       // #64
          10:   910003fd        mov     x29, sp
          14:   93407c42        sxtw    x2, w2
          18:   94000000        bl      0 <find_next_bit>
          1c:   a8c17bfd        ldp     x29, x30, [sp], #16
          20:   d65f03c0        ret
          24:   d503201f        nop

After applying this patch:

        0000000000000140 <cpumask_next>:
         140:   11000400        add     w0, w0, #0x1
         144:   93407c00        sxtw    x0, w0
         148:   f100fc1f        cmp     x0, #0x3f
         14c:   54000168        b.hi    178 <cpumask_next+0x38>  // b.pmore
         150:   f9400023        ldr     x3, [x1]
         154:   92800001        mov     x1, #0xffffffffffffffff         // #-1
         158:   9ac02020        lsl     x0, x1, x0
         15c:   52800802        mov     w2, #0x40                       // #64
         160:   8a030001        and     x1, x0, x3
         164:   dac00020        rbit    x0, x1
         168:   f100003f        cmp     x1, #0x0
         16c:   dac01000        clz     x0, x0
         170:   1a800040        csel    w0, w2, w0, eq  // eq = none
         174:   d65f03c0        ret
         178:   52800800        mov     w0, #0x40                       // #64
         17c:   d65f03c0        ret
Quoted 6 lines

find_next_bit() call is replaced with 6 instructions. find_next_bit() itself is 41 instructions plus function call overhead.

Despite inlining, the scripts/bloat-o-meter report smaller .text size after applying the series:

        add/remove: 11/9 grow/shrink: 233/176 up/down: 5780/-6768 (-988)
Quoted 111 lines
---
 include/asm-generic/bitops/find.h | 30 ++++++++++++++++++++++++++++++
 include/asm-generic/bitops/le.h   | 21 +++++++++++++++++++++
 2 files changed, 51 insertions(+)
include/asm-generic/bitops/find.h +30 -0
index 7ad70dab8e93..4148c74a1e4d 100644
@@ -20,6 +20,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 +50,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 +78,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
include/asm-generic/bitops/le.h +21 -1
index 21305f6cea0b..5a28629cbf4d 100644
@@ -5,6 +5,7 @@
 #include <asm-generic/bitops/find.h>
 #include <asm/types.h>
 #include <asm/byteorder.h>
+#include <linux/swab.h>
 
 #if defined(__LITTLE_ENDIAN)
 
@@ -37,6 +38,16 @@ static inline
 unsigned long find_next_zero_bit_le(const void *addr, unsigned
                long size, unsigned long offset)
 {
+       if (small_const_nbits(size)) {
+               unsigned long val = *(const unsigned long *)addr;
+
+               if (unlikely(offset >= size))
+                       return size;
+
+               val = swab(val) | ~GENMASK(size - 1, offset);
+               return val == ~0UL ? size : ffz(val);
+       }
+
        return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
 }
 #endif
@@ -46,6 +57,16 @@ static inline
 unsigned long find_next_bit_le(const void *addr, unsigned
                long size, unsigned long offset)
 {
+       if (small_const_nbits(size)) {
+               unsigned long val = *(const unsigned long *)addr;
+
+               if (unlikely(offset >= size))
+                       return size;
+
+               val = swab(val) & GENMASK(size - 1, offset);
+               return val ? __ffs(val) : size;
+       }
+
        return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
 }
 #endif
--

2.25.1

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#13 lore raw

PATCH v6 10/12 lib: add fast path for find_first_*_bit() and find_last_bit()

In reply to Yury Norov

Similarly to bitmap functions, users would benefit if we'll handle a case of small-size bitmaps that fit into a single word.

While here, move the find_last_bit() declaration to bitops/find.h where other find_*_bit() functions sit.

---
 include/asm-generic/bitops/find.h | 50 ++++++++++++++++++++++++++++---
 include/linux/bitops.h            | 12 --------
 lib/find_bit.c                    | 12 ++++----
 3 files changed, 52 insertions(+), 22 deletions(-)
include/asm-generic/bitops/find.h +46 -4
index 4148c74a1e4d..0d132ee2a291 100644
@@ -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
 /**
@@ -102,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);
+}
 
 /**
  * find_first_zero_bit - find the first cleared bit in a memory region
@@ -113,8 +125,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.
  */
-extern 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);
+}
 #else /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
 #ifndef find_first_bit
@@ -126,6 +147,27 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
 
 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
+#ifndef find_last_bit
+/**
+ * find_last_bit - find the last set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The number of bits to search
+ *
+ * Returns the bit number of the last set bit, or size.
+ */
+static inline
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val = *addr & GENMASK(size - 1, 0);
+
+		return val ? __fls(val) : size;
+	}
+
+	return _find_last_bit(addr, size);
+}
+#endif
+
 /**
  * find_next_clump8 - find next 8-bit clump with set bits in a memory region
  * @clump: location to store copy of found clump
include/linux/bitops.h +0 -12
index a5a48303b0f1..26bf15e6cd35 100644
@@ -286,17 +286,5 @@ static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
 })
 #endif
 
-#ifndef find_last_bit
-/**
- * find_last_bit - find the last set bit in a memory region
- * @addr: The address to start the search at
- * @size: The number of bits to search
- *
- * Returns the bit number of the last set bit, or size.
- */
-extern unsigned long find_last_bit(const unsigned long *addr,
-				   unsigned long size);
-#endif
-
 #endif /* __KERNEL__ */
 #endif
lib/find_bit.c +6 -6
index b03a101367f8..0f8e2e369b1d 100644
@@ -75,7 +75,7 @@ EXPORT_SYMBOL(_find_next_bit);
 /*
  * 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;
 
@@ -86,14 +86,14 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 
 	return size;
 }
-EXPORT_SYMBOL(find_first_bit);
+EXPORT_SYMBOL(_find_first_bit);
 #endif
 
 #ifndef find_first_zero_bit
 /*
  * 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;
 
@@ -104,11 +104,11 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 
 	return size;
 }
-EXPORT_SYMBOL(find_first_zero_bit);
+EXPORT_SYMBOL(_find_first_zero_bit);
 #endif
 
 #ifndef find_last_bit
-unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
 {
 	if (size) {
 		unsigned long val = BITMAP_LAST_WORD_MASK(size);
@@ -124,7 +124,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 	}
 	return size;
 }
-EXPORT_SYMBOL(find_last_bit);
+EXPORT_SYMBOL(_find_last_bit);
 #endif
 
 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
Signature · 1 line
2.25.1
#14 lore raw

Re: [PATCH 10/12] lib: add fast path for find_first_*_bit() and find_last_bit()

Thank you for the patch! Yet something to improve:

Hi Yury,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on asm-generic/master]
[also build test ERROR on linux/master m68k/for-next linus/master hnaz-linux-mm/master v5.12-rc5 next-20210331] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/0day-ci/linux/commits/Yury-Norov/lib-find_bit-fast-path-for-small-bitmaps/20210401-083548
base:   https://git.kernel.org/pub/scm/linux/kernel/git/arnd/asm-generic.git master
config: h8300-randconfig-r023-20210330 (attached as .config)
compiler: h8300-linux-gcc (GCC) 9.3.0

reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/3e907bda2d6a980c07eae54c78a1162e1c94cda1
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Yury-Norov/lib-find_bit-fast-path-for-small-bitmaps/20210401-083548 git checkout 3e907bda2d6a980c07eae54c78a1162e1c94cda1
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=h8300

If you fix the issue, kindly add following tag as appropriate

All errors (new ones prefixed by >>):

In file included from arch/h8300/include/asm/bitops.h:167,

                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h: In function 'find_last_bit':
>> include/asm-generic/bitops/find.h:164:16: error: implicit declaration of function '__fls'; did you mean '__ffs'? [-Werror=implicit-function-declaration]
     164 |   return val ? __fls(val) : size;
         |                ^~~~~
         |                __ffs
   In file included from arch/h8300/include/asm/bitops.h:177,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/__fls.h: At top level:
>> include/asm-generic/bitops/__fls.h:13:38: error: conflicting types for '__fls'
      13 | static __always_inline unsigned long __fls(unsigned long word)
         |                                      ^~~~~
   In file included from arch/h8300/include/asm/bitops.h:167,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h:164:16: note: previous implicit declaration of '__fls' was here
     164 |   return val ? __fls(val) : size;
         |                ^~~~~
   cc1: some warnings being treated as errors
--
   In file included from arch/h8300/include/asm/bitops.h:167,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h: In function 'find_last_bit':
>> include/asm-generic/bitops/find.h:164:16: error: implicit declaration of function '__fls'; did you mean '__ffs'? [-Werror=implicit-function-declaration]
     164 |   return val ? __fls(val) : size;
         |                ^~~~~
         |                __ffs
   In file included from arch/h8300/include/asm/bitops.h:177,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/__fls.h: At top level:
>> include/asm-generic/bitops/__fls.h:13:38: error: conflicting types for '__fls'
      13 | static __always_inline unsigned long __fls(unsigned long word)
         |                                      ^~~~~
   In file included from arch/h8300/include/asm/bitops.h:167,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h:164:16: note: previous implicit declaration of '__fls' was here
     164 |   return val ? __fls(val) : size;
         |                ^~~~~

cc1: some warnings being treated as errors
make[2]: *** [scripts/Makefile.build:117: scripts/mod/devicetable-offsets.s] Error 1 make[2]: Target '__build' not remade because of errors.
make[1]: *** [Makefile:1205: prepare0] Error 2
make[1]: Target 'modules_prepare' not remade because of errors.
make: *** [Makefile:185: __sub-make] Error 2
make: Target 'modules_prepare' not remade because of errors.
--
In file included from arch/h8300/include/asm/bitops.h:167,

                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h: In function 'find_last_bit':
>> include/asm-generic/bitops/find.h:164:16: error: implicit declaration of function '__fls'; did you mean '__ffs'? [-Werror=implicit-function-declaration]
     164 |   return val ? __fls(val) : size;
         |                ^~~~~
         |                __ffs
   In file included from arch/h8300/include/asm/bitops.h:177,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/__fls.h: At top level:
>> include/asm-generic/bitops/__fls.h:13:38: error: conflicting types for '__fls'
      13 | static __always_inline unsigned long __fls(unsigned long word)
         |                                      ^~~~~
   In file included from arch/h8300/include/asm/bitops.h:167,
                    from include/linux/bitops.h:32,
                    from include/linux/log2.h:12,
                    from include/asm-generic/getorder.h:8,
                    from include/asm-generic/page.h:99,
                    from arch/h8300/include/asm/page.h:5,
                    from arch/h8300/include/asm/string.h:8,
                    from include/linux/string.h:21,
                    from include/linux/uuid.h:12,
                    from include/linux/mod_devicetable.h:13,
                    from scripts/mod/devicetable-offsets.c:3:
   include/asm-generic/bitops/find.h:164:16: note: previous implicit declaration of '__fls' was here
     164 |   return val ? __fls(val) : size;
         |                ^~~~~

cc1: some warnings being treated as errors
make[2]: *** [scripts/Makefile.build:117: scripts/mod/devicetable-offsets.s] Error 1 make[2]: Target '__build' not remade because of errors.
make[1]: *** [Makefile:1205: prepare0] Error 2
make[1]: Target 'prepare' not remade because of errors.
make: *** [Makefile:185: __sub-make] Error 2
make: Target 'prepare' not remade because of errors.

vim +164 include/asm-generic/bitops/find.h

149
150 #ifndef find_last_bit
151 /**
152 * find_last_bit - find the last set bit in a memory region
153 * @addr: The address to start the search at
154 * @size: The number of bits to search
155 *
156 * Returns the bit number of the last set bit, or size.
157 */
158 static inline
159 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
160 {
161 if (small_const_nbits(size)) {
162 unsigned long val = *addr & GENMASK(size - 1, 0);
163

 > 164			return val ? __fls(val) : size;

165 }
166
167 return _find_last_bit(addr, size);
168 }
169 #endif
170

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

Acked-by on v6 10/12
#15 lore raw

Re: [PATCH 10/12] lib: add fast path for find_first_*_bit() and find_last_bit()

In reply to Yury Norov
Quoted 6 lines · Yury Norov

Similarly to bitmap functions, users would benefit if we'll handle a case of small-size bitmaps that fit into a single word.

While here, move the find_last_bit() declaration to bitops/find.h where other find_*_bit() functions sit.

Quoted 168 lines
---
 include/asm-generic/bitops/find.h | 50 ++++++++++++++++++++++++++++---
 include/linux/bitops.h            | 12 --------
 lib/find_bit.c                    | 12 ++++----
 3 files changed, 52 insertions(+), 22 deletions(-)
include/asm-generic/bitops/find.h +46 -4
index 4148c74a1e4d..0d132ee2a291 100644
@@ -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
 /**
@@ -102,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);
+}
 
 /**
  * find_first_zero_bit - find the first cleared bit in a memory region
@@ -113,8 +125,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.
  */
-extern 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);
+}
 #else /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
 #ifndef find_first_bit
@@ -126,6 +147,27 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,
 
 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
 
+#ifndef find_last_bit
+/**
+ * find_last_bit - find the last set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The number of bits to search
+ *
+ * Returns the bit number of the last set bit, or size.
+ */
+static inline
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+{
+       if (small_const_nbits(size)) {
+               unsigned long val = *addr & GENMASK(size - 1, 0);
+
+               return val ? __fls(val) : size;
+       }
+
+       return _find_last_bit(addr, size);
+}
+#endif
+
 /**
  * find_next_clump8 - find next 8-bit clump with set bits in a memory region
  * @clump: location to store copy of found clump
include/linux/bitops.h +0 -12
index a5a48303b0f1..26bf15e6cd35 100644
@@ -286,17 +286,5 @@ static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
 })
 #endif
 
-#ifndef find_last_bit
-/**
- * find_last_bit - find the last set bit in a memory region
- * @addr: The address to start the search at
- * @size: The number of bits to search
- *
- * Returns the bit number of the last set bit, or size.
- */
-extern unsigned long find_last_bit(const unsigned long *addr,
-                                  unsigned long size);
-#endif
-
 #endif /* __KERNEL__ */
 #endif
lib/find_bit.c +6 -7
index b03a101367f8..0f8e2e369b1d 100644
@@ -75,7 +75,7 @@ EXPORT_SYMBOL(_find_next_bit);
 /*
  * 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;
 
@@ -86,14 +86,14 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 
        return size;
 }
-EXPORT_SYMBOL(find_first_bit);
+EXPORT_SYMBOL(_find_first_bit);
 #endif
 
 #ifndef find_first_zero_bit
 /*
  * 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;
 
@@ -104,11 +104,11 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 
        return size;
 }
-EXPORT_SYMBOL(find_first_zero_bit);
+EXPORT_SYMBOL(_find_first_zero_bit);
 #endif
 
 #ifndef find_last_bit
-unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
 {
        if (size) {
                unsigned long val = BITMAP_LAST_WORD_MASK(size);
@@ -124,7 +124,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
        }
        return size;
 }
-EXPORT_SYMBOL(find_last_bit);
+EXPORT_SYMBOL(_find_last_bit);
 #endif
 
 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
--

2.25.1

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#16 lore raw

PATCH v6 11/12 tools: sync lib/find_bit implementation

In reply to Yury Norov

Add fast paths to find_*_bit() functions as per kernel implementation.

---
 tools/include/asm-generic/bitops/find.h | 58 +++++++++++++++++++++++--
 tools/lib/find_bit.c                    |  4 +-
 2 files changed, 57 insertions(+), 5 deletions(-)
tools/include/asm-generic/bitops/find.h +55 -3
index 9fe62d10b084..6481fd11012a 100644
@@ -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_ */
tools/lib/find_bit.c +2 -2
index 589fd2f26f94..109aa7ffcf97 100644
@@ -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;
 
Signature · 1 line
2.25.1
#17 lore raw

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

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?

tools/include/linux/bits.h +1 -2
index 7f475d59a097..0aba9294f29d 100644
@@ -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.

#18 lore raw

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

+Cc: Rikard

Quoted 105 lines · Tetsuo Handa

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

Quoted 1 line

Applying below diff seems to solve the build failure.

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

Quoted 1 line

Do we need to use BUILD_BUG_ON_ZERO() here?

Rikard?

Quoted 17 lines
tools/include/linux/bits.h +1 -2
index 7f475d59a097..0aba9294f29d 100644
@@ -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,
Quoted 3 lines

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?

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#19 lore raw

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

Quoted 118 lines · Andy Shevchenko

+Cc: Rikard

Quoted 104 lines · Tetsuo Handa

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

Quoted 2 lines

Applying below diff seems to solve the build failure.

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

Quoted 1 line

Do we need to use BUILD_BUG_ON_ZERO() here?

Rikard?

Quoted 1 line
Quoted 14 lines
Quoted 5 lines
tools/include/linux/bits.h +0 -0
index 7f475d59a097..0aba9294f29d 100644

tools/include/linux/bits.h line 27

Quoted 9 lines
tools/include/linux/bits.h +1 -2
@@ -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.

Quoted 11 lines
Quoted 3 lines

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/[email protected]/

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

#20 lore raw

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

In reply to Andy Shevchenko
Quoted 108 lines · Andy Shevchenko

+Cc: Rikard

Quoted 104 lines · Tetsuo Handa

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

Quoted 9 lines
Quoted 2 lines

Applying below diff seems to solve the build failure.

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

Quoted 1 line

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.

Quoted 16 lines
Quoted 7 lines
tools/include/linux/bits.h +0 -0
index 7f475d59a097..0aba9294f29d 100644

tools/include/linux/bits.h line 27

Quoted 9 lines
tools/include/linux/bits.h +1 -2
@@ -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.

tools/include/linux/bits.h +4 -1
index 7f475d59a097..7bc4c31a7df0 100644
@@ -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

#21 lore raw

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

Quoted 1 line · Rikard Falkeborn

On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:

...

Quoted 4 lines

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...

Quoted 2 lines

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

Right.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#22 lore raw

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

Quoted 5 lines · Andy Shevchenko
Quoted 1 line · Rikard Falkeborn

On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:

...

Quoted 8 lines
Quoted 4 lines

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.

Quoted 3 lines

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

Agreed.

Quoted 10 lines
Quoted 2 lines

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

Right.

Signature · 2 lines
With Best Regards,
Andy Shevchenko

With Best Regards,
Rikard

#23 lore raw

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

Quoted 3 lines · Andy Shevchenko

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,

Quoted 5 lines · Rikard Falkeborn

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.

Quoted 21 lines
tools/include/linux/bits.h +4 -1
index 7f475d59a097..7bc4c31a7df0 100644
@@ -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,
Quoted 3 lines · Yury Norov

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 <[email protected]>
Vendor      : CentOS
URL         : http://gcc.gnu.org
Summary     : GCC version 8
Description :
The devtoolset-8-gcc package contains the GNU Compiler Collection version 7.
#24 lore raw

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

Quoted 41 lines · Tetsuo Handa
Quoted 3 lines · Andy Shevchenko

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

(quoted diff) +10 -0
+       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.

Quoted 9 lines

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.

Quoted 11 lines

But what a surprise,

Quoted 5 lines · Rikard Falkeborn

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/[email protected]/

Rikard

Quoted 58 lines
Quoted 21 lines
tools/include/linux/bits.h +4 -1
index 7f475d59a097..7bc4c31a7df0 100644
@@ -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,
Quoted 3 lines · Yury Norov

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 <[email protected]>
Vendor      : CentOS
URL         : http://gcc.gnu.org
Summary     : GCC version 8
Description :
The devtoolset-8-gcc package contains the GNU Compiler Collection version 7.
maintainer
#25 lore raw

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

Quoted 18 lines · Rikard Falkeborn
Quoted 6 lines · Tetsuo Handa
#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.

Quoted 9 lines

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?

Quoted 5 lines

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

#26 lore raw

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

Quoted 26 lines · Arnd Bergmann
Quoted 18 lines · Rikard Falkeborn
Quoted 6 lines · Tetsuo Handa
#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.

Quoted 9 lines

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?

Quoted 5 lines

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.

Quoted 5 lines

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/[email protected]/

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

maintainer
#27 lore raw

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

Quoted 18 lines · Rasmus Villemoes

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/[email protected]/

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.

Quoted 3 lines

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

#28 lore raw

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

In reply to Rikard Falkeborn
Quoted 12 lines · Rikard Falkeborn
Quoted 10 lines · Andy Shevchenko
Quoted 1 line · Rikard Falkeborn

On Mon, May 10, 2021 at 06:44:44PM +0300, Andy Shevchenko wrote:

...

Quoted 4 lines

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)

Quoted 5 lines
Quoted 3 lines

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)

Quoted 2 lines

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

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#29 lore raw

PATCH v6 12/12 MAINTAINERS: Add entry for the bitmap API

In reply to Yury Norov

Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.

---
 MAINTAINERS | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
MAINTAINERS +16 -0
index bbd4484b5ba6..fcf89f8cbb6a 100644
@@ -3172,6 +3172,22 @@ F:	Documentation/filesystems/bfs.rst
 F:	fs/bfs/
 F:	include/uapi/linux/bfs_fs.h
 
+BITMAP API
+M:	Yury Norov <[email protected]>
+R:	Andy Shevchenko <[email protected]>
+R:	Rasmus Villemoes <[email protected]>
+S:	Maintained
+F:	include/asm-generic/bitops/find.h
+F:	include/linux/bitmap.h
+F:	lib/bitmap.c
+F:	lib/find_bit.c
+F:	lib/find_bit_benchmark.c
+F:	lib/test_bitmap.c
+F:	tools/include/asm-generic/bitops/find.h
+F:	tools/include/linux/bitmap.h
+F:	tools/lib/bitmap.c
+F:	tools/lib/find_bit.c
+
 BLINKM RGB LED DRIVER
 M:	Jan-Simon Moeller <[email protected]>
 S:	Maintained
Signature · 1 line
2.25.1
#30 lore raw
In reply to Yury Norov
Quoted 10 lines · Yury Norov

Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.c we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.

find_*_bit() API lacks this functionality; but users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG.

Cool, thanks!

I guess it's assumed to go via Andrew's tree.

But after that since you are about to be a maintainer of this, I think it would make sense to send PRs directly to Linus. I would recommend creating an official tree (followed by an update in the MAINTAINERS) and connecting it to Linux next (usually done by email to Stephen).

Quoted 42 lines

v6 is mostly a resend. The only change comparing to v5 is a fix of small_const_nbits() synchronization patch.

v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: https://patchwork.kernel.org/project/linux-sh/cover/[email protected]/
v5: https://lore.kernel.org/linux-arch/[email protected]/T/
v6: - sync small_const_nbits() properly (patch 6).
- Rasmus' ack added.

Yury Norov (12):
tools: disable -Wno-type-limits
tools: bitmap: sync function declarations with the kernel
tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel
arch: rearrange headers inclusion order in asm/bitops for m68k and sh
lib: extend the scope of small_const_nbits() macro
tools: sync small_const_nbits() macro with the kernel
lib: inline _find_next_bit() wrappers
tools: sync find_next_bit implementation
lib: add fast path for find_next_*_bit()
lib: add fast path for find_first_*_bit() and find_last_bit()
tools: sync lib/find_bit implementation
MAINTAINERS: Add entry for the bitmap API

 MAINTAINERS                             |  16 ++++
 arch/m68k/include/asm/bitops.h          |   6 +-
 arch/sh/include/asm/bitops.h            |   5 +-
 include/asm-generic/bitops/find.h       | 108 +++++++++++++++++++++---
 include/asm-generic/bitops/le.h         |  38 ++++++++-
 include/asm-generic/bitsperlong.h       |  12 +++
 include/linux/bitmap.h                  |   8 --
 include/linux/bitops.h                  |  12 ---
 lib/find_bit.c                          |  68 ++-------------
 tools/include/asm-generic/bitops/find.h |  85 +++++++++++++++++--
 tools/include/asm-generic/bitsperlong.h |   3 +
 tools/include/linux/bitmap.h            |  18 ++--
 tools/lib/bitmap.c                      |   4 +-
 tools/lib/find_bit.c                    |  56 +++++-------
 tools/scripts/Makefile.include          |   1 +
 15 files changed, 284 insertions(+), 156 deletions(-)
Quoted 3 lines

--
2.25.1

--
With Best Regards,
Andy Shevchenko

maintainer
#31 lore raw
Quoted 13 lines · Andy Shevchenko
Quoted 10 lines · Yury Norov

Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.c we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.

find_*_bit() API lacks this functionality; but users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG.

Quoted 8 lines

Cool, thanks!

I guess it's assumed to go via Andrew's tree.

But after that since you are about to be a maintainer of this, I think it would make sense to send PRs directly to Linus. I would recommend creating an official tree (followed by an update in the MAINTAINERS) and connecting it to Linux next (usually done by email to Stephen).

It depends on how often we expect to see updates to this. I have not followed the changes as closely as I should have, but I can also merge them through the asm-generic tree for this time so Andrew has to carry fewer patches for this.

I normally don't have a lot of material for asm-generic either, half the time there are no pull requests at all for a given release. I would expect future changes to the bitmap implementation to only need an occasional bugfix, which could go through either the asm-generic tree or through mm and doesn't need another separate pull request.

If it turns out to be a tree that needs regular updates every time, then having a top level repository in linux-next would be appropriate.

Arnd

#32 lore raw
Quoted 30 lines · Arnd Bergmann
Quoted 13 lines · Andy Shevchenko
Quoted 10 lines · Yury Norov

Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.c we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.

find_*_bit() API lacks this functionality; but users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG.

Quoted 8 lines

Cool, thanks!

I guess it's assumed to go via Andrew's tree.

But after that since you are about to be a maintainer of this, I think it would make sense to send PRs directly to Linus. I would recommend creating an official tree (followed by an update in the MAINTAINERS) and connecting it to Linux next (usually done by email to Stephen).

It depends on how often we expect to see updates to this. I have not followed the changes as closely as I should have, but I can also merge them through the asm-generic tree for this time so Andrew has to carry fewer patches for this.

Quoted 8 lines

I normally don't have a lot of material for asm-generic either, half the time there are no pull requests at all for a given release. I would expect future changes to the bitmap implementation to only need an occasional bugfix, which could go through either the asm-generic tree or through mm and doesn't need another separate pull request.

If it turns out to be a tree that needs regular updates every time, then having a top level repository in linux-next would be appropriate.

Agree. asm-generic may serve for this. My worries are solely about how much burden we add on Andrew's shoulders.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
maintainer
#33 lore raw
Quoted 11 lines · On Thu, 1 Apr 2021 12:50:31 +0300 Andy Shevchenko <[email protected]>…
Quoted 8 lines

I normally don't have a lot of material for asm-generic either, half the time there are no pull requests at all for a given release. I would expect future changes to the bitmap implementation to only need an occasional bugfix, which could go through either the asm-generic tree or through mm and doesn't need another separate pull request.

If it turns out to be a tree that needs regular updates every time, then having a top level repository in linux-next would be appropriate.

Agree. asm-generic may serve for this. My worries are solely about how much burden we add on Andrew's shoulders.

Is fine. Saving other developers from having to maintain tiny trees is a thing I do.