linux-kernel - Re: [PATCH 4/5] crypto: lib/sha256 - Unroll SHA256 loop 8 times intead of 64

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: <20201020194555.GA3464628@rani.riverdale.lan>
Date:   Tue, 20 Oct 2020 15:45:55 -0400
From:   Arvind Sankar <nivedita@...m.mit.edu>
To:     David Laight <David.Laight@...LAB.COM>
Cc:     'Arvind Sankar' <nivedita@...m.mit.edu>,
        Herbert Xu <herbert@...dor.apana.org.au>,
        "David S. Miller" <davem@...emloft.net>,
        "linux-crypto@...r.kernel.org" <linux-crypto@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 4/5] crypto: lib/sha256 - Unroll SHA256 loop 8 times
 intead of 64

On Tue, Oct 20, 2020 at 02:55:47PM +0000, David Laight wrote:
> From: Arvind Sankar
> > Sent: 20 October 2020 15:07
> > To: David Laight <David.Laight@...LAB.COM>
> > 
> > On Tue, Oct 20, 2020 at 07:41:33AM +0000, David Laight wrote:
> > > From: Arvind Sankar> Sent: 19 October 2020 16:30
> > > > To: Herbert Xu <herbert@...dor.apana.org.au>; David S. Miller <davem@...emloft.net>; linux-
> > > > crypto@...r.kernel.org
> > > > Cc: linux-kernel@...r.kernel.org
> > > > Subject: [PATCH 4/5] crypto: lib/sha256 - Unroll SHA256 loop 8 times intead of 64
> > > >
> > > > This reduces code size substantially (on x86_64 with gcc-10 the size of
> > > > sha256_update() goes from 7593 bytes to 1952 bytes including the new
> > > > SHA256_K array), and on x86 is slightly faster than the full unroll.
> > >
> > > The speed will depend on exactly which cpu type is used.
> > > It is even possible that the 'not unrolled at all' loop
> > > (with the all the extra register moves) is faster on some x86-64 cpu.
> > 
> > Yes, I should have mentioned this was tested on a Broadwell Xeon, at
> > least on that processor, no unrolling is a measurable performance loss.
> > But the hope is that 8x unroll should be generally enough unrolling that
> > 64x is unlikely to speed it up more, and so has no advantage over 8x.
> 
> (I've just looked at the actual code, not just the patch.)
> 
> Yes I doubt the 64x unroll was ever a significant gain.
> Unrolling completely requires a load of register moves/renames;
> probably too many to be 'zero cost'.
> 
> With modern cpu you can often get the loop control instructions
> 'for free' so unrolling just kills the I-cache.
> Some of the cpu have loop buffers for decoded instructions,
> unroll beyond that size and you suddenly get the decoder costs
> hitting you again.
> 
> ...
> > > If you can put SHA256_K[] and W[] into a struct then the
> > > compiler can use the same register to address into both
> > > arrays (using an offset of 64*4 for the second one).
> > > (ie keep the two arrays, not an array of struct).
> > > This should reduce the register pressure slightly.
> > 
> > I can try that, could copy the data in sha256_update() so it's amortized
> > over the whole input.
> 
> Having looked more closely the extra copy needed is probably
> bigger than any saving.
> 

On x86-64 it doesn't make much difference, but it speeds up x86-32 by
around 10% (on long inputs).