[PATCH 0/2] bitmap: introduce for_each_set_bitrange()

[PATCH 0/2] bitmap: introduce for_each_set_bitrange()

[Yury Norov]

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

[PATCH 1/2] lib: bitmap: add performance test for bitmap_print_to_pagebuf

[Yury Norov]

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

[PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Yury Norov]

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

Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Yury Norov]

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.

Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Steven Rostedt]

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;
>  }
>  

Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Yury Norov]

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;
> >  }
> >  

Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Petr Mladek]

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

Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

[Yury Norov]

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.