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/[email protected]/ > Signed-off-by: Yury Norov <[email protected]> > --- > 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/[email protected]/ > v1: https://lore.kernel.org/all/[email protected]/ > > 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 <[email protected]>"); > +MODULE_DESCRIPTION("Benchmark bitmap, IDA and Maple Tree region allocation"); > +MODULE_LICENSE("GPL"); > -- > 2.53.0
