Skip to contentSkip to conversation

lib: rework bitmap_parse

PATCH In review Yury Norov 3 participants 15 messages Apr 28, 2019 – May 1, 2019

Subsystems (4)
lore
Share & tools
lore

Yury Norov

author maintainer
#0 lore raw

cover lib: rework bitmap_parse

On top of next-20190418.

Similarly to recently revisited bitmap_parselist() [1], bitmap_parse() is ineffective and overcomplicated. This series reworks it, aligns its interface with bitmap_parselist() and makes usage simpler.

The series also adds a test for the function and fixes usage of it in cpumask_parse() according to new design - drops the calculating of length of an input string.

The following users would also consider to drop the length argument, if possible:
drivers/block/drbd/drbd_main.c:2608
kernel/padata.c:924
net/core/net-sysfs.c:726
net/core/net-sysfs.c:1309
net/core/net-sysfs.c:1391

bitmap_parse() takes the array of numbers to be put into the map in the BE order which is reversed to the natural LE order for bitmaps. For example, to construct bitmap containing a bit on the position 42, we have to put a line '400,0'. Current implementation reads chunk one by one from the beginning ('400' before '0') and makes bitmap shift after each successful parse. It makes the complexity of the whole process as O(n^2). We can do it in reverse direction ('0' before '400') and avoid shifting, but it requires reverse parsing helpers.

Tested on arm64 and BE mips.

[1] https://lkml.org/lkml/2019/4/16/66

Yury Norov (6):
lib/string: add strnchrnul()
bitops: more BITS_TO_* macros
lib/bitmap: make bitmap_parse_user a wrapper on bitmap_parse
lib: rework bitmap_parse()
lib: add test for bitmap_parse()
cpumask: don't calculate length of the input string

 include/linux/bitmap.h       |   8 +-
 include/linux/bitops.h       |   3 +
 include/linux/cpumask.h      |   4 +-
 include/linux/string.h       |   3 +
 lib/bitmap.c                 | 197 +++++++++++++++++------------------
 lib/string.c                 |  20 ++++
 lib/test_bitmap.c            | 102 +++++++++++++++++-
 tools/include/linux/bitops.h |   9 +-
 8 files changed, 230 insertions(+), 116 deletions(-)
Signature · 1 line
2.17.1
author maintainer
#1 lore raw

PATCH 1/6 lib/string: add strnchrnul()

New function works like strchrnul() with a length limited strings.

---
 include/linux/string.h |  3 +++
 lib/string.c           | 20 ++++++++++++++++++++
 2 files changed, 23 insertions(+)
include/linux/string.h +3 -0
index 4deb11f7976b..69e8df51b630 100644
@@ -62,6 +62,9 @@ extern char * strchr(const char *,int);
 #ifndef __HAVE_ARCH_STRCHRNUL
 extern char * strchrnul(const char *,int);
 #endif
+#ifndef __HAVE_ARCH_STRNCHRNUL
+extern char * strnchrnul(const char *, int, int);
+#endif
 #ifndef __HAVE_ARCH_STRNCHR
 extern char * strnchr(const char *, size_t, int);
 #endif
lib/string.c +20 -0
index 6016eb3ac73d..dd99e6ac517a 100644
@@ -429,6 +429,26 @@ char *strchrnul(const char *s, int c)
 EXPORT_SYMBOL(strchrnul);
 #endif
 
