Skip to contentSkip to conversation

x86/KASLR: Randomize virtual address separately

PATCH Superseded Kees Cook 5 participants 23 messages May 9, 2016 – May 10, 2016

Subsystems (2)

v7 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Kees Cook

author
#0 lore raw

v7 cover x86/KASLR: Randomize virtual address separately

Okay, here's the remaining patches for this series. Hopefully these are clean and obvious. Technically this is v7 of the series, though much of it has already been added to -tip already. This is all based on the work of Yinghai, Baoquan, and myself.

***Background:
Bugs have been reported around kdump, kexec, and some netboot situations that didn't work when KASLR was enabled. While discussing the bugs, it was found that the current KASLR implementation had various limitations, but most importantly that it can only randomize in a 1GB region of physical memory.

The current KASLR implementaion only randomizes the base physical address of the kernel. If the delta from build-time load address and KASLR run-time load address (i.e. the physical address of where the kernel actually decompressed) is not equal to 0, relocation handling is performed using the delta. Though in principle kernel can be randomized to any physical address, the physical kernel text mapping address space is limited to 1G and the virtual address is just offset by the same amount. On x86_64 the result is the following range:
[0xffffffff80000000, 0xffffffffc0000000)

hpa and Vivek suggested we should change this by decoupling the physical address and virtual address randomization of kernel text and let them work separately. Then kernel text physical address can be randomized in region [16M, 64T), and kernel text virtual address can be randomized in region [0xffffffff80000000, 0xffffffffc0000000).

***Problems that needed solving:
- When booting from the startup_32 case, only a 0~4G identity mapping is built. If kernel will be randomly put anywhere from 16M to 64T at most, the price to build all the identity mappings is too high. We need to build the identity mapping on demand, not covering all of the physical address space. (The infrastructure for solving this has already landed in -tip now.)

- Decouple the physical address and virtual address randomization of kernel text and let them work separately.

- Kernels loaded high will not randomize into a lower memory region.

***Parts:
- The 1st part includes a bug fix and clean ups.

     (Patches 1-2)

- The 2nd part is Baoquan's new randomization slot management code for handling the much larger possible memory space.
(Patches 3-4)
- The 4th part is Baoquan's decoupling the physical address and virtual address randomization of kernel text and letting them work separately, based on Yinghai's ident mapping patches, fixing problem #2 above. (Patches 5-7)
- The 5th part lifts the upper and lower limits on physical addresses, fixing problem #3 above.
(Patches 8-9)

I've boot tested this a bunch on 32-bit and 64-bit, and things appear to be working as expected. I've cleaned up the changelogs, improved some comments, refactored a few things, split out things and merged others, etc. Changes are noted in the individual changelogs.

Thanks!

-Kees

v6->v7:
- general refactoring to adapt to changing casts, etc in earlier patches.
- found and fixed a typo in my refactorings that was obscuring a bug in my changes to the page table ident mapping code (physical address was never being added to identity maps).
- found some more file header comments to add, fixed mem_avoid comment typo.

v5->v6:
- sent other clean-ups as separate patches
- squashed code removal into the patches that made them removable
- refactoring slot calculation to avoid the confusing "if" statement
- protected slot_area_index in store_slot_info to be paranoid
- adjusted Kconfig language to be more complete but with hopefully less jargon
- fixed up as much of the unsigned long casts as possible
- fixed some coding styel on brace usage
- made find_random_phys_addr look like find_random_virt_addr
- clarified various variable names

v4->v5:
- rewrote all the changelogs, and several comments.
- refactored e820 parser to use a while loop instead of goto.
- rearranged removal of CONFIG_RANDOMIZE_BASE_MAX_OFFSET to earlier.
- additionally dropped KERNEL_IMAGE_SIZE_DEFAULT
- refactored minimum address calculation
- refactored slot offset calculation for readability
- fixed 32-bit boot failures
- fixed CONFIG_RANDOMIZE_BASE=n boot failure
- improved debug reporting

