kernel/linux.git/include/linux/find.h, branch linux-6.9.y

lib/find: optimize find_*_bit_wrap

2023-12-03T18:28:17+00:00

When an offset is 0, there's no need to search a bitmap from the beginning after the 1st search failed, because each bit has already been tested. Signed-off-by: Yury Norov

lib/find_bit: Fix the code comments about find_next_bit_wrap

2023-12-03T18:28:16+00:00

The function find_next_bit_wrap only has one memory region to search on. Adjust the comments. Signed-off-by: Guanjun Signed-off-by: Yury Norov

cpumask: introduce for_each_cpu_or

2023-03-19T17:02:04+00:00

Equivalent of for_each_cpu_and, except it ORs the two masks together so it iterates all the CPUs present in either mask. Signed-off-by: Dave Chinner Reviewed-by: Darrick J. Wong Signed-off-by: Darrick J. Wong

lib/find: introduce find_nth_and_andnot_bit

2023-02-08T02:20:00+00:00

In the following patches the function is used to implement in-place bitmaps traversing without storing intermediate result in temporary bitmaps. Signed-off-by: Yury Norov Acked-by: Tariq Toukan Reviewed-by: Jacob Keller Reviewed-by: Peter Lafreniere Signed-off-by: Jakub Kicinski

cpumask: Introduce for_each_cpu_andnot()

2022-10-06T12:57:36+00:00

for_each_cpu_and() is very convenient as it saves having to allocate a temporary cpumask to store the result of cpumask_and(). The same issue applies to cpumask_andnot() which doesn't actually need temporary storage for iteration purposes. Following what has been done for for_each_cpu_and(), introduce for_each_cpu_andnot(). Signed-off-by: Valentin Schneider

lib/find_bit: Introduce find_next_andnot_bit()

2022-10-06T12:57:36+00:00

In preparation of introducing for_each_cpu_andnot(), add a variant of find_next_bit() that negate the bits in @addr2 when ANDing them with the bits in @addr1. Signed-off-by: Valentin Schneider

lib/find: optimize for_each() macros

2022-10-01T17:22:58+00:00

Moving an iterator of the macros inside conditional part of for-loop helps to generate a better code. It had been first implemented in commit 7baac8b91f9871ba ("cpumask: make for_each_cpu_mask a bit smaller"). Now that cpumask for-loops are the aliases to bitmap loops, it's worth to optimize them the same way. Bloat-o-meter says: add/remove: 8/12 grow/shrink: 147/592 up/down: 4876/-24416 (-19540) Signed-off-by: Yury Norov

lib/bitmap: introduce for_each_set_bit_wrap() macro

2022-10-01T17:22:57+00:00

Add for_each_set_bit_wrap() macro and use it in for_each_cpu_wrap(). The new macro is based on __for_each_wrap() iterator, which is simpler and smaller than cpumask_next_wrap(). Signed-off-by: Yury Norov

lib/find_bit: add find_next{,_and}_bit_wrap

2022-10-01T17:22:57+00:00

The helper is better optimized for the worst case: in case of empty cpumask, current code traverses 2 * size: next = cpumask_next_and(prev, src1p, src2p); if (next >= nr_cpu_ids) next = cpumask_first_and(src1p, src2p); At bitmap level we can stop earlier after checking 'size + offset' bits. Signed-off-by: Yury Norov

cpumask: switch for_each_cpu{,_not} to use for_each_bit()

2022-10-01T17:22:57+00:00

The difference between for_each_cpu() and for_each_set_bit() is that the latter uses cpumask_next() instead of find_next_bit(), and so calls cpumask_check(). This check is useless because the iterator value is not provided by user. It generates false-positives for the very last iteration of for_each_cpu(). Signed-off-by: Yury Norov