[PATCH v7 0/9] x86/KASLR: Randomize virtual address separately

[PATCH v7 0/9] x86/KASLR: Randomize virtual address separately

[Kees Cook]

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/

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

[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.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

diff --git a/arch/x86/boot/compressed/pagetable.c b/arch/x86/boot/compressed/pagetable.c
index 3c99051566a9..34b95df14e69 100644
--- a/arch/x86/boot/compressed/pagetable.c
+++ b/arch/x86/boot/compressed/pagetable.c
@@ -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. */
-- 
2.6.3

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

[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.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 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(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index f82975b0f9d6..3f0692dcd30d 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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
diff --git a/arch/x86/boot/early_serial_console.c b/arch/x86/boot/early_serial_console.c
index 45a07684bbab..f0b8d6d93164 100644
--- a/arch/x86/boot/early_serial_console.c
+++ b/arch/x86/boot/early_serial_console.c
@@ -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 */
diff --git a/arch/x86/mm/ident_map.c b/arch/x86/mm/ident_map.c
index 751ca920773a..ec21796ac5fd 100644
--- a/arch/x86/mm/ident_map.c
+++ b/arch/x86/mm/ident_map.c
@@ -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)
 {
-- 
2.6.3

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

[Kees Cook]

From: Baoquan He <bhe@redhat.com>

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.

Signed-off-by: Baoquan He <bhe@redhat.com>
[kees: rewrote changelog, squash with new functions]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 3f0692dcd30d..89f0148e3e84 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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. */
-- 
2.6.3

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

[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.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c | 29 ++++++++++++++++++++---------
 1 file changed, 20 insertions(+), 9 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 89f0148e3e84..1c02f07ce55a 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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);
 	}
-- 
2.6.3

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

[Kees Cook]

From: Baoquan He <bhe@redhat.com>

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().

Signed-off-by: Baoquan He <bhe@redhat.com>
[kees: rewrote changelog, refactor slot calculation for readability]
[kees: renamed find_random_phys_addr() and size argument]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 1c02f07ce55a..82d00282df3f 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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;
-- 
2.6.3

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

[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...

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 82d00282df3f..c4b1e4b05cb6 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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;
 }
-- 
2.6.3

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

[Kees Cook]

From: Baoquan He <bhe@redhat.com>

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.

Signed-off-by: Baoquan He <bhe@redhat.com>
[kees: rewrote changelog, limited virtual split to 64-bit only, update checks]
[kees: fix CONFIG_RANDOMIZE_BASE=n boot failure]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 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(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index c4b1e4b05cb6..1d1338f04bbd 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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;
 }
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index f14db4e21654..b3c5a5f030ce 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -170,7 +170,8 @@ void __puthex(unsigned long value)
 }
 
 #if CONFIG_X86_NEED_RELOCS
-static void handle_relocations(void *output, unsigned long output_len)
+static void handle_relocations(void *output, unsigned long output_len,
+			       unsigned long virt_addr)
 {
 	int *reloc;
 	unsigned long delta, map, ptr;
@@ -182,11 +183,6 @@ static void handle_relocations(void *output, unsigned long output_len)
 	 * and where it was actually loaded.
 	 */
 	delta = min_addr - LOAD_PHYSICAL_ADDR;
-	if (!delta) {
-		debug_putstr("No relocation needed... ");
-		return;
-	}
-	debug_putstr("Performing relocations... ");
 
 	/*
 	 * The kernel contains a table of relocation addresses. Those
@@ -198,6 +194,20 @@ static void handle_relocations(void *output, unsigned long output_len)
 	map = delta - __START_KERNEL_map;
 
 	/*
+	 * 32-bit always performs relocations. 64-bit relocations are only
+	 * needed if KASLR has chosen a different starting address offset
+	 * from __START_KERNEL_map.
+	 */
+	if (IS_ENABLED(CONFIG_X86_64))
+		delta = virt_addr - LOAD_PHYSICAL_ADDR;
+
+	if (!delta) {
+		debug_putstr("No relocation needed... ");
+		return;
+	}
+	debug_putstr("Performing relocations... ");
+
+	/*
 	 * Process relocations: 32 bit relocations first then 64 bit after.
 	 * Three sets of binary relocations are added to the end of the kernel
 	 * before compression. Each relocation table entry is the kernel
@@ -250,7 +260,8 @@ static void handle_relocations(void *output, unsigned long output_len)
 #endif
 }
 #else
-static inline void handle_relocations(void *output, unsigned long output_len)
+static inline void handle_relocations(void *output, unsigned long output_len,
+				      unsigned long virt_addr)
 { }
 #endif
 
@@ -327,7 +338,7 @@ asmlinkage __visible void *extract_kernel(void *rmode, memptr heap,
 				  unsigned long output_len)
 {
 	const unsigned long kernel_total_size = VO__end - VO__text;
-	unsigned char *output_orig = output;
+	unsigned long virt_addr = (unsigned long)output;
 
 	/* Retain x86 boot parameters pointer passed from startup_32/64. */
 	boot_params = rmode;
@@ -366,13 +377,16 @@ asmlinkage __visible void *extract_kernel(void *rmode, memptr heap,
 	 * the entire decompressed kernel plus relocation table, or the
 	 * entire decompressed kernel plus .bss and .brk sections.
 	 */
-	output = choose_random_location((unsigned long)input_data, input_len,
-					(unsigned long)output,
-					max(output_len, kernel_total_size));
+	choose_random_location((unsigned long)input_data, input_len,
+				(unsigned long *)&output,
+				max(output_len, kernel_total_size),
+				&virt_addr);
 
 	/* Validate memory location choices. */
 	if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1))
-		error("Destination address inappropriately aligned");
+		error("Destination physical address inappropriately aligned");
+	if (virt_addr & (MIN_KERNEL_ALIGN - 1))
+		error("Destination virtual address inappropriately aligned");
 #ifdef CONFIG_X86_64
 	if (heap > 0x3fffffffffffUL)
 		error("Destination address too large");
@@ -382,19 +396,16 @@ asmlinkage __visible void *extract_kernel(void *rmode, memptr heap,
 #endif
 #ifndef CONFIG_RELOCATABLE
 	if ((unsigned long)output != LOAD_PHYSICAL_ADDR)
-		error("Wrong destination address");
+		error("Destination address does not match LOAD_PHYSICAL_ADDR");
+	if ((unsigned long)output != virt_addr)
+		error("Destination virtual address changed when not relocatable");
 #endif
 
 	debug_putstr("\nDecompressing Linux... ");
 	__decompress(input_data, input_len, NULL, NULL, output, output_len,
 			NULL, error);
 	parse_elf(output);
-	/*
-	 * 32-bit always performs relocations. 64-bit relocations are only
-	 * needed if kASLR has chosen a different load address.
-	 */
-	if (!IS_ENABLED(CONFIG_X86_64) || output != output_orig)
-		handle_relocations(output, output_len);
+	handle_relocations(output, output_len, virt_addr);
 	debug_putstr("done.\nBooting the kernel.\n");
 	return output;
 }
diff --git a/arch/x86/boot/compressed/misc.h b/arch/x86/boot/compressed/misc.h
index b6fec1ff10e4..a6a5f3463c17 100644
--- a/arch/x86/boot/compressed/misc.h
+++ b/arch/x86/boot/compressed/misc.h
@@ -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
 
-- 
2.6.3

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

[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.

Cc: Baoquan He <bhe@redhat.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
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(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 5892d549596d..bba81cf02b69 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 1d1338f04bbd..def1da9e7863 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -132,17 +132,6 @@ enum mem_avoid_index {
 
 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 
-static bool mem_contains(struct mem_vector *region, struct mem_vector *item)
-{
-	/* Item at least partially before region. */
-	if (item->start < region->start)
-		return false;
-	/* Item at least partially after region. */
-	if (item->start + item->size > region->start + region->size)
-		return false;
-	return true;
-}
-
 static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
 {
 	/* Item one is entirely before item two. */
@@ -319,8 +308,6 @@ static bool mem_avoid_overlap(struct mem_vector *img,
 	return is_overlapping;
 }
 
-static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
-
 struct slot_area {
 	unsigned long addr;
 	int num;
@@ -351,36 +338,44 @@ static void store_slot_info(struct mem_vector *region, unsigned long image_size)
 	}
 }
 
-static void slots_append(unsigned long addr)
-{
-	/* Overflowing the slots list should be impossible. */
-	if (slot_max >= KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN)
-		return;
-
-	slots[slot_max++] = addr;
-}
-
 static unsigned long slots_fetch_random(void)
 {
+	unsigned long slot;
+	int i;
+
 	/* Handle case of no slots stored. */
 	if (slot_max == 0)
 		return 0;
 
-	return slots[get_random_long("Physical") % slot_max];
+	slot = get_random_long("Physical") % slot_max;
+
+	for (i = 0; i < slot_area_index; i++) {
+		if (slot >= slot_areas[i].num) {
+			slot -= slot_areas[i].num;
+			continue;
+		}
+		return slot_areas[i].addr + slot * CONFIG_PHYSICAL_ALIGN;
+	}
+
+	if (i == slot_area_index)
+		debug_putstr("slots_fetch_random() failed!?\n");
+	return 0;
 }
 
 static void process_e820_entry(struct e820entry *entry,
 			       unsigned long minimum,
 			       unsigned long image_size)
 {
-	struct mem_vector region, img, overlap;
+	struct mem_vector region, overlap;
+	struct slot_area slot_area;
+	unsigned long start_orig;
 
 	/* Skip non-RAM entries. */
 	if (entry->type != E820_RAM)
 		return;
 
-	/* Ignore entries entirely above our maximum. */
-	if (entry->addr >= KERNEL_IMAGE_SIZE)
+	/* On 32-bit, ignore entries entirely above our maximum. */
+	if (IS_ENABLED(CONFIG_X86_32) && entry->addr >= KERNEL_IMAGE_SIZE)
 		return;
 
 	/* Ignore entries entirely below our minimum. */
@@ -390,31 +385,55 @@ static void process_e820_entry(struct e820entry *entry,
 	region.start = entry->addr;
 	region.size = entry->size;
 
-	/* Potentially raise address to minimum location. */
-	if (region.start < minimum)
-		region.start = minimum;
+	/* Give up if slot area array is full. */
+	while (slot_area_index < MAX_SLOT_AREA) {
+		start_orig = region.start;
 
-	/* Potentially raise address to meet alignment requirements. */
-	region.start = ALIGN(region.start, CONFIG_PHYSICAL_ALIGN);
+		/* Potentially raise address to minimum location. */
+		if (region.start < minimum)
+			region.start = minimum;
 
-	/* Did we raise the address above the bounds of this e820 region? */
-	if (region.start > entry->addr + entry->size)
-		return;
+		/* Potentially raise address to meet alignment needs. */
+		region.start = ALIGN(region.start, CONFIG_PHYSICAL_ALIGN);
 
-	/* Reduce size by any delta from the original address. */
-	region.size -= region.start - entry->addr;
+		/* Did we raise the address above this e820 region? */
+		if (region.start > entry->addr + entry->size)
+			return;
 
-	/* Reduce maximum size to fit end of image within maximum limit. */
-	if (region.start + region.size > KERNEL_IMAGE_SIZE)
-		region.size = KERNEL_IMAGE_SIZE - region.start;
+		/* Reduce size by any delta from the original address. */
+		region.size -= region.start - start_orig;
 
-	/* Walk each aligned slot and check for avoided areas. */
-	for (img.start = region.start, img.size = image_size ;
-	     mem_contains(&region, &img) ;
-	     img.start += CONFIG_PHYSICAL_ALIGN) {
-		if (mem_avoid_overlap(&img, &overlap))
-			continue;
-		slots_append(img.start);
+		/* On 32-bit, reduce region size to fit within max size. */
+		if (IS_ENABLED(CONFIG_X86_32) &&
+		    region.start + region.size > KERNEL_IMAGE_SIZE)
+			region.size = KERNEL_IMAGE_SIZE - region.start;
+
+		/* Return if region can't contain decompressed kernel */
+		if (region.size < image_size)
+			return;
+
+		/* If nothing overlaps, store the region and return. */
+		if (!mem_avoid_overlap(&region, &overlap)) {
+			store_slot_info(&region, image_size);
+			return;
+		}
+
+		/* Store beginning of region if holds at least image_size. */
+		if (overlap.start > region.start + image_size) {
+			struct mem_vector beginning;
+
+			beginning.start = region.start;
+			beginning.size = overlap.start - region.start;
+			store_slot_info(&beginning, image_size);
+		}
+
+		/* Return if overlap extends to or past end of region. */
+		if (overlap.start + overlap.size >= region.start + region.size)
+			return;
+
+		/* Clip off the overlapping region and start over. */
+		region.size -= overlap.start - region.start + overlap.size;
+		region.start = overlap.start + overlap.size;
 	}
 }
 
@@ -431,6 +450,10 @@ static unsigned long find_random_phys_addr(unsigned long minimum,
 	for (i = 0; i < boot_params->e820_entries; i++) {
 		process_e820_entry(&boot_params->e820_map[i], minimum,
 				   image_size);
+		if (slot_area_index == MAX_SLOT_AREA) {
+			debug_putstr("Aborted e820 scan (slot_areas full)!\n");
+			break;
+		}
 	}
 
 	return slots_fetch_random();
-- 
2.6.3

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

[Kees Cook]

From: Yinghai Lu <yinghai@kernel.org>

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.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
[kees: rewrote changelog, refactor to use min()]
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/boot/compressed/kaslr.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index def1da9e7863..d972a026d44c 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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 {
-- 
2.6.3

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

[Yinghai Lu]

On Mon, May 9, 2016 at 1:22 PM, Kees Cook <keescook@chromium.org> wrote:
> 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.
>
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
>  1 file changed, 5 insertions(+), 11 deletions(-)
>
> diff --git a/arch/x86/boot/compressed/pagetable.c b/arch/x86/boot/compressed/pagetable.c
> index 3c99051566a9..34b95df14e69 100644
> --- a/arch/x86/boot/compressed/pagetable.c
> +++ b/arch/x86/boot/compressed/pagetable.c
> @@ -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;

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

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

[Yinghai Lu]

On Mon, May 9, 2016 at 3:01 PM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Mon, May 9, 2016 at 1:22 PM, Kees Cook <keescook@chromium.org> wrote:
>> 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.
>>
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>>  arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
>>  1 file changed, 5 insertions(+), 11 deletions(-)
>>
>> diff --git a/arch/x86/boot/compressed/pagetable.c b/arch/x86/boot/compressed/pagetable.c
>> index 3c99051566a9..34b95df14e69 100644
>> --- a/arch/x86/boot/compressed/pagetable.c
>> +++ b/arch/x86/boot/compressed/pagetable.c
>> @@ -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;
>
> 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:

-/*
- * 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);

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

[Kees Cook]

On Mon, May 9, 2016 at 3:01 PM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Mon, May 9, 2016 at 1:22 PM, Kees Cook <keescook@chromium.org> wrote:
>> 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.
>>
>> Signed-off-by: Kees Cook <keescook@chromium.org>
>> ---
>>  arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
>>  1 file changed, 5 insertions(+), 11 deletions(-)
>>
>> diff --git a/arch/x86/boot/compressed/pagetable.c b/arch/x86/boot/compressed/pagetable.c
>> index 3c99051566a9..34b95df14e69 100644
>> --- a/arch/x86/boot/compressed/pagetable.c
>> +++ b/arch/x86/boot/compressed/pagetable.c
>> @@ -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;
>
> 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.

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

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

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

[Yinghai Lu]

On Mon, May 9, 2016 at 3:23 PM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Mon, May 9, 2016 at 3:01 PM, Yinghai Lu <yinghai@kernel.org> wrote:

>> 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:
>
> -/*
> - * 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);

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

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

[Yinghai Lu]

On Mon, May 9, 2016 at 3:23 PM, Kees Cook <keescook@chromium.org> wrote:
>> 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

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

[Ingo Molnar]

* Yinghai Lu <yinghai@kernel.org> wrote:

> On Mon, May 9, 2016 at 3:23 PM, Kees Cook <keescook@chromium.org> wrote:
> >> 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

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

[tip-bot for Kees Cook]

Commit-ID:  434a6c9f90f7ab5ade619455df01ef5ebea533ee
Gitweb:     http://git.kernel.org/tip/434a6c9f90f7ab5ade619455df01ef5ebea533ee
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Mon, 9 May 2016 13:22:04 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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.

Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-2-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/pagetable.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

diff --git a/arch/x86/boot/compressed/pagetable.c b/arch/x86/boot/compressed/pagetable.c
index 3c99051..34b95df 100644
--- a/arch/x86/boot/compressed/pagetable.c
+++ b/arch/x86/boot/compressed/pagetable.c
@@ -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. */

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

[tip-bot for Kees Cook]

Commit-ID:  cb18ef0da259db611fbf52806592fde5f469ae67
Gitweb:     http://git.kernel.org/tip/cb18ef0da259db611fbf52806592fde5f469ae67
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Mon, 9 May 2016 13:22:05 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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.

Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-3-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 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(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index f5a138c..f15d7b8 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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
diff --git a/arch/x86/boot/early_serial_console.c b/arch/x86/boot/early_serial_console.c
index 45a0768..f0b8d6d 100644
--- a/arch/x86/boot/early_serial_console.c
+++ b/arch/x86/boot/early_serial_console.c
@@ -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 */
diff --git a/arch/x86/mm/ident_map.c b/arch/x86/mm/ident_map.c
index 751ca92..ec21796 100644
--- a/arch/x86/mm/ident_map.c
+++ b/arch/x86/mm/ident_map.c
@@ -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)
 {

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

[tip-bot for Baoquan He]

Commit-ID:  c401cf1524153f9c2ede7ab8ece403513925770a
Gitweb:     http://git.kernel.org/tip/c401cf1524153f9c2ede7ab8ece403513925770a
Author:     Baoquan He <bhe@redhat.com>
AuthorDate: Mon, 9 May 2016 13:22:06 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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.

Signed-off-by: Baoquan He <bhe@redhat.com>
[ Rewrote changelog, squashed with new functions. ]
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-4-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index f15d7b8..81edf99 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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. */

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

[tip-bot for Kees Cook]

Commit-ID:  06486d6c97cebc2433a40a979f3849cd68184de9
Gitweb:     http://git.kernel.org/tip/06486d6c97cebc2433a40a979f3849cd68184de9
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Mon, 9 May 2016 13:22:07 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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.

Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-5-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c | 29 ++++++++++++++++++++---------
 1 file changed, 20 insertions(+), 9 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 81edf99..e55ebcb 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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);
 	}

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

[tip-bot for Baoquan He]

Commit-ID:  071a74930e60d1fa51207d71f00a35b4f9d4d179
Gitweb:     http://git.kernel.org/tip/071a74930e60d1fa51207d71f00a35b4f9d4d179
Author:     Baoquan He <bhe@redhat.com>
AuthorDate: Mon, 9 May 2016 13:22:08 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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().

Signed-off-by: Baoquan He <bhe@redhat.com>
[ Rewrote changelog, refactored slot calculation for readability. ]
[ Renamed find_random_phys_addr() and size argument. ]
Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-6-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index e55ebcb..016a4f4 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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;

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

[tip-bot for Kees Cook]

Commit-ID:  d2d3462f9f08da364c8fbd41e8e32229d610d49d
Gitweb:     http://git.kernel.org/tip/d2d3462f9f08da364c8fbd41e8e32229d610d49d
Author:     Kees Cook <keescook@chromium.org>
AuthorDate: Mon, 9 May 2016 13:22:09 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
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...

Signed-off-by: Kees Cook <keescook@chromium.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Baoquan He <bhe@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Borislav Petkov <bp@suse.de>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Dave Young <dyoung@redhat.com>
Cc: Denys Vlasenko <dvlasenk@redhat.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vivek Goyal <vgoyal@redhat.com>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: kernel-hardening@lists.openwall.com
Cc: lasse.collin@tukaani.org
Link: http://lkml.kernel.org/r/1462825332-10505-7-git-send-email-keescook@chromium.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/boot/compressed/kaslr.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 016a4f4..cfeb025 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -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;
 }

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

[Borislav Petkov]

On Tue, May 10, 2016 at 07:58:54AM +0200, Ingo Molnar wrote:
> 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.

-- 
Regards/Gruss,
    Boris.

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