linux-kernel - [PATCH v4 0/4] lib: optimize find

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:   Wed, 14 Sep 2022 19:07:26 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Cc:     Yury Norov <yury.norov@...il.com>,
        Alexey Klimov <klimov.linux@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Andy Whitcroft <apw@...onical.com>,
        Catalin Marinas <catalin.marinas@....com>,
        David Laight <David.Laight@...LAB.COM>,
        Dennis Zhou <dennis@...nel.org>,
        Guenter Roeck <linux@...ck-us.net>,
        Kees Cook <keescook@...omium.org>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Valentin Schneider <vschneid@...hat.com>,
        Sven Schnelle <svens@...ux.ibm.com>,
        Russell King <linux@...linux.org.uk>
Subject: [PATCH v4 0/4] lib: optimize find_bit() functions

In the recent discussion, it was noticed that find_next_bit() functions may
be improved by adding wrappers around common __find_next_bit() in .c file.

As suggested by Linus, I tried the meta-programming trick with the
EXPRESSION macro, which is passed from wrapper into find_bit()
helpers:

  #define BIT_FIND_BODY(addr, size, start, EXPRESSION)          \
        BIT_FIND_SETUP(addr, size, start)                       \
        BIT_FIND_FIRST_WORD(addr, size, start, EXPRESSION)      \
        BIT_WORD_LOOP(addr, size, idx, val, EXPRESSION)         \
        return size;                                            \
  found:        BIT_WORD_SWAB(val);                             \
        return min((idx)*BITS_PER_LONG + __ffs(val), size)

  unsigned long _find_next_and_bit(const unsigned long *addr1,
                                 const unsigned long *addr2,
                                 unsigned long size,
                                 unsigned long start)
  { BIT_FIND_BODY(addr, size, start, addr1[idx] & addr2[idx]); }

I appreciated the potential of how the EXPRESSION works, but I don't like
that the resulting macro is constructed from pieces because it makes it
harder to understand what happens behind the ifdefery. Checkpatch isn't
happy as well because the final macro contains 'return' statement; and I
would agree that it's better to avoid it.

I spun the idea one more time, trying to make FIND helper a more or
less standard looking macro.

This new approach saves 10-11K of Image size, and is 15% faster in the
performance benchmark. See the 3rd patch for some statistics.

v1: https://lore.kernel.org/all/20220728161208.865420-2-yury.norov@gmail.com/T/
v2: https://lore.kernel.org/lkml/YwaXvphVpy5A7fSs@yury-laptop/t/
v3: https://lore.kernel.org/all/xhsmhedwnb15r.mognet@vschneid.remote.csb/T/
v4:
 - fix for-loop break condition in FIND_NEXT_BIT;
 - add review tags from Valentin Schneider.

Yury Norov (4):
  lib/find_bit: introduce FIND_FIRST_BIT() macro
  lib/find_bit: create find_first_zero_bit_le()
  lib/find_bit: optimize find_next_bit() functions
  tools: sync find_bit() implementation

 include/linux/find.h       |  46 +++++++---
 lib/find_bit.c             | 178 ++++++++++++++++++++++---------------
 tools/include/linux/find.h |  61 +++----------
 tools/lib/find_bit.c       | 149 ++++++++++++++-----------------
 4 files changed, 220 insertions(+), 214 deletions(-)

-- 
2.34.1