Improve generic fls64 for 64-bit machines
Subsystems (25)
cover Improve generic fls64 for 64-bit machines
This series of patches:
[1/3] adds __fls.h to asm-generic
[2/3] modifies asm-*/bitops.h for 64-bit archs to implement __fls [3/3] modifies asm-generic/fls64.h to make use of __fls
I have compiled i386 and x86_64, and they generate the same code as before the change. The changes to the other archs are a best effort. Please comment.
If this patch series is accepted, it will make one tiny bit of the x86-unification a tiny bit cleaner. The patches are against Linus' current tree.
Andrew, if no concensus can be reached that this is a bad patch series, would you be willing to add this to your tree?
Greetings,
Alexander
--
To unsubscribe from this list: send the line "unsubscribe linux-arch" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH 1/3 Introduce a generic __fls implementation
Add a generic __fls implementation in the same spirit as the generic __ffs one. It finds the last (most significant) set bit in the given long value.
--- include/asm-generic/bitops/__fls.h | 43 ++++++++++++++++++++++++++++++++++++ 1 files changed, 43 insertions(+), 0 deletions(-) create mode 100644 include/asm-generic/bitops/__fls.h
include/asm-generic/bitops/__fls.h new file +43 -0
@@ -0,0 +1,43 @@ +#ifndef _ASM_GENERIC_BITOPS___FLS_H_ +#define _ASM_GENERIC_BITOPS___FLS_H_ + +#include <asm/types.h> + +/** +* __fls - find last (most-significant) set bit in a long word +* @word: the word to search +* +* Undefined if no set bit exists, so code should check against 0 first. +*/ +static inline unsigned long __fls (unsigned long word) +{ +int num =BITS_PER_LONG -1 ; + +#if BITS_PER_LONG ==64 +if (!(word & (~0ul <<32 ))) { + num -=32 ; + word <<=32 ; + } +#endif +if (!(word & (~0ul << (BITS_PER_LONG -16 )))) { + num -=16 ; + word <<=16 ; + } +if (!(word & (~0ul << (BITS_PER_LONG -8 )))) { + num -=8 ; + word <<=8 ; + } +if (!(word & (~0ul << (BITS_PER_LONG -4 )))) { + num -=4 ; + word <<=4 ; + } +if (!(word & (~0ul << (BITS_PER_LONG -2 )))) { + num -=2 ; + word <<=2 ; + } +if (!(word & (~0ul << (BITS_PER_LONG -1 )))) + num -=1 ; +return num; +} + +#endif /* _ASM_GENERIC_BITOPS___FLS_H_ */
--
To unsubscribe from this list: send the line "unsubscribe linux-arch" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH 2/3 Implement __fls on all 64-bit archs
In reply to Alexander van HeukelumImplement __fls on all 64-bit archs:
alpha has an implementation of fls64.
Added __fls(x) = fls64(x) - 1.
ia64 has fls, but not __fls.
Added __fls based on code of fls.
mips and powerpc have __ilog2, which is the same as __fls.
Added __fls = __ilog2.
parisc, s390, sh and sparc64:
Include generic __fls.
x86_64 already has __fls.
--- include/asm-alpha/bitops.h | 5 +++++ include/asm-ia64/bitops.h | 16 ++++++++++++++++ include/asm-mips/bitops.h | 5 +++++ include/asm-parisc/bitops.h | 1 + include/asm-powerpc/bitops.h | 5 +++++ include/asm-s390/bitops.h | 1 + include/asm-sh/bitops.h | 1 + include/asm-sparc64/bitops.h | 1 + 8 files changed, 35 insertions(+), 0 deletions(-)
include/asm-alpha/bitops.h +5 -0
@@ -388,6 +388,11 @@ static inline int fls64(unsigned long x) }#endif +static inline unsigned long __fls (unsigned long x) +{ +return fls64 (x) -1 ; +} +static inline int fls (int x) {return fls64 ((unsigned int ) x);
include/asm-ia64/bitops.h +16 -0
@@ -407,6 +407,22 @@ fls (int t)return ia64_popcnt (x); } +/* +* Find the last (most significant) bit set. Undefined for x==0. +* Bits are numbered from 0..63 (e.g., __fls(9) == 3). +*/ +static inline unsigned long +__fls (unsigned long x) +{ + x |= x >>1 ; + x |= x >>2 ; + x |= x >>4 ; + x |= x >>8 ; + x |= x >>16 ; + x |= x >>32 ; +return ia64_popcnt (x) -1 ; +} +#include <asm-generic/bitops/fls64.h> /*
include/asm-mips/bitops.h +5 -0
@@ -591,6 +591,11 @@ static inline int __ilog2(unsigned long x)return 63 - lz; } +static inline unsigned long __fls (unsigned long x) +{ +return __ilog2 (x); +} +#if defined(CONFIG_CPU_MIPS32 ) || defined(CONFIG_CPU_MIPS64 )/*
include/asm-parisc/bitops.h +1 -0
@@ -210,6 +210,7 @@ static __inline__ int fls(int x)return ret; } +#include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/lock.h>
include/asm-powerpc/bitops.h +5 -0
@@ -312,6 +312,11 @@ static __inline__ int fls(unsigned int x) asm ("cntlzw %0,%1" :"=r" (lz) :"r" (x));return 32 - lz; } + +static __inline__unsigned long __fls (unsigned long x) +{ +return __ilog2 (x); +}#include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/hweight.h>
include/asm-s390/bitops.h +1 -0
@@ -769,6 +769,7 @@ static inline int sched_find_first_bit(unsigned long *b) }#include <asm-generic/bitops/fls.h> +#include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/hweight.h>
include/asm-sh/bitops.h +1 -0
@@ -95,6 +95,7 @@ static inline unsigned long ffz(unsigned long word)#include <asm-generic/bitops/ext2-atomic.h> #include <asm-generic/bitops/minix.h> #include <asm-generic/bitops/fls.h> +#include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> #endif /* __KERNEL__ */
include/asm-sparc64/bitops.h +1 -0
@@ -34,6 +34,7 @@ extern void change_bit(unsigned long nr, volatile unsigned long *addr);#include <asm-generic/bitops/ffz.h> #include <asm-generic/bitops/__ffs.h> #include <asm-generic/bitops/fls.h> +#include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> #ifdef __KERNEL__
--
To unsubscribe from this list: send the line "unsubscribe linux-arch" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH 3/3 Use __fls for fls64 on 64-bit archs
In reply to Alexander van HeukelumUse __fls for fls64 on 64-bit archs. The implementation for 64-bit archs is moved from x86_64 to asm-generic.
--- include/asm-generic/bitops/fls64.h | 22 ++++++++++++++++++++++ include/asm-x86/bitops_64.h | 15 ++------------- 2 files changed, 24 insertions(+), 13 deletions(-)
include/asm-generic/bitops/fls64.h +22 -0
@@ -3,6 +3,18 @@#include <asm/types.h> +/** +* fls64 - find last set bit in a 64-bit word +* @x: the word to search +* +* This is defined in a similar way as the libc and compiler builtin +* ffsll, but returns the position of the most significant set bit. +* +* fls64(value) returns 0 if value is 0 or the position of the last +* set bit if value is nonzero. The last (most significant) bit is +* at position 64. +*/ +#if BITS_PER_LONG ==32 static inline int fls64 (__u64 x) {__u32 h = x >>32 ;
@@ -10,5 +22,15 @@ static inline int fls64(__u64 x)return fls (h) +32 ;return fls (x); } +#elif BITS_PER_LONG ==64 +static inline int fls64 (__u64 x) +{ +if (x ==0 ) +return 0 ; +return __fls (x) +1 ; +} +#else +#error BITS_PER_LONG not 32 or 64 +#endif #endif /* _ASM_GENERIC_BITOPS_FLS64_H_ */
include/asm-x86/bitops_64.h +2 -13
@@ -112,19 +112,6 @@ static inline int ffs(int x) }/** -* fls64 - find last bit set in 64 bit word -* @x: the word to search -* -* This is defined the same way as fls. -*/ -static inline int fls64 (__u64 x) -{ -if (x ==0 ) -return 0 ; -return __fls (x) +1 ; -} - -/** * fls - find last bit set * @x: the word to search *
@@ -146,6 +133,8 @@ static inline int fls(int x)#endif /* __KERNEL__ */ +#include <asm-generic/bitops/fls64.h> +#ifdef __KERNEL__#include <asm-generic/bitops/ext2-non-atomic.h>
--
To unsubscribe from this list: send the line "unsubscribe linux-arch" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [3/3] Use __fls for fls64 on 64-bit archs
(Sorry, sending this again as I screwed up the previous mail).
Hi,
I have a question about fls64() which I hope you or someone else could clarify, please see below.
include/asm-generic/bitops/fls64.h static inline int fls64(__u64 x) · line 31
Quoted 7 lines · Alexander van Heukelum
include/asm-generic/bitops/fls64.h +7
-0+#elif BITS_PER_LONG ==64 +static inline int fls64 (__u64 x) +{ +if (x ==0 ) +return 0 ; +return __fls (x) +1 ; +}
It seems fls64() is implemented on top of __fls(), however the __fls() implementation on the x86-64 architecture states that the result is undefined if the argument does not have any zero bits.
So if I understand correctly, the statement "fls64(~0ULL)" would return an undefined result on x64-64 instead of 64 as one would expect.
Wouldn't it make sense to check for ~0ULL in fls64()?
Thanks,
Ricardo
PATCH 1/1 x86: fix description of __fls(): __fls(0) is undefined
Ricardo M. Correia spotted that the use of __fls() in fls64() did not seem to make sense. In fact fls64()'s implementation is fine, but the description of __fls() was wrong. Fix that.
---
Quoted 6 lines · Ricardo M. Correia
Hi,
I have a question about
fls64()which I hope you or someone else could clarify, please see below.On Sáb, 2008-03-15 at 18:32 +0100, Alexander van Heukelum wrote:
Quoted 11 lines
Review
Quoted 7 lines
(quoted diff) +7
-0+#elif BITS_PER_LONG == 64 +static inline int fls64(__u64 x) +{ + if (x == 0) + return 0; + return __fls(x) + 1; +}It seems
fls64()is implemented on top of__fls(), however the__fls()implementation on the x86-64 architecture states that the result is undefined if the argument does not have any zero bits.
You have found a bug. It's not in fls64, though, but a copy/paste one in the comment preceding __fls(). __fls() gives an undefined result if there are no _set_ bits: only __fls(0) gives an undefined result.
The inconsistency is well-spotted, though, thanks.
Patch is against current -tip.
Greetings,
Alexander
Quoted 7 lines
So if I understand correctly, the statement "fls64(~0ULL)" would return an undefined result on x64-64 instead of 64 as one would expect.
Wouldn't it make sense to check for ~0ULL in
fls64()?Thanks,
Ricardo
---
include/asm-x86/bitops.h +1 -1
@@ -356,7 +356,7 @@ static inline unsigned long ffz(unsigned long word)* __fls: find last set bit in word * @word: The word to search * -* Undefined if no zero exists, so code should check against ~0UL first. +* Undefined if no set bit exists, so code should check against 0 first. */ static inline unsigned long __fls (unsigned long word) {
Ingo Molnar
AppliedRe: [PATCH] x86: fix description of __fls(): __fls(0) is undefined
Quoted 6 lines · Alexander van Heukelum
Ricardo M. Correia spotted that the use of
__fls()infls64()did not seem to make sense. In fact fls64()'s implementation is fine, but the description of__fls()was wrong. Fix that.Reported-by "Ricardo M. Correia" <[email protected]>Signed-off-by Alexander van Heukelum <[email protected]>
applied to tip/x86/cleanups, thanks!
Ingo
Quoted 9 lines · Alexander van Heukelum
This series of patches:
[1/3] adds
__fls.hto asm-generic
[2/3] modifiesasm-*/bitops.hfor 64-bit archs to implement__fls[3/3] modifiesasm-generic/fls64.hto make use of__flsI have compiled i386 and
x86_64, and they generate the same code as before the change. The changes to the other archs are a best effort. Please comment.
i've applied #1 and #3 to x86.git/testing, to see how this works out on x86. But it looks good to me in general.
Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-arch" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 5 lines · Alexander van Heukelum
This series of patches:
[1/3] adds
__fls.hto asm-generic
[2/3] modifiesasm-*/bitops.hfor 64-bit archs to implement__fls[3/3] modifiesasm-generic/fls64.hto make use of__fls
I strongly support this.
I wish we'd also have a consistent naming convention for all the bitops functions so it will be clearer what data type the function is working on and is the result 0 or 1 based.
It seems like what we currently have is:
name type first bit#
---- ---- ----------
ffs int 1
fls int 1__ffs ulong 0__fls ulong 0 # in your proposal
ffz ulong 0
fls64 __u64 1
so it seems like
- ffz is misnamed and is rather confusing.
Apprently is should be renamed to __ffz.
- (new) ffz(x) can be defined to ffs(~(x))
- It'd be nice to have ffs64, and maybe ffz64.
Benny
Quoted 19 lines
I have compiled i386 and
x86_64, and they generate the same code as before the change. The changes to the other archs are a best effort. Please comment.If this patch series is accepted, it will make one tiny bit of the x86-unification a tiny bit cleaner. The patches are against Linus' current tree.
Andrew, if no concensus can be reached that this is a bad patch series, would you be willing to add this to your tree?
Greetings,
Alexander
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 28 lines · Benny Halevy
Quoted 5 lines · Alexander van Heukelum
This series of patches:
[1/3] adds
__fls.hto asm-generic
[2/3] modifiesasm-*/bitops.hfor 64-bit archs to implement__fls[3/3] modifiesasm-generic/fls64.hto make use of__flsI strongly support this.
I wish we'd also have a consistent naming convention for all the bitops functions so it will be clearer what data type the function is working on and is the result 0 or 1 based.
It seems like what we currently have is:
name type first bit#
---- ---- ----------
ffs int 1
fls int 1__ffsulong 0__flsulong 0 # in your proposal
ffz ulong 0
fls64__u641so it seems like
- ffz is misnamed and is rather confusing.
Apprently is should be renamed to__ffz.
Quoted 5 lines
- (new) ffz(x) can be defined to ffs(~(x))
- It'd be nice to have ffs64, and maybe ffz64.
Benny
I think every programmer who thinks in terms of bits realises that ffz(x) == __ffs(~x) and ffz(~x) == __ffs(x) etc... so I would rather get rid of ffz entirely by converting all uses to __ffs. Patch (against current linus) below. After that all implementations of ffz could be removed.
ffs64 would be a good addition to complete the set of functions, but that would be the same as glibc's (and gcc-builtin) ffsll.
Looking into that... the relevant gcc builtins are __builtin_ffs (find first set bit), __builtin_clz (count leading zeroes), __builtin_ctz (count trailing zeroes), __builtin_popcount, maybe __builtin_parity and their -l and -ll variants. Maybe the kernel should be changed to use those names instead of the current ones? ffs would stay as it is. __ffs would become ctz, __fls would become something like 31-clz, and hweight would become popcount.
Greetings,
Alexander
[RFC] how about getting rid of ffz?
The patch is not tested, but the conversion should be completely trivial.
---
arch/alpha/kernel/irq_i8259.c | 2 +- arch/alpha/kernel/irq_pyxis.c | 2 +- arch/alpha/kernel/sys_alcor.c | 2 +- arch/alpha/kernel/sys_cabriolet.c | 2 +- arch/alpha/kernel/sys_dp264.c | 2 +- arch/alpha/kernel/sys_eb64p.c | 2 +- arch/alpha/kernel/sys_mikasa.c | 2 +- arch/alpha/kernel/sys_noritake.c | 2 +- arch/alpha/kernel/sys_rx164.c | 2 +- arch/arm/kernel/smp.c | 2 +- arch/ia64/hp/common/sba_iommu.c | 2 +- arch/ia64/kernel/perfmon.c | 2 +- arch/ia64/kernel/smp.c | 2 +- arch/ia64/mm/init.c | 2 +- arch/mips/kernel/irixelf.c | 2 +- arch/parisc/kernel/smp.c | 2 +- arch/sh/kernel/cpu/irq/imask.c | 2 +- block/blk-barrier.c | 2 +- crypto/lrw.c | 2 +- drivers/ieee1394/pcilynx.c | 2 +- drivers/input/keyboard/hilkbd.c | 2 +- drivers/md/bitmap.c | 4 ++-- drivers/md/md.c | 2 +- drivers/md/raid0.c | 2 +- drivers/md/raid10.c | 2 +- drivers/net/wan/cycx_x25.c | 2 +- drivers/scsi/NCR_Q720.c | 2 +- fs/adfs/map.c | 4 ++-- fs/binfmt_elf.c | 2 +- fs/binfmt_elf_fdpic.c | 2 +- fs/ntfs/mft.c | 2 +- fs/udf/balloc.c | 2 +- fs/xfs/xfs_bit.c | 2 +- include/asm-m68knommu/bitops.h | 4 ++-- include/linux/inetdevice.h | 2 +- include/linux/signal.h | 2 +- kernel/signal.c | 6 +++--- lib/find_next_bit.c | 6 +++--- mm/page_alloc.c | 2 +- net/sched/sch_cbq.c | 4 ++-- net/sched/sch_htb.c | 10 +++++----- sound/core/oss/mixer_oss.c | 2 +- 42 files changed, 54 insertions(+), 54 deletions(-)
arch/alpha/kernel/irq_i8259.c +1 -1
@@ -174,7 +174,7 @@ isa_no_iack_sc_device_interrupt(unsigned long vector) pic &=0xFFFB ;/* mask out cascade & hibits */ while (pic) { -int j =ffz (~pic); +int j =__ffs (pic); pic &= pic -1 ;handle_irq (j); }
arch/alpha/kernel/irq_pyxis.c +1 -1
@@ -95,7 +95,7 @@ pyxis_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==7 )isa_device_interrupt (vector);
arch/alpha/kernel/sys_alcor.c +1 -1
@@ -113,7 +113,7 @@ alcor_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==31 ) {isa_device_interrupt (vector);
arch/alpha/kernel/sys_cabriolet.c +1 -1
@@ -95,7 +95,7 @@ cabriolet_device_interrupt(unsigned long v)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==4 ) {isa_device_interrupt (v);
arch/alpha/kernel/sys_dp264.c +1 -1
@@ -233,7 +233,7 @@ dp264_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==55 )isa_device_interrupt (vector);
arch/alpha/kernel/sys_eb64p.c +1 -1
@@ -93,7 +93,7 @@ eb64p_device_interrupt(unsigned long vector)* them and call the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==5 ) {
arch/alpha/kernel/sys_mikasa.c +1 -1
@@ -94,7 +94,7 @@ mikasa_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i <16 ) {isa_device_interrupt (vector);
arch/alpha/kernel/sys_noritake.c +1 -1
@@ -100,7 +100,7 @@ noritake_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i <16 ) {isa_device_interrupt (vector);
arch/alpha/kernel/sys_rx164.c +1 -1
@@ -99,7 +99,7 @@ rx164_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==20 ) {isa_no_iack_sc_device_interrupt (vector);
arch/arm/kernel/smp.c +1 -1
@@ -596,7 +596,7 @@ asmlinkage void __exception do_IPI(struct pt_regs *regs) nextmsg = msgs & -msgs; msgs &= ~nextmsg; - nextmsg =ffz (~nextmsg); + nextmsg =__ffs (nextmsg);switch (nextmsg) {case IPI_TIMER :
arch/ia64/hp/common/sba_iommu.c +1 -1
@@ -502,7 +502,7 @@ sba_search_bitmap(struct ioc *ioc, unsigned long bits_wanted, int use_hint)unsigned int bitshiftcnt;for (; res_ptr < res_end ; res_ptr++) {if (likely (*res_ptr != ~0UL )) { - bitshiftcnt =ffz (*res_ptr); + bitshiftcnt =__ffs (~(*res_ptr)); *res_ptr |= (1UL << bitshiftcnt); pide = ((unsigned long )res_ptr - (unsigned long )ioc->res_map); pide <<=3 ;/* convert to bit address */
arch/ia64/kernel/perfmon.c +1 -1
@@ -6683,7 +6683,7 @@ pfm_init(void) pmu_conf->num_pmcs, pmu_conf->num_pmds, pmu_conf->num_counters, - ffz(pmu_conf->ovfl_val)); + __ffs(~(pmu_conf->ovfl_val)));/* sanity check */ if (pmu_conf->num_pmds >=PFM_NUM_PMD_REGS || pmu_conf->num_pmcs >=PFM_NUM_PMC_REGS ) {
arch/ia64/kernel/smp.c +1 -1
@@ -134,7 +134,7 @@ handle_IPI (int irq, void *dev_id) do { unsigned long which; - which = ffz(~ops); + which = __ffs(ops); ops &= ~(1 << which); switch (which) {
arch/ia64/mm/init.c +1 -1
@@ -333,7 +333,7 @@ ia64_mmu_init (void *my_cpu_data)# define vmlpt_bits (impl_va_bits - PAGE_SHIFT + pte_bits)# define POW2 (n) (1ULL << (n)) - impl_va_bits =ffz (~(local_cpu_data->unimpl_va_mask | (7UL <<61 ))); + impl_va_bits =__ffs (local_cpu_data->unimpl_va_mask | (7UL <<61 ));if (impl_va_bits <51 || impl_va_bits >61 )panic ("CPU has bogus IMPL_VA_MSB value of %lu!\n" , impl_va_bits -1 );
arch/mips/kernel/irixelf.c +1 -1
@@ -1207,7 +1207,7 @@ static int irix_core_dump(long signr, struct pt_regs *regs, struct file *file, u notes[1 ].type =NT_PRPSINFO ; notes[1 ].datasz =sizeof (psinfo); notes[1 ].data = &psinfo; - i = current->state ?ffz (~current->state) +1 :0 ; + i = current->state ?__ffs (current->state) +1 :0 ; psinfo.pr_state = i; psinfo.pr_sname = (i <0 || i >5 ) ?'.' :"RSDZTD" [i]; psinfo.pr_zomb = psinfo.pr_sname =='Z' ;
arch/parisc/kernel/smp.c +1 -1
@@ -168,7 +168,7 @@ ipi_interrupt(int irq, void *dev_id)break ;while (ops) { -unsigned long which =ffz (~ops); +unsigned long which =__ffs (ops); ops &= ~(1 << which);
arch/sh/kernel/cpu/irq/imask.c +1 -1
@@ -84,7 +84,7 @@ static void disable_imask_irq(unsigned int irq)static void enable_imask_irq (unsigned int irq) {set_bit (irq, &imask_mask); - interrupt_priority =IMASK_PRIORITY -ffz (imask_mask); + interrupt_priority =IMASK_PRIORITY -__ffs (~imask_mask);set_interrupt_registers (interrupt_priority); }
block/blk-barrier.c +1 -1
@@ -57,7 +57,7 @@ inline unsigned blk_ordered_cur_seq(struct request_queue *q) {if (!q->ordseq)return 0 ; -return 1 <<ffz (q->ordseq); +return 1 <<__ffs (~(q->ordseq)); }unsigned blk_ordered_req_seq (struct request *rq)
crypto/lrw.c +1 -1
@@ -115,7 +115,7 @@ static inline int get_index128(be128 *block)if (!~val)continue ; -return x +ffz (val); +return x +__ffs (~val); }return x;
drivers/ieee1394/pcilynx.c +1 -1
@@ -141,7 +141,7 @@ static pcl_t alloc_pcl(struct ti_lynx *lynx)int i, j;spin_lock (&lynx->lock); -/* FIXME - use ffz() to make this readable */ +/* FIXME - use __ffs() to make this readable */ for (i =0 ; i < (LOCALRAM_SIZE /1024 ); i++) { m = lynx->pcl_bmap[i];for (j =0 ; j <8 ; j++) {
drivers/input/keyboard/hilkbd.c +1 -1
@@ -254,7 +254,7 @@ hil_keyb_init(void) kbid =-1 ;printk (KERN_WARNING "HIL: no keyboard present\n" ); }else { - kbid =ffz (~c); + kbid =__ffs (c);printk (KERN_INFO "HIL: keyboard found at id %d\n" , kbid); }
drivers/md/bitmap.c +2 -2
@@ -538,7 +538,7 @@ static int bitmap_read_sb(struct bitmap *bitmap) reason ="unrecognized superblock version" ; else if (chunksize < PAGE_SIZE) reason ="bitmap chunksize too small" ; - else if ((1 << ffz(~chunksize)) != chunksize) + else if ((1 << __ffs(chunksize)) != chunksize) reason = "bitmap chunksize not a power of 2"; else if (daemon_sleep < 1 || daemon_sleep > MAX_SCHEDULE_TIMEOUT / HZ) reason ="daemon sleep period out of range" ;
@@ -1540,7 +1540,7 @@ int bitmap_create(mddev_t *mddev)if (err) goto error; - bitmap->chunkshift =ffz (~bitmap->chunksize); + bitmap->chunkshift =__ffs (bitmap->chunksize);/* now that chunksize and chunkshift are set, we can use these macros */ chunks = (blocks + CHUNK_BLOCK_RATIO(bitmap) - 1) /
drivers/md/md.c +1 -1
@@ -3316,7 +3316,7 @@ static int do_md_run(mddev_t * mddev)/* * chunk-size has to be a power of 2 and multiples of PAGE_SIZE */ -if ( (1 <<ffz (~chunk_size)) != chunk_size) { +if ( (1 <<__ffs (chunk_size)) != chunk_size) {printk (KERN_ERR "chunk_size of %d not valid\n" , chunk_size);return -EINVAL ; }
drivers/md/raid0.c +1 -1
@@ -407,7 +407,7 @@ static int raid0_make_request (struct request_queue *q, struct bio *bio) chunk_size = mddev->chunk_size >>10 ; chunk_sects = mddev->chunk_size >>9 ; - chunksize_bits =ffz (~chunk_size); + chunksize_bits =__ffs (chunk_size); block = bio->bi_sector >>1 ;
drivers/md/raid10.c +1 -1
@@ -2029,7 +2029,7 @@ static int run(mddev_t *mddev) conf->copies = nc*fc; conf->far_offset = fo; conf->chunk_mask = (sector_t)(mddev->chunk_size>>9 )-1 ; - conf->chunk_shift =ffz (~mddev->chunk_size) -9 ; + conf->chunk_shift =__ffs (mddev->chunk_size) -9 ; size = mddev->size >> (conf->chunk_shift-1 );sector_div (size, fc); size = size * conf->raid_disks;
drivers/net/wan/cycx_x25.c +1 -1
@@ -1207,7 +1207,7 @@ static int x25_place_call(struct cycx_device *card,return -EAGAIN ; } - key =ffz (card->u.x.connection_keys); + key =__ffs (~(card->u.x.connection_keys));set_bit (key, (void *)&card->u.x.connection_keys); ++key;dprintk (1 ,KERN_INFO "%s:x25_place_call:key=%d\n" , card->devname, key);
drivers/scsi/NCR_Q720.c +1 -1
@@ -66,7 +66,7 @@ NCR_Q720_intr(int irq, void *data)return IRQ_NONE ; -while ((siop =ffz (sir)) < p->siops) { +while ((siop =__ffs (~sir)) < p->siops) { sir |=1 <<siop;ncr53c8xx_intr (irq, p->hosts[siop]); }
fs/adfs/map.c +2 -2
@@ -101,7 +101,7 @@ lookup_zone(const struct adfs_discmap *dm, const unsigned int idlen, v =le32_to_cpu (_map[mapptr >>5 ]); } - mapptr +=1 +ffz (~v); + mapptr +=1 +__ffs (v); }if (frag == frag_id)
@@ -179,7 +179,7 @@ scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm) v =le32_to_cpu (_map[mapptr >>5 ]); } - mapptr +=1 +ffz (~v); + mapptr +=1 +__ffs (v); } total += mapptr - start;
fs/binfmt_elf.c +1 -1
@@ -1383,7 +1383,7 @@ static int fill_psinfo(struct elf_prpsinfo *psinfo, struct task_struct *p, psinfo->pr_pgrp =task_pgrp_vnr (p); psinfo->pr_sid =task_session_vnr (p); - i = p->state ?ffz (~p->state) +1 :0 ; + i = p->state ?__ffs (p->state) +1 :0 ; psinfo->pr_state = i; psinfo->pr_sname = (i >5 ) ?'.' :"RSDTZW" [i]; psinfo->pr_zomb = psinfo->pr_sname =='Z' ;
fs/binfmt_elf_fdpic.c +1 -1
@@ -1396,7 +1396,7 @@ static int fill_psinfo(struct elf_prpsinfo *psinfo, struct task_struct *p, psinfo->pr_pgrp =task_pgrp_vnr (p); psinfo->pr_sid =task_session_vnr (p); - i = p->state ?ffz (~p->state) +1 :0 ; + i = p->state ?__ffs (p->state) +1 :0 ; psinfo->pr_state = i; psinfo->pr_sname = (i >5 ) ?'.' :"RSDTZW" [i]; psinfo->pr_zomb = psinfo->pr_sname =='Z' ;
fs/ntfs/mft.c +1 -1
@@ -1207,7 +1207,7 @@ static int ntfs_mft_bitmap_find_and_alloc_free_rec_nolock(ntfs_volume *vol, byte = buf + (bit >>3 );if (*byte ==0xff )continue ; - b =ffz ((unsigned long )*byte); + b =__ffs (~((unsigned long )*byte));if (b <8 && b >= (bit &7 )) { ll = data_pos + (bit & ~7ull ) + b;if (unlikely (ll > (1ll <<32 ))) {
fs/udf/balloc.c +1 -1
@@ -75,7 +75,7 @@ static inline int find_next_one_bit(void *addr, int size, int offset) found_first: tmp &= ~0UL >> (BITS_PER_LONG - size); found_middle: -return result +ffz (~tmp); +return result +__ffs (tmp); }#define find_first_one_bit (addr, size)\
fs/xfs/xfs_bit.c +1 -1
@@ -179,7 +179,7 @@ xfs_contig_bits(uint *map, uint size, uint start_bit) }return result - start_bit; found: -return result +ffz (tmp) - start_bit; +return result +__ffs (~tmp) - start_bit; }/*
include/asm-m68knommu/bitops.h +2 -2
@@ -289,9 +289,9 @@ found_first:* see above. But then we have to swab tmp below for ffz, so * we might as well do this here. */ -return result +ffz (__swab32 (tmp) | (~0UL << size)); +return result +__ffs (~(__swab32 (tmp) | (~0UL << size))); found_middle: -return result +ffz (__swab32 (tmp)); +return result +__ffs (~(__swab32 (tmp))); }#define ext2_find_next_bit (addr, size, off) \
include/linux/inetdevice.h +1 -1
@@ -217,7 +217,7 @@ static __inline__ int inet_mask_len(__be32 mask)__u32 hmask =ntohl (mask);if (!hmask)return 0 ; -return 32 -ffz (~hmask); +return 32 -__ffs (hmask); }
include/linux/signal.h +1 -1
@@ -64,7 +64,7 @@ static inline int sigismember(sigset_t *set, int _sig)static inline int sigfindinword (unsigned long word) { -return ffz (~word); +return __ffs (word); }#endif /* __HAVE_ARCH_SIG_BITOPS */
kernel/signal.c +3 -3
@@ -142,7 +142,7 @@ int next_signal(struct sigpending *pending, sigset_t *mask)default :for (i =0 ; i < _NSIG_WORDS; ++i, ++s, ++m)if ((x = *s &~ *m) !=0 ) { - sig =ffz (~x) + i*_NSIG_BPW +1 ; + sig =__ffs (x) + i*_NSIG_BPW +1 ;break ; }break ;
@@ -153,11 +153,11 @@ int next_signal(struct sigpending *pending, sigset_t *mask) sig = _NSIG_BPW +1 ; else break; - sig +=ffz (~x); + sig +=__ffs (x);break ;case 1 :if ((x = *s &~ *m) !=0 ) - sig =ffz (~x) +1 ; + sig =__ffs (x) +1 ;break ; }
lib/find_next_bit.c +3 -3
@@ -103,7 +103,7 @@ found_first:if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle: -return result +ffz (tmp); +return result +__ffs (~tmp); }EXPORT_SYMBOL (find_next_zero_bit);
@@ -170,10 +170,10 @@ found_first:if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. Skip ffz */ found_middle: -return result +ffz (tmp); +return result +__ffs (~tmp); found_middle_swap: -return result +ffz (ext2_swab (tmp)); +return result +__ffs (~(ext2_swab (tmp))); }EXPORT_SYMBOL (generic_find_next_zero_le_bit);
mm/page_alloc.c +1 -1
@@ -2447,7 +2447,7 @@ static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)*/ static inline unsigned long wait_table_bits (unsigned long size) { -return ffz (~size); +return __ffs (size); }#define LONG_ALIGN (x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
net/sched/sch_cbq.c +2 -2
@@ -637,7 +637,7 @@ static enum hrtimer_restart cbq_undelay(struct hrtimer *timer) q->pmask =0 ;while (pmask) { -int prio =ffz (~pmask); +int prio =__ffs (pmask);psched_tdiff_t tmp; pmask &= ~(1 <<prio);
@@ -961,7 +961,7 @@ cbq_dequeue_1(struct Qdisc *sch) activemask = q->activemask&0xFF ;while (activemask) { -int prio =ffz (~activemask); +int prio =__ffs (activemask); activemask &= ~(1 <<prio); skb =cbq_dequeue_prio (sch, prio);if (skb)
net/sched/sch_htb.c +5 -5
@@ -343,7 +343,7 @@ static inline void htb_add_class_to_row(struct htb_sched *q, { q->row_mask[cl->level] |= mask;while (mask) { -int prio =ffz (~mask); +int prio =__ffs (mask); mask &= ~(1 << prio);htb_add_to_id_tree (q->row[cl->level] + prio, cl, prio); }
@@ -373,7 +373,7 @@ static inline void htb_remove_class_from_row(struct htb_sched *q,int m =0 ;while (mask) { -int prio =ffz (~mask); +int prio =__ffs (mask); mask &= ~(1 << prio);if (q->ptr[cl->level][prio] == cl->node + prio)
@@ -401,7 +401,7 @@ static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)while (cl->cmode ==HTB_MAY_BORROW && p && mask) { m = mask;while (m) { -int prio =ffz (~m); +int prio =__ffs (m); m &= ~(1 << prio);if (p->un.inner.feed[prio].rb_node)
@@ -436,7 +436,7 @@ static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl) m = mask; mask =0 ;while (m) { -int prio =ffz (~m); +int prio =__ffs (m); m &= ~(1 << prio);if (p->un.inner.ptr[prio] == cl->node + prio) {
@@ -925,7 +925,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch) m = ~q->row_mask[level];while (m != (int )(-1 )) { -int prio =ffz (m); +int prio =__ffs (~m); m |=1 << prio; skb =htb_dequeue_tree (q, prio, level);if (likely (skb !=NULL )) {
sound/core/oss/mixer_oss.c +1 -1
@@ -217,7 +217,7 @@ static int snd_mixer_oss_set_recsrc(struct snd_mixer_oss_file *fmixer, int recsrif (mixer->get_recsrc && mixer->put_recsrc) {/* exclusive input */ if (recsrc & ~mixer->oss_recsrc) recsrc &= ~mixer->oss_recsrc; - mixer->put_recsrc (fmixer,ffz (~recsrc)); + mixer->put_recsrc (fmixer,__ffs (recsrc)); mixer->get_recsrc (fmixer, &result); result =1 << result; }
Quoted 32 lines · Alexander van Heukelum
Quoted 31 lines · Benny Halevy
Quoted 5 lines · Alexander van Heukelum
This series of patches:
[1/3] adds
__fls.hto asm-generic
[2/3] modifiesasm-*/bitops.hfor 64-bit archs to implement__fls[3/3] modifiesasm-generic/fls64.hto make use of__flsI strongly support this.
I wish we'd also have a consistent naming convention for all the bitops functions so it will be clearer what data type the function is working on and is the result 0 or 1 based.
It seems like what we currently have is:
name type first bit#
---- ---- ----------
ffs int 1
fls int 1__ffsulong 0__flsulong 0 # in your proposal
ffz ulong 0
fls64__u641so it seems like
- ffz is misnamed and is rather confusing.
Apprently is should be renamed to__ffz.- (new) ffz(x) can be defined to ffs(~(x))
- It'd be nice to have ffs64, and maybe ffz64.
Quoted 7 lines
Quoted 1 line
Benny
I think every programmer who thinks in terms of bits realises that ffz(x) ==
__ffs(~x)and ffz(~x) ==__ffs(x)etc... so I would rather get rid of ffz entirely by converting all uses to__ffs. Patch (against current linus) below. After that all implementations of ffz could be removed.
Yeah, very few architectures have an optimized version of ffz that will perform noticeably better than __ffs(~x). (e.g. h8300, sh)
Quoted 4 lines
ffs64 would be a good addition to complete the set of functions, but that would be the same as glibc's (and gcc-builtin) ffsll.
Quoted 8 lines
Looking into that... the relevant gcc builtins are
__builtin_ffs(find first set bit),__builtin_clz(count leading zeroes),__builtin_ctz(count trailing zeroes),__builtin_popcount, maybe__builtin_parityand their -l and -ll variants. Maybe the kernel should be changed to use those names instead of the current ones? ffs would stay as it is.__ffswould become ctz,__flswould become something like 31-clz, and hweight would become popcount.
Interesting idea. ctz much better than __ffs with regards to the return value's first bit number, but unless you expose clz and convert the code how do you get rid of the __fls vs. fls confusion?
(BTW for __fls, I'd use BITS_PER_LONG - 1, not 31 :)
I think that adopting libc's convention might make more sense, i.e., define ffs, ffsl, ffsll, and fls, flsl, flsll, and have *all* be 1-based.
Benny
Quoted 703 lines
Greetings,
Alexander[RFC] how about getting rid of ffz?
The patch is not tested, but the conversion should be completely trivial.
Signed-off-by Alexander van Heukelum <[email protected]>---
arch/alpha/kernel/irq_i8259.c | 2 +- arch/alpha/kernel/irq_pyxis.c | 2 +- arch/alpha/kernel/sys_alcor.c | 2 +- arch/alpha/kernel/sys_cabriolet.c | 2 +- arch/alpha/kernel/sys_dp264.c | 2 +- arch/alpha/kernel/sys_eb64p.c | 2 +- arch/alpha/kernel/sys_mikasa.c | 2 +- arch/alpha/kernel/sys_noritake.c | 2 +- arch/alpha/kernel/sys_rx164.c | 2 +- arch/arm/kernel/smp.c | 2 +- arch/ia64/hp/common/sba_iommu.c | 2 +- arch/ia64/kernel/perfmon.c | 2 +- arch/ia64/kernel/smp.c | 2 +- arch/ia64/mm/init.c | 2 +- arch/mips/kernel/irixelf.c | 2 +- arch/parisc/kernel/smp.c | 2 +- arch/sh/kernel/cpu/irq/imask.c | 2 +- block/blk-barrier.c | 2 +- crypto/lrw.c | 2 +- drivers/ieee1394/pcilynx.c | 2 +- drivers/input/keyboard/hilkbd.c | 2 +- drivers/md/bitmap.c | 4 ++-- drivers/md/md.c | 2 +- drivers/md/raid0.c | 2 +- drivers/md/raid10.c | 2 +- drivers/net/wan/cycx_x25.c | 2 +- drivers/scsi/NCR_Q720.c | 2 +- fs/adfs/map.c | 4 ++-- fs/binfmt_elf.c | 2 +- fs/binfmt_elf_fdpic.c | 2 +- fs/ntfs/mft.c | 2 +- fs/udf/balloc.c | 2 +- fs/xfs/xfs_bit.c | 2 +- include/asm-m68knommu/bitops.h | 4 ++-- include/linux/inetdevice.h | 2 +- include/linux/signal.h | 2 +- kernel/signal.c | 6 +++--- lib/find_next_bit.c | 6 +++--- mm/page_alloc.c | 2 +- net/sched/sch_cbq.c | 4 ++-- net/sched/sch_htb.c | 10 +++++----- sound/core/oss/mixer_oss.c | 2 +- 42 files changed, 54 insertions(+), 54 deletions(-)arch/alpha/kernel/irq_i8259.c +1
-1@@ -174,7 +174,7 @@ isa_no_iack_sc_device_interrupt(unsigned long vector) pic &=0xFFFB ;/* mask out cascade & hibits */ while (pic) { -int j =ffz (~pic); +int j =__ffs (pic); pic &= pic -1 ;handle_irq (j); }arch/alpha/kernel/irq_pyxis.c +1
-1@@ -95,7 +95,7 @@ pyxis_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==7 )isa_device_interrupt (vector);arch/alpha/kernel/sys_alcor.c +1
-1@@ -113,7 +113,7 @@ alcor_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==31 ) {isa_device_interrupt (vector);arch/alpha/kernel/sys_cabriolet.c +1
-1@@ -95,7 +95,7 @@ cabriolet_device_interrupt(unsigned long v)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==4 ) {isa_device_interrupt (v);arch/alpha/kernel/sys_dp264.c +1
-1@@ -233,7 +233,7 @@ dp264_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==55 )isa_device_interrupt (vector);arch/alpha/kernel/sys_eb64p.c +1
-1@@ -93,7 +93,7 @@ eb64p_device_interrupt(unsigned long vector)* them and call the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==5 ) {arch/alpha/kernel/sys_mikasa.c +1
-1@@ -94,7 +94,7 @@ mikasa_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i <16 ) {isa_device_interrupt (vector);arch/alpha/kernel/sys_noritake.c +1
-1@@ -100,7 +100,7 @@ noritake_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i <16 ) {isa_device_interrupt (vector);arch/alpha/kernel/sys_rx164.c +1
-1@@ -99,7 +99,7 @@ rx164_device_interrupt(unsigned long vector)* the appropriate interrupt handler. */ while (pld) { - i =ffz (~pld); + i =__ffs (pld); pld &= pld -1 ;/* clear least bit set */ if (i ==20 ) {isa_no_iack_sc_device_interrupt (vector);arch/arm/kernel/smp.c +1
-1@@ -596,7 +596,7 @@ asmlinkage void __exception do_IPI(struct pt_regs *regs) nextmsg = msgs & -msgs; msgs &= ~nextmsg; - nextmsg =ffz (~nextmsg); + nextmsg =__ffs (nextmsg);switch (nextmsg) {case IPI_TIMER :arch/ia64/hp/common/sba_iommu.c +1
-1@@ -502,7 +502,7 @@ sba_search_bitmap(struct ioc *ioc, unsigned long bits_wanted, int use_hint)unsigned int bitshiftcnt;for (; res_ptr < res_end ; res_ptr++) {if (likely (*res_ptr != ~0UL )) { - bitshiftcnt =ffz (*res_ptr); + bitshiftcnt =__ffs (~(*res_ptr)); *res_ptr |= (1UL << bitshiftcnt); pide = ((unsigned long )res_ptr - (unsigned long )ioc->res_map); pide <<=3 ;/* convert to bit address */ arch/ia64/kernel/perfmon.c +1
-1@@ -6683,7 +6683,7 @@ pfm_init(void) pmu_conf->num_pmcs, pmu_conf->num_pmds, pmu_conf->num_counters, - ffz(pmu_conf->ovfl_val)); + __ffs(~(pmu_conf->ovfl_val)));/* sanity check */ if (pmu_conf->num_pmds >=PFM_NUM_PMD_REGS || pmu_conf->num_pmcs >=PFM_NUM_PMC_REGS ) {arch/ia64/kernel/smp.c +1
-1@@ -134,7 +134,7 @@ handle_IPI (int irq, void *dev_id) do { unsigned long which; - which = ffz(~ops); + which = __ffs(ops); ops &= ~(1 << which); switch (which) {arch/ia64/mm/init.c +1
-1@@ -333,7 +333,7 @@ ia64_mmu_init (void *my_cpu_data)# define vmlpt_bits (impl_va_bits - PAGE_SHIFT + pte_bits)# define POW2 (n) (1ULL << (n)) - impl_va_bits =ffz (~(local_cpu_data->unimpl_va_mask | (7UL <<61 ))); + impl_va_bits =__ffs (local_cpu_data->unimpl_va_mask | (7UL <<61 ));if (impl_va_bits <51 || impl_va_bits >61 )panic ("CPU has bogus IMPL_VA_MSB value of %lu!\n" , impl_va_bits -1 );arch/mips/kernel/irixelf.c +1
-1@@ -1207,7 +1207,7 @@ static int irix_core_dump(long signr, struct pt_regs *regs, struct file *file, u notes[1 ].type =NT_PRPSINFO ; notes[1 ].datasz =sizeof (psinfo); notes[1 ].data = &psinfo; - i = current->state ?ffz (~current->state) +1 :0 ; + i = current->state ?__ffs (current->state) +1 :0 ; psinfo.pr_state = i; psinfo.pr_sname = (i <0 || i >5 ) ?'.' :"RSDZTD" [i]; psinfo.pr_zomb = psinfo.pr_sname =='Z' ;arch/parisc/kernel/smp.c +1
-1@@ -168,7 +168,7 @@ ipi_interrupt(int irq, void *dev_id)break ;while (ops) { -unsigned long which =ffz (~ops); +unsigned long which =__ffs (ops); ops &= ~(1 << which);arch/sh/kernel/cpu/irq/imask.c +1
-1@@ -84,7 +84,7 @@ static void disable_imask_irq(unsigned int irq)static void enable_imask_irq (unsigned int irq) {set_bit (irq, &imask_mask); - interrupt_priority =IMASK_PRIORITY -ffz (imask_mask); + interrupt_priority =IMASK_PRIORITY -__ffs (~imask_mask);set_interrupt_registers (interrupt_priority); }block/blk-barrier.c +1
-1@@ -57,7 +57,7 @@ inline unsigned blk_ordered_cur_seq(struct request_queue *q) {if (!q->ordseq)return 0 ; -return 1 <<ffz (q->ordseq); +return 1 <<__ffs (~(q->ordseq)); }unsigned blk_ordered_req_seq (struct request *rq)crypto/lrw.c +1
-1@@ -115,7 +115,7 @@ static inline int get_index128(be128 *block)if (!~val)continue ; -return x +ffz (val); +return x +__ffs (~val); }return x;drivers/ieee1394/pcilynx.c +1
-1@@ -141,7 +141,7 @@ static pcl_t alloc_pcl(struct ti_lynx *lynx)int i, j;spin_lock (&lynx->lock); -/* FIXME - use ffz() to make this readable */ +/* FIXME - use __ffs() to make this readable */ for (i =0 ; i < (LOCALRAM_SIZE /1024 ); i++) { m = lynx->pcl_bmap[i];for (j =0 ; j <8 ; j++) {drivers/input/keyboard/hilkbd.c +1
-1@@ -254,7 +254,7 @@ hil_keyb_init(void) kbid =-1 ;printk (KERN_WARNING "HIL: no keyboard present\n" ); }else { - kbid =ffz (~c); + kbid =__ffs (c);printk (KERN_INFO "HIL: keyboard found at id %d\n" , kbid); }drivers/md/bitmap.c +2
-2@@ -538,7 +538,7 @@ static int bitmap_read_sb(struct bitmap *bitmap) reason ="unrecognized superblock version" ; else if (chunksize < PAGE_SIZE) reason ="bitmap chunksize too small" ; - else if ((1 << ffz(~chunksize)) != chunksize) + else if ((1 << __ffs(chunksize)) != chunksize) reason = "bitmap chunksize not a power of 2"; else if (daemon_sleep < 1 || daemon_sleep > MAX_SCHEDULE_TIMEOUT / HZ) reason ="daemon sleep period out of range" ;@@ -1540,7 +1540,7 @@ int bitmap_create(mddev_t *mddev)if (err) goto error; - bitmap->chunkshift =ffz (~bitmap->chunksize); + bitmap->chunkshift =__ffs (bitmap->chunksize);/* now that chunksize and chunkshift are set, we can use these macros */ chunks = (blocks + CHUNK_BLOCK_RATIO(bitmap) - 1) /drivers/md/md.c +1
-1@@ -3316,7 +3316,7 @@ static int do_md_run(mddev_t * mddev)/* * chunk-size has to be a power of 2 and multiples of PAGE_SIZE */ -if ( (1 <<ffz (~chunk_size)) != chunk_size) { +if ( (1 <<__ffs (chunk_size)) != chunk_size) {printk (KERN_ERR "chunk_size of %d not valid\n" , chunk_size);return -EINVAL ; }drivers/md/raid0.c +1
-1@@ -407,7 +407,7 @@ static int raid0_make_request (struct request_queue *q, struct bio *bio) chunk_size = mddev->chunk_size >>10 ; chunk_sects = mddev->chunk_size >>9 ; - chunksize_bits =ffz (~chunk_size); + chunksize_bits =__ffs (chunk_size); block = bio->bi_sector >>1 ;drivers/md/raid10.c +1
-1@@ -2029,7 +2029,7 @@ static int run(mddev_t *mddev) conf->copies = nc*fc; conf->far_offset = fo; conf->chunk_mask = (sector_t)(mddev->chunk_size>>9 )-1 ; - conf->chunk_shift =ffz (~mddev->chunk_size) -9 ; + conf->chunk_shift =__ffs (mddev->chunk_size) -9 ; size = mddev->size >> (conf->chunk_shift-1 );sector_div (size, fc); size = size * conf->raid_disks;drivers/net/wan/cycx_x25.c +1
-1@@ -1207,7 +1207,7 @@ static int x25_place_call(struct cycx_device *card,return -EAGAIN ; } - key =ffz (card->u.x.connection_keys); + key =__ffs (~(card->u.x.connection_keys));set_bit (key, (void *)&card->u.x.connection_keys); ++key;dprintk (1 ,KERN_INFO "%s:x25_place_call:key=%d\n" , card->devname, key);drivers/scsi/NCR_Q720.c +1
-1@@ -66,7 +66,7 @@ NCR_Q720_intr(int irq, void *data)return IRQ_NONE ; -while ((siop =ffz (sir)) < p->siops) { +while ((siop =__ffs (~sir)) < p->siops) { sir |=1 <<siop;ncr53c8xx_intr (irq, p->hosts[siop]); }fs/adfs/map.c +2
-2@@ -101,7 +101,7 @@ lookup_zone(const struct adfs_discmap *dm, const unsigned int idlen, v =le32_to_cpu (_map[mapptr >>5 ]); } - mapptr +=1 +ffz (~v); + mapptr +=1 +__ffs (v); }if (frag == frag_id)@@ -179,7 +179,7 @@ scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm) v =le32_to_cpu (_map[mapptr >>5 ]); } - mapptr +=1 +ffz (~v); + mapptr +=1 +__ffs (v); } total += mapptr - start;fs/binfmt_elf.c +1
-1@@ -1383,7 +1383,7 @@ static int fill_psinfo(struct elf_prpsinfo *psinfo, struct task_struct *p, psinfo->pr_pgrp =task_pgrp_vnr (p); psinfo->pr_sid =task_session_vnr (p); - i = p->state ?ffz (~p->state) +1 :0 ; + i = p->state ?__ffs (p->state) +1 :0 ; psinfo->pr_state = i; psinfo->pr_sname = (i >5 ) ?'.' :"RSDTZW" [i]; psinfo->pr_zomb = psinfo->pr_sname =='Z' ;fs/binfmt_elf_fdpic.c +1
-1@@ -1396,7 +1396,7 @@ static int fill_psinfo(struct elf_prpsinfo *psinfo, struct task_struct *p, psinfo->pr_pgrp =task_pgrp_vnr (p); psinfo->pr_sid =task_session_vnr (p); - i = p->state ?ffz (~p->state) +1 :0 ; + i = p->state ?__ffs (p->state) +1 :0 ; psinfo->pr_state = i; psinfo->pr_sname = (i >5 ) ?'.' :"RSDTZW" [i]; psinfo->pr_zomb = psinfo->pr_sname =='Z' ;fs/ntfs/mft.c +1
-1@@ -1207,7 +1207,7 @@ static int ntfs_mft_bitmap_find_and_alloc_free_rec_nolock(ntfs_volume *vol, byte = buf + (bit >>3 );if (*byte ==0xff )continue ; - b =ffz ((unsigned long )*byte); + b =__ffs (~((unsigned long )*byte));if (b <8 && b >= (bit &7 )) { ll = data_pos + (bit & ~7ull ) + b;if (unlikely (ll > (1ll <<32 ))) {fs/udf/balloc.c +1
-1@@ -75,7 +75,7 @@ static inline int find_next_one_bit(void *addr, int size, int offset) found_first: tmp &= ~0UL >> (BITS_PER_LONG - size); found_middle: -return result +ffz (~tmp); +return result +__ffs (tmp); }#define find_first_one_bit (addr, size)\fs/xfs/xfs_bit.c +1
-1@@ -179,7 +179,7 @@ xfs_contig_bits(uint *map, uint size, uint start_bit) }return result - start_bit; found: -return result +ffz (tmp) - start_bit; +return result +__ffs (~tmp) - start_bit; }/* include/asm-m68knommu/bitops.h +2
-2@@ -289,9 +289,9 @@ found_first:* see above. But then we have to swab tmp below for ffz, so * we might as well do this here. */ -return result +ffz (__swab32 (tmp) | (~0UL << size)); +return result +__ffs (~(__swab32 (tmp) | (~0UL << size))); found_middle: -return result +ffz (__swab32 (tmp)); +return result +__ffs (~(__swab32 (tmp))); }#define ext2_find_next_bit (addr, size, off) \include/linux/inetdevice.h +1
-1@@ -217,7 +217,7 @@ static __inline__ int inet_mask_len(__be32 mask)__u32 hmask =ntohl (mask);if (!hmask)return 0 ; -return 32 -ffz (~hmask); +return 32 -__ffs (hmask); }include/linux/signal.h +1
-1@@ -64,7 +64,7 @@ static inline int sigismember(sigset_t *set, int _sig)static inline int sigfindinword (unsigned long word) { -return ffz (~word); +return __ffs (word); }#endif /* __HAVE_ARCH_SIG_BITOPS */ kernel/signal.c +3
-3@@ -142,7 +142,7 @@ int next_signal(struct sigpending *pending, sigset_t *mask)default :for (i =0 ; i < _NSIG_WORDS; ++i, ++s, ++m)if ((x = *s &~ *m) !=0 ) { - sig =ffz (~x) + i*_NSIG_BPW +1 ; + sig =__ffs (x) + i*_NSIG_BPW +1 ;break ; }break ;@@ -153,11 +153,11 @@ int next_signal(struct sigpending *pending, sigset_t *mask) sig = _NSIG_BPW +1 ; else break; - sig +=ffz (~x); + sig +=__ffs (x);break ;case 1 :if ((x = *s &~ *m) !=0 ) - sig =ffz (~x) +1 ; + sig =__ffs (x) +1 ;break ; }lib/find_next_bit.c +3
-3@@ -103,7 +103,7 @@ found_first:if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle: -return result +ffz (tmp); +return result +__ffs (~tmp); }EXPORT_SYMBOL (find_next_zero_bit);@@ -170,10 +170,10 @@ found_first:if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. Skip ffz */ found_middle: -return result +ffz (tmp); +return result +__ffs (~tmp); found_middle_swap: -return result +ffz (ext2_swab (tmp)); +return result +__ffs (~(ext2_swab (tmp))); }EXPORT_SYMBOL (generic_find_next_zero_le_bit);mm/page_alloc.c +1
-1@@ -2447,7 +2447,7 @@ static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)*/ static inline unsigned long wait_table_bits (unsigned long size) { -return ffz (~size); +return __ffs (size); }#define LONG_ALIGN (x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))net/sched/sch_cbq.c +2
-2@@ -637,7 +637,7 @@ static enum hrtimer_restart cbq_undelay(struct hrtimer *timer) q->pmask =0 ;while (pmask) { -int prio =ffz (~pmask); +int prio =__ffs (pmask);psched_tdiff_t tmp; pmask &= ~(1 <<prio);@@ -961,7 +961,7 @@ cbq_dequeue_1(struct Qdisc *sch) activemask = q->activemask&0xFF ;while (activemask) { -int prio =ffz (~activemask); +int prio =__ffs (activemask); activemask &= ~(1 <<prio); skb =cbq_dequeue_prio (sch, prio);if (skb)net/sched/sch_htb.c +5
-5@@ -343,7 +343,7 @@ static inline void htb_add_class_to_row(struct htb_sched *q, { q->row_mask[cl->level] |= mask;while (mask) { -int prio =ffz (~mask); +int prio =__ffs (mask); mask &= ~(1 << prio);htb_add_to_id_tree (q->row[cl->level] + prio, cl, prio); }@@ -373,7 +373,7 @@ static inline void htb_remove_class_from_row(struct htb_sched *q,int m =0 ;while (mask) { -int prio =ffz (~mask); +int prio =__ffs (mask); mask &= ~(1 << prio);if (q->ptr[cl->level][prio] == cl->node + prio)@@ -401,7 +401,7 @@ static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)while (cl->cmode ==HTB_MAY_BORROW && p && mask) { m = mask;while (m) { -int prio =ffz (~m); +int prio =__ffs (m); m &= ~(1 << prio);if (p->un.inner.feed[prio].rb_node)@@ -436,7 +436,7 @@ static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl) m = mask; mask =0 ;while (m) { -int prio =ffz (~m); +int prio =__ffs (m); m &= ~(1 << prio);if (p->un.inner.ptr[prio] == cl->node + prio) {@@ -925,7 +925,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch) m = ~q->row_mask[level];while (m != (int )(-1 )) { -int prio =ffz (m); +int prio =__ffs (~m); m |=1 << prio; skb =htb_dequeue_tree (q, prio, level);if (likely (skb !=NULL )) {sound/core/oss/mixer_oss.c +1
-2@@ -217,7 +217,7 @@ static int snd_mixer_oss_set_recsrc(struct snd_mixer_oss_file *fmixer, int recsrif (mixer->get_recsrc && mixer->put_recsrc) {/* exclusive input */ if (recsrc & ~mixer->oss_recsrc) recsrc &= ~mixer->oss_recsrc; - mixer->put_recsrc (fmixer,ffz (~recsrc)); + mixer->put_recsrc (fmixer,__ffs (recsrc)); mixer->get_recsrc (fmixer, &result); result =1 << result; } --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 42 lines · Benny Halevy
Quoted 32 lines · Alexander van Heukelum
Quoted 31 lines · Benny Halevy
Quoted 5 lines · Alexander van Heukelum
This series of patches:
[1/3] adds
__fls.hto asm-generic
[2/3] modifiesasm-*/bitops.hfor 64-bit archs to implement__fls[3/3] modifiesasm-generic/fls64.hto make use of__flsI strongly support this.
I wish we'd also have a consistent naming convention for all the bitops functions so it will be clearer what data type the function is working on and is the result 0 or 1 based.
It seems like what we currently have is:
name type first bit#
---- ---- ----------
ffs int 1
fls int 1__ffsulong 0__flsulong 0 # in your proposal
ffz ulong 0
fls64__u641so it seems like
- ffz is misnamed and is rather confusing.
Apprently is should be renamed to__ffz.- (new) ffz(x) can be defined to ffs(~(x))
- It'd be nice to have ffs64, and maybe ffz64.
Quoted 7 lines
Quoted 1 line
Benny
I think every programmer who thinks in terms of bits realises that ffz(x) ==
__ffs(~x)and ffz(~x) ==__ffs(x)etc... so I would rather get rid of ffz entirely by converting all uses to__ffs. Patch (against current linus) below. After that all implementations of ffz could be removed.
Quoted 3 lines
Yeah, very few architectures have an optimized version of ffz that will perform noticeably better than
__ffs(~x). (e.g. h8300, sh)
Yeah, and these implementations seem to be based on a loop over all bits in the word. I don't think adding one extra not-operation to convert ffz to __ffs will hurt much ;).
Quoted 12 lines
Quoted 11 lines
ffs64 would be a good addition to complete the set of functions, but that would be the same as glibc's (and gcc-builtin) ffsll.
Looking into that... the relevant gcc builtins are
__builtin_ffs(find first set bit),__builtin_clz(count leading zeroes),__builtin_ctz(count trailing zeroes),__builtin_popcount, maybe__builtin_parityand their -l and -ll variants. Maybe the kernel should be changed to use those names instead of the current ones? ffs would stay as it is.__ffswould become ctz,__flswould become something like 31-clz, and hweight would become popcount.
Quoted 4 lines
Interesting idea. ctz much better than
__ffswith regards to the return value's first bit number, but unless you expose clz and convert the code how do you get rid of the__flsvs. fls confusion?
Exposing clz/ctz on all architectures will be the harder part. Changing all current uses of ffs/fls (and __fls) will take some time. Mostly because converting code using fls to use clz instead needs to be done a bit carefully, because fls(0) has defined behaviour, while clz(0) is undefined.
Quoted 1 line
(BTW for
__fls, I'd useBITS_PER_LONG- 1, not 31 :)
:)
Quoted 3 lines
I think that adopting libc's convention might make more sense, i.e., define ffs, ffsl, ffsll, and fls, flsl, flsll, and have *all* be 1-based.
I agree that it makes sense for fls. For clz (and ctz) I would choose clz(unsigned long), clz32(u32), and clz64(u64).
Greetings,
Alexander
Quoted 1 line
Benny
Signature · 5 lines
Alexander van Heukelum [email protected] -- http://www.fastmail.fm - Choose from over 50 domains or use your own