Skip to contentSkip to conversation

lib: rework bitmap_parselist and tests

PATCH Superseded Yury Norov 3 participants 14 messages Feb 20, 2019 – Mar 15, 2019

Subsystems (2)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Yury Norov

author maintainer
#0 lore raw

v2 cover lib: rework bitmap_parselist and tests

bitmap_parselist has been evolved from a pretty simple idea for long and now lacks for refactoring. It is not structured, has nested loops and a set of opaque-named variables. All this leads to extremely hard understanding of the code. Once during the optimization of it I missed a scenario which leads to kernel hangup. Tetsuo Handa spotted this and found it simpler to rewrite the code instead fixing it. (Though, that attempt had some flaws.)
https://lkml.org/lkml/2018/4/1/93

Things are more complicated than they may be because bitmap_parselist() is part of user interface, and its behavior should not change.

In this patchset
- __bitmap_parselist() is reworked (patches 2 and 3);
- time measurement in test_bitmap_parselist switched to ktime_get (patch 4);
- new tests introduced (patch 5), and
- bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 6).

Patch 1 is a fix and may be applied separately.

V1: https://lkml.org/lkml/2018/12/23/50
v2: - use PTR_ERR() and ERR_PTR() where appropriate;
- fix parser logic (last byte of string handling);
- tests for bitmap_parselist_user() in patch 5.

Yury Norov (4):
bitmap_parselist: don't calculate length of the input string
bitmap_parselist: move non-parser logic to helpers
bitmap_parselist: rework input string parser lib/test_bitmap: switch test_bitmap_parselist to ktime_get() lib/test_bitmap: add testcases for bitmap_parselist lib/test_bitmap: add tests for bitmap_parselist_user

 lib/bitmap.c      | 293 ++++++++++++++++++++++++++++++----------------
 lib/test_bitmap.c |  67 +++++++++--
 2 files changed, 245 insertions(+), 115 deletions(-)
Signature · 1 line
2.17.1
author maintainer
#1 lore raw

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

bitmap_parselist() calculates length of the input string before passing it to the __bitmap_parselist(). But the end-of-line condition is checked for every character in __bitmap_parselist() anyway. So doing it in wrapper is a simple waste of time.

---
 lib/bitmap.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
lib/bitmap.c +1 -4
index 98872e9025da..ad1fb7e6ad0e 100644
@@ -614,10 +614,7 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 
 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
 {
-	char *nl  = strchrnul(bp, '\n');
-	int len = nl - bp;
-
-	return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
+	return __bitmap_parselist(bp, UINT_MAX, 0, maskp, nmaskbits);
 }
 EXPORT_SYMBOL(bitmap_parselist);
 
Signature · 1 line
2.17.1
author maintainer
#2 lore raw

PATCH 2/6 bitmap_parselist: move non-parser logic to helpers

In reply to Yury Norov

Move region checking and setting functionality of __bitmap_parselist() to helpers.

---
 lib/bitmap.c | 64 +++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 53 insertions(+), 11 deletions(-)
lib/bitmap.c +53 -11
index ad1fb7e6ad0e..307a1b20bead 100644
@@ -477,6 +477,42 @@ int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 }
 EXPORT_SYMBOL(bitmap_print_to_pagebuf);
 
