Skip to contentSkip to conversation

x86/KASLR: Randomize virtual address separately

PATCH Superseded Kees Cook 5 participants 29 messages May 5, 2016 – May 8, 2016

Subsystems (2)

v6 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Kees Cook

author
#0 lore raw

v6 cover x86/KASLR: Randomize virtual address separately

This is v6 of the x86 KASLR improvement series from Yinghai, Baoquan, and myself. The current branch lives here:
http://git.kernel.org/cgit/linux/kernel/git/kees/linux.git/log/?h=kaslr/highmem

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

- 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 prepares the code for more invasive changes.

     (Patches 01-02)

- The 2nd part is Yinghai's building of identity mappings on demand, fixing problem #1 above.
(Patches 03-04)
- The 3rd part is Baoquan's new randomization slot management code for handling the much larger possible memory space.
(Patches 05-06)
- 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 07-09)
- The 5th part lifts the upper and lower limits on physical addresses, fixing problem #3 above.
(Patches 10-11)

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

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 v6 1/11 x86/boot: Clean up pointer casting

Currently extract_kernel() defines the input and output buffer pointers as "unsigned char *" since that's effectively what they are. It passes these to the decompressor routine and to the ELF parser, which both logically deal with buffer pointers too. There is some casting ("unsigned long") done to validate the numerical value of the pointers, but it is relatively limited.

However, choose_random_location() operates almost exclusively on the numerical representation of these pointers, so it ended up carrying a lot of "unsigned long" casts. With the future physical/virtual split these casts were going to multiply, so this attempts to solve the problem by doing all the casting in choose_random_location()'s entry and return instead of through-out the code. Adjusts argument names to be more meaningful, and changes one us of "choice" to "output" to make the future physical/virtual split more clear (i.e. "choice" should be strictly a function return value and not used as an intermediate).

---
 arch/x86/boot/compressed/kaslr.c | 20 ++++++++++++++------
 arch/x86/boot/compressed/misc.h  | 10 +++++-----
 2 files changed, 19 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/kaslr.c +14 -6
