summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2022-06-05 00:04:27 +0300
committerLinus Torvalds <torvalds@linux-foundation.org>2022-06-05 00:04:27 +0300
commitd0e60d46bc03252b8d4ffaaaa0b371970ac16cda (patch)
tree73d0b5c620a1bc73e9fe62522eabb7b4326ddc2b /lib
parent23df9ba64bb9e26cfee6b34f5c3ece49a8a61ee1 (diff)
parent0dfe54071d7c828a02917b595456bfde1afdddc9 (diff)
downloadlinux-d0e60d46bc03252b8d4ffaaaa0b371970ac16cda.tar.xz
Merge tag 'bitmap-for-5.19-rc1' of https://github.com/norov/linux
Pull bitmap updates from Yury Norov: - bitmap: optimize bitmap_weight() usage, from me - lib/bitmap.c make bitmap_print_bitmask_to_buf parseable, from Mauro Carvalho Chehab - include/linux/find: Fix documentation, from Anna-Maria Behnsen - bitmap: fix conversion from/to fix-sized arrays, from me - bitmap: Fix return values to be unsigned, from Kees Cook It has been in linux-next for at least a week with no problems. * tag 'bitmap-for-5.19-rc1' of https://github.com/norov/linux: (31 commits) nodemask: Fix return values to be unsigned bitmap: Fix return values to be unsigned KVM: x86: hyper-v: replace bitmap_weight() with hweight64() KVM: x86: hyper-v: fix type of valid_bank_mask ia64: cleanup remove_siblinginfo() drm/amd/pm: use bitmap_{from,to}_arr32 where appropriate KVM: s390: replace bitmap_copy with bitmap_{from,to}_arr64 where appropriate lib/bitmap: add test for bitmap_{from,to}_arr64 lib: add bitmap_{from,to}_arr64 lib/bitmap: extend comment for bitmap_(from,to)_arr32() include/linux/find: Fix documentation lib/bitmap.c make bitmap_print_bitmask_to_buf parseable MAINTAINERS: add cpumask and nodemask files to BITMAP_API arch/x86: replace nodes_weight with nodes_empty where appropriate mm/vmstat: replace cpumask_weight with cpumask_empty where appropriate clocksource: replace cpumask_weight with cpumask_empty in clocksource.c genirq/affinity: replace cpumask_weight with cpumask_empty where appropriate irq: mips: replace cpumask_weight with cpumask_empty where appropriate drm/i915/pmu: replace cpumask_weight with cpumask_empty where appropriate arch/x86: replace cpumask_weight with cpumask_empty where appropriate ...
Diffstat (limited to 'lib')
-rw-r--r--lib/bitmap.c117
-rw-r--r--lib/nodemask.c4
-rw-r--r--lib/test_bitmap.c25
3 files changed, 116 insertions, 30 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 0d5c2ece0bcb..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);
@@ -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.
@@ -1505,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
diff --git a/lib/nodemask.c b/lib/nodemask.c
index 3aa454c54c0d..e22647f5181b 100644
--- a/lib/nodemask.c
+++ b/lib/nodemask.c
@@ -3,9 +3,9 @@
#include <linux/module.h>
#include <linux/random.h>
-int __next_node_in(int node, const nodemask_t *srcp)
+unsigned int __next_node_in(int node, const nodemask_t *srcp)
{
- int ret = __next_node(node, srcp);
+ unsigned int ret = __next_node(node, srcp);
if (ret == MAX_NUMNODES)
ret = __first_node(srcp);
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 0c82f07f74fc..d5923a640457 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -585,6 +585,30 @@ static void __init test_bitmap_arr32(void)
}
}
+static void __init test_bitmap_arr64(void)
+{
+ unsigned int nbits, next_bit;
+ u64 arr[EXP1_IN_BITS / 64];
+ DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
+
+ memset(arr, 0xa5, sizeof(arr));
+
+ for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
+ memset(bmap2, 0xff, sizeof(arr));
+ bitmap_to_arr64(arr, exp1, nbits);
+ bitmap_from_arr64(bmap2, arr, nbits);
+ expect_eq_bitmap(bmap2, exp1, nbits);
+
+ next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
+ if (next_bit < round_up(nbits, BITS_PER_LONG))
+ pr_err("bitmap_copy_arr64(nbits == %d:"
+ " tail is not safely cleared: %d\n", nbits, next_bit);
+
+ if (nbits < EXP1_IN_BITS - 64)
+ expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
+ }
+}
+
static void noinline __init test_mem_optimisations(void)
{
DECLARE_BITMAP(bmap1, 1024);
@@ -852,6 +876,7 @@ static void __init selftest(void)
test_copy();
test_replace();
test_bitmap_arr32();
+ test_bitmap_arr64();
test_bitmap_parse();
test_bitmap_parselist();
test_bitmap_printlist();