+/*
+ * Region 9-38:4/10 describes the following bitmap structure:
+ * 0	   9  12    18			38
+ * .........****......****......****......
+ *	    ^  ^     ^			 ^
+ *      start  off   grlen	       end
+ */
+struct region {
+	unsigned int start;
+	unsigned int off;
+	unsigned int grlen;
+	unsigned int end;
+};
+
+static int bitmap_set_region(const struct region *r,
+				unsigned long *bitmap, int nbits)
+{
+	unsigned int start;
+
+	if (r->end >= nbits)
+		return -ERANGE;
+
+	for (start = r->start; start <= r->end; start += r->grlen)
+		bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
+
+	return 0;
+}
+
+static int bitmap_check_region(const struct region *r)
+{
+	if (r->start > r->end || r->grlen == 0 || r->off > r->grlen)
+		return -EINVAL;
+
+	return 0;
+}
+
 /**
  * __bitmap_parselist - convert list format ASCII string to bitmap
  * @buf: read nul-terminated user string from this buffer
@@ -507,10 +543,11 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 		int nmaskbits)
 {
 	unsigned int a, b, old_a, old_b;
-	unsigned int group_size, used_size, off;
+	unsigned int group_size, used_size;
 	int c, old_c, totaldigits, ndigits;
 	const char __user __force *ubuf = (const char __user __force *)buf;
-	int at_start, in_range, in_partial_range;
+	int at_start, in_range, in_partial_range, ret;
+	struct region r;
 
 	totaldigits = c = 0;
 	old_a = old_b = 0;
@@ -599,15 +636,20 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 		/* if no digit is after '-', it's wrong*/
 		if (at_start && in_range)
 			return -EINVAL;
-		if (!(a <= b) || group_size == 0 || !(used_size <= group_size))
-			return -EINVAL;
-		if (b >= nmaskbits)
-			return -ERANGE;
-		while (a <= b) {
-			off = min(b - a + 1, used_size);
-			bitmap_set(maskp, a, off);
-			a += group_size;
-		}
+
+		r.start = a;
+		r.off = used_size;
+		r.grlen = group_size;
+		r.end = b;
+
+		ret = bitmap_check_region(&r);
+		if (ret)
+			return ret;
+
+		ret = bitmap_set_region(&r, maskp, nmaskbits);
+		if (ret)
+			return ret;
+
 	} while (buflen && c == ',');
 	return 0;
 }
Signature · 1 line
2.17.1
author maintainer
#3 lore raw

PATCH 3/6 bitmap_parselist: rework input string parser

In reply to Yury Norov

The requirement for this rework is to keep the __bitmap_parselist() copy-less and single-pass but make it more readable and maintainable by splitting into logical parts and removing explicit nested cycles and opaque local variables.

__bitmap_parselist() can parse userspace inputs and therefore we cannot use simple_strtoul() to parse numbers.

---
 lib/bitmap.c | 246 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 148 insertions(+), 98 deletions(-)
lib/bitmap.c +148 -98
index 307a1b20bead..f1c42ee8b8f2 100644
@@ -513,6 +513,139 @@ static int bitmap_check_region(const struct region *r)
 	return 0;
 }
 