index f1818d95d726..2072d82c1911 100644
@@ -305,12 +305,21 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size)
 {
-	unsigned long choice = (unsigned long)output;
+	/*
+	 * The caller of choose_random_location() uses unsigned char * for
+	 * buffer pointers since it performs decompression, elf parsing, etc.
+	 * Since this code examines addresses much more numerically,
+	 * unsigned long is used internally here. Instead of sprinkling
+	 * more casts into extract_kernel, do them here and at return.
+	 */
+	unsigned long input = (unsigned long)input_ptr;
+	unsigned long output = (unsigned long)output_ptr;
+	unsigned long choice = output;
 	unsigned long random_addr;
 
 #ifdef CONFIG_HIBERNATION
@@ -328,11 +337,10 @@ unsigned char *choose_random_location(unsigned char *input,
 	boot_params->hdr.loadflags |= KASLR_FLAG;
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init((unsigned long)input, input_size,
-		       (unsigned long)output, output_size);
+	mem_avoid_init(input, input_size, output, output_size);
 
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_addr(choice, output_size);
+	random_addr = find_random_addr(output, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
arch/x86/boot/compressed/misc.h +5 -5
index 9887e0d4aaeb..1f23d022d241 100644
@@ -67,20 +67,20 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
 static inline
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size)
 {
-	return output;
+	return output_ptr;
 }
 #endif
 
Signature · 1 line
2.6.3
#2 lore raw

[tip:x86/boot] x86/boot: Clean up pointer casting

x86/boot: Clean up pointer casting
Commit-ID:  2bc1cd39fa9f659956b25e500422e700a6cd4ec3
Gitweb:     http://git.kernel.org/tip/2bc1cd39fa9f659956b25e500422e700a6cd4ec3
Author:     Kees Cook <[email protected]>
AuthorDate: Thu, 5 May 2016 15:13:46 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 6 May 2016 09:00:59 +0200

x86/boot: Clean up pointer casting

Currently extract_kernel() defines the input and output buffer pointers as "unsigned char *" since that's effectively what they are. It passes these to the decompressor routine and to the ELF parser, which both logically deal with buffer pointers too. There is some casting ("unsigned long") done to validate the numerical value of the pointers, but it is relatively limited.

However, choose_random_location() operates almost exclusively on the numerical representation of these pointers, so it ended up carrying a lot of "unsigned long" casts. With the future physical/virtual split these casts were going to multiply, so this attempts to solve the problem by doing all the casting in choose_random_location()'s entry and return instead of through-out the code. Adjusts argument names to be more meaningful, and changes one us of "choice" to "output" to make the future physical/virtual split more clear (i.e. "choice" should be strictly a function return value and not used as an intermediate).

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 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 | 20 ++++++++++++++------
 arch/x86/boot/compressed/misc.h  | 10 +++++-----
 2 files changed, 19 insertions(+), 11 deletions(-)
arch/x86/boot/compressed/kaslr.c +14 -6
index f1818d9..2072d82 100644
@@ -305,12 +305,21 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size)
 {
-	unsigned long choice = (unsigned long)output;
+	/*
+	 * The caller of choose_random_location() uses unsigned char * for
+	 * buffer pointers since it performs decompression, elf parsing, etc.
+	 * Since this code examines addresses much more numerically,
+	 * unsigned long is used internally here. Instead of sprinkling
+	 * more casts into extract_kernel, do them here and at return.
+	 */
+	unsigned long input = (unsigned long)input_ptr;
+	unsigned long output = (unsigned long)output_ptr;
+	unsigned long choice = output;
 	unsigned long random_addr;
 
 #ifdef CONFIG_HIBERNATION
@@ -328,11 +337,10 @@ unsigned char *choose_random_location(unsigned char *input,
 	boot_params->hdr.loadflags |= KASLR_FLAG;
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init((unsigned long)input, input_size,
-		       (unsigned long)output, output_size);
+	mem_avoid_init(input, input_size, output, output_size);
 
 	/* Walk e820 and find a random address. */
-	random_addr = find_random_addr(choice, output_size);
+	random_addr = find_random_addr(output, output_size);
 	if (!random_addr) {
 		warn("KASLR disabled: could not find suitable E820 region!");
 		goto out;
arch/x86/boot/compressed/misc.h +5 -5
index 9887e0d..1f23d02 100644
@@ -67,20 +67,20 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
 static inline
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size)
 {
-	return output;
+	return output_ptr;
 }
 #endif
 
maintainer
#3 lore raw

Re: [tip:x86/boot] x86/boot: Clean up pointer casting

Quoted 8 lines · tip-bot for Kees Cook
Commit-ID:  2bc1cd39fa9f659956b25e500422e700a6cd4ec3
Gitweb:     http://git.kernel.org/tip/2bc1cd39fa9f659956b25e500422e700a6cd4ec3
Author:     Kees Cook <[email protected]>
AuthorDate: Thu, 5 May 2016 15:13:46 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 6 May 2016 09:00:59 +0200

x86/boot: Clean up pointer casting

...

Quoted 15 lines
arch/x86/boot/compressed/kaslr.c +2 -2
index f1818d9..2072d82 100644
@@ -305,12 +305,21 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input,
+unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output,
+				      unsigned char *output_ptr,
 				      unsigned long output_size)
 {

arch/x86/boot/compressed/kaslr.c static unsigned long find_random_addr(unsigned long minimum, · line 321

Quoted 10 lines
arch/x86/boot/compressed/kaslr.c +9 -1
-	unsigned long choice = (unsigned long)output;
+	/*
+	 * The caller of choose_random_location() uses unsigned char * for
+	 * buffer pointers since it performs decompression, elf parsing, etc.
+	 * Since this code examines addresses much more numerically,
+	 * unsigned long is used internally here. Instead of sprinkling
+	 * more casts into extract_kernel, do them here and at return.
+	 */
+	unsigned long input = (unsigned long)input_ptr;
+	unsigned long output = (unsigned long)output_ptr;

This can be simplified even further:

---
From: Borislav Petkov <[email protected]>
Date: Fri, 6 May 2016 10:43:21 +0200
Subject: [PATCH] x86/boot: Simplify pointer casting in
choose_random_location()

Pass them down as unsigned long directly and get rid of more casting and assignments.

---
 arch/x86/boot/compressed/kaslr.c | 17 ++++++-----------
 arch/x86/boot/compressed/misc.c  |  3 ++-
 arch/x86/boot/compressed/misc.h  |  8 ++++----
 3 files changed, 12 insertions(+), 16 deletions(-)
arch/x86/boot/compressed/kaslr.c +6 -11
index 6392f0041b8a..a49f48317dad 100644
@@ -350,20 +350,15 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input_ptr,
+/*
+ * 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 char *output_ptr,
+				      unsigned long output,
 				      unsigned long output_size)
 {
-	/*
-	 * The caller of choose_random_location() uses unsigned char * for
-	 * buffer pointers since it performs decompression, elf parsing, etc.
-	 * Since this code examines addresses much more numerically,
-	 * unsigned long is used internally here. Instead of sprinkling
-	 * more casts into extract_kernel, do them here and at return.
-	 */
-	unsigned long input = (unsigned long)input_ptr;
-	unsigned long output = (unsigned long)output_ptr;
 	unsigned long choice = output;
 	unsigned long random_addr;
 
arch/x86/boot/compressed/misc.c +2 -1
index 9536d778149e..f14db4e21654 100644
@@ -366,7 +366,8 @@ 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(input_data, input_len, output,
+	output = choose_random_location((unsigned long)input_data, input_len,
+					(unsigned long)output,
 					max(output_len, kernel_total_size));
 
 	/* Validate memory location choices. */
arch/x86/boot/compressed/misc.h +4 -4
index 1f23d022d241..1c793463328b 100644
@@ -67,17 +67,17 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
 static inline
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size)
 {
 	return output_ptr;
Signature · 7 lines
2.7.3

-- 
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
#4 lore raw

Re: [tip:x86/boot] x86/boot: Clean up pointer casting

Quoted 8 lines · Borislav Petkov

This can be simplified even further:

---
From: Borislav Petkov <[email protected]>
Date: Fri, 6 May 2016 10:43:21 +0200
Subject: [PATCH] x86/boot: Simplify pointer casting in
choose_random_location()

Quoted 8 lines

Pass them down as unsigned long directly and get rid of more casting and assignments.

 arch/x86/boot/compressed/misc.h  |  8 ++++----
 3 files changed, 12 insertions(+), 16 deletions(-)

Great, thanks!

Ingo

author
#5 lore raw

Re: [tip:x86/boot] x86/boot: Clean up pointer casting

Quoted 14 lines · Ingo Molnar
Quoted 11 lines · Borislav Petkov

This can be simplified even further:

---
From: Borislav Petkov <[email protected]>
Date: Fri, 6 May 2016 10:43:21 +0200
Subject: [PATCH] x86/boot: Simplify pointer casting in
choose_random_location()

Pass them down as unsigned long directly and get rid of more casting and assignments.

Quoted 7 lines
Quoted 5 lines
 arch/x86/boot/compressed/misc.h  |  8 ++++----
 3 files changed, 12 insertions(+), 16 deletions(-)

Great, thanks!

Thanks! Yeah, I did that originally, but then extract_kernel() was filled with casts, so I took a stab at it. I do prefer the casts being done in extract_kernel(), though. I was just worried Ingo won't like it. :)

-Kees

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

Re: [tip:x86/boot] x86/boot: Clean up pointer casting

In reply to Borislav Petkov

Hm, your patch throws a lot of warnings during allnoconfig builds:

In file included from arch/x86/boot/compressed/error.c:6:0:
arch/x86/boot/compressed/misc.h: In function ‘choose_random_location’:
arch/x86/boot/compressed/misc.h:83:9: warning: return makes pointer from integer without a cast [-Wint-conversion]

  return output_ptr;
         ^

In file included from arch/x86/boot/compressed/early_serial_console.c:1:0:
arch/x86/boot/compressed/misc.h: In function ‘choose_random_location’:
arch/x86/boot/compressed/misc.h:83:9: warning: return makes pointer from integer without a cast [-Wint-conversion]

  return output_ptr;
         ^

CC arch/x86/boot/compressed/misc.o
In file included from arch/x86/boot/compressed/cmdline.c:1:0:
arch/x86/boot/compressed/misc.h: In function ‘choose_random_location’:
arch/x86/boot/compressed/misc.h:83:9: warning: return makes pointer from integer without a cast [-Wint-conversion]

  return output_ptr;
         ^

In file included from arch/x86/boot/compressed/misc.c:14:0:
arch/x86/boot/compressed/misc.h: In function ‘choose_random_location’:
arch/x86/boot/compressed/misc.h:83:9: warning: return makes pointer from integer without a cast [-Wint-conversion]
return output_ptr;

Thanks,

Ingo

maintainer
#7 lore raw

Re: [tip:x86/boot] x86/boot: Clean up pointer casting

Quoted 9 lines · Ingo Molnar

Hm, your patch throws a lot of warnings during allnoconfig builds:

In file included from arch/x86/boot/compressed/error.c:6:0:
arch/x86/boot/compressed/misc.h: In function ‘choose_random_location’:
arch/x86/boot/compressed/misc.h:83:9: warning: return makes pointer from integer without a cast [-Wint-conversion]

  return output_ptr;
         ^

Blergh, that's when choose_random_location() is a stub and it needs to do

	return (unsigned char *)output_ptr;

too.

Lemme run all the *config builds on the fixed version before I send you a v2.

Thanks.

Signature · 4 lines
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
maintainer
#8 lore raw

PATCH 1/1 x86/boot: Simplify pointer casting in choose_random_location()

From: Borislav Petkov <[email protected]>

Pass them down as unsigned long directly and get rid of more casting and assignments.

---
 arch/x86/boot/compressed/kaslr.c | 17 ++++++-----------
 arch/x86/boot/compressed/misc.c  |  3 ++-
 arch/x86/boot/compressed/misc.h  | 10 +++++-----
 3 files changed, 13 insertions(+), 17 deletions(-)
arch/x86/boot/compressed/kaslr.c +6 -11
index 6392f0041b8a..a49f48317dad 100644
@@ -350,20 +350,15 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input_ptr,
+/*
+ * 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 char *output_ptr,
+				      unsigned long output,
 				      unsigned long output_size)
 {
-	/*
-	 * The caller of choose_random_location() uses unsigned char * for
-	 * buffer pointers since it performs decompression, elf parsing, etc.
-	 * Since this code examines addresses much more numerically,
-	 * unsigned long is used internally here. Instead of sprinkling
-	 * more casts into extract_kernel, do them here and at return.
-	 */
-	unsigned long input = (unsigned long)input_ptr;
-	unsigned long output = (unsigned long)output_ptr;
 	unsigned long choice = output;
 	unsigned long random_addr;
 
arch/x86/boot/compressed/misc.c +2 -1
index 9536d778149e..f14db4e21654 100644
@@ -366,7 +366,8 @@ 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(input_data, input_len, output,
+	output = choose_random_location((unsigned long)input_data, input_len,
+					(unsigned long)output,
 					max(output_len, kernel_total_size));
 
 	/* Validate memory location choices. */
arch/x86/boot/compressed/misc.h +5 -5
index 1f23d022d241..0112005a3f23 100644
@@ -67,20 +67,20 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
 static inline
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size)
 {
-	return output_ptr;
+	return (unsigned char *)output_ptr;
 }
 #endif
 
Signature · 7 lines
2.7.3

-- 
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
#9 lore raw

[tip:x86/boot] x86/boot: Simplify pointer casting in choose_random_location()

x86/boot: Simplify pointer casting in choose_random_location()
Commit-ID:  549f90db68c9f8e21a40ec21c8047441984e7164
Gitweb:     http://git.kernel.org/tip/549f90db68c9f8e21a40ec21c8047441984e7164
Author:     Borislav Petkov <[email protected]>
AuthorDate: Fri, 6 May 2016 13:50:15 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Sat, 7 May 2016 07:38:38 +0200

x86/boot: Simplify pointer casting in choose_random_location()

Pass them down as 'unsigned long' directly and get rid of more casting and assignments.

---
 arch/x86/boot/compressed/kaslr.c | 17 ++++++-----------
 arch/x86/boot/compressed/misc.c  |  3 ++-
 arch/x86/boot/compressed/misc.h  | 10 +++++-----
 3 files changed, 13 insertions(+), 17 deletions(-)
arch/x86/boot/compressed/kaslr.c +6 -11
index 6392f00..ff12277 100644
@@ -350,20 +350,15 @@ static unsigned long find_random_addr(unsigned long minimum,
 	return slots_fetch_random();
 }
 
-unsigned char *choose_random_location(unsigned char *input_ptr,
+/*
+ * 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 char *output_ptr,
+				      unsigned long output,
 				      unsigned long output_size)
 {
-	/*
-	 * The caller of choose_random_location() uses unsigned char * for
-	 * buffer pointers since it performs decompression, elf parsing, etc.
-	 * Since this code examines addresses much more numerically,
-	 * unsigned long is used internally here. Instead of sprinkling
-	 * more casts into extract_kernel, do them here and at return.
-	 */
-	unsigned long input = (unsigned long)input_ptr;
-	unsigned long output = (unsigned long)output_ptr;
 	unsigned long choice = output;
 	unsigned long random_addr;
 
arch/x86/boot/compressed/misc.c +2 -1
index 9536d77..f14db4e 100644
@@ -366,7 +366,8 @@ 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(input_data, input_len, output,
+	output = choose_random_location((unsigned long)input_data, input_len,
+					(unsigned long)output,
 					max(output_len, kernel_total_size));
 
 	/* Validate memory location choices. */
arch/x86/boot/compressed/misc.h +5 -5
index 1f23d02..0112005a 100644
@@ -67,20 +67,20 @@ int cmdline_find_option_bool(const char *option);
 
 #if CONFIG_RANDOMIZE_BASE
 /* kaslr.c */
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
 static inline
-unsigned char *choose_random_location(unsigned char *input_ptr,
+unsigned char *choose_random_location(unsigned long input_ptr,
 				      unsigned long input_size,
-				      unsigned char *output_ptr,
+				      unsigned long output_ptr,
 				      unsigned long output_size)
 {
-	return output_ptr;
+	return (unsigned char *)output_ptr;
 }
 #endif
 
author
#10 lore raw

PATCH v6 2/11 x86/KASLR: Consolidate mem_avoid entries

In reply to Kees Cook

From: Yinghai Lu <[email protected]>

The mem_avoid array is used to track positions that should be avoided (like the compressed kernel, decompression code, etc) when selecting a memory position for the randomly relocated kernel. Since ZO is now at the end of the decompression buffer and the decompression code (and its heap and stack) are at the front, we can safely consolidate the decompression entry, the heap entry, and the stack entry. The boot_params memory, however, could be elsewhere, so it should be explicitly included.

Cc Kees Cook <[email protected]>
[kees: rewrote changelog, cleaned up code comment]
---
 arch/x86/boot/compressed/kaslr.c | 77 +++++++++++++++++++++++++++++++---------
 1 file changed, 61 insertions(+), 16 deletions(-)
arch/x86/boot/compressed/kaslr.c +61 -16
index 2072d82c1911..6392f0041b8a 100644
@@ -121,7 +121,7 @@ struct mem_vector {
 	unsigned long size;
 };
 
-#define MEM_AVOID_MAX 5
+#define MEM_AVOID_MAX 4
 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 
 static bool mem_contains(struct mem_vector *region, struct mem_vector *item)
@@ -146,22 +146,71 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
 	return true;
 }
 
+/*
+ * In theroy, KASLR can put the kernel anywhere in area of [16M, 64T). The
+ * mem_avoid array is used to store the ranges that need to be avoided when
+ * KASLR searches for a an appropriate random address. We must avoid any
+ * regions that are unsafe to overlap with during decompression, and other
+ * things like the initrd, cmdline and boot_params.
+ *
+ * How to calculate the unsafe areas is detailed here, and is informed by
+ * the decompression calculations in header.S, and the diagram in misc.c.
+ *
+ * The compressed vmlinux (ZO) plus relocs and the run space of ZO can't be
+ * overwritten by decompression output.
+ *
+ * ZO sits against the end of the decompression buffer, so we can calculate
+ * where text, data, bss, etc of ZO are positioned.
+ *
+ * The follow are already enforced by the code:
+ *  - init_size >= kernel_total_size
+ *  - input + input_len >= output + output_len
+ *  - kernel_total_size could be >= or < output_len
+ *
+ * From this, we can make several observations, illustrated by a diagram:
+ *  - init_size >= kernel_total_size
+ *  - input + input_len > output + output_len
+ *  - kernel_total_size >= output_len
+ *
+ * 0   output            input            input+input_len    output+init_size
+ * |     |                 |                       |                       |
+ * |     |                 |                       |                       |
+ * |-----|--------|--------|------------------|----|------------|----------|
+ *                |                           |                 |
+ *                |                           |                 |
+ * output+init_size-ZO_INIT_SIZE   output+output_len  output+kernel_total_size
+ *
+ * [output, output+init_size) is for the buffer for decompressing the
+ * compressed kernel (ZO).
+ *
+ * [output, output+kernel_total_size) is for the uncompressed kernel (VO)
+ * and its bss, brk, etc.
+ * [output, output+output_len) is VO plus relocs
+ *
+ * [output+init_size-ZO_INIT_SIZE, output+init_size) is the copied ZO.
+ * [input, input+input_len) is the copied compressed (VO (vmlinux after
+ * objcopy) plus relocs), not the ZO.
+ *
+ * [input+input_len, output+init_size) is [_text, _end) for ZO. That was the
+ * first range in mem_avoid, which included ZO's heap and stack. Also
+ * [input, input+input_size) need be put in mem_avoid array, but since it
+ * is adjacent to the first entry, they can be merged. This is how we get
+ * the first entry in mem_avoid[].
+ */
 static void mem_avoid_init(unsigned long input, unsigned long input_size,
-			   unsigned long output, unsigned long output_size)
+			   unsigned long output)
 {
+	unsigned long init_size = boot_params->hdr.init_size;
 	u64 initrd_start, initrd_size;
 	u64 cmd_line, cmd_line_size;
-	unsigned long unsafe, unsafe_len;
 	char *ptr;
 
 	/*
 	 * Avoid the region that is unsafe to overlap during
-	 * decompression (see calculations in ../header.S).
+	 * decompression.
 	 */
-	unsafe_len = (output_size >> 12) + 32768 + 18;
-	unsafe = (unsigned long)input + input_size - unsafe_len;
-	mem_avoid[0].start = unsafe;
-	mem_avoid[0].size = unsafe_len;
+	mem_avoid[0].start = input;
+	mem_avoid[0].size = (output + init_size) - input;
 
 	/* Avoid initrd. */
 	initrd_start  = (u64)boot_params->ext_ramdisk_image << 32;
@@ -181,13 +230,9 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 	mem_avoid[2].start = cmd_line;
 	mem_avoid[2].size = cmd_line_size;
 
-	/* Avoid heap memory. */
-	mem_avoid[3].start = (unsigned long)free_mem_ptr;
-	mem_avoid[3].size = BOOT_HEAP_SIZE;
-
-	/* Avoid stack memory. */
-	mem_avoid[4].start = (unsigned long)free_mem_end_ptr;
-	mem_avoid[4].size = BOOT_STACK_SIZE;
+	/* Avoid params */
+	mem_avoid[3].start = (unsigned long)boot_params;
+	mem_avoid[3].size = sizeof(*boot_params);
 }
 
 /* Does this memory vector overlap a known avoided area? */
@@ -337,7 +382,7 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 	boot_params->hdr.loadflags |= KASLR_FLAG;
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init(input, input_size, output, output_size);
+	mem_avoid_init(input, input_size, output);
 
 	/* Walk e820 and find a random address. */
 	random_addr = find_random_addr(output, output_size);
Signature · 1 line
2.6.3
#11 lore raw

[tip:x86/boot] x86/KASLR: Consolidate mem_avoid[] entries

x86/KASLR: Consolidate mem_avoid[] entries
Commit-ID:  9dc1969c24eff8b7d7a9a565d1047b624921ba06
Gitweb:     http://git.kernel.org/tip/9dc1969c24eff8b7d7a9a565d1047b624921ba06
Author:     Yinghai Lu <[email protected]>
AuthorDate: Thu, 5 May 2016 15:13:47 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 6 May 2016 09:00:59 +0200

x86/KASLR: Consolidate mem_avoid[] entries

The mem_avoid[] array is used to track positions that should be avoided (like the compressed kernel, decompression code, etc) when selecting a memory position for the randomly relocated kernel. Since ZO is now at the end of the decompression buffer and the decompression code (and its heap and stack) are at the front, we can safely consolidate the decompression entry, the heap entry, and the stack entry. The boot_params memory, however, could be elsewhere, so it should be explicitly included.

[ Rwrote changelog, cleaned up code comments. ]
Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[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]>
---
 arch/x86/boot/compressed/kaslr.c | 77 +++++++++++++++++++++++++++++++---------
 1 file changed, 61 insertions(+), 16 deletions(-)
arch/x86/boot/compressed/kaslr.c +61 -16
index 2072d82..6392f00 100644
@@ -121,7 +121,7 @@ struct mem_vector {
 	unsigned long size;
 };
 
-#define MEM_AVOID_MAX 5
+#define MEM_AVOID_MAX 4
 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 
 static bool mem_contains(struct mem_vector *region, struct mem_vector *item)
@@ -146,22 +146,71 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
 	return true;
 }
 
+/*
+ * In theroy, KASLR can put the kernel anywhere in area of [16M, 64T). The
+ * mem_avoid array is used to store the ranges that need to be avoided when
+ * KASLR searches for a an appropriate random address. We must avoid any
+ * regions that are unsafe to overlap with during decompression, and other
+ * things like the initrd, cmdline and boot_params.
+ *
+ * How to calculate the unsafe areas is detailed here, and is informed by
+ * the decompression calculations in header.S, and the diagram in misc.c.
+ *
+ * The compressed vmlinux (ZO) plus relocs and the run space of ZO can't be
+ * overwritten by decompression output.
+ *
+ * ZO sits against the end of the decompression buffer, so we can calculate
+ * where text, data, bss, etc of ZO are positioned.
+ *
+ * The follow are already enforced by the code:
+ *  - init_size >= kernel_total_size
+ *  - input + input_len >= output + output_len
+ *  - kernel_total_size could be >= or < output_len
+ *
+ * From this, we can make several observations, illustrated by a diagram:
+ *  - init_size >= kernel_total_size
+ *  - input + input_len > output + output_len
+ *  - kernel_total_size >= output_len
+ *
+ * 0   output            input            input+input_len    output+init_size
+ * |     |                 |                       |                       |
+ * |     |                 |                       |                       |
+ * |-----|--------|--------|------------------|----|------------|----------|
+ *                |                           |                 |
+ *                |                           |                 |
+ * output+init_size-ZO_INIT_SIZE   output+output_len  output+kernel_total_size
+ *
+ * [output, output+init_size) is for the buffer for decompressing the
+ * compressed kernel (ZO).
+ *
+ * [output, output+kernel_total_size) is for the uncompressed kernel (VO)
+ * and its bss, brk, etc.
+ * [output, output+output_len) is VO plus relocs
+ *
+ * [output+init_size-ZO_INIT_SIZE, output+init_size) is the copied ZO.
+ * [input, input+input_len) is the copied compressed (VO (vmlinux after
+ * objcopy) plus relocs), not the ZO.
+ *
+ * [input+input_len, output+init_size) is [_text, _end) for ZO. That was the
+ * first range in mem_avoid, which included ZO's heap and stack. Also
+ * [input, input+input_size) need be put in mem_avoid array, but since it
+ * is adjacent to the first entry, they can be merged. This is how we get
+ * the first entry in mem_avoid[].
+ */
 static void mem_avoid_init(unsigned long input, unsigned long input_size,
-			   unsigned long output, unsigned long output_size)
+			   unsigned long output)
 {
+	unsigned long init_size = boot_params->hdr.init_size;
 	u64 initrd_start, initrd_size;
 	u64 cmd_line, cmd_line_size;
-	unsigned long unsafe, unsafe_len;
 	char *ptr;
 
 	/*
 	 * Avoid the region that is unsafe to overlap during
-	 * decompression (see calculations in ../header.S).
+	 * decompression.
 	 */
-	unsafe_len = (output_size >> 12) + 32768 + 18;
-	unsafe = (unsigned long)input + input_size - unsafe_len;
-	mem_avoid[0].start = unsafe;
-	mem_avoid[0].size = unsafe_len;
+	mem_avoid[0].start = input;
+	mem_avoid[0].size = (output + init_size) - input;
 
 	/* Avoid initrd. */
 	initrd_start  = (u64)boot_params->ext_ramdisk_image << 32;
@@ -181,13 +230,9 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 	mem_avoid[2].start = cmd_line;
 	mem_avoid[2].size = cmd_line_size;
 
-	/* Avoid heap memory. */
-	mem_avoid[3].start = (unsigned long)free_mem_ptr;
-	mem_avoid[3].size = BOOT_HEAP_SIZE;
-
-	/* Avoid stack memory. */
-	mem_avoid[4].start = (unsigned long)free_mem_end_ptr;
-	mem_avoid[4].size = BOOT_STACK_SIZE;
+	/* Avoid params */
+	mem_avoid[3].start = (unsigned long)boot_params;
+	mem_avoid[3].size = sizeof(*boot_params);
 }
 
 /* Does this memory vector overlap a known avoided area? */
@@ -337,7 +382,7 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 	boot_params->hdr.loadflags |= KASLR_FLAG;
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init(input, input_size, output, output_size);
+	mem_avoid_init(input, input_size, output);
 
 	/* Walk e820 and find a random address. */
 	random_addr = find_random_addr(output, output_size);
maintainer
#12 lore raw

Re: [tip:x86/boot] x86/KASLR: Consolidate mem_avoid[] entries

Quoted 7 lines · tip-bot for Yinghai Lu
Commit-ID:  9dc1969c24eff8b7d7a9a565d1047b624921ba06
Gitweb:     http://git.kernel.org/tip/9dc1969c24eff8b7d7a9a565d1047b624921ba06
Author:     Yinghai Lu <[email protected]>
AuthorDate: Thu, 5 May 2016 15:13:47 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 6 May 2016 09:00:59 +0200
Quoted 5 lines

x86/KASLR: Consolidate mem_avoid[] entries

The mem_avoid[] array is used to track positions that should be avoided (like the compressed kernel, decompression code, etc) when selecting a memory position for the randomly relocated kernel. Since ZO is now at the end of

Can we stop with those ZO(MG) obfuscated abbreviations and call it simply the "compressed kernel image"?

Quoted 43 lines

the decompression buffer and the decompression code (and its heap and stack) are at the front, we can safely consolidate the decompression entry, the heap entry, and the stack entry. The boot_params memory, however, could be elsewhere, so it should be explicitly included.

[ Rwrote changelog, cleaned up code comments. ]
Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[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]>
---
 arch/x86/boot/compressed/kaslr.c | 77 +++++++++++++++++++++++++++++++---------
 1 file changed, 61 insertions(+), 16 deletions(-)
arch/x86/boot/compressed/kaslr.c +1 -1
index 2072d82..6392f00 100644
@@ -121,7 +121,7 @@ struct mem_vector {
 	unsigned long size;
 };
 
-#define MEM_AVOID_MAX 5
+#define MEM_AVOID_MAX 4
 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 
 static bool mem_contains(struct mem_vector *region, struct mem_vector *item)

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 150

Quoted 5 lines
arch/x86/boot/compressed/kaslr.c +2 -0
@@ -146,22 +146,71 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
 	return true;
 }
 
+/*
+ * In theroy, KASLR can put the kernel anywhere in area of [16M, 64T). The
	 ^^^^^^

Spellchecker please.

in the range of [...

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 152

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+ * mem_avoid array is used to store the ranges that need to be avoided when
+ * KASLR searches for a an appropriate random address. We must avoid any
			s/a //

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 165

Quoted 13 lines
arch/x86/boot/compressed/kaslr.c +13 -0
+ * regions that are unsafe to overlap with during decompression, and other
+ * things like the initrd, cmdline and boot_params.
+ *
+ * How to calculate the unsafe areas is detailed here, and is informed by
+ * the decompression calculations in header.S, and the diagram in misc.c.
+ *
+ * The compressed vmlinux (ZO) plus relocs and the run space of ZO can't be
+ * overwritten by decompression output.
+ *
+ * ZO sits against the end of the decompression buffer, so we can calculate
+ * where text, data, bss, etc of ZO are positioned.
+ *
+ * The follow are already enforced by the code:

" ... following conditions are ..."

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 171

Quoted 6 lines
arch/x86/boot/compressed/kaslr.c +6 -0
+ *  - init_size >= kernel_total_size
+ *  - input + input_len >= output + output_len
+ *  - kernel_total_size could be >= or < output_len
+ *
+ * From this, we can make several observations, illustrated by a diagram:
+ *  - init_size >= kernel_total_size

You just said this above?!

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 173

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+ *  - input + input_len > output + output_len
+ *  - kernel_total_size >= output_len

Ok, what is the point of the observations? To show that we're making the conditions enforced by the code more concrete, stricter, ...?

Quoted 7 lines
arch/x86/boot/compressed/kaslr.c +7 -0
+ *
+ * 0   output            input            input+input_len    output+init_size
+ * |     |                 |                       |                       |
+ * |     |                 |                       |                       |
+ * |-----|--------|--------|------------------|----|------------|----------|
+ *                |                           |                 |
+ *                |                           |                 |

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 190

Quoted 10 lines
arch/x86/boot/compressed/kaslr.c +10 -0
+ * output+init_size-ZO_INIT_SIZE   output+output_len  output+kernel_total_size
+ *
+ * [output, output+init_size) is for the buffer for decompressing the
+ * compressed kernel (ZO).
+ *
+ * [output, output+kernel_total_size) is for the uncompressed kernel (VO)
+ * and its bss, brk, etc.
+ * [output, output+output_len) is VO plus relocs
+ *
+ * [output+init_size-ZO_INIT_SIZE, output+init_size) is the copied ZO.

..., i.e., ZO_INIT_SIZE.

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 196

Quoted 6 lines
arch/x86/boot/compressed/kaslr.c +6 -0
+ * [input, input+input_len) is the copied compressed (VO (vmlinux after
+ * objcopy) plus relocs), not the ZO.
+ *
+ * [input+input_len, output+init_size) is [_text, _end) for ZO. That was the
+ * first range in mem_avoid, which included ZO's heap and stack. Also
+ * [input, input+input_size) need be put in mem_avoid array, but since it

" ... needs to be in the mem_avoid ..."

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 199

Quoted 3 lines
arch/x86/boot/compressed/kaslr.c +3 -0
+ * is adjacent to the first entry, they can be merged. This is how we get
+ * the first entry in mem_avoid[].
+ */

<--- my head smokes right about here. :-)

Quoted 11 lines
arch/x86/boot/compressed/kaslr.c +2 -2
 static void mem_avoid_init(unsigned long input, unsigned long input_size,
-			   unsigned long output, unsigned long output_size)
+			   unsigned long output)
 {
+	unsigned long init_size = boot_params->hdr.init_size;
 	u64 initrd_start, initrd_size;
 	u64 cmd_line, cmd_line_size;
-	unsigned long unsafe, unsafe_len;
 	char *ptr;
 
 	/*

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 213

Quoted 10 lines
arch/x86/boot/compressed/kaslr.c +3 -5
 	 * Avoid the region that is unsafe to overlap during
-	 * decompression (see calculations in ../header.S).
+	 * decompression.
 	 */
-	unsafe_len = (output_size >> 12) + 32768 + 18;
-	unsafe = (unsigned long)input + input_size - unsafe_len;
-	mem_avoid[0].start = unsafe;
-	mem_avoid[0].size = unsafe_len;
+	mem_avoid[0].start = input;
+	mem_avoid[0].size = (output + init_size) - input;

There's a define above called MEM_AVOID_MAX but the array elements are adressed with naked numbers here. Perhaps if we had defines for them too, it'll make the code a bit more understandable:

	mem_avoid[MEM_AVOID_ZO_RANGE] ...
	mem_avoid[MEM_AVOID_INITRD] ...

and so on.

Signature · 4 lines
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
author
#13 lore raw

Re: [tip:x86/boot] x86/KASLR: Consolidate mem_avoid[] entries

Quoted 8 lines · Borislav Petkov
Quoted 7 lines · tip-bot for Yinghai Lu
Commit-ID:  9dc1969c24eff8b7d7a9a565d1047b624921ba06
Gitweb:     http://git.kernel.org/tip/9dc1969c24eff8b7d7a9a565d1047b624921ba06
Author:     Yinghai Lu <[email protected]>
AuthorDate: Thu, 5 May 2016 15:13:47 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 6 May 2016 09:00:59 +0200
Quoted 8 lines
Quoted 5 lines

x86/KASLR: Consolidate mem_avoid[] entries

The mem_avoid[] array is used to track positions that should be avoided (like the compressed kernel, decompression code, etc) when selecting a memory position for the randomly relocated kernel. Since ZO is now at the end of

Can we stop with those ZO(MG) obfuscated abbreviations and call it simply the "compressed kernel image"?

I can expand them in the change logs, but it helps to keep reinforcing their names since all the variables are named using these.

Quoted 46 lines
Quoted 46 lines

the decompression buffer and the decompression code (and its heap and stack) are at the front, we can safely consolidate the decompression entry, the heap entry, and the stack entry. The boot_params memory, however, could be elsewhere, so it should be explicitly included.

[ Rwrote changelog, cleaned up code comments. ]
Cc Andrew Morton <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Andy Lutomirski <[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]>
---
 arch/x86/boot/compressed/kaslr.c | 77 +++++++++++++++++++++++++++++++---------
 1 file changed, 61 insertions(+), 16 deletions(-)
arch/x86/boot/compressed/kaslr.c +1 -1
index 2072d82..6392f00 100644
@@ -121,7 +121,7 @@ struct mem_vector {
      unsigned long size;
 };
 
-#define MEM_AVOID_MAX 5
+#define MEM_AVOID_MAX 4
 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 
 static bool mem_contains(struct mem_vector *region, struct mem_vector *item)
@@ -146,22 +146,71 @@ static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
      return true;
 }
 
Quoted 4 lines

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 150

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+/*
+ * In theroy, KASLR can put the kernel anywhere in area of [16M, 64T). The
         ^^^^^^

Spellchecker please.

Gah, thanks. No matter how many times I run through these, I keep adding more typos. :)

Quoted 31 lines

in the range of [...

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 152

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+ * mem_avoid array is used to store the ranges that need to be avoided when
+ * KASLR searches for a an appropriate random address. We must avoid any
                        s/a //

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 165

Quoted 13 lines
arch/x86/boot/compressed/kaslr.c +13 -0
+ * regions that are unsafe to overlap with during decompression, and other
+ * things like the initrd, cmdline and boot_params.
+ *
+ * How to calculate the unsafe areas is detailed here, and is informed by
+ * the decompression calculations in header.S, and the diagram in misc.c.
+ *
+ * The compressed vmlinux (ZO) plus relocs and the run space of ZO can't be
+ * overwritten by decompression output.
+ *
+ * ZO sits against the end of the decompression buffer, so we can calculate
+ * where text, data, bss, etc of ZO are positioned.
+ *
+ * The follow are already enforced by the code:

" ... following conditions are ..."

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 171

Quoted 6 lines
arch/x86/boot/compressed/kaslr.c +6 -0
+ *  - init_size >= kernel_total_size
+ *  - input + input_len >= output + output_len
+ *  - kernel_total_size could be >= or < output_len
+ *
+ * From this, we can make several observations, illustrated by a diagram:
+ *  - init_size >= kernel_total_size
Quoted 7 lines

You just said this above?!

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 173

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+ *  - input + input_len > output + output_len
+ *  - kernel_total_size >= output_len

Ok, what is the point of the observations? To show that we're making the conditions enforced by the code more concrete, stricter, ...?

This was an earlier attempt by Baoquan to fully explain the reasoning in this code since I couldn't understand it. He added the specific conditions, observations, and added the diagram. The goal is to prove that the changes to mem_avoid are safe since mistakes here lead to really hard to debug bugs.

Quoted 18 lines
Quoted 7 lines
arch/x86/boot/compressed/kaslr.c +7 -0
+ *
+ * 0   output            input            input+input_len    output+init_size
+ * |     |                 |                       |                       |
+ * |     |                 |                       |                       |
+ * |-----|--------|--------|------------------|----|------------|----------|
+ *                |                           |                 |
+ *                |                           |                 |

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 190

Quoted 10 lines
arch/x86/boot/compressed/kaslr.c +10 -0
+ * output+init_size-ZO_INIT_SIZE   output+output_len  output+kernel_total_size
+ *
+ * [output, output+init_size) is for the buffer for decompressing the
+ * compressed kernel (ZO).
+ *
+ * [output, output+kernel_total_size) is for the uncompressed kernel (VO)
+ * and its bss, brk, etc.
+ * [output, output+output_len) is VO plus relocs
+ *
+ * [output+init_size-ZO_INIT_SIZE, output+init_size) is the copied ZO.
Quoted 1 line

..., i.e., ZO_INIT_SIZE.

Well, no, these are ranges, so literally what it says. "output+init_size-ZO_INIT_SIZE" is the start of the compressed image (ZO). It's position is now found from the end of the buffer, which is output+init_size (VO's position plus VO's total run size) minus the total run size of ZO.

Quoted 8 lines

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 196

Quoted 7 lines
arch/x86/boot/compressed/kaslr.c +6 -0
+ * [input, input+input_len) is the copied compressed (VO (vmlinux after
+ * objcopy) plus relocs), not the ZO.
+ *
+ * [input+input_len, output+init_size) is [_text, _end) for ZO. That was the
+ * first range in mem_avoid, which included ZO's heap and stack. Also
+ * [input, input+input_size) need be put in mem_avoid array, but since it
Quoted 7 lines

" ... needs to be in the mem_avoid ..."

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 199

Quoted 3 lines
arch/x86/boot/compressed/kaslr.c +3 -0
+ * is adjacent to the first entry, they can be merged. This is how we get
+ * the first entry in mem_avoid[].
+ */

<--- my head smokes right about here. :-)

