lib: rework bitmap_parse
Subsystems (4)
Yury Norov
maintainercover lib: rework bitmap_parse
On top of next-20190418.
Similarly to recently revisited bitmap_parselist() [1], bitmap_parse() is ineffective and overcomplicated. This series reworks it, aligns its interface with bitmap_parselist() and makes usage simpler.
The series also adds a test for the function and fixes usage of it in cpumask_parse() according to new design - drops the calculating of length of an input string.
The following users would also consider to drop the length argument, if possible:drivers/block/drbd/drbd_main.c:2608kernel/padata.c:924net/core/net-sysfs.c:726net/core/net-sysfs.c:1309net/core/net-sysfs.c:1391
bitmap_parse() takes the array of numbers to be put into the map in the BE order which is reversed to the natural LE order for bitmaps. For example, to construct bitmap containing a bit on the position 42, we have to put a line '400,0'. Current implementation reads chunk one by one from the beginning ('400' before '0') and makes bitmap shift after each successful parse. It makes the complexity of the whole process as O(n^2). We can do it in reverse direction ('0' before '400') and avoid shifting, but it requires reverse parsing helpers.
Tested on arm64 and BE mips.
v1: https://lkml.org/lkml/2019/4/27/597
v2:
- strnchrnul() signature and description changed, ifdeffery and exporting removed;
- test split for better demonstration of before/after changes;
- minor naming and formatting issues fixed.
[1] https://lkml.org/lkml/2019/4/16/66
Yury Norov (7):
lib/string: add strnchrnul()
bitops: more BITS_TO_* macros
lib: add test for bitmap_parse()
lib: make bitmap_parse_user a wrapper on bitmap_parse
lib: rework bitmap_parse()
lib: new testcases for bitmap_parse{_user}
cpumask: don't calculate length of the input string
include/linux/bitmap.h | 8 +- include/linux/bitops.h | 5 +- include/linux/cpumask.h | 4 +- include/linux/string.h | 1 + lib/bitmap.c | 197 +++++++++++++++++------------------ lib/string.c | 17 +++ lib/test_bitmap.c | 102 +++++++++++++++++- tools/include/linux/bitops.h | 9 +- 8 files changed, 226 insertions(+), 117 deletions(-)
Signature · 1 line
2.17.1
Yury Norov
maintainerPATCH 1/7 lib/string: add strnchrnul()
New function works like strchrnul() with a length limited strings.
--- include/linux/string.h | 1 + lib/string.c | 17 +++++++++++++++++ 2 files changed, 18 insertions(+)
include/linux/string.h +1 -0
@@ -62,6 +62,7 @@ extern char * strchr(const char *,int);#ifndef __HAVE_ARCH_STRCHRNULextern char *strchrnul (const char *,int );#endif +extern char *strnchrnul (const char *,size_t ,int );#ifndef __HAVE_ARCH_STRNCHRextern char *strnchr (const char *,size_t ,int );#endif
lib/string.c +17 -0
@@ -429,6 +429,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
Signature · 1 line
2.17.1
Re: [PATCH 1/7] lib/string: add strnchrnul()
Quoted 2 lines · Yury Norov
New function works like
strchrnul()with a length limited strings.
Quoted 49 lines
Signed-off-by Yury Norov <[email protected]>--- include/linux/string.h | 1 + lib/string.c | 17 +++++++++++++++++ 2 files changed, 18 insertions(+)include/linux/string.h +1
-0@@ -62,6 +62,7 @@ extern char * strchr(const char *,int);#ifndef __HAVE_ARCH_STRCHRNULextern char *strchrnul (const char *,int );#endif +extern char *strnchrnul (const char *,size_t ,int );#ifndef __HAVE_ARCH_STRNCHRextern char *strnchr (const char *,size_t ,int );#endif lib/string.c +17
-0@@ -429,6 +429,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 Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 2/7 bitops: more BITS_TO_* macros
In reply to Yury NorovIntroduce 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.
--- include/linux/bitops.h | 5 ++++- tools/include/linux/bitops.h | 9 +++++---- 2 files changed, 9 insertions(+), 5 deletions(-)
include/linux/bitops.h +4 -1
@@ -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);
tools/include/linux/bitops.h +5 -4
@@ -13,10 +13,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);
Signature · 1 line
2.17.1
Re: [PATCH 2/7] bitops: more BITS_TO_* macros
Quoted 6 lines · Yury Norov
Introduce
BITS_TO_U64,BITS_TO_U32andBITS_TO_BYTESas they are handy in the following patches (BITS_TO_U32specifically). Reimplementtools/version of the macros according to the kernel implementation.Also fix indentation for
BITS_PER_TYPEdefinition.
Quoted 46 lines
Signed-off-by Yury Norov <[email protected]>--- include/linux/bitops.h | 5 ++++- tools/include/linux/bitops.h | 9 +++++---- 2 files changed, 9 insertions(+), 5 deletions(-)include/linux/bitops.h +4
-1@@ -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);tools/include/linux/bitops.h +5
-4@@ -13,10 +13,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);Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 3/7 lib: add test for bitmap_parse()
In reply to Yury NorovThe test is derived from bitmap_parselist()NO_LEN is reserved for use in following patches.
--- lib/test_bitmap.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 93 insertions(+), 1 deletion(-)
lib/test_bitmap.c +93 -1
@@ -205,7 +205,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 0x2struct test_bitmap_parselist {const int errno;
@@ -328,6 +329,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 );
@@ -338,6 +418,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 )
@@ -409,6 +499,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 ();
Signature · 1 line
2.17.1
Re: [PATCH 3/7] lib: add test for bitmap_parse()
Quoted 3 lines · Yury Norov
The test is derived from
bitmap_parselist()NO_LENis reserved for use in following patches.
Quoted 134 lines
Signed-off-by Yury Norov <[email protected]>--- lib/test_bitmap.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 93 insertions(+), 1 deletion(-)lib/test_bitmap.c +93
-1@@ -205,7 +205,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 0x2struct test_bitmap_parselist {const int errno;@@ -328,6 +329,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 );@@ -338,6 +418,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 )@@ -409,6 +499,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 ();Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 4/7 lib: make bitmap_parse_user a wrapper on bitmap_parse
In reply to Yury NorovCurrently 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.
--- lib/bitmap.c | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-)
lib/bitmap.c +10 -10
@@ -434,22 +434,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);
Signature · 1 line
2.17.1
Re: [PATCH 4/7] lib: make bitmap_parse_user a wrapper on bitmap_parse
Quoted 7 lines · Yury Norov
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 callbitmap_parselist(). This rework lets us unify and simplifybitmap_parse()andbitmap_parse_user(), which is done in the following patch.
Quoted 45 lines
Signed-off-by Yury Norov <[email protected]>--- lib/bitmap.c | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-)lib/bitmap.c +10
-10@@ -434,22 +434,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);Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 5/7 lib: rework bitmap_parse()
In reply to Yury Norovbitmap_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.
--- include/linux/bitmap.h | 8 +- lib/bitmap.c | 179 ++++++++++++++++++++--------------------- 2 files changed, 88 insertions(+), 99 deletions(-)
include/linux/bitmap.h +1 -7
@@ -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
lib/bitmap.c +87 -92
209 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH 5/7] lib: rework bitmap_parse()
Quoted 13 lines · 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:
- removebitmap_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 withbitmap_parselist();
- splitbitmap_parse()to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of thebitmap_parse()won't bother doing this.
lib/bitmap.c static inline bool end_of_region(char c) · line 461
Quoted 5 lines
lib/bitmap.c +5
-0+static inline bool in_str (const char *start,const char *ptr) +{ +return start <= ptr; +} +
The explicit use of the conditional is better.
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerRe: [PATCH 5/7] lib: rework bitmap_parse()
Hi Andy,
Thanks for thorough review.
Quoted 14 lines · Andy Shevchenko
Quoted 12 lines · 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:
- removebitmap_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 withbitmap_parselist();
- splitbitmap_parse()to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of thebitmap_parse()won't bother doing this.
Quoted 11 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+static inline bool in_str(const char *start, const char *ptr) +{ + return start <= ptr; +} +The explicit use of the conditional is better.
Signature · 2 lines
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 <[email protected]>
Date: Thu, 9 May 2019 17:54:23 -0700
Subject: [PATCH] lib: opencode in_str()
--- lib/bitmap.c | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-)
lib/bitmap.c +3 -8
@@ -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 ;
Signature · 1 line
2.17.1
Andrew Morton
maintainerRe: [PATCH 5/7] lib: rework bitmap_parse()
Quoted 27 lines · On Thu, 9 May 2019 19:26:33 -0700 Yury Norov <[email protected]> wrote:
Hi Andy,
Thanks for thorough review.
Quoted 22 lines · Andy Shevchenko
Quoted 13 lines · 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:
- removebitmap_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 withbitmap_parselist();
- splitbitmap_parse()to small readable helpers;
- make an explicit calculation of the end of input line at the beginning, so users of thebitmap_parse()won't bother doing this.Review
Quoted 5 lines
(quoted diff) +5
-0+static inline bool in_str(const char *start, const char *ptr) +{ + return start <= ptr; +} +The explicit use of the conditional is better.
Quoted 7 lines
Quoted 3 lines
Signature · 2 lines
With Best Regards, Andy ShevchenkoI 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.
lib/bitmap.c int bitmap_parse(const char *start, unsigned int buflen, · line 651
Quoted 6 lines
lib/bitmap.c +1
-1@@ -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?
Quoted 3 lines
lib/bitmap.c +0
-0if (!chunks--)return -EOVERFLOW ;
Yury Norov
maintainerPATCH 6/7 lib: new testcases for bitmap_parse{_user}
In reply to Yury NorovNew 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.
--- lib/test_bitmap.c | 8 ++++++++ 1 file changed, 8 insertions(+)
lib/test_bitmap.c +8 -0
@@ -343,14 +343,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 },
Signature · 1 line
2.17.1
Re: [PATCH 6/7] lib: new testcases for bitmap_parse{_user}
Quoted 8 lines · Yury Norov
New version of
bitmap_parse()is unified withbitmap_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 passingUINT_MAXor any other big number as the length of input string instead of actual string length.The patch covers the cases.
Quoted 36 lines
Signed-off-by Yury Norov <[email protected]>--- lib/test_bitmap.c | 8 ++++++++ 1 file changed, 8 insertions(+)lib/test_bitmap.c +8
-0@@ -343,14 +343,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 },Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerPATCH 7/7 cpumask: don't calculate length of the input string
In reply to Yury NorovNew design of inner bitmap_parse() allows to avoid calculating the size of a null-terminated string.
--- include/linux/cpumask.h | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)
include/linux/cpumask.h +1 -3
@@ -633,9 +633,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); }/**
Signature · 1 line
2.17.1
Re: [PATCH 7/7] cpumask: don't calculate length of the input string
Quoted 3 lines · Yury Norov
New design of inner
bitmap_parse()allows to avoid calculating the size of a null-terminated string.
FWIW,
Quoted 23 lines
Signed-off-by Yury Norov <[email protected]>--- include/linux/cpumask.h | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)include/linux/cpumask.h +1
-3@@ -633,9 +633,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); }/** Signature · 1 line
2.17.1
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerQuoted 29 lines · Yury Norov
On top of next-20190418.
Similarly to recently revisited
bitmap_parselist()[1],bitmap_parse()is ineffective and overcomplicated. This series reworks it, aligns its interface withbitmap_parselist()and makes usage simpler.The series also adds a test for the function and fixes usage of it in
cpumask_parse()according to new design - drops the calculating of length of an input string.The following users would also consider to drop the length argument, if possible:
drivers/block/drbd/drbd_main.c:2608kernel/padata.c:924net/core/net-sysfs.c:726net/core/net-sysfs.c:1309net/core/net-sysfs.c:1391
bitmap_parse()takes the array of numbers to be put into the map in the BE order which is reversed to the natural LE order for bitmaps. For example, to construct bitmap containing a bit on the position 42, we have to put a line '400,0'. Current implementation reads chunk one by one from the beginning ('400' before '0') and makes bitmap shift after each successful parse. It makes the complexity of the whole process as O(n^2). We can do it in reverse direction ('0' before '400') and avoid shifting, but it requires reverse parsing helpers.
Quoted 1 line
Tested on arm64 and BE mips.
Any comments?
Quoted 30 lines
v1: https://lkml.org/lkml/2019/4/27/597
v2:
-strnchrnul()signature and description changed, ifdeffery and exporting removed;
- test split for better demonstration of before/after changes;
- minor naming and formatting issues fixed.[1] https://lkml.org/lkml/2019/4/16/66
Yury Norov (7):
lib/string: addstrnchrnul()
bitops: more BITS_TO_* macros
lib: add test forbitmap_parse()
lib: makebitmap_parse_usera wrapper onbitmap_parse
lib: reworkbitmap_parse()
lib: new testcases for bitmap_parse{_user}
cpumask: don't calculate length of the input stringinclude/linux/bitmap.h | 8 +- include/linux/bitops.h | 5 +- include/linux/cpumask.h | 4 +- include/linux/string.h | 1 + lib/bitmap.c | 197 +++++++++++++++++------------------ lib/string.c | 17 +++ lib/test_bitmap.c | 102 +++++++++++++++++- tools/include/linux/bitops.h | 9 +- 8 files changed, 226 insertions(+), 117 deletions(-)Signature · 1 line
2.17.1