[Baoquan's histroy]
v3->v4:
- Made changes according to Kees's comments.
Add one patch 20/20 as Kees suggested to use KERNEL_IMAGE_SIZE as offset max of virtual random, meanwhile clean up useless CONFIG_RANDOM_OFFSET_MAX

x86, kaslr: Use KERNEL_IMAGE_SIZE as the offset max for kernel virtual randomization

v2->v3:
- It only takes care of the kaslr related patches.
For reviewers it's better to discuss only one issue in one thread.
* I take off one patch as follows from Yinghai's because I think it's unnecessay.
- Patch 05/19 x86, kaslr: rename output_size to output_run_size output_size is enough to represen the value:
output_len > run_size ? output_len : run_size

* I add Patch 04/19, it's a comment update patch. For other patches, I just adjust patch log and do several places of change comparing with 2nd round. Please check the change log under patch log of each patch for details.

* Adjust sequence of several patches to make review easier. It doesn't affect codes.

v1->v2:
- In 2nd round Yinghai made a big patchset including this kaslr fix and another setup_data related fix. The link is here:
http://lists-archives.com/linux-kernel/28346903-x86-updated-patches-for-kaslr-and-setup_data-etc-for-v4-3.html
You can get the code from Yinghai's git branch:
git://git.kernel.org/pub/scm/linux/kernel/git/yinghai/linux-yinghai.git for-x86-v4.3-next

v1:
- The first round can be found here:

    https://lwn.net/Articles/637115/
author
#1 lore raw

PATCH v7 1/9 x86/KASLR: Initialize mapping_info every time

As it turns out, mapping_info DOES need to be initialized every time. Without this, page tables were not being corrected updated, which could cause reboots when a physical address beyond 2G was chosen.

---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/pagetable.c +5 -11
index 3c99051566a9..34b95df14e69 100644
@@ -90,23 +90,17 @@ static void prepare_level4(void)
 }
 
 /*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-	.alloc_pgt_page	= alloc_pgt_page,
-	.context	= &pgt_data,
-	.pmd_flag	= __PAGE_KERNEL_LARGE_EXEC,
-};
-
-/*
  * Adds the specified range to what will become the new identity mappings.
  * Once all ranges have been added, the new mapping is activated by calling
  * finalize_identity_maps() below.
  */
 void add_identity_map(unsigned long start, unsigned long size)
 {
+	struct x86_mapping_info mapping_info = {
+		.alloc_pgt_page	= alloc_pgt_page,
+		.context	= &pgt_data,
+		.pmd_flag	= __PAGE_KERNEL_LARGE_EXEC,
+	};
 	unsigned long end = start + size;
 
 	/* Make sure we have a top level page table ready to use. */
Signature · 1 line
2.6.3
#2 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 30 lines · Kees Cook

As it turns out, mapping_info DOES need to be initialized every time. Without this, page tables were not being corrected updated, which could cause reboots when a physical address beyond 2G was chosen.

---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/pagetable.c +0 -11
index 3c99051566a9..34b95df14e69 100644
@@ -90,23 +90,17 @@ static void prepare_level4(void)
 }
 
 /*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-       .alloc_pgt_page = alloc_pgt_page,
-       .context        = &pgt_data,
-       .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
-};
-
-/*
  * Adds the specified range to what will become the new identity mappings.
  * Once all ranges have been added, the new mapping is activated by calling

arch/x86/boot/compressed/pagetable.c static void prepare_level4(void) · line 104

Quoted 10 lines
arch/x86/boot/compressed/pagetable.c +5 -0
  * finalize_identity_maps() below.
  */
 void add_identity_map(unsigned long start, unsigned long size)
 {
+       struct x86_mapping_info mapping_info = {
+               .alloc_pgt_page = alloc_pgt_page,
+               .context        = &pgt_data,
+               .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
+       };
        unsigned long end = start + size;

Still should be assigned once, and should be done in prepare_level4(). --- by may need different name for that ?

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Thanks

Yinghai

#3 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 45 lines · Yinghai Lu
Quoted 30 lines · Kees Cook

As it turns out, mapping_info DOES need to be initialized every time. Without this, page tables were not being corrected updated, which could cause reboots when a physical address beyond 2G was chosen.

---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/pagetable.c +0 -11
index 3c99051566a9..34b95df14e69 100644
@@ -90,23 +90,17 @@ static void prepare_level4(void)
 }
 
 /*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-       .alloc_pgt_page = alloc_pgt_page,
-       .context        = &pgt_data,
-       .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
-};
-
-/*
  * Adds the specified range to what will become the new identity mappings.
  * Once all ranges have been added, the new mapping is activated by calling

arch/x86/boot/compressed/pagetable.c static void prepare_level4(void) · line 104

Quoted 10 lines
arch/x86/boot/compressed/pagetable.c +5 -0
  * finalize_identity_maps() below.
  */
 void add_identity_map(unsigned long start, unsigned long size)
 {
+       struct x86_mapping_info mapping_info = {
+               .alloc_pgt_page = alloc_pgt_page,
+               .context        = &pgt_data,
+               .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
+       };
        unsigned long end = start + size;

Still should be assigned once, and should be done in prepare_level4(). --- by may need different name for that ?

Quoted 4 lines

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Something like:

-/*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {

-       .alloc_pgt_page = alloc_pgt_page,
-       .context        = &pgt_data,
-       .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,

-};
+static struct x86_mapping_info mapping_info;

/*
* Adds the specified range to what will become the new identity mappings.
@@ -110,8 +101,14 @@ void add_identity_map(unsigned long start, unsigned long size)

        unsigned long end = start + size;

        /* Make sure we have a top level page table ready to use. */
-       if (!level4p)
+       if (!level4p) {
+               /* need to set once during run time */
+               mapping_info.alloc_pgt_page     = alloc_pgt_page;
+               mapping_info.context    = &pgt_data;
+               mapping_info.pmd_flag   = __PAGE_KERNEL_LARGE_EXEC;
+
                prepare_level4();

+ }

        /* Align boundary to 2M. */
        start = round_down(start, PMD_SIZE);
#4 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 42 lines · Yinghai Lu
Quoted 7 lines · Yinghai Lu

Still should be assigned once, and should be done in prepare_level4(). --- by may need different name for that ?

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Something like:

arch/x86/boot/compressed/pagetable.c +8 -11
-/*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-       .alloc_pgt_page = alloc_pgt_page,
-       .context        = &pgt_data,
-       .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
-};
+static struct x86_mapping_info mapping_info;
 
 /*
  * Adds the specified range to what will become the new identity mappings.
@@ -110,8 +101,14 @@ void add_identity_map(unsigned long start,
 unsigned long size)
        unsigned long end = start + size;
 
        /* Make sure we have a top level page table ready to use. */
-       if (!level4p)
+       if (!level4p) {
+               /* need to set once during run time */
+               mapping_info.alloc_pgt_page     = alloc_pgt_page;
+               mapping_info.context    = &pgt_data;
+               mapping_info.pmd_flag   = __PAGE_KERNEL_LARGE_EXEC;
+
                prepare_level4();
+       }
 
        /* Align boundary to 2M. */
Quoted 1 line
        start = round_down(start, PMD_SIZE);

It would be better if Ingo could fold the change to

https://git.kernel.org/cgit/linux/kernel/git/tip/tip.git/patch/?id=3a94707d7a7bb1eb82acae5fbc035247dd1ba8a5
x86/KASLR: Build identity mappings on demand

As it happens to the last commit in tip/x86/boot.

Thanks

Yinghai

author
#5 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

In reply to Yinghai Lu
Quoted 45 lines · Yinghai Lu
Quoted 30 lines · Kees Cook

As it turns out, mapping_info DOES need to be initialized every time. Without this, page tables were not being corrected updated, which could cause reboots when a physical address beyond 2G was chosen.

---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/pagetable.c +0 -11
index 3c99051566a9..34b95df14e69 100644
@@ -90,23 +90,17 @@ static void prepare_level4(void)
 }
 
 /*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-       .alloc_pgt_page = alloc_pgt_page,
-       .context        = &pgt_data,
-       .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
-};
-
-/*
  * Adds the specified range to what will become the new identity mappings.
  * Once all ranges have been added, the new mapping is activated by calling

arch/x86/boot/compressed/pagetable.c static void prepare_level4(void) · line 104

Quoted 10 lines
arch/x86/boot/compressed/pagetable.c +5 -0
  * finalize_identity_maps() below.
  */
 void add_identity_map(unsigned long start, unsigned long size)
 {
+       struct x86_mapping_info mapping_info = {
+               .alloc_pgt_page = alloc_pgt_page,
+               .context        = &pgt_data,
+               .pmd_flag       = __PAGE_KERNEL_LARGE_EXEC,
+       };
        unsigned long end = start + size;

Still should be assigned once, and should be done in prepare_level4(). --- by may need different name for that ?

Quoted 4 lines

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Ah-ha, that explains why I had to keep it on the stack. Thanks for the clarification!

-Kees

Signature · 2 lines
Kees Cook
Chrome OS & Brillo Security
#6 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 7 lines · Kees Cook
Quoted 4 lines

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Ah-ha, that explains why I had to keep it on the stack. Thanks for the clarification!

My fault, I should put that comment in the code at first place.

Thanks

Yinghai

#7 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 10 lines · Yinghai Lu
Quoted 7 lines · Kees Cook
Quoted 4 lines

The exact reason to have assigning in functions.

pgt_data address could be changed during kernel relocation. so can not assigned during compiling time.

Ah-ha, that explains why I had to keep it on the stack. Thanks for the clarification!

My fault, I should put that comment in the code at first place.

Ok, could you guys please update the code and the changelog as well, and also rename that horribly named prepare_level4() function?

Also, since this code is multi-author, it would be nice to add explicit copyright notices to the new arch/x86/boot/compressed/pagetable.c file, it was originally written by you, then modified by Kees. Something like:

/*
* Copyright (C) 2015-2016 Yinghai Lu
* Copyright (C) 2016 Kees Cook
*/

Thanks,

Ingo

#8 lore raw

Re: [PATCH v7 1/9] x86/KASLR: Initialize mapping_info every time

Quoted 2 lines · Ingo Molnar

Ok, could you guys please update the code and the changelog as well, and also rename that horribly named prepare_level4() function?

Oh, and while at it, call that new function at the beginning of choose_random_location() before the first call to add_identity_map() through mem_avoid_init() and make the code flow even clearer this way instead of doing funky checks like

        if (!level4p)
                prepare_level4();

Thanks.

Signature · 5 lines
Regards/Gruss,
    Boris.

SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nürnberg)
-- 
#9 lore raw