Heh. Yeah, and this is LESS confusing than when the ZO wasn't aligned to the end of the buffer. A whole other set of conditions vanish now. I will try to further explain these.

Quoted 22 lines
Quoted 11 lines
arch/x86/boot/compressed/kaslr.c +2 -2
 static void mem_avoid_init(unsigned long input, unsigned long input_size,
-                        unsigned long output, unsigned long output_size)
+                        unsigned long output)
 {
+     unsigned long init_size = boot_params->hdr.init_size;
      u64 initrd_start, initrd_size;
      u64 cmd_line, cmd_line_size;
-     unsigned long unsafe, unsafe_len;
      char *ptr;
 
      /*

arch/x86/boot/compressed/kaslr.c static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two) · line 213

Quoted 10 lines
arch/x86/boot/compressed/kaslr.c +3 -5
       * Avoid the region that is unsafe to overlap during
-      * decompression (see calculations in ../header.S).
+      * decompression.
       */
-     unsafe_len = (output_size >> 12) + 32768 + 18;
-     unsafe = (unsigned long)input + input_size - unsafe_len;
-     mem_avoid[0].start = unsafe;
-     mem_avoid[0].size = unsafe_len;
+     mem_avoid[0].start = input;
+     mem_avoid[0].size = (output + init_size) - input;
Quoted 8 lines

There's a define above called MEM_AVOID_MAX but the array elements are adressed with naked numbers here. Perhaps if we had defines for them too, it'll make the code a bit more understandable:

        mem_avoid[MEM_AVOID_ZO_RANGE] ...
        mem_avoid[MEM_AVOID_INITRD] ...

and so on.

Ah! Yes, excellent. I'll actually use an enum so I can get MEM_AVOID_MAX automatically.

-Kees

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

Re: [tip:x86/boot] x86/KASLR: Consolidate mem_avoid[] entries

Quoted 2 lines · Kees Cook

I can expand them in the change logs, but it helps to keep reinforcing their names since all the variables are named using these.

Sure, in the comments in the code, but the commit messages should be more dealing with the big picture and explaining to normal humans too :)

