bitmap: optimize small_const path for
Subsystems (3)
Yury Norov
maintainercover bitmap: optimize small_const path for
Make all inline bitmap functions __always_inline to ensure that small_const optimization is always possible, and improve on it for find_next_bit() and friends.
Yury Norov (3):
bitmap: switch from inline to __always_inline
bitmap: improve small_const case for find_next() functions
bitmap: add tests for find_next_bit()
include/asm-generic/bitsperlong.h | 12 +++ include/linux/bitmap.h | 46 +++++----- include/linux/cpumask.h | 144 +++++++++++++++--------------- include/linux/find.h | 85 ++++++++---------- include/linux/nodemask.h | 86 +++++++++--------- lib/test_bitmap.c | 23 ++++- 6 files changed, 208 insertions(+), 188 deletions(-)
Signature · 1 line
2.34.1
Yury Norov
maintainerPATCH 1/3 bitmap: switch from inline to __always_inline
'inline' keyword is only a recommendation for compiler. If it decides to not inline bitmap, find_bit, cpumask or nodemask functions, the whole small_const_nbits() machinery doesn't work.
This is how a standard GCC 11.3.0 does for my x86_64 build now. This patch replaces 'inline' directive with unconditional '__always_inline' to make sure that there's always a chance for compile-time optimization. It doesn't change size of kernel image, according to bloat-o-meter.
--- include/linux/bitmap.h | 46 ++++++------- include/linux/cpumask.h | 144 +++++++++++++++++++-------------------- include/linux/find.h | 40 +++++------ include/linux/nodemask.h | 86 +++++++++++------------ 4 files changed, 158 insertions(+), 158 deletions(-)
include/linux/bitmap.h +23 -23
@@ -189,7 +189,7 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,* the bit offset of all zero areas this function finds is multiples of that * power of 2. A @align_mask of 0 means no alignment is required. */ -static inline unsigned long +static __always_inline unsigned long bitmap_find_next_zero_area(unsigned long *map, unsigned long size, unsigned long start,
@@ -237,7 +237,7 @@ extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,#define BITMAP_FIRST_WORD_MASK (start) (~0UL << ((start) & (BITS_PER_LONG - 1)))#define BITMAP_LAST_WORD_MASK (nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) -static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) +static __always_inline void bitmap_zero(unsigned long *dst, unsigned int nbits) {unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long );
@@ -247,7 +247,7 @@ static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)memset (dst,0 , len); } -static inline void bitmap_fill (unsigned long *dst,unsigned int nbits) +static __always_inline void bitmap_fill(unsigned long *dst, unsigned int nbits) {unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long );
@@ -257,7 +257,7 @@ static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)memset (dst,0xff , len); } -static inline void bitmap_copy (unsigned long *dst,const unsigned long *src, +static __always_inline void bitmap_copy(unsigned long *dst, const unsigned long *src,unsigned int nbits) {unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long );
@@ -271,7 +271,7 @@ static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,/* * Copy bitmap and clear tail bits in last word. */ -static inline void bitmap_copy_clear_tail (unsigned long *dst, +static __always_inline void bitmap_copy_clear_tail(unsigned long *dst,const unsigned long *src,unsigned int nbits) {bitmap_copy (dst, src, nbits);
@@ -317,7 +317,7 @@ void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits); bitmap_copy_clear_tail((unsigned long *)(buf), (const unsigned long *)(bitmap), (nbits))#endif -static inline bool bitmap_and (unsigned long *dst,const unsigned long *src1, +static __always_inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -325,7 +325,7 @@ static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,return __bitmap_and (dst, src1, src2, nbits); } -static inline void bitmap_or (unsigned long *dst,const unsigned long *src1, +static __always_inline void bitmap_or(unsigned long *dst, const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -334,7 +334,7 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,__bitmap_or (dst, src1, src2, nbits); } -static inline void bitmap_xor (unsigned long *dst,const unsigned long *src1, +static __always_inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -343,7 +343,7 @@ static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,__bitmap_xor (dst, src1, src2, nbits); } -static inline bool bitmap_andnot (unsigned long *dst,const unsigned long *src1, +static __always_inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -351,7 +351,7 @@ static inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1,return __bitmap_andnot (dst, src1, src2, nbits); } -static inline void bitmap_complement (unsigned long *dst,const unsigned long *src, +static __always_inline void bitmap_complement(unsigned long *dst, const unsigned long *src,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -367,7 +367,7 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr#endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) -static inline bool bitmap_equal (const unsigned long *src1, +static __always_inline bool bitmap_equal(const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -387,7 +387,7 @@ static inline bool bitmap_equal(const unsigned long *src1,* * Returns: True if (*@src1 | *@src2) == *@src3, false otherwise */ -static inline bool bitmap_or_equal (const unsigned long *src1, +static __always_inline bool bitmap_or_equal(const unsigned long *src1,const unsigned long *src2,const unsigned long *src3,unsigned int nbits)
@@ -398,7 +398,7 @@ static inline bool bitmap_or_equal(const unsigned long *src1,return !(((*src1 | *src2) ^ *src3) &BITMAP_LAST_WORD_MASK (nbits)); } -static inline bool bitmap_intersects (const unsigned long *src1, +static __always_inline bool bitmap_intersects(const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {
@@ -408,7 +408,7 @@ static inline bool bitmap_intersects(const unsigned long *src1,return __bitmap_intersects (src1, src2, nbits); } -static inline bool bitmap_subset (const unsigned long *src1, +static __always_inline bool bitmap_subset(const unsigned long *src1,const unsigned long *src2,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -417,7 +417,7 @@ static inline bool bitmap_subset(const unsigned long *src1,return __bitmap_subset (src1, src2, nbits); } -static inline bool bitmap_empty (const unsigned long *src,unsigned nbits) +static __always_inline bool bitmap_empty(const unsigned long *src, unsigned int nbits) {if (small_const_nbits (nbits))return ! (*src &BITMAP_LAST_WORD_MASK (nbits));
@@ -425,7 +425,7 @@ static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)return find_first_bit (src, nbits) == nbits; } -static inline bool bitmap_full (const unsigned long *src,unsigned int nbits) +static __always_inline bool bitmap_full(const unsigned long *src, unsigned int nbits) {if (small_const_nbits (nbits))return ! (~(*src) &BITMAP_LAST_WORD_MASK (nbits));
@@ -482,7 +482,7 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,__bitmap_clear (map, start, nbits); } -static inline void bitmap_shift_right (unsigned long *dst,const unsigned long *src, +static __always_inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,unsigned int shift,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -491,7 +491,7 @@ static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *s__bitmap_shift_right (dst, src, shift, nbits); } -static inline void bitmap_shift_left (unsigned long *dst,const unsigned long *src, +static __always_inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,unsigned int shift,unsigned int nbits) {if (small_const_nbits (nbits))
@@ -500,7 +500,7 @@ static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *sr__bitmap_shift_left (dst, src, shift, nbits); } -static inline void bitmap_replace(unsigned long *dst, +static __always_inline void bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, const unsigned long *mask,
@@ -512,7 +512,7 @@ static inline void bitmap_replace(unsigned long *dst,__bitmap_replace (dst, old, new, mask, nbits); } -static inline void bitmap_next_set_region (unsigned long *bitmap, +static __always_inline void bitmap_next_set_region(unsigned long *bitmap,unsigned int *rs,unsigned int *re,unsigned int end) {
@@ -563,7 +563,7 @@ static inline void bitmap_next_set_region(unsigned long *bitmap,* That is ``(u32 *)(&val)[0]`` gets the upper 32 bits, * but we expect the lower 32-bits of u64. */ -static inline void bitmap_from_u64 (unsigned long *dst,u64 mask) +static __always_inline void bitmap_from_u64(unsigned long *dst, u64 mask) {bitmap_from_arr64 (dst, &mask,64 ); }
@@ -576,7 +576,7 @@ static inline void bitmap_from_u64(unsigned long *dst, u64 mask)* Returns the 8-bit value located at the @start bit offset within the @src * memory region. */ -static inline unsigned long bitmap_get_value8 (const unsigned long *map, +static __always_inline unsigned long bitmap_get_value8 (const unsigned long *map,unsigned long start) {const size_t index =BIT_WORD (start);
@@ -591,7 +591,7 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map,* @value: the 8-bit value; values wider than 8 bits may clobber bitmap * @start: bit offset of the 8-bit value; must be a multiple of 8 */ -static inline void bitmap_set_value8 (unsigned long *map,unsigned long value, +static __always_inline void bitmap_set_value8(unsigned long *map, unsigned long value,unsigned long start) {const size_t index =BIT_WORD (start);
include/linux/cpumask.h +72 -72
541 lines not on this page · raw message
include/linux/find.h +20 -20
@@ -45,7 +45,7 @@ unsigned long _find_next_bit_le(const unsigned long *addr, unsigned* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) {
@@ -74,7 +74,7 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_next_and_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size,unsigned long offset)
@@ -105,7 +105,7 @@ unsigned long find_next_and_bit(const unsigned long *addr1,* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_next_andnot_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size,unsigned long offset)
@@ -134,7 +134,7 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,* Returns the bit number of the next zero bit * If no bits are zero, returns @size. */ -static inline +static __always_inline unsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) {
@@ -161,7 +161,7 @@ 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. */ -static inline +static __always_inline unsigned long find_first_bit (const unsigned long *addr,unsigned long size) {if (small_const_nbits (size)) {
@@ -187,7 +187,7 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)* Returns the bit number of the N'th set bit. * If no such, returns @size. */ -static inline +static __always_inline unsigned long find_nth_bit (const unsigned long *addr,unsigned long size,unsigned long n) {if (n >= size)
@@ -212,7 +212,7 @@ unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsign* Returns the bit number of the N'th set bit. * If no such, returns @size. */ -static inline +static __always_inline unsigned long find_nth_and_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size,unsigned long n) {
@@ -239,7 +239,7 @@ unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long ** Returns the bit number of the N'th set bit. * If no such, returns @size. */ -static inline +static __always_inline unsigned long find_nth_andnot_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size,unsigned long n) {
@@ -265,7 +265,7 @@ unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned lon* Returns the bit number for the next set bit * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_first_and_bit (const unsigned long *addr1,const unsigned long *addr2,unsigned long size)
@@ -289,7 +289,7 @@ unsigned long find_first_and_bit(const unsigned long *addr1,* Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ -static inline +static __always_inline unsigned long find_first_zero_bit (const unsigned long *addr,unsigned long size) {if (small_const_nbits (size)) {
@@ -310,7 +310,7 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)* * Returns the bit number of the last set bit, or size. */ -static inline +static __always_inline unsigned long find_last_bit (const unsigned long *addr,unsigned long size) {if (small_const_nbits (size)) {
@@ -333,7 +333,7 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)* Returns the bit number for the next set bit, or first set bit up to @offset * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_next_and_bit_wrap (const unsigned long *addr1,const unsigned long *addr2,unsigned long size,unsigned long offset)
@@ -356,7 +356,7 @@ unsigned long find_next_and_bit_wrap(const unsigned long *addr1,* Returns the bit number for the next set bit, or first set bit up to @offset * If no bits are set, returns @size. */ -static inline +static __always_inline unsigned long find_next_bit_wrap (const unsigned long *addr,unsigned long size,unsigned long offset) {
@@ -373,7 +373,7 @@ unsigned long find_next_bit_wrap(const unsigned long *addr,* Helper for for_each_set_bit_wrap(). Make sure you're doing right thing * before using it alone. */ -static inline +static __always_inline unsigned long __for_each_wrap (const unsigned long *bitmap,unsigned long size,unsigned long start,unsigned long n) {
@@ -414,19 +414,19 @@ extern unsigned long find_next_clump8(unsigned long *clump,#if defined(__LITTLE_ENDIAN) -static inline unsigned long find_next_zero_bit_le (const void *addr, +static __always_inline unsigned long find_next_zero_bit_le (const void *addr,unsigned long size,unsigned long offset) {return find_next_zero_bit (addr, size, offset); } -static inline unsigned long find_next_bit_le (const void *addr, +static __always_inline unsigned long find_next_bit_le (const void *addr,unsigned long size,unsigned long offset) {return find_next_bit (addr, size, offset); } -static inline unsigned long find_first_zero_bit_le (const void *addr, +static __always_inline unsigned long find_first_zero_bit_le (const void *addr,unsigned long size) {return find_first_zero_bit (addr, size);
@@ -435,7 +435,7 @@ static inline unsigned long find_first_zero_bit_le(const void *addr, #elif defined(__BIG_ENDIAN) #ifndef find_next_zero_bit_le -static inline +static __always_inline unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset) {
@@ -454,7 +454,7 @@ unsigned long find_next_zero_bit_le(const void *addr, unsigned#endif #ifndef find_first_zero_bit_le -static inline +static __always_inline unsigned long find_first_zero_bit_le (const void *addr,unsigned long size) {if (small_const_nbits (size)) {
@@ -468,7 +468,7 @@ unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)#endif #ifndef find_next_bit_le -static inline +static __always_inline unsigned long find_next_bit_le (const void *addr,unsigned long size,unsigned long offset) {
include/linux/nodemask.h +43 -43
318 lines not on this page · raw message
Signature · 1 line
2.34.1
Yury Norov
maintainerPATCH 2/3 bitmap: improve small_const case for find_next() functions
In reply to Yury Norovfind_next_bit() and friends use small_const_nbits() to detect possibility of compile-time optimization. It works well for nbits up to BITS_PER_LONG, i.e. for 1-word bitmaps. When nbits belongs to 2nd, 3rd or any other word, small_const_nbits() returns false.
But when both offset and size are within the same word boundary, we still can make a small_const optimization because the whole business is just fetching a single word, and masking head and tail bits if needed.
This patch adds a new small_const_nbits_off() macro doing that. It replaces small_const_nbits() in find_next_bit() functions.
--- include/asm-generic/bitsperlong.h | 12 +++++++++ include/linux/find.h | 45 ++++++++++++------------------- 2 files changed, 29 insertions(+), 28 deletions(-)
include/asm-generic/bitsperlong.h +12 -0
@@ -35,4 +35,16 @@#define small_const_nbits (nbits) \ (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0) +/* +* small_const_nbits_off(nbits, off) is true precisely when it is known at +* compile-time that all bits in range [off, nbits) belong to the same word. +* 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 using the out-of-line functions, so that the inline implementations +* can unconditionally dereference the pointer(s). +*/ +#define small_const_nbits_off (nbits, off) \ + (__builtin_constant_p(nbits) && __builtin_constant_p(off) && (nbits) > 0 && \ + (nbits) > (off) && (off) / BITS_PER_LONG == ((nbits) - 1) / BITS_PER_LONG) +#endif /* __ASM_GENERIC_BITS_PER_LONG */
include/linux/find.h +17 -28
79 lines not on this page · raw message
Signature · 1 line
2.34.1
Yury Norov
maintainerPATCH 3/3 bitmap: add tests for find_next_bit()
In reply to Yury NorovTest out-of-line and inline paths of find_next_bit().
--- lib/test_bitmap.c | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-)
lib/test_bitmap.c +21 -2
@@ -221,7 +221,7 @@ static void __init test_zero_clear(void)expect_eq_pbl ("" , bmap,1024 ); } -static void __init test_find_nth_bit (void ) +static void __init test_find_bit (void ) {unsigned long b, bit, cnt =0 ;DECLARE_BITMAP (bmap,64 *3 );
@@ -236,6 +236,25 @@ static void __init test_find_nth_bit(void)__set_bit (80 , bmap);__set_bit (123 , bmap); +expect_eq_uint (10 ,find_next_bit (bmap,64 *3 ,0 )); +expect_eq_uint (20 ,find_next_bit (bmap,64 *3 ,11 )); +expect_eq_uint (30 ,find_next_bit (bmap,64 *3 ,21 )); +expect_eq_uint (40 ,find_next_bit (bmap,64 *3 ,31 )); +expect_eq_uint (50 ,find_next_bit (bmap,64 *3 ,41 )); +expect_eq_uint (60 ,find_next_bit (bmap,64 *3 ,51 )); +expect_eq_uint (80 ,find_next_bit (bmap,64 *3 ,61 )); +expect_eq_uint (123 ,find_next_bit (bmap,64 *3 ,81 )); + +/* Test small_const_nbits_off() optimization path */ +expect_eq_uint (10 ,find_next_bit (bmap,20 +0 ,0 )); +expect_eq_uint (20 ,find_next_bit (bmap,20 +11 ,11 )); +expect_eq_uint (30 ,find_next_bit (bmap,20 +21 ,21 )); +expect_eq_uint (40 ,find_next_bit (bmap,20 +31 ,31 )); +expect_eq_uint (50 ,find_next_bit (bmap,20 +41 ,41 )); +expect_eq_uint (60 ,find_next_bit (bmap,20 +51 ,51 )); +expect_eq_uint (80 ,find_next_bit (bmap,20 +61 ,61 )); +expect_eq_uint (90 ,find_next_bit (bmap,20 +70 ,81 )); +expect_eq_uint (10 ,find_nth_bit (bmap,64 *3 ,0 ));expect_eq_uint (20 ,find_nth_bit (bmap,64 *3 ,1 ));expect_eq_uint (30 ,find_nth_bit (bmap,64 *3 ,2 ));
@@ -1226,7 +1245,7 @@ static void __init selftest(void)test_bitmap_print_buf ();test_bitmap_const_eval (); -test_find_nth_bit (); +test_find_bit (); test_for_each_set_bit(); test_for_each_set_bit_from(); test_for_each_clear_bit();
Signature · 1 line
2.34.1
Yury Norov
maintainerPing?
Quoted 19 lines · Yury Norov
Make all inline bitmap functions
__always_inlineto ensure thatsmall_constoptimization is always possible, and improve on it forfind_next_bit()and friends.Yury Norov (3):
bitmap: switch from inline to__always_inline
bitmap: improvesmall_constcase forfind_next()functions
bitmap: add tests forfind_next_bit()include/asm-generic/bitsperlong.h | 12 +++ include/linux/bitmap.h | 46 +++++----- include/linux/cpumask.h | 144 +++++++++++++++--------------- include/linux/find.h | 85 ++++++++---------- include/linux/nodemask.h | 86 +++++++++--------- lib/test_bitmap.c | 23 ++++- 6 files changed, 208 insertions(+), 188 deletions(-)Signature · 1 line
2.34.1
Yury Norov
maintainerping again
Quoted 22 lines · Yury Norov
Ping?
Quoted 19 lines · Yury Norov
Make all inline bitmap functions
__always_inlineto ensure thatsmall_constoptimization is always possible, and improve on it forfind_next_bit()and friends.Yury Norov (3):
bitmap: switch from inline to__always_inline
bitmap: improvesmall_constcase forfind_next()functions
bitmap: add tests forfind_next_bit()include/asm-generic/bitsperlong.h | 12 +++ include/linux/bitmap.h | 46 +++++----- include/linux/cpumask.h | 144 +++++++++++++++--------------- include/linux/find.h | 85 ++++++++---------- include/linux/nodemask.h | 86 +++++++++--------- lib/test_bitmap.c | 23 ++++- 6 files changed, 208 insertions(+), 188 deletions(-)Signature · 1 line
2.34.1