[tip:x86/boot] x86/KASLR: Initialize mapping_info every time

In reply to Kees Cook
x86/KASLR: Initialize mapping_info every time
Commit-ID:  434a6c9f90f7ab5ade619455df01ef5ebea533ee
Gitweb:     http://git.kernel.org/tip/434a6c9f90f7ab5ade619455df01ef5ebea533ee
Author:     Kees Cook <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:04 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:02 +0200

x86/KASLR: Initialize mapping_info every time

As it turns out, mapping_info DOES need to be initialized every time, because pgt_data address could be changed during kernel relocation. So it can not be build time assigned.

Without this, page tables were not being corrected updated, which could cause reboots when a physical address beyond 2G was chosen.

Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Baoquan He <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/pagetable.c +5 -11
index 3c99051..34b95df 100644
@@ -90,23 +90,17 @@ static void prepare_level4(void)
 }
 
 /*
- * Mapping information structure passed to kernel_ident_mapping_init().
- * Since this never changes, there's no reason to repeatedly fill it
- * in on the stack when calling add_identity_map().
- */
-static struct x86_mapping_info mapping_info = {
-	.alloc_pgt_page	= alloc_pgt_page,
-	.context	= &pgt_data,
-	.pmd_flag	= __PAGE_KERNEL_LARGE_EXEC,
-};
-
-/*
  * Adds the specified range to what will become the new identity mappings.
  * Once all ranges have been added, the new mapping is activated by calling
  * finalize_identity_maps() below.
  */
 void add_identity_map(unsigned long start, unsigned long size)
 {
+	struct x86_mapping_info mapping_info = {
+		.alloc_pgt_page	= alloc_pgt_page,
+		.context	= &pgt_data,
+		.pmd_flag	= __PAGE_KERNEL_LARGE_EXEC,
+	};
 	unsigned long end = start + size;
 
 	/* Make sure we have a top level page table ready to use. */
author
#10 lore raw

PATCH v7 2/9 x86/boot: Add missing file header comments

In reply to Kees Cook

There were some files with missing header comments. Since they are included from both compressed and regular kernels, make note of that. Also corrects a typo in the mem_avoid comments.

---
 arch/x86/boot/compressed/kaslr.c     | 2 +-
 arch/x86/boot/early_serial_console.c | 4 ++++
 arch/x86/mm/ident_map.c              | 5 +++++
 3 files changed, 10 insertions(+), 1 deletion(-)
arch/x86/boot/compressed/kaslr.c +1 -1
index f82975b0f9d6..3f0692dcd30d 100644
@@ -163,7 +163,7 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
  * memory ranges lead to really hard to debug boot failures.
  *
  * The initrd, cmdline, and boot_params are trivial to identify for
- * avoiding. The are MEM_AVOID_INITRD, MEM_AVOID_CMDLINE, and
+ * avoiding. They are MEM_AVOID_INITRD, MEM_AVOID_CMDLINE, and
  * MEM_AVOID_BOOTPARAMS respectively below.
  *
  * What is not obvious how to avoid is the range of memory that is used
arch/x86/boot/early_serial_console.c +4 -0
index 45a07684bbab..f0b8d6d93164 100644
@@ -1,3 +1,7 @@
+/*
+ * Serial port routines for use during early boot reporting. This code is
+ * included from both the compressed kernel and the regular kernel.
+ */
 #include "boot.h"
 
 #define DEFAULT_SERIAL_PORT 0x3f8 /* ttyS0 */
arch/x86/mm/ident_map.c +5 -0
index 751ca920773a..ec21796ac5fd 100644
@@ -1,3 +1,7 @@
+/*
+ * Helper routines for building identity mapping page tables. This is
+ * included by both the compressed kernel and the regular kernel.
+ */
 
 static void ident_pmd_init(unsigned long pmd_flag, pmd_t *pmd_page,
 			   unsigned long addr, unsigned long end)
@@ -10,6 +14,7 @@ static void ident_pmd_init(unsigned long pmd_flag, pmd_t *pmd_page,
 			set_pmd(pmd, __pmd(addr | pmd_flag));
 	}
 }
+
 static int ident_pud_init(struct x86_mapping_info *info, pud_t *pud_page,
 			  unsigned long addr, unsigned long end)
 {
Signature · 1 line
2.6.3
#11 lore raw

[tip:x86/boot] x86/boot: Add missing file header comments

x86/boot: Add missing file header comments
Commit-ID:  cb18ef0da259db611fbf52806592fde5f469ae67
Gitweb:     http://git.kernel.org/tip/cb18ef0da259db611fbf52806592fde5f469ae67
Author:     Kees Cook <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:05 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:03 +0200

x86/boot: Add missing file header comments

There were some files with missing header comments. Since they are included from both compressed and regular kernels, make note of that. Also corrects a typo in the mem_avoid comments.

Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Baoquan He <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/kaslr.c     | 2 +-
 arch/x86/boot/early_serial_console.c | 4 ++++
 arch/x86/mm/ident_map.c              | 5 +++++
 3 files changed, 10 insertions(+), 1 deletion(-)
arch/x86/boot/compressed/kaslr.c +1 -1
index f5a138c..f15d7b8 100644
@@ -163,7 +163,7 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
  * memory ranges lead to really hard to debug boot failures.
  *
  * The initrd, cmdline, and boot_params are trivial to identify for
- * avoiding. The are MEM_AVOID_INITRD, MEM_AVOID_CMDLINE, and
+ * avoiding. They are MEM_AVOID_INITRD, MEM_AVOID_CMDLINE, and
  * MEM_AVOID_BOOTPARAMS respectively below.
  *
  * What is not obvious how to avoid is the range of memory that is used
arch/x86/boot/early_serial_console.c +4 -0
index 45a0768..f0b8d6d 100644
@@ -1,3 +1,7 @@
+/*
+ * Serial port routines for use during early boot reporting. This code is
+ * included from both the compressed kernel and the regular kernel.
+ */
 #include "boot.h"
 
 #define DEFAULT_SERIAL_PORT 0x3f8 /* ttyS0 */
arch/x86/mm/ident_map.c +5 -0
index 751ca92..ec21796 100644
@@ -1,3 +1,7 @@
+/*
+ * Helper routines for building identity mapping page tables. This is
+ * included by both the compressed kernel and the regular kernel.
+ */
 
 static void ident_pmd_init(unsigned long pmd_flag, pmd_t *pmd_page,
 			   unsigned long addr, unsigned long end)
@@ -10,6 +14,7 @@ static void ident_pmd_init(unsigned long pmd_flag, pmd_t *pmd_page,
 			set_pmd(pmd, __pmd(addr | pmd_flag));
 	}
 }
