From c56f97c5c71f17d781461d44acb777cd21521b81 Mon Sep 17 00:00:00 2001 From: "Yury Norov [NVIDIA]" Date: Thu, 19 Jun 2025 14:26:23 -0400 Subject: bitmap: generalize node_random() 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]" --- lib/find_bit.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'lib') 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 #include #include +#include /* * 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); -- cgit v1.2.3 From dcb23e1878013dd04122122ed8eba35f354a091b Mon Sep 17 00:00:00 2001 From: Vincent Mailhol Date: Mon, 9 Jun 2025 11:45:47 +0900 Subject: test_bits: add tests for __GENMASK() and __GENMASK_ULL() The definitions of GENMASK() and GENMASK_ULL() do not depend any more on __GENMASK() and __GENMASK_ULL(). Duplicate the existing unit tests so that __GENMASK{,ULL}() are still covered. Because __GENMASK() and __GENMASK_ULL() do use GENMASK_INPUT_CHECK(), drop the TEST_GENMASK_FAILURES negative tests. It would be good to have a small assembly test case for GENMASK*() in case somebody decides to unify both in the future. However, I lack expertise in assembly to do so. Instead add a FIXME message to highlight the absence of the asm unit test. Signed-off-by: Vincent Mailhol Reviewed-by: Lucas De Marchi Signed-off-by: Yury Norov (NVIDIA) --- lib/tests/test_bits.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'lib') 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), -- cgit v1.2.3