* [PATCH v4 0/5] lib: rework bitmap_parselist and tests @ 2019-04-05 17:32 Yury Norov 2019-04-05 17:32 ` [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() Yury Norov ` (4 more replies) 0 siblings, 5 replies; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel 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. Things are more complicated because bitmap_parselist() is a part of user interface, and its behavior should not change. In this patchset - bitmap_parselist_user() made a wrapper on bitmap_parselist(); - bitmap_parselist() reworked (patch 2); - time measurement in test_bitmap_parselist switched to ktime_get (patch 3); - new tests introduced (patch 4), and - bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 5). v1: https://lkml.org/lkml/2018/12/23/50 v2: https://www.spinics.net/lists/kernel/msg3048976.html v3: https://lkml.org/lkml/2019/4/3/68 v4: - use handy memdup_user_nul() instead of copy_from_user() in patch 1; - comments indentation fixed. Yury Norov (5): lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() lib: rework bitmap_parselist 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 | 277 ++++++++++++++++++++++++++-------------------- lib/test_bitmap.c | 67 ++++++++--- 2 files changed, 210 insertions(+), 134 deletions(-) -- 2.17.1 ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov @ 2019-04-05 17:32 ` Yury Norov 2019-04-08 9:30 ` Andy Shevchenko 2019-04-05 17:32 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov ` (3 subsequent siblings) 4 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel Currently we parse user data byte after byte which leads to overcomplification of parsing algorithm. The only user of bitmap_parselist_user() is not performance-critical, and so we can duplicate user data to kernel buffer and simply call bitmap_parselist(). This rework lets us unify and simplify bitmap_parselist() and bitmap_parselist_user(), which is done in the following patch. Signed-off-by: Yury Norov <ynorov@marvell.com> --- lib/bitmap.c | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 98872e9025da..79ed5538617b 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -632,19 +632,22 @@ EXPORT_SYMBOL(bitmap_parselist); * @nmaskbits: size of bitmap, in bits. * * Wrapper for bitmap_parselist(), 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_parselist_user(const char __user *ubuf, unsigned int ulen, unsigned long *maskp, int nmaskbits) { - if (!access_ok(ubuf, ulen)) - return -EFAULT; - return __bitmap_parselist((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_parselist(buf, maskp, nmaskbits); + + kfree(buf); + return ret; } EXPORT_SYMBOL(bitmap_parselist_user); -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() 2019-04-05 17:32 ` [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() Yury Norov @ 2019-04-08 9:30 ` Andy Shevchenko 0 siblings, 0 replies; 14+ messages in thread From: Andy Shevchenko @ 2019-04-08 9:30 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Yury Norov, linux-kernel On Fri, Apr 05, 2019 at 08:32:07PM +0300, Yury Norov wrote: > Currently we parse user data byte after byte which leads to > overcomplification of parsing algorithm. The only user of > bitmap_parselist_user() is not performance-critical, and so we > can duplicate user data to kernel buffer and simply call > bitmap_parselist(). This rework lets us unify and simplify > bitmap_parselist() and bitmap_parselist_user(), which is done > in the following patch. > Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > Signed-off-by: Yury Norov <ynorov@marvell.com> > --- > lib/bitmap.c | 19 +++++++++++-------- > 1 file changed, 11 insertions(+), 8 deletions(-) > > diff --git a/lib/bitmap.c b/lib/bitmap.c > index 98872e9025da..79ed5538617b 100644 > --- a/lib/bitmap.c > +++ b/lib/bitmap.c > @@ -632,19 +632,22 @@ EXPORT_SYMBOL(bitmap_parselist); > * @nmaskbits: size of bitmap, in bits. > * > * Wrapper for bitmap_parselist(), 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_parselist_user(const char __user *ubuf, > unsigned int ulen, unsigned long *maskp, > int nmaskbits) > { > - if (!access_ok(ubuf, ulen)) > - return -EFAULT; > - return __bitmap_parselist((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_parselist(buf, maskp, nmaskbits); > + > + kfree(buf); > + return ret; > } > EXPORT_SYMBOL(bitmap_parselist_user); > > -- > 2.17.1 > -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 2/5] lib: rework bitmap_parselist 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov 2019-04-05 17:32 ` [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() Yury Norov @ 2019-04-05 17:32 ` Yury Norov 2019-04-08 9:55 ` Andy Shevchenko 2019-04-05 17:32 ` [PATCH 3/5] lib/test_bitmap: switch test_bitmap_parselist to ktime_get() Yury Norov ` (2 subsequent siblings) 4 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel Remove __bitmap_parselist helper and split the function to logical parts. Signed-off-by: Yury Norov <ynorov@marvell.com> --- lib/bitmap.c | 258 +++++++++++++++++++++++++++++---------------------- 1 file changed, 145 insertions(+), 113 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 79ed5538617b..28e17b71f72f 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -477,12 +477,133 @@ 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 group_len end + */ +struct region { + unsigned int start; + unsigned int off; + unsigned int group_len; + 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->group_len) + 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->group_len == 0 || r->off > r->group_len) + return -EINVAL; + + return 0; +} + +static const char *bitmap_getnum(const char *str, unsigned int *num) +{ + unsigned int n = 0, _num = 0; + + if (!isdigit(*str)) + return ERR_PTR(-EINVAL); + + for (; isdigit(*str); str++) { + _num = _num * 10 + (*str - '0'); + if (_num < n) + return ERR_PTR(-EOVERFLOW); + + n = _num; + } + + *num = _num; + + return str; +} + +static inline bool end_of_str(char c) +{ + return c == '\0' || c == '\n'; +} + +static inline bool __end_of_region(char c) +{ + return isspace(c) || c == ','; +} + +static inline bool end_of_region(char c) +{ + return __end_of_region(c) || end_of_str(c); +} + +/* + * The format allows commas and whitespases at the beginning + * of the region. + */ +static const char *bitmap_find_region(const char *str) +{ + while (__end_of_region(*str)) + str++; + + return end_of_str(*str) ? NULL : str; +} + +static const char *bitmap_parse_region(const char *str, struct region *r) +{ + str = bitmap_getnum(str, &r->start); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_end; + + if (*str != '-') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->end); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_pattern; + + if (*str != ':') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->off); + if (IS_ERR(str)) + return str; + + if (*str != '/') + return ERR_PTR(-EINVAL); + + return bitmap_getnum(str + 1, &r->group_len); + +no_end: + r->end = r->start; +no_pattern: + r->off = r->end + 1; + r->group_len = r->end + 1; + + return end_of_str(*str) ? NULL : str; +} + /** - * __bitmap_parselist - convert list format ASCII string to bitmap - * @buf: read nul-terminated user string from this buffer - * @buflen: buffer size in bytes. If string is smaller than this - * then it must be terminated with a \0. - * @is_user: location of buffer, 0 indicates kernel space + * bitmap_parselist - convert list format ASCII string to bitmap + * @buf: read user string from this buffer; must be terminated + * with a \0 or \n. * @maskp: write resulting mask here * @nmaskbits: number of bits in mask to be written * @@ -498,127 +619,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); * * 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, - int is_user, unsigned long *maskp, - int nmaskbits) +int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits) { - unsigned int a, b, old_a, old_b; - unsigned int group_size, used_size, off; - int c, old_c, totaldigits, ndigits; - const char __user __force *ubuf = (const char __user __force *)buf; - int at_start, in_range, in_partial_range; + 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; - } + while (buf) { + buf = bitmap_find_region(buf); + if (buf == NULL) + return 0; - if (c == ':') { - old_a = a; - old_b = b; - at_start = 1; - in_range = 0; - in_partial_range = 1; - a = b = 0; - continue; - } + buf = bitmap_parse_region(buf, &r); + if (IS_ERR(buf)) + return PTR_ERR(buf); - if (c == '-') { - if (at_start || in_range) - return -EINVAL; - b = 0; - in_range = 1; - at_start = 1; - continue; - } + ret = bitmap_check_region(&r); + if (ret) + return ret; - if (!isdigit(c)) - return -EINVAL; + ret = bitmap_set_region(&r, maskp, nmaskbits); + if (ret) + return ret; + } - 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; - 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; - } - } while (buflen && c == ','); return 0; } - -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); -} EXPORT_SYMBOL(bitmap_parselist); -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/5] lib: rework bitmap_parselist 2019-04-05 17:32 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov @ 2019-04-08 9:55 ` Andy Shevchenko 0 siblings, 0 replies; 14+ messages in thread From: Andy Shevchenko @ 2019-04-08 9:55 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Yury Norov, linux-kernel On Fri, Apr 05, 2019 at 08:32:08PM +0300, Yury Norov wrote: > Remove __bitmap_parselist helper and split the function to logical > parts. > +static const char *bitmap_getnum(const char *str, unsigned int *num) > +{ > + unsigned int n = 0, _num = 0; > + > + if (!isdigit(*str)) > + return ERR_PTR(-EINVAL); > + > + for (; isdigit(*str); str++) { > + _num = _num * 10 + (*str - '0'); > + if (_num < n) > + return ERR_PTR(-EOVERFLOW); > + > + n = _num; > + } > + > + *num = _num; > + > + return str; > +} This looks like (semi) open coded simple_strtoull() unsigned long long _num; char *endp; _num = simple_strtoull(str, &endp, 10); if (endp == str) return ERR_PTR(-EINVAL); if (_num > UINT_MAX || (endp - str) > 10) return ERR_PTR(-EOVERFLOW); *num = _num; return endp; > +static inline bool end_of_str(char c) > +{ > + return c == '\0' || c == '\n'; > +} This reminds me a check at the end of _kstrtoull(). Can we use same approach in both cases? -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 3/5] lib/test_bitmap: switch test_bitmap_parselist to ktime_get() 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov 2019-04-05 17:32 ` [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() Yury Norov 2019-04-05 17:32 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov @ 2019-04-05 17:32 ` Yury Norov 2019-04-05 17:32 ` [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist Yury Norov 2019-04-05 17:32 ` [PATCH 5/5] lib/test_bitmap: add tests for bitmap_parselist_user Yury Norov 4 siblings, 0 replies; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel test_bitmap_parselist currently uses get_cycles which is not implemented on some platforms, so use ktime_get() instead. Signed-off-by: Yury Norov <ynorov@marvell.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> --- lib/test_bitmap.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 6cd7d0740005..b06e0fd3811b 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -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); } } -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov ` (2 preceding siblings ...) 2019-04-05 17:32 ` [PATCH 3/5] lib/test_bitmap: switch test_bitmap_parselist to ktime_get() Yury Norov @ 2019-04-05 17:32 ` Yury Norov 2019-04-11 18:39 ` Guenter Roeck 2019-04-05 17:32 ` [PATCH 5/5] lib/test_bitmap: add tests for bitmap_parselist_user Yury Norov 4 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel Add tests for non-number character, empty regions, integer overflow. Signed-off-by: Yury Norov <ynorov@marvell.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> --- lib/test_bitmap.c | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index b06e0fd3811b..709424a788ee 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -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) -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist 2019-04-05 17:32 ` [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist Yury Norov @ 2019-04-11 18:39 ` Guenter Roeck 2019-04-12 8:40 ` Andy Shevchenko 0 siblings, 1 reply; 14+ messages in thread From: Guenter Roeck @ 2019-04-11 18:39 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Yury Norov, linux-kernel On Fri, Apr 05, 2019 at 08:32:10PM +0300, Yury Norov wrote: > Add tests for non-number character, empty regions, integer overflow. > > Signed-off-by: Yury Norov <ynorov@marvell.com> > Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > --- > lib/test_bitmap.c | 18 +++++++++++++++++- > 1 file changed, 17 insertions(+), 1 deletion(-) > > diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c > index b06e0fd3811b..709424a788ee 100644 > --- a/lib/test_bitmap.c > +++ b/lib/test_bitmap.c > @@ -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}, > + This results in error messages such as test_bitmap: parselist: 17: input is ,, ,, , , ,, result is 0x0, expected 0x11111111 test_bitmap: parselist: 18: input is , ,, , , , result is 0x0, expected 0x11111111 on 32-bit systems. The above should be "&exp[12 * step]". Guenter > {-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) ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist 2019-04-11 18:39 ` Guenter Roeck @ 2019-04-12 8:40 ` Andy Shevchenko 0 siblings, 0 replies; 14+ messages in thread From: Andy Shevchenko @ 2019-04-12 8:40 UTC (permalink / raw) To: Guenter Roeck Cc: Yury Norov, Andrew Morton, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Yury Norov, linux-kernel On Thu, Apr 11, 2019 at 11:39:46AM -0700, Guenter Roeck wrote: > On Fri, Apr 05, 2019 at 08:32:10PM +0300, Yury Norov wrote: > > Add tests for non-number character, empty regions, integer overflow. > > {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}, > > + > > This results in error messages such as > > test_bitmap: parselist: 17: input is ,, ,, , , ,, result is 0x0, expected 0x11111111 > test_bitmap: parselist: 18: input is , ,, , , , result is 0x0, expected 0x11111111 > > on 32-bit systems. The above should be "&exp[12 * step]". Nice catch! -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 5/5] lib/test_bitmap: add tests for bitmap_parselist_user 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov ` (3 preceding siblings ...) 2019-04-05 17:32 ` [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist Yury Norov @ 2019-04-05 17:32 ` Yury Norov 4 siblings, 0 replies; 14+ messages in thread From: Yury Norov @ 2019-04-05 17:32 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel Propagate existing bitmap_parselist() tests to bitmap_parselist_user(). Signed-off-by: Yury Norov <ynorov@marvell.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> --- lib/test_bitmap.c | 46 ++++++++++++++++++++++++++++++++++++---------- 1 file changed, 36 insertions(+), 10 deletions(-) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 709424a788ee..d4ecac0da160 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -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) -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH v5 0/5] lib: rework bitmap_parselist and tests @ 2019-04-16 6:37 Yury Norov 2019-04-16 6:37 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov 0 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-16 6:37 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Guenter Roeck Cc: Yury Norov, Yury Norov, linux-kernel 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. Things are more complicated because bitmap_parselist() is a part of user interface, and its behavior should not change. In this patchset - bitmap_parselist_user() made a wrapper on bitmap_parselist(); - bitmap_parselist() reworked (patch 2); - time measurement in test_bitmap_parselist switched to ktime_get (patch 3); - new tests introduced (patch 4), and - bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 5). v1: https://lkml.org/lkml/2018/12/23/50 v2: https://www.spinics.net/lists/kernel/msg3048976.html v3: https://lkml.org/lkml/2019/4/3/68 v4: https://lkml.org/lkml/2019/4/5/640 v5: - fix sadly missed '* step' in patch 4, as spotted by Guenter Roeck; - use _parse_integer() in bitmap_getnum() to avoid opencoding mentioned by Andy Shevchenko. Yury Norov (5): lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() lib: rework bitmap_parselist 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 | 274 ++++++++++++++++++++++++++-------------------- lib/test_bitmap.c | 67 +++++++++--- 2 files changed, 207 insertions(+), 134 deletions(-) -- 2.17.1 ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 2/5] lib: rework bitmap_parselist 2019-04-16 6:37 [PATCH v5 0/5] lib: rework bitmap_parselist and tests Yury Norov @ 2019-04-16 6:37 ` Yury Norov 2019-04-16 13:18 ` Andy Shevchenko 0 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-16 6:37 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Guenter Roeck Cc: Yury Norov, Yury Norov, linux-kernel From: Yury Norov <ynorov@marvell.com> Remove __bitmap_parselist helper and split the function to logical parts. Signed-off-by: Yury Norov <ynorov@marvell.com> --- lib/bitmap.c | 255 ++++++++++++++++++++++++++++----------------------- 1 file changed, 142 insertions(+), 113 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index c63ddd06a5da..f235434df87b 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -20,6 +20,8 @@ #include <asm/page.h> +#include "kstrtox.h" + /** * DOC: bitmap introduction * @@ -477,12 +479,128 @@ 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 group_len end + */ +struct region { + unsigned int start; + unsigned int off; + unsigned int group_len; + 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->group_len) + 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->group_len == 0 || r->off > r->group_len) + return -EINVAL; + + return 0; +} + +static const char *bitmap_getnum(const char *str, unsigned int *num) +{ + unsigned long long n; + unsigned int len; + + len = _parse_integer(str, 10, &n); + if (!len) + return ERR_PTR(-EINVAL); + if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n) + return ERR_PTR(-EOVERFLOW); + + *num = n; + return str + len; +} + +static inline bool end_of_str(char c) +{ + return c == '\0' || c == '\n'; +} + +static inline bool __end_of_region(char c) +{ + return isspace(c) || c == ','; +} + +static inline bool end_of_region(char c) +{ + return __end_of_region(c) || end_of_str(c); +} + +/* + * The format allows commas and whitespases at the beginning + * of the region. + */ +static const char *bitmap_find_region(const char *str) +{ + while (__end_of_region(*str)) + str++; + + return end_of_str(*str) ? NULL : str; +} + +static const char *bitmap_parse_region(const char *str, struct region *r) +{ + str = bitmap_getnum(str, &r->start); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_end; + + if (*str != '-') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->end); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_pattern; + + if (*str != ':') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->off); + if (IS_ERR(str)) + return str; + + if (*str != '/') + return ERR_PTR(-EINVAL); + + return bitmap_getnum(str + 1, &r->group_len); + +no_end: + r->end = r->start; +no_pattern: + r->off = r->end + 1; + r->group_len = r->end + 1; + + return end_of_str(*str) ? NULL : str; +} + /** - * __bitmap_parselist - convert list format ASCII string to bitmap - * @buf: read nul-terminated user string from this buffer - * @buflen: buffer size in bytes. If string is smaller than this - * then it must be terminated with a \0. - * @is_user: location of buffer, 0 indicates kernel space + * bitmap_parselist - convert list format ASCII string to bitmap + * @buf: read user string from this buffer; must be terminated + * with a \0 or \n. * @maskp: write resulting mask here * @nmaskbits: number of bits in mask to be written * @@ -498,127 +616,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); * * 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, - int is_user, unsigned long *maskp, - int nmaskbits) +int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits) { - unsigned int a, b, old_a, old_b; - unsigned int group_size, used_size, off; - int c, old_c, totaldigits, ndigits; - const char __user __force *ubuf = (const char __user __force *)buf; - int at_start, in_range, in_partial_range; + 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; - } + while (buf) { + buf = bitmap_find_region(buf); + if (buf == NULL) + return 0; - if (c == ':') { - old_a = a; - old_b = b; - at_start = 1; - in_range = 0; - in_partial_range = 1; - a = b = 0; - continue; - } + buf = bitmap_parse_region(buf, &r); + if (IS_ERR(buf)) + return PTR_ERR(buf); - if (c == '-') { - if (at_start || in_range) - return -EINVAL; - b = 0; - in_range = 1; - at_start = 1; - continue; - } + ret = bitmap_check_region(&r); + if (ret) + return ret; - if (!isdigit(c)) - return -EINVAL; + ret = bitmap_set_region(&r, maskp, nmaskbits); + if (ret) + return ret; + } - 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; - 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; - } - } while (buflen && c == ','); return 0; } - -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); -} EXPORT_SYMBOL(bitmap_parselist); -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/5] lib: rework bitmap_parselist 2019-04-16 6:37 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov @ 2019-04-16 13:18 ` Andy Shevchenko 0 siblings, 0 replies; 14+ messages in thread From: Andy Shevchenko @ 2019-04-16 13:18 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Guenter Roeck, Yury Norov, linux-kernel On Mon, Apr 15, 2019 at 11:37:58PM -0700, Yury Norov wrote: > From: Yury Norov <ynorov@marvell.com> > > Remove __bitmap_parselist helper and split the function to logical > parts. > One comment below. Overall looks good to me, thanks! Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > Signed-off-by: Yury Norov <ynorov@marvell.com> > --- > lib/bitmap.c | 255 ++++++++++++++++++++++++++++----------------------- > 1 file changed, 142 insertions(+), 113 deletions(-) > > diff --git a/lib/bitmap.c b/lib/bitmap.c > index c63ddd06a5da..f235434df87b 100644 > --- a/lib/bitmap.c > +++ b/lib/bitmap.c > @@ -20,6 +20,8 @@ > > #include <asm/page.h> > > +#include "kstrtox.h" > + > /** > * DOC: bitmap introduction > * > @@ -477,12 +479,128 @@ 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 group_len end > + */ > +struct region { > + unsigned int start; > + unsigned int off; > + unsigned int group_len; > + 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->group_len) > + 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->group_len == 0 || r->off > r->group_len) > + return -EINVAL; > + > + return 0; > +} > + > +static const char *bitmap_getnum(const char *str, unsigned int *num) > +{ > + unsigned long long n; > + unsigned int len; > + > + len = _parse_integer(str, 10, &n); I think we are good here, since it's only for use inside lib itself. > + if (!len) > + return ERR_PTR(-EINVAL); > + if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n) Second part is simple to compare to UINT_MAX: "n > UINT_MAX", or "upper_32_bits(n)" would work as well. Among all I would rather go to comparison with limits, i.e. UINT_MAX. > + return ERR_PTR(-EOVERFLOW); > + > + *num = n; > + return str + len; > +} > + > +static inline bool end_of_str(char c) > +{ > + return c == '\0' || c == '\n'; > +} > + > +static inline bool __end_of_region(char c) > +{ > + return isspace(c) || c == ','; > +} > + > +static inline bool end_of_region(char c) > +{ > + return __end_of_region(c) || end_of_str(c); > +} > + > +/* > + * The format allows commas and whitespases at the beginning > + * of the region. > + */ > +static const char *bitmap_find_region(const char *str) > +{ > + while (__end_of_region(*str)) > + str++; > + > + return end_of_str(*str) ? NULL : str; > +} > + > +static const char *bitmap_parse_region(const char *str, struct region *r) > +{ > + str = bitmap_getnum(str, &r->start); > + if (IS_ERR(str)) > + return str; > + > + if (end_of_region(*str)) > + goto no_end; > + > + if (*str != '-') > + return ERR_PTR(-EINVAL); > + > + str = bitmap_getnum(str + 1, &r->end); > + if (IS_ERR(str)) > + return str; > + > + if (end_of_region(*str)) > + goto no_pattern; > + > + if (*str != ':') > + return ERR_PTR(-EINVAL); > + > + str = bitmap_getnum(str + 1, &r->off); > + if (IS_ERR(str)) > + return str; > + > + if (*str != '/') > + return ERR_PTR(-EINVAL); > + > + return bitmap_getnum(str + 1, &r->group_len); > + > +no_end: > + r->end = r->start; > +no_pattern: > + r->off = r->end + 1; > + r->group_len = r->end + 1; > + > + return end_of_str(*str) ? NULL : str; > +} > + > /** > - * __bitmap_parselist - convert list format ASCII string to bitmap > - * @buf: read nul-terminated user string from this buffer > - * @buflen: buffer size in bytes. If string is smaller than this > - * then it must be terminated with a \0. > - * @is_user: location of buffer, 0 indicates kernel space > + * bitmap_parselist - convert list format ASCII string to bitmap > + * @buf: read user string from this buffer; must be terminated > + * with a \0 or \n. > * @maskp: write resulting mask here > * @nmaskbits: number of bits in mask to be written > * > @@ -498,127 +616,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); > * > * 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, > - int is_user, unsigned long *maskp, > - int nmaskbits) > +int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits) > { > - unsigned int a, b, old_a, old_b; > - unsigned int group_size, used_size, off; > - int c, old_c, totaldigits, ndigits; > - const char __user __force *ubuf = (const char __user __force *)buf; > - int at_start, in_range, in_partial_range; > + 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; > - } > + while (buf) { > + buf = bitmap_find_region(buf); > + if (buf == NULL) > + return 0; > > - if (c == ':') { > - old_a = a; > - old_b = b; > - at_start = 1; > - in_range = 0; > - in_partial_range = 1; > - a = b = 0; > - continue; > - } > + buf = bitmap_parse_region(buf, &r); > + if (IS_ERR(buf)) > + return PTR_ERR(buf); > > - if (c == '-') { > - if (at_start || in_range) > - return -EINVAL; > - b = 0; > - in_range = 1; > - at_start = 1; > - continue; > - } > + ret = bitmap_check_region(&r); > + if (ret) > + return ret; > > - if (!isdigit(c)) > - return -EINVAL; > + ret = bitmap_set_region(&r, maskp, nmaskbits); > + if (ret) > + return ret; > + } > > - 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; > - 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; > - } > - } while (buflen && c == ','); > return 0; > } > - > -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); > -} > EXPORT_SYMBOL(bitmap_parselist); > > > -- > 2.17.1 > -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH v3 0/5] lib: rework bitmap_parselist and tests @ 2019-04-03 4:45 Yury Norov 2019-04-03 4:45 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov 0 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-03 4:45 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel 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. Things are more complicated because bitmap_parselist() is a part of user interface, and its behavior should not change. In this patchset - bitmap_parselist_user() made a wrapper on bitmap_parselist(); - bitmap_parselist() reworked (patch 2); - time measurement in test_bitmap_parselist switched to ktime_get (patch 3); - new tests introduced (patch 4), and - bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 5). v1: https://lkml.org/lkml/2018/12/23/50 v2: https://www.spinics.net/lists/kernel/msg3048976.html v3: Implementation of an approach with copying the data to kernel space in bitmap_parselist_user() instead of parsing user data byte by byte. For me, it looks better than v2. Yury Norov (5): lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() lib: rework bitmap_parselist 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 | 285 ++++++++++++++++++++++++++-------------------- lib/test_bitmap.c | 67 ++++++++--- 2 files changed, 218 insertions(+), 134 deletions(-) -- 2.17.1 ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 2/5] lib: rework bitmap_parselist 2019-04-03 4:45 [PATCH v3 0/5] lib: rework bitmap_parselist and tests Yury Norov @ 2019-04-03 4:45 ` Yury Norov 2019-04-03 11:22 ` Andy Shevchenko 0 siblings, 1 reply; 14+ messages in thread From: Yury Norov @ 2019-04-03 4:45 UTC (permalink / raw) To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis Cc: Yury Norov, Yury Norov, linux-kernel Remove __bitmap_parselist helper and split the function to logical parts. Signed-off-by: Yury Norov <ynorov@marvell.com> --- lib/bitmap.c | 258 +++++++++++++++++++++++++++++---------------------- 1 file changed, 145 insertions(+), 113 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index ce9ea804d06d..0c08f18aed88 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -477,12 +477,133 @@ 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 group_len end + */ +struct region { + unsigned int start; + unsigned int off; + unsigned int group_len; + 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->group_len) + 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->group_len == 0 || r->off > r->group_len) + return -EINVAL; + + return 0; +} + +static const char *bitmap_getnum(const char *str, unsigned int *num) +{ + unsigned int n = 0, _num = 0; + + if (!isdigit(*str)) + return ERR_PTR(-EINVAL); + + for (; isdigit(*str); str++) { + _num = _num * 10 + (*str - '0'); + if (_num < n) + return ERR_PTR(-EOVERFLOW); + + n = _num; + } + + *num = _num; + + return str; +} + +static inline bool end_of_str(char c) +{ + return c == '\0' || c == '\n'; +} + +static inline bool __end_of_region(char c) +{ + return isspace(c) || c == ','; +} + +static inline bool end_of_region(char c) +{ + return __end_of_region(c) || end_of_str(c); +} + +/* + * The format allows commas and whitespases at the beginning + * of the region. + */ +static const char *bitmap_find_region(const char *str) +{ + while (__end_of_region(*str)) + str++; + + return end_of_str(*str) ? NULL : str; +} + +static const char *bitmap_parse_region(const char *str, struct region *r) +{ + str = bitmap_getnum(str, &r->start); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_end; + + if (*str != '-') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->end); + if (IS_ERR(str)) + return str; + + if (end_of_region(*str)) + goto no_pattern; + + if (*str != ':') + return ERR_PTR(-EINVAL); + + str = bitmap_getnum(str + 1, &r->off); + if (IS_ERR(str)) + return str; + + if (*str != '/') + return ERR_PTR(-EINVAL); + + return bitmap_getnum(str + 1, &r->group_len); + +no_end: + r->end = r->start; +no_pattern: + r->off = r->end + 1; + r->group_len = r->end + 1; + + return end_of_str(*str) ? NULL : str; +} + /** - * __bitmap_parselist - convert list format ASCII string to bitmap - * @buf: read nul-terminated user string from this buffer - * @buflen: buffer size in bytes. If string is smaller than this - * then it must be terminated with a \0. - * @is_user: location of buffer, 0 indicates kernel space + * bitmap_parselist - convert list format ASCII string to bitmap + * @buf: read user string from this buffer; must be terminated + * with a \0 or \n. * @maskp: write resulting mask here * @nmaskbits: number of bits in mask to be written * @@ -498,127 +619,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); * * 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, - int is_user, unsigned long *maskp, - int nmaskbits) +int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits) { - unsigned int a, b, old_a, old_b; - unsigned int group_size, used_size, off; - int c, old_c, totaldigits, ndigits; - const char __user __force *ubuf = (const char __user __force *)buf; - int at_start, in_range, in_partial_range; + 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; - } + while (buf) { + buf = bitmap_find_region(buf); + if (buf == NULL) + return 0; - if (c == ':') { - old_a = a; - old_b = b; - at_start = 1; - in_range = 0; - in_partial_range = 1; - a = b = 0; - continue; - } + buf = bitmap_parse_region(buf, &r); + if (IS_ERR(buf)) + return PTR_ERR(buf); - if (c == '-') { - if (at_start || in_range) - return -EINVAL; - b = 0; - in_range = 1; - at_start = 1; - continue; - } + ret = bitmap_check_region(&r); + if (ret) + return ret; - if (!isdigit(c)) - return -EINVAL; + ret = bitmap_set_region(&r, maskp, nmaskbits); + if (ret) + return ret; + } - 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; - 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; - } - } while (buflen && c == ','); return 0; } - -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); -} EXPORT_SYMBOL(bitmap_parselist); -- 2.17.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/5] lib: rework bitmap_parselist 2019-04-03 4:45 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov @ 2019-04-03 11:22 ` Andy Shevchenko 0 siblings, 0 replies; 14+ messages in thread From: Andy Shevchenko @ 2019-04-03 11:22 UTC (permalink / raw) To: Yury Norov Cc: Andrew Morton, Rasmus Villemoes, Arnd Bergmann, Kees Cook, Matthew Wilcox, Tetsuo Handa, Mike Travis, Yury Norov, linux-kernel On Wed, Apr 03, 2019 at 07:45:37AM +0300, Yury Norov wrote: > Remove __bitmap_parselist helper and split the function to logical > parts. > /** > - * __bitmap_parselist - convert list format ASCII string to bitmap > - * @buf: read nul-terminated user string from this buffer > - * @buflen: buffer size in bytes. If string is smaller than this > - * then it must be terminated with a \0. > - * @is_user: location of buffer, 0 indicates kernel space > + * bitmap_parselist - convert list format ASCII string to bitmap > + * @buf: read user string from this buffer; must be terminated > + * with a \0 or \n. It's still good idea to put line continuation with deeper level of indentation. > * @maskp: write resulting mask here > * @nmaskbits: number of bits in mask to be written > * > @@ -498,127 +619,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf); > * > * 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 > */ -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2019-04-16 13:18 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-04-05 17:32 [PATCH v4 0/5] lib: rework bitmap_parselist and tests Yury Norov 2019-04-05 17:32 ` [PATCH 1/5] lib: make bitmap_parselist_user() a wrapper on bitmap_parselist() Yury Norov 2019-04-08 9:30 ` Andy Shevchenko 2019-04-05 17:32 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov 2019-04-08 9:55 ` Andy Shevchenko 2019-04-05 17:32 ` [PATCH 3/5] lib/test_bitmap: switch test_bitmap_parselist to ktime_get() Yury Norov 2019-04-05 17:32 ` [PATCH 4/5] lib/test_bitmap: add testcases for bitmap_parselist Yury Norov 2019-04-11 18:39 ` Guenter Roeck 2019-04-12 8:40 ` Andy Shevchenko 2019-04-05 17:32 ` [PATCH 5/5] lib/test_bitmap: add tests for bitmap_parselist_user Yury Norov -- strict thread matches above, loose matches on Subject: below -- 2019-04-16 6:37 [PATCH v5 0/5] lib: rework bitmap_parselist and tests Yury Norov 2019-04-16 6:37 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov 2019-04-16 13:18 ` Andy Shevchenko 2019-04-03 4:45 [PATCH v3 0/5] lib: rework bitmap_parselist and tests Yury Norov 2019-04-03 4:45 ` [PATCH 2/5] lib: rework bitmap_parselist Yury Norov 2019-04-03 11:22 ` Andy Shevchenko
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).