+
 static int ident_pud_init(struct x86_mapping_info *info, pud_t *pud_page,
 			  unsigned long addr, unsigned long end)
 {
author
#12 lore raw

PATCH v7 3/9 x86/KASLR: Add slot_area to manage random_addr slots

In reply to Kees Cook

From: Baoquan He <[email protected]>

In order to support KASLR moving the kernel anywhere in physical memory (which could be up to 64TB), we need to handle counting the potential randomization locations in a more efficient manner.

In the worst case with 64TB, there could be roughly 32 * 1024 * 1024 randomization slots if CONFIG_PHYSICAL_ALIGN is 0x1000000. Currently the starting address of candidate positions is stored into the slots[] array, one at a time. This method would cost too much memory and it's also very inefficient to get and save the slot information into the slot array one by one.

This patch introduces struct slot_area to manage each contiguous region of randomization slots. Each slot_area will contain the starting address and how many available slots are in this area. As with the original code, the slot_areas will avoid the mem_avoid regions.

Since setup_data is a linked list, it could contain an unknown number of memory regions to be avoided, which could cause us to fragment the contiguous memory that the slot_area array is tracking. In normal operation this level of fragmentation will be extremely rare, but we choose a suitably large value (100) for the array. If setup_data forces the slot_area array to become highly fragmented and there are more slots available beyond the first 100 found, the rest will be ignored for KASLR selection.

The function store_slot_info() is used to calculate the number of slots available in the passed-in memory region and stores it into slot_areas[] after adjusting for alignment and size requirements.

[kees: rewrote changelog, squash with new functions]
---
 arch/x86/boot/compressed/kaslr.c | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
arch/x86/boot/compressed/kaslr.c +29 -0
index 3f0692dcd30d..89f0148e3e84 100644
@@ -308,8 +308,37 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 }
 
 static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
+
+struct slot_area {
+	unsigned long addr;
+	int num;
+};
+
+#define MAX_SLOT_AREA 100
+
+static struct slot_area slot_areas[MAX_SLOT_AREA];
+
 static unsigned long slot_max;
 
+static unsigned long slot_area_index;
+
+static void store_slot_info(struct mem_vector *region, unsigned long image_size)
+{
+	struct slot_area slot_area;
+
+	if (slot_area_index == MAX_SLOT_AREA)
+		return;
+
+	slot_area.addr = region->start;
+	slot_area.num = (region->size - image_size) /
+			CONFIG_PHYSICAL_ALIGN + 1;
+
+	if (slot_area.num > 0) {
+		slot_areas[slot_area_index++] = slot_area;
+		slot_max += slot_area.num;
+	}
+}
+
 static void slots_append(unsigned long addr)
 {
 	/* Overflowing the slots list should be impossible. */
Signature · 1 line
2.6.3
#13 lore raw

[tip:x86/boot] x86/KASLR: Add 'struct slot_area' to manage random_addr slots

x86/KASLR: Add 'struct slot_area' to manage random_addr slots
Commit-ID:  c401cf1524153f9c2ede7ab8ece403513925770a
Gitweb:     http://git.kernel.org/tip/c401cf1524153f9c2ede7ab8ece403513925770a
Author:     Baoquan He <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:06 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:04 +0200

x86/KASLR: Add 'struct slot_area' to manage random_addr slots

In order to support KASLR moving the kernel anywhere in physical memory (which could be up to 64TB), we need to handle counting the potential randomization locations in a more efficient manner.

In the worst case with 64TB, there could be roughly 32 * 1024 * 1024 randomization slots if CONFIG_PHYSICAL_ALIGN is 0x1000000. Currently the starting address of candidate positions is stored into the slots[] array, one at a time. This method would cost too much memory and it's also very inefficient to get and save the slot information into the slot array one by one.

This patch introduces 'struct slot_area' to manage each contiguous region of randomization slots. Each slot_area will contain the starting address and how many available slots are in this area. As with the original code, the slot_areas[] will avoid the mem_avoid[] regions.

Since setup_data is a linked list, it could contain an unknown number of memory regions to be avoided, which could cause us to fragment the contiguous memory that the slot_area array is tracking. In normal operation this level of fragmentation will be extremely rare, but we choose a suitably large value (100) for the array. If setup_data forces the slot_area array to become highly fragmented and there are more slots available beyond the first 100 found, the rest will be ignored for KASLR selection.

The function store_slot_info() is used to calculate the number of slots available in the passed-in memory region and stores it into slot_areas[] after adjusting for alignment and size requirements.

[ Rewrote changelog, squashed with new functions. ]
Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/kaslr.c | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
arch/x86/boot/compressed/kaslr.c +29 -0
index f15d7b8..81edf99 100644
@@ -308,8 +308,37 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 }
 
 static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
+
+struct slot_area {
+	unsigned long addr;
+	int num;
+};
+
+#define MAX_SLOT_AREA 100
+
+static struct slot_area slot_areas[MAX_SLOT_AREA];
+
 static unsigned long slot_max;
 
