lib: test bitmap vs IDA vs Maple Tree performance for region allocations
Subsystems (9)
PATCH v3 1/1 lib: test bitmap vs IDA vs Maple Tree performance for region allocations
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.
---
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
MAINTAINERS +3 -0
@@ -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
lib/Kconfig.debug +13 -0
@@ -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
lib/Makefile +1 -0
@@ -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
lib/region_alloc_benchmark.c new file +217 -0
217 lines not on this page · raw message
Signature · 1 line
2.53.0
[email protected]
AI reviewThank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [Medium] Silent integer truncation for capacities > UINT_MAX leads to corrupted benchmark state and false…
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] Silent integer truncation for capacities > UINT_MAX leads to corrupted benchmark state and false positive warnings.
- [Medium] Unhandled -ENOMEM from internal allocations triggers false positive WARN_ON.
--
--- Patch [1]: [PATCH v3] lib: test bitmap vs IDA vs Maple Tree performance for region allocations --- commit d6b29e543ce674f28d588ee458044d2815d73caa
Author: Yury Norov <[email protected]>
lib: test bitmap vs IDA vs Maple Tree performance for region allocations
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.
Quoted 4 lines
lib/region_alloc_benchmark.c new file +0
-0
[ ... ]
Quoted 8 lines
lib/region_alloc_benchmark.c new file +8
-0+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) +{
[ ... ]
lib/region_alloc_benchmark.c line 40
Quoted 8 lines
lib/region_alloc_benchmark.c new file +8
-0+ 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]);
[Severity: Medium]
Since the capacities array is populated from a module parameter using ulong, but bitmap_set() expects an unsigned int for the start index, could passing a capacity larger than UINT_MAX cause the start index to silently truncate to 32 bits here?
[ ... ]
Quoted 2 lines
lib/region_alloc_benchmark.c new file +2
-0+static unsigned long __init benchmark_ida (unsigned long cap) +{
[ ... ]
lib/region_alloc_benchmark.c line 89
Quoted 4 lines
lib/region_alloc_benchmark.c new file +4
-0+ 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 );
[Severity: Medium]
Similarly, ida_alloc_max() takes an unsigned int max parameter. Does this code truncate the 64-bit capacity bounds when cap exceeds UINT_MAX?
Quoted 7 lines
lib/region_alloc_benchmark.c new file +7
-0+if (id <0 ) +break ; + +if (!off) + reg_idx[cnt] = id; + } +if (id <0 ) {
lib/region_alloc_benchmark.c line 106
Quoted 10 lines
lib/region_alloc_benchmark.c new file +10
-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 );
[Severity: Medium]
If the system is under memory pressure, ida_alloc_max() can return -ENOMEM since it allocates with GFP_KERNEL. Will this trigger a false positive warning if internal allocations fail before reaching the capacity limit?
[ ... ]
Quoted 2 lines
lib/region_alloc_benchmark.c new file +2
-0+static unsigned long __init benchmark_maple_tree (unsigned long cap) +{
[ ... ]
lib/region_alloc_benchmark.c line 145
Quoted 3 lines
lib/region_alloc_benchmark.c new file +3
-0+ alloc_time =ktime_get () - alloc_time; + +WARN_ON (ret != -EBUSY );
[Severity: Medium]
Like the IDA implementation, mtree_alloc_range() can fail with -ENOMEM. Can this code trigger a system warning if memory is exhausted early?
[ ... ]
Quoted 2 lines
lib/region_alloc_benchmark.c new file +2
-0+static int __init region_alloc_benchmark (void ) +{
[ ... ]
lib/region_alloc_benchmark.c line 201
Quoted 6 lines
lib/region_alloc_benchmark.c new file +6
-0+ 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);
[Severity: Medium]
If one of the allocators fails early due to -ENOMEM while the others succeed, could that cause their region counts to diverge and trigger these assertions?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Guys, please send your comments / tags!
If no objections, I'll move it in bitmap-for-next before the end of week.
Thanks,
Yury
Quoted 380 lines · 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 16Region 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 848The 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.
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 inKconfig(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-EAGAINfor 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.cMAINTAINERS +3
-0@@ -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-treelib/Kconfig.debug +13
-0@@ -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 RUSTlib/Makefile +1
-0@@ -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.olib/region_alloc_benchmark.c new file +217
-0@@ -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" );Signature · 1 line
2.53.0
Quoted 368 lines · 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 16Region 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 848The 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.
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 inKconfig(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-EAGAINfor 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.cMAINTAINERS +3
-0@@ -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-treelib/Kconfig.debug +13
-0@@ -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 RUSTlib/Makefile +1
-0@@ -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.olib/region_alloc_benchmark.c new file +207
-0@@ -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:
lib/region_alloc_benchmark.c line 217
Quoted 10 lines
lib/region_alloc_benchmark.c new file +10
-0+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" );
Thanks Yury. I tested this out and got similar results to you. Code looks good to me too.