Merge tag 'bitmap-for-7.3' of https://github.com/norov/linux

Pull bitmap updates from Yury Norov:
 "The usual set of fixes, cleanups and performance improvements together
  with a couple of new tests:

   - bitmap_find_next_zero_area_off() optimization (Sunyi)

   - bitmap_find_next_zero_area_off(): return size when no zero area is
     found (Yury)

   - bitmap vs IDA vs Maple Tree performance test (Yury)

   - get rid of cpumap_print_to_pagebuf() (Yury)

   - use nr_node_ids in __nodemask_pr_numnodes() (Li RongQing)

   - bitops: make the *_bit_le functions use unsigned long (Benjamin)

   - bitmap scatter & gather test fix (Christophe)

   - use __ASSEMBLER__ in bitmap header files (Thomas)"

* tag 'bitmap-for-7.3' of https://github.com/norov/linux: (25 commits)
  lib: test bitmap vs IDA vs Maple Tree performance for region allocations
  bitmap: Return size when no zero area is found
  media: s5p-mfc: Treat bitmap size as allocation failure
  crypto: ccp: Treat bitmap size as allocation failure
  powerpc/msi: Treat bitmap size as allocation failure
  ARM: dma-mapping: Treat bitmap size as allocation failure
  bitmap: drop bitmap_next_set_region()
  nodemask: reduce bitmap width to nr_node_ids in __nodemask_pr_numnodes()
  bitmap: Properly initialise destination bitmap for scatter & gather test
  lib/bitmap-str: get rid of cpumap_print_to_pagebuf()
  perf: Use sysfs_emit() for cpumask show callbacks
  PCI/sysfs: Use sysfs_emit() for cpumask show callbacks
  RDMA/hfi1: Use sysfs_emit() for cpumask show helper
  hwtracing: hisi_ptt: Use sysfs_emit() for cpumask show
  fpga: dfl-fme-perf: Use sysfs_emit() for cpumask show
  devfreq: Use sysfs_emit() for cpumask show callbacks
  cpu: Use sysfs_emit() for cpumask show callback
  x86/events: Use sysfs_emit() for cpumask show callbacks
  powerpc: Use sysfs_emit() for cpumask show callbacks
  arm: Use sysfs_emit() for cpumask show callbacks
  ...

7 files changed, 308 insertions, 18 deletions

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 73287ef2498c..6ea441f2fade 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2683,6 +2683,19 @@ config FIND_BIT_BENCHMARK
 
 	  If unsure, say N.
 
+config REGION_ALLOC_BENCHMARK
+	tristate "Benchmark bitmap, IDA and Maple Tree region allocation"
+	help
+	  This builds a microbenchmark comparing variable-sized region
+	  allocation using bitmaps, IDA and Maple Tree. The benchmark
+	  runs at initialization time.
+
+	  Usage:
+	    insmod region_alloc_benchmark.ko
+	    insmod region_alloc_benchmark.ko capacities=1024,2048,4096,65536
+
+	  If unsure, say N.
+
 config FIND_BIT_BENCHMARK_RUST
 	tristate "Test find_bit functions in Rust"
 	depends on RUST
diff --git a/lib/Makefile b/lib/Makefile
index 7f75cc6edf94..adb18810e3f7 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -64,6 +64,7 @@ obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
+obj-$(CONFIG_REGION_ALLOC_BENCHMARK) += region_alloc_benchmark.o
 obj-$(CONFIG_FIND_BIT_BENCHMARK_RUST) += find_bit_benchmark_rust.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 test_dhry-objs := dhry_1.o dhry_2.o dhry_run.o
diff --git a/lib/bitmap-str.c b/lib/bitmap-str.c
index 26d36c938c6a..dd9aa0635fa5 100644
--- a/lib/bitmap-str.c
+++ b/lib/bitmap-str.c
@@ -75,8 +75,7 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
  * @off: in the string from which we are copying, We copy to @buf
  * @count: the maximum number of bytes to print
  *
- * The sprintf("%*pb[l]") is used indirectly via its cpumap wrapper
- * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal
+ * The sprintf("%*pb[l]") format is used 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::
@@ -115,9 +114,9 @@ static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
  * parameters such as off, count from bin_attribute show entry to this API.
  *
  * 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
