summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--MAINTAINERS3
-rw-r--r--lib/Kconfig.debug13
-rw-r--r--lib/Makefile1
-rw-r--r--lib/region_alloc_benchmark.c217
4 files changed, 234 insertions, 0 deletions
diff --git a/MAINTAINERS b/MAINTAINERS
index 1ab8736850ea..7f8662a0e5a0 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
@@ -15583,6 +15584,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
@@ -29329,6 +29331,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");
generated by cgit v1.2.3 (git 2.0.4) at 2026-08-20 22:42:20 +0000