Helper to isolate least-significant bit
Subsystems (27)
cover Helper to isolate least-significant bit
Isolation of the least significant bit can be achieved with 3 basic ALU operations which are already open-coded in various places in the kernel.
However, since other places less efficient constructs, for example 1UL << ffs(x), I assume the trick is known only to some authors, and it's worth adding a helper to promote its use.
Petr Tesarik (2):
bits: introduce ffs_val()
treewide, bits: use ffs_val() where it is open-coded
arch/alpha/include/asm/bitops.h | 2 +- arch/alpha/kernel/core_cia.c | 2 +- arch/alpha/kernel/smp.c | 2 +- arch/arc/include/asm/bitops.h | 2 +- arch/m68k/include/asm/bitops.h | 12 +++++------ arch/mips/dec/ecc-berr.c | 2 +- arch/mips/include/asm/bitops.h | 4 ++-- arch/mips/pci/pci-malta.c | 4 ++-- arch/powerpc/include/asm/bitops.h | 4 ++-- arch/powerpc/kvm/e500_mmu_host.c | 2 +- arch/powerpc/lib/sstep.c | 2 +- arch/powerpc/xmon/ppc-dis.c | 3 ++- arch/powerpc/xmon/ppc-opc.c | 6 +++--- arch/s390/include/asm/bitops.h | 2 +- arch/xtensa/include/asm/bitops.h | 6 +++--- arch/xtensa/kernel/traps.c | 2 +- drivers/gpu/drm/gma500/psb_intel_sdvo.c | 2 +- drivers/iommu/dma-iommu.c | 2 +- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +- drivers/net/usb/cdc_ncm.c | 4 ++-- include/asm-generic/div64.h | 4 ++-- include/linux/bitfield.h | 3 ++- include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 ++++++++++++++++++++ include/linux/log2.h | 2 +- include/linux/min_heap.h | 5 +++-- lib/math/gcd.c | 4 ++-- lib/sort.c | 3 ++- net/bluetooth/mgmt.c | 2 +- net/netfilter/nft_set_pipapo.c | 2 +- 30 files changed, 70 insertions(+), 44 deletions(-) create mode 100644 include/linux/ffs_val.h
Signature · 1 line
2.52.0
RFC PATCH 1/2 bits: introduce ffs_val()
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Define the macro in a separate header file included from <linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.
--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+) create mode 100644 include/linux/ffs_val.h
MAINTAINERS +1 -0
@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.h F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*
include/linux/bitops.h +1 -0
@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <uapi/linux/kernel.h>
include/linux/ffs_val.h new file +21 -0
@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit +* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself. +* +* Returns: +* least significant non-zero bit, 0 if all bits are zero +*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \ +}) + +#endif /* _ASM_LINUX_FFS_VAL_H_ */
Signature · 1 line
2.52.0
Arnd Bergmann
maintainerRe: [RFC PATCH 1/2] bits: introduce ffs_val()
include/linux/ffs_val.h line 19
Quoted 8 lines · Petr Tesarik
+ * Returns:
+ * least significant non-zero bit, 0 if all bits are zero
+ */include/linux/ffs_val.h new file +5
-0+#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \ +})
This looks good to me, but I'd suggest using 'const auto val__' instead of typeof(), to reduce expanding complex arguments twice.
Arnd
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 13 lines · On Fri, 09 Jan 2026 18:01:02 +0100 "Arnd Bergmann" <[email protected]> wrote:
include/linux/ffs_val.h line 19
Quoted 8 lines · Petr Tesarik
+ * Returns:
+ * least significant non-zero bit, 0 if all bits are zero
+ */include/linux/ffs_val.h new file +5
-0+#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \ +})This looks good to me, but I'd suggest using 'const auto
val__' instead oftypeof(), to reduce expanding complex arguments twice.
It is more usual to just use a single _ prefix and the same name. I wouldn't bother with 'const' either, maybe:
#define ffs_val(val) ({ \
auto _val = val; \
_val & -_val; \
})However it isn't necessarily better than using __ffs(). FIELD_PREP(mask, val) (for non-constant mask) can be (mask & -mask) * val or val << __ffs(mask).
So the 'ffs' version is fewer instructions (assuming non-zero mask). The timings for bsf/bsr are similar to those for imul on intel cpu, mul wins on zen3 and bsf/bsr on zen4.
On balance the __ffs() version is actually likely to be faster.
Other architectures may fair better or worse.
Clearly you don't want to use __ffs() unless it is a single instruction.
Of course, for FIELD_GET(reg, mask) you'd need reg/(mask & -mask) and the cost of the integer division is far more than __ffs(). (But that will give you a compile-time error if mask is a constant zero and the compiler will convert the divide to a shift.)
And for 64bit calculations on 32bit 'all bets are off'. Even the shift left might be problematic.
David
Quoted 3 lines
Arnd
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
In reply to Petr TesarikQuoted 11 lines · Petr Tesarik
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Define the macro in a separate header file included from <
linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.
Nice catch. Thanks!
Quoted 14 lines
Signed-off-by Petr Tesarik <[email protected]>--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+) create mode 100644 include/linux/ffs_val.hMAINTAINERS +0
-0
MAINTAINERS F: arch/*/lib/bitops.c · line 4469
Quoted 4 lines
MAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.h
No need for a separate header. Just put int straight in bitops.h.
Quoted 21 lines
MAINTAINERS +0
-0F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*include/linux/bitops.h +1
-0@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <uapi/linux/kernel.h> include/linux/ffs_val.h new file +0
-0
include/linux/ffs_val.h line 6
Quoted 6 lines
include/linux/ffs_val.h new file +6
-0@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit
By definition, the value of 1st set bit is 1, just like any other set bit. :)
include/linux/ffs_val.h line 17
Quoted 11 lines
include/linux/ffs_val.h new file +11
-0+* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself. +* +* Returns: +* least significant non-zero bit, 0 if all bits are zero +*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \
const auto? Also, are you sure it works OK with unsigned types? No warnings? Maybe add a test?
include/linux/ffs_val.h line 19
Quoted 2 lines
include/linux/ffs_val.h new file +2
-0+ val__ & -val__; \ +})
This macro returns in fact a mask containing LSB only, so I'd suggest to choose a name like lsb_mask().
This is also a replacement of BIT(ffs()), GENMASK(ffs(), 0) constructions. Can you check the kernel, and convert those patterns too? I found at least one in drivers/clk/nxp/clk-lpc32xx.c:lpc32xx_clk_div_quirk().
Thanks,
Yury
Quoted 4 lines
include/linux/ffs_val.h new file +2
-0+ +#endif /* _ASM_LINUX_FFS_VAL_H_ */ Signature · 1 line
2.52.0
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 9 lines · On Fri, 9 Jan 2026 12:16:06 -0500 Yury Norov <[email protected]> wrote:
Quoted 8 lines · Petr Tesarik
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Quoted 5 lines
Quoted 3 lines
Define the macro in a separate header file included from <
linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.Nice catch. Thanks!
It's been on my TODO list for months, but my first attempt failed because of a coccinelle bug, and then I never got to it again.
Quoted 8 lines
Quoted 8 lines
Signed-off-by Petr Tesarik <[email protected]>--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+) create mode 100644 include/linux/ffs_val.h
Quoted 11 lines
MAINTAINERS F: arch/*/lib/bitops.c · line 4469
Quoted 9 lines
MAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.hNo need for a separate header. Just put int straight in
bitops.h.
Well, <linux/bitops.h> is a bit heavy, so I was afraid of spoiling build times if I include it from <asm-generic/div64.h>, but if you say it's fine, yes, why not, let's put it into bitops.h somewhere before #include <asm/bitops.h>.
Quoted 14 lines
Quoted 14 lines
MAINTAINERS +0
-0F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*include/linux/bitops.h +1
-0@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h>
Quoted 16 lines
include/linux/ffs_val.h line 6
Quoted 13 lines
include/linux/bitops.h +0
-0#include <uapi/linux/kernel.h> include/linux/ffs_val.h new file +6
-0@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit By definition, the value of 1st set bit is 1, just like any other set bit. :)
I'm struggling with suitable wording. The trouble is that "find first set bit" is generally understood as find the bit _position_. Maybe I should say _isolate_ the bit, or something like that.
Quoted 6 lines
Quoted 6 lines
include/linux/ffs_val.h new file +6
-0+* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself. +* +* Returns:
Quoted 8 lines
include/linux/ffs_val.h line 17
Quoted 5 lines
include/linux/ffs_val.h new file +5
-0+* least significant non-zero bit, 0 if all bits are zero +*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \const auto? Also, are you sure it works OK with unsigned types? No warnings? Maybe add a test?
The "const auto" is good idea. Regarding unsigned types, indeed, the result of applying unary minus to any non-zero value is out of bounds of an unsigned type. However, the C standard has this much to say:
"C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense in that overflows or out-of-bounds results silently wrap."
Besides, this patch series does not change anything, it merely puts the arithmetic inside a macro.
Quoted 5 lines
include/linux/ffs_val.h line 19
Quoted 2 lines
include/linux/ffs_val.h new file +2
-0+ val__ & -val__; \ +})This macro returns in fact a mask containing LSB only, so I'd suggest to choose a name like
lsb_mask().
Mask is a terrible word, because it doesn't say if the masked bit is set or clear. Even if I limit myself to the Linux kernel, it's used for both in different contexts.
What about isolate_lsb()?
The only issue is that LSB may also refer to least-significant BYTE. :-(
Quoted 3 lines
This is also a replacement of BIT(ffs()),
GENMASK(ffs(), 0)constructions. Can you check the kernel, and convert those patterns too? I found at least one in drivers/clk/nxp/clk-lpc32xx.c:lpc32xx_clk_div_quirk().
Yes, there's a lot of places under drivers/ that can benefit from this macro. I didn't want to spam everyone with this RFC, as we iron out the details. I'm even unsure about the correct process to get such a change into the kernel.
Thanks for the review and suggestions!
Petr T
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 6 lines
Quoted 1 line
No need for a separate header. Just put int straight in
bitops.h.Well, <
linux/bitops.h> is a bit heavy, so I was afraid of spoiling build times if I include it from <asm-generic/div64.h>, but if you say it's fine, yes, why not, let's put it intobitops.hsomewhere before #include <asm/bitops.h>.
Unless you have strong performance numbers, let's keep it in the bitops.h
Quoted 40 lines
Quoted 5 lines
Quoted 2 lines
+/**
+ *ffs_val- find the value of the first set bitBy definition, the value of 1st set bit is 1, just like any other set bit. :)
I'm struggling with suitable wording. The trouble is that "find first set bit" is generally understood as find the bit _position_. Maybe I should say _isolate_ the bit, or something like that.
Quoted 6 lines
Quoted 6 lines
+ * @x: the value to search
+ *
+ * Unlikeffs(), which returns a bit position,ffs_val()returns the bit
+ * value itself.
+ *
+ * Returns:Quoted 8 lines
include/linux/ffs_val.h line 17
Quoted 5 lines
+ * least significant non-zero bit, 0 if all bits are zero
+ */include/linux/ffs_val.h new file +3
-0+#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \const auto? Also, are you sure it works OK with unsigned types? No warnings? Maybe add a test?
The "const auto" is good idea. Regarding unsigned types, indeed, the result of applying unary minus to any non-zero value is out of bounds of an unsigned type. However, the C standard has this much to say:
"C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense in that overflows or out-of-bounds results silently wrap."Besides, this patch series does not change anything, it merely puts the arithmetic inside a macro.
Quoted 5 lines
include/linux/ffs_val.h line 19
Quoted 2 lines
include/linux/ffs_val.h new file +2
-0+ val__ & -val__; \ +})This macro returns in fact a mask containing LSB only, so I'd suggest to choose a name like
lsb_mask().
Quoted 5 lines
Mask is a terrible word, because it doesn't say if the masked bit is set or clear. Even if I limit myself to the Linux kernel, it's used for both in different contexts.
What about
isolate_lsb()?
In bitops world, something_mask() has a very clear meaning. Consider GENMASK(), BITMAP_FIRST_BYTE_MASK(), __BF_FIELD_CHECK_MASK(), and so on.
lsb_mask(), or LSB_MASK() if you prefer, is just right.
Quoted 1 line
The only issue is that LSB may also refer to least-significant BYTE. :-(
It will never mean byte because it hosts in bitops.h, not byteops.h
Quoted 8 lines
Quoted 3 lines
This is also a replacement of BIT(ffs()),
GENMASK(ffs(), 0)constructions. Can you check the kernel, and convert those patterns too? I found at least one in drivers/clk/nxp/clk-lpc32xx.c:lpc32xx_clk_div_quirk().Yes, there's a lot of places under
drivers/that can benefit from this macro. I didn't want to spam everyone with this RFC, as we iron out the details. I'm even unsure about the correct process to get such a change into the kernel.
If you don't want to fix every driver, it's OK. But please keep core kernel clean.
Quoted 4 lines
Thanks for the review and suggestions!
Petr T
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 9 lines · On Fri, 9 Jan 2026 13:26:30 -0500 Yury Norov <[email protected]> wrote:
Quoted 6 lines
Quoted 1 line
No need for a separate header. Just put int straight in
bitops.h.Well, <
linux/bitops.h> is a bit heavy, so I was afraid of spoiling build times if I include it from <asm-generic/div64.h>, but if you say it's fine, yes, why not, let's put it intobitops.hsomewhere before #include <asm/bitops.h>.Unless you have strong performance numbers, let's keep it in the
bitops.h
OK.
Quoted 44 lines
Quoted 44 lines
Quoted 5 lines
Quoted 2 lines
+/**
+ *ffs_val- find the value of the first set bitBy definition, the value of 1st set bit is 1, just like any other set bit. :)
I'm struggling with suitable wording. The trouble is that "find first set bit" is generally understood as find the bit _position_. Maybe I should say _isolate_ the bit, or something like that.
Quoted 6 lines
Quoted 6 lines
+ * @x: the value to search
+ *
+ * Unlikeffs(), which returns a bit position,ffs_val()returns the bit
+ * value itself.
+ *
+ * Returns:Quoted 8 lines
include/linux/ffs_val.h line 17
Quoted 5 lines
+ * least significant non-zero bit, 0 if all bits are zero
+ */include/linux/ffs_val.h new file +3
-0+#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \const auto? Also, are you sure it works OK with unsigned types? No warnings? Maybe add a test?
The "const auto" is good idea. Regarding unsigned types, indeed, the result of applying unary minus to any non-zero value is out of bounds of an unsigned type. However, the C standard has this much to say:
"C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense in that overflows or out-of-bounds results silently wrap."Besides, this patch series does not change anything, it merely puts the arithmetic inside a macro.
Quoted 5 lines
include/linux/ffs_val.h line 19
Quoted 2 lines
include/linux/ffs_val.h new file +2
-0+ val__ & -val__; \ +})This macro returns in fact a mask containing LSB only, so I'd suggest to choose a name like
lsb_mask().Mask is a terrible word, because it doesn't say if the masked bit is set or clear. Even if I limit myself to the Linux kernel, it's used for both in different contexts.
Quoted 7 lines
Quoted 1 line
What about
isolate_lsb()?In bitops world,
something_mask()has a very clear meaning. ConsiderGENMASK(),BITMAP_FIRST_BYTE_MASK(),__BF_FIELD_CHECK_MASK(), and so on.
lsb_mask(), orLSB_MASK()if you prefer, is just right.
I assume you mean BITMAP_FIRST_WORD_MASK(), not btrfs-specific BITMAP_FIRST_BYTE_MASK(), defined in fs/btrfs/extent_io.h.
But then it nicely illustrate exactly what I mean:
BIT_MASK(4) = 0x0000000000000010
GENMASK(4, 0) = 0x000000000000001f
BITMAP_FIRST_WORD_MASK(4) == 0xfffffffffffffff0
Quoted 3 lines
Quoted 1 line
The only issue is that LSB may also refer to least-significant BYTE. :-(
It will never mean byte because it hosts in
bitops.h, notbyteops.h
I'm afraid that identifiers from various sources end up next to each other and they do not carry tags where each of them came from...
Quoted 11 lines
Quoted 8 lines
Quoted 3 lines
This is also a replacement of BIT(ffs()),
GENMASK(ffs(), 0)constructions. Can you check the kernel, and convert those patterns too? I found at least one in drivers/clk/nxp/clk-lpc32xx.c:lpc32xx_clk_div_quirk().Yes, there's a lot of places under
drivers/that can benefit from this macro. I didn't want to spam everyone with this RFC, as we iron out the details. I'm even unsure about the correct process to get such a change into the kernel.If you don't want to fix every driver, it's OK. But please keep core kernel clean.
Yes, getting acks from all maintainers will take a lot of time even then.
Again, thank you for all the tips!
Petr T
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 2 lines · Petr Tesarik
On Fri, 9 Jan 2026 13:26:30 -0500
Yury Norov <[email protected]> wrote:
...
Quoted 10 lines
Quoted 5 lines
In bitops world,
something_mask()has a very clear meaning. ConsiderGENMASK(),BITMAP_FIRST_BYTE_MASK(),__BF_FIELD_CHECK_MASK(), and so on.
lsb_mask(), orLSB_MASK()if you prefer, is just right.I assume you mean
BITMAP_FIRST_WORD_MASK(), not btrfs-specificBITMAP_FIRST_BYTE_MASK(), defined infs/btrfs/extent_io.h.But then it nicely illustrate exactly what I mean:
They all have a consistent meaning:
Quoted 1 line
BIT_MASK(4)=0x0000000000000010
A mask constructed from bit #4.
Quoted 1 line
GENMASK(4, 0)=0x000000000000001f
A mask constructed from bits #0..4.
Quoted 1 line
BITMAP_FIRST_WORD_MASK(4)==0xfffffffffffffff0
A mask constructed from all bits starting #4.
Don't see any misalignment here.
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
The only issue is that LSB may also refer to least-significant BYTE. :-(
It will never mean byte because it hosts in
bitops.h, notbyteops.hI'm afraid that identifiers from various sources end up next to each other and they do not carry tags where each of them came from...
You can name it lsb_bitmask() if you want, either way works. But to me shorter is better.
Arnd Bergmann
maintainerRe: [RFC PATCH 1/2] bits: introduce ffs_val()
In reply to Petr TesarikQuoted 13 lines · Petr Tesarik
Quoted 11 lines · On Fri, 9 Jan 2026 12:16:06 -0500 Yury Norov <[email protected]> wrote:
MAINTAINERS F: arch/*/lib/bitops.c · line 4469
Quoted 9 lines
MAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.hNo need for a separate header. Just put int straight in
bitops.h.
Quoted 4 lines
Well, <
linux/bitops.h> is a bit heavy, so I was afraid of spoiling build times if I include it from <asm-generic/div64.h>, but if you say it's fine, yes, why not, let's put it intobitops.hsomewhere before #include <asm/bitops.h>.
A single macro definition makes zero difference for build times.
What makes linux/bitops.h expensive is the 419kb of preprocessed source code that result from the generated atomics in asm/bitops.h that get included everywhere.
Arnd
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
In reply to Petr TesarikQuoted 7 lines · On Fri, 9 Jan 2026 17:37:56 +0100 Petr Tesarik <[email protected]> wrote:
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
I'm not sure whether ffs_val(x) is actually more readable than an open-coded (x & -x).
If you don't know what either means you have to look it up or work it out.
The latter just requires a bit of thought, the former searching through the source tree for the correct header and then believing the comment or, again, working out what it does.
That said, I'm not objecting to adding it, but the churn of changing existing code is probably not worth the effort.
I'd also define it as x & (~x + 1) - which makes it a lot more obvious why it is correct, the compiler will convert it to a signed negate.
Also, as I pointed out earlier, many modern cpu have an instruction for ffs(). While x & -x is usualy better than 1u << __ffs(x); the same is not true for y * (x & -x) and y << __ffs(x).
In particular on Zen4/5 bsf (used for __ffs) has a latency of 1 but the multiply has a latency of 3.
Intel mainstream x86 cpu all have latency 3 for both imul and bsf.
There should be #define definitions of is_power_of_2_or_zero() !(x + (x-1)) and is_power_of_2() (!x && is_power_of_2_or_zero(x)) in the same header. But there is only an inline is_power_of_2(unsigned long) in log.h.
David
Thomas Zimmermann
maintainerRe: [RFC PATCH 1/2] bits: introduce ffs_val()
In reply to Petr TesarikHi Petr
Am 09.01.26 um 17:37 schrieb Petr Tesarik:
Quoted 50 lines
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Define the macro in a separate header file included from <
linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.Signed-off-by Petr Tesarik <[email protected]>--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+)create mode 100644
include/linux/ffs_val.hMAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.h F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*include/linux/bitops.h +1
-0@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <uapi/linux/kernel.h> include/linux/ffs_val.h new file +0
-0
include/linux/ffs_val.h line 10
Quoted 10 lines
include/linux/ffs_val.h new file +10
-0@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit +* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself.
This sentence was confusing me at first, because the individual bit's value is always '1'. Maybe say something more descriptive, such as 'ffs_val returns the value resulting from that bit's position.'
include/linux/ffs_val.h line 13
Quoted 3 lines
include/linux/ffs_val.h new file +3
-0+* +* Returns: +* least significant non-zero bit, 0 if all bits are zero
Same here.
include/linux/ffs_val.h line 18
Quoted 5 lines
include/linux/ffs_val.h new file +5
-0+*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \
Is this construct supposed to work with signed integers and/or negative numbers? I assume that two's complement can be expected nowadays, but for LONG_MIN it returns zero AFAICT. The documentation should mention these cases.
Best regards
Thomas
Quoted 3 lines
include/linux/ffs_val.h new file +3
-0+}) + +#endif /* _ASM_LINUX_FFS_VAL_H_ */
Signature · 6 lines
-- Thomas Zimmermann Graphics Driver Developer SUSE Software Solutions Germany GmbH Frankenstr. 146, 90461 Nürnberg, Germany, www.suse.com GF: Jochen Jaser, Andrew McDonald, Werner Knoblich, (HRB 36809, AG Nürnberg)
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 59 lines · On Mon, 12 Jan 2026 09:15:41 +0100 Thomas Zimmermann <[email protected]>…
Hi Petr
Am 09.01.26 um 17:37 schrieb Petr Tesarik:
Quoted 56 lines
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Define the macro in a separate header file included from <
linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.Signed-off-by Petr Tesarik <[email protected]>--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+)create mode 100644
include/linux/ffs_val.hMAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.h F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*include/linux/bitops.h +1
-0@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <uapi/linux/kernel.h> include/linux/ffs_val.h new file +6
-0@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit
Quoted 8 lines
include/linux/ffs_val.h line 10
Quoted 4 lines
include/linux/ffs_val.h new file +4
-0+* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself. This sentence was confusing me at first, because the individual bit's value is always '1'. Maybe say something more descriptive, such as '
ffs_valreturns the value resulting from that bit's position.'
I think I found the best wording only when composing the cover letter:
isolate the least significant set bit. I should have gone back and adjusted the patches, too.
Quoted 6 lines
include/linux/ffs_val.h line 13
Quoted 3 lines
include/linux/ffs_val.h new file +3
-0+* +* Returns: +* least significant non-zero bit, 0 if all bits are zero Same here.
Quoted 10 lines
include/linux/ffs_val.h line 18
Quoted 5 lines
include/linux/ffs_val.h new file +5
-0+*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \Is this construct supposed to work with signed integers and/or negative numbers? I assume that two's complement can be expected nowadays, but for
LONG_MINit returns zero AFAICT. The documentation should mention these cases.
It works fine for all numbers: -LONG_MIN is LONG_MIN, and that is incidentally the number with only the least significant bit set.
But this is all moot. After reading some other replies, I'm not even sure, this helper adds any value. I'm going to start over by converting occurrences of x & -x with the most suitable existing helper, and see if there's still some value then.
Last but not least, if there's no good self-explanatory name for this operation, then I'm told that open-coding "x & -x" is in fact easier to read. Then again, this is the opinion of people who coded back in the 1980s, and my general feeling is that bit operations are generally less well understood by people born after 2000...
Glad to spark a bikeshedding flamewar, anyway. /s
Petr T
Re: [RFC PATCH 1/2] bits: introduce ffs_val()
In reply to Thomas ZimmermannQuoted 59 lines · On Mon, 12 Jan 2026 09:15:41 +0100 Thomas Zimmermann <[email protected]>…
Hi Petr
Am 09.01.26 um 17:37 schrieb Petr Tesarik:
Quoted 56 lines
Introduce a macro that can efficiently extract the least significant non-zero bit from a value.
Interestingly, this bit-twiddling trick is open-coded in some places, but it also appears to be little known, leading to various inefficient implementations in other places. Let's make it part of the standard bitops arsenal.
Define the macro in a separate header file included from <
linux/bitops.h>, to allow using it in very low-level header files that may not want to include all of <linux/bitops.h>.Signed-off-by Petr Tesarik <[email protected]>--- MAINTAINERS | 1 + include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 +++++++++++++++++++++ 3 files changed, 23 insertions(+)create mode 100644
include/linux/ffs_val.hMAINTAINERS +1
-0@@ -4466,6 +4466,7 @@ F: arch/*/lib/bitops.c F: include/asm-generic/bitops F: include/asm-generic/bitops.h F: include/linux/bitops.h +F: include/linux/ffs_val.h F: lib/hweight.c F: lib/test_bitops.c F: tools/*/bitops*include/linux/bitops.h +1
-0@@ -4,6 +4,7 @@#include <asm/types.h> #include <linux/bits.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <uapi/linux/kernel.h> include/linux/ffs_val.h new file +6
-0@@ -0,0 +1,21 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _ASM_LINUX_FFS_VAL_H_ +#define _ASM_LINUX_FFS_VAL_H_ + +/** +* ffs_val - find the value of the first set bit
Quoted 8 lines
include/linux/ffs_val.h line 10
Quoted 4 lines
include/linux/ffs_val.h new file +4
-0+* @x: the value to search +* +* Unlike ffs(), which returns a bit position, ffs_val() returns the bit +* value itself. This sentence was confusing me at first, because the individual bit's value is always '1'. Maybe say something more descriptive, such as '
ffs_valreturns the value resulting from that bit's position.'
An example would clarify things massively.
Perhaps ffs_val(0x40100) is 0x100.
Quoted 6 lines
include/linux/ffs_val.h line 13
Quoted 3 lines
include/linux/ffs_val.h new file +3
-0+* +* Returns: +* least significant non-zero bit, 0 if all bits are zero Same here.
Quoted 10 lines
include/linux/ffs_val.h line 18
Quoted 5 lines
include/linux/ffs_val.h new file +5
-0+*/ +#define ffs_val (x) \ +({ \ + const typeof(x) val__ = (x); \ + val__ & -val__; \Is this construct supposed to work with signed integers and/or negative numbers? I assume that two's complement can be expected nowadays, but for
LONG_MINit returns zero AFAICT. The documentation should mention these cases.
Writing as 'x & (~x + 1)' makes it pretty obvious that it is always valid. For two's compliment '-x == ~x + 1' and the compiler will do the transformation. That expression would also be valid for one's compliment and sign overpunch systems - but the result for negative values might be unexpected!
OTOH I'm pretty sure most modern C code assumes two's compliment binary numbers (and NULL being the all-zero bit pattern).
You'd have grief trying to compile C for an ICL System-25 - decimal/BCD numbers with sign overpunch and addresses binary_page * 10000 + BCD_offset. (Still in use in the late 1980s.)
David
Quoted 8 lines
Best regards
ThomasQuoted 3 lines
include/linux/ffs_val.h new file +3
-0+}) + +#endif /* _ASM_LINUX_FFS_VAL_H_ */
Maciej W. Rozycki
maintainerRe: [RFC PATCH 1/2] bits: introduce ffs_val()
Quoted 2 lines · David Laight
OTOH I'm pretty sure most modern C code assumes two's compliment binary numbers (and NULL being the all-zero bit pattern).
FWIW ISO C23 mandates the two's complement integer sign representation.
Other sign representations are no longer allowed.
Maciej
RFC PATCH 2/2 treewide, bits: use ffs_val() where it is open-coded
In reply to Petr TesarikReplace the open-coded bit-twiddling trick to get the least significant bit with a call to ffs_val().
This patch has been generated by the following coccinelle script:
@
depends on !(file in "include/asm-generic/bitops/ffs_val.h")
&& !(file in "tools/")
@
expression E;
@@
- ((E) & (-(E)))
+ ffs_val(E)
Include <linux/ffs_val.h> where the result did not build.
--- arch/alpha/include/asm/bitops.h | 2 +- arch/alpha/kernel/core_cia.c | 2 +- arch/alpha/kernel/smp.c | 2 +- arch/arc/include/asm/bitops.h | 2 +- arch/m68k/include/asm/bitops.h | 12 ++++++------ arch/mips/dec/ecc-berr.c | 2 +- arch/mips/include/asm/bitops.h | 4 ++-- arch/mips/pci/pci-malta.c | 4 ++-- arch/powerpc/include/asm/bitops.h | 4 ++-- arch/powerpc/kvm/e500_mmu_host.c | 2 +- arch/powerpc/lib/sstep.c | 2 +- arch/powerpc/xmon/ppc-dis.c | 3 ++- arch/powerpc/xmon/ppc-opc.c | 6 +++--- arch/s390/include/asm/bitops.h | 2 +- arch/xtensa/include/asm/bitops.h | 6 +++--- arch/xtensa/kernel/traps.c | 2 +- drivers/gpu/drm/gma500/psb_intel_sdvo.c | 2 +- drivers/iommu/dma-iommu.c | 2 +- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +- drivers/net/usb/cdc_ncm.c | 4 ++-- include/asm-generic/div64.h | 4 ++-- include/linux/bitfield.h | 3 ++- include/linux/log2.h | 2 +- include/linux/min_heap.h | 5 +++-- lib/math/gcd.c | 4 ++-- lib/sort.c | 3 ++- net/bluetooth/mgmt.c | 2 +- net/netfilter/nft_set_pipapo.c | 2 +- 28 files changed, 48 insertions(+), 44 deletions(-)
arch/alpha/include/asm/bitops.h +1 -1
@@ -317,7 +317,7 @@ static inline unsigned long ffz_b(unsigned long x) {unsigned long sum, x1, x2, x4; - x = ~x & -~x;/* set first 0 bit, clear others */ + x =ffs_val (~x);/* set first 0 bit, clear others */ x1 = x &0xAA ; x2 = x &0xCC ; x4 = x &0xF0 ;
arch/alpha/kernel/core_cia.c +1 -1
@@ -1035,7 +1035,7 @@ cia_decode_ecc_error(struct el_CIA_sysdata_mcheck *cia, const char *msg)cia_decode_mem_error (cia, msg); syn = cia->cia_syn &0xff ; -if (syn == (syn & -syn)) { +if (syn ==ffs_val (syn)) { fmt =KERN_CRIT " ECC syndrome %#x -- check bit %d\n" ; i =ffs (syn) -1 ; }else {
arch/alpha/kernel/smp.c +1 -1
@@ -525,7 +525,7 @@ handle_ipi(struct pt_regs *regs) do { unsigned long which; - which = ops & -ops; + which = ffs_val(ops); ops &= ~which; which = __ffs(which);
arch/arc/include/asm/bitops.h +1 -1
@@ -94,7 +94,7 @@ static inline __attribute__ ((const)) unsigned long __fls(unsigned long x)* ffs = Find First Set in word (LSB to MSB) * @result: [1-32], 0 if all 0's */ -#define ffs (x) ({ unsigned long __t = (x); fls(__t & -__t); }) +#define ffs (x) ({ unsigned long __t = (x); fls(ffs_val(__t)); })/* * __ffs: Similar to ffs, but zero based (0-31)
arch/m68k/include/asm/bitops.h +6 -6
@@ -368,7 +368,7 @@ static inline unsigned long find_first_zero_bit(const unsigned long *vaddr, } __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num))); res ^=31 ; out: res += ((long )p - (long )vaddr -4 ) *8 ;
@@ -392,7 +392,7 @@ static inline unsigned long find_next_zero_bit(const unsigned long *vaddr,/* Look for zero in first longword */ __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num)));if (res <32 ) { offset += res ^31 ;return offset < size ? offset : size;
@@ -425,7 +425,7 @@ static inline unsigned long find_first_bit(const unsigned long *vaddr, } __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num))); res ^=31 ; out: res += ((long )p - (long )vaddr -4 ) *8 ;
@@ -449,7 +449,7 @@ static inline unsigned long find_next_bit(const unsigned long *vaddr,/* Look for one in first longword */ __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num)));if (res <32 ) { offset += res ^31 ;return offset < size ? offset : size;
@@ -473,7 +473,7 @@ static inline unsigned long __attribute_const__ ffz(unsigned long word)int res; __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (~word & -~word)); + :"=d" (res) :"d" (ffs_val (~word)));return res ^31 ; }
@@ -527,7 +527,7 @@ static inline __attribute_const__ int ffs(int x) __asm__ ("bfffo %1{#0:#0},%0" :"=d" (cnt) - :"dm" (x & -x)); + :"dm" (ffs_val (x)));return 32 - cnt; }
arch/mips/dec/ecc-berr.c +1 -1
@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack (); -if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {if (syn ==0x01 ) { fmt =KERN_ALERT "%s" "%#04x -- %s bit error "
arch/mips/include/asm/bitops.h +2 -2
@@ -395,7 +395,7 @@ static __always_inline __attribute_const__ unsigned long __fls(unsigned long wor*/ static __always_inline __attribute_const__ unsigned long __ffs(unsigned long word) { -return __fls (word & -word); +return __fls (ffs_val (word)); }/*
@@ -463,7 +463,7 @@ static inline __attribute_const__ int ffs(int word)if (!word)return 0 ; -return fls (word & -word); +return fls (ffs_val (word)); }#include <asm-generic/bitops/ffz.h>
arch/mips/pci/pci-malta.c +2 -2
@@ -117,7 +117,7 @@ void __init mips_pcibios_init(void) mask = ~(start ^ end);/* We don't support remapping with a discontiguous mask. */ BUG_ON ((start >_PCI_HD_MSK ) != (map >_PCI_HD_MSK ) && - mask != ~((mask & -mask) -1 )); + mask != ~(ffs_val (mask) -1 )); gt64120_mem_resource.start = start; gt64120_mem_resource.end = end; gt64120_controller.mem_offset = (start & mask) - (map & mask);
@@ -134,7 +134,7 @@ void __init mips_pcibios_init(void) mask = ~(start ^ end);/* We don't support remapping with a discontiguous mask. */ BUG_ON ((start >_PCI_HD_MSK ) != (map >_PCI_HD_MSK ) && - mask != ~((mask & -mask) -1 )); + mask != ~(ffs_val (mask) -1 )); gt64120_io_resource.start = map & mask; gt64120_io_resource.end = (map & mask) | ~mask; gt64120_controller.io_offset =0 ;
arch/powerpc/include/asm/bitops.h +2 -2
@@ -87,8 +87,8 @@ static __always_inline bool is_rlwinm_mask_valid(unsigned long x)if (!x)return false;if (x &1 ) - x = ~x;// make the mask non-wrapping - x += x & -x;// adding the low set bit results in at most one bit set + x = ~x;// make the mask non-wrapping + x +=ffs_val (x);// adding the low set bit results in at most one bit set return !(x & (x -1 )); }
arch/powerpc/kvm/e500_mmu_host.c +1 -1
@@ -205,7 +205,7 @@ void inval_gtlbe_on_host(struct kvmppc_vcpu_e500 *vcpu_e500, int tlbsel,local_irq_save (flags);while (tmp) { - hw_tlb_indx =__ilog2_u64 (tmp & -tmp); + hw_tlb_indx =__ilog2_u64 (ffs_val (tmp));mtspr (SPRN_MAS0 ,MAS0_TLBSEL (1 ) |MAS0_ESEL (to_htlb1_esel (hw_tlb_indx)));
arch/powerpc/lib/sstep.c +1 -1
@@ -236,7 +236,7 @@ static nokprobe_inline unsigned long mlsd_8lsd_ea(unsigned int instr,static nokprobe_inline unsigned long max_align (unsigned long x) { x |=sizeof (unsigned long ); -return x & -x;/* isolates rightmost bit */ +return ffs_val (x);/* isolates rightmost bit */ }static nokprobe_inline unsigned long byterev_2 (unsigned long x)
arch/powerpc/xmon/ppc-dis.c +2 -1
@@ -9,6 +9,7 @@ This file is part of GDB, GAS, and the GNU binutils.#include <asm/cputable.h> #include <asm/cpu_has_feature.h> +#include <linux/ffs_val.h> #include "nonstdio.h" #include "ansidecl.h" #include "ppc.h"
@@ -44,7 +45,7 @@ operand_value_powerpc (const struct powerpc_operand *operand,unsigned long top = operand->bitm;/* top & -top gives the rightmost 1 bit, so this fills in any trailing zeros. */ - top |= (top & -top) -1 ; + top |=ffs_val (top) -1 ; top &= ~(top >>1 ); value = (value ^ top) - top; }
arch/powerpc/xmon/ppc-opc.c +3 -3
@@ -1417,7 +1417,7 @@ insert_fxm (unsigned long insn,one bit of the mask field is set. */ if ((insn & (1 <<20 )) !=0 ) { -if (value ==0 || (value & -value) != value) +if (value ==0 ||ffs_val (value) != value) { *errmsg =_ ("invalid mask field" ); value =0 ;
@@ -1430,7 +1430,7 @@ insert_fxm (unsigned long insn,new form unless -mpower4 has been given, or -many and the two operand form of mfcr was used. */ else if (value > 0 - && (value & -value) == value + &&ffs_val (value) == value && ((dialect &PPC_OPCODE_POWER4 ) !=0 || ((dialect &PPC_OPCODE_ANY ) !=0 && (insn & (0x3ff << 1)) == 19 << 1)))
@@ -1460,7 +1460,7 @@ extract_fxm (unsigned long insn,if ((insn & (1 <<20 )) !=0 ) {/* Exactly one bit of MASK should be set. */ -if (mask ==0 || (mask & -mask) != mask) +if (mask ==0 ||ffs_val (mask) != mask) *invalid =1 ; }
arch/s390/include/asm/bitops.h +1 -1
@@ -193,7 +193,7 @@ static __always_inline __flatten __attribute_const__ int ffs(int word) {unsigned int val = (unsigned int )word; -return BITS_PER_LONG -__flogr (-val & val); +return BITS_PER_LONG -__flogr (ffs_val (val)); }#else /* CONFIG_CC_HAS_BUILTIN_FFS */
arch/xtensa/include/asm/bitops.h +3 -3
@@ -39,7 +39,7 @@ static inline unsigned long __cntlz (unsigned long x) static inline int __attribute_const__ ffz(unsigned long x) { -return 31 -__cntlz (~x & -~x); +return 31 -__cntlz (ffs_val (~x)); }/*
@@ -48,7 +48,7 @@ static inline int __attribute_const__ ffz(unsigned long x)static inline __attribute_const__ unsigned long __ffs (unsigned long x) { -return 31 -__cntlz (x & -x); +return 31 -__cntlz (ffs_val (x)); }/*
@@ -59,7 +59,7 @@ static inline __attribute_const__ unsigned long __ffs(unsigned long x) static inline __attribute_const__ int ffs(unsigned long x) { -return 32 -__cntlz (x & -x); +return 32 -__cntlz (ffs_val (x)); }/*
arch/xtensa/kernel/traps.c +1 -1
@@ -309,7 +309,7 @@ static void do_interrupt(struct pt_regs *regs)break ;/* clear lowest pending irq in the unhandled mask */ - unhandled ^= (int_at_level & -int_at_level); + unhandled ^=ffs_val (int_at_level);do_IRQ (__ffs (int_at_level), regs); }
drivers/gpu/drm/gma500/psb_intel_sdvo.c +1 -1
@@ -1226,7 +1226,7 @@ psb_intel_sdvo_multifunc_encoder(struct psb_intel_sdvo *psb_intel_sdvo) {/* Is there more than one type of output? */ int caps = psb_intel_sdvo->caps.output_flags &0xf ; -return caps & -caps; +return ffs_val (caps); } static struct edid *
drivers/iommu/dma-iommu.c +1 -1
@@ -943,7 +943,7 @@ static struct page **__iommu_dma_alloc_noncontiguous(struct device *dev, iommu_deferred_attach(dev, domain))return NULL ; - min_size = alloc_sizes & -alloc_sizes; + min_size =ffs_val (alloc_sizes);if (min_size <PAGE_SIZE ) { min_size =PAGE_SIZE ; alloc_sizes |=PAGE_SIZE ;
drivers/net/ethernet/netronome/nfp/bpf/jit.c +1 -1
@@ -1565,7 +1565,7 @@ static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm) rvalue =reciprocal_value_adv (imm,32 ); exp = rvalue.exp;if (rvalue.is_wide_m && !(imm &1 )) { - pre_shift =fls (imm & -imm) -1 ; + pre_shift =fls (ffs_val (imm)) -1 ; rvalue =reciprocal_value_adv (imm >> pre_shift,32 - pre_shift); }else { pre_shift =0 ;
drivers/net/usb/cdc_ncm.c +2 -2
@@ -668,7 +668,7 @@ static void cdc_ncm_fix_modulus(struct usbnet *dev) val = ctx->tx_ndp_modulus;if ((val <USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ) || - (val != ((-val) & val)) || (val >= ctx->tx_max)) { + (val !=ffs_val (val)) || (val >= ctx->tx_max)) {dev_dbg (&dev->intf->dev,"Using default alignment: 4 bytes\n" ); ctx->tx_ndp_modulus =USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ; }
@@ -682,7 +682,7 @@ static void cdc_ncm_fix_modulus(struct usbnet *dev) val = ctx->tx_modulus;if ((val <USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ) || - (val != ((-val) & val)) || (val >= ctx->tx_max)) { + (val !=ffs_val (val)) || (val >= ctx->tx_max)) {dev_dbg (&dev->intf->dev,"Using default transmit modulus: 4 bytes\n" ); ctx->tx_modulus =USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ; }
include/asm-generic/div64.h +2 -2
@@ -111,8 +111,8 @@ } \ \/* Reduce m / p to help avoid overflow handling later. */ \ - ___p /= (___m & -___m); \ - ___m /= (___m & -___m); \ + ___p /=ffs_val (___m); \ + ___m /=ffs_val (___m); \ \/* \ * Perform (m_bias + m * n) / (1 << 64). \
include/linux/bitfield.h +2 -1
@@ -8,6 +8,7 @@#define _LINUX_BITFIELD_H#include <linux/build_bug.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <asm/byteorder.h>
@@ -202,7 +203,7 @@ static __always_inline u64 field_multiplier(u64 field) {if ((field | (field -1 )) & ((field | (field -1 )) +1 ))__bad_mask (); -return field & -field; +return ffs_val (field); } static __always_inline u64 field_mask(u64 field) {
include/linux/log2.h +1 -1
@@ -266,7 +266,7 @@ int __bits_per(unsigned long n)static inline __attribute__((const))unsigned int max_pow_of_two_factor (unsigned int n) { -return n & -n; +return ffs_val (n); }#endif /* _LINUX_LOG2_H */
include/linux/min_heap.h +3 -2
@@ -3,6 +3,7 @@#define _LINUX_MIN_HEAP_H#include <linux/bug.h> +#include <linux/ffs_val.h> #include <linux/string.h> #include <linux/types.h>
@@ -257,7 +258,7 @@ static __always_inlinevoid __min_heap_sift_down_inline (min_heap_char *heap,size_t pos,size_t elem_size,const struct min_heap_callbacks *func,void *args) { -const unsigned long lsbit = elem_size & -elem_size; +const unsigned long lsbit =ffs_val (elem_size);void *data = heap->data;void (*swp)(void *lhs,void *rhs,void *args) = func->swp;/* pre-scale counters for performance */
@@ -297,7 +298,7 @@ static __always_inlinevoid __min_heap_sift_up_inline (min_heap_char *heap,size_t elem_size,size_t idx,const struct min_heap_callbacks *func,void *args) { -const unsigned long lsbit = elem_size & -elem_size; +const unsigned long lsbit =ffs_val (elem_size);void *data = heap->data;void (*swp)(void *lhs,void *rhs,void *args) = func->swp;/* pre-scale counters for performance */
lib/math/gcd.c +2 -2
@@ -23,12 +23,12 @@ static unsigned long binary_gcd(unsigned long a, unsigned long b) b >>=__ffs (b);if (b ==1 ) -return r & -r; +return ffs_val (r);for (;;) { a >>=__ffs (a);if (a ==1 ) -return r & -r; +return ffs_val (r);if (a == b)return a <<__ffs (r);
lib/sort.c +2 -1
@@ -12,6 +12,7 @@#include <linux/types.h> #include <linux/export.h> +#include <linux/ffs_val.h> #include <linux/sort.h> /**
@@ -196,7 +197,7 @@ static void __sort_r(void *base, size_t num, size_t size, {/* pre-scale counters for performance */ size_t n = num * size, a = (num/2 ) * size; -const unsigned int lsbit = size & -size;/* Used to find parent */ +const unsigned int lsbit =ffs_val (size);/* Used to find parent */ size_t shift =0 ;if (!a)/* num < 2 || size == 0 */
net/bluetooth/mgmt.c +1 -1
@@ -8664,7 +8664,7 @@ static bool requested_adv_flags_are_valid(struct hci_dev *hdev, u32 adv_flags) supported_flags =get_supported_adv_flags (hdev); phy_flags = adv_flags &MGMT_ADV_FLAG_SEC_MASK ;if (adv_flags & ~supported_flags || - ((phy_flags && (phy_flags ^ (phy_flags & -phy_flags))))) + ((phy_flags && (phy_flags ^ffs_val (phy_flags)))))return false;return true;
net/netfilter/nft_set_pipapo.c +1 -1
@@ -370,7 +370,7 @@ int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,for (k =0 ; k < len; k++) { bitset = map[k];while (bitset) { -unsigned long t = bitset & -bitset; +unsigned long t =ffs_val (bitset);int r =__builtin_ctzl (bitset);int i = k *BITS_PER_LONG + r;
Signature · 1 line
2.52.0
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 80 lines · Petr Tesarik
Replace the open-coded bit-twiddling trick to get the least significant bit with a call to
ffs_val().This patch has been generated by the following coccinelle script:
@
depends on !(file in "include/asm-generic/bitops/ffs_val.h")&& !(file in "tools/")@
expression E;
@@- ((E) & (-(E)))
+ffs_val(E)Include <
linux/ffs_val.h> where the result did not build.Signed-off-by Petr Tesarik <[email protected]>--- arch/alpha/include/asm/bitops.h | 2 +- arch/alpha/kernel/core_cia.c | 2 +- arch/alpha/kernel/smp.c | 2 +- arch/arc/include/asm/bitops.h | 2 +- arch/m68k/include/asm/bitops.h | 12 ++++++------ arch/mips/dec/ecc-berr.c | 2 +- arch/mips/include/asm/bitops.h | 4 ++-- arch/mips/pci/pci-malta.c | 4 ++-- arch/powerpc/include/asm/bitops.h | 4 ++-- arch/powerpc/kvm/e500_mmu_host.c | 2 +- arch/powerpc/lib/sstep.c | 2 +- arch/powerpc/xmon/ppc-dis.c | 3 ++- arch/powerpc/xmon/ppc-opc.c | 6 +++--- arch/s390/include/asm/bitops.h | 2 +- arch/xtensa/include/asm/bitops.h | 6 +++--- arch/xtensa/kernel/traps.c | 2 +- drivers/gpu/drm/gma500/psb_intel_sdvo.c | 2 +- drivers/iommu/dma-iommu.c | 2 +- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +- drivers/net/usb/cdc_ncm.c | 4 ++-- include/asm-generic/div64.h | 4 ++-- include/linux/bitfield.h | 3 ++- include/linux/log2.h | 2 +- include/linux/min_heap.h | 5 +++-- lib/math/gcd.c | 4 ++-- lib/sort.c | 3 ++- net/bluetooth/mgmt.c | 2 +- net/netfilter/nft_set_pipapo.c | 2 +- 28 files changed, 48 insertions(+), 44 deletions(-)arch/alpha/include/asm/bitops.h +1
-1@@ -317,7 +317,7 @@ static inline unsigned long ffz_b(unsigned long x) {unsigned long sum, x1, x2, x4; - x = ~x & -~x;/* set first 0 bit, clear others */ + x =ffs_val (~x);/* set first 0 bit, clear others */ x1 = x &0xAA ; x2 = x &0xCC ; x4 = x &0xF0 ;arch/alpha/kernel/core_cia.c +1
-1@@ -1035,7 +1035,7 @@ cia_decode_ecc_error(struct el_CIA_sysdata_mcheck *cia, const char *msg)cia_decode_mem_error (cia, msg); syn = cia->cia_syn &0xff ; -if (syn == (syn & -syn)) { +if (syn ==ffs_val (syn)) { fmt =KERN_CRIT " ECC syndrome %#x -- check bit %d\n" ; i =ffs (syn) -1 ; }else {arch/alpha/kernel/smp.c +0
-0
arch/alpha/kernel/smp.c handle_ipi(struct pt_regs *regs) · line 530
Quoted 7 lines
arch/alpha/kernel/smp.c +1
-1@@ -525,7 +525,7 @@ handle_ipi(struct pt_regs *regs) do { unsigned long which; - which = ops & -ops; + which = ffs_val(ops); ops &= ~which; which = __ffs(which);
I guess, this should be:
which = __ffs(ops);
ops &= ops - 1;Check how fns() works. And to that extend, you can make another
helper: clear_lsb().
Quoted 54 lines
arch/arc/include/asm/bitops.h +1
-1@@ -94,7 +94,7 @@ static inline __attribute__ ((const)) unsigned long __fls(unsigned long x)* ffs = Find First Set in word (LSB to MSB) * @result: [1-32], 0 if all 0's */ -#define ffs (x) ({ unsigned long __t = (x); fls(__t & -__t); }) +#define ffs (x) ({ unsigned long __t = (x); fls(ffs_val(__t)); })/* * __ffs: Similar to ffs, but zero based (0-31) arch/m68k/include/asm/bitops.h +4
-4@@ -368,7 +368,7 @@ static inline unsigned long find_first_zero_bit(const unsigned long *vaddr, } __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num))); res ^=31 ; out: res += ((long )p - (long )vaddr -4 ) *8 ;@@ -392,7 +392,7 @@ static inline unsigned long find_next_zero_bit(const unsigned long *vaddr,/* Look for zero in first longword */ __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num)));if (res <32 ) { offset += res ^31 ;return offset < size ? offset : size;@@ -425,7 +425,7 @@ static inline unsigned long find_first_bit(const unsigned long *vaddr, } __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num))); res ^=31 ; out: res += ((long )p - (long )vaddr -4 ) *8 ;@@ -449,7 +449,7 @@ static inline unsigned long find_next_bit(const unsigned long *vaddr,/* Look for one in first longword */ __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (num & -num)); + :"=d" (res) :"d" (ffs_val (num)));if (res <32 ) { offset += res ^31 ;return offset < size ? offset : size;
arch/m68k/include/asm/bitops.h static inline unsigned long __attribute_const__ ffz(unsigned long word) · line 476
Quoted 5 lines
arch/m68k/include/asm/bitops.h +1
-1@@ -473,7 +473,7 @@ static inline unsigned long __attribute_const__ ffz(unsigned long word)int res; __asm__ __volatile__ ("bfffo %1{#0,#0},%0" - :"=d" (res) :"d" (~word & -~word)); + :"=d" (res) :"d" (ffs_val (~word)));
This should be ffz_val(word). But if you like fsb_mask(), maybe fzb_mask()?
Quoted 17 lines
arch/m68k/include/asm/bitops.h +1
-1return res ^31 ; }@@ -527,7 +527,7 @@ static inline __attribute_const__ int ffs(int x) __asm__ ("bfffo %1{#0:#0},%0" :"=d" (cnt) - :"dm" (x & -x)); + :"dm" (ffs_val (x)));return 32 - cnt; }arch/mips/dec/ecc-berr.c +0
-0
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 5 lines
arch/mips/dec/ecc-berr.c +1
-1@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack (); -if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {
It opencodes is_power_of_2().
Quoted 67 lines
arch/mips/dec/ecc-berr.c +0
-0if (syn ==0x01 ) { fmt =KERN_ALERT "%s" "%#04x -- %s bit error " arch/mips/include/asm/bitops.h +2
-2@@ -395,7 +395,7 @@ static __always_inline __attribute_const__ unsigned long __fls(unsigned long wor*/ static __always_inline __attribute_const__ unsigned long __ffs(unsigned long word) { -return __fls (word & -word); +return __fls (ffs_val (word)); }/* @@ -463,7 +463,7 @@ static inline __attribute_const__ int ffs(int word)if (!word)return 0 ; -return fls (word & -word); +return fls (ffs_val (word)); }#include <asm-generic/bitops/ffz.h> arch/mips/pci/pci-malta.c +2
-2@@ -117,7 +117,7 @@ void __init mips_pcibios_init(void) mask = ~(start ^ end);/* We don't support remapping with a discontiguous mask. */ BUG_ON ((start >_PCI_HD_MSK ) != (map >_PCI_HD_MSK ) && - mask != ~((mask & -mask) -1 )); + mask != ~(ffs_val (mask) -1 )); gt64120_mem_resource.start = start; gt64120_mem_resource.end = end; gt64120_controller.mem_offset = (start & mask) - (map & mask);@@ -134,7 +134,7 @@ void __init mips_pcibios_init(void) mask = ~(start ^ end);/* We don't support remapping with a discontiguous mask. */ BUG_ON ((start >_PCI_HD_MSK ) != (map >_PCI_HD_MSK ) && - mask != ~((mask & -mask) -1 )); + mask != ~(ffs_val (mask) -1 )); gt64120_io_resource.start = map & mask; gt64120_io_resource.end = (map & mask) | ~mask; gt64120_controller.io_offset =0 ;arch/powerpc/include/asm/bitops.h +2
-2@@ -87,8 +87,8 @@ static __always_inline bool is_rlwinm_mask_valid(unsigned long x)if (!x)return false;if (x &1 ) - x = ~x;// make the mask non-wrapping - x += x & -x;// adding the low set bit results in at most one bit set + x = ~x;// make the mask non-wrapping + x +=ffs_val (x);// adding the low set bit results in at most one bit set return !(x & (x -1 )); }arch/powerpc/kvm/e500_mmu_host.c +0
-0
arch/powerpc/kvm/e500_mmu_host.c void inval_gtlbe_on_host(struct kvmppc_vcpu_e500 *vcpu_e500, int tlbsel, · line 208
Quoted 5 lines
arch/powerpc/kvm/e500_mmu_host.c +1
-1@@ -205,7 +205,7 @@ void inval_gtlbe_on_host(struct kvmppc_vcpu_e500 *vcpu_e500, int tlbsel,local_irq_save (flags);while (tmp) { - hw_tlb_indx =__ilog2_u64 (tmp & -tmp); + hw_tlb_indx =__ilog2_u64 (ffs_val (tmp));
Is it the same as __ffs64(tmp)?
Quoted 29 lines
arch/powerpc/kvm/e500_mmu_host.c +0
-0mtspr (SPRN_MAS0 ,MAS0_TLBSEL (1 ) |MAS0_ESEL (to_htlb1_esel (hw_tlb_indx)));arch/powerpc/lib/sstep.c +1
-1@@ -236,7 +236,7 @@ static nokprobe_inline unsigned long mlsd_8lsd_ea(unsigned int instr,static nokprobe_inline unsigned long max_align (unsigned long x) { x |=sizeof (unsigned long ); -return x & -x;/* isolates rightmost bit */ +return ffs_val (x);/* isolates rightmost bit */ }static nokprobe_inline unsigned long byterev_2 (unsigned long x)arch/powerpc/xmon/ppc-dis.c +1
-0@@ -9,6 +9,7 @@ This file is part of GDB, GAS, and the GNU binutils.#include <asm/cputable.h> #include <asm/cpu_has_feature.h> +#include <linux/ffs_val.h> #include "nonstdio.h" #include "ansidecl.h" #include "ppc.h"
arch/powerpc/xmon/ppc-dis.c operand_value_powerpc (const struct powerpc_operand *operand, · line 48
Quoted 5 lines
arch/powerpc/xmon/ppc-dis.c +1
-1@@ -44,7 +45,7 @@ operand_value_powerpc (const struct powerpc_operand *operand,unsigned long top = operand->bitm;/* top & -top gives the rightmost 1 bit, so this fills in any trailing zeros. */ - top |= (top & -top) -1 ; + top |=ffs_val (top) -1 ;
Yeah, to me here it would be more verbose if:
top |= lsb_mask(top) - 1;
arch/powerpc/xmon/ppc-opc.c insert_fxm (unsigned long insn, · line 1420
Quoted 13 lines
arch/powerpc/xmon/ppc-dis.c +0
-0top &= ~(top >>1 ); value = (value ^ top) - top; }arch/powerpc/xmon/ppc-opc.c +1
-1@@ -1417,7 +1417,7 @@ insert_fxm (unsigned long insn,one bit of the mask field is set. */ if ((insn & (1 <<20 )) !=0 ) { -if (value ==0 || (value & -value) != value) +if (value ==0 ||ffs_val (value) != value)
Again, opencodes is_power_of_2()
Quoted 13 lines
arch/powerpc/xmon/ppc-opc.c +1
-1{ *errmsg =_ ("invalid mask field" ); value =0 ;@@ -1430,7 +1430,7 @@ insert_fxm (unsigned long insn,new form unless -mpower4 has been given, or -many and the two operand form of mfcr was used. */ else if (value > 0 - && (value & -value) == value + &&ffs_val (value) == value && ((dialect &PPC_OPCODE_POWER4 ) !=0 || ((dialect &PPC_OPCODE_ANY ) !=0 && (insn & (0x3ff << 1)) == 19 << 1)))
arch/powerpc/xmon/ppc-opc.c extract_fxm (unsigned long insn, · line 1463
Quoted 5 lines
arch/powerpc/xmon/ppc-opc.c +1
-1@@ -1460,7 +1460,7 @@ extract_fxm (unsigned long insn,if ((insn & (1 <<20 )) !=0 ) {/* Exactly one bit of MASK should be set. */ -if (mask ==0 || (mask & -mask) != mask) +if (mask ==0 ||ffs_val (mask) != mask)
And again.
--
OK, let me stop here.
Can you please instead of mechanical rework check each case individually and find the best replacement to highlight the intention?
Can you also split this patch to a series according to subsystems, so that corresponding maintainers will have better access to their changes?
Thanks,
Yury
Quoted 268 lines
arch/powerpc/xmon/ppc-opc.c +0
-0*invalid =1 ; }arch/s390/include/asm/bitops.h +1
-1@@ -193,7 +193,7 @@ static __always_inline __flatten __attribute_const__ int ffs(int word) {unsigned int val = (unsigned int )word; -return BITS_PER_LONG -__flogr (-val & val); +return BITS_PER_LONG -__flogr (ffs_val (val)); }#else /* CONFIG_CC_HAS_BUILTIN_FFS */ arch/xtensa/include/asm/bitops.h +3
-3@@ -39,7 +39,7 @@ static inline unsigned long __cntlz (unsigned long x) static inline int __attribute_const__ ffz(unsigned long x) { -return 31 -__cntlz (~x & -~x); +return 31 -__cntlz (ffs_val (~x)); }/* @@ -48,7 +48,7 @@ static inline int __attribute_const__ ffz(unsigned long x)static inline __attribute_const__ unsigned long __ffs (unsigned long x) { -return 31 -__cntlz (x & -x); +return 31 -__cntlz (ffs_val (x)); }/* @@ -59,7 +59,7 @@ static inline __attribute_const__ unsigned long __ffs(unsigned long x) static inline __attribute_const__ int ffs(unsigned long x) { -return 32 -__cntlz (x & -x); +return 32 -__cntlz (ffs_val (x)); }/* arch/xtensa/kernel/traps.c +1
-1@@ -309,7 +309,7 @@ static void do_interrupt(struct pt_regs *regs)break ;/* clear lowest pending irq in the unhandled mask */ - unhandled ^= (int_at_level & -int_at_level); + unhandled ^=ffs_val (int_at_level);do_IRQ (__ffs (int_at_level), regs); }drivers/gpu/drm/gma500/psb_intel_sdvo.c +1
-1@@ -1226,7 +1226,7 @@ psb_intel_sdvo_multifunc_encoder(struct psb_intel_sdvo *psb_intel_sdvo) {/* Is there more than one type of output? */ int caps = psb_intel_sdvo->caps.output_flags &0xf ; -return caps & -caps; +return ffs_val (caps); } static struct edid *drivers/iommu/dma-iommu.c +1
-1@@ -943,7 +943,7 @@ static struct page **__iommu_dma_alloc_noncontiguous(struct device *dev, iommu_deferred_attach(dev, domain))return NULL ; - min_size = alloc_sizes & -alloc_sizes; + min_size =ffs_val (alloc_sizes);if (min_size <PAGE_SIZE ) { min_size =PAGE_SIZE ; alloc_sizes |=PAGE_SIZE ;drivers/net/ethernet/netronome/nfp/bpf/jit.c +1
-1@@ -1565,7 +1565,7 @@ static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm) rvalue =reciprocal_value_adv (imm,32 ); exp = rvalue.exp;if (rvalue.is_wide_m && !(imm &1 )) { - pre_shift =fls (imm & -imm) -1 ; + pre_shift =fls (ffs_val (imm)) -1 ; rvalue =reciprocal_value_adv (imm >> pre_shift,32 - pre_shift); }else { pre_shift =0 ;drivers/net/usb/cdc_ncm.c +2
-2@@ -668,7 +668,7 @@ static void cdc_ncm_fix_modulus(struct usbnet *dev) val = ctx->tx_ndp_modulus;if ((val <USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ) || - (val != ((-val) & val)) || (val >= ctx->tx_max)) { + (val !=ffs_val (val)) || (val >= ctx->tx_max)) {dev_dbg (&dev->intf->dev,"Using default alignment: 4 bytes\n" ); ctx->tx_ndp_modulus =USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ; }@@ -682,7 +682,7 @@ static void cdc_ncm_fix_modulus(struct usbnet *dev) val = ctx->tx_modulus;if ((val <USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ) || - (val != ((-val) & val)) || (val >= ctx->tx_max)) { + (val !=ffs_val (val)) || (val >= ctx->tx_max)) {dev_dbg (&dev->intf->dev,"Using default transmit modulus: 4 bytes\n" ); ctx->tx_modulus =USB_CDC_NCM_NDP_ALIGN_MIN_SIZE ; }include/asm-generic/div64.h +2
-2@@ -111,8 +111,8 @@ } \ \/* Reduce m / p to help avoid overflow handling later. */ \ - ___p /= (___m & -___m); \ - ___m /= (___m & -___m); \ + ___p /=ffs_val (___m); \ + ___m /=ffs_val (___m); \ \/* \ * Perform (m_bias + m * n) / (1 << 64). \ include/linux/bitfield.h +2
-1@@ -8,6 +8,7 @@#define _LINUX_BITFIELD_H#include <linux/build_bug.h> +#include <linux/ffs_val.h> #include <linux/typecheck.h> #include <asm/byteorder.h> @@ -202,7 +203,7 @@ static __always_inline u64 field_multiplier(u64 field) {if ((field | (field -1 )) & ((field | (field -1 )) +1 ))__bad_mask (); -return field & -field; +return ffs_val (field); } static __always_inline u64 field_mask(u64 field) {include/linux/log2.h +1
-1@@ -266,7 +266,7 @@ int __bits_per(unsigned long n)static inline __attribute__((const))unsigned int max_pow_of_two_factor (unsigned int n) { -return n & -n; +return ffs_val (n); }#endif /* _LINUX_LOG2_H */ include/linux/min_heap.h +3
-2@@ -3,6 +3,7 @@#define _LINUX_MIN_HEAP_H#include <linux/bug.h> +#include <linux/ffs_val.h> #include <linux/string.h> #include <linux/types.h> @@ -257,7 +258,7 @@ static __always_inlinevoid __min_heap_sift_down_inline (min_heap_char *heap,size_t pos,size_t elem_size,const struct min_heap_callbacks *func,void *args) { -const unsigned long lsbit = elem_size & -elem_size; +const unsigned long lsbit =ffs_val (elem_size);void *data = heap->data;void (*swp)(void *lhs,void *rhs,void *args) = func->swp;/* pre-scale counters for performance */ @@ -297,7 +298,7 @@ static __always_inlinevoid __min_heap_sift_up_inline (min_heap_char *heap,size_t elem_size,size_t idx,const struct min_heap_callbacks *func,void *args) { -const unsigned long lsbit = elem_size & -elem_size; +const unsigned long lsbit =ffs_val (elem_size);void *data = heap->data;void (*swp)(void *lhs,void *rhs,void *args) = func->swp;/* pre-scale counters for performance */ lib/math/gcd.c +2
-2@@ -23,12 +23,12 @@ static unsigned long binary_gcd(unsigned long a, unsigned long b) b >>=__ffs (b);if (b ==1 ) -return r & -r; +return ffs_val (r);for (;;) { a >>=__ffs (a);if (a ==1 ) -return r & -r; +return ffs_val (r);if (a == b)return a <<__ffs (r);lib/sort.c +2
-1@@ -12,6 +12,7 @@#include <linux/types.h> #include <linux/export.h> +#include <linux/ffs_val.h> #include <linux/sort.h> /** @@ -196,7 +197,7 @@ static void __sort_r(void *base, size_t num, size_t size, {/* pre-scale counters for performance */ size_t n = num * size, a = (num/2 ) * size; -const unsigned int lsbit = size & -size;/* Used to find parent */ +const unsigned int lsbit =ffs_val (size);/* Used to find parent */ size_t shift =0 ;if (!a)/* num < 2 || size == 0 */ net/bluetooth/mgmt.c +1
-1@@ -8664,7 +8664,7 @@ static bool requested_adv_flags_are_valid(struct hci_dev *hdev, u32 adv_flags) supported_flags =get_supported_adv_flags (hdev); phy_flags = adv_flags &MGMT_ADV_FLAG_SEC_MASK ;if (adv_flags & ~supported_flags || - ((phy_flags && (phy_flags ^ (phy_flags & -phy_flags))))) + ((phy_flags && (phy_flags ^ffs_val (phy_flags)))))return false;return true;net/netfilter/nft_set_pipapo.c +1
-1@@ -370,7 +370,7 @@ int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,for (k =0 ; k < len; k++) { bitset = map[k];while (bitset) { -unsigned long t = bitset & -bitset; +unsigned long t =ffs_val (bitset);int r =__builtin_ctzl (bitset);int i = k *BITS_PER_LONG + r;Signature · 1 line
2.52.0
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 10 lines · On Fri, 9 Jan 2026 13:19:25 -0500 Yury Norov <[email protected]> wrote:
[...]
--OK, let me stop here.
Can you please instead of mechanical rework check each case individually and find the best replacement to highlight the intention?
Can you also split this patch to a series according to subsystems, so that corresponding maintainers will have better access to their changes?
Well, then it makes more sense to start by identifying the intention in every place and getting them fixed one by one. Whatever remains should be converted to use the new macro.
In fact, I can do both in parallel, converting the places where the result of ffs() is immediately used as a shift count.
Then no tree-wide change is necessary, as long as we can first get the helper (under whichever name) into bitops.h. But it will be rejected without an in-tree user. I somehow feel caught by Catch XXII.
Advice welcome. Non-ironically.
Petr T
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 18 lines · Petr Tesarik
Quoted 10 lines · On Fri, 9 Jan 2026 13:19:25 -0500 Yury Norov <[email protected]> wrote:
[...]
--OK, let me stop here.
Can you please instead of mechanical rework check each case individually and find the best replacement to highlight the intention?
Can you also split this patch to a series according to subsystems, so that corresponding maintainers will have better access to their changes?
Well, then it makes more sense to start by identifying the intention in every place and getting them fixed one by one. Whatever remains should be converted to use the new macro.
Quoted 8 lines
In fact, I can do both in parallel, converting the places where the result of
ffs()is immediately used as a shift count.Then no tree-wide change is necessary, as long as we can first get the helper (under whichever name) into
bitops.h. But it will be rejected without an in-tree user. I somehow feel caught by Catch XXII.Advice welcome. Non-ironically.
Build your series like this:
1. Switch all 'a & -a' chunks to the existing helpers where possible;
2. Introduce the new macro;
3. Convert the rest of the codebase to using the macro;
In cover-letter mention that patches from #1 may be taken individually or together with the rest of the series at maintainers' discretion, and #2 and 3 must be merged at once, for example with my branch.
Then depending on feedback, I'll take your series as is, or will take only explicitly acked patches. In 2nd case, I will ask you to resend non-acked part for better visibility, and then decide either take it or drop.
Thanks,
Yury
Maciej W. Rozycki
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
In reply to Yury NorovQuoted 15 lines · Yury Norov
arch/alpha/kernel/smp.c handle_ipi(struct pt_regs *regs) · line 530
Quoted 12 lines
arch/alpha/kernel/smp.c +1
-1@@ -525,7 +525,7 @@ handle_ipi(struct pt_regs *regs) do { unsigned long which; - which = ops & -ops; + which = ffs_val(ops); ops &= ~which; which = __ffs(which);I guess, this should be:
Quoted 2 lines
which = __ffs(ops);
ops &= ops - 1;I think it's the wrong operation order.
Quoted 8 lines
Quoted 8 lines
arch/mips/dec/ecc-berr.c +0
-0@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack ();
Quoted 4 lines
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 2 lines
arch/mips/dec/ecc-berr.c +1
-1-if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {It opencodes
is_power_of_2().
Correct and it also predates that helper's existence by ~4 years. I'll
be happy to see this converted as the intent will be obviously clearer.
Maciej
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 17 lines · On Sat, 10 Jan 2026 10:36:07 +0000 (GMT) "Maciej W. Rozycki"…
Quoted 15 lines · Yury Norov
arch/alpha/kernel/smp.c handle_ipi(struct pt_regs *regs) · line 530
Quoted 12 lines
arch/alpha/kernel/smp.c +1
-1@@ -525,7 +525,7 @@ handle_ipi(struct pt_regs *regs) do { unsigned long which; - which = ops & -ops; + which = ffs_val(ops); ops &= ~which; which = __ffs(which);I guess, this should be:
Quoted 4 lines
Quoted 2 lines
which = __ffs(ops); ops &= ops - 1;I think it's the wrong operation order.
If you are going to do the __ffs() do it first.
which = __ffs(ops); ops &= ~(1u << which);
OTOH what follows is:
switch (which) {
case IPI_RESCHEDULE:
so changing to 'case 1u << IPI_RESCHEDULE: would save the ffs().
But the entire loop is pointless, three tests, the first being:
if (op & (1u << IPI_RESCHEDULE))
scheduler_ipi();would be far less code.
But probably pointless churn - no one cares about alpha any more :-)
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
arch/mips/dec/ecc-berr.c +0
-0@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack ();
Quoted 4 lines
Quoted 4 lines
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 2 lines
arch/mips/dec/ecc-berr.c +1
-1-if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {It opencodes
is_power_of_2().
Badly...
David
Quoted 6 lines
Correct and it also predates that helper's existence by ~4 years. I'll
be happy to see this converted as the intent will be obviously clearer.Maciej
Maciej W. Rozycki
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 8 lines · David Laight
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
arch/mips/dec/ecc-berr.c +0
-0@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack ();
Quoted 6 lines
Quoted 4 lines
Quoted 4 lines
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 2 lines
arch/mips/dec/ecc-berr.c +1
-1-if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {It opencodes
is_power_of_2().Badly...
It's 4 MIPS instructions and exactly the same machine code produced as
compiler output from `is_power_of_2'. If you know of a better alternative I'll be happy to get enlightened, however it's academic anyway, as it's the ECC memory error handler. If you get here, then you have a bigger issue than a couple of extra instructions executed per kernel log entry produced. If you indeed can get rid of them in the first place, that is.
Maciej
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 15 lines · On Sun, 11 Jan 2026 03:15:22 +0000 (GMT) "Maciej W. Rozycki"…
Quoted 13 lines · David Laight
Quoted 12 lines
Quoted 12 lines
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 10 lines
arch/mips/dec/ecc-berr.c +1
-1@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack (); -if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {It opencodes
is_power_of_2().
Quoted 4 lines
Quoted 1 line
Badly...
It's 4 MIPS instructions and exactly the same machine code produced as
compiler output from `is_power_of_2'.
The compiler must be detecting that x == (x & -x) is the same as (x & (x - 1)) == 0.
Although for MIPS the former is negate, and, beq(x,y) - so 3 instructions. On x86 it is negate, and, cmp, beq(zero flag) - one extra instruction. (The 4th MIPS instruction will be beq(syn,0).)
So maybe s/Badly/In an unusual way/
Quoted 1 line
If you know of a better alternative
Doing is_power_of_2() with only one conditional branch would be a gain. But I've not thought about it hard enough to find one.
I suspect there may not be one, but all these 'tricks' come from the 1970s (or earlier) and don't allow for the behaviour of modern cpu with multiple execution units and long pipelines.
(Although MIPS is likely to be relatively sane.)
David
Quoted 7 lines
I'll be happy to get enlightened, however it's academic anyway, as it's the ECC memory error handler. If you get here, then you have a bigger issue than a couple of extra instructions executed per kernel log entry produced. If you indeed can get rid of them in the first place, that is.
Maciej
Maciej W. Rozycki
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 5 lines · David Laight
Quoted 2 lines
It's 4 MIPS instructions and exactly the same machine code produced as
compiler output from `is_power_of_2'.The compiler must be detecting that x == (x & -x) is the same as (x & (x - 1)) == 0.
There are 3 basic operations either way, so unless a CPU has an odd
instruction that combines any, there's no way to reduce the instruction count.
Quoted 3 lines
Although for MIPS the former is negate, and,
beq(x,y)- so 3 instructions. On x86 it is negate, and, cmp, beq(zero flag) - one extra instruction. (The 4th MIPS instruction will bebeq(syn,0).)
This code only ever runs on R2000/R3000 and R4000/R4400 processors, on
which the cost of an untaken branch is nil. The cost of a taken branch on the former ones is nil too, with their 4-stage pipelines, and while there is a fixed penalty on the latter ones, the compiler should be able to arrange code here such that at most one branch is taken anyway.
Quoted 1 line
So maybe s/Badly/In an unusual way/
What's unusual in this way of determining that exactly one bit is set in
a word? It's as good as any I suppose.
Quoted 4 lines
Quoted 1 line
If you know of a better alternative
Doing
is_power_of_2()with only one conditional branch would be a gain. But I've not thought about it hard enough to find one.
Sure you can, either of:
(x != 0) & (x == (x & -x))
and:
(x != 0) & ((x & (x - 1)) == 0)
will do, but it's 5 instructions on MIPS, so no gain here.
If you have a population count instruction such as CTPOP on EV67 Alpha,
you can do it in two instructions, such as:
ctpop $16, $0 cmpeq $0, 1, $0
so there seems to be room for improvement here, but GCC stubbornly refuses to produce this instruction sequence for this code:
bool is_power_of_2(unsigned long n)
{
return __builtin_popcountl(n) == 1;
}apparently owing to no insn cost set for the POPCOUNT RTX in the backend causing the middle end to pick up some default. Instead GCC comes up with what can be coded in C as:
bool is_power_of_2(unsigned long n)
{
return n - 1 < (n ^ (n - 1));
}which seems an interesting alternative that produces 3 instructions only across Alpha, MIPS and RISC-V targets. It's 5 instructions on POWER and x86-64 vs 8 and 9 respectively with our current implementation. There are no branches produced here, although an inline expansion will likely end with one.
Overall it seems a worthwhile improvement even if still an instruction
longer than necessary for EV67 Alpha (and also for POWER, which also has a population count operation, and which GCC does pick up in this case).
FWIW on VAX, notorious for the lack of conditional set operations, it's 7
instructions and 1 branch, down from 14 and 2 respectively.
Quoted 3 lines
I suspect there may not be one, but all these 'tricks' come from the 1970s (or earlier) and don't allow for the behaviour of modern cpu with multiple execution units and long pipelines.
As we can see you never know. I've sent a code update proposal.
The use of the population count operation can be considered separately,
but we'd have to be careful here as the quality of code produced by the intrinsic varies, e.g. with pre-EV67 Alpha, RISC-V and VAX (!) GCC emits code equivalent to my proposal, but with MIPS or x86-64 it resorts to a libcall, so a guarding condition would be required. So I'd leave it for another occasion.
Thanks for sparking this discussion overall!
Maciej
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 56 lines · On Sun, 11 Jan 2026 21:22:03 +0000 (GMT) "Maciej W. Rozycki"…
Quoted 5 lines · David Laight
Quoted 2 lines
It's 4 MIPS instructions and exactly the same machine code produced as
compiler output from `is_power_of_2'.The compiler must be detecting that x == (x & -x) is the same as (x & (x - 1)) == 0.
There are 3 basic operations either way, so unless a CPU has an odd
instruction that combines any, there's no way to reduce the instruction count.Quoted 3 lines
Although for MIPS the former is negate, and,
beq(x,y)- so 3 instructions. On x86 it is negate, and, cmp, beq(zero flag) - one extra instruction. (The 4th MIPS instruction will bebeq(syn,0).)This code only ever runs on R2000/R3000 and R4000/R4400 processors, on
which the cost of an untaken branch is nil. The cost of a taken branch on the former ones is nil too, with their 4-stage pipelines, and while there is a fixed penalty on the latter ones, the compiler should be able to arrange code here such that at most one branch is taken anyway.Quoted 1 line
So maybe s/Badly/In an unusual way/
What's unusual in this way of determining that exactly one bit is set in
a word? It's as good as any I suppose.Quoted 4 lines
Quoted 1 line
If you know of a better alternative
Doing
is_power_of_2()with only one conditional branch would be a gain. But I've not thought about it hard enough to find one.Sure you can, either of:
(x != 0) & (x == (x & -x))and:
(x != 0) & ((x & (x - 1)) == 0)will do, but it's 5 instructions on MIPS, so no gain here.
If you have a population count instruction such as CTPOP on EV67 Alpha,
you can do it in two instructions, such as:ctpop $16, $0 cmpeq $0, 1, $0so there seems to be room for improvement here, but GCC stubbornly refuses to produce this instruction sequence for this code:
bool
is_power_of_2(unsigned long n){ return __builtin_popcountl(n) == 1; }
Quoted 8 lines
apparently owing to no insn cost set for the POPCOUNT RTX in the backend causing the middle end to pick up some default. Instead GCC comes up with what can be coded in C as:
bool
is_power_of_2(unsigned long n){ return n - 1 < (n ^ (n - 1)); }
Not seen that one - and not thought of popcnt, far too new for me. (I learnt asm for a pdp11 first...)
Quoted 5 lines
which seems an interesting alternative that produces 3 instructions only across Alpha, MIPS and RISC-V targets. It's 5 instructions on POWER and x86-64 vs 8 and 9 respectively with our current implementation. There are no branches produced here, although an inline expansion will likely end with one.
I'm seeing:is_power_of_2:
leaq -1(%rdi), %rax
xorq %rax, %rdi
cmpq %rdi, %rax
setb %al retq
on x86-64 - which is really 3 instructions.
While using the popcnt instruction would reduce it by one, it will only be faster on amd zen cpu, on intel cpu popcnt has a latency of 3 and only executes on p1 (according to Agner).
Quoted 7 lines
Overall it seems a worthwhile improvement even if still an instruction
longer than necessary for EV67 Alpha (and also for POWER, which also has a population count operation, and which GCC does pick up in this case).FWIW on VAX, notorious for the lack of conditional set operations, it's 7
instructions and 1 branch, down from 14 and 2 respectively.
I worked for ICL through the 1980s so missed out on VAX. Picked up 8085, x86, sparc32 and m68k.
Quoted 5 lines
Quoted 3 lines
I suspect there may not be one, but all these 'tricks' come from the 1970s (or earlier) and don't allow for the behaviour of modern cpu with multiple execution units and long pipelines.
As we can see you never know. I've sent a code update proposal.
I'd suggest moving is_power_of_2() to bits.h as:
#define is_power_of_2(n) ({ auto _n = n; _n - 1 < _n ^ (_n - 1); }) and add:
#define is_zero_or_power_of_2(n) ({ auto _n = n; _n & (_n - 1) != 0; })
Quoted 7 lines
The use of the population count operation can be considered separately,
but we'd have to be careful here as the quality of code produced by the intrinsic varies, e.g. with pre-EV67 Alpha, RISC-V and VAX (!) GCC emits code equivalent to my proposal, but with MIPS or x86-64 it resorts to a libcall, so a guarding condition would be required. So I'd leave it for another occasion.
I'd guess that many of those popcnt instructions aren't actually as fast as the dec/xor pair.
But the libcall is just plain stupid.
I think that happens elsewhere - which is one reason __ffs() is x86 asm.
Quoted 2 lines
Thanks for sparking this discussion overall!
Nice wet Sunday bikeshed...
David
Quoted 3 lines
Maciej
Maciej W. Rozycki
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 18 lines · David Laight
Quoted 18 lines
If you have a population count instruction such as CTPOP on EV67 Alpha,
you can do it in two instructions, such as:ctpop $16, $0 cmpeq $0, 1, $0so there seems to be room for improvement here, but GCC stubbornly refuses to produce this instruction sequence for this code:
bool
is_power_of_2(unsigned long n){ return __builtin_popcountl(n) == 1; }apparently owing to no insn cost set for the POPCOUNT RTX in the backend causing the middle end to pick up some default. Instead GCC comes up with what can be coded in C as:
Quoted 7 lines
Quoted 4 lines
bool
is_power_of_2(unsigned long n){ return n - 1 < (n ^ (n - 1)); }Not seen that one - and not thought of popcnt, far too new for me. (I learnt asm for a pdp11 first...)
It does show up as an RTL operation in the compiler; it's a good way to
discover stuff.
Quoted 6 lines
Quoted 5 lines
which seems an interesting alternative that produces 3 instructions only across Alpha, MIPS and RISC-V targets. It's 5 instructions on POWER and x86-64 vs 8 and 9 respectively with our current implementation. There are no branches produced here, although an inline expansion will likely end with one.
Quoted 8 lines
I'm seeing:
is_power_of_2:leaq -1(%rdi), %rax xorq %rax, %rdi cmpq %rdi, %rax setb %alretq
on x86-64 - which is really 3 instructions.
Ack, this is unsigned long' vs bool' return type. I'm just too used to
RISC psABIs. FWIW I have this:
leaq -1(%rdi), %rax xorq %rax, %rdi cmpq %rdi, %rax setb %al movzbl %al, %eax ret
in the former case and I take it `bool' is 8-bit on x86.
Quoted 3 lines
While using the popcnt instruction would reduce it by one, it will only be faster on amd zen cpu, on intel cpu popcnt has a latency of 3 and only executes on p1 (according to Agner).
Ack. I've lost track of x86 after ~Pentium Pro.
Quoted 10 lines
Quoted 5 lines
Quoted 3 lines
I suspect there may not be one, but all these 'tricks' come from the 1970s (or earlier) and don't allow for the behaviour of modern cpu with multiple execution units and long pipelines.
As we can see you never know. I've sent a code update proposal.
I'd suggest moving
is_power_of_2()tobits.has:
#defineis_power_of_2(n)({ auto _n = n; _n - 1 < _n ^ (_n - 1); }) and add:
#defineis_zero_or_power_of_2(n)({ auto _n = n; _n & (_n - 1) != 0; })
I'll leave it as an exercise for someone else.
Quoted 9 lines
Quoted 6 lines
The use of the population count operation can be considered separately,
but we'd have to be careful here as the quality of code produced by the intrinsic varies, e.g. with pre-EV67 Alpha, RISC-V and VAX (!) GCC emits code equivalent to my proposal, but with MIPS or x86-64 it resorts to a libcall, so a guarding condition would be required. So I'd leave it for another occasion.I'd guess that many of those popcnt instructions aren't actually as fast as the dec/xor pair.
With EV67 Alpha and POWER being proper RISC architectures I'd expect the
instruction to be implemented using a dedicated logic gate network. After all the population count operation is just an n-operand addition of 1-bit inputs, so not a big deal. The propagation delay is probably on the same order of magnitude as with a 2-operand n-bit adder, so the operation ought to fit in a single pipeline stage.
I suppose it's just a matter of whether you want to dedicate a piece of
silicon just for this somewhat exotic operation, and in the old days the answer would be no for a general-purpose CPU owing to manufacturing cost and die size limitation, while nowadays with process shrinkage and power consumption reduction it may have become worthwhile.
Quoted 1 line
But the libcall is just plain stupid.
It could just be that it's a recent addition as my compilation of GCC for
x86-64 and MIPS turns out to be version 11 and 13 respectively, while I have version 15 for the remaining targets. Indeed when I tried now GCC 14 that I have at hand for another MIPS configuration the libcall is gone, so the optimisation must have been added in that version.
Of course you still need a libcall for a plain `__builtin_popcountl' call
where there's no suitable hardware instruction available.
Maciej
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 49 lines · On Mon, 12 Jan 2026 11:21:59 +0000 (GMT) "Maciej W. Rozycki"…
Quoted 18 lines · David Laight
Quoted 18 lines
If you have a population count instruction such as CTPOP on EV67 Alpha,
you can do it in two instructions, such as:ctpop $16, $0 cmpeq $0, 1, $0so there seems to be room for improvement here, but GCC stubbornly refuses to produce this instruction sequence for this code:
bool
is_power_of_2(unsigned long n){ return __builtin_popcountl(n) == 1; }apparently owing to no insn cost set for the POPCOUNT RTX in the backend causing the middle end to pick up some default. Instead GCC comes up with what can be coded in C as:
Quoted 7 lines
Quoted 4 lines
bool
is_power_of_2(unsigned long n){ return n - 1 < (n ^ (n - 1)); }Not seen that one - and not thought of popcnt, far too new for me. (I learnt asm for a pdp11 first...)
It does show up as an RTL operation in the compiler; it's a good way to
discover stuff.Quoted 6 lines
Quoted 5 lines
which seems an interesting alternative that produces 3 instructions only across Alpha, MIPS and RISC-V targets. It's 5 instructions on POWER and x86-64 vs 8 and 9 respectively with our current implementation. There are no branches produced here, although an inline expansion will likely end with one.
Quoted 8 lines
I'm seeing:
is_power_of_2:leaq -1(%rdi), %rax xorq %rax, %rdi cmpq %rdi, %rax setb %alretq
on x86-64 - which is really 3 instructions.Ack, this is
unsigned long' vsbool' return type. I'm just too used to
RISC psABIs. FWIW I have this:
Quoted 8 lines
leaq -1(%rdi), %rax xorq %rax, %rdi cmpq %rdi, %rax setb %al movzbl %al, %eax retin the former case and I take it `bool' is 8-bit on x86.
That was _Bool on godbolt, it you return 'int' the extra 'zero extend' is needed. SETcc was added for 386 (I still forget about it) and someone assumed you wouldn't want the 'word' variant.
(It isn't as though they couldn't have allocated another row of the 0F opcode to it.)
I sort of hate 'bool' types, something sane has to happen for 'a & b' when the bit patterns are unexpected - and it ought to be well defined. The traditional C where 'a > b' generates 0 or 1 is fine.
Quoted 5 lines
Quoted 3 lines
While using the popcnt instruction would reduce it by one, it will only be faster on amd zen cpu, on intel cpu popcnt has a latency of 3 and only executes on p1 (according to Agner).
Ack. I've lost track of x86 after ~Pentium Pro.
Those were the days :-)
I do remember something from one of the Intel manuals of that period about not intermixing data with code because of the possibility of the cpu speculatively executing the data following a branch and if the data happened to be a floating point trig function it had to wait for it to finish. SLS isn't a modern thing.
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
I suspect there may not be one, but all these 'tricks' come from the 1970s (or earlier) and don't allow for the behaviour of modern cpu with multiple execution units and long pipelines.
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
As we can see you never know. I've sent a code update proposal.
I'd suggest moving
is_power_of_2()tobits.has:
#defineis_power_of_2(n)({ auto _n = n; _n - 1 < _n ^ (_n - 1); }) and add:
#defineis_zero_or_power_of_2(n)({ auto _n = n; _n & (_n - 1) != 0; })I'll leave it as an exercise for someone else.
I might add it to the patchset I'm writing - mostly bits.h
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines
The use of the population count operation can be considered separately,
but we'd have to be careful here as the quality of code produced by the intrinsic varies, e.g. with pre-EV67 Alpha, RISC-V and VAX (!) GCC emits code equivalent to my proposal, but with MIPS or x86-64 it resorts to a libcall, so a guarding condition would be required. So I'd leave it for another occasion.I'd guess that many of those popcnt instructions aren't actually as fast as the dec/xor pair.
Quoted 6 lines
With EV67 Alpha and POWER being proper RISC architectures I'd expect the
instruction to be implemented using a dedicated logic gate network. After all the population count operation is just an n-operand addition of 1-bit inputs, so not a big deal. The propagation delay is probably on the same order of magnitude as with a 2-operand n-bit adder, so the operation ought to fit in a single pipeline stage.
There are some tricks that can be done to reduce the propagation delay of a 64bit add from ~64 (for the ripple carry) to nearer 16 (add each byte with and without a carry input and then use a mux to select the correct output). That may not work for popcnt.
Also I suspect that multiply isn't single clock, so multicycle instructions have to be supported.
Throw silicon at multiply and you can reduce it to full-adders with a carry- chain the length of the result, not sure you can do much better.
For my sins I re-implemented the Nios-II cpu a couple of years ago (because Intel had deprecated it), the single 64bit add needed at the end of multiply (done by fgpa DSP blocks) made it impossible to feed the product straight back into the ALU for the next cycle.
My version is about the same size, 1 clock faster in a few places (like predicted taken branches and the stall if a multiply result (and I think memory reads) is needed in the next-but-one instruction.
FMax is a bit lower, but we were constrained by the PCIe interface to 67.5MHz and it was fast enough.
David
Quoted 20 lines
I suppose it's just a matter of whether you want to dedicate a piece of
silicon just for this somewhat exotic operation, and in the old days the answer would be no for a general-purpose CPU owing to manufacturing cost and die size limitation, while nowadays with process shrinkage and power consumption reduction it may have become worthwhile.Quoted 1 line
But the libcall is just plain stupid.
It could just be that it's a recent addition as my compilation of GCC for
x86-64 and MIPS turns out to be version 11 and 13 respectively, while I have version 15 for the remaining targets. Indeed when I tried now GCC 14 that I have at hand for another MIPS configuration the libcall is gone, so the optimisation must have been added in that version.Of course you still need a libcall for a plain `__builtin_popcountl' call
where there's no suitable hardware instruction available.Maciej
Kuan-Wei Chiu
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
In reply to Maciej W. RozyckiQuoted 35 lines · Maciej W. Rozycki
Quoted 15 lines · Yury Norov
arch/alpha/kernel/smp.c handle_ipi(struct pt_regs *regs) · line 530
Quoted 12 lines
arch/alpha/kernel/smp.c +1
-1@@ -525,7 +525,7 @@ handle_ipi(struct pt_regs *regs) do { unsigned long which; - which = ops & -ops; + which = ffs_val(ops); ops &= ~which; which = __ffs(which);I guess, this should be:
Quoted 2 lines
which = __ffs(ops); ops &= ops - 1;I think it's the wrong operation order.
Quoted 8 lines
Quoted 8 lines
arch/mips/dec/ecc-berr.c +0
-0@@ -153,7 +153,7 @@ static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker)/* Ack now, now we've rewritten (or not). */ dec_ecc_be_ack ();Quoted 4 lines
arch/mips/dec/ecc-berr.c static int dec_ecc_be_backend(struct pt_regs *regs, int is_fixup, int invoker) · line 156
Quoted 2 lines
arch/mips/dec/ecc-berr.c +1
-1-if (syn && syn == (syn & -syn)) { +if (syn && syn ==ffs_val (syn)) {It opencodes
is_power_of_2().
Quoted 5 lines
Correct and it also predates that helper's existence by ~4 years. I'll
be happy to see this converted as the intent will be obviously clearer.Maciej
Hi all,
(Apologies for the off-topic question regarding email delivery)
I noticed Maciej's reply only after seeing David's subsequent response. For some reason, this specific email from Maciej never reached my gmail inbox, nor did it appear in my spam folder. It seems gmail may have silently dropped it.
I have retrieved this raw message from the lore.kernel.org web interface to reply here.
Since there are other gmail users on this thread (e.g., David, whom I assume received it successfully given the reply), I am wondering if anyone else using gmail experienced similar issues with this message?
If anyone has insights on why this might be happening or how to adjust settings to prevent this, please let me know. I want to ensure I don't inadvertently miss any comments or appear unresponsive in the future.
Regards,
Kuan-Wei
Re: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
On Sun, 11 Jan 2026 00:42:56 +0800
Kuan-Wei Chiu <[email protected]> wrote:
...
Quoted 3 lines
Since there are other gmail users on this thread (e.g., David, whom I assume received it successfully given the reply), I am wondering if anyone else using gmail experienced similar issues with this message?
Me 'David' ?
I'm actually subscribed to the lists on a different email provider. I used to use gmail, but it bounces, spams and just plain discards far too many messages to reliably receive lkml and friends.
I post from the gmail address to avoid leaking the other address to spammers.
David
Kuan-Wei Chiu
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 8 lines · David Laight
On Sun, 11 Jan 2026 00:42:56 +0800
Kuan-Wei Chiu <[email protected]> wrote:...
Quoted 3 lines
Since there are other gmail users on this thread (e.g., David, whom I assume received it successfully given the reply), I am wondering if anyone else using gmail experienced similar issues with this message?
Quoted 6 lines
Me 'David' ?
I'm actually subscribed to the lists on a different email provider. I used to use gmail, but it bounces, spams and just plain discards far too many messages to reliably receive lkml and friends.
I post from the gmail address to avoid leaking the other address to spammers.
Ah, I misunderstood. I thought you were receiving on gmail as well.
I actually just missed another reply from Maciej (again, nothing in spam). It appears gmail has decided to silently drop messages from him for some reason.
I'm a bit surprised to hear gmail described as generally unsuitable. I have used this account for Linux and several other open source projects for the past three years without issues until now.
Also, a quick check shows:
$ grep "gmail.com" MAINTAINERS | wc -l 534
Given that over 500 maintainers and reviewers use gmail, it implies it is widely relied upon. I even recall Linus mentioning issues with gmail spam filters regarding PRs in the past t (though I am not sure of the exact association between linux-foundation.org and gmail), suggesting that even at that level, gmail is part of the workflow.
TBH, if these emails were simply going to spam, it wouldn't be an issue as I check that folder regularly. The problem here is that Maciej's emails aren't even in spam.
That said, if direct emails continue to vanish like this, I may indeed have to start looking for an alternative. (sigh...)
Regards,
Kuan-Wei
Maciej W. Rozycki
maintainerRe: [RFC PATCH 2/2] treewide, bits: use ffs_val() where it is open-coded
Quoted 10 lines · Kuan-Wei Chiu
Quoted 10 lines
Quoted 3 lines
Since there are other gmail users on this thread (e.g., David, whom I assume received it successfully given the reply), I am wondering if anyone else using gmail experienced similar issues with this message?
Me 'David' ?
I'm actually subscribed to the lists on a different email provider. I used to use gmail, but it bounces, spams and just plain discards far too many messages to reliably receive lkml and friends.
I post from the gmail address to avoid leaking the other address to spammers.
Quoted 5 lines
Ah, I misunderstood. I thought you were receiving on gmail as well.
I actually just missed another reply from Maciej (again, nothing in spam). It appears gmail has decided to silently drop messages from him for some reason.
Not at all silent, GMail rejects any e-mail sent here and I get a bounce
every time. It has been like this for a while now. I'm not going to do anything about it, my SMTP service complies with the relevant RFC AFAIK and GMail is the only recipient showing any issues.
FWIW I chose to host my e-mail myself for the very reason to avoid any
odd limitations imposed by professional hosting services and have the choice to use my own tools to process e-mail. I have no direct influence on other people's choices. I'll appreciate your understanding.
Maciej
Kuan-Wei Chiu
maintainerHi Petr,
Quoted 7 lines · Petr Tesarik
Isolation of the least significant bit can be achieved with 3 basic ALU operations which are already open-coded in various places in the kernel.
However, since other places less efficient constructs, for example
1UL << ffs(x), I assume the trick is known only to some authors, and it's worth adding a helper to promote its use.
Just out of curiosity, are there any existing users employing 1 << ffs(x) (or other inefficient variants) in performance-critical hotpaths?
From a quick grep, I only found one instance in drivers/clk/ti/mux.c matching the 1 << ffs(x) pattern. However, this doesn't appear to be a bottleneck since it is followed by ti_clk_ll_ops->clk_writel(...). The latency of the MMIO write would likely overshadow the savings of a few ALU cycles.
Additionally, it seems that patch #2 focuses on replacing the x & -x implementation with the new API, rather than converting inefficient constructs like 1 << ffs(x) to use ffs_val().
Regards,
Kuan-Wei
Quoted 41 lines
Petr Tesarik (2):
bits: introduceffs_val()
treewide, bits: useffs_val()where it is open-codedarch/alpha/include/asm/bitops.h | 2 +- arch/alpha/kernel/core_cia.c | 2 +- arch/alpha/kernel/smp.c | 2 +- arch/arc/include/asm/bitops.h | 2 +- arch/m68k/include/asm/bitops.h | 12 +++++------ arch/mips/dec/ecc-berr.c | 2 +- arch/mips/include/asm/bitops.h | 4 ++-- arch/mips/pci/pci-malta.c | 4 ++-- arch/powerpc/include/asm/bitops.h | 4 ++-- arch/powerpc/kvm/e500_mmu_host.c | 2 +- arch/powerpc/lib/sstep.c | 2 +- arch/powerpc/xmon/ppc-dis.c | 3 ++- arch/powerpc/xmon/ppc-opc.c | 6 +++--- arch/s390/include/asm/bitops.h | 2 +- arch/xtensa/include/asm/bitops.h | 6 +++--- arch/xtensa/kernel/traps.c | 2 +- drivers/gpu/drm/gma500/psb_intel_sdvo.c | 2 +- drivers/iommu/dma-iommu.c | 2 +- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +- drivers/net/usb/cdc_ncm.c | 4 ++-- include/asm-generic/div64.h | 4 ++-- include/linux/bitfield.h | 3 ++- include/linux/bitops.h | 1 + include/linux/ffs_val.h | 21 ++++++++++++++++++++ include/linux/log2.h | 2 +- include/linux/min_heap.h | 5 +++-- lib/math/gcd.c | 4 ++-- lib/sort.c | 3 ++- net/bluetooth/mgmt.c | 2 +- net/netfilter/nft_set_pipapo.c | 2 +- 30 files changed, 70 insertions(+), 44 deletions(-) create mode 100644 include/linux/ffs_val.hSignature · 1 line
2.52.0
Quoted 15 lines · On Sat, 10 Jan 2026 01:20:59 +0800 Kuan-Wei Chiu <[email protected]> wrote:
Hi Petr,
Quoted 7 lines · Petr Tesarik
Isolation of the least significant bit can be achieved with 3 basic ALU operations which are already open-coded in various places in the kernel.
However, since other places less efficient constructs, for example
1UL << ffs(x), I assume the trick is known only to some authors, and it's worth adding a helper to promote its use.Just out of curiosity, are there any existing users employing 1 << ffs(x) (or other inefficient variants) in performance-critical hotpaths?
Quoted 5 lines
From a quick grep, I only found one instance in
drivers/clk/ti/mux.cmatching the 1 << ffs(x) pattern. However, this doesn't appear to be a bottleneck since it is followed byti_clk_ll_ops->clk_writel(...). The latency of the MMIO write would likely overshadow the savings of a few ALU cycles.
Most expressions are a bit more complex, like this one in page_cache_async_ra():
align = 1UL << min(ra->order, ffs(max_pages) - 1);
Or split across multiple lines, like this one in sata_down_spd_limit():
bit = ffs(mask) - 1; mask = 1 << bit;
I agree that there is most likely no measurable performance win. The resulting machine code merely looks quite silly on architectures without an instruction to do ffs() and a little bit silly on architectures where the instruction has a slightly different semantics (bit position numbering and/or handling of zero value).
Quoted 3 lines
Additionally, it seems that patch #2 focuses on replacing the x & -x implementation with the new API, rather than converting inefficient constructs like 1 << ffs(x) to use
ffs_val().
This is correct. This patch series merely introduces the helper. Patch 2/2 was created mechanically. I haven't sent any follow-up yet to replace inefficient use, because that would require more effort, and I'm trying to get some early feedback first (that's why the series is tagged RFC).
If we agree that it's worth the effort, and I split the patches by subsystem, it may become a rather long series.
Petr T
Quoted 6 lines
arch/alpha/kernel/core_cia.c +0
-0@@ -1035,7 +1035,7 @@ cia_decode_ecc_error(struct el_CIA_sysdata_mcheck *cia, const char *msg) cia_decode_mem_error(cia, msg);
Quoted 7 lines
syn =cia->cia_syn&0xff;
- if (syn == (syn & -syn)) {
+ if (syn ==ffs_val(syn)) {
fmt =KERN_CRIT" ECC syndrome %#x -- check bit %d\n"; i = ffs(syn) - 1;
} else {
This is a check for multiple bits set, which has a simpler expression to calculate. (the ffs() in context shows that syn isn't expected to be 0.)
In Xen I added this helper while tiding things up, and it's applicable to the more common pattern of checking hweight() of a bitmap against 1.
/*
* Calculate if a value has two or more bits set. Always use this in
* preference to an expression of the form 'hweight(x) > 1'. */
#define multiple_bits_set(x) \
({ \
typeof(x) _v = (x); \
(_v & (_v - 1)) != 0; \
})
~Andrew