linux/lib/bitmap.c, branch v5.6

lib: rework bitmap_parse()

2020-02-04T03:05:26Z

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

lib: make bitmap_parse_user a wrapper on bitmap_parse

2020-02-04T03:05:26Z

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. Link: http://lkml.kernel.org/r/20200102043031.30357-5-yury.norov@gmail.com Signed-off-by: Yury Norov Reviewed-by: Andy Shevchenko Cc: Amritha Nambiar 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

bitmap: Introduce bitmap_cut(): cut bits and shift remaining

2020-01-27T07:54:30Z

The new bitmap function bitmap_cut() copies bits from source to destination by removing the region specified by parameters first and cut, and remapping the bits above the cut region by right shifting them. Signed-off-by: Stefano Brivio Signed-off-by: Pablo Neira Ayuso

lib/bitmap: introduce bitmap_replace() helper

2019-12-05T03:44:14Z

In some drivers we want to have a single operation over bitmap which is an equivalent to: *dst = (*old & ~(*mask)) | (*new & *mask) Introduce bitmap_replace() helper for this. Link: http://lkml.kernel.org/r/20191022172922.61232-8-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko Acked-by: Linus Walleij Cc: Rasmus Villemoes Cc: Bartosz Golaszewski Cc: Geert Uytterhoeven Cc: Marek Vasut Cc: Thomas Petazzoni Cc: William Breathitt Gray Cc: Yury Norov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

cpumask: Implement cpumask_or_equal()

2019-07-25T13:47:37Z

The IPI code of x86 needs to evaluate whether the target cpumask is equal to the cpu_online_mask or equal except for the calling CPU. To replace the current implementation which requires the usage of a temporary cpumask, which might involve allocations, add a new function which compares a cpumask to the result of two other cpumasks which are or'ed together before comparison. This allows to make the required decision in one go and the calling code then can check for the calling CPU being set in the target mask with cpumask_test_cpu(). Signed-off-by: Thomas Gleixner Acked-by: Peter Zijlstra (Intel) Link: https://lkml.kernel.org/r/20190722105220.585449120@linutronix.de

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 230

2019-06-19T15:09:06Z

Based on 2 normalized pattern(s): this source code is licensed under the gnu general public license version 2 see the file copying for more details this source code is licensed under general public license version 2 see extracted by the scancode license scanner the SPDX license identifier GPL-2.0-only has been chosen to replace the boilerplate/reference in 52 file(s). Signed-off-by: Thomas Gleixner Reviewed-by: Enrico Weigelt Reviewed-by: Allison Randal Reviewed-by: Alexios Zavras Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190602204653.449021192@linutronix.de Signed-off-by: Greg Kroah-Hartman

lib: rework bitmap_parselist

2019-05-15T02:52:49Z

Remove __bitmap_parselist helper and split the function to logical parts. [ynorov@marvell.com: v5] Link: http://lkml.kernel.org/r/20190416063801.20134-3-ynorov@marvell.com Link: http://lkml.kernel.org/r/20190405173211.11373-3-ynorov@marvell.com Signed-off-by: Yury Norov Reviewed-by: Andy Shevchenko Cc: Arnd Bergmann Cc: Kees Cook Cc: Matthew Wilcox Cc: Mike Travis Cc: Rasmus Villemoes Cc: Tetsuo Handa Cc: Guenter Roeck Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib: make bitmap_parselist_user() a wrapper on bitmap_parselist()

2019-05-15T02:52:49Z

Patch series "lib: rework bitmap_parselist and tests", v5. bitmap_parselist has been evolved from a pretty simple idea for long and now lacks for refactoring. It is not structured, has nested loops and a set of opaque-named variables. Things are more complicated because bitmap_parselist() is a part of user interface, and its behavior should not change. In this patchset - bitmap_parselist_user() made a wrapper on bitmap_parselist(); - bitmap_parselist() reworked (patch 2); - time measurement in test_bitmap_parselist switched to ktime_get (patch 3); - new tests introduced (patch 4), and - bitmap_parselist_user() testing enabled with the same testset as bitmap_parselist() (patch 5). This patch (of 5): Currently we parse user data byte after byte which leads to overcomplification of parsing algorithm. The only user of bitmap_parselist_user() is not performance-critical, and so we can duplicate user data to kernel buffer and simply call bitmap_parselist(). This rework lets us unify and simplify bitmap_parselist() and bitmap_parselist_user(), which is done in the following patch. Link: http://lkml.kernel.org/r/20190405173211.11373-2-ynorov@marvell.com Signed-off-by: Yury Norov Reviewed-by: Andy Shevchenko Cc: Rasmus Villemoes Cc: Arnd Bergmann Cc: Kees Cook Cc: Matthew Wilcox Cc: Tetsuo Handa Cc: Mike Travis Cc: Guenter Roeck Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/bitmap.c: guard exotic bitmap functions by CONFIG_NUMA

2019-05-15T02:52:49Z

The bitmap_remap, _bitremap, _onto and _fold functions are only used, via their node_ wrappers, in mm/mempolicy.c, which is only built for CONFIG_NUMA. The helper bitmap_ord_to_pos used by these functions is global, but its only external caller is node_random() in lib/nodemask.c, which is also guarded by CONFIG_NUMA. For !CONFIG_NUMA: add/remove: 0/6 grow/shrink: 0/0 up/down: 0/-621 (-621) Function old new delta bitmap_pos_to_ord 20 - -20 bitmap_ord_to_pos 70 - -70 bitmap_bitremap 81 - -81 bitmap_fold 113 - -113 bitmap_onto 123 - -123 bitmap_remap 214 - -214 Total: Before=4776, After=4155, chg -13.00% Link: http://lkml.kernel.org/r/20190329205353.6010-2-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes Cc: Andy Shevchenko Cc: Yury Norov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/bitmap.c: remove unused EXPORT_SYMBOLs

2019-05-15T02:52:49Z

AFAICT, there have never been any callers of these functions outside mm/mempolicy.c (via their nodemask.h wrappers). In particular, no modular code has ever used them, and given their somewhat exotic semantics, I highly doubt they will ever find such a use. In any case, no need to export them currently. Link: http://lkml.kernel.org/r/20190329205353.6010-1-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes Cc: Andy Shevchenko Cc: Yury Norov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds