lib/find_bit: fast path for small bitmaps
Subsystems (9)
Yury Norov
maintainerv2 cover lib/find_bit: fast path for small bitmaps
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.h we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.
find_*_bit() API lacks this functionality; despite users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG. In the very best case, the compiler may replace a find_*_bit() call for such a bitmap with a single ffs or ffz instruction.
Tools is synchronized with new implementation where needed.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: - employ GENMASK() for bitmaps;
- unify find_bit inliners in;
- address comments to v1;
Yury Norov (8):
tools: disable -Wno-type-limits
tools: bitmap: sync function declarations with linux kernel
arch: rearrange headers inclusion order in asm/bitops for m68k and sh
lib: introduce BITS_{FIRST,LAST} macro
bitsperlong.h: introduce SMALL_CONST() macro
lib: inline _find_next_bit() wrappers
lib: add fast path for find_next_*_bit()
lib: add fast path for find_first_*_bit() and find_last_bit()
arch/m68k/include/asm/bitops.h | 4 +- arch/sh/include/asm/bitops.h | 3 +- include/asm-generic/bitops/find.h | 108 +++++++++++++++++++++--- include/asm-generic/bitops/le.h | 38 ++++++++- include/asm-generic/bitsperlong.h | 2 + include/linux/bitmap.h | 60 ++++++------- include/linux/bitops.h | 12 --- include/linux/bits.h | 6 ++ include/linux/cpumask.h | 8 +- include/linux/netdev_features.h | 2 +- include/linux/nodemask.h | 2 +- lib/bitmap.c | 26 +++--- lib/find_bit.c | 72 +++------------- lib/genalloc.c | 8 +- tools/include/asm-generic/bitops/find.h | 85 +++++++++++++++++-- tools/include/asm-generic/bitsperlong.h | 2 + tools/include/linux/bitmap.h | 47 ++++------- tools/include/linux/bits.h | 6 ++ tools/lib/bitmap.c | 10 +-- tools/lib/find_bit.c | 56 +++++------- tools/scripts/Makefile.include | 1 + tools/testing/radix-tree/bitmap.c | 4 +- 22 files changed, 337 insertions(+), 225 deletions(-)
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH 1/8 tools: disable -Wno-type-limits
GENMASK(h, l) may be passed with unsigned types. In such case, this warning is generated for example in case GENMASK(h, 0)
--- tools/scripts/Makefile.include | 1 + 1 file changed, 1 insertion(+)
tools/scripts/Makefile.include +1 -0
@@ -38,6 +38,7 @@ EXTRA_WARNINGS += -Wswitch-enum EXTRA_WARNINGS += -Wundef EXTRA_WARNINGS += -Wwrite-strings EXTRA_WARNINGS += -Wformat +EXTRA_WARNINGS += -Wno-type-limits CC_NO_CLANG := $(shell $(CC) -dM -E -x c /dev/null | grep -Fq "__clang__"; echo $$?)
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH 2/8 tools: bitmap: sync function declarations with linux kernel
In reply to Yury NorovSome functions in tools/include/linux/bitmap.h declare nbits as int. In the kernel nbits is declared as unsigned int.
--- tools/include/linux/bitmap.h | 8 ++++---- tools/lib/bitmap.c | 4 ++-- 2 files changed, 6 insertions(+), 6 deletions(-)
tools/include/linux/bitmap.h +4 -4
@@ -30,7 +30,7 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len);#define small_const_nbits (nbits) \ (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG) -static inline void bitmap_zero (unsigned long *dst,int nbits) +static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) {if (small_const_nbits (nbits)) *dst =0UL ;
@@ -66,7 +66,7 @@ static inline int bitmap_full(const unsigned long *src, unsigned int nbits)return find_first_zero_bit (src, nbits) == nbits; } -static inline int bitmap_weight (const unsigned long *src,int nbits) +static inline int bitmap_weight (const unsigned long *src,unsigned int nbits) {if (small_const_nbits (nbits))return hweight_long (*src &BITMAP_LAST_WORD_MASK (nbits));
@@ -74,7 +74,7 @@ static inline int bitmap_weight(const unsigned long *src, int nbits) }static inline void bitmap_or (unsigned long *dst,const unsigned long *src1, -const unsigned long *src2,int nbits) +const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits)) *dst = *src1 | *src2;
@@ -141,7 +141,7 @@ static inline void bitmap_free(unsigned long *bitmap)* @buf: buffer to store output * @size: size of @buf */ -size_t bitmap_scnprintf (unsigned long *bitmap,int nbits, +size_t bitmap_scnprintf (unsigned long *bitmap,unsigned int nbits,char *buf,size_t size);/**
tools/lib/bitmap.c +2 -2
@@ -28,11 +28,11 @@ void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, dst[k] = bitmap1[k] | bitmap2[k]; } -size_t bitmap_scnprintf (unsigned long *bitmap,int nbits, +size_t bitmap_scnprintf (unsigned long *bitmap,unsigned int nbits,char *buf,size_t size) {/* current bit is 'cur', most recently seen range is [rbot, rtop] */ -int cur, rbot, rtop; +unsigned int cur, rbot, rtop;bool first = true;size_t ret =0 ;
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH 3/8 arch: rearrange headers inclusion order in asm/bitops for m68k and sh
In reply to Yury Norovm68k and sh include bitmap/find.h prior to ffs/fls headers. New fast-path implementation in find.h requires ffs/fls. Reordering the headers inclusion sequence helps to prevent compile-time implicit-function-declaration error.
--- arch/m68k/include/asm/bitops.h | 4 ++-- arch/sh/include/asm/bitops.h | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)
arch/m68k/include/asm/bitops.h +2 -2
@@ -440,8 +440,6 @@ static inline unsigned long ffz(unsigned long word)#endif -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__#if defined(CONFIG_CPU_HAS_NO_BITFIELDS )
@@ -531,4 +529,6 @@ static inline int __fls(int x)#include <asm-generic/bitops/hweight.h> #endif /* __KERNEL__ */ +#include <asm-generic/bitops/find.h> +#endif /* _M68K_BITOPS_H */
arch/sh/include/asm/bitops.h +2 -1
@@ -58,7 +58,6 @@ static inline unsigned long __ffs(unsigned long word)return result; } -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/ffs.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/lock.h>
@@ -69,4 +68,6 @@ static inline unsigned long __ffs(unsigned long word)#include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> +#include <asm-generic/bitops/find.h> +#endif /* __ASM_SH_BITOPS_H */
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH 4/8 lib: introduce BITS_{FIRST,LAST} macro
In reply to Yury NorovBITMAP_{LAST,FIRST}_WORD_MASK() in linux/bitmap.h duplicates the functionality of GENMASK(). The scope of there macros is wider than just bitmap. This patch defines 4 new macros: BITS_FIRST(), BITS_LAST(), BITS_FIRST_MASK() and BITS_LAST_MASK() in linux/bits.h on top of GENMASK() and replaces BITMAP_{LAST,FIRST}_WORD_MASK() to avoid duplication and increases scope of the macros.
--- include/linux/bitmap.h | 27 ++++++++++++--------------- include/linux/bits.h | 6 ++++++ include/linux/cpumask.h | 8 ++++---- include/linux/netdev_features.h | 2 +- include/linux/nodemask.h | 2 +- lib/bitmap.c | 26 +++++++++++++------------- lib/find_bit.c | 4 ++-- lib/genalloc.c | 8 ++++---- tools/include/linux/bitmap.h | 20 ++++++-------------- tools/include/linux/bits.h | 6 ++++++ tools/lib/bitmap.c | 6 +++--- tools/lib/find_bit.c | 2 +- tools/testing/radix-tree/bitmap.c | 4 ++-- 13 files changed, 61 insertions(+), 60 deletions(-)
include/linux/bitmap.h +12 -15
@@ -219,9 +219,6 @@ extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned intextern int bitmap_print_to_pagebuf (bool list,char *buf,const unsigned long *maskp,int nmaskbits); -#define BITMAP_FIRST_WORD_MASK (start) (~0UL << ((start) & (BITS_PER_LONG - 1))) -#define BITMAP_LAST_WORD_MASK (nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) -/* * The static inlines below do not handle constant nbits==0 correctly, * so make such users (should any ever turn up) call the out-of-line
@@ -257,7 +254,7 @@ static inline void bitmap_copy_clear_tail(unsigned long *dst, {bitmap_copy (dst, src, nbits);if (nbits %BITS_PER_LONG ) - dst[nbits /BITS_PER_LONG ] &=BITMAP_LAST_WORD_MASK (nbits); + dst[nbits /BITS_PER_LONG ] &=BITS_FIRST_MASK (nbits -1 ); }/*
@@ -282,7 +279,7 @@ static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; + return (*dst = *src1 & *src2 & BITS_FIRST(nbits - 1)) != 0;return __bitmap_and (dst, src1, src2, nbits); }
@@ -308,7 +305,7 @@ static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; + return (*dst = *src1 & ~(*src2) & BITS_FIRST(nbits - 1)) != 0;return __bitmap_andnot (dst, src1, src2, nbits); }
@@ -332,7 +329,7 @@ static inline int bitmap_equal(const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); + return !((*src1 ^ *src2) & BITS_FIRST(nbits - 1));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT ))return !memcmp (src1, src2, nbits /8 );
@@ -356,14 +353,14 @@ static inline bool bitmap_or_equal(const unsigned long *src1,if (!small_const_nbits (nbits))return __bitmap_or_equal (src1, src2, src3, nbits); -return !(((*src1 | *src2) ^ *src3) &BITMAP_LAST_WORD_MASK (nbits)); +return !(((*src1 | *src2) ^ *src3) &BITS_FIRST (nbits -1 )); }static inline int bitmap_intersects (const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits)) -return ((*src1 & *src2) &BITMAP_LAST_WORD_MASK (nbits)) !=0 ; +return ((*src1 & *src2) &BITS_FIRST (nbits -1 )) !=0 ;else return __bitmap_intersects (src1, src2, nbits); }
@@ -372,7 +369,7 @@ static inline int bitmap_subset(const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits)); + return !((*src1 & ~(*src2)) & BITS_FIRST(nbits - 1)); else return __bitmap_subset(src1, src2, nbits); }
@@ -380,7 +377,7 @@ static inline int bitmap_subset(const unsigned long *src1,static inline bool bitmap_empty (const unsigned long *src,unsigned nbits) {if (small_const_nbits (nbits)) -return ! (*src &BITMAP_LAST_WORD_MASK (nbits)); +return !(*src &BITS_FIRST (nbits -1 ));return find_first_bit (src, nbits) == nbits; }
@@ -388,7 +385,7 @@ static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)static inline bool bitmap_full (const unsigned long *src,unsigned int nbits) {if (small_const_nbits (nbits)) -return ! (~(*src) &BITMAP_LAST_WORD_MASK (nbits)); +return !(~(*src) &BITS_FIRST (nbits -1 ));return find_first_zero_bit (src, nbits) == nbits; }
@@ -396,7 +393,7 @@ static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits) {if (small_const_nbits (nbits)) -return hweight_long (*src &BITMAP_LAST_WORD_MASK (nbits)); +return hweight_long (*src &BITS_FIRST (nbits -1 ));return __bitmap_weight (src, nbits); }
@@ -432,7 +429,7 @@ static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *s unsigned int shift, unsigned int nbits) { if (small_const_nbits(nbits)) - *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift; + *dst = (*src & BITS_FIRST(nbits - 1)) >> shift; else__bitmap_shift_right (dst ,src ,shift ,nbits ); }
@@ -441,7 +438,7 @@ static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *sr unsigned int shift, unsigned int nbits) { if (small_const_nbits(nbits)) - *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits); + *dst = (*src << shift) & BITS_FIRST(nbits - 1); else__bitmap_shift_left (dst ,src ,shift ,nbits ); }
include/linux/bits.h +6 -0
@@ -37,6 +37,12 @@#define GENMASK (h, l) \ (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l)) +#define BITS_FIRST (nr) GENMASK((nr), 0) +#define BITS_LAST (nr) GENMASK(BITS_PER_LONG - 1, (nr)) + +#define BITS_FIRST_MASK (nr) BITS_FIRST((nr) % BITS_PER_LONG) +#define BITS_LAST_MASK (nr) BITS_LAST((nr) % BITS_PER_LONG) +#define __GENMASK_ULL (h, l) \ (((~ULL(0)) - (ULL(1) << (l)) + 1) & \ (~ULL(0) >> (BITS_PER_LONG_LONG - 1 - (h))))
include/linux/cpumask.h +4 -4
@@ -899,7 +899,7 @@ static inline const struct cpumask *get_cpu_mask(unsigned int cpu)#if NR_CPUS <=BITS_PER_LONG #define CPU_BITS_ALL \ { \ - [BITS_TO_LONGS(NR_CPUS)-1] = BITMAP_LAST_WORD_MASK(NR_CPUS) \ + [BITS_TO_LONGS(NR_CPUS)-1] = BITS_FIRST_MASK(NR_CPUS - 1) \ }#else /* NR_CPUS > BITS_PER_LONG */
@@ -907,7 +907,7 @@ static inline const struct cpumask *get_cpu_mask(unsigned int cpu)#define CPU_BITS_ALL \ { \ [0 ... BITS_TO_LONGS(NR_CPUS)-2] = ~0UL, \ - [BITS_TO_LONGS(NR_CPUS)-1] = BITMAP_LAST_WORD_MASK(NR_CPUS) \ + [BITS_TO_LONGS(NR_CPUS)-1] = BITS_FIRST_MASK(NR_CPUS - 1) \ }#endif /* NR_CPUS > BITS_PER_LONG */
@@ -931,13 +931,13 @@ cpumap_print_to_pagebuf(bool list, char *buf, const struct cpumask *mask)#if NR_CPUS <=BITS_PER_LONG #define CPU_MASK_ALL \ (cpumask_t) { { \ - [BITS_TO_LONGS(NR_CPUS)-1] = BITMAP_LAST_WORD_MASK(NR_CPUS) \ + [BITS_TO_LONGS(NR_CPUS)-1] = BITS_FIRST_MASK(NR_CPUS - 1) \ } }#else #define CPU_MASK_ALL \ (cpumask_t) { { \ [0 ... BITS_TO_LONGS(NR_CPUS)-2] = ~0UL, \ - [BITS_TO_LONGS(NR_CPUS)-1] = BITMAP_LAST_WORD_MASK(NR_CPUS) \ + [BITS_TO_LONGS(NR_CPUS)-1] = BITS_FIRST_MASK(NR_CPUS - 1) \ } }#endif /* NR_CPUS > BITS_PER_LONG */
include/linux/netdev_features.h +1 -1
@@ -162,7 +162,7 @@ enum {*/ static inline int find_next_netdev_feature (u64 feature,unsigned long start) { -/* like BITMAP_LAST_WORD_MASK() for u64 +/* like BITS_FIRST_MASK() for u64 * this sets the most significant 64 - start to 0. */ feature &= ~0ULL >> (-start & ((sizeof (feature) *8 ) -1 ));
include/linux/nodemask.h +1 -1
@@ -302,7 +302,7 @@ static inline int __first_unset_node(const nodemask_t *maskp) find_first_zero_bit(maskp->bits, MAX_NUMNODES)); } -#define NODE_MASK_LAST_WORD BITMAP_LAST_WORD_MASK(MAX_NUMNODES) +#define NODE_MASK_LAST_WORD BITS_FIRST_MASK(MAX_NUMNODES - 1)#if MAX_NUMNODES <=BITS_PER_LONG
lib/bitmap.c +13 -13
@@ -52,7 +52,7 @@ int __bitmap_equal(const unsigned long *bitmap1,return 0 ;if (bits %BITS_PER_LONG ) -if ((bitmap1[k] ^ bitmap2[k]) &BITMAP_LAST_WORD_MASK (bits)) +if ((bitmap1[k] ^ bitmap2[k]) &BITS_FIRST_MASK (bits -1 ))return 0 ;return 1 ;
@@ -76,7 +76,7 @@ bool __bitmap_or_equal(const unsigned long *bitmap1,return true; tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k]; -return (tmp &BITMAP_LAST_WORD_MASK (bits)) ==0 ; +return (tmp &BITS_FIRST_MASK (bits -1 )) ==0 ; }void __bitmap_complement (unsigned long *dst,const unsigned long *src,unsigned int bits)
@@ -103,7 +103,7 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, {unsigned k, lim =BITS_TO_LONGS (nbits);unsigned off = shift/BITS_PER_LONG , rem = shift %BITS_PER_LONG ; -unsigned long mask =BITMAP_LAST_WORD_MASK (nbits); +unsigned long mask =BITS_FIRST_MASK (nbits -1 );for (k =0 ; off + k < lim; ++k) {unsigned long upper, lower;
@@ -246,7 +246,7 @@ int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, result |= (dst[k] = bitmap1[k] & bitmap2[k]);if (bits %BITS_PER_LONG ) result |= (dst[k] = bitmap1[k] & bitmap2[k] & -BITMAP_LAST_WORD_MASK (bits)); +BITS_FIRST_MASK (bits -1 ));return result !=0 ; }EXPORT_SYMBOL (__bitmap_and);
@@ -284,7 +284,7 @@ int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);if (bits %BITS_PER_LONG ) result |= (dst[k] = bitmap1[k] & ~bitmap2[k] & -BITMAP_LAST_WORD_MASK (bits)); +BITS_FIRST_MASK (bits -1 ));return result !=0 ; }EXPORT_SYMBOL (__bitmap_andnot);
@@ -310,7 +310,7 @@ int __bitmap_intersects(const unsigned long *bitmap1,return 1 ;if (bits %BITS_PER_LONG ) -if ((bitmap1[k] & bitmap2[k]) &BITMAP_LAST_WORD_MASK (bits)) +if ((bitmap1[k] & bitmap2[k]) &BITS_FIRST_MASK (bits -1 ))return 1 ;return 0 ; }
@@ -325,7 +325,7 @@ int __bitmap_subset(const unsigned long *bitmap1,return 0 ;if (bits %BITS_PER_LONG ) -if ((bitmap1[k] & ~bitmap2[k]) &BITMAP_LAST_WORD_MASK (bits)) +if ((bitmap1[k] & ~bitmap2[k]) &BITS_FIRST_MASK (bits -1 ))return 0 ;return 1 ; }
@@ -340,7 +340,7 @@ int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) w +=hweight_long (bitmap[k]);if (bits %BITS_PER_LONG ) - w +=hweight_long (bitmap[k] &BITMAP_LAST_WORD_MASK (bits)); + w +=hweight_long (bitmap[k] &BITS_FIRST_MASK (bits -1 ));return w; }
@@ -351,7 +351,7 @@ void __bitmap_set(unsigned long *map, unsigned int start, int len)unsigned long *p = map +BIT_WORD (start);const unsigned int size = start + len;int bits_to_set =BITS_PER_LONG - (start %BITS_PER_LONG ); -unsigned long mask_to_set =BITMAP_FIRST_WORD_MASK (start); +unsigned long mask_to_set =BITS_LAST_MASK (start);while (len - bits_to_set >=0 ) { *p |= mask_to_set;
@@ -361,7 +361,7 @@ void __bitmap_set(unsigned long *map, unsigned int start, int len) p++; }if (len) { - mask_to_set &=BITMAP_LAST_WORD_MASK (size); + mask_to_set &=BITS_FIRST_MASK (size -1 ); *p |= mask_to_set; } }
@@ -372,7 +372,7 @@ void __bitmap_clear(unsigned long *map, unsigned int start, int len)unsigned long *p = map +BIT_WORD (start);const unsigned int size = start + len;int bits_to_clear =BITS_PER_LONG - (start %BITS_PER_LONG ); -unsigned long mask_to_clear =BITMAP_FIRST_WORD_MASK (start); +unsigned long mask_to_clear =BITS_LAST_MASK (start);while (len - bits_to_clear >=0 ) { *p &= ~mask_to_clear;
@@ -382,7 +382,7 @@ void __bitmap_clear(unsigned long *map, unsigned int start, int len) p++; }if (len) { - mask_to_clear &=BITMAP_LAST_WORD_MASK (size); + mask_to_clear &=BITS_FIRST_MASK (size -1 ); *p &= ~mask_to_clear; } }
@@ -1282,7 +1282,7 @@ void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits/* Clear tail bits in last word beyond nbits. */ if (nbits %BITS_PER_LONG ) - bitmap[(halfwords -1 ) /2 ] &=BITMAP_LAST_WORD_MASK (nbits); + bitmap[(halfwords -1 ) /2 ] &=BITS_FIRST_MASK (nbits -1 ); }EXPORT_SYMBOL (bitmap_from_arr32);
lib/find_bit.c +2 -2
@@ -44,7 +44,7 @@ static unsigned long _find_next_bit(const unsigned long *addr1, tmp ^= invert;/* Handle 1st word. */ - mask =BITMAP_FIRST_WORD_MASK (start); + mask =BITS_LAST_MASK (start);if (le) mask =swab (mask);
@@ -141,7 +141,7 @@ EXPORT_SYMBOL(find_first_zero_bit);unsigned long find_last_bit (const unsigned long *addr,unsigned long size) {if (size) { -unsigned long val =BITMAP_LAST_WORD_MASK (size); +unsigned long val =BITS_FIRST_MASK (size -1 );unsigned long idx = (size-1 ) /BITS_PER_LONG ; do {
lib/genalloc.c +4 -4
@@ -87,7 +87,7 @@ bitmap_set_ll(unsigned long *map, unsigned long start, unsigned long nr)unsigned long *p = map +BIT_WORD (start);const unsigned long size = start + nr;int bits_to_set =BITS_PER_LONG - (start %BITS_PER_LONG ); -unsigned long mask_to_set =BITMAP_FIRST_WORD_MASK (start); +unsigned long mask_to_set =BITS_LAST_MASK (start);while (nr >= bits_to_set) {if (set_bits_ll (p, mask_to_set))
@@ -98,7 +98,7 @@ bitmap_set_ll(unsigned long *map, unsigned long start, unsigned long nr) p++; }if (nr) { - mask_to_set &=BITMAP_LAST_WORD_MASK (size); + mask_to_set &=BITS_FIRST_MASK (size -1 );if (set_bits_ll (p, mask_to_set))return nr; }
@@ -123,7 +123,7 @@ bitmap_clear_ll(unsigned long *map, unsigned long start, unsigned long nr)unsigned long *p = map +BIT_WORD (start);const unsigned long size = start + nr;int bits_to_clear =BITS_PER_LONG - (start %BITS_PER_LONG ); -unsigned long mask_to_clear =BITMAP_FIRST_WORD_MASK (start); +unsigned long mask_to_clear =BITS_LAST_MASK (start);while (nr >= bits_to_clear) {if (clear_bits_ll (p, mask_to_clear))
@@ -134,7 +134,7 @@ bitmap_clear_ll(unsigned long *map, unsigned long start, unsigned long nr) p++; }if (nr) { - mask_to_clear &=BITMAP_LAST_WORD_MASK (size); + mask_to_clear &=BITS_FIRST_MASK (size -1 );if (clear_bits_ll (p, mask_to_clear))return nr; }
tools/include/linux/bitmap.h +6 -14
@@ -19,14 +19,6 @@ int __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits);void bitmap_clear (unsigned long *map,unsigned int start,int len); -#define BITMAP_FIRST_WORD_MASK (start) (~0UL << ((start) & (BITS_PER_LONG - 1))) - -#define BITMAP_LAST_WORD_MASK (nbits) \ -( \ - ((nbits) % BITS_PER_LONG) ? \ - (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ -) -#define small_const_nbits (nbits) \ (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
@@ -47,13 +39,13 @@ static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)unsigned int len = (nlongs -1 ) *sizeof (unsigned long );memset (dst,0xff , len); } - dst[nlongs -1 ] =BITMAP_LAST_WORD_MASK (nbits); + dst[nlongs -1 ] =BITS_FIRST (nbits -1 ); }static inline int bitmap_empty (const unsigned long *src,unsigned nbits) {if (small_const_nbits (nbits)) -return ! (*src &BITMAP_LAST_WORD_MASK (nbits)); +return !(*src &BITS_FIRST (nbits -1 ));return find_first_bit (src, nbits) == nbits; }
@@ -61,7 +53,7 @@ static inline int bitmap_empty(const unsigned long *src, unsigned nbits)static inline int bitmap_full (const unsigned long *src,unsigned int nbits) {if (small_const_nbits (nbits)) -return ! (~(*src) &BITMAP_LAST_WORD_MASK (nbits)); +return !(~(*src) &BITS_FIRST (nbits -1 ));return find_first_zero_bit (src, nbits) == nbits; }
@@ -69,7 +61,7 @@ static inline int bitmap_full(const unsigned long *src, unsigned int nbits)static inline int bitmap_weight (const unsigned long *src,unsigned int nbits) {if (small_const_nbits (nbits)) -return hweight_long (*src &BITMAP_LAST_WORD_MASK (nbits)); +return hweight_long (*src &BITS_FIRST (nbits -1 ));return __bitmap_weight (src, nbits); }
@@ -155,7 +147,7 @@ static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; + return (*dst = *src1 & *src2 & BITS_FIRST(nbits - 1)) != 0;return __bitmap_and (dst, src1, src2, nbits); }
@@ -171,7 +163,7 @@ static inline int bitmap_equal(const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) - return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); + return !((*src1 ^ *src2) & BITS_FIRST(nbits - 1));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT ))return !memcmp (src1, src2, nbits /8 );
tools/include/linux/bits.h +6 -0
@@ -37,6 +37,12 @@#define GENMASK (h, l) \ (GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l)) +#define BITS_FIRST (nr) GENMASK((nr), 0) +#define BITS_LAST (nr) GENMASK(BITS_PER_LONG - 1, (nr)) + +#define BITS_FIRST_MASK (nr) BITS_FIRST((nr) % BITS_PER_LONG) +#define BITS_LAST_MASK (nr) BITS_LAST((nr) % BITS_PER_LONG) +#define __GENMASK_ULL (h, l) \ (((~ULL(0)) - (ULL(1) << (l)) + 1) & \ (~ULL(0) >> (BITS_PER_LONG_LONG - 1 - (h))))
tools/lib/bitmap.c +3 -3
@@ -13,7 +13,7 @@ int __bitmap_weight(const unsigned long *bitmap, int bits) w +=hweight_long (bitmap[k]);if (bits %BITS_PER_LONG ) - w +=hweight_long (bitmap[k] &BITMAP_LAST_WORD_MASK (bits)); + w +=hweight_long (bitmap[k] &BITS_FIRST_MASK (bits -1 ));return w; }
@@ -68,7 +68,7 @@ int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, result |= (dst[k] = bitmap1[k] & bitmap2[k]);if (bits %BITS_PER_LONG ) result |= (dst[k] = bitmap1[k] & bitmap2[k] & -BITMAP_LAST_WORD_MASK (bits)); +BITS_FIRST_MASK (bits -1 ));return result !=0 ; }
@@ -81,7 +81,7 @@ int __bitmap_equal(const unsigned long *bitmap1,return 0 ;if (bits %BITS_PER_LONG ) -if ((bitmap1[k] ^ bitmap2[k]) &BITMAP_LAST_WORD_MASK (bits)) +if ((bitmap1[k] ^ bitmap2[k]) &BITS_FIRST_MASK (bits -1 ))return 0 ;return 1 ;
tools/lib/find_bit.c +1 -1
@@ -43,7 +43,7 @@ static inline unsigned long _find_next_bit(const unsigned long *addr1, tmp ^= invert;/* Handle 1st word. */ - tmp &=BITMAP_FIRST_WORD_MASK (start); + tmp &=BITS_LAST_MASK (start); start =round_down (start,BITS_PER_LONG );while (!tmp) {
tools/testing/radix-tree/bitmap.c +2 -2
@@ -7,7 +7,7 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len)unsigned long *p = map +BIT_WORD (start);const unsigned int size = start + len;int bits_to_clear =BITS_PER_LONG - (start %BITS_PER_LONG ); -unsigned long mask_to_clear =BITMAP_FIRST_WORD_MASK (start); +unsigned long mask_to_clear =BITS_LAST_MASK (start);while (len - bits_to_clear >=0 ) { *p &= ~mask_to_clear;
@@ -17,7 +17,7 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len) p++; }if (len) { - mask_to_clear &=BITMAP_LAST_WORD_MASK (size); + mask_to_clear &=BITS_FIRST_MASK (size -1 ); *p &= ~mask_to_clear; } }
Signature · 1 line
2.25.1
Re: [PATCH 4/8] lib: introduce BITS_{FIRST,LAST} macro
Quoted 6 lines · Yury Norov
BITMAP_{LAST,FIRST}_WORD_MASK() in
linux/bitmap.hduplicates the functionality ofGENMASK(). The scope of there macros is wider than just bitmap. This patch defines 4 new macros:BITS_FIRST(),BITS_LAST(),BITS_FIRST_MASK()andBITS_LAST_MASK()inlinux/bits.hon top ofGENMASK()and replaces BITMAP_{LAST,FIRST}_WORD_MASK() to avoid duplication and increases scope of the macros.
...
Quoted 8 lines
include/linux/bitmap.h | 27 ++++++++++++--------------- include/linux/bits.h | 6 ++++++ include/linux/cpumask.h | 8 ++++---- include/linux/netdev_features.h | 2 +- include/linux/nodemask.h | 2 +- lib/bitmap.c | 26 +++++++++++++------------- lib/find_bit.c | 4 ++-- lib/genalloc.c | 8 ++++----
Answering to your reply. I meant to split the below to a separate patch.
Quoted 5 lines
tools/include/linux/bitmap.h | 20 ++++++-------------- tools/include/linux/bits.h | 6 ++++++ tools/lib/bitmap.c | 6 +++--- tools/lib/find_bit.c | 2 +- tools/testing/radix-tree/bitmap.c | 4 ++--
...
include/linux/bits.h line 44
Quoted 5 lines
include/linux/bits.h +5
-0+#define BITS_FIRST (nr) GENMASK((nr), 0) +#define BITS_LAST (nr) GENMASK(BITS_PER_LONG - 1, (nr)) + +#define BITS_FIRST_MASK (nr) BITS_FIRST((nr) % BITS_PER_LONG) +#define BITS_LAST_MASK (nr) BITS_LAST((nr) % BITS_PER_LONG)
Any pointers to the difference in generated code for popular architectures (x86. x86_64, arm, aarch64, ppc, ppc64)?
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 5/8 bitsperlong.h: introduce SMALL_CONST() macro
In reply to Yury NorovMany algorithms become simpler if they are passed with relatively small input values. One example is bitmap operations when the whole bitmap fits into one word. To implement such simplifications, linux/bitmap.h declares small_const_nbits() macro.
Other subsystems may also benefit from optimizations of this sort, like find_bit API in the following patches. So it looks helpful to generalize the macro and extend it's visibility.
--- include/asm-generic/bitsperlong.h | 2 ++ include/linux/bitmap.h | 33 +++++++++++-------------- tools/include/asm-generic/bitsperlong.h | 2 ++ tools/include/linux/bitmap.h | 19 ++++++-------- 4 files changed, 27 insertions(+), 29 deletions(-)
include/asm-generic/bitsperlong.h +2 -0
@@ -23,4 +23,6 @@#define BITS_PER_LONG_LONG 64#endif +#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) +#endif /* __ASM_GENERIC_BITS_PER_LONG */
include/linux/bitmap.h +15 -18
@@ -224,9 +224,6 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,* so make such users (should any ever turn up) call the out-of-line * versions. */ -#define small_const_nbits (nbits) \ - (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0) -static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) {unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long );
@@ -278,7 +275,7 @@ extern void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,static inline int bitmap_and (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return (*dst = *src1 & *src2 &BITS_FIRST (nbits -1 )) !=0 ;return __bitmap_and (dst, src1, src2, nbits); }
@@ -286,7 +283,7 @@ static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,static inline void bitmap_or (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = *src1 | *src2;else __bitmap_or (dst, src1, src2, nbits);
@@ -295,7 +292,7 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,static inline void bitmap_xor (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = *src1 ^ *src2;else __bitmap_xor (dst, src1, src2, nbits);
@@ -304,7 +301,7 @@ static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,static inline int bitmap_andnot (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return (*dst = *src1 & ~(*src2) &BITS_FIRST (nbits -1 )) !=0 ;return __bitmap_andnot (dst, src1, src2, nbits); }
@@ -312,7 +309,7 @@ static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,static inline void bitmap_complement (unsigned long *dst,const unsigned long *src,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = ~(*src);else __bitmap_complement (dst, src, nbits);
@@ -328,7 +325,7 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *srstatic inline int bitmap_equal (const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !((*src1 ^ *src2) &BITS_FIRST (nbits -1 ));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT ))
@@ -350,7 +347,7 @@ static inline bool bitmap_or_equal(const unsigned long *src1, const unsigned long *src3, unsigned int nbits) { - if (!small_const_nbits(nbits)) + if (!SMALL_CONST(nbits - 1)) return __bitmap_or_equal(src1, src2, src3, nbits);return !(((*src1 | *src2) ^ *src3) &BITS_FIRST (nbits -1 ));
@@ -359,7 +356,7 @@ static inline bool bitmap_or_equal(const unsigned long *src1,static inline int bitmap_intersects (const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return ((*src1 & *src2) &BITS_FIRST (nbits -1 )) !=0 ;else return __bitmap_intersects (src1, src2, nbits);
@@ -368,7 +365,7 @@ static inline int bitmap_intersects(const unsigned long *src1,static inline int bitmap_subset (const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !((*src1 & ~(*src2)) &BITS_FIRST (nbits -1 ));else return __bitmap_subset (src1, src2, nbits);
@@ -376,7 +373,7 @@ static inline int bitmap_subset(const unsigned long *src1,static inline bool bitmap_empty (const unsigned long *src,unsigned nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !(*src &BITS_FIRST (nbits -1 ));return find_first_bit (src, nbits) == nbits;
@@ -384,7 +381,7 @@ static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)static inline bool bitmap_full (const unsigned long *src,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !(~(*src) &BITS_FIRST (nbits -1 ));return find_first_zero_bit (src, nbits) == nbits;
@@ -392,7 +389,7 @@ static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return hweight_long (*src &BITS_FIRST (nbits -1 ));return __bitmap_weight (src, nbits); }
@@ -428,7 +425,7 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,static inline void bitmap_shift_right (unsigned long *dst,const unsigned long *src,unsigned int shift,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = (*src &BITS_FIRST (nbits -1 )) >> shift;else __bitmap_shift_right (dst, src, shift, nbits);
@@ -437,7 +434,7 @@ static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *sstatic inline void bitmap_shift_left (unsigned long *dst,const unsigned long *src,unsigned int shift,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = (*src << shift) &BITS_FIRST (nbits -1 );else __bitmap_shift_left (dst, src, shift, nbits);
@@ -449,7 +446,7 @@ static inline void bitmap_replace(unsigned long *dst,const unsigned long *mask, unsigned int nbits) { - if (small_const_nbits(nbits)) + if (SMALL_CONST(nbits - 1)) *dst = (*old & ~(*mask)) | (*new & *mask); else__bitmap_replace (dst ,old ,new ,mask ,nbits );
tools/include/asm-generic/bitsperlong.h +2 -0
@@ -18,4 +18,6 @@#define BITS_PER_LONG_LONG 64#endif +#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) +#endif /* __ASM_GENERIC_BITS_PER_LONG */
tools/include/linux/bitmap.h +8 -11
@@ -19,12 +19,9 @@ int __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits);void bitmap_clear (unsigned long *map,unsigned int start,int len); -#define small_const_nbits (nbits) \ - (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG) -static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst =0UL ;else {int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long );
@@ -35,7 +32,7 @@ static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)static inline void bitmap_fill (unsigned long *dst,unsigned int nbits) {unsigned int nlongs =BITS_TO_LONGS (nbits); -if (!small_const_nbits (nbits)) { +if (!SMALL_CONST (nbits -1 )) {unsigned int len = (nlongs -1 ) *sizeof (unsigned long );memset (dst,0xff , len); }
@@ -44,7 +41,7 @@ static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)static inline int bitmap_empty (const unsigned long *src,unsigned nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !(*src &BITS_FIRST (nbits -1 ));return find_first_bit (src, nbits) == nbits;
@@ -52,7 +49,7 @@ static inline int bitmap_empty(const unsigned long *src, unsigned nbits)static inline int bitmap_full (const unsigned long *src,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !(~(*src) &BITS_FIRST (nbits -1 ));return find_first_zero_bit (src, nbits) == nbits;
@@ -60,7 +57,7 @@ static inline int bitmap_full(const unsigned long *src, unsigned int nbits)static inline int bitmap_weight (const unsigned long *src,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return hweight_long (*src &BITS_FIRST (nbits -1 ));return __bitmap_weight (src, nbits); }
@@ -68,7 +65,7 @@ static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)static inline void bitmap_or (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 )) *dst = *src1 | *src2;else __bitmap_or (dst, src1, src2, nbits);
@@ -146,7 +143,7 @@ size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,static inline int bitmap_and (unsigned long *dst,const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return (*dst = *src1 & *src2 &BITS_FIRST (nbits -1 )) !=0 ;return __bitmap_and (dst, src1, src2, nbits); }
@@ -162,7 +159,7 @@ static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,static inline int bitmap_equal (const unsigned long *src1,const unsigned long *src2,unsigned int nbits) { -if (small_const_nbits (nbits)) +if (SMALL_CONST (nbits -1 ))return !((*src1 ^ *src2) &BITS_FIRST (nbits -1 ));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT ))
Signature · 1 line
2.25.1
Re: [PATCH 5/8] bitsperlong.h: introduce SMALL_CONST() macro
Quoted 8 lines · Yury Norov
Many algorithms become simpler if they are passed with relatively small input values. One example is bitmap operations when the whole bitmap fits into one word. To implement such simplifications,
linux/bitmap.hdeclaressmall_const_nbits()macro.Other subsystems may also benefit from optimizations of this sort, like
find_bitAPI in the following patches. So it looks helpful to generalize the macro and extend it's visibility.
Hmm... Are we really good to allow 0 as a parameter to it? I remember we had a thread at some point where Rasmus explained why 0 is excluded.
...
tools/include/asm-generic/bitsperlong.h
Quoted 2 lines
tools/include/asm-generic/bitsperlong.h +0
-0
Tools part in a separate patch?
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 5/8] bitsperlong.h: introduce SMALL_CONST() macro
Quoted 7 lines · Andy Shevchenko
Quoted 5 lines · Yury Norov
Many algorithms become simpler if they are passed with relatively small input values. One example is bitmap operations when the whole bitmap fits into one word. To implement such simplifications,
linux/bitmap.hdeclaressmall_const_nbits()macro.
Quoted 6 lines
Quoted 3 lines
Other subsystems may also benefit from optimizations of this sort, like
find_bitAPI in the following patches. So it looks helpful to generalize the macro and extend it's visibility.Hmm... Are we really good to allow 0 as a parameter to it? I remember we had a thread at some point where Rasmus explained why 0 is excluded.
Now we pass (nbits - 1) instead of nbits, which is ULONG_MAX in case of nbits == 0
Quoted 10 lines
tools/include/asm-generic/bitsperlong.h
Quoted 2 lines
tools/include/asm-generic/bitsperlong.h +0
-0Tools part in a separate patch?
--
With Best Regards,
Andy Shevchenko
Yury Norov
maintainerPATCH 6/8 lib: inline _find_next_bit() wrappers
In reply to Yury Norovlib/find_bit.c declares five single-line wrappers for _find_next_bit(). We may turn those wrappers to inline functions. It eliminates unneeded function calls and opens room for compile-time optimizations.
--- include/asm-generic/bitops/find.h | 28 ++++++++++--- include/asm-generic/bitops/le.h | 17 ++++++-- lib/find_bit.c | 56 +------------------------ tools/include/asm-generic/bitops/find.h | 27 +++++++++--- tools/lib/find_bit.c | 52 ++++++++++------------- 5 files changed, 79 insertions(+), 101 deletions(-)
include/asm-generic/bitops/find.h +22 -6
@@ -2,6 +2,10 @@#ifndef _ASM_GENERIC_BITOPS_FIND_H_#define _ASM_GENERIC_BITOPS_FIND_H_ +extern unsigned long _find_next_bit (const unsigned long *addr1, +const unsigned long *addr2,unsigned long nbits, +unsigned long start,unsigned long invert,unsigned long le); +#ifndef find_next_bit/** * find_next_bit - find the next set bit in a memory region
@@ -12,8 +16,12 @@* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -extern unsigned long find_next_bit (const unsigned long *addr,unsigned long - size,unsigned long offset); +static inline +unsigned long find_next_bit (const unsigned long *addr,unsigned long size, +unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); +}#endif #ifndef find_next_and_bit
@@ -27,9 +35,13 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -extern unsigned long find_next_and_bit (const unsigned long *addr1, +static inline +unsigned long find_next_and_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size, -unsigned long offset); +unsigned long offset) +{ +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); +}#endif #ifndef find_next_zero_bit
@@ -42,8 +54,12 @@ extern unsigned long find_next_and_bit(const unsigned long *addr1,* Returns the bit number of the next zero bit * If no bits are zero, returns @size. */ -extern unsigned long find_next_zero_bit (const unsigned long *addr,unsigned -long size,unsigned long offset); +static inline +unsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size, +unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); +}#endif #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
include/asm-generic/bitops/le.h +13 -4
@@ -2,6 +2,7 @@#ifndef _ASM_GENERIC_BITOPS_LE_H_#define _ASM_GENERIC_BITOPS_LE_H_ +#include <asm-generic/bitops/find.h> #include <asm/types.h> #include <asm/byteorder.h>
@@ -32,13 +33,21 @@ static inline unsigned long find_first_zero_bit_le(const void *addr,#define BITOP_LE_SWIZZLE ((BITS_PER_LONG-1) & ~0x7)#ifndef find_next_zero_bit_le -extern unsigned long find_next_zero_bit_le (const void *addr, -unsigned long size,unsigned long offset); +static inline +unsigned long find_next_zero_bit_le (const void *addr,unsigned +long size,unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset, ~0UL ,1 ); +}#endif #ifndef find_next_bit_le -extern unsigned long find_next_bit_le (const void *addr, -unsigned long size,unsigned long offset); +static inline +unsigned long find_next_bit_le (const void *addr,unsigned +long size,unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset,0UL ,1 ); +}#endif #ifndef find_first_zero_bit_le
lib/find_bit.c +2 -54
74 lines not on this page · raw message
tools/include/asm-generic/bitops/find.h +21 -6
@@ -2,6 +2,10 @@#ifndef _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_#define _TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_ +extern unsigned long _find_next_bit (const unsigned long *addr1, +const unsigned long *addr2,unsigned long nbits, +unsigned long start,unsigned long invert,unsigned long le); +#ifndef find_next_bit/** * find_next_bit - find the next set bit in a memory region
@@ -12,8 +16,12 @@* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -extern unsigned long find_next_bit (const unsigned long *addr,unsigned long - size,unsigned long offset); +static inline +unsigned long find_next_bit (const unsigned long *addr,unsigned long size, +unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); +}#endif #ifndef find_next_and_bit
@@ -27,13 +35,16 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -extern unsigned long find_next_and_bit (const unsigned long *addr1, +static inline +unsigned long find_next_and_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size, -unsigned long offset); +unsigned long offset) +{ +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); +}#endif #ifndef find_next_zero_bit -/** * find_next_zero_bit - find the next cleared bit in a memory region * @addr: The address to base the search on
@@ -43,8 +54,12 @@ extern unsigned long find_next_and_bit(const unsigned long *addr1,* Returns the bit number of the next zero bit * If no bits are zero, returns @size. */ +static inline unsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size, -unsigned long offset); +unsigned long offset) +{ +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); +}#endif #ifndef find_first_bit
tools/lib/find_bit.c +21 -31
77 lines not on this page · raw message
Signature · 1 line
2.25.1
Re: [PATCH 6/8] lib: inline _find_next_bit() wrappers
Quoted 6 lines · Yury Norov
lib/find_bit.cdeclares five single-line wrappers for_find_next_bit(). We may turn those wrappers to inline functions. It eliminates unneeded function calls and opens room for compile-time optimizations.tools/include/asm-generic/bitops/find.h | 27 +++++++++--- tools/lib/find_bit.c | 52 ++++++++++-------------
In a separated patch, please. I don't think we need to defer this series in case if tools lagged (which is usual case in my practice).
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 6/8] lib: inline _find_next_bit() wrappers
Quoted 11 lines · Andy Shevchenko
Quoted 6 lines · Yury Norov
lib/find_bit.cdeclares five single-line wrappers for_find_next_bit(). We may turn those wrappers to inline functions. It eliminates unneeded function calls and opens room for compile-time optimizations.tools/include/asm-generic/bitops/find.h | 27 +++++++++--- tools/lib/find_bit.c | 52 ++++++++++-------------In a separated patch, please. I don't think we need to defer this series in case if tools lagged (which is usual case in my practice).
Splitting it to kernel and tools parts means either a patch bomb for tools or doubling the size of the series. Both options look worse than what we have now.
Can you explain more on the lagged tools argument?
Quoted 5 lines
--
With Best Regards,
Andy Shevchenko
Yury Norov
maintainerPATCH 7/8 lib: add fast path for find_next_*_bit()
In reply to Yury NorovSimilarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word. In the very best case, the compiler may replace a function call with a single ffs or ffz instruction.
--- include/asm-generic/bitops/find.h | 30 +++++++++++++++++++++++++ include/asm-generic/bitops/le.h | 21 +++++++++++++++++ tools/include/asm-generic/bitops/find.h | 30 +++++++++++++++++++++++++ 3 files changed, 81 insertions(+)
include/asm-generic/bitops/find.h +30 -0
@@ -20,6 +20,16 @@ static inlineunsigned long find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size -1 )) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); }#endif
@@ -40,6 +50,16 @@ unsigned long find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long offset) { + if (SMALL_CONST(size - 1)) { + unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr1 & *addr2 &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); }#endif
@@ -58,6 +78,16 @@ static inlineunsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size -1 )) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); }#endif
include/asm-generic/bitops/le.h +21 -0
@@ -5,6 +5,7 @@#include <asm-generic/bitops/find.h> #include <asm/types.h> #include <asm/byteorder.h> +#include <linux/swab.h> #if defined(__LITTLE_ENDIAN)
@@ -37,6 +38,16 @@ static inlineunsigned long find_next_zero_bit_le (const void *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,1 ); }#endif
@@ -46,6 +57,16 @@ static inlineunsigned long find_next_bit_le (const void *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,1 ); }#endif
tools/include/asm-generic/bitops/find.h +30 -0
@@ -20,6 +20,16 @@ static inlineunsigned long find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size -1 )) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); }#endif
@@ -40,6 +50,16 @@ unsigned long find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long offset) { + if (SMALL_CONST(size - 1)) { + unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr1 & *addr2 &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); }#endif
@@ -58,6 +78,16 @@ static inlineunsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (SMALL_CONST (size -1 )) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); }#endif
Signature · 1 line
2.25.1
Re: [PATCH 7/8] lib: add fast path for find_next_*_bit()
Quoted 4 lines · Yury Norov
Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word. In the very best case, the compiler may replace a function call with a single ffs or ffz instruction.
Would be nice to have the examples how it reduces the actual code size (based on the existing code in kernel, especially in widely used frameworks / subsystems, like PCI).
Signature · 2 lines
With Best Regards, Andy Shevchenko
RE: [PATCH 7/8] lib: add fast path for find_next_*_bit()
From: Andy Shevchenko
Quoted 11 lines
Sent: 01 February 2021 13:49
Quoted 4 lines · Yury Norov
Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word. In the very best case, the compiler may replace a function call with a single ffs or ffz instruction.
Would be nice to have the examples how it reduces the actual code size (based on the existing code in kernel, especially in widely used frameworks / subsystems, like PCI).
I bet it makes the kernel bigger but very slightly faster. But the fact that the wrappers end up in the i-cache may mean that inlining actually makes it slower for some calling sequences.
If a bitmap fits in a single word (as a compile-time constant) then you should (probably) be using different functions if you care about performance.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Re: [PATCH 7/8] lib: add fast path for find_next_*_bit()
Quoted 12 lines · David Laight
From: Andy Shevchenko
Quoted 10 lines
Sent: 01 February 2021 13:49
Quoted 4 lines · Yury Norov
Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word. In the very best case, the compiler may replace a function call with a single ffs or ffz instruction.
Would be nice to have the examples how it reduces the actual code size (based on the existing code in kernel, especially in widely used frameworks / subsystems, like PCI).
Quoted 8 lines
I bet it makes the kernel bigger but very slightly faster. But the fact that the wrappers end up in the i-cache may mean that inlining actually makes it slower for some calling sequences.
If a bitmap fits in a single word (as a compile-time constant) then you should (probably) be using different functions if you care about performance.
Isn't this patch series exactly about it?
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 7/8] lib: add fast path for find_next_*_bit()
[ CC Alexey Klimov, andRasmus Villemoes as they also may be interested ]
Quoted 18 lines · Andy Shevchenko
Quoted 16 lines · David Laight
From: Andy Shevchenko
Quoted 10 lines
Sent: 01 February 2021 13:49
Quoted 4 lines · Yury Norov
Similarly to bitmap functions, find_next_*_bit() users will benefit if we'll handle a case of bitmaps that fit into a single word. In the very best case, the compiler may replace a function call with a single ffs or ffz instruction.
Would be nice to have the examples how it reduces the actual code size (based on the existing code in kernel, especially in widely used frameworks / subsystems, like PCI).
I bet it makes the kernel bigger but very slightly faster. But the fact that the wrappers end up in the i-cache may mean that inlining actually makes it slower for some calling sequences.
Quoted 5 lines
Quoted 3 lines
If a bitmap fits in a single word (as a compile-time constant) then you should (probably) be using different functions if you care about performance.
Isn't this patch series exactly about it?
Probably, David meant something like find_first_bit_fast_path(). Not sure that this approach would be better than pure inlining.
Addressing questions above.
My arm64 build for qemu:
Before:
Idx Name Size VMA LMA File off Algn 0 .head.text 00010000 ffff800010000000 ffff800010000000 00010000 2**16
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .text 011603a8 ffff800010010000 ffff800010010000 00020000 2**16
CONTENTS, ALLOC, LOAD, READONLY, CODE
2 .got.plt 00000018 ffff8000111703a8 ffff8000111703a8 011803a8 2**3
CONTENTS, ALLOC, LOAD, DATA
3 .rodata 007a29b2 ffff800011180000 ffff800011180000 01190000 2**12
CONTENTS, ALLOC, LOAD, DATA
4 .pci_fixup 000025f0 ffff8000119229c0 ffff8000119229c0 019329c0 2**4
CONTENTS, ALLOC, LOAD, READONLY, DATA
5 __ksymtab 000100d4 ffff800011924fb0 ffff800011924fb0 01934fb0 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
6 __ksymtab_gpl 000147cc ffff800011935084 ffff800011935084 01945084 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
7 __ksymtab_strings 0003b0be ffff800011949850 ffff800011949850
01959850 2**0
CONTENTS, ALLOC, LOAD, READONLY, DATA
8 __param 00003e58 ffff800011984910 ffff800011984910 01994910 2**3
CONTENTS, ALLOC, LOAD, READONLY, DATA
9 __modver 00000678 ffff800011988768 ffff800011988768 01998768 2**3
CONTENTS, ALLOC, LOAD, DATA
10 __ex_table 00002270 ffff800011988de0 ffff800011988de0 01998de0 2**3
CONTENTS, ALLOC, LOAD, READONLY, DATA
11 .notes 0000003c ffff80001198b050 ffff80001198b050 0199b050 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
12 .init.text 0007b09c ffff8000119a0000 ffff8000119a0000 019a0000 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
13 .exit.text 00004120 ffff800011a1b09c ffff800011a1b09c 01a1b09c 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
...
After:
Idx Name Size VMA LMA File off Algn 0 .head.text 00010000 ffff800010000000 ffff800010000000 00010000 2**16
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .text 011613a8 ffff800010010000 ffff800010010000 00020000 2**16
CONTENTS, ALLOC, LOAD, READONLY, CODE
2 .got.plt 00000018 ffff8000111713a8 ffff8000111713a8 011813a8 2**3
CONTENTS, ALLOC, LOAD, DATA
3 .rodata 007a26b2 ffff800011180000 ffff800011180000 01190000 2**12
CONTENTS, ALLOC, LOAD, DATA
4 .pci_fixup 000025f0 ffff8000119226c0 ffff8000119226c0 019326c0 2**4
CONTENTS, ALLOC, LOAD, READONLY, DATA
5 __ksymtab 000100bc ffff800011924cb0 ffff800011924cb0 01934cb0 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
6 __ksymtab_gpl 000147cc ffff800011934d6c ffff800011934d6c 01944d6c 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
7 __ksymtab_strings 0003b09b ffff800011949538 ffff800011949538
01959538 2**0
CONTENTS, ALLOC, LOAD, READONLY, DATA
8 __param 00003e58 ffff8000119845d8 ffff8000119845d8 019945d8 2**3
CONTENTS, ALLOC, LOAD, READONLY, DATA
9 __modver 00000678 ffff800011988430 ffff800011988430 01998430 2**3
CONTENTS, ALLOC, LOAD, DATA
10 __ex_table 00002270 ffff800011988aa8 ffff800011988aa8 01998aa8 2**3
CONTENTS, ALLOC, LOAD, READONLY, DATA
11 .notes 0000003c ffff80001198ad18 ffff80001198ad18 0199ad18 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
12 .init.text 0007b1a8 ffff8000119a0000 ffff8000119a0000 019a0000 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
13 .exit.text 00004120 ffff800011a1b1a8 ffff800011a1b1a8 01a1b1a8 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
The size of .text is increased by 0x1000 bytes, or 0.02% The size of .rodata is decreased by 0x300 bytes, or 0.06% The size of __ksymtab is decreased by 24 bytes, or 0.018%
So the cost of this fast path is ~3.3K.
Regarding code generation, this is the quite typical find_bit() user:
unsigned int cpumask_next(int n, const struct cpumask *srcp)
{
/* -1 is a legal arg here. */
if (n != -1)
cpumask_check(n);
return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1);
}EXPORT_SYMBOL(cpumask_next);
Before:
0000000000000000 <cpumask_next>:
0: a9bf7bfd stp x29, x30, [sp, #-16]! 4: 11000402 add w2, w0, #0x1 8: aa0103e0 mov x0, x1 c: d2800401 mov x1, #0x40 // #64 10: 910003fd mov x29, sp 14: 93407c42 sxtw x2, w2 18: 94000000 bl 0 <find_next_bit> 1c: a8c17bfd ldp x29, x30, [sp], #16 20: d65f03c0 ret 24: d503201f nop
After:
0000000000000140 <cpumask_next>:
140: 11000400 add w0, w0, #0x1 144: 93407c00 sxtw x0, w0 148: f100fc1f cmp x0, #0x3f 14c: 54000168 b.hi 178 <cpumask_next+0x38> // b.pmore 150: f9400023 ldr x3, [x1] 154: 92800001 mov x1, #0xffffffffffffffff // #-1 158: 9ac02020 lsl x0, x1, x0 15c: 52800802 mov w2, #0x40 // #64 160: 8a030001 and x1, x0, x3 164: dac00020 rbit x0, x1 168: f100003f cmp x1, #0x0 16c: dac01000 clz x0, x0 170: 1a800040 csel w0, w2, w0, eq // eq = none 174: d65f03c0 ret 178: 52800800 mov w0, #0x40 // #64 17c: d65f03c0 ret
find_next_bit() call is removed with the cost of 6 instructions. (And I suspect we can improve the GENMASK() for better code generation.) find_next_bit() itself is 41 instructions, so I believe this fast path would bring
value for many users.
On the other hand, if someone is limited with I-cache and wants to avoid generating fast paths, I think it's worth to make SMALL_CONST() configurable, which would also disable fast paths in lib/bitmap.c. We may rely on -Os flag, or enable fast path in config explicitly:
(quoted diff) +0 -0
b/include/asm-generic/bitsperlong.h
index 0eeb77544f1d..209e531074c1 100644
include/asm-generic/bitsperlong.h +1 -0
@@ -23,6 +23,10 @@#define BITS_PER_LONG_LONG 64#endif +#ifdef CONFIG_FAST_PATH #define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n)
< BITS_PER_LONG)
+#else
+#define SMALL_CONST(n) (0)
+#endif
#endif /* __ASM_GENERIC_BITS_PER_LONG */
lib/Kconfig +7 -0
@@ -39,6 +39,14 @@ config PACKING When in doubt, say N. +config FAST_PATH + bool "Enable fast path code generation" + default y + help + This option enables fast path optimization with the cost + of increasing the text section. + config BITREVERSE tristate
Quoted 2 lines
With Best Regards,
Andy Shevchenko
Yury Norov
maintainerPATCH 8/8 lib: add fast path for find_first_*_bit() and find_last_bit()
In reply to Yury NorovSimilarly to bitmap functions, users will benefit if we'll handle a case of small-size bitmaps that fit into a single word.
While here, move the find_last_bit() declaration to bitops/find.h where other find_*_bit() functions sit.
--- include/asm-generic/bitops/find.h | 50 +++++++++++++++++++++++-- include/linux/bitops.h | 12 ------ lib/find_bit.c | 12 +++--- tools/include/asm-generic/bitops/find.h | 28 ++++++++++++-- tools/lib/find_bit.c | 4 +- 5 files changed, 79 insertions(+), 27 deletions(-)
include/asm-generic/bitops/find.h +46 -4
@@ -5,6 +5,9 @@extern unsigned long _find_next_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long nbits,unsigned long start,unsigned long invert,unsigned long le); +extern unsigned long _find_first_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_last_bit (const unsigned long *addr,unsigned long size);#ifndef find_next_bit/**
@@ -102,8 +105,17 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,* Returns the bit number of the first set bit. * If no bits are set, returns @size. */ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (SMALL_CONST (size -1 )) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__ffs (val) : size; + } + +return _find_first_bit (addr, size); +}/** * find_first_zero_bit - find the first cleared bit in a memory region
@@ -113,8 +125,17 @@ extern unsigned long find_first_bit(const unsigned long *addr,* Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ -extern unsigned long find_first_zero_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +{ +if (SMALL_CONST (size -1 )) { +unsigned long val = *addr | ~BITS_FIRST (size -1 ); + +return val == ~0UL ? size :ffz (val); + } + +return _find_first_zero_bit (addr, size); +}#else /* CONFIG_GENERIC_FIND_FIRST_BIT */ #ifndef find_first_bit
@@ -126,6 +147,27 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +#ifndef find_last_bit +/** +* find_last_bit - find the last set bit in a memory region +* @addr: The address to start the search at +* @size: The number of bits to search +* +* Returns the bit number of the last set bit, or size. +*/ +static inline +unsigned long find_last_bit (const unsigned long *addr,unsigned long size) +{ +if (SMALL_CONST (size -1 )) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__fls (val) : size; + } + +return _find_last_bit (addr, size); +} +#endif +/** * find_next_clump8 - find next 8-bit clump with set bits in a memory region * @clump: location to store copy of found clump
include/linux/bitops.h +0 -12
@@ -286,17 +286,5 @@ static __always_inline void __assign_bit(long nr, volatile unsigned long *addr, })#endif -#ifndef find_last_bit -/** -* find_last_bit - find the last set bit in a memory region -* @addr: The address to start the search at -* @size: The number of bits to search -* -* Returns the bit number of the last set bit, or size. -*/ -extern unsigned long find_last_bit (const unsigned long *addr, -unsigned long size); -#endif -#endif /* __KERNEL__ */ #endif
lib/find_bit.c +6 -6
@@ -75,7 +75,7 @@ EXPORT_SYMBOL(_find_next_bit);/* * Find the first set bit in a memory region. */ -unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +unsigned long _find_first_bit (const unsigned long *addr,unsigned long size) {unsigned long idx;
@@ -86,14 +86,14 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)return size; } -EXPORT_SYMBOL (find_first_bit); +EXPORT_SYMBOL (_find_first_bit);#endif #ifndef find_first_zero_bit/* * Find the first cleared bit in a memory region. */ -unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size) {unsigned long idx;
@@ -104,11 +104,11 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)return size; } -EXPORT_SYMBOL (find_first_zero_bit); +EXPORT_SYMBOL (_find_first_zero_bit);#endif #ifndef find_last_bit -unsigned long find_last_bit (const unsigned long *addr,unsigned long size) +unsigned long _find_last_bit (const unsigned long *addr,unsigned long size) {if (size) {unsigned long val =BITS_FIRST_MASK (size -1 );
@@ -124,7 +124,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size) }return size; } -EXPORT_SYMBOL (find_last_bit); +EXPORT_SYMBOL (_find_last_bit);#endif unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
tools/include/asm-generic/bitops/find.h +25 -3
@@ -5,6 +5,9 @@extern unsigned long _find_next_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long nbits,unsigned long start,unsigned long invert,unsigned long le); +extern unsigned long _find_first_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_last_bit (const unsigned long *addr,unsigned long size);#ifndef find_next_bit/**
@@ -102,8 +105,17 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,* Returns the bit number of the first set bit. * If no bits are set, returns @size. */ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (SMALL_CONST (size -1 )) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__ffs (val) : size; + } + +return _find_first_bit (addr, size); +}#endif /* find_first_bit */
@@ -117,7 +129,17 @@ extern unsigned long find_first_bit(const unsigned long *addr,* Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ -unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size); +static inline +unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +{ +if (SMALL_CONST (size -1 )) { +unsigned long val = *addr | ~BITS_FIRST (size -1 ); + +return val == ~0UL ? size :ffz (val); + } + +return _find_first_zero_bit (addr, size); +}#endif #endif /*_TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_ */
tools/lib/find_bit.c +2 -2
@@ -83,7 +83,7 @@ unsigned long _find_next_bit(const unsigned long *addr1,/* * Find the first set bit in a memory region. */ -unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +unsigned long _find_first_bit (const unsigned long *addr,unsigned long size) {unsigned long idx;
@@ -100,7 +100,7 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)/* * Find the first cleared bit in a memory region. */ -unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size) {unsigned long idx;
Signature · 1 line
2.25.1
Re: [PATCH 8/8] lib: add fast path for find_first_*_bit() and find_last_bit()
Quoted 5 lines · Yury Norov
Similarly to bitmap functions, users will benefit if we'll handle a case of small-size bitmaps that fit into a single word.
While here, move the
find_last_bit()declaration tobitops/find.hwhere other find_*_bit() functions sit.
As per previous patches:
- decouple from tools
- show examples of the code generation difference
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainer[add David Laight <[email protected]> ]
Quoted 11 lines · Yury Norov
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In
linux/bitmap.hwe have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.find_*_bit() API lacks this functionality; despite users will benefit from it a lot. One important example is cpumask subsystem when
NR_CPUS<=BITS_PER_LONG. In the very best case, the compiler may replace a find_*_bit() call for such a bitmap with a single ffs or ffz instruction.
Quoted 6 lines
Tools is synchronized with new implementation where needed.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: - employGENMASK()for bitmaps;
- unifyfind_bitinliners in;
- address comments to v1;
Comments so far:
- increased image size (patch #8) - addressed by introducing CONFIG_FAST_PATH;
- split tools and kernel parts - not clear why it's better.
Anything else?
Quoted 21 lines · Yury Norov
[add David Laight <[email protected]> ]
Quoted 11 lines · Yury Norov
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In
linux/bitmap.hwe have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.find_*_bit() API lacks this functionality; despite users will benefit from it a lot. One important example is cpumask subsystem when
NR_CPUS<=BITS_PER_LONG. In the very best case, the compiler may replace a find_*_bit() call for such a bitmap with a single ffs or ffz instruction.Quoted 6 lines
Tools is synchronized with new implementation where needed.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: - employGENMASK()for bitmaps;
- unifyfind_bitinliners in;
- address comments to v1;
Quoted 5 lines
Comments so far:
- increased image size (patch #8) - addressed by introducingCONFIG_FAST_PATH;- split tools and kernel parts - not clear why it's better.
Because tools are user space programs and sometimes may not follow kernel specifics, so they are different logically and changes should be separated.
Quoted 1 line
Anything else?
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerQuoted 22 lines · Andy Shevchenko
Quoted 21 lines · Yury Norov
[add David Laight <[email protected]> ]
Quoted 17 lines · Yury Norov
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In
linux/bitmap.hwe have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.find_*_bit() API lacks this functionality; despite users will benefit from it a lot. One important example is cpumask subsystem when
NR_CPUS<=BITS_PER_LONG. In the very best case, the compiler may replace a find_*_bit() call for such a bitmap with a single ffs or ffz instruction.Tools is synchronized with new implementation where needed.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: - employGENMASK()for bitmaps;
- unifyfind_bitinliners in;
- address comments to v1;
Quoted 8 lines
Quoted 5 lines
Comments so far:
- increased image size (patch #8) - addressed by introducingCONFIG_FAST_PATH;- split tools and kernel parts - not clear why it's better.
Because tools are user space programs and sometimes may not follow kernel specifics, so they are different logically and changes should be separated.
In this specific case tools follow kernel well.
Nevertheless, if you think it's a blocker for the series, I can split. What option for tools is better for you - doubling the number of patches or squashing everything in a patch bomb?
Quoted 27 lines · Yury Norov
Quoted 26 lines · Andy Shevchenko
Quoted 24 lines · Yury Norov
[add David Laight <[email protected]> ]
Quoted 11 lines · Yury Norov
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In
linux/bitmap.hwe have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.find_*_bit() API lacks this functionality; despite users will benefit from it a lot. One important example is cpumask subsystem when
NR_CPUS<=BITS_PER_LONG. In the very best case, the compiler may replace a find_*_bit() call for such a bitmap with a single ffs or ffz instruction.Quoted 6 lines
Tools is synchronized with new implementation where needed.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: - employGENMASK()for bitmaps;
- unifyfind_bitinliners in;
- address comments to v1;Comments so far:
- increased image size (patch #8) - addressed by introducingCONFIG_FAST_PATH;
Quoted 8 lines
Quoted 4 lines
Quoted 1 line
- split tools and kernel parts - not clear why it's better.
Because tools are user space programs and sometimes may not follow kernel specifics, so they are different logically and changes should be separated.
In this specific case tools follow kernel well.
Nevertheless, if you think it's a blocker for the series, I can split.
It's not a blocker from my side. But you make it harder to push like this, because you will need a tag from tools, which in my practice is quite hard to get -> blocker. My point is: don't make obstacles where we can avoid them. So, if tools won't take this, it won't block us.
Quoted 3 lines
What
option for tools is better for you - doubling the number of patches or squashing everything in a patch bomb?
Not a tools guy, but common sense tells me that the best approach is to follow kind of changes in the kernel (similar granularity).
Signature · 2 lines
With Best Regards, Andy Shevchenko