assorted minor bitmap patches
Subsystems (2)
Rasmus Villemoes
reviewercover 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
Rasmus Villemoes
reviewerPATCH 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
@@ -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
Rasmus Villemoes
reviewerPATCH 2/7 linux/bitmap.h: handle constant zero-size bitmaps correctly
In reply to Rasmus VillemoesThe 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
@@ -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
Rasmus Villemoes
reviewerPATCH 3/7 linux/bitmap.h: remove redundant uses of small_const_nbits()
In reply to Rasmus VillemoesIn 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
@@ -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
Rasmus Villemoes
reviewerPATCH 4/7 linux/bitmap.h: fix type of nbits in bitmap_shift_right()
In reply to Rasmus VillemoesMost other bitmap API, including the OOL version __bitmap_shift_right, take unsigned nbits. This was accidentally left out from 2fbad29917c98.
--- include/linux/bitmap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/bitmap.h +1 -1
@@ -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
Rasmus Villemoes
reviewerPATCH 5/7 linux/bitmap.h: relax comment on compile-time constant nbits
In reply to Rasmus VillemoesIt'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
@@ -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
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.
Signed-off-by Rasmus Villemoes <[email protected]>
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@@ -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
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
Signed-off-by Rasmus Villemoes <[email protected]>Hi Rasmus,
Maybe too late, but
Acked-by Yury Norov <[email protected]>
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@@ -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
Rasmus Villemoes
reviewerRe: [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.
Signed-off-by Rasmus Villemoes <[email protected]>Hi Rasmus,
Quoted 7 lines
Quoted 3 lines
Maybe too late, but
Acked-by Yury Norov <[email protected]>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
Rasmus Villemoes
reviewerPATCH 6/7 lib/bitmap.c: fix remaining space computation in bitmap_print_to_pagebuf
In reply to Rasmus VillemoesFor 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
@@ -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
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
...
4097i.e., if the caller has already written two bytes into the page buffer, len is 8190 rather than 4094, because
PTR_ALIGNaligns 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 <[email protected]>--- lib/bitmap.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)lib/bitmap.c +0
-3@@ -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
Rasmus Villemoes
reviewerRe: [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
Rasmus Villemoes
reviewerPATCH 7/7 lib/bitmap.c: simplify bitmap_print_to_pagebuf
In reply to Rasmus Villemoeslen 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
@@ -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
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 documentationlinux/bitmap.h: handle constant zero-size bitmaps correctlylinux/bitmap.h: remove redundant uses ofsmall_const_nbits()linux/bitmap.h: fix type of nbits inbitmap_shift_right()linux/bitmap.h: relax comment on compile-time constant nbitslib/bitmap.c: fix remaining space computation in
bitmap_print_to_pagebuf
lib/bitmap.c: simplifybitmap_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