+static long get_char(char *c, const char *str, int is_user)
+{
+	if (unlikely(is_user))
+		return __get_user(*c, (const char __force __user *)str);
+
+	*c = *str;
+	return 0;
+}
+
+static const char *bitmap_getnum(unsigned int *num, const char *str,
+			    const char *const end, int is_user)
+{
+	unsigned int n = 0;
+	const char *_str;
+	long ret;
+	char c;
+
+	for (_str = str, *num = 0; _str <= end; _str++) {
+		ret = get_char(&c, _str, is_user);
+		if (ret)
+			return ERR_PTR(ret);
+
+		if (!isdigit(c)) {
+			if (_str == str)
+				return ERR_PTR(-EINVAL);
+
+			return _str;
+		}
+
+		*num = *num * 10 + (c - '0');
+		if (*num < n)
+			return ERR_PTR(-EOVERFLOW);
+
+		n = *num;
+	}
+
+	return _str;
+}
+
+static const char *bitmap_find_region(const char *str,
+			const char *const end, int is_user)
+{
+	long ret;
+	char c;
+
+	for (; str <= end; str++) {
+		ret = get_char(&c, str, is_user);
+		if (ret)
+			return ERR_PTR(ret);
+
+		/* Unexpected end of line. */
+		if (c == 0 || c == '\n')
+			return NULL;
+
+		/*
+		 * The format allows commas and whitespases
+		 * at the beginning of the region, so skip it.
+		 */
+		if (!isspace(c) && c != ',')
+			break;
+	}
+
+	return str <= end ? str : NULL;
+}
+
+static const char *bitmap_parse_region(struct region *r, const char *str,
+				 const char *const end, int is_user)
+{
+	long ret;
+	char c;
+
+	str = bitmap_getnum(&r->start, str, end, is_user);
+	if (IS_ERR(str))
+		return str;
+
+	ret = get_char(&c, str, is_user);
+	if (ret)
+		return (char *)ret;
+
+	if (c == 0 || c == '\n') {
+		str = end + 1;
+		goto no_end;
+	}
+
+	if (isspace(c) || c == ',')
+		goto no_end;
+
+	if (c != '-')
+		return ERR_PTR(-EINVAL);
+
+	str = bitmap_getnum(&r->end, str + 1, end, is_user);
+	if (IS_ERR(str))
+		return str;
+
+	ret = get_char(&c, str, is_user);
+	if (ret)
+		return ERR_PTR(ret);
+
+	if (c == 0 || c == '\n') {
+		str = end + 1;
+		goto no_pattern;
+	}
+
+	if (isspace(c) || c == ',')
+		goto no_pattern;
+
+	if (c != ':')
+		return ERR_PTR(-EINVAL);
+
+	str = bitmap_getnum(&r->off, str + 1, end, is_user);
+	if (IS_ERR(str))
+		return str;
+
+	ret = get_char(&c, str, is_user);
+	if (ret)
+		return (char *)ret;
+
+	if (c != '/')
+		return ERR_PTR(-EINVAL);
+
+	str = bitmap_getnum(&r->grlen, str + 1, end, is_user);
+
+	return str;
+
+no_end:
+	r->end = r->start;
+no_pattern:
+	r->off = r->end + 1;
+	r->grlen = r->end + 1;
+
+	return str;
+}
+
 /**
  * __bitmap_parselist - convert list format ASCII string to bitmap
  * @buf: read nul-terminated user string from this buffer
@@ -534,113 +667,29 @@ static int bitmap_check_region(const struct region *r)
  *
  * Returns: 0 on success, -errno on invalid input strings. Error values:
  *
- *   - ``-EINVAL``: second number in range smaller than first
+ *   - ``-EINVAL``: wrong region format
  *   - ``-EINVAL``: invalid character in string
  *   - ``-ERANGE``: bit number specified too large for mask
+ *   - ``-EOVERFLOW``: integer overflow in the input parameters
  */
