linux-kernel - Re: [RFC 8/8] bitops: prevent compiler inline decision distortion

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]

Date:   Wed, 16 May 2018 07:09:46 -0700
From:   Kees Cook <keescook@...omium.org>
To:     Nadav Amit <namit@...are.com>
Cc:     LKML <linux-kernel@...r.kernel.org>,
        Nadav Amit <nadav.amit@...il.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Ingo Molnar <mingo@...hat.com>,
        "H. Peter Anvin" <hpa@...or.com>, X86 ML <x86@...nel.org>
Subject: Re: [RFC 8/8] bitops: prevent compiler inline decision distortion

On Tue, May 15, 2018 at 7:11 AM, Nadav Amit <namit@...are.com> wrote:
> There are several places in the kernel in which there is a condition
> that is based on whether the input is known to be constant in
> compilation time. If it is, there are complex computations, which only
> take place during compilation time.

What we found while rewriting the min()/max() defines was that GCC's
__builtin_choose_expr() evaluates constant expressions, not the wider
possibility of constant values. And the older the GCC the less
__builtin_constant_p() would resolve to a constant expression, which
would force __builtin_choose_expr() along the "non constant" path.

> Although this scheme works correctly, when GCC computes the expected
> cost of this code in time and size, it disregards the fact that the
> computations of the "constant" case will not take place during runtime
> for the non-constant case. The cost of these functions is considered to
> be much higher.  As a result, inline and branching decisions of the
> compiler are distorted. Specifically, functions are less likely to be
> inlined due to their preserved big size and execution time.
>
> One of this cases is test_bit() which performs some computations for
> constant inputs.
>
> The solution is to use __builtin_choose_expr() to detect whether the
> input is constant instead of a C condition. GCC evaluates the builtin
> earlier, which allows it to improve code-generation decisions.

In the case of test_bit(), I *think* all the optimization-desired
cases are already only constant expressions, so I think this is safe,
but I wouldn't want to do this generally for uses of
__builtin_constant_p().

-Kees

>
> This patch allows function such as bitmap_pos_to_ord() to be inlined.
> Its overall effect on size:
>
>    text    data     bss     dec     hex filename
> 18149165 10064176 2936832 31150173 1db505d ./vmlinux before
> 18149210 10064048 2936832 31150090 1db500a ./vmlinux after (-83)
>
> Static text symbols:
> Before: 39643
> After:  39632   (-11)
>
> Cc: Thomas Gleixner <tglx@...utronix.de>
> Cc: Ingo Molnar <mingo@...hat.com>
> Cc: "H. Peter Anvin" <hpa@...or.com>
> Cc: x86@...nel.org
>
> Signed-off-by: Nadav Amit <namit@...are.com>
> ---
>  arch/x86/include/asm/bitops.h | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/arch/x86/include/asm/bitops.h b/arch/x86/include/asm/bitops.h
> index 9f645ba57dbb..f1cb1c9125a9 100644
> --- a/arch/x86/include/asm/bitops.h
> +++ b/arch/x86/include/asm/bitops.h
> @@ -349,10 +349,10 @@ static __always_inline bool variable_test_bit(long nr, volatile const unsigned l
>  static bool test_bit(int nr, const volatile unsigned long *addr);
>  #endif
>
> -#define test_bit(nr, addr)                     \
> -       (__builtin_constant_p((nr))             \
> -        ? constant_test_bit((nr), (addr))      \
> -        : variable_test_bit((nr), (addr)))
> +#define test_bit(nr, addr)                                     \
> +       __builtin_choose_expr(__builtin_constant_p((nr)),       \
> +               constant_test_bit((nr), (addr)),                \
> +               variable_test_bit((nr), (addr)))
>
>  /**
>   * __ffs - find first set bit in word
> --
> 2.17.0
>



-- 
Kees Cook
Pixel Security