linux.git/tools/include/linux/bitmap.h, branch v5.15.185

tools: move alignment-related macros to new

2024-09-04T11:23:37+00:00

commit 10a04ff09bcc39e0044190ffe9f00f998f13647c upstream.

Currently, tools have *ALIGN*() macros scattered across the unrelated
headers, as there are only 3 of them and they were added separately
each time on an as-needed basis.
Anyway, let's make it more consistent with the kernel headers and allow
using those macros outside of the mentioned headers. Create
 inside the tools/ folder and include it where needed.

Signed-off-by: Yury Norov 
Signed-off-by: Alexander Lobakin 
Signed-off-by: David S. Miller 
Signed-off-by: Greg Kroah-Hartman

bitmap: introduce generic optimized bitmap_size()

2024-09-04T11:23:16+00:00

commit a37fbe666c016fd89e4460d0ebfcea05baba46dc upstream.

The number of times yet another open coded
`BITS_TO_LONGS(nbits) * sizeof(long)` can be spotted is huge.
Some generic helper is long overdue.

Add one, bitmap_size(), but with one detail.
BITS_TO_LONGS() uses DIV_ROUND_UP(). The latter works well when both
divident and divisor are compile-time constants or when the divisor
is not a pow-of-2. When it is however, the compilers sometimes tend
to generate suboptimal code (GCC 13):

48 83 c0 3f          	add    $0x3f,%rax
48 c1 e8 06          	shr    $0x6,%rax
48 8d 14 c5 00 00 00 00	lea    0x0(,%rax,8),%rdx

%BITS_PER_LONG is always a pow-2 (either 32 or 64), but GCC still does
full division of `nbits + 63` by it and then multiplication by 8.
Instead of BITS_TO_LONGS(), use ALIGN() and then divide by 8. GCC:

8d 50 3f             	lea    0x3f(%rax),%edx
c1 ea 03             	shr    $0x3,%edx
81 e2 f8 ff ff 1f    	and    $0x1ffffff8,%edx

Now it shifts `nbits + 63` by 3 positions (IOW performs fast division
by 8) and then masks bits[2:0]. bloat-o-meter:

add/remove: 0/0 grow/shrink: 20/133 up/down: 156/-773 (-617)

Clang does it better and generates the same code before/after starting
from -O1, except that with the ALIGN() approach it uses %edx and thus
still saves some bytes:

add/remove: 0/0 grow/shrink: 9/133 up/down: 18/-538 (-520)

Note that we can't expand DIV_ROUND_UP() by adding a check and using
this approach there, as it's used in array declarations where
expressions are not allowed.
Add this helper to tools/ as well.

Reviewed-by: Przemek Kitszel 
Acked-by: Yury Norov 
Signed-off-by: Alexander Lobakin 
Signed-off-by: David S. Miller 
Signed-off-by: Greg Kroah-Hartman

tools: rename bitmap_alloc() to bitmap_zalloc()

2021-09-08T18:50:27+00:00

Rename bitmap_alloc() to bitmap_zalloc() in tools to follow the bitmap API
in the kernel.

No functional changes intended.

Link: https://lkml.kernel.org/r/20210814211713.180533-14-yury.norov@gmail.com
Signed-off-by: Andy Shevchenko 
Signed-off-by: Yury Norov 
Suggested-by: Yury Norov 
Acked-by: Yury Norov 
Tested-by: Wolfram Sang 
Acked-by: Jiri Olsa 
Cc: Alexander Lobakin 
Cc: Alexey Klimov 
Cc: Dennis Zhou 
Cc: Ulf Hansson 
Cc: Will Deacon 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

tools lib: Adopt bitmap_intersects() operation from the kernel sources

2021-06-30T18:28:00+00:00

Adopt bitmap_intersects() routine that tests whether bitmaps bitmap1 and
bitmap2 intersects. This routine will be used during thread masks
initialization.

Signed-off-by: Alexey Bayduraev 
Acked-by: Andi Kleen 
Acked-by: Namhyung Kim 
Cc: Adrian Hunter 
Cc: Alexander Antonov 
Cc: Alexander Shishkin 
Cc: Alexei Budankov 
Cc: Jiri Olsa 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Riccardo Mancini 
Link: http://lore.kernel.org/lkml/f75aa738d8ff8f9cffd7532d671f3ef3deb97a7c.1625065643.git.alexey.v.bayduraev@linux.intel.com
Signed-off-by: Arnaldo Carvalho de Melo

tools: sync small_const_nbits() macro with the kernel