+static unsigned long slot_area_index;
+
+static void store_slot_info(struct mem_vector *region, unsigned long image_size)
+{
+	struct slot_area slot_area;
+
+	if (slot_area_index == MAX_SLOT_AREA)
+		return;
+
+	slot_area.addr = region->start;
+	slot_area.num = (region->size - image_size) /
+			CONFIG_PHYSICAL_ALIGN + 1;
+
+	if (slot_area.num > 0) {
+		slot_areas[slot_area_index++] = slot_area;
+		slot_max += slot_area.num;
+	}
+}
+
 static void slots_append(unsigned long addr)
 {
 	/* Overflowing the slots list should be impossible. */
author
#14 lore raw

PATCH v7 4/9 x86/KASLR: Return earliest overlap when avoiding regions

In reply to Kees Cook

In preparation for being able to detect where to split up contiguous memory regions that overlap with memory regions to avoid, we need to pass back what the earliest overlapping region was. This modifies the overlap checker to return that information.

Based on a separate mem_min_overlap() implementation by Baoquan He.

---
 arch/x86/boot/compressed/kaslr.c | 29 ++++++++++++++++++++---------
 1 file changed, 20 insertions(+), 9 deletions(-)
arch/x86/boot/compressed/kaslr.c +20 -9
index 89f0148e3e84..1c02f07ce55a 100644
@@ -279,15 +279,24 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 #endif
 }
 
-/* Does this memory vector overlap a known avoided area? */
-static bool mem_avoid_overlap(struct mem_vector *img)
+/*
+ * Does this memory vector overlap a known avoided area? If so, record the
+ * overlap region with the lowest address.
+ */
+static bool mem_avoid_overlap(struct mem_vector *img,
+			      struct mem_vector *overlap)
 {
 	int i;
 	struct setup_data *ptr;
+	unsigned long earliest = img->start + img->size;
+	bool is_overlapping = false;
 
 	for (i = 0; i < MEM_AVOID_MAX; i++) {
-		if (mem_overlaps(img, &mem_avoid[i]))
-			return true;
+		if (mem_overlaps(img, &mem_avoid[i]) &&
+		    mem_avoid[i].start < earliest) {
+			*overlap = mem_avoid[i];
+			is_overlapping = true;
+		}
 	}
 
 	/* Avoid all entries in the setup_data linked list. */
@@ -298,13 +307,15 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 		avoid.start = (unsigned long)ptr;
 		avoid.size = sizeof(*ptr) + ptr->len;
 
-		if (mem_overlaps(img, &avoid))
-			return true;
+		if (mem_overlaps(img, &avoid) && (avoid.start < earliest)) {
+			*overlap = avoid;
+			is_overlapping = true;
+		}
 
 		ptr = (struct setup_data *)(unsigned long)ptr->next;
 	}
 
-	return false;
+	return is_overlapping;
 }
 
 static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
@@ -361,7 +372,7 @@ static void process_e820_entry(struct e820entry *entry,
 			       unsigned long minimum,
 			       unsigned long image_size)
 {
-	struct mem_vector region, img;
+	struct mem_vector region, img, overlap;
 
 	/* Skip non-RAM entries. */
 	if (entry->type != E820_RAM)
@@ -400,7 +411,7 @@ static void process_e820_entry(struct e820entry *entry,
 	for (img.start = region.start, img.size = image_size ;
 	     mem_contains(&region, &img) ;
 	     img.start += CONFIG_PHYSICAL_ALIGN) {
-		if (mem_avoid_overlap(&img))
+		if (mem_avoid_overlap(&img, &overlap))
 			continue;
 		slots_append(img.start);
 	}
Signature · 1 line
2.6.3
#15 lore raw

[tip:x86/boot] x86/KASLR: Return earliest overlap when avoiding regions

x86/KASLR: Return earliest overlap when avoiding regions
Commit-ID:  06486d6c97cebc2433a40a979f3849cd68184de9
Gitweb:     http://git.kernel.org/tip/06486d6c97cebc2433a40a979f3849cd68184de9
Author:     Kees Cook <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:07 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:04 +0200

x86/KASLR: Return earliest overlap when avoiding regions

In preparation for being able to detect where to split up contiguous memory regions that overlap with memory regions to avoid, we need to pass back what the earliest overlapping region was. This modifies the overlap checker to return that information.

Based on a separate mem_min_overlap() implementation by Baoquan He.

Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Baoquan He <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/kaslr.c | 29 ++++++++++++++++++++---------
 1 file changed, 20 insertions(+), 9 deletions(-)
arch/x86/boot/compressed/kaslr.c +20 -9
index 81edf99..e55ebcb 100644
@@ -279,15 +279,24 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 #endif
 }
 
-/* Does this memory vector overlap a known avoided area? */
-static bool mem_avoid_overlap(struct mem_vector *img)
+/*
+ * Does this memory vector overlap a known avoided area? If so, record the
+ * overlap region with the lowest address.
+ */
+static bool mem_avoid_overlap(struct mem_vector *img,
+			      struct mem_vector *overlap)
 {
 	int i;
 	struct setup_data *ptr;
+	unsigned long earliest = img->start + img->size;
+	bool is_overlapping = false;
 
 	for (i = 0; i < MEM_AVOID_MAX; i++) {
-		if (mem_overlaps(img, &mem_avoid[i]))
-			return true;
+		if (mem_overlaps(img, &mem_avoid[i]) &&
+		    mem_avoid[i].start < earliest) {
+			*overlap = mem_avoid[i];
+			is_overlapping = true;
+		}
 	}
 
 	/* Avoid all entries in the setup_data linked list. */
@@ -298,13 +307,15 @@ static bool mem_avoid_overlap(struct mem_vector *img)
 		avoid.start = (unsigned long)ptr;
 		avoid.size = sizeof(*ptr) + ptr->len;
 
-		if (mem_overlaps(img, &avoid))
-			return true;
+		if (mem_overlaps(img, &avoid) && (avoid.start < earliest)) {
+			*overlap = avoid;
+			is_overlapping = true;
+		}
 
 		ptr = (struct setup_data *)(unsigned long)ptr->next;
 	}
 
-	return false;
+	return is_overlapping;
 }
 
 static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
@@ -361,7 +372,7 @@ static void process_e820_entry(struct e820entry *entry,
 			       unsigned long minimum,
 			       unsigned long image_size)
 {
-	struct mem_vector region, img;
+	struct mem_vector region, img, overlap;
 
 	/* Skip non-RAM entries. */
 	if (entry->type != E820_RAM)
@@ -400,7 +411,7 @@ static void process_e820_entry(struct e820entry *entry,
 	for (img.start = region.start, img.size = image_size ;
 	     mem_contains(&region, &img) ;
 	     img.start += CONFIG_PHYSICAL_ALIGN) {
-		if (mem_avoid_overlap(&img))
+		if (mem_avoid_overlap(&img, &overlap))
 			continue;
 		slots_append(img.start);
 	}
author
#16 lore raw

PATCH v7 5/9 x86/KASLR: Add virtual address choosing function

In reply to Kees Cook

From: Baoquan He <[email protected]>

To support randomizing the kernel virtual address separately from the physical address, this patch adds find_random_virt_addr() to choose a slot anywhere between LOAD_PHYSICAL_ADDR and KERNEL_IMAGE_SIZE. Since this address is virtual, not physical, we can place the kernel anywhere in this region, as long as it is aligned and (in the case of kernel being larger than the slot size) placed with enough room to load the entire kernel image.

For clarity and readability, find_random_addr() is renamed to find_random_phys_addr() and has "size" renamed to "image_size" to match find_random_virt_addr().

[kees: rewrote changelog, refactor slot calculation for readability]
[kees: renamed find_random_phys_addr() and size argument]
---
 arch/x86/boot/compressed/kaslr.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)
arch/x86/boot/compressed/kaslr.c +28 -4
index 1c02f07ce55a..82d00282df3f 100644
@@ -417,8 +417,8 @@ static void process_e820_entry(struct e820entry *entry,
 	}
 }
 
