[PATCH 0/7] assorted minor bitmap patches

[PATCH 0/7] assorted minor bitmap patches

[Rasmus Villemoes]

A recent LKML thread had me look into bitmap.{h,c} again, and I
stumbled on/rediscovered a few things.

Rasmus Villemoes (7):
  lib/bitmap.c: remove wrong documentation
  linux/bitmap.h: handle constant zero-size bitmaps correctly
  linux/bitmap.h: remove redundant uses of small_const_nbits()
  linux/bitmap.h: fix type of nbits in bitmap_shift_right()
  linux/bitmap.h: relax comment on compile-time constant nbits
  lib/bitmap.c: fix remaining space computation in
    bitmap_print_to_pagebuf
  lib/bitmap.c: simplify bitmap_print_to_pagebuf

 include/linux/bitmap.h | 37 +++++++++++++++----------------------
 lib/bitmap.c           | 21 +++++++--------------
 2 files changed, 22 insertions(+), 36 deletions(-)

-- 
2.16.4

[PATCH 1/7] lib/bitmap.c: remove wrong documentation

[Rasmus Villemoes]

This promise is violated in a number of places, e.g. already in the
second function below this paragraph. Since I don't think anybody relies
on this being true, and since actually honouring it would hurt
performance and code size in various places, just remove the paragraph.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 5 -----
 1 file changed, 5 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 58f9750e49c6..1f73b2e52186 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -35,11 +35,6 @@
  * carefully filter out these unused bits from impacting their
  * results.
  *
- * These operations actually hold to a slightly stronger rule:
- * if you don't input any bitmaps to these ops that have some
- * unused bits set, then they won't output any set unused bits
- * in output bitmaps.
- *
  * The byte ordering of bitmaps is more natural on little
  * endian architectures.  See the big-endian headers
  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
-- 
2.16.4

[PATCH 2/7] linux/bitmap.h: handle constant zero-size bitmaps correctly

[Rasmus Villemoes]

The static inlines in bitmap.h do not handle a compile-time constant
nbits==0 correctly (they dereference the passed src or dst pointers,
despite only 0 words being valid to access). I had the 0-day buildbot
chew on a patch [1] that would cause build failures for such cases
without complaining, suggesting that we don't have any such users
currently, at least for the 70 .config/arch combinations that was
built. Should any turn up, make sure they use the out-of-line versions,
which do handle nbits==0 correctly.

This is of course not the most efficient, but it's much less churn than
teaching all the static inlines an "if (zero_const_nbits())", and since
we don't have any current instances, this doesn't affect existing code
at all.

[1] lkml.kernel.org/r/20180815085539.27485-1-linux@rasmusvillemoes.dk

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/bitmap.h | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 1ee46f492267..b91a6b5d3e78 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -196,8 +196,13 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,
 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
 
+/*
+ * The static inlines below do not handle constant nbits==0 correctly,
+ * so make such users (should any ever turn up) call the out-of-line
+ * versions.
+ */
 #define small_const_nbits(nbits) \
-	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
+	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
 
 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
-- 
2.16.4

[PATCH 3/7] linux/bitmap.h: remove redundant uses of small_const_nbits()

[Rasmus Villemoes]

In the _zero, _fill and _copy functions, the small_const_nbits
branch is redundant. If nbits is small and const, gcc knows full well
that BITS_TO_LONGS(nbits) is 1, so len is also a compile-time
constant (sizeof(long)), and calling memset or memcpy with a length
argument of sizeof(long) makes gcc generate the expected code anyway:

#include <string.h>
void a(unsigned long *x) { memset(x, 0, 8); }
void b(unsigned long *x) { memset(x, 0xff, 8); }
void c(unsigned long *x, const unsigned long *y) { memcpy(x, y, 8); }

turns into

0000000000000000 <a>:
   0:   48 c7 07 00 00 00 00    movq   $0x0,(%rdi)
   7:   c3                      retq
   8:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
   f:   00

0000000000000010 <b>:
  10:   48 c7 07 ff ff ff ff    movq   $0xffffffffffffffff,(%rdi)
  17:   c3                      retq
  18:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
  1f:   00

0000000000000020 <c>:
  20:   48 8b 06                mov    (%rsi),%rax
  23:   48 89 07                mov    %rax,(%rdi)
  26:   c3                      retq

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/bitmap.h | 24 ++++++------------------
 1 file changed, 6 insertions(+), 18 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index b91a6b5d3e78..a7a8b5017d62 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -206,33 +206,21 @@ extern int bitmap_print_to_pagebuf(bool list, char *buf,
 
 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
-	if (small_const_nbits(nbits))
-		*dst = 0UL;
-	else {
-		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
-		memset(dst, 0, len);
-	}
+	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+	memset(dst, 0, len);
 }
 
 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
 {
-	if (small_const_nbits(nbits))
-		*dst = ~0UL;
-	else {
-		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
-		memset(dst, 0xff, len);
-	}
+	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+	memset(dst, 0xff, len);
 }
 
 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
 			unsigned int nbits)
 {
-	if (small_const_nbits(nbits))
-		*dst = *src;
-	else {
-		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
-		memcpy(dst, src, len);
-	}
+	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+	memcpy(dst, src, len);
 }
 
 /*
-- 
2.16.4

[PATCH 4/7] linux/bitmap.h: fix type of nbits in bitmap_shift_right()

[Rasmus Villemoes]

Most other bitmap API, including the OOL version __bitmap_shift_right,
take unsigned nbits. This was accidentally left out from 2fbad29917c98.

Fixes: 2fbad29917c98 (lib: bitmap: change bitmap_shift_right to take unsigned parameters)
Reported-by: Yury Norov <ynorov@caviumnetworks.com>
Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/bitmap.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index a7a8b5017d62..e34c361f4a92 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -383,7 +383,7 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
 }
 
 static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
-				unsigned int shift, int nbits)
+				unsigned int shift, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
 		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
-- 
2.16.4

[PATCH 5/7] linux/bitmap.h: relax comment on compile-time constant nbits

[Rasmus Villemoes]

It's not clear what's so horrible about emitting a function call to
handle a run-time sized bitmap. Moreover, gcc also emits a function call
for a compile-time-constant-but-huge nbits, so the comment isn't even
accurate.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 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 e34c361f4a92..3f0cac3aedca 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -28,8 +28,8 @@
  * The available bitmap operations and their rough meaning in the
  * case that the bitmap is a single unsigned long are thus:
  *
- * Note that nbits should be always a compile time evaluable constant.
- * Otherwise many inlines will generate horrible code.
+ * The generated code is more efficient when nbits is known at
+ * compile-time and at most BITS_PER_LONG.
  *
  * ::
  *
-- 
2.16.4

[PATCH 6/7] lib/bitmap.c: fix remaining space computation in bitmap_print_to_pagebuf

[Rasmus Villemoes]

For various alignments of buf, the current expression computes

4096 ok
4095 ok
8190
8189
...
4097

i.e., if the caller has already written two bytes into the page buffer,
len is 8190 rather than 4094, because PTR_ALIGN aligns up to the next
boundary. So if the printed version of the bitmap is huge, scnprintf()
ends up writing beyond the page boundary.

I don't think any current callers actually write anything before
bitmap_print_to_pagebuf, but the API seems to be designed to allow it.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 1f73b2e52186..277c9a63a5ab 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -460,14 +460,15 @@ EXPORT_SYMBOL(bitmap_parse_user);
  * ranges if list is specified or hex digits grouped into comma-separated
  * sets of 8 digits/set. Returns the number of characters written to buf.
  *
- * It is assumed that @buf is a pointer into a PAGE_SIZE area and that
- * sufficient storage remains at @buf to accommodate the
- * bitmap_print_to_pagebuf() output.
+ * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
+ * area and that sufficient storage remains at @buf to accommodate the
+ * bitmap_print_to_pagebuf() output. Returns the number of characters
+ * actually printed to @buf, excluding terminating '\0'.
  */
 int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 			    int nmaskbits)
 {
-	ptrdiff_t len = PTR_ALIGN(buf + PAGE_SIZE - 1, PAGE_SIZE) - buf;
+	ptrdiff_t len = PAGE_SIZE - ((unsigned long)buf & (PAGE_SIZE-1));
 	int n = 0;
 
 	if (len > 1)
-- 
2.16.4

[PATCH 7/7] lib/bitmap.c: simplify bitmap_print_to_pagebuf

[Rasmus Villemoes]

len is guaranteed to lie in [1, PAGE_SIZE]. If scnprintf is called with
a buffer size of 1, it is guaranteed to return 0. So in the extremely
unlikely case of having just one byte remaining in the page, let's just
call scnprintf anyway. The only difference is that this will write a
'\0' to that final byte in the page, but that's an improvement: We now
guarantee that after the call, buf is a properly terminated C string of
length exactly the return value.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 277c9a63a5ab..75175da01fd8 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -469,12 +469,9 @@ int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 			    int nmaskbits)
 {
 	ptrdiff_t len = PAGE_SIZE - ((unsigned long)buf & (PAGE_SIZE-1));
-	int n = 0;
 
-	if (len > 1)
-		n = list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
-			   scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
-	return n;
+	return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
+		      scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
 }
 EXPORT_SYMBOL(bitmap_print_to_pagebuf);
 
-- 
2.16.4

Re: [PATCH 6/7] lib/bitmap.c: fix remaining space computation in bitmap_print_to_pagebuf

[Andy Shevchenko]

On Sat, Aug 18, 2018 at 4:17 PM Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
>
> For various alignments of buf, the current expression computes
>
> 4096 ok
> 4095 ok
> 8190
> 8189
> ...
> 4097
>
> i.e., if the caller has already written two bytes into the page buffer,
> len is 8190 rather than 4094, because PTR_ALIGN aligns up to the next
> boundary. So if the printed version of the bitmap is huge, scnprintf()
> ends up writing beyond the page boundary.
>
> I don't think any current callers actually write anything before
> bitmap_print_to_pagebuf, but the API seems to be designed to allow it.
>
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  lib/bitmap.c | 9 +++++----
>  1 file changed, 5 insertions(+), 4 deletions(-)
>
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 1f73b2e52186..277c9a63a5ab 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -460,14 +460,15 @@ EXPORT_SYMBOL(bitmap_parse_user);
>   * ranges if list is specified or hex digits grouped into comma-separated
>   * sets of 8 digits/set. Returns the number of characters written to buf.
>   *
> - * It is assumed that @buf is a pointer into a PAGE_SIZE area and that
> - * sufficient storage remains at @buf to accommodate the
> - * bitmap_print_to_pagebuf() output.
> + * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
> + * area and that sufficient storage remains at @buf to accommodate the
> + * bitmap_print_to_pagebuf() output. Returns the number of characters
> + * actually printed to @buf, excluding terminating '\0'.
>   */
>  int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
>                             int nmaskbits)
>  {
> -       ptrdiff_t len = PTR_ALIGN(buf + PAGE_SIZE - 1, PAGE_SIZE) - buf;
> +       ptrdiff_t len = PAGE_SIZE - ((unsigned long)buf & (PAGE_SIZE-1));

Don't we have offset_in_page() helper macro?

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 0/7] assorted minor bitmap patches

[Andy Shevchenko]

On Sat, Aug 18, 2018 at 4:17 PM Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
>
> A recent LKML thread had me look into bitmap.{h,c} again, and I
> stumbled on/rediscovered a few things.
>

Good fixes, thanks!

Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com>

P.S. Perhaps needs addressing my comment to patch 6.
> Rasmus Villemoes (7):
>   lib/bitmap.c: remove wrong documentation
>   linux/bitmap.h: handle constant zero-size bitmaps correctly
>   linux/bitmap.h: remove redundant uses of small_const_nbits()
>   linux/bitmap.h: fix type of nbits in bitmap_shift_right()
>   linux/bitmap.h: relax comment on compile-time constant nbits
>   lib/bitmap.c: fix remaining space computation in
>     bitmap_print_to_pagebuf
>   lib/bitmap.c: simplify bitmap_print_to_pagebuf
>
>  include/linux/bitmap.h | 37 +++++++++++++++----------------------
>  lib/bitmap.c           | 21 +++++++--------------
>  2 files changed, 22 insertions(+), 36 deletions(-)
>
> --
> 2.16.4
>


--
With Best Regards,
Andy Shevchenko

Re: [PATCH 6/7] lib/bitmap.c: fix remaining space computation in bitmap_print_to_pagebuf

[Rasmus Villemoes]