- * scnprintf("%*pb[l]") mainly serves sysfs attribute with the assumption
- * the destination buffer is exactly one page and won't be more than one page.
+ * is similar to direct sysfs_emit("%*pb[l]") formatting, but the latter
+ * assumes the destination buffer is exactly one page and won't be more than
+ * one page.
  * cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf(), on the other
  * hand, mainly serves bin_attribute which doesn't work with exact one page,
  * and it can break the size limit of converted decimal list and hexadecimal
diff --git a/lib/bitmap.c b/lib/bitmap.c
index b9bfa157e095..ed685127a107 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -424,6 +424,9 @@ EXPORT_SYMBOL(__bitmap_clear);
  * The @align_mask should be one less than a power of 2; the effect is that
  * the bit offset of all zero areas this function finds plus @align_offset
  * is multiple of that power of 2.
+ *
+ * Return: The bit offset of the found area or a value greater than or equal
+ * to @size if no area is found.
  */
 unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long size,
@@ -432,22 +435,23 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long align_mask,
 					     unsigned long align_offset)
 {
-	unsigned long index, end, i;
-again:
-	index = find_next_zero_bit(map, size, start);
+	unsigned long end, i, off;
+
+	for_each_clear_bit_from(start, map, size) {
+		start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
+		end = start + nr;
+		if (end > size)
+			break;
 
-	/* Align allocation */
-	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
+		off = round_down(start, BITS_PER_LONG);
+		i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off;
+		if (i >= end || i < start)
+			return start;
 
-	end = index + nr;
-	if (end > size)
-		return end;
-	i = find_next_bit(map, end, index);
-	if (i < end) {
-		start = i + 1;
-		goto again;
+		start = i;
 	}
-	return index;
+
+	return size;
 }
 EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
 
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 00d9dc61cd46..05305e655f99 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -149,6 +149,21 @@ static int __init test_find_next_and_bit(const void *bitmap,
 	return 0;
 }
 
+static int __init
+test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len)
+{
+	unsigned long i, cnt;
+	ktime_t time;
+
+	time = ktime_get();
+	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+		i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1;
+	time = ktime_get() - time;
+	pr_err("bitmap_find_next_zero_area_off:%7llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
 static int __init find_bit_test(void)
 {
 	unsigned long nbits = BITMAP_LEN / SPARSE;
@@ -158,6 +173,7 @@ static int __init find_bit_test(void)
 	get_random_bytes(bitmap, sizeof(bitmap));
 	get_random_bytes(bitmap2, sizeof(bitmap2));
 
+	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
@@ -181,6 +197,7 @@ static int __init find_bit_test(void)
 		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap2);
 	}
 
+	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
diff --git a/lib/region_alloc_benchmark.c b/lib/region_alloc_benchmark.c
new file mode 100644
index 000000000000..e88b4cf55c62
--- /dev/null
+++ b/lib/region_alloc_benchmark.c
@@ -0,0 +1,217 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Benchmark bitmap, IDA and Maple Tree allocation of variable-sized regions. */
+
+#include <linux/bitmap.h>
+#include <linux/idr.h>
+#include <linux/kernel.h>
+#include <linux/maple_tree.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/random.h>
+#include <linux/slab.h>
+#include <linux/xarray.h>
+
+#define REGION_MAX_SIZE	32
+
+static unsigned long *bitmap __initdata;
+/* One more request guarantees that even an all-ones trace reaches ENOSPC. */
+static u8 *reg_sz __initdata;
+static unsigned long *reg_idx __initdata;
+static unsigned long capacities[64] = { 1000000, 100000, 10000, 1000, 100, 10 };
+static unsigned int cap_cnt = 6;
+
+module_param_array(capacities, ulong, &cap_cnt, 0400);
+MODULE_PARM_DESC(capacities, "Region capacities to benchmark");
+
+static unsigned long __init benchmark_bitmap(unsigned long cap)
+{
+	unsigned long cnt, idx;
+	ktime_t alloc_time, free_time;
+	size_t sz;
+
+	bitmap_zero(bitmap, cap);
+	alloc_time = ktime_get();
+	for (cnt = 0; cnt <= cap; cnt++) {
+		idx = bitmap_find_next_zero_area(bitmap, cap, 0, reg_sz[cnt], 0);
+		if (idx >= cap)
+			break;
+
+		reg_idx[cnt] = idx;
+		bitmap_set(bitmap, idx, reg_sz[cnt]);
+	}
+	alloc_time = ktime_get() - alloc_time;
+
+	idx = cnt;
+
+	free_time = ktime_get();
+	while (idx--)
+		bitmap_clear(bitmap, reg_idx[idx], reg_sz[idx]);
+	free_time = ktime_get() - free_time;
+
+	WARN_ON(!bitmap_empty(bitmap, cap));
+
+	sz = BITS_TO_LONGS(cap) * sizeof(unsigned long);
+	pr_err("Bitmap  %12llu  %12llu  %8lu  %8lu  %10zu\n",
+	       alloc_time, free_time, cnt, cap, sz);
+
+	return cnt;
+}
+
+static size_t __init ida_size(unsigned long nr_ids)
+{
+	unsigned long entries = DIV_ROUND_UP(nr_ids, IDA_BITMAP_BITS);
+	unsigned long bitmaps = nr_ids / IDA_BITMAP_BITS;
+	unsigned long nodes = 0;
+
+	if (nr_ids % IDA_BITMAP_BITS > BITS_PER_XA_VALUE)
+		bitmaps++;
+
+	while (entries > 1) {
+		entries = DIV_ROUND_UP(entries, XA_CHUNK_SIZE);
+		nodes += entries;
+	}
+
+	return sizeof(struct ida) +
+		bitmaps * sizeof(struct ida_bitmap) +
+		nodes   * sizeof(struct xa_node);
+}
+
+static unsigned long __init benchmark_ida(unsigned long cap)
+{
+	struct ida ida = IDA_INIT(ida);
+	unsigned long cnt, idx, off, nr_ids = 0;
+	ktime_t alloc_time, free_time;
+	int id = -ENOSPC;
+
+	alloc_time = ktime_get();
+	for (cnt = 0; cnt <= cap; cnt++) {
+		for (off = 0; off < reg_sz[cnt]; off++) {
+			id = ida_alloc_max(&ida, cap - 1, GFP_KERNEL);
+			if (id < 0)
+				break;
+
+			if (!off)
+				reg_idx[cnt] = id;
+		}
+		if (id < 0) {
+			while (off--)
+				ida_free(&ida, reg_idx[cnt] + off);
+			break;
+		}
+		WARN_ON(id != reg_idx[cnt] + reg_sz[cnt] - 1);
+		nr_ids += reg_sz[cnt];
+	}
+	alloc_time = ktime_get() - alloc_time;
+
+	WARN_ON(id != -ENOSPC);
+
+	idx = cnt;
+
+	free_time = ktime_get();
+	while (idx--) {
+		for (off = 0; off < reg_sz[idx]; off++)
+			ida_free(&ida, reg_idx[idx] + off);
+	}
+	free_time = ktime_get() - free_time;
+
+	WARN_ON(!ida_is_empty(&ida));
+
+	pr_err("IDA     %12llu  %12llu  %8lu  %8lu  %10zu\n",
+	       alloc_time, free_time, cnt, cap, ida_size(nr_ids));
+
+	ida_destroy(&ida);
+	return cnt;
+}
+
+static unsigned long __init benchmark_maple_tree(unsigned long cap)
+{
+	struct maple_tree mt = MTREE_INIT(mt, MT_FLAGS_ALLOC_RANGE);
+	unsigned long cnt, idx;
+	ktime_t alloc_time, free_time;
+	size_t sz;
+	int ret;
+
+	alloc_time = ktime_get();
+	for (cnt = 0; cnt <= cap; cnt++) {
+		ret = mtree_alloc_range(&mt, &idx, xa_mk_value(cnt + 1),
+					reg_sz[cnt], 0, cap - 1, GFP_KERNEL);
+		if (ret)
+			break;
+
+		reg_idx[cnt] = idx;
+	}
+	alloc_time = ktime_get() - alloc_time;
+
+	WARN_ON(ret != -EBUSY);
+
+	idx = cnt;
+
+	free_time = ktime_get();
+	while (idx--)
+		mtree_erase(&mt, reg_idx[idx]);
+	free_time = ktime_get() - free_time;
+
+	WARN_ON(!mtree_empty(&mt));
+
+	/* Minimum storage assuming fully occupied allocation-range leaf nodes. */
+	sz = sizeof(mt) + DIV_ROUND_UP(cnt, MAPLE_ARANGE64_SLOTS) * sizeof(struct maple_node);
+	pr_err("Maple   %12llu  %12llu  %8lu  %8lu  %10zu\n",
+	       alloc_time, free_time, cnt, cap, sz);
+
+	mtree_destroy(&mt);
+	return cnt;
+}
+
+static int __init region_alloc_benchmark(void)
+{
+	unsigned long bitmap_count, ida_count, maple_count;
+	unsigned long i, max_cap = 0;
+	int ret = -ENOMEM;
+
+	for (i = 0; i < cap_cnt; i++) {
+		if (capacities[i] == 0) {
+			pr_err("capacity must be nonzero\n");
+			return -EINVAL;
+		}
+		max_cap = max(max_cap, capacities[i]);
+	}
+
+	bitmap = kvmalloc_array(BITS_TO_LONGS(max_cap), sizeof(*bitmap), GFP_KERNEL);
+	reg_sz = kvmalloc_array(max_cap + 1, sizeof(*reg_sz), GFP_KERNEL);
+	reg_idx = kvmalloc_array(max_cap, sizeof(*reg_idx), GFP_KERNEL);
+	if (!bitmap || !reg_sz || !reg_idx)
+		goto out;
+
+	pr_err("\nStart testing bitmap vs IDA vs Maple Tree region allocation\n");
+	pr_err("memory: bitmap is exact; IDA and Maple Tree are lower bounds\n");
+	pr_err("Type      alloc (ns)     free (ns)   regions  capacity  memory (B)\n");
+
+	for (i = 0; i < cap_cnt; i++) {
+		unsigned long idx, max_size;
+
+		max_size = min(REGION_MAX_SIZE, capacities[i] / 10) ? : 1;
+		for (idx = 0; idx <= capacities[i]; idx++)
+			reg_sz[idx] = get_random_u32_below(max_size) + 1;
+
+		bitmap_count = benchmark_bitmap(capacities[i]);
+		maple_count  = benchmark_maple_tree(capacities[i]);
+		ida_count    = benchmark_ida(capacities[i]);
+
+		WARN_ON(bitmap_count != ida_count);
+		WARN_ON(bitmap_count != maple_count);
+	}
+
+	/* Return an error so the benchmark can run repeatedly without rmmod. */
+	pr_info("Region allocation benchmark complete\n");
+	ret = -EAGAIN;
+out:
+	kvfree(reg_idx);
+	kvfree(reg_sz);
+	kvfree(bitmap);
+	return ret;
+}
+module_init(region_alloc_benchmark);
+
+MODULE_AUTHOR("Yury Norov <ynorov@nvidia.com>");
+MODULE_DESCRIPTION("Benchmark bitmap, IDA and Maple Tree region allocation");
+MODULE_LICENSE("GPL");
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 69813c10e6c0..56bd23059b26 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void)
 	}
 }
 
