kernel/linux.git/lib/bitmap.c, branch v7.3-rc1

bitmap: Return size when no zero area is found

2026-07-22T19:38:38+00:00

Return the bitmap size, rather than size + 1, when bitmap_find_next_zero_area_off() cannot find a suitable area. This matches the conventional find_bit() failure sentinel and still lets callers detect failure with an out-of-range check. Document the public failure contract as a value greater than or equal to the bitmap size, without requiring callers to depend on the exact sentinel. Signed-off-by: Yury Norov

lib: bitmap: optimize bitmap_find_next_zero_area_off()

2026-07-22T19:38:37+00:00

Finding a contiguous free region in a highly fragmented bitmap is not easy and may require many repeated attempts. Therefore, find_next_bit(map, end, index) is not the optimal choice. This is because there may be multiple scattered free regions within the range [index, end) and none of them will meet the length requirement of @nr. Instead, it's sufficient to directly find the last bit within the range [index, end), thus reducing unnecessary repeated calls. An example of a bitmap: Bits 0-3: cleared(4 bits) Bits 4-5: set (2 bits) Bits 6-8: cleared(4 bits) Bits 9-10: set (2 bits) Bits 11-20: cleared(10 bits) The goal is to find a 10-bit free region. The old code logic is as follows: find_next_zero_bit(start = 0, find bit 0) -> find_next_bit(find bit 4) -> next loop -> find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 10, find bit 11) -> success The new code logic is as follows: find_next_zero_bit(start = 0, find bit 0) -> find_last_bit(find bit 9) -> next loop -> find_next_zero_bit(start = 10, find bit 11) -> success Performance test results on my hardware(use lib/find_bit_benchmark.c): before after change p-value dense 1211 688 -43.2% 8.3e-11 sparse 13.3 13.4 0.8% 0.27 Yury: The less micro-benchmark kselftest/dmabuf-heaps/dmabuf-heap gives even better numbers: Metric Before After Change Trace span 194.0 ms 87.1 ms -55.1% Total CMA alloc time 48.46 ms 16.11 ms -66.8% Avg alloc latency 184.94 us 61.49 us -66.8% Median alloc latency 73.72 us 20.59 us -72.1% p90 alloc latency 329.76 us 55.63 us -83.1% p99 alloc latency 1866.76 us 859.83 us -53.9% Max alloc latency 4821.91 us 2324.41 us -51.8% By request size: Request Before Avg After Avg Change 1 page 79.68 us 34.47 us -56.7% 256 pages 285.50 us 87.30 us -69.4% Co-developed-by: Yury Norov Signed-off-by: Yury Norov Signed-off-by: sunyi <279644543@qq.com> Signed-off-by: Yury Norov

bitmap: introduce bitmap_weighted_xor()

2026-04-02T00:03:07+00:00

The function helps to XOR bitmaps and calculate Hamming weight of the result in one pass. Reviewed-by: Aleksandr Loktionov Reviewed-by: Jacob Keller Signed-off-by: Yury Norov

bitmap: add test_zero_nbits()

2026-03-24T17:39:53+00:00

In most real-life cases, 0-length bitmap provided by user is a sign of an error. The API doesn't provide any guarantees on returned value, and the bitmap pointers are not dereferenced. Signed-off-by: Yury Norov

cpumask: Introduce cpumask_weighted_or()

2025-11-20T11:14:54+00:00

CID management OR's two cpumasks and then calculates the weight on the result. That's inefficient as that has to walk the same stuff twice. As this is done with runqueue lock held, there is a real benefit of speeding this up. Depending on the system this results in 10-20% less cycles spent with runqueue lock held for a 4K cpumask. Provide cpumask_weighted_or() and the corresponding bitmap functions which return the weight of the OR result right away. Signed-off-by: Thomas Gleixner Signed-off-by: Peter Zijlstra (Intel) Reviewed-by: Yury Norov (NVIDIA) Reviewed-by: Mathieu Desnoyers Link: https://patch.msgid.link/20251119172549.448263340@linutronix.de

cpumask: add cpumask_weight_andnot()

2024-02-01T12:06:40+00:00

Similarly to cpumask_weight_and(), cpumask_weight_andnot() is a handy helper that may help to avoid creating an intermediate mask just to calculate number of bits that set in a 1st given mask, and clear in 2nd one. Signed-off-by: Yury Norov Reviewed-by: Jacob Keller Signed-off-by: Paolo Abeni

bitmap: move bitmap_*_region() functions to bitmap.h

2023-10-16T23:14:45+00:00

Now that bitmap_*_region() functions are implemented as thin wrappers around others, it's worth to move them to the header, as it opens room for compile-time optimizations. CC: Andy Shevchenko CC: Rasmus Villemoes CC: Greg Kroah-Hartman Signed-off-by: Yury Norov

bitmap: drop _reg_op() function

2023-10-15T03:25:23+00:00

Now that all _reg_op() users are switched to alternative functions, _reg_op() machinery is not needed anymore. CC: Andy Shevchenko CC: Rasmus Villemoes Signed-off-by: Yury Norov

bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()

2023-10-15T03:25:22+00:00

_reg_op(REG_OP_ISFREE) can be trivially replaced with find_next_bit(). Doing that opens room for potential small_const_nbits() optimization. CC: Andy Shevchenko CC: Rasmus Villemoes Signed-off-by: Yury Norov

bitmap: replace _reg_op(REG_OP_RELEASE) with bitmap_clear()

2023-10-15T03:25:22+00:00

_reg_op(REG_OP_RELEASE) duplicates bitmap_clear(). CC: Andy Shevchenko CC: Rasmus Villemoes Signed-off-by: Yury Norov