* [PATCH 0/2] bitmap: introduce for_each_set_bitrange()
@ 2021-07-09 3:45 Yury Norov
2021-07-09 3:45 ` [PATCH 1/2] lib: bitmap: add performance test for bitmap_print_to_pagebuf Yury Norov
2021-07-09 3:45 ` [PATCH 2/2] bitmap: introduce for_each_set_bitrange Yury Norov
0 siblings, 2 replies; 8+ messages in thread
From: Yury Norov @ 2021-07-09 3:45 UTC (permalink / raw)
To: linux-kernel
Cc: Yury Norov, Andy Shevchenko, Rasmus Villemoes, Petr Mladek,
Steven Rostedt, Sergey Senozhatsky, Tejun Heo
Introduce for_each_set_bitrange() and improve bitmap_list_string().
On top of:
https://lore.kernel.org/lkml/YNp3extAkTY8Aocd@yury-ThinkPad/T/ and
https://lore.kernel.org/lkml/YNirnaYw1GSxg1jK@yury-ThinkPad/T/
The full series is here:
https://github.com/norov/linux/commits/bm-f3
Yury Norov (2):
lib: bitmap: add performance test for bitmap_print_to_pagebuf
bitmap: introduce for_each_set_bitrange{_from}
include/linux/find.h | 7 +++++++
lib/test_bitmap.c | 37 +++++++++++++++++++++++++++++++++++++
lib/vsprintf.c | 40 ++++++++++++++++------------------------
3 files changed, 60 insertions(+), 24 deletions(-)
--
2.30.2
^ permalink raw reply [flat|nested] 8+ messages in thread* [PATCH 1/2] lib: bitmap: add performance test for bitmap_print_to_pagebuf 2021-07-09 3:45 [PATCH 0/2] bitmap: introduce for_each_set_bitrange() Yury Norov @ 2021-07-09 3:45 ` Yury Norov 2021-07-09 3:45 ` [PATCH 2/2] bitmap: introduce for_each_set_bitrange Yury Norov 1 sibling, 0 replies; 8+ messages in thread From: Yury Norov @ 2021-07-09 3:45 UTC (permalink / raw) To: linux-kernel Cc: Yury Norov, Andy Shevchenko, Rasmus Villemoes, Petr Mladek, Steven Rostedt, Sergey Senozhatsky, Tejun Heo This patch adds performance test for a fully set bitmap. Functional tests are in lib/test_printf.c. Signed-off-by: Yury Norov <yury.norov@gmail.com> --- lib/test_bitmap.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 4ea73f5aed41..452d525007da 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -430,6 +430,42 @@ static void __init test_bitmap_parselist(void) } } +static void __init test_bitmap_printlist(void) +{ + unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL); + char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + char expected[256]; + int ret, slen; + ktime_t time; + + if (!buf || !bmap) + goto out; + + memset(bmap, -1, PAGE_SIZE); + slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1); + if (slen < 0) + goto out; + + time = ktime_get(); + ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8); + time = ktime_get() - time; + + if (ret != slen + 1) { + pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen); + goto out; + } + + if (strncmp(buf, expected, slen)) { + pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected); + goto out; + } + + pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time); +out: + kfree(buf); + kfree(bmap); +} + static const unsigned long parse_test[] __initconst = { BITMAP_FROM_U64(0), BITMAP_FROM_U64(1), @@ -669,6 +705,7 @@ static void __init selftest(void) test_bitmap_arr32(); test_bitmap_parse(); test_bitmap_parselist(); + test_bitmap_printlist(); test_mem_optimisations(); test_for_each_set_clump8(); test_bitmap_cut(); -- 2.30.2 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-09 3:45 [PATCH 0/2] bitmap: introduce for_each_set_bitrange() Yury Norov 2021-07-09 3:45 ` [PATCH 1/2] lib: bitmap: add performance test for bitmap_print_to_pagebuf Yury Norov @ 2021-07-09 3:45 ` Yury Norov 2021-07-09 6:21 ` Yury Norov 2021-07-09 13:59 ` Steven Rostedt 1 sibling, 2 replies; 8+ messages in thread From: Yury Norov @ 2021-07-09 3:45 UTC (permalink / raw) To: linux-kernel Cc: Yury Norov, Andy Shevchenko, Rasmus Villemoes, Petr Mladek, Steven Rostedt, Sergey Senozhatsky, Tejun Heo bitmap_list_string() is very ineffective when printing bitmaps with long ranges of set bits because it calls find_next_bit for each bit. We can do better by detecting ranges of set bits. This patch introduces a macro for_each_set_bitrange and uses it in bitmap_list_string(). In my environment, before/after is 943008/31008 ns. Signed-off-by: Yury Norov <yury.norov@gmail.com> --- include/linux/find.h | 7 +++++++ lib/vsprintf.c | 40 ++++++++++++++++------------------------ 2 files changed, 23 insertions(+), 24 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index ae9ed52b52b8..1a5ed45dc81b 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) +#define for_each_set_bitrange(b, e, addr, size) \ + for ((b) = find_next_bit((addr), (size), 0), \ + (e) = find_next_zero_bit((addr), (size), (b) + 1); \ + (b) < (size); \ + (b) = find_next_bit((addr), (size), (e) + 1), \ + (e) = find_next_zero_bit((addr), (size), (b) + 1)) + /** * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits * @start: bit offset to start search and to store the current iteration offset diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 87acf66f0e4c..1ee54dace71e 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, struct printf_spec spec, const char *fmt) { int nr_bits = max_t(int, spec.field_width, 0); - /* current bit is 'cur', most recently seen range is [rbot, rtop] */ - int cur, rbot, rtop; - bool first = true; + char *start = buf; + int b, e; if (check_pointer(&buf, end, bitmap, spec)) return buf; - rbot = cur = find_first_bit(bitmap, nr_bits); - while (cur < nr_bits) { - rtop = cur; - cur = find_next_bit(bitmap, nr_bits, cur + 1); - if (cur < nr_bits && cur <= rtop + 1) - continue; + for_each_set_bitrange(b, e, bitmap, nr_bits) { + buf = number(buf, end, b, default_dec_spec); + if (e == b + 1) + goto put_comma; - if (!first) { - if (buf < end) - *buf = ','; - buf++; - } - first = false; + if (buf < end) + *buf = '-'; - buf = number(buf, end, rbot, default_dec_spec); - if (rbot < rtop) { - if (buf < end) - *buf = '-'; - buf++; + buf = number(++buf, end, e - 1, default_dec_spec); +put_comma: + if (buf < end) + *buf = ','; + buf++; + } - buf = number(buf, end, rtop, default_dec_spec); - } + if (buf > start) + buf--; - rbot = cur; - } return buf; } -- 2.30.2 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-09 3:45 ` [PATCH 2/2] bitmap: introduce for_each_set_bitrange Yury Norov @ 2021-07-09 6:21 ` Yury Norov 2021-07-09 13:59 ` Steven Rostedt 1 sibling, 0 replies; 8+ messages in thread From: Yury Norov @ 2021-07-09 6:21 UTC (permalink / raw) To: linux-kernel Cc: Andy Shevchenko, Rasmus Villemoes, Petr Mladek, Steven Rostedt, Sergey Senozhatsky, Tejun Heo On Thu, Jul 08, 2021 at 08:45:19PM -0700, Yury Norov wrote: > bitmap_list_string() is very ineffective when printing bitmaps with long > ranges of set bits because it calls find_next_bit for each bit. We can do > better by detecting ranges of set bits. > > This patch introduces a macro for_each_set_bitrange and uses it in > bitmap_list_string(). In my environment, before/after is 943008/31008 ns. Ah, it seems we already have bitmap_for_each_{set,clear}_region() with the same functionality. I'll check everything again and submit v2 soon. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-09 3:45 ` [PATCH 2/2] bitmap: introduce for_each_set_bitrange Yury Norov 2021-07-09 6:21 ` Yury Norov @ 2021-07-09 13:59 ` Steven Rostedt 2021-07-15 15:50 ` Yury Norov 1 sibling, 1 reply; 8+ messages in thread From: Steven Rostedt @ 2021-07-09 13:59 UTC (permalink / raw) To: Yury Norov Cc: linux-kernel, Andy Shevchenko, Rasmus Villemoes, Petr Mladek, Sergey Senozhatsky, Tejun Heo On Thu, 8 Jul 2021 20:45:19 -0700 Yury Norov <yury.norov@gmail.com> wrote: > bitmap_list_string() is very ineffective when printing bitmaps with long > ranges of set bits because it calls find_next_bit for each bit. We can do > better by detecting ranges of set bits. > > This patch introduces a macro for_each_set_bitrange and uses it in > bitmap_list_string(). In my environment, before/after is 943008/31008 ns. > > Signed-off-by: Yury Norov <yury.norov@gmail.com> > --- > include/linux/find.h | 7 +++++++ > lib/vsprintf.c | 40 ++++++++++++++++------------------------ > 2 files changed, 23 insertions(+), 24 deletions(-) > > diff --git a/include/linux/find.h b/include/linux/find.h > index ae9ed52b52b8..1a5ed45dc81b 100644 > --- a/include/linux/find.h > +++ b/include/linux/find.h > @@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned > (bit) < (size); \ > (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) > > +#define for_each_set_bitrange(b, e, addr, size) \ The above needs a kerneldoc header. > + for ((b) = find_next_bit((addr), (size), 0), \ > + (e) = find_next_zero_bit((addr), (size), (b) + 1); \ > + (b) < (size); \ > + (b) = find_next_bit((addr), (size), (e) + 1), \ > + (e) = find_next_zero_bit((addr), (size), (b) + 1)) > + > /** > * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits > * @start: bit offset to start search and to store the current iteration offset > diff --git a/lib/vsprintf.c b/lib/vsprintf.c > index 87acf66f0e4c..1ee54dace71e 100644 > --- a/lib/vsprintf.c > +++ b/lib/vsprintf.c > @@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, > struct printf_spec spec, const char *fmt) > { > int nr_bits = max_t(int, spec.field_width, 0); > - /* current bit is 'cur', most recently seen range is [rbot, rtop] */ > - int cur, rbot, rtop; > - bool first = true; > + char *start = buf; > + int b, e; > > if (check_pointer(&buf, end, bitmap, spec)) > return buf; > > - rbot = cur = find_first_bit(bitmap, nr_bits); > - while (cur < nr_bits) { > - rtop = cur; > - cur = find_next_bit(bitmap, nr_bits, cur + 1); > - if (cur < nr_bits && cur <= rtop + 1) > - continue; > + for_each_set_bitrange(b, e, bitmap, nr_bits) { > + buf = number(buf, end, b, default_dec_spec); > + if (e == b + 1) > + goto put_comma; Using a goto to skip a few lines instead of just having the reverse conditional is rather sloppy IMO. if (e != b + 1) { if (buf < end) *buf = '-'; buf++; buf = number(buf, end, e - 1, default_dec_spec); } Is much clearer. > > - if (!first) { > - if (buf < end) > - *buf = ','; > - buf++; > - } > - first = false; > + if (buf < end) > + *buf = '-'; > > - buf = number(buf, end, rbot, default_dec_spec); > - if (rbot < rtop) { > - if (buf < end) > - *buf = '-'; > - buf++; > + buf = number(++buf, end, e - 1, default_dec_spec); > +put_comma: > + if (buf < end) > + *buf = ','; > + buf++; > + } > > - buf = number(buf, end, rtop, default_dec_spec); > - } > + if (buf > start) > + buf--; If the above is to undo the last comma, please put back the first logic. -- Steve > > - rbot = cur; > - } > return buf; > } > ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-09 13:59 ` Steven Rostedt @ 2021-07-15 15:50 ` Yury Norov 2021-07-16 13:46 ` Petr Mladek 0 siblings, 1 reply; 8+ messages in thread From: Yury Norov @ 2021-07-15 15:50 UTC (permalink / raw) To: Steven Rostedt Cc: linux-kernel, Andy Shevchenko, Rasmus Villemoes, Petr Mladek, Sergey Senozhatsky, Tejun Heo On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote: > On Thu, 8 Jul 2021 20:45:19 -0700 > Yury Norov <yury.norov@gmail.com> wrote: > > > bitmap_list_string() is very ineffective when printing bitmaps with long > > ranges of set bits because it calls find_next_bit for each bit. We can do > > better by detecting ranges of set bits. > > > > This patch introduces a macro for_each_set_bitrange and uses it in > > bitmap_list_string(). In my environment, before/after is 943008/31008 ns. > > > > Signed-off-by: Yury Norov <yury.norov@gmail.com> > > --- > > include/linux/find.h | 7 +++++++ > > lib/vsprintf.c | 40 ++++++++++++++++------------------------ > > 2 files changed, 23 insertions(+), 24 deletions(-) > > > > diff --git a/include/linux/find.h b/include/linux/find.h > > index ae9ed52b52b8..1a5ed45dc81b 100644 > > --- a/include/linux/find.h > > +++ b/include/linux/find.h > > @@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned > > (bit) < (size); \ > > (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) > > > > +#define for_each_set_bitrange(b, e, addr, size) \ > > The above needs a kerneldoc header. OK. > > > + for ((b) = find_next_bit((addr), (size), 0), \ > > + (e) = find_next_zero_bit((addr), (size), (b) + 1); \ > > + (b) < (size); \ > > + (b) = find_next_bit((addr), (size), (e) + 1), \ > > + (e) = find_next_zero_bit((addr), (size), (b) + 1)) > > + > > /** > > * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits > > * @start: bit offset to start search and to store the current iteration offset > > diff --git a/lib/vsprintf.c b/lib/vsprintf.c > > index 87acf66f0e4c..1ee54dace71e 100644 > > --- a/lib/vsprintf.c > > +++ b/lib/vsprintf.c > > @@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, > > struct printf_spec spec, const char *fmt) > > { > > int nr_bits = max_t(int, spec.field_width, 0); > > - /* current bit is 'cur', most recently seen range is [rbot, rtop] */ > > - int cur, rbot, rtop; > > - bool first = true; > > + char *start = buf; > > + int b, e; > > > > if (check_pointer(&buf, end, bitmap, spec)) > > return buf; > > > > - rbot = cur = find_first_bit(bitmap, nr_bits); > > - while (cur < nr_bits) { > > - rtop = cur; > > - cur = find_next_bit(bitmap, nr_bits, cur + 1); > > - if (cur < nr_bits && cur <= rtop + 1) > > - continue; > > + for_each_set_bitrange(b, e, bitmap, nr_bits) { > > + buf = number(buf, end, b, default_dec_spec); > > + if (e == b + 1) > > + goto put_comma; > > Using a goto to skip a few lines instead of just having the reverse > conditional is rather sloppy IMO. > > if (e != b + 1) { > if (buf < end) > *buf = '-'; > buf++; > buf = number(buf, end, e - 1, default_dec_spec); > } > > Is much clearer. I don't think it's clearer, but as you wish. > > > > - if (!first) { > > - if (buf < end) > > - *buf = ','; > > - buf++; > > - } > > - first = false; > > + if (buf < end) > > + *buf = '-'; > > > > - buf = number(buf, end, rbot, default_dec_spec); > > - if (rbot < rtop) { > > - if (buf < end) > > - *buf = '-'; > > - buf++; > > + buf = number(++buf, end, e - 1, default_dec_spec); > > +put_comma: > > + if (buf < end) > > + *buf = ','; > > + buf++; > > + } > > > > - buf = number(buf, end, rtop, default_dec_spec); > > - } > > + if (buf > start) > > + buf--; > > If the above is to undo the last comma, please put back the first logic. > > -- Steve You're asking me to move part of the logic inside the loop which generally should be avoided. Is there any particular reason to do this? > > > > > - rbot = cur; > > - } > > return buf; > > } > > ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-15 15:50 ` Yury Norov @ 2021-07-16 13:46 ` Petr Mladek 2021-07-16 17:05 ` Yury Norov 0 siblings, 1 reply; 8+ messages in thread From: Petr Mladek @ 2021-07-16 13:46 UTC (permalink / raw) To: Yury Norov Cc: Steven Rostedt, linux-kernel, Andy Shevchenko, Rasmus Villemoes, Sergey Senozhatsky, Tejun Heo On Thu 2021-07-15 08:50:21, Yury Norov wrote: > On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote: > > On Thu, 8 Jul 2021 20:45:19 -0700 > > Yury Norov <yury.norov@gmail.com> wrote: > > > > > bitmap_list_string() is very ineffective when printing bitmaps with long > > > ranges of set bits because it calls find_next_bit for each bit. We can do > > > better by detecting ranges of set bits. > > > diff --git a/lib/vsprintf.c b/lib/vsprintf.c > > > index 87acf66f0e4c..1ee54dace71e 100644 > > > --- a/lib/vsprintf.c > > > +++ b/lib/vsprintf.c > > > > > > - buf = number(buf, end, rtop, default_dec_spec); > > > - } > > > + if (buf > start) > > > + buf--; > > > > If the above is to undo the last comma, please put back the first logic. > > You're asking me to move part of the logic inside the loop which generally > should be avoided. Is there any particular reason to do this? vsprintf() should write what is needed and keep the rest of the given buffer intact. There is even a test for this in the test_printf module. I think that test_printf does not complain here because only a single character is used and it is later replaced by the trailing '\0'. By other words, undoing the last comma does not cause visible problems in the end. But from vsprintf() point of view, it is a hack that does not trigger the warning only by chance. And it is better to avoid it. Best Regards, Petr ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange 2021-07-16 13:46 ` Petr Mladek @ 2021-07-16 17:05 ` Yury Norov 0 siblings, 0 replies; 8+ messages in thread From: Yury Norov @ 2021-07-16 17:05 UTC (permalink / raw) To: Petr Mladek Cc: Steven Rostedt, linux-kernel, Andy Shevchenko, Rasmus Villemoes, Sergey Senozhatsky, Tejun Heo On Fri, Jul 16, 2021 at 03:46:43PM +0200, Petr Mladek wrote: > On Thu 2021-07-15 08:50:21, Yury Norov wrote: > > On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote: > > > On Thu, 8 Jul 2021 20:45:19 -0700 > > > Yury Norov <yury.norov@gmail.com> wrote: > > > > > > > bitmap_list_string() is very ineffective when printing bitmaps with long > > > > ranges of set bits because it calls find_next_bit for each bit. We can do > > > > better by detecting ranges of set bits. > > > > diff --git a/lib/vsprintf.c b/lib/vsprintf.c > > > > index 87acf66f0e4c..1ee54dace71e 100644 > > > > --- a/lib/vsprintf.c > > > > +++ b/lib/vsprintf.c > > > > > > > > - buf = number(buf, end, rtop, default_dec_spec); > > > > - } > > > > + if (buf > start) > > > > + buf--; > > > > > > If the above is to undo the last comma, please put back the first logic. > > > > You're asking me to move part of the logic inside the loop which generally > > should be avoided. Is there any particular reason to do this? > > vsprintf() should write what is needed and keep the rest of the given > buffer intact. There is even a test for this in the test_printf module. > > I think that test_printf does not complain here because only a single > character is used and it is later replaced by the trailing '\0'. > > By other words, undoing the last comma does not cause visible problems > in the end. But from vsprintf() point of view, it is a hack that does > not trigger the warning only by chance. And it is better to avoid it. > > Best Regards, > Petr Ah, OK. Thanks Petr. ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2021-07-16 17:05 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-07-09 3:45 [PATCH 0/2] bitmap: introduce for_each_set_bitrange() Yury Norov 2021-07-09 3:45 ` [PATCH 1/2] lib: bitmap: add performance test for bitmap_print_to_pagebuf Yury Norov 2021-07-09 3:45 ` [PATCH 2/2] bitmap: introduce for_each_set_bitrange Yury Norov 2021-07-09 6:21 ` Yury Norov 2021-07-09 13:59 ` Steven Rostedt 2021-07-15 15:50 ` Yury Norov 2021-07-16 13:46 ` Petr Mladek 2021-07-16 17:05 ` Yury Norov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).