aboutsummaryrefslogtreecommitdiffstats
path: root/lib/bitmap.c (follow)
AgeCommit message (Collapse)AuthorFilesLines
2022-09-26lib/bitmap: remove bitmap_ord_to_posYury Norov1-33/+3
Now that we have find_nth_bit(), we can drop bitmap_ord_to_pos(). Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-09-26lib/bitmap: add bitmap_weight_and()Yury Norov1-9/+21
The function calculates Hamming weight of (bitmap1 & bitmap2). Now we have to do like this: tmp = bitmap_alloc(nbits); bitmap_and(tmp, map1, map2, nbits); weight = bitmap_weight(tmp, nbits); bitmap_free(tmp); This requires additional memory, adds pressure on alloc subsystem, and way less cache-friendly than just: weight = bitmap_weight_and(map1, map2, nbits); The following patches apply it for cpumask functions. Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-09-26lib/bitmap: don't call __bitmap_weight() in kernel codeYury Norov1-1/+1
__bitmap_weight() is not to be used directly in the kernel code because it's a helper for bitmap_weight(). Switch everything to bitmap_weight(). Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-08-07Merge tag 'bitmap-6.0-rc1' of https://github.com/norov/linuxLinus Torvalds1-6/+5
Pull bitmap updates from Yury Norov: - fix the duplicated comments on bitmap_to_arr64() (Qu Wenruo) - optimize out non-atomic bitops on compile-time constants (Alexander Lobakin) - cleanup bitmap-related headers (Yury Norov) - x86/olpc: fix 'logical not is only applied to the left hand side' (Alexander Lobakin) - lib/nodemask: inline wrappers around bitmap (Yury Norov) * tag 'bitmap-6.0-rc1' of https://github.com/norov/linux: (26 commits) lib/nodemask: inline next_node_in() and node_random() powerpc: drop dependency on <asm/machdep.h> in archrandom.h x86/olpc: fix 'logical not is only applied to the left hand side' lib/cpumask: move some one-line wrappers to header file headers/deps: mm: align MANITAINERS and Docs with new gfp.h structure headers/deps: mm: Split <linux/gfp_types.h> out of <linux/gfp.h> headers/deps: mm: Optimize <linux/gfp.h> header dependencies lib/cpumask: move trivial wrappers around find_bit to the header lib/cpumask: change return types to unsigned where appropriate cpumask: change return types to bool where appropriate lib/bitmap: change type of bitmap_weight to unsigned long lib/bitmap: change return types to bool where appropriate arm: align find_bit declarations with generic kernel iommu/vt-d: avoid invalid memory access via node_online(NUMA_NO_NODE) lib/test_bitmap: test the tail after bitmap_to_arr64() lib/bitmap: fix off-by-one in bitmap_to_arr64() lib: test_bitmap: add compile-time optimization/evaluations assertions bitmap: don't assume compiler evaluates small mem*() builtins calls net/ice: fix initializing the bitmap in the switch code bitops: let optimize out non-atomic bitops on compile-time constants ...
2022-07-15lib/bitmap: change type of bitmap_weight to unsigned longYury Norov1-3/+2
bitmap_weight() doesn't return negative values, so change it's type to unsigned long. It may help compiler to generate better code and catch bugs. Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-07-14lib/bitmap: change return types to bool where appropriateYury Norov1-2/+2
Some bitmap functions return boolean results in int variables. Fix it by changing return types to bool. Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-07-12lib/bitmap: fix off-by-one in bitmap_to_arr64()Alexander Lobakin1-1/+1
GENMASK*() family takes the first and the last bits of the mask *including* them. So, with the current code bitmap_to_arr64() doesn't clear the tail properly: nbits % exp mask must be 1 GENMASK(1, 0) 0x3 0x1 ... 63 GENMASK(63, 0) 0xffffffffffffffff 0x7fffffffffffffff This was found by making the function always available instead of 32-bit BE systems only (for reusing in some new functionality). Turn the number of bits into the last bit set by subtracting 1. @nbits is already checked to be positive beforehand. Fixes: 0a97953fd221 ("lib: add bitmap_{from,to}_arr64") Signed-off-by: Alexander Lobakin <alexandr.lobakin@intel.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-06-03bitmap: Fix return values to be unsignedKees Cook1-15/+15
Both nodemask and bitmap routines had mixed return values that provided potentially signed return values that could never happen. This was leading to the compiler getting confusing about the range of possible return values (it was thinking things could be negative where they could not be). In preparation for fixing nodemask, fix all the bitmap routines that should be returning unsigned (or bool) values. Cc: Yury Norov <yury.norov@gmail.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Christophe de Dinechin <dinechin@redhat.com> Cc: Alexey Dobriyan <adobriyan@gmail.com> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Zhen Lei <thunder.leizhen@huawei.com> Signed-off-by: Kees Cook <keescook@chromium.org> Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-06-03lib: add bitmap_{from,to}_arr64Yury Norov1-0/+54
Manipulating 64-bit arrays with bitmap functions is potentially dangerous because on 32-bit BE machines the order of halfwords doesn't match. Another issue is that compiler may throw a warning about out-of-boundary access. This patch adds bitmap_{from,to}_arr64 functions in addition to existing bitmap_{from,to}_arr32. CC: Alexander Gordeev <agordeev@linux.ibm.com> CC: Andy Shevchenko <andriy.shevchenko@linux.intel.com> CC: Christian Borntraeger <borntraeger@linux.ibm.com> CC: Claudio Imbrenda <imbrenda@linux.ibm.com> CC: David Hildenbrand <david@redhat.com> CC: Heiko Carstens <hca@linux.ibm.com> CC: Janosch Frank <frankja@linux.ibm.com> CC: Rasmus Villemoes <linux@rasmusvillemoes.dk> CC: Sven Schnelle <svens@linux.ibm.com> CC: Vasily Gorbik <gor@linux.ibm.com> Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-06-03lib/bitmap.c make bitmap_print_bitmask_to_buf parseableMauro Carvalho Chehab1-13/+20
The documentation of such function is not on a proper ReST format, as reported by Sphinx: Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:526: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:532: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:533: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Definition list ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:542: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:536: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:543: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Unexpected indentation. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:545: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:545: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:552: WARNING: Inline emphasis start-string without end-string. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:554: WARNING: Block quote ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:556: WARNING: Definition list ends without a blank line; unexpected unindent. Documentation/core-api/kernel-api:81: ./lib/bitmap.c:580: WARNING: Unexpected indentation. So, the produced output at: https://www.kernel.org/doc/html/latest/core-api/kernel-api.html?#c.bitmap_print_bitmask_to_buf is broken. Fix it by adding spaces and marking the literal blocks. Signed-off-by: Mauro Carvalho Chehab <mchehab@kernel.org> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Signed-off-by: Yury Norov <yury.norov@gmail.com>
2022-03-23lib: bitmap: fix many kernel-doc warningsRandy Dunlap1-7/+17
Fix kernel-doc warings in lib/bitmap.c: lib/bitmap.c:498: warning: Function parameter or member 'buf' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'maskp' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'nmaskbits' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'off' not described in 'bitmap_print_to_buf' lib/bitmap.c:498: warning: Function parameter or member 'count' not described in 'bitmap_print_to_buf' lib/bitmap.c:561: warning: contents before sections lib/bitmap.c:606: warning: Function parameter or member 'buf' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'maskp' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'nmaskbits' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'off' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:606: warning: Function parameter or member 'count' not described in 'bitmap_print_list_to_buf' lib/bitmap.c:819: warning: missing initial short description on line: * bitmap_parselist_user() This still leaves 15 warnings for function return values not described, similar to this one: bitmap.c:890: warning: No description found for return value of 'bitmap_parse' Link: https://lkml.kernel.org/r/20220306065823.5153-1-rdunlap@infradead.org Fixes: 1fae562983ca ("cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask and list") Fixes: 4b060420a596 ("bitmap, irq: add smp_affinity_list interface to /proc/irq") Signed-off-by: Randy Dunlap <rdunlap@infradead.org> Cc: Yury Norov <yury.norov@gmail.com> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Tian Tao <tiantao6@hisilicon.com> Cc: Mike Travis <mike.travis@hpe.com> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2021-10-26lib: bitmap: Introduce node-aware alloc APITariq Toukan1-0/+13
Expose new node-aware API for bitmap allocation: bitmap_alloc_node() / bitmap_zalloc_node(). Signed-off-by: Tariq Toukan <tariqt@nvidia.com> Reviewed-by: Moshe Shemesh <moshe@nvidia.com> Signed-off-by: Saeed Mahameed <saeedm@nvidia.com>
2021-08-13bitmap: extend comment to bitmap_print_bitmask/list_to_bufYury Norov1-0/+18
Extend comment to new function to warn potential users about caveats. Signed-off-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Barry Song <song.bao.hua@hisilicon.com> Link: https://lore.kernel.org/r/20210806110251.560-6-song.bao.hua@hisilicon.com Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2021-08-13cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask and listTian Tao1-0/+103
The existing cpumap_print_to_pagebuf() is used by cpu topology and other drivers to export hexadecimal bitmask and decimal list to userspace by sysfs ABI. Right now, those drivers are using a normal attribute for this kind of ABIs. A normal attribute typically has show entry as below: static ssize_t example_dev_show(struct device *dev, struct device_attribute *attr, char *buf) { ... return cpumap_print_to_pagebuf(true, buf, &pmu_mmdc->cpu); } show entry of attribute has no offset and count parameters and this means the file is limited to one page only. cpumap_print_to_pagebuf() API works terribly well for this kind of normal attribute with buf parameter and without offset, count: static inline ssize_t cpumap_print_to_pagebuf(bool list, char *buf, const struct cpumask *mask) { return bitmap_print_to_pagebuf(list, buf, cpumask_bits(mask), nr_cpu_ids); } The problem is once we have many cpus, we have a chance to make bitmask or list more than one page. Especially for list, it could be as complex as 0,3,5,7,9,...... We have no simple way to know it exact size. It turns out bin_attribute is a way to break this limit. bin_attribute has show entry as below: static ssize_t example_bin_attribute_show(struct file *filp, struct kobject *kobj, struct bin_attribute *attr, char *buf, loff_t offset, size_t count) { ... } With the new offset and count parameters, this makes sysfs ABI be able to support file size more than one page. For example, offset could be >= 4096. This patch introduces cpumap_print_bitmask/list_to_buf() and their bitmap infrastructure bitmap_print_bitmask/list_to_buf() so that those drivers can move to bin_attribute to support large bitmask and list. At the same time, we have to pass those corresponding parameters such as offset, count from bin_attribute to this new API. Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Randy Dunlap <rdunlap@infradead.org> Cc: Stefano Brivio <sbrivio@redhat.com> Cc: Alexander Gordeev <agordeev@linux.ibm.com> Cc: "Ma, Jianpeng" <jianpeng.ma@intel.com> Cc: Yury Norov <yury.norov@gmail.com> Cc: Valentin Schneider <valentin.schneider@arm.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Daniel Bristot de Oliveira <bristot@redhat.com> Reviewed-by: Jonathan Cameron <Jonathan.Cameron@huawei.com> Signed-off-by: Tian Tao <tiantao6@hisilicon.com> Signed-off-by: Barry Song <song.bao.hua@hisilicon.com> Link: https://lore.kernel.org/r/20210806110251.560-2-song.bao.hua@hisilicon.com Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2021-07-05Merge tag 'gpio-updates-for-v5.14' of git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linuxLinus Torvalds1-2/+3
Pull gpio updates from Bartosz Golaszewski: "One new driver, support for new models in existing ones, dt-bindings conversions for several modules and improvements all over the place. Summary: - new driver for the IDT 79RC3243x GPIO controller - device tree bindings coversion to YAML for the following drivers: gpio-rk3328-grf, gpio-omap, gpio-davinci, gpio-zynq, gpio-stp, gpio-pcf857x - cleanup of probe functions in many drivers from Alexandru Ardelean, mostly dropping unnecessary calls to platform_set_drvdata() and removing error messages where none are needed (handled by the subsystem already) - several improvements to the core gpiolib and the sysfs interface code from Andy Shevchenko - conversion of the gpio-xilinx driver to using the bitmap API + improvements of suspend/resume handling + minor tweaks - convert the gpio-stmpe to using devres helpers exclusively in probe for improved robustness - updates for the generic gpio-regmap driver - updates for the gpio-dwapb driver - support for a new model in gpio-pca953x - cleanups in gpio-tegra186, gpio-104-idio-16, gpio-mxs & gpio-xgene - slight code refactoring of the gpio-zynq driver - documentation fixes from Mauro Carvalho Chehab - a bunch of minor tweaks and improvements all over the place" * tag 'gpio-updates-for-v5.14' of git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linux: (57 commits) docs: driver-api: gpio: using-gpio.rst: avoid using ReST :doc:`foo` markup dt-bindings: gpio: pcf857x: Convert to json-schema gpio: mxs: Prefer unsigned int to bare use of unsigned dt-bindings: gpio: stp: convert to json-schema dt-bindings: gpio: zynq: convert bindings to YAML dt-bindings: gpio: gpio-davinci: Convert to json-schema gpio: pca953x: Add support for the On Semi pca9655 gpio: gpio-xilinx: update on suspend and resume calls gpio: zynq: Check return value of irq_get_irq_data gpio: zynq: Check return value of pm_runtime_get_sync gpio: zynq: use module_platform_driver to simplify the code gpio: idt3243x: Fix return value check in idt_gpio_probe() MAINTAINERS: update ti,omap-gpio.yaml reference dt-bindings: gpio: Add devicetree binding for IDT 79RC32434 GPIO controller gpio: Add support for IDT 79RC3243x GPIO controller gpio: regmap: move drvdata to config data gpio-dwapb: Drop unused headers and sort the rest gpio: gpio-regmap: Use devm_add_action_or_reset() gpio: dwapb: Switch to use fwnode_irq_get() gpio: dwapb: Drop redundant check in dwapb_irq_set_type() ...
2021-05-12bitmap: Make bitmap_remap() and bitmap_bitremap() available to usersAndy Shevchenko1-2/+3
Currently the bitmap_remap() and bitmap_bitremap() are available only for CONFIG_NUMA=y case, while some users may benefit out of it and being independent to NUMA code. Make them available to users by moving out of ifdeffery and exporting for modules. Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Tested-by: Neeli Srinivas <sneeli@xilinx.com> Acked-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
2021-05-10bitmap_parse: Support 'all' semanticsYury Norov1-0/+9
RCU code supports an 'all' group as a special case when parsing rcu_nocbs parameter. This patch moves the 'all' support to the core bitmap_parse code, so that all bitmap users can enjoy this extension. Moving 'all' parsing to a bitmap_parse level also allows users to pass patterns together with 'all' in regular group:pattern format, for example, "rcu_nocbs=all:1/2" would offload all the even-numbered CPUs regardless of the number of CPUs on the system. Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-05-05Merge tag 'gpio-updates-for-v5.13-v2' of git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linuxLinus Torvalds1-4/+38
Pull gpio updates from Bartosz Golaszewski: - new driver for the Realtek Otto GPIO controller - ACPI support for gpio-mpc8xxx - edge event support for gpio-sch (+ Kconfig fixes) - Kconfig improvements in gpio-ich - fixes to older issues in gpio-mockup - ACPI quirk for ignoring EC wakeups on Dell Venue 10 Pro 5055 - improve the GPIO aggregator code by using more generic interfaces instead of reimplementing them in the driver - convert the DT bindings for gpio-74x164 to yaml - documentation improvements - a slew of other minor fixes and improvements to GPIO drivers * tag 'gpio-updates-for-v5.13-v2' of git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linux: (34 commits) dt-bindings: gpio: add YAML description for rockchip,gpio-bank gpio: mxs: remove useless function dt-bindings: gpio: fairchild,74hc595: Convert to json-schema gpio: it87: remove unused code gpio: 104-dio-48e: Fix coding style issues gpio: mpc8xxx: Add ACPI support gpio: ich: Switch to be dependent on LPC_ICH gpio: sch: Drop MFD_CORE selection gpio: sch: depends on LPC_SCH gpiolib: acpi: Add quirk to ignore EC wakeups on Dell Venue 10 Pro 5055 gpio: sch: Hook into ACPI GPE handler to catch GPIO edge events gpio: sch: Add edge event support gpio: aggregator: Replace custom get_arg() with a generic next_arg() lib/cmdline: Export next_arg() for being used in modules gpio: omap: Use device_get_match_data() helper gpio: Add Realtek Otto GPIO support dt-bindings: gpio: Binding for Realtek Otto GPIO docs: kernel-parameters: Add gpio_mockup_named_lines docs: kernel-parameters: Move gpio-mockup for alphabetic order lib: bitmap: provide devm_bitmap_alloc() and devm_bitmap_zalloc() ...
2021-05-05lib: bitmap: provide devm_bitmap_alloc() and devm_bitmap_zalloc()Bartosz Golaszewski1-0/+33
Provide managed variants of bitmap_alloc() and bitmap_zalloc(). Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
2021-05-05lib: bitmap: order includes alphabeticallyBartosz Golaszewski1-4/+5
For better readability and maintenance: order the includes in bitmap source files alphabetically. Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
2021-03-08lib: bitmap: support "N" as an alias for size of bitmapPaul Gortmaker1-5/+17
While this is done for all bitmaps, the original use case in mind was for CPU masks and cpulist_parse() as described below. It seems that a common configuration is to use the 1st couple cores for housekeeping tasks. This tends to leave the remaining ones to form a pool of similarly configured cores to take on the real workload of interest to the user. So on machine A - with 32 cores, it could be 0-3 for "system" and then 4-31 being used in boot args like nohz_full=, or rcu_nocbs= as part of setting up the worker pool of CPUs. But then newer machine B is added, and it has 48 cores, and so while the 0-3 part remains unchanged, the pool setup cpu list becomes 4-47. Multiple deployment becomes easier when we can just simply replace 31 and 47 with "N" and let the system substitute in the actual number at boot; a number that it knows better than we do. Cc: Yury Norov <yury.norov@gmail.com> Cc: Peter Zijlstra <peterz@infradead.org> Cc: "Paul E. McKenney" <paulmck@kernel.org> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Suggested-by: Yury Norov <yury.norov@gmail.com> # move it from CPU code Acked-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-03-08lib: bitmap: move ERANGE check from set_region to check_regionPaul Gortmaker1-9/+5
It makes sense to do all the checks in check_region() and not 1/2 in check_region and 1/2 in set_region. Since set_region is called immediately after check_region, the net effect on runtime is zero, but it gets rid of an if (...) return... Cc: Yury Norov <yury.norov@gmail.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Acked-by: Yury Norov <yury.norov@gmail.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2021-03-08lib: bitmap: fold nbits into region structPaul Gortmaker1-9/+10
This will reduce parameter passing and enable using nbits as part of future dynamic region parameter parsing. Cc: Yury Norov <yury.norov@gmail.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Suggested-by: Yury Norov <yury.norov@gmail.com> Acked-by: Yury Norov <yury.norov@gmail.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
2020-10-16lib: bitmap: delete duplicated wordsRandy Dunlap1-1/+1
Drop the repeated word "an". Signed-off-by: Randy Dunlap <rdunlap@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Link: https://lkml.kernel.org/r/20200823040424.25760-1-rdunlap@infradead.org Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-09-01Merge branch 'master' into for-nextJiri Kosina1-19/+25
Sync with Linus' branch in order to be able to apply fixups of more recent patches.
2020-08-12lib/bitmap.c: fix bitmap_cut() for partial overlapping caseStefano Brivio1-2/+2
Patch series "lib: Fix bitmap_cut() for overlaps, add test" This patch (of 2): Yury Norov reports that bitmap_cut() will not produce the right outcome if src and dst partially overlap, with src pointing at some location after dst, because the memmove() affects src before we store the bits that we need to keep, that is, the bits preceding the cut -- as long as we the beginning of the cut is not aligned to a long. Fix this by storing those bits before the memmove(). Note that this is just a theoretical concern so far, as the only user of this function, pipapo_drop() from the nftables set back-end implemented in net/netfilter/nft_set_pipapo.c, always supplies entirely overlapping src and dst. Fixes: 2092767168f0 ("bitmap: Introduce bitmap_cut(): cut bits and shift remaining") Reported-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Stefano Brivio <sbrivio@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Pablo Neira Ayuso <pablo@netfilter.org> Link: http://lkml.kernel.org/r/cover.1592155364.git.sbrivio@redhat.com Link: http://lkml.kernel.org/r/003e38d4428cd6091ef00b5b03354f1bd7d9091e.1592155364.git.sbrivio@redhat.com Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-06-10lib: fix bitmap_parse() on 64-bit big endian archsAlexander Gordeev1-2/+7
Commit 2d6261583be0 ("lib: rework bitmap_parse()") does not take into account order of halfwords on 64-bit big endian architectures. As result (at least) Receive Packet Steering, IRQ affinity masks and runtime kernel test "test_bitmap" get broken on s390. [andriy.shevchenko@linux.intel.com: convert infinite while loop to a for loop] Link: http://lkml.kernel.org/r/20200609140535.87160-1-andriy.shevchenko@linux.intel.com Fixes: 2d6261583be0 ("lib: rework bitmap_parse()") Signed-off-by: Alexander Gordeev <agordeev@linux.ibm.com> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <yury.norov@gmail.com> Cc: Amritha Nambiar <amritha.nambiar@intel.com> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Chris Wilson <chris@chris-wilson.co.uk> Cc: Kees Cook <keescook@chromium.org> Cc: Matthew Wilcox <willy@infradead.org> Cc: Miklos Szeredi <mszeredi@redhat.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Steffen Klassert <steffen.klassert@secunet.com> Cc: "Tobin C . Harding" <tobin@kernel.org> Cc: Vineet Gupta <vineet.gupta1@synopsys.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Willem de Bruijn <willemb@google.com> Cc: <stable@vger.kernel.org> Link: http://lkml.kernel.org/r/1591634471-17647-1-git-send-email-agordeev@linux.ibm.com Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-05-18lib/bitmap.c: fix spelloRandy Dunlap1-1/+1
Fix typo/spello for whitespaces. Signed-off-by: Randy Dunlap <rdunlap@infradead.org> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
2020-04-20lib: bitmap.c: get rid of some doc warningsMauro Carvalho Chehab1-15/+16
There are two ascii art drawings there. Use a block markup tag there in order to get rid of those warnings: ./lib/bitmap.c:189: WARNING: Unexpected indentation. ./lib/bitmap.c:190: WARNING: Block quote ends without a blank line; unexpected unindent. ./lib/bitmap.c:190: WARNING: Unexpected indentation. ./lib/bitmap.c:191: WARNING: Line block ends without a blank line. It should be noticed that there's actually a syntax violation right now, as something like: /** ... @src: will be handled as a definition for @src parameter, and not as part of a diagram. So, we need to add something before it, in order for this to be processed the way it should. Signed-off-by: Mauro Carvalho Chehab <mchehab+huawei@kernel.org> Link: https://lore.kernel.org/r/1e2568fdfa838c1a0d8cc2a1d70dd4b6de99bfb1.1586881715.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet <corbet@lwn.net>
2020-02-04lib: rework bitmap_parse()Yury Norov1-92/+83
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 <yury.norov@gmail.com> Cc: Amritha Nambiar <amritha.nambiar@intel.com> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Chris Wilson <chris@chris-wilson.co.uk> Cc: Kees Cook <keescook@chromium.org> Cc: Matthew Wilcox <willy@infradead.org> Cc: Miklos Szeredi <mszeredi@redhat.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Steffen Klassert <steffen.klassert@secunet.com> Cc: "Tobin C . Harding" <tobin@kernel.org> Cc: Vineet Gupta <vineet.gupta1@synopsys.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Willem de Bruijn <willemb@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-02-04lib: make bitmap_parse_user a wrapper on bitmap_parseYury Norov1-10/+10
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 <yury.norov@gmail.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Amritha Nambiar <amritha.nambiar@intel.com> Cc: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Chris Wilson <chris@chris-wilson.co.uk> Cc: Kees Cook <keescook@chromium.org> Cc: Matthew Wilcox <willy@infradead.org> Cc: Miklos Szeredi <mszeredi@redhat.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Steffen Klassert <steffen.klassert@secunet.com> Cc: "Tobin C . Harding" <tobin@kernel.org> Cc: Vineet Gupta <vineet.gupta1@synopsys.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Willem de Bruijn <willemb@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-01-27bitmap: Introduce bitmap_cut(): cut bits and shift remainingStefano Brivio1-0/+66
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 <sbrivio@redhat.com> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
2019-12-04lib/bitmap: introduce bitmap_replace() helperAndy Shevchenko1-0/+12
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 <andriy.shevchenko@linux.intel.com> Acked-by: Linus Walleij <linus.walleij@linaro.org> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Bartosz Golaszewski <bgolaszewski@baylibre.com> Cc: Geert Uytterhoeven <geert@linux-m68k.org> Cc: Marek Vasut <marek.vasut+renesas@gmail.com> Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com> Cc: William Breathitt Gray <vilhelm.gray@gmail.com> Cc: Yury Norov <yury.norov@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-07-25cpumask: Implement cpumask_or_equal()Thomas Gleixner1-0/+20
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 <tglx@linutronix.de> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Link: https://lkml.kernel.org/r/20190722105220.585449120@linutronix.de
2019-06-19treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 230Thomas Gleixner1-3/+1
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 <tglx@linutronix.de> Reviewed-by: Enrico Weigelt <info@metux.net> Reviewed-by: Allison Randal <allison@lohutok.net> Reviewed-by: Alexios Zavras <alexios.zavras@intel.com> Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190602204653.449021192@linutronix.de Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-05-14lib: rework bitmap_parselistYury Norov1-113/+142
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 <ynorov@marvell.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Arnd Bergmann <arnd@arndb.de> Cc: Kees Cook <keescook@chromium.org> Cc: Matthew Wilcox <willy@infradead.org> Cc: Mike Travis <travis@sgi.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Cc: Guenter Roeck <linux@roeck-us.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-05-14lib: make bitmap_parselist_user() a wrapper on bitmap_parselist()Yury Norov1-8/+11
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 <ynorov@marvell.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Arnd Bergmann <arnd@arndb.de> Cc: Kees Cook <keescook@chromium.org> Cc: Matthew Wilcox <willy@infradead.org> Cc: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Cc: Mike Travis <travis@sgi.com> Cc: Guenter Roeck <linux@roeck-us.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-05-14lib/bitmap.c: guard exotic bitmap functions by CONFIG_NUMARasmus Villemoes1-0/+2
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 <linux@rasmusvillemoes.dk> Cc: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <yury.norov@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-05-14lib/bitmap.c: remove unused EXPORT_SYMBOLsRasmus Villemoes1-4/+0
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 <linux@rasmusvillemoes.dk> Cc: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <yury.norov@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-01-03Remove 'type' argument from access_ok() functionLinus Torvalds1-2/+2
Nobody has actually used the type (VERIFY_READ vs VERIFY_WRITE) argument of the user address range verification function since we got rid of the old racy i386-only code to walk page tables by hand. It existed because the original 80386 would not honor the write protect bit when in kernel mode, so you had to do COW by hand before doing any user access. But we haven't supported that in a long time, and these days the 'type' argument is a purely historical artifact. A discussion about extending 'user_access_begin()' to do the range checking resulted this patch, because there is no way we're going to move the old VERIFY_xyz interface to that model. And it's best done at the end of the merge window when I've done most of my merges, so let's just get this done once and for all. This patch was mostly done with a sed-script, with manual fix-ups for the cases that weren't of the trivial 'access_ok(VERIFY_xyz' form. There were a couple of notable cases: - csky still had the old "verify_area()" name as an alias. - the iter_iov code had magical hardcoded knowledge of the actual values of VERIFY_{READ,WRITE} (not that they mattered, since nothing really used it) - microblaze used the type argument for a debug printout but other than those oddities this should be a total no-op patch. I tried to fix up all architectures, did fairly extensive grepping for access_ok() uses, and the changes are trivial, but I may have missed something. Any missed conversion should be trivially fixable, though. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-10-31lib/bitmap.c: simplify bitmap_print_to_pagebuf()Rasmus Villemoes1-5/+2
len is guaranteed to lie in [1, PAGE_SIZE]. If scnprintf is called with a buffer size of 1, it is guaranteed to return 0. So in the extremely unlikely case of having just one byte remaining in the page, let's just call scnprintf anyway. The only difference is that this will write a '\0' to that final byte in the page, but that's an improvement: We now guarantee that after the call, buf is a properly terminated C string of length exactly the return value. Link: http://lkml.kernel.org/r/20180818131623.8755-8-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <ynorov@caviumnetworks.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-10-31lib/bitmap.c: fix remaining space computation in bitmap_print_to_pagebufRasmus Villemoes1-4/+6
For various alignments of buf, the current expression computes 4096 ok 4095 ok 8190 8189 ... 4097 i.e., if the caller has already written two bytes into the page buffer, len is 8190 rather than 4094, because PTR_ALIGN aligns up to the next boundary. So if the printed version of the bitmap is huge, scnprintf() ends up writing beyond the page boundary. I don't think any current callers actually write anything before bitmap_print_to_pagebuf, but the API seems to be designed to allow it. [akpm@linux-foundation.org: use offset_in_page(), per Andy] [akpm@linux-foundation.org: include mm.h for offset_in_page()] Link: http://lkml.kernel.org/r/20180818131623.8755-7-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <ynorov@caviumnetworks.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-10-31lib/bitmap.c: remove wrong documentationRasmus Villemoes1-5/+0
This promise is violated in a number of places, e.g. already in the second function below this paragraph. Since I don't think anybody relies on this being true, and since actually honouring it would hurt performance and code size in various places, just remove the paragraph. Link: http://lkml.kernel.org/r/20180818131623.8755-2-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com> Cc: Yury Norov <ynorov@caviumnetworks.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Sudeep Holla <sudeep.holla@arm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-08-22lib/bitmap.c: drop unnecessary 0 check for u32 array operationsAndy Shevchenko1-8/+1
nbits == 0 is safe to be supplied to the function body, so remove unnecessary checks in bitmap_to_arr32() and bitmap_from_arr32(). Link: http://lkml.kernel.org/r/20180531131914.44352-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Acked-by: Yury Norov <ynorov@caviumnetworks.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-08-18Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dtor/inputLinus Torvalds1-0/+20
Pull input updates from Dmitry Torokhov: - a new driver for Rohm BU21029 touch controller - new bitmap APIs: bitmap_alloc, bitmap_zalloc and bitmap_free - updates to Atmel, eeti. pxrc and iforce drivers - assorted driver cleanups and fixes. * 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dtor/input: (57 commits) MAINTAINERS: Add PhoenixRC Flight Controller Adapter Input: do not use WARN() in input_alloc_absinfo() Input: mark expected switch fall-throughs Input: raydium_i2c_ts - use true and false for boolean values Input: evdev - switch to bitmap API Input: gpio-keys - switch to bitmap_zalloc() Input: elan_i2c_smbus - cast sizeof to int for comparison bitmap: Add bitmap_alloc(), bitmap_zalloc() and bitmap_free() md: Avoid namespace collision with bitmap API dm: Avoid namespace collision with bitmap API Input: pm8941-pwrkey - add resin entry Input: pm8941-pwrkey - abstract register offsets and event code Input: iforce - reorganize joystick configuration lists Input: atmel_mxt_ts - move completion to after config crc is updated Input: atmel_mxt_ts - don't report zero pressure from T9 Input: atmel_mxt_ts - zero terminate config firmware file Input: atmel_mxt_ts - refactor config update code to add context struct Input: atmel_mxt_ts - config CRC may start at T71 Input: atmel_mxt_ts - remove unnecessary debug on ENOMEM Input: atmel_mxt_ts - remove duplicate setup of ABS_MT_PRESSURE ...
2018-08-01bitmap: Add bitmap_alloc(), bitmap_zalloc() and bitmap_free()Andy Shevchenko1-0/+20
A lot of code become ugly because of open coding allocations for bitmaps. Introduce three helpers to allow users be more clear of intention and keep their code neat. Note, due to multiple circular dependencies we may not provide the helpers as inliners. For now we keep them exported and, perhaps, at some point in the future we will sort out header inclusion and inheritance. Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Dmitry Torokhov <dmitry.torokhov@gmail.com>
2018-06-07lib/bitmap.c: micro-optimization for __bitmap_complement()Yury Norov1-4/+1
Use BITS_TO_LONGS() macro to avoid calculation of reminder (bits % BITS_PER_LONG) On ARM64 it saves 5 instruction for function - 16 before and 11 after. Link: http://lkml.kernel.org/r/20180411145914.6011-1-ynorov@caviumnetworks.com Signed-off-by: Yury Norov <ynorov@caviumnetworks.com> Reviewed-by: Andrew Morton <akpm@linux-foundation.org> Cc: Matthew Wilcox <mawilcox@microsoft.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-04-05lib: fix stall in __bitmap_parselist()Yury Norov1-1/+1
syzbot is catching stalls at __bitmap_parselist() (https://syzkaller.appspot.com/bug?id=ad7e0351fbc90535558514a71cd3edc11681997a). The trigger is unsigned long v = 0; bitmap_parselist("7:,", &v, BITS_PER_LONG); which results in hitting infinite loop at while (a <= b) { off = min(b - a + 1, used_size); bitmap_set(maskp, a, off); a += group_size; } due to used_size == group_size == 0. Link: http://lkml.kernel.org/r/20180404162647.15763-1-ynorov@caviumnetworks.com Fixes: 0a5ce0831d04382a ("lib/bitmap.c: make bitmap_parselist() thread-safe and much faster") Signed-off-by: Yury Norov <ynorov@caviumnetworks.com> Reported-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Reported-by: syzbot <syzbot+6887cbb011c8054e8a3d@syzkaller.appspotmail.com> Cc: Noam Camus <noamca@mellanox.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Matthew Wilcox <mawilcox@microsoft.com> Cc: Mauro Carvalho Chehab <mchehab@kernel.org> Cc: <stable@vger.kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-02-06bitmap: replace bitmap_{from,to}_u32arrayYury Norov1-87/+0
with bitmap_{from,to}_arr32 over the kernel. Additionally to it: * __check_eq_bitmap() now takes single nbits argument. * __check_eq_u32_array is not used in new test but may be used in future. So I don't remove it here, but annotate as __used. Tested on arm64 and 32-bit BE mips. [arnd@arndb.de: perf: arm_dsu_pmu: convert to bitmap_from_arr32] Link: http://lkml.kernel.org/r/20180201172508.5739-2-ynorov@caviumnetworks.com [ynorov@caviumnetworks.com: fix net/core/ethtool.c] Link: http://lkml.kernel.org/r/20180205071747.4ekxtsbgxkj5b2fz@yury-thinkpad Link: http://lkml.kernel.org/r/20171228150019.27953-2-ynorov@caviumnetworks.com Signed-off-by: Yury Norov <ynorov@caviumnetworks.com> Signed-off-by: Arnd Bergmann <arnd@arndb.de> Cc: Ben Hutchings <ben@decadent.org.uk> Cc: David Decotigny <decot@googlers.com>, Cc: David S. Miller <davem@davemloft.net>, Cc: Geert Uytterhoeven <geert@linux-m68k.org> Cc: Matthew Wilcox <mawilcox@microsoft.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Heiner Kallweit <hkallweit1@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-02-06bitmap: new bitmap_copy_safe and bitmap_{from,to}_arr32Yury Norov1-0/+56
This patchset replaces bitmap_{to,from}_u32array with more simple and standard looking copy-like functions. bitmap_from_u32array() takes 4 arguments (bitmap_to_u32array is similar): - unsigned long *bitmap, which is destination; - unsigned int nbits, the length of destination bitmap, in bits; - const u32 *buf, the source; and - unsigned int nwords, the length of source buffer in ints. In description to the function it is detailed like: * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining * bits between nword and nbits in @bitmap (if any) are cleared. Having two size arguments looks unneeded and potentially dangerous. It is unneeded because normally user of copy-like function should take care of the size of destination and make it big enough to fit source data. And it is dangerous because function may hide possible error if user doesn't provide big enough bitmap, and data becomes silently dropped. That's why all copy-like functions have 1 argument for size of copying data, and I don't see any reason to make bitmap_from_u32array() different. One exception that comes in mind is strncpy() which also provides size of destination in arguments, but it's strongly argued by the possibility of taking broken strings in source. This is not the case of bitmap_{from,to}_u32array(). There is no many real users of bitmap_{from,to}_u32array(), and they all very clearly provide size of destination matched with the size of source, so additional functionality is not used in fact. Like this: bitmap_from_u32array(to->link_modes.supported, __ETHTOOL_LINK_MODE_MASK_NBITS, link_usettings.link_modes.supported, __ETHTOOL_LINK_MODE_MASK_NU32); Where: #define __ETHTOOL_LINK_MODE_MASK_NU32 \ DIV_ROUND_UP(__ETHTOOL_LINK_MODE_MASK_NBITS, 32) In this patch, bitmap_copy_safe and bitmap_{from,to}_arr32 are introduced. 'Safe' in bitmap_copy_safe() stands for clearing unused bits in bitmap beyond last bit till the end of last word. It is useful for hardening API when bitmap is assumed to be exposed to userspace. bitmap_{from,to}_arr32 functions are replacements for bitmap_{from,to}_u32array. They don't take unneeded nwords argument, and so simpler in implementation and understanding. This patch suggests optimization for 32-bit systems - aliasing bitmap_{from,to}_arr32 to bitmap_copy_safe. Other possible optimization is aliasing 64-bit LE bitmap_{from,to}_arr32 to more generic function(s). But I didn't end up with the function that would be helpful by itself, and can be used to alias 64-bit LE bitmap_{from,to}_arr32, like bitmap_copy_safe() does. So I preferred to leave things as is. The following patch switches kernel to new API and introduces test for it. Discussion is here: https://lkml.org/lkml/2017/11/15/592 [ynorov@caviumnetworks.com: rename bitmap_copy_safe to bitmap_copy_clear_tail] Link: http://lkml.kernel.org/r/20180201172508.5739-3-ynorov@caviumnetworks.com Link: http://lkml.kernel.org/r/20171228150019.27953-1-ynorov@caviumnetworks.com Signed-off-by: Yury Norov <ynorov@caviumnetworks.com> Cc: Ben Hutchings <ben@decadent.org.uk> Cc: David Decotigny <decot@googlers.com>, Cc: David S. Miller <davem@davemloft.net>, Cc: Geert Uytterhoeven <geert@linux-m68k.org> Cc: Matthew Wilcox <mawilcox@microsoft.com> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.