Skip to contentSkip to conversation

assorted minor bitmap patches

PATCH In review Rasmus Villemoes 4 participants 14 messages Aug 18, 2018 – Sep 4, 2018

Subsystems (2)
lore
Share & tools
lore

Rasmus Villemoes

author reviewer
#0 lore raw

cover assorted minor bitmap patches

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(-)
Signature · 1 line
2.16.4
author reviewer
#1 lore raw

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

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.

---
 lib/bitmap.c | 5 -----
 1 file changed, 5 deletions(-)
lib/bitmap.c +0 -5
index 58f9750e49c6..1f73b2e52186 100644
@@ -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
Signature · 1 line
2.16.4
author reviewer
#2 lore raw

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

In reply to 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/[email protected]

---
 include/linux/bitmap.h | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
include/linux/bitmap.h +6 -1
index 1ee46f492267..b91a6b5d3e78 100644
@@ -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)
 {
Signature · 1 line
2.16.4
author reviewer
#3 lore raw

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

In reply to 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
---
 include/linux/bitmap.h | 24 ++++++------------------
 1 file changed, 6 insertions(+), 18 deletions(-)
include/linux/bitmap.h +6 -18
index b91a6b5d3e78..a7a8b5017d62 100644
@@ -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);
 }
 
 /*
Signature · 1 line
2.16.4
author reviewer
#4 lore raw

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

In reply to 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)
---
 include/linux/bitmap.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/bitmap.h +1 -1
index a7a8b5017d62..e34c361f4a92 100644
@@ -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;
Signature · 1 line
2.16.4
author reviewer
#5 lore raw

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

In reply to 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.

---
 include/linux/bitmap.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/bitmap.h +2 -2
index e34c361f4a92..3f0cac3aedca 100644
@@ -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.
  *
  * ::
  *
Signature · 1 line
2.16.4
Acked-by on v1 5/7
#6 lore raw

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

Quoted 6 lines · 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.

Hi Rasmus,

Maybe too late, but

Quoted 21 lines
---
 include/linux/bitmap.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/bitmap.h +2 -3
index e34c361f4a92..3f0cac3aedca 100644
@@ -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

#7 lore raw

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

Quoted 6 lines · Yury Norov
Quoted 5 lines · 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.

Quoted 7 lines
Quoted 1 line

Hi Rasmus,

Maybe too late, but

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?

Quoted 21 lines
Quoted 21 lines
---
 include/linux/bitmap.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/bitmap.h +2 -3
index e34c361f4a92..3f0cac3aedca 100644
@@ -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

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author reviewer
#8 lore raw

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

Quoted 11 lines · Andy Shevchenko
Quoted 10 lines · Yury Norov
Quoted 6 lines · 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.

Hi Rasmus,

Quoted 7 lines
Quoted 3 lines

Maybe too late, but

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

author reviewer
#9 lore raw

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

In reply to 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.

---
 lib/bitmap.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
lib/bitmap.c +5 -4
index 1f73b2e52186..277c9a63a5ab 100644
@@ -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)
Signature · 1 line
2.16.4
#10 lore raw

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

Quoted 34 lines · 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.

---
 lib/bitmap.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
lib/bitmap.c +0 -3
index 1f73b2e52186..277c9a63a5ab 100644
@@ -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.

lib/bitmap.c EXPORT_SYMBOL(bitmap_parse_user); · line 471

Quoted 10 lines
lib/bitmap.c +5 -1
+ * 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?

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author reviewer
#11 lore raw

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

Quoted 10 lines · Andy Shevchenko

lib/bitmap.c EXPORT_SYMBOL(bitmap_parse_user); · line 471

Quoted 6 lines · Rasmus Villemoes

int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
int nmaskbits)
{

lib/bitmap.c +1 -1
-       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

author reviewer
#12 lore raw

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

In reply to 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.

---
 lib/bitmap.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)
lib/bitmap.c +2 -5
index 277c9a63a5ab..75175da01fd8 100644
@@ -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);
 
Signature · 1 line
2.16.4
Reviewed-by on the v1 series
#13 lore raw
In reply to Rasmus Villemoes
Quoted 4 lines · Rasmus Villemoes

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

Good fixes, thanks!

P.S. Perhaps needs addressing my comment to patch 6.

Quoted 10 lines

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

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

--
2.16.4

--
With Best Regards,
Andy Shevchenko