-static int __bitmap_parselist(const char *buf, unsigned int buflen,
+static int __bitmap_parselist(const char *buf, const char *const end,
 		int is_user, unsigned long *maskp,
 		int nmaskbits)
 {
-	unsigned int a, b, old_a, old_b;
-	unsigned int group_size, used_size;
-	int c, old_c, totaldigits, ndigits;
-	const char __user __force *ubuf = (const char __user __force *)buf;
-	int at_start, in_range, in_partial_range, ret;
 	struct region r;
+	long ret;
 
-	totaldigits = c = 0;
-	old_a = old_b = 0;
-	group_size = used_size = 0;
 	bitmap_zero(maskp, nmaskbits);
-	do {
-		at_start = 1;
-		in_range = 0;
-		in_partial_range = 0;
-		a = b = 0;
-		ndigits = totaldigits;
 
-		/* Get the next cpu# or a range of cpu#'s */
-		while (buflen) {
-			old_c = c;
-			if (is_user) {
-				if (__get_user(c, ubuf++))
-					return -EFAULT;
-			} else
-				c = *buf++;
-			buflen--;
-			if (isspace(c))
-				continue;
 
-			/* A '\0' or a ',' signal the end of a cpu# or range */
-			if (c == '\0' || c == ',')
-				break;
-			/*
-			* whitespaces between digits are not allowed,
-			* but it's ok if whitespaces are on head or tail.
-			* when old_c is whilespace,
-			* if totaldigits == ndigits, whitespace is on head.
-			* if whitespace is on tail, it should not run here.
-			* as c was ',' or '\0',
-			* the last code line has broken the current loop.
-			*/
-			if ((totaldigits != ndigits) && isspace(old_c))
-				return -EINVAL;
-
-			if (c == '/') {
-				used_size = a;
-				at_start = 1;
-				in_range = 0;
-				a = b = 0;
-				continue;
-			}
-
-			if (c == ':') {
-				old_a = a;
-				old_b = b;
-				at_start = 1;
-				in_range = 0;
-				in_partial_range = 1;
-				a = b = 0;
-				continue;
-			}
-
-			if (c == '-') {
-				if (at_start || in_range)
-					return -EINVAL;
-				b = 0;
-				in_range = 1;
-				at_start = 1;
-				continue;
-			}
-
-			if (!isdigit(c))
-				return -EINVAL;
-
-			b = b * 10 + (c - '0');
-			if (!in_range)
-				a = b;
-			at_start = 0;
-			totaldigits++;
-		}
-		if (ndigits == totaldigits)
-			continue;
-		if (in_partial_range) {
-			group_size = a;
-			a = old_a;
-			b = old_b;
-			old_a = old_b = 0;
-		} else {
-			used_size = group_size = b - a + 1;
-		}
-		/* if no digit is after '-', it's wrong*/
-		if (at_start && in_range)
-			return -EINVAL;
+	while (buf && buf <= end) {
+		buf = bitmap_find_region(buf, end, is_user);
+		if (buf == NULL)
+			return 0;
 
-		r.start = a;
-		r.off = used_size;
-		r.grlen = group_size;
-		r.end = b;
+		buf = bitmap_parse_region(&r, buf, end, is_user);
+		if (IS_ERR(buf))
+			return PTR_ERR(buf);
 
 		ret = bitmap_check_region(&r);
 		if (ret)
@@ -649,14 +698,14 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
 		ret = bitmap_set_region(&r, maskp, nmaskbits);
 		if (ret)
 			return ret;
+	}
 
-	} while (buflen && c == ',');
 	return 0;
 }
 
 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
 {
-	return __bitmap_parselist(bp, UINT_MAX, 0, maskp, nmaskbits);
+	return __bitmap_parselist(bp, (char *)SIZE_MAX, 0, maskp, nmaskbits);
 }
 EXPORT_SYMBOL(bitmap_parselist);
 
@@ -683,7 +732,8 @@ int bitmap_parselist_user(const char __user *ubuf,
 	if (!access_ok(ubuf, ulen))
 		return -EFAULT;
 	return __bitmap_parselist((const char __force *)ubuf,
-					ulen, 1, maskp, nmaskbits);
+				  (const char __force *)ubuf + ulen - 1,
+				  1, maskp, nmaskbits);
 }
 EXPORT_SYMBOL(bitmap_parselist_user);
 
Signature · 1 line
2.17.1
author maintainer
#4 lore raw

PATCH 4/6 lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

In reply to Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

---
 lib/test_bitmap.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)
lib/test_bitmap.c +4 -5
index 6cd7d0740005..b06e0fd3811b 100644
@@ -266,15 +266,15 @@ static void __init test_bitmap_parselist(void)
 {
 	int i;
 	int err;
-	cycles_t cycles;
+	ktime_t time;
 	DECLARE_BITMAP(bmap, 2048);
 
 	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 #define ptest parselist_tests[i]
 
-		cycles = get_cycles();
+		time = ktime_get();
 		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
-		cycles = get_cycles() - cycles;
+		time = ktime_get() - time;
 
 		if (err != ptest.errno) {
 			pr_err("test %d: input is %s, errno is %d, expected %d\n",
@@ -291,8 +291,7 @@ static void __init test_bitmap_parselist(void)
 
 		if (ptest.flags & PARSE_TIME)
 			pr_err("test %d: input is '%s' OK, Time: %llu\n",
-					i, ptest.in,
-					(unsigned long long)cycles);
+					i, ptest.in, time);
 	}
 }
 
Signature · 1 line
2.17.1
#5 lore raw

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

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

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