On 2018-08-19 14:37, Andy Shevchenko wrote:
> On Sat, Aug 18, 2018 at 4:17 PM Rasmus Villemoes
> <linux@rasmusvillemoes.dk> wrote:
>>
>>  int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
>>                             int nmaskbits)
>>  {
>> -       ptrdiff_t len = PTR_ALIGN(buf + PAGE_SIZE - 1, PAGE_SIZE) - buf;
>> +       ptrdiff_t len = PAGE_SIZE - ((unsigned long)buf & (PAGE_SIZE-1));
> 
> Don't we have offset_in_page() helper macro?

Indeed, thanks! Andrew, if you pick this up, can you use the much more
obvious

PAGE_SIZE - offset_in_page(buf)

instead? bitmap.c already (unsurprisingly) includes mm.h through some
recursive path.

Rasmus

Re: [PATCH 5/7] linux/bitmap.h: relax comment on compile-time constant nbits

[Yury Norov]

On Sat, Aug 18, 2018 at 03:16:21PM +0200, Rasmus Villemoes wrote:
> It's not clear what's so horrible about emitting a function call to
> handle a run-time sized bitmap. Moreover, gcc also emits a function call
> for a compile-time-constant-but-huge nbits, so the comment isn't even
> accurate.
> 
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

Hi Rasmus,

Maybe too late, but 

Acked-by: Yury Norov <ynorov@caviumnetworks.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 e34c361f4a92..3f0cac3aedca 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -28,8 +28,8 @@
>   * The available bitmap operations and their rough meaning in the
>   * case that the bitmap is a single unsigned long are thus:
>   *
> - * Note that nbits should be always a compile time evaluable constant.
> - * Otherwise many inlines will generate horrible code.
> + * The generated code is more efficient when nbits is known at
> + * compile-time and at most BITS_PER_LONG.
>   *
>   * ::
>   *
> --
> 2.16.4

Re: [PATCH 5/7] linux/bitmap.h: relax comment on compile-time constant nbits

[Andy Shevchenko]

On Tue, Sep 04, 2018 at 02:08:59PM +0300, Yury Norov wrote:
> On Sat, Aug 18, 2018 at 03:16:21PM +0200, Rasmus Villemoes wrote:
> > It's not clear what's so horrible about emitting a function call to
> > handle a run-time sized bitmap. Moreover, gcc also emits a function call
> > for a compile-time-constant-but-huge nbits, so the comment isn't even
> > accurate.
> > 
> > Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> 
> Hi Rasmus,
> 
> Maybe too late, but 
> 
> Acked-by: Yury Norov <ynorov@caviumnetworks.com>

Actually not, I don't see this in linux-next.

Rasmus, do you know what happened to the series? Is it got stuck by unknown reasons?

> > ---
> >  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 e34c361f4a92..3f0cac3aedca 100644
> > --- a/include/linux/bitmap.h
> > +++ b/include/linux/bitmap.h
> > @@ -28,8 +28,8 @@
> >   * The available bitmap operations and their rough meaning in the
> >   * case that the bitmap is a single unsigned long are thus:
> >   *
> > - * Note that nbits should be always a compile time evaluable constant.
> > - * Otherwise many inlines will generate horrible code.
> > + * The generated code is more efficient when nbits is known at
> > + * compile-time and at most BITS_PER_LONG.
> >   *
> >   * ::
> >   *
> > --
> > 2.16.4

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 5/7] linux/bitmap.h: relax comment on compile-time constant nbits

[Rasmus Villemoes]

On 2018-09-04 13:30, Andy Shevchenko wrote:
> On Tue, Sep 04, 2018 at 02:08:59PM +0300, Yury Norov wrote:
>> On Sat, Aug 18, 2018 at 03:16:21PM +0200, Rasmus Villemoes wrote:
>>> It's not clear what's so horrible about emitting a function call to
>>> handle a run-time sized bitmap. Moreover, gcc also emits a function call
>>> for a compile-time-constant-but-huge nbits, so the comment isn't even
>>> accurate.
>>>
>>> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
>>
>> Hi Rasmus,
>>
>> Maybe too late, but 
>>
>> Acked-by: Yury Norov <ynorov@caviumnetworks.com>
> 
> Actually not, I don't see this in linux-next.
> 
> Rasmus, do you know what happened to the series? Is it got stuck by unknown reasons?

I just assumed Andrew was busy doing more important things. He usually
gets around to these kinds of minor cleanups, eventually.

Rasmus