+static void __init
+test_bitmap_find_next_zero_area_off(void)
+{
+	DECLARE_BITMAP(bmap, 192);
+
+	bitmap_set(bmap, 0, 192);
+
+	bitmap_clear(bmap, 0, 8);
+	__clear_bit(50, bmap);
+	bitmap_clear(bmap, 60, 18);
+	__set_bit(69, bmap);
+	__clear_bit(80, bmap);
+	bitmap_clear(bmap, 100, 10);
+	__clear_bit(120, bmap);
+	bitmap_clear(bmap, 145, 8);
+	bitmap_clear(bmap, 160, 32);
+
+	expect_eq_uint(0,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0));
+	expect_eq_uint(0,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0));
+	expect_eq_uint(163,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1));
+	expect_eq_uint(60,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0));
+	expect_eq_uint(160,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0));
+	expect_eq_uint(60,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4));
+	expect_eq_uint(100,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0));
+	expect_eq_uint(160,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0));
+	expect_eq_uint(1,
+		!!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >= 192));
+}
+
 static void __init test_fill_set(void)
 {
 	DECLARE_BITMAP(bmap, 1024);
@@ -392,6 +429,7 @@ static void __init test_bitmap_sg(void)
 
 	/* Scatter/gather relationship */
 	bitmap_zero(bmap_tmp, 100);
+	bitmap_zero(bmap_res, 100);
 	bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits);
 	bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits);
 	expect_eq_bitmap(bmap_scatter, bmap_res, 100);
@@ -1559,6 +1597,7 @@ static void __init selftest(void)
 	test_for_each_clear_bitrange_from();
 	test_for_each_set_clump8();
 	test_for_each_set_bit_wrap();
+	test_bitmap_find_next_zero_area_off();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);