Quoted 5 lines · Andy Shevchenko
Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

Ah, okay, it's already first for test module.
Perhaps Fixes tag and actually one or more examples of such architectures?

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

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

Quoted 9 lines · Andy Shevchenko
Quoted 5 lines · Andy Shevchenko
Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

Ah, okay, it's already first for test module.
Perhaps Fixes tag and actually one or more examples of such architectures?

Hi Andy, thanks for your time on it.

Only arm, arm64, openrisc, riscv and sparc64 #define get_cycles. So IIUC, others take stub from include/asm-generic/timex.h.

sparc32, xtensa, m68k, um, and in some cases x86, mips and nios2 provide zero-stubs explicitly.

Yury

Quoted 4 lines
Signature · 2 lines
With Best Regards,
Andy Shevchenko
#8 lore raw

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

Quoted 8 lines · On Wed, 20 Feb 2019 06:20:48 PST (-0800), [email protected] wrote:
Quoted 7 lines · Andy Shevchenko
Quoted 5 lines · Andy Shevchenko
Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

Quoted 7 lines
Quoted 2 lines

Ah, okay, it's already first for test module.
Perhaps Fixes tag and actually one or more examples of such architectures?

Hi Andy, thanks for your time on it.

Only arm, arm64, openrisc, riscv and sparc64 #define get_cycles. So IIUC, others take stub from include/asm-generic/timex.h.

Should we (RISC-V) be doing something else? It seems odd to be in such a minority here, but we do have a ISA-mandated timer so the get_cycles() implementation is super easy.

Quoted 9 lines

sparc32, xtensa, m68k, um, and in some cases x86, mips and nios2 provide zero-stubs explicitly.

Yury

Quoted 4 lines

--
With Best Regards,
Andy Shevchenko

author maintainer
#9 lore raw

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

Quoted 12 lines · Palmer Dabbelt
Quoted 11 lines · On Wed, 20 Feb 2019 06:20:48 PST (-0800), [email protected] wrote:
Quoted 9 lines · Andy Shevchenko
Quoted 5 lines · Andy Shevchenko
Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

Ah, okay, it's already first for test module.
Perhaps Fixes tag and actually one or more examples of such architectures?

Quoted 8 lines
Quoted 4 lines

Hi Andy, thanks for your time on it.

Only arm, arm64, openrisc, riscv and sparc64 #define get_cycles. So IIUC, others take stub from include/asm-generic/timex.h.

Should we (RISC-V) be doing something else? It seems odd to be in such a minority here, but we do have a ISA-mandated timer so the get_cycles() implementation is super easy.

I think you are completely fine because you are one of those who implement get_cycles().

get_cycles() is the problem for those who use it in generic code because their code surprisingly gets broken on some machines while works OK on others. This is not a problem of any specific arch.

For long term, we should inspect the non-arch code and replace get_cycles() with ktime_get() where appropriate, and avoid introducing new get_cycles() uses.

Quoted 9 lines
Quoted 9 lines

sparc32, xtensa, m68k, um, and in some cases x86, mips and nios2 provide zero-stubs explicitly.

Yury

Quoted 4 lines

--
With Best Regards,
Andy Shevchenko

author maintainer
#10 lore raw

Re: [PATCH 4/6] lib/test_bitmap: switch test_bitmap_parselist to ktime_get()

In reply to Yury Norov
Quoted 11 lines · Yury Norov
Quoted 9 lines · Andy Shevchenko
Quoted 5 lines · Andy Shevchenko
Quoted 2 lines · Yury Norov

test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead.

This sounds like a fix that should go first in the series.

Ah, okay, it's already first for test module.
Perhaps Fixes tag and actually one or more examples of such architectures?

Quoted 7 lines

Hi Andy, thanks for your time on it.

Only arm, arm64, openrisc, riscv and sparc64 #define get_cycles. So IIUC, others take stub from include/asm-generic/timex.h.

sparc32, xtensa, m68k, um, and in some cases x86, mips and nios2 provide zero-stubs explicitly.