-static unsigned long find_random_addr(unsigned long minimum,
-				      unsigned long size)
+static unsigned long find_random_phys_addr(unsigned long minimum,
+					   unsigned long image_size)
 {
 	int i;
 	unsigned long addr;
@@ -428,12 +428,36 @@ static unsigned long find_random_addr(unsigned long minimum,
 
 	/* Verify potential e820 positions, appending to slots list. */
 	for (i = 0; i < boot_params->e820_entries; i++) {
-		process_e820_entry(&boot_params->e820_map[i], minimum, size);
+		process_e820_entry(&boot_params->e820_map[i], minimum,
+				   image_size);
 	}
 
 	return slots_fetch_random();
 }
 
+static unsigned long find_random_virt_addr(unsigned long minimum,
+					   unsigned long image_size)
+{
+	unsigned long slots, random_addr;
+
+	/* Make sure minimum is aligned. */
+	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
+	/* Align image_size for easy slot calculations. */
+	image_size = ALIGN(image_size, CONFIG_PHYSICAL_ALIGN);
+
+	/*
+	 * There are how many CONFIG_PHYSICAL_ALIGN-sized slots
+	 * that can hold image_size within the range of minimum to
+	 * KERNEL_IMAGE_SIZE?
+	 */
+	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
+		 CONFIG_PHYSICAL_ALIGN + 1;
+
+	random_addr = get_random_long() % slots;
+
+	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
+}
+
 /*
  * Since this function examines addresses much more numerically,
  * it takes the input and output pointers as 'unsigned long'.
@@ -464,7 +488,7 @@ unsigned char *choose_random_location(unsigned long input,
 	mem_avoid_init(input, input_size, output);
 
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_addr(output, output_size);
+	random_addr = find_random_phys_addr(output, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
Signature · 1 line
2.6.3
#17 lore raw

[tip:x86/boot] x86/KASLR: Add virtual address choosing function

x86/KASLR: Add virtual address choosing function
Commit-ID:  071a74930e60d1fa51207d71f00a35b4f9d4d179
Gitweb:     http://git.kernel.org/tip/071a74930e60d1fa51207d71f00a35b4f9d4d179
Author:     Baoquan He <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:08 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:06 +0200

x86/KASLR: Add virtual address choosing function

To support randomizing the kernel virtual address separately from the physical address, this patch adds find_random_virt_addr() to choose a slot anywhere between LOAD_PHYSICAL_ADDR and KERNEL_IMAGE_SIZE. Since this address is virtual, not physical, we can place the kernel anywhere in this region, as long as it is aligned and (in the case of kernel being larger than the slot size) placed with enough room to load the entire kernel image.

For clarity and readability, find_random_addr() is renamed to find_random_phys_addr() and has "size" renamed to "image_size" to match find_random_virt_addr().

[ Rewrote changelog, refactored slot calculation for readability. ]
[ Renamed find_random_phys_addr() and size argument. ]
Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/kaslr.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)
arch/x86/boot/compressed/kaslr.c +28 -4
index e55ebcb..016a4f4 100644
@@ -417,8 +417,8 @@ static void process_e820_entry(struct e820entry *entry,
 	}
 }
 
-static unsigned long find_random_addr(unsigned long minimum,
-				      unsigned long size)
+static unsigned long find_random_phys_addr(unsigned long minimum,
+					   unsigned long image_size)
 {
 	int i;
 	unsigned long addr;
@@ -428,12 +428,36 @@ static unsigned long find_random_addr(unsigned long minimum,
 
 	/* Verify potential e820 positions, appending to slots list. */
 	for (i = 0; i < boot_params->e820_entries; i++) {
-		process_e820_entry(&boot_params->e820_map[i], minimum, size);
+		process_e820_entry(&boot_params->e820_map[i], minimum,
+				   image_size);
 	}
 
 	return slots_fetch_random();
 }
 
