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

Steven Rostedt
2021-07-09T14:00:00Z

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