[PATCH v3] lib: test bitmap vs IDA vs Maple Tree performance for region allocations

[PATCH v3] lib: test bitmap vs IDA vs Maple Tree performance for region allocations

[Yury Norov]

Compare the cost of allocating and freeing variable-sized regions using
a bitmap, IDA and a Maple Tree. All implementations process the same
randomly generated sequence of regions containing up to 32 entries, until
the configured capacity is exhausted.

The benchmark exercises monotonic allocation into an initially empty pool,
followed by reverse-order freeing. It does not model fragmentation or
interleaved allocation and freeing, nor does it isolate locking or RCU
overhead. Allocation time includes the terminal failed request that detects
exhaustion.

Run the benchmark at several capacities to show how the approaches scale.
Report allocation and free times separately because bitmap, IDA and Maple
Tree removal have substantially different costs.

On x86/kvm, the output example is:

Start testing bitmap vs IDA vs Maple Tree region allocation
memory: bitmap is exact; IDA and Maple Tree are lower bounds
Type      alloc (ns)     free (ns)   regions  capacity  memory (B)
Bitmap      93457345        176151     60644   1000000      125000
Maple       11758660      12870146     60644   1000000     1552656
IDA         31066416      20870824     60644   1000000      134864
Bitmap        919119         17679      6032    100000       12504
Maple        1158193       1187140      6032    100000      154640
IDA          2759670       2116004      6032    100000       14288
Bitmap         17120          2043       613     10000        1256
Maple         116350        117537       613     10000       15888
IDA           243396        202654       613     10000        1872
Bitmap          1220           262        55      1000         128
Maple          12076         10106        55      1000        1552
IDA            25730         20875        55      1000         144
Bitmap           593           124        18       100          16
Maple           3599          4782        18       100         528
IDA             3266          1960        18       100         144
Bitmap           414           129        10        10           8
Maple           2143          1385        10        10         272
IDA              892           648        10        10          16
Region allocation benchmark complete

Reported IDA and Maple Tree memory figures exclude slab overhead
and transient allocations. The Maple Tree figure is additionally
a lower-bound estimate that assumes fully occupied leaf nodes and
excludes internal nodes.

IDA has no region-allocation API, so each region is implemented as
a sequence of single-ID allocations. The IDs remain contiguous
because this benchmark fills an initially empty IDA monotonically.

The benchmark is motivated by the discussion linked below about choosing
the best data structure for the channel ID pool with the capacity of 2048
IDs for the nova GPU driver.

Specifically for 2048 IDs the result is:

Bitmap          5112           615       121      2048         256
Maple          78526         59592       121      2048        3344
IDA           165274        117761       121      2048         848

The benchmark accepts a list of up to 64 nonzero capacities to test.
For example:

  insmod region_alloc_benchmark.ko capacities=1024,2048,4096,65536

The list may contain duplicate capacities. Each occurrence generates a new
region-size sequence, which is useful for collecting statistical
characteristics of the benchmark results.

Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
Signed-off-by: Yury Norov <ynorov@nvidia.com>
---
v3:
- allow capacities to be configured through the module parameter (Yury Norov)
- document default and custom-capacity usage in Kconfig (Yury Norov)
- store and generate only the region sizes required by each run (Yury Norov)
- clarify the workload, timing semantics and memory estimates (Pedro Falcato, Onur Özkan)
- report region count and capacity while retaining raw timings (Gary Guo)
- add post-free integrity checks (Yury Norov)
- add default capacities of 10 and 100 IDs (Matthew Wilcox)
- bound generated region sizes appropriately for small capacities (Matthew Wilcox)
- report successful completion and return -EAGAIN for repeat runs (Yury Norov)
v2: https://lore.kernel.org/all/20260711063602.426311-1-ynorov@nvidia.com/
v1: https://lore.kernel.org/all/20260711013910.349586-1-ynorov@nvidia.com/

 MAINTAINERS                  |   3 +
 lib/Kconfig.debug            |  13 +++
 lib/Makefile                 |   1 +
 lib/region_alloc_benchmark.c | 217 +++++++++++++++++++++++++++++++++++
 4 files changed, 234 insertions(+)
 create mode 100644 lib/region_alloc_benchmark.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 7cc4bca5a2c5..9e487a94aba4 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4615,6 +4615,7 @@ F:	lib/bitmap.c
 F:	lib/cpumask.c
 F:	lib/find_bit.c
 F:	lib/find_bit_benchmark.c
+F:	lib/region_alloc_benchmark.c
 F:	lib/test_bitmap.c
 F:	lib/tests/cpumask_kunit.c
 F:	tools/include/linux/bitfield.h
@@ -15581,6 +15582,7 @@ F:	Documentation/core-api/maple_tree.rst
 F:	include/linux/maple_tree.h
 F:	include/trace/events/maple_tree.h
 F:	lib/maple_tree.c
+F:	lib/region_alloc_benchmark.c
 F:	lib/test_maple_tree.c
 F:	rust/helpers/maple_tree.c
 F:	rust/kernel/maple_tree.rs
@@ -29323,6 +29325,7 @@ F:	Documentation/core-api/xarray.rst
 F:	include/linux/idr.h
 F:	include/linux/xarray.h
 F:	lib/idr.c
+F:	lib/region_alloc_benchmark.c
 F:	lib/test_xarray.c
 F:	lib/xarray.c
 F:	tools/testing/radix-tree
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 1244dcac2294..0451dfca7098 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/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");
-- 
2.53.0