Merge tag 'bitmap-for-7.3' of https://github.com/norov/linux

Pull bitmap updates from Yury Norov:
"The usual set of fixes, cleanups and performance improvements together
with a couple of new test

Merge tag 'bitmap-for-7.3' of https://github.com/norov/linux

Pull bitmap updates from Yury Norov:
"The usual set of fixes, cleanups and performance improvements together
with a couple of new tests:

- bitmap_find_next_zero_area_off() optimization (Sunyi)

- bitmap_find_next_zero_area_off(): return size when no zero area is
found (Yury)

- bitmap vs IDA vs Maple Tree performance test (Yury)

- get rid of cpumap_print_to_pagebuf() (Yury)

- use nr_node_ids in __nodemask_pr_numnodes() (Li RongQing)

- bitops: make the *_bit_le functions use unsigned long (Benjamin)

- bitmap scatter & gather test fix (Christophe)

- use __ASSEMBLER__ in bitmap header files (Thomas)"

* tag 'bitmap-for-7.3' of https://github.com/norov/linux: (25 commits)
lib: test bitmap vs IDA vs Maple Tree performance for region allocations
bitmap: Return size when no zero area is found
media: s5p-mfc: Treat bitmap size as allocation failure
crypto: ccp: Treat bitmap size as allocation failure
powerpc/msi: Treat bitmap size as allocation failure
ARM: dma-mapping: Treat bitmap size as allocation failure
bitmap: drop bitmap_next_set_region()
nodemask: reduce bitmap width to nr_node_ids in __nodemask_pr_numnodes()
bitmap: Properly initialise destination bitmap for scatter & gather test
lib/bitmap-str: get rid of cpumap_print_to_pagebuf()
perf: Use sysfs_emit() for cpumask show callbacks
PCI/sysfs: Use sysfs_emit() for cpumask show callbacks
RDMA/hfi1: Use sysfs_emit() for cpumask show helper
hwtracing: hisi_ptt: Use sysfs_emit() for cpumask show
fpga: dfl-fme-perf: Use sysfs_emit() for cpumask show
devfreq: Use sysfs_emit() for cpumask show callbacks
cpu: Use sysfs_emit() for cpumask show callback
x86/events: Use sysfs_emit() for cpumask show callbacks
powerpc: Use sysfs_emit() for cpumask show callbacks
arm: Use sysfs_emit() for cpumask show callbacks
...

show more ...

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 p

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.

Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
Tested-by: Eliot Courtney <ecourtney@nvidia.com>
Reviewed-by: Eliot Courtney <ecourtney@nvidia.com>
Signed-off-by: Yury Norov <ynorov@nvidia.com>

show more ...