[PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Tzu-Ching Yang]

generic_ffs(), generic___ffs(), generic_fls() and generic___fls() each
open-code the same binary search: if the low (or high) half of the bits
still in play is zero, shift it out and adjust the result, then repeat
with half the width. Each copy spells out its own masks, the two
unsigned long versions need an #if for their 32-bit step, and the
copies differ in the order of the two updates in a step and in how the
test is written. They implement some or all of these operations on
riscv (without Zbb, and as the fallback with Zbb), ARM before ARMv5,
m68k without bitfield instructions, sh, sparc32, microblaze, nios2 and
a few other architectures.

Add <asm-generic/bitops/ffs-fls-search.h> with one search step per
direction, whose shift and mask follow from the step number and the
type of the word, and expand the steps with UNROLL() from
<linux/unroll.h>. The four functions keep their definitions and
kernel-doc; only the steps are shared. UNROLL() works in the
preprocessor, so every shift and mask is still an integer constant
expression. Its count has to be a literal, so rather than hard-coding
six steps for a 64-bit word, expand the 20 that UNROLL() supports: a
step past the width of the word shifts by 0 and is optimized away,
which also removes the #if.

The shared step tests with "!", shifts the word and then adjusts the
result, as generic_ffs() and generic_fls() did, so those two compile to
the same code as before. generic___ffs() and generic___fls() adjusted
the result first; GCC now mostly emits the same instructions with the
shift and the update swapped, and Clang 18 changes a few riscv callers
somewhat more (sizes below). Nothing was timed on hardware that runs
this code. For the reordered code, models of the affected cores
(llvm-mca for riscv) predict no slowdown, except 1-2 cycles on a few
inputs in the out-of-order SiFive P450 model, whereas adjusting the
result first in all four functions is predicted to slow down
generic_ffs() and generic_fls().

A plain loop with unrolled_full would not need the step macros, but the
pragma is only a hint and leaves the code to each compiler's unroller:
both GCC and Clang unroll the loop completely, yet Clang then generates
different code for nearly every target, better in some cases and worse
in others, and so does GCC in some callers once the helpers are inlined.

As a side effect, every user of <linux/bitops.h> on these architectures,
including every riscv kernel, now also sees <linux/unroll.h>. The header
is small, but it defines the lower-case object-like macros unrolled,
unrolled_full and unrolled_none, so a variable, struct member or
parameter with one of these names stops building there while it still
builds on x86 and arm64. With GCC 11 and later, a parameter named
"unrolled" can even build, with only -Wunknown-pragmas warnings, and
silently lose its value. No in-tree code uses these names.

Results are unchanged for every 32-bit argument and every 64-bit word
with a zero low half (QEMU user mode; riscv64, rv32, m68k, sh4,
sparc32, ARMv4T, openrisc and parisc with GCC 16.2, riscv64 with Clang
18). The ffs and bitops KUnit tests, test_bitmap and test_bitops pass
on riscv64 without Zbb, and W=1 builds report no new warnings.

bloat-o-meter on vmlinux with GCC 16.2: no change for arm v4t, m68k
ColdFire 5475, sh4, sparc32, openrisc, parisc64 and xtensa without NSA;
+4 bytes for riscv without Zbb. With Clang 18, riscv without Zbb is -38
bytes (assoc_array_insert() -42, iio_device_add_event() +8). m68k
ColdFire 5208 is +16 bytes, from two functions that use none of these
helpers; GCC compiles them identically with -ftrack-macro-expansion=0.

Signed-off-by: Tzu-Ching Yang <shingekinocore@gmail.com>
---
<linux/unroll.h> now reaches 2327 of 2513 compiled units in a riscv
defconfig build (Zbb off), up from 44. Test modules with a local
variable or struct member named "unrolled" fail to build with this
patch on riscv (GCC with Zbb on and off, Clang with Zbb off), m68k
ColdFire and ARMv4T, and still build on x86_64 and arm64.

Generated code. generic_ffs() and generic_fls() are unchanged. In
callers of generic___ffs() and generic___fls() the shift and the
counter update trade places, e.g. riscv64 _find_first_bit(), GCC 16.2:

    mainline                   with this patch
    bnez   a3,<next>           bnez   a3,<next>
    addiw  a0,a0,16            srli   a4,a4,0x10
    srli   a4,a4,0x10          addiw  a0,a0,16
    zext.b a3,a4               zext.b a3,a4

Functions that differ in vmlinux, GCC 16.2:
  riscv, Zbb off   300; 298 reordered only, 2 with other registers
                   (alloc_large_system_hash +6 bytes, bpf_msg_push_data
                   one instruction fewer, same size)
  loongarch32      144 (LA32R), reordered only
  parisc64         114 (__fls only); 90 reordered only, 23 with another
                   delay slot fill, 1 with two registers swapped
  sparc32 48, openrisc 44, xtensa 12 (one also renames registers),
  sh4 4: reordered only
  arm v4t, m68k ColdFire 5475: vmlinux byte-identical
  m68k ColdFire 5208: percpu_rwsem_wait +8, __wait_for_common -4; they
                   inline no ffs/fls helper and compile identically with
                   -ftrack-macro-expansion=0 or -g
Except on riscv and 5208, function sizes are unchanged. Clang 18, riscv
with Zbb off: 12 functions, none only reordered; the _find_first*_bit()
helpers use "or" instead of "add" for idx + __ffs(),
assoc_array_insert() is 42 bytes smaller and iio_device_add_event() 8
bytes larger, with a 16-byte larger stack frame.

bloat-o-meter, riscv defconfig with RISCV_ISA_ZBB=n:
  GCC 16.2: add/remove: 0/0 grow/shrink: 1/1 up/down: 6/-2 (4)
  Clang 18: add/remove: 0/0 grow/shrink: 2/3 up/down: 44/-82 (-38)
mm_core_init -2 and dw_pcie_irq_domain_alloc -4 come from byte-identical
objects and change at link time (relaxation). On loongarch32 with
CONFIG_IKHEADERS only kernel_headers_data changes (-800 bytes).

Performance is model-only: no affected architecture could be timed on
hardware. llvm-mca 17/18 ran on every executed path for the SiFive
U74/E76/P450, Rocket and SCR1 models; m68k, sh, sparc32, xtensa,
parisc, openrisc, loongarch32 and microblaze only got simple static
issue models (and MC68000 instruction timings). Of 648 changed
compiler/target/flags/function combinations, none is predicted slower
except 20 riscv64 caller cases in which the out-of-order P450 model
needs 1-2 more cycles on some inputs (-0.4% to +0.4% averaged over the
inputs); the in-order SiFive-7 model is up to 4 cycles faster per
__ffs() call. llvm-mca did not predict the slowdowns that this kind of
reordering showed on x86 hardware (up to about 10% on single paths;
x86 does not use this code), so this is weak evidence. Adjusting the
result first everywhere is predicted slower for ffs()/fls() on every
affected architecture, e.g. +3 cycles per ffs() call on the U74.

