From 2d6261583be005a91e4933aa53bbd678ef98e4c4 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 3 Feb 2020 17:37:34 -0800 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. Link: http://lkml.kernel.org/r/20200102043031.30357-6-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amritha Nambiar Cc: Andy Shevchenko Cc: Arnaldo Carvalho de Melo Cc: Chris Wilson Cc: Kees Cook Cc: Matthew Wilcox Cc: Miklos Szeredi Cc: Rasmus Villemoes Cc: Steffen Klassert Cc: "Tobin C . Harding" Cc: Vineet Gupta Cc: Will Deacon Cc: Willem de Bruijn Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/bitmap.h | 8 +------- 1 file changed, 1 insertion(+), 7 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 80ad521116d7..e52ceb1a73d3 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -186,7 +186,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); @@ -454,12 +454,6 @@ static inline void bitmap_replace(unsigned long *dst, __bitmap_replace(dst, old, new, mask, 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); -} - static inline void bitmap_next_clear_region(unsigned long *bitmap, unsigned int *rs, unsigned int *re, unsigned int end) -- cgit v1.2.3 From 780d2a9c86dc12594e263752cd8426a5794f1cc8 Mon Sep 17 00:00:00 2001 From: Wolfram Sang Date: Wed, 4 Mar 2020 15:09:19 +0100 Subject: include/bitmap.h: add missing parameter in docs bitmap_find_next_zero_area_off() has an additional parameter which was not specified in the list of functions. Add it. Fixes: 5e19b013f55a ("lib: bitmap: add alignment offset for bitmap_find_next_zero_area()") Signed-off-by: Wolfram Sang Signed-off-by: Dennis Zhou --- include/linux/bitmap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index e52ceb1a73d3..804600f7dc35 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -50,7 +50,7 @@ * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area - * bitmap_find_next_zero_area_off(buf, len, pos, n, mask) as above + * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest -- cgit v1.2.3 From a392d26f32cdd87e09b1ea3849db79cfc4eae745 Mon Sep 17 00:00:00 2001 From: Wolfram Sang Date: Wed, 4 Mar 2020 15:09:20 +0100 Subject: include/bitmap.h: add new functions to documentation I found these functions only by chance although I was looking exactly for something like them. So, add them to the list of functions to make them more visible. Fixes: e837dfde15a4 ("bitmap: genericize percpu bitmap region iterators") Signed-off-by: Wolfram Sang Signed-off-by: Dennis Zhou --- include/linux/bitmap.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 804600f7dc35..99058eb81042 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -51,6 +51,12 @@ * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above + * bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region + * bitmap_next_set_region(map, &start, &end, nbits) Find next set region + * bitmap_for_each_clear_region(map, rs, re, start, end) + * Iterate over all clear regions + * bitmap_for_each_set_region(map, rs, re, start, end) + * Iterate over all set regions * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest -- cgit v1.2.3