I forgot about Fixes tag:

Fixes 6df0d464dbcc1a5 ("lib/test_bitmap.c: add test for bitmap_parselist()")

If it comes to v3, I'll add the tag and explanations above to the patch message.

author maintainer
#11 lore raw

PATCH 5/6 lib/test_bitmap: add testcases for bitmap_parselist

In reply to Yury Norov

Add tests for non-number character, empty regions, integer overflow.

---
 lib/test_bitmap.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
lib/test_bitmap.c +17 -1
index b06e0fd3811b..709424a788ee 100644
@@ -224,7 +224,8 @@ static const unsigned long exp[] __initconst = {
 	BITMAP_FROM_U64(0xffffffff),
 	BITMAP_FROM_U64(0xfffffffe),
 	BITMAP_FROM_U64(0x3333333311111111ULL),
-	BITMAP_FROM_U64(0xffffffff77777777ULL)
+	BITMAP_FROM_U64(0xffffffff77777777ULL),
+	BITMAP_FROM_U64(0),
 };
 
 static const unsigned long exp2[] __initconst = {
@@ -247,19 +248,34 @@ static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 	{0, "1-31:4/4",			&exp[9 * step], 32, 0},
 	{0, "0-31:1/4,32-63:2/4",	&exp[10 * step], 64, 0},
 	{0, "0-31:3/4,32-63:4/4",	&exp[11 * step], 64, 0},
+	{0, "  ,,  0-31:3/4  ,, 32-63:4/4  ,,  ",	&exp[11 * step], 64, 0},
 
 	{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},
 
 	{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
 
+	{0, "",				&exp[12], 8, 0},
+	{0, "\n",			&exp[12], 8, 0},
+	{0, ",,  ,,  , ,  ,",		&exp[12], 8, 0},
+	{0, " ,  ,,  , ,   ",		&exp[12], 8, 0},
+	{0, " ,  ,,  , ,   \n",		&exp[12], 8, 0},
+
 	{-EINVAL, "-1",	NULL, 8, 0},
 	{-EINVAL, "-0",	NULL, 8, 0},
 	{-EINVAL, "10-1", NULL, 8, 0},
 	{-EINVAL, "0-31:", NULL, 8, 0},
 	{-EINVAL, "0-31:0", NULL, 8, 0},
+	{-EINVAL, "0-31:0/", NULL, 8, 0},
 	{-EINVAL, "0-31:0/0", NULL, 8, 0},
 	{-EINVAL, "0-31:1/0", NULL, 8, 0},
 	{-EINVAL, "0-31:10/1", NULL, 8, 0},
+	{-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
+
+	{-EINVAL, "a-31", NULL, 8, 0},
+	{-EINVAL, "0-a1", NULL, 8, 0},
+	{-EINVAL, "a-31:10/1", NULL, 8, 0},
+	{-EINVAL, "0-31:a/1", NULL, 8, 0},
+	{-EINVAL, "0-\n", NULL, 8, 0},
 };
 
 static void __init test_bitmap_parselist(void)
Signature · 1 line
2.17.1
author maintainer
#12 lore raw

PATCH 6/6 lib/test_bitmap: add tests for bitmap_parselist_user

In reply to Yury Norov

Propagate existing bitmap_parselist() tests to bitmap_parselist_user().

---
 lib/test_bitmap.c | 46 ++++++++++++++++++++++++++++++++++++----------
 1 file changed, 36 insertions(+), 10 deletions(-)
lib/test_bitmap.c +36 -10
index 709424a788ee..d4ecac0da160 100644
@@ -11,6 +11,7 @@
 #include <linux/printk.h>
 #include <linux/slab.h>
 #include <linux/string.h>
+#include <linux/uaccess.h>
 
 static unsigned total_tests __initdata;
 static unsigned failed_tests __initdata;
@@ -278,39 +279,63 @@ static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 	{-EINVAL, "0-\n", NULL, 8, 0},
 };
 
-static void __init test_bitmap_parselist(void)
+static void __init __test_bitmap_parselist(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(parselist_tests); i++) {
 #define ptest parselist_tests[i]
 
-		time = ktime_get();
-		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
-		time = ktime_get() - time;
+		if (is_user) {
+			mm_segment_t orig_fs = get_fs();
+			size_t len = strlen(ptest.in);
+
+			set_fs(KERNEL_DS);
+			time = ktime_get();
+			err = bitmap_parselist_user(ptest.in, len,
+						    bmap, ptest.nbits);
+			time = ktime_get() - time;
+			set_fs(orig_fs);
+		} else {
+			time = ktime_get();
+			err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
+			time = ktime_get() - time;
+		}
 
 		if (err != ptest.errno) {
-			pr_err("test %d: input is %s, errno is %d, expected %d\n",
-					i, ptest.in, err, ptest.errno);
+			pr_err("parselist%s: %d: input is %s, errno is %d, expected %d\n",
+					mode, i, ptest.in, err, ptest.errno);
 			continue;
 		}
 
 		if (!err && ptest.expected
 			 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
-			pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
-					i, ptest.in, bmap[0], *ptest.expected);
+			pr_err("parselist%s: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
+					mode, i, ptest.in, bmap[0],
+					*ptest.expected);
 			continue;
 		}
 
 		if (ptest.flags & PARSE_TIME)
-			pr_err("test %d: input is '%s' OK, Time: %llu\n",
-					i, ptest.in, time);
+			pr_err("parselist%s: %d: input is '%s' OK, Time: %llu\n",
+					mode, i, ptest.in, time);
 	}
 }
 
