aboutsummaryrefslogtreecommitdiff
path: root/lib/bitmap.c
AgeCommit message (Collapse)AuthorFilesLines
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 <[email protected]>
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 <[email protected]>
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 <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Signed-off-by: Yury Norov <[email protected]>
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 <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Christophe de Dinechin <[email protected]> Cc: Alexey Dobriyan <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Andrew Morton <[email protected]> Cc: Zhen Lei <[email protected]> Signed-off-by: Kees Cook <[email protected]> Signed-off-by: Yury Norov <[email protected]>
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 <[email protected]> CC: Andy Shevchenko <[email protected]> CC: Christian Borntraeger <[email protected]> CC: Claudio Imbrenda <[email protected]> CC: David Hildenbrand <[email protected]> CC: Heiko Carstens <[email protected]> CC: Janosch Frank <[email protected]> CC: Rasmus Villemoes <[email protected]> CC: Sven Schnelle <[email protected]> CC: Vasily Gorbik <[email protected]> Signed-off-by: Yury Norov <[email protected]>
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 <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Signed-off-by: Yury Norov <[email protected]>
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/[email protected] 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 <[email protected]> Cc: Yury Norov <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Tian Tao <[email protected]> Cc: Mike Travis <[email protected]> Cc: Greg Kroah-Hartman <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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 <[email protected]> Reviewed-by: Moshe Shemesh <[email protected]> Signed-off-by: Saeed Mahameed <[email protected]>
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 <[email protected]> Signed-off-by: Barry Song <[email protected]> Link: https://lore.kernel.org/r/[email protected] Signed-off-by: Greg Kroah-Hartman <[email protected]>
2021-08-13cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask ↵Tian Tao1-0/+103
and list 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 <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Randy Dunlap <[email protected]> Cc: Stefano Brivio <[email protected]> Cc: Alexander Gordeev <[email protected]> Cc: "Ma, Jianpeng" <[email protected]> Cc: Yury Norov <[email protected]> Cc: Valentin Schneider <[email protected]> Cc: Peter Zijlstra <[email protected]> Cc: Daniel Bristot de Oliveira <[email protected]> Reviewed-by: Jonathan Cameron <[email protected]> Signed-off-by: Tian Tao <[email protected]> Signed-off-by: Barry Song <[email protected]> Link: https://lore.kernel.org/r/[email protected] Signed-off-by: Greg Kroah-Hartman <[email protected]>
2021-07-05Merge tag 'gpio-updates-for-v5.14' of ↵Linus Torvalds1-2/+3
git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linux 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 <[email protected]> Tested-by: Neeli Srinivas <[email protected]> Acked-by: Yury Norov <[email protected]> Signed-off-by: Bartosz Golaszewski <[email protected]>
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 <[email protected]> Signed-off-by: Yury Norov <[email protected]> Signed-off-by: Paul E. McKenney <[email protected]>
2021-05-05Merge tag 'gpio-updates-for-v5.13-v2' of ↵Linus Torvalds1-4/+38
git://git.kernel.org/pub/scm/linux/kernel/git/brgl/linux 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 <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]>
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 <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]>
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 <[email protected]> Cc: Peter Zijlstra <[email protected]> Cc: "Paul E. McKenney" <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Andy Shevchenko <[email protected]> Suggested-by: Yury Norov <[email protected]> # move it from CPU code Acked-by: Yury Norov <[email protected]> Signed-off-by: Paul Gortmaker <[email protected]> Signed-off-by: Paul E. McKenney <[email protected]>
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 <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Andy Shevchenko <[email protected]> Acked-by: Yury Norov <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Signed-off-by: Paul Gortmaker <[email protected]> Signed-off-by: Paul E. McKenney <[email protected]>
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 <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Andy Shevchenko <[email protected]> Suggested-by: Yury Norov <[email protected]> Acked-by: Yury Norov <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Signed-off-by: Paul Gortmaker <[email protected]> Signed-off-by: Paul E. McKenney <[email protected]>
2020-10-16lib: bitmap: delete duplicated wordsRandy Dunlap1-1/+1
Drop the repeated word "an". Signed-off-by: Randy Dunlap <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Link: https://lkml.kernel.org/r/[email protected] Signed-off-by: Linus Torvalds <[email protected]>
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 <[email protected]> Signed-off-by: Stefano Brivio <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Pablo Neira Ayuso <[email protected]> Link: http://lkml.kernel.org/r/[email protected] Link: http://lkml.kernel.org/r/003e38d4428cd6091ef00b5b03354f1bd7d9091e.1592155364.git.sbrivio@redhat.com Signed-off-by: Linus Torvalds <[email protected]>
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. [[email protected]: convert infinite while loop to a for loop] Link: http://lkml.kernel.org/r/[email protected] Fixes: 2d6261583be0 ("lib: rework bitmap_parse()") Signed-off-by: Alexander Gordeev <[email protected]> Signed-off-by: Andy Shevchenko <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Cc: Amritha Nambiar <[email protected]> Cc: Arnaldo Carvalho de Melo <[email protected]> Cc: Chris Wilson <[email protected]> Cc: Kees Cook <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Miklos Szeredi <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Steffen Klassert <[email protected]> Cc: "Tobin C . Harding" <[email protected]> Cc: Vineet Gupta <[email protected]> Cc: Will Deacon <[email protected]> Cc: Willem de Bruijn <[email protected]> Cc: <[email protected]> Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Linus Torvalds <[email protected]>
2020-05-18lib/bitmap.c: fix spelloRandy Dunlap1-1/+1
Fix typo/spello for whitespaces. Signed-off-by: Randy Dunlap <[email protected]> Signed-off-by: Jiri Kosina <[email protected]>
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 <[email protected]> Link: https://lore.kernel.org/r/1e2568fdfa838c1a0d8cc2a1d70dd4b6de99bfb1.1586881715.git.mchehab+huawei@kernel.org Signed-off-by: Jonathan Corbet <[email protected]>
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/[email protected] Signed-off-by: Yury Norov <[email protected]> Cc: Amritha Nambiar <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Arnaldo Carvalho de Melo <[email protected]> Cc: Chris Wilson <[email protected]> Cc: Kees Cook <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Miklos Szeredi <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Steffen Klassert <[email protected]> Cc: "Tobin C . Harding" <[email protected]> Cc: Vineet Gupta <[email protected]> Cc: Will Deacon <[email protected]> Cc: Willem de Bruijn <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Yury Norov <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Amritha Nambiar <[email protected]> Cc: Arnaldo Carvalho de Melo <[email protected]> Cc: Chris Wilson <[email protected]> Cc: Kees Cook <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Miklos Szeredi <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Steffen Klassert <[email protected]> Cc: "Tobin C . Harding" <[email protected]> Cc: Vineet Gupta <[email protected]> Cc: Will Deacon <[email protected]> Cc: Willem de Bruijn <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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 <[email protected]> Signed-off-by: Pablo Neira Ayuso <[email protected]>
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/[email protected] Signed-off-by: Andy Shevchenko <[email protected]> Acked-by: Linus Walleij <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Bartosz Golaszewski <[email protected]> Cc: Geert Uytterhoeven <[email protected]> Cc: Marek Vasut <[email protected]> Cc: Thomas Petazzoni <[email protected]> Cc: William Breathitt Gray <[email protected]> Cc: Yury Norov <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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 <[email protected]> Acked-by: Peter Zijlstra (Intel) <[email protected]> Link: https://lkml.kernel.org/r/[email protected]
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 <[email protected]> Reviewed-by: Enrico Weigelt <[email protected]> Reviewed-by: Allison Randal <[email protected]> Reviewed-by: Alexios Zavras <[email protected]> Cc: [email protected] Link: https://lkml.kernel.org/r/[email protected] Signed-off-by: Greg Kroah-Hartman <[email protected]>
2019-05-14lib: rework bitmap_parselistYury Norov1-113/+142
Remove __bitmap_parselist helper and split the function to logical parts. [[email protected]: v5] Link: http://lkml.kernel.org/r/[email protected] Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Yury Norov <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Arnd Bergmann <[email protected]> Cc: Kees Cook <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Mike Travis <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Tetsuo Handa <[email protected]> Cc: Guenter Roeck <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Yury Norov <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Arnd Bergmann <[email protected]> Cc: Kees Cook <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Tetsuo Handa <[email protected]> Cc: Mike Travis <[email protected]> Cc: Guenter Roeck <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Rasmus Villemoes <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Rasmus Villemoes <[email protected]> Cc: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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 <[email protected]>
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/[email protected] Signed-off-by: Rasmus Villemoes <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Sudeep Holla <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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. [[email protected]: use offset_in_page(), per Andy] [[email protected]: include mm.h for offset_in_page()] Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Rasmus Villemoes <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Sudeep Holla <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Rasmus Villemoes <[email protected]> Reviewed-by: Andy Shevchenko <[email protected]> Cc: Yury Norov <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Sudeep Holla <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Signed-off-by: Andy Shevchenko <[email protected]> Acked-by: Yury Norov <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2018-08-18Merge branch 'for-linus' of ↵Linus Torvalds1-0/+20
git://git.kernel.org/pub/scm/linux/kernel/git/dtor/input 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 <[email protected]> Signed-off-by: Dmitry Torokhov <[email protected]>
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/[email protected] Signed-off-by: Yury Norov <[email protected]> Reviewed-by: Andrew Morton <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Rasmus Villemoes <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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/[email protected] Fixes: 0a5ce0831d04382a ("lib/bitmap.c: make bitmap_parselist() thread-safe and much faster") Signed-off-by: Yury Norov <[email protected]> Reported-by: Tetsuo Handa <[email protected]> Reported-by: syzbot <[email protected]> Cc: Noam Camus <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Mauro Carvalho Chehab <[email protected]> Cc: <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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. [[email protected]: perf: arm_dsu_pmu: convert to bitmap_from_arr32] Link: http://lkml.kernel.org/r/[email protected] [[email protected]: fix net/core/ethtool.c] Link: http://lkml.kernel.org/r/20180205071747.4ekxtsbgxkj5b2fz@yury-thinkpad Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Yury Norov <[email protected]> Signed-off-by: Arnd Bergmann <[email protected]> Cc: Ben Hutchings <[email protected]> Cc: David Decotigny <[email protected]>, Cc: David S. Miller <[email protected]>, Cc: Geert Uytterhoeven <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Heiner Kallweit <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
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 [[email protected]: rename bitmap_copy_safe to bitmap_copy_clear_tail] Link: http://lkml.kernel.org/r/[email protected] Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Yury Norov <[email protected]> Cc: Ben Hutchings <[email protected]> Cc: David Decotigny <[email protected]>, Cc: David S. Miller <[email protected]>, Cc: Geert Uytterhoeven <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Rasmus Villemoes <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2017-10-19documentation: kernel-api: add more info on bitmap functionsRandy Dunlap1-1/+3
There are some good comments about bitmap operations in lib/bitmap.c and include/linux/bitmap.h, so format them for document generation and pull them into core-api/kernel-api.rst. I converted the "tables" of functions from using tabs to using spaces so that they are more readable in the source file and in the generated output. Signed-off-by: Randy Dunlap <[email protected]> Signed-off-by: Jonathan Corbet <[email protected]>
2017-09-08lib/bitmap.c: make bitmap_parselist() thread-safe and much fasterYury Norov1-12/+6
Current implementation of bitmap_parselist() uses a static variable to save local state while setting bits in the bitmap. It is obviously wrong if we assume execution in multiprocessor environment. Fortunately, it's possible to rewrite this portion of code to avoid using the static variable. It is also possible to set bits in the mask per-range with bitmap_set(), not per-bit, as it is implemented now, with set_bit(); which is way faster. The important side effect of this change is that setting bits in this function from now is not per-bit atomic and less memory-ordered. This is because set_bit() guarantees the order of memory accesses, while bitmap_set() does not. I think that it is the advantage of the new approach, because the bitmap_parselist() is intended to initialise bit arrays, and user should protect the whole bitmap during initialisation if needed. So protecting individual bits looks expensive and useless. Also, other range-oriented functions in lib/bitmap.c don't worry much about atomicity. With all that, setting 2k bits in map with the pattern like 0-2047:128/256 becomes ~50 times faster after applying the patch in my testing environment (arm64 hosted on qemu). The second patch of the series adds the test for bitmap_parselist(). It's not intended to cover all tricky cases, just to make sure that I didn't screw up during rework. Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Yury Norov <[email protected]> Cc: Noam Camus <[email protected]> Cc: Rasmus Villemoes <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: Mauro Carvalho Chehab <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2017-07-10bitmap: optimise bitmap_set and bitmap_clear of a single bitMatthew Wilcox1-4/+4
We have eight users calling bitmap_clear for a single bit and seventeen calling bitmap_set for a single bit. Rather than fix all of them to call __clear_bit or __set_bit, turn bitmap_clear and bitmap_set into inline functions and make this special case efficient. Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Matthew Wilcox <[email protected]> Acked-by: Rasmus Villemoes <[email protected]> Cc: Martin Schwidefsky <[email protected]> Cc: Matthew Wilcox <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>