kernel/linux.git/lib/find_bit.c, branch v7.0-rc7

lib/find_bit: fix uninitialized variable use in FIND_NTH_BIT

2026-02-08T23:47:29+00:00

In the FIND_NTH_BIT macro, if the 'size' parameter is 0, both the loop conditions and the modulo condition are not met. Consequently, the 'tmp' variable remains uninitialized before being used in the 'found' label. This results in the following smatch errors: lib/find_bit.c:164 __find_nth_bit() error: uninitialized symbol 'tmp'. lib/find_bit.c:171 __find_nth_and_bit() error: uninitialized symbol 'tmp'. lib/find_bit.c:178 __find_nth_andnot_bit() error: uninitialized symbol 'tmp'. lib/find_bit.c:187 __find_nth_and_andnot_bit() error: uninitialized symbol 'tmp'. Initialize 'tmp' to 0 to ensure that fns() operates on a zeroed value (no bits set) when size is 0, preventing the use of garbage values. [Yury: size == 0 is generally a sign of error on client side, and in this case, any returned value is OK because the returned value would be greater than 'size'. Applying the patch to reduce the checker noise.] Signed-off-by: Lee Yongjun Signed-off-by: Yury Norov

bitmap: generalize node_random()

2025-07-08T23:11:57+00:00

Generalize node_random() and make it available to general bitmaps and cpumasks users. Notice, find_first_bit() is generally faster than find_nth_bit(), and we employ it when there's a single set bit in the bitmap. See commit 3e061d924fe9c7b4 ("lib/nodemask: optimize node_random for nodemask with single NUMA node"). CC: Andrew Morton Signed-off-by: "Yury Norov [NVIDIA]"

find: Add find_first_andnot_bit()

2025-05-15T18:24:40+00:00

The function helps to implement cpumask_andnot() APIs. Signed-off-by: Yury Norov [NVIDIA] Signed-off-by: James Morse Signed-off-by: Borislav Petkov (AMD) Reviewed-by: James Morse Reviewed-by: Reinette Chatre Reviewed-by: Fenghua Yu Tested-by: James Morse Tested-by: Tony Luck Tested-by: Fenghua Yu Link: https://lore.kernel.org/20250515165855.31452-3-james.morse@arm.com

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

2024-05-21T22:29:01+00:00

Pull bitmap updates from Yury Norov: - topology_span_sane() optimization from Kyle Meyer - fns() rework from Kuan-Wei Chiu (used in cpumask_local_spread() and other places) - headers cleanup from Andy - add a MAINTAINERS record for bitops API * tag 'bitmap-for-6.10v2' of https://github.com/norov/linux: usercopy: Don't use "proxy" headers bitops: Move aligned_byte_mask() to wordpart.h MAINTAINERS: add BITOPS API record bitmap: relax find_nth_bit() limitation on return value lib: make test_bitops compilable into the kernel image bitops: Optimize fns() for improved performance lib/test_bitops: Add benchmark test for fns() Compiler Attributes: Add __always_used macro sched/topology: Optimize topology_span_sane() cpumask: Add for_each_cpu_from()

bitmap: relax find_nth_bit() limitation on return value

2024-05-09T16:25:08+00:00

The function claims to return the bitmap size, if Nth bit doesn't exist. This rule is violated in inline case because the fns() that is used there doesn't know anything about size of the bitmap. So, relax this requirement to '>= size', and make the outline implementation a bit cheaper. All in-tree kernel users of find_nth_bit() are safe against that. Reported-by: Rasmus Villemoes Closes: https://lore.kernel.org/all/Zi50cAgR8nZvgLa3@yury-ThinkPad/T/#m6da806a0525e74dcc91f35e5f20766ed4e853e8a Signed-off-by: Yury Norov

cpumask: Introduce cpumask_first_and_and()

2024-04-24T19:23:49+00:00

Introduce cpumask_first_and_and() to get intersection between 3 cpumasks, free of any intermediate cpumask variable. Instead, cpumask_first_and_and() works in-place with all inputs and produces desired output directly. Signed-off-by: Dawei Li Signed-off-by: Thomas Gleixner Acked-by: Yury Norov Link: https://lore.kernel.org/r/20240416085454.3547175-2-dawei.li@shingroup.cn

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

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: add find_nth{,_and,_andnot}_bit()

2022-09-26T19:19:12+00:00

Kernel lacks for a function that searches for Nth bit in a bitmap. Usually people do it like this: for_each_set_bit(bit, mask, size) if (n-- == 0) return bit; We can do it more efficiently, if we: 1. find a word containing Nth bit, using hweight(); and 2. find the bit, using a helper fns(), that works similarly to __ffs() and ffz(). fns() is implemented as a simple loop. For x86_64, there's PDEP instruction to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the most of improvement comes from using hweight(), so I kept fns() simple. New find_nth_bit() is ~70 times faster on x86_64/kvm in find_bit benchmark: find_nth_bit: 7154190 ns, 16411 iterations for_each_bit: 505493126 ns, 16315 iterations With all that, a family of 3 new functions is added, and used where appropriate in the following patches. Signed-off-by: Yury Norov