linux-kernel - [PATCH 0/4] bitops: optimize fns() for more

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date: Thu,  2 May 2024 16:32:00 -0700
From: Yury Norov <yury.norov@...il.com>
To: linux-kernel@...r.kernel.org
Cc: Yury Norov <yury.norov@...il.com>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 0/4] bitops: optimize fns() for more

This series follows up [1].

[1] improves performance by switching from __ffs() + __clear_bit()
in fns() to the equivalent but much faster expression that searches
and clears first N-1 bits:

	while (word && n--)
		word &= word - 1;

We can squeeze out of fns() even more by replacing linear walk over all
the bits in a word with a binary search.

Patch #3 implements it by adding fns8(), fns16(), fns32() and fns64(), 
and patches 1 and 2 are cleanups related to fns().

The last patch creates a MAINTAINERS record for bitops. Currently they
aren't maintained. I add Rasmus and myself as a reviewer and maintainer,
accordingly, just like for bitmaps. Rasmus, please let me know if you
don't want to review it.

[1] https://lore.kernel.org/linux-kernel/20240502092443.6845-2-visitorckw@gmail.com/T/

Yury Norov (4):
  lib: make test_bitops compilable into the kernel image
  bitmap: relax find_nth_bit() limitation on return value
  bitops: squeeze even more out of fns()
  MAINTAINERS: add BITOPS API record

 MAINTAINERS            | 13 +++++++++++++
 include/linux/bitops.h | 42 +++++++++++++++++++++++++++++++++++++-----
 include/linux/find.h   |  2 +-
 lib/Kconfig.debug      |  1 -
 lib/find_bit.c         |  2 +-
 lib/test_bitmap.c      |  4 ++--
 6 files changed, 54 insertions(+), 10 deletions(-)

-- 
2.40.1