diff options
| author | Linus Torvalds <torvalds@linux-foundation.org> | 2025-07-31 16:52:32 -0700 |
|---|---|---|
| committer | Linus Torvalds <torvalds@linux-foundation.org> | 2025-07-31 16:52:32 -0700 |
| commit | f2d282e1dfb3d8cb95b5ccdea43f2411f27201db (patch) | |
| tree | 26d837c473d4a16edd7e956ef1694631dce4b041 /lib | |
| parent | 6a68cec16b647791d448102376a7eec2820e874f (diff) | |
| parent | e2b02d382ae0cb90697e8529dfd3f93bf8c6905c (diff) | |
| download | linux-f2d282e1dfb3d8cb95b5ccdea43f2411f27201db.tar.gz linux-f2d282e1dfb3d8cb95b5ccdea43f2411f27201db.zip | |
Merge tag 'bitmap-for-6.17' of https://github.com/norov/linux
Pull bitmap updates from Yury Norov:
- find_random_bit() series (Yury)
- GENMASK() consolidation (Vincent)
- random cleanups (Shaopeng, Ben, Yury)
* tag 'bitmap-for-6.17' of https://github.com/norov/linux:
bitfield: Ensure the return values of helper functions are checked
test_bits: add tests for __GENMASK() and __GENMASK_ULL()
bits: unify the non-asm GENMASK*()
bits: split the definition of the asm and non-asm GENMASK*()
cpumask: Remove unnecessary cpumask_nth_andnot()
watchdog: fix opencoded cpumask_next_wrap() in watchdog_next_cpu()
clocksource: Improve randomness in clocksource_verify_choose_cpus()
cpumask: introduce cpumask_random()
bitmap: generalize node_random()
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/find_bit.c | 24 | ||||
| -rw-r--r-- | lib/tests/test_bits.c | 19 |
2 files changed, 43 insertions, 0 deletions
diff --git a/lib/find_bit.c b/lib/find_bit.c index 06b6342aa3ae..d4b5a29e3e72 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -18,6 +18,7 @@ #include <linux/math.h> #include <linux/minmax.h> #include <linux/swab.h> +#include <linux/random.h> /* * Common helper for find_bit() function family @@ -291,3 +292,26 @@ EXPORT_SYMBOL(_find_next_bit_le); #endif #endif /* __BIG_ENDIAN */ + +/** + * find_random_bit - find a set bit at random position + * @addr: The address to base the search on + * @size: The bitmap size in bits + * + * Returns: a position of a random set bit; >= @size otherwise + */ +unsigned long find_random_bit(const unsigned long *addr, unsigned long size) +{ + int w = bitmap_weight(addr, size); + + switch (w) { + case 0: + return size; + case 1: + /* Performance trick for single-bit bitmaps */ + return find_first_bit(addr, size); + default: + return find_nth_bit(addr, size, get_random_u32_below(w)); + } +} +EXPORT_SYMBOL(find_random_bit); diff --git a/lib/tests/test_bits.c b/lib/tests/test_bits.c index 47325b41515f..ab88e50d2edf 100644 --- a/lib/tests/test_bits.c +++ b/lib/tests/test_bits.c @@ -26,6 +26,23 @@ static_assert(assert_type(u16, GENMASK_U16(15, 0)) == U16_MAX); static_assert(assert_type(u32, GENMASK_U32(31, 0)) == U32_MAX); static_assert(assert_type(u64, GENMASK_U64(63, 0)) == U64_MAX); +/* FIXME: add a test case written in asm for GENMASK() and GENMASK_ULL() */ + +static void __genmask_test(struct kunit *test) +{ + KUNIT_EXPECT_EQ(test, 1ul, __GENMASK(0, 0)); + KUNIT_EXPECT_EQ(test, 3ul, __GENMASK(1, 0)); + KUNIT_EXPECT_EQ(test, 6ul, __GENMASK(2, 1)); + KUNIT_EXPECT_EQ(test, 0xFFFFFFFFul, __GENMASK(31, 0)); +} + +static void __genmask_ull_test(struct kunit *test) +{ + KUNIT_EXPECT_EQ(test, 1ull, __GENMASK_ULL(0, 0)); + KUNIT_EXPECT_EQ(test, 3ull, __GENMASK_ULL(1, 0)); + KUNIT_EXPECT_EQ(test, 0x000000ffffe00000ull, __GENMASK_ULL(39, 21)); + KUNIT_EXPECT_EQ(test, 0xffffffffffffffffull, __GENMASK_ULL(63, 0)); +} static void genmask_test(struct kunit *test) { @@ -123,6 +140,8 @@ static void genmask_input_check_test(struct kunit *test) static struct kunit_case bits_test_cases[] = { + KUNIT_CASE(__genmask_test), + KUNIT_CASE(__genmask_ull_test), KUNIT_CASE(genmask_test), KUNIT_CASE(genmask_ull_test), KUNIT_CASE(genmask_u128_test), |