lib/find_bit: fast path for small bitmaps
Subsystems (9)
Yury Norov
maintainerv4 cover lib/find_bit: fast path for small bitmaps
Bitmap operations are much simpler and faster in case of small bitmaps which fit into a single word. In linux/bitmap.c we have a machinery that allows compiler to replace actual function call with a few instructions if bitmaps passed into the function are small and their size is known at compile time.
find_*_bit() API lacks this functionality; but users will benefit from it a lot. One important example is cpumask subsystem when NR_CPUS <= BITS_PER_LONG.
v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: - move le.h header together with find.h for m68 and sh;
- preserve small_const_nbits() macro;
- drop FAST_PATH config option as this series doesn't increase .text, instead, it compacts it;
- add Andy and Rasmus as reviewers of BITMAP API.
Yury Norov (13):
tools: disable -Wno-type-limits
tools: bitmap: sync function declarations with the kernel
arch: rearrange headers inclusion order in asm/bitops for m68k and sh
lib: introduce BITS_{FIRST,LAST} macro
tools: sync BITS_MASK macros with the kernel
lib: extend the scope of small_const_nbits() macro
tools: sync small_const_nbits() macro with the kernel
lib: inline _find_next_bit() wrappers
tools: sync find_next_bit implementation
lib: add fast path for find_next_*_bit()
lib: add fast path for find_first_*_bit() and find_last_bit()
tools: sync lib/find_bit implementation
MAINTAINERS: Add entry for the bitmap API
MAINTAINERS | 16 ++++ arch/m68k/include/asm/bitops.h | 6 +- arch/sh/include/asm/bitops.h | 5 +- include/asm-generic/bitops/find.h | 108 +++++++++++++++++++++--- include/asm-generic/bitops/le.h | 38 ++++++++- include/asm-generic/bitsperlong.h | 9 ++ include/linux/bitmap.h | 30 +++---- 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 | 3 + tools/include/linux/bitmap.h | 31 +++---- 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 +- 23 files changed, 340 insertions(+), 204 deletions(-)
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH v4 1/13 tools: disable -Wno-type-limits
GENMASK(h, l) may be passed with unsigned types. In such case, type-limits warning is generated for example in case of GENMASK(h, 0).
--- tools/scripts/Makefile.include | 1 + 1 file changed, 1 insertion(+)
tools/scripts/Makefile.include +1 -0
@@ -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
Rasmus Villemoes
reviewerRe: [PATCH 01/13] tools: disable -Wno-type-limits
Quoted 13 lines · Yury Norov
GENMASK(h, l)may be passed with unsigned types. In such case, type-limits warning is generated for example in case ofGENMASK(h, 0).Signed-off-by Yury Norov <[email protected]>--- tools/scripts/Makefile.include | 1 + 1 file changed, 1 insertion(+)tools/scripts/Makefile.include +0
-0
tools/scripts/Makefile.include EXTRA_WARNINGS += -Wswitch-enum · line 42
Quoted 5 lines
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
I don't like that kind of collateral damage. I seem to recall another instance where a macro was instead rewritten to avoid triggering the type-limits warning (with a comment explaining the uglyness). Something like
foo > bar is the same as
!(foo <= bar) which is the same as
!(foo == bar || foo < bar)
Dunno if that would work here, but if it did, it would have the bonus that when somebody builds the kernel proper with Wtype-limits enabled (maybe W=1 or W=2) there would be no false positives from GENMASK to wade through.
Alternatively, we really should consider making use of _Pragma to locally disable/re-enable certain warnings.
Rasmus
Re: [PATCH 01/13] tools: disable -Wno-type-limits
Quoted 3 lines · Rasmus Villemoes
Quoted 2 lines · Yury Norov
GENMASK(h, l)may be passed with unsigned types. In such case, type-limits warning is generated for example in case ofGENMASK(h, 0).
...
Quoted 8 lines
I don't like that kind of collateral damage. I seem to recall another instance where a macro was instead rewritten to avoid triggering the type-limits warning (with a comment explaining the uglyness). Something like
foo > bar is the same as
!(foo <= bar) which is the same as
!(foo == bar || foo < bar)
Quoted 7 lines
Dunno if that would work here, but if it did, it would have the bonus that when somebody builds the kernel proper with Wtype-limits enabled (maybe W=1 or W=2) there would be no false positives from GENMASK to wade through.
Alternatively, we really should consider making use of
_Pragmato locally disable/re-enable certain warnings.
Rasmus, in the kernel the same was fixed as per 355a3587d4ca. I don't know why tools should be different to that.
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH v4 2/13 tools: bitmap: sync function declarations with the 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
Re: [PATCH 02/13] tools: bitmap: sync function declarations with the kernel
Quoted 4 lines · Yury Norov
Some functions in
tools/include/linux/bitmap.hdeclare nbits as int. In the kernel nbits is declared as unsigned int.Signed-off-by Yury Norov <[email protected]>
Yury Norov
maintainerPATCH v4 3/13 arch: rearrange headers inclusion order in asm/bitops for m68k and sh
In reply to Yury Norovm68k and sh include bitmap/{find,le}.h prior to ffs/fls headers. New fast-path implementation in find.h requires ffs/fls. Reordering the headers inclusion sequence helps to prevent compile-time implicit function declaration error.
--- arch/m68k/include/asm/bitops.h | 6 +++--- arch/sh/include/asm/bitops.h | 5 +++-- 2 files changed, 6 insertions(+), 5 deletions(-)
arch/m68k/include/asm/bitops.h +3 -3
@@ -440,8 +440,6 @@ static inline unsigned long ffz(unsigned long word)#endif -#include <asm-generic/bitops/find.h> -#ifdef __KERNEL__#if defined(CONFIG_CPU_HAS_NO_BITFIELDS )
@@ -525,10 +523,12 @@ static inline int __fls(int x)#define __clear_bit_unlock clear_bit_unlock#include <asm-generic/bitops/ext2-atomic.h> -#include <asm-generic/bitops/le.h> #include <asm-generic/bitops/fls64.h> #include <asm-generic/bitops/sched.h> #include <asm-generic/bitops/hweight.h> +#include <asm-generic/bitops/le.h> #endif /* __KERNEL__ */ +#include <asm-generic/bitops/find.h> +#endif /* _M68K_BITOPS_H */
arch/sh/include/asm/bitops.h +3 -2
@@ -58,15 +58,16 @@ static inline unsigned long __ffs(unsigned long word) return result; } -#include <asm-generic/bitops/find.h> #include <asm-generic/bitops/ffs.h> #include <asm-generic/bitops/hweight.h> #include <asm-generic/bitops/lock.h> #include <asm-generic/bitops/sched.h> -#include <asm-generic/bitops/le.h> #include <asm-generic/bitops/ext2-atomic.h> #include <asm-generic/bitops/fls.h> #include <asm-generic/bitops/__fls.h> #include <asm-generic/bitops/fls64.h> +#include <asm-generic/bitops/le.h> +#include <asm-generic/bitops/find.h> +#endif /* __ASM_SH_BITOPS_H */
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH v4 4/13 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 BITMAP* macros is wider than just bitmaps. 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 increase the scope of the macros.
This change doesn't affect code generation. On ARM64:scripts/bloat-o-meter vmlinux.before vmlinux add/remove: 1/2 grow/shrink: 2/0 up/down: 17/-16 (1)
Function old new delta ethtool_get_drvinfo 900 908 +8 e843419@0cf2_0001309d_7f0 - 8 +8 vermagic 48 49 +1 e843419@0d45_000138bb_f68 8 - -8 e843419@0cc9_00012bce_198c 8 - -8
Total: Before=26092016, After=26092017, chg +0.00%
The compilerr is:
aarch64-linux-gnu-gcc (Linaro GCC 7.3-2018.05) 7.3.1 20180425
--- 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 ++++---- 8 files changed, 43 insertions(+), 40 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
@@ -173,7 +173,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; } }
@@ -1291,7 +1291,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; }
Signature · 1 line
2.25.1
Rasmus Villemoes
reviewerRe: [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro
Quoted 10 lines · Yury Norov
BITMAP_{LAST,FIRST}_WORD_MASK() in
linux/bitmap.hduplicates the functionality ofGENMASK(). The scope of BITMAP* macros is wider than just bitmaps. 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 increase the scope of the macros.This change doesn't affect code generation. On ARM64:
scripts/bloat-o-metervmlinux.before vmlinux add/remove: 1/2 grow/shrink: 2/0 up/down: 17/-16 (1)
Quoted 6 lines
Function old new delta ethtool_get_drvinfo 900 908 +8 e843419@0cf2_0001309d_7f0 - 8 +8 vermagic 48 49 +1 e843419@0d45_000138bb_f68 8 - -8 e843419@0cc9_00012bce_198c 8 - -8
[what on earth are those weird symbols?]
include/linux/bits.h line 44
Quoted 13 lines
include/linux/bits.h +5
-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)
I don't think it's a good idea to propagate the unusual closed-range semantics of GENMASK to those wrappers. Almost all C and kernel code uses the 'inclusive lower bound, exclusive upper bound', and I'd expect BITS_FIRST(5) to result in a word with five bits set, not six. So I think these changes as-is make the code much harder to read and understand.
Regardless, please add some comments on the valid input ranges to the macros, whether that ends up being 0 <= nr < BITS_PER_LONG or 0 < nr <= BITS_PER_LONG or whatnot.
It would also be much easier to review if you just redefined the BITMAP_LAST_WORD_MASK macros etc. in terms of these new things, so you wouldn't have to do a lot of mechanical changes at the same time as introducing the new ones - especially when those mechanical changes involve adding a "minus 1" everywhere.
Rasmus
Re: [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro
Quoted 45 lines · Rasmus Villemoes
Quoted 10 lines · Yury Norov
BITMAP_{LAST,FIRST}_WORD_MASK() in
linux/bitmap.hduplicates the functionality ofGENMASK(). The scope of BITMAP* macros is wider than just bitmaps. 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 increase the scope of the macros.This change doesn't affect code generation. On ARM64:
scripts/bloat-o-metervmlinux.before vmlinux add/remove: 1/2 grow/shrink: 2/0 up/down: 17/-16 (1)Quoted 6 lines
Function old new delta ethtool_get_drvinfo 900 908 +8 e843419@0cf2_0001309d_7f0 - 8 +8 vermagic 48 49 +1 e843419@0d45_000138bb_f68 8 - -8 e843419@0cc9_00012bce_198c 8 - -8[what on earth are those weird symbols?]
include/linux/bits.h line 44
Quoted 13 lines
include/linux/bits.h +5
-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)I don't think it's a good idea to propagate the unusual closed-range semantics of GENMASK to those wrappers. Almost all C and kernel code uses the 'inclusive lower bound, exclusive upper bound', and I'd expect
BITS_FIRST(5)to result in a word with five bits set, not six. So I think these changes as-is make the code much harder to read and understand.Regardless, please add some comments on the valid input ranges to the macros, whether that ends up being 0 <= nr <
BITS_PER_LONGor 0 < nr <=BITS_PER_LONGor whatnot.
Quoted 5 lines
It would also be much easier to review if you just redefined the
BITMAP_LAST_WORD_MASKmacros etc. in terms of these new things, so you wouldn't have to do a lot of mechanical changes at the same time as introducing the new ones - especially when those mechanical changes involve adding a "minus 1" everywhere.
I tend to agree with Rasmus here.
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro
Quoted 46 lines · Andy Shevchenko
Quoted 45 lines · Rasmus Villemoes
Quoted 10 lines · Yury Norov
BITMAP_{LAST,FIRST}_WORD_MASK() in
linux/bitmap.hduplicates the functionality ofGENMASK(). The scope of BITMAP* macros is wider than just bitmaps. 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 increase the scope of the macros.This change doesn't affect code generation. On ARM64:
scripts/bloat-o-metervmlinux.before vmlinux add/remove: 1/2 grow/shrink: 2/0 up/down: 17/-16 (1)Quoted 6 lines
Function old new delta ethtool_get_drvinfo 900 908 +8 e843419@0cf2_0001309d_7f0 - 8 +8 vermagic 48 49 +1 e843419@0d45_000138bb_f68 8 - -8 e843419@0cc9_00012bce_198c 8 - -8[what on earth are those weird symbols?]
include/linux/bits.h line 44
Quoted 13 lines
include/linux/bits.h +5
-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)I don't think it's a good idea to propagate the unusual closed-range semantics of GENMASK to those wrappers. Almost all C and kernel code uses the 'inclusive lower bound, exclusive upper bound', and I'd expect
BITS_FIRST(5)to result in a word with five bits set, not six. So I think these changes as-is make the code much harder to read and understand.Regardless, please add some comments on the valid input ranges to the macros, whether that ends up being 0 <= nr <
BITS_PER_LONGor 0 < nr <=BITS_PER_LONGor whatnot.
Quoted 7 lines
Quoted 5 lines
It would also be much easier to review if you just redefined the
BITMAP_LAST_WORD_MASKmacros etc. in terms of these new things, so you wouldn't have to do a lot of mechanical changes at the same time as introducing the new ones - especially when those mechanical changes involve adding a "minus 1" everywhere.I tend to agree with Rasmus here.
OK. All this plus terrible GENMASK(high, low) design, when high goes first, makes me feel like we need to deprecate GENMASK and propose a new interface.
What do you think about this:
BITS_FIRST(bitnum) -> [0, bitnum) BITS_LAST(bitnum) -> [bitnum, BITS_PER_LONG) BITS_RANGE(begin, end) -> [begin, end)
We can pick BITS_{LAST,FIRST} implementation from existing BITMAP_*_WORD_MASK analogues, and make the BITS_RANGE like:
#define BITS_RANGE(begin, end) BITS_FIRST(end) & BITS_LAST(begin)
Regarding BITMAP_*_WORD_MASK, I can save them in bitmap.h as aliases to BITS_{LAST,FIRST} to avoid massive renaming. (Should I?)
Would this all work for you?
Rasmus Villemoes
reviewerRe: [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro
Quoted 10 lines · Yury Norov
Quoted 7 lines · Andy Shevchenko
Quoted 5 lines
It would also be much easier to review if you just redefined the
BITMAP_LAST_WORD_MASKmacros etc. in terms of these new things, so you wouldn't have to do a lot of mechanical changes at the same time as introducing the new ones - especially when those mechanical changes involve adding a "minus 1" everywhere.I tend to agree with Rasmus here.
Quoted 8 lines
OK. All this plus terrible
GENMASK(high, low)design, when high goes first, makes me feel like we need to deprecate GENMASK and propose a new interface.What do you think about this:
BITS_FIRST(bitnum) -> [0, bitnum) BITS_LAST(bitnum) -> [bitnum, BITS_PER_LONG) BITS_RANGE(begin, end) -> [begin, end)
Better, though I'm not too happy about BITS_LAST(n) not producing a word with the n highest bits set. I dunno, I don't have better names. BITS_FROM/BITS_UPTO perhaps, but not really (and upto sounds like it is inclusive). BITS_LOW/BITS_HIGH have the same problem as BITS_LAST.
Also, be careful to document what one can expect from the boundary values 0/BITS_PER_LONG. Is BITS_FIRST(0) a valid invocation? Does it yield 0UL? How about BITS_FIRST(BITS_PER_LONG), does that give ~0UL? Note that BITMAP_{FIRST,LAST}_WORD_MASK never produce 0, they're never used except with a word we know to be part of the bitmap.
Quoted 6 lines
We can pick BITS_{LAST,FIRST} implementation from existing BITMAP_*_WORD_MASK analogues, and make the
BITS_RANGElike:#define BITS_RANGE(begin, end) BITS_FIRST(end) & BITS_LAST(begin)Regarding BITMAP_*_WORD_MASK, I can save them in
bitmap.has aliases to BITS_{LAST,FIRST} to avoid massive renaming. (Should I?)
Yes, now that I read these again, I definitely think the BITMAP_{FIRST,LAST}_WORD_MASK should stay (whether their implementation change I don't care). Their names document what they do much better than if you replace them with their potential new implementations:BITMAP_FIRST_WORD_MASK(start) is obviously about having to mask off some low bits of the first word we're looking at because we're looking at an offset into the bitmap, and similarly BITMAP_LAST_WORD_MASK(nbits) explains itself: nbits is such that the last word needs some masking. But their replacements would be BITS_LAST(start) and BITS_FIRST(nbits) respectively (possibly with those arguments reduced mod N), which is quite confusing.
Quoted 1 line
Would this all work for you?
Maybe, I think I'd have to see the implementation and how those new macros get used.
Thanks,
Rasmus
Yury Norov
maintainerRe: [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro
Quoted 50 lines · Rasmus Villemoes
Quoted 10 lines · Yury Norov
Quoted 7 lines · Andy Shevchenko
Quoted 5 lines
It would also be much easier to review if you just redefined the
BITMAP_LAST_WORD_MASKmacros etc. in terms of these new things, so you wouldn't have to do a lot of mechanical changes at the same time as introducing the new ones - especially when those mechanical changes involve adding a "minus 1" everywhere.I tend to agree with Rasmus here.
Quoted 8 lines
OK. All this plus terrible
GENMASK(high, low)design, when high goes first, makes me feel like we need to deprecate GENMASK and propose a new interface.What do you think about this:
BITS_FIRST(bitnum) -> [0, bitnum) BITS_LAST(bitnum) -> [bitnum, BITS_PER_LONG) BITS_RANGE(begin, end) -> [begin, end)Better, though I'm not too happy about
BITS_LAST(n)not producing a word with the n highest bits set. I dunno, I don't have better names. BITS_FROM/BITS_UPTO perhaps, but not really (and upto sounds like it is inclusive). BITS_LOW/BITS_HIGH have the same problem asBITS_LAST.Also, be careful to document what one can expect from the boundary values 0/BITS_PER_LONG. Is
BITS_FIRST(0)a valid invocation? Does it yield 0UL? How aboutBITS_FIRST(BITS_PER_LONG), does that give ~0UL? Note that BITMAP_{FIRST,LAST}_WORD_MASK never produce 0, they're never used except with a word we know to be part of the bitmap.Quoted 6 lines
We can pick BITS_{LAST,FIRST} implementation from existing BITMAP_*_WORD_MASK analogues, and make the
BITS_RANGElike:#define BITS_RANGE(begin, end) BITS_FIRST(end) & BITS_LAST(begin)Regarding BITMAP_*_WORD_MASK, I can save them in
bitmap.has aliases to BITS_{LAST,FIRST} to avoid massive renaming. (Should I?)Yes, now that I read these again, I definitely think the BITMAP_{FIRST,LAST}_WORD_MASK should stay (whether their implementation change I don't care). Their names document what they do much better than if you replace them with their potential new implementations:
BITMAP_FIRST_WORD_MASK(start)is obviously about having to mask off some low bits of the first word we're looking at because we're looking at an offset into the bitmap, and similarlyBITMAP_LAST_WORD_MASK(nbits)explains itself: nbits is such that the last word needs some masking. But their replacements would beBITS_LAST(start)andBITS_FIRST(nbits)respectively (possibly with those arguments reduced mod N), which is quite confusing.
Quoted 7 lines
Quoted 1 line
Would this all work for you?
Maybe, I think I'd have to see the implementation and how those new macros get used.
Thanks,
Rasmus
I looked at this with a fresh eye this morning. All the noise we discuss I made to just call BITS_FIRST() 3 times in find.h. I think that for the purpose of this series, in find.h, it's worth to use GENMASK(size - 1, 0) where needed.
Regarding the general view on this, all the problems come from the fact that bitmap API is split between linux/bitmap.h and asm_generic/bitops/find.h. Find.h is naturally a part of bitmaps, but because of the split, it's hard to use handy bitmap.h macros in find.h.
Joining the headers is far out of the scope of this series. If no objections, I'd prefer to drop this patch now, and later carefully figure out how to join find.h and bitmap.h.
Yury
Yury Norov
maintainerPATCH v4 5/13 tools: sync BITS_MASK macros with the kernel
In reply to Yury NorovRemove BITMAP_{FIRST,LAST}_WORD_MASK and introduce BITS_{FIRST,LAST}{,_MASK} as per kernel implementation.
--- 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 ++-- 5 files changed, 18 insertions(+), 20 deletions(-)
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
Yury Norov
maintainerPATCH v4 6/13 lib: extend the scope of small_const_nbits() macro
In reply to Yury Norovfind_bit would also benefit from small_const_nbits() optimizations.
--- include/asm-generic/bitsperlong.h | 9 +++++++++ include/linux/bitmap.h | 3 --- 2 files changed, 9 insertions(+), 3 deletions(-)
include/asm-generic/bitsperlong.h +9 -0
@@ -23,4 +23,13 @@#define BITS_PER_LONG_LONG 64#endif +#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) + +/* +* The valid number of bits for a bitmap to be small enough, or in other words, +* fit into a single machine word is 1 to BITS_PER_LONG inclusively. 0 is not a +* valid number for size, and most probably a sing of error. +*/ +#define small_const_nbits (n) SMALL_CONST((n) - 1) +#endif /* __ASM_GENERIC_BITS_PER_LONG */
include/linux/bitmap.h +0 -3
@@ -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 );
Signature · 1 line
2.25.1
Rasmus Villemoes
reviewerRe: [PATCH 06/13] lib: extend the scope of small_const_nbits() macro
Quoted 15 lines · Yury Norov
find_bitwould also benefit fromsmall_const_nbits()optimizations.Signed-off-by Yury Norov <[email protected]>--- include/asm-generic/bitsperlong.h | 9 +++++++++ include/linux/bitmap.h | 3 --- 2 files changed, 9 insertions(+), 3 deletions(-)include/asm-generic/bitsperlong.h +0
-0@@ -23,4 +23,13 @@#define BITS_PER_LONG_LONG 64#endif
include/asm-generic/bitsperlong.h line 34
Quoted 10 lines
include/asm-generic/bitsperlong.h +9
-0+#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) + +/* +* The valid number of bits for a bitmap to be small enough, or in other words, +* fit into a single machine word is 1 to BITS_PER_LONG inclusively. 0 is not a +* valid number for size, and most probably a sing of error. +*/ +#define small_const_nbits (n) SMALL_CONST((n) - 1) +
I still don't see the point of introducing SMALL_CONST and still don't like the much-too-generic-name - especially since AFAICT you don't actually use it anywhere outside the definition of small_const_nbits()?
include/linux/bitmap.h extern int bitmap_print_to_pagebuf(bool list, char *buf, · line 226
Quoted 9 lines
include/asm-generic/bitsperlong.h +0
-0#endif /* __ASM_GENERIC_BITS_PER_LONG */ include/linux/bitmap.h +0
-0@@ -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. */
You added another comment near its new definition, but the left-behind comment in bitmap.h is now somewhat confusing, no? I suggest expanding your new comment a bit so it's clear why we're interested in whether a bitmap is known at compile-time to consist of exactly one word:
/*small_const_nbits(n) is true precisely when it is known at compile-time that BITMAP_SIZE(n) is 1, i.e. 1 <= n <= BITS_PER_LONG. This allows various bit/bitmap APIs to provide a fast inline implementation. Bitmaps of size 0 are very rare, and a compile-time-known-size 0 is most likely a sign of error. They will be handled correctly by the bit/bitmap APIs, but using the out-of-line functions, so that the inline implementations can unconditionally dereference the pointer(s).
*/
include/linux/bitmap.h extern int bitmap_print_to_pagebuf(bool list, char *buf, · line 229
Quoted 7 lines
include/linux/bitmap.h +0
-3-#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 );
Rasmus
Yury Norov
maintainerRe: [PATCH 06/13] lib: extend the scope of small_const_nbits() macro
Quoted 46 lines · Rasmus Villemoes
Quoted 15 lines · Yury Norov
find_bitwould also benefit fromsmall_const_nbits()optimizations.Signed-off-by Yury Norov <[email protected]>--- include/asm-generic/bitsperlong.h | 9 +++++++++ include/linux/bitmap.h | 3 --- 2 files changed, 9 insertions(+), 3 deletions(-)include/asm-generic/bitsperlong.h +0
-0@@ -23,4 +23,13 @@#define BITS_PER_LONG_LONG 64#endif include/asm-generic/bitsperlong.h line 34
Quoted 10 lines
include/asm-generic/bitsperlong.h +9
-0+#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) + +/* +* The valid number of bits for a bitmap to be small enough, or in other words, +* fit into a single machine word is 1 to BITS_PER_LONG inclusively. 0 is not a +* valid number for size, and most probably a sing of error. +*/ +#define small_const_nbits (n) SMALL_CONST((n) - 1) +I still don't see the point of introducing
SMALL_CONSTand still don't like the much-too-generic-name - especially since AFAICT you don't actually use it anywhere outside the definition ofsmall_const_nbits()?include/linux/bitmap.h extern int bitmap_print_to_pagebuf(bool list, char *buf, · line 226
Quoted 9 lines
include/asm-generic/bitsperlong.h +0
-0#endif /* __ASM_GENERIC_BITS_PER_LONG */ include/linux/bitmap.h +0
-0@@ -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. */ You added another comment near its new definition, but the left-behind comment in
bitmap.his now somewhat confusing, no? I suggest expanding your new comment a bit so it's clear why we're interested in whether a bitmap is known at compile-time to consist of exactly one word:
Quoted 9 lines
/*
small_const_nbits(n)is true precisely when it is known at compile-time thatBITMAP_SIZE(n)is 1, i.e. 1 <= n <=BITS_PER_LONG. This allows various bit/bitmap APIs to provide a fast inline implementation. Bitmaps of size 0 are very rare, and a compile-time-known-size 0 is most likely a sign of error. They will be handled correctly by the bit/bitmap APIs, but using the out-of-line functions, so that the inline implementations can unconditionally dereference the pointer(s).
*/
Ok, make sense
Quoted 9 lines
include/linux/bitmap.h extern int bitmap_print_to_pagebuf(bool list, char *buf, · line 229
Quoted 7 lines
include/linux/bitmap.h +0
-3-#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 );Rasmus
Yury Norov
maintainerPATCH v4 7/13 tools: sync small_const_nbits() macro with the kernel
In reply to Yury NorovMove the macro from tools/include/asm-generic/bitsperlong.h to tools/include/linux/bitmap.h
--- tools/include/asm-generic/bitsperlong.h | 3 +++ tools/include/linux/bitmap.h | 3 --- 2 files changed, 3 insertions(+), 3 deletions(-)
tools/include/asm-generic/bitsperlong.h +3 -0
@@ -18,4 +18,7 @@#define BITS_PER_LONG_LONG 64#endif +#define SMALL_CONST (n) (__builtin_constant_p(n) && (unsigned long)(n) < BITS_PER_LONG) +#define small_const_nbits (n) SMALL_CONST((n) - 1) +#endif /* __ASM_GENERIC_BITS_PER_LONG */
tools/include/linux/bitmap.h +0 -3
@@ -19,9 +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 small_const_nbits (nbits) \ - (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG) -static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) {if (small_const_nbits (nbits))
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH v4 8/13 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 ++----------------------------- 3 files changed, 37 insertions(+), 64 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
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH v4 9/13 tools: sync find_next_bit implementation
In reply to Yury NorovSync the implementation with recent kernel changes.
--- tools/include/asm-generic/bitops/find.h | 27 ++++++++++--- tools/lib/find_bit.c | 52 ++++++++++--------------- 2 files changed, 42 insertions(+), 37 deletions(-)
tools/include/asm-generic/bitops/find.h +21 -6
@@ -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
Yury Norov
maintainerPATCH v4 10/13 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 inline. In the very best case, the compiler may replace a function call with a few instructions.
This is the quite typical find_next_bit() user:
unsigned int cpumask_next(int n, const struct cpumask *srcp)
{
/* -1 is a legal arg here. */
if (n != -1)
cpumask_check(n);
return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1);
}
EXPORT_SYMBOL(cpumask_next);Currently, on ARM64 the generated code looks like this:
0000000000000000 <cpumask_next>: 0: a9bf7bfd stp x29, x30, [sp, #-16]! 4: 11000402 add w2, w0, #0x1 8: aa0103e0 mov x0, x1 c: d2800401 mov x1, #0x40 // #64 10: 910003fd mov x29, sp 14: 93407c42 sxtw x2, w2 18: 94000000 bl 0 <find_next_bit> 1c: a8c17bfd ldp x29, x30, [sp], #16 20: d65f03c0 ret 24: d503201f nop
After applying this patch:
0000000000000140 <cpumask_next>: 140: 11000400 add w0, w0, #0x1 144: 93407c00 sxtw x0, w0 148: f100fc1f cmp x0, #0x3f 14c: 54000168 b.hi 178 <cpumask_next+0x38> // b.pmore 150: f9400023 ldr x3, [x1] 154: 92800001 mov x1, #0xffffffffffffffff // #-1 158: 9ac02020 lsl x0, x1, x0 15c: 52800802 mov w2, #0x40 // #64 160: 8a030001 and x1, x0, x3 164: dac00020 rbit x0, x1 168: f100003f cmp x1, #0x0 16c: dac01000 clz x0, x0 170: 1a800040 csel w0, w2, w0, eq // eq = none 174: d65f03c0 ret 178: 52800800 mov w0, #0x40 // #64 17c: d65f03c0 ret
find_next_bit() call is replaced with 6 instructions. find_next_bit() itself is 41 instructions plus function call overhead.
Despite inlining, the scripts/bloat-o-meter report smaller .text size after applying the series:
add/remove: 11/9 grow/shrink: 233/176 up/down: 5780/-6768 (-988)
--- include/asm-generic/bitops/find.h | 30 ++++++++++++++++++++++++++++++ include/asm-generic/bitops/le.h | 21 +++++++++++++++++++++ 2 files changed, 51 insertions(+)
include/asm-generic/bitops/find.h +30 -0
@@ -20,6 +20,16 @@ static inlineunsigned long find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (small_const_nbits (size)) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); }#endif
@@ -40,6 +50,16 @@ unsigned long find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long offset) { + if (small_const_nbits(size)) { + unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr1 & *addr2 &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); }#endif
@@ -58,6 +78,16 @@ static inlineunsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (small_const_nbits (size)) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); }#endif
include/asm-generic/bitops/le.h +21 -0
@@ -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_nbits (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,1 ); }#endif
@@ -46,6 +57,16 @@ static inlineunsigned long find_next_bit_le (const void *addr,unsigned long size,unsigned long offset) { +if (small_const_nbits (size)) { +unsigned long val = *(const unsigned long *)addr; + +if (unlikely (offset >= size)) +return size; + + val =swab (val) &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,1 ); }#endif
Signature · 1 line
2.25.1
Yury Norov
maintainerPATCH v4 11/13 lib: add fast path for find_first_*_bit() and find_last_bit()
In reply to Yury NorovSimilarly to bitmap functions, users would benefit if we'll handle a case of small-size bitmaps that fit into a single word.
While here, move the find_last_bit() declaration to bitops/find.h where other find_*_bit() functions sit.
--- include/asm-generic/bitops/find.h | 50 ++++++++++++++++++++++++++++--- include/linux/bitops.h | 12 -------- lib/find_bit.c | 12 ++++---- 3 files changed, 52 insertions(+), 22 deletions(-)
include/asm-generic/bitops/find.h +46 -4
@@ -5,6 +5,9 @@extern unsigned long _find_next_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long nbits,unsigned long start,unsigned long invert,unsigned long le); +extern unsigned long _find_first_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_last_bit (const unsigned long *addr,unsigned long size);#ifndef find_next_bit/**
@@ -102,8 +105,17 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,* Returns the bit number of the first set bit. * If no bits are set, returns @size. */ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr &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_nbits (size)) { +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_nbits (size)) { +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,
Signature · 1 line
2.25.1
Re: [PATCH 11/13] lib: add fast path for find_first_*_bit() and find_last_bit()
Quoted 30 lines · Yury Norov
Similarly to bitmap functions, users would benefit if we'll handle a case of small-size bitmaps that fit into a single word.
While here, move the
find_last_bit()declaration tobitops/find.hwhere other find_*_bit() functions sit.Signed-off-by Yury Norov <[email protected]>--- include/asm-generic/bitops/find.h | 50 ++++++++++++++++++++++++++++--- include/linux/bitops.h | 12 -------- lib/find_bit.c | 12 ++++---- 3 files changed, 52 insertions(+), 22 deletions(-)include/asm-generic/bitops/find.h +3
-0@@ -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.
include/asm-generic/bitops/find.h unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, · line 114
Quoted 10 lines
include/asm-generic/bitops/find.h +7
-2*/ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__ffs (val) : size;
This patch results in:
include/asm-generic/bitops/find.h: In function 'find_last_bit':include/asm-generic/bitops/find.h:164:16: error: implicit declaration of function '__fls'; did you mean '__ffs'?
and:
./include/asm-generic/bitops/__fls.h: At top level:./include/asm-generic/bitops/__fls.h:13:38: error: conflicting types for '__fls'
when building scripts/mod/devicetable-offsets.o.
Seen with h8300 builds.
Guenter
Quoted 130 lines
include/asm-generic/bitops/find.h +36
-2+ } + +return _find_first_bit (addr, size); +}/** * find_first_zero_bit - find the first cleared bit in a memory region @@ -113,8 +125,17 @@ extern unsigned long find_first_bit(const unsigned long *addr,* Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ -extern unsigned long find_first_zero_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr | ~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_nbits (size)) { +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,
Yury Norov
maintainerRe: [PATCH 11/13] lib: add fast path for find_first_*_bit() and find_last_bit()
Quoted 49 lines · Guenter Roeck
Quoted 30 lines · Yury Norov
Similarly to bitmap functions, users would benefit if we'll handle a case of small-size bitmaps that fit into a single word.
While here, move the
find_last_bit()declaration tobitops/find.hwhere other find_*_bit() functions sit.Signed-off-by Yury Norov <[email protected]>--- include/asm-generic/bitops/find.h | 50 ++++++++++++++++++++++++++++--- include/linux/bitops.h | 12 -------- lib/find_bit.c | 12 ++++---- 3 files changed, 52 insertions(+), 22 deletions(-)include/asm-generic/bitops/find.h +3
-0@@ -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. include/asm-generic/bitops/find.h unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, · line 114
Quoted 10 lines
include/asm-generic/bitops/find.h +7
-2*/ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__ffs (val) : size;This patch results in:
include/asm-generic/bitops/find.h: In function 'find_last_bit':include/asm-generic/bitops/find.h:164:16: error: implicit declaration of function '__fls'; did you mean '__ffs'?and:
Quoted 8 lines
./include/asm-generic/bitops/__fls.h: At top level:./include/asm-generic/bitops/__fls.h:13:38: error: conflicting types for '__fls'when building
scripts/mod/devicetable-offsets.o.Seen with h8300 builds.
Guenter
The patch is here:
https://lkml.org/lkml/2021/4/1/1184
Yury
Yury Norov
maintainerPATCH v4 12/13 tools: sync lib/find_bit implementation
In reply to Yury NorovAdd fast paths to find_*_bit() functions as per kernel implementation.
--- tools/include/asm-generic/bitops/find.h | 58 +++++++++++++++++++++++-- tools/lib/find_bit.c | 4 +- 2 files changed, 57 insertions(+), 5 deletions(-)
tools/include/asm-generic/bitops/find.h +55 -3
@@ -5,6 +5,9 @@extern unsigned long _find_next_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long nbits,unsigned long start,unsigned long invert,unsigned long le); +extern unsigned long _find_first_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_first_zero_bit (const unsigned long *addr,unsigned long size); +extern unsigned long _find_last_bit (const unsigned long *addr,unsigned long size);#ifndef find_next_bit/**
@@ -20,6 +23,16 @@ static inlineunsigned long find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (small_const_nbits (size)) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr,NULL , size, offset,0UL ,0 ); }#endif
@@ -40,6 +53,16 @@ unsigned long find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long offset) { + if (small_const_nbits(size)) { + unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr1 & *addr2 &GENMASK (size -1 , offset); +return val ?__ffs (val) : size; + } +return _find_next_bit (addr1, addr2, size, offset,0UL ,0 ); }#endif
@@ -58,6 +81,16 @@ static inlineunsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { +if (small_const_nbits (size)) { +unsigned long val; + +if (unlikely (offset >= size)) +return size; + + val = *addr | ~GENMASK (size -1 , offset); +return val == ~0UL ? size :ffz (val); + } +return _find_next_bit (addr,NULL , size, offset, ~0UL ,0 ); }#endif
@@ -72,8 +105,17 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,* Returns the bit number of the first set bit. * If no bits are set, returns @size. */ -extern unsigned long find_first_bit (const unsigned long *addr, -unsigned long size); +static inline +unsigned long find_first_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr &BITS_FIRST (size -1 ); + +return val ?__ffs (val) : size; + } + +return _find_first_bit (addr, size); +}#endif /* find_first_bit */
@@ -87,7 +129,17 @@ extern unsigned long find_first_bit(const unsigned long *addr,* Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ -unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size); +static inline +unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) +{ +if (small_const_nbits (size)) { +unsigned long val = *addr | ~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
Yury Norov
maintainerPATCH v4 13/13 MAINTAINERS: Add entry for the bitmap API
In reply to Yury NorovAdd myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of lib/find_bit and an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.
--- MAINTAINERS | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
MAINTAINERS +16 -0
@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rst F: fs/bfs/ F: include/uapi/linux/bfs_fs.h +BITMAP API +M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.c +F: lib/find_find_bit_benchmark.c +F: lib/test_bitmap.c +F: tools/include/asm-generic/bitops/find.h +F: tools/include/linux/bitmap.h +F: tools/lib/bitmap.c +F: tools/lib/find_bit.c + BLINKM RGB LED DRIVER M: Jan-Simon Moeller <[email protected]> S: Maintained
Signature · 1 line
2.25.1
Re: [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API
Quoted 22 lines · Yury Norov
Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of
lib/find_bitand an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.Signed-off-by Yury Norov <[email protected]>Acked-by Andy Shevchenko <[email protected]>Acked-by Rasmus Villemoes <[email protected]>--- MAINTAINERS | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)MAINTAINERS +1
-0@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rst F: fs/bfs/ F: include/uapi/linux/bfs_fs.h +BITMAP API
MAINTAINERS F: Documentation/filesystems/bfs.rst · line 3164
Quoted 10 lines
MAINTAINERS +9
-0+M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.c +F: lib/find_find_bit_benchmark.c
Does this file exist?
I guess checkpatch.pl nowadays has a MAINTAINER data base validation.
Quoted 12 lines
MAINTAINERS +6
-0+F: lib/test_bitmap.c +F: tools/include/asm-generic/bitops/find.h +F: tools/include/linux/bitmap.h +F: tools/lib/bitmap.c +F: tools/lib/find_bit.c + BLINKM RGB LED DRIVER M: Jan-Simon Moeller <[email protected]>S: Maintained
Signature · 1 line
2.25.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API
[CC Andy Whitcroft, Joe Perches, Dwaipayan Ray, Lukas Bulwahn]
Quoted 32 lines · Andy Shevchenko
Quoted 30 lines · Yury Norov
Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of
lib/find_bitand an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.Signed-off-by Yury Norov <[email protected]>Acked-by Andy Shevchenko <[email protected]>Acked-by Rasmus Villemoes <[email protected]>--- MAINTAINERS | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)MAINTAINERS +9
-0@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rst F: fs/bfs/ F: include/uapi/linux/bfs_fs.h +BITMAP API +M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.c
Quoted 4 lines
MAINTAINERS F: Documentation/filesystems/bfs.rst · line 3163
Quoted 1 line
MAINTAINERS +1
-0+F: lib/find_find_bit_benchmark.cDoes this file exist?
I guess checkpatch.pl nowadays has a MAINTAINER data base validation.
No lib/find_find_bit_benchmark.c doesn't exist. It's a typo, it should be lib/find_bit_benchmark.c. Checkpatch doesn't warn:
yury:linux$ scripts/checkpatch.pl 0013-MAINTAINERS-Add-entry-for-the-bitmap-API.patch
total: 0 errors, 0 warnings, 22 lines checked
Quoted 17 lines
Quoted 12 lines
MAINTAINERS +6
-0+F: lib/test_bitmap.c +F: tools/include/asm-generic/bitops/find.h +F: tools/include/linux/bitmap.h +F: tools/lib/bitmap.c +F: tools/lib/find_bit.c + BLINKM RGB LED DRIVER M: Jan-Simon Moeller <[email protected]> S: MaintainedSignature · 1 line
2.25.1Signature · 2 lines
With Best Regards, Andy Shevchenko
Re: [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API
Quoted 38 lines · Yury Norov
[CC Andy Whitcroft, Joe Perches, Dwaipayan Ray, Lukas Bulwahn]
Quoted 35 lines · Andy Shevchenko
Quoted 33 lines · Yury Norov
Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of
lib/find_bitand an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.Signed-off-by Yury Norov <[email protected]>Acked-by Andy Shevchenko <[email protected]>Acked-by Rasmus Villemoes <[email protected]>---
MAINTAINERS | 16 ++++++++++++++++1 file changed, 16 insertions(+)MAINTAINERS +0
-0@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rstF:
fs/bfs/
F:include/uapi/linux/bfs_fs.hMAINTAINERS +10
-0+BITMAP API +M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.c +F: lib/find_find_bit_benchmark.c
Quoted 8 lines
Quoted 2 lines
Does this file exist?
I guess checkpatch.pl nowadays has a MAINTAINER data base validation.No
lib/find_find_bit_benchmark.cdoesn't exist. It's a typo, it should belib/find_bit_benchmark.c. Checkpatch doesn't warn:yury:linux$
scripts/checkpatch.pl0013-MAINTAINERS-Add-entry-for-the-bitmap-API.patch
total: 0 errors, 0 warnings, 22 lines checked
checkpatch does not validate filenames for each patch.
checkpatch does have a --self-test=patterns capability that does validate file accessibility.
Re: [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API
Quoted 46 lines · Joe Perches
Quoted 44 lines · Yury Norov
[CC Andy Whitcroft, Joe Perches, Dwaipayan Ray, Lukas Bulwahn]
Quoted 33 lines · Andy Shevchenko
Quoted 31 lines · Yury Norov
Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of
lib/find_bitand an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.Signed-off-by Yury Norov <[email protected]>Acked-by Andy Shevchenko <[email protected]>Acked-by Rasmus Villemoes <[email protected]>--- MAINTAINERS | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)MAINTAINERS +9
-0@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rst F: fs/bfs/ F: include/uapi/linux/bfs_fs.h +BITMAP API +M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.cQuoted 4 lines
MAINTAINERS F: Documentation/filesystems/bfs.rst · line 3163
Quoted 1 line
MAINTAINERS +1
-0+F: lib/find_find_bit_benchmark.cDoes this file exist?
I guess checkpatch.pl nowadays has a MAINTAINER data base validation.No
lib/find_find_bit_benchmark.cdoesn't exist. It's a typo, it should belib/find_bit_benchmark.c. Checkpatch doesn't warn:
Quoted 7 lines
Quoted 2 lines
yury:linux$
scripts/checkpatch.pl0013-MAINTAINERS-Add-entry-for-the-bitmap-API.patch
total: 0 errors, 0 warnings, 22 lines checkedcheckpatch does not validate filenames for each patch.
checkpatch does have a --self-test=patterns capability that does validate file accessibility.
Joe meant: get_maintainers does have a --self-test=patterns capability that does validate file accessibility.
You can run that before patch submission; otherwise, I run that script on linux-next once a week and send out correction patches as far as my "spare" time allows to do so.
Lukas
Yury Norov
maintainerRe: [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API
Quoted 55 lines · Lukas Bulwahn
Quoted 46 lines · Joe Perches
Quoted 44 lines · Yury Norov
[CC Andy Whitcroft, Joe Perches, Dwaipayan Ray, Lukas Bulwahn]
Quoted 33 lines · Andy Shevchenko
Quoted 31 lines · Yury Norov
Add myself as maintainer for bitmap API and Andy and Rasmus as reviewers.
I'm an author of current implementation of
lib/find_bitand an active contributor to lib/bitmap. It was spotted that there's no maintainer for bitmap API. I'm willing to maintain it.Signed-off-by Yury Norov <[email protected]>Acked-by Andy Shevchenko <[email protected]>Acked-by Rasmus Villemoes <[email protected]>--- MAINTAINERS | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)MAINTAINERS +9
-0@@ -3151,6 +3151,22 @@ F: Documentation/filesystems/bfs.rst F: fs/bfs/ F: include/uapi/linux/bfs_fs.h +BITMAP API +M: Yury Norov <[email protected]> +R: Andy Shevchenko <[email protected]> +R: Rasmus Villemoes <[email protected]> +S: Maintained +F: include/asm-generic/bitops/find.h +F: include/linux/bitmap.h +F: lib/bitmap.c +F: lib/find_bit.cQuoted 4 lines
MAINTAINERS F: Documentation/filesystems/bfs.rst · line 3163
Quoted 1 line
MAINTAINERS +1
-0+F: lib/find_find_bit_benchmark.cDoes this file exist?
I guess checkpatch.pl nowadays has a MAINTAINER data base validation.No
lib/find_find_bit_benchmark.cdoesn't exist. It's a typo, it should belib/find_bit_benchmark.c. Checkpatch doesn't warn:Quoted 7 lines
Quoted 2 lines
yury:linux$
scripts/checkpatch.pl0013-MAINTAINERS-Add-entry-for-the-bitmap-API.patch
total: 0 errors, 0 warnings, 22 lines checkedcheckpatch does not validate filenames for each patch.
checkpatch does have a --self-test=patterns capability that does validate file accessibility.
Quoted 6 lines
Joe meant:
get_maintainersdoes have a --self-test=patterns capability that does validate file accessibility.You can run that before patch submission; otherwise, I run that script on linux-next once a week and send out correction patches as far as my "spare" time allows to do so.
Thanks for the hint. I see it's able to detect the issue.