From e041e0ac53dd52d2d201aa87edc3adaca1085299 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Thu, 28 Apr 2022 13:51:12 -0700 Subject: lib/bitmap: extend comment for bitmap_(from,to)_arr32() On LE systems bitmaps are naturally ordered, therefore we can potentially use bitmap_copy routines when converting from 32-bit arrays, even if host system is 64-bit. But it may lead to out-of-bond access due to unsafe typecast, and the bitmap_(from,to)_arr32 comment doesn't explain that clearly CC: Alexander Gordeev CC: Andy Shevchenko CC: Christian Borntraeger CC: Claudio Imbrenda CC: David Hildenbrand CC: Heiko Carstens CC: Janosch Frank CC: Rasmus Villemoes CC: Sven Schnelle CC: Vasily Gorbik Signed-off-by: Yury Norov --- include/linux/bitmap.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 7dba0847510c..afcf7b8dddd1 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -264,8 +264,12 @@ static inline void bitmap_copy_clear_tail(unsigned long *dst, } /* - * On 32-bit systems bitmaps are represented as u32 arrays internally, and - * therefore conversion is not needed when copying data from/to arrays of u32. + * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64 + * machines the order of hi and lo parts of numbers match the bitmap structure. + * In both cases conversion is not needed when copying data from/to arrays of + * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead + * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit + * architectures are not using bitmap_copy_clear_tail(). */ #if BITS_PER_LONG == 64 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, -- cgit v1.2.3 From 0a97953fd2210d0ac8eb5c76f8bd08fb53b6d3d6 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Thu, 28 Apr 2022 13:51:13 -0700 Subject: lib: add bitmap_{from,to}_arr64 Manipulating 64-bit arrays with bitmap functions is potentially dangerous because on 32-bit BE machines the order of halfwords doesn't match. Another issue is that compiler may throw a warning about out-of-boundary access. This patch adds bitmap_{from,to}_arr64 functions in addition to existing bitmap_{from,to}_arr32. CC: Alexander Gordeev CC: Andy Shevchenko CC: Christian Borntraeger CC: Claudio Imbrenda CC: David Hildenbrand CC: Heiko Carstens CC: Janosch Frank CC: Rasmus Villemoes CC: Sven Schnelle CC: Vasily Gorbik Signed-off-by: Yury Norov --- include/linux/bitmap.h | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index afcf7b8dddd1..71147b7d721b 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -72,6 +72,8 @@ struct device; * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst + * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst + * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst * bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start * @@ -285,6 +287,22 @@ void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, (const unsigned long *) (bitmap), (nbits)) #endif +/* + * On 64-bit systems bitmaps are represented as u64 arrays internally. On LE32 + * machines the order of hi and lo parts of numbers match the bitmap structure. + * In both cases conversion is not needed when copying data from/to arrays of + * u64. + */ +#if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN) +void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits); +void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits); +#else +#define bitmap_from_arr64(bitmap, buf, nbits) \ + bitmap_copy_clear_tail((unsigned long *)(bitmap), (const unsigned long *)(buf), (nbits)) +#define bitmap_to_arr64(buf, bitmap, nbits) \ + bitmap_copy_clear_tail((unsigned long *)(buf), (const unsigned long *)(bitmap), (nbits)) +#endif + static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { @@ -518,10 +536,7 @@ static inline void bitmap_next_set_region(unsigned long *bitmap, */ static inline void bitmap_from_u64(unsigned long *dst, u64 mask) { - dst[0] = mask & ULONG_MAX; - - if (sizeof(mask) > sizeof(unsigned long)) - dst[1] = mask >> 32; + bitmap_from_arr64(dst, &mask, 64); } /** -- cgit v1.2.3 From 005f17007f47495dbbb659aa5db7e581065d16e7 Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Wed, 18 May 2022 13:52:22 -0700 Subject: bitmap: Fix return values to be unsigned Both nodemask and bitmap routines had mixed return values that provided potentially signed return values that could never happen. This was leading to the compiler getting confusing about the range of possible return values (it was thinking things could be negative where they could not be). In preparation for fixing nodemask, fix all the bitmap routines that should be returning unsigned (or bool) values. Cc: Yury Norov Cc: Rasmus Villemoes Cc: Christophe de Dinechin Cc: Alexey Dobriyan Cc: Andy Shevchenko Cc: Andrew Morton Cc: Zhen Lei Signed-off-by: Kees Cook Signed-off-by: Yury Norov --- include/linux/bitmap.h | 25 +++++++++++++------------ 1 file changed, 13 insertions(+), 12 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 71147b7d721b..2e6cd5681040 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -134,8 +134,8 @@ unsigned long *devm_bitmap_zalloc(struct device *dev, * lib/bitmap.c provides these functions: */ -int __bitmap_equal(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int nbits); +bool __bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int nbits); bool __pure __bitmap_or_equal(const unsigned long *src1, const unsigned long *src2, const unsigned long *src3, @@ -159,10 +159,10 @@ int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, void __bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, const unsigned long *mask, unsigned int nbits); -int __bitmap_intersects(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int nbits); -int __bitmap_subset(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int nbits); +bool __bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int nbits); +bool __bitmap_subset(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int nbits); int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); @@ -353,8 +353,8 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr #endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) -static inline int bitmap_equal(const unsigned long *src1, - const unsigned long *src2, unsigned int nbits) +static inline bool 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)); @@ -384,8 +384,9 @@ static inline bool bitmap_or_equal(const unsigned long *src1, return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits)); } -static inline int bitmap_intersects(const unsigned long *src1, - const unsigned long *src2, unsigned int nbits) +static inline bool 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; @@ -393,8 +394,8 @@ static inline int bitmap_intersects(const unsigned long *src1, return __bitmap_intersects(src1, src2, nbits); } -static inline int bitmap_subset(const unsigned long *src1, - const unsigned long *src2, unsigned int nbits) +static inline bool 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)); -- cgit v1.2.3 From ba1afa676d0babf99e99f5415db43fdd7ecef104 Mon Sep 17 00:00:00 2001 From: Qu Wenruo Date: Fri, 24 Jun 2022 17:31:47 +0800 Subject: lib: bitmap: fix the duplicated comments on bitmap_to_arr64() Thanks to the recent commit 0a97953fd221 ("lib: add bitmap_{from,to}_arr64") now we can directly convert a U64 value into a bitmap and vice verse. However when checking the header there is duplicated helper for bitmap_to_arr64(), but no bitmap_from_arr64(). Just fix the copy-n-paste error. Signed-off-by: Qu Wenruo Signed-off-by: Yury Norov --- include/linux/bitmap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 2e6cd5681040..f091a1664bf1 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -71,9 +71,9 @@ struct device; * bitmap_release_region(bitmap, pos, order) Free specified bit region * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst + * bitmap_from_arr64(dst, buf, nbits) Copy nbits from u64[] buf to dst * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst - * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst * bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start * -- cgit v1.2.3 From 3e7e5baaaba78075a7f3a57432609e363bf2a486 Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Fri, 24 Jun 2022 14:13:12 +0200 Subject: bitmap: don't assume compiler evaluates small mem*() builtins calls Intel kernel bot triggered the build bug on ARC architecture that in fact is as follows: DECLARE_BITMAP(bitmap, BITS_PER_LONG); bitmap_clear(bitmap, 0, BITS_PER_LONG); BUILD_BUG_ON(!__builtin_constant_p(*bitmap)); which can be expanded to: unsigned long bitmap[1]; memset(bitmap, 0, sizeof(*bitmap)); BUILD_BUG_ON(!__builtin_constant_p(*bitmap)); In most cases, a compiler is able to expand small/simple mem*() calls to simple assignments or bitops, in this case that would mean: unsigned long bitmap[1] = { 0 }; BUILD_BUG_ON(!__builtin_constant_p(*bitmap)); and on most architectures this works, but not on ARC, despite having -O3 for every build. So, to make this work, in case when the last bit to modify is still within the first long (small_const_nbits()), just use plain assignments for the rest of bitmap_*() functions which still use mem*(), but didn't receive such compile-time optimizations yet. This doesn't have the same coverage as compilers provide, but at least something to start: text: add/remove: 3/7 grow/shrink: 43/78 up/down: 1848/-3370 (-1546) data: add/remove: 1/11 grow/shrink: 0/8 up/down: 4/-356 (-352) notably cpumask_*() family when NR_CPUS <= BITS_PER_LONG: netif_get_num_default_rss_queues 38 4 -34 cpumask_copy 90 - -90 cpumask_clear 146 - -146 and the abovementioned assertion started passing. Signed-off-by: Alexander Lobakin Signed-off-by: Yury Norov --- include/linux/bitmap.h | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index f091a1664bf1..c91638e507f2 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -238,20 +238,32 @@ extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp, static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); - memset(dst, 0, len); + + if (small_const_nbits(nbits)) + *dst = 0; + else + memset(dst, 0, len); } static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); - memset(dst, 0xff, len); + + if (small_const_nbits(nbits)) + *dst = ~0UL; + else + memset(dst, 0xff, len); } static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, unsigned int nbits) { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); - memcpy(dst, src, len); + + if (small_const_nbits(nbits)) + *dst = *src; + else + memcpy(dst, src, len); } /* @@ -431,6 +443,8 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start, { if (__builtin_constant_p(nbits) && nbits == 1) __set_bit(start, map); + else if (small_const_nbits(start + nbits)) + *map |= GENMASK(start + nbits - 1, start); else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && @@ -445,6 +459,8 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start, { if (__builtin_constant_p(nbits) && nbits == 1) __clear_bit(start, map); + else if (small_const_nbits(start + nbits)) + *map &= ~GENMASK(start + nbits - 1, start); else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && -- cgit v1.2.3 From e2863a78593d638d3924a6f67900c4820034f349 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:24 -0700 Subject: lib/bitmap: change return types to bool where appropriate Some bitmap functions return boolean results in int variables. Fix it by changing return types to bool. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index c91638e507f2..e1a438bdda52 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -148,13 +148,13 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, unsigned int shift, unsigned int nbits); void bitmap_cut(unsigned long *dst, const unsigned long *src, unsigned int first, unsigned int cut, unsigned int nbits); -int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, +bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); -int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, +bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); void __bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, @@ -315,7 +315,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 int bitmap_and(unsigned long *dst, const unsigned long *src1, +static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) @@ -341,7 +341,7 @@ static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, __bitmap_xor(dst, src1, src2, nbits); } -static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, +static inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) { if (small_const_nbits(nbits)) -- cgit v1.2.3 From 4dea97f8636d0514befc9fc5cf342b351b7d0e20 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:25 -0700 Subject: lib/bitmap: change type of bitmap_weight to unsigned long bitmap_weight() doesn't return negative values, so change it's type to unsigned long. It may help compiler to generate better code and catch bugs. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index e1a438bdda52..035d4ac66641 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -163,7 +163,7 @@ bool __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); bool __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); -int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); +unsigned long __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); @@ -431,7 +431,8 @@ static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) return find_first_zero_bit(src, nbits) == nbits; } -static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits) +static __always_inline +unsigned long bitmap_weight(const unsigned long *src, unsigned int nbits) { if (small_const_nbits(nbits)) return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); -- cgit v1.2.3 From 24291caf8447f6fc060c8d00136bdc30ee207f38 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Sat, 17 Sep 2022 20:07:12 -0700 Subject: lib/bitmap: add bitmap_weight_and() The function calculates Hamming weight of (bitmap1 & bitmap2). Now we have to do like this: tmp = bitmap_alloc(nbits); bitmap_and(tmp, map1, map2, nbits); weight = bitmap_weight(tmp, nbits); bitmap_free(tmp); This requires additional memory, adds pressure on alloc subsystem, and way less cache-friendly than just: weight = bitmap_weight_and(map1, map2, nbits); The following patches apply it for cpumask functions. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index f65410a49fda..b2aef45af0db 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -51,6 +51,7 @@ struct device; * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits + * bitmap_weight_and(src1, src2, nbits) Hamming Weight of and'ed bitmap * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area @@ -164,6 +165,8 @@ bool __bitmap_intersects(const unsigned long *bitmap1, bool __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); +unsigned int __bitmap_weight_and(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int nbits); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); @@ -439,6 +442,15 @@ unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits) return __bitmap_weight(src, nbits); } +static __always_inline +unsigned long bitmap_weight_and(const unsigned long *src1, + const unsigned long *src2, unsigned int nbits) +{ + if (small_const_nbits(nbits)) + return hweight_long(*src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)); + return __bitmap_weight_and(src1, src2, nbits); +} + static __always_inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) { -- cgit v1.2.3 From 97848c10f9f8a8ce4296b149d06cab424eba05b3 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Sat, 17 Sep 2022 20:07:15 -0700 Subject: lib/bitmap: remove bitmap_ord_to_pos Now that we have find_nth_bit(), we can drop bitmap_ord_to_pos(). Signed-off-by: Yury Norov --- include/linux/bitmap.h | 1 - 1 file changed, 1 deletion(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index b2aef45af0db..7d6d73b78147 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -225,7 +225,6 @@ void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int n #else #define bitmap_copy_le bitmap_copy #endif -unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits); int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, int nmaskbits); -- cgit v1.2.3