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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] Large uninitialized static arrays marked with `__initdata` bloat the kernel binary by ~9.1MB.
- [Medium] Transient memory allocation failures trigger false positive `WARN_ON` bug reports.
- [Medium] Initializing a maple tree on the stack with `MTREE_INIT` causes a lockdep splat.
--

--- Patch [1]: [PATCH] lib: test bitmap vs Maple Tree performance for region allocations ---
commit b546f14f1527daeb17ae5d45e14a867ddc37369e
Author: Yury Norov <ynorov@nvidia.com>

lib: test bitmap vs Maple Tree performance for region allocations

This commit adds a microbenchmark to compare the performance of allocating
and freeing variable-sized regions. It tests a bitmap implementation against
a Maple Tree implementation across several capacities when the module loads.

Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
Link: https://lore.kernel.org/all/tencent_FBA5367F4AA8C57DE2198975767E416FC90A@qq.com/

> diff --git a/lib/region_alloc_benchmark.c b/lib/region_alloc_benchmark.c
> new file mode 100644
> index 0000000000000..7459e37608bca
> --- /dev/null
> +++ b/lib/region_alloc_benchmark.c
> @@ -0,0 +1,112 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/* Benchmark bitmap and Maple Tree allocation of variable-sized regions. */
> +
> +#include <linux/bitmap.h>
> +#include <linux/kernel.h>
> +#include <linux/maple_tree.h>
> +#include <linux/module.h>
> +#include <linux/printk.h>
> +#include <linux/random.h>
> +#include <linux/xarray.h>
> +
> +#define MAP_SIZE	(1000000UL)
> +#define REGION_MAX_SIZE	32
> +
> +static DECLARE_BITMAP(alloc_bitmap, MAP_SIZE) __initdata;
> +/* One more request guarantees that even an all-ones trace reaches ENOSPC. */
> +static u8 region_sizes[MAP_SIZE + 1] __initdata;
> +static unsigned long region_indexes[MAP_SIZE] __initdata;

[Severity: Medium]
Does using the __initdata macro on these large uninitialized arrays push
them into the PROGBITS .init.data section instead of .bss?

This can bloat the vmlinux image by around 9.1MB at build time, which
might cause boot or build failures on memory-constrained embedded
architectures with strict size limits.

[ ... ]

> +static unsigned long __init benchmark_maple_tree(unsigned long capacity)
> +{
> +	struct maple_tree mt = MTREE_INIT(mt, MT_FLAGS_ALLOC_RANGE);

[Severity: Medium]
Is it safe to initialize this maple tree on the stack using MTREE_INIT?

The MTREE_INIT macro uses __SPIN_LOCK_UNLOCKED, which relies on a C99
compound literal for the lockdep lock class key. At block scope, C99
compound literals have automatic storage duration. This places the lockdep
key on the stack and triggers a lockdep warning about registering a
non-static key.

Should dynamic initialization with mt_init_flags() be used here instead?

> +	unsigned long count, index;
> +	ktime_t alloc_time, free_time;
> +	size_t memory;
> +	int ret;
> +
> +	alloc_time = ktime_get();
> +	for (count = 0; count < ARRAY_SIZE(region_sizes); count++) {
> +		ret = mtree_alloc_range(&mt, &index, xa_mk_value(count + 1),
> +					region_sizes[count], 0, capacity - 1,
> +					GFP_KERNEL);
> +		if (ret)
> +			break;
> +
> +		region_indexes[count] = index;
> +	}
> +	alloc_time = ktime_get() - alloc_time;
> +	WARN_ON(ret != -EBUSY);

[Severity: Medium]
Could mtree_alloc_range() legitimately fail with -ENOMEM?

Since it uses GFP_KERNEL to allocate tree nodes internally, transient
memory pressure could cause an allocation failure. If that happens, this
WARN_ON will trigger a false positive bug report.

[ ... ]

> +static int __init region_alloc_benchmark(void)
> +{
> +	static const unsigned long capacities[] = { 1000000, 100000, 10000, 1000 };
> +	unsigned long bitmap_count, maple_count;
> +	unsigned long i;
> +
> +	for (i = 0; i < ARRAY_SIZE(region_sizes); i++)
> +		region_sizes[i] = get_random_u32_below(REGION_MAX_SIZE) + 1;
> +
> +	pr_err("\nStart testing bitmap vs Maple Tree region allocation\n");
> +	pr_err("%-6s   %12s   %12s   %8s   %10s\n", "type", "alloc (ns)", "free (ns)",
> +		"capacity", "memory (B)");
> +	for (i = 0; i < ARRAY_SIZE(capacities); i++) {
> +		bitmap_count = benchmark_bitmap(capacities[i]);
> +		maple_count = benchmark_maple_tree(capacities[i]);
> +		WARN_ON(bitmap_count != maple_count);

[Severity: Medium]
If benchmark_maple_tree() experiences an early -ENOMEM failure, will it
return a different element count than benchmark_bitmap(), leading to a
secondary false positive warning here?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260711013910.349586-1-ynorov@nvidia.com?part=1