linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v4 00/13] lib/find_bit: fast path for small bitmaps
@ 2021-03-16  1:54 Yury Norov
  2021-03-16  1:54 ` [PATCH 01/13] tools: disable -Wno-type-limits Yury Norov
                   ` (12 more replies)
  0 siblings, 13 replies; 31+ messages in thread
From: Yury Norov @ 2021-03-16  1:54 UTC (permalink / raw)
  To: linux-kernel
  Cc: Yury Norov, linux-m68k, linux-arch, linux-sh, Alexey Klimov,
	Andrew Morton, Andy Shevchenko, Arnd Bergmann, David Sterba,
	Dennis Zhou, Geert Uytterhoeven, Jianpeng Ma, Joe Perches,
	John Paul Adrian Glaubitz, Josh Poimboeuf, Rasmus Villemoes,
	Rich Felker, Stefano Brivio, Wei Yang, Wolfram Sang,
	Yoshinori Sato

Bitmap operations are much simpler and faster in case of small bitmaps
which fit into a single word. In linux/bitmap.c we have a machinery that
allows compiler to replace actual function call with a few instructions
if bitmaps passed into the function are small and their size is known at
compile time.

find_*_bit() API lacks this functionality; but users will benefit from it
a lot. One important example is cpumask subsystem when
NR_CPUS <= BITS_PER_LONG.

v1: https://www.spinics.net/lists/kernel/msg3804727.html
v2: https://www.spinics.net/lists/linux-m68k/msg16945.html
v3: https://www.spinics.net/lists/kernel/msg3837020.html
v4: - move le.h header together with find.h for m68 and sh;
    - preserve small_const_nbits() macro;
    - drop FAST_PATH config option as this series doesn't increase .text,
      instead, it compacts it;
    - add Andy and Rasmus as reviewers of BITMAP API.

Yury Norov (13):
  tools: disable -Wno-type-limits
  tools: bitmap: sync function declarations with the kernel
  arch: rearrange headers inclusion order in asm/bitops for m68k and sh
  lib: introduce BITS_{FIRST,LAST} macro
  tools: sync BITS_MASK macros with the kernel
  lib: extend the scope of small_const_nbits() macro
  tools: sync small_const_nbits() macro with the kernel
  lib: inline _find_next_bit() wrappers
  tools: sync find_next_bit implementation
  lib: add fast path for find_next_*_bit()
  lib: add fast path for find_first_*_bit() and find_last_bit()
  tools: sync lib/find_bit implementation
  MAINTAINERS: Add entry for the bitmap API

 MAINTAINERS                             |  16 ++++
 arch/m68k/include/asm/bitops.h          |   6 +-
 arch/sh/include/asm/bitops.h            |   5 +-
 include/asm-generic/bitops/find.h       | 108 +++++++++++++++++++++---
 include/asm-generic/bitops/le.h         |  38 ++++++++-
 include/asm-generic/bitsperlong.h       |   9 ++
 include/linux/bitmap.h                  |  30 +++----
 include/linux/bitops.h                  |  12 ---
 include/linux/bits.h                    |   6 ++
 include/linux/cpumask.h                 |   8 +-
 include/linux/netdev_features.h         |   2 +-
 include/linux/nodemask.h                |   2 +-
 lib/bitmap.c                            |  26 +++---
 lib/find_bit.c                          |  72 +++-------------
 lib/genalloc.c                          |   8 +-
 tools/include/asm-generic/bitops/find.h |  85 +++++++++++++++++--
 tools/include/asm-generic/bitsperlong.h |   3 +
 tools/include/linux/bitmap.h            |  31 +++----
 tools/include/linux/bits.h              |   6 ++
 tools/lib/bitmap.c                      |  10 +--
 tools/lib/find_bit.c                    |  56 +++++-------
 tools/scripts/Makefile.include          |   1 +
 tools/testing/radix-tree/bitmap.c       |   4 +-
 23 files changed, 340 insertions(+), 204 deletions(-)

-- 
2.25.1


^ permalink raw reply	[flat|nested] 31+ messages in thread

end of thread, other threads:[~2021-04-06 18:15 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-16  1:54 [PATCH v4 00/13] lib/find_bit: fast path for small bitmaps Yury Norov
2021-03-16  1:54 ` [PATCH 01/13] tools: disable -Wno-type-limits Yury Norov
2021-03-16  8:17   ` Rasmus Villemoes
2021-03-16 11:39     ` Andy Shevchenko
2021-03-16  1:54 ` [PATCH 02/13] tools: bitmap: sync function declarations with the kernel Yury Norov
2021-03-16  8:18   ` Rasmus Villemoes
2021-03-16  1:54 ` [PATCH 03/13] arch: rearrange headers inclusion order in asm/bitops for m68k and sh Yury Norov
2021-03-16  1:54 ` [PATCH 04/13] lib: introduce BITS_{FIRST,LAST} macro Yury Norov
2021-03-16  8:35   ` Rasmus Villemoes
2021-03-16 11:42     ` Andy Shevchenko
2021-03-17  5:40       ` Yury Norov
2021-03-17 19:58         ` Rasmus Villemoes
2021-03-17 23:33           ` Yury Norov
2021-03-16  1:54 ` [PATCH 05/13] tools: sync BITS_MASK macros with the kernel Yury Norov
2021-03-16  1:54 ` [PATCH 06/13] lib: extend the scope of small_const_nbits() macro Yury Norov
2021-03-16  8:56   ` Rasmus Villemoes
2021-03-17  4:53     ` Yury Norov
2021-03-16  1:54 ` [PATCH 07/13] tools: sync small_const_nbits() macro with the kernel Yury Norov
2021-03-16  1:54 ` [PATCH 08/13] lib: inline _find_next_bit() wrappers Yury Norov
2021-03-16  1:54 ` [PATCH 09/13] tools: sync find_next_bit implementation Yury Norov
2021-03-16  1:54 ` [PATCH 10/13] lib: add fast path for find_next_*_bit() Yury Norov
2021-03-16  1:54 ` [PATCH 11/13] lib: add fast path for find_first_*_bit() and find_last_bit() Yury Norov
2021-04-06 16:03   ` Guenter Roeck
2021-04-06 18:15     ` Yury Norov
2021-03-16  1:54 ` [PATCH 12/13] tools: sync lib/find_bit implementation Yury Norov
2021-03-16  1:54 ` [PATCH 13/13] MAINTAINERS: Add entry for the bitmap API Yury Norov
2021-03-16 11:45   ` Andy Shevchenko
2021-03-17  4:47     ` Yury Norov
2021-03-17  4:57       ` Joe Perches
2021-03-17  6:40         ` Lukas Bulwahn
2021-03-17 19:29           ` Yury Norov

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).