linux-kernel - Re: [RFC 0/3] x86: Patchable constants

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CA+55aFxJO7kDNp6wRnU58Z6-sPbK1SqdzpgLBTAe54mdPjnd=g@mail.gmail.com>
Date:   Wed, 7 Feb 2018 09:01:42 -0800
From:   Linus Torvalds <torvalds@...ux-foundation.org>
To:     "Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>
Cc:     "the arch/x86 maintainers" <x86@...nel.org>,
        Tom Lendacky <thomas.lendacky@....com>,
        Peter Zijlstra <peterz@...radead.org>,
        Dave Hansen <dave.hansen@...el.com>,
        Andy Lutomirski <luto@...nel.org>,
        Borislav Petkov <bp@...e.de>, linux-mm <linux-mm@...ck.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Peter Anvin <hpa@...or.com>
Subject: Re: [RFC 0/3] x86: Patchable constants

On Wed, Feb 7, 2018 at 6:59 AM, Kirill A. Shutemov
<kirill.shutemov@...ux.intel.com> wrote:
> This patchset introduces concept of patchable constants: constant values
> that can be adjusted at boot-time in response to system configuration or
> user input (kernel command-line).
>
> Patchable constants can replace variables that never changes at runtime
> (only at boot-time), but used in very hot path.

So I actually wanted something very close to this, but I think your
approach is much too simplistic.

You force all constants into a register, which means that the
resulting code is always going to be very far from non-optimal.

You also force a big "movabsq" instruction, which really is huge, and
almost never needed. Together with the "use a register", it just makes
for big code.

What I wanted was something that can take things like a shift by a
variable that is set once, and turn it into a shift by a boot-time
constant. Which means that you literally end up patching the 8-bit
immediate in the shift instruction itself.

In particular, was looking at the dcache hashing code, and (to quote
an old email of mine), what I wanted was to simplify the run-time
constant part of this:

│ mov $0x20,%ecx
│ sub 0xaf8bd5(%rip),%ecx # ffffffff81d34600 <d_hash_shift>
│ mov 0x8(%rsi),%r9
│ add %r14d,%eax
│ imul $0x9e370001,%eax,%eax
│ shr %cl,%eax

and it was the expression "32-d_hash_shift" that is really a constant,
and that sequence of

│ mov $0x20,%ecx
│ sub 0xaf8bd5(%rip),%ecx # ffffffff81d34600 <d_hash_shift>
│ shr %cl,%eax

should be just a single

│ shr $CONSTANT,%eax

at runtime.

Look - much smaller code, and register %rcx isn't used at all. And no
D$ miss on loading that constant (that is a constant depending on
boot-time setup only).

It's rather more complex, but it actually gives a much bigger win. The
code itself will be much better, and smaller.

The *infrastructure* for the code gets pretty hairy, though.

The good news is that the patch already existed to at least _some_
degree. Peter Anvin did it about 18 months ago.

It was not really pursued all the way because it *is* a lot of extra
complexity, and I think there was some other hold-up, but he did have
skeleton code for the actual replacement.

There was a thread on the x86 arch list with the subject line

    Disgusting pseudo-self-modifying code idea: "variable constants"

but I'm unable to actually find the patch. I know there was at least a
vert early prototype.

Adding hpa to the cc in the hope that he has some prototype code still
laying around..

                Linus