linux-kernel - Re: [PATCH 2/2] bitmap: introduce for_each_set

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20210709095950.6a451ccb@oasis.local.home>
Date:   Fri, 9 Jul 2021 09:59:50 -0400
From:   Steven Rostedt <rostedt@...dmis.org>
To:     Yury Norov <yury.norov@...il.com>
Cc:     linux-kernel@...r.kernel.org,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Petr Mladek <pmladek@...e.com>,
        Sergey Senozhatsky <senozhatsky@...omium.org>,
        Tejun Heo <tj@...nel.org>
Subject: Re: [PATCH 2/2] bitmap: introduce for_each_set_bitrange

On Thu,  8 Jul 2021 20:45:19 -0700
Yury Norov <yury.norov@...il.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@...il.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;
>  }
>