2021-05-07T02:24:12+00:00

Sync implementation with the kernel and move the macro from
tools/include/linux/bitmap.h to tools/include/asm-generic/bitsperlong.h

Link: https://lkml.kernel.org/r/20210401003153.97325-7-yury.norov@gmail.com
Signed-off-by: Yury Norov 
Acked-by: Rasmus Villemoes 
Cc: Alexey Klimov 
Cc: Andy Shevchenko 
Cc: Arnd Bergmann 
Cc: David Sterba 
Cc: Dennis Zhou 
Cc: Geert Uytterhoeven 
Cc: Jianpeng Ma 
Cc: Joe Perches 
Cc: John Paul Adrian Glaubitz 
Cc: Josh Poimboeuf 
Cc: Rich Felker 
Cc: Stefano Brivio 
Cc: Wei Yang 
Cc: Wolfram Sang 
Cc: Yoshinori Sato 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

tools: sync BITMAP_LAST_WORD_MASK() macro with the kernel

2021-05-07T02:24:11+00:00

Kernel version generates better code.

Link: https://lkml.kernel.org/r/20210401003153.97325-4-yury.norov@gmail.com
Signed-off-by: Yury Norov 
Acked-by: Rasmus Villemoes 
Cc: Alexey Klimov 
Cc: Andy Shevchenko 
Cc: Arnd Bergmann 
Cc: David Sterba 
Cc: Dennis Zhou 
Cc: Geert Uytterhoeven 
Cc: Jianpeng Ma 
Cc: Joe Perches 
Cc: John Paul Adrian Glaubitz 
Cc: Josh Poimboeuf 
Cc: Rich Felker 
Cc: Stefano Brivio 
Cc: Wei Yang 
Cc: Wolfram Sang 
Cc: Yoshinori Sato 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

tools: bitmap: sync function declarations with the kernel

2021-05-07T02:24:11+00:00

Some functions in tools/include/linux/bitmap.h declare nbits as int.  In
the kernel nbits is declared as unsigned int.

Link: https://lkml.kernel.org/r/20210401003153.97325-3-yury.norov@gmail.com
Signed-off-by: Yury Norov 
Acked-by: Rasmus Villemoes 
Cc: Alexey Klimov 
Cc: Andy Shevchenko 
Cc: Arnd Bergmann 
Cc: David Sterba 
Cc: Dennis Zhou 
Cc: Geert Uytterhoeven 
Cc: Jianpeng Ma 
Cc: Joe Perches 
Cc: John Paul Adrian Glaubitz 
Cc: Josh Poimboeuf 
Cc: Rich Felker 
Cc: Stefano Brivio 
Cc: Wei Yang 
Cc: Wolfram Sang 
Cc: Yoshinori Sato 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

tools bitmap: Implement bitmap_equal() operation at bitmap API

2020-01-06T14:46:04+00:00

Extend tools bitmap API with bitmap_equal() implementation.

The implementation has been derived from the kernel.

Extend tools bitmap API with bitmap_free() implementation for symmetry
with bitmap_alloc() function.

Signed-off-by: Alexey Budankov 
Acked-by: Jiri Olsa 
Cc: Alexander Shishkin 
Cc: Andi Kleen 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Link: http://lore.kernel.org/lkml/43757993-0b28-d8af-a6c7-ede12e3a6877@linux.intel.com
Signed-off-by: Arnaldo Carvalho de Melo

xarray: Add XArray unconditional store operations

2018-10-21T14:45:57+00:00

xa_store() differs from radix_tree_insert() in that it will overwrite an
existing element in the array rather than returning an error.  This is
the behaviour which most users want, and those that want more complex
behaviour generally want to use the xas family of routines anyway.

For memory allocation, xa_store() will first attempt to request memory
from the slab allocator; if memory is not immediately available, it will
drop the xa_lock and allocate memory, keeping a pointer in the xa_state.
It does not use the per-CPU cache, although those will continue to exist
until all radix tree users are converted to the xarray.

This patch also includes xa_erase() and __xa_erase() for a streamlined
way to store NULL.  Since there is no need to allocate memory in order
to store a NULL in the XArray, we do not need to trouble the user with
deciding what memory allocation flags to use.

Signed-off-by: Matthew Wilcox

tools: introduce test_and_clear_bit

2018-08-22T14:48:36+00:00

We have test_and_set_bit but not test_and_clear_bit.  Add it.

Signed-off-by: Peter Xu 
Signed-off-by: Paolo Bonzini