From 2699e5143c9b071d68b12b9a86b6312866a6160b Mon Sep 17 00:00:00 2001 From: Randy Dunlap Date: Wed, 23 Mar 2022 16:05:53 -0700 Subject: lib: bitmap: fix many kernel-doc warnings Fix kernel-doc warings in lib/bitmap.c: lib/bitmap.c:498: warning: Function parameter or member 'buf' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'maskp' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'nmaskbits' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'off' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'count' not described in 'bitmap_print_to_buf' lib/bitmap.c:561: warning: contents before sections lib/bitmap.c:606: warning: Function parameter or member 'buf' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'maskp' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'nmaskbits' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'off' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'count' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:819: warning: missing initial short description on line: * bitmap_parselist_user() This still leaves 15 warnings for function return values not described, similar to this one: bitmap.c:890: warning: No description found for return value of 'bitmap_parse' Link: https://lkml.kernel.org/r/20220306065823.5153-1-rdunlap@infradead.org Fixes: 1fae562983ca ("cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask and list") Fixes: 4b060420a596 ("bitmap, irq: add smp_affinity_list interface to /proc/irq") Signed-off-by: Randy Dunlap Cc: Yury Norov Cc: Andy Shevchenko Cc: Rasmus Villemoes Cc: Tian Tao Cc: Mike Travis Cc: Greg Kroah-Hartman Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/bitmap.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 926408883456..0d5c2ece0bcb 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -492,6 +492,11 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); * @list: indicates whether the bitmap must be list * true: print in decimal list format * false: print in hexadecimal bitmask format + * @buf: buffer into which string is placed + * @maskp: pointer to bitmap to convert + * @nmaskbits: size of bitmap, in bits + * @off: in the string from which we are copying, We copy to @buf + * @count: the maximum number of bytes to print */ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp, int nmaskbits, loff_t off, size_t count) @@ -512,6 +517,11 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp, /** * bitmap_print_bitmask_to_buf - convert bitmap to hex bitmask format ASCII string + * @buf: buffer into which string is placed + * @maskp: pointer to bitmap to convert + * @nmaskbits: size of bitmap, in bits + * @off: in the string from which we are copying, We copy to @buf + * @count: the maximum number of bytes to print * * The bitmap_print_to_pagebuf() is used indirectly via its cpumap wrapper * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal @@ -553,12 +563,6 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp, * move to use bin_attribute. In result, we have to pass the corresponding * parameters such as off, count from bin_attribute show entry to this API. * - * @buf: buffer into which string is placed - * @maskp: pointer to bitmap to convert - * @nmaskbits: size of bitmap, in bits - * @off: in the string from which we are copying, We copy to @buf - * @count: the maximum number of bytes to print - * * The role of cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf() * is similar with cpumap_print_to_pagebuf(), the difference is that * bitmap_print_to_pagebuf() mainly serves sysfs attribute with the assumption @@ -597,6 +601,11 @@ EXPORT_SYMBOL(bitmap_print_bitmask_to_buf); /** * bitmap_print_list_to_buf - convert bitmap to decimal list format ASCII string + * @buf: buffer into which string is placed + * @maskp: pointer to bitmap to convert + * @nmaskbits: size of bitmap, in bits + * @off: in the string from which we are copying, We copy to @buf + * @count: the maximum number of bytes to print * * Everything is same with the above bitmap_print_bitmask_to_buf() except * the print format. @@ -807,7 +816,8 @@ EXPORT_SYMBOL(bitmap_parselist); /** - * bitmap_parselist_user() + * bitmap_parselist_user() - convert user buffer's list format ASCII + * string to bitmap * * @ubuf: pointer to user buffer containing string. * @ulen: buffer size in bytes. If string is smaller than this -- cgit From 430cd4a28d7321d1e37b030a3793757077cc4f3c Mon Sep 17 00:00:00 2001 From: Mauro Carvalho Chehab Date: Sat, 26 Mar 2022 11:41:46 +0100 Subject: lib/bitmap.c make bitmap_print_bitmask_to_buf parseable The documentation of such function is not on a proper ReST format, as reported by Sphinx: Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:526: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:533: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Definition list ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:542: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:543: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:545: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:545: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:554: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:556: WARNING: Definition list ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:580: WARNING: Unexpected indentation. So, the produced output at: https://www.kernel.org/doc/html/latest/core-api/kernel-api.html?#c.bitmap_print_bitmask_to_buf is broken. Fix it by adding spaces and marking the literal blocks. Signed-off-by: Mauro Carvalho Chehab Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/bitmap.c | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 0d5c2ece0bcb..8ebe508580ea 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -527,33 +527,39 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp, * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal * bitmask and decimal list to userspace by sysfs ABI. * Drivers might be using a normal attribute for this kind of ABIs. A - * normal attribute typically has show entry as below: - * static ssize_t example_attribute_show(struct device *dev, + * normal attribute typically has show entry as below:: + * + * static ssize_t example_attribute_show(struct device *dev, * struct device_attribute *attr, char *buf) - * { + * { * ... * return bitmap_print_to_pagebuf(true, buf, &mask, nr_trig_max); - * } + * } + * * show entry of attribute has no offset and count parameters and this * means the file is limited to one page only. * bitmap_print_to_pagebuf() API works terribly well for this kind of - * normal attribute with buf parameter and without offset, count: - * bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, + * normal attribute with buf parameter and without offset, count:: + * + * bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, * int nmaskbits) - * { - * } + * { + * } + * * The problem is once we have a large bitmap, we have a chance to get a * bitmask or list more than one page. Especially for list, it could be * as complex as 0,3,5,7,9,... We have no simple way to know it exact size. * It turns out bin_attribute is a way to break this limit. bin_attribute - * has show entry as below: - * static ssize_t - * example_bin_attribute_show(struct file *filp, struct kobject *kobj, + * has show entry as below:: + * + * static ssize_t + * example_bin_attribute_show(struct file *filp, struct kobject *kobj, * struct bin_attribute *attr, char *buf, * loff_t offset, size_t count) - * { + * { * ... - * } + * } + * * With the new offset and count parameters, this makes sysfs ABI be able * to support file size more than one page. For example, offset could be * >= 4096. @@ -577,6 +583,7 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp, * This function is not a replacement for sprintf() or bitmap_print_to_pagebuf(). * It is intended to workaround sysfs limitations discussed above and should be * used carefully in general case for the following reasons: + * * - Time complexity is O(nbits^2/count), comparing to O(nbits) for snprintf(). * - Memory complexity is O(nbits), comparing to O(1) for snprintf(). * - @off and @count are NOT offset and number of bits to print. -- cgit 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 --- lib/bitmap.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 8ebe508580ea..4061a5dd2bc6 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1512,5 +1512,59 @@ void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits) buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31)); } EXPORT_SYMBOL(bitmap_to_arr32); +#endif + +#if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN) +/** + * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap + * @bitmap: array of unsigned longs, the destination bitmap + * @buf: array of u64 (in host byte order), the source bitmap + * @nbits: number of bits in @bitmap + */ +void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits) +{ + int n; + + for (n = nbits; n > 0; n -= 64) { + u64 val = *buf++; + + *bitmap++ = val; + if (n > 32) + *bitmap++ = val >> 32; + } + + /* + * Clear tail bits in the last word beyond nbits. + * + * Negative index is OK because here we point to the word next + * to the last word of the bitmap, except for nbits == 0, which + * is tested implicitly. + */ + if (nbits % BITS_PER_LONG) + bitmap[-1] &= BITMAP_LAST_WORD_MASK(nbits); +} +EXPORT_SYMBOL(bitmap_from_arr64); + +/** + * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits + * @buf: array of u64 (in host byte order), the dest bitmap + * @bitmap: array of unsigned longs, the source bitmap + * @nbits: number of bits in @bitmap + */ +void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits) +{ + const unsigned long *end = bitmap + BITS_TO_LONGS(nbits); + while (bitmap < end) { + *buf = *bitmap++; + if (bitmap < end) + *buf |= (u64)(*bitmap++) << 32; + buf++; + } + + /* Clear tail bits in the last element of array beyond nbits. */ + if (nbits % 64) + buf[-1] &= GENMASK_ULL(nbits % 64, 0); +} +EXPORT_SYMBOL(bitmap_to_arr64); #endif -- cgit 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 --- lib/bitmap.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 4061a5dd2bc6..b18e31ea6e66 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -45,19 +45,19 @@ * for the best explanations of this ordering. */ -int __bitmap_equal(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int bits) +bool __bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int bits) { unsigned int k, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; ++k) if (bitmap1[k] != bitmap2[k]) - return 0; + return false; if (bits % BITS_PER_LONG) if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) - return 0; + return false; - return 1; + return true; } EXPORT_SYMBOL(__bitmap_equal); @@ -303,33 +303,33 @@ void __bitmap_replace(unsigned long *dst, } EXPORT_SYMBOL(__bitmap_replace); -int __bitmap_intersects(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int bits) +bool __bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int bits) { unsigned int k, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; ++k) if (bitmap1[k] & bitmap2[k]) - return 1; + return true; if (bits % BITS_PER_LONG) if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) - return 1; - return 0; + return true; + return false; } EXPORT_SYMBOL(__bitmap_intersects); -int __bitmap_subset(const unsigned long *bitmap1, - const unsigned long *bitmap2, unsigned int bits) +bool __bitmap_subset(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int bits) { unsigned int k, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; ++k) if (bitmap1[k] & ~bitmap2[k]) - return 0; + return false; if (bits % BITS_PER_LONG) if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) - return 0; - return 1; + return false; + return true; } EXPORT_SYMBOL(__bitmap_subset); -- cgit From 428bc098635680a664779f26f24fe9197d186172 Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Mon, 11 Jul 2022 20:09:29 +0200 Subject: lib/bitmap: fix off-by-one in bitmap_to_arr64() GENMASK*() family takes the first and the last bits of the mask *including* them. So, with the current code bitmap_to_arr64() doesn't clear the tail properly: nbits % exp mask must be 1 GENMASK(1, 0) 0x3 0x1 ... 63 GENMASK(63, 0) 0xffffffffffffffff 0x7fffffffffffffff This was found by making the function always available instead of 32-bit BE systems only (for reusing in some new functionality). Turn the number of bits into the last bit set by subtracting 1. @nbits is already checked to be positive beforehand. Fixes: 0a97953fd221 ("lib: add bitmap_{from,to}_arr64") Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index b18e31ea6e66..e903e13c62e1 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1564,7 +1564,7 @@ void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits) /* Clear tail bits in the last element of array beyond nbits. */ if (nbits % 64) - buf[-1] &= GENMASK_ULL(nbits % 64, 0); + buf[-1] &= GENMASK_ULL((nbits - 1) % 64, 0); } EXPORT_SYMBOL(bitmap_to_arr64); #endif -- cgit 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 --- lib/bitmap.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index e903e13c62e1..9bc80f5bf149 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -237,7 +237,7 @@ void bitmap_cut(unsigned long *dst, const unsigned long *src, } EXPORT_SYMBOL(bitmap_cut); -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 bits) { unsigned int k; @@ -275,7 +275,7 @@ void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_xor); -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 bits) { unsigned int k; -- cgit 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 --- lib/bitmap.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 9bc80f5bf149..2b67cd657692 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -333,10 +333,9 @@ bool __bitmap_subset(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_subset); -int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) +unsigned long __bitmap_weight(const unsigned long *bitmap, unsigned int bits) { - unsigned int k, lim = bits/BITS_PER_LONG; - int w = 0; + unsigned long k, w = 0, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; k++) w += hweight_long(bitmap[k]); -- cgit From 70a1cb106d9410f1f37e0261728e46722b74c29f Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Sat, 17 Sep 2022 20:07:11 -0700 Subject: lib/bitmap: don't call __bitmap_weight() in kernel code __bitmap_weight() is not to be used directly in the kernel code because it's a helper for bitmap_weight(). Switch everything to bitmap_weight(). Signed-off-by: Yury Norov --- lib/bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 488e6c3e5acc..d56e275db73e 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -953,7 +953,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne if (pos >= nbits || !test_bit(pos, buf)) return -1; - return __bitmap_weight(buf, pos); + return bitmap_weight(buf, pos); } /** -- cgit 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 --- lib/bitmap.c | 30 +++++++++++++++++++++--------- 1 file changed, 21 insertions(+), 9 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index d56e275db73e..3fc2e338ec30 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -333,20 +333,32 @@ bool __bitmap_subset(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_subset); +#define BITMAP_WEIGHT(FETCH, bits) \ +({ \ + unsigned int __bits = (bits), idx, w = 0; \ + \ + for (idx = 0; idx < __bits / BITS_PER_LONG; idx++) \ + w += hweight_long(FETCH); \ + \ + if (__bits % BITS_PER_LONG) \ + w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits)); \ + \ + w; \ +}) + unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) { - unsigned int k, lim = bits/BITS_PER_LONG, w = 0; - - for (k = 0; k < lim; k++) - w += hweight_long(bitmap[k]); - - if (bits % BITS_PER_LONG) - w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); - - return w; + return BITMAP_WEIGHT(bitmap[idx], bits); } EXPORT_SYMBOL(__bitmap_weight); +unsigned int __bitmap_weight_and(const unsigned long *bitmap1, + const unsigned long *bitmap2, unsigned int bits) +{ + return BITMAP_WEIGHT(bitmap1[idx] & bitmap2[idx], bits); +} +EXPORT_SYMBOL(__bitmap_weight_and); + void __bitmap_set(unsigned long *map, unsigned int start, int len) { unsigned long *p = map + BIT_WORD(start); -- cgit 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 --- lib/bitmap.c | 36 +++--------------------------------- 1 file changed, 3 insertions(+), 33 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 3fc2e338ec30..1c81413c51f8 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -968,36 +968,6 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne return bitmap_weight(buf, pos); } -/** - * bitmap_ord_to_pos - find position of n-th set bit in bitmap - * @buf: pointer to bitmap - * @ord: ordinal bit position (n-th set bit, n >= 0) - * @nbits: number of valid bit positions in @buf - * - * Map the ordinal offset of bit @ord in @buf to its position in @buf. - * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord - * >= weight(buf), returns @nbits. - * - * If for example, just bits 4 through 7 are set in @buf, then @ord - * values 0 through 3 will get mapped to 4 through 7, respectively, - * and all other @ord values returns @nbits. When @ord value 3 - * gets mapped to (returns) @pos value 7 in this example, that means - * that the 3rd set bit (starting with 0th) is at position 7 in @buf. - * - * The bit positions 0 through @nbits-1 are valid positions in @buf. - */ -unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits) -{ - unsigned int pos; - - for (pos = find_first_bit(buf, nbits); - pos < nbits && ord; - pos = find_next_bit(buf, nbits, pos + 1)) - ord--; - - return pos; -} - /** * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap * @dst: remapped result @@ -1047,7 +1017,7 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src, if (n < 0 || w == 0) set_bit(oldbit, dst); /* identity map */ else - set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst); + set_bit(find_nth_bit(new, nbits, n % w), dst); } } EXPORT_SYMBOL(bitmap_remap); @@ -1086,7 +1056,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *old, if (n < 0 || w == 0) return oldbit; else - return bitmap_ord_to_pos(new, n % w, bits); + return find_nth_bit(new, bits, n % w); } EXPORT_SYMBOL(bitmap_bitremap); @@ -1210,7 +1180,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig, * The following code is a more efficient, but less * obvious, equivalent to the loop: * for (m = 0; m < bitmap_weight(relmap, bits); m++) { - * n = bitmap_ord_to_pos(orig, m, bits); + * n = find_nth_bit(orig, bits, m); * if (test_bit(m, orig)) * set_bit(n, dst); * } -- cgit