A loop with unrolled_full, against the current headers in userspace
builds (GCC 9/12/13/14 and Clang 17/18, 75 compiler/target pairs, -O2,
-Os and kernel-like -O2): out of line, GCC gives identical code in all
324 cases and Clang different code in 567 of 576, e.g. Clang 18 rv64
fls() 33 -> 25 instructions but __ffs() 29 -> 31 and one more branch,
Clang 17 ARMv4 ffs() 23 -> 37. Inlined into callers, GCC differs in 60
of 324 cases.

UNROLL(20) rather than six steps: the extra steps vanish when
optimizing, but not at -O0 or under Clang's GCOV instrumentation, where
the four helpers out of line grow from 405 to 564 instructions and from
280 to 728 bytes of counters (Clang 18 riscv64; measured with the same
expansion before the step order was unified).

tools/include/asm-generic/bitops/{fls,__fls}.h copy two of these
headers, so tools/perf/check-headers.sh will report them as different.
They cannot simply be resynced, since tools/include has no
<linux/unroll.h> or ffs-fls-search.h; the current copies compute the
same values, so keeping them, or dropping the two entries from
check-headers.sh, is enough.

Testing details: all 2^32 arguments in 12 configurations and every 7th
block of 2^16 in 51 more (GCC 8.1 to 16.2, LLVM 17 to 23), with no
mismatch against the old code or an independent reference. W=1 vmlinux
builds: arm multi_v4t, m68k m5475evb and m5208evb, sh rts7751r2dplus,
sparc32, openrisc without ff1/fl1, parisc64, xtensa (custom core
without NSA), loongarch32 (LA32R) and riscv with Zbb off, GCC 16.2,
plus riscv with Clang 18. Not covered: hardware timing, and any model
of the Clang 18 riscv changes; run-time tests on parisc64, loongarch32,
microblaze, nios2, xtensa and SH-2A; other compiler versions in kernel
builds; modules; sparse, smatch, coccinelle.

Against bitmap-for-next (a73b4d1fa7d3); applies as is to v7.3-rc7 and
next-20261012, where the four headers are identical.

 include/asm-generic/bitops/__ffs.h          | 26 +----------
 include/asm-generic/bitops/__fls.h          | 26 +----------
 include/asm-generic/bitops/ffs-fls-search.h | 51 +++++++++++++++++++++
 include/asm-generic/bitops/ffs.h            | 23 ++--------
 include/asm-generic/bitops/fls.h            | 23 ++--------
 5 files changed, 61 insertions(+), 88 deletions(-)
 create mode 100644 include/asm-generic/bitops/ffs-fls-search.h

diff --git a/include/asm-generic/bitops/__ffs.h b/include/asm-generic/bitops/__ffs.h
index 3a899c626f..ad5c014c62 100644
--- a/include/asm-generic/bitops/__ffs.h
+++ b/include/asm-generic/bitops/__ffs.h
@@ -3,6 +3,7 @@
 #define _ASM_GENERIC_BITOPS___FFS_H_
 
 #include <asm/types.h>
+#include <asm-generic/bitops/ffs-fls-search.h>
 
 /**
  * generic___ffs - find first bit in word.
@@ -14,30 +15,7 @@ static __always_inline __attribute_const__ unsigned int generic___ffs(unsigned l
 {
 	unsigned int num = 0;
 
-#if BITS_PER_LONG == 64
-	if ((word & 0xffffffff) == 0) {
-		num += 32;
-		word >>= 32;
-	}
-#endif
-	if ((word & 0xffff) == 0) {
-		num += 16;
-		word >>= 16;
-	}
-	if ((word & 0xff) == 0) {
-		num += 8;
-		word >>= 8;
-	}
-	if ((word & 0xf) == 0) {
-		num += 4;
-		word >>= 4;
-	}
-	if ((word & 0x3) == 0) {
-		num += 2;
-		word >>= 2;
-	}
-	if ((word & 0x1) == 0)
-		num += 1;
+	__ffs_fls_unroll(__ffs_step, word, num);
 	return num;
 }
 
diff --git a/include/asm-generic/bitops/__fls.h b/include/asm-generic/bitops/__fls.h
index 35f33780ca..1c439e881b 100644
--- a/include/asm-generic/bitops/__fls.h
+++ b/include/asm-generic/bitops/__fls.h
@@ -3,6 +3,7 @@
 #define _ASM_GENERIC_BITOPS___FLS_H_
 
 #include <asm/types.h>
+#include <asm-generic/bitops/ffs-fls-search.h>
 
 /**
  * generic___fls - find last (most-significant) set bit in a long word
@@ -14,30 +15,7 @@ static __always_inline __attribute_const__ unsigned int generic___fls(unsigned l
 {
 	unsigned int num = BITS_PER_LONG - 1;
 
-#if BITS_PER_LONG == 64
-	if (!(word & (~0ul << 32))) {
-		num -= 32;
-		word <<= 32;
-	}
-#endif
-	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
-		num -= 16;
-		word <<= 16;
-	}
-	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
-		num -= 8;
-		word <<= 8;
-	}
-	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
-		num -= 4;
-		word <<= 4;
-	}
-	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
-		num -= 2;
-		word <<= 2;
-	}
-	if (!(word & (~0ul << (BITS_PER_LONG-1))))
-		num -= 1;
+	__ffs_fls_unroll(__fls_step, word, num);
 	return num;
 }
 
diff --git a/include/asm-generic/bitops/ffs-fls-search.h b/include/asm-generic/bitops/ffs-fls-search.h
new file mode 100644
index 0000000000..5c64364e54
--- /dev/null
+++ b/include/asm-generic/bitops/ffs-fls-search.h
@@ -0,0 +1,51 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_
+#define _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_
+
+#include <linux/unroll.h>
+
+/*
+ * Steps of a binary search for the first or last set bit of a word
+ * @i: the step number, from 0
+ * @x: the word, a local variable that the steps shift in place
+ * @n: the result, a local variable that the steps adjust in place
+ *
+ * Step @i looks at the low (__ffs_step) or high (__fls_step)
+ * __ffs_fls_shift(@i, @x) bits of @x: half of its width, then a quarter,
+ * and so on. If they are all zero, the step shifts them out of @x and adds
+ * their number to @n (__ffs_step) or subtracts it (__fls_step). @x is
+ * shifted before @n is adjusted: the next step tests @x, while @n is only
+ * needed at the end. The masks are computed in the type of @x.
+ *
+ * UNROLL() expands the steps in the preprocessor, so every shift and mask
+ * is an integer constant expression, as in a hand-written search. It puts
+ * the steps next to each other with nothing in between, hence the braces.
+ */
+#define __ffs_fls_shift(i, x)	((int)sizeof(x) * 8 >> ((i) + 1))
+#define __ffs_mask(i, x)	(((typeof(x))1 << __ffs_fls_shift(i, x)) - 1)
+#define __fls_mask(i, x)	((typeof(x))~(~(typeof(x))0 >> __ffs_fls_shift(i, x)))
+
+#define __ffs_step(i, x, n)						\
+	{								\
+		if (!((x) & __ffs_mask(i, x))) {			\
+			(x) >>= __ffs_fls_shift(i, x);			\
+			(n) += __ffs_fls_shift(i, x);			\
+		}							\
+	}
+
+#define __fls_step(i, x, n)						\
+	{								\
+		if (!((x) & __fls_mask(i, x))) {			\
+			(x) <<= __ffs_fls_shift(i, x);			\
+			(n) -= __ffs_fls_shift(i, x);			\
+		}							\
+	}
+
+/*
+ * Six steps cover a 64-bit word. UNROLL() needs a literal count, which
+ * cannot be derived from sizeof(@x), so expand the most it supports. Steps
+ * past the width of @x shift by 0 and are optimized away.
+ */
+#define __ffs_fls_unroll(step, x, n)	UNROLL(20, step, x, n)
+
+#endif /* _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_ */
diff --git a/include/asm-generic/bitops/ffs.h b/include/asm-generic/bitops/ffs.h
index 5ff2b7fbda..53705ba8c9 100644
--- a/include/asm-generic/bitops/ffs.h
+++ b/include/asm-generic/bitops/ffs.h
@@ -2,6 +2,8 @@
 #ifndef _ASM_GENERIC_BITOPS_FFS_H_
 #define _ASM_GENERIC_BITOPS_FFS_H_
 