Quoted 5 lines

This was an earlier attempt by Baoquan to fully explain the reasoning in this code since I couldn't understand it. He added the specific conditions, observations, and added the diagram. The goal is to prove that the changes to mem_avoid are safe since mistakes here lead to really hard to debug bugs.

So add that last sentence :)

Quoted 5 lines

Well, no, these are ranges, so literally what it says. "output+init_size-ZO_INIT_SIZE" is the start of the compressed image (ZO). It's position is now found from the end of the buffer, which is output+init_size (VO's position plus VO's total run size) minus the total run size of ZO.

I meant the range is of ZO_INIT_SIZE size. But I like this here explanation better, maybe add it...

Quoted 3 lines

Heh. Yeah, and this is LESS confusing than when the ZO wasn't aligned to the end of the buffer. A whole other set of conditions vanish now. I will try to further explain these.

Thanks, the whole picture is certainly becoming clearer slowly, so keep doin' whatcha doin'! :-)

Quoted 2 lines

Ah! Yes, excellent. I'll actually use an enum so I can get MEM_AVOID_MAX automatically.

Yap.

Thanks.

Signature · 4 lines
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
author
#15 lore raw

PATCH v6 3/11 x86/boot: Split out kernel_ident_mapping_init

In reply to Kees Cook

From: Yinghai Lu <[email protected]>

In order to support on-demand page table creation when moving the kernel for KASLR, we need to use kernel_ident_mapping_init() in the decompression code. This splits it out into its own file for use outside of init_64.c. Additionally, checking for __pa/__va defines is added since they need to be overridden in the decompression code.

[kees: rewrote changelog]
---
 arch/x86/include/asm/page.h |  5 +++
 arch/x86/mm/ident_map.c     | 74 +++++++++++++++++++++++++++++++++++++++++++++
 arch/x86/mm/init_64.c       | 74 +--------------------------------------------
 3 files changed, 80 insertions(+), 73 deletions(-)
 create mode 100644 arch/x86/mm/ident_map.c
arch/x86/include/asm/page.h +5 -0
index 802dde30c928..cf8f619b305f 100644
@@ -37,7 +37,10 @@ static inline void copy_user_page(void *to, void *from, unsigned long vaddr,
 	alloc_page_vma(GFP_HIGHUSER | __GFP_ZERO | movableflags, vma, vaddr)
 #define __HAVE_ARCH_ALLOC_ZEROED_USER_HIGHPAGE
 
+#ifndef __pa
 #define __pa(x)		__phys_addr((unsigned long)(x))
+#endif
+
 #define __pa_nodebug(x)	__phys_addr_nodebug((unsigned long)(x))
 /* __pa_symbol should be used for C visible symbols.
    This seems to be the official gcc blessed way to do such arithmetic. */
@@ -51,7 +54,9 @@ static inline void copy_user_page(void *to, void *from, unsigned long vaddr,
 #define __pa_symbol(x) \
 	__phys_addr_symbol(__phys_reloc_hide((unsigned long)(x)))
 
+#ifndef __va
 #define __va(x)			((void *)((unsigned long)(x)+PAGE_OFFSET))
+#endif
 
 #define __boot_va(x)		__va(x)
 #define __boot_pa(x)		__pa(x)
arch/x86/mm/ident_map.c new file +74 -0

74 lines not on this page · raw message

arch/x86/mm/init_64.c +1 -73

80 lines not on this page · raw message

Signature · 1 line
2.6.3
author
#16 lore raw

PATCH v6 4/11 x86/KASLR: Build identity mappings on demand

In reply to Kees Cook

From: Yinghai Lu <[email protected]>

Currently KASLR only supports relocation in a small physical range (from 16M to 1G), due to using the initial kernel page table identity mapping. To support ranges above this, we need to have an identity mapping for the desired memory range before we can decompress (and later run) the kernel.

32-bit kernels already have the needed identity mapping. This patch adds identity mappings for the needed memory ranges on 64-bit kernels. This happens in two possible boot paths:

If loaded via startup_32, we need to set up the identity mapping we need.

If loaded from a 64-bit bootloader, the bootloader will have already set up an identity mapping, and we'll start via ZO's (arch/x86/boot/compressed/vmlinux) startup_64. In this case, the bootloader's page tables need to be avoided when we select the new VO (vmlinux) location. If not, the decompressor could overwrite them during decompression.

To accomplish avoiding the bootloader's page tables, we could walk the pagetable and find every page that is used, and add them to mem_avoid, but this needs extra code and will require increasing the size of the mem_avoid array.

Instead, we can create a new ident mapping instead, and pages for the pagetable will come from the _pagetable section of ZO, which means they are already in mem_avoid array. To do this, we reuse the code for the kernel's identity mapping.

The _pgtable will be shared by 32-bit and 64-bit path to reduce init_size, as now ZO _rodata to _end will contribute init_size.

To handle the possible mappings, we need to increase the pgt buffer size:

When booting via startup_64, as we need to cover the old VO, params, cmdline and new VO. In an extreme case we could have them all beyond the 512G boundary, which needs (2+2)*4 pages with 2M mappings. And we'll need 2 for first 2M for VGA RAM. One more is needed for level4. This gets us to 19 pages total.

When booting via startup_32, KASLR could move the new VO above 4G, so we need to set extra identity mappings for the VO, which should only need (2+2) pages at most when it is beyond the 512G boundary. So 19 pages is sufficient for this case as well.

Cc Kees Cook <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Borislav Petkov <[email protected]>
[kees: rewrote changelog]
---
 arch/x86/boot/compressed/Makefile   |  3 ++
 arch/x86/boot/compressed/head_64.S  |  4 +-
 arch/x86/boot/compressed/kaslr.c    | 14 ++++++
 arch/x86/boot/compressed/misc.h     | 11 +++++
 arch/x86/boot/compressed/misc_pgt.c | 93 +++++++++++++++++++++++++++++++++++++
 arch/x86/include/asm/boot.h         | 19 ++++++++
 6 files changed, 142 insertions(+), 2 deletions(-)
 create mode 100644 arch/x86/boot/compressed/misc_pgt.c
arch/x86/boot/compressed/Makefile +3 -0
index 77ce3a04d46e..0c5c0b50fa83 100644
@@ -75,6 +75,9 @@ vmlinux-objs-y := $(obj)/vmlinux.lds $(obj)/head_$(BITS).o $(obj)/misc.o \
 
 vmlinux-objs-$(CONFIG_EARLY_PRINTK) += $(obj)/early_serial_console.o
 vmlinux-objs-$(CONFIG_RANDOMIZE_BASE) += $(obj)/kaslr.o
+ifdef CONFIG_X86_64
+	vmlinux-objs-$(CONFIG_RANDOMIZE_BASE) += $(obj)/misc_pgt.o
+endif
 
 $(obj)/eboot.o: KBUILD_CFLAGS += -fshort-wchar -mno-red-zone
 
arch/x86/boot/compressed/head_64.S +2 -2
index 7c047002950c..0d80a7ad65cd 100644
@@ -134,7 +134,7 @@ ENTRY(startup_32)
 	/* Initialize Page tables to 0 */
 	leal	pgtable(%ebx), %edi
 	xorl	%eax, %eax
-	movl	$((4096*6)/4), %ecx
+	movl	$(BOOT_INIT_PGT_SIZE/4), %ecx
 	rep	stosl
 
 	/* Build Level 4 */
@@ -486,4 +486,4 @@ boot_stack_end:
 	.section ".pgtable","a",@nobits
 	.balign 4096
 pgtable:
-	.fill 6*4096, 1, 0
+	.fill BOOT_PGT_SIZE, 1, 0
arch/x86/boot/compressed/kaslr.c +14 -0
index 6392f0041b8a..36356fb6d4cf 100644
@@ -211,6 +211,7 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 	 */
 	mem_avoid[0].start = input;
 	mem_avoid[0].size = (output + init_size) - input;
+	fill_pagetable(mem_avoid[0].start, mem_avoid[0].size);
 
 	/* Avoid initrd. */
 	initrd_start  = (u64)boot_params->ext_ramdisk_image << 32;
@@ -219,6 +220,7 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 	initrd_size |= boot_params->hdr.ramdisk_size;
 	mem_avoid[1].start = initrd_start;
 	mem_avoid[1].size = initrd_size;
+	/* No need to set mapping for initrd */
 
 	/* Avoid kernel command line. */
 	cmd_line  = (u64)boot_params->ext_cmd_line_ptr << 32;
@@ -229,10 +231,19 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 		;
 	mem_avoid[2].start = cmd_line;
 	mem_avoid[2].size = cmd_line_size;
+	fill_pagetable(mem_avoid[2].start, mem_avoid[2].size);
 
 	/* Avoid params */
 	mem_avoid[3].start = (unsigned long)boot_params;
 	mem_avoid[3].size = sizeof(*boot_params);
+	fill_pagetable(mem_avoid[3].start, mem_avoid[3].size);
+
+	/* don't need to set mapping for setup_data */
+
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+	/* for video ram */
+	fill_pagetable(0, PMD_SIZE);
+#endif
 }
 
 /* Does this memory vector overlap a known avoided area? */
@@ -396,6 +407,9 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 		goto out;
 
 	choice = random_addr;
+
+	fill_pagetable(choice, output_size);
+	switch_pagetable();
 out:
 	return (unsigned char *)choice;
 }
arch/x86/boot/compressed/misc.h +11 -0
index 1f23d022d241..ffacded0e66a 100644
@@ -84,6 +84,17 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 }
 #endif
 