+#ifndef __HAVE_ARCH_STRNCHRNUL
+/**
+ * strnchrnul - Find and return a character in a length limited string,
+ * or end of string
+ * @s: The string to be searched
+ * @count: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the null byte at the end of s.
+ */
+char *strnchrnul(const char *s, int count, int c)
+{
+	while (count-- && *s && *s != (char)c)
+		s++;
+	return (char *)s;
+}
+EXPORT_SYMBOL(strnchrnul);
+#endif
+
 #ifndef __HAVE_ARCH_STRRCHR
 /**
  * strrchr - Find the last occurrence of a character in a string
Signature · 1 line
2.17.1
#2 lore raw

Re: [PATCH 1/6] lib/string: add strnchrnul()

Quoted 1 line · Yury Norov

New function works like strchrnul() with a length limited strings.

The prototype better to be consistent with strchrnul() and memchr(), i.e. the size parameter to go last.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#3 lore raw

Re: [PATCH 1/6] lib/string: add strnchrnul()

Quoted 5 lines · Andy Shevchenko
Quoted 1 line · Yury Norov

New function works like strchrnul() with a length limited strings.

The prototype better to be consistent with strchrnul() and memchr(), i.e. the size parameter to go last.

But if so it would be inconsistent with strnchr(). I'm OK to do the change, but I'm not sure if this version better than that.

Parameter 'count' should be size_t, not int.

#4 lore raw

Re: [PATCH 1/6] lib/string: add strnchrnul()

Quoted 9 lines · Yury Norov
Quoted 5 lines · Andy Shevchenko
Quoted 1 line · Yury Norov

New function works like strchrnul() with a length limited strings.

The prototype better to be consistent with strchrnul() and memchr(), i.e. the size parameter to go last.

But if so it would be inconsistent with strnchr(). I'm OK to do the change, but I'm not sure if this version better than that.

Forgot to check it. In this case, yes, strnchr() + size.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#5 lore raw

Re: [PATCH 1/6] lib/string: add strnchrnul()

In reply to Yury Norov
Quoted 13 lines · Yury Norov

New function works like strchrnul() with a length limited strings.

---
 include/linux/string.h |  3 +++
 lib/string.c           | 20 ++++++++++++++++++++
 2 files changed, 23 insertions(+)
include/linux/string.h +0 -0
index 4deb11f7976b..69e8df51b630 100644

include/linux/string.h extern char * strchr(const char *,int); · line 65

Quoted 4 lines
include/linux/string.h +1 -0
@@ -62,6 +62,9 @@ extern char * strchr(const char *,int);
 #ifndef __HAVE_ARCH_STRCHRNUL
 extern char * strchrnul(const char *,int);
 #endif
+#ifndef __HAVE_ARCH_STRNCHRNUL

I find it unlikely this would ever be performance-critical, so an arch would want to implement its own. Please let's avoid adding redundant ifdeffery (and yes, there's probably quite a few of the existing ones that should go away).

include/linux/string.h extern char * strchr(const char *,int);

Quoted 11 lines
include/linux/string.h +10 -0
+#ifndef __HAVE_ARCH_STRNCHRNUL
+/**
+ * strnchrnul - Find and return a character in a length limited string,
+ * or end of string
+ * @s: The string to be searched
+ * @count: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the null byte at the end of s.

Pet peeve: nul, not null. Especially important when this is in contrast to returning a NULL pointer. Also, the description is inaccurate; the whole point of the n-variant is that there is not necessarily any nul terminator.

include/linux/string.h

Quoted 3 lines

+ */

include/linux/string.h +2 -0
+char *strnchrnul(const char *s, int count, int c)
+{

Yes, make count size_t so it's easier to distinguish from the c, and keep this parameter ordering (that matches the str n chr name).

include/linux/string.h

Quoted 5 lines
include/linux/string.h +5 -0
+	while (count-- && *s && *s != (char)c)
+		s++;
+	return (char *)s;
+}
+EXPORT_SYMBOL(strnchrnul);

This can be added if a modular user shows up. No reason to add that bloat to the kernel image immediately.

Rasmus

author maintainer
#6 lore raw

PATCH 2/6 bitops: more BITS_TO_* macros

In reply to Yury Norov

Introduce BITS_TO_U64, BITS_TO_U32 and BITS_TO_BYTES as they are handy in the following changes (BITS_TO_U32 specifically). Sync tools/ version of the macros with the kernel implementation.

---
 include/linux/bitops.h       | 3 +++
 tools/include/linux/bitops.h | 9 +++++----
 2 files changed, 8 insertions(+), 4 deletions(-)
include/linux/bitops.h +3 -0
index cf074bce3eb3..3477e179dca7 100644
@@ -6,6 +6,9 @@
 
 #define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
 #define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
+#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
+#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
+#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
 
 extern unsigned int __sw_hweight8(unsigned int w);
 extern unsigned int __sw_hweight16(unsigned int w);
tools/include/linux/bitops.h +5 -4
index 0b0ef3abc966..959dcb8214ba 100644
@@ -13,10 +13,11 @@
 #include <linux/bits.h>
 #include <linux/compiler.h>
 
-#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
-#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64))
-#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32))
-#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE)
+#define BITS_PER_TYPE(type)	(sizeof(type) * BITS_PER_BYTE)
+#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
+#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
+#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
+#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
 
 extern unsigned int __sw_hweight8(unsigned int w);
 extern unsigned int __sw_hweight16(unsigned int w);
Signature · 1 line
2.17.1
#7 lore raw

Re: [PATCH 2/6] bitops: more BITS_TO_* macros