+#include <asm-generic/bitops/ffs-fls-search.h>
+
 /**
  * generic_ffs - find first bit set
  * @x: the word to search
@@ -16,26 +18,7 @@ static inline __attribute_const__ int generic_ffs(int x)
 
 	if (!x)
 		return 0;
-	if (!(x & 0xffff)) {
-		x >>= 16;
-		r += 16;
-	}
-	if (!(x & 0xff)) {
-		x >>= 8;
-		r += 8;
-	}
-	if (!(x & 0xf)) {
-		x >>= 4;
-		r += 4;
-	}
-	if (!(x & 3)) {
-		x >>= 2;
-		r += 2;
-	}
-	if (!(x & 1)) {
-		x >>= 1;
-		r += 1;
-	}
+	__ffs_fls_unroll(__ffs_step, x, r);
 	return r;
 }
 
diff --git a/include/asm-generic/bitops/fls.h b/include/asm-generic/bitops/fls.h
index 8eed3437ed..42625a0785 100644
--- a/include/asm-generic/bitops/fls.h
+++ b/include/asm-generic/bitops/fls.h
@@ -2,6 +2,8 @@
 #ifndef _ASM_GENERIC_BITOPS_FLS_H_
 #define _ASM_GENERIC_BITOPS_FLS_H_
 
+#include <asm-generic/bitops/ffs-fls-search.h>
+
 /**
  * generic_fls - find last (most-significant) bit set
  * @x: the word to search
@@ -16,26 +18,7 @@ static __always_inline __attribute_const__ int generic_fls(unsigned int x)
 
 	if (!x)
 		return 0;
-	if (!(x & 0xffff0000u)) {
-		x <<= 16;
-		r -= 16;
-	}
-	if (!(x & 0xff000000u)) {
-		x <<= 8;
-		r -= 8;
-	}
-	if (!(x & 0xf0000000u)) {
-		x <<= 4;
-		r -= 4;
-	}
-	if (!(x & 0xc0000000u)) {
-		x <<= 2;
-		r -= 2;
-	}
-	if (!(x & 0x80000000u)) {
-		x <<= 1;
-		r -= 1;
-	}
+	__ffs_fls_unroll(__fls_step, x, r);
 	return r;
 }
 

base-commit: a73b4d1fa7d334a5f7de5bb0a14726530f66196e
-- 
2.34.1

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Arnd Bergmann]

On Fri, Oct 16, 2026, at 04:56, Tzu-Ching Yang wrote:
> generic_ffs(), generic___ffs(), generic_fls() and generic___fls() each
> open-code the same binary search: if the low (or high) half of the bits
> still in play is zero, shift it out and adjust the result, then repeat
> with half the width. Each copy spells out its own masks, the two
> unsigned long versions need an #if for their 32-bit step, and the
> copies differ in the order of the two updates in a step and in how the
> test is written. They implement some or all of these operations on
> riscv (without Zbb, and as the fallback with Zbb), ARM before ARMv5,
> m68k without bitfield instructions, sh, sparc32, microblaze, nios2 and
> a few other architectures.
>
> Add <asm-generic/bitops/ffs-fls-search.h> with one search step per
> direction, whose shift and mask follow from the step number and the
> type of the word, and expand the steps with UNROLL() from
> <linux/unroll.h>. The four functions keep their definitions and
> kernel-doc; only the steps are shared. UNROLL() works in the
> preprocessor, so every shift and mask is still an integer constant
> expression. Its count has to be a literal, so rather than hard-coding
> six steps for a 64-bit word, expand the 20 that UNROLL() supports: a
> step past the width of the word shifts by 0 and is optimized away,
> which also removes the #if.

I don't understand what you are trying to do here, but I don't
think we want this change: I find the nested macros harder
to read than the open-coded version and your changelog text
fails to explain what the purpose is.

If you have a specific problem with one of the platforms using
this, I would suggest you address that one but leave the
generic code unchanged.

      Arnd

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Arnd Bergmann]

On Fri, Oct 16, 2026, at 07:54, Arnd Bergmann wrote:
>
> I don't understand what you are trying to do here, but I don't
> think we want this change: I find the nested macros harder
> to read than the open-coded version and your changelog text
> fails to explain what the purpose is.

If you are interested in creating helpful patches in this area,
maybe you could work towards eliminating the generic versions
of these functions in favor of using the builtin ones on targets
where the compilers produce sensible code for them.

      Arnd

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Tzu-Ching Yang]

On Fri, Oct 16, 2026, at 09:16, Arnd Bergmann wrote:
> If you are interested in creating helpful patches in this area,
> maybe you could work towards eliminating the generic versions
> of these functions in favor of using the builtin ones on targets
> where the compilers produce sensible code for them.

Thanks, I looked into this. For each architecture variant, I put the
kernel's current version of each function and the builtin one into a
small userspace test file, each in a function of its own, compiled it
at -O2 and -Os with every GCC major release from 8 to 16 and Clang 17
to 23 that supports the target, and compared the instruction counts
for a variable argument. Of the rows below, only hexagon (Clang only),
powerpc and mips other than octeon could be built with Clang. A few
GCC -Os builds did not inline the kernel's version, so those cells
(arc ARCompact, ffs() and fls() on mips, and ffs() on microblaze) use
-O2 only.

Each cell below gives what the kernel uses today (G the generic
version or a copy of it, A arch asm, B the builtin) and how the
builtin compares with it:

  +  inline and never more instructions, with every compiler
  ~  as +, but only with some compilers (see below)
  -  more instructions, with every compiler
  x  the hardware has an instruction, but the compiler never emits it
     (the builtin is a library call)

In the "fls (clzg)" column, the code in parentheses is for fls()
written as 32 - __builtin_clzg(x, 32), which needs GCC 14 or Clang 19
or later, so it covers only those compilers.

                     | __ffs | ffs | __fls | fls (clzg)
---------------------+-------+-----+-------+-----------
ColdFire ISA_A+/C    | A-    | A-  | G+    | G+  (G+)
microblaze PCMP 8.10 | G+    | G+  | G+    | G+  (G+)
microblaze PCMP 11.0 | G~    | G~  | G~    | G~  (G+)
hexagon              | A+    | A+  | A+    | A+  (A+)
mips32 r2/r6         | A~    | A+  | A+    | A~  (A+)
mips64 r2            | A~    | A+  | A+    | A~  (A~)
mips64 r6            | G+    | A+  | G+    | A~  (A~)
mips octeon          | A+    | A+  | A+    | A-  (A+)
xtensa NSA           | A+    | A+  | A+    | A-  (A-)
arc ARCompact        | A+    | A-  | A+    | A-  (A-)
m68k 68020+          | A+    | A-  | A+    | A-  (A-)
arc HS               | A~    | A+  | A~    | A-  (A-)
csky                 | Ax    | Ax  | A+    | A-  (A-)
openrisc FF1/FL1     | Ax    | Ax  | Ax    | Ax  (Ax)
powerpc              | B     | B   | B     | A~  (A+)

The ~ cells depend on the compiler: microblaze 11.0 needs GCC 14
(older GCC compares "v11.0" and "v8.10.a" as plain strings and emits a
library call), arc HS needs GCC 12, mips __ffs() is + only with GCC,
mips and powerpc fls() only with Clang, and on mips64 neither fls()
nor clzg is + with Clang 19.

Not listed are the targets without a suitable instruction, where GCC
turns the builtins into library calls, so their current code has to
stay: alpha ev56, arm v4/v4t, ColdFire ISA_A/ISA_B, m68000, microblaze
without PCMP or before 8.10.a, mips R3000, nios2, openrisc without
FF1/FL1, parisc, riscv without Zbb, loongarch la32r, sh and sparc32.

The G cells are the clear candidates: microblaze with PCMP (8.10.a or
later) uses the generic versions although GCC emits clz for the
builtins, and ColdFire ISA_A+/C still uses them for __fls() and fls(),
while __ffs() and ffs() there already use ff1 in asm. On mips64 r6,
__ffs() and __fls() end up in the C fallback of __fls(), a copy of the
generic version. I confirmed this in 64r6el_defconfig builds with GCC
16 and Clang 23: the dclz branch is used only if cpu_has_mips64 is a
compile-time constant, and on r6 it is not, because cpu_has_mips64r6
still tests a runtime flag. The builtins would cut both functions
there from 34-64 instructions to 4-8; making cpu_has_mips64r6 constant
on 64-bit r6 kernels would fix this as well.

In the A cells, __ffs() and __fls() could mostly switch at no cost,
which also lets the compiler fold constant arguments where the asm
does not. fls() pays for the zero test that __builtin_clz() needs,
unless the compiler knows what the instruction returns for 0: Clang
does on hexagon, mips and powerpc, and GCC only with __builtin_clzg(),
on mips and powerpc. That test is why powerpc keeps asm for fls() with
non-constant arguments.

If this is what you had in mind, I would send one patch per
architecture to its maintainers, with you, Yury and Rasmus on Cc:
first the G+ cells (microblaze, ColdFire and mips64 r6), then the A+
cells (hexagon, mips, xtensa, arc, m68k 68020+ and csky), with fls()
using __builtin_clzg() behind a __has_builtin() check where the table
shows that it helps (mips and powerpc). The same change to
builtin-fls.h would make fls() smaller with some compilers, and never
larger, on arm, arm64, loongarch and s390 (on arm64 from 6 to 4
instructions at -O2 with GCC 14 and later). The ~ cells would need a
check for the compiler or its version, so I would only do those if the
maintainers want it. Each patch would be tested with kernel builds and
the ffs KUnit test.

> On Fri, Oct 16, 2026, at 07:54, Arnd Bergmann wrote:
>> I don't understand what you are trying to do here, but I don't
>> think we want this change: I find the nested macros harder
>> to read than the open-coded version and your changelog text
>> fails to explain what the purpose is.

Sorry, the changelog buried the point. This is a cleanup of the
generic versions, which are still needed on targets without a suitable
instruction. generic_ffs(), generic___ffs(), generic_fls() and
generic___fls() each open-code the same binary search with their own
hand-written masks. The copies differ in the order of the two updates
in a step and in how the test is written, and the two unsigned long
ones need an #if around the extra step for 64-bit words. The patch
replaces the four copies with one shared step per direction, whose
shift and mask are computed from the step number and the type of the
word, so the literal masks and the #if go away (27 fewer lines
overall).

One detail that may look odd is that the patch uses UNROLL(20)
although a 64-bit word needs only six steps. The steps are not tied to
a particular width, so it expands all 20 that UNROLL() supports: once
the shift reaches 0, a step does nothing and the compiler drops it
when optimizing.

generic_ffs() and generic_fls() compile to the same code as before.
With GCC 16.2, the code in callers of generic___ffs() and
generic___fls() mostly differs only in the order of two independent
instructions, and vmlinux size is unchanged on most of the
architectures I built.

I agree that each step is easier to check in the open-coded version.
The trade-off is one place to check instead of four, but since you
find the current code easier to read, I'm happy to drop this unless
Yury sees it differently.

>> If you have a specific problem with one of the platforms using
>> this, I would suggest you address that one but leave the
>> generic code unchanged.

No, the patch did not come from a problem on a specific platform; it
was meant purely as a cleanup.

A few minor notes, for completeness. Because the shifts and masks are
derived from the type of the word, the steps also work for wider words
(I checked unsigned __int128) and could be used to build ctz/clz-style
helpers for other unsigned types, though nothing needs that today. And
__fls_step as posted is only correct for unsigned words, which is what
both of its users pass; if there were a v2, it would make the steps
work in the unsigned type of the same width as the word. Separately
from this patch, generic_ffs() in mainline right-shifts its int
argument; for negative values that is implementation-defined, though
GCC and Clang shift arithmetically and the result is correct. If you
think it is worth fixing, I can send a small patch that copies the
argument to an unsigned int first.

Thanks,
Tzu-Ching

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Arnd Bergmann]

On Fri, Oct 16, 2026, at 15:53, Tzu-Ching Yang wrote:
> On Fri, Oct 16, 2026, at 09:16, Arnd Bergmann wrote:
>> If you are interested in creating helpful patches in this area,
>> maybe you could work towards eliminating the generic versions
>> of these functions in favor of using the builtin ones on targets
>> where the compilers produce sensible code for them.
>
> Thanks, I looked into this. For each architecture variant, I put the
> kernel's current version of each function and the builtin one into a
> small userspace test file, each in a function of its own, compiled it
> at -O2 and -Os with every GCC major release from 8 to 16 and Clang 17
> to 23 that supports the target, and compared the instruction counts
> for a variable argument. Of the rows below, only hexagon (Clang only),
> powerpc and mips other than octeon could be built with Clang. A few
> GCC -Os builds did not inline the kernel's version, so those cells
> (arc ARCompact, ffs() and fls() on mips, and ffs() on microblaze) use
> -O2 only.
>
> Each cell below gives what the kernel uses today (G the generic
> version or a copy of it, A arch asm, B the builtin) and how the
> builtin compares with it:
>
>   +  inline and never more instructions, with every compiler
>   ~  as +, but only with some compilers (see below)
>   -  more instructions, with every compiler
>   x  the hardware has an instruction, but the compiler never emits it
>      (the builtin is a library call)
>
> In the "fls (clzg)" column, the code in parentheses is for fls()
> written as 32 - __builtin_clzg(x, 32), which needs GCC 14 or Clang 19
> or later, so it covers only those compilers.

Thanks for checking those!

                      | __ffs | ffs | __fls | fls (clzg)
> ---------------------+-------+-----+-------+-----------
> ColdFire ISA_A+/C    | A-    | A-  | G+    | G+  (G+)
> microblaze PCMP 8.10 | G+    | G+  | G+    | G+  (G+)
> microblaze PCMP 11.0 | G~    | G~  | G~    | G~  (G+)
> hexagon              | A+    | A+  | A+    | A+  (A+)
> mips32 r2/r6         | A~    | A+  | A+    | A~  (A+)
> mips64 r2            | A~    | A+  | A+    | A~  (A~)
> mips64 r6            | G+    | A+  | G+    | A~  (A~)
> mips octeon          | A+    | A+  | A+    | A-  (A+)
> xtensa NSA           | A+    | A+  | A+    | A-  (A-)
> arc ARCompact        | A+    | A-  | A+    | A-  (A-)
> m68k 68020+          | A+    | A-  | A+    | A-  (A-)
> arc HS               | A~    | A+  | A~    | A-  (A-)
> csky                 | Ax    | Ax  | A+    | A-  (A-)
> openrisc FF1/FL1     | Ax    | Ax  | Ax    | Ax  (Ax)
> powerpc              | B     | B   | B     | A~  (A+)
>
> The ~ cells depend on the compiler: microblaze 11.0 needs GCC 14
> (older GCC compares "v11.0" and "v8.10.a" as plain strings and emits a
> library call), arc HS needs GCC 12, mips __ffs() is + only with GCC,
> mips and powerpc fls() only with Clang, and on mips64 neither fls()
> nor clzg is + with Clang 19.
>
> Not listed are the targets without a suitable instruction, where GCC
> turns the builtins into library calls, so their current code has to
> stay: alpha ev56, arm v4/v4t, ColdFire ISA_A/ISA_B, m68000, microblaze
> without PCMP or before 8.10.a, mips R3000, nios2, openrisc without
> FF1/FL1, parisc, riscv without Zbb, loongarch la32r, sh and sparc32.

Right, that list is pretty much anyone using the generic helpers
today, so it does not sound like we can convert any of them to
the built-in version, only the architectures that currently use
a custom helper.

> The G cells are the clear candidates: microblaze with PCMP (8.10.a or
> later) uses the generic versions although GCC emits clz for the
> builtins, and ColdFire ISA_A+/C still uses them for __fls() and fls(),
> while __ffs() and ffs() there already use ff1 in asm. On mips64 r6,
> __ffs() and __fls() end up in the C fallback of __fls(), a copy of the
> generic version. I confirmed this in 64r6el_defconfig builds with GCC
> 16 and Clang 23: the dclz branch is used only if cpu_has_mips64 is a
> compile-time constant, and on r6 it is not, because cpu_has_mips64r6
> still tests a runtime flag. The builtins would cut both functions
> there from 34-64 instructions to 4-8; making cpu_has_mips64r6 constant
> on 64-bit r6 kernels would fix this as well.

> In the A cells, __ffs() and __fls() could mostly switch at no cost,
> which also lets the compiler fold constant arguments where the asm
> does not. fls() pays for the zero test that __builtin_clz() needs,
> unless the compiler knows what the instruction returns for 0: Clang
> does on hexagon, mips and powerpc, and GCC only with __builtin_clzg(),
> on mips and powerpc. That test is why powerpc keeps asm for fls() with
> non-constant arguments.
>
> If this is what you had in mind, I would send one patch per
> architecture to its maintainers, with you, Yury and Rasmus on Cc:
> first the G+ cells (microblaze, ColdFire and mips64 r6), then the A+
> cells (hexagon, mips, xtensa, arc, m68k 68020+ and csky), with fls()
> using __builtin_clzg() behind a __has_builtin() check where the table
> shows that it helps (mips and powerpc). The same change to
> builtin-fls.h would make fls() smaller with some compilers, and never
> larger, on arm, arm64, loongarch and s390 (on arm64 from 6 to 4
> instructions at -O2 with GCC 14 and later). The ~ cells would need a
> check for the compiler or its version, so I would only do those if the
> maintainers want it. Each patch would be tested with kernel builds and
> the ffs KUnit test.

I would focus on the ones where you can manage to reduce complexity
in the architecture specific code, i.e. replace a custom helper with
the builtin one, but skip the ones where you would need additional
conditionals on toolchain or target options.

On most of these architectures, adding performance or size
optimization is no longer a concern, but source code
simplification does help.

If you have cases where gcc-12 and above produce better code wiht
the built-in, it may still be worth doing that for all toolchains
even if the older compilers may be off slightly worse.

> I agree that each step is easier to check in the open-coded version.
> The trade-off is one place to check instead of four, but since you
> find the current code easier to read, I'm happy to drop this unless
> Yury sees it differently.

Ok.

     Arnd

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Yury Norov]

On Fri, Oct 16, 2026 at 10:56:34AM +0800, Tzu-Ching Yang wrote:
> generic_ffs(), generic___ffs(), generic_fls() and generic___fls() each
> open-code the same binary search: if the low (or high) half of the bits
> still in play is zero, shift it out and adjust the result, then repeat
> with half the width. Each copy spells out its own masks, the two
> unsigned long versions need an #if for their 32-bit step, and the
> copies differ in the order of the two updates in a step and in how the
> test is written. They implement some or all of these operations on
> riscv (without Zbb, and as the fallback with Zbb), ARM before ARMv5,
> m68k without bitfield instructions, sh, sparc32, microblaze, nios2 and
> a few other architectures.
> 
> Add <asm-generic/bitops/ffs-fls-search.h> with one search step per
> direction, whose shift and mask follow from the step number and the
> type of the word, and expand the steps with UNROLL() from
> <linux/unroll.h>. The four functions keep their definitions and
> kernel-doc; only the steps are shared. UNROLL() works in the
> preprocessor, so every shift and mask is still an integer constant
> expression. Its count has to be a literal, so rather than hard-coding
> six steps for a 64-bit word, expand the 20 that UNROLL() supports: a
> step past the width of the word shifts by 0 and is optimized away,
> which also removes the #if.
> 
> The shared step tests with "!", shifts the word and then adjusts the
> result, as generic_ffs() and generic_fls() did, so those two compile to
> the same code as before. generic___ffs() and generic___fls() adjusted
> the result first; GCC now mostly emits the same instructions with the
> shift and the update swapped, and Clang 18 changes a few riscv callers
> somewhat more (sizes below). Nothing was timed on hardware that runs
> this code. For the reordered code, models of the affected cores
> (llvm-mca for riscv) predict no slowdown, except 1-2 cycles on a few
> inputs in the out-of-order SiFive P450 model, whereas adjusting the
> result first in all four functions is predicted to slow down
> generic_ffs() and generic_fls().
> 
> A plain loop with unrolled_full would not need the step macros, but the
> pragma is only a hint and leaves the code to each compiler's unroller:
> both GCC and Clang unroll the loop completely, yet Clang then generates
> different code for nearly every target, better in some cases and worse
> in others, and so does GCC in some callers once the helpers are inlined.
> 
> As a side effect, every user of <linux/bitops.h> on these architectures,
> including every riscv kernel, now also sees <linux/unroll.h>. The header
> is small, but it defines the lower-case object-like macros unrolled,
> unrolled_full and unrolled_none, so a variable, struct member or
> parameter with one of these names stops building there while it still
> builds on x86 and arm64. With GCC 11 and later, a parameter named
> "unrolled" can even build, with only -Wunknown-pragmas warnings, and
> silently lose its value. No in-tree code uses these names.
> 
> Results are unchanged for every 32-bit argument and every 64-bit word
> with a zero low half (QEMU user mode; riscv64, rv32, m68k, sh4,
> sparc32, ARMv4T, openrisc and parisc with GCC 16.2, riscv64 with Clang
> 18). The ffs and bitops KUnit tests, test_bitmap and test_bitops pass
> on riscv64 without Zbb, and W=1 builds report no new warnings.
> 
> bloat-o-meter on vmlinux with GCC 16.2: no change for arm v4t, m68k
> ColdFire 5475, sh4, sparc32, openrisc, parisc64 and xtensa without NSA;
> +4 bytes for riscv without Zbb. With Clang 18, riscv without Zbb is -38
> bytes (assoc_array_insert() -42, iio_device_add_event() +8). m68k
> ColdFire 5208 is +16 bytes, from two functions that use none of these
> helpers; GCC compiles them identically with -ftrack-macro-expansion=0.
> 
> Signed-off-by: Tzu-Ching Yang <shingekinocore@gmail.com>
> ---
> <linux/unroll.h> now reaches 2327 of 2513 compiled units in a riscv
> defconfig build (Zbb off), up from 44. Test modules with a local
> variable or struct member named "unrolled" fail to build with this
> patch on riscv (GCC with Zbb on and off, Clang with Zbb off), m68k
> ColdFire and ARMv4T, and still build on x86_64 and arm64.
> 
> Generated code. generic_ffs() and generic_fls() are unchanged. In
> callers of generic___ffs() and generic___fls() the shift and the
> counter update trade places, e.g. riscv64 _find_first_bit(), GCC 16.2:
> 
>     mainline                   with this patch
>     bnez   a3,<next>           bnez   a3,<next>
>     addiw  a0,a0,16            srli   a4,a4,0x10
>     srli   a4,a4,0x10          addiw  a0,a0,16
>     zext.b a3,a4               zext.b a3,a4
> 
> Functions that differ in vmlinux, GCC 16.2:
>   riscv, Zbb off   300; 298 reordered only, 2 with other registers
>                    (alloc_large_system_hash +6 bytes, bpf_msg_push_data
>                    one instruction fewer, same size)
>   loongarch32      144 (LA32R), reordered only
>   parisc64         114 (__fls only); 90 reordered only, 23 with another
>                    delay slot fill, 1 with two registers swapped
>   sparc32 48, openrisc 44, xtensa 12 (one also renames registers),
>   sh4 4: reordered only
>   arm v4t, m68k ColdFire 5475: vmlinux byte-identical
>   m68k ColdFire 5208: percpu_rwsem_wait +8, __wait_for_common -4; they
>                    inline no ffs/fls helper and compile identically with
>                    -ftrack-macro-expansion=0 or -g
> Except on riscv and 5208, function sizes are unchanged. Clang 18, riscv
> with Zbb off: 12 functions, none only reordered; the _find_first*_bit()
> helpers use "or" instead of "add" for idx + __ffs(),
> assoc_array_insert() is 42 bytes smaller and iio_device_add_event() 8
> bytes larger, with a 16-byte larger stack frame.
> 
> bloat-o-meter, riscv defconfig with RISCV_ISA_ZBB=n:
>   GCC 16.2: add/remove: 0/0 grow/shrink: 1/1 up/down: 6/-2 (4)
>   Clang 18: add/remove: 0/0 grow/shrink: 2/3 up/down: 44/-82 (-38)
> mm_core_init -2 and dw_pcie_irq_domain_alloc -4 come from byte-identical
> objects and change at link time (relaxation). On loongarch32 with
> CONFIG_IKHEADERS only kernel_headers_data changes (-800 bytes).
> 
> Performance is model-only: no affected architecture could be timed on
> hardware. llvm-mca 17/18 ran on every executed path for the SiFive
> U74/E76/P450, Rocket and SCR1 models; m68k, sh, sparc32, xtensa,
> parisc, openrisc, loongarch32 and microblaze only got simple static
> issue models (and MC68000 instruction timings). Of 648 changed
> compiler/target/flags/function combinations, none is predicted slower
> except 20 riscv64 caller cases in which the out-of-order P450 model
> needs 1-2 more cycles on some inputs (-0.4% to +0.4% averaged over the
> inputs); the in-order SiFive-7 model is up to 4 cycles faster per
> __ffs() call. llvm-mca did not predict the slowdowns that this kind of
> reordering showed on x86 hardware (up to about 10% on single paths;
> x86 does not use this code), so this is weak evidence. Adjusting the
> result first everywhere is predicted slower for ffs()/fls() on every
> affected architecture, e.g. +3 cycles per ffs() call on the U74.
> 
> A loop with unrolled_full, against the current headers in userspace
> builds (GCC 9/12/13/14 and Clang 17/18, 75 compiler/target pairs, -O2,
> -Os and kernel-like -O2): out of line, GCC gives identical code in all
> 324 cases and Clang different code in 567 of 576, e.g. Clang 18 rv64
> fls() 33 -> 25 instructions but __ffs() 29 -> 31 and one more branch,
> Clang 17 ARMv4 ffs() 23 -> 37. Inlined into callers, GCC differs in 60
> of 324 cases.
> 
> UNROLL(20) rather than six steps: the extra steps vanish when
> optimizing, but not at -O0 or under Clang's GCOV instrumentation, where
> the four helpers out of line grow from 405 to 564 instructions and from
> 280 to 728 bytes of counters (Clang 18 riscv64; measured with the same
> expansion before the step order was unified).
> 
> tools/include/asm-generic/bitops/{fls,__fls}.h copy two of these
> headers, so tools/perf/check-headers.sh will report them as different.
> They cannot simply be resynced, since tools/include has no
> <linux/unroll.h> or ffs-fls-search.h; the current copies compute the
> same values, so keeping them, or dropping the two entries from
> check-headers.sh, is enough.
> 
> Testing details: all 2^32 arguments in 12 configurations and every 7th
> block of 2^16 in 51 more (GCC 8.1 to 16.2, LLVM 17 to 23), with no
> mismatch against the old code or an independent reference. W=1 vmlinux
> builds: arm multi_v4t, m68k m5475evb and m5208evb, sh rts7751r2dplus,
> sparc32, openrisc without ff1/fl1, parisc64, xtensa (custom core
> without NSA), loongarch32 (LA32R) and riscv with Zbb off, GCC 16.2,
> plus riscv with Clang 18. Not covered: hardware timing, and any model
> of the Clang 18 riscv changes; run-time tests on parisc64, loongarch32,
> microblaze, nios2, xtensa and SH-2A; other compiler versions in kernel
> builds; modules; sparse, smatch, coccinelle.
> 
> Against bitmap-for-next (a73b4d1fa7d3); applies as is to v7.3-rc7 and
> next-20261012, where the four headers are identical.

It's written in a great length indeed. I'm not sure I'm ready to walk
through all this wording, sorry.

>  include/asm-generic/bitops/__ffs.h          | 26 +----------
>  include/asm-generic/bitops/__fls.h          | 26 +----------
>  include/asm-generic/bitops/ffs-fls-search.h | 51 +++++++++++++++++++++
>  include/asm-generic/bitops/ffs.h            | 23 ++--------
>  include/asm-generic/bitops/fls.h            | 23 ++--------
>  5 files changed, 61 insertions(+), 88 deletions(-)
>  create mode 100644 include/asm-generic/bitops/ffs-fls-search.h
> 
> diff --git a/include/asm-generic/bitops/__ffs.h b/include/asm-generic/bitops/__ffs.h
> index 3a899c626f..ad5c014c62 100644
> --- a/include/asm-generic/bitops/__ffs.h
> +++ b/include/asm-generic/bitops/__ffs.h
> @@ -3,6 +3,7 @@
>  #define _ASM_GENERIC_BITOPS___FFS_H_
>  
>  #include <asm/types.h>
> +#include <asm-generic/bitops/ffs-fls-search.h>
>  
>  /**
>   * generic___ffs - find first bit in word.
> @@ -14,30 +15,7 @@ static __always_inline __attribute_const__ unsigned int generic___ffs(unsigned l
>  {
>  	unsigned int num = 0;
>  
> -#if BITS_PER_LONG == 64
> -	if ((word & 0xffffffff) == 0) {
> -		num += 32;
> -		word >>= 32;
> -	}
> -#endif
> -	if ((word & 0xffff) == 0) {
> -		num += 16;
> -		word >>= 16;
> -	}
> -	if ((word & 0xff) == 0) {
> -		num += 8;
> -		word >>= 8;
> -	}
> -	if ((word & 0xf) == 0) {
> -		num += 4;
> -		word >>= 4;
> -	}
> -	if ((word & 0x3) == 0) {
> -		num += 2;
> -		word >>= 2;
> -	}
> -	if ((word & 0x1) == 0)
> -		num += 1;
> +	__ffs_fls_unroll(__ffs_step, word, num);
>  	return num;
>  }
>  
> diff --git a/include/asm-generic/bitops/__fls.h b/include/asm-generic/bitops/__fls.h
> index 35f33780ca..1c439e881b 100644
> --- a/include/asm-generic/bitops/__fls.h
> +++ b/include/asm-generic/bitops/__fls.h
> @@ -3,6 +3,7 @@
>  #define _ASM_GENERIC_BITOPS___FLS_H_
>  
>  #include <asm/types.h>
> +#include <asm-generic/bitops/ffs-fls-search.h>
>  
>  /**
>   * generic___fls - find last (most-significant) set bit in a long word
> @@ -14,30 +15,7 @@ static __always_inline __attribute_const__ unsigned int generic___fls(unsigned l
>  {
>  	unsigned int num = BITS_PER_LONG - 1;
>  
> -#if BITS_PER_LONG == 64
> -	if (!(word & (~0ul << 32))) {
> -		num -= 32;
> -		word <<= 32;
> -	}
> -#endif
> -	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
> -		num -= 16;
> -		word <<= 16;
> -	}
> -	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
> -		num -= 8;
> -		word <<= 8;
> -	}
> -	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
> -		num -= 4;
> -		word <<= 4;
> -	}
> -	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
> -		num -= 2;
> -		word <<= 2;
> -	}
> -	if (!(word & (~0ul << (BITS_PER_LONG-1))))
> -		num -= 1;
> +	__ffs_fls_unroll(__fls_step, word, num);
>  	return num;
>  }
>  
> diff --git a/include/asm-generic/bitops/ffs-fls-search.h b/include/asm-generic/bitops/ffs-fls-search.h
> new file mode 100644
> index 0000000000..5c64364e54
> --- /dev/null
> +++ b/include/asm-generic/bitops/ffs-fls-search.h
> @@ -0,0 +1,51 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_
> +#define _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_
> +
> +#include <linux/unroll.h>
> +
> +/*
> + * Steps of a binary search for the first or last set bit of a word
> + * @i: the step number, from 0
> + * @x: the word, a local variable that the steps shift in place
> + * @n: the result, a local variable that the steps adjust in place
> + *
> + * Step @i looks at the low (__ffs_step) or high (__fls_step)
> + * __ffs_fls_shift(@i, @x) bits of @x: half of its width, then a quarter,
> + * and so on. If they are all zero, the step shifts them out of @x and adds
> + * their number to @n (__ffs_step) or subtracts it (__fls_step). @x is
> + * shifted before @n is adjusted: the next step tests @x, while @n is only
> + * needed at the end. The masks are computed in the type of @x.
> + *
> + * UNROLL() expands the steps in the preprocessor, so every shift and mask
> + * is an integer constant expression, as in a hand-written search. It puts
> + * the steps next to each other with nothing in between, hence the braces.
> + */
> +#define __ffs_fls_shift(i, x)	((int)sizeof(x) * 8 >> ((i) + 1))
> +#define __ffs_mask(i, x)	(((typeof(x))1 << __ffs_fls_shift(i, x)) - 1)
> +#define __fls_mask(i, x)	((typeof(x))~(~(typeof(x))0 >> __ffs_fls_shift(i, x)))
> +
> +#define __ffs_step(i, x, n)						\
> +	{								\
> +		if (!((x) & __ffs_mask(i, x))) {			\
> +			(x) >>= __ffs_fls_shift(i, x);			\
> +			(n) += __ffs_fls_shift(i, x);			\
> +		}							\
> +	}
> +
> +#define __fls_step(i, x, n)						\
> +	{								\
> +		if (!((x) & __fls_mask(i, x))) {			\
> +			(x) <<= __ffs_fls_shift(i, x);			\
> +			(n) -= __ffs_fls_shift(i, x);			\
> +		}							\
> +	}
> +
> +/*
> + * Six steps cover a 64-bit word. UNROLL() needs a literal count, which
> + * cannot be derived from sizeof(@x), so expand the most it supports. Steps
> + * past the width of @x shift by 0 and are optimized away.
> + */
> +#define __ffs_fls_unroll(step, x, n)	UNROLL(20, step, x, n)
> +
> +#endif /* _ASM_GENERIC_BITOPS_FFS_FLS_SEARCH_H_ */
> diff --git a/include/asm-generic/bitops/ffs.h b/include/asm-generic/bitops/ffs.h
> index 5ff2b7fbda..53705ba8c9 100644
> --- a/include/asm-generic/bitops/ffs.h
> +++ b/include/asm-generic/bitops/ffs.h
> @@ -2,6 +2,8 @@
>  #ifndef _ASM_GENERIC_BITOPS_FFS_H_
>  #define _ASM_GENERIC_BITOPS_FFS_H_
>  
> +#include <asm-generic/bitops/ffs-fls-search.h>
> +
>  /**
>   * generic_ffs - find first bit set
>   * @x: the word to search
> @@ -16,26 +18,7 @@ static inline __attribute_const__ int generic_ffs(int x)
>  
>  	if (!x)
>  		return 0;
> -	if (!(x & 0xffff)) {
> -		x >>= 16;
> -		r += 16;
> -	}
> -	if (!(x & 0xff)) {
> -		x >>= 8;
> -		r += 8;
> -	}
> -	if (!(x & 0xf)) {
> -		x >>= 4;
> -		r += 4;
> -	}
> -	if (!(x & 3)) {
> -		x >>= 2;
> -		r += 2;
> -	}
> -	if (!(x & 1)) {
> -		x >>= 1;
> -		r += 1;
> -	}
> +	__ffs_fls_unroll(__ffs_step, x, r);
>  	return r;
>  }
>  
> diff --git a/include/asm-generic/bitops/fls.h b/include/asm-generic/bitops/fls.h
> index 8eed3437ed..42625a0785 100644
> --- a/include/asm-generic/bitops/fls.h
> +++ b/include/asm-generic/bitops/fls.h
> @@ -2,6 +2,8 @@
>  #ifndef _ASM_GENERIC_BITOPS_FLS_H_
>  #define _ASM_GENERIC_BITOPS_FLS_H_
>  
> +#include <asm-generic/bitops/ffs-fls-search.h>
> +
>  /**
>   * generic_fls - find last (most-significant) bit set
>   * @x: the word to search
> @@ -16,26 +18,7 @@ static __always_inline __attribute_const__ int generic_fls(unsigned int x)
>  
>  	if (!x)
>  		return 0;
> -	if (!(x & 0xffff0000u)) {
> -		x <<= 16;
> -		r -= 16;
> -	}
> -	if (!(x & 0xff000000u)) {
> -		x <<= 8;
> -		r -= 8;
> -	}
> -	if (!(x & 0xf0000000u)) {
> -		x <<= 4;
> -		r -= 4;
> -	}
> -	if (!(x & 0xc0000000u)) {
> -		x <<= 2;
> -		r -= 2;
> -	}
> -	if (!(x & 0x80000000u)) {
> -		x <<= 1;
> -		r -= 1;
> -	}
> +	__ffs_fls_unroll(__fls_step, x, r);
>  	return r;
>  }

Alright, so the basic idea is to hide the exact implementation behind
the macro magic. This is highly unfavorable unless it brings substantial
improvement i.e. in code generation. In kernel we're drifting toward the
exactly opposite direction: getting rid of those macro tricks folded one
into another in favor of the plain human-readable code.

Please refer the recent __MAKE_OP() removal:

https://lore.kernel.org/all/20260914204929.240310-1-ynorov@nvidia.com/

In the bitops-related area you can find meta-programming approach, for
example, in lib/find_bit.c. Notice how the macros _help_ to highlight
implementation in there.

Thanks,
Yury

Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

[Tzu-Ching Yang]

On Fri, Oct 16, 2026 at 12:17:00PM -0400, Yury Norov wrote:
> Alright, so the basic idea is to hide the exact implementation behind
> the macro magic. This is highly unfavorable unless it brings substantial
> improvement i.e. in code generation. In kernel we're drifting toward the
> exactly opposite direction: getting rid of those macro tricks folded one
> into another in favor of the plain human-readable code.

Thanks for having a look and for the pointers, understood, and sorry
about the length of the description. I'm dropping this one and will
follow Arnd's suggestion instead, replacing custom arch helpers with
the builtins where that simplifies the code.

Thanks,
Tzu-Ching