* Re: [PATCH v1 1/1] bitmap: Refactor bitmap_read() and bitmap_write() to avoid too big shift [not found] <20261119191530.1716850-1-andriy.shevchenko@linux.intel.com> @ 2026-11-19 20:37 ` Yury Norov 2026-11-19 21:03 ` Andy Shevchenko 0 siblings, 1 reply; 3+ messages in thread From: Yury Norov @ 2026-11-19 20:37 UTC (permalink / raw) To: Andy Shevchenko Cc: linux-kernel, Yury Norov, Rasmus Villemoes, Jonathan Cameron, Chris Li, Luc Van Oostenryck, linux-sparse Hi Andy! + sparse people. On Thu, Nov 19, 2026 at 08:15:30PM +0100, Andy Shevchenko wrote: > While compiling ad4691.c I have noticed the following warnings: > > drivers/iio/adc/ad4691.c: note: in included file: > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > > Since the bitmap_read() is called with statically define 'start', > the 'space' local variable becomes equal to BITS_PER_LONG, or 64 on > 64-bit machines. The 'nbits' parameter is coming from the run-time > defined value. Static analyser doesn't see that the right shift > by 64-bit can't happen — the space >= nbits check guards that. > While Jonathan put it as false positive [1], we still can give a hint > to it without growing in the code (`bloat-o-meter` for above mentioned > driver shows no difference in size). So this is what this change does. Jonathan put it right. If the analyzer (assuming sparse?) throws false positives, we don't need to change the kernel. This is simply a wrong motivation. We need to improve sparse instead. Otherwise, the kernel will become a collection of hacks for various poorly written tools. Let's do it the other way, please. > For completeness, bitmap_write() is also refactored in the similar manner. > I have also checked a few users of it and `bloat-o-meter` showed no change. > > Link: https://lore.kernel.org/r/20260531111528.32697d1f@jic23-huawei [1] > Fixes: 63c15822b8dd ("lib/bitmap: add bitmap_{read,write}()") > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > --- > include/linux/bitmap.h | 24 +++++++++++------------- > 1 file changed, 11 insertions(+), 13 deletions(-) > > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h > index adafbcf2016b..f331cf06130d 100644 > --- a/include/linux/bitmap.h > +++ b/include/linux/bitmap.h > @@ -846,7 +846,7 @@ unsigned long bitmap_read(const unsigned long *map, unsigned long start, unsigne > if (unlikely(!nbits || nbits > BITS_PER_LONG)) > return 0; > > - if (space >= nbits) > + if (space >= nbits || offset == 0) > return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); So, doubling the number of conditions, and the new one duplicates the existing check. This version suppresses sparse false positive: if (offset <= BITS_PER_LONG - nbits) And even with that I'm not sure we need to touch the kernel to make sparse or whatever else tool happy... > value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); > @@ -874,25 +874,23 @@ void bitmap_write(unsigned long *map, unsigned long value, > unsigned long start, unsigned long nbits) > { > size_t index; > - unsigned long offset; > - unsigned long space; > - unsigned long mask; > - bool fit; > + unsigned long offset = start % BITS_PER_LONG; > + unsigned long space = BITS_PER_LONG - offset; > > if (unlikely(!nbits || nbits > BITS_PER_LONG)) > return; Initialization of local variables before the sanity check may become useless waste of cycles if this sanity fails. This is also not necessarily needed for sparse happiness, I guess... Let's keep the patch minimal? > - mask = BITMAP_LAST_WORD_MASK(nbits); > - value &= mask; > - offset = start % BITS_PER_LONG; > - space = BITS_PER_LONG - offset; > - fit = space >= nbits; I don't like this 'fit' thing, and would like to drop it. But let's find a better motivation to do that? Thanks, Yury > + value &= BITMAP_LAST_WORD_MASK(nbits); > index = BIT_WORD(start); > > - map[index] &= (fit ? (~(mask << offset)) : ~BITMAP_FIRST_WORD_MASK(start)); > - map[index] |= value << offset; > - if (fit) > + if (space >= nbits || offset == 0) { > + map[index] &= ~(BITMAP_LAST_WORD_MASK(nbits) << offset); > + map[index] |= value << offset; > return; > + } > + > + map[index] &= ~BITMAP_FIRST_WORD_MASK(start); > + map[index] |= value << offset; > > map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits); > map[index + 1] |= (value >> space); > -- > 2.50.1 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH v1 1/1] bitmap: Refactor bitmap_read() and bitmap_write() to avoid too big shift 2026-11-19 20:37 ` [PATCH v1 1/1] bitmap: Refactor bitmap_read() and bitmap_write() to avoid too big shift Yury Norov @ 2026-11-19 21:03 ` Andy Shevchenko 2026-11-19 21:22 ` Yury Norov 0 siblings, 1 reply; 3+ messages in thread From: Andy Shevchenko @ 2026-11-19 21:03 UTC (permalink / raw) To: Yury Norov Cc: linux-kernel, Yury Norov, Rasmus Villemoes, Jonathan Cameron, Chris Li, Luc Van Oostenryck, linux-sparse On Thu, Nov 19, 2026 at 03:37:33PM -0500, Yury Norov wrote: > On Thu, Nov 19, 2026 at 08:15:30PM +0100, Andy Shevchenko wrote: Thanks for review, my answers below. > > While compiling ad4691.c I have noticed the following warnings: > > > > drivers/iio/adc/ad4691.c: note: in included file: > > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > > > > Since the bitmap_read() is called with statically define 'start', > > the 'space' local variable becomes equal to BITS_PER_LONG, or 64 on > > 64-bit machines. The 'nbits' parameter is coming from the run-time > > defined value. Static analyser doesn't see that the right shift > > by 64-bit can't happen — the space >= nbits check guards that. > > While Jonathan put it as false positive [1], we still can give a hint > > to it without growing in the code (`bloat-o-meter` for above mentioned > > driver shows no difference in size). So this is what this change does. > > Jonathan put it right. > > If the analyzer (assuming sparse?) throws false positives, we don't > need to change the kernel. This is simply a wrong motivation. We need > to improve sparse instead. > > Otherwise, the kernel will become a collection of hacks for various > poorly written tools. Let's do it the other way, please. I agree in general. However, we can sometimes give hints without breaking the code. Now, thinking of this, the mentioned check can be done against offset leaving code generation and sparse happy and have no unneeded bulk. > > For completeness, bitmap_write() is also refactored in the similar manner. > > I have also checked a few users of it and `bloat-o-meter` showed no change. ... > > - if (space >= nbits) > > + if (space >= nbits || offset == 0) > > return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); > > So, doubling the number of conditions, and the new one duplicates the > existing check. This version suppresses sparse false positive: > > if (offset <= BITS_PER_LONG - nbits) Yes, you beat me up to it. I just was thinking about similar check in the above comment. > And even with that I'm not sure we need to touch the kernel to make > sparse or whatever else tool happy... It might take ages for sparse to fix even more annoying issues (if you remember something related to cleanup or alike change in the kernel and sparse was lagging for weeks). ... > > size_t index; > > - unsigned long offset; > > - unsigned long space; > > - unsigned long mask; > > - bool fit; > > + unsigned long offset = start % BITS_PER_LONG; > > + unsigned long space = BITS_PER_LONG - offset; > > > > if (unlikely(!nbits || nbits > BITS_PER_LONG)) > > return; > > Initialization of local variables before the sanity check > may become useless waste of cycles if this sanity fails. How? they are not used and function is marked as always inline. I believe optimisation in the compiler does the right thing. > This is also not necessarily needed for sparse happiness, This is to make both look similar at a glance. > I guess... Let's keep the patch minimal? > > > - mask = BITMAP_LAST_WORD_MASK(nbits); > > - value &= mask; > > - offset = start % BITS_PER_LONG; > > - space = BITS_PER_LONG - offset; > > - fit = space >= nbits; > > I don't like this 'fit' thing, and would like to drop it. But > let's find a better motivation to do that? Why? The fit keeps the check I want to refactor, since it makes it twice the code with that ternary looks ugly and unreadable. This is exactly the chance to kill two birds with one stone. -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH v1 1/1] bitmap: Refactor bitmap_read() and bitmap_write() to avoid too big shift 2026-11-19 21:03 ` Andy Shevchenko @ 2026-11-19 21:22 ` Yury Norov 0 siblings, 0 replies; 3+ messages in thread From: Yury Norov @ 2026-11-19 21:22 UTC (permalink / raw) To: Andy Shevchenko Cc: linux-kernel, Yury Norov, Rasmus Villemoes, Jonathan Cameron, Chris Li, Luc Van Oostenryck, linux-sparse On Thu, Nov 19, 2026 at 11:03:53PM +0200, Andy Shevchenko wrote: > On Thu, Nov 19, 2026 at 03:37:33PM -0500, Yury Norov wrote: > > On Thu, Nov 19, 2026 at 08:15:30PM +0100, Andy Shevchenko wrote: > > Thanks for review, my answers below. > > > > While compiling ad4691.c I have noticed the following warnings: > > > > > > drivers/iio/adc/ad4691.c: note: in included file: > > > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > > > include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long > > > > > > Since the bitmap_read() is called with statically define 'start', > > > the 'space' local variable becomes equal to BITS_PER_LONG, or 64 on > > > 64-bit machines. The 'nbits' parameter is coming from the run-time > > > defined value. Static analyser doesn't see that the right shift > > > by 64-bit can't happen — the space >= nbits check guards that. > > > While Jonathan put it as false positive [1], we still can give a hint > > > to it without growing in the code (`bloat-o-meter` for above mentioned > > > driver shows no difference in size). So this is what this change does. > > > > Jonathan put it right. > > > > If the analyzer (assuming sparse?) throws false positives, we don't > > need to change the kernel. This is simply a wrong motivation. We need > > to improve sparse instead. > > > > Otherwise, the kernel will become a collection of hacks for various > > poorly written tools. Let's do it the other way, please. > > I agree in general. However, we can sometimes give hints without breaking the code. > Now, thinking of this, the mentioned check can be done against offset leaving code > generation and sparse happy and have no unneeded bulk. > > > > For completeness, bitmap_write() is also refactored in the similar manner. > > > I have also checked a few users of it and `bloat-o-meter` showed no change. > > ... > > > > - if (space >= nbits) > > > + if (space >= nbits || offset == 0) > > > return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); > > > > So, doubling the number of conditions, and the new one duplicates the > > existing check. This version suppresses sparse false positive: > > > > if (offset <= BITS_PER_LONG - nbits) > > Yes, you beat me up to it. I just was thinking about similar check in the above > comment. > > > And even with that I'm not sure we need to touch the kernel to make > > sparse or whatever else tool happy... > > It might take ages for sparse to fix even more annoying issues (if you remember > something related to cleanup or alike change in the kernel and sparse was > lagging for weeks). > > ... > > > > size_t index; > > > - unsigned long offset; > > > - unsigned long space; > > > - unsigned long mask; > > > - bool fit; > > > + unsigned long offset = start % BITS_PER_LONG; > > > + unsigned long space = BITS_PER_LONG - offset; > > > > > > if (unlikely(!nbits || nbits > BITS_PER_LONG)) > > > return; > > > > Initialization of local variables before the sanity check > > may become useless waste of cycles if this sanity fails. > > How? they are not used and function is marked as always inline. I believe > optimisation in the compiler does the right thing. Maybe yes. I've seen quite many non-trivial compiler decisions before, so I want to make sure... > > This is also not necessarily needed for sparse happiness, > > This is to make both look similar at a glance. > > > I guess... Let's keep the patch minimal? > > > > > - mask = BITMAP_LAST_WORD_MASK(nbits); > > > - value &= mask; > > > - offset = start % BITS_PER_LONG; > > > - space = BITS_PER_LONG - offset; > > > - fit = space >= nbits; > > > > I don't like this 'fit' thing, and would like to drop it. But > > let's find a better motivation to do that? > > Why? The fit keeps the check I want to refactor, since it makes it twice > the code with that ternary looks ugly and unreadable. This is exactly the > chance to kill two birds with one stone. That's what I meant regarding the motivational part and minimizing the patch. Thanks, Yury From dfac9a524aa8658fe63c03804cca9f0980b58ef7 Mon Sep 17 00:00:00 2001 From: Yury Norov <ynorov@nvidia.com> Date: Thu, 19 Nov 2026 16:03:21 -0500 Subject: [PATCH] bitmap: Rephrase read and write bounds checks for sparse Reword bitmap_read/write() conditionals such that it improves on code generation and performance. Tested with minimal x86-64 kernels with GCC 15.2 and CONFIG_TEST_BITMAP=y. Run 400 fresh boots per kernel under virtme/KVM on a Core Ultra 7 268V, using one vCPU and 256 MiB RAM. Before, us After, us Change, us t p Read 277.00 (6.99) 265.33 (17.05) -4.21% -12.695 2.97e-31 Write 496.96 (14.38) 488.56 (10.41) -1.69% -9.615 8.03e-20 Bloat-o-meter reports 60 fewer function bytes in vmlinux and in lib/test_bitmap.o: Function Before After Delta test_bitmap_read_perf 234 227 -7 test_bitmap_write_perf 298 286 -12 test_bitmap_write_helper 880 872 -8 test_bitmap_read_write 800 767 -33 It also fixes the following sparse errors: include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long include/linux/bitmap.h:854:55: warning: shift too big (64) for type unsigned long Reported-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Link: https://lore.kernel.org/r/20261119191530.1716850-1-andriy.shevchenko@linux.intel.com Signed-off-by: Yury Norov <ynorov@nvidia.com> --- include/linux/bitmap.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index adafbcf2016b..08de1467367e 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -846,7 +846,7 @@ unsigned long bitmap_read(const unsigned long *map, unsigned long start, unsigne if (unlikely(!nbits || nbits > BITS_PER_LONG)) return 0; - if (space >= nbits) + if (offset <= BITS_PER_LONG - nbits) return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); @@ -886,7 +886,7 @@ void bitmap_write(unsigned long *map, unsigned long value, value &= mask; offset = start % BITS_PER_LONG; space = BITS_PER_LONG - offset; - fit = space >= nbits; + fit = offset <= BITS_PER_LONG - nbits; index = BIT_WORD(start); map[index] &= (fit ? (~(mask << offset)) : ~BITMAP_FIRST_WORD_MASK(start)); -- 2.53.0 ^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-11-19 21:24 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <20261119191530.1716850-1-andriy.shevchenko@linux.intel.com>
2026-11-19 20:37 ` [PATCH v1 1/1] bitmap: Refactor bitmap_read() and bitmap_write() to avoid too big shift Yury Norov
2026-11-19 21:03 ` Andy Shevchenko
2026-11-19 21:22 ` Yury Norov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox