[RFC PATCH 00/11] Finer grained kernel address space randomization Kristen Carlson Accardi
 ` [RFC PATCH 01/11] modpost: Support >64K sections Kristen Carlson Accardi
   ` Kees Cook
 ` [RFC PATCH 02/11] x86: tools/relocs: Support >64K section headers Kristen Carlson Accardi
   ` Kees Cook
 ` [RFC PATCH 03/11] x86/boot: Allow a "silent" kaslr random byte fetch Kristen Carlson Accardi
   ` Andy Lutomirski
     ` Kees Cook
     ` Kristen Carlson Accardi
 ` [RFC PATCH 04/11] x86/boot/KASLR: Introduce PRNG for faster shuffling Kristen Carlson Accardi
   ` Andy Lutomirski
   ` Jason A. Donenfeld
       ` Kees Cook
         ` Kristen Carlson Accardi
 ` [RFC PATCH 05/11] x86: Makefile: Add build and config option for CONFIG_FG_KASLR Kristen Carlson Accardi
   ` Peter Zijlstra
     ` Kees Cook
   ` Arvind Sankar
     ` Kristen Carlson Accardi
     ` Kristen Carlson Accardi
       ` Kees Cook
 ` [RFC PATCH 06/11] x86: make sure _etext includes function sections Kristen Carlson Accardi
   ` Kees Cook
     ` Jann Horn
       ` David Laight
     ` Arvind Sankar
       ` Arvind Sankar
         ` Andy Lutomirski
     ` Arvind Sankar
       ` Arvind Sankar
     ` Kristen Carlson Accardi
       ` Andy Lutomirski
         ` Peter Zijlstra
           ` Kees Cook
             ` Peter Zijlstra
               ` Arjan van de Ven
                 ` Arvind Sankar
                   ` Josh Poimboeuf
                     ` Arvind Sankar
 ` [RFC PATCH 07/11] x86/tools: Adding relative relocs for randomized functions Kristen Carlson Accardi
   ` Kees Cook
 ` [RFC PATCH 08/11] x86: Add support for finer grained KASLR Kristen Carlson Accardi
   ` Andy Lutomirski
     ` Kees Cook [this message]
       ` Kristen Carlson Accardi
   ` Peter Zijlstra
     ` Kees Cook
       ` Peter Zijlstra
         ` Kristen Carlson Accardi
           ` Peter Zijlstra
             ` Kristen Carlson Accardi
   ` Arvind Sankar
     ` Kristen Carlson Accardi
 ` [RFC PATCH 09/11] kallsyms: hide layout and expose seed Kristen Carlson Accardi
   ` Kees Cook
     ` Kristen Carlson Accardi
       ` Jann Horn
         ` Kristen Carlson Accardi
           ` Kees Cook
             ` Kristen Carlson Accardi
       ` Baoquan He
         ` Kees Cook
           ` Baoquan He
 ` [RFC PATCH 10/11] module: Reorder functions Kristen Carlson Accardi
   ` Kees Cook
     ` Jessica Yu
 ` [RFC PATCH 11/11] x86/boot: Move "boot heap" out of .bss Kristen Carlson Accardi
   ` Arvind Sankar
     ` Kristen Carlson Accardi
     ` Kees Cook
       ` Arvind Sankar
         ` Kees Cook

From:		Kees Cook <keescook-AT-chromium.org>
To:		Andy Lutomirski <luto-AT-kernel.org>
Subject:		Re: [RFC PATCH 08/11] x86: Add support for finer grained KASLR
Date:		Thu, 06 Feb 2020 03:56:36 -0800
Message-ID:		<202002060353.A6A064A@keescook>
Cc:		Kristen Carlson Accardi <kristen-AT-linux.intel.com>, Thomas Gleixner <tglx-AT-linutronix.de>, Ingo Molnar <mingo-AT-redhat.com>, Borislav Petkov <bp-AT-alien8.de>, "H. Peter Anvin" <hpa-AT-zytor.com>, Arjan van de Ven <arjan-AT-linux.intel.com>, Rick Edgecombe <rick.p.edgecombe-AT-intel.com>, X86 ML <x86-AT-kernel.org>, LKML <linux-kernel-AT-vger.kernel.org>, Kernel Hardening <kernel-hardening-AT-lists.openwall.com>

On Wed, Feb 05, 2020 at 05:17:11PM -0800, Andy Lutomirski wrote:
> On Wed, Feb 5, 2020 at 2:39 PM Kristen Carlson Accardi
> <kristen@linux.intel.com> wrote:
> >
> > At boot time, find all the function sections that have separate .text
> > sections, shuffle them, and then copy them to new locations. Adjust
> > any relocations accordingly.
> >
> 
> > +       sort(base, num_syms, sizeof(int), kallsyms_cmp, kallsyms_swp);
> 
> Hah, here's a huge bottleneck.  Unless you are severely
> memory-constrained, never do a sort with an expensive swap function
> like this.  Instead allocate an array of indices that starts out as
> [0, 1, 2, ...].  Sort *that* where the swap function just swaps the
> indices.  Then use the sorted list of indices to permute the actual
> data.  The result is exactly one expensive swap per item instead of
> one expensive swap per swap.

I think there are few places where memory-vs-speed need to be examined.
I remain surprised about how much memory the entire series already uses
(58MB in my local tests), but I suspect this is likely dominated by the
two factors: a full copy of the decompressed kernel, and that the
"allocator" in the image doesn't really implement free():
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/...

-- 
Kees Cook