+static void __init test_bitmap_parselist(void)
+{
+	__test_bitmap_parselist(0);
+}
+
+static void __init test_bitmap_parselist_user(void)
+{
+	__test_bitmap_parselist(1);
+}
+
 #define EXP_BYTES	(sizeof(exp) * 8)
 
 static void __init test_bitmap_arr32(void)
@@ -383,6 +408,7 @@ static int __init test_bitmap_init(void)
 	test_copy();
 	test_bitmap_arr32();
 	test_bitmap_parselist();
+	test_bitmap_parselist_user();
 	test_mem_optimisations();
 
 	if (failed_tests == 0)
Signature · 1 line
2.17.1
author maintainer
#13 lore raw
In reply to Yury Norov

Ping?

Quoted 41 lines · Yury Norov

bitmap_parselist has been evolved from a pretty simple idea for long and now lacks for refactoring. It is not structured, has nested loops and a set of opaque-named variables. All this leads to extremely hard understanding of the code. Once during the optimization of it I missed a scenario which leads to kernel hangup. Tetsuo Handa spotted this and found it simpler to rewrite the code instead fixing it. (Though, that attempt had some flaws.)
https://lkml.org/lkml/2018/4/1/93

Things are more complicated than they may be because bitmap_parselist() is part of user interface, and its behavior should not change.

In this patchset
- __bitmap_parselist() is reworked (patches 2 and 3);
- time measurement in test_bitmap_parselist switched to ktime_get (patch 4);
- new tests introduced (patch 5), and
- bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 6).

Patch 1 is a fix and may be applied separately.

V1: https://lkml.org/lkml/2018/12/23/50
v2: - use PTR_ERR() and ERR_PTR() where appropriate;
- fix parser logic (last byte of string handling);
- tests for bitmap_parselist_user() in patch 5.

Yury Norov (4):
bitmap_parselist: don't calculate length of the input string
bitmap_parselist: move non-parser logic to helpers
bitmap_parselist: rework input string parser lib/test_bitmap: switch test_bitmap_parselist to ktime_get() lib/test_bitmap: add testcases for bitmap_parselist lib/test_bitmap: add tests for bitmap_parselist_user

 lib/bitmap.c      | 293 ++++++++++++++++++++++++++++++----------------
 lib/test_bitmap.c |  67 +++++++++--
 2 files changed, 245 insertions(+), 115 deletions(-)
Signature · 1 line
2.17.1