Quoted 3 lines · Yury Norov

Introduce BITS_TO_U64, BITS_TO_U32 and BITS_TO_BYTES as they are handy in the following changes (BITS_TO_U32 specifically). Sync tools/ version of the macros with the kernel implementation.

AFAICS you basically reimplement them for kernel use from tools/.

Quoted 1 line

#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)

Hmm... no TAB here? Perhaps another small fix can be done.

Quoted 24 lines

#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))

include/linux/bitops.h +3 -0
+#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
+#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
+#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
 
 extern unsigned int __sw_hweight8(unsigned int w);
 extern unsigned int __sw_hweight16(unsigned int w);
tools/include/linux/bitops.h +5 -4
index 0b0ef3abc966..959dcb8214ba 100644
@@ -13,10 +13,11 @@
 #include <linux/bits.h>
 #include <linux/compiler.h>
 
-#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
-#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64))
-#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32))
-#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE)
+#define BITS_PER_TYPE(type)	(sizeof(type) * BITS_PER_BYTE)
+#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
+#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
+#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
+#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#8 lore raw

PATCH 3/6 lib/bitmap: make bitmap_parse_user a wrapper on bitmap_parse

In reply to Yury Norov

Currently we parse user data byte after byte which leads to overcomplicating of parsing algorithm. There are no performance critical users of bitmap_parse_user(), and so we can duplicate user data to kernel buffer and simply call bitmap_parselist(). This rework lets us unify and simplify bitmap_parse() and bitmap_parse_user(), which is done in the following patch.

---
 lib/bitmap.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)
lib/bitmap.c +10 -10
index f235434df87b..300732031fad 100644
@@ -434,22 +434,22 @@ EXPORT_SYMBOL(__bitmap_parse);
  *    then it must be terminated with a \0.
  * @maskp: pointer to bitmap array that will contain result.
  * @nmaskbits: size of bitmap, in bits.
- *
- * Wrapper for __bitmap_parse(), providing it with user buffer.
- *
- * We cannot have this as an inline function in bitmap.h because it needs
- * linux/uaccess.h to get the access_ok() declaration and this causes
- * cyclic dependencies.
  */
 int bitmap_parse_user(const char __user *ubuf,
 			unsigned int ulen, unsigned long *maskp,
 			int nmaskbits)
 {
-	if (!access_ok(ubuf, ulen))
-		return -EFAULT;
-	return __bitmap_parse((const char __force *)ubuf,
-				ulen, 1, maskp, nmaskbits);
+	char *buf;
+	int ret;
 
+	buf = memdup_user_nul(ubuf, ulen);
+	if (IS_ERR(buf))
+		return PTR_ERR(buf);
+
+	ret = bitmap_parse(buf, ulen, maskp, nmaskbits);
+
+	kfree(buf);
+	return ret;
 }
 EXPORT_SYMBOL(bitmap_parse_user);
 
Signature · 1 line
2.17.1
author maintainer
#9 lore raw

PATCH 4/6 lib: rework bitmap_parse()

In reply to Yury Norov

bitmap_parse() is ineffective and full of opaque variables and opencoded parts. It leads to hard understanding of it. This rework includes:
- remove bitmap_shift_left() call from the cycle. Now it makes the complexity of the algorithm as O(nbits^2). In the suggested approach the input string is parsed in reverse direction, so no shifts needed;
- relax requirement on a single comma and no white spaces between chunks. It is considered useful in scripting, and it aligns with bitmap_parselist();
- split bitmap_parse() to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of the bitmap_parse() won't bother doing this.

---
 include/linux/bitmap.h |   8 +-
 lib/bitmap.c           | 179 ++++++++++++++++++++---------------------
 2 files changed, 88 insertions(+), 99 deletions(-)
include/linux/bitmap.h +1 -7
index f58e97446abc..c3e84864cc33 100644
@@ -172,7 +172,7 @@ bitmap_find_next_zero_area(unsigned long *map,
 					      align_mask, 0);
 }
 
-extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
+extern int bitmap_parse(const char *buf, unsigned int buflen,
 			unsigned long *dst, int nbits);
 extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
 			unsigned long *dst, int nbits);
@@ -408,12 +408,6 @@ static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *sr
 		__bitmap_shift_left(dst, src, shift, nbits);
 }
 
