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 <ynorov@nvidia.com>
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 <yury.norov@gmail.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: sunyi <279644543@qq.com>
Signed-off-by: Yury Norov <ynorov@nvidia.com>
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 <ynorov@nvidia.com>
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 <tglx@linutronix.de>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Link: https://patch.msgid.link/20251119172549.448263340@linutronix.de
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 <yury.norov@gmail.com>
Reviewed-by: Jacob Keller <jacob.e.keller@intel.com>
Signed-off-by: Paolo Abeni <pabeni@redhat.com>
lib/bitmap.c and corresponding include/linux/bitmap.h are intended to
hold functions related to operations on bitmaps, like bitmap_shift or
bitmap_set. Historically, some string-related operations like
bitmap_parse are also reside in lib/bitmap.c.
Now that the subsystem evolves, string-related bitmap operations became a
significant part of the file. Because they are quite different from the
other bitmap functions by nature, it's worth to split them to a separate
source/header files.
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
CC: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Besides the fact it's not used anywhere it should be implemented
differently, i.e. via helpers from linux/byteorder/generic.h.
Yet the helpers themselves need to be introduced first.
Also note, the function lacks of the test cases, they must be provided.
Hence, drop the current dead code for good.
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
bitmap_{from,to}_arr64() optimization is overly optimistic on 32-bit LE
architectures when it's wired to bitmap_copy_clear_tail().
bitmap_copy_clear_tail() takes care of unused bits in the bitmap up to
the next word boundary. But on 32-bit machines when copying bits from
bitmap to array of 64-bit words, it's expected that the unused part of
a recipient array must be cleared up to 64-bit boundary, so the last 4
bytes may stay untouched when nbits % 64 <= 32.
While the copying part of the optimization works correct, that clear-tail
trick makes corresponding tests reasonably fail:
test_bitmap: bitmap_to_arr64(nbits == 1): tail is not safely cleared: 0xa5a5a5a500000001 (must be 0x0000000000000001)
Fix it by removing bitmap_{from,to}_arr64() optimization for 32-bit LE
arches.
Reported-by: Guenter Roeck <linux@roeck-us.net>
Link: https://lore.kernel.org/lkml/20230225184702.GA3587246@roeck-us.net/
Fixes: 0a97953fd2 ("lib: add bitmap_{from,to}_arr64")
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Tested-by: Guenter Roeck <linux@roeck-us.net>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Alexander Lobakin <aleksander.lobakin@intel.com>
The function calculates Hamming weight of (bitmap1 & bitmap2). Now we
have to do like this:
tmp = bitmap_alloc(nbits);
bitmap_and(tmp, map1, map2, nbits);
weight = bitmap_weight(tmp, nbits);
bitmap_free(tmp);
This requires additional memory, adds pressure on alloc subsystem, and
way less cache-friendly than just:
weight = bitmap_weight_and(map1, map2, nbits);
The following patches apply it for cpumask functions.
Signed-off-by: Yury Norov <yury.norov@gmail.com>
__bitmap_weight() is not to be used directly in the kernel code because
it's a helper for bitmap_weight(). Switch everything to bitmap_weight().
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Pull bitmap updates from Yury Norov:
- fix the duplicated comments on bitmap_to_arr64() (Qu Wenruo)
- optimize out non-atomic bitops on compile-time constants (Alexander
Lobakin)
- cleanup bitmap-related headers (Yury Norov)
- x86/olpc: fix 'logical not is only applied to the left hand side'
(Alexander Lobakin)
- lib/nodemask: inline wrappers around bitmap (Yury Norov)
* tag 'bitmap-6.0-rc1' of https://github.com/norov/linux: (26 commits)
lib/nodemask: inline next_node_in() and node_random()
powerpc: drop dependency on <asm/machdep.h> in archrandom.h
x86/olpc: fix 'logical not is only applied to the left hand side'
lib/cpumask: move some one-line wrappers to header file
headers/deps: mm: align MANITAINERS and Docs with new gfp.h structure
headers/deps: mm: Split <linux/gfp_types.h> out of <linux/gfp.h>
headers/deps: mm: Optimize <linux/gfp.h> header dependencies
lib/cpumask: move trivial wrappers around find_bit to the header
lib/cpumask: change return types to unsigned where appropriate
cpumask: change return types to bool where appropriate
lib/bitmap: change type of bitmap_weight to unsigned long
lib/bitmap: change return types to bool where appropriate
arm: align find_bit declarations with generic kernel
iommu/vt-d: avoid invalid memory access via node_online(NUMA_NO_NODE)
lib/test_bitmap: test the tail after bitmap_to_arr64()
lib/bitmap: fix off-by-one in bitmap_to_arr64()
lib: test_bitmap: add compile-time optimization/evaluations assertions
bitmap: don't assume compiler evaluates small mem*() builtins calls
net/ice: fix initializing the bitmap in the switch code
bitops: let optimize out non-atomic bitops on compile-time constants
...
bitmap_weight() doesn't return negative values, so change it's type
to unsigned long. It may help compiler to generate better code and
catch bugs.
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Some bitmap functions return boolean results in int variables. Fix it
by changing return types to bool.
Signed-off-by: Yury Norov <yury.norov@gmail.com>
GENMASK*() family takes the first and the last bits of the mask
*including* them. So, with the current code bitmap_to_arr64()
doesn't clear the tail properly:
nbits % exp mask must be
1 GENMASK(1, 0) 0x3 0x1
...
63 GENMASK(63, 0) 0xffffffffffffffff 0x7fffffffffffffff
This was found by making the function always available instead of
32-bit BE systems only (for reusing in some new functionality).
Turn the number of bits into the last bit set by subtracting 1.
@nbits is already checked to be positive beforehand.
Fixes: 0a97953fd2 ("lib: add bitmap_{from,to}_arr64")
Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Yury Norov
sunyiandYury Norov
Thomas GleixnerandPeter Zijlstra
Yury NorovandPaolo Abeni
Andy ShevchenkoandYury Norov
Jonathan NeuschäferandYury Norov
Linus Torvalds
Alexander LobakinandYury Norov
Kees CookandYury Norov