linux-kernel - RE: [PATCH v4 05/11] arm64: csum: Disable KASAN for do

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: <cdfcda98bce54632953cae5e05305dc7@AcuMS.aculab.com>
Date:   Fri, 24 Apr 2020 13:04:04 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Robin Murphy' <robin.murphy@....com>,
        Will Deacon <will@...nel.org>,
        "Mark Rutland" <mark.rutland@....com>
CC:     "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "linux-arch@...r.kernel.org" <linux-arch@...r.kernel.org>,
        "kernel-team@...roid.com" <kernel-team@...roid.com>,
        Michael Ellerman <mpe@...erman.id.au>,
        Peter Zijlstra <peterz@...radead.org>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Segher Boessenkool <segher@...nel.crashing.org>,
        Christian Borntraeger <borntraeger@...ibm.com>,
        Luc Van Oostenryck <luc.vanoostenryck@...il.com>,
        Arnd Bergmann <arnd@...db.de>,
        Peter Oberparleiter <oberpar@...ux.ibm.com>,
        Masahiro Yamada <masahiroy@...nel.org>,
        Nick Desaulniers <ndesaulniers@...gle.com>
Subject: RE: [PATCH v4 05/11] arm64: csum: Disable KASAN for do_csum()

From: Robin Murphy
> Sent: 24 April 2020 12:01
> On 2020-04-24 10:41 am, David Laight wrote:
> > From: Robin Murphy
> >> Sent: 22 April 2020 12:02
> > ..
> >> Sure - I have a nagging feeling that it could still do better WRT
> >> pipelining the loads anyway, so I'm happy to come back and reconsider
> >> the local codegen later. It certainly doesn't deserve to stand in the
> >> way of cross-arch rework.
> >
> > How fast does that loop actually run?
> 
> I've not characterised it in detail, but faster than any of the other
> attempts so far ;)
...
> The aim here is to minimise load bandwidth - most Arm cores can slurp 16
> bytes from L1 in a single load as quickly as any smaller amount, so
> nibbling away in little 32-bit chunks would result in up to 4x more load
> cycles.

The x86 'problem' is that 'adc' takes two clocks and the carry
flag 'register chain' means you can only sum 4 bytes/clock regardless
of the memory accesses.

> Yes, the C code looks ridiculous, but the other trick is that
> most of those operations don't actually exist. Since a __uint128_t is
> really backed by any two 64-bit GPRs - or if you're careful, one 64-bit
> GPR and the carry flag - all those shifts and rotations are in fact
> resolved by register allocation, so what we end up with is a very neat
> loop of essentially just loads and 64-bit accumulation:
> 
> ...
>   138:   a94030c3        ldp     x3, x12, [x6]
>   13c:   a9412cc8        ldp     x8, x11, [x6, #16]
>   140:   a94228c4        ldp     x4, x10, [x6, #32]
>   144:   a94324c7        ldp     x7, x9, [x6, #48]
>   148:   ab03018d        adds    x13, x12, x3
>   14c:   510100a5        sub     w5, w5, #0x40
>   150:   9a0c0063        adc     x3, x3, x12
>   154:   ab08016c        adds    x12, x11, x8
>   158:   9a0b0108        adc     x8, x8, x11
>   15c:   ab04014b        adds    x11, x10, x4
>   160:   9a0a0084        adc     x4, x4, x10
>   164:   ab07012a        adds    x10, x9, x7
>   168:   9a0900e7        adc     x7, x7, x9
>   16c:   ab080069        adds    x9, x3, x8
>   170:   9a080063        adc     x3, x3, x8
>   174:   ab070088        adds    x8, x4, x7
>   178:   9a070084        adc     x4, x4, x7
>   17c:   910100c6        add     x6, x6, #0x40
>   180:   ab040067        adds    x7, x3, x4
>   184:   9a040063        adc     x3, x3, x4
>   188:   ab010064        adds    x4, x3, x1
>   18c:   9a030023        adc     x3, x1, x3
>   190:   710100bf        cmp     w5, #0x40
>   194:   aa0303e1        mov     x1, x3
>   198:   54fffd0c        b.gt    138 <do_csum+0xd8>
> ...
> 
> Instruction-wise, that's about as good as it can get short of
> maintaining multiple accumulators and moving the pairwise folding out of
> the loop. The main thing that I think is still left on the table is that
> the load-to-use distances are pretty short and there's clearly scope to
> spread out and amortise the load cycles better, which stands to benefit
> both big and little cores.

I realised most of the C would disappear - just hard to see what
the result would be.
Looking at the above there are 8 (64bit) loads and 16 adds.
(Plus 2 adds for the loop control, should only need one!
and a spare register move.)
Without multiple carry flags the best you are going to get
is one add instruction and one 'save the carry flag' instruction
for each 'word'.
The thing then is to arrange the code to avoid register dependency
chains so that the instructions can run in parallel.
I think you lose at the bottom of the above when you add to
the global sum - might be faster with 2 sums.
Actually trying to do one load and 4 adds every clock might
be possible - if the cpu can execute them.
But that would require a horrid interleaved loop.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)