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

[Yury Norov <ynorov@nvidia.com>]

Guys, please send your comments / tags!

If no objections, I'll move it in bitmap-for-next before the end of week.

Thanks,
Yury

On Fri, Jul 17, 2026 at 01:32:40AM -0400, Yury Norov wrote:
> 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