Re: [PATCH 5/7] lib: rework bitmap_parse()
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
[PATCH 5/7] 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.
Signed-off-by: Yury Norov
---
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 CHUNKSZ32
-#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'.
-
Re: [PATCH 5/7] lib: rework bitmap_parse()
On Sun, Jul 21, 2019 at 02:27:51PM -0700, Yury Norov wrote:
> From Yury Norov
>
> 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
> Signed-off-by: Yury Norov
I'm not sure this is good to have two SoB tags for one person.
> + if (hex_to_bin(*end) < 0)
Isn't it simple isxdigit() check?
> + 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;
Dunno if it's for this series, but perhaps we would like to have something like
/* Convert hex representation of u32 value to binary format */
static inline int hex2bin32(const char *buf, u32 *result)
{
u8 value[4];
int ret;
ret = hex2bin(value, buf, sizeof(u32));
if (ret)
return ret;
*result = get_unaligned((u32 *)value);
// I guess it's aligned and thus can be done with:
// *result = be32_to_cpup((__force __be32 *)value);
// just don't like enforcing bitwise types
return 0;
}
// also can be your variant with for-loop.
At least here for now and then can be moved to the kernel.h / hexdump.c.
> +
> + if (start > end || __end_of_region(*end))
> + goto out;
> + }
> +
> + if (hex_to_bin(*end) >= 0)
Isn't it simple isxdigit() check?
> + return ERR_PTR(-EOVERFLOW);
--
With Best Regards,
Andy Shevchenko
[PATCH 5/7] lib: rework bitmap_parse()
>From Yury Norov
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
Signed-off-by: Yury Norov
---
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 f58e97446abcf..c3e84864cc335 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -172,7 +172,7 @@ bitmap_find_next_zero_area(unsigned long *map,
align_mask, 0);
}
-extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
+extern int bitmap_parse(const char *buf, unsigned int buflen,
unsigned long *dst, int nbits);
extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
unsigned long *dst, int nbits);
@@ -408,12 +408,6 @@ static inline void bitmap_shift_left(unsigned long *dst,
const unsigned long *sr
__bitmap_shift_left(dst, src, shift, nbits);
}
-static inline int bitmap_parse(const char *buf, unsigned int buflen,
- unsigned long *maskp, int nmaskbits)
-{
- return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
-}
-
/**
* BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
* @n: u64 value
diff --git a/lib/bitmap.c b/lib/bitmap.c
index fbd4121c540b8..8fc918e74116d 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -333,97 +333,6 @@ EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
* second version by Paul Jackson, third by Joe Korty.
*/
-#define CHUNKSZ32
-#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
Re: [PATCH 5/7] lib: rework bitmap_parse()
On Thu, 9 May 2019 19:26:33 -0700 Yury Norov wrote:
> Hi Andy,
>
> Thanks for thorough review.
>
> On Wed, May 08, 2019 at 11:46:32AM +0300, Andy Shevchenko wrote:
> > On Tue, Apr 30, 2019 at 06:06:34PM -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 inline bool in_str(const char *start, const char *ptr)
> > > +{
> > > + return start <= ptr;
> > > +}
> > > +
> >
> > The explicit use of the conditional is better.
> >
> > --
> > With Best Regards,
> > Andy Shevchenko
>
> I still think that is_str() is more verbose, but it's minor issue
> anyways, so I obey. Below is the patch that removes the function.
> It's up to Andrew finally, either apply it or not.
I agree with Andy - open-coding the comparisons makes it easier to
understand the varoius in_str() callsites, IMO.
> @@ -653,7 +648,7 @@ int bitmap_parse(const char *start, unsigned int buflen,
> u32 *bitmap = (u32 *)maskp;
> int unset_bit;
>
> - while (in_str(start, (end = bitmap_find_region_reverse(start, end {
> + while (start <= (end = bitmap_find_region_reverse(start, end))) {
This statement hurts my little brain. Can it be broken into easier to digest
chunks?
> if (!chunks--)
> return -EOVERFLOW;
>
Re: [PATCH 5/7] lib: rework bitmap_parse()
Hi Andy,
Thanks for thorough review.
On Wed, May 08, 2019 at 11:46:32AM +0300, Andy Shevchenko wrote:
> On Tue, Apr 30, 2019 at 06:06:34PM -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 inline bool in_str(const char *start, const char *ptr)
> > +{
> > + return start <= ptr;
> > +}
> > +
>
> The explicit use of the conditional is better.
>
> --
> With Best Regards,
> Andy Shevchenko
I still think that is_str() is more verbose, but it's minor issue
anyways, so I obey. Below is the patch that removes the function.
It's up to Andrew finally, either apply it or not.
Thanks,
Yury
>From 7438c15a0b165032a3e5a6d87daabe877dc8cbc8 Mon Sep 17 00:00:00 2001
From: Yury Norov
Date: Thu, 9 May 2019 17:54:23 -0700
Subject: [PATCH] lib: opencode in_str()
Signed-off-by: Yury Norov
---
lib/bitmap.c | 11 +++
1 file changed, 3 insertions(+), 8 deletions(-)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index ebcf4700ebed..ecf93d2982a5 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -454,11 +454,6 @@ static inline bool end_of_region(char c)
return __end_of_region(c) || end_of_str(c);
}
-static inline bool in_str(const char *start, const char *ptr)
-{
- return start <= ptr;
-}
-
/*
* The format allows commas and whitespases at the beginning
* of the region.
@@ -473,7 +468,7 @@ static const char *bitmap_find_region(const char *str)
static const char *bitmap_find_region_reverse(const char *start, const char
*end)
{
- while (in_str(start, end) && __end_of_region(*end))
+ while (start <= end && __end_of_region(*end))
end--;
return end;
@@ -618,7 +613,7 @@ static const char *bitmap_get_x32_reverse(const char *start,
ret |= c << i;
- if (!in_str(start, end) || __end_of_region(*end))
+ if (start > end || __end_of_region(*end))
goto out;
}
@@ -653,7 +648,7 @@ int bitmap_parse(const char *start, unsigned int buflen,
u32 *bitmap = (u32 *)maskp;
int unset_bit;
- while (in_str(start, (end = bitmap_find_region_reverse(start, end {
+ while (start <= (end = bitmap_find_region_reverse(start, end))) {
if (!chunks--)
return -EOVERFLOW;
--
2.17.1
Re: [PATCH 5/7] lib: rework bitmap_parse()
On Tue, Apr 30, 2019 at 06:06:34PM -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 inline bool in_str(const char *start, const char *ptr)
> +{
> + return start <= ptr;
> +}
> +
The explicit use of the conditional is better.
--
With Best Regards,
Andy Shevchenko
[PATCH 5/7] 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.
Signed-off-by: Yury Norov
---
include/linux/bitmap.h | 8 +-
lib/bitmap.c | 179 -
2 files changed, 88 insertions(+), 99 deletions(-)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index f58e97446abc..c3e84864cc33 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -172,7 +172,7 @@ bitmap_find_next_zero_area(unsigned long *map,
align_mask, 0);
}
-extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
+extern int bitmap_parse(const char *buf, unsigned int buflen,
unsigned long *dst, int nbits);
extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
unsigned long *dst, int nbits);
@@ -408,12 +408,6 @@ static inline void bitmap_shift_left(unsigned long *dst,
const unsigned long *sr
__bitmap_shift_left(dst, src, shift, nbits);
}
-static inline int bitmap_parse(const char *buf, unsigned int buflen,
- unsigned long *maskp, int nmaskbits)
-{
- return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
-}
-
/**
* BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
* @n: u64 value
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 300732031fad..ebcf4700ebed 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -335,97 +335,6 @@ EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
* second version by Paul Jackson, third by Joe Korty.
*/
-#define CHUNKSZ32
-#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'.
-