-static inline int bitmap_parse(const char *buf, unsigned int buflen,
-			unsigned long *maskp, int nmaskbits)
-{
-	return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
-}
-
 /**
  * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
  * @n: u64 value
lib/bitmap.c +87 -92

209 lines not on this page · raw message

Signature · 1 line
2.17.1
#10 lore raw

Re: [PATCH 4/6] lib: rework bitmap_parse()

Quoted 12 lines · Yury Norov

bitmap_parse() is ineffective and full of opaque variables and opencoded parts. It leads to hard understanding of it. This rework includes:
- remove bitmap_shift_left() call from the cycle. Now it makes the complexity of the algorithm as O(nbits^2). In the suggested approach the input string is parsed in reverse direction, so no shifts needed;
- relax requirement on a single comma and no white spaces between chunks. It is considered useful in scripting, and it aligns with bitmap_parselist();
- split bitmap_parse() to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of the bitmap_parse() won't bother doing this.

lib/bitmap.c static inline bool end_of_region(char c) · line 461

Quoted 5 lines
lib/bitmap.c +5 -0
+static inline bool in_str(const char *start, const char *ptr)
+{
+	return start <= ptr;
+}
+

I don't see how it's better than explicit use. Moreover, explicit use shows the exact condition in-line. Even by used characters it's longer.

lib/bitmap.c int bitmap_parselist_user(const char __user *ubuf, · line 606

Quoted 2 lines
lib/bitmap.c +2 -0
+static const char *bitmap_get_hex32_rev(const char *start,
+					const char *end, u32 *num)

In kernel few functions to work with hex u32 named foo_x32(). I would rather use that. Besides, we spell "reverse" in full.

lib/bitmap.c int bitmap_parselist_user(const char __user *ubuf, · line 616

Quoted 10 lines
lib/bitmap.c +10 -0
+{
+	u32 ret = 0;
+	int c, i;
+
+	if (hex_to_bin(*end) < 0)
+		return ERR_PTR(-EINVAL);
+
+	for (i = 0; i < 32; i += 4) {
+		c = hex_to_bin(*end--);
+		if (c < 0)

Perhaps we may need similar patch for hex_to_bin() as in the commit 9888a588ea96 ("lib/hexdump.c: return -EINVAL in case of error in hex2bin()")

Quoted 15 lines
lib/bitmap.c +14 -0
+			return ERR_PTR(-EINVAL);
 
+
+		ret |= c << i;
+
+		if (!in_str(start, end) || __end_of_region(*end))
+			goto out;
+	}
+
+	if (hex_to_bin(*end) >= 0)
+		return ERR_PTR(-EOVERFLOW);
+out:
+	*num = ret;
+	return end;
+}
Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#11 lore raw

Re: [PATCH 4/6] lib: rework bitmap_parse()

Quoted 13 lines · Andy Shevchenko
Quoted 11 lines · Yury Norov

bitmap_parse() is ineffective and full of opaque variables and opencoded parts. It leads to hard understanding of it. This rework includes:
- remove bitmap_shift_left() call from the cycle. Now it makes the complexity of the algorithm as O(nbits^2). In the suggested approach the input string is parsed in reverse direction, so no shifts needed;
- relax requirement on a single comma and no white spaces between chunks. It is considered useful in scripting, and it aligns with bitmap_parselist();
- split bitmap_parse() to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of the bitmap_parse() won't bother doing this.

Quoted 8 lines

lib/bitmap.c static inline bool end_of_region(char c) · line 461

Quoted 5 lines
lib/bitmap.c +5 -0
+static inline bool in_str(const char *start, const char *ptr)
+{
+	return start <= ptr;
+}
+

I don't see how it's better than explicit use. Moreover, explicit use shows the exact condition in-line. Even by used characters it's longer.

I did 2 mistakes with a condition ('<' instead of '<=') during the development, after that I decided to introduce it. I would prefer keep it.

Quoted 5 lines

lib/bitmap.c int bitmap_parselist_user(const char __user *ubuf, · line 606

Quoted 2 lines
lib/bitmap.c +2 -0
+static const char *bitmap_get_hex32_rev(const char *start,
+					const char *end, u32 *num)

In kernel few functions to work with hex u32 named foo_x32(). I would rather use that. Besides, we spell "reverse" in full.

OK

Quoted 34 lines

lib/bitmap.c int bitmap_parselist_user(const char __user *ubuf, · line 616

Quoted 10 lines
lib/bitmap.c +10 -0
+{
+	u32 ret = 0;
+	int c, i;
+
+	if (hex_to_bin(*end) < 0)
+		return ERR_PTR(-EINVAL);
+
+	for (i = 0; i < 32; i += 4) {
+		c = hex_to_bin(*end--);
+		if (c < 0)

Perhaps we may need similar patch for hex_to_bin() as in the commit 9888a588ea96 ("lib/hexdump.c: return -EINVAL in case of error in hex2bin()")

Quoted 15 lines
lib/bitmap.c +14 -0
+			return ERR_PTR(-EINVAL);
 
+
+		ret |= c << i;
+
+		if (!in_str(start, end) || __end_of_region(*end))
+			goto out;
+	}
+
+	if (hex_to_bin(*end) >= 0)
+		return ERR_PTR(-EOVERFLOW);
+out:
+	*num = ret;
+	return end;
+}
Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#12 lore raw

PATCH 5/6 lib: add test for bitmap_parse()

In reply to Yury Norov

The test is derived from bitmap_parselist()

---
 lib/test_bitmap.c | 102 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 101 insertions(+), 1 deletion(-)
lib/test_bitmap.c +101 -1
index d3a501f2a81a..99ad6c35d038 100644
@@ -205,7 +205,8 @@ static void __init test_copy(void)
 	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 }
 
-#define PARSE_TIME 0x1
+#define PARSE_TIME	0x1
+#define NO_LEN		0x2
 
 struct test_bitmap_parselist{
 	const int errno;
@@ -328,6 +329,93 @@ static void __init __test_bitmap_parselist(int is_user)
 	}
 }
 
+static const unsigned long parse_test[] __initconst = {
+	BITMAP_FROM_U64(0),
+	BITMAP_FROM_U64(1),
+	BITMAP_FROM_U64(0xdeadbeef),
+	BITMAP_FROM_U64(0x100000000ULL),
+};
+
+static const unsigned long parse_test2[] __initconst = {
+	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
+	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
+	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
+};
+
+static const struct test_bitmap_parselist parse_tests[] __initconst = {
+	{0, "",				&parse_test[0 * step], 32, 0},
+	{0, " ",			&parse_test[0 * step], 32, 0},
+	{0, "0",			&parse_test[0 * step], 32, 0},
+	{0, "0\n",			&parse_test[0 * step], 32, 0},
+	{0, "1",			&parse_test[1 * step], 32, 0},
+	{0, "deadbeef",			&parse_test[2 * step], 32, 0},
+	{0, "1,0",			&parse_test[3 * step], 33, 0},
+	{0, "deadbeef,\n,0,1",		&parse_test[2 * step], 96, 0},
+
+	{0, "deadbeef,1,0",		&parse_test2[0 * 2 * step], 96, 0},
+	{0, "baadf00d,deadbeef,1,0",	&parse_test2[1 * 2 * step], 128, 0},
+	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, 0},
+	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, NO_LEN},
+	{0, "  badf00d,deadbeef,1,0  ",	&parse_test2[2 * 2 * step], 124, 0},
+	{0, " , badf00d,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},
+	{0, " , badf00d, ,, ,,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},
+
+	{-EINVAL,    "goodfood,deadbeef,1,0",	NULL, 128, 0},
+	{-EOVERFLOW, "3,0",			NULL, 33, 0},
+	{-EOVERFLOW, "123badf00d,deadbeef,1,0",	NULL, 128, 0},
+	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 90, 0},
+	{-EOVERFLOW, "fbadf00d,deadbeef,1,0",	NULL, 95, 0},
+	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 100, 0},
+};
+
+static void __init __test_bitmap_parse(int is_user)
+{
+	int i;
+	int err;
+	ktime_t time;
+	DECLARE_BITMAP(bmap, 2048);
+	char *mode = is_user ? "_user"  : "";
+
+	for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
+		struct test_bitmap_parselist test = parse_tests[i];
+
+		if (is_user) {
+			size_t len = strlen(test.in);
+			mm_segment_t orig_fs = get_fs();
+
+			set_fs(KERNEL_DS);
+			time = ktime_get();
+			err = bitmap_parse_user(test.in, len, bmap, test.nbits);
+			time = ktime_get() - time;
+			set_fs(orig_fs);
+		} else {
+			size_t len = test.flags & NO_LEN ?
+				UINT_MAX : strlen(test.in);
+			time = ktime_get();
+			err = bitmap_parse(test.in, len, bmap, test.nbits);
+			time = ktime_get() - time;
+		}
+
+		if (err != test.errno) {
+			pr_err("parse%s: %d: input is %s, errno is %d, expected %d\n",
+					mode, i, test.in, err, test.errno);
+			continue;
+		}
+
+		if (!err && test.expected
+			 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
+			pr_err("parse%s: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
+					mode, i, test.in, bmap[0],
+					*test.expected);
+			continue;
+		}
+
+		if (test.flags & PARSE_TIME)
+			pr_err("parse%s: %d: input is '%s' OK, Time: %llu\n",
+					mode, i, test.in, time);
+	}
+}
+
 static void __init test_bitmap_parselist(void)
 {
 	__test_bitmap_parselist(0);
@@ -338,6 +426,16 @@ static void __init test_bitmap_parselist_user(void)
 	__test_bitmap_parselist(1);
 }
 
+static void __init test_bitmap_parse(void)
+{
+	__test_bitmap_parse(0);
+}
+
+static void __init test_bitmap_parse_user(void)
+{
+	__test_bitmap_parse(1);
+}
+
 #define EXP_BYTES	(sizeof(exp) * 8)
 
 static void __init test_bitmap_arr32(void)
@@ -409,6 +507,8 @@ static void __init selftest(void)
 	test_fill_set();
 	test_copy();
 	test_bitmap_arr32();
+	test_bitmap_parse();
+	test_bitmap_parse_user();
 	test_bitmap_parselist();
 	test_bitmap_parselist_user();
 	test_mem_optimisations();
Signature · 1 line
2.17.1
author maintainer
#13 lore raw

PATCH 6/6 cpumask: don't calculate length of the input string

In reply to Yury Norov

New design of inner bitmap_parse() allows to avoid calculating the size of a null-terminated string.

---
 include/linux/cpumask.h | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
include/linux/cpumask.h +1 -3
index 21755471b1c3..d55d015edc58 100644
@@ -633,9 +633,7 @@ static inline int cpumask_parselist_user(const char __user *buf, int len,
  */
 static inline int cpumask_parse(const char *buf, struct cpumask *dstp)
 {
-	unsigned int len = strchrnul(buf, '\n') - buf;
-
-	return bitmap_parse(buf, len, cpumask_bits(dstp), nr_cpumask_bits);
+	return bitmap_parse(buf, UINT_MAX, cpumask_bits(dstp), nr_cpumask_bits);
 }
 
 /**
Signature · 1 line
2.17.1
#14 lore raw
In reply to Yury Norov
Quoted 19 lines · Yury Norov

On top of next-20190418.

Similarly to recently revisited bitmap_parselist() [1], bitmap_parse() is ineffective and overcomplicated. This series reworks it, aligns its interface with bitmap_parselist() and makes usage simpler.

The series also adds a test for the function and fixes usage of it in cpumask_parse() according to new design - drops the calculating of length of an input string.

The following users would also consider to drop the length argument, if possible:
drivers/block/drbd/drbd_main.c:2608
kernel/padata.c:924
net/core/net-sysfs.c:726
net/core/net-sysfs.c:1309
net/core/net-sysfs.c:1391

Quoted 9 lines

bitmap_parse() takes the array of numbers to be put into the map in the BE order which is reversed to the natural LE order for bitmaps. For example, to construct bitmap containing a bit on the position 42, we have to put a line '400,0'. Current implementation reads chunk one by one from the beginning ('400' before '0') and makes bitmap shift after each successful parse. It makes the complexity of the whole process as O(n^2). We can do it in reverse direction ('0' before '400') and avoid shifting, but it requires reverse parsing helpers.

Shouldn't test ceases pass on existing code base? I would rather start series with enabling tests and then we will have a proof that before and after at least tests have not been broken.

Quoted 26 lines

Tested on arm64 and BE mips.

[1] https://lkml.org/lkml/2019/4/16/66

Yury Norov (6):
lib/string: add strnchrnul()
bitops: more BITS_TO_* macros
lib/bitmap: make bitmap_parse_user a wrapper on bitmap_parse
lib: rework bitmap_parse()
lib: add test for bitmap_parse()
cpumask: don't calculate length of the input string

 include/linux/bitmap.h       |   8 +-
 include/linux/bitops.h       |   3 +
 include/linux/cpumask.h      |   4 +-
 include/linux/string.h       |   3 +
 lib/bitmap.c                 | 197 +++++++++++++++++------------------
 lib/string.c                 |  20 ++++
 lib/test_bitmap.c            | 102 +++++++++++++++++-
 tools/include/linux/bitops.h |   9 +-
 8 files changed, 230 insertions(+), 116 deletions(-)
Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards,
Andy Shevchenko