+#ifdef CONFIG_X86_64
+void fill_pagetable(unsigned long start, unsigned long size);
+void switch_pagetable(void);
+extern unsigned char _pgtable[];
+#else
+static inline void fill_pagetable(unsigned long start, unsigned long size)
+{ }
+static inline void switch_pagetable(void)
+{ }
+#endif
+
 #ifdef CONFIG_EARLY_PRINTK
 /* early_serial_console.c */
 extern int early_serial_base;
arch/x86/boot/compressed/misc_pgt.c new file +93 -0

93 lines not on this page · raw message

arch/x86/include/asm/boot.h +19 -0
index 6b8d6e8cd449..52a9cbc1419f 100644
@@ -32,7 +32,26 @@
 #endif /* !CONFIG_KERNEL_BZIP2 */
 
 #ifdef CONFIG_X86_64
+
 #define BOOT_STACK_SIZE	0x4000
+
+#define BOOT_INIT_PGT_SIZE (6*4096)
+#ifdef CONFIG_RANDOMIZE_BASE
+/*
+ * 1 page for level4, 2 pages for first 2M.
+ * (2+2)*4 pages for kernel, param, cmd_line, random kernel
+ * if all cross 512G boundary.
+ * So total will be 19 pages.
+ */
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+#define BOOT_PGT_SIZE (19*4096)
+#else
+#define BOOT_PGT_SIZE (17*4096)
+#endif
+#else
+#define BOOT_PGT_SIZE BOOT_INIT_PGT_SIZE
+#endif
+
 #else
 #define BOOT_STACK_SIZE	0x1000
 #endif
Signature · 1 line
2.6.3
#17 lore raw

Re: [PATCH v6 04/11] x86/KASLR: Build identity mappings on demand

Quoted 41 lines · Kees Cook

From: Yinghai Lu <[email protected]>

Currently KASLR only supports relocation in a small physical range (from 16M to 1G), due to using the initial kernel page table identity mapping. To support ranges above this, we need to have an identity mapping for the desired memory range before we can decompress (and later run) the kernel.

32-bit kernels already have the needed identity mapping. This patch adds identity mappings for the needed memory ranges on 64-bit kernels. This happens in two possible boot paths:

If loaded via startup_32, we need to set up the identity mapping we need.

If loaded from a 64-bit bootloader, the bootloader will have already set up an identity mapping, and we'll start via ZO's (arch/x86/boot/compressed/vmlinux) startup_64. In this case, the bootloader's page tables need to be avoided when we select the new VO (vmlinux) location. If not, the decompressor could overwrite them during decompression.

To accomplish avoiding the bootloader's page tables, we could walk the pagetable and find every page that is used, and add them to mem_avoid, but this needs extra code and will require increasing the size of the mem_avoid array.

Instead, we can create a new ident mapping instead, and pages for the pagetable will come from the _pagetable section of ZO, which means they are already in mem_avoid array. To do this, we reuse the code for the kernel's identity mapping.

The _pgtable will be shared by 32-bit and 64-bit path to reduce init_size, as now ZO _rodata to _end will contribute init_size.

To handle the possible mappings, we need to increase the pgt buffer size:

When booting via startup_64, as we need to cover the old VO, params, cmdline and new VO. In an extreme case we could have them all beyond the 512G boundary, which needs (2+2)*4 pages with 2M mappings. And we'll need 2 for first 2M for VGA RAM. One more is needed for level4. This gets us to 19 pages total.

Quoted 4 lines

When booting via startup_32, KASLR could move the new VO above 4G, so we need to set extra identity mappings for the VO, which should only need (2+2) pages at most when it is beyond the 512G boundary. So 19 pages is sufficient for this case as well.

In changelogs and comments please refer to C functions and symbols that point to executable code via '()', i.e. startup_64(), etc.

