linux-kernel - Re: [PATCH 0/2] x86/asm/bitops: optimize ff{s,z} functions for constant expressions

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAMZ6RqKD9O8OHVUGCOYK1BXm7SCOkWbxCsSb=6jjfzgKn61JEw@mail.gmail.com>
Date:   Wed, 11 May 2022 08:24:34 +0900
From:   Vincent MAILHOL <mailhol.vincent@...adoo.fr>
To:     Nick Desaulniers <ndesaulniers@...gle.com>
Cc:     Thomas Gleixner <tglx@...utronix.de>,
        Ingo Molnar <mingo@...hat.com>, Borislav Petkov <bp@...en8.de>,
        Dave Hansen <dave.hansen@...ux.intel.com>, x86@...nel.org,
        "H . Peter Anvin" <hpa@...or.com>,
        Nathan Chancellor <nathan@...nel.org>,
        Tom Rix <trix@...hat.com>, linux-kernel@...r.kernel.org,
        llvm@...ts.linux.dev
Subject: Re: [PATCH 0/2] x86/asm/bitops: optimize ff{s,z} functions for
 constant expressions

On Wed. 11 May 2022 at 07:14, Nick Desaulniers <ndesaulniers@...gle.com> wrote:
> On Tue, May 10, 2022 at 7:26 AM Vincent Mailhol
> <mailhol.vincent@...adoo.fr> wrote:
> >
> > The compilers provides some builtin expression equivalent to the
> > ffs(), __ffs() and ffz() function of the kernel. The kernel uses
> > optimized assembly which produces better code than the builtin
> > functions. However, such assembly code can not be optimized when used
> > on constant expression.
> >
> > This series relies on __builtin_constant_p to select the optimal solution:
> >
> >   * use kernel assembly for non constant expressions
> >
> >   * use compiler's __builtin function for constant expressions.
> >
> > I also think that the fls() and fls64() can be optimized in a similar
> > way, using __builtin_ctz() and __builtin_ctzll() but it is a bit less
> > trivial so I want to focus on this series first. If it get accepted, I
> > will then work on those two additionnal function.
> >
> >
> > ** Statistics **
> >
> > On a allyesconfig, before applying this series, I get:
> >
> > | $ objdump -d vmlinux.o | grep bsf | wc -l
> > | 1081
> >
> > After applying this series:
> >
> > | $ objdump -d vmlinux.o | grep bsf | wc -l
> > | 792
> >
> > So, roughly 26.7% of the call to either ffs() or __ffs() were using
> > constant expression and can be optimized (I did not produce the
> > figures for ffz()).
>
> These stats are interesting; consider putting them on patch 1/2 commit
> message though (in addition to the cover letter). (Sending thoughts on
> 1/2 next).

The fact is that patch 1/2 changes ffs() and patch 2/2 changes
__ffs(). For v2, I will run the stats on each patch separately in
order not to mix the results.

> >
> > (tests done on linux v5.18-rc5 x86_64 using GCC 11.2.1)
>
> Here's the same measure of x86_64 allyesconfig (./scripts/config -d
> CONFIG_HINIC) at 9be9ed2612b5aedb52a2c240edb1630b6b743cb6 with ToT
> LLVM (~clang-15):
>
> Before:
> $ objdump -d vmlinux.o | grep bsf | wc -l
> 1454
>
> After:
> $ objdump -d vmlinux.o | grep bsf | wc -l
> 1070
>
> -26.4% :)

Roughly same ratio. I am just surprise that the absolute number
are different:

  * GCC before: 1081, after 792
  * clang before 1454, after 1070

I wonder why clang produces more bsf instructions than GCC?

Also, on a side note, I am not the first one to realize that
__builtin_ffs() is able to optimize the constant variable. Some
people already used it to locally:

| $ git grep __builtin_ffs | wc -l
| 80

> >
> >
> > Vincent Mailhol (2):
> >   x86/asm/bitops: ffs: use __builtin_ffs to evaluate constant
> >     expressions
> >   x86/asm/bitops: __ffs,ffz: use __builtin_ctzl to evaluate constant
> >     expressions
> >
> >  arch/x86/include/asm/bitops.h | 65 +++++++++++++++++++++--------------
> >  1 file changed, 40 insertions(+), 25 deletions(-)
> >
> > --
> > 2.35.1
> >
>
>
> --
> Thanks,
> ~Nick Desaulniers