[PATCH 2/2] bitmap: introduce for_each_set_bitrange

Yury Norov
2021-07-09T03:45:39Z

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