arch/x86/boot/compressed/kaslr.c static void mem_avoid_init(unsigned long input, unsigned long input_size, · line 244

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+	/* for video ram */

Please capitalize RAM and generally free flowing comment sentences, i.e.:

arch/x86/boot/compressed/misc.h unsigned char *choose_random_location(unsigned char *input_ptr, · line 89

Quoted 5 lines
arch/x86/boot/compressed/misc.h +4 -0
+	/* For video RAM: */
 
+#ifdef CONFIG_X86_64
+void fill_pagetable(unsigned long start, unsigned long size);
+void switch_pagetable(void);

These are very ambiguous function names. Which pagetables are these? Kernel or user? Is it boot time or final page tables? etc.

Also what does the switching do?

arch/x86/boot/compressed/misc_pgt.c line 10

Quoted 13 lines
arch/x86/boot/compressed/misc_pgt.c new file +10 -0
@@ -0,0 +1,93 @@
+#define __pa(x)  ((unsigned long)(x))
+#define __va(x)  ((void *)((unsigned long)(x)))
+
+#include "misc.h"
+
+#include <asm/init.h>
+#include <asm/pgtable.h>
+
+#include "../../mm/ident_map.c"
+#include "../string.h"

Again a new .c file with no comments whatsoever :-(

Also, we just decided that 'misc.c' was a bad name. Is there really no better name than misc_pgt.c?

arch/x86/boot/compressed/misc_pgt.c line 18

Quoted 7 lines
arch/x86/boot/compressed/misc_pgt.c new file +7 -0
+struct alloc_pgt_data {
+	unsigned char *pgt_buf;
+	unsigned long pgt_buf_size;
+	unsigned long pgt_buf_offset;
+};
+
+static void *alloc_pgt_page(void *context)

Non-obvious functions with no comments describing them.

arch/x86/boot/compressed/misc_pgt.c line 46

Quoted 4 lines
arch/x86/boot/compressed/misc_pgt.c new file +4 -0
+unsigned long __force_order;
+static struct alloc_pgt_data pgt_data;
+static struct x86_mapping_info mapping_info;
+static pgd_t *level4p;

What's this __force_order flag? Why does it have double underscores?

arch/x86/boot/compressed/misc_pgt.c line 60

Quoted 12 lines
arch/x86/boot/compressed/misc_pgt.c new file +12 -0
+{
+	unsigned long end = start + size;
+
+	if (!level4p) {
+		pgt_data.pgt_buf_offset = 0;
+		mapping_info.alloc_pgt_page = alloc_pgt_page;
+		mapping_info.context = &pgt_data;
+		mapping_info.pmd_flag = __PAGE_KERNEL_LARGE_EXEC;
+
+		/*
+		 * come from startup_32 ?
+		 * then cr3 is _pgtable, we can reuse it.

come what? What does this comment mean??

arch/x86/boot/compressed/misc_pgt.c line 35

Quoted 2 lines
arch/x86/boot/compressed/misc_pgt.c new file +2 -0
+		 */
+		level4p = (pgd_t *)read_cr3();

Argh, another type cast. A quick check shows:

+static pgd_t *level4p;
+ if (!level4p) {
+ level4p = (pgd_t *)read_cr3();
+ if ((unsigned long)level4p == (unsigned long)_pgtable) {
+ level4p = (pgd_t *)alloc_pgt_page(&pgt_data);
+ kernel_ident_mapping_init(&mapping_info, level4p, start, end);
+ write_cr3((unsigned long)level4p);

... that the natural type for level4p would be unsigned long, not pgt_t ...

arch/x86/boot/compressed/misc_pgt.c line 69

Quoted 7 lines
arch/x86/boot/compressed/misc_pgt.c new file +7 -0
+		if ((unsigned long)level4p == (unsigned long)_pgtable) {
+			pgt_data.pgt_buf = (unsigned char *)_pgtable +
+						 BOOT_INIT_PGT_SIZE;
+			pgt_data.pgt_buf_size = BOOT_PGT_SIZE -
+						 BOOT_INIT_PGT_SIZE;
+			memset((unsigned char *)pgt_data.pgt_buf, 0,
+				pgt_data.pgt_buf_size);

Is that (unsigned char *) type cast really necessary??

Type casts are the absolute exception, we avoid them whenever possible - and this code is using them like candy :-(

Also, for heaven's sake, either ignore checkpatch.pl whining, or avoid the excessive indentation by using helper functions (or some other technique).

Quoted 41 lines
arch/x86/boot/compressed/misc_pgt.c new file +24 -0
+			debug_putstr("boot via startup_32\n");
+		} else {
+			pgt_data.pgt_buf = (unsigned char *)_pgtable;
+			pgt_data.pgt_buf_size = BOOT_PGT_SIZE;
+			memset((unsigned char *)pgt_data.pgt_buf, 0,
+				pgt_data.pgt_buf_size);
+			debug_putstr("boot via startup_64\n");
+			level4p = (pgd_t *)alloc_pgt_page(&pgt_data);
+		}
+	}
+
+	/* align boundary to 2M */
+	start = round_down(start, PMD_SIZE);
+	end = round_up(end, PMD_SIZE);
+	if (start >= end)
+		return;
+
+	kernel_ident_mapping_init(&mapping_info, level4p, start, end);
+}
+
+void switch_pagetable(void)
+{
+	write_cr3((unsigned long)level4p);
+}
arch/x86/include/asm/boot.h +8 -0
index 6b8d6e8cd449..52a9cbc1419f 100644
@@ -32,7 +32,26 @@
 #endif /* !CONFIG_KERNEL_BZIP2 */
 
 #ifdef CONFIG_X86_64
+
 #define BOOT_STACK_SIZE	0x4000
+
+#define BOOT_INIT_PGT_SIZE (6*4096)
+#ifdef CONFIG_RANDOMIZE_BASE
+/*
+ * 1 page for level4, 2 pages for first 2M.
+ * (2+2)*4 pages for kernel, param, cmd_line, random kernel
+ * if all cross 512G boundary.

arch/x86/include/asm/boot.h line 53

Quoted 10 lines
arch/x86/include/asm/boot.h +10 -0
+ * So total will be 19 pages.
+ */
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+#define BOOT_PGT_SIZE (19*4096)
+#else
+#define BOOT_PGT_SIZE (17*4096)
+#endif
+#else
+#define BOOT_PGT_SIZE BOOT_INIT_PGT_SIZE
+#endif

Please use proper nesting of defines to make it more readable, i.e. something like:

#define BOOT_INIT_PGT_SIZE (6*4096)

#ifdef CONFIG_RANDOMIZE_BASE
/*
* 1 page for level4, 2 pages for first 2M.
* (2+2)*4 pages for kernel, param, cmd_line, random kernel
* if all cross 512G boundary.
* So total will be 19 pages.
*/

# ifdef CONFIG_X86_VERBOSE_BOOTUP
#  define BOOT_PGT_SIZE (19*4096)
# else
#  define BOOT_PGT_SIZE (17*4096)
# endif
#else
# define BOOT_PGT_SIZE BOOT_INIT_PGT_SIZE
#endif

but more importantly, BOOT_PGT_SIZE is really a bad name for this. Since it's used by an allocator it's clear that this is a _maximum_. Why not put that fact into the name??

Basically you took a butt-ugly patch from Yinghai that shat all over the kernel and rewrote its changelog - but that's not enough to make it acceptable! As a general rule, most Yinghai patches I've seen in the past couple of years were butt-ugly. If you take a patch from Yinghai you have to completely rewrite it in most cases.

So I'm really annoyed, I see myself repeating the same kind of review feedback I gave to Yinghai again and again, and now to you?

If it's less work for you then please rewrite Yinghai's patches from scratch - and possibly split them up as well wherever possible, as they are risky as hell.

I've applied the first two patches because they look OK, but _please_ do a proper job with the rest of the series as well!

Thanks,

Ingo

author
#18 lore raw

Re: [PATCH v6 04/11] x86/KASLR: Build identity mappings on demand

Quoted 234 lines · Ingo Molnar
Quoted 41 lines · Kees Cook

From: Yinghai Lu <[email protected]>

Currently KASLR only supports relocation in a small physical range (from 16M to 1G), due to using the initial kernel page table identity mapping. To support ranges above this, we need to have an identity mapping for the desired memory range before we can decompress (and later run) the kernel.

32-bit kernels already have the needed identity mapping. This patch adds identity mappings for the needed memory ranges on 64-bit kernels. This happens in two possible boot paths:

If loaded via startup_32, we need to set up the identity mapping we need.

If loaded from a 64-bit bootloader, the bootloader will have already set up an identity mapping, and we'll start via ZO's (arch/x86/boot/compressed/vmlinux) startup_64. In this case, the bootloader's page tables need to be avoided when we select the new VO (vmlinux) location. If not, the decompressor could overwrite them during decompression.

To accomplish avoiding the bootloader's page tables, we could walk the pagetable and find every page that is used, and add them to mem_avoid, but this needs extra code and will require increasing the size of the mem_avoid array.

Instead, we can create a new ident mapping instead, and pages for the pagetable will come from the _pagetable section of ZO, which means they are already in mem_avoid array. To do this, we reuse the code for the kernel's identity mapping.

The _pgtable will be shared by 32-bit and 64-bit path to reduce init_size, as now ZO _rodata to _end will contribute init_size.

To handle the possible mappings, we need to increase the pgt buffer size:

When booting via startup_64, as we need to cover the old VO, params, cmdline and new VO. In an extreme case we could have them all beyond the 512G boundary, which needs (2+2)*4 pages with 2M mappings. And we'll need 2 for first 2M for VGA RAM. One more is needed for level4. This gets us to 19 pages total.

Quoted 4 lines

When booting via startup_32, KASLR could move the new VO above 4G, so we need to set extra identity mappings for the VO, which should only need (2+2) pages at most when it is beyond the 512G boundary. So 19 pages is sufficient for this case as well.

In changelogs and comments please refer to C functions and symbols that point to executable code via '()', i.e. startup_64(), etc.

arch/x86/boot/compressed/kaslr.c static void mem_avoid_init(unsigned long input, unsigned long input_size, · line 244

Quoted 2 lines
arch/x86/boot/compressed/kaslr.c +2 -0
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+     /* for video ram */

Please capitalize RAM and generally free flowing comment sentences, i.e.:

arch/x86/boot/compressed/misc.h unsigned char *choose_random_location(unsigned char *input_ptr, · line 89

Quoted 5 lines
arch/x86/boot/compressed/misc.h +4 -0
+     /* For video RAM: */
 
+#ifdef CONFIG_X86_64
+void fill_pagetable(unsigned long start, unsigned long size);
+void switch_pagetable(void);

These are very ambiguous function names. Which pagetables are these? Kernel or user? Is it boot time or final page tables? etc.

Also what does the switching do?

arch/x86/boot/compressed/misc_pgt.c line 10

Quoted 13 lines
arch/x86/boot/compressed/misc_pgt.c new file +10 -0
@@ -0,0 +1,93 @@
+#define __pa(x)  ((unsigned long)(x))
+#define __va(x)  ((void *)((unsigned long)(x)))
+
+#include "misc.h"
+
+#include <asm/init.h>
+#include <asm/pgtable.h>
+
+#include "../../mm/ident_map.c"
+#include "../string.h"

Again a new .c file with no comments whatsoever :-(

Also, we just decided that 'misc.c' was a bad name. Is there really no better name than misc_pgt.c?

arch/x86/boot/compressed/misc_pgt.c line 18

Quoted 7 lines
arch/x86/boot/compressed/misc_pgt.c new file +7 -0
+struct alloc_pgt_data {
+     unsigned char *pgt_buf;
+     unsigned long pgt_buf_size;
+     unsigned long pgt_buf_offset;
+};
+
+static void *alloc_pgt_page(void *context)

Non-obvious functions with no comments describing them.

arch/x86/boot/compressed/misc_pgt.c line 46

Quoted 4 lines
arch/x86/boot/compressed/misc_pgt.c new file +4 -0
+unsigned long __force_order;
+static struct alloc_pgt_data pgt_data;
+static struct x86_mapping_info mapping_info;
+static pgd_t *level4p;

What's this __force_order flag? Why does it have double underscores?

arch/x86/boot/compressed/misc_pgt.c line 60

Quoted 12 lines
arch/x86/boot/compressed/misc_pgt.c new file +12 -0
+{
+     unsigned long end = start + size;
+
+     if (!level4p) {
+             pgt_data.pgt_buf_offset = 0;
+             mapping_info.alloc_pgt_page = alloc_pgt_page;
+             mapping_info.context = &pgt_data;
+             mapping_info.pmd_flag = __PAGE_KERNEL_LARGE_EXEC;
+
+             /*
+              * come from startup_32 ?
+              * then cr3 is _pgtable, we can reuse it.

come what? What does this comment mean??

arch/x86/boot/compressed/misc_pgt.c line 35

Quoted 2 lines
arch/x86/boot/compressed/misc_pgt.c new file +2 -0
+              */
+             level4p = (pgd_t *)read_cr3();

Argh, another type cast. A quick check shows:

arch/x86/boot/compressed/misc_pgt.c new file +7 -0
+static pgd_t *level4p;
+       if (!level4p) {
+               level4p = (pgd_t *)read_cr3();
+               if ((unsigned long)level4p == (unsigned long)_pgtable) {
+                       level4p = (pgd_t *)alloc_pgt_page(&pgt_data);
+       kernel_ident_mapping_init(&mapping_info, level4p, start, end);
+       write_cr3((unsigned long)level4p);

... that the natural type for level4p would be unsigned long, not pgt_t ...

arch/x86/boot/compressed/misc_pgt.c line 69

Quoted 7 lines
arch/x86/boot/compressed/misc_pgt.c new file +7 -0
+             if ((unsigned long)level4p == (unsigned long)_pgtable) {
+                     pgt_data.pgt_buf = (unsigned char *)_pgtable +
+                                              BOOT_INIT_PGT_SIZE;
+                     pgt_data.pgt_buf_size = BOOT_PGT_SIZE -
+                                              BOOT_INIT_PGT_SIZE;
+                     memset((unsigned char *)pgt_data.pgt_buf, 0,
+                             pgt_data.pgt_buf_size);

Is that (unsigned char *) type cast really necessary??

Type casts are the absolute exception, we avoid them whenever possible - and this code is using them like candy :-(

Also, for heaven's sake, either ignore checkpatch.pl whining, or avoid the excessive indentation by using helper functions (or some other technique).

Quoted 41 lines
arch/x86/boot/compressed/misc_pgt.c new file +24 -0
+                     debug_putstr("boot via startup_32\n");
+             } else {
+                     pgt_data.pgt_buf = (unsigned char *)_pgtable;
+                     pgt_data.pgt_buf_size = BOOT_PGT_SIZE;
+                     memset((unsigned char *)pgt_data.pgt_buf, 0,
+                             pgt_data.pgt_buf_size);
+                     debug_putstr("boot via startup_64\n");
+                     level4p = (pgd_t *)alloc_pgt_page(&pgt_data);
+             }
+     }
+
+     /* align boundary to 2M */
+     start = round_down(start, PMD_SIZE);
+     end = round_up(end, PMD_SIZE);
+     if (start >= end)
+             return;
+
+     kernel_ident_mapping_init(&mapping_info, level4p, start, end);
+}
+
+void switch_pagetable(void)
+{
+     write_cr3((unsigned long)level4p);
+}
arch/x86/include/asm/boot.h +8 -0
index 6b8d6e8cd449..52a9cbc1419f 100644
@@ -32,7 +32,26 @@
 #endif /* !CONFIG_KERNEL_BZIP2 */
 
 #ifdef CONFIG_X86_64
+
 #define BOOT_STACK_SIZE      0x4000
+
+#define BOOT_INIT_PGT_SIZE (6*4096)
+#ifdef CONFIG_RANDOMIZE_BASE
+/*
+ * 1 page for level4, 2 pages for first 2M.
+ * (2+2)*4 pages for kernel, param, cmd_line, random kernel
+ * if all cross 512G boundary.

arch/x86/include/asm/boot.h line 53

Quoted 10 lines
arch/x86/include/asm/boot.h +10 -0
+ * So total will be 19 pages.
+ */
+#ifdef CONFIG_X86_VERBOSE_BOOTUP
+#define BOOT_PGT_SIZE (19*4096)
+#else
+#define BOOT_PGT_SIZE (17*4096)
+#endif
+#else
+#define BOOT_PGT_SIZE BOOT_INIT_PGT_SIZE
+#endif

Please use proper nesting of defines to make it more readable, i.e. something like:

#define BOOT_INIT_PGT_SIZE (6*4096)

#ifdef CONFIG_RANDOMIZE_BASE
/*
* 1 page for level4, 2 pages for first 2M.
* (2+2)*4 pages for kernel, param, cmd_line, random kernel
* if all cross 512G boundary.
* So total will be 19 pages.
*/

# ifdef CONFIG_X86_VERBOSE_BOOTUP
#  define BOOT_PGT_SIZE (19*4096)
# else
#  define BOOT_PGT_SIZE (17*4096)
# endif
#else
# define BOOT_PGT_SIZE BOOT_INIT_PGT_SIZE
#endif

but more importantly, BOOT_PGT_SIZE is really a bad name for this. Since it's used by an allocator it's clear that this is a _maximum_. Why not put that fact into the name??

Basically you took a butt-ugly patch from Yinghai that shat all over the kernel and rewrote its changelog - but that's not enough to make it acceptable! As a general rule, most Yinghai patches I've seen in the past couple of years were butt-ugly. If you take a patch from Yinghai you have to completely rewrite it in most cases.

Quoted 5 lines

So I'm really annoyed, I see myself repeating the same kind of review feedback I gave to Yinghai again and again, and now to you?

If it's less work for you then please rewrite Yinghai's patches from scratch - and possibly split them up as well wherever possible, as they are risky as hell.

Okay, noted. I'll rewrite them. And really, at this point, I've mostly rewritten half of them as it is, so easier to just keep going with it.

Quoted 2 lines

I've applied the first two patches because they look OK, but _please_ do a proper job with the rest of the series as well!

Okay, I'll give it a shot!

-Kees

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

PATCH v6 5/11 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 36356fb6d4cf..dc9ffceb556b 100644
@@ -275,8 +275,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
author
#20 lore raw

PATCH v6 6/11 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 dc9ffceb556b..391960e2cb08 100644
@@ -246,15 +246,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. */
@@ -265,13 +274,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];
@@ -328,7 +339,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)
@@ -367,7 +378,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
author
#21 lore raw

PATCH v6 7/11 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" for clarity and 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 391960e2cb08..05f564b6c70e 100644
@@ -384,8 +384,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;
@@ -395,12 +395,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;
+}
+
 unsigned char *choose_random_location(unsigned char *input_ptr,
 				      unsigned long input_size,
 				      unsigned char *output_ptr,
@@ -436,7 +460,7 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 	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
author
#22 lore raw

PATCH v6 8/11 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 05f564b6c70e..3672c7388e5a 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");
@@ -332,7 +333,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,
@@ -420,7 +421,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
author
#23 lore raw

PATCH v6 9/11 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 | 42 +++++++++++++++++++----------------
 arch/x86/boot/compressed/misc.c  | 47 +++++++++++++++++++++++++---------------
 arch/x86/boot/compressed/misc.h  | 22 ++++++++++---------
 3 files changed, 64 insertions(+), 47 deletions(-)
arch/x86/boot/compressed/kaslr.c +23 -19
index 3672c7388e5a..58d0871be037 100644
@@ -426,10 +426,11 @@ static unsigned long find_random_virt_addr(unsigned long minimum,
 	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
 }
 
-unsigned char *choose_random_location(unsigned char *input_ptr,
-				      unsigned long input_size,
-				      unsigned char *output_ptr,
-				      unsigned long output_size)
+void choose_random_location(unsigned char *input_ptr,
+				unsigned long input_size,
+				unsigned char **output_ptr,
+				unsigned long output_size,
+				unsigned char **virt_addr)
 {
 	/*
 	 * The caller of choose_random_location() uses unsigned char * for
@@ -439,19 +440,21 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 	 * more casts into extract_kernel, do them here and at return.
 	 */
 	unsigned long input = (unsigned long)input_ptr;
-	unsigned long output = (unsigned long)output_ptr;
-	unsigned long choice = output;
+	unsigned long output = (unsigned long)*output_ptr;
 	unsigned long random_addr;
 
+	/* By default, keep output position unchanged. */
+	*virt_addr = *output_ptr;
+
 #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
 
@@ -464,17 +467,18 @@ unsigned char *choose_random_location(unsigned char *input_ptr,
 	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) {
+			fill_pagetable(random_addr, output_size);
+			switch_pagetable();
+			*output_ptr = (unsigned char *)random_addr;
+		}
 	}
 
-	/* Always enforce the minimum. */
-	if (random_addr < choice)
-		goto out;
-
-	choice = random_addr;
-
-	fill_pagetable(choice, output_size);
-	switch_pagetable();
-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 = (unsigned char *)random_addr;
 }
arch/x86/boot/compressed/misc.c +29 -18

98 lines not on this page · raw message

arch/x86/boot/compressed/misc.h +12 -10
index ffacded0e66a..1a58fce66458 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 char *input_ptr,
-				      unsigned long input_size,
-				      unsigned char *output_ptr,
-				      unsigned long output_size);
+void choose_random_location(unsigned char *input_ptr,
+			    unsigned long input_size,
+			    unsigned char **output_ptr,
+			    unsigned long output_size,
+			    unsigned char **virt_addr);
 /* cpuflags.c */
 bool has_cpuflag(int flag);
 #else
-static inline
-unsigned char *choose_random_location(unsigned char *input_ptr,
-				      unsigned long input_size,
-				      unsigned char *output_ptr,
-				      unsigned long output_size)
+static inline void choose_random_location(unsigned char *input_ptr,
+					  unsigned long input_size,
+					  unsigned char **output_ptr,
+					  unsigned long output_size,
+					  unsigned char **virt_addr)
 {
-	return output_ptr;
+	/* No change from existing output location. */
+	*virt_addr = *output_ptr;
 }
 #endif
 
Signature · 1 line
2.6.3
author
#24 lore raw

PATCH v6 10/11 x86/KASLR: Add physical address randomization >4G

In reply to Kees Cook

From: Baoquan He <[email protected]>

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.

[kees: rewrote changelog, refactored goto into while]
[kees: limit 32-bit to KERNEL_IMAGE_SIZE]
[kees: squash dead-code removal into this patch]
[kees: refactored to use new mem_overlap code, renamed variables]
[kees: updated Kconfig to reflect updated implementation]
---
 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..39be0f7b49ef 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 is
+	  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
#25 lore raw

Re: [PATCH v6 10/11] x86/KASLR: Add physical address randomization >4G

Hi Kees,

Quoted 5 lines · Kees Cook

From: Baoquan He <[email protected]>

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

Sorry, I didn't get what you said about lifting the limitation for 64-bit. Do you mean 32-bit?

Thanks
Baoquan

Quoted 239 lines

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.

[kees: rewrote changelog, refactored goto into while]
[kees: limit 32-bit to KERNEL_IMAGE_SIZE]
[kees: squash dead-code removal into this patch]
[kees: refactored to use new mem_overlap code, renamed variables]
[kees: updated Kconfig to reflect updated implementation]
---
 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..39be0f7b49ef 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 is
+	  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
index 58d0871be037..8cf705826bdc 100644
@@ -125,17 +125,6 @@ struct mem_vector {
 #define MEM_AVOID_MAX 4
 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. */
@@ -286,8 +275,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;
@@ -318,36 +305,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. */
@@ -357,31 +352,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;
 	}
 }
 
@@ -398,6 +417,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();
Signature · 1 line
2.6.3
author
#26 lore raw

Re: [PATCH v6 10/11] x86/KASLR: Add physical address randomization >4G

Quoted 11 lines · Baoquan He

Hi Kees,

Quoted 5 lines · Kees Cook

From: Baoquan He <[email protected]>

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

Sorry, I didn't get what you said about lifting the limitation for 64-bit. Do you mean 32-bit?

Prior to this patch, physical address randomization was limited to KERNEL_IMAGE_SIZE on x86_64. After this patch, that limit is lifted for x86_64 but 32-bit remains limited to KERNEL_IMAGE_SIZE being the upper physical memory position.

Quoted 147 lines

Thanks
Baoquan

Quoted 142 lines

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.

[kees: rewrote changelog, refactored goto into while]
[kees: limit 32-bit to KERNEL_IMAGE_SIZE]
[kees: squash dead-code removal into this patch]
[kees: refactored to use new mem_overlap code, renamed variables]
[kees: updated Kconfig to reflect updated implementation]
---
 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..39be0f7b49ef 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 is
+       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 +19 -24
index 58d0871be037..8cf705826bdc 100644
@@ -125,17 +125,6 @@ struct mem_vector {
 #define MEM_AVOID_MAX 4
 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. */
@@ -286,8 +275,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;
@@ -318,36 +305,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;
 
Quoted 5 lines

arch/x86/boot/compressed/kaslr.c static void store_slot_info(struct mem_vector *region, unsigned long image_size) · line 346

Quoted 5 lines
arch/x86/boot/compressed/kaslr.c +2 -2
-     /* 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;

Since physical and virtual are not separated on 32-bit, it means the 32-bit physical address selection becomes the virtual address selection, and as such, it cannot be above KERNEL_IMAGE_SIZE on 32-bit.

-Kees

Quoted 92 lines
Quoted 92 lines
arch/x86/boot/compressed/kaslr.c +48 -21
      /* Ignore entries entirely below our minimum. */
@@ -357,31 +352,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;
      }
 }
 
@@ -398,6 +417,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

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

Re: [PATCH v6 10/11] x86/KASLR: Add physical address randomization >4G

Quoted 10 lines · Kees Cook
Quoted 9 lines · Baoquan He

Hi Kees,

Quoted 5 lines · Kees Cook

From: Baoquan He <[email protected]>

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

Quoted 7 lines
Quoted 2 lines

Sorry, I didn't get what you said about lifting the limitation for 64-bit. Do you mean 32-bit?

Prior to this patch, physical address randomization was limited to KERNEL_IMAGE_SIZE on x86_64. After this patch, that limit is lifted for x86_64 but 32-bit remains limited to KERNEL_IMAGE_SIZE being the upper physical memory position.

Ah, yes. This is lifting the limitation of physical addr from KERNEL_IMAGE_SIZE to max available physical addr. I must have been dizzy, please forgive my noise.

Quoted 259 lines
Quoted 148 lines

Thanks
Baoquan

Quoted 142 lines

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.

[kees: rewrote changelog, refactored goto into while]
[kees: limit 32-bit to KERNEL_IMAGE_SIZE]
[kees: squash dead-code removal into this patch]
[kees: refactored to use new mem_overlap code, renamed variables]
[kees: updated Kconfig to reflect updated implementation]
---
 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..39be0f7b49ef 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 is
+       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 +19 -24
index 58d0871be037..8cf705826bdc 100644
@@ -125,17 +125,6 @@ struct mem_vector {
 #define MEM_AVOID_MAX 4
 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. */
@@ -286,8 +275,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;
@@ -318,36 +305,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;
 
Quoted 5 lines

arch/x86/boot/compressed/kaslr.c static void store_slot_info(struct mem_vector *region, unsigned long image_size) · line 346

Quoted 5 lines
arch/x86/boot/compressed/kaslr.c +2 -2
-     /* 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;

Since physical and virtual are not separated on 32-bit, it means the 32-bit physical address selection becomes the virtual address selection, and as such, it cannot be above KERNEL_IMAGE_SIZE on 32-bit.

-Kees

Quoted 92 lines
Quoted 92 lines
arch/x86/boot/compressed/kaslr.c +48 -21
      /* Ignore entries entirely below our minimum. */
@@ -357,31 +352,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;
      }
 }
 
@@ -398,6 +417,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

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

PATCH v6 11/11 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 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 which ever 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 8cf705826bdc..ace41822d16f 100644
@@ -464,7 +464,7 @@ void choose_random_location(unsigned char *input_ptr,
 	 */
 	unsigned long input = (unsigned long)input_ptr;
 	unsigned long output = (unsigned long)*output_ptr;
-	unsigned long random_addr;
+	unsigned long random_addr, min_addr;
 
 	/* By default, keep output position unchanged. */
 	*virt_addr = *output_ptr;
@@ -486,8 +486,11 @@ void choose_random_location(unsigned char *input_ptr,
 	/* 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