cpumask: add cpumask_weight_andnot()

Similarly to cpumask_weight_and(), cpumask_weight_andnot() is a handy
helper that may help to avoid creating an intermediate mask just to
calculate number of bit

cpumask: add cpumask_weight_andnot()

Similarly to cpumask_weight_and(), cpumask_weight_andnot() is a handy
helper that may help to avoid creating an intermediate mask just to
calculate number of bits that set in a 1st given mask, and clear in 2nd
one.

Signed-off-by: Yury Norov <[email protected]>
Reviewed-by: Jacob Keller <[email protected]>
Signed-off-by: Paolo Abeni <[email protected]>

show more ...

bitmap: move bitmap_*_region() functions to bitmap.h

Now that bitmap_*_region() functions are implemented as thin wrappers
around others, it's worth to move them to the header, as it opens room
for

bitmap: move bitmap_*_region() functions to bitmap.h

Now that bitmap_*_region() functions are implemented as thin wrappers
around others, it's worth to move them to the header, as it opens room
for compile-time optimizations.

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
CC: Greg Kroah-Hartman <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: drop _reg_op() function

Now that all _reg_op() users are switched to alternative functions,
_reg_op() machinery is not needed anymore.

CC: Andy Shevchenko <[email protected]

bitmap: drop _reg_op() function

Now that all _reg_op() users are switched to alternative functions,
_reg_op() machinery is not needed anymore.

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()

_reg_op(REG_OP_ISFREE) can be trivially replaced with find_next_bit().
Doing that opens room for potential small_const_nbits() optimizatio

bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()

_reg_op(REG_OP_ISFREE) can be trivially replaced with find_next_bit().
Doing that opens room for potential small_const_nbits() optimization.

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: replace _reg_op(REG_OP_RELEASE) with bitmap_clear()

_reg_op(REG_OP_RELEASE) duplicates bitmap_clear().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <linux@ra

bitmap: replace _reg_op(REG_OP_RELEASE) with bitmap_clear()

_reg_op(REG_OP_RELEASE) duplicates bitmap_clear().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: replace _reg_op(REG_OP_ALLOC) with bitmap_set()

_reg_op(REG_OP_ALLOC) duplicates bitmap_set().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <linux@rasmusvill

bitmap: replace _reg_op(REG_OP_ALLOC) with bitmap_set()

_reg_op(REG_OP_ALLOC) duplicates bitmap_set().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: fix opencoded bitmap_allocate_region()

bitmap_find_region() opencodes bitmap_allocate_region().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <linux@rasmusvil

bitmap: fix opencoded bitmap_allocate_region()

bitmap_find_region() opencodes bitmap_allocate_region().

CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: align __reg_op() wrappers with modern coding style

Fix comments so that scripts/kernel-doc doesn't warn, and fix for-loop
stype in bitmap_find_free_region().

CC: Rasmus Villemoes <linux@ras

bitmap: align __reg_op() wrappers with modern coding style

Fix comments so that scripts/kernel-doc doesn't warn, and fix for-loop
stype in bitmap_find_free_region().

CC: Rasmus Villemoes <[email protected]>
Suggested-by: Andy Shevchenko <[email protected]>
Reviewed-by: Andy Shevchenko <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

lib/bitmap: split-out string-related operations to a separate files

lib/bitmap.c and corresponding include/linux/bitmap.h are intended to
hold functions related to operations on bitmaps, like bitmap

lib/bitmap: split-out string-related operations to a separate files

lib/bitmap.c and corresponding include/linux/bitmap.h are intended to
hold functions related to operations on bitmaps, like bitmap_shift or
bitmap_set. Historically, some string-related operations like
bitmap_parse are also reside in lib/bitmap.c.

Now that the subsystem evolves, string-related bitmap operations became a
significant part of the file. Because they are quite different from the
other bitmap functions by nature, it's worth to split them to a separate
source/header files.

CC: Andrew Morton <[email protected]>
CC: Andy Shevchenko <[email protected]>
CC: Rasmus Villemoes <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: Remove dead code, i.e. bitmap_copy_le()

Besides the fact it's not used anywhere it should be implemented
differently, i.e. via helpers from linux/byteorder/generic.h.
Yet the helpers themsel

bitmap: Remove dead code, i.e. bitmap_copy_le()

Besides the fact it's not used anywhere it should be implemented
differently, i.e. via helpers from linux/byteorder/generic.h.
Yet the helpers themselves need to be introduced first.

Also note, the function lacks of the test cases, they must be provided.

Hence, drop the current dead code for good.

Signed-off-by: Andy Shevchenko <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

bitmap: Fix a typo ("identify map")

A map in which each element is mapped to itself is called an "identity
map".

Signed-off-by: Jonathan Neuschäfer <[email protected]>
Reviewed-by: Andy Shevche

