The patch titled
Subject: lib: rework bitmap_parse()
has been added to the -mm tree. Its filename is
lib-rework-bitmap_parse.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/lib-rework-bitmap_parse.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/lib-rework-bitmap_parse.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Yury Norov <ynorov@xxxxxxxxxxx>
Subject: lib: rework bitmap_parse()
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.
[ynorov@xxxxxxxxxxx: opencode in_str()]
Link: http://lkml.kernel.org/r/20190510022633.GA30629@yury-thinkpad
Link: http://lkml.kernel.org/r/20190501010636.30595-6-ynorov@xxxxxxxxxxx
Signed-off-by: Yury Norov <ynorov@xxxxxxxxxxx>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
Cc: Rasmus Villemoes <linux@xxxxxxxxxxxxxxxxxx>
Cc: Amritha Nambiar <amritha.nambiar@xxxxxxxxx>
Cc: Willem de Bruijn <willemb@xxxxxxxxxx>
Cc: Kees Cook <keescook@xxxxxxxxxxxx>
Cc: Matthew Wilcox <willy@xxxxxxxxxxxxx>
Cc: "Tobin C . Harding" <tobin@xxxxxxxxxx>
Cc: Will Deacon <will.deacon@xxxxxxx>
Cc: Steffen Klassert <steffen.klassert@xxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/bitmap.h | 8 -
lib/bitmap.c | 174 ++++++++++++++++++---------------------
2 files changed, 83 insertions(+), 99 deletions(-)
--- a/include/linux/bitmap.h~lib-rework-bitmap_parse
+++ a/include/linux/bitmap.h
@@ -172,7 +172,7 @@ bitmap_find_next_zero_area(unsigned long
align_mask, 0);
}
-extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
+extern int bitmap_parse(const char *buf, unsigned int buflen,
unsigned long *dst, int nbits);
extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
unsigned long *dst, int nbits);
@@ -408,12 +408,6 @@ static inline void bitmap_shift_left(uns
__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
--- a/lib/bitmap.c~lib-rework-bitmap_parse
+++ a/lib/bitmap.c
@@ -335,97 +335,6 @@ EXPORT_SYMBOL(bitmap_find_next_zero_area
* 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
*
@@ -446,7 +355,7 @@ int bitmap_parse_user(const char __user
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;
@@ -557,6 +466,14 @@ static const char *bitmap_find_region(co
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);
@@ -680,6 +597,79 @@ int bitmap_parselist_user(const char __u
}
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 (hex_to_bin(*end) < 0)
+ 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 (hex_to_bin(*end) >= 0)
+ 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 (start <= (end = bitmap_find_region_reverse(start, end))) {
+ 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);
+ return 0;
+ }
+
+ if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
+ return -EOVERFLOW;
+
+ return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);
+
#ifdef CONFIG_NUMA
/**
_
Patches currently in -mm which might be from ynorov@xxxxxxxxxxx are
lib-string-add-strnchrnul.patch
bitops-more-bits_to_-macros.patch
lib-add-test-for-bitmap_parse.patch
lib-make-bitmap_parse_user-a-wrapper-on-bitmap_parse.patch
lib-rework-bitmap_parse.patch
lib-new-testcases-for-bitmap_parse_user.patch
cpumask-dont-calculate-length-of-the-input-string.patch
