From dc34d5036692c614eef23c1130ee42a201c316bf Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Fri, 24 Jun 2022 14:13:13 +0200 Subject: lib: test_bitmap: add compile-time optimization/evaluations assertions Add a function to the bitmap test suite, which will ensure that compilers are able to evaluate operations performed by the bitops/bitmap helpers to compile-time constants when all of the arguments are compile-time constants as well, or trigger a build bug otherwise. This should work on all architectures and all the optimization levels supported by Kbuild. The function doesn't perform any runtime tests and gets optimized out to nothing after passing the build assertions. Unfortunately, Clang for s390 is currently broken (up to the latest Git snapshots) -- see the comment in the code -- so for now there's a small workaround for it which doesn't alter the logics. Hope we'll be able to remove it one day (bugreport is on its way). Suggested-by: Yury Norov Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/test_bitmap.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) (limited to 'lib') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index d5923a640457..25967cfa4ab2 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -869,6 +869,67 @@ static void __init test_bitmap_print_buf(void) } } +static void __init test_bitmap_const_eval(void) +{ + DECLARE_BITMAP(bitmap, BITS_PER_LONG); + unsigned long initvar = BIT(2); + unsigned long bitopvar = 0; + unsigned long var = 0; + int res; + + /* + * Compilers must be able to optimize all of those to compile-time + * constants on any supported optimization level (-O2, -Os) and any + * architecture. Otherwise, trigger a build bug. + * The whole function gets optimized out then, there's nothing to do + * in runtime. + */ + + /* + * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`. + * Clang on s390 optimizes bitops at compile-time as intended, but at + * the same time stops treating @bitmap and @bitopvar as compile-time + * constants after regular test_bit() is executed, thus triggering the + * build bugs below. So, call const_test_bit() there directly until + * the compiler is fixed. + */ + bitmap_clear(bitmap, 0, BITS_PER_LONG); +#if defined(__s390__) && defined(__clang__) + if (!const_test_bit(7, bitmap)) +#else + if (!test_bit(7, bitmap)) +#endif + bitmap_set(bitmap, 5, 2); + + /* Equals to `unsigned long bitopvar = BIT(20)` */ + __change_bit(31, &bitopvar); + bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG); + + /* Equals to `unsigned long var = BIT(25)` */ + var |= BIT(25); + if (var & BIT(0)) + var ^= GENMASK(9, 6); + + /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */ + res = bitmap_weight(bitmap, 20); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(res != 2); + + /* !(BIT(31) & BIT(18)) == 1 */ + res = !test_bit(18, &bitopvar); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(!res); + + /* BIT(2) & GENMASK(14, 8) == 0 */ + res = initvar & GENMASK(14, 8); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(res); + + /* ~BIT(25) */ + BUILD_BUG_ON(!__builtin_constant_p(~var)); + BUILD_BUG_ON(~var != ~BIT(25)); +} + static void __init selftest(void) { test_zero_clear(); @@ -884,6 +945,7 @@ static void __init selftest(void) test_for_each_set_clump8(); test_bitmap_cut(); test_bitmap_print_buf(); + test_bitmap_const_eval(); } KSTM_MODULE_LOADERS(test_bitmap); -- cgit From 428bc098635680a664779f26f24fe9197d186172 Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Mon, 11 Jul 2022 20:09:29 +0200 Subject: lib/bitmap: fix off-by-one in bitmap_to_arr64() 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: 0a97953fd221 ("lib: add bitmap_{from,to}_arr64") Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index b18e31ea6e66..e903e13c62e1 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -1564,7 +1564,7 @@ void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits) /* Clear tail bits in the last element of array beyond nbits. */ if (nbits % 64) - buf[-1] &= GENMASK_ULL(nbits % 64, 0); + buf[-1] &= GENMASK_ULL((nbits - 1) % 64, 0); } EXPORT_SYMBOL(bitmap_to_arr64); #endif -- cgit From 30fd8cdf53a02b54b199043fcf1857db76e8badc Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Mon, 11 Jul 2022 20:09:30 +0200 Subject: lib/test_bitmap: test the tail after bitmap_to_arr64() Currently, test_bitmap_arr64() only tests bitmap_to_arr64()'s sanity by comparing the result of double-conversion (bm -> arr64 -> bm2) with the input bitmap. However, this may be not enough when one side hides bugs of the second one (e.g. tail clearing, which is being performed by both). Expand the tests and check the tail of the actual arr64 used as a temporary buffer for double-converting. Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/test_bitmap.c | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'lib') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 25967cfa4ab2..98754ff9fe68 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -604,6 +604,12 @@ static void __init test_bitmap_arr64(void) pr_err("bitmap_copy_arr64(nbits == %d:" " tail is not safely cleared: %d\n", nbits, next_bit); + if ((nbits % 64) && + (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) + pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n", + nbits, arr[(nbits - 1) / 64], + GENMASK_ULL((nbits - 1) % 64, 0)); + if (nbits < EXP1_IN_BITS - 64) expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5); } -- cgit From e2863a78593d638d3924a6f67900c4820034f349 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:24 -0700 Subject: lib/bitmap: change return types to bool where appropriate Some bitmap functions return boolean results in int variables. Fix it by changing return types to bool. Signed-off-by: Yury Norov --- lib/bitmap.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index e903e13c62e1..9bc80f5bf149 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -237,7 +237,7 @@ void bitmap_cut(unsigned long *dst, const unsigned long *src, } EXPORT_SYMBOL(bitmap_cut); -int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, +bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits) { unsigned int k; @@ -275,7 +275,7 @@ void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_xor); -int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, +bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits) { unsigned int k; -- cgit From 4dea97f8636d0514befc9fc5cf342b351b7d0e20 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:25 -0700 Subject: lib/bitmap: change type of bitmap_weight to unsigned long 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 --- lib/bitmap.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index 9bc80f5bf149..2b67cd657692 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -333,10 +333,9 @@ bool __bitmap_subset(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_subset); -int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) +unsigned long __bitmap_weight(const unsigned long *bitmap, unsigned int bits) { - unsigned int k, lim = bits/BITS_PER_LONG; - int w = 0; + unsigned long k, w = 0, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; k++) w += hweight_long(bitmap[k]); -- cgit From 8b6b795d9bfc031a8953c40fac8d3cf67e1a4d3d Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:27 -0700 Subject: lib/cpumask: change return types to unsigned where appropriate Switch return types to unsigned int where return values cannot be negative. Signed-off-by: Yury Norov --- lib/cpumask.c | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/cpumask.c b/lib/cpumask.c index a971a82d2f43..da68f6bbde44 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -31,7 +31,7 @@ EXPORT_SYMBOL(cpumask_next); * * Returns >= nr_cpu_ids if no further cpus set in both. */ -int cpumask_next_and(int n, const struct cpumask *src1p, +unsigned int cpumask_next_and(int n, const struct cpumask *src1p, const struct cpumask *src2p) { /* -1 is a legal arg here. */ @@ -50,7 +50,7 @@ EXPORT_SYMBOL(cpumask_next_and); * Often used to find any cpu but smp_processor_id() in a mask. * Returns >= nr_cpu_ids if no cpus set. */ -int cpumask_any_but(const struct cpumask *mask, unsigned int cpu) +unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu) { unsigned int i; @@ -74,9 +74,9 @@ EXPORT_SYMBOL(cpumask_any_but); * Note: the @wrap argument is required for the start condition when * we cannot assume @start is set in @mask. */ -int cpumask_next_wrap(int n, const struct cpumask *mask, int start, bool wrap) +unsigned int cpumask_next_wrap(int n, const struct cpumask *mask, int start, bool wrap) { - int next; + unsigned int next; again: next = cpumask_next(n, mask); @@ -205,7 +205,7 @@ void __init free_bootmem_cpumask_var(cpumask_var_t mask) */ unsigned int cpumask_local_spread(unsigned int i, int node) { - int cpu; + unsigned int cpu; /* Wrap: we always want a cpu. */ i %= num_online_cpus(); @@ -243,10 +243,10 @@ static DEFINE_PER_CPU(int, distribute_cpu_mask_prev); * * Returns >= nr_cpu_ids if the intersection is empty. */ -int cpumask_any_and_distribute(const struct cpumask *src1p, +unsigned int cpumask_any_and_distribute(const struct cpumask *src1p, const struct cpumask *src2p) { - int next, prev; + unsigned int next, prev; /* NOTE: our first selection will skip 0. */ prev = __this_cpu_read(distribute_cpu_mask_prev); @@ -262,9 +262,9 @@ int cpumask_any_and_distribute(const struct cpumask *src1p, } EXPORT_SYMBOL(cpumask_any_and_distribute); -int cpumask_any_distribute(const struct cpumask *srcp) +unsigned int cpumask_any_distribute(const struct cpumask *srcp) { - int next, prev; + unsigned int next, prev; /* NOTE: our first selection will skip 0. */ prev = __this_cpu_read(distribute_cpu_mask_prev); -- cgit From 9b2e70860ef2f0d74b6d9e57929d57b14481b9c9 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:28 -0700 Subject: lib/cpumask: move trivial wrappers around find_bit to the header To avoid circular dependencies, cpumask keeps simple (almost) one-line wrappers around find_bit() in a c-file. Commit 47d8c15615c0a2 ("include: move find.h from asm_generic to linux") moved find.h header out of asm_generic include path, and it helped to fix many circular dependencies, including some in cpumask.h. This patch moves those one-liners to header files. Signed-off-by: Yury Norov --- lib/cpumask.c | 55 ------------------------------------------------------- 1 file changed, 55 deletions(-) (limited to 'lib') diff --git a/lib/cpumask.c b/lib/cpumask.c index da68f6bbde44..cb7262ff8633 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -7,61 +7,6 @@ #include #include -/** - * cpumask_next - get the next cpu in a cpumask - * @n: the cpu prior to the place to search (ie. return will be > @n) - * @srcp: the cpumask pointer - * - * Returns >= nr_cpu_ids if no further cpus set. - */ -unsigned int cpumask_next(int n, const struct cpumask *srcp) -{ - /* -1 is a legal arg here. */ - if (n != -1) - cpumask_check(n); - return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1); -} -EXPORT_SYMBOL(cpumask_next); - -/** - * cpumask_next_and - get the next cpu in *src1p & *src2p - * @n: the cpu prior to the place to search (ie. return will be > @n) - * @src1p: the first cpumask pointer - * @src2p: the second cpumask pointer - * - * Returns >= nr_cpu_ids if no further cpus set in both. - */ -unsigned int cpumask_next_and(int n, const struct cpumask *src1p, - const struct cpumask *src2p) -{ - /* -1 is a legal arg here. */ - if (n != -1) - cpumask_check(n); - return find_next_and_bit(cpumask_bits(src1p), cpumask_bits(src2p), - nr_cpumask_bits, n + 1); -} -EXPORT_SYMBOL(cpumask_next_and); - -/** - * cpumask_any_but - return a "random" in a cpumask, but not this one. - * @mask: the cpumask to search - * @cpu: the cpu to ignore. - * - * Often used to find any cpu but smp_processor_id() in a mask. - * Returns >= nr_cpu_ids if no cpus set. - */ -unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu) -{ - unsigned int i; - - cpumask_check(cpu); - for_each_cpu(i, mask) - if (i != cpu) - break; - return i; -} -EXPORT_SYMBOL(cpumask_any_but); - /** * cpumask_next_wrap - helper to implement for_each_cpu_wrap * @n: the cpu prior to the place to search -- cgit From f0dd891dd5a1d6dc6c9d486333aac4f433f17d17 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Fri, 1 Jul 2022 05:54:30 -0700 Subject: lib/cpumask: move some one-line wrappers to header file After moving gfp flags to a separate header, it's possible to move some cpumask allocators into headers, and avoid creating real functions. Signed-off-by: Yury Norov --- lib/cpumask.c | 28 ---------------------------- 1 file changed, 28 deletions(-) (limited to 'lib') diff --git a/lib/cpumask.c b/lib/cpumask.c index cb7262ff8633..f0ae119be8c4 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -70,34 +70,6 @@ bool alloc_cpumask_var_node(cpumask_var_t *mask, gfp_t flags, int node) } EXPORT_SYMBOL(alloc_cpumask_var_node); -bool zalloc_cpumask_var_node(cpumask_var_t *mask, gfp_t flags, int node) -{ - return alloc_cpumask_var_node(mask, flags | __GFP_ZERO, node); -} -EXPORT_SYMBOL(zalloc_cpumask_var_node); - -/** - * alloc_cpumask_var - allocate a struct cpumask - * @mask: pointer to cpumask_var_t where the cpumask is returned - * @flags: GFP_ flags - * - * Only defined when CONFIG_CPUMASK_OFFSTACK=y, otherwise is - * a nop returning a constant 1 (in ). - * - * See alloc_cpumask_var_node. - */ -bool alloc_cpumask_var(cpumask_var_t *mask, gfp_t flags) -{ - return alloc_cpumask_var_node(mask, flags, NUMA_NO_NODE); -} -EXPORT_SYMBOL(alloc_cpumask_var); - -bool zalloc_cpumask_var(cpumask_var_t *mask, gfp_t flags) -{ - return alloc_cpumask_var(mask, flags | __GFP_ZERO); -} -EXPORT_SYMBOL(zalloc_cpumask_var); - /** * alloc_bootmem_cpumask_var - allocate a struct cpumask from the bootmem arena. * @mask: pointer to cpumask_var_t where the cpumask is returned -- cgit From 36d4b36b69590fed99356a4426c940a253a93800 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 25 Jul 2022 09:39:17 -0700 Subject: lib/nodemask: inline next_node_in() and node_random() The functions are pretty thin wrappers around find_bit engine, and keeping them in c-file prevents compiler from small_const_nbits() optimization, which must take place for all systems with MAX_NUMNODES less than BITS_PER_LONG (default is 16 for me). Moving them to header file doesn't blow up the kernel size: add/remove: 1/2 grow/shrink: 9/5 up/down: 968/-88 (880) CC: Andy Shevchenko CC: Benjamin Herrenschmidt CC: Michael Ellerman CC: Paul Mackerras CC: Rasmus Villemoes CC: Stephen Rothwell CC: linuxppc-dev@lists.ozlabs.org Signed-off-by: Yury Norov --- lib/Makefile | 2 +- lib/nodemask.c | 8 -------- 2 files changed, 1 insertion(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index f99bf61f8bbc..731cea0342d1 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -33,7 +33,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ flex_proportions.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ - nmi_backtrace.o nodemask.o win_minmax.o memcat_p.o \ + nmi_backtrace.o win_minmax.o memcat_p.o \ buildid.o lib-$(CONFIG_PRINTK) += dump_stack.o diff --git a/lib/nodemask.c b/lib/nodemask.c index e22647f5181b..b8a433d16b51 100644 --- a/lib/nodemask.c +++ b/lib/nodemask.c @@ -3,14 +3,6 @@ #include #include -unsigned int __next_node_in(int node, const nodemask_t *srcp) -{ - unsigned int ret = __next_node(node, srcp); - - if (ret == MAX_NUMNODES) - ret = __first_node(srcp); - return ret; -} EXPORT_SYMBOL(__next_node_in); #ifdef CONFIG_NUMA -- cgit