bitmap: Fix a typo ("identify map")

A map in which each element is mapped to itself is called an "identity
map".

Signed-off-by: Jonathan Neuschäfer <[email protected]>
Reviewed-by: Andy Shevchenko <[email protected]>
Signed-off-by: Yury Norov <[email protected]>

show more ...

lib/bitmap: drop optimization of bitmap_{from,to}_arr64

bitmap_{from,to}_arr64() optimization is overly optimistic on 32-bit LE
architectures when it's wired to bitmap_copy_clear_tail().

bitmap_cop

lib/bitmap: drop optimization of bitmap_{from,to}_arr64

bitmap_{from,to}_arr64() optimization is overly optimistic on 32-bit LE
architectures when it's wired to bitmap_copy_clear_tail().

bitmap_copy_clear_tail() takes care of unused bits in the bitmap up to
the next word boundary. But on 32-bit machines when copying bits from
bitmap to array of 64-bit words, it's expected that the unused part of
a recipient array must be cleared up to 64-bit boundary, so the last 4
bytes may stay untouched when nbits % 64 <= 32.

While the copying part of the optimization works correct, that clear-tail
trick makes corresponding tests reasonably fail:

test_bitmap: bitmap_to_arr64(nbits == 1): tail is not safely cleared: 0xa5a5a5a500000001 (must be 0x0000000000000001)

Fix it by removing bitmap_{from,to}_arr64() optimization for 32-bit LE
arches.

Reported-by: Guenter Roeck <[email protected]>
Link: https://lore.kernel.org/lkml/[email protected]/
Fixes: 0a97953fd221 ("lib: add bitmap_{from,to}_arr64")
Signed-off-by: Yury Norov <[email protected]>
Tested-by: Guenter Roeck <[email protected]>
Reviewed-by: Andy Shevchenko <[email protected]>
Reviewed-by: Alexander Lobakin <[email protected]>

show more ...

lib/bitmap: remove bitmap_ord_to_pos

Now that we have find_nth_bit(), we can drop bitmap_ord_to_pos().

Signed-off-by: Yury Norov <[email protected]>

lib/bitmap: add bitmap_weight_and()

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);
weig

lib/bitmap: add bitmap_weight_and()

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 <[email protected]>

show more ...

lib/bitmap: don't call __bitmap_weight() in kernel code

__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(

lib/bitmap: don't call __bitmap_weight() in kernel code

__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 <[email protected]>

show more ...

lib/bitmap: change type of bitmap_weight to unsigned long

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

lib/bitmap: change type of bitmap_weight to unsigned long

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]>

show more ...

lib/bitmap: change return types to bool where appropriate

Some bitmap functions return boolean results in int variables. Fix it
by changing return types to bool.

Signed-off-by: Yury Norov <yury.nor

lib/bitmap: change return types to bool where appropriate

Some bitmap functions return boolean results in int variables. Fix it
by changing return types to bool.

Signed-off-by: Yury Norov <[email protected]>

show more ...

lib/bitmap: fix off-by-one in bitmap_to_arr64()

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 p

lib/bitmap: fix off-by-one in bitmap_to_arr64()

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]>

show more ...

bitmap: Fix return values to be unsigned

Both nodemask and bitmap routines had mixed return values that provided
potentially signed return values that could never happen. This was
leading to the com

bitmap: Fix return values to be unsigned

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]>

show more ...

lib: add bitmap_{from,to}_arr64

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 co

lib: add bitmap_{from,to}_arr64

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]>

show more ...

lib/bitmap.c make bitmap_print_bitmask_to_buf parseable

The documentation of such function is not on a proper ReST format,
as reported by Sphinx:

Documentation/core-api/kernel-api:81: ./lib/bit

lib/bitmap.c make bitmap_print_bitmask_to_buf parseable

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]>

show more ...

lib: bitmap: fix many kernel-doc warnings

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

lib: bitmap: fix many kernel-doc warnings

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]>

show more ...

lib: bitmap: Introduce node-aware alloc API

Expose new node-aware API for bitmap allocation:
bitmap_alloc_node() / bitmap_zalloc_node().

Signed-off-by: Tariq Toukan <[email protected]>
Reviewed-by:

lib: bitmap: Introduce node-aware alloc API

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]>

show more ...

bitmap: extend comment to bitmap_print_bitmask/list_to_buf

Extend comment to new function to warn potential users about caveats.

Signed-off-by: Yury Norov <[email protected]>
Signed-off-by: Barr

bitmap: extend comment to bitmap_print_bitmask/list_to_buf

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]>

show more ...

cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask and list

The existing cpumap_print_to_pagebuf() is used by cpu topology and other
drivers to export hexadecimal bitmask a

cpumask: introduce cpumap_print_list/bitmask_to_buf to support large bitmask 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]>

show more ...