linux-kernel - Re: [PATCH] find_bit: Micro-optimise find_next_*

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: <20161224064335.GA7280@yury-N73SV>
Date:   Sat, 24 Dec 2016 12:13:35 +0530
From:   Yury Norov <ynorov@...iumnetworks.com>
To:     Matthew Wilcox <mawilcox@...uxonhyperv.com>
CC:     Yury Norov <yury.norov@...il.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        George Spelvin <linux@...izon.com>,
        Akinobu Mita <akinobu.mita@...il.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Andrew Morton <akpm@...ux-foundation.org>,
        <linux-kernel@...r.kernel.org>,
        Matthew Wilcox <mawilcox@...rosoft.com>
Subject: Re: [PATCH] find_bit: Micro-optimise find_next_*_bit

Hi Mattew,

On Fri, Dec 23, 2016 at 09:20:03AM -0800, Matthew Wilcox wrote:
> From: Matthew Wilcox <mawilcox@...rosoft.com>
> 
> This saves 20 bytes on my x86-64 build, mostly due to alignment
> considerations ... I think it actually saves about five bytes of
> instructions.  There's really two parts to this commit.  First, the
> first half of the test: (!nbits || start >= nbits) is trivially a subset
> of the second half, since nbits and start are both unsigned.

Yes... It's obvious... when you point it out.

ARM64 GCC compiler didn't notice it as well as me:

37 0000000000000070 <find_next_bit>:
38   70:   eb1f003f        cmp     x1, xzr
39   74:   fa421020        ccmp    x1, x2, #0x0, ne
40   78:   54000088        b.hi    88 <find_next_bit+0x18>
41   7c:   aa0103e0        mov     x0, x1
42   80:   d65f03c0        ret
43   84:   d503201f        nop
44   88:   a9bf7bfd        stp     x29, x30, [sp,#-16]!
45   8c:   910003fd        mov     x29, sp
46   90:   d2800003        mov     x3, #0x0 // #0
47   94:   97ffffdb        bl      0 <_find_next_bit.part.0>
48   98:   a8c17bfd        ldp     x29, x30, [sp],#16
49   9c:   d65f03c0        ret

> Second,
> while looking at the disassembly, I noticed that GCC was predicting the
> branch taken.  Since this is a failure case, it's clearly the less likely
> of the two branches, so add an unlikely() to override GCC's heuristics.
> 
> Signed-off-by: Matthew Wilcox <mawilcox@...rosoft.com>
> ---
>  lib/find_bit.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 18072ea9c20e..7d4a681d625f 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -33,7 +33,7 @@ static unsigned long _find_next_bit(const unsigned long *addr,
>  {
>  	unsigned long tmp;
>  
> -	if (!nbits || start >= nbits)
> +	if (unlikely(start >= nbits))
>  		return nbits;
>  
>  	tmp = addr[start / BITS_PER_LONG] ^ invert;
> -- 
> 2.11.0


There's also _find_next_bit_le() with same code. I think it should be
also patched.

Acked-by: Yury Norov <ynorov@...iumnetworks.com>