+static unsigned long find_random_virt_addr(unsigned long minimum,
+					   unsigned long image_size)
+{
+	unsigned long slots, random_addr;
+
+	/* Make sure minimum is aligned. */
+	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
+	/* Align image_size for easy slot calculations. */
+	image_size = ALIGN(image_size, CONFIG_PHYSICAL_ALIGN);
+
+	/*
+	 * There are how many CONFIG_PHYSICAL_ALIGN-sized slots
+	 * that can hold image_size within the range of minimum to
+	 * KERNEL_IMAGE_SIZE?
+	 */
+	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
+		 CONFIG_PHYSICAL_ALIGN + 1;
+
+	random_addr = get_random_long() % slots;
+
+	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
+}
+
 /*
  * Since this function examines addresses much more numerically,
  * it takes the input and output pointers as 'unsigned long'.
@@ -464,7 +488,7 @@ unsigned char *choose_random_location(unsigned long input,
 	mem_avoid_init(input, input_size, output);
 
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_addr(output, output_size);
+	random_addr = find_random_phys_addr(output, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
author
#18 lore raw

PATCH v7 6/9 x86/KASLR: Clarify purpose of each get_random_long()

In reply to Kees Cook

KASLR will be calling get_random_long() twice, but the debug output won't distinguishing between them. This patch adds a report on when it is fetching the physical vs virtual address. With this, once the virtual offset is separate, the report changes from:

KASLR using RDTSC...
KASLR using RDTSC...

into:

Physical KASLR using RDTSC...
Virtual KASLR using RDTSC...

---
 arch/x86/boot/compressed/kaslr.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
arch/x86/boot/compressed/kaslr.c +5 -4
index 82d00282df3f..c4b1e4b05cb6 100644
@@ -72,7 +72,7 @@ static unsigned long get_random_boot(void)
 	return hash;
 }
 
-static unsigned long get_random_long(void)
+static unsigned long get_random_long(const char *purpose)
 {
 #ifdef CONFIG_X86_64
 	const unsigned long mix_const = 0x5d6008cbf3848dd3UL;
@@ -82,7 +82,8 @@ static unsigned long get_random_long(void)
 	unsigned long raw, random = get_random_boot();
 	bool use_i8254 = true;
 
-	debug_putstr("KASLR using");
+	debug_putstr(purpose);
+	debug_putstr(" KASLR using");
 
 	if (has_cpuflag(X86_FEATURE_RDRAND)) {
 		debug_putstr(" RDRAND");
@@ -365,7 +366,7 @@ static unsigned long slots_fetch_random(void)
 	if (slot_max == 0)
 		return 0;
 
-	return slots[get_random_long() % slot_max];
+	return slots[get_random_long("Physical") % slot_max];
 }
 
 static void process_e820_entry(struct e820entry *entry,
@@ -453,7 +454,7 @@ static unsigned long find_random_virt_addr(unsigned long minimum,
 	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
 		 CONFIG_PHYSICAL_ALIGN + 1;
 
-	random_addr = get_random_long() % slots;
+	random_addr = get_random_long("Virtual") % slots;
 
 	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
 }
Signature · 1 line
2.6.3
#19 lore raw

[tip:x86/boot] x86/KASLR: Clarify purpose of each get_random_long()

x86/KASLR: Clarify purpose of each get_random_long()
Commit-ID:  d2d3462f9f08da364c8fbd41e8e32229d610d49d
Gitweb:     http://git.kernel.org/tip/d2d3462f9f08da364c8fbd41e8e32229d610d49d
Author:     Kees Cook <[email protected]>
AuthorDate: Mon, 9 May 2016 13:22:09 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 10 May 2016 10:12:08 +0200

x86/KASLR: Clarify purpose of each get_random_long()

KASLR will be calling get_random_long() twice, but the debug output won't distinguishing between them. This patch adds a report on when it is fetching the physical vs virtual address. With this, once the virtual offset is separate, the report changes from:

KASLR using RDTSC...
KASLR using RDTSC...

into:

Physical KASLR using RDTSC...
Virtual KASLR using RDTSC...

Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Baoquan He <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Dave Young <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Vivek Goyal <[email protected]>
Cc Yinghai Lu <[email protected]>
---
 arch/x86/boot/compressed/kaslr.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
arch/x86/boot/compressed/kaslr.c +5 -4
index 016a4f4..cfeb025 100644
@@ -72,7 +72,7 @@ static unsigned long get_random_boot(void)
 	return hash;
 }
 
-static unsigned long get_random_long(void)
+static unsigned long get_random_long(const char *purpose)
 {
 #ifdef CONFIG_X86_64
 	const unsigned long mix_const = 0x5d6008cbf3848dd3UL;
@@ -82,7 +82,8 @@ static unsigned long get_random_long(void)
 	unsigned long raw, random = get_random_boot();
 	bool use_i8254 = true;
 
-	debug_putstr("KASLR using");
+	debug_putstr(purpose);
+	debug_putstr(" KASLR using");
 
 	if (has_cpuflag(X86_FEATURE_RDRAND)) {
 		debug_putstr(" RDRAND");
@@ -365,7 +366,7 @@ static unsigned long slots_fetch_random(void)
 	if (slot_max == 0)
 		return 0;
 
-	return slots[get_random_long() % slot_max];
+	return slots[get_random_long("Physical") % slot_max];
 }
 
 static void process_e820_entry(struct e820entry *entry,
@@ -453,7 +454,7 @@ static unsigned long find_random_virt_addr(unsigned long minimum,
 	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
 		 CONFIG_PHYSICAL_ALIGN + 1;
 
-	random_addr = get_random_long() % slots;
+	random_addr = get_random_long("Virtual") % slots;
 
 	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
 }
author
#20 lore raw

PATCH v7 7/9 x86/KASLR: Randomize virtual address separately

In reply to Kees Cook

From: Baoquan He <[email protected]>

The current KASLR implementation randomizes the physical and virtual addresses of the kernel together (both are offset by the same amount). It calculates the delta of the physical address where vmlinux was linked to load and where it is finally loaded. If the delta is not equal to 0 (i.e. the kernel was relocated), relocation handling needs be done.

On 64-bit, this patch randomizes both the physical address where kernel is decompressed and the virtual address where kernel text is mapped and will execute from. We now have two values being chosen, so the function arguments are reorganized to pass by pointer so they can be directly updated. Since relocation handling only depends on the virtual address, we must check the virtual delta, not the physical delta for processing kernel relocations. This also populates the page table for the new virtual address range. 32-bit does not support a separate virtual address, so it continues to use the physical offset for its virtual offset.

Additionally updates the sanity checks done on the resulting kernel addresses since they are potentially separate now.

[kees: rewrote changelog, limited virtual split to 64-bit only, update checks]
[kees: fix CONFIG_RANDOMIZE_BASE=n boot failure]
---
 arch/x86/boot/compressed/kaslr.c | 44 ++++++++++++++++++++----------------
 arch/x86/boot/compressed/misc.c  | 49 ++++++++++++++++++++++++----------------
 arch/x86/boot/compressed/misc.h  | 22 ++++++++++--------
 3 files changed, 66 insertions(+), 49 deletions(-)
arch/x86/boot/compressed/kaslr.c +24 -20
index c4b1e4b05cb6..1d1338f04bbd 100644
@@ -463,46 +463,50 @@ static unsigned long find_random_virt_addr(unsigned long minimum,
  * Since this function examines addresses much more numerically,
  * it takes the input and output pointers as 'unsigned long'.
  */
-unsigned char *choose_random_location(unsigned long input,
-				      unsigned long input_size,
-				      unsigned long output,
-				      unsigned long output_size)
+void choose_random_location(unsigned long input,
+			    unsigned long input_size,
+			    unsigned long *output,
+			    unsigned long output_size,
+			    unsigned long *virt_addr)
 {
-	unsigned long choice = output;
 	unsigned long random_addr;
 
+	/* By default, keep output position unchanged. */
+	*virt_addr = *output;
+
 #ifdef CONFIG_HIBERNATION
 	if (!cmdline_find_option_bool("kaslr")) {
 		warn("KASLR disabled: 'kaslr' not on cmdline (hibernation selected).");
-		goto out;
+		return;
 	}
 #else
 	if (cmdline_find_option_bool("nokaslr")) {
 		warn("KASLR disabled: 'nokaslr' on cmdline.");
-		goto out;
+		return;
 	}
 #endif
 
 	boot_params->hdr.loadflags |= KASLR_FLAG;
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init(input, input_size, output);
+	mem_avoid_init(input, input_size, *output);
 
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_phys_addr(output, output_size);
+	random_addr = find_random_phys_addr(*output, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
-		goto out;
+	} else {
+		/* Update the new physical address location. */
+		if (*output != random_addr) {
+			add_identity_map(random_addr, output_size);
+			finalize_identity_maps();
+			*output = random_addr;
+		}
 	}
 
-	/* Always enforce the minimum. */
-	if (random_addr < choice)
-		goto out;
-
-	choice = random_addr;
-
-	add_identity_map(choice, output_size);
-	finalize_identity_maps();
-out:
-	return (unsigned char *)choice;
+	/* Pick random virtual address starting from LOAD_PHYSICAL_ADDR. */
+	if (IS_ENABLED(CONFIG_X86_64))
+		random_addr = find_random_virt_addr(LOAD_PHYSICAL_ADDR,
+						 output_size);
+	*virt_addr = random_addr;
 }
