linux-kernel - Re: [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-prev] [day] [month] [year] [list]

Message-ID: <YyswUKLcRiuRoUrn@yury-laptop>
Date:   Wed, 21 Sep 2022 08:40:00 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Cc:     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: Re: [PATCH v4 0/4] lib: optimize find_bit() functions

If no other comments, I'll address Andy's comments on formatting and
move it in bitmap-for-next.

Thanks,
Yury

On Wed, Sep 14, 2022 at 07:07:26PM -0700, Yury Norov wrote:
> 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