* [PATCH 1/7] lib/string: add strnchrnul()
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 3:30 ` [PATCH 2/7] bitops: more BITS_TO_* macros Yury Norov
` (5 subsequent siblings)
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
New function works like strchrnul() with a length limited strings.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/string.h | 1 +
lib/string.c | 17 +++++++++++++++++
2 files changed, 18 insertions(+)
diff --git a/include/linux/string.h b/include/linux/string.h
index 3cf684db4bc6b..cf8f47efeb051 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -107,6 +107,7 @@ extern char * strchr(const char *,int);
#ifndef __HAVE_ARCH_STRCHRNUL
extern char * strchrnul(const char *,int);
#endif
+extern char * strnchrnul(const char *, size_t, int);
#ifndef __HAVE_ARCH_STRNCHR
extern char * strnchr(const char *, size_t, int);
#endif
diff --git a/lib/string.c b/lib/string.c
index cd7a10c192109..75b10363e61f0 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -434,6 +434,23 @@ char *strchrnul(const char *s, int c)
EXPORT_SYMBOL(strchrnul);
#endif
+/**
+ * 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 the first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the last character of the string.
+ */
+char *strnchrnul(const char *s, size_t count, int c)
+{
+ while (count-- && *s && *s != (char)c)
+ s++;
+ return (char *)s;
+}
+
#ifndef __HAVE_ARCH_STRRCHR
/**
* strrchr - Find the last occurrence of a character in a string
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 2/7] bitops: more BITS_TO_* macros
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
2019-09-09 3:30 ` [PATCH 1/7] lib/string: add strnchrnul() Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 3:30 ` [PATCH 3/7] lib: add test for bitmap_parse() Yury Norov
` (4 subsequent siblings)
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
Introduce BITS_TO_U64, BITS_TO_U32 and BITS_TO_BYTES as they are handy
in the following patches (BITS_TO_U32 specifically). Reimplement tools/
version of the macros according to the kernel implementation.
Also fix indentation for BITS_PER_TYPE definition.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/bitops.h | 5 ++++-
tools/include/linux/bitops.h | 9 +++++----
2 files changed, 9 insertions(+), 5 deletions(-)
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index cf074bce3eb32..e61c4e6142641 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -4,8 +4,11 @@
#include <asm/types.h>
#include <linux/bits.h>
-#define BITS_PER_TYPE(type) (sizeof(type) * 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);
diff --git a/tools/include/linux/bitops.h b/tools/include/linux/bitops.h
index 140c8362f1139..5fca38fe1ba83 100644
--- a/tools/include/linux/bitops.h
+++ b/tools/include/linux/bitops.h
@@ -14,10 +14,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);
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 3/7] lib: add test for bitmap_parse()
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
2019-09-09 3:30 ` [PATCH 1/7] lib/string: add strnchrnul() Yury Norov
2019-09-09 3:30 ` [PATCH 2/7] bitops: more BITS_TO_* macros Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 3:30 ` [PATCH 4/7] lib: make bitmap_parse_user a wrapper on bitmap_parse Yury Norov
` (3 subsequent siblings)
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
The test is derived from bitmap_parselist()
NO_LEN is reserved for use in following patches.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
lib/test_bitmap.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 93 insertions(+), 1 deletion(-)
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 51a98f7ee79e6..e306d3da12019 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -206,7 +206,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;
@@ -329,6 +330,85 @@ 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, "0", &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,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},
+
+ {-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);
@@ -339,6 +419,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)
@@ -410,6 +500,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();
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 4/7] lib: make bitmap_parse_user a wrapper on bitmap_parse
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
` (2 preceding siblings ...)
2019-09-09 3:30 ` [PATCH 3/7] lib: add test for bitmap_parse() Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 3:30 ` [PATCH 5/7] lib: rework bitmap_parse() Yury Norov
` (2 subsequent siblings)
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
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.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
lib/bitmap.c | 20 ++++++++++----------
1 file changed, 10 insertions(+), 10 deletions(-)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index f9e834841e941..51ee14577166e 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -452,22 +452,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);
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 5/7] lib: rework bitmap_parse()
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
` (3 preceding siblings ...)
2019-09-09 3:30 ` [PATCH 4/7] lib: make bitmap_parse_user a wrapper on bitmap_parse Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 10:06 ` Andy Shevchenko
2019-09-09 3:30 ` [PATCH 6/7] lib: new testcases for bitmap_parse{_user} Yury Norov
2019-09-09 3:30 ` [PATCH 7/7] cpumask: don't calculate length of the input string Yury Norov
6 siblings, 1 reply; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
bitmap_parse() is ineffective and full of opaque variables and opencoded
parts. It leads to hard understanding and usage 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.
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/bitmap.h | 8 +-
lib/bitmap.c | 178 ++++++++++++++++++++---------------------
2 files changed, 87 insertions(+), 99 deletions(-)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 90528f12bdfa6..bad43c4a5eaca 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -176,7 +176,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);
@@ -431,12 +431,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
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 51ee14577166e..008f53714950a 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -353,97 +353,6 @@ EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
* second version by Paul Jackson, third by Joe Korty.
*/
-#define CHUNKSZ 32
-#define nbits_to_hold_value(val) fls(val)
-#define BASEDEC 10 /* fancier cpuset lists input in decimal */
-
-/**
- * __bitmap_parse - convert an ASCII hex string into a bitmap.
- * @buf: pointer to buffer containing string.
- * @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
- * @maskp: pointer to bitmap array that will contain result.
- * @nmaskbits: size of bitmap, in bits.
- *
- * Commas group hex digits into chunks. Each chunk defines exactly 32
- * bits of the resultant bitmask. No chunk may specify a value larger
- * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
- * then leading 0-bits are prepended. %-EINVAL is returned for illegal
- * characters and for grouping errors such as "1,,5", ",44", "," and "".
- * Leading and trailing whitespace accepted, but not embedded whitespace.
- */
-int __bitmap_parse(const char *buf, unsigned int buflen,
- int is_user, unsigned long *maskp,
- int nmaskbits)
-{
- int c, old_c, totaldigits, ndigits, nchunks, nbits;
- u32 chunk;
- const char __user __force *ubuf = (const char __user __force *)buf;
-
- bitmap_zero(maskp, nmaskbits);
-
- nchunks = nbits = totaldigits = c = 0;
- do {
- chunk = 0;
- ndigits = totaldigits;
-
- /* Get the next chunk of the bitmap */
- while (buflen) {
- old_c = c;
- if (is_user) {
- if (__get_user(c, ubuf++))
- return -EFAULT;
- }
- else
- c = *buf++;
- buflen--;
- if (isspace(c))
- continue;
-
- /*
- * If the last character was a space and the current
- * character isn't '\0', we've got embedded whitespace.
- * This is a no-no, so throw an error.
- */
- if (totaldigits && c && isspace(old_c))
- return -EINVAL;
-
- /* A '\0' or a ',' signal the end of the chunk */
- if (c == '\0' || c == ',')
- break;
-
- if (!isxdigit(c))
- return -EINVAL;
-
- /*
- * Make sure there are at least 4 free bits in 'chunk'.
- * If not, this hexdigit will overflow 'chunk', so
- * throw an error.
- */
- if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
- return -EOVERFLOW;
-
- chunk = (chunk << 4) | hex_to_bin(c);
- totaldigits++;
- }
- if (ndigits == totaldigits)
- return -EINVAL;
- if (nchunks == 0 && chunk == 0)
- continue;
-
- __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
- *maskp |= chunk;
- nchunks++;
- nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
- if (nbits > nmaskbits)
- return -EOVERFLOW;
- } while (buflen && c == ',');
-
- return 0;
-}
-EXPORT_SYMBOL(__bitmap_parse);
-
/**
* bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
*
@@ -464,7 +373,7 @@ int bitmap_parse_user(const char __user *ubuf,
if (IS_ERR(buf))
return PTR_ERR(buf);
- ret = bitmap_parse(buf, ulen, maskp, nmaskbits);
+ ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
kfree(buf);
return ret;
@@ -575,6 +484,14 @@ static const char *bitmap_find_region(const char *str)
return end_of_str(*str) ? NULL : str;
}
+static const char *bitmap_find_region_reverse(const char *start, const char *end)
+{
+ while (start <= end && __end_of_region(*end))
+ end--;
+
+ return end;
+}
+
static const char *bitmap_parse_region(const char *str, struct region *r)
{
str = bitmap_getnum(str, &r->start);
@@ -698,6 +615,83 @@ int bitmap_parselist_user(const char __user *ubuf,
}
EXPORT_SYMBOL(bitmap_parselist_user);
+static const char *bitmap_get_x32_reverse(const char *start,
+ const char *end, u32 *num)
+{
+ u32 ret = 0;
+ int c, i;
+
+ if (!isxdigit(*end))
+ return ERR_PTR(-EINVAL);
+
+ for (i = 0; i < 32; i += 4) {
+ c = hex_to_bin(*end--);
+ if (c < 0)
+ return ERR_PTR(-EINVAL);
+
+ ret |= c << i;
+
+ if (start > end || __end_of_region(*end))
+ goto out;
+ }
+
+ if (isxdigit(*end))
+ return ERR_PTR(-EOVERFLOW);
+out:
+ *num = ret;
+ return end;
+}
+
+/**
+ * bitmap_parse - convert an ASCII hex string into a bitmap.
+ * @start: pointer to buffer containing string.
+ * @buflen: buffer size in bytes. If string is smaller than this
+ * then it must be terminated with a \0 or \n. In that case,
+ * UINT_MAX may be provided instead of string length.
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Commas group hex digits into chunks. Each chunk defines exactly 32
+ * bits of the resultant bitmask. No chunk may specify a value larger
+ * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
+ * then leading 0-bits are prepended. %-EINVAL is returned for illegal
+ * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
+ * Leading, embedded and trailing whitespace accepted.
+ */
+int bitmap_parse(const char *start, unsigned int buflen,
+ unsigned long *maskp, int nmaskbits)
+{
+ const char *end = strnchrnul(start, buflen, '\n') - 1;
+ int chunks = BITS_TO_U32(nmaskbits);
+ u32 *bitmap = (u32 *)maskp;
+ int unset_bit;
+
+ while (1) {
+ end = bitmap_find_region_reverse(start, end);
+ if (start > end)
+ break;
+
+ if (!chunks--)
+ return -EOVERFLOW;
+
+ end = bitmap_get_x32_reverse(start, end, bitmap++);
+ if (IS_ERR(end))
+ return PTR_ERR(end);
+ }
+
+ unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
+ if (unset_bit < nmaskbits) {
+ bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
+ return 0;
+ }
+
+ if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
+ return -EOVERFLOW;
+
+ return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);
+
#ifdef CONFIG_NUMA
/**
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH 5/7] lib: rework bitmap_parse()
2019-09-09 3:30 ` [PATCH 5/7] lib: rework bitmap_parse() Yury Norov
@ 2019-09-09 10:06 ` Andy Shevchenko
0 siblings, 0 replies; 13+ messages in thread
From: Andy Shevchenko @ 2019-09-09 10:06 UTC (permalink / raw)
To: Yury Norov
Cc: Andrew Morton, Rasmus Villemoes, Dmitry Torokhov,
David S . Miller, Stephen Rothwell, Amritha Nambiar,
Willem de Bruijn, Kees Cook, Matthew Wilcox, Tobin C . Harding,
Will Deacon, Miklos Szeredi, Vineet Gupta, Chris Wilson,
Arnaldo Carvalho de Melo, linux-kernel, Jens Axboe,
Steffen Klassert
On Sun, Sep 08, 2019 at 08:30:19PM -0700, Yury Norov wrote:
> bitmap_parse() is ineffective and full of opaque variables and opencoded
> parts. It leads to hard understanding and usage 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.
> +static const char *bitmap_get_x32_reverse(const char *start,
> + const char *end, u32 *num)
> +{
> + u32 ret = 0;
> + int c, i;
> +
> + if (!isxdigit(*end))
> + return ERR_PTR(-EINVAL);
This seems redundant...
> +
> + for (i = 0; i < 32; i += 4) {
> + c = hex_to_bin(*end--);
> + if (c < 0)
> + return ERR_PTR(-EINVAL);
...because this will do the same check.
Am I right?
> +
> + ret |= c << i;
> +
> + if (start > end || __end_of_region(*end))
> + goto out;
> + }
> +
> + if (isxdigit(*end))
> + return ERR_PTR(-EOVERFLOW);
hex_to_bin() doesn't rely on ctype array, won't drain caches.
I guess it's not a fast path, so, either will work.
> +out:
> + *num = ret;
> + return end;
> +}
--
With Best Regards,
Andy Shevchenko
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 6/7] lib: new testcases for bitmap_parse{_user}
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
` (4 preceding siblings ...)
2019-09-09 3:30 ` [PATCH 5/7] lib: rework bitmap_parse() Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
2019-09-09 3:30 ` [PATCH 7/7] cpumask: don't calculate length of the input string Yury Norov
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
New version of bitmap_parse() is unified with bitmap_parse_list(),
and therefore:
- weakens rules on whitespaces and commas between hex chunks;
- in addition to \0 allows using \n as the line ending symbol;
- allows passing UINT_MAX or any other big number as the length
of input string instead of actual string length.
The patch covers the cases.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
lib/test_bitmap.c | 8 ++++++++
1 file changed, 8 insertions(+)
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index e306d3da12019..d9fe7c89e6a94 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -344,14 +344,22 @@ static const unsigned long parse_test2[] __initconst = {
};
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},
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 7/7] cpumask: don't calculate length of the input string
2019-09-09 3:30 [PATCH v4 0/7] lib: rework bitmap_parse Yury Norov
` (5 preceding siblings ...)
2019-09-09 3:30 ` [PATCH 6/7] lib: new testcases for bitmap_parse{_user} Yury Norov
@ 2019-09-09 3:30 ` Yury Norov
6 siblings, 0 replies; 13+ messages in thread
From: Yury Norov @ 2019-09-09 3:30 UTC (permalink / raw)
To: Andrew Morton, Andy Shevchenko, Rasmus Villemoes,
Dmitry Torokhov, David S . Miller, Stephen Rothwell,
Amritha Nambiar, Willem de Bruijn, Kees Cook, Matthew Wilcox,
Tobin C . Harding, Will Deacon, Miklos Szeredi, Vineet Gupta,
Chris Wilson, Arnaldo Carvalho de Melo, linux-kernel
Cc: Yury Norov, Jens Axboe, Steffen Klassert
New design of inner bitmap_parse() allows to avoid
calculating the size of a null-terminated string.
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
include/linux/cpumask.h | 4 +---
1 file changed, 1 insertion(+), 3 deletions(-)
diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 78a73eba64dd6..d5cc88514aee6 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -663,9 +663,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);
}
/**
--
2.20.1
^ permalink raw reply related [flat|nested] 13+ messages in thread