arch/x86/boot/compressed/misc.c +30 -19

100 lines not on this page · raw message

arch/x86/boot/compressed/misc.h +12 -10
index b6fec1ff10e4..a6a5f3463c17 100644
@@ -67,20 +67,22 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned long input_ptr,
-				      unsigned long input_size,
-				      unsigned long output_ptr,
-				      unsigned long output_size);
+void choose_random_location(unsigned long input,
+			    unsigned long input_size,
+			    unsigned long *output,
+			    unsigned long output_size,
+			    unsigned long *virt_addr);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
-static inline
-unsigned char *choose_random_location(unsigned long input_ptr,
-				      unsigned long input_size,
-				      unsigned long output_ptr,
-				      unsigned long output_size)
+static inline void choose_random_location(unsigned long input,
+					  unsigned long input_size,
+					  unsigned long *output,
+					  unsigned long output_size,
+					  unsigned long *virt_addr)
 {
-	return (unsigned char *)output_ptr;
+	/* No change from existing output location. */
+	*virt_addr = *output;
 }
 #endif
 
Signature · 1 line
2.6.3
author
#21 lore raw

PATCH v7 8/9 x86/KASLR: Add physical address randomization >4G

In reply to Kees Cook

This patch exchanges the prior slots[] array for the new slot_areas[] array, and lifts the limitation of KERNEL_IMAGE_SIZE on the physical address offset for 64-bit. As before, process_e820_entry() walks memory and populates slot_areas[], splitting on any detected mem_avoid collisions.

Finally, since the slots[] array and its associated functions are not needed any more, so they are removed.

Based on earlier patches by Baoquan He.

---
This patch is pretty noisy due to the indentation change in the e820 walker. I couldn't find a cleaner way to do this that didn't make the final code LESS readable, unfortunately. So, the diff is ugly, but I think the results are clean.

---
 arch/x86/Kconfig                 |  27 +++++----
 arch/x86/boot/compressed/kaslr.c | 115 +++++++++++++++++++++++----------------
 2 files changed, 85 insertions(+), 57 deletions(-)
arch/x86/Kconfig +16 -11
index 5892d549596d..bba81cf02b69 100644
@@ -1943,21 +1943,26 @@ config RANDOMIZE_BASE
 	  attempts relying on knowledge of the location of kernel
 	  code internals.
 
-	  The kernel physical and virtual address can be randomized
-	  from 16MB up to 1GB on 64-bit and 512MB on 32-bit. (Note that
-	  using RANDOMIZE_BASE reduces the memory space available to
-	  kernel modules from 1.5GB to 1GB.)
+	  On 64-bit, the kernel physical and virtual addresses are
+	  randomized separately. The physical address will be anywhere
+	  between 16MB and the top of physical memory (up to 64TB). The
+	  virtual address will be randomized from 16MB up to 1GB (9 bits
+	  of entropy). Note that this also reduces the memory space
+	  available to kernel modules from 1.5GB to 1GB.
+
+	  On 32-bit, the kernel physical and virtual addresses are
+	  randomized together. They will be randomized from 16MB up to
+	  512MB (8 bits of entropy).
 
 	  Entropy is generated using the RDRAND instruction if it is
 	  supported. If RDTSC is supported, its value is mixed into
 	  the entropy pool as well. If neither RDRAND nor RDTSC are
-	  supported, then entropy is read from the i8254 timer.
-
-	  Since the kernel is built using 2GB addressing, and
-	  PHYSICAL_ALIGN must be at a minimum of 2MB, only 10 bits of
-	  entropy is theoretically possible. Currently, with the
-	  default value for PHYSICAL_ALIGN and due to page table
-	  layouts, 64-bit uses 9 bits of entropy and 32-bit uses 8 bits.
+	  supported, then entropy is read from the i8254 timer. The
+	  usable entropy is limited by the kernel being built using
+	  2GB addressing, and that PHYSICAL_ALIGN must be at a
+	  minimum of 2MB. As a result, only 10 bits of entropy are
+	  theoretically possible, but the implementations are further
+	  limited due to memory layouts.
 
 	  If CONFIG_HIBERNATE is also enabled, KASLR is disabled at boot
 	  time. To enable it, boot with "kaslr" on the kernel command
arch/x86/boot/compressed/kaslr.c +69 -46

167 lines not on this page · raw message

Signature · 1 line
2.6.3
author
#22 lore raw

PATCH v7 9/9 x86/KASLR: Allow randomization below load address

In reply to Kees Cook

From: Yinghai Lu <[email protected]>

Currently the physical randomization's lower boundary is the original kernel load address. For bootloaders that load kernels into very high memory (e.g. kexec), this means randomization takes place in a very small window at the top of memory, ignoring the large region of physical memory below the load address.

Since mem_avoid is already correctly tracking the regions that must be avoided, this patch changes the minimum address to whatever is less:
512M (to conservatively avoid unknown things in lower memory) or the load address. Now, for example, if the kernel is loaded at 8G, [512M, 8G) will be added into possible physical memory positions.

[kees: rewrote changelog, refactor to use min()]
---
 arch/x86/boot/compressed/kaslr.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
arch/x86/boot/compressed/kaslr.c +5 -2
index def1da9e7863..d972a026d44c 100644
@@ -492,7 +492,7 @@ void choose_random_location(unsigned long input,
 			    unsigned long output_size,
 			    unsigned long *virt_addr)
 {
-	unsigned long random_addr;
+	unsigned long random_addr, min_addr;
 
 	/* By default, keep output position unchanged. */
 	*virt_addr = *output;
@@ -514,8 +514,11 @@ void choose_random_location(unsigned long input,
 	/* Record the various known unsafe memory ranges. */
 	mem_avoid_init(input, input_size, *output);
 
+	/* Low end should be the smaller of 512M or initial location. */
+	min_addr = min(*output, 512UL << 20);
+
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_phys_addr(*output, output_size);
+	random_addr = find_random_phys_addr(min_addr, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
 	} else {
Signature · 1 line
2.6.3